[OS] 8. Process Synchronization and Mutual Exclusion 1

728x90

Process Synchronizatiton (동기화)

동기화라는 말을 생각해보면, 하나의 프로세스를 대상으로 하는 행위는 아닐 것이라는 생각이 들 것이다.

동기화라는 말의 사전적 의미를 먼저 들여다보자.

동기화(同期化, synchronization)는 시스템을 동시에 작동시키기 위해 여러 사건들을 조화시키는 것을 의미한다.

여러 사건, 즉 컴퓨터에서는 "여러 프로세스"에 대한 행위가 되는 것이다. 이에 여러 개의 프로세스가 존재하는 다중 프로그래밍 시스템 상에서 필요로 하는 것이 동기화이다.

왜냐하면 각 프로세스들은 서로 독립적으로 동작하는데, 만약 공유 자원이나 데이터에 동시에 접근하게 되면 이 때 문제가 발생한다. 만약 자원 A를 P1(=프로세스)과 P2이 동시에 접근한다고 하면, 작업 도중에 값이 바뀌어 원하는 값을 얻어오지 못할 것이다.

이러한 문제를 방지하기 위해 프로세스 간 상호 대화를 해야한다, 즉 "동기화"해야한다. 동기화란, 프로세스들이 서로 동작을 맞추거나, 서로 정보를 공유하는 행위를 말한다.

Asynchronous and Concurrent Process

프로세스들이 서로에 대해 알지 못하는 경우 비동기적(Asynchronous)이라고 말하고, 여러 개의 프로세스들이 동시에 시스템에 존재하는 경우를 병행적(Concurrent)이라고 말한다.

앞서 봤던 문제는, 병행 수행 중인 비동기적 프로세스들이 공유 자원에 동시 접근할 때 발생한다고 좀 더 자세하게 말할 수 있다. 왜냐, 동시에 작업하고 있는데 서로에 대해 모르고 있기 때문이다.

용어를 잠깐 정리하고 넘어가보자.

공유 데이터 (Shared data or Critical data)
- 여러 프로세스들이 공유하는 데이터
임계 영역 (Critical section, CS)
- 공유 데이터를 접근하는 코드 영역(code segment)
상호배제 (Mutual exclusion)
- 두 개 이상의 프로세스가 동시에 임계 영역(critical section)에 진입하는 것을 막는 것

임계 영역에 P1이 들어가서 작업하고 있다면, P2가 들어오지 못하게 막아줘야 원하는 기댓값을 얻을 수 있다.

이러한 상호 배제를 구현해주기 위해서는 아래와 같은 방법을 따라줘야 한다.

Mutual Exclusion Method

상호 배제(Mutual Exclusion)을 작동시키기 위해서는 구현해야하는 기본 연산(primitive)이 있다.

enterCS( )
- critical section 진입 전 검사
- 다른 프로세스가 critical section 안에 있는지 검사
exitCS( )
- critical section을 벗어날 때의 후처리 과정
- critical section을 벗어남을 시스템이 알림 (다음 프로세스가 들어올 수 있도록)

ME 구현 조건

우선 ME(Mutual Exclusion)을 구현하기 위한 조건들 3가지를 알고 있어야 한다.

상호 배제(Mutual exclusion)
- CS영역에 프로세스가 있다면, 다른 프로세스의 진입을 금지한다. (당연한 이야기!)
진행(Process)
- CS안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해하면 안된다.
- A, B 프로세스가 아직 CS영역에 진입하지 않았고, CS영역이 비어있을 때, A가 B의 진입을 방해하면 안된다는 이야기다!
- 즉, 안에 아무도 없다면 그냥 들어갈 수 있어야 한다.
한정대기(Bounded waiting)
- 프로세스의 CS 진입은 유한시간 내에 허용되어야 한다. (= 계속 기다리게 하면 안된다!)

상호 배제를 구현하기 위해 초기에는 다음과 같이 다양한 방법으로 시도했었던 것을 볼 수 있다. 하지만 초기의 방식들은 모두 위 조건들에 부합하지 않아 다른 방법으로 발전되었는데, 이는 차차 알아가보자.

ME 구현

Version 1

turn이라는 변수를 하나 두어, 이를 기준으로 어떤 프로세스가 CS 영역에 들어갈 수 있는지 정해주었다.

turn이 0이라면 P0을 실행하고, turn이 1이라면 P1을 실행시키는 구조이다. P0의 입장에서 보면 turn이 1이라면 현재 P1이 실행중이라고 파악하여 끝날 때까지 기다리고(endwhile), turn이 0이라면 CS 영역에 진입하여 작업을 마치면 turn을 1로 바꾸어주는 것이다.

이러한 구조에서는 두 가지 문제가 발생할 수 있는데 이는 모두 Progress(진행)을 위배한 경우이다.

P0이 CS영역에 진입하지 않는 경우
- 만약 P0이 CS 영역에 진입하여 작업을 수행하고 나오지 않는다면, turn은 계속 0에 머무르기 때문에 P1은 영원히 수행될 수 없어 progress 원칙을 위반하게 된다.
P0이 연속하여 두 번 진입하려는 경우
- 만약 P0이 작업을 마치고, 또 다시 CS 영역에 진입하려고 하는 경우에는 작업을 마친 이후부터 turn은 1로 바뀌기 때문에 다시 P0은 들어가지 못하고 P1만이 들어갈 수 있게 된다. 이 또한 CS내 프로세스가 아닌 다른 요소가 진입을 방해했다는 부분에서 progress 원칙을 위반하게 되는 것이다.

Version 2

version 2는 flag를 배열의 형태로 두어서 진입 여부를 막을 수 있도록 하였다. 이렇게 flag를 두면 version 1에서 발생했던 문제를 해결할 수 있다.

version 1과 마찬가지로 P0입장에서 보면 flag[1]이 true라면 현재 P1이 CS 영역에 있다는 것으로 인식하여 작업을 마칠 때 까지 대기하고, flag[1]이 false가 되어야 P0이 CS영역에 진입할 수 있게 된다. 그리고 작업을 시작함과 동시에, flag[0]을 true로 바꾸어, "나 작업중이야!!"라고 알린다. 그리고 마찬가지로 작업을 마치면 다른 프로세스가 들어올 수 있도록 flag[0]을 false로 바꾸어 CS 영역에서 나왔음을 표현해준다.

이 경우에는 상호 배제 원칙을 어기는 경우가 발생할 수 있는데, 상황은 다음과 같이 P0이 CS에 진입하려고 할 때 선점(preemptive)가 발생한 경우이다.

P0이 CS영역에 진입하려다가 다른 프로세스가 선점하여 P0이 더 이상 진행되지 않는 경우
- flag[0]을 true로 돌리지 못하고 선점당했기 때문에, P1이 볼 때 현재 CS 영역에는 아무 프로세스도 없어 진입하게 된다.
- 그 이후, P0이 다시 CPU를 할당 받아서 작업을 재개하게 되면 현재 CS 영역에 P1이 작업을 수행하고 있음에도, P0도 들어가서 작업을 수행하게 되어 ME 원칙을 어기게 된다.

그러면 다음과 같이 flag를 조금 더 일찍 바꿔줄 수 있도록 하면 문제를 해결할 수 있을까?

아니다!

문제를 근본적으로 해결하기 보다는 오히려 다른 문제를 불러일으킬 수 있다!

P0이 진입하기 전 flag[0]를 true로 하고 선점 당한 후, P1이 진입하는 경우
- P0이 진입하기 전에 flag[0]만 true로 바꾸고 선점당한 후, P1이 진입하려고 우선 flag[1]을 true로 해주면 현재 flag[0]이 true이기 때문에 들어갈 수 없게 된다.
- 이 때 다시 P0이 돌아와서 CS 영역에 진입하려고 하면 flag[1]이 true이기 때문에, P0과 P1 모두 CS 영역에 진입할 수 없게 되고 계속 제자리에서 돌기만 할 것이다. 그렇기에 두 프로세스 모두 CS 영역에 진입할 수 없다는 점에서 Bounded waiting을 위반하고, CS 영역 내의 프로세스가 아닌 다른 요소에 의해 진입을 방해받는다는 점에서 Progress를 위반하게 된다.

이러한 조건들에 부합하는 방법들은 다음 강의를 통해 알아보도록 하자!

Ref:

https://ko.wikipedia.org/wiki/%EB%8F%99%EA%B8%B0%ED%99%94

https://www.youtube.com/watch?v=wdaf2gy83uU&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=12&t=4s