[운영체제] 세마포어(Semaphore)

개요(Overview)

 이번 포스팅은 이전 게시글에서 다루었던 병행 프로세스와 Dekker 알고리즘에 이어 조금 더 복잡한 문제를 다루기 위한 세마포어(Semaphore)에 대해서 다루도록 하겠습니다.

 

 

https://1-hee.tistory.com/147

[운영체제] 병행 프로세스와 Dekker 알고리즘

 

 

---

 

1. 세마포어(Semaphore)

 

여러 프로세스들이 조금 더 복잡하게 얽힌 경우에는 상호배제(mutual exclusion) 문제를 해결하기 어려운 경우가 존재합니다.

그래서, 이를 극복하기 위해 세마포어(Semaphore)라는 새로운 방법이 다익스트라에 의하여 도입되었습니다.

세마포어란 P와 V 그리고 세마포어의 초기치를 설정해주는 오퍼레이션에 의해서만 액세스 될 수 있는 통제된 변수입니다.

이진 세마포어에서는 0과 1의 두 가지 값만을 가질 수 있으며 산술 세마포어는 0과 영의 정수를 값으로 가질 수 있다는 특징이 있습니다.

 

 어떤 세마포어 S에 대하여 P 오퍼레이션 P(S)는 다음과 같이 수행됩니다.

	if (S > 0 )
	then S := S-1
	else (wait on S)

 

 

세마포어 S에 대한 V 오퍼레이션 V(S)는 다음과 같이 수행됩니다.

	if (1개 이상의 프로세스가 s에 대기중)
	then ( 그  중 1개의 프로세스만 진행 )
	else S := S+1

 

 

P, V 연산 내에서 세마포어의 정수 값 수정은 단위적으로 수행됩니다. 즉, 하나의 프로세스가 세마포어의 값을 수정할 때 다른 어떤 프로세스도 동시에 같은 세마포어의 값을 수정할 수 없습니다.

 

---

 

1.1. 세마포어의 사용

 세마포어는 n개의 프로세스의 임계 영역 문제를 다루는데 사용됩니다. n개의 프로세스는 1로 초기화된 공통 세마포어 mutex를 공유합니다. 각 프로세스의 Pi 구조는 다음과 같습니다.

 

repeat
	P(mutex) ;
		임계영역
	V(mutex) ;
		나머지 영역
	until false;

 

 

 세마포어는 이외에더 여러 가지 동기 문제를 해결하는 데 사용됩니다. 세마포어 S에 대한 상호배제는 P(S)와 V(S) 사이에서 보장됩니다. 만일 여러 개의 프로세스가 P(S)ffm t동시에 수행한다면 단지 한 개의 프로세스만이 P(S)를 넘어서 진행할 수 있게 되고, 다른 프로세스들은 기다리게 됩니다.

 

 세마포어와 그에 대한 오퍼레이션들은 소프트웨어나 하드웨어에 의해 구현될 수 있습니다. 이들은 보통 운영체제의 핵(nucleus)에 속하여 구현되는데, 이 핵(nucleus)에서는 CPU를 한 프로세스로부터 다른 프로세스에게로 넘겨주는 일을 하기도 합니다.

 

예를 들어 수행중인 2개의 프로세스 즉 문장 S1을 가진 P1과 문장 S2를 가진 P2를 생각해보겠습니다. 이때 S2는 S1이 끝난 후에만 수행된다고 가정하면, P1과 P2가 0으로 초기화되는 공통 세마포어 synch를 공유하게 하고 프로세스 P1에

	S1;
	V(synch)

 

를 삽입하고 프로세스 P2에

 

	P(synch);
	S2;

 

를 삽입함으로써 쉽게 구현될수 있습니다. synch는 0으로 초기화 되었으므로 P2는 p1이 V(synch)를 부르고 난 후에 S2를 수행하게 됩니다.

 

---

 

1.2. 세마포어의 구현

 세마포어의 가장 큰 단점은 바쁜 대기(busy-wating)을 요구하는 것입니다. 어떤 프로세스가 임계 영역 내에 있는 동안 그 임계 영역에 들어가려고 하는 다른 프로세스는 진입 코드에서 계속해서 돌게 됩니다. 이 문제는 하나의 CPU가 많은 프로세스에 의해 공유되는 실시간 다중 프로그래밍 시스템에서 특히 심각할 수 있습니다. 바쁜 대기(busy-wating)으로 다른 프로세스가 생산적으로 사용할 수 있었던 CPU시간을 낭비하기 때문입니다.

 

 바쁜 대기의 필요성을 극복하기 위해서 세마포어의 P, V 조작을 수정할 수 있는데, 어떤 프로세스가 P 조작을 수행하고 난 후 세마포어의 값이 양이 아님을 발견하면 그 프로세스 자체를 보류시킬 수 있습니다. 보류 조작은 프로세스를 대기 상태에 놓게 됩니다. 그리고 난 후 제어권을 CPU 스케줄러에게 넘기게 되며, CPU는 준비상태 큐에서 다른 프로세스를 선택하여 수행시킵니다.

 

 세마포어 S에 의해 보류되거나 대기 중인 프로세스는 다른 프로세스에 의한 V 조작의 수행에 의해 재시행됩니다. 그 프로세스는 wakeup 조작에 의해 새로 시행되는데, 이는 프로세스의 상태를 보류 상태에서 준비 상태(ready)로 바꾸고 이를 준비 큐에 넣습니다.

이때 CPU는 실행중은 프로세스로부터 새로운 준비 상태의 프로세스로 스케줄링 알고리즘에 따라 제어권을 옮기거나 옮기지 않을 수 있습니다. 이러한 가정 하에 세마포어를 구현한다면 다음과 같은 레코드로 정의할 수 있습니다.

 

type semaphore = record
			value : integer ;
			L : list of process
			end;

 

 

 각 세마포어는 정수 값과 프로세스의 리스트를 갖고 있습니다. 어떤 프로세스가 세마포어에 의해 대기중일 때에는 프로세스의 리스트에 의해 첨가됩니다. V 조작은 대기 프로세스의 리스트에서 하나를 제거하여 이를 깨우는 역할을 합니다. 이제 세마포어의 조작은 아래와 같이 정의됩니다.

 

P(S) : S.value : S.value – 1;
	if (S.value < 0 )
	then begin
		add this process to S.L ;
		block;
		end;
V(S) : S.value := S.value + 1;
	if(S.value <= 0)
	then begin
		remove a process P from S.L;
		wakeup(P);
		end;

 

  

 block 연산을 이를 부르게 되는 프로세스를 보류시키는 역할을 합니다. wakeup(P) 연산은 보류된 프로세스 P의 실행을 재개시키는 역할을 담당합니다. 이러한 두 연산 과정은 운영체제에 의해 기본적인 시스템 호출로 제공됩니다. 주목할 점은 바쁜 대기(busy-waiting) 세마포어에서는 그 값이 절대 음수가 될 수 없으나, 여기에 구현된 세마포어의 값은 음수가 될 수 있다는 점입니다.

 

 만일 세마포어의 값이 음수일 때에는 세마포어에서 기다리는 프로세스의 개수를 나타냅니다. 이러한 결과는 P 동작의 구현에 있어 감사과 테스트의 순서를 맞바꿈으로 인해 나타날 수 있습니다. 프로세스의 리스트는 각 프로세스 제어 블록(PCB)의 링크 필드(link field)에 의해 쉽게 구현될 수 있습니다.

 

 각 세마포어는 정수값과 PCB 리스트의 포인터를 포함합니다. 리스트에서 프로세스를 첨가하거나 제거하는 가장 간단한 방법은 스택(stack) 자료 구조의 LIFO(last in first out) 방식입니다. 그러나 이 방법은 기아 상태를 야기시킬 수 있으므로 스택 보다는 큐를 통해서 보다 보편적으로 구현할 수 있습니다.

 

 이때 사용되는 세마포어의 큐는 머리(head)와 꼬리(tail) 포인터를 포함합니다. 극러나, 일반적으로 이 리스트는 임의의 큐잉 정책을 사용할 수 있는데 가령 FIFO, LIFO, 우선 순위 와 같은 방식이 적용될 수 있습니다. 세마포어의 올바른 사용은 세마포어의 리스트에 대한 특정 큐잉 정책에 따라 좌우되지 않습니다.

 

 세마포어(semaphore)의 가장 중요한 특징은 단위적으로 수행된다는 점입니다. 두 개의 프로세스가 동시에 같은 세마포어에 대하여 P와 V 조작을 할 수 없게 해야 하고, 이 상황은 임계 영역의 문제의 한 예시이므로 두 방법 중 하나로 해결할 수 있습니다.

첫번째는 단일 프로세서 시스템에서 P와 V 조작이 수행중일 때에는 인터럽트를 금지시키면 됩니다. 이 방법은 일단 인터럽트가 금지되면 다른 프로세서로부터의 명령어의 실행이 중간에 끼어들지 않게 되므로 단일 프로세스 환경에서 활용되는 방식입니다.

 두번째는 다중 프로세서의 경우에 인터럽트의 금지가 운용되기 어려우므로, 다 프로세서로부터의 명령어는 어떤 임의의 명령어로서 끼어들 수도 있습니다. 하드웨어가 어떤 특별한 명령을 제공하지 않으면 임계 영역의 문제에 대한 정확한 소프트웨어 해결 방법을 사용해야 하는데 여기서 임계 영역은 P와 V 그리고 프로시저(Procedure)로 구성됩니다.

 

 이러한 P와 V 조작으로는 바쁜 대기(busy-waiting)를 완전히 제거할 수 없다는 한계점이 존재합니다. 그렇기에 응용 프로그램의 진입점으로부터 임계 영역으로의 바쁜 대기를 이동시키고 P, V 조작의 임계 영역 내에서만 아주 짧은 시간 동안 제한하는 방향이 더 좋습니다.

 

이에 따라 임계 영역은 거의 항상 비어 있으며 바쁜 대기가 거의 일어나지 않는 것처럼 보이게 됩니다. 바쁜 대기가 일어났을 때에는 아주 짧은 시간 동안이며, 어떤 응용프로그램에서는 임계 영역이 아주 길거나 거의 점유된 상황아 발생할 수도 있습니다. 이 경우에는 오히려 바쁜 대기가 매우 비효율적일 수 있습니다.

 

---

 

1.3. 생산자/소비자 관계와 판독기/기록기 관계

1.3.1. 생산자/소비자 관계

순차적 프로그램에서는 하나의 프로시저가 다른 프로시저를 호출하고 데이터를 넘겨주어도 두 프로시저들은 단일 프로세스에 속하는 것이므로 동시에 수행하는 것이 아닙니다. 그러나 서로 다른 프로세스끼리 데이터를 주고받는 것은 훨씬 복잡한데, 이러한 상황이 데이터 전송이 프로세스간 통신 (IPC, Inteprocess Commuication)의 한 예시입니다.

 

 이를 설명하기 위해 한 가지 관계를 가정해보도록 하겠습니다. 어떤 생산자 프로세스라는 것이 있는데 이 프로세스는 항상 정보를 생산합니다. 그리고 소비자 프로세스라는 것이 있는데 이 프로세스는 항상 정보를 소비하는 역할을 한다고 가정하겠습니다. 그리고 이 두 프로세스 간에는 주어진 데이터를 주고받기 위한 정수형인 공통의 변수 nBuffer를 통해서 통신한다고 가정해보겠습니다. 이때 생산자는 어떤 계산을 수행하여 nBuffer에다가 기록하게 되고 소비자는 nBuffer에서 그것을 읽어서 출력한다고 생각해보겠습니다.

 

 생산자와 소비자가 나란히 보조를 맞추어 진행될 수도 있지만, 둘의 속도 차이가 상당할 수도 있습니다. 만약 생산자가 nBuffer에다가 어떤 계산된 숫자를 넣자마자 소비자가 그것을 읽어내어 출력한다면 그 결과는 항상 올바른 숫자가 될 것입니다. 그러나 두 프로세스 간의 속도 차이가 다를 때, 소비자가 생산자보다 빨리 수행한다면, 즉 생산자보다 빠르게 nBuffer에 있는 값을 읽어낸다면 소비자는 생산자가 새로운 수를 계산해 내기 전에 같은 숫자를 두 번 이상 출력하는 현상이 나타날 수 있습니다.

 

 만일 생산자가 소비자보다 더 빨리 수행된다면 생산자는 소비자가 값을 읽기도 전에 있던 값 위에 새로운 값을 쓰게 되고 소비자는 이러한 문제점을 알지도 못한 채 몇 개의 데이터를 잘못 처리하게 될 수 있습니다. 생산자의 속도가 빠르다면 이와 같은 문제는 끊임없이 반복되고 많은 결과가 누락될 수 있습니다.

 

var exclusiveacess : semephore;
	ndeposited : smephore;
	nbuffer : integer;
procedure producerprocess;
	var nextresult : integer;
	begin
		while true do
			begin
				calculatenextresult;
				P(exclusiveaccess);
				nbuffer := nextresult;
				V(exclusiveaccess);
				V(ndeposited)
			end
	end
	procedure comsumerprocess;
		var nextresult : integer;
		begin
			while true do
				begin
					P(ndeposited);
					P(exclusiveaccess);
					nextresult := nbuffer;
					V(exclusiveaccess);
					write (nextresult)
				end
		end;
	begin
		smeaphoreinitialize(exclusiveaccess, 1);
		smeaphoreinitialize(ndeposited, 0);
		parbegin
			producerprocess;
			consumerprocess
		parend
	end.

 

 

 위 코드에서 해결해야 할 문제는 생산자와 소비자가 서로 협력하여 nbuffer에 쓰여진 결과가 소실되거나 중복되는 일이 없도록 하는 것입니다. 이 사례에서는 생산자/소비자 문제를 semaphore를 이용해서 구현하는 동시 프로그램을 제시하였습니다. 여기서 우리는 두 개의 semaphore를 사용하고 있는데, exclusive-acess는 공용 데이터에 대한 상호배제 엑세스를 위한 것이고, ndeposited는 동기화를 구현하기 위한 것입니다.

 

---

 

1.3.2. 판독기/기록기 관계

 데이터 객체(data object), 예컨데 파일이나 레코드 같은 정보들은 여러 병행 프로세스 간에 공요될 수 있습니다. 이러한 프로세스 중 일부는 다른 것들이 공유 객체를 갱신하는 작업, 즉 읽거나 쓰는 작업을 하기 원하는 때에 동시에 객체의 내용을 읽으려 할 수 도 있습니다. 이러한 동시 접근은 Bernstein 조건을 침해하게 될 것입니다.

 

---

 

Bernstein 조건이란?

번스타인 조건(Bernstein's Conditions)은 병렬 컴퓨팅에서 두 작업이 서로 독립적으로 실행될 수 있는지를 판단하기 위한 수학적 기준을 말합니다. 이 조건은 두 작업 간의 데이터 종속성을 분석하여, 동시에 실행해도 결과에 영향을 주지 않는지를 결정하는 데 사용됩니다.

 

번스타인 조건의 세 가지 요소

①   입력 집합(Data Read Set): 각 작업이 읽는 데이터의 집합입니다.

②   출력 집합(Data Write Set): 각 작업이 쓰는 데이터의 집합입니다.

③   교차 조건(Cross Conditions): 두 작업이 독립적으로 실행되기 위해 다음 세 가지 조건을 모두 만족해야 합니다:

• 작업의 출력 집합과 두 번째 작업의 입력 집합이 교집합이 없어야 합니다.
• 작업의 출력 집합과 첫 번째 작업의 입력 집합이 교집합이 없어야 합니다.
• 두 작업의 출력 집합 간에 교집합이 없어야 합니다.

 

이러한 조건을 모두 만족하면, 두 작업은 서로 독립적이며 병렬로 실행될 수 있습니다.

반대로, 하나라도 위반되면 데이터 종속성이 존재하여 병렬 실행 시 올바르지 않은 결과를 초래할 수 있습니다.

 

예컨대,  작업 A가 변수 X를 읽고 변수 Y를 쓴다고 가정하고, 작업 B가 변수 Y를 읽고 변수 Z를 쓴다면, 작업 A의 출력 집합은 {Y}, 작업 B의 입력 집합은 {Y}입니다.

 

이 경우, A의 출력과 B의 입력이 겹치므로 번스타인 조건을 만족하지 않습니다.

따라서, 작업 A와 B는 병렬로 실행될 수 없습니다. 번스타인 조건은 병렬 알고리즘 설계 시 중요한 개념으로, 작업 간의 데이터 종속성을 분석하여 효율적인 병렬 처리를 가능하게 합니다.

 

---

 

 이와 같은 문제를 발생시키지 않기 위해서는 기록기(Writers)가 공유 대상물에 대한 배타적 접근을 하도록 해야 합니다. 이러한 유형의 동기 문제가 판독기/기록기(readers/writers) 문제로 정의되었습니다.

  

 판독기/기록기(Readers/Writers) 문제는 여러 가지 변형이 있는데 모두가 우선 순위를 포함합니다. 가장 간단한 것은 판독기/기록기 문제 1이라고 논의되는 경우로 기록기가 이미 공유 객체를 사용할 수 있도록 허락되지 않았다면 판독기는 대기하지 않습니다. 다시 말해 어떠한 판독기도 기록기가 대기중이라는 이유로 다른 판독기가 끝나기 만을 기다리지 않는다는 것을 의미합니다. 다른 사례로는 판독기/기록기 문제2라고 논의되는 상황으로서 일단 기록기가 준비되었다면 기록을 가능한 빨리 수행할 수 있도록 하는 것입니다. 다시 말해 기록기가 대상물을 접근하기 위해 대기중일 때에는 어떠한 새로운 판독기도 읽기 시작할 수 없게 됩니다.

 

 위에 제시한 두 문제 상황에 대하여 모든 방법은 기아 상태를 낳을 수도 있음을 주목해야 합니다. 첫번째 경우에서는 기록기가 기아 상태에 빠질 수 있고, 두번째의 경우에서는 판독기가 기아 상태일 수도 있습니다. 이러한 이유로 인해 문제의 다른 변형이 제기되기도 하였습니다. 이번 포스팅에서는 판독기/기록기 문제 1에 대한 방법에 해결을 설명하도록 하겠습니다. 우선 판독기/기록기 문제 1에서 판독기(Reader) 프로세스는 다음의 자료 구조를 공유합니다.

 

var mutex, wrt : semaphore;
readcount : integer;

 

 

 세마포어(semaphore) mutex와 wrt는 1로 초기화 됩니다. 반면에 readcount는 0으로 초기화 됩니다. 세마포어 wrt는 판독기(reader)와 기록기(writer) 모두에게 공통입니다. mutex 세마포어는 변수 readcount가 갱신되는 중에 상호배제를 위하여 사용됩니다. readcount는 얼마나 많은 프로세스 가 현재 객체(object)를 읽고 있는 지 표시합니다. 세마포어 wrt는 기록기를 위한 상호배제 세마포어로 동작합니다.

 

 이는 역시 임계영역(Critical Section)으로 들어가고 나가는 처음고 kaos 나중의 판독기에 의해서 사용됩니다. 이는 다른 판독기(reader)가 임계 영역 내에 있는 동안에는 들어가고 나오는 판독기에는 사용되지 않습니다.

 

판독기 프로세스의 일반적 구조는 아래와 같습니다.

 

	P(mutex) ;
		readcount := readcount + 1 ;
		if(readcount = 1) then P(wrt) ;
	V(mutex) ;
		…
		reading is preformed
	P(mutex) ;
		readcount := readcount - 1;
		if (readcount = 0) then V(wrt) ;
	V(mutex) ;

 

기록기 프로세스의 일반적 구조는 아래와 같습니다.

 

	P(wrt) ;
		…
		writing is performed
		…
	V(wrt) ;

 

 이와 같이 기록기가 임계 영역에 존재하고 n개의 판독기가 대기중일 때에는 n-1 판독기가 mutex에 대한 큐에 들어있는 동안 한 개의 프로세스는 wrt에 대한 큐에 들어 있음을 주목해야 합니다. 또한 기록기가 V(wrt)를 수행하는 도중, 대기 중인 판독기나 대기 중인 하나의 기록기 중에서 실행을 계속할 수 있는데, 이러한 선택은 스케줄러에 의해 결정됩니다.

 

---

참고 자료

• 김완규, 고정국, 진광윤, 최신형, 하성권, 허덕행 | 핵심 운영 체제론 | 두양사