동기화 도구들
배경
생산자 소비자 문제
// 생산자
while (true) {
while (count == BUFFER_SIZE);
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
count++;
}
// 소비자
while (true) {
while (count == 0);
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
count--;
}생산자와 소비자 코드를 병행적으로 수행시키면 올바르게 동작하지 않는다. count 값이 5이고, 생산자 소비자가 count++, count--를 병행적으로 실행할 때 count의 값은 4,5,6이 될 수 있다. (올바른 값은 5)
// count++의 기계어 구현
register1 = count
register1 = register1 + 1
count = register1
// count--의 기계어 구현
register2 = count
register2 = register2 + 1
count = register다음과 같이 저수준의 문장(기계어)들이 뒤섞여서 수행되면 값이 5가 아닌 4,6이 나올 수 있다.
- count++, count--의 기계어 코드가 뒤섞여 실행되면 값이 부정확하게 나올 수 있음
여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라고 한다.
- 이를 막기 위해서는 한순간에 하나의 프로세스만이 변수 count를 조작하도록 보장해야 한다.
임계구역 문제
각 프로세스들은 임계 구역(critical section)이라고 부르는 코드 부분을 포함하고 있고, 그 안에서 적어도 하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 수정할 수 있다.
- 한 프로세스가 자신의 임계구역에서 수행되는 동안 다른 프로세스들은 임계 구역에 들어갈 수 없다.
여러 프로세스들이 임계구역에 접근할 수 있기 때문에 경쟁 상태가 발생한다.
임계구역 문제를 해결하기 위한 조건
- 상호 배제(mutual exclustion) : 한 프로세스가 임계구역에서 실행된다면, 다른 프로세스들은 임계구역에서 실행될 수 없다.
- 진행(progress) : 임계 구역에 들어간 프로세스가 없는 상태에서, 들어가려고 하는 프로세스가 여러 개 있다면 어느 것이 들어갈지를 적절히 결정해주어야 한다.
- 한정된 대기(bounded waiting) : 프로세스가 임계구역에 진입하려는 요청을 한 후로부터 그 요청이 허용될 때 까지 다른 프로세스들이 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.
Peterson 해결안
Peterson의 해결안은 임계 구역와 나머지 구역을 번갈아 가며 실행하는 두 개의 프로세스로 한정된다. 두 프로세스는 아래의 두 개의 데이터를 공유한다.
int turn;
boolean flag[2];turn은 임계구역으로 진입할 순번을 나타낸다.(turn == 1이면 1번 프로세스가 임계구역에서 실행 가능)
flag 배열은 프로세스가 임계구역으로 진입할 준비가 되었다는 것을 나타낸다.(flag[1] == true이면, 1번 프로세스가 임계 구역으로 진입할 준비가 됨)
while (true) {
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
// 임계 영역
falg[i] = false;
// 나머지 영역
}
while (true) {
flag[j] = true;
turn = i;
while (flag[i] && turn == i);
// 임계 영역
flag[j] = false;
// 나머지 영역
}위의 해결책은 임계구역 문제에 대한 해결책으로 올바르게 동작한다.
- 상호 배제가 제대로 지켜짐
- turn 값은 0, 1중 하나의 값만을 갖기 때문에 하나의 프로세스만 while 문을 빠져나갈 수 있다.
- 진행에 대한 요구조건을 만족한다.
- 대기시간이 한없이 길어지지 않음
- 프로세스 i는 프로세스 j가 임계 영역에서 코드를 수행하고 나오면 flag[j]값이 false가 되므로, while문에서 바로 탈출해서 코드 실행이 가능하다.
실제 위의 코드를 실행하면 정확하게 동작하지 않음
- turn = 1, while문 수행중 인터럽트가 발생하여 제대로 동작하지 않을 수 있음
- 피터슨 알고리즘은 임계 구역 문제를 해결하기 위한 알고리즘을 제공하는데 의의를 둠
동기화를 위한 하드웨어 지원
임계구역 문제를 해결하기 위한 하드웨어 명령어
메모리 장벽
- 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공하여 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사항이 보이는 것을 보장함
- 메모리 장벽 명령어가 실행될 때, 시스템은 후속 적재 또는 저장 연산이 수행되기 전에 모든 적재 및 저장이 완료되도록 한다.
하드웨어 명령어
인터럽트 되지 않는 하나의 단위로서, 특별한 하드웨어 명령어 제공
test_and_set
boolean test_and_set(boolean *target) {
boolean rv = *target;
*target = true;
return rv;
}
do {
while (test_and_set(&lock));
/* critical section */
lock = false;
/* remainder section */
} while (true);- test_and_set은 원자적으로 수행한다.
- lock을 통해 상호배제 구현(초기값 false)
compare_and_swap
int compare_and_swap(int *value, int expected, int new_value) {
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
while (true) {
while (compare_and_swap(&lock, 0, 1) != 0);
/* critical section */
lock = 0;
/* remain section */
}- 전역 변수 lock은 최초 0으로 초기화 된다.
- 원자적으로 수행
- 상호 배제는 만족시키지만, 한정된 대기조건을 만족시키지 못함
- P1, P2 프로세스가 있을 때, P1 임계영역에 나왔을 때, 계속해서 임계 영역에 진입할 수 있음
- test_and_set, compare_and_swap 한정 대기를 만족시키지 못함
- waiting[n] 변수와 lock 변수를 이용해서 한정된 대기를 해결할 수 있음
원자적 변수
원자적 변수(atomic variable)
- 정수 및 부울과 같은 기본 데이터 유형에 대한 원자적 연산 제공
- 카운터가 증가 할 때와 같이 갱신되는 동안 단일 변수에 대한 데이터 경쟁이 있을 수 있는 상황에서 상호 배제를 보장하는데 사용
Mutex Locks
mutex
- mutual exclusion의 줄임말
- 프로세스는 임계 구역에 들어가기전에 락을 획득해야 하고 빠져 나올때는 락을 반납해야 한다.
Mutex락 구현
acquire() {
while (!available); /* busy waiting */
available = false;
}
release() {
available = true;
}
while (true) {
acquire();
/* critical section */
release();
/* remainder section */
}- acquire()와 relase()는 원자적으로 수행한다.
- 단점으로는 바쁜 대기(busy waiting)이 발생한다.
- 임계 구역으로 들어가기 원하는 프로세스들은 acquire() 함수 안에서 반복문을 계속 실행한다.
- CPU를 바쁜 대기를 하게 함으로써 자원을 낭비함
- 스핀락(spinlock)이라도 한다.
- 단점만 있는것도 아니라 장점도 존재함
- 프로세스가 락을 기다려야 하고 문맥 교환에 상당한 시간이 소요될 때, 문맥 교환이 필요하지 않음
세마포(Semaphores)
세마포 S는 정수 변수로서, 초기화를 제외하고는 단지 두 개의 표준 원자적 연산 wait()와 signal()로만 접근할 수 있다
wait(S) {
while (S <= 0);
S--;
}
signal(S) {
S++;
}wait()과 signal() 연산 시 세마포의 정수 값을 변경하는 연산은 원자적으로 수행되어야 한다. wait() 수행시 S값을 검사하는 작업과 감소시키는 작업은 인터럽트 되지 않고 실행되어야 한다.
세마포 사용법
카운팅 세마포는 제한 없는 영역을 갖는다. 이진 세마포는 0과 1사이의 값만 가능하며 mutex 락과 유사하게 동작한다.
카운팅 세마포는 유한한 개수를 가진 자원에 대한 접근을 제어하는데 사용된다.
- 자원을 사용하려는 프로세스는 세마포에 wait() 연산을 수행하고, 세마포 값은 감소한다.
- 프로세스가 자원을 방출할 때는 signal() 연산을 수행하고, 세마포의 값이 증가한다.
- 세마포의 값이 0이 되면 모든 자원이 사용중이므로, 이후에 자원을 사용하려는 프로세스는 세마포 값이 0보다 커질때 까지 봉쇄된다.
세마포 구현
wait() 연산의 경우 while 문을 수행하는 도중 바쁜 대기 상태가 발생할 수 있다.
바쁜 대기 대신에 프로세스를 일시 중지 시킬 수 있다.
- 프로세스를 세마포에 연관된 대기 큐에 넣고, 프로세스의 상태를 대기 상태로 전환한다.
- 대기 중인 프로세스는 signal() 연산 내부에 있는 wakeup() 연산에 의해 재시작되는데, 이 연산은 프로세스의 상태를 대기 상태에서 준비 상태로 변경시킨다.
- 프로세스는 준비 완료 큐에 넣어짐
typedef struct {
int value;
struct process *list;
} semaphore;
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);
}
}모니터(Monitors)
세마포도 잘못 사용하면 발견하기 어려운 타이밍 오류를 야기할 수 있다.
mutex 락 또는 세마포어가 타이밍 오류를 발생시키는 예
- 모든 프로세스는 mutex 변수를 공유하며 초기 값은 1이다.
- 임계 구역을 진입할 때 wait(mutex)를, 임계 구역에서 나올 때는 signal(mutex)를 실행해야 한다.
wait()과 signal() 연산의 순서가 바뀜
signal(mutex);
...
critial section
...
wait(mutex);여러 프로세스가 동시에 임계 구역 안에서 실행될 수 있어 상호 배제를 위반하게 된다.
wait(mutex)를 잘못 호출
wait(mutex);
...
critical section
...
wait(mutex);두 번째 wait() 호출에서 영구적으로 봉쇄된다.
프로세스가 wait(mutex)나 signal(mutex) 또는 둘 다 빠트렸다고 가정했을 때, 상호 배제 조건을 위반하던가 프로세스가 영구적으로 봉쇄된다.
프로그래머가 세마포를 잘못 사용하면 다양한 오류가 쉽게 발생한다. 이러한 오류를 처리하기 위한 전략은 간단한 동기화 도구를 통합하여 고급 언어 구조물(모니터)을 제공하는 것이다.
모니터 사용법
추상화된 데이터 형(abstract data type, ADT)
- 데이터와 이 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어 보호한다.
모니터 형
- 모니터 내부에서 상호 배제가 보장되는 프로그래머가 정의한 일련의 연산자 집합을 포함하는 ADT
- 모니터 형은 변수들의 선언을 포함하고 있는데, 이 변수들의 값은 그 형에 해당하는 한 인스턴스의 상태를 정의한다.
- 또한 변수들을 조작할 수 있는 프로시저 또는 함수들의 본체도 포함하고 있다.
- 모니터 형의 표현은 다른 프로세스들이 직접 사용할 수 없다.
- 모니터 내의 정의된 함수만이 오직 모니터 내에 지역적으로 선언된 변수들과 형식 매개변수들에게만 접근할 수 있다.
모니터 구문 예시
monitor monitor name
{
/* shared variable declarations */
function P1 (...) {
...
}
...
function Pn (...) {
...
}
initialization_code (...) {
...
}
}모니터 구조물은 모니터 안에 항상 하나의 프로세스만이 활성화되도록 보장해 준다.
- 프로그래머들은 동기화 제약 조건을 명시적으로 코딩해야 할 필요가 없음
모니터에서는 실행 순서를 제어하기 위해 부가적인 동기화 기법을 정의할 필요가 있다.
- 이 동기화 기법들은 condition이라는 구조물로 제공될 수 있다.(조건 변수)
condition x,y조건 변수에 호출될 수 있는 연산은 wait()와 signal() 뿐이다.
x.wait();연산은 x.wait()을 호출한 프로세스는 다른 프로세스가
x.signal()을 호출할 때 까지 일시 중지 되어야 한다는 것을 의미한다.
x.signal() 연산은 정확히 하나의 일시 중지 프로세스를 재개한다. 만약 일시 중지된 프로세스가 없다면 signal() 연산은 아무런 효과가 없다.
x.signal() 연산이 프로세스 P에 의해 호출될 때, 조건 x와 연관된 일시 중지된 프로세스 Q가 있다고 가정해보자.
- 일시 중지된 스레드 Q가 실행을 재개하도록 허용된다면, signal을 보낸 스레드 P는 반드시 대기해야 한다.
- 만약 대기하지 않으면 P와 Q는 모니터 안에서 동시에 활성화된다.
P와 Q가 동시에 활성화되지 않게 하기 위해서는 두 가지 방법을 사용 할 수 있다.
- Signal and wait : P는 Q가 모니터를 떠날 때 까지 기다리거나 또는 다른 조건을 기다린다.
- Signal and continue : Q는 P가 모니터를 떠날 때 까지 기다리거나 또는 다른 조건을 기다린다.
라이브니스
라이브니스
- 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성
- 무한 대기와 같은 경우는 라이브니스 실패의 예이다.
라이브니스의 실패가 일어날 수 있는 상황
교착 상태
- 한 집합 내의 모든 프로세스가 그 집합 내의 다른 프로세스만이 유발할 수 있는 이벤트를 기다리는 상태
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
... ...
signal(S); signal(Q);
signal(Q); signal(S);위 상황에서 singal()연산들은 실행 될 수 없다.
- P0은 wait(Q)를 실행하고 나오면 P1이 signal(Q)를 실행할 때 까지 기다려야 한다.
- P1은 wait(S)를 실행하고 나오면 P0이 signal(S)를 실행할 때 까지 기다려야 한다.
- signal() 연산들은 실행될 수 없기 때문에 교착 상태가 발생하게 됨
우선순위 역전
일반적으로 커널 데이터는 락에 의해 보호되기 때문에 낮은 우선순위 프로세스가 자원의 사용을
마칠 떄 까지 높은 우선순위 프로세스가 기다려야 한다. 낮은 우선수위 프로세스가 또 다른 높은
우선순위 프로세스의 의해 선점되는 경우 상황은 더욱 복잡해진다.
- 우선순위 L < M < H인 프로세스가 존재한다고 가정
- 프로세스 H가 세마포 S를 필요함
- 현재 L이 자원을 선점하고 있다.
- H는 L이 끝날 때 까지 기다려야함
- 프로세스 M이 실행 가능 상태가 되고 프로세스 L을 선점한다.
- H가 L이 자원을 양도할 때까지 기다리는 시간에 영향을 줌
이러한 라이브니스 문제는 우선순위 역전(priority inversion)이라고 알려져 있다.
- 셋 이상의 우선순위를 가진 시스템에서 발생한다.
우선순위 역전 문제를 해결하기 위해 우선순위 상속 프로토콜(priority-inheritance protocol)
을 사용한다.
- 더 높은 우선순위 프로세스가 필요로 하는 자원에 접근하는 모든 프로세스는 문제가 된 자원의 사용이
끝날 떄 까지 더 높은 우선순위를 상속받고 자원 사용이 끝나면 원래 우선순위로 되돌아감- 프로세스 L은 프로세스 H의 우선순위를 상속받아서 프로세스 M이 L의 실행을 선점하는 것을 방지
- L이 자원을 사용하고 H의 우선순위와 동일한 자원을 방출 후 원래 우선순위로 되돌아감
- 자원은 M이 아닌 H가 사용하게 됨(H와 동일한 우선순위로 방출)
