운영체제 Chapter5 Concurrency : Mutual Exclusion and Synchronization 통합

Jimin·2023년 4월 16일

chapter5 운영체제

Operation System

목록 보기

17/34

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-2-3-4 → 400 ✅
1-3-2-4 → 300
1-3-4-2 → 200
3-4-1-2
3-1-2-4
3-1-4-2

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

Race Condition

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

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

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

Multiple-Processes or Multiple-Threads READ and WRITE data items.
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가지 방법이 존재한다.

소프트웨어적 Approach
하드웨어 insturction 도움 Approach
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 먼저 실행

분석

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

분석

해당 코드는 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을 실행하겠다는 의지를 보여준다.

분석

해당 코드는 Mutual Exclusion을 보장한다.
하지만, 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을 실행하게 된다.

분석

Mutual-Exclusion 지켜진다.
↳ 내 flag가 true이고, 상대편 flag가 false인 거 확인하고 Critical Section을 실행하게 된다. 결국 while문을 빠져나올 때는 상대편 flag가 false일 때만이다.
DeadLock 은 일어나지 않는다.
↳ 둘 다 while문을 돌 때 상대 flag가 바뀔 가능성이 존재한다.
하지만, 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이 실행되게 된다.

🌟 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가 flase인 거 확인한 후 Critical Section을 실행하게 된다.

Deadlock

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

Livelock

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

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

→ 가능하다.
P1가 flag가 false인한, 가능하다.

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

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

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. Multual Exclusion X?

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

모순만으로는 증명이 어렵다.
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
Ciritical Section 실행	flag[0]이 false이거나 turn == 1
	Ciritical Section 실행

3. Deadlock X?

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

4. Livelock X?

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

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

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

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

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

Process Interaction(상호작용) and Control Problems

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

Process Interaction

서로 Resource를 차지하려고 경쟁하는 상황
(Competition among processes for resources)
데이터를 공유하는 상황

↳ 공유 메모리 공간에, 또는 파일에 있는 데이터를 서로 다른 프로세스들이 서로 읽기, 쓰기 하며 데이터를 공유한다.
(Cooperation among processes by sharing)
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 관리가 제일 중요하다.
이건 무조건 지켜야 한다.

Requirements for Mutual Exclusion

Mutual Exclusion

Mutual Exclusion : 전체 코드가 아닌, Critical Section code 가 한 번에 하나의 프로세스만 실행할 수 있도록 하는 것.

Mutual Exclusion 은 어떠한 경우에도 지켜져야 한다.
오직 하나의 프로세스만 Critical Section 의 자원에 접근할 수 있다.

→ Critical Section Code 가 아닌 코드는 막 섞여서(interleaving, overlapping) 실행되어도 상관 없다.

Critical Section Code 와 Non-Critical Section Code 가 섞여 실행되는 것도 상관 없다.
⇒ Non-Critical Section Code 와 Critical Section Code 가 서로 때문에 정지하는 일은 없어야 한다.

Dekker와 Peterson의 알고리즘은
DeadLock X
Starvation X
LiveLock X

→ 하지만 DeadLock, Starvation, LiveLock이 발생해도 사용해야하는 경우가 존재한다.

Critical Section 을 사용하는 다른 프로세스가 없을 때, Critical Section 에 대한 액세스를 지연시켜서는 안 된다.

(Solution 1처럼)

프로세스의 상대적 속도 가정 의미 X

프로세스의 상대적 속도를 가정하면 안된다. (Solution4와 같이)
↳ 해법 X, 프로세스는 CPU가 있는지 없는지 신경쓰지 않는다.
⇒ 얼마나 기다릴지 모르기 때문에 몇 초를 기다린다는 말은 의미가 없다.

몇초 기다릴지 각 프로세스마다 부여 받아도, Ready Queue로 들어가게 되면,
원래 몇초 기다릴지 부여 받은 초보다 더 오래 기다릴 수도 있고,
먼저 CPU를 받은 프로세스가 먼저 다시 Running 하게 된다.

프로세스의 개수 가정 의미 X

Dekker와 Peterson 알고리즘은 2개의 프로세스 일 때를 가정한 것이다.
⇒ General한 Solution은 이러한 가정을 두면 안된다.

프로세스는 Critical Section 안에 유한한 시간 동안만 남아있는다.

무한루프 돌면 안된다.

한 번에 하나의 프로세스만을 실행할 건데, DeadLock X, LiveLock X, Starvation X, 어떠한 가정도 X
⇒ 문제 해결 방안 찾기!

Approaches for Mutual Exclusion

Software approaches

Dekker's algorithm
Peterson's algorithm

Hardware approaches
An approaches using the special-purpose machine instruction

Compare_and_swap instruction
Exchange instruction

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

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

Semaphore
monitor

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

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

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

Compare&Swap Instruction
(Hardware Instruction)

함수 형태이다.
인자가 3개 있다.
word 포인터 인자가 하나 있다. (memory location을 가르킨다.)
Compare&Swap은 밑에처럼 코드로 나타내져있지만, 사실 코드가 아니다. 따라서 호출만 가능하고 수정은 불가능한 코드이다. (exchange도 마찬가지)

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

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

Compare&Swap Instruction 의 특징

Compare&Swap 은 atomic instuction이다. (Hardware instruction)
→ 하드웨어 instruction 이기 때문에 인터럽트 가 발생하지 않는다.
↳ 이유: 하나의 instruction 이기 때문이다.

⇒ 위의 코드 중간에서 끊기는 상황은 발생하지 않는다.

⇒ instruction 은 Fetch stage + Execution stage 를 거치고 나서야 Interrupt stage 를 거치게 된다.

Compare&Swap Instruction 의 실행 시간 동안,
그 공간을 참조하는 모든 instruction 들은, 메모리 공간(위의 코드에서 word 가 가르키는 메모리 영역) 접근이 blocked 된다.

10개의 CPU 가 있을 때,
Process 개수 제한 없이 10개의 CPU를 이용하여 동시에 실행
→ 이 중 하나의 Process가 Compare&Swap 을 실행하고 있다면, 다른 Process는 Compare&Swap 을 실행할 수 없다.
⇒ Compare&Swap 은 하나의 Process 만 가능하다.

⇒ Compare&Swap 은 Interleaving , Overlapping 이 불가능하다.

Compare&Swap 진행 단계

Step1

처음 bolt 값은 0으로 설정된다.

n개의 프로세스가 메소드 P를 동시 실행한다.

Step2

여러 프로세스 중 P2가 먼저 메소드 P를 실행해서 compare_and_swap while문을 실행한다.

Step3

P2는 bolt 값(0) 과 0을 비교하는데, bolt값이 0이었기 때문에 bolt 값을 1로 바꾸고 0을 반환한다. while문 조건에 거짓이기 때문에 P2는 while문을 빠져나와 Critical Section 을 실행한다.

이제 다른 프로세스들은 bolt에 접근해 compare_and_swap while문을 돌려도 bolt값(1)과 0이 이제 다르기 때문에 bolt 값을 바꾸지 않고 1을 반환한다.
while문을 보면, 1과 같을 때 참이기 때문에 while문을 빠져나오지 못한다.

compare_and_swap while문은 Critical Section 전에 하나의 Process만 빠져나올 수 있다.

Step4

P2가 Critical Section을 실행하고 나면, bolt 값을 다시 0으로 바꿔준다.
이후 다음에 CPU를 차지한 프로세스가 compare_and_swap 을 실행하여 while문을 통과 한 다음 Critical Section에 진입하게 된다.

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;
}

Exchange Instruction 의 특징

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

⇒ Exchange 은 Interleaving , Overlapping 이 불가능하다.

Exchange 진행 단계

현재 코드에는 문제가 없지만, critical section과 non-critical section을 다르게 배열하면, 문제가 발생할 수 있다.

Step1

처음 bolt 값은 0으로 설정된다.

n개의 프로세스가 메소드 P를 동시 실행한다.

bolt는 공유 변수이고, key 값은 지역 변수이다.
초기 key 값은 1로 설정된다.

Step2

여러 프로세스 중 P2가 먼저 메소드 P를 실행해서 Exchange do-while문을 실행한다.

Step3

P2는 bolt 값(0) 과 key2 의 값(1) 을 교환한다.
bolt 값은 1이되고, P2의 key2 값은 0이 된다.
key2의 값이 0이 아니므로 while문을 통과하게 되어 Critical Section 을 실행하게 된다.

이제 다른 프로세스들은 bolt에 접근해 Exchange do-while문을 돌려도 bolt값(1)과 keyi 값(1)이 같기 때문에 bolt 값과 key 값을 바꾸어도 서로 같은 값 (1) 을 바꾸게 된다.
while문을 보면, key 값이 0아 아닐 때 참이기 때문에 key 값이 1이므로 while문을 빠져나오지 못한다.

⇒ Exchange do-while문은 Critical Section 전에 하나의 Process만 빠져나올 수 있다.

Step4

P2가 Critical Section을 실행하고 나면, bolt 값을 다시 0으로 바꿔준다.
이후 다음에 CPU를 차지한 프로세스가 Exchange 을 실행하여 do-while문을 통과 한 다음 Critical Section에 진입하게 된다.

Hardware Mutual Exclusion

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

장점

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

단점

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

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

Semaphore

Semaphore란?

프로세스들 간의 신호 전달에 사용되는 integer value이다.

⇒ Semaphore는 구조체 변수이다. (an integer + a queue)

Semaphore는 OS가 제공하는 Tool이다.

공유 메모리 변수 "bolt"

변수 bolt 는 공유 메모리 값으로 연산이(+, -) 가능하다. ⇒ 변화 가능 O

OS 변수 "S"

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

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

System-Call

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

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

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

Semaphore에 대한 System-Call은 딱 3가지만 존재한다.

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 → BlockedQueue
→ ProcessC → semSignal → s <= 0 → ProcessA → ReadyQueue
→ semSignal 다음 코드를 실행한다.

Semaphore Primitives

동기화 문제
↳ 내가 건드릴 수 있는 코드인가?
⇒ 내 application code X, OS code O
⇒ 함수 호출만 가능하며 함수 수정은 불가능하다.

밑의 코드는 OS 코드이기 때문에 수정할 수 없는 코드이다.
우리가 할 수 있는 것은 semWait, 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 */;
    }
}

semWait(semaphore s)

s 변수의 값을 줄인다.
s 변수의 값이 0보다 작은지 확인하고, 0보다 작을 경우, block을 하여 blocked queue로 옮긴다.

semSignal(semaphore s)

s 변수의 값을 증가시킨다.
s 변수의 값이 0보다 작거나 같은지 확인하고, 0보다 작거나 같을 경우 blocked queue에 있던 프로세스를 하나 꺼내 ready queue로 옮겨 실행할 수 있도록 만들어 준다.

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 이상의 값으로 설정해주어야 한다.

Example of Semaphore Mechanism

S Ready Queue Processor(CPU) System Call Blocked Queue
1 C D B A semWait
S Ready Queue Processor(CPU) System Call Blocked Queue
0 A C D B semWait
S Ready Queue Processor(CPU) System Call Blocked Queue
-1 A C D semSignal B
S Ready Queue Processor(CPU) System Call Blocked Queue
0 B A C D semSignal
S Ready Queue Processor(CPU) System Call Blocked Queue
0 D B A C semWait
S Ready Queue Processor(CPU) System Call Blocked Queue
-1 D B A semWait C
S Ready Queue Processor(CPU) System Call Blocked Queue
-2 D B semWait C A
S Ready Queue Processor(CPU) System Call Blocked Queue
-3 D semSignal C A B
S Ready Queue Processor(CPU) System Call Blocked Queue
-2 C D semSignal A B

S	Ready Queue	Processor(CPU)	System Call	Blocked Queue
1	C D B	A	semWait

S	Ready Queue	Processor(CPU)	System Call	Blocked Queue
0	A C D	B	semWait

S	Ready Queue	Processor(CPU)	System Call	Blocked Queue
-1	A C	D	semSignal	B

S	Ready Queue	Processor(CPU)	System Call	Blocked Queue
0	B A C	D	semSignal

S	Ready Queue	Processor(CPU)	System Call	Blocked Queue
0	D B A	C	semWait

S	Ready Queue	Processor(CPU)	System Call	Blocked Queue
-1	D B	A	semWait	C

S	Ready Queue	Processor(CPU)	System Call	Blocked Queue
-2	D	B	semWait	C A

S	Ready Queue	Processor(CPU)	System Call	Blocked Queue
-3		D	semSignal	C A B

S	Ready Queue	Processor(CPU)	System Call	Blocked Queue
-2	C	D	semSignal	A B

Mutual Exclusion Using Semaphore

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

여러 프로세스들 중 s가 1일 때 semWait을 실행한 프로세스가 block에 걸리지 않고 통과하여 Critical Section 을 실행할 수 있게 된다.
이미 s가 0이 된 이후에 semWait를 실행하는 프로세스들은 s < 0 이 되기 때문에 Block이 되어 Blocked Queue로 이동하게 된다.

↳ 앞에서는 Process가 Critical Section에 진입하면 다른 Process 들은 While 문에서 기다려야 했지만, 위의 코드에서는 OS가 실행하는 것이기 때문에 기다리는 Process들은 모두 Block 상태가 되어 Blocked Queue로 이동하게 된다. (프로세스를 Block 시키는 것은 OS만 가능하다.)

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

Critical Section을 마친 프로세스는 semSignal을 실행해 s 값을 1증가시키고 아직 s 값이 0보다 작거나 같다면 Blocked Queue 에 있던 프로세스 중 하나를 꺼내 Ready Queue에 보내 Running 상태가 될 수 있게 해준다.

Block상태에서 Ready상태를 거쳐 다시 Running 상태가 된 프로세스는 semWait 다음 줄인 Critical Section을 실행할 수 있게 되고,
실행한 이후에는 다시 semSignal을 실행시켜 다른 프로세스가 Critical Section을 실행할 수 있도록 해준다.

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

Mutual Exclusion O

S=1 → 하나만 semWait 통과 가능하다!

Busy Waiting X

semWait 을 통과한 프로세스 이외의 나머지 프로세스들은 Blocked Queue로 이동하게 된다.

Starvation △

Strong Semapho → 가능성 X
Weak Semapho → 가능성 O

Deadlock X

OS가 semapho 변수를 보고 동시 진입시, 하나는 진입할 수 있게 된다.
그러나 초기 s 값이 0 으로 되어 있으면, 아무도 들어가지 못하게 된다.
혹은 초기 s 값이 10으로 되어 있으면, 동시에 10개의 프로세스가 Critical Section을 실행할 수 있게 된다.
⇒ s의 초기값 설정이 중요하다.

Strong/Weak Semaphore

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

Strong Semaphore

Blocked Queue에 먼저 들어간 Process가 먼저 들어간 순서대로 나온다.
⇒ Starvation 가능성 X

Weak Semaphore

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

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

Mutual Exclusion Using Semaphore(2)

Semaphore

semWait : Process 를 Block 시킬 수 있는 명령어이다.
semSignal : 내가 아니라 Queue에 있는 프로세스를 Ready로 옮겨 실행할 수 있게 해준다.

Semaphore는 Critical Section뿐 아니라, 많은 동기화 문제에 사용된다.
↳ 특히 Critical Section을 다룰 때는 무조건 초기 세마포 변수 값을 1로 설정해야 한다!

Race Condition : 실행 순서에 따라 결과가 어떻게 될지 모르는 상황
→ 여러 프로세스가 Critical Section 을 동시 접근할 때 발생한다.

어느 위치에 semWait과 semSignal를 사용할지 잘 선택해야 한다.

Mutual Exclusion Using Semaphore

하늘색 네모 부분은 해당 프로세스가 Blocked Queue 에서 대기하고 있다는 의미이다.

세마포 방과 문에 비유하기

step1

여러 프로세스들이 Critical Section에 진입하려고 문에 서 있다고 가정해보자.

step2

Process 2가 먼저 문을 열고 Critical Section에 들어가서 문을 닫아버리고 s 값을 0으로 바꾼다.
이후 접근하는 프로세스들은 s 값이 음수가 되기 때문에 Blocked Queue에 들어가서 대기하게 된다.

s <= 0 : 문이 닫힌 상태
s > 0 : 문이 열린 상태

step3

Process2가 Critical Section 실행을 마친 후,
나갈 때 semSignal 명령어를 통해 대기하던 프로세스를 문 안으로 데려온다.
s > 0 (s == 1) 이되면, 문이 다시 열리는 것을 의미한다.

Semaphore는 좋은 도구인가?

Mutual Exclusion O
Deadlock X
Livelock X
Busy-Waiting X
Starvation △
- Strong Semaphore X (Queue 순서대로 진행)
- Weak Semaphore O

Binary Semaphore Primitives

지금까지 진행했던 Semaphore 는 Counting Semaphore 이다.
Binary Semaphore는 Semaphore 값을 0 아니면 1만 설정 가능하다.

Binary Semaphore는 작은 group의 문제들을 해결할 수 있다.

semWaitB

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

semSignalB

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

Buffer

Producer Process

데이터를 생성해서 Buffer에 쓴다.

Consumer Process

Buffer에서 데이터를 읽어서 작업한다.

Producer Process와 Consumer Process는 한 번에 하나만 Buffer에 접근할 수 있다!

위의 버퍼를 I/O Buffer라고 가정하자.
Memory Data → I/O buffer → I/O Device 출력

두 Producer Process 가 동시에 버퍼에 접근하여 데이터를 쓸 수 있고, 두 Concumer Process가 동시에 버퍼에 접근하여 데이터를 출력할 수 있다.
이렇게 프로세스가 동시에 버퍼에 접근하는 문제는 Critical Section 해결 방법과 동일하게 해결할 수 있다!

동시 buffer 접근 문제

Critical Section 해결 방법과 동일하게 해결할 수 있다!

Buffer가 비어 있는 문제

Consumer Process 가 Buffer에서 데이터를 가져갈 수 없다.

Buffer의 크기 제한

Producer Process 가 Buffer에 데이터를 쓸 수 없다.

⇒ Buffer의 크기 문제를 해결해야 한다!

Producer/Consumer Problem

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

Bounded Buffer

처음엔 버퍼가 비어 있다.

In

Producer Process가 다음에 Data를 쓸 위치

Out

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

in > out

out > in

위의 그림에서 아래 그림으로 바뀌는 동안, Producer 는 b[5] 부터 한바퀴를 돌아 b[2]까지 데이터를 쓴 것이고, Consumer는 b[4]까지 데이터를 읽은 것이다.

Buffer 가 비었을 때?

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

Buffer 가 꽉찼을 때?

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

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

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

Funcions 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 : 상황에 따라 기다리고 있던 프로세스를 풀어준다.

프로세스가 기다려야 하는 상황 3가지

Producer Process의 입장에서 buffer가 가득 찼을 때
Consumer Process의 입장에서 buffer가 비었을 때
Producer Process와 Consumer Process가 Critical Section에 진입할 때 → 한 번에 하나만 접근해야하므로 기다려야 한다.

Producer Process, Consumer Process, Critical Section 의 Blocked Queue를 하나로 관리하지 않는다.
⇒ 3개의 Queue에서 3개의 Semaphore를 관리해야 한다.

Semaphores Logic

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

Semaphore를 사용한 Buffer 관리 코드

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

producer()

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

consumer()

semSignal(e)의 의미:
버퍼에 데이터가 하나 지워진다. + blocked된 Procuder가 있으면 다시 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) 를 바꾸는 경우 문제 발생

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

Semaphore를 사용할 때

어떤 상황에서 프러세스가 기다려야 하는가?
프로세스가 몇 개의 Queue로 나뉘어져 관리가 되어야 하는가?
→ Queue의 개수를 결정해야 한다.
Queue의 수만큼 Semaphore를 생성한다.
→ Semaphore 1개당 Queue 1개

Semaphore에는 딱 두가지 함수만이 존재한다.
→ 이 두가지 함수만으로 다양한 동기화 문제를 해결할 수 있다.

semWait
semSignal

Bounded Buffer using Semaphores

위의 코드에서 세마포는 3가지가 존재한다.

s → Queue에 Produce와 Consumer가 섞여서 들어간다.
n → Queue에 Consumer만이 들어간다.
e → Queue에 Producer만이 들어간다.

Producer Process:

Buffer가 가득 찼는지 확인
Critical Section 진입 가능 여부 확인
Buffer에 데이터 쓰기
Critical Section 깨워주기
Consumer 깨워주기

Consumer Process:

Buffer가 비었는지 확인
Critical Section 진입 가능 여부 확인
Buffer에서 데이터 읽기
Criitcal Section 깨워주기
Producer 깨워주기

Monitors

OS는 Semaphore를 제공해서 우리가 Semaphore를 이용하여 여러 문제를 해결할 수 있게 해준다.
↔ 하지만, 잘못 사용하게 되면 Deadlock이 발생할 수 있다.

Monitor는 Programming-language construct 이다.

semaphore와 동등한 기능을 제공하고, 제어하기 쉬운 프로그래밍 언어 구조이다.

Programming-language construct

Programming-language construct 는 라이브러리 함수이다.

File에서 Data를 다룰 때 System Call에는 오로지 READ, WRITE만 존재한다.
하지만, READ, WRITE는 데이터 타입 구분을 하지 않는다.
⇒ 쉽게 시스템을 사용할 수 있게 하기 위해(입출력하기 위해) Buffering와 Printf, Scanf 와 같은 라이브러리를 이용한다.

이와 같이 우리가 바로 Semaphore 를 사용하게 되면, 어렵기도 하고 잘못 사용하면 Deadlock 이 발생할 수 있기 때문에 Monitor 라는 모듈 라이브러리를 사용하는 것이다.

간단히 말해서 Monitor 는 Semaphore 를 구현해 놓은 module 이다.

Monitor 는 software module 이다.

Monitor의 구성요소

한 가지 이상의 Procedures
initialization sequence
local data

Structure of a Monitor

Monitor

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

ex) Process1이 Procedure1을 실행하고 싶어하고, 
Process2가 Proedure2를 실행하고 싶어서 동시 호출해도, 
Monitor 안에는 하나의 Process만 진입할 수 있고 
다른 프로세스들은 모니터 밖의 Queue에서 대기하게 된다.

local data

monitor에 대한 local 이다.
→ Procedure 입장에서는 전역 변수이다.
즉, 여러 Procedure에서 accsee할 수 있는 변수이다.
⇒ 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에 들어오게 된다.

Characteristics

Local data variables are accessible only by the monitor
↳ Monitor들은 local data variable에 한 번에 하나만 접근할 수 있다.
Process enters monitor by invoking one of its procedures
↳ Process가 Procedure를 호출하면 monitor안으로 들어 오게 되고, procedure에서 연산을 진행하게 된다. 밖에서는 연산이 불가능하다.
⇒ Mutual Exclusion 이 지켜진다.
Only one process may be executing in the monitor at a time (mutual exclusion facility)
↳ 오직 하나의 프로세스만이 monitor를 실행할 수 있다.
⇒ Mutual Exclusion facility

Synchronization

condition variables

Synchronisation achieved by condition variables within a monitor
↳ only accessible by the monitor.

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

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

Monitor Funtions

cwait(c)

Suspend execution of the calling process on condition c
→ 무조건 이 함수를 호출한 Process를 Block 시킨다.

csignal(c)

Resume execution of some process blocked after a cwait on the same condition
→ Queue에 있는 Process 하나를 꺼내서 Monitor 안으로 들여온다. 세마포와 달리, 정수 값이 없기 때문에 Queue가 비었는지 안비었는지 확인할 수 없다.

Bounded Buffer Solution Using Monitor(2)

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

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

Bounded Buffer Solution Using Monitor

boundedbuffer

monitor boundedbuffer;

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

buffer[N]

char buffer [N]

N 크기의 버퍼

nextin, nextout

int nextin, nextout;

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

count

int count;

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

notfull, notempty

cond notfull, notempty;

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

초기값

buffer initially empty

nextin = 0
nextout = 0
count = 0

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

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

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

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

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

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

semWait(e) ↔ semWait(s) : Critical Section에 먼저 들어간 뒤, 버퍼가 찼는지 확인
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

A data area is shared among many processes

Some processes only read the data area, some only write to the area

Conditions to satisfy:

Multiple readers may read the file at once.
Only one writer at a time may write
If a writer is writing to the file, no reader may read it.
→ 만약 writer가 file에 쓰고 있다면, reader는 동시에 file을 읽을 수 없다.

Readers have Priority

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

main()

readcount 공유변수 1개가 있고, 값을 0으로 초기화한다.
reader, writer가 여러명 존재하며 동시에 작업을 시작할 수 있다.

비대칭적인 작업 ⇒ 이전과 달리 reader() 와 writer() 의 코드가 다른 것을 확인할 수 있다.

writer()

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

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

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

이 Ciritical Section 안에는 Data라고 하는 Buffer 가 있다.
wsem seamaphore가 지키고 있는 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가 아무도 없을 수도 있다.

만약 reader 가 자신의 차례를 기다리다가 차례가 되어 Critical Section 안으로 들어왔다고 가정하자.
밖에는 여전히 Writer 들이 wsem Quque에서 대기를 하고 있는데, 만약 이 때 새로운 reader 가 등장하게 되면 이 reader는 대기할 필요가 없다.

그냥 같이 들어가서 READ 작업을 하면 된다.

위와 같이 여러명의 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

초기값 = 0
reader가 한 명씩 올때마다 readCount를 하나씩 증가시킨다.
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에 가서 줄을 설 것이다.

if(readCount == 1) semWait(wsem);

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

if(readCount == 0) semSignal(wsem);

reader들이 줄 서 있는 곳?

첫 번째 reader 만 wsemQueue에 줄을 서는데, 그렇다면 나머지 reader 들은 어디에서 줄을 설까?
→ x 라고 하는 semaphore Queue에서 줄을 선다.

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들보다 먼저 실행된다.

정리

writer

writer 는 기본적으로 Critical Section 이다.
wsem 을 이용해서 기본 Critical Section 을 구현한다.

reader

reader 의 경우, 첫 번째 reader 만 wsem 에 대한 semWait(wsem)을 실행한다.
마지막 reader 만 wsem 에 대한 semSignal(wsem)을 실행한다. → 다음 writer 를 Critical Section 으로 넣어준다.
몇 번째 reader 인지 세야 한다. → 이 작업은 readCount 가 한다.
readCount 자체는 Critical Section 으로 구현했다.
semaphore x 의 역할
- readCount 동시 접근 제한
- 다른 reader 들이 대기하는 곳

Jimin

https://github.com/Dingadung

이전 포스트

운영체제 Chapter5 Concurrency : Mutual Exclusion and Synchronization - 4월 13일 목요일

다음 포스트

운영체제 Chapter5 Concurrency : Mutual Exclusion and Synchronization 통합

Operation System

Multiple Processes

1. Multiprogramming

2. Multiprocessing

3. Distributed Processing

🌟Concurrency🌟

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

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

Concurrency

Concurrency Control

A Simple Example

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

Race Condition

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

Critical Section

정리

Mutual Exclusion:SoftWare Approaches 1

공유 변수

분석

Mutual Exculsion

Mutual Exclusion:SoftWare Approaches 2

공유 변수

분석

Mutual Exclusion:SoftWare Approaches 3

분석

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

DeadLock

Mutual Exclusion:SoftWare Approaches 4

분석

LIVELOCK

Dekker’s Algorithm

Questions

Q. Multual Exclusion이 걸리는가?

Q. DeadLock이 걸리는가?

Q. LiveLock이 걸리는가?

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

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

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

🌟 Mutual Exclusion: Software Approach (3) 🌟

🌟 Mutual Exclusion: Software Approach (4) 🌟

Dekker’s Algorithm

turn

안쪽 while문

Mutual Exclusion

Deadlock

Livelock

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

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

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

Peterson's Algorithm

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

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

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

2. Multual Exclusion X?

3. Deadlock X?

4. Livelock X?

Process Interaction(상호작용) and Control Problems

Process Interaction

Control Problem

Mutual Exclusion

CPU가 3개인 SMP Machine

Deadlock

Starvation

Requirements for Mutual Exclusion

Mutual Exclusion

Critical Section 을 사용하는 다른 프로세스가 없을 때, Critical Section 에 대한 액세스를 지연시켜서는 안 된다.

프로세스의 상대적 속도 가정 의미 X

프로세스의 개수 가정 의미 X

프로세스는 Critical Section 안에 유한한 시간 동안만 남아있는다.

Approaches for Mutual Exclusion

Software approaches

Hardware approachesAn approaches using the special-purpose machine instruction

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

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

Compare&Swap Instruction(Hardware Instruction)

Compare&Swap Instruction 의 특징

Compare&Swap 진행 단계

Step1

Step2

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

Mutual Exclusion:
SoftWare Approaches 1

Mutual Exclusion:
SoftWare Approaches 2

Mutual Exclusion:
SoftWare Approaches 3

Mutual Exclusion:
SoftWare Approaches 4

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

Hardware approaches
An approaches using the special-purpose machine instruction

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

Compare&Swap Instruction
(Hardware Instruction)

Exchange Instruction
(Hardware Instruction)