- 공유데이터를 접근하는 코드가 크리티컬 섹션이다. 크리티컬 섹션의 동시접근을 막아야 하므로 엔트리 섹션을 넣어 lock을 걸어야 한다. 크리티컬 섹션이 끝나면 lock을 풀어 다른 프로세스가 크리티컬에 들어갈 수 있도록 해야한다.
- 크리티컬 섹션 문제를 풀기 위해 만족시켜야 하는 조건이 세 가지 있다.
- 먼저 mutual exclution(상호 배제)으로 한 프로세스가 크리티컬 섹션을 수행 중이면 다른 프로세스가 스스로의 크리티컬 섹션에 들어가면 안된다. 배타적 개념
- 다음은 progress(진행)로 아무로 크리티컬 섹션에 없을 때 크리티컬 섹션에 들어가려는 프로세스가 있으면 들어가게 해주어야 한다.
- 마지막을 bounded waiting 으로 프로세스가 크리티컬 섹션에 들어가려고 요청하면 그 요청이 허용될 때 까지 다른 프로세스가 크리티컬 섹션에 들어가는 횟수에 한계가 있어야 한다. 즉 기다리는 시간이 유한해야 한다는 것이다. 특정 프로세스 입장에서 크리티컬 섹션을 못 들어가고 지나치게 오래 기다리는 기아 문제를 해결하기 위한 것이다. 가령 프로세스가 셋인데 두 개의 프로세스만 계속 들어가면 나머지 하나는 기아 문제가 생기므로 크리티컬 섹션에 들어가는 횟수를 제한하여 남은 프로세스도 크리티컬로 들어갈 수 있게 하는 것이다.
- 어떻게 소프트웨어적으로 lock을 거는 알고리즘이 있는지를 알아보도록 하겠다.
- 프로세스 P0과 P1이 있는데, P0이 크리티컬 섹션을 들어가기 전에 while문을 돌며 turn이 몇 번인지 확인한다. turn이 0이면 P0의 차례라는 뜻이다. 0번 프로세스가 시작할때 자기 차례가 아니면(turn이 0이 아니면) 자기 차례를 계속 기다리는 것이다. 그러다 turn이 0이 되면 그때 크리티컬 섹션으로 들어간다. 그러고 크리티컬에서 나오면 turn을 1로 바꿔 상대방의 차례로 넘겨주는 것이다.
- 즉 본인 차례가 아닐때 while문에서 기다리고 본인 차례에 크리티컬에 들어가고, 크리티컬을 나오면 상대 차례로 넘겨주는 메커니즘이다.
- 이 코드는 mutual exclusion(상호 배제)를 만족하지만, 아무도 크리티컬 섹션에 없을 때 크리티컬 섹션에 들어가지 못하는 progess를 지키지 못하는 문제가 있다. 반드시 교대로 들어가도록 설계했기 때문이다.
- 따라서 progress 문제의 해결을 위해 다음과 같은 알고리즘이 도출되었다.
- 프로세스 두 개가 각각 자신의 플래그를 가진 형태다. 플래그는 본인이 크리티컬로 들어가고자 한다는 의중을 표시하는 것이다. 이는 True False 형태다. 본인이 들어가고자 할 때 플래그를 True로 바꾸고 상대방 플래그를 확인한다. 상대방이 True면 기다리고 False면 들어간다.
- 그러나 모두 True 상태일 때 서로 끊임없이 양보하면서 아무도 크리티컬로 들어가지 못하는 상황이 생길 수 있다.
- 따라서 다음과 같은 알고리즘이 도출되었다.
- turn과 플래그를 모두 사용하는 알고리즘이다. 프로세스가 섹션으로 들어가고자 할때 플래그를 true로 세팅하고, turn을 상대방 turn으로 바꾼다. 이제 상대방이 플래그가 true 상태고, turn이 상대방 차례임을 만족하면 양보를 한다. 상대방이 false 상태이거나, 상대방이 true 상태여도 나의 turn인 경우에 자신이 크리티컬로 가면 된다.
- 그러나 이 코드는 내가 cpu를 잡고 다른 프로세스가 크리티컬을 들어간 동안 계속 while문을 돌며 lock을 거는 방법이므로 계속 cpu와 메모리를 사용하는, Busy waiting 방식이라 효율성이 떨어지게 된다.
- 하나의 instruction에 데이터를 쓰고&데이터를 읽는 작업을 동시에 처리하도록 하면, 데이터를 쓰는 동안에 인터럽트가 들어와 cpu를 뺏기고 혼선이 발생하는 경우를 하드웨어적으로 미연에 차단할 수 있다. 이를 Synchronization Hardware이라 하는데, 관련된 대표적인 지시 방법으로 Test_and_set이 있다. A라는 데이터의 값을 읽어내고 A의 값을 바꾸는 두 작업을 하나의 instruction으로 처리하는 것이다.
- 따라서 Test and set을 이용해 1)크리티컬 섹션에 들어가기 전에 이미 누가 lock을 걸었는지 체크하고, 2)안 걸려있다면 lock을 1로 걸고 크리티컬로 들어가는 이 두 가지 작업을 한번에 처리한다. 이 모든 작업을 위의 Test_and_Set(lock)메소드로 수행한다. 크리티컬 섹션을 나오면 lock을 false로 셋팅한다. Test_and_Set(lock)이 1이면(이미 락이 걸려 있으면) while문을 계속 돌고 0이 되면 반복문을 빠져나와 자신인 lock을 걸고 크리티컬 섹션으로 들어간다.
하마드