서론

지난시간에 공유 메모리를 프로세스들이 동시에 건들면서 생기는 임계구역에 관한 문제들에 대해서 짧게 배웠었다. 이번시간에는 이런 임계 문제들을 어떻게 해결하는지에 대해서 다뤄보도록 하겠다.

임계구역 문제

임계구역 문제는 OS에서 여러 프로세스가 공유 메모리에 동시에 접근할 때 발생하는 데이터 불일치 문제를 해결하기 위한 "동기화" 이슈이다.

• 여러 프로세스가 공유 자원에 동시에 접근할 때 실행 순서에 따라 결과가 달라질 수 있다. (Race Condition)

임계구역 문제 요구 조건

임계구역 문제를 해결하기 위해서는 밑에 조건을 "반드시" 만족해야 한다.

1. 상호 배제(Mutual Exclusion)
   : 한 프로세스가 임계구역에 있으면, 다른 프로세스는 들어갈 수 없어야 한다.
2. 진행 (Progress)
   : 임계구역에 아무도 없고, 진입을 원하는 프로세스가 있다면 무한정 대기(postponed) 하면 안된다.
3. 한정 대기 (Bounded Waiting)
   : 한 프로세스가 임계구역 요청한 후, 다른 프로세스들은 임계구역에 횟수 제한이 있어야 한다. -> 무한정 대기 방지

임계구역 문제 해결 시도

Use Lock

단순 Lock 변수를 사용해 임계구역 진입 전 확인하는 방법

shared int locked = 0;

do {
	while (locked == 1);
	locked = 1;
    critical section
	locked = 0;
	remainder section
} while (true);

• 하지만 두 프로세스가 동시에 Whild(locked == 1) 을 통과하면 둘 다 임계구역에 들어갈 수 있기 때문에 실패한다.

Take Turns (번갈아 가기)

turn 변수를 두고, 자신의 차례일때만 임계구역에 진입하는 방법

shared int turn = 0;

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

• 하지만 진입을 원하지 않는 프로세스의 차례가 되면, 다른 프로세스는 그동안 진입을 하지 못한다는 문제가 발생한다. -> 진행 조건 위반

Check Intention (의도 확인)

각 프로세스가 자신의 진입 의도를 flag 변수로 표시한다.

shared int flag[2];

do {
	flag[me] = true;
	while (flag[ !me] == true);
	critical section
	flag[me] = false;
	remainder section
} while (true);

• 하지만 마찬가지로 두 프로세스가 동시에 flag를 true로 설정하면 교착상태에 빠지게 된다.

Perterson's Solution

Perterson 알고리즘은 위의 3개의 조건을 만족하는 고전적 소프트웨어 해법이다.

• 각 프로세스에 진입 의도를 flag 변수를 통해 구현하고 상대방에게 turn 을 넘긴다.
• 임계구역 진입 전, 상대방이 진입 의도가 있고 turn 이 상대면 대기.
• 임계구역에서 나오면 자신의 flag를 false로 한다.

//공유 변수
shared int turn, flag[2];

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

• 상보 배제, 진행, 한정 대기를 모두 증명 가능하다.

• Lock을 통해 임계구역에 진입하기 전에 락을 획득 하고, 임계구역을 벗어날 때 락을 해제해야한다. 이 과정에서 한번에 하나의 프로세스만 임계구역을 실행하게 보장한다.

Perterson 알고리즘의 한계점

• Peterson 알고리즘은 소프트웨어적으로 상호 배제, 진행, 한정 대기 조건을 만족하지만, 내부적으로 사용하는 공유 변수(flag, turn 등)에 대한 접근이 반드시
  "원자적(atomic)"이어야 한다.
  즉, 여러 명령어가 중간에 끊기지 않고 한 번에 실행되어야만 안전하게 동작한다.

<공유 변수의 문제>

register = <memory>;      // 메모리에서 값을 읽어 레지스터에 저장
register = <new value>;   // 레지스터 값을 갱신
<memory> = register;      // 레지스터 값을 다시 메모리에 저장

대부분의 프로그래밍 언어에서 이렇게 메모리를 읽고 쓰는 작업을 수행하게 되는데, 읽기(get)와 쓰기(set)사이에 인터럽트나 context switch가 발생하면 다른 프로세스가 동일한 메모리 값을 변경할 수 있다. -> Race Condition발생

• 원자적 연산의 필요성

한계점 해결 방법

1. 인터럽트 비활성화 (Disabling Interrupt)

• 단일 프로세스 환경에서는 임계구역에 진입할때 인터럽트를 비활성화 하면 현재 실행중인 코드가 중간에 끊기지 않고 끝까지 실행될 수 있다.
• 하지만 멀티 프로세스 환경에서는 비효율적이고, 전체 시스템 저하를 야기할 수 있다.

2. 원자적 하드웨어 명령어 (Atomic Instruction)

현대 CPU는 TestAndSet, CompareAndSwap, Swap등 특수한 원자적 명령어를 제공한다.

• 이 명령어들은 읽기-연산-쓰기를 한번에 수행하여 도중에 다른 프로세스가 개입할 수 없게 만든다.

shared int locked = false;
do {
    while (locked == true); // 다른 프로세스가 임계구역에 있으면 대기
    locked = true;          // 임계구역 진입 시도
    // critical section
    locked = false;         // 임계구역 종료 후 lock 해제
    // remainder section
} while (true);

기존 Lock구현 코드를 보면 여러 프로세스가 동시에 lock변수를 확인하고 임계구역에 들어가면 문제가 생긴다.
이는, while (locked==true)와 locked = true; 사이에 인터럽트나 context switch가 발생하게 되면 두 프로세스가 들어갈 수 있게 되는 것이다.

"즉, TEST(확인)와 SET(설정) 사이의 틈(gap) 때문에 문제가 발생."
따라서 원자적 명령어가 필요한 것이다. 참고로 원자성이란 결과가 온전히 실행되거나 아예 실행되지 않아야 하는것을 의미한다.

1. TestAndSet 명령어 사용

boolean TestAndSet (boolean *target)
{
  boolean rv = *target; //(1)현재 값을 읽는다.
  *target = true; //(2)값을 true로 한다.
  return rv: //(3)읽은 값을 반환한다.
}

여기서 핵심은 (1)번과 (2)번이 반드시 원자적으로 실행된다는 점이다. 따라서 이 함수가 실행되는 동안 어떤 다른 프로세스도 target값을 변경할 수 없다.

shared boolean lock = false;
do {
    while (TestAndSet(&lock)); // lock이 TRUE면 대기(busy waiting)
    // critical section
    lock = false;              // 임계구역 종료 후 lock 해제
    // remainder section
} while (true);

따라서 기존 Lock에서 TestAndSet을 사용하기 위해서는 이렇게 사용하면 된다.

do {
    waiting[i] = TRUE;
    key = TRUE;
    while (waiting[i] && key)
        key = TestAndSet(&lock);
    waiting[i] = FALSE;
    // critical section
    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
        j = (j + 1) % n;
    if (j == i)
        lock = FALSE;
    else
        waiting[j] = FALSE;
    // remainder section
} while (TRUE);

• waiting: 진입의도를 나타냄
• key: 이전 TestAndSet에서 lock을 얻었는지.
• lock가 false면 사용가능한 상태기 때문에, 반복문 break; (맨처음 lock은 false니까 바로 통과 후 lock이 true로 바뀜)
• j는 현재에서 다음 프로세스.
• j와 i가 다르고 j의 진입의도가 없다? -> 다음꺼 확인.
• 의도가 있는걸 찾기 위함임.
• 의도가 있는게 없다면 j=i까지 즉, 한바퀴 돌음.
• 한바퀴를 돈거라면 lock은 fasle로 하고 종료, 아니라면 j의 진입을 false로 한다. -> 차례를 넘긴것.
• J 프로세스는 while (waiting[i] && key) 여기에 갇혀있기 때문.

⚠️ 하지만 TestAndSet등 하드웨어를 명령어를 이용한 방법은 busy waiting(무한 루프) 의 문제점이 존재한다.

2. Semaphore

세마포어는 정수값을 가지는 변수로, 두 가지 원자적 연산만 허용된다.

• wait(S): S가 0보다 크면 1감소, 0이면 대기.
• signal(S): S를 1증가, 대기중인 프로세스가 있으면 깨운다.

wait (S) {
	while S <= 0
		; // no-op (busy waiting)
	S--;
}

signal (S) {
	S++;
}

1. wait

   • S가 0보다 크면 S를 1 감소시킨다.

   • S가 0 이하이면, S가 0보다 커질 때까지(즉, 다른 프로세스가 signal을 호출할 때까지) 반복해서 대기한다(busy waiting).

   • 이 연산은 임계구역 진입 전에 호출되어, 자원이 없으면 진입을 막고, 자원이 있으면 진입함.

2. signal

   • S값을 1증가시킨다.
   • 이 연산은 임계구역에서 나올때 호출되어, 대기 중인 다른 프로세스가 임계구역에 들어갈 수 있게 해준다.

세마포의 종류로는 크게 2가지가 있다.
1. 카운팅 세마포어: 값이 0 이상인 정수 (여러 자원 관리)
2. 이진 세마포어(뮤텍스):값이 0 또는 1(임계구역 보호)

Semephore 동작 방식

• Busy Waiting( Spinlock ) 문제
  • 전통적 세마포어는 값이 0일때 계속 루프를 돌며 대기(busy waiting)하게 된다.
  • CPU 자원을 낭비하므로 효율적이지 않다.
• Blocking 기반 세마포어 구현
  • 세마포어 내부에 대기 큐를 두고, wait에서 값이 0 이하일 때 프로세스를 큐에 넣고 block한다.
  • signal이 호출되면 큐에서 프로세스를 깨워서 ready상태로 전환한다.

Semephore 기본 사용 방식

semaphore count_mutex = 1;
do {
    wait(count_mutex);
    // critical section
    signal(count_mutex);
    // remainder section
} while (TRUE);

• 여러 프로세스가 동시에 임계구역에 들어가지 못하도록 보장.
• 자원 개수 제한 (카운팅 세마포어): 예를들어 5개만 필요하면 mutex값을 5로 설정해 최대 5개만 접근을 허용할 수 있다.

Busy Waiting없는 세마포어 구현

• 기존의 세마포어 wait 연산은 busy waiting으로 cpu를 낭비한다.
• 이를 개선하기 위해 세마포어 내부에 대기 큐를 두고, 자원이 없을때 프로세스를 Block한다.
• signal 연산은 대기 큐에서 ready상태로 만들어 준다.

// 세마포어 구조체
typedef struct {
    int value;
    struct process *list; // 대기 큐
} semaphore;

// wait 연산
wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // S->list에 현재 프로세스 추가
        block();
    }
}

// signal 연산
signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // S->list에서 프로세스 하나 꺼냄
        wakeup();
    }
}

• block() => 해당 작업을 요청한 프로세스를 적절한 대기 큐에 넣는다.

• wakeup() => 대기 큐에 있는 프로세스중 하나를 꺼내서 ready 큐에 넣는다.

• signal에서 value보다 작으면 꺼내는 이유: 대기 큐에 있다는 뜻이기 때문에.

• 세마포어의 waiting list

  • 세마포어마다 대기중인 프로세스의 PCB들을 연결 리스트로 관리한다.
  • bounded waiting, starving을 방지하기 위해 일반적으로 FIFO로 구현된다.

☝️ wait과 signal 연산 자체가 공유 데이터를 수정하기 때문에 이 연산들 자체가 임계구역이 된다!
✌️ 단일 프로세서의 경우에는 이 구간에서 인터럽트를 비활성화 하면 되지만 멀티 환경에서는 어렵고 비효율적이기 때문에 이 구간에서 spinlock을 사용해 임계구역을 보호한다.

Deadlock & Starvation

Deadlock (교착 상태)

두개 이상의 프로세스가 서로 상대방이 signal을 호출해주길 기다리며 영원히 block상태에 빠지는 현상.

• S와 Q 두 세마포어가 존재할때,
  • P0: wait(S) -> wait(Q)
  • P1: wait(Q) -> wait(S)
• 두 프로세스가 서로 상대의 signal을 기다리며 영원히 대기하게 될 수 있다.

Starvation (기아)

• 어떤 프로세스가 세마포어의 waiting queue에서 계속 대기만 해서 실행되지 못하는 현상.
• waiting queue가 FIFO가 아니거나, 우선순위 선점이면 기아가 발생할 수 있다.

Priority Inversion(우선순위 역전)

• 낮은 우선순위 프로세스가 락을 점유해 높은 우선순위 프로세스가 대기하게 되는 현상
• Priority Inheritance(우선순위 상속) 프로토콜 등으로 해결한다.

Bounded Buffer 문제 (생산자-소비자 문제)

• 생산자는 버퍼가 가득차면 대기해야 하고, 소비자는 버퍼가 비면 대기해야 한다.
• 생산자와 소비자가 동시에 버퍼에 접근하면 안된다.(임계구역 문제)

이 문제를 세마포어를 이용해 해결할 수 있다. 이제 단계적으로 어떻게 해결하는지 알아보자.

BBP v1 (기본 형태)

• 생산자

  do{
  	//produce an item
      wait(empty);
      //버퍼에 아이템 추가
  }while(true);

• 소비자

  do{
  	// 버퍼에서 아이템 삭제
      signal(empty);
      // 아이템 소비
  }while(true);

BBP v2 (full 세라포머 추가)

• 생산자

  do{
  	//produce an item
      wait(empty);
      //버퍼에 아이템 추가
      
      signal(full);
  }while(true);

• 소비자

  do{
  	wait(full);
      
  	// 버퍼에서 아이템 삭제
      signal(empty);
      // 아이템 소비
  }while(true);

BBP v3

• 생산자

  do{
  	//item 생성
      wait(empty);
      wait(mutex);
      //버퍼에 아이템 추가
      
      signal(mutex);
      signal(full);
  }while(true);

• 소비자

  do{
  	wait(full);
      wait(mutex);
  	// 버퍼에서 아이템 삭제
      signal(mutex);
      signal(empty);
      // 아이템 소비
  }while(true);

• mutex 초기값 = 1;

• full 초기값 = 0;

• empty 초기값 = N(버퍼 크기)

• mutex를 추가하여 생산자와 소비자가 공유버퍼를 동시에 접근하는것을 방지하여 데이터 불일치와 race condition을 완전히 해결하였다.

Readers-Writers Problem

• 여러 리더(읽기)는 동시에 허용한다. 하지만 Writers는 단독 진입만 허용한다.
• 공유변수 read_count와 세마포어 rw_mutex, wrt를 조합하여 사용한다.
• 첫번째 리더가 들어오면 wrt 세마포어를 wait한다. 마지막 Reader가 나갈때 signal한다.

=> wrt는 오직 reader들끼리 read_count를 안전하게 조작하기 위해 경쟁한다.
=> rw_mutex는 reader와 writer 모두 공유 자원 접근에 대해 경쟁한다.

이를 해결하기 위해 mutex(이진 세마포어)를 사용해 상호배제 한다.

Writer 알고리즘

• 데이터 셋 접근 전 wrt 세마포어를 wait, 작업후 signal한다.

do {
	wait(wrt)
     // 쓰기 작업 수행
    
    signal(wrt);
    
}while(true);

• 만약 다른 writer가 쓰고있거나 reader가 읽고있다면 대기한다.

Reader 알고리즘

• 첫번째 리더는 데이터셋에 writer가 접근하지 못하도록 wrt를 wait한다.
• 마지막 리더는 wrt를 signal하여 writer가 접근할 수 있도록 한다.

do {
	wait(mutex);
    read_count++;
    if (read_count == 1)
    	wait(wrt); // 첫번째 리더면 wrt 대기
   	signal(mutex);
    
    //읽기 작업 수행
    wait(mutex);
    read_count--;
    if (read_count == 0)
    	signal(wrt);
    signal(mutex);
} while(true);

• mutex로 readcount를 안전하게 수정
• 여러 리더가 동시에 읽을 수 있으나, writer가 접근 중이면 모두 대기

Dining Philosophers Problem (식사하는 철학자 문제)

• 여러 철학자가 두 젓가락(자원)을 공유하여 식사한다.
• 각 젓가락을 세마포어로 모델링 하여 교착상태와 기아를 방지한다.

• N명의 철학자가 원형 테이블에 앉아 있음.

• 각 철학자 사이에는 젓가락(자원)이 하나씩 놓여 있음(총 N개).

• 철학자는 생각(thinking)하다가 배가 고프면 식사(eating)를 하려 하고, 식사하려면 양쪽의 젓가락 두 개를 모두 들어야 함.

• 식사가 끝나면 젓가락을 내려놓고 다시 생각에 잠김.

철학자 알고리즘

공유 데이터: 젓가락으르 세마포어로 모델링 -> semephore chopstick[5]; (각 chopstick은 1로 초기화 한다.)

do {
	wait(chopstick[i]);
    wait(chopstick[(i+1)%5])
    //eat
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
    //think
} while(true);

• wait(chopstick[i]): 왼쪽 젓가락을 집음

• wait(chopstick[(i+1)%5]): 오른쪽 젓가락을 집음

• signal(...): 식사 후 젓가락을 내려놓음

⚠️모든 철학자(프로세서)가 동시에 한 젓가락씩만 잡으면 교착상태에 빠지게 된다.

해결책

• 적어도 한명은 식사하지 않도록 강제한다. -> 실용적이진 않음.
• 적어도 한명은 젓가락을 양쪽 다 얻을 때만 집도록 한다. -> 구현이 복잡해질 수 있음.
• 비대칭(짝수/홀수가 다르게 집기)등 다양한 방법을 활용한다.

---

Deadlock Problem (교착상태 문제)

여러 프로세스가 서로가 가진 자원을 기다리며 영원히 Block되는 문제.

예시: 시스템 디스크 드라이브 2개, p1 과 p2가 각각 하나씩 보유중인데 서로가 상대방의 디스크를 요구하며 대기한다 -> 교착상태 발생.

Deadlock 발생조건 4가지

1. Mutual Exclusion(상호 배제): 한 번에 하나만 자원 사용 가능

2. Hold and Wait(보유 및 대기): 자원을 보유한 채 추가 자원 요구

3. No Preemption(비선점): 자원을 강제로 빼앗을 수 없음

4. Circular Wait(순환 대기): 원형으로 자원을 기다림

---

Resource-Allocation Graph (RAG)

시스템 내 프로세스와 자원 간의 할당 및 요청 관계를 시각적으로 표현한 그래프.

• 정점(Vertex, V): 두가지 타입이 존재.

  • 프로세스(P): P1, P2 .... Pn
  • 자원 타입(R): R1, R2 .... Rm(각 자원 타입은 여러 인스턴스를 가질 수 있다.)

• 간선(Edge E):

  • 요청 간선(Request edge):프로세스의 자원으로 향하는 방향(Pi -> Rj). Pi가 Rj에게 인스턴스를 요청하고 있다는 의미이다.
  • 할당 간선(Assignment edge): 자원에서 프로세스로 향하는 방향(Rj -> Pi)Rj의 인스턴스가 Pi에게 할당됨을 의미한다.

• Resource: 시스템에서 프로세스들이 필요로 하는 대상의 "종류"를 의미한다. (프린터, 디스크 드라이브, 메모리 블록 등등)
• Instance: 각 자원 타입이 실제로 몇개의 "개별 단위"로 존재하는지를 나타낸다. (프린터 자원 타입이 2개의 인스턴스를 가지면 실제로 2개의 프린터가 존재한다는 뜻)

• 사이클이 없는 경우에는 deadlock이 없다.
• P3작업이 끝나면 R3를 반납하기 때문에 P2가 동작하고 P1이 동작할 수 있다. -> 데드락 아님.
• P->R은 요청간선 (프로세스가 자원을 요청중임을 의미)
• R->P는 할당간선 (자원의 인스턴스가 프로세스에 할당됨을 의미)

• 지원 타입이 인스턴스가 1개뿐이라면, 사이클이 곧 데드락이다.(R2)
• 여러 인스턴스가 있다면, 사이클이 있어도 데드락이 아닐 수 있다.(가능성은 존재)
• P3가 작업을 끝내기 위해서는 R2자원을 사용해야 하는데 이미 P1, P2에 할당되어있어서 끝낼 수 없다.
• P2는 P3가 할당하고 있는 R3를 원하지만 R3가 반납되지 않아 대기하게 된다.
• P1은 P2가 대기해서 같이 대기... 무한 대기 즉, 데드락 발생

• R1, R2처럼 자원 타입이 여러 인스턴스를 가지게 되면 여러 프로세서에 할당될 수 있다.

• P1-> R1-> P3-> R2로 사이클이 있지만 자원 인스턴스가 2개씩 존재하기 때문에 교착상태에 빠지지않는다.

• 즉 사이클이 존재하는데, 자원 인스턴스가 한개면 데드락이 발생하지만, 2개 이상이라면 데드락의 "가능성"이 있는것이다.

• P2나 P4의 작업이 끝나서 자원을 반납하게 되면, P1과 P3가 동작할 수 있기 때문에 데드락이 발생하지 않는다.

Deadlock 처리 방법

교착상태를 처리하는 방법으로는 크게 3가지가 존재한다.

• 데드락 예방
• 데드락 회피
• 데드락 감지

1. prevent Deadlock (데드락 예방)

교착상태에 빠지게 되는 4가지 필요조건중 하나 이상을 시스템적으로 "무효화"하는 전략

• 상호배제 무효화

  자원을 여러 프로세스가 동시에 사용할 수 있게 하기.

  • 모든 자원이 상호배제적으로 사용되면 교착에 빠지게 되기 때문에 깨드린다.(데드락 관점에서)
  • 일부자원(프린터)는 본질적으로 상호배제가 필요하지만 소프트웨어적으로 프린터 스폴링등을 통해 쪼갠다.(모든 디바이스가 가능한건 아님)

• 점유 및 대기 무효화

  프로세스가 실행하기 전에 필요한 모든 자원을 한번에 요청하게 하거나, 새로운 자원을 요청하기 전에 이미 점유한 자원은 반납하도록 요구한다.

  • 프로세스가 시작전에 필요한 자원을 모두 알기 어렵다.
  • 모든 자원이 동시에 할당할 때까지 대기해야 하기 때문에 시스템 활용도가 떨어지고 다른 프로세스가 할당해야 하는 자원까지 불필요하게 할당할 수 있다.

• 비선점 무효화

  프로세스가 자원을 점유한 상태에서 추가 자원을 요청하다가 대기하게 되면, 기존에 점유한 자원을 강제로 회수해 다른 프로세스에 할당해준다.

  • 실제로 모든 자원에 적용하기 어렵다. 예를들어 프린터 작업중에 자원이 뺏기게 되면 문서가 손상이 되기 때문이다.
  • 일부자원(CPU, 메모리)등은 선점이 가능하지만 I/O 장치들은 어렵다.
• 순환대기 무효화

  자원에 고유한 번호를 부여하고, 프로세스가 항상 오름차순(또는 내림차순)으로만 요청하게 하여 순환대기 조건을 방지한다.

  • 프로세스 자원을 순서대로만 요청하게 되면 원형대기가 발생할 수 없다.(방지 가능)

✅ Deadlock Prevention은 데드락의 네 가지 필요조건 중 하나 이상을 시스템적으로 무효화하여, 데드락이 발생할 수 없는 환경을 만드는 방법이다.

✅ 각 조건을 무효화하는 방법은 시스템의 특성과 자원 종류에 따라 적용 가능 여부와 효율성이 다르다.

✅ 현실적으로 모든 조건을 무효화하는 것은 어려우며, 실제 시스템에서는 여러 방법을 조합하거나, 일부만 적용하는 경우가 많다.

2. Deadlock Avoidence (데드락 회피)

교착상태 빠지지 않도록 자원 할당 시점마다 동적으로 안정성을 검사하는 방법이다. 데드락 예방처럼 미리 무효화 하는 것이 아니라, 자원 할당 요청이 들어올 때마다 그 요청을 허용할지 말지를 판단해 교착상태를 피하는 것이다.

1. Process Initation Denial (프로세스 시작 거부)

• 새로운 프로세스가 실행될 때, 현재 시스템의 모든 프로세서와 새 프로세서의 최대 자원 요구량을 충족시킬 수 없는 경우 거부한다.
• 단점: 모든 프로세서가 동시에 최대 자원을 요구할것이라고 가정하기 때문에 실제로는 자원 활용도가 떨어질 수 있다.

2. Resource Allocation Denial (자원 할당 거부)

• 프로세스가 추가적인 자원을 요구하면, 그 요청을 허용하게 될 경우 시스템이 안정상태를 벗어나게 된다면 거부한다.
• 대표적으로는 Banker's 알고리즘이 존재한다.

• 안전 상태 (safe state)

  • 모든 프로세서가 어떤 순서로든 자원을 할당받아 작업을 마치고 자원을 반환할 수 있는 상태.
  • 즉, 시스템 내에서 적어도 하나의 프로세스 완료 시퀀스가 존재하는 상태다,
  • 안전 상태라면 deadlock이 절대로 발생하지 않는다.
  • 시스템 내에서 프로세스 집합이 P1,P2,P3...가 있다면 각 Pi가 앞으로 필요로 하는 자원이 현재 시스템에 남아있는 (자원 + 다른 프로세스가 이미 완료해서 반환한 자원)의 합으로 충족될 수 있다면 안정상태.

• 불완전 상태 (unsafe state)

  • 현재 자원 할당 상태에서 모든 프로세스가 완료될 수 있는 시퀀스가 존재하지 않는 상태
  • 불완전 상태는 반드시 교착상태는 아니지만 가능성이 존재.
  • deadlock avoidence는 이 불완전 상태로 진입하는 것을 막는것이다.

Resource-Allocation Graph Algorithm

단일 인스턴스 자원일 경우 사용하는 Avoid 알고리즘이다.

• Claim Edge(청구 간선) 개념
  • Claim Edge는 프로세스가 미래에 해당 자원을 요청할 수 있음을 나타내는 점선이다. (Pi --- Rj)
  • 프로세스가 자원을 실제로 요청하면 청구 간선이 request edge로 바뀌고, 자원이 할당되면 assignment edge로 변환된다.
  • 자원을 반환하게 되면 다시 claim edge로 돌아온다.
  • 모든 자원 요청은 반드시 사전에 claim edge로 등록이 되어있어야 한다.

이렇게 실선을 통해 claim edge를 표현한다. 만약 R2자원이 P2에 할당이 되어있다면, 데드락 발생 가능성이 있어서 unsafe하다.

알고리즘 동작 방식

• 프로세스가 자원을 요청할 때, 요청 간선을 할당 간선으로 바꿨을 때 그래프에 사이클이 생기는지 검사한다.
• 사이클이 생기면 요청을 거부, 그렇지 않다면 허용한다.

Banker's 알고리즘

여러 인스턴스가 있는 자원 환경에서 deadlock을 회피하기 위한 대표적 알고리즘이다.

• 모든 프로세스가 자원의 최대 요구량을 시스템에 미리 알린다.
• 프로세스가 자원을 요청할 때, 그 요청을 허용하면 시스템이 여전히 안전 상태를 유지할 수 있는지 검사한다.
• 안전 상태: 프로세스가 어떤 순서로든 자원을 할당받아서 반드시 완료할 수 있는 실행 순서가 존재하는 상태
• 안전 상태라면 자원을 할당하고, 아니면 거부한다.

😃 데이터 구조

• n: 프로세스 개수
• m: 자원 타입 개수

이름	형태	의미
Available	1 x m 벡터	각 자원 타입별 현재 남은 인스턴스 수
Max	n x m 행렬	각 프로세스가 최대 몇개의 자원을 요구할 수 있는지
Allocation	n x m 행렬	현재 각 프로세스에 할당된 자원 수
Need	n x m 행렬	각 프로세스가 앞으로 추가로 필요한 자원 수 (max - allocation)

• Available[j] = k라면 자원 타입 Rj가 현재 시스템에 k개 남아있다는 뜻.
• 만약 m=3이고(A,B,C) Available = [3,2,2]라면 A는 3개, B는 2개, C는 2개가 현재 "아무것도 남아있지 않은 상태"로 있다는 뜻.
  
  
• Max[i, j] = k라면, 프로세스 Pi가 자원 타입 Rj를 최대 K개 까지 요청할 수 있다는 뜻.
  
  
• Allocation[i, j] = k라면, 프로세스 Pi에 자원 타입 Rj가 현재 k개 할당 되어 있다는 뜻.
  
  
• Need[i, j] = k라면, 프로세스 Pi가 작업을 마치기 위해 Rj가 앞으로 k개 더 필요하다는 뜻.
• 따라서 Need[i, j] = Max[i, j] - Allocation[i, j]이다.

Safety 알고리즘

시스템이 현재 안전 상태인지(모든 프로세스가 반드시 완료될 수 있는 순서가 존재하는지) 검사하는 절차

• 자원 할당의 "안정성"만을 검사한다.
• 뱅커 알고리즘의 핵심 구성 요소임

• 입려: 현재 Available, Allocation, Need등

• 출력: 안전 상태 여부(true,false), 안전 순서
  
  

• Step 1: 두 벡터를 준비한다.

  • work(길이 m): 현재 남은 자원 수.
  • finish(길이 n): 각 프로세스의 완료 여부.

• Step 2: 완료 가능한 프로세스 찾기.

  • 아직 완료 되지 않은 프로세스 중에서
  • finish[i] == false;
  • need[i] <= work 를 모두 만족하는 프로세스 Pi를 찾는다.
  • 없으면 Step4로 이동.

• Step 3: 자원 반환 및 완료 표시.

  • Pi가 작업을 마치고 자원을 모두 반환한다고 가정
  • work = work + Allocation[i]
  • finish[i] = true
  • Step 2로 돌아가서 반복한다.

• Step 4: 안정성 판별

  • 모든 i에 대해 finish[i] == true면 안전상태, 아니면 불안전 상태

Resource-Request Algorithm for Process Pi (자원 요청 처리 알고리즘)

프로세스 Pi가 자원을 요청할 때, 그 요청을 허용하면 시스템이 안전 상태를 유지할 수 있는지 검사하는 알고리즘.

• Step 1: 요청량이 need를 넘는지 확인,
  • Requesti <= Needi -> 아니면 오류(요구량 초과)
• Step 2: 요청량이 현재 Available을 초과하는지 검사.
  • Requesti <= Abailable -> 아니면 Pi는 대기
• Step 3: 임시로 자원 할당 및 안전성 검사
  • Available = Available - Requesti
  • Allocationi = Allocationi + Requesti
  • Needi = Needi - Requesti
  • 이 상태에서 Safety 알고리즘을 실행한다.

만약 이렇게 프로세스와 자원들이 있다고 가정해보자.

Max - Allocation이 Need가 되기 때문에 행렬로 각 프로세스들의 Need를 구할 수 있다.

그 다음에 Availavle이 (3,3,2)이기 때문에

• Step 1: 실행 가능한 프로세스 찾기 (Need <= Available)

  • P1. P3

• P1부터 실행하게 되면 -> Available = (3,3,2) + (2,0,0)(사용후 P1의 allocation 반환) = (5,3,2)

• P3가 실행 가능하기 때문에 실행하면 -> Available = (5,3,2) + (2,1,1) = (7,4,3)

• P4가 실행 가능하기 때문에 진행 후 P2진행

• 따라서 safe 시퀀스는 <p1, p3, p4, p2, p0>가 된다.

• 만약 safe시퀀스가 없다면 자원이 더 생길때까지 대기하게 된다.(실행 X)

• 만약 P1에서 (1,0,2)의 추가적인 요청이 온다면
• request <= need 여야 하기 때문에 => (1.0.2) <= (1,2,2)
• request <= Available 이기 때문에 => (1,0,2) <= (3,3,2)
• 만족하기 때문에 임시 할당 후 Safe 알고리즘 실행
• 요청보다 need가 작아야 하는 이유는 초기에 프로세스가 시스템에 신고한 최대 요구량을 초과해 자원을 요구하는 것이기 때문에 오류로 간주한다.(뱅커 알고리즘 신뢰성 이슈로)

• 원래 Available이 (3,3,2) 였는데 새로 요청된 (1,0,2)를 사용하기 때문에 (2,3,0)이 새로운 Available이 된다.

• Allocation[P1]도 (2,0,0) + (1,0,2) = (3,0,2)가 된다.

• Need[P1]도 (1,2,2) - (1,0,2) = (0,2,0)이 된다.

• 따라서 시퀀스를 다시 계산하게 되면 <P1,P3,P4,P0,P2>가 나온다.

3. Deadlock Detection (데드락 탐지)

데드락이 발생하는 것을 허용하지만, 시스템이 주기적으로 데드락 상태를 탐지하고 탐지된 후 적절한 복구를 수행하는 것.

Detection Deadlock Algorithm

Single Instance of Each Resource Type (각 자원 타입이 1개만 존재할 때)

• Wait-for Graph(대기 그래프) 유지

  • 노드: 프로세스

  • 간선: Pi->Pj(Pi가 Pj가 점유한 자원을 기다린다)

    

    P1은 P2가 할당하고 있는 자원을 요청하고 있기 때문에 wait-for 그래프에서는 P1->P2로 표현하는 것이다.

• 주기적으로 사이클 감지
  • 그래프에 사이클이 있으면 데드락이 발생.
  • 사이클 탐지 알고리즘: O(n^2) (n=프로세스 수)

데드락 탐지 알고리즘 흐름

• 초기화
  • Work: Available 벡터의 복사본 (현재 사용 가능한 자원 수)
  • Finish: n 길이의 bool 벡터, Allocation[i] !=0 이면 Finish[i] = false, 0이면 true.
• Step 1: 조건을 만족하는 프로세스 찾기
  • Finish[i] == false이고, Request[i] <= Work인 i가 존재하는지 찾는다.
  • 이는 현재 남은 자원만으로 Pi의 모든 요청을 바로 처리할 수 있는지 검사하는 것.
• Step 2: 프로세스 자원 반환
  • 해당 프로세스 Pi를 찾으면, Work = Work + Allocation[i](Pi가 점유하고 있던 자원을 모두 반환)
  • Finish[i] = true (Pi는 정상적으로 종료 가능)
  • 1번으로 돌아가 반복한다.
• Step 3: 더 이상 조건을 만족하는 프로세스가 없다면 종료
  • Finish[i] == false 인 프로세스가 남아있다면, 이 프로세스들은 데드락에 빠진것.

✅ 알고리즘 복잡도: O(m × n²)
(m: 자원 타입 수, n: 프로세스 수)

• 현재 그림을 보면 Available이 (0,0,0)인것을 볼 수 있다.
  또한 Finish[i] != 0 이므로 모두 false가 된다.

• P0과 P2의 request 값이 (0,0,0) <= work(0,0,0)이므로 만족하기 때문에 P0을 true로 하고 P0이 점유하고 있던 (0,1,0)을 work에 추가한다. 이렇게 하다보면 모두 ture가 되는 시퀀스가 나오게 된다.

• 그렇다면 만약에 P2가 C자원을 1개 요청하게 되면 어떻게 될까?
• 맨처음 Work는 마찬가지로 P0을 수행한 후 자원을 받기 때문에 (0,1,0)이 되는데 이 후 Request가 (0,1,0)보다 낮은것은 찾을 수 없기 때문에 데드락이 발생한다.

데드락 탐지 알고리즘 사용 시기

데드락 탐지 알고리즘이 언제, 얼마나 자주 실행할지는 다음과 같은 요소에 의해 달라진다.

• 데드락 발생 가능성

  • 데드락이 자주 발생하는 시스템에서는 탐지 알고리즘이 더 자주 실행되어야 한다. 반대로 드물게 발생하면 빈도를 낮출 수 있다.

• 복구 시 롤백해야 하는 프로세스 수

  • 데드락이 발생했을 때 복구를 위해 롤백(되돌리기)해야 할 프로세스가 많아질수록 탐지 주기를 짧게 잡는 것이 유리하다.
  • 특히, 여러개의 데드락 사이클이 발생할 경우 그 사이클마다 적어도 하나의 프로세스는 롤백해야 한다.

• 임의로 탐지 알고리즘을 사용할 경우 문제

  • 탐지 알고리즘을 아무 때나 실행할 경우, 자원 그래프의 여러 개의 사이클이 발생할 수 있고, 이 경우 어떤 프로세스가 데드락을 "유발" 했는지 명확히 알기 어렵다. 즉, 복구 대상을 선정하는것이 더 어려워 진다.

데드락 복구(Recovery)

데드락이 탐지된 후 시스템을 정상 상태로 되돌리기 위한 대표적인 방법은 프로세스 종료와 자원 선점이다.

1. 프로세스 종료(Process Termination)

• 모든 데드락 프로세스 종료

  • 데드락에 연관된 모든 프로세스를 한번에 종료하여 자원을 회수하는 방법이다. (간단하지만 많은 작업이 중단될 수 있다.)

• 하나씩 순차적으로 종료

  • 한번에 하나의 프로세스만 종료하고, 데드락이 해소 될때까지 반복한다. 이때 종료할 프로세스의 선정 기준이 필요하게 된다.

• 종료할 프로세스 선정 기준

  • 프로세스 우선순위(Priority)
  • 이미 얼마나 진행되었는지와 앞으로 남은 실행 시간.
  • 이미 사용된 자원의 양(많이 사용했으면 최대한 나중에 종료)
  • 완료까지 필요한 자원 양
  • 종료해야 할 프로세스 수(최소한의 프로세스만 종료하는게 바람직)
  • 프로세스가 대화형인지, 배치 작업인지(대화형은 사용자의 직접적인 반응을 요하므로 종료를 피해야 함.)
  • 이런 기준을 기반으로 Victim(희생) 프로세스를 선정한다.

2. 자원 선점 (Resource Preemption)

• 희생 프로세스(Victim) 선정
  • 자원을 회수할 프로세스를 선정할 때, 시스템이 미치는 비용이 최소화 되도록 선택한다.
• 롤백(rollback)
  • 회생 프로세스는 안전한 이전 상태로 되돌리고, 그 프로세스가 점유하던 자원을 회수한다. 이후 프로세스는 복구된 상태에서 다시 실행한다.
• Starvation 방지
  • 동일한 프로세스가 반복적으로 희생되지 않도록, 롤백 횟수를 비용 산정에 포함시킨다. 즉, 여러번 롤백된 프로세스는 더 이상 희생 대상으로 선정되지 않도록 해야한다.