1 Операционные системы и оболочки Одинцов Игорь Олегович ст. преподаватель кафедры информатики весна 2006 Слайды можно взять на сайтах: и

2 Лекция 5 Процессы и алгоритмы работы с ними в централизованных ОС (окончание)

3 Что надо знать о процессах? Определение, разновидности, состояния, поддержка многопоточности Средства коммуникации Взаимные исключения и блокировки Низкоуровневые и высокоуровневые средства синхронизации Проблема тупиков Планирование и диспетчеризация Безопасность Было на предыдущей лекции

4 Механизмы обеспечения синхронизации Атомарные операции для синхронизации Низкоуровневые (Hardware) Команда test&set Запрет прерываний Высокоуровневые (Software API) Крутящиеся блокировки Семафоры Мониторы Средства ЯВУ (рандеву, …) Было на предыдущей лекции

5 Скотт Максвелл: Ядро Linux в комментариях

6 План лекции Процессы: определение, разновидности, состояния, поддержка многопоточности Коммуникация процессов: простейшие средства (на примере сигналов в ОС Unix) Синхронизация процессов: взаимные исключения и блокировки Синхронизация процессов: низкоуровневые средства (HW) Синхронизация процессов: высокоуровневые средства (SW API) Решение задачи передачи данных между процессами "читатель" и "писатель" Процессы и ресурсы: проблема тупиков Планирование и диспетчеризация процессов Процессы: безопасность (отдельная лекция, позже) Централизованные ОС

7 Тупики Процессы и потоки управления (программные ресурсы) активные объекты. Аппаратные ресурсы: процессор (вытесняемый ресурс) и дисковое пространство (не вытесняемый ресурс) не являются активными объектами. Во время своей работы процесс (поток управления) может попасть в два неприятных состояния: зависание и тупик. Зависание это состояние неопределенного ожидания каких-либо ресурсов, из которого рано или поздно процессы выходят. Тупик это состояние ожидания некоторого события, которое никогда не произойдет (как правило, это круговое ожидание ресурсов). Система находится в тупиковой ситуации, если один или более процессов находятся в состоянии тупика. Было на предыдущей лекции

8 Четыре необходимых условия для возникновения тупика Условие взаимоисключения. Процессы требуют монопольного владения ресурсами, предоставляемыми им; Условие ожидания. Процессы удерживают уже выделенные им ресурсы, ожидая выделения дополнительных); Условие нераспределяемости. Ресурсы нельзя отобрать у удерживающих их процессов, пока они не будут использованы; Условие кругового ожидания. Существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся следующему процессу. Было на предыдущей лекции

9 Четыре основных стратегии работы с тупиками 1. Полное игнорирование проблемы ("алгоритм страуса") подход, при котором операционные системы не осуществляют борьбу с тупиками. Большинство реальных систем поступает именно так, поскольку ресурсов достаточно много. 2. Предотвращение тупиков (prevention) подход, целью которого является обеспечение условий, исключающих возможность возникновения тупиковой ситуации. Чтобы предотвратить тупик, достаточно нарушить хотя бы одно необходимое условие: первое условие (взаимоисключение) вполне естественно (например, для такого устройства, как накопитель на магнитной ленте); нарушая второе условие (ожидание), процесс должен сразу запросить все ресурсы. Эффективность системы при этом может значительно ухудшиться. В качестве компромиссного решения можно предложить разделять процесс на шаги; нарушить третье условие (нераспределяемость) можно следующим образом. Процесс, удерживающий ресурсы и получивший отказ на другие ресурсы, должен освободить все взятые ресурсы и через некоторое время запросить их заново. При этом процесс может потерять большую часть проделанной работы; нарушая четвертое условие (кругового ожидания), следует ввести линейную упорядоченность ресурсов, пронумеровав их, и выдавать их в порядке, не допускающем возникновения кругового ожидания. Данный подход требует значительных накладных расходов на хранение информации, связанной с типами ресурсов и упорядоченностью экземпляров ресурсов.

10 Четыре основных стратегии работы с тупиками 3.Обход тупиков (avoidance) подход, который обеспечивает рациональное распределение ресурсов по рациональным правилам. Он вводит менее жесткие ограничения, чем предыдущий подход. Наиболее известным методом обхода тупиков является алгоритм банкира. Перечислим основные идеи, лежащие в его основе: алгоритм банкира имитирует действия банкира, располагающего определенным источником капитала, выдающего ссуды и принимающего платежи. Алгоритм был предложен Дейкстрой; состояние системы будем называть надежным, если операционная система может обеспечить всем пользователям завершение их задач в течение конечного промежутка времени. Суть алгоритма в том, что система удовлетворяет только те запросы, при которых ее состояние остается надежным. Остальные запросы откладываются; 4.Обнаружение тупиков (detection) подход, который допускает возникновение тупиков, определяет процессы и ресурсы, которые вовлечены в тупиковую ситуацию, и пытается вывести систему из нее.

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

12 Сеть Петри Сеть Петри это помеченный ориентированный граф с двумя типами вершин: позициями и переходами. Позиции изображаются кругами, переходы квадратами, а пометки жирными точками в позициях. Разметка сети Петри функция, которая ставит в соответствие пометкам позиции целое неотрицательное число. Разметка может быть изменена с помощью срабатывания (запуска) перехода. Переход называется запускаемым, если в каждой позиции, из которой ведет стрелка в данный переход, есть хотя бы одна метка. Запуск перехода заключается в том, что из каждой позиции, из которой ведет стрелка, число пометок уменьшается на единицу. А в каждую позицию, в которую ведет стрелка, число пометок увеличивается на единицу. Семантически позиции удобно рассматривать как некоторые условия, а переходы как некоторые события, происходящие в системе. Разметка называется живучей, если каждый из переходов в системе может быть запущен бесконечное число раз. Когда достигается разметка, при которой ни один из переходов не может быть запущен, говорят, что сеть Петри "зависла". Если разметка живучая, то система не остановится.

13 Моделирование взаимного исключения с помощью сети Петри

14 План лекции Процессы: определение, разновидности, состояния, поддержка многопоточности Коммуникация процессов: простейшие средства (на примере сигналов в ОС Unix) Синхронизация процессов: взаимные исключения и блокировки Синхронизация процессов: низкоуровневые средства (HW) Синхронизация процессов: высокоуровневые средства (SW API) Решение задачи передачи данных между процессами "читатель" и "писатель" Процессы и ресурсы: проблема тупиков Планирование и диспетчеризация процессов Процессы: безопасность (отдельная лекция, позже) Централизованные ОС

15 Три уровня планирования процессов Планирование верхнего уровня это планирование при поступлении в систему, планирование стадии "оформления" процесса и его допуска в систему. Планирование промежуточного уровня это планирование при переводе процесса из очереди ожидающих ресурсы в очередь готовых к помещению на процессор. Планирование нижнего уровня (диспетчеризация) это планирование очереди готовых к помещению на процессор процессов.

16 Планирование и диспетчеризация процессов Системы с однопользовательским режимом. Система запускает одну задачу и ждет ее полного завершения: невытесняемость Системы с пакетным режимом. Переключение процессора с одной задачи на другую происходит лишь в том случае, если активная задача сама отказывается от процессора: пассивная вытесняемость Системы с многозадачным режимом. Переключение процессора происходит по истечении некоторого кванта времени: активная вытесняемость Многозадачный режим применяется в интерактивных системах и системах реального времени.

17 Цели планирования Справедливость планирования, заключающаяся в том, что надо относиться к процессам одинаково и не откладывать бесконечно их поступление на процессор Эффективность: занятие 100% процессорного времени Минимальные накладные расходы (работа – планирование) Постепенное снижение работоспособности системы Завершение максимального количества процессов в единицу времени Цель особенно актуальна для пакетных систем Обеспечение приемлемого времени ответа максимальному числу пользователей Цель особенно актуальна для интерактивных систем Предсказуемость планирования, определяемая тем, что одна и та же задача должна выполняться в системе за одно и то же время, независимо от условий Цель особенно актуальна для систем реального времени

18 Приоритет Приоритет некоторое число, сопоставленное каждому процессу из очереди готовых процессов и обозначающее важность процесса. Приоритеты бывают: статические (не меняющиеся с момента поступления процесса в систему) и динамические; присваиваемые автоматически (system defined) и назначаемые извне (user defined); купленные (например, в 70-х годах XX века в американских вычислительных центрах за назначение высокого приоритета платили деньги) и заслуженные; рациональные (назначенные из разумных соображений) и случайные (random). Проблема приоритетного планирования: низкоприоритетные процессы могут быть не запущены неопределенно долгое время

19 Приоритеты в ОС Solaris Реального времени Системные (ядра) Разделения времени высокий 29 низкий

20 Алгоритмы планирования (1) Первый пришедший в очередь процесс обслуживается первым (First Comes First Served FCFS). Процессы получают процессор в порядке их поступления в очередь готовых процессов. Получив процессор, они выполняются на нем до своего полного завершения. Циклическое (круговое) обслуживание (Round Robbin RR). Каждый процесс находится на процессоре ограниченный квант времени, по истечении которого становится в конец очереди. Разновидность кругового обслуживания круговорот со смещением, при котором квант времени зависит от внешнего приоритета процесса.

21 Алгоритмы планирования (2) Кратчайший процесс обслуживается первым (Shortest Job First SJF). На процессор первым поступает процесс с минимальным оценочным временем исполнения. Процессы исполняются до полного завершения. Заметим, что в большинстве случаев невозможно предсказать оценочное время завершения. Возможным вариантом решения является сохранение истории и анализ косвенных признаков (число обращений к внешним устройствам). Первым обслуживается процесс с наименьшим остаточным временем (Shortest Rest Time SRT). Это случай дополнения предыдущего алгоритма квантованием времени.

22 Алгоритмы планирования (3) Многоуровневые очереди (Multilevel Queue). Для систем в которых процессы могут быть легко рассортированы по нескольким группам (преподавательские, студенческие, школьные) Многоуровневые очереди с обратными связями. Данный алгоритм использует прошлое, чтобы предсказать будущее. Вначале каждый процесс попадает в очередь с одинаковым приоритетом. Если процесс не отработал весь квант времени, то он переходит в очередь с большим приоритетом. Высший приоритет получают те задачи, которым он, как правило, нужен (например, интерактивные). Если процесс провел весь положенный ему квант времени на процессоре, то он переходит в очередь с меньшим приоритетом. Сложные вычислительные задачи, занимающие много времени, попадают в очередь с небольшим приоритетом.

23 Планирование в многопроцессорных ОС Назначение процессов процессорам Планирование процессов: обычно общая очередь (или несколько) Планирование потоков: Разделение загрузки (общая очередь) Бригадное планирование (связанные потоки распределяются одновременно) Назначение процессоров (выделение пула) Использование многозадачности на отдельном процессоре Диспетчеризация процесса

24 Что надо знать о процессах? Средства коммуникации Средства синхронизации Проблема тупиков Планирование ИзучилиБудем изучать Переходим к сетевым и распределенным ОС

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

26 Семиуровневая модель протоколов Взаимосвязи Открытых Систем 1. Пользовательский уровень (уровень приложения). Предоставляет услуги конечному пользователю. 2. Уровень представления. Выполняет интерпретацию данных (например, определение кодировки). 3. Сеансовый уровень. Осуществляет проверку полномочий (аутентификацию). 4. Транспортный уровень. Обеспечивает корректную сквозную передачу данных. 5. Сетевой уровень. Выполняет маршрутизацию и ведение учета. 6. Канальный уровень. Обеспечивает прием и передачу пакетов, определение аппаратных адресов. 7. Физический уровень. Отвечает за передачу неструктурированного потока данных по физической среде.

27 Спасибо! Вопросы?

28 P.S. Экзаменационные вопросы: Процессы и ресурсы: проблема тупиков Планирование и диспетчеризация процессов