6.1 개요
두 개의 프로세스가 동시에 변수 count를 조작하도록 허용한다면 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황 → 경쟁 상황
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--;
}
JavaScript
복사
count ++, count —가 병행하게 실행된다면 count값은 4,5,6중 하나이다.
6.2 임계구역 문제
진입허가를 요청하는 부분 : 진입 구역
임계 구역: 하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있다.
임계 구역 뒤: 퇴출 구역
1.
상호 배제
a.
프로세스 Pi가 자기의 임계구역에서 실행된다면 다른 프로세스들은 임계구역에서 실행될 수 없다.
2.
진행 → 데드락
3.
한정된 대기
a.
프로세스가 임계구역으로 진입요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야한다.
6.3 Peterson 의 해결안
while(true){
flag[i] = true;
turn = j;
while(flag[j] && turn == j);
//critical section
flag[i] = false;
// remainder section
}
JavaScript
복사
각 Pi가 임계구역에 들어가기 위해서 flag[j] == false이든지 아니면 turn==i이여야한다.
두 프로세스 모두 자기 임계 구역을 수행 중이라면 flag[0] == flag[1] == true로 지정해야한다.
하지만 turn의 값은 0이든지 1이든지 둘 중 하나여야하기 때문이다. 따라서 둘 중 하나만이 while을 성공적으로 지나가고 나머지는 비교구문을 한 번더 실행해야했다.
그리고 마지막에 flag[j] = false로 함으로써 Pi가 지나갈 수 있게 한다. 이를 통해 자신이 끝나면 다음 프로세스가 진입할 수 있도록 한다.
하지만 잘 작동한다고 보장하지 않는다.
왜냐하면 컴파일러가 종속성이 없는 읽기 및 쓰기 작업을 재정렬할 수도 있다.
위의 예시에서 Peterson의 진입 구역에서 첫 두 문장의 순서를 바꾸면 두 스레드가 동시에 임계구역에서 활성화될 수 있다.
→ flag와 turn의 순서를 바꿔버리면 실행될 수 있다.
→기본적으로 자기가 할 때 깃발을 꽂아놓고 남에게 turn을 넘겨줌으로써 침범을 막을 수 있다.
→하지만 turn을 넘겨 주고 자기가 할거라고 해버리면 컨텍스트 스위치를 할 때 꼬일 수 있다.
6.4 동기화를 위한 하드웨어 지원
메모리 장벽
메모리 장벽을 사용하면 임의로 정렬하는 것을 막는다.
하드웨어 명령어
명령어가 원자적으로 실행된다.
test_and_set() 명령어와 compare_and_swap() 명령어를 이용해서 상호배제를 구현할 수 있다.
boolean test_and_set(boolean *target){
boolean rv = *target;
*target = true;
return rv;
}
int compare_and_swap(int *value, int expected, int new_value){
int temp = *value;
if(*value == expected)
*value = new_value;
return temp;
}
C
복사
test_and_set을 이용한 상호배제
do{
while(test_and_set(&lock));
// critical section
lock = false;
//remainder section
}while(true);
C
복사
Pi가 lock을 평가해서 true로 만들면 Pj는 끝없이 돈다. 그리고 다 끝나서 lock을 false로 하면 Pj가 while문을 탈출해서 진입하고, 이 때 lock은 true가 된다.
compare_and_swap을 이용한 상호배제
while(true){
while(compare_and_swap(&lock,0,1) != 0);
//critical section
lock = 0;
}
C
복사
상호 배제 조건을 지키지만 한정된 대기 조건을 지키지는 못한다.
맨 처음에 lock이 0으로 초기화되고 Pi가 compare_and_swap을 실행시키면, lock과 0이 같기 때문에 lock이 1로 바뀌고 0이 반환되므로 while문을 탈출한다.
그리고 Pj가 시작하면 lock이 0과 같지 않기 대문에 1이 반환되고 while문 조건이 성립하므로 계속돈다.
→ 만약 Pi가 계속 critical section에 있으면 무한정 기다려야한다.
한정된 대기 조건을 만족시키는 상호배제
while(true){
waiting[i] = true;
key = 1;
while(waiting[i] && key == 1)
key = compare_and_swap(&lock,0,1); //lock이 0이여야 key가 0을 반환받고 while문을 통과한다.
waiting[i] = false;
//critical section
j = (i+1) % n; // 그 다음으로 실행할 애들을 찾음
while((j!=i) && !waiting[j]) j = (j+1) % n; // waiting[j]값이 true인 애들
if(j==i)
lock = 0; // 만약에 다 돌았는데 기다리는 애들이 없다면 lock을 0으로 초기화, 누구든지 진입할 수 있도록
else
waiting[j] = false; // 만약 waiting[true]인 애들이 있다면, false로 만들어서 while문 통과하도록
//remainder section
}
C
복사
한 프로세스가 끝날 때 그 다음 실행될 애들을 찾음으로써 한정된 대기 조건을 만족시킨다. 따라서 임계구역에 들어가고자 하는 프로세스는 최대한 n-1회만 양보하면 된다.
6.5 Mutex locks
가장 간단한 도구가 mutex 락이다.
임계구역에 들어가기 전에 반드시 락을 획득해야하고, 임계구역을 나올 때 락을 반환해야한다.
acquire()함수가 락을 획득하고 release()함수가 락을 반환한다.
available이라는 불린 변수를 가지는데, 이 값이 락의 가용 여부를 표시함.
락이 가용하면 acquire()은 성공하고 락은 불가 상태가 된다.
acquire(){
while(!available);
availabe = false;
}
release(){
available = true;
}
C
복사
이 방식은 busy waiting을 해야한다.
임계구역에 들어가기를 원하는 다른 프로세스들은 acquire함수를 호출하는 반복문을 계속 실행해야한다. 다중 프로그래밍 시스템에서 문제이다. 생산적으로 사용할 수 있는 CPU주기를 낭비한다.
스핀락이라고 한다.
스핀락은 프로세스가 락을 기다려야하고 문맥 교환에 상당한 시간이 소요될 때 문맥 교환이 필요하지 않다. 잠깐 동안 락을 유지해야하는 경우, 다른 스레드가 하나의 코어에서 임계구역을 실행하는 동안 스레드는 다른 처리 코어에서 ‘스핀'하고 있을 수 있다.
6.6 세마포
초기화를 제외하고는 단지 두 개의 표준 원자적 연산 wait()와 signal()로만 접근할 수 있다.
세마포 사용법
카운팅 세마포 값은 한 번에 접근할 수 있는 스레드의 값이 정해져있다.
이진 세마포는 0이나 1의 값을 가지고, 따라서 mutex락과 유사하게 동작한다.
세마포 구현
wait()연산을 실행학 세마포 값이 양수가 아닌 것을 발견하면 프로세스는 대기해야한다.
바쁜 대기 대신에 세마포에 연관된 대기 큐에 넣고, 프로세스의 상태를 대기 상태로 전환.
세마포 S를 대기하다가 다른 프로세스가 signal()연산을 실행하면 재시작되어야한다.
typedef struct{
int value;
struct process *list;
}semaphore;
wait(semaphore *S){
S->value--;
if(S->value < 0){
add this proees to S->list;
sleep();
}
}
signal(semaphore *S){
S->value ++;
if(S->value <= 0){
remove a precess P from S->list;
wakeup(P);
}
}
C
복사
세마포 값이 음수일 때 절댓값은 세마포를 대기하고 있는 프로세스들의 수이다.
같은 세마포에 대해 두 프로세스가 동시에 wait()와 signal()연산들을 실행할 수 없도로 보장해야한다.
단일 처리기에서는 wait()와 signal()연산이 실행하는 동안 인터럽트를 금지함으로써 해결할 수 있다.
다중 코어에서는 모든 코어에서 인터럽트를 금지해야한다. 그렇지 않으면 다른 코어에서 실행되는 상이한 프로세스들의 명령어들이 임의의 방법으로 끼어들 수 있다. 이것은 성능을 심각하게 감소시킴
따라서 원자적으로 실행되기를 보장하기 위해 스핀락과 같은 기법을 제공해야한다.
6.7 모니터
mutex락 혹은 세마포를 사용할 때도 타이밍 오류는 여전히 발생할 수 있다.
각 프로세스는 임계구역에 진입하기 전에 wait(mutex)를 실행하고 나올 때 signal(mutex)를 실행해야한다. 이 순서가 제대로 지켜지지 않으면 동시에 임계구역에 있을 수 있다.
1.
signal, wait
a.
상호배제가 일단 지켜지지 않는다
2.
wait wait
a.
세마포를 사용할 수 없기에 영구적으로 봉쇄된다.
3.
wait나 signal을 빠뜨리면 상호배제를 위반하거나 영원히 봉쇄된다.
→ 이를 해결하기 위해 모니터 형을 ㅗ입
모니터에는 condition variable이 있다.
모니터는 기본적으로 락을 획득하더라도 condition variable 조건이 안 맞다면 해당 조건의 대기 큐에 가서 기다린다.
이 때 P가 x.signal을 하여 Q를 깨울 때, 두 가지 옵션이 있다.
1.
P가 계속 진행하도록 하거나 - signal and contiue
2.
Q가 계속 진행하도록 하거나 - signal and wait
6.8 라이브니스
교착 상태
서로가 서로를 물고 있는 상태이다.
프로세스 P0, P1이 세마포 S와 Q를 동시에 필요로 하는 상황에서, P0가 S를 들고 있고 P1이 Q를 들고 있다면 이것은 교착상태
우선순위 역전
L < M < H인 프로세스가 존재한다고 할 때
프로세스 H가 세마포 S가 필요하고 S는 L이 가지고 있다. 이 순간 M이 들어온다면 H는 M이 끝날 때까지 영원히 실행되지 않는다.
왜냐하면 L보다 M이 크므로 M이 실행되고 L이 실행되고 H가 실행된다. 이것을 막기 위해서 priority donation을 사용한다.
이를 통해 L을 H만큼 우선순위를 높여서 L, H, M 순서로 실행되게 함
