[운영체제] 병행 프로세스와 상호배제(2)

상호배제와 동기화(2)

임계 영역(Critical Section)

둘 이상의 프로세스가 공유할 수 없는 자원을 임계자원이라 하며, 프로그램에서 이를 이용하는 부분

• 공유 메모리가 참조되는 프로그램의 부분(데이터나 데이터 구조)으로 다수의 프로세스가 접근 가능한 영역이면서 한 순간에 하나의 프로세스만 사용할 수 있는 영역(공유 자원의 독점을 보장하는 코드 영역)을 의미
• 프로세스들이 공유 데이터를 통해 협력 시, 한 프로세스가 임계영역에 들어가면 다른 모든 프로세스는 임계영역으로의 진입 금지
• 다중 처리 시스템과 단일 처리 시스템(시분할)환경에 적용되는 하나의 실행단위, 실행 구간을 의미
  • 임계역역 내에서 빠른 속도로 작업을 수행, 한 프로세스가 오랫동안 머무르면 안됨
  • 프로세스가 무한 루프 등에 빠지지 않도록 관리

진입 상호 배제

• 프로세스 하나가 임계 역역에 있으면 다른 프로세스가 임계 영역에 들어가지 못하게 하는 것
• 임계 영역에 들어가기를 원하는 프로세스는 진입 상호배제를 수행해야 함
  • 프로세스가 접근하지 않은 임계 영역은 잠금 상태
  • 프로세스는 임계 영역에서 작업을 수행하기 전에 키를 얻어 임계 영역의 잠금 상태를 해제해야 함
  • 프로세스가 키를 반환할 때까지 다른 모든 프로세스에 대해 잠김 상태 유지

임계 영역을 떠나는 프로세스는 출구 상호배제를 수행함으로써 다른 프로세스가 임계 영역에 들어갈 수 있도록 함

프로세스들이 서로 협력하여 자원을 사용할 수 있도록 프로토콜을 설계하여 임계영역 문제를 해결 가능

진입 영역(진입 코드)

각 프로세스는 접근하려는 자원의 임계영역에 들어갈 수 있는지 여부를 미리 요청해야 하며, 이를 코드로 구현한 부분

출구영역

임계영역에서 수행을 마치고 나갈 프로세스를 선택

잔류영역

진입영역과 출구영역을 제외한 나머지 영역으로, 임계영역을 마치고 나와 수행함

임계영역을 해결하기 위해 아래 세 가지 요구를 만족시켜야 함

상호 배제

• 프로세스 Pi가 임게영역에서 수행중일 때 다른 프로세스는 임계영역에서 수행할 수 없다.

진행

• 임계영역에서 수행하는 프로세스가 없고 여러 개의 프로세스가 임계영역으로 들어가려고 하면 프로세스 선정 알고리즘에 따라 다음 임계영역에서 수행할 대상을 선정한다.
• 다음 임계영역으로 들어갈 프로세스 선택은 무한정 미룰 수 없다.

제한된 대기

• 한 프로세스가 임계영역을 요청한 후 요청이 수락되기까지 다른 프로세스가 임계영역에 진입 할 수 있는 회수를 제한해야 한다.

소프트웨어적인 임계영역 문제 해결

단일 프로세서 또는 메모리를 공유하는 다중 처리 환경의 프로세서가 존재

알고리즘 1(상호배제 단계 1 알고리즘)

• 두 개의 프로세스(P1, P2)에 대한 상호배제를 보장
• 현재 parbegin/parend 때문에 P1과 P2가 동시에 수행되며, 임계영역의 진입여부를 확인하기 위해 while문 구현
• 구현 방식
  • 한 개의 공유변수(processnumber)를 사용하여 해결
  • 두 개의 프로세스(P1, P2)가 교대로 실행됨
• 임계영역 진입 : processnumber 값에 따라 진입 여부(P1 = processnumber <- 1)가 결정
  • 임계영역 진입을 위해 반드시 상대 프로세스의 processnumber 값 확인이 필요함
• 상호배제가 보장되지만 반드시 P1이 먼저 시작해야 함
  • P2가 준비되어도 P1이 먼저 들어갔다 나와야 하므로 대기 시간이 길어 질 수 있음
• 프로세스는 반드시 한 번씩 번갈아 들어갔다 나와야 함
  • 프로세스 수행 속도가 느려질 수는 있으나 시스템은 교착상태에 빠지지 않음
• 공유변수 processnumber를 한 개 사용하였으므로, 두 프로세스 중 하나가 중지되면 다른 프로세스도 중지됨

데커 알고리즘

• 하드웨어의 도움 없이 프로세스 두 개의 상호배제 문제를 해결
• 아래와 같은 특징을 가짐
  • 특별한 하드웨어 명령문을 필요로 하지 않는다.
  • 임계영역 바깥에서 수행 중인 프로세스가 다른 프로세스들이 임계영역에 들어가려는 것을 막아서는 안 된다.
  • 임계영역에 들어가기를 원하는 프로세서로 하여금 무한정 기다리게 해서는 안 된다.

하드웨어적인 임계영역 문제 해결

• 특별한 하드웨어 명령을 사용, 임계영역 문제를 해결 가능
• 기계를 비교하거나 단어 내용을 검사 및 수정 또는 내용을 바꾸는(Swap) 명령을 사용하여 임계영역 문제 해결
• 하나의 기억장치 사이클에서 수행되므로 생산자/소비자 문제에서 예로 든 counter 변수 수정에 발생하는 문제 해결 가능

testandset을 이용한 상호배제 알고리즘

• testandset(a, b);는 논리변수 b를 읽어 a에 복사하고 b를 참으로 하는 명령
• 단일 프로세서 또는 메모리를 공유하는 다중 처리 환경과 관계없이 적용되며, 간단하여 쉽게 적용된다는 장점을 가짐
• 임계영역에 진입하려는 프로세스에 바쁜 대기가 발생
• 무한 연기 가능성이 발생할 수는 있지만 프로세스 수가 많으면 거의 발생하지 않음

세마포어(Semaphore)

음이 아닌 정수값을 갖는 플래그 변수

• 다익스트라(Dijkstra)가 상호배제의 문제를 극복하기 위해 제안함
• 세마포어의 유명한 예 ‘열차의 진행 가능 여부’를 나타내는 차단기
  • 차단기 올라감 : 정지/대기(운영체제는 자원이 없어 기다리는 경우)
  • 차단기 내려감 : 진행(프로세스가 해당 자원을 사용할 수 있는 자유 상태)

모니터(Monitor)

프로그래밍 언어에서 제공되는 프로그래머 정의 연산자들의 집합으로 구성

• 세마포어의 P, V 연산이 프로그램 전체에 퍼져 있으며, 이들 연산이 미치는 영향을 전체적으로 파악하기 쉽지 않아 프로그램 작성이 어려운 단점을 극복하기 위함
• 모니터의 형태 구현은 변수 선언으로 구성, 변수 값이 형태를 정의함

모니터의 구조

• 하나 이상의 프로시저와 초기화 코드, 공유 데이터로 구성된 소프트웨어 모듈로 이루어진 객체
• 모니터 안에 정의된 프로시저는 모니터 내에서 지역적으로 정의된 변수와 형식 매개변수들만 접근 가능
  • 모니터 밖에 있는 프로세스는 모니터에 있는 데이터에 접근 불가능
• 모니터 경계에서 한 번에 한 프로세스만 진입하도록 제어되므로 상호 배제 원칙을 지킴
  • 자원을 대기하는 프로세스 또는 모니터가 사용 중이면 진입을 원하는 프로세스는 대기해야 함
  • 모니터 내의 프로세스는 자원이 다른 프로세스에 할당되어 대기할 수 있음
  • 프로그래머는 동기화 제약 조건을 명시적으로 코드화할 필요 없음
• 자원 반납 시 모니터 진입 루틴 호출
  • 호출된 루틴은 대기 중인 프로세스에게 신호를 보내고, 모니터는 대기 중인 프로세스에 자원 할당
  • 대기가 무기한 연기되는 것을 막기 위해 대기 중인 프로세스에 더 높은 우선순위를 부여함

모니터의 조건 변수

• 임계영역과 유사하며, 프로세스가 실행되는 동안 상호배제와 동기화를 제공
• 조건 임계영역으로 확장되었으며, 동기화를 위한 부수 기법이 필요함
• 모니터 밖의 프로세스가 대기 시 조건 변수에 의해 수행 재개가 결정됨
  • 아래와 같이 한 개 이상, 조건 형태의 변수 정의

      var x, y: condition;
    

• wait와 signal 연산만이 호출 가능
  • 이러한 두 가지 연산을 제공하는 추상적인 데이터 형태로 볼 수 있음
• 모든 조건 변수는 관련된 큐가 있기 때문에 wait를 호출하는 프로세스는 해당 조건 변수와 연관된 큐에 놓임
• x.wait 연산
  • 어떤 프로세스가 x.signal을 호출할 때까지 x.wait를 호출한 프로세스는 연기/중단된다는 의미
• x.signal 연산
  • 중단된 프로세스 중에서 한 개만 재개하며, 호출 시 해당 조건 변수와 연관된 큐에서 대기 중인 프로세스 하나를 큐에서 꺼내 모니터로 진입할 수 있도록 함
  • 중단된 프로세스가 없으면 효과가 없으며, x의 상태는 연산이 전혀 실행 되지 않는 것과 같음
• 여러 개의 프로세스가 조건 x에서 중단되고 x.signal 연산이 어떤 프 로세스에 의해 실행된다면, 어느 프로세스를 다음에 재개할 것인가?
• 단순한 해결 방법으로 선입 선처리 기법을 이용하여 가장 오래 대기한 프로세스를 먼저 재개시킴
• 단순 스케줄링 기법 적용이 어려울 시 아래 형식의 조건 대기 구조 사용

x.wait(c);

• 조건 c가 만족될 때까지 모니터를 호출한 프로세스의 수행이 일시 정지됨, 또한 모니터를 다른 프로세스들이 사용 가능
• c는 정수 식으로, wait 연산이 실행될 때 평가됨
• c 값은 우선순위 번호로 중단된 프로세스의 이름과 같이 기억되며, 값이 가장 작은 우선순위를 가진 프로세스가 다음으로 실행됨