[OS] 06. Process Synchronization

 

 

Process Synchronization = 프로세스 동기화
(Concurrency Control = 병행제어)

데이터의 접근

데이터를 읽어와서 연산하고 수정하는 방식에서, 누가 먼저 읽었느냐에 따라 결과가 달라질 수도 있기 때문에 Synchronization 문제가 발생

Race Condition (경쟁 상태)

여러 주체가 하나의 데이터를 동시에 접근하려고 할 때

Synchronization 문제 예시

1. count++ 가 +1 하는 동안 count--가 기존 데이터를 읽음

2. count++가 작업 끝낸 후 S-box에 넣고 count--가 그 다음으로 S-box에 넣으면 count++의 작업은 덮어져서 없어짐

→ 조율 필요

발생 하는 경우의 수

1. CPU가 여러 개인 multiprocessor system

2. 공유 메모리를 사용하는 프로세스들

3. 커널 내부 데이터를 접근하는 루틴들 (시스템 콜, 커널 모드 수행 중 또 다른 인터럽트)

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

kernel 수행 중 인터럽트 발생 시 (interrupt handler v.s. kernel)

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

해결 방법

이 문제를 해결하기 위해 중요 변수를 건드리는 instruction 동안에는 인터럽트가 들어와도 인터럽트 처리 루틴으로 돌리는게 아니라 이 작업이 끝날 때까지는 인터럽트를 disabled 시켰다가 작업이 끝난 다음에 인터럽트 처리루틴으로 돌리기

→ 무작정 막으면 문제가 생기기 때문에 순서를 정해둠

process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우 (Preempt a process running in kernel?)

If you preempt CPU while in kernel mode …

1. 두 프로세스의 address space 간에 data sharing이 없음

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

3. 이 작업 중간에 CPU를 preempt 하면 race condition 발생

즉, Pa가 system call 하는 동안 Pa의 할당 시간이 끝나서 preempt 당하고 Pb가 다시 system call을 요청하여 기존의 Pa가 작업하고 kernel address space의 data를 access를 하게 되서 작업하면 Pa가 데이터 값을 이미 읽어온 값으로 작업하기 때문에 Pb의 값은 반영이 안됨

해결 방법

커널 모드에서 수행 중일 때는 CPU를 preempt 하지 않음 커널 모드에서 사용자 모드로 돌아갈 때 preempt

Multiprocessor에 shared memory 내의 kernel data
(multiprocessor - 작업주체 여러개)

어떤 CPU가 마지막으로 count를 store 했는가? → race conditon
multiprocessor의 경우 interrupt enable/disable로 해결되지 않음

해결 방법

• 방법1. 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법
  → 커널 모드가 될 때마다 lock이 걸려서 다른 CPU는 커널 내 수정되고 있는 데이터를 쓰지는 않지만 커널에 접근하지 못해 비효율적

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

Process Synchronization 문제

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

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

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

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

Race Condition 예시

사용자 프로세스 P1 수행 중 timer interrupt가 발생해서 context switch가 일어나서 P2가 CPU를 잡으면 아래의 경우에 문제가 생김 그밖에는 큰 문제가 생기지 않음

• shared memory를 쓰고 있을 때

• 커널에 있는 데이터를 쓰고 있을 때

The Critical-Section (임계 구역) Problem

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

• 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재

Problem

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

Initial Attempts to Solve Problem

• 두 개의 프로세스가 있다고 가정 P0, P1

• 프로세스의 일반적 구조

  

• 프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수를 공유할 수 있다. → synchronization variable

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

• Mutual Exclusion(상호 배제)
  프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다

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

• Bounded Waiting(유한 대기)
  프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
  특정 프로세스가 critical section에 지나치게 들어가지 못하는 starvation을 막는 것

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

Algorithm 1

• Synchronization variable
  int turn: initially turn = 0; ⇒ Pi can enter its critical section if (turn == i)
  turn은 critical section에 들어갈 수 있는 변수

• Process P0

  

  turn이 본인 차례 아닌 경우(turn 0이 아님)에는 기다리고, 상대방이 critical section을 빠져 나올 때 turn을 상대방 차례로 만들어주기 때문에 while문을 충족해서 critical section에 들어가고 마찬가지로 빠져 나올 때 turn을 상대방 차례로 만들어줌

• Satisfies mutual exclusion, but not progress

• 즉, 과잉양보 (prograss 조건 만족 못함)
  반드시 한 번씩 교대로 들어가야만 함 (swap-turn) 그가 turn을 내 값으로 바꿔줘야만 내가 들어갈 수 있음
  → 특정 프로세스가 더 빈번히 critical section을 들어가야 한다해도 한 쪽의 critical section 작업이 끝나야 들어갈 수 있음

Algorithm 2

• Synchronization variables
  • boolean flag[2]:
    initially flang [모두] = false; /*no one is in CS*/
  • “Pi ready to enter its critical section” if (flag[i] == true)

• Process Pi

  

  본인이 critical section에 들어가려면 flag를 true로 만들고 상대방 flag 체크 후 critical section 들어갈 지 유무 정하고 만약 상대방의 flag를 세팅하지 않았다면 critical section에 들어가고 들어갔다 나오면 flag를 false를 만들고 상대방이 들어갈 수 있도록 만듦

• Satisfies mutual exclusion, but not progress requirement

• 둘 다 2행까지 수행 후 끊임 없이 양보하는 상황 발생 가능
  → 둘 다 flag를 동시에 들었을 경우 prograss 조건 만족 못함

Algorithm 3 (Peterson’s Algorithm)

• Combined synchronization variable of algorithms 1 and 2

• Process Pi

  

  제일 먼저 자신의 깃발을 들어서 critical secton에 들어가겠다는 의사를 표현하고 turn을 상대방으로 바꾼다. 그리고 들어가기 전에 체크를 함. 상대방이 깃발을 들고 있고 이번이 상대방이 차례면 기다리고 그외는 critical secton에 들어가고 빠져나올 때 깃발을 내려 놓음

• Meets all three requirements; solves the critical secton problem for two processes

• Busy Waiting(=spin lock) (계속 CPU와 memory 쓰면서 wait)
  → 어느 프로세스가 이미 critical section에 들어간 상태에서 다른 프로세스가 CPU를 잡으면 while문을 계속 돈다. (만족이 되지 않으니 계속 wait하고 CPU 할당시간을 다 사용)

⇒ 문장 하나 실행되는 도중에 CPU를 빼앗길 수 있다는 가정 하에 코드를 짜다보니 SW적으로 복잡한 코드가 만들어짐, 사실은 HW적으로 하나의 instruction만 주어지면 critical section 문제는 아주 쉽게 해결

⇒ 즉, 어떤 데이터를 읽는 것과 쓰는 것을 하나의 instruction으로 처리할 수 없어서 생기는 문제 → 하나의 instruction으로 실행 가능하다면 instruction가 하나가 실행하는 도중에 CPU를 빼앗기지 않음

Synchronization Hardware

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

  

  a라는 data의 현재 값을 읽어오고 a라는 데이터를 1로 세팅해주기

• Mutual Exclusion with Test & Set

  

  lock이라는 변수를 하나 두고 처음에는 lock의 값이 0이 되고, critical section 들어가기 전에 lock을 1로 걸고 들어가는 것, 이미 lock이 걸려있으면 체크를 하고 lock을 걸면서(1을 1로 세팅) 기다리고, 안 걸려 있으면 내가 lock을 걸면서(0을 1로 세팅) critical section에 들어감.

Semaphores

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

busy-wait Implementation

• Semaphore S (P(S)연산 - S 자원 획득, V(S)연산 - S 자원 반납)
  • integer variable (정수값) - 자원의 개수
  • 아래의 두 가지 atomic 연산에 의해서만 접근 가능

lock을 걸고 푸는 것을 semaphore를 통해 컴퓨터에게 간단하게 제공
공유자원을 획득하고 반납하는 것을 semaphore가 처리해주는 것
자원의 개수가 하나일 때 P연산은 공유데이터를 획득하는 과정(lock 걸기 - S 1 빼기), V연산은 다 사용하고 반납하는 과정(lock 풀기 - S 1 더하기)
→ busy wait 문제는 생김

P() & V() Semaphore 연산 코드 (busy-wait)

→ Semaphore를 지원하면 프로그래머는 P연산과 V연산만 해주면 되고 구현은 시스템의 몫 (그러나 여전히 busy-wait 해결 x)

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

• Block&Wakeup 방식의 구현 (=sleep lock) → CPU 못쓰면 blocked 상태로 만들기

Block / Wakeup Implementation

• Semaphore를 다음과 같이 정의

  

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

P() & V() Semaphore 연산 코드 (Block/wakeup)

1. 자원의 여분이 없으면 프로세스를 S의 value 값을 마이너스하고, 해당 프로세스를 S에 리스트 형식으로 연결시켜서 blocked 시킴 (S의 value 값이 양수면 바로 내려감)

2. 자원을 쓰고있는 프로세스가 다 쓰면 S.value를 증가시키고도 S.value가 0 이하(기다리면서 잠든 프로세스가 있다는 것)면 리스트 형식으로 연결된 프로세스 하나를 wakeup 함

which is better?

• Busy-wait vs Block/wakeup

• Block/wakeup overhead v.s Critical section 길이
  • Critical section의 길이가 긴 경우 Block/wakeup이 적당
  • Critical section의 길이가 매우 짧은 경우 Block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
  • 일반적으로는 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가 1로 초기화된 semaphore라고 하자

  

  → 자원 획득 순서를 맞추면 Deadlock 해결 가능

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

Classic Problems of Synchronization

• Bounded-Buffer Problem (Producer-Consumer Problem)
  유한한 버퍼 크기에서 생산자 소비자 문제

• Readers and Writers Problem
  프로세스가 읽는 프로세스와 쓰는 프로세스 문제

• Dining-Philosophers Problem
  철학자가 생각하기, 밥 먹기 두 가지 업무를 하는데 배고파지면 왼, 오 젓가락 잡고 밥 먹고 배부르면 생각하기 (철학자마다 밥 먹는 시간, 생각하는 시간 다름)

Bounded-Buffer Problem (Producer-Consumer Problem)

Producer가 data를 만들어 buffer에 집어 넣음, Consumer가 buffer에서 data를 꺼내서 사용

Synchronization 문제 및 해결 방법

• Binary semaphore(=mutex)
  1. 생산자들이 비어있는 버퍼 확인하고 동시에 접근해서 데이터 집어 넣는 경우
     → 공유 버퍼에 lock 걸고 다른 생산자 접근 막고, 끝나면 lock 풀고 buffer 가리키는 pointer 변경 및 full buffer 하나 증가
  2. 소비자들이 차있는 버퍼 확인하고 동시에 꺼내가려고 하는 경우
     → 공유 버퍼에 lock 걸고 다른 소비자 접근 막고, 끝나면 lock 풀기 buffer 가리키는 pointer 변경 및 empty buffer 하나 증가

• Counting semaphore
  1. 생산자들이 한꺼번에 도착해서 공유 버퍼를 가득 채우면, 소비자는 오지 않고 생산자가 또 오는 상황이면 생산자가 사용할 수 있는 자원이 없는 경우
     → 자원의 여부(소비자가 꺼내갈 때까지)가 생길 때까지 기다려야 함
  2. 소비자들이 한꺼번에 도착해서 공유 버퍼를 모두 가져가고, 생산자는 오지 않고 소비자가 또 오는 상황이면 소비자가 사용할 수 있는 자원이 없는 경우
     → 자원의 여부(생산자가 생산할 때까지)가 생길 때까지 기다려야 함

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의 수 표시)

초반: semaphore full = 0, empty = n, mutex = 1;

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의 수*/ (counting semaphore)

Synchronization variables (둘 다 binary semaphore)

• mutex /*공유 변수 readecount를 접근하는 코드(critical section)의 mutual exclusion 보장을 위해 사용*/

• db /*Reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할*/

초반: semaphore mutex = 1, db = 1;

Starvation 해결 방법 (Reader가 계속 오는 경우)

큐에 우선순위를 둬서 writer를 계속 기다리지 않게 하기 (현실 상황의 신호등)

Dining-Philosophers Problem

Synchronization variables

semaphore chopsticks[5];

/*initially all values are 1*/

Philosopher i

solution 문제점

• Deadlock 가능성이 있다.

• 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우

해결 방안

• 4명의 철학만이 테이블에 동시에 앉을 수 있도록 한다. (밥을 먹을 때만 테이블에 앉게 한다)

• 젓가락 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
  enum {thinking, hungry, eating} state[5];
  → 다섯 명 철학자 상태
  semaphore self[5] = 0;
  → 다섯 명의 철학자가 젓가락을 다 잡을 수 있는지 표시 ex. semaphore self[1] = 0 (1번 철학자 젓가락 모두 잡을 수 없음), semaphore self[3] = 1 (3번 철학자 젓가락 모두 잡을 수 있음)
  semaphore mutex=1;
  → 철학자 자신 뿐만 아니라 옆의 철학자 상태를 바꿀 수 있기 때문에, 상태 공유 변수에 대한 접근을 막기 위해 사용
  

  

1. 철학자 i가 배가 고파서 젓가락을 잡는 함수를 호출하면 먼저 상태를 건드려서 lock을 건드리고 작업 끝나면 lock을 품 (thinking → hungry)

2. 철학자 i가 젓가락 두 개를 잡을 수 있는지 테스트 (테스트 함수)

3. 왼쪽 철학자도 밥 먹고 있지 않고, 오른쪽 철학자도 밥 먹고 있지 않고 내가 배가 고픈 상태 모두 만족할 때만 밥 먹는 상태로 바꾸며 젓가락 잡는 권한(0을 1으로 바꾸기)을 줌 (hungry → pickup)

4. 테스트 끝났으면 P연산을 통해 젓가락 두 개를 잡고(1을 0으로 바꾸기) 밥 먹기 (pickup → eat)

5. 밥 다 먹고 젓가락을 내려놓을 때 상태를 thinking으로 바꾸고 왼쪽 철학자와 오른쪽 철학자에 대한 테스트 하기 (인접 철학자가 배가 고픈데, 자신이 밥 먹고 있는 바람에 젓가락 못 잡았으면 잡을 수 있도록 내려놓고 인접 철학자 테스트 하기) (eat → thinking)

• 비대칭
  • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 하기

Monitor

Semaphore의 문제점

• 코딩하기 힘들다

• 정확성(correctness)의 입증이 어렵다

• 자발적 협력(voluntary cooperation)이 필요하다

• 한번의 실수가 모든 시스템에 치명적 영향

정의

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

 

• 공유 데이터를 접근하기 위해서는 이 모니터라고 정의된 내부의 procedure를 통해서만 이 공유 데이터에 접근할 수 있게 만들어 놓음

• 모니터가 원천적으로 모니터 내부에 있는 procedure는 동시에 여러 개가 실행이 안되도록 통제하는 권한을 줌
  → 프로그래머가 lock을 걸 필요가 없음

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

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

• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
  condition x, y; (자원을 세는 변수)

• Condition variable은 wait와 signal 연산에 의해서만 접근 가능
  • x.wait();x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend 된다
  • x.signal();x.signal()은 정확하게 하나의 suspend된 프로세스를 resume 한다. Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

Bounded-Buffer problem

공유 버퍼가 모니터 안에 정의되어 있으므로 생산하거나 소비하는 작업하기 위해서 모니터 내부 코드를 실행해야 하고 그러면 생산자든 소비자든 하나의 프로세스만 모니터 안에서 활성화되기 때문에 굳이 lock을 걸지 않아도 생산자가 접근하는 동안 또 다른 생산자나 소비자가 접근해서 생기는 문제를 고려할 필요가 없음

만약 생산자 입장에서 비어있는 버퍼가 없으면, 비어있는 버퍼를 기다리는 줄에 줄 서서 기다리는 상태가 됨 (blocked) 반대로 비어있는 버퍼가 있으면 버퍼에다가 내용을 집어넣고 작업 끝나면 내용이 든 버퍼가 없어서 잠들어 있는 소비자가 있다면 깨워 줌 (소비자 입장도 똑같음)

Dining Philosophers Example

• state는 공유 변수이지만 모니터 내부에서 접근하는 코드를 만들어서 lock은 필요 없음

• 잠들게 할 때 if 문으로 체크를 함

⇒ semaphore와 monitor는 코드가 비슷한 측면이 있어 서로 바꿀 수 있음

⇒ 그러나 모니터는 동시 접근을 막으며 세마포는 프로그래머가 접근하고 반납할 때 P연산 V연산을 해주어야 함.

Uploaded by

N2T