- Race condition : 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
공유 데이터와 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다. 데이터의 최종 연산 결과는 마지막에 데이터를 다룬 프로세스에 따라 달라지는데, 일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요하다.
Race condition을 막기 위해서 concurrent process는 동기화되어야 한다.
사용자 프로세스 P1 수행 중 timer interrupt가 발생해서 context switch가 일어나서 Process2가 CPU를 잡으면..?
● Critical Section (임계 영역)
공유 데이터인 X에 Process 1도 접근하려 하고 있고 Process 2도 접근하려고 하는 상황에서 공유 데이터를 접근하는 코드가 Critical Section이다. Process 1이 Critical section에 있을 때, 다른 프로세스에게 CPU 제어권을 뺏기더라도 공유 데이터에 접근하는 Critical Section에 들어가지 못하게 한다.
- Critical section : 공유 데이터를 접근하는 코드
n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우, 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드만 critical-section이 존재
★ 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.
● Initial Attempts to Solve Probelm
어떤 프로세스든 간에 공유 데이터를 접근하거나 접근하지 않거나 하는 코드로 반복되면서 구성이 될 것이다.
공유 데이터의 동시 접근 하는 것을 막기 위해 Entry Section을 넣어서 Lock을 건다. 여러 프로세스가 Critical section에 들어가는 걸 막고 접근이 끝난 후에 Lock을 풀어서 다른 프로세스가 접근할 수 있게 한다.
● 프로그램적 해결법의 충족 조건
Race Condition을 막기 위한 세 가지 조건이 있다.
1. 상호 배제 (Mutual Exclusion)
배타적으로 접근해야 한다. 어떤 프로세스가 Critical Section 영역을 수행 중이면 다른 모든 프로세스들은 그 Critical Section에 들어가지 못하게 하는 것이다.
2. 진행 (Progress)
Critical Section에 들어간 프로세스가 있지 않은 상태에서 Critical Section에 들어가려는 프로세스가 있으면 들어가게 해주어야 한다. 즉, Critical Section에 있는 프로세스 외에는 다른 프로세스가 Critical Section에 진입하는 것을 방해하면 안 된다.
3. 유한 대기 (Bounded Waiting)
기다리는 시간이 유한해야 한다. 특정 프로세스 입장에서 Critical Section에 못 들어가고 지나치게 오래 기다리는 starvation이 발생하면 안 된다. 프로세스가 Critical section에 들어가려고 요청한 후부터 다른 프로세스들이 Critical section에 들어가는 횟수에 한계가 있어야 한다. 즉, Critical section에 한 번 들어갔다 나온 프로세스는 다음에 들어갈 때 제한을 준다.
Ex) 세 개의 프로세스가 있을 때 두 개의 프로세스만 번갈아가며 Critical section에 들어가는 것은 유한 대기 조건을 만족하지 못한 것이다.
● Lock을 어떻게 구현해야 하는가?
- 소프트웨어 알고리즘
- 더 이상 쪼개지지 않는 하드웨어 명령어로 구현
- 인터럽트를 disable하고 enable하는 방법
지금 현재, 소프트웨어에 의한 해결책은 느리기 때문에 현재 운영체제들이 사용하고 있지 않다.
[ 소프트웨어 알고리즘 ① ]
turn 변수가 0이 아닐 때 while문을 계속 돌면서 본인의 차례를 기다린다. turn 변수가 0이 되면 Critical Section에 들어가고, 들어갔다 나오면 trun을 1로 변경시킨다. turn의 변수값을 1에서 0으로 변경시키는 것은 Process P1이 해준다.
위의 코드에서는 상호 배제 조건은 만족한다. 본인의 차례에만 Critical section에 들어가기 때문에 Process 두 개가 동시에 Critical section에 들어갈 일이 없다. 가장 중요한 문제점은 아무도 critical section에 없는데도 불구하고 아무도 못 들어갈 수 있는 경우가 생긴다. (Progress 조건이 충족하지 않는다.)
코드를 보면 Critical section은 반드시 교대로 들어가도록 되어있다. Process 0이 한 번 Critical section에 들어갔다 나와야지만 turn 변수가 1로 변경이 되어 Process 1이 들어갈 수 있게 된다. 즉, 어떠한 프로세스가 들어왔다 나가야지만 trun이 넘어가는 것이다. 이러한 상황에서 프로세스들이 Critical section에 들어가고자 하는 빈도가 균일하지 않을 수 있다. 프로세스 0번은 더 빈번하게 들어가고 싶은데 프로세스 1번이 꼭 들어갔다가 나와야지만 프로세스 0번의 차례가 될 수 있다. 프로세스 0번은 자주 들어가고 싶고 프로세스 1번은 한 번만 들어가고 싶은 경우에 프로세스 1번이 turn을 바꿔주지 않으면 프로세스 0번은 영원히 못 들어간다.
→ Progress 조건이 맞지 않는다. 다른 방법을 알아보자.
[ 소프트웨어 알고리즘 ② ]
flag라는 변수를 프로세스 두 개가 각각 자신의 flag를 갖고 있다. Critical section에 들어가려고 할 때 본인의 flag를 true로 만들어 줌으로써 Critical section에 들어가고자 하는 의사 표시를 한다. 그 후, Critical secion에 들어가기 전에 상대방 flag를 체크한다. 상대방이 flag를 true로 세팅해놨으면 기다리고, 상대방 flag가 false면 본인이 Critical section에 들어갈 수 있다. Critical section에 들어갔다가 나올 때 본인의 flag를 다시 false로 변경시켜 준다.
여기서 한 가지 문제가 생길 수 있다. 프로세스 i가 flag를 true로 해 놓은 상태에서 CPU 제어권을 빼앗기면 CPU 제어권이 프로세스 j로 넘어간다. 그때 프로세스 j가 본인의 flag를 true로 바꿔놓고 다른 프로세스의 flag가 true인지 확인하는데 프로세스 i의 flag가 true이기 때문에 Critical section에 들어가지 못하고 while문만 반복하다가 CPU 제어권을 프로세스 i에게 빼앗긴다. 똑같이 프로세스 i도 flag를 확인할 때, 프로세스 j의 flag가 true이기 때문에 똑같이 while문만 반복하다 CPU 제어권을 빼앗길 것이다. 결국 아무도 Critical section에 들어가지 못하는 경우가 생긴다.
[ 소프트웨어 알고리즘 ③ (피터슨 알고리즘) : turn과 flag 변수를 모두 사용 (알고리즘 1과 2의 혼합) ]
내가 Critical section에 들어가고 싶다고 알리기 위해 flag를 trun로 변경시켜주고 자신의 다음 차례를 프로세스 j로 변경시켜 준다. 그 후, i번째 프로세스가 Critical seciton에 들어가기 전에 먼저 쓰고 싶어 했던 프로세스가 있는지 확인하고 수행시켜 준다.
예를 들어, 프로세스 j가 Critical section에 접근하고 싶어 했으면(flag [j]가 true) 프로세스 i는 프로세스 j에게 차례를 양보한다. 현재 내 차례가 아니고 프로세스 j가 자원까지 쓰고 싶어 하는 상태이면 나는 spinlock에 머무르다가 turn이 내 차례이거나 프로세스 j가 자원을 쓰고 싶지 않은 경우에 프로세스 i는 spinlock을 빠져나와 Critical section에 진입할 수 있다. turn과 flag를 통해 동시 접근을 막는다. 마지막으로 자원을 다 사용했으면 flagfmf 다시 false로 변경시켜 준다.
프로세스 두 개가 동시에 들어가 있지 않으면서 아무도 들어가 있지 않을 때에는 들어갈 수 있게 해 준다. 특정 프로세스만 지나치게 오래 기다려야 하는 문제도 발생하지 않는다. 이 알고리즘은 Race Condition을 막기 위한 세 가지 조건을 모두 만족하는 코드이다. 하지만 busy waiting (spinlock)의 문제가 있다.
만약 어떤 프로세스가 이미 Critical section에 들어가 있는 상태에서 다른 프로세스가 CPU를 잡으면 While문을 빠져나가지 못하고 계속 돌다가 CPU를 반납하게 되어 비효율적이다.
● Mutual Exclusion with Test & Set
고급 언어의 문장 한 줄이 실행되기 위해서 여러 개의 instruction으로 구성되어 있다. Instruction 중간중간 코드를 빼앗길 수도 있다는 말이다. 그러다 보니 S/W적으로 복잡하게 구현이 된다. 하드웨어적으로 하나의 Instruction만 주어진다면 Critical section 문제는 쉽게 해결된다. 하드웨어적으로 고유의 Instruction이 지원되는 경우가 많은데, 그중에서 Test_and_Set()이라는 Instruction이 있다. 하드웨어적으로 Test & Modify를 Atomic 하게 수행할 수 있도록 지원하는 경우에는 앞의 문제를 간단하게 구현할 수 있다.
Test_and_set(a)는 a라는 데이터의 현재값을 읽어내고 a의 값을 바꾸는걸 하나의 Instruction으로 처리한다. 만약 a가 0이었다고 한다면 Test_and_set()을 하고 난 후 a의 값은 1로 바뀌게 된다. 무조건 1로 쓴다는 것이다.
Test_and_Set()을 사용해 어떻게 구현하는지 알아보자.
Lock의 초기 값은 false이고 Critical section에 들어가기 전에 Lock을 걸고 들어간다. Lock이 걸려있는지 체크한 후, Lock이 걸려있지 않으면 내가 Lock을 걸고 Critical section에 들어간다. 만약 Lock이 false였다고 하면 아무도 Critical section에 들어가 있지 않은 것이며, 내가 Lock을 걸고 들어가면 된다.
Test_and_Set()에서 읽어낸 값이 0이라면 while문의 결과 값이 0이 되니까 Critical section에 바로 들어가게 된다. 그렇지만 Test_and_Set()을 했기 때문에 Lock을 1로 바꾼 다음에 Critical section에 들어갔을 것이다. 즉, Lock이 0일 경우에는 Lock을 걸고 들어가는 작업이 atomic 하게 실행된 것이고, Lock이 1일 경우에는 Test_and_Set()을 했을 때 Lock이 1이기 때문에 while문을 계속 돌게 되는데 어차피 원래 얘는 1이라 상관이 없다.
