Classical problem of Synchronization

• Bounded-Buffer problem(Producer-Cusumer Problem):제한된 버퍼에 데이터를 채우고/가져가는 문제

• Readers and Writers problem: 데이터 공유 문제

• Dining-Philosophers problem: 한 자원을 가지고 다른 자원을 요청하는 문제

Deadlocks

프로세스들이 일어나지 않을 사건을 무한정 기다리는 상태를 말한다.

• Deadlock: 프로세스, 쓰레드가 서로 엉켜 결코 일어나지 않을 상태를 wait하는 상태

• Starvation: 프로세스가 running 할 수 있지만 우선 순위가 계속 밀려 자원을 무한정 기다리게 되는 상태

• Livelock: running은 하지만 진도가 나가지 않는 상태

Deadlock characterization

Necessary conditions for Deadlock

• Mutual exclusion: 한 프로세스 독점적으로 자원을 사용한다.

• Hold and wait: 적어도 하나의 자원을 보유하고 현재 다른 프로세스에 할당된 자원을 얻기 위해 기다리는 프로세스가 있어야한다.

• No preemption: 자원을 Preemption(선점)할 수 없으며, 해당 자원을 hold하고 있는 프로세스가 종료되어야 자원이 해제될 수 있다.

• Circular wait: 자원 할당 그래프에서 사이클이 존재한다. 이 때 하나의 자원 타입의 인스턴스가 1개 존재하면 Deadlock이며, 여러 개의 instance가 있으면 Deadlock의 가능성이 있는 것이다. 즉 Cycle이 존재하면 Deadlock이 있을 수도 있다는 것이다.

Methods for handling deadlocks

Deadlock prevention

• Mutual exclustion - 자원을 서로 동시에 사용하지 못하게 한다.

• Hold and wait - 프로세스가 자신에게 피리요한 자원들을 한꺼번에 요구하고 동시에 허용될 때까지 프로세스를 보류시킴으로서 방지하는 방법을 One shot Allocation이라 한다. 이 방법을 사용하면 Low throughput, starvation 야기 할 수 있다.

• No preemption - 프로세스가 필요한 자원을 가진 프로세스로부터 그것을 잠시 빼앗아 올 수 있다. 빼앗긴 프로세스의 실행이 지연될 수 있는 문제가 있다.

• Circular wiat - Cycle이 형성되는 것을 막는 것으로 Deadlock을 방지한다. Resource type에 번호를 부여하고, 프로세스가 자원을 요구할 때 오름차순으로만 요구한다.

Deadlock avoidance

• 시스템이 safe state - no deadlock

• 시스템이 unsafe state - Deadlock 가능성 있음 혹은 Deadlock

• Avoidance는 unsafe state에 절대 시스템이 들어가지 않게 하는 것이다.