[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()이 불려질 때까지 기다리는 것
끝!