Processes Synchronization or Synchronization is the way by which processes that share the same memory space are managed in an operating system.
- 동기화 : 공유되고 있는 변수를 사용해 한 프로세스가 작업을 하고 있을 때, 다른 프로세스가 그 변수 이용이 끝나기 전까지 사용하는 것을 막아주는 것. 즉 상호배제의 한 방법
race condition
경쟁 프로세스의 경우, 세 가지 제어 문제에 직면한다.
Mutual exclusion, deadlock, starvation이다.
P1(1), P2(1), P2(2), P2(3), P1(2), P1(3)
Final value of count = 6
P2(1), P1(1), P1(2), P1(3), P2(2), P2(3)
Final value of count = 4
P1(1), P1(2), P2(1), P2(2), P1(3), P2(3)
Final value of count = 4
교착상태(DeadLock) : 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 아무것도 완료되지 못하는 상태
- 교착 상태의 조건 : 아래 4가지 조건을 모두 충족시켜야 함
- 상호배재 : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.
- 점유대기 : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
- 비선점 : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.
- 순환대기 : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.
- 해결 방안
- 예방 : 교착 상태 발생 조건 중 하나를 제거하면서 해결(자원 낭비 심함)
- 회피 : 교착 상태 발생 시 피해나가는 방법 (ex. 은행원 알고리즘)
- 탐지 : 자원 할당 그래프를 통해 교착 상태를 탐지(그에 대한 오버헤드 발생함)
- 회복 : 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
기아상태(Starvation) : 특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태
- 해결 방안
스케줄링으로 해결 (우선 순위를 변경해준다.)
ex ) 라운드 로빈 스케줄링 : 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위로 CPU 할당
Critical Section
Critical section is a section of the program where a process access the shared resources during its execution.
- 임계구역 : multi thread 시스템에서 쓰레드가 공통의 변수를 바꾸거나, table을 업데이트하거나 파일에 써서 생기는 코드의 한 부분. 즉 공유 자원에 접근하는 코드의 영역을 말한다.
Requirements of Synchronization mechanisms
1) 상호배제(Mutual exclusion) : 특정 프로세스가 임계영역 내에서 실행중일 때, 다른 프로세스는 임계영역에 들어갈 수 없다.
2) 진행(progress) : 임계영역를 진행 중인 프로세스가 없을 경우에, 임계영역에 진입을 요구할 경우 유한한 시간내에 진입해야한다. 정당한 진입 프로세스를 막으면 안된다.
3) 한정된 대기(bounded waiting) : 임계영역에 대한 진입의 요청을 했을 경우, 무한히 기다리지 않고 유한한 시간내에 진입해야한다.
Solutions To The Critical Section Problem
Most solutions to the critical section problem utilize locks implemented on software.
1) 뮤텍스(Mutex)
- 임계구역을 보호하고 Race Condition을 방지하기 위한 기법으로, Mutual Exclusion 의 약자.
- 임계 구역에 들어가기 전에 반드시 Lock을 획득 해야하고, 임계영역을 나올 때 Lock을 반환.
- 2진 세마포어 기법, Locking 기법 으로도 불리운다.
2) 세마포어(Semaphore)
- 각 프로세스에 제어 신호를 전달하여 순서대로 작업을 수행하도록 하는 기법.
- S라는 정수 변수를 사용하여 wait()과 signal()로만 접근이 가능하다. 변수 S의 크기만큼 동시 접근이 가능한 개수를 의미하며, 어떤 쓰레드/프로세스도 이 값을 변경할 수 없다.
- 자원을 사용하려는 프로세스는 wait()연산(P연산이라고도 불림)을 수행하여 S 값을 감소 시키고, 자원의 사용이 끝날때 signal()연산(V연산)을 수행하여 세마포어 값을 증가시킨다.
- S의 값은 동시에 변경될 수 없다.
Semaphore
공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 여러 Process 혹은 Thread가 접근하는 것을 막아줌 (동기화 대상이 하나 이상)
Semaphores can be used for task synchronization and mutual exclusion.
세마포어 P, V 연산
P : 임계 구역 들어가기 전에 수행 ( 프로세스 진입 여부를 자원의 개수(S)를 통해 결정)
V : 임계 구역에서 나올 때 수행 ( 자원 반납 알림, 대기 중인 프로세스를 깨우는 신호 )
P(S);
// --- 임계 구역 ---
V(S);procedure P(S) --> 최초 S값은 1임
while S=0 do wait --> S가 0면 1이 될때까지 기다려야 함
S := S-1 --> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함
end P
--- 임계 구역 ---
procedure V(S) --> 현재상태는 S가 0임
S := S+1 --> S를 1로 원위치시켜 해제하는 과정
end V- 먼저 도착한 A가 P(S)를 실행하여 S를 0으로 만들고 임계구역에 들어감
- 그 뒤에 도착한 B가 P(S)를 실행하지만 S가 0이므로 대기 상태
- A가 임계구역 수행을 마치고 V(S)를 실행하면 S는 다시 1이 됨
- B는 이제 P(S)에서 while문을 빠져나올 수 있고, 임계구역으로 들어가 수행함
Mutex
공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 하나의 Process 혹은 Thread가 접근하는 것을 막아줌 (동기화 대상이 하나)
- lock : 현재 임계 구역에 들어갈 권한을 얻어옴 ( 만약 다른 프로세스/스레드가 임계 구역 수행 중이면 종료할 때까지 대기 )
- unlock : 현재 임계 구역을 모두 사용했음을 알림. ( 대기 중인 다른 프로세스/스레드가 임계 구역에 진입할 수 있음 )
데커(Dekker) 알고리즘
flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식
flag : 프로세스 중 누가 임계영역에 진입할 것인지 나타내는 변수
turn : 누가 임계구역에 들어갈 차례인지 나타내는 변수
while(true) {
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 turn이 끝나면 다시 진입 시도
}
}
}
// ------- 임계 구역 ---------
turn = j; // 임계 구역 사용 끝나면 turn을 넘김
flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림피터슨(Peterson) 알고리즘
데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있음
while(true) {
flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
turn = j; // 다른 프로세스에게 진입 기회 양보
while(flag[j] && turn == j) { // 다른 프로세스가 진입 시도하면 대기
}
}
// ------- 임계 구역 ---------
flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림제과점(Bakery) 알고리즘
여러 프로세스/스레드에 대한 처리가 가능한 알고리즘. 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입한다.
while(true) {
isReady[i] = true; // 번호표 받을 준비
number[i] = max(number[0~n-1]) + 1; // 현재 실행 중인 프로세스 중에 가장 큰 번호 배정
isReady[i] = false; // 번호표 수령 완료
for(j = 0; j < n; j++) { // 모든 프로세스 번호표 비교
while(isReady[j]); // 비교 프로세스가 번호표 받을 때까지 대기
while(number[j] && number[j] < number[i] && j < i);
// 프로세스 j가 번호표 가지고 있어야 함
// 프로세스 j의 번호표 < 프로세스 i의 번호표
}
}
// ------- 임계 구역 ---------
number[i] = 0; // 임계 구역 사용 종료ref
https://kelvin.ink/2018/10/27/IPC_and_Synchronization/
https://scrutinybykhimaanshu.blogspot.com/2019/08/all-about-java-semaphore.html
https://www.guru99.com/mutex-vs-semaphore.html
https://iredays.tistory.com/125
https://prepinsta.com/operating-systems/deadlock-avoidance-and-prevention/
https://www.scaler.com/topics/operating-system/process-synchronization-in-os/
