CPU 스케줄링

CPU 스케줄링

정의

CPU 코어 하나는 하나의 프로세스를 처리할 수 있다. CPU 코어가 작업을 모두 마치기 전까지, 프로세스는 대기하고 있는다. CPU 작업이 끝나면, 레디 큐에서 대기하는 프로세스 중 하나를 선택하여 작업을 해야하는데 이 때 선택 절차는 CPU 스케줄러에 의해 수행된다.

프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다. 프로세스는 두 상태를 교대로 왔다갔다 하면서 작업이 처리된다. 초기에는 CPU 버스트로 시작되고, 뒤이어 I/O 버스트가 발생한다.

CPU 스케줄링 결정은 다음의 네 가지 상황에서 발생할 수 있다.

1. 프로세스가 실행 상태에서 대기 상태로 전환될 때
2. 프로세스가 실행 상태에서 준비 상태로 전환될 때
3. 프로세스가 대기 상태에서 준비 상태로 전환될 때
4. 프로세스가 종료될 때

이때, 1번과 4번에서는 비선점형 스케줄링이 발생한다. 왜냐하면, 1번의 경우 I/O 작업 혹은 외부 이벤트 종료를 기다려야 하기 때문에 스스로 대기 상태로 전환되고 4번의 경우 작업이 모두 완료됐기 때문에 스스로 종료 상태로 전환된다.

반면에 2번과 3번에서는 선점형 혹은 비선점형 스케줄링이 발생한다. 2번의 경우 시분할이 끝나서 스스로 준비 상태로 갈 수 있지만, 레디 큐에 우선순위가 높은 작업이 존재하여 강제로 준비 상태로 전환될 수 있다. 3번의 경우 준비 상태로 들어갈 때, 현재 실행 중인 작업이 끝날 때까지 대기하거나 현재 실행 중인 작업보다 우선순위가 높아 CPU를 선점할 수 있다.

기준

CPU 스케줄링 알고리즘을 비교하는 기준은 여러가지가 있다.

• CPU 이용률(utilization) : 실제 시스템에서는 40%에서 90% 범위를 가져야 함
• 처리량(throughput) : 단위 시간당 처리량
• 총처리 시간(turnaround time) : 레디 큐에서 대기 시간 + CPU 실행 시간 + I/O 시간
• 대기 시간(waiting time) : 레디 큐에서 대기하는 시간
• 응답 시간(response time)

→ CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다.

종류

• FCFS

  • 선입선출, 비선점형
  • 대기 큐에 들어갈 때, PCB를 큐의 끝에 연결
  • 작업시간이 긴 작업이 먼저 실행될 경우 작업시간이 짧은 작업의 대기 시간이 길어짐 → 호위 효과(Convoy Effect)

• SJF

  • 작업 시간이 짧은 작업이 먼저 실행

  • 다음 작업 시간을 알 방법이 없기 때문에 구현이 어려움 → 과거의 기록을 통해 예측

    

    • tn : n번째 실제 측정된 CPU 버스트 시간
    • τn : n번째 예측값
    • α : 가중치 (0 ≤ α ≤ 1)

  • 비선점형이 될 수도 있고 선점형이 될 수도 있음

    • 비선점형의 경우 작업 시간이 더 짧은프로세스가 도착했을 때, 현재 실행하고 있는 프로세스가 작업이 끝나도록 허용
    • 선점형의 경우 작업 시간이 더 짧은 프로세스가 도착했을 때, CPU를 점유 → SRTF

• RR

  • 시분할을 통해 프로세스를 처리, 선점형

  • 일반적으로 10에서 100밀리초 동안 작업 처리하며, 원형 큐를 통해 동작

  • 작업 시간이 시분할보다 작은 경우 자발적으로 CPU에서 나옴

  • 작업 시간이 시분할보다 큰 경우 타이머가 끝난 후 OS에서 인터럽트가 발생하여 컨텍스트 스위칭 발생

  • 시분할의 크기에 따라 성능이 좌지우지

    

    • 짧게 잡으면 컨텍스트 스위치기 빈번하게 발생하여 성능 저하
    • 길게 잡으면 작업 처리량이 줄어듦

• Priority Scheduling

  • 우선순위에 의해 프로세스가 할당
  • 우선순위는 내부적 또는 외부적으로 정의될 수 있음
    • 내부적 : 시간 제한, 메모리 요구, 열린 파일의 수, 평균 I/O 버스트의 평균 CPU 버스트에 대한 비율
    • 외부적 : 프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 유형과 양, 작업을 후원하는 부서, 정치적인 요인
  • 우선순위가 낮아 우선순위가 높은 작업에 계속 밀려 작업이 처리되지 못하는 기아 현상이 발생할 수 있음
  • 이를 해결하기 위해 오랫동안 대기하는 작업들의 우선순위를 점진적으로 증가시키는 에이징 기법이 존재

• MLQ(Multi-Level Queue)

  

  • 대기 큐에 우선순위가 높은 작업을 찾기 위해 O(n) 검색이 필요할 수 있음
  • 우선순위에 따라 큐를 배치하여 작업을 처리한다면, 검색 비용을 개선할 수 있음
  • 각 큐는 독립적인 스케줄링 알고리즘을 가질 수 있음
  • 상위 큐에 작업이 있으면 무조건 먼저 실행되고 이로 인해 하위 큐에서 기아 현상이 발생할 수 있음
  • 큐별로 CPU 시간을 일정 비율로 분배할 수 있음 (상위 큐 80, 하위 큐 20)

• MLFQ(Multi-Level Feedback Queue)

  

  • MLQ와 달리, 작업들이 큐들 사이를 이동하는 것을 허용
  • 프로세스가 들어오면 가장 높은 우선순위 큐에 진입
    • 시분할을 모두 사용하면 한 단계 낮은 큐로 이동
    • 시분할이 끝나기 전에 I/O로 빠지면 현재 큐를 유지
  • 일반적으로 우선순위가 낮은 큐에 시분할 시간을 더 길게 부여
  • 기아 현상 방지를 위해 에이징 적용이 가능

디스패처

CPU 스케줄링 기능에 포함된 요소로 CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이며 다음 작업을 진행한다.

• 프로세스 컨텍스트 스위칭
• 사용자 모드 전환
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동

즉, 컨텍스트 스위칭가 발생할 때 호출되고 가능한 빠르게 수행되어야 한다. 왜냐하면 컨텍스트 스위칭 과정에서 프로세스 정지 및 재실행이 발생하고 이때 지연시간이 발생하기 때문이다. 이 지연 시간을 디스패치 지연이라고 한다.

컨텍스트 스위칭이 얼마나 자주 발생하는가는 vmstat 를 통해 확인할 수 있다.