동기화

소프트웨어를 이용한 해결방법의 문제점

• 다중 스레드 또는 임계영역보다 복잡한 문제로 일반화하기가 쉽지 않음. 이를 위해 세마포어사용.
• 특히 원자적 연산에 대한 하드웨어 지원이 가능한 경우 효과적인 모니터사용.
• 세마포어 연산(P연산, V연산), 모니터 연산

3. 세마포어(Semaphores)

1. 세마포어 개요

세마포어 개요

동기화를 위한 도구

• 음이 아닌 정수값을 갖는 플래그 변수
• 다익스트라가 상호배제를 극복하기 위해 제안
• 세마포어의 유명한 예 : 열차 진행 여부를 알리는 차단기

 

세마포어 연산

세마포어 변수

1. 카운팅 세마포어 (Counting Semaphore)

• S의 크기 : 총 사용 가능한 자원의 갯수
• S는 자원의 개수로 초기화 됨
• S의 범위는 한정되어 있지 않음

2. 이진 세마포어 (Binary Semaphore, mutex)

• S는 0 또는 1만 가질 수 있다. 초기값은 1
• 시스템에서 상호배제를 제공하기 때문에 mutex라고도 불린다.

 

세마포어는 두 개의 표준 원자적 연산인 P연산, V연산으로 접근이 가능

P(S){
	while(S <= 9) no-op;
	S = S - 1;
}
      
V(S){
	S = S + 1;
}
      
P(S);
	임계영역
V(S);
	잔류영역

 

• P(S), V(S) 연산은 분리되지 않고 실행되어야 한다. (원자적 연산)
• 한 프로세스가 세마포어의 값을 변경하면 다른 프로세스는 동일한 세마포어를 변경할 수 없다.
• 세마포어를 변경하는 동안에는 인터럽트 되지 않고 실행되어야 한다.

문제점 : 바쁜대기 발생

Busy waiting(바쁜 대기)

프로세스가 공유자원에 접근하고자 할 때, 진입구역에서 공유자원과 다른 프로세스들의 상태를 판단하는 루프를 돌면서 계속 기다리는 것

->바쁜 대기를 해결하기 위한 세마포어 P(S)와 V(S)연산

P(S) : begin
			s.count := s.count - 1;
			if s.count < 0 then
			Begin
				[호출한 프로세스를 대기큐에 넣는다];
				block;
			end;
V(S) : begin
			s.count := s.count + 1;
			if s.count <= 0 then
			begin
				[대기큐에서 프로세스를 꺼낸다];
				wakeup;
			end;
		end;

최초에는 세마포어는 음수를 가질 수 없었으나, 위와 같이 구현하면 음수가 될 수 있다.

세마포어가 음수라는 의미는 대기하고 있는 프로세스의 수를 의미한다.

두 프로세스가 동시에 P(S), V(S)연산을 실행할 수 없도록 반드시 보장해야한다.

다중처리 환경에서 모든 프로세서에서의 인터럽트를 금지해야 한다.

위와 같은 block-wait 방식을 sleep lock이라고도 한다.

 

세마포어의 문제점

• 데드락 또는 기아 발생
• 우선순위 역전 현상

2. 세마포어를 이용한 동기화 문제

1. 생산자-소비자 문제

program producer_consumer;
var mutex : semaphore; 		//중개역할 - 이진 세마포어 (초기값 1)
var produced : semaphore; 	//소비자 완성품
var consumed : semaphore; 	//생산자 원재료
procedure producer; 		//생산자 프로세스
begin
	while true do
	begin
		[정보생산];
		p(consumed);
		p(mutex);
		[생산한 정보를 유한 버퍼에 넣는다];
		v(mutex);
		v(produced);
	end
end

procedure consumer;
begin
	while true do
	begin
		p(produced);
		p(mutex);
		[유한 버퍼에서 정보 하나를 가져온다];
		v(mutex);
		v(consumed);
		[정보소비];
	end
end

 

문제점

p(mutex);
p(consumed);

 

일 때 문제점

소비할 물건이 가득

1. 생산자 생산
2. 소비자 소비

문제점

p(mutex);
p(produced);

 

일 때 문제점

생산할 물건이 가득

1. 소비자 소비
2. 생산자 생산

판독자-기록자 문제

program read_writer;
var readers : integer; 			//판독자
var s, writing : semaphore; 	//기록자
procedure reader;
begin
	P(s);
	readers := readers + 1;
	if readers = 1 then P(writing);
	V(s);
		[데이터 읽음];
	P(s);
	readers := readers - 1;
	if readers = 0 then V(writing);
	V(s);
end;

procedure writer;
begin
	P(writing);
		[데이터 기록];
	V(writing);
end;
begin
	readers := 0;
	s := 1;
	writing := 1;
	[reader와 writer를 병행하여 실행한다];
end;

 

식사하는 철학자

procedure phiolsopher(i : integer)
begin
	[생각한다];
	P(forks[i]);
	P(forks[(i+1) mod 5]);
	[먹는다];
	V(forks[i]);
	V(forks[(i+1) mod 5]);
end;

begin
	forks[0] := 1; forks[1] := 1; forks[2] := 1;
	forks[3] := 1; forks[4] := 1;
	[philosopher(0), (1), (2), (3), (4)를 병행하여 실행한다];
end;

 

식사하는 철학자의 기본 조건

구분	설명	실 환경
환경	원탁에서 둥글게 앉아서 사이에 포크를 공유한다.	공유자원, 선형조건
행위	철학자는 먹거나 사색한다.	대기와 실행
행위 조건	반드시 2개의 포크로 식사를 한다. 다른 상대의 포크를 뺏을 수 없다. (비선점) 왼쪽 포크를 항상 먼저 잡는다. 하나의 포크를 가지면, 나머지 하나를 기다린다. 아무도 식사에 간섭하지 않는다.(점유와 대기) 식사를 마치면 포크를 내려놓는다.(비선점)	취득 후 실행 상호배제 점유와 대기 비선점

식사하는 상황의 문제점

• 한 번에 2명만 식사를 할 수 있다.
• 누가 어떤 포크를 가졌는지 신경쓰지 않고 자기 생각만 한다.

식사하는 철학자 문제 알고리즘의 문제점 : 교착상태

식사하는 철학자 교착상태 해결책

1. 최대 4명의 철학자만 동시에 앉을 수 있도록 한다. (n-1명만 식사) -> 예방
2. 홀수번째 철학자는 왼쪽을 짝수번째 철학자는 오른쪽 포크를 먼저 집는다. -> 회피
3. 한 명만 오른쪽에서 왼쪽 순서로 포크를 집는다.