현재 글은 https://www.os-book.com/OS10/slide-dir/index.html 을 참고하고 있습니다.
어쩌다가 https://www.youtube.com/channel/UCOcPzXDWSrnaKXse9XOPiog 채널을 봤는데, 정말 교수님이 설명을 잘하시는 것 같습니다.
문제의 발단
CPU 스케줄러는 타임 슬라이싱(시간을 짧게 쪼개 돌아가면서 사용)을 통해 빠르게 콘텍스트 스위칭을 일으켜 프로세스들을 실행하며, 이 과정에 다양한 인터럽트 역시 발생할 수 있다. 따라서 각 프로세스 및 스레드들은 실행의 "일부분" 만을 완료한 상태에 있게 된다.
문제는, 이러한 프로세스나 스레드들이 공유 메모리에 접근할 때 발생한다. 예를 들어 다음의 상황을 가정하자.
| 프로세스 | 연산 |
| A | in_s = s in_s += 1 s = in_s |
| B | in_s = s in_s -=1 in_s = s |
프로세스 A는 공유 메모리 S의 변수 s에 접근하여 +1 을 수행한 후 이를 반영하는 연산을, B는 -1을 수행한 후 이를 반영하는 연산을 한다. 이때 A와 B가 동시에 공유 메모리 S의 변수 s에 접근하여 값을 덮어쓰려고 한다면, 어떤 결과가 나타나게 될까?
S 영역에 데이터 일관성을 유지하기 위한 어떠한 방법도 마련되어 있지 않다면, A와 B가 실행되는 순서에 따라 결과가 달라질 수 있다. 예를 들어, 동시에 s = 5에 A및 B 프로세스가 접근하여 모종의 이유로 A가 먼저 작업을 끝내게 되면, 뒤따라오는 B의 연산 결과가 A의 작업을 덮어써서 결과적으로 s = 4가 저장된다. 반대로 B가 먼저 실행된다면, B의 작업 결과는 뒤따라오는 A의 작업인 s = 6으로 덮어 쓰인다.
즉, 프로세스나 스레드가 공유 메모리와 같은 공유 자원에 동시에 접근하여 이를 작성하려고 하는 경우 이들의 실행 및 종료 순서에 따라 결과가 달라지는 데이터의 비일관성이 발생할 수 있는데, 이를 Race Condition 이라고 한다.
위 상황의 경우 대부분의 프로그래머들은 s의 값을 한 번에 하나의 프로세스 혹은 스레드만이 업데이트하는 상황을 가정하고 코드를 작성할 것이다. 그런데, 프로세스의 동시성(Concurrent)에 의해 공유 자원에 대해서 Race Condition이 발생하므로 데이터가 예상하지 못한 값을 가지게 되는 문제가 발생한다.
이런 현상은 상당히 심각한 문제를 발생시킬 수 있다. 예를 들어, 은행에서 돈을 입출금할 때, 입출금 프로세스의 실행 순서에 따라 내가 통장에 입금한 금액 1천만 원이 증발하거나, 돈이 복사된다면 어떨까? 어떤 경우든 현실에서는 용납할 수 없는 상황이다. 따라서 프로세스의 동기화 문제를 해결하기 위해 다양한 방법이 고안된다.
Critical Section
Critical Section은 여러 프로세스가 공유하는 자원에 대해, 한번에한 번에 하나의 프로세스만이 활동할 수 있도록 제한 조건을 주는 영역이다. 발단 부분에서 제시된 Race Condition 문제는 공유 자원을 여러 프로세스가 동시에 접근하여 읽고 쓰는 과정에서 발생했다. 따라서 데이터의 일관성이 필요한 공유 영역에 대해 한번에 하나의 프로세스만이 동작하게 만들자는 것이 Critical Section의 의도이다.
Critical Section을 포함한 경우, 프로세스가 활동하는 영역은 다음과 같이 분류될 수 있다.
- Entry Section : 크리티컬 섹션에 진입하는 구역
- Critical Section : 데이터 일관성을 위해 한번에 하나의 프로세스만이 실행되는 구역
- Exit Section : 크리티컬 섹션을 벗어나는 구역
- Remainder Section : 평범한 동작을 수행하는 구역
커널과 크리티컬 섹션
프로세스는 fork을 통해 자식 프로세스를 생성할 수 있다. fork 함수는 자식 프로세스의 pid를 반환하는데, 해당 자식 프로세스의 주소 값을 우연히 두 프로세스가 동시에 사용하게 되면 동일 pid에 대해 자식 프로세스가 생성되므로 충돌이 발생할 수 있다.
예를 들어 P0가 2615 pid를 알고 있는 채로 인터럽트가 발생하고, P1이 해당 pid를 기반으로 자식 프로세스를 생성한 후 P0이 다시 running 상태가 된 후 자신이 기억하고 있는 next_available_pid를 기반으로 자식 프로세스를 생성한다면, 동일한 프로세스를 생성할 수도 있을 것이다.
프로세스의 커널 모드에서는 다음과 같은 선택지가 있다.
- Preemptive
: 프로세스들이 Concurrent하게 실행되므로 Race Condition이 발생할 수 있다. - NonPreemptive
: 프로세스가 일단 실행되면 자신의 작업이 끝날 때까지 멈추지 않으므로, Race Condition 자체가 발생하지 않는다.
Critical Section 을 달성하기 위한 조건
Critical Section을 만들기 위해서는 다음과 같은 조건들을 만족해야 한다.
- Mutual Exclusion ( 상호 배제 )
- 하나의 프로세스가 크리티컬 섹션에 존재하는 경우, 다른 프로세스들은 관련 작업을 수행할 수 없다.
- 이 조건을 달성하는 과정에서 Dead Lock 및 Starvation 현상이 발생할 수 있다.
- Progress ( 진행, Dead Lock 방지 )
- 크리티컬 섹션이 비어있다면, Remainder Section에서 작업을 하고 있지 않은 이상 어떤 프로세스든 다음에 들어갈 순서를 정할 수 있다. 이 과정에서 크리티컬 섹션에 참여하지 않는 프로세스는 크리티컬 섹션에 참여하는 프로세스의 진입을 방해해서는 안된다.
- 크리티컬 섹션에 들어갈 프로세스는 빠르게 정할 수 있으며 ( Dead Lock X ), 나머지는 대기열에 들어간다.
- Bounded Waiting ( 제한된 대기, Starvation 방지 )
- 프로세스가 크리티컬 섹션에 진입하고자 요청한 후부터 크리티컬 섹션에 실제로 진입하기 전까지 다른 프로세스에게 크리티컬 섹션 사용을 양보하는 횟수는 제한되어 있어야 한다.
- 일단 크리티컬 섹션에 대한 진입을 요청하면 제한된 턴을 대기 후 들어갈 수 있다. ( Starvation 발생 X )
동기화 문제 해결 방법들
크리티컬 섹션과 관련된 문제는 소프트웨어 또는 하드웨어적으로 해결한다.
소프트웨어 측면
Interrupt-based
데이터의 비일관성은 하나의 프로세스가 크리티컬 섹션 작업을 끝내지 못하고 외부의 간섭을 받는 과정에서 발생한다. 따라서 외부에서 발생하는 인터럽트 자체를 크리티컬 섹션에 있는 경우 무효화하는 방안을 생각할 수 있다.
이 경우 각 섹션이 하는 역할은 다음과 같다.
- Entry Section : 인터럽트 비활성화. 프로세스는 크리티컬 섹션에 누군가 없을 때까지 이곳에서 대기한다.
- Exit Section : 인터럽트 활성화. 명시적으로 크리티컬 섹션이 해제되었음을 알린다.
인터럽트가 없어 크리티컬 섹션이 보장될 수 있을 것 같아 보이지만, 크리티컬 섹션의 프로세스가 무한히 지속되는 것을 막을 방법이 없어 특정 프로세스만이 독점하여 사용함으로써 Starvation 문제가 발생할 수 있겠다.
위 문제를 해결하기 위해 일정 시간 간격으로 프로세스들이 번갈아가면서 크리티컬 섹션에 들어가게 만들 수 있다.
Two Process Solution
Two Process Solution에서는 2개의 프로세스를 대상으로 각자의 턴을 부여하여 크리티컬 섹션에 들어갈 수 있음을 보장한다. 이를 위해 turn 변수를 두고 있으며, 각각의 프로세스는 자신의 턴이 되면 크리티컬 섹션에 들어갈 수 있다.
- 보장되는 속성
- Mutual Exclusion : 프로세스는 자신의 턴에만 들어갈 수 있다.
- Bounded Waiting : 자신의 턴이 명시적으로 존재하므로, 자신의 턴까지 제한된 횟수의 턴을 기다리면 크리티컬 섹션에 진입할 수 있다.
- 보장되지 않는 속성
- Progress : Process A가 크리티컬 섹션에서 나온 후 B가 크리티컬 섹션을 이용하지 않아서 다시 들어가려고 해도, B가 크리티컬 섹션에 들어갔다 나오기 전까지는 자신의 턴이 돌아올 때까지 무기한 기다려야 한다.
위 방법의 Progress 문제를 해결하기 위해서는 아무도 크리티컬 섹션에 들어가지 않았을 때를 판단할 수 있어야 한다. 이를 위해 각각의 프로세스에 대해 플래그를 두고, 다른 플래그가 세워지면 들어가지 않는 동작을 생각할 수 있다.
- 보장되는 속성
- Progress : 각각의 플래그가 존재하므로, 다른 프로세스가 크리티컬 섹션을 사용하지 않는 경우 자유롭게 크리티컬 섹션을 더 이용할 수 있다.
- 보장되지 않는 속성
- Mutual Exclusion : 프로세스들이 둘 다 크리티컬 섹션에 없는 상태에서 동시에 while문을 검사하면 상대방의 플래그는 false 이므로 크리티컬 섹션에 동시에 진입할 수 있다.
- Bounded Waiting : 어떠한 순서 같은 것이 없으므로, 하나의 프로세스가 크리티컬 섹션을 계속 들어갔다가 나오면서 독점하더라도 이를 방지할 방법이 존재하지 않는다.
turn 및 flag 방식 둘다 크리티컬 섹션에 대해 보장하지 못하는 속성이 존재한다. 그렇다면 이 두 가지 방식을 동시에 적용하면 어떨까? Petersons's Solution은 이 두 가지를 동시에 사용하여 크리티컬 섹션 문제를 해결한다.
Peterson's Solution
Peterson's Solution은 turn 및 flag 정보를 이용하여 크리티컬 섹션 문제를 해결한다. 조건은 다음과 같다.
- turn 이나 flag를 load & store 하는 과정은 인터럽트가 적용되지 않는 머신 수준의 원자적 연산( atomic ).
- 사용되는 변수
- int turn : 크리티컬 섹션에 들어갈 턴을 의미하는 변수
- bool flag[2] : 프로세스가 크리티컬 섹션에 들어갈 준비가 되었는지 알리는 변수
- flag를 true로 설정, 자신이 크리티컬 섹션에 진입할 준비가 되었음을 알린다.
- 턴을 상대에게 넘긴다.
- 상대도 진입할 준비가 되었고 (flag), 실제로 상대의 턴이면 대기한다.
- 3의 조건이 깨지면 크리티컬 섹션에 진입하여 작업을 진행한다.
- 작업이 끝나면 flag를 false로 설정하여 자신의 종료 상황을 알린다.
대략적인 구조도를 그리면 다음과 같다.
위 구조도에서는 나타나지는 않지만 P2가 먼저 플래그를 true로 세우고 있는 경우, P1이 턴을 넘겨주면 P2가 크리티컬 섹션을 사용한 후 자신의 플래그를 내려 크리티컬 섹션이 사용되고 있지 않음을 알린다.
- 보장되는 속성
- Mutual Exclusion : 프로세스는 자신의 턴에만 들어갈 수 있다.
- Progress : 크리티컬 섹션이 비어있는 경우, 어떤 프로세스든 크리티컬 섹션 진입에 참여할 수 있다.
- Bounded Waiting : 구조상 자신의 턴이 존재한다.
단, Peterson's Solution은 소프트웨어적으로 entry Section에서 자신의 턴이 올 때까지 while문을 순회하면서 대기해야 하므로 busy waiting으로 인해 컴퓨터 자원을 낭비할 수 있으며, 이 방식만으로는 둘 이상의 프로세스는 다룰 수 없다. 또한 멀티 스레드에 대해서는 처리할 수 없어 메모리 베리어를 추가적으로 이용한다고 한다.
메모리 베리어
메모리 상의 변화를 모든 프로세스에게 전파하도록 만드는 instruction으로, CPU나 컴파일러에게 특정 연산의 순서를 강제하여, 최적화 등에 의한 코드 실행 순서의 변경을 방지한다.
https://ko.wikipedia.org/wiki/메모리_베리어
하드웨어 측면
하드웨어를 단일 CPU(uni processor) 기반으로 interrupt 없이 사용하면 실행 중인 각 프로세스 및 스레드를 nonpreemption으로 동작시킬 수 있다. 다만, 이를 해결책으로 사용하면 멀티 프로세서에 대한 지원이 불가하므로, OS 시스템에 대한 확장성이 떨어지게 된다.
따라서 실제로는 다양한 OS에서 아래 형태의 하드웨어 구조를 지원함으로써 동기화 문제를 해결하려고 노력한다.
- Hardware Instruction
- Atomic Variables
이러한 하드웨어적 방법들은 공통적으로 크리티컬 섹션을 잠군다는(Locking) 아이디어를 이용한다.
Atomic
크리티컬 섹션에 진입하는 경우, 현재 크리티컬 섹션에 다른 프로세스가 있는지 혹은 사용을 원하는 다른 프로세스가 있는지 같은 정보를 얻기 위해 플래그 혹은 변수를 읽고 쓰는 과정이 필요하다. 그런데, 해당 과정까지도 인터럽트로 인해 중단 및 재개될 수 있다면 크리티컬 섹션의 조건을 제대로 만족시킬 수 없게 된다.
따라서 특정 instruction은 interrupt로 쪼갤 수 없는 최소 단위의 연산일 필요가 있다. Atomic은 "원자적"이라는 의미로, 깨지거나 중단되지 않음을 의미한다. 더 나아가면 작업이 실행될 때 반드시 완전히 진행되어 종료되는 것을 의미한다.
- 연산이 Atomic : 해당 연산을 더 작은 연산 단위로 쪼갤 수 없어, interrupt에 의해 방해받지 않는다.
- 특정 플래그를 읽고 쓰는 과정 사이에 인터럽트가 발생해서는 안되는 경우, 이를 하나의 연산으로 만든다.
- 변수가 Atomic : 해당 변수에 대해 둘 이상의 프로세스가 동시에 쓸 수 없다.
- 변수의 값이 일종의 플래그처럼 사용되는 경우, 해당 값을 2개 이상의 프로세스가 수정할 수 없게 만든다. 적용되는 연산이 Atomic 한 특수한 변수.
Hardware Instruction
특정 값을 테스트하고 수정하는 Test-and-Set 과, 두 개의 값을 원자적으로 교환하는 Compare-and-Swap 이 있다.
Test-and-Set
target 값을 true로 만들고, target의 이전 값을 반환하는 연산이다. 이 연산은 크리티컬 섹션이 현재 잠겨있는지 (사용 중인지) 여부를 알리기 위한 Lock 변수를 변환하는 연산이다. 위 코드를 보면 연산은 다음 단계를 가진다.
- target 값을 가져온다.
- 이전 값을 rv에 저장해둔다.
- target을 true로 지정한다.
- rv을 반환한다.
이때 중요한 점은 각 단계가 각각 하나의 연산으로 취급되는 것이 아니라, 전부 묶어 test_and_set 이라는 하나의 연산이라는 점이다. test_and_set이라는 단일 연산이므로, 각 단계 사이에 인터럽트가 발생하지 않는다.
(예시)
위 코드는 test_and_set 연산을 통해 크리티컬 섹션 문제를 해결하는 모습을 보여주고 있다. 크리티컬 섹션이 잠겨있는지 여부를 의미하는 변수를 초기에 false로 지정해두었다고 가정하자.
초기 프로세스는 test_and_set 연산을 통해 lock 값을 true로 바꾸는 동시에 이전 값인 false을 받아 크리티컬 섹션에 들어간다. 크리티컬 섹션에서 업무를 수행하는 동안 프로세스 2가 진입하려는 경우, test_and_set 연산을 통해 lock의 이전 값인 true를 가져오면서 동시에 lock을 true로 지정한다. 따라서 프로세스 2는 entry Section에서 대기하게 된다.
단, 경쟁하는 프로세스가 3개 이상인 경우 Bounded Waiting 을 보장할 수 없다. P1, P2, P3가 크리티컬 섹션을 사용하기 위해 while문을 돌고 있다고 생각해보자. P1이 크리티컬 섹션에서 나오고, 이번에는 P2가 크리티컬 섹션에 들어간다. P2도 크리티컬 섹션에서 나온다면, Bounded Waiting을 보장하기 위해서는 P3가 이번 차례에 들어가는 것이 맞다. 그런데, test_and_set에는 특정 프로세스의 턴을 지정하는 기능은 없다. 따라서 P1과 P2가 계속 크리티컬 섹션을 나눠 사용하고 P3는 배제될 수 있다. 따라서, test_and_set 만으로는 크리티컬 섹션 문제를 해결하지는 못한다.
Compare_and_swap
값을 비교하여 해당 값이 예상한 값이 맞는 경우 변경하고, 이전 값을 반환하는 연산이다. 입력받은 value가 expected와 동일한 경우 new_value를 value에 할당한다. 이후 기존 value 값을 저장한다.
이 연산도 test_and_set과 마찬가지로 atomic 하다. 따라서 interrupt을 통해 연산을 쪼갤 수 없다.
(예시)
test_and_set처럼 하드웨어적으로 lock을 구현할 수 있지만, 여전히 bounded waiting을 처리할 수 없다. 해당 문제까지 해결하기 위해서는 일정 시간 프로세스들이 대기하기 위한 대기열이 필요하다.
위 코드에는 waiting 배열을 추가하여 현재 대기중인 상태를 나타낸다.
- waiting & key == true 라면, 자신의 차례가 아니므로 대기한다.
- 특정 프로세스가 크리티컬 섹션에서 나오면, 다음 기다리고 있는 프로세스를 찾아 waiting을 false로 바꾼다. 이를 통해 해당 프로세스는 waiting == false가 되므로 while문 대기를 탈출할 수 있다.
단, 이 상황 자체는 CPU burst로써 while문을 계속 대기하는 것이므로 효율적이라고 말할 수는 없다.
Atomic Variables
atomic 변수는 원자적인 업데이트 방식을 지원하는 변수로, Mutual Exclusion 문제를 해결하기 위해 사용된다. 아래 예시에서는 atomic 변수에 대한 연산 increment을 원자적 연산 compare_and_swap을 통해 지원하고 있다.
앞서 언급한 하드웨어적 방식을 프로그래머가 바로 사용하기는 어려움이 있다. 따라서 운영체제는 이러한 기능들을 지원하면서 프로세스 동기화 문제를 해결하기 위한 소프트웨어적인 방법을 지원한다.
Mutex Locks
Mutual Exclusion Locks 의 약자인 Mutex Locks은 lock 변수를 이용하여 크리티컬 섹션 문제를 해결한다.
- lock : 현재 크리티컬 섹션이 잠겨있는지 여부를 의미하는 변수
- acquire( ) : 크리티컬 섹션에 들어가기 위한 권한을 요청하는 함수
- release( ) : 크리티컬 섹션에서 나올 때 사용하는 함수
bool available;
void acquire() {
while(!available)
busy_wait();
available = false;
}
void release() {
available = true;
}acquire 및 release 함수 자체는 atomic 하게 수행되어 외부의 인터럽트 영향을 받지 않는다. 해당 연산들은 보통 compare-and-swap과 같은 atomic instruction에 의해 구현된다.
크리티컬 섹션에 입장할 때는 acquire을 통해 현재 가능한지 여부를 조사하고 lock을 걸어 다른 변수가 크리티컬 섹션에 진입하지 못하도록 막는다. 퇴장할 때는 release을 통해 현재 사용 중인 lock을 풀어 다른 프로세스가 크리티컬 섹션을 이용할 수 있도록 한다.
Mutex locks 방식은 크리티컬 섹션을 이용하고자 하는 프로세스들을 while문을 통해 대기시킨다. 이러한 대기는 CPU burst을 잡아먹는 busy waiting 또는 spinlock 이므로, 성능적으로 좋지 않다.
Semaphore
Mutex locks 방식처럼 크리티컬 섹션 문제를 해결하기 위한 방법이나, Mutex의 lock 변수가 boolean으로 사용되는 것과는 달리 semaphore에서는 정수형 변수를 이용한다. 즉, 공유 자원이 여러개인 경우 동기화를 처리할 수 있는 방법이다. 세마포어를 통해 일정 범위의 프로세스에 대한 크리티컬 섹션 진입을 관리할 수 있다는 장점이 존재한다.
- S (semaphore) : int형 변수. 동기화에 사용되며, 사용가능한 자원의 수를 의미할 수 있다.
- P ( wait ) : 크리티컬 섹션에 대한 대기 및 진입 역할을 수행하는 원자적 함수.
- V ( signal ) : 크리티컬 섹션에서 나올 때 S 변수를 변경하기 위한 원자적 함수.
wait(S) {
while ( S <= 0 ) ;
S--;
}
signal(S) {
S++;
}
Semaphore의 종류
- Counting semaphore : 일정 범위의 도메인을 다루는 경우. 보통 특정 데이터가 사용할 수 있는지 혹은 가용 자원이 얼마나 되는지 등의 정보를 알기 위해 사용한다.
- Binary semaphore : S의 범위가 0, 1로 제한되는 경우. Mutex locks와 같다.
사용 예시
1. 크리티컬 섹션
크리티컬 섹션의 경우 mutex 값을 초기에 1로 지정해두면 세마포어를 이용하여 관리할 수 있다. 특정 프로세스가 크리티컬 섹션에 들어가는 경우, wait(mutex)을 통해 현재 크리티컬 섹션이 사용 중인지 여부를 검사한다. 만약 사용 중이라면 spinlock에 의해 계속 대기하다가, 다른 프로세스가 signal(mutex)을 통해 자원을 해제하면 그때서야 들어갈 수 있다.
2. 프로세스 동기화
S1 및 S2이 반드시 S1 -> S2 순으로 실행되어야 하는 경우를 생각해보자. 초기에 세마포어 변수 synch의 값을 0으로 지정해두면 P2가 먼저 실행되더라도 wait 조건에 의해 S2가 실행되지 않는다. 이후 P1이 실행되어 signal(synch)을 실행하고 나서야 wait(synch)의 대기 조건이 끝나 S2를 실행한다. 이처럼 동기화 문제도 해결해볼 수 있다.
Implementation
기본적으로 Mutex locks 과 크리티컬 섹션 문제를 해결하는 방식이 비슷하기 때문에 Busy Waiting을 가진다. 구현 방식도 비슷하게 하는 경우 코드가 짧아진다는 장점이 있으며, 크리티컬 섹션을 거의 사용하지 않는 경우 문제가 없다.
그러나, 크리티컬 섹션에서 많은 시간을 사용해야 하는 경우에는 Busy Waiting이 그대로 성능적 낭비가 된다. 따라서 해당 대기시간 동안 프로세스를 waiting queue에 넣어두고 다른 프로세스를 동작시키는 방식을 사용한다.
semaphore with no Busy Waiting
크리티컬 섹션에 진입하기 위해 대기하는 프로세스들을 잠시 대기시키기 위해 waiting queue로 옮기고, 이후 해당 프로세스의 순서가 되면 다시 실행하는 방식이다. 이 경우, 세마포어 변수는 해당 프로세스를 대기시킬 waiting queue를 변수 내에 구현해야 한다.
- S : 세마포어 변수
- queue : 대기중인 프로세스 정보를 저장하기 위한 큐
- value : 세마포어 값. 가용 자원 정보 또는 크리티컬 섹션 사용 가능 여부를 의미한다.
- block( ) : 연산을 호출한 프로세스를 적절한 waiting queue에 저장한다.
- wakeup( ) : waiting queue에서 프로세스 하나를 제거하고, ready queue로 삽입한다.
typedef struct {
int value;
struct process *list // 프로세스에 대한 링크드 리스트
} semaphore;
void wait(semaphore *S) {
S->value--; // 세마포어 값을 1 감소
if (S->value < 0) { // 프로세스가 대기중이면
add this process to S->list; // 프로세스를 대기열에 달고
block(); // 블럭시킨다.
}
}
void signal(semaphore *S) {
S->value++; // 자원 반환
if (S->value <= 0) { // 현재 대기중인 프로세스가 있다면
remove a process P from S->list; // 프로세스 하나를 제거해서
wakeup(P); // ready queue에 넣는다.
}
}발생 가능한 문제점
세마포어는 반드시 wait - signal 쌍으로 사용해야 한다. 만약 wait을 통해 사용한 자원을 signal을 통해 해제하지 않으면, 해당 자원은 사용 불가능한 영역이 된다.
Deadlock
둘 이상의 프로세스가 대기중인 프로세스 중 하나의 프로세스만 가능한 이벤트를 동시에 기다림으로써 무한히 대기하는 상태를 의미한다.
예를 들어, 두 프로세스가 상대방의 프로세스 실행과 관련된 자원을 보유한 상태로 상대가 해당 자원을 내놓기를 기다린다고 생각해보자. 당연히 두 프로세스는 동시에 while문을 통해 대기하기 때문에 더 이상 실행되지 못한다. 사실 이는 둘 중 하나의 프로세스가 자신의 자원을 먼저 양보하면 해결될 수 있겠지만, 대기 알고리즘을 이런 상황에 대비하여 작성하지 않는다면 반드시 데드락 문제가 발생하여 프로세스들이 무기한 대기하게 된다.
위 상황에서 P0 및 P1은 각각 다른 자원을 할당받는다. P0은 초기에 wait(S)을 통해 S와 관련된 크리티컬 섹션 자원을 얻는다. P1은 반대로 wait(Q)을 통해 Q와 관련된 크리티컬 섹션 자원을 할당받는다.
문제는 다음 라인에서 발생한다. P0가 2번째 라인에 진입하면 wait(Q)을 실행한다. 이때 Q는 P1이 사용하고 있으므로 P0는 해당 시점에서 대기한다. P1 역시 S를 P0가 사용 중이므로, 해당 위치에서 대기한다. 결과적으로 P0 및 P1은 둘 다 크리티컬 섹션에 진입하지 못하므로 exit Section에서 signal 함수를 실행할 수 없게 되고, 서로 데드락 상태가 된다.
만약 두 프로세스 이외의 다른 프로세스가 S, Q waiting queue 에서 대기하고 있었다면, 해당 프로세스는 계속 자원을 할당받지 못하는 Starvation ( indefinite blocking ) 상태가 된다. 두 프로세스 말고도 다른 프로세스들도 피해를 입게 되는 것이다.
위 상황에서의 문제는 waiting 및 signal 순서를 서로 맞춰주면 된다. 이 경우, 순서에 따라 P0이 S 및 Q 자원을 할당받아 크리티컬 섹션 작업을 끝낸 후 signal을 통해 P1에게 자원을 넘겨줄 수 있다.
Priority Inversion
Priority Inversion은 프로세스 사이의 우선순위가 역전되는 현상을 의미한다.
preemption을 허용하는 시스템에서 H, M, L 순으로 우선순위가 높다고 가정하자. H와 L은 동일한 세마포어를 이용하여 크리티컬 섹션에 접근하고 있으며, M은 일반적인 프로세스이다. L이 실행되다가 H의 선점에 의해 종료되어야 한다고 생각해보자. L이 H에게 세마포어 S 관련 정보를 넘기기 위해서는 크리티컬 섹션 영역의 동작을 종료한 후, signal을 통해 세마포어 자원을 해제해야 한다. 그제야 H가 스케줄러에 의해 배치될 수 있는 것이다. 이때, 일반적인 프로세스 M 역시 L을 선점할 수 있다. 특히 현재 시점에서 H는 "대기" 상태이므로, 우선순위가 크게 밀리지도 않는다. 따라서 프로세스 M은 스케줄링을 통해 자신의 동작을 수행한다.
이 상황에서 프로세스 H는 프로세스 M의 동작이 끝나기 전에는 실행될 수 없게 된다.
따라서 기존 우선순위 L < M < H 은 L < H < M 인 것처럼 동작한다. 즉, 우선순위의 역전이 발생한 것이다.
이 문제를 해결하는 방법은 간단하다. H가 L에게 자원 해제 및 선점을 요청하면 일시적으로 L의 우선 순위를 H만큼 올려 M이 중간에 자원을 뺏어먹지 못하게 만드는 것이다. 이렇게 하면 일시적으로 M < L의 우선순위가 발생하므로, L은 정상적으로 세마포어 및 크리티컬 섹션 관련 자원을 H에게 전달할 수 있게 된다.
Monitors
위에서 본 것처럼 세마포어의 signal 및 wait 설계를 잘못하는 경우 데드락 등의 문제가 발생할 수 있다. 운영체제는 프로그래머가 이러한 사항을 신경쓰지 않아도 되도록 프로세스 동기화를 위한 더 추상적이고 상위의 자료구조를 제공하는데, 이것이 Monitor이다.
Monitor 내에 공유 변수, 해당 공유변수에 사용되는 프로시저 및 초기화 코드를 정의해두며, 모니터는 알아서 내부적으로 둘 이상의 프로세스가 동시에 접근할 수 없도록 관리한다.
Conditional Variable
각각의 크리티컬 섹션에 대응되는 조건 변수.
conditional x, y;
x.wait()
x.signal()
semaphore x_sem = 0;
int x_count = 0;
wait() {
x_count++;
if (next_count > 0)
signal(next);
else
signal(mutex);
wait(x_sem);
x_count--;
}
signal() {
if(x_count > 0) {
next_count++;
signal(x_sem);
wait(next);
next_count--;
}- wait( ) : x.signal이 수행되기 전까지 다른 프로세스의 접근을 막음.
- signal( ) : x.wait을 호출한 프로세스 중 하나에 대해 접근을 재개.
두 프로세스를 P, Q라고 할 때 다음과 같은 옵션이 있다.
- Signal and Wait
: P가 signal을 보내면 Q에게 바로 제어권이 넘어간다. 이 경우, P는 Q가 동작을 마칠때까지 기다린다. - Signal and Continue
: P가 Q에게 signal을 보내더라도 P가 동작을 끝마칠 떄까지는 Q가 기다려야 한다.
두가지 옵션 모두 장단점이 있으며, 실제 구현은 프로그래머 혹은 언어마다 다를 수 있다.
프로세스 재개 구현
x.signal()을 통해 잠든 프로세스를 다시 깨우는 경우 여러가지 스케줄링 방식 (FCFS, SJFS... ) 을 통해 다시 깨울 프로세스를 정할 수 있다. 보통 우선순위를 부여하는 것이 흔하다.
'CS > 운영체제' 카테고리의 다른 글
| [운영체제] 메모리 (0) | 2022.05.09 |
|---|---|
| [운영체제] 데드락 (0) | 2022.04.30 |
| [운영체제] CPU 스케줄링 (0) | 2022.04.11 |
| [운영체제] 스레드 & Concurrency (0) | 2022.04.06 |
| [운영체제] 프로세스 (0) | 2022.04.03 |
