Semaphores

이전 Mutex lock과 유사하게 동작하지만 더 강력한 기능을 제공한다.

Semaphores란?

세마포어의 S는 정수 변수로서, 초기화를 제외하고는 wait()와 signal()인 두개의 원자적 연산으로만 접근한다.

wait()

wait(S){
	while(S <= 0);
	S--;
}

signal()

signal(S){
	S++;
}

S의 정수 변수를 다루는 모든 작업은 인터럽트 되지 않고 원자적으로 실행 되어야한다.

사용법

counting semaphore

카운팅 세마포어의 값은 제한 없는 domain을 갖는다.
유한한 개수를 가진 자원을 접근 제어하는데 사용된다. 세마포어는 가용한 자원의 개수로 초기화 되며 wait() 연산 수행시 세마포어 값은 감소한다. 이후 signal() 연산을 수행하면 세마포어 값은 증가한다. 세마포어 값이 0이 되면 모든 자원이 사용 중임을 나타낸다.

binary semaphore

이진 세마포어의 값은 0과 1사이의 값만 가능하다.
뮤텍스 락과 유사하게 동작한다.

동기화 문제에 사용하는 방법

P1은 S1 명령문을, P2는 S2 명령문을 병렬적으로 수행하려는 두 프로세스가 있다고 예를 들자. S2는 S1이 끝난후 수행되어야 한다고 가정하자. 이떄 우리는 P1과 P2가 synch 변수를 공유하도록 하고 synch를 0으로 초기화 한다.

P1의 코드

S1;
signal(synch);

P2의 코드

wait(synch);
S2;

초기 synch 값은 0이므로 S2의 명령문은 실행되지 않는다. S1명령문이 실행 된 후 signal을 통해 synch의 값이 1증가한다. wait()로 기다리고 있던 P2가 synch 값이 변경됨을 확인하고 S2명령문이 실행된다.

Semaphore Implementation (세마포어 구현)

바쁜 대기의 문제를 해결하기 위해선 wait()와 signal() 세마포어 연산을 새롭게 정의해야한다. wait() 연산 실행 후 세마포어 값이 양수가 아니면 바쁜 대기를 하는것이 아닌 프로세스를 일시 정지하도록 한다. 일시 중지 연산은 프로세스를 세마포어에 연관된 대기 큐에 넣고 프로세스 상태를 대기 상태로 전환한다.
세마포어 S 변수 값을 대기하면서 일시 중지된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작 된다. 프로세스는 wakeup() 연산에 의해 재시작되는데 프로세스를 대기 상태에서 준비 상태로 변경한다. 그리고 프로세스는 준비 큐에 들어가게 된다.

자료구조

typedef struct{
	int value;
	//  세마포어를 기다려야 한다면 프로세스는 리스트에 추가 된다.
    // signal() 연산은 프로세스 리스트에서 하나의 프로세스를 꺼내서 정지된 프로세스를 깨운다.
    struct process *list;
} semaphore;

wait()

바쁜 대기를 하는 고전적인 세마포어에서는 S의 값이 음수가 될 수 없지만 프로세스를 중지 시키는 방식에서는 세마포어값이 음수가 가능하다. 음수값의 절대값이 의미하는것은 대기중인 프로세스의 수이다.

wait(semaphore *S){
	S->value--;
	if(S->value < 0){
		add this process to S->list;
		
        // 현재 프로세스를 일시 중지한다.
		sleep();
	}
}

signal()

signal(semaphore *S){
	S->value++;
	if (S->value <= 0){
		remove a process P from S->list;
        
		// 입력으로 받은 프로세스를 재실행시킨다.
		wakeup(P);
	}
}

주의할 점

같은 세마포어에 대해서 두 프로세스가 동시에 wait(), signal() 연산을 실행할 수 없도록 보장해야한다. 단일 코어에서 인터럽트를 금지함으로써 이문제를 해결할 수 있다.
다중 코어 환경에서는 모든 코어에서 인터럽트를 금지하도록 하는것이 쉽지 않을 뿐더러 성능마저 감소하는 문제가 발생한다. 다중 코어 환경에서는 원자적으로 실행됨을 보장하기 위해 compare_and_swap() 또는 스핀락과 같은 다른 기법을 사용해야 한다.
우리는 wait()와 signal() 연산에서 바쁜대기를 완전히 제거하지 못했다. 바쁜 대기를 진입 코드에서 응용 프로그램의 임계 영역으로 이동하였으며 wait()와 signal() 연산의 임계 영역에만 한정 하였다. 임계 영역의 코드는 매우 짧고 임계 영역은 거의 비어 있으며 바쁜 대기는 드물게 발생한다. 발생하더라도 그 시간은 매우 짧게 된다. 만약 임계 영역이 길고 항상 점유하는 프로그램들도 있을 수 있다. 이 경우 바쁜대기는 성능에 비효율적이다.