Process Synchronization

동기화가 필요한 이유

OS에서 Race Condition이 언제 발생하는가?

1. Kernel 모드 running 중 interrupt가 발생하여 인터럽트 처리루틴이 수행

   →양쪽 다 커널 코드이므로 kernel address space 공유

   →Solution : disable/enable interrupt 기능

2. Process가 system call을 하여 kernel 모드로 수행 중인데 context switch가 일어나는 경우

   →Solution : 커널 모드에서 수행 중일 때는 CPU를 preempt하지 않음

3. Multiprocessor에서 shared memory 내의 kernel data

   →Solution 1 : 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법

   →Solution 2 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법

Process Synchronization 문제

• 공유데이터의 동시 접근(concurrent access)은 데이터의 불일치(inconsistency) 문제를 발생시킬 수 있다.
• 일관성(consistency) 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 메커니즘 필요
• Race condition
  • 여러 프로세스들이 동시에 공유 데이터에 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
• race condition을 막기 위해선 concurrent process는 동기화되어야 한다

The Critical-Section Problem(임계 구역 문제)

• n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
• Problem
  • 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

Initial Attempts to Solve Problem

두 개의 프로세스가 있다고 가정 P0, P1

프로세스들의 일반적인 구조

do{
	entry section - 이용해서 critical section을 락 걸어줌
	critical section
	exit section - 다쓰면 락 풀어줌
	remainder section
} while (1);

프로세스들은 수행의 동기화를 위해 몇몇 변수를 공유할 수 있다 → synchronization variable

프로그램적 해결법의 충족 조건

• Mutual Exclusion (상호 배제)

  • 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다

• Progress (진행)

  • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.

• Bounded Waiting(유한 대기)

  • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다 → Starvation이 생기지 않아야함

• 가정

  • 모든 프로세스의 수행 속도는 0보다 크다
  • 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.

해결 알고리즘

턴을 사용

위 알고리즘은 P0가 critical section을 사용하고 나온 뒤 P1이 critical section을 들려야 다시 턴이 넘어온다.

플래그를 사용해서 체크

턴과 플래그를 동시 사용

피터슨 알고리즘
→ 세 조건을 모두 충족하지만 계속 CPU와 메모리를 쓰면서 기다린다. (Busy Waiting = spin lock)

Synchronization Hardware

• 하드웨어적으로 Test & modify 를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결

Semaphores

• 앞의 방식들을 추상화시킴 - 추상 자료형
• atomic하게 공유자원을 획득하고 반납하기 위해 사용하는 추상적인 신호
• Semaphore S
  • integer variable
  • 아래의 두 가지 atomic 연산에 의해서만 접근 가능

P(S) → 공유데이터를 획득하는 과정

V(S) → 반납하는 과정

Critical Section of n Processes

Synchronization variable
semaphore mutex; // mutual exclusion / initially 1: 1개가 CS에 들어갈 수 있다

Process Pi
do {
		P(mutex);        // if positive, dec-&-enter, Otherwise, wait.
		critical section
		V(mutex);        // Increment semaphore
		remainder section
} while (1);

busy-wait 는 효율적이지 못함

Block / Wakeup Implementation

• Semaphore를 다음과 같이 정의

typedef struct
{
	int value;             // semaphore
	struct process *L;     // process wait queue
} semaphore;

• block과 wakeup을 다음과 같이 가정
  • block : 커널은 block을 호출한 프로세스를 suspend 시킴, 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
  • wakeup(P) : block된 프로세스 P를 wakeup시킴, 이 프로세스의 PCB를 ready queue로 옮김

Implementation

• Semaphore 연산이 이제 다음과 같이 정의됨

→ 일반적으로는 Block/wakeup 방식이 더 좋음

→ Critical Section의 길이가 매우 짧은 경우 Block/Wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음

Two Types of Semaphores

• Counting semaphore
  • 도메인이 0 이상인 임의의 정수값
  • 주로 resource counting에 사용
• Binary semaphore(=mutex)
  • 0 또는 1 값만 가질 수 있는 semaphore
  • 주로 mutual exclusion (lock/unlock)에 사용

Deadlock and Starvation

• Deadlock
  • 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
• S와 Q가 1로 초기화된 semaphore라 하자

두 자원을 필요로 하는 두 프로세스는 조건을 충족하지 못하고 무한히 상대방의 자원을 기다린다.

• Starvation
  • indefinite blocking. 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

Classical Problems of Synchronization

Bounded-Buffer Problem(Producer-Consumer Problem)

Shared data

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

Synchronization variables

• mutual exclusion → Need binary semaphore (shared data의 mutual exclusion을 위해)
• resource count → Need integer semaphore ( 남은 full/empty buffer의 수 표시)

→ 수도 코드로 표현

Synchronization variables
semaphore full = 0, empty = n, mutex = 1;

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);

	consumer the item in y

}while(1);

Readers-Writers Problem

• 한 process가 DB에 write중일 때 다른 process가 접근하면 안됨
• read는 동시에 여럿이 해도 됨
• solution
  • Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다
  • Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다
  • 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다
  • Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다
• Shared data
  • DB 자체
  • readcount // 현재 DB에 접근 중인 Reader의 수
• Synchronization variables
  • mutex // 공유 변수 readcount를 접근하는 코드(critical section)의 mutual exclusion 보장용
  • db // Reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

→ 수도 코드

Shared data

int readcount = 0;

DB;

Synchronization variables

semaphore mutex = 1, db = 1;

Writer

P(db);

writing DB is performed

V(db);

!Starvation 발생 가능

Reader

P(mutex);
readcount++;
if(readcount == 1) P(db); //block writer
V(mutex);          // readers follow

reading DB is performed

P(mutex);
readcount--;
if(readcount == 0) V(db); // enable writer
V(mutex);

writer가 읽을 수 있는 상태가 되기전에 reader가 계속 들어오면 writer가 굶어죽을 수 있음

→ 큐에 우선순위를 둬서 writer의 우선 순위를 점점 높여주면 된다

Dining-Philosophers Problem

Synchronization variables
semaphore chopstick[5];
//initially all values are 1

Philosopher i
do {
	P(chopstick[i]);
	P(chopstick[i+1]%5);

	eat();

	V(chopstick[i]);
	V(chopstick[i+1]%5);

	think();

} while (1);

• 위 solution의 문제점
  • Deadlock 가능성이 있다
  • 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우
• 해결방안
  • 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다
  • 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다
  • 비대칭
    • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록

Sol 2 수도코드

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

Philosopher i
do{
	pickup(i);
	eat();
	putdown(i);
	think();
} while(1);

Monitor

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

• 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct

• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
• Condition variable은 wait와 signal 연산에 의해서만 접근 가능
  • x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend 된다.
  • x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다. suspend된 프로세스가 없으면 아무 일도 일어나지 않는다