2 분 소요

임계구역 문제 (The Critical-Section Problem)

  • 각 프로세스는 임계구역이라고 부르는 코드 부분을 포함하고 있고, 그 안에서 다른 프로세스와 공유하는 변수를 변경하거나, 테이블 갱신 등의 작업을 진행한다.
  • 이 시스템의 중요한 특징은 한 프로세스가 자신의 임계 구역에서 수행하는 동안 다른 프로세스들은 그 임계구역에 들어갈 수 없다는 사실이다.
  • 각 프로세스는 임계구역에 진입하려면 진입 허가를 요청해야 한다.
  • 요청을 하는 부분을 진입 구역(entry section), 그 뒤는 퇴출 구역(exit session)이라고 한다.
  • 임계 구역이 아닌 구역은 나머지 구역(remainder section) 이라고 한다.
  • 임계 구역 문제 해결안은 다음의 3가지를 충족해야 한다.
    • 상호 배제 (mutual exclusion)
      • 프로세스가 자기의 임계 구역에서 실행된다면 다른 프로세스들은 자신의 임계 구역에서 실행될 수 없다.
    • 진행 (progress)
      • 자기의 임계 구역에서 실행되는 프로세스가 없고 자신의 임계 구역으로 진입하려는 프로세스가 있다면, 나머지 구역이 아닌 프로세스들만 그 다음에 누가 진입할지를 결정하는 데 참여할 수 있다. 이 선택은 무한정 연기될 수 없다.
    • 한정된 대기 (bounded waiting)
      • 프로세스가 자기의 임계 구역에 진입하려는 요청을 한 후 부터 허용 될 때 까지 다른 프로세스들이 그들 자신의 임계구역에 진입하는 횟수에 제한이 있어야 한다.

피터슨의 해결안

  • flag를 두어 두 개의 프로세스가 번갈아 가면서 실행된다.

Mutex Locks

  • 프로세스는 임계 구역에 들어가기 전에 반드시 lock을 획득 해야 하고, 빠져 나올 때 반납 해야 한다.
  • acquire() 락을 획득, busy waiting 사용 (spin lock) -> CPU 사이클 낭비, but 문맥 교환을 필요로 하지 않는다. 짧은 시간 동안만 락을 소유할 경우 유용하다.
  • release() 락을 반환

세마포 (Semaphore)

  • 세마포는 wait()과 signal()로만 접근 가능하다.
  • 카운팅 세마포 값은 제한이 없고, 이진 세마포 값은 0, 1 사이의 값만 가능하다.
  • 따라서 이진 세마포는 mutex락과 유사하게 동작한다.
  • 카운팅 세마포는 가용한 자원의 갯수로 초기화 된다. 자원을 사용하려는 프로세스는 wait() 연산을 수행하며, 세마포의 값이 감소가 된다. 값을 방출 하면 signal()연산을 수행하고, 세마포 값은 증가한다. 세마포의 값이 0이 되면 모든 자원이 사용중이고, 0 이상이 될 때까지 봉쇄된다.

교착 상태와 기아

  • 세마포에서 프로세스들이 하나에 의해서만 야기될 수 있는 상황 (signal 연산)을 무한정 기다리는 상황이 발생할 수 있다. 이를 교착 상태(deadlock) 이라고 한다.
  • 무한 봉쇄, 또는 기아는 세마포에서 무한정 대기하는 것이다. 이는 큐에서 LIFO 순서로 제거할 경우 발생 할 수 있다.

우선순위 역전

  • 셋 이상의 우선 순위를 가진 시스템에서만 발생한다. 상대적으로 낮은 우선 순위를 가진 프로세스가 높은 프로세스에게 영향을 끼치는 상황이다.
  • 두 가지 우선순위만 가지게 하면 해결 할 수 있다.
  • 우선순위 상속 프로토콜을 구현함으로서 해결할 수 있다.
    • 우선순위가 높은 프로세스가 필요로 하는 자원을 사용하는 프로세스들은 끝날 때 까지 더 높은 우선순위를 상속받는다.

고전적인 동기화 문제들

유한 버퍼 문제 (The Bounded-Buffer Problem)

  • 유한한 크기를 가지는 버퍼에 여러 프로세스들이 접근할 때 발생하는 문제.
  • 이진 세마포어를 통해 해결할 수 있다.

Readers-Writers 문제

  • writer와 reader이 동시에 접근 할 때 발생할 수 있는 문제.
  • reader/reader 접근은 허용, writer은 한 개만 접근할 수 있도록 함.

식사하는 철학자들 문제 (The Dining-Philosophers Problem)

  • 자신의 바로 좌우의 젓가락만 집을 수 있다.
  • 두 젓가락을 모두 집어야 식사를 할 수 있다.
  • 식사를 하고 난 다음에 두 젓가락을 모두 내려놓는다.
  • 모두 오른쪽의 젓가락을 집게 된다면 아무도 먹을 수 없을 것이다. (교착상태와 기아)
  • 이는 모니터로 해결 할 수 있다.

모니터

  • 세마포를 사용할 때 다음과 같은 문제점이 발생할 수 있다.
    • 코딩하는 것이 힘들다.
    • 타이밍 오류가 발생할 수 있다.
    • 정확성(correctness) 입증이 어렵다.
    • 자발적 협력(voluntary cooperation)이 필요하다.
    • 한 번의 실수가 시스템 전체에 치명적으로 영향을 미친다.
  • 모니터 구조물은 모니터 안에 항상 하나의 프로세스만이 활성화된다. -> 동기화 제약 조건을 구현할 필요 없다.
  • 동기화는 condition이라는 구조물로 제공된다.
  • condition은 signal()과 wait()을 가지고 있다.
  • x.wait(), x.signal()과 같이 사용한다.

함수형 프로그래밍 언어

  • C++, Java와 같은 절차형 언어들은 변수들이 다른 값을 배정받을 수 있기 때문에 변경이 가능하다.
  • 함수형 프로그래밍은 상태를 유지하지 않는다. 변수가 정의 되어 값을 배정받으면 값이 변경 될 수 없기 때문에 경쟁 조건이나 교착 상태의 쟁점에서 자유롭다.

카테고리:

업데이트:

참고