기록하는 곳

병행 프로세스 - 1

동시에 실행되는 여러 개의 프로세스 또는 쓰레드

병행성 (concurrency)

여러 개의 프로세스 또는 쓰레드가 동시에 실행되는 시스템

병행 프로세스의 개념

병행 프로세스의 실행 형태

  • CPU의 개수에 따른 병행 프로세스의 실행 형태
    • 단일 CPU : 하나의 CPU에서 인터리빙 형식으로 실행
    • 멀티 CPU : 여러 개의 CPU에서 병렬 처리 형식으로 실행

  • 멀티 CPU에서의 메모리 구조에 따른 병행 프로세스의 실행 형태
    • 강결합 멀티프로세서 시스템 : 공유 메모리 구조 (여러 CPU가 하나의 메모리를 공유함)
    • 약결합 멀티프로세서 시스템 : 분산 메모리 구조 (CPU마다 자신만의 메모리를 가지고 있음) => CPU 간 통신선으로 연결됨

병행성 문제

  • 병행 프로세스들이 상호작용 하는 경우

    • 공유자원 점유 문제
    • 동기화 문제
    • 통신 문제

  • 상황에 따른 구분

    • 단일 프로세스 내의 병행성
    • 프로세스 간의 병행성

단일 프로세스 내의 병행성

우선순위 그래프

  • 정점: 문장
  • 방향 있는 간선: 우선순위 관계

우선순위 그래프

Fork/Join 구조

  • fork L : 2개의 병행 수행을 만듦 (레이블 L 위치, fork 명령어 다음)
  • join n : 병행하는 n개의 흐름을 하나로 재결합

병행문

  • 1개의 프로세스가 여러 가닥의 병렬 프로세스로 분할되었다가 다시 하나로 결합
  • parbegin / parend 문
parbegin // parbegin ~ parend 사이에 있는 a, b는 병행처리된다.
    a := x + y;
    b := z + 1;
parend
    c := a + b;
    write(c);

동기화와 임계영역

  • 프로세스 동기화 : 2개 이상의 프로세스에 대한 처리순서를 결정하는 것
  • 임계영역 : 2개 이상의 프로세스가 동시에 엑세스하면 안되는 공유자원을 액세스하는 코드 영역
  • 상호배제 : 2개 이상의 프로세스가 동시에 임계영역에 진입하지 못하도록 하는 것

임계영역을 갖는 프로세스의 일반적 구조

진입영역 - 임계영역 - 해제영역 - 잔류영역

임계영역 문제 해결을 위한 요구조건

  • 상호배제 : 한 프로세스가 임계영역에서 실행 중일 때 다른 어떤 프로세스도 임계영역에서 실행될 수 없음

  • 진행 : 임계영역에서 실행 중인 프로세스가 없고 여러 프로세스가 임계영역에 진입하고자 할 때 그 중에서 적절히 한 프로세서를 결정해야 하며 이 결정은 무한정 미룰 수 없음

  • 제한된 대기 : 한 프로세스가 임계영역 진입 요청을 한 후 수락될 때까지 다른 프로세스가 임계영역 진입을 허가 받는 횟수는 제한이 있어야 함

임계영역 문제 해결을 위한 도구

Test-and-Set 명령어 (TS 명령어)

  • 상호배제의 하드웨어적 해결 방법
  • 분리가 불가능한 단일 기계 명령어(원자적으로 수행)

구현방법

repeat
    // 임계영역이 사용중이면 접근 못하게 막아줌
    while Test_and_Set(lock) do skip; // (진입영역): lock=false
    (임계영역)
    lock := false; // (해제영역)
    (잔류영역)

문제점

  • 많은 프로세스가 임계영역에 들어가기를 원할 때 기아가 발생할 수 있음 (계속 대기하게 될 수도 있음)
  • 진입영역에 갇혀서 Busy waiting을 함으로써 다른 작업이 사용할 수 있는 CPU 사이클을 낭비

세마포어(semaphore)

  • Dijkstra가 제안한 동기화 도구
  • 세마포어 s : 사용 가능한 자원의 수 또는 잠김/열림 등의 상태를 나타내는 값을 저장하는 정수형 공용변수
  • 세마포어 s는 두 표준단위 연산 P와 V에 의해서만 접근됨

P(s) : 검사, 감소시키려는 시도

if (s > 0) then
    s := s - 1;
else
    현재 프로세스 대기;

V(s) : 증가

if (1개 이상의 프로세스가 대기 중) then
    그 중 1개의 프로세스만 진행;
else
    s := s + 1;

상호배제 구현 방법

repeat
    p(mutex); // 진입영역
    (임계영역);
    V(mutex); // 해제영역
    (잔류영역);
until false;

동기화 문제 해결
프로세스1이 문장 S1을 실행한 후, 프로세스2가 문장 S2를 실행하도록 동기화하고 싶다면? (block / wakeup 프로토콜)

  • 프로세스1
S1;
V(sync); // 다음 프로세스를 깨워주기 때문에 wakeup이라고 표현함
  • 프로세스2
P(sync); // 작업을 기다리기 때문에 block이라고 표현함
S2;
Last Updated: