CPU Scheduling
multiprogrammed 에서 필수적이다. 멀티프로그래밍은 여러개의 프로세스가 메모리에 동시에 로드되어 있고 cpu가 선점해서 concurrent하게 실행하는것을 멀티프로그래밍이라고 한다.
멀티프로그래밍은 cpu가 속도가 빨라서 놀고있으니 이걸 줄이기 위해 time sharing을 해서 cpu utilization을 높이려는 목적을 가지고 있다.
- CPU burst(running) : 프로그램의 수행 중에 연속적으로 cpu를 사용하는 단절된 구간을 말한다. scheduling의 단위가 된다.
- I/O burst(waiting) : 프로그램의 수행 중에 I/O의 완료를 기다리며 블록되는 구간을 말한다.
- CPU bound : CPU burst 시간이 많다
- I/O bound : I/O burst 시간이 많다.
주로 I/O와 관련된 처리는 CPU burst가 짧고 우주항공과 같은 전문 분야에서 많은 연산이 사용되는 경우는 CPU burst가 길다.
CPU Scheduler
CPU를 어떤 프로세스에 할당해줄까 선택한다. 레디 상태에 있는 프로세스 중에서 cpu를 할당해줄 수 있다.
CPU Scheduling은 언제 일어날까?
- Running ->Ready
하드웨어 인터럽트에 의한 Preemptive Scheduling or Non-Premmptive Scheduling. - Running ->Waiting
스스로 CPU yield 함수 호출에 의해 Waitng 상태로 전환. Non-Premmptive Scheduling. - Running ->Terminating
수행을 다 마치고 종료하는 것. Non-Preemptive Scheduling. - Waiting -> Ready
비동기적 이벤트에 의한 Preemptive Scheduling or Non-Premmptive Scheduling.
스케줄링의 목표
- CPU Utilization : cpu를 최대한 사용가능 해야한다.
- throughput : 시간당 완료되는 프로세스의 시간을 높이기!
- Turnaround time : 실행과 제출까지의 시간이 최소가 되어야한다.
- waiting time : ready queue에서 대기하는 시간을 최소화해야한다.
4번을 최소화하면 1,2,3은 따라온다. - response time : 반응시간이 빨라야한다. ex) ui, 게이머
preemptive(선점형) vs non-preemptive(비선점형)
쫓아낼 수 있다 vs 못쫓아낸다.
- Preemptible Resource : 한 프로세스가 점유한 상태에서 다른 프로세스에게 양보할 수 있는 자원. 대표적으로 CPU(Context Switching), 메인메모리(Swapping)가 있다.
- Non-Preemptible Resource : 한 프로세스가 점유하면 사용을 마칠 때까지 다른 프로세스에게 양보할 수 없는 자원. 대표적으로 프린터가 있다
dispatcher
cpu core의 controle을 주며 cpu의 context switch를 해주는 모듈을 말한다. 그러므로 dispatcher는 속도가 빨라야한다.
- dispatcher latency : 현재 실행되고 있는 프로세스를 저장하고 다른 프로세스를 restore하는 시간, 짧아야 한다.
기능
- 프로세스를 다른 프로세스로 context switching 하는 기능
- user mode로 switching
- jumping to the proper location to resume the user program
스케줄링 방법
ready queue에 있는 프로세스 중 어느것을 할당할까?
1. FCFS : First-Come, First-Served
2. SJF : Shortest Job First (SRTF : Shortest Remaining Time First) : 남은 시간이 제일 짧은 것
3. RR : Round-Robin : 시분할 time-sharing
4. Priority-based
5. MLQ : Multi-Level Queue
6. MLFQ : Multi-Level Feedback Queue
FCFS
가장 간단한 방법이다. CPU를 먼저 요청하는 프로세스의 순서대로 처리한다.
프로세스의 도착시간이 0이라고 가정하고 프로세스의 도착 순서가 P1,P2,P3라고 가정한다.
프로세스가 오는 순서에 따라서 효율이 달라진다.
convoy effect : cpu를 오래쓰는게 처음으로 오면 다른 프로세스는 계속해서 기달려야한다. 좋은 효과를 낼 수 없다.
SJF
CPU burst 시간이 가장 짧은 것부터 먼저 처리하는 방식이다. 같은게 오면 FCFS 방식으로 결정한다.
- Preemptive SJF
새로운 프로세스가 CPU burst가 더 짧다면 CPU 자원을 내주는 방식. STCF(Shortest Time to Completion First)라고도 한다. - Non-Preemptive SJF
일단 자신이 제일 짧은 CPU burst를 가진다고 생각하면 새로운 프로세스의 CPU burst가 더 짧더라도 상관없이 자신의 일을 끝내는 것.
하지만 OS가 태스크의 남은 CPU burst Size를 정확하게 예측을 할 수 없다는 문제점이 있다. 그러니 예측을 해야한다. 식에는 α(alpha)값이 존재하는데 0에 가까울 수록 과거의 CPU burst History 값을 참조하고, 1에 가까울 수록 가장 최근의 CPU burst History 값을 참조한다. 하지만 이 마저도 alpha 값이 매 상황마다 달라지기 때문에 실제 OS에서는 정확히 구현해내지 못한다.
RR(Round-Robin)
일정 시간 할당량(Time quantum) 단위로 여러 프로세스를 번갈아가며 프로세서에 할당한다. 시스템의 time-sharing과 같은 방식이다. 시간 할당량에 따라서 운영체제가 계속 개입하는 preemptive 스케줄링 방식이다.
Priority Scheduling
특정 기준으로 프로세스에게 우선순위를 부여해 우선순위에 따라 프로세서에 할당한다. 프로세스를 에이징(Aging)해서 오래 대기한 프로세스의 우선순위를 높이는 방식으로 사용된다. 다른 스케줄링 알고리즘과 결합해 사용할 수 있으므로 선점, 비선점 모두 가능하다.
하지만 이러한 방식은 starvation 문제를 발생시킨다.
- Starvation : 수행할 준비를 마치고 CPU를 할당받기를 기다리는 프로세스가 무기한 연기되는 현상.
- Aging : Task(프로세스)가 수행되지 못한채 CPU를 기다리는 시간에 비례하여 처리 우선순위를 점차적으로 높이는 기법.
출처
https://parksb.github.io/article/9.html
인프런 강의 - 운영체제 공룡책 전공강의
