S E P H ' S

[OS] 프로세스 동기화 1 본문

CS/OS

[OS] 프로세스 동기화 1

yoseph0310 2023. 11. 24. 20:01

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

 

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

 

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

 

1. Bank Account Problem(은행 계좌 문제)

동기화 문제 중에서 대표적인 은행 계좌 문제를 살펴보자. 은행에는 하나의 계좌에 입출금을 할 수 있다. 여기서 계좌는 공유 자원이고 입출금은 각각의 프로세스라고 볼 수 있다.

 

public 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);
        }
    }
}

 

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

 

이는 매우 정상적이다. 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에서 1,000으로 증가시켰다. 실행 결과는 다음과 같다.

 

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

balance = 1000000

 

+ 는 입금, - 는 출금 결과다. 주목할 것은 결과가 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 Exclustion) : 오직 한 스레드만이 진입 가능하다. 한 스레드가 임계구역에서 수행 중인 상태에서는 다른 스레드는 절대 이 구역에 접근할 수 없다.
  • 진행(Progress) : 한 임계구역에 접근하는 스레드를 결정하는 것은 유한 시간 이내에 진행되야한다.
  • 유한대기(Bounded waiting) : 임계구역으로 진입하기 위해 대기하는 모든 스레드는 유한 시간 이내에 해당 임계구역으로 진입할 수 있어야 한다.

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

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

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

3. Semaphore(세마포)

세마포는 동기화를 위해 만들어진 소프트웨어로서, 대표적인 동기화 도구이다.

세마포는 두 가지 동작이 존재한다. 초기에는 P, V 로 불렸다. P는 test를 의미하며 acquire() 로 사용하고 V 는 increment를 의미하며 release() 로 사용한다.

 

public class Semaphore {
    int value;
    
    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 는 일반적으로 queue 이다)

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

 

 

세마포를 그림으로 나타내면 위와 같다. 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;

 

P1 P2
  sem.acquire()
Section 1 Section 2
sem.release()  

 

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

 

1. P1이 먼저 실행된 경우

  • Section 1 이전에 아무런 동작이 없으므로 바로 수행한다.
  • sem.release() 를 만나면 value 값을 1 증가시키고, 세마포 큐에 있는 프로세스를 깨워주는데 현재에는 큐에 프로세스가 없으므로 아무 동작도 하지 않는다.
  • P2가 실행.
  • P2의 sem.acquire()를 만나면 현재 value 값은 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가 수행된다.

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

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

class BankAccount2 {
    int balance;

    Semaphore sem, semOrder;

    BankAccount2() {   
        sem = new Semaphore(1);  
        semOrder = new Semaphore(0);        // Ordering 을 위한 세마포
    }

    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

 

입금이 먼저 실행된 것을 볼 수 있다. 만약 교대로 출력하려면 세마포 두개를 사용해 아래와 같이 구현 가능하다.

 

class BankAccount3 {
    int balance;

    Semaphore sem, semDeposit, semWithdraw;

    BankAccount3() {
        sem = new Semaphore(1);
        semDeposit = new Semaphore(0);
        semWithdraw = new Semaphore(0);
    }

    void deposit(int amount) {
        try {
            sem.acquire();      // 임계구역 진입 요청
            int temp = balance + amount;
            System.out.print("+");;
            balance = temp;
            sem.release();
            semWithdraw.release();
            semDeposit.acquire();      // 입금 후에는 반드시 출금해야 하므로 자신을 block.
        } catch (InterruptedException e) {}
    }

    void withdraw(int amount) {
        try {
            semWithdraw.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
저작자표시

'CS > OS' 카테고리의 다른 글

[OS] 프로세스 동기화 3  (3) 2023.11.27
[OS] 프로세스 동기화 2  (1) 2023.11.27
[OS] 쓰레드(Thread)  (0) 2023.11.17
[OS] CPU 스케줄링  (0) 2023.11.17
[OS] 프로세스 관리  (0) 2023.11.17
'CS/OS' Related Articles more