Chapter 5-2. Concurrency : Mutual Exclusion and Synchronization

🌟 Mutual Exclusion: Software Approach (3) 🌟

Mutual Exclusion이 지켜지는 것 중요
DeadLock이 걸릴 경우의 수 존재 → 둘 다 true이면 while문을 둘 다 돌게 된다.

---

🌟 Mutual Exclusion: Software Approach (4) 🌟

DeadLock과 LiveLock의 차이점 = while문을 빠져나올 가능성

내가 Critical Section에 들어가려면,
while문 마지막에 본인 flag를 true로 바꾸고
while문에 있는 상대편 flag가 false인 것을 보고 Critical Section에 진입하기 때문에 Mutual Exclusion이 성립한다.

LiveLock이 걸릴 가능성이 있다.
→ 한 줄 한 줄 번갈아가며 TIMEOUT이 발생해서 같은 상황이 반복될 경우,
While문을 빠져나올 수 없다.
but, LiveLock이 걸릴 가능성은 굉장히 낮다.

 

---

Dekker’s Algorithm

turn

sol1에서의 turn 값은 다음에 누가 Critical Section을 진행할지를 알려주는 의미이다.

Dekker’s Algorithm에서의 turn 값은 두 사람이 동시에 Critical Section에 진입하려 할 때 우선순위를 의미한다.

turn 값만 바뀐다고 프로세스가 바뀌는 것이 아니라, 대기하고 있는 것이다.

turn 값의 우선순위가 상대 프로세스여도,
상대 프로세스의 flag값이 false로 Critical Section을 진행할 의사가 없으면,
while문을 돌지 않고 바로 Critical Section을 진행할 수 있다.

turn은 두 프로세스 모두가 Critical Section을 진행하고 싶어 경쟁할 때 사용된다.

안쪽 while문

중요함, CPU가 바뀔 때까지, 해당 차례가 아닌 Process를 막는 역할이다.

Mutual Exclusion

X → 마지막에 내 flag가 true이고, while문에서 상대방 flag가 false인 거 확인한 후 Critical Section을 실행하게 된다.

Deadlock

X → 둘 다 flag가 true여도, 둘 중 하나는 if에 걸려서 본인의 flag를 false로 바꾼다.

Livelock

둘 다 false로 바꾸는게 아니라, 둘 중 하나만 바뀐다.

Q1. P0가 Critical Section에 진입했을 때, P0가 Critical Section 실행 후, P1이 대기하고 있다가 P0가 다시 진입이 가능한가? → 가능하다. P1가 flag가 false인한, 가능하다.

Q2. While문 바깥쪽을 돌다가 안쪽을 도는 것이 가능한가? X

Q3. While문 안쪽을 돌다가 바깥쪽 While문을 도는 것이 가능한가? O

 

-> 자세한 내용은 전 게시물 참조

---

Peterson's Algorithm

Dekker's Algorithm을 간단하게 만든 것

먼저 양보한 사람이 양보 받아서

Critical Section을 진행하고 싶은 프로세스는 turn 값을 상대편 프로세스로 바꾸어 준다.
P0 → 1
P1 → 0

Critical Section을 실행하려면,

• 상대편이 false이거나,
• turn이 0이면 된다.

→ 즉, 둘 중 하나면 while문 조건에 성립하지 않으면 Critical Section을 실행할 수 있다.

Critical Section 진입 전에는 항상 코드가 필요하다!

1. 번갈아 가야하며 실행해야하는 작업 상황이 없는가?

내가 Critical Section에 진입하고 싶은데, 상대편이 Critical Section에 들어갔다 나올 때까지 기다려야하는 상황은 없는지?
교대 진입 불필요 → 상대편 flag를 확인.

CASE: P0가 Critical Section에 들어가고 싶은 상황이고, P1은 Critical Section에 들어가고 싶지 않는 경우

P1은 본인 flag[1]=false로 해놓는다.
P0는 본인 flag[0]=true로 바꾸고,
turn은 1으로 바꾼다.
그 뒤, while문을 실행한다.
이 때, 상대편 flag[1]=false이므로 while문을 빠져나오게 된다. (turn 값에 상관 X)
⇒ 번갈아 가며 실행하지 않아도 된다.

CASE: P0와 P1 모두 Critical Section에 들어가고 싶은 경우

P0가 본인 flag[0]=true로 설정
CPU가 P1으로 이동
P1도 본인 flag[1]=true로 설정
CPU가 P0로 이동
P0가 turn 값을 1로 변경
만약 이 상황에서 P0가 CPU를 뺏기지 않고 계속 CPU를 갖고 있는다 해도,
while문의 조건에 걸리게 된다.
P0는 Critical Section에 진입 불가.
P0의 TIMEOUT 후 P1이 CPU를 가져가게 된다.

P1이 turn 값을 0으로 바꾼다.
그 뒤, P1은 while문에 걸리게 된다.
다시 P1의 TIMEOUT이 되어 P0가 CPU를 가져가게 된다.

P0의 while문에서 turn 값이 0이되어 while문 조건 성립이 안되므로,
P0는 Critical Section을 실행할 수 있다.

교대로 진행할 필요가 없다.

2. Mutual Exclusion 잘지켜짐?

지켜진다. 두 사람 중 하나의 프로세스만 들어갈 수 있다.

모순만으로는 증명이 어렵다.
P0 기준, flag[1]이 false이거나 turn값이 0이기만해도 Critical Section을 증명할 수 있다.
즉, timeline에 turn 값이 바뀌는 것을 넣고 작업을 해야한다.

 

P0	P1
flag[0] == true	flag[1] == true
turn = 1	turn = 0
flag[1] == false이거나 turn == 0
Critical Section 실행	flag[0]이 false이거나 turn == 1
	Critical Section 실행

3. Deadlock X?

P0와 P1 모두 while문에 걸리면 Deadlock이 걸리는건데,
while문을 둘 다 들어가게 될 때 둘 중 하나의 turn 값은 달라지게 되므로
위의 코드에서는 해당사항 없다.

4. Livelock X?

while문 내에서 값이 수정되지 않고, 같은 상태에서 while문을 돌고 있으므로 해당사항 없다.

결국 Critical Section을 실행하는 프로세스는?
만약 P0가 turn 값을 먼저 1로 바꿨을 때,
P1이 다시 turn을 다시 0으로 바꾸어 P0이 실행하게 된다.

반대로, P1이 turn 값을 먼저 0으로 바꿨을 때,
P1이 다시 turn을 1로 바꾸어 P1이 실행되게 된다.

두 사람이 서로 경쟁하며 Ciritical Section에 들어갈 때는
먼저 turn 값을 상대편 우선으로 바꾼 Process가 먼저 Critical Section을 실행하게 된다.

⇒ 먼저 양보한 사람이 먼저 들어가는 알고리즘이다.

---

Process Interaction(상호작용) and Control Problems

우리들의 프로그램이 시스템 안에서 실행이 되면,
다른 프로세스와 어쩔 수 없이 몇가지 interaction을 해야한다.
크게 세가지가 있다.

Process Interaction

1. 서로 Resource를 차지하려고 경쟁하는 상황
   (Competition among processes for resources)
   
   
2. 데이터를 공유하는 상황
   ↳ 공유 메모리 공간에, 또는 파일에 있는 데이터를 서로 다른 프로세스들이 서로 읽기, 쓰기 하며 데이터를 공유한다.
   (Cooperation among processes by sharing)
   
   
3. Communication에 의한 Process Cooperation
   ↳ 메시지를 직접 주고 받는 것(공유 X)
   (Cooperation among processes by communication)

이러한 세가지 종류의 Process interaction이 존재한다.

만약 우리가 사용하는 프로세스가 Process interaction을 하지 않는다면, 우리가 Concurrency Control을 할 필요가 없다.

Control Problem

Concurrency Control이 실패하는 경우 발생하는 상황

Mutual Exclusion

동시에 실행하면 안되는 코드를 동시에 실행하는 경우를 배제해야한다.

• Critical section
• Data coherence

메모리에 있는 데이터를 캐시에 갔을 때 또는 파일에 있는 데이터를 읽어 갔을 때 여러개의 데이터가 시스템 안에 있을 때,
이 데이터 값들이 하나처럼 움직여야 한다.
즉, CPU1이 x값을 10에서 30으로 바꾸는 순간, 모든 캐시값과 메모리에 있는 모든 x가 30으로 바뀌어야 한다.

그렇기 때문에 데이터를 마구 바꾸어서는 안된다.
이런 것들을 지키는 것이 Mutual Exclusion이다.
당연히 Mutual Exclusion이 지켜지지 않는다고 한다면, 이 시스템은 사용할 수 없는 시스템이다.

CPU가 3개인 SMP Machine

각 CPU들은 각자 자신의 Cache를 가진다.
→ 근데, 메모리는 1개로, 공유 메모리를 사용한다.

3개의 CPU에서 3개의 프로세스 또는 스레드가 실행하고 있는데,
얘네들이 메모리에 있는 x라는 데이터 값을 캐싱해놨다.

x 값은 현재 10이라는 값이다.
⇒ 모든 CPU의 x값에 10이 들어있다.

그런데 만약, 여기서 CPU1에서는 x값을 30으로 바꾸고,
CPU2에서는 x값을 25로 바꾸게 되는 상황이 발생해서는 안된다.
x값이 10도 30도 25도 아니게 된다.

Deadlock

Starvation

Dekker's Algorithm → Critical Section에 들어갔다가 나왔는데, 상대편이 들어가려고 기다리고 있는데 내가 먼저 들어가서 또 들어가고 또 들어가고 결국 상대편이 영영 Critical Section을 진입하지 못하는 상황이 발생 한다면,
Starvation 이 발생했다고 한다.

 

Starvation 이 발생했다는 말은,
얘가 필요한 자원을 또는 내가 실행해야하는 코드를 자원을 얻지 못하거나 코드를 실행하지 못하는 상황을 얘기한다.
즉, 실행이 멈추게 되는 것이다.

 

Dekker's Algorithm에서는 Starvation이 발생하지 않는다.
하나의 프로세스만 평생 Critical Section에 들어갈 수 있지않다.

 

Pekker's Algorithm에서는 Starvation이 발생하지 않는다.
상대편 flag가 false인 동안에는 내가 계속 Critical Section을 실행해도 Starvation이라고 하지 않는다.

Starvation은, 상대편이 Critical Section을 들어가려고 하는 경우일 때 말한다. 상대편(P1)이 flag를 true로 해놓고 기다리는 상황이다.

P0가 계속 Critical Section을 들어가는 경우
상대편은 flag가 false X, true이지만,
turn 값이 0이라 P0가 실행되는 경우이다.

P1은 계속 while문을 돌고 있고, P0가 Critical Section 실행 후 나머지 section을 진행하고, TIMEOUT이 안되면, 다시 자신의 flag를 true로 할 수 있다.

중요한 건, 자신의 flag를 true로 한 뒤, turn 값을 상대편 값으로 바꿔준다.

따라서, while문에 걸려서 P0는 while문을 빠져나올 수 없게 된다.

 

결정적인 문제는, 우리들이 가정한 것은 시스템 안에 Process가 2개만 존재한다고 했는데, 시스템 안에 프로세스가 늘어나게 되면 지금까지의 알고리즘들을 적용하기가 어려워 진다. 훨씬 복잡한 알고리즘을 사용해야 한다.

• 하드웨어
• 세마포
• 모니터

Mutual Exclusion이 발생하면 세가지 문제가 발생할 수 있다.
→ 만약 Mutual Exclusion이 발생하면 이 프로세스는 사용할 수 없다.

하지만, Mutual Exclusion이 지켜지는데 다음의 문제들이 발생가능성이 있는 프로세스는 사용할 수 있다.

• Deadlock
• Livelock
• Starvation

⇒ Mutual Exclusion 관리가 제일 중요하다.
이건 무조건 지켜야 한다.