[운영체제] 6. Process Synchronization

• 데이터 접근
  
  Execution-Box: CPU, 컴퓨터내부, process
  Storage-Box: Memory, Disk, process 주소 공간

Process Synchronization Problem

공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다

일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process) 간의 실행 순서(orderly execution)를 정해주는 메커니즘 필요 => 조율

Race Condition

Storage-box를 공유하는 Execution-box가 여럿 있는 경우 발생 가능

여러 개의 process나 CPU가 동시에 공유 데이터를 접근하는 상황
데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 process에 따라 달라짐

• OS에서 race condition은 언제 발생하는가?

1. Kernel 수행 중 interrupt 발생 시

   1) kernel running
   2) interrupt 발생
   3) interrupt handler에서 load, sub, store => 1 감소
   ex) 10 -> 9
   4) kernel로 복귀
   5) kernel에서의 load: 이때 interrupt 결과인 9가 아니라 기존에 저장해둔 10을 load
   6) kernel에서의 add, store => 1 증가
   ex) 10 -> 11
   
   (10->9->10)이 아니라 (10->11)이 되어버림
   * kernel 사이의 context switch. 양쪽 다 kernel code이므로 kernel address space 공유

   => Solution: kernel의 running 중에 interrupt가 들어와도 kernel의 process가 끝날 때까지 interrupt 처리 X

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

   1) Process A(in usermode)의 system call
   2) kernel mode 전환
   3) A의 time quantum expires & Process B needs CPU
   => Process A는 CPU를 preempt 당함 (while in kernel)
   4) Process B의 할당 시간 종료
   5) Process A가 CPU 되돌려 받음
   두 process의 address space 간에는 data sharing X
   
   BUT! system call을 하는 동안, kernel address space의 data를 access하게 됨 (share)
   이 작업 중간에 kernel에서 running 중인 process의 CPU를 Preempt? => race condition 발생

   => Solution: kernel mode 수행 중일 때는 CPU를 preempt X. kernel mode에서 user mode로 돌아갈 때 preempt

3. Multiprocessor에서 shared memory 내의 kernel data

   
   어떤 CPU가 마지막으로 count를 store했는가? => race condition

   Multiprocessor의 경우 interrupt enable/disable로 해결되지 X

   => Solution
   1) 한 번에 하나의 CPU만 kernel에 들어갈 수 있게 하는 방법 (kernel 전체를 lock / unlock)
   2) kernel 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 lock / unlock을 하는 방법

단순히 P1 수행 중 timer interrupt 가 발생해서 context switch가 일어나서 P2가 CPU를 잡는다고 발생하는 문제가 아님. shared data를 사용 중이거나, kernel mode일 때 발생.

race condition을 막기 위해서 concurrent process는 동기화(synchronize)되어야 한다

The critical-section problem

n개의 process가 공유 데이터를 동시에 사용하기를 원하는 경우에 발생

Critical section: 각 code의 segment에서 공유 데이터를 접근하는 code

• Problem: 하나의 process가 critical section에 있을 때 다른 모든 process는 critical section에 들어갈 수 없어야 한다.

Solution

• 프로그램적 해결법의 충족 조건
  - Mutual Exclusion
  : 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
  - Progress
  : 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
  - Bounded Waiting
  : 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.

  가정
  - 모든 프로세스의 수행 속도 > 0
  - 프로세스들 간의 상대적인 수행 속도는 가정 X

• Initial Attemps to solve problem
  - Synchronization variable: 프로세스들이 수행의 동기화(synchronization)를 위해 공유하는 변수

  두 개의 process가 있다고 가정 P0, P1

do {
	entry section
    critical section
    exit section
    remainder section
} while(1);

• Algorithm 1
  - Synchronization Variable

  int turn;
  initially turn = 0;	// Pi can enter its critical section if (turn == 1)

      - Process P0

do {
	while (turn != 0);
    critical section	// my turn
    turn = 1;			// P1의 critical section 수행
    remainder section	// your turn
} while(1);

      - Process P1

do {
	while (turn == 0);
    critical section
    turn = 0;
    remainder section
} while(1);

Mutual exclusion (O) Progress (X)
과잉양보 : 반드시 한 번씩 교대로 들어가야만 함 (swap-turn)
P0이 turn을 P1의 값으로 바꿔줘야만 P1이 들어갈 수 있음
만약 특정 process가 더 빈번히 critical section을 들어가야 한다면?

• Algorithm 2
  - Synchronization Variable

  boolean flag[2];	// 들어가고자 하는 intention
  initially flag[모두] = false;	// no one is in critical section
  // Pi ready to endter its critical section if (flag[i] == true)

      - Process P0

do {
	// i = 0
	flag[i] = true;		// Pretend I am in
    // 여기까지 수행 후 context switch가 일어나면 Pi가 critical section에 아직 들어가지 않았는데도
    // Pj의 while문에 걸려서 더이상 진행하지 못한다.
	while (flag[j]);	// Is he also in? Then wait
    critical section
    flag[i] = false;	// I am out now
    remainder section
} while(1);

      - Process P1

do {
	// i = 1
	flag[i] = true;	
    // 밑에 while문과 순서를 바꾸면 서로 양보하느라 critical section에 못 들어가는 문제는 해결됨
    // 그러나 둘 다 들어가버리는 경우가 발생
	while (flag[j]);
    critical section
    flag[i] = false;
    remainder section
} while(1);

Mutual exclusion (O) Progress (X)
P0과 P1이 둘 다 flag[i] = true까지만 수행 후 critical section에 들어가지 못하고 끊임없이 양보 하는 상황 발생 가능

Peterson's Algorithm

• Combined synchronization variables of algorithms 1 and 2.
• Process Pi

do {
	flag[i] = true;	// 내가 들어가고자 함
    turn = j;	// 상대방 turn
	while (flag[j] && turn == j);	// 상대방이 들어가고자 하고, 상대방 차례일 때 wait
    critical section
    flag[i] = false;
    remainder section
} while(1);

Mutual exclusion (O) Progrss (O) Bounded Waiting (O)
Busy Waiting (=spin lock): 계속 CPU와 memory를 쓰면서 wait

• Test_and_Set
  : 하드웨어적으로 test & modify를 atomic(하나의 operation인것처럼)하게 수행할 수 있도록 지원하는 경우, 앞의 문제는 간단히 해결
  instruction 하나로 데이터를 읽고 쓰는 작업이 모두 가능하도록 하드웨어적 지원이 있으면 lock 문제 해결 가능

  Test와 Set 사이의 Context Switch

      - Synchronization Variable

	boolean lock = false;

      - Process Pi

do {
	while (Test_and_Set(lock));	// busy waiting
    critical section	// lock -> TRUE. false 전까지 계속 수행
    lock = false;	// SET
    remainder section
}

각자 lock = TRUE에서 critical section 수행
수행 종료 후, lock = FALSE => 다른 process lock = TRUE. 서로 번갈아가며 atomic 수행

Semaphore

추상자료형

• Busy Waiting Implementation
  : integer variable. P(S), V(S) 두 가지 atomic 연산(context switch 발생 x)에 의해서만 접근 가능

P(S):
	while (s<=0) do no-op; // wait
	S--;	// S: resource 개수 count
// if S is positive, decrement & enter.
// otherwise, wait until positive (busy-wait)
V(S):
	S++;

• Critical Section of n Processes
  - Synchronization variable

    semaphore mutex; 	// initially 1: 1개가 critical section에 들어갈 수 있다

      - Process Pi

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

busy-wait(=spin lock): 효율적 X. => block & wakeup(=sleep lock) 방식의 구현

• Block / Wakeup Implementation
  - Semaphore 정의

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

  - block: 커널은 block을 호출한 process를 suspend시킴
  이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
  - wakeup(P): block된 프로세스 P를 wakeup시킴
  이 프로세스의 PCB를 ready queue로 옮김

P(S):	// resource 획득 연산
	S.value--;	
    // 자원의 개수 X. '상황'을 나타냄. wakeup할 게 있는지 판단.
    // 음수: 누군가가 resource 기다리고 있음, 양수: resource 여분이 있어서 기다리지 않고 사용 중
    if (S.value < 0) {
    	add this process to S.L;	// wait queue에 linked list 연결
        block();	// suspend
    }

V(S):	// resource 반납 연산
	S.value++;
    if (S.value <= 0) {
    	remove a process P from S.L;
        wakeup(P);
    }

Busy-wait VS Block/Wakeup
: 일반적으로 Block/Wakeup 효율적. CPU 의미 있는 이용.
BUT! block/wakeup overhead가 있음
if critical section 길이 ⬆ : Block/Wakeup
                             ⬇ : Block/Wakeup 오버헤드가 busy-wait 오버헤드보다 커질 수 있음

• Semaphore 종류
  - Counting semaphore: 도메인이 0 이상인 임의의 정수값 -> resource counting에 사용
  - Binary semaphore(=mutex): 0 or 1 값만 가질 수 있음 -> mutual exclusion(lock/unlock)에 사용

Deadlock & Starvation

• Deadlock: 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상 (상호교차적) => 반드시 starvation 유발

  context switch. 서로의 것을 위해 무한히 wait

  ex) S, Q: 1로 초기화된 semaphore

  P0	P1
  P(S)	P(Q)
  P(Q)	P(S)
  ...	...
  V(S)	V(Q)
  V(Q)	V(S)

1. P(S)와 P(Q) 서로 하나씩 차지.

2. P0의 P(S)는 P1의 P(S)를, P1의 P(Q)는 P0의 P(Q)를 서로 기다리며 계속 wait

3. V에 와야 각자 release

   P(S) -> P(Q) 순으로 CPU 잡는다는 rule 만들면 deadlock 방지 가능

• Starvation: 프로세스가 suspend된 이유에 해당하는 semaphore queue에서 빠져나갈 수 없는 현상 (indefinite blocking)

Classic Problems of Synchronization

Bounded-Buffer Problem

임시로 데이터를 저장하는 공간인 buffer의 크기가 유한함
생산자-소비자 문제 (producer-consumer)

• Shared data: buffer 자체 및 buffer 조작 변수(empty/full buffer 시작 위치)
• Synchronization variables
  - mutual exclusion: need binary semaphore (for shared data's mutual exclusion)
  - resource count: need integer semaphore (to show the # of full/empty buffer)

semaphore full = 0, empty = n, mutex = 1;	// n: buffer size

• Producer

1. Empty buffer가 있나요? : 없으면 기다림
2. 공유데이터 lock
3. Empty buffer에 데이터 입력 및 buffer 조작
4. unlock
5. Full buffer 하나 증가

do { ...
	produce an item in x
    ...
    P(empty);	// 1. empty buffer 확인
    P(mutex);	// ring buffer 접근. 공유데이터 lock
    ...
    add x to buffer	// 3. 데이터 입력
    ...
    V(mutex);	// 4. unlock
    V(full);	// 5. full buffer 하나 증가
} while (1);

• Consumer

1. Full buffer가 있나요? : 없으면 기다림
2. 공유데이터 lock
3. Full buffer에서 데이터 꺼내고 buffer 조작
4. unlock
5. Empty buffer 하나 증가

do {
	P(full);	// 1. full buffer 확인
    P(mutex);	// 2. 공유데이터 lock
    ...
    remove an item from buffer to y	// 3. 데이터 제거
    ...
    V(mutex);	// 4. unlock
    V(empty);	// 5. empty buffer 증가
    ...
    consume the item in y
    ...
} while (1);

Semaphore 업무
1. producer와 consumer가 동시에 공유 buffer 접근 막기 위해 공유 buffer 전체에 lock/unlock을 걸어 배타적 접근 => binary semaphore
2. buffer가 비었을 때 producer or consumer가 내용을 만들거나 꺼내갈 buffer가 없으면 가용자원의 개수 count => integer semaphore

Readers-Writers Problem

한 process가 DB에 write 중일 때 다른 process 접근하면 X
write는 exclusion. BUT!! read는 동시에 여럿이 가능

1. Writer가 DB에 접근 허가를 아직 얻지 못한 상태: 모든 대기 중인 reader 다 DB 접근 가능
2. Writer는 대기 중인 reader가 하나도 없을 때 DB 접근 허용
3. Writer가 DB에 접근 중이면 reader 접근 금지
4. Writer가 DB에서 빠져나가야만 reader 접근 허용

• Shared data

int readcount = 0;	// 현재 DB에 접근 중인 reader의 수 => 나중에 다 빠져나가는지 확인해야함
DB 자체;

• Synchronization variables
  - mutex: 공유 변수 readcount 접근 code(critical section)의 mutual exclusion 보장
  - db: reader와 writer가 공유 db 자체를 올바르게 접근하게 하는 역할

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

Dining-Philosophers Problem

• Synchronization variables

semaphore chopsticks[5];	// initially all values are 1: 동시에 둘이 젓가락을 잡을 수 X. 무조건 한 명만.

• Philosopher i

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

Deadlock 의 가능성이 있음: 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우 => 오른쪽 젓가락은 아무도 집을 수 X

• Solutions

1. 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
2. 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.

enum { thinking, hungry, eating } state[5];	// 상태. 공유 변수
semaphore self[5] = 0;	// 다섯 명의 철학자가 젓가락을 두 개 다 잡을 수 있어서 잡을 권한을 줄것인가 여부. 0 => 없음 / 1 => 있음
semaphore mutex = 1;	// lock

Philosopher i:
	do {
    	pickup(i);
        eat();
        putdown(i);
        think();
    } while(1);
    
void putdown(int i) {
	P(mutex);
    state[i] = thinking;
    test((i+4) % 5);
    test((i+1) % 5);
    V(mutex);
}

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

// i가 젓가락 두 개를 다 잡을 수 있는 상태인지 test
void test(int i) {
	// (i+4) % 5 : 왼쪽 철학자 eating X && (i+1) % 5 : 오른쪽 철학자 eating X && hungry : 내가 지금 배고픈 상태
	if (state[(i+4) % 5] != eating && state[i] == hungry && state[(i+1) % 5] != eating) {
    	state[i] = eating;
        V(self[i]);	// 젓가락 잡는 권한 부여
    }
}

3. 비대칭: 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 한다.

Monitor

• Semaphore의 문제점
  - 코딩하기 힘들다 (sync 맞추기 hard)
  - 정확성 입증 어려움
  - 자발적 협력이 필요함
  - 한 번의 실수가 모든 시스템에 치명적 영향
  ex)

  V(mutex)
  Critical Seciton
  P(mutex)

  => Mutual Exclusion 깨짐

  P(mutex)
  Critical Section
  P(mutex)

  => Deadlock

Monitor (OOP와 유사)

동시 수행 중인 process 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
=> lock이 필요 없음

- 모니터 내에서는 한 번에 하나의 process만 활동 가능
- 프로그래머가 동기화 제약 조건(semaphore에서는 명시)을 명시적으로 코딩할 필요 X
- 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용

• Condition variable : 상태변수 (값을 가지는 변수가 아니라 어떤 조건을 만족하지 못하는 경우 process를 상태 변수 자신의 queue에 메달아두는 역할만 수행)
  wait와 signal 연산에 의해서만 접근 가능

 condition x,y;	

      - x.wait() : x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend된다
     - x.signal() : 정확하게 하나의 suspend된 프로세스 resume. suspned된 process가 없으면 nothing happens

monitor monitor-name {
	shared variable declarations
    // 한 번에 하나의 process만 수행
    procedure body P1(...){
    }
    procedure body P2(...){
	}
    ...
    procedure body Pn(...){
    }
    {
    	initialization code
    }
}

Semaphore VS Monitor

• Semaphore: 여러 프로세스 각각의 활동에 전적으로 의존. 프로그래머가 각각의 프로세스에 대한 공유 자원 접근 코드를 모두 올바르게 작성했을 때만 제대로 동작
  • P, V 연산: busy waiting / block & wakeup으로 구현 가능. block & wakeup은 OS에 의존해서 process 상태 변화시켜줌. => 세마포어 변수값 자체를 증가/감소
• Monitor: 공유 자원 사용 부분은 무조건 모니터 호출을 통해서만 가능하게 함. => 모니터가 전부 책임. 프로그래밍 언어 차원에서 지원해 줄 수 있는 기법. 객체지향 프로그램에서 공유자원을 정의하고 그 자원을 접근하는 코드는 공유자원 내부에서 정의해서 그 내부에서만 한 번에 하나씩 접근할 수 있게 제공하는 것.
  • wait, signal 연산: 모니터 자체가 처리. 모니터 안에서 기다리는 프로세스가 있는지 체크하는 루틴은 있지만 signal 연산 시 기다리는 프로세스가 없으면 condition variable 값을 증가시키는 일을 하지 않는다

Bounded-Buffer problem

Dining Philosophers problem

• 5명 중 4명이 식사를 끝내지 않을 시, 한 명은 계속 starvation

---

운영체제 - 반효경
http://www.kocw.net/home/cview.do?cid=3646706b4347ef09