[OS] Chap07. Synchronization Example

해당 글은
경희대학교 조진성, 허선영 교수님의 강의 자료 및 내용을 정리한 글입니다
개인적으로 공부하며 작성된 글이라 잘못된 부분이 있을 수 있습니다!
오류가 있다면 알려주세요

 

 

Background

• Process들은 concurrently하게 실행될 수 있고, 언제든지 interrupted 될 수 있음
• 데이터 일관성을 유지하기 위해서는 프로세스간의 orderly한 실행을 보장하는 메커니즘을 필요로 함
• Race condition: shared data에 대한 엑세스가 제어되지 않을 경우 발생함. 실행 결과가 엑세스 발생 특정 순서에 따라서 달라지거나, 데이터 값의 손상을 초래할 수 있음
• Process는 변수 값 변경, table update, 파일 작성을 수행하면서 코드의 중요한 Critical Section를 가짐

 

앞서 공부한 Tools을 통해서 어떤 Synchronization 문제를 해결할 수 있는지 알아보자!

 

 

 

Bounded-buffer Problem

[문제]

$n$개의 고정된 buffer 크기. 각 buffer는 하나의 데이터를 hold할 수 있다

Producer와 Consumer가 어떻게 같은 bounded buffer를 hold할 수 있을까?

 

[해결] → Semaphore

• mutex : 1로 초기화. mutual exclusion을 제공하기 위함
• full : 0로 초기화. 채워진 buffer의 갯수를 count
• empty : $n$로 초기화. 비어있는 buffer의 갯수를 count

Producer code

while (true) {
/* produce an item */
    wait(empty); 	//empty buffer가 존재해야 채울 수 있으므로, 기다린다
    
    // critical section에 진입하기 전에 확인합니다 
    wait(mutex); 	//semaphore 값이 0보다 작거나 같을 경우 기다리다가, 커지면 -1하고 진입
    /* add the item to the buffer */
    signal(mutex); 	//semaphore 값을 +1
    
    signal(full);	// buffer가 하나 채워졌음을 알려주는 역할
}

 

Consumer code

while (true) {
 wait(full); 		//full buffer가 존재해야 쓸 수 있으므로, 기다린다
    
    wait(mutex); 	//위와 동일하다
    /* remove an item from buffer */
    signal(mutex);
    
    signal(empty);	//소모한 buffer에 대한 작업을 알리기 위함
    /* consume the item */
}

 

 

 

Readers-Writers Problem

Data set이 여러 process에 의해 공유되고 있고, readers와 writers의 역할이 존재함

 

[문제] 

여러 명의 reader는 동시에 접근할 수 있지만, 데이터를 업데이트하는 writer는 한 명만이 접근 할 수 있다.

 

[해결]

First readers-writers

 readers에 우선권 주기. writer가 글을 쓰지 않는 한, 어떤 reader도 기다려서는 안된다

 해당 방법은 writer에서 starvation이 발생할 수 있다는 문제가 있어요👎

• mutex : 1로 초기화. mutual exclusion을 제공하기 위함
• rw_mutex : 1로 초기화. readers와 writers.를 동기화 시키는 역할
• read_count : 0로 초기화. 현재 읽고 있는 reader의 개수를 count

Reader code

while (true) {

	wait(mutex);
    
    read_count++;
    if (read_count == 1)	//첫번째 reader인 경우, writer가 접근 못하게 data lock
    	wait(rw_mutex);
    
    signal(mutex);
    /*reading is performed*/
    wait(mutex));
    
    read_count--;
    if (read_count == 0)	//마지막 나가는 reader가 해당 data lock 해제
    	signal(rw_mutex);
        
    signal(mutex);
}

 

Writer code

while (true) {

	wait(rw_mutex);		//rw_mutex의 값이 0보다 크게 되면 데이터로 접근할 수 있음! 그 전까지 기다림
    /*writing is performed*/
    signal(rw_mutex);
}

 

 

Second readers-writers

 writers에 우선권을 줍니다. 새로 들어오는 reader는 기다리게 하고, writer의 처리를 우선적으로 하는 것임!

 마찬가지로 reader에 starvation이 발생할 수도 있어요 👎

 

일부 시스템에서는 kernel에서 reader-writer lock을 제공하여, 문제를 해결한다고 하네요

 

 

 

Dining-Philosophers Problem

[문제]

 

$N$명의 철학자가 원형의 식탁에서 식사를 하고 있다

자신의 양옆에 있는 젓가락 2개를 가져가야만 식사가 가능하므로, 

누군가 식사를 할 때 양 옆의 철학자는 동시에 식사할 수 없다

 

 

 

 

 

[해결]

 

Semapohre

• Semapore chopstick[5] : 1로 초기화

Philosopher code

while (true) {

	//wait를 순서대로 불러서, chopstick 0-1 순서로 가져간다
    //wait이 되므로 양 옆의 철학자는 chopstick이 올 때까지 기다려야함
	wait (chopstick[i]);
    wait (chopstick[(i+1)%5]);
    
    /*eat for awhile*/
    
    signal (chopstick[i]);
    signal (chopstick[(i+1)%5]);
    
    /*think for awhile*/
    
}

그러나, 순서대로 젓가락을 가져가는 과정에서 문제가 발생할 수 있다👎

각 프로세스가 하나씩 젓가락을 잡을 경우 아무도 데이터에 접근하지 못하는 Dead lock 상태에 걸린다

 

 

Monitor : class object를 구현함

• enum state[5] : 각 철학자의 상태를 array로 표현함
• condition 개념을 사용

Philosopher code

//젓가락을 집으려고 기다림. 집지 못한 경우 기다림
DiningPhilosophers.pickup(i);

/* E A T */

//젓가락을 내려놓음
DiningPhilosophers.putdowm(i);

Deadlock은 발생하지 않지만👍, Starvation이 발생할 수도 있습니다👎!

 

 

 

Synchronization in Linux

• version 2.6~ 의 Linux는 interrupt를 허용합니다. fully preemptive!
• Semaphore / Atomic integers / Spinlocks / Reader-writer version of both 를 제공함
• single core에서는 spinlock에 의한 에너지 소모를 줄이고자 interrupt able/disable이 가능함. ex) 임베디드

 

 

 

POSIX Synchronization

여러 방법을 제공하고 있습니다

UNIX, Linux, macOS에서 widely하게 사용됨

 

Mutex Locks

 

Semaphores

• named: 여러 프로세스가 이름(string)을 통해서 이를 사용할 수 있음
• unnamed: 하나의 프로세스 내에서만 공유. thread 간의 동기화를 위함
  • sem_post를 wait보다 먼저 해주면 안 됩니다!
  • 중요한건 초기화 값! (아래는 1로 초기값 설정함)

 

condition variable

 

semaphore와 condition variable의 차이 잘 알아둡시다

둘 다 wait-signal의 형태인데,

semaphore의 경우는 integer 값에 따라서 wait()를 할지말지 결정하는 것

condition variable의 경우는 일단 wait()를 하고, signal()이 불려질 때까지 기다리는 것

 

끝!