7. 병행 프로세스와 동기화 ①

이 글은 병행프로세스와 상호배제에 대해 다루겠습니다. 스케줄링이란 주어진 시점에서 어떤 프로세스가 이 자원을 사용할 수 있도록 해 줄 것인가를  결정하는 것을 뜻합니다. 전체적인 내용은 OS? Oh Yes! 서적 기반, 숙명여대 김주균 교수님 강의, 티스토리 등을 정리했습니다. 공부한 것을 정리하는 형식으로 작성되었으므로 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요?

Concurrent Processes (병행 프로세스)

병렬처리는 여러 개의 프로세스가 동시에 실행 가능함을 뜻하는 반면 병행이란 메모리에 여러 프로세스가 같이 존재한다는 뜻이므로 병렬과는 다른 개념입니다. 병행성은 처리기의 수와 상관 없으나, 병렬처리가 성공하기 위해서는 기본적으로 병행성이 전제되어야 하는 관계라고 볼 수 있습니다.

공유하는 자원이나 데이터가 있는 병행 프로세스들이 각자 비동기적(asynchronous)으로 실행되는 것을 제대로 관리하지 못한 채 방치할 경우 문제가 발생하게 됩니다. 이 때 비동기적이란 병행 프로세스들은 자신이 아닌 다른 프로세스들이 어떤 상태에 있는지, 어떤 자원을 가지고 있는지, 어디까지 실행되었는지 등을 모른 채 실행한다는 뜻입니다. 만약 [한 사람만 건널 수 있는 다리가 있다고 할 때, 다리를 아무도 건너고 있지 않으면 다리 난간에 초록불이, 누군가가 건너고 있다면 다리 난간에 빨간불이 켜진다고 합시다. 또, 초록불일 때 다리를 건너고 싶다면 다리 앞에 있는 버튼을 눌러 난간의 불을 빨갛게 만들고 건너고, 다 건넌 후에는 반대편에 있는 버튼을 눌러 다시 초록색으로 난간 빛을 바꿔야 한다고 합시다.] 이렇게 비유를 한다고 하면 이 다리를 건너게 될 사람들이 병행 프로세스들에 해당 되고 누가 언제 다리를 건널 지 모르므로 이들은 비동기적인 관계라고 할 수 있습니다.

Mutual Exclusion (상호 배제)

만일 위의 예시에서 누군가가 빨간불일 때 다리를 건너려고 한다면, 또는 다리를 건너기 전에 버튼을 누르지 않았더라면, 또는 다리를 다 건넌 후 버튼을 누르지 않았다면 문제가 생길 것입니다. 즉, 정해 놓은 규칙을 지키지 않았을 경우에 문제가 생기게 되는 것입니다. 그러나 만약 이 다리를 건널 사람들의 수 만큼 다리가 존재했다면 이런 문제는 생기지 않았을 겁니다. 즉, 병행 프로세스들의 비동기적 실행은 공유된 자원(다리)이 없다면 생기지 않는 문제이지만, 자원이 공유될 수 밖에 없기 때문에 정해놓은 룰을 따라야 하는 것입니다. 이 'rule'을 다시 정리해보자면 : '한 번에 한 프로세스만이 접근하고, 해당 자원에 대해 의도했던 실행을 완료하도록 보장함'이라고 할 수 있겠습니다.

조금 더 현실적으로, 

• 공유자원 count의 초기값 = 10
• 프로세스 A의 역할 : count += 1
• 프로세스 B의 역할 : count -= 1

라고 할 때, A → B 순서로 진행된다면 결과는 똑같이 10이어야 할 것입니다. 그러나 만약 A가 count = 11로 만들고 메모리에 그 값을 저장하기 전에 time out 되어 CPU를 B에게 빼앗긴다면 여전히 10인 count 값에  B를 수행하므로 최종 count = 9가 되게 됩니다. 즉, 한 프로세스가 공유 변수 조작을 하는 도중 다른 프로세스가 같은 자원에 조작을 하게 되는 경우를 부정확한 값이 나오므로 이런 일은 방지해야 하는 것입니다. 이렇게 프로세스들이 공유 데이터에 대해 서로 접근을 시도하는 상황을 race condition(경쟁 상태)라고 부릅니다. 이 때문에 생기는 문제는 다음과 같습니다.

• 상호 배제(Mutual exclusion)
• 교착 상태(Deadlock)
• 기아(Starvation)

 [ Mutual Exclusion ] (상호배제) 

우선 임계 자원(critical resource)과 임계 영역(critical section)에 대해 알아야 합니다. 임계 자원이란 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원을 뜻하고 임계 영역이란 어떤 프로그램에서 임계 자원에 대해 접근하고 실행하는 코드 부분을 뜻합니다. 그래서 상호배제란 한 번에 하나의 프로세스만이 임계영역에 들어가야 함을 의미합니다. 임계 영역의 성공적인 실행을 위해서는

• 상호배제가 지켜져야 함
• 임계 영역에 있지 않는 프로세스가 다른 프로세스의 임계 영역 진입을 막으면 안됨
• 비어 있는 임계 영역에 대한 진입은 바로 허용해야 함
• 특정 프로세스의 진입이 무산되는 기아를 겪으면 안됨

 [ Deadock ] (교착상태) 

자원이 한정적인 상황에서 두 개 이상의 프로세스가 각자 먼저 확보한 자원ㅇ르 가진 채 상대방의 자원을 필요로 할 경우, 외부로부터의 조치가 없는 한 프로세들은 아무 일도 못하고 계속 기다려야 하는 상태

 

 [ Starvation ] (기아)  특정 프로세스의 임계 영역으로 진입이 무산되는 현상 / 스케줄되지 못하고 계속 밀리는 현상

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

소프트웨어 기법이란 운영체제의 지원 없이 프로세스들 간에 자신의 프로그램에서 임계 영역 앞뒤로 적절한 코딩을 통해 상호배제를 해결하는 방식입니다.

 [ Peterson's Algorithm ] 

2개의 프로세스 사이의 상호배제를 제대로 구현한 것으로 Dekker의 알고리즘이 있으나 이해하기 어렵고 정확성을 증명하기 까다롭습니다. 그러나 Peterson의 알고리즘이 간결하게 나와 이 단점으로 해결하였으며 다음과 같이 생겼습니다. (P1( )의 경우 1은 0으로, 0은 1로 바꾸면 됨)

 [ Lamport's Bakery Algorithm ] 

위 알고리즘은 프로세스가 2개일 때 상호배제를 해결할 수 있지만 실제로는 그 보다 더 많은 프로세스들이 존재하기 때문에 한계가 있습니다. n개의 프로세스를 대상으로 하는 알고리즘은 많이 있으나 그 중에서도 bakery algorithm으로 알려져 있는 Lamport의 알고리즘을 살펴보도록 하겠습니다. 원래는 분산 시스템용으로 소개가 되었으나 n 개의 프로세스들을 대상으로 하는 상호배제 기법으로도 유용합니다.

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

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

단일처리 시스템에서 사실상 병행 프로세스들이 하나의 CPU를 번갈아 사용하는 것이므로 어떤 프로세스가 임계영역에 들어가 있다면 CPU를 빼앗기지 않도록 인터럽트가 발생하지 않도록 하면 됩니다. 그러나 다중처리 시스템에서는 다른 처리기에서 실행되는 프로세스로부터의 접근 가능성은 여전히 존해하므로 사용하기 힘든 방법입니다.

 

 [ 하드웨어 명령어를 사용한 기법 ] 

기계 명령어로 알려져 있는 testandset과 exchange(또는 swap) 명령어를 사용하여 문제를 해결할 수 있습니다. 기계 명령어란 원자적으로 실행 도중 끊김 없이 완료되는 연산입니다. 각각의 기계 명령어를 활용한 상호배제는 아래와 같이 구현이 되고, 비록 아래에는 코드처럼 적혀있지만 실행 시 절대 끊기지 않는 연산입니다. 기계 명령어를 활용하면 간단하고, 다중처리 시스템에서도 쉽게 쓸 수 있고, 한 프로그램 내에서 서로 다른 변수를 사용하여 여러 개의 임계 영역도 지원할 수 있는장점이 있습니다.

testandset 명령어를 사용한 상호배제

exchange 명령어를 사용한 상호배제