Understanding Process Synchronization
프로세스 동기화를 이해하기 위한 짧은 노트
38 min readNov 6, 2021
Process Synchronization vs Thread Synchronization
- 현대 운영체제는 Thread Synchronization 위주로 동작한다.
- Context Switching 비용은 Process가 Thread보다 많이 든다. Thread는 Stack 영역을 제외한 모든 메모리를 공유하기 때문에 Context Switching 발생시 Stack 영역만 변경을 진행하면 된다. 따라서 Context Switching은 현대 운영체제에서 Thread 기반으로 동작한다.
- Process 1의 Thread A가 실행되고, Process 1의 Thread B가 실행되고 이후 Process 2의 Thread C가 실행되는 형태로 진행된다. 즉, Context Switching의 기준이 현대 OS에는 Thread인 것이다. 각 프로세스 내의 Thread 1, Thread 2… 동일 프로세스 내에서 서로 다른 쓰레드들이 번갈아가며 처리된다.
- Independent Process란 Process 1, Process 2 가 아무런 관계가 없는 독립적인 프로세서인 경우를 의미한다. 이와 달리, Cooperating Processor는 Process 1, Process 2가 서로 영향을 주고 받는 경우를 의미한다. 예를 들면, 프로세스 간 자원공유가 필요한 경우(DB 등)을 꼽아볼 수 있다.
- Cooperating Processor의 경우, 쓰레드 간의 공유자원을 사용하므로 동기화 작업이 필요하다. 공유 자원에 대한 동시 접근(concurrent access)는 데이터 일관성을 깨뜨리므로, cooperating process 간의 순서있는 실행(orderly execution)을 통해 데이터 일관성을 유지해야 한다.
Example: Bank Account Problem
// Test.java
class Test {
public static void main(String[] args) throws InterruptedException {
BankAccount b = new BankAccount();
Parent p = new Parent(b);
Child c = new Child(b);
p.start(); // start(): 쓰레드를 실행하는 메서드
c.start();
p.join(); // join(): 쓰레드가 끝나기를 기다리는 메서드
c.join();
System.out.println("balance = " + b.getBalance());
}
}
// 계좌
class BankAccount {
int balance;
void deposit(int amount) {
int temp = balance + amount; // 임계구역 코드
System.out.print("+"); // 시간 지연 의도를 위한 코드
balance = temp;
}
void withdraw(int amount) {
int temp = balance - amount; // 임계구역 코드
System.out.print("-"); // 시간 지연 의도를 위한 코드
balance = temp;
}
int getBalance() {
return balance;
}
}
// 입금 프로세스
class Parent extends Thread {
BankAccount b;
Parent(BankAccount b) {
this.b = b;
}
public void run() { // run(): 쓰레드가 실제로 동작하는 부분(치환)
for (int i = 0; i < 100; i++)
b.deposit(1000);
}
}
// 출금 프로세스
class Child extends Thread {
BankAccount b;
Child(BankAccount b) {
this.b = b;
}
public void run() {
for (int i = 0; i < 100; i++)
b.withdraw(1000);
}
}위 코드에 대한 출력값은 다음과 같다. 만약 시간 지연을 위한 코드(System.out.print 함수 호출)이 없었다면, balance 값은 0이 되었을 것이다.
++++++++++++++++++++++++++++++++++----------------------------------------------
--------------------------------------------------------------------------++++++
+++----------------------------------------------+++++++++++++++++++++++++++++++
+----+++++++-+++++----+++-------------------------------------------------------
-+++++++-++++-+++++++++-------++++++++++++++++++++++++++++++++++++++++++++++++++
++++++---------------+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+-++++++++++++-------------------++++++++++++++++++++-++++++++++++++++++++++++++
++++++-+------------------------------------------------------------------------
-+++++++++++-+++++++----------------------------------------+-------+-----------
-+------+-----------------------------------------------------------------------
-+------------------------------------------------------------------------------
-+------------------------------------------------------------------------------
-------------------+-------+----------------------------------------------------
------------------------------+-------------------------------------------------
------------------------------------------------------+-------------------------
-+------------------------------------------------------------------------------
-++---------------------------------------++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
balance = 1000000간단한 실험을 통해, 우리는 시간 지연이 주어질 때 여러 쓰레드가 하나의 공유 자원을 사용하는 프로그램은 망가진다는 사실을 알 수 있다. 출력되는 결과는 운영체제에서 쓰레드를 스위칭하는 패턴이 매번 다르므로 수행할 때마다 다르다. 이는 공통변수, 즉 계좌의 잔액(common variable)에 대한 동시 업데이트(concurrent update) 가 이루어지기 때문이다. Java와 같이 High-level 언어에서는 한 줄로 족하지만, assembly code로 번역될 때 여러 줄로 바뀌므로 중간에 스위칭이 발생할 수 있다.
이를 해결하기 위해서는, 공통변수에 해당하는 임계구역(critical section)을 설정해 임계구역 코드에 접근하는 쓰레드가 단 하나만 존재하도록 해야 한다.
// 해결 코드
class Test {
static final int MAX = 100; // 입출금 회수
public static void main(String[] args) throws InterruptedException {
// 은행계좌를 만들고
BankAccount b =
new BankAccount();
// 부모 쓰레드와
Parent p = new Parent(b, MAX);
// 자식 쓰레드를 만든 후
Child c = new Child(b, MAX);
// 각각 실행시킨다.
p.start();
c.start();
p.join();// 부모와 자식 쓰레드가
c.join();// 각각 종료하기를 기다린다.
System.out.println("Final balance = "
+ b.getBalance());// 최종 잔액 출력
}
}
class BankAccount {
int balance;
void deposit(int amount) {
balance = balance + amount;
}
void withdraw(int amount) {
balance = balance - amount;
}
int getBalance() {
return balance;
}
}
class Parent extends Thread {
BankAccount b;
int count;
Parent(BankAccount b, int count) {
this.b = b;
this.count = count;
}
public void run() {
for (int i=0; i<count; i++)
b.deposit(1);
}
}
class Child extends Thread {
BankAccount b;
int count;
Child(BankAccount b, int count) {
this.b = b;
this.count = count;
}
public void run() {
for (int i=0; i<count; i++)
b.withdraw(1);
}
}임계구역 문제를 해결하기 위해서는 다음의 해결책을 꼽아볼 수 있다. 이를 통하여 프로세스의 실행 순서를 제어하는 것이 목적이다.
- Mutual exclusion(상호배타): 오직 한 쓰레드만이 진입 가능하다. 한 쓰레드가 임계구역에서 수행 중인 상태에서는 다른 쓰레드는 절대 이 구역에 접근할 수 없다.
- Progress(진행): 한 임계구역에 접근하는 쓰레드를 결정하는 것은 유한 시간 이내에 이루어져야한다.
- Bounded waiting(유한대기): 임계구역으로 진입하기 위해 대기하는 모든 쓰레드는 유한 시간 이내에 해당 임계구역으로 진입할 수 있어야 한다.
Semaphore
- 세마포어에는 P와 V가 있다. P : 임계 구역 들어가기 전에 수행 (프로세스 진입 여부를 자원의 개수(S)를 통해 결정), V : 임계 구역에서 나올 때 수행 (자원 반납 알림, 대기 중인 프로세스를 깨우는 신호)
class Semaphore {
int value; // number of permits
Semaphore(int value) {
// ...
}
void acquire() { // P
value--;
if (value < 0) {
// add this process/thread to list
// block
}
}
void release() { // V
value++;
if (value <= 0) {
// remove a process P from list
// wakeup P
}
}
}procedure P(S) --> 최초 S값은 1임
while S=0 do wait --> S가 0면 1이 될때까지 기다려야 함
S := S-1 --> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함
end P
--- 임계 구역 ---
procedure V(S) --> 현재상태는 S가 0임
S := S+1 --> S를 1로 원위치시켜 해제하는 과정
end V
- 위 코드에서 acquire 함수는 P에 해당하는 것으로서, 쓰레드가 임계구역에 진입하는 경우 value 값을 감소시키는 역할을 한다. 만약 value 값이 0보다 작으면 해당 임계구역에 어느 쓰레드가 존재한다는 뜻이므로, 새로운 쓰레드가 접근하지 못하도록 막아야 한다.
- If the semaphore value is negative, its magnitude is the number of processes waiting on that semaphore. 즉, value의 절댓값 크기만큼 현재 프로세스/쓰레드들이 임계구역 접근 번호표를 뽑은 셈이 된다. 이와 달리, value의 초기값은 1이므로 1일 때는 프로세스가 직접 접근 가능하다는 뜻이며 0이면 현재 누군가가 쓰고 있으니 잠깐만 대기하라는 뜻이다.
- 대기열은 list(Queue)로 구현하되, 원소 추가 이후 block을 걸어준다.
- 위 코드에서 release 함수는 V에 해당하는 것으로서, 쓰레드가 임계구역에 빠져나가는 경우 value 값을 증가시키는 역할을 한다. 만약 value 값이 0보다 크면 임계구역에 진입하려고 대기하는 프로세스가 list(Queue)에 남아있다는 의미이므로 순서대로 상위 프로세스를 임계구역에 접근하도록 해 주어야 한다.
- 예시: 최초 S 값은 1이고, 현재 해당 구역을 수행할 프로세스 A, B가 있다고 가정하자.
- 먼저 도착한 A가 P(S)를 실행하여 S를 0으로 만들고 임계구역에 들어감
- 그 뒤에 도착한 B가 P(S)를 실행하지만 S가 0이므로 대기 상태
- A가 임계구역 수행을 마치고 V(S)를 실행하면 S는 다시 1이 됨
- B는 이제 P(S)에서 while문을 빠져나올 수 있고, 임계구역으로 들어가 수행함
- Bank Account Problem을 Semaphore를 활용하여 해결하면 다음과 같다. 쓰레드 동기화를 통하여 임계구역 문제를 해결하였고, 이에 따라 +- 출력을 제외하고 balance 값이 0 출력된다.
import java.util.concurrent.Semaphore;
class BankAccount {
int balance;
Semaphore sem;
BankAccount() {
sem = new Semaphore(1);// 초기값 = 1
}
void deposit(int amount) { // 입금
try {
sem.acquire(); // 진입 전: acquire()
} catch (InterruptedException e) {}
int temp = balance + amount;
System.out.print("+");
balance = temp;
sem.release(); // 나온 후: release()
}
void withdraw(int amount) { // 출금
try {
sem.acquire(); // 진입 전: acquire()
} catch (InterruptedException e) {}
int temp = balance - amount;
System.out.print("-");
balance = temp;
sem.release(); // 나온 후: release()
}
int getBalance() {
return balance;
}
}Ordering
- 세마포어를 사용하는 이유 중 하나는 ordering하기 위함인데, 이는 프로세스의 실행 순서를 원하는 대로 설정하는 것에 있다.
- 예시: 프로세스가 Process 1, Process 2 두 개가 있다고 가정하자. 원하는 순서는 Process 1, Process 2 순으로 실행하기를 원한다. 그러면 아래와 같이 설정해줄 수 있다.
- 위의 사진은, Process 1 > Process 2 순서로 프로세스 실행됨이 보장된다.
P1이 먼저 실행된 경우는 다음과 같다.
- Section 1 이전에 아무런 동작이 없으므로 바로 수행한다.
sem.release()를 만나면 value값을 1 증가시키고, 세마포 큐에 있는 프로세스를 깨워주는데 현재에는 큐에 프로세스가 없으므로 아무 동작도 하지 않는다.- P2가 실행된다.
- P2의
sem.acquire()를 만나면 현재 value값은 1이고 이를 1감소시키면 0이 된다. value = 0이면 block을 하지 않으므로, 무사히 Section 2가 수행된다.
P2가 먼저 실행된 경우는 다음과 같다.
- Section 2 이전에
sem.acquire()가 있으므로 이를 수행하는데, 현재 value값은 0이고 이를 1 감소 시키면 -1 이 된다. value값이 음수면 해당 프로세스를 block 시킨다. 즉, 세마포 큐에 삽입한다. - P1이 실행되면 Context Switch으로 Section 1이 바로 수행된다.
sem.release()를 만나면 value값을 1 증가시키고, 세마포 큐에 있는 P2 프로세스를 깨워준다.(현재 value = 0)- P2의 Section 2가 수행된다.
Bank Account Problem을 Ordering으로 해결해보면 다음과 같다.
- 입금(Parent) 또는 출금(Child)가 먼저 실행되는 경우: 상호배타를 위한 sem 세마포어 및 실행순서 조정을 위한 sem2 세마포어 할당.
- 프로그램 시작 시, 부모 쓰레드는 그대로 실행하도록 하고 자식 쓰레드가 실행되는 경우 sem2 세마포어에 의해 일단 block되고 이후 부모 쓰레드를 실행하여 자식 쓰레드가 이후에 블록된 상태에서 벗어나도록 설정.
- 구체적으로, 초기값이 0인 sem2 세마포어에 대해 acquire()를 호출하게 하도록 deposit(), withdraw() 메소드를 각각 수정
class BankAccount {
int balance;
Semaphore sem, sem2;
BankAccount() {
sem = new Semaphore(1);
sem2 = new Semaphore(0); // Ordeing을 위한 세마포
}
void deposit(int amount) {
try {
sem.acquire();
} catch (InterruptedException e) {}
int temp = balance + amount;
System.out.print("+");
balance = temp;
sem.release();
sem2.release(); // block된 출금 프로세스가 있다면 깨워준다.
}
void withdraw(int amount) {
try {
sem2.acquire(); // 출금을 먼저하려고 하면 block한다.
sem.acquire();
} catch (InterruptedException e) {}
int temp = balance - amount;
System.out.print("-");
balance = temp;
sem.release();
}
int getBalance() {
return balance;
}
}- 입출금이 교대로 이루어지는 경우(Child-Parent-Child-Parent…): 블록된 부모 쓰레드는 자식 쓰레드가 깨워주고, 블록된 자식 쓰레드는 부모 쓰레드가 각각 깨워주도록 한다.
- 상호배타를 위한 sem 세마포어 외에 부모 쓰레드의 블록을 위해 dsem 세마포어를, 자식 쓰레드의 블록을 위해 wsem 세마포어를 각각 사용한다.
- 잔액이 항상 0 이상인 경우: 출금하려는 액수보다 잔액이 작으면 자식 쓰레드가 블록되도록 하며 이후 부모 쓰레드가 깨워주게 한다.
- 상호배타를 위한 sem 세마포어 외에 sem2 세마포어를 사용하여 잔액 부족시 자식 쓰레드가 블록되도록 한다.
Classical Synchronization Problems
- Producer and Consumer Problem
- Readers-Writers Problem
- Dining Philosopher Problem
Producer-Consumer Problem
- Bounded-Buffer Problem라고 불린다.
- 생산자가 데이터를 생산하면 소비자는 그것을 소비하는데, 그 생산자와 소비자 사이에는
저장공간인 buffer가 있고 이 buffer의 크기는 유한하다. - 한계가 있는 저장공간(Bounded Buffer): 생산된 데이터는 버퍼에 일단 저장(속도차이 등)하는데, 현실 시스템에서 버퍼 크기는 유한하다. 생산자는 버퍼가 가득 차면 더 넣을 수 없다 (size = count). 반면, 소비자는 버퍼가 비면 뺄 수 없다.
class Buffer {
int[] buf;
int size; //버퍼 갯수(용량), 크기
int count; //버퍼안의 생산되어 저장되어있는 갯수
int in; //처음 in 인덱스 값부터 생산자의 데이터를 넣겠다.
int out; // 빼내는 위치
}
Buffer(int size){
buf = new int(size);
this.size = size;
count = in = out = 0
}// check if buf is full
void insert(int item) { // 생산자가 버퍼에 데이터를 집어넣는 함수
while (count == size) // 같다면 무한루프를 돌며 여기서 멈춰있다.
// buf is not full
buf(in) = item; //소비자가 하나를 가져가 1의 공간이 생긴다면 item을 in에 넣고
in = (in + 1) % size; //나머지가 0
count ++;
}
int remove() {
// check if buf is empty
while (count == 0) //버퍼가 비어져있으면 무한루프 돌면서 소비자는 기다리고 있음
// buf is not empty
int item = buf(out); //buf에 out한 값을 item에 넣는다.
out = (out + 1)%size; //나머지가 0
count --;
return item
}class Test {
public static void main(String[] args) {
Buffer b = new Buffer(100);
Producer p = new Producer(b, 10000);
Consumer c = new Consumer(b, 10000);
p.start()
c.start()
try {
p.join()
c.join()
} catch (InterruptedException e) {
System.out.println("Number of items in the buf", b.count);
}
}
}
- 동기화를 했을 때 count 결과값은 0이다.
- 그러나, 잘못된 결과값이 나오는 경우가 있다. 실행불가 또는 count ≠ 0인 경우이다.
- 이러한 결과가 나타나는 이유는 1) 공통변수 count(), buf[]에 대한 동시 업데이트 진행 또는 2) 공통변수 업데이트 구간(임계구역)에 대한 동시 진입이 진행을 꼽아볼 수 있다.
- Busy-Wait: 바쁘게 기다린다는 뜻으로, CPU에서 Producer의 버퍼가 가득차 있으면 Producer는 더 이상 생산을 할 수 없다. 즉, Producer는 버퍼가 빌 때까지 기다린다. 반대로, Consumer의 입장에서 버퍼가 비어있으면 Consumer는 버퍼가 찰 때까지 기다려야 한다.
- size == count 라면 무한루프를 돌면서 기다리라고 하는데, 지속적으로 연산이 이루어지는 상태이므로 계속 세기만 할 뿐, 다른 일을 하지 못한다.
- 이 때 다음과 같이 Semaphore를 이용하여 Busy-Wait을 회피할 수 있고, 궁극적으로 운영체제의 성능을 높인다.
- mutex.value = 1, 생산자: empty.acquire() # of permit = BUF SIZE, 소비자: full.acquire() # of permit = 0
- 만약 버퍼가 가득 차 있다면, Producer 측에서 Semaphore에 block 처리를 해 주어 CPU가 무한루프에 빠지지 않도록 한다. 이 때 Consumer는 버퍼에서 빼주어 빈 공간이 생기는데, 이런 경우 Producer가 새로이 넣을 수 있게 된다. 즉, 서로가 서로를 가두고 풀어줌으로써 효율을 높여준다.
// https://zzsza.github.io/development/2018/07/30/process-synchronization/
import java.util.concurrent.Semaphore;
class Buffer {
int[] buf;
int size, count, in, out;
Semaphore mutex, full, empty;
Buffer(int size) {
buf = new int[size];
this.size = size;
count = in = out = 0;
mutex = new Semaphore(1);
full = new Semaphore(0);
empty = new Semaphore(size);
}
void insert(int item) {
try {
empty.acquire();
// while (count == size);
mutex.acquire();
count++;
buf[in] = item;
in = (in+1)%size;
mutex.release();
full.release();
}
catch (InterruptedException e) {
}
}
int remove() {
try {
full.acquire();
// while (count == 0);
mutex.acquire();
count--;
int item = buf[out];
out = (out+1)%size;
mutex.release();
return item;
}
catch (InterruptedException e) {
return -1; // dummy
}
}
}Reader-Writer Problem
- 공통된 DB를 접근할 경우 발생하는 문제이다. DB는 공통이므로 임계구역이 존재한다.
- 임계구역의 경우, 한 프로세스만 들어올 수 있도록 해야 하는데 이는 비효율적이다.
- DB에서 Reader의 경우 데이터를 읽기만 하고, 쓰지는 않는다. Writer는 데이터를 읽기도 하고 쓰기도 한다. 이 과정에서 상호배타 조건을 사용하는 것은 비효율적이다.
- 효율성을 제고하기 위하여 Each read or write of the shared data must happen within a critical action, guarantee mutual exclusion for Writer, allow multiple readers to execute in the critical section at once 원칙을 따른다.
- 즉, 서로 공유하는 데이터에 한해서, Read/Write는 임계구역에 접근하는 로직으로 구현해야 한다. Writer 두 명이 들어오면 임계구역을 나누어 접근해야 하지만, Reader는 내용이 바뀌지는 않으니까 여러 명이 들어오기를 허용한다. 단, reader가 들어와서 database를 조회하고 있는데 writer가 온다면 writer는 기다려야 한다.
- reader가 들어왔는데 writer는 block되어야 한다. writer가 들어왔는데 reader가 있으면 기다려야 한다. 그리고 reader가 들어와있는데 다른 reader가 들어오고 싶다면 효율성 측면에서 허용된다.
Reader’s Process
- 아래 코드에서 윗 부분은 읽기 작업 전 공통 데이터베이스에 대한 접근 권한을 확인하는 구간이다. 일단 Reader 하나가 들어왔으니 r_count의 값을 1 올려주고, 그 다음 자신이 1빠로 도착한 Reader인지 확인한다. 1빠가 맞다면 자신의 바로 앞에 Writer가 실행중일 수도 있으니 rw_mutex.acquire 하여 Writer의 실행중 여부를 파악한다. 만약 Writer가 정말 실행중이었다면 0값에서 rw_mutex.acquire하는 것이니 Reader는 block되지만, 그냥 아무도 없던 상태에서 1빠로 도착한 것이었다면 1값에서 rw_mutex.acquire 하는 것이므로 이를 0으로 바꿔 Writer의 접근을 막고, 공통 데이터베이스에 진입하게 된다.
- 아랫 부분은 공통 데이터베이스에서 읽기 작업이 끝나고 마무리를 하는 과정이다. 곧 나갈 것이니 r_count를 1 내려주고, 자신이 마지막으로 문닫고 나가는 Reader인지 확인한다. 만약 마지막이라면 이 Reader 프로세스는 다음에 들어올 Writer를 위해 rw_mutex의 값을 1로 갱신하지만, 반면에 마지막이 아니라면 아직 남은 Reader들이 공통 데이터베이스에서 실행중인 것이므로 그냥 조용히 나간다.
while(true) {
rc_mutex.acquire(); // r_count 접근 보호
r_count++;
if(r_count == 1) // 1등으로 도착한 Reader라면
rw_mutex.acquire(); // Writer가 실행중인지 점검
rc_mutex.release(); // r_count 접근 보호 해제
/* some reading tasks... */
rc_mutex.acquire(); // r_count 접근 보호
r_count--;
if(r_count == 0) // 마지막으로 나가는 Reader라면
rw_mutex.release(); // 이제 Writer 들어와~
rc_mutex.release(); // r_count 접근 보호 해제
}Writer’s Process
- 실질적인 쓰기 작업에 들어서기 전 rw_mutex로 자신이 공통 데이터베이스에 접근 가능한지 알아본다. 만약 다른 Reader나 Writer가 작업 중이면 rw_mutex의 값이 0이니 못 들어가지만, 아무도 없으면 1일테니 본인이 rw_mutex의 문을 잠그고 들어갈 수 있게 된다.
while(true) {
rw_mutex.acquire(); // Reader, Writer 실행중인지 검사
/* some writing tasks... */
rw_mutex.release(); // 이제 아무나 들어와~
}- Writer는 같은 Writer가 들어가있어도 block되어 기다려야 한다. 최악의 경우 Reader가 실행중인 상태에서 계속 새로운 Reader 프로세스들이 물밀듯이 밀려오면, Writer는 오랫동안 진입하지 못하고 기아 상태(Starvation)에 빠질 수도 있다.
Dining Philosopher’s Problem
- 문제 설명: 철학자 다섯이서 원형 식탁에 둘러앉아 생각에 빠지다가, 배고플 땐 밥을 먹는다. 그들의 양쪽엔 각각 젓가락 한 짝씩 놓여있고, 밥을 먹으려 할 땐 다음의 과정을 따른다.
1. 왼쪽 젓가락부터 집어든다. 다른 철학자가 이미 왼쪽 젓가락을 쓰고 있다면 그가 내려놓을 때까지 생각하며 대기한다.
2. 왼쪽을 들었으면 오른쪽 젓가락을 든다. 들 수 없다면 1번과 마찬가지로 들 수 있을 때까지 생각하며 대기한다.
3. 두 젓가락을 모두 들었다면 일정 시간동안 식사를 한다.
4. 식사를 마쳤으면 오른쪽 젓가락을 내려놓고, 그 다음 왼쪽 젓가락을 내려놓는다.
5. 다시 생각하다가 배고프면 1번으로 돌아간다.
// https://pastebin.com/z7dAmvAYimport java.util.concurrent.Semaphore;
class Philosopher extends Thread {
int id; // 철학자 id
Semaphore lstick, rstick; // 왼쪽, 오른쪽 젓가락
Philosopher(int id, Semaphore lstick, Semaphore rstick) {
this.id = id;
this.lstick = lstick;
this.rstick = rstick;
}
public void run() {
try {
while(true) {
lstick.acquire(); // 왼쪽 집어들기
rstick.acquire(); // 오른쪽 집어들기
eating(); // 식사
rstick.release(); // 오른쪽 내려놓기
lstick.release(); // 왼쪽 내려놓기
thinking(); // 생각하기
}
} catch (InterruptedException e) {}
}
void eating() {
System.out.println("[" + id + "] eating..");
}
void thinking() {
System.out.println("[" + id + "] thinking..");
}
}
- 만약 모든 철학자가 동시에 배가 고파서 왼쪽 젓가락을 집어든다면 어떻게 될까? 오른쪽 젓가락은 이미 자신의 우측에 앉은 철학자가 집어들었을 것이므로, 모두가 영원히 오른쪽 젓가락을 들지 못하게 된다.
- 그렇게 상단 과정의 2번에서 더이상 진행하지 못하고 철학자들은 영원히 생각에 빠지게 되는데, 이런 현상을 컴퓨터과학에선 교착상태(Deadlock)라고 한다. 한 번 교착상태에 빠진 철학자들은 계속 고뇌만 하다가 기아현상(Starvation)으로 굶어 죽는다.
교착상태 4가지 필요 조건
- 상호배타(Mutual Exclusion):젓가락은 한번에 한 철학자만 사용할 수 있다.
- 보유 및 대기(Hold and Wait): 집어든 젓가락은 계속 들은 채로 사용중인 반대쪽 젓가락을 기다린다.
- 비선점(No Preemption): 이미 누군가 집어 든 젓가락을 강제로 뺏을 수 없다.
- 환형대기(Circular Wait): 모든 철학자들이 자신의 오른쪽에 앉은 철학자가 젓가락을 놓기를 기다린다.
교착상태의 해결: 환형대기 제거
- id가 짝수인 철학자는 왼쪽부터, id가 홀수인 철학자는 오른쪽부터 젓가락을 집어들게 하면 교착상태가 일어나지 않는다.
- 하단의 코드를 실행해보면 계속 무한루프를 돌며 철학자들이 eating과 thinking을 출력하는 것을 확인할 수 있다.
import java.util.concurrent.Semaphore;
class Philosopher extends Thread {
int id; // 철학자 id
Semaphore lstick, rstick; // 왼쪽, 오른쪽 젓가락
Philosopher(int id, Semaphore lstick, Semaphore rstick) {
this.id = id;
this.lstick = lstick;
this.rstick = rstick;
}
public void run() {
try {
while(true) {
if(id % 2 == 0) { /* id가 짝수라면 */
lstick.acquire(); // 왼쪽 집어들기
rstick.acquire(); // 오른쪽 집어들기
}
else { /* id가 홀수라면 */
rstick.acquire(); // 오른쪽 집어들기
lstick.acquire(); // 왼쪽 집어들기
}
eating(); // 식사
rstick.release(); // 오른쪽 내려놓기
lstick.release(); // 왼쪽 내려놓기
thinking(); // 생각하기
}
} catch (InterruptedException e) {}
}
void eating() {
System.out.println("[" + id + "] eating..");
}
void thinking() {
System.out.println("[" + id + "] thinking..");
}
}Banker’s Algorithm
- 회피(Avoidance)는 교착상태를 조금 다른 관점으로 해석한다. 교착상태는 운영체제의 잘못된 자원 분배로 발생하는 것이기에, 교착상태가 발생하지 않도록 운영체제가 안전한 자원 할당에 신경써야 한다고 생각한다.
Unsafe Allocation
- OS가 프로세스 Process 0, Process 1, Process 2에게 12개의 자원을 안전하게 할당시켜야 한다고 가정하자.
- 1. 각 프로세스가 현재 필요로 하는 자원을 나눠준다. (12-(5+2+3) = 2, 자원 2개 남음)
- 2. 자원 2개를 P1에게 마저 할당해준다. P1의 실행이 종료되어 자원 4개가 반환된다. (자원 4개 남음)
- 3. 4개의 자원으로 종료시킬 수 있는 프로세스가 없다. (DEADLOCK)
- 운영체제가 자원이 부족할 지 모르고 불안전한 자원 할당을 했기에, 3번에서 교착상태가 발생했다. 운영체제는 1번에서 P2에게 3개가 아닌 2개의 자원만 할당했어야 한다.
Safe Allocation
- OS가 프로세스 Process 0, Process 1, Process 2에게 12개의 자원을 안전하게 할당시켜야 한다고 가정하자.
- 1. 각 프로세스가 현재 필요로 하는 자원을 나눠준다. (12-(5+2+2) = 3, 자원 3개 남음)
- 2. 총필요가 P1이 4개로 가장 낮으므로, 남은 자원 3개 중 자원 2개를 P1에게 마저 할당해준다. P1의 실행이 종료되어 자원 4개가 반환된다. (자원 5개 남음)
- 3. 5개의 자원으로 P0을 마저 지원하여, 끝까지 실행시키고 자원을 반환받는다. (자원 10개 남음)
- 4. P2에 자원 7개를 할당시켜서 무사히 프로세스 관리를 마친다.
- Banker’s Algorithm의 경우, 운영체제는 은행원 알고리즘으로 사용자 요구가 교착상태를 초래할 수 있는지 사전 검사하여, 안전한 요구만 수락한다. 위험성이 있는 요구는 차후 수락할 수 있을 때까지 계속 거절한다.
Monitor
- 세마포어가 어셈블리어 같은 로우레벨에 적합했다면, 모니터는 하이레벨 환경에 적합한 동기화 도구이다.
- 모니터는 공유 자원과 이에 대한 접근 함수들, 그리고 2개의 큐로 이루어져 있다. 이 2개의 큐는 각각 배타동기, 조건동기를 위한 것이다.
- 배타동기 큐로 인해 공유 자원에는 매 항상 최대 1개의 스레드만 접근 가능하다(=mutex 보장). 만약 접근 중인 스레드가 조건동기로 인해 block 되어 조건동기 큐에 들어가면(=wait), 새로운 스레드가 공유 자원에 접근할 수 있다. 이렇게 들어온 새 스레드는 조건동기 큐에 갇힌 스레드를 깨울 수 있고(=notify), 깨어난 스레드는 현재 공유 자원에 접근 중인 다른 스레드가 없을 때 다시 임계구역에 진입할 수 있다.
- 배타동기: synchronized 키워드 사용
- 조건동기: wait(), notify(), notifyAll() 메소드 사용
Mutual Exclusion(Mutex)
- 임계구역에 synchronized 키워드만 붙이면 상호배제가 보장된다. 아래 코드는 공유 자원 balance에 대한 임계구역인 balance++과 balance — 에 뮤텍스 처리를 한 것이다.
class SharedData {
int balance; // 공유 자원 변수
synchronized void add() { balance++; }
synchronized void sub() { balance--; }
int getBalance() { return balance; }
}Bank Account Problem
class BankAccount {
int balance;
synchronized void deposit(int amount) {
int temp = balance + amount;
System.out.print("+");
balance = temp;
notify();// 자식 쓰레드를 깨워준다.
}
synchronized void withdraw(int amount) {
// 잔액이 부족하면 블록된다.
while (balance < amount)
try {
wait();
}
catch (InterruptedException e) {}
int temp = balance - amount;
System.out.print("-");
balance = temp;
}
int getBalance() {
return balance;
}
}Producer-Consumer Problem
class Buffer {
int[] buf; // 공유 버퍼
int size, count, in , out;
Buffer(int size) {
buf = new int[size];
this.size = size;
count = in = out = 0;
}
synchronized void insert(int item) {
while (count == size) try { // 버퍼가 꽉 차면
wait(); // 쉬러 간다~
} catch (InterruptedException e) {}
buf[in] = item;
in = (in + 1) % size;
count++; // 버퍼에 남은 재고 1 up
notify(); // 지금 쉬는 녀석 나와
}
synchronized int remove() {
while (count == 0) try { // 버퍼가 텅 비었으면
wait(); // 쉬러 간다~
} catch (InterruptedException e) {}
int item = buf[out];
out = (out + 1) % size;
count--; // 버퍼에 남은 재고 1 down
notify(); // 지금 쉬는 녀석 나와
return item;
}
}
