CPU 스케줄링

삼각김밥·2023년 7월 3일

일을 쉬지않고 계속 시키는 것이 OS의 숙제.(Maximize CPU Utilization)
여러 개의 프로세스가 CPU를 사용하기 위해 경쟁하는 상황에서 어떤 순서로 CPU를 할당할지 결정하는 것.
프로세스 실행은 CPU 실행 및 입출력(I/O) 대기로 구성.
많은 수의 짧은 CPU 버스트와 적은 수의 긴 CPU 버스트 존재.
- I/O-bound 프로그램: 많은 수의 짧은 CPU 버스트.
- CPU-bound 프로그램: 적은 수의 긴 CPU 버스트.

CPU Burst

메모리에 있는 프로세스들 중 실행할 준비가 되어있는 Ready 상태의 프로세스를 선택하고, 그 프로세스에 CPU를 할당.
CPU 스케줄링 결정
1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때.(비선점형)
2. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때.(선점형)
3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때.(선점형)
4. 프로세스가 종료될 때.(비선점형)
디스패쳐
1. Context Switch.
2. 사용자 모드로 전환.
3. 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동.
스케줄링 기준
- CPU 이용률(Utilization): 가능한 최대한 바쁘게 유지. (⬆️)
- 처리량(Throughput): 단위 시간 당 완료된 프로세스의 개수. (⬆️)
- 총 처리 시간(Turnaround Time): 프로세스의 제출 시간과 완료 시간의 간격. (⬇️)
- 대기 시간(Waiting Time): 준비 완료 큐에서 대기하면서 보낸 시간의 합. (⬇️)
- 응답 시간(Response Time): 하나의 요구를 제출한 후 첫 번째 응답이 발생할 때 까지의 시간(출력 X). (⬇️)

선입 선처리 스케줄링(First-Come, First-Served, FCFS)
- CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받음.
- FIFO 큐로 관리
최단 작업 우선 스케줄링(Shortest-Job-First, SJF)
- CPU Burst가 짧을 수록 CPU를 먼저 할당 받음.
우선 순위 스케줄링(Priority)
- 우선순위가 프로세스들에게 연관되어 있으며, 높은 우선순위를 가진 프로세스에게 CPU 할당.
라운드 로빈 스케줄링(Round-Robin)
- 시간 할당량이라고 일컫는 작은 단위의 시간을 정의.
- 한 번에 한 프로세스에게 한 번의 시간 할당량동안 CPU를 할당.

장점:
- 가장 간단한 형태.
- 코드 작성이 쉽고 이해하기 쉬움.
- 공정한 방식으로 프로세스 처리.
단점:
- 순서에 따라 대기 시간의 차이가 큼.
- 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다려야 함.
- 비선점형이기 때문에, 시분할에 부적합.

장점:
- 내부적 정의(시간제한, 메모리 요구, open files수 등) 활용 가능
- 외부적 정의(프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 유형과 양 등) 활용 가능.
단점:
- 무한 봉쇄, 기아 상태발생 가능.

장점:
- 모든 프로세스에게 공평한 CPU 할당을 제공.
- 시분할 시스템 최적화
단점:
- 시간 할당량(Time Quantum)에 따른 영향 존재.
  - 너무 클 경우 - FCFS와 동일한 알고리즘.
  - 너무 작을 경우 - Context Switch에 시간을 더 뺏김.
- 대기 시간이 긴 프로세스에 대해 평균 대기 시간이 높아질 수 있음.

프로세스 타입에 따라 몇 개의 큐로 나누어 프로세스를 분류.
- 프그라운드(대화형), 백그라운드(일괄처리)
큐 별로 별도의 스케줄링 알고리즘을 가짐.
- 포그라운드(RR), 백그라운드(FCFS)
각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가짐.
각 큐는 일정 비율로 CPU 시간을 나누어 사용.
- 포그라운드 큐 - RR, CPU 시간의 80%
- 백그라운드 큐 - FCFS, CPU 시간의 20%