2021. 4. 3. 16:29ㆍComputer Science/Operating System
Background
현대의 컴퓨터 프로세스들은 다중 코어, 다중 프로세스, 다중 스레드 방식 등을 통해 여러 명령들(instruction lines)이 병행하게, 혹은 병렬로 실행될 수 있습니다. 하나의 CPU에서 스케줄링 없이 각각의 프로세스를 sychronized 한 방식으로 처리한다면 아무런 문제가 없겠지만, 이러한 방식은 답답한 UX를 만들고, 프로그램의 성능을 떨어뜨리는 결과를 가져옵니다. (최신의 노트북은 적어도 4개~8개의 CPU 코어를 가지고 있습니다.)
이렇게 여러 개의 코어에서 여러 프로세스들이 스케줄되어 실행되기 때문에 현대의 컴퓨터는 우수한 성능을 낼 수 있지만, Process Scheduling, Shared Memory 등등 여러 가지 복잡한 사항들을 고려해야 합니다. 이번 포스팅에서는 여러 가지 프로세스들이 공유하는 메모리(Shared Memory)에 접근할 때 발생할 수 있는 잠재적인 문제점들을 살펴보고, 이를 해결하기 위한 여러 방법들을 살펴보려고 합니다.
Race Condition
CPU는 한번의 하나의 인스트럭션만 실행할 수 있기 때문에 여러 개의 프로세스들을 동시에 실행하기 위해서는 각각의 프로세스들을 적절한 시간 단위(timeslice)로 쪼개서 여러 개의 프로세스들을 동시에 실행하는 것처럼 보이도록 프로세스를 스케줄 합니다. (Scheduling). 하지만 여기서 주의해야 할 점은 CPU가 프로세스를 스케줄 하는 단위는 Java, C 등의 언어로 개발자가 작성한 코드라인이 아닌, 해당 코드라인이 기계어로 컴파일된 단위인 인스트럭션(Instruction)이라는 것입니다. 예를 들어 단순히 어떤 변수에 값을 할당하는 한줄짜리 연산인 다음과 같은 연산도,
- let s = 1
기계어로 컴파일 되면 다음과 같이 1개 이상의 인스트럭션이 되기 때문에 이러한 시점에서 스케줄링되고, 다른 여러 프로세스들이 공유하는 변수에 대해 연산을 하게 된다면 예상하지 못한 결과가 나타날 수 있습니다.
- load s
- move 1 to s
- store s
흔하게 제시되는 예는 Producer & Consumer 예제입니다.
couter변수는 두 프로세스가 공통으로 접근할 수 있는 변수이고, Producer 코드는 BufferSize보다 count변수가 작으면 couter를 증가시키고, Consumer코드는 couter가 0보다 크면 couter를 감소시키는 코드입니다.
현재 Couter가 5이고, producer와 consumer가 동시에 동작했을 때, 스케줄링 방식 등에 따라서 다음과 같은 결과가 발생할 수 있습니다. (항상 아래와 같은 결과가 나오는 것이 아니며, CPU가 어떤 타이밍에 어떻게 프로세스 스케줄링을 진행하는가에 따라서 임의의 순서로 실행됩니다.)
이러한 결과가 나올 수 있는 이유는, 각각의 프로세스는 공용변수인공용 변수인 counter를 조작하기 위해 자신의 local register에 counter값을 올려놓고 조작한 뒤에 register값을 counter에 이동하는 방식으로 instruction을 실행하는데, 이때 이 공용 변수인 counter가 아무런 보호를 받지 않고 두 프로세스가 모두 접근할 수 있도록 허용함으로써 다음과 같은 결과가 발생한 것입니다.
위와 같이 두 개 이상의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 것은 경쟁 조건 (Race Condition)이라고 합니다. 운영체제는 이러한 경쟁 조건이 발생하지 않도록 공용변수를 보호해야 하는 책임이 있습니다. 특정 순간에 다수의 커널 모드 프로세스들이 운영체제 안에서 활성화될 수 있기 때문에 커널 코드는 경쟁 조건이 발생하기 쉬우며, 프로그램이 이러한 상황에서도 올바른 실행결과를 반환할 수 있도록 해야 합니다.
The Critical Section Problem
n개의 프로세스 [P0 ~ Pn-1] 이 있는 시스템을 고려해 보자. 각 프로세스는 임계 구역(critical section)이라고 부르는 코드 부분을 포함하고 있고, 그 안에서는 공유 데이터에 접근하고 갱신할 수 있다. 한 프로세스가 자신의 임계 구역에서 수행하는 동안에는 다른 프로세스들은 자신의 임계 구역에 들어갈 수 없다.
각 프로세스는 자신의 임계구역으로 진입하려면 진입 허가를 요청해야 하며 이를 entry section이라고 부른다.
임계 구역 이후에는 임계 구역에서 나왔다는 것을 알려야 하며 이를 exit section이라고 한다.
위와 같은 임계 구역 문제를 해결하기 위해서는 다음의 요건을 충족해야 합니다.
- Mutual Exclusion: 한 프로세스가 자신의 임계 구역에서 실행하고 있다면 다른 프로세스들은 임계 구역에서 실행할 수 없다.
- Progress: 자신의 임계구역에서 실행되고 있는 프로세스가 있고, 임계 구역으로 진입하려는 프로세스들이 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음 임계 구역으로 진입하려는 자격이 주어지고, 선택은 무제한 연기될 수 없다.
- Bounded Waiting: 프로세스가 자기의 임계구역에 진입 요청을 한 이후부터, 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계 구역에 진입하도록 허용되는 횟수에는 한계가 있어야 한다. (무한정 기다리게 하면 안 된다)
Peterson's Solution
위의 Critical Section Problem에 대해 Peterson의 해결안이 널리 알려져 있습니다. flag배열과 turn이라는 공유 변수를 통해 특정 프로세스가 entry section에 접근하려고 했을 때, 이 프로세스가 접근 요청을 했는지 + 이 프로세스의 차례가 맞는지를 확인함으로써 특정 순간에 단 하나의 프로세스만이 Critical Section에 접근하여 수행할 수 있도록 처리한 것입니다.
Limitation
위에 알려진 Peterson의 해결법은 몇 가지 유용한 insight들을 제공해주기는 하지만, 아쉽게도 현대의 시스템에서는 사용되기가 어렵습니다. 주된 이유는 최신의 시스템에서 시스템 성능을 향상하기 위해 연관되지 않은 (종속성이 없는) Read / Write작업을 임의로 재정렬할 수 있기 때문입니다. 즉, flag배열과 turn변수는 서로 종속성이 없으므로, 위 두 변수에 대한 할당은 시스템에 의해 재 정렬될 수 있으며, 위 두 변수의 할당 순서가 바뀌면 올바르게 Critical Section Problem을 해결할 수 없기 때문입니다.
또한 위의 방식은 대기하는 동안 Process를 Block상태로 만드는 것이 아닌 무한정 While Loop를 돌면서 CPU 사이클을 낭비한다는 문제도 있습니다. Context Switch의 비용이 큰 경우에는 Context Switch 없이 다른 스레드에서 작업을 진행하게 하여 위와 같은 While Loop이 유용할 때가 있지만, 그렇지 않은 경우에 이는 낭비가 됩니다.
Reference
codex.cs.yale.edu/avi/os-book/OS10/index.html
Operating System Concepts - 10th edition
codex.cs.yale.edu