이 포스팅은 운영체제 정리 시리즈 20 편 중 8 번째 글 입니다.
목차
프로세스 동기화가 발생하는 예시와 목적, 그리고 그것을 해결하기 위한 원칙에 대해 알아본다.
1. 프로세스 동기화란?
하나의 자원을 한 순간에 하나의 프로세스(쓰레드)만이 이용하도록 제어하는 것
1.1 배경
현대 컴퓨터의 메모리에는 여러 프로세스가 존재하는데, 이러한 프로세스들이 하나의 공유 메모리나 또 다른 프로세스에 접근할 때는 매우 신중해야 한다. 이처럼 한 프로세스가 다른 프로세스에게 영향을 받거나 주는 프로세스를 Cooperating process라고 한다. 반대로 아무런 영향을 미치지 않는 독립적인 프로세스는 Independent process이다.
현대 컴퓨터 환경에는 cooperating process가 훨씬 많이 존재하고, 이들은 서로 영향을 미치기 때문에 데이터나 흐름에 대한 동기화가 매우 중요하다. 프로세스 사이에 동기화를 하는 것을 프로세스 동기화(Process Synchronization) 라고 한다.(현재에는 대부분 쓰레드 기준으로 스위칭을 하므로, Thread synchronization으로 많이 불린다.)
1.2 필요성
대표적인 예로 기차표 예매가 있다. 어느 시간에 한 좌석의 기차표는 반드시 하나만 존재해야한다. 그런데 이를 예매하려는 사용자(프로세스)는 여러 명이다. 이 사용자들이 동시에 하나의 좌석 기차표를 구매하려고 하면 어떠한 일이 발생할까? 실제 환경에서는 당연하게도 동기화 문제를 해결한 시스템이므로 한 사람만이 기차표를 예매할 수 있을 것이다. 만약 동기화에 문제가 발생한다면 한 기차표를 여러 사람이 예매하는 불상사가 발생할 수 있다.
1.3 목표
프로세스 동기화는 여러 프로세스가 공유하는 자원의 일관성을 유지하는 것이다. 가령 여러 프로세스가 동시에 하나의 공유된 자원에 접근하려고 할 때 이 프로세스들의 순서를 정하여 데이터의 일관성을 유지시켜주어야 한다. 이 부분에 대한 자세한 목적은 아래의 예를 파악하며 문제를 인지한 후에 명확하게 재정의하겠다.
2. Bank Account Problem(은행 계좌 문제)
동기화의 필요성을 가장 잘 느낄 수 있는 은행 계좌 문제에 대해 알아본다.
2.1 문제 설명
동기화 문제 중에서 대표적인 은행 계좌 문제를 살펴보자. 은행에는 하나의 계좌에 입금, 출금을 할 수 있다. 여기서 계좌는 공유하는 자원이고, 입금과 출금은 각각 프로세스라고 볼 수 있다. 부모님이 자식에게 입금을 하고, 자식은 출금을 하는 상황을 자바로 구현한 코드는 아래와 같다.
// 계좌
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;
// 생성자는 공유하는 계좌를 초기값으로 가진다.
Parent(BankAccount b) {
this.b = b;
}
public void run() { // run(): 쓰레드가 실제로 동작하는 부분(치환)
for (int i = 0; i < 100; i++)
b.deposit(1000);
}
}
멤버 변수로 계좌를 가지고, 이것을 생성할 때 인자로 받는 클래스이다. 해당 클래스에서 run()은 입금을 100번 수행한다.
// 출금 프로세스
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);
}
}
멤버 변수로 계좌를 가지고, 이것을 생성할 때 인자로 받는 클래스이다. 해당 클래스에서 run()은 출금을 100번 수행한다.
// 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());
}
}
main 함수에서는 위에서 만든 클래스들을 사용하여, 계좌를 공유하는 두 개의 쓰레드를 만든다. 그리고 부모, 자식 클래스에서 각각 입금과 출금을 100번씩 수행하고, 결과적으로 남은 잔액을 조회한다. 잔액은 0이 나와야 할 것이다.
// Result
balance = 0
이 결과는 정상적이다. 100번 1,000원을 입금하고, 100번 1,000원을 출금하면 잔액은 0원이 남는다. 위 코드는 2개의 쓰레드가 동작하고 있음에도 불구하고 동기화 문제가 발생할 확률은 매우 낮다. 반복이 100번 밖에 안 일어나는 매우 간단한 코드 이기 때문이다.
2.2 동기화 문제 발생
실제 상황에서는, 입금, 출금 명령을 내리고 이 명령이 전달되는데 까지 시간이 소요된다. 그런 상황을 만들기 위해 출금하는 과정에서 temp라는 필요없는 변수를 추가하고, +,-를 출력하고, 반복 횟수를 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;
}
}
// Result
++++++++++++++++++++++++++++++++++----------------------------------------------
--------------------------------------------------------------------------++++++
+++----------------------------------------------+++++++++++++++++++++++++++++++
+----+++++++-+++++----+++-------------------------------------------------------
-+++++++-++++-+++++++++-------++++++++++++++++++++++++++++++++++++++++++++++++++
++++++---------------+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+-++++++++++++-------------------++++++++++++++++++++-++++++++++++++++++++++++++
++++++-+------------------------------------------------------------------------
-+++++++++++-+++++++----------------------------------------+-------+-----------
-+------+-----------------------------------------------------------------------
-+------------------------------------------------------------------------------
-+------------------------------------------------------------------------------
-------------------+-------+----------------------------------------------------
------------------------------+-------------------------------------------------
------------------------------------------------------+-------------------------
-+------------------------------------------------------------------------------
-++---------------------------------------++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
balance = 1000000
+는 입금을 한 경우, -는 출금을 한 경우이고, 주목할 점은 balance값이 0이 아닌 1000000이라는 알 수 없는 값이 출력되었다. 또한 여러번 실행할 경우 100000이라는 값이 고정되어 출력되는 것도 아니다. 결과가 불일치하며, 비일관적이다. (비일관적인 이유는 운영체제에서 쓰레드를 스위칭하는 패턴이 매번 다르기 때문이다.)
약간의 시간 지연을 준 것만으로도 여러 쓰레드가 하나의 공유 자원을 사용하는 프로그램은 망가지게 된다.
2.3 왜 발생할까?
이러한 문제가 발생하는 원인은 공통변수(common variable)에 대한 동시 업데이트(concurrent update) 때문이다.
위 예제에서 공통 변수는 계좌의 잔액이다. 이에 접근하는 프로세스의 코드를 보면 다음과 같다.
balance = balance + amount; // 입금
balance = balance - amount; // 출금
이는 자바 문법에서는 한 줄이라 문제가 없어 보이지만, 로우 레벨(어셈블리어)로 내려가면 여러 줄로 구현된다. 예를 들어, balance를 업데이트 하는 하이 레벨 코드 1줄이 로우 레벨에서 3줄로 구현된다고 하자.
- 공유 변수인 현재 잔액을 복사한다.
- 현재 잔액에서 명령을 수행한다.
- 나온 결과를 가지고 잔액을 갱신한다.
그런데, parent가 수행하던 도중에 1000번을 다 수행하지 못한 상황에서 interrupt(이 경우에는 시간 지연을 걸었으므로 timer interrupt가 되겠다.)가 걸려 2번 라인에서 멈췄다고 생각해보자. parent가 1000원을 입금했지만, 업데이트가 되지 않아 여전히 현재 잔액은 0이다.
이번에는 child가 부모님이 용돈을 넣은 줄 알고 신나서 돈을 뽑는 상황을 생각해보자. 잔액을 확인했더니, 아직 0이다. 그래서 child는 마이너스 통장을 통해 돈은 인출하고 현재 잔액은 -1000이 된다.
따라서 이 경우, 입금과 인출이라는 행위는 프로세스 입장에서 원자성을 갖는 행위이므로 동기화가 필수적이다. 기억이 안난다면 이 글을 보자. 가볍게 이해하는 컴퓨터 01: 용어 정리
3. 임계구역(Critical section) 문제
위의 예에서 보았던 문제를 임계구역 문제라 한다. 임계구역은 여러 개의 쓰레드가 수행되는 시스템에서 각 쓰레드들이 공유하는 데이터(변수, 테이블, 파일 등)를 변경하는 코드 영역을 말한다. 이는 동기화에서 중요한 문제 중 하나이다. 은행계좌 문제에서의 임계구역은 다음과 같다.
void deposit(int amount) {
balance = balance + amount;
}
void withdraw(int amount) {
balance = balance - amount;
}
3.1 해결 방법
임계구역을 해결하기 위해서는 3가지 조건이 만족해야한다.
- Mutual exclusion(상호배타)
- 오직 한 쓰레드만이 진입 가능하다. 한 쓰레드가 임계구역에서 수행 중인 상태에서는 다른 쓰레드는 절대 이 구역에 접근할 수 없다.
- Progress(진행)
- 한 임계구역에 접근하는 쓰레드를 결정하는 것은 유한 시간 이내에 이루어져야한다.
- 누가 먼저 들어갈 것인지 빠르게 결정해라
- Bounded waiting(유한대기)
- 임계구역으로 진입하기 위해 대기하는 모든 쓰레드는 유한 시간 이내에 해당 임계구역으로 진입할 수 있어야 한다.
- 기다리는 모든 쓰레드가 진입가능하도록 만들어라.
4. 프로세스/쓰레드 동기화의 목적
- 원하는 결과값을 도출하도록 임계구역 문제를 해결한다.
- 프로세스의 실행 순서를 원하는대로 제어한다.
- Busy wait 등과 같은 비효율성을 제거한다.
Reference
KOCW 양희재 교수님 - 운영체제
양희재 교수님 블로그(시험 기출 문제)
codemcd 님의 정리글
Operating System Concepts, 9th Edition - Abraham Silberschatz