Operation System 3(스레드 2)

💿 Dead Lock(교착 상태)

스레드(혹은 프로세스)가 자원을 얻지 못해서 다음 처리를 못하는 상태

시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생

🔔 주의

밑에서 나오는 모든 프로세스에 대한 것은 스레드에도 똑같이 해당되는 내용임

즉 프로세스 = 프로세스 + 스레드

데드락이 일어나는 경우

• 프로세스1과 2가 자원1,2를 모두 얻어야 한다고 가정해보자
• t1 : 프로세스1이 자원1을 얻음 / 프로세스2가 자원2를 얻음
• t2 : 프로세스1은 자원2를 기다림 / 프로세스2는 자원1을 기다림

즉 현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠짐

• 멀티 프로그램 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황
• 한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있음. 이때 프로세스는 대기 상황에 들어감
• 대기 상태에 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 교착 상태 발생

데드락의 조건

1. 상호 배제(Mutual exclustion)
   • 자원은 한번에 한 프로세스만 사용할 수 있음
2. 점유 대기(Hold and wait)
   • 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야함
3. 비선점(No Preemption)
   • 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음
4. 순환 대기(Circular wait)
   • 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

데드락 처리

예방 & 회피

• 예방(prevention): 교착 상태발생 조건 중 하나를 제거하면서 해결한다(자원 낭비가 심하다)
  • 상호 배제 부정: 여러 프로세스가 공유 자원 사용(IPC 같은거)
  • 점유 대기 부정: 프로세스 실행전 모든 자원을 할당
  • 비선점 부정: 자원 점유 중인 프로세스가 다른 자원을 요구 할 때 가진 자원 반납
  • 순환 대기 부정: 자원에 고유번호 할당 후 순서대로 자원 요구(세마포어, 뮤텍스)
• 회피(avoidance): 교착 상태 발생 시 피해가는 방법
  • 은행원 알고리즘
    • 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
    • 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
    • 안정상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기

탐지 & 회복

• 탐지(Detection): 자원 할당 그래프를 통해 교착 상태 탐지
  • 자원 요청 시 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생
• 회복(Recovery): 교착 상태를 일으킨 프로세스를 종료하거나 할당된 자원을 해제시켜 회복시키는 방법
  • 프로세스 종료 방법
    • 교착 상태의 프로세스를 모드 중지
    • 교착 상태가 제거될 때까지 하나씩 프로세스 중지
  • 자원 선점 방법
    • 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당(해당 프로세스 일시정지 시킴)
    • 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점

주요 질문

1. 데드락(교착 상태)가 뭔가요? 발생 조건에 대해 말해보세요.
2. 회피 기법인 은행원 알고리즘이 뭔지 설명해보세요.
3. 기아상태를 설명하는 식사하는 철학자 문제에 대해 설명해보세요.
   • 교착 상태 해결책
     • n명이 앉을 수 있는 테이블에서 철학자를 n-1명만 앉힘
     • 한 철학자가 젓가락 두개를 모두 집을 수 있는 상황에서만 젓가락 집도록 허용
     • 누군가는 왼쪽 젓가락을 먼저 집지 않고 오른쪽 젓가락을 먼저 집도록 허용

💿 Race Condition

공유 자원에 대해 여러 프로세스가 동시에 접근할 떄, 결과값이 영향을 줄 수 있는 상태

(즉 동시 접근 시 자료의 일관성을 해치는 결과가 나타남)

Race Condition이 발생하는 경우

• 커널 작업을 수행하는 중에 인터럽트 발생
  • 문제점: 커널모드에서 데이터를 로드하여 작업을 수행하다가 인터럽트가 발생하여 같은 데이터를 조작하는 경우
  • 해결법: 커널모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 한다.
• 프로세스가 System Call 을 하여 커널 모드로 진입하여 작업을 수행하는 도중 문맥 교환이 발생할 때
  • 문제점: 프로세스 1이 커널 모드에서 데이터를 조작하는 도중, 시간이 초과되어 CPU 제어권이 프로세스2로 넘어가 같은 데이터를 조작하는 경우(프로세스2가 작업에 반영되지 않음)
  • 해결법: 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되더라도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함
• 멀티 프로세스 환경에서 공유 메모리 내의 커널 데이터에 접근할 때
  • 문제점: 멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우
  • 해결법: 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 벙법(세마포어, 뮤텍스)

💿 세마포어(Semaphore) & 뮤텍스(Mutex)

세마포어: 멀티 프로그래밍 환경에서 공유 자원에 대한 접근을 제어한느 방법

뮤텍스: 임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술

공유된 자원에 여러 프로세스가 동시에 접근하면서 문제가 발생할 수 있다. 이 때 공유된 자원의 데이터는 한번에 하나의 프로세스만 접근할 수 있도록 제한을 둬야 한다.

차이점

• 세마포어
  • 공유 자원에 세마포어의 변수만큼의 프로세스가 접근할 수 있습니다.
  • 현재 수행중인 프로세스가 아닌 다른 프로세스가 세마포어를 해제할 수 있습니다.
• 뮤텍스
  • 오직 1개만의 프로세스만 접근할 수 있습니다.
  • 락(lock)을 획득한 프로세스가 반드시 그 락을 해제해야 합니다.

임계 구역(Critical Section)

여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분

공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 때문에, 한 프로세스가 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 한다.

🃏 세마포어

세마포어 P, V 연산

• P: 임계 구역에 들어가기 전에 수행(프로세스 진입 여부를 자원의 개수(S)를 통해 결정)
• V: 임계 구역에서 나올 때 수행(자원 반납 알림, 대기 중인 프로세스를 깨우는 신호)

구현

1
2
3
4
5

P(S);

// --- 임계 구역 ---

V(S);

1
2
3
4
5
6
7
8
9
10

procedure P(S)   --> 최초 S값은 1임
    while S=0 do wait  --> S가 0면 1이 될때까지 기다려야 함
    S := S-1   --> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함
end P

--- 임계 구역 ---

procedure V(S) --> 현재상태는 S가 0임
    S := S+1   --> S를 1로 원위치시켜 해제하는 과정
end V

이를 통해, 한 프로세스가 P 혹은 V를 수행하고 있는 동안 프로세스가 인터럽트 당하지 않게 된다. P와 V를 사용하여 임계 구역에 대한 상호배제 구현이 가능하게 되었다.

예시

최초 S 값은 1이고, 현재 해당 구역을 수행할 프로세스 A, B가 있다고 가정하자

1. 먼저 도착한 A가 P(S)를 실행하여 S를 0으로 만들고 임계구역에 들어감
2. 그 뒤에 도착한 B가 P(S)를 실행하지만 S가 0이므로 대기 상태
3. A가 임계구역 수행을 마치고 V(S)를 실행하면 S는 다시 1이 됨
4. B는 이제 P(S)에서 while문을 빠져나올 수 있고, 임계구역으로 들어가 수행함

🃏 뮤텍스

• lock: 현재 임계 구역에 들어갈 권한을 얻어옴(만약 다른 프로세스가 임계 구역 수행 중이면 종료할 때까지 대기)
• unlock: 현재 임계 구역을 모두 사용했음을 알림(대기 중인 프로세스에 진입할 수 있음)

뮤텍스는 상태가 0, 1로 이진 세마포어로 부르기도 함

뮤텍스 알고리즘

데커 알고리즘: flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스를 결정하는 방식

• flag: 프로세스 중 누가 임계 영역에 진입할 것인지 나타내는 변수
• turn: 누가 임계 구역에 들어갈 차례인지 나타내는 변수 j

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

while(true) {
    flag[i] = true;           // 프로세스 i가 임계 구역 진입 시도
    while(flag[j]) {          // 프로세스 j가 현재 임계 구역에 있는지 확인
        if(turn == j) {       // j가 임계 구역 사용 중이면
            flag[i] = false;  // 프로세스 i 진입 취소
            while(turn == j); // turn이 j에서 변경될 때까지 대기
            flag[i] = true;   // j turn이 끝나면 다시 진입 시도
        }
    }
}

// ------- 임계 구역 ---------

turn = j;         // 임계 구역 사용 끝나면 turn을 넘김
flag[i] = false;  // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

피터슨 알고리즘: 데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있음

1
2
3
4
5
6
7
8
9
10

while(true) {
    flag[i] = true;               // 프로세스 i가 임계 구역 진입 시도
    turn = j;                     // 다른 프로세스에게 진입 기회 양보
    while(flag[j] && turn == j) { // 다른 프로세스가 진입 시도하면 대기
    }
}

// ------- 임계 구역 ---------

flag[i] = false;    // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

제과점(Bakery) 알고리즘: 여러 프로세스/스레드에 대한 처리가 가능한 알고리즘. 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

while(true) {
    
    isReady[i] = true;                    // 번호표 받을 준비
    number[i] = max(number[0~n-1]) + 1;   // 현재 실행 중인 프로세스 중에 가장 큰 번호 배정 
    isReady[i] = false;                   // 번호표 수령 완료
    
    for(j = 0; j < n; j++) {              // 모든 프로세스 번호표 비교
        while(isReady[j]);                // 비교 프로세스가 번호표 받을 때까지 대기
        while(number[j] && number[j] < number[i] && j < i);
        
        // 프로세스 j가 번호표 가지고 있어야 함
        // 프로세스 j의 번호표 < 프로세스 i의 번호표
    }
}

// ------- 임계 구역 ---------

number[i] = 0; // 임계 구역 사용 종료