[OS] Process Synchronization

데이터의 접근

컴퓨터 시스템 안에서 데이터가 접근 되는 패턴이다

 

Race Condition

 두 개 이상의 프로세스가 데이터에 동시에 접근하려 할 때 race conditon이 발생한다

S-Box(memory address space)를 공유하는 E-box(CPU space)가 여러개 있는 경우 race condition의 가능성이 있다

 

 

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

1. kernel 수행 중 인터럽트 발생 시
2. Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
3. Multiprocessor에서 shared memory 내의 kernel data

 

1. interrupt handler vs kernel

count++ 과정 중간에 interrupt handler로 count-- 가 들어와서 결과적으로 원래 값과 동일하다고 생각할 수 있다. 하지만 1. load 에 저장된 값이 count-- 후의 값이 아니라 처음 값이기 때문에 interrupt 처리 후 다시 돌아와도 load 에 저장된 값을 2. Inc 후에 3. store 되어서 초기값에서 +1 만큼 커진 값이 된다.

커널모드 running중 interrupt가 발생하여 인터럽트 처리 루틴이 수행
-> 양쪽 다 커널 코드이므로 kernel address space 공유

 

2. Preempt a process running in kernel?

P(A)가 커널모드에서 작업을 수행 중인데 시간이 다 끝나 CPU를 P(B)에게 넘겨야하는 상황 -> race condition 발생

 

커널 모드에서 수행 중일 때는 CPU를 preempt 하지 않고, 커널 모드에서 사용자 모드로 돌아갈 때 preempt하게 해결가능!

 

3. Multiprocessor

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

multiprocessor의 경우 interrupt enable/disable로 해결되지 않음

 

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

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

 

Process Synchronization 문제

• 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생 시킬 수 있다
• 일관성(cosistency) 유지를 위해서는 협력 프로세스(cooperating process) 간의 실행 순서(orderly execution)를 정해주는 메커니즘 필요
• Race condition
  • race condition을 막기 위해서는 concurrent process는 동기화(synchronize) 되어야 한다

 

The Critical-Section Problem

• n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재

하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다!!

 

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

• Mutual Exclusion
  • 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
• Progress
  • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.

• Bounded Waiting
  • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.

 

Algorithm 1

극단적으로 P0는 critical sectoin에 빈번하게 들어가고 P1은 한번만 들어간다고 하면 P0는 영원히 못 들어갈 수 있

=> Progress 만족 X

 

Algorithm 2

flag를 통해서 critical section에 들어갈 의사를 표시한다

상대방 flag를 체크해서 상대방 프로세스가 critical section에 들어가 있으면 기다리고 아니면 들어간다

critical section에서 빠져나올 때 flag를 false로 바꿔주어 나왔다는 표시를 해준다

 

Pi가 flag를 표시했을때 Pj에게 CPU에게 빼앗기면 Pj도 flag를 표시하게된다

이런 상황에서는 Pi와 Pj 둘 다 flag = true인 상태지만 critical section에는 아무도 들어가 있지 않은 상태가 된다. while문에서 Pi와 Pj는 계속 대기하는 상태가된다

=> Progress 만족 X

 

Algorithm 3 (Peterson's Algorithm)

3가지 조건을 모두 만족한다 !

하지만 Busy Waiting(=Spin lock) 문제가 있음 : 계속 CPU와 memory를 쓰면서 wait하기 때문

 

 

Synchronization Hardware

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

critical section에 들어가기전에 lock을 걸고 들어가서 나올때 lock을 푼다

 

 

Semaphores

• 앞의 방식들을 추상화 시킴
• Semaphore S
  • integer variable
  • 아래의 두 가지 atomic 연산에 의해서만 접근 가능

변수 S : 자원의 개수

연산 P : 공유 데이터를 획득하는 과정

연산 V : 공유데이터를 다 사용하고 반납하는 과정

 

 

Critical Section of N-Processes

busy-wait는 효율적이지 못함(=spin lock)

 

 

Block / Wakeup Implementation

Semaphore를 다음과 같이 정의한다

block과 wakeup을 다음과 같이 가정

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

 

Semaphore 연산은 다음과 같이 정의됨

 

 

Busy-wait vs Block/wakeup

• Critical section의 길이가 긴 경우 Block/wakeup이 적당
• Critical section의 길이가 매우 짧은 경우 Block/wakeup 오버헤드가 더 커질 수 있음, Busy-wait가 유리
• 일반적으로는 Block/wakeup 방식이 더 좋음

 

 

Two Types of Semaphores

• Counting semaphore
  • 도메인이 0 이상인 임의의 정수 값
  • resource couting에 사용

• Binary semaphore (=mutex)
  • 0 또는 1 값만 가질 수 있는 semaphore
  • 주로 mutual exclusion (lock/unlock)에 사용

 

 

Deadlock and Starvation

Deadlock

: 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

 

Starvation

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

 

 

Bounded-Buffer Problem (Producer-Consumer Problem)

Shared data

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

Synchronization variables

• mutual exclusion -> Need binary semaphore
• resource count -> Need integer semaphore

 

 

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를 접근하는 코드의 mutual exclusion 보장을 위해 사용
• DB : Reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

writer가 지나치게 오래 기다리는 starvation 발생이 가능하다

 

 

Dining-Philosophers Problem

Deadlock 가능성이 있다 : 모두가 동시에 왼쪽 젓가락을 잡는 경우

 

해결법

• 4명의 철학자만 동시에 앉을 수 있도록 한다
• 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다
• 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 잡게 한다

 

 

Semaphore의 문제점

• 코딩하기 힘들다
• 정확성의 입증이 어렵다
• 자발적 협력이 필요하다
• 한 번의 실수가 모든 시스템에 치명적인 영향을 준다

 

 

Monitor

동시 수행 중인 프로세스 사이에서 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된 프로세스가 없으면 아무 일도 일어나지 않는다

 

Bounded-Buffer Problem