Chapter 05. Process Scheduling (4of4) - MLQ, MFQ

목차

• 기본 스케줄링 알고리즘들
  • 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)

여러개의 ready queue

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

  • 최초 배정된 queue를 벗어날 수 없음
  • 각각 queue는 자신만의 스케줄링 기법 사용

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

  • ex) fixed-priority preemptive scheduling

• 장점

  • 빠른 응답시간 (과연 그럴까?)
  • 중요한 애들한테 빠른 응답시간

• 단점

  • 여러개의 queue 관리 등 스케줄링 overhead

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

MFQ (Multi-level Feedback Queue)

남은 시간 적은 애 먼저 처리

• 프로세스의 queue간 이동이 허용된 MLQ
• Feedback을 통해 우선 순위 조정
  • 현재까지의 프로세서 사용 정보(패턴) 활용
• 특성
  • Dynamic priority
  • Preemptive scheduling
• 장점
  • 프로세스에 대한 사전 정보 없이
    SPN, SRTN, HRRN 기법의 효과를 볼 수 있음!!
• 단점
  • 설계 및 구현이 복잡, overhead 큼
  • starvation 문제
• 변형
  • 각 ready queue 마다 time quantum (시간 할당량)을 다르게 배정할 수 있음
  • 입출력 위주 프로세스(I/O-bounded)를 상위 단계의 큐로 이동(우선순위 높이기)
    • 프로세스가 block될 때 상위의 ready queue로 진입하게 함
    • 시스템 전체의 평균 응답 시간을 줄일 수 있다.
  • 대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동
    • Aging 기법 : 오래기다렸으면 위로 높이기