Resource
자원의 특징, 종류
Non Preemptable Resource
뺏을 수 없음, 한 번 내주면 자발적으로 Release 할 때까지 기다려야 함
Reusable Resource
오직 동시에 하나의 Process만 사용할 수 있고, 고갈 X
=> Lock, Unlock
Consumable Resource
생산하고 삭제할 수 있는 리소스
Reusable, Consumable Resource 모두 Deadlock 발생
Deadlock
정의
Process가 진행되지 못하고 교착 상태에 있는 것
ex:) S와 Q라는 Semaphore 변수를 사용하는 CS에 모두 접근해야지 끝나는 두 Process가 있을 때,
한쪽이 S를 선점한 후 Q를 선점하려고 하는 와중 Scheduling이 일어나,
다른 쪽에서 Q를 선점하면, 이후 S를 선점하려고 하지만, 다른 쪽이 사용하고 있어 접근하지 못함
그래서 무한히 돌다가 Process Switching이 발생하는데,
다른 한쪽은 Q를 접근할 수가 없어 서로 무한히 돌면서 두 Process가 영원히 끝나지 않게 됨
상황
Reusable Resource
각각의 Process가 한 자원을 점유한 채로 다른 자원을 요청할 때
Consumable Resource
Server와 Client간 한 쪽에 Send하면 한쪽이 Receive하는 등 순서가 맞아야 하는데, 안 맞을 때 ( 서로 Receive 하려고 한다던지 )
조건
Mutex
비선점
한번 자원을 내주면 그 프로세스가 자발적으로 Release할 때까지 기다려야 하는 것
점유 및 대기
Process가 최소 1개의 자원을 점유하면서, 다른 프로세스가 들고 있는 자원을 추가적으로 얻으려고 대기하는 것
순환 대기
사이클이 생겨서 각자가 서로의 자원을 필요로 하며 대기하는 것
1~3번까지는 Deadlock이 발생하기 위한 필요 조건이지만 충분 X, 무조건 발생 X
4번까지 발생할 때 비로소 필요 충분 조건 만족 => Deadlock 발생
4번이 발생하려면, 1~3번을 만족해야 함
Prevention
4가지 중 한 가지를 만족 못하도록 해야 함
점유 대기 해결
모든 필요한 Resource를 한번에 요청하고 모두 승인될 때까지 Blocking
단점
당장 필요할 가능성이 낮은 자원까지 요청하므로 비효율적
순환 대기 해결
자원에 대해서 순서를 매기고, 사용 시 순서대로 요청 하도록 함
단점
모든 자원에 대해서, 순서 매기기가 복잡, 어려움
자원 요청 순서가 Process마다 다를 수 있음
Concurrency 제약 생김
단점
- Utilization 저하
- Concurrency 저하
- 자원 사용 난이도 높음
Avoidence
Deadlock이 발생하지 않는 안전한 상황을 정의한 뒤, 요청이 올 때마다 상황을 보고서, 동적으로 회피할지 안 할지 결정
Resource-Allocation-Graph Algorithm
자원을 할당했을 때, Cycle이 생기면 자원을 할당하지 않음
단점
하나의 자원이 여러 개 존재할 때
=> Multiple Instance에 대해서는 고려하지 않음
Process Initial Denial
Multiple Instance의 경우를 고려
하나의 Process가 필요한 모든 자원들에 대해서, 각 자원의 갯수가 현재 실행 중인 모든 Process와 실행시키고자 하는 프로세스가 최대로 필요로 하는 것보다 많을 경우에 할당하고 아니면 아무것도 할당하지 않음
단점
항상 최대 양을 가정해야 하니 비효율적
Resource Allocation Denial (Banker’s Algorithm)
Resource Request 때마다 Safe State면 Alloc 아니면 기다리는 전략
System에서 어떤 Resource R이 할당 가능한 양이 K개라고 가정, 그 때 어떤 Process X의 최대 할당량이 A, 현재 할당받은 양이 B라고 할 때, 잠재적 요청량은 A-B이고, 이 잠재적 요청량이 K개보다 적을 때만 할당
당장의 요청량이 얼마든 잠재적 요청량을 기준으로 판단
생산자/소비자 문제
공유 자원 (버퍼)를 동시에 접근하기 때문에 상호 배제가 필요하고, 버퍼에는 상한과 하한이 있기 때문에 조건 동기가 필요함
소비자 입장
버퍼의 상한을 고민할 필요X
오직 하한을 신경쓰면서, 비어 있지 않으면 가져가고 아니면 기다려야 함
소비자를 깨워주는 것은 내용을 채우는 생산자
생산자 입장
만약 상한이 존재하는 버퍼라면, 버퍼가 다 채워져 있다면 생산자는 기다려야 함
생산자는 빈 슬롯이 생기기를 기다리고, 이 빈 슬롯을 만든 뒤 생산자를 깨워주는 것은 소비자
Reader/Writer 문제
읽기만 할 때는 공유 자원에 여럿이 접근해도 상관없음 Writer는 접근할 때 상호배제를 해주어야 하지만, Reader들은 Writer들이 못 들어오게만 하면 Mutex가 필요 X => 효율적으로 동작 가능
But Reader가 계속 들어오면 Writer들이 Starvation될 수 있음
Semantic of Signaling
Signal로 깨울 때 어떤 Thread를 깨울 것인지에 대해 두가지 방법이 존재
Mesa Semantics
시그널은 그냥 Ready 상태의 아무 Thread를 깨워주기만 할 뿐, 만족된 특정 조건이 충족되기를 기다리던 Thread가 다시 기다리던 작업을 바로 실행할 수 있도록 보장해주지는 않음
=> while문으로 계속해서 조건을 체크해야 함, 구현이 단순해 보편적
=> 생산자/소비자 원인
Hoare Semantics
시그널이 깨워 놓은 Thread가 바로 기다리던 작업을 실행할 수 있도록 보장해주는 Signal
구현 어려움
