Слайд 3
Функции ОС по управлению процессами и потоками:
Слайд 4
Процесс - программа, находящаяся в стадии выполнения.
Потоки
возникли как средство распараллеливания вычислений в рамках одного процесса.
Процесс
рассматривается как заявка на потребление всех видов ресурсов, кроме одного – процессорного времени.
Процессорное время выделяется потокам.
В простейшем случае процесс состоит из одного потока.
Слайд 6
Преимущества использования потоков:
Слайд 9
1. Поток выбран на выполнение
2. Поток ожидает завершения
ввода/вывода
3. Ввод/вывод завершен (событие произошло)
4. Поток вытеснен планировщиком
Граф состояний
потока
Слайд 12
Идентификаторы, дескрипторы и контекст
Дескриптор процесса содержит такую информацию
о процессе, которая необходима ядру в течение всего жизненного
цикла процесса независимо от того, находится он в активном или пассивном состоянии. В дескрипторе прямо или косвенно содержится информация о состоянии процесса, о расположении образа процесса в оперативной памяти и на диске, о значении отдельных составляющих приоритета, глобальном приоритете, об идентификаторе пользователя, создавшего процесс, о родственных процессах и некоторая др. информация.
Контекст процесса содержит менее оперативную, но более объемную часть информации о процессе, необходимую для возобновления выполнения процесса с прерванного места: содержимое регистров процессора, коды ошибок выполняемых процессором системных вызовов, таблица открытых файлов, информация о незавершенных операциях ввода/вывода и др.
Слайд 15
Планирование и диспетчеризация потоков
Слайд 17
Диспетчеризация
это реализация найденного в
результате планирования решения, т.е.:
Слайд 18
Моменты перепланировки
Время, отведенное активной задаче на выполнение, закончилось.
Планировщик переводит задачу в состояние готовности и выполняет перепланирование.
Активная
задача выполнила системный вызов, связанный с запросом на ввод/вывод или на доступ к ресурсу, который в настоящий момент занят. Планировщик переводит задачу в состояние ожидания и выполняет перепланирование.
Активная задача выполнила системный вызов, связанный с освобождением ресурса. Если есть задача, ожидающая это событие, то она переводится из состояния ожидания в состояние готовность.
Завершение периферийным устройством операции ввода/вывода переводит соответствующую задачу в очередь готовых и выполняется планирование.
Внутреннее прерывание сигнализирует об ошибке, которая произошла в результате выполнения активной задачи. Планировщик снимает задачу и выполняет перепланирование.
Слайд 19
Лекция № 5
Планирование процессов
Слайд 21
Алгоритмы планирования, основанные на квантовании
Слайд 22
Алгоритмы планирования, основанные на приоритетах
Слайд 24
Смешанный алгоритм планирования
Слайд 25
Схема назначения приоритета потокам в Windows NT
Уровни приоритета
потоков.
Слайд 26
Классы приоритетов процессов и приоритеты потоков Win32
Слайд 28
Алгоритм планирования Linux
В операционной системе Linux поддерживаются три
класса потоков:
1. потоки реального времени, обслуживаемые по алгоритму FIFO;
2.
потоки реального времени, обслуживаемые в порядке циклической очереди;
3. потоки разделения времени.
Linux различает 140 уровней приоритета.
Потоки реального времени имеют приоритеты от 0 до 99, причем 0 – самый высокий приоритет.
Обычному потоку ставится в соответствие уровень приоритета от 100 до 139.
Каждому уровню приоритета обычных потоков соответствует свое значение длительности кванта времени.
Linux связывает с каждым потоком значение nice, которое определяет статический приоритет каждого потока. По умолчанию он равен 0, но его можно изменить при помощи системного вызова nice(value), где value меняется от -20 до +19.
Слайд 29
Очередь исполнения и массивы приоритетов в Linux
Слайд 30
Алгоритмы планирования в ОС пакетной обработки информации
1. "Первый
пришел - первым обслужен" (FIFO)
+ Достоинства:
простота;
справедливость.
2. "Кратчайшая задача –
первая»
Минимизирует среднее оборотное время выполнения задачи.
Оборотное время – время, прошедшее от момента запуска всего пакета на выполнение до получения результата задачи.
A
B C D
Время выполнения: 8 мин. 4 мин. 4 мин. 4 мин.
Слайд 33
4. Трехуровневое планирование
3. Наименьшее оставшееся время выполнения
Слайд 34
Планирование в интерактивных системах
+
простота;
справедливость.
-
- слишком малый квант времени приводит к частому переключению процессов и снижению производительности;
- слишком большой квант может привести к увеличению времени ответа на интерактивный запрос.
1. Циклическое планирование (квантование)
Слайд 36
4.Гарантированное планирование
Суть алгоритма
Необходимо отслеживать, сколько процессорного времени затрачено
на каждый процесс с момента его создания. Затем вычисляют
отношение времени, фактически полученного процессом к количеству времени, на которое он имел право.
На выполнение выбирается процесс с наименьшим отношением, который будет работать до тех пор, пока его соотношение не превысит соотношение его ближайшего конкурента.
3. Самый короткий процесс - следующий
Слайд 37
5. Лотерейное планирование
Основная идея состоит в раздаче процессам
лотерейных билетов на доступ к различным системным ресурсам, в
том числе и к процессорному времени. Когда планировщику нужно принимать решение, в случайном порядке выбирается лотерейный билет, и ресурс отдается процессу, обладающему этим билетом. Применительно к планированию процессорного времени система может проводить лотерейный розыгрыш 50 раз в секунду, и каждый победитель будет получать в качестве приза 20 мс процессорного времени.
Слайд 38
6. Справедливое планирование
Некоторые системы перед планированием работы процесса
берут в расчет, кто является его владельцем. В этой
модели каждому пользователю распределяется некоторая доля процессорного времени и планировщик выбирает процессы, соблюдая это распределение. Таким образом, если каждому из двух пользователей было обещано по 50% процессорного времени, то они его получат, независимо от количества имеющихся у них процессов.
Слайд 39
Планирование в системах реального времени
Критерий эффективности – способность
системы выдерживать заранее заданные интервалы времени между запуском программы
и получением результата (реактивность системы).
периодический набор задач
pi - периоды
di - предельные сроки
сi - требования к времени выполнения
μ – коэффициент использования процессора
μi = сi / pi
Необходимое условие существования расписания:
μ =∑ сi / pi ≤ k,
где k - количество доступных процессоров.
Слайд 42
Алгоритм Лью - Лейланда
Классический
алгоритм для жестких систем реального времени с одним процессором.
Алгоритм
основан на следующих предположениях:
Запросы на выполнение всех задач набора, имеющих жесткие ограничения на время реакции, являются периодическими.
Все задачи независимы.
Срок выполнения задачи равен ее периоду.
Максимальное время выполнения каждой задачи сi известно и постоянно.
Время переключения контекста можно игнорировать.
Максимальный суммарный коэффициент загрузки процессора ∑ сi / pi ≤ n(21/n -1), где n – число задач.
Суть алгоритма: задача с самым коротким периодом получает наивысший приоритет, задача с наибольшим периодом получает наименьший приоритет.
Слайд 43
Межпроцессное взаимодействие
согласование действий процессов;
передача информации от одного процесса
другому;
контроль над деятельностью процессов.
Слайд 44
Лекция № 6
Синхронизация процессов и потоков
Слайд 45
Потребность в синхронизации потоков возникает только в мультипрограммной
операционной системе и связана с совместным использованием аппаратных и
информационных ресурсов вычислительной системы.
Слайд 46
Гонки (взаимные состязания)
Состязания (гонки)–
ситуация, когда два или более потока обрабатывают разделяемые данные
и конечный результат зависит от соотношения скоростей потоков.
Слайд 47
Способы реализации взаимного исключения
1. Запрет прерываний
2. Блокирующие переменные
Слайд 49
Семафоры Дейкстры
Семафоры – переменные, которые могут принимать целые
неотрицательные значения и используются для синхронизации вычислительных процессов.
Для
работы с семафорами определены два примитива:
V(S): S=S+1 единым действием;
P(S): S=S-1 , если возможно; если это невозможно, то поток, вызвавший P(S) переводится в состояние ожидания.
Слайд 50
Решение классической задачи синхронизации «читатели – писатели» с
помощью семафоров
буферный пул состоит из N буферов.
e - число
пустых буферов и f - число заполненных буферов
Слайд 51
Взаимные блокировки
(тупики, клинчи, дедлоки)
Взаимная блокировка –
ситуация, когда несколько процессов борются за ресурсы, и ни
один из них не может завершить начатую работу.
Слайд 53
Условия взаимоблокировки:
Условие взаимного исключения.
Каждый
ресурс в данный момент или отдан одному процессу или
свободен.
Условие удержания и ожидания.
Процесс, удерживающий в данный момент ресурс, может запрашивать новые ресурсы.
Условие отсутствия принудительной выгрузки ресурса.
У процесса нельзя забрать ранее полученные ресурсы.
Условие циклического ожидания .
Должна существовать круговая последовательность из процессов, каждый, из которых ждет доступа к ресурсу, удерживаемому следующим членом последовательности.
Слайд 55
процессы A, B, C
ресурсы R, S, T
А
Запросить R
Запросить S
Освободить R
Освободить S
B
Запросить S
Запросить T
Освободить S
Освободить T
C
Запросить T
Запросить R
Освободить T
Освободить R
Слайд 57
Стратегии при столкновении с взаимными блокировками
Слайд 58
Обнаружение и устранение взаимоблокировок
1. Обнаружение взаимоблокировки при наличии
одного ресурса каждого типа
Для каждого узла N в графе
выполняются следующие 5 шагов
Слайд 59
2. Обнаружение взаимоблокировки при наличии нескольких ресурсов каждого
типа
m - число классов ресурсов
n - количество процессов,
P1… Pn
E = (Е1, Е2, Е3 , …, Еm ) - вектор существующих ресурсов, где
Ei - количество ресурсов класса i,
A = (A1, A2, A3 , …, Am ) - вектор доступных ресурсов,
Ai - количество доступных ресурсов класса i,
С - матрица текущего распределения R - матрица запросов
Слайд 63
Динамическое избежание взаимоблокировок
Траектории ресурсов
А1 - запрос принтера процессом
А,
А2 - запрос плоттера процессом А,
А3 - освобождение
принтера процессом А,
А4 - освобождение плоттера процессом А
В1 - запрос плоттера процессом В,
В2 - запрос принтера процессом В,
В3 - освобождение плоттера процессом В,
В4 - освобождение принтера процессом В.
Слайд 64
Опасные и безопасные состояния
Состояние безопасно, если система не
находится в тупике и существует некоторый порядок планирования, при
котором каждый процесс может работать до завершения, даже если все процессы захотят получить свое максимальное количество ресурсов.
В безопасном состоянии система может гарантировать, что все процессы закончат свою работу, в небезопасном состоянии такой гарантии дать нельзя.
Слайд 65
Алгоритм банкира для одного вида ресурсов
Слайд 66
Алгоритм банкира для несколько видов ресурсов
E=(6342) - существующие ресурсы,
P=(5322) -
занятые ресурсы,
A=(1020) - доступные ресурсы
Слайд 67
Предотвращение условий, необходимых для взаимоблокировок
Слайд 68
Системные средства синхронизации
Системные семафоры;
мьютексы;
события;
объекты
таймеры; ядра
файлы, процессы, потоки…
Слайд 69
Мьютексы (от MUTual Exclusion -взаимоисключения) – объекты ядра
позволяют координировать взаимное исключение доступа к разделяемому ресурсу.
Системные семафоры
- принцип действия мьютексов, но в них заложена возможность подсчета ресурсов, что позволяет заранее определенному числу потоков одновременно войти в синхронизуемый участок кода.
Слайд 70
События используются в качестве сигналов о завершении какой-либо
операции.
Слайд 71
Сигнал
или виртуальное прерывание является сообщением, которое система
посылает процессу или один процесс посылает другому.
Слайд 72
Мониторы Хоара
Монитор – это пассивный набор разделяемых переменных
и повторно входимых процедур доступа к ним, которыми процессы
пользуются в режиме разделения, причем в каждый момент времени им может пользоваться только один процесс.
Слайд 74
Обмен данными между процессами и потоками
Слайд 76
Очереди сообщений
позволяют процессам и потокам обмениваться структурированными сообщениями;
являются глобальными средствами коммуникаций для процессов, так как каждая
очередь в пределах ОС имеет уникальное имя.
Почтовые ящики
Почтовые ящики обеспечивают только однонаправленные соединения.
