CPU 스케줄링 (CPU Scheduling)

CPU 스케줄링이란?

• 멀티프로그래밍 되어있는 OS에서 기본이 되는 요소이다.
• 멀티프로그래밍의 목적은 프로세스가 동시에 전부 돌 수 있게하고, CPU 사용성을 최대화 하기 위해서이다.
• 메모리에 있는 프로세스 중 ready 상태에 있는 프로세스에게 CPU를 할당해주는 것
• 선택 방식
  • FIFO 큐: First-In, First-Out
  • Priority 큐

 

선점형(Preemptive) vs 비선점형(Non-preemptive)

• 비선점형 스케줄링
  • CPU를 프로세스가 놓을 때까지 강제로 스위치할 수 없음
• 선점형 스케줄링
  • 스케줄러가 프로세스를 쫓아낼 수 있음
• CPU 스케줄링의 결정
  1. 프로세스가 running -> waiting (비선점)
  2. 프로세스가 running -> ready (선점/비선점)
  3. 프로세스가 waiting -> ready (선점/비선점)
  4. 프로세스가 종료 (비선점)
• 디스패쳐(Dispatcher)
  • CPU의 코어를 제어하는 모듈
  • 스케줄러가 어떤 프로세스로 스위치할 지 결정하면 디스패쳐가 실제로 그 프로세스로 스위치하게 만들어 줌
  • 디스패쳐의 기능
    • 프로세스에서 다른 프로세스로 context switching 하게 해줌
    • user mode로 스위칭하게 해줌
    • 새로운 프로세스의 적당한 위치로 이어갈 수 있게 해줌

 

CPU 스케줄링의 목적

• CPU 사용성
• 시간 당 완료되는 프로세스의 수를 최대화
• 교체시간 최소화
• 대기시간 최소화(ready 큐에 있는 시간 최소화)
• 응답시간 최소화

 

스케줄링 문제의 해결법

• FCFS: First-Come, First-Served
  • 가장 단순한 스케줄링 알고리즘
  • 먼저 할당된 프로세스 먼저 처리
  • 비선점형 스케줄링 알고리즘
  • convoy effect(호송 효과/똥차 효과)
    • 짧은 프로세스가 와도 긴 프로세스가 앞에 선점하고 있어서 비효율적임
• SJF: Shortest Job First
  • 온 순서와 무관하게 현재 가장 작은 CPU 소요시간을 가진 프로세스를 먼저 할당한다
  • 평균 시간에서 가장 효율적인 알고리즘
  • 구현해낼 방법이 없음 -> CPU 소요시간을 예측해서 근사값으로 적용함(과거의 데이터를 토대로)
  • 비선점형 스케줄링 알고리즘도 될 수 있고, 선점형 스케줄링 알고리즘이 될 수도 있다
• SRTF: Shortest Remaining Time First
  • 새로 들어온 프로세스가 CPU 소요시간이 더 작으면 새로운 프로세스가 CPU를 선점한다
• RR: Round-Robin -> 시분할
  • 시분할을 도입시킨 선점형 FCFS
  • 1 시분할보다 작을 경우 프로세스가 CPU를 자발적으로 놓아준다
  • 1 시분할보다 클 경우 타이머가 OS에게 인터럽트를 발생시킨다
    • 컨텍스트 스위치가 일어난 후 실행중이던 프로세스는 레디 큐의 마지막으로 위치시킨다
  • 시분할 단위(time quantum)가 무한인 상태: FCFS
• Priority-based
  • 우선순위가 높을 수록 먼저 실행하는 알고리즘
  • 기아 문제 생김(무한 대기 현상)
    • 레디큐에 있는 프로세스가 우선순위가 계속 가장 낮을 경우 무한 대기할 수 있음
    • 해결책: aging
      • 오랜 시간 기다린 프로세스의 경우 우선순위를 올려준다
• MLQ: Multi-Level Queue
  • 우선순위별 레디큐 분리
  • 가장 높은 우선순위 레디큐가 비워지면 다음 우선순위 레디큐 실행
• MLFQ: Multi-Level Feedback Queue
  • MLQ + 시분할

 

실시간 CPU 스케줄링

• Soft Realtime
  • 스케줄링된 실시간 프로세스가 실행된다는 보장없는 시스템
• Hard Realtime
  • 반드시 기간 안에 실행돼야 하는 시스템