Process Synchronization

 

데이터의 접근

 

Race Condition

 

  • 1) 공유 메모리를 사용하는 프로세스들
  • 2) 커널 내부 데이터를 접근하는 루틴들 간(시스템콜)

 

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

 

1. Kernel 수행 중 인터럽트 발생 시

inturrupt를 disable시켜서 해결. 순차적으로 하도록!

 

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

 

3. Multiprocessor에서 shared memory 내의 kernel data

 

Process Synchronization 문제

 

  • 공유데이터 shared data의 동시 접근 concurrent access는 데이터의 불일치 문제 inconsistency를 발생시킬 수 있다.
  • 일관성 consistency 유지를 위해서는 협력 프로세스 cooperating process 간의 실행 순서 orderly execution를 정해주는 매커니즘 필요

 

Race Condition

 

  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
  • Race condition을 막기 위해서는 concurrent process는 동기화 Sycnhronize되어야 한다

Example of a Race Condition

  • 보통은 문제가 안생기지만, 공유데이터에 접근하는 등의 위의 예에서는 문제가 될 수도 있다.

 

The Critical-Section Problem

Critical-Section = 임계구역

 

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

이 문제를 어떻게 해결할까? 를 고민하는 챕터

 

Initial Attempts to Solve Probelm

 

  • 두개의 프로세스가 있다고 가정
  • 프로세스들의 일반적인 구조
do {
	entry section
	ciritical section
	exit section
	remainder section
} while (1);
  • 프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수를 공유할 수 있다 → synchronization variable

 

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

 

  • Mutual Exclusion(상호 배제)
    • 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.
  • Progress
    • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
  • Bounded Waiting(유한대기)
    • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.

* 코드로 작성된 문장의 고급언어이기 때문에 단일 instruction이 아니라서 CPU를 빼앗길 수 있는 상황을 가정

 

Algorithm 1

  • 문제점: Progress를 충족 못함

 

Algoritm 2

 

 

Algoritm 3 (Peterson’s Algoritm)

 

  • 턴과 플래그를 모두 사용
  • 상대방이 깃발과 턴을 모두 가지고있지 않을때만 대기하고 있음
  • 문제점: Busy Waiting(=spin lock) / 계속 CPU와 메모리 자원을 쓰면서 기다린다.

 

Synchronization Hardware

 

  • 하드웨어적으로 Test & Modify를 atomic(intruction 단위로 끊어)하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결된다.

 

Semaphores

 

  • 앞의 방식들을 추상화시킴
    • 추상자료형(object, operation) → 더 알아보기
  • Semaphore S
    • integer variable
    • 아래의 두가지 automic 연산에 의해서만 접근 가능

 

1. Busy Wait

Critical Section of n Processes By Semaphore - Spin Lock

 

  • 단점: Spin Lock
  • Block & Wakeup 방식의 구현도 가능 (=sleep lock)

 

2. Block & Await

 

Critical Section of n Processes By Semaphore - Block & WakeUp

  • 구체적인 구현(block/wakeup)
    • P: 자원반출 / V: 자원반납

 

어떤 방식이 더 나을까? (busy wait vs block wakeup)

 

  • Block/wakeup overhead versus Critical Section의 길이
    • Critical section의 길이가 긴 경우 Block Wakeup이 적당
    • Critical section의 길이가 매우 짧은 경우 Block/Wakeup 오버헤드가 Busy-wait오버헤드보다 더 커질 수 있음
    • 일반적으로는 Block/WakeUP 방식이 더 좋음

 

두가지 타입의 세마포어

 

  • 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된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
    • 식사하는 철학자 문제(데드락 문제도 발생할수 있음! 생각해보자)

Dining-Philosophers Problem

  • 해결방법
    • 자원의 획득 순서를 정의해주면 된다.(프로그래머가 유의해서 작성해야 할 문제임)

 

Bounded-Buffer Problem(생산자-소비자 문제)

 

  • 버퍼의 크기가 유한한 환경에서
  • 생산자 프로세스, 소비자 프로세스가 각각 여러개 있는 상황
  • 버퍼가 가득 찼을때는 생산자도 버퍼에 데이터를 쓰지 못함
  • 세마포어의 역할이 2가지
    • 동시 접근을 방해하기 위해(전체버퍼에 대한 접근을 막는건가?)
    • 가용자원을 표시하기 위해(생산자: 비어있는 버퍼, 소비자: 내용이 있는 버퍼)

  • 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);
	...
	consume the item in y
	...
} while (1);

 

Readers-Writers Problem

 

  • 한 프로세스가 DB에 write 중일 때, 다른 프로세스가 접근하면 안됨
  • read는 동시에 여럿이 해도 됨
  • 해결책
    • 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); // 공유변수 lock
readcount++;
if (readcount == 1) P(db); /* block writer */
V(mutex);
    ...
reading DB is performed
    ...
P(mutex);
readcount--;
if (readcount == 0) V(db); /* enable writer */
V(mutex):
  • Starvation을 어떻게 해결해야 하나?
    • Writer의 차례를 한번씩 주는걸로 해결할 수 있다.

 

Dining-Philosophers Problem

 

  • Synchronization Variables
    • semaphore chopstick[5] (모든 처음 값은 1]
  • Philosopher i
do {
	P(chopstick[i]);
	P(chopstock[(i+1) % 5]);
	...
	eat();
	...
	V(chopstick[i]);
	V(chopstick[(i+1) % 5]);
	...
	think();
	...
} while (1);
  • 위 코드의 문제점
    • Deadlock 가능성이 있다.
    • 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우
  • 해결방안
    • 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다
    • 젓가락을 두개 모두 집을 수 있을 때에만 젓가락을 잡을 수 있게
    • 비대칭
      • 짝수 철학자는 왼쪽 젓가락부터 잡도록, 홀수는 오른쪽 부터
      enum { thinking, hungry, eating } state[5];
      semaphore self[5]=0 ;
      semaphore mutex=1;
      
      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(mutext);
      }
      
      void pcickup(int i) {