[운영체제] Process Synchronization (3)

Semaphores S

 

일종의 추상 자료형. 정수 값을 가질 수 있음. 변수에 대해 정의되는 operation 필요.

S는 자원의 갯수.

 

lock을 걸고 푸는 과정을 간단하게 semaphore로 구성할 수 있음.

공유 자원을 획득하고 반납하는 것을 semaphore가 처리해 줌.

 

아래 두 가지 atomic  연산에 의해서만 접근 가능.

 

- P 연산 

P(S) {
    while(S<=0)
    do no-op;
    S--;
}

 설명 : semaphore 변수 획득 과정.

 

- V 연산

V(S){
	S++;
}

설명 : 다 사용한 후 반납하는 과정.

 

앞서 본 lock은 S가 1인 경우로 생각하면 됨.

semaphore mutex;
// initally 1 : 1개에 cs가 들어갈 수 있음.
Process Pi;

do {
   P(mutex);
   // critical section
   V(mutex);
   //remainder section
} while(1);

프로그래머가 코딩하는 것이 아니라 추상 자료 형태로 제공을 해주고 semaphore를 통해 더 간단한 프로그램을 작성할 수 있음. 만약 다른 process가 critical section에 들어가 있다면 Busy waiting(=spin lock) : critical section을 얻을 때 까지 계속 기다림.을 통해 하는데 이는 효율적이지 못함.

 

Block & WakeUp(=sleep lock) 의 방식으로 얻지 못한다면 잠들게 됨.

 

---

Classical Problems of Synchronization

 

- Bounded-Buffer Problem (Producer-Consumer Problem)

: 유한한 Buffer 크기.

 

Producer : 데이터를 생성하여 버퍼에 넣는 역할. (비어있는 버퍼 = 자원의 갯수) 

비어있는 버퍼를 확인하고 데이터를 집어넣는 작업. -> 공유 버퍼에 lock을 걸어 다른 프로세스 막은 후에 비어있는 버퍼에 데이터를 집어 넣음.-> lock을 풀어 다른 생산자 혹은 소비자가 접근하게 함.

Consumer : 데이터를 가져올 때 -> 버퍼에 lock을 걸어 데이터를 꺼냄 -> lock을 푼다. (데이터 있는 버퍼 = 자원의 갯수)

 

만약 생산자가 버퍼를 다 채운 상태 -> 생산자가 데이터를 만들어 넣으려고 하는 상태

-> 생산자 프로세스는 자원이 생길 때 까지(비어있는 버퍼가 생길 때 까지) 기다림.

  

소비자 버퍼에 있는 데이터를 다 꺼내고 비어있는 상태 -> 소비자 프로세스 때 자원을 가져갈 것이 없음. -> 생산자 프로세스가 내용을 만들 때 까지 기다림. 

 

Pseudo 코드 구현

semaphore full = 0;
empty = n;
mutex = 1;

 

Producer

do {
    P(empty); // 빈 버퍼가 있는지 확인 -> 0이라면 기다림.
    P(mutex); // 있으면 획득. 
    
    // 락
    
    // add x to buffer
    
    V(mutex); // 버퍼의 lock을 풀음.
    V(full); // 버퍼 갯수 1을 증가.

} while(1);

Consumer 

do {
    P(full); // 내용이 들어있다면 획득. 0이라면 생산자가 데이터 만들 때 까지 기다림.
    P(mutex); // 버퍼 전체에 lock을 검.
    
    // remove an item from buffer to y
    
    V(mutex); // 버퍼가 끝나면 공유 버퍼 락을 푼다.
    V(empty); // 비어있는 버퍼의 갯수 1 증가.
	
    // consume the item in y
    
} while(1);

 

- Reader-Writers Problem

 

읽는 프로세스 / 쓰는 프로세스 있음, 주로 DB에서 발생함.

write는 문제가 있지만 read는 동시에 하더라도 synchronization에 문제가 되지 않음.

(write는 동시에 읽을 수 없으므로 기다려야 함.)

 

Pseudo 코드

 

공유 데이터  

- 공유 코드 : DB 자체

- readcount : 현재 db에 접근 중인 reader의 수

 

- mutex : 공유 변수 readcount 접근 코드(공유 코드) 의 상호 배제를 위해 사용.

- db: 세마포

int readcount = 0;
db;
semaphore mutex = 1;
db = 1;

 

Writer

P(db);

// lock을 걸고 쓰기

V(db);

// starvation 발생 가능. 
// 정도에 따라 reader를 막고 writer를 주는 식으로 작동.

Reader 

P(mutex);
readcount ++;
if(readcount == 1) P(db); // 락을 걸어서 write하지 못하게 함.
V(mutex);

P(mutex);
readcount--;
if(readcount == 0) V(db);
// 마지막으로 읽는 프로세스라고 하면, db에 건 lock을 풀어줌. 
V(mutex);

//락을 걸었지만 다른 프로세스가 읽으려고 할 때 같이 읽어야 함.

 

- Dining-Philosophers Problem

 

철학가 i명 : 생각을 하거나 배가 고프면 젓가락을 잡아 옆에 있는 밥을 먹음.

semaphore chopstick[5];

Philosopher i

do {

    P(chopstick[i]);
    P(chopstick[(i+1)%5]);
    
    eat();
    
    V(chopstick[i]);
    V(chopstick[(i+1)%5]);
   
    think();

} while(1);

위 코드는 Deadlock의 가능성이 있음.

: 만약 철학자 모두가 왼쪽 젓가락을 잡았으면 오른쪽 젓가락은 영영 잡을 수 없음.

 

- 해결 방안

: 4명의 철학자만 테이블에 동시에 앉을 수 있게 함. 

: 젓가락을 두개 잡을 수 있을 때만 젓가락을 잡을 수 있게 함.

: 비대칭 : 짝수(홀수) 철학자 왼쪽(오른쪽) 젓가락 부터 잡도록 함.

 

 

이를 해결한 코드 

: 세마포와는 약간 다른 개념.

enum(thinking, hungry, eating) states[5];
semaphore self[5] = 0;
semaphore mutex = 1;

Philosopher i
do {
   pickup(i); // 젓가락 두개 잡음.
   eat();
   putdown(i);
   think();
} while(1);


void putdown(int i) {
   P(mutex);
   state[i] = thinking;
   // 왼쪽, 오른쪽 철학자에 대한 테스트 
   test((i+4)%5);
   test((i+1)%5);
   V(mutex);
}

void pickup(int i) {
   P(mutex);
   state[i] = hungry;
   test(i);
   V(mutex);
   P(self[i]);
}

void test(int i) {
   if(state[(i+4)%5] != eating && state[i] == hungry && state[(i+4)%5] != eating) {
      state[i] = eating;
      V(self[i]);
   }
}

---

Monitor

 

- Semaphore의 문제점 해결

 : 코딩하기 힘듬.

 : 정확성 입증 어려움.

 : 한번의 실수가 모든 시스템에 치명적 영향. 

 

- 프로그래밍 언어 차원에서 synchronization 문제 해결. high-level synchronization construct.

- 공유 데이터 접근 위해 모니터라고 정의된 내부 procedure를 통해 데이터 접근할 수 있게 함.

- 명시적으로 코딩할 필요 없음.

- 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용

 : x라는 자원이 여분 있으면 접근, 없으면 -> 기다려야 하면 x.wait() : 줄에 서서 기다림.

   접근 후 빠져나갈 때 x.signal()을 통해 빠져나갈 수 있게 함.

 

 

Monitor를 활용한 생산자-소비자 문제 

monitor bounded_buffer
{
   int buffer[N];
   condition full, empty;
   
   void produce(int x)
   {
      // 비어있는 버퍼 없다면
      empty.wait();
      
      // 있다면
      full.signal();
   }
   
   void cousume(int *x) {
      // 데이터 있는 버퍼가 없다면
      full.wait();
      
      // 있다면
      empty.wait();
    }
}

 

하나의 프로세스만 활성화되기에 락을 걸거나 풀 필요 없음.

또 다른 생산자, 소비자 접근해서 생기는 문제 없음. (큐는 대기 중)