Need for Process Synchronization
공유 데이터에 동시에 액세스하면 데이터 불일치가 발생할 수 있다.
데이터 일관성을 유지하려면 협력 프로세스의 orderly 실행을 보장하는 메커니즘이 필요
생산자와 소비자가 동시에 버퍼를 업데이트하려고 하면 assembly statements가 interleaved 될 수 있습니다.
- example
1. Race Condition
Race Condition(경쟁 상태)은 여러 프로세스들이 동시에 데이터에 접근하는 상황에서, 어떤 순서로 데이터에 접근하느냐에 따라 결과 값이 달라질 수 있는 상황을 말한다.
공유 데이터의 동시 접근(Concurrent access)은 데이터의 불일치 문제를 발생시킬 수 있다. 따라서, Race condition을 막고 일관성을 유지하기 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘인 동기화(Synchronization)가 필요하다.
The statements
counter++;
counter--;
must be performed atomically.
Atomic operation means an operation that completes entirely
without interruption.
대표적으로 다음 세 경우에서 Race Condition이 발생할 수 있다.
1. 커널 모드로 수행 중 인터럽트가 발생하는 경우
의도된 동작은 count++과 count--가 모두 반영되어 count가 초기값을 유지하는 것이지만, 만약 Load를 한 후에 인터럽트가 발생하는 경우 인터럽트의 결과는 반영되지 않고 count++만 반영된다.
이는 커널 모드의 수행이 끝나기 전에는 인터럽트를 받지 않도록 하는 방법(disable/enable)으로 문제를 해결할 수 있다.
2. 프로세스가 시스템 콜을 호출해서 커널 모드로 수행 중인데 Context switch가 발생하는 경우
두 프로세스의 주소 공간에서는 데이터를 공유하지 않지만, 시스템 콜을 수행하는 동안에는 둘 다 커널 주소 공간의 데이터를 접근한다. 따라서 커널 주소 공간에서 작업을 수행하는 도중에 CPU를 빼앗으면 race condition이 발생한다
이는 커널 모드를 수행 중일 땐 CPU가 preempt 되지 않도록 하고, 커널 모드에서 유저 모드로 돌아갈 때 preempt 되도록 함으로써 해결할 수 있다.
3. 멀티 프로세서에서 공유 메모리 내의 커널 데이터에 접근하는 경우
어떤 CPU가 마지막으로 Count를 저장했는지에 따라 결괏값이 달라진다.
싱글 프로세서인 경우 1번에서와 같이 인터럽트 disable/enable 방법으로는 해결할 수 있지만 멀티 프로세서인 경우 인터럽트 제어로는 해결할 수 없다.
한 번에 한 CPU만 커널에 들어갈 수 있도록 하는 방법이 있으나 이는 비효율적이다. 만약 두 프로세서가 서로 다른 데이터에 접근하여 Race condition의 가능성이 없음에도 불구하고 한 번에 한 CPU만 커널에 들어갈 수 있기 때문이다.
따라서, 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대해서만 lock/unlock을 하는 방식으로 해결할 수 있다.
2. Critical Section
critical Section(임계 구역)은 코드 상에서 Race condition이 발생할 수 있는 특정 부분을 말한다. 즉, 공유 데이터를 접근하는 코드 부분을 말한다.
-
Problem – ensure that when one process is executing in its critical section, other process is not allowed to execute in its critical section.
-
Approaches to CS Implementation
- Software-based approaches (software checks to ensure CS) – No guarantee that they will work correctly on modern computers
- Synchronization instructions such as TestAndSet and Swap
- Semaphore
- High-level synchronization construct such as monitor
Critical Section으로 인해 발생하는 문제들을 해결하기 위해서는 다음 조건들을 만족해야 한다.
- Mutual Exclusion (상호 배제)
- 이미 한 프로세스가 Critical Section에서 작업 중이면 다른 모든 프로세스는 Critical Section에 진입하면 안 된다.
- Progress (진행)
- Critical Section에서 작업 중인 프로세스가 없다면, Critical Section에 진입하고자 하는 프로세스가 존재하는 경우 진입할 수 있어야 한다.
- Bounded Waiting (한정 대기)
- 프로세스가 Critical Section에 들어가기 위해 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 Critical Section에 들어가는 횟수에 한계가 있어야 한다. 쉽게 말해, Critical Section에 진입하려는 프로세스가 무한정 기다려서는 안 된다.
3. Synchronization Algorithms
Software-based Approach
Critical Section Problem을 해결하기 위한 알고리즘 들을 살펴보자. 두 프로세스 Pi와 Pj가 있고, 공유하는 공통 변수가 존재한다고 가정하자.
[Algorithm 1]
현재 Critical Section에 들어갈 프로세스가 어떤 프로세스인지를 한 변수로 나타내어 일치하는 프로세스만 진입하도록 하는 단순한 방식이다.
이 방식은 Mutual Exclusion은 만족하지만 Progress는 만족하지 못한다.
예를 들어 Pi의 remainder section 수행 시간이 매우 길어서 여전히 remainder section에서 수행 중이고, Pj가 수행을 한번 마치고 다시 Critical Section으로 진입하려고 한다면 turn == i이기 때문에 진입할 수 없다.
따라서 Critical Section에 아무런 프로세스가 존재하지 않게 된다.
[Algorithm 2]
다른 방식으로는, 특정 프로세스가 Critical Section에 진입할 준비가 되었다는 것을 나타내는 변수를 두어, 다른 프로세스가 Critical Section에 진입하려고 한다면 현재 프로세스는 기다리는 방법이다.
이 방식도 마찬가지로 Mutual Exclusion은 만족하지만 Progress는 만족하지 못한다.
두 프로세스가 flag = true를 수행하고 나면 두 프로세스 모두 무한히 Critical Section에 진입하지 못하고 기다리는 상황이 발생하게 된다.
[Algorithm 3 (Peterson's Algorithm)]
Peterson's Algorithm은 이전의 알고리즘 1과 2를 합쳐놓은 개념이다. turn 변수와 flag 변수를 동시에 사용한다
Pi 프로세스에 대해서, Pi는 flag[i] = true로 바꾸면서 Critical Section에 진입하려고 한다. 그리고 turn = j로 바꿔주면서 상대방이 들어가게 한다. 만약 상대방이 들어가고 싶고 (flag[j] == true), 현재 상대방이 Critical Section에 들어가 있으면 (turn == j) 기다린다. 그렇지 않으면 Pi가 들어간다.
그리고나서 Critical Section을 빠져나오면 들어가고 싶지 않다고 flag[i] = false로 바꿔준다.
이 방식으로는 Mutual Exclusion, Progress, Bounded waiting 모두 만족한다.
하지만, Critical Section 진입을 기다리면서 계속 CPU와 메모리를 사용하는 Busy Waiting의 문제점이 있다.
이제, 이 복잡한 코드 구현들이 하드웨어/소프트웨어 측면에서 어떤 지원들이 제공되는지 알아보자.
4. Synchronization Hardware
- Many systems provide hardware support for critical section code.
- In uni-processors, we could disable interrupts.
- Currently running code would execute without preemption.
- This is generally too inefficient on multiprocessor systems.
- Operating systems using this are not broadly scalable.
하드웨어적으로 현재 상태를 확인하고 변경하는 Test & modify를 atomic 하게 수행할 수 있도록 지원하면 Critical Section Problem은 간단히 해결할 수 있다. 많은 시스템들은 이러한 하드웨어적인 지원을 제공한다.
현대 기계들은 특별한 atomic hardware instruction을 제공한다. (Test_and_Set, swap 등)
이전까지의 알고리즘들은 데이터를 읽고 쓰는 것을 하나의 명령어로 처리할 수 없기 때문에 복잡해졌다.
만약 메모리에서 데이터를 읽으면서 쓰는 것까지 하나의 명령어로 동시에 수행이 가능하다면 코드가 훨씬 간결해지고, 이는 Test_and_Set을 이용하여 아래와 같이 구현된다.
하지만 이러한 하드웨어적인 명령어는 bounded waiting 조건을 만족하지 못하는 단점이 있다. 이 문제를 해결하기 위해서 waiting array라는 배열을 추가로 사용할 수 있는데, 자세한 설명은 생략하겠다
6. Semaphores
세마포어(Semaphore)는 Busy Waiting이 필요 없는 동기화 도구이며, 여러 프로세스나 스레드가 Critical Section에 진입할 수 있는 Signaling 메커니즘이다.
세마포어는 카운터(Counter)를 이용하여 동시에 자원에 접근할 수 있는 프로세스를 제한한다.
주로 S라는 정수형 변수로 나타내며, 이는 사용 가능한 자원의 개수를 의미한다.
또 세마포어 변수는 오직 두 개의 atomic 한 연산을 통해서 접근할 수 있다. 한 프로세스가 세마포어 변수를 수정할 때 다른 프로세스가 동시에 같은 세마포어 변수를 수정할 수 없다.
P(S)는 공유 데이터를 획득하는 연산이고, V(S)는 반납하는 연산이다.
세마포어 종류
-
Counting Semaphore : 정수 값의 범위가 0 이상으로 제한이 없다. 주로 자원의 개수를 세는 데 사용한다.
-
Binary Semaphore : 정수 값이 오직 0 또는 1이다. Mutex lock과 동일한 역할을 갖는다. (Mutex lock과의 차이점)
In general, busy waiting wastes CPU cycles that some other process might be able to use productively.
- Spinlock : process spins while waiting for the lock.
- Have an advantage in that no context switch is required.
- When locks are expected to be held for short times, spinlocks are useful.
- Often employed on multiprocessor systems.
Using Semaphores **
하지만, 이 방식은 Busy Waiting이 발생하므로 비효율적이다. 따라서 Block & Wakeup 방식을 사용한다.
Block & Wakeup 방식은 Critical Section으로의 진입에 실패한 프로세스를 기다리게 하지 않고 Block 시킨 뒤 Critical Section에 자리가 나면 다시 깨워줌으로써 Busy waiting에서의 CPU 낭비 문제를 해결해준다.
일반적으로 Busy Waiting이 비효율적이지만, Critical Section이 매우 짧은 경우 Block & Wakeup의 오버헤드가 더 커질 수도 있다.
7. Deadlock and Starvation
- Deadlock : two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes.
- Let S and Q be two semaphores initialized to 1.
- Starvation : indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended.
8. Monitors
이전의 세마포어의 문제점은 코딩하기가 힘들고 실수하기 쉬우며, 정확성을 입증하기가 어렵다. V(mutex)와 P(mutex)의 순서에 따라 Deadlock이 생기거나 Mutual Exclusion이 깨질 수 있기 때문이다. 이러한 단점을 보완할 수 있는 구조로 Monitor가 있다.
Monitor(모니터)는 동시 수행 중인 프로세스 사이에서 추상 데이터의 안전한 공유를 보장하기 위한 High-level 동기화 구조이다. 공유 데이터를 접근하기 위해서는 모니터의 내부 Procedure를 통해서만 접근할 수 있도록 한다.
세마포어와의 가장 큰 차이점은, 모니터는 락(Lock)을 걸 필요가 없다. 세마포어는 프로그래머가 직접 wait와 signal을 사용하여 Race condition을 해결해야 하지만 모니터는 자체적인 기능으로 해결할 수 있게 된다.
반면, 모니터는 아래와 같이 이루어져 있다.
모니터는 공유 데이터 구조, 공유 데이터에 대한 연산을 제공하는 프로시저(Procedure), 현재 호출된 프로시저간의 동기화를 캡슐화한 모듈(module)이다.
프로세스가 공유 데이터를 사용하기 위해서는 반드시 모니터 내의 Procedure를 통해야 한다. 그리고 동일한 시간엔 오직 한 프로세스나 스레드만 모니터에 들어갈 수 있다.
모니터에 진입하려고 했지만 내부에 프로세스가 들어가 있어 진입하지 못한 프로세스들은 모니터 큐(Monitor Queue)에서 기다린다. 프로세스가 모니터 내에서 기다릴 수 있게 하도록 조건 변수(Condition variable)가 사용된다.
조건 변수는 오직 wait와 signal 연산만으로 사용될 수 있다. 세마포어 변수와 유사하지만 변수가 어떤 값을 가지진 않고, 자신의 큐에 프로세스를 매달아서 sleep 시키거나 큐에서 프로세스를 깨우는 역할만 한다.
9. Classical Problems of Synchronization
1. Bounded-Buffer Problem
생산자 스레드들과 소비자 스레드들이 있고, 사이에 공유 버퍼가 있다고 가정하자.
만약 둘 이상의 생산자가 비어있는 버퍼를 동시에 보고 데이터를 만들어 넣는다면 문제가 발생할 수 있다. 마찬가지로 둘 이상의 소비자가 동시에 동일한 버퍼의 데이터를 사용한다면 문제가 발생할 수 있다. 따라서, 동시에 버퍼에 접근할 수 없도록 락을 걸어줘야 한다.
또, 버퍼가 꽉 찬 상태에서 생산자는 반드시 소비자가 버퍼의 데이터를 사용하기를 기다려야 하고, 버퍼가 빈 상태에서 소비자는 생산자가 버퍼를 채우기를 기다려야 한다.
그러므로 락을 걸고 푸는 용도, 자원의 개수를 카운팅 하는 용도로 세마포어 변수를 사용한다.
2. Readers and Writers Problem **
Readers-Writers Problem은 한 프로세스가 데이터를 수정하는 작업을 수행할 때 다른 프로세스가 접근하면 안 되고, 읽는 작업은 여러 프로세스가 동시에 수행 가능하도록 하는 문제이다.
만약 데이터에 대해 하나의 lock을 사용하게 되면 데이터의 일관성은 지킬 수 있으나, 여러 프로세스가 동시에 읽을 수 있음에도 불구하고 한 프로세스만 읽도록 강제하는 것이므로 비효율적이다.
따라서 현재 수정하려고 하는 프로세스가 없다면 모든 대기 중인 Reader들의 접근을 허용하고, Writer는 대기 중인 Reader가 하나도 없는 경우 접근하도록 한다. 그리고 Writer가 접근 중이면 Reader들은 접근할 수 없도록 한다.
만약 n개의 reader가 기다리고 있다면, 제일 처음 reader만 wrt 세마포어에 넣고 나머지 n-1개의 reader는 mutex 세마포어 큐에 넣어둠으로써 효율성을 높여준다.
Readers-Writers Problem의 해결책은 Starvation의 가능성이 있다. 계속해서 reader가 들어오거나 writer가 들어오는 경우 한쪽이 계속 수행되지 않을 수 있다. 이는 큐에 우선순위를 부여한다거나, 일정 시간이 지나면 자동으로 write or read가 되도록 하여 해결할 수 있다.
- Dining-Philosophers Problem
