5-2. CPU Scheduling 2

5-2. CPU Scheduling 2

CPU-burst Time의 분포, Schedulling Algorithms, Round Robin(RR), Multilevel Queue, Multilevel Feedback Queue, Multi-Processor Scheduling, Real-time Scheduling, Example of Non-Preemptive SJF, Thread Scheduling, Algorithm Evaluation,

 

Multilevel Queue

사용자와 상호작용하는 앞단의 프로세스들은 중요하다고 판단하고, 백그라운드에서 돌아가는 프로세스들은 상대적으로 덜 중요하다고 판단하여 분류!

• Ready queue를 여러개로 분할
  • foreground(interactive)
  • background(batch - no human interaction)
• 각 큐는 독립적인 스케쥴링 알고리즘을 가짐
  • foreground - RR (사람과 인터렉션을 하기에 라운드로빈)
  • background - FCFS (어쩌피 CPU오랫동안 사용하는 프로세스들이고 응답시간이 빠르다고 좋을게아니니까 문맥전환을 줄여 오버헤드를 줄이기위해 FCFS)
• 큐에 대한 스케쥴링이 필요
  • Fixed priority scheduling
    • serve all foreground then from background
    • possibility of starvation (우선순위가 높은게 비워지지 않으면, starvation 발생 가능!)
  • Time slice
    • 각 큐에 CPU time을 적절한 비율로 할당
    • 예를들어, 80%는 foreground (RR)로 , 20%는 background(FCFS)로!
    

Multilevel Feedback Queue

multilevel queue의 확장판이라 생각, 멀티피드백 큐 또한 멀티 레벨이기에 여러개의 큐로 구성되어있음.

각 큐마다 스케쥴링 알고리즘을 적용할 수 있는것까지 동일함.

• Three Queues:
  • Q0 : time quantum 8 milliseconds
  • Q1 : time quantum 16 milliseconds
  • Q2 : FCFS
• Scheduling
  • new job이 queue Q0로 들어감
  • CPU를 잡아서 할당 시간 8 milliseconds동안 수행됨
  • 8 milliseconds 동안 다 끝내지 못했으면, queue Q1으로 내려감
  • Q1에 줄서서 Q0가 비어지길 기다렸다가, CPU를 잡아서 16 milliseconds동안 수행됨
  • 16 milliseconds에 끝내지 못한 경우 queue Q2로 쫓겨남
• 처음 들어오는 프로세스는 우선순위가 가장 높은 큐에 집어넣고, 우선순위가 가장 높은 큐는 라운드로빈에서 time quantum을 짧게 줌 밑에 큐로 갈수록 라운드로빈의 할당 시간을 길게 주고 가장 아래에는 FCFS방식을 씀. 할당시간이 맨위에큐에서 끝나게되면 아래큐로 강등이되는 방식

Multiple-Processor Scheduling (CPU가 여러개 있을 때)

• CPU가 여러개인 경우 스케쥴링은 더욱 복잡해짐
• Homogeneous processor인 경우
  • queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐(어떤 job은 특정 CPU가 꼭 수행해야하는 경우 예를들어 전담 헤어디자이너한테만 받아야할때!)
• Load sharing (특정 CPU만 일하고 나머지는 놀면 안되겠지)
  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
  • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
• Symmetric Multiprocessing(SMP) (모든 CPU가 대등한것)
  • 각 프로세서가 각자 알아서 스케쥴링 결정
• Asymmetric multiprocessing (보통 CPU가 여러개 있는데 그중 하나의 CPU가 전체적인 컨트롤을 담당)
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

Real-Time Scheduling (데드라인이 있는것!)

• Hard real-time system (반드시 시간안에!!!)
• Soft real-time task : 일반 프로세스에 비해 높은 priority를 갖도록 해야함 (데드라인을 꼭 보장하진 않음)

Thread Scheduling

• Local Scheduling (사용자 프로세스가 직접 쓰레드를 관리하고, 운영체제는 쓰레드의 존재를 모르는 경우)
  • user level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케쥴 할지 결정
• Global Scheduling (운영체제가 쓰레드의 존재를 이미 알고 있는 경우)
  • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케쥴러가 어떤 thread를 스케쥴할지 결정

Algorithm Evaluation

• Queueing models
  • 확률 분포로 주어지는 arrival rate와 service rate등을 통해 각종 performance index값을 계산 (이론적인 방법)
• Implementation(구현) & Measurement(성능 측정)
  • 실제시스템에 구현해서 돌려보고 판단
• Simulation(모의 실험)
  • 알고리즘을 모의 프로그램을 통해 작성 후 trace를 입력으로 하여 결과 비교