Process Synchronization-2

Process Synchronization-2

Mutex Locks

acquire() {
	while (!available)
		; // busy waiting
	available = false;
}

release() {
	available = true;
}

do {
	acquire();

    /** critical section **/

    release();

    /** remainder section **/
} while (true);
  • 임계 영역에 대한 입장을 보호하는 도구
  • available이라는 변수와 acquire, release 함수로 구성됨
  • 임계 영역 이전에 acquire 함수를 실행하면서 다른 프로세스의 임계 영역 접근을 막음
    • 만약 다른 프로세스가 임계 영역을 사용하고 있다면, 현재 프로세스가 busy waiting이 걸림
  • 임계 영역 이후에 release 함수를 실행하면서 다른 프로세스의 임계 영역 접근을 허용
  • 특정 프로세스가 mutex lock의 소유권을 가짐

Semaphores

  • Mutex lock 보다 정교한 도구이며, 특정 프로세스가 소유권을 가지지 않음
  • Semaphore라는 정수 값과 wait, signal 함수로 구성됨
  • Busy waiting 혹은 block / wakeup을 이용한 구현이 가능

Semaphore 구현 (Busy Waiting)

wait(S) {
	while (S <= 0)
		; // busy waiting
	S--;
}

signal(S) {
	S++;
}
  • Busy waiting을 이용한 구현. Mutex lock과 유사
  • wait 함수는 acquire 함수와, signal 함수는 release 함수와 유사
  • 임계 영역이 짧은 경우에는 효과적

Semaphore 구현 (block / wakeup)

typedef struct {
	int value;
	struct process *list;
} semaphore

wait(semaphore *S) {
	S->value--;
    if (S->value < 0){
    	add the PCB of this process to S->list;
        block();
    }
}

signal(semaphore *S) {
	S->value++;
	if (S->value <= 0) {
    	remove a process P from S->list;
		wakeup(P);
	}
}
  • block / wakeup 함수를 통한 semaphore 구현
  • list라는 멤버 변수에 PCB 배열을 저장
  • wait
    • block() 함수는 프로세스 실행을 중지하는 함수
    • 만약 임계 영역에 진입이 불가한 경우 block 함수를 통해 현재 프로세스를 중지시키고 PCB를 리스트에 넣음
  • signal
    • wakeup(P) 함수는 중지된 프로세스 P를 다시 실행하는 함수
    • 리스트에 중지된 프로세스가 있다면 wakeup 함수를 통해 해당 프로세스를 다시 실행시키고 PCB를 리스트에서 제거
  • 장점
    • 임계 영역이 길수록 효과적
    • Busy waiting을 사용하지 않아도 된다는 장점 존재
  • 단점
    • 임계 영역을 진입함에 있어 deadlock 발생 가능
    • 프로세스를 큐에서 꺼낼 때 LIFO 순으로 꺼낸다면 starvation 발생 가능

References

  1. Operating System Concepts 9th Edition, Silberschatz, Galvin and Gagne ©2013

기타

2022-07-30에 작성된 Process Synchronization 문서를 정리하고 보완하는 중