[OS] 5-4. 프로세스 스케줄링 알고리즘 - MLQ, MFQ

목차

• 스케줄링의 목적
• 스케줄링 기준 및 단계
• 스케줄링 정책
• 기본 스케줄링 알고리즘들
• Case study

---

Basic Scheduling algorithms

공평성을 고려한 방식

• FCFS (First Come First Service)
• RR (Round Robin)

효율성을 고려한 방식

• SPN (Shortest Process Next)
• SRTN (Shortest Remaining Time Next)
• HRRN (High Response Ratio Next)

BT 예측문제를 개선한 방식

• MLQ (Multi level Queue)
• MFQ (Multi level Feedback Queue)

---

앞서 효율성을 고려한 방식의 문제점은 BT를 예측해야 하는데 힘들다

그래서 효율성을 고려한 방식과 비슷한 효과를 내면서 BT를 예측하지 않는 방식이 MLQ, MFQ이다.

MLQ (Multi-level Queue)

큐를 여러개 두는 것.

앞서 알고리즘 SPN, SRTN, HRRN은 ready, Q가 하나였는데 MLQ는 ready, q가 여러개

작업 (or 우선순위) 별 별도의 ready queue 를 가짐

• 최초 배정 된 queue 를 벗어나지 못함 => 시스템 변화에 적용하기 힘듦
• 각각의 queue 는 자신만의 스케줄링 기법 사용

Queue 사이에는 우선순위 기반의 스케줄링 사용 => 다양한 우선순위 적용

장점

빠른 응답시간?? => 중요한 우선순위는 빠르게 처리될 수 있다. 

단점

• 여러 개의 Queue 관리 등 스케줄링 overhead
• 우선순위가 낮은 queue 는 starvation 현상 발생 가능

Queue의 구성은 정책에 따라 결정

 

MFQ (Multi level Feedback Queue)

MLQ의 최초 배정 된 queue 를 벗어나지 못함 => 시스템 변화에 적용하기 힘듦 의 단점을 극복하기 위해 나온 방법임

• 프로세스의 Queue 간 이동이 허용된 MLQ
• Feedback 을 통해 우선 순위 조정

특성

• Dynamic priority
• Preemptive scheduling
• Favor short burst time processes
• Favor I/O bounded processes
• Improve adaptability

MFQ를 쓰면 무엇이 좋은가? (장점)

프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있음 (BT를 예상하지 않아도 됨)

단점

• 설계 및 구현이 복잡 , 스케줄링 overhead 가 큼
• Starvation 문제 등

변형

• 각 준비 큐마다 시간 할당량을 다르게 배정
  
  • 프로세스의 특성에 맞는 형태로 시스템 운영 가능
• 입출력 위주 프로세스(I/O bounded)들을 상위 단계의 큐로 이동, 우선 순위 높임
  
  • 프로세스가 block 될 때 상위의 준비 큐로 진입하게 함
  • 시스템 전체의 평균 응답 시간 줄임 , 입출력 작업 분산 시킴
• 대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동
  
  • 에이징 (aging) 기법

Parameters for MFQ scheduling (다양한 MFQ 파라미터)

• Queue 의 수
• Queue 별 스케줄링 알고리즘
• 우선 순위 조정 기준
• 최초 Queue 배정 방법

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---