운영체제 - Process Synchronization

Race condition

: 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐

Race condition이 발생하는 상황

(1) 커널 모드 실행 중 인터럽트가 발생하는 경우(둘 다 커널 코드이므로 kernel address space 공유)
=> 커널 모드에서 데이터를 다루고 있을 때는 인터럽트 처리를 하지 않게 함

(2) 프로세스가 system call을 하여 커널 모드로 수행 중인데 context switch가 일어나는 경우
=> 커널 모드에서 수행 중일 때는 할당 시간이 지나도 CPU를 뺏지 않게 함

(3) Multiprocessor에서 shared memory 내의 kernel data
=> 한 번에 하나의 CPU만이 커널에 들어갈 수 있게 함
=> 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock을 함

Critical Section (임계 영역)

: 공유 데이터를 접근하는 코드

The Critical-Section Problem

: n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

해결을 위한 충족 조건

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

해결책

Synchronization Hardware

: Critical section에 들어가는 프로세스는 lock을 획득하고(true), critical section을 빠져나올 때 lock을 방출(false)함으로써 동시에 접근할 수 없도록 한다

Semaphores

• Semaphore S : 자원의 개수(integer)
  P연산 : 공유 데이터를 획득하는 과정
  V연산 : 데이터를 반납하는 과정

  P(S) : while (S <= 0) do no-op
        S--
     ---critical section---
  V(S) : S++

• Busy wait(=spin lock)
  : Critical section에 진입해야 하는 프로세스는 진입 코드를 계속 반복 실행해야 하며, CPU를 낭비한다
• Block & wakeup
  • block : semaphore를 획득할 수 없으면 프로세스를 block시키고, 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
  • wakeup : 다른 프로세스가 semaphore를 반납하게 되면, block된 프로세스를 wakeup시킴
• Busy wait vs Block & wakeup
  • Critical section의 길이가 긴 경우 block/wakeup이 적당
  • Critical section의 길이가 매우 짧은 경우 block/wakeup의 오버헤드가 busy-wait 오버헤드보다 커질 수 있음
• Counting semaphore
  : Semaphore의 값이 임의의 정수 값. 주로 resource counting에 사용
• Binary semaphore(=mutex)
  : Semaphore의 값이 0 또는 1 (lock과 unlock)
• Deadlock
  : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상