[OS] 프로세스 동기화(2)

위영민(Victor)·2021년 5월 17일
OS
0

Semaphore(세마포어)

정의

= lock/unlock 기능, 공유 자원을 획득하게 해준다.

  • 앞선, 일반 방식들을 추상화시킨 것

  • Semaphore S == 자원의 갯수

    • Integer variable
    • 두 가지 Atomic 연산에 의해서만 접근이 가능함

P(S), V(S) 연산

[P(S)] 	// S변수(=공유변수)를 획득하는 경우의 연산
----------------------------------------------
while(S <= 0) do no-op;	// 자원이 없다면 wait..
S--;	// 음수일 경우, Busy-wait 발생
[V(S)] 	// S변수(=공유변수)를 다 사용하고 반납하는 경우의 연산
-------------------------------------------------------
S--;

Critical Section of n Process

  • semaphore가 지원 된다면, 프로그래머는 P&V 연산만 넣으면 된다.

Shared Data

semaphore mutex;		// init = 1 (1개의 자원이 있음)

공유자원 mutex로 Critical Section을 제어할 수 있음

do {
    P(mutex);			// Critical Section 들어가는 경우 (자원 1개 소모)
    critical section
    V(mutex);			// Critical Section 나오는0 경우 (자원 1개 반납)
    remainder section
} while(1);

이 방식의 문제점

  • Busy-wait(Spin-lock) 현상이 여전히 존재한다.
  • Block & Wake-Up(Sleep Lock)방식으로 해결가능
    = 자원이 없을 때, Block 됐다가, 자원 생기면 깨어남

Block / wake up

Semaphore를 다음과 같이 정의함

typedef struct
{
    int value;			// semaphore
    struct process *L;	// process wait queue
} Semaphores

Block과 Wake-Up을 다음과 같이 가정

  • Block
    • 커널은 Block을 호출한 프로세스를 Suspend(지연)시킴
    • 이 프로세스의 PCB를 Semaphore에 대한 wait queue에 넣음
  • Wakeup(P)
    • Block된 프로세스 P를 WakeUp 시킴
    • 이 프로세스의 PCB를 Ready queue로 옮김

semaphore를 기다리면서, 잠들어 있는 PCB를 연결

Implementation : block/wakeup version of P() & V()

P(S)
----

S.value--;			// Critical Section 들어갈 준비
if(S.value < 0)		// 음수면 못 들어감, Block 상태
{
    add this process to S.L;
    block();
}
V(S)
----

S.value++;			// 자원을 내놓았는데도
if(S.value <= 0)	// 자원이 0 이하라는 것은, 다른 누군가(프로세스)가 잠들어있는 놈들이 존재한다는 것
{
    remove a process P from S.L;
    wakeup(P);
}
  • 여기서 음수라는 것은 누군가 자원을 쓰기 위해 기다리고 있다는 의미

Busy-wait VS Block-wakeup

무엇이 더 좋은가요 ?

  • 일반적으론, CPU 소모를 줄일 수 있는 Block-WakeUp 방식이 좋음
  • 그러나, Block-WakeUp 방식은, 결국 오버헤드가 존재
    • 어떤 Block 프로세스를, WakeUp하는 과정에서, Ready queue로 배치하거나, 그 반대의 wait queue로 배치하는데 있어서 발생하는 오버헤드

그래서
Block/wakeup overhead v.s. Critical section 길이

  • critical section 길이가 길면, Block/wakeup이 적당
  • critical section 길이가 매우 짧으면, busy-wait 가 적당

세마포어 유형

Two types of Semaphores

  1. Counting semaphore

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

  • 주로 resource counting에 사용

  1. Binary semaphore (=mutex)

  • 0 또는 1 값만 가질 수 있는 semaphore

  • 주로 mutual exclusion (lock/unlock)에 사용

세마포어 사용시 주의할점

1. DeadLock(교착상태)

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

EX) S와 Q가 1로 초기화된 semaphore라 하자.

P0과 P1는 S와 Q를 동시에 가질 수 없음

  • 자원 갖는 순서를 (S->Q)로 지정하면 해결 가능.

2. Starvation(기아현상, Indefinite Blocking)

= 프로세스가 suspend된 이유에 해당하는 semaphore 큐에서 빠져나갈 수 없는 현상

Monitor(모니터)

정의

= 동시 수행 중인 프로세스 사이에서 abstract data type의 안전 공유를 보장하기 위한 high-level synchronization construct (semaphore에 비해 프로그래머의 부담을 줄여주고, monitor가 알아서 해줌)

monitor monitor-name
{   shared variable declarations
    procedure body P1(...){
        ...
    }
    procedure body P2(...){
        ...
    }
    {
        initialization code
    }
}

monitor라고 정의된 내부의 프로시저를 통해서만 공유 데이터에 접근 가능

  • monitor내부에 A, B프로세스(각각 공유 데이터를 접근하는 코드)를 가지고 있다.
  • monitor는 한번에 하나의 프로세스만 활용 가능
  • 프로그래머가 동기화 제약조건을 명시적으로 코딩할 필요가 X **(lock을 걸 필요가 X)
    • 만약, 실행 도중에 CPU를 빼앗겨도, monitor내부에 active한 상태로 남아있게 된다.
      따라서, 다른 프로세스가 monitor내의 코드를 실행하지 못하고 밖의 큐에 줄 서서 있게 된다. monitor 내부에 active한 자원 수가 0이 될 때, 밖에서 기다리던 프로세스가 들어온다.
  • 프로세스가 monitor 안에서 기다릴 수 있도록 하기 위해 Condition Variable사용
    (자원 여분 여부/ 어떤 조건을 충족시키지 못해 잠들거나 깨울 때)
  • (condition x, y : 자원이 있으면 바로 접근, 없으면 기다리게 함
    (condition variable은 값을 가지는 변수가 아님!)

condition variable은 wait 와 signal 연산에 의해서만 접근 가능.

x.wait()

  • 자원 x를 원하는 줄에 기다리는..
  • x. wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend된다.

x.signal()

  • 자원 x를 기다리는 프로세스가 있으면 빠져나올 수 있도록
  • x.signal()은 정확하게 하나의 suspend된 프로세스를 resume 한다.
    suspend된 프로세스가 없으면 아무 일도 일어나지 않음.

Block-wakeup과 wait-signal의 차이점

  • 한 프로세스가 지금 막, Sleep 하려하고, 다른 프로세스가 이 프로세스를 WakeUp 하려고하면, Sleep과 WakeUp은 동작 불능 == 생산자-소비자 문제를 생각해보자.
  • 반면, 모니터 프로시져의 경우, 자동으로 모니터 자체에서 상호배제가 이뤄지므로, 문맥교환 될 것을 걱정하지 않고 연산을 진행해도 된다.

고전적인 Synchronization 문제들 -> Monitor방식으로

(1) monitor bounded-bufffer

monitor내부에 monitor bounded_buffer {
    int buffer[N];          
    // 공유 버퍼가 모니터 안에 정의(굳이 lock을 걸지 않아도 produce나 consume 중 하나만 실행됨)
    condition full, empty;
    // 값을 가지지 않고, 자신의 큐에 프로세스를 매달아 sleep시키거나, 큐에서 프로세스를 깨우는 역할만 함
    
    void produce(int x) {
        empty.wait();   // 빈 버퍼가 없으면 줄서서 기다림
        add x to an empty buffer
        full.signal();  // 다 채운 후, 기다리는 프로세스를 깨워줌
    }
    
    void consume(int *x) {
        full.wait();    // 찬 버퍼가 없으면 줄서서 기다림
        remove an item from buffer and store it to *x
        empty.signal(); // 비운 후, 기다리는 프로세스를 깨워줌
    }
}

(2) Dining Philosophers (monitor ver.)

Each Philosopher: {
    pickup(i);      // enter monitor
    eat();
    putdown(i);     // enter monitor
    think();
}
​
monitor dining_philosopher {
    enum {thinking, hungry, eating} state[5];
    condition self[5];
    void pickup(int i) {
        state[i] = hungry;
        test(i);
        if (state[i] != eating)
            self[i].wait();      // wait here
    }
    
    void putdown(int i) {
        state[i] = thinking;
        test((i+4)%5);      
        test((i+1)%5);
    }
    
    void test(int i) {
        if ((state[(i+4)%5] != eating) && (state[i] == hungry) && (state[(i+1)%5] != eating)) {
            state[i] = eating;
            self[i].signal();   // wake up P(i)
        }
    }
    void init() {
        for(int i = 0; i < 5; i++)
            state[i] = thinking;
    }
}

자료 출처

  • 반효경 교수님 OS 온라인 강의
profile
위영민(Victor)
블로그 이사했습니다 :) 👉 https://www.youngminss-log.com/blog
이전 포스트

[OS] 프로세스 동기화 (1)

다음 포스트

[OS] 프로세스 동기화 (3)

0개의 댓글