운영체제 OS - 동기화 (Process Synchronization), 상호배제(mutual exclusion), 세마포어(semaphore)

다중 프로그래밍 시스템
여러 개의 프로세스들이 존재
프로세스들은 서로 독립적으로 동작
공유 자원 또는 데이터가 있을 때 문제 발생 가능

동기화
프로세스들이 서로 동작을 맞추는 것
프로세스들이 서로 정보를 공유하는 것

비동기적 (Asynchronous)
프로세스들이 서로에 대해 모름
병행적 (Concurrent)
여러 개의 프로세스들이 동시에 시스템에 존재
=> 병행 수행중인 비동기적 프로세스들이 공유자원에 동시 접근 할 때 문제가 발생 할 수 있음

Shared data 공유 데이터
Critical section 임계 영역 - 공유 데이터를 접근하는 코드 영역
Mutual exclusion 상호배제 - 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것

machine instruction의 특성
atomicity (원자성), Indivisible (분리불가능)
한 기계어 명령의 실행 도중에 인터럽트 받지 않음

Mutual exclusion
한 process가 Critical Section에 있으면 다른 process의 접근을 막는 것
Progress
CS안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해 하면 안됨
Bounded waiting
프로세스의 cs진입은 유한시간 내에 허용되어야 함

Mutual exclusion primitives 
(primitive ~ 가장 기본이 되는 연산)
- enterCS() primitive
critical section진입 전 검사
다른 프로세스가 critical section안에 있는지 검사
- exitCS() primitive
critical section을 벗어날 때의 후처리 과정
critical section을 벗어남을 시스템이 알림

Mutual Exclusion Solution

SW solution
Dekker's Algorithm
Two precess ME을 보장하는 최초의 알고리즘

f0 ← false
f1 ← false
turn ← 0   // or 1

 p0:                                 p1:
     f0 ← true                         f1 ← true
     while f1 {                          while f0 {
         if turn ≠ 0 {                      if turn ≠ 1 {
             f0 ← false                         f1 ← false
             while turn ≠ 0 {                  while turn ≠ 1 {
             }                                   }
             f0 ← true                          f1 ← true
         }                                   }
     }                                    }

    // 임계 구역                          // 임계 구역 
    ...                                   ...
    // 나머지 구역                        // 나머지 구역
   turn ← 1                             turn ← 0
   f0 ← false                           f1 ← false

N-Process Mutual Exclusion
Dijkstra's Algorithm

SW solution들의 문제점
속도가 느림, 구현이 복잡 ME primitive 실행 중 preemption될 수 있음 (overhead)

HW Solution
TestAndSet (TAS) instruction
Test와 Set을 한 번에 수행하는 기계어
실행 중 interrupt를 받지 않음

// target을 검사하고, target 값을 true로 설정
boolean TestAndSet(boolean *target){
   boolean temp = *target;    // 이전 값 기록
   *target = true;            // true로 설정
   return temp;                    // 값 반환
}

3개 이상의 프로세스의 경우, Bounded waiting 조건 위배
N-process mutual exclusion

do{                                            // 프로세스 Pi의 진입 영역
   waiting[i] = true;
   key = true;
   while(waiting[i] && key)
      key = TestAndSet(&lock);
   waiting[i] = false;
       //임계 영역
       //탈출 영역
   j = (i + 1) % n;
   while((j != i) && !waiting[j])    // 대기 중인 프로세스를 찾음
      j = (j + 1) % n;                    
   if(j == i)                                // 대기 중인 프로세스가 없으면
      lock = false;                        // 다른 프로세스의 진입 허용
   else                                        // 대기 프로세스가 있으면 다음 순서로 임계 영역에 진입
      waiting[j] = false;                // Pj가 임계영역에 진입할 수 있도록
       //나머지 영역
}while(true);

단점 Busy waiting이 아직 존재한다.

OS supported SW solution
Spinlock
멀티 프로세스에서만 사용 가능
정수 변수
초기화, P(), V() 연산으로만 접근 가능
위 연산들은 indivisible 연산 OS Support -> 아직도 Busy waiting

P(S){
while(s<=0)do 
    endwhile;
    S <- S-1;
}

V(S){
	S<-S+1;
}

Semaphore
Dijkstra가 제안, Busy waiting문제 해결
음이 아닌 정수형 변수 (S)
초기화 연산, P(), V()로만 접근 가능
P: probern(검사)
V: verhogen(증가)
모두 visible OS가 보장한다.
wake-up순서는 비결정적 Starvation problem

임의의 s 변수 하나에 ready queue 하나가 할당 됨

Binary semaphore 
S가 0과 1 두 종류의 값만 갖는 경우, 상호배제나 프로세스 동기화의 목적으로 사용
Counting semaphore
S가 0이상의 정수값을 가질 수 있는 경우
Producer-Consumer문제 등을 해결하기 위해 사용

Window, Unix/Linux에서 실제 사용하고 있다.

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

상호배제 문제

프로세스 동기화 문제 : Process들의 실행 순서 맞추기 - 프로세스들은 병행적이며, 비동기적으로 수행

생산자-소비자 문제 : producer process - shared memory buffer - consumer process
buffer가 critical section이 된다. 
buffer가 1일때 

N-buffer

Reader-writer문제
데이터에 대해 읽기 연산만 수행, 데이터에 대해 갱신 연산을 수행
데이터 무결성 보장 필요 reader,writer에 대한 우선권 부여

Dining philosoper problem

Eventcount/ Sequencer (SW solution)
Semaphore starvation문제 해결
semaphore보다 더 low-level control이 가능

Sequencer (은행 번호표)
정수형 변수 생성시 0으로 초기화, 감소하지 않음, 발생 사건들의 순서 유지
ticket()연산으로만 접근 가능

ticket(S)
현재까지 ticket()연산이 호출 된 횟수를 반환

Eventcount
정수형 변수, 생성시 0으로 초기화, 감소하지 않음

read(E)
현재 Eventcount값 반환
advance(E)
E를 기다리고 있는 프로세스를 깨움
await(E,v)
v는 정수형 변수
if(E<v)이면 E에 연결된 Qe에 프로세스 전달 및 CPU scheduler 호출

Monitor (language-level solution)
JAVA Monitor Class
Object-Oriented concept와 유사
Critical data & Critical sections를 모아둔 방

Entry queue(진입 큐) - procedure수만큼 존재
Mutual exclusion - 모니터 내에는 항상 하나의 프로세스만 진입 가능 language가 보장
Information hiding -공유 데이터는 프로세스만 접근 가능
Condition queue - 특정 이벤트를 기다리는 프로세스가 대기
Signaler queue - 프로세스에 signal을 보내기 위한 공간

장점 : 사용이 쉽다, Deadlock등 error 발생 가능성이 낮음
단점 : 지원하는 언어에서만 사용 가능, 컴파일러가 OS를 이해하고 있어야 함