📌 CPU 스케줄러(Scheduler)2

CPU 스케줄러

CPU를 쓰는 CPU burst, I/O를 쓰는 I/O burst 작업을 반복하게 된다.

Scheduling Algorithm

1. FCFS: First Come First Served (non-preemptive)

   • 먼저온 순서대로 CPU를 부여한다.
   • non-preemptive다.
   • 말그대로 선착순이다
   • 하지만 이 알고리즘은 효율적이지 못하다
   • 왜냐하면 앞에 긴 시간이 걸리는 프로세스가 있으면, 평균적으로 대기하는 시간이 길어지기 때문이다. 이를 Convoy Effect라고 한다.
   • Convoy Effect(호위 효과): short process behind long process

2. SJF: Shortest-Job-First

   • 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 필요
   • CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄함
   • Two Schemes
     • Nonpreeemptive
       • 일단 CPU를 잡으면 CPU burst가 끝날 때 까지 CPU를 선점 당하지 않는다.
     • Preemptive
       • 현재 수행중인 프로세스의 남은 CPU burst time보다 더 짧은 프로세스가 도착하면 CPU를 빼았긴다.
       • 이 방법을 Shortest-Remaining-time-First(SRTF)라고 한다.
   • SJF is optimal
     • 주어진 프로세스들에게 minimum average waiting time을 보장한다. (실제로 programmers에 해당 문제가 있음, 풀이를 보면 heapq를 이용함)
   • Problem
     • starvation: 긴 프로세스는 영원히 스케줄을 못얻을 수 있음
     • 누가 CPU를 길게 쓰는지 처음에는 알 수 없다.
       • 추정(estimate)만 가능하다
       • 또는 과거의 CPU burst를 이용하는 경우도 있다.
       • 이러한 예측값을 실제값과 예측값의 가중치(alpha)로 예측하게 되는데
       • 이를 계산하게 되면, 첫 예측값에 후속 term은 선행 term보다 적은 가중치 값을 갖을 수 밖에 없게 된다.
       • 즉 이전 영향들을 더 적게 반영한다. 이를 exponential averaging이라고 한다. (사실 지수 평활법과 같은 이치이다.)

3. Priority Scheduling

   • A Priority Number(Integer) is associated with process
   • Highest Priority를 가진 프로세스에게 CPU를 할당한다. Highest Priority는 숫자가 작을 수록 우선 순위가 더 높다는 것을 의미한다.
     • 이또한 nonpreemptive와 preemptive로 구현이 가능하다.
       • 우선 순위가 높은 process가 도착하면 빼았을 것인가?
         • NO! (nonpreemptive)
         • YES! (preemptive)
   • Shortest-Job-First은 Highest Priority가 Predicted next burst time 인 것이다.
   • Problem: The low priority processes may never execute
   • Solution: Aging, as time processes increase the priority of the process

4. Round Robin (실제로 제일 많이 사용하는 CPU 스케줄링 알고리즘)

   • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖는다. (일반적으로 10-100 millisecond)
   • 할당 시간이 끝나면 프로세스는 선점(preemptive)당하면 ready queue에 제일 뒤에 가서 줄을 선다.
   • n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
     • 그 어떤 프로세스도 (n-1)q time unit 이상을 기다리지 않는다.
   • Performance
     • q large: FCFS
     • q small: context switch 오버헤드가 커진다.
   • Response Time을 줄일 수 있다.
   • 대기 시간이 CPU burst time에 비례한다.

5. Multilevel Queue

   • Ready Queue를 여러 개로 분할. 여기서는 foreground와 background로 표현

     • foreground (interactive: 짧은 것)
     • background (batch - no human interactive: 긴 것)

   • 각 큐는 독립적인 스케줄링 알고리즘을 갖음

     • foreground - RR
     • background - FCFS

   • 큐에 대한 스케줄링이 필요

     • Fixed priority Scheduling

       • Save all from foreground then from background / 모든 foreground의 처리가 끝났을 때 background 처리가 시작된다.
       • possibility of starvation / 이 때 background 쪽에서는 starvation 가능성이 있음.

     • Time Slice

       • 각 queue에 CPU 타임을 적절한 비율로 할당 / background를 실행하기 위해서 설정
       • Eg..80% to foreground in RR, 20% to background in FCFS

     • EX) 각각은 어느정도 우선순위를 나타내는 Queue 들임

       high priority

       • System process
       • interactive process
       • interactive editing process
       • Batch process
       • Student process

       low priority

   1. Multilevel Feedback Queue

      • 프로세스가 다른 큐로 이동 가능

      • 에이징을 위와 같은 방식으로 구현할 수 있다.

      • Multilevel Feedback Queue scheduler를 정의하는 파라미터들

        • Queue의 수

        • 각 큐의 스케줄링 알고리즘

        • Process를 상위 큐로 보내는 기준

        • Process를 하위 큐로 보내는 기준

        • 프로세스가 CPU 서비스를 받으려 할 때 큐를 결정하는 기준

          Ex) 1

          high

          • quantum 8: 모든 프로세스는 여기에 담김 8을 실행하고 프로세스가 끝나면 끝이고 아니면 아래 큐에 담긴
          • quantum 16
          • FCFS

          low

        ---

        Ex) 2

        Three Queue

        • Q0 - quantum 8
        • Q1 - quantum 16
        • Q2 - FCFS

        Scheduling

        • New job이 Q0에 들어감
        • CPU를 잡아서 할당 시간 8 milliseconds 동안 수행됨
        • 8 milliseconds 동안 다 수행을 못한 Q1에 들어감
        • Q1을 잡아서 CPU에 할당된 시간이 16ms를 실행함
        • 16ms 안에 끝내지 못하면 Q2로 쫓겨남

Multi - processor Scheduling

• CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
• Homogeneous processor인 경우
  • Queue에 한줄로 세워 각 프로세스가 알아서 꺼내 갈 수 있도록 할 수 있다.
  • 반드시 특정 프로세스에서 수행해야 하는 프로세스가 있는 경우에는 문제가 더욱 복잡해진다.
• Loading Sharing
  • 일부 프로세스에서 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요
  • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 법
• Sysmmetric Multiprocessing (SMP)
  • 각 프로세스가 각자 알아서 스케줄링 결정
• Asymmetric Multiprocessing
  • 하나의 프로세스가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세스는 거기에 따름