[OS] 07. Synchronization Tools

Background

프로세스는 동시에 실행 가능 / 어느 시점에서나 인터럽트 가능 / 실행이 부분적으로 완료될 수 있음

Shared Data에 대한 동시 접근은 데이터 일관성을 무너지게 할 수 있음 (Data inconsistency)

데이터 일관성 유지는 서로 협력하는 프로세스의 순서 있는 실행을 보장하기 위한 메커니즘이 요구됨

모든 버퍼를 채우는 소비자-생산자 문제 : 전체 버퍼 수를 추적하는 integer 카운터를 사용

초기에 카운터는 0으로 세팅 / 생산자가 새 아이템을 생산하면 증가, 소비자가 버퍼에서 소비하면 감소

---

경쟁 조건 (Race Condition)

생산자와 소비자 작업이 올바르게 작성되어도 이들이 동시에 수행되면 바르게 동작하지 않을 수 있음
counter가 5일 때, counter++과 counter--가 동시에 수행되면 4 혹은 6이 될 수도 있음

 

counter++ 명령어는 내부적으로 다음과 같이 구현

• register1 = counter
• register1 = register1 + 1
• counter = register1

counter-- 명령어는 내부적으로 다음과 같이 구현

• register2 = counter
• register2 = register2 – 1
• counter = register2

counter = 5인 상황에서 두 명령어가 다음과 같이 섞여 수행되었다고 가정

S0: 생산자가 수행 register1 = counter {register1 = 5}

S1: 생산자가 수행 register1 = register1 + 1 {register1 = 6}

S2: 소비자가 수행 register2 = counter {register2 = 5} 

S3: 소비자가 수행 register2 = register2 – 1 {register2 = 4} 

S4: 생산자가 수행 counter = register1 {counter = 6} 

S5: 소비자가 수행 counter = register2 {counter = 4} 

=> counter = 4

경쟁 조건에 의해 불확실한 상태에 도달할 수 있음

2개 이상의 프로세스가 동시에 하나의 변수를 조작하는 것을 허용했기 때문

 

경쟁 조건

• 여러 프로세스들이 동일한 데이터에 동시에 접근해서 조작할 수 있는 상황
• 이 경우 실행 결과 값은 접근과 갱신이 일어나는 순서에 따라 달라질 수 있음

경쟁 조건의 예방

• 한 번에 오직 하나의 프로세스만이 특정 변수를 조작하는 것을 보장할 필요가 있음
• 프로세스들이 어떤 방법으로든 동기화(synchronization)될 필요가 있음

---

Critical Section Problem (임계 구역)

n개의 프로세스를 가지는 시스템을 고려 {p0, p1, … pn-1 }

Critical Section : 공유 변수에 접근하며 그로 인해 문제가 발생할 수 있는 코드 영역

각 프로세스는 코드의 Critical Section 세그먼트를 가짐

프로세스는 공통 변수 변경 / 테이블 업데이트 / 파일 작성 등이 가능

한 프로세스가 Critical Section에 들어가 있으면 다른 프로세스는 들어올 수 없음

Critical Section Problem은 위 문제를 해결하기 위한 디자인 프로토콜임

각 프로세스는 Critical Section에 들어가기 위해 entry section에서 허가를 받아야 함

그 후에 Critical Section 뒤에 exit section, remainder section이 따름

 

1. Mutual Exclusion : 만약 프로세스 Pi가 Critical Section에서 실행 중이라면, 다른 프로세스는 
   그들의 Critical Section에서 실행될 수 없음
2. Progress : Critical Section에 실행 중인 프로세스가 없고 자신의 Critical Section에 들어가고 싶어 하는
   프로세스들이 존재한다면, 다음으로 Critical Section에 들어갈 프로세스의 Section을 무한으로 연기할 수 없음
3. Bounded Waiting : 어떤 프로세스가 자신의 Critical Section에 들어가기를 원하고 그 요청이 승인되기 전에
   다른 프로세스들이 Critical Section에 들어가는 횟수에 대한 제한이 존재 (Starvation-free)

많은 커널 모드 프로세스들이 OS 안에서 활성화될 수 있음

 

커널 내에서 발생하는 경쟁 조건 예시
: next_available_pid 변수에 대한 경쟁

 

 

 

 

 

 

Critical Section Problem (임계 구역 문제) 해결

• 운영체제를 구현하는 코드(커널 코드)도 경쟁 조건이 발생함
• 열린 파일 리스트를 유지하는 자료구조, 메모리 할당을 관리하는 자료구조, 프로세스 리스트를 관리하는 자료구조, 인터럽트 처리를 위한 자료구조 등
• 커널 개발자의 책임
• 단일 코어 환경에서는 인터럽트 불능으로 임계 구역 문제를 해결할 수 있음

OS 내에서 임계 구역을 다루는 두 가지 일반적인 접근법

• 선점형 커널 / 비선점형 커널
• 비선점형 커널은 실행 중인 프로세스가 하나밖에 없으므로 커널 자료구조에 대한 경쟁 조건은 발생 X
• SMP 시스템에서 선점형 커널을 설계하는 것은 매우 어려움
• 선점형 커널이 응답성이 높고 실시간 프로그래밍에 적당하므로 선점형을 선호

Peterson’s Solution

• 임계 구역 문제를 해결하는 좋은 알고리즘 설명
• 2개의 프로세스 해결책
• load와 store 기계어 명령어가 atomic(하드웨어적으로 1번에 끝남)하다고 가정, 즉 인터럽트되지 않음
• 2개의 프로세스가 2개의 변수를 공유
• int turn / Boolean flag[2]
• turn 변수는 Critical Section에 들어갈 차례가 누구인지 나타냄
• flag 배열은 프로세스가 Critical Section에 들어갈 준비가 되었는지 나타냄
   -> flag[ i ] = true는 프로세스 Pi가 준비되었다는 의미

임계 구역 해결책의 3가지의 조건을 충족해야 함

• 상호 배제(mutual exclusion) : Pi는 flag[ j ]==false거나 turn==i인 두 조건 중 하나가 만족되어야만 임계 구역에 들어감
  Pi는 flag[ i ]==true인 상태에서만 임계 구역에 들어감
  Pi 와 Pj는 동시에 임계 구역에 들어갈 수 없음
• 진행(progress) : Pi는 flag[ j ]==true이고 turn==j인 경우에만 멈춤
• 한정된 대기(bounded waiting) : Pi는 기껏해야 Pj의 한 번의 출입 후에 임계 구역에 들어가게 됨

Peterson’s Solution 적용의 어려움

• 최신 컴퓨터 구조에는 보장되기 어려움
• 성능 향상을 위해 종속성이 없는 읽기 및 쓰기 작업들을 재정렬할 수 있음
• 데이터 Boolean flag = false; int x = 0;

 

-> x = 100을 프린트하려는 의도지만 결과는 그렇지 않을 수 있음
Peterson 해결책의 진입구역에 나타난 첫 두 문장을 바꾸면?
 -> Mutual exclusion이 보장되지 않음

 

Synchronization Hardware

많은 시스템은 Critical Section 코드의 구현을 위해 하드웨어 지원을 제공

• locking 아이디어 기반의 해결책
  lock을 통해서 Critical 영역을 보호
• Uniprocessors – 인터럽트 비활성화 가능
   - 현재 실행 중인 코드는 선점(preemption) 없이 실행됨
   - 일반적으로 multiprocessor 시스템에서는 비효율적 (이를 사용하는 OS는 확장 가능하지 않음(not scalable))
• 현대의 기계는 특별한 atomic 하드웨어 명령어를 제공
   - Atomic = non-interruptible
   - 메모리 워드를 테스트하고 값을 설정하거나 2개의 메모리 워드 내용을 swap하는 방식

---

Lock을 이용한 임계 구역 문제 해결

 

---

test_and_set 명령어

1. atomic하게 실행
2. 전달된 파라미터의 원래 값을 리턴
3. 전달된 파라미터의 새 값을 “TRUE”로 설정

Boolean 변수 lock을 공유, FALSE로 초기화

---

compare_and_swap 명령어

1. atomic하게 실행
2. 전달된 파라미터 ‘value’의 원래 값을 리턴
3. ‘value’ 변수의 값을 전달된 파라미터인 ‘new_value’ 값으로 설정, 단 ‘value’==’expected’일 경우에만 swap이 발생

Boolean 변수 lock을 공유, 0으로 초기화

---

Bounded-waiting Mutual Exclusion with test_and_set

---

Mutex Locks

• 과거의 해결책은 복잡했고 애플리케이션 개발자가 접근하기 어려움
• OS 디자이너는 임계 구역 문제를 해결하기 위한 소프트웨어 도구를 개발
• 가장 간단한 것이 mutex lock
• 먼저 acquire( )로 Critical Section을 보호하고 release( )로 해제함
   - lock이 가능한지 나타내는 Boolean 변수가 존재
• acquire( )과 release( )는 atomic해야 함
   - 일반적으로 하드웨어의 atomic 명령어로 구현
• 이 해결 방법은 busy waiting을 요구 (Mutex lock의 단점)
• 이 lock은 spinlock으로 불림

 

 

 

---

Semaphore

Mutex Lock보다 더 정교한 프로세스의 활동 동기화 방법을 제공하는 동기화 도구

2가지의 atomic 연산으로 접근 가능

wait( ) & signal( )

원래는 P( ) & V( )라고 불림 (P는 acquire, V는 release)

• Counting semaphore (Integer semaphore) : 정수값 범위에 따라 다양한 값을 가짐
• Binary semaphore : 0과 1 사이의 값을 가짐 (Mutex Lock과 같음)

S1이 S2보다 먼저 발생해야 하는 상황인 P1과 P2

semaphore “synch”를 0으로 초기화하여 생성

Counting semaphore인 S를 Binary semaphore로도 생성 가능

 

 

 

 

두 프로세스가 같은 시간에 같은 세마포어에서 wait( )과 signal( )을 실행하지 못하도록 보장해야 함

세마포어 구현은 임계 구역 문제가 됨

wait( )과 signal( ) 코드가 임계 구역에 위치함

임계 구역 구현에 busy waiting이 발생 가능

구현 코드는 매우 짧음

임계 구역이 거의 점유되지 않는 경우, busy waiting이 적게 발생

애플리케이션이 임계 구역에서 많은 시간을 보낼 수 있으며 이는 좋은 방법이 아님

---

Busy Waiting이 없는 세마포어 구현

각 세마포어에 관련된 Waiting Queue가 존재
Waiting Queue의 각 엔트리는 2가지 데이터 항목을 가짐
Value (integer) / 리스트의 다음 프로세스를 가리키는 포인터

 

2가지의 추가적인 연산

• block : 이 연산을 발생시키는 프로세스를 적절한 Waiting Queue에 위치시킴
• wakeup : Waiting Queue에서 프로세스 중 하나를 제거하고 Ready Queue에 위치시킴

Semaphore의 waiting queue 구현 방법

• Semaphore 구조체에 연결된 연결 리스트로 구현
• 대기 중인 프로세스들의 PCB를 연결
• 음수 값은 대기 중인 프로세스의 개수를 의미함
• 양수 값은 이용 가능한 자원의 개수를 의미함

동일 semaphore에 대해 둘 이상의 프로세스가 동시에 wait()와 
signal() 연산을 실행할 수 없도록 보장해야 함

• 단일 처리기에서는 인터럽트 금지시킴으로써 간단히 해결됨
• 다중 처리기에서는 모든 프로세서에서 인터럽트를 금지하여야 함
• 인터럽트 금지는 어려운 작업이며 성능이 심각하게 감소하는 결과 초래
• SMP에서는 wait()와 signal() 연산이 원자적으로 실행되는 것을 보장하기 위해서 compare_and_swap() 또는 spinlock을 제공해야 함

세마포어의 문제점 : 부적절한 사용

1. signal (mutex) ... wait (mutex)
2. wait (mutex) ... wait (mutex)
3. wait (mutex)와 signal (mutex) 중 하나 혹은 둘 다 빠진 경우

Deadlock과 Starvation(기아)이 발생 가능

---

Monitors

Monitor : 프로세스 동기화를 위한 편리하고 효과적인 메커니즘을 제공하는 고수준의 추상화 (Java, Python에서 가능, C++도 나중에 추가)

추상화 데이터 타입(Abstract Data Type)과 내부 변수는 프로시저 내의 코드에서만 접근 가능

한 번에 하나의 프로세스만 모니터 내에서 활성화될 수 있음

그러나 일부 동기화 기법을 모델링하기에는 충분히 강력하지 않음

 

 

 

---

Condition Variables (조건 변수)

기본 모니터는 여러 동기화 기법 모델링을 위해서 충분히 강력하지 않으므로 조건 변수가 도입됨
프로그래머는 하나 이상의 조건 타입의 변수를 정의 가능
조건 변수에 적용되는 2가지 연산 (조건 변수 condition x;)

• x.wait( ) : 이 연산을 호출한 프로세스는 보류 (x.signal( )이 발생할 때까지)
• x.signal( ) : 보류 중인 프로세스가 있다면 x.wait( )를 호출한 프로세스 중 하나가 재개 / 보류 중이던 프로세스 중 정확히 1개만 재개 / 보류 중인 프로세스가 없다면 아무 일도 일어나지 않음 (세마포어에서 signal( )이 항상 세마포어 상태에 영향을 주는 것과 차이가 있음)

만약 프로세스 P가 x.signal을 호출, 프로세스 Q가 x.wait에 중단되어 있었다면

 -> Q와 P는 병렬로 실행될 수 없음 / Q가 재개되면 P는 기다려야 함

Signal and wait : P는 Q가 모니터를 떠나거나 다른 조건을 기다릴 때까지 기다림

Signal and continue : Q는 P가 모니터를 떠나거나 다른 조건을 기다릴 때까지 기다림
 -> 두 가지 방법 모두 장단점이 있으며 프로그래머가 선택할 수 있고 C#, Java 등 여러 언어에 구현되어 있음

---

Deadlock and Starvation

Deadlock : 2개 이상의 프로세스가 하나의 이벤트에 대해 무한히 기다리고 있는 상태

대기 중인 프로세스 중 오직 하나에 의해서만 발생 가능

 

S와 Q를 세마포어로 정의하고 1로 초기화한 상황

 

 

 

 

 

Starvation / indefinite blocking
중단된 세마포어 큐에서 프로세스가 영원히 제거되지 않을 수 있음

 

Priority Inversion

낮은 우선순위 프로세스가 높은 우선순위 프로세스가 필요로 하는 lock을 가지고 있을 때 발생하는 스케줄링 문제
-> Priority-inheritance 프로토콜로 해결 가능