대학교 공부/운영체제

운영체제 (6) - Concurrency: Deadlock and Starvation

오답노트의 주인 2025. 6. 18. 16:18

2024년 1학기 운영체제 수업을 듣고 정리한 내용입니다. 수업 교재는 운영체제 - 내부구조 및 설계원리 8 판입니다.

Deadlock

두 개 이상의 프로세스에서 발생한다. 서로 Blocked 상태인데 오직 상대방이 나의 Blocked 상태를 해제시켜줄 수 있을 때 Deadlock이 발생했다고 한다.

발생 조건

데드락은 4가지 조건이 모두 만족될 경우 발생한다.

  • Mutual Exclusion : 한 자원에 대해 한 프로세스만 사용가능할 때

  • Hold and Wait : 어떤 자원을 가진 상태에서 다른 자원을 쓰기 위해 기다릴 때

  • No Preemption : 누구도 프로세스가 가진 자원을 뺏지 못할 때

  • Circular wait : 프로세스끼리 원형 관계가 형성될 때

    원형관계는 서로가 서로의 자원을 얻으려하는 것이다.

Resource Allocation Graph

자원의 소유와 요청을 그래프로 표현하면 이렇다.

프로세스가 자원을 요청할 때에는 자원으로 향하는 화살표로, 프로세스가 자원을 소유할 때에는 자원의 점에서 프로세스로 향하는 화살표로 표현된다. Circular wait를 나타내면 이렇다.

해결 전략

데드락을 해결하는 방법은 일반적으로 3가지다.

Prevent

데드락을 예방하는 방법이다. 자원을 할당할 때 정해진 규칙에 의해 할당하고 데드락의 발생 가능성에 대해서는 검사하지 않는다.

데드락을 예방하려면 4가지 발생 조건 중 하나라도 만족하지 않도록 강제하면 된다.

  • Mutual Exclusion (?)

    상호 배제가 아니라면 동시성 문제가 발생하기 때문에 이 조건을 만족하지 않도록 할 수 없다.

  • Hold and Wait

    모든 프로세스가 초기화 단계에서 실행에 필요한 모든 자원을 요청하도록 한다. 즉, 모든 자원을 Hold하므로 Wait하지 않도록 만드는 방법이다. 그러나 미리 Hold 시키는 방법이 어렵다.

  • No Preemption

    어떤 자원을 요청할 때 그 자원을 다른 프로세스가 소유하고 있다면, 다른 프로세스로부터 자원을 강제로 뺏고 그 프로세스를 처음부터 다시 시작하도록 한다. 이렇게 한다면 자원을 뺏긴 프로세스는 처음부터 다시 시작하게 되므로 실행이 언제 끝날지 모르게 된다.

  • Circular wait

    자원에 번호를 붙이고, 자원 할당 시 오름차순으로 자원을 선택해 할당한다.

    이 방법이 Circular wait가 안되도록 만드는 것을 증명하면 다음과 같다.

    P1이 Rb를 소유하고 Ra를 요청한다는 것은 Rb의 번호가 Ra보다 낮다는 것인데 P2가 Ra를 소유하고 Rb를 요청한다는 것은 Ra의 번호가 Rb보다 낮다는 것이다. 즉, $Ra < Rb$와 $Rb < Ra$가 성립해야하는데 모순이므로 Circular wait가 깨지게 된다.

Avoid

데드락을 피하는 방법이다. 자원을 할당할 때 OS가 이 자원을 할당하면 데드락이 일어나는지 검사한다. OS가 검사를 하기 위해서는 프로세스가 요청할 자원을 최대치를 알고 있어야 한다.

Initial Denial

프로세스를 시작하기 전에 검사하고, 안전하다고 판단되면 실행시키는 것이다. 안전하지 않다고 판단되면 프로세스를 Blocked한다.

현재 할당된 자원의 수 + 프로세스가 요청할 자원의 수가 전체 자원의 수보다 작을 경우 Safe하다고 판단한다. 현재 할당된 자원의 수 및 전체 자원의 수와 프로세스가 요청할 자원의 수 등은 테이블을 통해 판단한다.

Claim matrix는 프로세스가 요청할 자원의 수, Resource Vector는 시스템 내 자원의 총량을 의미한다. Initial Denial 방식은 프로세스가 하나씩 도착하여 Resource Vector값을 변경하고 자원을 받아간다.

만약 P1, P2, ... P4순으로 시작하게 된다면,

  1. P1에게 자원을 할당한다. => Resource Vector = [9, 3, 6] - [3, 2, 2] = [6, 1, 4]
  2. P2에게 자원을 할당한다. => [6, 1, 4] - [4, 1, 3] = [2, 0, 1]
  3. P3에게 자원을 할당한다. => [2, 0, 1] - [3, 1, 4] = [-1, -1, -3]
    시스템이 가진 자원의 수가 음수일 수 없으므로 P3는 자원을 받아가지 못하고 Suspend 된다.

Allocation Denial

프로세스에게 자원을 할당하는 시기에 검사한다. 검사하기 위해서는 자원 테이블을 보고 판단해야하는데, 프로세스가 요청할 자원의 총량은 변하지 않아야 한다. 프로세스에게 자원을 할당한 후 모든 프로세스가 자원을 반납하고 종료하는 시나리오가 존재한다면 Safe하다고 판단한다.

Allocation matrix는 현재 할당된 자원의 수를, C-A는 프로세스가 요청한 자원의 수와 프로세스에게 할당된 자원의 수를 뺀 값이다. Available Vector는 현재 사용 가능한 자원의 수를 말한다.

현재 상황이 데드락인지 판단하려면 사용 가능한 자원을 가져갔을 때 종료가능한 프로세스가 하나라도 있어야 한다. 그러려면 C-A에서 Available Vector를 가져갔을 때 C-A가 0이 되는 행을 찾는다. 즉, C-A의 행의 값에서 Available Vector값을 뺐을 때 모든 원소가 0이 되는 행을 찾는다. 여기서는 P2에게 자원을 할당한다면 P2는 요청한 모든 자원을 갖게 된다.

모든 자원을 가져갔다면 그 프로세스는 결국 가진 자원을 반납하고 종료될 것이다. P2가 종료되었다고 가정하고 가져간 자원(Allocation matrix)을 모두 반납하면 Available Vector는 [0, 1, 1] + [6, 1, 2] = [6, 2, 3]이 된다. 다시 Available Vector를 가져갔을 때 C-A가 0이 되는 행을 찾는다.

앞에서 찾을 때에는 P2만 0이 될 수 있는 행이었지만 지금은 모든 프로세스가 0이 될 수 있다. 기본적으로 위에서부터 탐색하기 때문에 다음으로 0이 되는 행은 P1이다. P1이 자원을 가져가고 언젠가 종료된다고 가정하면 Available Vector는 [6, 2, 3] + [1, 0, 0] = [7, 2, 3]이 된다.

그 다음으로는 P3이 종료될 수 있으므로 Available Vector는 [7, 2, 3] + [2, 1, 1] = [9, 3, 4]가 되고 마지막으로 P4가 종료된다면 Available Vector는 [9, 3, 4] + [0, 0, 2] = [9, 3, 6]이 된다. 모든 프로세스가 종료되고 자원을 반납할 수 있으므로 이 상태는 Safe다.

이 알고리즘을 Banker의 알고리즘이라고 하고 코드로 보면 다음과 같다.

struct state {
  int resource[m];
  int available[m];
  int claim[n][m];
  int alloc[n][m];
}

위의 테이블을 각각 배열로 관리한다. 

if (alloc[i,*] + request[*] > claim[i,*]) 
  /* 요청한 모든 자원의 수가 시스템 자원의 수보다 많으면 
     알고리즘의 전제가 깨진 상태이므로 에러 발생 */; 
else if (request[*] > available[*]) 
  /* 할당 가능한 자원보다 더 많이 요청하는 경우엔 Suspend */;
else {
  /* 자원을 가져갔다고 가정하기 */
  alloc[i,*] = alloc[i,*] + request[*];
  available[*] = available[*] - request[*];
}
if (safe())
  /* 자원할당 수행 */;
else {
  /* 이전 상태로 복구 */
  /* 프로세스를 중단시킴 */
}

먼저 프로세스가 요청한 자원의 전체 수(Claim matrix)가 달라졌는지 if (alloc[i,*] + request[*] > claim[i,*])으로 검사한다. 그런 경우가 발생한다면 알고리즘을 실행시킬 수 없으므로 프로세스를 종료시킨다.

그 다음으로는 프로세스가 요청한 자원이 현재 사용 가능한 자원보다 더 많이 요청하는 경우에는 알고리즘을 돌릴 필요 없이 Suspend시키면 되므로 else if (request[*] > available[*])로 검사한다.

위 두 가지 예외를 처리하고 나서 프로세스가 요청한 자원을 가져갔다고 가정한 다음 safe()함수를 호출하여 알고리즘을 실행한다.

boolean safe() {
  int currentAvail[m];
  process rest[<numberOfProcess>]; // 프로세스 목록
  currentAvail = available;
  rest = {all processes}; 
  possible = true;
  int found = 0;
  while (possible) {
    /* claim[k,*] - alloc[k,*] <= currentAvail인 인덱스 k를 프로세스 목록에서 찾기 */

    if (found) {
      currentAvail = currentAvail + alloc[k,*];
      rest = rest - {process k}; // 프로세스 목록에서 인덱스 k번째 프로세스 제거
    }
    else possible = false;
  }
  return (rest == null);
}

현재 사용 가능한 자원의 수를 복사한 후 그 값을 변경해가면서 프로세스를 종료시킨다. C-A에서 Available Vector를 뺐을 때 0이 되는 행을 찾기 위해 /* claim[k,*] - alloc[k,*] <= currentAvail인 인덱스 k를 프로세스 목록에서 찾기 */줄에서 탐색한다. 탐색에 성공했다면 found값이 1로 바뀌고 currentAvail값을 업데이트한다. 그리고 인덱스 k번째 프로세스를 프로세스 목록에서 제거하고 탐색을 진행한다. 모든 프로세스가 종료되었다면 프로세스 목록 rest가 null값이 되어있으므로(남은 프로세스가 없으므로) true가 반환될 것이다.

Detect

데드락을 피하기 위해 사용하는 알고리즘이 상당히 복잡하기 때문에, 데드락이 발생하는지 확인만 하면 간단해질 것이다.

Banker의 알고리즘과 유사하지만 Request matrix가 등장한다. Request matrix는 요청했으나 아직 할당되지 않은 자원의 수, Allocation matrix는 할당된 자원의 수, 그리고 Available Vector는 사용 가능한 자원의 수다.

이 알고리즘은 데드락이 발생하지 않는 프로세스를 찾아 표시를 하고, 표시되지 않은 프로세스가 생긴다면 데드락이 감지된 것이다.

Allocation matrix에서 모든 행이 0이라면, 아무 자원을 할당하고 있지 않은 상태이므로, Hold and Wait 조건을 만족하지 않는다. 그러므로 P4는 데드락이 발생하지 않는 프로세스이니까 표시를 한다.

그 다음으로는 현재 사용 가능한 자원을 가져갔을 때 Request matrix의 행이 0이 되는 프로세스를 찾는다. 위에서부터 찾는다면 P3이 적합하다. 그렇다면 P3를 표시한 뒤 Allocation matrix에 있는 P3행의 값을 Available Vector에 더한다. 그리고 수정된 Available Vector를 가져갔을 때 Request matrix의 행이 0이 되는 프로세스를 찾는다.

P1과 P2는 둘다 Available Vector의 값을 가져가도 Request matrix의 행을 0으로 만들 수 없다. 그러므로 P1과 P2는 데드락이 감지된 것이다.

Recovery Strategies

데드락이 감지되었다면 아래의 전략 중 하나를 선택한다.

  • 강제로 데드락 프로세스를 종료한다.
  • 프로세스의 체크포인트를 백업 후 그곳부터 재시작한다.
  • 하나씩 프로세스를 종료시켜 처음부터 재시작한다.
  • 프로세스를 종료시키지 않고 체크포인트로 되돌려서 시작한다.

철학자 문제

5명의 철학자들이 테이블에 둘러 앉아서 밥을 먹는다. 밥을 먹기 위해서는 양쪽 포크를 잡아야 하는데, 테이블에 포크가 5개밖에 없다. 그렇기 때문에 옆 사람이 자신의 포크를 가져갔다면 밥을 먹지 못하고 기다리는 상황이 된다.

First solution with semaphore

semaphore fork[5] = {1};
int i;
void philosopher (int i) {
  while (true) {
    think();
    wait(fork[i]);
    wait(fork[(i+1) % 5)]);
    eat();
    signal(fork[(i+1) % 5]);
    signal(fork[i]);
  }
}

void main() {
  parbegin(philosopher(0), philosopher(1) ... , philosopher(4));
}

함수 내에서 i는 프로세스 번호로, 각 프로세스는 i번째 포크를 먼저 집고 (i+1)%5번째 포크를 집게 된다. 각 포크는 세마포어가 할당되어 있어 옆 사람이 자신의 포크를 가져갔다면 세마포어에서 기다리게 된다. 그 사람이 밥을 먹고 포크를 내려놨다면(signal을 호출했다면) 포크를 집고 밥을 먹게 된다.

하지만 모두 왼쪽 포크만 집게 되는 상황이 발생한다면(wait(fork[i])에서 timeout걸린다면) circular wait상태가 되어 데드락이 걸리게 된다.

Q. Circular Wait를 해결하는 방법을 적용한다면?

앞서 데드락의 4가지 조건중 Circular wait를 해결하기 위해 자원에 번호를 붙여 할당하도록 했었다. 이 방법을 적용한다면 각 프로세스는 항상 더 낮은 숫자의 자원을 먼저 wait하여야 한다.

semaphore fork[5] = {1};
void philosopher(int i) {
  int left = i;
  int right = (i+1)%5;
  if (right < left) {   // 왼쪽 포크가 오른쪽 포크보다 번호가 크다면
    left = (i+1)%5;     // 오른쪽 포크를 먼저 잡도록 순서를 바꾼다. 
   right = i;
  }
  while(true) {
    think();
    wait(left);
    wait(right);
    eat();
    signal(right);
    signal(left);
  }
}

void main() {
parbegin(philosopher(0), philosopher(1) ... , philosopher(4));
}


**왼쪽 포크의 인덱스와 오른쪽 포크의 인덱스를 확인하여 더 낮은 것부터 잡도록 처리한다**. 이렇게 하면 4번 철학자는 4번 포크와 0번 포크중 0번을 먼저 잡으려고 기다리므로 3번 철학자는 3번과 4번 포크를 잡을 수 있다.

Second solution with semaphore

세마포어를 하나 더 만드는 방법으로 첫 번째 솔루션을 완성할 수 있다. 

semaphore fork[5] = {1};
semaphore room = {4};
int i;
void philosopher (int i) {
  while (true) {
    think();
    wait(room);
    wait(fork[i]);
    wait(fork[(i+1) % 5)]);
    eat();
    signal(fork[(i+1) % 5]);
    signal(fork[i]);
    signal(room);
  }
}

void main() {
  parbegin(philosopher(0), philosopher(1) ... , philosopher(4));
}

room은 포크를 잡을 수 있는 구역을 의미한다. room의 초기값이 4로 지정되어 있는 것은 4명의 철학자들만 그곳으로 진입할 수 있다는 것을 의미한다. 4명만 들어갈 수 있는 것은 5개의 포크를 잡게 될 때 어느 한 명은 2개를 잡게 된다는 것이다. 2개를 잡았다면 밥을 먹고 나오기 때문에 5명 모두 왼쪽 포크를 잡거나 오른쪽 포크를 잡고 기다리는 상황이 발생하지 않는다.

Monitor solution

get_forks와 release_forks는 모두 모니터 속 프로시저다. get_forks속에는 왼쪽 포크를 잡고 오른쪽 포크를 잡는 코드로 구현되어 있다. 모니터를 이용하여 포크를 집는다면 데드락이 발생하지 않는다.

Q. 세마포어와 동일하게 왼쪽 포크를 잡고 오른쪽 포크를 잡는데 왜 데드락이 발생하지 않는가?

모니터에는 한 번에 한 프로세스만 진입하니까 (x)
프로세스가 모니터 밖 큐에서 기다리기 때문에 (x)

모니터 속에서도 Timeout이 걸릴 수 있다. 하지만 Timeout이 되더라도 다른 프로세스가 모니터 속으로 들어올 수 없기 때문에 왼쪽 포크를 잡고 Timeout이 되더라도 오른쪽 포크를 잡기 전까지는 모니터 속에 있게 된다.

만약 왼쪽 포크를 잡는 것과 오른쪽 포크를 잡는 코드가 두 개의 프로시저로 나누어 구현되었다면 왼편 포크를 잡고 모니터 밖으로 나가는 경우가 생기기 때문에 데드락이 발생한다.

저작자표시 (새창열림)