= lock/unlock 기능, 공유 자원을 획득하게 해준다.
앞선, 일반 방식들을 추상화시킨 것
Semaphore S == 자원의 갯수
[P(S)] // S변수(=공유변수)를 획득하는 경우의 연산
----------------------------------------------
while(S <= 0) do no-op; // 자원이 없다면 wait..
S--; // 음수일 경우, Busy-wait 발생
[V(S)] // S변수(=공유변수)를 다 사용하고 반납하는 경우의 연산
-------------------------------------------------------
S--;
Critical Section of n Process
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);
이 방식의 문제점
Semaphore를 다음과 같이 정의함
typedef struct
{
int value; // semaphore
struct process *L; // process wait queue
} Semaphores
Block과 Wake-Up을 다음과 같이 가정
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);
}
무엇이 더 좋은가요 ?
그래서
Block/wakeup overhead v.s. Critical section 길이
Two types of Semaphores
도메인이 0 이상인 임의의 정수값
주로 resource counting에 사용
0 또는 1 값만 가질 수 있는 semaphore
주로 mutual exclusion (lock/unlock)에 사용
1. DeadLock(교착상태)
= 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
EX) S와 Q가 1로 초기화된 semaphore라 하자.
P0과 P1는 S와 Q를 동시에 가질 수 없음
2. Starvation(기아현상, Indefinite Blocking)
= 프로세스가 suspend된 이유에 해당하는 semaphore 큐에서 빠져나갈 수 없는 현상
= 동시 수행 중인 프로세스 사이에서 abstract data type의 안전 공유를 보장하기 위한 high-level synchronization construct (semaphore에 비해 프로그래머의 부담을 줄여주고, monitor가 알아서 해줌)
monitor monitor-name
{ shared variable declarations
procedure body P1(...){
...
}
procedure body P2(...){
...
}
{
initialization code
}
}
monitor라고 정의된 내부의 프로시저를 통해서만 공유 데이터에 접근 가능
condition variable은 wait 와 signal 연산에 의해서만 접근 가능.
x.wait()
x.signal()
(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;
}
}
자료 출처