Semaphore

Semaphore

 

 

int형 변수로 사용자마음대로 수정할 수 없고 wait,signal을 이용해서만 수정이 가능하다.

공유데이터 문제(Critical Section)을 해결하기 위한 문제중 하나로써, Critical Section 코드 위에 세마포어로 락을 걸어주어 프로세스가 크리티컬 섹션을 진행하다가 Context-Swich가 일어나도 다른 프로세스의 접근을 막아주어 하나의 프로세스만 들어가게 끔 만들어 준다.

 

 

Wait(S){                 // S는 세마포어를 지칭함.

while(S<=0);    // 세마포어 변수가 0이하 일때에는 루프를 돌게해서 락을 건다.

s--;                // 세마포어 변수가 1이라서 락인부분을 통과하면 Critical Section을 사용하고 다른 프로세스의 접근을 막기위해서 세마포어를 -1 시켜준다.

}

 

Signal(S){

S++;                //Critical Section을 거치고 난 프로세스가 실행하는 함수로 다른 프로세스의 접근을 허용함.

}

 

또한, 하나의 프로세스가 wait,singal을 사용하여 세마포어 값을 변경하고 있을 때에는 다른 프로세스가 값을 변경할 수 없다. Wait , Signal을 실행시에는 Atomic 해야 한다.

Atomic => 실행중에 interrupt가 발생하지 않도록 해주는 것.

 

운영체제는 세마포어를 Binary semaphore와 Counting semaphore로 나누기도 한다.

바이너리 세마포어는 0 or 1만을 값으로 가지지만 카운팅 세마포어의 값은 제한이 없다. 바이너리 세마포어(이진 세마포어)는 위에서 설명한 방식대로 공유리소스에 하나의 프로세스만 넣는 기법이고, 카운팅 세마포어는 공유리소스의 접근할 수 있는 최대 허용치만큼을 초기값으로 가지고 나서 공유 자원에 프로세스가 들어갈때 마다 값을 -1 해주고 세마포어 변수가 0이 되면 다른 프로세스의 접근을 막는 방식이다.

 

세마포어의 방법에는 2가지가 있는데...

Busy waiting

Critical Section을 사용중인 프로세스가 signal에 들어가기 전까지 다른 프로세스들은 while루프를 돌고 있으므로 오버헤드가 단점이다.

 

Blocking & Wake-up

waiting Queue를 만들어 waiting process를 저장하고 뮤텍스를 두어서 Critical Section을 사용한 프로세스가 waiting queue에 있는 process중 하나에게 뮤텍스를 전달하면 전달받은 프로세스가 Critical Section에 들어가는 방식. 하지만 크리티컬섹션 실행시간이 아주 짧을때는 큐에 집어넣고 뮤텍스를 전달하고 다시 큐를 빠져 나오게 해야 하므로 오버헤드가 busy waiting보다 더 클 수가 있다.

 

Semaphore problem

 

Deadlock 현상

프로세스들이 Critical Section에 들어가지 못하고 계속 while루프만 도는 것을 의미함. 예를 들어

 

P1                             P2

wait(S);                   wait(Q);

wait(Q);                   wait(S);

 

     C r i t i c a l   S e c t i o n

 

Signal(S);                Signal(Q);

Signal(Q);                Signal(S);

 

와 같은 코드가 있다면, 맨처음 p1의 wait(S);가 일어나고 Context-Switch가 일어 난 후에 P2의 wait(Q);가 실행되고 다시 P1이 실행된다면 P2의 wait(Q);에 의해서 P1 프로세스는 wait(Q);에서 signal(Q);가 있을때까지 루프를 돌게 된다. 루프를 돌던 중 P2가 실행되고 P2도 wait(S);에서 계속 루프를 돌게 된다. P1,P2둘다 아무런 진척이 없이 무한루프에 빠지는 현상을 Deadlock현상이라고 한다.

 

Starvation 현상

앞의 스케쥴링 기법에서도 있었던 문제점인데, 세마포어를 사용할때 Block & wake-up 방식을 이용한다고 가정하자. 이때 Queue는 LIFO방식으로 작동한다면, 처음에 들어온 프로세스는 Starvation현상이 발생할 것이다.

 

Priority Inversion(우선순위 역전현상)

우선순위가 낮은 프로세스가 Critical Section을 실행하던 중 우선순위가 높은 프로세스가 들어오면 CPU는 우선순위가 높은 프로세스를 실행한다. 그러다가 실행중 프로세스보다 더 높은 우선순위의 프로세스가 들어왔는데 Critical Section에 진입해야 하는 경우에 wait를 이미 한번 호출했기 때문에 진입을 할 수가 없다. 이처럼 우선순위가 낮은 프로세스가 문제가 되어 우선순위가 높은 프로세스가 진행할 수 없는 경우를 뜻한다.

 

이럴경우 우선순위 계승방법으로 해결이 가능한데, 우선순위가 낮은 T3가 signal을 호출하기 전까지만 T1의 우선순위를 계승하는 방법이다. signal을 호출하고 나면 우선순위가 원래대로 돌아오게 됨.