|
| |
 |
Главная » Мануалы 1 ... 7 8 9 10 11 12 13 ... 32 {з} Упооядоченные взаимные вызовы и приемы. {6} Взаимнь(е вызовы, один из KoropbfJC условный  (в) Пара односторонних вызовов [г) Задача-курьер, действующая в одном направлении.  {0) Де задачи-курьеры, одной на каждое направление* i?) Одна задача-курьер, общая для двух направлений (ж) Единстаеиная буферизующая задача <t6  (з) Индивидуальная буферизующая задача для каждйгв адресата. Рис. 3.21. Структуры двусторонних взаимодействий. редоваться. Этот подход накладывает, однако, слишком жесткие ограничения. Другой метод предотвращения непосредственного цикла на структурном графе состоит в использовании однонаправленного условного вызова входа. Такой метод достаточно прост, но требует дополнительных логических ветвей, обеспечивающих принятие решений о том, что делать, если вызов не состоялся, и как часто следует повторять вызовы. Система в целом тоже концептуально усложняется, поскольку возврат из рандеву еще не означает, что конкретная работа выполнена. Кроме того, в этом методе используется особая возможность языка Ада - условный вызов входа; существуют, однако, другие достаточно хорошие методы предотвращения тупиков, не требующие принятия этой крайней меры. В соответствии с кисс-принципом при желании использовать язык Ада для проектирования систем вполне естественно стремление к поиску каких-то других решений, которые могут оказаться более предпочтительными. На рис. 3.21,0 отдельные рандеву одного направления используются для передачи данных в противоположных направлениях. Сбор сообщений в данном случае может осуществляться путем организации последовательного опроса или условного ожидания, однако ни один из этих методов, вообще говоря, не дает удовлетворительных результатов. В варианте, представленном на рис. 3.21, г, предусматривается рандеву в обоих направлениях, а во избежание тупиковой ситуации в одном из направлений используется задача-курьер. Отправитель осуществляет прием вызовов от этой вспомогательной задачи в конкретном направлении только тогда, когда у него есть сообщение для передачи. В противоположном направлении отправитель обращается ко второй задаче непосредственно. Такое решение приемлемо, если только непосредственное взаимодействие между двумя основными задачами не приводит к нежелательным помехам работе вызывающей задачи, Следовательно, вызов не должен включать условное ожидание. Преимущество данного подхода по сравнению с рассматриваемым ниже заключается в использовании меньшего количества задач, а недостаток в том, что он дает асимметричное решение симметричной проблемы. На рис. 3.21, для развязки тупиковых ситуаций используются две задачи-курьеры, по одной в каждом направлении; обе они находятся в состоянии условного ожидания сообщений для передачи. Такое решение оказывается более гибким, поскольку не накладывает никаких ограничений на основные задачи в отношении их взаимодействий с другими задачами; кроме того, вспомогательные задачи-курьеры позволяют, как всегда, минимизировать помехи работе обслуживаемых ими основных задач. На рис. 3.21, е имитируется механизм взаимодействий, часто встречающийся в организационных системах, когда передача сообщений ведется пакетами, поскольку немедленная их доставка не требуется, а стоимость передачи играет существенную роль. В данном случае единственная задача-курьер собирает и передает пакеты сообщений в обоих направлениях по фиксированному графику без введения условного ожидания. Если интенсивность взаимодействий в обоих направлениях высока, одна такая вспомогательная задача, обслуживающая оба направления по установленному расписанию, обеспечивает такой же эффект, как и две задачи (по одной на каждое направление), работающие по одинаковому графику. Сомнительно, однако, чтобы в машинных программах могли возникнуть ограничения, которые приводили бы к необходимости пакетной передачи сообщений. Организация взаимодействий с использованием задач-курьеров ведет к большей гибкости, но при некоторых обстоятельствах имеет два дефекта: количество требуемых задач-курьеров пропорционально числу взаимодействующих пар, а оно может быть довольно велико, если каждая задача контактирует с множеством других; если интенсивность взаимодействий высока, задаче-отправителю или задаче-адресату может понадобиться буфер. Чтобы избавиться от этих дефектов (как в случае двусторонних, так и односторонних взаимодействий), можно прибегнуть к буферизующей задаче, описанной в подразд. 3.3.4, немного проигрывая при этом в гибкости. Рис. 3.21, г и 3.21, з иллюстрируют методы, аналогичные соответствующим методам для односторонних взаимодействий, за тем исключением, что вступающие во взаимодействие задачи могут быть как отправителями, так и адресатами. Связанная с этим проблема утраты необходимой гибкости уже обсуждалась в подразд. 3.3.4. Что касается соображений эффективности, то в обоих методах (с буфером и с задачей-курьером) для передачи данных между парой исходных задач требуется одинаковое количество рандеву. Однако впечатление об одинаковой эффективности несколько обманчиво, поскольку иногда при использовании метода с задачей-курьером происходит больше переключений с одной задачи на другую по той простой причине, что задач больше. Структуры многосторонних взаимодействий между большим числом задач можно соответствующим образом компоновать из структур попарных взаимодействий, приведенных на рис. 3.21. Следует избегать произвольного установления различных структур взаимодействий для одного и того же набора задач. Такие неоднородные комбинации могут содержать скрытые тупиковые ситуации как следствие недопустимых сочетаний обращений к входам и защитных блокировок, даже если структурный граф не содержит циклов. Пример такого тупика уже бйл приведен на рис. 3.20, в. Читателю предлагается в качестве упражнения показать, что наличие различных структур взаимо- 4 Зак. 453 действий для конкретных наборов задач может приводить к тупиковым ситуациям, связанным с зацикливанием в состоянии ожидания. 3.3.6. Управление потоками данных между задачами Мы теперь знаем, каким образом одни задачи передают сообщения другим и сами ждут от них сообщений в условиях использования разнообразных стандартных структур взаимодействий. Попутно нам удалось установить, что задача-отправитель может иногда оказаться заблокированной из-за нехватки места в памяти для передаваемого сообщения. Впервые мы встретились с возможностью такой ситуации в первом примере организации прохождения задач в гл. 2 при рассмотрении буферизующей задачи; там блокировка осуществлялась путем защиты входа WRITE. Подобная защита - это один из способов, используемых задачей-адресатом для управления входящим потоком сообщений. Однако возможны и другие способы, которые описываются ниже. Вызывающие задачи-адресаты управляют входящим потоком очень просто; они не обращаются за получением сообщений; что же касается вызываемых задач-адресатов, то они сталкиваются с более сложными проблемами. В общем случае вызываемый адресат имеет следующие возможности управления: заблокировать пересылаемый объект путем установки предохранителя на входе задачи-отправителя; заблокировать пересылаемый объект в процессе рандеву, не приняв его, но освободив задачу-отправитель от ожидания; . отбросить пересылаемый объект уже в ходе рандеву; осуществить вызов потенциальных отправителей с целью уведомления их о том, что установлен контроль над входящим потоком сообщений; о заблаговременно выдать отправителям разрешение (предоставить кредит ) на передачу сообщений. В трех первых методах предполагается, что отправитель должен сначала попытаться передать сообщения, а затем, если потоки информации контролируются, быть готовым к ожиданию или отказу в приеме; при этом его ресурсы расходуются нерационально, и часть информации может теряться. Четвертый метод также нельзя считать подходящим потому, что уведомление может не прийти вовремя, и, кроме того, одновременные обращения задач могут привести к тупиковой ситуации. Пятый метод, предполагающий заблаговременную выдачу разрешения, имеет некоторые преимущества, поскольку при та- КОЙ организации взаимодейст0ИЙ отправителю гарантировано, что пересылаемые им сообщения не будут заблокированы, а адресату-что поступающие сообщения всегда можно будет принять. В простейшей форме разрешение реализуется посредством счетчика, показывающего, сколько сообщений может в данный момент принять адресат. При этом отправитель не должен превышать выданный ему текущий кредит . Если же кредитный лимит исчерпан, отправитель должен ждать предоставления ему дополнительного кредита^ и только после этого сможет продолжать пересылку сообщений. Как же необходимо организовать взаимодействия между отправителем и адресатом, 4fo6bi кредитный лимит использовался эффективно? Это определяется выбором подходящей стандартной структуры межзадачных взаимодействий, ряд вариантов которой отображен на рис. 3.22. Если взаимодействия осуществляются непосредственно или через задачу-курьер, то можно использовать подходы, иллюстрируемые на рис. 3.22, а-б, гДе предполагается, что пока кредитный лимит не исчерпан, он передается в качестве выходного параметра входа SEND (ОТПРАВКА) (начальное значение кредита можно получить, обратившись к входу SEND и передав некоторое нулевое фиктивное сообщение). Различие этих двух подходов заключается лишь в разных способах получения дополнительного кредита после того, как полученный через вход SEND кредитный лимит будет исчерпан. После предоставления кредита адресат мол^ет сам вызвать отправителя (рис. 3.22,а); при этом тупиковой ситуации не будет благодаря фиксированйому порядку чередования операторов вызова и приема. Однако возникнет чересчур тесная (и, следовательно, нарушающая принцип модульности) завязка отправителя и адресата. На рис. 3.22, б отображен случай, когда адресат может иметь отдельный защищенный вход ASK-CREDIT (ЗАПРОС КРЕДИТА), через который отправитель может ждать получения дополнительного кредита после отправки некоторого сообщения по исчерпании кредитного лимита. Если же отправитель не может находиться в состоянии ожидания, для этой цели возможно введение задачи-курьера. При организации взаимодействий на основе использования буферизующих задач больше всего подходит структура, показанная на рис. 3.22, е, где вхоДЫ PUT могут обслуживать сразу нескольких отправителей, а каждый вход GET - ровно одну задачу-адресат, которая является владельцем данной буферизующей задачи. Каждый отправитель может одновременно быть и адресатом.  (а) Непосредственные взаимные вызовы . Задача отправитель (или задача-курьер).  !Ь / 1 <-*-- /ПкредТт^й лими-и^/ егпи он есть (6) Отдельный вход ASK. CREDIT в задаче-адресате . Буфер отправителя Буфер адресата  Сообщение Кредит (в, Предоставление кредита через буферизующие задачи. Рис. 3.22. Структуры межзадачных взаимодействий при управлении потоками информации путем выделения кредитных лимитов. 3.3.7. Наборы задач, объединенные в пакет: активные пакеты Как уже упоминалось при рассмотрении работы обычного учреждения в качестве аналога процедур параллельного программирования, часто бывает желательно трактовать совокупность задач, обслуживающих некоторые другие задачи, как активный пакет, выполняющий сервисные функции. Подобные активные пакеты могут быть тех же типов, что и задачи, т. е. могут выполнять роль подчиненных, исполнителей, секретарей, агентов, курьеров и т. п. (см. подразд. 3.3.1). Однако, как будет видно из дальнейшего, они выполняют и некоторые новые функции, например могут играть роль бюро обслуживания. Методы использования активных пакетов можно без излишних подробностей проиллюстрировать на простом примере, взятом из жизни. Рассмотрим очередь клиентов, ожидающих обслуживания каким-нибудь кассиром в банке. Стандартное решение проблемы состоит в том, чтобы организовать одну общую очередь и распределять затем клиентов между конкретными окошками. Здесь будет описан один частный метод, при котором клиенты стоят в очереди к окошку диспетчера, а тот сообщает им фамилию (номер окошка) свободного кассира. Клиент переходит затем к назначенному ему окошку и получает от кассира требуемую услугу. В данном слз^чае диспетчер управляет единственной очередью клиентов. Каждый кассир информирует его о том, что он свободен, и сообщает номер своего окошка для передачи его клиенту Клиенты ожидают, пока им сообщат номер окошка, и переходят затем к соответствующему окошку за получением услуг. Рассмотренный пример упрощенно представлен на рис. 3.23 в форме структурных графов с использованием терминов языка Ада, причем более сложные элементы организации прохождения задач на рисунке не отобрал<ены (это будет сделано в гл. 5). На рис. 3,23, а и 3.23,6 задачи и пакет банковских услуг представлены в форме структурного графа. Клиент, диспетчер и кассиры - это задачи, а банк-активный пакет, предоставляющий клиентам услуги, реализуемые с помощью процедур. Диспетчер выполняет функции планировщика, а кассиры - функции подчиненных, которых их начальник (диспетчер) назначает на выполнение работы для клиентов. Предполагается, что для этого они взаимодействуют с другими задачами, решаемыми в банке, но не показанными на рисунке; если это не так, то нет никакой необходимости уподоблять кассиров задачам. Очередь на входе WAIT (ОЖИДАНИЕ), принадлежащем диспетчеру (рис. 3.23,6), является очередью для клиентов. Задача-диспетчер принимает обращение к входу WAIT только после рандеву со свободным кассиром, вызвавшим вход READY (ГОТОВ). Таким образом он организует цикл, принимая поочередно обращения к входам READ и WAIT и назначая на каждом цикле одному клиенту по одному кассиру. Кассиры работают в своем цикле, поочередно вызывая вход READY и принимая обращение к входу ASK (ЗАПРОС). Каждый кассир знает номер своего окошка и сообщает его диспетчеру, как только освобождается. Предполагается, что каждый клиент, получив номер окошка, немедленно вызывает вход ASK, принадлежащий соответствующему кассиру, посредством процедуры REQUEST-SERVICE (ОТСЛУЖИВАНИЕ ЗАПРОСА). Если он этого не сделает, то произойдет ошибка, в результате которой кассир окажется заблокированным. Таким образом, клиенту, вызвавшему процедуру REQU-EST TELLER (ЗАПРОС-КАССИРА), может быть придется ожидать возврата из процедуры WAIT. Возможно, самому диспетчеру тоже придется ждать обращения к входам WAIT или READY. Кассир может ожидать возврата из процедуры READY, а затем ладать обращения к входу ASK. На рис. 3.24 приведен скелет Ада-программы, соответствующей построенным структурным графам. Заметьте еще раз, насколько полно структурный граф помогает выработать концептуальное представление принципов организации и функционирования программы. Для этого скелет программы на самом деле совсем не нужен. Обсуждение решений в ходе проектирования можно вести исключительно в терминах структурного графа. Программа необходима только для того, чтобы определить некоторые детали, например метод идентификации задач-кассиров, который в данном случае предельно прост: каждой такой задаче присвоен собственный номер окошка, инициализируемый до начала выполнения программы. Этот номер передается от задачи к задаче, как показано на рисунках, и используется на конечном этапе в операторе отбора для определения нужного кассира. Более совершенные способы определения и идентификации пулов задач рассматриваются в гл. 5. Для полноты представлений на рис. 3.25 приведены опущенные подробности скелета программы. Тела задач, замененные в теле пакета BANK (БАНК) заглушками, здесь определены во всех деталях. Хотя в данном конкретном примере взаимодействия кассиров с пакетами и задачами, внешними по отношению к их собственному пакету, не показаны, в реальной жизни они встречаются повсеместно. В общем случае активные пакеты Задача CUSTOMER Иаентифицирует окошко кассира Пакет BANK 
Задача TRANSPORTER Для нетерпеливых КЛИЕНТОВ, которые не могут терять время на ожидание в БАНКЕ (а) Структурный граф, иллюстрирующий внешний вид активного банковского пакета Пакет BANK NAME NAME О- REQUEST-TELLER  ask3 / TELLERS г NAME 16) Структурный граф, иллюстрирующий внутренние детали банковского пакета. Рис. 3.23. Активный пакет на примере банковских операций. могут не только быть вызываемыми, но и сами способны вызывать другие модули. Конкретный тип активных пакетов, проиллюстрированный на этом примере, можно назвать сервисным пулом. Сервисный пул - это активный пакет, который предоставляет отдельным package BANK is type T TYPE is (DEPOSIT, V/ITHDRAW, CHECK ACCOUNT, PAY BILU; type RETYPE is ...--ЗДЕСЬ ПЕРЕЧИСЛЯЮТСЯ РЕЗУЛЬТАТЫ; type WICKET is integer range 1 .. 3; procedure REQUEST TELLER (NAME : out WICKET; procedure REQUEST SERVICE (NAME : in WICKET; TRANSACTION : in T TYPE; RESULT : out R TYPE); end BANK; package body BANK is NAME ; WICKET; task TEULER1 is entry ASKfTRANSACTION : in T TYPE; RESULT : out R TYPE); endTELLERI; task body TELLER 1 is separate; task TELLER2 is task TELLERS is task DISPATCHER is entry WAIT ( NAME : out WICKET); entry READY ( NAME : in WICKET); end DISPATCHER; task body DISPATCHER is separate; procedure REQUEST TELLER ( NAME ; out WICKET) is begin DISPATCHER.WAIT ( NAME ); end REaUEST TELLER; procedure REQUEST SERVICE ( NAME : in WICKET; TRANSACTION.: in T TYPE; RESULT ; out R TYPE; begin case NAME is when 1 = > TELLER1.ASK (TRANSACTION, RESULT); when 2 = > TELLER2.ASK (TRANSACTION, RESULT); when 3 =- > TELLER3.ASK (TRANSACTION, RESULT); end case; end REaUEST SERVlCE; end BANK; Рис, 3.24. Банковский пакет, содержащий следы задач (заглушки). вызывающим задачам услуги одной из ряда идентичных обслуживающих задач. Как будет видно из последующих глав, активные пакеты можно использовать так же, как транспортное средство дауна- 1 ... 7 8 9 10 11 12 13 ... 32 |