[OS] 12. Process Synchronization and Mutual Exclusion 5

728x90

그 유명한 세마포어(Semaphore)에 대해 알아봅시다.

Semaphore

다익스트라씨가 또 만듬...(대단하신 분,,) 가장 핵심은 이전에 고질적인 문제였던 busy waiting 문제 해결했다는 것!

음이 아닌 정수형 변수(S)를 사용하며 spinlock과 동일하게 초기화 연산, P(검사), V(증가)연산으로만 접근이 가능하다.

하지만 spinlock과 다른 점이 있다! 세마포어는 임의의 S 변수 하나에 ready queue 하나를 할당한다는 것이 큰 차이이다.

우선 세마포어는 두 가지로 구분할 수 있다.

Binary semaphore

S가 0 혹은 1의 값만 가지는 경우
상호배제(Mutual Exclusion)나 프로세스 동기화를 목적으로 사용

Counting semaphore

S가 0이상의 정수 값을 가지는 경우
Producer-consumer 문제를 해결하기 위해 사용

자 다시 세마포어로 돌아와서, 세마포어의 연산자들을 살펴보자.

초기화 연산

간단하다. S 변수에 초기 값을 부여하는 연산이다.

P( ), V( ) 연산

P는 물건을 꺼내가는 연산, V는 물건을 되돌려놓는 것과 유사하다고 이야기 했었다. 여기서도 마찬가지로 S는 물건 수를 의미한다.

P연산을 먼저 보자.

func P(S: inout Int) {
    if S > 0 {
        S -= 1
    } else {
        // ready queue(Qs)에서 대기 = 서비스를 받기 위해 대기실에서 대기하는 느낌
    }
}

대략 이런 느낌이다.

S를 우선 검사(0보다 큰지)하고 조건을 충족한다면 하나를 꺼낸 후 작업을 수행하고, 만약 조건에 충족하지 않는다면 ready queue에서 기다리게 된다. 이전에 spinlock에서는 조건을 충족하지 못한다면 while문 안에서 계속 뺑뺑 돌았지만, 세마포어에서는 그렇지 않고 ready queue에 들어가있게 된다. 이에 뺑뺑 돌지않고 가만히 기다리게 된다.

이제 일을 마치고 나갈 때 V 연산을 수행하게 된다.

func V(S: inout Int) {
    if !Qs.isEmpty {
        // ready queue 중에 하나 아무나 깨우기
    } else {
        S += 1
    }    
}

Qs가 비어있지 않다는 것은 아직 순서를 기다리는 작업들이 있다는 것을 의미한다. 이에 Qs가 비어있지 않고 기다리는 작업이 있다면 그 들 중 아무 작업이나 선택하여 수행을 하게 된다. 그리고 만약 Qs가 비어있는 상황이라면 물건(S)를 반납하고 나가면 된다.

차이점!	Spinlock	Semaphore
(조건 미충족시(S가 없다면)) P연산	while문 안에서 뺑뺑 돈다	ready queue에서 대기
V연산	-	끝나면 와서 ready queue내 작업 깨워줌

Semaphore Solution

이러한 세마포어(semaphore)를 통해 다양한 동기화 문제들을 해결할 수 있다.

상호배제 문제 (Mutual exclusion)
프로세스 동기화 문제 (process syncronization problem)
생산자-소비자 문제 (producer-consumer problem)
Reader-writer 문제
Dining philosopher problem

이러한 문제들을 semaphore가 어떻게 해결하는지 살펴보자.

상호배제 문제 (Mutual exclusion)

spinlock과 마찬가지로 P와 V를 넣어줌으로써 바로 해결된다! semaphore에서 사용하는 ready queue가 busy waiting 문제를 해결해준다고 볼 수 있다.

프로세스 동기화 문제 (process syncronization problem)

프로세스들은 병행적이고, 비동기적으로 수행되기 때문에 프로세스들의 실행 순서를 맞추는 것은 중요한 일이다.

말풍선과 같이 "Pi는 Pj가 Lj 지점을 통과할 때까지 Li 지점에서 대기해야한다"는 것을 세마포어로 구현하려면 어떻게 해야할까?

sync를 0으로 세팅해준다 = 현재 물건이 없다는 것 = 현재 Pj가 들고 있다.
Pi는 Pj가 Lj를 지나간 이후 수행되어야 하기 때문에 P연산을 통해 ready queue에서 대기하도록 한다.
Pj는 V연산을 통해 Lj를 빠져나오면서 현재 ready queue에 대기중인 작업이 있는지 확인한다.
현재는 Pi가 대기하고 있기에 sync를 +1 하지 않고 Pi를 깨워 작업을 수행한다.

세마포어를 활용하여 위와 같은 순서로 프로세스 동기화 문제를 해결해낼 수 있다.

생산자-소비자 문제 (producer-consumer problem)

생산자는 말 그대로 무언가를 생성해내는 역할을 한다. 소비자도 당연히 무언가를 가져다가 소비하는 역할을 한다.

생산자는 위처럼 무언가를 생성하여 buffer라고 불리는 곳에 저장해두면 소비자는 필요할 때 가져다가 사용하는 그런 방식이 된다.

그런데 생산자가 생산하여 무언가를 두는 동안에 소비자가 그걸 가져가면 안된다. 또한 A 생산자가 생산하는 도중에 B 생산자가 생산하여 물건을 두게 되면 문제가 발생할 수 있다. 그렇기에 이러한 일련의 과정 속에 "동기화"가 필요하게 된다.

Single-buffer

우선 buffer의 크기가 1인 경우를 먼저 살펴보자.

물건을 놓으려고 할 때 소비하면 안되고, 소비하려할 때 생산하면 안된다. 즉 CS영역처럼 한 번에 한 명만 접근해야한다.

세마포어 변수가 두 개 있는 것을 볼 수 있다.

consumed : 소비되었는지 확인
produced : 생산되었는지 확인

Pi(생산자)를 보면 소비되었는지 체크하기 위해 P(consumed) 연산을 한다. 현재 1이라는 것은 소비되었다는 것이기에 이를 0으로 바꿔주고 이제 생산할 것이기 때문에 V(produced)를 통해 produced 세마포어를 1 올려준다.

Pj(소비자)는 반대로 생각하면된다. 생산되었는지를 확인해주고, 아니라면 대기해주면 된다. 생산되어 있다면 소비하고 consumed 세마포어를 하나 올려주면 된다.

N-buffer

buffer의 크기가 N인 경우 어떻게 해결할 수 있을까?

마치 원형 컨베이어 벨트처럼 순차적으로 무언가 수행되는 것 처럼 보인다. 대략 살펴보면 in을 통해 생산자는 버퍼로 보내고, out을 통해 소비자는 버퍼에서 받고 있음을 알 수 있다.

우선 Pi나 Pj를 보면 모두 P,V 연산으로 묶여있음을 알 수 있다. 이를 통해 한 번에 한 명만 일 할 수 있도록 한 것을 알 수 있다.

위와 같이 묶여있음을 알았기에 사실 이제 mutexP, mutexC는 볼 필요가 없어진다. 그러니 nrfull과 nrempty만 보자.

nrfull : 채워진 buffer의 수
nrempty : 비어있는 buffer의 크기

두 변수의 합은 항상 N개로 고정된다.

보면, 생산자가 생산하러 왔을 때 공간이 있는지 우선 확인해야한다. 이를 P(nrempty)를 통해 확인한다. 만약 공간이 없다면 생길 때까지 대기하고, 공간이 생기면 들어가게 된다. 즉 공간이 0보다 크다면 들어가고, 아니면 대기하게 된다. 그리고 물건을 두고(buffer[in] <- M) 다음에 물건을 어디에 둬야하는지 위치를 갱신(in <- (in+1) mod N)해준다. 물건을 생산했으니 V(nrfull)을 통해 물건 수를 하나 늘려주면 된다.

정리해보면 생산자는 아래와 같은 프로세스로 일하게 된다.

공간 확인
물건을 두고(생산)
다음 생산 위치로 조정하고
물건 수를 증가

반대로 소비자는 소비를 하러 왔을 때, 물건이 있는지를 확인해줘야 한다. 즉 P(nrfull)을 통해 물건이 있는지 확인하며, 없을 경우 마찬가지롤 대기하며, 있을 때 소비할 수 있게 된다. 이후 물건을 소비(m <- buffer[out])하고 그 다음 꺼낼 위치를 갱신(out <- (out+1) mod N)해준다. 이후 물건을 소비했기 때문에 V(nrempty)를 통해 공간을 하나 늘려준다(= 물건을 소비했으니)

소비자 프로세스를 정리해보자.

물건 확인
물건을 빼오고(소비)
다음 소비 위치로 조정하고
공간 크기를 증가

Reader-writer 문제

Reader : 데이터 읽기 연산만 수행
Writer : 데이터 갱신 연산만 수행

생산자-소비자와 유사해 보이나 조금 다른 부분이 있다. 생산자-소비자 문제에서는 한 명씩 소비하도록 했었지만, reader-writer에서 reader는 여러 명이 동시에 read(=소비)해도 된다. 어떤 아티클에 대해서 여러 명이 동시에 읽어도 무방한 것 처럼 말이다! 반면에 글을 쓰는 것을 여러 명이 한 번에 하게 된다면 내용이 엉망이 될 수 있다. 그렇기에 writer의 경우는 한 명씩 접근해야 한다. 이와 같이 데이터의 무결성을 보장해줘야 하며 정리해보면 다음과 같다.

Reader : 동시에 데이터 접근 가능
Writer : 동시에 데이터 접근 시 상호배제(동기화) 필요

그리고 누군가 읽을 때는 수정할 수 없고(reader preference solution), 누군가 수정하고 있을 때는 읽지 못하도록(writer preference solution) 해야한다. 즉 상황에 따라 reader/writer에 대해 우선권이 주어지는 것이다.

reader preference solution

읽고 있다면, 쓰는 사람은 계속 기다려줘야 한다.

사전 작업과 사후 작업은 모두 CS영역이다.

처음 P ~ V는 읽으러 들어갈 때를 의미한다. (사전작업)

우선 nreaders가 0인지 체크해주는데, 이는 사전 작업을 하기 위함이다. 아직 아무도 읽지 않고 있다면 P(wmutex)를 통해 쓰기를 멈추게 하고 nreaders를 증가시킨다. 만약 nreaders가 0보다 컸다면 누군가 이미 사전 작업을 했다는 것이기에 뛰어넘어도 된다. 그 다음에 읽는 연산은 동시에 해도 무방하기에 P~V 사이에 두지 않는다.

이후 P~V 쌍이 하나 더 등장하는 데 이는 사후 작업에 해당한다. 마찬가지로 한 명만 수행하게 된다. 우선 내가 나가니 독자의 수를 하나 줄여주고 그 이후 nreaders의 수를 체크한다. 만약 아직 남아있다면 누군가 읽고 있다는 것이기 때문에 그대로 두고, 그 수가 0이라면 이제 V(wmutex)를 통해 쓰기를 허용해준다.

writer preference의 경우도 마찬가지로 쓸 때는 읽기를 멈출 수 있게 P(rmutex)를 통해 잠궈주고, 한 명만이 쓸 수 있기 때문에 Perform write operations를 CS영역 안으로 넣어주면 될 듯 싶다. 그리고 다 썼으면 다음에 쓸 사람이 있는지 체크해주고 없다면 이제 읽기를 허용해주는 그런 순서가 될 것 같다.

마지막으로 세마포어의 특징을 정리해보자면 다음과 같다.

장점 : Busy waiting이 없다. (기다려야 하는 프로세스는 block(asleep)상태가 된다)
문제점 : Semaphore queue에 대한 wake-up 순서는 비결정적이다. (starvation 발생 가능)

세마포어의 문제점을 해결한 Eventcount와 Sequencer에 대해서는 다음 강의에서 알아보자.

Ref : https://www.youtube.com/watch?v=CitsUz-Dx7A&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=16&t=24s