운영체제 - 병행제어(6)

2020-10-03

OS를 공부하면서 정리를 한 내용들 입니다.

Classical Problems of Synchronization

동기화와 관련된 전통적인 문제는 3가지가 있습니다.

Bounded-Buffer Problem(Producer-Consumer Problem)
Readers and Writers Problem
Dining-Philosophers Problem

하나씩 알아봅니다.

Bounded-Buffer Problem(Producer-Consumer Problem)

공유 버퍼가 Bounded한, 유한한 크기를 가지는 버퍼입니다.

여기서 프로세스는 2가지 종류가 있습니다.

하나는 Producer, 생산자 프로세스이고

다른 하나는 Consumer, 소비자 프로세스 입니다.

생산자 프로세스는 데이터를 만들어서 버퍼내에 집어 넣어주는 역할을 하고,

소비자 프로세스는 데이터를 꺼내가는 역할을 하게 됩니다.

여기서 어떤 문제가 생길 수 있는가?

공유 버퍼의 비어있는 버퍼를 확인하고 생산자 프로세스가 비어있는 공간에 생산자 프로세스가 데이터를 집어 넣으려고 합니다.

해당 공간을 바라보고 있는 상태에서 프로세스가 CPU를 빼앗겼습니다.

이때 생산자 프로세스2가 나타나서 아까 바라보았던 공간에 데이터를 집어넣으려 한다면,

두 가지 데이터 중 하나는 유실이 될 수 있습니다.(공유 데이터 문제)

이 문제를 풀기 위해서는 바라보는 공간의 공유 버퍼를 LOCK을 거는 방식을 사용할 수 있습니다.

이것은 소비자 프로세스에서도 동일하게 적용할 수 있습니다.

Synchronization variables

semaphore full = 0, empty = n(버퍼의 갯수), mutex = 1(lock을 거는 세마포어);

Producer

do{
	...
	produce an item in x

	P(empty);
	P(mutex);
	...
	add x to buffer
	...
	V(mutex);
	V(full);

}while(1);

Consumer

do{
	P(full);
	P(mutex);
	...
	remove an item from buffer to y
	...
	V(mutex);
	V(empty);
	...
	consume the item in y
	...
}while(1);

Readers-Writers Problem

공유 데이터에 접근하는 프로세스는 2가지가 있습니다.

읽는 프로세스와 쓰는 프로세스

한 프로세스가 DB에 write 중일 때 다른 프로세스가 접근을 막는게 이 문제입니다.

그러나 문제를 해결하는데 있어서 간단히 생각하면,

Lock을 걸면 끝나지 않는가?

라고 생각할 수 있는데, 조금 더 효율성을 높이는 것이 목표입니다.

read는 동시에 여럿이 읽더라도 문제가 안생깁니다.

그럼에도 Lock을 걸어서 혼자만 접근 할 수 있도록 한다면 비효율적입니다.

해당 문제에서는 Readers에서는 여럿이 접근해도 상관이 없으나,

Writers에서는 접근할 때 배타적으로 접근이 가능하도록 하는 것이 문제입니다.

해결 방법은?

Writer가 DB에 접근 허가를 앚기 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다.
Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.

Synchronization variables

semaphore db = 1(db에 Lock을 거는), mutex = 1(lock을 거는 세마포어);

Writer

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

Writer

P(mutex);
readcount++;
if(readcount == 1) P(db);/*writer Block, reader Follow*/
V(mutex);
...
reading DB is performed
...
P(mutex);
readcount--;
if(readcount==0) V(db);/* enable writer*/
V(mutex);

Dining-Philosophers Problem

“식사하는 철학자” 라고 불리는 문제입니다.

각 철학자들은 식사 또는 철학에 대해 생각을 합니다.

식사를 하는 주기는 철학자 마다 다릅니다.

문제는 밥을 먹기 위해서는 젓가락이 2짝을 모두 가지고 있어야 식사가 가능한데,

젓가락은 하나씩 가지고 있고 하필 젓가락이 공유데이터입니다.

젓가락을 이용해 밥을 먹고있다면 젓가락을 빼앗긴 철학자도 있다는 뜻입니다.

Synchronization variables

semaphore chopstick[5]; /* Initially all values are 1 */

Philosophers i

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

해결 방법은?

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

-참고 KOCW 이화여자 대학교 반효경 교수님 : 운영체제 강의

« BOJ 1915 BOJ 2096 »