Процессы. Процессы и потоки. Процессы и потоки

• Название: Процессы и потоки
• Анкор: Процессы
• Дата: 09.03.2023
• Размер: 0.73 Mb.
• Имя файла: Процессы и потоки.ppt
• Тип: Программа; #975992
• страница: 8 из 8

Мониторы

В 1974 году Хоар (Ноаге) и Бринч Хансен (Brinch Hansen) предложили примитив синхронизации более высокого уровня, называемый монитором.
Монитор - набор процедур, переменных и других структур данных, объединенных в особый модуль или пакет. Процессы могут вызывать процедуры монитора, но у процедур, объявленных вне монитора, нет прямого доступа к внутренним структурам данных монитора.

Передача сообщений

Этот метод межпроцессного взаимодействия использует два примитива: send и receive, которые скорее являются системными вызовами, чем структурными компонентами языка.
Например:
send(destination, Smessage);
receive(source, &message);
Первый запрос посылает сообщение заданному адресату, а второй получает сообщение от указанного источника. Если сообщения нет, второй запрос блокируется до поступления сообщения либо немедленно возвращает код ошибки.

Барьеры

Последний из рассмотренных нами механизмов синхронизации предназначался скорее для групп процессов, нежели для ситуаций с двумя процессами. Некоторые приложения делятся на фазы, и существует правило, что процесс не может перейти в следующую фазу, пока к этому не готовы все остальные процессы. Этого можно добиться, разместив в конце каждой фазы барьер.

Планирование

Поведение процесса

Практически все процессы чередуют периоды вычислений с операциями ввода-вывода. Обычно процессор некоторое время работает без остановки, затем происходит системный вызов на чтение из файла или запись в файл. После выполнения системного вызова процессор опять считает, пока ему не понадобятся новые данные или не потребуется записать полученные данные и т. д.

Когда планировать ?

Ключевым вопросом планирования является выбор момента принятия решений. Оказывается, существует множество ситуаций, в которых необходимо планирование.
Во-первых, когда создается новый процесс, необходимо решить, какой процесс запустить: родительский или дочерний.
Во-вторых, планирование необходимо, когда процесс завершает работу.
В-третьих, когда процесс блокируется на операции ввода-вывода, семафоре, или по какой-либо другой причине, необходимо выбрать и запустить другой процесс.
В-четвертых, необходимость планирования может возникнуть при появлении прерывания ввода-вывода. Если прерывание пришло от устройства ввода-вывода, закончившего работу, можно запустить процесс, который был блокирован в ожидании этого события.

Когда планировать ? (2)

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





В различных средах требуются различные алгоритмы планирования. Это связано с тем, что различные операционные системы и различные приложения ориентированы на разные задачи. Другими словами, то, для чего следует оптимизировать планировщик, различно в разных системах.
Можно выделить три среды:
Системы пакетной обработки данных.
Интерактивные системы.
Системы реального времени.





В системах пакетной обработки нет пользователей, сидящих за терминалами и ожидающих ответа. В таких системах приемлемы алгоритмы без переключений или с переключениями, но с большим временем, отводимым каждому процессу. Такой метод уменьшает количество переключений между процессами и улучшает эффективность.





В интерактивных системах необходимы алгоритмы планирования с переключениями, чтобы предотвратить захват процессора одним процессом. Даже если ни один процесс не захватывает процессор на неопределенно долгий срок намеренно, из-за ошибки в программе один процесс может заблокировать остальные. Для исключения подобных ситуаций используется планирование с переключениями.





В системах с ограничениями реального времени приоритетность, как это ни странно, не всегда обязательна, поскольку процессы знают, что их время ограничено, и быстро выполняют работу, а затем блокируются. Отличие от интерактивных систем в том, что в системах реального времени работают только программы, предназначенные для содействия конкретным приложениям. Интерактивные системы являются универсальными системами.

Задачи алгоритмов планирования

Все системы
Равнодоступность — предоставление каждому процессу справедливой доли времени центрального процессора.
Принуждение к определенной политике — наблюдение за выполнением установленной политики.
Баланс — поддержка загруженности всех составных частей системы.
Пакетные системы
Производительность — выполнение максимального количества заданий в час.
Оборотное время — минимизация времени между представлением задачи и ее завершением.
Использование центрального процессора — поддержка постоянной загруженности процессора.
Интерактивные системы
Время отклика — быстрый ответ на запросы.
Пропорциональность — оправдание пользовательских надежд.
Системы реального времени
Соблюдение предельных сроков — предотвращение потери данных.
Предсказуемость — предотвращение ухудшения качества в мультимедийных системах.

Планирование в системах пакетной обработки заданий

«Первым пришел – первым ушел»

«Первым пришел – первым ушел»

Алгоритм без переключений «первым пришел - первым обслужен» является, пожалуй, самым простым из алгоритмов планирования. Процессам предоставляется доступ к процессору в том порядке, в котором они его запрашивают. Чаще всего формируется единая очередь ждущих процессов. Как только появляется первая задача, она немедленно запускается и работает столько, сколько необходимо.
Остальные задачи ставятся в конец очереди. Когда текущий процесс блокируется, запускается следующий в очереди, а когда блокировка снимается, процесс попадает в конец очереди. Основным преимуществом этого алгоритма является то, что его легко понять и столь же легко программировать. Он справедлив в том же самом смысле, в каком справедливо распределение дефицитных билетов на концерт или соревнования среди всех желающих стоять в очереди с двух часов ночи. В этом алгоритме все процессы в состоянии готовности контролируются одним связным списком. Чтобы выбрать процесс для запуска, нужно всего лишь взять первый элемент списка и удалить его. Появление нового процесса приводит к помещению его в конец списка - что может быть проще?

«Кратчайшая задача - первая»

Рассмотрим еще один алгоритм без переключений для систем пакетной обработки, предполагающий, что временные отрезки работы известны заранее.
Например, работники страховой компании могут довольно точно предсказать, сколько времени займет обработка Пакета из 1000 исков, поскольку они делают это каждый день. Если в очереди есть несколько одинаково важных задач, планировщик выбирает первой самую короткую задачу.
Есть четыре задачи: А, В, С и D, со временем выполнения 8, 4, 4 и 4 мин соответственно.

Наименьшее оставшееся время выполнения

Версией предыдущего алгоритма с переключениями является алгоритм наименьшего оставшегося времени выполнения.
В соответствии с этим алгоритмом планировщик каждый раз выбирает процесс с наименьшим оставшимся временем выполнения.
В этом случае также необходимо заранее знать время выполнения задач.
Когда поступает новая задача, ее полное время выполнения сравнивается с оставшимся временем выполнения текущей задачи.
Если время выполнения новой задачи меньше, текущий процесс приостанавливается и управление передается новой задаче.
Эта схема позволяет быстро обслуживать короткие запросы.

Трехуровневое планирование

Системы пакетной обработки позволяют реализовать трехуровневое планирование. По мере поступления в систему новые задачи сначала помещаются в очередь, хранящуюся на диске.
Впускной планировщик выбирает задание и передает его системе. Остальные задания остаются в очереди. Характерный алгоритм входного контроля может заключаться в выборе смеси из процессов, ограниченных возможностями процессора, и процессов, ограниченных возможностями устройств ввода-вывода.
Также возможен алгоритм, в котором устанавливается приоритет коротких задач перед длинными.
Впускной планировщик волен придержать некоторые задания во входной очереди, а пропустить задание, поступившее позже остальных.

Трехуровневое планирование (2)

Планирование в интерактивных системах

Циклическое планирование
Приоритетное планирование
Несколько очередей
«Самый короткий процесс – следующий»
Гарантированное планирование
Лотерейное планирование
Справедливое планирование

Циклическое планирование

Одним из наиболее старых, простых, справедливых и часто используемых является алгоритм циклического планирования. Каждому процессу предоставляется некоторый интервал времени процессора, так называемый квант времени.
Если к концу кванта времени процесс все еще работает, он прерывается, а управление передается другому процессу. Разумеется, если процесс блокируется или прекращает работу раньше, переход управления происходит в этот момент. Реализация циклического планирования проста. Планировщику нужно всего лишь поддерживать список процессов в состоянии готовности. Когда процесс исчерпал свой лимит времени, он отправляется в конец списка.

Приоритетное планирование

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

Приоритетное планирование (2)

Несколько очередей

Один из первых приоритетных планировщиков был реализован в системе CTSS (compatible time-shared system - совместимая система с разделением времени).
В результате было разработано решение с классами приоритетов. Процессам класса с высшим приоритетом выделялся один квант, процессам следующего класса - два кванта, следующего - четыре кванта и т. д. Когда процесс использовал все отведенное ему время, он перемещался на класс ниже. В качестве примера рассмотрим процесс, которому необходимо производить вычисления в течение 100 квантов. Вначале ему будет предоставлен один квант, затем он будет перекачан на диск. В следующий раз ему достанется 2 кванта, затем 4, 8,16, 32, 64, хотя из 64 он использует только 37.





Поскольку алгоритм «Кратчайшая задача – первая» минимизирует среднее оборотное время в системах пакетной обработки, хотелось бы использовать его и в интерактивных системах. Интерактивные процессы чаще всего следуют схеме «ожидание команды, исполнение команды, ожидание команды, исполнение команды...» Если рассматривать выполнение каждой команды как отдельную задачу, можно минимизировать общее среднее время отклика, запуская первой самую короткую задачу.
Один из методов основывается на оценке длины процесса, базирующейся на предыдущем поведении процесса. При этом запускается процесс, у которого оцененное время самое маленькое. Допустим, что предполагаемое время исполнения команды равно Т0 и предполагаемое время следующего запуска равно Т1. Можно улучшить оценку времени, взяв взвешенную сумму этих времен аТ0 + (1 - а)Т1.
Метод оценки следующего значения серии через взвешенное среднее предыдущего значения и предыдущей оценки часто называют старением.

Гарантированное планирование

Принципиально другим подходом к планированию является предоставление пользователям реальных обещаний и затем их выполнение. Вот одно обещание, которое легко произнести и легко выполнить: если вместе с вами процессором пользуются п пользователей, вам будет предоставлено 1/n мощности процессора.
В системе с одним пользователем и n запущенными процессорами каждому достанется 1/n циклов процессора. Чтобы выполнить это обещание, система должна отслеживать распределение процессора между процессами с момента создания каждого процесса. Затем система рассчитывает количество ресурсов процессора, на которое процесс имеет право, например время с момента создания, деленное на n. Теперь можно сосчитать отношение времени, предоставленного процессу, к времени, на которое он имеет право. Полученное значение 0.5 означает, что процессу выделили только половину положенного, а 2.0 означает, что процессу досталось в два раза больше, чем положено. Затем запускается процесс, у которого это отношение наименьшее, пока оно не станет больше, чем у его ближайшего соседа.

Лотерейное планирование

Хотя идея обещаний пользователям и их выполнения хороша, но ее трудно реализовать. Для более простой реализации предсказуемых результатов используется другой алгоритм, называемый лотерейным планированием.
В основе алгоритма лежит раздача процессам лотерейных билетов на доступ к различным ресурсам, в том числе и к процессору. Когда планировщику необходимо принять решение, выбирается случайным образом лотерейный билет, и его обладатель получает доступ к ресурсу. Что касается доступа к процессору, «лотерея» может происходить 50 раз в секунду, и победитель получает 20 мс времени процессора.

Справедливое планирование

До сих пор мы предполагали, что каждый процесс управляется независимо от того, кто его хозяин. Поэтому если пользователь 1 создаст 9 процессов, а пользователь 2 - 1 процесс, то с использованием циклического планирования или в случае равных приоритетов пользователю 1 достанется 90 % процессора, а пользователю 2 всего 10.
Чтобы избежать подобных ситуаций, некоторые системы обращают внимание на хозяина процесса перед планированием. В такой модели каждому пользователю достается некоторая доля процессора, и планировщик выбирает процесс в соответствии с этим фактом. Если в нашем примере каждому из пользователей было обещано по 50 % процессора, то им достанется по 50 % процессора, независимо от количества процессов.
В качестве примера рассмотрим систему и двух пользователей, каждому из которых отведено по 50 % процессора. У первого пользователя четыре процесса: А, В, С и D, у второго один процесс Е. Если используется циклическое планирование, цепочка процессов, удовлетворяющая всем требованиям, будет выглядеть следующим образом:
A E B E C E D E A E B E C E D E ...





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

Планирование в системах реального времени (2)

Внешние события, на которые система должна реагировать, можно разделить на:
периодические (возникающие через регулярные интервалы времени);
непериодические (возникающие непредсказуемо).
Возможно наличие нескольких периодических потоков событий, которые система должна обрабатывать. В зависимости от времени, затрачиваемого на обработку каждого из событий, может оказаться, что система не в состоянии своевременно обработать все события.
Если в систему поступает m периодических событий, событие с номером i поступает с периодом Рi и на его обработку уходит Сi, секунд работы процессора, все потоки могут быть своевременно обработаны только при выполнении условия


Системы реального времени, удовлетворяющие этому условию, называются планируемыми.

Проблема обедающих философов