CPU 스케줄링 (CPU Scheduling, Processor Scheduling)
✓ 정의 : CPU(프로세서)를 사용하려 하는 프로세스들 사이에서 우선순위를 관리하는 일
✓ 작업 처리율과 CPU 이용률을 향상시키기 위해 필요한 기법이다.
✓ 비선점 스케줄링과 선점 스케줄링으로 나뉜다.
비선점 스케줄링 (Non-preemptive Scheduling)
✓ 정의 : 어떤 프로세스가 사용 중인 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링
✓ 일괄 처리 시스템에 적합하며, 응답 시간 예측이 쉬운 장점이 있다.
✓ 중요한 작업(짧은 작업)이 중요하지 않은 작업(긴 작업)을 기다리는 경우가 발생할 수 있는 단점이 있다.
✓ FCFS 스케줄링 (First-Come First-Served Scheduling)
- FIFO 스케줄링이라고도 하며, 준비 큐(Ready Queue)에 먼저 도착한 순서에 따라 CPU를 할당하는 스케줄링이다.
- 먼저 들어온 프로세스가 먼저 처리되어 공평성은 유지되나, 중요한 작업이 중요하지 않은 작업을 기다릴 가능성이 있다.
✓ SJF 스케줄링 (Shortest Job First Scheduling)
- 실행 시간이 가장 짧은 프로세스에 먼저 CPU를 할당하는 스케줄링이다.
- 프로세스들의 평균 대기 시간이 가장 짧다.
- 기아 상태가 발생할 수 있다. 기아는 에이징으로 해결할 수 있다.
✓ HRRN 스케줄링 (Highest Reponse Ratio Next Scheduling)
- HRN 스케줄링이라고도 하며, SJF 스케줄링의 문제점을 보완한 스케줄링이다.
- 실행 시간과 대기 시간을 둘 다 고려해 우선순위를 정하고, 각 프로세스의 우선순위에 따라 CPU를 할당한다.
- 우선순위 = (대기 시간 + 실행 시간) / 실행 시간
✓ 우선순위 스케줄링 (Priority Scheduling)
- 각 프로세스마다 우선순위를 부여하고, 각 프로세스의 우선순위에 따라 CPU를 할당하는 스케줄링이다.
- 우선순위는 시간제한, 메모리 요구, 열린 파일의 수, 평균 실행 시간, 프로세스의 중요도, 자원 사용량 등을 복합적으로 고려하여 정한다.
- SJF 스케줄링과 마찬가지로 기아 상태가 발생할 수 있다.
선점 스케줄링 (Preemptive Scheduling)
✓ 정의 : 어떤 프로세스가 사용 중인 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 있는 스케줄링
✓ 시분할 시스템에 적합하며, 응답 시간이 빠른 장점이 있다.
✓ CPU를 선점할 프로세스에게 일정한 시간을 배정하기 위해 인터럽트용 타이머가 필요하다.
✓ 비선점 스케줄링에 비해 오버헤드가 큰 단점이 있다.
✓ RR 스케줄링 (Round Robin Scheduling)
- 라운드 로빈 스케줄링은 시분할 시스템을 위해 설계된 스케줄링이다.
- FCFS 스케줄링과 유사하며, 선점이 가능하도록 시간 단위(Time Quantum, Time Slice) 개념이 추가돼있다.
- FCFS 처럼 준비 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만, 각 프로세스는 Time Quantum 만큼만 실행된 후 다시 준비 큐로 돌아간다.
- Time Quantum이 커지면 FCFS 스케줄링과 같아지고, Time Quantum이 작으면 Context Switch가 자주 발생하여 오버헤드가 커진다.
✓ SRT 스케줄링 (Shortest Remaining Time Scheduling)
- SJF 스케줄링을 선점이 가능하도록 변형한 스케줄링이다.
- 실행 중인 프로세스의 남은 실행 시간과 준비 큐에 도착한 프로세스의 실행 시간을 비교하고, 그중 실행 시간이 짧은 프로세스에게 CPU를 할당하는 스케줄링이다.
✓ MLQ 스케줄링 (Multilevel Queue Scheduling)
- 멀티레벨 큐 스케줄링(다단계 큐 스케줄링)은 프로세스를 특정 그룹으로 분류하고, 각 그룹에 따라 각기 다른 준비 큐를 이용하는 스케줄링이다.
- 각 준비 큐는 각기 다른 스케줄링 알고리즘을 가질 수 있으며, 큐와 큐 사이에도 스케줄링 알고리즘이 필요하다.
✓ MLFQ 스케줄링 (Multilevel Feedback Queue Scheduling)
- 멀티레벨 피드백 큐 스케줄링(다단계 피드백 큐)는 멀티레벨 큐를 변형한 스케줄링이다.
- MLQ에서는 프로세스가 큐와 큐 사이를 이동할 수 없으나, MLFQ에서는 프로세스가 큐와 큐 사이를 이동할 수 있다.
- 예를 들어, 특정 프로세스가 CPU를 너무 많이 사용하면(실행 시간이 길면), 우선순위가 낮은 큐로 이동된다. 또한, 우선순위가 낮은 큐에서 너무 오래 대기하는 프로세스가 있다면, 해당 프로세스는 우선순위가 높은 큐로 이동된다.
스케줄링 이해를 돕기 위한 도표
✓ 주어지는 조건 : 4개의 프로세스와, 각 프로세스의 도착 시간(Arrival Time)과 실행 시간(Burst Time)
✓ 조건을 통해 구할 수 있는 것 : 각 프로세스의 대기 시간(Waiting Time)과 소요 시간(Turnaround Time)
✓ Gantt 차트(막대 모양)를 통해 각 프로세스의 스케줄을 표현했다.
용어 설명
✓ 도착 시간 (Arrival Time) : 프로세스가 준비 큐(Ready Queue)에 도착한 시각.
✓ 완료 시간 (Completion Time) : 프로세스가 작업을 마친 시각.
✓ 스케줄 시간 (Schedule Time) : 프로세스가 CPU에서 실행된 시각.
✓ 응답 시간 (Response Time) : 프로세스가 도착 시간부터 CPU에서 실행되기까지 걸린 시간. [도착 시간 - 스케줄 시간]과 같다.
✓ 실행 시간 (Execution Time) : 프로세스가 CPU에서 실행된 총 시간. 버스트 시간(Burst Time)이라고도 한다.
✓ 대기 시간 (Waiting Time) : 프로세스가 준비 큐에서 기다린 총 시간.
✓ 소요 시간 (Turnaround Time) : 프로세스가 모든 작업을 마치는데 걸린 시간. [완료 시간 - 도착 시간] 또는 [실행 시간 + 대기 시간]과 같다. 반환 시간, 총 처리 시간이라고도 한다.
✓ 기아 (Starvation) : 실행 시간이 긴 프로세스가 자원을 계속 할당받지 못하는 문제이다. 실행 시간이 긴 프로세스가 대기하는 상황에서, 실행 시간이 짧은 프로세스가 준비 큐에 계속 들어오면, 실행 시간이 긴 프로세스는 계속 자원을 할당받지 못하는 문제가 생긴다.
✓ 에이징 (Aging) : 준비 큐에 있는 프로세스에 나이를 부여하는 방법이다. 특정 프로세스가 얼마나 오래 기다렸는지 고려하고, 기다린 시간이 길다면 자원을 할당해 준다.