임계 구역과 임계 구역 해결 방법

2021. 10. 2. 00:51 

2022. 6. 22. 15:30 복습을 위한 수정 시작

 

프로세스는 독립적으로 작업을 할 수도 있고 공유된 자원을 가지고 공동 작업을 할 수도 있다고 이전 장에서 언급했다.

이번에는 본격적으로 여러 프로세스가 한정된 자원을 가지고 공동으로 작업을 할 때 발생할 수 있는 문제에 대해 알아보자.

공유자원

• 공유자원이란 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말한다.
• 공유자원은 여러 프로세스가 공동으로 이용하기 때문에 누가 언제 데이터를 읽거나 쓰느냐에 따라 그 결과가 달라질 수 있다.
•  따라서 프로세스들의 공유 자원 접근 순서를 정하여 예상치 못한 문제가 발생하지 않도록 해야 한다.
• 2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황을 '경쟁 조건이 발생했다'라고 한다.
• 경쟁조건이 발생하면 공유 자원 접근 순서에 따라 우리가 프로그램에 예상하는 실행 결과가 달라질 수 있다.
• 동일한 프로세스 내부에서 작업하는 모든 스레드가 사용하는 힙 영역이나 메서드 영역도 공유자원이다.

임계 구역

• 공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역을 임계 구역이라고 한다.
• 즉 공유 메모리를 참조하는 프로그램 코드이다.임계 구역이라는 의미의 영어 단어 critical Section 'critical'
  (앞으로의 상황에 영향을 미친다는 점에서)은 대단히 중요한 이라는 뜻으로,
  프로세스 실행 상황에서는 공유할 수 없는 자원이 중요한 자원이다.
• 임계 구역에서는 프로세스들이 동시에 작업할 수 없으므로,
  어떤 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역 밖에서 기다려야 한다.
  임계구역의 프로세스가 나와야 들어갈 수 있다.

생산자-소비자 문제

임계 구역과 관련된 전통적인 문제로 생산자-소비자 문제가 있다.

생산자-소비자 문제에서는 생산자 프로세스와 소비자 프로세스가 서로 독립적인 작업을 한다. 문제를 간단히 말로 설명해보겠다.

버퍼 하나가 존재한다. 생산자는 계속해서 문제를 버퍼에 넣고 소비자는 계속 버퍼에서 물건을 가져온다.

우리는 작업을 계속하기 위해 원형 버퍼를 사용한다. 우리는 또한 버퍼가 가득 찼는지 파악하기 위해 sum이라는 전역 변수를 사용한다. sum에는 버퍼에 있는 상품의 총수가 저장된다.  (생산자, 소비자 프로세스 관계를 협력 프로세스라고도 한다.)

그냥 보면 문제가 없어 보인다. 하지만 문제가 있다.

1. 생산자가 버퍼 4번째 칸에 물건 하나를 집어넣었다. sum은 4로 바뀌어야 하나 아직 바뀌지 못했다. (현재 sum은 3)
2. 소비자가 물건 하나를 소비했다. sum을 2로 바꿔야 하나 아직 바꾸지 못했다. (현재 sum은 3)
3. 이 상태에서 생산자의 sum=sum+1과 소비자의 sum=sum-1이 거의 동시에 실행되면 문제가 발생한다. 생산자와 소비자가 독립적이기 때문에 상대방이 sum을 바꾸려는 것을 모른 채 현재 상태인 sum=3을 읽어서 작업을 한다.
4. 미세한 시간 차를 두고 위 예시의 어느 순서대로라도 실행되면 sum값은 2나 4가 된다.

임계구역 해결 조건

• 임계구역 문제를 해결하는 방법은 크게 3가지 조건이 있다.
• 상호 배제 : 한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없다.
• 한정 대기 : 임계 구역에서 작업중인 프로세스가 나오기를 기다리면서, 무한 대기를 하면 안된다.
• 진행의 융퉁성 : 한 프로세스가 다른 프로세스의 진행을 방해해서는 안 된다.
• 이중에서도 상호 배제는 정말 중요하다.

상호 배제 Mutual Exclusion 

• 한 프로세스가 임계 영역에 들어가면 다른 프로세스는 임계 영역에 들어가지 못하도록 운영체제가 통제한다.
• 임계 영역 내에서는 빠른 처리! Block 되지 않도록 처리한다.
• 상호 배제를 하기 위한 기본 처리구조는 진입 영역 (상호 배제 사전처리), 임계 영역, 출구 영역 (상호 배제 사후 처리), 잔류 영역으로 구성된다.
• 임계 영역 설정이 매우 중요하다.

임계 구역 해결 방법

임계 구역 해결 방법 피터슨 알고리즘, 데커 알고리즘, 세마포어, 모니터에 대해 살펴보겠습니다.

피터슨 알고리즘

• 피터슨 알고리즘의 변수로는 프로세스 1을 잠글 변수 1개 (lock 1), 프로세스 2를 잠글 변수 (lock 2), turn이라는 변수가 존재한다.
• turn 변수는 두 프로세스가 동시에 lock을 설정하여 임계 구역에 못 들어가는 상황에 대비하기 위한 장치다.
• 즉 데드락을 대비한 장치다.
• 두 프로세스가 lock를 설정했더라도 turn을 사용하여 다른 프로세스에 양보한다.

//공유 변수

boolean lock1=false;
boolean lock2=false;
int turn=1;

//프로세스 P1

lock=true
turn=2

while(lock2==true&& turn==2);
/*
     임계 구역
*/
lock1=false

//프로세스 P2

lock2=true
turn=1

while(lock1==true&& turn==1);
/*
     임계 구역
*/

lock2=false

만약 프로세스가 P2가 잠금을 설정하지 않았거나 잠금을 설정했더라도

곧바로 turn=1로 바꾸면 프로세스 P1은 임계구역에 진입하여 작업을 마친 후 잠금을 해제하고 임계 구역을 빠져나온다.프로세스 P2도 같은 방식으로 임계 구역에 진입한다.

피터슨 알고리즘은 위 3가지 문제를 다 해결하지만 2개의 프로세스만 사용가능하다는 한계가 있다.여러 프로세스가 하나의 임계 구역을 사용하려면 공유 변수를 추가하고 코드를 변경해야 한다.

데커 알고리즘

데커 알고리즘은 쉽게 생각해 양보하는 알고리즘이다. 임계구역에 들어갈 기회가 생겨도 자기 차례가 아니면 들어가지 않는다.

공유변수

boolean lock1=false
boolean lock2=false
int turn=1

//프로세스 1

lock1=true
while(lock2==true)
{
	if(turn==2){
    	lock1=false
        while(turn==2);
    	lock1=true
    }
}
	/*
    	임계구역
    
    */
    
turn=2
lock1=false

//프로세스 2

lock2=true
while(lock1==true)
{
	if(turn==1){
    	lock2=false;
        while(turn==1);
        lock2=true;
    }
}
/*
	임계구역
*/

turn=1
lock2=false

데커 알고리즘이 어떻게 작동하는지 프로세스 P1의 입장에서 살펴보자.

1. 프로세스 P1은 우선 잠금을 건다.(lock1=true;).
2. 프로세스 p2의 잠금이 걸렸는지 확인한다.[while(lock2==true)].
3. 만약 프로세스 P2도 잠금을 걸었다면 누가 먼저인지 확인한다.
   [if(turn==2)], 만약 프로세스 P1의 차례라면 (turn=1) 임계구역으로 진입한다.
   만약 프로세스 P2의 차례라면 (turn=2) 4번으로 이동한다.
4. 프로세스 P1은 잠금을 풀고 (lock1=false) 프로세스 P2가 작업을 마칠 때까지 기다린다.
   [while(turn==2);] 프로세스 P2가 작업을 마치면 잠금을 걸고 (lock1=true;) 임계구역으로 진입한다.

피터슨 알고리즘이나 데커 알고리즘은 해결의 세 가지 조건을 모두 만족하지만 매우 복잡하다.

프로세스가 늘어나면 변수도 늘어나고 전체적인 알고리즘도 복잡해진다.

임계 구역을 보호하기 위해 복잡한 알고리즘을 구현하도록 주문하는 것은 바람직한 접근 방법이 아니다.

 

세마포어

기존의 해법으로는 임계 구역 해결 알고리즘은 문제들을 일반화하기 힘들다.

그래서 세마포어라는 알고리즘이 등장했다.

 

세마포어는 임계구역에 진입하기 전에 스위치를 사용 중으로 놓고 임계구역으로 들어간다.

이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때까지 기다린다.

프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다.

세마포어는 다른 알고리즘과 달리 임계구역이 잠겼는지 직접 점검하거나, 바쁜 대기를 하거나,

다른 프로세스에 동기화 메시지를 보낼 필요가 없다.

 

세마포어가 어떻게 작동하는지 세마포어 내부 코드와 역할을 알아보자.

• Semaphore(n) : 전역 변수 RS를 n으로 초기화한다. RS에는 현재 사용 가능한 자원의 수가 저장된다.
• P() : 잠금을 수행하는 코드로, RS가 크면 (사용 가능한 자원이 있으면) 1만큼 감소시키고 임계구역에 진입한다. 만약 RS가 0보다 작으면 (사용 가능한 자원이 없으면) 0보다 커질 때까지 기다린다.
• V() : 잠금 해제와 동기화를 같이 수행하는 코드로, RS 값을 1 증가시키고, 세마포어에서 기다리는 프로세스에게 임계 구역에 진입해도 좋다는 wake up 신호를 보낸다.

Semaphore(n); ->
RS=n

p();->
if RS>0 then RS=RS-1;
else block();   //until RS>0

/*
	임계 구역
*/

V();->
RS=RS+1;
wake_up();

세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어 큐에 저장되어 있다가,

wake_up 신호를 받으면 큐에서 나와 임계구역에 진입한다. 따라서 바쁜 대기를 하는 프로세스가 없다.

그러나 세마포어의 P()나 V() 내부 코드가 실행되는 도중에 다른 코드가 실행되면 상호 배제와 한정 대기 조건을 보장하지 못한다.

그러므로 P()와 V()의 내부 코드는 검사와 지정을 사용하여 분리 실행되지 않고 완전히 실행되게 해야 한다.

 

세마포어의 가장 큰 문제는 잘못된 사용으로 인해 임계 구역이 보호받지 못한다는것이다.

사용자가 고의로 세마포어를 사용하지 않거나, 사용 중에 실수가 발생할 수 있다.

모니터

공유 자원을 사용할 때 모든 프로세스가 세마포어 알고리즘을 따른다면 굳이 P()와 V()를 사용할 필요 없이 자동으로 처리하면 된다.

이를 실제로 구현한 것이 모니터다.

모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써

자원을 보호하고 프로세스 간에 동기화를 시킨다.

 

모니터는 시스템 호출과 같은 개념이다. 커피머신을 사용자가 직접 만지면 고장 날 가능성이 높아지는 것처럼, 운영체제가 관리하는 자원을 사용자가 마음대로 사용하게 두면 실수나 악의적인 의도로 시스템 자원을 망가뜨릴 수 있다.

이러한 문제를 예방하기 위해 운영체제는 시스템 자원을 사용자로부터 숨기고 사용자의 요구 사항을 처리할 수 있는 인터페이스만 제공하는데, 이를 시스템 호출이라고한다. 이전 시간에 분명 사용자로부터 커널을 보호하기 위한 인터페이스가 시스템 호출이라고 학습했었다!

시스템 호출과 같은 방법으로 모니터도 보호할 자원을 임계구역으로 숨기고 임계구역에서 작업할 수 있는 인터페이스만 제공하여 자원을 보호한다.

 

• 임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세는 직접 P()나 V()를 사용하지 않게 모니터에 작업 요청을 한다.
• 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.

 

이상으로 운영체제 전공 복습 포스팅을 마칩니다!

 

2022. 6. 23. 16 : 20 수정 완료

복습 완료!

 

참고 자료

쉽게 배우는 운영체제 (저자 : 조성호)

https://www.kyobobook.co.kr/product/detailViewKor.laf?barcode=9791156644071 

운영체제 - 교보문고