Concurrency 환경 혹은 Parallelism 환경에서
둘 이상의 Thread 혹은 Process가 공유자원에서 접근할 때 여러 문제들이 발생한다.
Race Condition
Race Condition은 Concurrency 환경 혹은 Parallelism 환경에서 공유자원에 접근할 때,
접근의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말한다.
Race Condition은 결과적으로 데이터의 불일치(inconsistency)를 일으킬 수 있다.
데이터 불일치(Data inconsistency)란 같은 데이터임에도 다른 값을 가지는 상태가 존재하는 것을 의미한다.
"Multi-Processor"의 경우 부터 살펴보자.
우선 P1, P2는
memory로부터 데이터를 읽어오는 "Load과정"과,
연산을 진행하는 "연산과정"과,
결과값을 다시 메모리에 저장하는 "store단계"로 나누어 생각할 수 있다.
이 3가지의 단계 중 어떤 타이밍에 다른 Task가 접근하냐에 따라 결과값은 달라진다.
모든 케이스는 P1이 먼저 수행된다고 가정하자.
결과값 2의 경우
P1이 Store단계를 마쳤을 때는 P1의 연산 결과가 Memory에 반영된 직후이다.
따라서 이후에 실행되는 Task가 해당 Memory에 접근하여도 데이터 불일치가 발생하지 않는다.
결과값 3 혹은 1의 경우 (데이터 불일치)
P1이 Store 되기 전에, P2에서 X에 대해 접근하게 되면,
X는 1과 2라는 값이 동시에 존재하는 데이터 불일치 현상이 발생한다.
위와 같이, "Race Condition"은 접근 타이밍 혹은 순서에 따라서 결과 값이 바뀌며
결과적으로 Data inconsistency 현상을 초래할 수 있다.
"Multi-Tasking"의 경우에는 timer Interrupt로 인해 다른 Task로 전환될 수 있다.
따라서, 다른 Task로 전환되는 타이밍 혹은 작업의 순서 등으로 인해
Multi-Tasking에서도 경쟁 상태가 발생할 수 있다.
Critical Section
"Critical Section(임계구역)"이란, Concurrency 혹은 Parallelism환경에서
동시에 접근하면 안되는 공유 자원에 접근하는 코드를 의미한다.
Critical Section에선 DeadLock, Race Condition 등 여러 문제들이 발생할 수 있다.
앞서 살펴본 Race Condition의 예제에서 Critical Section은 다음과 같다.
Critical Section Problem
"Critical Section"에선, 동시에 접근하게 되면 Race Condition과 같은 여러 문제가 발생할 수 있다.
이러한 문제들이 발생하지 않기 위해선,
"Critical Section"에 접근하는 Task들에 대해 Synchronization(동기화)를 제공해야 한다.
이러한 문제를 해결하기 위해 나온 개념이 Critical Section Problem이다.
"Critical Section Problem"은
Critical Section에 안전하게 접근할 수 있기 위해,
하나의 Task만 Critical Section에 접근이 가능하는 것을 보장해야 하는 문제이다.
Critical Section Problem을 해결하기 위한 Protocol은 다음과 같다.
"Entry Section"에선 Critical Section에 접근하기 위한 Permission을 요청한다.
Permission을 받게 되면 Critical Section에 진입하여, 코드를 수행한 후,
"Exit Section"을 통해 Critical Section에서 나왔다는 것을 알린다.
이러한 Critical Section Problem을 해결하기 위해 몇 가지 조건을 충족하여야 한다.
- Mutual Exclusion : 어떤 Task가 Critical Section에서 수행 중이라면, 다른 Task는 Critical Section에 접근 할 수 없다.
- Progress : Critical Section에서 수행하는 Task가 없다면, 다른 Task가 Critical Section에 진입할 수 있어야 한다.
- Bounded Waiting : Critical Section에 진입할려고 하는 Task들이 Starvation현상이 발생하지 않도록 time bound가 존재해야 한다.
Non-Preemptive Kernel vs. Preemptive Kernel
"Non-Preemptive Kernel"의 경우는,
Kernel Mode를 빠져나갈 때까지, Kernel이 Block 될 때까지, 혹은 자발적으로 CPU 제어권을 양도할 때까지 실행된다.
즉, 중간에 interrupt로 인해 다른 Task에게 CPU Control을 뺏기지 않는다.
이는 Critical Section에서 하나의 Task만 수행가능 할 수 있게 해주므로,
Race Condition이 발생하지 않는다.
"Preemptive Kernel"의 경우는,
Kernel Mode에서 수행하고 있는 도중에 다른 Task가 Preemption(선점)하는 것을 허용한다.
따라서, Race Condition과 같은 문제들이 발생할 수 있다.
유저와 Interative한 환경에선 반응성이 중요하기 때문에,
Non-Preemptive Kernel을 잘 사용하진 않는다.
SW Solution - Peterson's Solution
"Peterson's Solution"은
2개의 Task에 대해 Critical Section Problem을 해결하는 SW적 Solution이다.
2개의 Task는 2개의 변수를 Share한다.
int turn: 어떤 Task가 Critical Section에 들어갈 것인지boolean flag[2]: flag[i]가 true라면, i Task가 Critical Section에 들어갈 수 있다는 것을 의미한다.
Peterson's Solution은 어떻게 Critical Section Problem을 해결하기 위한 3가지 조건을 만족하는지 알아보자.
Mutual Exclusion
$P_i$가 Critical Section에 들어가기 위해선,
turn == i 와 flag[i] = true를 만족하여야 한다.
따라서, 처음엔 flag[i] = true를 통해 자신이 들어갈 준비가 되었음을 알린다.
또한, Entry Section에서 turn을 상대방으로 변경하고
while문을 통해 상대방이 Critical Section에서의 수행을 완료할 때까지 기다린다.
상대방이 Critical Section에서의 수행을 마치면, i Task는 Critical Section에 진입하여 수행한다.
수행을 마치고, Exit Section에선 자신의 flag를 false로 설정함으로써,
상대방 Process가 while문을 통해 기다리는 현상을 방지한다.
만약, flag[0]과 flag[1]값이 모두 true라 하여도,
flag와 turn 변수는 공유 변수이기 때문에, Data inconsistency가 발생하지 않는다.
따라서, 하나의 값만 가지는 turn값에 의해 2개의 Task가 동시에 critical section에 접근하는 문제는 발생하지 않는다.
또한, Critical Section 내부에서 turn과, flag값이 변경되지 않는다.
이를 통합해 보았을 때, Peterson's Solution은 Mutual Exclusion을 만족한다.
Progress & Bounded Waiting
$P_i$가 Critical Section에서 수행 중이고,
$P_j$는 Critical Section에 진입할 준비가 완료되었다면,
$P_j$는 while문을 통해, $P_i$가 Critical Section을 나올 때까지 기다린다.
$P_i$가 Exit Section에서 flag[i] = false로 설정되기 때문에,
$P_j$는 Critical Section에 들어갈 수 있게 된다.
즉, $P_i$가 진입하였다면, 다음엔 $P_j$도 한 번은 수행할 수 있게 보장한다.
따라서, 어느 하나의 Task도
while문으로 상대의 상태를 계속 체크하기 때문에 Starvation 현상은 발생하지 않고, (Bounded Waiting)
바로 다음 Task가 진입할 수 있게 해준다. (Progress)
다음 3가지 조건을 만족하기 때문에 Peterson's Solution은
Critical Section Problem의 해결책이 될 수 있다.
SW Solution의 문제점
Peterson's Solution과 같은 SW 동기화는 여러 문제점이 발생한다.
첫 번째는 Busy Waiting 문제이다.
"Busy Waiting"이란,
원하는 자원을 얻기 위해서 while문을 통해 상대의 상태를 체크하는 현상을 말한다.
무언가를 반복해서 확인한다는 것은 CPU 자원의 낭비를 의미한다.
해당 알고리즘은 모든 명령어들이 Atomic하다는 가정하에 수행한 것이다.
"Atomic"이란 쪼개지지 않는 즉, 중간에 interrupt이 발생하지 않는 것을 의미한다.
하지만, 현대 컴퓨터 아키텍처에서는 기계어로 번역되는 과정에서
여러 줄로 번역되기 때문에 제대로 동작하지 않을 수 있다.
turn = j;위와 같이 공유 변수를 수정하는 명령어가 기계어로 번역되면서 line으로 분리될 수 있다는 것인데,
이는 공유 변수를 수정하는 도중 preemption이 일어날 수 있음을 의미하며 이는 동기화가 제대로 이루어지지 않을 수 있다.
이를 위해 공유 변수를 수정하는 도중엔 Interrupt가 일어나지 않도록 OS적 support를 추가할 수 있지만,
이는 Overhead가 발생하는 작업이다.
HW Solution
SW적 Solution은 다양한 문제점이 존재하였기에,
현대 Machine들은 atomic HW instruction을 제공한다.
"기계어"는 Atomic하다는 것을 보장하기 때문에
실행 중 Interrupt를 받지 않는 것(Preemption 되지 않는 것)을 보장한다.
TAS(TestAndSet) Instruction
TAS는 Test와 Set을 한 번에 수행하는 기계어이다.
target의 값을 기록하고, 변경한 다음, target의 변경하기 전 값을 리턴한다.
중요한 점은 HW Solution은 중간에 Preemption 되지 않기에 한 번에 수행된다.
lock은 공유 변수로 처음에 false로 초기화한다.
이후 TestAndSet 에서 lock 변수는 true로 변경되고, false를 리턴한다.
false이기 때문에 Critical Section에 진입하여 수행하게 된다.
이때, 다른 Task가 접근하게 되면, lock 변수는 여전히 true기 때문에
Critical Section에 진입하지 않고 lock 변수가 false가 될 때까지 계속 기다리게 된다.
따라서, 위와 같이 공유 변수를 수정하는 도중 interrupt가 발생하지 않는 것을 보장한다.
Swap Instruction
lock은 공유 변수로 처음에 false로 초기화한다.
key는 각 Task마다 가지는 local 변수이며, 해당 Task가 Critical Section에 들어갈 준비가 됐다는 것을 알린다.
HW Solution의 장단점
장점은 HW적으로 Support 해주기 때문에 구현이 간단해진다는 것이다.
하지만, 여전히 Busy Waiting 문제가 발생한다.
OS Supported Solution - Semaphore
"Semaphore($S$)"는 공유 변수로 정수형태 변수이며,
P와 V라는 2개의 Operation으로만 조작된다.
Semaphore가 0보다 커야 Task는 Critical Section에 진입할 수 있다.
- P (wait): Entry Section으로 Critical Section에 들어갈 수 있다면($S > 0$), $S$를 1 감소시키고 Critical Section에 진입한다.
- V (signal): Exit Section으로 $S$를 1 증가시킨다.
P와 V는 OS에 의해 atomic하다는 것을 보장하기 때문에, 중간에 interrupt가 발생하지 않는다.
Semephore에는 Binary Semaphore와 Counting Semaphore가 있다.
"Binary Semaphore"는 Semaphore($S$)가 [0,1]의 범위를 갖는다.
즉, 한 번에 하나의 Task만 진입이 가능하기 때문에, Mutual Exclusion을 제공한다.
"Counting Semaphore"는 Semaphore($S$)의 값의 범위가 정해져 있지 않다.
즉, 10이 될 수도 100이 될수도 있다.
Semaphore를 구현하는 방법에는 크게 2가지가 있다.
Spinlock
SpinLock에서 P연산은 다음과 같이 이루어진다.
우선, Semaphore($S$)가 0 이상이 될 때까지 while문을 통해 체크한다.
$S$가 0보다 된다면, $S$를 감소시키고 Critical Section에 진입한다.
하지만, $S$값을 확인하기 위해 while문을 돈다는 점에서 busy waiting 현상이 발생하게 된다.
DeadLock
Single-Processor라고 가정하자.
모든 Task들이 Critical Section에 진입하여 $S$가 0이라고 가정해 보자.
특정 Task에서 Critical Section에서 수행하고 있던 중
timer interrupt로 인해 Task A가 수행하게 되면,
Task A는 P연산에 들어가게 되고,
while문을 통해 $S$가 0 이상이 되기까지 기다린다.
따라서, Task A는 다른 Task가 끝나 $S$가 0보다 커질 때까지 기다리고 있는다.
또한, P 연산은 atomic하기 때문에 중간에 interrupt가 발생하지 않는다.
따라서, 다른 Task들은 Task A의 P연산이 끝나기를 기다리고 있는 현상이 발생한다.
위와 같이, 두 개 이상의 Task가 서로의 작업이 끝나기를 기다리게 되면서
결과적으로 아무것도 못하는 상태를 "DeadLock"이라 한다.
Block And Wakeup
Block And Wakeup 방식에선 각각의 Semaphore는 "Waiting Queue"를 가지고 있다.
Block 과 Wakeup Operation이 추가로 존재하는데,
Block 연산은 P 내부에서 , Wakeup은 V 내부에서 수행된다.
- Block : 해당 Task의 PCB를 waiting queue에 추가하고, 해당 Task를 waiting state로 전환한다.
- Wakeup : waiting queue에서 Task를 가져와, 이를 수행한다.
P 연산
P연산은 semaphore를 감소시키고,
Critical Section에 접근할 수 없을 경우($S$가 음수인 경우),
Block 연산을 통해 PCB를 waiting Queue에 추가하고, waiting state로 전환한다.
$S$가 양수인 경우는 Critical Section에 접근할 수 있으므로
Block 연산이 진행되지 않고 Critical Section에 진입하게 된다.
V 연산
Semaphore를 증가시켰음에도 $S$가 0인 경우는
waiting상태에 있는 Task가 많다는 의미이다.
따라서, wakeup을 통해 수행할 수 있게 해 준다.
Block And Wakeup 방식은 Spinlock과 다르게
block하고 wakeup하는 과정에서 Context Switching이 일어나게 되지만,
Busy Waiting이 발생하지 않고, Signle-Processor에서도 Deadlock 현상이 발생하지 않는다.
Probelm of Synchronization
Concurrency 환경에서 발생할 수 있는 유명한 3가지 문제들이 있다.
- Producer-Consumer Problem
- Reader-Writer Problem
- Dining Philosophers Problem
Producer-Consumer Problem
이는 Bounded-Buffer Problem으로도 불리며,
Producer는 Data를 생산하여 Buffer에 넣으면,
Consumer는 Buffer에서 Data를 가져와 사용한다.
여기서 Buffer는 공유 자원이 되며, 여러 문제가 발생한다.
Producer 입장에선, 데이터를 넣을 수 있는 곳 (빈 곳)을 찾아야 한다.
또한, 넣는 도중 Consumer가 접근할 수도 있고, 다른 Producer가 채우려 할 수도 있기 때문에
공유자원(Buffer)에 대해서 Mutual Exclusion을 제공해야 한다.
Consumer입장에서 살펴보자면, 데이터를 꺼낼 수 있는지 (채워진 곳)을 찾아야 한다.
또한, Producer가 동시에 접근할 수 있기 때문에 Mutual Exclusion을 제공해야 한다.
Using Semaphore
이는 Semaphore를 통해 해결할 수 있는데,
3가지의 Semaphore가 필요하다.
- $S_{mutex}$ : Consumer와 Producer는 buffer에 접근할 땐, Mutual Exclusion을 제공해야 한다. 따라서, Binary Semaphore를 사용한다.
- $N_{empty~buf}$ : Empty buffer의 갯수이다. N으로 초기화한다.
- $N_{full~buf}$ : Full buffer의 갯수이다. 0으로 초기화한다.
Producer 입장에선, Empty Buffer가 있고, Buffer에 접근할 수 있다면,
Critical Section인 buffer에 접근하여 데이터를 삽입한다.
Consumer는 Full Buffer가 있고, Buffer에 접근할 수 있다면,
Critical Section인 buffer에 접근하여 데이터를 가져온다.
Reader-Writer Problem
Reader는 공유자원에서 데이터를 read하고,
Writer는 공유자원에서 데이터를 write한다.
여러 명의 Reader가 접근하는 경우는 문제가 발생하지 않는다.
반면, Writer가 공유자원에 write작업에 진행하는 동안, Reader나 Writer가 접근하게 되면 Race Condition이 발생하게 된다.
따라서, Writer가 공유자원에 접근하는 동안은, 다른 Writer나 Reader도 접근할 수 없다.
Using Semaphore
우선, r readerCount 공유 변수를 0으로 초기화한다.
- int readCount : read작업을 하고 있는 Reader의 수를 나타내는 공유변수로, 0으로 초기화 한다.
- Semaphore mutex : readCount라는 공유변수에 접근하기 위해 Mutual Exclusion을 제공하는 Binary Semaphore.
- Sepaphore wrt : writer가 작업할 때 Mutual Exclusion을 제공하는 Binary Semaphore
Writer는 wrt Semaphore를 통해 Mutual Exclusion하게 공유자원에 접근한다.
Reader는 mutex Semaphore를 통해 readCount라는 공유 변수에 접근하기 위한 Mutual Exlusion을 제공한다.
또한, readCount == 1은 첫 번째 Reader를 의미하며,
해당 경우엔, write 하고 있는 Writer가 작업을 마칠 때까지 기다린다.
Reader는 읽기 작업을 마치고 mutex를 통해 Mutual Exclusion하게 접근하여
readCount를 감소시킨다.
만약 readCount == 0이라면, 마지막 Reader라는 의미이므로
독자가 없다는 것을 Writer에게 알린다.
Dining-Philosipher Problem
식탁에는 5명의 철학자들이 앉아있고,
밥(공유자원)과 5개의 젓가락(공유자원) 이 있다.
철학자들은 밥을 먹기 위해선 2개의 젓가락을 집어야 한다.
만약, 모든 철학자들이 왼쪽의 젓가락을 동시에 집어 들게 된다면,
모두가 오른쪽의 젓가락을 기다리는 상태에 빠지는 DeadLock상태가 발생한다.
또한, 누군가 2개의 젓가락을 집어 식사를 한다면, 다른 누군가는 식사를 못하는 상태인 Starvation현상이 발생한다.
이는, Semaphore는 순서를 보장할 수 없기 때문인데 이는 Monitor를 통해 해결할 수 있다.
Reference
https://www.youtube.com/watch?v=CitsUz-Dx7A&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=16
Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』
위키피디아
'CS > Operating System' 카테고리의 다른 글
| [OS] Main Memory (1) (1) | 2023.05.09 |
|---|---|
| [OS] DeadLock (1) | 2023.04.29 |
| [OS] CPU Scheduling (0) | 2023.04.05 |
| [OS] Threads (0) | 2023.04.02 |
| [OS] Processes (1) | 2023.03.29 |