[운영체제(OS)] 7-1. 프로세스 동기화 (Process Synchronization)

여러개의 process가 동시에 동작할 때, 공유된 데이터에 대해 안전하게 동작하기 위해서 프로세스 동기화가 필요하다. 

 

프로세스가 shared data(공유 데이터)에 concurrent access(동시접근)하면 data가 일치하지 않을 수 있다. 그 예는 밑에 작성하도록 하겠다. 따라서 데이터 일관성(data consistency)을 유지하려면 프로세스가 차례대로 데이터에 접근해 실행을 할 수 있도록 해야한다.

 

Race Condition

: 여러 프로세스가 동시에 공유 데이터에 접근하고 데이터를 수정하고 있는 상황을 말한다.

이렇게 Race Condition이 발생하면 공유 데이터의 최종 값은 마지막으로 공유 데이터에 쓰여지는 값이 된다.

 

Race Condition을 방지하려면 프로세스를 동기화해 한번에 하나의 프로세스만 공유 데이터에 접근하도록 해야한다.

 

예제

CPU가 2개 존재하고 각각의 CPU는 왼쪽과 오른쪽의 명령어를 번갈아 가면서 실행한다고 생각해보자. (아래 그림 참조, X는 메모리에 있다고 생각)

 

1. 1번 CPU는 X에 존재하는 data 10을 읽어온다.
2. 2번 CPU는 X에 존재하는 data 10을 읽어온다. 
3. 1번 CPU는 읽어온 data에 10을 더하여준다. (10 + 10)
4. 2번 CPU는 읽어온 data에 10을 더하여준다. (10 + 10)
5. 1번 CPU가 계산한 값 20을 써준다.
6. 2번 CPU가 계산한 값 20을 써준다.

결과적으로 20이라는 값을 두번 써주게 된것이다. 일반적으로 생각하였을 때 X의 값에 10을 두번 더하면 X+20이 되어야 하는 것이 맞다. 하지만 서로 번갈아 실행하였기 때문에(interleaved execution) 10+10을 두번한 결과가 나오게 되었고 프로세스 동기화가 필요한 이유이다.

출처 : https://www.youtube.com/watch?v=7aF0q7NfwfA

---

Critical Section Problem

n 개의 프로세스들이 공유된 데이터(shared data)에 대해 서로 경쟁적으로 접근하는 상황이 있을 때, 각 프로세스들이 접근 하는 코드를 critical section이라고 부른다. (위의 예제에서는 X가 공유된 데이터이고 X = X + 10이 critical section이 된다)

Probelm

이 critical section의 문제점은 공유된 데이터를 서로 접근해서 사용하면 원하는 값이 나오지 않는다는 것이다. 서로 값을 가져와 연산을 하고 data를 적기 때문이다.

 

Solution

각 프로세스들은 critical section을 수행할때, 프로세스가 자신의 critical section 코드를 수행중이면 다른 프로세스들은 자신들의 critical section 코드를 수행할 수 없도록 만드는 것이 해결책이 된다.

critical section problem을 해결하기 위해서는 다음 조건이 필수적으로 필요하다.

 

- Mutual Exclusion(동시 실행 방지하기)

프로세스 P가 critical section을 실행중이면 다른 프로세스는 critical section을 실행할 수 없다.

- Progress(계속적으로 프로세스가 들어오지 못하도록하는 것을 방지)
현재 critical section을 실행 중인 프로세스가 없고 critical section을 실행하려는 프로세스가 있는 경우라면, 다음에 critical section에 들어갈 프로세스의 선택을 해야한다. 즉 critical section을 실행 중인 프로세스가 없는데 critical section에 들어갈 프로세스들을 막아서는 행위가 있어서는 안된다. 

- Bounded Waiting(과도한 차단 방지)

한 프로세스가 계속 기다려야 하는 경우를 막아야 한다. 어떤 프로세스가 들어가고자 한다면, 기다리는 시간에 대해 bound가 제공되어야 한다. 즉 다른 프로세스에게만 계속 critical section에 들어가도록 양보해서는 안된다는 것이다.

 

---

Critical Section의 형태

Critical Section을 가지고 있는 Process들은 다음과 같은 형태를 띄게 된다.

• Entry section : critical section에 들어가기 전 상태를 확인하는 부분
• Critical section : 공유된 변수를 가지고 연산을 수행 부분
• Exit section : critical section을 끝내고 다른 프로세스에게 끝났다고 알려주는 영역

출처 : https://www.geeksforgeeks.org/introduction-of-process-synchronization/

---

Critical Section Problem을 해결하기 위한 Algorithm 1

 

알고리즘을 살펴보기 위해서 P0와 P1 프로세스 두가지가 있다고 가정하자.

 

Shared data는 int turn 변수이며 처음 turn 변수는 0의 값으로 초기화 되어있다. 

 

동작 방식

프로세스 P0의 코드는 다음과 같으며 P0입장에서 동작을 서술하겠다.

1. P0 입장에서 turn 변수의 값이 0이면 critical section으로 들어갈 수 있다.
2. 만약 turn 값이 1 이라면 while 문에 계속 걸리게 된다.(주의 할점은 while문은 한줄 while(turn !=0); 이어서 조건에 맞으면 루프를 돈다는 것이다)
3. critical section이 끝나고나면 P1이 들어갈 수 있도록 변수 turn을 1로 바꿔준다.

 

P0의 코드

여기서는 Entry, Exit Section을 다음과 같이 나눌 수 있다. 

 

Entry Section

while(turn !=0);

Exit Section

turn = 1;

 

이 알고리즘은 프로세스 하나만 critical section을 수행하기 때문에 mutual exclusion(상호 배제)을 만족하지만 progress(계속적으로 프로세스가 들어오지 못하도록하는 것을 방지)를 만족하지 않는다.

 

Progress를 만족하지 않는 이유

P0가 do_while문을 끝내고 나면 P1이 들어가야한다.(turn = 1이기 때문에)

만약 P1이 Entry Section을 수행중이 아니라 다른 코드를 수행중에 있다면 P0는 다시 critical section을 수행하고 싶어도 Entry Section에서 루프만 돌고 있는 상황이 된다. 즉 들어가지 못하는 상황이 생기기 때문에 Progress를 만족하지 않는다.

 

위의 알고리즘은 Swap-turn 상황이 발생된다. 한 프로세스가 critical section을 더많이 실행되도록 만들었다면 swap-turn 상황은 비효율적이게 된다.

 

Swap-turn 이란? 

두개의 프로세스들이 자신의 차례에 한번만 실행할 수 있는 것을 말한다.

---

Critical Section Problem을 해결하기 위한 Algorithm 2

프로세스는 n개 있다고 가정하고 Shared data는 boolean flag[n] 변수이며 flag[0]과 flag[1]은 모두 false로 초기화 되어있다. 

flag[0]의 값이 true 이면 P0는 들어갈 준비가 되었다는 뜻이다.

 

동작 방식

프로세스 Pi(i번째 프로세스)의 코드는 다음과 같으며 Pi 입장에서 동작을 서술하겠다.

1. Pi 프로세스는 critical section에 들어가기 위해서 flag[i]를 true로 설정해 "나는 들어가고싶다" 라고 알려준다.
2.  j 번째 프로세스(Pj)가 critical section에 들어가려고 했다면, flag[j]가 true일 것이다. 따라서 while 문에서 조건인 flag[j]가 true이면 무한루프를 돌게된다. 즉 프로세스 Pi는 j번째 프로세스에게 양보한다.
3. j번째 프로세스가 critical section에 들어가려고 하지않으면(flag[j]가 false) 그때야 프로세스 Pi가  critical section에 들어가 수행한다.
4. critical section을 모두 수행한 후에 자신의 flag를 false로 바꾸고 나온다.

Entry Section

flag[i] = true;
while(flag[j]);

Exit Section

flag[i] = false;

 

mutual exclusion을 만족하고 swap-turn도 발생하지 않는다. 하지만 progress를 만족시키지 않는다. 

 

Progress를 만족하지 않는 이유

만약 flag[i]와 flag[j] 모두 true라면 while문에서 서로 양보하게 된다. 따라서 critical section을 실행 중인 프로세스가 없는데 critical section에 들어갈 프로세스들을 막아서는 행위가 있기 때문에 progress를 만족하지 않는다.

---

Critical Section Problem을 해결하기 위한 Algorithm 3

 

위에서 배운 algorithm 1과 2를 결합해서 만든 것으로 Pterson's algorithm이라고 불린다.

 

프로세스는 n개 있다고 가정하고 Shared data는 boolean flag[n] 변수이며 flag[0]과 flag[1]은 모두 false로 초기화 되어있다. 또한 int turn 변수도 있으며 처음 turn 변수는 0의 값으로 초기화 되어있다. 

flag[0]의 값이 true 이면 P0는 들어갈 준비가 되었다는 뜻이고 turn 값이 0이면  프로세스 P0가 들어갈 수 있다.

 

동작 방식

프로세스 Pi(i번째 프로세스)의 코드는 다음과 같으며 Pi 입장에서 동작을 서술하겠다.

1. Pi 프로세스는 critical section에 들어가기 위해서 flag[i]를 true로 설정해 "나는 들어가고싶다" 라고 알려준다.
2. turn 변수의 값은 j로 설정해 프로세스 Pj에게 먼저 critical section에 들어가도록 양보를 한다.
3. 만약 프로세스 Pj가 critical section에 들어가려고 하며(flag[j]가 true) Pj 차례이면(turn값이 j) 프로세스 Pi는 while문에서 루프를 돈다. 하지만 둘 중 하나라도 만족하지 않는다면 프로세스 Pi는 critical section에 들어가 코드를 수행한다.
4. critical section을 모두 수행한 후에 자신의 flag를 false로 바꾸고 나온다.

 

Entry Section

flag[i] = true;
turn = j;
while(flag[j] and turn ==j);

Exit Section

flag[i] = false;

 

이 알고리즘은 Mutual Exclusion, Progress, Bounded Waiting을 모두 만족하면서 critical section problem을 해결하는 알고리즘이 된다.

 

하지만 while문의 조건을 CPU가 계속 체크해줘야하기 때문에 CPU는 다른일을 하지 못한다. 즉 Busy Waiting이 발생한다.

 

다음 글에서는 Lock을 이용해서 critical section에 Problem을 해결하는 방법을 이어서 작성하도록 하겠다.