CS 정리 | OS | 5. 병행제어 | 프로세스 동기화의 SW, HW적 해결법 | kocw 반효경 교수님

Konseo·2023년 9월 12일

CS OS cs스터디 운영체제

운영체제

목록 보기

10/19

프로세스 동기화의 프로그램적 해결법

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

아래 3가지 조건을 모두 만족해야한다.

Mutual Exclusion(상호 배체)
- 프로세스 P가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
Progress(진행)
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
Bounded Waiting(유한대기)
- 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
- starvation을 막아야하는 이유와 같은 맥락
가정
1. 모든 프로세스의 수행 속도는 0보다 크다.
2. 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.

문제 해결을 위한 초기 시도

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

프로세스들의 일반적인 구조

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

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

Algorithm 1

synchronization variable
```
int turn;
 initially turn = 0
```

Process P2

do{
  while(turn!=0); /* My turn? */
  critical section
  turn = 1; /* Now its your turn */
  remainder section
}while(1)

critical section 수행 후 turn을 상대방에게 내어주는 방식

mutual exclusion(상호 배제)을 만족시킨다 (+)
progress를 만족시키지 못한다 (-)

이는 과잉 양보 를 하게 되어 발생한 문제이다. 위 로직에 따르면 반드시 한 번씩 교대로 들어가햐만 하는데 (swap-turn). 결국 상태가 turn 값을 내 값으로 바꿔줘야만 내가 들어갈 수 있다. 만약 특정 프로세스는 critical section이 없어서 turn이 업데이트 될 일이 없는데 또다른 특정 프로세스는 매우 빈번히 critical section을 들어가야 한다면 ? 이럴 때 progress 조건을 만족시키지 못하는 것이다.

Algorithm 2

synchronization variable
```
boolean flag[2]
flag[모두] = false
```
- 즉, flag[i] == true 라면 Pi는 critical section에 들어간 것임
Progress Pi
```
do{
  flag[i]=true; /*Pretend I am in */
  while(flag[j]); /*Is he also in? then wait */
  critical section
  flag[i]=false; /*I am out not */
  remainder section
}while(1)
```
- 자신의 flag 상태를 true로 '직접' 바꿈으로써 critical section에 들어가겠다는 의사표시를 함
- critical section 수행 후에도 마찬가지로 자신의 flag 상태를 false로 직접 바꿈으로써 상대에게 간접적으로 자리를 내어주는 방식임
mutual exlusion을 만족시킨다 (+)
여전히 progress를 만족시키지 못한다 (-)
- why? 두 프로세스 다 2행까지 수행 후 끊임 없이 양보하는 상황이 발생할 수 있기 때문이다.
  
  ex) flag를 true로 바꾼 상태에서 critical section 영역에 들어가려는 찰나에 CPU 제어권이 뺏기게 되는 경우, 다른 프로세스가 자신의 flag를 true로 바꾸어 의사표시를 했음에도 while문이 영원히 수행되면서 아무도 critical section을 사용하지 않음에도 들어가지 못하는 상황이 발생할 수 있다 (=서로가 깃발로 의사표시는 하였는데 아무도 못들어가는 상태)

Algorithm 3 (Peterson's Algorithm)

알고리즘 1과 2의 변수를 모두 활용함

Progress Pi

do{
  flag[i]=true; /*My intentions is to enter... */
  turn =j /*Set to his turn */
  while (flag[i] && turn ==j); /* wait only if... */
  critical section
  flag[i] = false
  remainder section
}while(1);

세 가지 요구조건을 모두 충족한다.
Busy Waiting (spin lock) (-)
- while문을 빠져나오려면 j의 flag 상태를 확인해야하는데 flag[i]와 turn은 자신의 코드에서 이미 결정된 값이기 때문에 while문만 계속 불필요하게 반복하게 됨
- 계속 CPU와 memory를 쓰면서 wait. 불필요한 낭비 발생

프로세스 동기화의 하드웨어적 해결법

하드웨어적으로 Test & modify 를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결됨
synchronization variable
```
boolean lock = false;
```

Progress Pi

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

Semaphores

앞의 방식들을 추상화시킴 (추상 자료형)
Semaphore S
- 정수형 integer variable
- 아래 두 가지 atomic 연산에 의해서만 접근이 가능하다
  - P(S) (자원 획득 과정) : while(S<=0) do no-op; S--;
  - V(S) (자원 반납 과정) : s++;

Critical Section of n Processes

synchronization variable

semaphore mutex; /* initially 1: 1개가 CS에 들어갈 수 있다 */

Progress Pi

do{
  P(mutex); /* If positive, dec-&-enter, Otherwize,, wait */
  critical section
  V(mutex); /* Increment semaphore */
  remainder section
 }while (1);

위 코드와 같은 busy-wait(spin lock) 방식은 효율적이지 못함

Block / Wakeup Implementation

semaphore를 다음과 같이 구조체 형태로 정의

typedef struct{
	int value; /*semaphore */
    struct process *L /*process wait queue */
} semaphore

block과 wakeup을 다음과 같이 가정
- block
  - 커널은 block을 호출한 프로세스sms suspend 시킴
  - 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
  - 아래 참고 사진에 비추어보면 공유 데이터에 있는 큐에 넣는 격
- wakeup(P)
  - block된 프로세스 P를 wakeup 시킴
  - 이 프로세스의 PCB를 ready queue로 옮김
- 참고 사진

Implementation (block/wakeup version of P() & V())

Semaphore 연산이 아래와 같이 정의됨

P(S)

S.value--; /*prepare to enter */
if(S.value<0) /*Oops, negative, I cannot enter */
{
	add this process to S.L; /* block시키지 전에 대기 큐에 넣어둠 */
  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
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)에 사용