[운영체제] 프로세스 동기화 3 (Semaphore, Block & Wake-up, DeadLock, Starvation)

2022.12.27 - [Operating System] - [운영체제] 프로세스 동기화 1 (Race Condition/경쟁 상태)

[운영체제] 프로세스 동기화 1 (Race Condition/경쟁 상태)

 

2023.01.04 - [Operating System] - [운영체제] 프로세스 동기화 2 (Critical Section, Race condition)

[운영체제] 프로세스 동기화 2 (Critical Section, Race condition)

---

● Semaphore (세마포어)

​세마포어는 일종의 추상 자료형이다. 세마포어 변수 S가 있다고 하면 변수 S는 정수 값을 가질 수 있으며, 세마포어라는 변수에 대해서 정의되는 오퍼레이션(연산)은 P연산과 V연산 두 가지가 있다.

세마포어를 사용하는 이유는 Lock을 걸거나 풀 때 간단하게 사용할 수 있으며, 공유 자원을 획득하고 반납하는 과정을 세마포어가 해준다.

P연산은 공유 데이터를 획득하는 과정이고 V연산은 자원을 다 사용하고 반납하는 과정이며, 세마포어의 변수는 자원의 개수를

만약 세마포어의 변수 값이 5라면 자원의 개수가 5라는 뜻이다. P연산을 한 번 해주면 그 자원을 하나 가져가서 4개가 되고 한 번 더 해주게 되면 3이 된다.

반대로 자원의 개수가 4인 상황에서 V연산을 하게 되면 5개가 된다.

​

Lock을 걸고 푸는 과정은 세마포어 변수 값이 1인 경우이다. P 연산을 하면 Lock을 거는 것이고, V 연산을 하면 Lock을 푸는 것이다.

// P(S)
while (S <= 0) do no-op; // ex) wait.
S--;

// V(S)
S++;

변수 값 S에 대해서 S가 음수(자원을 다 가져가서 없는 상태) 일 경우 while문을 돌면서 아무것도 안 하고 기다린다.

S값이 양수가 되면 (누군가 자원을 내어놓으면) S값을 1 빼고 자원을 획득하며 사용이 끝나면 S값을 증가시켜서 자원을 반납한다.

자원이 없을 때 P 연산을 하게 되면 busy waiting 문제가 생긴다.

 

Synchronization variable
semaphore mutex;

Process Pi
do {
    P(mutex); // mutex의 값이 양수면 임계 구역 접근하고, 아니면 기다린다.
    critical section
    V(mutex); // mutex의 값을 1 증가한다.
    remainder section
} while (1);

세마포어 변수 값만큼 여러 개의 프로세스가 임계 구역에 접근할 수 있다.

위 예제에서는 한 개의 프로세스만 Critical section에 접근할 수 있도록 mutex의 값이 1이라고 가정한다. Critical section 문제에 세마포어를 사용해 보자.

뮤텍스 변수를 1로 놓고 Critical section에 ​들어갈 때 P 연산을 하고 Critical section에서 빠져나올 때 V 연산을 한다. 

 

P(mutex) 연산을 수행할 때, mutex의 값이 양수가 아니면 계속 기다려야 하는데 프로세스의 CPU할당 시간이 끝날 때까지 무의미하게 CPU를 낭비한다.

이러한 현상을 busy-wait 또는 spin lock이라고 부른다. 이러한 단점을 보완하기 위해 Block & Wake-up 혹은 Sleep lock이라고 부르는 기법​이 생겨났다.

​

세마포어의 구현 방식을 busy waiting (spin Lock) 방식이 아니고 block and wake up (sleep lock) 방식으로 구현할 수 있다.

---

이전에 어떤 프로세스가 CPU를 사용하다가 I/O 같이 오래 걸리는 작업을 하러 가게 되면 그 프로세스의 상태는 Blocked가 된다고 했다. Blocked 상태가 되면 CPU를 얻을 권한 자체가 없어진다.

마찬가지로 공유 데이터에 접근하려고 할 때 다른 프로세스가 공유 데이터를 쓰고 있으면 그 프로세스가 데이터를 내어놓기 전까지는 사용하지 못한다. 그러니까 while문을 계속 돌고 있는 게 아니라 그 프로세스를 blocked 상태로 만들어 놔 잠들어 있다가​ 공유 데이터를 갖고 있던 프로세스가 공유 데이터를 내어 놓으면 그때 깨어나서 Ready Queue에 들어온다.

Ready Queue에 줄을 서서 CPU 제어권을 얻을 때까지 기다린다.

---

● Block & Wake-up

Block과 Wake-up을 다음과 같이 가정해 보자

• Block : 커널은 Block을 호출한 프로세스를 suspend 시키고, 이 프로세스의 PCB를 세마포어에 대한 Wait Queue에 넣는다.
• wake-up(P) : Blocked된 프로세스 P를 wake up 시키고, 이 프로세스의 PCB를 Ready Queue로 옮긴다.

typedef struct
{
    int value; // 세마포어 변수
    struct process *L; // 프로세스 Wait Queue
} semaphore;

 

만약 세마포어를 획득할 수 없으면 그 프로세스를 Blocked 시키게 되고, 누군가 세마포어를 쓰고 나서 반납을 하게 되면 Blocked 된 프로세스들 중 하나의 프로세스를 깨워서 wake-up 시킨다. 예를 들어, 세마포어 변수가 하나 있으면 그 자원을 누군가는 획득을 했을 것이고 획득하지 못한 프로세스는의 PCB를 세마포어 변수에다 연결시켜 준다.

​

Implementation Block/Wake-up Version of P() & V()

// P(S)
S.value--;    // 세마포어 값을 1 빼줌
if (S.value < 0)    //음수면 자원이 없다는 얘기
{
    add this process to S.L;    // 리스트에다가 프로세스를 연결 시키고 ..
    block();  // block 상태로 감
}

자원의 여분이 있으면 자원을 획득하고 자원의 여분이 없으면 Blocked 상태가 된다.

​

// V(S)
S.value++;
if (S.value <= 0)    // 자원을 내놓았는데도 불구하고 그 값이 0 이하라는 것은 누군가가 잠들어있다는 뜻
{
    remove a process P from S.L;    // 리스트에서 프로세스를 빼주고 ..
    wakeup(P);    // 깨워주기
}

자원을 다 쓰고 반납하는 과정이다. Block & Wake-up에서는 자원을 반납하고 끝나는 게 아니라 혹시 잠든 프로세스가 있다면 깨워야 하는 작업이 추가가 되어야 한다.

 

그렇다면 뭐가 더 좋을까?

Critical Section의 길이가 긴 경우, Block/Wake-up이 적당하고 Critical section의 길이가 매우 짧은 경우에는 Block/Wake-up 방식의 Overhead가 busy wait 방식의 Overhead보다 더 커질 수 있다.

일반적으로는 Block/Wake-up 방식이 더 좋다.

​

Block/Wake-up도 오버헤드가 있을 수 있다. 자원의 여분이 없을 때에는 프로세스의 상태를 Ready에서 Blocked 상태로 바꿔줘야 하고 공유 데이터의 여분이 생기면 Blocked 상태를 Ready 상태로 바꿔줘야 하기 때문에 Context Switch를 하면서 오버헤드가 발생한다.

​

---

● Two Types of Semaphores

• Counting Semaphore : 자원의 갯수가 여러개 있어서 counting 하는 경우

도메인이 0 이상인 임의의 정수값, 주로 resource counting에 사용​

• Binary Semaphore (=mutex) : 자원의 갯수가 하나인 경우​

0 또는 1 값만 가질 수 있는 semaphore, 주로 Mutual exclusion(lock/unlock)에 사용

​

---

● Dead Lock & Starvation (교착 상태 & 기아 상태)

- DeadLock

DeadLock이란 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 Event를 무한히 기다리는 현상이다.​

세마포어 S와 Q가 있는데, 어떤 일을 하기 위해 S와 Q 두 개 다 획득을 해야지 일을 할 수 있는 환경이 있다.

예를 들어, 하드 디스크 A에 있는 데이터를 하드디스크 B에다가 Copy를 하고 싶다면 자원 S와 Q를 둘 다 얻어서 Copy를 하고 그 후에 반환을 해아 한다고 가정해 보자.

해당 과정을 프로세스 0에서도 하고 프로세스 1에서도 한다.

​

프로세스 0이 CPU를 먼저 얻어서 S라는 세마포어를 먼저 획득한 다음에 CPU 제어권을 빼앗겨 제어권이 프로세스 1에게 넘어갔다고 해보자.

그리고 프로세스 1은 세마포어 Q를 획득하고 S를 획득하려고 봤더니 이미 프로세스 0이 획득해 버려서 영원히 기다려야 하는 상황이 발생한다

왜냐하면 프로세스 0이 자원 S를 내어 놓아야 하는데 프로세스 0은 자원 Q를 얻어서 다 쓰고 반환할 때 자원 S를 내놓기 때문이다.

​

이렇게 자원이 여러 개일 때 프로세스들이 서로 자원을 놓지 않고 있을 때, 조건을 영원히 충족하지 못한다. 이를 DeadLock (교착 상태)라고 한다.

상대방이 가진 것을 놓기를 기다리면서 본인이 가진 자원은 내놓지 않고 영원히 기다리는 것이다.

해결방법은 자원을 획득하는 순서를 똑같이 맞춰주면 간단하게 해결된다.

위의 시퀀스처럼 자원 Q를 획득하려면 자원 S부터 획득하도록 하면 된다.

좀 전과 같이 둘이서 하나씩 갖고 있으면서 영원히 기다리는 문제는 발생하지 않는다.

 

- ​Starvation

Indefinite Blocking. 무한히 기다리는 상황이다. DeadLock도 일종의 Starvation이라고 볼 수 있다.

근데 여기서의 Starvation은 특정 프로세스들만 공유하면서 다른 프로세스들은 공유를 안 해주는 것이다. (ex 식사하는 철학자 문제)