TIL 정리_98(Deadlock&Memory)

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323

운영체제 강의를 듣고 정리한 내용입니다

 

 

Deadlock의 처리방법

Deadlock Prevention

• 자원 할당 시 deadlock의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 것이다.

Deadlock Avoidance

• 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당한다.
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원을 할당한다

Deadlock Detection and recovery

• deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover 한다

Deadlock Ignorance

• Deadlock을 시스템이 책임지지 않는다

---

Deadlock Detection and recovery

Resource type(자원)당 인스턴스가 하나인 경우

- 자원 할당 그래프에서의 cycle이 곧 deadlock을 의미한다

 

Resource type(자원)당 인스턴스가 여러 개인 경우

- Banker’s algorithm과 유사한 방법을 활용한다

 

Wait-for graph 알고리즘

Resource type당 인스턴스가 하나인 경우에 활용한다

 

Wait-for graph

• 자원 할당 그래프의 변형이다
• 프로세스만으로 node가 구성된다 
• Pj가 가지고있는 자원을 Pk가 기다리는 경우 Pk -> Pi로 이동
• 자원의 최대 사용량을 미리 알릴 필요가 없다

-> 그래프에 점선이 없다

 

Wait-for graph 사이클이 존재하는지를 주기적으로 조사한다

시간 복잡도는 O(n^2)이다

 

Deadlock 확인법 :

• 가용자원이 있는지를 확인한다
• 요청하지 않은 프로세스들 중 처리가능한 것이 있는지를 확인

=> 발견시 RECOVERY를 해야한다

 

Recovery

Processtermination

• 데드락에 연관된 모든 프로세스를 없앤다
• 데드락에 연관된 프로세스를 하나씩 없앤다(권장)

 

Resource Preemption

- 비용을 최소화할 victim을 선정한다

- safe state로 되돌리고, 프로세스를 다시 시작한다

단점 

Starvation 문제가 있다 

- 동일한 프로세스가 계속해서 victim으로 선정되는 경우

- cost factor에 되돌리는 횟수도 같이 고려해야 한다

 

Deadlock Ignorance

• deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있다
• 만약 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처한다
• UNIX, Windows 등 대부분의 범용 OS가 이 방식을 채택한다

 

---

Memory Management

Logical vs Physical Address

Logical address (= virtual address) //논리적인 주소

• 프로세스마다 독립적으로 가지는 주소 공간을 말한다
• 각 프로세스마다 0번지부터 시작한다
• CPU가 보는 주소는 logical address이다

 

Physical address //물리적인 주소

• 메모리에 실제 올라가는 위치를 의미한다

 

**주소 바인딩 : 주소를 결정하는 것을 의미한다

Symbolic Address -> Logical Address -> Physical Address

                                                  ㄴ이 시점이 언제인가?

 

Symbolic Address

프로그래머는 프로그래밍 할 때 숫자 주소를 사용하지 않고 심볼로 된 주소를 이용한다

->이러한 주소 == 소스코드를 의미한다

 

 

주소 바인딩 (Address Binding)

Compile time binding

• 물리적 메모리 주소가 컴파일 시 알려진다
• 시작 위치 변경 시 재컴파일 한다
• 컴파일러는 절대 코드(absolute code)를 생성한다

-> 물리적인 메모리에 컴파일 주소를 올릴때는 이미 정해진 논리적인 메모리 주소를 올려야한다

 

Load time binding

• Loader의 책임하에 물리적 메모리 주소를 부여한다
• 컴파일러가 재배치 가능한 코드(relocatable code)를 생성한 경우 가능하다

->  프로그램이 시작되어 메모리에 올라갈 때 논리적인 주소가 결정된다

 

Execution time binding (= Runtime Binding)

• 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있다
• CPU가 주소를 참조할 때마다 binding을 점검한다 (address mapping table)
• 하드웨어적인 지원이 필요하다

-> 실행시에 주소가 결정되는 것은 load time과 동일하나

경우에 따라서 실행 도중 주소가 바뀔 수 있다는 차이점이 있다

 

**우리가 사용하는 시스템은 rumtime binding을 제공한다