[운영체제] 5. CPU Scheduling(2)

Multilevel Queue

• Ready Queue를 여러개로 분할

  • foreground 큐 (주로 interactive한 작업)
  • background 큐 (batch - no human interaction, cpu만 오래 사용하는 작업 처리할 때)

• 각 큐는 독립적인 스케줄링 알고리즘을 가짐

  • foreground - RR => 응답시간을 짧게 하는 방법
  • background - FCFS => cpu만 오래 사용하는 작업이기 때문 switch overhead를 줄이기 위해 효율적

• 큐에 대한 스케줄링이 필요

  • Fixed priority scheduling
    : foreground 큐를 먼저 처리한 후 background 큐 처리 -> starvation 문제 발생 가능
    • serve all from foreground then from background
    • possibility of starvation
  • Time slice ⇒ 예를 들어, 80%는 우선순위가 높은 줄에게 이렇게 시간을 나누어서 할당 - 80%가 우선순위가 높은 큐에 할당되어 응답성이 좋아지고, 20%는 우선순위가 낮은 큐에 할당되어 오랜시간 동안 cpu 활용하는 작업 처리
    • 각 큐에 cpu time을 적절한 비율로 할당
    • 예) 80% to foreground in RR , 20% to background in FCFS

Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동 가능한 스케줄링
• 에이징(aging)을 이와 같은 방식으로 구현할 수 있다.
• multilevle-feedback-queue scheduler를 정의하는 파라미터들
  • Queue의 수: 일반적으로 우선순위에 따라 여러 개의 큐가 구성
  • 각 큐의 scheduling algorithm: 각 큐마다 다른 스케줄링 알고리즘 선택 가능
  • Process를 상위 큐로 보내는 기준: 일정 시간 동안 CPU를 할당받아도 작업을 완료하지 못한 프로세스를 상위 큐로 이동시킬 조건을 결정
  • Process를 하위 큐로 내쫓는 기준: 상위 큐에서 일정 시간 동안 CPU를 할당받지 못한 프로세스를 하위 큐로 내쫓을 조건을 결정
  • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준: 새로운 작업이 도착했을 때, 어떤 큐에 할당할지를 결정하는 기준을 설정

(예시)

• Three queues:
  • Q0 : time quantum 8 milliseconds
  • Q1: time quantum 16 milliseconds
  • Q2: FCFS
• 스케줄링:
  • new job이 queue Q0으로 들어감
  • CPU를 잡아서 할당시간 8 milliseconds동안 수행됨
  • 8 ms 동안 다 끝내지 못했으면 queue Q1으로 내려감
  • Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms 동안 수행
  • 16 ms 동안 다 끝내지 못한 경우 큐2 로 쫓겨남

작업의 우선순위와 수행 시간에 따라 프로세스를 다른 큐로 이동시킴으로써 효율적인 스케줄링을 수행 -> 상위 큐에서는 짧은 시간 동안 CPU를 할당받아 빠른 응답성을 유지하고, 하위 큐에서는 CPU를 오랜 시간 동안 사용하는 작업을 처리 가능

Multiple-Processor Scheduling

• CPU가 여러개인 경우를 다루는 것 - 스케줄링은 더욱 복잡해짐
• Homogeneous processor(동일한 아키텍처와 성능을 가진 프로세서)인 경우
  • Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세서가 있는 경우에는 문제가 더 복잡해짐 => 특정 작업을 특정 프로세서에 할당하는 스케줄링 메커니즘이 필요
• Load sharing
  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 매커니즘
  • 전체적으로 골고루 cpu가 일할 수 있도록
    1. 별개의 큐를 두는 방법 - 별도의 줄 서기(각 프로세서마다 독립적인 큐를 가지고 있고, 작업은 각 큐에 독립적으로 들어가게 됨)
    2. 공통 큐를 사용하는 방법(모든 프로세서가 하나의 큐를 공유하고, 작업은 해당 큐에 동시에 들어가며 각 프로세서가 작업을 선택하여 처리)
• Symmetric Multiprocessing(SMP)
  • 각 프로세서가 각자 알아서 스케줄링 결정 - 모든 프로세서가 대등하게 스케줄링 결정
• Asymmetric multiprocessing
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
  • 하나의 프로세서가 control, 작업 분배하는 역할

Real-Time Scheduling

• Hard real-time systems
  • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
  • 반드시 데드라인 보장 - 미리 스케줄링하는 방법을 보통 사용
  • 미리 정의된 우선순위에 따라 작업을 스케줄링하고, 데드라인을 준수하기 위해 작업이 실행되는 시간을 엄격하게 관리 -> 신뢰성/안정성 보장
• Soft real-time computing
  • Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
  • 데드라인이 존재하지만 반드시 지켜야하는 것은 아님
    : 데드라인을 놓치는 경우가 있더라도 전반적인 시스템 성능을 유지하면서 작업을 처리 -> 응답성과 성능 최적화

Thread Scheduling: 스레드 실행 순서 스케줄링

• Local Scheduling
  • User level Thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
  • 운영체제는 thread를 알지 못하고 사용자 프로그램 내부에서 결정 - OS가 아니라 사용자 프로그램이 직접 결정
    : 사용자 수준의 스레드 라이브러리는 스케줄링 알고리즘을 사용하여 어떤 스레드가 실행되어야 할지 결정 -> 빠른 스레드 전환, 유연한 스케줄링
• Global Scheduling
  • kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
  • OS가 thread의 존재를 알기 때문에 운영체제가 알고리즘에 의해서 결정
    : 운영체제가 스레드의 스케줄링을 알고리즘에 따라 결정하므로 시스템 전체의 리소스를 효율적으로 관리 가능 but 스레드 전환에 오버헤드 발생 가능/성능 저하 발생 가능

Algorithm Evaluation

: 알고리즘을 평가할 수 있는 방법

• Queueing models
  • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산 - 도착률 / (이론적) cpu 처리률 → throughput 이 계산을 통해 나오게 된다.
• Implementation(구현) & Measurement(성능측정)
  • 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
• Simulation(모의실험)
  • 알고리즘을 모의 프로그램으로 작성 후 trace(인풋 데이터)를 입력으로 하여 결과 비교

[이화여자대학교 반효경 교수님 운영체제 강의를 정리한 내용입니다.]