병행(Concurrent): 같이 존재하고 있다는 의미. 메모리에 다수의 프로세스가 같이 존재하는 것.
프로세스들의 실행 순서는 일차적으로 스케줄링에서 담당하겠지만,
실제 실행 과정에서 프로세스 간의 좀 더 복잡한 문제는 세심한 프로세스 관리를 요구함.
다중처리 시스템의 경우 여러 개의 프로세스가 동시에 병렬(Parallel)로 실행됨 (=> 병행 != 병렬)
프로세스의 병행성은 처리기의 수와 상관없으나,
병렬처리가 성공하기 위해서는 기본적으로 병행성이 전제되어야 한다.
- 병행 프로세스들은 서로 간에 비동기적(Asyschronous)이다.
= 다른 프로세스들이 어떤 상태에 있는지, 어떤 자원을 가지고 있는지, 어디까지 실행됐는지 등에 대해 모른 채 실행 됨
이번 장의 목적
: 공유하는 자원이나 데이터가 있는 병행 프로세스들이 각자 비동기적으로 실행되는 것을 제대로 관리하지 못한 채 방치할 경우 생기는 문제와 이를 해결할 수 있는 방법을 설명한다.
병행 프로세스 (Concurrent Processes)
병행 프로세스들의 비동기적 실행은 서로 공유된 자원이 없는 한 아무 문제없이 독립적으로 진행되지만, 공유된 자원이 있을 경우 이 자원의 접근에는 일정한 룰(Rule)을 따라야 한다.
여기서 일정한 룰이란, "한 번에 한 프로세스만이 접근하도록 하고, 해당 자원에 대해 의도했던 실행을 완료하도록 보장" 하는 것.
상호배제 (Mutual Exclusion)
: 한 번에 하나의 프로세스만이 임계영역에 들어가야 함(임계영역을 실행해야 함)을 의미
- 경쟁 상태 (Race Condition): 프로세스들이 공유 데이터에 대해 서로 접근을 시도하는 상황
=> 교착 상태(Deadlock), 기아(Starvation) 등의 문제 발생.
- 임계영역(Critical Section): 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원(임계자원(Critical Resource)에 대해 접근하고 실행하는 프로그램 내의 코드 부분
임게영역의 성공적 실행을 위해서는,
1) 상호배제가 지켜져야 한다.
2) 임계영역에 있지 않는 프로세스가 다른 프로세스의 임계영역 진입을 막아서는 안 된다.
3) 비어있는 (아무도 실행하고 있지 않는) 임계영역에 대한 진입은 바로 허용하되, 특정 프로세스의 진입 시도가 계속 무산되어 기아를 겪지 않도록 해야 한다.
- 병행 (concurrent)
: 같이 존재하고 있다.
= 메모리에 다수의 프로세스가 존재 (다중프로그래밍)
- CPU가 하나 있는 단일처리 시스템에서는 병행 프로세스 중 한 개만이 실제로 실행되지만, CPU의 처리 시간을 효과적으로 나눔으로써 겉으로는 병행 프로세스들이 동시에 처리되는 것
프로세스 처리 순서는
1차적: CPU 스케줄링에 의해 진행.
하지만, 실제 실행 과정에서 프로세스 간의 관계로부터 발생하는 문제 발생 O.
ㄴ 이를 관리하는 것이 프로세스 관리의 핵심!
* 병행(concurrent) ≠ 병렬(parallel)
- 병행(concurrent): 다중프로그래밍, 메모리에 다수의 프로세스가 존재
- 병렬(parallel): 다중처리시스템, 여러 개의 CPU가 여러 개의 프로세스를 동시에 처리 (병렬 처리)
⇒ 병행에 있어서는 처리기(CPU) 수 관계 x,
but, 병렬처리 위해서는 병행성이 전제 되어야 함.
(ex. 다중처리 프로그래밍 위해서는 다중 프로그래밍이 되어있어야 함)
- 단일처리 - 논리적 병행성 (Logical Concurrency)
- 다중처리 - 물리적 병행성 (Physical Concurrency)
~> 이 두 경우 모두 프로세스가 병행하기 때문에 생기는 문제는 같으므로, 해결책 역시 같을 것!
- 병행 프로세스는 서로 간에 비동기적(Asynchronous)이다.
- 비동기적(Asynchronous)
: 프로세스들이 어떤 상태에 있는지, 어떤 자원을 가지고 있는지, 어디까지 실행됐는지 등에 대해 모른 체 실행되고 있음을 의미
5.1 병행 프로세스 (Concurrent Process)
- 병행(concurrent) = 함께 있는 것
- 비동기적(Asynchronous) = 서로 정보 모르는 것
ㄴ 서로 공유된 자원이 없다면, 문제 X (독립적)
서로 공유된 자원이 있다면, 일정한 Rule 따라야 함.
= “한 번에 한 프로세스만이 접근하도록 하고,
해당 자원에 대해 의도했던 실행을 완료하도록 보장한다.”
*다중처리 시스템의 경우, 두 프로세스가 동시에 실행될 수 있으므로
둘다 각자의 실행 결과를 저장하게 될 것이고,
결국 변수의 최종값은 조금이라도 늦게 저장하는 프로세스의 결과값이 될 것이다.
*단일처리 시스템의 경우, 조작도중 CPU가 넘겨지더라도 조작 허용을 하지 않아야 한다.
5.2 상호배제 (Mutual Exclusion)
- Race Condition (경쟁상태)
: 프로세스들이 공유 데이터에 대해 서로 접근을 시도하는 상황
→ <문제>
- 상호배제 (Mutual Exclusion) →이번 장
- 교착상태 (Deadlock) → 다음 장
- 기아 (Starvation) → 다음 장
- 임계자원 (Critical Resource): 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원
- 임계영역 (Critical Section): 임계영역에 대해 접근하고 실행하는 프로그램 내의 코드부분
⇒ 상호배제 (Mutual Exclusion): 한 번에 하나의 프로세스만이 임계영역에 들어가야 함.
(★=critical section에 대한 action은 전부 mutual exclusion을 해주어야 한다.)
<상호배제를 실현하기 위한 필요조건(원칙)>
- 상호배제 O
- 임계영역 X 프로세스가 다른 프로세스의 임계영역 진입을 막으면 X
- 비어있는 임계영역 진입 바로 허용
- 특정 프로세스의 진입시도가 계속 무산되어 기아를 겪지 않도록
<임계영역 진입 순서>
- 임계영역 진입할 때(enter primitive): 임계영역 내 다른 프로세스 존재 확인
ㄴ 확인한 후 있다면 기다리고, 없다면 들어가면서 자신이 나올 때까지 다른 프로세스가 들어오지 못하도록 함
- 임계영역 나올 때(exit primitive): 자신이 나오는 사실을 알려 다른 프로세스가 들어올 수 있도록!
⇒ 이것들을 어떻게 잘 구현(코딩)느냐가 상호배제의 성공여부 결정!
* 운영체제가 다양한 경우마다 구체적인 모든 내역을 파악하여 알아서 상호배제를 해주기가 어렵다.
- 공유 자원에 대한 상호배제의 의무는 일반적으로 프로그래머 책임
- 운영체제는 사용자의 상호배제 구현을 지원하기 위한 도구를 제공
예) 세마포어, 모니터
5.3 상호배제를 위한 소프트웨어 기법들
- 소프트웨어 기법들은,
운영체제의 지원 없이 프로세스들 간에 자신의 프로그램에서
임계영역 앞뒤로 적절한 코딩을 해줌으로써 상호배제를 해결하는 방식
(이 과정에서 CPU를 낭비할 수도, 프로그래머의 실수로 인한 오류가 생길 수도…)
● parbegin/parend 구조 (=cobegin/coend 구조)
parbegin
statement_1;
statement_2;
. . .
statement_n;
parend
: parbegin과 parend 사이 존재하는 n개의 문장들이 동시에 수행 가능
⇒ 이 구조에서 n개의 문장들의 나열 순서는 아무 의미가 없다!
예) 단일처리기 시스템 - 각 문장의 수행 순서를 임의로 진행해도 된다.
다중처리기 시스템 - 각 문장을 병렬로 실행하겠다.
<★중요> 병행 프로세스 간의 실행 속도와 임계영역을 들어가려는 횟수의 차이는 얼마든지 날 수 O
5.3.1 몇 가지 미완성 시도들
제대로 된 프로그램은 프로세스 critical section에 대한 수행횟수에 제약이 있으면 안 된다. 그리고 프로세스들 사이 상대속도(시행속도)에 전혀 제약을 두어서는 안 된다.
- 첫 번째 시도
P0:
While (ture) do:
.
.
While (turn=1); /*do nothing*/
<critical section>; //turn 값이 0이면 임계영역 접근 가능
turn:=1;
.
.
endwhile;
P1:
While (ture) do:
.
.
While (turn=0); /*do nothing*/
<critical section>;
turn:=0;
.
.
endwhile;
Begin /*main*/
int turn=0;
parbegin
p0;
p1;
parend
End
<두 프로세스 사이의 상호베제를 위한 첫 번째 시도>
<문제점>
- turn의 초기값이 0으로 되어있으므로, 두 프로세스에서 임계영역의 첫 번째 진입이 고정되어있다.
⇒ 임계영역이 비어있을 경우, 진입을 원하는 프로세스를 방해해서는 안 된다는 원칙 위배
- 임계영역의 진입이 turn 값을 바꾸어줌으로써 가능하기에, p0과 p1은 정확하게 한 번씩 번갈아가며 진입이 가능하고 누구든 연속해서 두 번 이상 진입할 수 없다.
⇒ 프로세스 각자의 진입을 원하는 횟수는 얼마든지 다를 수 있으므로 상대적으로 많은 횟수의 진입이 요구되는 프로세스는 그 횟수만큼 상대 프로세스가 임계영역을 진입해주어야 함.
이것은 상태 프로세스가 먼저 종료될 경우에 자신도 더 이상 임계영역을 들어갈 수 없다는 문제 야기
& 상대적으로 실행 속도 느린 프로세스의 속도에 의존한다는 문제
- 두 번째 시도
boolean flag[0], flag[1];
void p0()
{
While (true)
{ .
.
While (flag[1]); /* do nothing */
flag[0]=true;
<critical section>;
flag[0]=false;
.
.
}
}
void p1()
{
While (true)
{ .
.
While (flag[0]); /* do nothing */
flag[1]=true;
<critical section>;
flag[1]=false;
.
.
}
}
void main()
{
flag[0]=false;
flag[1]=false;
parbegin
p0;
p1;
parend
}
<두 프로세스 사이의 상호베제를 위한 두 번째 시도>
<해결점>
-임계영역 최초 진입 제한 X
-상대적으로 많은 횟수의 진입이나 상대 프로세스가 먼저 종료되어도 진입 가능 O
<문제점>
-임계영역에 p0과 p1이 둘 다 존재할 가능성 有 (→ 상호배제 X)
- 세 번째 시도 : 위의 코드에서 flag[0]과 flag[1] 값을 모두 true로 변경.
<문제점>
-p0와 p1 모두 임계영역의 진입 불가능
5.3.2 성공적인 기법들
앞선 시도들의 경험을 바탕으로 flag와 turn 변수를 적절히 사용하여 두 프로세스 사이의 상호배제를 제대로 구현하였다.
● Dekker의 알고리즘
: Dekker의 알고리즘은 이해하기 어렵고 정확성을 증명하기 까다롭다 말해짐.
● Peterson의 알고리즘
: 간결하게 만들어진 Peterson의 알고리즘은 Dekker의 알고리즘의 단점을 해결하였음.
void p0()
{
While (true)
{
flag[0]=true;
turn=1;
While (flag[1]&&turn==1); /*do nothing*/
<critical section>;
flag[0]=false;
<remainder>;
}
}
<Peterson의 알고리즘>
5.3.3 n 프로세스 간의 상호배제를 위한 소프트웨어 기법들
: Dekker나 Peterson이 소개한 알고리즘들은 두 프로세스 사이의 상호배제를 해결한 것이지만, 실제로는 그보다 많은 다수의 프로세스들 사이에서의 상호배제가 요구될 가능성이 높다. 따라서, n개의 프로세스들을 대상으로 하는 상호배제 기법을 살펴보자.
● Dijkstra의 알고리즘
: 무한대기 발생 가능
● Knuth의 알고리즘
: 지연 시간이 커지는 단점
● Eisenberg와 Mcguire의 알고리즘
: 유한 시간 내에 임계영역으로의 진입 보장
● Lamport의 알고리즘 (=베이커리(Bakery) 알고리즘)
: 원래는 분산 시스템용으로 소개되었으나, n개의 프로세스들을 대상으로 하는 상호배제 기법으로도 유용
- 상호배제가 요구되는 n개의 프로세스에서 임의의 프로세스 i를 위한 프로그램
- 모든 number 값과 choosing 값은 0과 false로 초기화되어 있고, 임계영역의 진입을 원하는 프로세스 i는 먼저 number 값이 주어지는데 다른 프로세스들이 이미 받은 값보다 더 큰 값을 받게 된다.
- for문 안에서 첫 번째 while문은 번호 값을 받는 중인 프로세스가 있다면 그 값도 비교해야 하기 때문에 기다리는 것이며, 두 번째 while문에서 자신의 값이 가장 작을 때 임계영역의 진입이 허가되는 것
- 임계영역을 벗어난 후 자신의 값을 0으로 해줌으로써 차례를 기다리는 다른 프로세스들에게 임계영역의 진입 기회를 주게 되는데, 번호 값에 의해 차례가 정해지므로 특정 프로세스의 무한 대기는 걱정하지 않아도 된다.
do{
choosing[i]=true;
number[i]=max(number[0], number[1],...,number[n-1])+1;
choosing[i]=false;
for(j=0; j<n; j++)
{
while (choosing[j]);
while ((number[j]!=0)&&((number[j],j)<(number[i],i)));
}
<critical section>;
number[i]=0;
<remainder>;
} while(1);
<Lamport의 베이커리 알고리즘>
⇒ 지금까지 설명한 소프트웨어 기법들은 운영체제의 특별한 지원 없이, 프로세스 간 협력을 통해 상호배제를 실현하는 것이므로 실행시의 부하가 크며, 실수도 인한 오류의 가능성도 높다.
*바쁜 대기(Busy Wait) 또는 스핀락(Spinlock)
: 임계영역의 중복을 막기 위해 while문을 계속 맴돌며 CPU를 낭비하는 것
*동기화(Synchronization) (=“차례대로”의 의미)
: 임계영역에 대한 실행 “한 번에 한 프로세스만 하도록” 하는 것
5.4 상호배제를 위한 하드웨어 기법들
5.4.1 인터럽트 금지를 사용한 기법
단일처리 시스템의 경우, CPU를 뺏기지 않도록 하면 상호배제 가능!
⇒ 즉, 시간 종료나 우선순위 등에 의해 CPU를 뺏길 수 있는 인터럽트를 임계영역의 실행을 완료할 때까지 발생하지 않도록 하면 된다.
<장점>
- 간단하게 구현 가능
<단점>
- 임계영역의 처리 동안 모든 종류의 인터럽트를 금지해
시스템의 효율적 운영 방해 가능성 多
- 다중처리 시스템에서는 해결 X (인터럽트 금지는 처리기 단위이기 때문)
While (true) do
.
.
Interrupt Disable;
<critical section>;
Interrupt Enable;
.
.
endwhile;
<인터럽트 금지를 사용한 상호배제>
5.4.2 하드웨어 명령어를 사용한 기법
기본적으로 하드웨어 자체는 특정 메모리 주소에 대한 접근을 한 번에 하나의 요청으로 제한하고 있다. 메모리의 같은 위치에 대한 읽기와 쓰기, 또는 읽기와 검사와 같은 일을 한 명령어 사이클 동안 처리해주는 명령어가 있다면, 이런 종류의 기계명령어는 다른 접근 요청이 차단된 가운데, 원자적(Atomic)으로, 실행 동안 끊기지 않고(Indivisible) 완료될 수 있다.
- 기계명령어로 잘 알려져 있는 testandset과 exchange(=swap) 명령어
boolean testandset(boolean &target)
{
boolean rv=target;
target=true;
return rv;
}
void exchange (boolean &r, boolean &m)
{
boolean temp=r;
r=m;
m=temp;
}
<testandset과 exchange 명령어>
- 이해를 돕기 위해 함수 또는 프로시저의 형식으로 표현되어 있으나, 실제로는 기계명령어로서 원자적으로 실행 도중 끊김 없이 완료되는 연산이다.
const int n=...; /* 프로세스 개수 */
boolean lock;
void P(int i);
{
while(true)
{
while(testandset(lock));
<critical section>;
lock:=false;
<remainder>;
}
}
void main()
{
lock:=false;
parbegin
P(1), P(2),...,P(n);
parend;
}
(a)
const int n=...; /* 프로세스 개수 */
boolean lock;
void P(int i);
{
while(true)
{
key:=true;
while(key=true) do exchange(key, lock);
<critical section>;
lock:=false;
<remainder>;
}
}
void main()
{
lock:=false;
parbegin
P(1), P(2),...,P(n);
parend;
}
(b)
<testandset과 exchange를 사용한 상호배제>
<장점>
- 간단하고, 다중처리 시스템에서도 쉽게 사용 가능
- 한 프로그램 내에서 서로 다른 변수를 사용하여 여러 개의 임계영역도 지원할 수 있음
<단점>
- 여전히 바쁜 대기를 함
- 차례가 정해지지 않아, 기아를 겪을 수도 있음
- 임계영역 실행 중 높은 우선순위의 프로세스에게 CPU를 뺏길 경우, 교착 상태 빠질 수 있음
5.5 세마포어(Semaphore)
- Dijkstra가 1965년에 제안한 개념인 세마포어는 세 개의 특수한 명령들만 접근할 수 있게 허용되는 보호된 변수로서, 앞서 다루었던 것들보다 더 높은 수준에서 상호배제를 구현 가능
- 세마포어는 그 변수가 가질 수 있는 값의 범위에 따라,
- 이진(Binary) 세마포어: 이진값 (0 또는 1)
- 계수(Counting) 혹은 정수(Integer) 세마포어: 음이 아닌 모든 정수
- 세마포어를 위한 특수한 명령들 = 비분리(Indivisible) 명령들
: 세마포어 값을 초기화하는 명령, P 명령, V 명령
- P 명령: wait 또는 down 이라는 이름을 사용하기도 함
- V 명령: signal 또는 up 이라는 이름을 사용하기도 함
- 책들에 따라 초기화 명령을 따로 두지 않고 Semaphore 변수로 선언한 다음 초기 값을 부여하는 방식을 쓰기도 하고, P와 V 명령은 각각 wait와 signal 또는 down과 up이라는 이름으로 사용하기도 한다.
- P(S): if (S>0) then S = S - 1;
- **else** S > 0 조건이 만족될 때까지 큐에서 대기;
- V(S): if (큐에서 대기 중인 프로세스들이 존재)
- **then** 그 중의 한 프로세스를 준비 또는 실행 상태로 만듦; **else** S = S + 1;
- P 명령은 S값이 0보다 크면 단순히 S값을 1 감소시키는 작업을 하지만, 그렇지 않으면 S값이 0보다 크게 되기를 기다리게 된다.
- V 명령에서는 S가 0보다 크게 되기를 기다리는 프로세스가 있으면, 그들 중 하나의 프로세스가 수행되고, 만약 그러한 프로세스가 존재하지 않는다면 단순히 S의 값을 1만큼 증가시키는 작업만 한다.
- 세마포어에 대한 명령들은 각각 분리되지 않고 수행될 수 있도록 구현해야 하며, 같은 세마포어에 대해서는 동시에 시행될 수 없다.
const int n= /* 프로세스의 수*/;
semaphore s=1;
void p(int i)
{
while (true)
{
P(s);
<critical section>;
V(s);
<remainder>;
}
}
void main()
{
parbegin
p(1), p(2),...,p(n);
parend
}
<세마포어를 사용한 상호배제>
⇒ P와 V 명령의 정의에 따라 한 번에 하나의 프로세스만이 임계영역에 들어갈 수 있음을 알 수 있다.
- 세마포어는 동기화(Synchronization), 상호배제(Mutual Exclusion), 자원관리(Resource Management)까지 활용 범위가 넓다.
예) 상호배제→위의 <세마포어를 사용한 상호배제> 코드
자원관리→프린트 풀(Pool)
동기화=”서로를 의식하고 실행의 보조를 맞추다.”
→ P0는 P1이 데이터를 생성하여 주면 받아 계속 실행을 하는 경우
- 세마포어는 시스템에서 바로 주어지는 도구가 아닐 경우가 많다. 결론적으로 말하면, 쓰임새는 많지만, 세마포어를 선언할 수 있는 상황이 아니거나 P,V라는 operation을 사용할 수 없는 상황이라면 이것을 다른 도구를 사용하여 impliment 해야 한다.
'CS > 운영체제' 카테고리의 다른 글
| Chapter 07 메모리 관리 (0) | 2023.05.26 |
|---|---|
| Chapter 6. 교착 상태(Deadlock) (0) | 2023.05.22 |
| Chapter 4. CPU 스케줄링 (1) | 2023.04.12 |
| Chapter3. 프로세스와 스레드 (0) | 2023.04.07 |
| Chapter2. 들어가기 전에 (인터럽트, I/O 방식) (0) | 2023.03.22 |