- 공룡책 10판(Operating System Concepts 10th)과 수업 내용을 참고로 한 내용 정리이다.
- 정리 목적 그리고 배우는 입장의 포스팅이기에 잘못된 내용이 있을 수 있다.
FCFS(First-Come, First-Served), FIFO
- Non-preemptive 즉 비선점형 스케줄링 알고리즘이다.
- NO starvation: 프로세스가 시스템에 들어온 순서대로 처리하기 때문에 계속 우선순위가 밀려 자원을 할당 받지 못하는 현상은 없다.
문제점
- 자원을 할당받기 위한 평균 대기 시간이 상당히 길어질 수 있다.
- I/O와 CPU의 overlap이 좋지 못하다.(주로 CPU 자원을 많이 사용하는데 둘을 동시에 사용하는 것이 가장 효율적)
-
Convoy effect: 들어온 순서대로 처리하다보니 긴 프로세스가 앞에 있을 경우 뒤따르는 작은 프로세스들에게 긴 대기시간을 주는 비효율적인 상황이 발생한다.
SJF(Shortest Job First)
짧은 CPU burst를 가진 가장 작은 프로세스부터 처리하는 것이다.
- Non-preemtive: FCFS와 마찬가지로 비선점형 방식이다.
문제점
-
Starvation
짧은 작업의 프로세스를 우선적으로 처리하다보니 긴 작업의 프로세스는 계속해서 서비스를 받지 못하게 되는 현상이 일어난다. -
비현실성
현재 우리가 사용하는 컴퓨터에 적용되기에는 비현실적이다.
SRT(Shortest Remaining Time First), SJF의 preemptive 버전
새로운 프로세스가 들어왔을 때, 만약 기존에 처리 중이던 프로세스의 잔량 시간보다 더 짧은 CPU burst를 요구할 경우 선점하여 새로운 프로세스에게 CPU 자원을 할당하는 방식이다.
RR(Round Robin)
Time sharing, preemptive한 방식이다.
RR 방식은 프로세스의 요구 자원의 크기와 관계없이 설정된 Time Quantum 만큼 CPU 자원을 할당하고 시간이 충족되면 큐의 가장 뒤로 보내고 다음 프로세스에게 자원을 할당하는 방식이다.
-
No starvation: 우선순위가 없고 항상 프로세스를 항상 균등하게 자원 배분을 해주기 때문에 기아 현상이 발생하지 않는다.
-
Turnaround time의 증가: waiting time이 늘어나게 되면서 turnaround time이 증가하는 경향을 보인다. Turnaround time = CPU burst + Waiting time
-
Response time의 감소: SJF에 비해 평균적으로 높은 turnaround time 하지만 Response time은 빠르다. 이는 차별없이 균등하게 time quantum을 배분하기 때문이다.
RR 방식에서의 중요한 부분은 Time Quantum의 길이에 따라 context switching 횟수가 변하여 오버헤드에 영향을 미치기 때문에 이를 잘 조절하는 것이 중요하다.(Time quantum이 길다 = turnaround time 감소 = overhead 감소 = Response time 증가) –> 결국에 완벽한 스케줄링 알고리즘은 존재하지 않는다.
Priority Scheduling(우선순위 스케줄링)
우선순위 스케줄링이란 단어 그대로 프로세스에 우선순위를 부여하여 실행되게 하는 것이다. 앞에서 언급한 SJF도 우선순위 스케줄링으로 짧은 CPU burst를 가진 프로세스에게 우선순위를 높게 부여하고 CPU burst가 큰 프로세스에게는 낮은 우선순위를 부여하는 것이다. 반면 RR 방식이나 FCFS 방식은 비교적 공평한 자원분배를 한다고 할 수 있다.
우선순위 스케줄링의 문제점과 그 해결법
우선순위 스케줄링은 기아 현상을 초래하는데 당연한 얘기지만 낮은 우선순위를 가진 프로세스는 계속 그 순번을 밀려 CPU 자원을 할당받지 못하는 현상을 보인다.
이를 해결하기 위해 Aging 방식을 고안해냈는데, 이는
- 대기 시간이 길수록 우선순위를 높이고
- CPU를 할당받은 시간이 길수록 우선순위를 낮춘다 이를 통해 우선순위를 유동적으로 변경시켜 프로세스가 외면되는 일이 없도록 하는 해결법이다.
Multilevel Queue(다단계 큐)
다단계 큐란 높은 우선순위부터 낮은 우선순위까지 여러 단계의 큐를 두어서 스케줄링하는 방식이다.(모든 프로세스를 하나의 큐에서 관리하는 것보다 여러 개의 큐로 관리하는 것이 더 효과적일 수 있다.) 특히 이 방식은 우선순위 스케줄링과 RR 스케줄링이 결합된 경우 매우 좋은 효율을 보여준다.
간단히 설명하자면 위 그림에서 우선순위가 가장 높은 큐에 있는 프로세스들 중에 RR 방식을 따라 순서를 정해 실행된다.
예시로 Interactive process Queue(Foreground)는 batch process Queue(Background)에 절대적인 우선순위를 가진다(이유는 Foreground는 I/O bound job이 많고 Background는 CPU bound job이 많기 때문에)
그러므로 CPU를 독점하지 않는 큐에 우선순위를 주어 효율을 높이고 반대로 CPU을 많이 잡아먹는 큐에는 더 적은 CPU를 배분함으로써 자원을 활용도를 높인다.
문제점
- 하지만 프로세스가 항상 I/O bound job일지 아니면 시간이 지남에 따라 CPU를 많이 잡아먹는 프로세스가 될지는 아무도 모른다.(I/O를 하다 연산을 미친듯이 한다던지..)이러면 결국에 낮은 우선순위에서의 Starvation이 일어나게 된다. –> 이를 해결하기 위해 우선순위를 재배치하는데 이 방식을 Multilevel Feedback Queue라고 한다.(바로 다음에 설명)
Multilevel Feedback Queue(다단계 피드백 큐)
다단계 피드백 큐는 우선순위 별로 큐를 두어 그 안에서 RR을 하는 방식이었던 다단계 큐와는 달리, 상태가 좋지 않으면(CPU를 너무 많이쓰는 프로세스들) demotion 즉 우선순위를 강등하고 CPU를 짧게쓰고 I/O를 많이하는 프로세스들은 높은 우선순위로 올려준다(User interactive한 I/O bound)
고려 사항
- 큐의 개수는 몇 개로 만들 것인지?
- 스케줄링 알고리즘은 어떻게 적용시킬 것인지?(대개 RR) - 상위 80% RR, 하위 20% FCSF
- 우선순위의 Promotion과 demotion
- 프로세스가 처음 왔을 때 어느 큐에 배정할 것인지?
예를 들면 time quantum이 8일 때, 계속 8을 꽉 채워서 사용하는 프로세스가 있으면 이는 CPU-bound일 확률이 높다.(I/O bound는 왠만해서 꽉 채워 사용하지 않음) 이를 지켜봤다가 계속 반복되면 우선순위를 밑으로 내린다. 반대로 반납하는 CPU가 많을 경우(할당된 time quantum보다 적게 사용 후 반납하고 I/O) I/O bound라고 판단하여 우선순위를 높여준다.
대충 생각해봐도 매우 복잡한 스케줄링 알고리즘이다.
다음 글에서는 동기화에 대해 쓰고 싶은데 글쓰기 너무 힘들고 오래 걸린다…
OS(Operating System) - Scheduling(스케줄링)