[운영체제(OS)] 8. 프로세스 동기화 1

SungBum Park·2020년 2월 3일
OS
12

운영체제 KOCW 양희재 교수님 강의 정리

목록 보기
8/19

현대 컴퓨터의 메모리에는 여러 프로세스가 존재하는데, 이러한 프로세스들이 하나의 공유 메모리나 또 다른 프로세스에 접근할 때는 매우 신중해야 한다. 이처럼 한 프로세스가 다른 프로세스에게 영향을 받거나 주는 프로세스를 Cooperating process라고 한다. 반대로 아무런 영향을 미치지 않는 독립적인 프로세스는 Independent process이다.

현대 컴퓨터 환경에는 cooperating process가 훨씬 많이 존재하고, 이들은 서로 영향을 미치기 때문에 데이터나 흐름에 대한 동기화가 매우 중요하다. 프로세스 사이에 동기화를 하는 것을 프로세스 동기화(Process Synchronization) 라고 한다.(현재에는 대부분 쓰레드 기준으로 스위칭을 하므로, Thread synchronization으로 많이 불린다.)

대표적인 예로 기차표 예매가 있다. 어느 시간에 한 좌석의 기차표는 반드시 하나만 존재해야한다. 그런데 이를 예매하려는 사용자(프로세스)는 여러 명이다. 이 사용자들이 동시에 하나의 좌석 기차표를 구매하려고 하면 어떠한 일이 발생할까? 실제 환경에서는 당연하게도 동기화 문제를 해결한 시스템이므로 한 사람만이 기차표를 예매할 수 있을 것이다. 만약 동기화에 문제가 발생한다면 한 기차표를 여러 사람이 예매하는 불상사가 발생할 수 있다.

프로세스 동기화는 여러 프로세스가 공유하는 자원의 일관성을 유지하는 것이다. 가령 여러 프로세스가 동시에 하나의 공유된 자원에 접근하려고 할 때 이 프로세스들의 순서를 정하여 데이터의 일관성을 유지시켜주어야 한다.

1. 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) {
		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);
	}
}

// 출금 프로세스
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);
	}
}

위의 코드를 실행시키면 대부분 아래와 같은 결과를 얻을 수 있다.

balance = 0

이 결과는 정상적이다. 100번 1,000원을 입금하고, 100번 1,000원을 출금하면 잔액은 0원이 남는다. 위 코드는 매우 간단한 코드 이므로 2개의 쓰레드가 동작하고 있지만 동기화 문제가 발생할 확률은 매우 낮다. 이를 조금 더 실제 상황과 비슷하게 만들기 위해 시간 지연을 시켜보도록 하자.

// 계좌
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;
	}
}

위 코드는 입금, 출금 기능을 담당하는 BankAccount 클래스에서 입금과 출금을 수행하는 동작에 약간의 시간 지연을 추가하였다. (화면에 출력하는 동작, 변수 대입 동작 추가) 그리고 입출금 횟수를 100에서 1000으로 늘려주었다. 이 코드를 실행시키면 결과는 다음과 같다.

++++++++++++++++++++++++++++++++++----------------------------------------------
--------------------------------------------------------------------------++++++
+++----------------------------------------------+++++++++++++++++++++++++++++++
+----+++++++-+++++----+++-------------------------------------------------------
-+++++++-++++-+++++++++-------++++++++++++++++++++++++++++++++++++++++++++++++++
++++++---------------+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+-++++++++++++-------------------++++++++++++++++++++-++++++++++++++++++++++++++
++++++-+------------------------------------------------------------------------
-+++++++++++-+++++++----------------------------------------+-------+-----------
-+------+-----------------------------------------------------------------------
-+------------------------------------------------------------------------------
-+------------------------------------------------------------------------------
-------------------+-------+----------------------------------------------------
------------------------------+-------------------------------------------------
------------------------------------------------------+-------------------------
-+------------------------------------------------------------------------------
-++---------------------------------------++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

balance = 1000000

+는 입금을 한 경우, -는 출금을 한 경우이고, 주목할 점은 balance값이 0이 아닌 1000000이라는 알 수 없는 값이 출력되었다. 약간의 시간 지연을 준 것만으로도 여러 쓰레드가 하나의 공유 자원을 사용하는 프로그램은 망가지게 된다. 이는 동기화 문제를 해결하지 못하였기 때문에 생기는 문제점이다. +, - 출력되는 결과는 운영체제에서 쓰레드를 스위칭하는 패턴이 매번 다르므로 수행할 때마다 다르게 출력될 수 있다.

이러한 문제가 발생하는 원인은 공통변수(common variable)에 대한 동시 업데이트(concurrent update) 때문이다.

위 예제에서 공통 변수는 계좌의 잔액이다. 이에 접근하는 프로세스의 코드를 보면 다음과 같다.

balance = balance + amount;   // 입금
balance = balance - amount;   // 출금

이는 자바 문법에서는 한 줄이라 문제가 없어 보이지만, 로우 레벨(어셈블리어)로 내려가면 여러 줄로 구현된다. 위 코드를 사용한 예제에서는 문제가 발생할 확률이 매우 낮았지만, 두 번째로 본 예제와 같이 공통변수에 접근하는 공간에서 조금만 시간 지연을 발생시켜도 비정상적인 결과값이 나온 것을 확인하였다.

이를 해결하는 방법은 공통변수에 접근하는 쓰레드는 하나만 존재하도록 관리해야 한다. 이러한 공통변수 구역을 임계구역이라한다.

2. 임계구역(Critical section) 문제

임계구역은 여러 개의 쓰레드가 수행되는 시스템에서 각 쓰레드들이 공유하는 데이터(변수, 테이블, 파일 등)를 변경하는 코드 영역을 말한다. 이는 동기화에서 중요한 문제 중 하나이다.

void deposit(int amount) {
  balance = balance + amount;
}
void withdraw(int amount) {
  balance = balance - amount;
}

위 코드는 은행계좌 문제에서의 임계구역이다.

임계구역을 해결하기 위해서는 3가지 조건이 만족해야한다.

  • Mutual exclusion(상호배타): 오직 한 쓰레드만이 진입 가능하다. 한 쓰레드가 임계구역에서 수행 중인 상태에서는 다른 쓰레드는 절대 이 구역에 접근할 수 없다.
  • Progress(진행): 한 임계구역에 접근하는 쓰레드를 결정하는 것은 유한 시간 이내에 이루어져야한다.
  • Bounded waiting(유한대기): 임계구역으로 진입하기 위해 대기하는 모든 쓰레드는 유한 시간 이내에 해당 임계구역으로 진입할 수 있어야 한다.

2.1 프로세스/쓰레드 동기화

프로세스(쓰레드) 동기화를 통해 이루고자 하는 목적은 다음과 같다.

  • 원하는 결과값을 도출하도록 임계구역 문제를 해결한다.
  • 프로세스의 실행 순서를 원하는대로 제어한다.
  • Busy wait 등과 같은 비효율성을 제거한다.

3. Semaphore(세마포)

세마포는 동기화를 위해 만들어진 소프트웨어로서, 대표적인 동기화 도구이다. 사전적 의미로는 역이나 군대에서 사용하는 수신호라는 뜻이다.

세마포는 두 가지 동작이 존재하는데, 초기에는 P, V로 불렸다.(네덜란드에서 만들어져 네덜란드어의 약자이다.) 현재에는 P는 test를 의미하며 acquire() 로 사용하고, V는 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라는 기다리는 줄에 추가한 뒤 block을 걸어준다.(list는 일반적으로 큐로 되어있다.)

release() 는 value값을 증가시키고, 만약 value값이 0보다 같거나 작으면 임계구역에 진입하려고 대기하는 프로세스가 list에 남아있다는 의미이므로 그 중에서 하나를 꺼내어 임계구역을 수행할 수 있도록 해주어야 한다.

os08-1

세마포를 그림으로 나타내면 위와 같다. list는 실제로 큐로 볼 수 있다. acquire()에 의해 block되는 프로세스는 세마포 내부에 있는 큐에 삽입된 후, 다른 프로세스가 임계구역을 나오면서 release()를 호출하여 세마포 큐에 있는 프로세스를 깨워야 한다.(다시 ready queue로 보낸다.)

위에서 살펴본 것처럼 세마포는 일반적으로 Mutual exclusion을 위해 사용된다.

3.1 Bank Account Problem(은행 계좌 문제)

처음에 살펴본 은행계좌 문제에 세마포를 적용해보자. 위에서 임계구역은 BankAccount 클래스 내부의 입출력하는 부분인 것을 보았다. 여기에 세마포를 적용해보면 아래와 같다.

import java.util.concurrent.Semaphore;  // 세마포를 사용하기 위해 파일 가장 위에 추가해야 한다.

class BankAccount {
	int balance;

	Semaphore sem;
	BankAccount() {   // BankAccount 클래스의 생성자가 호출되면 세마포를 만든다.
		sem = new Semaphore(1);  // value 값을 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;
	}
}

value 값은 임계구역에 몇 개의 프로세스를 접근할 것인지 정하는 것과 같다. 지금은 임계 구역에 하나의 프로세스만 접근가능하기 때문에 1 로 초기화 한다. (위 코드를 제외한 부분은 동일하다.) 이 코드를 수행하면 아래와 같은 결과가 나온다.

// +,- 출력 생략
balance = 0

정상적으로 잔액이 0원이 나온 것을 확인할 수 있다. 이 코드는 임계구역의 문제를 해결하였으므로 몇 번을 수행하여도 같은 결과값이 출력된다.

3.2 Ordering

세마포는 mutual exclusion뿐 아니라 ordering을 하기 위해서도 사용한다. 즉, 프로세스의 실행 순서를 원하는 순서로 설정 할 수 있다.

예를 들어, 프로세스가 P1, P2 두 개가 있다고 가정하자. 원하는 순서는 P1, P2 순으로 실행하기를 원한다. 그러면 아래와 같이 설정해줄 수 있다.

  • sem value = 0;
P1P2
sem.acquire()
Section 1Section 2
sem.release()

먼저, 세마포로 감싼 구역에 들어갈 수 있는 프로세스 개수를 정하는 value값을 0으로 설정한다.

1. P1이 먼저 실행된 경우

  • Section 1 이전에 아무런 동작이 없으므로 바로 수행한다.
  • sem.release() 를 만나면 value값을 1 증가시키고, 세마포 큐에 있는 프로세스를 깨워주는데 현재에는 큐에 프로세스가 없으므로 아무 동작도 하지 않는다.
  • P2가 실행된다.
  • P2의 sem.acquire() 를 만나면 현재 value값은 1이고 이를 1감소시키면 0이 된다. value = 0이면 block을 하지 않으므로, 무사히 Section 2가 수행된다.

2. P2가 먼저 실행된 경우

  • Section 2 이전에 sem.acquire() 가 있으므로 이를 수행하는데, 현재 value값은 0이고 이를 1 감소 시키면 -1 이 된다. value값이 음수면 해당 프로세스를 block시킨다.(세마포 큐에 삽입한다.)
  • P1이 실행되면 Section 1이 바로 수행된다.
  • sem.release() 를 만나면 value값을 1 증가시키고, 세마포 큐에 있는 P2 프로세스를 깨워준다.(현재 value = 0)
  • P2의 Section 2가 수행된다.

위에서 두 가지 경우를 살펴보았듯이, P1, P2 둘 중 어느 것을 먼저 실행하여도 결과적으로 P1 -> P2 순서로 수행하는 것을 알 수 있다.

3.3 입금 출금 순서로 은행계좌 문제 해결하기

위에서 계속 살펴봤던 은행계좌 문제에서 ordering을 적용해보자. 프로세스의 실행 순서는 반드시 입금, 출금 순서로 수행해야한다.

class BankAccount {
	int balance;

	Semaphore sem, semOrder;
	BankAccount() {
		sem = new Semaphore(1);
		semOrder = 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();
		semOrder.release();   // block된 출금 프로세스가 있다면 깨워준다.
	}
	void withdraw(int amount) {
		try {
			semOrder.acquire();   // 출금을 먼저하려고 하면 block한다.
			sem.acquire();
		} catch (InterruptedException e) {}
		int temp = balance - amount;
		System.out.print("-");
		balance = temp;
		sem.release();
	}
	int getBalance() {
		return balance;
	}
}

위처럼 코드를 수정할 수 있다. Ordering을 위한 semOrder 세마포 변수를 선언하고, 출금하는 동작 앞에 acquire(), 입금하는 동작 뒤에 release() 를 추가하였다.

+++++++++++++++++++++++++------------+++++-----++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++------------------------------------------
----------------------------------------
balance = 0

실행 결과는 위와 같다. +(입금)가 맨 앞에서 실행한 모습을 볼 수 있다.(입금, 출금 횟수는 100번으로 줄였다.)

만약, 입금, 출금, 입금, 출금, ... 교대로 출력하도록 하려면 세마포를 두 개 사용하여 아래와 같이 구현할 수 있다.

Semaphore sem, semDeposit, semWithraw;
BankAccount() {
	sem = new Semaphore(1);
	semDeposit = new Semaphore(0);
	semWithraw = new Semaphore(0);
}

void deposit(int amount) {
	try {
		sem.acquire();
		int temp = balance + amount;
		System.out.print("+");
		balance = temp;
		sem.release();
		semWithraw.release();
		semDeposit.acquire();   // 입금후에는 반드시 출금을 해야 하므로 자신을 block한다.
	} catch (InterruptedException e) {}
}
void withdraw(int amount) {
	try {
		semWithraw.acquire();  // 입금보다 먼저 수행하는 것을 막는다.
		sem.acquire();
	} catch (InterruptedException e) {}
	int temp = balance - amount;
	System.out.print("-");
	balance = temp;
	sem.release();
	semDeposit.release();  // 출금 수행이 완료되면 block되었던 입금 프로세스를 깨워준다.
}
int getBalance() {
	return balance;
}
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
balance = 0

Reference

profile
SungBum Park
https://parker1609.github.io/ 블로그 이전
이전 포스트

[운영체제(OS)] 7. 쓰레드(Thread)

다음 포스트

[운영체제(OS)] 9. 프로세스 동기화 2

2개의 댓글

comment-user-thumbnail
HwangJinSeong
2021년 2월 4일

잘 읽었습니다. 👍

답글 달기
comment-user-thumbnail
원종서
2021년 12월 25일

잘 읽고 있습니다 :)
세마포를 스레드의 순서를 정하는 용도로 사용할때

  1. P1이 먼저 실행된 경우
    2.Section 1 이전에 아무런 동작이 없으므로 바로 수행한다.
    3.sem.release() 를 만나면 value값을 1 증가시키고, 세마포 큐에 있는 프로세스를 깨워주는데 현재에는 큐에 프로세스가 없으므로 아무 동작도 하지 않는다.

  2. P2가 실행된다.

  3. P2의 sem.acquire() 를 만나면 현재 value값은 1이고 이를 1감소시키면 0이 된다. value = 0이면 block을 하지 6. 않으므로, 무사히 Section 2가 수행된다.

으로 정리해 주셨는데

만약 4번째 스텝에서 P2가 아닌 P1가 실행될 확률은 없는건가요?

답글 달기