[운영체제] 동기화 도구들: 세마포

세마포(Semaphore)

세마포는 프로세스들이 더 정교하게 동기화할 수 있는 방법을 제공하는 도구이다.

세마포 S는 정수 변수로서, 초기화를 제외하고는 두 개의 표준 원자적 연산 wait()과 signal()로만 접근할 수 있다.

wait()과 signal()의 정의는 다음과 같다.

세마포의 정수 값을 변경하는 연산은 반드시 원자적으로 수행되어야 한다.

즉, 한 프로세스가 세마포 값을 변경할 때, 다른 프로세스는 동시에 변경할 수 없다.

os는 종종 counting semaphore와 binary semaphore를 구분한다.

counting semaphore의 값은 제한이 없다.

따라서 공유 자원이 여러 개인 경우에 사용되고, 이때 공유 자원의 수로 couting semaphore가 초기화된다.

자원을 사용하려는 프로세스는 wait() 연산을 수행하고, 자원을 사용한 후에는 signal() 연산을 사용한다.

세마포의 값이 0보다 작거나 같으면 자원이 모두 사용되었다는 것을 의미하고, 세마포의 값이 0보다 커질 때까지 block 된다.

(0보다 작다는 것은 대기하고 있는 프로세스가 존재한다는 것을 의미하고, 세마포 값의 절댓값이 대기하고 있는 프로세스의 개수이다.)

binary semaphore의 값은 0 아니면 1이다.

따라서 공유 자원이 하나인 경우 사용되고, mutex lock 대신 사용할 수 있다.

세마포는 다양한 동기화 문제를 해결하기 위해서 사용된다.

예시)

P1에서 S1을 P2에서 S2를 실행하는데, S2는 S1이 끝난 뒤에만 수행되어야 한다.

위에서 정의한 세마포 연산 wait()와 signal()은 busy waiting 문제를 가진다.

이를 해결하기 위해서 wati() 연산과 signal() 연산의 정의를 다음과 같이 바꿀 수 있다.

1. 프로세스가 wait() 연산을 실행하고 세마포 값이 양수가 아닌 것을 발견하면 프로세스는 반드시 대기해야 한다.

이때, busy waiting 대신에 프로세스는 자신을 일시 중지(suspend)시킬 수 있다.

일시 중지 연산은 프로세스를 세마포에 연관된 waiting 큐에 넣고, 프로세스의 상태를 waiting state로 전환한다.

2. 세마포 S를 기다리던 일시 중지된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작된다.

프로세스는 wakeup() 연산에 의해 waiting state에서 ready state로 변경되고, ready queue에 넣어진다.

위와 같이 변경된 연산을 위해 세마포와 wait(), signal()은 다음과 같이 정의해야 한다.

세마포는 한 개의 정수 value와 프로세스 리스트 list를 가진다.

wait() 연산은 프로세스가 세마포 사용을 위해 기다리면 세마포의 프로세스 리스트에 추가한다.

signal() 연산은 기다리던 프로세스를 리스트에서 제거하고 깨운다.

프로세스를 리스트에 추가하거나 리스트에서 제거하기 위한 한 가지 방법으로 FIFO 큐를 사용할 수 있다.

이는 한정된 대기를 만족시켜준다.

이외에도 다양한 queueing 전략을 사용할 수 있다.

세마포 연산에서 가장 중요한 것이 원자적으로 실행되는 것이다.

single-core 프로세서에서는 단순히 wait(), signal() 연산이 실행될 때 인터럽트를 금지함으로써 간단히 해결할 수 있다.

multcore 프로세서에서는 모든 코어에서 인터럽트를 금지해야 하는데, 이는 성능 저하를 발생시킨다.

따라서, compare_and_swap()이나 spin lock과 같은 다른 방법을 제공한다.

세마포 구현에서 wait(), signal() 연산에서 busy waiting을 완전히 제거하지 못했다는 한계가 있다.

이는 임계구역이 매우 길거나 항상 사용되는 환경에서는 매우 비효율적이다.