CPU 스케줄링 알고리즘
CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다.
프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정한다. CPU 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게 준비 큐(ready queue)에 있는 프로세스는 적게, 응답시간은 짧게 설정하는 것을 목표로 한다
즉 CPU 스케줄링 알고리즘의 목표는 상황에 맞게 CPU를 어떤 프로세스에 배정하여 효율적으로 처리하는방법
오버헤드를 낮추고, 사용률을 높히고, 응답시간은 짧게, 기아현상을 낮추는것이 목표
비선점형 방식
비선점(Non-Preemptive) : 프로세스가 CPU를 점유하면 I/O나 인터럽트 발생 또는 프로세스가 종료될 떄 까지 다른 프로세스가 CPU를 못뺐음. 스스로 CPU 소유권을 포기하는 방식이며 강제로 프로세스를 중지하지 않는것.
- 즉, 일이 끝날 때 까지 CPU 소유권을 포기하지 않으니까 프로세스 교체가 적어지고 컨텍스트 스위칭으인한 부하가 적어진다
- 그러므로 처리시간 예측이 용이하다.
- FCFS(First Come, First Served, FIFO)
- 먼저 큐에 온 순서대로 처리.
- 실행시간이 짧은게 뒤로가면 평균 대기시간이 길어짐
- 오랫동안 수행되는 프로세스가 있따면 준비 큐에서 오래 기다리는 현상(convoy effect)이 발생하는 단점이 있다.
- SJF(Shortest - Job - First)
- 다른 프로세스가 먼저 도착했어도
수행시간이 가장 짧은 프로세스를 먼저 처리 하는 알고리즘 - FCFS보다 평균 대기시간 감소
- 그러나 사용시간이 긴 프로세스는 거의 영원히 할당받을 수 없다.
- 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했떤 시간을 토대로 추측해서 사용한다.
- 다른 프로세스가 먼저 도착했어도
- Priority : 우선순위
- 우선순위(정수로 나타냄)가 가장 높은 프로세스에게 할당한하는 스케줄링
- 선점 / 비선점 모두 가능
- 우선순위가 낮으면 기아상태 발생
점형 방식
선점(Preemptive) : 현대 운영체제가 쓰는 방식으로 프로세스가 CPU를 점유하고 있는 동안 I/O나 인터럽트가 발생하지 않았을 경우에도 CPU를 뺏는것을 말한다. 강제로 다른 프로세스에게 CPU 소유권을 할당하는 방식
- 처리시간 예측이 어렵다.
- SRT(Shortest Remaining Time) : 최단 잔여(짧은) 시간 우선
- 잔여시간이 짧은 순서대로 프로세스 수행.
- 현재 프로세스가 남은 CPU 버스트 시간보다 더짧은 CPU 버스트시간을 가진 프로세스가 도착하면 나중에 온 애가 선점
- RR, RoundRobin() : 라운드로빈
- Queue를 이용하며. 각 프로세스는 동일한 할당 시간을 주고 그 시간안에 끝나지 않으면 다시 큐의 뒤로 가는 알고리즘
- 각 프로세스는 동일한 크기의 사용 시간을 할당받음.
- 장점으로 응답시간이 빨라지고, 각 프로세스들이 공평하게 사용된다.
- 단점으로는 할당된 시간이 작으면 컨텍스트 스위칭이 잦아져서 오버헤드 증가
- 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰인다.
- SRF(Shortest Remaining Time First))
- 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘
- Multilevel-Queue(멀티레벨 큐, 다단계 큐)
- 큐를 여러 개 두고 큐마다 RR이나 FCFS 등 다른 스케줄링 알고리즘을 지정하여 프로세스를 그룹으로 나누어 각 그룹에 따라 각 큐마다 다른 규칙을 지정하여 사용.
- 프로세스들이 여러줄로 슨다.
- Multilevel feedback queue(멀티레벨 피드백 큐, 다단계 피드백 큐 )
- 기본적으로 다단계 큐와 동일하나, 프로세스가 기다리고 있던 큐에서 다른 큐로 이동가능하다.
- 기다리고 있던 큐에 대기시간이 너무 길면 대기시간이 짧은 큐로 프로세스를 옮겨서 대기시간을 조정
- 대부분의 상용 운영체제는 여러개의 큐를 사용하고 각 큐마다 다른 스케쥴링을 사용하여 최대한 효율을 높힌다.