5-3.[os] 임계구역 해결 방법

임계구역 문제 해결:

  • 잠금: lock = true
  • 잠금 해제 : lock = false

  • 임계구역은 한순간에 한 프로세스만 접근할 수 있는 곳

상호 배제 문제

image.png

  • lock = true 잠겨있다
  • 잠겨 있으면 해제될 때까지 루프를 돌며 기다린다 while(lock==true)
  • 잠금을 해제하면 lock = false 무한루프를 빠져나와서 작업할 준비가 됨
  • 다른 프로세스가 진입하지 못하도록 잠금을 걸고(lock=true) 작업
  • 작업을 마치면 다른 프로세스가 사용할 수 있게끔 잠금을 해제(lock=false)

image.png

  • while(lock = = true); 문을 실행하고 나서 곧바로 lock = true; 문을 실행해야 다른 프로세스가 임계구역에 들어오는 것을 막을 수 있음

  • while (lock = = true); 잠금이 풀리기를 기다리면서 바쁜 대기, 작업을 할 필요가 없는 시간에도 계속 무한 루프를 돌면서 시스템 자원을 낭비

  • 잠금이 걸려있는지 확인 후 잠금을 건다 만약 그 사이에 다른 프로세스가 진입하면 상호 배제 조건을 보장하지 못하고 진입을 허락

한정 대기 문제

image.png

  • P1은 임계구역에 진입하기 전에 먼저 잠금을 설정 lock = true;
  • P2가 잠금을 설정했는지 확인 [while(lock2 = = true);]
  • P2 잠금이 해제(false)되어있다면 P1의 잠금도 해제 lock1 = false;
  • 잠금을 2개 사용한다. 일단 잠금을 하고 다른 프로세스가 잠겼는지 확인하므로 상호 배제가 보장된다

무한 대기 상황

image.png

  1. 프로세스 P1은 lock1 =true; 문을 실행한 후 자신의 CPU 시간을 다 써버렸다(타임아웃). 문 맥교환이 발생하고 프로세스 P2가 실행상태로 바뀐다.

  2. 프로세스 P2도 lock2=true; 문을 실행한 후 자신의 CPU 시간을 다 써버렸다(타임아웃). 문맥교환이 발생하고 프로세스 P1 이 실행상태로 바뀐다.

  3. 프로세스 P2가 lock2 = true; 문을 실행했기 때문에 프로세스 P1 은 while(lock2 == true); 문 에서 무한루프에 빠진다

  4. 프로세스 P1이 lock1 =true; 문을 실행했기 때문에 프로세스 P2도 while(lockl == true);문 에서 무한루프에 빠진다.

교착 상태(deadlock):

  • 한정 대기 조건을 보장하지 못하는 상황
  • 프로세스가 살아 있으나 작업이 진행되지 못하는 상태

단점:

  • 프로세스가 많으면 검사해야 하는 lock의 개수도 늘어난다

진행의 융통성 문제

  • 임계구역 문제를 해결하기 위한 방법
  • lock 값이 1 -> P1 사용 중
  • lock 값이 2 -> P2 사용 중

image.png

  • 공유 변수 lock의 값을 통해 다른 프로세스가 임계구역에 있는지 확인하고, 없으면 진입
  • 프로세스 P1은 while(lock == 2); 문을 실행하고 프로세스 P2가 잠금을 걸었으면 기다린다
  • 한 프로세스가 두 번 연달아 임계구역에 진입하고 싶어도 그럴 수 없다

경직된 동기화 (lockstep synchronization): 프로세스의 진행이 다른 프로세스로 인해 방해받는 현상


피터슨 알고리즘

  • 임계구역 3문제를 해결
  • 게리 피터슨이 고안

image.png

  • turn 이라는 공유 변수 사용
  • : 두 프로세스가동시에 lock을 설정하여 임계구역에 못 들어가는상황게 대비하기 위한장치
  • 두 프로세스가 동시에 lock을 설정했더라도 turn을 사용하여 다른 프로세스에게 양보

단점:

  • 2개의 프로세스만 사용가능하다
  • 여러 프로세스가 하나의 임계구역을 사용하려면 공유 변수를 추가

데커 알고리즘

  • 임계구역 해결의 세 가지 조건을 모두 만족
  • 검사와 지정 같은 하드웨어의 도움이 필요하지 않음

image.png

  1. 프로세스 P1 은 우선 잠금을 건다(lockl=true;).
  2. 프로세스P2의 잠금이 걸렸는지 확인한다[while(lock2 = = true)].
  3. 만약 프로세스 P2도 잠금을 걸었다면 누가 먼저인지 확인한다[if(turn = = 2)]. 만약 프로세스 P1 의 차례라면(turn = l) 임계구역으로 진입한다. 만약 프로세스 P2의 차례라면(turn = 2) 4번으로 이동한다.

  4. 프로세스 P1 은 잠금을 풀고(lock1 = false;) 프로세스 P2가 작업을 마칠 때까지 기다린다 [while(turn == 2 ); ]. 프로세스 P2가 작업을 마치면 잠금을 걸고(lock1 =true;) 임계구역으로 진입한다.

단점:

  • 매우 복잡하다

세마포어

  • 다익스트라가 고안
  • 간단한 알고리즘
  • 스위치를 사용 중으로 놓고 임계구역으로 들어간다
  • 프로세스가 끝남
  • 세마포어: 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다

Semaphore(n): 전역 변수 RS를 n으로 초기화

  • RS에는 현재 사용 가능한 자원의 수가 저장된다.

P(): 잠금을 수행하는 코드

  • RS가 0보다 크면(사용 가능한 자원이 있으면) 1만큼 감소시키고 임계구역에 진입한다. 만약 RS가 0보다 작으면(사용 가능한 자원이 없으면) 0보다 커질 때까지 기다린다

V(): 잠금해제와 동기화를 같이 수행하는 코드

  • RS 값을 1 증가시키고 세마포어에서 기다리는 프로세스에게 임계구역에 진입해도 좋다는 wake_up 신호를 보낸다

image.png

  • 세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어 큐에 저장되어 있다가 wake_up 신호를 받으면 큐에서 나와 임계구역에 진입
  1. 먼저 도착한 프로세스 P1이 임계구역에 진입한다. 현재 RS는 1이므로 이 값을 1 감소시키고 임계구역에 진입한다.
  2. 나중에 도착한 프로세스 P2는 현재 RS 값이 0이므로 프로세스 P1 이 임계구역을 빠져나올 때 까지 세마포어 큐에서 기다린다.
  3. 프로세스 P1은 현재 예금이 10만원인 것을 확인하고 10만 원을 더해 20만 원으로 바꾼 다음 작업을 마친다.
  4. 프로세스 P1 은 V()를 실행하여 RS 값을 1 증가시키고 wake_up 신호를 프로세스 P2에 보낸다.

  5. wake_up 신호를 받은 프로세스 P2가 작업을 시작한다. 프로세스 P2는 현재 예금이 20만 원 인 것을 확인하고 5만원을 더해 25만원으로 바꾼다.

image.png

image.png


단점:

  • 잘못된 사용으로 인해 임계구역이 보호받지 못 한다

세마포어의 잘못된 사용 예

image.png

프로세스가 세마포어를 사용하지 않고 바로 임계구역에 들어간 경우로 임계구역을 보호할 수 없다.

  1. P() 두 번 사용하여 wake_up 신호가 발생하지 않은 경우이다. 프로세스 간의 동기화가 이루어지지 않아 세마포어 큐에서 대기하고있는프로세스들이 무한대기에 빠진다.
  2. P()와 V()를 반대로 사용하여 상호배제가 보장되지 않은 경우로 임계구역을 보호할 수 없다.

모니터

  • 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함
  • 자원을 보호하고 프로세스 간에 동기화를 시킨다
  • 시스템 호출과 같은 개념
  • 불필요한 정보를 숨기고 공유 자원에 대한 인터페이스만 제공 -> 오늘날의 객체지향 언어와 매우 닮음

모니터의 작동 원리

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

image.png

Did you find this article valuable?

Support Software Engineer at Your Service by becoming a sponsor. Any amount is appreciated!