Operating Systems: Three Easy Pieces. Part 5: ΠŸΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅: Multi-Level Feedback Queue (ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄)

Π’Π²Π΅Π΄Π΅Π½ΠΈΠ΅ Π² ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΎΠ½Π½Ρ‹Π΅ систСмы

ΠŸΡ€ΠΈΠ²Π΅Ρ‚, Π₯Π°Π±Ρ€! Π₯ΠΎΡ‡Ρƒ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π²Π°ΡˆΠ΅ΠΌΡƒ вниманию ΡΠ΅Ρ€ΠΈΡŽ статСй-ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄ΠΎΠ² ΠΎΠ΄Π½ΠΎΠΉ интСрСсной Π½Π° ΠΌΠΎΠΉ взгляд Π»ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΡƒΡ€Ρ‹ β€” OSTEP. Π’ этом ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Π΅ рассматриваСтся достаточно Π³Π»ΡƒΠ±ΠΎΠΊΠΎ Ρ€Π°Π±ΠΎΡ‚Π° unix-ΠΏΠΎΠ΄ΠΎΠ±Π½Ρ‹Ρ… ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΎΠ½Π½Ρ‹Ρ… систСм, Π° ΠΈΠΌΠ΅Π½Π½ΠΎ β€” Ρ€Π°Π±ΠΎΡ‚Π° с процСссами, Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹ΠΌΠΈ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊΠ°ΠΌΠΈ, ΠΏΠ°ΠΌΡΡ‚ΡŒΡŽ ΠΈ ΠΏΡ€ΠΎΡ‡ΠΈΠΈΠΌΠΈ ΠΏΠΎΠ΄ΠΎΠ±Π½Ρ‹ΠΌΠΈ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚Π°ΠΌΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΡΠΎΡΡ‚Π°Π²Π»ΡΡŽΡ‚ ΡΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ ОБ. ΠžΡ€ΠΈΠ³ΠΈΠ½Π°Π» всСх ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»ΠΎΠ² Π²Ρ‹ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ ΠΏΠΎΡΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Π²ΠΎΡ‚ Ρ‚ΡƒΡ‚. ΠŸΡ€ΠΎΡˆΡƒ ΡƒΡ‡Π΅ΡΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ Π½Π΅ΠΏΡ€ΠΎΡ„Π΅ΡΡΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ (достаточно вольно), Π½ΠΎ надСюсь ΠΎΠ±Ρ‰ΠΈΠΉ смысл я сохранил.

Π›Π°Π±ΠΎΡ€Π°Ρ‚ΠΎΡ€Π½Ρ‹Π΅ Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΏΠΎ Π΄Π°Π½Π½ΠΎΠΌΡƒ ΠΏΡ€Π΅Π΄ΠΌΠ΅Ρ‚Ρƒ ΠΌΠΎΠΆΠ½ΠΎ Π½Π°ΠΉΡ‚ΠΈ Π²ΠΎΡ‚ Ρ‚ΡƒΡ‚:

Π”Ρ€ΡƒΠ³ΠΈΠ΅ части:

А Π΅Ρ‰Π΅ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ Π·Π°Π³Π»ΡΠ΄Ρ‹Π²Π°Ρ‚ΡŒ ΠΊΠΎ ΠΌΠ½Π΅ Π½Π° ΠΊΠ°Π½Π°Π» Π² Ρ‚Π΅Π»Π΅Π³Ρ€Π°ΠΌ =)

ΠŸΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅: Multi-Level Feedback Queue

Π’ этой Π»Π΅ΠΊΡ†ΠΈΠΈ ΠΌΡ‹ ΠΏΠΎΠ³ΠΎΠ²ΠΎΡ€ΠΈΠΌ ΠΎ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ°Ρ… Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈΠ· самых извСстных ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΎΠ² ΠΊ
ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΡŽ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ называСтся Multi-Level Feedback Queue (MLFQ). Π’ΠΏΠ΅Ρ€Π²Ρ‹Π΅ MLFQ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ Π±Ρ‹Π» описан Π² 1962 Π³ΠΎΠ΄Ρƒ Fernando J. CorbatΓ³ Π² систСмС, Π½Π°Π·Ρ‹Π²Π°Π΅ΠΌΠΎΠΉ
Compatible Time-Sharing System (CTSS). Π­Ρ‚ΠΈ Ρ€Π°Π±ΠΎΡ‚Ρ‹ (Π² Ρ‚ΠΎΠΌ числС ΠΈ ΠΏΠΎΠ·Π΄Π½ΠΈΠ΅ Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π½Π°Π΄
Multics) впослСдствии Π±Ρ‹Π»ΠΈ прСдставлСны ΠΊ Π½Π°Π³Ρ€Π°Π΄Π΅ Turing Award. ΠŸΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ Π±Ρ‹Π»
впослСдствии ΡƒΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½ΡΡ‚Π²ΠΎΠ²Π°Π½ ΠΈ ΠΏΡ€ΠΈΠΎΠ±Ρ€Π΅Π» ΠΎΠ±Π»ΠΈΠΊ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΌΠΎΠΆΠ½ΠΎ Π²ΡΡ‚Ρ€Π΅Ρ‚ΠΈΡ‚ΡŒ ΡƒΠΆΠ΅ Π²
Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… соврСмСнных систСмах.

Алгоритм MLFQ пытаСтся Ρ€Π΅ΡˆΠΈΡ‚ΡŒ 2 Ρ„ΡƒΠ½Π΄Π°ΠΌΠ΅Π½Ρ‚Π°Π»ΡŒΠ½Ρ‹Π΅ ΠΏΠ΅Ρ€Π΅ΡΠ΅ΠΊΠ°ΡŽΡ‰ΠΈΠ΅ΡΡ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹.
Π’ΠΎ-ΠΏΠ΅Ρ€Π²Ρ‹Ρ…, ΠΎΠ½ пытаСтся ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ врСмя ΠΎΠ±ΠΎΡ€ΠΎΡ‚Π°, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ ΠΊΠ°ΠΊ ΠΌΡ‹ рассматривали Π² ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰Π΅ΠΉ Π»Π΅ΠΊΡ†ΠΈΠΈ, оптимизируСтся ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ запуска Π² Π½Π°Ρ‡Π°Π»Π΅ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅
ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΈΡ… Π·Π°Π΄Π°Ρ‡. Однако, ОБ Π½Π΅ Π·Π½Π°Π΅Ρ‚ ΠΊΠ°ΠΊ Π΄ΠΎΠ»Π³ΠΎ Π±ΡƒΠ΄Π΅Ρ‚ Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ Ρ‚ΠΎΡ‚ ΠΈΠ»ΠΈ ΠΈΠ½ΠΎΠΉ процСсс, Π° это
Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΠ΅ Π·Π½Π°Π½ΠΈΠ΅ для Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² SJF, STCF. Π’ΠΎ-Π²Ρ‚ΠΎΡ€Ρ‹Ρ…, MLFQ пытаСтся
ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ систСму ΠΎΡ‚Π·Ρ‹Π²Ρ‡ΠΈΠ²ΠΎΠΉ для ΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚Π΅Π»Π΅ΠΉ (Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€ для Ρ‚Π°ΠΊΠΈΡ…, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ сидят ΠΈ
пялятся Π² экран Π² ΠΎΠΆΠΈΠ΄Π°Π½ΠΈΠΈ Π·Π°Π²Π΅Ρ€ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ) ΠΈ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ врСмя
ΠΎΡ‚ΠΊΠ»ΠΈΠΊΠ°. К соТалСнию, Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π½Π°ΠΏΠΎΠ΄ΠΎΠ±ΠΈΠ΅ RR ΡƒΠΌΠ΅Π½ΡŒΡˆΠ°ΡŽΡ‚ врСмя ΠΎΡ‚ΠΊΠ»ΠΈΠΊΠ°, Π½ΠΎ ΠΊΡ€Π°ΠΉΠ½Π΅
ΠΏΠ»ΠΎΡ…ΠΎ Π²Π»ΠΈΡΡŽΡ‚ Π½Π° ΠΌΠ΅Ρ‚Ρ€ΠΈΠΊΡƒ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ ΠΎΠ±ΠΎΡ€ΠΎΡ‚Π°. ΠžΡ‚ΡΡŽΠ΄Π° наша ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ°: Как ΠΏΡ€ΠΎΠ΅ΠΊΡ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ
ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΡ‚Π²Π΅Ρ‡Π°Ρ‚ΡŒ нашим трСбованиям ΠΈ ΠΏΡ€ΠΈ этом Π½ΠΈΡ‡Π΅Π³ΠΎ Π½Π΅ Π·Π½Π°Ρ‚ΡŒ ΠΎ
Ρ…Π°Ρ€Π°ΠΊΡ‚Π΅Ρ€Π΅ процСсса, Π² ΠΎΠ±Ρ‰Π΅ΠΌ? Как ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ смоТСт ΠΈΠ·ΡƒΡ‡ΠΈΡ‚ΡŒ характСристики Π·Π°Π΄Π°Ρ‡,
ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΎΠ½ запускаСт ΠΈ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Ρ‚ΡŒ Π»ΡƒΡ‡ΡˆΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ ΠΎ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠΈ?

Π‘ΡƒΡ‚ΡŒ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹: Как ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ постановку Π·Π°Π΄Π°Ρ‡ Π±Π΅Π· идСального знания?
Как Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΡƒΠ΅Ρ‚ врСмя ΠΎΡ‚ΠΊΠ»ΠΈΠΊΠ°
для ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡ ΠΈ ΠΏΡ€ΠΈ этом ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΡƒΠ΅Ρ‚ врСмя ΠΎΠ±ΠΎΡ€ΠΎΡ‚Π° Π±Π΅Π· Π·Π°Π²Π΅Π΄ΠΎΠΌΠΎΠ³ΠΎ
знания Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ исполнСния Π·Π°Π΄Π°Ρ‡ΠΈ?

Π—Π°ΠΌΠ΅Ρ‚ΠΊΠ°: обучаСмся ΠΏΠΎ ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰ΠΈΠΌ событиям

ΠžΡ‡Π΅Ρ€Π΅Π΄ΡŒ MLFQ являСтся прСкрасным ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠΌ систСмы, которая обучаСтся Π½Π°
ΠΏΡ€ΠΎΡˆΠ΅Π΄ΡˆΠΈΡ… событиях, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΡ€Π΅Π΄ΡΠΊΠ°Π·Π°Ρ‚ΡŒ Π±ΡƒΠ΄ΡƒΡ‰Π΅Π΅. ΠŸΠΎΠ΄ΠΎΠ±Π½Ρ‹Π΅ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Ρ‹ часто
Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‚ΡΡ Π² ОБ (И ΠΌΠ½ΠΎΠ³ΠΈΡ… Π΄Ρ€ΡƒΠ³ΠΈΡ… отраслях Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅, Π²ΠΊΠ»ΡŽΡ‡Π°Ρ Π²Π΅Ρ‚ΠΊΠΈ
прСдсказаний Π² ΠΎΠ±ΠΎΡ€ΡƒΠ΄ΠΎΠ²Π°Π½ΠΈΠΈ ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΊΡΡˆΠΈΡ€ΠΎΠ²Π°Π½ΠΈΡ). ΠŸΠΎΠ΄ΠΎΠ±Π½Ρ‹Π΅ ΠΏΠΎΡ…ΠΎΠ΄Ρ‹
ΡΡ€Π°Π±Π°Ρ‚Ρ‹Π²Π°ΡŽΡ‚, ΠΊΠΎΠ³Π΄Π° Ρƒ Π·Π°Π΄Π°Ρ‡ Π΅ΡΡ‚ΡŒ повСдСнчСскиС Ρ„Π°Π·Ρ‹ ΠΈ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΎΠ½ΠΈ прСдсказуСмы.
Однако с Ρ‚Π°ΠΊΠΎΠΉ Ρ‚Π΅Ρ…Π½ΠΈΠΊΠΎΠΉ слСдуСт Π±Ρ‹Ρ‚ΡŒ остороТным, ΠΏΠΎΡ‚ΠΎΠΌΡƒ Ρ‡Ρ‚ΠΎ прСдсказания ΠΎΡ‡Π΅Π½ΡŒ Π»Π΅Π³ΠΊΠΎ
ΠΌΠΎΠ³ΡƒΡ‚ ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ Π½Π΅ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½Ρ‹ΠΌΠΈ ΠΈ привСсти систСму ΠΊ ΠΏΡ€ΠΈΠ½ΡΡ‚ΠΈΡŽ Ρ…ΡƒΠ΄ΡˆΠΈΡ… Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΉ, Π½Π΅ΠΆΠ΅Π»ΠΈ
Π±Ρ‹Π»ΠΈ Π±Ρ‹ Π±Π΅Π· Π·Π½Π°Π½ΠΈΠΉ Π²ΠΎΠΎΠ±Ρ‰Π΅.

MLFQ: Basic Rules

Рассмотрим Π±Π°Π·ΠΎΠ²Ρ‹Π΅ ΠΏΡ€Π°Π²ΠΈΠ»Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° MLFQ. И хотя Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΉ этого Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°
сущСствуСт нСсколько, Π±Π°Π·ΠΎΠ²Ρ‹Π΅ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄Ρ‹ схоТи.
Π’ Ρ‚ΠΎΠΉ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΌΡ‹ Π±ΡƒΠ΄Π΅ΠΌ Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Ρ‚ΡŒ, Π² MLFQ Π±ΡƒΠ΄Π΅Ρ‚ нСсколько
ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½Ρ‹Ρ… ΠΎΡ‡Π΅Ρ€Π΅Π΄Π΅ΠΉ, каТдая ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ Ρ€Π°Π·Π½Ρ‹ΠΉ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚. Π’ любоС врСмя,
Π·Π°Π΄Π°Ρ‡Π°, готовая ΠΊ исполнСнию находится Π² ΠΎΠ΄Π½ΠΎΠΉ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ. MLFQ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Ρ‹,
Ρ‡Ρ‚ΠΎΠ±Ρ‹ Ρ€Π΅ΡˆΠΈΡ‚ΡŒ, ΠΊΠ°ΠΊΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ Π·Π°ΠΏΡƒΡΠΊΠ°Ρ‚ΡŒ Π½Π° исполнСниС, Ρ‚.Π΅. Π·Π°Π΄Π°Ρ‡Π° с Π±ΠΎΠ»Π΅Π΅ высоким
ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ΠΎΠΌ (Π·Π°Π΄Π°Ρ‡Π° ΠΈΠ· ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ с Π²Ρ‹ΡΡˆΠΈΠΌ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ΠΎΠΌ) Π±ΡƒΠ΄Π΅Ρ‚ Π·Π°ΠΏΡƒΡ‰Π΅Π½Π° Π² ΠΏΠ΅Ρ€Π²ΡƒΡŽ
ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ.
НСсомнСнно, Π² ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΠΎΠΉ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ ΠΌΠΎΠΆΠ΅Ρ‚ Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ Π±ΠΎΠ»Π΅Π΅ ΠΎΠ΄Π½ΠΎΠΉ Π·Π°Π΄Π°Ρ‡ΠΈ, Ρ‚Π°ΠΊΠΈΠΌ
ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ Ρƒ Π½ΠΈΡ… Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹ΠΉ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚. Π’ этом случаС Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒΡΡ ΠΌΠ΅Ρ…Π°Π½ΠΈΠ·ΠΌ
RR для планирования запуска срСди этих Π·Π°Π΄Π°Ρ‡.
Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΌΡ‹ ΠΏΡ€ΠΈΡ…ΠΎΠ΄ΠΈΠΌ ΠΊ Π΄Π²ΡƒΠΌ Π±Π°Π·ΠΎΠ²Ρ‹ΠΌ ΠΏΡ€Π°Π²ΠΈΠ»Π°ΠΌ для MLFQ:

  • Rule1: Если ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚(А) > ΠŸΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚(Π‘), Π±ΡƒΠ΄Π΅Ρ‚ Π·Π°ΠΏΡƒΡ‰Π΅Π½Π° Π·Π°Π΄Π°Ρ‡Π° А (Π‘ Π½Π΅ Π±ΡƒΠ΄Π΅Ρ‚)
  • Rule2: Если ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚(А) = ΠŸΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚(Π‘), АиБ Π·Π°ΠΏΡƒΡΠΊΠ°ΡŽΡ‚ΡΡ с использованиСм RR

Π˜ΡΡ…ΠΎΠ΄Ρ ΠΈΠ· Π²Ρ‹ΡˆΠ΅ΠΏΠ΅Ρ€Π΅Ρ‡ΠΈΡΠ»Π΅Π½Π½ΠΎΠ³ΠΎ, ΠΊΠ»ΡŽΡ‡Π΅Π²Ρ‹ΠΌΠΈ элСмСнтами ΠΊ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΡŽ MLFQ
ΡΠ²Π»ΡΡŽΡ‚ΡΡ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Ρ‹. ВмСсто Ρ‚ΠΎΠ³ΠΎ Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π·Π°Π΄Π°Π²Π°Ρ‚ΡŒ фиксированный ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡƒ
заданию, MLFQ измСняСт Π΅Π³ΠΎ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ Π² зависимости ΠΎΡ‚ наблюдаСмого повСдСния.
НапримСр, Ссли Π·Π°Π΄Π°Ρ‡Π° постоянно бросаСт Ρ€Π°Π±ΠΎΡ‚Ρƒ Π½Π° CPU Π² ΠΎΠΆΠΈΠ΄Π°Π½ΠΈΠΈ Π²Π²ΠΎΠ΄Π° с ΠΊΠ»Π°Π²ΠΈΠ°Ρ‚ΡƒΡ€Ρ‹,
MLFQ Π±ΡƒΠ΄Π΅Ρ‚ ΠΏΠΎΠ΄Π΄Π΅Ρ€ΠΆΠΈΠ²Π°Ρ‚ΡŒ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ процСсса Π½Π° высоком ΡƒΡ€ΠΎΠ²Π½Π΅, ΠΏΠΎΡ‚ΠΎΠΌΡƒ Ρ‡Ρ‚ΠΎ ΠΈΠΌΠ΅Π½Π½ΠΎ Ρ‚Π°ΠΊ
Π΄ΠΎΠ»ΠΆΠ΅Π½ Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΉ процСсс. Если ΠΆΠ΅ Π½Π°ΠΏΡ€ΠΎΡ‚ΠΈΠ² Π·Π°Π΄Π°Ρ‡Π° постоянно ΠΈ
интСнсивно ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ CPU Π² Ρ‚Π΅Ρ‡Π΅Π½ΠΈΠ΅ Π΄ΠΎΠ»Π³ΠΎΠ³ΠΎ ΠΏΠ΅Ρ€ΠΈΠΎΠ΄Π°, MLFQ Π±ΡƒΠ΄Π΅Ρ‚ ΠΏΠΎΠ½ΠΈΠΆΠ°Ρ‚ΡŒ Π΅Π³ΠΎ
ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, MLFQ Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΠ·ΡƒΡ‡Π°Ρ‚ΡŒ ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ процСссов Π² ΠΌΠΎΠΌΠ΅Π½Ρ‚ ΠΈΡ… Ρ€Π°Π±ΠΎΡ‚Ρ‹
ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ повСдСния.
НарисуСм ΠΏΡ€ΠΈΠΌΠ΅Ρ€ Ρ‚ΠΎΠ³ΠΎ ΠΊΠ°ΠΊ ΠΌΠΎΠ³Π»ΠΈ Π±Ρ‹ Π²Ρ‹Π³Π»ΡΠ΄Π΅Ρ‚ΡŒ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ Π² Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ‚
Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ ΠΈ Ρ‚ΠΎΠ³Π΄Π° получится Ρ‡Ρ‚ΠΎ-Ρ‚ΠΎ Π²Ρ€ΠΎΠ΄Π΅ этого:
Operating Systems: Three Easy Pieces. Part 5: ΠŸΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅: Multi-Level Feedback Queue (ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄)

Π’ Π΄Π°Π½Π½ΠΎΠΉ схСмС 2 процСсса А ΠΈ B находятся Π² ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ с Π½Π°ΠΈΠ²Ρ‹ΡΡˆΠΈΠΌ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ΠΎΠΌ. ΠŸΡ€ΠΎΡ†Π΅ΡΡ
Π‘ Π³Π΄Π΅-Ρ‚ΠΎ посСрСдинС, Π° процСсс D Π² самом ΠΊΠΎΠ½Ρ†Π΅ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ. Богласно ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½Ρ‹ΠΌ Π²Ρ‹ΡˆΠ΅
описаниям Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° MLFQ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΡΠΏΠΎΠ»Π½ΡΡ‚ΡŒ Π·Π°Π΄Π°Ρ‡ΠΈ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ с Π½Π°ΠΈΠ²Ρ‹ΡΡˆΠΈΠΌ
ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ΠΎΠΌ согласно RR, Π° Π·Π°Π΄Π°Ρ‡ΠΈ C,D Π±ΡƒΠ΄ΡƒΡ‚ Π½Π΅ Ρƒ Π΄Π΅Π».
ЕстСствСнно статичСский ΡΠ½Π°ΠΏΡˆΠΎΡ‚ Π½Π΅ даст ΠΏΠΎΠ»Π½ΡƒΡŽ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½Ρƒ Ρ‚ΠΎΠ³ΠΎ ΠΊΠ°ΠΊ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ MLFQ.
Π’Π°ΠΆΠ½ΠΎ ΠΏΠΎΠ½ΠΈΠΌΠ°Ρ‚ΡŒ, ΠΊΠ°ΠΊ ΠΈΠΌΠ΅Π½Π½ΠΎ мСняСтся ΠΊΠ°Ρ€Ρ‚ΠΈΠ½Π° с Ρ‚Π΅Ρ‡Π΅Π½ΠΈΠ΅ΠΌ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ.

ΠŸΠΎΠΏΡ‹Ρ‚ΠΊΠ° 1: Как ΠΈΠ·ΠΌΠ΅Π½ΡΡ‚ΡŒ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚

Π’ этот ΠΌΠΎΠΌΠ΅Π½Ρ‚ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Ρ€Π΅ΡˆΠΈΡ‚ΡŒ, ΠΊΠ°ΠΊ MLFQ Π±ΡƒΠ΄Π΅Ρ‚ ΠΌΠ΅Π½ΡΡ‚ΡŒ ΡƒΡ€ΠΎΠ²Π΅Π½ΡŒ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π°
Π·Π°Π΄Π°Ρ‡ΠΈ (ΠΈ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ полоТСния Π·Π°Π΄Π°Ρ‡ΠΈ Π² ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ) ΠΏΠΎ Ρ…ΠΎΠ΄Ρƒ Π΅Π΅ ΠΆΠΈΠ·Π½Π΅Π½Π½ΠΎΠ³ΠΎ Ρ†ΠΈΠΊΠ»Π°. Для
этого Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Π΄Π΅Ρ€ΠΆΠ°Ρ‚ΡŒ Π² Π³ΠΎΠ»ΠΎΠ²Π΅ Ρ€Π°Π±ΠΎΡ‡ΠΈΠΉ процСсс: Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ количСство
ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡ с ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΈΠΌ Π²Ρ€Π΅ΠΌΠ΅Π½Π΅ΠΌ Ρ€Π°Π±ΠΎΡ‚Ρ‹ (ΠΈ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ частоС освобоТдСниС
CPU) ΠΈ нСсколько Π΄ΠΎΠ»Π³ΠΈΡ… Π·Π°Π΄Π°Ρ‡, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ CPU всС своС Ρ€Π°Π±ΠΎΡ‡Π΅Π΅ врСмя, ΠΏΡ€ΠΈ этом
врСмя ΠΎΡ‚ΠΊΠ»ΠΈΠΊΠ° для Ρ‚Π°ΠΊΠΈΡ… Π·Π°Π΄Π°Ρ‡ Π½Π΅ Π²Π°ΠΆΠ½ΠΎ. И Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ ΠΏΠ΅Ρ€Π²ΡƒΡŽ ΠΏΠΎΠΏΡ‹Ρ‚ΠΊΡƒ
Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ MLFQ со ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌΠΈ ΠΏΡ€Π°Π²ΠΈΠ»Π°ΠΌΠΈ:

  • Rule3: Когда Π·Π°Π΄Π°Ρ‡Π° поступаСт Π² систСму, ΠΎΠ½Π° помСщаСтся Π² ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ с Π½Π°ΠΈΠ²Ρ‹ΡΡˆΠΈΠΌ
  • ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ΠΎΠΌ.
  • Rule4a: Если Π·Π°Π΄Π°Ρ‡Π° ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ Ρ†Π΅Π»ΠΈΠΊΠΎΠΌ ΠΎΡ‚Π²Π΅Π΄Π΅Π½Π½ΠΎΠ΅ Π΅ΠΉ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠ΅ ΠΎΠΊΠ½ΠΎ, Ρ‚ΠΎ Π΅Π΅
  • ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ пониТаСтся.
  • Rule4b: Если Π—Π°Π΄Π°Ρ‡Π° освобоТдаСт CPU Π΄ΠΎ истСчСния своСго Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠ³ΠΎ ΠΎΠΊΠ½Π°, Ρ‚ΠΎ ΠΎΠ½Π°
  • остаСтся с ΠΏΡ€Π΅ΠΆΠ½ΠΈΠΌ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ΠΎΠΌ.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 1: ΠžΠ΄ΠΈΠ½ΠΎΡ‡Π½Π°Ρ Π΄ΠΎΠ»Π³ΠΎΡ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‰Π°Ρ Π·Π°Π΄Π°Ρ‡Π°

Как Π²ΠΈΠ΄Π½ΠΎ Π² этом ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅, Π·Π°Π΄Π°Ρ‡Π° ΠΏΡ€ΠΈ поступлСнии ставится с Π½Π°ΠΈΠ²Ρ‹ΡΡˆΠΈΠΌ
ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ΠΎΠΌ. ПослС Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠ³ΠΎ ΠΎΠΊΠ½Π° Π² 10мс процСсс пониТаСтся Π² ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π΅
ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊΠΎΠΌ. ПослС ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅Π³ΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠ³ΠΎ ΠΎΠΊΠ½Π° Π·Π°Π΄Π°Ρ‡Π°, Π½Π°ΠΊΠΎΠ½Π΅Ρ†, пониТаСтся Π΄ΠΎ
низшСго ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π° Π² систСмС, Π³Π΄Π΅ ΠΈ остаСтся.
Operating Systems: Three Easy Pieces. Part 5: ΠŸΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅: Multi-Level Feedback Queue (ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄)

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 2: ПодвСзли ΠΊΠΎΡ€ΠΎΡ‚ΠΊΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ

Π’Π΅ΠΏΠ΅Ρ€ΡŒ посмотрим ΠΏΡ€ΠΈΠΌΠ΅Ρ€ Ρ‚ΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ MLFQ попытаСтся ΠΏΡ€ΠΈΠ±Π»ΠΈΠ·ΠΈΡ‚ΡŒΡΡ ΠΊ SJF. Π’ этом
ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ Π΄Π²Π΅ Π·Π°Π΄Π°Ρ‡ΠΈ: А, которая являСтся Π΄ΠΎΠ»Π³ΠΎΠΈΠ³Ρ€Π°ΡŽΡ‰Π΅ΠΉ Π·Π°Π΄Π°Ρ‡Π΅ΠΉ постоянно
Π·Π°Π½ΠΈΠΌΠ°ΡŽΡ‰Π΅ΠΉ CPU ΠΈ B, которая являСтся ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΎΠΉ ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π·Π°Π΄Π°Ρ‡Π΅ΠΉ. ΠŸΡ€Π΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΠΌ,
Ρ‡Ρ‚ΠΎ А ΡƒΠΆΠ΅ Ρ€Π°Π±ΠΎΡ‚Π°Π»Π° Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ врСмя ΠΊ ΠΌΠΎΠΌΠ΅Π½Ρ‚Ρƒ ΠΊΠΎΠ³Π΄Π° поступила Π·Π°Π΄Π°Ρ‡Π° B.
Operating Systems: Three Easy Pieces. Part 5: ΠŸΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅: Multi-Level Feedback Queue (ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄)

На Π΄Π°Π½Π½ΠΎΠΌ Π³Ρ€Π°Ρ„ΠΈΠΊΠ΅ Π²ΠΈΠ΄Π½Ρ‹ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ сцСнария. Π—Π°Π΄Π°Ρ‡Π° А, ΠΊΠ°ΠΊ ΠΈ любая Π·Π°Π΄Π°Ρ‡Π°,
ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‰Π°Ρ CPU оказалась Π² самом Π½ΠΈΠ·Ρƒ. Π—Π°Π΄Π°Ρ‡Π° Π’ ΠΏΡ€ΠΈΠ±ΡƒΠ΄Π΅Ρ‚ Π²ΠΎ врСмя Π’=100 ΠΈ Π±ΡƒΠ΄Π΅Ρ‚
ΠΏΠΎΠΌΠ΅Ρ‰Π΅Π½Π° Π² ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ с Π½Π°ΠΈΠ²Ρ‹ΡΡˆΠΈΠΌ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ΠΎΠΌ. ΠŸΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ врСмя Π΅Π΅ Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π½Π΅Π²Π΅Π»ΠΈΠΊΠΎ, Ρ‚ΠΎ
ΠΎΠ½Π° Π·Π°Π²Π΅Ρ€ΡˆΠΈΡ‚ΡΡ Π΄ΠΎ Ρ‚ΠΎΠ³ΠΎ ΠΊΠ°ΠΊ достигнСт послСднСй ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ.

Из этого ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π° слСдуСт ΠΏΠΎΠ½ΡΡ‚ΡŒ Π³Π»Π°Π²Π½ΡƒΡŽ Ρ†Π΅Π»ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°: ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π½Π΅
Π·Π½Π°Π΅Ρ‚ длинная Π·Π°Π΄Π°Ρ‡Π° ΠΈΠ»ΠΈ короткая, Ρ‚ΠΎ Π² ΠΏΠ΅Ρ€Π²ΡƒΡŽ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ ΠΎΠ½ ΠΏΡ€Π΅Π΄ΠΏΠΎΠ»Π°Π³Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ Π·Π°Π΄Π°Ρ‡Π°
короткая ΠΈ Π²Ρ‹Π΄Π°Π΅Ρ‚ Π΅ΠΉ Π½Π°ΠΈΠ²Ρ‹ΡΡˆΠΈΠΉ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚. Если это Π΄Π΅ΠΉΡΡ‚Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ короткая Π·Π°Π΄Π°Ρ‡Π°, Ρ‚ΠΎ
ΠΎΠ½Π° выполнится быстро, ΠΈΠ½Π°Ρ‡Π΅ Ссли это длинная Π·Π°Π΄Π°Ρ‡Π°, Ρ‚ΠΎ ΠΎΠ½Π° Π±ΡƒΠ΄Π΅Ρ‚ ΠΌΠ΅Π΄Π»Π΅Π½Π½ΠΎ Π΄Π²ΠΈΠ³Π°Ρ‚ΡŒΡΡ
Π² ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π΅ Π²Π½ΠΈΠ· ΠΈ вскорС Π΄ΠΎΠΊΠ°ΠΆΠ΅Ρ‚, Ρ‡Ρ‚ΠΎ ΠΎΠ½Π° Π΄Π΅ΠΉΡΡ‚Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ долгая Π·Π°Π΄Π°Ρ‡Π°, которая Π½Π΅
Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ ΠΎΡ‚ΠΊΠ»ΠΈΠΊΠ°.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 3: Π§Ρ‚ΠΎ ΠΆΠ΅ ΠΎ Π²Π²ΠΎΠ΄Π΅-Π²Ρ‹Π²ΠΎΠ΄Π΅?

Π’Π΅ΠΏΠ΅Ρ€ΡŒ взглянСм Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€ с Π²Π²ΠΎΠ΄ΠΎΠΌ-Π²Ρ‹Π²ΠΎΠ΄ΠΎΠΌ. Как ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π°Π»ΠΎΡΡŒ Π² ΠΏΡ€Π°Π²ΠΈΠ»Π΅ 4b,
Ссли процСсс освобоТдаСт процСссор, Π½Π΅ использовав ΠΏΠΎΠ»Π½ΠΎΡΡ‚ΡŒΡŽ Π΅Π³ΠΎ процСссорноС врСмя,
Ρ‚ΠΎ ΠΎΠ½ остаСтся Π½Π° ΠΏΡ€Π΅ΠΆΠ½Π΅ΠΌ ΡƒΡ€ΠΎΠ²Π½Π΅ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π°. НамСрСния этого ΠΏΡ€Π°Π²ΠΈΠ»Π° довольно просты
β€” Ссли ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½ΠΎΠ΅ Π·Π°Π΄Π°Π½ΠΈΠ΅ выполняСт ΠΌΠ½ΠΎΠ³ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ Π²Π²ΠΎΠ΄Π°-Π²Ρ‹Π²ΠΎΠ΄Π°, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, оТидая
ΠΎΡ‚ ΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚Π΅Π»Ρ Π½Π°ΠΆΠ°Ρ‚ΠΈΠΉ клавиши ΠΈΠ»ΠΈ ΠΌΡ‹ΡˆΠΈ, Ρ‚Π°ΠΊΠΎΠ΅ Π·Π°Π΄Π°Π½ΠΈΠ΅ Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΡΠ²ΠΎΠ±ΠΎΠΆΠ΄Π°Ρ‚ΡŒ процСссор
Ρ€Π°Π½ΡŒΡˆΠ΅ ΠΎΡ‚Π²Π΅Π΄Π΅Π½Π½ΠΎΠ³ΠΎ ΠΎΠΊΠ½Π°. ΠœΡ‹ Π½Π΅ Ρ…ΠΎΡ‚Π΅Π»ΠΈ Π±Ρ‹ ΠΎΠΏΡƒΡΠΊΠ°Ρ‚ΡŒ Ρ‚Π°ΠΊΠΎΠ΅ Π·Π°Π΄Π°Π½ΠΈΠ΅ ΠΏΠΎ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Ρƒ,
ΠΈ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΎΠ½ΠΎ останСтся Π½Π° ΠΏΡ€Π΅ΠΆΠ½Π΅ΠΌ ΡƒΡ€ΠΎΠ²Π½Π΅.
Operating Systems: Three Easy Pieces. Part 5: ΠŸΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅: Multi-Level Feedback Queue (ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄)

Π­Ρ‚ΠΎΡ‚ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ ΠΏΠΎΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚ ΠΊΠ°ΠΊ Π±ΡƒΠ΄Π΅Ρ‚ Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ с Ρ‚Π°ΠΊΠΈΠΌΠΈ процСссами β€” ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½ΠΎΠ΅ Π·Π°Π΄Π°Π½ΠΈΠ΅ Π’, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ нуТдаСтся Π² CPU Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π½Π° 1мс ΠΏΠ΅Ρ€Π΅Π΄ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ΠΌ
процСсса Π²Π²ΠΎΠ΄Π°-Π²Ρ‹Π²ΠΎΠ΄Π° ΠΈ Π΄ΠΎΠ»Π³ΠΎΠ΅ Π·Π°Π΄Π°Π½ΠΈΠ΅ А, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ всС своС врСмя ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ CPU.
MLFQ Π΄Π΅Ρ€ΠΆΠΈΡ‚ процСсс Π’ с Π½Π°ΠΈΠ²Ρ‹ΡΡˆΠΈΠΌ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ΠΎΠΌ, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΎΠ½ всС врСмя ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠ°Π΅Ρ‚
ΠΎΡΠ²ΠΎΠ±ΠΎΠΆΠ΄Π°Ρ‚ΡŒ CPU. Если B β€” ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½ΠΎΠ΅ Π·Π°Π΄Π°Π½ΠΈΠ΅, Ρ‚ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π² Ρ‚Π°ΠΊΠΎΠΌ случаС достиг
своСй Ρ†Π΅Π»ΠΈ Π·Π°ΠΏΡƒΡΠΊΠ°Ρ‚ΡŒ ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½Ρ‹Π΅ Π·Π°Π΄Π°Ρ‡ΠΈ быстро.

ΠŸΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹ с Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ MLFQ

Π’ ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰ΠΈΡ… ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π°Ρ… ΠΌΡ‹ построили Π±Π°Π·ΠΎΠ²Ρ‹ΠΉ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ MLFQ. И каТСтся Ρ‡Ρ‚ΠΎ ΠΎΠ½
выполняСт свою Ρ€Π°Π±ΠΎΡ‚Ρƒ Ρ…ΠΎΡ€ΠΎΡˆΠΎ ΠΈ чСстно, распрСдСляя процСссорноС врСмя чСстно ΠΌΠ΅ΠΆΠ΄Ρƒ
Π΄ΠΎΠ»Π³ΠΈΠΌΠΈ Π·Π°Π΄Π°Ρ‡Π°ΠΌΠΈ ΠΈ позволяя ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΈΠΌ Π·Π°Π΄Π°Ρ‡Π°ΠΌ ΠΈΠ»ΠΈ Π·Π°Π΄Π°Ρ‡Π°ΠΌ интСнсивно ΠΎΠ±Ρ€Π°Ρ‰Π°ΡŽΡ‰ΠΈΠΌΡΡ
ΠΊ Π²Π²ΠΎΠ΄Ρƒ-Π²Ρ‹Π²ΠΎΠ΄Ρƒ ΠΎΡ‚Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒ быстро. К соТалСнию, Ρ‚Π°ΠΊΠΎΠΉ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ содСрТит нСсколько
ΡΠ΅Ρ€ΡŒΠ΅Π·Π½Ρ‹Ρ… ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌ.
Π’ΠΎ-ΠΏΠ΅Ρ€Π²Ρ‹Ρ…, ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ° Π³ΠΎΠ»ΠΎΠ΄Π°: Ссли Π² систСмС Π±ΡƒΠ΄Π΅Ρ‚ мноТСство ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½Ρ‹Ρ…
Π·Π°Π΄Π°Ρ‡, Ρ‚ΠΎ ΠΎΠ½ΠΈ Π±ΡƒΠ΄ΡƒΡ‚ ΠΏΠΎΡ‚Ρ€Π΅Π±Π»ΡΡ‚ΡŒ всС процСссорноС врСмя ΠΈ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ Π½ΠΈ ΠΎΠ΄Π½ΠΎ Π΄ΠΎΠ»Π³ΠΎΠ΅
Π·Π°Π΄Π°Π½ΠΈΠ΅ Π½Π΅ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ возмоТности ΠΈΡΠΏΠΎΠ»Π½ΡΡ‚ΡŒΡΡ (ΠΎΠ½ΠΈ Π³ΠΎΠ»ΠΎΠ΄Π°ΡŽΡ‚).

Π’ΠΎ-Π²Ρ‚ΠΎΡ€Ρ‹Ρ…, ΡƒΠΌΠ½Ρ‹Π΅ ΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚Π΅Π»ΠΈ ΠΌΠΎΠ³Π»ΠΈ Π±Ρ‹ ΠΏΠΈΡΠ°Ρ‚ΡŒ свои ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ Ρ‚Π°ΠΊ, Ρ‡Ρ‚ΠΎΠ±Ρ‹
ΠΎΠ±ΠΌΠ°Π½ΡƒΡ‚ΡŒ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ. Обман кроСтся Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ Ρ‡Ρ‚ΠΎ-Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π·Π°ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ
ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ Π²Ρ‹Π΄Π°Π²Π°Ρ‚ΡŒ процСссу большС процСссорного Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ. Алгоритм, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ
описан Π²Ρ‹ΡˆΠ΅ Π²ΠΏΠΎΠ»Π½Π΅ уязвим ΠΊ ΠΏΠΎΠ΄ΠΎΠ±Π½Ρ‹ΠΌ Π°Ρ‚Π°ΠΊΠ°ΠΌ: ΠΏΠ΅Ρ€Π΅Π΄ Ρ‚Π΅ΠΌ ΠΊΠ°ΠΊ ΠΎΠΊΠ½ΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ практичСски
ΠΊΠΎΠ½Ρ‡ΠΈΠ»ΠΎΡΡŒ Π½ΡƒΠΆΠ½ΠΎ Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΡŽ Π²Π²ΠΎΠ΄Π°-Π²Ρ‹Π²ΠΎΠ΄Π° (ΠΊ ΠΊΠ°ΠΊΠΎΠΌΡƒ-Ρ‚ΠΎ, Π½Π΅Π²Π°ΠΆΠ½ΠΎ ΠΊΠ°ΠΊΠΎΠΌΡƒ Ρ„Π°ΠΉΠ»Ρƒ)
ΠΈ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΎΡΠ²ΠΎΠ±ΠΎΠ΄ΠΈΡ‚ΡŒ CPU. ПодобноС ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΡ‚ ΠΎΡΡ‚Π°Π²Π°Ρ‚ΡŒΡΡ Π² Ρ‚ΠΎΠΉ ΠΆΠ΅
самой ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ ΠΈ снова ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ больший ΠΏΡ€ΠΎΡ†Π΅Π½Ρ‚ процСссорного Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ. Если ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ
это ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΠΎ (Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, ΠΈΡΠΏΠΎΠ»Π½ΡΡ‚ΡŒΡΡ 99% Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ ΠΎΠΊΠ½Π° ΠΏΠ΅Ρ€Π΅Π΄ освобоТдСниСм CPU),
такая Π·Π°Π΄Π°Ρ‡Π° попросту ΠΌΠΎΠΆΠ΅Ρ‚ ΠΌΠΎΠ½ΠΎΠΏΠΎΠ»ΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ процСссор.

НаконСц, ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° ΠΌΠΎΠΆΠ΅Ρ‚ ΠΌΠ΅Π½ΡΡ‚ΡŒ своС ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ со Π²Ρ€Π΅ΠΌΠ΅Π½Π΅ΠΌ. Π’Π΅ Π·Π°Π΄Π°Ρ‡ΠΈ,
ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ использовали CPU, ΠΌΠΎΠ³ΡƒΡ‚ ΡΡ‚Π°Ρ‚ΡŒ ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΌΠΈ. Π’ нашСм ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ ΠΏΠΎΠ΄ΠΎΠ±Π½Ρ‹Π΅
Π·Π°Π΄Π°Ρ‡ΠΈ Π½Π΅ ΠΏΠΎΠ»ΡƒΡ‡Π°Ρ‚ Π΄ΠΎΠ»ΠΆΠ½ΠΎΠ³ΠΎ обращСния ΠΎΡ‚ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊΠ°, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠ»ΠΈ Π±Ρ‹ Π΄Ρ€ΡƒΠ³ΠΈΠ΅
(ΠΈΠ·Π½Π°Ρ‡Π°Π»ΡŒΠ½Ρ‹Π΅) ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½Ρ‹Π΅ Π·Π°Π΄Π°Ρ‡ΠΈ.

Вопрос ΠΊ Π·Π°Π»Ρƒ: ΠΊΠ°ΠΊΠΈΠ΅ Π°Ρ‚Π°ΠΊΠΈ Π½Π° ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ ΠΌΠΎΠΆΠ½ΠΎ Π±Ρ‹Π»ΠΎ ΡΠΎΠ²Π΅Ρ€ΡˆΠ°Ρ‚ΡŒ Π² соврСмСнном ΠΌΠΈΡ€Π΅?

ΠŸΠΎΠΏΡ‹Ρ‚ΠΊΠ° 2: ΠŸΠΎΠ²Ρ‹ΡˆΠ΅Π½ΠΈΠ΅ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π°

ΠŸΠΎΠΏΡ€ΠΎΠ±ΡƒΠ΅ΠΌ ΠΏΠΎΠΌΠ΅Π½ΡΡ‚ΡŒ ΠΏΡ€Π°Π²ΠΈΠ»Π° ΠΈ посмотрим получится Π»ΠΈ ΠΈΠ·Π±Π΅ΠΆΠ°Ρ‚ΡŒ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌ с
Π³ΠΎΠ»ΠΎΠ΄Π°Π½ΠΈΠ΅ΠΌ. Π§Ρ‚ΠΎ Π±Ρ‹ ΠΌΡ‹ ΠΌΠΎΠ³Π»ΠΈ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ для Ρ‚ΠΎΠ³ΠΎ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ связанныС с
CPU Π·Π°Π΄Π°Ρ‡ΠΈ ΠΏΠΎΠ»ΡƒΡ‡Π°Ρ‚ своС врСмя (Π΄Π°ΠΆΠ΅ Ссли ΠΈ Π½Π΅ Π΄ΠΎΠ»Π³ΠΎΠ΅).
Π’ качСствС простого Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€Π΅Π΄Π»ΠΎΠΆΠΈΡ‚ΡŒ пСриодичСски
ΠΏΠΎΠ²Ρ‹ΡˆΠ°Ρ‚ΡŒ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ всСх Ρ‚Π°ΠΊΠΈΡ… Π·Π°Π΄Π°Ρ‡ Π² систСмС. БущСствуСт мноТСство способов
достиТСния этого, ΠΏΠΎΠΏΡ€ΠΎΠ±ΡƒΠ΅ΠΌ Π²ΠΎΠΏΠ»ΠΎΡ‚ΠΈΡ‚ΡŒ Π² качСствС ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π° Ρ‡Ρ‚ΠΎ-Ρ‚ΠΎ простоС: ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄ΠΈΡ‚ΡŒ
сразу всС Π·Π°Π΄Π°Ρ‡ΠΈ Π² Π½Π°ΠΈΠ²Ρ‹ΡΡˆΠΈΠΉ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚, ΠΎΡ‚ΡΡŽΠ΄Π° Π½ΠΎΠ²ΠΎΠ΅ ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ:

  • Rule5: По ΠΏΡ€ΠΎΡˆΠ΅ΡΡ‚Π²ΠΈΠΈ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ ΠΏΠ΅Ρ€ΠΈΠΎΠ΄Π° S пСрСвСсти всС Π·Π°Π΄Π°Ρ‡ΠΈ Π² систСмС Π² Π½Π°ΠΈΠ²Ρ‹ΡΡˆΡƒΡŽ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ.

НашС Π½ΠΎΠ²ΠΎΠ΅ ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ Ρ€Π΅ΡˆΠ°Π΅Ρ‚ Π΄Π²Π΅ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹ сразу. Π’ΠΎ-ΠΏΠ΅Ρ€Π²Ρ‹Ρ…, процСссы
Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎ Π½Π΅ Π³ΠΎΠ»ΠΎΠ΄Π°ΡŽΡ‚: Π·Π°Π΄Π°Ρ‡ΠΈ, находящиСся Π² Π²Ρ‹ΡΡˆΠ΅ΠΉ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ Π±ΡƒΠ΄ΡƒΡ‚ Π΄Π΅Π»ΠΈΡ‚ΡŒ
процСссорноС врСмя согласно Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ RR ΠΈ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ всС процСссы ΠΏΠΎΠ»ΡƒΡ‡Π°Ρ‚
процСссорноС врСмя. Π’ΠΎ-Π²Ρ‚ΠΎΡ€Ρ‹Ρ…, Ссли ΠΊΠ°ΠΊΠΎΠΉ-Ρ‚ΠΎ процСсс, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Ρ€Π°Π½Π΅Π΅ использовал
Ρ‚ΠΎΠ»ΡŒΠΊΠΎ процСссор, становится ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΌ, Ρ‚ΠΎ ΠΎΠ½ Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΡΡ‚Π°Π²Π°Ρ‚ΡŒΡΡ Π² ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ с Π²Ρ‹ΡΡˆΠΈΠΌ
ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ΠΎΠΌ послС Ρ‚ΠΎΠ³ΠΎ ΠΊΠ°ΠΊ Π΅Π΄ΠΈΠ½ΠΎΠΆΠ΄Ρ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ ΠΏΠΎΠ²Ρ‹ΡˆΠ΅Π½ΠΈΠ΅ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π° Π΄ΠΎ Π½Π°ΠΈΠ²Ρ‹ΡΡˆΠ΅Π³ΠΎ.
Рассмотрим ΠΏΡ€ΠΈΠΌΠ΅Ρ€. Π’ этом сцСнарии рассмотрим ΠΎΠ΄ΠΈΠ½ процСсс, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‰ΠΈΠΉ
Operating Systems: Three Easy Pieces. Part 5: ΠŸΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅: Multi-Level Feedback Queue (ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄)

CPU ΠΈ Π΄Π²Π° ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½Ρ‹Ρ…, ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΈΡ… процСсса. Π‘Π»Π΅Π²Π° Π½Π° рисункС рисунок дСмонстрируСт ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ Π±Π΅Π· ΠΏΠΎΠ²Ρ‹ΡˆΠ΅Π½ΠΈΡ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π°, ΠΈ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ долгая Π·Π°Π΄Π°Ρ‡Π° Π½Π°Ρ‡ΠΈΠ½Π°Π΅Ρ‚ Π³ΠΎΠ»ΠΎΠ΄Π°Ρ‚ΡŒ послС прибытия Π² систСму Π΄Π²ΡƒΡ… ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡. На рисункС справа ΠΊΠ°ΠΆΠ΄Ρ‹Π΅ 50мс выполняСтся ΠΏΠΎΠ²Ρ‹ΡˆΠ΅Π½ΠΈΠ΅ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π° ΠΈ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ всС процСссы Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎ ΠΏΠΎΠ»ΡƒΡ‡Π°ΡŽΡ‚ процСссорноС врСмя ΠΈ Π±ΡƒΠ΄ΡƒΡ‚ пСриодичСски Π·Π°ΠΏΡƒΡΠΊΠ°Ρ‚ΡŒΡΡ. 50мс Π² Π΄Π°Π½Π½ΠΎΠΌ случаС взято для ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π°, Ρ€Π΅Π°Π»ΡŒΠ½ΠΎ это число нСсколько большС.
ΠžΡ‡Π΅Π²ΠΈΠ΄Π½ΠΎ, Ρ‡Ρ‚ΠΎ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠ΅ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ пСриодичСского ΠΏΠΎΠ²Ρ‹ΡˆΠ΅Π½ΠΈΡ S ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ
Π·Π°ΠΊΠΎΠ½ΠΎΠΌΠ΅Ρ€Π½ΠΎΠΌΡƒ вопросу: ΠΊΠ°ΠΊΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±Ρ‹Ρ‚ΡŒ выставлСно? Один ΠΈΠ· заслуТСнных
систСмных ΠΈΠ½ΠΆΠ΅Π½Π΅Ρ€ΠΎΠ² John Ousterhout Π½Π°Π·Ρ‹Π²Π°Π» ΠΏΠΎΠ΄ΠΎΠ±Π½Ρ‹Π΅ Π²Π΅Π»ΠΈΡ‡ΠΈΠ½Ρ‹ Π² систСмах ΠΊΠ°ΠΊ voo-doo
константа, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΎΠ½ΠΈ Π² Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ Ρ€ΠΎΠ΄Π΅ Ρ‚Ρ€Π΅Π±ΠΎΠ²Π°Π»ΠΈ Ρ‡Π΅Ρ€Π½ΠΎΠΉ ΠΌΠ°Π³ΠΈΠΈ для ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚Π½ΠΎΠ³ΠΎ
выставлСния. И, ΠΊ соТалСнию S ΠΈΠΌΠ΅Π΅Ρ‚ Ρ‚Π°ΠΊΠΎΠΉ Π°Ρ€ΠΎΠΌΠ°Ρ‚. Если Π²Ρ‹ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ слишком
большим β€” Π΄ΠΎΠ»Π³ΠΈΠ΅ Π·Π°Π΄Π°Ρ‡ΠΈ Π½Π°Ρ‡Π½ΡƒΡ‚ Π³ΠΎΠ»ΠΎΠ΄Π°Ρ‚ΡŒ. А Ссли Π²Ρ‹ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ слишком Π½ΠΈΠ·ΠΊΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅,
ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½Ρ‹Π΅ Π·Π°Π΄Π°Ρ‡ΠΈ Π½Π΅ ΠΏΠΎΠ»ΡƒΡ‡Π°Ρ‚ Π΄ΠΎΠ»ΠΆΠ½ΠΎΠ³ΠΎ процСссорного Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ.

ΠŸΠΎΠΏΡ‹Ρ‚ΠΊΠ° 3: Π›ΡƒΡ‡ΡˆΠΈΠΉ ΡƒΡ‡Π΅Ρ‚

Π’Π΅ΠΏΠ΅Ρ€ΡŒ Ρƒ нас Π΅ΡΡ‚ΡŒ Π΅Ρ‰Π΅ ΠΎΠ΄Π½Π° ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ°, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Ρ€Π΅ΡˆΠΈΡ‚ΡŒ: ΠΊΠ°ΠΊ Π½Π΅
ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡ‚ΡŒ ΠΎΠ±ΠΌΠ°Π½Ρ‹Π²Π°Ρ‚ΡŒ наш ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ? Π’ΠΈΠ½ΠΎΠ²Π°Ρ‚Ρ‹ΠΌΠΈ Π² этой возмоТности ΠΎΠΊΠ°Π·Ρ‹Π²Π°ΡŽΡ‚ΡΡ
ΠΏΡ€Π°Π²ΠΈΠ»Π° 4a, 4b, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‚ заданию ΡΠΎΡ…Ρ€Π°Π½ΡΡ‚ΡŒ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚, освобоТдая процСссор
Π΄ΠΎ истСчСния Π²Ρ‹Π΄Π΅Π»Π΅Π½Π½ΠΎΠ³ΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ. Как ΠΆΠ΅ с этим ΡΠΏΡ€Π°Π²ΠΈΡ‚ΡŒΡΡ?
РСшСниСм Π² этом случаС ΠΌΠΎΠΆΠ½ΠΎ ΡΡ‡ΠΈΡ‚Π°Ρ‚ΡŒ Π»ΡƒΡ‡ΡˆΠΈΠΉ ΡƒΡ‡Π΅Ρ‚ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ CPU Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ
ΡƒΡ€ΠΎΠ²Π½Π΅ MLFQ. ВмСсто Ρ‚ΠΎΠ³ΠΎ Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π·Π°Π±Ρ‹Π²Π°Ρ‚ΡŒ врСмя, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° использовала
процСссор Π·Π° ΠΎΡ‚Π²Π΅Π΄Π΅Π½Π½Ρ‹ΠΉ ΠΏΡ€ΠΎΠΌΠ΅ΠΆΡƒΡ‚ΠΎΠΊ, слСдуСт ΡƒΡ‡ΠΈΡ‚Ρ‹Π²Π°Ρ‚ΡŒ ΠΈ ΡΠΎΡ…Ρ€Π°Π½ΡΡ‚ΡŒ Π΅Π³ΠΎ. ПослС Ρ‚ΠΎΠ³ΠΎ ΠΊΠ°ΠΊ
процСсс израсходовал ΠΎΡ‚Π²Π΅Π΄Π΅Π½Π½ΠΎΠ΅ Π΅ΠΌΡƒ врСмя слСдуСт ΠΏΠΎΠ½ΠΈΠΆΠ°Ρ‚ΡŒ Π΅Π³ΠΎ Π΄ΠΎ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅Π³ΠΎ
уровня ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π°. Π’Π΅ΠΏΠ΅Ρ€ΡŒ Π½Π΅Π²Π°ΠΆΠ½ΠΎ ΠΊΠ°ΠΊ процСсс Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ своС врСмя β€” ΠΊΠ°ΠΊ
постоянно Π²Ρ‹Ρ‡ΠΈΡΠ»ΡΡŽΡ‰ΠΈΠΉ Π½Π° процСссорС ΠΈΠ»ΠΈ ΠΊΠ°ΠΊ мноТСство Π²Ρ‹Π·ΠΎΠ²ΠΎΠ². Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ,
слСдуСт ΠΏΠ΅Ρ€Π΅ΠΏΠΈΡΠ°Ρ‚ΡŒ ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ 4 ΠΊ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌΡƒ Π²ΠΈΠ΄Ρƒ:

  • Rule4: ПослС Ρ‚ΠΎΠ³ΠΎ ΠΊΠ°ΠΊ Π·Π°Π΄Π°Ρ‡Π° израсходовала Π²Ρ‹Π΄Π΅Π»Π΅Π½Π½ΠΎΠ΅ Π΅ΠΉ врСмя Π² Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ (нСзависимо ΠΎΡ‚ Ρ‚ΠΎΠ³ΠΎ сколько Ρ€Π°Π· ΠΎΠ½Π° освобоТдала CPU) ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ Ρ‚Π°ΠΊΠΎΠΉ Π·Π°Π΄Π°Ρ‡ΠΈ пониТаСтся (ΠΎΠ½Π° двигаСтся Π²Π½ΠΈΠ· ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ).

ΠŸΠΎΡΠΌΠΎΡ‚Ρ€ΠΈΠΌ Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€:
Operating Systems: Three Easy Pieces. Part 5: ΠŸΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅: Multi-Level Feedback Queue (ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄)»

На рисункС ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ Ρ‡Ρ‚ΠΎ случаСтся, Ссли ΠΏΠΎΠΏΡ€ΠΎΠ±ΠΎΠ²Π°Ρ‚ΡŒ ΠΎΠ±ΠΌΠ°Π½ΡƒΡ‚ΡŒ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ, ΠΊΠ°ΠΊ
Ссли Π±Ρ‹ Π±Ρ‹Π»ΠΎ с ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰ΠΈΠΌΠΈ ΠΏΡ€Π°Π²ΠΈΠ»Π°ΠΌΠΈ 4a, 4b получится Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ слСва. Π‘ Π½ΠΎΠ²Ρ‹ΠΌ
ΠΏΡ€Π°Π²ΠΈΠ»ΠΎΠΌ β€” Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ справа. Π”ΠΎ Π·Π°Ρ‰ΠΈΡ‚Ρ‹ любой процСсс ΠΌΠΎΠ³ Π²Ρ‹Π·Π²Π°Ρ‚ΡŒ I/O Π΄ΠΎ Π·Π°Π²Π΅Ρ€ΡˆΠ΅Π½ΠΈΡ ΠΈ
Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ Π΄ΠΎΠΌΠΈΠ½ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π½Π° CPU, послС Π²ΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΡ Π·Π°Ρ‰ΠΈΡ‚Ρ‹, нСзависимо ΠΎΡ‚ повСдСния
I/O, ΠΎΠ½ Π±ΡƒΠ΄Π΅Ρ‚ всС Ρ€Π°Π²Π½ΠΎ ΠΎΠΏΡƒΡΠΊΠ°Ρ‚ΡŒΡΡ Π² ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ Π²Π½ΠΈΠ· ΠΈ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ Π½Π΅ смоТСт нСчСстно
Π·Π°Π²Π»Π°Π΄Π΅Ρ‚ΡŒ рСсурсами CPU.

Π£Π»ΡƒΡ‡ΡˆΠ°Π΅ΠΌ MLFQ ΠΈ ΠΏΡ€ΠΎΡ‡ΠΈΠ΅ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹

Π‘ ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½Ρ‹ΠΌΠΈ Π²Ρ‹ΡˆΠ΅ ΡƒΠ»ΡƒΡ‡ΡˆΠ΅Π½ΠΈΡΠΌΠΈ Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡŽΡ‚ Π½ΠΎΠ²Ρ‹Π΅ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹: ΠΎΠ΄ΠΈΠ½ ΠΈΠ· Π³Π»Π°Π²Π½Ρ‹Ρ…
вопросов β€” ΠΊΠ°ΠΊ ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€ΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΠΎΠ΄ΠΎΠ±Π½Ρ‹ΠΉ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ? Π’.Π΅. Бколько Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±Ρ‹Ρ‚ΡŒ
ΠΎΡ‡Π΅Ρ€Π΅Π΄Π΅ΠΉ? Каков Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±Ρ‹Ρ‚ΡŒ Ρ€Π°Π·ΠΌΠ΅Ρ€ ΠΎΠΊΠ½Π° Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ Π² ΠΏΡ€Π΅Π΄Π΅Π»Π°Ρ… ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ? Как
часто слСдуСт ΠΏΠΎΠ²Ρ‹ΡˆΠ°Ρ‚ΡŒ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ для Ρ‚ΠΎΠ³ΠΎ Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΈΠ·Π±Π΅ΠΆΠ°Ρ‚ΡŒ голодания ΠΈ
ΠΏΡ€ΠΈΠ½ΡΡ‚ΡŒ Π²ΠΎ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ повСдСния ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹? На эти вопросы, Π½Π΅Ρ‚ простого
ΠΎΡ‚Π²Π΅Ρ‚Π° ΠΈ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ экспСримСнты с Π½Π°Π³Ρ€ΡƒΠ·ΠΊΠ°ΠΌΠΈ ΠΈ ΠΏΠΎΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅Π΅ ΠΊΠΎΠ½Ρ„ΠΈΠ³ΡƒΡ€ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅
ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊΠ° ΠΌΠΎΠΆΠ΅Ρ‚ привСсти ΠΊ Π½Π΅ΠΊΠΎΠ΅ΠΌΡƒ ΡƒΠ΄ΠΎΠ²Π»Π΅Ρ‚Π²ΠΎΡ€ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΌΡƒ балансу.

НапримСр, Π±ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²ΠΎ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΉ MLFQ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‚ Π½Π°Π·Π½Π°Ρ‡Π°Ρ‚ΡŒ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅
Π²Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»Ρ‹ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹ΠΌ очСрСдям. ВысокоприоритСтным очСрСдям ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ
Π½Π°Π·Π½Π°Ρ‡Π°ΡŽΡ‚ΡΡ ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΈΠ΅ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»Ρ‹. Π­Ρ‚ΠΈ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ состоят ΠΈΠ· ΠΈΠ½Ρ‚Π΅Ρ€Π°ΠΊΡ‚ΠΈΠ²Π½Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡,
ΠΏΠ΅Ρ€Π΅ΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρƒ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΌΠΈ довольно Ρ‡ΡƒΠ²ΡΡ‚Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΈ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π·Π°Π½ΠΈΠΌΠ°Ρ‚ΡŒ 10 ΠΈΠ»ΠΈ мСньшС
мс. Π’ противовСс Π½ΠΈΠ·ΠΊΠΎΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π½Ρ‹Π΅ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ состоят ΠΈΠ· Π΄ΠΎΠ»Π³ΠΈΡ… Π·Π°Π΄Π°Ρ‡, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‰ΠΈΡ…
CPU. И Π² этом случаС Π΄Π»ΠΈΠ½Π½Ρ‹Π΅ Π²Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ ΠΈΠ½Ρ‚Π΅Ρ€Π²Π°Π»Ρ‹ подходят ΠΎΡ‡Π΅Π½ΡŒ Ρ…ΠΎΡ€ΠΎΡˆΠΎ (100мс).
Operating Systems: Three Easy Pieces. Part 5: ΠŸΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅: Multi-Level Feedback Queue (ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄)

Π’ этом ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ Π΅ΡΡ‚ΡŒ 2 Π·Π°Π΄Π°Ρ‡ΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΏΡ€ΠΎΡ€Π°Π±ΠΎΡ‚Π°Π»ΠΈ Π² высокоприоритСтной ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ 20
мс, Ρ€Π°Π·Π±ΠΈΡ‚Ρ‹Π΅ Π½Π° ΠΎΠΊΠ½Π° ΠΏΠΎ 10мс. 40мс Π² срСднСй ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ (ΠΎΠΊΠ½ΠΎ Π² 20мс) ΠΈ Π² Π½ΠΈΠ·ΠΊΠΎΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π½ΠΎΠΉ
ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠ΅ ΠΎΠΊΠ½ΠΎ стало 40мс, Π³Π΄Π΅ Π·Π°Π΄Π°Ρ‡ΠΈ Π·Π°Π²Π΅Ρ€ΡˆΠΈΠ»ΠΈ свою Ρ€Π°Π±ΠΎΡ‚Ρƒ.

РСализация MLFQ Π² ОБ Solaris β€” класс ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊΠΎΠ², Ρ€Π°Π·Π΄Π΅Π»ΡΡŽΡ‰ΠΈΡ… ΠΏΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ.
ΠŸΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ прСдоставлят Π½Π°Π±ΠΎΡ€ Ρ‚Π°Π±Π»ΠΈΡ†, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‚ Π² точности, ΠΊΠ°ΠΊ Π΄ΠΎΠ»ΠΆΠ΅Π½
ΠΌΠ΅Π½ΡΡ‚ΡŒΡΡ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ процСсса с Ρ‚Π΅Ρ‡Π΅Π½ΠΈΠ΅ΠΌ Π΅Π³ΠΎ ΠΆΠΈΠ·Π½ΠΈ, ΠΊΠ°ΠΊΠΈΠΌ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±Ρ‹Ρ‚ΡŒ Ρ€Π°Π·ΠΌΠ΅Ρ€
выдСляСмого ΠΎΠΊΠ½Π° ΠΈ ΠΊΠ°ΠΊ часто Π½ΡƒΠΆΠ½ΠΎ ΠΏΠΎΠ΄Π½ΠΈΠΌΠ°Ρ‚ΡŒ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Ρ‹ Π·Π°Π΄Π°Ρ‡ΠΈ. Администратор
систСмы ΠΌΠΎΠΆΠ΅Ρ‚ Π²Π·Π°ΠΈΠΌΠΎΠ΄Π΅ΠΉΡΡ‚Π²ΠΎΠ²Π°Ρ‚ΡŒ с этой Ρ‚Π°Π±Π»ΠΈΡ†Π΅ΠΉ ΠΈ Π·Π°ΡΡ‚Π°Π²Π»ΡΡ‚ΡŒ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ вСсти сСбя
ΠΏΠΎ-Π΄Ρ€ΡƒΠ³ΠΎΠΌΡƒ. По-ΡƒΠΌΠΎΠ»Ρ‡Π°Π½ΠΈΡŽ Π² этой Ρ‚Π°Π±Π»ΠΈΡ†Π΅ 60 ΠΎΡ‡Π΅Ρ€Π΅Π΄Π΅ΠΉ с постСпСнным ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠ΅ΠΌ
Ρ€Π°Π·ΠΌΠ΅Ρ€Π° ΠΎΠΊΠ½Π° с 20мс (высокий ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚) Π΄ΠΎ Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… сотСн мс (низший ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚), Π°
Ρ‚Π°ΠΊΠΆΠ΅ с бустом всСх Π·Π°Π΄Π°Ρ‡ Ρ€Π°Π· Π² сСкунду.

Π”Ρ€ΡƒΠ³ΠΈΠ΅ MLFQ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊΠΈ Π½Π΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ ΠΈΠ»ΠΈ ΠΊΠ°ΠΊΠΈΠ΅-Ρ‚ΠΎ ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½Ρ‹Π΅
ΠΏΡ€Π°Π²ΠΈΠ»Π°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ описаны Π² этой Π»Π΅ΠΊΡ†ΠΈΠΈ, Π½Π°ΠΏΡ€ΠΎΡ‚ΠΈΠ² ΠΎΠ½ΠΈ Π²Ρ‹Ρ‡ΠΈΡΠ»ΡΡŽΡ‚ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Ρ‹, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ
матСматичСскиС Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρ‹. Π’Π°ΠΊ, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ Π² FreeBSD ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρƒ для
вычислСния Ρ‚Π΅ΠΊΡƒΡ‰Π΅Π³ΠΎ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π° Π·Π°Π΄Π°Ρ‡ΠΈ, ΠΎΡΠ½ΠΎΠ²Ρ‹Π²Π°ΡΡΡŒ Π½Π° Ρ‚ΠΎΠΌ, сколько процСсс
использовал CPU. Π’ Π΄ΠΎΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅, использованиС CPU со Π²Ρ€Π΅ΠΌΠ΅Π½Π΅ΠΌ Π·Π°Π³Π½ΠΈΠ²Π°Π΅Ρ‚, ΠΈ Ρ‚Π°ΠΊΠΈΠΌ
ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΏΠΎΠ²Ρ‹ΡˆΠ΅Π½ΠΈΠ΅ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π° происходит нСсколько ΠΈΠ½Π°Ρ‡Π΅, Ρ‡Π΅ΠΌ описано Π²Ρ‹ΡˆΠ΅. Π­Ρ‚ΠΎ Ρ‚Π°ΠΊ
Π½Π°Π·Ρ‹Π²Π°Π΅ΠΌΡ‹Π΅ decay Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹. Π‘ вСрсии 7.1 Π² FreeBSD ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊ ULE.

НаконСц, ΠΌΠ½ΠΎΠ³ΠΈΠ΅ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊΠΈ ΠΈΠΌΠ΅ΡŽΡ‚ Π΄Ρ€ΡƒΠ³ΠΈΠ΅ особСнности. НапримСр, Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅
ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊΠΈ Ρ€Π΅Π·Π΅Ρ€Π²ΠΈΡ€ΡƒΡŽΡ‚ Π²Ρ‹ΡΡˆΠΈΠ΅ ΡƒΡ€ΠΎΠ²Π½ΠΈ для Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ систСмы ΠΈ Ρ‚Π°ΠΊΠΈΠΌ
ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, Π½ΠΈΠΊΠ°ΠΊΠΎΠΉ ΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΡΠΊΠΈΠΉ процСсс Π½Π΅ смоТСт ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ Π½Π°ΠΈΠ²Ρ‹ΡΡˆΠΈΠΉ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ Π²
систСмС. НСкоторыС систСмы ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‚ Π΄Π°Π²Π°Ρ‚ΡŒ совСты для Ρ‚ΠΎΠ³ΠΎ Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎΠΌΠΎΡ‡ΡŒ
ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊΡƒ ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚Π½ΠΎ Π²Ρ‹ΡΡ‚Π°Π²Π»ΡΡ‚ΡŒ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Ρ‹. Π’Π°ΠΊ Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΊΠΎΠΌΠ°Π½Π΄Ρ‹ nice
ΠΌΠΎΠΆΠ½ΠΎ ΡƒΠ²Π΅Π»ΠΈΡ‡ΠΈΠ²Π°Ρ‚ΡŒ ΠΈΠ»ΠΈ ΡƒΠΌΠ΅Π½ΡŒΡˆΠ°Ρ‚ΡŒ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ Π·Π°Π΄Π°Ρ‡ΠΈ ΠΈ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΏΠΎΠ²Ρ‹ΡˆΠ°Ρ‚ΡŒ ΠΈΠ»ΠΈ
ΠΏΠΎΠ½ΠΈΠΆΠ°Ρ‚ΡŒ ΡˆΠ°Π½ΡΡ‹ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ Π½Π° процСссорноС врСмя.

MLFQ: Π˜Ρ‚ΠΎΠ³ΠΈ

ΠœΡ‹ описали ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ ΠΊ ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΡŽ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ называСтся MLFQ. Π•Π³ΠΎ Π½Π°Π·Π²Π°Π½ΠΈΠ΅
Π·Π°ΠΊΠ»ΡŽΡ‡Π΅Π½ΠΎ Π² ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΠ΅ Ρ€Π°Π±ΠΎΡ‚Ρ‹ β€” ΠΎΠ½ ΠΈΠΌΠ΅Π΅Ρ‚ нСсколько ΠΎΡ‡Π΅Ρ€Π΅Π΄Π΅ΠΉ ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ ΠΎΠ±Ρ€Π°Ρ‚Π½ΡƒΡŽ связь
для опрСдСлСния ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Π° Π·Π°Π΄Π°Ρ‡ΠΈ.
Π˜Ρ‚ΠΎΠ³ΠΎΠ²Ρ‹ΠΉ Π²ΠΈΠ΄ ΠΏΡ€Π°Π²ΠΈΠ» Π±ΡƒΠ΄Π΅Ρ‚ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ:

  • Rule1: Если ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚(А) > ΠŸΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚(Π‘), Π±ΡƒΠ΄Π΅Ρ‚ Π·Π°ΠΏΡƒΡ‰Π΅Π½Π° Π·Π°Π΄Π°Ρ‡Π° А (Π‘ Π½Π΅ Π±ΡƒΠ΄Π΅Ρ‚)
  • Rule2: Если ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚(А) = ΠŸΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚(Π‘), АиБ Π·Π°ΠΏΡƒΡΠΊΠ°ΡŽΡ‚ΡΡ с использованиСм RR
  • Rule3: Когда Π·Π°Π΄Π°Ρ‡Π° поступаСт Π² систСму, ΠΎΠ½Π° помСщаСтся Π² ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ с Π½Π°ΠΈΠ²Ρ‹ΡΡˆΠΈΠΌ ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ΠΎΠΌ.
  • Rule4: ПослС Ρ‚ΠΎΠ³ΠΎ ΠΊΠ°ΠΊ Π·Π°Π΄Π°Ρ‡Π° израсходовала Π²Ρ‹Π΄Π΅Π»Π΅Π½Π½ΠΎΠ΅ Π΅ΠΉ врСмя Π² Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ (нСзависимо ΠΎΡ‚ Ρ‚ΠΎΠ³ΠΎ сколько Ρ€Π°Π· ΠΎΠ½Π° освобоТдала CPU) ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ Ρ‚Π°ΠΊΠΎΠΉ Π·Π°Π΄Π°Ρ‡ΠΈ пониТаСтся (ΠΎΠ½Π° двигаСтся Π²Π½ΠΈΠ· ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ).
  • Rule5: По ΠΏΡ€ΠΎΡˆΠ΅ΡΡ‚Π²ΠΈΠΈ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ ΠΏΠ΅Ρ€ΠΈΠΎΠ΄Π° S пСрСвСсти всС Π·Π°Π΄Π°Ρ‡ΠΈ Π² систСмС Π² Π½Π°ΠΈΠ²Ρ‹ΡΡˆΡƒΡŽ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ.

MLFQ интСрСсСн ΠΏΠΎ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ ΠΏΡ€ΠΈΡ‡ΠΈΠ½Π΅ β€” вмСсто Ρ‚ΠΎΠ³ΠΎ Ρ‡Ρ‚ΠΎΠ±Ρ‹ Ρ‚Ρ€Π΅Π±ΠΎΠ²Π°Ρ‚ΡŒ Π·Π½Π°Π½ΠΈΠ΅ ΠΎ
ΠΏΡ€ΠΈΡ€ΠΎΠ΄Π΅ Π·Π°Π΄Π°Ρ‡ΠΈ Π·Π°Ρ€Π°Π½Π΅Π΅, Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΈΠ·ΡƒΡ‡Π°Π΅Ρ‚ ΠΏΡ€ΠΎΡˆΠ»ΠΎΠ΅ ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ Π·Π°Π΄Π°Ρ‡ΠΈ ΠΈ выставляСт
ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚Ρ‹ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰Π΅. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΎΠ½ стараСтся ΡƒΡΠΈΠ΄Π΅Ρ‚ΡŒ сразу Π½Π° Π΄Π²ΡƒΡ… ΡΡ‚ΡƒΠ»ΡŒΡΡ… β€” Π΄ΠΎΡΡ‚ΠΈΡ‡ΡŒ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ для ΠΌΠ°Π»Π΅Π½ΡŒΠΊΠΈΡ… Π·Π°Π΄Π°Ρ‡ (SJF, STCF) ΠΈ чСстно Π·Π°ΠΏΡƒΡΠΊΠ°Ρ‚ΡŒ Π΄ΠΎΠ»Π³ΠΈΠ΅,
Π·Π°Π³Ρ€ΡƒΠΆΠ°ΡŽΡ‰ΠΈΠ΅ CPU задания. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΠΌΠ½ΠΎΠ³ΠΈΠ΅ систСмы, Π²ΠΊΠ»ΡŽΡ‡Π°Ρ BSD ΠΈ ΠΈΡ… ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄Π½Ρ‹Π΅,
Solaris, Windows, Mac ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ Π² качСствС ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Ρ‰ΠΈΠΊΠ° Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°
MLFQ Π² качСствС Π±Π°Π·ΠΎΠ²ΠΎΠΉ основы.

Π”ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Ρ‹:

  1. manpages.debian.org/stretch/manpages/sched.7.en.html
  2. en.wikipedia.org/wiki/Scheduling_(computing)
  3. pages.lip6.fr/Julia.Lawall/atc18-bouron.pdf
  4. www.usenix.org/legacy/event/bsdcon03/tech/full_papers/roberson/roberson.pdf
  5. chebykin.org/freebsd-process-scheduling

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ: habr.com