4강 4강 병행프로세스 1

학습목표

1. 병행성의 개념을 설명할 수 있따.

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

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

4. 세마포어를 이용하여 생산자/소비자. 판독기/ 기록기 문제를 해결할 수 있다.

5. 프로세스 사이에 통신을 위한 논리적 구조에 대해 설명할 수 있다.

 

주요용어

#병행성 # Fork/join #프로세스의 동기화 #임계영역 #상호배제 #세마포어 #생산자/소비자문제 #판독기/기록기문제 #메세지시스템

 

 

 

 

4.1 병행 프로세스의 개념

 

 

4.1.1 병행성 ( concurrency ) 

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

이때,  동시에 실행되는 여러 개의 프로세스 또는 쓰레드를 앞으로 병행 프로세스라고 부른다.

 

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

위에서 부터 1,2,3, 이라고 하면  1 > 2 > 3 > 1 > 2 > 3 순으로 돌아가면서 실행

 

병행성 문제 

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

-공유자원 점유 문제

-동기화 문제

-통신 문제

 

상황에 따른 구분

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

-프로세스 간의 병행성 

 

 

 

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

 

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

 

(1) 우선순위 그래프

 어떤 연산의 일부분이 가지는 우선순위 제약조건을 정의하는 데 유용한 방법

 

 

S1 :  a := x + y;

S2 :  b := z + 1;

S3 :  c := a + b;

S4 : write(c):

 

위에서 문장 S3은 a 와 b의 연산이 모두 완료되기 전에는 실행할 수 없다.

비슷한 방법으로 S4는 c의 새로운 값이 연산되기전에는 수행될숭벗다.

그러나 S1과 S2는 동시에 실행 가능하며, 문장 사이에 우선순위 제약조건 (precesence constraints)이 존재하는것을 보여준다.

 

우선순위 그래프란 각 정점이 개개의 문장에 대응하는 사이클이 없는 방향 그래프(directed acyclic graph) 이다.

 

 

(2) Fork/Join 구조 

 

Fork/Join 명령어는 병행성을 식별하는 최초의 언어 표기법이다.

 

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

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

 

 

 

fork L1문이 수행될때 b : z +1; 이 시작 되며, a:=x+y; 와 동시 수행된다.

fork 문장은 단일 연산을 2개의 독립적인 연산과 분할한다.

join 명령어는 병행하는 2개의 연산을 하나로 재결합시키는 방법을 제공

Fork/Join 구조는 다중 쓰레드 프로그래밍을 할 때 주로 이용된다.

 

 

(3) 병행문

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

병행성을 식별하는 고급 언어구조 는 parbegin/parend 문에서 볼수 있다.

 

 

 

4.1.3 프로세스 간의 병행성

 

프로세스가 서로 완전히 독립하여 수행되거나 다른 프로세스와 가끔 협력하면서 기능을 수행하는 방법으로 구분

특히 프로세스 간의 병행성에서 상호 협력하는 경우를 비동기적(asynchronous)이라고 말하며, 때때로 자원을 공유해야 되기 때문에 다소 복잡하다.

 

비동기 병행 프로세스는 어떤 프로세스가 실행 중인 다른 프로세스에 영향을 주는 유기적 프로세스가 된다.

 

 

 

 

4.2. 동기화와 임계영역

 

프로세스 동기화 ( synchronization ) :

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

예 : 동시에 사용할 수 없는 공유자원. 한 프로세스의 처리결화에 따라 다른 프로세스의 처리가 영향을 받는 경우

 

 

임계영역 (critial section ) 

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

 

상호배제 ( mutual exclusion ) 

2개 이상의 프로세스가 동시에 임계영역에 진입하지 못하도록 하는것

 

 

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

 

상호배제

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

 

진행 

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

 

제한된 대기 

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

 

 

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

 Test-and-Set 

 세마포어

 

 

 

4.2.1 Test-and-Set 

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

 

Test-and-Set 의 개념을 추상화해 보면,

 

function Test_and_Set(var target: boolean): boolean; 

          begin

                    Test_and_Set:= target;

                    target:= true;

           end

 

명령의 중요한 특징은 원자적으로 (atomically ) 수행된다는 점이다.

원자적이란 인터럽트되지 않는 하나의 단위로 처리됨을 의미한다.

 

 

이런 Test-and-Set 는 두가지 결점을 가지고 있다.

 

1. 많은 프로세스가 절대 영역에 들어가기를 원할 떄 기아가 발생

 >>> 프로세스가 임의의 접근을 시도하기 때문이다. FCFS 정책이 정해지지 않는 다면 어떤프로세스가 실행되지 못할 수도 있다.

(기아 ( starvation ) : 쓰레드가 필요한 자원할당을 받지 못하고 계속 적으로 대기하게 되는 상황 )

 

2. 대기 프로세스는 비생산적이고 자원만을 소비하는 busy waiting이 일어나게 된다.

 

 

 

 

4.2.2 세마 ( semaphore ) 포어

세마포어 s : 사용 가능한 자원의 수 또는 잠김/열림 등의 

                상태를 나타내는 값을 저장하는 정수형 공용변수

세마포어 s는 두 표준단위 연산 P와 V에 의해서만 접근됨

P : 네덜란드어로 검사 ( proberen, 또는 감소시키려는 시도, probeerte verlagen )

V : 증가 (verhogen)

 

 

세마포어는 또한 여러 가지 동기화 문제를 해결하는데 사용된다. 한 프로세스가 입출력을 요구하면 입출력이 끝날 때까지 그 프로세스는 블록 상태가 된다. 그러면 다른 프로세스는 이 블록 상태의 프로세스를 깨워야 한다.

이를 block/wakeup 프로토콜이라 한다. 

 

 

 

 

 

3강 제 3강 스케줄링 알고리즘

3강 제 3강 스케줄링 알고리즘