[운영체제] 공룡책🦖 ch06. Synchronization Tools

Reference

1. Abraham Silberschatz, Greg Gagne, Peter B. Galvin - Operating System Concepts (2018)

2. Operating System class by Professor Sukyong-Choi at Korea University 

3. 혼자 공부하는 컴퓨터구조 + 운영채재 (강민철)

중요한 내용 위주로 요약 && 정리했습니다.

 

목차

1. Background
2. The Critical-Section Problem
3. Peterson’s solution
4. Hardware Support for Synchronization
5. Mutex Locks
6. Semaphores
7. Monitors
8. Liveness
9. Evaluation

---

• race condition : shared data에 대한 접근이 제어되지 않으면 발생하며, 데이터 손상을 야기함
• process synchronization : race condition을 피하기 위해 shared data에 대한 접근을 제어하는 tool들을 사용한다.
• tool을 잘못 사용하면 deadlock와 같은 시스템 성능 저하로 이어진다.
• cooperationg process : 논리 주소 공간 공유 or 공유메모리/메시지 전달로 데이터를 공유

⇒ 이때 동시성 문제가 발생할 수 있다. ⇒ 프로세스 간 순차적 실행을 보장해야 한다!

 

---

6.1 Background

cooperationg process간(비동기적 실행, 데이터 공유)의 데이터 공유로 인한 무결성 문제를 해결해야 한다.

• 원형의 Bounded buffer을 통해서 process간 통신한다.

***Producer process***
while (true) {
	/* produce an item in next produced */
	while (count == BUFFER SIZE)
		; /* do nothing */
	
	buffer[in] = next produced;
	in = (in + 1) % BUFFER SIZE;
	count++;
}

***Consumer process***
while (true) {
	while (count == 0)
		; /* do nothing */
	next consumed = buffer[out];
	out = (out + 1) % BUFFER SIZE;
	count--;
	/* consume the item in next consumed */
}

⇒ 각각은 올바르게 동작하지만, 병행하여 실행 시 올바르지 않을 수 있다!

⇒ low level statement들이 임의의 순서로 뒤섞이게 된다. ⇒ incorrect state 발생

• race condition: 동일한 data에 동시에 접근/조작하고, 그 결과가 접근이 발생한 특정 순서에 의존하는 상황 → 이를 방지하기 위해서는 한번에 하나의 프로세스만 조작하도록 보장해야 한다! (동기화)

 

---

6.2 Critical Section Problem

• critical section (임계 구역): 다른 process와 공유 데이터에 접근/갱신하는 code section
• 각 process는 critical section을 가진다.
• 한 프로세스가 자신의 critical section에서 실행하는 동안 다른 프로세스들은 그들의 임계구역에서 실행 불가
• critical-section problem : 프로세스들이 협력하며 데이터를 공유할 수 있도록 자신들의 activity를 동기화할 때 사용할 수 있는 프로토콜을 설계하는 것
• 각 process들은 반드시 임계 구역에 진입할 때 permission을 요청해야 한다!

• 각 process들은 nonzero speed로 실행된다.

critical-section problem의 해결 방안의 요구 조건은 다음 3가지이다.

1. Mutual exclusion (상호 배제): 임계구역 당 하나의 process만 실행
2. Progress : 현재 임계구역에서 실행 중인 process가 없는데, 임계구역에서 실행하려는 process를 막아서는 안된다. ⇒ 계속해서 process들이 임계구역에 들어오지 못하는 것을 방지
3. Bounded Waiting : 어떤 process가 임계구역에 들어가고자 한다면, 기다리는 시간에 대해 bound가 있어야 한다. ⇒ 특정 process가 무한정 대기하는 상황을 방지

Example (1): kernel의 자료 구조는 open files의 리스트를 관리한다. 이때 새로 file을 열고 닫을 때마다 리스트를 갱신해야 한다. → 두 process가 동시에 file을 open하는 경우 list에 대한 각 update 동작은 race condition에 빠진다.

Example (2): P0와 P1은 fork() system call로 자식 process를 동시에 생성하는 경우 → 서로 다른 child process가 생성되었지만 pid가 같은 경우가 발생한다.

OS에서 critical section을 다루는 두 가지 방법

1. nonpreemptive kernel : 커널 모드에서 실행되는 process는 선점되지 않는다.                                                               ⇒ race condition이 발생하지 않는다.
2. preemptive kernel : 커널 모드에서 실행되더라도 선점될 수 있다.                                                                               ⇒ race condition이 발생할 수 있다.

 

---

6.3 Peterson’s Solution

• Peterson's Solution : critical section과 reminder section을 번갈아 실행하는 두 process로 제한
• turn: 누가 임계구역에 들어갈 차례인지 표시
• flag: 임계구역에 들어갈 준비가 되었다는 의사 표시

figure 6.3에 나온 코드가 (1) Mutual exclusion, (2) Progress, (3) Bounded-waiting 을 만족하는지 확인

1. mutual exclusion을 만족하는가? : 동시에 실행되지만 turn 값에 따라서 임계구역에 한 process만 진입하고 있으므로 만족한다. 한 process가 CS에 있는 한, 조건이 변하지 않고 유지되므로 나머지 process는 무조건 대기해야 한다.
2. Progress, Bounded-waiting을 만족하는가?: 프로세스 Pi는 while문에서 대기하면서 변수 값을 변경하지 않으므로, Pj가 CS를 나오면서 flag[j] 를 false로 변경할 때 CS에 진입한다. (1회 대기 → bounded waiting) Pj가 CS를 나오면 다음 CS 진입 process는 대기중이던 Pi가 된다. (Pj가 다시 진입 X → progress)

• 하지만 Peterson’s solution은 instruction들의 재배치로 인해 제대로 실행함을 보장할 수 없다.

⇒ x와 flag간 의존성이 없기 때문에 명령어들이 재배치될 수 있다.

만약 순서가 바뀐다면 위와 같이 CS에 두 process가 동시에 진입할 수도 있다.

결국 Peterson’s solution은 사용할 수 없고, 다른 synchronization tool을 사용해야 한다.

 

---

6.4 Hardware Support for Synchronization

hardware를 사용하여 critical-section problem을 해결할 수 있다.

6.4.1 Memory Barriers

computer architecture는 메모리 변경 사항을 다른 모든 process들에게 전파하는 명령어를 제공한다.

• memory barriers (memory fences) : 다음 명령 실행 전에 모든 load와 store이 완료됨을 보장하고, reorder 되더라도 후속 명령의 실행 전에 저장을 완료하고 그 결과가 모두에게 보여준다.

⇒ 메모리 간 변경 사항을 전파하여 명령어들의 순서를 보장한다!

6.4.2 Hardware Instructions - TAS, CAS

• test_and_set() : 제일 처음 process만 CS에 진입하도록 함
• compare_and_swap() : Swapping에 기반하여 two words에 atomically하게 동작하는 명령어

 

test_and_set()

• target 값을 test하고 true로 set한다.
• 두 TAS가 동시에 실행되면, 임의 순서로 순차 실행된다.
• lock : CS 진입 권한, false로 초기화

boolean test_and_set(boolean *target) {
	boolean rv = *target;
	*target = true; ///target의 값을 true로 set
	return rv;  //원래 target 값을 return
}

⇒ 1번 실행 후 TAS()의 결과는 무조건 true이다. (즉, 두 번째로 실행하는 process는 무조건 true)

**TAS을 통한 Mutual-exclusion 구현**
do {
	while (test and set(&lock))
		; /* do nothing */
		/* critical section */

	lock = false; // 끝나면 lock을 해제
		/* remainder section */
} while (true);

⇒ 처음 실행하는 process: lock=false ⇒ while 조건 : false ⇒ CS 진입

⇒ 두 번째로 실행하는 process (lock 공유): lock = true ⇒ CS 진입 불가

 

compare_and_swap()

• value와 expected가 같다면 value을 new_value로 갱신한다.
• lock : 0으로 초기화

int compare_and_swap(int *value, int expected, int new value) {
	int temp = *value;
	if (*value == expected)
		*value = new value;  //new_value 값으로 설정
	return temp;           // original value 값 return
}

⇒ 첫 실행: value 값을 return

⇒ 두 번째 실행: new_value 값을 return

**CAS을 통한 Mutual exclusion 구현**
while (true) {
	while (compare_and_swap(&lock, 0, 1) != 0)
		; /* do nothing */
		/* critical section */

	lock = 0;  //끝나면 lock 해제
		/* remainder section */
}

⇒ lock = 0: 0을 return ⇒ CS 진입 가능 (첫 process 진입)

⇒ lock = 1: 1을 return ⇒ CS 진입 불가능 (나머지 process 대기)

이 경우 무한 대기할 가능성이 존재하므로 아래와 같이 수정한다.

 

Bounded-waiting Mutual exclusion with CAS()

 

6.4.3 Atomic Variables

• atomic variable : 기본 데이터 타입(integer, boolean)에 대한 원자적 연산을 제공
• 한 변수가 update 되는 동안 경쟁(race)이 있을 때 mutual exclusion을 보장한다.

• 모든 상황의 경쟁 조건(race condition)을 해결하지는 못한다. (bounded-buffer problem)
• 1 producer, 2 consumer⇒ buffer가 비었고, 두 consumer가 동시에 while 문에서 대기중인 경우

 

---

6.5 Mutex Locks

• mutex : mutual exclusion을 의미한다.
• mutex lock(spin lock) : critical sections을 보호하고, race condition을 방지한다.
• acquire(): process는 반드시 critical section에 들어가지 전에 lock을 얻어야 한다.
• release(): process가 critical section을 나가면 lock을 해제한다.
• acquire()와 release()는 atomically하게 수행되어야 한다.

• busy waiting : 한 process가 CS에 있는 동안 나머지 process들은 계속 조건을 확인하며 loop을 실행하는 상황이다. (Mutex lock의 단점) ⇒ CPU 낭비
• spin lock : lock이 available할 때까지 기다리면서 process가 “회전”한다.

⇒ spin lock을 사용하면 context switch가 일어나지 않는다.

 

 

---

6.6 Semaphore

“semaphore”라는 용어는 철도 신호기에서 유래한 단어이다. 기차는 신호기가 내려가 있을 때는 ‘STOP’ 신호로 간주하고 잠시 멈춘다. 반대로 신호기가 올라가 있을 때는 ‘GO’ 신호로 간주하고 다시 움직이기 시작한다.

이처럼 semaphore는 STOP(wait() )와 GO(signal())을 통해서 process가 critical section에 진입하는 것을 관리한다.

• semaphore : 정수형 변수, 초기화를 제외하고 두 표준 atomic 연산으로만 접근된다.(wait, signal)

⇒ 공유 자원이 여러 개 있는 상황에서도 적용이 가능한 synchronization tool

⇒ 여러 개의 process가 각각 공유 자원에 접근이 가능해진다.

• binary semaphore 와 counting semaphore 가 있다.
• S : 임계 구역에 진입할 수 있는 process의 개수 (== 사용 가능한 공유 자원의 개수)
• signal() : 임계 구역 앞에서 기다리는 process에게 ‘이제 가도 좋다’고 신호를 주는 함수
• wait() : 임계 구역에 들어가도 좋은지, 기다려야 할지를 알려주는 함수

signal(S) {
	S++
}

wait(S) {
	while(S <= 0)
		;
	S--;
}

⇒ 모두 원자적으로 수행된다.(한 process가 semaphore를 변경할 때, 다른 process가 동시 변경 불가)

1. P1 wait(). S는 현재 2이므로 1로 감소시키고 임계 구역 진입
2. P2 wait(). S는 현재 1이므로 0으로 감소시키고 임계 구역 진입
3. P3 wait(). S는 현재 0이므로 무한히 반복하며 S확인
4. P1의 임계 구역 작업 종료. signal() 호출. S를 1 증가
5. P3가 S가 1이 됨을 확인. S를 0으로 감소시키고 임계 구역 진입

 

6.6.1 Semaphore Usage

counting VS binary semaphores

• counting semaphores : 공유 자원이 N개인 경우 (0이면 unavailable), 가용한 자원의 수로 초기화
• binary semaphores : 공유 자원이 1개인 경우, metex lock 대신 사용 가능

counting semaphores

• 자원 사용 전 wait() ⇒ S—
• 자원 사용 후 signal() ⇒ S++
• count == 0 이면 자원이 모두 사용됨
• count ≤ 0 이면 process는 block됨

⇒ S는 0으로 초기화되기 때문에, P1에서 S를 1증가시키기 전까지는 P2가 실행되지 않는다.

⇒ 즉, P1 → P2 로 순서가 보장되고, 임계 구역에 하나의 process만 들어가게 된다.

⇒ But, busy waiting 문제 발생

6.6.2 Semaphore Implementation

mutex lock과 마찬가지로 위에서 살펴본 semaphore을 통한 동기화도 busy waiting 문제가 발생한다. 따라서 wait()와 signal()을 아래와 같이 수정해야 한다.

또한 semaphore을 새롭게 정의한다.

1. wait(): semaphore 사용을 위해 기다리면, 프로세스가 list에 추가된다.
   • busy waiting 대신, process가 스스로 suspend operation (sleep())을 통해서 waiting queue로 이동하여 waiting state로 전환한다. ⇒ 제어가 cpu 스케줄러로 이동 → 다음 process 선택
2. signal(): 기다리던 process를 리스트에서 제거하고 wakeup 시킨다.
   • S를 기다리던, suspend 된 process는 다른 process의 signal()(wakeup())로 ready state로 전환되어 restart 된다.

**Semaphore**
typedef struct {
	int value;
	struct process *list;  // PCB 리스트의 포인터
} semaphore;

wait(semaphore *S) {
	S->value--;
	if (S->value < 0) {
		add this process to S->list;
		sleep();
	}
}

signal(semaphore *S) {
	S->value++;
	if (S->value <= 0) {
		remove a process P from S->list;
		wakeup(P);
	}
}

• busy waiting 대신 sleep() → wakeup()
• Semaphore의 value가 음수가 될 수도 있다. (절대값이 semaphore를 기다리는 process의 수)
• bounded waiting을 보장하기 위해, FIFO 큐를 이용해서 리스트에 삽입/삭제한다.
• 동일 semaphore에 대해서 두 process가 wait/signal 연산을 동시에 실행하지 않도록 보장한다.
  1. single-processor 환경 : Interrupt 금지
  2. multicore 환경 : 모든 core에서 Interrupt 금지
• ⇒ 성능 저하 발생

1. P1 wait() 호출. S가 2에서 1로 감소. 임계 구역 진입
2. P2 wait() 호출. S가 1에서 0으로 감소. 임계 구역 진입
3. P3 wait() 호출. S가 0이므로 본인의 PCB를 waiting queue에 넣고 waiting state로 전환 sleep()
4. P1의 임계 구역 작업 종료. signal() 호출. S를 1로 증가시키고 waiting queue에 있던 P3를 꺼내서 ready queue로 옮긴다. wakeup()
5. wake up한 P3는 임계 구역에 진입한다.
6. P2의 임계 구역 작업이 종료. signal() 호출. S가 0에서 1로 증가
7. P3의 임계 구역 작업이 종료. signal() 호출. S가 1에서 2로 증가

한계점

wait/signal 연산에서 busy waiting을 완전히 제거하지 못했다.

잘 살펴보면, Entry section에서의 busy waiting은 해결했지만, critical section에서는 여전히 busy waiting이 존재할 수 있다.(sleep())

Semaphore로 process 순서 조절

• semaphore 변수를 0으로 둔다.
• 먼저 실행할 process 뒤에 signal 함수, 다음에 실행할 process 앞에 wait 함수를 둔다.

⇒ P2가 먼저 실행되더라도, wait()에 의해서 대기하고 대신 P1이 임계 구역에 진입하게 된다.

즉, 둘 중 누가 먼저 실행되던지 반드시 P1, P2 순서로 실행된다.

 

---

6.7 Monitors

• Timing errors : 특정 실행 순서로 진행되었을 때만 나타난다.

Timing errors in Semaphores

semaphore에서는 wait() → CS → signal() 순서로 진행되어야 한다.

하지만, process 중 하나라도 순서를 지키지 않고 잘못 동작한다면 timing error가 발생한다.

⇒ 결국 개발자가 semaphore나 mutex lock을 잘못 사용하면 error가 매우 쉽게 발생하는 구조이다.

⇒ 간단한 synchronization tool들을 high-level 언어의 구조물로 통합시킨다! (Monitor)

6.7.1 Monitor Usage

• monitor : 공유 자원과 공유 자원에 접근하기 위한 interface(통로)를 묶어서 관리한다.
• abstract data type (ADT) : 특정 구현과 무관한 데이터 및 연산을 캡슐화함
• monitor는 ADT이다. ⇒ instance의 state을 정의한 변수와 그 변수에 동작하는 함수 본체를 선언

• 

• monitor type은 process가 직접 사용 금지! → interface을 통해 접근한다. (캡슐화)
• monitor 내에서 한번에 한 process만 active함을 보장함
• 동기화를 위해 condition 변수를 사용한다.(직접 정의) (process나 thread의 실행 순서를 제어)

• x.wait() : 특정 process가 아직 실행될 조건이 되지 않았을 때 해당 process를 suspend한다. 다른 process가 x.signal()을 호출하기 전까지 suspend된다.
• x.signal() : 특정 process가 실행될 조건이 충족되었을 때 해당 process의 실행을 resume한다.

위 그림을 좀 더 자세히 그려보았다.

wait() 으로 일시 중지된 process는 다른 process의 signal()을 통해서 실행이 재개된다.

즉, signal은 wait을 호출하여 queue에 삽입된 process의 실행을 재개하는 연산이다.

그림에서, x.signal()에 의해서 x에 대해 waiting state에 있던 process가 wake up하여 monitor 안으로 들어올 수 있게 되었다.

Monitor 내의 경쟁

condition x 와 관계되는 process P, Q가 있다고 하자.

P에서 x.signal()을 호출 → condition x에 대해서 기다리면서 Q는 suspend된다.

⇒ 이때 Q가 resume된다면, P는 wait 해야 한다.

⇒ 만약, P가 wait 하지 않으면, monitor 내에 P, Q 두 개가 동시에 actice 된다.

해결 방안

(1) Signal and Wait (P가 대기)

P는 Q가 monitor를 떠날 때까지 wait한다. OR 다른 조건 y에 대해서 wait한다.

(2) Signal and Continue (Q가 대기)

Q는 P가 monitor를 떠날 때까지 wait한다. OR 다른 조건 y에 대해서 wait한다.

(3) 절충안

P가 signal()하고 즉시 monitor를 떠남 → Q가 즉시 resume함

 

6.7.2 Implementing a Monitor Using Semaphores

• wait(mutex) → 모니터 → signal(mutex)
• Signal and wait scheme을 사용한다.
• int next : suspend된 process의 수
• semaphore next : 스스로 suspend하기 위한 변수, [0으로 초기화]
• mutex : 상호 배제를 위한 변수, [1로 초기화]

⇒ 둘 다 binary semaphore

 

Each procedure F

wait(mutex);
...
	body of F
...
if (next count > 0)
	signal(next);
else
	signal(mutex);

⇒ 큐에 있던 process P가 함수 F를 실행하여 모니터에 진입한다.

 

x.wait() && x.signal()

"x.wait()"
x count++;
if (next count > 0)
	signal(next);
else
	signal(mutex);
wait(x sem);
x count--;

"x.signal()"
if (x count > 0) {
	next count++;
	signal(x sem);
    wait(next);
	next count--;
}

 

Implementation of condition variales

 

Semaphore VS Monitor

• Semaphore
  • signal시 wait로 대기중인 여러 process가 반응함
  • wait() : 해당 process가 block(suspend)될 수 있음, mutex—
  • signal() : 다른 process를 release함, mutex++
• Monitor
  • signal시 모니터 내 x에 대해 큐에서 대기중인 process만 반응함
  • x에 대해 대기중인 process가 없다면 signal은 무시됨
  • x.wait() : 해당 process는 x.signal()될 때까지 항상 block됨(suspend)
  • x.signal() : 다른 process를 release하거나 무시됨

 

6.7.3 Resuming Processes within a Monitor

suspend된 process의 resume 순서는 어떻게 정해야 하는가? (하나의 process만 깨움)

(1) FCFS ordering - first come, first served

가장 오랫동안 wait한 process부터 resume하는 방법이다.

단순하지만, 많은 상황에서 적절치 않다.

(2) priority number을 사용한 ordering

signal() 연산 시 우선순위 번호가 낮은 process가 먼저 resume된다.

아래의 예시는 시간을 우선순위로 사용하여 자원 할당을 하는 동작이다.

• 자원 요청 시, 사용 시간을 명시하고, ResourceAllocator 는 shortest 시간을 요청한 process에게 할당한다.
• Timing error 발생 가능 : 접근 순서(acquire→release)가 지켜진다는 것을 보장하지 않는다.

⇒ 이를 해결하기 위해서 모니터 내에 resource-access 연산을 포함시킨디.

 

---

6.8 Liveness

synchronization tool의 사용 결과로 임계 구역에 들어가려는 process의 무한정 대기가 발생할 가능성이 있다.

⇒ 무한 대기는 progress 와 bounded-waiting 을 위반한다.

⇒ 시스템은 progress를 보장해야 한다.

• Liveness : system이 process의 progress를 보장하기 위해 만족해야 하는 property set
• Liveness failure 가 생기면 성능과 응답성이 안 좋아진다. ⇒ Deadlock, Priority Inversion

6.8.1 Deadlock

• Deadlock : 둘 이상의 process가, 대기 중인 process 중 하나에 의해 일어나는 event를 무한히 기다리는 상황

⇒ P0는 “P1이 signal(S)”하기를 기다림 && P1는 “P0이 signal(Q)”하기를 기다림

⇒ 둘 다 무한 대기

• Deadlocked state (교착 상태): set 내의 모든 process가 다른 process에 의해 야기되는 이벤트를 기다림

 

6.8.2 Priority Inversion

⇒높은 순위의 process가 낮은 순위의 process가 사용 중인 kernel data에 접근하는 경우에 일어난다.

• kernel data는 lock으로 보호된다. → 높은 순위의 process가 대기해야 함

• Priority-inheritance protocol : 높은 순위 process가 필요로 하는 자원에 접근하는 모든 process는 자원의 사용이 끝날 때까지 높은 순위를 상속받고, 종료 시 원래 우선 순위로 돌아간다

1. L이 H의 우선순위를 일시적으로 상속 받는다. → M이 선점 못 함
2. L이 종료 시 우선순위가 원상 복구됨
3. S를 요청하며 대기중이던 H가 다음에 실행됨