[운영체제] 프로세스 동기화

프로세스 동기화

멀티 쓰레드 프로그램에서 쓰레드들은 자원을 공유하며 협력한다. 이때 공유 자원 접근 시에 동기화가 보장되지 않으면 Race condition이 발생할 수 있고 부정확한 결과로 이어진다. 이를 방지하기 위한 방법을 동기화라고 한다.

동기화라는 것은 공유 자원을 어떠한 프로세스가 사용하고 있을 경우 값이 반환되기 전까지 blocking 하는 것을 말한다. 즉, Critical section에 대한 상호 배제를 제공해 race condition을 회피하는 방법이다.

Race condition

쓰레드에 의해서 공유 자원에 접근한 결과가 스케줄러에 의한 접근 타이밍에 의존해 결정되는 상태이다. 결과를 예측할 수 없고 싱글 프로세스이든 멀티 프로세스이든 발생할 수 있다.

임계 구역 문제 (Critical Section Problem)

동일한 자원을 동시에 접근하는 작업을 실행하는 코드 영역을 critical section이라고 한다. 만약 모든 쓰레드가 read만 할 경우에는 race condition이 발생하지 않는다. 임계 구역 문제(Critical Section Problem)은 프로세스들이 Critical Section을 함께 사용할 수 있는 프로토콜을 설계하는 것이다.

해결을 위한 3가지 조건

crtical section 문제를 해결하기 위해서는 기본적으로 3가지 조건을 만족해야 한다.

상호 배제 (Mutual Exclusion)

한 번에 하나의 쓰레드만 임계 구역에 접근할 수 있도록 보장하는 것을 말한다.

진행 조건 (Progress)

임계 구역에서 실행 중인 프로세스가 없고, 별도의 동작이 없는 프로세스들만 임계 구역의 진입 후보로서 참여될 수 있다.

한정 대기 (Bounded Waiting)

모든 프로세스의 대기가 언젠가는 끝나야 한다. starvation이 일어나서는 안된다.

해결 방안

Spin Lock

들어가길 원하는 flag와 차례인지 표시하는 turn을 써서 임계 구역 문제를 해결을 위한 3가지 조건 1. 상호 배제 2. 진 행 3. 유한 대기 를 만족시는 알고리즘이다.

busy waiting에 의해 lock되는 것을 spin lock이라고 한다. busy waiting은 대기를 하는 동안 실제 작업 없이 CPU를 계속 사용하여 대기하는 것이다. 자원이 낭비되며 fairness를 보장하지 않아 starvation이 일어날 수 있다. 또한 다중 쓰레드가 데이터를 공유하는 과정에서 명령어의 순서를 바꿔버리면 상호 배제 조건이 충족되지 않는다는 한계가 있다.

Disabling Interrupt

싱글 프로세서 시스템의 경우에 어떤 프로세스가 임계 영역에 들어갔을때 나머지 인터럽트를 disable하는 방법이 있다. 하지만 interrupt가 lost 될 수 있고 멀티 프로세스에서는 사용할 수 없으며 비효율적이다. 고의적인 프로그램에 의해 privileged operation이 남용될 수 있다.

예) 커널 작업을 수행하는 중에 인터럽트 발생

Mutex Lock

동시에 공유 자원에 접근하는 것을 막기 위해 Critical Section에 진입하는 프로세스는 Lock을 획득하고 Critical Section을 빠져 나올 때, Lock을 방출하므로써 동시에 접근이 되지 않도록 한다. Binary Semaphore라고도 불린다. 세마포어가 locked / unclocked로 0 또는 1의 정수 값만 가질 수 있기 때문이다.

한계

다중쓰레드 환경에서는 시간적인 효율성 측면에서 적용할 수 없다.

Semaphore

세마포어는 프로그램 레벨에서 쉽게 상호 배제 시키기 위해서 2개의 primtive opertation (wait P, signal V)와 하나의 공통으로 관리하는 값(세마 포어)를 사용한 기법이다. 진입에 실패한 프로세스에 대해서 Lock 시킨 뒤, Critical Section에 자리가 날 때 다시 깨우는 방식으로 Busy waiting을 해결했다.

• 카운팅 세마포어 : 가용한 개수를 가진 자원에 대한 접근 제어용으로, 세마포어는 그 가용한 자원의 개수로 초기화된다. 자원을 사용하면 세마포어가 감소, 방출하면 세마포어가 증가한다.
• 이진 세마포어 = mutex lock

한계

• 데드락이 발생할 수 있다. (두 개 이상의 프로세스들이 실행되지 못하는 상태로 서로의 점유하고 있는 자원을 기다리면서 실행되지도 종료되지도 못하는 상태에 빠진 것을 말한다.)
• 프로그램에 흩어져 있어서 디버깅하기가 어렵다.

Monitor

세마포어의 단점을 보완한 고급 언어의 설계 구조물로서, 개발자의 코드를 상호 배제 하게끔 만든 추상화된 데이터 형이다.

직접 키 해제와 공유 자원 접근 처리가 필요한 세마포어와 달리 공유 자원에 접근하기 위한 키 획득과 자원 사용 후 해제를 모두 처리한다.

생산자 소비자 문제

생산자가 데이터를 생산하면 소비자는 그것을 소비하는 형태에서 발생하는 문제를 말한다. 일반적으로 멀티 쓰레드 웹서버를 예로 들 수 있다.

생산자와 소비자의 속도 차이를 보완하기 위해 버퍼라는 공간을 활용한다. 생산자는 데이터를 생산해 버퍼를 채운다. 버퍼가 가득 차면 생산자를 더 이상 생산을 할 수 없다. 소비자는 버퍼에서 데이터를 꺼내 소비한다. 버퍼가 비어 있으면 소비자는 소비를 할 수 없다.

해결 방안

• 생산자, 소비자는 공유 자원을 이용하고 관리를 위해 상호 배제여야한다. -> mutex lock
• 공유 자원의 상태를 체크해야한다. -> semaphore as cv