CPU 스케쥴링

• 여러 개의 프로세스가 있는 시스템에서 CPU 자원을 어떻게 나누어 할당할지 결정하는 작업

• CPU 사용률, 처리량, 응답 시간, 대기 시간, Turnaroud Time을 종합적으로 고려하여 해당 작업에서 효율적인 CPU 스케쥴링 알고리즘을 선택해야 한다.

  1. CPU 사용률 (CPU Utilization): 전체 시스템에서 CPU가 작업을 처리하는 시간의 비율
  2. 처리량 (Throughput): 단위 시간 동안 CPU가 처리하는 작업의 양
  3. 응답 시간 (Response Time): 사용자가 요청을 시작한 후 첫 응답이 도착하는 데 걸리는 시간
  4. 대기 시간 (Waiting Time): 프로세스가 Ready Queue에서 대기하는 시간
  5. Turnaround Time: 프로세스가 시작해서 끝날 때까지 걸리는 총 시간
     → 대기 시간 + 실행 시간

---

1. 비선점형 CPU 스케쥴링 알고리즘

• 비선점형(Non-preemptive): 프로세스가 CPU 사용 중인 경우, 해당 프로세스가 자발적으로 CPU를 반납할 때까지 다른 프로세스가 CPU를 빼앗아 사용할 수 없는 방식

  • 프로세스 독점: 한 번 CPU를 할당받은 프로세스는 CPU를 종료하기 전까지 다른 프로세스가 CPU를 사용할 수 없다.
    이는 긴급한 작업이 있더라도 할당된 CPU를 빼앗을 수 없음을 의미한다.
  • Context Switching 부하 감소: 비선점형 알고리즘은 프로세스 간의Context Switching 부하가 발생하지 않아 CPU 사용량에 따른 오버헤드가 적다.
  • 간단한 구현: 비선점형 알고리즘은 간단하게 구현할 수 있어서 구현이 쉽다.

• FCFS (First Come First Serve): 먼저 도착한 프로세스가 먼저 CPU를 할당받는 방식

  • FCFS는 공평성을 유지하며, 모든 프로세스에게 동일한 기회를 부여
    → 기아 상태가 발생하지 않는다.
  • Convoy Effect: 실행 시간이 짧은 프로세스가 실행 시간이 긴 프로세스 앞에서 기다려야 하므로, 평균 대기 시간이 증가하고 성능이 저하될 수 있다.
    

• SJF (Shortest Job First): 실행 시간이 가장 짧은 프로세스에 CPU를 할당하는 방식으로 동작

  • 최소 대기 시간: SJF 알고리즘은 실행 시간이 짧은 프로세스를 우선적으로 처리하므로, 평균 대기 시간이 가장 짧다.
  • Starvation 현상: SJF 알고리즘은 실행 시간이 긴 프로세스에 대한 처리를 미루기 때문에, 실행 시간이 긴 프로세스는 CPU 자원을 할당받지 못하는 Starvation(기아) 현상이 발생할 수 있다.
    → Aging 기법: 프로세스의 대기 시간에 따라 우선순위를 높이는 방법으로, 실행 시간이 긴 프로세스의 Starvation을 방지
  • 실행 시간 예측 어려움: 실행 시간을 예측하는 것이 현실적으로 어려우므로, 과거로부터 얻은 정보를 기반으로 실행 시간을 예측한다.
    → 예측이 부정확할 경우 평균 대기 시간이 더 길어질 수 있다.
    

• HRN (Highest Response Ratio Next): 프로세스의 대기 시간과 CPU 사용률을 고려하여 응답 시간을 최대화하는 스케줄링 알고리즘

---

2. 선점형 CPU 스케쥴링 알고리즘

• 선점형(Preemptive): 현대 운영체제에서 채택한 방식으로, CPU를 사용 중인 프로세스가 다른 프로세스에 의해 중단될 수 있는 방식

  • 프로세스 독점을 방지: 선점형 알고리즘은 긴급한 작업이 있을 경우에도 CPU를 할당된 프로세스로부터 가져을 수 있어, CPU 독점을 방지할 수 있다.
  • Context Switching 부하 증가: 선점형 알고리즘은 CPU 스케줄링이 더 자주 발생하므로 Context Switching 부하가 증가할 수 있다.
  • 복잡한 구현: 선점형 알고리즘은 프로세스 간의 경쟁과 우선순위 관리 등을 복잡하게 다뤄야 하므로, 비선점형 방식에 비해서 구현이 어려울 수 있다.

• 라운드 로빈 (Round Robin): 각 프로세스에게 동일한 시간 슬라이스를 할당하여 CPU 소유권을 주고, 해당 시간 내에 실행을 완료하지 못한 경우에 프로세스는 Ready Queue의 맨 뒤로 이동

  • 공평성을 유지
    → 시분할 시스템(time-sharing system)에서 사용
  • 시간 슬라이스가 크면, FCFS 방식처럼 동작하여 CPU 소유권이 독점될 수 있다.
  • 시간 슬라이스가 작으면, Context switching이 자주 발생되어 오버헤드가 증가할 수 있다.
  • 각 프로세스의 평균 응답 시간이 짧아질 수 있으나, 작업 시간은 길어질 수 있다.
    
  • 로드 밸런서에서 트래픽을 분산하기 위한 알고리즘으로도 활용
    

• SRF (Shortest Remaining Time First): 중간에 실행 시간이 더 짧은 프로세스가 도착하면, 현재 수행 중인 프로세스를 중지하고 해당 프로세스에게 CPU 소유권을 할당하는 선점형 스케줄링 방식

  • SJF 알고리즘은 중간에 실행 시간이 더 짧은 프로세스가 들어와도, 현재 수행 중인 프로세스가 계속해서 CPU 소유권을 점유하고 기다리게 하는 비선점형 스케줄링 방식
  • SJF (Shortest Job First) 알고리즘의 선점형 버전으로, 현재 실행 중인 프로세스보다 남은 실행 시간이 더 짧은 프로세스가 대기열에 도착하면 CPU를 빼앗아 사용

• 다단계큐 (Multi-level queue): 다양한 우선순위를 가진 Ready Queue를 사용하여 각각의 준비큐마다 서로 다른 스케줄링 알고리즘을 적용하는 방식

  • 다양한 우선순위: 다양한 스케줄링 알고리즘을 적용할 수 있다.
  • 큐 간 이동 제한: 다단계 큐에서는 프로세스가 한 큐에서 다른 큐로 이동하는 것이 제한되므로 유연성이 떨어질 수 있다.
  • Starvation(기아) 현상: 낮은 우선순위를 가진 레디 큐는 높은 우선순위 큐에 비해 처리 기회가 적을 수 있으며, 이로 인해 낮은 우선순위 프로세스가 오랜 시간 동안 실행되지 않는 Starvation 현상이 발생할 수 있다.