CPU 스케줄링

: 여러 프로세스가 CPU를 기다리는 상황에서 CPU를 어떤 프로세스에 할당할지 결정하는 과정
스케줄링 알고리즘을 통해 프로세스 실행 순서를 결정한다.

CPU 스케줄링 성능 척도

; 성능 평가 지표

CPU 이용률 (CPU Utilization)

전체 시간 중 CPU가 놀지 않고 일한 시간 비율.
높을수록 CPU를 가용할 수 있는 시간 대비 CPU가 일한 시간이 높은 것이므로, 높을수록 좋음

처리량 (Throughput)

주어진 시간 동안 처리되는 프로세스 수.
클수록 좋음

대기 시간 (Waiting Time)

Ready 상태에서 CPU를 기다린 총 시간
Ready Queue에 머문 시간
짧을수록 좋음

응답 시간 (Response Time)

Ready 상태의 프로세스에게 최초로 CPU가 할당되기까지 걸린 시간.
즉, 얼마나 빨리 시작할 수 있는지

소요 시간 (Turnaround time)

프로세스가 CPU를 요청한 시점으로부터 원하는 만큼의 CPU를 모두 사용하는 데 걸린 시간
짧을 수록 좋음

시스템 입장에서의 성능 척도

• CPU 하나 가지고 최대한 많은 일을 시킬 수 있으면 성능이 좋음
• 주요 지표: CPU 이용률, 처리량

프로그램 입장에서의 성능 척도

• 프로그램이 최대한 빨리 끝날 수 있으면 성능이 좋음
• 주요 지표: 대기 시간, 응답 시간, 소요 시간

CPU 스케줄링 알고리즘

선점형 스케줄링과 비선점형 스케줄링

선점형 스케줄링은 CPU를 강제로 빼앗기지만,
비선점형 스케줄링은 CPU를 강제로 빼앗기지 않음.
즉, 비선점형은 모든 실행을 끝내야지만 다음 프로세스를 실행할 수 있다.

FCFS (First-Come First-Serve)

• 먼저 온 프로세스부터 CPU를 할당, 비선점형 스케줄링
• 단점: 소요 시간이 긴 프로세스가 먼저 도착할 경우, 전체적으로 프로세스들의 효율성을 낮춤

SJF (Shortest-Job-First)

CPU Burst: 프로세스가 CPU를 사용해 계산이나 데이터 처리 작업을 수행하는 시간
Starvation: 우선순위가 낮은 프로세스가 장시간 동안 자원을 할당받지 못하는 상태

• CPU Burst가 짧은 프로세스에게 먼저 CPU를 할당, 비선점형 스케줄링
  CPU를 적게 사용하는 프로세스 먼저 실행
• 단점: CPU Burst가 긴 프로세스는 오랜 시간 CPU를 할당받지 못하는 starvation 문제가 발생할 수 있음

SRTF (Shortest-Remaining-Time-First)

• SJF와 유사하나 중간에 새로운 프로세스가 도착하면 새로 스케줄링, 선점형 스케줄링
• 현재 실행 중인 프로세스의 남은 CPU Burst 시간보다 더 짧은 CPU Burst 시간을 가지는 프로세스가 도착하면 CPU를 빼앗김

Priority Scheduling

• 우선순위대로 CPU 할당
• 선점형 스케줄링 방식에서는 더 높은 우선 순위의 프로세스가 도착하면 그 프로세스에게 CPU를 빼앗김
• 비선점형 스케줄링 방식에서는 더 높은 우선 순위의 프로세스가 도착하더라도 그 프로세스는 우선 ready queue에 위치됨
• 이 방식에서도 starvation 문제가 발생하여 aging 기법을 사용
• aging은 오래 기다린 프로세스에게 우선순위를 높여주는 것

Round Robin

• 가장 현대적인 방식, 각 프로세스에게 동일한 크기의 CPU 할당 시간을 줌
• 할당 시간이 지난 프로세스는 ready queue의 제일 뒤에 가서 다시 CPU를 기다림
• 장점: 가장 빠른 응답 시간을 기대할 수 있음
• 주의: 할당 시간이 너무 큰 경우, FCFS처럼 동작해버리고,
  너무 짧은 경우, 문맥 교환 오버헤드(Context switching overhead)가 커지기 때문에 적절한 할당시간을 설정해야 함