스케줄링 - 멀티 레벨 피드백 큐

요약

• 핵심 아이디어 한 줄 요약
• “이 노트는 왜 중요한가?” → 맥락 설명

본문

• 1962년 Corbato등에 의해 개발되었음

• 해결하고자 하는 문제
  1. 짧은 작업을 먼저 실행시켜 반환 시간을 최적화
  2. 대화형 사용자의 케이스를 고려해 응답시간 최적화
     • RoundRobin 은 응답시간을 단축시키지만 반환시간은 최악임
• MLFQ: 기본 규칙
  • 여러개의 큐로 구성되며 다른 우선순위가 배정됨
  • 큐 하나에는 두개이상의 작업이 존재할 수 있고 이들은 모두 같은 우선순위를 가짐
  • 어떻게 우선순위를 정하는가?
    • 각 작업의 특성에 따라 동적으로 우선순위를 부여한다.
  • 기본 규칙
    1. Prioriy A > Priority B이면 A가 실행된다.
    2. Priority A = Priority B면 A와 B는 RR 방식으로 실행된다.
    3. 작업이 시스템에 진입하면, 가장 높은 우선순위, 맨위의 큐에 놓여진다.
    4. 주어진 타임슬라이스를 모두 사용하면 우선순위는 낮아진다.(한단계 아래 큐로 이동)
    5. 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선 순위를 유지한다.
  • 오래 실행되는 작업들은 우선순위를 낮게 해서 과도하게 점유하는 일이 없게함
  • 입출력의 경우, 타임 슬라이스가 종료되기전에 CPU를 양도하기 때문에 우선순위가 유지됨
• MLFQ 단점
  • 기아 상태가 발생할 수 있음
    • 시스템에 너무 많은 대화형 작업이 존재하면, 모든 CPU시간을 소모하게 되어서 긴 실행시간 작업은 starvation 됨
  • 스케줄러를 과도하게 점유하도록 공격 가능
    • 슬라이스가 끝나기전에 입출력 시도
  • 작업이 시간에 따라 특성이 바뀜
    • CPU intensive 하다가 대화형 작업으로 바뀔 수도 있음
• 규칙 5: 일정기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동 시킨다.
  • starvation 문제와 작업이 시간에 따라 특성이 바뀌는 문제를 해결할 수 있음
• 그렇다면 스케줄러를 과도하게 점유하도록 공격하는 케이스는?
  • MLFQ의 각 단계에서 CPU 총 사용시간을 측정하는 방식
  • 현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장
  • 단순히 1회의 타임슬라이스가 아니라 프로세스가 전체 사용시간을 트랙킹하는 방식으로 해결
  • 규칙 4: 주어진 단계에서 시간 할당량을 소진하면 우선순위는 낮아진다.
• MLFQ 조정과 다른 쟁점
  • 필요한 변수들을 스케줄러가 어떻게 설정해야하는지?
    • 몇개의 큐, 큐당 타임 슬라이스, 우선순위 상향 조정 시간
  • FreeBSD의 스케줄러(4.3버전) 작업의 현재 우선순위를 계산하기 위해 프로세스가 사용한 CPU 시간을 기초로 한 공식을 사용

참고

• https://pages.cs.wisc.edu/~remzi/OSTEP/Korean/08-cpu-sched-mlfq.pdf
• CPU 스케줄링 방식의 naive한 구현 FIFO, SJF,