병행성의 원리

• 병행성의 원리
  • 시스템에서 프로세스들은 병행 처리되며, 단일 처리시스템에서는 프로세스들이 인터리빙(interleaving), 즉 여러 프로세스가 서로 번갈아 수행됨
    • 인터리빙은 실제로 병렬처리되는 것은 아니고, 프로세스들 간의 문맥교환 비용도 발생하지만, 처리 효율과 구조적 프로그래밍에 유익함
    • 다중처리기 시스템에서는 프로세스들의 인터리빙과 오버래핑(overlapping)도 지원
      • 오버래핑 : 프로세스들이 여러 개의 처리기들에서 실제로 병렬 수행되는 것
  • 인터리빙과 오버래핑의 문제점
    • 단일 처리기 환경에서, 프로세스 간의 수행 순서는 비동기적이라는 다중프로그래밍의 기본 특성에서 다음과 같은 문제 발생
      • 전역 자원 공유의 어려움
        • 두 개의 프로세스가 같은 전역변수에 write하는 경우, 프로세스의 순서에 따라 프로세스의 수행결과가 달라진다.
      • 운영체제 자원을 최적으로 할당하기 어려움
        • 프로세스 A가 어떤 IO 채널을 할당받음, 근데 IO 채널 사용 이전에 보류가 됨, 이 경우 다른 프로세스들은 해당 채널을 사용할 수 없음
        • 가용한 자원이 프로세스의 수행 순서에 따라 사용될 수 없는 상황이 발생 => 교착상태
      • 프로그래밍 디버깅이 어려워짐
        • 프로세스간 수행 순서에 따라 결과가 달라지만 오류가 재현되지 않을 수도 있고 이는 디버깅이 어렵다.
  • 병행 처리할 때 전역자원에 두 개의 프로세스가 동시에 접근하는 경우
    • 단일 처리기
      • 인터럽트가 프로세스의 어떤 곳에서도 발생하여 명령 중지가 일어나 이로 인해 수행 결과가 달라질 수 있음
    • 병렬 처리기
      • 인터럽트의 비동기적 발생 + 두 개의 프로세스가 동시에 수행하면서 같은 전역 변수에 접근해 수행 결과가 올바르지 않을 수 있음
      • 해결 안 : 공유 자원에 대한 접근을 제어
• 경쟁조건 (race condition)
  • 다수의 프로세스나 스레드가 공유 자원을 동시에 읽거나 쓰려고 하는 상황
  • 경쟁조건이 발생하면 프로세스의 최종 수행 결과가 프로세스들의 수행순서에 달라질 수 있다.
• 운영체제가 고려해야 하는 사항들
  • 모든 프로세스를 추적해야함, 이는 PCB를 이용하여 할 수 있다.
  • 활동 중인 각 프로세스들에게 다양한 자원들을 할당하고 해제할 수 있어야 한다.
    • 처리기 시간
    • 메모리
    • 파일
    • 입출력 장치
  • 각 프로세스에게 할당된 자원과 데이터들을 다른 프로세스들의 예기치 못한 간섭으로 부터 보호해야 한다.
  • 프로세스의 기능과 수행 결과는 프로세스 간의 수행 순서에 대해 독립적이여야 한다.
• 프로세스간 상호작용

인식 정도	관계	프로세스 간 상호 영향	잠재적인 제어 문제
서로를 인식하지 못함	경쟁	한 프로세스의 수행 결과는 다른 프로세스의 행위와는 독립 프로세스의 타이밍에 영향을 받을 수 있음	상호배제 교착상태 (재사용 가능 자원) 기아상태
서로를 간접적으로 인식 (예 : 자원 공유)	공유를 통한 협력	한 프로세스의 수행 결과는 다른 프로세스들로부터 얻은 정보에 의해 영향을 받을 수 있음 프로세스의 타이밍에 영향을 받을 수 있음	상호배제 교착상태 기아상태 데이터 일관성
서로를 직접적으로 인식 (예 : IPC)	통신을 위한 협력	한 프로세스의 수행 결과는 다른 프로세스들로부터 얻은 정보에 의해 영향을 받을 수 있음 프로세스의 타이밍에 영향을 받을 수 있음	교착상태 (소모성 자원) 기아상태

• 자원에 대한 프로세스간 경쟁
  • 병행 프로세스가 동일한 자원을 동시에 접근하려고 하는 경우 경쟁이 발생
  • 경쟁 관계에 있는 프로세스들은 서로 아무런 정보를 교환하지 않는다.
    • 프로세스의 수행은 경쟁 관계의 다른 프로세스의 행위에 영향을 줄 수 있다.
    • 한 프로세스가 자원을 할당받으면 다른 프로세스는 기다려야함
    • 수행속도가 떨어지며 무한 대기상태에 빠질 수도 있다.
  • 경쟁 관계에 있는 프로세스들이 존재하는 경우 상호배제(mutual exclusion), 교착상태(deadlock), 기아(starvation)라는 세 가지 제어 문제가 발생
    • 임계자원 (critical resource) : 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원
    • 임계영역 (critical section) : 프로그램 코드 중 임계자원에 접근하는 부분
  • 상호배제 (mutual exclusion)
    • 한 시점에 단 하나의 프로세스만이 임계영역에 들어갈 수 있다는 것을 의미
    • 상호배제의 보장은 교착상태와 기아라는 제어 문제를 발생시킴
      • 기아 : 교착상태는 아니지만 특정 프로세스가 오랜기간 자원을 사용하지 못하는 상태
• 상호배제를 위한 요구조건
  • 상호배제가 강제되어야 함
  • 임계영역이 아닌 곳에서 멈춘 프로세스는 다른 프로세스의 수행을 간섭해서는 안됨
  • 임계영역에 접근하고자 하는 프로세스의 수행이 무한이 미루어져서는 안됨, 즉 교착상태 및 기아가 발생해서는 안됨
  • 임계영역이 비어 있을 때, 임계영역에 진입하려는 프로세스는 즉시 임계영역에 들어갈 수 있어야 한다.
  • 처리기 개수나 프로세스 상대적 수행속도에 대한 가정은 없어야함
  • 일단 임계영역에 들어간 프로세스는 유한 시간 내에 임계영역에서 나와야 함