Шпаргалка по "Операционные системы и среды "

Многопоточность-  это использование нескольких потоков в  одном процессе. При запуске многопоточного процесса, в системе с одним процессором, потоки работают поочередно.

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

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

Вопрос  10.   Ресурсы.

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

Последовательность  использования ресурсов:  запрос- использование-возврат. Если процесс  занят, процесс уходит в режим  ожидания: запрос- режим ожидания- снова  запрос и т.д.- использование- возврат.

Природа запросов ресурсов зависит от системы; процессы могут  запрашивать 2, 3 и более ресурсов; ресурсы можно получить последовательно.

Вопрос 11. Межпроцессорное взаимодействие.

Межпроцессорное взаимодействие разбивается на три пункта: 1) передача инф-ции  от одного процесса к другому. 2) контроль над деятельностью процесса. 3) согласование действий процессов.

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

 Критические области. Основным способом предотвращения проблем состязания является запрет одновременного чтения, записи более чем одним процессом т.е. необходимо взаимоисключения. Часть программы, в которой есть обращение к используемым данным ( ресурсам), называется критической областью или критической санкцией. Чтобы избежать критической области необходимо выполнение 4-х условий: 1) два процесса не должны одновременно находиться в критической области. 2) в программе не должно быть предположения о скорости и количеству процессов. 3) процесс, находящийся вне критической области может блокировать другие процессы. 4) невозможна ситуация, в которой процесс вечно ждет опадения в критическую область.

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

1. Запрет прерываний при входе процесса в критическую область и разрешение прерываний при выходе из нее.
2. Переменные блокировки. Вводятся переменные: если равно нулю, то свободно; если равно единице- занято. Однако этот метод не достаточно эффективен.
3. Строгое чередование. Попадание в критическую область по очереди. Этот метод нарушает три условия успешной работы двух параллельных процессов, совместно используемыми данными. Здесь проходит постоянная проверка значения переменной, в ожидании можно входить в критическую область или нет. Блокировка, использующая активное ожидание, называется спин- блокировкой.

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

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

2) проблема ограниченного доступа. Если два процесса совместно используют буфер ограниченного размера: а) отправитель заполняет буфер, получатель не успевает обрабатывать; отправитель находится в ожидании. б) получатель обработал все данные, отправитель не успевает отправлять; получатель ожидает. Решение проблемы: добавление бита ожидания – установка значений, когда процесс пытается уйти в состояние ожидания.

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

4) мьютексы. Это упрощенная версия семафора. Он управляет взаимным исключением доступа к совместно используемым ресурсам или кодам.  Мьютекс- переменная, которая находится в одном из двух состояний ( блокированном или неблокированном).

5) мониторы.

Монитор был разработан в 1974 году Хоаром и Брингеном Хансонами. Монитор – набор процедур, переменных  и других структур данных, объеденных в модуль или пакет. Процессы могут вызывать процедуры монитора, но у процедур, объявленных вне монитора, нет прямого доступа к внутренним структурам данного монитора. При обращении к монитору в любой момент времени активным может быть только один процесс.

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

Вопрос 12. Планирование процессов.

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

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

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

Существует  множества ситуаций, связанных с планированием. Несколько из них:

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

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

1. Без переключений ( неприоритетное планирование). Процесс работает столько, сколько ему требуется.
2. С переключением ( приоритетное планирование). Процесс работает ровно в течении отведенного ему времени.

В различных системах применяют различные системы  планирования: в системах реального  времени- оба алгоритма; в системах пакетной обработки- оба алгоритма; в интерактивных системах- алгоритм с переключением.

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

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

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

Планирование  в интерактивной  системе.

1. Циклическое планирование. Каждому процессу определяется квант времени, если процесс в него не улаживается, управление передается другому процессу. Здесь важно выбирать размер кванта.
2. Алгоритм приоритетного планирование. Управление передается процессу с большим приоритетом. Установка производится по формуле 1/f, где f- часть использованного последний раз кванта времени.
3. Самый короткий процесс- следующий. Выбирается в очереди самый короткий по времени исполнения процесс.
4. Гарантийное планирование. Система рассчитывает кол-во ресурсов процессора, и распределяет их по стоящим в очереди процессам.
5. Лотерейное планирование.  Процесс выбирается случайным образом. Взаимодействующие процессы могут обменивается местами в очереди.
6. Справедливое планирование. Каждому процессу предоставляется определенная доля ресурсов процессора.

Планирование  в системах реального  времени.

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

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

Планирование  потоков.  Планирование потоков зависит от того, поддерживаются они на уровне пользователя, на уровне ядра или в том и другом варианте.

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

На уровне ядра. Ядро выбирает поток, ему предоставляется  квант времени, после чего предоставляется  управление следующему потоку. На переключение ядра с потока на поток требуется  время. 

Вопрос 13. Взаимоблокировка. 

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

Условия взаимоблокировки:

- Условия взаимного  исключения. Каждый ресурс в данный  момент доступен или отдан  только одному процессу.

- Условия и удержания.  Процесс удерживает в данный  момент полученные ранее ресурсы  и может запрашивать новые  ресурсы. 

- Условие отсутствия  принудительной выгрузки ресурсов.

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

Для того чтобы произошла  взаимоблокировка, должны выполняется  все 4 условия.

При столкновении с взаимоблокировкой  применяются стратегии:

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

  

Выход из взаимоблокировки.

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