[OS] Process Synchronization - 1

본 글은 반효경 교수님의 운영체제 강의를 들으며 정리하는 글 입니다.

 

1. Critical Section 문제를 해결하기 위한 충족 조건

▶ 상호 배제 (Mutual Exclusion)

어떤 프로세스가 임계 구역 부분을 수행 중이면 다른 모든 프로세스는 그의 임계 구역에 들어가면 안 된다.

즉, 상호 배타적이여야 한다.

 

▶ 진행 (Progress)

아무도 임계 구역에 있지 않은 상태에서 임계 구역에 들어가고자 하는 프로세스가 있으면 임계 구역에 들어가게 해 주어야 한다.

 

▶ 유한 대기 (Bounded Waiting)

프로세스가 임계 구역에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 임계 구역에 들어가는 횟수에 한계가 있어야 한다.

ex) 세 개의 프로세스가 있을 때 두 개의 프로세스만 번갈아가며 임계 구역에 들어가는 것은 유한 대기 조건을 만족하지 못한 것이다. 즉 기아 현상이 생기면 안된다.

 

2. Critical Section 문제 해결 알고리즘

Algorithm 1

▶ Synchronization variable

int turn; 
initially turn = 0; // 몇 번 프로세스가 들어갈 수 있는지를 알려주는 turn 변수

turn 이 0이라면 P0이 들어가게 되고, 1이라면 P1이 들어가게 된다.

 

▶ Process P0

turn 변수가 0이 아닌 동안 while문을 계속 돌면서 자기 차례를 기다린다.

do {
    while (turn != 0); // 계속 기다림, busy waiting
    critical section
    turn = 1;
    remainder section
} while (1);

 

mutual exclusion은 만족하지만 progress는 만족하지 않는다.

반드시 한 번씩 교대로 임계 구역에 들어가야 하기 때문이다.

 

만약 P0은 임계 구역에 총 5번 들어가야 하고, P1은 한 번만 들어가면 된다고 가정해 보자.

P1은 한 번 임계 구역에 들어가고 나오면 끝나지만, P0은 프로세스 1이 다시 들어갈 때까지 본인도 못 들어가므로 progess 조건이 성립하지 않는다.

 

P1이 꼭 임계 구역에 들어가야만 그 다음으로 P0가 임계구역에 들어갈 수 있는 점이 문제다.

 

Algorithm 2

▶ Synchronization variable

boolean flag[2];
initially flag[모두] = false; // critical section에 들어가고자 하는 의사 표시

만약 임계 구역에 들어가는 Pi가 있다면, 들어가면서 flag[i] = true로 바꿔준다.

 

▶ Process Pi

do {
    flag[i] = true; // 내가 임계 구역에 들어갈려 한다는 점을 표시한다
    while (flag[j]); // 상대방 flag를 확인한다
    critical section
    flag[i] = false; // 탈출 처리
    remainder section
} while (1);

 

상대방이 임계 영역에서 빠져 나왔을 때 내가 들어간다.

 

mutual exclusion은 만족하지만 progress는 만족하지 않는다.

프로세스 A가 임계 구역에 들어가려고 flag를 true로 바꾼 상황에서(flag[A] = true 인 상황) context switch가 발생하여 프로세스 B에게 CPU가 넘어갔다고 하자.

 

이때 프로세스 B도 flag를 true로 바꿨는데, 문제는 while(flag[A])를 확인하는 시점에는 A가 깃발을 들고 있는 상황이다.

따라서 무한 대기하게 된다.

 

따라서 2번 알고리즘도, 둘이 동시에 들어가는 상황은 발생하지 않지만, 아무도 못 들어가는 상황이 발생할 수 있다.

 

Algorithm 3 (Peterson's Algorithm)

Combined synchronization variables of algorithm 1 and algorithm 2

 

Process Pi

do {
    flag[i] = true; // 내가 임계 구역에 들어가고 싶다고 알림
    turn = j; // 자신의 다음 차례를 프로세스 j로 바꿔 줌
    while (flag[j] && turn == j); // 상대방이 깃발을 들고 있고, 이번이 상대방 차례라면
    critical section
    flag[i] = false;
    remainder section
} while (1);

 

상대방이 임계 구역에 들어가 있지 않고, 들어갈 준비도 하지 않는다면 내가 들어간다.

 

임계구역에 들어갈려 하는 경우에만 turn을 따져서 나의 turn인 경우에만 들어가고, 그렇지 않고 아무도 들어가 있지 않다면 turn에 관계없이 그냥 들어가면 된다!

 

이 방식은 임계구역 문제를 해결하기 위한 세 조건을 모두 만족하지만, 계속 CPU와 메모리를 쓰면서 기다리기 때문에 busy waiting (spin lock)이 발생한다.

 

쉽게 말해 임계 구역에 들어가려면 상대방이 CPU를 잡고 flag 변수를 false로 바꿔주어야 하는데, 내가 CPU를 잡고 있는 상황에서 의미 없이 while문을 조건을 반복적으로 확인하면서 CPU 할당 시간을 낭비해야 한다.

 

3. 동기화 하드웨어

임계 구역 문제가 발생한 근본적인 이유는 데이터를 읽고 쓰는 동작을 하나의 명령어로 수행할 수 없기 때문이다.

따라서 명령어 하나만으로 데이터를 읽는 작업과 쓰는 작업을 atomic 하게 수행하도록 지원하면 앞선 임계 구역 문제를 간단하게 해결할 수 있다.

 

 

위 그림은 a 변수를 읽은 후, 그 변수를 무조건 1로 설정하도록 명령어가 구성되어 있다.

 

3 - 1) Mutual Exclusion With Test & Set

▶ Synchronization variable

boolean lock = false;

 

▶ Process Pi

do {
    while (Test_and_Set(lock)); // lock의 값을 읽어옴고 동시에 true로 설정한다
    critical section
    lock = false;
    remainder section;
} while (1);

Test_and_Set() 함수는 매개 변수를 읽어내고, 그 변수를 1로 바꿔 주는 역할을 한다.

 

위 예시에서 lock을 읽고 난 뒤 1로 바꿔준다.

만약 처음에 lock의 값이 0이었다면, while문을 탈출하고 lock 값이 1이 된다. 즉 자기가 사용하면 된다.

반대로 lock의 값이 1이면 while문에서 갇히고 lock 값은 그대로 1이 된다.

 

출처

https://steady-coding.tistory.com/537