6-2. Process Synchronization 2

6-2 Process Synchronization 2

Semaphores, Critical Section of n Processes, Block / Wakeup Implementation, Implementation, Two Types of Semaphores, Deadlock and Starvation, Dining-Philosophers Problem

 

Semaphores

추상자료형 : Object와 Operation으로 구성됨

앞의 방식들을 추상화 시킴

공유자원을 획득하고 반납하는 것을 Semaphore가 처리해줌

Semaphore S : 정수값(integer variable)을 가질 수 있는데 그것이 자원의 개수라고 생각(즉 S가 5면, 자원이 5개있는것)

P연산은 값을 획득하는 과정이고, V연산은 반납하는 과정

P(S) : while (S≤0)do no-op; //lock을 거는과정

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

mutex : CS이 1개인것

semaphore : CS이 1개이상 들어갈 수 있다

Critical Section of n Processes

Synchronization variable
semaphore mutex; /* initially 1: 1개가 CS에 들어갈 수 있다 */

Process Pi
do {
		P(mutex); //lock을 걸때 CS에 들어가야하면 P연산을 해주고,
		critical section
		V(mutex); //빠져나올 때에는 V연산 해줌
		remainder section
}while(1);

busy-wait는 효율적이지 못함(=spin lock)

Block&Wakeup 방식의 구현(=sleep lock)

 

Block / Wakeup Implementation

Semaphore를 다음과 같이 정의

typedef struct
{
	int value; /* semaphore 변수 값 */
	struct process *L; /* semaphore때문에 잠들어있는 프로세스들을 연결하기 위한 큐! */
}semaphore;

block : 커널은 block을 호출한 프로세스를 suspend시킴, 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음 (semaphore를 획득할 수 없으면 그 프로세스를 block 시킴)

wakeup(P) : block된 프로세스 P를 wakeup시킴, 이 프로세스의 PCB를 ready queue로 옮김

P(S): S.value--; /* prepare to enter */ //값을 1 빼줌!!
			if (S.value <0) // 깂이 음수이면 자원이 없겠지,
			{
			add this process to S.L; //S.L에 연결 시키고
			Block(); //Block 상태로 만듦!
			}

V(S) : S.value++; //자원을 다 쓰고 나면, 값을 1증가시켜주고,
			if (S.value <= 0) //S.value가 0이하면, 자원을 내놓았음에도 불구하고 0이하라면, 이친구를 기다리며 누군가가 잠들어 있다는 거지
      {
			remove a process P from S.L;
			wakeup(P);
      }

Which is better?

• Busy wait vs Block/wake up
• Block/Wakeup overhead vs Critical Section 길이
  • Critical Section의 길이가 긴 경우 Block/Wakeup이 적당함
  • Critical Section의 길이가 매우 짧은 경우 Block/Wakeup의 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
  • 일반적으로 Block/wakeup방식이 더 좋음

Two types of Semaphores

• Counting semaphore
  • 도메인이 0 이상인 임의의 정수값
  • 주로 resource counting에 사용
• Binary semaphore(=mutex)
  • 0 또는 1 값만 가질 수 있는 semaphore
  • 주로 mutual exclusion(lock/unlock)에 사용

Deadlock and Starvation

Deadlock

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

Starvation

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