[CS, 운영체제] CPU-scheduling

스케쥴링 알고리즘 (복수개)

• multilevel Queue : 공정 X, 차별적임
  
  - Ready queue를 여러 개로 분할
  - foreground(interactive한 job을 넣음)
  - background(barch-no human interaction 을 넣음)
  • 각 큐는 독립적인 스케줄링 알고리즘을 가짐
    • foreground => RR
  • background => FCFS
• queue에 대한 스케줄링이 필요
  • Fixed priority scheduling (=> 우선순위에 따라 엄격하게 우선순위가 높은 큐가 비어야 낮은 큐 실행)
    - serve all from foreground then from background
    • possibility of starvation
  • time slice (=> starvation이 발생하지 않음)
    - 각 큐에 CPU time을 적절한 비율로 할당
    • Eg., 80% to foreground in RR, 20% to background in FCFS
• multilevel Feedback Queue
  
  - 프로세스가 다른 큐로 이동 가능
  • 에이징(aging)을 이와 같은 방식으로 구현할 수 있다
  • multilevel-feedback-queue scheduler를 정의하는 파라미터들
    • Queue의 수
      • 각 큐의 scheduling algorithm
      • process를 상위 큐로 보내는 기준
      • process를 하위 큐로 내쫒는 기준
      • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
  

=> 여기까지는 CPU가 한개일 때

Multiple-Processor Scheduling

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

Real-Time Scheduling

• Hard real-time system : 정해진 시간 안에 반드시 끝내도록 스케줄링해야함

• Soft real-time system : 일반 프로세스에 비해 높은 priority를 갖도록 해야함

Thread Scheduling

• Local Schduling : User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정 => OS가 스케줄하는게 아니라 사용자 프로세스가 직접 어느 thread에 CPU를 줄지 결정. OS는 thread의 존재를 모름

• Global Schedulig : Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
  => OS가 thread의 존재를 앎

스케쥴링 알고리즘 평가

Queuing models (이론적인 방법)

(server = CPU)

• 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산

Implementation (구현) & Measurement (성능 측정)

• 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교

Simulation (모의 실험)

• 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
  (trace: 실제 프로그램을 돌려서 뽑은 input data가 될 수 있음)