1.55M
Category: programmingprogramming

Планировщик задач

1.

Тема: Планировщик задач

2.

План занятия
1. Что такое планировщик процессов в ОС;
2. Типы многозадачности в ОС;
3. Проблемы планировщиков;
4. Приоритетность процессов;
5. Планировщики, используемые в Linux;
6. Особенности работы с планировщиком на примере ОС
Linux .
7. Итоги.
8. Домашнее/практическое задание.
По итогу занятия вы сможете получить представления
о работе планировщика процессов операционной
системы, а именно особенности работы и главные
аспекты его функционирования

3.

Планировщик задач
Планировщик (шедулер, англ. scheduler) — часть
операционной
системы,
ответственная
за
распределение
ресурсов
компьютера
между
рабочими
юнитами
(процессами,
потоками,
пользователями и т. д.).
В данной теме мы будем рассматривать
планировщик задач, отвечающий за ресурсы
процессора.

4.

Схема работы компьютера
процессор — сильно ограничен по памяти, но
умеет совершать операции над этими данными;
память — условно считаем, что способна
вместить достаточно данных для выполнения
текущих процессов;
шина данных — последовательно передаёт
данные между процессором и памятью.

5.

Проблемы прошлых систем
Проблема с обработкой внешних событий: событие
ввода с клавиатуры, прихода пакета из сети,
изменение изображения на мониторе и т.д

6.

Проблемы прошлых систем
1. Проблема с обработкой внешних событий:
событие ввода с клавиатуры, прихода пакета из сети,
изменение изображения на мониторе и т.д.
2. Проблемы с одновременной работой нескольких
пользователей, нескольких задач.

7.

Проблемы при работе нескольких
процессов
● «одновременности» для массового пользователя у нас
пока нет, но есть иллюзия, которую нужно поддерживать;
●нужна программа для управления программами;
●планировщик должен быть сравнительно «честным», но
не всегда, не совсеми, а даже с ними непостоянно;
Основной трудностью реализации многозадачной среды
является её надёжность, выраженная в защите памяти,
обработке сбоев и прерываний, предохранении от
зависаний и тупиковых ситуаций.
Кроме надёжности, многозадачная среда должна быть
эффективной. Затраты ресурсов на её поддержание не
должны: мешать процессам проходить, замедлять их
работу, резко ограничивать память

8.

Проблемы при работе нескольких
процессов
● невозможно узнать, когда завершится программа;
Например, в рамках Машины Тьюринга невозможно определить,
когда закончится программа (дойдёт до какого-то момента).
● программа может зависнут, а процессор не знает о
времени;
● использование аппаратных прерываний.
На программном уровне невозможно понять, что прошло
какое-то время. Остаётся использовать аппаратные
прерывания.

9.

Проблемы мультипроцессинга
Примеры, если не используется программно-аппаратная проверка
(система договорённостей):
●Если пользователь забыл сохранить IP перед переключением или
код программы, то планировщик использует данные, которые
окажутся некорректными, управление перейдёт непонятно по
какому адресу.
● Если программа обращается к системному стеку глубже, чем
нужно — другая программа потеряет данные.
Любой отход от договорённостей или ошибка реализации
приводят к отказу всей системы.
● Планировщик сохраняет регистры в системной очереди;
● Планировщик берёт следующую программу из списка
зарегистрированных, восстанавливает её регистры, long jump к
сохранённому адресу исполнения

10.

Типы многозадачности

11.

Многозада́чность
Многозада́чность (англ. multitasking) — свойство
операционной
системы
или
среды
выполнения
обеспечивать
возможность
параллельной
(или
псевдопараллельной)
обработки
нескольких
задач.
Истинная многозадачность операционной системы возможна
только в распределённых вычислительных системах.
Другими словами, многозадачностью можно назвать способ
исполнения нескольких задач в один промежуток времени. При
этом задачи распределяют между собой общие ресурсы
(resources sharing), а также выполняют планирование
(scheduling) задачи в очереди исполнения.
первоисточник

12.

Многозада́чность
Все современные многозадачные ОС, по своей сути,
делают тоже самое, что и однозадачные, они точно
также прерывают одну задачу, чтобы запустить
вторую, а потом третью и так далее, но это
переключение происходит настолько быстро, что
создается
иллюзия,
будто
всё
происходит
одновременно.
Но
чем
тогда
отличаются
многозадачные и однозадачные ОС?
А тем, что многозадачные системы способны прервать
выполняемую задачу практически в любой момент и передать
управление ожидающей задаче.
первоисточник

13.

Процессная многозадачность.
Здесь программа — наименьший элемент управляемого кода,
которым может управлять планировщик операционной
системы. Известна большинству пользователей (одновременная
работа в текстовом редакторе и прослушивание музыки).
Многозадачная система позволяет двум или более программам
выполняться одновременно.
Процесс — это понятие, относящееся к операционной системе.
Каждый раз при запуске приложения создается и запускается
новый процесс.
С каждым процессом связаны следующие ресурсы, как:
• виртуальное адресное пространство;
• исполнимый код и данные;
• базовый приоритет;
• описатели объектов;
• переменные окружения.
первоисточник

14.

Поточная многозадачность.
Многопоточность — специализированная форма многозадачности.
Наименьший элемент управляемого кода — поток. Многопотоковая (multithreaded) система предоставляет возможность одновременного выполнения
одной программой 2 и более задач (потоков). Поток (thread) — это
основной элемент системы, которому ОС выделяет машинное время.
Поток может выполнять какую-то часть общего кода процесса, в том числе
и ту часть, которая в это время уже выполняется другим потоком.
Потоки и процессы:
• Поток определяет последовательность исполнения кода в процессе.
• Процесс ничего не исполняет, он просто служит контейнером
потоков.
• Потоки всегда создаются в контексте какого-либо процесса, и вся их
жизнь проходит только в его границах.
• Потоки могут исполнять один и тот же код и манипулировать одними и
теми же данными, а также совместно использовать описатели объектов
ядра, поскольку таблица описателей создается не в отдельных потоках, а
в процессах.
• Т.к. потоки расходуют существенно меньше ресурсов, чем процессы,
следует решать свои задачи за счет использования дополнительных
потоков и избегать создания новых процессов.
первоисточник

15.

Многозада́чность
Какую задачу вытеснить и какой отдать преимущество
определяет планировщик операционной системы (по
таймеру). На самом деле современные ОС — не просто
многозадачные, они многопоточные. В чём разница?
В многозадачных ОС, минимальная единица, которой
может управлять планировщик — это программа. Одна
программа = один процесс, и всё что мы можем делать —
это переключаться между процессами.
А в многопоточных ОС, каждая программа может иметь
несколько потоков, то есть подзадач. Поэтому
планировщик может переключаться между потоками, что
позволяет уменьшить задержки, и куда рациональнее
распределять ресурсы.
первоисточник

16.

Свойства многозадачной среды
Примитивные многозадачные среды обеспечивают чистое «разделение ресурсов», когда за каждой
задачей закрепляется определённый участок памяти, и задача активизируется в строго
определённые интервалы времени.
Более развитые многозадачные системы проводят распределение ресурсов динамически, когда
задача стартует в памяти или покидает память в зависимости от её приоритета и от стратегии
системы. Такая многозадачная среда обладает следующими особенностями:
• Каждая задача имеет свой приоритет, в соответствии с которым получает процессорное время
и память
• Система организует очереди задач так, чтобы все задачи получили ресурсы, в зависимости от
приоритетов и стратегии системы
• Система организует обработку прерываний, по которым задачи могут активироваться,
деактивироваться и удаляться
• По окончании положенного кванта времени ядро временно переводит задачу из состояния
выполнения в состояние готовности, отдавая ресурсы другим задачам. При нехватке памяти
страницы невыполняющихся задач могут быть вытеснены на диск (своппинг), а потом, через
определённое системой время, восстанавливаться в памяти
• Система обеспечивает защиту адресного пространства задачи от несанкционированного
вмешательства других задач
• Система обеспечивает защиту адресного пространства своего ядра от несанкционированного
вмешательства задач
• Система распознаёт сбои и зависания отдельных задач и прекращает их
• Система решает конфликты доступа к ресурсам и устройствам, не допуская тупиковых
ситуаций общего зависания от ожидания заблокированных ресурсов
• Система гарантирует каждой задаче, что рано или поздно она будет активирована
• Система обрабатывает запросы реального времени
• Система обеспечивает коммуникацию между процессами[Источник 1]
первоисточник

17.

2 основных подхода многозадачности
● Кооперативная многозадачность;
Процессы сами по доброй воле (вызовом
специальной команды) отдают управление.
● Вытесняющая многозадачность.
Планировщик (по таймеру) останавливает текущий
процесс и передаёт управление другому.

18.

Многозада́чность
• Preemptive multitasking (режим реального времени)
— преимущественная, или вытесняющая,
многозадачность.
Особенности:
прогнозируемая отзывчивость;
Ближе к реальности, т.к. переключение завязано на
реальном таймере.
● независимость процессов;
Если процесс завис, то остальные от этого меньше
зависят.
● схожая скорость число-дробилок;
В CPU-bound скорость не проседает.
● дороже.
Излишние смены контекстов (context-switch).
первоисточник

19.

По способу организации времени
выполнения каждого процесса
Параллельная многозадачность
Идеальным
случаем
многозадачности
является
параллельная
многозадачность, когда каждая задача исполняется в своём аппаратном
микропроцессорном ядре действительно одновременно друг с другом.
Истинная многозадачность операционной системы возможна только в
распределенных вычислительных системах. Реализация данного типа
многозадачности требует больших материальных вложений (требуется
отдельное аппаратное средство для каждой задачи), поэтому обычно её
применение не является целесообразным. Ниже представлен пример
системы , в которой реализована параллельная многозадачность.
Микроконтроллер Propeller от Parallax обеспечивает работу сразу 8
задач. Восемь встроенных процессоров-ядер, могут выполнять как
совместные, так и независимые задачи, получая доступ к разделяемым
ресурсам посредством центрального переключающего устройства.
Разработчик полностью контроллирует, как и когда загружать каждое из
ядер; ни компилятор, ни какая-либо операционная система не распределяет
задачи между несколькими ядрами. Общий источник тактовой частоты
обеспечивает всем процессорам единую временную базу и
синхронизацию.
Контроллер
имеет
два
возможных
языка
программирования: легкий для освоения высокоуровневый язык Spin, а так
же низкоуровневый Propeller Ассемблер
первоисточник

20.

По способу организации времени
выполнения каждого процесса
Альтернативой параллельной многозадачности
является применение псевдопараллельной
многозадачности или совокупности параллельной и
псевдопараллельной многозадачности при наличии
нескольких процессорных ядер.
первоисточник

21.

Кооперативная многозадачность это:
● простота;
Планировщик проще: просто список.
● скорость;
Нет необходимости зря прерывать процесс (в
моменте исполнения).
● низкая отзывчивость;
Потенциально получаем перерасход времени частью
процессов.
● зависания;
Если в одном из процессов ошибка/блокировка —
висят все процессы.
первоисточник

22.

Многозада́чность
Именно такое свойство быстро переключаться между потоками позволяет
вам одновременно использовать много приложений и мгновенно
переключаться между ними.
первоисточник

23.

Многозада́чность
Многопоточность в Google Chrome
Хороший пример программы, которая по максимуму использует
возможности многозадачности и многопоточности — это родной
прожорливый браузер Google Chrome. Каждая вкладка в Chrome — это
отдельный процесс, с несколькими потоками. Это хорошо заметно если
открыть диспетчер задач: кучка маленьких Chrome занимают ваш
процессор пока вкладки открыты (нажмите в браузере shift+esc)
первоисточник

24.

Многозадачные ОС
Какая операционная система самая многозадачная? Самая эффективная,
самая распределенно-параллельно вычисляющая?
Все популярные ОС — это всё многозадачные, многопоточные,
многопроцессорные, вытесняющие операционные системы. К таким
системам относится и Windows, и UNIX, и Linux. Ну и соответственно туда
же входят MacOS и iOS, которые основаны на UNIX. Android, который
основан на Linux.
Но почему тогда многозадачность в смартфонах и планшетах считается
неполноценной?
первоисточник

25.

Многозадачность на смартфонах
Несмотря на то, что iOS и Android на уровне ядра позволяют реализовать
полноценную многозадачность, такую же как на взрослых операционных,
Google и Apple блокируют эту возможность. Почему?
На самом деле очень простой причине: многозадачность очень
ресурсоемкая вещь, которая сильно нагружает процессор и потребляет
аккумулятор, что посадило бы аккумулятор за пару часов активного
пользования. В мобильных ОС используют чуть другой подход к
многозадачности.
И работает это так — каждое приложение может находиться в 4-х
состояниях:
• Нерабочее
• Активное
• Фоновое
• Приостановленное
первоисточник

26.

Диспетчеризация
Эффективность многозадачной системы во многом зависит от способа
диспетчеризации задач на исполнение.
Состояние задачи
Для понимания диспетчеризации важным является понятие состояния
задачи.
Основные состояния задач такие:
выполняется;
готова к исполнению;
заблокирована.
первоисточник

27.

Диспетчеризация
Задача находится в состоянии исполнения тогда, когда под неё выделен
ресурс процессора и передано управление.
Очевидно, что в системе не может быть выполняющихся задач больше,
чем физических процессоров.
Поэтому существует второе состояние — готовность к исполнению.
Задача в это состояние тогда, когда она может исполняться, то есть не
существует причин, вызывающих блокировку, но вычислительные
ресурсы отданы под другие задачи.
В третье состояние задача попадает при невозможности её исполнения в
данный момент времени.
ожидание какого либо события ;
незавершённая инициализация (когда ещё не созданы другой задачей или
системой начальные условия для запуска);
«заморозка» (явная остановка исполнения, обычно в отладочных целях);
завершение (состояние , когда исполнение уже закончено, но ресурсы ещё
не освобождены);
первоисточник

28.

Диспетчеризация
Стратегии диспетчеризации
Известно несколько основных стратегий диспетчеризации:
круговая (round-robin).Управление между задачами производится в в
каком-либо фиксированном порядке через определённые промежутки
времени;
случайная (random).Через каждый определённый промежуток времени
управление передаётся на произвольную задачу;
приоритетная (priority-driven).Каждая задача имеет уровень приоритета и
управление получает незаблокированная задача имеющая наибольший
уровень;
управляемая дедлайнами
производится в порядке,
определённый срок
первоисточник
(deadline-driven). Передача управления
обеспечивающем выполнение задач в

29.

Приоритетность процессов

30.

Приоритетность
Приоритетность процессов
Некоторые процессы могут выполняться без проблем в фоне, какимто нужно выделить больше времени. Для управления приоритетами в
Unix-like системах используется nice:
Приоритеты расставляются от значений
● от -20 до 19;
● чем меньше, тем приоритетнее;
● может отличаться от реального приоритета задачи.

31.

Использование команды nice
nice -n {приоритет} {программа} {аргументы};
● sudo nice –n команда— если приоритет меньше 0;
● renice -n {приоритет} PID — для уже запущенного процесса;
● renice -n -g -u —
Для запущенной группы
процессов, для пользователя.
● ps ax -o pid,ni,cmd —
чтобы посмотреть
nice запущенных
процессов.

32.

Планировщики Linux

33.

Планировщики Linux
За время жизни ОС GNU/Linux у неё были различные реализации
планировщика:
● O(n) — первый, самый простой линейный планировщик;
● O(1) — с версии 2.6, работающий быстрее при большем объёме
задач;
● CFS — текущий (c 2.6.23). Также ускоренный, с дополнительными
возможностями.
● SCHED_DEADLINE — альтернативный (с 3.14) планировщик
реального времени.

34.

Планировщик O(n)
- чем больше задач, тем линейно больше времени требуется на
планирование
● проблемы работы с несколькими процессами;
● при выборе следующей задачи из списка задач в поисках самой
недоработавшей: выбирается, исполняется, и изменяется в дескрипторе
время ее исполнения;
● доступ к списку задач блокировался 1-м lock-ом
планировщик O(1)
● хранит процессы в отсортированном списке;
● присутствует еще один список для процессов, отработавших ресурс
времени;
● если первый список закончился, то списки меняются местами;
● на каждый процессор по своей паре этих списков
● появилась проблема миграции процесса с одного процессора на
другой.

35.

планировщик CFS
● хранит не процессы, а sched_entity — планировщик может рассчитывать
время, например, для пользователей;
● все sched_entity лежат в бинарном сбалансированном дереве,
отсортированном по оставшемуся времени исполнения и имеет
сложность O(logN);
● CFS планировщик более справедлив — при равном приоритете
задачи будут получать более равные кванты, чем в O(1);
● Работает сразу на все процессоры — нет проблемы с локальными
spinlock-ами.

36.

планировщик SCHED_DEADLINE
● используется для систем реального времени;
● основная задача — выполнить задачу за фиксированное реальное время
(не позже);
● использует алгоритм планирования по ближайшему сроку
завершения:
- планировщик ведёт список процессов, отсортированный по
сроку завершения (deadline);
- в работу берётся готовый процесс, имеющий самый близкий
deadline;
- при появлении нового процесса — пересортировка.

37.

Итоги
● рассмотрели основные подходы и проблемы реализации
многозадачных систем;
● рассмотрели типы многозадачности
● узнали что такое многопоточность и процессы
● получили представление об утилитах работы с
планировщиком GNU/Linux;
● узнали особенности реализаций планировщиков Linux.
Материалы к закреплению:
Принцип работы планировщика задач в Linux
English     Русский Rules