OS-7-Process Synchronization

Race Condition

• S-box(Memory Address Space)를 공유하는 E-box(CPU Process)가 여럿 있는 경우 Race Condition의 가능성이 있음
• Multiprocessor system에서 공유 메모리를 사용하는 프로세스들이 커널 내부 데이터를 접근하는 루틴들 간에 발생할 수 있음

OS에서 Race Conditoin이 발생하는 경우

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

Case1. interrupt handler v.s kernel

• 커널 모드 running 중 interrupt가 발생하여 인터럽트 처리 루틴이 수행

  양쪽 다 커널 코드이므로 kernel address space를 공유하기 때문에 Race Condition이 발생할 수 있다

  커널 모드 running중에는 interrupt가 걸리는 것을 막아서 Race Condition을 피할 수 있다

Case2. Preempt a process running in kernel?

• 두 프로세스의 address space 간에는 data sharing이 없음

• 그러나 system call을 하는 동안에는 kernel address space의 data를 access하게 됨(share)

• 커널 작업 중간에 CPU를 preempt하면 Race Condition 발생

  

• 해결책: 커널 모드에서 수행 중일 때는 CPU를 preempt하지않고, 커널 모드에서 사용자 모드로 돌아갈 때 preempt한다

Case3. Multiprocessor

• 여러 CPU가 한 자원에 동시 접근한다 -> Race Condition

• Multi Processor인 경우 서로 다른 CPU가 접근하기 때문에 interrupt를 enable/disable로 해결되지 않는다

• 해결 방법

  1. 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법
  2. 커널 내부에 있는 각 공유 데이터를 접근할 때마다 그 데이터에 대한 lock/unlock하는 방법

Process Synchronization 문제

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

• 일관성(consistency) 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 매커니즘이 필요하다

• Race Condition

  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황

  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐

    

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

The Critical-Section Problem

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

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

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

해결 알고리즘 Case 1

• Synchronization variable

  • int turn;

  • initially turn = 0;

    

• mutual exclusion은 만족하나, progress를 만족하지 못함

  반드시 한번씩 교대로 들어가야만 한다. 임계 구역에 작업하는 프로세스가 없어도, 한 프로세스가 연속해서 들어가지 못한다

해결 알고리즘 Case 2

• Synchronization variable

  • boolean flag[2];

  • initially flag[] = false;

    

• mutual exclusion은 만족하나, progress를 만족하지 못함

  프로세스 둘 다 2행까지 수행 후에 끊임없이 서로에게 양보하는 상황 발생 가능

해결 알고리즘 Case 3 (Peterson’s Algorithm)

• algorithm 1 2 번을 조합함

  

• 두 프로세스의 임계영역 문제 해결조건을 모두 만족한다

  하지만 Busy Waiting!이다 (계속 CPU와 memroy를 쓰면서 wait)

Synchronization Hardware

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

  

• Mutual Exclusion with Test & Set

  

Semaphores

• 앞의 방식들을 추상화 시킴

• Semaphores S

  • integer variable

  • S는 자원의 갯수

  • 아래의 두 가지 atomic 연산에 의해서만 접근 가능

    

• 세마포어의 두가지 종류

  1. Counting Semaphore
     • 도메인이 0 이상인 임의의 정수값
     • 주로 resource counting에 사용
  2. Binary Semaphore (=mutex)
     • 0 또는 1 값만 가질 수 있는 semaphore
     • 주로 mutual exclusion (lock/unlock)에 사용

Critical Section Of n Processes

위의 방식은 busy-wait 방식으로 임계구역이 오래걸리는 작업일 경우 효율적이지 못하다 따라서 Block & Wake up 방식을 사용하는 방법도 있다

Block And Wake Up 구현

• Semaphore를 다음과 같이 정의한다

  <img width=”400” alt=”스크린샷 2021-07-23 오후 10 02 04” src=”https://user-images.githubusercontent.com/12459864/126785511-2912b40c-b763-4646-a1ea-

  

• block과 wakeup을 다음과 같이 가정

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

• Semaphore 연산

  

  value는 block과 wake up의 기준

Busy-wait vs Block/wakeup

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

Deadlock and Starvation

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

  

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

대표적인 Race Condition 문제

Bounded-Buffer Problem

• shared data

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

• Synchronization variables

  • mutual exclusion -> Need binary semaphore (Buffer의 사용 여부)

  • resource count -> Need integer semaphore (남은 empty/full buffer의 수 표시)

    

Readers-Writers Problem

• 한 프로세스가 DB에 write 중일 때 다른 process가 접근하면 안됨

• read는 동시에 여럿이 해도 됨

• solution

  • Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다
  • Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다
  • 일단 Wrtier가 DB에 접근 중이면 Reader들은 접근이 금지된다
  • Wrtier가 DB에서 빠져나가야만 Reader의 접근이 허용된다

• shared data

  • DB 자체
  • readcount; -> 현재 DB에 접근 중인 Reader의 수

• Synchronization variables

  • mutex -> 공유 변수 readcount의 mutual exclusion을 보장

  • db -> reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

    

Dining-Philosophers Problem

• 위의 solution의 문제점

  • Deadlock 가능성이 있다
  • 모든 철학자가 동시에 배가 고파져서 왼쪽 젓가락만 집을 경우

• 해결 방안

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

Monitor

• Semaphore의 문제점

  • 코딩하기 힘들다

  • 정확성의 입증이 어렵다

  • 자발적 협력이 필요하다

  • 한 번의 실수가 모든 시스템에 치명적인 영향을 미친다

    

• 모니터란?

  • 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct

    

  • 모니터 내에서는 한 번에 하나의 프로세스만이 활동 가능하다

  • 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음

  • 프로세스가 모니터 안에서 대기할 수 있도록 하기 위해 conditional variable 사용

    • condition x, y;

  • condition variable은 wait와 signal 연산에 의해서만 접근 가능

    • x.wait(); : x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지는 suspend된다

    • x.signal(); : x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다. Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다

      

      monitor에 프로세스가 작업중이면 외부 entry queue에서 대기한다

      monitor내부에서 condition x가 없으면 x에 관한 queue에서 대기한다

      내부에서 작업중인 프로세스가 없거나 작업중인 프로세스가 condition 대기 queue에서 sleep하고 있으면 외부 작업 큐에서 프로세스가 monitor를 작업한다

Monitor를 적용한 Bounded Buffer Problem

Monitor를 적용한 Dining-Philosophers Problem

참고

• 반효경 교수님 운영체제 강의