OS-6-CPU Scheduling

CPU and I/O Burst Time

• CPU burst time: CPU 실행시간

• I/O burst time: I/O 작업 대기 시간

  

• 프로세스 특성에 따른 분류

  • I/O bound process
    • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
    • (many short CPU bursts)
  • CPU bound process
    • 계산 위주의 job
    • (few very long CPU bursts)

• 여러 종류의 process이 섞여 있기 때문에 CPU 스케줄링이 필요하다

  • Interactivce job에게 적절한 response 제공
  • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

CPU Scheduler & Dispatcher

• CPU Scheduler

  • Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다

• Dispatcher

  • CPU 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘긴다
  • 이 과정을 context switching(문맥 교환)이라고 한다

• CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다

  1. Running -> Blocked (예: I/O 요청하는 시스템 콜)

  2. Running -> Ready (예: 할당 시간 만료 timer interrupt)

  3. Blocked -> Ready (예: I/O 완료 후 인터럽트)

  4. Terminate

     1, 4에서 스케줄링은 nonpreemptive, 나머지는 preemptive

Scheduling Criteria

• CPU utilization(이용률) : CPU가 놀지 않고 사용하는 비율

• Throughput(처리량) : 주어진 시간안에 몇 개의 작업을 완료하였는가?

• Turnaround time(소요시간) : CPU를 대기하고 다 쓰고 반환하는 시간

• Waiting time(대기시간) : CPU를 대기하는 시간

• Response time(응답시간) : CPU를 처음으로 얻기까지 걸린 시간

  이용률, 처리량은 시스템 입장에서

  소요시간, 대기 시간, 응답 시간 프로세스(사용자) 입장에서 기준이다

Scheduling Algorithm

• CPU를 누구한테 줄 것 인가?
• CPU를 오래 잡고있으면 뺐을 것인가?

FCFS(First-Come First-Served)

• 프로세스 도착 순서대로 스케줄링 한다
• 오래걸리는 프로세스가 먼저 도착하면 전체 평균 응답시간이 느리다
  • 소요시간이 긴 프로세스가 먼저 도착할 경우
  • 소요시간이 짧은 프로세스가 먼저 도착할 경우

SJF (Shortest-Job-First)

• CPU burst time이 가장 짧은 프로세스를 먼저 스케줄링 한다

• SJF 종류

  • Nonpreemptive(비선점형)

    • CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음

  • Preemptive(선점형)

    • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
    • Shortest-Remaining Time-First(SRTF)이라고도 부른다

    SJF는 최적의 스케줄링 알고리즘으로 주어진 프로세스에게 minmum average waiting time을 보장한다

• 문제점

  • starvation : CPU burst time이 긴 프로세스는 CPU를 얻기 힘들다.

  • 실제 프로세스들의 CPU burst time 예측하기 어려움

    • 과거의 CPU burst time을 이용하여 추정만이 가능하다

      

      최근의 CPU burst time 측정값이 현재의 추정치에 영향을 더 미친다

Priority Scheduling

• 우선순위가 높은 것 먼저 스케줄링한다
• 선점형 비선점형 두가지 종류가 있다
• SJF도 priority = predicted next CPU burst time인 일종의 priority scheduling이다
• 문제점으로 우선순위가 낮은 프로세스가 실행되지 않는 Starvation 문제가 있다
• 따라서 Aging 방식을 통해서 프로세스의 우선순위를 시간이 지남에 따라 증가시켜 주는 방식으로 해결한다

Round Robin (RR)

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다
• 할당 시간이 지나면 프로세스는 선점(preempted) 당하고 ready queue의 제일 뒤에서 다시 줄 선다.
• n개의 프로세스가 ready queue에 할당 시간이 q time unit인 경우
  • 어떤 프로세스도 (n - 1)q time unit 이상을 기다리지 않는다
  • 응답시간이 빨리진다

time quantum이 많이 길어지면 FCFS Scheduling 처럼 동작하고

time quantum이 짧아지면 짧아질수록 context switching 오버헤드가 커진다

Multilevel Queue

• 우선순위가 높은 큐의 작업을 우선시 한다
• Ready queue를 여러 개로 분할
  • foreground (interactive)
  • background (batch - no human interactive)
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground - RR
  • background - FCFS
• 큐간의 스케줄링이 필요
  • Fixed priority scheduling
    • foreground에 작업을 우선으로 하고 foreground에 작업이 없으면 background 작업 시작
    • starvation의 가능성이 있다
  • Time slice
    • 각 큐에 CPU time을 적절한 비율로 할당한다
    • 80% foregound in RR, 20% to background in FCFS

Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동가능하다
• Scheduling
  1. new job이 queue Q0로 들어감
  2. CPU를 잡아서 할당 시간 8 milliseconds 동안 수행됨
  3. 8 milliseconds 동안 다 끝내지 못했으면 queue Q1으로 내려감
  4. Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms 동안 수행됨
  5. 16ms에서 끝내지 못한 경우 queue Q2로 쫓겨남

Multiple-Processor Scheduling

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

Real-Time Scheduling

• Hard real-time systems : 정해진 시간 안에 반드시 스케줄링해야 함
• Soft read-time systems : 정해진 시간에 반드시 스케줄링하지 않지만, 일반 프로세스에 비해 높은 prioty를 갖도록 해야함

Thread Scheduling

• Local Scheduling : User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
• Global Scheduling : Kernel level tthrea의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

참고

• 반효경 교수님 운영체제 강의