[운영체제] 프로세스 동기화

이민선(Jasmine)·2024년 4월 14일
CS운영체제
0

[CS] 운영체제

목록 보기
6/8

컴퓨터 시스템 안에서 데이터가 접근되는 패턴

데이터가 저장되어 있는 위치(ex. memory, 디스크, 프로세스의 주소 공간)에서 데이터를 읽어와서 연산을 하고(ex. CPU, 컴퓨터 내부, 프로세스) 연산 결과를 원래 있던 위치에 저장함.

-> 2가지 이상의 연산 수정 결과를 동시에 원래 있던 위치에 저장하려고 할 때 동기화 문제 발생

경쟁 상태(race condition)

2개 이상의 주체가 동시에 데이터를 접근하려고 할 때 경쟁 상태 발생 가능성이 있음.

  • 공유 메모리를 사용하는 프로세스 간:

    • 같은 주소 공간을 공유하는 여러 프로세스가 동시에 메모리 접근을 시도할 경우.

  • 공유 데이터인 커널 내부 데이터 접근:

    • 한 프로세스가 시스템콜을 통해 커널 코드를 실행 중일 때, 컨텍스트 스위칭으로 인해 다른 프로세스의 시스템콜로 동일한 커널 데이터에 접근하는 경우. (즉, 두 프로세스의 주소 공간 간에는 데이터 공유가 없음에도 불구하고, 시스템 콜을 하는 동안 커널 주소 공간에 있는 동일한 데이터에 접근하게 되고 그 과정에서 CPU time out으로 CPU가 preempt되는 경우)
      (1) 프로세스 A가 system call read()후 CPU 레지스터에 커널 공유 주소 공간에 있던 count 변수 LOAD
      (2) 프로세스 A의 time quantum 만료.
      (3) 프로세스 B가 CPU를 preempt함. (context switching)
      (4) 프로세스 B가 system call read()후 CPU 레지스터에 커널 공유 주소 공간에 있던 count 변수 LOAD
      (5) 프로세스 B가 count++하고 커널 공유 주소 공간에 다시 저장 후 프로세스 B의 time out
      (6) 프로세스 A가 CPU를 돌려받고 count++ 후 커널 공유 주소 공간에 다시 저장
      • 최종적으로 count가 2만큼 증가하지 못하고 1만큼만 증가
        • 해결책: 커널 모드에서 수행 중일 때는 CPU를 preempt하지 않음. 커널모드에서 사용자 모드로 돌아갈 때 preempt
    • 커널 모드에서 실행 중인 커널 코드가 외부 인터럽트에 응답하는 과정에서 사용되는 코드로 인해 커널 데이터가 수정되는 경우.
      (1) 커널 모드에서 커널 공유 주소 공간에 있는 변수 값을 CPU 내부의 레지스터로 불러들이고(LOAD),
      -------이 때 인터럽트 들어왔다고 가정. 인터럽트 처리 루틴으로 넘어감. 커널에 있는 코드인 interrupt handler 실행. 커널 공유 주소 공간에 있던 동일한 count 변수를 레지스터로 불러들인 후 (LOAD), count--하고 메모리에 쓰기 연산 후 인터럽트 종료-------------
      (2) 처음에 불러들였던 레지스터 값을 count++하고,
      (3) 해당 레지스터 값을 메모리에 쓰기 연산
      • 최종적으로 count++된 결과만 반영이 된다.
        • 해결책: count 변수를 LOAD하고 커널 공유 주소 공간에 다시 count를 저장하는 동안에는 interrupt disable.

  • Multiprocessor 시스템:

    • 여러 CPU가 동일한 커널 주소 공간을 공유할 경우.
      - 위의 예시와 달리 다른 CPU의 interrupt를 disable할 수는 없다.
      • 해결책
        (1) 한번에 하나의 CPU만 커널에 들어갈 수 있게 함 -> 좀 더 구현이 쉽지만 비효율적임
        (2) 커널 내부에 있는 공유 데이터에 접근할 때마다 데이터 별로 lock/unlock을 하는 방식

프로세스 동기화 문제

  • 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다.
    - ex. 프로세스 1 실행 중에 공유데이터의 x 변수를 CPU 레지스터에 LOAD한 동안, time interrupt가 발생해서 context switch가 발생하고, 프로세스 2가 x 변수를 CPU 레지스터에 LOAD, x--, 공유 메모리 공간에 저장 후, 다시 프로세스 1로 context switch가 발생해서 프로세스 1이 CPU를 잡고 x++, store하면 프로세스 1의 연산 결과만 반영되서 최종적으로 1만큼 증가.
  • 일관성 문제를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요하다.
  • 프로세스 동기화는 concurrency control(병행 제어)라고도 부른다.

race condition

  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다.

-> race condition을 막기 위해서는 동시에 실행되는 프로세스(concurrent process)는 동기화되어야 한다.

임계구역 문제 (critical section problem)

  • n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
  • 각 프로세스의 code segment에는 공유 데이터를 접근하는 '코드'인 critical section이 존재 (공유 메모리를 의미하는 게 아님 주의!)
  • 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

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

  • 상호 배제 (mutual exclusion)
    프로세스 Pi가 임계구역 부분을 수행 중이면 다른 모든 프로세스들은 그들의 임계구역에 들어가면 안된다.
  • 진행의 융통성 (progress)
    아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
  • 한정 대기 (bounded waiting)
    프로세스가 임계구역에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 임계구역에 들어가는 횟수에 한계가 있어야 한다.

임계구역 문제를 해결하기 위한 초기 시도

  • 프로세스들의 일반적인 코드 구조
do {
	// entry section (lock)
    // critical section
    // exit section (unlock)
    // remainder section
} while (1);
  • 소프트웨어적으로 lock을 거는 코드를 추가하여 임계구역 문제를 해결하는 알고리즘들을 살펴보자.

Algorithm 1

// synchronization variable
int turn
turn = 0; // Pi는 turn == i일 때 임계구역 진입 가능

// 프로세스 0 입장에서
do {
	while (turn != 0); /* My turn?이 아니면 대기 */
	// critical section
    turn = 1; /* 프로세스 1아 이제 니 차례다 */
	// remainder section
} while(1)
  • 진행의 융통성 조건을 충족하지 못함 (같은 프로세스가 연속으로 CS에 진입 불가능)

    • 프로세스 0이 turn=1로 바꿔놓고 임계구역을 빠져나왔는데, 프로세스 1이 turn=0으로 바꿔주기 전까지는 임계구역에 진입하지 못함.

    • 극단적으로, 프로세스 1이 처음에 한 번만 임계구역에 진입하고, 프로세스 0은 임계구역에 100번 진입해야 하는 경우, 프로세스 0은 한 번 진입 후 다시 임계구역에 진입하지 못할 수도 있음.

      ❓: 이렇게 극단적인 경우를 미루어볼 때 이 코드는 한정 대기 조건을 충족하지 못하는 경우 아닌가? 프로세스1이 turn=0로 안바꿔주면 프로세스 1이 한 번 진입 후 다시 임계구역에 진입하지 못하게 되니까?

Algorithm 2:

// synchronization variable
boolean flag[2];
flag[0], flag[1] = false, false; /* 아무도 임계구역에 없다. */
// Pi는 flag[i] = true일 때 임계구역 진입 가능

// 프로세스 0 입장에서
do {
	flag[i] = true; /* CS에 진입하겠다는 의사 표시 */
    // 이 때 CPU timeout이 된다면? 한정 대기 조건 미충족
	while (flag[j]); /* 저 쪽이 이미 깃발을 들었으면 대기 */
	// critical section
    flag[i] = false;
	// remainder section
} while(1)
  • Algorithm 1의 문제 해결. 같은 프로세스가 연속으로 여러번 CS에 진입 가능.
  • 다만, 두 프로세스가 동시에 flag를 true로 바꾸면, 프로세스 i와 j 모두 CS에 진입하지 못함. 즉, 한정 대기 조건 미충족

Algorithm 3 (Peterson's Algorithm):

// synchronization variable
int turn
boolean flag[2];

turn = 0; // Pi는 turn == i일 때 임계구역 진입 가능
flag[0], flag[1] = false, false; /* 아무도 임계구역에 없다. */
// Pi는 flag[i] = true일 때 임계구역 진입 가능

// 프로세스 0 입장에서
do {
	flag[i] = true; /* CS에 진입하겠다는 의사 표시 */
    turn = j /* 재빨리 j 차례로 바꿔줌 */
	while (flag[j] && turn == j); /* 두 프로세스가 동시에 flag를 true로 바꾸더라도, 한쪽이 turn을 상대방쪽으로 바꿔주면 상대가 CS 진입 가능 */
	// critical section
    flag[i] = false;
	// remainder section
} while(1)
  • 2개 프로세스의 임계구역 문제 해결에 있어 3가지 조건 모두 충족
  • 하지만 여전히 while문에서 busy waiting(=spin lock)을 한다는 문제가 있다. 즉, 상대가 계속 while문을 돌면서 기다리게 만든다. (계속 CPU와 memory를 사용하면서 wait)
    - 예를 들어, 프로세스 i가 critical section에 진입했을 때 프로세스 j에 CPU를 preempt 당하면, flag[i] = true이고 j 본인이 turn = i로 바꿔놓았으므로 while문에서 다른 작업을 못하고 busy waiting 해야 함. 이는 CPU 할당 시간이라는 자원의 낭비이다.

lock을 걸고 lock을 푸는 코드가 왜 이리 복잡할까?

애초에 CPU instruction 각각 실행되는 도중에 CPU를 빼앗길 수 있기 때문이다.
-> 하드웨어적으로 instruction들을 하나로 묶어 atomic하게 처리하자!

하드웨어적 동기화

  • 하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결
// synchronization variable:
boolean lock = false;

do {
	while (Test_and_Set(lock)); /* lock을 atmoic하게 true로 바꿈 */
    // critical section
    lock = false;
	// remainder section
}
  • lock이라는 변수를 읽고 쓰는 연산을 하나로 묶어 atomic하게 처리하겠다! -> 코드를 복잡하게 짜지 않아도 도중에 CPU preemtion 당할일이 없음.

mutex와 semaphore의 비교

  • mutex locks: 프로세스가 임계구역에 진입하기 전에 atomic하게 lock을 획득해야하고(acquire()), 임계구역에서 나올 때 lock을 atomic하게 방출해야 한다.(release()). busy waiting(spin lock) 문제가 여전히 발생한다.
acuire() {
	while (!available) /* busy wait */
    avilable = false;
}

release() {
	available = true;
}

  • Semaphores: 프로세스가 임계구역에 진입하기 전에 S를 atomic하게 감소시켜야 하고(P(S)), 임계구역에서 나올 때 S를 atomic하게 증가시켜야 한다.(V(S)), busy waiting(=spin lock)은 효율적이지 못하므로 block & wakeup의 방식으로 구현 가능하다. (=sleep lock)

  • 카운팅 세마포어(counting semaphore)와 이진 세마포어(binary semaphore)로 구분된다.

    • counting semaphore: 도메인이 0 이상인 임의의 정수값. 주로 resource counting의 사용.
    • binary semaphore: 0 또는 1만 가질 수 있는 semaphore.
      -> 이진 세마포어(S=1)는 lock을 걸고 푸는 뮤텍스를 대체할 수 있다고 생각해도 무방하다.
wait(S) {
	while (S <= 0); /* busy wait */
    S--;
}

signal(S) {
	S++;
}

세마포어(semaphores)

  • 세마포어는 추상자료형의 일종이다.

    추상 자료형(ADT)
    구현과 분리하여 자료형을 추상적으로 정의한 것. 구현 방법을 명시하지 않는다는 점에서 자료구조와 다르다.

  • S라는 integer variable이 있고, 이 변수에 대해 정의되는 연산 P, V가 있다. P, V도 atomic하게 연산이 수행됨을 가정하고 있음.

P(S): 공유자원 S의 획득:

while (S <= 0) no-op; // 양수가 될 때까지 대기 (busy waiting 문제 여전히 발생)
S--; // S가 양수이면 S-- 하고 진입

V(S): 공유자원 S의 반납

S++;

이 있다.

block & wakeup 방식

resource queue에서 sleep하며 CPU를 얻을 권한을 block하다가, 공유데이터가 반납되면 깨움

  • Semaphore를 다음과 같이 정의
typedef struct
{
	int value; /* semaphore */
    struct process L; /* process wait queue */
} semaphore
  • block과 wakeup을 다음과 같이 가정
    • block: 커널은 block을 호출한 프로세스를 suspend 시킴. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음.
    • wake up(P): block된 프로세스 P를 wakeup 시킴. 이 프로세스의 PCB를 ready queue로 옮김

P()와 V()의 구현
P(S):

S.value--;
if (S.value < 0) {
	// add this process to S.L
    // block();
}

V(S):

S.value++;
if (S.value <= 0) { // 양수였다면 sleep중인 프로세스를 깨울 일도 없으므로 if문에 진입하지 않음
	// remove a process P from S.L
    // wake up(P);
}

busy wait vs block/wakeup, 뭐가 더 낫나?

일반적으로는 CPU 사용률만 놓고 봤을 때 block/wakeup이 더 효과적임.
다만 block/wakeup의 경우, 프로세스의 상태를 바꾸는 데에 overhead가 존재하긴 한다. (자원이 부족하면 프로세스의 상태를 잠자는 상태로 바꿔야 함. 자원이 반납되면 프로세스의 상태를 ready 상태로 바꿔야 함)

  • critical section의 길이가 긴 경우, block/wakeup이 적당. (오래 while문 돌 바에, 잠을 자라)
  • critical section의 길이가 매우 짧은 경우, block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있다. (잠깐 잘바에 그냥 기다려라)

Deadlock, Starvation

Deadlock

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

  • S와 Q가 각각 1로 초기화된 semaphore라 하자. P0과 P1은 모두 S와 Q를 둘 다 획득해야 각자의 일을 할 수 있는 상황. (ex. 하드디스크 A에 있는 데이터를 하드디스크 B로 copy하려면 하드디스크 A와 하드디스크 B라는 자원을 둘다 획득해야 함.)
    • P0가 S를, P1이 Q를 하나씩 차지
    • P0는 Q를 요구, P1은 S를 (서로 상대방이 쥐고 있는 자원을) 요구
    • 서로 가진 자원을 쥐고 놓지 않아 무한히 기다려야 함 (deadlock)
  • P0와 P1이 둘 다 Q를 얻기 전에 P부터 획득하도록 순서를 정해놓으면 해결된다.

Starvation

이미 자원을 획득한 프로세스들이 잠자고 있는 프로세스가 필요한 자원을 release하지 않아, 잠자는 프로세스가 wakeup하지 못하는 현상.

식사하는 철학자 문제

  • deadlock
// synchronization variable
semaphore chopsticks[5];
// 모든 젓가락이 1로 초기화되어 있음.

// Philosopher i
do {
	P(chopsticks[i]); /* 왼쪽 젓가락 집기 */ 
    // 모든 철학자가 동시에 실행하면 다음 코드 실행 불가 (deadlock)
    // P(chopsticks[(i + 1) % 5]); /* 오른쪽 젓가락 집기 */
    ...
} while (1);
  • starvation
    철학자 A가 젓가락을 집으려고 하는데, 왼쪽 철학자와 오른쪽 철학자가 계속 번갈아서 양쪽 젓가락을 들고 밥을 먹으면 철학자 A는 굶어죽을 수도 있음.

동기화와 관련된 고전적 문제들

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

Bounded-Buffer Problem (생산자-소비자 문제)


이미지 출처: https://pages.mtu.edu/~shene/NSF-3/e-Book/SEMA/TM-example-buffer.html

버퍼: 임시로 데이터를 저장하는 공간

  • 생산자 프로세스, 소비자 프로세스 2종류가 있고, 생산자와 소비자는 한명만 있는게 아니라 여러명이 있음.
  • 생산자는 공유 버퍼에 데이터를 입력하는 역할, 소비자는 데이터를 꺼내는 역할
  • 동기화 문제:
    • 2명의 생산자가 동시에 비어있는 한 버퍼에 동시에 데이터를 입력하면 -> lock을 걸어서 다른 생산자의 접근을 막음. 입력 후 unlock.
    • 2명의 소비자가 동시에 한 버퍼에서 동시에 데이터를 꺼내면 -> lock을 걸어서 다른 소비자의 접근을 막음. 입력 후 unlock.
  • circular buffer 가정 (크기가 유한함)
  • 세마포어로 해야할 작업은 크게 2가지임
    • 2개 이상의 프로세스가 공유 버퍼에 동시에 접근할 수 없도록, 공유 버퍼 전체에 lock을 걸기 -> need binary semaphore (공유 데이터의 상호 배제를 위해)
      • 생산자
        (1) Empty 버퍼가 있나요? (없으면 기다림)
        (2) 공유 데이터에 lock을 건다.
        (3) Empty 버퍼에 데이터 입력 및 버퍼 조작 (비어있는 버퍼의 포인터를 옆의 위치로 옮김)
        (4) lock을 푼다.
        (5) full 버퍼 하나 증가
      • 소비자
        (1) full 버퍼가 있나요? (없으면 기다림)
        (2) 공유 데이터에 lock을 건다.
        (3) full 버퍼에서 데이터 꺼내고 버퍼 조작 (full 버퍼의 포인터를 옆의 위치로 옮김)
        (4) lock을 푼다.
        (5) empty 버퍼 하나 증가
    • 가용자원의 개수를 세기 -> need integer semaphore (남은 full/empty buffer의 수 세기)
      • 생산자에게 자원은 비어있는 버퍼의 개수
      • 이미 다 찬 버퍼라면 생산자에게 더 이상 자원이 없다고 볼 수 있음. 소비자가 자원을 꺼내가야 또 생산할 수 있음.
    • 소비자에게 자원은 내용이 들어있는 버퍼의 개수
      • 이미 모두 비어있는 버퍼라면 소비자에게 가용자원이 없으므로, 생산자 프로세스가 내용을 만들어서 입력해야만 또 소비자할 수 있음.

pseudo code (생산자 코드와 소비자 코드가 대칭임)

// synchronization variable
semaphore full = 0, empty = n, mutex = 1;

// producer
do {
	...
	produce an item in x
    ...
    P(empty)
    P(mutex)
    ...
    add x to buffer
    ...
    V(mutex)
    V(full)
} while (1);
    
// consumer
do {
	P(full)
    P(mutex);
    ...
    remove an item from buffer to y
    ...
    V(mutex)
    V(empty)
    ...
    consume the item in y
    ...
} while(1);

Readers-Writers Problem


이미지 출처: https://www.zephyrproject.org/common-multithreading-problems-and-their-fixes-part-3/

  • Reader와 Writer라는 2종류의 프로세스가 있고, Reader와 Writer는 각각 1개가 아니라 여러 개가 있음.
  • Write는 동시에 여럿이서 하면 안되지만, Read는 동시에 여럿이서 해도 문제 없음. 한 프로세스가 종류가 무엇이든 db에 접근할 때마다 lock을 걸어도 되겠지만, 여러명의 Reader만 접근하는 경우 무조건 lock을 걸면 비효율적임.
    • 누군가 Write하는 동안에는 lock을 건다.
    • 누군가가 Read하고 있을 때 Reader가 도착하면 같이 Read한다.
    • 누군가가 Read하고 있을 때 Writer가 도착하면 기다려야 한다.

pseudo code

//shared data
int readcount = 0;
DB 자체;
// synchronization variables (mutex는 공유 변수 readcount를 접근하는 코드(임계 구역)의 상호 배제 보장을 위해 사용 - readcount에 lock을 거는 용도의 이진 세마포어,
// db는 Reader와 Writer가 공유 DB 자체를 올바르게 접근하게 하는 역할 - DB 자체에 lock을 거는 용도의 이진 세마포어)
semaphore mutex = 1, db = 1;

// writer
P(db);
	...
writing
	...
V(db);

// Reader
P(mutex);
readcount++;
if (readcount == 1) P(db); /* block writer */
V(mutex); /* readers follow */

	...
reading DB is performed
	...
P(mutex);
readcount--;
if (readcount == 0) V(db); /* enable writer */
V(mutex);
  • Reader가 계속 도착하면 Writer가 write할 수 없음 (starvation 발생 가능)
    • 신호등처럼 코드를 구현하면 starvation 해결 가능 (어느 정도의 Reader가 접근하고 나면 Writer에게 기회를 주는 방식)

Dining-Philosophers Problem


이미지 참조: https://www.geeksforgeeks.org/dining-philosopher-problem-using-semaphores/

배가 고파지면 왼쪽과 오른쪽 젓가락을 집어서 밥을 먹고, 배가 부르면 젓가락을 내려놓고 생각하는 것을 무한 반복.
젓가락은 공유자원이고 1로 초기화되어있기 때문에, 만약 잡을 수 없다면 기다려야 함.

// synchronization variable
semaphore chopsticks[5];
// 모든 젓가락이 1로 초기화되어 있음.

// Philosopher i
do {
	P(chopsticks[i]); /* 왼쪽 젓가락 집기 */ 
    P(chopsticks[(i + 1) % 5]); /* 오른쪽 젓가락 집기 */
    ...
    eat();
    ...
	V(chopsticks[i]); /* 왼쪽 젓가락 내려놓기 */ 
    V(chopsticks[(i + 1) % 5]); /* 오른쪽 젓가락 내려놓기 
    ...
    think();
    ...
} while (1);

앞의 solution의 문제점

  • Deadlock
    • 모든 철학자가 왼쪽 젓가락을 집으면 오른쪽 젓가락은 아무도 잡을 수 없음.
  • 해결 방안
    • 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다. (최소 1명은 먹을 수 있음)
    • 젓가락을 2개 모두 잡을 수 있을 때에만 젓가락을 집을 수 있게 한다.
    • 비대칭
      • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록. 즉, 두명의 철학자 사이에 놓인 젓가락을 먼저 집은 철학자가 다른 편 젓가락도 집을 수 있도록 함.

해결 코드

enum { thinking, hungry, eating } state[5];
semaphore self[5] = 0; /* 젓가락을 잡을 수 있는지 여부를 나타내는 이진 semaphore */
semaphore mutex = 1; /* state에 lock 거는 용도의 semaphore */

// philosopher i
do { 
	pickup(i);
	eat();
    putdown(i);
    think();
} while(1)

void pickup(int i) {
	P(mutex);
    state[i] = hungry;
    test(i); /* 양쪽 젓가락을 집을 수 있는지 체크 */
    V(mutex);
    P(self[i]); /* 양쪽 젓가락을 집을 수 없으면 wait, 집을 수 있으면 self[i]를 다시 0으로 만들고 eat()하러 감 */
    
void test(int i) {
	if (state[(i + 4) % 5] != eating && state[i] = hungry && state[(i + 1) % 5] != eating) {
    	state[i] = eating;
        V(self[i]); /* 젓가락을 집을 수 있는 상태로 바꿔줌 (자원을 1만큼 늘림) */
    }
}

void putdown(int i) {
	P(mutex);
    state[i] = thinking;
    test((i + 4) % 5) /* 왼쪽 철학자가 젓가락을 집을 수 있도록 알림을 해주는 역할 */
    test((i + 1) % 5) /* 오른쪽 철학자가 젓가락을 집을 수 있도록 알림을 해주는 역할 */
    V(mutex)

모니터(Monitor)

Semaphore의 문제점

  • 코딩하기 힘들다.
  • 정확성 입증이 어렵다.
  • 자발적 협력이 필요하다.
  • 한번의 실수가 모든 시스템에 치명적인 영향을 미친다.
    • 예
      V(mutex)
Critical Section
P(mutex)
// mutual exclusion 깨짐 (lock이 제대로 안 걸림)
      P(mutex)
Critical Section
P(mutex)
// Deadlock 발생 (lock이 반환이 안됨)

모니터

프로그래밍 언어 차원에서 동기화 문제를 해결.
동시 수행 중인 프로세스 사이에서 ADT의 안전한 공유를 보장하기 위한 high level synchronization constructor임.

monitor 내부의 procedure를 통해서만 공유 데이터에 접근할 수 있음

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

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

    • 만약 프로세스 A가 procedure를 실행하다가 CPU timeout이 되더라도, 모니터 입장에서는 active한 프로세스이므로 entry queue에서 기다리고 있는 프로세스에게 procedure를 실행하지 못하게 함. active 한 프로세스의 수가 0일 때만 다음 프로세스가 monitor에 진입 가능.

  • 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없음
    (원천적으로 procedure는 여러개가 동시에 실행될 수 없음
    -> semaphore와 달리 개발자가 동시 접근을 막기 위해 lock을 걸 필요가 없음. 모니터가 알아서 하나의 프로세스만 공유데이터에 접근하게끔 해줌.)

  • 단, 세마포어에서처럼 모니터에서도 자원의 개수가 0 이상일 때에만 임계구역에 접근하고 그렇지 않을 때에는 suspend하게끔 하는 코드가 필요.

    • 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용 (x라는 자원이 여분이 있으면 바로 접근하게 해주고, 여분이 없으면 줄서서 wait하도록 함)

      condition x, y;

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

      x.wait()
      x.wait()을 호출한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지는 suspend된다.
      x.signal
      x.signal은 정확하게 하나의 suspend된 프로세스를 resume한다. suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

생산자 소비자 문제도 monitor를 이용하여 lock 없는 코드로 개선 가능.

pseudo code

// monitor bounded_bufffer
{	int buffer[N];
	condition full, empty; /* condition variable은 값을 가지지 않고 자신의 큐에 프로세스를 매달아서 sleep 시키거나 큐에서 프로세스를 깨우는 역할만 함. */
    
    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 not full buffer
    	// 내용이 들어있는 버퍼를 기다리게 함
    	full.wait();
      remove an item from buffer and store it to *x
      // 내용이 비기를 기다리느라 잠들었던 생산자를 깨움
      empty.signal();
    }
}
  • monitor 내에서는 하나의 프로세스만 활성화되기 때문에, 나머지 프로세스는 entry queue에서 줄 서서 기다려야 한다.
  • monitor 내에서 공유자원의 개수가 부족하다면 condition variable에 줄서서 기다려야 한다.

식사하는 철학자 문제도 monitor를 이용하여 lock 없는 코드로 개선 가능

Each Philosopher:
{ 
	pickup(i);
    eat();
    putdown(i);
    think();
} while(1);
	
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(); /* test 내부에서 if문에 진입 못했으면 못 먹으니까 기다려야 함. */
    }
    
    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(); /* 못 먹고 기다리고 있는 상태였으면 깨움 */
		}
	}
    
    void init() {
    	for (int i = 0; i < 5;i++) state[i] = thinking;
    }
}
profile
이민선(Jasmine)
기록에 진심인 개발자 🌿
이전 포스트

[운영체제] 프로세스 관리

다음 포스트

[운영체제] 교착상태

0개의 댓글