[Chapter 6. 프로세스 동기화] 프로세스의 비간섭 관계와 결정성

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

 

협력적 프로세스의 주요 이슈 : 결정성 / 상호 배제와 동기화 / 교착 상태 / 기아

 

프로세스 비간섭 관계

---

프로세스 시스템에서 두 개의 프로세스가 있을 때

1. 한 프로세스가 다른 프로세스를 선행하거나 (이 경우에는 간섭이 발생할 가능성이 없음)

2. 이들이 서로 독립적일 경우

한 프로세스의 출력 장소가 다른 프로세스의 입력 장소나 출력 장소가 아니면

이들은 비간섭 관계에 있다고 정의한다.

 

 

두 프로세스가 독립적이라는 것은 두 프로세스 사이에 선행 제약 관계가 없다는 것이다.

 

만약 두 프로세스가 독립적이지 않고, 둘 사이에 선행 제약 관계가 존재한다면 이는 비순환적이어야 한다.

 

선행 제약(precedence relation) 관계

부분 순서(partial order) 성질을 갖는 관계 즉, 이행성(transitive relation)을 가지는 관계이다.

 

프로세스 P1, P2, ... , Pn이 있고, 선행 순서가 Pi < Pj로 표시된다고 한다면

Pi < Pj, Pj < Pk일 때 Pi < Pk를 만족한다는 것이다.

 

 

선행 그래프

프로세스 간의 선행 제약 관계를 방향 그래프로 표현한 것이다.

 

(예시) 순환이 내포된 선행 그래프

 

P3 < P2이고 P2 < P3이기 때문에 P3 < P3이라는 모순이 생기며

선행 그래프 상에서 순환하는 것으로 나타나, 선행 제약 관계의 판단이 불가능하다.

 

---

그렇다면 프로세스들이 전부 독립적이거나 비순환적 선행 관계가 있다면 더 이상 문제가 없는 것일까?

 

아니다!

아래 두 예제를 보자.

 

메모리에는 공유 변수 a와 b가 있다. (초기값 a = 1, b = 2)

 

프로세스 P1가 P2가 있고, 이 둘은 독립적이다.

두 프로세스들은 예제 1, 예제 2마다 각각 정해진 일을 한다.

 

	예제 1 (상대방 입력 셀에 출력)	예제 2 (같은 출력 셀에 출력)
P1	a ← a + b	a ← a + b
P2	b ← a + b	a ← b

 

활동 순열은 다음과 같다. (r : read / w : write)

P1 : r1 w1

P2 : r2 w2

 

(예제 1)

 

1. 프로세스 실행 순서 : P1 → P2

 

	초기값	r1	w1	r2	w2
a 값	1	1	3	3	3
b 값	2	2	2	2	5

 

2. 프로세스 실행 순서 : P2 → P1

 

	초기값	r2	w2	r1	w1
a 값	1	1	1	1	4
b 값	2	2	3	3	3

 

(예제 2)

 

1. 프로세스 실행 순서 : P1 → P2

 

	초기값	r1	w1	r2	w2
a 값	1	1	3	3	2
b 값	2	2	2	2	2

 

2. 프로세스 실행 순서 : P2 → P1

 

	초기값	r2	w2	r1	w1
a 값	1	1	2	2	4
b 값	2	2	2	2	2

 

두 예제 모두 프로세스가 실행되는 순서에 따라 결과값이 달라지는 것을 볼 수 있다.

 

이는 P1과 P2가 변수 a와 b를 공유하면서

상대의 입력 변수에 출력을 하기 때문에 문제가 발생하는 것이다. (간섭 발생)

 

 

이때 나타나는 개념으로는 '결정성'이 있다.

 

결정성

---

프로세스 시스템 내의 프로세스들 간의 코드 실행 순열이 매번 다를 수 있지만

같은 조건과 입력이 주어진다면 항상 같은 결과를 산출해야 한다는 성질을 말한다.

 

아래의 선행 그래프를 띠는 프로세스 4개가 있고, 각각 다음의 코드 순열을 가진다고 하자.

 

프로세스	코드 순열
P1	a1 b1 c1
P2	a2 b2
P3	a3 b3 c3
P4	a4 b4

 

가능한 실행 순열은

     1. a1 b1 c1 / a2 b2 / a3 b3 c3 / a4 b4

     2. a1 b1 c1 / a3 b3 c3 / a2 b2 / a4 b4

     3. a1 b1 a3 c1 b3 a2 c3 b2 a4 b4

등등으로 다양하다.

 

이 실행 순열들이 모두 같은 결과를 낸다면 해당 시스템은 결정성을 가진다는 것이다.

 

---

한 프로세스 시스템에서 모든 프로세스 쌍에 대해 비간섭 관계가 성립하면

그 시스템은 비간섭 관계를 만족한다고 하며,

 

한 프로세스 시스템에 있어서 비간섭 관계는 그 시스템이 결정적인가에 대한 필요충분조건이다.

(비간섭 관계 → 결정성이 생긴다)

 

선행 제약, 독립성, 간섭, 결정성 간의 관계

 

결정성 지원 방향

우리는 프로세스 시스템 혹은 스레드들을 결정성 있도록 개발해야 함을 깨달았다.

결정성을 위하여 제공되는 것들에는 무엇이 있을까?

 

1. 선행 제약 관계를 명시하도록 지원

상호작용 프로세스나 스레드용 표현법을 제공하여 프로그래머가 상호작용 프로그래밍을 할 수 있도록 한다.

 

(1) parbegin / parend

parbegin과 parend 사이의 각 문장은 독립적 프로세스로 실행됨을 명시할 수 있다.

 

S0;
parbegin
  // 병렬 수행
  S1;
  S2;
  //
parend
S3;

 

(2) fork / join

fork으로 프로세스의 분기, join으로 프로세스의 합류를 명시할 수 있다.

join n;

...

n--; // 각 프로세스 종료 시 n-1
if (n != 0) exit; // 전체 프로세스 종료

 

2. 공유 변수 간섭 문제에 대한 해결 방법을 지원

공유 변수에 대한 상호 배제 및 동기화 프로그래밍 방법(수단)을 제공한다.

 

• 임계 구역
• 상호 배제(Mutex)
• 세마포어(Semaphore) 등등..