Process Synchronization(2)

Semaphore

Busy Waiting을 필요로 하지 않는 동기화 도구

🛑 Busy Waiting이란? Critical Section에 들어가기 위해 계속 while문의 조건을 검사하느라 바쁘게 기다리는 것.

Semaphore는 Integer 변수의 이름을 Semaphore라고 한다. → 공유된 자원의 수를 가르키는 변수‼️

두 표준함수 **Wait(S)와 Signal(S)**를 통해서 동작한다.

Wait(S)와 Signal(S) 은 Atomic한 Operations으로 주어진 작업을 처리할 때 까지 끝까지 동작한다.

• Binary Semaphore : Semaphore Integer Variable이 0 or 1의 값만 가지는 것. → mutex (mutual exclusive) lock이라고도 한다. 열쇠를 획득하기 위한 exclusion
• Counting Semaphore : Semaphore Integer Variable의 값이 제한된 영역을 벗어날 수 있다.
• Ex) 0...1...2..3...4..

Wait(S) -> Critical Section -> Signal(S)의 순서대로 실행되며

//Entry Section
Wait(S);

//Critical Section
CriticalWork(S);

//Exit Section
Signal(S);

Wait(S)는 S의 값이 0보다 커질 때 까지 기다리며, 0보다 커지면 S를 감소(S--;)시키고 탈출한다.

Wait(int S){
	while(S <= 0); //Do Nothing
	//While문이 깨지면 아래 코드 실행.
	DoSomething();
	S--; //S 감소시키고 탈출.
}

Signal(S)는 S값을 하나 증가시킨다. (S++;)

Signal(S){
	S++;
}

Semaphore의 구현

동시에 같은 Semaphore의 Wait(), Signal()함수를 실행하지 않는 것을 보장해야한다.

→ Single CPU에서는 Interrupt를 끄는 방식을 통해서 보장한다. (Interrupt Disable)

→ Multiple CPU에서는 Spinlock을 사용. Spinlock : 열쇠를 획득하기 위해 프로세스가 헛도는 것. Mutiple CPU 환경에서는 여러가지 선택지가 있다.

1. Spin lock : Busy Waiting 방식, Short time에 효과적 → Critical Section에서 하는 일이 짧을 경우 ➕ Process가 기다리는 시간이 짧을 경우 효과적
2. Context Switching : 한 Process를 중지시키고, Scheduling한 뒤, 다른 Process실행 → 기다려야 하는 시간이 길다면 효과적이다.

1. Busy Waiting을 사용한 Semaphore 구현.

//Entry Section
Wait(S);

//Critical Section
CriticalWork(S);

//Exit Section
Signal(S);

그냥 Wait(S)와 Signal(S) 사용.

Busy Waiting의 장점

1. 구현 코드가 짧다 -> 구현이 쉽다.
2. 조금 기다린다면 (Critical Section을 차지하는 시간이 짧다면) 효율적이다.

BUT. Critical Section을 차지하는 시간이 오래 걸린다면 좋은 방법이 아니다!

2. Busy Waiting을 사용하지 않는 Semaphore 구현.

각각의 Semaphore는 각각 자신만의 Waiting Queue를 갖고 있다.

그 Waiting Queue에 들어갈 때 Value와 Pointer를 저장한다.

• Value : Semaphore의 변수값(정수)
• Pointer : 그 다음 프로세스의 주소값.

또. 두개의 Operation을 통해서 동작한다.

• Block : 프로세스를 중지하고 Waiting Queue에 넣는 것.
• Wakeup : Waiting Queue에서 프로세스를 꺼내 Ready Queue에 넣는 것

//Entry Section
Wait(S){
	S--; //Semaphore 값. 감소
	if(S < 0){
		Block(P); //P라는 프로세스를 Wait state로 변경.
	}
}

//Critical Section
CriticalWork();

//Exit Section
Signal(S){
	S++;
	if(Value <= 0){
		Wakeup(P); //P라는 Process를 Ready state로 변경.
	}
}

Deadlock과 Starvation

Deadlock : 두개 이상의 Process들이 서로 풀어주기를 기다려야 하는 현상.

서로가 서로를 기다려 Process들이 기다리기만 하고 있는 상태.

Starvation : Deadlock으로 인해서 일어나는 Indefinite Blocking.

Classical Problems of Synchronization

EX) Bounded-Buffer Problem : Producer - Consumer

Producer와 Consumer 사이에는 Buffer가 있다.

N개의 Buffer를 사용하는 경우 다음과 같은 3가지의 Semaphore값을 가진다.

1. Mutex : 정수. 초기값은 1. 상호배제용 변수.
2. Full : 정수. 초기값은 0. Data가 차있는 버퍼의 수.
3. Empty : 정수. 초기값은 N. 빈 버퍼의 수

Producer의 진행과정.

do{
	//Entry Section
	Wait(empty); //Buffer가 꽉 차지 않았는지 확인한다.
	Wait(mutex); //Critical Section을 사용하고 있는 Process가 있는지 확인.

	//Critical Section
	CriticalWork(); //Critical Section에서 Consumer에게 제공할 정보를 Buffer에 저장한다.

	//Exit Section
	Signal(mutex); //Critical Section을 나갔음을 표시한다.
	Signal(full); //Buffer가 하나 찼음을 표시한다.

}while(true);

Consumer의 진행과정.

do{
	//Entry Section
	Wait(full); //Buffer가 차 있는지 검사. 있으면 통과!
	Wait(mutex); //Critical Section을 사용하고 있는 Process가 있는지 확인.

	//Critical Section
	CriticalWork(); //Producer가 제공한 정보를 확인하고, 버퍼를 비운다.

	//Exit Section
	Signal(mutex); //Consumer가 Critical Section에서 나왔음을 표시
	Signal(empty); //Consumer가 Buffer를 하나 비웠음을 표시.

}while(true);

→ Full이라는 Semaphore와 Empty라는 Semaphore는 상호 보완적임을 알 수 있다.

CASE Study.

Solaris

• Multitasking, Multithreading, Multiprocessing을 지원하기 위한 여러가지 lock매커니즘을 제공한다.
• Adaptive Mutexes : 상황에 적절한 Mutexes(mutual exclusive) 기법을 적용한다.Critical Section에 접근하는 시간이 길다 ⇒ Sleep(Waiting Queue 사용)
• Single Processor의 경우 항상 Spin lock보다는 Sleep(Block)을 선호
• Critical Section에 접근하는 시간이 짧다 ⇒ Spin lock(Busy Waiting)
• (Wait & Sleep)을 조절하는 Condition Variable을 사용한다.
• Readers Writers lock기법 사용 → lock의 종류가 Reader와 Writer에 따라 달라져 reader의 키는 상관쓰지 않고 Writer의 키를 중요하게 관리한다.
• Turnsile(줄세우기) 기법 사용 → 일종의 회전문. Adaptive Mutex or Reader Writer lock을 휙득하기 위해 기다리는 Thread들을 순서화 하는 기법.

Window XP

• Uniprocessor System에 대해서는 Interrupt mask사용. Interrupt mask : Interrupt를 꺼버리는 것.
• Multi Processor System에 대해 Spin lock 사용.
• Dispatcher objects 제공 → Dispatcher Objects는 Event를 발생 ⇒ Event : Condition Variable으로 조건에 따라서 Wait & Sleep을 조절한다.

Linux

• Critical Sections에 접근하는 시간이 짧다면 Disables Interrupt를 사용한다. → Interrupt 꺼버리기.
• MultiProcessor에 대해서는 Semaphore, Spin lock을 사용한다.