Operating System 7 - Critical Section

 shared data를 필요로 하는 여러 프로세스를 동시에 실행할 경우 일관성이 없어져 원하는 결과가 나오지 않을 수 있다. 이를 해결하는 방법이 동기화를 이용하는 것이다.

예를 들어 count++을 실행할 때 어셈블리어로는 3줄의 instruction이 필요하다. 이 때 만약 2 개의 instruction 마다 interrupt가 발생하여 context switch가 발생한다면 저장하지 못한 값을 참조하여 잘못된 결과가 나올 수 있다. (공유 데이터를 사용하는 시점과 load-exec-store의 단계가 온전히 실행되지 않기 때문)

Race condition : 두개의 프로세스가 같은 영역과 데이터에 대해 접근하고 조작하여 사용하는 경우. 이 경우는 instruction의 순서에 따라 결과가 바뀌게 된다. 따라서 이는 undesirable 한 상황이다.
이를 해결하는 방법은 하나의 프로세스만 자원에 접근하도록 막아야 한다. (=동기화 하는 것)

critical section : 공유데이터를 사용하는 구간. (어떤 프로세스의 실행 블럭에서 해당 공유 데이터를 사용하는 segment of code)
따라서 해당 구간(entry section ~ exit section)을 실행하는 프로세스가 있다면 해당 프로세스 하나만 실행되어야 한다.

- critical section problem : 상기 문제를 해결하기 위해 프로세스를 디자인 하는 것.
이를 위해 필요한 feature는 3가지가 있다. mutual exclusion(상호 배제), progress(하나가 끝나면 그 다음 프로세스가 들어와 진행해야 함), bounded waiting(무한정 기다리는 상황이 발생하면 안된다.)

* 상호배제가 일어나지 않으면 OS에서 pid를 배정할 때도 같은 pid가 배정하는 경우가 생길 수 있다. (커널에서 이런 경우가 발생하면 컴퓨터가 셧다운 된다)

그러나 멀티 코어 시스템에서 간단한 비선점 식으로 인터럽트를 막으면 다른 프로세스가 모두 멈춰 효율이 급감한다. 따라서 이를 선점형 커널에서 여러 기법을 사용하여 해결한다. (이는 하드웨어 성능 향상을 위한 것으로 학부과정에서 다루지 않는다)

Peterson's Solution
critical section problem을 완벽하게 해결할 수 있는 고전적 솔루션. 그러나 현재 컴퓨터 환경에서는 작동할 지 보장할 수 없다.

- turn : 어떤 프로세스가 할 차례라는 것을 알려줌.
- flag : 해당 프로세스가 준비되었다고 표시하는 것.

turn을 사용한 코드 예시를 살펴보면, mutual exclusion이 보장된다. context switch에 의해서 실행되는 코드가 변경되어도, turn의 값에 따라 프로세스가 while문 안에서 갇혀 있으므로 상호배제가 된다.
그러나 상기의 조건 중 progress가 만족되지 않는다. (turn만 사용할 경우) 왜냐하면 critical section이 빌 때도 다른 프로세스가 아직 turn 값을 바꿔주지 않았다면 (remainder를 실행하느라) 들어갈 수 없는 경우가 생길 수 있기 때문이다.

flag를 사용한 코드 역시 자기가 들어갈 때 값을 바꿔 다른 프로세스에게 자신이 실행 중이라는 것을 알린다. 이 것 역시 상호배제는 이루어지지만 progress는 이루어지지 않는다. 또한 context switch가 잘못되면 각 flag가 true일 경우가 발생하여 deadloack이 발생할 수 있다.  (flag 초기값은 false)

따라서 두 변수를 동시에 사용하여 progress와 상호배제를 모두 만족 시킨 것이 peterson's solution이다. while문의 조건에 공유변수 turn과 각각의 flag를 모두 사용하여 deadlock을 방지한다. (상기 3조건 모두 만족함)

그러나 실제로 현대 컴퓨터 아키텍처에서는 컴파일러가 자체적으로 instruction 들의 순서를 재조정하므로 (CA에서 배운 것 처럼 실행 속도 상승과 instruction 수 감소를 위해) peterson solution은 제대로 작동하지 않을 수 있다. (turn와 flag의 순서가 바뀌면 제대로 작동하지 않는다)
Hardware support for synchronization
critical section problem을 해결하기 위한 하드웨어적 방법.

1. Memory barrier
memory_barrier() 명령어가 들어가면, 이 부분까지 실행한 것들을 모두 전파시킨다는 의미이다. 따라서 컴파일러가 이 명령어가 있는 사이에서는 instruction을 재배열하지 않는다. 따라서 flag와 turn 사이에 해당 명령어를 추가하면 된다.

2. hardware instruction
uninterruptible unit (atomic, 해당 instruction들은 모두 한번에 실행, 인터럽트나 context switch가 발생하지 않는다)을 설정하는 것.

- test_and_set instruction : 파라미터로 입력된 어떤 boolean 값을 반드시 true로 바꾸고, 오리지널 value를 리턴한다. (오리지널 값이 false라면 리턴은 false. 오리지널 값은 true로 변경됨) 위에서 말한 것 처럼 해당 작업은 모두 atomic 하게 수행된다. 따라서 이를 while의 조건문에 삽입하여 flag/turn 등을 바꿀 때 사용된다.

- compare_and_swap instruction : 예상한 값과 현재 값이 같으면 새로운 값으로 변경하고 오리지널 value를 리턴한다.

* 두 함수 모두 리턴 값은 항상 초기 값.

자원 선점이 발생하면 lock(lock=1)을 걸고, 다 수행한 다음 아무도 기다리는 사람이 없으면 lock을 다시 푼다. (lock=0)

atomic variable : race condition이 발생하는 곳에서 (count++) 상호배제를 보장하기 위해 사용하는 변수. 일반적으로 int나 boolean이다. 이는 compare_and_swap을 이용하여 ++ 작업을 수행하는 방식으로 구현된다.

Mutex lock : 들어갈 때 키를 받아 사용하고, 다 쓰고 나오면 키를 반납하는 형식. 키는 단 한개 뿐이므로 상호배제를 수행하는 방식이다. (MUTual EXception lock)
acquire(), release(), available() 등의 함수를 구현하여 사용할 수 있다.
이 때 acquire/release 등은 모두 atomic하게 실행해야 하므로 상기의 compare_and_swap 등 함수 등으로 구현해야 한다.

Busy waiting : while 문에 갇혀 기다리는 것. 자신이 풀리는 지 아닌 지 계속적으로 수행하며 확인하는 과정(잉여시간)

busy waiting을 하고 있는 mutex lock을 spinlock이라 한다. 이는 일반적으로 cpu의 사용을 낭비하는 것으로 여겨질 수 있지만, 멀티 코어 시스템에서는 context switch의 시간을 줄여주어 성능을 개선하는 데에 사용된다. (CPU가 많을 경우, 하나의 코어가 담당하여 하던 작업을 완료하여 flag가 바뀌면, 다른 코어에서 spinlock되어 무한 루프 되던 것이 바로 수행될 수 있다)

따라서 상기 경우는 플랫폼과 상황에 따라 최적인 OS가 계속 바뀔 수 있다는 대표적인 예시가 된다.

Semaphore
여러 자원이 있을 때 동시 접근을 허용하는 것. integer variable을 가지고 있고 P() / wait() 과 V() / signal()  두 개의 atomic operation으로만 접근할 수 있다. P는 --, V는 ++ 작업이다.
integer variable을 상기의 key처럼 사용하여 값에 따라 busy waiting을 하도록 설정한다. (use resource = wait(), count decrement / release resource = signal(), count increment)

이 값에 따라 순서대로 수행해야 하는 프로세스가 있을 경우 이에 대한 동기화도 진행할 수 있다. 이 때 이 integer variable을 0/1(binary semaphore) 뿐 아니라 일정 값을 줄 수 있는데, 이럴 경우 허용된 n 개의 프로세스가 자원에 접근하는 것을 허용할 수 있다. (counting semaphore)

그러나 이 역시도 busy waiting을 사용한다. CPU 개수가 많이 않아 이를 좀 개선하고 싶다면 busy waiting을 해야 할 때 block을 통해 suspend 시켜서 큐에서 대기하다가 작업이 완료되면 wakeup()을 시켜 프로세스를 재시작 하게 만들 수 있다.