[Operating System] Semaphore

 

 

한 프로세스가 임계 구역에 접근할 때 CPU Interrupt를 비활성화하면 현재 실행 중인 코드가 중단되지 않아 Critical Section을 보호할 수 있다. 

 

원래는 CPU는 명령어를 실행하고 Interrupt가 발생했는지 매번 확인하는데, Atomic Operation을 실행할 때는 Interrupt를 비활성화한다.

이 때 Interrupt를 아예 무시하는건 아니고, Atomic Operation이 마무리 된 후에 그 동안 발생한 Interrpt를 수행하는 방식으로 동작해 처리를 뒤로 미룬다고 생각하자.

 

시스템 성능 저하 문제 때문..

사용자 코드를 Atomic Operation으로 실행하는건 좋지 않지만, Entry Section을 Atomic Operation으로 다루는건 합리적이다.

 

운영체제는 Test and Set Instruction 명령어같은 하드웨어 지원 명령어를 사용해 Entry Section을 안전하게 구현한다.

 

 

 

 

testset 함수는 실행 전에 Interrupt를 비활성화해서 Atomic 환경에서 실행된다.

 

P(1)이 CPU를 할당받고 Critical Section을 작업하던 도중 시간이 만료되어 P(2)에게 CPU가 넘어가더라도 testset 함수가 Atomic하게 실행되고 있기에 P(2) ~ P(n)은 Critical Section을 작업할 수 없다.

 

Critical Section 자체를 Atomic하게 구현하는 Bakery Algorithm을 사용할 때 보다 쉽게 구현할 수 있지만..

 

여전히 Busy Waiting이 발생해 CPU 자원을 낭비하게 되고,

P(1)이 수행된 후 P(2)가 아닌 다른 프로세스가 실행될 수 있어 Bounded Waiting을 보장할 수 없고, 

우선순위가 차등적으로 부여된 프로세스를 스케쥴링 할 때 데드락이 발생할 수 있다는 문제가 있다. 

 

현대 운영체제는 우선순위가 낮은 프로세스도 장기간 대기 시 우선순위가 높은 프로세스가 있더라도 CPU를 할당해 해당 프로세스가 Critical Section을 마무리 할 수 있도록 스케쥴링 수준에서 해당 문제를 해결한다. 

 

 

 

---

 

 

 

TestSet함수를 사용하는 하드웨어 방식의 단점을 극복하기 위해 Semaphore가 도입됐다.

 

Semaphore는 운영체제에서 프로세스간 동기화와 공유 자원 접근 제어를 위해 사용되는 정수형 동기화 도구이다.

운영체제가 제공하는 Semaphore 관련 함수는 하드웨어의 지원을 받아 Atomic하게 실행됨이 보장된다.

 

TestSet의 단점은 BusyWaiting인데, Semaphore는 프로세스가 Critical Section에 진입할 수 없음을 인지했을 때 무한정 대기하지 않고 프로세스를 block 상태로 변경하고 다시 스케쥴링한다.

 

Semaphore는 정수 변수와 대기 큐로 구성된다. 

 

 

 

다른 프로세스가 Critical Section을 점유하고 있으면 현재 프로세스는 Block Queue로 이동한다.

Critical Section 조작이 끝났다면 Queue에 있는 프로세스는 Ready 상태가 되고, 다시 스케쥴링되어 CPU를 할당받는다.

 

 

 

 

운영체제가 제공하는 semWait와 semSignal 함수는 Atomic Operation이다.

 

count는 현재 사용 가능한 자원의 수, queue는 자원을 기다리는 프로세스들을 저장하는 대기 큐를 의미한다.

 

semWait는 자원을 요청하고, 자원이 없으면 현재 프로세스를 대기 상태로 만드는 역할을 수행한다.

semSignal은 자원을 반납하고 대기 중인 프로세스가 있다면 하나를 깨워 실행 가능 상태로 만드는 역할을 수행한다.

 

동시에 여러 프로세스가 Semaphore에 접근한다면 Race Condition이 발생해 count가 꼬이거나 Queue가 손상될 수 있으니 두 함수는 반드시 Atomic하게 실행되어야 한다.

 

 

 

 

(mutual exclusion = mutex)

 

testset과 비교했을 때..

Busy Waiting 문제와 Bounded Waiting 문제를 깔끔하게 해결했고, 코드 라인도 줄어들었다.

 

semaphore s = 1; 부분에 집중하자.

값이 0과 1만을 가지는 Binary Semaphore로, 한 번에 하나의 프로세스만 Critical Section에 들어가도록 설정하기 위한 값이다.

s가 2 이상의 값을 가지는 경우 Counting Semaphore로 한 번에 최대 n개의 프로세스가 Critical Section에 진입할 수 있음을 의미한다.

 

 

/* program producerconsumer */
semaphore counter = 0;
semaphore empty = BUFFER_SIZE;
semaphore mut_ex = 1;
void producer()
{
    while (true)
    {
        produce();
        semWait(empty);
        semWait(mut_ex);
        append(); /* put the produced item into the buffer */
        semSignal(mut_ex);
        semSignal(counter);
    }
}

void consumer()
{
    while (true)
    {
        semWait(counter);
        semWait(mut_ex);
        take(); /* get an item from the buffer */
        semSignal(mut_ex);
        semSignal(empty);
        consume();
    }
}
void main()
{
    parbegin(producer1, producer2,…, consumer);
}

 

 

Producer는 데이터를 버퍼에 넣고 Consumer는 데이터를 버퍼에서 꺼낸다.

 

세마포어를 정의하는 부분이 중요하다.

counter - 버퍼에 들어 있는 항목의 수 

empty - 버퍼에 남은 빈 공간의 수 

mut_ex - 한 번에 하나의 프로세스만 Critical Section에 접근하도록 하는 Binary Semaphore

 

Producer와 Consumer가 서로를 깨워주면서 

여러 생산자와 소비자가 버퍼를 공유하더라도 자원 수를 정확하게 관리하고 Race Condition을 방지한다.

 

semWait가 호출되는 횟수와 semSignal이 호출되는 횟수는 일치해야 한다.

 

 

 

 

프로그램의 실행 순서를 결정할 때도 세마포어를 사용할 수 있다.

 

Pi의 A프로그램이 실행된 이후에 Pk의 B 프로그램이 실행되어야 한다고 하자.

semaphore flag = 0; 으로 시작한다. 이 플래그는 B의 실행을 지연시키는 역할을 수행한다.

 

초기 값이 0이니 B는 block 상태이고, A가 semSignal(flag)를 보내야 플래그가 1로 변하고 B가 semWait(flag)를 통과한다.

 

 

/* program readersandwriters */
int readcount;
semaphore rsem = 1, wsem = 1;
void main()
{
    readcount = 0;
    parbegin(reader1, reader2, … writer1, writer2,…);
}

void writer()
{
    while (true)
    {
        semWait(wsem); /* wsem : writer semaphore */
        WRITEUNIT();
        semSignal(wsem);
    }
}

void reader()
{
    while (true)
    {
        semWait(rsem); /* rsem : reader semaphore */
        readcount++;
        if (readcount == 1)
            semWait(wsem);
        semSignal(rsem);
        READUNIT();
        semWait(rsem);
        readcount--;
        if (readcount == 0)
            semSignal(wsem);
        semSignal(rsem);
    }
}

 

 

공유 자원에 대해 읽기 작업만 수행하는 경우 동시 접근을 허용해도 되고, 쓰기 작업을 수행할 때만 배타적으로 접근해야 한다.

 

rsem은 readcount를 보호하기 위한 값이고, wsem은 Writer 전용 락을 의미한다.

 

Reader는 동시에 읽을 수 있도록 허용되지만

semWait(wsem) - 첫 번째 Reader는 Writer가 접근할 수 없도록 방지한다.

semSignal(wsem) - 마지막 Reader가 나가면 Writer를 다시 풀어준다.

 

Writer는 wsem이 잠겨 있지 않으면 바로 쓰기 작업을 수행할 수 있고, Reader가 들어올 때 마다 wsem을 잠가서 Writer를 차단한다. 

 

 

Mutex라고도 불리는 Binary Semaphore에서 0은 잠김 상태를, 1은 열림 상태를 의미한다.

프로세스가 깨어나는 순서를 보장하지는 않아 Bounded Waiting 문제가 발생할 수 있는데.. 이 부분은 운영체제마다 다르게 구현되어 문제를 해결한다. (리눅스는 pthread_mutex 사용)

 

Monitor는 Semaphore보다 더 높은 수준에서 락을 조작할 수 있도록 도와준다.
자바에서는 synchronized 키워드를 통해 문법 수준에서 자연스럽게 사용할 수 있다.

 

이렇게.. 실제로 여러 세마포어를 함께 사용해 동시성을 제어한다. 

Counting Semaphore는 버퍼 공간, 네트워크 포트 수 처럼 자원의 수를 나타내고 (n)

Binary Semaphore는 뮤텍스처럼 상호 배제 용도로 사용된다. (0 or 1)

 

즉, 세마포어마다 역할이 다르다. 

Producer - Consumer Problem에서도 empty는 생산자를 제한할 때 사용되고, counter는 소비자를 제한할 때 사용되며 mut_ex는 버퍼 접근에 대한 상호 배제를 구현할 때 사용했다.