[OS] 임계구역, 임계구역 해결

공유 자원

• shared resource
• 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등
• 공동으로 이용되기 때문에 프로세스들의 접근 순서를 정하여 예상치 못한 문제가 발생하지 않도록 해야함
• 경쟁 조건 (race condition) : 2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황

 

임계구역

• critical section
• 공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역
• 임계구역에서는 프로세스들이 동시에 작업하면 안 됨

 

- 생산자-소비자 문제 (producer-consumer problem)

• 생산자는 계속 물건을 생산해 버퍼에 넣고 : input(buf)
• 소비자는 계속 버퍼에서 물건을 가져온다 : output(buf)
• 버퍼는 작업을 계속하기 위해 원형 버퍼(circular buffer) 를 사용
• 상품의 총 개수가 저장된  sum이라는 전역 변수 사용
• 생산자 코드와 소비자 코드가 동시에 실행될 경우, 문제 발생!

 

- 임계 구역 해결 조건

• 상호 배제(mutual exclusion) : 한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없음
• 한정 대기(bounded waiting) : 어떤 프로세스도 무한 대기(infinite postpone)하지 않아야 함
• 진행의 융통성(progress flexibility) : 한 프로세스가 다른 프로세스의 진행을 방해해서는 안됨

 

임계구역 해결 방법

- 잠금(lock) 이용

[상호 배제 문제]

// 공유 변수
boolean lock=false;

// 프로세스 1
while(lock==true);
lock=true;
// 임계구역
lock=false;

// 프로세스 2
while(lock==true);
lock=true;
// 임계구역
lock=false;

• lock의 초깃값은 false
• 프로세스는 임계구역에 진입하기 전에 잠금이 걸려 있는지 확인
• 잠겨 있으면 다른 프로세스가 임계구역에서 작업하고 있다는 뜻이므로 해제될 때까지 무한루프 돌면서 기다림
• 임께 구역에 있는 프로세스가 작업 마치고 잠금 해제하면 무한 루프 빠져나와 잠금을 걸고 작업
• 작업을 마치면 잠금 해제
• 문제점
  • 프로세스 1이 임계구역에 진입한 후 자신에게 주어진 CPU 시간을 다 써서 (타임아웃) 준비 상태로 옮겨질 경우, 문맥 교환이 발생하고 프로세스 2가 실행 상태로 바뀌며 임계구역에 진입할 수 있게 됨
  • 잠금이 풀리기를 기다리려면 바쁜 대기를 해야 함

 

[한정 대기 문제]

// 공유 변수
boolean lock1=false;
boolean lock2=false;

// 프로세스 1
lock1=true;
while(lock2==true);
// 임계구역
lock1=false;

// 프로세스 2
lock2=true;
while(lock1==true);
// 임계구역
lock2=false;

• 프로세스는 임계구역에 진입하기 전에 잠금을 설정하고 다른 프로세스가 잠금을 설정했는지 확인
• 만약 잠금을 설정하지 않았다면 임계구역에 진입하여 작업을 마친 후 잠금 해제
• 문제점
  • 프로세스 1이 잠금을 설정한 후 타임 아웃, 문맥 교환 후 프로세스 2가 잠금 설정한 후 타임아웃
    → 이 경우 두 프로세스가 모두 임계구역에 진입하지 못하는 무한 대기 현상 발생
  • 교착 상태(deadlock) : 프로세스가 살아 있으나 작업이 진행되지 못하는 상태
  • 프로세스가 늘어나면 검사해야하는 lock의 개수도 늘어나 비효율적

 

[진행의 융통성 문제]

// 공유 변수
int lock=1;

// 프로세스 1
while (lock==2);
// 임계구역
lock=2;

// 프로세스 2
while (lock==1);
// 임계구역
lock=1;

• lock값이 1이면 프로세스 1이, 2이면 프로세스 2가 임계구역 사용
• 공유변수 lock의 값을 통해 다른 프로세스가 임계구역에 있는지 확인하고, 없으면 진입
• 문제점
  • 한 프로세스는 다른 프로세스가 임계구역에 진입했다가 나온 다음에야 다시 진입 가능
  • 경직된 동기화(lockstep synchronization) : 프로세스의 진행이 다른 프로세스로 인해 방해받는 현상

 

[하드웨어적 해결 방법]

// 공유 변수
boolean lock=false;

// 프로세스
while(testandset(&lock)==true);
// 임계구역
lock=false;

• 하드웨어적으로 잠금이 걸렸는 지 검사하는 문과 검사 후 잠금 설정을 하는 문을 동시에 실행
• 검사와 지정(test-and-set)코드를 사용하여 명령어 실행 중간에 타임아웃이 걸려 임계구역을 보호하지 못하는 문제 차단

 

- 피터슨 알고리즘

// 공유 변수
boolean lock1=false;
boolean lock2=false;
int turn=1;

// 프로세스 1
lock1=true;
turn=2;
while(lock2==true && turn==2);
// 임계구역
lock1=false;

// 프로세스 2
lock2=true;
turn=1;
while(lock1==true && turn==1);
// 임계구역
lock2=false;

• 프로세스 1은 임계구역 진입 전, 잠금을 한 후 turn을 2로 설정
• turn은 두 프로세스가 동시에 lock을 설정하여 임계구역에 못 들어가는 상황에 대비하는 장치
• 임계구역 해결 조건을 모두 만족하지만, 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;

• 프로세스는 우선 잠금을 걸고, 다른 프로세스의 잠금여부를 확인
• 다른 프로세스도 잠금을 걸었다면 누가 먼저인지 확인우 임계구역 진입 혹은 대기
• 임계구역 해결 조건을 모두 만족하지만, 매우 복잡

 

- 세마포어

• 임계구역 진입 전, 스위치를 사용 중으로 놓고 진입
• 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때까지 대기
• 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보냄
• 임계구역이 잠겼는지 직접 점검하거나, 바쁜 대기를 하거나, 다른 프로세스에 동기화 메세지를 보낼 필요 없음

Semaphore(n);
P();
// 임계구역
V();

• Semaphore(n) : 전역변수 RS를 n으로 초기화 (n = 공유 가능한 자원의 수, RS = 현재 사용 가능한 자원의 수 저장)
• P() : 잠금을 수행하는 코드
  • RS가 0보다 크면(사용 가능한 자원이 있으면) 1만큼 감소시키고 임계구역 진입
  • RS가 0보다 작으면 (사용 가능한 자원이 없으면) 0보다 커질 때까지 대기 (block())
• V() : 잠금 해제와 동기화를 같이 수행하는 코드
  • RS 값을 1 증가시키고 세마포어 큐에서 기다리는 프로세스에게 임계구역에 진입하라는 wake_up 신호 보냄
• P()와 V()의 내부 코드는 검사와 지정을 사용하여 분리 실행되지 않고 완전히 실행되게 해야 함
• 문제점 : 사용자의 잘못된 사용으로 임계구역이 보호받지 못할 수 있음
  • 프로세스가 세마포어를 사용하지 않고 바로 임계구역에 들어간 경우
  • P()를 두 번 사용하여 wake_up 신호가 발생하지 않은 경우 (세마포어 큐의 프로세스들이 무한대기)
  • P()와 V()를 반대로 사용하여 상호 배제가 보장되지 않은 경우

 

- 모니터

• 공유 자원 사용 시 모든 프로세스가 세마포어 알고리즘을 따를 경우 자동으로 처리
• 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스간 동기화를 시킴
• 임계구역에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청
• 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에게 알려줌
• 모니터는 임계구역 보호와 동기화를 위해 내부적으로 상태 변수(condition variable) 사용
  • wait() : 모니터 큐에서 자신의 차례가 올 때까지 대기, 세마포어의 P()에 해당
  • signal() : 모니터 큐에서 기다리는 다음 프로세스에 순서를 넘겨줌, 세마포어의 V()에 해당