[Operating System] 동시성 제어

멀티 프로세싱 또는 멀티 쓰레드 등을 통해 프로그램을 실행할 때 발생할 수 있는 동시성 문제와 이를 제어하는 방법에 대해 알아보겠습니다.

 

동시성 문제란 무엇인가?

동시성 문제란 같은 Resource 를 공유하는 프로세스, 쓰레드 사이에서 하나의 작업이 다 완료되지 않았는데 다른 하나가 공유하는 Resource 에 접근할 때 발생하는 문제를 이야기합니다.

 

동시성 문제는 왜 발생하는가?

동시성 문제가 발생하는 이유는 한마디로 요약하면 'Race Condition' 입니다. 경주를 하면 누가 결승선에 먼저 들어올지 결과가 나오기 전까지 모르는 것처럼, 동시성 문제가 발생하는 이유는 같은 자원을 공유하는 Process 들이 Race 를 하여 어떤 결과가 나올지 알 수 없게 되기 때문입니다.

 

다음은 동시성 문제를 다룰 때 주로 사용되는 용어들에 대한 정의입니다.

 

• Mutual Exclusion : The requirement that when one process accesses shared resources, no other process may access of those shared resources.
• Critical Section : A section of code within a process that requires access to shared resources and that may not be executed while another process is in a corresponding section of code. Only one program at a time is allowed in its critical section.
• Starvation : A situation in which a runnable process is overlooked indefinetly by the scheduler. although it is able to proceed, it is never chosen.
• Deadlock : A situation in which two or more processes are unable to proceed because each is waiting for one of the others to do something. Deadlock is starvation for an indefinite duration.

 

멀티 프로세싱에서 동시성 문제가 발생하는 예시 

멀티 프로세싱에서 동시성 문제

위 그림을 보면, Process P1 과 P2 는 모두 문자를 하나 입력받아 출력하는 프로그램을 실행하고 있습니다. P1과 P2 가 멀티 코어 시스템에서 각각 CPU 를 하나씩 할당 받아 처리하고 있다고합시다. 이 때, P1과 P2 는 chin 과 chout 을 shared memory 에 저장하고 사용합니다. 즉 공유하는 자원을 가지고 있습니다.

 

P1 이 chin 에 getchar() 를 통해 문자하나를 저장합니다. 이 Instruction 직후 concurrent 하게 프로세스가 실행되고 있으므로, P2 에서도 chin = getchar() 가 수행된다고 합시다. 그러면 chout 에는 P2 의 getchar() 에서 입력받은 문자가 저장되게 되고 P1과 P2 의 putchar(chout) 에서 모두 P2 에서 입력받은 getchar() 값이 출력이 됩니다.

 

즉, P1 은 P1 의 getchar() 가 있었음에도, concurrent 하게 실행되던 P2 에 의해서 예상된 결과를 얻을 수 없습니다. 즉, P1과 P2 가 race condition 에 있습니다.

 

Uniprocessor 에서 Race Condition 이 발생하는 예시

Race Condition in Uniprocessor

 

위와 같이 Producer 와 Consumer 라는 프로세스가 동작하고 있다고 가정합시다. 이 때, Counter 라는 전역변수를 이용하여 버퍼안에 몇개의 Item 이 들어있는지 셀 수 있습니다. 즉 Buffer 와 Counter 는 shared resource 가 됩니다. Producer 와 Consumer 프로그램의 코드는 아래와 같습니다.

Code of Producer

 

Code of Consumer

 

이 때, Producer 와 Consumer 는 Race Condition 에 있기 때문에 다음과 같은 동시성 문제가 발생할 수 있습니다. 다음 예시를 살펴봅시다.

 

Race Condition

즉, 버퍼에 실제로 5개 들어있어야 하는 상황에 6이 저장되는, 예상치 못한 결과를 만날 수 있습니다.

 

그렇다면, 어떻게 Race Condition 을 막을 수 있을까?

Race Condition 을 막는 구체적인 예시를 살펴보기 앞서, Critical Section Problem 이 방지되는 조건에 대해서 알아봅시다.

 

다음 조건들을 만족하면 Critical Section Problem 을 막을 수 있습니다.

• Mutual Exclusion : The requirement that when one process accesses shared resources, no other process may access of those shared resources.
• Progress : If there is a process that wishes to enter its critical section and no other process is executing in its critical section, then this process should be able to enter by itself.
• Bounded Waiting : If there is a process that wishes to enter its critical section and a process is executing in its critical section, then waiting process can enter its critical section in some time (does not wait indefinitely)

 

이제 위 조건을 만족시키는 Race Condition 을 해결할 수 있는 솔루션은 무엇이 있는지 알아봅시다.

 

1. Make a critical section be executed as atomic operations. -> It's not a good way.
2. Make a fence around a critical section

1번 솔루션은 critical section 에 해당하는 instruction 을 수행할 때 interrupt 를 disable 시키고 해당 instruction 이 끝나면 다시 enable 시켜 critical section 의 code 를 atomic 하게 수행하는 방법입니다. 하지만 Critical Section 의 길이가 길면 CPU 는 오랜시간동안 인터럽트를 처리하지 못하게 되어 여러 Side Effect (네트워크 인터럽트 처리 x 등) 가 발생할 수 있습니다.

 

2번 솔루션은 1번 솔루션의 단점인 Interrupt 를 처리하지 못한다는 점을 해소합니다. Critical Section 을 수행 중일 때 다른 프로세스가 Critical Section 을 수행하지 못하도록 합니다.

 

Software 적으로 2번 솔루션을 구현하는 방법이 있지만 이를 위한 overhead 가 크기 때문에 실제 잘 사용하지는 않습니다.

 

다음은 Software 적으로 2번 솔루션을 구현하는 간단한 예시입니다.

 

가장 간단한 형태의 Fence, Progress 를 만족하지 못한다.

위의 솔루션은 Fence 를 만들지만 progress 를 만족하지 못합니다. 즉, Critical Section 을 수행하고 있는 프로세스가 없어도, turn 이 오지 않으면 Critical Section 안에 들어갈 수 없습니다.

 

Peterson's Algorithm, Mutual Exclusion과 progress 를 모두 만족한다.

피터슨 알고리즘은 Mutual Exclusion 과 Progress 요구사항을 모두 만족하지만, 오직 두 프로세스 사이에서만 적용가능하다는 한계가 있습니다.

 

Bakery Algorithm, Overhead 가 크다.

마지막으로, Bakery Algorithm 입니다. Peterson's algorithm 을 확장하여 여러 프로세스에 적용가능하지만, Overhead (반복 횟수 등) 가 매우 크므로, 비효율적인 Critical Section Problem 을 제어하는 방법입니다.