[운영체제] Chapter 6. Process Synchronization (3)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

 

Semaphores, Implementation, Classical Problems of Synchronization, Bounded-Buffer Problem, Readers-Writers Problem, Dining-Philosophers Problem

 

1. 고질적인 프로세스 동기화 문제

1-1. Bounded-Buffer Problem (Producer-Consumer Problem), 유한 버퍼 문제 (생산자 소비자 문제)

• Producer: 생산자 프로세스: 공유 버퍼에 데이터를 하나 만들어 집어넣는 역할
• Consumer: 소비자: 공유 버퍼에 있는 데이터를 꺼내는 역할
• shared data: buffer 자체 및 buffer 조작 변수(empty/full buffer의 시작 위치)
• 문제
  • n개의 생산자가 동시에 1개의 버퍼에 데이터를 만들어 집어넣는다면?
  • 어떤 소비자 프로세스가 공유 버퍼에서 데이터를 꺼내가려고 하다가 CPU를 빼앗기고, 다른 소비자 프로세스가 같은 버퍼에서 데이터를 꺼내가려고 한다면? 실제 데이터는 1개인데 둘이 동시에 꺼내가려는 문제가 발생할 수 있다.
    
    • → Mutual exclusion: Binary semaphore
    • 공유 버퍼에 lock을 걸어 다른 프로세스의 접근을 막고, 조작 후에 lock을 풀어서 다른 생산자와 소비자의 접근을 허용한다.
  •  유한한 버퍼에 데이터가 가득 차 빈 공유 버퍼가 없으면 생산자의 입장에서는 자원이 없다. 그렇다면 언제 빈 버퍼를 생산자가 조작할 수 있는가?
    • → Resource count: Counting semaphore
    • 생산자의 입장에서 빈 버퍼는 자원 / 소비자의 입장에서는 데이터가 있는 버퍼가 자원
    • 소비자가 버퍼의 데이터를 꺼내가서 빈 버퍼가 생기면 생산자는 해당 버퍼를 조작할 수 있다.
    • 생산자가 버퍼에 데이터를 채워서 데이터가 있는 버퍼가 생기면 소비자는 해당 버퍼를 조작할 수 있다.
    • ⇒ 그리고 가용 자원의 개수를 새는 counting semaphore를 이용해 남은 full/empty 버퍼의 수를 표시하고,
      ⇒ 공유 버퍼에 동시 접근을 막는 lock을 걸고 푸는 것을 binary semaphore를 이용할 수 있다.
      
• 동작 원리 - Producer

//Synchronization variables
semaphore full = 0;    //데이터가 있는 버퍼 개수
semaphore empty = n;   //데이터가 비어 있는 버퍼 개수: 처음에는 다 비어있음
semaphore mutex = 1;   //공유 버퍼에 하나의 프로세스만 접근할 수 있게 하는 용도

//Producer
do{ 
	...
	produce an item in x    //item x를 만들고 공유 버퍼에 집어 넣고자 함
	...
	P(emtpy);    //1. Empty buffer(빈 버퍼)가 있다면 -> 획득, 없다면 -> 기다림
	P(mutex);    //2. 공유 데이터에 lock을 건다.
  ...
	add x to buffer         //3. 빈 버퍼에 데이터 입력 및 버퍼 조작
	...
	V(mutex);    //4. Lock을 푼다.
	V(full);    //5. Full buffer(내용이 든 버퍼) 하나 증가

}while(1);

• 동작 원리 - Consumer

//Synchronization variables
semaphore full = 0;    //데이터가 있는 버퍼 개수
semaphore empty = n;   //데이터가 비어 있는 버퍼 개수: 처음에는 다 비어있음
semaphore mutex = 1;   //공유 버퍼에 하나의 프로세스만 접근할 수 있게 하는 용도

//Producer
do{ 
	P(full);     //1. Full buffer가 있다면 -> 획득, 없다면 -> 기다림
	P(mutex);    //2. 공유 데이터에 lock을 건다.
  ...
	remove an item from buffer to y //3. Full buffer에 데이터 꺼내고 버퍼 조작
	...
	V(mutex);    //4. Lock을 푼다.
	V(empty);    //5. empty buffer(내용이 든 버퍼) 하나 증가
  ...
	consume the item in y
	...

}while(1);

1-2. Readers-Writers Problem

• 한 프로세스(데이터를 쓰거나/읽는)가 DB(공유 데이터)에 write 중일 때 다른 프로세스가 접근하면 안 되지만 / read는 동시에 여럿이 접근해도 됨
  • read를 동시에 여럿이 해도 → synchronization 문제 발생하지 않음
  • write할 때에는 배타적으로 접근해야 하기 때문에 lock을 걸지만 read에도 lock을 걸면 비효율적이다.
• 공유 변수: readcount(reader의 수), DB자체
• 동기화 변수: mutex(readcount 접근), db(DB접근)
• Writer

//공유 변수 Shared data - 접근하기 위해 lock을 걸어 다른 프로세스의 접근을 막아야 함
int readcount = 0;    //현재 DB에 접근 중인 reader의 수
DB 자체

//Synchronization variables
semaphore mutex = 1;  //공유 변수 readcount를 접근하는 코드의 mutual exclusion 보장을 위해 사용
semaphore db = 1;   //Reader와 writer가 공유 DB 자체에 올바르게 접근하게 하는 역할

//Wrtier

P(db);    //공유 DB에 lock걸기
...
writing DB is performed    //공유 데이터에 접근
...
V(db);    //공유 DB unlock

• Reader

//Synchronization variables
semaphore mutex = 1;  //readcount lock, critical section의 mutual exclusion 보장
semaphore db = 1;   //db lock, reader와 writer가 공유 DB 자체에 올바르게 접근하게 

//Reader

P(mutex);         //1. readCount의 변경을 위해 lock을 걸어둠
readcount++;      //2. 여러 reader가 같이 읽을 수 있게
if(readcount==1)  //3. reader가 처음 읽으러온 상황 ~ db를 lock: writer의 접근을 막기 위해서
	P(db);		  //   처음이 아니라면 lock을 걸 필요가 없다: 이미 걸어져있을 것이기 때문
V(mutex);         //4. 공유 변수 readcount에 대한 작업이 끝나면 unlock, 

...
reading DB is performed
...

P(mutex);         //1-1. readcount의 접근을 원자적으로 수행하기 위해 ㅣock
readcount--;      //5. DB를 읽고 빠져나감
if(readcount==0)  //6. reader가 마지막으로 읽고 나가는 프로세스라면 ~ db unlock
	V(db);        
V(mutex);		  //4-1. readcount에 대한 접근이 끝나면 unlock

1. writer가 lock을 걸고 사용하는 것을 막기 위해 lock을 걸어 둠
   • Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 Reader들을 다 DB에 접근하게 해 준다.
   • 일단 writer가 DB에 접근 중이면 reader들은 접근이 금지되고 writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.
2. 현재 DB에 접근 주인 reader의 수 증가
   • 여러 reader가 동시에 readcount를 증가시키다 보면 2를 증가시켰는데 1만 증가되는 문제가 발생할 수도 있다.
     → mutual exclusion 한 readcount 변경을 위해 mutex를 이용해 readcount를 위한 lock을 건다.
3. readercount == 1인 상황은 reader가 db를 처음 읽으러 온 상황 → DB의 올바른 접근을 위해 P(db)로 db에 lock을 건다.
   • writer의 접근을 막기 위해서
   • 만약 최초의 reader가 아니라면(readercount != 1) == 누군가가 읽고 있는 상황에 도착한 reader라면 → lock을 걸지 않고 그냥 DB를 읽는다.
4. 공유 변수 readcount에 대한 작업이 끝나면 readcount에 대한 lock 해제
5. reader 프로세스가 db를 마지막으로 읽고 나가면(readercount==0) db의 lock을 해제해서 writer의 접근이 가능하게 한다.
   • writer는 reader들이 모두 다 빠져나가고 마지막으로 나가는 reader가 lock을 풀어줄 때까지 기다린다.
     → 그래서 starvation이 발생할 수 있다.
6. 해결방법) 일정 시간까지 도착한 reader까지만 DB를 읽을 수 있게 하자

1-3. Dining-Philosophers Problem, 식사하는 철학자 문제

• 원탁에 5명의 철학자가 앉아 있고, 철학자는 생각하고 밥만 먹을 수 있다. 철학자의 왼쪽과 오른쪽에는 공유하는 젓가락이 있다. 철학자는 왼쪽과 오른쪽의 젓가락 두 개를 동시에 모두 들어야 밥을 먹을 수 있다. 젓가락은 두 명이상의 철학자가 동시에 들 수 없다.
• 교착 상태와 기아를 발생시키지 않고 여러 스레드에게 여러 자원을 할당해야 할 필요를 단순하게 표현한 것

• 식사하는 철학자 기본 코드

//Synchronization variables
semaphore chopstick[5] = 1;

//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명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
  • 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
  • 비대칭: 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 잡도록 해서, 젓가락을 집은 철학자만 다른 젓가락을 집을 수 있게 한다.
    자원을 잡는 순서를 지정해두는 것

1-3-1. 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.

• shared data와 synchronization variable

enum{thinking, hungry, eating} state[5]; 
//다섯명의 철학자의 상태를 나타내는 공유 변수
semaphore self[5] = 0;   
//두개의 젓가락을 모두 집을 수 있는 철학자에게 젓가락을 잡는 권한을 줄 것인지 말것인지를 나타내는 변수
//self[1]=0: 1번 철학자는 젓가락 두개를 다 잡을 수 있는 권한이 없다.
semaphore mutex = 1;    
//state는 각각의 철학자에 대한 상태를 나타내지만 옆의 철학자의 상태도 바꿀 수 있는 공유 변수이다.
//그래서 공유 변수에 대한 동시 접근을 막기 위해 lock을 나타내는 세마포어 변수

• philosopher i

//다섯명의 철학자가 하는 일은 밥을 먹고 생각하기의 무한 반복
do{
	pickup(i);  //먹기 전 젓가락 집기
	eat();      //먹기
	putdown(i); //먹은 후 젓가락 놓기
	think();
} while(1) //무한 반복

• void pickup(int i) - 젓가락을 잡는 함수

void pickup(int i){
	P(mutex);   //state를 수정하기 때문에 lock
	state[i] = hungry;
	test(i);    //철학자 i가 젓가락 2개를 잡을 수 있는 상태인지를 test
	V(mutex);   //작업이 끝나면 unlock
	P(self[i]); //젓가락을 잡을 권한을 1 -> 0 : 젓가락을 잡을 수 없는 상태로 변경
}

• void test(int i)

void test(int i){
	//왼쪽, 오른쪽 철학자도 모두 밥을 먹고 있지 않고 && 내가 배가 고플 때
    //철학자 i의 상태를 밥먹는 상태로 변경하고 밥먹을 수 있는 권한을 준다.
	if(state[(i+4)%5]!=eating && state[i]==hungry && state[(i+1)%5]!=eating){
		state[i] = eating;
		V(self[i]);    //젓가락을 잡을 권한을 0->1: 젓가락을 잡을 수 있다.
  }
	//else : 권한을 얻지 못하고 함수가 끝남
}

• void putdown(int i)

void putdown(int i){
	P(mutex);
	state[i] = thinking;  //생각하는 상태
	test((i+4)%5);      //왼쪽에 있는 철학자를 test해서 젓가락을 못잡고 있던 상황이면 잡게 해줌
	test((i+1)%5);      //오른쪽
	V(mutex);
}

• semaphore self[5]=0;
  • 원래 세마포어는 자원의 개수를 세고, 초기 값이 얼마인지를 두고 일을 하는데
  • 식사하는 철학자 문제에서는 젓가락 2개를 얻을 수 있는 권한이 처음에는 0으로 주어지지 않고
  • 이후에는 체크를 해서 만족할 때 1로 두고 젓가락 2개를 잡을 수 있는 권한을 준다.
  • 세마포어의 철학과는 조금 맞지 않음

 

[복습]

1.  Bounded-Buffer Problem (Producer-Consumer Problem), 유한 버퍼 문제 (생산자 소비자 문제)
   
   • 생산자: P(empty) → P(mutex) → V(mutex) → V(full)
   • 소비자: P(full) → P(mutex) → V(mutex) → V(empty)
2. Readers-Writers Problem: 한 프로세스가 DB에 write 중일 때는 다른 프로세스가 접근할 수 없지만 read는 동시에 여럿이 접근할 수 있다.
   
   • writer: P(db) → writing → V(db)
   • reader: P(mutex) → readcount++ → if(readcount==1) P(db) → V(mutex) → P(mutex) → readcount-- → if(readcount==0) V(db) → V(mutex)
   • writer가 DB에서 빠져나가야만 Reader의 접근이 허용되기 때문에 starvation 문제가 발생할 수 있다.
3. Dining-Philosophers Problem, 식사하는 철학자 문제: deadlock 발생할 수 있다
   
   • 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
   • pickup: P(mutex) → state[i] = hungry → test(i) → V(mutex) -> P(self[i])
   • test(i): 왼쪽 오른쪽 state != eating && hungry일 때만 → eating → V(self[i])
   • putdown: P(mutex) → state[i] = hungry → test(왼, 오) → V(mutex)

 

 

 

 

---

이화여자대학교 반효경 교수님의 [2014년 1학기 운영체제], [2017년 1학기 운영체제] 강의 정리입니다.

 [Operating System Concepts] 교재를 참고하였습니다. 감사합니다.

https://core.ewha.ac.kr/publicview/C0101020140408134626290222?vmode=f 

반효경 [운영체제] 14. Process Synchronization 3