🌟 본 게시물은 이화여자대학교 반효경 교수님 강의를 참고로 작성한 게시물 입니다. 틀린 내용은 꼬옥 지적 부탁드립니다 ! 🌟

Process Synchronization(Concurrency)

‼️ 프로세스 동기화와 관련된 3가지 문제

Bounded-Buffer Problem
Readers and Writers Problem
Dining-Philosophers Problem

1. Bounded-Buffer Problem (Producer-Consumer Problem)

Bounded-Buffer Problem란 생산자와 사용자의 비율이 맞지않아서 사용자나 생산자가 무한히 대기하거나, 공유데이터에 동시에 접근하여 데이터 통일성이 깨질 수 있는 문제점을 얘기한다.
아래 내용은 이러한 문제점을 세마포어로 해결한 예시이다.

스크린샷 2022-03-28 오후 8 48 56

1.1 Bounded-Buffer의 문제점 해결 방안

✔️ Producer - 데이터를 버퍼에 채워넣는 역할

비어있는 버퍼가 있는 지 확인한다. (없을 경우 대기)
비어있는 버퍼가 있으면 공유데이터에 접근하고 lock을 건다.
비어있는 버퍼에 데이터 입력 및 버퍼를 조작한다
Lock을 해제한다.
Full Buffer를 하나 증가시킨다.

✔️ Consumer - 데이터를 사용하는 역할

full 버퍼가 있는 지 확인한다. (없으면 대기)
full 버퍼가 있을 경우 공유데이터에 접근하고 lock을 건다.
full 버퍼에서 데이터를 읽어오고 버퍼를 조작한다.
Lock을 해제한다.
Empty Buffer를 하나 증가시킨다.

‼️ 여기서 말하는 공유데이터는 ‼️

Buffer 자체 및 Buffer 조작 변수(empty/full buffer의 시작 위치)

1.2 세마포어를 적용한 동기화 기법 예제코드

Producer

Consumer

  
do {
	produce an item in x
	... 
	P(empty); /* 비어있는 버퍼의 수 확인 */
	P(mutex); /* 버퍼가 비어있으면 버퍼에 진입하고 lock */ 
	...
	add x to buffer
	...
	V(mutex); /* 버퍼 unlock */
	V(full);  /* full 자원을 증가시킴 */

} while(1)

  
do {
	P(full); /* 비어있지않은 버퍼의 수 확인 */
	P(mutex); /* 버퍼가 하나라도 비어있지 않으면 버퍼에 진입하고 lock */
	...
	remove an item from buffer to y
	...
	V(mutex); /* 버퍼 unlock */
	V(empty); /* 비어있는 버퍼의 갯수 증가 */
	...
	consume the item in y
	...
} while(1)

✔️ Synchrozination variables

semaphore empty = n; semaphore full = 0;
- 남은 full/empty의 buffer의 수 표시
semaphore mutex = 1;
- 공유 데이터의 상호배제를 위한 변수

2. Readers and Writers Problem

다수의 Readers Writer가 공용 데이터베이스에 접근하여 데이터 일관성을 해치는 문제점을 말한다. 이는 프로세스 동기화 기법으로 해결할 수 있다.
아래 내용은 프로세스 동기화 기법을 사용하여 해결한 예시이다.

2.1 Readers and Writers 문제점 해결 방안

✔️ Reader & Writer

Reader는 데이터를 읽기만 하는 프로세스
Writer는 데이터를 읽고 수정하는 프로세스

✔️ Reader & Writer Problem 방지

한 Writer가 임계구역에 진입한 상황일 때는 다른 프로세스가 임계구역에 접근하게 해선 안된다.
- 일단 Writer가 공유데이터에 접근 중이면 다른 Writer나 Reader들은 접근이 금지된다.
- Writer가 공유데이터에서 빠져나가야만 Reader의 접근이 허용된다.
Reader는 여럿이 임계구역에 접근해도 된다. 하지만 Reader가 접근 중일 때 Writer가 접근하게 해선 안된다.
- Writer는 대기 중인 Reader가 하나도 없을 때 공유데이터 접근이 허용된다.
Writer가 공유데이터에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 임계구역에 접근하게 해준다

2.2 세마포어를 적용한 동기화 기법 예제코드

✔️ Shared data

int readcount = 0
DB 자체

✔️ Synchronization variables

semaphore mutex = 1;
semaphore db = 1;

Writer

Reader

  
P(db);
...
writing DB is performed 
...
V(db);

  
P(mutex); /* 동시에 다른 reader가 readcount를 변경하는 문제가 발생하지 않도록 lock */
readcount++;
if(readcount == 1) P(db); /* 최초의 접근일 경우 writer가 접근 못하도록 db 봉쇄 */
V(mutex); /* readcount unlock */

‼️ 하지만 위 코드와 같은 해결방법은 stavation 발생 위험이 있음 ‼️

예를 들어 writer가 대기 중일 때 reader가 끈임없이 진입하게 되면 wrtier가 무한히 대기하게 되는 현상이 발생한다.

단순한 프로세스 동기화 예제일 뿐 최적의 해결방법이 아니기 때문에 참고만 하자.

3. Dining-Philosophers Problem (식사하는 철학자 문제)

하나 이상의 프로세스가 공유데이터 중 서로에게 필요한 자원을 하나씩만 가지고 양보하지 않아서 Deadlock 이 발생할 수 있는 문제
아래 예제를 참고하여 어떤한 경우에 문제가 발생하는지 알아보고 어떻게 해결하는지 알아보자

[문제 발생 예제 코드]

✔️ Synchronization variables

semaphore chopstick[5]
- 배열의 모든 값을 1로 초기화 했다고 가정한다

Philosopher i

  
do {
	P(chopstick[i]);
	P(chopstick[j + 1] % 5);
	...
	eat();
	...
	V(chopstick);
	V(chopstick);
	...
	think();
	...
} while(1);

스크린샷 2022-03-29 오전 9 25 43

✔️ 위 예제 코드의 문제점

모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우 아무도 먹지 못하는 문제가 발생한다.
Deadlock 발생 위험이 있다.

[해결방안 예제 코드]

✔️ Synchronization variables

enum {thinking, hungry, eating} state[5];
semaphore self[5] = 0;
semaphore mutex = 1;

Philosopher i

  
/* 실행메소드 */
do {
	pickup(i);
	eat();
	putdown(i);
	think();
} while (1);

void pickup(int i) {
	P(mutex);
	state[i] = hungry;
	test(i);
	V(mutex);
	P(self[i]);
}

void pickdown(int i) {
	P(mutex);
	state[i] = thinking;
	test((j+4) % 5);
	test((j+1) % 5);
	V(mutex);
}

/* 대상 철학자의 오른쪽과 왼쪽 철학자가 식사중인지 검사하고 대상 철학자가 배고픈 상태일 때 식사를 허용한다. */
void test(int i) {
	if(state[(j+4) & 5] != eating && state[i] == hungry && state[(i + 1) % 5] != eating ) {
		state[i] = eating;
		V(self[i]);		
	}
}

✔️ 해결 방안

4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다
젓가락을 두 개 모두 잡을 수 있을 때에만 젓가락을 집을 수 있게 한다
비대칭
- 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록

‼️ 여태까지의 예제코드를 살펴봤을 때 Semaphore의 문제점 ‼️

코딩하기 힘들다
정확성(correctness)의 입증이 어렵다
자발적 협력(voluntary cooperation)이 필요하다
한번의 실수가 모든 시스템에 치명적 영향을 끼친다.

💡 예시 1번

💡 예시 2번

  
V(mutex)
Critical Section
P(mutex)

  
P(mutex)
Critical Section
P(mutex)

[예시 1번]

Wait 시점과 Signal 시점이 반대가 되어 Mutual Exclusion이 깨진다.

[예시 2번]

자원을 해제하는 코드가 없기 때문에 서로 필요한 자원을 얻지 못하여 Deadlock 발생 위험이 있다.

4. Monitor

동시에 수행중인 프로세스 사이에서 추상 데이터 타입의 안전한 공유를 보장하기 위한 high-level synchronization construct이다. 기본적으로 Monitor는 여러 프로세스가 동시적으로 접근할 수 없기 때문에 lock, unlock이 필요없다. 이는 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 사라지기 때문에 프로그래머의 부담이 줄어든다고 할 수 있다.

✔️ Monitor

모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
프로세스가 모니터를 사용하다가 타이머 인터럽트가 발생하여도 다른 프로세스가 모니터에 접근하지 못한다. active한 프로세스가 0이 되거나 프로세스가 모니터 내부에서 잠들었을 때 다른 프로세스가 진입한다.
프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
condition x;
- condition value는 값을 가지지 않고 자신의 큐에 프로세스를 sleep 시키거나 깨우는 역할만 한다.
condition variable은 wait과 signal 연산에 의해서만 접근 가능
- x.wait();
  - x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend된다
- x.signal();
  - x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다. suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

4.1 모니터를 활용한 Bounded-Buffer Problem 문제 해결 방법

  
monitor bounded_buffer
{ int buffer[N];
	condition full, empty;

	void produce(int x) 
	{ if (buffer.size() == N) // 1
			empty.wait();  // 2
		else
			/* add x to empty buffer*/
			full.signal() ; // 3
		
	}

	void consume(int *x) 
	{ if (buffer.size == 0) // 1
				full.wait();      // 2
		else 
			/* remove an item from buffer an store it to */
			empty.signal();     // 3
	}

}

앞에 소개한 Bounded-Buffer 문제를 모니터로 변경한 소스코드이다. 모니터는 한 프로세스만 접근할 수 있으므로

세마포어처럼 공유변수에 lock/unlock 작업을 수행하지 않아도 된다.

✔️ produce(int x)

빈 버퍼가 있는 지 확인한다.
빈 버퍼가 없으면 empty큐에서 대기한다.
빈 버퍼가 있으면 버퍼에 데이터를 추가하고 full큐에 잠들어있는 프로세스 하나를 깨운다.

✔️ consume(int *x)

버퍼에 데이터가 있는 지 확인한다.
버퍼에 데이터가 없으면 full큐에 대기한다.
데이터가 있을 경우 버퍼에서 데이터 하나를 읽어오고 empty큐에 잠들어있는 프로세스 하나를 깨운다.

Reference

https://mangkyu.tistory.com/104

이화여자대학교 반효경 교수님 운영체제 강의

[운영체제 스터디] 프로세스 동기화 문제 3가지 해결방법과 세마포어 뮤텍스 차이