ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [ 운영체제 ] 세마포어( Semaphore ) 와 Mutex, deadlock, starvation, priority inversion
    컴퓨터/운영체제 2020. 11. 15. 20:09

    Q. busy waiting

    * What is a Semaphore?

     

    - A semaphore is an integer variable, shared among multiple processes. The main aim of using a semaphore is process synchronization and access control for a common resource in a concurrent environment.

    - 예츠허르 다익스트라가 제안한 교착 상태에 대한 해법으로 두개의 Atomic한 함수로 제어되는 정수 변수

    멀티프로그래밍 환경에서 공유자원에 대한 접근 제어 알고리즘, 상호배제 원리를 보장하는 알고리즘(Mutual Exclusion)

    - 임계구역에 대하여 각각의 프로세스들의 접근을 제어하고 프로세스 사이의 동기를 유지한다.

    - 여러 개의 프로세스가 동시에 그 값을 수정하거나 접근하지 못한다.

    세마포어에 대한 연산은 처리 중에 인터럽트 되어서는 안 된다.

     

    [ 유래 ]

    과거 기찻길에서는 깃발 표식으로 기차 이동을 통제했다. 깃발을 Semaphore라고 한다.

    파란색 깃발이면 지나갈 수 있고, 빨간색 깃발이면 대기 후 다른 기차를 먼저 보내고 진행했다.

     

    * Mutex와의 비교

     

    - 세마포어와 마찬가지로 병행 처리를 위한 프로세스(process or thread) 동기화 기법의 하나

    - A semaphore is a signaling mechanism where on the other hand, a mutex is a locking mechanism.

    - 세마포어는 허용치만큼 프로세스가 접근 가능한 반면, 뮤텍스는 하나의 프로세스만 접근 가능

    - 세마포어는 수행중인 프로세스 외에 다른 프로세스가 세마포어를 해제할 수 있으나, <- ???

    뮤텍스는 수행중인 프로세스만 lock을 해제할 수 있다.

    - 뮤텍스는 제어되는 섹션에 하나의 Thread만 허용하기 때문에 해당 섹션에 접근하려는 다른 Thread들을 강제적으로 막아 첫 번째 Thread가 세션에서 빠져 나올 때까지 대기한다.

    https://www.youtube.com/watch?v=481K0TaM-6U

     

    - 사용할 수 있는 공유자원의 개수, shared data의 개수, 따라서 0,1,2,3... (counting Semaphore)

    값은 0 또는 1, 누가 쓰면 0이고 비어 있으면 1 ( binary semaphore : 0 또는 1의 값만 가짐 )

    Note : Lock은 누가 사용하면 1

    - It's a synchronization tool that does not requrie busy waiting. Hence, the operating system does not waste the CPU cycles when a process can't operate due to a lack of access to a resource.

    - With careful use, a semaphore is a powerful synchronization tool that can enable process synchronization.

     

    * Semaphore Operations

     

    세마포어 s는 정수값을 가지는 변수이며 P와 V라는 명령에 의해서만 접근할 수 있다

    - shared data는 semaphore s;

    - 잠자기와 깨우기의 연산을 이용하며, 공유 자원의 수를 나타내는 변수 세마포어변수 S라고 한다.

    세마포어 변수는 일반적으로 정수형 변수(0, 양의 정수)를 사용한다.

    - A semaphore has two indivisible (atomic) operations, namely: wait and signal. These operations are sometimes referred to as P and V, or down and up in some contexts.

    (P와 V는 각각 try와 increment를 뜻하는 네덜란드어 Proberen과 Verhogen의 머릿글자를 딴 것이다)

    💡 V조작은 큐에 대기 중인 프로세스를 깨우는 신호(Wake-up)로서, 흔히 Signal 동작이라 한다.

    💡 P 조작은 임계 영역을 사용하려는 프로세스들의 진입여부를 결정하는 조작으로, 흔히 Wait 동작이라 한다.

    - the waitfor and signal operations are implemented as system calls.

    - wait와 signal을 통해서만 s가 수정가능하면 동시에 동작할수는 없다

     

    [ 예시 1 ]

    function wait(S) {
        while (s<=0) {} // s 변수값이 0이하면 루프문에 갇히도록, 인터럽트 차단 목적
        s=s-1;
    }
    
    function signal(s) {
        s = s+1; // 다른 프로세스가 임계구역에 진입할 수 있도록 허용
    }
    
    do {
        wait(S);
        signal(s);
    } while(true);

     

    # 예시 2

    [ Semaphore Wait Operation : P(s) ]

    Function wait(S) is
        if S>0 then
            /* do not block the process */
            S <- S-1;
            return;
        else
            /* block the calling process */
            sleep;
        end
    end

    할당 가능한 자원이 없으면 the call process is put to sleep.

     

    [ Signal Operation : V(s) ]

    Function signal(S) is
        if there are processes sleeping on S then
            select a process to wake up;
            wake up the selected process;
            return;
        else
            /* no process is waiting on S */
            S <-S+1;
            return;
        end;
    end

    If there are other processes are waiting for the resource, a  waiting process is selected to be wakened up by the operating system scheduler. As a result, that process gains control of the resource.

     

    * Semaphore Types

     

    1) Binary semaphore ( 이진형 세마포어 ): can have only two integer values, 0 or 1.

     0과 1의 값, 한 개의 공유자원을 상호배제

    provides mutual exclusion. use to solve the critical section

    - Test-and-Set 등 하드웨어 지원 기능을 이용하여 구현 가능하다

    Note : 세마포어에 대한 연산은 소프트웨어나 하드웨어로 구현 가능하다

     

    2) Counting Semaphore ( 계수형 세마포어 ) : an integer value, which can range over an unrestricted domain

    0과 양의 정수, 여러개의 공유자원을 상호배제

    use to solve synchronization problems like resource allocation.

     

    3) 강성 세마포어 : 프로세스 wake up시 큐에서 선입선출 방식으로 추출

    4) 약성 세마포어 : 큐에서 프로세스 wake up 순서가 정해지지 않은 기법

     

    * Semaphore Implementation

     

    An implementation with no busy waiting requires an integer value ( to hold semaphore value) and a pointer to the next process in the waiting list. The list consists of processes that are put to sleep on the waitfor operation. The kernel uses two additional operations:block and wakeup, to command the process.

     We can think of semaphore implementation as a critical section problem since we don't want more than one process accessing the semaphore variable concurrently.

     

    * Problem that might be caused by the inefficient use of semaphores

    1) Deadlock avoidance

    * Deadlock

    - 시스템 자원에 대한 요구가 뒤엉킨 상태

    - 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황

    A deadlock occurs when a group of processes is blocked in a state waiting for some other member's action.

    If we were to reverse the order of the lines in any of the processes and used a common ordering, 

    we would omit the deadlock in this example

     

    * Avoiding Starvation

    Starvation : indefinite blocking of a process.

    A famous starvavtion example is the Dining Philosophers problem.

    => using process synchronization, we want to make sure that each process will get service sonner or later.

     

    * priority inversion

    실시간 스케쥴링 문제의 하나로, 공유자원 동기화 시 높은 우선순위 프로세스가 낮은 우선순위 프로세스로 인하여 수행이 지연되는 현상

    Real Time OS인 경우 심각성 증가

    [ 우선순위 역전 현상 시나리오 ]

    고순위 프로세스(H), 중순위 프로세스(M), 하순위 프로세스(L), 자원(R : 공유자원을 처리하기 위한 세마포어, 임계구역을 포함한다)

    source : https://www.youtube.com/watch?v=tGm0alD--iM

    고,중,하순위 프로세스 순으로 나열돼 있음.

    하순위 프로세스가 먼저 공유자원을 할당받아서 임계구역에서 처리하고 있다.

    고순위 프로세스가 공유자원을 필요로해서 공유자원 요청, 사용되고 있으므로 standby 상태

    그 후 중순위 프로세스가 들어옴, 공유자원을 필요로 하지 않는 프로세스이며 하순위보다 순위가 높아 cpu를 선점, 실행, 완료한다.

    고순위 프로세스는 공유자원을 기다리느라 중순위 프로세스보다 늦게 처리된다.

    중순위 프로세스가 지속적으로 유입된다면 고순위 프로세스는 기아상태에 돌입한다.

     

    * 우선순위 역전현상 해결방안

    1) 우선순위 상속 (PIP, Priority Inheritance Protocol) - 많이 쓰인다

    하순위 프로세스가 자원 R을 선점할 경우, 고순위 프로세스의 우선순위를 상속받아 중순위 프로세스 인터럽트를 차단

    자원 R 사용이 끝나면 하순위 프로세스는 원래 순위로 돌아간다.

     

    2) 우선순위 상한 (PCP, Priority Ceiling Protocol )

    동시에 존재하는 프로세스 중에서 고순위 프로세스의 우선순위와 같거나 작은 순위를 하순위 프로세스가 가짐.

    최고순위 프로세스가 종료되면 하순위 프로세스는 그 다음 고순위 프로세스 우선순위를 가진다.

     

    * Semaphores in Action : [todo : www.baeldung.com/cs/semaphore 뒷 부분 읽고 정리 더 해야함 ]

    1) Critical Section Problem

    The critical section is a part of the program code, where we want to avoid concurrent access.

    use binary semaphore to solve the critical section problem.

    - Instead of busy waiting, the waiting process is sleeping as it's waiting for its turn on the critical section.

    Then the signal operation is performed, kernel adds a sleeping process to the ready queue. If the kernel decides to run the process, it will continue into the critical section.

     

    * 계수형 세마포어 알고리즘

    - 빵집주인은 S=10일 때 잠을 자고, 아니면 빵을 만들어 판매대에 갖다 놓는다

    - 손님은 빵집주인이 S=10이므로 자고 있을거라 생각하고, 빵집주인을 깨우고 빵을 사간다(S=S-1)

    - 손님은 S=0일 때 잠을 자고, 아니면 빵이 있으므로 빵을 사간다(S=S-1)

    - 빵집주인은 손님이 S=0이므로 자고 있을거라 생각하고, 손님을 깨우고 빵을 만들어 판매대에 갖다 놓는다(S=S+1)

     

     

    source : www.baeldung.com/cs/semaphore

    www.youtube.com/watch?v=tGm0alD--iM

    www.youtube.com/watch?v=481K0TaM-6U

    '컴퓨터 > 운영체제' 카테고리의 다른 글

    프로세스와 스레드의 차이  (0) 2021.03.24

    댓글

Designed by Tistory.