[OS] 6. 프로세스 동기화 - Mutual Exclusion OS supported SW Solution (Spinlock / Semaphore)

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

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

(비 효율적인 SW, HW의 솔루션 과정들을 통해 OS에서 해결하는 과정을 보게됨.)

OS supported SW solution

Spinlock

• 정수형 변수(특별한 변수)
• 초기화 , P(), V() 연산으로만 접근 가능

위 연산들은 indivisible (or atomic) 연산이다 => OS가 이를 보장함.

전체가 한 instruction cycle 에 수행 됨

(S: 물건 개수, P: 물건을 꺼내는 것, V: 물건을 집어넣는 것)

즉, 위의 연산은 실행될 때 중단될 수 없다. 

1. active라는 spinlock 변수가 있다고 가정하고 1로 설정 (물건이 있는 상태)
2. P연산을 하면 물건이 있으니까(1) CS에 들어감. 
3. 물건을 0으로 바꿈(active = 0)
4. Pi가 CS에 나가면서 물건을 반납함(active=1)
5. Pj는 P에서 돌다가 active가 1이 된 것을 보고 CS에 진입함

P, V는 OS에서 Preemption이 일어나지 않는 것을 보장하기 때문에 ME조건을 위배하는 것을 간단히 해결할 수 있다.

spinlock의 단점

멀티 프로세서 시스템에서만 사용 가능

1. 단일 프로세서인 경우에는 Pi가 CS에 들어가서 active = 0 으로 만들고 일을 할 것임
2. Pi가 CS진입한 상황에서 멈췄다면 Pj가 들어가려고 한다.
3. Pj는 while문에서 active가 1이 되는 상황을 기다림.
4. OS는 P 연산을 멈추는 것을 방해하지 않기 때문에 Pj는 계속 P연산을 수행하게 됨.
5. Pi가 V연산을 수행하고자 할 때, 단일 프로세서인경우에는 Pj가 이미 CPU할당을 받음
6. P연산을 계속 수행하고 있기 때문에 두 프로세스 전부 일을 하지 못함. 

Busy waiting!

• 여전히 P의 while문 문제

 

Semaphore

1965 년 Dijkstra 가 제안한 Busy waiting 문제를 해결함.

• 음이 아닌 정수형 변수 (S)
• 초기화 연산, P(), V()로만 접근 가능 (P: Probern 검사, V: Verhogen 증가)
• 임의의 S 변수 하나에 ready queue 하나가 할당 됨

Binary semaphore

• S 가 0 과 1 두 종류의 값만 갖는 경우
• 상호배제나 프로세스 동기화의 목적으로 사용

Counting semaphore

• S 가 0 이상의 정수값을 가질 수 있는 경우
• Producer Consumer 문제 등을 해결하기 위해 사용
• 생산자 소비자 문제

초기화 연산

S 변수에 초기값을 부여하는 연산

P() 연산 , 연산

P(S): 자물쇠를 거는 연산, V(S): 자물쇠를 푸는 연산

1. P(S) 물건이 있는지 if문으로 검사, 있다면 물건을 꺼내감
2. 없으면 else문으로 진입함

앞서 스핀락에서는 else문에서 while문이 반복되어 busy waiting문제가 있었음. 

그러나 semaphore는 S에 할당된 대기실(ready Q)에 대기함.

1. V(S)가 대기실에 있는 프로세스가 있다면 wake up 시긴다.
2. 기다리는 사람이 없다면 S에 +1을 하고 나가면 된다.

스핀락은 while문에서 돌면서 대기, semaphore는 대기실 이라는 큐에서 대기함.

모두 indivisible 연산

전체가 한 instruction cycle 에 수행 됨 (OS support)

Semaphore in OSs가 어디에 사용되는데?

Windows
MSDN : https://msdn.microsoft.com/en-us/library/windows/desktop/ms685129(v=vs.85).aspx

Unix/Linux
System V : https://docs.oracle.com/cd/E19683-01/816-5042/auto32/index.html

Semaphore 로 해결 가능한 동기화 문제들

• 상호배제 문제 (Mutual exclusion)
• 프로세스 동기화 문제 (process synchronization problem)
• 생산자 소비자 문제 (producer consumer problem)
• Reader writer 문제
• Dining philosopher problem
• 기타

상호배제 문제 (Mutual exclusion)

P와 V를 사용해 상호배제 문제를 해결함. 

Process synchronization

Process 들의 실행 순서 맞추기 (프로세스들은 병행적이며 , 비동기적으로 수행)

가정

1. Sync라는 세마포어 변수에 0이 있다. (물건이 없는 상태)
2. 이 물건을 Pj가 들고 있었다 라고 가정한다.
3. 프로세서 Pi가 두번째로 지나가야 하므로 Pi는 지나가도록 대기한다. 
4. Pj는 물건을 가지고 있으므로 Lj를 통과 할 때 반납한다.
5. V연산을 호출하고 Sync는 1이 된다. (P에 있는 대기 프로세서를 보고 깨운다)
6. Pi는 Li를 통과한다.

Producer Consumer problem

• 생산자 (프로세스)
  
  • 메시지를 생성하는 프로세스 그룹
• 소비자 (프로세스)
  
  • 메세지 전달받는 프로세스 그룹

생산된 데이터가 버퍼에 쌓인다. Consumer Process가 Buffer에 데이터를 놓는 동안에 가져가거나

Producer Process가 해당 버퍼에 또 다른 데이터를 가져다 놓으면 문제가 발생 할 것이다.

이 사이에 동기화가 필요하다. 이 문제를 해결하는 방법을 아래에 제시한다.

 

Producer Consumer problem with single buffer

Buffer는 한 프로세서만 접근해야한다. 

간단하게 Buffer가 한개일 때 생산자 소비자가 어떻게 접근하는지 알아보자

 

먼저 세마포어 3개 변수를 선언했다.(소비되었는지 확인, 생산되었는지 확인, 버퍼)

편의상 물건은 작업이라고 하자.

1. Producer Pi에 P(consumed)가 되었는지 확인한다. 
2. P(consumed)가 1이면 consumed semaphore를 1에서 0으로 바꾼다.
3. Buffer로 들어가서 물건을 놓는다.
4. 이후 V(produced) 수행하여 produced semaphore를 0에서 1로 바꾼다. 
5. Consumer Cj가 P(produced)가 1인지(생산되었는지) 확인한다.
6. 없으면 대기함.
7. Producer Pi에서 V(produced)가 1이된순간 Consumer Cj의 P(produced)가 1로 바뀜
8. 즉, 물건이 버퍼에 있으니까 소비하러 감. (Consumer Cj가 buffer로 들어감)
9. V(consumed)가 1이 된다. 

생산되었는지 소비되었는지 체크한다..

 

Producer Consumer problem with N buffers

 

여러 프로세서가 일할 수 있으므로 한 버퍼에 한 프로세서만 일하라는 것을 지정한다.

P(mutexP)부터 V(mutexP)까지 Critical Section 이다.

 

위의 한개의 버퍼일때와 동작은 비슷하게 작동한다.

한번에 하나의 프로세서만 일하게 하기 위해 P(mutexP)부터 V(mutexP)까지 한번에 동작한다. 

 

1. Procude가 생산하러 왔다. 먼저 Buffer가 있는지 확인한다. P(nrempty)연산 수행
2. 공간이 없으면 공간이 생길때까지 대기한다 
3. 즉 P(nrempty)가 0보다 크면 Producer가 buffer안에 들어가고 아니면 대기한다
4. 안으로 들어오면(CS) Buffer에 물건을 놓고(buffer를 M으로 만들고)
5. Curcular Q를 쓰므로 다음 위치를 업데이트한다
6. CS에 나오면 물건수 를 하나 더 늘려주고 나온다.
7. Consumer Cj는 Buffer에 물건의 개수를 체크한다. (P(nrfull))연산)
8. 물건을 꺼내고 
9. 꺼낼 위치를 갱신하고
10. 공간이 하나 늘었다고 바꾸고 나오게 된다.

생산자는 들어갈 때 공간이 있는지 확인하고 소비자는 꺼낼 때 물건이 있는지 확인한다. 

 

Reader Writer problem

• Reader
  
  • 데이터에 대해 읽기 연산만 수행 (여러개의 프로세서가 읽을 수 있음)
• Write
  • 데이터에 대해 갱신 연산을 수행 (여러개의 프로세서가 쓰면 문제발생)
• 데이터 무결성 보장 필요
  • Reader 들은 동시에 데이터 접근 가능
  • Writer 들 (또는 reader 와 write) 이 동시 데이터 접근 시 (상호배제 동기화) 필요
  • 이러한 문제를 Reader Writer problem이라고 한다. 세마포어로 해결
• 해결법
  • reader / writer 에 대한 우선권 부여
  • => reader preference solution
  • => writer preference solution

reader preference solution 일 때

1. 읽고 있을 때 Writer 쓰려고하면 못쓰게 한다. 
2. 그 사이 다른 reader읽고 가버리면 writer는 써야하는데 기다리게 됨.(reader가 있는 동안 계속 기다림)
3. 이를 reader preference solution 이라 한다

Reader를 보면 P(rmutex)~V(rmutex)가 두개가 있고 가운데

Perform read opeations (읽기 작업)이 수행됨을 알 수 있다. 

Reader 여러개가 읽을 수 있다고 하였는데 왜 mutex가 나타날까?

 

사전작업과 사후작업은 한명만 할 수 있기 때문에 mutex로 묶어놓은 것이다.

1. 처음에 현재 reader의 수를 체크한다. if(nreaders = 0)
2. 만약 읽는 사람이 없다면 P(wmutex)를 통해 writer는 읽지 말라는 연산을 수행한다. 
3. 만약 nreader가 0보다 크다면 누군가 작업을 하는 중이므로 writer에 대해 mutex를 할 필요가 없다.
4. P(wmutex)를 끝내고 읽는 사람의 수를 1개 증가시킨다. (이 작업도 CS에 들어가며 여러명이 증가시키면 안된다)
5. 읽으러 가는 사전작업은 내가 읽을 것이니까 writer가 못쓰게 막고 읽는 사람 1 증가
6. 읽는 작업을 수행하고 Reader는 나가는 과정을 수행하게 된다.
7. 마찬가지로 1명만들어가서 작업을 하게된다.
8. 내가 나갈 것이니 읽는사람 수를 줄이고 내가 마지막 reader였다면
9. V(wmutex)를 통해 writer가 써도 된다는 것을 알려준다.
10. 만약 nreader가 0이 아니면(읽는 작업자가 있다면) V(rmutex)를 수행하지 않는다.
11. 이렇게 동작하면 reader가 있다면 writer는 작업을 하지못한다.

reader가 우선권을 가지는 솔루션을 다음 방법처럼 정리할 수 있다.

 

Semaphore의 특징

• No busy waiting
  • loop를 돌면서 대기하지 않아도 됨 (대기실에서 대기함)
  • 기다려야 하는 프로세스는 block(asleep) 상태가 됨
• Semaphore연산의 단점
  • V연산은 누군가가 기다리고 있다면 wake up 해주는데 아무나 깨워준다 (wake up one of them)
  • 운없는(?) 프로세서는 계속 잠을 자고 있을 것이다.
  • Semaphore queue 에 대한 wake up 순서는 비결정적
  • 들어오는 순서대로 깨워주면 되지 않을까? (큐를 만들거나 다른 방법으로 푼다)
  • 이 문제에 대해 다음 포스팅 주제인 sequencial event counter를 통해 해결할 수 있음

 

---

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

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

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

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

---