자 여기 counter 변수를 1 증가시켜야 하는 생산자 프로세스와, counter 변수를 1 감소시켜야 하는 소비자 프로세스가 있다고 해보자. 만약 이 두 프로세스가 counter변수에 동시에 접근하여 조작을 한다면 의도했던 실행결과가 보장되지 않는다. 실행 결과가 자원에 접근이 발생한 특정 순서에 의존하기 때문이다. 이러한 상황을 경쟁상황(race condition)이라고 한다.
따라서 일관적인 실행결과를 보장하기 위해서는 변수에 대해 하나의 프로세스만 접근할 수 있도록, 프로세스를 동기화할 필요가 있다.
임계영역 문제
프로세스들이 임계영역을 포함하고 있는 코드로 작성되어있는 시스템을 생각해보자. 프로세스는 아래와 같은 구조를 가지고 있을 것이다.
do{
진입 영역 // 임계 영역으로 들어가기 위한 허가 요청
임계 영역 // 프로세스 공유 변수 변경, 테이블 갱신 , 파일 쓰기 등의 작업 실행
퇴출 영역 // 임계 영역에서 퇴출
나머지 영역
}while(TRUE) ;이 시스템에서 가장 중요한 '임계 영역'은 한 프로세스가 자신의 임계 영역에서 실행하는 동안에는 다른 프로세스가 자신의 임계 영역에 들어올 수 없다. 다른 프로세서와의 작업의 독립성을 확보하는 영역이다. 이러한 임계 영역의 특징은 다음과 같다.
- 상호 배제(Mutual exclusion) : 프로세스가 자기의 임계 영역에서 실행된다면, 다른 프로세스들은 그들 자신의 임계영역에서 실행될 수 없다.
- 진행(progress) : 자신의 임계영역으로 진입하려고 하는 프로세스가 있다면, 자기 자신은 임계 영역을 실행중이지 않아야 하고, 나머지 영역에서 실행중이지 않은 프로세스들 중 임계영역으로 진입할 프로세스를 결정한다. 그리고 이 결정은 무기한 연기될 수 없다.
- 한정된 대기(bounded waiting) : 다른 프로세스가 자신의 임계 영역에 진입하도록 허용되는 횟수는 한계 또는 제한이 있어야 한다.
피터슨의 해결안(Peterson's Solution)
피터슨은 이러한 임계영역의 문제를 소프트웨어적으로 해결할 수 있는 알고리즘을 제공한다. 이 해결책은 임계 영역과 나머지 영역을 번갈아 가며 실행하는 두개의 프로세스로 한정된다. 이 솔루션은 다음과 같이 작성될 수 있다.
int turn; // process idx which will be the next
boolean flag[2]; // 프로세스들이 실행중인지 아닌지 체크하는 배열
do{
flag[i]=TRUE; // i번째 프로세스가 임계영역으로 진입할 준비가 완료됨
turn = j; // i 이후에는 j가 실행될 것임
while(flag[j] && turn == j ) ; // j번째 프로세스가 실행중이라면 대기한다
임계영역
flag[i] = FALSE; // i번째 프로세스가 임계영역의 작업을 완료함
나머지 영역
}while(TRUE);
이는 임계 영역의 상호 배제, 진행, 한정된 대기의 모든 조건을 만족한다.
동기화 하드웨어
피터슨의 해결책보다는 임계 영역의 접근을 위해서 Lock을 획득하게 구성하면 더욱 간단하게 동기화할 수 있다. 단일처리기 환경에서는 공유변수가 변경되는 동안 인터럽트 발생을 허용하지 않음으로써 임계영역 문제를 처리할 수 있지만, 다중 처리기 환경에서는 인터럽트 불능 상태에 대한 메시지를 프로세스에 전달하는 것이 더 시간을 소비하기 때문에 적절하지 않다.
따라서 많은 현대의 기계들은 한 워드(word)의 내용을 검사하고 변경하거나, 두 워드의 내용을 원자적으로 교환(swap)할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로서 특별한 하드웨어 명령어들을 제공한다. TestAndSet()과 swap()인데 이는 응용프로그래머들의 영역이 아니기 때문에 다음에 다시 보기로 한다.
세마포(semaphores)
세마포는 정수 변수로서 초기화를 제외하고는 단지 두 개의 표준 원자적 연산 wait() 와 signal()로만 접근이 가능하다.
wait(S){
while(S<=0) ;
S--;
}
signal(S){
S++;
}
do{
wait(mutex); // 이진세마포(0과 1사이의 값만 가능)의 경우 상호 배제를 제공하기 때문에 mutex라고 부른다.
// critical section
signal(mutex);
// remainder section
}while(TRUE)이때 가장 중요한 것은 한 스레드가 세마포 값을 변경할 때 다른 어떤 스레드도 동시에 세마포 값을 변경할 수 없도록 하는 것이다.
하지만 위의 코드처럼 구현하면 만약 한 프로세스가 자신의 임계영역에 있으면, 그 임계영역으로 들어오고자 하는 다른 프로세스는 계속해서 진입 코드를 실행해야 하는 바쁜 대기 상태에 놓이게 된다. 이는 해당 프로세스가 생산적을 일을 할 수 있는 CPU시간을 낭비하게 되므로 비효율적이다. 바쁜 대기로 인해 프로세스가 락을 기다리는동안 회전하기 때문에 이러한 타입의 세마포를 우리는 spinlock 이라고 부른다.
spinlock에서 발생하는 CPU 시간의 낭비를 해결하기 위해서 wait() 와 signal() 연산의 정의를 변경해야 한다. 변경된 프로세스는 아래와 같다.
- 프로세스가 wait() 연산을 실행하고 세마포 값이 양수가 아닌 것을 발견하면 프로세스는 대기한다
- 프로세스가 대기할 때는 바쁜대기가 아니라, 세마포와 연관된 대기 큐에 프로세스를 넣고 대기한다.(프로세스 상태: 대기)
- 다른 프로세스가 signal() 연산을 실행하면 봉쇄된 프로세스는 재시작되어야 한다.
- 프로세스는 wakeup()연산에 의하여 재시작된다(프로세스 상태: 준비 완료)
- 프로세스를 준비 완료 큐에 넣는다.
typedef struct {
int value;
struct process *list;
}semaphore;
void wait(semaphore *S){
S->value--; // wait중인 프로세스들이 늘어날때마다 세마포가 감소하기 때문에 세마포가 음수일때 절대값 = 대기중인 프로세스 갯수
if(S->value < 0){ // 임계영역이 사용중일때
프로세스를 S->list에 넣는다; // 프로세스를 대기 큐에 넣고
block(); // 봉쇄한다
}
}
void signal(semaphore *S){
S->value++;
if(S->value <=0){ // 임계영역에 접근이 가능해지면
S->list로부터 하나의 프로세스 P를 꺼낸다; // 프로세스를 꺼내고
wakeup(P); // wakeup호출 -> 준비완료 큐에 넣는다.
}
}
이러한 방식으로 구현했을 경우 다중처리기 환경에서는 모든 처리기에서 세마포에 대한 인터럽트를 금지해야 한다. 그렇지 않으면 상이한 프로세스들으 ㅣ명령어들이 임의의 방법으로 서로 끼어들수 있다. 따라서 SMP 시스템은 wait()와 signal() 연산이 원자적으로 실행되는 것을 보장하기 위하여 spinlocks와 같은 다른 락킹 기법을 사용하기도 한다. 하지만 임계영역이 매우 길거나 거의 항상 점유되어있는 프로그램들은 spinlocks로 인한 바쁜대기가 매우 비효율적임을 잊지 말자.
교착상태와 기아, 우선순위 역전
한 집합 내의 모든 프로세스들이 그 집합 내의 다른 프로세스만이 유발할 수 있는 사건을 기다릴 때, 이 프로세스들의 집합이 교착상태에 있다고 말한다. 이와 연관된 또 다른 문제는 무기한 봉쇄(indefinite blocking) 또는 기아(starvation)로서 이것은 프로세스들이 세마포에서 무기한 대기하는 것이다. 무기한 봉쇄는 우리가 세마포와 연관된 큐에서 프로세스들을 LIFO의 순서로 제거할 때 발생할 수 있다.
우선순위의 역전이란 높은 우선순위 프로세스가 현재 낮은 우선순위 프로세스 또는 연속된 낮은 우선순위 프로세스들에 의해 접근되고 있는 커널 데이터를 읽거나 변경할 필요가 있을 때 스케줄링에 어려움이 발생한다. 통상 우선순위 역전의 문제는 우선순위 상속 프로토콜을 구현함으로서 해결할 수 있다. 이 프로토콜에 따르면 더 높은 우선순위 프로세스가 필요로 하는 자원을 접근하는 모든 프로세스들은 문제가 된 자원의 사용이 끝날 때까지 더 높은 우선순위를 상속받는다.