이 글은 공룡책으로 유명한 운영체제 9판을 가지고 작성한 글입니다.
다르거나 이상한 점이 있다면 댓글로 알려주시면 감사하겠습니다.
협력적 프로세스는 시스템 내에서 실행 중인 다른 프로세스의 실행에 영향을 주거나 영향을 받는 프로세스입니다. 협력적 프로세스는 논리 주소 공간(코드와 데이터)을 직접 공유하거나, 단지 파일 또는 메시지에 의해서 데이터의 공유가 허용됩니다. 전자의 경우 4장에서 논의한 스레드를 사용해 달성할 수 있습니다. 공유 데이터에 대한 동시 접근은 데이터의 비일관성을 낳을 수 있습니다. 이 장에서는, 논리 주소 공간을 공유하는 협력적 프로세스의 질서 있는 실행을 보장하여, 이를 통해 데이터의 일관성을 유지하는 다양한 메커니즘을 논의합니다.
배경
저흰 이미 프로세스가 병행하게 또는 병렬로 실행될 수 있다는 것을 알고 있습니다. 프로세스 스케줄링의 역할을 소개했고 CPU 스케줄러가 프로세스 사이에서 빠르게 오가며 각 프로세스를 실행하여 모든 프로세스를 병행 실행시킨다는 것을 설명했습니다. 이는 한 프로세스는 다른 프로세스가 스케줄되기 전에 일부분만 진행할 수 있다는 것을 의미합니다. 사실 프로세스는 명령어가 실행될 때 어느 지점에서나 인터럽트 되고, 처리 코어는 다른 프로세스의 명령어를 실행하도록 할당될 수 있습니다. 또한, 병렬 실행, 즉 다른 프로세스에 속한 두 개의 명령어 흐름이 한 순간에 다른 처리 코어에서 동시에 실행되는 방식을 소개했습니다. 본 장에서 프로세스가 병행 또는 병렬로 실행될 때 여러 프로세스가 공유하는 데이터의 무결성에 어떤 문제를 일으키는지에 대해 설명합니다.
동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라고 합니다. 위와 같은 경쟁 상황으로부터 보호하기 위해, 저흰 한 순간에 하나의 프로세스만이 변수 counter를 조작하도록 보장해야 합니다. 이러한 보장을 위해, 저희는 어떤 형태로든 프로세스들이 동기화 되도록 할 필요가 있습니다.
운영체제의 여러 부분에서 자원을 조작하기 때문에 위와 같은 상황은 빈번하게 발생합니다. 또한, 앞선 장들에서 강조한 것처럼 다중코어 시스템의 성장과 더불어 다중스레드 응용의 개발에 관한 관심이 증가하고 있고, 이러한 다중스레드 응용에서는 자원을 공유할 가능성이 매우 높은 여러 스레드가 서로 다른 처리 코어에서 병렬로 실행됩니다. 저흰 이러한 행동에서 서로 간에 영향을 주지 않기를 원합니다. 이 문제는 굉장히 중요하기에, 분 장의 많은 부분은 협력하는 프로세스들 간의 프로세스 동기화와 조정에 할애하겠습니다.
// 유한 버퍼에서의 생산자를 위한 코드
while (TRUE) {
// produce an item in nextProduced
while (counter == BUFFER_SIZE)
// do nothing
buffer[in] = nextProduced;
int = (in + 1) % BUFFER_SIZE;
counter++;
}
// 유한 버퍼에서의 소비자를 위한 코드
while (TRUE) {
while (counter == 0)
// do nothing
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter --;
// consume the item in nextConsumed
}임계구역 문제(The Critical-Section Problem)
프로세스 동기화에 관한 논의는 소위 임계구역 문제라고 불리는 문제로부터 시작합니다. n개의 프로세스 {P0 ~ Pn-1}이 있는 시스템을 고려해보면, 각 프로세스는 임계구역(critical section)이라고 부르는 코드 부분을 포함하고 있고, 그 안에서는 다른 프로세스와 공유하는 변수를 변경하거나, 테이블을 갱신하거나 파일을 쓰거나 하는 등의 작업을 수행합니다.
이 시스템의 중요한 특징은 "한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다"는 사실입니다. 즉 동시에 두 프로세스는 그들의 임계구역 안에서 실행할 수 없습니다. 임계구역 문제는 프로세스들이 협력할 때 사용할 수 있는 프로토콜을 설계하는 것입니다. 각 프로세스는 자신의 임계구역으로 진입하려면 진입 허가를 요청해야 합니다. 이러한 요청을 구현하는 코드 부분을 진입 구역(entry section)이라고 부릅니다. 임계구역 뒤에는 퇴출 구역(exit section)이 따라올 수 있습니다. 코드의 나머지 부분들은 총칭하여 나머지 구역(remainder section)이라고 부릅니다. 전형적인 프로세스 Pi의 일반적인 구조가 그림 6.1에 나와 있습니다. 진입 구역과 퇴출 구역은 중요한 코드 부분임을 강조하기 위하여 상자로 둘러 싸여 있습니다.
임계구역 문제에 대한 해결안은 다음의 세 가지 요구조건을 충족해야 합니다.
- 상호 배제(mutual exclusion) : 프로세스 Pi가 자신의 임계구역에서 실행된다면, 다른 프로세스들은 그들 자신의 임계구역에서 실행될 수 없습니다.
- 진행(progress) : 자기의 임계구역에서 실행되는 프로세스가 없고 그리고 그들 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는 지를 결정하는데 참여할 수 있으며, 이 선택은 무한정 연기될 수 없습니다. (쉽게 설명하면 빈 방에 지정된 애가 들어가려고 하는데 상관도 없는 애가 그 행위를 막는 것을 해선 안되는 뜻입니다)
- 한정된 대기(bounded waiting) : 프로세스가 자기의 임계구역에 진입하려는 요청을한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 합니다. (쉽게 설명하면 프로세스의 CS 진입은 유한시간 내에 허용되어야 합니다)
저흰 각 프로세스가 0이 아닌 속도로 실행되는 것을 가정합니다. 그러나 n개의 프로세스들 간의 상대적인 속도에 대한 가정은 하지 않습니다.
임의의 한 순간에 많은 커널 모드 프로세스들이 운영체제 안에서 활성화 될 수 있습니다. 그 결과 운영체제를 구현하는 코드(커널 코드)는 경쟁 조건이 일어나기 쉽습니다. 예로서, 시스템의 모든 열린 파일의 리스트를 유지하는 커널 자료구조를 고려해 봅시다. 이 리스트는 새 파일이 열리거나 닫히면 수정되어야 합니다(파일을 리스트에 추가하거나 리스트에서 삭제해야 합니다). 만일 두 프로세스가 동시에 파일을 열려고 한다면, 리스트에 대한 개별적인 갱신은 경쟁 조건을 일으킬 수 있습니다. 경쟁 조건이 발생하기 쉬운 다른 커널 자료구조로는 메모리 할당을 관리하는 자료구조, 프로세스 리스트를 유지하는 자료구조, 인터럽트 처리를 위한 자료구조 등이 있습니다. 운영체제에서 이러한 경쟁 조건이 발생하지 않도록 보장하는 것은 커널 개발자의 책임입니다.
운영체제 내에서 임계구역을 다루기 위해 선점형 커널, 비선점형 커널의 두 가지 일반적인 접근법이 사용됩니다. 선점형 커널은 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용합니다. 비선점형 커널은 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고 커널 모드 프로세스는 커널을 빠져 나갈 때까지 또는 봉쇄될 때까지 또는 자발적으로 CPU의 제어를 양보할 때까지 계속 수행됩니다.
분명히 비선점형 커널은 한 순간에 커널 안에서 실행 중인 프로세스는 하나 밖에 없기 때문에 커널 자료구조에 대한 경쟁 조건을 염려할 필요는 없습니다. 선점형 커널에 대해서는 동일한 주장을 할 수 없기 때문에 공유되는 커널 자료구조에서 경쟁 조건이 발생하지 않는 다는 것을 보장하도록 신중하게 설계되어야 합니다. 그러면, 왜 사람들은 선점형 커널을 비선점형 커널보다 좋아할까요? 커널 모드 프로세스가 대기 중인 프로세스에게 처리기를 양도하기 전에 오랫동안 실행할 위험이 적기 때문에 선점형 커널은 응답이 더 민첩할 수 있습니다. 선점형 커널은 실시간 프로세스가 현재 커널에서 실행 중인 프로세스를 서넞ㅁ할 수 있기 때문에 실시간 프로그래밍에 더 적합합니다.
피터슨의 해결안(Peterson's Solution)
임계구역에 대한 고전적인 소프트웨어 기반 해결책을 먼저 소개하겠습니다. 이 해결책은 Peterson's solution이라고 알려져 있습니다. 현대 컴퓨터 구조에 잘 맞다곤 할 수 없지만, 상호 배제, 진행, 한정된 대기의 요구조건을 만족할 수 있습니다.
피터슨의 해결안은 임계구역과 나머지 구역을 번갈아 가며 실행하는 두 개의 프로세스로 한정됩니다. 플로세스는 P0과 P1으로 번호를 매깁니다. 편의상 Pi라고 표현하면 Pj는 다른 프로세스를 가리키고 j는 1-i와 같습니다. 피터슨 해결안은 두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결합니다.
int turn;
boolean flag[2];변수 turn은 임계구역으로 진입할 순번을 나타냅니다. 즉 만일 turn == i이면 프로세스 Pi가 임계구역에서 실행될 수 있습니다. flg 배열은 프로세스가 임계구역으로 진입할 준비가 되었다는 것을 나타냅니다. 예를 들어 flag[i]가 참이면 이 값은 Pi가 임계구역으로 진입할 준비가 되었다는 것을 나타냅니다.
do {
flag[i] = TRUE;
turn = j;
while (flag[j] && turn ==j);
critical section
flag[i] = FALSE;
remainder section
} while (TRUE);임계구역으로 진입하기 위해서 Pi는 먼저 flag[i]를 참으로 만들고, turn을 j로 지정합니다. 이렇게 함으로써 프로세스 j는 임계구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장합니다. 만일 두 프로세스가 동시에 진입하기를 원한다면 turn은 거의 동시에 i와 j로 지정될 것입니다. 그러나 둘 중 오직 한 배정만이 지속됩니다. 다른 배정은 발생하기는 하지만 곧바로 겹쳐 쓰이게 됩니다. turn의 궁극적인 값이 둘 중 누가 먼저 임계구역으로 진입할 것인가를 결정합니다.
이제 해결책이 올바르게 동작한다는 것을 증명한다. 우리는 다음과 같은 사실을 보여야 합니다.
- 상호 배제가 제대로 지켜진다는 사실
- 진행에 대한 요구 조건을 만족한다는 사실(progress)
- 대기 시간이 한없이 길어지지 않는다는 사실(bounded waiting)
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] && turn == j) 조건으로 묶어두어 계속 공회전하도록 만드는 방법이라는 사실에 주목해야 합니다. 이 while loop가 유일한 방법이기 때문입니다. Pj가 임계구역에 들어갈 준비가 안 되었을 때는 (flag[j] == false)이고 Pi는 임계구역에 진입할 수 있습니다. Pj가 flag[j]를 trun로 지정하고 역시 자신의 while 문을 수행하게 되면 이 때 turn ==i이든지 turn == j일 것입니다. turn == i라면 Pi가 임계구역에 진입하게 되고 turn == j 라면 Pj가 임계구역에 진입하게 됩니다. 그러나 추후 Pj가 임계구역을 빠져나올 때는 Pj가 flag[j]를 재지정하여 Pi로 하여금 진입하게 만들어 줍니다. Pj가 flag[j]를 true로 재지정하고 나면 반드시 turn 값도 i로 지정해주어야 합니다. Pi는 while 문을 수행하는 동안 turn 값을 바꾸지 않기 때문에 Pi는 Pj가 지난번에 진입했다면 이번에는 자기도 한번은(따라서 대기 시간이 한없이 길어지지 않음) 들어갈 수 있게 (progress 보장) 됩니다.
Mutex Locks
임계구역 문제에 대한 하드웨어 기반 해결책(이 포스팅에선 다루지 않습니다) 복잡할 뿐 아니라 응용 프로그래머는 사용할 수가 없습니다. 대신 운영체제 설계자들은 임계구역 문제를 해결하기 위한 소프트웨어 도구들을 개발합니다. 가장 간단한 도구가 바로 mutex 락입니다. 사실 mutex라는 용어는 mutual exclusion의 축약 형태입니다. 우리는 임계구역을 보호하고 따라서 경쟁 조건을 방지하기 위해 mutex 락을 사용합니다. 즉, 프로세스는 임계구역에 들어가기 전에 반드시 락을 획득해야 하고 임계구역을 빠져 나올 때 락을 반환해야 합니다.
mutex 락은 available이라는 불린 변수를 가집니다. 이 변수 값이 락의 가용 여부를 표시합니다. 락이 가용하면 acquire() 호출은 성공하고 락은 곧 사용불가 상태가 됩니다. 사용불가 상태의 락을 획득하려고 시도하는 프로세스는 락이 반환될 때까지 봉쇄됩니다.
do {
락을 획득
임계구역
락을 반환
나머지구역
} while (true)사용 불가 상태의 락을 획득하려고 시도하는 프로세스는 락이 반환될 때까지 봉쇄됩니다.
acquire() 함수의 정의는 다음과 같습니다. release() 함수도 다음과 같습니다.
acquire() {
while (!available)
// busy wait
available = false // 임계영역 들어가고 문을 막습니다.
}
release () {
available = true // 임계영역 나오고 문을 엽니다.
}acquire() 또는 release() 함수 호출은 원자적으로 수행되어야 합니다. 따라서 mutex 락은 종종 6.4절에서 설명한 하드웨어 기법 중 하나를 사용하여 구현됩니다.
지금까지 설명한 구현 방식의 단점은 바쁜 대기(busy waiting)를 해야 한다는 점입니다. 프로세스가 임계구역에 있는 동안 임계구역에 들어가기 원하는 다른 프로세스들은 acquire() 함수를 호출하는 반복문을 계속 실행해야 합니다. 사실 이러한 유형의 mutex 락은 락이 가용해지기를 기다리면서 프로세스가 계속 회전을 하고 있기 때문에 spinlock이라고 부릅니다. 이 지속적인 반복은 많은 프로세스들이 CPU를 공유하는 실제 다중프로그래밍 시스템에서는 분명한 문제가 됩니다. 바쁜 대기는 다른 프로세스가 더 생산적인 작업에 사용할 수 있었던 CPU 사이클을 낭비하게 됩니다.
그러나 락을 기다리는 동안 상당한 시간을 소모하는 문맥교환을 전혀 필요로 하지 않는 것이 spinlock의 장점입니다. 따라서 프로세스들이 짧은 시간 동안만 락을 소유할 것이라고 예상되면 spinlock이 유용합니다. 이 spinlock은 다중 처리기 시스템에서 많이 채용되는데, 한 처리기에서 실행되는 스레드가 임계구역을 실행하는 동안, 다른 스레드는 다른 처리기에서 회전을 수행하게 됩니다.
세마포(Semaphores)
앞에서 언급한 것처럼 mutex는 일반적으로 동기화 도구의 가장 간단한 형태로 생각됩니다. 본 적렝서는 mutex와 유사하게 동작하지만 프로세스들이 자신들의 행동을 더 정교하게 동기화 할 수 있는 방법을 제공하는 강력한 도구를 설명합니다.
세마포 S는 정수 변수로서, 초기화를 제외하고는, 단지 두 개의 표준 원자적 연산 wait()와 signal()로만 접근이 가능합니다. wait() 연산은 원래 검사하다를 의미하는 네덜란드어 Proberen에서 P, 그리고 signal() 연산은 증가하다를 의미하는 Verhogen에서 V라고 지어졌습니다. wait()와 signal()의 정의는 다음과 같습니다.
wait(S) {
while (S <= 0)
// 바쁜 대기
S--;
}
signal(S) {
S++;
}wait()와 signal() 연산 시 세마포의 정수 값을 변경하는 연산은 반드시 분리되지 ㅇ낳고 수행되어야 합니다. 즉, 한 스레드가 세마포 값을 변경하면, 다른 어떤 스레드도 동시에 동일한 세모파 값을 변경할 수 없습니다. 부가하여, wait(S)의 경우, S의 정수 값을 검사하는 작업 (S <= 0)과 그에 따라 실행될 수 있는 변경(S--)하는 작업 또한 인터럽트 되지 않고 실행되어야 합니다.
세마포 사용법
운영체제는 종종 카운팅(counting)과 이진(binary) 세마포를 구분합니다. 카운팅 세마포의 값은 제한 없는 영역(domain)을 가집니다. 이진 세마포의 값은 0과 1 사이의 값만 가능합니다. 따라서 이진 세마포는 mutex 락과 유사하게 동작합니다. 사실 몇몇 시스템에서는 mutex 락을 제공하지 않고 상호 배제를 보장하기 위해 이진 세마포가 대신 사용됩니다.
그렇다면 정확하게 mutex와 binary semaphores의 차이는 무엇일까요?
가장 큰 차이는 소유권입니다. 뮤텍스의 경우 커널 객체중 유일하게 소유권 개념을 가지고 있습니다. 다른 모든 커널 객체는 소유권 개념이 없습니다.
소유권이란 해당 커널 객체가 자신을 소유하고 있는 스레드 정보를 저장하는 것입니다.
뮤텍스에선 어떤 스레드가 객체를 먼저 소유했을 때 다른 스레드가 해당 객체를 해제하려는 시도를 하면 FALSE를 우선 리턴하고 Error를 뱉어내면서 해당 객체를 해제하려고 했던 스레드가 소유권을 가지지 않다는 것으로 설정됩니다. 즉, 소유를 하고 있는 애가 소유를 한 채로 종료한 경우 모든 스레드들이 소유권을 가지지 않았다는 것으로 간주되어 데드락이 발생됩니다.
세마포의 경우엔 소유권 개념이 없기 때문에 이러한 문제가 발생하지 않습니다.
카운팅 세마포는 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용될 수 있습니다. 세마포는 가용한 자원의 개수로 초기화됩니다. 각 자원을 사용하려는 프로세스는 세마포에 wait() 연산을 수행하며, 이 때 세마포의 값은 감소됩니다. 프로세스가 자원을 방출할 때는 signal() 연산을 수행하고 세마포는 증가하게 됩니다. 세마포의 값이 0이 되면 모든 자원이 사용 중임을 나타냅니다. 이 후 자원을 사용하려는 프로세스는 세마포 값이 0보다 커질 때까지 봉쇄됩니다.
우리는 또한 다양한 동기화 문제를 해결하기 위해서 세마포를 사용할 수 있습니다. 예를 들어 P1은 S1 명령문을, P2는 S2 명령문을 병행하게 수행하려는 두 프로세스를 고려해봅시다. 또한 S2는 S1이 끝난 뒤에만 수행되어야 한다고 가정합니다. 우리는 이 문제를 P1과 P2가 세마포 synch를 공유하도록하고, synch는 0으로 초기화합니다. P1에 다음 명령문을 삽입합니다.
S1;
signa(synch);또 P2에 다음 명령문을 삽입합니다.
wait(synch);
S2;synch 값은 0으로 초기화되어 있어, P2가 S2를 수행하는 것은 P1이 signal(sync)를 호출한 후에만 가능할 것입니다. 그리고 이 호출은 S1을 실행한 후에만 가능합니다.
구현(Implementation)
mutex 락 구현은 바쁜 대기를 했어야 한다는 사실을 상기합시다. 지금 설명한 세마포 연산 wait()와 signal()의 정의 역시 같은 문제를 가지고 있습니다.
바쁜 대기를 해야 하는 필요성을 극복하기 위해서, wait()와 signal() ㅅ마포 연산의 정의를 다음과 같이 변경할 수 있습니다. 프로세스가 wait() 연산을 실행하고 세마포 값이 양수가 아닌 것을 발견하면, 프로세스는 대기해야합니다. 그러나 바쁜 대기 대신에 프로세스는 자신을 봉쇄시킬 수 있습니다. 봉쇄 연산은 프로세스를 세마포에 연관된 대기 큐에 넣고, 프로세스의 상태를 대시 강태로 전환합니다. 그 후에 제어가 CPU 스케줄러로 넘어가고, 스케줄러는 다른 프로세스를 실행하기 위해 선택하게 됩니다.
세마포 S를 대기하면서 봉쇄된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작 되어야 합니다. 프로세스는 wakeup() 연산에 의해 재시작이 되는데 이것은 프로세스의 상태를 대기상태에서 준비 완료 상태로 변경합니다. 그리고 프로세스는 준비 완료 큐에 넣어집니다.(CPU는 CPU 스케줄링 알고리즘에 따라 실행 중인 프로세스로부터 새로 준비 완료가 된 프로세스로 전환될 수도 있고 되지 않을 수도 있습니다)
이러한 정의를 따르는 세마포를 구현하기 위해, 저흰 세마포를 다음과 같이 정의합니다.
typedef struct {
int value;
struct process *list;
} semaphore;각 세마포는 한 개의 정수 value와 프로세스 리스트 list를 가집니다. 프로세스가 세마포를 기다려야 한다면, 이 프로세스를 세마포의 프로세스 리스트에 추가됩니다. signal() 연산은 프로세스 리스트에서 한 프로세스를 꺼내서 그 프로세스를 깨워줍니다.
wait 연산은 이제 다음과 같이 정의될 수 있습니다.
void wait(semaphore *S) {
S->value--;
if (S->value < 0) {
이 프로세스를 S->list에 넣는다;
block;
}
}signal() 연산은 다음과 같이 정의될 수 있습니다.
void signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
S->list로부터 하나의 프로세스 P를 꺼낸다;
wakeup(P);
}
}block() 연산은 자기를 호출한 프로세스를 중지시킵니다. wakeup(P) 연산은 봉쇄된 프로세스 P의 실행을 재개시킵니다.
이들 두 연산들은 운영체제의 기본적인 시스템 호출로 제공됩니다.
바쁜 대기를 하는 세마포의 고전적 정의에서는 세마포의 값은 음수를 가질 수 없으나, 이와 같이 구현하면 음수 값을 가질 수 있습니다. 세마포 값이 음수일 때, 그 절대 값은 세마포를 대기하고 있는 프로세스들의 수입니다. 이 사실은 wait() 연산의 구현에서 세마포 값의 감소와 검사의 순서를 바꾼 결과입니다.
대기하는 프로세스들의 리스트는 각 프로세스 제어 블록(PCB)에 있는 연결 필드에 의해 쉽게 구현될 수 있습니다. 각 세마포는 정수 값과 프로세스 제어 블록의 리스트에 대한 포인터를 갖고 있습니다. 한정된 대기를 보장하도록 리스트에 프로세스를 추가하고 삭제하는 한 가지 방법은 선입 선출 큐를 사용하는 것입니다. 세마포가 큐의 머리와 꼬리에 대한 포인터를 모두 가지게 됩니다. 그러나 일반적으로 ㅅ리스트는 임의의 큐잉 전략을 사용할 수 있습니다. 세마포를 정확하게 사용하는 것은 세마포 리스트를 위해 특정한 큐잉 전략을 사용하는 것과 무관합니다.
세마포가 원자적으로 실행되어야 한다는 것은 매우 중요합니다. 우리는 같은 세마포에 대해 두 프로세스가 동시에 wait()와 signal() 연산들을 실행할 수 없도록 반드시 보장해야합니다. 이런 상황은 임계구역 문제에 해당합니다. 단일 처리기 환경에서는, 단순히 wait()와 signal() 연산들이 실행되는 동안 인터럽트를 금지시킴으로써 간단히 해결할 수 있습니다. 이 방법은 일단 인터럽트가 금지되면, 다른 프로세스들의 명령어들이 끼어 들 수 없기 때문에 단일 처리기 환경에서는 올바르게 동작합니다. 인터럽트가 다시 가능화되고 스케줄러가 제어를 다시 얻을 수 있을 때까지 오로지 현재 수행되고 있는 프로세스만 실행됩니다.
다중 처리기 환경에서는 모든 처리기에서 인터럽트를 금지하여야만 합니다. 그렇지 않으면(다른 처리기에서 실행되는) 상이한 프로세스들의 명령어들이 임의의 방법으로 서로 끼어 들 수 있습니다. 모든 처리기에서 인터럽트를 금지시키는 매우 어려운 작업일 수 있으며, 더욱이 성능을 심각하게 감소시킵니다.
그래서 우리는 wait()와 signal() 연산의 현재 정의에서 바쁜 대기를 완전하게 제거하지 못했다는 것을 인정했습니다.
---------------------
Spinlock
P(S)
while (S<=0) do
endwhile
S <- S - 1
V(S)
S <- S + 1
---------------------
Semaphore
P(S)
if (S <= 0) enqueue()
else S <- S - 1
V(S)
S <- S + 1
if Q wakeup()
---------------------교착 상태와 기아(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은 교착 상태가 됩니다.
한 집합 내의 모든 프로세스들이 그 집합 내의 다른 프로세스만이 유발할 수 있는 사건을 기다릴 때, 이 프로세스들의 집합이 교착 상태에 있다고 말합니다. 저희가 여기서 주로 관심을 갖고 있는 사건들은 자원의 획득과 방출입니다. 다른 유형의 사건들도 교착 상태를 야기할 수 있습니다.
교착 상태와 연관된 다른 문제는 무한 봉쇄(indefinite blocking), 기아(starvvation)로서, 이것은 프로세스들이 세마포에서 무한정 대기하는 것입니다. 무한 봉쇄는 우리가 세마포와 연관된 큐에서 프로세스들을 후입 선출(LIFO) 순서로 제거할 경우 발생할 수 있습니다.
여기서 잠깐 ?!
교착상태와 기아의 차이는 뭘까요? 둘 다 자원을 사용 못하는 것으로 비슷해 보이는데 말이죠
교착상태는 두 개 이상의 프로세스가 서로가 필요한 자원을 대기하면서 결코 일어나지 않을 사건을 기다리는 상태입니다. 어찌보면 자원을 너도나도 사용할 수 있도록 자유롭게 할당한 결과가 교착상태입니다. 교착상태의 경우 하나 이상의 작업에 영향을 주기 때문에 무한 대기나 기아 상태보다 더 심각한 문제를 일으킵니다.
기아상태는 교착 상태가 자원을 자유롭게 할당한 결과라면 결코 사용할 수 없는 자원을 계속 기다리는 결과입니다. 하나의 프로세스가 stack 제일 밑 (배열 기준 0번 인덱스)에서 하염없이 기다리는 거죠
우선순위 역전(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이 자원 R의 사용을 마치면 상속받은 우선순위를 방출하고 원래의 우선순위로 되돌아갑니다. 자원 R이 이제 가용 상태가 되었기 때문에 M이 아닌 H가 다음에 실행됩니다.
고전적인 동기화 문제들(Classic Problems of Synchronization)
많은 클래스의 병행 제어(concurrency control) 문제에 대한 예로서 중요한 여러 가지의 다른 동기화 문제들을 제시할 것입니다. 이 문제들은 거의 새롭게 제안된 동기화 방법들을 검증하는 데 사용됩니다. 동기화 문제에 대한 해결책을 제시할 때 전통적으로 세마포를 사용해 왔기 때문에 저희의 해결안에서도 세마포가 사용됩니다. 그러나 이 해결책을 실제 구현할 때에는 이진 세마포 대신에 mutex 락이 사용될 수 있습니다.
유한 버퍼 문제 (The Bounded-Buffer Problem)
유한 버퍼 문제는 일반적으로 동기화 프리미티브(primitive)들의 능력을 설명하기 위해 사용됩니다. 어느 특정 구현에 국한됨 없이 이 해결 방법의 일반적인 구조를 제시합니다.
저희가 해결하려는 문제에서 소비자와 생산자는 다음과 같은 자료구조를 공유합니다.
int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0저희는 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);
// 소비자 프로세스의 구조
do {
wait(full);
wait(mutex);
...
// remove an item from buffer to nextc
...
signal(mutex);
signal(empty);
...
// consume the item in nextc
...
} while (TRUE);Readers-Writers 문제(The Readers-Writers Problem)
하나의 DB가 다수의 병행 프로세스들 간에 공유된다고 가정합시다. 이들 프로세스들 중의 일부는 데이터베이스의 내용을 읽기만 하고 어떤 프로세스들은 데이터베이스를 읽고, 쓰기를 원할 수 있습니다. 저흰 전자를 readers, 후자를 writers로 불러 이 두 가지 유형의 프로세스들을 구별합니다. 명백히, 만약 두 reader가 동시에 공유 데이터를 접근하더라도, 불행한 결과가 발생하지는 않습니다. 그러나 하나의 writer와 어떤 다른 스레드(reader 또는 writer)가 동시에 데이터베이스를 접근하면, 혼란이 야기될 수 있습니다.
이러한 문제점이 발생하지 않도록 보장하기 위해, 우리는 writer가 쓰기 작업 동안에 공유 데이터베이스에 대해 배타적 접근 권한을 가지게 할 필요가 있습니다. 이 동기화 문제를 readers-writers 문제라고 합니다. 이 문제는 처음으로 언급된 이후부터 거의 모든 새로운 동기화 프리미티브를 시험하기 위해 사용되었습니다. readers-writers 문제에는 여러가지 변형들이 있는데, 모두 우선순위와 연관된 변형들입니다. 첫 번째론 readres-writers 문제라 일컬어지는, 가장 간단한 문제에서는 writer가 공유 객체를 사용할 수 있는 허가를 아직 얻지 못했다면, 어느 reader도 기다리게 해서는 안 됩니다. 즉, reader의 우선순위가 더 높은 것입니다. 두 번째 readers-writers 문제는 일단 writer가 준비되면 가능한 한 빨리 쓰기를 수행할 것을 요구합니다. 바꿔 말해, writer가 객체에 접근하려고 기다리고 있다면, 새로운 reader들은 읽기를 시작하지 못합니다.
이들 문제에 대한 해결안이 기아를 낳을 수 있음에 유의해야 합니다. 첫 번째 경우에는 writer가 기아 상태에 도달할 수 있으며, 두 번째 경우에서는 reader가 기아할 수 있습니다. 이러한 이유 때문에, 이 문제의 다른 변형들이 제안되었습니다.
첫 번째 readers-writers 문제에 대한 해결안에서, reader 프로세스는 다음과 같은 자료 구조를 공유합니다.
// writer 프로세스의 구조
do {
wait(rw_mutex);
...
//writing is performed
...
signal(rw_mutex);
} while (true)
// reader 프로세스의 구조
do {
wait(mutex);
read count++;
if (read count == 1)
wait(rw mutex);
signal(mutex)
...
// reading is perform
...
wait(mutex)
read count--;
if (read count == 0)
signal(rw mutex)
signal(mutex);
} while (true)
// 첫 번째 문제의 reader 프로세스 구조
semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;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_mtex)을 수행하면 대기 중인 여러 reader들 혹은 대기 중인 한 개의 writer의 수행이 재개됨을 관찰할 수 있습니다. 어느 쪽을 수행할 지는 스케줄러가 결정합니다.
Reader-writer 락은 다음과 같은 상황에서 가장 유용합니다.
- 공유 데이터를 읽기만 하는 프로세스와 쓰기만 하는 스레드를 식별하기 쉬운 응용
- Writer보다 Reader가 더 많은 응용
식사하는 철학자들 문제 (The Dining-Philosophers Problem)
생각하고 먹으면서 그들의 생애를 보내는 5명의 철학자들을 고려해 봅시다. 철학자들은 원형 테이블을 공유하며, 이 테이블은 각각 한 철학자에 속하는 5개의 의자로 둘러 싸여 있습니다. 테이블 중앙에는 한 사발의 밥이 있고, 테이블에는 다섯 개의 젓가락이 놓여 있습니다. 철학자가 생각할 때는 다른 동료들과 상호 작용하지 않습니다. 때때로 철학자들은 배가 고파지고 자신에게 가장 가까이 있는 두 개의 젓가락(자신과 자신의 왼쪽 철학자 그리고 오른쪽 철학자 사이에 있는 젓가락)을 집으려고 시도합니다. 철학자는 한 번에 한 개의 젓가락만 집ㅇ을 수도 있습니다. 분명히 철학자는 이미 옆 사람의 손에 들어간 젓가락을 집을 수 는 없습니다. 배고픈 철학자가 동시에 젓가락 두 개를 집으면, 젓가락을 놓지 않고 식사를 합니다. 배고픈 철학자가 동시에 젓가락 두 개를 집으면, 젓가락을 놓지 않고 식사를 합니다. 식사를 마치면, 젓가락두 개를 모두 놓고 다시 생각하기 시작합니다.
식사하는 철학자들 문제는 고전적인 동기화 문제로 간주됩니다. 그 이유는 실용적으로 중요하거나 혹은 컴퓨터 과학자들이 철학자를 싫어해서가 아니라 많은 부류의 병행 제어 문제의 한 예이기 때문ㅇ비니다. 그것은 교착 상태와 기아를 발생시키지 않고 여러 스레드에게 여러 자원을 할당해야 할 필요를 단순하게 표현한 것입니다.
한 가지 간단한 해결책은 각 젓가락을 하나의 세마포로 표현하는 것입니다. 철학자는 그 세마포에 wait() 연산을 실행하여 젓가락을 집으려고 시도합니다. 그는 또한 해당 세마포에 signal() 연산을 실행함으로써 자신의 젓가락을 놓습니다. 그러므로 공유 자료는 다음과 같습니다.
semaphore chopstick[5];여기서 chopstick의 원소들은 모두 1로 초기화됩니다. 철학자 i의 구조를 아래와 같이 표현할 수 있습니다.
do {
wait(choopstick[i]);
wait(chopstick[(i+1) % 5]);
// eat
signal(chopstick[i]);
signal(coopstick[(i+1) % 5];
// think
} while (TRUE);이 해결안은 인접한 두 철학자가 동시에 식사하지 않는다는 것을 보장하지만, 교착 상태를 야기할 가능성이 있기 때문에 채택할 수 없습니다. 5명의 철학자 모두가 동시에 배가 고피게 되어, 각각 자신의 왼쪽 젓가락을 잡는다고 가정해 봅시다. chopstick의 모든 원소들은 이제 0이 될 것입니다. 각 철학자가 그의 오른쪽 젓가락을 집으려고 하면 영원히 기다려야 할 것입니다.
교착 상태 문제에 대한 여러 가지 해결책들이 다음 사항들에 의해 교체될 수 있습니다.
- 최대 4명의 철학자들만이 테이블에 동시에 앉을 수 있도록 합니다.
- 한 철학자가 젓가락 두 개를 모두 집을 수 있을 때만 젓가락을 집도록 허용합니다(이렇게 하려면 철학자는 임계구역 안에서만 젓가락을 집어야 합니다)
- 비대칭 해결안을 사용합니다. 즉, 홀수 번호의 철학자는 먼저 왼쪽 젓가락을 집고 다음에 오른쪽 젓가락을 집습니다. 반면에 짝수 번호의 철학자는 오른쪽 젓가락을 집고 다음에 왼쪽 젓가락을 집습니다.
사실 여기서 부턴 이해가 잘 되지 않아서 다른 강의를 정리해서 올려보도록 하겠습니다.
이상 공룡책 6장 프로세스 동기화이었습니다. ^_^
'OS > OS' 카테고리의 다른 글
| 데드락 (Deadlock) (0) | 2019.11.07 |
|---|---|
| 프로세스 동기화 (Process Synchronization and Mutual Exclusive) (0) | 2019.11.07 |
| 공룡책 5장 CPU 스케줄링 (2) | 2019.11.06 |
| 공룡책 4장 스레드 (0) | 2019.11.03 |
| 공룡책 3장 프로세스 (0) | 2019.11.02 |
