Chapter 5-5. Concurrency : Mutual Exclusion and Synchronization

Semaphore를 사용할 때

1. 어떤 상황에서 프로세스가 기다려야 하는가?
2. 프로세스가 몇 개의 Queue로 나뉘어져 관리가 되어야 하는가?
   → Queue의 개수를 결정해야 한다.
3. Queue의 수만큼 Semaphore를 생성한다.
   → Semaphore 1개당 Queue 1개

Semaphore에는 딱 두가지 함수만이 존재한다.
→ 이 두가지 함수만으로 다양한 동기화 문제를 해결할 수 있다.

• semWait
• semSignal

Bounded Buffer using Semaphores

위의 코드에서 세마포는 3가지가 존재한다.

• s → Queue에 Produce와 Consumer가 섞여서 들어간다.
• n → Queue에 Consumer만이 들어간다.
• e → Queue에 Producer만이 들어간다.

Producer Process:

1. Buffer가 가득 찼는지 확인
2. Critical Section 진입 가능 여부 확인
3. Buffer에 데이터 쓰기
4. Critical Section 깨워주기
5. Consumer 깨워주기

Consumer Process:

1. Buffer가 비었는지 확인
2. Critical Section 진입 가능 여부 확인
3. Buffer에서 데이터 읽기
4. Criitcal Section 깨워주기
5. Producer 깨워주기

---

Monitors

OS는 Semaphore를 제공해서 우리가 Semaphore를 이용하여 여러 문제를 해결할 수 있게 해준다.
↔ 하지만, 잘못 사용하게 되면 Deadlock이 발생할 수 있다.

Monitor는 Programming-language construct 이다.

semaphore와 동등한 기능을 제공하고, 제어하기 쉬운 프로그래밍 언어 구조이다.

Programming-language construct

Programming-language construct 는 라이브러리 함수이다.

File에서 Data를 다룰 때 System Call에는 오로지 READ, WRITE만 존재한다.
하지만, READ, WRITE는 데이터 타입 구분을 하지 않는다.
⇒ 쉽게 시스템을 사용할 수 있게 하기 위해(입출력하기 위해) Buffering와 Printf, Scanf 와 같은 라이브러리를 이용한다.

이와 같이 우리가 바로 Semaphore 를 사용하게 되면, 어렵기도 하고 잘못 사용하면 Deadlock 이 발생할 수 있기 때문에 Monitor 라는 모듈 라이브러리를 사용하는 것이다.

간단히 말해서 Monitor 는 Semaphore 를 구현해 놓은 module 이다.

Monitor 는 software module 이다.

Monitor의 구성요소

• 한 가지 이상의 Procedures
• initialization sequence
• local data

---

Structure of a Monitor

Monitor

Monitor 자체가 Critical Section이다.
→ 한 번에 하나의 Process만 Monitor에 진입할 수 있다.

ex) Process1이 Procedure1을 실행하고 싶어하고, 
Process2가 Proedure2를 실행하고 싶어서 동시 호출해도, 
Monitor 안에는 하나의 Process만 진입할 수 있고 
다른 프로세스들은 모니터 밖의 Queue에서 대기하게 된다.

local data

monitor에 대한 local 이다.
→ Procedure 입장에서는 전역 변수이다.
즉, 여러 Procedure에서 access할 수 있는 변수이다.
⇒ Monitor 안에서만 access가 가능하다.
⇒ 두 프로세스 동시 접근 불가

Procedure

여러개의 Procedure가 존재한다. (1~k)
Monitor "안" 에서만 실행된다.

어떤 프로세스가 Procedure를 실행시키기 위해서는 monitor 안에 들어와서 실행해야 한다.

cwait(cn)

호출한 프로세스가 바로 Block된다.
→ 바로 Condition Queue로 들어가게 된다.
→ 이후 바깥의 Queue에서 대기 중이던 프로세스가 Monitor로 들어온다.

urgent queue

monitor 안에 Process1가 Procedure1을 실행 중
→ semSignal(c) 호출
→ 새로운 Process가 monitor 안으로 들어오게 됨

이 경우, monitor 바깥의 Queue에서 대기하다가 막 깨어난 프로세스가 우선순위를 갖게 되어 막 들어온 프로세스가 monitor 작업을 진행하게 된다.
원래 monitor안에서 실행 중이던 Process1은 Urgent Queue로 들어가서 block 하게 된다.

→ 이후 바깥에서 막 들어온 프로세스가 작업 진행을 마치면 다시 Process1이 Urgent Queue에서 나와 원래 하던 작업을 실행하고 monitor에서 나가게 된다.
→ 이후 바깥의 Queue에서 대기하던 프로세스 중 하나가 monitor에 들어오게 된다.

---

Characteristics

1. Local data variables are accessible only by the monitor
   ↳ Monitor들은 local data variable에 한 번에 하나만 접근할 수 있다.
2. Process enters monitor by invoking one of its procedures
   ↳ Process가 Procedure를 호출하면 monitor안으로 들어 오게 되고, procedure에서 연산을 진행하게 된다. 밖에서는 연산이 불가능하다.
   ⇒ Mutual Exclusion 이 지켜진다.
3. Only one process may be executing in the monitor at a time (mutual exclusion facility)
   ↳ 오직 하나의 프로세스만이 monitor를 실행할 수 있다.
   ⇒ Mutual Exclusion facility

---

Synchronization

condition variables

Synchronization achieved by condition variables within a monitor
↳ only accessible by the monitor.

condition variables 는 버퍼가 차있는지 동기화를 해결하기 위해 사용된다.

1. monitor 안에서만 사용 가능
2. Queue 존재
3. Semaphore와 다르다. ↔ condition variable에는 정수값이 존재하지 않는다. Queue만 존재한다.

Monitor Functions

cwait(c)

Suspend execution of the calling process on condition c
→ 무조건 이 함수를 호출한 Process를 Block 시킨다.

csignal(c)

Resume execution of some process blocked after a cwait on the same condition
→ Queue에 있는 Process 하나를 꺼내서 Monitor 안으로 들여온다. 세마포와 달리, 정수 값이 없기 때문에 Queue가 비었는지 안비었는지 확인할 수 없다.

---

Bounded Buffer Solution Using Monitor(2)

여러개의 Producer와 Consumer들이 존재하는 상황이다.

char x와 같이 데이터를 만드는 작업이나 consume()은 monitor 바깥에서 작업해도 된다.
↔ 하지만, append()와 take() 작업은 반드시 monitor 안에서 작업해야한다.

---

Bounded Buffer Solution Using Monitor

boundedbuffer

monitor boundedbuffer;

데이터를 읽고 쓰기 전 후 monitor 안에서 둘 이상의 Producer가 append를 동시에 하는 것을 막고, 둘 이상의 Consumer가 take를 동시에 하는 것을 막는다.

buffer[N]

char buffer [N]

N 크기의 버퍼

nextin, nextout

int nextin, nextout;

• nextin: 다음에 데이터를 쓸 위치
• nextout: 다음에 데이터를 읽을 위치

count

int count;

local data → 버퍼의 데이터가 가득찼는지 안 찼는지를 판단한다.

notfull, notempty

cond notfull, notempty;

• notfull: producer들이 버퍼가 full 했을 때 block 되는 Queue
• notempty: consumer들이 버퍼가 empty 했을 때 block 되는 Queue

초기값

buffer initially empty

• nextin = 0
• nextout = 0
• count = 0

---

Q. Count 변수를 사용할 수 있는 이유?

↳ monitor안의 local 변수 count를 사용했기 때문이다.

이 monitor 자체가 Critical Section이기 때문이다.
Count는 monitor 안에 있기 때문에 연산이 가능한 것이고, Count를 사용해서 코드가 간단해졌다.

Semaphore에서는 count와 같은 변수를 사용할 수 없다.

Q. Monitor에서 Deadlock이 발생하지 않을까?

Semaphore로 Buffer 문제 해결했을 때는 코드 위치를 변경했을 때 Deadlock이 발생했다.

1. semWait(e) ↔ semWait(s) : Critical Section에 먼저 들어간 뒤, 버퍼가 찼는지 확인
2. semWait(n) ↔ semWait(s) : Critical Section에 먼저 들어간 뒤, 버퍼가 비었는지 확인
   
   ↔
   monitor의 경우, Critical Section에 원래 먼저 들어간 뒤, 버퍼가 비었는지 꽉 찼는지를 확인한다. ⇒ Deadlock이 발생하지 않는다.

⇒ 왜 순서를 바꿨을 때, Semaphore는 Deadlock이 발생하고 왜 Monitor에서는 Deadlock이 발생하지 않을까?

---

Readers/Writers Problem

버퍼 안에 공유데이터 가 존재한다. → Producer와 Consumer처럼 서로 대칭 작업을 하는 두 종류의 프로세스가 있는 게 아니라, readers와 writers라고 하는 서로 비대칭 적인 작업을 하는 두 종류의 프로세스가 있다.

Readers와 Writers는 비대칭 작업 을 한다.

Readers : 동시 작업이 가능하다.
→ 공유 영역 데이터를 "읽기" 만 한다.
↳ 데이터 값 변경 X

Writers : 동시 작업이 불가능하다. (Race condition이 발생할 수 있다.)
→ 데이터를 쓰는 애 X, 데이터를 읽고 계산하고 쓰는 역할을 한다.
↳ 데이터 값 변경 O

• r-r O
• w-w X
• r-w X
• w-r X

A data area is shared among many processes

• Some processes only read the data area, some only write to the area

Conditions to satisfy:

• Multiple readers may read the file at once.
• Only one writer at a time may write
• If a writer is writing to the file, no reader may read it.
  → 만약 writer가 file에 쓰고 있다면, reader는 동시에 file을 읽을 수 없다.

---

Readers have Priority

Reader 하나 들어가면 나머지 reader가 따라 들어온다.

main()

readcount 공유변수 1개가 있고, 값을 0으로 초기화한다.
reader, writer가 여러명 존재하며 동시에 작업을 시작할 수 있다.

비대칭적인 작업 ⇒ 이전과 달리 reader() 와 writer() 의 코드가 다른 것을 확인할 수 있다.

writer()

reader가 1명도 없다고 가정했을 때, writer는 그냥 critical section이다.

semWait(wsem) 을 통과해서 write 작업을 한다. 그 뒤 semSignal(wsem) 을 진행한다.

writer는 한 번에 하나씩만 critical section에 접근할 수 있는 완벽한 critical section 문제이다.

---

이 Ciritical Section 안에는 Data라고 하는 Buffer 가 있다.
wsem seamaphore가 지키고 있는 Critical Section이다.

Critical Section 이기 때문에 wsem semaphore의 초기값이 1이다.

w1이 Critical Section으로 들어와서 읽고 쓰고 업데이트를 할 때, wsem의 값은 0이 된다. ⇒ Criitcal Section의 문은 닫히게 된다.

이 때 다른 writer 들이 Critical Section에 들어가고 싶어서 대기를 하면, wsem의 값을 하나씩 빼 가며 writer들이 줄을 서게 된다.

이 때, 밖의 wsem Queue에 reader 하나가 Critical Section에 들어가고자 등장한다.
reader 도 당연히 줄을 서야 한다.
↳ writer 가 작업하고 있는 동안에 reader 는 들어갈 수 없다.

이후 두번째 reader 도 Critical Section에 들어가고자 나타났다고 하자.
그런데 이 reader 도 wsem Queue에 줄을 서야할까?
↳ 첫번째 reader 는 당연히 줄을 서야 한다.
⬇
r1이 들어가면 r2는 같이 들어간다.
⇒ 첫번째 reader 만 줄을 서고 나머지 reader 는 줄을 서지 않는다.
최대 1명의 reader 만 줄을 선다. (1개 또는 0개만 줄을 선다.)

어느 순간 wsem Queue를 보면, writer는 여러 명이 줄을 서있고, reader는 한 명만 줄을 서 있는다. 또는 reader가 아무도 없을 수도 있다.

만약 reader 가 자신의 차례를 기다리다가 차례가 되어 Critical Section 안으로 들어왔다고 가정하자.
밖에는 여전히 Writer 들이 wsem Queue에서 대기를 하고 있는데, 만약 이 때 새로운 reader 가 등장하게 되면 이 reader는 대기할 필요가 없다.

그냥 같이 들어가서 READ 작업을 하면 된다.

위와 같이 여러명의 reader들이 동시에 읽을 수 있다.

⇒ Critical Section 안에 reader 가 들어있다 == wsem Queue 안에는 대기하는 reader 가 존재하지 않는다.

r1이 작업을 완료해서 Critical Section을 나오게 된다.
원래는 Critical Section에서 작업하던 애가 작업을 마치고 나올때는 바깥 Queue에 대기하고 있던 애를 깨워주고 Critical Section에 넣어주고 나가게 된다.

그런데 여기서는 r1이 작업이 끝났다고 해서 대기하고 있던 프로세스를 Critical Section 안에 넣어줄 수 없다.
→ 아직 reader들이 남아있기 때문이다.

Critical Section 안에 들어있는 모든 reader 가 작업을 마칠 때까지 writer 는 Critical Section 에 들어올 수 없다.

reader 의 경우, 첫번째 reader 만 줄을 서기 때문에, 내가 첫번째 reader 인지 알아야 한다.
또, 마지막에 나오는 reader 의 경우에만 semSignal()을 해서 writer 를 깨워서 Critical Section 안에 넣어줄 것이다.
⇒ 내가 몇 번째 reader 인지 알아야 한다.
↳ 이 일을 하는 것이 readCount 이다.

readCount

1. 초기값 = 0
2. reader가 한 명씩 올때마다 readCount를 하나씩 증가시킨다.
3. reader가 작업을 마칠때마다 readCount를 하나씩 감소시킨다.

⇒ 내가 몇 번째 reader 인지 알 수 있다.

readCount 자체는 Critical Section 안에서 연산(+, -)를 진행해야 한다.

⇒ Critical Section 이 하나 더 필요하다!

X라고 하는 Critical Section을 하나 더 사용할 것이다.

• readCount를 이 Critical Section 안에 집어 넣는다.
• 새로운 reader가 도착하면 readCount++ 를 Critical Section 안에 들어가서 진행한다.
• 작업을 다 마치고 나면, readCount-- 를 Critical Section 안에서 진행한다.

• 내가 read 작업을 하기 전에, readCount++ 를 하는데, Critical Section 에서 작업하기 위해 → semWait(x) 를 통해 Critical Section 진입한 후 readCount 연산을 진행한다.
• 내가 read 작업을 다 마친 후, readCount-- 를 하는데, Critical Section 에서 작업하기 위해 → semWait(x) 를 통해 Critical Section 진입한 후 readCount 연산을 진행한다.

readCount == 1 일 때, 해당 reader 가 첫번째 reader 라는 뜻이므로 wsemWait에 가서 줄을 설 것이다.

if(readCount == 1) semWait(wsem);

readCount == 0 일 때, 해당 reader 가 마지막 reader 라는 뜻이므로 semSignal(wsem)을 통해 wsemQueue에서 대기 중이던 writer 를 Critical Section 안으로 들여보내 줄 것이다.

if(readCount == 0) semSignal(wsem);

reader들이 줄 서 있는 곳?

첫 번째 reader 만 wsemQueue에 줄을 서는데, 그렇다면 나머지 reader 들은 어디에서 줄을 설까?
→ x 라고 하는 semaphore Queue에서 줄을 선다.

x semaphore 의 기능

• Critical Section 기능 구현: readCount++, readCount-- 를 둘 이상의 reader 가 동시에 실행하면 안되기 때문에 한 번에 하나씩만 readCount 연산을 진행하기 위해 사용하는 semaphore
• 대기하고 있던 reader 들을 줄 세우는 작업을 한다.

r1

• semWait(x) → x = 0
• readCount++ → readCount = 1
• semWait(wsem) → wsem Queue에 대기 → 이미 wsem에는 대기 프로세스가 앞에 있어 문이 닫혀 있는 상태라 통과 X
  ⇒ 다음 코드로 넘어갈 수 없다. ⇒ swmSignal(x)를 해서 reader 들을 blocked 상태에서 풀어줄 수 없다.

r2

• semWait(x) → x = -1
• Critical Section에 들어가지 못한다.

r1이 Critical Section에 들어가지 못했기 때문에 다른 reader 들이 x Queue에서 대기하고 있어도 readCount는 여전히 1이다.
Critical Section에 들어가지 못했기 때문에 readCount 값을 바꿀 수 없다.

reader 가 4명이나 있어도 reader 들 중에 어느 누구도 Critical Section 에 들어가서 data를 읽지 못하는 상황에서는 readCount가 계속 1을 유지한다.

여러명의 reader 가 도착했더라도 하나의 reader 만 wsem Queue에 대기하고 나머지 reader 들은 x Blocked Queue에서 대기하게 된다.

Writer 가 작업을 마침
r1이 드디어 Critical Section 에 들어가게 된다.

• semSignal(x) 를 실행한다.
• x Queue에 대기하고 있던 reader 를 Critical Section으로 넣어준다.
• readCount가 1 증가한다.
• semSignal(x) → 다른 reader 를 깨워준다.
• 늦게온 r5가 먼저 기다리고 있던 w들보다 먼저 실행된다.

정리

writer

1. writer 는 기본적으로 Critical Section 이다.
2. wsem 을 이용해서 기본 Critical Section 을 구현한다.

reader

1. reader 의 경우, 첫 번째 reader 만 wsem 에 대한 semWait(wsem)을 실행한다.
2. 마지막 reader 만 wsem 에 대한 semSignal(wsem)을 실행한다. → 다음 writer 를 Critical Section 으로 넣어준다.
3. 몇 번째 reader 인지 세야 한다. → 이 작업은 readCount 가 한다.
4. readCount 자체는 Critical Section 으로 구현했다.
5. semaphore x 의 역할
   • readCount 동시 접근 제한
   • 다른 reader 들이 대기하는 곳