기본미션📣
12-2 확인문제 1번 | ④ 반드시 바쁜 대기를 하지 않아도 되기 때문에
선택미션📣
임계 구역, 상호 배제 개념 정리 | 임계 구역은 공유 자원에 접근하는 코드 중에서 동시에 실행하면 문제가 발생하는 코드 영역을 말하고, 상호 배제는 공유가 불가능한 자원의 동시 사용을 막기 위한 알고리즘이다.
12-1 동기화란
동기화의 의미
동시다발적으로 실행되는 프로세스들은 공동의 목적을 올바르게 수행하기 위해 서로 데이터를 주고받으며 협력하며 실행되기도 한다. 이렇게 협력적으로 실행되는 프로세스들은 아무렇게나 마구 동시에 실행되서는 안되기 때문에 동기화가 필수이다.
프로세스 동기화란 프로세스들 사이의 수행 시기를 맞추는 것을 의미하는데, 실행 순서를 제어하여 프로세스를 올바른 순서대로 실행하게 하는 역할을 하고, 상호 배제로 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하는 역할도 한다.
즉, 동기화에는 실행 순서 제어를 위한 동기화가 있고, 상호 배제를 위한 동기화도 있다.
실행 순서 제어를 위한 동기화
예를 들어 A 프로세스, B 프로세스가 있을 때 A는 파일에 데이터를 저장하는 역할을 하고 B는 저장한 데이터를 파일에서 읽어들이는 역할을 한다. 그러면 이때 B는 무조건 A의 실행이 끝나야 실행이 된다. '파일 안에 데이터값이 존재한다'는 조건이 있어야 실행될 수 있는 것이다.
만약 B가 먼저 실행된다면 올바른 실행 순서가 아니다. 이렇게 특정 조건이 만족되어야 실행이 되어 올바른 순서대로 실행하게 만드는 것이 첫 번째 프로세스 동기화이다.
상호 배제를 위한 동기화
상호 배제는 공유가 불가능한 자원의 동시 사용을 막기 위해 사용하는 알고리즘이다.
또 예를 들어보자면 계좌에 2만 원을 넣는 A 프로세스가 있고, 5만 원을 넣는 B 프로세스가 있다고 했을 때 동기화가 제대로 이루어지지 않는다면 아래와 같은 상황이 발생한다. 
이러한 결과가 나오는 까닭은 A와 B가 '잔액'이라는 데이터를 동시에 사용하는데, A가 끝나기도 전에 B가 잔액을 읽어버렸기 때문이다. A와 B가 올바르게 실행되기 위해서는 한 프로세스가 잔액에 접근했을 때 다른 프로세스가 기다려야 한다.
공유 자원과 임계 구역
공유 자원은 계좌 잔액 문제에서 프로세스들이 사용한 전역 변수인 '잔액'과 같은 공동의 자원을 말한다. 공유 자원은 전역 변수가 될 수도 있고, 파일이 될 수도 있고, 입출력장치, 보조기억장치가 될 수도 있다.
그리고 이 공유 자원 중에는 두 개 이상의 프로세스를 동시에 실행하면 문제가 발생하는 자원이 있는데, 이 자원에 접근하는 코드 영역을 임계 구역이라고 한다. 이 임계 구역에는 두 개 이상의 프로세스가 진입하고자 하면 둘 중 하나는 대기를 해야 한다. 그러고 먼저 진입한 프로세스가 마무리되면 임계 구역에 들어갈 수 있다.
이렇게 임계 구역은 두 개 이상의 프로세스가 동시에 실행되면 안 되는 영역이지만, 잘못된 실행으로 인해 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 문제가 발생하는 경우가 있는데, 이를 레이스 컨디션이라고 한다. 레이스 컨디션이 발생하면 데이터의 일관성이 깨지게 된다.
운영체제는 이런 문제를 발생시키지 않기 위해 다음에 세가지 원칙을 지키며 임계 구역을 관리한다.
1 ) 상호배제 : 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다. 2 ) 진행 : 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
3 ) 유한 대기 : 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가는 임계 구역에 들어올 수 있어야 한다. ( 임계 구역에 들어오기 위해 무한정 대기해서는 안 된다. )
12-2 동기화 기법
뮤텍스 락
프로세스는 임계 구역에 프로세스가 있다면 그 프로세스가 작업이 끝날 때까지 기다렸다가 임계 구역에 진입을 하게 되는데, 임계 구역 안에 이미 다른 프로세스가 있다는 것을 알려주는 도구가 바로 뮤텍스 락이다.
임계 구역에 진입하는 프로세스는 '내가 지금 임계 구역에 있음'을 알리기 위해 뮤텍스 락을 이용해 임계 구역에 자물쇠를 걸어둘 수 있고, 다른 프로세스는 임계 구역이 잠겨 있다면 기다리고 잠겨 있지 않다면 임계 구역에 진입하는 형식이다.
뮤텍스 락의 매우 단순한 형태는 하나의 전역 변수와 두 개의 함수로 구현할 수 있다.
- 자물쇠 역할 : 프로세스들이 공유하는 전역 변수 lock
- 임계 구역을 잠그는 역할 : acquire 함수
- 임계 구역의 잠금을 해제하는 역할 : release 함수
acquire() {
while (lock == true) // 만약 임계 구역이 잠겨 있다면
; // 임계 구역이 잠겨 있는지를 반복적으로 확인
lock = true // 만약 임계 구역이 잠겨 있지 않다면 임계 구역 잠금
}
release() {
lock = false; // 임계 구역 작업이 끝났으니 잠금 해제
}acquire 함수는 프로세스가 임계 구역에 진입하기 전에 호출하는 함수로, 임계 구역이 잠겨있을 때는 임계 구역이 열릴 때까지(lock이 false가 될 때까지) 임계 구역을 반복적으로 확인하고, 임계 구역이 열려 있을 때는 임계 구역을 잠그는(lock을 true로 바꾸는) 함수이다.
release 함수는 임계 구역에서의 작업이 끝나고 호출하는 함수로, 현재 잠긴 임계 구역을 열어주는(lock을 false로 바꾸는) 함수이다.
이렇게 프로세스는 임계 구역에 진입할 수 없다면 무작정 기다리고, 임계 구역에 진입할 수 있다면 임계 구역을 잠근 뒤 임계 구역에서의 작업을 진행하고, 임계 구역에서 빠져나올 때엔 다시 임계 구역의 잠금을 해제함으로써 임계구역을 보호한다. 이러한 대기 방식을 바쁜 대기라고 한다.
세마포 ( 카운팅 세마포 )
세마포는 뮤텍스 락과 비슷하지만, 조금 더 일반화된 방식의 동기화 도구이다.
뮤텍스 락은 하나의 공유 자원에 접근하는 프로세스를 상정하는 방식이라면 세마포는 공유 자원이 여러 개 있을 경우를 상정한 방식이다. 예를 들어 한 번에 하나의 프로세스만 이용할 수 있는 프린터 세 대가 있을 때, 하나의 프린터에 사용할 수 있는 프로세스는 하나이지만, 총 세 개의 프로세스가 공유 자원(프린터)을 각각 이용할 수 있는 것이다.
세마포도 뮤텍스 락과 비슷하게 하나의 변수와 두 개의 함수로 단순하게 구현할 수 있다.
- 임계 구역에 진입할 수 있는 프로세스의 개수를 나타내는 전역 변수 S
- 임계 구역에 들어가도 좋은지, 기다려야 할지를 알려주는 wait 함수
- 임계 구역 앞에서 기다리는 프로세스에 '이제 가도 좋다'고 신호를 주는 signal 함수
wait() {
while ( S <= 0 ) // 만일 임계 구역에 진입할 수 잇는 프로세스 개수가 0이하라면
; // 사용할 수 있는 자원이 있는지 반복적으로 확인하고,
S--; // 임계 구역에 진입할 수 있는 프로세스 개수가 하나 이상이면
// S를 1 감소시키고 임계 구역에 진입.
}
signal() {
S++; // 임계 구역에서의 작업을 마친 뒤 S를 1 증가시킨다.
}여기서 문제가 있다. 뮤텍스 락도 해당되는 문제인데, 사용할 수 있는 공유 자원이 없는 경우 프로세스는 무작정 무한히 반복하며 S를 확인해야 한다. 이렇게 바쁜 대기를 반복하며 확인할 시간에 CPU는 더 생산성 있는 작업을 할 수 있을 텐데, CPU 주기를 낭비한다는 점에서 손해이다.
그래서 실제로 세마포는 더 좋은 방법을 사용하는데, 지금 당장 사용할 수 있는 자원이 없을 경우 wait 함수는 해당 프로세스 상태를 대기 상태로 만들고, 그 프로세스의 PCB를 세마포를 위한 대기 큐에 집어넣는다. 그 후 다른 프로세스가 임계 구역에서의 작업이 끝나고 signal 함수를 호출하면 signal 함수는 대기 중인 프로세스를 대기 큐에서 제거하고, 프로세스 상태를 준비 상태로 변경한 뒤 준비 큐로 옮긴다. 그 후 실행이 되는 구조이다.
wait() {
S--;
if ( S < 0 ) {
add this process to Queue; // 해당 프로세스 PCB를 대기 큐에 삽입
sleep(); // 대기 상태로 접어든다.
}
}
signal() {
S++;
if ( S <= 0 ) {
remove a process p from Queue; // 대기 큐에 있는 프로세스 p를 제거
wakeup(p); // 프로세스 p를 대기 상태에서 준비 상태로 만든다.
}
}모니터
모니터는 세마포를 사용할 때 번거롭거나 불편했던 점들을 해결하기 위해 나온 도구로, 공유 자원과 공유 자원에 접근하기 위한 인터페이스(통로)를 묶어 관리하여 프로세스가 공유 자원에 접근할 때는 반드시 인터페이스를 통해서만 접근하도록 한다.
이를 위해 모니터는 공유 자원을 다루는 인터페이스에 접근하기 위한 큐(모니터에 진입하기 위한 큐)를 만들고, 모니터 안에 항상 하나의 프로세스만 들어오도록 하여 상호 배제를 위한 동기화를 제공한다.
이 밖에도 모니터는 실행 순서 제어를 위한 동기화도 제공하는데, 이를 위해 조건 변수를 사용한다. 조건 변수는 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수이다.
실행 순서 제어를 위한 동기화를 하기 위해서는 먼저 wait가 호출한 프로세스의 상태를 대기 상태로 전환하고 일시적으로 조건 변수에 대한 대기 큐에 삽입하는 연산을 하는데, 여기서 삽입되는 큐는 모니터에 진입하기 위한 큐(상호 배제를 위한 큐)와 다르다. 모니터에 이미 진입한 프로세스의 실행 조건이 만족될 때까지 잠시 실행이 중단되어 기다리기 위해 만들어진 큐이기 때문이다.
wait 연산으로 일시 중지된 프로세스는 다른 프로세스의 signal 연산을 통해 실행이 재개되는데, 그러면 조건 변수 x에 대해 대기 상태에 있던 프로세스가 깨어나 모니터 안으로 다시 들어오게 된다. 하지만 모니터 안에는 하나의 프로세스만이 있을 수 있으므로 signal을 호출한 프로세스가 모니터를 떠난 뒤에 실행이 되거나, signal을 호출한 프로세스의 실행을 일시 중단하고 자신이 실행된 뒤 일시 중단한 프로세스의 수행을 재개하기도 한다.
13-1 교착 상태란
교착 상태란 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 말한다.
예를 들자면 게임 프로세스가 자원 A를 점유한 채 웹 브라우저 프로세스가 점유하고 있는 자원 B의 사용이 끝나길 기다리고, 웹 브라우저 프로세스는 자원 B를 점유한 채 게임 프로세스의 자원 A 사용이 끝나길 기다리고 있는 것이다. 이 경우 게임과 웹 브라우저 프로세스는 상대방이 가진 자원을 기다리기만 하다가 결국 실행 한 번 못하는 상황이 벌어지는데, 이것이 교착 상태이다.
교착 상태에 제일 유명한 예로는 '식사하는 철학자 문제'도 있다.
교착 상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있는데, 이 그래프는 어떤 프로세스가 어떤 자원을 사용하고, 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현한 간단한 그래프이다.
자원 할당 그래프에는 규칙이 있는데, 프로세스는 원으로, 자원의 종류는 사각형으로 표현된다.
또한 같은 자원이라 할지라도 사용 가능한 자원의 개수는 여러 개 있을 수 있으므로 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현한다. 그리고 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다. 또 프로세스가 어떤 자원을 기다리고 있을 때는 프로세스에서 자원으로 화살표를 표시한다.
유명한 '식사하는 철학자 문제'도 이 규칙에 따라 자원 할당 그래프로 나타내보면 다음과 같다.
이와 마찬가지로 교착 상태가 발생한 상황에 자원 할당 그래프를 보면 모두 원에 형태를 띄고 있는데, 이것은 아래에서 나올 교착 상태 발생 조건인 원형 대기를 만족했기 때문이다.
교착 상태 발생 조건
교착 상태의 근본적인 원인을 더 알아보자면, 교착 상태가 발생할 조건에는 총 네 가지가 있는데, 상호 배제, 점유와 대기, 비선점, 원형 대기이다. 이 조건들이 모두 만족될 때 교착 상태가 발생한 가능성이 생긴다고 볼 수 있다.
상호 배제
우선 교착 상태가 발생한 근복적인 원인은 해당 자원을 한 번에 하나의 프로세스만 이용 가능했기 때문이다. 만약 하나의 자원을 여러 프로세스가 동시에 사용할 수 있었다면 교착 상태는 발생하지 않았을 것이다. 어쩔 수 없이 이런 상호 배제 상황에서는 교착 상태가 발생할 수 있다.
점유와 대기
식사하는 철학자 문제에서 누구도 식사를 할 수 없었던 이유는 '왼쪽 포크를 들고' 다른 철학자의 포크를 기다렸기 때문인데, 프로세스도 마찬가지로 어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있다. 이렇게 '자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태'를 점유와 대기라고 한다.
비선점
교착 상태가 발생하게 된 또 하나의 근복적인 문제는 프로세스가 자원을 비선점하고 있기 때문이다. 비선점 자원은 그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있기 때문에, 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗을 수 없는 것이다. 그렇기 때문에 교착 상태가 발생했다고 볼 수 있다.
원형 대기
교착 상태가 발생한 마지막 이유는 프로세스들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이루었기 때문인데, 자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 수 있다. 이렇게 프로세스들이 원의 형태로 자원을 대기하는 것을 원형 대기라고 한다.
13-2 교착 상태 해결 방법
교착 상태 예방
교착 상태를 예방하는 방법은 교착 상태 발생 필요 조건 네 가지 중 하나를 충족하지 못하게 하는 것이다. 하나하나 살펴보자면
우선 자원의 상호 배제를 없애 본다면, 즉 모든 자원을 공유 가능하게 만든다는 것과 같다.
하지만 이 방식은 현실적으로 모든 자원의 상호 배제를 없애기는 어렵기 때문에 다소 무리가 있다.
그렇다면 점유와 대기를 없애보겠다. 점유와 대기를 없애면 운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다. 다만 이 방법에는 단점이 있는데, 이는 당장 자원이 필요해도 기다릴 수 밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문에 자원의 활용률이 낮아진다. 또한 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아 현상을 야기할 수 있다.
비선점 조건을 없애면 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있다. 이 방식은 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적이지만, 한 프로세스의 작업이 끝날 때까지 다른 프로세스가 기다려야 되는 프린터같은 자원에게는 다소 범용성이 떨어지는 방안이다.
마지막으로 원형 대기를 없애는 방법은 간단하다. 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않는다. 이 방법은 앞선 세 방식에 비하면 비교적 현실적이고 실용적인 방식이지만, 단점이 있다. 모든 컴퓨터 시스템 내에 존재하는 자원에 번호를 붙이는 일은 힘들고, 번호에 따라 특정 자원의 활용률이 떨어질 수 있다.
교착 상태 회피
교착 상태 회피는 교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당하는 방식이다. 일단 교착 상태를 회피하는 방법을 학습하기 위해서는 안전 상태와 불안전 상태, 그리고 안전 순서열이란 단어를 알아야 한다.
교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태를 안전 상태라 하고, 교착 상태가 발생할 수도 있는 상황을 불안전 상태라 한다.
또 안전 순서열은 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미한다. 즉, 안전 순서열이 있는 상태를 안전 상태라고 볼 수 있다.
따라서 운영체제가 교착 상태를 회피하기 위해서는 시스템 상태가 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하면 된다. 즉, 교착 상태 회피 방식은 항시 안전 상태를 유지하도록 자원을 할당하는 방식이라 보면 된다.
교착 상태 검출 후 회복
교착 상태 예방과 회피는 교착 상태 발생을 막기 위한 노력이었다면, 교착 상태 검출 후 회복은 교착 상태 발생을 인정하고 사후에 조치하는 방식이다. 검출 후 회복 방식에서 운영체제는 프로세스들이 자원을 요구할 때마다 그때그때 모두 할당하며, 교착 상태 발생 여부를 주기적으로 검사한다. 그리고 교착 상태가 검출되면 그때 비로소 다음과 같은 방식으로 회복한다.
선점을 통한 회복
선점을 통한 회복은 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗아
한 프로세스에 자원을 몰아주는 방식이다.
프로세스 강제 종료를 통한 회복
프로세스 강제 종료를 통한 회복은 가장 단순하면서 확실한 방식으로, 운영체제가 교착 상태에 놓인 프로세스를 모두 강제 종료하거나, 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료하는 것이다. 전자는 가장 확실한 방식이지만 그만큼 많은 프로세스들이 작업 내역을 잃게 될 가능성이 있고, 후자는 작업 내역을 잃는 프로세스는 최대한 줄일 수 있지만 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기한다.
마지막으로 사실 교착 상태를 아예 무시하는 방법도 있다. 드물게 발생하는 잠재적 문제를 무시로 대처하는 방식으로 타조 알고리즘이라 한다. 완벽을 추구하는 과학자나 수학자 입자에서는 납득할 수 없는 방식일지 모르나, 문제 발생의 빈도나 심각성에 따라 최대 효율을 추구하는 엔지니어 입장에서는 때때로 이 방식이 적합할 때도 많다.
