[OS] Critical Section Problem H/W Solution - Mutex Locks & Semaphore

앞의 Synchronization과 Critical-Section Problem에서 설명했던 critical section problem의 solution에 대해 알아보자!

Critical section의 기본 조건

1. Mutual Exclusion

어떤 프로세스가 Critical section을 실행 중이라면, 다른 프로세스는 Critical section을 실행할 수 없다!

2. Progress

어떠한 프로세스도 critical section을 실행하지 않고, critical section을 실행하려는 프로세스가 있다면, 다음 critical section을 실행하는 프로세스가 무기한 연기되어선 안 된다!

👉 deadlock 방지

3. Bounded Waiting

각 프로세스는 유한한 횟수의 시도 후에 critical section에 들어갈 수 있어야 한다.

👉 starvation 방지

 

🔍 Hardware based Critical Section Solution

Atomic hardware instructions

Atomic: interrupt가 발생하지 않는다는 것을 의미한다.

TestAndSet

🔍 Mutex Lock & Semaphore

왜 Mutex Lock과 Semaphore를 사용할까 ❔❔

Atomic hardware instruction은 low-level language라서 개발자가 직접 작성하지 않는다.

👉 Atomic hardware instruction을 high-level에서 사용할 수 있게끔하는 툴이 필요함!

Mutex Lock

Mutex Lock은 atomic hardware instruction을 간단하게 사용할 수 있는 API tool이다!

critical section에 들어가고(acquire) 나가는 함수(release) 모두 atomic하게 구현된다.

Example - pthread library

Semaphore

Semaphore 또한 atomic hardware instruction을 간단하게 사용할 수 있는 API tool이다!

Semaphore S는 integer 변수고, 이 S를 수정하는 함수를 wait(S)와 signal(S)이라고 한다.

wait(S)와 signal(S) 두 함수는 atomic instruction이다.

👉 오직 하나의 프로세스만이 Semphore 변수 S를 수정할 수 있다.

 

Semaphore 종류

Binary Semaphore

semaphore 변수 S가 0과 1을 가진다. (== Mutex Lock)

Counting Semaphore

semaphore 변수 S가 이용 가능한 리소스의 수만큼의 값을 가진다.

 

Busy waiting (=spinlock)

Busy waiting: Semaphore를 획득하기 전까지 무한루프를 도는 것을 말한다.

단점: CPU cycle이 낭비된다.

→ 해결 방법: 해당 프로세스를 waiting state로 보내고 다른 프로세스로 context switch한다.

→ 문제점: context switch가 2번 일어남

 

장점: context switch가 일어나지 않아 spinlock 시간이 짧다면 유용함

 

Tradeoff: context switch time vs spinlock time

 

Busy waiting을 피하기 위해 block() 함수와 wakeup() 함수를 사용한다.

 

Semaphore의 문제점

1. Deadlock

두 개의 Semaphore가 1로 초기화되어 있고, 두 프로세스가 두 Semaphore를 원한다고 가정해보자.

P0: S(사용중) → Q(원함)

P1: Q(사용중) → S(원함)

👉 이 경우 P(0)는 wait(Q)에서 lock되고 P(1)은 wait(S)에서 lock된다.

 

2. Priority Inversion

Priority Schduling을 사용하는 CPU에서 Priority Inversion이 일어날 수 있다.

출처: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=kimchoyoungg&logNo=221496188353&view=img_1

1. 가장 우선 순위가 낮은 Task 3이 수행중이다. Task 3은 Resource에 접근하기 위해 Semaphore를 획득 후 실행되는 중이다.

2. 잠시후 Task 1이 들어오고 Task 1의 priority가 더 높기 때문에 Task 3을 중단시키고 Task 1이 실행된다.

3. 이때 Task 1 Resource에 접근하기 위해 Semaphore를 획득하려고 하지만 Semaphore는 Task 3이 획득한 상태이기 때문에 Task1은 중단된다.

4. 다시 Task 3가 실행되고 이후 Task 2가 들어온다.

5. Task 2는 Resource에 접근이 필요하지 않으므로 끝까지 실행된다.

6. 이후 Task 3가 실행되고 Task 3가 Semaphore를 릴리즈한 후에야 Task 1이 실행된다.

 

👉 이와 같이 priority가 가장 높음에도 Semaphore를 얻지 못해 priority가 더 낮은 프로세스가 먼저 수행되는 Priority Inversion이 발생한다.

 

해결 방법

Prority-inheritance protocol: Priority가 낮은 프로세스가 Semaphore를 획득하여 수행하고 있고 priority가 높은 프로세스가 이를 기다린다면 priority가 낮은 프로세스의 priority를 기다리는 프로세스의 priority로 변경하는 방법을 사용한다.

 

3. Incorrect user of Semaphore

Semaphore를 high-level에서 개발자가 직접 사용할 수 있기 때문에 잘못 사용하는 경우가 발생한다.

signal(S) -> wait(S)

👉 사용할 수 있는 Semaphore의 수보다 더 많은 Semaphore를 풀기 때문에 mutual exclusion을 보장할 수 없음

wait(S) -> wait(S)

👉 Semaphore를 가지고 있는 프로세스가 릴리즈를 하지 않아 아무도 Semaphore를 획득할 수 없음
→ progress를 보장할 수 없음 (deadlock)

wait(S) 생략 or signal(S) 생략 or 둘 다 생략

👉 둘 다 생략할 경우: race condition 발생

👉 wait(S)를 생략할 경우: mutual exclusion 위배

👉 signal(S)를 생략할 경우: progress 위배