[OS] CPU Scheduling

프로세스 특성 분류

CPU burst와 I/O burst를 하는 단계가 번갈아가면서 사용된다.

I/O-bound process

• CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
• many short CPU bursts

CPU-bound process

• 계산 위주의 job
• few very long CPU bursts

여러 종류의 job(=process, I/O bound job과 CPU bound jop)이 섞여 있기 때문에 CPU Scheduling(누구에게 얼만큼 시간을 주고 뺏을 것인가)이 필요하다.

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

CPU Scheduler & Dispatcher

둘다 하드웨어가 아니라 운영체제 안에 있는 것이다.

CPU Scheduler

참고(프로세스)

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

Dispatcher

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

스케줄링이 필요한 경우

다음과 같은 상태 변화가 있는 경우

1. Running -> Blocked (ex. I/O 요청하는 시스템 콜)
2. Running -> Ready (ex. 할당 시간 만료로 timer interrupt)
3. Blocked -> Ready (ex. I/O 완료 후 인터럽트)
4. Terminate

1, 4 : nonpreemptive (-> 강제로 빼앗지 않고 자진 반납)
2, 3 : preemptive (-> 강제로 빼앗음)

Scheduling Criteria

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

시스템 측면(H/W, OS)

• CPU utilization(이용률) : CPU를 가능한 바쁘게 일을 시키는 것
• Throughput(처리율) : 주어진 수행시간동안 몇 개의 프로세스를 완료했는지

프로세스 측면

• Turnaround time(소요시간, 반환시간)
  CPU를 가져온 후 다 쓰고 나갈 때까지의 시간
  프로세스가 끝나는 시간이 아니라 CPU 수행을 끝나는 시간
• Waiting time
  ready 큐에서 줄서서 기다리는 시간
  매번 CPU를 기다리는 시간의 총합
• Response time
  ready 큐에서 최초로 CPU를 얻기까지의 시간
  최초의 CPU를 얻기까지의 시간으로 waiting time과 차이점이 있음.

Scheduling Algorithms

FCFS(First-Come First-Service)

• 먼저 온 순서대로 처리해주는 알고리즘
• Convoy effect : 긴 프로세스가 앞에 오면 짧은 프로세스는 오래 기다리는 현상
• 효율적이지 않다.
• Nonpreemptive

SJF(Shortest-Job-First)

• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
• 2가지 방식
  • Nonpreemptive
    일단 CPU를 잡으면 CPU burst가 완료 될 때까지 CPU를 선점 당하지 않음
  • Preemptive
    더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 뺏김
    이 방법을 Shortest Remaining Time First(SRTF)이다.
    Average waiting time이 제일 적어지는 알고리즘이다. (SRTF)
• SJF is optimal
  • 주어진 프로세스들에 대해 minimum average waiting time 보장

Priority Scheduling

• 가장 높은 priority를 가진 프로세스에게 CPU 할당
• 2가지 방식(preemptive, nonpreeptive)
  • 우선순위 높은 프로세스가 오면 CPU 뺏을 수 있냐의 관점
• SJF도 일종의 priority scheduling이다.
  priority = predicted next CPU burst time
• Problem : Starvation(기아 현상) - 시간이 긴 프로세스가 CPU를 못 얻을 수 있음
• Solution : Aging - process가 시간이 지남에 따라 우선순위를 조금씩 높여가는 것이다.

RR(Round Robin)

• 현대 스케줄링의 기반
• 선점형 스케줄링(preemptive)
• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (10 ~ 100ms)
• 할당 시간이 지나면 프로세스는 선점 당하고 ready queue에 제일 뒤로 줄을 선다.
• 일반적으로 SJF보다 average turnaround time이 길지만, response time이 빨라진다.
• 기다리는 시간은 본인의 CPU 타임에 비례하게 된다.
• n개의 프로세스가 ready queue에 있고, 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
  👉 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
• [성능] 할당 시간을 크게 잡으면 FCFS(FIFO), 작게 잡으면 context switch 오버헤드가 커진다.

Multilevel Queue

• 작업을 그룹화하여 여러 큐 관리 및 할당
• Ready queue를 여러 개로 분할
  • foreground(interactive)
  • background(batch - no human interaction)
• 각 큐는 독립적인 스케줄링 알고리즘을 가진다.
  • foreground - RR
  • background - FCFS
• 큐에 대한 Scheduling이 필요하다.
  • Fixed priority scheduling
    • 우선순위가 높은 순으로 부여, starvation 가능성 O
    • background보다 foreground에게 더 높은 우선순위를 부여
  • Time slice
    • CPU time을 적절한 비율로 할당
    • ex) foreground 80% in RR, background 20% in FCFS

Multilevel Feedback Queue

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

처음에는 할당시간이 제일 작은 RR의 큐에 할당된다.
시간이 끝나면 낮은 큐로 옮긴다.
프로세스 시간이 짧을 경우 우선순위가 높아지는 방식 길수록 점점 밑 큐로 쫓겨 난다.

Multiple-Processor Scheduling

• CPU가 여러 개인 경우, 스케줄링은 더욱 복잡해진다.

• Homogeneous processor인 경우(동일 프로세서)

  • queue를 한줄로 세워서 각 프로세서가 알아서 꺼내가게 해야한다.
  • 반드시 특정 프로세서가 처리해야할 경우도 있는데 더 복잡해진다.
  • ex. 헤어디자이너가 여러 명 있는데 특정 디자이너에게 자르기

• Load Sharing

  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요
  • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법

• Symmetric Multiprocessing(SMP)

  • 각 프로세서가 각자 알아서 스케줄링 결정

• Asymmetric Multiprocessing

  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따르는 방식

Real-Time Scheduling

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

Thread Scheduling

• Local Scheduling : User level thread 사용자 프로세스가 직접 thread를 관리한다.
  -> OS, 커널이 관여하지 않는다.
• Global Scheduling : Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정한다.
  -> OS가 관여(조정)

Algorithm Evaluation

• Queueing models
  확률분포로 주어지는 arriaval rate(도착률)와 service rate(처리률) 등을 통해 perfomance index
• Implementation(구현) & Measurement(성능 측정)
  실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정비교
• Simulation(모의 실험)
  위의 실측방법보다 간단한 방법
  모의 프로그램으로 작성후 trace(input data)를 입력으로 하여 결과 비교(ATT값 내보기)
  cf) ATT: Averaget Turnaround Time