[OS] 동기화(세마포어)

세마포어(Semaphores)

1) 세마포어 개요

         1. 세마포어 : 동기화를 위한 도구

             - 음이 아닌 정수 값을 갖는 플래그 변수(S) 사용

             - 다익스트라(Dijkstra)가 상호 배제를 극복하기 위해 제안

             - 세마포어의 예 : 열차 진행을 알리는 차단기

---

         2.  세마포어 연산

           ㄱ: 세마포어 변수(S)

                a) 카운팅 세마포어(Counting Semaphore)

                    - S의 크기 : 총 사용 가능한 자원의 개수

                    - S는 자원의 개수로 초기화됨

                    - S의 범위는 한정되어 있지 않음

                b) 이진 세마포어(Binary Semaphore, mutex)

                    - S는 0 또는 1 만 가질 수 있음. (초기값은 1)

                    - 시스템에서 상호 배제를 제공하기 때문에 mutex라고도 불림

 

             ㄴ: 세마포어(S)는 두 개의 표준 원자적 연산인 P(S) 연산, V(S) 연산으로 접근 가능

세마포어 참고

        => 문제점 : 바쁜대기(Busy Wait) 발생

---

     3.  Busy Waiting(바쁜 대기)

• 프로세스가 공유자원에 접근하고자 할 때, 진입 구역에서 공유자원과 다른 프로세스들의 상태 판단하는 루프를 돌면서 계속 기다리는 것

[바쁜 대기를 해결하기 위한 세마포어 P(S)와 V(S) 연산]

P(S) : begin 
		  S.count := S.count - 1;
          if S.count < 0 then                // S가 음수이면 그 수만큼 대기큐에 프로세스가 있다.
          begin
        	  [호출한 프로세스를 S.queue에 넣는다.]; 
              block;
          end;
       end;

V(S) : begin
		  S.count := S.count + 1;
          if S.count <= 0 then               // S가 양수이면 그 수만큼 임계영역에 진입 가능.
          begin
          		[S.queue에서 프로세스를 꺼낸다.];
                wakeup;
          end;
        end;

• 최초에는 세마포어는 음수를 가질 수 없었으나, 위와 같이 구현하면 음수가 될 수 있다. 
• 세마포어가 음수라는 의미는 대기하고 있는 프로세스의 수를 의미한다.
• 두 프로세스가 동시에 P(S), V(S) 연산을 실행할 수 없도록 반드시 보장해야 한다. 
• 다중처리 환경에서 모든 프로세서에서의 인터럽트를 금지해야 한다. 
• 위와 같은 block-wait 방식을 sleep lock이라고도 한다.

---

    3)  세마포어의 문제점

• 데드락(deadlock) 또는 기아(Starvation) 발생
• 우선순위 역전 현상

---

2) 세마포어를 이용한 동기화 문제

     1. 생산자 - 소비자 문제

program producer_consumer;
var mutex: semaphore;           // 이진 세마포어, 상호배제를 위한 것, 초기값 1
var produced : semaphore;       // 완성품 (카운팅 세마포어)
var consumed : semaphore;       // 원재료 (카운팅 세마포어)

// 완성품 0 , 원재료 : n

procedure producer;
begin
	while true do
    begin
    	[정보 생산];
        p(consumed);            // n - 1
        p(mutex);			
        [생산한 정보를 유한 버퍼에 넣는다.]; // 임계영역
        v(mutex)
        v(produced);			// + 1
    end;
end;

procedure consumer;              // 소비자 프로세스
begin
	while true do
    begin 
    	p(produced);             // 완성품 소비
        p(mutex);
        [유한 버퍼에서 정보 하나를 가져온다];  // 임계영역
        v(mutex);
        v(consumed);
        [정보 소비];
    end;
end;

---

     2. 판독자 - 기록자 문제

program read_writer;
var readers : integer;			// 카운팅 세마포어
var s, writing : semaphore; 	// 2진 세마포어

// 읽는 중에는 쓰기는 대기 해야 함.
procedure reader;
begin 
	P(s);
    readers += 1;
    if readers = 1 then P(writing);
    V(s);
    	[데이터 읽기];	// 임계영역
    P(s);
    readers -= 1;
    if readers = 0 then V(writing);
    V(s);
end;

procedure writer;
begin
	P(writing);					// 리더가 계속 들어오면 기록자는 여기서 대기
    	[데이터 기록];
    V(writing);
end;
begin
	readers = 0;
    s = 1;
    writing = 1;
    [reader와 writer를 병행하여 실행];
end;

 => 문제점 : 기록자 프로세스가 기아상태에 빠질 수 있다.

---

     3. 식사하는 철학자

 

식사하는 철학자

 

Procedure philosopher(i : integer)
begin 
	[생각한다];
    P(forks[i]);
    P(forks[(i+1) mod 5]);
    [먹는다];
    V(forks[i];
    V(forks[(i+1) mod 5];
end;

begin 
	forks[0] = 1; forks[1] = 1; forks[2] = 1;
    forks[3] = 1; forks[4] = 1;
    [philosopher(0), (1), (2), (3), (4)를 병행하여 실행];
end;

 식사하는 철학자 기본 조건

구분	설명	실환경
환경	원탁에 둥글게 앉아서 사이에 포크를 공유한다.	공유자원, 선형조건
행위	철학자는 먹거나 사색한다.	대기와 실행
행위 조건	반드시 2개의 포크로 식사를 한다. 다른 상대의 포크는 뺏을 수 없다. 왼쪽 포크를 항상 먼저 집는다.  하나를 가지면 하나를 기다린다. 아무도 식사에 간섭하지 않는다. 식사를 마치면 포크를 내려놓는다.	취득 후 실행 상호배제 점유와 대기 비선점

식사하는 철학자 문제점

• 한 번에 2명만 식사를 할 수 있다.
• 누가 어떤 포크를 가졌는지 신경 쓰지 않고 자기 생각만 한다.

=> 교착상태가 발생한다. 

 

식사하는 철학자 교착상태 해결책

1. 최대 4명의 철학자만 동시에 앉을 수 있도록 한다. (n-1명만 식사) => 예방
2. 홀수번째 철학자는 왼쪽을 짝수번째 철학자는 오른쪽 포크를 먼저 집는다. => 회피
3. 한 명만 오른쪽에서 왼쪽 순서로 포크를 집는다.