정의\
Critical Section은 (임계구역 또는 공유변수 영역) 병렬프로그래밍에서 둘 이상의 스레드 (멀티스레드)가 동시에 접근해서는 안되는 공유 자원(파일, 입출력, 공유 데이터 등) 을 접근하는 명령문 또는 코드의 일부 영역을 말합니다.
Race condition의 정의\
두 개 이상의 프로세스가 공통 자원을 병행적으로(concurrently) 읽거나 쓰는 동작을 할 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황을 말한다. Race의 뜻 그대로, 간단히 말하면 경쟁하는 상태, 즉 두 개의 스레드가 하나의 자원을 놓고 서로 사용하려고 경쟁하는 상황을 말한다.
이런 Race condition은 3가지 문제를 직면한다.
1. Mutual exclusion
2. DeadLock
3. Starvation
정의\
특정 프로세스가 공유 자원을 사용 중일 때 다른 프로세스가 이 자원에 접근하지 못하도록 막는 것을 의미한다. 그러니까, 공유를 하면 안되는 자원(Resource)의 동시 사용을 피하는 방법 중 하나이다.
while(1) {
flag[i] = true; // 프로세스 i가 임계영역 진입을 시도한다.
while(flag[j]) { // 프로세스 j가 현재 임계영역에 있는지 확인한다.
if(turn == j) { // 프로세스 j가 임계영역을 사용 중이라면
flag[i] = false; // 프로세스 i의 진입을 취소하고,
while (turn == j); // turn이 j에서 바뀔 때 까지 기다린다...
flag[i] = true; // 임계영역에서 j가 나오면 재진입을 시도한다.
}
}
/* critical section */
turn = j; // 임계영역의 사용이 끝나면, turn을 넘긴다
flag[i] = false; // 진입 flag값을 false로 바꾸어 임계영역 사용 완료를 알린다.
...
}
Flag와 Turn 이라는 변수로 임계영역에 들어갈 프로세스를 결정하는 알고리즘으로 turn을 통해 내 차례 라면 들어 가는 알고리즘이다.
장담점
while(1){
flag[i] = true; // 프로세스 i가 임계영역 진입시도
turn = j; // 다른 프로세스에 진입기회를 양보
while(flag[j] && turn == j);
/* critical section */
...
flag[i] = false; //임계영역 사용완료
...
}
Dekker와 비슷하지만 먼저 다른 프로세스를 확인 하고 기다린다는 점에서 조금 다르다.
장단점
while(1){
choosing[i] = true;
number[i] = max(number[0] ... number[n-1]) + 1
choosing[i] = false;
for(int j = 0; j <= n-1; j++) {
while(choosing[j]);
while(number[j] != 0 &&((number[j],j)<(number[i],[i])));
}
/* critical section */
...
number[i] = 0;
...
}
위 두 알고리즘과 다르게 여러개의 프로세스나 쓰레드의 대한 처리가 가능하다.
가장 작은수의 번호표를 가지고 있는 프로세스가 임계영역에 진입한다.
장단점
정의\
신호기, 깃발을 의미하며 각 프로세스에 제어 신호를 전달하여 순서대로 작업하도록 하는 기법.\
세마포어의 값에 따라 운영체제는 프로세스가 즉시 자원을 사용할 지, 자원이 다른 프로세스에 의해 사용 중인걸 알게 될 경우엔 일정 시간을 기다려야 한다.
- 공유자원의 상태를 나타낼 수 있는 카운터로 생각할 때,
- 사용하고 있는 스레드/프로세스의 수를 공통으로 관리하는 하나의 값을 이용해 상호배제를 달성한다.
- 운영체제 또는 커널의 한 지정된 저장장치 내의 값
- 일반적으로 비교적 긴 시간을 확보하는 리소스에 대한 이용
- 유닉스 프로그래밍에서 세마포어는 운영체제의 리소스를 경쟁적으로 사용하는 다중 프로세스에서 행동을 조정하거나 또는 동기화하는 기술
- 공유 자원에 접근할 수 있는 프로세스의 최대 허용치만큼 동시에 사용자가 접근할 수 있다.
- 각 프로세스는 세마포어의 값을 확인하고 변경할 수 있다.
- 자원을 사용하지 않는 상태가 될 때, 대기하던 프로세스가 즉시 자원을 사용한다.
- 이미 다른 프로세스에 의해 사용중이라는 사실을 알게 되면, 재시도 전에 일정시간 대기해야 한다.
- 세마포어를 사용하는 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에는 그 값을 변경함으로써 다른 세마포어 사용자들이 대기하도록 해야 한다.
- 마포어는 이진수를 사용하거나 추가적인 값을 가질 수 있다.
...
P(s);
/* critical section */
V(s);
...
P(Semaphores){
while(S==0);
s = s - 1;
}
V(Semaphores){
s = s + 1;
}
명심\
P - Critical section - P : 교착 상태 발생\
V - Critical section - P : mutex exclusion을 보장할 수 없다.
mutex는 semaphore와 비슷하다.
여러 쓰레드가 접근하는 것을 막고 오직 하나의 쓰레만 접근하게 하는데, 0 or 1의 값을 가지는 이진 세마포어랑 유사하게 동작한다.
가장 큰 차이점은 동기화 대상의 개수이다.
어떤 공유 데이터에 대해 모니터를 지정해놓으면, 프로세스는 그 데이터에 접근하기 위해 모니터에 들어가야만 한다. 즉, 모니터 내부에 들어간 프로세스에게만 공유 데이터를 접근할 수 있는 기능을 제공하는 것이다. 또한, 프로세스가 모니터에 들어가고자 할 때, 다른 프로세스가 모니터 내부에 있다면 입장 큐에서 기다려야 한다
배타동기의 queue는 하나의 스레드만 공유자원에 접근할 수 있게 하는 작용을 하는 공간이다. 특정 스레드가 공유자원을 사용하는 함수를 사용하고 있으면 다른 스레드는 접근을 할 수 없고 대기해야 한다.
조건 동기의 queue는 진입 스레드가 블록되면서 새 스레드가 진입가능하게 하는 공간이다. 새 스레드는 조건동기로 블록된 스레드를 깨울 수 있다. 깨워진 쓰레드는 현재 쓰레드가 나가면 재진입할 수 있다.
정의\
프로세스가 CPU자원의 할당을 무한히 대기하는 것을 말한다. 특히 기아상태는 CPU 스케줄링과 밀접한 관련이 있다.
해결책