#11. 프로세스 동기화

임계구역 문제

- The Critical-Section Problem

- Critical Section

  * A system consisting of multiple threads

  * Each thread has a segment of code, called critical section, in which the thread may be changing common variables, updating a table, writing a file, and so on.

(임계 영역은 다중 스레드로 이루어진 시스템)

(임계 영역은 스레드가 갖고있는 코드 영역으로, 공통변수, 테이블 업데이트, 파일 쓰기 등의 변화를 가하는 영역(구간))

- Solution

  * Mutual exclusion (상호배타): 오직 한 쓰레드만 진입

  * Progress (진행): 진입 결정은 유한 시간 내

  * Bounded waiting (유한대기): 어느 쓰레드라도 유한 시간 내

(Critical Section문제를 해결하기 위해 다음 3가지 조건을 만족 할 수 있는 방법을 찾아야 한다.)

 

프로세스/쓰레드 동기화

- 임계구역 문제 해결 (틀린 답이 나오지 않도록)

- 프로세스 실행 순서 제어 (원하는대로)

- Busy wait 등 비효율성은 제거

 

정리 : O/S는 Process Management, Memory Management, File System ... 등이 있는데 이중 Process Management가 가장 중요하다. 이곳에서는 하는 일 중 가장 중요한 일은 CPU Scheduling과 Synchronization이다.

 

동기화 도구

- Synchronization Tools

- Semaphores

- Monitors

- Mutex

등등..

 

- Semaphores(세마포어)

  * 철도의 신호기, 군대의 수기 신호 등

  * 동기화 문제 해결을 위한 소프트웨어 도구

  * 네덜란드의 에츠허르 데이크스트라가 제안

  *구조: 정수형 변수 + 두 개의 동작 (P, V)

- 동작 (네덜란드 언어 표현)

  * P : Proberan (test) -> acquire();              // 검사

  * V : Verhogen (increment) -> release();   // 증가

- 구조

class Semaphore(
    int value // number of permits
    Semaphore(int value) {
    ...
    }
    void acquire() {
    ...
    }
    void release() {
    ...
    }
}

 

- 내부 구조

void acquire() {
    value--;
    if (value < 0) {
        add a process P to list;
        block;
    }
}

void release() {
    value++;
    if (value <= 0) {
        remove a process P from list;
        wakeup P
    }
}

(어떤 쓰레드가 acquire()를 호출하면 이 프로세스를 queue(list)에 집어넣고 실행될 순서를 기다린다. 반대로 release()는 자신의 차례가 되면 이 프로세스를 queue(list)에서 빼내어 실행함.)

 

- 일반적 사용 : Mutual exclusion

  * sem value = 1;

 

sem.acquire(); ↓

criticalSection  ↓

sem.release(); ↓

 

sem value가 1로 시작 -> acquire()를 호출 -> value = 0이 됨. 0보다 작지 않기 때문에 그대로 통과 -> I/O작업 수행 -> I/O작업을 하고 있는데 다른 프로세스가 I/O작업 수행을 위해 acquire() 호출 -> value < 0이 됨. ->

해당 프로세스를 block시킴. -> 처음 들어온 프로세스가 I/O작업을 마침 -> release() 호출 -> value = 0이 됨 ->

queue(list)에 block되었던 프로세스를 wake up 함 -> I/O 작업 수행 -> 반복

(이렇게 함으로써 Mutual Exclusion이 보장되었다.)

import java.util.concurrent.Semaphore;

class BankAccount {
    int balance;
    Semaphore sem;
    BankAccount() {
        sem = new Semaphore(1);
    }
    void deposit(int n) {
        try {
            sem.acquire();
        } catch (InterruptedException e) { }
        ////////////////////// 임계영역
        int temp = balance + n;
        System.out.println("+");
        balance = temp;
        ////////////////////// 임계영역
        sem.release();    
    }
    
    void withdraw(int n) {
        try {
            sem.acquire();
        } catch (InterruptedException e) { }
        ////////////////////// 임계영역
        int temp = balance - n;
        System.out.println("-");
        balance = temp;
        ////////////////////// 임계영역
        sem.release();
    }
}

class Parent extends Thread {
    BankAccount b;
    Parent(BankAccount b) {
        this.b = b;
    }
    @Override
    public void run() {
        for(int i = 0; i < 1000; ++i) {
            b.deposit(1000);
        }
    }
}

class Child extends Thread {
    BankAccount b;
    Child(BankAccount b) {
        this.b = b;
    }
    @Override
    public void run() {
        for(int i = 0; i < 1000; ++i) {
            b.withdraw(1000);
        }
    }
}

(자바 acquire() 관련 api 문서를 보면 InterruptedException()을 발생시키므로 try ~ catch로 감싸서 Exception 처리)