[OS] Synchronization & Deadlock

 

Synchronization 필요한 이유

- Process는 병행하게, 또는 병렬로 실행될 수 있음

- 공유 데이터에 동시 접근하게 되면 data inconsistency 발생할 수 있음

- Cooperating process들의 질서있는 실행을 위한 메커니즘이 필요함

 

Synchronization 관련 용어

- 동기화: 한정적인 자원에 여러 thread가 동시 접근하면 문제 발생하므로 thread에게 처리 권한을 주거나 순서 조정

- Race Condition 경쟁상황: process 간 자원을 사용하려고 경쟁하는 것

- Critical Section 임계구역:

   공유 자원에 접근하는 process 내부의 코드 영역

   한 process가 이 영역을 수행 중일 때 다른 process가 자신의 영역 수행하면 문제 발생

- Mutual Exclusion 상호배제: 한 process가 공유 자원 접근하는 코드 수행 중이면 다른 process는 수행할 수 없다는 조건

 

생산자-소비자 문제 예시

- 버퍼에 새 항목 추가할 때마다 counter 값 증가시키고, 버퍼에서 한 항목 꺼낼 때마다 counter 값 감소시키기

/* Producer */
while (true) {
    /* produce an item in next produced */
    while (counter == BUFFER_SIZE); // do nothing
    buffer[in] = next produced;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}

/* Consumer */
while (true) {
    while (counter == 0); // do nothing
    next_consumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
    /* consume the item in next consumed */
}

- 위 생산자, 소비자 코드는 개별적으로는 올바를지라도, 병행적으로 수행하면 문제가 발생

- counter 값이 5라고 했을 때, counter++; counter--; 병행 실행되고 나면 값이 5가 되어야 하나 4, 5, 6 중 하나가 될 수 있음

- 둘을 병행 실행하는 것은 저수준 문장들을 임의의 순서로 뒤섞어 실행하는 것과 같음

- 두 process가 동시에 변수 counter를 조작하기 때문에 특정 순서에 의존하는 race condition이 발생

- 한 순간에 하나의 process만이 조작하도록 보장해야 함

 

Critical Section Problem 임계구역 문제

- 한 process가 자신의 임계구역에서 수행하는 동안 다른 process는 그들의 임계구역에 들어갈 수 없음

do {
    entry section
        critical section
    exit section
        remainder section
} while (true);

do {
    while (turn == j);
        critical section
    turn = j;
        remainder section
} while (true);

- 임계구역 들어가기 전에 entry section에서 허가 요청받아야 함

- 임계구역 문제에 대한 해결안이 만족해야 하는 3가지 조건:

1) Mutual Exclusion 상호배제

Process Pi가 자신의 임계구역에서 실행된다면, 다른 process는 임계구역에서 실행될 수 없음

2) Progress 진행

임계구역에서 실행되고 있는 process가 없고 진입하고자 하는 process들이 존재한다면, 이중 선택하는 시간은 무한정 연기될 수 없음

3) Bounded Waiting 한정된 대기

process가 자신의 임계구역에 진입하려는 요청을 한 후 그 요청이 허용될 때까지 다른 process들이 허용되는 횟수에 제한이 있어야 함

→ SW적인 방법 있으나 복잡해서 CPU가 지원하는 동기화 명령어를 사용함

 

Peterson's Solution

- 임계구역, 나머지 구역 번갈아가며 실행하는 2개의 프로세스로 한정 (Pi, Pj = P(1-i))

- 두 개의 데이터 항목을 공유하며 해결

- turn == i : Pi가 임계구역에서 실행될 수 있음

- flag[i] == true : Pi가 임계구역으로 진입할 준비가 되었음을 의미

int turn; // 임계구역으로 진입할 순번
boolean flag[2]; // 프로세스가 임계구역으로 진입할 준비가 되었음을 표시

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);
        critical section
    flag[i] = false;
        remainder section
} while (true);

- load, store 기계어는 interrupt가 발생할 수 없다고 가정 (atmoic)

1) Pi 임계구역으로 진입하기 위해 먼저 flag[i]를 true로 만들고, turn을 j로 지정함 (Pj에게 우선 양보하는 것)

    이렇게 하면 Pj가 임계구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장할 수 있음

    두 process가 동시에 진입하길 원하면 turn은 거의 동시에 i, j로 지정될 것, 궁극적인 값에 따라 결정됨

2) flag[j] && turn == j를 확인, 충족하지 않으면 임계구역 진입

3) 임계구역에서 나올 때 flag[i]를 false로 만듦

- 예를 들어, Pj가 임계구역에 있을 동안 flag[j] == true, turn ==j 상태 변하지 않음 (Mutual Exclusion)

- Pi while 문 수행하는 동안 (공회전) turn = i 값을 바꾸지 않기 때문에 자신도 한 번은 진입할 수 있게 됨 (Process)

 

Synchronization Hardware

- Peterson's solution 같은 SW 기반 해결책은 올바르게 동작하지 않을 수 있음

- 단일 프로세서에서는 단순히 interrupt를 금지하면 되지만, 멀티 프로세서에서는 너무 비효율적임

- 많은 시스템이 임계구역 코드를 보완하기 위한 HW 지원을 제공함

- Non-interruptible(atomic) 하드웨어 명령어를 제공함 (한 워드 내용 검사/변경하거나, 두 워드 내용 원자적으로 교환)

- Locking이 핵심

do {
    acquire lock
        critcial section
    release lock
        remainder section
} while (true);

 

Mutex Locks

- 위에서 설명한 하드웨어 기반 해결책은 복잡해서 사용 어려움, 대신 소프트웨어 도구를 개발 → Mutex 락

do {
    acquire lock
        critcial section
    release lock
        remainder section
} while (true);

- 임계구역을 보호하고 race condition을 방지하기 위해 mutex 락 사용

- Process는 임계구역에 들어가기 전 반드시 락을 획득해야 하고(acquire), 빠져나올 때 락을 반환해야 함(release)

- available 변수의 값은 락의 가용 여부를 표시함

acquire() {
    while (!available); // busy wait
    available = false;
}

release() {
    available = true;
}

- acquire, release 함수 호출은 atmoic 하게 수행되어야 함, 따라서 종종 하드웨어 기법을 사용하여 구현됨

- Busy wait를 해야 함

   Process가 임계구역에 있는 동안 진입 원하는 다른 process들은 acquire 함수를 호출하는 반복문 계속 실행해야 함

   락이 가용해지기를 기다리며 process가 계속 회전하고 있기 때문에 spinlock이라고 함

- 락을 기다리는 동안 context switching 하지 않으므로 락 소유 예상 시간이 짧은 프로그램에서는 유용함

 

Semaphores

- Mutex는 동기화 도구의 가장 간단한 형태임

- Mutex와 유사하게 동작하지만 processe들이 자신의 행동을 더 정교하게 동기화할 수 있는 방법 → Semaphores

- Semaphore S = 정수 변수. 초기화를 제외하고는 atomic 연산인 wait(), signal()로만 접근 가능

/* 검사 */
wait(S) {
    while (S <= 0); // busy wait
    S--;
}

/* 증가 */
signal(S) {
    S++;
}

- wait(), signal() 연산 시 세마포의 정수 값을 변경하는 연산은 반드시 분리되지 않고 수행되어야 함

- 즉, 한 스레드가 세마포 값 변경하면 다른 어떤 스레드도 동시에 동일한 세마포 값을 변경할 수 없음

- wait(S)의 경우, S의 값을 검사하는 작업 (S <= 0) 과 이에 따라 실행될 수 있는 변경 작업 (S--) 또한 interrupt 되지 않고 실행되어야 함

 

- Count semaphore의 값은 제한 없는 영역을 가지고, 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용됨

- 세마포는 가용한 자원 개수로 초기화 됨

- 각 자원을 사용하려는 process는 세마포에 wait() 연산을 수행하며, 이때 세마포 값이 감소됨

- Process가 자원 방출할 때는 signal() 연산을 수행하며, 이때 세마포 값이 증가됨

- 세마포 값이 0이면 모든 자원이 사용 중임을 의미, 세마포 값이 0보다 커질 때까지 자원을 이용하려는 process가 봉쇄됨

 

- 같은 세마포에 대해, 두 process가 동시에 wait(), signal() 연산을 실행할 수 없도록 반드시 보장해야 함

- 이는 임계구역 문제에 해당하는데, 이를 어느 정도 해결하기 위해 wait(), signal() 연산을 임계구역에서 실행하도록 함

- 임계구역은 거의 항상 비어있으며, busy wait는 드물게 발생하며, 발생하더라도 시간이 짧음

- 하지만 임계구역에서 많은 시간을 소요하는 프로그램에게는 좋지 않은 방법임

 

Deadlock and Starvation

P0		P1
wait(S);	wait(Q);
wait(Q);	wait(S);
.			.
.			.
.			.
signal(S);	signal(Q);
signal(Q);	signal(S);

- P0이 wait(Q) 실행할 때, P1이 signal(Q) 실행할 때까지 기다려야 함

- P1이 wait(S) 실행할 때, P0이 signal(S) 실행할 때까지 기다려야 함

→ Deadlock(교착 상태)

- Starvation(기아): process들이 세마포에서 무한정 대기하는 것 (LIFO 할 경우 발생할 수 있음)

- Priority Inversion(우선순위 역전): 우선순위 낮은 process가 우선순위 높은 process에 필요한 lock을 계속 hold 하는 경우 문제 발생

→ Priority-inheritance protocol(우선순위 상속 프로토콜)로 해결

- 우선순위 높은 process가 필요로 하는 자원 접근하는 process들은 자원 사용 끝날 때까지 더 높은 우선순위 상속받고, 끝나면 원래 우선순위로 돌아감

 

System Model

- 시스템은 자원들로 구성되어 있으며, 자원들은 여러 유형으로 분할되고, 각각 동등한 다수의 인스턴스로 구성됨

- Resource types R1, R2, ..., Rm (ex. CPU cycle, memory space, I/O device) 

- 각 resource type Ri 는 Wi instance를 가짐

- Process는 Request, Use, Release 순서로만 resource를 이용할 수 있음

 

Deadlock 특징

- Deadlock은 한 시스템에 다음 4가지 조건이 동시에 성립될 때 발생할 수 있음

1) Mutual Exclusion 상호배제

하나의 process가 자원을 사용하고 있을 때, 다른 process가 그 자원을 요청하면 방출될 때까지 반드시 지연되어야 함

2) Hold-and-wait 점유하며 대기

Process는 최소한 하나의 자원을 점유한 채, 다른 process에 의해 점유된 다른 자원을 추가로 얻기 위해 반드시 대기해야 함

3) No preemption 비선점

자원을 선점할 수 없어야 함. 즉, 자원이 강제로 방출될 수 없음

4) Circular wait 순환대기

대기하고 있는 process의 집합에서 P0은 P1이 점유한 자원을 대기하고, Pn-1은 Pn이 점유한 자원을 대기하고, Pn은 P0이 점유한 자원을 대기함

→ 이 조건이 발생하는 것을 방지해야 함