병행 프로세스 1

병행 프로세스는 여러 개의 프로세스가 동시에 병행하여 실행되는 것을 의미한다. 최근 많은 응용에서 단순한 순차 처리가 아닌 병행 처리를 필요로 하고 있다. 일례로 멀티미디어 응용에서는 여러 종류의 미디어가 동시에 재생되어야 하며, 이를 위한 처리가 병행하여 이루어져야 한다. 특히 이처럼 병행 처리되는 프로세스가 서로 유기적으로 상호작용하며 동작하기 위해서는 해결해야 할 많은 문제가 발생한다. 병행 프로세스의 기본 개념과 함께, 병행 프로세스의 처리과정에서 이슈가 되는 자원의 공유, 동기화 등을 위해 제공되는 장치들에 대하여 살펴본다.

 

• 학습목표

• 병행성의 개념을 설명할 수 있다.

---

• 병행 프로세스의 실행으로 인해 발생할 수 있는 자원의 공유, 동기화 등의 문제를 설명할 수 있다.

---

• Test-and-Set과 세마포어의 개념을 이해한다.

• 병행 프로세스의 실행 형태
  • CPU의 개수에 따른 병행 프로세스의 실행 형태
    • 하나의 CPU에서 인터리빙 형식으로 실행
    • 여러 개의 CPU에서 병렬 처리 형식으로 실행
  • 메모리 구조에 따른 병행 프로세스의 실행 형태
    • 강 결합 멀티 프로세서 시스템 -> 공유 메모리 구조
    • 약 결합 멀티 프로세서 시스템 -> 분산 메모리 구조
• 병행성 문제
  • 변행 프로세스들이 상호작용 하는 경우 발생
    • 공유자원 점유 문제
    • 동기화 문제
    • 통신 문제
  • 상황에 따른 구분
    • 단일 프로세스 내의 병행성
    • 프로세스 간의 병행성
  • 단일 프로세스 내의 병행성
    • 우선순위 그래프
      • 점점 : 문장, 간선 : 선후 관계
    • Fork/Join 구조
      • fork L : 2개의 병행 수행을 만듦(레이블 L 위치부터와 fork 명령어 다음부터)
      • join n : 병행하는 n개의 흐름을 하나로 재결합
    • 병행문
      • 1개의 프로세스가 여러 가닥의 병렬 프로세스로 분할되었다가 다시 하나로 결합
      • parbegin / parend 문
  • 프로세스 간의 병행성
    • 비동기 병행 프로세스
      • 프로세스 A <-> 유기적 프로세스 (공유 자원) <-> 프로세스 B
  • 동기화와 임계영역
    • 프로세스 동기화
      • 2개 이상의 프로세스에 대한 처리 순서를 결정하는 것
      • 예) 동시에 사용할 수 없는 공유자원, 한 프로세스의 처리 결과에 따라 다른 프로세스의 처리가 영향을 받는 경우
    • 임계영역
      • 2개 이상의 프로세스가 동시에 액세스하면 안 되는 공유자원을 액세스하는 코드 영역
    • 상호배제
      • 2개 이상의 프로세스가 동시에 임계영에 진입하지 못하도록 하는 것
    • 임계영역의 예
      • 상호배제를 통한 프로세스 동기화
    • 임계영역을 갖는 프로세스의 일반적 구조
      • repeat
        • 진입영역
        • 임계영역
        • 해제영역
        • 잔류영역
      • until false;
    • 임계영역 문제 해결을 위한 요구조건
      • 상호배제
        • 한 프로세스가 임계영역에서 실행 중 -> 다른 어떤 프로세스 실행 x
      • 진행
        • 임계영역에서 실행 중인 프로세스가 없고 여러 프로세스가 임계영역에 진입하고자 할 때 그중에서 적절히 한프로세를 결정해야하며 이 결정은 무한정 미룰 수 없음
      • 제한된 대기
        • 한 프로세스가 임계 영영 진입 요청을 한 후 수락될 때까지 다른 프로세스가 임계영역 진입을 허가 받는 횟수는 제한이 있어야 함
    • 임계영역 문제 해결을 위한 도구
      • Test-and-Set 명령어 (TS 명령어)
        • 상호배제의 하드웨어적 해결 방법
        • 분리가 불가능한 단일 기계 명령어 (원자적으로 수행)
        • 상호배제의 구현

repeat
	while Test_and_Set(lock) do skip;
    임계영역
    lock := false;
    잔류영역
until false;

• 문제점
  • 많은 프로세스가 임계영역에 들어아기를 원할 때 기아가 발생할 수 있음
    • (기아 : 프로세스가 필요한 자원 할당을 받지 못하고 계속적으로 대기하게 되는 상황)
  • Busy waiting을 함으로써 다른 작업이 사용할 수 있는 CPU 사이클을 낭비
• 세마포어 (semaphore)
  • Dijkstra가 제안한 동기화 도구
  • 세마포어 s:사용 가능한 자원의 수 또는 잠김/열림 등의 상태를 나타내는 값을 지정하는 정수형 공용 변수
  • 세마포어 s는 두 표준단위 연산 Pdhk V에 의해서만 접근됨
  • P(s) : 검사, 감소시키려는 시도
  • V(s) : 증가시키려는 시도
  • 상호배제의 구현
  • 동기화 문제 해결
    • 프로세스 1이 문장을 S1 실행한 후 프로세스2가 문장 S2를 실행하도록 동기화(block/wakeup 프로토콜)

P(s) : 검사, 감소시키려는 시도
if ( s > 0 > then
	s : s-1;
else
	현재 프로세스 대기

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