문제

문제 정의

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

이때, 주어진 각 N에 대해 문제에서 주어진 fibonacci 함수를 적용했을 때, 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력합니다.

코드

import sys
input=sys.stdin.readline
count0=[1,0,1]
count1=[0,1,1]
def fibonacci(n):
  if n>=len(count0):
    for i in range(len(count0), n+1):
      count0.append(count0[i-1]+count0[i-2])
      count1.append(count1[i-1]+count1[i-2])

T=int(input())
for i in range(T):
  num=int(input())
  fibonacci(num)
  print(count0[num], count1[num])

문제 해결

0의 개수와 1의 개수를 저장할 리스트를 선언

dp의 개념을 활용하여 피보나치 문제를 해결한다

-> 배열을 만들어서 값을 저장하는 이유는 이미 구한 숫자를 또 다시 구하는 일이 없도록 하여 단축시키기 위함이다

fibonacci(n)= fibonacci(n-1) + fibonacci(n-2)를 적용하여

피보나치 n에서의 0,1의 호출 횟수 = 피보나치 n-1 에서의 0,1의 호출 횟수 + 피보나치 n-2에서의 0,1의 호출 횟수

를 활용하여 새로운 값을 리스트에 추가

문제

#코드

import sys
input=sys.stdin.readline

a, b= map(int, input().split())
print(a+b)

#해설

파이썬의 문법을 이용하여 해결, 간단한 입출력 문제

map()과 split() 함수를 적당히 같이 활용하는 것이 입출력 받기 좋다.

🌟 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 값이 바뀌는 것을 넣고 작업을 해야한다.

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 관리가 제일 중요하다.
이건 무조건 지켜야 한다.

Multiple Processes

최신 운영체제 설계의 핵심은 여러 프로세스 를 관리하는 것이다.

시스템이 프로그램을 1개만 실행한다면, OS가 복잡할 이유가 없다.
⇒ 시스템이 여러 프로그램을 동시에 실행하려고 하기에 문제가 발생하고 이를 해결하기 위해 OS가 복잡해지는 것이다.

여러가지 프로그램을 실행시킨다고 할 때 사용하는 용어가 세가지 존재한다.

1. Multiprogramming

메모리를 잘라서 여러 프로그램들을 메모리에 집어 넣고, 이 프로그램들을 번갈아가면서 실행한다.

→ 이 경우, CPU의 개수는 상관이 없다 .
메모리 안에 여러 프로그램이 들어가서 번갈아가며 실행되기만 하면 Multi-Programming 이라고 할 수 있다.

2. Multiprocessing

CPU가 N개가 있을 때, 프로그램들이 동시에 실행되는 것.

CPU의 개수가 상관이 있다. CPU가 여러개이어야 한다.
⇒ CPU가 하나일 때는 Multi-Processing 이라고 말할 수 없다.

Multi-Programming 을 포함한다.

ex) CPU가 10개일 때, 프로그램이 100개이면,
어차피 동시에 실행시킬 수 있는 프로그램은 10개로 제한된다.
⇒ 10개 안에서 번갈아 가며 실행해야 한다.

3. Distributed Processing

각각 하나씩 CPU와 OS를 갖고 있는 컴퓨터들을 하나의 네트워크로 연결해서,
원래 있던 OS위에 하나의 OS Layer (Distributed OS)를 덮어서,
여러개의 CPU를 갖고 있는 것처럼 실행한다.

⇒ 프로세스들이 여러군데에서 동시에 실행될 수 있고, 각각의 컴퓨터에서는 번갈아 가며 프로세스들을 실행시킨다.

🌟Concurrency🌟

CPU가 10개 존재하는 시스템이 CPU가 1개일 때보다 실행 속도가 10배 빠르지 않다.
→ 이유가 여러개 존재하지만, 그 중 하나가 Concurrency Control 이다.
Concurrency Control 은 CPU가 많이 존재 하는 시스템일 수록 중요하다.

1. Interleaving 과 Overlapping processes 들의 상호작용 관리

• interleaving : 번갈아 가면서 실행
• overlapping : 정말로 동시에 실행

⇒ 문제가 발생할 수 있다.

ex) 내 프로그램에서 3+5 연산을 실행하려고 한다.
정확한 답은 8이 나와야 하지만, 다른 프로그램을 Interleaving 과
Overlapping 하면서 동시에 실행하게 되면,
결과가 달라질 수 있다.

2. OS structure: OS 자체는 일련의 프로세스 또는 스레드로 구현된다.

OS 프로그램은 여러 OS 프로그램들로 구현되어 있다.
이 여러 OS 프로그램들은 다시 Interleaving 과 Overlapping 을 하며 실행된다.
→ 이 때, Concurrency Control 이 되지 않으면 시스템의 신뢰도가 낮아지게 된다.

Concurrency

Concurrency 는 여러 프로그램을 동시에 실행되는 것을 말한다.

Concurrency Control

Concurrency Control 은 여러 프로그램이 동시 실행될 때 Correctness (정확도) 를 지키게 하는 것을 말한다.

그런데, Concurrency Control 을 구현하는데에는 많은 비용이 들게 된다.

• Correctness (정확도)
  기준? → 이 프로그램을 다른 프로세스 없이 홀로 실행했을 때와 다른 프로세드와 같이 실행했을 때의 결과 값이 같냐?

A Simple Example

Process P1과 Process P2가 Interleaving, Overlapping 되며 실행이 된다.
READ 와 WRITE 는 file을 읽는 입출력 문장이다.

file에 x에 100이라는 값이 저장되어 있는 상태이다.

P1에서 file로부터 x 값을 읽어온다.

P1이 Timeout되어서 P2에게 CPU를 뺏긴다.
P2에서 file로부터 x 값을 읽어온다.

P1에서 x에 100을 더한 후 file에 쓴다.

P2에서 x에 200을 더한 후 file에 쓴다.

결과적으로 x에는 300이 들어가게 된다.
하지만, 원래 의도한대로라면 400이라는 값이 들어가야 한다.

Q. 언제 x가 400이라는 결과를 얻을 수 있을까?

P1 P2

경우의 수

1. 1-2-3-4 → 400 ✅
2. 1-3-2-4 → 300
3. 1-3-4-2 → 200
4. 3-4-1-2 → 400 ✅
5. 3-1-2-4 → 300
6. 3-1-4-2 → 200

실행 순서에 따라 결과가 달라진다.
→ Race Condition 이 존재한다.
⇒ Race Condition이 발생하지 않는, 즉, 경우의 수가 발생하지 않는 코드를 사용해야 한다.
⇒ Concurrency Control 달성!

Race Condition

Race Condition 은 여러 프로세스, 스레드가 데이터를 읽고 쓰는 작업을 할 때 발생한다.
파일뿐만 아니라, 공유 메모리를 읽고 쓸 때도 발생한다.
↳ 읽고 쓰는 순서에 따라 결과가 달라질 때 Race Condition 이 존재한다고 한다.

ex) 달리기 → 엎치락 뒤치락 하므로 결과를 예측할 수 없다. (경우의 수가 많다.)

Race Condition은 다음의 상황에서 발생한다.

1. Multiple-Processes or Multiple-Threads READ and WRITE 
2. Process들의 실행 순서 에 최종결과가 변하는 상황

결과값은 누가 race의 마지막을 끝내냐에 따라서 달라진다.

Critical Section

Interleving 이나 Overlapping을 하면서 프로그램을 동시실행 할 때,
동시 실행하면 안되는 부분, 즉 동시 실행하면 Race condition 이 발생하는 부분을 Critical Section 이라고 한다.

Critical Section 은 일부 코드만 해당한다.
공유 자원이 존재하여 같이 공유하는 프로그램들이 동시 실행하면 안되는 부분이다.

정리

Critical Section 은 전체 프로그램 중 일부 코드 이다.
↳ 이 일부 코드 에 Race condition 이 있다.
→ Race condition 은 두 프로세스의 Critical Section 코드를 동시 실행 하여 결과가 달라져 정확한 결과값을 얻지 못하는 상황을 말한다.
↳ Concurrency Control 은 조절을 해서 Race condition 이 발생 하지 않게 하여 정확한 결과값이 나오게 하는 것을 말한다.

⇒ Concurrency Control 에는 3가지 방법이 존재한다. 

1. 소프트웨어적 Approach
2. 하드웨어 insturction 도움 Approach → chap 5.2
3. OS의 도움(세마포) Approach → chap 5.2

SoftWare Approaches: 코드를 잘 작성하는 것
→ 밑에 4가지 시도의 코드가 나오는데, 전부 실패한 시도이다.
이 시도에서 실수를 잘 찾아내야 한다.

Mutual Exclusion: SoftWare Approaches 1

First attempt for two processes w/turn (공유변수)

가정: Process는 딱 두개만 존재하며, CPU는 하나만 존재한다.
Interleaved된 상태에서 진행되며, 둘 다 Critical Section이 존재한다.

해당 코드는 Critical Section 위쪽에 While문 있다.
→ Critical Section 을 동시에 실행하지 않기 위한 코드이다.

해당 코드는 Critical Section 아래쪽에 turn의 값이 바뀌는 코드가 존재한다.
→ Critical Section 실행 후, 상대편이 Critical Section 을 실행할 수 있게 하기 위한 코드이다.

공유 변수

메모리는 Process 단위로 할당되므로 다른 프로세스가 access 할 수 없다.
하지만, 공유메모리 는 다른 프로세스도 함께 access 할 수 있다.

turn 변수는 공유메모리 공간에 존재하는 공유 변수이다.

• turn == 0 → P0 먼저 실행
• turn == 1 → P1 먼저 실행

분석

1. 해당 코드는 Mutual Exclusion 을 보장한다.
2. Busy Waiting (Spin Waiting) 문제가 발생한다.
3. 만약 하나의 프로세스가 실패하면, 다른 프로세스는 영원히 Blocked 된다.

⇒ Mutual Exclusion 이므로, 동시에 Critical Section 에 진입하지 않는다.

↔ 하지만, 해당 코드는 사용이 불가능한 코드이다.
↳ P0가 Critical Section 을 진행할 때,
P0가 Timeout이 되어 CPU가 P1에 가더라도 P1은 while문만 무한 반복한다.

⇒ 결론적으로 프로세스가 실행 중이어도 Waiting을 한 것이다.
즉, Blocked 상태라고 볼 수 있는데, 이를 Busy Waiting 한다고 한다.
CPU를 주면 계속 작업을 하기 때문에 Busy 이지만, while 문에서 Waiting을 하는 중이다.

두 코드가 둘 다 Critical Section에 진입하려고 1번씩 시도하는 것처럼 보이지만, 이 Critical Section은 프로그램의 일부일 뿐이다.

만약 p0이 위의 코드 부분을 10번 반복하고 p1은 1번만 반복한다고 하면,
첫 번째 부분은 괜찮지만, p0가 두 번째 이후 turn 값을 1로 바꾸고 나면,
turn 값은 더 이상 0으로 바뀌지 못해 p0는 더 이상 실행될 수 없다.
⇒ 두 프로세스 중 하나가 fail 하거나 반복되는 횟수가 달라지면,
나머지 하나가 Busy Waiting 하게 된다.

Mutual Exclusion

상호 배제

동시에 실행되면 안되는 코드가 절대 서로 동시에 실행되지 않는다는 것을 보장한다는 의미이다.

Mutual Exclusion: Software Approaches 2

Second attempt for two processes w/flag[2] (공유변수)

Process 0이 Critical Section 을 실행 하기 위해서,

• Critical Section 실행 전,
  → 상대편이 실행 중인지 확인하기 위해 flag[1]이 false인지 확인한다.
  → flag[0]을 true로 바꾼다.
• Critical Section 실행 후,
  → 상대 프로세스가 Critical Section을 실행할 수 있게 하기 위해 flag[0]을 false로 바꾼다. (나 Critical Section 실행 끝났어!)

공유 변수

flag[0] == true → Process 0 이 실행
flag[1] == true → Process 1 이 실행

초기 값은 둘 다 false

분석

해당 코드는 Mutual Exclusion 을 보장하지 않는다.
⇒ 두 프로세스의 Critical Section 동시 진입 상황이 발생할 수 있다.
↳ 첫 줄에서 TIMEOUT 되면 그냥 끝이다.

Mutual Exclusion: Software Approaches 3

Third attempt for two processes w/flag[2] (공유변수)

SoftWare Approaches 2에서 Critical Section 위쪽 코드를 뒤바꾼 코드이다.

Process 0을 실행하기 위해서,
상대 flag[1] 확인 전, flag[0] = true로 먼저 바꾸어서 Process 0이 Critical Section을 실행하겠다는 의지를 보여준다.

분석

1. 해당 코드는 Mutual Exclusion을 보장한다.
2. 하지만, DEADLOCK 이라는 또다른 문제를 유발한다.
   ↳ 첫 줄에서 두 프로세스의 flag가 둘다 true가 된 후, TIMEOUT 되면 그냥 끝이다.

즉, Critical Section 을 두 프로세스가 동시에 작업할 일은 없다.

Q. Mutual-Exclusion 증명하는 방법?

두 프로세스가 동시에 작업하는 경우가 존재하는 경우에는 한가지 경우만 예시로 들어주면 증명이 가능하지만,
어떠한 경우에도 두 프로세스가 동시에 작업하는 경우가 없는 경우(Mutual-Exclusion)의 증명 방법은 ⇒ 모순 을 보여주면 된다.

일단, P0가 Critical Section에 진입했다고 가정하자!

1~3까지 f[0]=true인 상태 유지

P1도 Critical Section 코드를 동시에 실행한다고 가정하자!

1~2까지 f[1]=true인 상태 유지

Deadlock

두 프로세스가 둘 다 뭔가(while문: 상대편이 false가 되기를)를 기다린다.
근데 상대편이 영원히 false가 되지 않을 수 있다.

밑에와 같은 상황을 DeadLock 이라고 한다.
→ 두 프로세스 모두 flag값이 true가 되어 While문을 빠져 나올 수가 없다.
CPU를 가져가 줘도 While문만 돈다.

내가 어떤 상황에서 While문을 돌면서 Waiting이 됐는데,
이 때, While문 조건을 바꿀 사람 → 나 X / 상대편 O
근데, 상대편도 똑같이 While 문을 돌고 있어서 While문의 조건을 바꾸지 못한다.

⇒ 3번 시도코드가 2번 시도코드보다 낫다.
2번 시도는 정확도가 낮아지게 된다.

⇒ 정확도 가 제일 첫번째로 중요한 요소이다!
DeadLock 도 항상 발생하는 상황이 아니다.(10번 중 1번 정도 발생)

Mutual Exclusion: Software Approaches 4

Fourth attempt for two processes w/flag[2] (공유변수)

Process 0이 Critical Section을 실행하고 싶을 때,
flag[0] 을 true로 설정한다.
그 후 while 문을 돌며 상대 flag[1]이 true인지 확인한다.

• flag[1] = true 인 경우
  → falg[0] = false로 설정 ⇒ Process 0 이 양보할게,, ( DeadLock 예방)
• flag[1] = false 인 경우
  → Critical Section 실행 후, flag[0] 다시 false로 설정

만약 Process 1이 Critical Section을 실행하고 싶어서 flag[1]을 true로 설정했는데,
flag[0]이 true라 while 안으로 들어가서 flag[1] 이 false가 되고,
delay 구간에서 TIMEOUT 이 되어 P0에게 CPU가 돌아가게 되면,
flag[0] == true, flag[1] == false이므로 Process 0이 Critical Section을 실행하게 된다.

분석

1. Mutual-Exclusion 지켜진다.
   ↳ 내 flag가 true이고, 상대편 flag가 false인 거 확인하고 Critical Section을 실행하게 된다. 결국 while문을 빠져나올 때는 상대편 flag가 false일 때만이다.
2. Deadlock 은 일어나지 않는다.
   ↳ 둘 다 while문을 돌 때 상대 flag가 바뀔 가능성이 존재한다.
3. 하지만, LIVELOCK 이라는 새로운 문제를 유발한다.

LIVELOCK

DeadLock 과 확률 이 다르다.

• Deadlock
  일단 While 문을 시작하면, While문을 빠져나올 확률이 0%.
• Livelock
  일단 While 문을 시작하면, While문을 빠져나올 확률이 굉장히 높다.
  오히려 빠져나오지 못할 확률이 더 낮다.
  ⇒ 4번째 방식이 나머지 3가지 방식보다 제일 문제가 발생할 확률이 적다.

ex) 밑의 명령어들이 한 줄, 한 줄 TIMEOUT이 되는 상황이라고 가정해보자.
- P0 sets flag[0] to true
- P1 sets flag[1] to true
- P0 checks flag[1]
- P1 checks flag[0]
- P0 sets flag[0] to false
- P1 sets flag[1] to false
- P0 sets flag[0] to true
- P1 sets flag[1] to true

↑ 위의 상황에서는 while문을 빠져나올 수 없다.
false와 true 사이의 Delay 구간에서 Timeout이 걸려서 상황이 맞아 Critical Section을 실행할 수 있는 것인데, 위의 경우에서는 그게 불가능하다.

Dekker’s Algorithm

공유 변수 turn
1. 첫번째 시도에서의 turn : 다음에 누가 들어갈지 정하는 변수
2. Dekker’s Algorithm 에서의 turn : 두 사람이 동시에 Critical Section에 들어가려고 할 때, 누가 양보할 차례인지 나타내는 값이다.

→ turn이 1일 때,

• Process 0이 양보할 차례이므로 자신의 flag[0]을 false로 설정하고, while(turn==1)에서 잠시 기다린다.
• Process 1은 flag[0]이 true라고 하더라도, if문 안쪽을 실행하지 않는다.
  ⇒ 바깥쪽 while문을 돌며, 상대편 flag[0]가 false가 될 때까지, 상대가 양보할 때까지 기다린다.

Critical Section 진입 전,

• 바깥쪽 while문을 돌면서 상대편이 false가 될때까지 기다린다.
  안쪽 while(turn==1)에서는 조금 기다린다. → 상대방이 Critical Section을 끝내고 turn이 0이 될 때까지
• Critical Section 진입 직전에는 상대편 flag가 false, 내 flag가 true인 것을 확인하고 진입하게 된다.

Critical Section 진입 후,

• turn 값 변경 → 상대편에게 넘겨줌
• flag 값 변경

Remainder : 전체 프로그램 중 Critical Section 이외의 부분들을 말한다.

Questions

항상 확인해야 할 것

• Mutual Exclusion
• DeadLock
• LiveLock

Q. Multual Exclusion이 걸리는가? X

3,4 번째 알고리즘과 동일하다.
어쨌든 Critical Section에 진입하기 전에 내 flag 값이 true인 것을 보고, 상대편 flag 값이 false인 거 보고 진입한다.

Q. DeadLock이 걸리는가? X

바깥 While 문에서 멈춰야 DeadLock이 걸리는데, 상대편 flag가 바뀌는 것을 확인 할 수 있다.

Q. LiveLock이 걸리는가? X

두 사람이 다 자기 flag를 바꾸면 livelock이 생기는데 이 코드에서는 서로 계속 다르다.

while문 2개
상대편 flag 값을 검사하는 바깥쪽 while문
turn 값을 검사하는 안쪽 while 문

만약 내가 상대편 flag가 true라서 turn 조건이 안맞아 바깥쪽에서 돌다가 turn 이 바껴서 안쪽 while 문을 돌게 되는 경우가 발생하는가?

반대로 내가 안쪽 while문을 돌다가 turn 값이 바껴서 안쪽 while문을 빠져나와서 바깥쪽 while문을 돌아야 하는 상황이 생기는가?

Q. 안쪽 돌다가 → 바깥쪽 도는 경우 생기는지? O

상대편이 어떻게 하면 이런 상황이 발생하는지?

→ P0 안쪽 while문(turn==1)만 도는 상황일 때,
turn이 1이기 때문에 안쪽 while문을 돌고 있고,
바깥쪽 while문(flag[1])을 돌기 위해서는 turn 이 0으로 바뀌어야 한다.

P1에서 Critical Section을 실행한 뒤, turn이 0으로 바뀐다.
만약 이때 TIMEOUT이 걸리게 되면, 아직 flag[1]은 true인 상태이므로
flag[1]==true, turn == 0 인 상태로 바깥쪽 while문을 돌 수 있다.

Q. 바깥쪽 돌다가 → 안쪽 도는 경우 생기는지? X

상대편이 어떻게 하면 이런 상황이 발생하는지?

→ P0 기준 바깥쪽을 돌려면 flag[1] == true인 상태이다.
안쪽 while문을 돌고 있지 않으므로 turn == 0 값이다.
그러므로 아예 if문 안으로 들어가지 못하는 상황일 것이다.

안쪽 while문을 돌기 위해서는 turn 값이 1로 바뀌어서 if문부터 통과해야한다.
그런데 turn 값을 1로 바꾸기 위해서는 P0가 Critical Section을 실행해야한다.

바깥쪽을 돌다가 안쪽을 돌기 위해서는
flag[1]이 true인 상태에서, turn 값이 0이었다가
여전히 flag[1]이 true인 상태에서, turn 값이 1로 바뀌어야 하는데,
turn 값이 0인 상태일 때, turn 값을 1로 바꾸기 위해서는
바깥쪽 while문을 나가 P0가 Critical Section을 실행해야만 한다.

즉, 바깥쪽 돌다가 → 안쪽 도는 경우 는 발생되지 못한다.

Q. 언제 무한대로 진입이 안되는 상황이 생기는가?

공통적으로 내가 Critical Section을 진행하고 나면,
상대편이 진입할 수 있게 양보를 해준다.

이 알고리즘은 Critical Section에 P1이 들어갔다가 나와서 다시 또 Critical Section에 진입할 수 있다.
여러번,,!
어떤 상황에서 계속 진입을 할 수 있는지?

그러나 무한대로 진입은 안됨
언제 무한대로 진입이 안되는 상황이 생기는가?

→ P1의 flag[1]==false인 상태에서 P0이 한번 실행되고 나면, turn 값이 1로 바뀌게 되고,
    P1이 실행되지 않는다면, P0는 while문을 거치지 않고 계속 Critical Section을 돌 수 있다.

그러나, P1이 한 번이라도 실행되게 되면, turn 값이 1인 상태이므로
flag[0]==true이라할지라도, 무조건 P1이 실행되게 된다.