[4주차] CPU 스케줄링

신은지·2021년 10월 3일
0

반효경 공룡 OS

목록 보기
4/8

프로세스는 일생동안 CPU burst와 I/O burst를 반복한다.
이때 프로그램마다 CPU 사용 시간이 다르므로, 자원의 효율적 관리를 위해 CPU 스케줄링이 필요하다.

프로세스의 특성 분류

  • 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를 넘겨줄지 고민하고, 실제로 넘겨준다.

  • Dispatcher
    : 실제로 CPU를 넘겨주는 역할!
    : CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다 (= 문맥 교환)

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

    • 아래와 같은 프로세스 상태변화에서 CPU 스케줄링이 필요하다.
      (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 (강제로 빼앗음)


Sheduling Criteria

Performance Index (= Performance Measure, 성능 척도)
스케줄링 알고리즘의 적합성 판단 기준

시스템 입장

CPU가 얼마나 많은 일을 했느냐?

  • CPU utilization (이용률)
    : 전체 시간 중에서 CPU가 일한 시간의 비율
    : 높을수록 좋다

  • Throughput (처리량)
    : 단위시간당 프로세스 처리량.
    : 많을수록 좋다

사용자 입장

사용자가 기다리는 시간. 모두 빠를수록 좋다

  • Turnaround time (소요시간, 반환시간)
    : 지금까지 걸린 전체 시간
    : CPU 실제 쓴 시간 + CPU 기다린 시간

  • Waiting time (대기 시간)
    : CPU를 쓰러 와서 기다린 전체 시간
    : 줄 섰던 시간 다 합친거. CPU 쓰고 반납 후 I/O 처리하고 다시 기다린 시간들 다 합친 시간

  • Response time (응답 시간)
    : 프로세스가 CPU를 쓰러 들어와서 최초로 CPU를 얻기까지 걸린 시간
    : I/O 마친 후 Ready queue에 들어와서 최초로 CPU를 얻기까지의 시간


Scheduling Algorithms

FCFS (First-Come First-Served)

먼저 도착한 프로세스에게 먼저 CPU 준다. nonpreemtive

선착순으로 처리하며, 한 프로세스가 완료될 때 까지 다음 프로세스들은 기다린다.

  • Convoy efffect (호위 효과)
    : short process가 long process 때문에 오래 걸린다
    : 먼저 오는 프로세스의 CPU 사용시간에 따라 Waiting time이 엄청나게 길어질 수 있다!

SJF (Shortest-Job-First) & SRTF (Shortest-Remaining-Time-First)

짧은 프로세스에게 먼저 CPU 준다.
optimal한 방법 = 대기시간의 평균이 모든 알고리즘 중 제일 짧다.

  • 각 프로세스의 다음번 CPU burst time을 기준으로 스케줄링한다.
    : CPU burst time이 제일 짧은 프로세스를 제일 먼저 스케줄!
    : 일종의 priority scheduling

  • Schemes

    • Nonpreemptive
      : 일단 CPU 잡으면 해당 CPU burst 완료될 때까지 CPU를 preemption 당하지 않는다.

    • Preemptive (Optimal)
      : Shortest-Remaining-Time-First (=SRTF)
      : 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가진 새로운 프로세스가 도착하면 CPU를 빼앗긴다

  • 단점
    (1) Starvation 발생 : CPU burst 긴 프로세스는 언제까지고 기다려야한다
    (2) CPU burst time의 예측 : 다음의 CPU burst time을 정확하게 알 수 없고, 과거의 CPU burst time으로부터 추정만 가능하다.

Priority Scheduling

우선순위가 높은 프로세스에게 먼저 CPU를 준다

  • smallest integer = highest priority
  • preemptive와 nonpreemptive가 있다.
  • 단점 : Starvation
  • 해결 : Aging. 기다린 시간만큼 우선순위를 높여주는 방식으로 starvation을 해소한다.

RR (Round Robin)

실제 CPU 스케줄링에서 제일 많이 사용한다
타이머에 세팅된 시간동안 CPU 사용후 다음으로 넘겨주는 preemptive 방법

  • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖는다.
    : 할당 시간이 지나면 다음 프로세스에게 CPU 넘어가고, 만약 아직 작업이 끝나지 않았다면 다시 ready queue의 제일 뒤로 가서 줄 선다.
    : 반복이 RR의 철학!

  • n개의 프로세스가 ready queue에 있고, 할당 시간이 q time unit인 경우
    : 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다
    : 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다!

  • SJF에 비해 평균 대기 시간은 길지만, 응답 시간이 짧다
    : time sharing 환경에서 큰 장점
    : 단, long job과 short job이 섞여있을 때 좋다.
    : 전체 프로세스의 burst time이 비슷한 경우 비효율적인 상황이 생길 수 있다!

  • 성능
    : q large => FCFS
    : q small => context switch 오버헤드가 커진다

Multilevel Queue

Ready queue를 여러 개로 분할하여, 여러 줄에서 대기한다.

  • Ready queue의 분할
    (1) foreground (interative) : RR 스케줄링 알고리즘
    (2) background (batch - no human interaction) : FCFS 스케줄링 알고리즘. 줬다 뺐었다 하는게 더 비효율적이니까!

  • 큐에 대한 스케줄링 필요
    (1) Fixed priority scheduling :
    (2) Time slice : 각 큐에 CPU time을 적절한 비율로 할당

Multilevel Feedback Queue

여러 줄에서 대기하는데, 프로세스가 다른 줄로 넘어갈 수 있다.

  • 프로세스가 다른 큐로 이동 가능한 방식
    : Aging을 이런 방식으로 구현할 수 있다.
    : 큐의 우선순위는 위로 갈수록 높으며, 각 큐마다 파라미터를 정해야 한다.

  • Multilevel-feedback-queue scheduler를 정의하는 파라미터
    (1) Queue의 수
    (2) 각 큐의 scheduling algorithm
    (3) Process를 상위 큐로 보내는 기준
    (4) Process를 하위 큐로 보내는 기준
    (5) 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

  • Multilevel Queue와의 차이점
    : Aging을 사용, MQ와 달리 Starvation을 해소할 수 있다.

Multiple-Processor Scheduling

CPU가 여러개인 환경에서의 스케줄링

  • Homogeneous processor
    : 큐에 한 줄로 세워서 프로세서가 알아서 꺼내가도록 한다
    : 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우, 더 문제 복잡해짐

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

  • Symmetric Multiprocessing (SMP)
    : 각 프로세서가 알아서 각자 스케줄링 결정
    : 모든 프로세스가 균일한 일을 수행하는 경우엔 비효율적

  • Asymmetric multiprocessing
    : 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 그에 따른다


Real-Time Scheduling

빨리 처리하는게 아닌, 데드라인 안에 끝내는게 중요한 시스템

  • Hard real-time systems
    : 정해진 시간(데드라인) 안에 반드시 끝내도록 스케줄링 필요
    : CPU 용량도 데드라인에 맞춰서! 오프라인으로 미리 스케줄링 해두고 시스템은 그에 따라가도록 한다.

  • Soft real-time computing
    : 일반 프로세스에 비해 높은 priority를 갖도록 한다
    : 가능한 CPU 먼저 얻을 수 있게 처리


Thread Scheduling

  • Local Scheduling
    : OS가 모르는 경우, 스레드에게 맡긴다
    : User level thread의 경우 사용자 수준의 thread library에 의해 어떤 스레드를 스케줄할지 결정

  • Global Scheduling
    : OS가 누구에게 줄지 미리 알고 있는 경우
    : Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 스레드를 스케줄할지 결정


Algorithm Evaluation

어떤 CPU 스케줄링 알고리즘이 제일 좋은가?

  • Queueing models
    : 확률 분포로 주어지는 값들을 통해 각종 성능 index 값을 계산한다
    : 단위시간 당 얼마나 CPU가 일을 하느냐, job의 분포 등을 기반으로 계산

  • Implementation (구현) & Measurement (성능 측정)
    : 실제 시스템에 알고리즘을 구현 - 실제 작업 (workload)에 대한 성능을 측정하여 비교

  • Simulation (모의 실험)
    : 알고리즘을 모의 프로그램으로 작성한 후 trace을 입력으로 하여 결과를 비교한다

profile
호그와트 장학생

0개의 댓글