[운영체제] 임계구역의 조건 및 구현

임계구역에 대한 요구사항

• 임계 구역을 만들 때 내부를 어떻게 설계해야 제대로 임계구역을 만든 것인가?
• Mutex (상호 배제, **MUTual EXclusion)** : 한 프로세스가 임계 구역을 실행 중일 때는 다른 어떤 프로세스도 임계구역을 실행할 수 없다.
• 진행 : 임계구역을 실행하는 프로세스가 없고 여러개의 프로세스들이 임계구역에 들어오려고 시도하면 이 중 하나의 프로세스만 선택하는 '결정 기법'이 있어야 하며, 이러한 결정은 무한정 미뤄져선 안된다.
• 제한된 대기 : 한 프로세스가 임계 구역에 대한 진입을 요청하고 요청이 수락될 때까지, 다른 프로세스가 임계구역을 실행하는 횟수에는 제한이 있어야 한다. 어떤 프로세스든 일정 시간 내에는 임계구역에 들어갈 수 있도록 다른 프로세스에 제한을 줘야 한다.

mutex의 잘못된 구현

enter_mutex(lock){ //entry section
    while (lock == true) ;
    lock = true;
}
// 임계구역
exit_mutex(lock) { // exit section
    lock = false;
}

• 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; 
} 

void* thread_body(void* arg) 
{ 
    long t_id = (long)arg; // i를 t_id로 넘겨준다.

    usleep(rand() % 0xFFFFF); // 랜덤한 값을 넣어 sleep

    lock(t_id); // lock 시도

    // Critical Section (임계구역)
    use_resource(t_id); 

    unlock(t_id); // lock 해제

    return NULL; 
} 

void use_resource(int t_id) 
{ 
    counter++; 
    usleep(rand() % 0xFFFF); 
    counter++; 
    usleep(rand() % 0xFFFF); 
    counter--; 
    usleep(rand() % 0xFFFF); 
    counter--; 
    usleep(rand() % 0xFFFF); 
    counter++; 
    usleep(rand() % 0xFFFF); // 결과적으로는 counter 1증가

    printf("   %d\t       %d\t   %d\n", numbers[t_id], t_id, counter); 
    fflush(stdout); 
} 

void lock(int t_id) 
{ 
    choosing[t_id] = 1; // choosing을 1로 설정하고 번호표 생성

    int max = 0; 

    for (int i = 0; i < THREAD_COUNT; ++i) { 
        max = numbers[i] > max ? numbers[i] : max; 
    } 
    numbers[t_id] = max + 1; 

    choosing[t_id] = 0; // 번호표 받았으면 0으로 돌려놓음

    for (int j = 0; j < THREAD_COUNT; ++j) { 

        while (choosing[j]); // 번호를 아직 안받은 것은 대기해준다.

        while (numbers[j] != 0 
            && (numbers[j] < numbers[t_id] 
            || (numbers[j] == numbers[t_id] && j < t_id))) { 
        } // unlock이 완료된 것은 0으로 처리되어있으니 넘기고, 나머지에 대해 알고리즘 처리
    } 
} 

void unlock(int t_id) 
{ 
    numbers[t_id] = 0; // 완료처리
} 

---

HW적 mutex 구현1 : test and set

int Test-and-Set (int *target) {
    int temp;
    temp = *target ; // target이 되는 전역변수
    *target = 1 ; //true
    return temp;
}

/* before critical section */
while (Test-and-Set ( &lock ));
// critical section
lock = 0;
/* after critical section */

• 핵심 원리는 프로그래밍 코드를 하나의 CPU 명령어(인스트럭션)으로 만들어 제공함으로써, 문맥교환없이 atomic하게 수행되도록 하는 것이다.
• Test-and-Set 함수는 단순히 target값(lock)을 포인터로 받고, 해당 값을 리턴해준다.
• 어떤 쓰레드가 임계구역을 빠져나가면서 lock을 0으로 만들면, 해당 인스트럭션에서 제일 먼저 수행시키게 되는 쓰레드 하나만 0을 리턴받아 임계구역에 진입하게 된다. 나머지는 1로 설정된다. 코드 전체가 한 인스트럭션에 끝나기 때문에 값이 꼬이게 될 염려도 없다.

---

HW적 mutex 구현2 : Swap

void Swap (int *a, int *b) {
    int temp;
    temp = *a ;
    *a = *b ;
    *b = temp ;
}

key = 1;
do {
    Swap(&lock,&key) ;
} while (key == 1);
// critical section
lock = 0 ; // false

• test and set 방식과 마찬가지로 하나의 CPU 명령어로 되어 있어 atomic하게 수행된다.
• Swap 함수는 말그대로 두 값을 받아 swap 해준다.
• lock의 값과 key값을 바꾸고, key값이 1일 동안은 반복된다.
• 어떤 쓰레드가 임계구역을 빠져나가면서 lock을 0으로 만들면, 해당 인스트럭션에서 제일 먼저 수행시키게 되는 쓰레드 하나가 lock을 0으로 만들고, 이를 swap 하면서 key는 0, lock은 1이 된다. 나머지는 lock이 1로 설정되어 있어 값을 처리할 수 없고, 해당 쓰레드는 임계구역에 진입해 작업을 수행한다.

---

HW적 mutex 구현2-1 : compare and swap

void compare_and_swap (int *value, int expected,int new_value) {
    int temp = *value;
    if(*value == expected)
        *value = new_value;
    return temp;
} 

while (compare_and_swap(&lock, 0, 1));
// critical section;
lock = 0 ; // false

• swap 방식에서 용도를 조금 확장한 버전이다.
• value, expected, new_value를 파라미터로 받아 만약 value와 expected가 같지 않으면 현재의 value를 리턴하고, 같으면 value를 new_value로 설정하고 이전의 value를 리턴한다.
• 만약 value가 1이면 1을 리턴하지만, 0일 경우 해당 value를 1로 바꾸고 0을 리턴해준다.
• 지금까지와 유사한 원리로 mutex가 실현된다.

---

HW적 mutex 구현3 : 인터럽트 통제

interrupt-disable;
// critical section
interrupt-enable;

• interrupt-disable과 interrupt-enable을 사용하는 방법이다.
• 임계구역을 수행하지 않도록 하기 위해 인터럽트 자체를 diable시킨다.
• interrupt-disable과 interrupt-enable은 커널모드에서만 사용가능한 특권명령어이다. 따라서 커널 내의 시스템 호출 부와 인터럽트 처리기의 임계구역을 보호하기 위해 사용할 수 있다. 물론 interrupt-disable 기간이 길어져선 안되니, 적당한 짧은 시간동안만 사용해야 한다.