운영체제 6주차] 병행제어(2)

##본 포스팅은 운영체제 강의 '이화여자대학교 운영체제 강의 - 반효경 교수님'를 보고 정리한 내용입니다.

 

동기화와 관련된 문제

1. Bounded-Buffer Problem (Producer-Consumeer Problem)
크기가 유한한 공유 버퍼를 다룰 때 생기는 문제이다.

출처 : 강의 캡쳐

생산자 프로세스는 데이터를 만들어 비어있는 버퍼에 넣는 역할을 하며,
소비자는 데이터를 꺼내 사용하는 역할을 한다.

생산자가 버퍼에 입장을 할 때는 lock을 걸어야하고,
소비자가 버퍼에 접근을 할 때는 lock을 걸어 데이터를 한 소비자만 접근할 수 있도록 해야한다.

<Synchronization variables>
- mutual exclusion : vinary semaphore
- resource count : 소비자와 생산자에게 표시하기 위한, 남은 buffter의 수 표시

2. Readers and Writers Problem
공유 데이터에 대해 읽고 쓰는 process(DB)에 write 중일 때 다른 process가 접근하면 안된다.
단순 lock을 걸고/풀고하는 식으로 해결할 수도 있겠지만, read는 동시에 할 수 있기에 보다 추가적인 설정이 필요하다.

<Shared data>
- DB 자체
- readcount : 현재 DB에 접근 중인 Reader의 수

<Synchronization variables>
- mutex : 공유 변수 readcount를 접근하는 코드의 mutual exclusion 보장을 위해 사용
- db : Reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

3. Dining-Philosophers Problem

철학자들은 생각하는 것과 배고파서 밥을 먹는 것을 계속 수행하는 것이다.
여기서 젓가락 5개가 공유데이터이고, 젓가락 모두 얻어야 식사를 할 수 있다.

문제는 모든 철학자가 배고파서 왼쪽 적가락만 집는다면?
젓가락은 밥을 다 먹은 뒤에 내려놓기 때문에, 이 상황에서 Deadlock이 걸리게 된다.

<해결 방안>
- 4명만 동시에 앉을 수 있게
- 젓가락 두 개 모두 잡을 수 있을 때만 젓가락을 잡을 수 있게
- 비대칭(짝수 철학자는 왼쪽 젓가락부터, 홀수는 오른쪽부터)

*세마포어 관점에서는 이해하기 힘든 코드이며, monitoring 관점에서는 이해 가능한 코드이다.

 

Semaphore의 문제를 해결할 Monitor

<Semaphore의 문제점>
- 코딩하기가 힘들다
- 정확성 입증이 어렵다
- 자발적 협력이 필요하다
- 한번의 실수가 모든 시스템에 치명적이다

이러한 프로세스 동기화를 더욱 쉽게 할 수 없을까?하고 나온 대안이 바로 Monitoring이다.

<Monitor>
고급언어 차원에서 보장하는 동기화 구조이다.

공유자원에 대한 접근은 오로지 monitor 안에 접근된 함수를 통해서만 접근할 수 있게 하며,
monitor 안에서 active하게 동작하는 것은 하나로 제한 한다.

즉, 공유 데이터에 대해서 lock을 할 필요가 없고,
프로그래머가 monitor 안에 있는 함수를 통해서만 접근을 하게 해주면 알아서 동기화가 된다.

이미 한 프로세스가 monitor 내부의 operation을 접근하여 사용 중이고,
다른 프로세스가 와서 접근을 요청한다면 monitor가 알아서 제어를 하여 queue에 줄 세워둔다.

그림에서 제일 위의 x, y는 condition variable이다.
만약 x라는 자원의 여분이 없으면, x.wait() 등과 같은 작업으로 x에 queue를 세워 기다리게 한다.
여분이 생길 경우, x.signal()을 통해 자원이 생겼음을 알리며 깨운다.

이 monitor를 사용하면, 위에서 얘기한 problem들을 해결할 수 있다.

 

Deadlock

Deadlock은 교착상태를 의미한다.

<Deadlock>
일련의 프로세스들이 서로가 가진 자원을 기다리면서 block된 상태

여기서 자원(Resource)은 하드웨어나 세마포어 같은 소프트웨어를 포함하는 개념이다.
이러한 데드락이 걸리는 이유는 '두 개의 자원이 필요한데, 누구도 양보하지 않아' 생긴다.

<Deadlock 발생의 4가지 조건>
1) Mutual exclusion (상호 배제)
매 순간 하나의 프로세스만이 자원을 사용할 수 있음

2) No preemption (비선점)
프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

3) Hold and wait (보유 대기)
자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

4) Circular wait (선형 대기)
자원을 기다리는 프로세스간에 사이클이 형성되어야 함 (위 그림처럼)

위 4가지 조건이 모두 만족해야만 deadlock이 발생한다.
다시 말해, 어느 하나를 깨야 deadlock을 빠져나올 수 있다.

위는 Resource-Allocation Graph를 의미하며,
그래프에 cycle이 없으면 deadlock이 아니다.

그래프에 cycle이 있으면,
- resource가 여러개 있으면 필수적으로 deadlock이 걸리지는 않음
- 하나면 반드시 생긴다.

왼쪽 그래프에서는 cycle이 두개 생기면서, deadlock이 생기는 예시이고
오른쪽 그래프에서는 cycle이 한개 생기지만, 자원이 하나이기에 deadlock이 발생하지는 않는 예시이다.

<Deadlock을 처리하는 방법>
1) Deadlock Prevention (미연에 방지)
자원 할당 시 Deadlock의 4가지 조건 중 하나를 무산시킨다.

• mutual exclusion : 공유해서는 안되는 자원의 경우 반드시 성립해야하기에 어쩔 수 없음
• hold and wait : 프로세스가 자원을 요청할 때 가지고 있는 어떤 자원도 던져버리게
• no preemption : CPU나 memory같은 빼앗을 수 있는 자원은 빼앗게
• circular wait : 모든 자원 유형에 할당 순서를 정해서 정해진 순서대로만 자원을 할당
  예) 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당받기 위해서는 우선 Ri를 release해야 함

하지만 위 방법은 비효율적이다.

2) Deadlock Avoidance
"자원 요청에 대한 부가정보"를 이용해서 자원 할당이 deadlock으로부터 안전한 경우에만 할당한다.

위에서 말한 그래프와 다르게, "점선"은 "언젠가 요청할 가능성이 있다"를 의미한다.

Deadlock Avoidance는 이 때의 점선까지 고려하여, deadlock의 가능성이 있는 자원을 주지 않는다.
즉, 위험성이 있는 자원을 요청했을 때, 그 데이터가 가용하더라도 주지않는 방법이다.