CPU Scheduling 3

kocw 강의 : 이화여자대학교 반효경 교수님의 운영 체제 강의,11강 CPU Scheduling

 

Ready Queue 에 줄을 어떻게 서는가?

 

Multi-level queue

• priority 에 따라 줄을 선다. 가장 위에 줄이 system process, 가장 아래 줄이 student process (이게 뭔지는 모르겠다)
• ready queue 를 여러 개로 분할, queue 별 scheduling 방법을 사용한다.
  • foreground (interactive) -> round robin 방법을 사용
  • bacground (batch - no human interaction) -> FCFS 방법을 사용
• queue 에 대한 스케줄링이 필요
  • fixed priority scheduling
    • serve all from foreground then from background
    • possibility of starvation
  • time slice
    • 각 큐에 cpu time 을 적절한 비율로 할당
      • ex) 80% to foreground in RR, 20% to background in FCFS

---

Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동 가능
• aging 을 이와 같은 방법으로 구현할 수 있다
• 대게, 처음 들어오는 process를 위에 queue 로 놓는다. 늦게 올 수록 아래 queue 로 넣는다.
• 아래 이미지에서 보면 알 수 있듯, 우선 순위가 높은 queue 일 수록 time quantum 이 작다. 즉, cpu burst time 이 짧아야만 high priority queue 에서 process를 종료할 수 있다.
• 이는, cpu burst time 이 짧은 얘들이 더 빨리 끝나게 유도한다.

---

Multi-processor Sheduling

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

운영 체제 수업에서 multi-processor 를 자세히 다루지는 않는다고 함

---

Real-Time Scheduling

• Hard real-time systems
  • 정해진 시간 안에 반드시 끝내도록 스케줄링 해야 함
• Soft real-time systems
  • 일반 프로세스에 비해 높은 priority 를 갖도록 해야 함

Thread scheduling

• Local Scheduling
  • user level thread 의 경우, 사용자 수준의 thread library에 의해 어떤 thread 를 스케줄할 지 결정
• Global Scheduling
  • kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread 를 줄 지 결정