'상호배제'에 해당되는 글 1건

  1. 2010.01.02 [펌]교착 상태와 그 조건

2010.01.02 14:15 System


1) What is Deadlock?
교착 상태(膠着狀態, deadlock)란 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다. 예를 들어 하나의 사다리가 있고, 두 명의 사람이 각각 사다리의 위쪽과 아래쪽에 있다고 가정한다. 이때 아래에 있는 사람은 위로 올라 가려고 하고, 위에 있는 사람은 아래로 내려오려고 한다면, 두 사람은 서로 상대방이 사다리에서 비켜줄 때까지 하염없이 기다리고 있을 것이고 결과적으로 아무도 사다리를 내려오거나 올라가지 못하게 되듯이, 전산학에서 교착 상태란 다중 프로그래밍 환경에서 흔히 발생할 수 있는 문제이다. 이 문제를 해결하는 일반적인 방법은 아직 없는 상태이다.

출처:위키백과


2) Condition of Deadlock

4가지 조건을 모두 만족할시 교착상태가 발생한다.
순환대기는 점유대기 조건과 비선점 조건을 만족해야 성립하므로
완전히 독립적인 것은 아니다.


상호배제(Mutual exclusion) : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.

상호 배제(mutual exclusion, Mutex, 뮤텍스)는 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘으로, 임계 구역(critical section)으로 불리는 코드 영역에 의해 구현된다.

공유 불가능한 자원의 예로는 동시에 실행되고 있는 프로그램간의 통신에 사용되는 비트 단위의 깃발, 계수기, 등이다. 문제는 스레드가 언제라도 정지되거나 시작될 수 있다는 것이다.

예) 프로그램의 일부분이 여러 단계를 거치면서 데이터를 읽고 쓰고 있다고 하자. 그런데 예상치 못한 사건 등에 의해 다른 스레드가 동작하기 시작했다. 첫 번째의 스레드가 쓰고 있는 영역에서, 이 두 번째의 스레드가 또 다른 작업을 시작한다면, 해당 영역의 값은 부적절하며 예상할 수 없는 상태에 놓이게 된다. 게다가 두 번째의 스레드가 값을 덮어 써버리기라도 한다면, 복구 불가능한 상태로 되고 만다. 그러므로 공유 데이터를 접근하는 프로그램 내부의 이른바 임계 구역이라는 부분은 홀로 수행되도록 보호되어야 하며, 다른 스레드가 동일한 부분의 프로그램을 수행해서 동일한 공유 데이터를 접근하는 것을 막아야 한다.

단일 프로세서 시스템에서, 상호 배제를 구현하는 가장 단순한 방법은 인터럽트를 억제해서 공유 데이터가 손상되는 것을 막는 것이다. 성능에 최소한의 영향을 주기 위해 인터럽트가 발생하지 않을 명령어 집합의 수는 가능한 최소로 유지시키는 것이 좋다.


점유대기(Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.

비선점(No preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺐을 수 없다.

순환대기(Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.


'System' 카테고리의 다른 글

셸 코드 작성  (0) 2010.01.17
2008 JFF 8번 문제 풀이  (0) 2010.01.10
[펌]교착 상태와 그 조건  (0) 2010.01.02
What is CALLBACK function?  (0) 2010.01.01
[펌]함수 호출규약 [Calling Convention]  (0) 2010.01.01
Format String Bug  (0) 2009.12.22
Posted by LinkC
이전버튼 1 이전버튼

블로그 이미지
LinkC

태그목록

Tistory Cumulus Flash tag cloud by BLUEnLIVE requires Flash Player 9 or better.

공지사항

Yesterday35
Today62
Total331,082

달력

 « |  » 2019.8
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

최근에 받은 트랙백

글 보관함


. .