2 процесса называют параллельными, если они оба одновременно присутствуют в вычислительной смеси.
2 парал. процесса называют асинхронными, если по сост. одного процесса невозможно определить состояние другого. И зачастую асинхронность нужно синхронизировать.
Критические участки - участок кода процесса, проходя через который данный процесс может нарушить целостность некоторых глобальных разделяемых данных.
Синхронизация двух и более процессов заключается в реализации исключения одновременного вхождения процессов в свои критические участки, связанные с одним и теми же глобальными разделяемыми данными. Это реализация взаимного исключения.
Делится на 3 вида:
· программная
· аппаратная
· системная
Программная - Алгоритм Деккера.
Системная:
Семафоры - некоторые системные переменные, непосредственно доступные ОС и доступные пользовательским процессам через систему. В системе существует два вызова - p и v примитивы.
Реализация заключается в помещении системного вызова P(S) непосредственно перед входом в крит. зону. V(S) - после выхода из нее. S - семафоры относятся к крит. участкам, связанным с одними и теми же глоб. раздел. данными.
Семафор называется бинарным, если умеет принимать только значения 1 и 0.
Аппаратная: Заключается в добавлении спец. инструкции - test&set(a,b), с двумя операндами, и она меняет в зависимости от состояния одного из них состояние другого, при этом непрерывно.
РЕЖИМ РЕАЛЬНОГО ВРЕМЕНИ: Системы реального времени характеризуются предельно допустимым временем реакции на внешнее событие, в течение которого должна быть выполнена программа, управляющая объектом. Система должна обрабатывать поступающие данные быстрее, чем те могут поступать, причем от нескольких источников одновременно.
Столь жесткие ограничения сказываются на архитектуре систем реального времени, например, в них может отсутствовать виртуальная память, поддержка которой дает непредсказуемые задержки в выполнении программ.
от времени, за которое эти вычисления производятся.
Для событий, происходящих в такой системе, важно время, когда эти события происходят, и их логическая корректность.
Система работает в реальном времени, если ее быстродействие адекватно скорости протекания физических процессов на объектах контроля или управления (имеются в виду процессы, непосредственно связанные с функциями, выполняемыми конкретной системой реального времени). Система управления должна собрать данные, произвести их обработку по заданным алгоритмам и выдать управляющее воздействие за такой промежуток времени, который обеспечивает успешное выполнение поставленных задач.
Основные требования к СРВ:
возможность параллельного выполнения нескольких задач;
предсказуемость;
важно максимальное (не среднее) время отклика на событие;
особые требования в вопросах безопасности;
возможность безотказной работы в течение длительного времени.
|
|
МНОГОУРОВНЕВАЯ ОЧЕРЕДЬ С ОБРАТНЫМИ СВЯЗЯМИ: Можно сказать, что данный алгоритм использует прошлое, чтобы предсказать будущее. Вначале каждый процесс попадает в очередь с одинаковым приоритетом. Если процесс не отработал весь квант времени, то он переходит в очередь с большим приоритетом. Высший приоритет получают те задачи, которым он, как правило, нужен (например, интерактивные). Сложные вычислительные задачи, занимающие много времени, попадают в очередь с небольшим приоритетом.
|
|
АЛГОРИТМ ДЕККЕРА: Если два процесса пытаются перейти в критическую секцию одновременно, алгоритм позволит это только одному из них, основываясь на том, чья в этот момент очередь. Если один процесс уже вошёл в критическую секцию, другой будет ждать, пока первый покинет её. Это реализуется при помощи использования двух флагов и переменной turn. Процессы объявляют о намерении войти в критическую секцию; это проверяется внешним циклом «while». Если другой процесс не заявил о таком намерении, в критическую секцию можно безопасно войти. Взаимное исключение всё равно будет гарантировано, так как ни один из процессов не может войти в критическую секцию до установки этого флага. Это также гарантирует продвижение, так как не будет ожидания процесса, оставившего «намерение» войти в критическую секцию. В ином случае, если переменная другого процесса была установлена, входят в цикл «while» и переменная turn будет показывать, кому разрешено войти в критическую секцию. Процесс, чья очередь не наступила, оставляет намерение войти в критическую секцию до тех пор, пока не придёт его очередь. Процесс, чья очередь пришла, выйдет из цикла «while» и войдёт в критическую секцию.
Алгоритм Деккера гарантирует взаимное исключение, невозможность возникновения deadlock или starvation. Рассмотрим, почему справедливо последнее свойство. Предположим, что p0 остался внутри цикла «while flag» навсегда. Поскольку взаимная блокировка произойти не может, рано или поздно p1 достигнет своей критической секции и установит turn = 0. p0 выйдет из внутреннего цикла «while turn ≠ 0». После этого он присвоит flag значение true и будет ждать, пока flag примет значение false. В следующий раз когда p1 попытается войти в критическую секцию, он будет вынужден исполнить действия в цикле «while flag». В частности, он присвоит flag значение false и будет исполнять цикл «while turn ≠ 1». Когда в следующий раз управление перейдёт к p0, он выйдет из цикла «while flag» и войдёт в критическую секцию.
Если модифицировать алгоритм так, чтобы действия в цикле «while flag» выполнялись без проверки условия «turn = 0», то появится возможность starvation. Таким образом, все шаги алгоритма являются необходимыми.
|
|
СИСТЕМА РАЗДЕЛЕНИЯ ВРЕМЕНИ: системы разделения времени призваны исправить основной недостаток систем пакетной обработки - изоляцию пользователя-программиста от процесса выполнения его задач. Каждому пользователю системы разделения времени предоставляется терминал, с которого он может вести диалог со своей программой. Так как в системах разделения времени каждой задаче выделяется только квант процессорного времени, ни одна задача не занимает процессор надолго, и время ответа оказывается приемлемым. Если квант выбран достаточно небольшим, то у всех пользователей, одновременно работающих на одной и той же машине, складывается впечатление, что каждый из них единолично использует машину. Ясно, что системы разделения времени обладают меньшей пропускной способностью, чем системы пакетной обработки, так как на выполнение принимается каждая запущенная пользователем задача, а не та, которая "выгодна" системе, и, кроме того, имеются накладные расходы вычислительной мощности на более частое переключение процессора с задачи на задачу. Критерием эффективности систем разделения времени является не максимальная пропускная способность, а удобство и эффективность работы пользователя.
СИСТЕМЫПАКЕТНОЙ ОБРАБОТКИ ДАННЫХ предназначались для решения задач в основном вычислительного характера, не требующих быстрого получения результатов. Главной целью и критерием эффективности систем пакетной обработки является максимальная пропускная способность, то есть решение максимального числа задач в единицу времени. Для достижения этой цели в системах пакетной обработки используются следующая схема функционирования: в начале работы формируется пакет заданий, каждое задание содержит требование к системным ресурсам; из этого пакета заданий формируется мультипрограммная смесь, то есть множество одновременно выполняемых задач. Для одновременного выполнения выбираются задачи, предъявляющие отличающиеся требования к ресурсам, так, чтобы обеспечивалась сбалансированная загрузка всех устройств вычислительной машины; так, например, в мультипрограммной смеси желательно одновременное присутствие вычислительных задач и задач с интенсивным вводом-выводом. Таким образом, выбор нового задания из пакета заданий зависит от внутренней ситуации, складывающейся в системе, то есть выбирается "выгодное" задание. Следовательно, в таких ОС невозможно гарантировать выполнение того или иного задания в течение определенного периода времени. В системах пакетной обработки переключение процессора с выполнения одной задачи на выполнение другой происходит только в случае, если активная задача сама отказывается от процессора, например, из-за необходимости выполнить операцию ввода-вывода. Поэтому одна задача может надолго занять процессор, что делает невозможным выполнение интерактивных задач. Таким образом, взаимодействие пользователя с вычислительной машиной, на которой установлена система пакетной обработки, сводится к тому, что он приносит задание, отдает его диспетчеру-оператору, а в конце дня после выполнения всего пакета заданий получает результат. Очевидно, что такой порядок снижает эффективность работы пользователя.
Проблемы "deadlock"ов.
Тупик - ситуация, когда 2 или более процессов ожидают от друг друга какого - то события, которое никогда не произойдет.
Необходимые, но не достаточные условия возникновения тупиков:
· Неразделяемость ресурсов - заключается в том, что два процесса одновременно не могут владеть одним и тем же ресурсом.
· Условие ожидания - процесс при запросе занятого ресурса блокируется, пока ресурс не освободится.
· Условие неперераспределяемости ресурсов - процесс при запросе нового ресурса не освобождает ранее им захваченный.
· Условие кругового ожидания - существует замкнутая цепочка процессов, каждый из которых хочет завладеть ресурсом, которым уже владеет другой процесс, следующий по этой цепи.
Метод борьбы с тупиками:
· Предотвращение тупиков - принципиальное недопущение возможности их возникновения.
· Обход тупиков - их возникновение возможно, но система старается их избегать.
· Распознавание тупиков и восстановление после них.
Предотвращение - нарушение одного из необходимых условий возникновения:
· Невозможно нарушить программным способом, т.к. это аппаратное свойство ресурсов.
· Выдача всех необходимых процессу ресурсов при его инициализации, если какой либо из ресурсов уже занят, то процесс не начинает свою работу, пока все нужные ему ресурсы не освободятся. Недостаток: непредсказуемое время инициализации процесса, дискриминация процессов с большими требованиями к ресурсам.
· У процесса, требующего уже занятый ресурс, отнимают все ранее захваченные ресурсы и процесс блокируется до тех пор, пока не освободится требуемая ему память + все ранее им захваченные блоки. Но очень сложный алгоритм распределения ресурсов. При запросе занятого ресурса процесс будет блокирован с большой вероятностью на длит. время.
· Процессы нумеруются по ресурсам, если процесс требует ресурс с номером типа k, то он не должен владеть ресурсами с типами меньшими, чем k. Если ими владеет, то он должен их освободить и вернуть, когда освободит ресурс с типом k. За этим может следить процесс и система. Но самый сложный алгоритм перераспределения ресурсов + большая чувствительность алгоритма к добавлению новых ресурсов.
Обход тупиков - Алгоритм Банкира.
Распознавание тупиков.
Существует специальная структура данных, предоставляющая собой ориентированный граф, возможно с циклами или несколькими компонентами связности.
Вершинами графа являются элементы множества, полученного объединением множества процессов и ресурсов.
Дуги графов стоятся по следующему признаку:
· Если процесс хочет завладеть ресурсом, то стрела направляется от процесса к ресурсу.
· Если уже владеет им, то обратно.
Алгоритм распознавания тупиков заключается в следующем:
на каждой операции алгоритма просматриваются все процессы. Если процесс можно удовлетворить немедленно либо он не требует ресурсов, то у него удаляются все стрелки, идущие от него и к нему.
После окончания очередной операции, смотрят, был ли на очередной итерации изменен граф.
Если не был изменен, то алгоритм завершается.
В противном случае начинается следующая итерация алгоритма.
По завершения алгоритма смотрят на состояние графа. Если он вполне не связан, то тупиков нет.
В противном случае каждый компонент связного графа содержит в себе те процессы, которые находятся между собой в тупике. Граф с тупиком - нередуцируемый. Редукция графов.
Если система обнаруживает тупиковую ситуацию, то происходит одно из следующих действий:
· РЕСЕТ ЛОЛ
· Уничтожение всех процессов, находящихся в тупике.
· Реализация контрольных точек (дамп всех процессов во внешнюю память).
· Несколько процессов из тупика целесообразно приостановить.