[OS] 동기화 문제의 예시와 모니터

프로세스 동기화의 대표적인 3가지 문제에 대해 다룸
또 세마포어의 문제점과 모니터에 대해 다룸

Bounded-Buffer Problem(=생성자-소비자 문제)

• Producer(생성자) : 자원을 만드는 역할을 하는 프로세스(빈 버퍼가 자원에 해당됨)
• Consumer(소비자) : 만들어진 자원을 소비하는 역할을 하는 프로세스(꽉 찬 버퍼가 자원에 해당됨)
• Shared date : 여기서의 공유데이터는 버퍼자체 및 버퍼 조작 변수등이 해당됨
• 필요한 세마포어 변수
  - mutual exclusion(상호배제) : 바이너리 세마포어가 필요함(공유 데이터의 mutal exclusion을 위해)
  - resource count : 정수 세마포어가 필요함(남은 full/empty 버퍼의 수를 표시하기 위해)
  

Reader-Writers Problem

• 한 프로세스가 DB에 write 중일때, 다른 프로세스는 그 DB에 접근하면안됨

• read는 동시에 여럿이 해도 상관이 없음

• 해결법

  • writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 reader들을 다 DB에 접근하게 해줌
  • writer는 대기 중인 reader가 하나도 없을 때 DB접근이 허용됨
  • 일단 writer가 DB에 접근 중이면 reader들은 접근이 금지됨
  • writer가 DB에서 빠져나가야지만 reader이 접근할 수 있도록함

• 공유 데이터 : DB 자체 및 readcount(현재 DB에 접근 중임 reader의 수)

• 필요한 세마포어 변수

  • mutex : 공유 변수 readcount를 접근하는 코드(critical section)의 mutual exclusion(상호배제)를 보장하기 위해
  • DB : reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

• reader는 다른 reader의 접근을 허용하기 때문에 지속적으로 reader가 들어오게될 경우 writer는 starvation이 발생 할 수 있음
• writer가 지나치게 오래 기다리지 않도록 일정시간이 지나면 우선순위를 높여 reader가 더 이상 들어오지 못하게 막는 방식으로 해결가능
  (멀티 피드백 큐에서 우선순위 boost와 비슷한 아이디어)

Dining-Philosophers Problem

• 철학자는 생각하는 시간, 밥을 먹는 시간 둘 중하나의 상태로 나누어짐
• 철학자가 밥을 먹기위해서 양쪽 젓가락을 사용해야됨
• 공유 데이터 : 젓가락
• 필요한 세마포어 변수 : chopstick[5](젓가락의 배열) 초기값은 1로 채워져있음(젓가락이 1이면 아무도사용x 0이면 누군가가 사용)

• 문제점

  • Deadlock의 가능성이 있음
  • 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락으 집어서, 사용 못하는 젓가락이 생김

• 해결방법

  1. 의 철학자만 테이블에 동시에 앉을 수 있도록함
  2. 락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게만듦
  3. 철학자는 왼쪽 젓가락부터 집도록, 홀수 철학자는 오른쪽 젓가락부터 집도록 정해둠
     
  • 3의 해당하는 부분의 코드화 한것,
  • 철학자는 생각, 배고픔, 먹는다의 3개의 상태가있고, 젓가락을 집는 픽업, 먹는 eat, 젓가락을 내려놓는 putdown, 생각하는 think행동이 있음
  • 주위 할 점이 self 세마포어는 양쪽 젓가락을 사용할 수 있는지 아닌지에 대한 세마포어로 초기값이 0임 0이면 집을 수 없고, 1이면 집을 수 있음
  • putdown : 다른 프로세스를 접근 못하게 락을 걸고 철학자의 상태를 thinking으로 바꾸고, 왼쪽 오른쪽의 철학자에 대해 test함수를 실행후 락을 품
  • test : 현재 젓가락을 집을 수 있는지를 테스트하는 함수 왼쪽,오른쪽 철학자가 바을 먹고있지않고, 상태가 배고픈상태면 집을 수 있음(=self값을 1로 만들 수 있음)
  • pickup : 락을 걸고 상태를 배고픈 상태로 바꾸고 test를 실행하고 락을 풀고 self의 값을 흭득함(젓가락을 집음)

Monitor

• 세마포어의 문제점

  • 코딩하기 힘듦
  • 정확성의 입증이 어려움
  • 자발적 협력이 필요하게됨
  • 한번의 실수가 모든 시스템에 치명적인 영향을 끼침
  • 예시, 락을 풀고 락을 걸려고 상호배제가 깨짐, 또 락을 걸고 또 락을 걸려고하니깐 데드락이 걸려서 두번쨰 P에서 빠져나가질못함

  

• 모니터 : 동시에 수행주인 프로세스 사이에서 추상 데이터 타입의 안전한 공유를 보장하기 위한 high level synchronization construct

  • 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
  • 프로그래머가 동기화 제약 조건을 명시적을 코딩할 필요가 없음(락이 필요하지않음)
  • 프로세스가 모니터 안에서 기다릴 수 있도록 하기위해 condition variable를 사용

  condition x,y;

  • condition variable은 wait와 signal 연산에 의해서만 접근 가능.

  x.wait(); 
  // X.wait를 invoke한 프로세스는 다른 프로세스가 x.signal을 invoke하기 전까지 suspend 됨
  x.signal();
  //x.signal은 정확하게 하나의 suspend된 프로세스를 resume함, suspend된 프로세스가 없다면 아무 일도 일어나지않음

  

• entry 큐 : 공유데이터에 접근하려고하는 프로세스가 존재하는 큐

• 생산자 소비자 문제를 모니터로 코딩

여기서 CV에 해당하는건 full큐(자원이 채워져있는 큐)와 empty큐(자원이 비어져있는큐)로 나타남
생산자는 empty큐에 자원을 넣고 소비자는 full큐에있는 자원을 흭득 그리고 각 프로세스는 entry큐에서 공유 데이터 접근 순서를 정함

• 철학자 문제 모니터 코드

Reference
주니온 교수님 유튜브 채널
반효경 교수님 KOCW 운영체제
운영체제 아주 쉬운 세 가지 이야기(OSTEP 번역서)