세마포어

세마포어는 뮤텍스와 비슷하게 동작하지만 프로세스들이 자신의 행동을 더욱 정교하게 동기화 할 수 있는 방법을 제공한다.

세마포어 S는 정수 변수로 초기화를 제외하고는 원자적 연산인 wait() , signal() 로만 접근 가능하다.

 

 

세마포어 사용법

운영체제는 카운팅 세마포어와 이진 세마포어를 구분한다.

카운팅 세마포어의 값의 범위는 제한이 없고,

이진 세마포어의 값은 0과 1 사이의 값만 가능하다.

따라서 이진 세마포어는 뮤텍스 락과 유사하게 동작한다.

 

카운팅 세마포어는 유한한 개수를 가진 자원에 대한 접근을 제어하는데 사용될 수 있다.

세마포어는 사용 가능한 개수로 초기화 된다.

각 자원을 사용하려는 프로세스는 세마포어에 wait() 연산을 실행하고

세마포어의 값을 감소시키고 작업이 끝나고 자원을 방출할 때에는 signal 연산을 수행하고

세마포어의 값을 증가시킨다.

 

세마포어의 값이 0일떄에는 모든 자원이 사용 중임을 나타낸다.

이 때 자원을 사용하려는 프로세스는 세마포어의 값이 0보다 커질 때까지 봉쇄된다.

 

wait(), signal()

wait  (S) {     while (S <= 0)     // 바쁜 대기     S--; }

signal (S) {     S++; }

 

 

구현

세마포어 연산 wait() , signal()의 정의 역시 바쁜 대기 문제를 가지고 있다.

빠른 대기 문제를 해결하기 위해서 다른 방법이 고안된다.

 

프로세스 봉쇄 방식

세마포어의 값이 양수가 아닐 때 바쁜 대기 대신 프로세스를 봉쇄하는 방식

봉쇄 연산은 프로세스를 대기 큐에 넣고 프로세스의 상태를 대기 상태로 전환한다.

세마포어를 대기하면서 봉쇄된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재 시작 된다.

프로세스는 wakeup() 연산에 의하여 재 시작 되는데 대기 큐에 있던 프로세스를 준비 완료 큐에 넣어준다.

 

봉쇄 방식의 세마포어 정의

typedef struct {     int value;     struct process *list; } semaphore;

 

각 세마포어는 한 개의 정수 value 와 프로세스 리스트 list를 가진다.

만약 프로세스가 세마포어를 기다려야 한다면

이 프로세스를 세마포어의 프로세스 리스트에 추가한다.

signal() 연산은 프로세스 리스트에서 한 프로세스를 꺼내어 그 프로세스를 깨워준다.

 

봉쇄 방식의 wait(), signal()

void wait (semaphore *S) {     S->value--;     // 이 프로세스를 S->list에 넣는다.     if (S->value < 0) {         block();     } }

void signal (semaphore *S) {     S->value++;     // S->list로부터 하나의 프로세스를 꺼낸다.     if (S->value <= 0) {         wakeup(P);     } }

 

block 연산은 자기를 호출한 프로세스를 중지시킨다.

wakeup(P) 연산은 봉쇄된 프로세스 P의 실행을 재개 시킨다.

바쁜 대기 방식의 세마포어의 고전적 정의에서는 세마포어의 값은 음수를 가질 수 없으나

봉쇄 방식의 세마포어 에서는 음수 값을 가질 수 있다.

세마포어의 값이 음수일 때 그 절대 값은 세마포어를 대기하고 있는 프로세스들의 수이다.

 

 

교착 상태와 기아

2개의 프로세스가 2개의 자원을 각각 점유한 상태에서

다른 프로세스가 보유하고 있는 파일을 요청해

두 프로세스 모두 작업을 완수하지 못하는 상태에 도달했을 때

이들 프로세스를 교착상태라고 한다.

 

교착상태와 연관된 다른 문제는 무한 봉쇄 또는 기아 가 있다.

이것들은 프로세스들이 세마포어에서 무한정 대기하는 것이다.

기아는 세마포어와 연관된 큐가 후입선출 방식일 경우 발생할 수 있다.

 

 

우선순위 역전

예를 들어 a > b > c 형태로 우선 순위를 갖는 작업이 있고 x라는 임계 영역을 a와 c 가 사용할 예정이다.

그런데 c가 도착 시간이 빨라서 먼저 x영역을 사용하면서 세마포어 wait를 실행시키게 된다.

그 다음 b의 작업이 수행되게 될 경우 우선 순위가 높은 b가 수행되게 된다.

이렇게 될 경우 c-b-a 순서로 태스크가 수행되고 우선 순위 역전 상황이 발생하게 된다.

이런 문제는 실시간 운영체제에서 마감 시간을 지키지 못해 심각한 문제가 발생할 수 있다.

 

이러한 문제를 해결하기 위해 우선 순위 상속 프로토콜을 구현함으로써 이 문제를 해결한다.

이 방식에서는 c가 작업을 할 때 해당 임계 영역 x를 사용하는 다른 태스크가 있는지 파악 후

그중 가장 높은 우선 순위를 c에 임시로 상속하여 문제를 해결한다.

이렇게 할 경우 c는 a의 우선 순위를 상속하여 실행하므로 b보다 먼저 실행되고

a는 b보다 우선 순위가 높으므로 c-a-b 순서로 태스크가 수행되게 된다.