[운영체제 #08] Synchornization Tools

 

기존의 counter++를 하려면, 메모리에 존재하는 counter 변수 값을 CPU 내 레지스터 R1에 복사해온 다음, R1에서 증가시키고 다시 counter에 넘겨준다. 이처럼 high-level language인 counter++는 low-level language(assembly language)로 3개의 명령어로 쪼개져 실행된다.

 

여기서 문제는 위처럼 프로세스가 동시에 실행됐을 때이다. 명령어 실행 순서가 랜덤하므로 항상 다른 값이 나올 수 있다. 누가 마지막에 counter를 write했느냐에 따라 값이 변경되는데, 이런 상황을 race condition이라고 한다.

 

OS에서도 같은 문제가 발생할 수 있다. 위 그림처럼 두 프로세스가 동시에 fork를 요청하면 생성된 프로세스 pid가 같을 수있다. 이런 race condition을 막기 위해 shared resource를 사용하는 구역에 한 프로세스가 작업하는 동안 다른 프로세스의 접근을 차단하는 로직을 추가하는데, 이 구역을 critical section라 하고 아래 그림과 같다.

Critical section concept

 

critical section 문제를 해결하기 위해선 3가지 요구사항이 존재한다.

• Mutual Exclusion : 프로세스 Pi가 critical section에서 실행중이면 다른 프로세스들은 접근할 수 없다는 요구사항
• Progress : critical section에 프로세스가 없고 entry section에 대기 중인 프로세스가 존재할 때, entry section 내 프로세스들 중 하나를 연기하지 않고 반드시 선택해야 한다는 요구사항
• Bounded Waiting : 프로세스 Pi가 entry section에 들어간 시간과 critical section에 들어갈 시간 사이에 다른 프로세스가 중간에 critical section에 접근할 수도 있는데(새치기),  그럼 Pi는 계속 밀리는 starvation 상태가 되므로 이런 경우가 n번(Bound) 발생하게 되면 반드시 critical section에 접근해야 한다는 요구사항

이런 요구사항을 맞춰 실제로 해결한 여러 solution들이 존재한다.

Solution1 : Peterson's solution

Peterson's solution algorithm

Examples

 

P0과 P1으로 2개 프로세스만 있다고 가정하고, 두 프로세스는 flag과 turn을 공유하는 방법이다.

• flag : critical section에 들어갈 준비가 되었는지에 대한 상태를 표시 (flag[0]가 true면 P0은 준비완료)
• turn : 다음 critical section에 어느 프로세스가 들어가는가를 표시 (0이면 P0이 들어간다.)
• turn을 상대방에게 양보한 후 상대방이 critical section에 들어가있는동안 무한 loop를 돌다가 끝나면 들어간다.
• critical section을 나오면 본인 flag를 다시 false로 바꿔 상대방이 들어가게 한다.

Solution2 : test_and_set Instruction

Acquire lock 권한을 얻은 프로세스가 critical section에 접근하고, 나가면서 release lock(권한을 다시 뿌림)

1. lock이라는 shared 변수를 하나 둔다. 아무도 소유를 안한 상태면 false이다.
2. while조건이 false가 되야 무한루프를 벗어나 critical section에 접근한다.
3. 한 프로세스가 들어가는 순간 test_and_set 함수에서 *target이 true가 되어 다른 프로세스가 접근하지 못한다.
4. 이후 프로세스가 나가면 다시 lock이 false가 되어 다른 프로세스가 critical section에 접근할 수 있다.

Solution3: compars_and_sqap Instruction

첫번째 파라메터가 두번째 파라메터와 같으면 3번째 파라메터로 변경하는 방식. 전체적인 메커니즘은 solution1과 유사하지만 과정이 조금 더 복잡하다.

Solution4 : Mutex Locks

앞선 solution들은 모두 하드웨어(CPU) instruction을 쓰는 방식이라 프로그래머가 접근하기 어려웠다. 그래서 이를 사용하지 않은 방법이 Mutex Locks이다.

 

프로세스가 critical section 진입 전 반드시 acquire()로 lock을 획득해야 하고, 사용 종료 시 해제하는 방식. 다시 말해 순서가 acquire() → critical section → release()다. 그러나 여전히 busy waiting이라 비효율적이다.

Solution5 : Semaphores

가장 대중적이고 중요한 방법으로, 간단히 말하면 shared 영역의 깃발을 보고 프로세스들이 접근할지 말지를 결정하는 방법. 이 깃발을 Semaphore(S)라고 하며, wait()과 signal() 상태가 존재한다.

wait() : S가 양수일때만 1감소, P()라고도 함. wait을 통과하면 S를 감소시키고 critical section에 접근 가능

signal() : S를 1증가, V()라고도 함. S를 다시 올려서 다른 프로세스가 critical section에 접근 가능하도록 함

Usuage Example 1

세마포어를 만들고, 초기값을 1로 설정. critical section 들어가기 전에 wait(), 이러면 여러 프로세스가 존재할 때, 단 하나의 프로세스만 wait()으로 s를 1 감소시키고 wait을 통과하여 critical section에 접근한다. 그리고 이 프로세스는 나가면서 signal()을 통과하므로 s를 다시 1 증가.

 

Usuage Example 2

 

예를 들어 다운로드 프로세스인 P1, 랜더링 프로세스인 P2가 동시에 실행중이라 하면, 이 순서가 S1 -> S2일 수도 있고, S2 -> S1일 수도 있다. 그러나 랜더링은 무조건 다운로드 이후여야 하기 때문에 S1 -> S2로 설정하려는 경우이다.

 

이 케이스도 마찬가지로 둘 사이에 synch라는 semaphore을 두어 P1(S1) + P2(wait) -> P1(signal) + P2(S2) 순으로 실행하게 한다.