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

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)

• 함수 형태이다.
• 인자가 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;
}

1. word 와 testval 의 값이 같을 경우
   → word의 값을 newval의 값으로 변경한다.

2. word 와 testval 의 값이 다를 경우
   → word의 값 변경하지 않는다.

3. 항상 oldval, word에 들어 있던, 원래의 값이 return 된다.

Compare&Swap Instruction 의 특징

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

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

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

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

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

Exchange Instruction 의 특징

1. Exchange는 atomic instruction이다. (Hardware instruction)
   ↳ 하나의 instruction 이기 때문에 중간에 interrupt가 발생하지 못한다. (fetch, execution stage 까지 진행한 후 interrupt 가 진행된다.)

2. 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

장점

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

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)

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

semSignal(semaphore s)

1. s 변수의 값을 증가시킨다.
2. 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

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

   
   

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

   
   

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

   
   

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

   
   

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

   
   

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

   
   

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

   
   

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

   
   

9. 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

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

---

Mutual Exclusion Using Semaphore(2)