운영체제 (10) - CPU scheduling
CPU scheduling
중요한 주제가 나왔습니다. 바로 CPU scheduling입니다.
왜 중요한가?
실행중인 프로그램인 프로세스는 일련의 instruction으로 구현되어 있습니다. 또한, I/O 작업(I/O burst) 과 CPU가 instruction을 수행하는 것(CPU burst)은 분리되어 있다는 것을 기본 전제로 깔고 갑니다. 옛날에는, 메모리의 용량이 매우 부족했습니다. 하지만 현대 메모리는 어떤가요? 요즘 최소 단위가 GB단위입니다. 메모리의 용량이 늘어남에 따라, 당연히 현대 컴퓨터는 멀티 프로그래밍 기반으로 작동합니다. context-switching이라는 overhead를 감수하면서도 당연히, 멀티 프로그래밍이 성능이 훨씬 좋음을 우리는 압니다. 멀티 프로그래밍이 발달함에 따라, 당연히 CPU가 어떤 프로세스를 먼저 작업해야 하는가에 대한 CPU scheduling도 발달했습니다.
Preemptive and Nonpreemptive Scheduling
scheduling algorithm을 알아보기에 앞서 scheduling은 Preemptive(선점형)과, Nonpreemptive(비선점형)으로 나뉩니다. 선점형 스케줄링은 어떤 프로세스가, 다른 프로세스를 제어할 수 있는 방식입니다. 어떤 프로세스는 바로 운영체제입니다.
Nonpreemtive Scheduling
비선점형 스케줄링은 하나의 프로세스가 끝나거나, 스스로 기다림을 자처하는 상황을 제외하면, context-switching을 끝날 때 까지 하지 않는 스케줄링 기법을 말합니다. 비선점형 스케줄링은 context-switching을 많이 하지 않기에, overhead가 적지만 크나큰 단점이 있습니다. 바로 사용자 임의 process에게 CPU 사용 순서를 위임한다는 점입니다.
어떤 뜻인지 알아보기에 앞서, 예시를 하나 살펴봅시다. 한 프로세스가 CPU에 할당됩니다. 만약 무한 루프와 같은 프로세스라고 생각해봅시다. 비선점형 scheduling을 한다면, 끝나지 않는 무한 루프 프로세스를 계속 CPU가 독점합니다. 즉, 프로세스가 자신의 의지대로 CPU를 차지한다면 다른 프로세스가 굶는(starving) 현상이 발생합니다.
Preemptive scheduling
preemptive(선점형) scheduling을 자세하게 살펴보자면, 한 process가 CPU에 할당되면, 할당된 프로세스는 운영체제의 스케줄링 알고리즘에 의해 적절히 context-switching됩니다. 이는 overhead가 생길 수 있지만, 사용자 process를 운영체제가 적절히 제어함으로써, 안정성을 높일 수 있습니다. 이는 멀티프로세싱으로 동시에 시스템이 실행되어 보이게 하는 시분할 시스템에 적합합니다. 또한, CPU가 무한 루프에 빠지는 등의 문제에서 벗어나, CPU가 idle(유휴) 상태에 빠지는 것을 최대한 막을 수 있습니다. 이러한 선점형 스케줄링은, hardware interrupt 혹은 프로세스별 timer를 두어 구현합니다. 어떤 프로세스가 있습니다. 이 프로세스는 매우 중요하고 자주 메모리에 할당되는 프로세스입니다. 운영체제가 이렇게 중요한 프로세스에 CPU를 오랜 시간이 지난 후 할당하면 문제가 됩니다. 따라서 현대 운영체제는 선점형 스케줄링 방식으로 다른 프로세스가 실행되다가, 이를 멈추고, 중요한 프로세스에 CPU를 할당해줍니다. 이에 따라, Ready queue에 존재하는 어떤 프로세스에 CPU를 할당할지 정하기 위해 scheduling algorithm이 발달하게 되었습니다.
scheduling Criteria
cpu scheduling이 발달한 당위성은 이해했습니다. 기준 없는 평가는 존재하지 않기에, 그렇다면 발달을 평가하는 기준(척도)에 대해 알아봐야 합니다. 프로세스들은 각자의 이유로 ready queue에서 cpu를 기다리고 있습니다. 프로세스가 기다리고 있는데, CPU가 놀면 당연히 안됩니다. 이렇게 CPU가 놀지 않고 얼마나 일하는지를 CPU utilization이라고 합니다. 또한, 단위 시간에 처리되는 프로세스의 양을 throughput이라고 합니다. throughput은 network에서도 많이 들어본 단어입니다. 이 두 지표를 최대화하는것이 CPU scheduling의 목표입니다. 기타 지표로, 언제 시작하고 언제 끝나는지 그 유격을 나타내는 지표를 turn around time이라고 합니다. 얼마나 ready queue에서 대기했는지 총 시간을 나타내는 지표를 waiting time이라 하고, 언제 queue에 도착해서 처음으로 실행되었는지, 즉 얼마나 첫 실행까지 기다렸는지를 response time이라 합니다. response time은 첫 시작까지 기다리는 시간이기에, 이는 현재 CPU scheduling이 얼마나 공정한지를 나타내는 척도가 됩니다.
scheduling algorithm
이제 scheduling algorithm에 대해 알아봅시다.
1
2
3
4
5
6
7
1. FCFS (First Come First Served, 선입 선처리)
2. SJF (Shortest Job First, 최단작업 우선)
3. SRTF (Shortest Remaining Time First, 최소 잔여시간 우선)
4. Priority Scheduling (우선순위 스케줄링)
5. RR (Round Robin)
6. MLQ (Multi-Level Queue, 다단계 큐)
7. MLFQ (Multilevel Feedback Queue, 다단계 피드백 큐)
정도로 나뉩니다. 하나하나씩 알아보도록 합시다.
FCFS (First Come First Served, 선입 선처리)
First Come First Served 방식입니다. 선입 선출이라는 의미지 않나요? 바로 queue(대기열)을 사용해서 먼저 온 process를 먼저 수행하는 방식입니다. 직관적인 방식입니다. 이는 비선점형 스케줄링 기법입니다. 근데 이 방식이 좋나요? 예시로 어떤 작업이 굉장히 오래 걸립니다. 유감스럽게도 이 작업이 제일 먼저 queue에 들어왔습니다. 그렇다면 이후 프로세스들은 1초가 걸리건, 0.1초가 걸리건, 지금 수행되는 프로세스를 기다려야 합니다.
오늘 카페에서 치즈 케이크를 시켜먹었습니다. 오랜만에 달달한 음식을 먹었습니다.
제가 먹은 치즈케이크입니다. 제가 54번였습니다. 케이크는 준비하는데 오래 걸리기에, 55번 손님의 아이스 아메리카노가 먼저 나왔습니다. 당연한 것이죠. 하나에 의해 병목 현상이 나타났다간, 다른 프로세스들이 오래 기다리고, 이는 user의 답답함을 느끼게 하기에 충분하다고 생각합니다. 즉, FCFS 방식은 앞 프로세스에 따라서, 평균 대기시간의 편차가 매우 커지고, 이는 CPU의 효율적인 이용이 불가능하다는 의미입니다.
마무리하며
쓰다보니, 호흡이 너무 길어지는 것 같습니다. 이쯤에서 마무리하고, 다음 포스팅에서 다른 알고리즘에 대해 살펴보겠습니다.