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

kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다.

1. Multilevel Queue

• Ready queue를 여러 개로 분할
  • foreground(interactive)
  • background(batch - no human interaction)
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground - RR
  • background - FCFS
• 큐에 대한 스케줄링이 필요
  • Fixed priority scheduling
    • serve all from foreground then from background
    • possibility of starvation
  • Time slice
    • 각 큐에 CPU time을 적절한 비율로 할당 eg) 80% to foreground in RR, 20% to background in FCFS

2. Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동 가능
• 에이징(aging)을 이와 같은 방식으로 구현 가능
• multilevel feedback queue scheduler를 정의하는 파라미터
  • Queue의 수
  • 각 큐의 scheduling algorithm (fg-rr, bg-fcfs)
  • process를 상위 큐로 보내는 기준
  • process를 하위 큐로 보내는 기준
  • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

new job에 대해 예측할 필요 없이 higher priority queue로 들어온 후, quantum time unit 내 수행하지 못한다면 하위 큐로 강등된다. 어느 ready queue에 존재할지를 조정하며 계산량이 많은 프로세스는 하위 큐로 내려가고(FCFS), interactive한 프로세스는 상위 큐에서 수행이 완료된다. 

3. Multiple-Processor Scheduling

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

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

4. Real-Time Scheduling

• Hard real-time systems : hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링 해야 함.
• Soft real-time computing : soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함. 하지만 데드라인을 보장하지는 못할 수 있음.

5. Thread Scheduling

• Local Scheduling : User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄 할 지 결정. (OS가 아닌 사용자 프로세스 내부에서 결정)
• Global Scheduling : Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할 지 결정 (OS가 조정)

6. Algorithm Evaluation

• Queueing models : 확률 분포로 주어지는 arrival rate과 service rate 등을 통해 각종 performance index 값을 계산. 이론적 평가
• Implementation(구현) & Measurement(성능 측정) : 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교 (OS 상에서 구현)
• Simulation(모의 실험) : 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교 (user level)