다단계 피드백 대기열

Multilevel feedback queue

컴퓨터 과학에서 다단계 피드백 대기열은 스케줄링 알고리즘이다.스케줄링 알고리즘은 중앙처리장치(CPU)의 사용량을 유지하기 위해 일부 프로세스가 항상 실행되도록 설계되어 있다.[1]다단계 피드백 대기열은 다음과 같은 설계 요구사항에 따라 표준 알고리즘을 확장한다.

  1. 프로세서에 대한 필요에 따라 프로세스를 여러 개의 준비된 대기열로 구분하십시오.
  2. CPU 버스트가 짧은 프로세스를 우선으로 설정
  3. I/O 버스트가 높은 프로세스를 우선한다(I/O 바인딩된 프로세스는 대기열에서 유휴 상태로 유지되어 다른 프로세스에 CPU 시간을 부여함).

다단계 피드백 대기열은 페르난도 J. 코르바토(1962)에 의해 처음 개발되었다.이 업적으로, 컴퓨터 기계 협회는 튜링 상을 코르바토에게 수여했다.[2]

프로세스 스케줄링

멀티레벨 대기열 알고리즘은 프로세스를 초기 대기열 할당에 영구적으로 할당하는 반면, 멀티레벨 피드백 대기열은 대기열 간에 프로세스를 이동시킨다.[3]이전 타임슬릭의 CPU 버스트에 따라 이동이 달라진다.[4]

  • 프로세스가 CPU 시간을 너무 많이 사용하는 경우 우선 순위가 낮은 대기열로 이동한다.
  • 프로세스가 I/O 바인딩되거나 대화형 프로세스인 경우 우선 순위가 높은 대기열로 이동한다.
  • 프로세스가 낮은 우선순위의 대기열에서 너무 오래 대기하고 굶는 경우 높은 우선순위의 대기열로 노후화된다.

알고리즘.

복수의 FIFO 대기열을 사용하며 조작은 다음과 같다.

  1. 최상위 FIFO 대기열의 끝(꼬리)에 새로운 프로세스가 삽입된다.
  2. 어떤 단계에서 프로세스는 대기열의 머리 부분에 도달하고 CPU가 할당된다.
  3. 지정된 대기열의 시간 간격 내에 프로세스가 완료되면 시스템이 종료된다.
  4. 프로세스가 CPU에 대한 제어를 자발적으로 포기하면 대기열 네트워크를 탈퇴하고 프로세스가 다시 준비되면 이전에 포기했던 동일한 대기열의 꼬리에 삽입된다.
  5. 공정이 모든 양자 시간을 사용하는 경우, 다음 하위 수준 대기열의 끝에 미리 비우고 삽입한다.이 다음 하위 수준 대기열은 이전 상위 수준 대기열보다 많은 시간 퀀텀을 가질 것이다.
  6. 이 계획은 프로세스가 완료되거나 기본 수준 대기열에 도달할 때까지 계속된다.
  • 기본 레벨의 대기열에서 프로세스가 완료되고 시스템이 종료될 때까지 원형 로빈 방식으로 순환한다.기본 수준 대기열의 프로세스도 선착순으로 예약할 수 있다.[5]
  • 선택적으로 프로세스가 I/O를 차단하는 경우 한 레벨 '추진'되어 다음 높은 대기열의 끝에 배치된다.이를 통해 I/O 바인딩된 프로세스가 스케줄러에 의해 선호되고 프로세스가 기본 수준 대기열을 '탈피'할 수 있다.

스케줄러는 항상 최상위 큐의 머리에서 프로세스를 선택하기 시작한다.최고 수준의 대기열이 비어 있는 경우에만 스케줄러는 다음 하위 수준의 대기열에서 프로세스를 맡게 된다.후속 하위 수준 대기열에서 픽업을 위해 동일한 정책이 구현된다.한편, 프로세스가 상위 수준의 대기열 중 하나에 들어오면 하위 수준의 대기열에 있는 프로세스를 선점한다.

또한 새로운 공정이 항상 짧은 시간 안에 완성될 것이라는 가정 하에 최상급 대기열의 꼬리 부분에 삽입된다.긴 프로세스는 시간 소모량과 상호작용 수준에 따라 자동으로 하위 레벨의 대기열로 가라앉는다.멀티레벨 피드백 대기열에서 프로세스는 하위 레벨 대기열로 강제 다운되기 전에 주어진 대기열 수준에서 완료될 수 있는 단 한 번의 기회가 주어진다.

예약 매개 변수

일반적으로 다단계 피드백 대기열 스케줄러는 다음과 같은 매개변수로 정의된다.[5]

  • 대기열 수입니다.
  • FIFO와 다를 수 있는 각 대기열의 스케줄링 알고리즘.
  • 프로세스를 높은 우선 순위 대기열로 승격할 시기를 결정하는 데 사용되는 방법.
  • 프로세스를 낮은 우선순위 대기열로 강등할 시기를 결정하는 데 사용되는 방법.
  • 프로세스가 서비스를 필요로 할 때 프로세스가 어떤 대기열을 입력할지 결정하는 데 사용되는 방법.

외부 링크

참고 항목

참조

  1. ^ Silberschatz, Abraham (1994). Operating System Concepts, Fourth Edition. Addison-Wesley. p. 131. ISBN 978-0-201-50480-4.
  2. ^ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014). "Multi-level Feedback Queue". Operating Systems: Three Easy Pieces (PDF). Arpaci-Dusseau Books.
  3. ^ Silberschatz, Abraham (1994). Operating System Concepts, Fourth Edition. Addison-Wesley. p. 147. ISBN 978-0-201-50480-4.
  4. ^ Silberschatz, Abraham (1994). Operating System Concepts, Fourth Edition. Addison-Wesley. p. 148. ISBN 978-0-201-50480-4.
  5. ^ a b Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008). Operating system concepts (8th ed.). Hoboken, N.J.: Wiley. p. 198. ISBN 978-0470128725.