Machine Learning Book Reviews Github

CPU Scheduling

CPU and I/O Bursts in Program Execution

CPU-burst Time의 분포

Process 의 특성 분류

Process는 그 특성에 따라 다음 두 가지로 나눈다

  • CPU bound job

    • CPU를 길게 쓰고, I/O를 짧게 쓰는 작업

      • few very log CPU bursts

    • 계산 위주의 job

    • ex) 과학적 연산 등 연산이 오래 걸리는 작업을 수행하는 경우

  • I/O bound job

    • CPU를 짧게 쓰고, I/O를 길게 쓰는 작업

      • many short CPU bursts

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

    • ex) 사람과 Interaction을 많이 하는 경우

CPU Scheduling의 필요성

  • 여러 종류의 job(=process)이 섞여 있기 때문에 CPU Scheduling 이 필요하다

    • Interactive job에게 적절한 response 제공 요망

      • 사람과 Interaction을 하는 job

    • CPU와 I/O 장치 등 system 자원을 골고루 효율적으로 사용

  • I/O bound job이 CPU를 빨리 얻을 수 있도록 하는 목적

    • CPU를 먼저 주어야 빨리빨리 CPU를 쓰고 나가기 때문

    • 사람과 interaction 하기 때문에 빠른 응답성 제공 필요

    • 쓰고 나서는 바로 I/O 작업이 아루어지는데, CPU를 못주고 있으면

CPU Scheduler & Dispatcher

CPU Scheduler

  • 운영체제 코드 중 CPU scheduling을 하는 code

  • Ready 상태의 process 중에서 CPU를 줄 process를 고른다

Dispatcher

  • CPU의 제어권을 CPU Scheduler에 의해 선택된 process에게 넘긴다

  • 이 과정을 context switch 라고 한다

CPU Scheduling이 필요한 경우

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

  1. Running → Blocked (e.g. I/O 요청하는 system call)

  2. Running → Ready (e.g. 할당 시간 만료로 timer interrupt)

  3. Blocked → Ready (e.g. I/O 완료 후 interrupt)

  4. Terminate

→ 1, 4 에서의 scheduling은 nonpreemptive (= 강제로 빼앗지 않고 자진 반납)

→ 그 외 다른 scheduling은 preemptive (= 강제로 빼앗음)

Scheduling Criteria

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

  • CPU Utilization (이용률)

    • keep the CPU as busy as possible

    • CPU를 놀게 하지 않고 이용률은 높을 수록 좋다

  • Throughput (처리량)

    • number of processes that complete their execution per time unit

    • 처리량은 많을수록 좋다

  • Turnaround Time (소요 시간, 반환 시간)

    • amount of time to execute a particular process

    • CPU burst를 하고 나서, I/O burst를 하러 나가기까지 전체 시간

      • ready queue에서 기다린 시간 + 실제로 CPU를 쓴 시간

  • Waiting Time (대기 시간)

    • amount of time a process has been waiting in the ready queue

    • 처음으로 기다리는 시간이 아닌, CPU를 쓰러 와서 기다린 전체 시간의 합

  • 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를 쓰러 들어와서 처음 쓰기까지의 시간을 뜻함

      • process가 시작해서 처음 CPU를 쓰기 까지의 시간 아님!!

Scheduling Algorithms

FCFS (First-Come First-Served)

  • 설명

    • ready queue에 먼저 들어온 process 순으로 실행한다

  • 문제점

    • Convoy effect (호위 효과)

      • short process behind long process

      • 오래 걸리는 process가 먼저 도착해서 CPU를 오래 쓰는 탓에 짧게 걸리는 process가 오래 걸리게 되는 것

SJF (Shortest Job First)

  • 설명

    • 각 process의 다음번 CPU burst time 을 가지고 scheduling에 활용

    • CPU burst time이 가장 짧은 process를 제일 먼저 schedule

      • CPU를 가장 짧게 쓰려는 job에게 제일 먼저 CPU를 주는 것

  • 종류

    Two schemes

    • Non-preemptive (비선점)

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

    • Preemptive (선점)

      • 현재 수행중인 process의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 process가 도착하면 CPU를 빼앗김

      • 이 방법을 Shortest-Remaining-Time-First (SRTF) 라고도 부름

  • 특징

    • SJF is optional

      • 주어진 process들에 대해 minimum average waiting time 을 보장한다

      • 대기 시간 측면에서 최적이다

    • A priority number (integer) is associated with each process

      • high priority를 가진 process에게 CPU 할당

        • (smallest integer = high priority)

    • SJF는 일종의 priority scheduling이다

      • priority = predicated next CPU burst time

  • 문제점

    • Starvation

      • low priority processes may never executed

    • Aging

      • as time progresses increase the priority of the process

  • 다음 CPU Burst Time 의 예측

    다음번 CPU burst time을 어떻게 알 수 있을까? (input data, branch, user …)

    • 추정만이 가능하다

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

Priority Scheduling

A priority number (integer) is associated with each process

  • 특징

    • highest priority 를 가진 process에게 CPU를 할당

      • smallest integer == highest priority

    • SJF는 일종의 priority scheduling이다

  • 문제점

    • Starvation : low priority process may never execute

  • 해결

    • Aging : as time progresses, increase the priority of the process

Round Robin (RR)

  • 특징

    • 각 process 는 동일한 크기의 할당 시간 (time quantum) 을 가진다

      • 일반적으로 10 - 100 ms

    • 할당 시간이 지나면 process는 선점당하고, ready queue의 제일 뒤에 가서 다시 줄을 선다

    • n개의 process가 ready queue에 있고, 할당 시간이 q time unit인 경우, 각 process는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다

      → 어떤 process도 (n-1)q time unit 이상 기다리지 않는다

  • Performance

    • q large → FCFS

    • q small → context switch overhead가 커진다

  • 장점

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

Multilevel Queue

  • Ready queue를 여러개로 분할

    • foreground

      • interactive job

    • background

      • batch job (no human interaction)

  • 각 queue는 독립적인 scheduling algorithm을 가짐

    • foreground

      • RR

    • background

      • FCFS

  • Queue에 대한 scheduling이 필요

    각 queue 마다 wait을 주는 것

    • Fixed priority scheduling

      • 두 개의 우선 순위 그룹을 나눈다 (foreground, background)

      • serve all from foreground then from background

        • foreground에 속한 process들이 먼저 모두 실행되고 나면, 그 다음에 background group에 속한 process들을 실행한다

      • possibility of starvation

    • Time slice

      • 각 queue에 CPU time을 적절한 비율로 할당

      • e.g.

        • 80% to foreground in RR

        • 20% to background in FCFS

  • Priority 별 queue 분배

    한번 정해진 queue는 바뀌지 않는다

Multilevel Feedback Queue

  • Process가 다른 queue로 이동 가능

    • 상위 queue가 우선순위가 높다

    • 상위 queue가 비어야 하위 queue가 채워진다

  • aging을 이와 같은 방식으로 구현할 수 있다

    • aged job을 상위 queue로 보내기

  • Multilevel feedback queue scheduler 를 정의하는 Parameters

    1. Queue의 수

    2. 각 queue의 scheduling algorithm

    3. Process를 상위 queue로 보내는 기준

    4. Process를 하위 queue로 내쫓는 기준

    5. Process가 CPU 서비스를 받으러 할 때, 들어갈 queue를 결정하는 기준

  • e.g.

  • Three queues

    • Q0 - time quantum 8 ms

    • Q1 - time quantum 16 ms

    • Q2 - FCFS

  • Scheduling Flow

    • new job이 queue Q0로 들어감

    • CPU를 잡아서 할당 시간인 8ms 동안 수행됨

    • 8ms 동안 다 끝내지 못했으면 Q1으로 내려감

    • Q1에 줄서서 기다리다가, CPU를 잡아서 16ms 동안 수행됨

    • 16ms 안에 끝내지 못한 경우 Q2로 쫓겨남

Multiple-Processor Scheduling

  • CPU가 여러 개인 경우 scheduling은 더욱 복잡해짐

  • Homogeneous process 인 경우

    누구나 처리할 수 있는 역량이 똑같은 CPU

    • Queue에 한줄로 세워서 processor가 알아서 꺼내가게 할 수 있다

    • but, 반드시 특정 processor에서 수행되어야 하는 process가 있는 경우에는 문제가 더 복잡해진다

  • Load sharing (= Load balancing)

    • 일부 processor에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요

    • 별개의 queue를 두는 방법 vs 공동 queue를 사용하는 방법

  • Symmetric Multiprocessing (SMP)

    • 각 processor가 각자 알아서 스케줄링 결정

    • 균일한 작업을 여러곳에서 할 때는 조율하는 processor가 없는게 효율적일 수도 있다

  • Asymmetric multiprocessing

    • 하나의 processor가 system data의 접근과 공유를 책임지고, 나머지 processor는 거기에 따름

Real-Time Scheduling

  • Hard real-time systems

    • 정해진 시간 안에 반드시 끝내도록 scheduling 해야 함

    • 그러기 위해 process들의 CPU 도착 시간을 미리 알고 scheduling 하는 경우도 있다 (off-line scheduling)

      • ↔ online scheuluing

        • system이 실행중에 동적으로 process를 scheduling

        • 작업이 도착하는 시점에서 결정을 내릭 때문에, 실행 시점에 알려진 정보만 사용할 수 있다

  • Soft real-time computing

    • 일반 process에 비해 높은 priority를 갖도록 해야 함

    • e.g. 동영상이 끊기지 않도록 동영상 재생 process가 먼저 CPU를 얻을 수 있도록 priority를 높이기

Thread Scheduling

하나의 process 안에 CPU 수행 단위가 여러개 있는 것

  • Local Scheduling

    • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 scheduling 할지 결정

  • Global Scheduling

    • Kernel level thread의 경우 일반 process와 마찬가지로, kernel의 단기 scheduler가 어떤 thread를 scheduling 할지 결정

Algorithm Evaluation

  • Queueing models

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

  • Implementation & Measurement

    • 실제 시스템에 알고리즘을 구현 하여 실제 작업에 대해서 성능을 측정 하여 비교

  • Simulation

    • 알고리즘을 모의 프로그램으로 작성 후 trace 를 입력으로 하여 결과 비교

    • trace 란?

      • simulation의 input이 되는 data

      • 신빙성이 있어야함 (실제 프로그램의 동작을 대변할 수 있어야 함)

PreviousProcessNextOS Basics

Last updated