지난 강의 내용인 프로세스 충돌 해결 1과 이어집니다.
0. 복습
Critical Section 코드들이 Race Condition을 발생하지 않게 하기 위해서는 Critcal Section 전후에 Entry Section, Exit Section로 울타리를 두어 Mutual Exclusion을 만족시켜야 한다.
이 때 Entry Section은 울타리 영역 내부에 다른 프로세스가 실행 중인지 체크하고 비어 있는 경우 프로세스의 접근을 허용하는 역할을 하고, Exit Section은 울타리 영역 밖 다른 프로세스가 대기하고 있는 경우 영역 내부로 들어가도 되는지의 여부를 전달하는 역할을 한다.
지난 시간 말미에 소프트웨어적으로 이를 구현해보았으나 애로사항이 다소 발생하였고, 이를 하드웨어 지원을 받아 Mutual Exclusion을 만족시키는 방법을 정리하려 한다.
1. Test and Set Instruction
프로세스 실행 중 Inturrupt가 발생하는 경우, 실행하던 상태 레지스터 값을 저장한 후 커널로 넘어가게 된다.
또한 Race Condition을 방지하기 위한 한 가지 방법으로 Atomic operation이 존재하는데, 레지스터 처리 과정을 하나로 묶어 (원자화) interrupt가 비활성화된 상태에서 실행해야될 Instruction들을 처리하는 것이다.
counter++ 등의 사용자 코드가 원자화될 경우 시스템에 위협이 될 수 있기 때문에 이를지양해야 될 필요가 있다.
따라서 이를 원자화하는 것이 아닌 Entry Section을 원자화하는 방법이 사용되었다. 대표적으로 Test and Set Instruction이 존재한다.
작동원리
작동원리는 간단하다. 인자로 넘어온 값을 판별(Test) 후, 0인 경우 1로 변환 후 True를 반환한다. 이 때 True의 의미는 Key를 받아 Entry Section으로 진입할 수 있음을 의미한다. 1인 경우 Key가 다른 프로세스의 소유임을 의미하는 False를 반환한다.
장단점
지난 강의에서 언급한 SW적인 해법에서 Bakery Algorithm등과 비교하여 굉장히 짧고 간결한 코드로 Mutual Exclusion을 만족할 수 있게 되었지만, 단점 또한 존재한다.
첫 번째 단점으로는 while문 사용을 통한 Busy Waiting이 발생한다. Busy Waiting이란 특별한 일은 하지 않으면서 조건을 만족하는지 판별하기 위해 CPU의 시간을 사용하는 것을 의미한다.
두 번째는 Bounded waiting을 막을 방법이 부재하다는 것이다.
세 번째로 DeadLock의 발생 가능성인데, 프로세스들이 서로 상대방의 리소스를 사용하기 위해 대기하고 있는 상태를 말한다.
2. Semaphore
Test and Set Instruction의 단점을 보완한 Critical-Section Problem 해결책. Busy Waiting을 방지할 수 있고, Mutual Exclusion을 만족한다.
Semaphore은 음수,0,양수 구간의 정수값을 가지며, 값을 변화시키는 함수가 운영체제 내부에 구현되어 있다. TestSet처럼 하드웨어 지원을 받아 Race Condition을 방지하는 함수이다. semWait(s) 함수를 통해 정수형 변수를 감소시키고, semSignal(s) 함수를 통해 정수형 변수를 증가시킨다. 각각의 함수는 Atomic하여 실행되는 동안에는 Interrupt가 발생하여도 Delay시키고 남은 코드를 마저 처리한다.
이처럼 변수 값을 통해 컴퓨팅 자원이 사용가능한 상태인지를 나타내게 된다. 현재 컴퓨팅 자원이 사용 중인 상태라면 순서대로 대기(Block, Wait)하여 별도의 queue를 생성한다.
기존의 TestSet에서는 대기할 때 Running 상태에서 CPU를 가지고 대기하여 Busy Waiting 현상이 발생하였지만, Semaphore에서는 CPU를 아예 놓고 Block queue에 진입함으로써 Busy Waiting을 방지할 수 있는 것이다.
struct semaphore {
int count;
queueType queue;
}
void semWait (semaphore s)
{
s.count--;
if (s.count <0)
{
해당 프로세스를 s.queue로 편입
해당 프로세스를 대기 상태로 전환
}
}
void semSignal (semaphore s)
{
s.count++;
if (s.count <= 0)
{
가장 먼저 기다리고 있었던 프로세스를 깨움 (s.queue에서 빼내옴)
깨운 프로세스를 실행대기 상태로 전환
}
}semWait, semSignal 함수를 이용한 Semaphore 의사 구현 코드이다.
초기의 카운트 값은 1이고, 이는 프로세스가 컴퓨팅 자원에 접근 가능한 상태임을 의미한다.
semWait 함수는 카운트를 감소시켜 컴퓨팅 자원 사용을 위해 대기 상태로 변환시킨다. 카운트가 -n인 경우 n개의 프로세스가 자원을 사용하기 위해 대기 중인 것이다.
semSignal 함수는 컴퓨팅 자원을 다 사용한 프로세스가 나갈 때 호출된다. 카운트를 증가시키고, 대기 상태에 있는 가장 첫 번째 프로세스를 깨워 실행대기 상태로 전환시킨다.
따라서 Critical Section 접근을 위한 Entry Section을 semWait()로, 처리를 마치고 나갈 때 Exit Section을 semSignal()로 구성하여 Semephore를 구현하게 되는 것이다. 앞에서도 말했듯 각각의 함수는 Atomic하다.
3. Semaphore 활용사례
프로세스간 실행 순서 제어 방법
스케쥴링에 의존한 프로세스 간 실행은 항상 원하는 순서대로 일어날 수 없기 때문에, Semephore를 이용해 순서를 지정해주기도 한다.
두 프로세스 Pi, Pk가 있다고 가정할 때, Pi가 항상 우선적으로 처리되길 원하는 경우 Count 초기값을 0으로 설정하여 Pi의 코드 끝단에 semSignal이, Pk의 코드 시작점에 semWait가 오게 구성한다.
이와 같이 코드를 구성할 경우 Pi의 코드가 전부 실행된 후 semSignal을 통해 Count값이 증가되어야 비로소 Pk가 실행될 수 있으므로 프로세스 간 순서를 원하는대로 제어할 수 있게 되는 것이다.
Readers-writers Problem
프로세스가 값을 변경(Write)하는 경우에는 Race Condition을 방지하기 위해 Critical Section에의 접근을 막아야 하는 게 맞지만, 읽기만 하는 프로세스의 경우에는 여러 개의 프로세스가 접근할 수 있다. 이처럼 Reader 프로세스에 대한 접근 기준을 완화시켜주는 것을 Readers/Writers Problem이라고 한다.
Binary Semaphore & Lock
변수값을 0과 1만 갖는 특수한 Semaphore이다. 0인 경우 컴퓨팅 자원을 사용할 수 없는 상태, 1인 경우 사용 가능한 상태를 뜻한다.
