[OS] 8. 프로세스 동기화

KYJ의 Tech Velog·2023년 4월 13일

OS Operating System Process Synchronization process 운영체제 프로세스 프로세스 동기화

OS

목록 보기

10/23

프로세스 동기화

프로세스 동기화란 프로세스가 공유하는 자원의 일관성을 유지하는 것을 의미합니다.

Race Condition (경쟁 상태)

여러 프로세스들이 동시에 데이터에 접근하는 상황에서 어떤 순서로 데이터에 접근하냐에 따라 결과 값이 달라질 수 있는 상황을 의미합니다.

공유 데이터의 동시 접근은 데이터의 불일치 문제를 야기할 수 있습니다. Race Condition을 막고 일관성을 유지하기 위해서는 프로세스 간의 실행 순서를 정해주는 동기화가 필요합니다.

Critical Section (임계 영역)

코드 상에서 Race Condition이 발생할 수 있는 특정 부분을 의미합니다. 바로 공유 데이터에 접근하는 코드 부분입니다.

Critical Section때문에 발생하는 문제들은 다음 조건들을 만족해야 해결될 수 있습니다.

Mutual Exclusion (상호 배제)
프로세스가 Critical Section에서 작업중이면 다른 프로세스는 Critical Section에 진입 불가능
Progress (진행)
Critical Section에서 작업중인 프로세스가 없다면 Critical Section에 진입하고자 하는 프로세스가 있을 경우 진입 가능
Bounded Waiting (한정 대기)
프로세스가 Critical Section에 진입하기 위해 요청한 후부터 허용될 때까지 다른 프로세스가 Critical Section에 들어갈 수 있는 횟수가 제한

동기화 알고리즘

알고리즘 1

Critical Section에 들어갈 프로세스가 어떤 프로세스인지 한 변수로 나타내어 일치하는 프로세스만 진입하는 방식입니다.

int turn;

do
{
	while(turn != i); // 내 순서인지 확인
    // critical section
    turn = j; // 이제 다음 순서
    // remainder section
} while(true);

이 방식은 Mutual Exclusion은 만족하지만 Progress를 만족하지 못합니다. 프로세스 Pi가 진행되려면 Pj에서 프로세서가 돌고 공유 변수 값을 전달해야만 Pi가 진행이 됩니다. 만약 Pj가 진행이 되지 않는다면 Pi는 무한 대기 상태가 됩니다.

알고리즘 2

특정 프로세스가 Critical Section에 진입할 준비가 되었다는 것을 알려주는 변수를 두어 다른 프로세스가 Critical Section에 진입하려 하면 현재 프로세스는 기다리는 방식입니다.

bool flag[2];

do
{
	flag[i] = true;
	while(flag[j]);
    // critical section
    flag[i] = false;
    // remainder section
} while(true);

이 방식도 알고리즘 1과 마찬가지로 Mutual Exclusion은 만족하지만 Progress를 만족하지 못합니다. 두 프로세스가 flag = true 구문을 수행하면 두 프로세스 모두 무한 대기 상태가 됩니다.

알고리즘 3 (Peterson's Algorithm)

알고리즘 1,2를 합쳐놓은 방식입니다.

do
{
	flag[i] = true;
    turn = j;
	while(flag[j] && turn == j);
    // critical section
    flag[i] = false;
    // remainder section
} while(true);

이 방식은 Mutual Exclusion, Progress, Bounded Waiting 모두 만족합니다. 하지만 프로세스들이 Critical Section 진입을 대기하면서 계속 자원을 사용하는 Busy Waiting 문제가 있습니다.

하드웨어 동기화

현대 기계들은 Atomic(중단되지 않는)한 하드웨어 명령을 제공합니다. 이 명령들을 사용하면 Critical Section의 문제들을 해결할 수 있습니다.

TestAndSet

bool TestAndSet(bool &target)
{
	bool rv = target;
    target = true;
    return rv;
}

do
{
	while(TestAndSet(&lock));
   	// critical section
    lock = false;
    // remainder section
} while(true);

lock은 false로 초기화되어 있습니다. 처음으로 실행한 프로세스는 첫 반복문을 통과합니다. 그리고 TestAndSet 함수에 의해서 lock은 true가 되어 다른 프로세스가 Critical Section에 진입하려 해도 반복문에 걸려 실행할 수 없습니다. 여기서 Mutual Exclusion을 만족합니다.

그리고 Critical Section을 끝낸 프로세스는 lock을 다시 false로 바꿔 다른 프로세스도 Critical Section에 진입할 수 있도록 합니다. 여기서 Progress도 만족합니다.

하지만 Bounded Waiting을 만족하지 못합니다.

Swap

bool Swap(bool &a, bool &b)
{
	bool tmp = a;
    a = b;
    b = tmp;
}

do
{
	key = true;
	while(key) Swap(lock, key);
   	// critical section
   	lock = false;
    // remainder section
} while(true);