Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

САМАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ (СамГУПС)

Электротехнический факультет

Кафедра «Мехатроника в автоматизированных производствах»

Курсовой проект

по дисциплине операционные системы «Синхронизация процессов и потоков»

Выполнил:

студент гр. 1301

Ерохова И.Ю.

Самара 2014

Введение

Существуют мультипрограммные и мультипроцессорные системы. В данных системах возникает потребность в синхронизации процессов и потоков. Синхронизация требуется для исключения эффектов «гонок» и «тупиков». Средство синхронизации относится к сервису ОС, IPC.

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

Ситуация когда два или более процессов или потоков образуют разделяемые данные и конечный результат зависит от соотношения скоростей потоков называется «гонкой».

В мультипрограммных системах «тупик» возникает из-за неправильного обращения к данным.

Рассмотрим несколько задач по тупикам, взаимным блокировкам.

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

Курсовая работа состоит из приведенных ниже 4-х заданий, варианты которых индивидуальны для каждого из студентов.

1. Алгоритмы планирования мультипрограммных операционных систем

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

Другой тип планирования - статический(off-line) - может быть использован в специализированных системах, в которых весь набор одновременно выполняемых задач определен заранее, например, в системах реального времени.

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

Диспетчеризация сводится к следующему:

1)сохранению контекста текущего потока, который требуется сменить;

2)загрузке контекста нового потока, выбранного в результате планирования;

3)запуску нового потока на выполнение.

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

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

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

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

В большинстве современных операционных систем (ОС), например Windows 2000/XP, используются вытесняющие алгоритмы планирования.

Далее среди множества алгоритмов планирования выделяются два больших класса - бесприоритетные и приоритетные алгоритмы (рис. 1).

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

Рис. 1 Классификация алгоритмов планирования

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

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

Линейные алгоритмы планирования реализуют выполнение процессов и потоков в порядке очереди, которая организуется согласно тем или иным соглашениям /7-9/.

Самой простой в реализации является дисциплина обслуживания, при которой процессы и потоки выполняются в порядке их появления в ВС. Этот алгоритм называется «первым пришел - первым обслужен», или FCFS (Firstcome - FirstServed). Те процессы и потоки, которые были заблокированы в процессе выполнения, после перехода в состояние готовности вновь ставятся в очередь готовности. При этом возможны два варианта.

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

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

К основным преимуществам этого алгоритма можно отнести его простую реализацию, справедливость и малые затраты системных ресурсов на формирование очереди задач.

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

Избежать указанного недостатка позволяет невытесняющий алгоритм, при котором планировщик выбирает первым для выполнения самый короткий процесс (задачу). Этот алгоритм называется «кратчайший процесс (задача) - первый», или SJN (ShortestJobNext) /2/. Алгоритм позволяет уменьшить оборотное время - среднее время от момента поступления процесса (задачи) на выполнение до завершения выполнения.

Пусть имеются четыре процесса с временем выполнения первого - a, второго - b, третьего - c и четвертого - d. Тогда первый процесс выполнится через время t_a=a, второй - через время t_b=a+b, третий через время t_c=a+b+c, а четвертый через время t_d=a+b+c+d. Следовательно, среднее оборотное время t_oвычисления четырех процессов равно t_o=(t_a+t_b+t_c+t_d)/4=(4a+3b+2c+d)4. Очевидно, что вклад времени a в среднее больше, чем всех остальных интервалов времени, поэтому первым должен выполняться самый короткий процесс, а последним - самый длинный, вносящий вклад равный собственному оборотному времени. Этот вывод справедлив для любого количества процессов и потоков.

Следующей версией предыдущего алгоритма планирования является алгоритм наименьшего оставшегося времени выполнения, или SRT (ShortestRemainingTime) /2,7-9/. В соответствии с этим алгоритмом планировщик всякий раз выбирает на выполнение процесс с наименьшим оставшимся временем выполнения. Когда появляется новый процесс, его полное время выполнения сравнивается с оставшимся временем выполнения текущего процесса. Если время выполнения нового процесса меньше, текущий процесс приостанавливается и управление передается новому процессу. Этот алгоритм позволяет быстро обслуживать короткие процессы.

В вытесняющем алгоритме планирования, основанном на квантовании, каждому потоку поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени - квант (timeslice). Этот алгоритм получил название циклического (карусельного), или RR (RoundRobin).Смена активного потока происходит, если:

поток завершился и покинул систему

произошла ошибка;

поток перешел в состояние ожидания;

исчерпан квант процессорного времени, отведенный данному потоку.

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

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

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

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

Существуют две разновидности приоритетного планирования: обслуживание с относительными приоритетами и обслуживание с абсолютными приоритетами.

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

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

В системах с относительными приоритетами активный поток выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ожидания (или же из-за ошибки или завершения потока).

В системах с абсолютными приоритетами выполнение активного потока прерывается еще при одном условии: если в очереди готовых потоков появился поток, приоритет которого выше приоритета активного потока. В этом случае прерванный поток переходит в состояние готовности.

Смешанные алгоритмы планирования построены с использованием как концепции квантования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора потока из очереди готовых определяется приоритетами потоков.

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

Подобным образом реализовано планирование в системах WindowsNT/2000, в которых квантование сочетается с динамическими абсолютными приоритетами. На выполнение выбирается готовый поток с наивысшим приоритетом, и ему выделяется квант времени. Если во время выполнения в очереди готовых потоков появляется поток с более высоким приоритетом, то он вытесняет выполняемый поток.

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

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

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

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

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

Одним из эффективных методов планирования для периодических задач является частотно-монотонное планирование (ratemonotonicscheduling -- RMS). Система RMS назначает приоритеты заданиям на основе их периодов.

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

Задание № 1-А

Исходные данные:

Вычислительная система выполняет два процесса: опрос и обработку информации с датчика А и опрос и обработку информации с датчика В. Вычислительные процессы А и В периодические, и их периоды (периоды опроса датчиков) равны =120 и =300 соответственно. Времена обработки информации с датчиков А и В равны соответственно =60 и =150. Планировщик процессов принимает решения с периодом П=60.

Задание:

1) Рассчитать требуемое число процессоров для выполнения процессов А и В в реальном масштабе времени.

2) Составить таблицу профиля выполнения процессов А и В.

3) Построить и описать временные диаграммы выполнения процессов А и В для следующих режимов планирования:

3.0) с квантованием времени;

3.1) с квантованием времени и вытеснением, если приоритет потока А выше приоритета потока В;

3.2) с квантованием времени и вытеснением, если приоритет потока В выше приоритета потока А;

3.3) с приоритетом процесса с наиболее ранним предельным сроком завершения задачи.

4) Определить возможность выполнения процессов в реальном масштабе времени.

5) Рассмотреть перечень средств обеспечения выполнения процессов в реальном масштабе времени.

Таблица 1

Процесс	Время поступления	Время выполнения	Предельное время окончания
А(1)	0	60	120
А(2)	120	60	240
А(3)	240	60	360
А(4)	360	60	480
А(5)	480	60	600
В(1)	0	150	300
В(2)	300	150	600

Компьютер может принимать решение о планировании каждые 60 ms

Рис. 1



Рис. 2 Расчет увеличения производительности процессора.

=>

=150*0,8=120

=> 20% простой системы

Рис. 4

=>

=> 50% простой системы

Рис. 5

д) с частотно-монотонным планированием - полностью совпадает с квантованием времени и вытеснением, если приоритет потока А выше приоритета В

=> 43% простой системы

Оценка выполнения в реальном масштабе времени двух периодических заданий:

Общая загруженность процессора RMC (0,828<1)=> при RMC планировании не будут успешно выполнены все задания. Если повысить производительность процессора, то, тогда 0,80,828 => процессы могут выполняться в реальном времени.

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

задание P₁: C₁ = 60; Т₁ = 120;

задание P₂: С₂ = 150; T₂ =300;

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

.

В табл. 4 приведены некоторые значения верхней границы загруженности процессора для метода RMS для разных значений n. При возрастании количества заданий верхняя граница стремится к значению In 2 =0,693.

Таблица 2

N
1	1.000
2	0.828
3	0.779
4	0.756
5	0.743
6	0.734
*	*
*	*

Загруженность процессора каждым из заданий составляет соответственно: U₁= 0,5; U₂= 0,5. Тогда общая загруженность процессора тремя заданиями составляет U_o=0,5+0,5=1.

Верхняя граница загруженности этих трех задач при использовании метода RMS составляет

.

Поскольку общая загруженность процессора по обработке приведенных заданий выше верхней границы для метода RMS (0,828<1), можно сделать вывод, что при RMS-планировании не будут успешно выполнены все задания. Если повысить производительность, то .Тогда , значит процессы могут выполниться в реальном времени.

Задание №1- Б

По условию вычислительная система выполняет четыре непериодические процессы А, В, С, Д, для которых в таблице 1.3 заданы время поступления, время выполнения и предельные сроки начала работы.

Таблица 3

Процесс	Время поступления	Время выполнения	Предельное время начала работы
A	40	80	440
B	80	80	80
C	160	80	200
D	200	80	360

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

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



Рисунок 1.14 ? Планирование четырех непериодических заданий.

Рисунок 1.15 ? Планирование с наиболее ранним предельным сроком.

Простейшая схема планирования состоит в запуске задания с наиболее ранним предельным сроком и выполнении его до полного завершения.

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

Рисунок 1.16 ? Планирование с наиболее ранним сроком со свободным временем простоя

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

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

Рисунок 1.17? Планирование с использованием стратегии FCFS.

Для сравнения на рисунке 1.17 приведен результат использования стратегии FCFS «первым поступил - первым обслужен». Как видно, в этом случае отклоненным оказывается задание - В.

Задание №2

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

Объяснить достоинства и недостатки каждого из методов взаимного исключения или организации доступа к разделяемым ресурсам. Привести примеры использования в Windows 2000/XP.

Передача сообщений.

Передача сообщений

В рати чего-то другого выступает передача сообщений. Этот метод межпроцессного взаимодействия использует два примитива: send и receive, которые скорее являются системными вызовами, чем структурными компонентами языка (что отличает их от мониторов и делает похожим на семафоры). Поэтому их легко можно поместить в библиотечные процедуры, например sendtcfcsttration.iross-sge): r«:eive(scarce. Snessas?»:

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

Разработка систем передачи сообщений

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

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

Для систем обмена сообщениями также важен вопрос названий процессов. Необходимо однозначно определять процесс, указанный в запросе send или receive. Кроме того, встает вопрос аутентификации: каким образом клиент может определить, что он взаимодействует с настоящим файловым сервером, а не с самозванцем?

Помимо этого, существуют конструктивные проблемы, существенные при расположении отправителя и получателя на одном компьютере. Одной из таких проблем является производительность. Копирование сообщений из одного процессав другой происходит гораздо медленнее, чем операция на семафоре или вход в монитор. Было проведено множество исследований с целью увеличения эффективности передачи сообщений. В (65), например, предлагалось ограничивать размер сообщения до размеров регистра и передавать сообщения через регистры. Решение проблемы производителя и потребителя с передачей сообщений. Теперь рассмотрим решение проблемы производителя и потребителя с передачей сообщений и без использования разделенной памяти. Решение представлено в листинге. Мы предполагаем, что все сообщения имеют одинаковый размер и сообщения, которые посланы, но еще не получены, автоматически помещаются операционной системой в буфер. В этом решении используются N сообщений, по аналогии с сегментами в буфере. Потребитель начинает с того, что посылает производителю N пустых сообщений. Как только у производителя оказывается элемент данных, который он может предоставить потребителю, он берег пустое смещение и отсылает назад полное. Таким образом, общее число сообщений в системе постоянно их можно хранить в заранее заданном участке памяти.

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

Передача сообщений может быть реализована по-разному. Рассмотрим способ адресации сообщений. Можно присвоить каждому из процессов уникальный адрес и адресовать сообщение непосредственно процессам. Другой подход состоит в использовании новой структуры данных, называемой почтовым ящиком. Почтовый ящик -- это буфер для определенного количества сообщений, тип которых задается при создании ящика. При использовании почтовых ящиков в качестве параметров адреса send и receive задаются почтовые ящики, а не процессы. Если процесс пытается послать сообщение в полный почтовый ящик, ему приходится подождать, пока хотя бы одно сообщение нс будет удалено из ящика.

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

Ниже приведена программа.

Работают 3 процесса: Р1, Р2, Р3. И почтовые ящики, передающия сообщения процессам g, i, k.

Работает процесс Р1, затем передает сообщение почтовому ящику g, почтовый ящик g передает сообщение процессу Р2, Р2-I, i-P3, P3- k, k-P1.

Рис.2.1 Передача сообщений



Рис.2.2 Передача сообщений

Рис.2.3 Передача сообщений

Задание №3-А

А) Разработать программу обнаружения взаимных блокировок процессов в вычислительной системе при наличии одного ресурса каждого типа. Распределение ресурсов в вычислительной системе задается графом распределения ресурсов.

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

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

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

1.Задаются начальные условия: L-пустой список, все ребра немаркированы.

2.Текущий узел добавляем в конец списка L и проверяем количество появления узла в списке. Если он встречается два раза, значит цикл и взаимоблокировка.

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

4.Выбираем новое немаркированное исходящее ребро и маркируем его. И переходим по нему к новому узлу и возвращаемся к шагу 3.

5.Зашли в тупик. Удаляем последний узел из списка и возвращаемся к предыдущему узлу. Возвращаемся к шагу 3. Если это первоначальный узел, значит, циклов нет, и алгоритм завершается.

Для реализации работы алгоритма была разработана программа (рисунок 3.2 и 3.4).

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

Рис. 3.1. Граф процессов и ресурсов к примеру рис. 3.2.

Рис. 3.2. Блокировки не обнаружены.



Рис. 3.3. Граф процессов и ресурсов к примеру рис. 3.4.

Рис. 3.4.Есть блокировки.

Задание №3-В

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

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

при наличии нескольких экземпляров ресурсов каждого типа.

Для обнаружения взаимных блокировок в этом случае используются матричные операции. Пусть, например, имеются n процессов, которые захватывают и требуют ресурсы P1,…, Pn. Пусть имеется m классов ресурсов, при этом внутри каждого класса имеется несколько ресурсов:

E1 класс 1

E2 класс 2

Ei класс C

……………….

Em класс m

Задача предполагает следующие понятия (рис. 3.5):

Вектор существующих ресурсов E (E1,E2,…,Em);

Вектор доступных ресурсов A (A1,A2,…,Am), Ai в этом векторе равен количеству экземпляров ресурсов класса i доступных в текущий момент времени;

C - матрица текущего распределения ресурсов (какому процессу какие ресурсы принадлежат), C(ij) - количество экземпляров ресурса j, которое занимает процесс P(i).

R - матрица запросов ресурсов (какой процесс какой ресурс запросил),

R(ij) - количество экземпляров ресурса j, которое хочет получить процесс P(i).

Рис. 3.5. Векторы ресурсов вычислительной системы

Общее количество ресурсов равно сумме занятых и свободных ресурсов.

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

1. Находится процесс Pi для которого i-я строка матрицы R? A.

2. Если такой процесс найден, то прибавляем i-ю строку матрицы C к вектору A и возвращаемся к шагу 1.

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

Для реализации работы этого алгоритма была разработана программа (рисунок 3.6).

Пример. Пусть имеются 4 класса ресурсов - плоттеры, сканеры, принтеры, HDD и 4 процесса - Р₁, Р₂, Р_3, Р₄.

Е = (4 4 3 1) - вектор существующих ресурсов.

А = (2 1 0 1) - вектор доступных ресурсов.

- матрица текущего распределения ресурсов

- матрица запросов ресурсов

Следуем алгоритму:

Находим процесс Pi, для которого i-я строка матрицы R? A. Из всех 4-х процессов этому условию удовлетворяют два процесса - Р_1, Р₂.

Р₁ R₁ ? A₁ 2000 < 2101

Р₂ R₂ ? A₂ 0100 < 2101

Прибавляем 1-ю строку матрицы C к вектору A.

С1 + А = (2 0 1 0) + (2 1 0 1) = 4 1 1 1 А = (4 1 1 1)

Маркируем 1-ый процесс - Р₁.

Снова ищем процесс Pi, для которого i-я строка матрицы R? A. Таких процессов два - Р₂, Р₃.

Прибавляем 2-ю строку матрицы C к вектору A.

С2 + А = (0 2 1 0) + (4 1 1 1) = 4 3 2 1 А = (4 3 2 1)

Маркируем 2-ой процесс - Р₂.

Ищем процесс Pi, для которого i-я строка матрицы R? A. Таких процессов два - Р₃, Р₄.

Прибавляем 3-ю строку матрицы C к вектору A.

С3 + А = (0 1 0 0) + (4 3 2 1) = 4 4 2 1 А = (4 4 2 1)

Маркируем 3-ой процесс - Р₃.

Прибавляем 4-ю строку матрицы C к вектору A.

С4 + А = (0 0 1 0) + (4 4 2 1) = 4 4 3 1

Маркируем последний 4-ый процесс - Р₄.

Выполнились все 4 процесса - Р₁, Р₂, Р_3, Р₄.

Проверка: А = (4 4 3 1) = Е = (4 4 3 1). После выполнения всех четырех процессов вектор доступных ресурсов равен вектору существующих ресурсов.

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

Задание №4

Исходные данные. Дана симметричная мультипроцессорная система. Все N=4 процессоров системы независимы, однотипны и функционально эквивалентны. Предельная скорость обмена по шине V =266, причем каждый процессор при решении задачи требует скорости обмена P= 70 мбайт/сек.

Задание:

1) Разработать структурную и функциональную схемы арбитража со сменой приоритетов для мультипроцессорной системы и описать алгоритм ее работы. Децентрализованный арбитраж.

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

3) Предложить для схемы методы преодоления эффекта насыщения в шине.

Рис.4.1.Структурная схема

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

N = V / P

N = 266 / 70 = 3

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

Не увеличивать надежность, но увеличить производительность.

1. Взять более производительную шину.

Рис. 4.2. Децентрализованный параллельный арбитраж

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

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

(разреш. шины N) = (запр. шины N);

(разреш. шины N-1) = (запр. шины N-1)&(запр. шины N);

____________ ______________

(разреш. шины N-2) = (запр. шины N-2)&(запр. шины N)&(запр. шины N-1) и т.д.

Получив сигнал разрешения шины, контроллер арбитра анализирует состояние линии занятости шины и, если шина свободна, занимает шину и формирует сигнал занятости шины.

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

Сложной проблемой в симметричных мультипроцессорных системах является создание высокоскоростной коммуникационной среды, посредством которой осуществляется доступ процессоров к общим системным ресурсам, и межпроцессорный обмен сообщениями. Типовые системные шины, например, PCI, PCI-X имеют недостаточную скорость обмена, а коммутаторы, многопортовая память и специальные высокоскоростные сети сложны и дороги для широкого применения /4,5/. Одним из возможных решений этой проблемы является выделение для каждого из процессоров ВС локальных ресурсов - памяти и каналов ввода-вывода, которые подключаются к процессору с помощью локальных шин. Этими локальными ресурсами каждый из процессоров владеет монопольно, что сокращает число обращений к общим системным ресурсам и снижает требования к пропускной способности коммуникационной среды. По сути наблюдается переход от мультипроцессорных к мультикомпьютерным системам, реализуемым на основе высокоскоростных сетей - к кластерным системам. Если в качестве коммуникационной сети используется типовая локальная сеть, такая ВС называется распределенной.

мультипрограммный сообщение блокировка вычислительный

Заключение

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

Список использованной литературы

1. Сетевые операционные системы/ В.Г. Олифер, Н.А. Олифер. - СПб.: Питер, 2001. - 544 с.

2. Иртегов Д. В. Введение в операционные системы. - СПб.: БХВ-Петербург, 2002. - 624 с.

3. Таненбаум Э. Современные операционные системы. - СПб.: Питер, 2002. - 1040 с.

4. Таненбаум Э., Вудхал А. Операционные системы: Разработка и реализация. Классика CS. - СПб.: Питер, 2006. - 576 с.

5. Столлингс В. Операционные системы: Внутреннее устройство и принципы проектирования. - М.: Изд. дом «Вильямс», 2002. - 848 с.

6. Операционные системы. Параллельные и распределенные системы / Д. Бэкон, Г. Харрис. - СПб.: Питер, 2004. - 800 с.

7. Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. - СПб.: Питер, 2004. - 668 с.

8. Засов В.А. Операционные системы. - Самара, 2006 - 44 с.

Приложение 1.

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Runtime.InteropServices;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace LocksDetection

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

}

public List<Node> Nodes { get; set; }

void ReadGraph()

{

Nodes = new List<Node>();

L = new List<Node>();

AddNode();

var all = new List<string>();

for (int i = 0; i < dataGridView1.RowCount ; i++)

{

all.Add((string)dataGridView1.Rows[i].Cells[1].Value);

all.AddRange(((string)dataGridView1.Rows[i].Cells[2].Value).Split(','));

}

var n = all.Distinct().Count(x => x != "0") + dataGridView1.RowCount - 1;

for (int i = 0; i < n; i++)

{

AddNode();

}

for (int i = 0; i < dataGridView1.RowCount ; i++)

{

var prev = int.Parse((string)dataGridView1.Rows[i].Cells[1].Value);

var next = int.Parse((string)dataGridView1.Rows[i].Cells[2].Value);

var edge = AddEdge(prev, next);

if (prev == 0)

{

var node = edge.Prev;

L.Add(node);

}

}

if (L.Any())

first = L.First();

}

bool CheckLoop(Node node)

{

//3. Для заданного узла смотрим, выходит ли из него хотя бы одно немаркированное ребро.

var unmarked = node.Edges.Where(x => x.Mark == false);

if (unmarked.Any())

{

//Если да, выбираем новое немаркированное исходящее ребро и маркируем его.

//И переходим по нему к новому узлу и возвращаемся к шагу 3.

var edge = unmarked.First();

edge.Mark = true;

if (L.Contains(edge.Next)) return true;

else

{

L.Add(edge.Next);

return CheckLoop(edge.Next);

}

}

//Eсли нет - зашли в тупик.

//Возвращаемся к шагу 3.

else

{

//Удаляем последний узел из списка и возвращаемся к предыдущему узлу.

var last = L.Last();

L.Remove(last);

last = L.Last();

// Если это первоначальный узел, значит циклов нет, и алгоритм завершается.

if (last == first)

return false;

return CheckLoop(last);

}

return false;

}

private Node first;

private List<Node> L = new List<Node>();

private int count;

void AddNode()

{

count++;

var node = new Node();

node.Id = count;

Nodes.Add(node);

}

Edge AddEdge(int prev, int next)

{

var edge = new Edge();

edge.Mark = false;

edge.Prev = Nodes[prev];

edge.Next = Nodes[next];

Nodes[prev].Edges.Add(edge);

return edge;

}

private void btnDeadlock_Click(object sender, EventArgs e)

{

try

{

ReadGraph();

}

catch (Exception)

{

richTextBox1.AppendText("Некорректно введены данные\n");

return;

}

if (L.Any() == false)

{

richTextBox1.AppendText("Некорректно введены данные\n");

return;;

}

var last = L.Last();

if (CheckLoop(last))

{

richTextBox1.AppendText("Есть блокировки\n");

}

else

{

richTextBox1.AppendText("Блокировки не обнаружены\n");

}

}

private void button1_Click(object sender, EventArgs e)

{

dataGridView1.Rows.Clear();

for (int i = 0; i < numericUpDown1.Value; i++)

{

dataGridView1.Rows.Add();

dataGridView1.Rows[i].Cells[0].Value =i+1;

}

}

}

}

Приложение 2.

using System.Collections.Generic;

using System.Windows;

using GalaSoft.MvvmLight;

using GalaSoft.MvvmLight.Command;

namespace DeadlockPreventing.ViewModel

{

/// <summary>

/// This class contains properties that the main View can data bind to.

/// <para>

/// Use the <strong>mvvminpc</strong> snippet to add bindable properties to this ViewModel.

/// </para>

/// <para>

/// You can also use Blend to data bind with the tool's support.

/// </para>

/// <para>

/// See http://www.galasoft.ch/mvvm

/// </para>

/// </summary>

public class MainViewModel : ViewModelBase

{

/// <summary>

/// Initializes a new instance of the MainViewModel class.

/// </summary>

public MainViewModel()

{

ProcessCount = 3;

FreеResources = 3;

}

private int _processCount;

public int ProcessCount

{

get { return _processCount; }

set

{

if (_processCount == value) return;

_processCount = value;

RaisePropertyChanged("ProcessCount");

Processes = new int[_processCount, 2];

}

}

private int _freеResources;

public int FreеResources

{

get { return _freеResources; }

set

{

if (_freеResources == value) return;

_freеResources = value;

RaisePropertyChanged("FreеResources");

}

}

private int[,] _processes;

public int[,] Processes

{

get { return _processes; }

set

{

_processes = value;

RaisePropertyChanged("Processes");

}

}

private RelayCommand _deadlockPreventingCommand;

public RelayCommand DeadlockPreventingCommand

{

get

{

if (_deadlockPreventingCommand == null)

{

_deadlockPreventingCommand = new RelayCommand(PreventDeadlock, CanPreventDeadlock);

}

return _deadlockPreventingCommand;

}

set { _deadlockPreventingCommand = value; }

}

void PreventDeadlock()

{

Log = "";

var completed = new List<int>();

bool released = true;

var tmp = FreеResources;

while (completed.Count < ProcessCount)

{

released = false;

for (int i = 0; i < ProcessCount; i++)

{

if (completed.Contains(i)) continue;

var has = Processes[i, 0];

var need = Processes[i, 1];

if (need > has)

{

var dif = need - has;

if (FreеResources >= dif)

{

FreеResources += has;

completed.Add(i);

released = true;

AddLog(string.Format("Выполнен {0} процесс, свободный ресурс {1}", i, FreеResources));

break;

}

}

else

{

FreеResources += has;

completed.Add(i);

released = true;

AddLog(string.Format("Выполнен {0} процесс, свободный ресурс {1}", i, FreеResources));

break;

}

}

if (released == false)

{

break;

}

}

FreеResources = tmp;

MessageBox.Show(released ? "Все процессы выполнены" : "Недостаточно свободных ресурсов");

}

bool CanPreventDeadlock()

{

return ProcessCount > 0;

}

private string _log;

public string Log

{

get { return _log; }

set

{

_log = value;

RaisePropertyChanged("Log");

}

}

void AddLog(string msg)

{

Log += msg + "\n";

}

}

}

Размещено на Allbest.ru