OS [OS]Process Synchronization(Problem, DeadLock and Starvation, Semaphore)

이 글은 KOCW에 공개되어있는 '반효경 교수님'의 운영체제 강의 및 강의 교재 Operation System Concepts(a.k.a 공룡책🦕)의 내용을 기반으로 작성했습니다.

이번 챕터에서는 Process Synchronization에 관해 정리해보겠습니다
오류가 있다면 댓글로 정정 부탁드립니다

---

Process Synchronization Problem

• Process Synchronization variable : 수행의 동기화(synchronize)를 위해 몇몇의 변수를 공유할 수 있다
• 공유 데이터(shared data)의 동시 접근(concurrent access)는 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다(여러 프로세스가 동시에 데이터를 읽은 후 수정한다면, 누가 먼저 읽었느냐에 따라 문제가 발생할 수 있다)
• 이러한 문제는 CPU-Memory, 컴퓨터 내부-IO 장치, 프로세스-주소공간 등 여러 곳에서 일어날 수 있다
• 일관성 유지(consistency)를 위해 협력 프로세스(cooperating process)간의 실행 순서(orderly execution)을 정해주는 메커니즘이 필요하다

| Race Condition

여러 프로세스들이 동시에 공유 데이터에 접근하는 상황

• 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
• race condition을 막기 위해서는 concurrent process는 동기화 되어야 한다

| OS에서 Race Condition이 발생 할 수 있는 상황

1. kernel 수행 중 인터럽트 발생

1) 메모리에 있는 값(ex Count)을 CPU 내의 register로 읽고 그 값에 변화를 주고 있는 상태(Count + 1을 명령함)에서 Interrupt가 발생
2) 해당 작업을 멈추고 Interrupt 처리 루틴으로 갔을 때 Interrupt Handler가 Count 값에 변화를 주라고 명령함(Count - 1)
3) 이후 중단됐던 작업을 다시 수행할 때 Context상 2번 작업에 대해 알 수 없기 때문에, 1번의 값 변화만 적용이 된다(Count는 +1 만 됨)

• 이러한 상황을 발생시키지 않기 위해 중요한 값을 수정하는 상황에서는 중간에 Interrupt가 들어오더라도, 그 작업이 끝나 값을 저장할 때까지는 Interrupt를 받지 않도록 한다

2. Process가 System Call 을 해 Kernel mode로 수행 중인데, Context Switch가 일어나는 경우

1) 각 Process가 User Mode -> Kernel Mode -> ...-> 와 같이 실행이 되며 User Mode, Kernel Mode 모두 실행 시간에 제한을 둔다(Time interrupt 발생)
2) Process A가 Kernel Mode를 수행하며, 메모리에 있는 값(Count)을 조작(Count + 1)하는 와중에 Time Interrupt 당함
3) Process B가 Kernel Mode를 수행하며 메모리에 있는 값(Count)을 조작함(Count + 1)
4) 하지만 Count 값은 2, 3번의 값이 모두 적용되지 않는 문제가 발생함(Count +2가 되지 않은 상태)

• 이러한 상황을 발생시키지 않기 위해 Process가 Kernel 모드에 있을 때는 CPU 할당 시간이 끝나도 CPU를 뺏기지 않도록 한다

3. Multiprocessor에서 Shared Memory 내의 Kernel data

• Memory Address Space를 공유하는 CPU Process가 여러개 있는 경우(공유 메모리 사용) 어떤 하나의 주체가 데이터를 수정하는 동안 다른 주체가 데이터를 또 수정한다면, 우리가 원하지 않는 데이터를 얻을 수 있다
• 이러한 상황을 발생시키지 않기 위해 한번에 하나의 CPU만이 커널에 들어갈 수 있도록 하거나, 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 Lock/Unlock을 하도록 한다

| Critical-Section Problem

critical-section은 공유 데이터에 접근하고자 하는 코드를 말한다

• n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우 각 프로세스의 code segment에는 code critical section이 존재

| 프로그램적 해결법

모든 프로세스의 수행 속도는 0보다 크고, 프로세스들 간의 상대적인 수행 속도는 고려하지 않는다고 가정한다

1. Mutual Exclusion(상호 배제)

• 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical-section에 들어갈 수 없어야 한다

2. Progress(진행)

• 어떤 프로세스도 critical section에 있지 않을 때 critical section에 들어가고자 하는 프로세스가 있다면 들어가게 해줘야 한다
• 코드를 잘못 짜면 들어가고 싶은 프로세스가 두 개일 경우 아무도 들어가지 못하는 문제가 발생한다

3. Bounded Waiting(유한 대기)

• 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가려는 횟수에 제한이 있어야 한다
• 특정 프로세스 입장에서 critical section에 못 들어가고, starvation이 발생하면 안된다
• 만약 세 개의 프로세스가 들어가고자 할 때 두 개의 프로세스만 계속 진입하고 하나는 진입하지 못한다면 위와 같은 상황이 발생한다

알고리즘 구현

turn, flag를 이용해 구현을 할 수 있다

Algorithm 1(turn 이용)

Process 0가 아래 코드를 진행하는 상황이고, Process i는 turn == i 여야 critical section에 진입할 수 있다

do{
while(turn != 0);
critical section
turn = 1;
remainder section
}while(1);

• Mutual Exclusion은 만족하나, Progress를 만족하지 않는다
• Swap-turn : Process간 반드시 교대가 이루어져야 진행이 된다(다른 Process가 turn 값을 바꿔줘야 다른 프로세스가 진입할 수 있다)
• 특정 프로세스가 더 빈번하게 critical section에 들어가야 할 경우 Swap-turn 을 하는 것이 비효율적일 수 있다

Algorithm 2 (flag 이용)

do{
flag[i] = true;
while(flag[i]);
critical section
flag[i] = false;
remainder section 
}while(1);

• Mutual Exclusion은 만족하나, Progress를 만족하지 않는다
• 결국 모든 값이 false가 되기 때문에 끊임없이 양보를 하는 상황이 발생한다

Algorithm 3(turn과 flag 모두 이용, Peterson's Algorithm)

Process 0가 아래 코드를 진행하는 상황이고, Process i는 turn == i 여야 critical section에 진입할 수 있다

do{
flag[i] = true;
turn = j // j는 다른 process 번호이다 
while(flag[j] && turn == j);
critical section 
flag[i] = false;
remainder section 
}while(1);

• Mutual Execution, Process, Bounded Waiting 모두를 만족한다
• Process i 가 critical section으로 들어가려고 할 때 flag=true로 바꾸고, turn 을 상대방 turn으로 바꾸어놓는다
• critical section 들어가기 전 상대방이 깃발을 들고 있고, 이번이 상대방 차례인 경우에만 기다리게 되고 아니면 critical section으로 진입한다
• Busy Waiting(spin lock) 발생: while문을 돌면서 lock을 걸어서 상대방이 들어가지 못하게 하기 때문에 기다리면서 쓸데없이 CPU 시간을 할애할 수 있다

Semaphores

멀티프로그래밍 환경에서 공유 자원에 접근을 제한하기 위해 고안된 두개의 원자적 함수로 조작되는 정수 변수

• 앞선 방식들을 모두 추상화 시킨 것이 Semaphore이다
• 다음의 원자적(atomic) 함수 두개에 의해 접근이 가능하다( P(S), V(S) )
• 락을 걸고 푸는 작업, 공유 자원 획득/반납을 간결하게 해준다
• 세마포어 변수는 정수값을 가질 수 있으며, 자원의 갯수를 의미한다
• 세마포어 구현을 위해서는 자발적 협력이 필요하다
• 구현과 정확성 입증이 어렵고, 한 번 실수해서 코딩하면 모든 시스템에 치명적인 영향을 줄 수 있다

P(S)

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

• 세마포어 공유 데이터를 획득하는 함수이다
• 변수가 하나인 경우, P연산을 하면 락을 거는 것을 의미한다

V(S)

S++;

• 세마포어 공유 데이터를 반납하는 함수이다
• 변수가 하나인 경우, V연산을 하면 락을 푸는 것을 의미한다

세마포어 종류는 다음과 같다

1) Counting semaphore

• 도메인이 0이상인 임의의 점수값, resource counting에 주로 사용된다

2) Binary semaphore(=mutex)

• 0 또는 1만 가질 수 있고(Binary) 주로 mutual exclusoin(lock/unlock)에 사용된다

| Critical Section

process(n)이 진입하는 상황이다

| Busy waiting 방식

semaphore mutex;

do {
P(mutex); // 양수이면 진입, 아니라면 wait
critical section 
V(mutex); // semaphore 변수 증가
remainder section;
}while(1);

• 프로그래머는 세마포어가 지원된다면 P와 V연산만 작업하면 되기 때문에 간편하다
• 위 코드에서 spin lock(busy waiting) 문제가 발생한다

| Block/Wakeup Implementation

공유자원을 얻지 못하면 쓸데없이 CPU 시간을 낭비하지 않고 잠들도록 하는 것

• 보통은 block/wakeup을 쓰는 것이 효율적이나, 이 방식도 overhead가 발생하게 된다
• critical section의 길이가 짧으면 busy waiting을 사용해도 overhead가 덜 발생할 수 있다

typedef struct{
int value; //세마포어 
struct process *L; //process waite queue
}semaphore;

• IO 작업을 하면 blocked 상태가 되고, CPU를 얻게 되는데 공유데이터도 마찬가지로 자원을 얻을 수 없게 되면 blocked 시키고 자원을 얻을 수 있게 되면 wakeup 시키게 된다

block

• 커널은 block을 호출한 프로세스를 suspend 시킴
• 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음

wakeup(P)

• block 된 프로세스(P)를 wakeup 시킴
• 이 프로세스의 PCB를 ready queue로 옮김

P(S)

S.value--;
if (S.value <0){
add this process to S.L; //자원 waiting하는 queue에 PCB 연결 
block(); //재운다 
}

• 여분이 있다면 자원을 획득하게 하고 아니면 잠들도록 한다
• 이 때 자원을 waiting하는 List에 프로세스를 연결시키고 프로세스를 blocked 시킨다

V(S)

S.value++;
if (S.value <=0){ //S.value <= 0이면 자원을 기다리는 상태(자원의 갯수는 아님)
remove a process P from S.L; //자원 waiting queue에서 지움
wakeup(P); //자고 있는 프로세스를 깨움 
}

• 자원을 반납하게 된다
• 자원을 반납했을 때도 S가 0 이하라는 것은 누군가 자원을 기다리면서 잠들어 있다는 뜻(S.value가 자원의 갯수를 뜻하는 것은 아님)
• 잠들어 있는 프로세스를 wait List에서 빼서 자원을 주고 기다려야 함
  
  

Deadlock and Starvation

| Deadlock

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

• 어떤 일을 하기 위해 각 프로세스(P0, P1)가 세마포어 S와 Q를 모두 획득해야 하는데 P0, P1이 각각 S, Q를 나누어 가져가면 두 프로세스 모두 영원히 기다릴 수 있다

| Starvation(Indefinite blocking)

특정 프로세스가 자원을 얻지 못하고 영원히 기다리는 상황

• Deadlock도 starvation의 일종이라 할 수 있다

| Bounded-Buffer Problem

Buffer의 갯수(크기)가 제한되어 있기 때문에 생산자 - 소비자 문제가 발생할 수 있다

• Empty Buffer : 생산자는 Empty Buffer을 찾아 데이터를 집어넣는다(Full Buffer++, Empty Buffer--)
• Full Buffer : 소비자는 Full Buffer을 찾아 데이터를 꺼낸다(Empty Buffer++, Full Buffer--)
• Empty Buffer가 없으면 생산자가 대기를 하게 되고, Full Buffer이 없다면 소비자가 대기를 하게 된다

문제점

1) 생산자 두개가 하나의 Empty Buffer 에 동시 도착
2) 소비자 두개가 하나의 Full Buffer에 동시 도착

• 1, 2를 해결하기 위해 공유 버퍼에 lock을 걸어 다른 프로세스의 접근을 막은 후 버퍼에 데이터를 넣거나 빼도록 한다

3) Buffer의 크기가 제한되어 있기 때문에 생기는 문제

• 버퍼가 다 차면 생산자는 계속해서 기다려야 하고, 버퍼가 다 비면 소비자는 계속해서 기다려야 하는 문제가 생긴다

구현

• Mutual Execlusion을 충족하기 위해 Binary Semaphore이 필요하다(Shared Data의 Mutual Execlusion)
• Resource Count를 하기 위해 Integer Semaphore이 필요하다(남은 Full/Empty Buffer 수 표시)
• Producer과 Consumer의 흐름이 반대로 되는 것을 확인할 수 있다

Producer

do{
produce an item in x 

P(empty); //empty : 비어있는 버퍼의 변수 
P(mutex); // mutex : lock을 걸기 위한 변수 
...
add x to buffer 
...
V(mutex); // 값을 집어넣은 후 lock을 풀어준다 
V(full); //empty -> full이 된 모습

}while(1)

Consumer

do{
P(full); //full : 차있는 버퍼의 변수 
P(mutex); //mutex : lock을 걸기 위한 변수
...
remove an item from buffer to y  
...
V(mutex); //값을 뺀 후 lock을 풀어준다 
V(empty); //full -> empty가 된 모습
...
consume the item in y 
...
}while(1);

| Readers-Writers Problem

한 process가 DB에 write 중일 때 다른 process가 접근하면 안된다(read는 여러 process가 동시에 해도 됨)

• Writer가 DB의 허가를 얻지 못했다면, Reader은 DB에 접근해도 되며, Writer은 대기 중인 Reader이 없을 때 DB 접근이 허용된다
• Writer가 DB 접근 중이라면 Reader의 접근은 금지되며, Writer가 DB를 빠져나가면 Reader의 접근이 허용된다
• Writer가 지나치게 오래 기다려서 starvation이 일어날 수 있기 때문에 Queue를 두어서 Writer을 접근하게 하거나 신호등과 같은 것을 구현해 해결할 수 있다

구현

• 공유 데이터로는 readCount(0으로 초기화), db가 있다
• readCount도 공유 변수이기 때문에 lock이 필요하고 이를 위해 mutex라는 세마포어가 필요하다

Writer

semaphore mutex = 1, db = 1;

P(db);
...
writing DB is performed
...
V(db);

Reader

int readCount = 0; //shared Data

P(mutex);
readCount++;
if (readCount == 1) P(db); //writer blocked 되고 readers는 뒤의 과정을 진행할 수 있다  
V(mutex);
...
reading DB is performed
...
P(mutex);
readCount--;
if(readCount == 0) V(db); //마지막으로 읽고 빠져나가면 read count는 0일 것이고 writer 접근이 가능하도록 lock을 풀어줘야한다  
V(mutex); 

| Dining-Philosophers Problem

젓가락을 한짝씩만 준 아주 놀라운 상황

문제

• 여러개의 Process가 있고, 양쪽의 자원을 모두 점유해야 Process 진행이 가능하다
• 한 번 잡은 자원은 배가 부를 때 까지 놓지 않게 된다
• 왼쪽의 자원을 잡았는데 오른쪽의 자원을 옆의 사람이 점유해 얻을 수 없고 그 상황이 지속될 때 deadlock의 가능성이 있다(누구도 자원을 양보하지 않아 진행되는 프로세스가 없다)

해결

• 철학자를 짝수개로 놓으면 해결될 수 있다
• 두개의 resource(젓가락)를 모두 점유할 수 있을 때만 resource를 점유하도록 하면 해결할 수 있다
• 짝수(홀수) process는 왼쪽(오른쪽)의 resource부터 집도록 설계하면 해결할 수 있다

구현
Process(철학자)
Process i의 실행 코드이다

do{
pickup(i); //i는 process 번호
eat();
putdown(i);
think();
}while(1);
void putdown(int i){
P(mutex);
state[i] = thinking;
test((i+4) % 5);
test((i+1) % 5);
V(mutex);
}

void pickup(int i){
P(mutex);
state[i] = hungry;
test(i);
V(mutex);
P(self[i]);
}

//오른쪽, 왼쪽 젓가락을 점유할 수 있고 현재 상태가 hungry이면 젓가락을 점유할 수 있도록 한다 
void test(int i){
if (state[(i+4)%5] != eating && state[i] == hungry && state[(i+1)%5] != eating){
state[i] = eating;
V(self[i]);
}
}

• state[i]는 철학자의 상태로 enum {thinking, hungry, eating} 으로 이루어져있다
• test : 오른쪽, 왼쪽 젓가락을 점유할 수 있고 현재 상태가 hungry이면 젓가락을 점유할 수 있도록 한다