프로세스 동기화 & 상호배제 #4 - Mutual Exclusion Solutions(Eventcount/sequencer, Monitor)

Mutual Exclusion Solutions

SW solutions

• Dekker’s algorithm (Peterson’s algorithm)
• Dijkstra’s algorithm, Knuth’s algorithm, Eisenberg and McGuire’s algorithm, Lamport’s algorithm

HW solution

• TestAndSet (TAS) instruction

OS supported SW solution

• Spinlock
• Semaphore
• Eventcount/sequencer

Language-Level solution

• Monitor

---

Eventcount/Sequencer

• 은행의 번호표와 비슷한 개념
• Sequencer
  • 정수형 변수
  • 생성시 0으로 초기화, 감소하지 않음
  • 발생 사건들의 순서 유지
  • ticket() 연산으로만 접근 가능
• ticket(S)
  • 현재까지 ticket() 연산이 호출 된 횟수를 반환
  • Indivisible operation
• Eventcount
  • 정수형 변수
  • 생성시 0으로 초기화, 감소하지 않음
  • 특정 사건의 발생 횟수를 기록
  • read(E), advance(E), await(E, v) 연산으로만 접근 가능
• read(E)
  • 현재 Eventcount 값 반환
• advance (E)
  • E <- E + 1
  • E를 기다리고 있는 프로세스를 깨움 (wake-up)
• await(E, v)
  • V는 정수형 변수
  • if (E < v) 이면 E에 연결된 Qe(대기 큐)에 프로세스 전달(push) 및 CPU scheduler 호출

 

Mutual exclusion

실행 순서

• E, v, S 초기값 0
• P1 도착
• ticket(S) : 번호표 뽑기 ( S : 0 -> 1 , E : 0 v : 0) 
• await(E, v) : E = v = 0 이므로 P1 실행 
• P2 도착
• ticket(S) : 번호표 뽑기 ( S : 1 -> 2, E : 0 , v : 1 )
• await(E, v) : E < v 이므로 P2대기 ( 대기큐 Qe에서 E가 1이 될 때까지 대기 )
• P1 종료 
• advance(E) : E : 0 -> 1, v : 1 인 프로세스를 Qe에서 깨운다.
• P2 실행
• ...

Producer-Consumer problem

• Pticket : Producer sequencer, Cticket : Consumer sequencer
• In : 넣는 이벤트, out : 꺼내는 이벤트
• buffer : 저장소

Producer

• t <- ticket(Pticket) : 생산자 티켓 생성
• await(In, t) : Eventcount(In)와 같은 티켓 번호의 프로세스 실행
• await(Out, t - N + 1) : buffer에 저장할 공간이 있는지 확인 
  공간 ≥ 1 (공간 = N(buffer 개수) - t(티켓 생성한 개수) + Out(꺼내서 수행한 개수)
  N - t + Out  ≥ 1
  Out ≥ t - N + 1 ↔ Out < t - N + 1
  => await(Out, t - N + 1) : 공간이 없으면 대기
• buffer[t mod N] <- M : 메시지 저장
• advance(In) : EventCount + 1 , 대기중인 프로세스 깨운다

Consumer

• u <- ticket(Cticket) : 소비자 티켓 생성
• await(Out, u) : Eventcount(Out)와 같은 티켓 번호의 프로세스 실행
• await(In, u + 1) : buffer공간에 메시지가 있는지 확인 
  메시지 수 ≥ 1
  In - u ≥ 1 ↔ In < u + 1
  await(in, u + 1) : buffer안에 메시지가 없으면 대기
• m <- buffer[u mod N] : 메시지 꺼낸다.
• advance(Out) : EventCount + 1 , 대기중인 프로세스 깨운다

특징

• No busy waiting
• No starvation
  • FIFO scheduling for QE
• Semaphore 보다 더 low-level control이 가능( 순서 control가능 )

---

High-level Mechanism

• Monitor
• Path expressions
• Serializers
• Critical region, conditional critical region

 

• Language-level constructs
• Object-Oriented concept과 유사
• 사용이 쉬움

Monitor

• 공유 데이터와 Critical section의 집합
• 한 번에 하나의 프로세스만 진입 가능
• Conditional variable
  • wait(), signal() operations

Monitor의 구조

• Entry queue (진입 큐)
  • 모니터 내의 procedure 수만큼 존재( function )
• Mutual exclusion
  • 모니터 내에는 항상 하나의 프로세스만 진입 가능
  • Language가 보장
• Information hiding (정보 은폐)
  • 공유 데이터는 모니터 내의 프로세스만 접근 가능
• Condition queue (조건 큐)
  • 모니터 내의 특정 이벤트를 기다리는 프로세스가 대기
• Signaler queue (신호제공자 큐)
  • 모니터에 항상 하나의 신호제공자 큐가 존재
  • signal() 명령을 실행한 프로세스가 임시 대기

 

자원 할당 문제

• R : 자원
• requestR() : 자원 요청 function
• releaseR() : 자원 반납 function
• entry queues for releaseR() : releaseR() 사용 대기 큐
• entry queues for requestR() : requestR() 사용 대기 큐
• condition queue R_Free : 자원을 사용할 수 있을 때까지 대기하는 큐
• signaler queue : condition queue에 있는 프로세스를 깨운다.

• procedure requestR() : 자원 요청
• (~R_Available) 자원을 사용할 수 없으면 (R_Free.wait();) condition queue에서 대기
• 자원을 사용할 수 있으면 자원 사용 ( 사용 중이므로 R_Available = false ) 
• procedure releaseR() : 자원 반납
• 자원 반납 ( R_Available = true )
• R_Free.signal(); 자원 사용 대기 중인 프로세스를 깨움

 

자원 할당 시나리오

• 자원 R 사용 가능
• Monitor 안에 프로세스 없음

• 프로세스 Pj가 모니터 안에서 자원 R을 요청
  • R_Avaliable : 1 -> 0
  • Pj 가 자원 R을 사용

• 자원 R이 Pj에게 할당 됨
• 프로세스 Pk 가 R 요청, Pm 또한 R요청
  • 자원 R이 사용 중이므로 Pk, Pm은 condition queue에서 대기

• Pj가 R 반환
• R_Free.signal() 호출에 의해 Pk가 wakeup
  • Pj가 entry queues for releaseR()로 이동 후 자원 반납(releaseR())
  • Monitor 안에는 프로세스가 하나만 들어갈 수 있으므로 Pj가 signaler queue 이동 후 condition queue로 다음 프로세스를 깨운다.
  • Pk가 requestR() 로 이동하여 자원 사용

• 자원 R이 Pk에게 할당 됨
• Pj가 모니터 안으로 돌아와서, 남은 작업 수행

 

Producer-Consumer Problem

• fillBuf() : 메시지 저장
• emptyBuf() : 메시지 꺼내기(수행)
• bufHasSpace : buffer에 공간이 없을 때 대기하는 condition queue
• bufHasData : buffer에 메시지가 없을 때 대기하는 condition queue
• in , out : 메시지를 buffer의 어디에 넣고 뺄지에 대한 위치
• validBufs : 메시지 개수

procedure fillBuf(data : message) : 버퍼에 메시지 저장

• 버퍼 안에 공간이 없으면 (validBufs = N) condition queue에서 대기(bufHasSpace.wait())
• 공간이 있으면 버퍼의 in 위치에 메시지 저장 (buffer[in] <- data )
• 버퍼안의 메시지 개수 추가(validBufs + 1)
• 다음 저장할 위치 지정 (( in + 1 ) mod N;)
• 다음 수행할 프로세스를 깨운다 (bufHasData.signal();)

procedure emptyBuf(var data : message) : 버퍼에서 메시지 꺼내기

• 버퍼 안에 메시지가 없으면 (validBufs = 0) condition queue에서 대기(bufHasData.wait())
• 메시지가 있으면 버퍼의 out 위치에서 메시지를 꺼냄 (data <- buffer[out])
• 버퍼 안의 메시지 개수 validBufs - 1
• 다음 위치 지정 ( (out + 1) mod N )
• 다음 수행할 프로세스를 깨운다 (bufHasSpace.signal() )

 

Reader-Writer Problem

• reader/writer 프로세스들간의 데이터 무결성 보장 기법
• writer 프로세스에 의한 데이터 접근 시에만 상호 배제 및 동기화 필요함
• 모니터 구성
  • 변수 2개
    • 현재 읽기 작업을 진행하고 있는 reader 프로세스의 수
    • 현재 writer 프로세스가 쓰기 작업을 진행 중인지 표시
  • 조건 큐 2개
    • reader/writer프로세스가 대기해야 할 경우에 사용
  • 프로시져 4개
    • reader(writer) 프로세스가 읽기(쓰기) 작업을 원할 경우에 호출, 읽기(쓰기) 작업을 마쳤을 때 호출

procedure beginReading : 읽기 시작

• 쓰기 중이거나 대기중인 writer가 있으면 condition queue에서 대기( readingAllowed.wait() )
• numReaders + 1
• 대기중인 reader가 있으면 깨운다. ( readingAllowed.signal() )

procedure finishReading : 읽기 종료

• reader의 개수를 하나 줄인다 ( numReaders - 1 )
• reader가 없으면 ( numReaders = 0 ) 대기중인 writer 를 깨운다. ( writingAllowed.signal() )

procedure beginWriting : 쓰기 시작

• reader가 있거나 쓰기 중이라면 ( numReaders > 0 or writing ) condition queue에서 대기 ( writingAllowed.wait() )
• 아니면 실행 ( writing <- true )

procedure finishWriting : 쓰기 종료

• writing <- false 
• 대기중인 reader가 있으면 깨운다 ( readingAllowed.signal() )
• 대기중인 reader가 없으면 대기중인 writer를 깨운다. ( writingAllowed.signal() )

 

Dining philosopher problem

• 5명의 철학자
• 철학자들은 생각하는 일, 스파게티 먹는 일만 반복함
• 공유 자원 : 스파게티, 포크
• 스파게티를 먹기 위해서는 좌우 포크 2개 모두 들어야 함

• pickup() : 포크 집기
• eating : 스파게티 먹기
• putdown() : 포크 내려놓기
• thinking : 생각하기

• numForks : 현재 사용가능 포크 수

procedure pickup(me) : 포크 집기

• 포크가 2개가 아니라면 ( numForks[me] ≠ 2 ) 자신의 condition queue에서 대기 (ready[me].wait())
• 나의 포크가 2개라면 왼쪽과 오른쪽 사람의 포크를 하나씩 뺀다. ( numForks[left(me)] - 1, numForks[right(me)] - 1)

procedure pickup(me) : 포크 내려놓기

• 왼쪽과 오른쪽 사람의 포크를 하나씩 늘린다. ( numForks[left(me)] + 1, numForks[right(me)] + 1)
• 오른쪽 사람의 포크가 2개라면 (numForks[right(me)] = 2 ) condition queue에서 프로세스를 깨운다 (ready(right[(me)].signal();
• 왼쪽 사람의 포크가 2개라면 (numForks[left(me)] = 2 ) condition queue에서 프로세스를 깨운다 (ready(left[(me)].signal();

 

장점

• 사용이 쉽다
• Deadlock 등 error 발생 가능성이 낮음

단점

• 지원하는 언어에서만 사용 가능
• 컴파일러가 OS를 이해하고 있어야 함
  • Critical section 접근을 위한 코드 생성

---

 

 

강의

www.youtube.com/watch?v=S7l2UEXVhb0&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=17

www.youtube.com/watch?v=AnYN-kbCbRI&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=18