deadlock

Lock의 정의
http://en.wikipedia.org/wiki/Lock_(computer_science)

----------------------------

Operating SystemsChapter 3: I/O
http://isel.cs.pusan.ac.kr/~lik/OS2002SpringChapter3.ppt

데드락 발생조건 네가지
Deadlock 은 다음의 모든 조건이 만족되어야 일어난다.
Mutual Exclusion : 하나의 Process 에만 Resource가 할당
Hold and Wait Condition :
프로세스는 하나 이상의 Resource를 가지고 있으며
다른 Resource의 할당을 기다리고 있음
No Preemption Condition
Circular Wait:Wait For Graph에 Cyclye이 존재

해결방법
1. Optimistic Approach (Ostrich Algorithm)
Deadlock 무시 :
Deadlock이 발생하는 가능성이 상당히 작으면
Deadlock이 발생하는 경우를 무시
Deadlock을 처리하기 위한 부하를 최소화
일정한 Process가 특정 Timeout 동안에 처리되지 않으면
Ctrl-Alt-Del !!

2. Deadlock Detection and Recovery
Deadlock이 발생하는지를 검사
Wait-For-Graph를 검사하여 Cycle이 존재여부 검사
발생하면, 하나의 Process를 Kill
Wait-For-Graph의 Cycle이 존재하는지를 조사
Resource가 Allocate될 때 마다 Wait-For-Graph를 Update
Process가 Resource를 요청할 때 Wait-For-Graph를 조사
Overhead가 발생 : 주기적으로 조사


3. Deadlock Prevention
Deadlock 조건 중 하나를 공략

Deadlock의 조건 중 하나를 파괴

3.1 Mutual Exclusion
Queuing (Spooling) : Spooling Daemon
Spooling이 곤란한 경우 존재
Spooling 자체가 Deadlock 을 유발
바람직한 방법이 아님
3.2 Hold and Wait
필요한 Resource를 한꺼번에 요청
만일 한가지라도 사용 불가능하면 Wait
두 가지 문제
사용할 Resource를 미리 아는 것은 어려움
성능의 심각한 저하

3.3 Preemption Condition
실행 중에 사용중인 Resource를 회수
Non-Preemptive Resource의 경우 적용 불가능

3.4 WFG의 Cycle 모든 Resource를 Ordering
현재 M 번째 Resource 를 사용 중이면, N>M인 Resource 만 사용하도록 허락
N<M인 Resource는 사용 불가
Resource를 Ordering하는 것이 매우 어려움


4. Deadlock Avoidance
Banker’s Algorithm

----------------------------------
CS 140: OS hacking Lecture 5 : Deadlocks
http://www.stanford.edu/class/cs140/lectures/fall0506/07lec5notes.pdf#search=%22fine%20grain%20lock%20rule%22


----------------------------------

Automatic Detection of Potential Deadlock
http://www.ddj.com/184404351

데드락 탐지(deadlock detection) c++ 코드 제공
-----------------------------------

Advanced Synchronization in Java Threads, Part 2
http://www.onjava.com/pub/a/onjava/2004/10/20/threads2.html?page=1

락 금지의 가장 쉬운 방법인 lock을 same order로 하는 것 알려줌
Deadlock detection 자바 코드 제공


Avoid synchronization deadlocks
http://www.javaworld.com/javaworld/jw-10-2001/jw-1012-deadlock.html

역시 Lock order얘기임.

-----------------------------------

Locks, Blocks, and Deadlocks
Chapter 4. Concurrency
http://www.sleepycat.com/docs/gsg_txn/JAVA/blocking_deadlocks.html


FreeBSD: Lock Order Reversal Documentation
Witness 프로그램을 이용하여 Lock 순서 역전(Lock order reversal)으로
deadlock 발생 가능한 부분을 static lock order 분석과 runtmie lock order
분석으로 찾아내는 이야기.
http://kerneltrap.org/node/3620
http://sources.zabbadoz.net/freebsd/lor.html

------------------------------------------------
C340 Concurrency: Databases Concurrency Control
2 Phase Locking, Hierarchical Locknig 소개
http://www.cs.ucl.ac.uk/staff/W.Emmerich/lectures/C340-99-00/conc24.pdf


A Deadlock-Free Multi-Granular, Hierarchical Locking Scheme for Real-time Collaborative Editing
http://www.ntu.edu.sg/home/ashfshen/iwce07/papers/iwces2005_hierarchical_locking.pdf

--------------------------------------------

Hardware/Software Deadlock Avoidance for
Multiprocessor Multiresource System-on-a-Chip
Deadlock Avoidance(회피)알고리즘 Banker 알고리즘을 하드웨어로 구현
http://www.ece.iupui.edu/~johnlee/paper/JLeeThesis0525DoubleSided.pdf#search=%22deadlock%20avoidance%22