CPU Scheduler
운영체제 안에서 CPU 스케줄링을 하는 코드가 있는 부분. Ready 상태의 프로세스 중 누구한테 CPU를 줄지 결정한다.
Dispatcher
CPU를 누구한테 줄지 결정됐으면 실제로 그 프로세스에 CPU를 넘겨주는 역할을 하는 운영체제 커널 코드(현재 돌아가고 있는 프로세스의 context를 저장하고 새로 CPU를 넘겨줄 프로세스의 context를 가져온다.)
성능 척도
시스템 입장(CPU 하나로 최대한 일을 많이 시키면 좋은 것)
- CPU utilization(이용률): 전체 시간 중에서 CPU가 놀지 않고 일한 시간의 비율
- Throughput(처리량): 주어진 시간 동안 몇 개의 작업을 완료하였나
프로세스 입장(CPU를 빨리 얻어서 빨리 끝나면 좋은 것)
- Turnaround time(소요 시간): CPU를 쓰러 들어와서 다쓰고 나갈 때까지 걸린 시간
- Waiting time(대기 시간): 기다리는 시간(CPU가 하나 밖에 없으므로 ready 큐에 줄서서 기다리므로 이때 기다리는 시간)
- Response time(응답 시간): ready 큐에 들어와서 처음으로 CPU(최초로)를 얻기까지 걸린 시간
Waiting time vs Response time
프로세스는 CPU를 뺏겼다가 다시 실행되고 뺏겼다가 다시 실행될고 할 수 있다. 이때 매번 ready 큐에 줄서서 기다려야하는데 ready 큐에 줄서서 기다리는 모든 시간은 Waiting time, 제일 최초로 기다리는 시간은 Response time이다.
CPU 스케줄링 알고리즘
스케줄링이 필요한 이유는 CPU를 많이 쓰는 작업, CPU를 적게 쓰는 작업이 섞여있기 때문이다.
비선점
CPU를 강제로 빼앗기지 않음
선점형
CPU를 강제로 빼앗음
FCFS(First-Come-First-Served)
먼저 들어온 프로세스를 먼저 서비스 해주는 방법. 효율적이진 않다.(CPU를 오래 쓰는 프로그램이 도착해서 먼저 CPU를 잡으면, CPU를 짧게 쓰는 프로그램들이 도착해도 계속 기다려야 한다.) 비선점형 방법.
SJF(Shortest-Job-First)
CPU를 사용하고자 하는 시간이 제일 짧은 프로그램에 CPU를 주는 스케줄링. 평균 waiting time을 가장 줄일 수 있는 방법. 비선점형, 선점형 두 가지 방법으로 나뉠 수 있다.
비선점형: CPU 사용시간이 짧은 순으로 순차적으로 진행되고(현재 진행중인 프로세스가 CPU를 다 쓰고 나가는 시점에 스케줄링 여부 결정)
선점형: 중간에 더 짧은 프로세스가 들어오면 CPU를 빼앗아서 그 프로세스에 CPU를 넘겨준다.(새로운 프로세스가 도착하면 스케줄링 여부 결정)
문제점:
starvation: CPU 사용시간이 긴 프로세스는 영원히 사용되지 못할 수도 있다.
CPU 사용시간을 미리 알 수 없음: 프로세스가 CPU를 얼마나 쓸지는 알 수 없지만 예측할 수 있다.(과거의 기록을 보고 예측한다 보통 exponential averaging 사용)
Priority Scheduling
우선순위가 제일 높은 프로세스에게 CPU를 주는 방법.
비선점형: 일단 CPU를 줬으면 더 높은 우선순위를 가진 프로세스가 도착하더라도 끝날때까지 기다린다.
선점형: 현재 프로세스보다 우선순위가 높은 프로세스가 도착하면 CPU를 빼앗는다.
문제점:
starvation: 우선 순위가 낮은 프로세스는 영원히 사용되지 못할 수도 있다. -> Aging(아무리 우선순위가 낮은 프로세스여도 오래 기다리면 우선순위를 높여줌)으로 해결
Round Robin
현대적인 컴퓨터 시스템에서 사용하는 CPU 스케줄링. CPU를 넘겨줄 때 할당 시간을 세팅해서 넘겨준다. 할당 시간이 끝나면 timer interrupt가 걸려서 CPU를 빼앗긴다.(선점형 스케줄링)
CPU를 최초로 얻기 위한 시간이 빨라진다.
CPU를 길게 쓰는 프로그램은 기다리는 시간이 길어지고, 짧게 쓰는 프로그램은 기다리는 시간이 짧아진다.
할당 시간을 너무 길게 잡으면 FCFS와 같은 성능이 될 수 있고, 할당 시간을 너무 짧게 잡으면 context switch overhead가 커진다. -> 적당한 규모를 줘야함(10ms ~ 100ms)
response time이 빨리지는 장점을 가짐
Multilevel Queue
CPU를 기다리는 ready queue에 프로세스들이 한 줄 서기가 아닌 여러 줄 서기를 하는 방법. 줄 마다 우선순위가 존재한다. 무조건 높은 우선순위의 줄 부터 CPU를 준다. 각 줄마다 스케줄링 방법이 다를 수 있다.
이런 경우 우선순위가 낮은 줄에 서있는 프로세스들은 starvation을 겪을 수도 있기 때문에, 각 큐에 CPU time을 적절한 비율로 할당하거나 하여 어느정도 해결할 수 있다.
Multilevel Feedback Queue
Multilevel Queue와 동일하게 여러 줄이 있지만 우선순위가 낮아도 우선순위가 올라갈 수도 있고, 우선순위가 높더라도 낮아질수도 있다.
처음 들어오면 모두 가장 우선순위가 높은 큐에 들어가고 Round Robin에 의해 다 수행되지 못할경우 우선순위가 떨어지는 방식으로 실행된다.
ex) Q0 = RR: 할당 시간 8ms
Q1 = RR: 할당 시간 16ms
Q2 = FCFS
