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. read	3. read
2. write	4. write

경우의 수

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

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

---

Race Condition

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

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

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

1. Multiple-Processes or Multiple-Threads READ and WRITE data items.
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
3. OS의 도움(세마포) Approach

---

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 Exculsion 을 보장한다.
2. Busy Waiting (Spin Waiting) 문제가 발생한다.
3. 만약 하나의 프로세스가 실패하면, 다른 프로세스는 영원히 Blocked 된다.

⇒ Mutual Exculsion 이므로, 동시에 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 Exculsion

상호 배제

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

---

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

분석

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

Process 0	Process 1
1. while 문 실행 → 상대편 false인지 확인 → while 문 빠져나온 후, 내거 true라고 바꾸기 전에 TIMEOUT
	2. while문 → 상대편 false인지 확인 → while문 빠져 나옴
	3. f[1] = true
	4. Critical Section 작업
5. f[0] = true
6. Critical Section 작업

---

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에 진입했다고 가정하자!

Process 0	Process 1
1. flag[0]=true 로 설정
2. flag[1]=false 확인 OK
3. Critical Section 실행 시작

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

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

Process 0	Process 1
	1. flag[1]=true 로 설정
	2. flag[0]=false 확인 OK..? → X 오류 ⇒ Process 1 Critical Section 실행 불가

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

DeadLock

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

Process 0	Process 1
1. f[0]=true
	2. f[1]=true
	3. while f[0] 확인 → 무한 반복
4. while() 이 true인지 확인 ⇒ while문만 돌게 된다.

밑에와 같은 상황을 DeadLock 이라고 한다.
→ 두 프로세스 모두 flag값이 ture가 되어 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] 다시 flase로 설정

만약 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

항상 확인해야 할 것

• Multual Exclusion
• DeadLock
• LiveLock

Q. Multual Exclusion이 걸리는가?

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

Q. DeadLock이 걸리는가?

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

Q. LiveLock이 걸리는가?

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

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

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

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

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

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

→ 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. 바깥쪽 돌다가 → 안쪽 도는 경우 생기는지?

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

→ 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이 실행되게 된다.