Devvoo

앞으로 포스팅은 velog에…
https://velog.io/@root-devvoo/posts

Process Synchronization (1), (2), (3), (4)

🔊 이화여자대학교 반효경 교수님의 KOCW 2014년 1학기 운영체제 강의를 들으며 정리한 노트입니다.
      캡쳐한 이미지 중 따로 출처 명시를 하지 않은 이미지 또한 반효경 교수님 강의 자료에 있음을 밝힙니다.

데이터의 접근

image

위와 같은 데이터의 접근 방식은 데이터가 저장되어있는 위치에서 읽어와서 연산을 하고, 다시 원래의 위치에 반영을 하기 때문에 누가 먼저 읽어갔느냐에 따라서 결과가 달라질 수 있는 프로세스 동기화 문제가 발생한다.

Race Condition
image

Storage Box를 좌측 Execution Box 혼자 사용한다고 하면 문제될게 없지만,
위와 같은 식으로 여러 주체가 하나의 데이터를 동시에 접근하려고 할 때를 Race Condition(경쟁 상태)라고 한다. 이런 경쟁 상태에서 어떤 하나의 주체가 읽어갔고 반환하지 않은 상황인데, 그동안에 또다른 주체가 또 읽어간다면 우리가 원치않는 결과를 얻을 수 있다.

OS에서 race condition은 언제 발생하는가?

  1. kernel 수행 중 인터럽트 발생 시
  2. Process가 System call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
  3. Multiprocessor에서 shared memory 내의 kernel data
OS에서의 race condition (1/3)
interrupt handler v.s. kernel
image
  • ※ 커널모드 running 중 interrupt가 발생하여 인터럽트 처리루틴이 수행
    • → 양쪽 다 커널 코드이므로 kernel address space 공유
OS에서의 race condition (2/3)
Preempt a process running in kernel?
image
  • ＊두 프로세스의 address 간에는 data sharing이 없음
  • ＊＊그러나 system call을 하는 동안에는 kernel address space의 data를 access하게 됨 (share)
  • ＊＊＊이 작업 중간에 CPU를 preempt 해가면 race condition 발생
OS에서의 race condition (2/3)
Preempt a process running in kernel?
If you preempt CPU while in kernel mode …..
image
  • ＊＊＊＊해결책: 커널 모드에서 수행 중일 때는 CPU를 preempt(선점)하지 않음
    커널모드에서 사용자모드로 돌아갈 때 preempt(선점)
OS에서의 race condition (3/3)
multiprocessor
(CPU가 여러개 있는 환경)
image

어떤 CPU가 마지막으로 count를 store했는가? → race condition
multiprocessor의 경우 interrupt enable/disable로 해결되지 않음
(인터럽트를 막아서 해결할 수 없다)

(해결방법 1) 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법

(해결방법 2) 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법

Process Synchronization(프로세스 동기화) 문제

  • 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다
  • 일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process)
  • Race condition
    • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
    • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
  • race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 한다
Example of a Race Condition
image

※ 사용자 프로세스 P1 수행중 timer interrupt가 발생해서 context switch가 일어나서 P2가 CPU를 잡으면?
원하는 결과가 나오지 않고, 일관성(consistency)이 깨어진 불일치 문제가 생길 수 있다.
(위에서 얘기했던 얘기랑 같은 얘기)

The Critical-Section Problem(임계영역 문제)

  • n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
  • 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section(임계영역)이 존재
  • Problem
    • 하나의 프로세스가 critical section(임계영역)에 있을 때 다른 모든 프로세스는 critical section(임계영역)에 들어갈 수 없어야 한다

image

Initial Attempts to Solve Problem

  • 두 개의 프로세스가 있다고 가정 P0, P1
  • 프로세스들의 일반적인 구조

image

우리가 공유데이터를 접근하는 코드를 critical section이라고 했다.
공유데이터를 그냥 접근하게 하면 동시접근을 통해서 문제가 발생할 수 있기 때문에, 공유데이터를 접근하는 코드 이전에 entry section을 넣어서 lock을 걸게함으로써 여러 프로세스가 동시에 critical section에 들어가는 것을 막고,
그 다음에 critical section이 끝났으면 lock을 풀어서(exit section) 다른 프로세스가 critical section에 들어갈 수 있게 해준다.

  • 프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수를 공유할 수 있다 → synchronization variable

프로그램적 해결법의 충족 조건

critical section문제를 풀기 위해서 만족해야될 조건이 무엇인가?
그 조건 3가지…

  • Mutual Exclusion (상호 배제)
    • 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다
  • Progress (진행)
    • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다
  • Bounded Waiting (유한 대기)
    • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다
      (특정 프로세스 입장에서 critical section을 못들어가고 지나치게 오래 기다리는 starvation이 생기지 않아야겠다는 얘기)
  • ※ 가정
    • 모든 프로세스의 수행 속도는 0보다 크다
    • 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다

이러한 조건을 만족하면서 (윗 부분과 같이 소프트웨어적으로) critical section의 문제를 푸는(lock을 잘 걸었다가 푸는) 알고리즘들을 소개한다.

Algorithm 1

  • Synchronization variable

    int turn;
    initially turn = 0; → Pi can enter its critical section if (turn == i)

    turn이 0이면 0번 프로세스 차례라는 얘기, turn이 1이면 1번 프로세스

  • Process P0
    image

  • Process P1

    do {
    while (turn != 1);       /* My turn? */
    // critical section
    turn = 0;                /* Now it's your turn */
    // remainder section
} while (1);

즉, turn은 누구 차례인지 판별하는 변수

그러나, 이 방식의 가장 중요한 문제점이 아무도 critical section에 없는데도 불구하고 critical section에 들어가지 못하는 문제가 발생… 즉, progress 조건을 만족하지 못함

Satisfies mutual exclusion, but not progress
즉, 과잉양보:
반드시 한번씩 교대로 들어가야만 함 (swap-turn)
그가 turn을 내 값으로 바꿔줘야만 내가 들어갈 수 있음
특정 프로세스가 더 빈번히 critical section을 들어가야 한다면?

이런 문제 때문에 turn을 교대로만 해줘서는 안되겠다. 해서 다른 방법을 생각해본게 아래…

Algorithm 2

  • Synchronization variables

    • boolean flag[2];
      initially flag[모두] = false; /* no one is in CS */

    • “Pi ready to enter its critical section” if (flag[i] == true)

      여기서는 flag라는 변수를 사용하고 있음.
      프로세스 2개가 각각 자신의 flag를 가지고 있으며, flag는 본인이 critical section에 들어가고자 한다는 의중을 표시함

  • Process Pi
    image

    critical section에 들어갈 때 어떻게 하느냐? (Pi 입장에서)
    본인의 flag를 true로 만든다. (내가 지금 critical section에 들어가고자 한다는 의사표시를 하는 것)
    그 다음 while문으로 상대방 flag를 체크,(상대방도 flag를 셋팅해놨는가? 상대방이 flag를 셋팅해놨으면 기다림)
    만약 상대방이 flag를 셋팅하지 않았다면 critical section에 들어감.
    들어갔다가 나올 때 본인의 flag를 false로 만들어준다. (혹시 상대방이 기다리고 있으면 들어갈 수 있게…)

그러나 이 알고리즘도 문제가 있다… ㅠ

  • Satisfies mutual exclusion, but not progress requirement.
  • 둘 다 2행까지 수행 후 끊임없이 양보하는 상황 발생 가능

이 알고리즘도 마찬가지로 둘이 동시에 들어가는 문제가 발생하지는 않는다.
다만, 둘 다 들어가기도 전에 깃발만 들었지 실제로는 아무도 들어가있지 않은 상황인데도 눈치만 살피다가 아무도 들어가지 못하는 상황이 생긴다.

그래서 생각해본 다음 방법이 3번째 알고리즘…

Algorithm 3 (Peterson’s Algorithm)

  • Combined synchronization variables of algorithms 1 and 2.

  • Process Pi
    image

    이 방법은 위에서 설명한 turn과 flag 두 변수를 모두 사용하고 있다.

    프로세스 i가 critical section에 들어가고자 할 때, 제일 먼저 자신의 깃발을 들어서 critical section에 들어가겠다는 의사표현을 하고(flag[i] = true;)
    그리고, turn을 상대방 turn으로 바꿔놓는다.(turn = j;)
    그 다음 들어가기 전에 상대방 flag와 turn을 체크… 상대방이 깃발을 들고 있고, 이번이 상대방 차례(turn)인 두 가지를 모두 만족하는 동안에는 while문을 통해 기다리도록 한다. (while (flag[j] && turn == j);)

  • Meets all three requirements; solves the critical section problem for two processes
  • Busy Waiting(=spin lock)! (계속 CPU와 memory를 쓰면서 wait)

이 방법은 모든 경우의 수를 다 따져서 중간 어딘가에서 CPU를 빼앗긴다 하더라도 위에서 소개했던 충족조건을 모두 만족한다.

하지만, 이 코드도 사실 문제점이 있다… Busy Waiting문제
쓸데없이 자원을 낭비하면서 체크… 비효율적

Synchronization Hardware

  • 하드웨어적으로 Test & Modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결

    image

    사실, 이런 문제가 생겼던 이유는 우리가 어떤 데이터를 읽는거하고, 데이터를 쓰는 것을 하나의 instruction으로 처리할 수 없기 때문에 문제가 생겼던 것이다.

    그래서, instruction 하나를 가지고 어떤 데이터를 읽는 작업하고, 데이터를 쓰는 작업을 동시에 실행할 수 있다면(하드웨어적인 instruction이 지원된다면) 대단히 간단하게 lock을 걸고 푸는 문제를 해결할 수가 있다.

    즉, 하드웨어적으로 하나의 instruction만 주어지면 이러한 critical section 문제는 아주 쉽게 해결이 된다.
    하드웨어적으로 이러한 고유의 instruction이 지원이 되는 경우가 많은데 그것이 Test_and_set이라는 instruction이다.

    이 Test_and_set instruction은 a라는 데이터의 현재값을 읽어내고, 그 다음에 a라는 데이터의 값을 1로 바꿔주는 이 두 가지의 작업을 atomic하게 하나의 instruction으로 처리하는 것이다.
    (만약에 a라는 데이터가 원래 0이었다고하면, 0이 읽히고, 그리고 나서 a의 값은 1로 바뀌게 되는 것)
    (반대로 Test_and_set인데 a의 값이 1이었다면 읽었을 때 1이 읽힐 것이고, 그 값은 다시 1로 셋팅하는 것)

  • Mutual Exclusion with Test & Set
    image

여기서 lock이라는 변수를 하나 두고… 처음에는 lock = false; // 0
critical section에 들어가기 전에 lock = true; // 1로 해서 lock을 걸고 들어감
이미 lock이 걸려있는지 체크하고(while (Test_and_Set(lock)))
안걸려있다고 하면 내가 lock을 걸고 critical section에 들어가는 이 두개의 작업을 Test_and_Set이라는 instruction을 이용해서 동시에 실행을 함

누군가가 이미 lock을 걸어놔서 lock이 1(true)이면 Test_and_Set을 해서 읽어보면 1이 읽힐 것이다. 1이 읽히니까 while문을 계속 돌면서 기다리고 있는다. 그리고 lock의 값은 1로 다시 셋팅

Semaphores

  • 앞의 방식들을 추상화시킴

    (추상 자료형)

    먼저 위에서 나왔던 방식들처럼 프로그래머(사용자)가 이런 작업을 일일히 코딩하는게 아니라 추상 자료형 형태로 제공을 해주고, 프로그래머는 Semaphore를 통해서 프로그래밍을 하면 훨씬 간단한 프로그램을 작성할 수 있다.

  • Semaphore S

    • integer variable

      정수 값을 가질 수 있다. (정수 값 == 자원의 개수)

    • 아래의 두 가지 atomic 연산에 의해서만 접근 가능
      image

세마포어 자료형은 P 연산, V 연산 두 가지가 정의된다.

P 연산은 Semaphore 변수 값을(공유 데이터를) 획득하는 과정
V 연산은 다 사용하고나서 반납하는 과정

예를 들어, 변수 값이 5면 P 연산을 5번해서 다섯이서 동시에 가져갈 수가 있음
자원의 개수가 4개인 상태에서 V 연산을 하고나면 원래 상태인 5개로 되돌아온다.

lock을 걸고 푸는 과정은 여기서 Semaphore 변수가 1인 경우를 생각하면 된다.
(변수)자원의 개수가 한개니까 P 연산을 하면 lock을 거는 과정이고, V 연산을 하면 lock을 푸는 과정이다.

구체적으로 P 연산과 V 연산이 어떻게 정의되는지 위 이미지를 통해 보자…

변수 S에 대해서 P 연산을 하게 되면 그 S 값이 0 이하인 동안에 while문을 돌면서 아무 일도 안하고 기다리게 된다. (자원을 다 가져가고 없는 상태이기 때문) 기다리다가 S 값이 양수가 되면(누군가가 자원을 내어놓으면) 그때 S값을 1 빼고 자원을 획득, 사용

사용이 다 끝나고 나면 V 연산을 해서 S 값을 1 증가시켜서 반납함

여기서도 busy waiting 문제는 생김.. 자원이 없는 상태에서도 계속 기다리면서 본인의 CPU 시간을 다 쓰고 반납

Critical Section of n Processes

image

busy-wait는 효율적이지 못함 (=spin lock)
Block & Wakeup 방식의 구현 (=sleep lock)

Block & Wakeup Implementation

  • Semaphore를 다음과 같이 정의
    image

    여기서는 Semaphore를 위해서 Semaphore 변수 안에는 실제 Semaphore변수 값하고(int value;), Semaphore 때문에 잠들어있는 프로세스들을 연결하기 위한 queue가 하나 만들어지게 됨(struct process *L;)

  • block과 wakeup을 다음과 같이 가정

    • block
      커널은 block을 호출한 프로세스를 suspend시킴
      이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음

    • wakeup(P)
      block된 프로세스 P를 wakeup시킴
      이 프로세스의 PCB를 ready queue로 옮김

      image

그래서 만약에 지금 semaphore를 획득할 수 없으면 그 프로세스를 block시키게 되고, 누군가가 semaphore를 쓰고나서 반납을 하게되면 block된 프로세스 중에 하나를 깨워서 wakeup을 시키게 된다.

예를 들어 semaphore 변수가 하나 있다고 하면, 그 친구를 누군가는 획득을 했을 것이고, 획득을 못한 친구들은 바로 위 이미지와 같이 PCB를 Semaphore변수 queue에다가 매달아 두는 것이다.
(여기서는 semaphore를 기다리면서 잠들어있는 프로세스들을 연결을 해놓는 것)

구체적으로 어떻게 구현이 되는지 살펴보자.

Implementation
block & wakeup version of P() & V()
  • Semaphore 연산이 이제 다음과 같이 정의됨
    image

P 연산은 자원을 획득하는 과정…
자원에 여분이 있다면 획득을 바로 할 것이고,
자원에 여분이 없다면 잠든다.(block 상태로 들어감)

V 연산은 자원을 다 쓰고나서 반납을 하는 것, 그러나 block & wakeup 방식에서는 반납하고 끝나는게 아니라 혹시 이 자원을 기다리면서 잠들어있는 프로세스가 있다면 그것을 깨워주는 작업이 같이 들어가야한다.

S는 Semaphore 변수…
S 하나에 값이 있을 것이고, 프로세스를 연결하는 List가 있을 것임.
먼저 P 연산에서는 그 Semaphore 변수 값을 1 빼준다.(S.value--;)
그런 다음에 그 값이 만약 음수라고 하면(S.value < 0) 이미 누군가가 다 가져가고 자원의 여분이 없다는 얘기이므로 이때는 이 프로세스를 S.L(리스트)에다가 연결시킨다음에 block();을 시킴
그러면 이 친구는 block 상태에 있다가 자원이 생기면 그때 깨어날 수가 있는 것인데…

자원을 이미 쓰고 있는 프로세스가 다 쓰고나면 그 S의 value를 1 증가 시키고(S.value++;), 그런 다음에 만약 S.value가 0 이하라고 하면(if (S.value <= 0))(조심해야하는 부분… S.value가 0 이상일 때 자원의 여분이 있는게 아니고, 여기서(P(S) 첫번째 줄)는 일단 S의 값을 빼고나서 잠들었음.. 그래서 만약 내가 지금 자원을 내놓았는데도 불구하고 그 값이 0 이하라는 것은 이 친구를 기다리면서 누군가가 지금 잠들어있다는 뜻이다) 잠들어있는 프로세스 하나를 그 Semaphore의 List에서(S.L) 빼가지고 그 프로세스를 깨워주는 작업을 해야한다는 것

여기서 S.value는 자원의 개수를 세는 의미하고는 좀 다르다…
S값이 음수가 되버리면 누군가가 자원을 기다리고 있다는 의미가 되고, 양수면 자원에 여분이 있기 때문에 기다리지 않고 쓰고 있는 상황이다. 라는 상황을 나타내는 거라서 앞서 나왔던거 하고는 조금 의미가 다르다는 것을 유념해서 봐야한다.
즉, 누군가 깨워야 될 것이 있는지 없는지를 확인하기 위해서 value값을 사용하는 개념이라는 것

Which is better?

  • Busy-wait v.s. Block & Wakeup

    지금까지 Semaphore를 구현하는 방식에 있어서 Busy-wait를 쓸 것이냐 Block & Wakeup을 쓸 것이냐 두 가지에 대해서 설명을 했음

  • Block & Wakeup overhead v.s. Critical Section 길이

    • Critical section의 길이가 긴 경우 Block & Wakeup이 적당

    • Critical section의 길이가 매우 짧은 경우 Block & Wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음

      Block & Wakeup도 오버헤드가 있다. 어떤 프로세스의 상태를 Ready상태에서 잠드는 상태로 바꿔야되고, 나중에 자원이 반납되면(공유데이터에 여분이 생기면) Block 상태에 있던걸 다시 Ready상태로 바꿔줘야되는 작업이 필요하기 때문에

      Critical section의 길이가 매우 짧은 경우 busy wait방식을 써도 크게 문제가 없다.

    • 일반적으로는 Block & Wakeup 방식이 더 좋음

      당연히 쓸데없이 CPU를 계속 쓰면서 기다릴 필요가 없이 자원을 누군가가 가지고 있다고 하면 그냥 CPU 반납하고 Block 상태로 들어가는게 전체적으로 CPU도 훨씬 더 의미있게 이용하는 비율이 높아질 것임

Two Types of Semaphores

Semaphore도 2가지 종류로 나눠볼 수 있는데…(이미 설명했던 개념)

  • Counting semaphore

    semaphore 변수 값이 5나 10 이렇게 주어질 수 있는 경우
    (즉, 자원의 개수가 여러개 있어서 여분이 있으면 가져다 쓸 수 있는 경우)

    • 도메인이 0 이상인 임의의 정수값

    • 주로 resource counting에 사용

      여분의 자원을 counting 하는 용도로

  • Binary semaphore (=mutex)

    자원의 개수가 하나인 경우
    (보통, 락을 걸 때 자원의 개수를 하나로 셋팅해서 사용… 이와 같은 경우)

    • 0 또는 1 값만 가질 수 있는 semaphore
    • 주로 mutual exclusion (lock/unlock)에 사용

Deadlock and Starvation

Semaphore는 쓸 때 주의할 점이 있다. 원치않는 문제가 생길 수 있는데…

  • Deadlock

    • 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

  • S와 Q가 1로 초기화된 semaphore라 하자.
    image

    어떤 일을 하기 위해서 세마포어 S하고 Q를 모두 획득한 다음에 일을 하고, 반환하는 방식을 P0, P1 둘다 하는데… S와 Q는 배타적으로 프로세스 하나만 동시에 사용할 수 있는 1로 초기화된 세마포어라고 하면…

    P0이 자원 하나(S)를 획득하고, P1은 또다른 자원 하나(Q)를 획득한 상태에서 둘이서 하나씩 쥐고 놓지는 않고 상대방이 가진 것을 기다리면서 영원히 조건을 충족하지 못하는 이런 Deadlock 상황의 문제가 발생할 수 있다.

    이것은 어떻게 해결해야 하느냐?
    자원을 획득하는 순서를 똑같이 맞춰주면 해결 가능
    image
    (프로그래머가 유의를 해서 작성해야할 부분)

  • Starvation

    • indefinite blocking. 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

      원래 Starvation이 특정한 프로세스가 영원히 자원을 얻지 못하고 무한히 기다려야되는 상황을 말하는데, 위에 나와있는 deadlock도 일종의 Starvation이라고 볼 수도 있다.

      그러나, 여기서 특별히 이야기하는 Starvation은 특정 프로세스들만 자원을 자기들끼리 공유하면서 다른 프로세스는 영원히 자기 차례가 오지 못하게하는 그런 것을 Starvation이라고 부른 것이다.

Classical Problems of Synchronization

Synchronization과 관련된 고전적인 문제 3가지

  • Bounded-Buffer Problem (Producer-Consumer Problem)
  • Readers and Writers Problem
  • Dining-Philosophers Problem
Bounded Buffer Problem (Producer-Consumer Problem(생산자-소비자 문제))

Bounded Buffer는 임시로 데이터를 저장하는 공간인 Buffer의 크기가 유한한 것을 말함.

image

생산자 프로세스, 소비자 프로세스 두 종류가 있음. 이것이 여러개 있는 상황이라고 생각하면 된다.
생산자는 어떤 역할을 하냐면 공유 버퍼에다가 데이터를 하나 만들어서 집어넣는 역할을 하게 된다. (주황색으로 표시된 버퍼들이 데이터가 들어있는 버퍼, 흰색으로 구멍이 뚫려있는 것은 비어있는 버퍼)

여기서 Synchronization과 관련해서 어떤 문제가 발생할 수 있을까?
먼저 한 가지 문제는 이게 공유 버퍼이기 때문에 생산자가 둘이 동시에 도착해서 비어있는 버퍼를 둘이서 봤고, 생산자 둘이 동시에 데이터를 만들어 집어넣으면 생기는 문제…
그래서 생산자가 비어있는 버퍼를 확인하고 데이터를 만들어서 집어넣는 작업을 그냥하는 것이 아니라 공유 버퍼에 lock을 걸어서 다른 프로세스들의 접근을 막은 다음 데이터를 집어넣고, 데이터 집어넣는 작업이 끝났으면 lock을 풀어서 다른 생산자나 소비자가 공유 버퍼를 접근할 수 있게 해야함.
소비자도 마찬가지의 문제가 있기 때문에, 버퍼에다가 lock을 걸어서 데이터를 꺼내고 lock을 풀어야 함.

그 다음 또 다른 문제가 있다… Bounded Buffer이기 때문에(버퍼가 유한하기 때문에) 생기는 문제이다.
만약에 생산자들이 한꺼번에 도착해가지고 데이터를 순식간에 집어넣어 공유 버퍼를 가득 채운 상황에서 소비자가 와서 데이터를 꺼내가면 좋겠는데, 소비자는 안오고 생산자가 또 도착해서 데이터를 만들어 집어넣고 싶은 상황이라면 생산자 입장에서는 사용할 수 있는 자원이 없는 상태로 볼 수 있다. 생산자는 소비자가 나타나서 내용을 꺼내가야지만 빈 버퍼가 생겨 생산자는 데이터를 만들어 집어넣을 수 있다.
그래서, 생산자 입장에서는 비어있는 버퍼의 개수가 counting 해야 될 자원이 되고, 이 개수가 0이라면 생산자 프로세스는 데이터를 집어넣는 것이 가능한 자원이 없기 때문에 소비자 프로세스가 데이터를 꺼내갈 때까지 기다려야 한다.

반대로, 소비자 입장에서 갑자기 소비자들이 도착해서 데이터를 다 꺼내가고 비어버렸다. 이런 상황에서 소비자 프로세스가 도착하면 꺼내갈게 없다.
즉, 소비자 입장에서는 내용이 들어있는 버퍼가 자원이고, 그 개수가 0이 되면 소비자 프로세스는 꺼내가는 것이 가능한 자원이 없기 때문에 생산자 프로세스가 내용을 만들어서 집어 넣어줄 때까지 기다려야 한다.

그래서, 생산자-소비자 문제에서는 세마포어를 이용해서 해야 될 업무가 크게 2가지가 있다.
둘이 동시에 공유 버퍼를 접근하는 것을 막기 위해서 공유 버퍼 전체에다가 lock을 걸어서 나 혼자 배타적으로 접근하게 하고, 접근이 끝났으면 lock을 풀어주는 것
그리고, 버퍼가 가득차거나 버퍼가 비었을 때 생산자 또는 소비자가 내용을 만들어줄 버퍼가 없거나 또는 꺼내갈 버퍼가 없을 수가 있다, 그럴 때 가용 자원의 개수를 세는 Counting Semaphore 용도로 Semaphore 변수가 필요함

Shared data

  • buffer 자체 및 buffer 조작 변수(empty/full buffer의 시작 위치)

    공유 버퍼 자체가 공유 데이터가 되고, 버퍼 조작을 하는 변수(공유 데이터에서 비어있는 위치가 어디있고, 내용이 들어있는 위치가 어딘지 나타내는 포인터 변수같은…) 이런것들이 생산자나 소비자들이 모두 접근할 수 있는 데이터이기 때문에 공유 데이터임.
    접근을 하려면 lock을 걸고, 푸는 절차가 필요

Synchronization variables

  • mutual exclusion

    → Need binary semaphore (shared data의 mutual exclusion을 위해)

    lock을 걸고 푸는 용도로 semaphore변수 사용이 필요

  • resource count

    → Need integer semaphore (남은 full/empty buffer의 수 표시)

    자원의 개수를 counting 하는 용도로 semaphore변수 필요
    (생산자 입장의 자원의 개수 : 비어있는 버퍼의 개수, 소비자 입장 : 들어있는 버퍼의 개수)

그래서, 이 생산자-소비자 문제를 semaphore를 이용한 코드 형태로 표현하면 다음과 같이 표현된다.

image

먼저, semaphore 변수를 3개를 두고 있다.
lock을 걸기 위한 변수인 mutex… (mutex = 1은 공유 버퍼를 하나의 프로세스만 접근할 수 있게 lock을 거는 용도의 semaphore)
내용이 들어있는 버퍼의 개수를 세기 위한 변수 full
비어있는 버퍼의 개수를 세기 위한 변수 empty (처음에는 전부 다 비어있을테니까 비어있는 버퍼의 개수가 empty = n이 되는 것임)

생산자 프로세스 부분…
내용을 만드는 코드produce an item in x item x를 만든 다음에 이것을 공유 버퍼에 집어넣고자 하는 것임.
집어 넣기 전에 집어 넣을 빈 버퍼가 있는지 확인 P(empty); 빈 버퍼가 있으면 그것을 획득하는 과정임
그 다음 버퍼에다가 데이터를 집어넣기 위해서 P 연산을 통해서 버퍼 전체에다가 lock을 검 P(mutex);
그리고 나서, 버퍼에다가 데이터를 집어넣음 add x to buffer
버퍼 조작이 끝났으면 buffer에 걸었던 lock을 품 V(mutex);
마지막으로, 내용이 들어있는 buffer의 개수를 증가시키는 과정 V(full);(P 연산은 자원을 획득, V 연산은 자원을 반납하는 과정이지만 여기서, empty는 프로듀서(생산자) 입장에서 빈 버퍼가 자원이 되고 P(empty);, 내용이 들어있는 버퍼는 full 소비자 입장에서의 자원이기 때문에 소비자 입장에서의 자원을 하나 증가시켜서 V(full); 소비자가 내용이 들어있는 버퍼가 없어서 기다렸다면 깨워주는 역할을 함… 소비자는 반대로 구성이 되있음)

Readers-Writers Problem

프로세스가 읽는 프로세스, 쓰는 프로세스 두 종류가 있음

  • 한 프로세스가 DB에 write 중일 때 다른 process가 접근하면 안됨
  • read는 동시에 여럿이 해도 됨
  • solution
    • Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다
    • Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다
    • 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다
    • Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다

Shared data

  • DB 자체

  • readcount; /* 현재 DB에 접근 중인 Reader의 수 */

    readcount도 reader들이 동시에 접근할 수 있는 데이터기 때문에 공유 데이터

Synchronization variables

  • mutex
    /* 공유 변수 readcount를 접근하는 코드(critical section)의 mutual exclusion 보장을 위해 사용 */

    (readcount라는 변수에 대해서 lock을 거는 용도로 mutex라는 바이너리 세마포어를 사용)

  • db
    /* Reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할 */

    (DB에 대한 lock을 거는 용도로 db라는 바이너리 세마포어를 사용함)

코드

image

DB :: 공유 데이터, 이것을 접근하려면 lock을 걸어야 된다는 얘기.
db :: DB에 대한 lock에 해당하는 세마포어 변수

읽는 작업은 여럿이 동시에 해도되는데, 어쨋든 lock은 걸어야 한다.
lock을 걸지 않고 읽으면 writer가 와서 lock이 안걸려있네? 하고 lock을 걸고 써버리니까…
lock은 걸어놨지만 내가 읽으려고 lock을 건거라면 다른 읽는 친구들이 왔을 때 같이 읽을 수 있게 해줘야 된다.
그래서, 여기서 readcount라는 변수(공유변수)를 하나 둔다.
만약 내가 최초의 reader라면(아무도 읽고있지 않은 상황에서 내가 처음 읽으러 들어온거라면) DB에다가 lock을 걸고P(db);
만약 최초의 reader가 아니라면(누군가가 DB에서 읽고 있는 상황에서 도착한 reader라면)(readcount를 증가시켰을 때 누군가가 이미 읽고 있으니까 1이 아니라 그거보다 더 큰 값일 것이다. 그럴 때는) lock을 걸지 않음.

근데, readcount라는 변수가 공유변수이기 때문에 그냥 증가시키게 되면 문제가 생길 것이다. 여러 reader가 동시에 와서 readcount를 증가시키다보면 2개를 증가했는데도 결국에는 하나만 증가되는 이런 문제가 생길 수 있는 것임.
그래서, readcount를 바꾸기 위해서도 이 공유 변수에 대해서 lock을 걸 필요가 있다. readcount라는 공유 변수를 위한 lock이 mutex라는 세마포어 변수임.

그래서, readcount를 건드리기 위해서 이 변수에 대해서 lock을 걸고P(mutex);, readcount를 증가시키고readcount++;, 그럼에도 불구하고 이 값이 1이라고 하면if (readcount == 1) 내가 최초에 읽으려는 프로세스니까 DB전체에다가 lock을 걸고P(db); 이러한 공유 변수를 건드리는 작업이 끝났으면 readcount에 대한 lock을 풀어주는 것이다.V(mutex);
그런 다음에 DB를 읽고reading DB is performed DB를 읽는 작업이 다 끝났으면 빠져나가면 되는데 만약에 내가 지금 제일 마지막으로 읽는 프로세스라고 하면if (readcount == 0) DB에 건 lock을 풀어준다.V(db);
(여기서도 readcount라는 변수를 건드리기 때문에 그거에 대해서 lock을 걸고P(mutex);, 끝나면 lock을 품V(mutex);)

이 코드 상으로 Reader들이 계속 들어오게 되면 Writer는 계속 기다려야되는 Starvation 문제가 발생함…
이런 문제를 해결하기 위해서 큐에다가 우선 순위를 둬서 Writer가 일정 수준 이상 기다리지 않게 지나치게 늦게 들어온 Reader는 (read를 해서 lock이 걸려있지만) 잠깐 기다리라고 해놓고 먼저 빠져나가서 lock을 풀게 한 다음 Writer가 접근할 수 있게 해줄 수 있을 것임

Dining-Philosophers Problem

식사하는 철학자 문제

image

5명의 철학자가 원탁에 앉아있다.
이 원탁은 식탁이면서 생각하는 원탁을 겸하고 있다.
이 5명의 철학자가 하는 일은 2가지로 나눠진다.
생각하는 일, 생각하다가 배고파지면 밥 먹는 일

근데 이 5명의 철학자가 생각하는 시간과 배고파지는 주기가 각각 다르다.
배가 고파지면 자신의 왼쪽과 오른쪽에 있는 젓가락을 집어서 밥을 먹고, 배가 불러졌으면 다시 젓가락을 놓고 생각을 하게 되고, 또 생각하다가 배가 고파지면 젓가락을 집어서 밥을 먹고 이런 일을 계속 무한히 반복

밥을 먹기 위해서는 젓가락 두 짝을 집어야 되는데, 그 옆에 있는 철학자가 이미 젓가락을 집고 밥을 먹고 있다면 그 젓가락을 못집을 것이다.
이게 공유 자원이기 때문에, 그리고 각각의 5짝의 젓가락은 1로 초기화 되있다. (동시에 둘이 잡을 수 없고 혼자서만 젓가락을 잡을 수 있다)

그래서, 왼쪽 젓가락을 잡고P(chopstick[i]);, 오른쪽 젓가락을 잡고P(chopstick[(i+1) % 5]);…
(만약 잡을 수 없는 상황이라면 P 연산에서 옆에 철학자가 젓가락을 놓을 때까지 기다려야 되는 상황)
양쪽을 다 잡았으면 밥을 먹는다eat();. 밥을 다 먹었으면 왼쪽과 오른쪽 젓가락을 순서대로 놓는다V(chopstick[i]);, V(chopstick[(i+1) % 5]);. 그러면 옆에 철학자가 만약 배가 고팠다면 젓가락을 잡을 수 있는 이런 상황이다.

이게 식사하는 철학자 문제를 세마포어를 이용해서 간단하게 코딩을 해놓은 것이다.

  • 앞의 solution의 문제점

    • Deadlock 가능성이 있다

      Deadlock :: 더 이상 아무것도 진행이 안되고 막혀있는 상황

    • 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우

  • 해결 방안

    • 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다

    • 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다

    • 비대칭

      • 짝수 철학자는 왼쪽 젓가락부터 집도록
        홀수 철학자는 오른쪽 젓가락부터 집도록

        하나의 젓가락이 더 우선 순위가 높아서 그것을 잡기 전에는 나머지 젓가락을 못잡기 때문에 이 문제가 해결이 됨

두번째 나와있는 젓가락을 두 개 모두 잡을 수 있을 때만 잡는 권한을 준다에 해당하는 코드 (아래)
image

이 코드가 세마포어의 원리에 맞게 잘 짜여진 코드는 아니라 이해하는데 불편할 수 있다. 그냥 이게 잘 동작하는지 그것만 파악하면 된다.

5명의 철학자 i가 하는 일은 먹거나eat(); 생각하거나think(); 이 두 가지가 무한 반복이고, 먹기 전에는 젓가락을 잡는 pickup(i); 과 젓가락을 놓는 putdown(i); 이 두개의 함수를 호출하고 있다. (이미지 맨 좌측)

여기서 사용된 변수를 보면(이미지 최상단 좌측) semaphore변수 self 해가지고 5개가 있다semaphore self[5] = 0;. 이 5개는 각각의 5명의 철학자가 젓가락 2개를 다 잡을 수 있어서 젓가락 잡는 권한을 줄 것인가, 말 것인가 나타내는 semaphore변수.(예를 들어 semaphore self[1] = 0; 이면 1번 철학자가 젓가락 2개를 다 잡을 수 있는 권한이 없다는 얘기, self[3] = 1;이면 3번 철학자는 젓가락 2개를 다 잡을 수 있는 권한이 있다.)
그 다음, 5명의 철학자의 상태를 나타내는 공유 변수가 있다.enum {thinking, hungry, eating} state[5]; 그리고, 생각하고 있는 상태, 배고픈 상태, 먹는 상태 이렇게 5명의 철학자의 상태를 3가지 상태로 나눠놓은 것이다.
그 다음에 mutex라는 lock이 있는데semaphore mutex = 1;, 이것은 5명 철학자의 상태state를 바꾸는거는 본인만 상태를 바꿀 수 있는게 아니라 옆에 철학자도 이 사람 혹은 다른 사람의 상태를 바꿀 수 있는 공유 변수임… 그 공유 변수에 대한 동시 접근을 막기 위해서 lock을 나타내는 mutex 변수를 하나 두고 있음.

철학자 i가 배가 고파서 젓가락을 집는 함수를 호출pickup(i);하게 되면, 그 철학자 i는 먼저 상태state[i]를 건드리기 때문에, lock을 걸고P(mutex);, 그런 작업이 끝나면 lock을 푸는 코드V(mutex);가 들어있다.
이 사람이 젓가락 집는 함수를 호출했기 때문에 자신의 상태를 hungry로 바꿔놓고state[i] = hungry;, 그런 다음에 철학자 i가 젓가락 2개를 다 잡을 수 있는 상태인지를 테스트해본다test(i);.

test 함수로 가서 보면void test (int i) 젓가락 2개를 다 잡을 수 있는 권한을 언제 주느냐하면 왼쪽 철학자도 밥먹고 있지 않고, 오른쪽 철학자도 밥먹고 있지 않고, 그리고 내가 지금 배가 고픈 상태 이 세 개를 모두 만족할 때에만if (state[(i+4)%5]!= eating && state[i]==hungry && state[(i+1)%5] != eating) 그 철학자의 상태를 밥먹는 상태로 바꾸어 주고state[i] = eating;, 그 철학자에 대한 젓가락 잡는 권한을 주는 것이다V(self[i]);.
(이게 대부분 이해가 안되는 부분일 것이다. 보통 세마포어 하면 원래 자원의 개수를 초기 값으로 하고, 그 자원의 개수가 1이거나 또는 1이상인 값을 처음에 주게 되는 것이다. 즉, 두개를 다 잡을 수 있는 권한을 보통은 1을 줘서 시작을 하는데…)
(이 세마포어 코드는 특이하게도 처음에는 두개다 잡을 수 있는 권한을 0으로 놓고 시작을 한 다음에semaphore self[5] = 0; test하는 단계에서 주변 철학자들이 밥을 먹고 있지 않으면서, 내가 배가 고프면 그때 나의 젓가락 두개를 잡을 수 있는 권한을 주는 것이다. (V 연산은 0이었던 값을 1로 바꾸는 역할을 함))

test(test(i);)가 끝났으면 젓가락 잡을 수 있는 권한을 철학자 i가 얻은 상황이므로 P 연산을 해서 1이었던 것을 0으로 바꾸고P(self[i]); pickup 함수가 끝난다.(젓가락 2개를 다 잡은 것임)
(만약 이 test 연산에서 왼쪽 철학자나 오른쪽 철학자 중에 누군가가 밥을 먹고 있었다면 내가 젓가락 2개를 다 잡을 수 없는 상황일 것이다. 그러면 그 if문을 만족하지 못하기 때문에 젓가락 잡을 수 있는 권한은 얻지 못하고, test함수가 끝나게 된다. 그 경우에는 P 연산을 하더라도 철학자 i의 젓가락 잡을 권한이 0인 상태이기 때문에 젓가락을 못 얻고 P(self[i]);에서 self[i]가 1이 될 때까지 기다려야 됨.)
(이것은 누가 1로 만들어주느냐 하면 인접한 철학자가 밥을 다 먹고 내려놓았을 때 내가 젓가락 두개를 다 잡을 수 있는 권한이 생기든지 말든지 할 것임)

그래서, 젓가락을 2개를 다 잡았으면 밥을 먹고eat(); 젓가락을 내려놓을 때putdown(i); 그 때 이 철학자는 상태가 생각하는 상태가 되고state[i] = thinking; 그리고, 왼쪽 철학자하고 오른쪽 철학자에 대한 test를 해주는 것이다.test((i+4) % 5);, test((i+1) % 5); 즉, 왼쪽 철학자가 혹시 배가 고픈데 아까 내가 밥먹고 있는 바람에 젓가락을 못잡고 있는 상황이면 잡을 수 있게 해주는 코드… 오른쪽 철학자에 대해서도 똑같은 코드를 실행해서 젓가락을 내려놓을 때 인접 철학자를 챙기는 것임
(예를 들어서, 왼쪽 철학자에 대해서 test 연산을 하게 되면test((i+4) % 5); 그 왼쪽 철학자의 양 인접한 철학자들이 밥을 먹고 있지 않고(젓가락 내려놓은 다음에 이 코드 들어왔으니까 적어도 한쪽은 밥을 먹고 있지 않을 것이다. 반대쪽 젓가락도 지금 가능한지 체크해보고), 그리고 왼쪽 철학자가 아까 배가 고팠는데 pickup을 못해서 기다리고 있는 상황이라면 이 철학자가 밥을 먹게 해주고 왼쪽 철학자에 대해서 self값을 주는 것임.)
(그럼 아까 왼쪽 철학자가 여기서(P(self[i]);) P연산을 못하고 기다리고 있었다면 그제서야 P 연산을 빠져나와서 1이었던 것을 0으로 잽싸게 바꾸고 pickup이 끝나서 밥을 먹게 되는 것이다.)

Monitor

  • Semaphore의 문제점

    • 코딩하기 힘들다
    • 정확성(correctness)의 입증이 어렵다
    • 자발적 협력(voluntary cooperation)이 필요하다
    • 한번의 실수가 모든 시스템에 치명적 영향

  • 예

    image

어떤 사람이 코딩을 굉장히 많이 하면서 좌측과 같이 실수를 했다면… 둘이 동시에 들어가는 문제가 생김
코딩 하는 사람이 정확하게 코딩을 했을 때는 잘 동작하지만, 한번만이라도 실수를 하면 Semaphore로 문제가 제대로 해결이 안되는 상황 발생

우측과 같이 실수를 하면 영원히 P 상황을 빠져나갈 수가 없음… lock이 반환이 안되고 계속 0인 상황에서 어느 누구도 critical section에 들어가지 못하는 문제가 생김

그래서 Monitor라는 것을 Synchronization을 위해서 제공하고 있다.

Monitor

  • 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct

    모니터는 특별히 프로그래밍 언어 차원에서 Synchronization 문제를 해결하는 high-level synchronization construct라고 얘기할 수 있다.
    객체 지향 프로그래밍 언어 같은 것을 보면 어떤 객체를 중심으로 그 Operation들이 정의가 되는 것을 알 수가 있다.

    image

그런거에 기반해서 Monitor는 이런식으로 어떤 공유 데이터를 접근하기 위해서는 이 모니터라고 정의된 내부의 procedure를 통해서만 공유 데이터를 접근할 수 있게 만들어 놓는 것임

image

그래서 예를 들어서 이런 공유 데이터들이 있다.(shared data)
그러면, 이 공유 데이터를 밖에서 아무나 접근할 수 있는게 아니라 모니터 안에다가 공유 데이터와 그 공유 데이터를 접근하는 procedure(프로시저)를 정의해놓고(operations)
만약에 이 공유 데이터를 접근하겠다라고 하면 procedure(프로시저)를 통해서만 접근할 수 있게 하는 것.

그리고, 모니터가 원천적으로 이 모니터 내부에 있는 프로시저는 동시에 여러개가 실행이 안되도록 통제를 하는 권한을 주는 것
(프로그램 입장에서 이렇게 하면 락을 걸 필요가 없다!)
모니터는 기본적으로 모니터에 대한 동시접근을 허락하지 않는다. 모니터 자체가 그렇게 만들어져서 프로그래머가 락을 걸 필요가 없이 그냥 모니터에 있는 공유 데이터를 안에 있는 프로시저를 이용해서 접근하면 된다.
그러면, 모니터가 알아서 어차피 하나의 프로세스만 모니터를 접근할 수 있게 하고 나머지 프로세스들은 줄서서 기다리도록 함(entry queue)

  • 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능

  • 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요 없음

  • 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
    condition x, y;

    Semaphore에서 자원의 개수를 세거나 이런건 필요했다.
    지금 락을 거는건 할 필요가 없다고 했지만 자원이 몇개 인지를 세고, 자원이 있으면 접근할 수 있게 해주고, 자원이 없으면 기다리게 하는 이런건 모니터에도 여전히 필요함.
    그걸 위해서 semaphore변수처럼 비슷한 역할을 해주는 condition variable이라는 것이 모니터에 있다.

    만약에 x라는 자원이 여분이 있으면 바로 접근을 하게 해주고,

  • Condition variable은 wait와 signal 연산에 의해서만 접근 가능
    x.wait();
    x.wait()을 invoke한 프로세스는 다른 프로세스가
    x.signal()을 invoke하기 전까지 suspend된다

    x.signal();
    x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다
    Suspend된 프로세스가 없으면 아무일도 일어나지 않는다

뭔가 여분이 없어서 기다려야되면 그것을 기다리는 줄에 줄서서 기다리도록 하는 함수 정의 :: x.wait();

접근을 다하고 빠져나갈 때는 x.signal(); 을 호출해서 혹시 기다리고 있는 프로세스가 있으면 빠져나갈 수 있게 해줌

Bounded-Buffer Problem

image

아까 생산자-소비자 문제의 Semaphore(세마포어) 코드를 모니터 코드로 그냥 변환한 것임. 그랬을 때 위 이미지와 같은식으로 코딩이 됨.

아까 Semaphore 코드에서 생산자는 공유 버퍼에 접근하기 위해서 락을 걸고, 락을 풀고 그 다음에 내용이 비어있는 버퍼의 개수가 있으면 그것을 얻어야 했고,
소비자는 내용이 들어있는 버퍼를 하나 얻어서 공유 버퍼를 접근하기 위해서 락을 걸고, 락을 푸는 이런 절차를 거쳤다.

그런데, 모니터에서는 락을 걸거나 풀 필요가 없다.
위 이미지를 보면 공유 버퍼가 모니터 안에 정의가 되있기 때문에 생산하거나 소비하는 작업을 하기 위해서는 모니터 내부 코드를 실행해야되고, 그러면 생산자든 소비자든 하나의 프로세스만 모니터 안에서 활성화가 되기 때문에 굳이 락을 걸지 않아도 생산자가 접근하는 동안에 또 다른 생산자나 소비자가 접근해서 생기는 문제는 고려할 필요가 없다.
즉, 공유 버퍼에다가 데이터를 집어넣거나 빼는 작업 앞, 뒤에 락을 거는게 없다.
생산자 입장void produce (int x)에서는 (비어있는 버퍼가 필요하기 때문에) 만약 비어있는 버퍼가 없다면if there is no empty buffer 비어있는 버퍼를 기다리는 줄에 줄서서 기다리게 block 상태로 보내게 되는 것이고empty.wait();,
만약에 비어있는 버퍼가 있다면 그냥 버퍼에다가 내용을 하나 집어넣어주면 될 것이다add x to an empty buffer. 그리고, 그 작업이 끝났으면 혹시 내용이 들어있는 버퍼가 없어서 잠들어있는 소비자 프로세스가 있다면 그것을 깨워주는 코드full.signal();가 추가되있는 것이다.

반대로, 소비자 입장void consume (int *x)에서는 내용이 들어있는 버퍼가 없으면 기다려야 됨, 그럴 때는if there is no full buffer 내용이 들어있는 버퍼를 기다리는 줄에 줄서서 잠들게 되고full.wait();,
만약에 내용이 들어있는 버퍼가 있다면 그걸 하나 꺼내가고remove an item from buffer and store it to *x, 비어있는 버퍼를 기다리는 생산자가 잠들어있다면 그것을 깨워주는empty.signal(); 이런식으로 코딩 되어있음.

그렇기 때문에, 세마포어보다 더 프로그래머 입장에서 이해도 쉽고, 락을 걸 필요도 없다는 장점이 있다.

image

즉, 모니터 안에서 하나의 프로세스만 활성화되기 때문에 나머지 프로세스들은 줄서서 기다려야되는 것이 있고(entry queue), 그 다음에 이 모니터 안에서 공유 자원의 개수가 없어서 그래서 기다려야 된다면 예를 들면, 내용이 들어있는 버퍼를 기다리는 프로세스는 x에서 줄서고, 비어있는 버퍼를 기다리는 프로세스는 y에서 줄서서 기다리고…
그러다가 그런 버퍼가 생기게 되면 그러면 (x나 y 큐 그에 맞는)큐에 줄 서 있는 프로세스 하나를 깨워주는 그게 signal()연산

모니터에서는, 아까 설명했듯이 모니터 안에서 어떤 코드를 실행하다가 조건 충족이 되지 않아서 오래 기다려야 되는 상황이면 그 프로세스를 잠들게 한다.
어떤 조건이 충족이 안되서 잠들게 했는지에 따라서 그 조건에 해당하는 것을 변수로 둘 수가 있는데, 이것을 condition variable이라고 한다.queues associated with x, y conditions

Dining Philosophers Example

(참고: 식사하는 철학자 문제에 대한 Semaphore(세마포어) 버전에 대한 내용, 코드 …차이점 보기)

식사하는 철학자 문제에 대한 모니터 버전의 코드

image

세마포어 버전과 마찬가지로 여기서도 state 변수는 5명의 철학자 각각에 대해서 상태를 표시할 수 있고, 본인만 본인의 상태를 바꿀 수 있는게 아니라 인접 철학자들도 상태를 바꿀 수 있게 코딩 되있기 때문에 공유 변수이자 공유 데이터임.

여기선, 모니터 안에서 공유 데이터 접근하는 코드를 만들었기 때문에, 락을 걸거나 푸는게 필요 없음

맨 위로 이동하기

Leave a comment

You may also enjoy