Skip to content

운영체제 12회 #64

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
102092 merged 4 commits into from
Nov 3, 2021
Merged

운영체제 12회 #64

Changes from 1 commit
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
4a3dcee
Add deadlock
102092 Oct 10, 2021
50e37b8
Add extra
102092 Oct 11, 2021
c1c26fc
Add context-switch
102092 Oct 11, 2021
ffacebf
Clean up
102092 Oct 11, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Add extra
  • Loading branch information
@102092
102092 committed Oct 11, 2021
commit 50e37b891ffabd935da010586952858ddcb4836d
52 changes: 42 additions & 10 deletions operating-system/deadlock/han/README.md
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,10 +1,12 @@
# Deadlock이란?

- 교착 상태
- 프로세스나 스레드가, 어떤 특정 이벤트를 기다리고 있는데, 그 이벤트는 발생할 수 없는 상태에 놓여있음.
- 즉 쓸 데 없이, 기다리고 있는 상태를 의미하는듯.

- 둘 이상의 프로세스가 각자가 가지고 있는 자원을 보유한 채, 외부 조치 없는 한 영원히 그 상태에서 기다리고 있는 상황을 의미.

- 즉 어떤 자원을 가지고 있고 + 무슨 이유에서 인지, 외부 조치 없이는 무조건 기다리게 되어있는 상황을 의미



## 실제 시스템에서 교착 상태

Expand All @@ -24,34 +26,48 @@
## 교착 상태를 만족하기 위한 4가지 필요조건

- 아래 4가지 조건은 만족하게 되면, 교착 상태에 빠지게 된다.
- 아래 4가지 중에 하나만이라도 생기지 않도록 할 수 있다면, 교착 상태는 절대 발생하지 않는다.



### 상호 배제 조건

- mutual exclusion condition
> *mutual exclusion condition*

- 자원의 배타적인 사용이라 부르기도 함.

- 한번에 프로세스 하나만 해당 자원을 사용할 수 있음.
- 다른 프로세스가 위 자원을 사용하려 하면, 기다려야 한다.
- 한정된 자원에 대한 프로세스들의 사용 경쟁을 의미.



### 점유와 대기 조건

- hold and wait condition
- 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 위해 대기하는 프로세스가 존재.
> *hold and wait condition*

- 자원의 부분 할당이라 부르기도 함.
- 각각의 프로세스는 자신의실행 전체 과정에서 자원이 필요할 때 마다, 일부분을 확보, 실행해나가다가, 할당 불가능한 자원 때문에 교착 상태에 빠진다.

- 즉 프로세스는 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 위해 대기하는 프로세스가 존재함을 의미.



### 비 선점 조건

- nopremption condition
> *nopremption condition*

- 자원의 선점 불가능성이라 부르기도 함.

- 이미 할당된 자원을 강제로 뻈을수는 없음
- 즉 자원의 선점 불가능성을 고수하는 경우, 해당 조건 때문에 교착 상태를 일으키는 조건을 만족하게 되기도 함.



### 순환 대기 조건

- circular wait conditon
> *circular wait conditon*

- 대기 프로세스의 집합이 순한 형태로 자원을 대기


Expand All @@ -63,14 +79,26 @@
### 예방

- 위 4가지 발생 조건 중에, 하나라도 발생하지 않도록 하는 것.
- 예를 들면 상호 배제 조건 의 경우, **여러 프로세스** 들이 해당 자원을 사용할 수 있도록 해주는 것.
- 예를 들면..
- 상호 배제 조건 의 경우, **여러 프로세스** 들이 해당 자원을 사용할 수 있도록 해주는 것.
- 다만, 배타적으로 사용할 수 밖에 없는 자원도 있기에, 상호 배제 조건을 배제하는건 불가능할듯.
- 점유와 대기 조건의 경우, 자원이 부분할당 되지 않고, 필요한 자원을 모두 할당해 버리는 것.
- 자원의 낭비 발생. 심각하게..
- 비 선점 조건의 경우, 모든 자원이 선점 가능하도록 해주는 것.
- 즉 어떤 자원을 A 프로세스가 잡고 실행 중에 있는데, B 프로세스 에서 해당 자원을 요청할 경우, A프로세스는 자신이 보유하고 있는 자원을 내놔야함.
- A 프로세스 입장에서는.. 잘 하고 있는 도중 자신의 일의 결과를 모두 뺏길 수 있음 (중단 혹은 다시 시작 가능성 있으므로.)
- 자원 낭비
- 순환 대기 조건을 배제하는 경우, 자원의 요청 순서를 단 방향으로만 하도록 하는 것일듯.
- 그래도 자원 낭비, 무한 대기는 피해갈 수 없을듯. (모든 경우의 수를 따질 수 없으므로)



### 회피

> *Safe sequence, Safe state*

- 교착 상태를 피해가게 하는 방법

- 안전 상태?
- 프로세스들이 요청하는 모든 자원을, 교착 상태에 빠지지 않으면서 모두에게 자원을 할당해줄 수 있는 상태
- 안전 순서?
Expand All @@ -97,13 +125,17 @@
- 왜?
- 교착 상태는 안 만들어지는게 좋지만, 교착 상태가 발생할 수 없는 환경을 만들어 버린다면, 할당된 자원을 효율적으로 사용하는 것은 불가능한 일이 됨.
- 탐지
- RAG Resource Allocation Graph
- 자원 할당 그래프.
- 교착 상태 탐지를 위해, 현 시스템의 상황을 나타내는 그래프임.
- Allocation, Request, Available
- **순환 대기 조건**이 존재하는 지 탐지함 (시스템의 자원 상태를 확인함)
- 탐지 알고리즘을 사용..해서 오버헤드 존재

- 복구
- 순환 대기를 깨서, 교착 상태로 부터 회복하도록 함.
- 순환 대기에 포함된 프로세스의 제어권을 빼고 롤백.. 혹은 순환 대기가 깨질 때까지 프로세스 종료
- 순환 대기에 포함된 **프로세스의 제어권을 뺏고 롤백**.. 혹은 순환 대기가 깨질 때까지 **프로세스 종료**
- 전자 최소 비용의 프로세스를 고를 수 있지만, 이를 계산하는 데 복잡
- 후자 프로세스를 종료할 때 마다, 교착 상태가 해결 되었는지 확인해야함 (오버헤드)
- 어떤 프로세스를 깰까?
- 시스템마다 다른 기준으로 우선 순위
- MySQL의 경우, 트랜잭션의 크기가 가장 작은..
Expand Down