[운영체제] Process Synchronization (1) - Race Condition, Peterson's Solution

프로세스 동기화 파트에서는 앞에서 잠깐 설명한 적이 있는 Race Condition에 관한 문제를 다루게 됩니다. 프로세스들은 병렬적으로 실행이 될 수 있기 때문에 여러 프로세스가 공유하고 있는 데이터의 무결성에 문제를 야기할 수 있습니다. Race Condition에 대해서 먼저 알아보도록 하겠습니다.

 

1. Producer-Consumer Problem

가장 쉽게 Race Condition에 대해서 알아볼 수 있는 모델이 바로 생산자-소비자 모델입니다. 

 

Producer - Consumer Problem

위 그림과 같은 모델에서 A와 B는 버퍼를 공유하고 있고, A는 공유하고 있는 버퍼에 데이터를 채워 넣기만 하고, B는 데이터를 가져가기만 합니다. 버퍼가 가득 차있으면 A는 버퍼에 빈 공간이 생길 때까지 대기하여야 하고, 버퍼가 텅 비어있다면, B는 A가 데이터를 넣어줄 때까지 대기해야 합니다. 여기서 두 프로세스는 Counter라는 int형 변수를 이용해 버퍼에 얼마만큼의 데이터가 존재하는지 파악하게 됩니다. 이러한 상황에서 A와 B에서 실행되는 코드를 들여다보면, A에서는 데이터를 채워 넣을 때마다 "counter++"를 실행할 것이고, B에서는 데이터를 빼낼 때마다 "counter--"를 실행하게 될 것입니다. counter가 현재 5이고, A가 먼저 데이터를 채워 넣고 그 뒤에 B가 데이터를 가져가는 실행을 예로 들면, counter는 다음 그림과 같이 조작이 됩니다.

 

컴퓨터 구조에서 배웠듯이 Register 1에 counter 값을 가져와서 수정을 해준 뒤 다시 counter 변수에 옮겨주는 형태입니다. 결과적으로 데이터를 한 개 집어넣은 뒤 하나를 빼냈기 때문에, counter 값은 그대로 5가 되어 올바른 값이 나옵니다. 하지만, 타이밍의 문제로 A의 호출 거의 직후에 B가 실행되면 다음과 같이 실행되는 경우가 발생할 수 있습니다.

 

이 경우에는 A의 연산이 채 끝나기 전에 B가 실행되어 버려 결과적으로 counter는 잘못된 값인 4를 가지게 됩니다. 이렇게 잘못 저장된 counter의 값은 언젠가 시스템에 오류를 발생시키게 될 것입니다. 우리는 운영체제에서 다중 코어, 다중 스레드에 대해 이미 공부했기 때문에 이러한 일들이 빈번하게 일어날 수 있다는 사실을 알고있습니다. 하지만 우리는 이러한 Race Condition 문제가 발생하지 않기를 바라기 때문에, 반드시 동시에 실행되는 프로세스들 간에는 동기화 처리가 되어있어야 합니다.

2. Critical-Section Problem (임계구역 문제)

Critical Section (임계구역)이란 코드 중에 다른 프로세스와의 공유하고 있는 변수를 변경하거나, 파일을 쓰는 등, Race Condition이 발생할 수 있는 부분을 뜻합니다. 따라서 하나의 프로세스가 이미 Critical section 안에 들어가 있다면, 다른 프로세스들은 Critical section에 접근해서는 안됩니다. 두 프로세스가 동시에 하나의 Critical section안에 들어가게 되면 바로 위에서 봤던 것과 같이 타이밍의 문제로 올바르지 않은 값이 변수에 저장될 수 있기 때문입니다. 따라서 하나의 Critical section에는 하나의 프로세스만 접근할 수 있는 프로토콜을 설계하는 것이 중요합니다. 그리고 코드 중에 Critical section이 아닌, Race condition과 무관한 부분은 Remainder section이라고 부릅니다.

 

이러한 Critical section을 보호하기 위한 해결법을 만들 때에는 다음의 세 가지가 반드시 모두 지켜져야 합니다.

 

1. Mutual Exclusion (상호 배제)

Mutual Exclusion은 한 번에 하나의 프로세스만 Critical section에 들어갈 수 있다는 것입니다. 즉, 프로세스 A가 한 Critical section에서 실행되고 있다면, 다른 프로세스들은 이 Critical section을 실행할 수 없습니다.  

2. Progress (진행)

Progress는 한 Critical section에서 실행되고 있는 프로세스가 없는 상황에서, 어떤 프로세스가 그 Critical section에 들어가고 싶어 한다면, 들어갈 수 있어야 한다는 내용입니다. 즉, 비어있는 Critical section이 있다면, Remainder section에서 실행 중인 프로세스들을 제외한 다른 프로세스들은 Critical section으로의 진입을 요청할 수 있고, 진입을 요청한 프로세스들 중에서 알고리즘에 의해 다음으로 Critical section에 들어가게 될 프로세스가 결정되게 됩니다.

3. Bounded Waiting (한정된 대기)

Critical Section으로 들어가고자 하는 프로세스는 비록 지금은 알고리즘에 의해 우선순위가 밀려서 못 들어갈 수 있을지언정, 언젠가는 해당 Critical section에 진입할 수 있어야 한다는 내용입니다. 다시 말해 프로세스가 진입을 요청하게 되면 그 요청이 허용되어 Critical section에 들어가기까지, 그 사이에 다른 프로세스들은 정해진 횟수만큼만 들어갈 수 있어야 합니다.

 

그럼 다음의 코드는 세 가지를 모두 만족할까요? 

 

Strict Alternation

위의 방법을 Strict Alternation이라고 합니다. 이 방법은 프로세스가 2개만 존재한다는 가정 하에 만들어 진 방법입니다. 프로세스 i의 입장에서보면, j가 turn을 i로 바꿔줄 때까지 기다리다가, j가 바꿔주면, Critical section으로 들어가고, Critical section에서의 작업을 다 마치면 빠져나오면서 다시 turn을 j로 바꿔주고 Remainder section을 실행하게 됩니다. 그럼 j는 i가 Critical section에서 빠져나와서 turn을 j로 바꿔줄 때까지 while문 안에 갇혀있기 때문에 두 개의 프로세스가 동시에 Critical section을 실행할 일은 없는 것이죠. 

 

물론 이렇게 하면 실행은 됩니다. 하지만 위의 세 가지 조건 중 Progress를 만족하지 못하는 상황이 존재할 수 있습니다. 예를 들면, i가 Critical section에서 빠져나오면서 turn을 j로 바꿔줍니다. 이 때 프로세스 j는 while문에 갇혀있거나, Remainder section을 실행하고 있을 것입니다. j가 Remainder section을 실행하고 있다고 생각해 봅시다. 마침 j가 Remainder section에서 시간이 오래 걸려서 i가 먼저 Remainder section을 모두 수행하고 다시 while문에 들어가 Critical section에 들어가고 싶어 하는 상황이 생겼습니다. 이때 Critical section은 비어있고, i는 진입을 요청했기 때문에, Progress를 만족하려면, i는 Critical section에 들어갈 수 있어야 합니다. 하지만 j는 아직 Remainder section을 수행하고 있고, turn을 i로 바꿔줄 수가 없는 상황이죠. 이렇게 되면 Progress를 만족하지 못하게 됩니다. 다시 말해 상대방이 준비가 안되어 있는 상황에서 turn을 넘겨주게 되면 상황이 꼬일 수 있다는 것입니다.

 

3. Peterson's Solution

Strict Alternation이 문제점을 가지고 있었기 때문에 다음으로는 Peterson's Solution이라는 것이 등장하게 됩니다. 코드를 먼저 살펴보겠습니다.

 

Peterson's Solution

여기서는 두 가지 변수를 사용합니다. int turn과 boolean flag[2]입니다. turn은 누가 Critical section에 들어갈 차례인지를 나타내고, flag는 각 프로세스가 Critical section에 들어갈 준비가 되었는 지를 나타냅니다. flag 값이 true면 준비가 되어있다는 뜻입니다. 코드에 대해 설명하기보다는 개인적으로 자신 나름대로 코드를 따라가 보고 이해하는 편이 훨씬 좋을 것 같습니다. 간단하게만 설명하자면 상대방의 flag가 true여서, 상대방이 Critical section에 들어갈 준비가 되어있고, turn도 상대방에게 있는 상황에서만, 즉 상대방이 Critical section에 들어갈 모든 조건을 충족한 상태에서만, while문에서 Critical section으로 들어가기 위해 대기하게 되고, 상대의 flag나 turn 중 하나라도 만족하지 않으면 자신이 Critical section에 들어갈 수 있게 됩니다.

 

코드 상으로 Peterson's Solution은 세 가지 조건을 모두 만족합니다. 하지만, 우리가 예상하지 못한 문제가 하나 존재합니다. 바로 컴파일 도중에 코드의 순서가 바뀔수도 있다는 점입니다. 컴퓨터 구조에서 배웠듯이 컴파일러는 메모리 접근을 위해 컴파일 도중에 필요에 따라 코드들의 위치를 조금씩 조정하기도 합니다. 그래서 만약 Peterson's solution에서 제일 위의 코드인 flag [i] = true라는 줄과 두 줄 밑의 while(flag [j] && turn ==j);라는 줄의 순서가 바뀌면 제대로 동작하지 않을 수 있게 됩니다.

 

 

 

 

 

오늘은 프로세스 간의 동기화에 대해 알아보았습니다. 다음 글에서는 프로세스 동기화의 더 심화된 내용에 대해 공부해보도록 하겠습니다. 읽어주셔서 감사합니다.