운영체제 16. 결정성 문제를 어떻게 해결할까

결정성 문제를 어떻게 해결하는가?

[!NOTE] 먼저, 프로세스 시스템 개념을 정의하자.{title} 프로세스의 집합과, 선행 제약들을 프로세스 시스템이라고 정의한다. 선행 제약(precedence relation)이란 프로세스의 실행 순서다. 즉, \(P_{1}, P_{2}, \dots, P_{n}\) 프로세스가 있을 때 선행 제약은 \(P_{i} < P_{j}\)와 같이 표시된다. 이는 \(P_{i}\)를 먼저 실행해야 한다는 의미다.

언제 프로세스 시스템이 비결정적일까? 한번이라도 Race Condition이 발생하면 비결정적이게 된다. 이를 간섭이라고 부르자. 반대로 말하면, 모든 상호작용하는 프로세스가 비간섭이면 프로세스 시스템은 결정적이다.

선행 제약 관계가 없는 두 프로세스는 독립적이라고 한다. 선행 제약 관계가 있다면 비순환적이어야 한다. 만약 순환적이라면?

\[P_{i} < P_{j} < P_{i} < P_{j} < \dots\]

무엇을 먼저 실행해야 하는가? 모순이 발생한다.

따라서 프로세스 시스템 내의 프로세스들은 서로 독립적이거나, 선행제약 관계가 있다면 비순환적이어야 한다는 조건이 있다.

두 프로세스가 선형제약 관계라면, 반드시 순서화 되있으므로 간섭이 발생하지 않는다. 두 프로세스가 독립적이고, 공유 자원이 있다면 간섭이 발생할 수 있다. 간섭이 생기는 경우는 두가지가 있다.

• 동시에 Write하려 할 때.
• 동시에 Write와 Read하려 할 때.

[!question]- 왜 Write와 Read 관계가 문제되는가?{title} 만약 한쪽에서 n=n+1을 수행하고, 다른쪽에서 t = n을 수행한다고 해보자. write가 실행됐어. 그리고 레지스터에 갖고와서 1 더하는거까지 했어. 그리고 나서 context switch가 되어 read를 했어. 그럼 write되기 전의 값을 들고가겠지? 그리고 나서 1이 더해져. 의도한 동작은 write 이후 1이 더해진 값을 read해야 했을 거야. 따라서 간섭이 발생했어.

따라서 두 프로세스가 비간섭 관계라면, 두 조건중 하나를 만족해야 한다.

• 두 프로세스가 선형 제약 관계다.
• 두 프로세스가 독립적이고, 두 프로세스의 사이의 공유 자원에 Write하지 않는다.

write하는 동시에 다른 프로세스가 write or read하면 간섭이 발생한다.

따라서, 프로세스 시스템이 결정적이라는 것은 모든 프로세스가 비간섭인 것과 동치다. 다음은 어떤 프로세스 시스템의 결정성을 판단하는 Flow Chart다.

만약 간섭적이면 뮤텍스, 세마포어 등의 상호 배제가 가능하게 하는 도구를 사용해서 두 프로세스의 실행 순서를 부여해야 한다. 그러면 선행 관계가 생기므로, 프로세스 시스템이 결정성을 만족하게 된다.