Synchronization Tools

본 자료 정리는 'Operating System Concepts'(Tenth Edition) - Abraham Silberschatz 원서에 출처합니다.
Copyright © 2020 John Wiley & Sons, Inc.

Chapter 6: Synchronization Tools

• Backgroud
• The Critical-Section Problem
• Peterson's Solution
• Hardware Support for Synchronization
• Mutex Locks
• Semaphores
• Monitors
• Liveness
• Evaluation

Objectives

• critical section 및 race condition 설명

• 메모리 배리어, 비교 및 스왑 작업, semaphores를 사용하여 임계 영역 문제(critical section problem)에 대한 하드웨어 솔루션 제시

• critical section 문제를 해결하기 위해 mutex locks, semaphores, 모니터 및 조건 변수를 사용할 수 있는 방법 설명

Background

• 프로세스는 동시에 또는 병렬로 실행될 수 있다.

  • [동시 실행] 한 프로세스는 다른 프로세스가 스케줄링되기 전까지 잠깐만 실행된다. 사실상 언제나 인터럽트 당할 수 있다.

  • [병렬 실행] 두 개의 명령 스트림(서로 다른 프로세스)이 분리된 코어에서 동시에 실행된다.

• 공유 데이터에 대한 동시 액세스로 인해 데이터 불일치가 발생할 수 있다.

• 데이터 일관성을 유지하려면 협력 프로세스의 질서 있는 실행을 보장하는 메커니즘이 필요하다.

Producer-Consumer Problem

Chapter 3에서 다룬 기존의 생산자-소비자 문제 알고리즘에서 초기값이 0인 count라는 공유 변수를 추가한다. count는 버퍼에 새 원소를 추가할 때마다 증가되며, 버퍼에서 원소가 하나 씩 줄어들 때마다 감소된다.

위의 생산자-소비자 함수가 각각 옳다 하더라도, 동시에 실행될시 제대로 작동이 안될 수 있다. 공유변수인 count 값이 제대로된 정보 유지를 못하게 되면 데이터 불일치성 문제가 발생한다.

Race Condition

메모리에 있는 counter값을 가져와 register에 담고, register 값을 증가/감소 시켜 다시 count변수에 저장하는 방식으로 작동한다.

초기 설정된 counter값이 5인 경우를 가정해보자. 만약 T1에서 업데이트된 register1의 값을 count변수에 넣지 않은채로 다른 프로세스한테 interrupt 되는경우, 두 개의 프로세스가 공유하는 counter 변수가 각각 다른 값을 갖게되어 interrupt가 발생하게 된다.

즉, 명령문 실행 순서에 따라 count 값이 완전히 다른 결과가 나올 수 있다.

여러 프로세스가 동시에 동일한 데이터에 액세스하고 조작하는 상황을 경합조건(Race condition)이라 부른다. 실행 결과는 액세스가 발생하는 레이스 조건 특정 순서에 따라 달라진다.

race condition이 발생하면 data inconsistency가 생긴다.

따라서 race condition이 생기는 것을 방지하려면 오로지 한 프로세스가 한 순간에 count를 조작할 수 있도록 보장해야된다. 이걸 보장하려면 프로세스를 동기화해줘야 한다.

Critical Section Problem

n개의 프로세스 {p0, p1,...,pn-1} 로 이루어진 시스템을 고려해보자. 각 프로세스에는 공통 변수, 테이블, 파일 등의 공유 데이터에 액세스하고 업데이트할 수 있는 코드 세그먼트가 있다.(PCB)

이때 critical section이란 공유 데이터가 조작될 수 있고 경쟁 조건이 발생할 수 있는 코드 섹션이다.

이 시스템의 중요한 기능으로는

그렇다면 Critical section problem을 어떻게 해결할 것인가?

• 프로세스가 협력적으로 자료를 공유할 수 있도록 자신의 활동을 동기화하기 위한 프로토콜을 설계한다.

• 한 프로세스가 임계구역(critical section)에서 실행 중이면, 임계구역을 공유하는 다른 프로세스는 자신의 임계구역을 실행할 수 없게 한다.

일반적인 프로세스 구조는 다음과 같다.

각 프로세스는 반드시 자신의 임계구역에 들어갈 때 허락을 맡아야 한다. 즉, critical setion을 수행할 수 있는 상황인지 확인하고 입장을 허용/거절 하는 부분을 entry section이라 한다.

critical section에 입장한 경우 공유 데이터를 조작하고, 이후에 퇴장할 때 exit section을 거친다. 이 부분은 자신의 프로세스의 접근이 끝났으니 critical section에 다른 프로세스가 들어올 수 있도록 하용해준다.

나머지 부분은 remainder section이라 한다.

Solution to Critical-Section Problem

critical section 문제를 해결하려면 다음의 3가지 조건을 동시에 만족해야한다.

• Mutual Exclusion(상호배제): 프로세스 Pi가 크리티컬 섹션에서 실행 중이면 다른 프로세스는 크리티컬 섹션에서 실행될 수 없다.
  -> 한 번에 하나의 프로세스만 실행

• Progress(진행): 만약 자신의 크리티컬 섹션에서 실행 중인 프로세스가 없고 크리티컬 섹션에 들어가고자 하는 프로세스가 있다면 다음에 크리티컬 섹션에 들어갈 프로세스의 선택을 무한정 연기할 수 없다.

• Bounded waiting(한정 대기): 프로세스가 자신의 크리티컬 섹션에 들어가도록 요청한 후 해당 요청이 승인되기 전에 다른 프로세스가 크리티컬 섹션에 들어가도록 허용되는 횟수에 제한이 있다.

(각 프로세스가 0이 아닌 속도로 실행 중이라고 가정함)
(n개의 프로세스 간의 상대적인 속도에 대해서는 어떠한 가정도 할 수 없음)

Critical-Section Handling in OS

주로 운영체제를 구현한 코드(커널 코드 kernel code)는 공유데이터가 많기 때문에 여러 경합 조건(race condition)의 대상이 된다.

예를 들어 현재 열려있는 파일의 목록을 관리하는 커널 자료 구조가 있는 경우를 살펴보자. 두 프로세스가 동시에 파일을 열었다고 가정하면 이 목록에 두 번의 갱신이 일어날 수도 있어 경합 조건이 발생한다.

두 프로세스 P0와 P1이 fork() 시스템 호출로 새 자식 프로세스 생성 한다. chapter 3에서 언급했듯 fork() 함수는 새롭게 생성된 프로세스의 식별자를 부모 프로세스에게 반환해준다. 이 예제에서는 다음에 사용 가능한 프로세스 식별자의 값을 의미하는 커널 변수 next_available_pid에 대해 경합 조건이 발생했다. 상호 배제를 제공하지 않는 이상 같은 프로세스 식별자 숫자가 서로 다른 프로세스에게 할당될 수 있다.

이렇게 pid가 같아지는 경우 문제가 발생한다.

경합 조건에 취약한 다른 커널 자료구조로는 메모리 할당 관리, 프로세스 목록 관리, 인터럽트 처리할 때 사용하는 구조들이 있다. 운영체제가 이런 경합 조건 문제에서 자유롭게 만드는 것은 커널 개발자의 책임이다.

단일 코어 환경에서는 임계구역 문제를 공유 변수를 처리하는 도중 인터럽트만 막으면 손쉽게 해결 가능하다.

Critical-Section Handling in OS 2

커널이 선점형인지 비선점형인지에 따라 운영체제에서 critical section을 처리하는 방법이 두 가지로 나뉜다.

• Preemptive: 커널 모드에서 프로세스가 실행 중에 선점이 될 수 있도록 허용
  -> 주로 이용되는 방법

• Non-preemptive: 커널 모드를 종료하거나 차단하거나 자발적으로 CPU를 양보할 때까지 실행. (선점 허용 x)
  -> race condition이 안생김

따라서 선점적 커널은 공유 커널 데이터가 경합 조건에 안 걸리게 신중하게 설계해야한다. (특히 SMP 구조의 경우)

그럼 왜 선점적 커널을 더 사용하는 것인가?

선점적 커널은 실시간 프로세스가 현재 커널에서 실행 중인 프로세스를 선점할 수 있어 실시간 프로그래밍에 더욱 적합하다.

Peterson Solution

피터슨의 해법은 critical section과 나머지 구역 간을 왔다 갔다하는 두 프로세스 간에만 대한 것이다. 프로세스는 P0와 P1로 구분한다. 편의상 Pi이라 할 때, 이 프로세스의 짝은 Pj라 표현한다.

피터슨의 해법을 하려면 두 프로세스 간 두 개의 데이터를 공유해야 한다.

• int turn;
  -> turn: 프로세스 번호(i/j)
  -> 어떤 프로세스가 들어갈 것인지..

• Boolean flag[2]
  -> 프로세스 개수만큼 true/false를 갖는 배열
  -> 프로세스가 critical section에 들어갈 준비가 됐는지 상태 return
  -> true를 리턴할 경우 프로세스가 준비되었음을 의미

Algorithm for Process Pi

위의 그림을 보면 직관적으로 이해할 수 있다. Pj의 경우도 위와 같다.

Pi 와 Pj가 동시 진입하는 경우는, turn을 먼저 수행하는 애가 진입하고 상대는 대기하게 된다.

이렇듯 critical section에 한 번에 하나의 프로세스만 들어가게 되므로 mutual exclusion을 만족한다.

Peterson's Solution 2

• 피터슨 해결법은 3가지 CS(Critical section) 요구사항이 충족됨을 증명할 수 있다.

1. 상호배제(Mutual exclusion)가 유지된다.
   

2. 진행 요건(progress)이 충족된다.

3. 한정 대기(Bounded-waiting) 요건이 충족된다.

Peterson's Solution 3

하지만 Peterson 솔루션은 최신 컴퓨터 아키텍처에서 작동한다고 보장할 수 없다.

• 시스템 성능을 개선 때문에 프로세서는 종속성이 없는 읽기 및 쓰기 작업을 재정렬한다.

Peterson의 솔루션에서 명령어 재정렬의 효과

두 스레드가 동시에 중요한 섹션에서 활성화될 수 있다.. 따라서 피터슨 솔루션은 현대식 컴퓨터에서 상호배제가 확실히 보장이 안된다. 따라서 상호 배제(mutual exclusion)을 보존할 수 있는 유일한 방법은 제대로된 동기화 도구를 사용하는 것이다.

이러한 도구를 논하는 것은 하드웨어에서 애초에 원시적으로 지원하는 것으로 시작해서 나중엔 커널 개발자와 어플리케이션 프로그래머가 사용 가능한 추상적인, 고수준의 소프트웨어 기반 API로 나아가야 한다.

Hardware Support for Synchronization

위에서와 같이 임계구역에 대한 소프트웨어 기반 솔루션은 최신 컴퓨터 아키텍처에서 작동되지 않을 수 있다.

따라서 임계구역 문제를 해결하는데 도움을 주는 hardware support 는 다음 세가지 방법이 있다.

• Memory barriers

• Hardware Instructions

• Atomic variables

Memory barriers

컴퓨터 아키텍처는 메모리의 모든 변경 사항을 다른 모든 프로세서에 전파한다.

메모리 장벽 명령이 수행될 때 시스템은 후속 로드 또는 저장 작업이 수행되기 전에 모든 로드 및 저장이 완료되도록 한다.

-> 이는 순서가 지켜져서 실행되도록 보장해준다.

따라서 명령어를 재배치하더라도 메모리 배리어에 의해 저장 연산이 메모리에 적용이 되어 나중에 불러오기나 저장을 하더라도 수정 사항이 다른 프로세서에게도 즉시 반영 되도록 할 수 있다.

Hardware Instructions

최신 컴퓨터는 메모리 워드를 테스트 및 수정하거나 두 메모리 워드의 내용을 원자적으로 교환할 수 있는 특수 하드웨어 명령을 하나의 중단 불가능한 장치로 제공한다.

대부분의 요즘 컴퓨터 시스템에서는 원자적으로(atomically) 워드의 내용물을 테스트하고 수정해줄 수 있게 하거나 두 워드 간의 내용물을 스왑할 수 있게 하는 특수한 하드웨어 명령어를 제공한다. 이 특수한 명령어로 상대적으로 간단하게 임계구역 문제 해결할 수 있다.

-> 코드를 interrupt 당하지 않고 한번의 CPU cycle 안에 해결하도록 함

Example:

• test_and_set()

• compare_and_swap()

(OS마다 함수명, 수행에 차이가 있음)

test_and_set Instruction

프로세스 Pi의 구조는 다음과 같다.

중요한 점은 코드가 원자적으로 실행되기에 만약 두 test_and_set() 명령어가 (서로 다른 코어에서) 동시에 실행되더라도 임의의 순서로 순차적으로 실행된다.(내용물이 교차되면서 실행되지 않고 함수 단위로 순차적으로 실행된다)

만약 기계가 test_and_set() 명령어를 지원하면 불리언 변수 lock을 선언하여 false로 초기화해주어 상호 배제 구현이 가능하다.

하지만 Bounded-waiting은 만족하지 않는다. critical section에 접근하는 프로세스가 여러 개일 경우 무한대기 할 수 있기 때문이다.

compare_and_swap(CAS) Instruction

오로지 표현식 (*value == expected)이 true일 때만 피연산자 value를 new_value로 설정해준다. CAS는 언제나 value의 원본 값을 반환한다.

중요한 건 원자적으로 실행되므로 두 CAS가 동시에 (서로 다른 코어에서) 실행되더라도 임의의 순서로 순차적으로 실행된다는 것이다.

1) 전역 변수(lock)를 선언해놓고 0으로 초기화한다.

2) compare_and_swap()을 처음 호출한 프로세스가 lock을 1로 설정한다.

3) 원래 lock의 값은 예상값 0과 같아야 했으므로 임계구역에 입장한다.

4) 이후에 compare_and_swap() 호출할 경우 lock은 이제 예상값 0과 같지 않으므로 실패한다.

5) 프로세스가 임계구역 벗어나면 lock을 다시 0으로 설정하여 다른 프로세스가 임계구역 들어 갈 수 있도록 해준다.

이 또한 상호배제 조건은 만족하지만 Bounded-waiting은 만족하지 않는다.

Bounded-waiting Mutual Exclusion with compare_and_swap

다음 코드는 compare_and_swap() 명령어를 사용하면서 모든 임계구역 조건을 만족하는 알고리즘이다. (단점 해결)

공통 데이터

• Boolean waiting[n];

• int lock;

-> waiting[i]는 FALSE로 초기화

-> lock은 0으로 초기화

key의 값은 오로지 compare_and_swap()이 실행 되어야 0이 된다.

compare_and_swap()을 실행할 첫번째 프로세스가 key == 0임을 확인한다. 나머지는 대기해야한다.

상호 배제 조건을 만족함을 보이려면 프로세스 Pi가 오로지 waiting[i] == false이거나 key == 0일 때만 임계구역에 들어갈 수 있다는 점을 들면 된다. 변수 waiting[i]은 오로지 다른 프로세스가 임계구역을 나가야만 false가 될 수 있다. 유일하게 waiting[i]은 false가 되어 상호 배제 조건을 만족한다.

진행 조건이 만족함을 보이려면 임계구역을 탈출하는 프로세스가 lock을 0으로 설정해주거나 waiting[j]를 false로 된 것을 확인하면 된다.
( 둘 다 대기 중이던 한 프로세스를 임계구역에 입장할 수 있게 해준다.)

한정 대기 조건 만족하는지 보려면 프로세스가 임계구역 탈출할 때 waiting 배열을 순환 순서(i + 1, i + 2, …, n - 1, 0, …, i - 1)로 쭉 훑는다.
이 순서에서 가장 처음으로 입장 구역에 있는 프로세스를 다음으로 임계구역에 들어갈 프로세스로 지정해주면된다.(waiting[j] = true)
임계구역 들어가려고 대기하는 모든 프로세스는 n - 1 번 내로 실행된다.

Atomic Variables

임계구역 문제를 해결하는데 사용되는 다른 도구로는 원자적 변수 atomic variable가 있다. 원자 변수는 기본 데이터 유형(예: 정수, 부울)에 대한 원자 연산을 제공한다.

딘일 변수 값이 갱신 중일 때 자료 간 경합이 발생할 수 있는 상황(race condition)에서 mutual exclusion(상호배제)를 보장해줄 때 원자적 변수를 사용한다. (e.g. counter++, counter--)

원자 변수에 액세스하고 조작하는 함수는 종종 compare_and_swap 작업을 사용하여 구현된다.

Example: 원자적 정수열 증가 함수

Mutex Locks

하드웨어 기반 솔루션은 복잡하고 일반적으로 애플리케이션 프로그래머들은 액세스할 수 없다. 대신 OS 설계자는 중요한 섹션 문제를 해결하기 위한 소프트웨어 도구를 구축한다.

가장 간단한 도구가 mutex lock(mutual exclusion)이다. mutex lock으로 임계구역을 보호하여 경합 조건을 방지한다. 즉, 프로세스는 임계구역에 들어가기 전에 반드시 락을 얻어야 임계구역에 들어갈 수 있고, 나갈 땐 락을 반납하고 나가야 한다.

acquire() 함수로 락을 얻고, release() 함수로 반납한다. 두 함수는 반드시 atomic으로 호출된다.

• 일반적으로 하드웨어 원자 명령어(CAS 작업)를 통해 구현된다.

상호배제 락에는 available이라는 boolean 변수가 있어 락이 사용 가능한지 여부를 알 수 있다. 지금 사용할 수 있으면 acquire() 호출이 성공하여 이제 락은 사용할 수 없게 된다.

(사용자가 반납할 때까지 다른 프로세스가 락 받으려는 시도가 막힌다)

단점: busy waiting

어떤 프로세스가 임계구역에 이미 들어가있으면 다른 프로세스는 반드시 acquire()을 얻기 위해 계속해서 루프를 돌려야 한다. 이렇게 되면 다른 프로세스가 좀 더 생산적인 일에 사용할 수도 있는 CPU 사이클을 busy waiting 하는데 낭비하는 꼴이 된다.

따라서 mutex lock은 락이 사용 가능할 때까지 "돌린다 spin"는 점에서 spinlock이라고도 부른다.

Semaphore

mutex lock과 비슷하게 작동하면서도 프로세스를 좀 더 복잡하게 동기화할 수 있도록 해주는 Semaphore에 대해 살펴보자.

세마포어 semophore S는 정수 변수로, 초기화할 때 말고는 오로지 두 가지 표준 원자적 연산 wait()과 signal()로만 접근이 가능하다.
(수행하는동안 interrupt 당하지 않음)

• wait() 연산

  • Originally called P()

• signal() 연산

  • Originally called V()

세마포어라는 정수 값을 수정하려면 wait()이나 signal() 연산을 원자적으로 실행해야 한다.

즉, 만약 한 프로세스가 세마포어 값을 수정하면, 그 어떠한 다른 프로세스도 동시에 같은 세마포어 값을 수정할 수 없다.

추가적으로 wait(S)의 경우 정수값 S(S ≤ 0) 테스트하는 것과 마찬가지로 가능한 모든 수정사항들(S--)도 반드시 인터럽트 없이 실행이 되어야 한다.

Semaphore Usage

semaphore가 어떻게 사용될 수 있는지 보자.

• Counting Semaphore: 정수 값에 한계가 없다.

• Binary Semaphore: 정수 값은 오로지 0 또는 1이다. (뮤텍스 잠금과 동일)

카운팅 세마포어로 한정된 개수의 개체로 구성된 자원에 접근을 제어할 수 있다. (세마포어는 사용 가능한 리소스 수로 초기화 된다.)

자원을 쓰려는 각 프로세스는 세마포어에 대해 wait() 연산을 해주어야 한다(즉, 카운트를 감소). 프로세스가 자원을 반납하면 signal() 연산을 수행한다(카운트를 증가). 세마포어의 카운트가 0이 되면 모든 자원이 사용된 것이다. 이후에 프로세스가 자원을 사용하려고 하면 카운트가 0보다 커질 때까지 막히게 된다.

또한 세마포어는 다양한 동기화 문제를 해결할 수 있다.

Example:

• 동시에 실행 중인 프로세스 P1은 구문 S1을 갖고, P2는 구문 S2를 갖는다.

• S2는 반드시 S1이 완료되어야만 실행이 가능하다.

• P1과 P2가 공통된 공유 세마포어 synch를 공유하고, 이는 0으로 초기화 한다.

synch가 0으로 초기화되었기 때문에 P2 입장에서는 P1이 signal(synch)를 호출해야만 S2를 실행할 수 있으므로, S1은 완료가 된 상태이다.

Semaphore Imple. with no Busy Waiting

• 각 세마포어에는 연결된 ready queue가 있다.

• 각 세마포어에는 정수 값과 대기 중인 프로세스 list를 가진다.

OS에서 기본 시스템 호출로 제공되는 두 가지 연산이 있다.

• sleep: 자기를 호출한 프로세스를 중단시킴
  (작업을 호출하는 프로세스를 적절한 ready queue에 배치)

• wakeup: 중단된 프로세스의 실행을 재개해줌.
  (ready queue에서 프로세스 중 하나를 제거하고 ready queue에 배치)

busy waiting 문제를 해결하려면 정의를 수정해야 한다.

프로세스가 wait() 연산을 실행할 때, 세마포어 값이 양수가 아니면, 대기해야한다. 이때 busy waiting을 하는게 아니라, 프로세스가 스스로를 중지시킨다. (sleep)

(세마포어 값이 음수면 그 절대값이 해당 세마포어에 대기 중인 프로세스의 개수이다.)

이때 중지 연산은 프로세스를 세마포어에 대한 대기 큐로 보내어 프로세스의 상태를 대기 상태로 바꾼다는 뜻이다. 그럼 제어권이 CPU 스케줄러로 넘어가서 실행할 다른 프로세스를 선택하게 된다.

중단된 프로세스는 세마포어 S를 ready queue에서 대기하므로 다른 프로세스가 signal() 연산을 실행할 때 재시작되어야한다.

프로세스는 wakeup() 연산에 의해 재시작되어 프로세스를 대기 상태에서 준비 상태로 바꿔준다. 그럼 프로세스가 ready queue로 올라가게 된다.

이 정의에 따라 세마포어를 재정의하면 다음과 같다.

Semaphore Implementation

wait() 및 signal()은 원자적으로 실행되어야 한다.

• 두 개의 프로세스가 wait()를 실행할 수 없도록 보장해야한다.

• 두 프로세스가 동시에 같은 세마포어에서 wait() 및 signal()을 실행할 수 없도록 보장해야한다.

• 따라서 구현은 wait 및 signal 코드가 임계 영역에 배치되는 critical section problem이 된다.

busy waitng in wait() and signal()

critical section이 짧은 경우 busy waiting의 범위가 제한되어있다.

하지만 응용 프로그램이 critical section에서 많은 시간을 보낼 수 있는 경우 매우 비효율적입니다.
-> 이 경우 Busy Waiting을 극복하기 위해 작업을 수정한다.

Monitors

세마포어를 잘못 사용하면 감지하기 어려운 타이밍 오류가 발생할 수 있다.

세마포 연산의 잘못된 사용:
binary semaphore mutex 공유 (1로 초기화됨 = lock이 걸린 상태)

첫 번째 코드 상황은 여러 프로세스가 동시에 임계구역에서 실행 될 수 있으므로 상호 배제 조건을 위배한다.

두 번째 코드 상황에서 프로세스는 wait()에 대한 두 번째 호출을 영구히 막아버려 세마포어를 더 이상 사용할 수 없게된다.

이러한 오류를 처리하기 위한 간단한 고급 언어 동기화 구성: monitor 유형

Monitor Type

• 모니터 형(Monitor Type)은 프로세스 동기화를 위한 편리하고 효과적인 메커니즘을 제공하는 ADT(추상 데이터 유형)이다.

• 모니터 형은 변수에서 작동하는 내부 변수 및 함수 선언문을 갖고 있다.

• 로컬 변수는 로컬 함수에서만 액세스할 수 있습니다.

• 모니터 내에서 한 번에 하나의 프로세스만 활성화되도록 한다.
  -> 따라서 프로그래머는 동기화 제약 조건을 명시적으로 코딩할 필요가 없다.

Schematic view of a Monitor

Condition Variables

모니터 생성은 지금까지 공부한 걸로 봤을 땐 몇가지 동시성 scheme에 적용하기엔 충분히 강력하지 않다. 그렇기에 추가적인 동기화 메커니즘이 필요한데, 이는 condition 생성으로 해결한다. 조건형 변수를 하나 이상을 정의해야 한다.

조건 유형의 하나 이상의 변수

• condition x, y;
  -> x: 생성자가 기다리고 있는 것
  -> y: 소비자가 기다리고 있는 것

조건 변수에는 두 가지 작업이 허용된다.

• x.wait()
  -> wait 작업을 호출하는 프로세스는 x.signal()까지 일시 중지된다.

• x.signal()
  -> 정확히 하나의 일시 중단된 프로세스를 다시 시작한다.
  -> 중단된 프로세스가 없으면 아무런 영향도 주지 않는다.

Condition Variables Choices

프로세스 P가 x.signal()을 호출하고 프로세스 Q가 x.wait()에서 일시 중지된 경우 다음에 어떤 일이 발생하는가?

-> Q와 P는 병렬로 실행할 수 없다. Q가 재개되면 P는 기다려야 한다.

그러나 개념적으로 두 프로세스 다 실행을 지속할 수 있는 두 가지 가능성이 존재한다.

• Signal and wait(신호 후 대기): P가 Q가 모니터를 벗어나거나 다른 조건을 대기할 때까지 대기.
  -> 깨워준 프로세스가 대기

• Signal and continue(신호 후 지속): Q는 P가 모니터를 벗어나거나 다른 조건을 기다릴 때까지 대기.
  -> 깨어난 애가 P가 나갈때까지 대기

Concurrent Pascal 타협에서 구현된 모니터 [이 두 선택지의 절충안]
->P 실행 신호는 즉시 모니터를 떠나고 Q는 다시 시작.

Java, C#, Erlang을 포함한 다른 언어로 구현 가능하다.

Monitor Implementation Using Semaphores

모니터를 세마포어를 통해 구현해보자.

각 모니터마다 이진 세마포어 mutex를 두어 상호 배제 보장한다.

프로세스는 모니터에 들어가기 전에 반드시 wait(mutex)를 실행해야 하고, 모니터 나갈 때 반드시 signal(mutex)를 호출해야 한다.

각각의 외부 함수 F는 다음으로 대체된다.

신호 후 대기를 사용한 예이다. 송신 프로세스가 반드시 재개된 프로세스가 떠나거나 대기할 때까지 대기해야하기 때문에 추가적인 이진 세마포어 next(0으로 초기화)가 필요하다.

(생성자가 소비자를 개운다음 스스로 대기)

송신 프로세스는 next를 사용하여 자기 스스로를 중단시킬 수 있다. 정수형 변수 next_count로 next에서 중단된 프로세스의 개수를 얻을 수 있다.

이렇게 되면 모니터 내의 상호 배제가 보장된다.

Monitor Implementation with Condition Variables

각 조건 변수 x마다 이진 세마포어 x_sem과 정수형 변수 x_count를 두고 둘 다 0으로 초기화한다.

• x_sem: 조건을 대기하는 프로세스들의 queue

• x_count: 조건을 대기하는 프로세스 수

x.wait() & x.signal() 작업은 다음과 같이 구현될 수 있다.

Resuming Processes within a Monitor

여러 프로세스가 조건 x에서 대기열에 있고 x.signal()이 실행된 경우 어떤 프로세스를 재개해야 하는가?

-> FCFS는 종종 적절하지 않다.

x.wait(c) 형식의 조건부 대기 구성

-> c는 우선순위 숫자이다.
-> 가장 낮은 번호(가장 높은 우선 순위)의 프로세스가 다음으로 예약된다.

Liveness

여러 개의 프로세스가 오로지 한 프로세스에서 발생한 이벤트를 무한정 대기하는 일이 발생할 수 있다. 이러한 상태에 들어오게 되면 프로세스가 deadlock 상태에 있다고 한다.

-> 서로 다른 프로세스가 풀어주길 기다리지만 서로 lock 되서 못풀고 멈추는 경우이다.

(여기서 말하는 이벤트란 singal() 연산의 실행을 의미)

동기화 도구로 임계구역으로의 접근을 조정하게 되면 프로세스가 무한정 임계구역에 입장하기를 대기하게 되는 문제가 발생할 수 있다.

Liveness란 프로세스가 실행 수명 주기에서 제대로 진행이 되도록 시스템이 보장하는 속성을 의미한다. 위에서 언급한 deadlock 발생은 "liveness failure"의 한 예시이다.

두 프로세스 P0와 P1이 각각 1로 설정된 두 세마포어 S와 Q를 가진다고 가정해보자.

P0이 wait(S)을 실행하고, P1이 wait(Q)를 실행한다고 가정한다. P0이 wait(Q)를 실행하면 반드시 P1이 signal(Q)를 실행할 때까지 대기해야한다. 마찬가지로 P1이 wait(S)를 실행하면 P0가 signal(S)를 실행할 때까지 대기해야한다.

이렇게 되면 signal() 연산은 절대 실행되지 않으므로 P0와 P1은 데드락 상태이다.

Starvation(기아): 무기한 차단
-> 중단된 세마포 큐에서 프로세스를 제거할 수 없다.
(프로세스가 멈추게 되는 상황)

Priority Inversion(우선순위 역전): 우선 순위가 낮은 프로세스가 우선 순위가 높은 프로세스에 필요한 잠금을 보유하는 경우 스케줄링 문제

-> 우선 순위 상속 프로토콜을 통해 해결

수정할 부분이 있으면 댓글로 알려주세요 :)