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

목차

1. 병행 프로세스의 개념
2. 동기화와 임계 영역

---

:   병행성 

■ 병행성(concerrency)

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

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

 

:   병행 프로세스의 실행 형태 

■ CPU의 개수에 따른 병행 프로세스의 실행 형태

- 하나의 CPU에서 인터리빙 형식으로 실행

- 여러 개의 CPU에서 병렬 처리 형식으로 실행

 

:   병행 프로세스의 실행 형태 - 여러 개의 CPU 

■ 메모리 구조에 따른 병행 프로세스의 실행 형태

- 강 결합 멀티 프로세서 시스템 : 공유 메모리 구조

- 약 결합 멀티 프로세서 시스템 : 분산 메모리 구조

 

:   병행성 문제 

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

- 공유자원 점유 문제

- 동기화 문제

- 통신 문제

 

■ 상황에 따른 구분

- 단일 프로세스 내의 병행성

- 프로세스 간의 병행성

 

:   단일 프로세스 내의 병행성 

- 우선순위 그래프

- Fork / Join 구조

- 병 행문

 

■ 우선순위 그래프

- 정점 : 문장

- 방향 있는 간선 : 우선순위 관계

 

■ Fork/ Join 구조

- fork L : 2개의 병행 수행을 만듦(레이블 L위치, fork 명령아 다음)

- join n : 병행하는 n개의 흐름을 하나로 재결합

 

■ 병 행문

- 1개의 프로세스가 여러 가닥의 병렬 프로세스로 분할되었다가 다시 하나로 결합

- parbegin / parend 문

 

:   프로세스 간의 병행성 

■ 비동기 병행 프로세스

 

:   동기화와 임계 영역 

■ 프로세스 동기화

- 2개 이상의 프로세스에 대한 처리 순서를 결정하는 것

- ex) 동시에 사용할 수 없는 공유자원, 한 프로세스의 처리 결과에 따라 다른 프로세스의 처리가 영향을 받는 경우

 

■ 임계 영역

- 2개 이상의 프로세스가 동시에 액세스 하면 안 되는 공유자원을 액세스 하는 코드 영역

 

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

-----------------------

| repeat                |  

|        진입 영역      |

|        임계 영역      |

|        해제 영역      |

|        잔류 영역      |

|until false;            |

-----------------------

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

■ 상호 배제

- 한 프로세스가 임계 영역에서 실행 중일 때

  다른 어떤 프로세스도 임계영역에서 실행될 수 없음

 

■ 진행

- 임계영역에서 실행 중인 프로세스가 없고 여러 프로세스가 임계영역에 진입하고자 할 때

  그중에서 적절히 한 프로세스를 결정해야 하며 이 결정은 무한정 미룰 수 없음

 

■ 제한된 대기

- 한 프로세스가 임계 영역 진입 요청을 한 후 수락될 때까지

  다른 프로세스가 임계영역 진입을 허가받는 횟수는 제한이 있어야 함

 

:   Test-and-Set 

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

- 상호 배제의 하드웨어적 해결 방법

- 분리가 불가능한 단일 기계 명령어(원자적으로 수행)

function Test and Set(var target: boolean : boolean;)
	begin
    	Test_and_Set:= target;
        target:= true;
    end

■ 상호배제의 구현

repeat
	while Test_and_set(lock) do skip; // lock의 초기값은 fasle
    임계영역
    lock:= flase;
    잔류영역
until false;

■ 문제점

- 많은 프로세스가 임계 영역에 들어가기를 원할 때 기아가 발생할 수 있음

- Busy wating을 함으로써 다른 작업이 사용할 수 있는 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;

■ 상호 배제의 구현

// 세마포어 mutex의 초기값은 1
repeat
	P(mutex); 
    임계영역
    V(mutex);
    잔류영역
until false;

■ 동기화 문제 해결

- 프로세스 1이 문장 S1을 실행한 후

  프로세스 2가 문장 S2를 실행하도록 동기화(block/wakeup 프로토콜)

// 세마포어 sync의 초기값은 0

/* 프로세스 1 */
S1;
V(sync); // wakeup

/* 프로세스 2 */
P(sync); // block
S2;

---

정리하기

- 병행 시스템은 여러 개의 프로세스가 동시에 실행되며, 이들이 상호작용함에 따라 공유자원 점유, 동기화, 통신 등의 문제 발생

- 동기화는 2개 이상의 프로세스에 대한 처리 순서를 결정하는 것을 의미

- 임계 영역 : 2개 이상의 프로세스가 동시에 액세스 하면 안 되는 공유자원에 액세스 하는 코드 영역

- 상호 배제 : 2개 이상의 프로세스가 임계 영역에 진입하지 못하도록 막는 것

- P와 V라는 원자 연산에 의해서만 접근되는 정수형 공용 변수인 세마포어를 이용하여 상호 배제 및 동기화 구현 가능