while문에서 무한루프를 돌다가 exit함수에서 lock이 false가 되면 반복문 탈출
하지만 해당 코드는 시분할 시스템 때문에 문제가 발생할 수 있다. lock을 다시 true로 만들기 전에 문맥교환이 일어날 수 있기 때문이다. 그렇게되면 lock이 false인 상태에서 다른 쓰레드가 타임 슬라이스를 받아 작업을 수행하고, 그러면서 while문을 통과하게 된다. 결국 lock이 두 군데에서 true로 놓이게 되면서 임계구역에 2개의 쓰레드가 들어가게 된다.
이는 임계구역의 '상호배제' 조건에 위반된다.
Peterson's Solution
int turn = 0; // 공유 변수
boolean flag[2] = {0,0}; // 공유 변수
enter_mutex {
flag[i] = TRUE; // i는 나, j는 너의 프로세스 id
turn = j;
while (flag[j] && turn == j) ;
}
// 임계구역
exit_mutex {
flag[i] = FALSE;
}
쓰레드 i와 j가 각각 수행, 위 코드는 쓰레드 i의 입장
j에게 양보를 한번 해주고, j가 진입하고 활동할 때까지의 시간을 기다린다.
양 측 입장을 둘 다 생각해보면, 서로 양보하기 때문에 먼저 양보한 쪽이 먼저 들어가게 된다.
turn이라는 입장티켓을 한번 씩 상대방에게 건내는 것이라고 볼 수 있다.
Bakery 알고리즘
choosing[i] = true; // 번호표 아직 안받음
number[i] = max(number[0],number[1],...number[n-1]) +1 ;
choosing[i] = false; // 번호표 받음
for ( j = 0 , j < n-1, j++ ) {
while ( choosing[j] );
while ( number[j] != 0 && ((number[j]< number[i] ) || (number[j]== number[i] && j < i )) );
// 고유번호 비교하고 PID 비교
}
// 임계 구역
number[i] = 0;
피터슨 솔루션은 두 개의 프로세스 혹은 쓰레드를 위한 해결책이기 때문에 한계가 있다.
프로세스(쓰레드)마다 도착 순서대로 번호표를 부여하고, 가장 작은 번호인 프로세스(쓰레드)가 임계구역 내로 들어가도록 한다.
경우에 따라 각 프로세스(쓰레드)가 갖는 고유번호에 한계가 있을 수 있다. 따라서 숫자가 겹치는 경우가 발생할 수 있다. 이 때는 PID(TID)를 활용해 이 값이 더 작은 것을 먼저 처리한다.
번호표를 받고 있는 프로세스(쓰레드)가 있다면 대기한다.
고유번호가 더 작거나 고유번호가 같고 PID가 작은 프로세스(쓰레드)들이 먼저 임계구역을 처리하도록 대기한다.
Bakery 알고리즘 예제 주석
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>
#include <time.h>
#define THREAD_COUNT 32 // 고유번호 갯수
volatile int numbers[THREAD_COUNT]={0}; // 각 방문자의 번호 저장 array
volatile int choosing[THREAD_COUNT]={0}; // 번호표 뽑기 전엔 true
volatile int counter=0; // 사용할 공유변수
// cf. volatile : 변수에 대한 c코드를 컴파일러가 optimize하는 것 방지
void lock(int);
void unlock(int);
void use_resource(int);
void* thread_body(void*);
int main(int argc, char** argv)
{
pthread_t threads[THREAD_COUNT];
srand(time(NULL)); // 각자 랜덤한 시점에 lock을 시도하도록
printf("\n");
printf("number thread_id counter\n");
fflush(stdout);
for (int i = 0; i < THREAD_COUNT; ++i) { // i ; TID의 역할
pthread_create(&threads[i], NULL, &thread_body, (void*)((long)i));
}
for (int i = 0; i < THREAD_COUNT; ++i) {
pthread_join(threads[i], NULL);
}
printf("\n");
return 0;
}
test and set 방식과 마찬가지로 하나의 CPU 명령어로 되어 있어 atomic하게 수행된다.
Swap 함수는 말그대로 두 값을 받아 swap 해준다.
lock의 값과 key값을 바꾸고, key값이 1일 동안은 반복된다.
어떤 쓰레드가 임계구역을 빠져나가면서 lock을 0으로 만들면, 해당 인스트럭션에서 제일 먼저 수행시키게 되는 쓰레드 하나가 lock을 0으로 만들고, 이를 swap 하면서 key는 0, lock은 1이 된다. 나머지는 lock이 1로 설정되어 있어 값을 처리할 수 없고, 해당 쓰레드는 임계구역에 진입해 작업을 수행한다.
interrupt-disable과 interrupt-enable은 커널모드에서만 사용가능한 특권명령어이다. 따라서 커널 내의 시스템 호출 부와 인터럽트 처리기의 임계구역을 보호하기 위해 사용할 수 있다. 물론 interrupt-disable 기간이 길어져선 안되니, 적당한 짧은 시간동안만 사용해야 한다.
