CPU 스케줄링
1. 개요
CPU 코어가 하나라면 한 번에 하나의 프로세스만 실행 가능하다.
CPU의 이용률을 극대화하기 위해 다중프로그래밍이 필요하고, CPU 스케줄링은 프로세스들에게 CPU를 할당하기 위한 정책을 계획하는 방법이다.
즉, 운영체제는 CPU를 프로세스 간에 교환함으로써, 작업 효율을 높인다.
2. 평가 기준
- CPU 이용률
- 시간당 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)
- 가장 짧은 실행 시간에 따라 CPU 할당
7) HRN 스케줄링 (HRN, Highest Response Ratio Next)
- SJF 스케줄링에 Aging 기법을 합친 알고리즘
- 실행 시간이 짧은 프로세스가 우선 순위가 높지만, 대기 시간이 길어지면 우선 순위를 높여 긴 프로세스도 CPU를 할당받음
구현에 따라 둘 다
7) 우선순위 스케줄링 (Priority)
- 프로세스의 우선순위에 따라 CPU 할당
- SJF, HRN, SRT도 우선순위 스케줄링 알고리즘 중 하나이다.
- 기아문제 발생 가능
기아문제: 낮은 우선 순위의 프로세스가 절대 실행되지 않는 문제 노화(aging)으로 해결 가능. 시간이 지날수록 우선순위를 높여주는 방법
SSAFY 7기. HMG. 협업, 소통, 사용자중심