[OS 공룡책] Ch06. Synchronization Tools

Chapter 6: Synchronization Tools

Background

thread

• Consistency 보장 X
  • 공유 변수를 동시에 접근할 경우
  • 일관성 : 코딩할 때 답이 하나. 순서 보장
• Synchronization
  • OS, H/W가 Consistency 보장 지원
  • 잘못하면 deadlock, livelock 발생 (→ 8장)

Race Condition

• Race Condition
  • 불확실한 상태
  • 여러 프로세스들 동시 접근 → 순서 보장 X
• Counter
  • 1씩 증가
  • counter == BUFFER_SIZE : 버퍼 꽉 참 → busy waiting
    
• Producer

  • counter < BUFFER_SIZE 일 때 write

    while (True) {
    		while (counter == BUFFER_SIZE) ;   //do nothing
    		buffer[in] = nextProduced;
    		in = (in + 1) % BUFFER_SIZE;
    		counter++;
    }

• Consumer

  • counter > 0 일 때 read

    while (True) {
    		while (counter == 0) ;   //do nothing
    		nextConsumed = buffer[out];
    		out = (out + 1) % BUFFER_SIZE;
    		counter--;
    }

• Counter : 공유 변수
  • race condition 발생하는 영역 → inconsistency 발생 가능성
    
  • critical section : race condition이 발생하는 코드
• 해결 : Synchronization → 한 번에 오직 하나의 프로세스만 조작 보장
  

The Critical-Section Problem

Critical Section Problem

• critical
  1. critical section (운영체제)
     • process, thread가 한 번에 하나씩만 들어가도록
     • 동시 access가 이루어지면 안 되는 구간
  2. critical path (소프트웨어 공학)
     • 컴퓨터 시스템에서 성능에 가장 영향을 많이 미치는 경로
     • critical path랑 그렇지 않은 path랑 차이가 적어야 좋은 프로그램
• 해결법 : 한 번에 한 개만 들어가도록 보장하는 입구, 출구

  do {
  		<entry section>   // 들어가는 문
  				critical section
  		<exit section>   // 나가는 문
  				remainder section
  } while (true);

• 조건 : 반드시 만족돼야 해결 ⭐️

  1. Mutual Exclusion

     • 상호 배타적 접근
     • Critical section엔 반드시 하나만

  2. Progress

     • 기다리고 있는 애가 있으면 반드시 하나는 들어가야 됨.
     • 다 막아버리면 X

  3. Bounded Waiting
     - 유한한 기다림
     - starvation 발생 X

     → 모두 만족해야 critical section problem이 해결됨

임계 구역 문제의 해결

• 비선점형 커널
  • 명령어(load, add, store) 수행할 동안 interrupt disable
  • race condition 발생 X
  • 성능 저하 → 선점형 커널 사용
• 선점형 커널 (선호)
  • 높은 응답성, 실시간 프로그래밍에 적당
  • race condition은? → Peterson’s Solution

Peterson’s Solution

Peterson’s Solution

• 충돌 발생 시 상대에게 먼저 양보

  • int turn critical section에 들어갈 process

  • bool flag[i] Pi가 들어갈 준비가 되었는지 여부

    

    → turn을 서로 양보해준다.

• Mutual exclusion 만족

  • Pi : flag[j] == false or turn == i 인 상태에서만 들어감

  • Pj : flag[j] == true 인 상태에서만 들어감

    → Pi, Pj는 동시에 들어갈 수 X

• Progress 만족

  • Pi : flag[j] == true && turn == j 인 경우에만 멈춤 → busy waiting
    

• Bounded waiting 만족

  • Pi : Pj의 한 번의 출입 후에 들어감

Hardware Support for Synchronization

Synchronization Hardware

• Peterson’s Solution 적용 어려움

  • 최신 컴퓨터 구조 : 성능 향상을 위해 종속성이 없는 작업들 재정렬 → Peterson’s Solution 보장 X
    

• atomic operation 이 필요

  

  • H/W : 명령어 간 순서가 변경되지 않는 operation 지원
  • locking : critical section에 들어올 때 lock 필요 → 나갈 때 lock 풀어줌
    

  1. test_and_set()

     

     

     • target이 0일 때 가져와서 1로 바꾸면 lock 얻음 → return이 0이면 lock 획득한 것
       
     • target이 1일 때 가져오면 lock 풀릴 때까지 기다림

  2. compare_and_swap

     ![](https://velog.velcdn.com/images/jnary/post/15c9cbe8-57ab-40fc-b9f5-e63021ed88d8/image.png)
     
     
     ![](https://velog.velcdn.com/images/jnary/post/fa7024f1-257f-4faa-82fb-849bd7b240c8/image.png)
     
     
     - expected = 0, new_value = 1
     - test_and_set()과 동일, 같은 기능

     → Bounded waiting 보장 X

• Bounded waiting 보장

  

  • 사용하기 불편함 → 대신 Mutex lock, semaphore 등을 사용
    

Mutex Locks

Mutex Lock

• mutex : mutual exclusion 상호배제
  • critical section 보호
  • race condition 방지
  • atomic 수행 보장
• lock

  • 사용 가능 X → busy waiting

  • 사용 가능 → available = false로 변경 후 자기만 사용

    acquire() {
    		while (!available)
    				/* busy wait */
    		available = false;
    }
    release() {
    		available = true
    }
    do {
    		<acquire lock>
    				/* ciritical section */
    		<release lock>
    				/* remainder section */
    } while (true);

• 단점
  • busy waiting : CPU cycle 낭비 → Spinlock : context switch 시간 X (무조건 나쁜 게 아니다!)
    
  • 공유자원 하나만 control 가능 → 여러 개에 대해 동일한 control : Semaphore
    

Semaphores

Semaphore

• Semaphore
  1. Integer semaphore : 공유자원 2개 이상
     • integer variable : 공유 자원 control 개수 → cf. Mutex Lock : 0, 1 (2개만 있을 때)
       
  2. Binary semaphore = mutex lock : 1개
• wait(), signal() → P(), V() 라고도 함

  wait(S) {
  		while (S <= 0)
  				/* busy wait */
  		S--;
  }
  signal(S) {
  		S++;
  }

• 순서 control 가능

  • S1 끝나야 S2 실행되도록

  • synch = 0 초기화

    P1:
    		S1;
    		signal(synch);
    P2:
    		wait(synch);
    		S2;

Semaphore Implementation

• busy waiting
  • semaphore 값 < 0
  • 성능 저하
• block → wakeup
  • 재우는 것, run → wait(stop)
  • waiting queue 구현
  • PCB 리스트 가리키는 포인터 존재

typedef struct {
		int value;   //semaphore 값
		//음수 : 대기중인 프로세스 개수, 양수 : 이용가능한 자원 개수
		struct process *list;   //대기 중인 PCB 리스트 가리키는 포인터
} semaphore;
wait(semaphore *S) {
		S -> value--;
		if (S -> value < 0) {
				add this process to S -> list;
				block();
		}
}
signal(semaphore *S) {[
		S -> value++;
		if (S -> value <= 0) {
				remove a process P from S -> list;
				wakeup(P);
		}
}

• 동일 semaphore에 대해 둘 이상의 프로세스가 동시에 wait(), signal() 연산 atomic하게 실행하도록 보장 → interrupt disable
  

Problems with Semaphores

• 틀린 사용 Honest programming error
  • signal → wait
  • wait → wait
• Deadlock, starvation 발생 가능

→ Monitor : Simple Synchronization Tool

Monitors

Monitors

• high-level abstraction
  • Semaphore보다 error 발생 확률 낮음
  • 동기화 쉬워짐
  • Java, Python
• Abstract Data Type

  • 내부 변수는 오직 code를 통해서만 접근 가능

  • monitor내의 함수들은 한 번에 하나씩만 활성화 가능

    monitor monitor_name {
    		function P1 (..) {...}
    		...
    		function Pn (..) {...}
    				Initialization code (..) {...}
    		}
    }

Condition Variables

• 기본 모니터 : 여러 동기화 scheme 모델링을 위해 충분히 강력 X → 조건 변수 도입
• 조건 : x, y → 하나 이상의 조건 타입의 변수 정의 가능
  
• 연산

  1. X.wait()

     호출한 프로세스 일시 중단

  2. X.signal()

     • 보류 중인 프로세스 존재 → X.wait()을 호출한 프로세스 중 하나만 재개
       
     • 보류 중인 프로세스 X → 아무 일도 발생 X (Semaphore와의 차이점)
       

Condition Variables Choices

• 프로세스 P → x.signal() 호출 프로세스 Q → x.wait()에서 일시 중단
  
• 병행 실행 X

  1. Signal and wait

     • P : Q가 모니터 떠날 때까지 대기

  2. Signal and continue
     - Q : P가 모니터 떠날 때까지 대기

     → 둘 다 장단점 존재, 프로그래머가 결정

Liveness

동기화 고려하다보면 deadlock, starvation 발생 가능

Deadlock

• 두 개 이상의 프로세스가 서로 끝나기를 무한정 기다리고 있는 상황
• live lock : 살아있는데 못 가는 것, CPU 리소스 사용 dead lock : 죽어서 못 가는 것, 사용 X
  

Starvation

• 특정 프로세스가 자원에 접근하기 위해 무한정 기다려야 하는 상황
• Infinite blocking

Priority Inversion

• priority 역전
  • priority : A(signal) < B(wait)
  • B의 우선순위가 더 높지만 항상 A가 먼저 실행
• A(signal) : 10, B(wait) : 1, C : 3, D : 5 C → D → A → B
  
• priority-inheritance protocal
  • A가 signal 할 때까지만 A의 우선순위와 B의 우선순위를 바꿔주는 것
  • 복잡 → 보통은 안 해줌

+) OS를 사용하는 목적

1. Abstraction
2. Concurrency → synchronization
3. Virtualization → Process 초기화, Memory 가상화