동기화

1. 동기화

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

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

3. 세마포어(Semaphores)

1. 세마포어 개요

1. 세마포어 개요

   동기화를 위한 도구

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

2. 세마포어 연산

   1. 세마포어 변수

      1. 카운팅 세마포어 (Counting Semaphore)
         • S의 크기 : 총 사용 가능한 자원의 갯수
         • S는 자원의 개수로 초기화 됨
         • S의 범위는 한정되어 있지 않음
      2. 이진 세마포어 (Binary Semaphore, mutex)
         • S는 0 또는 1만 가질 수 있다. 초기값은 1
         • 시스템에서 상호배제를 제공하기 때문에 mutex라고도 불린다.

   2. 세마포어는 두 개의 표준 원자적 연산인 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) 연산은 분리되지 않고 실행되어야 한다. (원자적 연산)
      • 한 프로세스가 세마포어의 값을 변경하면 다른 프로세스는 동일한 세마포어를 변경할 수 없다.
      • 세마포어를 변경하는 동안에는 인터럽트 되지 않고 실행되어야 한다.

      문제점 : 바쁜대기 발생

3. 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이라고도 한다.

4. 세마포어의 문제점

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

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. 한 명만 오른쪽에서 왼쪽 순서로 포크를 집는다.