CPU 스케줄링
1. 개요
CPU 코어가 하나라면 한 번에 하나의 프로세스만 실행 가능하다.
CPU의 이용률을 극대화하기 위해 다중프로그래밍
이 필요하고, CPU 스케줄링은 프로세스들에게 CPU를 할당하기 위한 정책을 계획하는 방법이다.
즉, 운영체제는 CPU를 프로세스 간에 교환함으로써, 작업 효율을 높인다.
2. 평가 기준
- CPU 이용률
- 처리율
- 반환시간
- 프로세스의 생성~종료 후 자원 반환까지의 시간
- 대기시간
- 대기열에 들어와 CPU를 할당받기까지의 총 시간
- 응답시간
- 대기열에서 처음으로 CPU를 얻을 때까지 걸린 시간
3. 스케줄링 결정 시기
- 실행(running)에서 대기(waiting)로 전환될 때 (I/O 발생)
- 실행(running)에서 준비(ready)로 전환될 때 (intterupt 발생)
- 대기(waiting)에서 준비(ready)로 전환될 때 (I/O 완료 시)
- 종료(Terminated)될 때
4. 선점과 비선점
- 선점(Preemptive)
- 진행 중인 프로세스를 중지하고 CPU 점유 가능
- CPU 사용 독점을 막을 수 있어 효율적
- contextSwitching으로 인해 오버헤드가 커질 수 있다.
- 비선점(Nonpreemptive)
- 진행 중인 프로세스가 다 끝나야 다른 프로세스 사용 가능
- 프로세스의 배치에 따라 효율성 차이가 날 수 있다.
- contextSwitching으로 인한 오버헤드가 적다.
5. CPU 스케줄링 알고리즘
선점형
1) SRT 스케줄링 (SRT, Shortest Remaining Time)
- 선점형 SJF 스케줄링이라고도 불린다.
- 가장 짧게 남은 버스트 시간에 따라 CPU 할당
- 기아 현상 발생 가능
2) 라운드 로빈 스케줄링 (Round-Robin)
- 정해진 시간만큼 돌아가면서 CPU를 사용하는 것
3) 다단계 큐 스케줄링
- 여러 개의 준비 큐가 있고, 각자의 스케줄링 알고리즘을 갖고 있다.
- 각 큐들에 우선순위를 부여
- 각 큐 사이에서 프로세스들은 이동 불가
- 기아문제 발생 가능
4) 다단계 피드백 큐 스케줄링
- 다단계 큐 스케줄링에서 프로세스는 각 큐 사이를 이동 할 수 있다.
비선점형
5) 선입선처리 스케줄링 (FCFS, First Come First Served)
- 가장 먼저 요청한 프로세스에 CPU 할당
- 가장 간단하지만 convoy effect가 발생할 수 있다.
호위효과: 처리 시간이 긴 프로세스가 앞에 있으면 뒤는 매우 긴 시간을 기다려야 함
6) 최단 작업 우선 스케줄링 (SJF, Shortest Job First)
7) HRN 스케줄링 (HRN, Highest Response Ratio Next)
- SJF 스케줄링에 Aging 기법을 합친 알고리즘
- 실행 시간이 짧은 프로세스가 우선 순위가 높지만, 대기 시간이 길어지면 우선 순위를 높여 긴 프로세스도 CPU를 할당받음
구현에 따라 둘 다
7) 우선순위 스케줄링 (Priority)