[운영체제](반효경) 7강. Process Synchronization

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에 들어가는 횟수에 한계가 있어야 한다.

💡 가정: 1) 모든 프로세스의 수행속도는 0보다 크다

              2) 프로세스들 간의 상대적인 수행속도는 가정하지 않는다

* 코드로 작성된 문장의 고급언어이기 때문에 단일 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) {