Semaphore with 수도 코드

Semaphore

 

공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 여러 Process 혹은 Thread가 접근하는 것을 막아줌 (동기화 대상이 하나 이상) semaphore는 특정 임계 구역에 접근할 수 있는 프로세스의 수를 나타내는 변수이다.

 

- mutex와 달리 대기할 프로세스를 레디 큐에 넣는 것이 아니라 block시켜서 스케쥴러의 대상에서 빠지게 만든다. busy wating할 필요가 없어서 cpu 사용효율을 높일 수 있다. 이러한 프로세스의 상태 변경을 sleep - awake 라고 부른다

 

- semaphore 변수가 0과 1만 사용되면 mutex와 같은 방식의 동기화를 수행한다. 이를 binary semaphore라고 한다.

 

- 0과 1이 아닌 다른 범위의 정수를 semaphore 변수로 사용하는 것을 counting semaphore라고 한다.

 

 

Binary semaphore 수도 코드

struct binary_semaphore {
	enum {zero, one} value;
	queueType queue;
};

enum은 임계 구역을 사용할 수 있는 프로세스의 갯수이고, queue는 대기큐이다.

 

 

void semWaitB(binary_semaphore s) {
	if (s.value == one)
		s.value = zero;
	else {
	/* place this process in s.queue */;
	/* block this process */;
	}
}

wait함수는 임계구역을 사용하고 있는 프로세스가 존재할 때 접근한 다른 프로세스를 대기시키는 함수이다.

-> 어떤 프로세스에서 임계 구역에 접근할 때 호출 됨

 

 

만약 현재 임계 구역을 사용할 수 있는 프로세스의 갯수가 1개라면  value를 0으로 바꾸고 사용하면 된다. 만약 s.value가 0이라면 프로세스를 block 상태로 바꾸어 큐에 집어 넣어서 스케쥴링 대상에서 제외한다.

semaphore에선 이 작업을 P [stands for proberen (“try")] 라고 한다.

 

 

 

void semSignalB(semaphore s) {
	if (s.queue is empty())
		s.value = one;
	else {
	/* remove a process P from s.queue */;
	/* place process P on ready list */;
	}
}

Siginal 함수는 임계 구역을 사용하고 있는 프로세스가 없을 때 새로운 프로세스를 할당하는 함수이다.

-> 하나의 프로세스에서 임계 구역 사용을 종료할 때 호출됨

 

만약 s.queue가 비었다면 임계구역 사용을 대기하고 있는, 사용 중인 프로세스가 없다는 뜻이므로 value를 1로 바꿔주고 만약 큐가 비어있지 않다면 큐에서 다음 순서로 임계 구역을 사용할 프로세스를 레디큐로 위치시킨다.

이 작업을 V stands for verhogen ("increase") 라고 부르기도 한다.

 

 

 

Counting Semaphore 수도 코드

struct semaphore {
	int count;
    queueType queue;
}

임계 구역을 사용할 수 있는 프로세스의 수가 0, 1이 아닌 여러 값을 가질 수 있다.

 

 

void semWait(semaphore s) {
	s.count--;
    if (s.count < 0) {
    	/* place this process in s.queue */;
        /* block this process */;
    }
}

Wait가 호출되면 count를 -1 감소시키고 만약 그 값이 0보다 작다면 프로세스 상태를 block으로 바꾸고 대기큐로 위치시킨다. 

 

 

void semSignal(semaphore s) {
	s.count++;
    if(s.count <=0) {
    	/* remove a process P from s.queue */;
        /* place  process P on ready list */;
    }
}

Signal이 호출되면 count를 1 증가시키고 만약 그 값이 0보다 크다면 대기큐에 존재하는 프로세스를 레디큐로 위치시켜 스케쥴러에 의해 cpu에 할당되어 원래 사용하려던 임계 구역을 사용할 수 있게 끔한다.

이러한 방식은 mutex 방식과 달리 queue에 있던 대기 프로세스부터 실행되므로 FIFO구조로 프로세스의 우선순위를 정할 수 있게 된다. (오래 기다린 프로세스부터 임계 구역 사용)

 

 

 

 

DeadLocks

 

하지만 이와 같은 형태의 semaphore는 Deadlock을 발생시킬 수 있다.

 

semaphore는 한가지 임계 자원이 아닌 여러 임계 자원에 대한 상태를 나태낼 수 있고

아래와 같이 P0, P1가 S, Q라는 임계 자원을 동시에 접근했다고 하면,

 

첫 S와 Q는 각각 1개의 프로세스가 사용할 수 있다고 가정했을 때 P0와 첫줄의 wait함수를 호출하면 S의 count가 1에서 0으로 바뀐다.

 

이 때 만약 스케쥴러가 P1을 할당하면 Q도 마찬가지로 0으로 바뀔 것이다. 하지만 또다시 스케쥴러가 P0를 호출한다면 두번째 줄의 wait함수를 호출했을 때 Q가 0이므로 대기 상태로 들어가고 다시 P1이 실행되면 P1도 마찬가지로 S가 0이므로 대기 상태로 들어갈 것이다.

 

이렇게 두 프로세스가 어느 한쪽도 수행되지 못하는 Deadloack이 발생된다.