1. Critical Section(임계 영역)
프로세스 동기화 문제를 해결하는 방법에 대해 알아보기 전에, 먼저 알아야할 용어가 있습니다. Critical Section(임계 영역)에 대한 것입니다.
사진을 통해 설명드리자면, 공유 데이터인 X에 프로세스 P1과 P2가 거의 동시에 접근하는 상황에서 공유 데이터를 접근하는 코드가 Critical Section 입니다. 만약 프로세스 1이 Critical Section에 있을 때, 다른 프로세스에게 CPU 제어권을 빼앗기더라도 공유 데이터에 접근하는 Critical Section은 막아두어야 합니다. 프로세스 1이 Critical Section에 빠져나왔을 때 프로세스 2가 Critical Section에 접근할 수 있습니다.
즉, Critical Section은 공유 데이터에 접근하는 코드로, 하나의 프로세스가 Critical Section에 있을 때 다른 모든 프로세스는 Critical Section에 들어갈 수 없습니다.
2. Initial Attempts to Solve Problem
소프트웨어적으로 문제를 해결하기 위한 초기 아이디어는 아래와 같을 수 있습니다.
어떤 프로세스든 간에 공유 데이터를 접근하는 코드와 아닌 코드로 반복되며 구성이 될 것입니다.
위 코드처럼 공유 데이터에 접근하는 것을 막기 위해 entry section에서 Lock를 걸어줍니다. 이후 다른 프로세스들이 Critical Section에 들어가는 것을 막고, 공유 데이터에 접근이 끝나면 exit section에서 Lock을 풀어 다른 프로세스가 접근할 수 있게 해줍니다.
이렇게 소프트웨어적인 방법으로 코드를 넣어 해결하는 방식을 이번 포스팅에서 다루어 볼 것입니다.
3. 프로그램적 해결법의 충족 조건
우선 Critical section 문제를 풀기 위해 만족해야할 조건이 무엇이 있는지 정리해보겠습니다. 크게 세 가지가 있습니다.
1. Mutual Exclusion (상호 배제)
배타적으로 접근해야한다는 의미입니다. 한 프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스는 그 critical section에 들어가서는 안됩니다.
2. Progress (진행)
누구도 critical section에 있지 않은 상태에서 critical section에 들어가고자하는 프로세스가 있다면 critical section에 들어갈 수 있게 해주는 것입니다.
3. Bounded Waiting (유한 대기)
프로세스가 critical section에 들어가기 위해 기다리는 시간이 유한해야한다는 것입니다. 특정 프로세스가 critical section에 들어갈려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 제한이 있어야 합니다.
4. 소프트웨어 알고리즘
(1) Algorithm 1
우선 사진의 Synchronization variable은 프로세스들이 수행의 동기화를 위해 공유하는 변수입니다.
turn 값이 0으로 초기화되어 있습니다. 여기서 turn에 해당하는 숫자의 프로세스가 Critical section에 들어갈 수 있습니다.
그래서 처음에는 프로세스 P0이 실행이 되고 Critical section에서 빠져나오면서 turn을 바꾸어 다른 프로세스가 들어갈 수 있게 하는 것입니다.
그러나 이 알고리즘은 프로그램적 해결법의 충족 조건 중 Mutual Exclusion은 만족하지만, Progress 는 만족하지 못합니다. 즉, 아무도 Critical section에 없어도 순서를 기다려야하는 문제가 생깁니다.
또 코드를 보면 교대로 들어가도록 코드가 짜여져 있기 때문에, 만약 프로세스 P1이 실행되고자 한다면 프로세스 P0이 한번 Critical section에 들어갔다가 나와야지만 프로세스 P1이 들어갈 수 있습니다.
이런 문제로 Progress 조건을 만족하지 못하기 때문에, 다른 알고리즘을 사용해야합니다.
(2) Algorithm 2
두 번째 방법은 동기화 변수로 flag를 사용하는 방식입니다. flag는 프로세스가 Critical section에 들어가고 싶다는 의중을 표현하는 것으로 볼 수 있습니다.
우선 모든 flag는 false값으로 초기화하여 Critical section에 아무도 없게 초기화를 시킵니다. Critical section에 들어가고자 할 때는 본인의 flag를 true로 만들어 Critical section에 들어가고자 하는 의사를 표시합니다. 그리고 Critical section에 들어가기전 상대방의 flag를 체크합니다. 상대방이 flag를 true로 바꾸었다면 기다리고, 상대방이 false라면 이제 Critical section에 들어갈 수 있습니다. Critical section에서 나올 때는 flag를 다시 false로 바꾸어줍니다.
이 소프트웨어 방식의 문제는 프로세스 i가 flag를 true로 변경한 상태에서 CPU 제어권을 빼앗겨 CPU 제어권이 프로세스 j에게 넘어가는 상황일 때 입니다. 프로세스 j가 Critical section에 들어갈려는데 i가 계속해서 flag가 true인 상태기 때문에 무한 while문을 반복하다가 다시 프로세스 i에게 CPU를 빼앗기는 것입니다. 결국 아무도 Critical section에 들어가지 못하는 상황이 생기는 것입니다.
(3) Algorithm 3 (피터슨 알고리즘)
위의 알고리즘 1과 2의 방식을 모두 합친 것입니다.
프로세스 i가 Critical section에 들어가고 싶다고 알리기 위해 자신의 flag를 true로 변경합니다. 그리고 자신의 다음 차례를 프로세스 j로 바꾸어줍니다. 이후 프로세스 i가 Critical section에 들어가기 전에 먼저 flag를 true 로 바꾼 프로세스가 있는지 확인하고 Critical section에 입장합니다.
이 방법은 프로세스 2개가 동시에 들어가있으면서 아무도 들어가 있지 않을 때에는 들어갈 수 있게 해주는, 해결법의 모든 조건을 충족하는 코드입니다.
하지만 문제도 있는데, 만약 어떤 프로세스가 이미 Critical Section에 들어가 있는 상태에서 다른 프로세스가 CPU를 잡으면 while문을 계속해서 돌다가 CPU를 반납하게 된다는 문제가 있습니다. 이 문제를 Busy waiting 또는 Spin Lock이라고 부르며, CPU와 메모리를 계속해서 쓰면서 기다리는 것을 의미합니다.
5. Synchronization Hardware
지금까지 소프트웨어적인 해결법을 알아보았는데 하드웨어적으로 하나의 인스트럭션만 주어지면 Critical Section 문제는 쉽게 해결됩니다. 하드웨어적으로 고유의 인스트럭션이 지원되는 경우가 많은데, 그중 하나가 바로 Test and set입니다.
위에서 언급한 문제가 생기는 이유는 데이터를 읽고 쓰는 것을 하나의 인스트럭션에서 실행을 못하기 때문에 생기는 것입니다. 만약 이 두 가지의 동작이 하나의 인스트럭션에서 수행이 가능하다면 매우 간단하게 Lock에 대한 문제점을 해결할 수 있습니다
Mutal Exclusion with Test & Set (Test & Set 을 통한 상호간 배제)
test & set을 통한 해결법에 대해 알아보겠습니다.
동기화 변수인 lock은 초기값을 false로 세팅합니다. Critical Section에 들어가기 전 Test and Set() 메서드를 호출해 lock의 현재 값을 읽어오고, 만약 읽어온 값이 0(false)라면 해당 프로세스가 Critical Section에 진입하게 됩니다. 이후 Test and Set()은 Lock을 1로 설정하게 됩니다. 이후 Critical Section에서 나오면 Lock을 다시 0(false)로 설정하여 다른 프로세스가 Critical Section에 진입할 수 있게 합니다. 만약 읽어온 값이 1(true)라면 while 루프를 통해 계속 대기하게 됩니다.
Test and Set()은 Lock의 값을 읽어오고 설정하는 두 개의 과정이 인스트럭션에서 atomic하게 수행되기 때문에 while 문을 반복해서 돌아도 Lock은 true로 설정되어있기 때문에 상관이 없습니다.
참고자료
[KOCW 이화여대 반효경 교수님 - Process Synchronization 1]
https://core.ewha.ac.kr/publicview/C0101020140401134252676046?vmode=f
반효경 [운영체제] 11. CPU Scheduling 2 / Process Synchronization 1
설명이 없습니다.
core.ewha.ac.kr
[ Chapter5 Operating System Concepts - Abraham Silberschatz ]
https://www.yes24.com/Product/Goods/89496122
운영체제 - 예스24
운영체제
www.yes24.com
