[운영체제] 세마포어

Busy Wating

• 기존에 배웠던 방식의 공통점은 모두 while문을 사용했다. 즉, Busy Wating 알고리즘이다.
• 이는 무한루프를 돌면서 기다리고, 계속해서 타임슬라이스를 사용하기 때문에 낭비이다.
• 이에 대한 대안으로 제안된 것이 '세마포어'이다.
• 하지만 무한루프를 도는 것이 무조건 나쁜 것은 아니다. 커널 내에서 루프를 활용해 임계구역에 락을 거는 것을 'spin lock'이라고 한다. 상호 배제 관계에 있는 임계구역의 계산량이 현저히 적다는 것을 이미 개발자가 알고 있다면 spin lock을 활용하는 것이 세마포어보다 문맥교환의 오버헤드를 줄일 수 있어 효과적이다.

세마포어

• 세마포어는 임계구역을 진입하기 어려울 때, 자발적으로 '대기(BLOCK)'상태에 들어가는 것이다. 임계구역을 떠나는 프로세스가 대기상태에 있는 프로세스를 준비 상태로 깨워준다. 즉, block/wakeup 알고리즘이다. 따라서 타임슬라이스의 낭비가 적다.
• 일종의 객체와 같이 구성되어 있다. 하나의 정수값(value), 프로세스 대기큐(세마포어 대기큐), 정수에 대한 3가지 연산(init,wait(P연산), signal(V연산))
• 세마포어의 객체를 S라 하면, S.value는 자원 활용 현황이다. 양수라면 남아있는 자원 수를 나타내고 음수라면 부족하여 대기 중인 대기자 수를 뜻한다. S.value의 초기값 n이 자원의 개수이다.

세마포어의 동작

init(semaphore *S, int n) {
    S->value = n;
}

wait(semaphore *S){ // P 연산이라고도 함
    S->value-- ;
    if ( S->value < 0 ) {
        //이 프로세스를 S->list에 넣는다;
        block();
    }
}

signal(semaphore *S) { // V 연산이라고도 함
    S->value++;
    if ( S->value <= 0 ) {
        S->list로부터 하나의 프로세스 P를 꺼낸다;
        wakeup(P);
    }
}

• init 함수는 초기값 n을 세마포어의 S에 할당한다.
• wait 함수에서는 자원을 하나 줘야 하므로 value 값 하나를 뺀다. 만약 value가 음수가 되었다면 자원이 모자라다는 뜻이므로 해당 프로세스(쓰레드)를 세마포어의 list(대기큐)에 넣고 block상태를 호출하여 대기상태로 바꿔놓는다.
• signal 함수가 호출되면 자원을 반납받을테니 value 값을 하나 늘려준다. 만약 value가 0이거나 음수라면 아직 자원을 사용하기 위해 대기하는 프로세스가 존재한다는 의미이다. 따라서 대기큐 list에서 프로세스 P를 꺼내서 wakeup해준다. 그에 따라 해당 프로세스는 준비상태가 되고, 스케줄링에 의해 실행상태가 될 것이다.
• 세마포어의 모든 연산은 atomic하게 실행되어야 한다. wait연산을 하는 동안 signal 연산을 하거나 signal 연산을 하는 동안 wait 연산을 하는 경우가 발생해선 안된다. 처리기가 하나인 경우 각 연산들이 실행되는 동안 인터럽트를 disable하여 해결한다. 다중처리기인 경우 모든 처리기를 disalble 시키면 시스템 성능이 저하될 수 있으므로, wait와 signal을 처리할 때 해당 value를 대상으로 spin lock방식을 사용한다. wait와 signal을 처리하는 데 걸리는 시간이 매우 적어 가능한 일이다.

세마포어의 다양한 활용

• 세마포어 실행에 있어 중요한 것은 value값 처리이다. 해당 값이 음수인 경우엔 대기중인 프로세스 수를 의미하고, 양수인 경우 남는 자원의 수를 의미한다.
• 세마포어는 value의 초기값을 어떻게 설정하느냐에 따라 다양하게 활용이 가능하다. 초기값이 1이라면 공유변수에 대한 상호배제에 활용하겠지만, 그보다 클 경우 자원 여러개에 대해 대기자를 관리하는데에 활용할 수 있을 것이다.
• 초기값이 0일 경우 한 쓰레드가 wait하고 나면 value값이 곧바로 음수가 되기 때문에 블록된다. 그러면 다른 쓰레드가 signal을 호출하기 전까진 수행이 블록된다. 따라서 wait를 호출한 쓰레드는 signal을 호출하는 쓰레드에서 signal을 수행하기 전까지 수행되지 않는다. 따라서 프로세스 흐름을 serialize(순서화)할 수 있게 된다.

세마포어 활용의 예

Semaphore Mtx;
init(Mtx, 1);

wait(Mtx);
//critical section
signal(Mtx);

• 처음 임계구역에 진입하는 프로세스는 정상적으로 작동하지만, 나머지 프로세스는 value값이 0보다 작을 것이므로 block 상태에 들어간다.
• signal을 받으면 value가 다시 1이 되고, 프로세스 하나가 wakeup하여 준비,실행 상태가 된다.

세마포어를 활용한 생산자/소비자 문제

semaphore cs, full, empty; 
init(cs, 1); // 공유변수 상호배제를 위한 임계구역 설정에 사용
init(full, n); // 생산자 입장에서 볼 때 n개의 빈 셀이 없어지면 full
init(empty, 0); // 소비자 입장에서 볼 때 자료가 있는 셀이 0개이면 empty

producer :
    //아이템생성
    wait(full); // 빈 셀이 있는지
    wait(cs);
    // 아이템 저장
    signal(cs);
    signal(empty);
    goto producer; 

consumer :
    wait(empty); // 자료가 있는지
    wait(cs);
    remove an item;
    signal(cs);
    signal(full);
    //아이템소비
    goto consumer; 

Readers-Writers 문제

• 여러개의 프로세스(쓰레드)가 하나의 공유 버퍼에 대해 읽기와 쓰기를 할 경우 : 하나의 읽기 프로세스가 임계구역에 진입하면, 쓰기 프로세스는 대기해야한다. 하지만, 다른 읽기 프로세스들도 대기해야될 이유는 없다.
• 이를 해결하기 위해 공유 변수나 파일에 쓰기 연산을 하는 프로세스는 모든 프로세스에 대해 배타적으로 구동되는 exclusive lock을 사용하고, 읽기 프로세스끼리는 lock을 공유하는 shared lock을 사용하도록 한다. 즉, writer’s lock과 reader’s lock을 구분하는 것이다.
• 하지만 이 경우 lock을 처리하기 위해 reader모드인지 writer모드인지 밝히도록 처리해야하는 번거로움이 있다.
• 만약 읽기 프로세스가 계속해서 꼬리에 꼬리를 물고 shared lock을 차지하면 특정 writer 프로세스는 무한히 기다려야 할 수 있다. 결국 기아 또한 무한 봉쇄 문제를 야기할 수 있다. Reader-Writer를 위한 대기 큐와 Reader를 위한 대기큐를 분리하여 ReaderWriter 대기 큐에는 많은 Reader 프로세스 중 하나를 들어가도록 함으로써 이를 해결할 수 있다.

---

순위 역전 문제

• mutex나 세마포어를 사용시, 높은 우선순위의 프로세스가 낮은 우선순위 프로세스가 자원 사용을 마칠 때까지 기다려야 할 수 있다.
• 예를 들어 프로세스1과 프로세스2가 있는데, 프로세스2가 우선순위가 더 높다. 세마포어의 value는 1이라 가정해보자. 이 때 프로세스1이 먼저 수행하면서 wait를 실행하고 자원을 하나 가져갔다. 그러던 중 프로세스2가 실행된다. 우선순위가 더 높기 때문에 프로세스1의 수행은 멈추고 프로세스2가 처리된다. 그런데 이 때 wait를 하려했더니 이미 프로세스1에서 자원을 가져가 처리할 수 없다. 그에 따라 프로세스2는 대기상태가 되고 이는 프로세스1이 signal을 하기 전까지 유지된다.
• 결국 우선순위가 역전된 것이다.
• 이러한 문제는 실제로 화상 탐사선의 컴퓨터에서 발생하여 이를 원격으로 수정해 문제를 해결한바가 있다.