지난시간
세마포: 동기화 문제를 추상화하여 프로그래머로 하여금 코딩으로 해결할 수 있게끔 하는 요소
P, V 연산을 통해 자원 관리.
Monitor
- Semaphore의 문제점
처음 접하는 사람 입장에선 코딩하기 힘들다.
정확성의 입증이 어렵다.
한번의 실수가 모든 시스템에 치명적 영향.
프로그래머의 실수가 치명적. P연산 V연산이 모두 알맞은 순서로 존재해야한다.
동기화를 조금 더 쉽게 하는 방법 -> Monitor가 등장
- 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level syncronization construct.
고급 언어 차원에서 제공되는 동기화 수단. 객체 지향 프로그래밍에서는 객체를 중심으로 연산들이 정의됨.
모니터는 모니터 내에 정의된 함수로만 공유 데이터에 접근할 수 있게하고, 공유데이터에 대해 lock이 필요없고, 프로그래머는 그냥 모니터 내에 있는 코드로 공유데이터 접근을 하게 하여 동기화를 진행.
모니터가 공유데이터에 동시접근하는 것을 제한. 다른 프로세스들은 큐에 줄세우고 진입을 대기시킴.
Monitor에는 condition variable이라는 세마포어 변수와 유사한 기능을 하는 변수가 있음.
자원의 여분이 있을때만 실행되고, 여분이 없다면, 프로세스를 block. -> 큐에 줄세워 잠들게함.
자원의 여분을 세는 세마포어같은 기능이 없어서, 훨씬 의미적으로 느끼는 것이 용이하다.
ex1. Bounded-Buffer Problem
monitor bounded_buffer
{
int buffer[N];
condition full, empty;
/* condition variable은 값을 가지지 않고 자신의 큐에 프로세스를 매달아서 sleep 시키거나 큐에서 프로세스를 깨우는 역할만 함 */
void produce(int x)
{
if there is no empty buffer
empty.wait(); // 큐에 줄서서 잠들어 대기.
add x to an empty buffer
full.signal(); // 혹시 대기하는 프로세스가 있다면 시그널로 깨움.
}
void consume(int *x)
{
if there is no full buffer
full.wait(); // 큐에 줄서서 잠들어 대기.
remove an item from buffer and store it to *x
empty.signal(); // 혹시 대기하는 프로세스가 있다면 시그널로 깨움.
}
}모니터 내에 활성화되는 프로세스는 하나.
세마포는 연산을 원자적으로 해주는 것만 지원. 프로그래머가 직접 동기화 문제를 해결해야함.
모니터는 동기화 문제를 기본적으로 책임져줌. 락을 걸거나 할 필요 없다. 자원이 없을 때 잠들어 대기하게 하는 컨디션 변수를 활용한다. -> 프로그래밍하기 수월하다.
ex2. Dining Philosophers Example
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(); /* wait here. wake up by test. */
}
void putdown(int i)
{
state[i] = thinking;
/* test left and right neighbors */
test((i + 4) % 5); /* if L is waiting */
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(); /* wake up Pi */
}
}
void init()
{
for (int i = 0; i < 5; i++)
state[i] = thinking;
}
}Each philosopher:
{
pickup(i); // enter monitor
eat();
putdown(i); // enter monitor
think();
} while (1)모니터 안에 젓가락을 잡는 코드를 구현(pickup). 젓가락을 잡을 수 있냐 없냐를 판단해주는 state 변수 공유데이터를 가짐.
컨디션 변수로 5명의 철학자에 대한 self 변수.
Deadlocks
: 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태.
교착상태를 나타냄. 빼도박도 할 수 없는 상태.
위 사진처럼 네 곳이 모두 막혀서 더 이상 진행이 불가능한 상태이다.
자원이 있는데 각각이 자원을 가지고 있으면서 다른 친구의 자원을 기다리는 중.
내가 가진 자원을 내려놓지 않고 다른 친구 자원을 기다리다보니, 모두가 내려놓지 못하고 기다리고만 있는 상황.
마치 철학자 문제에서 모두 왼쪽 젓가락을 들고 오른쪽 젓가락을 놓아주길 기다리고 있는 상태와 같다.
Deadlock 발생의 4가지 조건
-
Mutual exclusion
: 매 순간 하나의 프로세스만이 자원을 사용할 수 있음. -
No preemption
: 프로세스는 자원을 스스로 내어놓을 뿐, 강제로 빼앗기지 않음. -
Hold and wait
: 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음 -
Circular wait
: 자원을 기다리는 프로세스간에 사이클이 형성되어야 함.
4가지 중 하나라도 깨지면 데드락이 발생하지 않는다.
Resource-Allocation Graph (자원 할당 그래프)
R -> P : 자원이 해당 프로세스에게 피 점유되고 있다.
P -> R : 프로세스가 자원을 기다리고있다.
이 그래프에서 cycle이 없으면 데드락이 아니다.
cycle이 있으면,
1. 공유자원의 갯수가 하나인 경우, 데드락 발생.
2. 공유 자원의 갯수가 여러개인 경우, 데드락이 발생할 가능성이 존재. -> 자원들이 모두 사이클에 기여하고 있어야 데드락.
데드락 처리 방법
Deadlock Prevention
: 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
-
Mutual Exclusion
: 공유해서는 안되는 자원의 경우 반드시 성립해야함.
뮤텍스를 풀어버리는 것은 공유자원으로서 사용하기 위험해져서 해당 요소는 항상 만족시킬 수 밖에 없다. -
No preemption
: process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨.
모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory) -
Hold and Wait
: 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청. -
Circular wait
: 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
예를 들어 순서가 3인 자원 Ri를 보유중인 프로세스가 순서가 1인 자원 Rj를 할당받기 위해서는 우선 Ri를 release해야한다.
-> Utilization 저하, throughput 감소, starvation문제.
데드락의 처리 자체가 비효율적이다. 데드락이 아예 발생하게 하지 않지만, 효율이 많이 떨어짐.
Deadlock Avoidance
: 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
: 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당.
가장 단순하고 일반적인 모델은 프로세스들이 필요로하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임.
점선은 미래에 해당 자원을 요청할 수 있음을 나타내는데, 이를 통해 점선으로라도, 사이클이 형성되어 데드락이 발생할 수 있다면 자원을 할당하지 않는 것이 Deadlock Avoidance.
다음시간
데드락에 대해 더 자세히 알아보도록 하자.
-
Deadlock Detection and recovery
: Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover -
Deadlock Ignorance
: Deadlock을 시스템이 책임지지 않음.
: UNIX를 포함한 대부분의 OS가 채택.
