[Operating System] Synchronization Examples

hina·2023년 7월 12일

Operating System

목록 보기

8/9

Readers-Writers Problem

Readers-Writers: 공유 데이터 set에 접근하는 프로세스
- Readers: 읽기만 가능한 프로세스들
- Writers: 읽기와 쓰기가 모두 가능한 프로세스들

Problem

Readers 끼리는 동시에 데이터를 읽는 것을 허용한다.

Wrtier는 shared data에 하나의 writer만 들어갈 수 있다. 이때 reader도 들어갈 수 없다.
-> 어떻게 readers와 writers를 관리하는가에 따라 많은 변수가 존재한다.

Shared data
- data set
- Semaphore rw_mutex - 1로 초기화
- Semaphore mutex - 1로 초기화
- integer read_count - 0으로 초기화
  - read_count가 0일 때만 write 가능

가정
- read하고 있는 경우 다른 reader도 동시에 read 가능하다.
- read하고 있는데 writer가 들어오면, writer는 read가 끝날 때까지 waiting 한다.
- write하고 있는 경우, read와 write 모두 대기한다.

Readers-Writers 구조

writer process

do {
	wait (rw_mutex);

	/* writing is perforemed */

	signal (rw_mutex);
} while (true)

reader process

do {
	wait (mutex); // read_count 에 접근 권한 얻기까지 대기
	read_count++; // read_count > 1이면, 이미 읽고 있던 프로세스가 있으므로
								// writer가 없음이 보장된다.
	if (read_count == 1) // reader가 처음으로 들어왔을 경우엔 보장할 수 없으므로
		wait(rw_mutex); // writer가 있다면 대기한다.
	signal(mutex); // read는 동시에 가능하므로, 기다리고 있던 reader들에게 신호 전송
	
	/* reading is performed */

	wait (mutex); // read_count 에 접근 권한 얻기까지 대기
	read_count--; // perform 완료

	if (read_count == 0) // read_count == 0 이므로, writer가 가능함
		signal(rw_mutex); // write
	signal(mutex); // write가 끝나면 다시 read. read_count 접근 권한 해제
} while (true)

Readers-Writers Problem Variations

첫 번째 버전: writer가 공유 데이터를 사용할 수 있는 권한이 없으면, reader는 대기하지 않는다.
두 번째 버전: 한 명의 writer가 준비되면, 가능한 바로 일을 수행하도록 reader는 stop한다.
두 버전 모두 starvation이 발생한다. -> 더 정교한 설계가 필요하다.
일부 시스템에서는 reader-writer lock을 제공하는 커널로 이 문제를 해결한다.

Dining-Philosophers Problem

철학자는 그들의 삶을 생각하기, 먹기만 하며 보낸다.
본인의 이웃과 상호작용할 수 없으며, 한 번에 젓가락을 하나씩 집어 젓가락이 2개가 되면 밥을 먹을 수 있다.
이 케이스에는 5명의 철학자가 있다.

Dining-Philosophers Problem Solution 1

Solution 1: Semaphore를 이용한 해결 방법
- Semaphore 변수를 공유한다. semaphore chopstick[5]
Philosopher i의 구조

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

Problem: Deadlock 발생
- 5명의 철학자가 동시에 첫 줄을 실행하여 모두가 하나씩 젓가락을 들면, 모두가 다음 젓가락을 기다리는 무한 대기상태에 빠진다. 두 젓가락을 얻어야 내려놓을 수 있다.

How to avoid deadlock?
1. 철학자 수를 4명으로 줄이거나 젓가락을 6개로 늘린다.
2. 양쪽을 집을 수 있는 상황에서만 젓가락을 집는다. -> 젓가락을 집는 과정 자체가 임계영역이 된다.
3. 젓가락을 모두 같은 방향으로 집지 않고 방향을 바꾼다.

Dining-Philosophers Problem Solution 2

Solution 2: Monitor 해결 방법
- enum {THINKING, HUNGRY, EATING} state[5]
  - 철학자 i는 본인 양쪽의 철학자가 EATING 상태가 아니어야 state[i]가 EATING 상태가 될 수 있다.
- condition self[5]: 철학자 i는 그가 HUNGRY 상태지만 젓가락을 집을 수 없을 때 대기한다.

code

monitor DiningPhilosophers {
	enum {THINKING, HUNGRY, EATING} state[5];
	condition self[5];

	void pickup(int i) {
		state[i] = HUNGRY;
		test(i);
		if (state[i] != EATING) self[i].wait; // test하고 왔는데 eating이 아니라면
																					// 당장 먹을 수 없는 상황이므로 wait
	}
	void putdown(int i) {
		state[i] = THINKING;
		test((i+4)%5);
		test((i+1)%5);
	}

	void test(int i) {
		if ((state[(i+4)%5] != EATING) && (state[(i+1)%5] != EATING) &&
				(state[i] == HUNGRY)) {
			state[i] = EATING;
			self[i].signal();
		}
	}
	initialization_code() {
		for (int i = 0; i < 5; i++)
			state[i] = THINKING;
	}

deadlock은 발생하지 않지만, starvation은 발생할 수 있다. -> 계속 못 먹는 철학자 발생

Synchronization Example

Linux Synchronization
- kernal 2.6 버전 이전에는 disables interrupts를 임계 영역에 이용했다.
- 2.6 버전 이후에는, preemptive 방식이다.
Linux provides:
- Semaphores
- Atomic integers: atomic_t 타입과 atomic 연산
  - atomic_t counter; int value;
- Spinlocks