[OS] Synchronization

Producer-Consumer

item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int count = 0;

Producer

Consumer

 

몇 가지 변수들을 공유하며 producer 와 consumer 의 코드는 위와 같다고 하자. 이 코드들은 BUFFER SIZE − 1 크기의 버퍼를 공유하며 사용하도록 하는 코드이다. 개별적으로 보면 잘 작동할 것 같지만, 동시에 실행하면 문제가 발생할 수 있다.

예를 들어, count 가 5 이고 producer 와 consumer 가 동시에 실행된다면 "count++" 과 "count--" 이후의 count 값이 4, 5, 6 이 될 수 있다.

 

Race Condition

 "count++" 과 "count--" 의 동시 실행은 위와 같이 이루어 진다. 위와 같은 경우는 producer 와 consumer 의 count 가  4, 6 이 되며, T4 와 T5 의 순서가 바뀌면 6, 4 가 된다.

이렇게 여러 스레드나 프로세서가 동일한 데이터에 동시에 접근하고 조작하여, 실행 결과가 접근이 이뤄지는 특정 순서에 따라 달라지는 상황을 race condition 이라고 한다.

race condition 을 막기 위해서는 한번에 한 프로세스가 count 변수를 조작하도록 보장해야 하는데, 이를 위해 프로세스의 동기화가 필요하다. multithread 의 병렬처리 중 변경 사항의 간섭을 막기 위해 프로세스 동기화는 필수적이다.

 

Critical Section Problem

shared memory 나 resouce 가 여러 프로세스에 의해 접근되는 프로그램의 일부를 critical seciton 이라고 한다. 동기화 시스템에선 한 프로세스가 critical section 을 실행한다면, 다른 프로세스는 critical section 을 실행할 수 없다.

race condition ( or critical section problem ) 의 해결책은 프로세스가 데이터를 협력적으로 공유할 수 있도록 활동을 동기화 하는데 사용할 수 있는 프로토콜을 설계하는 것이다. 

 

프로세스는 critical section 에 들어가 전 권한을 요청해야 하며 코드의 구조는 다음과 같다.

• Entry section  : 요청을 구현하는 코드의 segment
• Critical section
• Exit section : critical section 의 종료를 알려주는 코드의 segment
• Remainer section : 나머지 코드

 

critical section problem 의 해결방법으로 다음 세 가지 요구사항을 만족해야 한다.

• Mutual Exclusion : 프로세스 Pi 가 critical section 에서 실행 중이라면, 다른 프로세스는 해당 critical section 에서 실행할 수 없다.
• Progress : critical section 에서 실행 중인 프로세스가 없고 일부 프로세스가 critical section 에 들어가기 원하면, 다음에 critical section 에 넣을 프로세스를 결정하는 것은 무기한으로 연기할 수 없다.
• Bounded Waiting : 한 프로세스가 critical section 에 들어가도록 요청한 후 요청이 승인되기 전까지 다른 프로세스가 해당 critical sections 에 들어갈 수 있는 횟수에 제한이 있다.

 

 

Peterson's Solution

 

 

 

Mutex Locks

mutual exclusion 의 약어로, 프로세스는 critical section 에 들어가기 전에 lock 을 획득하고, critical section 을 벋어나면 lock 을 해제한다.

acquire() 은 lock 을 얻는 함수, release() 는 lock 을 놓아주는 함수이다. acquire() 또는 realse() 는 atomic 하게 수행되어야 한다.

mutex lock 은 available 변수를 가지고 있어, lock 이 가능한지 아닌지 알려준다. available 의 상태에 따라 프로세스는 다음과 같이 작동한다.

• available : mutex lock 을 사용하는 스레드가  없으므로, acquire() 이 성공하고 lock 은 unavaialbe 상태가 된다.
• unavailable : 특정 스레드가 mutex lock 을 사용중이므로, 프로세스는 lock 이 해제될 때까지 block 된다.

mutex 에는 스레드의 queue 가 있어, block 된 프로세스들은 queue 에서 Sleep 상태로 대기하다가 Wakeup 상태가 되면 acquire() 를 시도한다.

 

 

Spin Locks

한 프로세스가 critical section 을 사용중일 때, cirtical section 에 들어가려는 다른 프로세스는 acquire() 을 호출하기 전까지 계속 loop 해야만 한다. 즉, 무한 루프를 돌며 기다리는 lock 을 Spin Lock 이라고 한다.

Sping Lock 에서는 acquire() 과 release() 가 위와 같이 구현된다.

resource 가 spin lock 에 의해 보호된다면, resource 를 얻기 시도하는 스레드는 해당 resource 가 unlock 될 때까지 busy-wait (loop, or spin) 하게 된다. 이는 멀티프로그래밍 시스템에서 문제가 되며 CPU cycle 을 낭비한다

 

 

Semaphore

mutex lock 과 유사하게 동작하지만, 동기화에 있어 보다 정교함을 제공한다.

wait(int* pCount) {
    while (*pCount <= 0); // no-op
    (*pCount)--;
}

signal(int* pCount) {
    (*pCount)++;
}

정수 변수인 Semaphore S 는 atomic operations 인 wait(), signal() 를 통해서만 접근 된다. wait() 연산은 P(), signal() 연산은 V() 로도 부른다.

한 프로세스가 wait()나 signal()을 통해 세마포어 값을 수정할 때, 다른 프로세스는 동일한 세마포어 값을 동시에 수정할 수 없다.  또한 wait(S)의 경우, S의 정수 값(S ≤ 0)과 그 수정 가능성(S--)에 대한 테스트가 중단 없이 실행되어야 한다

 

 

Binary Semaphore

Binary Semaphore의 정수값은 오직 0 과 1사이의 범위만 가능하다.

Mutex Locks 와 동일한 역할을 한다.

 

Counting Semaphore

Counting Semaphore의 정수값은 0 이상인 임의의 정수값이다.

유한한 수의 인스턴스로 구성된 특정 resource 에 대한 액세스를 제어하는 데 사용할 수 있다.

Counting Semaphore 의 동작 과정은 다음과 같다.

1. 세마포어는 사용 가능한 리소스 수로 초기화
2. 리소스 사용하려는 각 프로세스는 세마포어의 wait() 사용하여 count 는 줄어듬
3. 프로세스가 리소스 해제하면 signal() 사용하여 count 증가함
4. count 가 0이면 모든 리소스가 사용중이므로, 해당 상태에서 리소스를 사용하려는 프로세스는 count 가 0보다 커질때까지 block

 

A Solution of the Busy-Waiting Problem of Semaphore

위에서 구현한 세마포어도 busy-wait (loop, or spin) 문제가 발생한다. (한 스레드가 critical section 에 있다면, critical section 에 들어가려는 다른 스레드들은 entry code 에서 계속 loop 해야한다.)

block(sleep) 과 wakeup 연산을 사용하면 wait 와 signal 을 구현하면 busy-waiting 문제를 해결할 수 있다. 

프로세스가 wait 연산을 실행하고 semaphore 값이 양수가 아님을 확인하면 즉시 block() 한다. block 된 프로세스는 semaphore 에 연결된 waiting queue 에 배치하고 프로세스의 상태를 waiting state 로 변경한다. 다음 CPU scheduler 로 제어권이 넘어가 실행할 다른 프로세스를 선택한다

중단된 프로세스는 signal() 을 실행할 때 다시 시작된다. 프로세스는 wakeup() 연산에 의해 재시작되어 ready queue 에 배치된다. 

 

 

Monitor

나중에 정리 예정

 

 

 

참조
Silberschatz_Operating_System_Concepts_10e_2018
광운대 운영체제 강의(안우현 교수, 2021)