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

2021-12-30 4 분 소요

본 글은 (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분

프로세스 동기화 (또는 Concurrency Control (병행 제어) 라고도 부른다.)

데이터의 접근

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
- mutliprocessor의 경우 interrupt enable/disable로 해결되지 않음
해결1. 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법
해결2. 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법

Process Synchronization 문제

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

The Critical-Section Problem

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

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

Mutual Exclusion (상호 배제)
- 프로세스 $Pi$가 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);

<br>
<br>

### 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[i]);
    critical section
    flag [i] = false;
    remainder section
} while (1);

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

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

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)

Block / Wakeup Implementation

Semaphore를 다음과 같이 정의

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

block과 wakeup을 다음과 같이 정의
- block : 커널은 block을 호출한 프로세스를 suspend 시킴
- wakeup(P) : block된 프로세스 P를 wakeup시킴
  이 프로세스의 PC를 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);
}

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

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된 프로세스가 없으면 아무 일도 일어나지 않는다.

KakaoTalk Twitter Facebook LinkedIn

poeun 🔅