5. Process Synchronization (1)

Process Synchronization (프로세스 동기화)

여러 프로세스들 또는 스레드들이 동시에 동작할 때, 그들이 공유하는 데이터에 대해서 안전하게 접근할 수 있도록 하는 것

 

프로세스 동기화가 왜 필요할까?

만약 공유하는 데이터가 있더라도 여러 프로세스들이 그 데이터에 대해 순차적으로 접근하면 문제가 되지 않지만, 동시에 데이터에 접근하여 값을 바꾸려고 하면 문제가 발생한다.

 

Race Condition

여러 프로세스가 동시에 접근해서 값을 바꾸려고하는 상황

=> 정상적인 산술의 결과가 아닌 제일 마지막에 쓴 값으로 값이 결정되어 버리는 문제가 발생한다.

=> 의도치 않게 최종적인 데이터의 값이 잘못된 값으로 결정

 

Q. 그렇다면 하나의 프로세스는 Write를 하려고 하고, 다른 하나는 Read만 한다면 동기화 문제가 발생할까?

OS의 관점에서 답은 "아니다". 하나의 프로세스만 Write를 하는 경우에는 잘못된 값이 쓰이는 경우가 발생하지 않는다. 그리고 OS에는 Read할 때는 항상 최신값을 Read한다 라는 원칙이 있는데, Read후에 값이 바뀐다고 해도 Read 할 당시에는 해당 값이 최신값이었으니까 문제가 없다.

그런데 문제가 생기는 경우가 있다. 데이터의 크기가 매우 커서, Write하는데 시간이 걸리는 경우, 전체 중 일부 비트에만 값을 쓴 와중에 Read를 한다면 깨진 값을 읽게 된다. 이때는 문제가 발생.

=> 결국, Write하고 있을 때는 Read를 하지 않는 게 맞음.

 

프로세스들이 서로가 서로의 상황을 알고 그에 맞게 잘 판단해서 적절하게 움직일 때 동기화되어 움직인다고 한다.

=> 동기화는 서로가 연관이 있을 때만 필요하다. 즉, Race Condition이 발생하는 사이에만 필요하다.

 

Race Condition에 의해 발생할 수 있는 문제 상황을 보자

X의 값을 1 증가시키는 Operation과 1 감소시키는 Operation을 동시에 수행했는데, 최종적인 결과는 기존 X의 값인 2에서 1을 감소시킨 1이 저장되었다. 그러나 산술적으로 정상적인 값은 2가 저장되어야 한다. 

같은 데이터에 대한 두 Operation이 동시에 수행되면서 문제가 발생한 것이다.

 

이러한 문제를 해결하기 전에, 먼저 문제를 정형화 해야 한다.

 

Critical Section Problem

n개의 프로세스가 공유하는 데이터에 대해 경쟁적으로 접근하는 상황이 있을 때, 각 프로세스가 공유된 데이터에 접근하는 코드가 있을 것이다. 그 코드 부분을 그 프로세스의 critical section이라고 부른다.

즉, 각 프로세스는 critical section을 수행할 때 공유된 데이터에 접근해서 값을 바꿀 것이다.

어떤 프로세스가 자신의 critical section을 수행 중이면 다른 어떤 프로세스도 자신의 critical section을 수행하지 못하도록 막는 것이 Problem이다.

=> 즉, 2개 이상의 프로세스가 동시에 자신의 critical section을 수행하는 일이 있어서는 안 된다.

=> Solution은 이것을 막는 방법을 제시하는 것

 

Requirements for the Solution

Critical Section Problem의 해결책으로 제시될 Solution이 갖춰야 할 조건들이다.

Mutual Exclusion

: 상호 배타적으로 critical section을 수행하도록 하는 것.
한 프로세스가 critical section을 수행 중이면 다른 프로세스는 자신의 critical section을 수행하지 못하도록 할 수 있어야 한다.

그냥 단순히 못 들어가게 막는 것은 쉽다. 그런데 너무 과도하게 막으면 성능이 떨어질 수 있다.

들어가지 못하게 막되, 들어가도 되는 상황에는 들어갈 수 있게 해야 throughput을 유지할 수 있다.

올바른 해결책은 막기는 하지만 성능이 떨어지는 것은 허용하지 말아야 한다.

=> 이걸 위해서 Progress와 Bounded Waiting이 필요

Progress

현재 critical section을 수행하고 있는 프로세스가 하나도 없다면, 누군가는 들어가도 된다.
그리고 그 상황에서 누군가가 critical section으로 들어가고자 하면 그 놈은 반드시 들어갈 수 있어야 한다.
너무 과도하게 막아서, 아무도 critical section을 수행하지 않고 있는데도 critical section에 들어가지 못하는 상황은 발생하지 않아야 한다.

Bounded Waiting

이미 다른 프로세스가 critical section에 들어가 있다면 기다려야 한다. 그리고 그 프로세스가 critical section 수행을 마치면 내가 들어가야 하는데, 만약 그 사이에 다른 프로세스가 먼저 들어가 버리면 또 기다려야 한다.
이런 식으로 한정없이 기다려야 하는 상황을 막아야 한다. 
즉, 어떤 프로세스가 들어가고자 할 때 언젠가는 들어갈 수 있도록 기다리는 시간의 Bound가 제공되어야 한다.

=> 지난 시간에 배운 Starvation과 비슷한 느낌.

 

이제 Mutual Exclusion, Progress, Bounded Waiting을 만족시키는 Solution이 될 수 있는 알고리즘을 생각해보자.

생각하기 쉽도록 단 2개의 프로세스만 있다고 가정한다.

critical section에 무작정 들어가 버리면 안 된다. 누군가 critical section을 수행 중인지 확인을 하고 들어가야 한다.

그 확인을 하는 부분이 entry section.
그리고 들어갈 수 있는 조건이 충족되어 들어갔다고 치자. 그 일을 다 끝나고 빠져나올 때, 그냥 빠져나오면 안 된다. 내가 들어있어서 못 들어오고 있는 애들이 있을 수 있기 때문
그래서 내가 빠져 나왔으니까 이제 들어가도 돼 라고 알려주는 부분이 exit section.

그래서 기본적으로 critical section problem을 해결하는 Solution들은 critical section 앞뒤로 entry section과 exit section을 반드시 가져야 한다.

이 entry section과 exit section에 어떤 내용이 들어갈지는 알고리즘에 따라 다르다.

 

첫 번째 알고리즘을 보자. turn이라는 공유 변수가 있고, turn == i 일 때 i 번 프로세스가 critical section에 들어갈 수 있다.

while문을 통해 자신의 turn이 아니면 계속 루프를 돌며 기다린다.

turn의 초기값은 0이기 때문에 처음엔 0번 프로세스가 들어갈 수 있다. 그리고 critical section을 마친 후 빠져나오면서 turn을 1로 바꾼다.

그러면 다시 돌아갔을 때는 turn이 1이기 때문에 0번 프로세스는 while문에 걸려서 기다리게 된다.

사진엔 나와있지 않지만, Process 1의 코드는 while(turn != 1) 로 자신의 턴을 기다리다가 critical section을 끝내고 빠져나올 땐 turn을 0으로 바꿀 것이다.

 

이렇게 P0와 P1은 서로 한 번씩 번갈아가면서 critical section에 들어갈 수 있다. 한 번씩 돌아가면서 들어간다고 해서  Swap-turn이라고 한다.

최대 하나의 프로세스만 critical section에 들어갈 수 있으므로 Mutual exclusion의 조건은 만족하지만 Progress는 만족하지 못한다.

왜?

만약, 0번 프로세스가 critical section을 수행하고 turn을 1로 바꾼 후 빠져나왔다고 하자. 그럼 0번 프로세스는 1번 프로세스가 turn을 0으로 바꿔주기 전까지는 계속 while문을 돌면서 기다려야 한다.

그런데 이때 만약 P1은 critical section과 전혀 관련 없는 부분을 수행하고 있어서 critical section에 들어가는 시도조차 하지 않고 있다면? 현재 아무도 critical section에 들어가지 않았으므로 P0는 들어갈 수 있어야 하는데 들어가지 못 하는 상황이 발생한다.

 

Algorithm 1의 문제는 상대방이 critical section에 들어가고자 하는 의지가 없는데도 들어가지 못하고 기다려야 하는 문제가 발생한다는 것이었다.

=> 여기서 우리는 상대방이 critical section에 들어가려는 의지가 있는지 파악하는 것이 중요하다는 것을 알 수 있다.

그래서 두 번째 알고리즘에서는 상대방의 의지를 파악하기 위해 flag라는 공유 변수를 만들었다.

flag[i] == true라는 것은 i번 프로세스가 critical section에 들어가려는 의지가 있다는 뜻이다.

 

들어가기 전에 나의 flag를 true로 바꾸고 상대방의 flag를 확인한다.
상대방의 flag가 false가 되면 while문을 빠져나와서 critical section으로 진입하는 구조
=> 이렇게 하면 Swap-turn 현상이 발생하지 않는다.

상대방이 들어갈 의지가 없으면, 연속해서 계속 들어갈 수 있으므로 Algorithm 1에서의 문제가 해결되었다.

그리고 상대가 들어가고자 하면 나는 while문을 돌면서 기다리니까 Mutual exclusion도 만족한다.

그러나 여전히 Progress 조건을 만족시키지 못한다.

왜?

Pi와 Pj 둘 다 들어가겠다고 flag를 true로 바꾸면 둘이 동시에 while문을 돌게 된다.
=> critical section엔 아무도 안 들어갔는데, 서로 양보하느라 아무도 들어가지 않게 된다.

=> 따라서 Algorithm 2도 Solution이 되지 못한다.

Algorithm 2는 여러 프로세스가 동시에 들어가고자 할 때, 너가 들어가! 라고 통제해주는 애가 없는 것이 문제.

그런데 이런 역할을 하는 애가 Algorithm 1엔 있었다. 바로 turn이다. turn이 명확하게 이번에 들어갈 프로세스를 지정하는 역할을 했다.

 

그래서 1번과 2번 Algorithm을 섞은 것이 Peterson's Algorithm이라 불리는 세 번째 알고리즘이다.

flag[i] = true로 변경해서 들어가겠다는 의지를 밝힌다. 그리고 turn = j로 설정해서 상대에게 턴을 먼저 양보한다.

while(flag[j] and turn == j)를 통해 턴은 이미 상대로 밀어줬으니, 상대가 들어갈 의지가 있다면 루프를 돌며 기다린다.

두 프로세스가 동시에 turn을 서로에게 밀어줄 수도 있지만, 아무튼 최종적으로는 한 프로세스가 turn을 가질테니 서로 양보하느라 둘 다 critical section에 들어가지 못하고 루프를 도는 상황은 발생하지 않는다.

=> 여기서 turn을 밀어줬지만 상대가 의지가 없으면 flag[j] == false 일테니 while 루프를 탈출하게 되므로 Swap-turn이 발생하지 않는다.

그리고 상대방이 critical section을 끝내고 자신의 flag를 false로 바꾸는 순간 while문을 탈출하게 된다.

 

이렇게 하면 Mutual Exclusion도 지키고, Progress도 만족하게 되므로 Solution이 된다.

그러나 CPU를 쓰면서 while loop를 돌게 된다는 단점이 있다.

=> 시스템에서 무의미하게 CPU를 쓰는 것은 좋지 않다고 했다.

 

피터슨의 알고리즘을 사용하는 것 외에도 Lock을 사용해서 critical section problem을 해결할 수도 있다.

critical section에 들어가기 전 프로세스는 lock을 잡으려는 시도를 한다. lock을 잡으면 critical section에 들어가게 되고 lock을 잡지 못하면 들어가지 못하고 기다려야 한다.

그리고 critical section에 들어간 프로세스는 빠져나올 때 lock을 반납해서 다른 프로세스가 lock을 잡아서 들어올 수 있도록 해준다.

오직 하나의 프로세스만 lock을 잡을 수 있다는 전제 조건만 만족한다면 Solution이 될 것이다.

locking system이라고 하면 하드웨어를 기반으로 동작한다고 생각하는 사람들이 있는데, locking system이라는 것의 범위는 엄청 넓다. 열쇠를 한 프로세스만 잡을 수 있도록 하고, 열쇠를 잡은 프로세스만 수행할 수 있도록 하는 매커니즘 자체가 locking system이라고 할 수 있다.

뒤에서 다룰 모든 동기화 문제 솔루션들도 모두 locking system의 일부라고 할 수 있다. 그 중 하나가 하드웨어를 사용하는 방법인 것이지, locking system이 하드웨어 기반으로 돌아가느 것은 아니다.

 

개발자의 입장에서 피터슨의 알고리즘을 사용하는 것과 Lock을 사용하는 것 중에 어떤 것이 더 편할까?

피터슨의 알고리즘을 사용한다면, 피터슨의 알고리즘을 이해한 개발자만 critical section이 포함된 코드를 작성할 수 있다는 단점이 있다.

하지만 lock을 이용하면 그러한 이해 필요없이 critical section 앞뒤로 acquire lock과 release lock만 호출하면 쉽게 동기화 문제를 해결할 수 있으므로 훨씬 편리할 것이다.

 

 

하드웨어를 이용해서도 critical section problem을 해결할 수 있다.

critical section problem이 발생하는 이유는 아까 X=X+1이라는 명령을 실행하기 위해 실제로는 Load, Add, Store 3단계의 instruction이 수행되어야 한다고 했다.
그리고 P0와 P1의 Load, 연산, Store instruction들이 서로 섞여서 interleaved 하게 수행되다 보니 Critical section problem이 발생하게 된 것이다.

그렇다면 P0의 instruction을 쭉 수행하고 P1의 instruction이 쭉 수행되게 하면 되는데 얘네가 왜 섞여서 수행되는 것일까?
CPU Scheduling 때문이다. 
P0가 Load instruction을 가져와서 수행했는데 CPU Scheduling이 발생해서 P1에게 CPU를 넘겨주게 되고, P1이 Load instruction을 수행하고 또 CPU Scheduling이 발생하고 P0가 CPU를 받아 Add instruction을 수행하고 이런 식이다.

만약 P1이 Load instruction을 수행하기 전에 CPU Scheduling이 발생하지 않게 만들어 버린다면?
Load, Sub, Store를 한 번에 다 수행할 수 있게 된다.
이렇게 하면 코어가 하나라면 절대 두 프로세스의 instruction이 섞여서 수행되는 일은 없다.

내가 CPU를 잡고 있다가 놓아야 하는 경우는 2가지가 있다.
I/O가 발생한 경우, Time quantum이 끝이 나서 놓아야 하는 경우.
critical section에서는 I/O가 발생할 일은 없다.
따라서 critical section에서 CPU를 놓아야 하는 일은 Time quantum을 모두 소진한 경우 뿐이다.

Time quantum이 끝난 것을 확인하는 주체는 Timer. 얘가 시간을 측정해서 끝나면 interrupt를 보내는 것이다.
따라서 이 Timer device의 interrupt를 disabled 시켜버리면, interrupt를 체크하지 않는다. 그러면 주어진 Time quantum을 다 소진해도 Timer interrupt를 확인하지 않기 때문에 CPU를 계속 쓸 수 있게 된다.

critical section을 들어가기 전에 Timer interrupt를 disabled 시킨 다음에 critical section에 들어가면 CPU 스케줄링이 발생할 수가 없음. 그리고 빠져 나오면서 enable 시킨다.
 
=> 그런데 이게 만병통치약은 아니다, CPU가 하나인 싱글 코어에서만 사용할 수 있는 방식이다.

 

그래서 instruction들이 atomic하게 수행될 수 있도록 해주는 하드웨어가 있는데 그게 바로 Synchronization Hardware다.

동기화 문제를 해결하기 위해 요즘 CPU는 특별한 하드웨어 회로를 제공한다.
이 회로는 single cycle에 기능을 다 끝마칠 수 있도록 보장한다.
이 회로가 어떤 함수를 구현한다고 하면 이 함수가 일단 실행되면 끝까지 간다는 것을 보장해준다.
=> Atomic Hardware

이 하드웨어를 이용하면 동기화 문제를 해결할 수 있다.

대표적으로 Test and Set (TAS)과 Swap 2가지가 있다.

TAS( Test and Set )

TAS 하드웨어는 다음과 같은 TestAndSet 로직을 atomic하게 실행하도록 구현된 하드웨어이다.

TestAndSet 함수는 target 값을 true로 변경하고, 변경하기 전 기존의 target값을 리턴하는 단순한 함수이다.

이러한 로직을 수행하는 TAS를 이용해서 어떻게 동기화 문제를 해결할까?

맨 처음 진입을 시도한 프로세스는 TestAndSet을 호출하여 lock을 true로 바꾸고 초기 lock 값인 false를 리턴받아 critical section에 들어가게 된다.

그리고 이때 또 다른 프로세스가 진입을 위해 TestAndSet을 호출하면, lock은 true로 바뀌어있기 때문에 true를 리턴받아 while문을 돌며 기다리게 된다.

그리고 기존에 진입한 프로세스가 critical section을 끝내고 lock을 false로 바꾸는 순간 lock을 true로 바꾸고 false를 리턴받아 critical section에 들어가게 된다.

 

atomic 하드웨어 덕분에 피터슨 알고리즘보다 훨씬 간단하게 구현할 수 있게 되었다.

그리고 개발자는 TestAndSet(lock)을 호출하는 것만으로 간단하게 동기화 문제를 해결할 수 있게 된다.

 

Swap

Swap은 기존에 잘 알려진 Swap 코드를 atomic하게 실행해주는 하드웨어이다.

이러한 Swap 하드웨어를 이용해서 어떻게 동기화 문제를 해결할까?

critical section에 들어가기 전 key = true로 설정하고 Swap을 호출한다.

이미 들어간 프로세스가 있다면 해당 프로세스가 Swap을 통해 lock 값을 true로 바꿔놓았을 것이므로 key와 lock을 서로 swap해도 의미가 없다.

그리고 먼저 진입한 프로세스가 critical section을 끝내고 lock을 false로 바꾸는 순간 lock이 false이므로 Swap을 호출한 프로세스는 key = false가 되어 while 루프를 탈출하게 된다.

 

그런데 이 2가지는 atomic hardware가 제공되어야 사용할 수 있는 방식이다.

하드웨어를 사용하지 않고도 목적을 달성할 수 있는 방법은 없을까?

( 여기서의 목적은 동기화 문제를 해결하면서도 개발자의 부담을 덜어주는 것 )

 

Semaphore

세마포어 변수 S는 integer variable이고 2개의 atomic한 operation P(), V() 를 통해 접근될 수 있다.

P는 S가 양수가 될 때까지 기다리다가 양수가 되면 빠져나오면서 S를 1 감소시킨다.

V는 단순히 S의 값을 1 증가시키는 Operation이다.

세마포어 변수 하나와 P(), V() Operation을 통해 동기화 문제를 해결할 수 있다.

초기의 mutex 값은 1이기 때문에 맨 처음 진입을 시도한 프로세스가 P를 호출하면 while문에 걸리지 않고 mutex값을 0으로 바꾼다. 그리고 critical section에 진입하게 된다.

이때 또 다른 프로세스가 진입을 시도하기 위해 P를 호출하면 mutex가 0이기 때문에 while문에 걸리게 된다.

그러다가 앞서 진입한 프로세스가 critical section을 끝내고 나오면서 V를 호출하면 mutex값이 1 증가되어 1이 된다.

그러면 기다리던 프로세스 중 하나가 진입할 수 있게 되고 또 mutex 값을 0으로 바꾸게 된다.

 

개발자는 그냥 critical section 앞 뒤로 P와 V를 호출하기만 하면 동기화 문제를 해결할 수 있게 되는 것이다.

이게 어떻게 가능할까?

앞서 말했듯이 P와 V가 atomic한 함수이기 때문에 가능한 것이다.

P와 V가 atomic하지 않게 동작하면 어떤 문제가 발생할까?

진입하고자 하는 프로세스들이 동시에 P를 호출하게 되면 mutex 값을 Load하게 되는데, atomic하지 않게 수행되면 모두 mutex 값을 1로 Load 하는 상황이 발생할 수 있다.

그러면 여러 프로세스가 동시에 critical section에 진입하는 문제가 발생하게 된다.

 

아니 어떻게 software만으로 atomic하게 동작하게 만들 수 있었을까??

싱글 프로세스인 경우에는 간단하다.

P와 V를 호출하기 전에 Timer interrupt를 disable 시키면 된다.

그러면 Timeout이 되어도 CPU를 뺏기지 않고, 모든 instruction을 수행할 수 있다.

 

Q. 나는 여기서 궁금한 점이 하나 생겼다. 세마포어가 정상적으로 작동하려면 P, V 함수가 atomic하게 수행되어야 한다고 했는데, 이건 단일 프로세서일 때의 얘기 아닌가? 멀티 프로세서 환경이라면 atomic하게 수행된다고 하더라도 각각의 프로세서에서 atomic한 함수를 통해 세마포어 변수에 접근하면 결국은 Race condition이 발생하지 않을까? 라는 생각이었다.

atomic하다는 말에 여러 프로세스 중 단 하나의 프로세스만 수행할 수 있도록 한다는 개념이 포함된 건가? 헷갈렸다.

그래서 교수님께 질문을 드렸다.

 

A. 맞습니다. 발생할 수 있습니다. 

그래서 그 점을 고려해서 atomic operation을 "구현" 해야 하며, 따라서 multi-core 시스템에서의 atomic operation 구현은 더 복잡해집니다.

일반적으로 atomic operation이 multi-core 시스템에서도 "atomic" 하도록 구현하기 위해, operation이 사용하는 memory data (예: test-and-set에서의 'target' )에 대한 접근이 배타적으로 (exclusively) 일어나도록 만드는 방법을 사용합니다. 즉, 어떤 core에서 test-and-set을 호출하면서 target을 접근하게 되면 다른 core에서 동시에 (그러나 간발의 차이로 늦게) test-and-set을 실행하면 target에 접근하지 못하고 기다리게 만듭니다.

그렇게 되면 여러 core 에서 test-and-set이 각각 실행되더라도 그들 사이에 동기화가 이루어지게 되어 "atomic"하게 되죠. Memory data에 대한 배타적 접근을 구현하는 간단한 방법은, memory에 접근하기 전에 먼저 memory bus에 LOCK signal을 보내는 것입니다. 그 signal은 다른 core들의 memory 접근을 operation 종료 시까지 금지시키게 됩니다.

이렇게 구현된 atomic hardware를 사용해서 P(), V()를 atomic하게 만들면, multi-core 또는 multi-processor 시스템에서도 semaphore를 동기화 도구로 사용할 수 있게 됩니다. 물론 peterson의 알고리즘을 사용해도 됩니다.

이러면 이해가 훨씬 더 쉬워질 것이다. P, V를 호출하는 것만으로 세마포어 변수에는 단 하나의 프로세서만 접근하는 것이 보장된다는 것이다. 그렇다는 뜻은 critical section에 들어가는 프로세스도 하나 밖에 없음을 의미한다.

=> 아니 그러면 처음부터 그냥 피터슨 알고리즘을 사용하면 되지, 굳이 피터슨 알고리즘을 사용해서 P,V를 사용하게 해서 동기화 문제를 해결해야 하나?

세마포어를 사용하지 않으면 critical section을 만날 때마다 피터슨 알고리즘에 대한 코드를 작성해야 한다.

=> 그런데 세마포어 변수를 사용하면 P와 V 함수를 정의할 때만 피터슨 알고리즘을 적용해서 코딩해두면, critical section을 만나면 P와 V를 그냥 호출하기만 하면 된다.
=> 개발자 입장에서 코딩이 매우 간단해진다.

그러나 세마포어를 사용해도 여전히 CPU를 사용하면서 while문을 돌아야 하는 busy waiting이 발생한다.

=> 이 오버헤드는 critical section이 커질 수록 같이 커진다.

 

Block/Wakeup Implementation

프로세스들이 while문을 돌면서 기다리게 하는 것이 아니라 Sleep(Block)으로 재운 다음, critical section에 진입할 조건이 되면 Wakeup으로 깨워주자.

이때는 세마포어 변수를 integer variable이 아닌 구조체로 선언한다.

그리고 Linked List의 형태로 현재 잠들어 있는 프로세스들을 관리한다.

critical section에서 프로세스가 빠져나오면 이 리스트의 프로세스 중 하나를 깨워준다.

프로세스가 critical section에 진입하기 위해 P를 호출하면 일단 S.value 값을 1 감소시킨다.

그리고 S.value가 0보다 작다면 이미 들어가 있는 프로세스가 있다는 뜻이므로 프로세스를 리스트에 넣고 재운다.

(초기의 S.value 값은 1이므로, 맨 처음엔 S.value를 1 감소시키면 S.value가 0일 것임)

critical section 수행을 마치면 V를 호출하여 S.value를 1 증가시킨다.

그리고 S.value <= 0 이라면 리스트의 프로세스 중에 하나를 깨운다.

왜 S.value <= 0 일때만 깨우느냐, S.value를 1 증가시켰는데 S.value가 0보다 작다는 것은 S.value를 1 감소시키고 잠들어 있는 프로세스가 있다는 뜻임. 만약 없었다면 내가 S.value를 0으로 만들고 진입했으니까 다시 1 증가시켰을 땐 1이 되어야 한다.

그러면 여기서 S.value가 중요한 의미를 갖는다는 것을 알 수 있다. S.value의 절대값은 현재 대기중인 프로세스의 수를 의미한다.

이렇게 세마포어 변수의 값이 의미를 가지게 되면 integer semaphore라고 한다.

단지, 있다/없다를 파악하는 용도로만 사용되면 binary semaphore라고 한다.

 

Busy waiting or Block/Wakeup overhead ?

프로세스를 Block 시키고 List에 연결하고 나중에 Wakeup 시키는 것도 다 오버헤드다.

그래서 Critical section이 엄청 작다고 하면 그냥 while 루프를 돌면서 기다리는 세마포어 방식이 더 빠를 수도 있다.

critical section의 크기에 따라서 block/wakeup 세마포어를 쓸지 그냥 일반 세마포어를 쓸지 결정해야 한다.

또는 동시에 돌고 있는 프로세스가 매우 많다고 하면 그 많은 프로세스들이 각자 while루프를 도는 것은 엄청 낭비다.
그럴 땐 그냥 재우는 게 더 좋을 수도 있다. 

이건 개발자가 판단해야 할 요소

 

지금까지 Critical Section Problem을 해결하는 Solution에 대해서 살펴봤다.

그런데 이런 걸 왜 Operating System 시간에 배우는 걸까?

여러 프로세스들이 하나의 데이터에 대해서 접근하여 일을 하는 케이스가 OS 내에서 발생할까?

이런 건 보통 애플리케이션 안에서 일어나는 현상들이 아닌가. 공유된 데이터 베이스에 여러 프로세스 또는 스레드가 접근해서 DB의 값을 변경하는 경우는 자주 일어날 것 같은데, 그럼 데이터 베이스 시간에 배워야 하는 게 아닌가??

답은 OS 내에서도 발생한다.

1. Interrupt 핸들러와 Kernel Code 사이에 critical section problem 발생

CPU가 하나라면 critical section 앞 뒤로 interrupt를 disable 시키고 enable 시키는 방법으로 해결할 수 있다.

또는 앞에서 배운 여러가지 방법들을 사용해서 동기화 문제를 해결할 수도 있음.

 

2. 각 Userprogram에서 호출한 커널 코드 사이의 critical section problem

3. Multiprocessor

CPU가 여러 개인 경우에는 Interrupt를 dis/enable 시키는 것만으로 critical section problem이 해결되지 않는다.

모든 커널 변수에 대해서 세마포어로 보호를 하든, 피터슨 알고리즘으로 보호를 하든, atomic 하드웨어로 보호를 하든 모든 커널 변수 하나 하나를 보호하는 방법이 있다.

또는 OS 자체를 하나의 거대한 critical section으로 취급해서 어떤 하나의 프로세스가 OS 코드를 수행하고 있으면 (모드 비트로 구분할 수 있겠지) 다른 CPU는 커널 모드로 수행하지 못하도록 하는 방법도 있다.

OS 커널 자체를 하나의 critical section으로 생각하는 방법은 하나의 CPU가 커널 모드에서 동작하는 동안엔 다른 CPU는 커널 모드로 수행할 수가 없어서 다른 프로세스가 System call을 호출해도 수행해 줄 수가 없으므로 성능상의 큰 문제가 발생한다.

=> 단순하고 성능이 조금 떨어지는 방법을 선택할 것인가, 복잡하지만 성능이 유지되는 방법을 사용할 것인가 선택해야 한다.

 

※모든 내용은 한양대학교 강수용 교수님의 강의를 참고하여 작성되었습니다.