운영체제 2차 정리 - 데드락(Deadlock)

 호야의 블로그 

[OS] 운영체제 2차 정리

저번 포스트와 마찬가지로 운영체제 정리했던 자료를 공유하겠습니다. 오늘은 데드락에 관한 내용을 다루겠습니다. 기본 개념을 익히신 상태로 참고용으로 봐주시면 도움이 되겠습니다.

데드락(Deadlock)

※ 데드락

- 다중 프로그래밍 시스템에서 결코 일어나지 않을 사건을 기다리고 있는 프로세스를 Deadlock, 교착상태

- 두 개 이상의 작업이 중지되고 각각 사용할 수 있는 자원을 기다리는 경우, 시스템 측면에서 자원의 교우가 서로 뒤엉킨 상태

- 임의의 프로세스 집합에서 그 집합 내의 각각의 프로세스가 그 집합 내의 다른 프로세스에 의해서만 발생될 사건을 서로 기다리고 있는 상태

- Deadlock은 제한된 자원의 이용률과 효율성을 증가시키기 위한 병행 처리와 자원 공유에서 발생하는 문제

- 공유 불가능한 자원이라면 각 프로세스는 자원을 요청, 사용, 해제하는 순서로 이용한다.

- 프로세스의 Resource 요청, 해제, 사용은 OS에 의해서 이루어지는 것으로, 어떤 프로세스에 의해서 자원이 이용되는지 정보를 유지해야한다.

CS(임계구역): 여러 개의 프로세스가 공유하는 데이터 및 자원에 대해 어느 한 시점에서 하나의 프로세스만 자원 또는 데이터를 사용하도록 지정된 공유 공간. 하나의 프로세스만 접근 가능, 해당 프로세스는 자원을 반납한 후에만 다른 프로세스가 자원, 데이터를 사용가능. 임계 구역은 특정 프로세스가 독점 불가, 프로세스가 진입 요청하면 일정 시간 내 진입을 허락함.

상호 배제 기법(Mutual Exclusion): 공유 자원을 어느 시점에서 단지 한 개의 프로세스만이 사용하고 다른 프로세스가 공유자원에 접근 못하게 제어. 임계 구역을 유지하기 위함(데커 A)

동기화 기법(Synchronization): 두 개 이상의 프로세스를 한 시점에서는 동시에 처리할 수 없으므로 각 프로세스에 처리 순서를 결정하는 것으로 상호 배제의 한 형태.(세마포어 기법)

세마포어: 공유자원 접근하려면 S를 얻고, 끝나면 다른 프로세스가 사용할 수 있게 Wait로 S를 반환한다. 세마포어 변수는 공유자원의 개수를 나타내며 0, 1또는 0과 양의 값을 가짐. S는 키의 개수이다. signal은 키를 가져가는 행위다.

가. 세마포어(Semaphore)란?

1) 메모리 공간을 공유, 파일들을 공유 액세스하기 위한, 두 가지 정도의 목적을 위해 사용

2) 운영체계의 자원을 경쟁적으로 사용하는 다중프로세스에서 행동 조정 또는 동기화시키는 기술

3) 프로세스 간 데이터를 동기화 하고 보호하려는 목적

4) 한정된 수의 사용자만을 지원할 수 있는 공유 자원에 대한 접근을 통제하는데 유용

나. 세마포어의 작동원리

1) 세마포어는 운영체계 또는 커널의 한 지정된 저장장치 내 값이다.

2) 값의 변경은 P와 V라는 명령에 의해서 이루어진다.

3) 프로세스가 Critical section에 들어가면 P는 세마포의 값을 감소시킨다.

4) 프로세스가 작업수행 후 Critical section에서 나오면 V가 세마포 값을 증가시킨다.

5) 프로세스는 확인되는 값에 따라 자원을 활용, 또는 일정시간을 대기한다.

다. 뮤텍스(Mutex-상호배제)란?

1) 상호간에 비동기적으로 작동하는 쓰래드․프로세스간에 '통신'을 위한 한 방법이다.

2) 다수 쓰래드․프로세스가 공유 리소스에 대한 접근을 리소스를 "locking" 과 "unlocking"을 통해 조율.

3) Mutex가 설정되어 있는 경우 다른 쓰래드는 Mutex가 해제될 때까지 기다려야만 한다.

4) A쓰래드가 수행되고 B쓰래드가 수행되어야 할 때, A쓰래드가 작업하는 내용을 다른 쓰래드가 참조 변경할 수 없도록 Lock해 두었다가 작업이 끝나면 Unlock해 B쓰래드가 그 값을 읽어 사용할 수 있도록 함.

세마포어(Semaphore) : 공유된 자원의 데이터를 여러 프로세스가 접근하는 것을 막는 것

뮤텍스(Mutex) : 공유된 자원의 데이터를 여러 쓰레드가 접근하는 것을 막는 것

procedure P(S) -> 최초 S값은 1

while S=0 do wait -> S가 0이면 1이 될 때까지 wait

S := S-1 -> S를 0로 만들어 다른 프로세스가 들어오지 못하도록 함

end P

procedure V(S)         -> 현재 상태는 S가 0

S := S+1                    -> S를 1로 원위치 시켜 해제하는 과정

end V                        ->이제는 다른 프로세스가 들어 올수 있음

※ Deadlock Prevention

상호 배제 (Mutual exclusion) : 자원을 서로 동시에 사용하지 못하도록 하는 것이 상호 배제의 개념인데, Deadlock Prevetion을 위해서 Mutual Exclustion을 허용하지 않으면 공유를 가능하도록 만들어 준다는 것이다. 이 때, 공유 불가능한 자원 자체가 존재하게 되는 경우 이 자원을 공유 가능하도록 만들어 주는 것은 불가능하므로, 실행 불가하다.

점유 대기 (Hold and wait) : 자원을 hold하면서 다른 자원을 요구하면서 기다리는 것을 방지하려면 One shot Allocation의 방법이 있는데, 이는 프로세스가 자신에게 필요한 자원들을 한꺼번에 요구하고 동시에 허용될 때까지 프로세스를 보류시킴으로서 방지시키는 방법이다. 다른 방법으로 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용하는 방법이 있다. One Shot Allocation의 단점은 많은 자원을 동시에 요구하는 것은 제한적이며, 모든 자원을 얻어야 실행하므로 성능이 않좋아지며(Low Throughtput), 자원의 활용도가 떨어지고, Starvation의 문제가 발생할 수 있다.

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

순환 대기 (Circular wait) : Cycle이 형성되는 것을 막는 것으로 Deadlock으로 부터 보호한다. 모든 Resource Type에 번호를 부여하며, 프로세스가 자원을 요구할 때 오름차순으로만 요구를 한다. 예를 들어 2번 타입의 자원을 가지고 있으면 1번은 요구가 불가하면 3번은 요구가 가능하다.

※ Deadlock Avoidance

- Deadlock Prevention은 자원의 활용도가 떨어지고 시스템 성능이 안좋아지므로 Deadlock Avoidance를 사용 가능

- Deadlock이 될 수 있는 자원 할당 요규를 허락하지 않음으로써 Deadlock을 피할 수 있다.

- Deadlock Avoidance의 구현은 사전 정보(Priori information)이 필요하고 이것이 단점이다.

- 이 사전 정보에 대해서는 자원 할당 상태를 정의하며, 할당 가능하며 이용가능 한 자원의 수와, 프로세스가 최대로 요구하는 자원의 수로 구성된다.

- Deadlock Avoidance 알고리즘은 Resource-Allocation 상태를 동적으로 검사하여 Circular-wait 상태가 안 되게 함

- Safe 상태일 때가 Deadlock이 발생하지 않을 수 있는 상태이며, Unsafe state로 넘어가지 않도록 해야한다. Unsafe State는 Deadlock이 발생할 가능성이 있다.

- Process에 Safe Sequence가 존재하면 해당 프로세스는 Cycle이 형성되지 않는다.

※ Deadlock Detection

- Deadlock을 감지하는 것으로 Deadlock이 발생한 것에 대해서 회복을 시키는 정도로 한다.

- Deadlock Detection Algorithm을 사용한다.

- Detection Algorithm에서 사용하는 사전 정보는 Available, Allocation, Request가 있으며, Available은 할당 가능한 자원수, Allocation은 할당 된 자원 수, Request는 요구하는 자원 수를 나타낸다. Banker's Algorithm에서는 사용했던 Max가 없는데, 사전 예방하기 위한 것이 아닌 감지를 위한 것으로 최대 값 자체는 필요가 없기 때문이다.

 

후기 및 정리

어떻게 보면 되게 어려운 말들이 많은데 기본 개념을 갖추신 상태로 보신다면 많은 도움이 될 것입니다. 다음엔 메모리 관리에 관한 정리를 하겠습니다.

OS 7번째 글: 2018/10/26 - [IT/OS] - [OS] 운영체제 3차 정리 - Memory Management (2)

OS 6번째 글: 2018/10/26 - [IT/OS] - [OS] 운영체제 3차 정리 - Memory Management (1)

OS 5번째 글: 2018/10/26 - [IT/OS] - [OS] 운영체제 2차 정리 - 데드락(Deadlock)

OS 4번째 글: 2018/10/26 - [IT/OS] - [OS] 운영체제 1차 정리 - Scheduling

OS 3번째 글: 2018/10/24 - [IT/OS] - [OS] CPU 스케줄러

OS 2번째 글: 2018/10/24 - [IT/OS] - [OS] 진짜 간단히 정리한 프로세스 개념

OS 1번째 글: 2018/10/18 - [IT/OS] - [OS] 운영체제에 대해서

조금의 도움이 되셨다면 로그인 없이도 가능한 댓글과

왼쪽 아래 ♥공감 버튼을 꾹 눌러주세요!