[운영체제] 공유자원과 임계영역/교착상태/CPU 스케줄링 알고리즘

2023년 4월 24일 172p~181p

 

3.3.7 공유 자원과 임계 영역

공유 자원은 시스템 안에서 각 프로세스, 스레드가 함께 접근할 수 있는 모니터, 프린터, 파일, 데이터 등의 자원이나 변수를 의미한다.

이 공유 자원을 두 개 이상의 프로세스가 동시에 읽거나 쓰는 상황을 경쟁 상태(Race Condition)라고 한다. 동시에 접근을 시도할 때 접근의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태인 것이다.

A와 B가 동시에 접근하여 타이밍이 꼬여 정상 결괏값은 300인데 200이 출력된다.

Race Condition이 발생하는 경우를 정리하면 다음과 같다.

- 커널 작업을 수행하는 중에 인터럽트 발생
문제점 : 커널모드에서 데이터를 로드하여 작업을 수행하다가 인터럽트가 발생하여 같은 데이터를 조작하는 경우
해결법 : 커널모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 함

- 프로세스가 'System Call'을 하여 커널 모드로 진입하여 작업을 수행하는 도중 문맥 교환이 발생할 때
문제점 : 프로세스1이 커널모드에서 데이터를 조작하는 도중, 시간이 초과되어 CPU 제어권이 프로세스2로 넘어가 같은 데이터를 조작하는 경우 ( 프로세스2가 작업에 반영되지 않음 )
해결법 : 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되어도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함

- 멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 때
문제점 : 멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우
해결법 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법

임계 영역은 둘 이상의 프로세스나 스레드가 공유 자원에 접근할 때 순서 등의 이유로 결과가 달라지는 코드 영역을 말한다.

임계 구역은 지정된 시간이 지난 후 종료된다. 때문에 어떤 스레드(태스크 또는 프로세스)가 임계 구역에 들어가고자 한다면 지정된 시간만큼 대기해야 한다. 임계 구역 문제란 임계 구역으로 지정되어야 할 코드 영역이 임계 구역으로 지정되지 않았을 때 발생할 수 있는 문제를 말한다.

위의 그림과 같이 공유 자원에 대하여 다수의 프로세스 혹은 스레드가 접근할 때 경쟁 조건이 발생하여 의도하지 않은 동작이 발생할 수 있다. 따라서 프로세스나 스레드를 동기화 (synchronization) 해야한다. 이때, 동기화란 공유 자원에 동시에 접근하지 못하도록 접근 순서를 제어하는 방법을 의미한다.

프로세스/스레드간 동기화는 일반적으로 상호 배제 (mutual exclusion)을 통해 구현할 수 있다. 자원에 접근하고나서 해당 자원을 잠그고, 자원을 다 사용하고 난뒤 잠금을 해제하는 방식이다.

동기화를 위한 상호배제 방법으로는 뮤텍스, 세마포어, 모니터가 있으며, 위 방법 모두 상호 배제, 한정 대기, 융통성이라는 조건을 만족한다. 이 방법에 토대가 되는 메커니즘은 잠금이다(ex. 화장실에 누가 들어가면 문을 잠그고 그 사람이 나오면 다른 사람이 쓰는 방식)

상호 배제 : 한 프로세스가 임계 영역에 들어갔을 때 다른 프로세스는 들어갈 수 없다.
한정 대기 : 특정 프로세스가 영원히 임계 영역에 들어가지 못해선 안된다.
융통성 : 한 프로세스가 다른 프로세스의 일을 방해해선 안된다.

- 뮤텍스

뮤텍스는 프로세스나 스레드가 공유 자원을 lock(), unlock() 하는 방식이다.
공유 자원이 사용 중일땐 lock(), 사용이 끝나면 unlock() 한다. 뮤텍스는 잠금 또는 잠금해제라는 상태만 가진다.

뮤택스는 프로그램이 시작될 때 고유한 이름으로 생성된다. 뮤텍스는 오직 하나의 스레드만이 동일한 시점에 뮤텍스를 얻어 임계 영역(Critical Section)에 들어올 수 있다. 그리고 오직 이 스레드만이 임계 영역에서 나갈 때 뮤텍스를 해제할 수 있다. 

탈의실이 하나밖에 없는 작은 옷가게의 탈의실을 생각하면 된다.

뮤텍스를 알고리즘을 통해 구현하면 다음과 같다.

1. 데커(Dekker) 알고리즘

flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식이다.

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

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로 바꿔 임계 구역 사용 완료를 알림

 

2. 피터슨(Peterson) 알고리즘

데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있다.

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

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

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

3. 제과점(Bakery) 알고리즘

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

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; // 임계 구역 사용 종료

 

- 세마포어

세마포어는 현재 공유자원에 접근할 수 있는 스레드, 프로세스의 수를 나타내는 값을 두어 상호배제를 달성하는 기법이다. 

세마포어는 정수값 하나를 가지고 있는데, 이는 공유자원에 접근할 수 있는 프로세스 혹은 스레드의 최대 허용치이다. 만약 이 정수값이 3이라면, 최대 3개의 프로세스가 공유 자원에 접근할 수 있는 것이다.

프로세스는 이 공유 자원에 접근하면, 정수값 하나를 줄인다. 공유 자원을 모두 사용하고 임계 구역에서 나온 프로세스는 다시 정수값을 하나 늘린다. 각각의 과정을 wait() (또는 P), signal() (또는 V) 라고 한다. 

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

구현 방법)

P(S);

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

V(S);

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문을 빠져나올 수 있고, 임계구역으로 들어가 수행함

프로세스가 공유 자원에 접근할 때는 wait() 함수를 실행한다. wait() 함수는 세마포어 정수의 값을 1 감소시킨다. 만약 감소된 세마포어 정수가 음수라면, 해당 프로세스는 세마포어 대기열에서 기다려야 한다. 세마포어의 카운트가 0보다 작거나 같아질 경우에 락이 실행된다.

프로세스가 공유 자원을 모두 사용하고 임계 구역에서 벗어날 때 signal() 함수를 실행한다. signal() 함수를 실행하면 세마포어 정수를 1 증가시키고, 세마포어 대기열에서 기다리고 있는 맨 앞의 프로세스 하나를 깨워 공유 자원을 허용케한다.

세마포어에서는 메서드 이름이 lock에서 wait로, unlock에서 signal로 바뀐다.

세마포어의 카운트가 0보다 작거나 같아져 동기화가 실행된 상황에, 다른 스레드가 signal 함수를 호출하면 세마포어의 카운트가 1 증가하고, 해당 스레드는 락에서 나올 수 있다.

세마포어에는 조건 변수가 없고 프로세스나 스레드가 세마포어 값을 수정할 때 다른 프로세스나 스레드는 동시에 세마포어 값을 수정할 수 없다.

이 세마포어 정수의 크기에 따라 바이너리 세마포어(binary semaphore)와 카운팅 세마포어(counting semaphore)로 구분된다.

단점) Busy Waiting(바쁜 대기)
Spin lock이라고 불리는 세마포어 초기 버전에서 임계영역에 진입해야하는 프로세스는 진입 코드를 계속 반복 실행해야 하며, CPU 시간을 낭비했었다. 이를 Busy Waiting이라고 부르며 특수한 상황이 아니면 비효율적이다.

일반적으로는 세마포어에서 임계영역에 진입을 시도했지만 실패한 프로세스에 대해 Block시킨 뒤, 임계영역에 자리가 날 때 다시 깨우는 방식을 사용한다. 이 경우 Busy waiting으로 인한 시간낭비 문제가 해결된다.

1. 바이너리 세마포어

바이너리 세마포어는 세마포어 정수를 0과 1로만 가질 수 있다. 바이너리 세마포어는 뮤텍스와 비슷하게 동작한다. 단, 뮤텍스는 잠금 메커니즘이고, 세마포어는 신호 기반의 상호 배제 방법이다(ex. 휴대폰에서 노래 듣다가 전화오면 노래 중지되고 통화 처리 작업에 관한 인터페이스가 등장하는 것).

• 0일 때 사용 불가능, 1 일 때 사용 가능

2. 카운팅 세마포어

카운팅 세마포어는 1보다 큰 세마포어 정수를 가질 수 있는 방식이며, 설정한 값만큼 스레드를 허용하고 그 이상의 스레드가 자원에 접근하면 락이 실행된다. 여러 자원에 대한 접근을 제어하는데 사용한다.

* 뮤텍스 vs 세마포어?

뮤텍스도 임계 구역에 동시 진입을 허용할 프로세스가 1개이기 때문에 이진 세마포어와 동일하다 생각할 수 있지만 그렇지 않다. 뮤텍스의 경우, 락을 취득한 프로세스만이 언락을 할 수 있다는 점이 다르다. 따라서 뮤텍스를 통해 임계 구역에 진입한 프로세스가 비정상적으로 종료되거나 무한 루프에 빠진다면 같은 락을 바라보고 임계 구역에 진입하려고 시도하고 있던 프로세스는 영원히 진입할 수 없게 된다. 반면, 세마포어는 락의 동시 접근만을 제어할 뿐 언락을 시도하는 프로세스가 락을 취득했던 프로세스인지는 확인하지는 않는다. 이에 따라, 락을 취득했던 프로세스가 락을 해제하지 않은 채 비정상 종료가 되었다고 하더라도, 세마포어에서는 다른 프로세스가 대신 언락을 하여 무한히 대기하는 상황을 회피할 수 있다.

• Mutex는 동기화 대상이 오직 1개일 때 사용하며, Semaphore는 동기화 대상이 1개 이상일 때 사용
• Mutex는 자원을 소유할 수 있고 책임을 가지는 반면, Semaphore는 자원 소유 불가
• Semaphore는 시스템 범위에 걸쳐 있고, 파일 시스템 상의 파일로 존재하는 반면, Mutex는 프로세스의 범위를 가지며 프로세스 종료될 때 자동으로 Clean up됨

https://heeonii.tistory.com/14

[운영체제] Mutex 뮤텍스와 Semaphore 세마포어의 차이

- 모니터

세마포어를 사용하기 위해서는 임계 구역에 명시적으로 상호 배제 로직을 구현해야 한다.

모니터는 이 상호 배제 로직을 추상화하고, 공유 자원 접근에 대한 인터페이스만을 제공한다. 또한 공유 자원도 외부로부터 캡슐화하여 숨긴다. 세마포어에 비해 좀 더 고수준이라고 할 수 있다. 따라서 모니터를 사용하면 상호 배제를 세마포어에 비해 구현하기 쉬우며 실수가 줄어든다. 모니터는 주로 고급 프로그래밍 언어에서 제공하는 방식이다. 

https://hudi.blog/race-condition-critical-section-mutual-exclusion/

공유 자원에 접근하고자 하는 프로세스/스레드는 모니터 안으로 들어가야한다. 모니터는 모니터큐에 작업을 순차적으로 쌓아두고, 한번에 한 프로세스/스레드만 임계 영역에 접근할 수 있도록 한다. 즉, 한번에 하나의 프로세스만 모니터에서 활동할 수 있도록 보장한다. 개념적으로는 바이너리 세마포어의 기능을 제공하는 것이다.

https://hudi.blog/race-condition-critical-section-mutual-exclusion/

경쟁상태, 임계영역의 개념과 동기화를 위한 여러 상호배제 기법 (mutex, semaphore, monitor)

 

3.3.8 교착 상태

교착 상태(deadlock)은 두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며 중단된 상태를 이야기한다(마치, 외나무 다리의 양 끝에서 서로가 비켜주기를 기다리고만 있는 것과 같다).

예를 들어 프로세스 A가 프로세스 B의 어떤 자원을 요청할 때, 프로세스 B도 프로세스 A가 점유하고 있는 자원을 요청한다.

프로세스1과 2가 자원1, 2를 모두 얻어야 한다고 가정해보자.

• t1 : 프로세스1이 자원1을 얻음 / 프로세스2가 자원2를 얻음
• t2 : 프로세스1은 자원2를 기다림 / 프로세스2는 자원1을 기다림

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

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

* 기아상태(starvation)과 식사하는 철학자 문제

5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다.

1. 일정 시간 생각을 한다.
2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번으로 돌아간다.

만약 모든 철학자들이 동시에 자신의 왼쪽 포크를 잡는다면, 모든 철학자들이 자기 오른쪽의 포크가 사용 가능해질 때까지 기다려야 한다. 현재 모든 철학자들이 자신의 왼쪽 포크를 집은 상태에서 오른쪽 포크를 기다리고 있으므로 이 상태에서는 모든 철학자가 영원히 3번 상태에 머물러있어 아무것도 진행할 수가 없게 되는데, 이것이 교착(Deadlock)상태이다.

<식사하는 철학자 문제 상황 정리>
초기 상태: 사람 5명, 젓가락 5개

실행 과정: 5명의 사람이 순차적으로 사용하지 않은 젓가락을 1개씩 집으면서 2개의 쌍을 맞춘다. 그리고 밥을 먹은 후 젓가락을 내려 놓는다. 이 과정을 무수히 빠르게 진행한다.

문제 발생 시점: 5명의 사람 모두 젓가락을 1개씩 집은 상황에서 젓가락 5개를 모두 사용했지만 5명 누구도 식사를 하지 못한다. 여기서 젓가락을 나눠주지도 못하므로 5명이 젓가락 1개씩 들고 하루 종일 밥만 구경하는 교착(Deadlock)상태에 걸려 무한히 대기한다. 이렇게 한번 교착상태에 빠진 철학자들은 계속 고뇌만 하다가 기아현상(Starvation)으로 굶어 죽는다.

교착 상태 해결책은 다음과 같다.

1. n명이 앉을 수 있는 테이블에서 철학자를 n-1명만 앉힘
2. 젓가락 갯수 6개로 늘려 한 사람이라도 식사하게 하기. 그 사람 끝나면 다음 사람 식사하기(이 과정 반복).
3. 한 철학자가 젓가락 두 개를 모두 집을 수 있는 상황에서만 젓가락 집도록 허용 <- 모니터 사용하여 해결
   철학자가 EATING상태가 되기 위해서 자신이 HUNGRY상태이고, 자신의 왼쪽, 오른쪽 모두 EATING상태가 아니어야 한다.
   - HUNGRY: 철학자가 젓가락 집기를 원함 (임계구역 접근을 원함)
   - THINKING: 철학자가 젓가락 집기를 원치 않음 (임계구역 접근을 원치 않음)
   - EATING: 철학자가 2개의 젓가락을 집어 밥을 먹음 (임계구역에 접근함)
4. 누군가는 왼쪽 젓가락을 먼저 집지 않고 오른쪽 젓가락을 먼저 집도록 허용(철학자 위치 구분(홀짝) -> 환형대기 해결)

그러나 식사하는 철학자들의 문제에 대한 만족할 만한 해결안들은 반드시 철학자 중 어느 하나가 굶어 죽을 가능성이 생기지 않도록 방지해야 한다는 것을 주의해야 한다. 교착상태가 없는 해결안이 반드시 기아의 가능성도 제거하는 것은 아니다.

 

1) 발생 조건(아래의 4가지 조건이 모두 만족되는 경우(필요충분 조건)에 발생할 가능성이 있으며, 하나라도 만족하지 않으면 교착상태가 발생하지 않음)

• 상호 배제 : 한 프로세스가 자원을 독접하고 있으며 다른 프로세스들은 접근 불가능
• 점유 대기 : 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유 자원을 놓지 않고 계속 가지고 있음. 즉, 자발적으로도 자원을 놓아주지 않아야 함.
• 비선점 : 프로세스는 자원을 스스로 내어놓을 뿐, 강제로 빼앗기지 않음.
• 환형 대기 : 프로세스 A는 프로세스 B의 자원을 요구하고, 프로세스 B는 프로세스 A의 자원을 요구하는 등 서로가 서로의 자원을 요구하는 상황. 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 원형을 이루면서 대기하는 조건. 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있음

2) 해결 방법

-  예방(Prevention)

교착상태 예방 방법은 교착상태가 애초에 일어나지 않도록 방지하는 방법으로 교착상태의 발생조건 4가지 중 하나를 부정함으로써 교착상태를 예방하는 방법이다.

1. 상호 배제 부정
   여러 개의 프로세스가 동시에 공유자원을 사용할 수 있음
2. 점유 대기 부정
   프로세스가 실행되기 전에 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나, 자원이 점유되지 않은 상태에서만 자원 요청을 받도록 함
3. 비선점 부정
   모든 자원에 대한 선점을 허용
4. 순환 대기 부정
   자원을 선형으로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유번호보다 앞이나 뒤 한쪽 방향으로만 자원을 요구하도록 함

그러나 이렇게 교착상태 발생조건을 방지해서 데드락을 예방하는 방법은 시스템 처리량이나 자원 사용의 효율성을 떨어트리는 단점이 있다.

-  회피(Avoidance)

교착상태가 발생할 가능성이 있는 자원 할당(Unsafe allocation)을 하지 않고 안전한 상태(Safe state)에서만 자원 요청을 허용하는 방법이다. 하지만 교착상태 회피를 하기 위해서는 아래와 같은 가정이 필요하다.

• 프로세스 수 고정
• 자원의 종류와 수 고정
• 프로세스가 요구하는 최대 자원의 수를 알아야 함
• 프로세스는 자원 사용 후 반드시 반납

Safe state : safe sequence(교착상태를 발생시키지 않고 자원을 할당하는 순서)가 존재하며 모든 프로세스가 정상적으로 종료될 수 있는 상태를 의미
Unsafe state : 교착상태가 발생할 가능성이 있는 상태

교착상태를 회피하기 위한 알고리즘으로 크게 두 가지가 있다. 

1. 은행원 알고리즘(Banker's Algorithm)

다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구를 충족할 수 있도록 현금을 대출해주는 것에서 유래하였다. 은행원 알고리즘은 자원 할당 결정 전에 예상되는 모든 자원의 최대 할당량을 가지고 시뮬레이션을 하여 safe state에 들 수 있는지 여부를 검사하여 교착상태의 가능성을 미리 조사하는 알고리즘이다.

기본 개념 자체는 "CPU는 최소한 하나의 프로세스에게 할당해줄 만큼의 자원을 항상 보유하고 있어야 한다" 이다.

예시를 통해 이해해보자. 시스템은 총 12개의 자원을 가지고 있다고 가정한다.

(t=t0)	최대 자원 요청량	할당중인 자원량	남은 필요한 자원의 양
P0	10	5	5
P1	4	2	2
P2	9	2	7

현재 할당 중인 자원량의 합 은 5+2+2 = 9 이다. 시스템은 총 12개의 자원을 가지고 있으므로 현재 상태에서 가용 자원량은 12 - 9 = 3 이 된다. 

여기서 가용 자원을 어느 프로세스에게 할당해주느냐에 따라 자원을 효율적으로 이용할 수 있게 된다.

• 남은 가용자원 3개를 P1에게 할당 => 가용자원은 3 - 2 = 1
• P1의 작업이 끝나고 할당되어 있던 자원  4개 반납 => 가용자원은 1 + 4 = 5
• 남은 가용자원 5개를 P0에게 할당 => 가용자원은 5 - 5 = 0
• P0의 작업이 끝나고 할당되어 있던 자원 10개 반납 => 가용자원은 0 + 10 = 10
• 남은 가용자원 10개 중 7개를 P2에게 할당 => 가용자원은 10 - 7 = 3
• P2의 작업이 끝나고 할당되어 있던 자원 9개 반납 => 가용자원은 3 + 9 = 12

이렇게 P1 - P0 - P2 순서로 자원을 할당하면 Safe sequence를 만족하게 된다. 

그러나 은행원 알고리즘의 경우 미리 자원의 최대 요구량을 알아야 하고, 할당할 수 있는 자원의 수가 일정해야 하는 등 사용에 제약조건이 많다.

이처럼 교착상태 회피 방법의 가장 큰 문제는 문제 발생에 대한 일관성과 가정이 완벽할 것이라는 것을 보장하기가 현실적으로 어렵다는 점이다. 시스템의 규모가 작은 운영체제라면 고려해볼 만한 방법이지만, 멀티 리소스, 멀티 프로세스의 복잡한 운영체제 환경에서는 자원 할당 그래프를 분석하면서 Safe state를 파악하기가 상당히 어렵다.

2. 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)

자원 할당 그래프에 요청 간선과 할당 간선에 추가하여, 예약간선이라는 새로운 유형의 간선을 도입한다.

요청선 : 프로세스에서 자원으로 연결 된 선 (나 저 자원 쓰고 싶다~)
할당선 : 자원에서 프로세스로 연결 된 선 (이 자원은 이 프로세스가 쓰고 있음)

* 교착상태 확인 방법

1. 자원할당 그래프의 사이클이 존재하는 지 확인

2. 사이클이 존재한다면

• 만약 자원당 인스턴스가 하나밖에 없다면 사이클은 데드락 걸림.
• 만약 자원당 인스턴스가 여러개 있는 상항이면, 데드락일 수도 아닐 수도 있음.

교착상태가 있는 자원할당 그래프 예시)

사이클이 두개가 만들어졌으므로, 자원 두개가 있음에도 불구하고 진행이 불가능한 상황이 된다.

사이클은 있지만 교착상태가 아닌 자원 할당 그래프 예시)

 

프로세스 p1이 작업을 완료하고 R3의 자원을 반환하면 p3은 p1이 반환한 자원을 할당 받으면 된다.

-  탐지(Detection)

말 그대로 시스템에 교착상태가 발생했는지에 대한 여부를 탐색하고 회복 기법 알고리즘에 활용하는 것을 의미한다. 교착상태가 탐지되었다면 회복 기법을 통해 교착상태를 복구한다.

그러나 탐지 기법은 지속적으로 교착상태를 확인하는 작업이 필요하기 때문에 오버헤드(성능 저하)가 발생하게 된다.

-  회복(Recovery)

교착상태 회복 기법은 교착상태가 발생했을 때 해결하는 기법을 의미한다.

1) 사용자 처리

교착상태에 있는 프로세스 중 하나의 프로세스를 사용자가 강제 종료

2) 시스템 처리

1. 프로세스 중지 
   • 교착상태에 속해있는 모든 프로세스를 중지
   • 교착상태가 해결될 때까지 한 프로세스씩 중지
2. 자원 선점
   • 프로세스들로부터 자원을 빼앗아 교착상태가 해결될 때까지 다른 프로세스들에게 자원을 할당
     

- 무시

Deadlock을 시스템이 책임지지 않는다. 문제가 생긴다면, 사용자가 작업을 종료하는 등의 방법으로 이를 해결한다.
UNIX를 포함한 대부분의 OS가 채택하였다. Deadlock은 빈번하게 발생하는 이벤트가 아니기 때문에 사용할 수 있는 방법으로, 오히려 미리 방지하는게 오버헤드가 더 크다.

https://cocoon1787.tistory.com/858

[OS] 교착상태(Deadlock, 데드락)의 정의, 발생 조건, 해결 방법

https://vansoft1215.tistory.com/177

[문과 코린이의 IT 기록장] 운영체제(OS) - Deadlock(교착상태) (The Deadlock Problem, Deadlock 발생의 4가지

---

3.4 CPU 스케줄링 알고리즘

CPU를 효율적으로 사용하기 위해 프로세스들을 잘 배정해야 한다. CPU 스케줄링 알고리즘은 준비 큐에 있는 프로세스를 CPU에게 할당하는 순서와 방식을 결정한다.

버스트(burst)란 특정 기준에 따라 한 단위로서 취급되는 연속된 신호나 데이터의 모임을 말한다. 즉, 입출력 요청을 위해 CPU를 사용했다가 쉬었다가를 반복한다.

프로세스가 CPU를 사용할때를 CPU 버스트, 입/출력을 기다릴때를 입/출력 버스트라고 한다.

프로세스의 실행은 CPU 버스트를 시작으로 뒤이어 입출력 버스트가 발생하는 식으로 두 버스트의 사이클로 구성된다. 마지막 CPU버스트는 또 다른 입출력 버스트가 뒤따르는 대신에 실행을 종료하기 위한 시스템 요청과 함께 끝난다.

입출력 중심의 프로그램은 CPU 버스트 시간이 짧을 것이다. 반대로 CPU 지향 프로그램은 CPU 버스트 시간이 길 것이다. 이러한 분포는 적절한 CPU 스케줄링 알고리즘을 선택하는데 매우 중요할 수 있다.

CPU 스케줄링은 다음과 같은 4가지 상황에서만 생긴다.

- 프로세스가 종료(terminates)될때
- 프로세스가 실행상태(running)에서 대기상태(waiting)로 전환될 때(예를 들어 입출력 요청이나 자식 프로세스가 종료되기를 기다리기 위해 wait를 호출할때)
- 프로세스가 실행상태(running)에서 준비완료상태(ready)로 전환 될 때(예를 들어 인터럽트가 발생했거나 시간이 다 된경우, time slice 만료. 더 큰 우선순위가 들어올 경우)
- 프로세스가 대기상태(waiting)에서 준비완료상태(ready)로 전환 될때(예를 들어 입출력의 종료시)

서로 다른 CPU 스케줄링 알고리즘들은 다른 특성을 가지고 있으며 서로 다른 특성을 반드시 고려해야 한다. 이를 비교하기 위한 여러 기준이 제시되어있는데 아래와 같다.

- CPU 이용률 : 가능한 CPU를 바쁘게 이용해야 좋은 스케줄링이라고 할 수 있음
- 처리량(throughput) : 작업량 측정. 단위시간당 완료된 프로세스의 개수로 계산. 클수록 좋음
- 총 처리시간(turnaround time) : 반환시간, 소요시간이라고도 함. 프로세스가 메모리에 들어가기 위해 기다리며 소비한 시간 부터 프로세스가 종료되는 시간까지. 짧을수록 좋음
- 대기시간(waiting time) : 준비완료 큐에서 대기하면서 보낸 시간의 합
- 응답시간(response time) : 하나의 요구를 제출한 후 첫 번째 응답이 나올때까지의 시간. 응답이 시작되는데까지 걸리는 시간이지 그 응답을 출력하는데 걸리는 시간은 아님

CPU 스케줄링 알고리즘의 종류는 다음과 같다.

1. 비선점

비선점 방식은 프로세스가 자율적으로 반납할 때까지 CPU를 선점하는 방식이다. 프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않는다. 따라서, 컨텍스트 스위칭으로 인한 부하가 적다.

- FCFS

FCFS(First Come Fisrt Sserved)는 가장 먼저 온 것을 가장 먼저 처리한다.

장점 : 

• 스케줄링이 단순
• 모든 프로세스가 실행될 수 있음
• 프로세서가 지속적으로 유용한 프로세스를 수행하여 처리율이 높음

문제점 : 

• 길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리는 현상(convoy effect)이 발생-> p1이 오래걸리면 p4가 오래 기다리게 됨

- SJF

SJF(Short Job First)는 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행한다. 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용한다. 

실행 시간이 짧은 p4부터 실행한다.

장점 : 항상 짧은 작업을 먼저 처리하게 되니까 평균 대기시간이 가장 짧음

문제점 : 

• 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)
• 실행 시간을 예측할 수 없어 실용적이지 못함
• 짧은 작업이 먼저 실행되므로 공정하지 못한 정책

* convoy effect와 starvation의 차이?
- convoy effect는 시간이 오래 걸리는 프로세스로 인해 전체 OS가 느려지는 FCFS 알고리즘과 관련된 현상이다. (예를 들어, P1이 100, P2가 5 정도의 시간이 걸린다고 할때 P2는 적어도 100의 시간을 기다려야 한다.)
- starvation(기아)는 프로세스가 '무기한으로' 대기할 때 발생한다. 우선순위가 자꾸 밀려서 해당 프로세스가 아예 실행이 안되는 것이다.

- 우선순위

기존 SJF에서는 긴 시간을 가진 프로세스가 실행되지 않는 현상이 있었다. 이를 오래된 작업일 수록 우선순위를 높이는 방법(aging)을 통해 해결할 수 있다.

우선순위가 가장 높은 프로세스에게 CPU 를 할당하는 스케줄링이다. 우선순위는 정수로 표현되고, 숫자가 높을 수록 우선순위가 높고 만약 우선순위가 같다면 FIFO방식으로 동작한다.

• 선점형 스케줄링(Preemptive) 방식
  더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다.
• 비선점형 스케줄링(Non-Preemptive) 방식
  더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다.

장점 :

• 각 프로세스의 중요성에 따라서 작업을 수행하기 때문에 합리적
• 실시간 시스템에서 사용 가능

문제점 : 

• starvation
• 무기한 봉쇄(Indefinite blocking)
  실행 준비는 되어있으나 CPU 를 사용 못하는 프로세스를 CPU 가 무기한 대기하는 상태

해결책 : 

• aging
  아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주자.

2. 선점

선점 방식은 현재 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜버리고 강제로 다른 프로세스에게 CPU 소유권을 할당하는 방식이다.

- RR

현대 컴퓨터가 쓰는 스케줄링 방법이며 단순한 선점형 알고리즘이다. 

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다.
• 할당 시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다.
• RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적이다.
• RR이 가능한 이유는 프로세스의 context 를 save 할 수 있기 때문이다.

이 알고리즘은 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰인다.

장점 : 

• 모든 프로세스가 공정하게 스케줄링을 받을 수 있음. n 개의 프로세스가 ready queue 에 있고 할당시간이 q(time quantum)인 경우, 각 프로세스는 q 단위로 CPU 시간의 1/n 을 얻음. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않음.
• 실행 큐의 프로세스의 수를 알고 있을때 유용
• 평균 대기시간이 FIFO와 SJF보다 적음
• 프로세스가 기다리는 시간이 CPU 를 사용할 만큼 증가 -> 공정한 스케줄링

문제점:

• 설정한 time quantum이 너무 커지면 FCFS와 같아짐. 또 너무 작아지면 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 context switch 로 overhead 가 발생. 그렇기 때문에 적당한 time quantum을 설정하는 것이 중요!
• 하드웨어적 타이머가 필요
• 미완성 작업은 규정 시간량(시간 할당량)을 마친 후 프로세서를 기다리니까 평균 처리 시간이 높음

- SRT(SJF와 유사)

SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 짧은 작업을 끝까지 수행하고 그다음 짧은 작업을 이어나가는데, SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행한다. 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time(CPU가 일을 수행하는 시간) 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다.

문제점 :

• starvation
• 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수가 없음

- 다단계 큐

다단계 큐는 우선순위에 따른 준비 큐를 여러 개 사용하고, 큐 마다 RR, FCFS 등 다른 스케줄링 알고리즘을 적용한 것을 말한다.

작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용한다.

우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정 해주는 방식을 사용한다. 우선순위가 높은 큐는 작은 Time Quantum을 할당하고, 우선순위가 낮은 큐는 큰 Time Quantum을 할당한다.

문제점 :

• 큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어짐
• 우선순위가 높은 큐부터 처리되기 때문에 낮은 큐의 프로세스가 처리가 안되는 기아현상(starvation)이 발생할 수도 있음

- Multilevel-Feedback-Queue (다단계 피드백 큐)

다단계 큐에서 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동한다. 이 그림은 8안에 끝나는 프로세스는 맨위에 놓여 실행되며, 8안에 끝나지 못하는 프로세스는 밑으로 내려가는 식이다.

짧은 작업에 유리하며, 입출력 위주(Interrupt가 잦은) 작업에 우선권을 준다.

장점 : 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 처리시간 평균을 줄여준다.