6강) 프로세스 동기화 (Process Synchronization)

** KOCW에서 반효경 교수님의 운영체제(2014년) 강의를 수강한 내용을 정리한 글입니다.

운영체제

 

데이터 접근

만약 연산 주체(E-Box)가 여러 개라면?

 

Race Condition(경쟁 상태)

• S-box를 공유하는 E-box가 여럿 있는 경우
  • 메모리 주소공간(S-box), CPU 프로세서(E-box) → Multiprocessor system
  • 공유메모리를 사용하는 프로세스들
  • 커널 내부 데이터를 접근하는 루틴들 간(예: 커널모드 수행 중 인터럽트로 커널모드의 다른 루틴 수행 시)

 

Race condition 1 - OS에서 Interrupt handler vs kernel

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

 

Race condition 2 - 프로세스가 시스템 콜을 하여 커널 모드로 수행 중인데, context switch가 일어나는 경우

• u : user mode / k : kernel mode
• 해결책 : 커널 모드에서 수행 중일 때는 CPU를 선점(preempt)하지 않고, 사용자 모드로 돌아갈 때 선점

 

Race condition 3 - Multiprocessor에서 shared memory 내의 kernel data

• 방법 1) 한 번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법 (커널 전체에 대해 lock / unlock) → 비효율
• 방법 2) 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대해 lock / unlock을 하는 방법

 

Process Synchronizatino 문제

• 공유 데이터의 동시 접근(Concurrent access)은 데이터의 불일치 문제(Inconsistency) 발생 가능성
• 일관성(Consistency) 유지를 위해 협력 프로세스 간 실행 순서 정해주는 메커니즘 필요
• Race condition
  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
  • Race condition을 막기 위해 → Concurrent process는 동기화(Synchronize)되어야 한다.

 

The Critical-Section Problem

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

 

Critical-Section 문제를 해결하기 위한 초기의 시도

• 아래는 프로세스들의 일반적인 구조

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

• 프로세스들은 Synchronize를 위해 몇몇 변수를 공유할 수 있다 → Synchronization variable

아래에서 문제 해결을 알아보자

 

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

• Mutual Exclusion (상호 배제)
  • 한 프로세스가 Critical-section 부분을 수행 주이면, 다른 모든 프로세스들은 각자의 Critical-section에 들어가면 안 된다.
• Progress
  • 아무도 Critical-section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있다면 들어가게 해주어야 한다.
• Bounded Waiting (유한 대기)
  • 프로세스가 critical section에 들어가려고 요청한 후부터 허용될 때까지, 다른 프로세스들이 critical section에 들어가는 횟수에는 한계가 있어야 한다.

 

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

Algorithm 1

• Synchronization variable : turn 사용
• P0 프로세스의 코드

int turn = 0; // => Pi는 turn == i일 때 critical section에 들어갈 수 있음

do {
    while (turn != 0); // 자기 차례가 아니면 while문에서 대기
    critical section
    turn = 1;
    remainder section
} while (1);

→ Bounded waiting을 지키지 못함

 

Algorithm 2

• Synchronization variables
  • boolean flag[2];
  • initially flag[all] = false;
  • flag[i] == trun → Pi가 CS에 들어갈 준비가 되었다.
• Process Pi

do {
    flag[i] = true;
    while (flag[j]) ; // Pj가 CS에 있으면 while문에서 대기;
    critical section
    flag[i] = false // CS에서 나갈 때 flag를 false로
    remainder section
} while (1);

• Mutual Exclusion을 만족하지만, Progress를 만족하지 않음
• 두 프로세스가 모두 2행까지 수행 후, 끊임 없이 양보하는 상황이 발생할 수 있음

 

Algorithm 3 (Peterson’s Algorithm)

• Algorithm 1, 2의 synchronization variables를 합친 알고리즘
• Process Pi

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j); // 상대가 CS에 들어가려하고, 상대 턴이면 대기
    critical section // 상대가 CS에 들어갈 의사가 없거나, 의사는 있지만 상대 차례가 아니면 진입
    flag[i] = false;
    remainder section
} while (1);

• 3가지 충족 조건을 모두 만족; 2개의 프로세스에 대한 Critical-Section 문제를 해결
• Problem : Busy Waiting!(=Spin lock) (계속 CPU와 Memory를 쓰면서 wait)
  • while문을 계속 돌면서 lock을 건다.

 

Synchronization Hardware

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

• 읽기와 쓰기가 하나의 Instruction으로 실행 → 도중에 CPU를 뺏기지 않음
• a가 0이면 → 0을 읽어오고 1로 수정
• a가 1이면 → 1을 읽어오고 1로 수정
• Mutual Exclusion with Test & Set

// Synchronization variable:
boolean lock = false;

// Process Pi
do {
    while (test_and_set(lock));
    // lock이 0이면 -> 아무도 CS에 있지 않음 -> while문을 통과하고 1로 수정
    // lock이 1이면 -> while문에서 대기
    critical section
    lock = false;
    remainder section
} while (1);

• 여전히 Busy waiting 문제 발생

 

Semaphores

• 앞의 방식들을 추상화시킴
  • 추상 자료형을 사용 → 컴퓨터 내부에 구현된 실제 자료구조와 별개로, Object와 연산을 가지고 있는 자료형
• Semaphore S
  • Integer variable
  • 아래의 두 가지 atomic 연산에 의해서만 접근 가능
    • P(S) → 공유 데이터를 획득하는 과정
      • while(S≤0) do no-op; → wait / 여전히 busy waiting
      • S—;
    • V(S) → 사용 후 반납하는 과정
      • S++;
• Critical Section of n Processes

// Synchronization variable;
Semaphore mutex; // initially 1: 1개가 CS에 들어갈 수 있다

// Process Pi
do {
    P(mutex); // 양수면 감소시키고 CS 진입, 아니면 wait
    critical section
    V(mutex); // Semaphore 증가
    remainder section
} while (1);

 

Block / Wakeup Implementation

• CS 진입 차례가 아닌 프로세스를 block해 Busy waiting 문제 해결
• Semaphore를 아래와 같이 정의
• typedef struct { int value; // semaphore struct process *L; // process wait queue } semaphore;
• block : 호출한 프로세스를 suspend 시키고, 해당 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
• wakeup(P) : 블록된 프로세스 P를 wakeup / 해당 프로세스의 PCB를 Ready queue로 옮김

• P(S)
• S.value--; // prepare to enter if (S.value < 0) // 음수면 block { add this process to S.L // block(); }
• V(S)
• S.value++; if (S.value <= 0) { remove a process P from S.L; wakeup(P); }
• 추상 자료형에서 S는 자원의 개수를 나타냈지만, 지금 S.value는 기다리는 프로세스의 개수를 나타내는 값(음수로)

Busy-wait vs Block/Wakeup

• Critical section의 길이가 긴 경우 Block/Wakeup이 적당
• Critical section의 길이가 매우 짧은 경우 → Block/Wakeup 오버헤드가 Busy-wait 오버헤드보다 더 커질 수 있음
• 일반적으로는 Block/Wakeup 방식이 더 좋음

 

Semaphore의 종류

• Counting Semaphore
  • 도메인이 0 이상인 임의의 정수값
  • 주로 자원이 여러 개일 때, Resource counting에 사용
• Binary Semaphore (=mutex)
• 0 또는 1 → 자원이 1개
• 주로 Mutual exclusion(lock/unlock)에 사용

 

Deadlock and Starvation

• Deadlock(교착 상태) : 둘 이상의 프로세스가, 서로 상대방의 의해 충족될 수 있는 event를 무한히 기다리는 현상
  • S, Q가 1로 초기화된 Semaphore라 하자
   

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

 

Bounded-Buffer Problem

• mutex, empty, full 은 각각의 Semaphore
• mutex는 전체 lock/unlock을 관장

 

Readers-Writers Problem

• 한 프로세스가 DB에 write 중일 때, 다른 프로세스가 접근하면 안됨
• Read는 여럿이 동시에 해도 됨
• readcount(Shared data) : 현재 DB에 접근 중인 Reader의 수
• mutex(Synchronization variable) : readcount 접근(critical section)의 mutual exclusion 보장을 위해 사용
• db : Reader와 Writer가 공유 DB 자체를 올바르게 접근하게 하는 역할
• 처음 읽을 때 db에 P, 다 읽고 나갈 때 더이상 Reader가 없다면 V(db)
• Reader가 다 빠져나가야만 Writer가 DB에 접근 가능
  • → Starvation 발생 가능!

 

Dining-Philosophers Problem

• Philosopher의 행동
  • 밥 먹기 (양쪽 젓가락을 잡고)
  • 생각하기 (양쪽 젓가락을 놓고)
• 위의 Solution의 문제점 : Deadlock의 가능성이 있음
  • 모두가 왼쪽 젓가락을 잡게 되면 → 오른쪽 젓가락을 잡는 코드를 모두가 기다리게 됨
  • 해결 방안
    1. n-1명의 철학자만 테이블에 동시에 앉을 수 있도록 한다.
    2. 젓가락을 두 개 모두 집을 수 있을 때만 젓가락을 집게 한다.
    3. 비대칭 : 짝수 철학자는 왼쪽, 홀수 철학자는 오른쪽 젓가락부터 집도록
• 2번 해결 방안에 대한 코드

 

Semaphore의 문제점

• 코딩하기 힘들다
• 정확성의 입증이 어렵다
• 자발적 협력이 필요하다
• 한 번의 실수가 모든 시스템에 치명적 영향

→ Monitor 도입

 

Monitor

• 프로그래밍 언어 레벨에서 제공하는 High-level synchronization construct
• 동시 수행 중인 프로세스 사이에서 Abstract data type의 안전한 공유를 보장
• 내부의 프로시저를 통해서만 공유 데이터에 접근할 수 있게 만듦

• Monitor는 그 자체가 하나의 프로세스만 접근할 수 있음 (lock을 따로 걸 필요가 없다)
• Synchronization 제약 조건을 명시적으로 코딩할 필요 없음
• 프로세스가 모니터 안에서 기다릴 수 있도록 Condition variable 사용
  • condition x, y;

 

Problems solved by Monitor