Chap 5. Concurrency : Mutual Exclusion and Synchronization

Multiple Processes

• Multiprogramming
  • 메모리안에 여러 프로세스가 동시에 들어있고 프로세스를 동시에 또는 번갈아 실행하는 상황
• Multiprocessing
  • CPU가 여러 개 있는 상황
• Distributed processing
  • 네트워크로 연결된 여러 컴퓨터들 위에 하나의 OS 레이어로 하나의 시스템처럼 사용

프로세스를 동시에 실행하는 경우 오버래핑 , CPU가 하나인 상황에서 서로 번갈아가면서 실행하는 경우 인터리빙 이라고 한다.

이때 발생하는 문제가 Concurrency 이다.

Race Condition

공유자원을 서로 읽기/쓰기할 때 순서가 어떻게 될지 모르는 상황.

누가 마지막으로 작업하냐에 따라 결과가 바뀐다.

CPU가 하나인 경우에도 프로세스들은 서로 번갈아가면서 인터리빙 상태에서 실행한다.

Race Condition을 없애는 방법

• 좋은 알고리즘 사용
• 하드웨어 Instruction
• OS가 제공하는 동기화 툴 사용

Mutual Exclusion : Software Approaches

동시에 실행시키지 않는 코드 = Critical Section

즉, 한 프로세스의 Critical Section 코드가 진행되는 동안 다른 프로세스의 Critical Section 코드는 실행되지 않아야 한다.

First attempt (turn)

• 공유 변수 turn 사용
  • turn 값이 자신에게 해당한다면, while문을 빠져나와 Critical Section 에 진입
• Mutual Exclusion O
  • P0가 Critical Section 진입
    • turn = 0 확인
    • Critical Section 시작
  • P1도 Crtical Section 진입
    • turn = 1 확인 ⇒ P0가 Critical Section 실행중이므로 turn = 0 이라서 Critical Section 실행 X
• 문제
  • Busy Waiting = Spin Waiting
    • 아무것도 안하고 기다리는 것이 아니라 CPU를 잡고 기다린다.
  • 상대방이 작업해야 내가 작업할 수 있다.
    • 시간 당 실행 횟수가 다를 경우 문제 발생
    • 즉, 상대편이 들어가고 싶지 않으면 나도 못들어간다.

Second attempt (flag)

• 2개의 flag 사용
• flag는 Critical Section 에 진입할 의사가 있는지 나타낸다.
• Mutual Exclusion이 지켜지지 않는다.
  • 두 프로세스는 오버래핑 또는 인터리빙된 상태로 실행된다.
  • 타임아웃이 어디서 발생할지 모른다 = 인터리빙 발생
    • while문 빠져나오자마자 타임아웃 발생
      • 둘 다 Critical Section 진입

Mutual Exclusion

1. P0 Critical Section 진입
   1. flag[1] = false 확인
   2. flag[0] = true
   3. Critical Section 진입
2. P1도 Critical Section 진입
   1. flag[0] = false 확인 ⇒ flag[0] = false임을 확인할 수 있는 시점은 P0가 flag[1] = false를 확인한 직후이다. ⇒ 가능
   2. flag[1] = true

Third attempt (flag)

• 자신의 flag를 true로 만들고 상대편 flag 확인
  • 상대편 flag가 false면 Critical Section 에 들어간다.
• Mutual Exclusion이 지켜진다.
  • P0가 Critical Section 에 진입 = 상대 flag가 false
    • Critical Section 중간에 flag를 false로 바꾸는 과정은 없다.
  • P1이 동시에 Critical Section 진입하려면 flag[0]이 false인 걸 확인해야 한다.
  • 하지만 flag[0]은 Critical Section 동안 계속 true

Mutual Exclusion 증명방법

두 프로세스가 동시에 작업하는 경우가 존재하는 경우가 없다는 것은 모순을 보여준다.

1. P0가 Critical Section 진입
   1. flag[0] = true
   2. flag[1] = false 확인
   3. Critical Section 진입
2. P1도 Critical Section 코드 동시 실행
   1. flag[1] = true
   2. flag[0] = false 확인 ⇒ flag[0]이 false인 시점은 flag[0] = true로 만들기 직전이다. 그런데 P1은 flag[1] = true로 만든 다음에 flag[0] = false인지 확인한다. ⇒ P1의 flag는 true인 동시에 false이여야 P0와 P1가 동시에 Critical Section에 진입할 수 있다.

• DeadLock 발생 가능
  • 둘 이상의 프로세스가 상대편을 기다린다.
  • 타임아웃이 flag를 True로 설정한 직후 발생
  • Deadlock이 걸릴 확률은 낮기 때문에 위험하다.

Forth attempt (flag)

• flag를 true로 먼저 설정
• 상대편 flag가 true면 자신의 flag를 0으로 바꾼다.
  • 상대편도 while문을 돌고 있을 수 있기 때문에 양보한다.
• false로 바꾼 사이에 상대편에서 나의 flag가 false로 바뀐 것을 확인하고 Critical Section 에 들어가서 작업을 하고 나오면 들어간다.
• Mutual Exclusion이 지켜진다.
  • Critical Section 에 들어가는 사람은 상대 flag가 false인 것을 확인하고 들어간다.

Mutual Exclusion 증명

1. P0가 Critical Section 진입
   1. flag[0] = true
   2. flag[1] = false 확인
   3. Critical Section 진입
2. P1도 Critical Section 진입
   1. flag[1] = true
   2. flag[0] = false 확인 ⇒ flag[0] = false인 시점은 flag[0] = true로 만들기 직전 또는 while문 내에서 flag[0] = false로 바뀌었을 때이다. 그런데 P1은 flag[1] = true로 만든 이후 flag[0] = false인지 확인한다. P0도 flag[1] = false임을 확인하고 들어가므로 동시 진입은 불가능하다.

• DeadLock X
• LiveLock이 발생 가능
  • 한문장씩 서로 타임아웃
  • DeadLock보다 가능성이 적다.

Dekker`s Algorithm

• Mutual Exclusion O
  • 들어가는 사람은 true, 상대편은 false일 때만 Critical Section 에 진입한다.

Mutual Exclusion 증명

1. P0 Critical Section 진입
   1. flag[0] = true
   2. flag[1] = false 확인
   3. Critical Section 진입
2. P1 Critical Section 진입
   1. flag[1] = true
   2. flag[0] = false 확인 ⇒ 가능한 라인은 첫문장 실행 전 또는 while문 내에서 flag[0] = false로 바꾼 이후이다. 하지만 flag[1] = true로 바꾼 이후 flag[0] = false인지 확인한다. 따라서 flag[1]은 false인 동시에 true이여야만 동시에 Mutal Exclusion에 진입할 수 있다.

• DeadLock X
• LiveLock X
• 두 사람 다 동시에 양보를 하는 것이 아닌 두 사람 중 한 사람만 양보한다.
  • turn 값으로 양보할 사람을 정한다.
  • turn = 0이면, 0번이 양보받는다.
  • 양보하는 사람은 안쪽 while문을 돈다.
• flag는 Critical Section 실행 해야하는지 여부

💡 어디에서 타임아웃이 발생할지 모른다.

1. Critical Section 에 들어갔다가 나온 프로세스가 상대편이 기다리고 있음에도 불구하고 다시 Critical Section 에 진입하는 경우가 있을까?
   1. P0의 Critical Section이 실행되는 동안 P1은 if문 내의 flag[1]=false인 상태에서 타임아웃
   2. P0는 Critical Section이 끝나자마자 타임아웃
   3. P1은 while (turn == 0) 을 돌다가 타임아웃
   4. P0는 다시 while (flag[1]) 진행 ⇒ P1은 flag[1] = false로 만든 직후의 while문에서 타임아웃됐으므로 flag[1] = false인 상태로 유지
   5. P0 Critical Section 재진입
2. 바깥쪽 while문을 돌다가 안쪽 while 문을 돌게되는 상황이 있을까?
   1. 불가능하다. 바깥쪽 while문에서 안쪽 while문으로 넘어가려면 turn값이 상대방으로 넘어가야 한다. turn을 넘겨주는 작업은 본인의 Critical Section이 끝난 후에만 가능하다.
3. 안쪽 while문을 돌다가 바깥쪽 while 문을 돌게되는 상황이 있을까?
   1. P0의 Critical Section 이 끝나고 turn = 1까지만 실행하고 타임아웃
   2. P1은 안쪽 while문 탈출하지만, flag[0] = false가 실되지 않았으므로 바깥 while문 반복

Critical Section 에 무한하게 재진입하는 상황이 있을까?

존재하지 않는다. 재진입하는 데에 횟수 제한이 있다. 만약 P0가 한 번 재진입을 한 이후에는 turn값은 1로 계속 유지된다.

그러다 P0에서 타임아웃이 나면은 P1은 자신의 flag를 true로 다시 만들고 외부 반복문을 돌게된다.

P1에서 타임아웃 이후 P0로 돌아오게 되면 P0는 결국 while (flag[1]) 에 걸리게 되고, turn값은 1 이므로 자신의 flag를 false로 바꾸고 기다리게 된다.

Peterson`s Algorithm

• Peterson은 Dekker와 다르게 진입하기 전에 자신의 flag를 true로 만들고 turn을 상대편에게 준다.
• turn을 상대에게 줘도 상대편이 Critical Section 에 진입할 의사가 없으면 자신이 들어간다.
• 동시에 실행되어도 결국 turn값은 0 또는 1이므로 한쪽만 들어가게 된다.
• while (flag[1] && turn == 1)
  • flag[1] : 상대편이 Critical Section에 진입할 의사가 없으면 Critical Section에 진입
  • turn == 1 : 서로 Critical Section에 들어가려고 할 때 궁극적으로 한 사람이 Critical Section에 들어가는 사람이 누군지 확인
• 재진입 X
  • 진입 전 상대 flag와 turn값이 상대편인지 확인 ⇒ 상대방이 기다리고 있기 때문에 상대편 flag = true ⇒ P0가 다시 while문을 검사했을 때 flag[1] = true이고, turn은 P0가 1로 설정하기 때문에 재진입할 수 없다.
• Mutual Exclusion O
  • 자신의 turn값은 상대방만 바꿀 수 있다.
• 교대 진입 불필요
  • 프로세스가 C.S 진입을 원하는데 상대편에서 진입할 의사가 없다면 계속 들어갈 수 있어야 한다.
• Mutual Exclusion이 지켜짐
  • Mutual Exclusion이 지켜지지 않는다 = 동시에 C.S 진입
  • P1이 동시에 C.S에 진입하려면 f[0] = false or turn = 1임을 확인해야 한다.
    • P1이 둘 중 어느것을 확인하고 C.S에 들어가든지 간에 C.S 구간에서는 f[1] = true이고 turn은 1이다. 그런데 P0가 C.S에 들어가려면 f[1] = false or turn = 0이여야 하므로 가능하지 않다.

Mutual Exclusion 증명

1. P0 Critical Section 진입
   1. flag[0] = true
   2. turn = 1
   3. flag[1] = false 또는 turn = 0인지 확인
   4. Critical Section 진입
2. P1 Critical Section 진입
   1. flag[1] = true
   2. turn = 0
   3. flag[0] = false or turn = 1인지 확인 ⇒ 맨 처음 또는 P0가 turn = 1 실행한 이후에 가능 ⇒ 맨 처음이면 P0가 Critical Section 진입 불가 X/P0가 turn = 1 실행한 이후에 확인 → flag[1] = true && turn = 1인 상황이므로 P0가 Critical Section 진입 불가

• Deadlock 발생 X
  • turn 값은 1 또는 0 이기 때문 에 둘 다 while문을 돌 수 없다.
• Livelock 발생 X

3가지 문제점

• Busy Waiting
• 복잡성
• 2개의 프로세스만 가능

Process Interaction and Control Problems

• 프로세스 Interaction
  • 리소스를 차지하기 위한 Competetion
  • 공유 데이터 share
  • 메시지를 주고받으며 통신

이렇게 세가지 형태의 Interaction이 발생하다보면 문제들이 발생한다.

• Mutual Exclusion
  • Critical Section
  • Data coherence : 데이터를 바꾸는 순간 모든 캐싱 값과 메모리 값을 바꾸는 작업이 이루어져야 한다.
• Deadlock
• Starvation
  • 어떤 프로세스는 자원을 쉽게 차지하는 반면 어떤 프로세스는 계속 경쟁에서 밀려 CPU를 차지하지 못하는 상황

Requirements for Mutual Exclusion

• Mutual Exclusion이 지켜져야 한다.
  • Critical Section은 한 번에 한 사람만 실행할 수 있어야 한다.
• 다른 사람의 Critical Section 진입 여부가 나의 진입 여부에 영향을 주면 안된다.
• Deadlock이나 Starvation이 발생하면 안된다.
• Critcal Section에 진입하려는 다른 프로세스가 없다면 기다리는 상황이 있어서는 안된다.
• 프로세스간의 상대적인 속도에 대한 가정이나 프로세스의 개수에 대한 가정을 해서는 안된다.

Dekkers Algorithm과 Petersons Algorithm이 가지는 문제점

• Busy Waiting
• 복잡성
• 프로세스 개수의 제한

Approaches for Mutual Exclusion

• 소프트웨어 접근
  • Dekker`s Algorithm
  • Peterson`s Algorithm
• 하드웨어 Instruction을 사용한 접근
  • Busy Waiting 발생
  • 복잡성 해결
  • 프로세스 개수 문제 해결
  • 소프트웨어 접근에서는 없는 문제 발생
  • 방법
    • Compare&Swap Instruction
    • Exchange Instruction
• OS 레벨 또는 프로그래밍 언어 레벨에서 제공하는 툴
  • OS가 참여해서 프로세스 Block → Busy Waiting 문제 해결
  • 복잡성 해결
  • 프로세스 개수 문제 해결
  • 하드웨어 접근에서 발생하는 문제 해결
  • 방법
    • 세마포
    • 모니터

Compare&Swap Instruction

• 함수가 아닌 하드웨어 Instruction이다.
  • 하드웨어 Instruction = Fetch - Execution 사이클로 이루어진다.
  • 코드를 실행하는 것이 아니라 하드웨어적으로 작업한다 = 인터럽트가 걸릴 수 없다.
• word = 어떤 저장 장소의 주소
• 기존의 word값을 return
• atomic instruction
  • fetch-execution 한 사이클 내에서 실행되므로 어떠한 인터럽트 처리가 되지 않는다.
  • Instruction이 실행되는 동안 word에는 다른 프로세스나 쓰레드가 접근하지 못하게 Block 된다.

Compare&Swap을 통한 Critical Section 구현

• bolt 공유 변수 사용
• while (compare_and_swap(&bolt, 0, 1) == 1)
  • Critical Section에 누군가 진입해있다면 return 1
  • Critical Section에 아무도 없다면 return 0 & bolt 값을 1로 바꾼다.
• testval = 0
  • bolt에 저장된 값이 0과 같은지 비교 = Critical Section에 아무도 없는지 확인
• Critical Section을 나와서 bolt 값을 0으로 바꾸고 CPU를 계속 잡고 Compare&Swap 을 시도하면 재진입할 수 있다.
• critical Section에 진입을 위해 대기 중인 프로세스가 while문을 무한 반복하는 경우가 있다 ⇒ Starvation

Exchange Instruction

• 하드웨어 장치를 사용하는 Instruction 이기 때문에 중간에 인터럽트가 걸리지 않는다.
• atomic Instruction
• 여러 개의 Critical Section을 구현하는 경우, 여러 개의 bolt 값 사용이 필요하다.

Exchange Instruction을 통한 Critical Section 구현

• bolt = 0 ⇒ Critical Section에 아무도 안들어가있다.
• exchange 후 keyi = 0이면, Critical Section에 아무도 없음을 뜻한다.
• exchange에 들어가기전에 key값을 1로 놓고 시작해야 한다.
• 일시적으로 두 프로세스의 keyi값이 0이 되는 경우가 발생한다 ⇒ 두 프로세스가 동시에 Critical Section 진입 X, Critical Section에서 방금 나온 프로세스와 그 이후 바로 Critical Section에 들어간 프로세스면 가능하다.

Hardware Mutual Exclusion

• 장점
  • 프로세스 개수 제한 X
  • 복잡성 X
  • multiple Critical Section 지원
• 단점
  • busy waiting
  • starvation
    • 무한대로 Critical Section에 진입가능하다.
  • Deadlock 발생 가능
    • Critical Section이 1개인 상황에서는 발생 X, 즉 위 코드에서는 발생하지 않는다. Multiple Critical Section에서 발생
  • 소프트웨어 접근과 비교
    • Dekker 알고리즘은 Starvation이 일어날 수 있지만 횟수가 제한되어 있다.
    • Peterson 알고리즘에서는 Starvation 발생 X

Semaphore

OS가 mutal exclusion을 비롯한 동기화 문제를 해결하기 위한 대표적인 툴이다.

구조체 변수

정수 변수와 큐를 가지고 있다.

정수 변수의 값을 이용해서 프로세스를 기다리게 하거나, 기다리는 프로세스한테 시그널을 준다.

세마포의 3가지 오퍼레이션

• 세마포 초기화(음수값으로 초기화 X, 0이나 양수값으로 초기화해야한다.)
  • 음수값 = Blocked 큐에서 기다리고 있는 프로세스의 숫자를 나타낸다. 실제 Blocked 큐에서 기다리는 프로세스가 없는데 음수값으로 초기화하면 semaphore signal 연산이 제대로 작동하지 않는다.
• SemWait : 세마포 값을 1개 뺀다. 그리고 결과값이 0보다 작으면, 뺀 프로세스를 블락시킨다.
• SemSignal : 세마포값을 1 증가시킨다. 그리고나서 결과값이 0보다 작거나 같은 큐에 대기하고 있는 프로세스가 있다면 언블락시킨다. 0보다 큰 경우에는 대기하고 있는 프로세스가 없다.
• 세마포는 일반적인 산술, 논리연산을 사용할 수 없다. 지금 세마포값이 얼만지 알아볼 수 있는 연산이 없다.

Semaphore Primitives

세마포는 변수값과 연결된 큐를 가지고 있다.

wait 연산 실행 시 값이 0보다 크거나 같으면 통과하고 그렇지 않으면 큐에 들어간다.

• semWait
  • 값에 따라 Block이 될 수도 있고 안될 수도 있다.
• semSignal
  • 값에 따라 Block되어 기다리는 프로세스 중 하나를 레디큐로 보낸다.

Example of Semaphore Mechanism

세마포의 음수값은 Blocked 큐에 들어있는 프로세스의 개수를 의미한다.

세마포가 양수일 때는 Wait 연산을 해도 Block되지 않고 통과한다. 즉, 양수값은 통과할 수 있는 프로세스의 개수를 의미한다.

• S > 0 : n 명이 semWait을 통과할 수 있다.
• S ≤ 0 : semWait을 통과할 수 없고, n 명이 semWait을 통과하지 못해서 Blocked 큐에 존재한다.

이러한 Semaphore를 Counting Semaphore라고 한다.

Strong/Weak Semaphore

semSignal을 실행한 사람이 큐에 있는 프로세스 중 하나를 깨운다. 어떤 프로세스를 깨울지는 시스템마다 다르다.

• Strong Semaphore : FIFO
• Weak Semaphore : 다 다르다.

Binary Semaphore Primitives

0 또는 1 값을 가진다.

현재 대기하는 프로세스 숫자나, 몇개 프로세스가 통과할 수 있는지에 대해 알 수 없다.

1이 아니고 값이 0인 경우 해당하는 프로세스를 큐에 넣고 Block 시킨다.

1이면 semWait 통과, 0인 경우 Block 된다.

• semSignal
  • 큐가 비어있을 때(실행시킬 프로세스가 없는 경우)만 값을 1로 만들어준다.
  • 비어있지 않다면 큐에 들어있는 프로세스 중 하나를 Ready 큐에 넣는다.

Mutual Exclusion Using Semaphore

Semaphore는 초기값 설정이 중요하다. 설정값에 따라 몇 명이 진입하는지 정해진다.

Critical Section에 나온후 semSignal 연산을 실행해서 Blocked 큐에 들어있는 프로세스 중 하나를 뽑는다.

Binary Semaphore를 이용해도 똑같다.

Producer/Consumer Problem

• 두 종류의 프로그램
  • Producer
    • 데이터를 만들어서 버퍼에 넣는다.
  • Consumer
    • 버퍼에서 데이터를 가져간다.

동시에 여러 프로세스 레디 큐에 있는 동일한 데이터를 가져가거나 데이터를 쓸 수도 있다. 따라서 어디에 데이터를 저장하거나 프로세스를 집어넣을지는 한 번에 한 사람만 결정해야 한다.

Producer는 버퍼에 데이터를 집어넣기 때문에 가득 차 있으면 데이터를 집어넣을 수 없으므로 기다려야 한다. Consumer는 데이터가 없으면 기다려야 한다.

버퍼가 꽉 찼다는 정보와 비어있다는 정보는 어떻게 알까?

Bounded Buffer

in : Producer가 데이터를 저장할 위치

out : Consumer가 가져갈 데이터의 위치

버퍼가 비거나 꽉 찬 경우 둘 다 in과 out이 같은 위치에 있게 된다.

Functions in a Bounded Buffer

버퍼가 빈 상황과 꽉 차는 상황을 구분하기 위해 Producer는 (in + 1) % n == out 인 상황으로 체크한다.

위 코드는 이해하기 위한 코드이고, 실제 Semaphore에서는 Busy Waiting 없이 해결한다.

Bounded Buffer using Semaphores

Semaphore는 버퍼를 가득 채울 수 있다.

• Semaphore
  • s : Critical Section → in, out값을 동시에 수정하지 않는다.
  • n : 버퍼에 들어있는 데이터의 개수 = 버퍼가 비었을 때 Consumer가 대기하는 장소
  • e : 버퍼의 비어있는 자리 수 = Producer가 버퍼가 꽉 찼을 때 대기하는 장소
• producer
  • produce() : 데이터 생성
  • append() : 데이터를 원하는 위치에 집어넣는다.
• consumer
  • take() : 데이터를 가져간다.
  • consume() : 데이터 사용

만약 semWait(e) → semWait(s)가 아닌 semWait(s) → semWait(e)순서로 진행된다면?

Deadlock이 발생한다.

버퍼가 비어있는 상황

순서	s	n	e
초기값	1	0	10
consumer : semWait(s)	0	0	10
consumer : semWait(n)	0	-1(consumer Block)	10
producer : semWait(s)	-1(producer Block)	-1	10

버퍼가 꽉 찬 상황

순서	s	n	e
초기값	1	10	0
producer : semWait(s)	0	10	0
producer : semWait(e)	0	10	-1(producer Block)
consumer : semWait(s)	-1(consumer Block	10	-1

Monitors

• Programming language 레벨에서 제공하는 툴 = 라이브러리 함수들
• 세마포를 이용해서 만들어진 함수들 제공
• 구성
  • 여러 개의 procedure function들
  • function들을 사용할 수 있는 로컬 데이터들
  • 로컬 데이터에 대한 초기화 코드

• 하얀 부분 = 모니터
• local data = 모니터 안에서만 사용하는 데이터. 모니터 밖에서는 데이터를 읽고 쓸 수 없다.
• initialization code = local data값 초기화
• condition variables = Semaphore처럼 wait나 Signal을 할 수 있는 변수
  • 컨디션 변수는 세마포 문제를 쉽게 해결하기 위해 값을 없앴다. 즉. 값이 없는 큐

세마포의 두 가지 의미

1. 값
2. 프로세스들이 Block 됐을 때 대기하는 장소

• Procedure = function
  • 모니터는 한 번에 한 프로세스만 진입 가능
  • 만약 둘 이상의 프로세스가 동시에 모니터 안에 있는 function을 호출할 경우 두 프로세스 중 한 사람만 모니터 안에 들어가고 다른사람은 기다린다.
• 여러 프로세스가 동시에 모니터 안에 있는 function을 호출하는 경우 제일 먼저 모니터 안에 function을 호출한 사람만 모니터 안에 들어가고 나머지 사람들은 입구의 큐에 가서 순서대로 기다린다.
• 회색 부분 ⇒ 컨디션 변수들에 의해 만들어진 큐
• cwait(n) = n에 해당하는 큐에 가서 대기한다. csignal(n)도 마찬가지로 값을 따지지 않는다.
• 세마포 wait과 다르게 값을 따지지 않는다.
• urgent queue = csignal 명령을 호출했을 때 들어가는 큐
  • csignal 로 깨어난 프로세스는 모니터 안으로 들어오게 된다. 만약 중간에 csignal 을 사용한다면, 사용한 프로세스가 일시적으로 대피해있는 공간이 urgent queue 이다.
• 회색 공간에는 많은 프로레스가 대기하고 있을 수 있지만, 하얀색 공간에는 한 번에 한 프로세스만 있을 수 있다.
• 모니터 자체가 Mutual Exclusion을 지키는 Critical Section

Synchronization

모니터 자체가 Critical Section이기 때문에 동기화만 신경쓰면 된다. 즉, 버퍼가 가득 찼는지 아니면 버퍼가 비었는지만 확인한다.

이런 것들을 확인하기 위해 컨디션 변수를 사용한다.

• cwait(c) = 컨디션 변수 c와 연결된 큐에 들어가서 기다린다.
• csignal(c) = 컨디션 변수 c와 연결된 큐에서 대기중인 프로세스 중 하나를 꺼내서 실행시킨다.

Bounded Buffer Solution Using Monitor

• producer
  • X라는 데이터 생성
  • append = X를 버퍼에 쓴다.
• consumer
  • 데이터를 꺼낸다.
  • 데이터 X 사용

• 크키가 n인 버퍼가 모니터안에 있다 = Critical Section은 저절로 구현 → 둘 이상의 프로세스가 producer나 consumer가 동시에 버퍼에 접근할 수 없다.
• nextin, nextout은 다음에 어디에 데이터를 읽거나 쓸지 나타내는 인덱스이다.
• count = 현재 버퍼안에 데이터가 몇 개 있는지 나타낸다. 모니터 안에서만 사용하는 local 변수
  • count = n ⇒ producer가 기다린다.
  • count = 0 ⇒ consumer가 기다린다.
• notfull = 버퍼가 꽉 찼을 때 기다리는 큐, notempty = Consumer가 버퍼가 비었을 때 기다리는 큐
• append
  • count값이 n이면, notfull 큐에서 기다린다.
  • 그렇지 않다면 데이터를 쓰고 인덱스 값을 수정하고 count값을 증가시킨다.
  • 데이터를 읽으러 왔다가 데이터가 없어서 notempty 큐에서 기다리는 Consumer가 있을 수 있으므로 csignal(notempty) 실행
    • 누군가 기다리고 있는지 따로 따지지 않는다. 세마포처럼 값과 연동되어 있지 않기 때문이다.
• take
  • count값이 0이면, notempty 큐에서 기다린다.
  • 버퍼를 꺼내고, 인덱스 값을 수정하고 count값을 감소시킨다.
  • 버퍼가 꽉 차서 데이터를 쓰지 못하고 기다리는 프로세스가 있을 수 있으므로 csignal(notfull) 수행

💡 Monitor에서 Semaphore의 Deadlock 발생 코드의 순서와 유사하지만 Deadlock이 발생하지 않는 이유

버퍼가 비거나 꽉 차서 대기하는 경우 모니터 밖에서 대기하기 때문이다.

cwait 을 수행했는데 버퍼가 가득 차있으면 모니터(= Critical Section) 밖의 회색 영역의 큐에서 대기한다.

대기하고 있는 사이에 Consumer가 모니터 안에 들어와서 데이터를 사용할 수 있다.

Readers/Writers Problem

• Reader = 데이터를 읽기만 한다.
• Writer = 데이터를 읽고 쓴다.

Reader-Writer 작업 가능 여부(A → B)

Process A	Process B	가능 여부
Writer	Writer	X
Writer	Reader	X
Reader	Writer	X
Reader	Reader	O

Reader와 Writer는 같이 작업할 수 없다. 그러나 Reader끼리는 같이 작업 가능하다.

Readers have Priority

💡 위 코드에서 어떤 이유로 Reader가 우선순위를 갖고있는걸까?

첫번째 Reader가 wsem에서 기다리고 있고 뒤에 Writer가 있는 상황일 때, 첫번째 Reader는 추가로 더 기다리고 있는 Reader가 있다면 Reader먼저 작업을 하게한다.

• readcount
  • 몇 명이 동시에 데이터를 읽고 있는지 나타낸다.
  • 첫 번째 Reader인지 파악하는데 사용된다.
• 여러 명의 Reader가 동시에 데이터를 읽으러 온 경우 모두가 wsem Critical Section에 들어갈 필요가 없다. 한 명이 들어갔을 때 다른 사람이 다 같이 들어갈 수 있기 때문이다.
  • 따라서 첫 번째 Reader가 대표로 wsem에 줄을 선다 ⇒ 자신이 첫 번째 Reader인지 알기 위해 readcount 이용 = if (readcount == 0) semWait(wsem)
  • 공유변수 readcount를 둘 이상의 Reader가 동시에 연산하는 것을 막기 위해 Critical Section 내에서 작업한다.
    • x 세마포 → readcount Critical Section
  • Reader는 줄을 서는 위치가 두 개로 나눠진다.
    • 한 사람(첫 번째 Reader)은 wsem에 줄을 선다.
    • 나머지는 x에 줄을 선다.
  • 첫 번째 Reader가 semWait(wsem) 을 빠져나오면 semSignal(x) 를 통해 x의 문을 열어놓는다.
• 마지막 Reader가 읽을 때까지 wsem에서 대기하는 Writer들은 Critical Section안에 진입할 수 없다.
  • 마지막 Reader가 if (readcount == 0) semSignal(wsem) 을 실행해야 진입할 수 있다.
• 즉, Reader의 경우 동시에 여러 명이 들어갈 수 있기 때문에 동시에 몇 명이 들어갔는지 세기 위해 readcount 변수를 사용한다. readcount 는 Critical Section 안에서 연산을 해야하기 때문에 별도의 x 세마포를 만든다. 첫 번째 Reader만 wsem에 줄을 서고 마지막 Reader만 다음 Writer한테 Signal을 준다.