Cooperating Process 즉, 서로 협력하고 있는 프로세스 간의 동기화를 의미한다.
현대 운영체제에서는 쓰레드 동기화 (Thread Synchronization) 방식을 대부분 사용한다.
다른 프로세스와 분리되어있는 독립적인 프로세스
다른 프로세스에게 영향을 미치거나 영향을 받는 프로세스
프로세스는 보통 전자우편이나 파일 전송 등을 통해 서로 통신하며 메모리 상의 자료들, 데이터베이스 등의 자원을 공유한다.
대표적인 예시로는 명절 기차표 예약, 대학 온라인 수강신청, 실시간 주식 거래 등이 있다.
현대 운영체제들은 대부분 Cooperating Processes 들로 이루어져 있기 때문에 이 프로세스들 간의 데이터 동기화 (Synchronization)가 무척 중요하다.
많은 사람들이 명절 기차표를 예약한다고 하자. 한 사람이 이미 A2 좌석을 예약했는데 기차표 시스템에 반영이 되지 않는다면? ( = 동기화가 이루어지지 않는다면?) 다른 사람이 A2 좌석을 또 예약하게 되는 불상사가 발생할 수 있다.
이처럼 프로세스 동기화의 주요 목적은 여러 프로세스가 공유하는 자원의 일관성을 유지하는 것이다. 여러 프로세스가 동시에 하나의 공유된 자원에 접근하려고 할 때 이 프로세스들의 순서를 정하여 데이터의 일관성을 유지해야 한다.
하나의 은행 계좌가 있고 부모님은 이 계좌에 입금을, 자녀는 출금을 하려고 한다. 이때 입금(Deposit)과 출금(Withdraw)은 서로 독립적으로 일어난다.
{
InterruptedException {
();
(b);
(b);
p.start();
c.start();
p.join();
c.join();
System.out.println( + b.getBalance());
}
}
{
balance;
{
balance = balance + amount;
}
{
balance = balance - amount;
}
{
balance;
}
}
{
BankAccount b;
Parent(BankAccount b) {
.b = b;
}
{
( ; i < ; i++)
b.deposit();
}
}
{
BankAccount b;
Child(BankAccount b) {
.b = b;
}
{
( ; i < ; i++)
b.withdraw();
}
}
1000원을 100번 입금하고 다시 1000원을 100번 출금하므로 결과값으로 balance = 0이 출력된다.
매우 간단한 과정이므로 2개의 쓰레드가 동작하고 있지만 동기화 오류가 발생하지 않는다.
여기서 입금 과정에서 "+"를 출력하고 출금 과정에서 "-"를 출력해서 시간을 지연시켜 보도록 하자. 또한 입출금 횟수를 100회에서 1000회로 늘려보자.
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;
}
}
그러고 나서 결과값을 살펴보면
++++++++++++++++++++++++++++++++++----------------------------------------------
--------------------------------------------------------------------------++++++
+++----------------------------------------------+++++++++++++++++++++++++++++++
+----+++++++-+++++----+++-------------------------------------------------------
-+++++++-++++-+++++++++-------++++++++++++++++++++++++++++++++++++++++++++++++++
++++++---------------+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+-++++++++++++-------------------++++++++++++++++++++-++++++++++++++++++++++++++
++++++-+------------------------------------------------------------------------
-+++++++++++-+++++++----------------------------------------+-------+-----------
-+------+-----------------------------------------------------------------------
-+------------------------------------------------------------------------------
-+------------------------------------------------------------------------------
-------------------+-------+----------------------------------------------------
------------------------------+-------------------------------------------------
------------------------------------------------------+-------------------------
-+------------------------------------------------------------------------------
-++---------------------------------------++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
balance = 1000000
이와 같이 balance = 1000000로 잘못된 결과값이 출력된다.
이렇게 동작이 복잡해지고 시간 지연이 발생하면 곧바로 동기화 오류가 발생한다.
원인은 바로 서로 다른 쓰레드가 balance라는 공통 변수에 접근함으로써 동기화 오류가 발생하는 것이다. 이를 경쟁 조건 (Race Condition) 이라 하며, 공통 변수에 대한 동시 업데이트 (Concurrent Update)가 그 원인이다.
이러한 오류는 한 번에 하나의 쓰레드만 임계 구역에 접근할 수 있도록 임계구역 문제(Critical-Section Problem) 를 올바르게 해결함으로써 방지할 수 있다.
각각의 쓰레드들은 공통 변수를 변경하거나 테이블을 업데이트 하거나 파일을 작성하는 등의 작업을 담당하는 임계구역 (Critical Section)이라는 코드 뭉치를 갖고 있으며, 이로 인해 임계 구역 문제 (The Critical-Section Problem)가 발생할 수 있다.
임계 구역 문제를 해결하기 위해서는 다음의 조건을 만족해야 한다.
프로세스 또는 쓰레드의 동기화는 다음과 같은 목적을 갖고 있다.
프로세스/쓰레드를 동기화하는 도구는 세마포 (Semaphores), 모니터 (Monitors) 등이 있다.
NoteSemaphores n. (철도의) 까치발 신호기, 시그널; U (군대의) 수기(手旗) 신호
세마포란 동기화 문제를 해결하기 위한 대표적인 소프트웨어 도구이다. 다익스트라 알고리즘으로 유명한 네덜란드의 Edsger Dijkstra가 제안했다.
세마포는 정수형 변수와 두 개의 동작 (P, V)로 이루어져있다. 세마포의 초기값이 1이면 이진 세마포(Binary Semaphore), 1보다 크면 카운팅 세마포(Counting Semaphore)라 한다.
Edsger Dijkstra는 네덜란드 사람이기 때문에 용어가 네덜란드어로 되어있다.
P : Proberen (시도하다, Test)을 의미하며 acquire()로 동작한다.
V : Verhogen (Increment)을 의미하며 release()로 동작한다.
세마포의 구조를 코드로 나타내면 다음과 같다.
class Semaphore {
int value; // number of permits
Semaphore(int value) {
...
}
void acquire() {
value--;
if (value < 0) {
// add this process/thread to list
// block
}
}
void release() {
value++;
if (value <= 0) {
// remove a process P from list;
// wakeup P;
}
}
}
acquire()은 value 값을 감소시키며 만약 value가 0 미만이 된다면 해당 임계 구역에는 이미 다른 프로세스가 들어와있다는 것으로 판단해서 다른 프로세스의 접근을 막는다. 들어오지 못한 다른 프로세스들은 list라는 이름의 대기 큐에 삽입되어 순서를 기다린다. (실제 스케줄링 정책은 구현에 따라 다르다.)
release()는 value 값을 증가시키며 만약 value가 0 이하가 된다면 해당 임계 구역에 진입하기를 기다리는 프로세스가 남아있다는 것으로 판단해서 그 중 하나를 꺼내어 임계 구역에 진입시켜준다.
Note
acquire()는 자원이 사용가능한지 확인하고, 가능하다면 프로세스/쓰레드를 진입시키고 그렇지 않다면 대기시킨다.release()는 작업이 끝난 프로세스/쓰레드를 임계 구역에서 내보내고, 다음 프로세스/쓰레드를 진입시킨다.
세마포의 사용 목적은 다음과 같다.
import java.util.concurrent.Semaphore;
class BankAccount {
int balance;
Semaphore sem;
BankAccount() {
sem = new Semaphore(1);
}
void deposit(int amount) {
try {
sem.acquire();
} catch (InterruptedException e) {}
int temp = balance + amount;
System.out.print("+");
balance = temp;
sem.release();
}
void withdraw(int amount) {
try {
sem.acquire();
} catch (InterruptedException e) {}
int temp = balance - amount;
System.out.print("-");
balance = temp;
sem.release();
}
int getBalance() {
return balance;
}
}
deposit(), withdraw() 과정에 세마포를 추가하여, acquire가 성공할 때만 동작하도록 설정했다. (상호 배제)
결과값은 balance = 0 으로 정상 출력된다.
만약 2개의 프로세스 P1, P2가 있고 P1=>P2 순서로 실행시키려고 한다면 다음과 같이 할 수 있다.
세마포의 값을 0으로 초기화하고
| P1 | P2 |
|---|---|
| sem.acquire() | |
| S1 | S2 |
| sem.release() |
와 같이 설정한다.
결과적으로 P1, P2 둘 중 어느 것을 먼저 실행하여도 결과적으로 P1 -> P2 순서로 수행된다.
class BankAccount {
int balance;
Semaphore sem, semOrder;
BankAccount() {
sem = new Semaphore(1);
semOrder = new Semaphore(0);
}
void deposit(int amount) {
try {
sem.acquire();
} catch (InterruptedException e) {}
int temp = balance + amount;
System.out.print("+");
balance = temp;
sem.release();
semOrder.release();
}
void withdraw(int amount) {
try {
semOrder.acquire(); // 입금이 먼저 완료됐는지 확인 (Ordering)
sem.acquire(); // 임계 구역 진입 (Mutual Exclusion) — 락 획득 순서가 데드락 방지에 중요
} catch (InterruptedException e) {}
int temp = balance - amount;
System.out.print("-");
balance = temp;
sem.release();
}
int getBalance() {
return balance;
}
}
semOrder 변수를 선언하여 Ordering 작업을 담당하도록 한다.
계좌가 비어있는데 출금을 할 수는 없으므로 무조건 입금 => 출금 순으로 동작해야 한다.
따라서 deposit() 마지막에서 semOrder의 release()가 실행되고, withdraw() 실행 전에 semOrder의 acquire()가 실행된다.
만일 입금 전에 출금이 먼저 실행되려 한다면 Ordering에 의해 block된다.