![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Задача производителя потребителя
Сейчас мы рассмотрим одну из общих задач параллельных вычислений — задачу производителя/потребителя. Вот ее обобщенная формулировка. Имеются один или несколько производителей, генерирующих данные некоторого типа (записи, символы и т.п.) и помещающих их в буфер, а также единственный потребитель, который извлекает помещенные в буфер элементы по одному. Требуется защитить систему от перекрытия операций с буфером, т.е. обеспечить, чтобы одновременно получить доступ к буферу мог только один процесс (производитель или потребитель). Мы рассмотрим несколько решений этой задачи, с тем чтобы проиллюстрировать как мощь семафоров, так и встречающиеся при их использовании ловушки. Для начала предположим, что буфер бесконечен и представляет собой линейный массив элементов. Говоря абстрактно, мы можем определить функции производителя и потребителя следующим образом:
На рис. 5.4 показана структура буфера b. Производитель может генерировать данные и сохранять их в буфере со своей индивидуальной скоростью. Всякий раз при сохранении увеличивается индекс in. Потребитель поступает аналогично, с тем отличием, что он не должен считывать данные из пустого буфера. Следовательно, перед выполнением считывания он должен убедиться, что производитель обогнал его (in > out). Примечание. Занятая часть буфера заштрихована Рис. 5.4. Бесконечный буфер задачи производитель/потребитель Попытаемся реализовать нашу систему с использованием бинарных семафоров. В листинге 5.8 приведена первая попытка реализации. Вместо работы с индексами in и out мы можем просто отслеживать количество элементов в буфере посредством целой переменной n = in - out. Для осуществления взаимного исключения используется семафор s; семафор delay применяется для ожидания потребителя при пустом буфере. Листинг 5.8. [Неверное] решение задачи производитель/потребитель с использованием бинарных семафоров int n;
Решение представляется достаточно простым и очевидным. Производитель может добавлять данные в буфер в любой момент времени. Перед добавлением он выполняет waitB (s), а после добавления— signalB (s), чтобы предотвратить обращение к буферу других производителей или потребителя на все время операции добавления данных в буфер. Кроме того, при работе в критическом разделе производитель увеличивает значение п. Если n = 1, то перед этим добавлением данных в буфер он был пуст, так что производитель выполняет signalB (delay), чтобы сообщить об этом потребителю. Потребитель начинает с ожидания производства первого элемента, используя вызов waitB (delay). Затем потребитель получает данные из буфера и уменьшает значение n в своем критическом разделе. Если производители опережают потребителя (достаточно распространенная ситуация), то потребитель будет редко блокирован семафором delay, поскольку п обычно положительно. Следовательно, благополучно работают и производитель, и потребитель. Тем не менее в предложенной программе имеется один изъян. Когда потребитель исчерпывает буфер, он должен сбросить семафор delay с помощью инструкции if (n == 0) waits (delay);, чтобы дождаться размещения данных в буфере производителем. Рассмотрим сценарий, приведенный в табл. 5.2. В строке 14 потребитель не выполняет операцию waitB. Он действительно исчерпал буфер и установил п равным 0 в строке 8, но до проверки значения п в строке 14 оно было изменено производителем. В результате signals не соответствует предшествующему waitB. Значение п, равное -1 в строке 20, означает, что потребитель пытается извлечь из буфера несуществующий элемент. Простое перемещение проверки в критический раздел потребителя недопустимо, так как может привести к взаимоблокировке (например, после строки 8). Решение проблемы заключается во введении вспомогательной переменной, значение которой присваивается в критическом разделе и используется вне его, как показано в листинге 5.9. Внимательно рассмотрев приведенный код, вы убедитесь в отсутствии возможных взаимоблокировок.
Таблица 5.2. Возможный сценарий работы программы из листинга
Листинг 5.9. Верное решение задачи производитель/потребитель с использованием бинарных семафоров int n; Несколько более простое решение (приведенное в листинге 5.10) можно получить при использовании обобщенных семафоров (именуемых также семафорами со счетчиками). Переменная n в этом случае является семафором; ее значение остается равным количеству элементов в буфере. Предположим теперь, что при переписывании этой программы произошла ошибка, и операции signal (s) и signal (n) оказались взаимозамененными. Это может привести к тому, что операция signal (n) будет выполняться в критическом разделе производителя без прерывания потребителя или другого производителя. Повлияет ли это на выполнение программы? Нет, поскольку потребитель в любом случае должен ожидать установки обоих семафоров перед продолжением работы. Листинг 5.10. Решение задачи производитель/потребитель с использованием семафоров semaphore n = 0; Теперь предположим, что взаимозаменены операции wait(n) и wait(s). Это приведет к фатальным последствиям. Если пользователь войдет в критический раздел, когда буфер пуст (n.count = 0), то ни один производитель не сможет добавить данные в буфер и система окажется в состоянии взаимной блокировки. Это хороший пример тонкости работы с семафорами и сложности корректной разработки параллельно работающих процессов. А теперь добавим к нашей задаче новое, достаточно реалистичное ограничение — конечность буфера. Буфер рассматривается нами как циклическое хранилище (см. рис. 5.5), при работе с которым значения указателей должны выражаться по модулю размера буфера. При этом выполняются следующие условия.
Вопрос 22.
Монитор — конструкция языка программирования, поддерживающая управляемый доступ к разделяемым данным. Монитор инкапсулирует: 1. Разделяемые критические данные. 2. Функции, использующие разделяемые данные. 3. Синхронизацию выполнения параллельных потоков, вызывающих указанную функцию. § Доступ к данным, располагающимся в мониторе, реализуется только из его функций. § Код синхронизации добавляется автоматически компилятором. Для каждого экземпляра монитора в каждый момент времени может выполняться не более одной функции.
Мониторы Хаара if (усл) wait (cv); При вызове signal: 1. Немедленно запускается ожидающий поток. 2. Поток, пославший сигнал, блокируется на все время, пока выполняется поток, которого он вывел из состояния ожидания. + Предсказуемость.
Мониторы Меса while (усл) wait (cv); При вызове signal: 1. Ожидающий поток переводится в состояние «Готов к выполнению». Поток, пославший сигнал, продолжает исполнение. 2. При освобождении монитора поток, получивший сигнал, конкурирует с другими потоками за вход в монитор на равных условиях.
+ Более эффективны (используют меньшее кол-во переменных). + Непосредственно поддерживают broadcast. Если вы получили сигнал, значит, возможно, состояние монитора изменилось.
Вопрос 23. Если запрашиваемый процессом ресурс недоступен, ОС переводит данный процесс в состояние ожидания. В случае когда требуемый ресурс удерживается другим ожидающим процессом, первый процесс не сможет сменить свое состояние. Такая ситуация называется тупиком (deadlock). Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ожидает события, которое никогда не произойдет. Системная тупиковая ситуация, или "зависание системы", является следствием того, что один или более процессов находятся в состоянии тупика. Иногда подобные ситуации называют взаимоблокировками. В общем случае проблема тупиков эффективного решения не имеет. Рассмотрим пример. Предположим, что два процесса осуществляют вывод с ленты на принтер. Один из них успел монополизировать ленту и претендует на принтер, а другой наоборот. После этого оба процесса оказываются заблокированными в ожидании второго ресурса (см. рис. 7.1).
Определение. Множество процессов находится в тупиковой ситуации, если каждый процесс из множества ожидает события, которое может вызвать только другой процесс данного множества. Так как все процессы чего-то ожидают, то ни один из них не сможет инициировать событие, которое разбудило бы другого члена множества и, следовательно, все процессы будут спать вместе. Выше приведен пример взаимоблокировки, возникающей при работе с так называемыми выделенными устройствами. Тупики, однако, могут иметь место и в других ситуациях. Hапример, в системах управления базами данных записи могут быть локализованы процессами, чтобы избежать состояния гонок (см. лекцию 5 "Алгоритмы синхронизации"). В этом случае может получиться так, что один из процессов заблокировал записи, необходимые другому процессу, и наоборот. Таким образом, тупики могут иметь место как на аппаратных, так и на программных ресурсах. Тупики также могут быть вызваны ошибками программирования. Например, процесс может напрасно ждать открытия семафора, потому что в некорректно написанном приложении эту операцию забыли предусмотреть. Другой причиной бесконечного ожидания может быть дискриминационная политика по отношению к некоторым процессам. Однако чаще всего событие, которого ждет процесс в тупиковой ситуации, – освобождение ресурса, поэтому в дальнейшем будут рассмотрены методы борьбы с тупиками ресурсного типа.
Ресурсами могут быть как устройства, так и данные. Hекоторые ресурсы допускают разделение между процессами, то есть являются разделяемыми ресурсами. Например, память, процессор, диски коллективно используются процессами. Другие не допускают разделения, то есть являются выделенными, например лентопротяжное устройство. К взаимоблокировке может привести использование как выделенных, так и разделяемых ресурсов. Например, чтение с разделяемого диска может одновременно осуществляться несколькими процессами, тогда как запись предполагает исключительный доступ к данным на диске. Можно считать, что часть диска, куда происходит запись, выделена конкретному процессу. Поэтому в дальнейшем мы будем исходить из предположения, что тупики связаны с выделенными ресурсами, то есть тупики возникают, когда процессу предоставляется эксклюзивный доступ к устройствам, файлам и другим ресурсам. Традиционная последовательность событий при работе с ресурсом состоит из запроса, использования и освобождения ресурса. Тип запроса зависит от природы ресурса и от ОС. Запрос может быть явным, например специальный вызов request, или неявным – open для открытия файла. Обычно, если ресурс занят и запрос отклонен, запрашивающий процесс переходит в состояние ожидания. Далее в данной лекции будут рассматриваться вопросы обнаружения, предотвращения, обхода тупиков и восстановления после тупиков. Как правило, борьба с тупиками – очень дорогостоящее мероприятие. Тем не менее для ряда систем, например для систем реального времени, иного выхода нет.
|
||||||||||||||||||
Последнее изменение этой страницы: 2016-08-01; просмотров: 968; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.216.201.32 (0.028 с.) |