Critical Resource
임계 자원
한번에 하나의 Process만 접근할 수 있는 공유되는 Resource
Thread, Process는 각각의 Thread, Process들 간 공유하는 Sharing Resource들이 있음 ( ex : 프린터 )
Critical Section
Critical Resource에 접근하는 코드 영역
Critical Section Problem
Mutual Exclusion
만약 Process가 Critical Section에 접근할 때, 다른 Process들이 Critical Section에 접근할 수 없도록 해야 함
Progress
만약 어떤 Process도 Critical Section에 없고, Critical Section에 들어가길 원하는 다른 Process들이 존재한다면, 무기한으로 지연되어서는 안됨 => 진입할 수 있어야 함
Bounded Waiting
Bound, Limit, Time이 있으므로, Critical Section으로 들어가고자 한 Process를 무한정 대기시켜서는 안됨
동기화 접근
Naive approach (Incorrect)
1. 전역 Flag 변수를 두어서 사용 중이면 접근 못하도록 로직 체크
=> 만약 Flag를 변경하기 직전에 Scheduling이 되면 둘 다 접근할 수 있음
=> Mutual Exclusion 만족 X
// Occupied한 Process가 없을 때까지 수행되는 무한 반복문 While(1){ // Enter Critical Section if(Occupied == 0){ // 만약 Critical Section에 접근한 것이 없다면 Occupied를 1로 체크해서 사용 중임을 표시한 뒤 무한 반복문 탈출 // 만약 이 소스를 실행 시키는 Process들이 있을 때 // 조건문을 통과하고, 변수를 체크하기 전에, Scheduling으로 교체되어 버리면, // 다른 쪽에서는 접근한 것이 없는 줄 알고, Occupied를 1로 설정한 뒤 CS 영역에 들어가 작업을 수행할 것이고, // Scheduling으로 다시 돌아오더라도, 이 Process는 그냥 Occupied를 1로 설정한 뒤 탈출하여, CS 영역에 접근하여, CS 영역에 2개 이상의 Process가 접근할 수 있게 됨 Occupied = 1; break; } } // 여기서부터 Critical Section // Unlock, 접근 끝났으므로 다른 Process가 쓸 수 있도록 다시 변수를 되돌려 놓음 Occupied = 0;2. 각 Thread별 전역 변수를 두어서 각각의 Flag 변수를 설정
Mutual Exclusion은 만족했으나, Deadlock 발생할 수 있음 => Progress 불만족
// T0 Thread 코드 do { // 0번 Thread에서 CS에 접근할 의사가 있음을 설정 flag[0] = TRUE: // 만약 1번 Thread에서 CS에 접근할 의사가 있다면, 해제될 때까지 기다림 // 만약 여기서 변수를 True로 설정한 뒤 While문에 접근하기 전에 Scheduling이 돼서, T1에서 flag[1]이 True로 설정되면 // 모든 flag가 다 1로 설정되어 서로 접근하지 못하고 계속해서 막히는 현상 발생 => DeadLock // => Process들이 계속해서 CS에 접근하지 못하고 계속해서 대기함 => Progress 불만족 while ( flag[1] ); // 1번에서 CS에 접근할 의사가 없어지면 임계 영역에 접근 CRITICAL_SECTION // 접근 끝나고 해제 flag[0] = FALSE; } while (TRUE);// T1 Thread 코드 do { // 1번 Thread에서 CS에 접근할 의사가 있음을 설정 flag[1] = TRUE // 만약 0번 Thread에서 CS에 접근할 의사가 있다면, 해제될 때까지 기다림 while ( flag[0] ); // 0번에서 CS에 접근할 의사가 없어지면 임계 영역에 접근 CRITICAL_SECTION // 접근 끝나고 해제 flag[1] = FALSE; } while (TRUE);
3. Peterson’s
2번 접근 법에서 turn이라는 변수를 하나 두어 관리
만족하긴 하나 복잡함
아래의 코드는 오직 두 개의 Thread에 대한 제약, Multi Process에 대해서 이러한 접근으로 동기화를 유지하려면 복잡해짐
// T0 Thread 코드 do { // 0번 Thread에서 CS에 접근할 의사가 있음을 설정 flag[0] = TRUE: // 만약 1번 Thread에서 CS에 접근하려고 한다면 양보하겠다는 설정 turn = 1; // 만약 1번 Thread에서 CS에 접근할 의사가 있다면, 1번이 다 쓸 때까지 기다림 while ( flag[1] && turn == 1 ); // 1번에서 CS에 접근할 의사가 없어지면 임계 영역에 접근 CRITICAL_SECTION // 접근 끝나고 해제 flag[0] = FALSE; } while (TRUE);// T1 Thread 코드 do { // 1번 Thread에서 CS에 접근할 의사가 있음을 설정 flag[1] = TRUE: // 만약 0번 Thread에서 CS에 접근하려고 한다면 양보하겠다는 설정 turn = 0; // 만약 0번 Thread에서 CS에 접근할 의사가 있다면, 0번이 다 쓸 때까지 기다림 while ( flag[0] && turn == 0 ); // 0번에서 CS에 접근할 의사가 없어지면 임계 영역에 접근 CRITICAL_SECTION // 접근 끝나고 해제 flag[1] = FALSE; } while (TRUE);
=> SW로 동기화를 만족시키기는 어려움 => HW로 만족시켜야 함
HW적인 CS Problem 해결 방법
Disabling Interrupts
Single Processor에서 Race Condition의 주 원인은 예측할 수 없는 Scheduling Timing
=> 주원인인 Interrupt를 Disable 해서 Scheduling에 방해받지 않고, 실행할 수 있음
장점
단순함
단점
비효율적 ( Interrupt의 장점을 다 포기하는 등 문제 존재 )
다수 처리기에는 적합하지 않음
Test and Set (TAS)
Instruction Level에서 지원
Test : 옛날 Lock Value를 확인 Set : Lock에 새로운 Value를 Set
CS에 접근할 때 Lock을 위해 함수에 Lock 변수와 Lock을 설정한다는 의미의 1이라는 값을 넘겨 Lock을 세팅하고, 이전의 Lock Value를 받는데,
만약 반환된 값이 1이면 이미 다른 곳에서 사용하고 있다는 뜻이므로 계속 대기하고,
아니면 Lock을 걸었으므로, 탈출해서 CS 영역 접근
Compare And Swap
TAS와 유사, 기대 값이 추가됨
TAS에서 사용되는 인자는 피연산자, 새로 할당할 값이었다면
CAS는 피연산자, 기대값, 할당할 값을 넘겨서
피연산자 값이 기대값이랑 같을 때만 새로운 값을 할당하고, 아니면 할당하지 않음
단점
- Single Processor에서 Busy-Waiting ( 대기 ) 을 하기에 비효율적 ( CPU 낭비, Process Switch 비용과 비교해봐야 함 , 항상 비효율적이라고 단언할 수 X ) ( But Multi Processor에서는 그렇게 오래 기다리지 않아서 괜찮음 )
- Faireness가 좋지 않음 => FIFO를 보장하지 않음 (먼저 대기하고 있던 것이 선택되지 않을 수 있음)
