개요(Overview)
운영체제에서 '병행 프로세스'란 여러 개의 프로세스나 스레드가 '동시에' 실행되는 것처럼 보이는 상태를 말합니다.
실제로 단일 CPU 시스템에서 '병행' 또는 '병렬'로 일을 처리한다는 것은 하나뿐인 CPU를 반으로 분할하여 다른 작업을 처리하도록 하는 것을 의미하는 것이 아닙니다.
하지만, 컴퓨터가 단위 시간당 처리하는 작업 속도는 사람의 인지 능력으로 알아채기 어려울 만큼 굉장히 빠르기 때문에 실제로는 여러 가지 일을 순식간에 전환하여 마치 '동시에' 여러 가지 일을 처리하는 것처럼 보이도록 하는 기술을 의미합니다.
그리고 이렇게 운영체제가 프로세스가 CPU를 점유하는 시간을 빠르게 전환시켜서 사용자에게 동시에 실행되는 것처럼 보이게 하는 기술을 인터리빙(interleaving)이라고 합니다.
반면에 오늘날 범용적으로 사용되는 멀티 프로세스 시스템에서는 여러 CPU를 활용하여 실제로 여러 프로세스가 동시에 실행될 수 있도록 하는데 이를 '병렬 처리'라고 합니다.
따라서 위 내용을 요약하자면,
단일 프로세서 시스템에서는 하나의 CPU를 여러 프로세스가 '동시에' 사용할 수 있도록 '병행 프로세스', '인터리빙'이라는 기술이 적용되고
멀티 프로세서 시스템에서는 여러 CPU가 진정한 의미에 '동시성'을 갖도록 하는 '병렬 처리'라는 기술이 적용됩니다.
이처럼 '병행 처리'는 프로세스들이 서로 관계없이 독립적으로 수행할 수 있도록 다른 프로세스들과 협력하면서 기능을 수행하는 것이 특징입니다.
1.1. parbegin/parend 제어문
순차적인 수행으로부터 여러 개의 동시 수행으로 갈라짐을 지시하는 명렁어와 여러 개의 동시 수행되는 작업들이 하나로 모여 순차적인 수행이 되도록 지시하는 명렁어가 있습니다.
이러한 명령어를 parbegin/parend 제어문이라고 하는데 일반적인 형태는 아래와 같습니다.
parbegin
statement 1;
statement 2;
.
.
.
statement 3;
parend
위 선형 그래프에서는 parbegin/parend 제어문에서 선언한 각 문장들이 하나의 노드(Node)로 짝을 이룹니다. 따라서 각 문장에 대응되는 노드들이 유향 비순환 그래프(direct acyclic graph)를 이룹니다. 예컨데 노드 Si에서 노드 Sj로 가는 간선(Edge)에는 문장 Si가 완전히 수행된 다음에 문장 Sj가 수행된다는 것을 의미합니다.
예를 들어 위 그래프의 경우 아래와 같은 선행 관계가 성립됩니다.
- S2와 S2는 S1이 끝난 후 수행된다.
- S4는 S2가 끝난 후 수행된다.
- S5와 S6는 S4가 끝난 후 수행된다.
- S7는 S5, S6, S3이 끝난 후 수행된다.
추가로 아래와 같은 작업에 대한 선형 그래프가 있다고 가정해 봅시다.
위 그래프의 작업의 순서를 설명하기 위해서는 판독 집합과, 기록 집합이라는 개념이 필요합니다.
먼저, 판독 집합이란 문장 Si가 수행되는 과정에 Si에 의해 값이 참조되는 모든 변수의 집합을 의미합니다. 이를 수식으로 나타내면 아래와 같습니다.
R(Si) = { a1, a2, … , am }
다음으로, 기록 집합이란 문장 Si에 수행에 의하여 값이 변하게 되는 모든 변수들의 집합을 의미합니다. 이를 수식으로 나타내면 아래와 같습니다.
W(Si) = { b1, b2, … , bn }
위에 소개한 개념을 설명하기 위해, 간단한 알골(Algol) 계열의 프로그래밍 언어에서 사용되는 간단한 할당 연산자에 대해서 소개하도록 하겠습니다.
c := a-b
위 표현식은 변수 a에서 b를 뺀 결과를 변수 c에 할당하는 것을 의미하는 문장입니다.
이와 같은 표현식에서 a와 b는 c라는 값을 계산하기 위해 사용되는 변수이므로 판독 집합에 속합니다.
그러나 c의 경우 그 값이 문장에서 사용되지 않으므로 문장의 수행 결과에 의해 새로운 값이 결정되어 기록 집합에 속합니다.
이를 각각 판독 집합과, 기록 집합에 대한 수식으로 표현하면 아래와 같습니다.
R(c := a-b) = { a, b }
W(c := a-b) = { c }
지금 사례로 든 경우에는 판독 집합 R(Si)와 기록 집합 W(Si)이 교집합이 공집합이지만,
모든 경우에서 반드시 두 집합의 교집합이 공집합일 필요는 없습니다.
추가로 아래와 같은 사례도 살펴보자면,
x := x +2
위의 표현식에 대하여 각각 판독 집합과 기록 집합의 교집합은 아래와 같이 합집합입니다.
R(x := x+2) = W(x := x+2) = { x }
1.2. 상호 배제(Mutual Exclusion)와 임계영역(Critical Section)
프로세스들이 공용 변수에 접근(Access)할 때에는 그 프로세스만이 접근할 수 있게끔 함으로써 상호배제 문제를 해결할 수 있습니다. 이는 즉 하나의 프로세스가 공용 변수를 증가시키고 있는 동안에는 동일한 공용변수에 접근하고자 한다면, 나중에 접근한 프로세스들이 이 작업이 끝날 때까지 기다리게 한다는 것을 의미합니다.
그리고 선행 프로세스가 공용 변수를 다 사용하고 나면 기다리고 있던 다른 프로세스 중 하나가 공용 변수를 접근할 수 있도록 하는데, 이처럼 하나의 프로세스 외에는 다른 프로세스들이 공용 변수를 액세스하지 못하도록 제어하는 기법을 상호 배제(Mutual Exclusion)이라고 합니다.
따라서, 상호 배제는 프로그램들이 공용 데이터를 함께 접근하려 할 때 필요한 기법으로, 공용 변수나 데이터를 동시에 함께 접근하지 않으려 할 때는 프로세스들은 동시에 수행되는 것이 허용되어야 합니다. 어떤 프로세스가 공용 데이터를 접근하고 있을 때, 그 프로세스는 임계 영역(Critical Section) 내에 있다고 합니다.
임계 영역 내에 있던 프로세스가 임계 영역을 벗어나면 임계 영역에 들어가기를 기다리던 다른 프로세스들 중 하나가 임계 영역 내로 들어가도록 허용됩니다. 상호 배제를 지키는 것은 병행 프로그래밍에 있어서 굉장히 중요한 문제입니다. 임계 영역에 있다는 것은 한 프로세스만이 공용 데이터를 배타적으로 접근하고 나머지 프로세스들은 공용 데이터에 대한 접근을 필요로 하더라도 기다리도록 하기 때문입니다.
그러므로 임계 영역 내의 수행은 가능한 빨리 끝내 주어야 하며, 한번 임계 영역에 들어간 이후에는 프로세스가 보류(block)되는 일이 없어야 합니다. 또한, 임계 영역이 무한 루프에 빠지지 않도록 프로그램 코드를 잘 작성하여야 합니다.
만약 임계 영역 내에서 프로세스가 멈추게 되면 운영체제는 상호 배제를 풀어서 다른 프로세스가 임계 영역에 들어갈 수 있도록 처리하는 것이 중요합니다. 상호 배제를 처음으로 소프트웨어 적으로 해결한 사람은 네덜란드의 수학자 Dekker이며 이를 다익스트라가 설명하였습니다. Dekker가 고안한 알고리즘은 1.3.5 Dekker 알고리즘 장에서 다루도록 하겠습니다.
1.3. 상호배제 프리미티브(primitive)
본 장에서는 두 개 이상의 프로세스가 상호배제를 수행하는 것을 해결하는 다양한 예시에 대해 다루도록 하겠습니다. 앞서 설명한 parbegin/parend 제어문을 바탕으로 어떻게 상호 배제 상황을 다룰 수 있는지 예시문과 함께 살펴보도록 하겠습니다.
1.3.1. 상호배제 프리미티브(primitive) 1
var pnumber : integer ;
procedure pone;
begin
while true do
begin
while pnumber 2 do ;
CSone;
pnumber := 2;
end
end;
procedure ptwo ;
begin
while true do
begin
while pnumber = 1 do;
CStwo;
pnumber := 1;
end
end;
begin
pnumber := 1;
parbegin
pone ;
ptwo ;
parend
end
위 예시문은 2개의 프로세스가 상호배제를 수행하는 것을 해결하려 하는 예시입니다.
parbegin/parend 제어문 때문에 pone과 ptwo가 동시에 수행됩니다. 이 두 프로세스들은 무한 순환을 하는데 계속해서 임계 영역을 들어갔다가 나오는 작업을 반복합니다. 위 사례에서 while loop가 상호 배제로 들어가는 것으로 구현되었으며, pnumber라는 변수가 자기 프로세스의 번호와 같아질 때까지 계속 loop문을 돌면서 기다립니다.
상호배제 탈출은 pnumber라는 변수를 상대방 프로세스의 번호로 치환하도록 구현되었습니다. pone이 while do문을 수행하면, pnumber의 초기치가 1이므로 pone이 임계 영역에 진입하게 됩니다. ptwo는 pnumber가 1인 것을 확인하고 while do 순환을 계속하게 됩니다. ptwo가 CPU에 들어갈 때는 pnumber가 2로 되는 것을 기다리며 loop를 반복하게 됩니다. 따라서 ptwo는 임계영역에 들어가지 못하고 상호배제는 보장됩니다. 언젠가는 pone이 임계 영역 내의 일을 끝내고 pnumber가 2가 되도록 하여 ptwo로 하여금 임계영역으로 들어갈 수 있도록 할 것입니다.
위와 같은 방식은 상호 배제는 보장할 수 있지만, 그 비용이 매우 큽니다. 위 해결책은 pone이 반드시 먼저 시작해야 한다는 한계점을 가지고 있으며, ptwo가 먼저 임계영역에 들어갈 준비가 되어 있더라도 pone이 들어갔다가 나오기를 기다려야 하므로 오랜 시간 대기해야 할 수 있습니다.
즉 프로세스들은 반드시 한 번씩 교대로 들어갔다 나와야 하는데, 만일 한 프로세스가 자주 임계 영역을 접근할 필요가 있더라도 한 번씩 교대로 들어갔다가 나와야 하므로 프로세스의 전체적인 수행 속도는 느려지게 됩니다. 그러나 이러한 시스템은 교착상태에 빠질 염려는 없습니다. 만일 두 프로세스 중 하나가 중단되더라도 다른 프로세스도 더 이상 계속할 수 없게 되기 때문입니다.
위 사례에서는 공용변수가 단 한 개였기 때문에 lockstep synchronization 문제가 발생되었습니다. 그렇기에 다음 사례에서는 2개의 변수가 있는 경우에 대해 설명해보도록 하겠습니다.
1.3.2. 상호배제 프리미티브(primitive) 2
var p1, p2 : boolean;
procedure pone;
begin
while true do
begin
while p2 do
p1 := true;
CSone ;
p1 := false;
end
end
procedure ptwo;
begin
while true do
begin
while p1 do
p2 := true
CStwo;
p2 := false ;
end
end
begin
p1 := false;
p2 := false;
parbegin
pone;
ptow;
parend
end
위 사례에서 p1 변수는 pone이 임계영역에 있을 때 참(TRUE)이 되고, p2 변수는 ptwo가 임계영역에 있을 때 참(TRUE)가 됩니다. p2가 참(TRUE)일 동안 pone은 busy wait을 하게 됩니다. 언젠가는 ptwo가 임계영역을 벗어나게 되고, 그 때 p2를 거짓(FALSE)로 합니다. 이 시점에서 pone는 p1을 참(TRUE)으로 하고 임계영역으로 들어가게 됩니다. p1이 참(TRUE)인 동안에는 ptwo는 임계영역으로 들어갈 수 없습니다.
이러한 방식은 pone과 ptwo가 동시 프로세스 이므로 동시에 while 문에 도달할 수 있습니다. 이 상황에서 p1과 p2는 초기 값이 모두 거짓(FALSE)이므로 pone 이 p2를 확인해보면 거짓(FALSE)임을 알 수 있습니다. 그런데 pone이 p1을 참(TRUE)로 하기 전에 ptwo가 p1을 시험해 보면 역시 거짓(FALSE)임을 알 수 있습니다. 그러면 pone은 p1을 참(TRUE)으로 하고 임계 영역으로 들어가며, ptwo도 p2를 참(TRUE)으로 하여 임계영역에 들어가게 됩니다.
이 때 두개의 프로세스는 동시에 임계영역으로 들어갈 수 있으므로 이 방식에서는 상호배제가 보장되지 않습니다.
1.3.3. 상호배제 프리미티브(primitive) 3
var p1, p2 : boolean;
procedure pone;
begin
while true do
begin
p1 := true;
while p2 do
CSone ;
p1 := false;
end
end
procedure ptwo;
begin
while true do
begin
p2 := true;
while p1 do;
CStwo;
p2 := false;
end
end
begin
p1 := false;
p2 := false;
parbegin
pone;
ptwo;
parend
end
일단 어떤 프로세스가 while 검사를 시작하게 되면 다른 프로세스는 그것을 할 수 없도록 해야 합니다. 위의 예시에서는 while 검사를 하기 전에 자신이 먼저 while 검사를 시작하는 사실을 알리기 위해 자신의 플래그(flag)를 바꾸어 문제를 해결하려고 시도합니다.
위와 같은 방식으로 앞선 방식의 문제를 해결할 수 있지만, 두 프로세스가 while 검사를 하기 전에 자신의 flag를 동시에 바꾸면 각 프로세스는 서로 상대방의 flag의 상태를 확인하고는 영원히 while do만 할 것입니다. 즉, 이 사례에서는 2개의 프로세스의 교착 상태가 나타날 수 있음을 표현한 예시입니다. 이때 가장 큰 문제점은 각 프로세스가 while do 순환을 무한정 계속할 수 있다는 점입니다. 따라서 이러한 순환으로부터 빠져나올 방법은 다음 장에서 설명합니다.
1.3.4. 상호배제 프리미티브(primitive) 4
var p1, p2 ; boolean;
procedure pone;
begin
while true do
begin
p1 := true ;
while p2 do
begin
p1 := false;
delay (random, fewcycles) ;
p1 := true;
end
CSone;
p1 := false;
end
end
procedure ptwo;
begin
while true do
begin
p2 := true;
while p1 do
begin
p2 := false;
delay(random, fewcycles) ;
p2 : true;
end
CStwo;
p2 := false;
end
end
begin
p1 := false ;
p2 := false;
parbegin
pone;
ptwo;
parend
end.
위 방식에서는 순환하는 각 프로세스가 그 flag를 얼마동안 계속해서 거짓(FALSE)으로 설정하는 지를 주안점으로 둡니다. 이렇게 함으로써 다른 프로세스가 while 순환을 지나가게 되고, 상호 배제와 교착상태는 해결되지만 무한 연기 문제가 발생할 수 있습니다. 이때 개별 프로세스의 상대적은 속도를 예측할 수 없기 때문에 가능한 모든 수행순서를 고려해야 합니다.
각 프로세스가 신호를 참(TRUE)으로 하고 while 검사를 통해 while loop의 몸체 부분을 수행하여 flag를 거짓(false)으로 하고, 다시 참으로 하고, 다시 while 검사를 계속하게 할 수 있습니다. 이렇게 검사할 때마다 값은 계속 참(TRUE)으로 남아있을 수 있지만, 이러한 경우가 발생한 확률은 매우 적다고 볼 수 있겠습니다.
따라서 이러한 문제들을 해결하기 위하여 Dekker 알고리즘이 제시되었습니다. 이 알고리즘은 2개의 프로세스의 상호 배제 문제를 하드웨어의 도움 없이 해결하고 지금 제시된 무한 연기의 가능성을 해결합니다.
1.3.5. Dekker 알고리즘
var favoerP (first, second) ;
p1, p2 ; boolean;
procedure pone;
begin
while trud do
begin
p1 := true;
while p2 do
if favorP = second then
begin
p1 := false;
while favorP = second do
p1 : true;
end
CSone;
favorP := second;
p1 := false;
end
end
procedure ptwo;
begin
while true do
begin
p2 := true ;
while p1 do
if favorP = first then
begin
p2 := false;
while favorP = first do
p2 : true;
end
CStwo;
favorP := first;
p2 := false;
end
end
begin
p1 := false;
p2 := false;
favorP := first;
parbegin
pone;
ptwo;
parend
end.
이 사례는 Dekker 알고리즘을 설명한 것입니다. 이 알고리즘은 2개의 프로세스가 상호배제 문제를 하드웨어의 도움 없이 해결하고 그럼 8.6에서 발생한 무한연기의 가능성을 해결합니다. 위 코드에서 pone은 그 flag을 참(TRUE)으로 해두고 자신이 임계 영역에 들어가려고 한다는 것을 알려줍니다. 그리고 난 후 while 검사를 통해 ptwo가 임계 영역에 들어가기를 원하는 가를 알아봅니다. 만일 ptwo의 flag가 거짓(FALSE)이라면 pone은 while 순환을 넘어 임계 영역으로 들어가게 됩니다.
만약 pone이 while 검사를 할 때, ptwo의 flag가 참(TRUE)으로 되어 있다면 pone은 while 순환을 넘어서 임계 영역으로 들어가게 됩니다. 여기서 favorP라는 변수는 2개의 프로세스가동시에 임계영역으로 들어가려 할 때 그 충돌을 방지해주는 역할을 담당합니다.
만일 pone이 favorP라면 pone은 if의 몸체 부분을 수행하지 않고, 계속해서 ptwo가 flag를 거짓(FALSE)로 해주기까지 while 순환에서 기다리게 됩니다.
또한, pone이 ptwo가 favorP 임을 알게 되면 if의 몸체 부분에 들어가 자기의 flag를 거짓(FALSE)으로 해두고 ptwo가 favorP인 동안 계속 while 순환을 돌게 됩니다. 이렇게 자기의 flag를 거짓(FALSE)으로 함으로써 ptwo가 임계영역에 들어갈 수 있도록 해줍니다.
언젠가는 ptwo가 임계영역을 벗어나게 되고 상호 배제 탈출 코드를 실행하게 됩니다. 그러면 favorP는 다시 pone이 되고 ptwo는 flag를 거짓(FALSE)으로 해둡니다. 이때 pone은 자기의 flag를 참(TRUE)으로 해둠으로써 바깥 while 순환으로 나와 ptwo의 flag가 아직도 거짓(FALSE)임을 확인하고 임계 영역으로 들어갑니다.
이때 ptwo가 다시 임계영역으로 들어가려고 하면 ptwo의 flag가 참(TRUE)이 되고 pone은 다시 바깥 while 순환의 몸체로 오게 될 것입니다. 이 상황에서는 pone이 주도권을 갖게 됩니다. 왜냐하면 자기 자신이 favorP이기 때문입니다. 이는 ptwo가 임계영역을 벗어날 때, favorP를 pone으로 해두기 때문에 그렇습니다.
pone은 if문의 몸체 부분을 넘어 바깥의 while 순환을 계속 돌다가 ptwo가 자신의 flag를 거짓(FALSE)으로 하게 되면 임계 영역으로 들어가게 됩니다. pone이 내부의 busy wait 순환에서 나올 때 CPU에 대한 제어 권한을 반납하게 되고, ptwo가 순환을 하며 임계영역에 다시 들어가려고 한다고 가정한다면 ptwo는 자신의 flag를 참(TRUE)으로 할 것이고, 임계영역에 진입하게 됩니다.
pone이 CPU에 대한 제어 권한을 다시 받게 되면 pone이 flag를 참(TRUE)으로 할 것입니다. 이제는 pone의 차례이므로 만일 ptwo가 다시 들어가려고 한다면 자신의 flag를 거짓(FALSE)으로 두고, 내부의 busy wait을 하게 되서 pone이 임계 영역에 들어가게 되기 때문에 이 경우에는 무한 연기가 발생하지 않습니다.
참고 자료
- 김완규, 고정국, 진광윤, 최신형, 하성권, 허덕행 | 핵심 운영 체제론 | 두양사
'CS BASIC > 운영체제(Operation System)' 카테고리의 다른 글
| [운영체제] 교착 상태(Dead Lock)와 필요 조건 (0) | 2024.12.30 |
|---|---|
| [운영체제] 세마포어(Semaphore) (1) | 2024.12.24 |
| [운영체제] 파일 시스템(File System) (2) | 2024.12.01 |
| [운영체제] 가상 기억장치의 구성과 관리 – 페이지 교체 기법 (1) | 2024.11.25 |
| [운영체제] 가상 기억장치의 구성과 관리 - 페이징과 세그먼테이션 (0) | 2024.11.24 |
