TIL 정리_86

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323

운영체제 강의를 듣고 정리한 내용입니다

 

 

추상 자료형 : Object와 Operation으로 이루어져있다.

논리적으로 정의를 하는 것을 말한다.

 

Semaphore S

이전의 방식들을 추상화시킨 방법으로 정수값을 가질 수 있는 추상자료형이다

lock을 걸고 푸는 것을 간단하게 사용가능하게 만든다

공유 자원을 획득하고 반납하는 것을 처리해준다

 

P연산과 V연산에 의해서만 접근 가능하다

P(S) : //lock을 거는 과정

while(S<=0) do no-op;

s--;

-> 자원을 획득한다

V(S) : //lock을 푸는 과정

while(S<=0) do no-op;

s++;

-> 자원을 반납한다

 

코드로 구현 

Synchronization variable
-> semaphore mutex;
Process Pi
do {
P(mutex);
critical section
V(mutex);
remainder section
} while(1)
-> busy-wait는 효율적이지 못하다 (spin lock)
->> Block & Wakeup 방식의 구현이 필요하다 (sleep lock)

 

Block/Wakeup

Semaphore를 다음과 같이 정의한다

typedef struct {

int value;

struct proccess*L;

} semaphore;

 

block와 wakeup을 다음과 같이 가정한다

block

커널은 block을 호출한 프로세스를 suspend 시킨다

-> 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다

 

wakeup(P)

block된 프로세스 P를 wakeup 시킨다

-> 프로세스의 PCB를 ready queue로 옮긴다

 

구체적인 Semaphore 연산의 구현

 

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

V(S) :
S.value++;
if(S.value <= 0) {
remove a process P from S.L;
wakeup(P);
}

 

 

Busy wait vs Block/wakeup

• Critical section의 길이가 긴 경우 Block/Wakeup이 적당하다
• Critical section의 길이가 매우 짧은 경우 Block/wakeup의 오버헤드가 busy-wait 오버헤드보다 커질 수 있다

-> busy-wait를 써도 무방하다

• 일반적으로는 Block/wakeup 방식이 더 좋다

 

2가지 타입의 Semaphore

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

주로 resource counting에 사용된다

 

Binary semaphore (== mutex)

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

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

 

 

• Semaphore를 사용할 때 주의할 점

Deadlock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를

무한히 기다리는 현상을 말한다

-> 프로세스 P0과 P1이 얻어야 하는 event 순서를 동일하게 구성하여 해결한다

 

Starvation

indefinite blocking

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

-> 특정 프로세스들만 자원을 공유하여 다른 프로세스가 자원을 얻지 못하는 것을 말한다