[Chapter 3] 개념 이해를 위한 운영체제 [병행성

CS/운영체제

[Chapter 3] 개념 이해를 위한 운영체제 [병행성 - 임계 영역]

devrabbit22 2025. 2. 24. 17:25

프로세스의 영역 중에서 공유 자원을 접근하는 코드 영역을 임계 영역"(critical section)" 이라고 부르며, 어떤 프로세스가 이 영역을 실행하고 있을 때 그 프로세스가 "임계 영역에 있다"고 말한다.

ex) 공유 변수(buffer, counter)를 접근하는 코드 영역이 임계 영역에 해당되며, 생산자 프로세스의 counter = counter+1 문장이 실행되고 있을 때 생산자 프로세스가 "임계 영역에 있다"고 말한다. 마찬가지로 소비자 프로세스의 counter = counter-1 문장이 실행되고 있을 때 소비자 프로세스가 임계 영역에 있다"고 말한다.

주의할 점

모든 프로세스가 임계 영역을 가지고 있는 것은 아니다. 그러나 자원을 공유하면서 병해적으로 실행되는 프로세스들은 반드시 임계 영역을 가지고 있다. 따라서 임계 영역이 존재하는 프로세스의 결정성이 보장되기 위해서는 임계 영역이 상호 배제적으로 실행되어야 한다.

즉, 한 프로세스가 임계 영역에 있으면 다른 프로세스는 임계 영역에 진입하지 못하도록 하는 동기화 기법이 요구된다. 그렇지 않을 경우 프로세스의 경쟁 조건이 발생하게 되어 결정성을 보장할 수 없다.

진입 영역(entry section)은 프로세스가 임계 영역에 진입을 요청하는 부분이고, 출구 영역(exit section)은 임계 영역에서 빠져 나왔음을 알리는 부분이다. 그리고 잔류 영역(remainder section)은 임계 영역과 무관한 영역이다.

임계 영역의 문제에 대한 해결책

기본적으로 어떤 프로세스가 임계 영역의 실행이 시작되면 임계 영역의 실행이 완료될 때까지 문맥교환이 발생하지 않도록 진입 영역과 출구 영역에서 적절한 조치를 취하는 것으로써 3가지 조건을 만족시켜야 한다.

상호 배제(mutual exclusion) 조건 : 어떤 프로세스가 임계 영역에 있으면 다른 프로세스는 임계 영역에 진입할 수 없다. 즉, 두 개 이상의 프로세스가 임계 영역에 동시에 존재해서는 안된다.
진행(progress)조건 : 임계 영역에 있는 프로세스가 하나도 없을 경우 임계 영역에 진입하려는 프로세스가 반드시 임계 영역에 진입할 수 있어야 한다. 즉, 어느 프로세스도 임계 영역에 진입하지 못하도록 해서는 안된다.
제한된 대기(bounded waiting) 조건 : 어떤 프로세스가 임계 영역 진입을 요청한 후 진입이 허락될 때까지 다른 프로세스에게 진입이 허락되는 횟수에 제한이 있어야 한다. 즉, 어떤 프로세스가 임계 영역에 진입을 원할 경우 무한정 기다리게 해서는 안된다.

소프트웨어 방법

두(N=2) 프로세스 간 임계 영역

여러 개의 프로세스들 사이에서 임계 영역의 문제를 해결하기 위한 알고리즘은 매우 복잡하다. 따라서 두 프로세스(P0, P1)만으로 제한하여 본다.

알고리즘 -1 : Dekker 알고리즘-1

알고리즘-1은 Dekker가 제안한 방법으로 하나의 공유변수(turn)를 사용하여 두 프로세스(P0, P1)사이의 임계 영역이 상호 배제적으로 실행될 수 있도록 한다.

잔류 영역
while(trun != 0)
;
임계 영역
turn = 1;
잔류영역

(a) 프로세스 (P0)

잔류 영역
while(turn != 1)
;
임계 영역
turn = 0;
잔류 영역

(b) 프로세스 (P1)

공유 변수 turn의 값은 임계 영역에 진입할 수 있는 프로세스 번호를 의미한다. 임계 영역에 진입하려는 프로세스는 진입 영역에서 turn 값을 검사하여 임계 영역으로의 진입 여부를 판단한다.

프로세스 P0은 진입 영역에서 turn 값이 0이면 임계 영역으로 진입하고 아니면 turn 값이 0이 될 때 까지 기다리게 된다. 또한 임계 영역을 실행한 후 출구 영역에서는 turn 값을 1로 설정한다. 마찬가지로 프로세스 P1은 진입 영역에서 turn 값이 1이면 임계 영역으로 진입하고 아니면 turn 값이 1이 될 때 까지 기다리게 된다. 또한 임계 영역을 실행한 후 출구 영역에서는 turn 값을 0으로 설정한다. 이와 같이 교대로 프로세스의 임계 영역을 실행함으로써 임계 영역의 상호 배제 조건을 만족한다. 그러나 프로세스 P0이 임계 영역을 실행한 후 또 다시 임계 영역의 진입을 원할 경우 임게 영역에 존재하는 프로세스가 없음에도 불구하고 임계 영역에 진입할 수 없기 때문에 진행 조건을 만족시키지 못한다. 결국 P1이 임계 영역을 실행한 후 turn값이 0이 될 때 까지 무한정 기다려야 하기 때문에 제한된 대기조건을 만족시키지 못한다.

2. 알고리즘 - 2 : Dekker 알고리즘 -2

알고리즘-2는 알고리즘-1의 문제점을 보완하기 위하여 Dekker가 제안한 방법으로 두 개의 공유 변수(flag[0], flag[1])를 사용하여 두 프로세스(P0, P1) 사이의 임계 영역에 상호 배제적으로 실행될 수 있도록 한다. 두 개의 공유 변수는 상대 프로세스가 임계 영역에 있는지를 판단하기 위하여 각 프로세스의 상태를 표시한다.

잔류 영역
flag[0] = TRUE;
while(flag[1])
;
임계 영역
flag[0] = FALSE;
잔류 영역

(a) 프로세스 (P0)

잔류 영역
flag[1] = TRUE;
while(flag[0])
;
임계 영역
flag[1] = FALSE;
잔류 영역

(b) 프로세스 (P1)

두 프로세스(P0, P1)의 상태, 곧 임계 영역 진입 여뷰를 표시하기 위한 flag[0]과 flag[1]의 초기 값은 모두 FALSE로 선언된다. 각각의 프로세스는 임계 영역에 진입하기 위하여 진입 영역에서 자신의 flag 값을 TRUE로 설정한 후 상대방 프로세스의 flag 값을 검사해본다.

프로세스P0은 진입 영역에서 자신의 flag[0] 값을 TRUE로 설정한 후 상대방의 flag(1) 값이 FALSE이면 임계 영역으로 진입하고, 아니면 flag[1] 값이 FALSE로 될 때까지 기다리게 된다. 또한 임계 영역을 실행한 후 출구 명령에서는 자신의 flag[0] 값을 FALSE로 설정한다. 이와 같이 두 프로세스는 상대 프로세스의 임계 영역 진입 여부를 파악함으로써 임계 영역을 상호 배제적으로 실행하면서 알고리즘-1의 재진입 문제가 해결되었음을 알 수 있다.

그러나 프로세스 P0이 임계 영역에 진입하기 위하여 flag[0]을 TRUE로 설정한 후 문맥교환이 발생할 경우 P1은 자신의 flag[1]을 TRUE로 설정한 후 임계 영역에 진입하기 위하여 flag[0]을 검사할 것이다. 이 경우 flag[0]이 TRUE이기 떄문에 임계 영역에 진입하지 못하게 된다. 다시 P0이 임계 영역에 진입하기 위하여 flag[1]을 검사하면 그 값이 TRUE이기 때문에 임계 영역에 진입하지 못한다. 결국 임계 영역에 진입된 프로세스가 없음에도 두 프로세스(P0, P1) 모두 임계 영역에 진입할 수 없으며 무한정 기다리게 됨으로 진행 조건과 제한된 대기 조건을 만족시키지 못한다. 따라서 알고리즘 - 2도 완전한 해결책이 아니다.

알고리즘-3 : Peterson 알고리즘

Peterson이 제시한 방법으로 알고리즘 1과 알고리즘 2를 혼합하여 두 프로세스(P0, P1) 사이의 임계 영역 문제를 해결하기 위한 세 가지 조건(상호 배제, 진행, 제한된 대기)을 모두 만족한다. 공유 변수(turn, flag[2])는 알고리즘1과 알고리즘 2에서 사용한 것과 동일하다.

잔류 영역
flag[0] = TRUE;
turn = 1;
while(flag[1] && turn ==1)
;
임계 영역
flag[0] = FALSE;
잔류 영역

(a)프로세스 (P0)

잔류 영역
flag[1] = TRUE;
turn = 0; while(flag[0] && turn == 0)
;
임계 영역
flag[1] = FALSE;
잔류 영역

(b) 프로세스 (P1)

각각의 프로세스는 진입 영역에서 자신의 flag를 TRUE로 설정함으로써 임계 영역에 있음을 선언하고 turn을 상대 프로세스로 지정한 후 상대 프로세스의 flag및 turn을 검사해 본다. 상대 프로세스의 flag가 TRUE 이면서 turn이 상대 프로세스이면 진입 영역에서 기다린다. 출구 영역에서는 자신의 flag를 FALSE로 설정함으로써 임계 영역에서 나왔음을 선언한다.

상호 배제(mutual exclusion) 조건
프로세스 P0은 flag[1] 값이 FALSE 또는 turn이 0이면 임계 영역으로 진입하고 프로세스P1은 flag[0]이 FALSE 또는 turn이 1이면 임계 영역으로 진입한다. 만약 두 프로세스(P0, P1)가 동시에 임계 영역 진입을 원하여 flag[0]과 flag[1]이 모두 TRUE일지라도 turn은 0 아니면 1이 되기 때문에 항상 어느 한 프로세스만이 임계 영역에 진입하게 된다. 따라서 상호 배제 조건을 만족한다.
진행 조건(progress) 조건
프로세스P0이 임계 영역을 실행한 후 반복해서 임계 영역으로 재진입을 원할 경우 진입 영역에서 자신의 flag[0]을 TRUE로 turn을 1로 설정한 후 임계 영역의 진입 가능성을 검사한다. 검사 결과 flag[1]이 여전히 FALSE 이면서 turn이 1이기 때문에 재진입이 가능하다. 따라서 진행 조건을 만족한다.
제한된 대기(bounded waiting)조건
프로세스 P0이 임계 영역을 실행하는 동안 문맥 교환이 발생할 경우 임계 영역으로 진입하려는 프로세스 P1은 자신의 flag[1]을 TRUE로 설저앟고 turn을 0으로 변경한 후 대기하게 된다. 이 경우 프로세스 P0이 임계 영역을 실행한 후 출구 영역에서 자신의 flag[0]을 FALSE로 변경함으로써 프로세스 P1이 임계 영역에 진입할 수 있게 된다. 만약 프로세스 P0이 반복해서 임계 영역 재진입을 우너하게 되면 자신의 flag[0]을 TRUE로 설정하고 turn을 1로 변경한 후 임계 영역의 진입 가능성을 검사한다. 검사 결과 flag[1]을 TRUE이기 때문에 프로세스 P0은 대기하고 프로세스 P1이 임계 영역에 진입하게 된다. 따라서 임계 영역 진입을 요청한 프로세스 P1이 프로세스는 무한정 기다리지 않게 됨으로 제한된 대기 조건을 만족한다.

다중(N>2) 프로세스 간 임계 영역

다중 프로세스 간 임계 영역에 대한 알고리즘은 제과점이나 은행에서 서비스 순서를 결정하는 방법과 유사하기 때문에 "제과점 알고리즘"이라고도 부른다.(제과점이나 은행에서 들어온 순서대로 곡겍에게 일련의 번호표를 부여한 후 낮은 번호의 고객을 먼저 서비스한다.)
배열 choosing[n]과 number[n]은 공유 변수로써 모든 프로세스에 대한 임계 영역 진입 여부와 부여받은 번호를 나타낸다.
배열의 초기 값은 각각 FALSE 0으로 선언한다.

잔류 영역
choosing[i] = TRUE;
number[i] = max(number[0], number[1],...,number[n-1])+1;
choosing[i] = FALSE;
for(j=0; j<n; j++){
while(choosing[j])
;
while((number[j]!=0) && ((number[j], j) < number[i], i))
}

프로세스 (Pi)의 구조

임계 영역 진입을 원하는 프로세스는 진입 영역에서 자신의 choosing을 TRUE로 설정하고 번호를 부여받은 후에는 FALSE로 변경한다. 이 때 number는 이미 다른 프로세스에게 부여된 가장 큰 값보다 하나 큰 값이 부여된다 .그러나 여러 개의 프로세스가 비동기적으로 실행됨으로 동일한 번호가 부여될 수 있음을 유의해야 한다.

문장 for 내부에서는 모든 프로세스에게 부여된 번호를 비교하여 가장 작은 번호의 프로세스를 임계 영역으로 진입시킨다. 만약 프로세스에게 부여된 번호가 동일할 경우 프로세스 번호를 비교하여 번호가 작은 프로세스를 우선적으로 임계 영역에 진입하도록 한다. 또한"(number[j], j) < (number[i], i)"는 Pj에게 부여된 번호(number[j])가 pi에게 부여된 번호 (number[i])보다 작고 pj의 프로세스 번호 (j)가 pi의 프로세스 번호(i)보다 작음을 의미한다.

하드웨어 방법

하드웨어에 의한 방법은 CPU에서 제공하는 명령어(instruction)를 이용하여 임계 영역의 문제를 해결하는 것이다. 일반적으로 MOV, ADD와 같은 CPU 명령어가 처리되고 있는 동안에는 인터럽트 혹은 어떠 사건에 의해 문맥 교환이 발생하지 않는다.

Test-and-Set 명령어
CPU 명령어인 test and set을 사용하면 임계 영역 문제를 보다 쉽게 해결할 수 있다.

bool Test_and_Set(bool *lock){
bool ret = *lock;
*lock = TRUE;
return ret;
}

Test-and-Set 명령어

Test-and-Set 명령어는 형식 인자로써 bool형 포인터 변수 (*lock)을 사용하고 있다. 따라서 이 명령어를 호출할 때 주소 값을 전달하는 실 인자자(actual argument)를 플요로 한다. 이 명령어가 호출되면 변수(*lock)에 현재 값을 반환하고, 변수 (*lock)은 TRUE로 설정된다. 다시 말해 (*lock)값이 FALSE 이라면 FASLE 값이 반환되고 TRUE이라면 TRUE 값이 반환되고 (*lock) 값은 TRUE로 설정될 것이다.

중요한 사실은 이러한 일련의 연산을 수행하는 명령어가 CPU 내부에서 실행되는 동안에는 인터럽트나 어떤 사건에 의해 문맥 교환이 발생하지 않는다는 것이다.

잔류 영역
while(Test_and_Set(&flag));
임계 영역
flag = FALSE;
잔류 영역

Test-and-Set 명령어를 이용한 알고리즘 - 1

임계 영역의 진입 조건은 flag 값이 FALSE이어야 한다. 공유 변수 실 인자 flag의 초기 값은 FALSE로 선언한다. 임계 영역 진입을 원하는 프로세스스는 진입 영역에서 Test-and-Set 명령어를 호출하여 현재 flag 값을 검사한다. Test-and-Set 명령어는 현재 flag 값을 반환하고, flag의 값을 TRUE로 설정할 것이다. 어떤 프로세스가 임계 영역에 존재할 경우 TRUE 값이 반환될 것이다. 따라서 반환 값이 FALSE이면 임계 영역에 진입하고 TRUE이면 대기한다.

이 알고리즘은 임계 영역 진입을 원하는 프로세스가 여러 개 있을 경우 오직 하나의 프로세스만이 임계 영역에 진입할 수 있으며, 임계 영역을 실행하는 프로세스가 하나도 없을 경우 항상 진입할 수 있고, 임계 영역을 실행하는 프로세스가 하나도 없을 경우에 항상 진입할 수 있기 때문에 상호 배제조건과 진행 조건을 만족한다.

그러나 특정 프로세스가 임계 영역을 반복해서 진입할 수 있기 때문에 제한된 대기조건은 만족시키지 못한다.

잔류 영역
waiting[i] = TRUE;
key = TRUE;
while(waiting[i] && key) key = Test_and_Set(*flag);
waiting[i] = FALSE;
임계 영역
j = (i+1) % N;
while((j != i) && (waiting[j] == FALSE))
j=(j+1) % N;
if(j == i) flag == FALSE;
else waiting[j] = FALSE;
잔류 영역

Test-and-Set 명령어를 이용한 알고리즘 - 2 (제한된대기조건을 만족시키는 알고리즘)

프로세스 수(N) 크기의 배열 waiting[N]과 변수 flag는 공유 변수로써 초기 값은 False로 선언한다. 임계 영역과 진입을 원하는 프로세스 Pi는 진입 영역에서 자신의 waiting[i] 값과 key 값을 TRUE로 설정한 후 임계 영역 진입 조건을 검사한다.

임계 영역 진입 조건은 자신의 waiting[i]값이 FALSE이거나 key 값이 FALSE이어야 한다. 이 때 waiting[i]값이 FALSE가 되려면 다른 프로세스가 임계 영역을 실행한 후 출구 영역에서 변경해 주어야 한다 .또한 key 값이 FALSE가 되려면 TEst-and-Set 명령어를 호출하여 현재 flag값이 FASLE이어야 한다.

만약 프로세스 Pi가 임계 영역에 진입할 경우 flag 값은 TRUE로 설정되어 다른 프로세스 Pi는 임계 영역에 진입할 수 없으며 프로세스 Pi가 임계 영역을 실행한 후 출구 영역에서 waiting[j] 값을 FALSE로 변경해 주어야 한다. 따라서 이 알고리즘은 임계 영역 진입을 원하는 프로세스가 여러 개 있을 경우 옺기 하나의 프로세스만이 임계 영역에 진입할 수 있으며 임계 영역을 실행하는 프로세스가 하나도 없을 경우에 항상 진입할 수 있기 때문에 상호 배제 조건과 진행 조건을 만족한다.

또한 프로세스 Pi가 임계 영역에 있을 때 또 다른 프로세스 Pj가 임계 영역 진입을 원하게 되면 프로세스 Pj는 자신의 waiting[j]값과 flag 값을 TRUE로 설정하고 대기하게 된다. 이 경우 프로세스(i+1, i+2, ... N-1, 0, 1, ... i-1)에 대한 waiting[]값을 조사하여 waiting[] 값이 TRUE인 프로세스 Pj의 flag[j] 값을 FALSE로 변경해 줌으로써 프로세스 Pj가 임계 영역에 진입할 수 있게 된다. 따라서 임계 영역에 진입하기 위해 대기 중인 프로세스는 최대 N-1 번째 안에는 진입할 수 있기 때문에 제한된 대기 조건을 만족한다.

SWAP 명령어

CPU 명령어 (Swap)를 이용하게 되면 임계 영역 문제를 보다 쉽게 해결할 수 있다.

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

Swap 명령어

Swap 명령어는 형식 인자로써 정수형 포인터 변수(*a, *b)를 사용하고 있다. 따라서 이 명령어를 호출할 때 두 개의 주소 값을 전달하는 실 인자를 필요로 하며 이 명령어가 호출되면 두 개의 실 인자 값은 서로 교환된다.
여기에서 중요한 사실은 이러한 일련의 연산이 실행되는 동안에 인터럽트나 다른 사건에 의해 문맥 교환이 발생하지 않았다는 것이다.

잔류 영역
key = TRUE;
while(key) Swap(&flag, &key);
임계 영역
flag = FALSE;
잔류 영역

Swap 명령어를 이용한 알고리즘

실 인자 flag은 공유 변수로써 초기 값은 FALSE로 선언한다. 임계 영역 진입을 원하는 프로세스는 진입 영역에서 key 값을 FALSE 로 선언한다. 임계 영역 진입을 원하는 프로세스는 진입 영역에서 key 값을 TRUE로 설정한 후, Swap 명령어를 호출하여 임계 영역의 진입 여부를 검사한다. 임계 영역의 진입 조건은 key 값이 FALSE이어야 한다. 여기에서 key 값은 Swap 명령어 내부의 flag 값에서만 변경된다. 결국 현재 flag 값이 FALSE일 경우에만 임계 영역에 진입할 수 있다.

다른 프로세스가 임계 영역에 진입할 경우 현재 flag 값은 TRUE 이기 때문에 임계 영역에 진입할 수 없다. 따라서 이 알고리즘은 임계 영역 진입을 원하는 프로세스가 여러 개 있을 경우 오직 하나의 프로세스 만이 임계 영역에 진입할 수 있으며 임계 영역을 실행하는 프로세스가 하나도 없을 경우에 항상 진입할 수 있기 때문에 상호 배제 조건과 진행 조건을 만족한다.

그러나 특정 프로세스의 반복적인 임계 영역 진입을 제한할 수 없기 때문에 제한된 대기 조건은 만족시키지 못한다.

세마포어 방법

세마포어(semaphore)는 임계 영역의 문제 해결하기 위한 가장 일반적으로 사용되고 있는 소프트웨어 방법으로써 네덜란드의 Dijkstra가 제안하였다. 세마포어는 초기 값을 부여한 후, 오직 P, V 연산자에 의해서만 변경할 수 있는 정수형 변수이다. 여기서 연산자 이름 P, V는 네덜란드어의 Proberen(검사하다)과 Verhogen(증가하다)에서 유래한 것이며, 각각 영어의 Wait(기다리다)와 Signal(신호를 전하다)의 의미를 가지고 있다.

ex) 세마포머 변수 S에 대한 P(S), V(S)의 연산은 다음과 같이 정의한다.

P(S): while(S<=0);
S = S - 1;
V(S): S = S + 1;

일반적으로 세마포어는 운영체제에서 제공하기 때문에 P, V 연산이 실행되는 동안에는 인터럽트 혹은 어떤 사건에 의해 문맥 교환이 발생하지 않음을 가정한다.
위와 같이 정의된 P, V 연산자를 이용할 경우 임계 영역의 상호 배제 알고리즘은 매우 간단하다.

잔류 영역
P(mutex);
임계 영역
V(mutex);
잔류 영역

세마포어에 의한 상호 배제 알고리즘 - 1

세마포어 변수(mutex)의 초기 값은 공유될 수 있는 동일한 자원의 개수 즉, 임계 영역에 동시에 진입될 수 있는 프로세스 혹은 스래드의 수를 의미한다. 여기에서는 오직 하나의 프로세스 혹은 스래드 만이 임계 영역에 있을 수 있다고 가정하여 초기 값을 1로 선언한다.
어떤 프로세스가 임계 영역으로 진입을 원할 경우, 진입 영역에서 P(mutex) 연산을 수행함으로써 현재 mutex의 값을 검사한다. 만약 mutex의 값이 0보다 작거나 같으면 대기할 것이고, 0보다 클 경우에는 mutex 값을 1 감소하고 임계 영역으로 진입할 것이다.
출구 영역에서는 mutex 값을 1 증가함으로써 다른 프로세스로 하여금 임계 영역에 진입할 수 있도록 한다.
이 알고리즘은 임계 영역으로 진입을 원하는 프로세스가 여러 개 있을 경우 오직 하나의 프로세스 만이 임계 영역에 진입할 수 있으며 임계 영역을 실행하는 프로세스가 하나도 없을 경우에도 항상 진입할 수 있기 떄문에 상호 배제 조건과 진행 조건을 만족한다. 그러나 특정 프로세스의 반복적인 임계 영역 진입을 제한할 수 없기 떄문에 제한된 대기 조건은 만족시키지 못한다. 또한 P, V 연산자를 이용할 경우 ,프로세스들의 실행 순서를 제어하는 동기화 문제도 쉽게 해결할 수 있다.
ex)S1과 S2를 각각 포함하고 있는 두 개의 병행 프로세스(P1, P2)에서 문장 S1이 S2보다 반드시 먼저 실행되어야 할 경우, 세마포어 변수(synch)를 이용하여 항상 문자 S1이 S2 보다 먼저 실행되도록 제어할 수 있다.

S1;
V(synch);
:

(a) 프로세스 (P1)

:
P(synch);
S2;

(b) 프로세스 (P2)

두 프로세스 간의 동기화

세마포어 변수(synch)의 초기 값은 0으로 선언 한다. 만약 프로세스가 P2가 먼저 실행되더라도 P(synch)연산에 의해 문장 S2는 실행되지 않을 것이다.
오직 프로세스 P1이 V(synch)연산을 수행한 후에만 실행될 수 있으므로 항상 문장(S1이 S2보다 먼저 실행되도록 제어할 수 있다)
소프트웨어, 하드웨어 명령어, 그리고 세마포어를 이용한 알고리즘들은 어떤 프로세스가 임계 영역에 있을 경우 임계 영역에 진입을 원하는 프로세스는 진입 영역에서 무한 루프를 돌면서 진입 조건이 만족될 때까지 진입 조건을 반복적으로 검사하게 된다. 그러나 진입 조건은 임계 영역에 있는 프로세스가 임계 영역을 벗어날 때에 만족될 수 있다. 이와 같이 어떤 프로세스가 CPU를 사용하면서 무한정 기다리는 현상을 '바쁜 대기(busy waiting)' 혹은 '스핀 록(spin lock)'이라고 부른다. 이러한 현상은 CPU의 이용률을 저하기키는 요인이 되기 때문에 이를 해결하기 위한 방법이 필요하다.
바쁜 대기 현상을 해결하기 위하여 어떤 프로세스가 진입 영역에서 진입 조건을 만족하지 않으면 그 프로세스는 대기 상태로 변환되어 대기 큐에서 기다리도록 한다. 출구 영역에서는 대기 큐에서 임계 영역에 진입을 기다리고 있는 프로세스가 있으면 그 프로세스를 준비 상태로 변환시킴으로써 임계 영역에 진입하도록 한다. 이러한 방법을 구현하기 위하여 세마포어 변수(S)와 P(S), V(S) 연산자를 정의한다.

struct{
integer value;
struct pcb *ptr;
}S;

P(S): S.value = S.value-1;
if(S.value < 0){
이 프로세스를 S.ptr에 등록:
block();
}

V(S):S.value = S.value+1;
if(S.value <= 0 ){
S.ptr로부터 프로세스(P)를 제거;
wakeup(P);
}

바쁜 대기를 해결하기 위한 세마포어

세마포어 변수(S)는 정수형 value와 포인터 *ptr로 구성된 구조체로 선언한다. S.value는 세마포어 값을 나타내며 S.ptr은 임계 영역에 진입하려다 대기 상태로 변환된 프로세스들이 기다리고 있는 대기 큐의 주소를 가리킨다. P(S) 연산은 S.value 값을 1 감소시킨다. 만약 그 값이 0보다 작으면 그 프로세스는 대기 큐에 등록되고 함수 block()을 호출한다. 반면 V(S)연산은 S.value값을 1 증가시킨다. 만약 그 값이 0보다 작거나 같으면 대기 큐에 등록된 프로세스(P)를 선택하여 wakeup(P)을 호출한다. P(S) 연산 내부에서 block()함수를 호출함으로써 대기 큐에서 기다리고 있던 하나의 프로세스(P)를 준비 상태로 변환시켜 준다.
여기에서 S.value 값이 양수일 경우, 사용 가능한 공유 자원의 개 수 즉, 임계 영역에 진입할 수 있는 프로세스의 수를 의미한다. 반면 음수일 경우, 그 절대 값은 대기 쿠에서 기다리고 있는 대기 상태의 프로세스의 수를 의미한다.
ex) S.value값이 5라면 5개의 프로세스가 임계 영역에 진입할 수 있음을 의미하고, -5라면 임계 영역에 진입하려다 대기 상태로 변환된 프로세스가 5개 있음을 의미한다.

Reference

개념 이해를 위한 운영체제

https://thdbs523.tistory.com/143

[운영체제/OS] 임계 영역(critical section)

임계 영역(critical section) :프로세스 영역 중에서 공유 자원을 접근하는 코드 영역. (즉 공유 자원에 접근했을 때를 '임계 영역에 있다'고 말함) 모든 프로세스가 임계 영역을 가지고 있는 것은 아

thdbs523.tistory.com

'CS > 운영체제' 카테고리의 다른 글

[Chapter 3] 개념 이해를 위한 운영체제 [병행성 - 리눅스 병행성] (0)	2025.02.25
[Chapter 3] 개념 이해를 위한 운영체제 [병행성 - 프로세스 간 통신] (0)	2025.02.25
[Chapter 3] 개념 이해를 위한 운영체제 [병행성 - 개요] (0)	2025.02.24
[Chapter 2] 개념 이해를 위한 운영체제 [프로세스] (0)	2025.02.20
[Chapter 1] 개념 이해를 위한 운영체제 [운영체제] (0)	2025.02.20

현재글[Chapter 3] 개념 이해를 위한 운영체제 [병행성 - 임계 영역]

devrabbit22 님의 블로그

devrabbit22 님의 블로그 입니다.

네트워크 관련 기초 용어, 교환 시스템, 네트워크 기초 용어, 코딩테스트, 백준, Baekjoon, 네트워크의 기초 용어, 쉽게 배우는 데이터 통신과 컴퓨터 네트워크, 쉽게 배우는 데이터 통신과 네트워크, 네트워크 모델,

Today :
Yesterday :

일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

devrabbit22 님의 블로그