Lecture 11.~12. Semaphor

3 minute read

Semaphor란 ?

세마포는 다익스트라가 1965년에 발명했다고 합니다. 세마포는 두 개의 atomic-operation을 지원합니다. P/wait와 V/signal입니다.

세마포는 그저 하나의 변수일 뿐입니다. 세마포는 처음에 1로 초기화됩니다. Thread는 CS에 들어가기 전에 P-세마포(이하 P)를 Call 하거나 wait-세마포(이하 wait)해야합니다. Thread는 CS를 나올 때 V-세마포(이하 V)를 Call하거나 Signal-세마포(이하 signal)해야합니다.

냉장고 우유의 예시에서 두 쓰레드는 아래의 코드를 똑같이 실행합니다.

//Thread A and execute this code seperatively

milk->P();     //(1)
if(noMilk);    //(2)
    buy milk;  //(3)
milk->V();     //(4)

(2)와 (3)이 CS입니다. CS에 들어가기 전에 P 나오면서 V를 했습니다. 조금 더 자세히 보겠습니다.

Details of Semaphore Operation

P(s) or Wait(s)

CS에 들어가기 전에 P 또는 Wait 를 Call 합니다.

wait(s){
    s = s -1;
    if(s<0){
        뒤늦게 wait(s)를 call한 Thread를 block합니다.
        //설명 1
    }else{
        CS는 비어있습니다. 따라서 해당 Thread가 cS에 들어갑니다.
        //설명 2
    }
}

s는 처음에 1로 초기화 되어있습니다. CS에 들어가기 전에 P를 수행합니다. P는 s 를 -1하는 연산을 포함합니다. 만약에 어떤 Thread가 P를 수행했습니다. 그래서 s를 -1 감소시켰습니다. 원래 S는 1로 초기화가 되었기 때문에 나만 P를 수행했다면 s의 값은 0이어야 합니다. 그런데 내가 -1한 결과가 s<0라면 이미 다른 Thread가 P(s)를 call 한 상태입니다. 이 때는 뒤늦게 wait(s)를 call한 Thread를 block합니다.
-1을 한 s가 s>0라면 다른 Thread에서 P(s)를 한 적이 없는 것이므로 CS는 비어있습니다. 따라서 해당 Thread가 cS에 들어갑니다.

V(s) or signal(s)

signal(s){
    s = s+1;
    if(s<=0){
        기다리고 있는 Thread 중 하나를 깨우면 됩니다. 
        //설명 1
    }
}

s는 1로 초기화를 시켰었다. 그리고 CS에 들어보면서 s를 -1 시켰습니다. 이제 CS에서 나가면서 +1을 시킵니다. 만약에 나 혼자만 -1 시키고 +1 시켰다면 현재 s는 1이어야 합니다. 그런데 CS에 들어오려고하는 다른 Thread가 P(s)를 call해서 s를 -1 시킨 뒤, BLock된 상태라면 CS에 들어있던 Thread가 +1을 해도 S는 s<=0 입니다. 즉, s +=1 한 결과가 s<=0라면 CS에 들어오려는 다른 Thread가 있는 것이므로 기다리고 있는 Thread 중 하나를 깨우면 됩니다.

정리

Positive S : CS에 들어올 수 있는 Thread의 수 (waiting 하고 있는 Thread 중 몇 개가 깨어나서 CS에 들어올 수 있는지)
Negative s: waiting 하고 있는 Thread의 수
Binary semaphor는 1로 초기화 시킨다.
Binary Semaphor가 아닌 Counting semaphor라는 것은 1보다 큰 수로 초기화를 한다.

문제 풀이

semaphor-1

//TODO The Code Machine

Implementing Semaphores

Solution 1. : Basic

#wait(s){
    while(s<=0){
        //do nothing
    }
    s = s -1
}

지금까지는 -1을 먼저한 뒤 그 결과가 s<0이라면 block 되는 것으로 설명했습니다. 여기서는 -1을 한 결과가 s<0이 될 것을 미리 파악하고 s가 1이상인 경우만 s -= 1을 진행하는 모습입니다.

signal(s){
    s = s + 1
    }

signal은 그냥 더해줍니다.

문제점

CS에 들어가기 위해서 blocked 된 Thread의 Queue를 지원하지 않습니다.
Wait(S)를 진행하면서 아무것도 하지 않으면서 시간을 낭비합니다.
wait와 signal 속에 존재할 수 있는 CS를 보호하지 못합니다.

Solution 2. : disable/enable interrupts

#wait(s){
    disable interrupts
    while(s<=0){
        //do nothing
    }
    s = s -1
    enable interrupts
}

signal(s){
    disable interrupts
    s = s + 1
    enable interrupts
    }

solution 1.에 disable/enable interrupts를 추가한 것입니다. 이는 위의 3번 문제를 해결하기 위한 방법으로 생각해본 것입니다.

문제점

CS에 들어가기 위해서 blocked 된 Thread의 Queue를 지원하지 않습니다.
Wait(S)를 진행하면서 아무것도 하지 않으면서 시간을 낭비합니다.
Multi-processor에서는 작동하지 않습니다. disable하는 processor만 disable되기 때문입니다. 모든 Processor가 공동으로 접근할 수 있는 변수를 사용한 방법이 아니라, 그때 그때 Processor A를 접근 못하게 막고, B를 못하게 막고 이런식으로 진행된다고 볼 수 있기 때문입니다.
Timer와 연동될 수 없습니다. interrupt diable을 사용해서 timer가 소용이 없어집니다.
oS가 interrupt disable을 하도록 하는 것은 문제가 없지만, 사용자가 interrupt disable을 할 수 있도록 허용하는 것은 문제점을 낳을 수 있습니다.

Solution 3. : test&set

#wait(s){
    whlie(test&set(lk)!=0){
        do nothing
    }
    while(s<=0){
        //do nothing
    }
    s = s -1
    enable interrupts
    lk=0
}

signal(s){
    whlie(test&set(lk)!=0){
        do nothing
    }
    s = s + 1
    lk = 0

test&set은 LOCK이 걸려있는지 아닌지 test하고, LOCK이 안걸려 있다면 LOCK을 거는 것을 말합니다. LOCK은 특정 구역에 들어갈 수 있는지 아닌지를 나타내는 변수라고 생각하면 됩니다. 마지막에 lk=0 부분은 LOCK을 해제하는 Unlock을 이해할 수 있습니다.

Lock lk는 0으로 초기화됩니다.
LOCk이 안걸려있는 경우 ( lk == 0) : Atomic하게 lk의 값을 읽고(0), 쓰고(1), return(0)합니다.
Lock이 걸려있는 경우(lk == 1): Atomic 하게, lk의 값을 읽고(1), 쓰고(1), return(1)합니다.

위 코드의 test&set()은 test&set()이 시작될 때의 lk값을 return합니다. 0이었으면 0을 1로 바꿨더라도 0을 return하고, 1이었으면 그대로 1로 두고 1을 return 합니다. 따라서 test&set()의 결과가 1이라면 lock이 걸려있는 상태, 0이라면 unlock 상태입니다.

test&set()은 Read-Modify-Write(이하 RMW)패턴의 한 예시입니다. RMW 명령어는 Atomic하게 memory의 값을 읽고, 수정하고, 씁니다.

장점

Multiprocessor에서도 동작하게 만들 수 있습니다.

문제점

CS에 들어가기 위해서 blocked 된 Thread의 Queue를 지원하지 않습니다.
Wait(S)를 진행하면서 아무것도 하지 않으면서 시간을 낭비합니다.

다음 포스팅에서 LOCK에 대해서 제대로 알아보겠습니다.

Twitter Facebook LinkedIn

Niklas Jang