임계구역 문제, 세마포어, 뮤텍스에 대하여

사진출처 : 커널 모드 동기화 - 뮤텍스프로그래밍, by skensita(Programming world)


1. 임계구역 문제(Critical Section Problem)
n개의 프로세스가 동작하고 있는 시스템을 생각해봅시다, 각각의 프로세스는 임계구역(Critical Section)이라 불리는 코드 영역을 가지고 있습니다. 이 임계구역에서는 각 프로세스가 공용적으로 사용하는 변수(전역변수등)를 변경 할 수 있는 코드를 담고 있습니다. 만약 어떤 프로세스가 임계구역 내의 코드를 실행중일 때, 다른 프로세스들이 임계구역 내의 코드를 실행시킬 수 없게 한다는것이 이 개념의 목적입니다. 즉, 프로세스들이 동시에 같은 임계구역을 처리할 수 없다는것을 의미합니다. 임계구역 문제(Critical Section Problem)를 해결하기 위해, 프로세스간의 상호운용을 위해 일정한 프로토콜(규약)을 구상해야 했숩니다. 각각의 프로세스는 임계구역에 접근하기 위하여 진입을 요청해야 하며, 이러한 진입요청을 하는 코드집합을 진입구역(Entry Section)이라 합니다. 임계구역에는 탈출구역(Exit Section)이 뒤따르게 되며, 나머지 코드영역은 말그대로 나머지 구역(Remainder Section)이라 합니다. P라는 프로세스의 기본적인 구조는 아래와 같습니다. 진입구역과 탈출구역은 중요한 의미를 가지므로 굵게 표시하였습니다.

do {
ENTRY SECTION
critical section
EXIT SECTION
remainder section
} while(TRUE);


2. 세마포어(Semaphore)
임계구역 문제에는 많은 대처방안이 있으나 프로그래머가 사용하기에는 다소 복잡한 면이 있습니다. 이러한 문제를 해결하기 위하여, 세마포어(Semaphore)라는 동기화 도구를 사용할 수 있습니다. S라고 지칭할 세마포어는 정수 변수이며, 이것은 두개의 기본적인 원자함수(Atomic Operation)인 wait()와 signal()에 의해서 접근할 수 있습니다. 처음에는 wait()함수는 P함수, signal()함수는 V함수라고 정의되었으며, 각각 네덜란드어로 Proberen, Verhogen의 약어로서 실험, 증가를 의미합니다. wait()과 signal()의 정의는 다음과 같습니다. (대문자 S는 세마포어 자체를 의미합니다.)

function wait(S){
while(S<=0){} //세마포어가 0이하일 경우 계속 루프안에 갇혀있게 됨.

S--;
}

function signal(S){
S++;
}

정수변수인 세마포어의 값 수정은 wait()과 signal()에서만 이루어지며, 동시에 수행될 수 없습니다. 다시말하면, 하나의 프로세스가 세마포어값을 변경하고 있는 동안에는 다른 프로세스들은 이 값을 변경할 수 없다는 것이고, 추가로 wait(S)의 경우에는, 정수 S의 값 검사(S<=0)와 값 변경시(S--;)에는 다른 방해(Interruption)가 없이 수행되어야 합니다.이에 대한 구현에 대해서는 아래에서 따로 다룰것이며, 우선은 세마포어가 어떻게 사용되는지 알아봅시다. 

3. 세마포어의 사용

운영체제는 세마포어를 카운팅 세마포어와 이진 세마포어로 구분하기도 합니다. 카운팅 세마포어의 값은 범위에 제약이 없으나, 이진 세마포어는 0과 1만을 값으로 가질 수 있습니다. 몇몇 운영체제에서는 이진 세마포어를 상호 배타적(Mutual Exclusion)인 특성을 고려해, 뮤텍스 락(Mutex Lock)이라고 부릅니다. 이진 세마포어를 사용하여 여러개의 프로세스가 존재하는 상황에서 임계구역 문제를 해결할 수 있습니다. n개의 프로세스는 1로 초기화 된 세마포어 혹은 뮤텍스를 공유도록 설정하고 아래와 같은 코드를 갖는 프로세스들을 생각해 볼 수 있습니다.

do{
wait(mutex);
//임계구역
signal(mutex);
//나머지구역
}while(TRUE);

/*위 코드에 대한 설명을 덧붙이자면, 우선 뮤텍스 기본값이 1로 설정되어있으므로 처음 진입하는 프로세스는 wait()을 수행한 후 임계구역의 코드에 진입할 수 있다. 하지만 이와 동시에 다른 프로세스가 이 루프를 돈다고 한다면, 이미 앞에 있는 프로세스에서 wait()으로 뮤텍스 값을 0으로 만들어놓았기 때문에 wait()으로 진입하지 못하게 된다. 처음 진입한 프로세스가 임계구역에서 작업을 마치고 나면 signal()을 거쳐 나가며, signal()에서 뮤텍스 값이 다시 1으로 설정되기 때문에 아까 wait()에서 진입이 지연되던 프로세스의 진입이 허용된다. 이와같은 프로세스가 진행된다.*/

또한, 각각의 프로세스를 Pi라고 한다면, 카운팅 세마포어는 유한개의 자원에 대한 접근을 제어하는데에 사용할 수 있습니다. 자원을 사용하고자 하는 프로세스는 wait()함수를 호출하여 세마포어 값을 감소시킵니다. 만약 세마포어 값이 0으로 되어버리면 이는 곧 모든 자원을 다 사용했다는 의미를 가지며, 이때 자원을 사용하고자 하는 프로세스는 세마포어 값이 0보다 커질때까지 더이상의 작업을 멈출것입니다.(while()에서 갇힘) 세마포어는 여러가지 동기화 문제에도 사용될 수 있습니다. 동시에 작동하는 두개의 프로세스 P1, P2가 있고 각기 Code1, Code2라는 코드 부분을 가지고 있다고 가정하며, 만약 Code1이 수행 된 이후에만 Code2가 수행되어야 할 때(생산자-소비자 문제와 같은), 0으로 초기화된 세마포어를 사용하는 아래의 코드를 생각해 볼 수 있습니다(위의 1. 임계구역 문제 부분과 비교하여 보세요)

프로세스 P1에서..
Code1; 
signal(S);

프로세스 P2에서..
wait(S);
Code2;

S 세마포어가 초기값이 0으로 설정되어있기 떄문에 P1에서 signal()이 호출된(세마포어값이 증가되어 1이 된다) 이후에만 Code2가 실행될것이며, 이 시점은 이미 Code1이 수행된 이후입니다. 



===========================
흔히 말하는 공룡책은 원서만 보았지 번역판은 안봐서 거기에 있는 용어와 호환되게 번역했는지는 잘 모르겠다.. 아무튼 번역하려던 부분은 이보다 뒷부분인데 우선 이쪽을 번역해놓아야 참조하기 편할것 같아서 우선 해보았다. 그리고 일부 부분에 대하여 책의 내용에서 약간 변경한 부분도 있다. 사실 세마포어, 특히 뮤텍스는 어렵지 않은 개념이고(그냥 정수형 변수와 P, V인데..),  그림으로 설명하면 훨씬 쉬운데 P가 뭐였지 V가 뭐였지? 그래서 괜시리 어렵게 느껴진다. 뮤텍스는 변소와 열쇠(lock)의 비유를 들면 매우 직관적이다. Context Switching 등 이와 관련된 그림을 찾으려고고 했는데 간신히 찾은게 위의 사진이다. 예전에 깃발로 신호를 전송하는 행사가 진행될 때 semaphore라는 단어를 사용하길래 내가 잘못들었나? 했었는데 찾아보니 정말로 semaphore에 수기신호라는 뜻이 있어 혼자 큭큭댔던 기억이 있다.

Consider a system consisting of n processes {PQ, PI , ..., P,,~\}. Each process has a segment of code, called a critical section, in which the process may be changing common variables, updating a table, writing a file, and so on.

The important feature of the system is that, when one process is executing in its critical section, no other process is to be allowed to execute in its critical section. That is, no two processes are executing in their critical sections at the same time. The critical-section problem is to design a protocol that the processes can use to cooperate. Each process must request permission to enter its critical section. The section of code implementing this request is the entry section. The critical section may be followed by an exit section. The remaining code is the remainder section. The general structure of a typical process P, is shown in Figure 6.1. The entry section and exit section are enclosed in boxes to highlight these important segments of code.

The various hardware-based solutions to the critical-section problem (using the TestAndSetC) and SwapO instructions) presented in Section 6.4 are complicated for application programmers to use. To overcome this difficulty, we can use a synchronization tool called a semaphore. A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait () and signal (). The waitO operation was originally termed P (from the Dutch probercn, "to test"); signal () was originally called V (from verhogen, "to increment"). The definition of wait() is as follows: 

All the modifications to the integer value of the semaphore in the wait () and signal() operations must be executed indivisibly. That is, when one process modifies the semaphore value, no other process can simultaneously modify that same semaphore value. In addition, in the case of wait(S), the testing of the integer value of S (S < 0), and its possible modification (S—), must also be executed without interruption. We shall see how these operations can be implemented in Section 6.5.2; first, let us see how semaphores can be used.

 Operating systems often distinguish between counting and binary semaphores. The value of a counting semaphore can range over an unrestricted domain. The value of a binary semaphore can range only between 0 and 1. On some systems, binary semaphores are known as mutex locks, as they are locks that provide mutual exclusion. We can use binary semaphores to deal with the critical-section problem for multiple processes. The n processes share a semaphore, mutex, initialized to 1. Each process P, is organized as shown in Figure 6.9. Counting semaphores can be used to control access to a given resource consisting of a finite number of instances. The semaphore is initialized to the number of resources available. Each process that wishes to use a resource performs a wait() operation on the semaphore (thereby decrementing the count). When a process releases a resource, it performs a signal () operation (incrementing the count). When the count for the semaphore goes to 0, all resources are being used. After that, processes that wish to use a resource will block until the count becomes greater than 0. We can also use semaphores to solve various synchronization problems. For example, consider two concurrently running processes: P\ with a statement Si and Pi with a statement Si. Suppose we require that So be executed only after Si has completed. We can implement this scheme readily by letting Pi and Pi share a common semaphore synch, initialized to 0, and by inserting the statements

Operating Systems Concepts 7th Edition, Chapter 6.5