[OS] CPU 스케줄링

CPU and I/O Bursts in Program Execution

• CPU burst : CPU를 가지고 기계어를 실행하는 단계
• I/O burst : 시간이 좀 걸리는 I/O 작업을 하는 단계

CPU-burst Time의 분포

프로세스의 특성 분류

프로세스는 그 특성에 따라 두 가지로 나눔

• I/O bound job : CPU를 짧게 쓰는 프로그램
  • 주로 사람하고 interaction하는 프로그램이 많음 -> CPU를 빨리 줘야함
  • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
  • many short CPU bursts
• CPU bound job : CPU를 길게 쓰는 프로그램
  • 복잡한 계산을 하는 프로그램 -> 5초 있다가 CPU를 줘도 문제되지 않음
  • 계산 위주의 job
  • few very long CPU bursts

시스템에 여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요함

• Interactive job(= I/O bound job)에게 적절한 response 제공 요망
  • CPU bound job보다 I/O bound job에게 CPU를 먼저 할당 해줘야함
    -> CPU를 짧게 쓰고 돌려주기 때문에
• CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

CPU Scheduler & Dispatcher

CPU Scheduler

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

Dispatcher

• CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘김
• 이 과정을 context switch(문맥 교환)라고 함

CPU 스케줄링이 필요한 경우는 프로세스에게 아래와 같은 상태 변화가 있는 경우

1. Running -> Blocked (예: I/O 요청하는 시스템 콜)
2. Running -> Ready (예: 할당시간만료로 timer interrupt)
3. Blocked -> Ready (예: I/O 완료후 인터럽트)
4. Terminate (예: 프로세스가 종료되었을 때)

• 1, 4에서의 스케줄링은 nonpreemptive(= 강제로 빼앗지 않고 자진 반납)
• 2, 3에서의 스케줄링은 preemptive(= 강제로 빼앗음)
• CPU 스케줄링은 크게 nonpreemptive와 preemptive로 구분됨

Scheduling Criteria

Performance Index(= Performance Measure, 성능 척도)

CPU 스케줄링 알고리즘 중에 어떤게 좋은지 판단할 수 있는 방법

• CPU utilization(이용률)
  • keep the CPU as busy as possible
  • CPU 이용 시간 / 전체 시간 -> 높을 수록 좋음
• Throughput(처리량)
  • of processes that complete their execution per time unit
  • 처리량 / 단위 시간 -> 높을 수록 좋음
• Turnaround time(소요시간, 반환시간)
  • amount of time to execute a particular process
  • CPU burst에 들어와서 I/O burst로 나갈 때까지 전체 시간
    • CPU 사용 시간 + CPU 기다린 시간(Ready queue에 기다린 시간)
• Waiting time(대기 시간)
  • amount of time a process has been waiting in the ready queue
  • CPU 기다린 시간의 합
    • CPU 얻었다가 빼앗겼다가 하면서 Ready queue에서 기다린 총 시간
• Response time(응답 시간)
  • amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)
  • 프로세스가 최초로 CPU를 얻기까지 걸리는 시간
    • Ready queue에서 처음 CPU 얻기까지의 시간
    • 프로세스가 처음 시작해서 처음으로 CPU 얻은 시간은 아님
• 시간은 짧을 수록 좋음

Scheduling Algorithms

FCFS (Fist-Come First-Served)

CPU 사용시간이 긴 프로세스가 먼저들어온 경우

CPU 사용시간이 짧은 프로세스가 먼저들어온 경우

• Convoy effect
  • long process가 먼저 도착하는 바람에 short process가 오래 기다려야 되는 현상

SJF (Shortest-Job-First)

• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄

Two schemes:
1. Nonpreemptive

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

2. Preemptive

• 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
• 이 방법을 Shortest_Remaining_Time_First(SRTF)이라고도 부름
  • 남은 시간이 제일 짧은 프로세스에게 CPU를 줌

• SJF is optimal -> SRTF
  • 주어진 프로세스들에 대해 minimum average waiting time을 보장
  • 어떠한 CPU 스케줄링 알고리즘 보다 SRTF가 평균 대기 시간이 가장 짧음

Problem

• Starvation 현상 발생
• CPU burst time을 누가 짧게 쓰고 길게 쓰는지 알 수 없음

Solution

• 예측을 통해 해결할 수 있음

다음번 CPU Burst Time의 예측

• 추정(estimate)만이 가능함
• 과거의 CPU burst time을 이용해서 추정

Exponential Averaging

• 직전 CPU burst를 많이 반영하고 예전꺼는 적게 반영함

Priority Scheduling

• a priority number(integer) is associated with each process
• highest priority(높은 우선순위)를 가진 프로세스에게 CPU 할당
  • smallest integer = highest priority
  • Preemptive
  • nonpreemptive
• SJF는 일종의 priority scheduling
  • priority = predicted next CPU burst time

Problem

• Starvation : low priority processes may never execute

Solution

• Aging : as time progresses increase the priority of the process
  • 기다리는 시간이 오래된 프로세스는 우선순위를 올려줌

Round Robin (RR)

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
  (일반적으로 10~100 milliseconds)
• 할당 시간이 지나면 프로세스는 선점(preempted)당하고 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 오버헤드가 커짐

Example: RR with Time Quantum = 20

• 일반적으로 SJF보다 average turnarround time이 길지만 response time은 더 짧음

Multilevel Queue

• CPU는 하나 인데 queue가 여러 개 임
• Ready queue를 여러 개로 분할
  • forground(interactive) -> short job
  • background(batch - no human interaction) -> long job
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • forground - RR
  • background - FCFS
• 큐에 대한 스케줄링이 필요
  • Fixed priority scheduling -> 우선순위 변경 불가능
    • serve all from foreground then from background
    • possibility of starvation
  • Time slice
    • 각 큐에 CPU time을 적절한 비율로 할당
    • ex) 80% to foreground in RR, 20% to background in FCFS

Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동 가능 -> 우선순위 변경 가능
• 에이징(aging)을 이와 같은 방식으로 구현할 수 있음
• Multilevel-feedback-queue scheduler를 정의하는 파라미터들
  • Queue의 수
  • 각 큐의 scheduling algorithm
  • Process를 상위 큐로 보내는 기준
  • Process를 하위 큐로 내쫒는 기준
  • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

Example of Multilevel Feedback Queue

• Three queues:
  • Q0 - time quantum 8 milliseconds
  • Q1 - time quantum 16 milliseconds
  • Q2 - FCFS
• Scheduling
  • new job이 queue Q0로 들어감
  • CPU를 잡아서 할당 시간 8 milliseconds 동안 수행됨
  • 8 milliseconds 동안 다 끝내지 못했으면 queue Q1으로 내려감
  • Q1에 줄서서 기다렸다가 CPU를 잡아서 16 ms 동안 수행됨
  • 16 ms에 끝내지 못한 경우 queue Q2로 쫒겨남

위 내용 까지는 CPU가 1개 있는 환경에서의 스케줄링
뒤에 나오는 스케줄링은 좀 특수한 경우

Multiple-Processor Scheduling

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

Real-Time Scheduling

• Hard real-time systems
  • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
• Soft real-time computing
  • Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함

Thread Scheduling

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

Algorithm Evaluation

알고리즘을 평가할 수 있는 방법

• Queueing models
  • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산

• Implementation (구현) & Measurement (성능 측정)
  • 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
  • ex) 리눅스의 CPU 스케줄링하는 코드를 내가 작성한 알고리즘으로 넣어서 같은 하드웨어 조건에서 어떤것이 더 좋은지 성능을 측정 비교
• Simulation (모의 실험)
  • 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교

reference

운영체제 - 이화여자대학교