Занятие 15. Планировщик и диспетчер задач

• Задача планирования, метрики
  • Задачи известны заранее: классические NP полные задачи
  • Задачи поступают в процессе
• Многозадачность AMP и SMP
• Состояния задач (Running, Ready, Sleep (S и D), Stopped, Zombie)
• Планировщики: как выбрать следующую задачу?
  • Fifo, round-robin
  • Normal
• Классы задач в linux: stop, deadline, rt, normal, idle
• Диспетчер задач: как передать управление задаче?

Потом сесть и показать игру в планировщика

Небольшое введение

Задача выбора какой таской заниматься основывается на теории массового обслуживания. (ну типа 🤓)

Смирнов на паре разделил задачи эффективного распределения тасок на два типа: оффлайн и онлайн. Онлайн задача это то, что шедулер решает в реальной жизни — информации заранее нету, все задачи сваливаются по ходу дела

Оффлайн это два примера ниже — искуственные задачки на листочке, есть “дано”, есть “найти”. Заранее известен весь список задач и сколько каждая выполняется Надеюсь пон.

Рассмотрим два примерчика оффлайн задач:

<aside> 1️⃣

Один CPU и несколько независимых задач.

arrival time - время, когда задача попадает в очередь

completion time - время, когда задача завершила исполнение

wait time - время, до начала исполнения

burst - время исполнения

turn-around - полное время для одной задачи

Ну и нам надо эффективно распределить задачи

это можно по разному сделать:

1. Cуммарное wait time всех задач свести к минимуму,
2. Или время ожидания последней таски сделать минимальным.
3. Ну или еще как-нибудь

Для этого выполняем сначала те задачи, на которые трубется меньше времени

</aside>

<aside> 2️⃣

Два CPU и несколько независимых задач.

В таком случае нашей задачей будет минимизировать разницу времени выполнения(burst) на первом и втором cpu. т.е загрузить их максимально одинаково

</aside>

По сути аналогом второй задачи будет известная со школы загадка: Имеется набор гирь и весы с двумя чашами. Как разложить гири на двух чашах, чтобы весы были максимально близки к состоянию равновесия? Оказывается, что это NP-Complete задача. И поэтому…. Внезапно….

<aside> 🇫🇷

NP-Complete

$L$ is $NP\textrm{-}complete$ if:

1. $L$ is NP

2. $\forall L_1(L_1\in NP\Rightarrow L_1\prec L)$ (polynominal reduction)

Язык $L$ (он же задача) $NP\textrm{-}complete$, если он $NP$ и любой другой язык из $NP$ можно свести к $L$ за полиномиальное время.

</aside>

Если вдруг будете сдавать Смирнову этот билет, он точно это спросит