Race Condition
Race Condition : 여러 프로세스들이 동시에 동일한 데이터 접근할 때 접근 순서나 타이밍에 따라 결과값이 달라지는 현상
일반적으로 컴퓨터 시스템의 데이터 접근 방식은 데이터가 저장된 곳에서 데이터를 읽어와 연산을 진행한 이후 그 결과를 다시 해당 위치에 저장하는 방식으로 진행이 하는 여러 instruction 과정을 거치게 된다.
이 때 데이터를 읽어가는 타이밍에 따라 프로세스들의 결과값이 달라지는 현상이 발생할 수 있다. 이를 해결하기 위해서는 공유 데이터에 접근하는 프로세스 간의 실행 순서를 정해주는 메커니즘을 통해 일관성을 유지해 주어야 한다.
일반적으로 Race Condition은 아래와 같은 상황에서 발생하게 된다.
커널 모드 수행 중 인터럽트 발생
간단히 count연산이 모두 실행되어 기존 값을 유지할 것이라 생각하지만 실제 실행시켜보면 인터럽트의 결과는 반영되지 않고 count값이 1증가한 값이 된다. 이런 경우 하던 일을 완료할 때까지 인터럽트를 받아들이지 않도록 해서 해결이 가능하다.
시스템 콜을 통한 커널모드 수행 중 문맥교환 발생
시스템 콜을 통해서 커널의 코드 부분이 실행 중일 때 할당 시간이 만료되어 다른 프로세스로 넘어가 그 프로세스가 이전에 건드리던 커널 코드를 실행시키게 되는 경우 문제가 발생할 수 있다. 이런 경우 프로세스가 커널 모드에 있다면 할당 시간에 의해 cpu를 빼앗기지 않고 유저 모드로 빠져 나오는 경우에만 cpu를 빼앗도록 해서 해결이 가능하다. 스케줄링이 일부 밀릴 수는 있지만 real-time에 해당되지는 않기 때문에 큰 문제가 되지는 않는다.
멀티 프로세서 환경에서 공유 메모리내 데이터 접근
cpu가 여러개 있는 상황이라면 이전의 해결채들은 작업 주체가 여러개가 되는 것이기 때문에 무용지물이 된다. 이런 경우 데이터나 커널 자체에 lock을 걸어 하나의 주체만이 데이터 혹은 커널에 접근할 수 있도록해서 해결이 가능하다. 하지만 일반적으로는 커널을 하나만 사용하는 것은 비효율적이기 때문에 데이터에 lock을 거는 방식을 사용한다.
Critical Section
critical Section(임계 구역) : 공유 데이터에 접근하도록 작성된 코드
critical section 문제가 발생했을 때 해결하기 위해서는 3가지 조건을 만족해야 한다.
Mutual Exclusion
Mutual Exclusion(상호 배제)은 어떤 프로세스가 critical section에 들어가 있는 경우 다른 모든 프로세스들은 critical seciton에 들어가지 못하게 하는 것을 의미한다.
Progress
Progess(진행)는 critical section에 어떠한 프로세스도 들어가 있지 않다면 critical section에 들어가고자 하는 프로세스를 넣어줘야 하는 것을 의미한다.
Bounded Waiting
Bounded Waiting은 특정 프로세스 입장에서 critical section에 들어가지 못하게 기다리는 시간이 유한해야 하지 않다는 것을 의미한다. 즉, starvation이 생기지 않아야 한다.
Synchronization Algorithms
critical section 문제를 해결하기 위한 몇가지 알고리즘들이 존재한다.
프로세스 차례 변수 사용 알고리즘
어떤 프로세스가 critical section에 들어갈지를 결정하는 프로세스 차례 변수를 사용하는 알고리즘이다.
이 알고리즘의 경우 Mutual Exclusion은 만족하지만 Progress 조건을 만족시키지 못한다.
p0와 p1이 있다고 했을 때 p0가 빈번하게 들어가고 p1이 한번만 들어가게 된다면 p0는 한번은 수행될 수 있지만 이후로는 영원히 들어가지 못하는 현상이 발생하게 된다.
Flag 사용 알고리즘
프로세스가 자신이 Critical Section에 진입할 의사를 표명하는 flag 변수를 사용해 다른 프로세스가 진입 의사가 있다면 기다리게 하는 알고리즘이다.
마찬가지로 Mutual Exclusion은 만족하지만 Progress 조건은 만족시키지 못한다.
process i가 flag를 true만들고 cpu를 뺏긴 이후 다른 j프로세스가 cpu를 받아 flag를 true로 설정 이후 다시 cpu가 i로 돌아가게 된다면 i와 j프로세스 모두 대기하게 된다.
Peterson 알고리즘
차례 변수와 Flag를 모두 사용하는 알고리즘이다.
상대방이 critical section에 접근하고자 하는 의사 표현을 한 상황에서 상대방의 차례에 해당한다면 critical section에 접근하는 것을 대기하고 그 외의 경우라면 자신이 critical section에 접근하게 된다.
이 방식은 critical section 문제 해결을 위한 3가지를 조건을 모두 만족하지만 critical section 접근을 위해 대기하는 상황에서 cpu나 메모리를 계속 잡아 사용하는 busy waiting(spin lock) 문제가 발생 가능하다.
Synchorization Hardware
하드웨어적으로는 데이터를 읽고 저장하는 과정이 하나의 instruction으로 주어진다면 critical section 문제는 아주 쉽게 해결할 수 있다. 이를 위해 제공되는 대표적인 기능이 Test_and_set이다.
Test_and_set을 이용하면 간단하게 데이터 접근을 할 수 있다.
Semaphore
Semaphore : 운영체제나 동기화 프로그래밍에서 공유 자원 접근을 제어하기 위한 도구
Semaphore는 일종의 추상자료형으로 Busy Waiting이 필요 없는 동기화 도구이며, 여러 프로세스나 스레드가 critical section에 진입할 수 있는 signaling 메커니즘이다.
세마포어는 동시에 자원에 접근할 수 있는 프로세스를 제한하기 위한 카운터라는 변수를 사용하고 주로 S로 나타낸다. 즉 카운터를 통해 사용 가능한 자원의 개수를 나타내게 된다.
세마포어는 2가지 연산을 제공하는데 이 2가지 연산은 atomic하게 동작된다.
P()연산은 공유 데이터를 획득하는 연산이고 V()연산은 공유 데이터를 반환하는 연산이다.
세마포어는 일반적으로 2가지로 구분된다.
Binary Semaphore
0과 1만을 가질 수 있는 세마포어로 일반적으로 lock을 걸 때 사용한다. 즉, Mutual Exclusion에 사용되는 세마포어이다.
Counting Semaphore
변수값이 0과 1만이 아닌 여러 수가 주어지는 세마포어로 자원의 개수를 나타내는데 사용된다.
일반적인 세마포어 사용방식은 아래와 같다.
하지만 세마포어를 사용해도 Busy Waiting이 발생 가능하다. 세마포어에서는 Block & Wakeup 방식으로 구현하는 것도 가능하다. Block & Wait을 Sleep Lock이라고도 부르며 자원을 얻지 못하면 프로세스가 cpu나 메모리를 사용하면서 대기하는 것이 아니라 Blocked 상태로 잠들게 한다.
세마포어 변수값과 세마포어로 인해 잠들어 있는 프로세스들을 연결하기 위한 큐가 하나 만들어지게 되고 세마포어를 획득할 수 없으면 프로세스를 block시킨다. 그리고 누군가 자원을 반납하게 되면 block상태인 프로세스를 하나 깨워 동작시킨다.
S.value가 0이하임을 체크하는 것은 누군가가 기다리면서 잠들어 있는 경우를 체크하기 위함이다.
Classical Problems of Synchronization
Synchronizaiton 관련 대표적인 세가지 문제가 존재한다.
Bounded-Buffer Problem (Producer-Consumer Problem)
이 문제는 프로세스가 producer와 consumer 2가지로 구분되며 생산자와 소비자는 모두 여러개 존재할 수 있다는 가정 하에 이루어진다.
먼저 공유 버퍼이기 때문에 생산자가 같은 위치에 동시에 데이터를 생성하게 되면 문제가 발생가능하다. 마찬가지로 소비자도 같은 위치에 동시에 데이터를 빼내려 하면 문제가 발생된다. 이를 방지하기 위해 공유 버퍼에 락을 걸어서 다른 프로세스의 접근을 막는다.
공유 버퍼가 유한하다는 점도 문제를 발생시킨다. 생산자나 소비자들이 도착했는데 이미 버퍼가 꽉 차있거나 비어 있다면 문제가 발생하게 된다. 이 경우 소비자나 생산자가 대기하게 되어 이를 카운트 하기 위한 세마포어도 필요하다.
즉, 이 문제를 해결하기 위해서는 락을 걸고 해제하는 용도, 자원을 카운트 하기 위한 용도로 세마포어 변수가 사용된다.
Reader-Writer Problem
이 문제는 프로세스가 reader, writer 2가지로 구분되고 read 작업은 여러 프로세스가 동시에 진행해도 문제가 없지만 write 작업은 여러 프로세스가 진행할 수 없다는 것을 가정 하에 이루어진다.
공유 데이터에 lock을 걸게 되면 데이터의 일관성을 지킬 수 있으나 read 작업에 대한 효율성이 떨어지게 된다. 이 문제를 효율적으로 해결하기 위해서는 Reader의 수를 위한 체크하기 위한 공유 변수 readcount를 사용한다. 최초의 reader가 들어온 경우 DB 자체를 lock하기 위한 용도로 세마포어가 하나 상용되고 readcount도 공유 변수이기 때문에 readcount를 접근에 대한 lock을 하기 위한 용도로 세마포어가 하나 더 사용된다.
Read-Writer 문제의 해결방법은 starvation 문제가 발생할 수 있다. 예를 들어 writer는 reader가 데이터를 읽고 있다면 대기해야 한다. 이로 인해 reader 계속해서 들어오게 되면 writer 프로세스는 수행되지 않을 수 있다. 이를 해결하기 위해서는 큐에 우선순위를 붕여해 늦게 들어온 reader는 기다리게 해서 writer가 작업을 진행하고 다시 읽을 수 있도록 구현해 해결이 가능하다.
Dining-Philosophers Problem
가장 대표적인 문제로 원형의 식탁에서 철학자들이 젓가락을 집어 밥을 먹는 상황을 가정한다.
철학자가 할 수 있는 작업은 생각하고 생각하다 배가 고파지면 젓가락을 들어 밥을 먹는 작업들만 가능하다 가정한다.
위와 같은 방식은 두 철학자가 동시에 먹는 것을 방지할 수는 았지만 모든 철학자가 왼쪽 젓가락을 잡게 되면 모든 철학자가 오른쪽 젓가락을 잡게 되어 모두가 대기하게 되는 Deadlock 현상에 빠지게 될 수 있다.
Deadlock을 방지하기 위한 방식으로는 최대 4명의 철학자만이 테이블에 동시에 앉을 수 있게 하거나, 젓가락을 모두 집을 수 있을 때만 젓가락을 집을 수 있는 권한을 부여하거나 짝수 철학자는 왼쪽 젓가락부터 홀수 철학자는 오른쪽 젓가락부터 잡도록하여 해결 가능하다.
Monitor
Monitor : 프로그래밍 언어차원에서 synchornizaiton 문제를 해결하기 위한 high-level synchronizaiton construct
세마포어가 P연산과 V연산을 지원해 비교적 프로그램이 쉬워지기는 했으나 아직도 직접 코딩하기는 어렵고 문제가 생겼을 경우 버그를 잡아내기가 여럽다는 문제가 있다.
모니터는 이러한 단점을 해결하기 위한 기능으로 모니터 내부에 공유 데이터를 두고 모니터 내부의 프로시저를 통해서만 해당 데이터에 접근가능하도록 해준다. 내부의 프로시저가 직접 프로세스 공유 데이터에 대한 접근이 프로세스 하나만 가능하도록 해주며 이로 인해 따로 lock을 걸어줄 필요가 없어진다.
공유 데이터에 대한 접근이 프로세스 하나만 가능하게 해주는 것은 모니터가 자체적으로 제공하는 기능으로 프로그래머가 고려할 영역에서 벗어나 간단하게 코딩을 할 수 있게 된다.
모니터는 내부에 공유 데이터와 프로시저를 가지고 있어 프로시저를 통해서만 공유 데이터에 접근 가능하도록 하고 어떤 프로세스가 내부에서 프로시저를 사용하고 있다면 다른 프로세스가 들어왔을 때 block하고 모니터 큐에서 대기하도록 한다.
이를 위해 사용되는 condition variable이 있다. condition variable은 세마포어 변수와 유사하지만 어떤 값을 가지는 변수가 아니라 프로세스를 잠들게 하게 줄 세우기 위한 변수로 내부에 wait()과 signal()연산을 가진다.
