04. 병행 프로세스

병행 프로세스

병행 프로세스 개념

• 프로세스 여러 개가 동시에 실행되는 것.

  • 독립적으로 작업을 수행, 다른 프로세스와 협력하며 특정 기능 수행.
  • 프로세스 간 교신이 필요.

• 비동기적 병행 프로세스

  • 프로세스 간 교신 시 동기화되어야 하는 프로세스.

• 상호 작용

  • 제한된 자원을 공유하기 위함이며, 상호 작용하는 프로세스는 순서에 맞게 실행되도록 동기화되어야 함.

병행 프로세스의 과제

병행성

다수의 프로세서를 이용하여 작업을 수행하며, 다중 프로세싱 시스템, 분산 처리 환경, 다중 프로그래밍 운영체제에서 매우 중요함.
시스템의 신뢰도 향상과 처리 속도 개선을 통한 처리 능력 증대에 매우 중요함.

• 다중 프로세싱 시스템
  • 각 프로세서가 갖는 오버헤드를 감소시키면서 프로세서의 유효성을 증대시킴.
  • 여러 개의 명령어를 세분화하여 동시에 처리하기 위해 프로세서들을 연결, 상호작용을 제어.

다중 프로세싱 시스템의 성공적인 구현을 위한 해결 문제

• 공유 자원을 상호 배타적으로 사용해야 함.
  • 프린터, 통신망 등은 한 순간에 한 프로세스만 사용해야 함.
• 병행 프로세서들 사이는 협력 또는 동기화되어야 함.
  • 상호 배제도 동기화의 형태임.
• 두 프로세스 사이에 데이터 교환을 위한 통신이 이루어져야 함.
• 프로세서는 결정성(Determinacy)을 확보해야 함.
  • 동시에 수행되는 다른 프로세스들의 실행 속도와 관계 없이 항상 일정한 실행 결과 보장.
  • 교착 상태를 해결하고 병행 프로세스들의 병렬 처리 능력 극대화.
  • 실행 검증 문제 해결
  • 병행 프로세스 수행 과정에서 발생하는 상호 배제를 보장해야 함.
    • 어떤 프로세스가 작업을 실행 중일 때 나머지 프로세스들이 그 작업에 관련된 작업을 수행할 수 없음.

다중 프로세싱 시스템은 프로세스 동기화 알고리즘이 필요.

• 프로세서들이 모든 입출력 장치와 메모리를 참조 가능.
• 동시에 동일한 자원에 접근할 경우 충돌이 발생하므로 이를 해결.

선형 그래프

프로세스는 프로세스 집합과 이들의 선행 제약(Precedence Constraint)의 두 가지 요소로 정의

선형 제약

• 프로세스를 순서대로 다른 상태로 옮기는 것
  • 두 프로세스에 선행 제약이 없으면 이 둘은 독립적이므로 병행 실행 가능

선형 그래프

• 선행 제약의 논리적 표현
• 각 문장에 대응되는 노드가 비순환 그래프를 이룸
• 선행 그래프에서 노드는 소프트웨어 작업이거나 동시에 실행할 수 있는 프로그램 명령

예

간단한 산술 연산을 수행하는 알고리즘

• 병행 수행을 하기 위해 프로세서 안의 기능 단위(가산기 등)를 여러 개 두거나 프로세서를 여러 개 사용해야 함
• 프로세서를 여러 개 사용 시 여러 문장이 동시에 수행되어 총 수행시간을 줄일 수 있음

a := x + y; → S1
b := z + 1; → S2
c := a - b; → S3
w := c + 1; → S4

• S1과 S2연산은 동시에 수행이 가능 한 연산
• S3연산은 a와 b가 값을 할당 받기 전에 수행하면 안된다.
• S4연산은 c 값을 계산하기 전에 수행할 수 없다.

병행 프로세스를 표현하는 방법

프로그램의 여러 문장의 선행 관계 명시를 위해 두 가지 언어구조 제시

fork와 join 구조

• 선행 그래프는 연산 부분의 선행 제약을 정의하는데 유용하나, 2차원이므로 프로그래밍 언어에서 사용하기에 어려움.

• 병행을 최초로 언어적 표현으로 명시.

fork L 명령

• 프로그램에서 두 개의 병행 수행을 만듦
• 단일 연산을 두 개의 독립적인 연산으로 분할
• 다음 문장으로 이어지는 흐름과 라벨L 위치에서 시작하는 흐름으로 나뉨.

join n 명령

• 여러 개의 병행 연산을 하나로 결합하는 방법을 제공
  • 단위적으로 수행해야 함
• 합칠 연산의 수를 명시하는 매개변수를 가짐

    count := 2;
    fork L1;
    a := x + y;
    go to L2;
L1 : b := z + 1;
L2 : join count;
    c := a – b;
    w := c + 1;

병행 문장

• 하나의 프로세스가 여러 병렬 프로세스로 퍼졌다가 다시 하나로 뭉쳐지는 것을 나타내는 구조

다익스트라가 제안한 ‘parbegin/parend’

• 일반적인 형태

  parbegin S1; S2; ......; Sn; parend;

  • 각 Si는 단일 문장(명령어), parbegin과 parend 사이의 모든 문장은 병행 수행 가능.

• 보다 효과적인 병행 문장은 S0과 Sn+1 문장을 추가하여 아래와 같이 정의 가능.

  S0; parbegin S1; S2; ......; Sn; parend; Sn+1;

  • Sn+1 은 모든 S(i=1, 2,…, n)가 끝난 후에만 실행 가능.

• 위의 간단한 산술연산의 예를 parbegin/parend로 표현하면 아래와 같다.

  parbegin
      a := x + y;
      b := z + 1;
  parend;
      c := a – b;
      w := c + 1;

Reference

『IT CookBook, 운영체제(개정3판)』, 구현회 집필, 한빛아카데미

『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미

『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL