•
참고 강의
contents
Classical Problems of Synchronization
Bounded-Buffer Problem(Produer-Consumer Prolem)
Producer - 데이터를 하나 만들어서 넣는 역할
Consumer - 데이터를 꺼내가는 역할
Producer, Consumer는 여러개가 있을 수 있다.
공유 데이터 : buffer 자체, buffer 조작 변수(empty/full pointer 변수)
문제가 생기는 상황
1.
lock를 걸고 푸는 문제(동시 접근)
•
생산자 두 명이 동시에 데이터를 넣는 상황
◦
공유 버퍼에 lock를 걸어서 다른 프로세스들의 접근을 막은 후에 데이터를 집어 넣기
◦
데이터 넣는 작업이 끝나면 lock를 풀고 다른 프로세스들이 공유 버퍼를 사용할 수 있게 해준다.
•
소비자 두 명이 동시에 데이터를 꺼내는 상황
◦
공유 버퍼에 lock를 걸어서 다른 프로세스들의 접근을 막은 후에 데이터를 꺼내가기
◦
데이터를 꺼내가는 작업이 끝나면 lock를 풀고 다른 프로세스들이 공유 버퍼를 사용할 수 있게 해준다.
공유 자원에 대한 Synchronize 문제→ 다음 위치로 변경해주는 작업이 필요
binary semaphore (mutual exclusion)2.
데이터를 채우고 빼가는 문제
•
만약, Buffer가 다 차고(Bounded-Buffer이기 때문) 생산자가 도착한 상황
(= 사용할 수 있는 자원이 없는 상태, 빈 버퍼)
◦
새로운 생산자가 데이터를 집어넣을려면 소비자가 데이터를 꺼내가야 한다.(자원의 여분)
•
만약, Buffer가 다 비었는데 소비자가 도착한 상황
(= 사용할 수 있는 자원이 없는 상태, 사용할 수 있는 버퍼)
◦
새로운 소비자가 데이터를 꺼내가려면 생산자가 데이터를 집어넣어줘야 한다.
integer semaphore(resource count)생산자가 해야하는 일
1.
빈 버퍼가 있는 지 확인(없으면 기다림 = 소비자가 꺼내어 갈 때까지)
2.
공유 버퍼 전체에 lock를 검
3.
빈 버퍼에 데이터를 입력 및 버퍼 조작
4.
lock를 품
5.
full buffer(사용할 수 있는 자원이 있는 상태) 하나 증가
소비자가 해야하는 일
1.
데이터가 있는 버퍼가 있는 지 확인(없으면 기다림 = 생산자가 데이터를 넣을 때까지)
2.
공유 버퍼 전체에 lock를 검
3.
빈 버퍼에 데이터를 입력 및 버퍼 조작
4.
lock를 품
5.
empty buffer(빈 상태) 하나 증가
Semaphore 문제 Sudo 코드
•
mutex : lock를 걸 수 있는 변수
•
full : 내용이 들어있는 버퍼의 갯수
•
empty : 비어있는 버퍼의 갯수
Producer
1. x에 있는 item를 만드는 코드 |
2. 빈 버퍼가 있는 지 확인하기 P(empty) → 빈 버퍼가 없다면 기다림 |
3. 버퍼에다가 데이터를 집어넣기 위해서 버퍼에 lock를 검 |
4. 버퍼에다가 데이터를 집어넣음 |
5. 버퍼에 걸었던 lock를 품 |
6. 내용이 들어있는 버퍼를 1 증가시킴 |
Consumer
1. 꽉 찬 버퍼가 있는 지 확인하기 P(full) → 꽉 찬 버퍼가 없다면 기다림 |
2. 버퍼에서 데이터를 빼가기 위해서 버퍼에 lock를 검 |
3. 버퍼에 있는 데이터를 빼 감 |
4. 버퍼에 걸었던 lock를 품 |
5. 비어있는 버퍼를 1 증가시킴 |
6. y에 있는 item를 사용하는 코드 |
Readers-Writers Problem
DB 에 Read Process, Write Process 를 실행하고 Reader, Writer 는 여럿일 수 있음
공유 데이터 : DB
문제가 생기는 상황
1.
공유 데이터를 동시에 접근
•
lock를 사용해서 이를 해결
•
write는 여럿이 동시에 하면 Synchronize 문제를 발생시킬 수 있지만 read는 문제가 발생하지 않음
◦
read하는 동안에는 굳이 lock를 걸 필요가 없기 때문에 write동안에만 lock를 걸도록 함
◦
read하는 동안 lock를 걸면 비효율적
◦
write는 독점적으로 write해야 함
•
mutex : readCount 공유 변수를 위한 lock를 걸 수 있는 변수
•
db : DB에 대한 lock 변수
•
readCount : 현재 Reader가 얼마인지
Writer
1. db를 사용해서 lock를 검(db를 누가 쓰고 있다면 기다림) |
2. DB에다가 쓰는 작업 진행 |
3. lock를 풀어줌 |
Reader
1. readCount에 대한 lock를 검 |
2. readCount를 1 증가 시킴 |
3. 최초의 Reader라면 db에다가 lock를 검 |
4. 이미 다른 Reader가 있다면 lock를 걸 필요가 없어서 lock거는 프로세스 스킵 |
5. DB를 읽는 작업 진행 |
6. readCount를 1 감소 시킴 |
7. 마지막 Reader라면 db에 건 lock를 풀어줌 |
읽기 위해서 lock를 건 상태에서 읽을려면 프로세스와 쓸려는 프로세스가 모두 도착
•
Writer : Reader가 이미 읽고 있기 때문에 기다려야 함
(마지막 Reader가 lock를 풀어줄 때까지 기다려야 함 → Starvation 발생)
•
Reader : 같이 읽을 수 있기 때문에 DB에 접근 가능
순서를 두면 Reader들이 같이 돌 수 있는데 그러질 못함 지나치게 늦은 Reader는 잠깐 기다리라고 해놓고 먼저 빠져나가서 Writer로 접근(개선)Dining-Philosophers Problem
5명의 철학자가 배고파졌을 때 밥을 먹을 수 있는지에 대한 문제
밥을 먹기 위해선 젓가락 두 개를 다 잡아야 한다.
•
젓가락은 공유 자원이며 동시에 둘이 잡을 수 없다.
1. 왼쪽 젓가락을 잡음 |
2. 오른쪽 젓가락을 잡음(다른 철학자가 잡으면 잡을 수 없음 - 공유 자원) |
3. 밥을 먹음 |
4. 왼쪽 젓가락을 놓음 |
5. 오른쪽 젓가락을 놓음 |
Solution의 문제
•
Deadlock의 가능성 존재 → 진행이 안되고 막혀 있는 상황
•
모두 다 왼쪽 젓가락을 잡은 상황
해결 방안
•
4명의 철학자만 테이블에 동시에 앉을 수 있도록 함
•
젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 함
•
비대칭 → 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락을 집게 함
•
self[5] : 각각의 5명 철학자가 젓가락을 잡을 수 있어서(권한 존재) 젓가락 잡는 권한을 줄 것인가 말 것인가.
•
enum {thinking, hungry, eating} state[5] : 5명의 상태 공유 변수
•
mutex : 다른 철학자도 상태를 바꿀 수 있기 때문에 lock 변수
Monitor
•
semaphor의 문제점
◦
코딩하기 힘들다
◦
정확성의 입증이 어렵다
◦
자발적 협력이 필요하다
◦
한번의 실수가 모든 시스템에 치명적인 영향을 준다.
◦
버그 발생시킬 확률이 높다
동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
•
동시성 문제를 해결하는 Monitor
•
모니터 내에 한 번에 하나의 process만이 활동 가능
•
프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음
•
공유 데이터에 접근하기 위해서 모니터라고 정의된 내부의 procedure를 통해서만 접근하도록 만들어둔 것
◦
lock를 걸 필요가 없어진다. 모니터는 기본적으로 모니터에 대한 동시접근을 허락하지 않기 때문에 프로그래머가 lock를 걸 필요가 없어짐.
→ 어차피 하나의 procedure만 접근 가능
•
프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해서 condition variable 사용
◦
wait, signal 연산에 의해서만 접근 가능
하나의 process안에서 돌아가기 때문에 다른 생산자, 소비자가 접근해서 생기는 문제들이 일어나지 않는다.
•
lock를 걸지 않아도 된다.
•
이해도 쉬움
monitor 안에서는 하나의 process만 활성화되기 때문에 나머지 프로세스는 줄서서 기다려야 함.
monitor 내부에서도 공유 데이터(버퍼)를 사용하기 위해서 줄서서 기다려야 한다.