임계 영역에 몇 개의 프로세스가 접근할 수 있는가

병행이란?

병행이란 말 그대로 같이 존재하고 있다는 뜻이며 메모리에 다수의 프로세스가 같이 존재한다는 의미이다. 이런 프로세스들이 어떤 순서로 실행될 것인가 하는 일차적 문제는 스케줄링에서 담당하겠지만 실제 실행 과정에서 프로세스 간의 관계로부터 발생하는 좀 더 복잡한 문제는 세심한 관리를 요구한다. 

비동기적(Asynchronous)

병행 프로세스들이 서로 비동기적이라는 말은 다른 프로세스들이 어떤 상태에 있는지, 어떤 자원을 가지고 있는지, 어디까지 실행됐는지 모른 채 실행되고 있음을 의미한다. 공유하는 자원이나 데이터가 있는 병행 프로세스들이 각자 비동기적으로 실행되는 것을 관리하지 못한다면 문제가 생기게 된다.

#1. 병행 프로세스 (Concurrent Processes)

병행 프로세스들의 비동기적 실행은 서로 공유된 자원이 없는 한 아무 문제없이 독립적으로 진행되지만, 공유된 자원이 있을 경우 이 자원의 접근에는 일정한 룰(Rule)을 따라야 한다. 공유된 자원이나 데이터에 대해 병행 프로세스들이 따라야 하는 룰은 "한 번에 한 프로세스만이 접근하도록 하고, 해당 자원에 대해 의도했던 실행을 완료하도록 보장한다."는 것을 의미한다.

#2. 상호배제 (Mutual Exclusion)

• 프로세스들이 공유 데이터에 대해 서로 접근을 시도하는 상황을 경쟁 상태(Race Condition)라 하며 이러한 경쟁관계에 있는 프로세스들로 인해 상호 배제, 교착 상태(Deadlock), 기아(Starvation)와 같은 문제가 발생하게 된다. 
• 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원(임계 자원, Critical Resource)에 대해 접근하고 실행하는 프로그램 내의 코드 부분을 임계영역(Critical Section)이라 한다. 
• 상호 배제란 한 번에 하나의 프로세스만이 임계 영역(Critical Section)에 들어가야 함을 의미한다. 
• 임계 영역의 성공적인 실행을 위해서는 맨 먼저 상호 배제가 지켜져야 한다.
• 임계 영역에 있지 않는 프로세스가 다른 프로세스의 임계 영역 진입을 막아서는 안 된다.
• 비어있는 임계영역에 대한 진입은 바로 허용된다.
• 특정 프로세스의 진입 시도가 계속 무산되어 기아(Starvation)를 겪지 않도록 해야 한다.
• 임계 영역을 진입할 때와 나올 때 꼭 해야 하는 일들을 어떻게 잘 구현해서 프로그램 내의 임계영역 앞뒤에 적절하게 코딩해 주느냐가 상호 배제의 성공 여부를 결정짓게 된다.

임계 영역 문제를 해결하는 메커니즘에 대한 세 가지 충족 요건

• 상호 배제(mutual exclusive) : 한 프로세스가 임계 영역에서 실행하고 있으면 어떤 프로세스도 임계 영역에 진입할 수 없어야 한다.
• 진행(progress) : 임계 영역을 실행하고 있는 프로세스가 없을 때 몇 개의 프로세스가 임계 영역에 진입하고자 하면 인들의 진입 순서는 이들에 의해서만 결정되어야 한다. 이 선택은 무한정 연기되어서는 안 된다.
• 한계 대기(bounded waiting) : 한 프로세스가 자신의 임계 영역에 진입하고자 요청을 한 후부터 이 요청이 허용될 때까지 다른 프로세스가 그들의 임계 구역에 진입할 수 있는 횟수가 제한되어야 한다.

#3. 상호 배제를 위한 소프트웨어 기법들

Dekker의 알고리즘

• Dekker's 알고리즘은 2개의 프로세스를 보장하는 최초의 알고리즘이다.
• 둘 중 하나만 진입하고자 하면 다른 프로세스의 flag 값이 false이므로 진입할 수 있다. 
• 두 프로세스가 모두 진입하고자 하면 turn값이 진입하는 프로세스를 결정한다.
• Dekker's 알고리즘은 mutual exclusive, progress, bounded waiting 세 가지 요건 모두 충족한다.

Peterson의 알고리즘

• Dekker의 알고리즘을 간결하게 만든 것이 Peterson의 알고리즘이다.
• P0는 flag[0]을 true로 설정해서 자신이 진입하겠다고 알린다.
• P0는 flag[1]이 false이거나 turn이 1일 경우에만 진입이 가능하다.
• 임계 영역에 진입한 프로세스가 자신의 flag를 false로 전환하기 전까지는 다른 프로세스가 진입할 수 없음.
• mutual exclusive, progress, bounded waiting 세 가지 요건 모두 충족

Lamport의 Bakery 알고리즘

• n개의 프로세스들을 대상으로 하는 상호 배제 기법
• 모든 number, choosing값은 0과 false로 초기화
• 임계 영역의 진입을 원하는 프로세스 i는 먼저 number 값이 주어지는데 다른 프로세스들이 이미 받은 값보다 더 큰 값을 받게 된다.
• for문 안에서 첫 번째 while문은 번호 값을 받는 중인 프로세스가 있다면 그 값도 비교해야 하기 때문에 대기
• 두 번째 while문에서 자신의 값이 가장 작을 때 임계영역의 진입을 허가
• 임계 영역을 벗어난 후 자신의 값을 0으로 해줌으로써 다른 프로세스에게 기회를 준다.
• 번호 값에 의해 차례가 정해 지므로 특정 프로세스의 무한 대기는 걱정하기 않아도 됨.

소프트웨어 기법들의 문제점

• 실행 시 부하가 크며 실수로 인한 우류의 가능성이 높다
• 구현이 복잡하다.
• Busy Wait, Spinlock

#4. 상호 배제를 위한 하드웨어 기법들

인터럽트 금지를 사용한 기법

• 단일처리 시스템의 경우 임계 영역의 처리 동안 모든 종류의 인터럽트를 금지
• 다중 프로그래밍에 큰 영향을 주며 효율적인 해결책은 아님
• 다중처리 시스템에서는 다른 프로세스로부터의 접근 가능성이 여전히 존재, 임계영역 문제

TestAndSet과 Exchange 명령어

• 기계 명령어로서 원자적으로 실행 도중 끊김 없이 완료되는 연산
• testandset은 전역 변수 lock으로부터 넘겨받은 파라미터 target 값을 rv에 넣고 target의 값을 true로 만든 후 rv의 값을 넘겨준다.
• exchange는 넘겨받은 두 개의 파라미터 값을 맞바꾸는 일을 해줌

• lock의 초기 값이 false이므로 최초 진입 프로세스가 testandset을 실행하게 되면 target 값이 false가 되어 rv로 넘겨진다. 
• while문은 false가 되고 결과적으로 임계 영역의 진입이 가능해진다.
• 임계 영역을 실행 중인 프로세스가 있다면 lock의 값이 true이므로 진입을 시도하는 다른 프로세스들이 while문에서 맴돌게 됨으로써 상호 배제를 보장한다. 
• 프로그램 내 서로 다른 변수를 사용하여 여러 개의 임계 영역도 지원 가능
• 단점은 busy waiting과 차례가 정해지지 않으므로 starvation문제가 나타나고 교착 상태에 빠질 우려가 있음.

세마포어(Semaphore)

• 세 개의 특수한 명령들만 접근할 수 있게 혀용 되는 보호된 변수로서 높은 수준에 상호 배제 명령을 구현
• 세마포어가 0 또는 1의 이진 값만 가지면 이진 세마포어, 음이 아닌 모든 정수가 될 수 있으면 계수(정수) 세마포어라 한다.
• 세마포어 값을 초기화하는 명령, P명령, V명령이 있고, P와 V는 wait와 signal의 이름으로 사용하기도 한다.

• P명령은 S값이 0보다 크면 1 감소, 그렇지 않으면 S값이 0보다 크게 되기를 기다린다.
• V명령은 S가 0보다 크게 되기를 기다리는 프로세스 하나를 계속 진행하게 하고, 존재하지 않는다면 S값 +1

• 세마포어 변수 S가 1로 초기화되어 있음.
• 최초로 시도하는 프로세스가 S를 0으로 바꾸고 임계 영역에 진입
• 이후 진입을 시도하는 프로세스들은 S가 0이므로 대기 상태
• 임계 영역을 나오는 프로세스에 의해 S는 1이 되고 프로세스 하나는 실행 가능 상태가 되어 임계 영역 진입

세마포어를 활용하면 상호 배제뿐만 아니라 프로세스 간의 동기화도 쉽게 구현할 수 있다. 하지만 연산 P와 V가 뒤바뀔 경우 임계 영역 문제, 교착 상태 문제가 일어날 수 있다.

#5. 생산자-소비자 문제(Producer-consumer Problem)

• 생산자는 데이터를 만들어 버퍼에 저장하고, 소비자는 버퍼에 있는 데이터를 꺼내 소비하는 프로세스
• 버퍼는 공유 자원이므로 버퍼에 대한 저장하고 꺼내는 일들은 상호 배제되어야 함
• 버퍼가 차있을 때는 생산자가 버퍼가 비어 있을 때는 소비자가 기다려야 하는 동기화도 포함됨

• in과 out은 버퍼에서 채워 넣은 위치와 꺼낼 위치를 나타냄
• 초기 값은 각각 0이고, 버퍼가 차있거나 비어 있을 경우 중간의 while문을 맴돌게 됨.

• 버퍼에 대한 접근을 상호 배제하기 위해 (이진) 세마포어 변수 s를 사용
• 채우거나 꺼낼 수 있는 공간이 있는지 확인하기 위해 (정수) 세마포어 e와 f를 사용

OS 모니터와 관련한 참고 사이트 : https://codemcd.github.io/study/OperatingSystem-11%EC%9E%A5-%EB%AA%A8%EB%8B%88%ED%84%B0/

Mutex와 세마포어 차이 : https://worthpreading.tistory.com/90

참고 자료 

• OS? Oh Yes! , 김주균 지음

'OS' Related Articles