[OS] CPU Scheduling

CPU and I/O Bursts in Program Execution

프로그램 실행?

 CPU를 연속적으로 쓰는 단계와 I/O를 실행하는 단계가 반복되며 실행되는 것

*여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다!!

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

 

 

프로세스의 특성 분류

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

 

 

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(=강제로 빼앗지 않고 자진 반납)
• 나머지는 preemptive(=강제로 빼앗음) -> 현대적인 스케줄링방식

 

 

Scheduling Criteria

<시스템 입장에서의 성능 척도>

• CPU utilization (이용률) : CPU를 가능하면 바쁘게 해라
• Throughput (처리량) : 주어진 시간 동안에 몇개의 작업을 완료 했느냐

 

<프로세스 입장에서의 성능 척도>

• Turnaround Time (소요시간, 반환시간) : CPU를 사용하기위해 들어와서 I/O작업을 하러 나갈때까지 걸리는 시간
• Waiting Time (대기시간) : 순수하게 Ready queue에서 기다리는 시간을 합친 개념
• Response Time (응답시간) : Ready queue에 들어와서 최초로 CPU를 얻기까지 걸리는 시간

 

 

Scheduling Algorithms

FCFS (First-Come-First-Served)

프로세스가 도착한 순서대로 처리한다, 비선점형, 효율적이지 않음(Convoy effect)

 

SJF  (Shortest-Job-First)

CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
minimum average waiting time을 보장한다

 

Two Schemes:

• Nonpreemptive
  • 일단 CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음
• Preemptive
  • 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 갖는 새 프로세스가 도착하면 CPU를 빼앗김
  • SRTF(Shortest-Remaining-Time-First) 라고도 부른다

 

Non-Preemptive SJF 예시

 

Preemptive SJF 예시

 

다음 CPU Burst Time의 예측

과거의 CPU burst time을 이용해서 추정 (exponetial averaging)

 

Priority Scheduling

• A priority number(integer) is associated with each process
• highest priority를 가진 프로세스에게 CPU 할당
  • Nonpreemptive, Preemptive
• SJF는 일종의 priority scheduling 이다

 

• 문제점
  
  • Starvation(기아현상) : low priority processes may never execute
• 해결책
  • Aging : 오래 기다리면 우선순위를 높여주는 것

 

Round Robin (RR)

각 프로세스는 동일한 크기의 할당 시간 (time quantum)을 가진다

• 할당 시간이 지나면 프로세스는 선점(preemptive) 당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다
• n개의 프로세스가 ready queue에 있고 할당 시간이 q time unt 이면 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다
• Response Time(응답시간)이 빨라진다.

 

 

RR with Time Quantum = 20 예시

일반적으로 SJF 보다 average turnaround time이 길지만 response time은 더 짧다.

 

 

Multi Level Queue

• Ready Queue를 여러개로 분할
  • foreground (interactive)
  • background (batch - no human interaction)
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground - RR
  • background - FCFS
• 큐에 대한 스케줄링이 필요
  • Fixed priority scheduling
    • Serve all from foreground then from background
    • Possibility of Starvation
  • Time Slice
    • 각 큐에 CPU time을 적절한 비율로 할당

 

Muti Level Feedback Queue

• 프로세스가 다른 큐로 이동 가능
• Aging을 이와 같은 방식으로 구현할 수 있다
• Multilevel-feedback-queue scheduler를 정의하는 파라미터들
  • Queue의 수
  • 각 큐의 scheduling algorithm
  • Process를 상위 큐로 보내는 기준
  • Process를 하위 큐로 내쫓는 기준
  • Process가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

 

Multiple-Processor Scheduling

CPU가 여러개인 경우 스케줄린은 더 복잡해진다

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

 

Real-Time Scheduling

• Hard real-time systems : 정해진 시간 안에 반드시 끝내도록 스케줄링 해야 함
• Soft real-time systems : 일반 프로세스에 비해 높은 priority를 갖도록 해야 함 (deadline을 조금 어겨도 됨)

 

Thread Scheduling

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