운영체제(OS) - Process Synchronization (5)

2021-12-30 5 분 소요

본 글은 (KOCW) 운영체제, 이화여자대학교 반효경 교수님의 강의를 듣고 내용을 요약 및 정리했습니다. 개인 공부에 목적이 있으며, 자세한 사항은 http://www.kocw.or.kr/home/cview.do?mty=p&kemId=1046323에 참고하시면 됩니다.

Chapter 6.

CPU Scheduling 2 / Process Synchronization 1 - 1시간 7분
Process Synchronization 1 - 28분
Process Synchronization 2 - 25분
Process Synchronization 3 - 1시간 2분
Process Synchronization 4 - 27분

이 글은 이화여자대학교 반효경 교수님의 운영체제 강의 내용을 정리한 프로세스 동기화(Process Synchronization) 편이다. 데이터 접근에서의 race condition과 임계 구역 문제, Peterson 알고리즘을 비롯한 프로그램적 해결법, 세마포어와 모니터, 그리고 Bounded-Buffer·Readers-Writers·Dining-Philosophers 문제를 다룬다. 공유 데이터를 누가 언제 건드리는지를 어떻게 정할 것인가가 글 전체를 관통하는 질문이다.

이 글에서 다루는 것

공유 데이터에 대한 동시 접근이 언제 race condition을 만드는가
임계 구역 문제와 이를 푸는 프로그램적 해결법(Algorithm 1~3)
세마포어의 Busy-wait / Block-Wakeup 구현과 두 종류의 세마포어
모니터와 고전적 동기화 문제(Bounded-Buffer·Readers-Writers·Dining-Philosophers)
프로세스 동기화 (또는 Concurrency Control (병행 제어) 라고도 부른다.)

데이터의 접근

동기화 문제를 이해하려면 먼저 컴퓨터 시스템 안에서 ‘누가’ 데이터에 접근하는지부터 짚어야 한다.

Race Condition

여러 주체가 같은 데이터를 동시에 다루면, 연산 순서에 따라 결과가 달라진다 — 그것이 race condition이다.

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

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

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

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

두 프로세스의 address space 간에는 data sharing이 없음
그러나 system call을 하는 동안에는 kernel address space의 data를 access하게 됨 (share)
이 작업 중간에 CPU를 preempt 해가면 race condition 발생

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

3. Multiprocessor에서 shared memory 내의 kernel data

어떤 CPU가 마지막으로 count를 store했는가? -> race condition
- multiprocessor의 경우 interrupt enable/disable로 해결되지 않음
해결1. 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법
해결2. 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법

결국 공유 데이터를 누가 언제 건드리는가의 문제다.

Process Synchronization 문제

공유 데이터의 동시 접근이 왜 문제가 되는지, 그리고 무엇을 맞춰 주어야 하는지를 정리한다.

공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다.
일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘 필요
Race condition
- 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
- 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
race condition을 막기 위해서는 concurrent process는 동기화(synchronization)되어야 한다.

The Critical-Section Problem

동기화가 필요한 코드 구간을 임계 구역(critical section)이라 부른다 — 그 문제 상황과 구조를 먼저 본다.

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

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

어떤 해결법이든 아래 세 가지 조건을 만족해야 한다 — 이 기준으로 뒤의 알고리즘들을 평가한다.

Mutual Exclusion (상호 배제)
- 프로세스 $P_i$가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
Progress (진행)
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
Bounded Waiting (유한 대기)
- 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
가정
- 모든 프로세스의 수행 속도는 0보다 크다.
- 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
두 개의 프로세스가 있다고 가정 $P_0, P_1$
프로세스들의 일반적인 구조

do {
    entry section
    critical section
    exit section
    remainder section
} while (1);

Algorithm 1

Synchronization variable
- int turn;
- initially turn =0;
Process $P_0$ ```c

do { while (turn !=0); critical section turn = 1; remainder section } while (1);

### Algorithm 2

- Synchronization variable
  - boolean flag[2];
  - initially flag [모두] = false;
  - "$P_i$ ready to enter its critical section" if (flag [i] == true)
- Process $P_i$
```c
do {
    flag[i] = true;
    while (flag[j]);
    critical section
    flag [i] = false;
    remainder section
} while (1);

하지만 문제점으로 둘 다 2행까지 수행 후 끊임없이 양보하는 상황 발생 가능
- 눈치만 살피다가 못 들어가는 상황 발생

주의: Algorithm 2의 while (flag[j])는 상대 프로세스의 flag를 검사하는 코드라, 두 프로세스가 동시에 flag를 들면 서로를 기다리며 아무도 임계 구역에 들어가지 못하는 상황이 생긴다.

Algorithm 3 (Peterson’s Algorithm)

알고리즘 1, 2를 합침

do {
    flag [i]=true;
    turn = j;
    while (flag [j] && turn ==j);
    critical section
    flag [i] = false;
    remainder section
} while (1);

3가지 조건 모두 충족
문제점 : (spin lock) 계속 CPU와 memory를 쓰면서 wait

정리하면, Algorithm 1·2의 아이디어를 합쳐 세 가지 조건을 모두 만족시킨 것이 Peterson 알고리즘이다.

지금까지는 소프트웨어만으로 임계 구역을 지키는 방법이었다 — 다음은 하드웨어의 지원을 받는 쪽이다.

Synchronization Hardware

프로그램적 해결법의 부담을 하드웨어 차원에서 덜어낼 수 있다.

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

Mutual Exclusion with Test & Set

Synchronization variable:
    boolean lock = false;

Process P_i
do {
    while (Test_and_Set(lock));
    critical section
    lock = false;
    remainder section
}

Semaphores

앞의 방식들을 추상화시킴
Semaphore S
- 정수 변수
- 아래의 두 가지 atomic 연산에 의해서만 접근 가능
- P(S): while (S$\le$0) do no-op; S–; — pos하면 decrement-&-enter, neg하면 pos될 때까지 기다린다. (busy-wait)
- V(S): S++;

Critical Section of n Processes

Synchronization variable semaphore mutex;

Process $P_i$

do {
    P(mutex);
    critical section
    V(mutex);
    remainder section
} while (1);

busy-wait는 효율적이지 못함 (=spin lock)
Block & Wakeup 방식의 구현 (next page)

주의: busy-wait 방식과 Block/Wakeup 방식은 서로 다른 세마포어가 아니라, 같은 세마포어의 두 가지 구현이다.

Block / Wakeup Implementation

Semaphore를 다음과 같이 정의

typedef struct
{
    int value;
    struct process *L;
} semaphore;

block과 wakeup을 다음과 같이 정의
- block : 커널은 block을 호출한 프로세스를 suspend 시킴
- wakeup(P) : block된 프로세스 P를 wakeup시킴. 이 프로세스의 PCB를 ready queue로 옮김
P(S) : 자원을 획득하는 과정

S.value--;
if (S.value < 0)
{
    add this process to S.L;
    block();
}

V(S) : 자원을 반납하는 과정

S.value++;
if (S.value <=0) {
    remove a process P from S.L;
    wakeup(P);
}

정리하면, P(S)는 자원을 얻는 과정, V(S)는 자원을 반납하는 과정이다.

Which is better?

세마포어를 기다리는 두 방식 중 무엇이 나은지는 상황에 따라 갈린다.

Busy-wait vs Block/wakeup
Block/wakeup overhead vs 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를 무한히 기다리는 현상

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

Classical Problems of Synchronization

동기화 이론이 실제로 어떤 형태로 쓰이는지, 세 가지 대표 문제로 확인한다.

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

정리하면, mutual exclusion은 binary semaphore가, 남은 buffer의 수는 integer semaphore가 담당한다.

Readers-Writers Problem

한 process가 DB에 write 중일 때 다른 process가 접근하면 안됨
read는 동시에 여럿이 해도 됨
해결책
- Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 Reader들을 다 DB에 접근하게 해준다.
- Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
- 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
- Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.

Dining-Philosophers Problem

앞의 solution의 문제점
- Deadlock 가능성이 있다.
- 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우
해결책
- 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
- 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
- 비대칭
  - 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록

결국 자원을 잡는 순서가 문제다.

Monitor

세마포어를 직접 다루는 부담을 줄이기 위해 등장한 상위 수준의 구조가 모니터다.

Semaphore의 문제점
1. 코딩하기 힘들다.
2. 정확성의 입증이 어렵다.
3. 자발적 협력이 필요하다.
4. 한번의 실수가 모든 시스템에 치명적 영향
Monitor : 동시 수행 중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
- Semaphore와 차이점은 lock을 걸 필요가 없다는 것

모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요 없음
프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해
Condition variable은 wait와 signal 연산에 의해서만 접근 가능
- x.wait(); : x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend된다.
- x.signal(); : x.signal은 정확하게 하나의 suspend된 프로세스를 resume한다. Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

주의: 모니터 안에서는 한 번에 하나의 프로세스만 활동할 수 있고, 대기는 Condition variable의 wait/signal로만 표현된다.

핵심 정리

공유 데이터의 동시 접근. race condition은 여러 프로세스가 같은 데이터를 함께 다룰 때, 최종 결과가 마지막에 그 데이터를 다룬 프로세스에 따라 달라지는 현상이다.
임계 구역 해결의 세 조건. Mutual Exclusion, Progress, Bounded Waiting을 모두 만족해야 한다.
프로그램적 해결법. Algorithm 1·2를 합친 Peterson 알고리즘이 세 조건을 만족하지만, busy-wait라는 대가가 남는다.
세마포어. P(S)·V(S) 두 atomic 연산으로 추상화하며, Busy-wait와 Block/Wakeup 두 구현이 있고 용도에 따라 Counting·Binary로 나뉜다.
모니터. lock을 걸 필요 없이 high-level synchronization construct로 안전한 공유를 보장한다.

KakaoTalk Twitter Facebook LinkedIn