프로세스 동기화

이번 시간에는 프로세스 동기화에 대해서 알아보도록 하겠습니다. 

 

프로세스 동기화란 OS에서 같은 메모리 공간을 공유하고 있는 프로세스들을 관리하기위한 방법입니다. 프로세스 동기화를 진행하게 되면 변수를 사용함으로써 데이터의 일관성을 유지하는데 도움이 됩니다. 프로세스 동기화를 하기위해 여러가지 방법이 있는데 이번 시간에 semaphore (이하 세마포어), mutex lock (이하 뮤텍스 락), hardware synchronization (이하 하드웨어 동기화)를 알아봅니다. 

 

 

프로세스 동기화란?

OS는 컴퓨터에서 모든 애플리케이션을 관리하는 소프트웨어이고 기본적으로 우리 컴퓨터에서 부드럽게 동작하는 것을 도와줍니다. 

 

이러한 이유때문에 OS는 많은 일을 수행할 수 밖에 없습니다. 때로는 동시에 일을 수행해야 하기도 하죠. 동시에 일을 수행할 때 공유 자원에 접근하는 것이 아니면 보통 문제가 일어나지 않지만 공유 자원에 접근해야 하는 경우가 많기 때문에 문제가 발생할 수 밖에 없습니다. 

 

예를 들어서 온라인 뱅킹에서 같은 데이터베이스에 각각의 고객들에대한 계좌 잔액이 저장되어있다고 가정해봅시다. 우리는 현재 x원의 잔액을 가지고 있습니다. 

 

이때 우리는 우리 계좌에서 돈을 조금 빼고싶습니다. 그리고 마침 같은 시간에 어떤 사람이 내 계좌의 잔액을 보고싶어합니다. 

 

우선 우리는 계좌에서 돈을 조금 뺐기 때문에 x원보다 낮은 금액을 잔액으로 가지고 있을겁니다. 하지만 동시간에 내 계좌 잔액을 보고싶어한 사람은 어떨까요? 아마 잔액이 x원으로 찍혀있을것입니다. 

 

이렇듯 데이터 부정합은 하나의 시스템에서 여러 프로세스가 공유자원에 접근했을 때 생깁니다. 그리고 이것이 우리가 프로세스 동기화를 알아야 하는 이유이기도 하죠. 

 

 

프로세스 동기화에 필요한 Section

우리는 앞에서 프로세스 동기화에 대한 전반적인 내용과 어떤 상황에서 프로세스 동기화가 필요한지에 대해서 알아봤습니다. 프로세스 동기화를 하기 위해서는 다양한 Section에 접근해야 하는데 가장 기본적인 네개의 Section에 대해서 알아보죠

 

• Entry Section : Entry Section은 프로세스의 순서를 보여줍니다. 
• Critical Section : Critical Section은 공유자원에 오직 하나의 프로세스만 접근할 수 있도록 하는 구역입니다. 우리말로 임계 구역이라고도 해석되는데, 하나의  프로세스가 Critical Section에 있을 때 다른 프로세서가 못들어오게 막아야 합니다. 
• Exit Section : 하나의 프로세스 실행 후에 공유자원에서 다른 프로세스의 순서를 Exit Section이 관리합니다. 
• Remainder Section : 위에 세개의 Section을 제외한 나머지 코드를 Remainder Section이라고 합니다. 

 

우리가 이중에서 가장 눈여겨 봐야할 Section은 바로 Critical Section입니다. 

 

Critical Section은 race condition을 막기위해 사용되는 방법으로도 많이 알려져 있습니다. race condition에 대한 자세한 내용은 아래의 링크를 확인해주세요. 그런데 이 Critical Section이 없으면 어떻게 될까요? 어떤 문제가 생길까요? 

 

https://coding-review.tistory.com/351

동시성문제와 Thread-safe

 

어떤 상황에서 싱글 프로세스에 의해 접근될 수 있는 일련의 코드들을 우리는 Critical Section이라고 부릅니다. 이 의미는 많은 수의 프로세스가 공유 자원을 변경하기위해 접근할 때 오직 하나의 프로세스만 공유된 자원에 접근할 수 있도록 한다는 의미이죠. 

 

wail() 함수가 주로 Critical Section에서 순서를 관리하는데 사용되고 signal() 함수는 Critical Section으로부터 빠져나오는 것을 관리합니다. 

 

만약 Critical Section을 제거한다면 우리는 동시에 실행되는 프로세스가 끝났을 때 데이터의 정합성을 보장받지 못할 것입니다. 

 

이러한 문제를 Critical Section Problem 이라고 합니다. 

 

 

동기화에 필요한 요구사항

아래 소개하는 세개의 요구사항이 Critical Section Problem을 해결할 수 있는 방법입니다. 

 

• Mutual Exclusion (상호 배제) : 만약 하나의 프로세스가 Critical Section에서 실행중이라면 다른 프로세스는 동시에 Seciton에 접근할 수 없습니다. 
• Progress (진행) : 만약 Critical Section에 프로세스가 존재하지 않으면 프로세스는 Critical Section에 들어가기 위해 기다려야 하고 기다린 뒤엔 하나의 스레드만 Critical Section에 접근할 수 있습니다. 
• No Starvation (기아상태 방지) / Bounded Waiting : 기아상태는 프로세스가 Critical Section에 접근하기위해 평생 기다리는 것을 이야기합니다. 그리고 영원히 기회가 주어지지 않습니다. 이러한 기아상태를 방지를 보통 Bounded Waiting이라고 부릅니다. 
  • 프로세스가 Critical Section에 들어가기위해 영원히 기다려서는 안된다. 
  • 프로세스가 Critical Section으로의 접근이 허용되었을 때 반드시 제한되거나 경계가 있어야한다.
  • 이 경계에 도달했을 때, 프로세스는 Critical Section에 접근하는 것이 허용될 수 있어야한다. 

 

Mutual Exclusion 구현 방법

이 구현 방법에 대해서는 자세히 알 필요까지는 없습니다. 그냥 이런게 있구나 싶을정도만 알고 계시면 됩니다. 

 

상호 배제를 구현하는 방법에는 여러가지가 있지만 가장 대표적으로 알려진 것 두개만 소개해드리도록 하겠습니다. 바로 Dekker 알고리즘과 Peterson 알고리즘입니다. 

 

이 둘은 flag와 turn으로 프로세스의 접근을 막는 것이 비슷해보이지만 약간 다른 차이점을 가지고 있는데요. 우선 flag와 turn에 대해서 알아보죠

 

• boolean flag[] :  boolean 배열인 flag 변수는 우선 모두 false로 초기화합니다. 이 flag 배열들은 Critical Section으로 들어갈 수 있는지를 체크하는 배열입니다. 
• int turn : Integer 형 turn 변수는 Critical Section에 들어가기위해 준비중인 프로세스의 수를 나타냅니다. 

 

Dekker 알고리즘은 동시성 프로그래밍에서 상호 배제를 해결하기위한 첫번째 방법으로 알려져있습니다. 이 알고리즘은 충돌 없이 공유된 자원을 두개의 스레드가 사용할 수 있도록하는 방법입니다. 

 

package algorithm.dekker;

class Main {
    static boolean[] flag = {false, false};
    static int turn = 0;
    static int N = 4;
    // flag: 어떤 프로세스가 Critical Section에 접근하기를 원하는지
    // turn: Critical Section에 들어갈 순서
    // N: 루프를 돌 횟수

    static Thread process(int i) {
        return new Thread(() -> {
            int j = 1 - i;
            for (int n=0; n<N; n++) {
                log(i+": want CS"); // LOCK
                flag[i] = true;   // 1 Critical Section에 들어가길 원하는 프로세스
                while (flag[j]) { // 2 만약 Critical Section에 들어갈 수 있다면
                    if (turn == i) { Thread.yield(); continue; } // 3a 만약 내 차례이면
                    flag[i] = false;      // 4a 만약 내차례가 아니면 난 들어가지 않겠다
                    while (turn == j) Thread.yield(); // 4b 너의 차례가 끝날때가지 기다리겠다
                    flag[i] = true; // 4c 너의 차례가 다 끝났으니 내가 들어가겠다
                }

                log(i+": in CS"+n);
                sleep(1000 * Math.random()); // 5 Critical Section에 들어가서 수행중

                log(i+": done CS"); // UNLOCK
                turn = j;        // 6 이제 네차례야
                flag[i] = false; // 7 난 Critical Section에 이미 들어갔어
            }
        });
    }


    public static void main(String[] args) {
        try {
            log("Starting 2 processes (threads) ...");
            Thread p0 = process(0);
            Thread p1 = process(1);
            p0.start();
            p1.start();
            p0.join();
            p1.join();
        }
        catch (InterruptedException e) {}
    }

    static void sleep(double t) {
        try { Thread.sleep((long)t); }
        catch (InterruptedException e) {}
    }

    static void log(String x) {
        System.out.println(x);
    }
}

 

Peterson 알고리즘은 Dekker 알고리즘과 마찬가지로 동시성 프로그래밍에서 상호 배제를 해결하기위한 알고리즘입니다. 다만 차이점은 Peterson 알고리즘은 프로세스가 두개인 경우에만 사용할 수 있다는 점이죠. Dekker 와 process 부분만 다르니까 그부분만 설명하도록 하겠습니다. 

 

    static Thread process(int i) {
        return new Thread(() -> {
            int j = 1 - i;
            for (int n=0; n<N; n++) {
                log(i+": want CS"); // LOCK
                flag[i] = true; // 1 Critical Section에 들어가길 원해
                turn = j;       // 2 j는 다른 프로세스의 턴이야
                while (flag[j] && turn == j) Thread.yield(); // 3 만약 네가 들어가고 싶다면 양보해줄게

                log(i+": in CS"+n);
                sleep(1000 * Math.random()); // 4 Critical Section에 들어가서 수행중

                log(i+": done CS"); // UNLOCK
                flag[i] = false; // 5 나 이제 끝났어
            }
        });
    }

 

Peterson 알고리즘은 상대방 프로세스에게 자신의 순서를 양보한다는 특징이 있습니다. 

 

 

Hardware Synchronization (하드웨어 동기화)

하드웨어는 가끔 Critical Section 문제를 해결할 때 도움을 줍니다. 몇몇 OS는 Lock (이하 락) 을 제공하기 떄문이죠. 

 

하나의 프로세스가 Critical Section에 들어갈 때, 락이 주어지고 Critical Section에서 나오기 전에 프로세스는 반드시 실행되어야 합니다. 

 

그 결과 추가적인 프로세스는 만약 달느 프로세스가 이미 Section을 사용했다면 Critical Section에 접근할 수 없습니다. 

 

 

Mutex Locks (뮤텍스 락)

하드웨어 동기화를 구현하는 것은 매우 어려운 작업입니다. 그래서 뮤텍스 락이 대안책으로 떠오르게 되었습니다. 

 

뮤텍스는 중요 섹션의 리소스에 대한 액세스를 동기화하는 데 사용되는 잠금 메커니즘입니다. 이 방법에서는 중요 섹션에 락을 사용합니다. 프로세스가 진입 섹션에서 진입할 때 락이 설정되고, 프로세스가 종료 섹션에서 종료할 때 설정이 해제됩니다.

 

 

Semaphores (세마포어)

세마포어는 신호를 주고받는 방버입니다. 프로세스는 세마포어에서 기다리고있는 프로세스에 신호를 줄 수 있습니다. 세마포어는 뮤텍스와 다른데 뮤텍스는 shared lock를 세팅한 프로세스에 의하여 인지될 수 있기 때문입니다. 

 

세마포어는 wait() 과 signal() 함수를 이용해서 프로세스 사이에 동기화를 이끌어냅니다. 

 

 

 

마치며

여기까지 프로세스 동기화에 대해서 알아봤습니다. 알아야 할 내용도 많고 복잡해서 솔직히 이해를 했는지도 잘 모르겠네요. 면접용으로 다시 정리하면서 되새김질 해야할 것 같습니다. 

 

긴 글 읽어주셔서 감사합니다. 오늘도 즐거운 하루 되세요!

 

 

출처

https://www.scaler.com/topics/operating-system/process-synchronization-in-os/

Process Synchronisation in OS - Scaler Topics

https://github.com/javaf/peterson-algorithm/blob/master/Main.java

GitHub - javaf/peterson-algorithm: Peterson's algorithm is a concurrent algorithm for mutual exclusion with multiple processes u

https://github.com/javaf/dekker-algorithm/blob/master/Main.java

GitHub - javaf/dekker-algorithm: Dekker's algorithm is the first known correct solution to the mutual exclusion problem in concu