Skip to content

Latest commit

 

History

History
170 lines (104 loc) · 6.66 KB

07-뮤텍스_세마포어.md

File metadata and controls

170 lines (104 loc) · 6.66 KB

배경

프로세스 동기화 시 공유 데이터 관리 문제에서 상호 배제를 충족하기 위한 방법이다.

  • 뮤텍스 락 (Mutex Locks) : 가장 간단한 방법으로 임계 영역에 진입할 때 열쇠를 받고 나올 때 열쇠를 반납하는 개념으로 2개의 프로세스 간의 동기화를 제어 한다.

  • 세마포어 (Semaphore) : 뮤텍스와 달리 n개의 프로세스 간의 동기화를 제어 할 수 있다.

  • 모니터 (Monitor) : 뮤텍스와 세마포어의 단점을 해소한 방법으로 자바에서 사용된다.

  • 뮤텍스: 한 쓰레드, 프로세스에 의해 소유될 수 있는 Key를 기반으로 한 상호배제기법

  • 세마포어: Signaling mechanism. 현재 공유자원에 접근할 수 있는 쓰레드, 프로세스의 수를 나타내는 값을 두어 상호배제를 달성하는 기법



1. 뮤텍스 락 (Mutex Lock)

열쇠를 사용하여 임계 영역에 진입한다. 그리고 임계 영역을 모두 수행한 후에는 열쇠를 반납한다.

따라서, 열쇠를 얻는 과정 (acquire lock)과 열쇠를 반납하는 과정 (release lock)이 필요하며, aquire와 relase 과정은 반드시 atomic 하게 수행되어야 한다. 즉, aquire함수나 relase 함수 내부에서 중단된 후 context switch 가 일어나면 안된다.

aquire 함수

acquire(){
    while(!available){
        // 열쇠가 현재 사용중이므로
        // 기다린다...(Busy waiting)
    }
    // 열쇠 획득 후 사용중이라고 표시해준다.
    available = false;

}

release 함수

release(){
    avaiable=true;
}

Busy waiting 문제

acquire 함수에서 어떤 프로세스가 임계 영역에 접근하기 위해서는 열쇠가 release 될 때 까지 무한 루프 해야하는 문제

  • 만약 싱글 코어일 경우 Busy waiting의 무한루프는 CPU를 쓸데 없이 소모시키므로, 다른 프로세스가 생산적으로 사용 할 수 있는 시간을 감소시킨다.

SpinLock

위에서 Busy waiting을 일으키는 Mutex Lock을 SpinLock이라고 말하며, 이 SpinLock의 구현방식은 멀티코어 환경에서 아래와 같이 동작한다.

그림에서 세번째 CPU의 프로세스이름을 프로세스 3 으로 했어야했는디,,

  • 멀티 코어일 경우 다른 코어에서 Busy waiting을 하고 있다가 해당 코어에서 바로 임계 영역에 진입할 수 있으므로 Context Switch 비용을 아껴준다.

Spin Lock 을 구현하지 않는다면...

  • Spin Lock을 하지 않기 위해서는 프로세스가 Wait queue에서 기다려야하는데, 그럴 경우 Ready Queue에 들어가는 시간도 포함되므로 Context Switch 비용이 든다.


2. 세마포어 (Semaphore)

세마포어는 wait()과 signal()이라는 두 개의 Atomic한 함수로 구성된다.

여기서 S는 정수 변수이며 현재 공유 데이터로 접근 가능한 출입문의 갯수라고 생각하면 쉽다.

wait 함수

wait(S){
    while(S<=0){
        // 모든 출입문이 꽉 참
        // Busy wait
    }
    S--;
}

signal 함수

signal(S){
    S++;
}

바이너리 세마포어 (Binary Semaphore)

S = 1 인경우로, 이는 뮤텍스 락과 비슷하게 동작한다.

카운팅 세마포어 (Counting Sempahore)

S = n ( n > 1 ) 인 경우로 S가 무한대로 증가할 수 있다. 이는, 여러개의 인스턴스를 가진 자원에 사용될 수 있다. ex) 컴퓨터에 등록된 프린터가 3개인 경우, 인스턴스(프린터 )는 3개이다.

  1. S를 사용 가능한 자원의 갯수로 초기화 시켜준다.

  2. 프로세스가 자원을 사용할 경우

    • wait() 을 실행하여 현재 사용가능한 S의 갯수를 줄여준다.

  3. 프로세스가 자원을 반납할 경우

    • signal()을 실행하여 현재 사용가능한 S의 갯수를 늘려준다.

  4. S = 0 인 경우 (= 모든 리소스가 사용 중인 경우)

    • S가 0보다 커질 때 까지 Busy wait

순서 보장 해결법

Statement1을 가진 프로세스A와 Statement2를 가진 프로세스 B가 동시에 실행 될 경우, Statement1이 무조건 Statement2 보다 먼저 실행되어야 한다고 했을 때 어떻게 순서를 지킬 수 있을까?

이를 위해서는 프로세스A가 종료된 후, 프로세스 B가 실행된다는 것을 보장해야한다.

따라서 프로세스 A와 프로세스 B가 세마포어 Synch를 공유하고, wait 함수 에서 무조건 세마포어 synch를 0으로 초기화 해준다.

  1. 뒤에 실행되어야 하는 프로세스 B 에서 wait 을 실행한다 -> synch 가 0으로 초기화 되므로 프로세스 A에서 signal 이 실행될 때 까지 대기한다.
  2. 먼저 실행되어야 하는 프로세스 A 에서 Statement1 을 실행한 후 signal을 실행하면 synch가 증가하여 0보다 큰 수가 된다.
  3. synch 가 증가해으므로 프로세스 B에서 busy wait을 탈출하여 Statement2를 실행한다.
// 프로세스 A
Statement1; // 생략
signal(synch); // synch 증가


// 프로세스 B

wait(synch); // synch를 0으로 초기화한다.
Statement2;

Busy waiting 문제

뮤텍스 락과 마찬가지로 Busy waiting 문제가 있다. 세마포어 방법에서는 여러개의 자원을 사용하므로 아래와 같이 wait함수와 signal 함수를 수정하여 문제를 해결 할 수 있다.

  1. wait() 함수에서 세마포어가 음수라면 해당 프로세스 sleep 시켜 waiting queue에 적재한다.

  2. signal() 함수에서 waiting queue에서 대기 중인 프로세스 wake-up 하여 ready queue에 적재한다.



참고