Search
Duplicate

운영체제/ 프로세스 동기화

협력적 프로세스는 시스템 내에서 실행 중인 다른 프로세스의 실행에 영향을 주거나 영향을 받는 프로세스이다.
협력적 프로세스는 논리 주소 공간(다시 말해 코드와 데이터)을 직접 공유하거나 단지 파일 또는 메시지에 의해 데이터의 공유가 허용된다.
전자의 경우 4장에서 논의한 스레드를 사용해 달성할 수 있다. 공유 데이터에 대한 동시 접근은 데이터의 비일관성을 낳을 수 있다.

배경

우리는 이미 프로세스가 병행하게 또는 병렬로 실행될 수 있다는 것을 알고 있다. 이는 한 프로세스는 다른 프로세스가 스케줄되기 전에 일부분만 진행할 수 있다는 것을 의미한다.
사실 프로세스는 명령어가 실행될 때 어느 지점에서나 인터럽트 되고 처리 코어는 다른 프로세스의 명령어를 실행하도록 할당될 수 있다.
또한 4.2절에서 병렬 실행, 즉 다른 프로세스에 속한 두 개의 명령어 흐름이 한 순간에 다른 처리 코어에서 동시에 실행되는 방식을 소개하였다.
이러한 일들이 어떻게 발생할 수 있는지 예를 들어 보자. 3장에서 협력적인 순차적 프로세스 또는 스레드로 구성된 시스템을 설명하였다. 이들은 서로 비동기적으로 수행하면서 데이터를 공유할 가능성을 가진다.
우리는 생산자-소비자 문제를 가지고 이 모델을 설명하고 이 문제는 운영체제의 대표적인 문제 중 하나이다. 특시 3.4.1절에서 프로세스들 사이의 메모리 공유를 유한 버퍼를 이용하여 구현하였다.
다시 유한 버퍼 문제로 논의를 되돌린다. 앞서 지적한 바와 같이 우리가 제시한 해법은 동시에 최대 (BUFFER_SIZE - 1개)까지의 항목만을 버퍼에 저장할 수 있다. 이 단점을 없애기 위하여 알고리즘을 수정한다고 가정하자.
한 가지 가능성은 0으로 초기화 되어 있는 counter라는 정수형 변수를 추가하는 것이다. 버퍼에 새 항목을 추가할 떄마다 counter 값을 증가시키고 버퍼에서 한 항목을 꺼낼 때마다 counter 값을 감소시킨다. 생산자를 위한 코드는 아래처럼 수정할 수 있다.
while (TRUE) { /* produce an item in netxProduced */ while (counter == BUFFER_SIZE) ; /* do nothing */ buffer[n] = nextProduced; in = (in + 1) % BUFFER_SIZE; counter++; }
C
그리고 소비자를 위한 코드는 다음과 같이 수정할 수 있다.
while (TRUE) { while (counter ==) ; /* do nothing */ nextCnsumed = buffer[out] out = (out + 1) % BUFFER_SIZE; counter--; /* consume the item in nextConsumed */ }
C
위에 보인 생산자와 소비자 코드는 개별적으로는 올바를지라도 그들을 병행적으로 수행시키면 올바르게 동작하지 않는다. 예컨대 counter의 현재 앖은 5이고 생산자와 소비자는 couter++counter--를 병행하게 실행한다고 가정하자.
이 두 개의 명령이 수행되고 나면 counter의 값은 4나 5나 6이 된다. 유일한 올바른 결과는 counter == 5이고 이 결과는 생산자와 소비자의 실행이 분리되었을 때 얻을수 이는 결과이다.
우리는 counter 값이 잘못될 수 있다는 것을 다음과 같이 보일 수 있다. 문장 counter++는 다음과 같은 기계어(일반적인 기계에서)로 구현될 수 있음에 유의하라.
register1 = counter register1 = register1 + 1 counter = register1
Assembly
여기서 register1은 한 CPU만 접근할 수 있는(local) 레지스터 중 하나이다. 마찬가지로 문장 counter--는 다음과 같이 구현된다.
register2 = counter register2 = register2 - 1 counter = register2
Assembly
여기서 register2 역시 한 CPU만 접근할 수 있는 레지스터 중 하나이다. register1과 register2가 동일한 물리적 레지스터(이를테면 누산기)이더라도 이 레지스터의 내용은 인터럽트 처리기에 의해 메모리에 보관되었다가 다시 적재된다는 것을 상기하라.
counter++couter-- 문장을 병행하게 실행하는 것은 앞서 제시한 저수준의 문장들을 임의의 순서로 뒤섞어 순차적으로 실행하는 것과 동등하다(그러나 각 고수준 문장내에서의 순서는 유지된다) 그 중 하나는 다음과 같은 순서를 가질 수 있다.
T0: 생산자가 register1 = counter를 수행 { register1 = 5 } T1: 생산자가 register1 = register1 + 1를 수행 { register1 = 6 } T2: 소비자가 register2 = counter를 수행 { register2 = 5 } T3: 소비자가 register2 = register2 - 1를 수행 { register2 = 4 } T4: 생산자가 counter = register1를 수행 { counter = 6 } T5: 소비자가 counter = register2를 수행 { counter = 4 }
Assembly
실제로 5개의 버퍼가 채워져 있지만 4개의 버퍼가 채워져 있는 것을 의미하는 counter == 4인 부정확한 상태에 도달하게 된다. T4와 T5의 문장 순서를 바꾸면 counter == 6인 부정확한 상태에 도달한다.
이러한 부정확한 상태에 도달하는 것은 두 개의 프로세스가 동시에 변수 counter를 조작하도록 허용했기 때문이다. 이와 동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라고 한다.
위와 같은 경쟁 상황으로부터 보호하기 위해, 우리는 한 순간에 하나의 프로세스만이 변수 counter를 조작하도록 보장해야 한다. 이러한 보장을 위해 우리는 어떤 형태로든 프로세스들이 동기화 되도록 할 필요가 있다.
운영체제의 여러 부분에서 자원을 조작하기 때문에 위와 같은 상황은 빈번하게 발생한다. 게다가 앞선 장들에서 강조한 것처럼 다중코어 시스템의 성장과 더불어 다중스레드 응용의 개발에 관한 관심이 증가하고 있다.
이러한 다중스레드 응용에서는 자원을 공유할 가능성이 매우 높은 여러 스레드가 서로 다른 처리 코어에서 병렬로 실행된다. 분명히 우리는 이러한 행동에서 기인한 수정이 서로 간에 영향을 주지 않기를 원한다.

임계구역 문제

프로세스 동기화에 관한 논의는 소위 임계구역 문제라고 불리는 문제로부터 시작한다. n개의 프로세스 { P0, P1, … , Pn-1 }이 있는 시스템을 고려해 보자. 각 프로세스는 임계구역(critical section)이라고 부르는 코드 부분을 포함하고 있고 그 안에서는 다른 프로세스와 공유하는 변수를 변경하거나 테이블을 갱신하거나 팡리을 쓰거나 하는 등의 작업을 수행한다.
이 시스템의 중요한 특징은 ‘한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다’는 사실이다. 즉 동시에 두 프로세스는 그들의 임계구역 안에서 실행할 수 없다.
임계구역 문제는 프로세스들이 협력할 때 사용할 수 있는 프로코톨을 설계하는 것이다. 각 프로세스는 자신의 임계구역으로 진입하려면 진입 허가를 요청해야 한다.
이러한 요청을 구현하는 코드 부분을 진입 구역(entry section)이라고 부른다. 임계구역 뒤에는 퇴출 구역(exit section)이 따라올 수 있다. 코드의 나머지 부분들은 총칭하여 나머지 구역(ramainder section)이라고 부른다. 전형적인 프로세스 Pi의 일반적인 구조가 아래 코드에 나와있다.
do { entry section critical section exit section remainder section } while (TRUE);
C
임계구역 문제에 대한 해결안은 다음의 세 가지 요구조건을 충족해야 한다.
1.
상호 배제(mutual exclusion)
프로세스 Pi가 자기의 임계구역에서 실행된다면 다른 프로세스들은 그들 자신의 임계구역에서 실행될 수 없다.
2.
진행(progress)
자기의 임계구역에서 실행되는 프로세스가 없고 그들 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는지를 결정하는데 참여할 수 있으며, 이 선택은 무한정 연기될 수 없다.
3.
한정된 대기(bounded waiting)
프로세스가 자기의 임계구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.
우리는 각 프로세스가 0이 아닌 속도로 실행되는 것을 가정한다. 그러나 n개의 프로세스들간의 상대적인 속도에 대한 가정은 하지 않는다.
임의의 한 순간에 많은 커널 모드 프로세스들이 운영체제 안에서 활성화 될 수 있다. 그 결과 운영체제를 구현하는 코드(커널 코드)는 경쟁 조건이 발생하기 쉽다.
예컨대 시스템의 모든 열린 파일의 리스트를 유지하는 커널 자료구조를 고려해 보자. 이 리스트는 새 파일이 열리거나 닫히면 수정되어야 한다(파일을 리스트에 추가하거나 리스트에서 삭제해야 한다)
만일 두 프로세스가 동시에 파일을 열려고 한다면 리스트에 대한 개별적인 갱신은 경쟁 조건을 일으킬 수 있다. 경쟁 조건이 발생하기 쉬운 다른 커널 자료구조로는 메모리 할당을 관리하는 자료구조, 프로세스 리스트를 유지하는 자료구조, 인터럽트 처리를 위한 자료구조 등이 있다. 운영체제에서 이러한 경쟁 조건이 발생하지 않도록 보장하는 것은 커널 개발자의 책임이다.
운영체제 내에서 임계구역을 다루기 위해서 선점형 커널과 비선점형 커널의 두 가지 일반적인 접근법이 사용된다.
선점형 커널은 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용한다.
비선점형 커널은 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고 커널 모드 프로세스는 커널을 빠져 나갈 때까지 또는 봉쇄될 때까지 또는 자발적으로 CPU의 제어를 양보할 때까지 계속 수행된다.
분명히 비선점형 커널은 한 순간에 커널 안에서 실행 중인 프로세스는 하나 밖에 없기 때문에 커널 자료구조에 대한 경쟁 조건을 염려할 필요는 없다.
선점형 커널에 대해서는 동일한 주장을 할 수 없기 때문에 공유되는 커널 자료구조에서 경쟁 조건이 발생하지 않는다는 것을 보장하도록 신중하게 설계되어야 한다.
SMP 구조에서 선점형 커널을 설계하는 것은 특히 어렵다. 이 환경에서는 서로 다른 처리기의 두 프로세스가 동시에 커널 모드에 있을 수 있기 때문이다.
그러면 왜 사람들은 비선점형 커널보다 선점형 커널을 더 선호하는가?
커널 모드 프로세스가 대기 중인 프로세스에게 처리기를 양도하기 전에 오랫도안 실행할 위험이 적기 때문에 선점형 커널은 더 응답이 민첩할 수 있다. 물론 이 효과는 커널 모드 프로세스가 이런 식으로 행동하지 않도록 커널 코드를 설계하여 최소화할 수 있다.
게다가 선점형 커널은 실시간 프로세스가 현재 커널에서 실행 중인 프로세스를 선점할 수 있기 때문에 실시간 프로그래밍에 더 적당하다.

피터슨의 해결안(Peterson’s Solution)

임계구역에 대한 고전적인 소프트웨어 기반 해결책을 설명한다. 이 해결책은 Pterson’s solution이라고 알려져 있다. 현대 컴퓨터 구조가 load와 store 같은 기본적인 기계어를 수행하는 방식 때문에 Peterson’s solution이 이러한 구조에서 올바르게 실행된다고 보장할 수는 없다.
그러나 임계구역 문제를 해결하기 위한 좋은 알고리즘적인 설명을 제공하고 상호 배제, 진행, 한정된 대기의 요구조건을 중점으로 다루는 소프트웨어를 설계하는데 필요한 복잡성을 잘 설명하기 때문에 이 해결책을 제시한다.
Peterson’s solution은 임계구역과 나머지 구역을 번갈아 가며 실행하는 두 개의 프로세스로 한정된다. 프로세스는 P0과 P1로 번호 매긴다. 편의상 Pi라고 하면 Pj는 다른 프로세스를 가리키고 j는 1 - i와 같게 된다.
Peterson’s solution은 두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결한다.
int turn; boolean flag[2];
C
변수 turn은 임계구역으로 진입할 순번을 나타낸다. 만일 turn == i이면 프로세스 Pi가 임계구역에서 실행될 수 있다. flag 배열은 프로세스가 임계구역으로 진입할 준비가 되었다는 것을 나타낸다.
예컨대 flag[i]가 참이라면 이 값은 Pi가 임계구역으로 진입할 준비가 되었다는 것을 나타낸다. 데이터 구조에 대한 설며을 끝냈으므로 아래 코드에 보인 알고리즘을 설명하겠다.
do { flag[i] = TRUE; turn = j; while (flag[j] && turn == j); // critical section flag[i] = FALSE; // remainder section } while(TRUE);
C
임계구역으로 진입하기 위해 Pi는 먼저 flag[i]를 참으로 만들고, turn을 j로 지정한다. 이렇게 함으로써 프로세스 j가 임계구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장한다.
만일 두 프로세스가 동시에 진입하기를 원한다면 turn은 거의 동시에 i와 j로 지정될 것이다. 그러나 둘 중 오직 한 배정만이 지속된다. 다른 배정은 발생하기는 하지만 곧바로 겹쳐 쓰이게 된다. turn의 궁극적인 값이 둘 중 누가 먼저 임계궁겨으로 진입할 것인가를 결정한다.
이제 해결책이 올바르게 동작한다는 것을 증명한다. 우리는 다음과 같은 사실을 보여야 한다.
1.
상호 배제가 제대로 지켜진다는 사실
2.
진행에 대한 요구 조건을 만족한다는 사실
3.
대기 시간이 한없이 길어지지 않는다는 사실
1번을 증며하려면 각 Pi가 임계구역에 들어가기 위해서는 반드시 flag[j] == false이든지 아니면 turn == i 여야 함을 주목해야 한다. 두 프로세스 모두 자기 임계구역을 수행 중이라면 flag[0] == flag[1] == true로 지정해야 한다.
위 두 가지 분석을 살펴보면 P0와 P1이 모두 while 문을 동시에 성공적으로 지나가지는 못했을 것이다. 왜냐하면 turn 변수의 값은 0이든지 1 둘 중 하나여야 하지 동시에 두 값을 가질 수는 없기 때문이다.
따라서 둘 중 하나만이 예컨대 Pj만이 while을 성공적으로 지나갈 수 있었을 것이고 Pi는 turn == j 문을 한 번 이상 더 실행했어야 할 것이다. 그렇지만 그 순간에 flag[j] == true이고 turn == j인 상태는 Pj가 임계구역 안에 있을 동안에는 변하지 않는다. 따라서 상호 배제는 지켜진다.
2와 3을 증명하려면 우리는 프로세스 Pi가 임계구역에 진입 못하도록 막는 방법은 그것을 while 문에서 (flag[j] == true && turn == j) 조건으로 묶어두어 계속 공회전 하도록 만드는 방법이라는 사실에 주목하여야 한다. 이 while loop가 유일한 방법이기 때문이다.
Pj가 임계구역에 들어갈 준비가 안 되었을 때는 (flag[j] == false)이고 Pi는 임계구역에 진입할 수 있다. Pj가 flag[j]를 true로 지정하고 역시 자신의 while 문을 수행하게 되면 이 때 turn == i 이든지 turn == j일 것이다.
turn == i라면 Pi가 임계구역에 진입하게 되고 turn == j라면 Pj가 임계구역에 진입하게 된다. 그러나 추후 Pj가 임계궁겨을 빠져나올 때는 Pj가 flag[j]를 false로 재지정하여 Pi로 하여금 진입하게 만들어 준다.
Pj가 flag[j]를 true로 재지정하고 나면 반드시 turn 값도 i로 지정해주어야 한다. Pi는 while 문을 수행하는 동안 turn 값을 바꾸지 않기 땜누에 Pi는 Pj가 지난번에 진입했다면 이번에는 자기도 한 번은 (따라서 대기 시간이 한없이 길어지지 않음) 들어갈 수 있게 (progress 보장) 된다.

동기화 하드웨어

임계구역 문제에 대한 소프트웨어 기반 해결책을 설명하였다. 그러나 언급한 것과 같이 Peterson’s solution 같은 소프트웨어 기반 해결책은 현대의 컴퓨터 구조에서 올바르게 동작한다는 것을 보장하지 않는다.
다음의 논의에서 우리는 커널 프로그래머와 응용 프로그래머가 사용할 수 있는 하드웨어에서부터 소프트웨어 기반 API를 망라한 기법을 사용한 임계구역 문제에 대한 해결책을 탐구한다.
이 모든 해결책들은 락킹에 대한 가정, 즉 임계구역을 보호하기 위해 락을 사용하는 것에 기반을 둔다. 앞으로 접하면 알게 되겠지만 이러한 락을 설계하는 것은 매우 복잡한 작업이다.
우리는 많은 시스템에서 사용 가능한 간단한 하드웨어 명령어를 소개하고 그것들이 임계구역 문제의 해결책으로 얼마나 효과적으로 사용될 수 있는지를 보인다. 하드웨어 특징이 프로그래밍 작업을 더욱 쉽게 하고 시스템 효율을 향상시킬 수 있다.
임계구역 문제는 단일 처리기 환경에서는 공유 변수가 변경되는 동안 인터럽트 발생을 허용하지 않음으로써 간단히 해결할 수 있다. 이렇게 함으로써 우리는 명령어의 현재 순서가 선점 없이 순서적으로 실행됨을 확신할 수 있다.
다른 명령어가 실행될 수 없기 떄문에 공유 변수에 예측 못한 변경이 일어나지는 않는다. 비선점형 커널이 이 방법을 사용한다.
불행하게도 이 해결책은 다중 처리기 환경에서는 적용할 수 없다. 다중 처리기 상에서 인터럽트의 사용불가능화 메시지가 모든 처리기에 전달되게 하기 때문에 상당한 시간을 소비한다.
이러한 메시지 전달은 각 임계구역에 진입하는 것을 지연시켜, 시스템 효율을 떨어뜨린다. 또한 인터럽트에 의해 클록이 갱신된다면 시스템 클록에 대한 영향도 고려해야 한다.
그러므로 많은 현대 기계들은 한 워드(word)의 내용을 검사하고 변경하거나 두 워드의 내용을 원자적으로 교환할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로서 특별한 하드웨어 명령어들을 제공한다.
우리는 이들 특별한 명령어들을 사용하여 임계구역 문제를 상대적으로 간단한 방식으로 해결할 수 있다. 한 특정 기계를 위한 특정 명령어를 논의하기 보다는 test_and_set()과 compare_and_swap() 명령어를 설명함으로써 이러한 타입의 명령어들의 이면에 있는 주요 개념들을 추상화하여 설명한다.
test_and_set 명령어를 아래 코드처럼 정의할 수 있다.
중요한 특징으로는 이 명령어가 원자적(atomically)으로 실행된다는 점이다. 그러므로 만일 두 개의 test_and_set 명령어가 동시에 실행된다면(각각 다른 CPU에서), 이들은 어떤 임의의 순서로 순차적으로 실행될 것이다.
만일 기계가 test_and_set() 명령어를 지원한다면 false로 초기화되는 lock이라는 Boolean 변수를 선언하여 상호 배제를 구현할 수 있다. 이를 사용하는 프로세스 Pi의 구조가 아래 코드에 나와 있다.
// test_and_set() 명령어 정의 Boolean test_and_set(boolean *target) { boolean rv = *target; *target = true; return rv; }
C
// test_and_set() 명령어를 사용한 상호 배제 구현 do { while (test_and_set(&lock)) ; // do nothing //critical section lock = FALSE; // remainder section } while(TRUE);
C
compare_and_swap() 명령어는 test_and_set() 명령어완느 대조적으로 세 개의 피연산자를 인자로 전달받는다. compare_and_swap() 명령어가 아래 코드에 정의되어 있다. 피연산자 value는 오직 (*value == expected) 수식이 참일 때만 new_value로 지정된다.
// compare_and_swap() 명령어 정의 void compare_and_swap(int *value, int expected, int new_value) { int temp = *value; if (*value == exptected) *value = new_value; return temp; }
C
어떤 경우에든 compare_and_swap() 명령어는 언제나 value의 원래 값을 반환한다. test_and_set() 명령어처럼 compare_and_swap() 명령어는 원자적으로 실행된다.
상호배제는 다음과 같이 지켜질 수 있다. 전역 변수(lock)이 선언되고 0으로 초기화 된다. compare_and_swap()을 호출한 첫 번째 프로세스는 lock을 1로 지정할 것이다. lock의 원래 값이 expected 값과 같으므로 프로세스는 임계구역으로 들어간다.
이후의 compare_and_swap() 호출은 현재 lock의 값이 기대 값 0과 같지 않기 때문에 성공하지 못한다. 프로세스가 임계구역을 빠져 나올 때 lock을 0으로 변경하고, 다른 프로세스가 임계구역을 들어갈 수 있게 허용한다.
프로세스 Pi의 구조가 아래 코드에 나와 있다.
// compare_and_swap() 명령어를 사용한 상호 배제 구현 do { while (compare_and_swap(&lock, 0, 1) != 0) ; /* do nothing */ /* critical section */ lock = 0; /* remainder section */ } while (TRUE);
C
위의 알고리즘들은 상호 배제 조건은 만족시키지만 한정된 대기 조건을 만족시키지 못한다. 임계구역 요구 조건을 모두 만족 시키는 test_and_set() 명령어를 이용한 또 다른 알고리즘이 아래 코드에 나와 있다.
// test_and_set() 명령어를 사용한 한정된 대기 조건을 만족시키는 상호 배제 do { waiting[i] = true; key = true; while (waiting[i] && key) key = test_and_set(&lock); waiting[i] = false; // critical section j = (i + 1) % n; while ((j != i) && !waiting[j]) j = (j+1) % n; if (j == i) lock = false; else waiting[j] = false; // remainder section } while(true);
C
위 코드의 공통 데이터는 아래와 같다.
boolean waiting[n]; boolean lock;
C
이 자료구조들은 모두 false로 초기화된다. 이 알고리즘이 상호 배제 조건을 만족시킨다는 것을 증명하기 위해서는 Pi가 임계구역에 진입하는 경우가 오직 waiting[i] == false 이든지 key == false라는 사실을 주의해야 한다.
key 값은 test_and_set() 명령어를 실행했을 경우에만 false가 된다. 처음으로 test_and_set()을 실행시키는 프로세스는 key == false를 발견할 것이다. 다른 프로세스들은 모두 기다려야 한다.
변수 waiting[i]가 false가 되는 것은 다른 프로세스가 임계구역을 떠날 때 뿐이다. 이때 오직 한 개의 waiting[i]만이 false로 지정되고 따라서 상호 배제가 보장된다.
progress 조건이 만족됨을 보이기 위해서는 위의 상호 배제 논리를 여기에도 비슷하게 사용할 수 있다. 임계구역을 떠나는 프로세스는 lock을 false로 하든지 waiting[j]를 false로 한다. 어느 쪽이든 둘 다 임계구역으로 들어가고자 하는 프로세스를 진입하게 만들어 준다.
한정된 대기 조건을 만족시킴을 증명하기 위해서는 한 프로세스가 임계궁겨을 떠날 때에는 waiting 배열을 순환하면서 (i + 1, i + 2, … , n - 1, 0, … , i -1) 훑어본다는 사실에 착안하면 된다.
이처럼 순환하면서 조사하여 waiting[j] == true이면서 위 순환 순서 중 첫 번째 프로세스가 임계구역에 들어가게 된다. 따라서 임계구역에 들어가고자 하는 프로세스는 최대한 n-1회만 양보하면 들어갈 수 있다.

Mutex Locks

앞서 제시한 임계구역 문제에 대한 하드웨어 기반 해결책은 복잡할 뿐만 아니라 응용 프로그래머는 사용할 수가 없다. 대신 운영체제 설계자들은 임계구역 문제를 해결하기 위한 소프트웨어 도구들을 개발한다. 가장 간단한 도구가 바로 mutex 락이다.
사실 mutext라는 용어는 mutual exclusion의 축약 형태이다. 우리는 임계구역을 보호하고 따라서 경쟁 조건을 방지하기 위해 mutex 락을 사용한다.
즉 프로세스는 임계구역에 들어가기 전에 반드시 락을 획득해야 하고 임계구역을 빠져 나올 때 락을 반환해야 한다. 아래 코드에 설명된 것처럼 acquire() 함수가 락을 획득하고 release() 함수가 락을 반환한다.
do { // 락을 획득 // 임계구역 // 락을 반환 // 나머지 구역 } while(true);
C
불가 상태의 락을 획득하려고 시도하는 프로세스는 락이 반환될 때까지 봉쇄된다.
acquire() 함수의 정의는 다음과 같다.
acquire() { while (!available) ; /* busy wait */ available = false; }
C
release() 함수의 정의는 다음과 같다.
release() { available = true; }
C
acquire() 또는 release() 함수 호출은 원자적으로 수행되어야 한다. 따라서 mutex 락은 종종 하드웨어 기법 중 하나를 사용하여 구현된다.
지금까지 설명한 구현 방식의 단점은 바쁜 대기(busy waiting)을 해야 한다는 것이다. 프로세스가 임계구역에 있는 동안 임계구역에 들어가기 원하는 다른 프로세스들은 acquire() 함수를 호출하는 반복문을 계속 실행해야 한다.
사실 이러한 유형의 mutex 락은 락이 가용해지길 기다리면서 프로세스가 계속 회전을 하고 있기 때문에 spinlock이라고 부른다. test_and_set()과 compare_and_swap() 명령어를 설명하기 코드 예제에서도 동일한 쟁점이 발생한다.
이 지속적인 반복은 많은 프로세스들이 CPU를 공유하는 실제 다중 프로그램이 시스템에서는 분명한 문제이다. 바쁜 대기는 다른 프로세스가 더 생산적인 작업에 사용할 수 있었던 CPU 사이클을 낭비하게 된다.
그러나 락을 기다리는 동안 상당한 시간을 소모하는 문맥 교환을 전혀 필요로 하지 않는 것이 spinlock의 장점이다. 따라서 프로세스들이 짧은 시간 동안만 락을 소유할 것이라고 예상되면 spinlock이 유용하다.
spinlock은 다중 처리기 시스템에서 많이 채용되는데 한 처리기에서 실행되는 스레드가 임계구역을 실행하는 동안 다른 스레드는 다른 처리기에서 회전을 수행하게 된다.

세마포

mutex는 일반적으로 동기화 도구의 가장 간단한 형태로 생각된다. 본 절에서는 mutex와 유사하게 동작하지만 프로세스들이 자신들의 행동을 더 정교하게 동기화 할 수 있는 방법을 제공하는 강력한 도구를 설명한다.
세마포 S는 정수 변수로서, 초기화를 제외하고는 단지 두 개의 표준 원자적 연산 wait()와 signal()로만 접근이 가능하다. wait() 와 signal()의 정의는 다음과 같다.
wait(S) { while (S <= 0) ; // 바쁜 대기 S--; } signal(S) { S++; }
C
wait()와 signal() 연산 시 세마포의 정수 값을 변경하는 연산은 반드시 분리되지 않고 수행되어야 한다. 즉 한 스레드가 세마포 값을 변경하면, 다른 어떤 스레드도 동시에 동일한 값을 변경할 수 없다.
부가하여 wait(S)의 경우, S의 정수 값을 검사하는 작업(S0S \leq 0)과 그에 따라 실행될 수 있는 변경 S--하는 작업 또한 인터럽트 되지 않고 실행되어야 한다.

세마포 사용법

운영체제는 종종 카운팅(counting)과 이진(binary) 세마포를 구분한다. 카운팅 세마포의 값은 제한 없는 영역(domain)을 갖는다. 이진 세마포의 값은 0과 1 사이의 값만 가능하다. 따라서 이진 세마포는 mutex 락과 유사하게 동작한다.
사실 몇몇 시스템에서는 mutex 락을 제공하지 않고 상호 배제를 보장하기 위해 이진 세마포가 대신 사용된다.
카운팅 세마포는 유한한 개수를 가진 자원에 대한 접근을 제어하는데 사용될 수 있다. 세마포는 가용한 자원의 개수로 초기화된다.
각 자원을 사용하려는 프로세스는 세마포에 wait() 연산을 수행하며, 이때 세마포의 값은 감소된다. 프로세스가 자원을 방출할 때는 signal() 연산을 수행하고 세마포는 증가하게 된다.
세마포의 값이 0이 되면 모든 자원이 사용 중임을 나타낸다. 이후 자원을 사용하려는 프로세스는 세마포 값이 0보다 커질 때까지 봉쇄된다.
우리는 또한 다양한 동기화 문제를 해결하기 위해 세마포를 사용할 수 있다. 예컨대 P1은 S1 명령문을, P2는 S2 명령문을 병행하게 수행하려는 두 프로세스를 고려하자. 또한 S2는 S1이 끝난 뒤에만 수행해야 한다고 가정하자.
우리는 이 문제를 P1과 P2가 세마포 synch를 공유하도록 하고, synch는 0으로 초기화한다. P1에 다음 명령문을 삽입한다.
S1; signal(synch);
C
또 P2에 다음 명령문을 삽입한다.
wait(synch); S2;
C
synch 값은 0으로 초기화되어 있으므로 P2가 S2를 수행하는 것은 P1이 signal(synch)를 호출한 후에만 가능할 것이다. 그리고 이 호출은 S1을 실행한 이후에만 가능하다.

구현(Implementation)

바쁜 대기를 해야 하는 필요성을 극복하기 위해 우리는 wait()와 signal() 세마포 연산의 정의를 다음과 같이 변경할 수 있다. 프로세스가 wait() 연산을 실행하고 세마포 값이 양수가 아닌 것을 발견하면 프로세스는 반드시 대기해야 한다.
그러나 바쁜 대기 대신에 프로세스는 자신을 봉쇄시킬 수 있다. 봉쇄 연산은 프로세스를 세마포에 연관된 대기 큐에 넣고, 프로세스의 상태를 대기 상태로 전환한다. 그후에 제어가 CPU 스케줄러로 넘어가고 스케줄러는 다른 프로세스를 실행하기 위해 선택한다.
세마포 S를 대기하면서 봉쇄된 프로세스는 다른 프로세스가 signal() 연산을 실행함녀 재시작되어야 한다. 프로세스는 wakeup() 연산에 의해 재시작되는데 이것은 프로세스의 상태를 대기상태에서 준비 완료 상태로 변경한다. 그리고 프로세스는 준비 완료 큐에 넣어진다.
CPU는 CPU 스케줄링 알고리즘에 따라 실행 중인 프로세스로부터 새로 준비 완료가 된 프로세스로 전환될 수도 있고 되지 않을 수도 있다.
이러한 정의를 따르는 세마포를 구현하기 위해 우리는 세마포를 다음과 같이 정의한다.
typedef struct { int value; struct process *list; } semaphore
C
각 세마포는 한 개의 정수 value와 프로세스 리스트를 가진다. 프로세스가 세마포를 기다려야 한다면, 이 프로세스를 세마포의 프로세스 리스트에 추가된다. signal() 연산은 프로세스 리스트에서 한 프로세스를 꺼내서 그 프로세스를 깨워준다.
wait() 연산은 다음과 같이 정의될 수 있다.
void wait(semaphore *S) { S->value--; if (S->value < 0) { // 이 프로세스를 S->list에 넣는다. block(); } }
C
signal() 연산은 다음과 같이 정의될 수 있다.
void signal(semaphore *S) { S->value++; if (S->value <= 0) { // S->list로부터 하나의 프로세스 P를 꺼낸다. wakeup(P); } }
C
block() 연산은 자기를 호출한 프로세스를 중지시킨다. wakeup(P) 연산은 봉쇄된 프로세스 P의 실행을 재개시킨다. 이들 두 연산들은 운영체제의 기본적인 시스템 호출로 제공된다.
바쁜 대기를 하는 세마포의 고전적 정의에서는 세마포의 값은 음수를 가질 수 없으나, 이와 같이 구현하면 음수 값을 가질 수 있다. 세마포 값이 음수일 때, 그 절대 값은 세마포를 대기하고 있는 프로세스들의 수이다. 이 사실은 wait() 연산의 구현에서 세마포 값의 감소와 검사의 순서를 바꾼 결과이다.
대기하는 프로세스들의 리스트는 각 프로세스 제어 블록(PCB)에 있는 연결 필드에 의하여 쉽게 구현될 수 있다. 각 세마포는 정수 값과 프로세스 제어 블록의 리스트에 대한 포인터를 갖고 있다.
한정된 대기를 보장하도록 리스트에 프로세스를 추가하고 삭제하는 한 가지 방법은 선입 선출 방식 큐를 사용하는 것으로 세마포가 큐의 머리와 꼬리에 댛나 포인터를 모두 가지게 된다.
그러나 일반적으로 리스트는 임의의 큐잉 전략을 사용할 수 있다. 세마포를 정확하게 사용하는 것은 세마포 리스트를 위해 특정한 큐잉 전략을 사용하는 것과는 무관하다.
세마포가 원자적으로 실행되어야 한다는 것은 매우 중요하다. 우리는 같은 세마포에 대해 두 프로세스가 동시에 wait()와 signal() 연산들을 실행할 수 없도록 반드시 보장해야 한다.
이런 상황은 임계구역 문제에 해당한다. 단일 처리기 환경에서는 단순히 wait()와 signal() 연산들이 실행되는 동안 인터럽트를 금지시킴으로써 간단히 해결할 수 있다.
이 방법은 일단 인터럽트가 금지되면 다른 프로세스들의 명령어들이 끼어들 수 없기 때문에 단일 처리기 환경에서는 올바르게 동작한다. 인터럽트가 다시 가능화되고 스케줄러가 제어를 다시 얻을 수 있을 때까지 오로지 현재 수행되고 있는 프로세스만 실행된다.
다중 처리기 환경에서는 모든 처리기에서 인터럽트를 금지하여야만 한다. 그렇지 않으면(다른 처리기에서 실행되는) 상이한 프로세스들의 명령어들이 임의의 방법으로 서로 끼어들 수 있다.
모든 처리기에서 인터럽트를 금지시키는 매우 어려운 작업일 수 있으며 더욱이 성능을 심각하게 감소시킨다. 따라서 SMP 시스템은 wait()와 signal() 연산이 원자적으로 실행되는 것을 보장하기 위하여 compare_and_swap() 또는 spinlocks과 같은 다른 락킹 기법을 제공해야 한다.
우리는 wait()와 signal() 연산의 현재 정의에서 바쁜 대기를 완전하게 제거하지 못했다는 것을 인정하는 것이 중요하다. 오히려 우리는 바쁜 대기를 진입 코드에서 응용 프로그램의 임계구역으로 이동하였다.
더구나 우리는 바쁜 대기를 wait()와 signal() 연산들의 임계구역에만 국한 시켰으며, 이 구역은 매우 짧다. 그러므로 임계구역은 거의 항상 비어 있으며, 바쁜 대기는 드물게 발생하며, 발생하더라도 그 시간이 아주 짧다.
임계구역이 매우 길거나 또는 항상 점유되어 있는 응용 프로그램들을 갖는 전혀 다른 환경도 존재한다. 이 경우에 바쁜 대기는 극도로 비효율적이다.

교착 상태와 기아(Deadlock and Starvation)

대기 큐를 가진 세마포의 구현은 두 개 이상의 프로세스들이 오로지 대기 중인 프로세스들 중 하나에 의해서만 야기될 수 있는 사건을 무한정 기다리는 상황이 발생할 수 있다. 이 사건이란 signal() 연산의 실행을 의미한다. 이런 상태에 도달했을 때 이들 프로세스들을 교착 상태(deadlock)라고 한다.
이것을 설명하기 위해 두 개의 프로세스 P0과 P1로 구성되고 이들이 1로 지정된 세마포 S와 Q를 접근하는 시스템을 고려해 보자.
P0이 wait(S)를 실행하고, P1이 wait(Q)를 실행한다고 가정하자. P0이 wait(Q)를 실행할 때, P0는 P1이 signal(Q)를 실행할 때까지 기다려야 한다. 마찬가지로 P1이 wait(S)를 실행할 때는 P0이 signal(S)를 실행할 때까지 기다려야 한다.
이들 시그널 연산들은 실행될 수 없기 때문에 P0과 P1은 교착 상태가 된다.
한 집합 내의 모든 프로세스들이 그 집합 내의 다른 프로세스만이 유발할 수 있는 사건을 기다릴 때, 이 프로세스들의 집합이 교착 상태에 있다고 말한다. 우리가 여기서 주로 관심을 갖고 있는 사건들은 자원의 획득과 방출이다.
7장에서 보겠지만 다른 유형의 사건들도 교착 상태를 야기할 수 있다.
교착 상태와 연관된 다른 문제는 무한 봉쇄(indefinite blocking) 또는 기아(starvation)로서 이것은 프로세스들이 세마포에서 무한정 대기하는 것이다. 무한 봉쇄는 우리가 세마포와 연관된 큐에서 프로세스들을 후입 선출(last-in, first-out, LIFO) 순서로 제거할 경우 발생할 수 있다.

우선순위 역전(Priority Inversion)

높은 우선순위 프로세스가 현재 낮은 우선순위 프로세스 또는 연속된 낮은 우선순위 프로세스들에 의해 접근되고 있는 커널 데이터를 읽거나 변경할 필요가 있을 때 스케줄링의 어려움이 생기게 된다.
통상 커널 데이터는 락에 의해 보호되기 때문에 낮은 우선순위 프로세스가 자원의 사용을 마칠 때까지 높은 우선순위 프로세스가 기다려야 한다. 낮은 우선순위 프로세스가 또 다른 높은 우선순위 프로세스에 의해 선점되는 경우에 상황은 더욱 복잡해진다.
예컨대 우선순위가 L < M < H 순서인 L, M, H 세 개의 프로세스가 존재한다고 가정하자. 프로세스 H가 자원 R을 필요로 하고 이 자원은 현재 프로세스 L에 의해 접근되고 있는 상황을 생각해 보자.
보통은 프로세스 H는 L이 자원의 사용을 마칠 때까지 기다리게 된다. 그러나 이 순간 프로세스 M이 실행 가능 상태가 되고 따라서 프로세스 L을 선점한다고 가정하자.
간접적으로 낮은 우선순위의 프로세스(프로세스 M)은 프로세스 H가 L이 지원을 양도할 때까지 기다려야 하는 시간에 영향을 주게 된다.
이 문제는 우선순위 역전(priority inversion)문제로 알려져 있다. 이 문제는 셋 이상의 우선순위를 가진 시스템에서만 발생하므로 한 가지 해결 방안은 두 개의 우선순위만 가지도록 하는 것이다.
그러나 두 개의 우선순위는 대부분의 범용 운영체제에서 사용하기에는 불충분하다. 통상 이러한 시스템들은 우선순위 상속 프로토콜(priority-inheritance protocol)을 구현함으로써 이 문제를 해결한다.
이 프로토콜을 따르면, 더 높은 우선순위 프로세스가 필요로 하는 자원을 접근하는 모든 프로세스들은 문제가 된 자원의 사용이 끝날 때까지 더 높은 우선순위를 상속 받는다. 자원 사용이 끝나면 원래 우선순위로 돌아온다.
위의 예에서 우선순위 상속 프로토콜은 프로세스 L이 임시적으로 프로세스 H의 우선순위를 상속 받게 하고 따라서 프로세스 M이 L의 실행을 선점하는 것을 방지한다.
프로세스 L이 자원 R의 사용을 마치면 상속받은 우선순위를 방출하고 원래의 우선순위로 돌아간다. 자원 R이 이제 가용 상태가 되었기 때문에 프로세스 H(M이 아니라)가 다음에 실행된다.

우선순위 역전과 Mars Pathfinder

우선순위 역전은 스케줄링을 어렵게 만드는 것 이상일 수 있다. 실시간 시스템과 같이 엄격한 시간 제약을 가지는 시스템에서 우선순위 역전은 프로세스가 작업을 완료하는데 소요되는 시간이 정해진 시간 제약보다 길어지게 할 수 있다. 이런 일이 벌어지면 다른 고장이 종속적으로 발생하여 시스템 고장으로 이어지게 된다.
실험을 수행하기 위해 1997년 탐사로봇 Sojourner를 화성에 착륙시킨 NASA 우주 탐사선 Mard Pathfinder를 생각해 보자. Sojourner가 동작을 시작한 직후에 빈번한 컴퓨터 리셋이 발생했다. 매 리셋은 통신 장비를 포함한 모든 하드웨어와 소프트웨어를 초기화 하였다. 만일 문제가 해결되지 않았다면 Sojourner는 임무를 실패했을 것이다.
문제는 bc_dist라는 높은 우선순위 태스크가 예상 시간보다 더 오랜 시간이 걸려 작업을 완료했기 때문에 발생했다. 이 태스크는 ASI/MET 라는 낮은 우선순위 태스크가 보유하고 있는 공유자원을 기다려야 하는 상황이었고, 이 ASI/MET 태스크는 여러 중간 우선순위 작업들에 의해 선점되었다.
bc_dist 태스크는 공유자원을 기다리느라 정지되는 상황이 반복되고 결국 bc_sched 태스크가 문제를 발견하고 리셋을 수행하게 된 것이다. Sojourner는 전형적인 우선순위 역전 현상으로 고생한 것이다.
Sojourner의 운영체제는 VxWorks 실시간 운영체제였는데, 모든 세마포에 대해 우선순위 상속을 활성화하는 전역 변수를 가지고 있었다. 검증 후에 Sojourner의 변수가 세트되었고 문제는 해결되었다.

고전적인 동기화 문제들

유한 버퍼 문제(The Bounded-Buffer Problem)

유한 버퍼 문제는 6.1절에서 소개하였다. 이 문제는 일반적으로 동기화 프리미티브(primitive)들의 능력을 설명하기 위해 사용된다. 어느 특정 구현에 국한됨 없이 이 해결 방법의 일반적인 구조를 제시한다.
우리가 해결하려는 문제에서 소비자와 생산자는 다음과 같은 자료구조를 공유한다.
int n; semaphore mutex = 1; semaphore empty = n; semaphore full = 0;
C
우리는 n개의 버퍼들로 구성된 풀(pool)이 있으며 각 버퍼들은 한 항목(item)을 저장할 수 있다고 가정한다. mutex 세마포는 버퍼 풀을 접근하기 위한 상호 배제 기능을 제공하며 1로 초기화된다. empty와 full 세마포들은 각각 비어 있는 버퍼의 수와 꽉 찬 버프의 수를 기록한다.
세마포 empty는 n 값으로 초기화되고, 세마포 full은 0으로 초기화 된다.
아래 생산자, 소비자 코드가 있다. 생산자와 소비자 코드 간의 대칭성에 주목하라. 우리는 이 코드에서 생산자가 소비자를 위해 꽉 찬 버퍼를 생산해내고, 소비자는 생산자를 위해 비어 있는 버퍼를 생산해내는 것으로 해석할 수 있다.
// 생산자 프로세스의 구조 do { ... // produce an item in nextp ... wait(empty); wait(mutex); ... // add nextp to buffer ... signal(mutex); signal(full); } while (TRUE);
C
// 소비자 프로세스 구조 do { wait(full); wait(mutex); ... // remove an item from buffer to nextc ... signal(mutex); signal(empty); ... // consume the item in nextc ... } while (TRUE);
C

Readers-Writers 문제

하나의 데이터베이스가 다수의 병행 프로세스들 간에 공유된다고 가정하자. 이들 프로세스들 중의 일부는 데이터베이스의 내용을 읽기만 하고 어떤 프로세스들은 데이터베이스를 갱신하기를 원할 수 있다. 우리는 전자를 readers, 후자를 writers로 불러 이 두 가지 유형의 프로세스들을 구별한다.
명백히, 만약 두 reader가 동시에 공유 데이터를 접근하더라도 불행한 결과가 발생하지는 않는다. 그러나 하나의 wirter와 어떤 다른 스레드가 동시에 데이터베이스를 접근하면 혼란이 야기될 수 있다.
이러한 문제점이 발생하지 않도록 보장하기 위해 우리는 wirter가 쓰기 작업 동안에 공유 데이터베이스에 대해 배타적 접근 권한을 가지게 할 필요가 있다. 이 동기화 문제를 readers-writers 문제라고 한다. 이 문제는 처음 언급된 이후부터 거의 모든 새로운 동기화 프리미티브를 시험하기 위해 사용되었다.
readers-writers 문제에는 여러 변형들이 있는데 모두 우선순위와 연관된 변형들이다. 첫 번째 readers-writers 문제라 일컬어지는 가장 간단한 문제에서는 writer가 공유 객체를 사용할 수 있는 허가를 아직 얻지 못했다면 어느 reader도 기다리게 해서는 안 된다. 바꿔 말하면 단순히 writer가 기다리고 있기 때문에 다른 reader들이 끝날 때까지 기다리는 reader가 있어서는 안 된다.
두 번째 readers-writers 문제는 일단 writer가 준비되면 가능한 한 빨리 쓰기를 수행할 것을 요구한다. 바꿔 말해 writer가 객체를 접근하려고 기다리고 있다면 새로운 reader들은 읽기를 시작하지 못한다.
이들 문제에 대한 해결안이 기아를 낳을 수 있음에 유의해야 한다. 첫 번째 경우에는 writer가 기아할 수 있으며, 두 번째 경우에는 reader가 기아할 수 있다. 이러한 이유 때문에 이 문제의 다른 변형들이 제안되었다.
첫 번째 readers-writers 문제에 대한 해결찬에서 reader 프로세스는 다음과 같은 자료 구조를 공유한다.
semaphore rw_mutex = 1; semaphore mutex = 1; int read_count = 0;
C
mutex와 rw_mutex 세마포는 각각 1로 초기화되고 read_count는 0으로 초기화된다.
rw_mutex 세마포는 reader와 writer가 모두 공유한다. mutex 세마포는 read_count를 갱신할 때 상호 배제를 보장하기 위해 사용된다. read_count는 현재 몇 개의 프로세스들이 객체를 읽고 있는지 알려준다.
rw_mutex 세마포는 writer 들을 위한 상호 배제 세마포이다. 이것은 또한 임계구역으로 진입하는 첫 번째 reader와 임계구역을 빠져 나오는 마지막 reader에 의해서도 사용된다. 그러나 다른 reader들이 임계구역 안에 있는 동안 임계구역을 드나드는 reader들은 이것을 사용하지 않는다.
아래 코드는 writer 프로세스를 위한 코드를 보여준다. 그 다음 코드는 reader 프로세스를 보여준다. writer가 임계구역에 있고 n개의 reader들이 기다리고 있으면 한 개의 reader 만이 rw_mutex와 관련된 큐에 삽입되고, 나머지 n-1 개의 reader들은 mutex와 관련된 큐에 삽입됨을 주의하라.
또 writer가 signal(rw_mutex)을 수행하면 대기 중인 여러 reader들 혹은 대기 중인 한 개의 writer의 수행이 재개됨을 관찰할 수 있다 어느 쪽을 수행할 지는 스케줄러가 결정한다.
// Writer 프로세스 구조 do { wait(rw_mutex); ... // writing is performed ... signal(rw_mutex); } while (true);
C
do { wait(mutex); read_count++; if (read_count == 1) wait(rw_mutex); signal(mutex); ... /* reading is performed */ ... wait(mutex); read_count--; if (read_count == 0) signal(rw_mutex); signal(mutex); } while (true);
C
Readers-writers 무넺와 그 해결안들은 일반화 되어 몇몇 시스템에서는 read-writer 락을 제공한다. Reader-writer 락을 획득할 때는 읽기인지 또는 쓰기인지의 모드를 지정해야만한다.
프로세스가 공유 데이터를 읽기만 원한다면 읽기 모드의 reader-writer 락을 요청한다. 공유 데이터의 수정을 원한다면 쓰기 모드의 reader-writer 락을 요청해야 한다.
읽기 모드의 reader-writer 락은 여러 개의 프로세스들이 동시에 획득하는 것이 가능하다. writer는 공유 데이터를 배타적으로 접근해야 하기 때문에 오직 하나의 프로세스만이 쓰기 모드의 reader-writer 락을 획득할 수 있다.
Reader-writerㄹ 가은 다음과 같은 상황에서 가장 유용하다.
공유 데이터를 읽기만 하는 프로세스와 쓰기만 하는 스레드를 식별하기 쉬운 응용
Writer보다 reader의 개수가 많은 응용. 일반적으로 reader-writer 락을 설정하는데 드는 오버헤드가 세마포나 상호 배제 락을 설정할 때보다 크다. 이 오버헤드는 동시에 여러 reader가 읽게 하여 병행성을 높임으로써 상쇄할 수 있다.

식사하는 철학자들 문제(The Dining-Philosophers Problem)

원형 테이블을 공유하는 5명의 철학자가 있다. 테이블에는 다섯 개의 젓가락이 놓여 있다. 철학자가 생각할 때는 다른 동료와 상호작용하지 않지만, 배가 고파지면 자신과 가장 가까이 있는 두 개의 젓가락을 집으려고 시도한다. 철학자는 한 번에 한 개의 젓가락만 집을 수도 있다.
분명히 철학자는 이미 옆 사람의 손에 들어간 젓가락을 집을 수는 없다. 배고픈 철학자가 동시에 젓가락 두 개를 집으면 젓가락을 놓지 않고 식사를 한다. 식사를 마치면 젓가락 두 개를 모두 놓고 다시 생각하기 시작한다.
식사하는 철학자 문제는 고전적인 동기화 문제로 간주되는데, 그 이유는 많은 부류의 병행 제어 문제의 한 예이기 때문이다. 그것은 교착 상태와 기아를 발생시키지 않고 여러 스레드에게 여러 자원을 할당해야 할 필요를 단순하게 표현한 것이다.
한 가지 간단한 해결책은 각 젓가락을 하나의 세마포로 표현하는 것이다. 철학자는 그 세마포에 wait() 연산을 실행하여 젓가락을 집으려고 시도한다. 그는 또한 해당 세마포에 signal() 연산을 실행함으로써 자신의 젓가락을 놓는다. 그러므로 공유 자료는 다음과 같다.
semaphore chopstick[5];
C
여기서 chopstick의 원소들은 모두 1로 초기화 된다. 철학자 i의 구조를 아래 코드에 보였다.
do { wait(chopstick[i]); wait(chopstick[(i+1) % 5]); ... /* eat for awhile */ ... signal(chopstick[i]); signal(chopstick[(i+1) % 5]); ... /* think for awhile */ ... } while (true);
C
이 해결안은 인접한 두 철학자가 동시에 식사하지 않는다는 것을 보장하지만 교착 상태를 야기할 가능성이 있기 때문에 채택할 수 없다. 5명의 철학자가 모두 동시에 배가 고프게 되어 각각 잣니의 왼쪽 젓가락을 집는다고 가정하자.
chopstick의 모든 원소들은 이제 0이 될 것이다. 각 철학자가 그의 오른쪽 젓가락을 집으려고 하면 영원히 기다려야 할 것이다.
교착 상태 문제에 대한 여러 해결책들이 다음 사항들에 의해 교체될 수 있다.
최대 4명의 철학자들만이 테이블에 동시에 앉을 수 있도록 한다.
한 철학자가 젓가락 두 개를 모두 집을 수 있을 때만 젓가락을 집도록 허용한다 (이렇게 하려면 철학자는 임계구역 안에서만 젓가락을 집어야 한다)
비대칭 해결안을 사용한다. 즉 홀수 번호의 철학자는 먼저 왼쪽 젓가락을 잡고, 짝수 번호 철학자는 오른쪽 젓가락을 먼저 잡는다.

모니터

세마포가 프로세스들 간의 동기화를 위해 편리하고 효과적으로 쓰일 수 있지만 세마포는 자칫 잘못 사용하면 발견하기 아려운 타이밍 오류를 야기할 수 있는데, 이러한 타이밍 오류들은 특정 실행 순서로 진행되었을 때만 발생하고 이러한 순서가 항상 일어나는 것은 아니기 떄문이다.
6.1절의 생산자-소비자 문제에 대한 해결책을 설명하면서 counter를 사용할 때 이러한 오류 중 한 가지가 발생하는 것을 보았다. 그 예에서 시간적인 오류는 매우 드물게 발생하며, 설사 그 오류가 발생하더라도 오류 값이 단지 1만 차이 나기 때문에 외관상으로는 합당한 것처럼 보였다.
그렇다하더라도 우리는 이 해결책을 받아들일 수는 없다. 세마포를 도입한 이유는 바로 이러한 오류를 해결하기 위한 것이기 때문이다.
불행히도 세마포를 사용할 떄도 그와 같은 타이밍 오류는 여전히 발생할 수 있다. 어떻게 그러한 오류가 발생하는지를 알아보기 위해 임계구역 문제에 대한 세마포 해결책을 다시 생각해 보자.
모든 프로세스들은 mutex라는 세마포 변수를 공유하며 그 초시 값은 1이다. 각 프로세스는 임계궁겨에 진입하기 전에 wait(mutex)를 실행해야 하며 임계구역을 나올 때 signal(mutex)를 실행해야 한다. 만일 이 순서가 제대로 지켜지지 않으면 두 프로세스가 동시에 임계구역 안에 있을 수 있다.
다음으로 우리는 일어날 수 있는 여러 문제점들을 검토한다. 이러한 문제점들은 오직 하나의 프로세스라도 잘못 행동하면 발생하게 된다. 이러한 상황은 순수한 프로그래밍 오류 또는 비협조적인 프로그래머에 의해 야기된다.
세마포에 대한 wait()와 signal() 연산의 순서가 뒤바뀌어 아래와 같은 코드가 되었다고 하자.
signal(mutex); ... critical section ... wait(mutex);
C
이 경우에는 여러 프로세스들이 동시에 임계구역 안에서 실행될 수 있어 상호 배제 요구 조건을 위반하게 된다. 이러한 오류는 여러 프로세스들이 동시에 자신의 임계구역 안에서 실행되었을 때만 발견될 수 있다. 이러한 상황이 언제나 재현 가능하지 않다는 것에 주의하라.
프로세스가 signal(mutex)를 써야 할 곳에 잘못해서 wait(mutex)를 썼다고 가정하자.
wait(mutex); ... critical section ... wait(mutex);
C
이 경우에는 교착 상태가 발생하게 된다.
프로세스가 wait(mutex)나 signal(mutex) 또는 둘 다를 빠뜨렸다고 가정하자. 이 경우에는 상호 배제 요구조건을 위반하든지 교착 상태가 발생하게 된다.
이 예들에서 볼 수 있듯이 세마포를 이용하여 임계구역 문제를 해결할 떄 프로그래머가 세마포를 잘못 사용하면 다양한 유형의 오류가 너무나도 쉽게 발생할 수 있음을 알 수 있다. 이러한 오류들을 처리하기 위하여 연구자들은 고급 언어 구조물(constructs)들을 개발하였다.

모니터 사용법(Usage)

추상화 된 데이터형(abstract data type, ADT)은 데이터와 이 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어 보호한다. 이때 함수의 구현은 ADT의 특정한 구현과는 독립적이다. 모니터형은 모니터 내부에서 상호 배제가 보장되는 프로그래머가 정의한 일련의 연산자 집합을 포함하는 ADT이다.
모니터 형은 또한 변수들의 선언을 포함하고 있는데, 이 변수들의 값은 그 형에 해당하는 한 인스턴스의 상태를 정의한다. 그리고 모니터 형은 이 변수들을 조작할 수 있는 프로시저 또는 함수들의 본체도 같이 포함하고 있다.
모니터 구문을 소개하면 아래 코드와 같다. 모니터 형의 표현은 다른 프로세스들이 직접 사용할 수 없다. 따라서 모니터 내에 정의된 함수만이 오직 모니터 내에 지역적으로 선언된 변수들과 형식 매개변수들에만 접근할 수 있다. 마찬가지로 모니터 내의 지역 변수는 오직 지역 함수만이 접근할 수 있다.
monitor (monitor name) { // shared variable declarations procedure P1 ( ... ) { ... } procedure P2 ( ... ) { ... } ... procedure Pn ( ... ) { ... } initialization code ( ... ) { ... } }
C
모니터 구조물은 모니터 안에 항상 하나의 프로세스만이 활성화 되도록 보장해 준다. 그러므로 프로그래머들은 이와 같은 동기화 제약 조건을 명시적으로 코딩해야 할 필요가 없다. (그림 6.16)
그러나 지금까지 정의한 모니터 구조물은 어떤 동기화 기법을 모델링하는데는 충분한 능력을 제공하지 않는다. 이를 위해 우리는 부가적인 동기화 기법을 정의해야 할 필요가 있다.
이 동기화 기법들은 condition이라는 구조물로 제공될 수 있다. 자신의 주문형 동기화 기법을 작성할 필요가 있는 프로그래머는 하나 이상의 condition 형의 변수를 정의할 수 있다.
condition x, y;
C
이 condition 형 변수에 호출될 수 있는 연산은 오직 wait()와 signal()이다.
연산 x.wait(); 는 이 연산을 호출한 프로세스는 다른 프로세스가 x.signal();을 호출할 때까지 일시 중단 되어야 한다는 것을 의미한다.
x.signal() 연산은 정확히 하나의 일시중단 프로세스를 재개한다. 만약 일시중단 된 프로세스가 없으면 signal() 연산은 아무런 효과가 없다. 즉 x의 상태는 마치 연산이 전혀 실행되지 않는 것과 같다. (그림 6.17)
이것을 세마포의 signal() 연산과 대조해 보라. signal() 연산은 항상 세마포의 상태에 영향을 준다.
이제 x.signal() 연산이 프로세스 P에 의해 호출될 떄, 조건 x와 연관되어 있는 일시 중단(suspend)된 프로세스 Q가 있다고 가정해 보자. 명백히 만일 일시중단 된 스레드 Q가 실행을 재개하도록 허용된다면, signal을 보낸 스레드 P는 반드시 대기해야 한다. 그렇지 않으면 P와 Q는 모니터 안에서 동시에 활성화 된다.
그러나 두 프로세스들은 개념적으로 그들의 실행을 계속할 수 있다는 사실에 유의해야 한다. 여기에 두 가지 가능성이 존재한다.
1.
Signal and wait: P는 Q가 모니터를 떠날 때까지 기다리거나 또는 다른 조건을 기다린다.
2.
Signal and continue: Q는 P가 모니터를 떠날 때까지 기다리거나 또는 다른 조건을 기다린다.
이들 옵션 중 어느 것이든 옵션의 채택을 정당화하는 근거가 있다. 한편으로는 P가 이미 모니터 안에서 실행되고 있기 때문에 signal-and-continue 옵션을 선택하는 것이 더 합리적인 것으로 보인다.
만약 스레드 P를 계속하도록 허용한다면, Q가 재개될 때까지 Q가 기다리고 있는 논리적인 조건이 이미 참이 아닐 수도 있다.
Concurrent Pascal 언어는 이들 두 가지 선택의 절충안을 채택하였다. 스레드 P가 signal() 연산을 실행하면 즉시 모니터를 떠난다. 따라서 Q가 즉시 재개된다.
Java와 C# 등을 포함한 많은 프로그래밍 언어들은 이 절에서 설명한 모니터의 개념을 편입시켰다. Erlang 같은 다른 언어들은 유사한 기법을 사용하여 특정 형태의 병행 처리 지원을 하고 있다.

모니터를 사용한 식사하는 철학자 해결안

식사하는 철학자 문제에 대한 교착 상태가 없는 해결안을 제시함으로써 모니터 개념을 설명하기로 한다. 이 해결안은 철학자는 양쪽 젓가락 모두를 얻을 수 있을 때만 젓가락을 집을 수 있다는 제한을 강제한다.
이 해결안을 구현하려면 철학자가 처할 수 있는 세 가지 상태들을 구분할 필요가 있다. 이러한 목적으로 다음의 자료구조를 도입한다.
enum { thinking, hungry, eating } state[5];
C
철학자 i는 그의 양쪽 두 이웃이 식사하지 않을 때만 변수 state[i] = eating으로 설정할 수 있다 (조건 state[(i + 4) % 5] != eating) 그리고 (state[(i + 1) % 5] != eating) 이 성립할 때만.
또한 다음을 선언할 필요가 있다.
condition self[5];
C
self는 철학자 i가 배고프지만 자신이 원하는 젓가락을 집을 수 없을 때 젓가랏 집기를 미룰 수 있게 한다.
우리는 이제 식사하는 철학자 문제에 대한 우리의 해결안을 기술할 수 있게 되었다 젓가락의 분배는 모니터 DiningPhilosophers에 의해 제어된다. 이 모니터의 정의 아래 코드에 나와 있다.
각 철학자는 식사하기 전에 pickup() 연산을 반드시 호출해야 한다. 이 행동은 철학자 프로세스의 일시중단을 낳을 수도 있다.
연산이 성공적으로 끝나면, 철학자는 식사할 수 있다. 식사를 마친 후 철학자는 putdown() 연산을 호출한다. 따라서 철학자 i는 반드시 다음과 같은 순서로 pickup()과 putdown() 연산을 호출해야 한다.
monitor DiningPhilosopers { enum { THINKING, HUNGRY, EATING } state[5]; condition self[5]; void pickup(int i) { state[i] = HUNGRY; test(i); if (state[i] != EATING) self[i].wait(); } void putdown(int i) { state[i] = THINKING; test((i + 4) % 5); test((i + 1) % 5); } void test(int i) { if ((state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING) { state[i] = EATING; self[i].signal(); } } initialization code() { for (int i = 0; i < 5; i++) state[i] = THINKING; } }
C
이 해결안이 이웃한 두 철학자가 동시에 식사하지 않는다는 것과 교착 상태가 발생하지 않는다는 것을 보장한다는 것을 보이는 것은 쉽다. 그러나 우리는 철학자가 굶어 죽는 것이 가능하다는 것에 유의해야 한다.

세마포를 이용한 모니터의 구현(Implementing a Monitor Using Semaphores)

이제 세마포를 사용하여 모니터 기법을 구현하는 방법에 대해 살펴보도록 하겠다. 각 모니터마다 mutex라는 세마포가 정의되고 그 초기값은 1이다. 프로세스는 모니터로 들어가기 전에 wait(mutex)를 실행하고 모니터를 나온 후에 signal(mutex)를 실행해야 한다.
signaling 프로세스는 실행 재개되는 프로세스가 모니터를 떠나든지 아니면 wait() 할 때까지 그 자신이 다시 기다려야 하므로 next라는 세마포가 추가로 필요하게 되고 0으로 초기화 된다.
signaling 프로세스는 자신을 중단시키기 위해 next를 사용할 수 있다. 정수형 변수 next_count도 next에서 일시중단 되는 프로세스의 개수를 세기 위해 제공된다.
따라서 각 외부 프로시저 F는 이제 아래로 대체 된다.
wait(mutex); ... body of F ... if (next_count > 0) signal(next); else signal(mutex);
C
이와 같이 하면 모니터 안에서의 상호 배제는 보장된다.
이제 조건 변수를 세마포로 구현하는 방법에 대해 기술한다. 각 조건 x마다 x_sem이라는 세마포와 x_count라는 정수형 변수를 도입하고 둘 다 초기값을 0으로 준다. x.wait() 연산은 다음과 같이 구현할 수 있다.
x_count++; if (next_count > 0) signal(next); else signal(mutex); wait(x_sem); x_count--;
C
x.signal() 연산은 다음과 같이 구현할 수 있다.
if (x_count > 0) { next_count++; signal(x_sem); wait(next); next_count--; }
C
이것은 Hoare와 Brinch-Hansen이 정의한 모니터를 구현하는데 사용될 수 있다.

모니터 내에서 프로세스 수행 재개(Resuming Processes Within a Monitor)

이제 모니터 안에서 프로세스들이 수행 재개되는 순서로 주제를 전환한다. 조건 변수 x에 여러 프로세스들이 일시중단 되어 있고 어떤 프로세스가 x.signal() 연산을 수행했다면, 일시중단 되었던 프로세들 중 어느 프로세스가 수행 재개될 것인가를 어떻게 결정한느가?
한 가지 간단한 방법은 FCFS 순이다. 즉 가장 오래 기다렸던 프로세스가 가장 먼저 깨어나는 것이다.
그러나 많은 경우 이러한 간단한 스케줄링 기법은 충분하지 않다. 이를 위해 아래와 같은 형식의 conditional-wait 구조물을 사용할 수 있다. 이 구조물은 다음과 같은 형태를 가진다.
x.wait(c);
C
여기서 c는 정수 수식(expression)이고 이 수식은 wait() 연산이 호출될 때 값이 계산된다. c의 값은 우선순위 번호(piriority number)라고 불리며 일시중단 되는 프로세스의 이름과 함께 저장된다. x.signal()이 수행되면 가장 작은 우선순위 번호를 가진 프로세스가 다음 번에 수행 재개된다.
이 새로운 기법을 설명하기 위해 아래 코드의 ResourceAllocator 모니터를 예로 든다.
monitor ResourceAllocator { boolean busy; condition x; void acquire(int time) { if (busy) x.wait(time); busy = true; } void release() { busy = false; x.signal(); } initialization code() { busy = false; } }
C
이 모니터는 한 개의 지원을 여러 프로세스들 사이에 할당해 준다. 각 프로세스는 자원을 할당받기 원하면 그 자원을 사용할 최대 시간을 지정한다. 모니터는 이 중 가장 적은 시간을 희망한 프로세스에게 자원을 할당해 준다. 이 자원을 액세스하려는 프로세스는 아래의 순서를 따라야 한다.
R.acquire(t); ... acess the resource; ... R.realease();
C
여기서 R은 ResourceAllocator 형의 인스턴스이다.
불행하게도 모니터의 개념은 위에서 예시한 순서가 그대로 지켜지는 것을 보장해 주니는 않는다. 특히 다음과 같은 문제가 발생할 수 있다.
프로세스가 자원에 대한 허락을 받지 않고 자원을 액세스할 경우
프로세스가 자원에 대한 허락을 받은 다음 그 자원을 방출하지 않을 경우
프로세스가 자원에 대한 허락을 받지 않았는데도 그 자원을 방출할 경우
프로세스가 자원에 대한 허락을 받은 다음 방출하지 않은 상태에서 또 그 자원을 요청할 경우
사실은 동일한 문제가 세마포를 사용할 떄도 발생한다. 그리고 이 문제는 우리가 처음에 모니터 구조물으 개발하려고 했던 동기와 비슷한 유형의 문제들이다.
앞서 우리는 세마포의 올바른 사용에 대한 우려를 표명했었다. 이제 여기서는 모니터처럼 프로그래머가 정의한 고급 연산의 올바른 사용법에 대해 우려를 나타내고 있는 것이고 여기서는 컴파일러도 큰 도움을 줄 수 없다.
이 문제를 위한 한 가지 방법은 자원 액세스 연산 자체를 ResourceAllocator 모니터 내부에 두는 것이다. 그렇지만 이렇게 하면 스케줄링을 우리가 코딩한 스케줄링 방식이 아니고 모니터 자체의 스케줄러에게 맡기는 꼴이 된다.
프로세스들이 올바른 순서를 지키도록 보장하기 위해서는 ResourceAllocator 모니터와 모니터가 관리하는 자원을 사용하는 모든 프로그램을 검사해야 한다. 이 시스템이 제대로 작동하는지를 알려면 두 가지 조건을 검사해야 한다.
첫째, 프로세스들이 모니터를 정확한 순서에 맞추어 호출하는지 검사하여야 한다.
둘째, 비협조적인 프로세스가 액세스 제어 프로토콜을 사용하지 않아서 모니터가 정한 상호 배제 규칙 경로를 무시하여 공유 자원을 직접 액세스 하지 않는다는 것을 보장해야 한다.
이 두 가지 조건이 보장됐을 때에만 시간 종속적인 오류가 일어나지 않고 따라서 스케줄링이 지켜진다는 것을 보장할 수 있다.
이러한 검사가 적은 규모이며 정적인 시스템에서는 가능할지라도 규모가 큰 프로그램 또는 동적인 시스템에서는 비합리적이다. 이러한 접근 제어 문제는 오직 14장에서 설명될 추가적인 기법을 사용해야만 해결될 수 있다.

동기화 사례

Windows의 동기화(Synchronization in Windows)

Windows 운영체제는 실시간 응용과 다중 처리기 지원을 제공하는 다중 스레드 커널이다. Windows 커널이 단일처리기에서 전역 정보를 액세스할 때에는 동일한 전역 정보를 액세스할 가능성이 있는 인터럽트 핸들러가 실행되지 않도록, 인터럽트를 잠시 동안 못 걸리게 막는다.
다중 처리기 시스템에서는 Windows는 spinlock을 써서 전역 정보 액세스를 통제한다. 하지만 Windows 커널은 짧은 코드에 대해서만 spinlock을 사용한다. 게다가 효율성을 위해 스레드가 spinlock을 가지고 있는 동안에는 선점되지 않도록 보장한다.
커널 외부에서 스레드를 동기화하기 위하여 dispatcher 객체를 제공한다. 스레드는 dispatcher 객체를 사용하여 mutex 락, 세마포, event 및 타이머를 포함한 다양한 기법에 맞추어 동기화할 수 있다.
시스템은 데이터를 접근하기 위해 스레드가 mutex의 소유권을 획득한 후, 필요한 작업이 끝난 후에는 다시 반납하게 함으로써 공동으로 사용하는 데이터를 보호한다. 세마포는 6.6절에서 설명한 것처럼 동작한다.
Event는 조건 변수와 유사하다. 즉 기다리는 조건이 만족되면 기다리고 있는 스레드에게 통지해 줄 수 있다. 마지막으로 타이머는 지정한 시간이 만료되면 하나(또는 둘 이상의 )스레드에게 통지하는데 사용된다.
Dispatcher 객체는 signaled 상태에 있을 수도 있고 nonsignaled 상태에 있을 수도 있다.
signaled 상태는 ‘객체가 사용 가능하고 그 객체를 얻을 때 그 스레드가 봉쇄되지 않음’을 뜻한다.
nonsignaled 상태는 ‘객체가 사용 가능하지 않고 그 객체를 얻으려고 시도하면 그 스레드가 봉쇄됨’을 뜻한다. mutex 락 dispatcher 객체의 상태 전이를 그림 6.20에 보이고 있다.
Dispatcher 객체의 상태와 스레드 상태 간에는 관련성이 있다. 스레드가 nonsignaled 상태에 있는 dispatcher 객체 때문에 봉쇄되면 그 스레드의 상태는 준비로부터 대기 상태로 바뀌고 그 스레드는 그 객체의 대기 큐에 넣어지게 된다.
추후 dispatcher 객체의 상태가 signaled 상태로 바뀌면 커널은 그 객체를 기다리는 스레드가 있는지 여부를 알아내어 그 하나의 스레드(가능하다면 여러 스레드)를 대기 상태로부터 준비 상태로 바꾸어 다시 실행을 재개할 수 있도록 조치한다.
커널이 대기 큐로부터 선택하는 스레드의 개수는 그들이 기다리고 있는 dispatcher 객체의 유형에 달려 있다. Mutex 객체는 오직 하나의 스레드만 소유할 수 있으므로 mutex의 대기 큐에서는 오직 하나의 스레드만 선택한다.
Event 객체의 경우에는 이 사건을 기다리고 있는 모든 스레드를 선택하게 된다.
Mutex 락을 예로 들어 dispatcher 객체와 스레드 상태를 설명해 보자. 한 스레드가 nonsignaled 상태에 있는 mutex dispatcher 객체를 얻으려고 하면, 그 스레드는 일시 중단 되고 mutex 객체의 대기 큐에 넣어진다.
Mutex가 signaled 상태로 바뀌면(다른 스레드가 그 mutex의 락을 해제한 결과로) 대기 큐의 선두에서 기다리던 스레드가 대기 상태로부터 준비 상태로 바뀌고 mutex 락을 얻게 된다.
critical-section 객체는 커널의 개입 없이 획득하거나 방추할 수 있는 사용자 모드 mutex이다. 다중 처리기 시스템에서 critical-section 객체는 처음에는 spinlock을 사용하여 다른 스레드가 객체를 방출하기를 기다린다.
회전이 길어지게 되면 락을 획득하려는 프로세스는 커널 mutex를 할당하고 CPU를 양도한다. Critical-section 객체는 커널 mutex는 객체에 대한 경쟁이 발생할 때만 할당되기 때문에 특히 효율적이다. 실제로 경쟁은 거의 발생하지 않기 때문에 CPU 절약은 상당히 좋아진다.

리눅스의 동기화(Synchronization in Linux)

버전 2.6 이전 Linux는 비선점형 커널이었다. 즉 커널 모드에서 실행 중인 프로세스는 더 높은 우선순위의 프로세스가 실행 가능한 상태가 되더라도 선점될 수 없었다. 그러나 지금의 Linux 커널은 완전히 선점 가능하며 따라서 커널 모드에서 실행 중일 때에도 태스크는 선점될 수 있다.
Linux는 커널 안에서 동기화를 할 수 있는 많은 기법을 제공한다. 대부분의 컴퓨터 구조가 간단한 수학 연산의 원자적 버전으 ㄹ제공하기 때문에 Linux 커널 안에서의 가장 간단한 동기화 기법은 원자적 정수이다.
이러한 정수는 차단된 데이터 형인 atomic_t 데이터 형을 사용하여 표현된다. 이름이 암시하는 것처럼 원자적 정수를 사용하는 모든 수학 연산은 중단됨 없이 수행된다.
다음 코드는 원자적 정수 counter를 선언하고 다양한 원자적 연산을 수행하는 것을 설명하고 있다.
atomic_t counter; int value; atomic set(&counter, 5); /* counter = 5 */ atomic add(10, &counter); /* counter = counter + 10 */ atomic sub(4, &counter); /* counter = counter - 4 */ atomic inc(&counter, 5); /* counter = counter + 1 */ value = atomic read(&counter); /* value = 12 */
C
원자적 정수는 counter와 같은 정수형 변수가 갱신되어야 하는 상황에서 특히 효율적이다. 왜냐하면 원자적 연산은 락 기법을 사용할 때의 오버헤드가 필요 없기 때문이다. 그러나 이러한 종류의 상황에서만 유용하다는 제약이 있다.
발생 가능성 있는 경쟁 조건에 기여하는 많은 변수들이 존재하는 경우에는 더 정교한 락킹 도구가 사용되어야 한다.
Linux에서 커널 안의 임계구역을 보호하기 위해 mutex 락이 제공된다. 여기서 태스크는 임계구역에 들어가기 전에 mutex_lock()을 호출해야 하고 나오기 전에 mutex_unlock()을 호출해야 한다.
만일 mutex 락을 획득할 수 없으면 mutex_lock()을 호출한 태스크는 수면 상태에 놓여지고 락의 소유자가 mutex_unlock()을 호출할 때 깨어나게 된다.
Linux 커널은 커널 안에서의 락킹을 위하여 스핀 락과 세마포 및 두 락의 reader-writer 버전도 제공한다. SMP 기계에서는 기본적인 락킹 기법은 spinlock이다. 그리고 spinlock이 단지 짧은 시간 동안만 소유되도록 커널이 설계되었다.
하나의 처리 코어를 가지고 있는 임베디드 시스템과 같은 단일 처리기에서는 spinlock을 사용하는 것은 부적합하기 때문에 커널 선점을 가능하게 하고 불가능하게 하는 것으로 대치된다.
즉 단일처리기에서는 spinlock을 획득하는 것이 아니라 커널이 커널 선점을 불가능하게 한다. 그리고 spinlock을 방출하는 것이 아니라 커널은 커널 선점을 가능하게 한다. 이를 요약하면 아래와 같다.
단일 처리기
다중 처리기
커널 선점을 불능케 한다.
spin 락을 획득한다.
커널 선점을 가능케 한다.
spin 락을 방출한다.
Linux는 커널 선점을 불능케하고 가능케 하는데 흥미로운 방식을 사용한다. Linux는 preempt_disable()과 preempt_enable()이라는 두 개의 간단한 시스템 호출을 제공한다.
커널에서 실행 중인 태스크가 락을 소유하고 있을 경우에는 커널은 선점가능하지 않다. 이를 강제하기 위하여 시스템의 각 스레드는 thread_info 구조체를 가지고 있고 이 구조체에는 태스크가 소유하고 있는 락의 개수를 나타내는 preempt_count라는 카운터 필드가 있다.
락을 획득하면 preempt_count는 증가되고 락이 방출되면 이 필드는 감소된다. 현재 수행 중인 태스크의 preempt_count의 값이 0보다 크면 커널으 ㄹ선점하는 것은 안전하지 않다. 왜냐하면 이 태스크는 현재 락을 소유하고 있기 때문이다.
만일 카운트가 0이고 대기 중인 preempt_disable() 호출이 없다고 가정하면 커널은 안전하게 인터럽트 될 수 있다.
Spinlock과 커널 선점 불능 및 가능은 오직 락(또는 커널 선점 불가능)이 짧은 시간 동안만 유지될 때 사용된다. 락이 오랜 시간 동안 유지되어야 한다면 세마포 또는 mutex 락을 사용하는 것이 적절하다.

Solaris의 동기화(Synchronization in Solaris)

임계구역 접근을 제어하기 위해 Solaris는 적응적 mutex와 조건 변수, 세마포 그리고 reader-writer 락, tunrstiles을 제공한다. Solaris는 6.6절과 6.7절에서 제시한 그대로 세마포와 조건 변수를 구현한다. 여기서는 적응적 mutex(adaptive mutex)와 reader-writer 락, tunrstiles을 설명한다.
적응적 mutex(adaptive mutex)는 모든 임계 데이터 항목에 대한 접근을 보호한다. 다중 처리기 시스템에서 적응적 mutex는 스핀락(spinlock)으로 구현된 표준 세마포로 출발한다.
데이터가 잠겨 있으면, 즉 이미 사용 중이면 적응적 mutex는 두 가지 중 한 가지 일을 한다. 만일 현재 다른 CPU에서 실행 중인 스레드가 락을 소유하고 있으면 그 스레드는 락이 사용가능하게 되기를 기다리면서 공회전(spin) 한다.
왜냐하면 락을 소유하고 있는 스레드는 곧 끝날 것이기 때문이다. 만일 락을 소유하고 있는 스레드가 현재 수행 상태가 아니면 그 스레드는 봉쇄되고, 락이 방출되어 깨어날 때까지 잠자게(sleep) 된다.
락이 충분히 빨리 자유화되지 않을 때 스레드는 공회전 하는 것을 피하기 위해 잠자게(sleep) 된다. 잠자고 있는 스레드가 소유한 락은 이러한 부류에 들어 있을 가능성이 크다.
단일 처리기 시스템에서는 ㅎ나 번에 한 스레드만 수행될 수 있으므로, 락이 다른 스레드에 의해 검사되고 있으면 락을 소유하고 있는 스레드는 결코 수행되지 않는다. 그러므로 단일 처리기 시스템에서 스레드가 락을 만나게 되면 공회전하지 않고 항상 잠들게 된다.
Solaris는 짧은 코드 조각에 의해 접근되는 데이터를 보호하기 위해 적응적 mutex 방법을 사용한다. 즉 락이 수백 개 이하의 명려엉 동안만 소유된다면 mutex가 사용된다.
만일 코드 조각이 그보다 길면 공회전 대기는 극도로 비효율적이 될 것이다. 더 긴 코드 조각에 대해서는 조건 변수와 세마포가 사용된다.
만일 원하는 락을 누군가가 이미 소유하고 있으면 스레드는 대기를 호출하고 잠이 든다. 스레드가 락을 자유화할 때, 큐 안에서 다음으로 잠자고 있는 스레드에 신호를 보낸다.
스레드를 잠들게 하고 깨우는데, 그리고 문맥 교환에 연관된 추가 비용은 스핀락(spinlock)에서 대기하며 수백 개의 명령어를 낭비하는 비용보다 적다.
Readers-writers 락은 통상 읽기 전용으로만 자주 접근되는 데이터를 보호하기 위해 사용된다. 세마포는 항상 데이터 접근을 직렬화 하는 반면에 readers-writers 락은 다중 스레드가 데이터를 병행적으로 읽을 수 있게 하기 때문에 이런 상황에서는 세마포보다 효과적이다.
Readers-writers 락은 상대적으로 구현 비용이 비싸기 떄문에 역시 긴 코드 구역에 대해서만 사용된다.
Solaris는 reader-writer 락이나 적응적 mutex를 얻기 위해 기다리는 스레드들의 순서를 정해주기 위해 tunrstile을 사용한다. tunrstile이란 락 때문에 봉쇄된 스레드들을 수용하는 큐 구조이다.
예컨대 현재 한 스레드가 동기화가 필요한 객체에 대한 락을 가지고 있고, 다른 스레드들이 이 락을 얻고자 한다면 그 스레드들은 봉쇄되고 그 락에 대응하는 tunrstile에 들어가게 된다.
나중에 락이 풀리면 커널은 tunrstile에서 다음 차례로 락을 가질 스레드를 고른다. 동기화가 필요하고 한 개 이상의 스레드가 기다리게 될 수 있는 객체마다 tunrstile이 필요하다.
하지만 Solaris는 그와 같은 객체마다 모두 tunrstile을 두는 대신 커널 스레드마다 tunrstile을 가지게 한다. 스레드는 한 순간에 오직 하나의 객체에 대해서만 봉쇄되기 때문에 이 방법이 객체마다 turnstile을 두는 것보다 더 효율적이다.
동기화 객체에 봉쇄된 첫 번째 스레드를 위한 tunrstile은 객체 자신의 tunrstile이 된다. 이후 락에 봉쇄된 스레드들은 이 tunrstile에 추가된다.
첫 번째 봉쇄되었던 스레드가 락을 방출하면 이 스레드는 커널이 관리하는 자유 tunrstie 리스트에서 새로운 tunrstile을 얻게 된다. 우선순위 역전 현상을 방지하기 위해 tunrstile들은 우선순위 상속 프로토콜에 의해 구성된다.
다시 말해 현재 우선순위가 높은 스레드가 봉쇄되어 기다리고 있는 락을 낮은 우선수위의 스레드가 가지고 있다면, 낮은 우선순위를 가진 스레드는 임시로 높은 우선순위 스레드의 우선순위를 상속 받는다.
낮은 우선순위 스레드가 락을 방출할 때 이 스레드의 우선순위는 원래 우선순위로 되돌아간다.
커널에 의해 사용되는 락 기법이 사용자 수준의 스레드에도 역시 구현되어 있어 커널의 내부와 외부에서 모두 같은 유형의 락이 사용 가능한 것에 주목하라
결정적인 구현상의 차이점은 우선순위의 상속 프로토콜이다. 커널의 락 루틴은 6.6.4절에서 설명한 것처럼 스케줄러에 의해 사용되는 우선순위 상속 방법을 고수한다. 사용자 수준의 스레드 락 기법은 이러한 기능을 제공하지 않는다.
Solaris의 성능을 최적화하기 위해 개발자들은 세련되고 잘 조정된 락 방법을 사용한다. 락이 자주 사용되고 전형적으로 결정적인 커널 기능에 사용되므로 그것들의 구현과 사용을 조정함으로써 커달나 성능 향상을 얻을 수 있다.

Pthreads 동기화(Pthreads Synchronization)

Solaris에서 사용된 락킹 기법은 사용자 수준 스레드와 커널 스레드에 의해 사용 가능하지만 기본적으로 지금까지 논의된 동기화 기법은 커널 안에서 동기화를 하기 위한 기법들이다. 대조적으로 Pthreads API는 사용자 수준에서 프로그래머가 사용할 수 있으며 어떤 특정한 커널의 일부분이 아니다. 이 API는 스레드 동기화를 위하여 mutex 락, 조건 변수와 read-write 락을 제공한다.
Mutex 락은 Pthreads에서 사용할 수 있는 기본적인 동기화 기법을 대표한다. Mutex 락은 코드의 임계구역을 보호하기 위해 사용된다. 즉 스레드는 임계구역에 진입하기 전에 락을 획득하고 임계꾸역에서 나갈 때 락을 방출한다.
Pthreads는 mutex 락의 데이터 형으로 pthread_mutext_t 데이터 형을 사용한다. mutex는 pthread_mutex_init() 함수를 호출하여 생성한다.
첫 번째 매개변수는 mutex를 가리키는 포인터이다. 두 번째 매개변수로 NULL을 전달하여 속성을 디폴트 값으로 초기화 한다. 이러한 일련의 연산을 아래에서 보여준다.
#include <pthread.h> pthread_mutex_t mutex; /* create the mutex lock */ ptread mutex init(&mutex, NULL);
C
mutex는 pthread_mutex_lock()와 ptread_mutex_unlock() 함수를 통하여 각각 획득되고 방출된다. mutex 락을 획득할 수 없는 경우에 획득을 요청한 스레드는 락을 가지고 있는 스레드가 pthread_mutex_unlock() 함수를 호출할 때까지 봉쇄된다. 다음 코드는 mutex 락을 이용하여 임계구역을 보호하는 실례를 보이고 있다.
/* acquire the mutex lock */ pthread mutex lock(&mutex); /* critical section */ /* release the mutex lock */ pthread mutex unlock(&mutex);
C
모든 mutex 함수는 연산이 성공했을 경우 0 값을 반환한다. 만ㅇ리 오류가 발생한 경우는 이 함수들은 0이 아닌 오류 코드를 반환하게 된다. 조건 변수와 read-write 락은 6.8절과 6.7.2절에서 설명한 방식과 유사하게 동작한다.
세마포는 Pthreads 표준의 일부분이 POSIX SEM 확장판의 일부이지만 Pthreads를 구현하는 많은 시스템은 세마포도 함께 제공한다.
POSIX는 기명(named)과 무기명(unnamed)의 두 유형의 세마포를 명기하고 있다. 두 유형의 근본적인 차이점은 기명 세마포는 파일 시스템 안에 실제 이름을 가지고 있어서 여러 관계 없는 프로세스들이 공유할 수 있다는 것이다. 무기명 세마포는 같은 프로세스에 속한 스레드에 의해서만 사용 가능하다.
아래 코드는 무기명 세마포를 생성하고 초기화하는 sem_init() 함수의 실례를 보인다.
#include <semaphore.h> sem_t sem; /* create the semaphore and initialize it to 1 */ sem init(&sem, 0, 1);
C
sem_init() 함수는 다음 세 개의 인자를 전달 받는다.
1.
세마포를 가리키는 포인터
2.
공유 정도를 표시하는 플래그
3.
세마포의 초기값
이 예에서 플래그 값을 0으로 전달하여 이 세마포가 세마포를 생성한 프로세스에 속한 스레드만이 공유할 수 있다는 것을 표시하고 있다. 0이 아닌 값은 다른 프로세스들이 세마포에 접근할 수 있게 한다. 글고 세마포의 초기값을 1로 지정하고 있다.
6.6절에서 고전적인 wait()와 signal() 세마포 연산에 대해 설명하였다. Pthreads는 이 연산의 이름을 각각 sem_wait()와 sem_post()이라고 한다. 다음 예제는 위에서 생성한 세마포를 사용하여 임계궁겨을 보호하고 있는 예이다.
/* acquire the semaphore */ sem wait(&sem); /* critical section */ /* release the semaphore */ sem post(&sem);
C
mutex 락과 마찬가지로 모든 세마포 함수는 성공했을 경우 0을 반환하고 오류 조건이 발생한 경우 0이 아닌 값을 반환한다.
Pthreads API는 spinlock과 같은 추갖거인 확장판을 가지고 있지만 이런 모든 확장판이 모든 구현에서 사용 가능하지 않다는 것을 주의해야 한다.

대체 방안들

다중코어 시스템의 등장과 함께 이러한 여러 처리 코어의 이점을 극대화 할 수 있는 다중 스레드 응용 개발에 관한 압력이 증가하게 되었다. 그러나 다중 스레드 응용은 경쟁 조건과 교착 상태에 관한 위험을 증가시킨다.
전통적으로 mutex 락, 세마포와 모니터 같은 기법들이 이러한 쟁점을 해결하기 위해 사용되어 왔으나 처리 코어의 개수가 증가할 수록 경쟁 조건과 교착 상태 위험이 없는 다중 스레드 응용을 설계하는 작업은 점점 더 어려워지고 있다.

트랜잭션 메모리(Transactional Memory)

컴퓨터 과학 분야에서 매우 자주 한 연구 분야의 아이디어 다른 분야의 문제를 해결하는데 사용되곤 한다. 예컨대 트랜잭션 메모리의 개념은 데이터베이스 이론 분야에서 출발한 아이디어지만 프로세스 동기화 전략을 제공한다.
메모리 트랜잭션은 메모리 읽기와 쓰기 연산의 원자적인 연속적 순서이다. 한 트랜잭션의 모든 연산이 완수되면 메모리 트랜잭션은 확정(commit) 된다.
그렇지 않다면 그 시점까지 완수된 모든 연산들은 취소되고 트랜잭션 시작 이전의 상태로 되돌려야(roll-back) 한다.
트랜잭션 메모리의 이점을 활용하기 위해서는 프로그래밍 언어에 이를 위한 새로운 기능을 추가해야 한다.
다음 예를 보자. 공유 데이터를 수정하는 update() 함수가 있다고 가정하자. 전통적으로 이 함수는 다음과 같이 mutex 락 또는 세마포를 사용하여 구현된다.
update() { acquire(); /* 공유 데이터 변경 */ release(); }
C
그러나 락과 세마포 같은 동기화 기법을 사용하는 것은 교착상태와 같은 많은 잠재적인 문제를 야기할 수 있다. 또한 스레드의 개수가 증가할수록 락을 소유하기 위한 스레드의 경쟁 수준이 매우 높아지므로 전통적인 락킹 기법은 규모 적응성을 보이지 않는다.
전통적인 기법에 대한 대안으로 트랜잭션 메모리의 이점을 취할 수 있는 새로운 기능을 프로그래밍 언어에 추가할 수 있다. 우리의 예에서 새로운 구조물 atomic{S}가 추가되었다고 가정하자. 이 구조물은 S 내의 연산이 트랜잭션으로 실행된다는 것을 보장한다. 이 기능을 이용하여 udpate() 함수를 다음과 같이 다시 작성할 수 있다.
update(){ atomic { /* 공유 데이터 변경 */ } }
C
락 대신 이러한 기법을 사용하는 이점은 개발자가 아니라 트랜잭션 메모리 시스템이 원자성을 보장할 책임이 있다는 것이다. 또한 락이 전혀 사용되지 않기 때문에 교착 상태가 발생하는 것이 불가능하다.
게다가 트랜잭션 메모리 시스템은 원자적 블록 내에서 공유 변수에 대한 병행 읽기 연산과 같은 병행 실행될 수 있는 명령문들을 구별할 수 있다.
물론 프로그래머가 이 명령문을 식별하여 reader-writer 락을 사용할 수도 있지만 응용의 스레드 개수가 증가함에 따라 점점 더 어려워진다.
트랜잭션 메모리는 소프트웨어 또는 하드웨어로 구현될 수 있다. 이름이 나타내는 것처럼 소프트웨어 트랜잭션 메모리(STM)는 특별한 하드웨어 필요 없이 소프트웨어만으로 구현된다. STM은 트랜잭션 블록 안에 검사 코드를 삽입함으로써 동작한다.
이 코드는 컴파일러에 의해 삽입되어 명령문들이 동시에 실행될 수 있는 지점과 저수준 락킹이 필요한 지점을 검사함으로써 각 트랜잭션을 관리한다.
하드웨어 트랜잭션 메모리(작은 HTM) 개별 처리기 캐시에 존재하는 공유 데이터의 충돌을 해결하고 관리하기 위하여 하드웨어 캐시 계층 구조와 캐시 일관성 프로토콜을 사용한다.
HTM은 코드 계측이 필요 없고 따라서 STM 보다 적은 오버헤드를 가진다. 그러나 기존의 캐시 계층 구조와 캐시 일관성 프로토콜으 ㄹ트랜잭션 메모리를 지원하기 위해 변경해야 한다.
트랝개션 메모리는 널리 구현되지 않고 연구만 해 왔으나 다중코어 시스템의 성장과 이와 관련된 병행 및 병렬 프로그래밍에 대한 관심이 학계와 상업용 소프트웨어와 하드웨어 제조업자들로 하여금 상당히 많은 연구를 하게끔 하였다.

OpenMP

4.5.2절에서 OpenMP에 대한 개관을 섦여하고 공유 메모리 환경에서 병렬 프로그램이을 위한 지원 사항에 대해 설명하였다. OpenMP는 컴파일러 디렉티브와 API로 구성된다는 것을 기억하기 바란다.
컴파일러 디렉티브 #pragma omp parallel 이후에 등장하는 코드는 병렬구역으로 인식되어 시스템의 처리 코어 개수만큼의 스레드에 의해 실행된다.
OpenMP가 (그리고 그와 유사한 도구들) 가지는 장점은 스레드의 생성과 관리가 OpenMP 라이브러리에 의해 처리되어 응용 개발자들은 신경 쓰지 않아도 된다는 것이다.
#pragma omp paralle 컴파일러 디렉티브와 함꼐 OpenMP는 #pragma omp critical 이라는 디렉티브를 제공한다. 이 디렉티브는 디렉티브 이후에 나오는 코드 구역을 임계구역으로 지정하여 한 번에 하나의 스레드만을 실행할 수 있게 한다.
이러한 식으로 OpenMP는 스레드가 경쟁 조건을 발생시키지 않는다는 것을 보장할 수 있도록 지원한다.
임계구역 컴파일러 디렉티브의 사용 시례로 먼저 공유 변수 counter를 가정하고 이 변수는 다음과 같은 update() 함수를 통해 변경될 수 있다.
void update(int value) { counter += value; }
C
update() 함수가 병렬구역의 일부분이거나 혹은 병렬구역 안에서 호출된다면 변수 counter에서 경쟁 조건이 발생할 가능성이 있다.
임계구역 컴파일러 디렉티브가 이 경쟁조건을 막는 용도로 사용될 수 있으며 사용법은 다음과 같다.
void update(int value) { #pragma omp critical { counter += value; } }
C
임계구역 컴파일러 디렉티브는 이진 세마포 혹은 mutex 락처럼 동ㅈ가하여 한 순간에 오직 하나의 스레드만이 임계구역을 실행한다는 것을 보장하게 한다.
만일 어떤 스레드가 임계구역에서 실행 중일 때(즉 임계구역을 소유하고 있을 때) 다른 스레드가 임계구역에 진입하려고 한다면 소유주 스레드가 임계구역을 빠져나갈 때까지 호출 스레드는 봉쇄된다.
여러 임계구역이 사용되어야 한다면 각 임계구역은 별도의 이름을 할당받을 수 있으며 두 개 이상의 스레드가 동일한 이름을 가진 임계구역에서 동시에 활동할 수 없다는 규칙을 명시할 수 있다.
OpenMP에서 임계구역 컴파일러 디렉티브를 사용할 떄의 이점은 표준 mutex 락보다 쉽게 사용할 수 있다고 생각된다는 것이다. 그러나 응용 개발자가 가능한 경쟁 조건을 직접 발견해 내야만 하고 컴파일러 디렉티브를 이용하여 공유 메모리를 직접 보호해야 한다는 것이 단점이다.
추가적으로 임계구역 컴파일러 디렉티브는 mutex 락처럼 동작하기 때문에 두 개 이상의 임계구역이 관여되었을 때 여전히 교착상태가 발생할 수 있다.

함수형 프로그래밍 언어

C, C++, Java, C# 은 명령어 혹은 절차형 언어라고 한다. 명령형 언어는 상태에 기반을 둔 알고리즘을 구현하는데 사용된다. 이러한 언어에서 알고리즘의 흐름은 올바른 동작에 필수적이고 상태는 변수와 다른 자료구조를 통해서 표현된다.
물론 변수는 시간이 지남에 따라 다른 값을 배정받을 수 있기 때문에 프로그램 상태는 변경가능하다.
다중 코어 시스템에서 병행 및 병렬 프로그램이이 각광 받으면서 함수형 프로그래밍 언어에 대한 관심도 커지고 있다. 함수형 프로그래밍 언어는 명령형 언어가 제공하는 패러다임과는 많이 다른 패러다임을 따른다.
근본적인 차이는 함수형 언어는 상태를 유지하지 않는다는 것이다. 즉 변수가 정의되어 값을 배정받으면 그 값은 변경될 수 없기 때문에 변하지 않는다.
함수형 언어는 변경 가능 상태를 허용하지 않기 때문에 경쟁 조건이나 교착상태와 같은 쟁점에 대해 신경쓸 필요가 없다. 근본적으로 본 장에서 논의된 대부분의 문제는 함수형 언어에서는 존재하지 않는다.
현재 여러 함수형 언어가 사용되고 있으며 여기서는 그 중 Erlang과 Scala 두 개의 언어에 대해서만 간단히 언급한다.
Erlang 언어는 병행성과 병렬 시스템에서 실행되는 응용을 개발하기 쉬운 언어라는 점에서 큰 주목을 받았다.
Scala는 함수형 언어이면서 객체지향이기도 하다. 사실 Scala의 많은 문법은 대중적인 객체지향 언어인 Java와 C#과 유사하다.