협력적 프로세스는 다른 프로세스의 실행에 영향을 주거나 받는 프로세스이다.
공유 데이터를 동시에 접근하면 데이터의 일관성을 망칠 수 있다.
이러한 프로세스의 질서있는 실행을 보장하는 다양한 메커니즘을 논의한다.
1. Background
병행 또는 병렬 실행될 때 공유하는 데이터의 무결성에 어떤 문제를 일으키는지 알아보자.
count++같은 명령어도 기계어로
register = count
register = register + 1
count = register와 같이 구현될 수 있다.
여기서 register는 한 cpu만 접근할 수 있는 local 레지스터 중 하나이다.
따라서 병행 실행시 저수준의 명령어들의 순서가 뒤섞일 수 있다.
이처럼 여러 프로세스가 동일한 자료를 접근 및 조작하고,
그 실행결과가 접근 순서에 의존하는 상황을 경쟁 상황(race condition)이라고 한다.
이러한 문제를 예방하기 위해 프로세스들을 동기화 시켜야 한다.
2. Critical Section Problem
프로세스 동기화는 임계구역 문제부터 시작한다.
각 프로세스는 다른 프로세스와 공유하는 데이터에 접근하는 영역, 즉 임계구역을 포함하고 있다.
중요한 점은 동시에 두 프로세스가 그들의 임계구역 안에서 실행할 수 없다는 점이다.
각 프로세스는 자신의 임계구역을 진입하려면 진입 허가를 요청해야 한다.
이를 진입 구역이라하고 임계구역 뒤에는 퇴출 구역이 따라올 수 있다.
임계구역 문제에 대한 해결안은 다음 세 가지 요구조건을 충족해야 한다.
- 상호 배제(mutual exclusion) : 한 프로세스가 임계구역에서 실행중일 때, 다른 프로세스들은 자신의 임계구역에서 실행될 수 없다.
- 진행(progress) : 나머지 구역에서 실행중이지 않은 프로세스들만 다음에 누가 임계구역으로 진입할지 결정한다.
- 한정된 대기 : 진입 요청이 허용될 때까지 다른 프로세스의 진입 요청 허가에는 횟수 제한이 있어야 한다.
운영체제를 구현하는 코드(커널 코드)는 경쟁 조건이 발생하기 쉽다.
fork()시 상호 배제가 제공되지 않으면
동일한 프로세스 식별자 번호가 두 개의 다른 프로세스에 배정될 수 있다.
운영체제 내에서 임계구역을 다루기 위해서
선점형 커널과 비선점형 커널의 두 가지 일반적인 접근법이 사용된다.
선점형 커널은 경쟁 조건이 발생하지 않게 잘 설계해야 한다.
SMP에서는 특히 더 어려운데,
SMP에서는 서로 다른 처리기의 두 프로세스가 동시에 커널 모드에 있을 수 있기 때문이다.
3. Peterson의 해결안
지금은 적용되지 않지만 여러 문제들을 잘 설명한 고전 해결책이다.
해결안은 두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결한다.
while (true) {
flag[i] = true;
turn = j;
while (flag[j] && turn == j)
;
/* critical section */
flag[i] = false;
/* remainder section */
}여기서 turn은 임계구역으로 진입할 순번을 나타낸다.
flag 배열은 i번째 프로세스가 임계구역으로 진입할 준비 유무를 나타낸다.
이러한 방법은 최신 컴퓨터 아키텍처에선 유효성이 보장되지 않는다.
컴파일러가 성능을 위해 종속성이 없는 작업을 재정렬 할 수 있기 때문이다.
4. 동기화를 위한 하드웨어 지원
임계구역 문제를 해결하기 위한 세 가지 하드웨어 명령어를 제시한다.
4.1 Memory Barriers
메모리 접근 시 보장되는 사항을 결정한 방식을 메모리 모델이라고 한다.
일반적으로 두 가지 범주가 있다.
- 강한 순서 : 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보임
- 약한 순서 : 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않음
메모리 모델은 프로세서 유형에 따라 달라서 커널 개발자가 미리 알 수 없다.
따라서 컴퓨터 아키텍처는 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공한다.
이러한 명령어를 메모리 장벽 또는 memory fences라고 한다.
메모리 장벽 명령어가 실행되면 시스템은 후속 적재 또는 저장 연산이 수행되기전에
모든 적재 및 저장을 완료하도록 한다.
메모리 장벽은 매우 낮은 수준의 연산으로 일반적으로 커널 개발자만 사용한다.
4.2 Hardware Instructions
많은 현대 기계들은 한 word의 내용을 검사하고 변경하거나,
두 워드의 내용을 원자적으로 교환할 수 있는,
인터럽트 되지 않는 하나의 단위로서의,
특별한 하드웨어 명령어들을 제공한다.
이를 사용하여 임계구역 문제를 간단하게 해결할 수 있다.
중요한 점은 이러한 명령어들은 원자적으로 실행된다는 점이다.
원자적 실행을 강제하기 위해,
대상 피연산자가 갱신되는 동안 lock prefix를 사용해 버스를 잠궈버린다.
4.3 Atomic Variables
임계 구역 문제를 해결하는 다른 도구 중 하나로,
정수 및 bool과 같은 기본 데이터 유형에 대한 원자적 연산을 제공한다.
단일 변수에 대한 데이터 경쟁이 있을 수 있는 상황에서 상호 배제를 보장한다.
하지만 원자적 변수는 공유 데이터 한 개의 갱신에만 제한되는 경우가 많다.
다음 절에서 보다 일반적인 도구를 알아보자.
5. Mutex Locks
이 전에 제시한 하드웨어 기반 해결첵은 복잡하고, 응용 프로그래머가 사용할 수가 없다.
따라서 상위 수준 소프트웨어 도구들을 개발했다.
이 중 가장 간단한 도구가 바로 mutex lock이다.
이는 mutual exclusion 즉, 상호배제라는 뜻이다.
프로세스는 임계구역에 들어가기 전에 반드시 락을 획득해야 하고
임계구역을 빠져나올 때 락을 반환해야 한다.
acquire()로 락을 획득하고 release()로 락을 반환한다.
available이라는 변수로 락의 가용 여부를 표시한다.
acquire()와 release() 함수의 정의는 다음과 같다.
acquire() {
while (!available)
; // busy wait
available = false;
}
release() {
available = true;
}위 두 함수 호출은 원자적으로 수행되어야 한다.
따라서 mutex Lock은 CAS를 사용하여 구현될 수 있다.
하지만 위의 구현 방식의 단점은 busy waiting을 해야 한다는 점이다.
mutex lock 유형을 spinlock이라고도 하는데, 락을 받을 때까지 프로세스가 회전하기 때문이다.
하지만 스핀락은 락을 기다리는 동안 내려갔다 올라오는게 아니기 때문에
문맥교환이 필요하지 않다는 장점이 있다.
따라서 락 유지 기간이 문맥 교환 2번하는 시간보다 짧은 경우,
스핀락이 유용하게 쓰일 수 있다.
6. Semaphores
다익스트라에 의해 고안된,
mutex와 유사하게 동작하지만
프로세스들을 더 정교하게 동기화할 수 있는 도구다.
세마포어 S는 정수 변수로서,
wait()와 signal()로만 접근할 수 있다.
두 함수의 정의는 다음과 같다.
wait(S) {
while (S <= 0)
; // busy wait
S--;
}
signal(S) {
S++;
}wait()와 signal() 연산 시 세마포어의 정수 값을 변경하는 연산은
반드시 원자적으로 수행되어야 한다.
즉, 한 스레드가 세마포어 값을 변경하면 다른 어떤 스레드도 동시에 동일한 세마포어 값을 변경할 수 없다.
또한 S <= 0 과 S--와 같은 S에 대한 작업은 인터럽트 되지 말아야 한다.
6.1 세마포어 사용법
운영체제는 종종 counting semaphore와 binary semaphore를 구분한다.
counting semaphore의 값은 제한 없는 영역(domain)을 갖는다.
binary semaphore의 값은 0과 1의 값만 가능하다.
따라서 이진 세마포어는 mutex lock과 유사하게 동작한다.
실제 몇몇 시스템에서는 상호배제를 위해 mutex lock 대신 이진 세마포어를 사용한다.
counting semaphore는 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용될 수 있다.
두 프로세스 P1, P2가 명령문 s1 -> s2 순으로 병행 수행한다고 할 때,
두 프로세스가 세마포어 synch를 공유하도록 하고 synch는 0으로 초기화한다.
p1에는
s1;
signal(synch);p2에는
wait(synch);
s2;이러한 방법으로 s2는 p1이 signal()을 호출한 후에만 수행 가능하다.
6.2 Semaphore Implementation
앞서 설명한 wait()와 signal() 방식의 세마포어도 역시 busy waiting의 문제가 있다.
따라서 wait()와 signal()의 정의를 다음과 같이 변경할 수 있다.
프로세스는 바쁜 대기 대신에 자신을 일시 중지시킬 수 있다.
일시 중지 연산은 프로세스를 세마포어에 연관된 대기 큐에 넣고,
프로세스를 대기 상태로 전환한다.
대기 상태로 전환된 프로세스는
다른 프로세스가 signal()을 호출해 재시작 되어야 한다.
wakeup()에 의해 프로세스의 상태를 대기에서 준비 완료 상태로 변경 후
준비 완료 큐에 넣어진다.
새로운 정의를 따르는 세마포어를 다음과 같이 정의한다.
typedef struct{
int value;
struct process *list;
}semaphore;각 세마포어는 value와 프로세스 리스트 list를 가진다.
프로세스가 세마포어를 기다려야 한다면, 프로세스 리스트에 추가된다.
signal()은 프로세스 리스트에서 하나를 꺼내 깨운다.
wait()와 signal()은 이제 다음과 같이 정의될 수 있다.
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
sleep();
}
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}sleep() 연산은 프로세스를 일시 중지시킨다.
wakeup(P) 연산은 일시 중지된 프로세스 P의 실행을 재개시킨다.
이 두개는 운영체제의 기본적인 시스템콜로 제공된다.
고전 세마포어는 음수값을 가질 수 없으나
이렇게 하면 음수를 가질 수 있다.
세마포어의 값이 음수일 때, 그 절댓값은 세마포어를 대기하고 있는 프로세스의 수 이다. (wait()에서 값을 먼저 빼고 검사하기 때문에 나온 결과다)
대기하는 프로세스들의 리스트는 각 프로세스의 PCB에 있는 연결 필드에 의해 쉽게 구현 가능하다.
세마포어가 원자적으로 실행되어야 한다는 것은 매우 중요하다.
이를 위해 wait()와 signal()중에 인터럽트가 발생하면 안되는데,
다중 코어 환경에서는 이것이 어렵기도 하고 성능 감소가 심각하다.
따라서 compare_and_swap() 또는 spinlock같은 다른 기업을 제공해야 한다.
7. Monitors
세마포어는 잘못하면 발견하기 어려운 타이밍 오류를 야기할 수 있다.
불행하게도 mutex lock과 세마포어를 사용해도 타이밍 오류는 여전히 발생할 수 있다.
이러한 오류를 처리할 한 가지 전략은
간단한 동기화 도구를 통합하여
고급 언어 구조물을 제공하는 것이다.
그 중 하나인 모니터를 알아보자.
7.1 모니터 사용법
ADT(abstract data type)는 데이터와 이 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어 보호한다.
모니터 형은 모니터 내부에서 상호배제가 보장되는,
프로그래머가 정의한 일련의 연산자 집합을 포함하는 ADT이다.
모니터 안의 변수들은 함수를 통해서만 접근할 수 있다.(private?)
모니터 구조물은 모니터 안에 항상 하나의 프로세스만이 활성화되도록 보장해준다.
이를 위해 부가적인 동기화 기법을 정의해야 할 필요가 있다.
이 동기화 기법들은 condition이라는 구조물로 제공될 수 있다.
condition x, y;이 condition 형 변수에 호출될 수 있는 연산은 오직 wait()와 signal()이다.
x.signal() 연산은 정확히 하나의 일시 중지 프로세스를 재개한다.
만약 일시 중지된 프로세스가 없으면 signal() 연산은 아무런 효과가 없다.
이는 세마포어와는 다른점이다.
7.2 세마포어를 이용한 모니터의 구현
각 모니터마다 mutex라는 이진 세마포어가 정의되고 초기값은 1이다.
프로세스는 모니터로 들어가기 전에 wait(mutex)를 실행하고
모니터를 나온 후에 signal(mutex)을 실행해야 한다.
스터디 요약
뮤텍스와 세마포어는 운영체제가 원자성을 보장해준다.
스핀락은 싱글코엉
