CPU 스케줄링(CPU Scheduling)

운영 체제의 프로세스 관리자가 여러 프로세스 또는 스레드 사이에서 CPU 시간을 어떻게 분배할지 결정하는 과정

 

평가 척도

• 응답 시간(Response Time): 요청 후 시스템이 처음으로 응답할 때까지 걸린 시간
• 대기 시간(Waiting Time): 프로세스가 준비 상태에서 실행될 때까지 기다린 시간
• 실행 시간(Turnaround Time): 프로세스가 실행을 시작한 후 완료될 때까지 걸린 시간
• 처리량(Throughput): 단위 시간당 시스템이 완료할 수 있는 프로세스의 수

시스템 유형에 따른 스케줄링의 목표

• Batch System: 처리량(throughput) 최대화
• Interactive System: 빠른 응답 시간(response time)과 짧은 대기 시간(waiting time)을 우선시
• Real-time System: 작업의 완료 기한(deadline)을 준수

선점 vs 비선점 스케줄링

• 선점(Preemptive) 스케줄링: 운영 체제가 CPU를 현재 프로세스로부터 강제로 회수하여 다른 프로세스에 할당
  
  • Round Robin: 모든 프로세스에 동등한 시간 할당량(Time Quantum)을 부여하고, 이 시간 동안만 CPU를 사용할 수 있게 함
  • Multilevel Queue
    • Ready 큐를 여러 개 사용
    • 각각의 큐는 자신의 스케줄링 알고리즘을 수행
    • 우선순위가 높은 큐는 작은 Time Quantum 할당. 우선순위가 낮은 큐는 큰 Time Quantum 할당
  • Multilevel Feedback Queue:
    • 다단계 큐 방식에 피드백을 추가하여, 프로세스가 다른 큐로 이동 가능
    • Time Quantum을 다 채운 프로세스는 우선순위 낮은 큐로 이동
    • Time Quantum을 다 채우지 못한 프로세스는 그대로
• 비선점(Non-Preemptive) 스케줄링: 프로세스가 CPU를 점유하면, 종료되거나 대기 상태가 될 때까지 CPU를 계속 사용
  • FCFS (First Come First Served): 큐에 도착한 순서대로 CPU를 할당
  • SJF (Shortest Job First): 실행 시간이 가장 짧은 프로세스에게 우선적으로 CPU를 할당
  • HRN (Highest Response-ratio Next): 우선순위 = (대기시간 + 실행시간) / (실행시간)
  • Priority Scheduling: 프로세스에 우선순위를 부여, Aging 방식(시간 지나면 우선순위 증가)으로 기아 상태 해결