[Chapter 7,8]
I. Synchronization Example
A. Bounded Buffer Problem
1. 문제점: 첫번째로 count가 shared resource이지만 critical section이 보호되지 않고, 두번째로 busy waiting을 사용해서 CPU Utilization이 떨어진다.
2. 세마포어: 3가지의 세마포어를 사용해서 해결한다.
mutex는 lock을 걸기위해 사용하는 바이너리 세마포어이다.
empty와 full은 카운팅 세마포어로 busy waiting을 사용하지 않도록 하기 위해서 사용한다. 이전에는 Producer 프로세스가 큐 안에 데이터를 넣을때 카운트가 n과 동일하면 busy waiting을 하도록 구현되었는데 wait(empty)를 통해서 busy waiting을 사용하지 않고 빈 공간 의 갯수를 의미하는 세마포어 empty의 티켓이 존재할때만 진입할 수
있도록 한다.
empty=0이라는 것은 큐가 가득 찼다는 뜻이다. empty에서 진입한 경우는 mutex을 통해서 lock을 걸고 shared resource에 접근하고 작업이 끝나고 signal(mutex)을 통해서 mutex를 풀어 주고 signal(full)을 통해서 full 세마포어의 값을 1 증가시킨다.
Consumer는 데이터가 들어가있는 공간의 개수인 full이 1이상일때만 shared resource에 접근 할 수 있고 만약 full이 0인 상황이었다면 wait에서 기다리고 있다가 context switching되어 Producer에서의 signal이 실행되면 접근할 수 있게 된다.
3. MutexLock과 Conditional Variable사용: 과정은 세마포어를 사용하는것과 대부분 동일하다.
critical section을 lock으로 보호하고 not_full과 not_empty conditional variable로 비어있는지 꽉 찼는지 여부를 true/false로 관리한다.
B. Readers And Writers Problem
1. 문제점: 여러개의 동일한 프로세스들이 하나의 shared resource에 읽거나 쓰는 동작을 한다. 쓰는 작업은 mutually exclusive하게 동작해야하지만 읽는 작업은 여러명이 접근해도 상관없 다. Writer의 작업은 공유자원을 오염시킬 수 있기 때문이다.
Writer 프로세스는 exclusive하게 동작해야하며 다른 Reader, Writer프로세스와 동시에 접근하면 안된다.
문제를 해결하기위해서 3개의 세마포어를 사용한다.
wrt는 쓰기 작업 세마포어로 쓰기 작업을 할 수 있는 권한을 하나의 프로세스에만
준다. Writer의 작업을 Mutually exclusive하게 만들어준다.
mutex 세마포어는 Reader가 읽기작업을 하려면 wait(mutex)를 통해 세마포어가 있어야허용 함으로써 readcount를 보호한다. readcount세마포어는 읽고있는 프로세스의 개수를나타낸다. readcount가 0이 되어야 쓰기 작업을 수행할 수 있다.
readcount, wrt, mutex는 전역변수로 선언이 되는데, 멀티스레드 환경에서 동작하기 위해서 전역변수로 사용할 수 밖에 없지만 사용 시 주의가 필요하다.
쓰기 작업을 원하는 프로세스는 readcount세마포어가 0이 될때까지 wait한다. 읽기는 mutex세마포어를 사용해서 readcount값을 증가시키는 critical section을 보호한다. 읽기가 끝나면 readcount를 감소시키고 readcount가 0이라면 Writer프로세스는 wrt 세마포어를 획득하여 쓰기 작업을 진행한다.
C. Dining Philosopher Problem
1. 정의: 다익스트라가 만든 데드락을 검증하기 위한 가상의 동기화 문제이다. 철학자들이 앉아있는 원탁이 존재하고 사람 사이에 젓가락이 하나씩 놓여있다. 철학자는 앉아서 생각하다가 배고프면 양쪽에서 젓가락을 잡아서 밥을 먹고 돌려놓은 다음 다시 생 각한다. 철학자들은 왼쪽 젓가락이 사용가능하면 왼쪽 젓가락을 먼저 잡고 오른쪽 젓가락 이 사용 가능하면 가져와서 밥을먹고 오른쪽 젓가락을 내려놓은 다음 왼쪽 젓가락을 내려 놓는다. 만약 오른쪽 젓가락이 사용중이면 기다린다.
여기서 철학자는 프로세스이고 젓가락은 shared resource이다. 만약 모든 철학자가 동시에 왼쪽 젓가락을 잡는다면, 모든 철학자들이 자신의 오른쪽 젓가락이 사용가능해질 때까지 기다려야한다. 이렇게 되면 모든 철학자가 영원히 굶는 상황이 되는데 여기서 나온 단어가 starvation이다. 모든 프로세스가 다른 프로세스가 사용중인 자원을 기다리는 이런 상황을 deadlock이라고 한다.
2. 해결방법: 왼쪽과 오른쪽 젓가락을 한번에 가져오는 것이 아니라서 발생하는 문제이다.왼 쪽 젓가락과 오른쪽 젓가락이 사용가능한지가 아니라 철학자의 상태를 세마포어로 두고 왼쪽과 오른쪽의 철학자가 먹고있는지를 고려하고 두개를 동시에 pickup한다.
mutex는 상호배제를 위한 세마포어이고 s는 자신이 pickup가능한 상태인지를 알려주는세마 포어이고 state는 철학자들의 상태를 저장한다.
철학자들은 thinking hungry eating중 하나의 상태를 가진다.
철학자가 젓가락을 가져오려면 hungry상태가 되어야 하고 pickup을 수행할때는 자신의 상 태를 hungry로 변경하고 test를 수행한다. 왼쪽,오른쪽의 철학자가 먹고 있는 상태가 아니면 eating으로 상태를 바꾸고 내가 먹을 수 있는지에 대한 세마포어인 s[i]를 signal로 반환한다. 그럼 pickup에 있는 wait을 수행할 수 있게 된다.
putdown을 수행할때도 critical section을 보호하고 내 상태를 think로 바꾼 다음 왼쪽과 오른 쪽에 test를 수행해서 가져가라고 알려준다.
중요한 점은 젓가락이 아닌 철학자들의 상태값을 세마포어로 잡는 것이다.
D. 실제 사용하는 동기화 툴
1. Posix Synchronization: C,C++계열은 POSIX표준을 사용한다.
# include <semaphore.h>로 세마포어 라이브러리를 사용한다.
<pthread.h>에서 mutex와 conditional variable을 사용할 수 있다.
2. Java: Monitor를 사용한다. synchronized 키워드를 사용해서 동기화 영역을 선언할 수 있다. 세마포어나 Mutex와 Conditional Variable도 사용할 수 있다.
II. Deadlock
A. 데드락의 정의
1. 상황: 두 개 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다리며 무 한히 대기하는 상태에 빠지는 것.
세마포어와 같은 동기화 툴을 사용하면서 발생하는문제이다.
B. 데드락 발생 조건
1. Mutual exclusion: 한번에 한 프로세스만 리소스에 접근할 수 있다.
2. Hold and wait: 한 프로세스가 한 개 이상의 리소스를 점유한 상태에서 다른 리소스를 추가 로 점유하기 위해 기다린다.
3. No Preemption: 프로세스가 리소스를 잡고 작업이 완료될때까지 리소스를 놓지 않아야 한 다. (강제로 다른 프로세스의 자원을 빼앗을 수 없다)
4. Circular wait: p0은 p1이 가지고 있는 리소스를 기다리고 p1은 p2.. 다시 p0의 리소스를 기다 리는 순환형으로 리소스를 기다려야 한다.
이 4가지 조건을 동시에 충족해야 deadlock이 발생한다.
C. Deadlock handling
1. Deadlock Prevention: 데드락 발생 조건중 하나 이상을 충족되지 않게 만들어서 데드락을 방 지한다.
상호배제 부정: 여러 프로세스가 공유자원을 사용할 수 있도록 한다.
점유대기 부정: 프로세스 실행 전에 모든 자원을 할당한다.
비선점 부정: 자원 점유중인 프로세스가 다른 자원을 요구할때 가진 자원을 반납한다. 순환대기 부정: 자원에 고유번호를 할당하고 순서대로 자원을 요구한다.
2. Deadlock Avoidance: 운영체제가 데드락이 발생하는 상황을 런타임에서 모니터링해서 발생 하는지를 계속 테스트한다. 발생하기 이전에 커널이 처리하는 것. 모니터링 및 방지를 함 께 하므로 운영체제의 오버헤드가 커지는 문제가 있다.
대표적인 Avoidance 알고리즘으로 은행원 알고리즘이 있다. 은행에서 모든 고객의 요구를 충족하도록 현금을 할당하는 것에서 유래됐다.
프로세스가 자원을 요구할 때 운영체제는 자원을 할당한 후에도 프로세스가 안정상태로 남아있는지를 사전에 검사해서 안정상태이면 자원을 할당해주고 아니면 다른 프로세스의 자원이 해지될때까지 기다림으로써 교착상태를 회피한다.
3. Deadlock detection and recovery: 데드락이 발생했을 때 운영체제가 찾아내서 풀리도록 관리 하는 방식이다. detection과정에서 알고리즘을 수행해야 하기 때문에 운영체제 오버헤드가 커서 사용하지 않는다.
recovery 하는 방법은 교착 상태를 일으킨 프로세스를 종료하거나 프로세스를 일시 정지하 고 교착상태의 자원을 기다리고 있는 프로세스에게 할당하는 방법이 있다. 4. Deadlock ignorance: 데드락을 무시한다. Ostrich Algorithm이라고도 하며 타조가 위험이 발생 하면 모래에 머리를 박고 무시하는것에서 나왔다.
사용하지 않는 방식이다.
D. Dining Philosopher
1. Deadlock의 가장 대표적인 예시이다.
젓가락을 여러명이 동시에 사용할 수 없으니 mutual exclusion을 만족하고, 젓가락을 hold and wait하고, 잡은 이후 내려놓지 않으므로 No Preemption을 만족하고, 모든 철학자가 왼쪽 을 동시에 들면 circular wait을 만족한다.
젓가락이 아닌 철학자의 상태값을 세마포어로 잡아서 문제를 해결하는 방법은 하나를 잡 고 다른 젓가락을 기다리는 것이 아닌 상태를 확인하고 두개를 동시에 잡을 수 있도록 해서 hold and wait을 해결함으로써 deadlock을 해결한 예시이다.