[운영체제/OS] Mutex Locks, Semaphore, Conditional Variable

Mutex Locks

임계구역문제 해결을 위해서 운영체제 디자이너들이 만들었다.

임계구역문제에 대해서 알고싶다면 지난 게시글을 참고해주세요~

[운영체제 OS] - [운영체제/OS] Synchronization_동기화, 임계 구역 문제

[운영체제/OS] Synchronization_동기화, 임계 구역 문제

 

임계구역을 처음에 acquire()로 lock하고 그 다음 lock을 release()함으로써 임계구역을 보호한다.

acquire()과 release()는 "atomic"해야 한다.

하지만 이 해결책은 busy waiting을 유발할 수 있다. 이러한 lock은 spinlock(의미 없는 접근 반복)이라 불린다.

 

 

acquire(){
	while(!available)
    	;/*busy wait*/
    available = false;;
}
release(){
	available = true;
}
do{
	acquire lock
    	critical section
    release lock
    	remainder section
} while(true);

 

Semaphore(세마포어)

mutex(뮤텍스)보다 발전한 형태로 공유 자원을 사용한다. 

세마포어 S는 정수 변수다. 

wait()와 signal()이라는 두 atomic operations을 통해서만 접근할 수 있다.

wait(S){
	while(S<=0)
    	;//busy wait
    S--;	//자원점유
}

signal(S){
	S++;	//자원양보
}

세마포어는 2 종류:
-Counting semaphore - integer값의 범위를 통해

-Binary semaphore - integer값이 0과 1 뿐.(mutex lock과 동일)

 

세마포어를 구현할 때는

wait()와 signal()이 반드시 같은 세마포어에서 동시에 실행되지 않음을 보장해야한다. 

busy waiting이 일어날 수 있다는 단점이 있다....

 

Busy Waiting없는 세마포어 구현

각 세마포어에 대한 waiting queue가 있다.

각 waiting queue의 entry에는 두 가지: value(integer) & 다음프로세스 가리키는 list 내 포인터

 

typedef struct{
	int value;		//세마포어 값
   	struct process *list;	//대기 중인 PCB 리스트를 가리키는 포인터 
}

추가 operation) block과 wakeup 

block(): wait()내부에서 실행되며 list에 자기를 프로세스에 waiting queue에 추가하고 sleep한다.

wakeup(): signal()내부에서 실행되며 대기하고 있는 프로세스를 list에서 제거하고 ready queue로깨운다.

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

signal(semaphore *S){
	S->value++;
    if(S->value <= 0){
    	remove a process P from S->list;
       	wakeup(P);
    }
}

세마포어를 잘못 쓴 경우

signal(mutex)--wait(mutex): 잠들기 전에 깨우고 잠든 경우

wait(mutex)--wait(mutex): 아무도 안 깨우는 deadlock인 경우

wait(mutex)나 signal(mutex) (아니면 둘다) 빠뜨린 경우

 

--> Deadlock(다 wait)나 Starvation(wait하는데 signal 없음) 이 발생가능하다. 

 

 

 

Monitors

C와 C++엔 없고 C#과 Java에 있다.

클래스 객체 개념과 비슷하다.

monitor monitor-name
{
//shared variable declarations
function P1(...) {...}
.
.// 이 안에서만 이뤄짐
.
function Pn(...) {...}
	Initialization code (..) {...}
    }
}

 

조건 변수(Condition Variables)

-조건(condition) x, y

-프로그래머는 하나 이상의 조건 타입의 변수를 정의할 수 있다

 

조건 변수에 적용되는 두 가지 연산

-X.wait(): 이 연산을 호출한 프로세스는 보류하게 된다.

-X.signal(): X.wait()를 호출해서 보류 중이었던 프로세스 하나만 재개함. 없다면, 아무것도 일어나지 않음.

 

즉, x.wait()는 x.signal()이 불릴 때까지 프로세스가 기다리고

x.signal()는 x.wait()가 호출되었던 프로세스를 재개시킨다. (x.wait()였던 프로세스가 없다면 아무것도 일어나지 않음.)

 

 

만약 프로세스 P가 x.signal()를 받고, 프로세스 Q가 x.wait()를 받은 후에는?

-Signal and wait: Q가 먼저 수행할때까지 P가 기다린다.

-Signal and continue: P가 먼저 수행할때까지 Q가 기다린다.

 

세마포어를 사용한 Monitor 구현

wait(mutex);
	body of F;
if(next_count > 0)	//기다리는 애한테 머저 (순서 먼저)
	signal(next);
else
	signal(mutex);	//기다리는 애한테 풀어줌.

 

Producer-Consumer Problem 생산자-소비자 문제

Producer: 

x++
cond.signal();
cond.wait();
print(x);

Consumer:

cond.wait();
x++;
cond.signal();