[OS] Chap06. Synchronization Tools

해당 글은
경희대학교 조진성, 허선영 교수님의 강의 자료 및 내용을 정리한 글입니다
개인적으로 공부하며 작성된 글이라 잘못된 부분이 있을 수 있습니다!
오류가 있다면 알려주세요

 

 

 

Background

Synchronization이 왜 필요할까요? 

Process가 concurrent하게 실행될 수 있기 때문입니다. 여러 프로세스가 하나의 core에 의해 관리되는데, 번갈아가면서 실행되기 때문이죠

이때 여러 프로세스가 공유하는 메모리에 접근하면서, Data inconsistency가 문제가 될 수 있는 것입니다

 

 

▶ Race Condition

두 자동차가 race를 벌이듯이, 공유되는 data를 제어하지 않고 마구잡이로 사용하는 경우,

프로그램의 실행 결과가 instrction 실행 순서에 따라서 달라지는 Race condition이 발생합니다

 

 

▶ Critical Section

프로세스 간에 공유되는 자원이 있는 경우, 하나의 프로세스만 열어야하는 section이 존재합니다.

다른 프로세스가 동시에 연다면 Race condition이 발생하기 때문이죠

따라서 Entry section에서 permission을 받아야 접근할 수 있고, 그렇지 않을 경우 permission이 떨어질 때까지 대기합니다

 

 

 

 

Critical Section Problem

$n$개의 Processes 존재 ${P_0, P_1, ... P_(n-1)}$

• Mutual Exclusion: 오직 하나의 Process만이 critical section을 실행할 수 있음
• Progress: Critical Section을 실행하고 있는 process가 없는 경우, 빠르게 실행합니다
• Bounded Waiting: Starvation이 일어나서는 안됩니다. 모든 process가 Critical section에 접근할 수 있어야 합니다

 

 

▶ Based Solution - Interrupt

​Critical section에 입장할 때, Disable interrupt하고

나갈 때, Enable interrupt 합니다

 

👎🏼 문제점

• Critical section이 과하게 길어지는 경우, 하나의 process가 독점하게 되기 때문에 Starvation이 발생할 수 있음
• 따라서 Single core에서만 적용할 수 있는 개념
• Preemptive vs. Nonpreemptive kernels: 요즘은 성능의 이유로 preemptive로 구현합니다

 

 

Software Solution

▶ One Software Solution

Load와 Store는 atomic합니다. 한 큐에 처리된다는 의미

이는 Turn이 돌아오는 경우에만 실행할 수 있음

Process i의 경우

위 코드는 Process $i$의 경우이고, turn == j일 때 무한 loop를 돌면서 entry에서 대기합니다

Mutual exclusion 는 만족하네요 → Turn 변수가 이를 수행하는 중

 

👎🏼 문제점

• Progress를 만족하지 못합니다: Process $i$가 너무 빠른 경우, Critical section을 실행하고 turn를 j에게 넘겨줍니다. 이때 j의 속도가 느리면 turn을 바로 넘겨주지 못하는 것임\

 

▶  Peterson’s Solution ⭐

위 솔루션과 같이 Turn 변수를 공유하되, Flag[2]를 하나 더 둡니다

다른 점은, 

• code가 순서대로 실행된다는 전제가 필요합니다
• $j$가 remainder section을 실행하고 있을 때, $i$가 critical section에 들어갈 수 있도록 상대 process가 어떤 section을 실행하고 있는지 확인할 수 있습니다
• 프로세스 $j$가 준비되지 않았거나, Turn이 순서가 온다면 들어갑니다

따라서 Mutual exclusion, Progress, Bounded waiting 모두 만족됩니다

그러나,, 실제 컴퓨터 구조에서는 이와 같이 실행되지 않습니다. 코드가 순서대로 실행되지 않걸랑요

Processor가 성능 상의 이유로 instructions의 순서를 바꿔버릴 수도 있어요.

 

 

 

Hardware Solution

▶ Memory Barriers

Process가 지원하는 기능이고, 순서를 다시 재정렬하는 것입니다

Memory_barrier() 앞 뒤로 instruction의 순서를 바꿀 수 없음

 

 

▶ Atomic Instrctions

함수가 아니라, Hardware insruction으로 한번에 통으로 실행되는 것입니다

Test-and-Set, Compare-and-Swap

 

 

▶ Atomic Variables

해당 변수는 atomic하게 update됩니다~

Atomic instrction과 함께 사용할 수 있어요

 

 

 

Mutex Locks ⭐

Critical Section Problem을 해결하기 위해서 OS에서 지원하는 개념이예요

acquire()을 통해 lock을 잠그고, release()를 통해 lock을 해제합니다. 이들은 atomic하게 되어요

lock이 잠겨있는 경우에 wait합니다

해당 방법은 Busy waiting

while 내에서 lock이 잡힐 때까지 무한 로딩~ wait하면서 Core를 소모하는 특징을 가지죠

 

 

Semaphore ⭐

$S$ integer variable

• Counting semaphore
• Binary semaphore

 

▶Usage

예) Critical section problem 해결 방법

semaphore "mutex"를 생성, 1로 초기화합니다

wait(mutex); // acquire(lock)
/* critical section */
signal(mutex); // release(lock)

위 wait, signal operation 자체도 atomic하게 실행되어야 함!

 

 

예) 어떤 함수 $S_1$가 무조건 $S_2$ 앞에 실행되도록 하는 synchronization problem의 해결 방법!

semaphore "synch"를 생성, 0으로 초기화합니다.

// P1
S1;
signal(synch);

// P2
wait(synch);
S2;

 

▶w/o Busy waiting

위 같은 경우는 synch값이 0보다 커질 때까지 busy waiting을 하게 된다.

process state가 ready ⇄ running

CPU가 대기하며 계속 돌지 않게끔 구현할 수는 없을까?

 

각 semaphore 마다 waiting queue를 가집니다

해당 waiting queue의 item 구조는 아래와 같음

typedef struct {
	int value; 		// type integer
	struct process *list; 	// pointer to next record in the list
} semaphore;

operation

• block : 작업 호출 process를 해당 waiting queue에 배치함 
• wakeup : waiting queue에서 프로세스 중 하나를 제거하고, ready queue에 배치함

 

따라서 아래와 같이 활용할 수 있어요

semaphore의 값이 양수가 될 떄까지 기다리는 waiting queue가 존재

block()이 되면 waiting 상태로 들어가는 것이다! 더 이상 core를 점유하지 않음

그 다음에 signal해서 wait queue에 있는 대기하고 있는 친구 중 하나를 없애, wakeup()을 해주는 것임. 

해당 친구는 다시 ready state가 되겠죠?

 

busy wait를 하지 않으면, CPU를 다른 프로세스에게 좀 더 양보할 수 있기 때문에 리소스 면에서 효율적👍이다.

그러나 구현이 복잡할 수 있음 👎

 

 

 

Monitor

process synchronization을 위한 high-level abstraction

오직 하나의 process만이 monitor 내의 함수를 사용할 수 있어서 synchronize를 보장합니다.

monitor monitor-name
{
	// shared variable declarations
    procedure P1() {...}
    procedure P2() {...}
    procedure P3() {...}
    
    initialization code() {...}
}

 

▶ Condition Variables

condition type의 여러 변수를 정의하고, 각 변수마다 2개의 operations

• x.wait(): x.singal()이 발생하기 전까지 작업을 중지하는 process
• x.singal(): x.wait()를 호출한 process 중 하나를 다시 시작함.

 

예) $S_1$ 다음에 $S_2$가 실행될 수 있도록 하는 문제

// F1
S1;
done = true;
x.signal();

// F2
if (done == false)
	x.wait();
S2;

done이 false이므로 wait(); 하다가, F1에서 S1을 실행하면 x로 signal이 발생하므로 F2가 S2를 실행할 수 있게 됨!