인강 6) 프로세스 동기화(1)

강의 url www.kocw.net/home/search/kemView.do?kemId=1226304

1) 동기화의 문제에 대해 알아본다.
2) 동기화 문제의 해결 방법에 대해 알아본다.

데이터 접근과 Race Condition

- 프로그램은 CPU에서 연산을 수행하고, Memory에 data를 기록한다. CPU를 Execution Box, 메모리를 Storage Box 라고 하자. Execution Box-Storage Box의 구도는 CPU-Memory 외에도 컴퓨터내부-디스크, 프로세스-그 프로세스의 주소 공간도 예가 될 수 있다. 
- 문제는 데이터를 한 프로세스에서 읽는 구조가 아닌, 여러 프로세스에서 읽는 구조가 되면 Race Condition이 발생할 수 있다.

위 사진 예에서, 각각의 E-box가 수행하여 Storage-Box에 저장될 기대하는 결과 값이 원래의 값일 수 있다. 그러나  좌측의 E-box가 먼저 값을 가져가 연산하는 도중에 우측의 E-box도 값을 가져가 연산한다음, 순서에 상관없이 다시 S-box에 넣는다고 하자. 그러면 원래의 값에서 1의 오차가 있는 결과값이 될것이다.(+-1) 이러한 상황을 Race Condition이라고 한다.

OS Level에서 Race Condition이 발생한 경우

- Race Condition 은 두 프로세스가 시스템 콜을 통해 kernel 모드에 진입하였을 때에도 같은 현상이 벌어질 수 있다. 임의의 A 프로세스가 커널 모드에서 운영체제의 리소스(메모리 영역 또는 레지스터)를 읽어 왔고 커널 모드에서 더 진행할 사항이 남았을 때, CPU 스케쥴러에 의해 (타이머 인터럽트) CPU를 B 프로세스에게 선점 당한다음 같은 리소스를 프로세스 B가 사용한뒤 A 프로세스가 돌려받아 나머지 진행사항을 수행하는 경우를 생각해보자. 그러면 CPU는 레지스터를 A 프로세스의 레지스터로 업데이트한 뒤 연산을 수행하는데, A 프로세스가 CPU를 선점당할 때의 레지스터이므로, 그 후 시간대에 같은 Storage 영역을 프로세스 B가 수정한 상황은 포함되고 있지 않다. OS는 이런 상황을 방지하기 위해 커널 모드에서 수행 중일 때는 CPU를 preempt하지 않는다.

- 이 외에도 커널의 공유 변수를 건드리는 중에 CPU로 인터럽트가 들어왔을 때의 경우 또는 멀티프로세서에 의해 같은 메모리 영역을 쓰는 경우가 OS 레벨에서의 Race Condition이 발생한 경우이다. 전자의 경우는 커널의 공유 변수를 건드리는 중에 CPU로 인터럽트를 disable한다음 건드리는 작업이 끝난 경우 인터럽ㅌ르를 enable 하는 방식으로 해결할 수 있다. 후자의 경우 동시간대에는 단 하나의 프로세서만 운영체제를 활용할 수 있도록 제한할 수 있다. 또는 양자의 경우 소프트웨어적으로 Lock 을 지원하여 하나의 주체가 동작 중일 땐 다른 주체가 접근하지 못한도록 제한 할 수 있도록 한다.

Process Synchronization - Critical Section 문제

- 이론적인 설명으로 돌아와서, 프로세스가 공유 데이터에 접근할 때 Race Condition 문제가 발생할 수 있다. 각 프로세스가 공유 데이터를 접근하는 코드를 Critical Section 이라고 한다. 하나의 프로세스가 Critical Section에 있을 때 다른 모든 프로세스가 Critical Section에 접근하지 못하도록 막아야한다. 하나의 프로세스가 Critical Section 에 진입하여 동작을 수행하고 있다면, 설령 그 때에 다른 프로세스에거 CPU를 선점당해, 선점한 해당 프로세스가 Critical Section에 진입 시도할 때에 진입하지 못하게 한다.
- Critical Section 문제를 해소하기 위해 세가지 기준이 지켜져야한다. 상호 배제 Mutual Exclusion, 진행 Progress, 유한 대기 Bounded Waiting
상호 배제 Mutual Exclusion : 임의의 프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section 에 들어가면 안된다.
진행 Progress : 어느 프로세스도  Critical Section에 진입하지 않은경우, 임의의 프로세스가 Critical Section에 들어가려 할 때 들어갈 수 있어야한다.
유한 대기 Bounded Waiting : 임의의 프로세스가 Critical Section에 진입하려 대기 중일 때, 다른 프로세스들에게 적당한 양보(대기) 후에라도 들어갈 수 있어야한다.

Critical Section Algorithm - 소프트웨어적인 해결방법

mutual exclusion을 만족하지만, progress를 만족하지 않음

- 해당 알고리즘은 두 프로세스 P_0, P_1가 critical section에 진입할 때 유효하다. P_0, P_1 프로세스는 동기화 변수 turn의 값을 참조하여 본인의 값인 경우 Critical Section에 진입한다. 그 후 Critical Section에서 나올 때는 동기화 변수 turn을 P_0는 1로, P_1은 0으로 바꿔주며 상대방이 Critical Section에 들어갈 수 있도록한다. 진행의 관점에서는 위 알고리즘이 만족스럽지 못 하다. P_0 프로세스가 반드시 동기화 변수 turn을 P_1 프로세스의 값으로 바꾸어준 경우에만 P_1이 Critical Section에 진입할 수 있다. 그리고 P_1이 P_0보다 더 빈번히 Critical Section에 진입하고자 할 때도 위 알고리즘으로는 만족하지 못 한다.

- 해당 알고리즘은 더 위험한 상황이 발생할 수 있다. P_0이 flag를 true로 set 한 다음 타인의 flag를 확인하는 과정에서 Context Switch가 발생하여 P_1도 flag를 true로 set 한다음 타인의 flag를 확인 하는 과정에 들어가는데 이 과정에서 계속 critical section에 들어가지 못한다. 

위 두 알고리즘에서 사용하는 변수를 모두 이용하여 Critical Section 문제를 해결할 수 있는 완성적인 알고리즘을 도출해낼 수 있는데, Peterson's Algorithm이라 불린다.

- 위 알고리즘은 어느 순간에서도 Context Switch가 발생하여도 Critical Section 해결조건인 세 가지 조건을 모두 만족한다. 증명은 코드의 1, 2번 줄은 어떠한 순서로 P_0, P_1간 Context Switch가 발생하여도 상관이 없다. while문에서는 상대방이 flag 가 true로 설정되어있고, 상대방의 turn일 때는 무조건 양보한다. 그러나 상대방이 flag가 false로 되어있거나 내가 상대방에게 양보한 상태가 아니라면 무조건 critical section에 들어갈 수 있는 것이다. 만약 상대방 프로세스가 critical section에 들어갈 의향이 없거나, 들어갈 의향이 있더라도 나에게 양보를 하였다면 내 프로세스가 Critical Section에 성공적으로 진입할 수 있다.
- P_0가 Cirtical Section에 들어가지 못 할 때, 해당 P_0은 while 문에서 CPU 연산량을 소모하는 Busy Waiting 현상이 발생한다.

Critical Section - Synchronization Hardware

-code가 instruction으로 변경될 때 Critical Section이 발생할 수 있는 부분을 하드웨어적으로 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결할 수 있다.  

- 위의 동기화 변수 lock을 읽고 값을 쓰는데에, atmoic하게 동작할 수 있도록 하드웨어적으로 지원한다. lock 변수 값을 읽고 쓰는 것을 쪼개질 수 없는 instruction으로 제공하면 쉽게 해결이 된다.

Semaphore

- 세마포어는 동기화 문제를 해결하기 위한 추상적인 자료형이다. 구체적으로 동기화 문제를 어떻게 해결하겠다를 제시하는 것이 아닌, 프로그래밍에서 추상 클래스를 정의하듯 Semaphore란 개체가 존재하며, 특정 작업을 수행할 P(S), V(S)란 작업이 존재한다로 정의 내린다. 개발자는 이 Semaphore 자료형을 참조하여, Critical Section 문제를 어떻게 해소하는지에 대해 설명할 수 있다. 
- Semaphore는 자원의 수를 세는 integer variable S 을 가지고 있고, 자원의 수를 획득하는 P(S), 자원의 수를 반환하는 V(S)라는 atomic 한 작업을 제공한다. 어떻게 획득하고, 어떻게 반환할 것인지에 정확히 논의하는 것이 아닌, 이러한 역할이 필요하다는 추상적인 개념이다. 
- Mutual Exclusion을 제공하기 위해선 integer variable S는 1이면 된다.

Block and Wakeup Implementation 

- 임의의 프로세스에서 Semaphore가 P(S)를 수행할 때, 만약 획득할 수 없다면, 임의의 프로세스가 CPU 연산량을 소모하며 busy waiting으로 기다리게 하지 않고, 해당 프로세스를 Suspend를 하고, 세마포어 자료형이 제공해주는 PCB queue에 해당 프로세스를 줄세운다. 이 작업을 block 이라고 한다.
- 만약 또 다른 임의의 프로세스에서 Semaphore V(S) 작업을 수행하면, wakeup(P)를 수행하여 PCB queue에 위치한 프로세스 P를 wake up 시켜 ready queue로 대기시킨다.

이 때 S.value는 현재 여분의 개수를 세는 앞의 다른 알고리즘의 것과는 다르다.

세마포어는 자원의 개수에 따라 두가지 형식으로 나눌 수 있다. 1개 또는 다수이냐에 따라 사용 용도가 달라질 수 있다.

Deadlock and Starvation

세마포어에서 둘 이상의 프로세스가 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상이 발생할 수 있다. 이를 Deadlock 이라고 한다. 

S, Q를 Semaphore라고 하자. Process A가 S를, Process B가 Q를 획득하였을 때, A는 세마포어 Q를, B는 세마포어 S를 무한히 기다리는 상태에 빠지게된다. 어느 하나 획득한 세마포어에 대해 Release하지 못하므로, 무한히 기다리게 되며 이 상태를 Deadlock이라고 한다. 해소하는 방법으로는, 세마포어를 획득하는 방식을 각각 P(S), P(Q)로 동일한 순서로 세마포어를 요청하게 하면 deadlock을 해소할 수 있다. 이 방법은 프로그래머가 유의하여 개발하면 해결할 수 있다.

Starvation은, 프로세스가 세마포어 queue에서 대기하는 상태이다. 위의 deadlock 경우도 각각의 프로세스가 교차된 프로세스에 대해 세모파어 queue에 무한히 대기하므로 Starvation의 일종이라고 볼 수도 있다. 하지만 이 경우는, 특정 프로세스들만 자원을 자기들끼리만 공유하며 다른 프로세스는 영원히 세마포어 큐에서 대기 하는 문제를 뜻한다. Starvation을 잘 보여주는, 유명한 문제로는 철학자의 식탁문제가 있다.

한 철학자는 양 식기를 이용해서 식사를 할 수 있다고 하자. 가장 아래-중앙에 위치한 철학자는 양 쪽의 철학자가 식기를 사용하고 내려놓고 다시 집어감으로 인해 의도치않게 굶겨질 수 있다.

 또한 deadlock도 발생가능하다. 모든 철학자가 동시에 왼쪽 식기를 집어감으로 인해서 모두 다 오른쪽 식기를 기다리며 모두 다 굶어 죽을 수 있다.

Deadlock and Starvation 관련한 내용은 다음 포스트 내용에 더 자세히 나옵니다.