[OS] 8. Synchronization

1. 개요

- 하나의 프로세스에서 2개 이상의 Thread가 Concurrent하게 작업할 때 같은 Address space를 공유하기 때문에 같은 Data를 사용할 수 있다.

- 이 상황을 Race Condition이라고 하고 이는 Non-deterministic한 결과를 낳는다.

- Race Condition 때 발생하는 문제를 해결하기 위해 Synchronization을 수행한다.

 

cf) Scheduling은 OS 권한으로 프로그래머가 통제할 대상이 아님.

 

 

2. Critical section : 임계영역

- 공유되는 자원(resource)를 사용하는 Code 부분

 

 

3. Lock

프로세스의 shared resource에 대한 점유 상태를 나타내는 것으로써 상호배제(Mutual Exclusion : Mutex)를 제공

acquire(); // entry section(진입영역) : 공유된 자원의 사용 권한을 얻는 과정

// critical section(임계영역)

release(); // exit section(퇴출영역) : 점유한 자원을 놓아주는 과정

// reminder section(나머지 영역)

 

Property

1) Correctness

- Mutex : critical section을 동시에 점유할 수 없다.

- Progress : 자신의 critical section을 점유하는 다른 프로세스가 없을 때 반드시 점유할 수 있다. 즉 점유할 프로세스가 선택되는 것이 무기한 연기되지 않는다.

- Bounded waiting : Starvation-free를 보장한다.

 

2) Fairness

3) Performance

 

 

4. Implement

1) Init attempt : Peterson's Solution

void acquire(struct lock *l){
	
    while(l->held); // 점유가 풀릴 때까지 spin
    
    l->held = true; // 점유
}

상호배제가 보장되지 않는다.

 

2) Disable Interrupt

- acquire(), 연산, release()가 atomic하게 이루어져야 알맞은 연산이 이루어진다.

- 하지만 Interrupt 발생 시 preemption으로 atomic이 깨진다.

  (Time interrupt -> Scheduler -> preemption)

 

- 따라서 Interrupt를 끔으로써 atomic한 작업을 보장한다.

 

cf) multi-processor 환경에서는 모든 프로세스에 대해 Interrupt disable해야하므로 비효율적이다.

 

3) Test-And-Set

struct lock { int held = 0; }

int TestAndSet(int *v, int new_value){
	
    int old = *v;
    *v = new_value;
    
    return old;
}


void acquire(struct lock* l){
	
    while(TestAndSet(l->held, 1));
    
    ...
}

상호배제 보장(spin-lock과 비교해보자)

 

4) CompareAndSwap

int CompareAndSwap(int* v, int expect, int new_value){
	
    int old = *v;
    
    if(old == expect)
    	*v = new_value;
     
     return old;
}

 

5. High level synchronization

1) Spin lock (busy-wait) (⊂Mutex lock)

- Simple, No need to context-switch : critical section이 짧을 때 유리

- busy-wait로 인한 자원 소모, Progress 특성 보장 X

 

cf) 보통 busy-wait와 interrupt disable을 같이 사용하여 단점 보완

 

 

2) Semaphore

- 값 S를 통해 상태표현

- if S>=0, enter()

- else (S<0), wait()

 

- wait() : S--, wait until S>=0

- signal() : S++

 

 

6. Classic Problem of Synchronization

1) Bound Buffer Problem

- 원인 : 동시에 produce or consume

- 해결 : Semaphore 적용

int mutex = 1;
int empty = N, full = 0;

// 소비자 프로세스 입장에서의 flow, 생산자 프로세스는 대칭적 구조
wait(&full);
wait(&mutex);

// critical section

signal(&mutex);
signal(&empty);

 

2) Readers-Writers Problem

- 문제 : readers와 writers의 concurrent한 공유된 자원 사용

- 해결 : Semaphore

int readCnt = 0, mutex = 1, rw = 0;
...

cf) writer가 reader의 수가 0이 될 때까지 wait한다면 starvation이 일어날 수 있다.

    이를 해결하기 위해 writer wait semaphore를 사용한다면 반대로 reader의 starvation이 일어날 수 있다.

 

 

3) Dining Philosopher Problem

- 문제 : 하나의 task가 여러 개의 shared resource를 사용할 때 적절한 순서를 가지지 못하면 Dead lock(Circular wait)

- 해결 : 마지막 task만 선택하는 shared resource의 순서를 바꾸면 간단하게 해결 가능