[CS] Process Scheduler #4

이 포스팅은 한국기술교육대학교 김덕수 교수님의 운영체제 강의를 참고하여 작성되었습니다.

 

기본 스케줄링 알고리즘

• FCFS (First-Come-First-Service)
• RR (Round-Robin)
• SPN (Shortest-Process-Next)
• SRTN (Shortest Remaining Time Next)
• HRRN (High-Response-Ratio-Next)
• MLQ (Multi-level Queue)
• MFQ (Multi-level Feedback Queue)

 

MLQ (Multi-level Queue)

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

- 최초 배정 된 queue를 벗어나지 못함

- 각각의 queue는 자신만의 스케줄링 기법 사용

Queue 사이에는 우선순위 기반의 스케줄링 사용

- E.g., fixed-priority preemptive scheduling

장점

- 빠른 응답시간 (?)

단점

- 여러 개의 Queue 관리 등 스케줄링 overhead

- 우선순위가 낮은 queue는 starvation 현상 발생 가능

김덕수 교수님의 운영 체제 강의자료 中

 

MLFQ (Multi-level Feedback Queue)

프로세스의 Queue간 이동이 허용된 MLQ

Feedback을 통해 우선순위 조정

- 현재까지의 프로세서 사용 정보(패턴) 활용

특성

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

프로세스에 대한 사정 정보 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있다.

즉, BT를 예상하지 않고도 비슷한 효과를 발휘한다.

김덕수 교수님 운영 체제 강의자료 中

단점

- 설계 및 구현이 복잡, 스케줄링 overhead가 큼

- Starvation 문제 등

변형

- 각 준비 큐마다 시간 할당량을 다르게 배정

프로세스의 특성에 맞는 형태로 시스템 운영 가능

- 입출력 위주 프로세스들을 상위 단계의 큐로 이동, 우선 순위 높임

프로세스가 block 될 때 상위의 준비 큐로 진입하게 함

시스템 전체의 평균 응답 시간 줄임, 입출력 작업 분산 시킴

- 대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동

에이징 (aging) 기법

 

MLFQ는 다양한 Parameter와 정책들을 설정할 수 있다.

 

 

긴 글 읽어주셔서 감사드립니다.

22.12.16