저번 게시물에 이어서 Multilevel Queue와 Mulitilevel Feedback Queue에 대해 알아보겠습니다.

이전 게시물
https://velog.io/@doodung/OS-CPU-Scheduling-1

Scheduling Algorithms

1. FCFS (First-Come First-Served)
2. SJF (Shortest-Job-First)
3. Priority Scheduling
4. RR (Round Robin)
5. Multilevel Queue
6. Mulitilevel Feedback Queue

1. FCFS (First-Come First-Served)

: 먼저 온 순서대로 처리

2. SJF (Shortest-Job-First)

: cpu를 짧게 쓰는 프로그램에게 cpu를 먼저 주는 것.

3. Priority Scheduling

우선순위 스케줄링, 우선순위가 높은 프로세스에게 cpu 주겠다

4. RR (Round Robin)

효율적이고 공정한 방법으로. CPU를 주고 나서 쓰고싶은 만큼 무작정 쓰게하는게 아니라 할당된 시간만큼만 CPU를 쓰고 다음 프로세스에게 넘겨주는 스케줄링.

5. Multilevel Queue

: 한줄 서기가 아닌 여러줄, 줄마다 우선 순위가 있음.
완전히 계급제. CPU는 이 우선 순위대로 차지하고, 우선순위가 비어있을 때만 낮은 순위에게 간다.
신분을 극복하지 못하므로 좋진 않다.

고려해야 할 사항

1. 프로세스를 어느줄에 넣어야 할 것인가?
2. 우선순위 낮은 프로세스의 기아현상?

Ready queue를 여러 개로 분할

• foreground (interactivce job)
• background (batch - no human interaction)

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

• foreground - RR : 응답시간이 빠르게
• background - FCFS : context switch 오버헤드를 줄이기 위해서

큐에 대한 스케줄링이 필요 | 어떤 큐에게 cpu를 줄거냐. 줄이 결정되면 줄 안에서 누구에게 cpu를 줄지 결정해야함.

• Fixed proirity scheduling
  • serve all from foreground them background
  • Possibility of starvation
• Time slice (기아현상 줄이기 위해)
  • 각 큐에 CPU time을 적절한 비율로 할당
  • Ex) 80은 우선순위 높은애에게, 20은 우선순위 낮은애에게
    80% to foreground in RR, 20% to background in FCFS

6. Mulitilevel Feedback Queue

줄을 왔다갔다 할 수 있음. 처음 들어오는 프로세스는 우선순위가 가장 높은 큐에 넣음. RR로 quantum 8로 해서 시간을 짧게 줌. 밑에 큐로 갈수록 할당 시간을 길게 주고, 제일 아래한테는 fcfs 방식을 씀. 할당시간이 위에서 끝나면 아래 큐로 강등되는 방식.
cpu burst가 짧으면 맨위 큐에서 빨리 빠져나갈 수 있음. cpu 사용시간이 짧은 프로세스에게 우선순위를 더 주는 방식. cpu 사용시간에 대한 예측은 필요 없다.

고려해야 할 사항

1. 큐를 몇개 둘것이냐?
2. 각 큐에서 어떤 스케줄링을 사용할 것이냐?
3. 우선순위가 높은큐에서 낮은큐로 떨어지는 기준은?
4. 우선순위가 낮은큐에서 높은큐로 승격되는 기준은?
5. 처음 프로세스가 들어갈때 어느 큐로 들어가냐?

Scheduling

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

특이한 case 에서의 CPU Scheduling

---

1. Multiple-Processor Scheduling

CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐. 그래서 Load sharing이 잘되어야 한다. 특정 CPU만 일하면 안된다.

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

2. Real-Time Scheduling

real-time job : 정해진 시간에 반드시 이뤄져야 하는 스케줄링. 반드시 데드라인을 보장 해주어야함. 그때그때 스케줄링을 하기 보다는 미리 스케줄링을 해서 데드라인이 보장되도록 적재적소에 배치하는 방법을 쓴다. 보통 offline으로 미리 스케줄링을 해놓거나, 주기적으로 activate가 되는(1초 에 한번씩, 10초에 한번씩 cpu를 잡아서 적어도 1초동안은 cpu를 써야한다는 제약)식이므로 그에 맞게 데드라인을 보장해야한다.

• Hard real-time systems : cpu를 얻는 것을 반드시 보장
  • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링 해야함
• Soft real-time computing : 일반적인 time-sharing 시스템에서 다른 시스템과 섞여서 사용, 데드라인을 반드시 지킨다기 보다는 다른 프로세스에 비해 우선순위만 좀 높여줘서 cpu를 먼저 얻을 수 있게함.
  • Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야함

3. Thread Scheduling

process하나 안에 cpu 수행 단위(thread)가 여러개 있음

• Local Scheduling : OS가 하는 것이 아니라 사용자 프로세스가 결정
  • User level thread( : 사용자 프로세스가 직접 thread를 관리하고 운영체제는 쓰레드의 존재를 모름)의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
• Global Scheduling : 프로세스 스케줄링 하듯 OS가 알고리즘에 근거해서 CPU를 줄지 결정
  • Kernel level thread( : 운영체제가 thread의 존재를 알고있음)의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

Algorithm Evaluation

---

어떤 알고리즘이 좋은지 평가하는 방법

1. Queueing models : 이론적인 방법, 예전에 많이 사용함.

   

   • queue에 job들이 도착해서 쌓이게 된다. server(CPU로 생각) 도착한 프로세스들을 CPU능력에 따라 처리하고 빠져나가는 service rate(처리율)이 있다.
   • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산

2. Implementation (구현) & Measurement (성능 측정) : 실측하는 방법. 리눅스 커널 (운영체제 내부 고치는 일)을 만지는건 어려운일임. 쉽게할려면 3번째 방법으로 함

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

3. Simulation (모의 실험) :

   • 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교