1. Synchronization
멀티 프로그래밍에서 공유 데이터에 동시 접근할 경우 데이터에 일관성이 깨지는 문제가 발생할 수 있습니다. 한 스레드에서 공유 데이터를 변경하던 도중 Context Switching이 발생하여 다른 스레드가 잘못된 공유 데이터를 참조하거나, 중복 업데이트가 일어날 수 있습니다. 이러한 문제를 해결하기 위해 동기화라는 개념이 나왔습니다.
- Critical Section : 동기화 문제가 발생하는 코드 영역
- Critical Section는 짧을 수록 좋습니다. 이유는 어떤 스레드가 해당 영역에 진입했다면 다른 스레드는 해당 영역을 진입하지 못하고 Critical Section에 진입한 스레드가 완료할 때까지 기다리기 때문입니다.
동기화 문제를 해결하기 위해서 아래 세 가지 조건을 모두 만족해야합니다.
- Mutual Exclusion : 어떤 프로세스가 Critical Section에 진입 했다면 다른 프로세스들은 Critical Section에서 실행될 수 없습니다.
- Progress : Critical Section에서 실행중인 프로세스가 없고 별도의 동작이 없는 프로세스들만 Critical Section 진입 후보에 참여할 수 있습니다.
- Bounded Waiting : Critical Section에 진입할 때 무작정 기다리는것이 아닌 Process가 기다리는데 한계가 있습니다.
2. Synchronization 해결법
[1] Semaphore
세마포어는 동시에 공유 데이터에 접근할 수 있는 프로세스의 갯수를 제어합니다. 예를 들어 107호 병실에 방문객용 의자가 5개가 있습니다. 간호사는 이 병실에 방문자가 5명만 들어갈 수 있도록 허용하고 나머지 방문객들은 밖에서 대기하도록 합니다. 이후 병실의 방문자가 나가면 대기하고 있던 방문자가 병실로 입실합니다. 이렇게 카운터 갯수만큼 공유자원에 접근할 수 있는 방식을 의미합니다.
counter = n; // 가용 갯수 초기화
wait(S) {
while(counter <= 0) {} // 가용 갯수를 모두 사용했다면 대기
counter--; // 가용 갯수 감소
}
signal(S) {
counter++;
}
// CPU를 활용한 lock, unlock 매커니즘counter = n; // 가용 갯수 초기화
wait(S) {
counter--;
if(counter < 0) {
P.status = "wait"
list.push_back(P);
}
}
signal(S) {
counter++;
if(counter<=0) {
P = list.pop_back();
P.status = "ready";
}
}
// Process Status를 활용한 lock, unlock 매커니즘[2] Mutex
Locking 매커니즘을 활용하여 공유 데이터에 접근을 제어합니다. 예를 들어 카페의 공용 화장실은 누군가 화장실에 들어가 있으면 다른 사람들은 대기하고 있어야합니다. 이후 화장실에서 사람이 나와 키를 두고가면 다른 사람이 들어갈 수 있습니다. 즉, 열쇠를 가지고 있을 때만 공유 화장실에 접근할 수 있습니다.
flag = true; // 초기화
wait(S) {
while(!flag) {} // 누군가 Critical Section에 진입했다면 대기한다.
flag = false;
}
signal(S) {
flag = true;
}
// CPU를 활용한 lock, unlock 매커니즘
flag = true; // 초기화
wait(S) {
if(flag) {
flag = false;
}
else {
P.status = "wait";
list.push_back(P);
}
}
signal(S) {
flag = true;
if(!list.empty()) {
P = list.pop_back();
P.status = "ready";
}
}
// Process Status를 활용한 lock, unlock 매커니즘※ CPU 활용 -> Process State
초기 버전에서 대기하는 프로세스들은 반복 루프를 돌며 대기하여 CPU 리소스를 낭비합니다. 이를 Busy Waiting이라고 부릅니다.
따라서 다음 버전에서 프로세스의 상태를 활용했습니다. 대기하는 프로세스들을 Block 시킨 뒤 Critical Section에 진입이 가능하다면 다시 wakeUp하는 방식을 이용합니다.
3. Deadlock
프로세스들끼리 서로 자원을 가지고 있고, 다른 프로세스가 소유한 자원을 요구하면서 무한정 대기하는 상황을 말합니다.
이를 해결하기 위해서 OS는 문제가 생긴 사이클의 한 프로세스를 종료하거나, 문제가 생긴 모든 프로세스를 재시작하거나 무시한다. 사실 OS는 정확한 프로그램이기 보다는 프로그램들을 실행하는데 도움을 주는 역할이 크다. 즉, 데그락을 해결하는데 너무 많은 공을 들이면 OS가 가진 원래 목적과 맞지 않는다.
Deadlock 문제 발생 조건
Deadlock은 아래 4가지 조건을 모두 만족해야 발생합니다.
- Mutual Exclusion : 한 리소스는 하나의 프로세스만 사용 가능합니다.
- Hold and Wait : 다른 프로세스가 리소스를 소유하며 다른 프로세스가 가진 리소스를 기다립니다.
- No Preemption : 선점형으로 다른 프로세스가 소유한 리소스를 강제로 가져오지 못합니다.
- Circular wait : 프로세스가 리소스를 기다리는 일련의 사이클이 존재합니다. 기본적으로 사이클이 없다면 데드락도 존재하지 않습니다. 만약 사이클이 있다면 데드락이 존재할 수도, 존재하지 않을 수도 있습니다.
Deadlock 해결 방법
- 문제가 생긴 사이클의 모든 프로세스를 종료하고 재시작합니다.
- 무시합니다. 사실 OS는 정확한 프로그램이기 보단 프로그램을 실행하는데 도움을 주는 역할이 큽니다. 즉 데드락 문제를 해결하는데 너무 많은 공을 들이면 OS가 가진 원랙 목적과 맞지 않습니다.
- Queue를 활용하여 사이클을 해제합니다. 예를 들어, 1번부터 100번의 넘버링이 붙은 프로세스는 각각 자신의 넘버에 해당하는 리소스를 보유하고 있습니다. 이러한 상황에서 1번은 2번 리소스를, 2번은 3번리소스를 --- n번은 n+1번의 리소스를 요청하고 100번의 리소스는 1번의 리소스를 요청하는 상황을 가정해봅니다. 100번, 99번 --- 1번 순으로 큐에 넣습니다. 100번의 리소스를 Rollback시키고 queue에 제일 뒤로 다시 삽입합니다. 이후 99번 98번 --- 1, 100번 차례로 기능을 수행합니다.
