5. 프로세스 스케줄링 (4)

현 포스팅은 MLQ, MFQ를 다룹니다.
강의 링크 : https://www.youtube.com/watch?v=actKUqea6Xc

Basic Scheduling algorithms

1. FCFS (First-Come-First-Service)
2. RR (Round-Robin)
3. SPN (Shortest-Process-Next)
4. SRTN (Shortest Remaining Time Next)
5. HRRN (High-Response-Ratio-Next)
6. MLQ (Multi-level Queue)
7. MFQ (Multi-level Feedback Queue)

6. MLQ (Multi-level Queue)

ready queue가 여러 개인 알고리즘

• 작업(or 우선순위)별 별도의 ready queue를 가짐
  • 최초 배정 된 queue를 벗어나지 못함
  • 각각의 queue는 자신만의 스케줄링 기법을 사용함
• queue 사이에는 우선순위 기반의 스케줄링 사용
  • e.g., fixed-priority preemptive scheduling : 고정된 우선순위
• 장점
  • 우선순위가 높은 queue인 경우 빠른 응답시간을 가진다
• 단점
  • 여러 개의 queue 관리 등으로 인산 스케줄링 overhead
  • 우선순위가 낮은 queue는 starvation 현상이 발생할 수 있음
  • 최초 배정된 queue를 벗어나지 못하므로 시스템의 변화에 적응이 안될 수 있음

MLQ의 여러 ready queue 예시

• queue의 구성은 정책에 따라 결정됨!

7. MFQ (Multi-level Feedback Queue)

• 프로세스의 queue간 이동이 허용된 MLQ
• Feedback을 통해 우선 순위 조정
  • 현재까지의 프로세서 사용 정보(패턴) 활용
• 특성
  • Dynamic priority : 우선순위가 동적임
  • Preemptive scheduling
  • Favor short burst-time processes
  • Favor I/O bounded processes
  • Improve adaptability
• 프로세스에 대한 사전 정보 (예를 들면 BT(실행 시간)같은) 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있음

• 단점
  • 설계 및 구현이 복잡, 스케줄링 overhead가 큼
  • starvation 문제 존재
    • 우선 순위가 낮은 queue의 경우 starvation이 해소되지 않음.
• 다양한 변형을 줄 수 있음 
  • 변형 예시
    • 각 준비 큐마다 시간 할당량(time-quantum)을 다르게 배정
      • 프로세스의 특성에 맞는 형태로 시스템 운영 가능
    • 입출력 위주 프로세스(I/O bounded process)들을 상위 단계의 큐로 이동시켜 우선 순위를 높임
      • 프로세스가 block될 때 상위의 준비 큐로 진입하게 함
      • -> 시스템 전체의 평균 응답 시간을 줄여줌, 입출력 작업을 분산 시킴
      • I/O bounded process들은 CPU를 잠깐 쓰고 나옴. 시스템 입장에서는 많은 수를 빨리 처리하는게 이득인데, I/O bounded process는 CPU를 잠깐만 쓰고 나오므로 우선순위를 높여주는 것
      • 이러한 이유로 Computed bounded process의 우선순위는 낮추는 것
    • 대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동시킴
      • 에이징(aging) 기법

MFQ 변형 예시

 

• parameters for MFQ scheduling
  • queue의 수
  • queue별 스케줄링 알고리즘
  • 우선 순위 조정 기준
  • 최초 queue 배정 방법 등 ..