병행성 : 교착상태와 기아

교착상태는 데드락이라고도 한다.

무엇이냐면, 2개 이상의 프로세스들이 공유자원!! 에 대해서 경쟁하거나 통신, 즉 둘이 동시에 접근하려고 할 때 발생한다.

나도 사용하고, 너도 사용하려고 둘다 기다리면서 무한정 대기~~~> 로 이루어짐.

 

위의 예제의 경우 Pocess P가 A를 가지고 B를 요청하고 있다. Q는 B를 가지고 A를 요청하고 있다.

근데 B와 A모두 각각 P와 Q가 이미 가지고 있으므로 둘은 무한정 대기하게 된다. 방출을 위해서는 서로거를 가져와야만 하는데 서로 가지고만 있기 때문에.

해결을 위해서는 P가 A를 사용후 먼저 종료를 해줘야만 Q가 사용가능하므로 위의 예시처럼 변경하여 사용이 가능하다.

 

교착상태의 다른 예제를 살펴보도록 하겠다.

총 사용할 수 있는 메모리의 크기는 200이다.

근데 P1에서 80, P2에서 70을 사용하므로 이미 150을 사용했다.

이후 P1의 60이나 P2의 80 둘 중 어느것을 사용해도 150에 더하면 200을 초과하므로 교착상태가 발생한다.

디스크와 테이프를 사용하는 프로세스 2개가 있다.

P에서 D를 요청 후, 사용을 위해 락을 걸었다. Q에서는 T를 요청 후, 사용을 위해서 락을 걸었다. 이후 서로에 대해서 디스크와 테이프를 요청하고 있지만, 락을 걸고 각각 이미 사용 중이므로 교착상태가 발생한다.

---

교착 상태의 원리를 자원할당 그래프를 통해 표시할 수 있다.

 

화살표를 가리키며 Requests는 자원을 요청하는 것이고, 가리켜지면서 Held By는 할당된 것을 나타낸다.

C를 설명하면, P1은 Ra자원을 요청하지만 이미 P2에게 할당된 상태다. 반면 P2는 Rb를 요청했지만 얼탱이 없게 Rb는 P1에게 할당된 상태라 무한정 대기, 교착 상태가 발생하게 된다.

---

교착상태가 발생하기 위해서는 4가지 조건이 있다.

상호배제(mutual exclusion) : 특정 시간에 하나의 프로세스만 사용이 가능하다.

점유대기(hold and wait) : 하나의 자원을 확보한 상태에서 다른 자원을 기다리는 것이다.

비선점(no preemption) : 확보한 프로세스를 뺏기지 않는다.

환형대기(circular wait) : 프로세스간에 체인이 발생한다. 위에서 보인 환형대기처럼 요구하고, 요구되고를 반복하여 교착상태 발생.

 

그러면 어떻게 해결을 할까?

교착생태 해결을 위한 3가지 방법 ->>>

 

1. 교착상태 예방 : 교착상태가 발생하기 위한 4가지 조건중 하나를 없애는 것이다. 그런데 상호배제는 없앨 수 없다. 왜냐하면 상호배제를 없으면 경쟁상태가 발생하기 때문이다. 따라서 점유대기, 비선점, 환형대기 중에서 하나를 없앤다.

점유 대기 -> 프로세스가 필요한 모든 자원을 한꺼번에 요청하여 해결

비선점 -> 프로세스가 새로운 자원 요청에 실패하면 원래 가지고 있던거 반납 후에 다시 요청한다.

환형대기 -> 자원할당 순서를 다시 정의한다. 예를 들면 화살표를 한쪽 방향으로만 설계.

 

2. 교착상태 회피 : 자원을 할당할때 데드락이 발생하지 않도록 잘 할당하는 것.

현재 가용벡터 V에 1,1,2가 있다.

그런데 P1의 R1과 R3에 1씩 줘버려서 0, 1, 1이 남았다. 이렇게 남은 가용벡터로는 어떤 프로세스도 끝낼 수가 없기 때문에 할당을 잘못했다.

올바른 할당의 예시이다.

가용벡터 V에 0,1,1이 있다. 먼저 P2에게 0,0,1을 줘서 P2의 프로세스를 종료시키고 할당했던 6,1,2를 받아와서 6,2,3이 됐다.

이후 P1에 2,2,2를 줘서 4,0,1이 되었다가 할당했던 P1 3,2,2를 받아와서 7,2,3이 되었다.

P3도 동일한 방법이다.

이렇게 올바른 방법으로 자원을 할당하여 교착상태를 회피한다.

교착상태 예방에 비해 덜 제한적이고, 뒤에 나올 교착상태 발견에 비해 롤백이 필요가 없다.

 

3. 교착상태 발견 : 자원을 자유롭게 배정하는데, 데드락이 발생했는지 자주 체크한다.

발견 주기를 설정하는게 중요하다.

짧다면 -> 빠르게 발견이 가능하지만 부하가 크다.

반면 길면 -> 부하가 짧은 대신 발견이 늦어진다.

 

---

식사하는 철학자 문제

 

포크가 공유자원인데, 왼쪽포크와 오른쪽 포크를 사용하면 공유된 자원인 포크가 겹쳐서 못 먹을 수도 있다.

즉 데드락이 발생되서 기아상태에 빠질 수 있다.

문제를 해결하기 위해서는 방에 4명씩만 들어가게 하여 해결할 수 있다. 1~3명도 가능하지만 1명을 제외한 4명이 들어가는게 병행성이 제일 좋다.