프로세스 동기화

데이터의 접근

데이터를 읽어와서 연산을 해서 저장하는 방식에서는 프로세스 동기화 문제가 발생!

Race Condition

S-box를 공유하는 E-box가 여럿 있는 경우 Race Condition의 가능성이 있음

Race condition이 발생할 수 있는 상황

• 멀티 프로세서 시스템
• 공유메모리를 사용하는 프로세스들
• 커널 내부 데이터를 접근하는 루틴들 간
  예: 커널모드 수행 중 인터럽트로 커널모드 다른 루틴 수행시

  유저레벨보다 커널모드에서 문제 발생 시, 문제가 더 심각함

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

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

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

3. Multiprocessor에서 shared memory내의 kernel data

Kernel 수행 중 인터럽트 발생

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

위 그림에선 interrupt handler의 count--가 동작하지 않고 count++만 처리된 결과 값이 저장됨

해결방법으로 커널과 관련된 작업이 수행중일 땐, interrupt가 들어와도 수행시키지 않고 그 작업이 끝난 후에 수행하도록 해결함

Prcoess가 system call하여 kernel mode로 수행 중인데 context switch 발생

커널 코드 실행중에서(카운트 값 증가) 프로세스 B로 넘어간 상황

프로세스 B에서 요청한 count++이 반영되지 않고 A에서 요청한 count++만 반영됨

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

멀티프로세서인 경우

해결책

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

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

Process Synchronization 문제

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

일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process)간의 실행 순서(orderly execution)를 정해주는 메커니즘 필요

Race condition

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

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

The Critical-Section Problem

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

Problem

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

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

• Mutual Exclusion(상호배제)

  • 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세슫르은 그들의 critical section에 들어가면 안된다.

• Progress(진행)

  • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.

• Bounded Waiting(유한 대기)

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

가정

• 모든 프로세스의 수행 속도는 0보다 크다
• 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다

Algorithm 1

위 그림에서 turn은 critical section에 들어갈 차례를 나타내는 변수

그러나 위 코드는 progress 조건이 만족하지 않음

Algorithm 2

둘다 flag가 true인 상황에선 아무도 critical section에 접근할 수 없음
mutual exclusion는 만족하지만 progress 조건을 만족하지 않음

Algorithm 3(Peterson's Algorithm)

모든 조건 만족

그러나 Busy Waiting문제(=spin lock)를 가지고 있음(계속 CPU와 memory를 쓰면서 wait)

Synchronization Hardware

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

Semaphores

앞의 방식들을 추상화시킴

P연산은 CPU 자원을 획득하는 과정 V연산은 반납하는 과정

Critical Section of n Processes

하지만 이 방식은 busy-wait이며, 이는 효율적이지 못함(=spin lock)

➡️ Block & Wakeup 방식의 구현(=sleep lock)

Block / Wakeup Implementation

block과 wakeup을 다음과 같이 가짐

• block

  커널은 block을 호출한 프로세스를 suspend 시킴
  이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음

• wakeup(P)

  block된 프로세스 P를 wakeup시킴
  이 프로세스의 PCB를 ready queue로 옮김

S 값이 음수이면 누군가가 자원을 기다리고 있다는 의미 -> wakeup 시켜주어야함

Which is better?

Block/wakeup overhead v.s. Critical section 길이

• Critical section의 길이가 긴 경우 Block/Wakeup이 적당
• Critical section의 길이가 매우 짧은 경우 Block/Wakeup 오버헤드가 busy-wait 오버헤드(while문 안의 코드)보다 더 커질 수 있음
• 일반적으로 Block/wakeup을 사용하는 것이 더 좋음

Two Types of Semaphores

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

Deadlock and Starvation

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

각 프로세스가 얻어야하는 자원이 다른경우 (S와 Q) 0번 프로세스에서는 S를 얻고, 1번 프로세스에선 Q를 얻었을 때, 데드락이 발생할 수 있음
➡️ 이런 경우 각 프로세스마다 얻어야하는 자원의 순서를 맞추어 줌으로써 해결할 수 있음

Starvation

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

Classical Problems of Synchronization

Bounded-Buffer Problem(producer-consumer problem)

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

Synchronization variables

• mutual exclusion → Need binary semaphore(shared data의 mutual exclusion을 위해)
• resource count → Need integer semaphore(남은 full/empty buffer의 수 표시)

Readers-Writers Problem

한 process가 DB에 write 중일 때 다른 process가 접근하면 안됨
read는 동시에 여럿이 해도 됨

해결책

• 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 자체를 올바르게 접근하게 하는 역할

starvation 발생이 가능(writer가 계속 기다릴 가능성 있음)

Dining-Philosophers Problem

이 solution의 문제점

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

해결 방안

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

두 번째 해결방안을 코드로 구현한 결과
약간의 세마포어의 철학과는 잘 맞지 않음 → 세마포어는 기본값을 특정 값으로 준다음 그것을 낮추면서 사용하는 것인데 여기선 초기 값을 0으로 두고 시작

Monitor

Semaphore의 문제점

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

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

아래 그림은 모니터 구조

• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용

condition x,y;

세마포어 변수처럼 비슷한 역할을 해주는 것이 condition variable

Condition variable은 wait와 signal 연산에 의해서만 접근 가능
→ x.wait()
x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend된다.

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

모니터 버전으로 해결한 Bounded-Buffer Problem

모니터 코드가 더 추상화 되어 있어서 세마포어보다 훨씬 이해하기 쉬움!

모니터 버전으로 해결한 Dining Philosophers Example

참고사이트

http://www.kocw.net/home/cview.do?cid=3646706b4347ef09