[운영체제] 3. CPU 스케줄링

OS? Oh Yes! 책을 바탕으로 학습한 내용입니다.

장기 스케줄링

어느 작업을 커널에 등록시켜 프로세스로 만들어 줄 것인가를 결정하는 것으로 Job Scheduling이라고도 한다.

중기 스케줄링

보류 상태의 프로세스들 중에서 어느 프로세스에게 메모리를 할당해 줄 것인가를 결정한다. 스왑인 결정

단기 스케줄링

준비 상태의 프로세스들 중에서 어느 프로세스에게 CPU를 할당해 줄 것인가를 결정한다. process scheduler 또는 dispatcher에 의해서 수행된다.

스케줄링의 지표

• Response Time 요청 후 최초 출력이 발생하기까지의 시간
• Turn-around Time 요청 후 완료될 때까지의 시간

Nonpreemptive 비선점 스케줄링

• FCFS(First Come First Service)
  • 먼저 도착한 프로세스에게 CPU를 할당한다.
  • 평균 응답 시간이 길어 대화식 시스템에 적합하지 않다.

• SPN(Shortest Process Next) / SJF(Shortest Job First)
  • 준비 큐에서 가장 짧은(CPU 요구량이 가장 적은) 프로세스에게 CPU 할당.
  • starvation 발생가능, aging 기법으로 해결
  • 실행 전에는 실행 시간을 알 수 없다. 지수 평균 방법을 통해 추측한다.

• HRRN(Highest Response Ratio Next)
  • 준비 큐에 있는 프로세스들 중에서 응답률이 가장 높은 프로세스에게 CPU를 할당한다. 응답률 = (대기시간 + CPU 요구량) / CPU 요구량
  • starvation 보완을 위해 aging

Preemptive 선점 스케줄링

• SRT(Shortest Remaining Time)
  • 준비 큐에서 완료까지 남은 시간이 가장 짧은 것에 CPU를 할당
  • 남은 실행시간 계산, 잦은 문맥교환 발생 우려의 문제가 있다.
  • 너무 잦은 문맥교환 문제를 해결하기 위해 임계 값을 설정하고 남은 시간 차이가 임계 값을 넘지 않을 경우에는 선점되지 않도록 하는 보완책이 있다.

• RR(Round-Robin)
  • FCFS를 기반으로 하되 각 프로세스가 한 번에 사용할 수 있는 Time Quantum(시간 할당량)을 정하고 초과시 시간 종료 인터럽트를 일으킨다.
  • 문맥교환의 오버헤드
  • 대화식, 시분할 시스템에 적합
  • CPU bound 프로세스 우대(I/O bound 프로세스는 입출력 인터럽트로 인한 남은 시간 할당량을 보상받지 못한다.)

• Virture Round-Robin
  • 입출력을 마친 프로세스가 들어가는 준비 큐를 따로 하나 두고 우선순위를 더 높게 책정한다. 이 큐에서 CPU를 할당 받으면 이전에 남긴 시간 할당량 만큼만 주도록 한다.

• Multi-level Queue
  • 우선순위의 개수만큼 큐를 만들고 프로세스는 자신의 우선순위에 해당하는 준비 큐로 들어간다.
  • 정적 우선순위를 사용할 때 적합하다.

• MFQ(Multi-level Feedback Queue)
  • 우선순위의 개수만큼 큐를 만들고 각 준비 큐 마다 다른 CPU 시간 할당량을 가지게 한다. 우선순위가 높은 큐일수록 시간 할당량은 작다. 큐에서의 시간 할당량을 모두 사용했을 때 우선순위를 낮춘다.(한 단계 아래의 큐에 넣는다.) I/O 인터럽트의 경우에는 우선순위를 높인다.(한 단계 위의 큐에 넣는다.)
  • 기본적으로 큐는 FCFS를 따르며 마지막 큐는 RR을 따른다.
  • 시간 할당량을 사용하는 동안에는 선점되지 않는다.
  • 해당 단계에서 순환할 수 있는 횟수를 주거나, I/O 인터럽트에 따른 우선순위 상승폭을 더 크게 책정하거나 aging을 하는 등의 보완법이 있다.

• Fair-share
  • 프로세스들의 특성이나 중요도에 따라 몇 개의 그룹으로 나누고 그룹 별 시간할당량을 다르게 할당한다.
  • 특정 그룹에 속한 프로세스의 과도한 CPU 사용은 다른 그룹에 까지 영향을 끼치지 않는다.

실시간 스케줄링

• Hard Realtime 마감시한 내에 완료되지 않으면 치명적인 결과를 초래하는 시스템
• Soft Realtime 마감시한 내에 완료되지 않으면 피해는 발생하지만 운영은 가능한 시스템

• RM(Rate Monotonic)

  • 각 프로세스들은 서로 독립적이고 주기적으로 수행되는 환경에서 각 프로세스의 마감시한은 각자의 주기와 같다고 가정하고 주기가 짧을수록 높은 우선순위를 받는다.

  • 정적 스케줄링, 선점 스케줄링

  • 아래 식을 만족하면 RM 기법으로 모든 프로세스의 마감시한을 맞출 수 있는 스케줄링이 가능하다.

    U CPU 사용률
    P 주기
    C 크기 (수행시간)
    
    U = U1 + U2 + ... + Un
      = C1/P1 + C2/P2 + ... + Cn/Pn <= n(2^1/2 - 1)

  • 새로운 프로세스가 추가되면 바로 적응하지 못하고 전체 스케줄링을 다시 해야한다.

• EDF(Earliest Deadline First)

  • 마감시한이 가까울수록 우선순위를 높게 부여한다.

  • 동적 스케줄링, 선점 스케줄링

  • 아래 식을 만족하면 EDF 기법으로 가능한 스케줄이 존재한다.

    P 주기
    C 크기 (수행시간)
    
    C1/P1 + C2/P2 + ... + Cn/Pn <= 1

RM과 EDF는 프로세스가 상호 독립적이라는 가정을 하고 있다. 따라서 프로세스 간의 통신이 있는 경우에는 적용할 수 없다.

윈도우에서의 스케줄링

• 스레드 단위로 CPU를 할당하는 우선순위에 의한 선점 스케줄링
• 일반 클래스, 실시간 클래스로 구분하여 일반 클래스는 MFQ 실시간 클래스는 다단계 큐로 구현된다.
• 실시간 클래스의 다단계 큐 각각은 RR 방식이다.
• 시간 종료 인터럽트는 우선순위 하향, I/O 인터럽트는 상향