CPU 스케줄링

- CPU Scheduling이란?

CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스가 작업을 수행해야 함, 이때 어떤 프로세스를 다음에 처리할지 선택하는 알고리즘

따라서 상황에 맞게 CPU를 어떤 프로세스에 배정하여 효율적으로 처리하는가가 관건

- Preemptive vs Non-Preemptive

1) Preemptive(선점)

프로세스가 CPU를 점유하고 있는 동안 I/O나 인터럽트가 발생하지 않았음에도 다른 프로세스가 해당 CPU를 강제로 점유 가능

프로세스가 정상적으로 수행중인 동안 다른 프로세스가 CPU를 강제로 점유하여 실행 가능

2) Non-Preemptive(비선점)

한 프로세스가 CPU를 점유했다면 I/O나 인터럽트 발생 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못하는 것

- 선점형 스케줄링

1) SRT(Shortest Remaining Time) 스케줄링

짧은 시간 순서대로 프로세스를 수행
현재 CPU에서 실행 중인 프로세스의 남은 CPU burst 시간보다 더 짧은 CPU burst 시간을 갖는 프로세스가 도착하면 CPU가 선점됨

2) Round Robin 스케줄링

3) Multi-level Queue 스케줄링

4) Multi-level feedback Queue 스케줄링

기본 개념은 Multi-level Queue와 동일하나 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다름
모든 프로세스는 가장 위의 큐에서 CPU의 점유를 대기
이 상태로 진행하다가 이 큐에서 기다리는 시간이 너무 오래걸린다면 아래의 큐로 프로세스 옮김 -> 대기 시간 조정
만약 우선순위 순으로 큐를 사용하는 상황에서 우선순위가 낮은 아래의 큐에 있는 프로세스에서 starvation 상태가 발생하면 이를 우선순위가 높은 큐로 옮김
대부분 상용 OS는 여러 개의 큐를 사용하고 각 큐마다 다른 스케줄링 방식을 사용(프로세스 성격에 맞는 스케줄링 방식 사용)

- 비선점형 스케줄링

1) FCFS(First Come First Serve)

2) SJF(Shortest-Job-First)

3) Priority

우선순위가 높은 프로세스가 먼저 선택되는 스케줄링 알고리즘
우선순위는 정수값으로 나타내며, 작은 값이 우선순위가 높음(Unix / Linux 기준)
선점, 비선점 모두 가능
우선순위 내부적 요소 : time limit, memory requirement, I/O to CPU burst(I/O 작업은 길고 CPU 작업은 짧은 프로세스 우선)
우선순위 외부적 요소 : amount of funds being paid, political factors
Starvations 현상 발생 -> 해결법 : aging(ready queue에서 기다리는 동안 일정 시간이 지나면 우선 순위를 일정량 높여주는 것)

정리 블로그