OS - CPU Scheduling 2

---

🚀 OS - CPU Scheduling 1에서 이어지는 내용입니다.

지금까지 배운 개념에서는 ready queue에 한줄로 줄을 섰다. 하지만 이러한 줄을 여러줄 서는 개념이 뒤에 나오는 개념이다.

🧩 Multilevel Queue

그림을 보면 맨 위가 우선순위가 높은 줄이고, 맨 아래가 우선순위가 낮은 줄이다. CPU는 우선순위가 높은 곳부터 무조건 할당한다. 우선순위가 높은 곳에 대기가 없을 때부터 아래로 내려가면서 CPU를 할당한다. 대기 줄은 여러개인데 CPU는 하나이니 고려할 사항들이 있다.

• Ready queue를 여러 개로 분할
  • foreground(interactive)
  • background(batch - no human interaction)
• 각 큐 사이에 프로세스들이 이동할 수 없다.
• 각 큐는 독립적은 스케줄링 알고리즘을 가짐
  • foreground - RR
  • background - FCFS
• 큐에 대한 스케줄링이 필요
  • Fixed priority scheduling(우선순위 강하게 적용)
    • 우선순위 높은 줄이 비어있을 때만 낮은 곳에 CPU가 간다.
    • Starvation 가능성이 있음
  • Time slice
    • 각 큐에 CPU time을 적절한 비율로 할당
    • ex) 80% to foreground in RR, 20% to background in FCFS

위에 방식은 우선순위가 낮은 것은 계속 우선순위가 낮은채로 있어야한다는 문제가 있다. 이제 아래의 Multilevel Feedback Queue는 이러한 부분이 개선된다.

🧩 Multilevel Feedback Queue

• Multilevel Queue와 비슷하지만, MFQ는 각 큐 간에 프로세스들이 이동할 수 있다.
• Aging 으로 이와 같은 방식으로 구현할 수 있다.
• Multilevel Feedback Queue Scheduler를 정의하는 파라미터들
  • Queue의 수
  • 각 큐의 Scheduling algorithm
  • Process를 상위 큐로 보내는 기준
  • Process를 하위 큐로 보내는 기준
  • 프로세스가 CPU의 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

보통 Multilevel Feedback Queue를 어떤식으로 운영하냐고 하면 처음 들어오는 프로세스는 우선순위가 가장 높은 큐에 집어넣고 우선순위가 높은 곳은 RR에서 할당시간을 굉장히 짧게 준다. 그리고 밑에 큐로 갈수록 할당시간을 조금 더 길게 주고, 제일 아래 큐는 FCFS방식을 쓴다.

이 상태에서 위에큐에서 할당시간을 다 사용하면 아래큐로 강등이된다. CPU사용시간이 짧은 프로세스는 위에큐에서 바로 처리가 되고, CPU사용시간이 길면 길수록 아래큐로 강등당한다.
이 방식은 CPU사용시간이 짧은 프로세스에게 우선순위를 주는 방향이다.

---

이제 지금까지 말한 것들은 다 모두 CPU가 하나일때의 일반 상황을 가정했다. 이제부터 말할 것들은 특이한 케이스들에서의 CPU Scheduling을 알아볼 것이다.

🧩 Multiple-Processor Scheduling

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

🧩 Real-Time Scheduling

Deadline이 있는 스케줄링

• 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의 존재를 모르기때문에 사용자 프로세스 내부에서 CPU할당을 결정
• Global Scheduling
  • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
  • 운영체제가 결정

위에서 말하는 Thread는 프로세스 하나에 CPU수행단위가 여러개 있는 것을 말한다. 또한 위에서 말하는 User level thread는 사용자 프로세스가 직접 thread를 관리하고 운영체제는 thread의 존재를 모르는 경우이고, Kernel level thread는 운영체제가 thread의 존재를 아는 경우이다.

---

지금까지 알고리즘들을 알아봤으니 이것들에 대한 평가를 알아보겠다.

🧩 Alrorithm Evaluation

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