Chapter 5. Concurrency : Mutual Exclusion and Synchronization

Multiple Processes

1. Multiprogramming

메모리를 잘라서 여러 프로그램들을 메모리에 집어 넣고, 이 프로그램들을 번갈아가면서 실행한다.
→ 이 경우, CPU의 개수는 상관이 없다

2. Multiprocessing

CPU가 N개가 있을 때, 프로그램들이 동시에 실행되는 것
⇒ CPU가 하나일 때는 Multi-Processing 이라고 말할 수 없다.
Multi-Programming 을 포함한다.

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 자체는 일련의 프로세스 또는 스레드로 구현된다.

Concurrency

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

Concurrency Control

여러 프로그램이 동시 실행될 때 Correctness (정확도) 를 지키게 하는 것

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

A Simple Example

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 → 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 이 존재한다고 한다.

 

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

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

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

 

Critical Section

Interleaving 이나 Overlapping을 하면서 프로그램을 동시실행 할 때,
동시 실행하면 안되는 부분, 즉 동시 실행하면 Race condition 이 발생하는 부분

 

정리

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

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

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

---

Mutual Exclusion: SoftWare Approaches 1

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

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

분석

1. 해당 코드는 Mutual Exculsion 을 보장한다.
2. Busy Waiting (Spin Waiting) 문제가 발생한다.
   ⇒ 두 프로세스 중 하나가 fail 하거나 반복되는 횟수가 달라지면, 나머지 하나가 Busy Waiting 하게 된다.
3. 만약 하나의 프로세스가 실패하면, 다른 프로세스는 영원히 Blocked 된다.

Mutual Exclusion: SoftWare Approaches 2

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

공유 변수

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

초기 값은 둘 다 false

분석

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

Process 0	Process 1
1. while 문 실행 → 상대편 false인지 확인 → while 문 빠져나온 후, f[0] 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] (공유변수)

분석

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

 

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

→ 두 프로세스 모두 flag값이 true가 되어 While문을 빠져 나올 수가 없다.

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

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

 

Mutual Exclusion: Software Approaches 4

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

분석

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에 들어가려고 할 때, 누가 양보할 차례인지 나타내는 값이다.

 

분석

1. Mutual-Exclusion 지켜진다.
   ↳ 내 flag가 true이고, 상대편 flag가 false인 거 확인하고 Critical Section을 실행하게 된다. 결국 while문을 빠져나올 때는 상대편 flag가 false일 때만이다.
2. Deadlock 은 일어나지 않는다.
   ↳ 바깥 While 문에서 멈춰야 DeadLock이 걸리는데, 상대편 flag가 바뀌는 것을 확인 할 수 있다.
3. Livelock 은 일어나지 않는다.
   ↳두 사람이 다 자기 flag를 바꾸면 livelock이 생기는데 이 코드에서는 서로 계속 다르다.
   
4. Starvation이 발생하지 않는다.
   ↳하나의 프로세스만 평생 Critical Section에 들어갈 수 있지않다.

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

→ P0 안쪽 while문(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인 상태이고, 바깥쪽을 돌다가 안쪽을 돌기 위해서는 flag[1]이 true인 상태에서, turn 값이 0이었다가 여전히 flag[1]이 true인 상태에서, turn 값이 1로 바뀌어야 하는데, turn 값이 0인 상태일 때, turn 값을 1로 바꾸기 위해서는 바깥쪽 while문을 나가 P0가 Critical Section을 실행해야만 한다. 즉, 바깥쪽 돌다가 → 안쪽 도는 경우 는 발생되지 못한다.

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

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

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

---

Peterson's Algorithm

분석

1. 번갈아 가며 진행할 작업상황은 없다.(교대 진입 불필요)
   ↳ CASE1, 2로 밑에서 설명
2. Mutual-Exclusion 지켜진다.
   ↳ 내 flag가 true이고, 상대편 flag가 false이거나 turn값이 0이기만 해도 Critical Section을 실행하게 된다. 
   
3. Deadlock 은 일어나지 않는다.
   ↳ 모두 while문에 걸리면 Deadlock이 걸리는건데, while문을 둘 다 들어가게 될 때 둘 중 하나의 turn 값은 달라지게 되므로
4. Livelock 은 일어나지 않는다.
   ↳while문 내에서 값이 수정되지 않고, 같은 상태에서 while문을 돌고 있으므로 해당사항 없다.
5. Starvation이 발생하지 않는다.
   ↳Starvation은 상대편이 Critical Section을 들어가려고 하는 경우일 때 말한다. 상대편(P1)이 flag를 true로 해놓고 기다리는 상황이다. 상대편 flag가 false인 동안에는 내가 계속 Critical Section을 실행해도 Starvation이라고 하지 않는다.
   

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

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

 

CASE 2: 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을 실행할 수 있다. 교대로 진행할 필요가 없다.

 

cf) Mutual Exclusion이 잘지켜지는 이유

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 실행

 

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

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

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

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

---

Process Interaction(상호작용) and Control Problems

 Process Interaction

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

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

Mutual Exclusion: 전체 코드가 아닌, Critical Section에한 번에 하나의 프로세스만 실행할 수 있도록 하는 것. 어떠한 경우에도 지켜져야 한다.

1. Deadlock
2. Livelock
3. Starvation : 상대편이 영영 Critical Section을 진입하지 못하는 상황이 발생 한다면,Starvation 이 발생
   즉, 실행이 멈추게 되는 것이다.

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

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

---

Requirements for Mutual Exclusion

• Critical Section을 사용하는 다른 프로세스가 없을 때, Critical Section에 대한 액세스를 지연시켜서는 안 된다. (Approach 1처럼)
• 프로세스의 상대적 속도 가정 의미 X (Approach 4처럼)
• 프로세스의 개수 가정 의미 X (Dekker, Peterson Algorithm 처럼)
• 프로세스는 Critical Section 안에 유한한 시간 동안만 남아있는다.
  ↳ 한 번에 하나의 프로세스만을 실행할 건데, DeadLock X, LiveLock X, Starvation X, 어떠한 가정도 X
  ↳하지만 DeadLock, Starvation, LiveLock이 발생해도 사용해야하는 경우가 존재한다.
  

---

Approaches for Mutual Exclusion

Software approaches

1. Dekker's algorithm
2. Peterson's algorithm

Hardware approaches
An approaches using the special-purpose machine instruction

1. Compare_and_swap instruction
2. Exchange instruction

starvation 이 발생할 가능성이 있다.

Software+Hardware approaches
An approach using support within the OS or a programming language

1. Semaphore
2. monitor

Q. 위의 접근 방법을 다 알아야하는 이유?

하드웨어 instruction, Semaphore, ... 내가 사용하는 프로그램 OS 가 모든 방법을 제공하지 않을 수 있기 때문이다.

⇒ 즉, 시스템 상황이 어떻게 될 지 알 수 없기 때문이다.

---

Compare&Swap Instruction (Hardware Instruction)

int compare_and_swap (int *word, int testval, int newval)
{
	int oldval;
    
    oldval = *word;
    if(oldval == testval) *word = newval;
    return oldval;
}

1. word 와 testval 의 값이 같을 경우
   → word의 값을 newval의 값으로 변경한다.
2. word 와 testval 의 값이 다를 경우
   → word의 값 변경하지 않는다.
3. 항상 oldval, 즉 word에 들어 있던, 원래의 값이 return 된다.

 

 분석

1. Compare&Swap 은 atomic instuction이다. (Hardware instruction)
   → 하드웨어 instruction 이기 때문에 인터럽트가 발생하지 않는다.
   ↳ 이유: 하나의 instruction 이기 때문이다.
   ⇒ 위의 코드 중간에서 끊기는 상황은 발생하지 않는다.
   ⇒ instruction 은 Fetch stage + Execution stage 를 거치고 나서야 Interrupt stage 를 거치게 된다
   
2. Compare&Swap Instruction 의 실행 시간 동안,
   그 공간을 참조하는 모든 instruction 들은, 메모리 공간(위의 코드에서 word 가 가르키는 메모리 영역) 접근이 blocked 된다.
   ⇒ Compare&Swap 은 하나의 Process 만 가능하다.
   ⇒ Compare&Swap 은 Interleaving , Overlapping 이 불가능하다.

Starvation 가능성 O

P2가 Critical Section을 실행하다가 TIMEOUT
→ P2를 제외한 나머지 Process가 CPU를 잡음
→ compare_and_swap while문에 걸림
→ P2가 CPU를 다시 잡는다.
→ P2가 bolt값을 0으로 바꾸고 바로 다시 P2가 compare_and_swap을 실행
→ P2가 Critical Section 다시 진입

---

Exchange Instruction (Hardware Instruction)

void exchange (int *register, int *memory) {
	int temp;
    
    temp = *memory;
    *memory = *register
    *register = temp;
}

-> register(key) 값과 memory(bolt) 값을 교환한다.

 

분석

1. Exchange는 atomic instruction이다. (Hardware instruction)
   ↳ 하나의 instruction 이기 때문에 중간에 interrupt가 발생하지 못한다.
   (fetch, execution stage 까지 진행한 후 interrupt 가 진행된다.)
   
   
2. Exchange Instruction 의 실행 시간 동안,
   그 공간을 참조하는 모든 instruction 들은, 메모리 공간(위의 코드에서 word 가 가르키는 메모리 영역) 접근이 blocked 된다.
   → 동시 접근 불가 ⇒ 한 번에 하나의 Process 만 exchange 가 가능하다. ⇒ Exchange 은 Interleaving , Overlapping 이 불가능하다.

---

Hardware Mutual Exclusion

Softawre instruction: 복잡하지만, Starvation X, Deadlock X
Hardware instruction: 단순하지만, Starvation O, Deadlock O

 

분석

장점

1. 프로세스의 수에 제한이 없다.
   ↳ CPU, Process 숫자를 가정할 필요가 없다. → n개 적용 가능하다.
2. 간단하다 → 증명하기 쉽다. (한 줄)
3. multiple critical section 을 지원한다.
   ↳ OS가 Critical Section 뿐만 아니라 시스템 설계에 있어,
   해결해야하는 문제들이 존재하는데, 이 문제들은 while문을 여러개 통과해야 한다.
   ⇒ 그래도 Hardware instruction은 간단하기 때문에 쉽게 적용할 수 있다.

단점

1. Busy-Waiting
   ↳ Process 한 개 이외에는, CPU를 차지해도 whiel문에 걸려있는 상태로 CPU 시간을 낭비한다.
2. Starvation
   ↳ 한 Process만 Critical Section을 독점할 수 있다.
3. Deadlock
   ↳ 위의 예시에서는 while문이 1개이기 때문에 모두가 못들어가는 상황은 발생하지 않지만, multiple critical section 에서는 Deadlock 이 발생할 가능성이 존재하게 된다.

Busy-Waiting은 Software Approach 와 Hardware Approach 모두 에서 발생한다.
하지만, Starvation과 Deadlock은 Hardware Approach에서만 발생하므로 더 심각하다.

---

Semaphore

OS가 제공하는 Tool,구조체 변수이다. (an integer + a queue)

OS 변수 "S"

변수 S 는 OS의 변수 로 연산이(+, -) 불가능하다.(S++, S-- X)

변수 S 는 초기화할 때 0 이상의 값 만 가능하며, 음수는 불가능 하다.
변수 S 의 값: 어떤 상황을 의미한다. ⇒ 음수가 의미하는 상황이 따로 존재한다. 그렇기 때문에 음수로 초기화해서는 안된다.

 

semaphore s 의미

S > 0

semWait을 그냥 통과 할 수 있는 횟수를 의미한다.

즉, 현재 CPU를 잡고 있는 프로세스가 semWait System Call 을 호출해도,
Blocked 되지 않고 넘어갈 수 있는 횟수를 의미한다.

ex) s = 0 → semWait을 그냥 통과할 수 없다.
    s = 3 → semWait을 3번 통과할 수 있다.

S <= 0

절대값 s 는 Blocked queue에 들어 있는 프로세스의 개수를 의미한다.

ex) s = 0 → Blocked queue에 들어있는 프로세스 개수 = 0
    s = -10 → Blocked queue에 들어있는 프로세스 개수 = 10

⇒ s 에는 의미가 있기 때문에 초기값은 반드시 0 또는 0 이상의 값으로 설정해주어야 한다.

 

System-Call

OS에게 무언가를 해달라고 요청하는 것으로, OS의 function을 실행해달라고 요청하는 것이다.

여기서 프로세스1과 프로세스2가 System call 하는 것은 OS의 변수인 S 에 접근 요청을 하기 위해서이다.

 오직 세가지 operation만 존재하며 모두 atomic 이다.

1. Initialize (w/ nonnegaive integer value)

초기화(S의 값 초기화)
↳단, 음수는 불가능하다. (0이상의 값만 가능)

2. SemWait

세마포어 값을 감소 시킨다.

• s >= 0 → process 그냥 통과
• s < 0 → process를 Blocked queue로 이동

결과 값이 음수 이면 프로세스를 block 할 수도 있고 block 시키지 않을 수도 있다(프로세스가 그냥 통과할 수도 있다).

3. Semsignal

결과 값이 0보다 작거나 같으면 세마포어 값을 증가 시키고 대기열에서 프로세스 block을 해제한다.

S의 값을 하나 더한다.

• s > 0 → 아무것도 안함
• s <= 0 → process를 Blocked Queue에서 빼서 Ready Queue로 옮겨준다.

Semsignal을 호출한 Process가 아니라, Blocked queue에 있는 Process 중 하나를 꺼내서 Ready Queue로 옮긴다.
⇒ Running 가능

ProcessA → semWait → s < 0 → (ProcessA: BlockedQueue 이동 )
→ ProcessC → semSignal → s <= 0 → (ProcessA → ReadyQueue)
→ semSignal 다음 코드를 실행한다.

struct semaphore {
	int count;
    queueType queue;
};
void semWait(semaphore s)
{
	s.count--;
    if (s.count < 0) {
    	/* place this process in s.queue */
        /* block this process */
    }
}
void semSignal(semaphore s)
{
	s.count++;
    if (s.count <= 0) {
    	/* remove a process P from s.queue */;
        /* place process P on ready list */;
    }
}

⇒ 함수 호출만 가능하며 함수 수정은 불가능하다.

밑의 코드는 OS 코드이기 때문에 수정할 수 없는 코드이다.
우리가 할 수 있는 것은 semWait, semSignal 함수 호출뿐이다.

S	Ready Queue	Process(CPU)	SystemCall	Blocked Queue
1	C D B	A	semWait

S	Ready Queue	Process(CPU)	SystemCall	Blocked Queue
0	A C D	B	semWait

S	Ready Queue	Process(CPU)	SystemCall	Blocked Queue
-1	A C	D	semSignal	B

S	Ready Queue	Process(CPU)	SystemCall	Blocked Queue
0	B A C	D	semSignal

S	Ready Queue	Process(CPU)	SystemCall	Blocked Queue
0	D B A	C	semWait

S	Ready Queue	Process(CPU)	SystemCall	Blocked Queue
-1	D B	A	semWait	C

S	Ready Queue	Process(CPU)	SystemCall	Blocked Queue
-2	D	B	semWait	C A

S	Ready Queue	Process(CPU)	SystemCall	Blocked Queue
-3		D	semSignal	C A B

S	Ready Queue	Process(CPU)	SystemCall	Blocked Queue
-2	C	D	semSignal	A B

---

Mutual Exclusion Using Semaphore

초기 Semaphore s 의 값은 1로 설정한다.

While문이 사라졌다! OS는 OS 변수 S 값을 근거로 현재 CPU를 잡고 있는 프로세스를 Block 시킬지 말지를 결정한다.

 

여러 프로세스들 중 s가 1일 때 
-> semWait을 실행한 프로세스가 block에 걸리지 않고 통과하여 Critical Section 을 실행할 수 있게 된다

이미 s가 0이 된 이후에

-> semWait를 실행하는 프로세스들은 s < 0 이 되기 때문에 Block이 되어 Blocked Queue로 이동하게 된다

위의 코드에서는 OS가 실행하는 것이기 때문에 기다리는 Process들은 모두 Block 상태가 되어 Blocked Queue로 이동하게 된다.

 

OS는 누가 Critical Section을 진행하는지 안하는지 모른다.

앞의 approach들에서는 프로세스가 Critical Section에 들어갈 수 있게 보장을 해주었다면, 여기서는 아예 Critical Section에 넣어준다.

 

분석

1. Mutual Exclusion O
   ↳ S=1 → 하나만 semWait 통과 가능하다!
2. Busy waiting X
   ↳ semWait 을 통과한 프로세스 이외의 나머지 프로세스들은 Blocked Queue로 이동하게 된다.
   
3. Starvation △
   ↳ Strong Semaphor → 가능성 X , Weak Semaphor → 가능성 O
   
4. Deadlock X
   ↳OS가 s를 보고 동시 진입시, 하나는 진입할 수 있게 된다.
5. Livelock X
   

---

Strong/Weak Semaphore

우리가 선택하는게 아니라 OS가 제공해주는 것이다.

Strong Semaphore ⇒ Starvation 가능성 X

Blocked Queue에 먼저 들어간 Process가 먼저 들어간 순서대로 나온다. (FIFO)

Weak Semaphore ⇒ Starvation 가능성 O

Process가 Blocked Queue에 들어간 순서대로 나오지 않는다.
특정 Process 하나가 Process에서 나오지 않을 수 있다.

1. Blocked Queue는 semaphore 위에서 기다리는 프로세스들을 잡아놓기 위해 사용되어 진다.
   ↳ 어떠한 순서로 프로세스들이 Queue 에서 빼내질까?
2. Strong Semaphore 는 FIFO 를 사용한다.
3. Weak Semaphore 는 queue 에서 프로세스를 제거하는 순서를 구체화하지 않는다.

---

Binary Semaphore Primitives

 Semaphore 값을 0 아니면 1만 설정 가능하다. 작은 group의 문제들을 해결할 수 있다.

semWaitB

Binary Semaphore 에서는 Semaphore 값 S가 0이 되면 무조건 Block을 시킨다.
→ 몇 개가 block 되어 있는지는 알 수 없다.

semSignalB

Queue에서 프로세스를 꺼낼 때 Semaphore 값 S를 보고는 몇개의 프로세스가 Queue에 있는 지 알 수 없다.
⇒ Queue 자체를 확인한다. → isEmpty()

---

Producer/Consumer Problem

1. 보통의 상황:
   • Producer는 데이터를 생성하고 buffer 에 데이터를 놓는다.
   • Consumer 는 buffer에서 item을 가져간다.
   • 오직 한번에 하나의 Producer나 Consumer만 buffer에 접근할 수 있다.
2. 문제:
   Producer가 꽉찬 buffer에 데이터를 추가하지 못하거나 Consumer가 비어있는 buffer에서 데이터를 가져가지 못하는 상황
   
   

Buffer

In

Producer Process가 다음에 Data를 쓸 위치

Out

Consumer Process가 다음에 Data를 읽을 위치

 

Buffer 가 비었을 때?

in == out → 데이터가 빈 것이라고 볼 수 있다.

Buffer 가 꽉찼을 때?

in == out → 데이터가 꽉 것이라고 볼 수 있다.

⇒ 그렇다면 어떻게 Buffer가 비고 꽉찼는지 구분할 수 있을까?
↳ 버퍼가 꽉차기 전에 버퍼 하나를 비워둔다.

⇒ 즉, in == out-1 → 버퍼가 꽉 찼다고 인식한다.

---

Functions in a Bounded Buffer

Producer

• (in + 1) % n == out → Buffer가 가득찬 상황이므로 while문에 걸린다.
• 그 밖의 경우에는 buffer에 데이터 값을 넣고 in값을 하나 증가시킨다.

Consumer

• in == out → Buffer가 빈 상황이므로 while문에 걸린다.
• 그 밖의 경우에는 buffer에서 데이터를 읽고 out 값을 하나 증가시킨다

Busy-Waiting O & Buffer 1개 낭비

좋은 Solution이 아니다. ⇒ Semaphore 를 이용해서 해결하자

---

Bounded Buffer using Semaphores

• semWait : 상황에 따라 프로세스를 기다리게 한다.
• semSignal : 상황에 따라 기다리고 있던 프로세스를 풀어준다.
• Producer Process, Consumer Process, Critical Section 의 Blocked Queue를 하나로 관리하지 않는다.
  ⇒ 3개의 Queue에서 3개의 Semaphore를 관리해야 한다.

Semaphores Logic

1. 프로세스가 기다려야 하는 상황을 생각해야 한다. (n개)
2. n → 같은 Queue에서 기다려도 되는 프로세스들인지 판단하여 필요한 Queue의 개수를 판단한다.

producer()

semSignal(n)의 의미:
버퍼에 데이터가 하나 증가한다. + blocked된 Consumer가 있으면 다시 Ready 상태로 깨워준다.

consumer()

semSignal(e)의 의미:
버퍼에 데이터가 하나 지워진다. + blocked된 Producer가 있으면 다시 Ready 상태로 깨워준다.

즉, Producer와 Consumer는 서로 blocked 된 프로세스를 깨워준다.

 

Semaphore를 사용한 Buffer Logic

세개의 Semaphore 를 사용한다.
→ n, e, s
⇒ Semaphore 값이 어떻게 변하는지 알아야 한다.

s

Critical Section 처리 Semaphore

Critical Section에 여러 프로세스가 들어가려고 대기하면, s 값이 음수가 될 수 있다.

e

초기값: 버퍼의 크기

어느 순간 버퍼에 있는 빈칸의 수

• e > 0: 쓸 수 있는 버퍼의 수
• e <= 0: 버퍼가 꽉차, 버퍼에 데이터를 쓰기 위해 Blocked queue에서 대기 중인 Producer Process의 수

n

초기값: 0

어느 순간 버퍼에 있는 데이터의 개수

• n > 0: 읽을 수 있는 데이터의 수
• n <= 0: 버퍼가 비어있어, 버퍼의 데이터를 읽기 위해 Blocked queue에서 대기 중인 Consumer Process의 수

n+e

버퍼의 크기 (단, n > 0, e > 0 ⇒ blocked queue에 프로세스가 대기 중이지 않은 경우만 성립한다.)

n == 0 → 버퍼가 비었다.
e == 0 → 버퍼가 가득 찼다.

Q. 코드 순서를 변경할 때, 문제가 발생할 수 있다.

/* program boundedbuffer */
const int sizeofbuffer = /* buffer size */;
semaphore s = 1, n = 0, e = sizeofbuffer;
void producer()
{
	while(true) {
    	produce();
        /*순서 교체*/
        semWait(s);
        semWait(e);
        /*순서 교체*/
        append();
        semSignal(s);
        semSignal(n); // 버퍼에 데이터가 하나 증가한다. + blocked된 Consumer가 있으면 다시 Ready 상태로 깨워준다.
    }
}
void consumer()
{
	while(true) {
    	/*순서 교체*/
        semWait(s);
        semWait(n);
        /*순서 교체*/
        take();
        semSignal(s);
        semSignal(e); // 버퍼에 데이터가 하나 지워진다. + blocked된 Procuder가 있으면 다시 Ready 상태로 깨워준다.
        consume();
    }
}
void main()
{
	parbegin(producer, consumer); // 여러개의 producer들과 consumer 들이 함께 작업한다.
}

코드 순서를 변경할 때, 숫자 값의 변화는 없어도, Deadlock이 발생할 수 있다.
semWait(e) ↔ semWait(s) 이나 semWait(n) semWait(s) 를 바꾸는 경우 문제 발생

1. buffer가 어떤 상황일 때 어떤 순서로 producer와 consumer가 도착했을 때 Deadlock이 발생하는가?
   → 2가지 case가 존재한다.
2. 시스템이 Semaphore 제공 X → hardware instruction으로 구현해야 한다.
   → hardware instruction으로 buffer 문제 해결이 가능한가?
   → 가능하다면, 어떻게 구현해야하는가? swap&compare, exchange가 몇 개 필요한가?

---

Monitors

Monitor는 Programming-language construct 이다.

semaphore와 동등한 기능을 제공하고, 제어하기 쉬운 프로그래밍 언어 구조이다. Monitor 는 Semaphore 를 구현해 놓은 module이다.

 

Monitor의 구성요소

• 한 가지 이상의 Procedures
• initialization sequence
• local data

Structure of a Monitor

Monitor

Monitor 자체가 Critical Section이다.
→ 한 번에 하나의 Process만 Monitor에 진입할 수 있다.

 

local data

monitor에 대한 local 이다. → Procedure 입장에서는 전역 변수이다.
즉, 여러 Procedure에서 access할 수 있는 변수이다.
⇒ Monitor 안에서만 access가 가능하다.
⇒ 두 프로세스 동시 접근 불가

Procedure

여러개의 Procedure가 존재한다. (1~k)
Monitor "안" 에서만 실행된다.

어떤 프로세스가 Procedure를 실행시키기 위해서는 monitor 안에 들어와서 실행해야 한다.

cwait(cn)

호출한 프로세스가 바로 Block된다.
→ 바로 Condition Queue로 들어가게 된다.
→ 이후 바깥의 Queue에서 대기 중이던 프로세스가 Monitor로 들어온다.

urgent queue

monitor 안에 Process1가 Procedure1을 실행 중
→ semSignal(c) 호출
→ 새로운 Process가 monitor 안으로 들어오게 됨

이 경우, monitor 바깥의 Queue에서 대기하다가 막 깨어난 프로세스가 우선순위를 갖게 되어 막 들어온 프로세스가 monitor 작업을 진행하게 된다.
원래 monitor안에서 실행 중이던 Process1은 Urgent Queue로 들어가서 block 하게 된다.

→ 이후 바깥에서 막 들어온 프로세스가 작업 진행을 마치면 다시 Process1이 Urgent Queue에서 나와 원래 하던 작업을 실행하고 monitor에서 나가게 된다.
→ 이후 바깥의 Queue에서 대기하던 프로세스 중 하나가 monitor에 들어오게 된다.

---

Synchronization

condition variables

condition variables 는 버퍼가 차있는지 동기화를 해결하기 위해 사용된다.

1. monitor 안에서만 사용 가능
2. Queue 존재
3. Semaphore와 다르다. ↔ condition variable에는 정수값이 존재하지 않는다. Queue만 존재한다.

Monitor Functions

cwait(c)

→ 무조건 이 함수를 호출한 Process를 Block 시킨다.

csignal(c)

→ Queue에 있는 Process 하나를 꺼내서 Monitor 안으로 들여온다. 세마포와 달리, 정수 값이 없기 때문에 Queue가 비었는지 안비었는지 확인할 수 없다.

---

Bounded Buffer Solution Using Monitor

여러개의 Producer와 Consumer들이 존재하는 상황이다.

char x와 같이 데이터를 만드는 작업이나 consume()은 monitor 바깥에서 작업해도 된다.
↔ 하지만, append()와 take() 작업은 반드시 monitor 안에서 작업해야한다.

 

boundedbuffer

데이터를 읽고 쓰기 전 후 monitor 안에서 둘 이상의 Producer가 append를 동시에 하는 것을 막고, 둘 이상의 Consumer가 take를 동시에 하는 것을 막는다.

buffer[N]

N 크기의 버퍼

nextin, nextout

• nextin: 다음에 데이터를 쓸 위치
• nextout: 다음에 데이터를 읽을 위치

count

local data → 버퍼의 데이터가 가득찼는지 안 찼는지를 판단한다.

notfull, notempty

• notfull: producer들이 버퍼가 full 했을 때 block 되는 Queue
• notempty: consumer들이 버퍼가 empty 했을 때 block 되는 Queue

Q. Count 변수를 사용할 수 있는 이유?

↳ monitor안의 local 변수 count를 사용했기 때문이다.

이 monitor 자체가 Critical Section이기 때문이다.
Count는 monitor 안에 있기 때문에 연산이 가능한 것이고, Count를 사용해서 코드가 간단해졌다.

Semaphore에서는 count와 같은 변수를 사용할 수 없다.

 

Q. Monitor에서 Deadlock이 발생하지 않을까?

Semaphore로 Buffer 문제 해결했을 때는 코드 위치를 변경했을 때 Deadlock이 발생했다.

1. semWait(e) ↔ semWait(s) : Critical Section에 먼저 들어간 뒤, 버퍼가 찼는지 확인
2. semWait(n) ↔ semWait(s) : Critical Section에 먼저 들어간 뒤, 버퍼가 비었는지 확인
   
   ↔
   monitor의 경우, Critical Section에 원래 먼저 들어간 뒤, 버퍼가 비었는지 꽉 찼는지를 확인한다.
   ⇒ Deadlock이 발생하지 않는다.

⇒ 왜 순서를 바꿨을 때, Semaphore는 Deadlock이 발생하고 왜 Monitor에서는 Deadlock이 발생하지 않을까?

---

Readers/Writers Problem

 Producer와 Consumer처럼 서로 대칭 작업을 하는 두 종류의 프로세스가 있는 게 아니라, readers와 writers라고 하는 서로 비대칭 적인 작업을 하는 두 종류의 프로세스가 있다.

 

Readers와 Writers는 비대칭 작업 을 한다.

Readers : 동시 작업이 가능하다.
→ 공유 영역 데이터를 "읽기" 만 한다.
↳ 데이터 값 변경 X

Writers : 동시 작업이 불가능하다. (Race condition이 발생할 수 있다.)
→ 데이터를 쓰는 애 X, 데이터를 읽고 계산하고 쓰는 역할을 한다.
↳ 데이터 값 변경 O

• r-r O
• w-w X
• r-w X
• w-r X

Readers have Priority

Reader 하나 들어가면 나머지 reader가 따라 들어온다.

writer()

reader가 1명도 없다고 가정했을 때, writer는 그냥 critical section이다.

semWait(wsem) 을 통과해서 write 작업을 한다. 그 뒤 semSignal(wsem) 을 진행한다.

writer는 한 번에 하나씩만 critical section에 접근할 수 있는 완벽한 critical section 문제이다.

 

Critical Section 이기 때문에 wsem semaphore의 초기값이 1이다.

w1이 Critical Section으로 들어와서 읽고 쓰고 업데이트를 할 때, wsem의 값은 0이 된다. ⇒ Criitcal Section의 문은 닫히게 된다.

이 때 다른 writer 들이 Critical Section에 들어가고 싶어서 대기를 하면, wsem의 값을 하나씩 빼 가며 writer들이 줄을 서게 된다.

이 때, 밖의 wsem Queue에 reader 하나가 Critical Section에 들어가고자 등장한다.
reader 도 당연히 줄을 서야 한다.
↳ writer 가 작업하고 있는 동안에 reader 는 들어갈 수 없다.

이후 두번째 reader 도 Critical Section에 들어가고자 나타났다고 하자.
그런데 이 reader 도 wsem Queue에 줄을 서야할까?
↳ 첫번째 reader 는 당연히 줄을 서야 한다.
⬇
r1이 들어가면 r2는 같이 들어간다.
⇒ 첫번째 reader 만 줄을 서고 나머지 reader 는 줄을 서지 않는다.
최대 1명의 reader 만 줄을 선다. (1개 또는 0개만 줄을 선다.)

어느 순간 wsem Queue를 보면, writer는 여러 명이 줄을 서있고, reader는 한 명만 줄을 서 있는다. 또는 reader가 아무도 없을 수도 있다.

 

⇒ Critical Section 안에 reader 가 들어있다 == wsem Queue 안에는 대기하는 reader 가 존재하지 않는다.

r1이 작업을 완료해서 Critical Section을 나오게 된다.
원래는 Critical Section에서 작업하던 애가 작업을 마치고 나올때는 바깥 Queue에 대기하고 있던 애를 깨워주고 Critical Section에 넣어주고 나가게 된다.

그런데 여기서는 r1이 작업이 끝났다고 해서 대기하고 있던 프로세스를 Critical Section 안에 넣어줄 수 없다.
→ 아직 reader들이 남아있기 때문이다.

Critical Section 안에 들어있는 모든 reader 가 작업을 마칠 때까지 writer 는 Critical Section 에 들어올 수 없다.

reader 의 경우, 첫번째 reader 만 줄을 서기 때문에, 내가 첫번째 reader 인지 알아야 한다.
또, 마지막에 나오는 reader 의 경우에만 semSignal()을 해서 writer 를 깨워서 Critical Section 안에 넣어줄 것이다.
⇒ 내가 몇 번째 reader 인지 알아야 한다.
↳ 이 일을 하는 것이 readCount 이다.

 

readCount

1. 초기값 = 0
2. reader가 한 명씩 올때마다 readCount를 하나씩 증가시킨다.
3. reader가 작업을 마칠때마다 readCount를 하나씩 감소시킨다.

⇒ 내가 몇 번째 reader 인지 알 수 있다.

readCount 자체는 Critical Section 안에서 연산(+, -)를 진행해야 한다.

⇒ Critical Section 이 하나 더 필요하다!

X라고 하는 Critical Section을 하나 더 사용할 것이다.

• readCount를 이 Critical Section 안에 집어 넣는다.
• 새로운 reader가 도착하면 readCount++ 를 Critical Section 안에 들어가서 진행한다
• 작업을 다 마치고 나면, readCount-- 를 Critical Section 안에서 진행한다.

• 내가 read 작업을 하기 전에, readCount++ 를 하는데, Critical Section 에서 작업하기 위해 → semWait(x) 를 통해 Critical Section 진입한 후 readCount 연산을 진행한다.
• 내가 read 작업을 다 마친 후, readCount-- 를 하는데, Critical Section 에서 작업하기 위해 → semWait(x) 를 통해 Critical Section 진입한 후 readCount 연산을 진행한다.

readCount == 1 일 때, 해당 reader 가 첫번째 reader 라는 뜻이므로 wsemWait에 가서 줄을 설 것이다.

readCount == 0 일 때, 해당 reader 가 마지막 reader 라는 뜻이므로 semSignal(wsem)을 통해 wsemQueue에서 대기 중이던 writer 를 Critical Section 안으로 들여보내 줄 것이다.

 

x semaphore 의 기능

• Critical Section 기능 구현: readCount++, readCount-- 를 둘 이상의 reader 가 동시에 실행하면 안되기 때문에 한 번에 하나씩만 readCount 연산을 진행하기 위해 사용하는 semaphore
• 대기하고 있던 reader 들을 줄 세우는 작업을 한다.

r1

• semWait(x) → x = 0
• readCount++ → readCount = 1
• semWait(wsem) → wsem Queue에 대기 → 이미 wsem에는 대기 프로세스가 앞에 있어 문이 닫혀 있는 상태라 통과 X
  ⇒ 다음 코드로 넘어갈 수 없다. ⇒ swmSignal(x)를 해서 reader 들을 blocked 상태에서 풀어줄 수 없다.

r2

• semWait(x) → x = -1
• Critical Section에 들어가지 못한다.

r1이 Critical Section에 들어가지 못했기 때문에 다른 reader 들이 x Queue에서 대기하고 있어도 readCount는 여전히 1이다.
Critical Section에 들어가지 못했기 때문에 readCount 값을 바꿀 수 없다.

reader 가 4명이나 있어도 reader 들 중에 어느 누구도 Critical Section 에 들어가서 data를 읽지 못하는 상황에서는 readCount가 계속 1을 유지한다.

여러명의 reader 가 도착했더라도 하나의 reader 만 wsem Queue에 대기하고 나머지 reader 들은 x Blocked Queue에서 대기하게 된다.

Writer 가 작업을 마침
r1이 드디어 Critical Section 에 들어가게 된다.

• semSignal(x) 를 실행한다.
• x Queue에 대기하고 있던 reader 를 Critical Section으로 넣어준다.
• readCount가 1 증가한다.
• semSignal(x) → 다른 reader 를 깨워준다.
• 늦게온 r5가 먼저 기다리고 있던 w들보다 먼저 실행된다.