공룡책 요약하기 06

2019-09-08

프로세스 동기화

프로세스 동기화에 관한 논의는 소위 임계구역(critical section) 문제라고 불리는 문제로부터 시작한다.

데이터를 공유하는 상호 협력적인 순차 프로세스들이 주어지면, 한 순간에 하나의 프로세스 또는 스레드만이 임계 영역을 사용하는 것을 보장하는 상호 배제가 제공되어야 한다.

임계 구역
임계 구역(critical section) 또는 공유변수 영역은 병렬컴퓨팅에서 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원(자료 구조 또는 장치)을 접근하는 코드의 일부를 말한다. 임계 구역은 지정된 시간이 지난 후 종료된다. 때문에 어떤 스레드(태스크 또는 프로세스)가 임계 구역에 들어가고자 한다면 지정된 시간만큼 대기해야 한다.

각 프로세스는 임계구역이라고 부르는 코드 부분을 포함하고 있고, 그 안에서는 다른 프로세스와 공유하는 변수를 변경하거나, 테이블을 갱신하거나 파일을 쓰거나 하는 등의 작업을 수행한다.

가장 중요한 특징은 한 프로세스가 자신의 임계구역에서 수행하는 동안 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다는 것이다.

각 프로세스는 자신의 임계구역에 진입하려면 진입 허가를 요청해야 한다.

이러한 요청을 구현하는 코드 부분을 진입 구역(entry section)이라 부른다.

임계구역 뒤에는 퇴출 구역(exit section)이 따라올 수 있다.

코드의 나머지 부분들은 총칭하여 나머지 구역(remainder section)이라고 부른다.

6-1

임계구역 문제에 대한 해결안은 다음의 세 가지 요구조건을 충족해야 한다.

  1. 상호 배제(mutual exclusion): 프로세스 P가 자신의 임계구역에서 실행된다면, 다른 프로세스들은 그들 자신의 임계구역에서 실행될 수 없다.

  2. 진행(progress): 자기의 임계구역에서 실행되는 프로세스가 없고 그들 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는지를 결정하는 데 참여할 수 있으며, 이 선택은 무한정 연기될 수 있다.

  3. 한정된 대기(bounded waiting): 프로세스가 자기의 임계구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용하는 횟수에 한계가 있어야 한다.

운영체제 내에서 임계구역을 다루기 위해서 선점형 커널과 비선점형 커널의 접근법이 사용된다.

선점형 커널은 프로세스가 커널 모드에서 수행되는 동안 선점을 허용한다.

사람들이 선점형 커널을 더 선호하는 이유에는

  1. 커널 모드 프로세스가 대기 중인 프로세스에게 처리기를 양도하기 전에 오랫동안 실행할 위험이 적기 때문에 선점형 커널의 응답이 더 민첩할 수 있다.

  2. 실시간 프로세스가 현재 커널에서 실행 중인 프로세스를 선점할 수 있기 때문에 실시간 프로그래밍에 더 적당하다.

등이 있다.

통상 컴퓨터 하드웨어는 상호 배제를 보장하는 여러 연산을 제공하지만, 이런 하드웨어 기반 해결 방안은 너무 복잡하여 대부분의 개발자는 보통 소프트웨어 기반 해결책을 선호한(다고 책에 써있)다.

하지만 소프트웨어 기반 해결책은 현대의 컴퓨터 구조에서 올바르게 동작한다는 것을 보장하지 않는다.

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

피터슨의 해결안은 임계구역과 나머지 구역을 번갈아 가며 실행하는 두 개의 프로세스 P0와 P1으로 한정된다.

두 프로세스는 두 개의 데이터 항목을 공유한다

int turn;
boolean flag[2];

변수 turn은 임계구역으로 진입할 순번을 나타낸다.

turn == i 이면 프로세스 Pi가 임계구역에서 실행될 수 있다.

flag[i]가 참이면 Pi가 임계구역으로 진입할 준비가 되었다는 것을 나타낸다.

임계구역으로 진입하기 위해서 Pi는 먼저 flag[i]를 참으로 만들고, turn을 j로 지정한다.

6-2

해결책이 올바르게 동작한다는 것을 증명하기 위해 다음과 같은 사실을 보여야 한다.

  1. 상호 배제가 제대로 지켜진다는 사실

  2. 진행에 대한 요구 조건을 만족한다는 사실(progress)

  3. 대기 시간이 한없이 길어지지 않는다는 사실(bounded waiting)

Pi가 임계구역에 들어가기 위해서는 flag[j]가 false이던지 turn이 id이던지 해야 한다.

두 프로세스가 모두 자기 임계구역을 수행 중이라면(상호 배제가 지켜지지 못함) flag[0]과 flag[1]이 둘 다 true여야 한다.

하지만 모두 true라도 두 프로세스가 동시에 while 루프를 탈출하지 못한다.

turn 의 변수 값은 0과 1중 하나여야야만 하지, 두 값을 동시게 갖지 못하기 때문이다.

만약 Pj가 성공적으로 지나갈 수 있었다면, 나머지 Pi는 flag[j]가 false가 될 때까지 지나가지 못한다.

Pj가 작업을 완료하면 flag[j]도 false가 되므로 다른 프로세스가 임계영역을 사용할 수 있다.

즉, 상호 배제가 지켜지고 있다.

2와 3을 증명하려면 프로세스가 임계영역에 진입 못하도록 막는 방법은 그 프로세스를 while 문에서

(flag[i] == true AND turn == j)

조건으로 묶어두어 계속 공회전하도록 만드는 방법이라는 사실에 주목해야한다.

Pj가 임계구역에 들어갈 준비가 안 되었을 때는 (flag[j] == false) 이고 Pi는 임계구역에 진입할 수 있다.

Pj가 flag[j]를 true로 지정하고 자신의 while문을 수행하게 되면 이 때 turn은 i 혹은 j일 것이다.

turn이 i라면 Pi가 진입하고 j라면 Pj가 진입한다.

그러나 추후 Pj가 임계구역을 빠져나오면 flag[j]를 false로 재지정하여 Pi로 하여금 진입하게 만든다.

Pj가 flag[j]를 true로 재지정하고 나면 반드시 turn도 i로 지정해줘야 한다.

Pi는 while문을 수행하는 동안 turn값을 바꾸지 않기 때문에 Pi는 Pj가 지난번에 진입했다면 이번에는 자기도 한번은(따라서 대기 시간이 한없이 길어지지 않음) 들어갈 수 있게(progress) 된다.

동기화 하드웨어

임계구역 문제는 단일 처리기 환경에서는 공유 변수가 변경되는 동안 인터럽트 발생을 허용하지 않음으로써 간단히 해결할 수 있다.

이렇게 함으로써, 현재 순서가 선점 없이 순서적으로 실행됨을 확신할 수 있다.

불행하게도 다중 처리기 환경 상에서 인터럽트의 사용불가능화는 메세지가 모든 처리기에 전달되게 하기 때문에 상당한 시간을 소비한다.

이러한 메시지 전달은 각 임계구역에 진입하는 것을 지연시켜, 시스템 효율을 떨어뜨린다.

그러므로 많은 현대의 기계들은 한 워드의 내용을 검사하고 변경하거나, 두 워드의 내용을 원자적으로 swap할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로서, 특별한 하드웨어 명령어들을 제공한다.

검사와 지정(test-and-set)
동시성을 제어하기 위한 동기화 명령어 중 하나로서, 하드웨어의 도움을 받아 수행된다. 이것을 활용하면 상호 배제 등을 편리하게 구현할 수 있다. 이 명령어는 원자성을 가져 명령어가 실행되는 도중에 인터럽트될 수 없으며, 명령어 내에서 수행되는 두 명령어 “boolean initial = lock” 과 “lock = true”는 동시에 실행되어 둘 다 실행되거나 둘 중 하나가 실행되지 않으면 나머지 하나도 실행되지 않는다.
원자성
어떠한 작업이 실행될때 언제나 완전하게 진행되어 종료되거나, 그럴 수 없는 경우 실행을 하지 않는 경우를 말한다. 원자성을 가지는 작업은 실행되어 진행되다가 종료하지 않고 중간에서 멈추는 경우는 있을 수 없다.
function TestAndSet(boolean_ref lock) {
    boolean initial = lock
    lock = true
    return initial
}

검사와 지정을 활용하여 상호 배제를 구현하는 방법의 예제

do {
    while(TestAndSet(&lock))
        ; // do nothing
        // critical section
    lock = false;
        // remainder section
} while(true);

Mutex Locks

하드웨어 기반 해결책은 복잡할 뿐만 아니라 응용 프로그래머는 사용할 수 없다.

소프트웨어적 해결 도구로서 가장 간단한 도구가 바로 mutex lock이다.

Mutex는 mutual exclusion, 상호 배제를 뜻한다.

6-3

acquire()로 락을 획득, release()로 락을 반환한다.

available 변수가 락의 가용 여부를 표시한다.

락이 가용하면 acquire() 호출이 성공하고 락이 사용불가 상태가 된다.

사용 불가 상태의 락을 획득하려고 시도하는 프로세스는 락이 반환될 때까지 봉쇄된다.

acquire(){
	while (!available)
		; //busy wait
	available = false;
}


release(){
	available = ture;
}

이 방식의 단점은 acquire() 함수를 호출하는 반복문을 계속 실행하는 바쁜 대기(busy waiting)를 해야 한다는 것이다.

바쁜 대기(=spinlock)은 더 생산적인 작업에 사용할 수 있는 CPU 사이클을 낭비하게 된다.

장점은 시간을 상당히 소요하는 문맥 교환을 전혀 하지 않는 다는 점이다.

따라서 프로세스들이 짧은 시간 동안만 락을 소유하는 것이 예상되면 spinlock이 유용하다.

문맥 교환(Context Switch)
하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해, 이전의 프로세스의 상태(문맥)를 보관하고 새로운 프로세스의 상태를 적재하는 작업을 말한다.

Semaphores

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

wait(S){
	while (S <= 0)
		; // 바쁜 대기
	S--;
} 

signal(S) {
	S++;
}

한 스레드가 세마포 값을 변경하면, 다른 어떤 스레드도 동시에 동일한 세마포 값을 변경할 수 없다.

S의 정수 값을 검사하는 작업과 그에 다라 실행되는 변경 작업 또한 인터럽트 되지 않아야 한다.

운영체제는 종종 카운팅(counting)과 이진(binary) 세마포를 구분한다.

카운팅 세마포의 값은 제한 없는 영역을 갖고 이진 세마포의 값은 0과 1 사이의 값만 가능하다.

따라서 이진 세마포는 mutex 락과 유사하고, 몇몇 시스템에서는 상호 배제를 보장하기 위해 mutex 락 대신 이진 세마포가 사용된다.

카운팅 세마포는 가용한 자원의 개수로 초기화된다.

각 자원을 사용하려는 프로세스는 세마포어에 wait()연산을 수행하며, 이 때 세마포의 값은 감소된다.

프로세스가 자원을 방출할 때는 signal() 연산을 수행하고 세마포는 증가하게 된다.

세마포의 값이 0이 되면 모든 자원이 사용 중임을 나타낸다.

이후 자원을 사용하려는 프로세스는 세마포 값이 0보다 커질 때까지 봉쇄된다.

mutex 락의 단점은 바쁜 대기를 해야 한다는 점인데, 위에서 설명한 세마포 연산 wait과 signal 역시 같은 문제를 가지고 있다.

바쁜 대기를 해야 한다는 필요성을 극복하기 위해서 연산의 정의를 변경한다.

typeef struct {
	int value
	struct process *list;
} semaphore;

void wait(semaphore *S){
	S->value--;
	if(S->value <0) {
		이 프로세스를 S->list에 넣는다;
		block();
	}
}

void signal(semaphore *S) {
	S->value++;
	if(S->value <=0) {
		s->list로부터 하나의 프로세스 P를 꺼낸다;
		wakeup(P)
	}

}

바쁜 대기 대신 프로세스는 자신을 봉쇄시킬 수 있다.

봉쇄 연산은 프로세스를 세마포에 연관된 대기 큐에 넣고, 프로세스의 상태를 대기 상태로 전환한다.

그 후에 제어가 CPU 스케줄러로 넘어가고, 스케줄러는 다른 프로세스를 실행하기 위하여 선택한다.

봉쇄된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작 되어야 한다.

프로세스는 wakeup() 연산에 의해 재시작되는데 이것은 프로세스의 상태를 대기 큐에서 준비 완료 큐로 변경한다.

바쁜 대기를 하는 고전적 정의에서 세마포의 값은 음수를 가질 수 없으나 이와 같이 구현하면 음수 값을 가질 수 있다.

음수일 때, 그 절대값은 세마포를 대기하고 있는 프로세스의 수이다.

세마포의 구현에서 두 개 이상의 프로세스들이 오로지 대기 중인 프로세스들의 signal() 연산 실행을 무한정 기다리는 상황이 발생할 수 있다.

이런 상태를 교착 상태(deadlock)라고 한다.

6-4

P0이 wait(S)를 실행하고, P1이 wait(Q)를 실행한다고 가정하자.

P0이 wait(Q)를 실행할 때 P0은 P1이 signal(Q)를 실행할 때까지 기다려야 한다.

마찬가지로, P1이 wait(S)를 실행할 때는 P0이 signal(S)를 실행할 때까지 기다려야 한다.

이들 시그널 연산들은 실행될 수 없기 때문에 P0와 P1은 교착 상태가 된다.

무한 봉쇄(indefinite blocking) 또는 기아(starving)은 프로세스들이 세마포에서 무한정 대기하는 것이다.

무한 봉쇄는 우리가 세마포와 연관된 큐에서 프로세스들을 후입 선출 순서로 제거할 경우에 발생 가능하다.

무한 봉쇄
자원이 부족한 상태에서 우선순위가 높은 프로세스가 계속 들어와서 우선순위가 낮은 프로세스가 계속 수행되지 못하는 현상

높은 우선순위 프로세스가 낮은 우선순위 프로세스의 데이터가 필요할 경우 스케줄링의 어려움이 생기는데, 이것을 우선순위 역전 문제라고 한다.

이를 해결하기 위해 우선순위 상속 프로토콜을 구현한다.

이 프로토콜은 높은 우선순위 프로세스가 필요로 하는 자원에 접근하는 모든 프로세스들의 우선순위를 자원의 사용이 끝날 때까지 높인다.

식사하는 철학자 문제

  • 전산학에서 동시성과 교착 상태를 설명하는 예시
  • 여러 프로세스가 동시에 돌아갈 때 교착 상태가 나타나는 원인을 직관적으로 보임

고전적인 동기화 문제들 중에서도 유명한 식사하는 철학자들 문제이다.

  • 다섯 명의 철학자가 원탁에 앉아 있음

  • 각자의 앞에는 스파게티가 있고 양옆에 젓가락이 한 짝씩 있음

  • 각각의 철학자는 다른 철학자에게 말을 할 수 없음

  • 철학자가 스파게티를 먹기 위해서는 양 옆의 젓가락 짝을 동시에 들고 있어야 함

  • 각각의 철학자가 왼쪽의 젓가락 짝을 들고 그 다음 오른쪽의 젓가락 짝을 들어서 스파게티를 먹는 알고리즘을 가지고 있다면 다섯 철학자가 동시에 왼쪽의 젓가락 짝을 든 다음 오른쪽의 젓가락 짝을 들 때까지 무한정 기다리는 교착 상태에 빠질 수 있음

6-5

각 젓가락을 하나의 세마포로 표현하자.

철학자는 그 세마포에 wait() 연산을 실행하여 젓가락을 집으려고 시도한다.

그는 또한 해당 세마포에 signal() 연산을 실행함으로써 자신의 젓가락을 놓는다.

그러므로 공유 자료는 다음과 같다

semaphore chopstick[5];

여기서 chopstick의 원소들은 모두 1로 초기화된다.

6-6

이 해결안은 인접한 두 철학자가 동시에 식사하지 않는다는 것을 보장하지만 교착 상태의 가능성이 있다.

5명의 철학자 모두가 동시에 배가 고파 왼쪽 젓가락을 잡는다고 가정해 보자.

chopstick의 모든 원소들은 0이 되어 각 철학자가 오른쪽 젓가락을 집으려고 하면 영원히 대기해야 한다.

이를 해결하기 위해

  • 철학자의 수를 제한한다

  • 젓가락 두개를 모두 집을 수 있을 때만 집도록 허용한다

  • 비대칭 해결안을 사용한다 (ex:홀수 철학자 왼쪽 젓가락 먼저)

등의 해결책이 있다.

에츠허르 데이크스트라의 해결책은 다음과 같다.

각각의 철학자를 P[1,2,3,4,5]라고 하고,

각 철학자의 왼쪽 포크를 f[1,2,3,4,5]라고 하자.

P5를 제외한 네 명은 먼저 fn을 집은 후 fn+1를 집는 방식을 취한다.

그리고 P5는 이와 반대로, f1을 먼저 집은 후 f5를 집는다.

이것은 원래 방식의 대칭성을 제거하고, 따라서 교착 상태를 막을 수 있다.

생산자-소비자 문제

생산자-소비자 문제(producer-consumer problem)는 여러 개의 프로세스를 어떻게 동기화할 것인가에 관한 고전적인 문제이다.

한정 버퍼 문제(bounded-buffer problem)라고도 한다.

  • 유한한 개수의 물건(데이터)을 임시로 보관하는 보관함(버퍼)에 여러 명의 생산자들과 소비자들이 접근함

  • 생산자는 물건이 하나 만들어지면 그 공간에 저장함

  • 저장할 공간이 없는 문제가 발생할 수 있음

  • 소비자는 물건이 필요할 때 보관함에서 물건을 하나 가져옴,

  • 소비할 물건이 없는 문제가 발생할 수 있음

이 문제를 해결하는 것을 생산자-소비자 협동이라 하며, 버퍼가 동기화되어 정상적으로 동작하는 상태를 뜻한다.

문제를 해결하기 위해 세마포를 활용할 수 있다.

변수

  1. Empty : 버퍼 내에 저장할 공간이 있는지를 나타낸다. (초기값은 n)

  2. Full : 버퍼 내에 소비할 아이템이 있는지를 나타낸다. (초기값은 0)

  3. Mutex : 버퍼에 대한 접근을 통제한다. (초기값은 1)

생산자 프로세스

 do {
     ...
     아이템을 생산한다.
     ...
     wait(empty);  //버퍼에 빈 공간이 생길 때까지 기다린다.
     wait(mutex); //임계 구역에 진입할 수 있을 때까지 기다린다.
     ...
     아이템을 버퍼에 추가한다.
     ...
     signal(mutex); //임계 구역을 빠져나왔다고 알려준다.
     signal(full);  //버퍼에 아이템이 있다고 알려준다.
 } while (1);

소비자 프로세스

 do {
     wait(full);    //버퍼에 아이템이 생길 때까지 기다린다.
     wait(mutex);
     ...
     버퍼로부터 아이템을 가져온다.
     ...
     signal(mutex);
     signal(empty); //버퍼에 빈 공간이 생겼다고 알려준다.
     ...
     아이템을 소비한다.
     ...
 } while (1);

Readers-Writers 문제

독자-저자 문제(readers-writers problem)란 여러 명의 독자와 저자들이 하나의 저장 공간(버퍼)을 공유하며 이를 접근할 때 발생하는 문제이다.

독자는 공유 공간에서 데이터를 읽어온다.

여러 명의 독자가 동시에 데이터를 읽어오는 것이 가능하다.

저자는 공유 공간에 데이터를 쓴다.

한 저자가 공유 공간에 데이터를 쓰고 있는 동안에는 그 저자만 접근이 가능하며, 다른 독자들과 저자들은 접근할 수 없다.

변수

  1. readcount : 현재 버퍼에 접근 중인 독자의 수를 나타낸다. (초기값=0)

  2. wrt : 저자들 사이의 관계를 통제한다. 즉, 동기화한다. (초기값=1)

  3. mutex : readcount와 wrt에 접근하는 것이 원자적으로 수행될 수 있도록 하는 세마포어 (초기값=1)

저자 프로세스

wait(wrt);    // 임계구역에 들어가기 위해 허가가 나기를 기다린다.
...
쓰기 작업 수행
...
signal(wrt);  // 임계구역에서 빠져나왔음을 알린다.

독자 프로세스

wait(mutex);
    readcount++;     // 독자 수 1 증가
    if readcount = 1
        wait(wrt);   // 쓰고 있는 저자가 없을 때까지 기다린다.
signal(mutex);
...
읽기 작업 수행
...
wait(mutex);
    readcount--;     // 독자 수 1 감소
    if readcount = 0
        signal(wrt); // 독자가 없다면 이를 알린다.
signal(mutex);