[OS] 6. 프로세스 동기화 - Process Synchronization and Mutual Exclusion (Monitor)

어떻게 하면 상호배제가 잘 작동하는 알고리즘을 만들 수 있을까? 

Mutual Exclusion Solutions

• SW solutions
  
  • Dekker’s algorithm (Peterson’s algorithm)
  • Dijkstra’s algorithm , Knuth’s algorithm, Eisenberg and McGuire’s algorithm, Lamport’s algorithm
• HW solution
  
  • TestAndSet (TAS) instruction
• OS supported SW solution
  
  • Spinlock
  • Semaphore
  • Eventcount /sequencer
• Language Level solution
  
  • Monitor

 

다양하게 적용가능하다 그러나 복잡하다.

복잡하기도 하고 에러의 발생확률이 높아서 쓰기가 힘들다 

 

language-level에서 해결하는 방법이 있음. (앞서 설명한 솔루션들은 low-level Mechanism)

High level Mechanism

• Monitor
• Path expressions
• Serializers
• Critical region, conditional critical region

특징

• Language level constructs
• Object Oriented concept 과 유사
• 사용이 쉬움

 

Monitor

monitor는 critical data, critical sections를 하나로 모아놓은 방 이라고 생각하자.(한번에 한명만 들어올 수 있음)

• 공유 데이터와 Critical section 의 집합
• Conditional variable
  • wait(), signal() operations

 

Monitor의 구조

• Entry queue (진입 큐)
  
  • 모니터 내의 procedure 수만큼 존재
• Mutual exclusion
  
  • 모니터 내에는 항상 하나의 프로세스만 진입 가능 (Lang 가 보장함)
• Information hiding (정보 은폐)
  
  • 공유 데이터는 모니터 내의 프로세스만 접근 가능
• Condition queue (조건 큐)
  
  • 모니터 내의 특정 이벤트를 기다리는 프로세스가 대기
• Signaler queue (신호제공자 큐) (전화부스?)
  
  • 시그널을 보내기 위해 잠깐 들어가는 공간
  • 모니터에 항상 하나의 신호제공자 큐가 존재
  • signal() 명령을 실행한 프로세스가 임시 대기

 

Monitor in Languages

Monitor를 Language가 지원해 주는 것을 알 수 있음.

 

자원 할당 문제

각 function별로 entry queue가 한개씩 있음

entry queues for releaseR() : 자원을 반납하는 function

entry queues for requestR() : 자원을 요청하는 function

condition queue R_free(): 자원을 빌리기 위해 대기하는 공간.

signaler queue(): condition queue R_Free에 대기하는 프로세스를 깨우는 공간.

 

Monitor라는 것을 language가 보장해 줌으로써

간단하게 코드로 옮겨짐..

이를 세마포어 or 이벤트 카운터/시퀀셔로 짜라고 하면 복잡하다..

1. procedure requestR()을 통해서 자원을 요청하는 과정
2. 자원이 없으면 condition queue(R_Free)에서 기다려라(wait)
3. 자원이 있다면 자원을 빌려가고 R_available을 false로 바꿈
4. 다른 프로세스가 대기실(condition queue)에 있다면 

1. procedure requestR()을 통해서 자원을 요청하는 과정
2. R_available(자원을 빌려갈 수 있는지..) 를 true로 만든다.
3. R_Free에서 기다리는 프로세스에게 signal을 날려줌(R_Free.signal())

이런 일련의 과정들이 가능한 이유를 내부 과정을 통해 살펴본다.

 

자원 할당 시나리오

• 자원 R 사용 가능 (R은 밖에 있다고 가정한다)
• Monitor 안에 프로세스 없음

Monitor에는 한개의 프로세스만 들어갈 수 있음!.

 

• 프로세스 Pj 가 모니터 안에서 자원 R 을 요청

자원의 갯수를(있는지 없는지) R_Available가 나타냄.

1. 최초에 하나의 프로세스(Pj)가 자원을 요청하기 위해서 requestR()로 들어감
2. R_Available을 1에서 0으로 바꿈(내가 자원을 가져갔으니까)
3. Pj를 밖에서 자원을 사용한다.
4. 이때 또 다른 프로세스(Pk,Pm)가 entry queues for request()에서 자원을 빌리기 위해 대기한다.
5. Pk가 monitor안에 아무도 없으니 들어갈 것이다. 
6. R_Available(자원)이 0이므로 condition queue R_Free에 가서 대기한다. (Pm도 마찬가지)

 

• 자원 R 이 Pj 에게 할당 됨
• 프로세스 Pk 가 R 요청 , Pm 또한 R 요청

1. Pj가 자원을 다 썼으면 Pj는 entry queues for releaseR()로 들어간다. 
2. Pj는 Monitor에 아무도 없으므로 releaseR()에 들어가서 반납한다. 
3. R_Available은 0에서 1이 된다. (이후 Pj가 바로 Pk를 깨우러 간다면 Monitor에 Pj가 있기 때문에 Pk는 Monitor에 진입하지 못한다)
4. Pj는 signaler queue에 들어간다. (이제 Monitor에 어떠한 프로세스도 없다)
5. Pj가 Pk를 깨우러감

 

• Pj 가 R 반환
• R_Free.signal () 호출에 의해 Pk 가 wakeup

1. Pk는 requestR()에 들어가 자원을 빌리고 R_Available을 0에서 1로 바꾼다. 

• 자원 R 이 Pk 에게 할당 됨
• Pj 가 모니터 안으로 돌아와서 , 남은 작업 수행

1. Pk는 밖에 나가서 R(자원)을 사용한다.
2. Pj가 releaseR()에 들어가서 남은 일(releaseR()에서는 자원을 반납하고 그 자원을 다른 프로세스가 가져가게 한 다음에 추가적으로 마무리 작업을 할 것이다)을 마무리한다.

Monitor에 들어오는 작업들을 Language가 보장해준다. (실제 코드로 간단하게 구현할 수 있음)

 

CircularQ 를 사용하는 Producer-Consumer Problem에서는 어떨까?

• 프로시저는 두개 정의
  • => entry queue for fillBuf() (데이터를 넣음), entry queue for emptyBuf() (데이터를 사용)
• conditional queue 두개 정의
  • = >bufHasSpace(공간이 있는가?), bufHasData(데이터가 있는가?)
• Critical data (shared data)
  • in => producer가 어디에 데이터를 넣을지, out => consumer가 어디에 데이터를 가져갈지 위치를 나타내는 변수
  • validBufs => 물건의 개수

 

Monitor (Producer-Consumer Problem)

Procedure fillBuf(data : message): 

1. 먼저 공간이 있는지 확인 (validBufs(데이터 수가) == N 인가?), 즉, 공간이 다 찼는지 확인함.
2. 공간이 다 찼다면 bufHasSpace.wait()가서 기다림
3. 공간이 있다면? 데이터를 놓는 위치 buffer[in]에다가 데이터를 놓는다. 
4. 데이터를 놓았으니 데이터 수 증가
5. 그 다음 데이터를 놓을 공간을 지정해줌(in +1) (CircularQ 이므로 mod연산을 수행)
6. 혹시 데이터를 기다리는 프로세스가 있다면 깨워주러 감 ( vufHasData.signal() )

Procedure emptyBuf(var data : message):

1. 데이터가 있는지 확인함 
2. 0개면 데이터가 생기길 기다림
3. 데이터가 있거나 생기면 데이터를 가져옴
4. 데이터의 수를 감소시킴(validBufs - 1)
5. 꺼낼 위치를 갱신함(out +1)
6. 나가면서 공간을 기다리는 프로세스가 있다면 깨워라.

 

Reader Writer Problem

• 읽는 건 여러 프로세스, 쓰는건 하나의 프로세스가 가능
• reader/writer 프로세스들간의 데이터 무결성 보장 기법
• writer 프로세스에 의한 데이터 접근 시에만 상호 배제 및 동기화 필요함

모니터 구성

• 변수 2 개
  
  • 현재 읽기 작업을 진행하고 있는 reader 프로세스의 수
  • 현재 writer 프로세스가 쓰기 작업을 진행 중인지 표시
• 조건 큐 2 개
  
  • reader/writer 프로세스가 대기해야 할 경우에 사용
• 프로시져 4 개
  
  • reader(writer) 프로세스가 읽기 (쓰기) 작업을 원할 경우에 호출 , 읽기(쓰기) 작업을 마쳤을 때 호출

====수정예정=====

각 과정 정리해보기

===============

 

Dining philosopher problem

• 5 명의 철학자
• 철학자들은 생각하는 일 , 스파게티 먹는 일만 반복함
• 공유 자원 : 스파게티 , 포크
• 스파게티를 먹기 위해서는 좌우 포크 2 개 모두 들어야 함

 

포크를 집는 과정

1. procedure pickup 에서는 내가 사용할 수 있는 포크가 2개인가 를 검사함
2. 없으면 각자 자기만의 방에 들어가서 기다림 (누군가 나를 깨우기를 기다린다.) ready에 가서..
3. 내가 포크를 집는다는 것은 내 왼쪽 오른쪽의 철학자들은 사용 가능한 포크가 1개씩 줄어든다는 의미
4. 포크수를 줄이고 Monitor를 빠져나옴

포크를 내려놓음 (내가 음식을 다 먹어야 다른 사람도 포크를 집어들 수 있다.)

1. 포크를 내려놓는다 => 내 왼쪽 오른쪽 사람이 쓸 수 있는 포크 수가 1개씩 증가한다.
2. 내려놓은 다음에 내 오른쪽이 포크를 기다렸는지 확인함
3. 기다렸다면 오른쪽을 깨워줌
4. 왼쪽도 마찬가지 방법으로 수행함.

(Monitor의 특징: Monitor에는 최대 1명 들어갈 수 있음)

numForks: 철학자들이 사용 가능한 포크 수

각 철학자들은 자기만의 대기실을 가지고 있다. 

 

Monitor 장점

• 사용이 쉽다 (에러 발생 가능성 낮음)
• Deadlock 등 error 발생 가능성이 낮음

Monitor 단점

• 지원하는 언어에서만 사용 가능
• 컴파일러가 OS 를 이해하고 있어야 함
  
  • Critical section 접근을 위한 코드 생성

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---