[운영체제(2)]Process Synchronization 3

목표

• Classical Problems of Syncronization
• Bounded-Buffer Problem
• Readers-Writers Problem
• Dining-Philosophers Problem
• Monitor

Classical Problems of Syncronization

01. Bounded-Buffer Problem

Buffer: 데이터를 임시로 저장하는 공간.
Bounded-Buffer: 버퍼의 크기가 유한함.

Producer-Consumer 문제

process 두가지 종류

이 문제에는 process가 두가지 종류가 있음.

• Producer 프로세스
  • 여러개 있음
  • 역할: 버퍼에다가 공유 데이터를 만들어서 집어 넣음
  • 주황색 : producer가 데이터를 만들어서 집어넣은 상태
• Consumer 프로세스
  • 여러개 있음
  • 역할: 버퍼에 있는 데이터 빼가서 사용
  • 비어있음: 애초에 비어있든지, cousumer가 데이터를 꺼낸 상태

Synchronization 문제 3가지

이 곳에서 Synchronization 관련한 어떤 문제가 발생할 수 있을까?

1. 공유 버퍼이기 때문에 producer가 동시에 도착해서 비어있는 하나의 버퍼에 동시에 데이터를 만들어 집어넣는 문제
   => producer가 비어있는 buffer를 확인하고, 데이터를 집어넣는걸 그냥 하지않고,
   buffer에다가 lock을 걸어서 다른 process들의 접근을 막은 다음에
   buffer에다가 데이터를 넣고
   그 작업이 끝나면
   lock 풀고 다른 producer나 consumer가 버퍼에 접근하게 한다.

• idx를 비어있는 버퍼로 위치

2. consumer가 동시에 같은 데이터를 꺼내가려고 할 때
   => buffer에다가 lock을 걸어서
   데이터를 꺼내가고,
   lock을 풀고

• idx를 채워있는 데이터로 위치

3. buffer가 유한하기 때문에 생기는 문제
   buffer에 data가 다 찼을 때, consumer는 안오고 producer가 또 올 때
   => producer 입장에선 더이상 생산할 수 있는 자원이 없는 상태임/

• producer 입장에선 비어있는 자원의 개수가 counting 해야하는 자원이다.
• consumer 입장에서 자원은 내용이 들어있는 buffer다.

semaphore가 역할 2가지

1. 공유 버퍼에 접근하는 것을 막기 위해서 버퍼 전체에다가 lock을 걸어서 나 혼자 접근 가능하게 lock을 걸고, 접근이 끝났으면 lock을 풀어줘야 한다.
2. 버퍼가 가득 차거나 비었을 때 가용자원의 개수를 세는 counting semaphore 용도

semaphore 변수

semaphore 변수 3가지

1. full : 내용이 들어있는 개수를 세기위한 변수

• 처음에 full은 0개야. 채워져있는게 없다는 뜻임.

2. empty : 비어있는 buffer를 세기위한 변수

• 처음에 empty는 n개야. 모두다 비어있다는 뜻임.

3. mutex : lock을 걸고 풀기 위한 변수

생산자 process들은 어떤 절차를 거치는지

item x를 만든 다음 이걸 공유 버퍼에 넣고 싶은데, 그 전에 ~~

빈 버퍼가 있는지 확인부터 한다.

버퍼에다가 데이터를 집어넣기 위해서 lock을 건다.

버퍼에다가 데이터를 집어넣는다.

버퍼에 걸었던 lock을 푼다.

내용 들어있는 버퍼 개수 1증가 시키는게 full에 대한 V연산

소비자는 반대로 ~! ...아래 사진 참고 !

02. Readers-Writers Problem

Readers-Writer 문제는 process가 2문제가 있음.

• 읽는 process
• 쓰는 process
  여기서는 공유 data를 DB로 명명. (읽고 쓰는 문제는 보통 DB에서 일어나기 때문)

그런데 DB에서는,

• 쓰는 작업은 여러 Process가 접근하면 안되지만,
• 읽는 작업은 여러 Process가 접근해도 괜찮다.

Writer

• DB는 공유데이터를 뜻함. : 데이터에 접근하려면 lock을 걸어야함.
• db: DB에 대한 lock에해당하는 semaphore 변수 : 공유 데이터 DB에 접근하기 위해 P연산 lock을 건 것임.
  Reader
• 읽는 작업은 여러명이 해도 되는데 lock을 걸어버리면 비효율적
• readcount: reader 몇명이 읽고 있는지 세는 변수 , 이것도 공유변수라서 이에 대한 lock을 거는 mutex라는 semaphore 변수가 있는거야. (이 변수를 lock 걸지 않으면 여러 reader가 와서 혼잡해질 때 readcount를 제대로 세지 않는 경우가 생길 수 있음.) , 내가 만약 readcount를 최초로 올린 reader라면 DB에다가 lock을 거는 P(db)연산을 해야함.
• 빠져나갈 때, 내가 만약 마지막으로 읽었던 process라면 readcount가 0이 되고 DB에 걸었던 lock을 푸는 V(db) 연산을 한다.
  Starvation 문제
• Reader가 DB에서 읽고 있는데, 또 다른 Reader와 Writer가 왔다. 이미 Reader가 읽고 있다면 Reader가 들어오고, Writer는 기다려야 한다. 그런식이면 마지막Reader가 나가려고 하는데 또 Reader 1000개가 들어오면, Writer의 starvation 문제가 있음.
  => 어느정도 많이 기다리면 이제 Writer가 접근할 수 있게 한다.

03. Dining-Philosophers Problem

철학자들은 밥을 먹거나 생각하거나

밥 먹기 전에 왼쪽 젓가락, 오른쪽 젓가락 잡는 연산

밥 먹고 나면, 왼쪽 젓가락이랑, 오른쪽 젓가락을 놓는 연산

• 철학자들은 일단 왼쪽 젓가락 잡았으면 밥 먹을 때까지. 절대 놓지 않아요
  => 모두가 왼쪽 젓가락 잡고 안놔
  => Deadlock

해결 방안

• 4명만 동시에 앉아라.
• 젓가락 양쪽 잡을 수 있을 때만 권한을 준다.
• 각 철학자마다 우선순위의 젓가락을 잡아야만 다음 젓가락 잡을 수 있게 권한을 준다.

철학자는 젓가락을 잡고pickup, 먹고eat, 젓가락 내려놓고pickdown, 생각한다think

• semaphore self[i] = 1
  : 철학자 i번째 사람이 젓가락 잡을 권한 있다는 뜻 .
  ex) semaphore self[i] = 0;
  : 젓가락 잡을 권한 없다는 뜻.

• enum (thinking, hungry, eating) state[5]
  : 다섯명의 철학자 상태를 나타내는 공유 변수

  • 생각하는 상태
  • 배고픈 상태
  • 먹는 상태

• semaphore mutex = 1
  : i번째 철학자의 상태를 바꾸는 건 본인 뿐 아니라, 옆 철학자(i-1, i+1)도 가능함.

  • 따라서, state는 공유변수이고,
  • 공유변수에 대한 동시접근을 막기 위해서 mutex가 있음.
  • mutex는 lock을 나타냄

Monitor

예) 프로그래머의 한번의 실수가 모든 시스템에 치명적

• V연산과 P연산 순서를 바꿨을 때 => 둘이 동시에 들어가는 문제 발생.
  예2) P연산만 두번했을 때 => 영원히 어느 프로세스도 Critical section에 못들어감.

이런 문제 때문에 Monitor 제공

monitor는 프로그래밍 언어 차원에서 synchronization 문제 를 해결하는 high-level synchronization construct

객체지향 프로그래밍 언어들을 보면 객체를 중심으로 operation 들이 정의가 됨. 그런거에 기반해서 monitor는 이런식으로 공유 data에 접근하기 위해서는 이 monitor라고 정의된 내부의 procedure를 통해서만 가능하다.

예를들어, 이 공유데이터가 안에 있으면 밖에서 아무나 접근할 수 있는게 아니라 monitor 안에다가 shared data와 그것에 접근할 수 있는 procedure 즉, operations를 정의해놓는다.

monitor는 원천적으로 내부에 있는 procedure는 동시에 여러개 실행이 안되도록 통제를 한다. => 프로그래머 입장에선 lock을 걸 필요가 사라짐

semaphore처럼 lock을 걸 필요는 없어졌지만, 여전히 자원의 개수를 세는건 필요하다. 왜냐하면 자원이 없으면 프로세스를 기다리게 함. condition variable

• 자원의 개수를 세는 condition x;
• 자원이 없으면 기다리는 함수 x.wait()
• 접근 다하고 빠져나가면서 기다리는 프로세스 있으면 깨우는? 함수 x.signal()

생산자-소비자 문제의 semaphore 코드를 monitor 코드로 conversion

아까 여기선 lock을 걸고 푼다.

하지만, monitor는 lock을 걸고 풀 필요 없음.

공유 buffer가 monitor 안에 정의되어 있음.

생산하거나 소비하는 작업을 하기 위해서는 monitor 내부 코드를 실행해야함.

그러면 생산자든, 소비자들 하나의 코드만 monitor 안에서 활성화되기 때문에 굳이 lock을 걸지 않아도 또 다른 생산자나, 소비자가 접근해서 생기는 문제를 고려할 필요 없다.

만약에 비어있는 버퍼가 없다면, 버퍼 기다리는 줄에 줄서게 blocked 상태로 보냄

비어있는 버퍼가 있다면, 그냥 버퍼에다가 내용을 하나 넣어주면 됨.

그 작업이 끝났으면 버퍼 없어서 잠들어있던 프로세스를 깨워주는 코드

• 프로그래머한테 semaphore보다 monitor가 더 쉽다.