Process Synchronization

이연중·2021년 11월 8일

OS

목록 보기

6/9

공유 데이터의 동시 접근은 데이터 불일치 문제를 발생시킴

데이터의 일관성을 유지하기 위해 협력 프로세스 간 실행 순서를 정해주는 메커니즘 필요

Race Condition

여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
이를 막기 위해 동시에 실행하는 프로세스 간 동기화가 잘 되어야 함

데이터의 접근

데이터를 읽어가고 그 데이터에 대한 연산을 수행하고, 수행 결과 데이터를 다시 저장하는 과정을 거친다.

이 과정에서 같은 데이터를 읽어서 연산을 수행하는 경우가 있는데, 이러한 경우 발생하는 문제를 Synchronization 문제라 한다.

Race Condition

같은 Storage Box(Memory Address Space)를 여러 Execution Box(CPU Process)가 접근하는 경우 Race Condition(공유 메모리를 사용하는 프로세스들, 커널 내부 데이터를 접근하는 루틴들 간 발생하는 문제) 가능성이 있음

운영체제에서 Race Condition이 발생하는 경우

Kernel 수행 중 인터럽트 발생 시

커널모드에서 작업을 실행하고 있을 때, 인터럽트가 발생해 인터럽트 처리루틴 수행(커널에서 1. load까지 수행 하고 2. inc 하려하는데 인터럽트가 발생해 처리루틴을 수행하는데, 그 작업에서 count를 감소하는 작업을 수행 하고 다시 커널모드 작업을 재개함. 이때, 작업은 2. inc를 수행하는데 1. load에서 읽을 데이터를 기준으로 수행. 즉, count를 감소하는 작업은 반영이 안된채 count가 원래 값에서 증가만 함) -> 결국, 양쪽 다 커널 코드이므로 kernel address space를 공유함으로써 이러한 문제 해결

2. Process가 System Call 하여 Kernel Mode로 수행 중인데 Context Switch가 일어나는 경우

해결: 커널 모드에서 CPU가 수행중일때, CPU가 preempt 당하지 않게 하고, 커널 모드에서 사용자 모드로 돌아 갈 때 preempt하도록 함으로써 해결

3. Multiprocessor에서 Shared memory 내 Kernel Data

방법1: 한번에 하나의 CPU만 커널에 들어갈 수 있게 함

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

The Critical-Section(임계구역) Problem

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

Initial Attempts to Solve Problem

임계구역 문제를 해결하기 위한 첫 번째 방법

공유데이터를 접근하는 프로세스의 critical section 전에 entry section을 넣어 lock을 걸고, critical section 후에 lock을 푸는 방식

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

Mutual Exclusion(상호 배제): 한 프로세스가 critical section 부분을 수행 중이면 다른 프로세스는 접근하지 못한다.
Progress: critical section에 아무 프로세스도 들어가 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면, 들어갈 수 있게 해주어야 한다.
Bounded Waiting(유한 대기): 프로세스가 critical section에 들어가려 요청한 후부터 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 함

Algorithm 1

Synchronization variable: int turn, turn=0(처음에는 프로세스 0번 차례)
Process P0(프로세스 0 입장에서의 코드)

Mutual Exclusion 만족, Progress 불만족(critical section에 반드시 교대로 들어가도록 코딩되어 있음)

Algorithm 2

Synchronization variable: boolean flag[2], flag[모두]= false
flag가 true이면, critical section에 들어갈 수 있음
Process Pi
Mutual exclusion 만족, Progress 불만족(둘 다 flag가 true로 세팅해놓은 경우 대기만하고 critical section에 들어가지 못함. 아무도 못 들어가는 상황)

Algorithm 3

Peterson's Algorithm
Process Pi
Mutual Exclusion 만족, Progress 만족, Bounded Waiting 만족
Busy Waiting(=spin lock) 문제(while 문을 돌면서 체킹하기떄문에 계속 CPU와 memory를 쓰면서 wait)

Busy Waiting 문제 해결

하드웨어적으로 Test&Modify를 atomic하게 수행할 수 있도록 지원하면 해결
Test_and_Set(value): value의 현재값을 읽고, value의 값을 바꿈(lock이 걸려있는지를 확인하고, lock을 걸고 들어갈 수 있음)

Semaphores

프로그래머 입장에서 위 방식들은 구현이 너무 복잡. 위 방식들을 추상 자료형으로 제공해 프로그래머가 이를 이용해 코딩하게 하면 훨씬 수월할 것임
Semaphores는 위 방식들을 추상화시킴(추상 자료형: Object와 Operation으로 구성. 논리적으로 정의된 자료형)
Semaphore S
- Integer variable
- 두 가지 atomic 연산에 의해서만 접근 가능
- P(S): 공유 데이터 획득. lock
- V(S): 공유 데이터 반납. unlock
- busy-wait 문제는 아직 있음(Block & Wakeup 방식을 통해 해결 가능)
Semaphores의 종류
- Counting semaphore: 자원의 개수가 여러 개 있는 경우. resource counting에 사용
- Binary semaphore: 자원의 개수가 1개인 경우(0 또는 1 값만 가질 수 있음). mutual exclusion(lock/unlock)에 사용

Block&Wakeup 방식

Semaphore를 다음과 같이 정의
block: 커널은 block을 호출한 프로세스를 suspend 시킴. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
wake up: block된 프로세스를 wakeup시킴. 이 프로세스의 PCB를 ready queue로 옮김

구현

P(S) 연산에서 만약 사용 가능한 자원이 있다면, S.value를 감소시키고, 자원을 사용하고 사용 가능한 자원이 없다면, S.value를 감소시키고, 대기큐에 넣고 blocked 상태가 된다.
V(S) 연산에서 자원을 반납했는데, S.value가 0 이하라는 소리는 자원을 사용하기 위해 대기큐에서 기다리는 프로세스가 있다는 소리이므로 대기큐에서 프로세스 하나를 지우고 blocked 상태에서 깨운다(wakeup). 자원을 반납하고 S.value가 0 보다 크다면, 자원을 사용하기 위해 대기하는 프로세스가 없다는 소리이므로, 위 작업없이 그냥 넘어간다.

Busy-wait VS block/wakeup

critical section의 길이가 긴 경우 block/wakeup 방식이 적당
critical section의 길이가 매우 짧은 경우 busy-wait 방식이 적당
보통은 block/wakeup 방식이 더 좋음

Deadlock and Starvation

S와 Q가 1로 초기화된 semaphore라 가정

Deadlock: 자원이 2개가 있는 상황에서 하나의 프로세스가 자원을 하나 획득하고, 또 다른 프로세스가 다른 자원을 획득한 상태에서 각 프로세스가 상대방의 자원을 요구할 때, 내놓을때까지 무한히 기다리는 현상

-> 자원을 획득하는 순서를 똑같이 맞춰주면 됨(자원은 반드시 S먼저, 다음 Q 획득 이런식으로)
Starvation: 특정 프로세스들끼리만 자원을 공유하고, 다른 프로세스는 자원을 얻을 수 없는 현상

Classical Problem of Synchronization

Bounded-Buffer Problem(Producer-Consumer Problem)
Readers and Writers Problem
Dining-Philosophers Problem

Bounded-Buffer Problem(Producer-Consumer Problem)

왼쪽이 Producer 프로세스, 오른쪽이 Consumer 프로세스(Producer와 Consumer는 여러 개 있음)

생산자는 버퍼에 데이터를 만들어 넣는 역할, 소비자는 데이터를 꺼내는 역할

Synchronization 문제

생산자 둘이 동시에 빈 버퍼에 데이터를 넣는 경우(버퍼에 lock/unlock 검으로써 해결)
소비자 둘이 동시에 버퍼에서 데이터를 꺼내는 경우(버퍼에 lock/unlock 검으로써 해결)
버퍼의 개수가 유한하기 때문에, 모든 버퍼가 차 있는 경우(소비자가 데이터를 소비하지 않고), 더이상 버퍼에 데이터를 넣을 수 없게됨 -> 버퍼가 비워질때까지 기다려야 함(어떻게 버퍼가 비워졌는지 알까?)

버퍼의 개수가 유한하기 때문에, 모든 버퍼가 비워져있는 경우(생산자가 데이터를 넣지않고), 더이상 버퍼에서 꺼낼게 없게됨 -> 버퍼가 채워질때까지 기다려야 함(어떻게 버퍼가 채워졌는지 알까?)

=> 가용 자원의 개수를 세는 것이 필요(생산자: Full Buffer, 소비자: Empty Buffer)

Producer(with Semaphore)

P(empty): 빈 버퍼 획득(빈 버퍼가 없으면, 기다림)
P(mutex): 버퍼에 lock을 검
V(mutex): 버퍼에 lock을 품
V(full): 내용이 들어있는 버퍼 개수 증가(++)

Consumer(with Semaphore)

P(full): 내용이 들어있는 버퍼 획득(내용이 들어있는 버퍼가 없으면, 기다림)
P(mutex): 버퍼에 lock을 검
V(mutex): 버퍼에 lock을 품
V(empty): 비어있는 버퍼 개수 증가(++)

Readers-Writers Problem

한 Process(데이터를 읽거나 쓰는 주체: Reader, Writer)가 DB(공유데이터)에 write 중일 때 다른 process가 접근하면 안됨
read는 동시에 가능, write는 불가능
공유데이터
- DB 자체
- readcount: 현재 DB에 접근 중인 Rader의 수
synchronization variables
- mutex: readcount에 lock을 위한 binary semaphore
- db: 공유DB에 lock을 위한 binary semaphore

Writer(with Semaphore)

P(db): db에 대한 lock을 검
V(db): db에 대한 lock을 품

Reader(with Semaphore)

P(mutex): readcount라는 공유변수에 lock을 검(for ++)
readcount: 공유데이터를 read하는 reader의 수
if(readcount==1) P(db): 최초 reader만 공유데이터(db)에 lock을 검
V(mutex): readcount라는 공유변수에 lock을 품
P(mutex): DB를 다 읽고 readcount라는 공유변수에 lock을 검(for --)
if(readcount==0) V(db): 마지막 reader라면, db에 대한 lock을 품
V(mutex): readcount라는 공유변수에 lock을 품

=> Reader가 먼저 도착하고 Writer가 그 다음 도착했으면, Reader가 DB에 lock을 걸어놨기때문에 Writer는 기다린다. 그 다음, 또 다른 Reader가 들어왔다면, Reader끼리는 같이 read 할 수 있기때문에 DB에 접근이 가능해진다. 이후에도 Reader가 계속 들어온다면, Writer가 계속 기다린다.(Starvation 발생)

Dining-Philosophers Problem

5명의 철학자는 각각 생각하는 일과 밥먹는 일을 한다.

배고프면 자신의 오른쪽과 왼쪽에 있는 젓가락을 들고 밥을 먹는다.(둘 중 하나라도 없으면 밥을 못먹음)

Philosopher(with Semaphore)

위 코드의 문제점
- Deadlock 가능성이 있음(모든 철학자가 동시에 배가고파 왼쪽 젓가락을 잡으면(오른쪽 젓가락을 얻을때까지 놓지 않음), 오른쪽 젓가락을 잡을 수 없음)
해결방안
- 4명의 철학자만 테이블에 동시에 앉을 수 있게 함
- 젓가락을 모두 잡을 수 있을때에만 젓가락을 잡을 수 있게 함
- 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 잡도록 함
개선 코드

state: 철학자들의 상태,

self: 젓가락을 잡을 수 있는지 여부를 나타내는 Semaphore,

mutex: state 공용변수 lock을 위한 Semaphore

젓가락 잡는 코드: state 변수 접근을 위해 P(mutex) lock을 검-> 자신의 state hungry로 변경 -> test(i) -> V(mutex) 공유데이터에 건 lock을 품 -> 젓가락 잡을 수 있는 권한을 얻었으면, 종료(P(self[i])(1 -> 0). 젓가락 잡을 수 있은 권한이 없으면, P(self[i])에서 기다림

test(i): 왼쪽 철학자와 오른쪽 철학자 모두 밥을 먹지 않고, 내가 hungry인 경우 나의 상태를 eating으로 바꿈 -> 젓가락 잡을 수 있는 권한 부여 V(self[i])(0 -> 1)

젓가락 내려놓는 코드: P(mutex) 공유변수에 lock을 걸고, 자신의 상태를 thinking으로 바꿈 -> 왼쪽과 오른쪽 철학자가 자신으로 인해 밥을 못먹었다면, 밥을 먹을 수 있게 해줌 test() -> 공유변수에 대한 lock을 품 V(mutex)

세마포어가 자원의 개수가 아닌 상태체크용으로 사용되기에 세마포어의 철학과 벗어난 코드이다.

Monitor

Semaphore의 문제점

코딩하기 힘듦(프로그래머가 직접 코딩)
정확성의 입증이 어려움
자발적 협력이 필요
한번의 실수가 모든 시스템에 치명적 영향(프로그래머에게 부담이 큼.)
- V 연산을 먼저하게되면 Mutual exclusion 깨짐, P 연산만 하게되면 Deadlock 문제

모니터는 이러한 문제를 보완하기 위해 동시 수행중인 프로세스 사이에서 추상 데이터 타입의 안전한 공유를 보장하기 위한 high-level synchronization construct임

프로그래밍 언어차원에서 공유데이터 접근에 대한 문제를 자동으로 해결해줌으로써 프로그래머의 부담 줄여줌

목적: 공유데이터에 대한 동시접근을 모니터 차원에서 지원

모니터 내부 공유변수는 모니터 내부 프로시저만 접근할 수 있음
모니터 내에서는 한번에 하나의 프로세스만 활동 가능(프로그래머가 따로 lock을 걸어줄 필요가 없음)
프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음
프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
- wait(): 프로세스가 suspend 됨(sleep)
- signal(): 프로세스를 invoke 함(wakeup)