Планирование заданий, процессов и потоков ,Алгоритмы планирования , Взаимодействие и синхронизация

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

планирование заданий , процессов и потоков

1.Виды планирования

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

Схема планирования с учетом очередей заданий (процессов)

Типичный граф состояния потока

алгоритмы планирования потоков

• планирование распределяется между ОС и прикладными программами;
• необходимость частых передач управлений ОС, в противном случае возможна монополизация процессора приложением;
• зависания приложений могут привести к краху системы

2. Вытесняющие (preemptive)

• функции планирования сосредоточены в ОС;
• планирование на основе квантования процессорного времени;
• планирование на основе приоритетов потоков: статических, динамических, абсолютных, относительных, смешанных;

Простейший алгоритм планирования, реализующий состояния потока по кадру 27

Алгоритм планирования, реализующий предпочтения потокам с интенсивным вводом-выводом

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

Граф состояния потока

Алгоритмы приоритетного планирования

Приоритетное переключение с квантованием

Изменение базового приоритета потока

Увеличение приоритета

• + 1 – завершение ввода-вывода по диску;
• + 2 – для последовательной линии;
• + 6 – клавиатура;
• + 8 – звуковая карта;
• + 2 – снимается блокировка по семафору (для потока переднего плана);
• + 1 - снимается блокировка по семафору (для потока непереднего плана);

приоритет 15 на 2 кванта процессора, если готовый к выполнению поток простаивает более некоторого директивного времени.

Уменьшение приоритета

• - 1 – если полностью использован квант времени процессора (многократно, вплоть до базового приоритета).

взаимодействие и синхронизация процессов и потоков
.1. Проблемы взаимодействия и синхронизации

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

2. Об этом говорит сайт https://intellect.icu . Конкуренция процессов в борьбе за ресурсы

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

Необходимость взаимоисключений:

• 1.Процессы не должны одновременно находиться в критических областях.
• 2.В программе не должно быть предположений о скорости или количестве процессов.
• 3.Процесс, находящийся вне критической области, не может блокировать другие процессы.
• 4.Невозможна ситуация, в которой процесс вечно ждет попадания в критическую область.

Взаимоблокировки ( тупики , deadlock)

Группа процессов находится в тупиковой ситуации, если каждый процесс из группы ожидает события, которое может вызвать только другой процесс из этой же группы

Проблема “голодание”

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

3. Сотрудничество с использованием разделения

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

Проблемы: взаимоисключение, взаимоблокировка, голодание. Дополнительно: синхронизация процессов для обеспечения согласованности данных

Пример: пусть должно выполняться a = b при начальном значении a = b = 1

1-й вариант: процессы выполняются последовательно

P1: a = a + 1; b = b + 1; P2: b = 2 * b; a = 2 * a;

2-й вариант: процессы прерывают друг друга

P1: a = a + 1; прерывание; P2: b = 2 * b; прерывание;

P1: b = b + 1; прерывание; P2: a = 2 * a;

Согласование нарушено: a = 4, b = 3

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

4. Методы взаимоисключений

2. Блокирующие переменные (программный подход)

3.Использование системных функций входа в критическую секцию

4. семафоры Дийкстры (Dijkstra)

Семафор: переменная S, примитивы P (proberen – проверка; down) и V (verhogen – увеличение, up)

V(S) – переменная S увеличивается на 1 единым действием. Выборка, наращивание и запоминание не могут быть прерваны. К переменной S нет доступа во время выполнения этой операции.

P(S) – переменная S уменьшается на 1, если это возможно, составясь в области неотрицательных значений. Если S уменьшить невозможно, поток, выполняющий операцию P, ждет, пока это уменьшение станет возможным. Операция P неделима.

В частном случае семафор S может принимать двоичные значения 0 и 1, превращаясь в блокирующую переменную (двоичный семафор).

Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания (если S = 0).

Операция V может при некоторых обстоятельствах активизировать процесс, приостановленный операцией P.

Для хранения процессов, ожидающих семафоры, используется очередь, работающая по принципу FIFO.

5. Взаимоблокировки (тупики)

Условия возникновения взаимоблокировки (тупиковой) ситуации:

2. В системе несколько ресурсов каждого типа.

Алгоритм обнаружения тупиков

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

Алгоритм

A, т. е. Ri <= Aj или ri j <= Aj , j = 1, m.

строка матрицы С к вектору A, т.е. Aj := Aj + сi j , j = 1, m.

Возврат к шагу 1.

3. Если таких процессов не существует, работа алгоритма заканчивается. Если есть немаркированные процессы, то они попали в тупик.

Методы устранения тупиков

Недопущение тупиков путем безопасного распределения ресурсов. Подобные алгоритмы базируются на концепции безопасных состояний. Например, Дейкстрой был разработан алгоритм планирования, позволяющий избегать взаимоблокировок (алгоритм банкира).

.6. Синхронизирующие объекты ОС

Для синхронизации потоков, принадлежащих разным процессам, ОС должна предоставлять потокам системные объекты синхронизации.

К таким объектам относятся события (event), мьютексы (mutex – mutual exclusion – взаимное исключение), системные семафоры и др.

Объект-событие используется для того, чтобы оповестить потоки о том, что некоторые действия завершены.

Мьютекс (простейший двоичный семафор) используется для управления доступом к данным.

Семафоры используются для оповещения свершения последовательности событий.

Для синхронизации используются также “обычные ” объекты ОС: файлы, процессы, потоки

Все объекты синхронизации могут находиться в сигнальном и несигнальном (свободном) состоянии. Поток с помощью системного вызова WAIT(X) может синхронизировать свое выполнение с объектом синхронизации X. С помощью системного вызова SET(X) поток может перевести объект X в сигнальное состояние. Кроме того, в ОС определен набор сигналов для логической связи меду процессами, а также процессами и пользователями (терминалами).

.7 Аппаратно-программные средства поддержки мультипрограммирования

7.1 . Системы прерываний

Классы прерываний: внешние, внутренние, программные

.1 Внешние прерывания – результат действий пользователя, сигналы от периферийных устройств компьютера и управляемых объектов.

2. Внутренние прерывания – результат появления аварийных ситуаций при выполнении инструкции программы.

3. Програпрограмме ммные прерывания – результат выполнения запланированных в особых инструкций (системный вызов).

Принципы построения систем прерываний:

• аппаратная поддержка (контроллер прерываний, контроллер DMA, контроллеры внешних устройств, шины подключения внешних устройств, средства микропроцессора);
• векторный, опрашиваемый и комбинированный способы прерываний;
• приоритетный механизм обслуживания (с абсолютными и относительными приоритетами);
• маскирование прерываний;
• диспетчер прерываний и процедуры обслуживания прерываний.

Последовательность действий при обработке прерываний

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

2.Сохраняется некоторая часть контекста прерванного потока, которая позволит возобновить его исполнение после обработки прерывания (обычно слово состояния процессора – регистр EFLAGS в Pentium, регистры общего назначения). Может быть сохранен и полный контекст, если ОС обслуживает прерывание со сменой процесса.

3.В счетчик команд загружается адрес процедуры обработки прерывания и устанавливается новое PSW, которое определяет привилегированный режим работы процессора при обработке прерывания.

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

5.После обработки прерывания ядром операционной системы, прерванный контекст восстанавливается (частично аппаратно – PSW, содержимое счетчика команд, частично программно – извлечение данных из стека), снимается обработка прерываний данного типа и работа потока возобновляется с прерванного места.

.7.2. Системные вызовы

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

Реализация системных вызовов должна удовлетворять следующим требованиям:

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

Рис Централизованная схема обработки системных вызовов

Вау!! 😲 Ты еще не читал? Это зря!

• Процессы
• Потоки
• Нити
• мьютекс
• семафор
• трансакция

• организация синхронизации данных , клиент-сервер для мобильного приложения ,

• единая служба синхронизации ,
• теория синхронизации , синхронизация данных ,
• синхронизация и электропитание , синхронная передача сигнала ,
• синхронизация в system r ,
• синхронизация файлов ,

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