Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 142

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

Текст из файла (страница 142)

Соединение стека вновь инициированной задачи со стеком той программной единицы, в которую эта задача статически вложена, должно поддерживаться во время выполнения програмл!ы, поскольку задача может иметь нелокальные ссылки на совместно используемые данные в стеке программной единицы. Таким образом, должна поддерживаться некоторая связь, например указатель статической цепочки, которая позволит правильно разрешить эти нелокальные ссылки во время выполнения программы. Задача ! Рис. ! !.4.

Модель стека-кактуса дпв нескольких задач Взаимное исключение. Если две задачи А и В имеют доступ к одному и тому же объекту данных Х, то они должны синхронизировать свой доступ к Х таким образом, чтобы задача А не могла присвоить новое значение обьекту данных Х в тот момент, когда задача В ссылается на него или присваивает ему другое значение. Например, если значение переменной Х равно 1 и задача А выполняет оператор !Г Х > О !Пел Х:- Х + 1, а В выполняет оператор !Г Х > О тьеп К - Х - 2; то окончательное значение Х может оказаться либо О (если сначала выполняется Р), либо -1(если сначала выполняется В), либо, возможно, 2 (если случится так, что 514 Глава 11. Распределенная обработка данных А и В будут чередовать свои действия в попытке выполнить оба оператора одновременно).

Чтобы можно было гарантировать, что две задачи не станут предпринимать одновременных попыток доступа к совместно используемому объекту данных, одна из них должна обладать исключительным правом доступа к объекту данных во время его обработки. Существует несколько различных способов решения проблемы взаимного исключения, когда задачи работают с совместно используемыми данными. В разделе 11.2 мы уже обсуждали семафоры и атомарность, которые можно использовать для синхронизации данных. Далее будут рассмотрены другие механизмы. Критические области Критическая область — это последовательность операторон в задаче, в которой осуществляетсяя обработка некоторого объекта данных, используемого совместно с другимии задачами. Если критическая область задачи А обрабатывает объект данных М, то принцип внутреннего исключения требует, чтобы никакая другая задача нс выполняла одновременно с А свок1 критическую область, в которой обрабатывается тот же самый объект Х.

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

Монитор Другим способом реализации взаимного исключения является использовациемонитора. Мои из ар — зто совместно используемый объект данных вместе со множеством операций, которые могут пм манипулировать. Таким образом, монитор аналогичен объекгу данных, определяемому прп помощи абстрактного типа данных„ как описано в разделе 6,2. Задача может манипул яровать совместно используемым объектом данных только с помощью определенных операций, так что объект данных является инкапсулированным, как это обычно и происходит с объектами данных, определяемыми с использованием абстрактных типов данных. Для того чтобы реализовать взаимное исключение, необходимо лишь потребовать, чтобы в любой момент нрсмспп можно бьщо выполнять нс более одной операции, определенной для этого объекта данных.

Треоованпя для взаимного исключения и инкапсуляции в мониторе позволяюз. сстсствсшпям образом представить его в виде задачи. Совместно используемь~й объект данных представляется локальным обьектом данных для этой задачи, а операции определяются как локальные подпрограммы задачи.

К примеру, предположим, что совместно используемый объект данных — это табл и па В1 оТа1! е н для нес определены две опер шип, Ел1егйех11еп~ н Г1пп11еп, Для того чтобы одна из задач не пыталась изгяенить значение некоторого элемента в таблице в тот момщгг, когда 11.2. Параллельное программирование 515 другая задача пытается получить значение этого же элемента, необходимо взаимное исключение. В Аба монитор может быть представлен как задача ТаЫ еМападег с двумя точками входа, Ептегйеи[сеп и Е) О[[[топ (листинг 11.2).

В пределах этой задачи В) дТаЫ е является локальной переменной. Оператор эе1 ест с двумя вариантами ассерс используется для того, чтобы позволить монитору отвечать на запросы других задач на выполнение одной нз двух операций, Ептегцеы![ел) или Е)па[[топ, таким образом, что в любой момент времени будет выполняться только одна из ннх.

Двум задачам может одновременно потребоваться ввод или поиск каких-либо элементов таблицы. Например, задача А может выполнить оператор абра)цения к одной точке входа Елдегыеы[деш[...) а задача В может в тот жс момент обратиться к другой точке входа: Езлс[деш[ Первое, полученное задачей Тап1еМаладег обращение к точке входа начинает обрабатываться (то есть происходит рандеву, как описано в разделе 11.2). Если второй оператор обращения к точке входа выполняется до того, как задачей ТаЫ еМападег обработан псрвый, то вторая задача должна дождаться окончания его обработки. Таким образом, таблица В) дТаЫе защищена от одновременного доступа из двух различных задач. Листинг 11.2.

Представление монитора в виде задачи Ад[а Садк ТаЫ еналадег 1в епвгу Епсегмеы!дел[...); елвгу Емли!дел[.. ). елб. Савв воду !аЫ еМаладег 1э ВздТаЫе аггау [ . ) аг ргосебцге Елдег[ . ) 1э - Олерагоры для ввода элемента в ВздтаЫ е ела Елтег: тцлсвзал Езло[ .) гедцглв ... зз - Операторы для поиска элеиенма в В|дтаЫ е еле Езлб, Ьедзл - Операторы для инициализации ВздТаЫ е 1оор - Бесконечный цикл для обработки [очем входа зе)вод ассврд Елдегнеы![еш[. ,) Со — Вызов Елтег для ввода полученного элененза в ВздТаЫ е еле; ог ассерт Езпб!сев[. .) бо - Вызов Езго для поиска зал"ошенного элеменга в ВздТаЫ е ела; ело эе)ест елб 1оор ела ТаЫеМападег; Передача сообщений Другим решением проблемы совместного использования данных задачами является запрещение использования общих обьектоы данных, а предоставление использования только зличелцй таких объектов — путем передачи их в виде сообще- 616 Глава 11, Распределенная обработка данных ний.

Это та же самая концепция сообщений, которая уже обсуждалась ранее в связи с синхронизацией задач. Использование передачи сообщений в качестве основы совместного использования данных гарантирует взаимное исключение без применения какого-либо специального механизма, поскольку каждый объект данных принадлежит в точности только одной задаче и никакая другая задача не может получить к нему непосредственный доступ. Если некий объект данных принадлежит задаче А, то она посылает копию значений, хранящихся в этом объекте данных, на обработку задаче В, Теперь в В имеется своя локальная копия этого объекта данных.

Когда В завершит обработку своей локальной копии этого объекта, она перешлет копию с новыми значениями обратно в А, и затем А изменит фактический объект данных. Разумеется, задача А может продолжать изменение фактического объекта данных, пока В изменяет свою локальную копию. 11.3. Развитие аппаратной части компьютера Одним из способов, позволяющих решать па компьютере более сложные задачи, является увеличение скорости его работы. Хотя в настоящее время компьютеры становятся все более быстродействующими (приблизительно каждые два года скорость увеличивается вдвое), основная проблема все же остается.

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

Характеристики

Список файлов книги