[유혁 교수의 운영체제] 10. 동기화의 고전적 문제들

21 May 2021 • OS

동기화의 고전적 문제들

동기화의 고전 문제 3가지

  • Bounded-buffer problem
  • Readers and writers problem
    • Solution 1
  • Dining philosophers problem
    • Solution 1
    • Solution 2

Bounded-buffer problem

  • N개의 버퍼에 여러 생산자와 여러 소비자가 접근
  • 생산자(producer) – 한번에 하나의 아이템을 생산해 버퍼에 저장
    • 동작 조건: 버퍼 내에 저장할 공간이 있는가?
      • Buffer의 상태가 full이면 대기
  • 소비자(consumer) – 버퍼에서 하나의 아이템을 가져옴
    • 그리고 버퍼에서 삭제
    • 동작 조건: 버퍼 내에 소비할 아이템이 있는가?
      • Buffer의 상태가 empty이면 대기
  • 생산자와 소비자가 충돌없이 버퍼를 접근할 수 있도록
    • 버퍼 – critical section

Bounded-buffer problem 도식

Bounded-buffer problem 구현

  • Buffer의 구현
    • 1차원 배열로 구현
    • Boolean Buffer[n];
    • 초기화
      • Buffer[0…n-1] = empty
  • 생산자 operation
    • Buffer 배열 중, empty인 버퍼 찾아 full로 바꿈
    • Buffer[m] = full
  • 소비자 operation
    • Buffer 배열 중, full인 버퍼 찾아 empty로 바꿈
    • Buffer[m] = empty

Bounded-buffer problem 세마포

  • 문제 해결을 위한 세마포
    • Empty: 버퍼 내에 저장할 공간
      • 생산자의 진입을 관리
    • Full: 버퍼 내의 소비할 아이템
      • 소비자의 진입을 관리
    • Mutex: 버퍼에 대한 접근을 관리
      • 생산자, 소비자가 empty, full 세마포를 진입할 경우, buffer의 상태 값을 변경하기 위한 세마포
  • 세마포 value의 초기값
    • full = 0
      • counting 세마포
    • empty = n // buffer에 empty인 entry가 n개
      • counting 세마포
    • mutex = 1
      • binary 세마포

생산자 프로세스

do {
	...
	
	wait(empty); // 버퍼에 적어도 하나의 공간이 생기기를 기다림
	wait(mutex); // critical section에 진입하기 위해 기다림
	...
	
	produce an item in nextp
	nextp++;
	...
	
	signal(mutex); // critical section에서 빠져나왔음을 알림
	signal(full); // 버퍼에 아이템이 있음을 알림
} while(1);

소비자 프로세스

do {
	wait(full); // 버퍼에 적어도 하나의 아이템이 채워지기를 기다림
	wait(mutex);
	...
	remove an item from buffer;
	nextc++;
	...
	
	signal(mutex);
	signal(empty); // 버퍼에 하나의 빈 공간이 생겼음을 알림
	...

} while(1);

Q : 세마포를 wait, signal 말고 이외의 기능을 할 수록 설계할 수도 있나요? A : 안된다.

Q : bounded buffer problem에서는 그러면 read와 write 모두 mutex라는 binary 세마포를 잡을 수 있을 때만 critical section에 들어갈 수 있기 때문에 concurrency가 없다고 보면 되나요? A : mutex라는 binary 세마포에 의해 concurrency가 제한되어있다고 할 수 있다. 이를 개선하기 위해서는 버퍼의 모든 자리에 각각의 세마포를 두거나 등등 다양한 방법이 있을 것이다.

동기화 알고리즘 설계하는 methodology

  • 동기화 문제를 서술
    • 동작 조건을 명시하면서
  • 사용할 세마포를 설계
    • 몇 개를 사용할지
      • 앞에 Bounded-Buffer problem은 세마포 1개로도 구현이 가능하다. mutex, full, empty를 커버하는 마스터 세마포를 두고, 나머지를 모두 critical section으로 취급하는 것이다.
        • 그러나 이 방식은 concurrency가 배제된다. counting 세마포가 있던 지점이 모두 하나의 binary 세마포 안의 critical section이 되기 때문이다.
    • 무엇을 protect할지 고려
  • 알고리즘 구현
    • 위 세마포를 사용하여 pseudo-code로 구현한다.
    • Deadlock 대하여 고려한다.
  • 검증
    • 초기 값, starvation 체크
      • starvation : 특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태, 기아 상태

Readers-Writers Problem

  • 여러 Readers와 Writers가 하나의 공유 데이터를 읽거나 쓰기 위해 접근
  • Readers - 공유 데이터를 읽는다.
    • 여러 Reader는 동시에 데이터를 읽을 수 있다.
  • Writers - 공유 데이터에 쓴다.
    • Writer가 데이터를 수정하기 위해서는, reader 혹은 다른 writer가 작업을 하고 있지 말아야 한다.

Readers-Writers Problem 도식

Bounded-Buffer Problem과의 차이점

Bounded-Buffer에서 소비자는 reader가 아니라 writer였으므로 reader는 존재하지 않았지만 Readers-Writers에서는 Reader가 엄연히 존재하며 이들에 대해서는 mutex 만족할 필요가 없다.

Readers-Writers Problem Solution1

  • 문제 해결을 위한 자료구조와 세마포
    • int readcount : 버퍼에 현재 접근하는 Reader 숫자
    • semaphore wrt : Writers간 동기화를 위한 세마포
    • semaphore mutex : Readcount와 wrt의 접근이 원자적으로 수행됨을 보장하기 위한 세마포
  • 초기값
    • mutex = 1, wrt = 1, readcount = 0

Solution 1 - writer

wait(wrt);		// entry section
		...
		writing is performed
    ...
signal(wrt);	// exit section

Solution 1- reader

wait(mutex);
	readcount++;
	if (readcount == 1)
		wait(wrt); // writer 들어오지 못하게 함
signal(mutex);
		...
		reading is performed
		...
wait(mutex);
		readcount--;
		if (readcount == 0)
				signal(wrt);
signal(mutex);

Q : writer가 공유 데이터에 접근했을 때 reader의 접근을 막기 위해 mutex를 잡아야하지 않나요? A : 아니다. reader가 처음으로 들어올 때 writer가 이미 wait(wrt)를 한 상태라면, 들어오지 못한다.

문제점

  • Writer의 starvation
    • Readcount == 0일 때만 signal(wrt)가 수행되어 wait(wrt)로 대기하고 있던 writer가 수행될 수 있음
    • 첫 번째 Reader(Readcount == 1)가 wait(wrt)를 통과하면, 다른 Reader들은 wait(mutex)에 대한 signal(mutex)만 통과하면 writer에 관계없이 계속해서 진입할 수 있다.
      • reader preference가 있음
    • 여러 Reader들이 계속해서 진입할 경우, Readcount는 0까지 떨어지지 않을 수 있다.
  • Writer의 starvation을 예방하는 solution이 존재함

Q : Writer의 starvation을 방지하는 방법에 대해 생각해봤는데, readcount = 10 과같이 초기화하여 reader process가 한번 접근할때마다 readcount– 하는 형식으로 풀수 있을까요? A : 좋은 아이디어지만, 10과 같이 인위적인 숫자를 넣지 않는 것이 좋은 알고리즘이다.

Dining-Philosophers Problem

  • 고전적인 동기화 문제
  • 5명의 철학자가 한 식탁에서 함께 식사를 하는 상황
  • 젓가락이 5개뿐이다
    • 자신의 바로 옆 젓가락만 집을 수 있다
    • 두 젓가락을 모두 집어야 식사를 할 수 있다.
    • 식사를 하고 난 다음에 두 젓가락을 모두 내려놓는다.
  • Deadlock과 Starvation이 발생할 수 있음
    • 모두들 자신의 오른쪽 젓가락을 동시에 집었을 경우

Dining-Philosophers Problem Solution1

  • 젓가락을 집을 때 동기화를 하는 방법

    • 자신의 왼쪽과 오른쪽 젓가락부터 집고 식사를 한다.

  • 세마포

    • chopstic[5] : 각 젓가락에 대한 동기화

  • 초기값은 모두 1

  • 철학자 프로세스

    do {
	...
	think
	...
  	
	wait(chopstick[i])
	wait(chopstick[(i+1)%5])
	...
	eat // critical section
	...
	signal(chopstick[(i+1)%5])
	signal(chopstick[i])
	...
} while(1);

  • 동시에 chopstick[i]을 잡으면 deadlock 발생

    • 모두가 왼쪽 손에 젓가락을 집고 오른쪽을 기다리고 있는 채로 무한정 대기하는 경우

Dining-Philosophers Problem 개선안

  • Deadlock의 해결방안들
    1. 한 번에 최대 4명의 철학자만 식탁에 앉도록 한다.
    2. 젓가락의 상태를 미리 검사하여 양 쪽의 젓가락이 모두 사용 가능할 때만 젓가락을 집도록 한다.
    3. 철학자에게 번호를 부여하여 홀수인 철학자는 왼쪽의 젓가락을, 짝수인 철학자는 오른쪽의 젓가락을 먼저 집도록 한다.
  • 위의 해결방안들은 starvation까지 해결해주지는 못함
    • 각각의 방안에 대해 starvation에 대한 고려를 추가할 수 있다.
      • 한 차례 굶은 철학자에게 우선권을 주는 방안

Dining-Philosophers Problem Solution 2

  • 양쪽의 젓가락을 한꺼번에 집는 방법
    • 젓가락의 상태를 미리 검사하여 양 쪽의 젓가락이 모두 사용 가능할 때만 젓가락을 집도록 하는 방법
  • 사용되는 자료구조
    • State[5] : 각 철학자의 상태(THINKING, HUNGRY, EATING)
  • 문제 해결을 위한 세마포
    • mutex : 젓가락을 집거나 놓는 수행을 critical section으로 관리하기 위한 세마포 - 초기값: 1
    • self[5] : 각각 젓가락 두 개를 잡는 세마포
      • 초기값: 0
      • self[i] 의미는 철학자 i가 HUNGRY 상태이더라도, 다른 젓가락 하나를 사용할 수 없을 경우 waiting을 하기 위한 세마포
  • 철학자 프로세스
do {
	...
	think
	...
	take_chopsticks(i);
	...
	eat // critical section
	...
	put_chopsticks(i);
	...
} while(1);

  • take_chopsticks

    take_chopsticks(int i)
{
	wait(mutex);
	state[i] = HUNGRY;
	test(i);
	signal(mutex);
	wait(self[i]);
}
    • Mutex를 통해 진입하여, test(i)를 통해 양쪽의 철학자 상태를 검사한 후, 자신이 먹을 차례를 기다린다.

  • put_chopsticks

    put_chopsticks(int i)
{
	wait(mutex);
	state[i] = THINKING;
	test(LEFT);
	test(RIGHT);
	signal(mutex);
}
    • Mutex를 통해 진입하여 test(LEFT), test(RIGHT)를 통해 양쪽의 철학자 상태를 검사한 후, 먹을 차례를 기다리는 철학자에게 signal을 보내준다.

  • test

    test(int i)
{
	if(state[i] == HUNGRY &&
		state[LEFT] != EATING && state[RIGHT] != EATING) {
			state[i] = EATING;
			signal(self[i]);
		}
}

해설

  • Solution2
    • 철학자 좌우 젓가락이 사용 가능할 때 critical section에 진입
      • 즉, i번째 철학자가 식사를 하기 위해서는 i-1(LEFT)과 i+1(RIGHT) 철학자가 EATING 상태가 아니어야 한다.
  • take_chopstick()과 put_chopstick()의 동작을 구체적으로 살펴보자

take_chopstick()

take_chopsticks(int i)
{
	wait(mutex);
	state[i] = HUNGRY;
	test(i);
	signal(mutex);
	wait(self[i]);
}
  • 식사할 조건
    • Test() 함수 안에서 검사하는 LEFT와 RIGHT의 상태가 EATING이 아니어야 한다.
    • Test()를 만족하면 signal(self[i])에 의해 self[i]의 값은 1이 되므로 wait(self[i])에서 block되질 않고, 식사를 진행한다.
      • self[i]의 초기값은 0임을 기억할 것

put_chopstick()

put_chopsticks(int i)
{
	wait(mutex);
	state[i] = THINKING;
	test(LEFT);
	test(RIGHT);
	signal(mutex);
}
  • 식사를 마치면, 좌, 우 철학자의 test() 함수를 실행한다.
    • 이 때, 철학자 L과 R은 i에 의해 take_chopsticks()에서 wait() 함수에 의해 대기중
    • 철학자 i에 의해 실행한 test(LEFT)
      • i와 LL의 상태를 확인
    • 철학자 i가 실행한 test(RIGHT)
      • i와 RR의 상태를 확인
  • 철학자 i가 식사중인 동안 LL 혹은 RR 철학자의 상태가 EATING으로 바뀐다하더라도, test(LEFT), test(RIGHT)에서 LL과 RR의 상태를 확인 후 signal을 수행하므로 동기화에 문제가 없다.

Q : 갑자기 햇갈려서 그런데 수업때 하는 동기화의 전제조건은 single core가 맞나요?? A : 이런 알고리즘은 싱글코어이든 멀티코어이든 상관없이 항상 critical section에는 하나의 프로세스만 들어가도록 해야 한다.

동기화 알고리즘 체크 요소들

  • Data consistency(mutex)가 확보되는지
  • Deadlock이 발생하는지
  • Starvation 가능성이 있는지
  • Concurrency를 얼마나 제공하는지
    • Global lock을 쓰면 문제는 간단하게 풀리지만, concurrency가 심하게 제한된다.
 컴퓨터 구조

Comments

Related Posts