Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 133
Текст из файла (страница 133)
После некоторого периода выполнения задача А нуждается в ресурсе У для продолжения своего выполнения, поэтому она запрашивает ресурс у, но вынуждена подождать, пока задача В не освободит его. Аналогично, задача В запрашивает ресурс Х, но должна подождать, пока задача А не освоболит его. Ни одна из задач не освобождает используемые ими ресурсы, и в результате обе они теряют свою живучесть, вследствие чего выполнение программы никогда не завершится нормально. Этот частный вид потери живучести называется взаимной блокировкой (деаб)ос)с). Взаимная блокировки — это серьезная угроза надежности программы, и.
следовательно, вопрос предотврашения таких ситуаций требует серьезного рассмотрения как при разработке языка, так и при написании программ. Глава 12. Параллельность Теперь мы готовы обсудить некоторые лингвистические механизмы управления параллельными модулями. 12.2.2. Разработка языков для поддержки параллельности Для поддержки параллельности разработано много языков, начиная с РЕП в середине 1960-х годов и заканчивая современными языками Ада 95 и )ача. 12.2.3. Вопросы разработки языков программирования Наиболее важные вопросы поддержки параллельности языками программирования— синхронизация конкуренции и синхронизация взаимодействия — уже были детально обсуждены.
Кроме них, существуют вопросы, связанные с тем, как и когда начинается и заканчивается выполнение задач, а также как и когда они создаются. Ниже приведены основные вопросы разработки языков, поддерживающих параллельность. ° Как обеспечивается синхронизация взаимодействия? ° Как обеспечивается синхронизация конкуренции? ° Как и когда начинается и заканчивается выполнение задачи? ° Как именно создаются задачи: статически или динамически? Помимо указанных, есть несколько менее важных вопросов разработки языков. Самый значительный из них — как обеспечить планирование задач. Однако лля простоты наше обсуждение параллельности преднамеренно ограничивается только вопросами, перечисленными выше в этом разделе. Следующий раздел посвящен трем альтернативным ответам на вопросы разработки срелств обеспечения параллельности: семафорам, мониторам и передаче сообщений.
12.3. Семафоры Семафор — очень простоИ механизм, используемый для синхронизации задач. 12.3.1. Введение Семафоры в 1965 году изобрел Эдсгер Дийкстра (Едзйег 1)1)кзгга) для синхронизации конкуренции с помощью взаимно исключающего доступа к совместно используемым структурам данных (Р1)Юга, 1968а). Семафоры можно также использовать лля синхронизации взаимодействия. Семафор — это струкгура данных, состоящая из целого числа и очереди, хранящей дескрипторы задач. Дескриптор задачи — это структура данных. хранящая всю информанию о состоянии выполнения задачи. Для ограничения доступа к структуре данных семафор расставляет предохранители вокруг кода, имеющего доступ к этой структуре. Предохранитель можно использовать для того, чтобы открыть доступ к совместно используемой структуре данных только одной задачи в каждый момент времени.
Семафор — это реализация предохранителя. Неотъемлемой частью механизма предохранения является способ, гарантирующий успешное завершение выполнения заблокированного кода. Для этого запросы доступа, возникающие, когда доступ не может быть предостав- 12.3. Семафоры лен, размещаются в очереди дескрипторов задач. Затем эти задачи получают доступ к данным и выполняют заблокированный код. По этой причине семафор должен иметь и счетчик, и очередь дескрипторов задач. С семафорами можно выполнять только две операции, первоначально названные Дийкстрой буквами Р и У, от двух голландских слов раззегел (передать) и заулегел (освободить) (Апдгежз апд Бсппек)ег, 1983). Мы будем называть эти операции в ходе дальнейшего обсуждения иасг и ге1еаве.
12.3.2. Синхронизация взаимодействия В большей части этой главы мы рассматриваем пример совместно используемого буфера для иллюстрации различных подходов к синхронизации взаимодействия и синхронизации конкуренции. Для синхронизации взаимодействия такой буфер должен иметь возможность определить и количество пустых позиций, и количество заполненных позиций в буфере. Это можно сделать с помощью счетчика, являющегося компонентом переменной семафора.
Одну переменную семафора, скажем ежрсуаросв, можно использовать для хранения числа пустых ячеек в совместно используемом буфере, а лругую, скажем Еи11лрогв, — для хранения количества заполненных ячеек в буфере. Очереди задач в этих двух семафорах хранят задачи, которые были заблокированы соответствующим семафором с помощью операции задержки. Наш буфер разработан как абстрактный тип данных, в котором все данные входят в буфер через подпрограмму 0ЕРОЯ1Т, а удаляются из него через подпрограмму РЕТСН.
Поэтому подпрограмма 0ЕР051Т нуждается только в проверке семафора елзрсуврогв, чтобы определить, есть ли в буфере пустые позиции. Если есть хотя бы одна, ее можно передвинуть вперед подпрограммой 0ЕРОЯТТ, которая должна содержать операцию уменьшения значения счетчика переменной ежрсуяросв. Если буфер полон, задача, вызвавшая подпрограмму 0ЕРОЯ1Т, должна подождать, пока в очереди переменной еврсувроса не станет доступной какая-либо пустая ячейка. Когда выполнение подпрограммы 0ЕР051Т завершается, она увеличивает значение счетчика семафора 1ц11я росв, чтобы отметить, что в буфере стало на одну заполненную ячейку больше.
Подпрограмма РЕТСН действует прямо противоположным образом по отношению к подпрограмме 0ЕР051т. Она проверяет семафор гц11арогл, чтобы обнаружить, содержит ли буфер хотя бы одну заполненную ячейку. При положительном ответе содержимое этой ячейки извлекается из нее, и счетчик семафора еврсулросл увеличивается на 1. Если буфер пуст, то вызывающий процесс помещается в очередь семафора Ти11ароса и ожидает, пока не появится заполненная ячейка. Когда подпрограмма РЕТСН заканчивает свою работу, она должна увеличить значение счетчика семафора еврг уз роса. Операции с семафорами часто не являются прямыми — они выполняются через подпрограммы ожидания и подпрограммы освобождения.
Вследствие этого только что описанная операция 0ЕР051Т частично выполняется с помощью вызовов подпрограмм иааг и ге1еаве. Заметим, что эти подпрограммы должны иметь доступ к очереди задач, готовых к пуску. Для проверки счетчика заданной переменной семафора используется подпрограмма иаяс. Если это значение больше, чем О, вызывающая задача может выполнять свою операцию. В этом случае значение счетчика переменной семафора уменьшается, лля того чтобы отметить тот факт, что сущностей, количество которых он хранит, стало на одну меньше. Если значение счетчика равно О, вызывающая задача должна быть помещена 512 Глава 12. Параллальность в очередь ожидания, являющуюся компонентом данной переменной семафора, а процессор слелует предоставить в распоряжение другой задачи, готовой к пуску.
Для того чтобы открыть другой залаче доступ к сущностям, количество которых хранится в счетчике указанной переменной семафора, используется операция ге1еазе. Если очередь данной переменной семафора пуста, т.е. нет ожидающих пуска задач, то подпрограмма ге1еазе увеличивает значение своего счетчика (чтобы отметить тот факт, что количество управляемых сущностей, доступных в данный момент, увеличилось на единицу).
Если есть одна или несколько задач, ожндщоших пуска, то подпрограмма ге1еазе перемещает одну из них нз очереди семафора в очередь готовности. Ниже приводится точное описание подпрограмм набг и ге1еазе. на1Г(аЯещарпоге) дб счетчик переменной аЯешарпоге > О сЬеп уменьшить счетчик переменной аЯешарпоге в1ве поместить вызывающую задачу в очередь переменной аЯешар)тоге попытаться передать управление другой готовой к пуску задаче (Если очередь задач, готовых к пуску, пуста, возникнет взаимная блокировка) епс$ ге1еазе(аЯешар)зоге] ЕЕ очередь переменной аЯещарпоге пуста (нет ни одной ожидающей задачи) ЕЬеп увеличить счетчик переменной аЯещар)зоге е1ве поместить вызывающую задачу в очередь задач, готовых к пуску передать управление задаче из очереди переменной аЯещарпоге ° пс( Теперь мы можем привести пример программы, осуществляющей синхронизацию взаимодействия для совместного использования буфера.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
