[운영체제] 4. 병행 프로세스

1. 병행 프로세스의 개념

병행성

• 여러개의 프로세스 혹은 쓰레드가 동시에 실행되는 시스템적 특성을 의미한다.
• CPU(코어)가 한개라면 짧은 시간동안 번갈아가며 실행하며 아니면 여러개의 CPU를 각각의 프로세스 혹은 쓰레드가 사용한다.
• 메모리 구조에 따라 강결합 멀티프로세서 혹은 약결합 멀티프로세서로 나뉜다.
  • 강결합: 여러 CPU가 하나의 메모리를 공유 (하나의 운영체제)
  • 약결합: 각 시스템이 독립된 운영체제와 메모리를 가지고 서로 통신링크를 가짐

단일 프로세스 내의 병행성

단일 프로세스 내에서 병행성은 우선순위 그래프, Fork/Join 구조, 병행문 등을 통해 설명한다.

프로세스 간의 병행성

• 프로세스 간의 병행성에서 상호 협력하는 경우를 비동기적이라고 한다.
• 비동기 병행 프로세스는 서로 자원을 공유하며 영향을 끼칠 수 있다.

2. 동기화와 임계 영역

• 프로세스 동기화란 2개 이상의 프로세스의 처리 순서를 결정하는 것을 말한다.
• 임계 영역이란, 프로세스가 공용 변수를 읽거나, 테이블을 갱신하거나, 파일에 쓰는 등의 작업을 하는 코드 세그먼트를 의미한다.
• 임계 영역을 갖는 프로세스의 일반적 구조는 다음과 같다.
  1. 진입 영역 : 임계 영역에 진입할 수 있는지 확인
  2. 해제 영역 : 임계 영역에서 작업을 마치고 다른 프로세스의 진입을 허용
  3. 잔류 영역 : 나머지 영역
• 임계 영역의 동기화 문제를 해결하기 위해서는 다음과 같은 조건이 필요하다.
  1. 상호배제 : 서로 다른 프로세스가 임계영역에서 동시에 작업을 할 수 없다.
  2. 진행 : 임계영역에 진입 할 프로세스를 적절히 선택한다. 이 작업은 무한히 미루어 질 수 없다.
  3. 제한된 대기 : 어떠한 프로세스가 임계영역을 요청하면 다른 프로세스가 진입할 수 있는 횟수를 제한해야 한다.

Test - and - Set

• 상호배제의 하드웨어적 해결 방법이며, 분리가 불가능한 단일 명령어이다. 줄여서 TS라고도 한다.
• 메모리 내의 하나의 비트를 key 로 사용하여 busy 상태를 표현한다.
• 다른 프로세스가 임계영역에 진입하기 전에, 해당 영역이 점거 상태인지 체크하고 사용이 끝난 프로세스는 key 비트를 0으로 리셋해준다.
• 모든 절차는 인터럽트 되지 않게 원자적으로 수행된다.
• TS 메커니즘에는 두가지 결점이 있다.
  • 많은 프로세스가 동시에 임계영역에 들어가기를 원하면 ‘기아’상태가 발생한다. (쓰레드가 필요한 자원을 할당받지 못하고 계속 대기함)
  • 대기 프로세스는 비 생산적이고 자원만 소비하는 busy wating 상태에 있다.

세마포어(semaphore)

• TS 기법보다 조금 더 일반화에 용이하도록 다익스트라가 제시한 새로운 동기화 도구이다.
• 검사연산인 P(s) 연산과 증가 연산인 V(s) 연산으로 나누어 진다.
• P, V 연산은 각각 원자적 연산으로 간주된다. (도중에 인터럽트 되지 않는다.)

3. 프로세스의 상호 협력

• 몇 개의 프로세스가 공통작업을 수행하기 위해 서로 협동하는 경우가 있다.
• 두 가지 유명한 예제가 있는데 생산자와 소비자, 판독기와 기록기 예제이다.

생산자와 소비자 문제

• 개요
  • 고정된 크기를 가진 버퍼를 사이에 두고 버퍼가 비어 있다면 소비자가 기다리게 되고 버퍼가 가득 차게 되면 생산자가 기다리게 된다.
• 상호배제
  • 한 순간에 한 프로세스만 버퍼를 사용해야 한다.
• 동기화
  • 생산이 이루어져야 소비가 이루어지며, 버퍼 용량 이상으로 생산하면 안된다.
• 생산자 프로세스 의사코드

repeat
    ...         
    nextp에 데이터 항목을 생산함
    ...         
    P(empty);
    P(mutex);
    ...
    nextp를 버퍼에 넣음
    ...
    V(mutex)
	V(full)
until false;

• 소비자 프로세스 의사코드

repeat
    P(full);
    P(mutex);
    ...
    버퍼에서 데이터 항목을 꺼내 nextc에 넣음
    ...
    V(mutex);
    V(empty);
    ...
    nextxc에 있는 데이터 항목 소비
    ...
until false;

판독기/기록기 문제

• 개요
  • 데이터 오브젝트에 대해 읽고자 하는 프로세스를 판독기(reader), 쓰고자 하는 프로세스를 기록기 (writer) 라고 한다. 이에 대해 복수의 판독기가 동시에 공유객체에 접근 하는 것은 문제가 되지 않지만, 하나의 기록기와 다른 프로세스가 동시에 공유객체에 접근하는 것은 배타적으로 이루어져야 한다.
• 제 1판독기 문제
  • 기록기의 기아 상태를 유발할 수 있다.
  • 기록기가 공유객체를 사용하도록 허가되지 않는다.
• 제 2판독기 문제
  • 판독기의 기아 상태를 유발할 수 있다.
  • 기록기가 준비 되었다면 최대한 기록을 가능한 한 빨리 수행하도록 한다.

4. 프로세스 간의 통신

공유기억장치 기법

앞서 다룬 유한버퍼 문제와 같이 공유 변수를 이용하여 통신하는 기법이다. 통신기능을 제공하는 책임은 응용 프로그래머에게 있고, 운영체제는 단순히 공유 변수만을 제공한다.

메시지 시스템 기법

두 개 이상의 프로세스가 공유변수에 의존하지 않고서 메시지를 주고받을 수 있도록 통신 링크를 설치한다. 소량의 데이터를 주고받는데 최적화 되어있고, 통신에 대한 책임은 프로세스에 있다.

1. 직접 통신
   • 통신을 원하는 모든 프로세스 쌍 사이에 통신 링크가 설정되어야 한다.
   • 통신을 위해 상대의 신원을 알아야 한다.
   • 하나의 링크는 두 프로세스 사이에만 연결된다.
   • 링크는 양방향이다.
2. 간접 통신
   • 우편함 객체를 통해 메시지를 주거나 받을 수 있다.
   • 송신자/수신자를 분리하므로 통신의 유연성이 올라간다.
   • 한 링크는 두개 이상의 프로세스들과 연관될 수 있다.
3. 링크의 용량
   1. 용량이 없는 경우
   2. 링크는 어떤 메시지도 가질 수 없으므로 메시지를 수신할 때 까지 기다려야 한다.
   3. 제한된 용량
   4. 링크는 유한 길이 n을 가진다. 따라서 큐가 가득 차면 송신자는 대기가 발생한다.
   5. 무제한 용량
   6. 링크의 큐는 무한한 길이를 가지고 있으므로 송신자는 결코 대기가 없다.
   • 용량이 없는 경우를 가리켜 ‘비버퍼링 메시지 시스템’ 이라고도 한다.
   • 용량이 존재하는 경우 송신과 수신이 분리되므로 비 동기적 통신이라고도 한다.
4. 예외조건
   • 이런 메시지 시스템은 보통 분산 환경에서 구성하는데, 통신과 처리 과정에서 오류가 발생할 가능성이 단일 시스템보다 크다.
   • 예외를 미리 잘 예상하여 고장 회복이 일어나야 한다.
   • 일어날 수 있는 예외
     1. 프로세스 종료
        1. 이미 종료된 프로세스로에 메시지를 보내거나, 프로세스로부터 메시지를 기다릴 수 있다. 이 경우 프로세스 종료 사실을 상대 프로세스에 알려야 한다.
     2. 메시지 상실
        1. 통신 네트워크 내에서 메시지가 상실될 수 있다. 보편적으로 시간 제한 기법을 이용해 이를 탐지하며, 상황에 따라 메시지를 재 송신할 수 있다.
     3. 메시지 혼합
        1. 메시지가 송신 도중 변질되는 경우를 말한다. 이런 형태의 오류 탐지를 위해 검사 합계(CheckSum)를 이용한다.