Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 132
Текст из файла (страница 132)
12.2. Введение в параллельность на уровне подпрограмм Прежде чем обсудить поддержку параллельности в языках программирования, введем основные понятия параллельности и условия, при которых она становится полезной. Затем рассмотрим вопросы разработки языков, поддерживающих параллельность. 12.2.1. Рсновные понятия Задача Вазк) — это модуль программы, который выполняется параллельно с другими частями той же самой программы.
Каждая задача в программе обеспечивает один поток управления. Есть три свойства задач, отличающие их от подпрограмм. Во-первых, выполнение задачи может начинаться неявно. в то время как подпрограмма должна вызываться явно. Во-вторых, когда программный молуль вызывает задачу, он не обязан ожидать завершения выполнения задачи лля того, чтобы продолжить свою работу. В заключение, после завершения выполнения задачи управление может возвращаться, а может и не возвращаться в модуль, вызвавший это выполнение. Задача полдерживает связь с другими задачами через совместно используемые нелокальные переменные, передачу сообщений или параметры. Если задача не подаерживает 507 12.2.
Введение в параллельность иц уровне подпрограмм связи с другими задачами и никогда не вызывает выполнения никакой другой задачи. она называется отдельной (йз)о(пг). Поскольку задачи часто работают совместно при моделировании и других вычислениях и вследствие этого не являются отдельными, они должны использовать некоторые вилы связи либо для синхронизации своего выполнения, либо для совместного использования данных, либо лля того и другого одновременно. Синхронизация (зупсйгоп!гаг!оп) — это механизм, управляющий порядком выполнения задач.
При совместном использовании данных, а также когда задачи взаимодействуют друг с другом или конкурируют межлу собой, нужны два вида синхронизации. Синхронизация взаимодействия (соорегайоп зупспгоп(айаг(оп) между задачами А и В требуется, когда задача А должна ожидать, пока задача В закончит выполнение определенных действий, прежде чем задача А сможет продолжить свою работу. Синхронизация конкуренции (со~враг(г(оп зупсйгощгабоп) межлу двумя задачами необходима, когда обе задачи нуждаются в использовании некоторого ресурса, который невозможно использовать олновременно. В частности, если залача А нуждается в получении доступа к совместно используемой ячейке х в то время, котла эта ячейка находится в распоряжении задачи В, то задача А должна ожидать, пока задача В не закончит обработку ячейки х, независимо от того, что именно представляет собой зта обработка.
Итак, гази синхронизации взаимодействия задачам, возможно, придется ожидать завершения некоторой обработки, от которой зависит их правильное выполнение, в то время как при синхронизации конкуренции задачам, возможно, придется ожилать завершения любой другой обработки совместно используемых данных, выполняемой в данный момент любой другой задачей. Простую форму синхронизации взаимодействия можно проиллюстрировать с помощью широко распространенной задачи "производитель-потребитель". Эта задача возникла при разработке операционных систем, в которых один программный модуль вырабатывает некоторые данные или ресурс, а другие используют их. Эти данные обычно помещаются в буферной памяти вырабатывающим их модулем и удаляются из нее получающим их модулем.
Последовательность операций размещения данных в буферной памяти и удаления их отгула должна быть синхронизирована. Модулю-потребителю необходимо запретить извлекать данные из буфера, если буфер пуст. Аналогично, модуль- производитель не может помешать данные в буфер, если тот полон. Это приводит к задаче синхронизации взаимодействия, поскольку пользователи совместно используемых структур данных должны координировать свои действия, для того чтобы буферная память использовалась корректно. Синхронизация взаимодействия предотвращает ситуацию, когда две задачи обращаются к совместно используемой структуре данных точно в одно и то же время, что может разрушить целостность этой структуры.
Чтобы обеспечить синхронизацию конкуренции, должен быть гарантирован взаимно исключающий доступ к совместно используемым данным. Чтобы пояснить задачу синхронизации конкуренции, рассмотрим следующий сценарий. Предположим, что задача А должна добавлять 1 к совместно используемой целочисленной переменной ТОТА!., имеющей начальное значение 3. Кроме того, задача В должна умножать значение переменной ТОТАВ на 2. Каждая задача выполняет свою операцию с переменной ТОТАЬ, извлекая ее значение, производя арифметическую операцию и помещая новое значение назад в переменную ТОТАВ.
Без синхронизации конкуренции зти операции могут привести к трем разным результатам. Если задача А завершит свою операцию перед началом задачи В, то результат будет равен 8, что считается 508 Глава ! 2. Параллельность правильным ответом. Но если обе задачи А и В извлекут значение переменной СОТА!. до того, как одна из них присвоит ей новое значение, то результат окажется неправильным.
Если задача А вернет свой результат первой, то значение переменной ТСТА!. будет равно б. Этот случай показан на рис. 12.1.. Если задача В вернет свой результат первой, то значение переменной ТОТА!. будет равно 4. Важность синхронизации конкуренции должна быть теперь очевидной. Зинченко переменной тотл Задача А Выбрать тотл Сояанить тотл добееить 1 Ведите й СохРанить тотл Выбрать тоти.
Умножить не 2 Время Рис. П. А Необходиттость синхронизации конлурентттттт 2. Состояние пуска или готовности к пуску. Запускаемая задача готова к пуслу, но в данный момент не выполняется. Она либо еше не получила процессорное время от 509 12.2. Введение а параллельность иа уровне подпрограмм Общий полхол к обеспечению взаимно исключающего доступа к совместно используемому ресурсу заключается в том, что этот ресурс рассматривается как сушность. которая одновременно может принадлежать только одной задаче. Чтобы получить право владения совместно используемым ресурсом, задача должна запросить его.
Завершив свое выполнение, задача должна освободить ресурс, чтобы он стал доступен другим задачам. Три метода обеспечения взаимно исключаюшего доступа к совместно используемым ресурсам — это семафоры, обсуждаемые в разделе 12.3; мониторы. описанные в разделе! 2.4; и передача сообшений, рассматриваемая в разделе 12.5, Механизмы синхронизации должны иметь возможность задерживать выполнение задач. Синхронизация устанавливает порядок выполнения задач, определяемый этими задержками. Чтобы понять, что происходит с задачами во время их существования, рассмотрим, как осушествляется управление выполнением задачи.
Независимо от того, сколько процессоров имеет машина, всегда сушествует возможность того, что задач больше, чем процессоров. Программа, называемая планировщиком (зс!тедц1ег). управляет распределением процессоров между задачами. Если не происходит никаких прерываний и все задачи имеют одинаковый приоритет, то планировшик просто предоставляет каждой задаче некоторый отрезок времени, например, 0,1 с. Когда подходит очередь какой-либо задачи, планировщик позволяет процессору выполнять ее в течение некоторого времени.
Конечно, есть несколько осложияюших ситуацию факторов, например, синхронизируюшие задержки и ожидание операций ввода и вывода. Задачи могут находиться в нескольких описанных ниже состояниях. !. Новое состояние. Задача находится в новом состоянии, когда она уже созлана, но ее выполнение еше не началось. планировшика, либо была ранее запущена, но затем заблокирована одним из способов, описанных ниже в пункте 4. Задачи, готовые к пуску, помешаются в очередь, которую часто называют очередью задач, готовых к пуску (шзй геаду ацеце). 3.
Текушее состояние. Текущая задача — это задача, выполняемая в данное время, т.е. процессор предоставлен в ее распоряжение, и в данный момент выполняется именно ее код. 4. Заблокированное состояние. Заблокированная задача — это задача, которая была ранее запушена, но ее выполнение было прервано вследствие одного нли нескольких различных событиЯ (в основном, из-за операции ввода или вывода). Поскольку операции ввода и вывода выполняются намного медленнее, чем сама программа, задача, начинаюшая такие операции, блокируется, н ей запрещается использовать процессор до тех пор, пока операции ввода-вывода не будут завершены.
В дополнение к этим видам блокировки некоторые языки поддерживают операции, позволяющие пользовательской программе самой определять, какую именно задачу заблокировать. 5. Пассивное состояние. Пассивная задача больше не является активной ни в каком смысле. Задача становится пассивной после своего завершения. В некоторых языках залача может переЯти в пассивное состояние в результате явного требования пользовательской программы, например, при вызове метода а Сор в языке )ача. Важный вопрос при выполнении задачи заключается в следующем; какую именно задачу перевести из состояния готовности в текушее состояние в момент, когда задача, являюшаяся текущей, заблокирована, или ее отрезок времени истек? Этот выбор можно сделать с помощью нескольких алгоритмов, некоторые их которых основаны на определении уровней приоритета.
Алгоритм выбора реализуется планировшиком. С параллельным выполнением задач и использованием обших ресурсов связана концепция живучести. В среде последовательных программ некоторая программа облалает свойством живучести (йчепезз), если ее выполнение всегда продолжается и завершается нормальным образом. В обшем смысле живучесть означает следующее: если предполагается, что некоторое событие (скажем, завершение выполнения программы) должно состояться, то оно в конце концов обязательно состоится, Это означает также, что процесс выполнения задачи осушествляется непрерывно.
В среде параллельного выполнения прсирамм и использования обших ресурсов живучесть залачи может исчезнуть, т.е. выполнение программы нельзя будет продолжить, и, таким образом, она никогда не завершится. Предположим. что задачи А и В нуждаются в совместно используемых ресурсах Х и У для завершения своей работы. Далее, предположим, что задача А получает право на обладание ресурсом Х, а задача В получает право на обладание ресурсом у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
