TIL 정리_96(Monitor, Deadlock)

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

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

 

 

Monitor

동시 수행중인 프로세스 사이에서 추상 데이터 타입의 안전한 공유를 보장하기 위한

high-level synchronization construct이다

---

Monitor를 이용한 해결코드

• Monitor에서는 lock을 걸거나 풀 필요가 없다

 

Bounded-Buffer Problem (Monitor 이용)

monitor bounded_buffer {
int buffer[N];
condition full, empty;
//condition 변수는 값을 가지지 않고 자신의 큐에 프로세스를 매달아서 sleep 시키거나큐에서 프로세스를 깨우는 역할만 한다.

void produce(int x) {
empty.wait() //비어있는 버퍼가 없는 경우 기다린다
...
// x를 비어있는 버퍼에 추가한다
...
full.signal();
}

void consume(int * x) {
full.wait(); //값이 있는 버퍼가 없는 경우 기다린다
empty.signal();
}

 

 

Process Synchronization 프로세스 동기화

== Concurrency control 병행제어와 같은 의미이다

 

P 연산 : 자원을 획득

V 연산 : 자원을 반납

 

Dining Philoshphers Example (Monitor 이용)

monitor dining_philosopher {
enum {thinking, hungry, eating} state[5];
condition self[5];

void pickup(int I) {
state[i] = hungry;
test(i);
if(state[i] != eating)
self[i].wait(); //기다린다
}

void putdown(int I) {
state[i] = thinking;
//왼쪽과 오른쪽에 위치한 철학자를 테스트한다
test((i+4) % 5); //L이 기다리는 경우
test((i+1) % 5);

void test(int I) {
if(state[(i+4)%5] != eating) && (state[i] == hungry) && (state[(i+1) % 5] != eating)) {
state[i] = eating;
self[i].signal(); //Pi를 깨운다
}
}

void init() {
for(int I = 0; i<5; I++)
state[i] = thinking;
}

 

Each Philosopher

do {

pickup(i);

eat();

putdown(i);

think();

} while(1);

 

 

**Semaphore와 Monitor의 차이점

semaphore에서는 lock을 걸지만, monitor에서는 lock을 걸지 않는다

잠들게 할 때 monitor는 if문으로 조건을 건다

 

---

Deadlock

- 교착상태

 

예시) 4거리에서 서로 이동하려는 차량들이 양보를 하지 않아 막혀버리는 상황

->일부 자원을 가지고 있으면서 상대방의 자원을 요구하는 상황이 맞물려 교착상태에 빠진다

 

Deadlock 

일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태를 말한다

 

Resource

하드웨어, 소프트웨어 등을 포함하는 개념이다

예) I/O device, CPU cycle, memory space, semaphore 등이 있다

 

프로세스가 자원을 사용하는 절차

request, allocate, use, release

 

Deadlock 예시 1

• 시스템에 2개의 tape drive가 있다
• 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다

 

Deadlock 예시 2

Binary semaphores A and B

P0 P1

P(A); P(B);

P(B); P(A);

 

 

Deadlock이 발생하는 4가지 조건

Mutual excpusion (상호 배제)

매 순간 하나의 프로세스만이 자원을 사용할 수 있다

-> 자원을 독점적으로 사용할 때 발생한다

 

No preemption (비 선점)

프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다

-> 자원을 빼앗기지 않기 때문에 발생한다

 

Hold and wait (보유 대기)

자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는다

-> 자원을 내어놓지 않고 추가적으로 요청하기 때문에 발생한다

 

Circular wait (순환 대기)

자원을 기다리는 프로세스간에 사이클이 형성되어야 한다

프로세스 P0, P1, ...., Pn이 있을 때

P0은 P1이 가진 자원을 기다리고,

P1은 P2가 가진 자원,

Pn-1은 Pn이 가진 자원을,

Pn은 P0가 가진 자원을 기다린다.

-> 서로가 자원을 내어놓지 않고 기다리기만 하여 사이클이 형성되고, deadlock이 발생한다

 

 

데드락이 발생했는지를 알아보기 위한 방법

- Resource-Allocation Graph(자원 할당 그래프)

Vertex

Process P = { P1, P2, ..., Pn }

Resource R = { R1, R2, ..., Rm }

 

Edge

request edge Pi -> Rj

assignment edge Rj -> Pi

 

-> 그래프에 cycle(순환)이 없으면 Dealock이 아니다

그래프에 cycle이 있는 경우, 

자원의 인스턴스가 하나만 존재할 때 Deadlock이 발생한다

자원의 인스턴스가 여러 개 존재하는 경우 Deadlock일수도 있고, 아닐수도 있다