동기화 예제
Bounded Buffer Problem
•
문제점: 첫째로 count가 shared resource이지만 critical section이 보호되지 않으며, 둘째로 busy waiting을 사용해서 CPU Utilization이 떨어진다.
•
세마포어: 3가지의 세마포어를 사용해서 문제를 해결한다.
◦
mutex는 lock을 걸기 위해 사용하는 바이너리 세마포어이다.
◦
empty와 full은 카운팅 세마포어로 busy waiting을 사용하지 않도록 한다. Producer 프로세스가 큐 안에 데이터를 넣을 때 count가 N과 동일하면 busy waiting을 하도록 구현되었는데, wait(empty)를 통해 빈 공간의 개수를 의미하는 세마포어 empty의 티켓이 존재할 때만 진입할 수 있도록 한다. empty=0은 큐가 가득 찼다는 뜻이다.
•
Producer는 empty에서 진입한 경우 mutex를 통해 lock을 걸고 shared resource에 접근하며 작업이 끝나고 signal(mutex)를 통해 mutex를 풀어주고 signal(full)을 통해 full 세마포어의 값을 1 증가시킨다.
•
Consumer는 데이터가 들어가 있는 공간의 개수인 full이 1 이상일 때만 shared resource에 접근할 수 있으며, 만약 full이 0인 상황이라면 wait에서 기다리고 있다가 context switching되어 Producer에서의 signal이 실행되면 접근할 수 있게 된다.
Readers and Writers Problem
•
문제점: 여러 개의 동일한 프로세스들이 하나의 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 세마포어를 획득하여 쓰기 작업을 진행한다.
Dining Philosopher Problem
•
정의: 다익스트라가 만든 데드락을 검증하기 위한 가상의 동기화 문제이다. 철학자들이 앉아 있는 원탁이 존재하고 사람 사이에 젓가락이 하나씩 놓여 있다. 철학자는 앉아서 생각하다가 배고프면 양쪽에서 젓가락을 잡아서 밥을 먹고 돌려놓은 다음 다시 생각한다. 철학자들은 왼쪽 젓가락이 사용 가능하면 왼쪽 젓가락을 먼저 잡고 오른쪽 젓가락이 사용 가능하면 가져와서 밥을 먹고 오른쪽 젓가락을 내려놓은 다음 왼쪽 젓가락을 내려놓는다. 만약 오른쪽 젓가락이 사용 중이면 기다린다.
•
여기서 철학자는 프로세스이고 젓가락은 shared resource이다. 만약 모든 철학자가 동시에 왼쪽 젓가락을 잡는다면, 모든 철학자들이 자신의 오른쪽 젓가락이 사용 가능해질 때까지 기다려야 한다. 이렇게 되면 모든 철학자가 영원히 굶는 상황이 되며, 여기서 나온 단어가 starvation이다. 모든 프로세스가 다른 프로세스가 사용 중인 자원을 기다리는 이런 상황을 deadlock이라고 한다.
•
해결 방법: 왼쪽과 오른쪽 젓가락을 한 번에 가져오는 것이 아니라 철학자들의 상태를 세마포어로 두고, 왼쪽과 오른쪽의 철학자가 먹고 있는지를 고려하고 두 개를 동시에 pickup하도록 한다.
◦
mutex는 상호 배제를 위한 세마포어이고, s는 자신이 pickup 가능한 상태인지를 알려주는 세마포어이며, state는 철학자들의 상태를 저장한다. 철학자들은 thinking, hungry, eating 중 하나의 상태를 가진다.
◦
철학자가 젓가락을 가져오려면 hungry 상태가 되어야 하고, pickup을 수행할 때는 자신의 상태를 hungry로 변경하고 test를 수행한다. 왼쪽, 오른쪽의 철학자가 먹고 있는 상태가 아니면 eating으로 상태를 바꾸고 내가 먹을 수 있는지에 대한 세마포어인 s[i]를 signal로 반환한다. 그러면 pickup에 있는 wait을 수행할 수 있게 된다.
◦
putdown을 수행할 때도 critical section을 보호하고 내 상태를 think로 바꾼 다음 왼쪽과 오른쪽에 test를 수행해서 가져가라고 알려준다. 중요한 점은 젓가락이 아닌 철학자들의 상태값을 세마포어로 잡는 것이다.
데드락
데드락의 정의
•
상황: 두 개 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다리며 무한히 대기하는 상태에 빠지는 것. 세마포어와 같은 동기화 툴을 사용하면서 발생하는 문제이다.
데드락 발생 조건
1.
Mutual Exclusion: 한번에 한 프로세스만 리소스에 접근할 수 있다.
2.
Hold and Wait: 한 프로세스가 한 개 이상의 리소스를 점유한 상태에서 다른 리소스를 추가로 점유하기 위해 기다린다.
3.
No Preemption: 프로세스가 리소스를 잡고 작업이 완료될 때까지 리소스를 놓지 않아야 한다. (강제로 다른 프로세스의 자원을 빼앗을 수 없다)
4.
Circular Wait: P0은 P1이 가지고 있는 리소스를 기다리고, P1은 P2... 다시 P0의 리소스를 기다리는 순환형으로 리소스를 기다려야 한다.
이 4가지 조건을 동시에 충족해야 deadlock이 발생한다.
데드락 처리 방법
1.
Deadlock Prevention: 데드락 발생 조건 중 하나 이상이 충족되지 않게 만들어서 데드락을 방지한다.
•
상호배제 부정: 여러 프로세스가 공유 자원을 사용할 수 있도록 한다.
•
점유 대기 부정: 프로세스 실행 전에 모든 자원을 할당한다.
•
비선점 부정: 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원을 반납한다.
•
순환 대기 부정: 자원에 고유 번호를 할당하고 순서대로 자원을 요구한다.
2.
Deadlock Avoidance: 운영체제가 데드락이 발생하는 상황을 런타임에서 모니터링해서 발생하는지를 계속 테스트한다. 발생하기 전에 커널이 처리하는 것. 모니터링 및 방지를 함께 하므로 운영체제의 오버헤드가 커지는 문제가 있다. 대표적인 Avoidance 알고리즘으로 은행원 알고리즘이 있다.
프로세스가 자원을 요구할 때 운영체제는 자원을 할당한 후에도 프로세스가 안정 상태로 남아있는지를 사전에 검사해서 안정 상태이면 자원을 할당해주고 아니면 다른 프로세스의 자원이 해제될 때까지 기다림으로써 교착 상태를 회피한다.
3.
Deadlock Detection and Recovery: 데드락이 발생했을 때 운영체제가 찾아내서 풀리도록 관리하는 방식이다. detection 과정에서 알고리즘을 수행해야 하기 때문에 운영체제 오버헤드가 커서 사용하지 않는다. recovery하는 방법은 교착 상태를 일으킨 프로세스를 종료하거나 프로세스를 일시 정지하고 교착 상태의 자원을 기다리고 있는 프로세스에게 할당하는 방법이 있다.
4.
Deadlock Ignorance: 데드락을 무시하는 방법으로, Ostrich Algorithm이라고도 한다. 사용하지 않는 방식으로, 문제가 발생하지 않기를 기대하는 접근이다.
Dining Philosopher
•
Deadlock의 대표적인 예시: 젓가락을 여러 명이 동시에 사용할 수 없으므로 mutual exclusion을 만족하고, 젓가락을 hold and wait하며, 잡은 이후 내려놓지 않으므로 No Preemption을 만족하고, 모든 철학자가 왼쪽을 동시에 들면 circular wait을 만족한다.
•
젓가락이 아닌 철학자들의 상태값을 세마포어로 잡아서 문제를 해결하는 방법은 하나를 잡고 다른 젓가락을 기다리는 것이 아니라 상태를 확인하고 두 개를 동시에 잡을 수 있도록 해서 hold and wait을 해결함으로써 deadlock을 해결한 예시이다.
