CPU Scheduler

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

Dispatcher

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

 

CPU 스캐줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다

  1. Running → Blocked (I/O 요청하는 시스템 콜)
  2. Running → Ready (할당시간만료로 timer interrupt)( cpu 강제로 뺏기)
  3. Blocked → Ready (I/O 완료 후 인터럽트)
  4. Terminated

cpu를 가지고 기계어를 하는 것 CPU burst

i/o 를 하는 것은 i/o burst

  • i/o burst와 cpu burst를 번갈아가면서 실행하는 게 모든 프로그램의 경로 - 프로그램마다 좀 다르다
  • i/o burst가 빈번하게 끼어들지 않으면, cpu burst가 길게 나탄다
  • 사람과 interaction 하는 프로그램은 i/o burst가 끼어든다 → cpu를 연속적으로 쓰는 단계가 짧아진다

  • cpu가 긴 경우도 있고 짧은 경우도 있기 때문에 스케쥴링이 필요하다

cpu burst가 짧은 경우 - 사람과 interaction job →cpu를 늦게 주면 응답 시간이 오래걸려 사람이 답답

i/o bound job (사람과 하는 인터랙션)

스케쥴링 이슈

  • cpu burst에 들어온 여러가지 프로그램에서 누구에게 cpu를 줄것인가
  • cpu를 i/o를 하러 나갈때까지 끝까지 주느냐 혹은 중간에 뺏어서 다른 곳에 넘겨줄것인가 하는 이슈가 있다
    • 뺏지않고 cpu를 보장해준다면, cpu burst가 긴 프로세스가 계속 붙잡고 있어 다른 프로세스들이 기다려야한다
    • 지나치게 오래 기다리지 않게 해줘야한다 → 효율적으로 스케쥴링하기

스케쥴링을 크게 2가지로 나누면

  • non-preemptive (비선점형)(강제로 cpu를 빼앗지 않는 방법, 한번 주면 그 프로그램이 다쓰고 나갈때까지, io를 해서 자진반납 할때까지)
    • timer
  • preemptive (선점형) (줬지만 언제든지 뺏어올 수 있는것)을 주로 쓴다

성능척도 (scheduling criteria)

  • 시스템입장에서의 성능척도
    • cpu하나 가지고 최대한 일을 많이 시키는 게 좋은 것
    • cpu utilization (이용률)
      • 전체 시간에서 cpu가 놀지 않고 일한 시간의 비율
      • 가능한 바쁘게 일을 시켜라
    • Throughput(처리량)
      • 주어진 시간동안 몇 개의 작업을 완료했는가
  • 프로그램입장에서의 성능척도
    • 내가 cpu를 빨리 얻어서 빨리 끝내는 게 좋은것
    • Turnaround time(소요시간, 반환시간)
      • cpu를 쓰러 들어와서 다 쓰고 나갈때까지 걸린 시간
      • cpu를 기다리는 시간 (ready queue에 있던 시간+ running 시간)
    • waiting time(대기시간)
      • cpu queue에서 기다린 시간
      • 한번의 cpu burst 동안에서 얻고뺏고를 반복해서, 그 기다린 모든 시간을 합친것
    • response time(응답 시간)
      • ready queue에 들어와서 처음으로 cpu를 얻기까지 걸린 시간

FCFS (First come First served) - Queue

  • 먼저 온 순서대로 처리
  • 비선점형 스케쥴링
  • 효율적 X
  • CPU를 오래쓰는 프로세스이 들어와서 CPU를 잡아버리면 다른 프로세스들은 기다려야한다
  • 앞에 어떤 프로세스가 있느냐에 따라 성능의 차이가 크다
  • Convoy effect
    • 긴 프로세스가 도착해서 짧은 프로세스가 긴 시간을 기다리는 현상

SJF (Shortest Job First)

  • cpu burst가 제일 짧은 프로세스에게 먼저 cpu를 주는 것
  • 전체적으로 행복한 결과 햅삐, 전체적으로 queue가 짧아진다
  • average waiting time을 최소화 → preemptive
  • 2가지방식으로 나눠서 생각
    • 비선점형
      • 더 짧은 프로세스가 도착해도 넘겨줄 수 없다
      • cpu를 다 쓰고 나간 시점에 스케줄링을 할지 말지 결정
    • 선점형
      • 더 짧은 프로세스가 도착하면 cpu를 뺏어서 넘겨줄 수 있다
      • shortest ramaining time first라고도 부른다 (SRTF)
      • 새로운 프로세스가 도착하면 언제든지 스케줄링이 이루어질 수 있다
  • 2가지 문제점이 있다
    • Starvation (기아현상)
      • 극단적으로 cpu 사용이 짧은 job을 선호
      • cpu 사용시간이 긴 프로세스는 영원히 못 받을 수도 있다
  • 다음 번 cpu 사용시간을 미리 알 수 없다
    • cpu사용시간을 미리 알 수는 없지만 추정은 가능하다.
    • 과거의 CPU burst time 얼마나 썻는가를 확인해 예측하다 (정확 X)
    • 과거의 최근 것을 많이 반영, 완전 먼 과거는 적게 반영

Priority Scheduling - SJF의 일종

  • 우선순위가 제일 높은 프로세스에게 cpu주기
  • 2가지 방식으로 나눠서 생각
    • preemptive 위와 똑같음
    • non-preempive 위와 똑같음
  • 우선순위를 나타내는 값 - integer(정수)
  • 낮은 숫자가 우선순위가 높다 (smallest integer = highest priority)
  • 문제
    • 기아현상 - 영원히 cpu를 얻지 못한다
    • 기아현상을 해결하기 위해 aging 기법을 도입
      • 오래 기다릴 수록 우선순위를 높여주기
      • 기다리면 언젠간 cpu 얻기 가넝

Round Robin (RR) - Timer가 있는 이유

  • 현대적인 컴퓨터 시스템에서 사용하는 cpu 스케줄링
  • 할당시간을 세팅해서 넘겨주고, 끝나면 time interrupt에 의해 뺏기구… 반복
  • 선점형 스케줄링
  • 각 프로세스는 동일한 크기의 할당시간을 가진다 → 공정하다
  • 할당 시간이 끝나면 ready queue 의 제일 뒤로 가서 다시 줄을 선다
  • 좋은점
    • 응답시간이 빨라진다 (turnaround time 이 아닌..)
    • 예측할 필요 X
  • cpu를 오래쓰는 프로세스는 할당시간 만큼 쓰고 뺏기고 한다 → 여러번 반복해서 기다려야한다
  • cpu를 오래쓰는 프로세스는 대기시간도 길다 - 비례
  • cpu를 짧게 쓰는 프로세스는 대기시간도 짧다 - 비례
  • 할당시간을 아주 크게 잡으면 FCFS
  • 할당시간을 지나치게 작게 잡으면 context switch 오버헤드가 커진다 → 시스템의 전체 성능이 낮아진다
  • 적당한 할당시간 주기 → 무엇으로 계산할까요?! 평균?!
    • 보통 10-100 millisecond
  • SJF보다 average turnaroundtime이 길지만 response time은 짧다
  • 특이한 경우
    • cpu 사용시간이 100초 여러개 →짧게 나눠서 돌림→ 1000초대에 모조리 빠져나간다
      • FIFO하면 적어도 하나라도 빨리 끝내고 나갈 수 있다
  • RR은 cpu 사용시간이 긴지 짧은지 모르고 막 섞여있을 때 사용

Multilevel Queue (MLQ)

  • system process → interactive process → interactive editing process → batch process → student process 줄이 정해져있다
    • 프로세스가 계급처럼 나뉘어져서 알맞은 줄에 가서 기다린다
    • 위에서부터 내려온다, 절대 우선순위가 바뀌지 않는다 (가혹)
  • 우선순위가 낮다면 기아현상을 가질 수도 있다
  • Ready queue를 여러 개로 분할
    • foreground (interative)
    • background(batch - no human interaction)
  • 각 큐는 독립적인 스케줄링 알고리즘을 가진다
    • foreground - RR → 응답시간을 짧게
    • background - FCFS - context switch 오버헤드를 줄이기 위해 FCFS 사용, cpu를 어차피 오래쓴다
  • 어떤 큐에게 cpu를 줄것이냐!?
    • Fixed priority scheduling
      • 우선순위가 높은 줄이 비지 않는다면 우선순위가 낮은 곳에 starvation 발생가능
    • Time slice
      • 각 큐에 cpu time을 적절한 비율로 지정

Multilevel Feedback Queue

  • 프로세스가 다른 큐로 이동 가능
  • 에이징(aging)을 이와 같은 방식으로 구현할 수 있다
    • 윗 글 해석!
  • cpu이 사용시간이 짧은 프로세스에게 우선순위를 높게 주는 방식
    • 긴프로세스는 밑으로 쫓겨남 슝
  • cpu 실행시간의 예측이 필요없다
    • cpu실행시간이 짧은 프로세스가 우대받는다

cpu가 여러 개인 경우 스케줄링은 더욱 복잡해진다

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

Real-Time scheduling

  • 정해진 시간안데 반드시 실행되어야 하는 것 realtime job (보통 주기적으로 실행)
  • 데드라인 반드시 보장해줘야함
  • 미리 스케줄링을 해서 데드라인을 지키도록 한다
  • Hard real-time systems
    • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
  • Soft real-time computing
    • Soft real-time task는 일반 프로세스에 비해 높은 prioirity를 갖도록 해야함

Thread Scheduling

프로세스안의 cpu의 실행단위 thread

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

Algorithm Evaluation - 알고리즘 평가방법

  • Queueing models
    • 이론적인 방법
    • 확률 분포로 주어지는 arrival rate(도착률)와 service rate(처리율) 등을 통해 각종 performance index 값을 계산
  • Implemetation(구현) & Measurement(성능 측정)
    • 실제 시스템에 알고리즘을 구현하여 실제작업(workload)에 대해서 성능을 측정 비교
  • Simulation (모의실험)
    • 알고리즘을 모의 프로그램으로 작성 후 trace(실제 프로그램을 통해서 추출한 input 데이터)를 입력으로 하여 결과 비교
    • trace를 임의로 만들 수도 있고, 실제 시스템을 통해서도 만들 수 있다CPU Scheduler
      • Ready 상태의 프로세스 중에서, 이번에 CPU를 줄 프로세스를 고른다
developer-soyun
developer-soyun
developer-soyun 님의 블로그 입니다.

티스토리툴바