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

Ф ЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮМ ОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ(государственный технический университет)Кафедра 304(вычислительные машины, системы и сети)Курсовой проект по курсу«Операционные системы»Отчёт по работе№x .Семафоры и синхронизация процессов(наименование работы)Вариант задания№9 .Курсовой проект выполнил:студент гр. 13-501, Резвяков Денис Михайлович(должность)(Ф. И.

О.).(подпись)Курсовой проект принял:доц. каф.304, к.т.н. Алещенко Алла Степановна(должность)(Ф. И. О.)« 8 ».(подпись)декабря(дата приёма)2009 г.Синхронизация процессовСинхронизация процессов — приведение двух или нескольких процессов к такому их протеканию, когда определённыестадии разных процессов совершаются в определённомпорядке,либо одновременно.Синхронизация необходима в любых случаях, когда параллельно протекающим процессам необходимо взаимодействовать.Для её организации используются средства межпроцессноговзаимодействия. Среди наиболее часто используемых средств —сигналы и сообщения, семафоры и мьютексы, каналы (пайпы)и совместно используемая память.История семафоровСемафоры, критические секции и исключения придумалвыдающийся нидерландский учёный Э́дсгер Ви́бе Де́йкстра(Edsger Wybe Dijkstra) в начале 70 годов (1965-1973).

В 1960-хгодах он участвовал в создании ОС THE — первой операционнойсистемы, построенной в виде множества параллельно исполняющихся взаимодействующих процессов. Именно в процессе этойработы появились понятия синхронизации процессов, идеясемафора, а также была чётко осознана необходимость в структуризации процесса программирования и самих программ.Рассматривая ситуации с многопользовательским доступом,он ввёл понятие критический интервал (critical section).Критический интервал — последовательность шагов обработки,в которой последовательный процесс не должен прерыватьсяникаким другим процессом. Он сопоставил каждому, общему–2–для некоторых процессов, набору данных некоторую запирающую переменную (mutex), начальное значение которой равно 1.Если к началу критического интервала значение переменнойбольше нуля, то интервал должен выполняться, иначе ждать.В результате Дейкстра составил следующий алгоритм:mutex := 1;{в начале критического интервала}mutex := mutex – 1;if mutex < 0 then{жди}else{выполняй}{в конце критического интервала}mutex := mutex + 1;if mutex <= 0 then{возьми из очереди очередной процесс и выполняй его}else{всё, больше никого нет}Во время критического интервала значение mutex равно нулюили отрицательному числу.

Абсолютное значение его равнодлине очереди. Чтобы лучше понять эти идеи нужно смотретьне со стороны программы, а со стороны операционной системы.Этот алгоритм именно для неё. Только когда два потока обратятся к критической секции в очереди станет 1 (| 1|). И когдазначение станет 1, тогда ни один поток не находится в критической секции. Для синхронизации со стороны программы быловведено понятие семафор, который просто разрешал или запрещал обращаться потоку. Вот эту синхронизацию и назвалисинхронизацией запираний или взаимным исключением (mutualexclusion — mutex).

Вследствие ошибок при программированиисинхронных событий могут возникать системные заторы(system-deadlock) или мертвые хватки (deadly embrace).–3–СемафорыСемафо́р — это примитив синхронизации потоков,который позволяет войти в заданный участок кода не болеечем n потокам.

Определение ввёл нидерландский учёный —Э́дсгер Ви́бе Де́йкстра.Операции семафораС семафором можно выполнить три операции:● init(n) — инициализировать счётчик семафора в значение n;● wait — ждать пока счётчик станет больше 0; после этогоуменьшить счётчик на единицу (атомарная операция);● signal — увеличить счётчик на единицу.Принцип работы семафораsemaphore.init(3)<...>semaphore.wait<...работа с ресурсом...>semaphore.signalПеред началом работы с семафором его инициализируют,устанавливая количество доступных ресурсов.

Если потокупонадобился разделяемый ресурс, то он сначала занимает егооперацией wait, а затем использует его. После окончанияработы с ресурсом поток освобождает его операцией signal.Операция wait не допустит к ресурсу потоков больше, чем былоуказано при инициализации семафора. Если ресурс полностьюзанят, то очередной поток приостанавливается операцией waitдо освобождения ресурса.–4–Стандартный семафор не гарантирует порядок, в которомзаблокированные потоки будут получать доступ к ресурсу, т.е.доступ к освободившемуся ресурсу получит случайный поток.Типичные ошибкиПри использовании семафоров бывают следующие ошибки:● «утечка семафора» — после окончания работы с ресурсомпрограммист забывает освободить семафор, и ресурс блокируется «навсегда». Реже, случайно в разных местах освобождает егодважды, допуская в дальнейшем большее количество потоковв ресурс.● взаимная блокировка — при работе с несколькими ресурсамиодин поток блокирует сначала первый ресурс, а затем, в процессе работы, блокирует и использует ещё и второй.

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

При создании* атомарная операция — неделимая операция, т.е. такая операция либо выполняется полностью, либо не выполняется совсемсемафора вручную возможна ситуация, что два потока узнаютоб освобождении семафора одновременно, а затем они вдвоёмуменьшат счётчик на две единицы.–5–В настоящее время семафорами называются только семафоры общего вида. Для частных случаев были введены упрощенные примитивы синхронизации потоков на основе семафоров.МьютексМью́текс (англ. mutex, от mutual exclusion — взаимноеисключение) — одноместный или двоичный семафор.

Мьютексможет находиться в одном из двух состояний — отмеченном илинеотмеченном (открыт и закрыт соответственно).Мьютекс — это вариант семафора, проинициализированногоединицей. В результате в каждый момент времени только одинпоток может владеть разделяемым ресурсом.ФьютексФью́текс (англ. futex, сокращение от fast userspace mutex)— альтернативный способ реализации семафоров и мьютексов.Фьютекс представляет собой выровненное целое в общей памяти(для нескольких процессоров). Это целое может быть увеличеноили уменьшено на единицу за одну ассемблерную инструкцию.Процессы, «завязанные» на этот фьютекс, ждут, когда это значение станет положительным. Все операции с фьютексами практически полностью проводятся в пользовательском пространстве, а соответствующие функции ядра задействуются лишьв ограниченном наборе спорных случаев. Так как спорныеслучаи возникают редко, то скорость работы таких семафоровзначительно возрастает.–6–Событие (Event)Событие (event) — это объект синхронизации, состояниекоторого может быть установлено в сигнальное путём вызоваспециальных операций SetEvent или PulseEvent.Событие — это вариант двоичного семафора, обычное состояниекоторого считается «занято», что блокирует ожидающие потоки.Если потоку следует подать определённый сигнал, то семафорпросто освобождается.Такой подход позволяет передать сигнал ещё до окончаниядругой работы потока.

Либо поток может просто периодическипроверять event на наличие сигнала, а в случае его отсутствиявыполнять другую работу. Также механизм событий позволяетпотоку остановиться и ожидать сигнала от одного из несколькихили сразу от всех событий.Различают события с ручным и автоматическим сбросом.Вариант события с автоматическим сбросом, в отличиеот ручного, сам устанавливается в несигнальное состояние послеочередного считывания наличия сигнала ожидающим потоком.Сравнение объектов синхронизацииОбъектОтносительнаяскоростьДоступнесколькихпроцессовКритическаясекциябыстронетМьютексмедленнодаФьютексбыстро (еслинет ожидания)даСемаформедленнодаавтоматическиСобытиемедленнодада–7–Подсчёт числаобращений кресурсунет (эксклюзивныйдоступ)нет (эксклюзивныйдоступ)нет илиавтоматическиПостановка задачиРазработаем программу, эмулирующую работу несколькихпроцессов работающих параллельно на одном микропроцессоре.…т.е.

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

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