Главная » Мануалы

1 ... 27 28 29 30 31 32

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

Подход, основанный на динамическом порождении задач позволяет избежать ненужного связывания ресурсов памяти хранением контекстных таблиц и стеков незанятых задач. При таком подходе для организации доступа задачи ROUTER IN к задачам VCM необходимо, чтобы в задаче-диспетчере велась специальная таблица, содержащая ссылочные переменные этих задач.

Когда задача VCM прекращает свою работу, задача-диспетчер должна уведомляться о том, что данный канал свободен; тогда при повторном использовании того же канала для управления им можно будет создать новую задачу; следовательно, все задачи VCM должны обращаться к входу задачи-диспетчера DISPATCHER FREE (КАНАЛ-СВОБОДЕН). Более того, теперь мы должны принять ранее отвергнутую схему взаимодействий, в соответствии с которой задача ROUTER IN пересылает входящие пакеты с запросами на установление соединения диспетчеру.

Необходимо позаботиться также, чтобы задача ROUTER-. IN не делала попыток получить доступ к задаче VCM, уже закончившей работу. Однако, как будет показано ниже, подобная ситуация может все же возникнуть из-за состязания между этими двумя задачами. Задача ROUTER-IN могла получить ссылочную переменную, указывающую на некоторую задачу VCM, в промежутке времени между уведомлением диспетчера об освобождении канала и завершении ее собственной работы, и моментом, когда диспетчер обновляет свою внутреннюю таблицу. Указанная проблема, конечно, может быть решена, но ценой увеличения сложности системы; при этом возможны два пути ее решения:

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

В каждую задачу, которая может иметь рандеву с задачей VCM, включить локальный блок обработки исключений, который позволит обнаруживать эти ошибочные

/put / /рцу/

Рис. 7.8. Неиерархическая структура пакета, полученная из иерархической структуры путем ее реорганизации.

ситуации, если они возникнут, и ликвидировать их последствия.

Совершенно очевидно, что подход, основанный па динамическом порождении задач, оказывается более сложным.

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

В разной мере приемлемо и использование симметричных управляюш,их структур, отличие которых от нисходящих струк-

тур может заключаться лишь в некоторых косметических деталях организации пакетов, что иллюстрирует рис. 7.8 (естественно получающийся из рис. 6.4,6). Если модифицировать нисходящие схемы реализации протокола X. 25 путем изменения границ между уровнями, то взаимодействие между пакетами может быть сделано двусторонним без нарушения характера взаимодействий задач. В отличие от рис. 7.5 задача ROUTER-IN на рис. 7.8 перенесена в пакет управления канальным уровнем обмена, а в пакет, описывающий работу сетевого уровня, добавлена новая интерфейсная процедура PUT. Эта процедура обеспечивает теперь декодирование кадров данных и передает пакеты внутренним задачам. Прежде эти функции осуществляла задача ROUTER IN, которой не требуется различать пакеты, поступающие по разным виртуальным каналам; она функционирует просто как задача, осуществляющая транспортировку информационных кадров.

Проектирование еще одной альтернативной симметричной схемы взаимодействий с использованием буферизующей задачи вместо задач-курьеров может быть осуществлено на основе ркс. 6.4, в. Разработку этой схемы мы оставляем читателю в качестве упражнения.

7.5. Проектирование семиуровневой модели взаимодействия открытых систем

В этом разделе кратко обсуждается вопрос о том, каким образом вышеизложенный подход может быть использован при проектировании семиуровневой модели взаимодействия открытых систем (ВОС), предложенной Международной организацией по стандартизации. Эта модель базируется на концепции объектов, предоставляющих некоторые виды услуг объектам вышестоящего уровня. Обслуживающие объекты взаимодействуют с дистанционными равноправными объектами путем обмена протокольными блоками данных, реализуемого нижним уровнем.

Хотя управление физическим обменом протокольными блоками может осуществляться только с помощью объектов нижнего уровня, логическая структура этих блоков может быть скрытой. Скрытность ПБД обеспечивается тем, что протокольные блоки данных верхних уровней вложены в аналогичные блоки нижних уровней точно так же, как протокольные блоки данных сетевого уровня обмена протокола X. 25 (пакеты) вложены в протокольные блоки данных канального уровня (кадры).

Считается, что у каждого объекта имеется точка доступа к сервисным функциям (идентификатор объекта) и что он управляет соединениями, аналогичными виртуальным каналам

Протокола Х.25. Обслуживание обеспечивается с помощью сервисных примитивов, с каждым из которых могут быть связаны соответствующие параметры. Сервисные примитивы могут организовывать движение потока данных между объектами в двух направлениях - сверху вниз и снизу вверх.

Точно так же как в случае протокола Х.25, спецификация вое, определяет только протокольные блоки данных, порядок приема и передачи и результаты, но не описывает структуру системы, реализующей данный протокол обмена.

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

Опираясь на опыт, накопленный нами при рассмотрении предыдущих примеров, можно дать следующие рекомендации по проектированию модели ВОС, реализующей нисходящую уп-равляюшую структуру согласно схеме, изображенной на рис. 6.3, б:

Создавать каждый уровень модели с использованием активного пакета.

Реализовывать каждый объект внутри уровня с помощью видимого активного пакета, вызываемого извне.

Определять сервисные примитивы в контексте видимых процедур пакетов, снабженных необходимыми параметрами. Для придания большей четкости управляющей структуре примитивы, используемые в разных состояниях протокола, следует реализовывать отдельными процедурами.

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

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

> При установлении множественных соединений необходимо предусматривать буферизующую задачу, которая на-

капливает сообщения, идущие в направлении сверху вниз, для передачи их задаче-курьеру (если такая задача вообще существует). Проектирование системы с протоколом Х.25, проведенное выше, служит хорошим примером практического применения этих рекомендаций. Читатели, которые знакомы с соглашениями, принятыми в модели ВОС, могут заметить, однако, что в указанном примере существует целый ряд деталей, не соответствующих структуре ВОС. Например, процедура WAIT-FOR CALL вообще должна не обеспечивать установление соединения при поступлении вызова, а лишь сигнализировать о появлении входящего пакета; для подтверждения приема вызова необходимо иметь отдельную процедуру ACCEPT CALL (ПРИЕМ-ВЫЗОВА). Более того, в некоторых случаях (например, при реализации транспортного уровня модели) идентификаторы каналов должны динамически пересылаться задачам, управляющим их работой в динамическом режиме.

Совершенно очевидно, что можно было бы привести аналогичные рекомендации по проектированию модели ВОС, которая реализовывала бы симметричную управляющую структуру в соответствии со схемой, изображенной на рис. 6.4, в. Разработку такого проекта мы тоже оставляем читателю в качестве упражнения.

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

7.6. Заключение

Мы подошли к разделу, который завершает гл. 7, часть III и всю книгу. В третьей ее части было показано, как в процессе проектирования исследуются взаимосвязи и достигаются соответствующие компромиссы между обеспечением модульности, надежности и структурированности систем при помощи графи^ ческих представлений и методологии проектирования, основанной на использовании языка Ада. Графические средства этого языка в сочетании с изложенной методологией служат хорошей основой для коллективного обсуждения проектных решений. Процесс разработки систем с применением указанных средств может носить относительно неформальный характер и предоставлять разработчику определенную свободу. Однако конечный результат, а именно набор структурных графов, снабженных необходимыми комментариями, является уже формализованным

описанием в терминах языка Ада и может использоваться для написания соответствующих Ада-программ почти механически.

Характерной особенностью всех проектов, рассмотренных в части III (и всюду в данной книге), является организация в соответствующих пакетах и задачах раздельных процедур и входов для разных сервисных функций пакетов и задач. Применительно к задачам было показано, каким образом взаимодействия различного рода могут реализовываться с использованием разных входов в рамках так называемой линейной структуры взаимодействий, которая не допускает использования механизма вложенных рандеву. Такой подход дает возможность разработчику системы, оперирующему со структурными графами, четко показать различный характер требуемой обработки разных запросов. Кроме того, применительно к задачам оказывается возможным отобразить на граф-схемах механизмы ожидания, используемые в межзадачном интерфейсе, в результате чего гарантируется достаточно детальное описание системы на уровне структурного графа, который в свою очередь позволяет обосновывать окончательные проектные решения, не прибегая к текстам программ.

В общем виде мы показали, как в целях достижения необходимой модульности одна или несколько задач могут быть успешно скрыты в теле пакета.

Поскольку весь материал ориентирован на описание процесса проектирования, язык Ада в части III послужил в первую очередь семантической основой графической нотации, и примерам реальных программ, написанных на языке Ада, отведено не слишком много места.

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

Задания для самостоятельного выполнения

Глава 2

2.1. Спроектируйте заново изображенный на рис. 2.9 стековый пакет так, чтобы он имел единственную интерфейсную процедуру, подобную написанной на Паскале (см. рис. 2.5,6). Перепишите тело пакета (рис. 2.4) с использованием языка Ада. Прокомментируйте различия между новы.м и старым пакетами в отношении простоты построения, модульности и функциональных возможностей.

2.2. Напишите на Паскале программу, реализующую стековый пакет, следуя схеме, которая представлена на рис. 2.5, б. Перечислите существенные различия между програм.мой, написанной на Паскале, и соответствующей Ада-программой. Внимательно проанализируйте текст программы и ее поведение во время выполнения. Какое значение при прогоне имеет наличие пакета в программе, написанной на языке Ада, и его отсутствие в программе на Паскале?

2.3. Используя в качестве основы буферизующую задачу, которая схематически представлена на рис. 2.7 и 2.8, спроектируйте и запрограммируйте на языке Ада ее новую версию, предназначенную для организации работы с буферами строк. Новая задача должна иметь два входа: WRITE - для записи символов и READ-для чтения строк. Как и прежде, вход WRITE будет закрыт до тех пор, пока все буферы не освободятся, а вход READ - до тех нор, пока не будет сформирована целая строка. Предполагается также, что строки имеют переменную длину с ограничением по максимуму и оканчиваются специальным символом.

2.4. Предположим, что программист по соображениям удобства вместо реализации пассивного пакета, используемого единственной задачей, решает спроектировать для работы с буферами задачу, управляющую доступом к буферам. Строго говоря, работа с буферами при этом будет организована неправильно. При корректном использовании буферов входы READ и WRITE должны вызываться разными задачами, а в предполагаемом проекте обращение к ним должна выполнять одна и та же задача. Какого типа задачи могли бы быть использованы подобным образом - иллюстрируемые рис. 2.7 и 2.8 или задача

описанная в п. 2.3? Какие типы задач для этого непригодны? Объясните, почему.

2.5. Спроектируйте и запрограммируйте на языке Ада пассивный пакет для работы с буферами, проект которого описан в п. 2.4. Согласно п. 2.3, этот пакет должен включать процедуры для записи символов и чтения строк. Однако формирование условия, разрешающего доступ к строке символов, должно быть организовано по-другому.

2.6. Для буферизующей задачи (рис. 2.7), реализованной согласно схеме рис. 2.8, укажите минимальное и максимальное числа требуемых контекстных переключений при передаче одного символа от отправителя к адресату, предполагая, что в системе функционируют только те три задачи, которые приведены на рисунке. Объясните решение.

2.7. Перепишите заново стековый пакет, приведенный на рис. 2.4, определяя процедуры PUSH и POP с помощью заглушек, согласно рис. 2.12. (Метод, иллюстрируемый рис. 2.12, может быть применен не только к вложенным пакетам, но и к процедурам пакета.)

2.8. Исследуйте различные способы обработки прерываний, применяемые в разных многозадачных системах, сравнив их детально с методом, использующим концепции языка Ада (рис. 2.15).

2.9.(а) Запрограммируйте на языке Ада спецификацию и тело задачи, реализующей функции общего семафора со счетчиком. Семафоры используются как средство синхронизации задач, предотвращающее потерю сигналов, которыми они обмениваются. Такой семафор общего типа реализуется с помощью неделимых примитивов WAIT и SIGNAL внутреннего счетчика, позволяющего оценивать разность между числом задач, посылающих сигналы, и числом задач, ожидающих их поступления, и, наконец, очереди ожидающих задач с дисциплиной обслуживания первым пришел - первым обслужен . Задача, вызывающая WAIT, попадает в указанную очередь и блокируется в том случае, если ранее было зарегистрировано большее число обращений к примитиву WAIT, чем к SIGNAL; в противном случае ее выполнение продолжается без задержки. Задача, стоящая на первом месте в очереди ожидающих, будет выполняться после того как поступит очередной вызов примитива SIGNAL.

(б) Предполагается, что после вызова примитива SIGNAL выполнение вызывающей задачи продолжается без блокировки (исключая, возможно, тот случай, когда в однопроцессорной системе, реализующей приоритетное обслуживание, задача, стоящая во главе указанной очереди, имеет более высокий приоритет, чем задача, посылающая сигнал). Подобным же образом вызов входа WAIT не должен приводить к блокировке, ее-

ли ранее было зарегистрировано достаточное число вызовов входа SIGNAL. Объясните, каким образом это предположение нарушается в вашей Ада-программе; опишите два способа реализации, в которых подобное нарушение могло бы повлиять на поведение во времени задач, обращающихся к семафорам.

Глава 3

3.1. Изобразите структурные графы для буферизующих задач, которые рассматривались в качестве примеров в гл. 2, используя графические обозначения, приведенные на рис. 3.2 и 3.3.

3.2. Для буферизующих задач приведите конкретные примеры структурных задержек, задержек, вызванных перегрузкой, и скрытых задержек.

3.3. Рис. 3.10 и 3.11 служат иллюстрацией образного представления механизма рандеву в языке Ада на примере взаимодействий людей. Однако они иллюстрируют не все возможные случаи (согласно графическим обозначениям на рис. 3.2 и 3.3). Приведите новые схемы, соответствующие рис. 3.10 и 3.11, для условного и временного вызовов входов, а также для оператора отбора с альтернативой задержки и объясните их смысл.

3.4. Изобразите структурные графы, показав все возможные формы взаимодействия главного и подчиненного процессов, и прокомментируйте различия между ними (см. подразд. 3.3.1). Возникают ли при этом случаи, когда подчиненная задача может быть заменена пассивным пакетом? Объясните свой ответ.

3.5. Принимая во внимание определение функциональных типов задач, данное в подразд. 3.3.1, приведите примеры использования задач этих типов на рис. 3.6, б. Выполняет ли задача-секретарь, указанная на рис. 3.6,6, функции секретаря системы в соответствии с определением, данным в подразд. 3.3.1 ? Какие функциональные типы задач не представлены на рис. 3.6,6 ? Можете ли вы дополнить рисунок, найдя в нем место этим задачам?

3.6. Рассмотрите рис. 3.14, в, на котором изображен активный стековый пакет, содержащий вложенную задачу-планировщик ресурсов. Приведите полную структурную диаграмму для системы задач, использующих этот пакет, и затем объясните проявляющиеся в рабочем режиме фундаментальные различия между характером задач, изображенных на этом рисунке, и природой данного пакета. В каком смысле можно было бы сказать, что пакет исчезает в процессе выполнения программы, оставляя место задачам? Какую роль в этом случае играет указанный пакет в ходе выполнения задач? В каком смысле можно говорить об отсутствии различий в рабочем режиме между

вложенным планировщиком (рис. 3.14, е) и отдельным планировщиком (рис. 3.14,5).

3.7. Рассмотрите рис. 3.17, иллюстрирующий косвенное взаимодействие различных задач через буферизующую задачу. Имеются ли существенные различия в эффективности между методом, использующим единственную буферизующую задачу (рис. 3.17, г), и методом, использующим несколько таких задач, одну для каждого абонента (рис. 3.17,6)?

3.8. Рассмотрите рис. 3.19, на котором схематически представлена задача, реализующая сервисные функции на основе приоритетов. Объясните, почему существует теоретическая возможность приема обращений к входам в порядке, отличном от предписываемого приоритетами. При каких состояниях операционного окружения системы такие ситуации были бы возможны?

3.9. Предполагается, что одна высокоприоритетная задача вызывает вход задачи, реализующей сервисные функции (см. рис. 3,19), используя оператор временного вызова, а остальные задачи, имеющие средний и низкий приоритет, обращаются к ее другим входам. Постройте временную диаграмму, иллюстрирующую чередование последовательностей событий, соответствующих точкам синхронизации, когда сервисная задача оказывается не в состоянии обслужить задачи, обращающиеся к ее средне- и низкоприоритетному входам, несмотря на то что очередь вызовов высокоприоритетного входа пуста,

3.10. Приведите временные диаграммы, показывающие чередующиеся активности различных задач, взаимодействующих через задачу-курьер, выполняющую транспортировку данных (рис. 3.21,(3), или с помощью задачи, осуществляющей их буферизацию (рис. 3.21, з). Прокомментируйте различия.

3.11. Предполагается, что имеются четыре задачи, обменивающиеся данными произвольным образом. Изобразите структурные графы, иллюстрирующие схемы взаимодействий с использованием либо задачи-курьера (рнс. 3.21,д), либо буферизующей задачи (рис. 3.21, з). Сравните два подхода. Будут ли результаты сравнения существенно отличаться друг от друга, если четыре задачи взаимодействуют не произвольным образом, а так, что каждая взаимодействует только с двумя из остальных трех?

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

1 ... 27 28 29 30 31 32