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

1 ... 28 29 30 31 32

3.13. Напишите на псевдокоде программу, показывающую, каким образом задача SENDER (см. рис. 3.22,6) должна использовать механизм предоставления разрешения на обмен, реализуемый задачей TARGET.

3.14. Опишите на псевдокоде, как должны взаимодействовать задачи SENDER и TARGET (см. рис. 3.22, е), для того чтобы осуществлять прием и передачу элементов данных и предоставлять разрешение на обмен.

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

3.16. Даны две задачи, каждая из которых имеет один вход и может осуществлять вызов другой. Напишите па псевдокоде тела этих задач для иллюстрации двух ситуаций: 1) когда тупик возникает обязательно и 2) когда состояние тупика не возникает вообще.

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

упорядоченный прием вызовов;

прием вызовов с помощью оператора отбора;

прием одного вызова входа внутри критической секции, связанной с другим входом.

3.18. Напишите на псевдокоде программы, реализующие различные механизмы организации приема вызовов, указанные в п. 3.17.

Глава 4

4.1. На рис. 4.10 схематически изображены два механизма взаимодействия задачи CONTROL с некоторым числом подчиненных задач SLAVE: один - когда вызовы осуществляют задачи SLAVE, и второй - когда вызовы осуществляются задачей CONTROL. При каких условиях задачи SLAVE с целью увеличения эффективности системы можно было бы заменить процедурами? В каком случае оказывается более эффективным использование задач?

4.2. Напишите на псевдокоде тела задач LIFE и KEYBOARD, применяемых в системе LIFE. Используйте в задаче KEYBOARD буфер опережающего ввода символов.

4.3. Для определения конечных автоматов, описывающих работу модуля дешифратора команд в системе LIFE (рис. 4.17), используйте соответствующие составные значения

переменных регулярного типа. Предложите более эффективный способ представления конечных автоматов.

4.4. Разработайте новые структурные графы для случая, когда модуль обработки команд, лежащий в основе системы LIFE, строится на декодировании символов, а не слов. Сравните этот проект с проектом, описанным в гл. 4.

4.5. Напишите на псевдокоде тело пакета управления логическим обменом в системе FORMS и тело вложенного пакета редактирования.

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

4.7. Нарисуйте временную диаграмму, показывающую последовательность событий, в результате которой задача системы FORMS, управляющая работой печатающего устройства, не может начать вывод требуемых строк, пока оператор не нажмет соответствующую клавишу (см. рис. 4.25, а и сопутствующий текст).

4.8. Спроектируйте заново систему FORMS, применяя буферизующую задачу вместо задачи-курьера. Отправным пунктом может послужить соображение о том, что каждая основная задача в системе будет иметь свою собственную буферизующую задачу, с помощью которой она может осуществлять все взаимодействия с другими задачами системы. Двумя главными задачами в системе FORMS являются задача, выполняющая обработку событий, и задача, управляющая работой печатающего устройства. Сравните ваш проект с проектом, описанным в гл. 4.

4.9. Напишите на псевдокоде тела пакета распознавателя команд, и пакета, управляющего работой командного процессора, как внутренних пакетов задачи обработки событий (рис. 4.25).

4.10. Модифицируйте проект системы FORMS так, чтобы параллельное выполнение печати и редактирования достигалось с помощью двойной буферизации. С этой целью необходимо использовать буферы двух типов: 1) для ввода и редактирования данных, 2) для фоновой печати ранее введенной информации. Интерфейс оператора с системой должен быть расширен путем добавления команды печати. Для иллюстрации нового подхода изобразите структурный граф, соответствующий рис. 4.25, а.

4.11. Начертите полный структурный граф системы FORMS, разработанной в гл. 4, изобразив на рисунке все ее компоненты. Кроме пакетов и задач, включите в него также и обрабатываемые данные.

4.12. Постройте структурный граф, показывающий, каким образом в систему FORMS может быть добавлен интерфейс с файловой системой.

4.13. Рассмотрите расширенную версию системы FORMS, представив ее в виде набора подсистем управления пультом оператора, устройством печати и файлами. Исходя из сообра-жений модульности, было бы желательно реализовать каждую подсистему с помощью активного пакета. Изобразите структурный граф, показывающий, какие компоненты подсистемы должны быть включены в эти пакеты: а) при применении метода, описанного в гл. 4; б) при использовании буферизующей задачи, рассмотренной в п. 4.8. Объясните, каким образом эта структура может быть использована в качестве универсального метода создания встроенных операционных систем для персональных рабочих станций.

4.14. Рассмотрите структурный граф системы DIALOGUE, приведенный на рис. 4.32. Изобразите аналогичный структурный граф, который показывал бы, как непродуманная внутренняя структура активного пакета, реализующего интерфейс с подсистемой обмена сообщениями, может приводить к тупику. {Указание. Определите, что произойдет, если при обращении к процедуре SEND MESSAGE пакета вызывающий модуль вы-нуладен будет ожидать выделения области памяти для передачи сообщения?)

4.15. Можно ли получить какие-либо дополнительные преимущества, спроектировав систему DIALOGUE заново не на основе модели с буферизующей задачей для механизма межзадачного взаимодействия, а с использованием задачи-курьера, как показано на рис. 4.32 ? Объясните свой ответ.

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

4.17. Разработайте внутреннюю логику задачи, осуществляющей обработку событий (см. рис. 4.33), включая построение стрзктурного графа и написание программы на псевдокоде.

4.18. Начертите структурный граф, который служит основой для реализации графа потока данных, изображенного на рис. 4.34.

Глава 5

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

(рис. 5.1), появляется возможность состязания между ними. Решение, представленное на рис. 5.1, свободно от указанного недостатка, но даже небольшая его модификация легко приводит к появлению этой возможности. Предполагается, что задача-диспетчер обладает двумя входами, к которым обращаются задачи-кассиры; через вход READY (ГОТОВ) они могут сообщить о состоянии готовности, а по входу \VAIT FOR WORK (ОЖИДАНИЕ-РАБОТЫ) - ожидать поступления запросов. Вход WAIT-F0R--WORK должен быть защищен предохранителем. При такой структуре взаимодействия существует возможность возникновения состязаний между задачами, обращающимися к входу WAIT FOR WORK после вызова ими входа READY. Постройте структурный граф, иллюстрирующий взаимодействие между задачей-диспетчером и задачей-кассиром, и объясните механизм возникновения состязаний, используя временную диаграмму.

5.2. Запрограммируйте на псевдокоде процедуру REQUEST-SERVICE, содержащуюся в банковском пакете (рис. 5.1, а).

5.3. Разработайте тело пакета MAILROOM, изображенного на рис. 5.7.

5.4. Разработайте тело пакета MAILROOM, изображенного на рис. 5.8.

5.5. Рассмотрите механизм управления потоком данных, описываемый структурными графами, представленными на рис. 5.11. Запрограммируйте на псевдокоде тела задач, реализующих как линейную, так и нелинейную структуры взаимодействий (рис. 5.11,6 и 5.11, г). Сравните оба метода. Объясните, почему подход, иллюстрируемый рис. 5.11, г, не обеспечивает реализации универсального механизма блокировки активизации задач.

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

5.7. Объясните, каким образом использование линейной схемы ожидания в примере AGENT-POOL (АГЕНТСТВО) (рис. 5.17,6) может привести к возникновению состязания между задачами, в результате которого клиент получит неправильный номер обслуживающего его агента. Используйте временную диаграмму. Покажите, каким образом можно слегка модифицировать логику решения данной проблемы (см. рис. 5.17, а), чтобы вопрос возникновения состязаний между задачами стал несущественным.

5.8. Предполагается, что проблема возникновения состязаний между задачами (рис, 5.17,6) решена путем создания до-

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

5.9. Рассмотрите проблемы проектирования коммуникационного пакета, который реализует концепцию узла надежности (рис. 5.23). Предполагается, что пакет может быть разделен на две части, одна из которых обеспечивает экспорт и импорт специальных запросных сообщений, адресованных входам задач, а другая - обмен сообщениями любого тина между узлами надежности. Выберите подходящую структуру интерфейса для модуля обмена сообщениями, а затем спроектируйте экспортно-импортную часть процедуры вызова входа. Эта часть пакета должна предусматривать упорядочение и согласование обращений к входам задач, принадлежащих одному и тому же узлу надежности, например, ири помощи пула задач-партнеров . Другой способ реализации может быть связан с условными вызовами входов, исходящими от задачи, которая управляет обращениями к входам (распорядитель вызовов). В любом случае в вашем проекте должна учитываться возможность того, что операторы приема, соответствующие нужным входам, будут защищены предохранителями.

5.10. Изучите описание родовых программных структур, приведенное в каком-либо руководстве по языку программирования Ада, и прокомментируйте возможность их включения в набор инструментальных средств языка Ада, используемых при проектировании систем в гл. 2-5.

Глава 6

6.1. Структура интерфейса между системами DIALOGUE и СОММ (рис. 6.9) основывается на канонической форме представления с использованием задач-курьеров для осуществления транспортировки данных в многоуровневых системах (рис. 6.3, г). При таком каноническом представлении задачи, реализующие функции каждого уровня, включены в некоторые пакеты. Однако задачи, реализующие систему DIALOGUE (рис. 6.9), оформлены по-другому. Покажите, как вся эта система может быть целиком включена в некоторый пакет с целью получения канонической структуры.

6.2. Покажите, каким образом можно изменить структуру интерфейса DIALOGUE/COMM, представленную на рис. 6.9, для преобразования ее в каноническую структуру, ориентированную на использование буферизующих задач (см. рис. 6.4, е).

6.3. Спроектируйте заново управляющий пакет логического обмена кадрами данных, представленный на рис. 6.12, используя каноническую структуру с буферизующими задачами для многоуровневых систем (см. рис. 6.4,8).

6.4. Запрограммируйте на псевдокоде тело пакета F PRO-TOCOL (рис. 6.14), применяя таблицы переходов конечных автоматов и следуя методу, использованному в гл. 4 при проектировании модуля дешифратора команд в системе LIFE.

6.5. Напишите программу на псевдокоде, описывающую внутреннюю логику задачи FS и основанную на идеях, иллюстрируемых рис. 6.13-6.15.

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

6.7. Запрограммируйте на псевдокоде тело задачи, выполняющей обработку прерываний в рамках управляющего пакета физического обмена кадрами данных (рис. 6.16).

6.8. Предполагается, что в подсистеме СОММ тело пакета F (см. рис. 6.12) должно быть модифицировано без изменения синтаксиса и семантики его спецификации таким образом, чтобы он мог служить в качестве пакета ввода-вывода для устройства управления прямым доступом к памяти (УУПД) и реализовывал во всех деталях протокол обмена кадрами. Это автономное аппаратное устройство копирует кадры данных из буферных блоков, содержащихся в теле пакета F, в свои собственные буферы для последующей передачи; аналогичным образом оно копирзет входящие кадры из собственных внутренних буферов в буферные блоки пакета F. По завершении копирования в обоих направлениях УУПД формирует два разных сигнала прерывания. Будем считать, что УУПД осуществляет все функции протокола обмена кадрами, так что пакет F только управляет передачей кадров в это устройство и приемом кадров из него, а также реализует информационный обмен с пакетом М. В результате функции пакета F становятся аналогичными функциям описанного в гл. 6 пакета Р, который больше не нужен. Постройте и подробно прокомментируйте граф информационных потоков и структурный граф, соответствующие телу нового пакета F, и объясните принцип его функционирования.

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

6.10. Используйте информационный граф, изображенный на рис. 6.19, в качестве базиса для повторного проектирования структурных графов подсистемы СОММ, основанных на использовании канонической модели многоуровневой системы с буферизующими задачами (см. рис. 6.4, е).

Глава 7

7.1. Возникновение состязаний между задачами может происходить различным образом. Пакет управления сетевым уровнем обмена с использованием протокола Х.25 (рис. 7.5) служит одним из примеров такого рода. В этом пакете существует возможность возникновения состязания между задачей, пытающейся обратиться к входу CONNECT (после того как задача DISPATCHER выделила ей номер канала), и задачей ROUTER IN, вызывающей вход PUT для того, чтобы передать поступивший запрос на установление связи. Объясните причины появления эффекта состязания и возникающие прн этом последствия, используя временную диаграмму. Какие механизмы восстановления информации неявно присутствуют на рис. 7.5?

7.2. Постройте упрощенный структурный граф, соответствующий пакету, который реализует сетевой уровень протокола Х.25 (рис. 7.5), для случая, когда этот пакет обеспечивает обмен по единственному виртуальному каналу. Исключите из рассмотрения все неиспользуемые элементы рис. 7.5. Обоснуйте ваш способ решения проблемы.

7.3. Перечертите заново соответствующие части структурного графа, описывающего пакет управления сетевым уровнем протокола X. 25 (рис. 7.5) для отображения возможности pea-, лизации несколько иного способа приема входящих вызовов; при поступлении пакета, содержащего запрос, из него извлекается адрес отправителя и передается абоненту, ожидающему по входу WAIT FOR CALL; абонент должен подтвердить прием этого запроса до того как будет послан пакет, содержащий ответ. Такой способ действий противоположен методу, иллюстрируемому рис. 7.5, где задача VCM немедленно отправляет пакет, содержащий подтверждение приема, и вынуждает абонента снять запрос на установление соединения, если оно нежелательно. Рассмотрите возможность изменения интерфейса пакета, выполняемых задачами функций и механизмов межзадачного взаимодействия с целью реализации указанного метода.

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

виртуальных каналов обмена, а номера каналов выделяются им динамически? При таком подходе данная задача в различные моменты времени может управлять разными виртуальными каналами. Напомним, что поступающие пакеты с запросами на установление соединения, исходящие запросы, а также посылаемые подтверждения приема запросов содерлот номер виртуального канала. В методе, иллюстрируемом рис. 7.5, номер виртуального канала, имеющийся в поступающем запросе, совершенно однозначно идентифицирует задачу VCM. Поэтому задача ROUTER IN может использовать этот номер для пересылки запроса соответствующей задаче VCM. При использовании же метода динамического распределения номеров каналов подобная возможность отсутствует, поскольку в момент поступления такого пакета задаче ROUTER-IN неизвестно, какая из задач VCM будет управлять виртуальным соединением. В общем случае каждый раз, когда поступает пакет, содержащий запрос на установление соединения, или инициируется локальный вызов, свободной задаче VCM должен быть сообщен новый номер выделенного виртуального канала. Этот способ действий противоположен иллюстрируемому рис. 7.5, где свободная задача VCM сообщает диспетчеру номер обслуживаемого ею виртуального канала. (Пул задач-агентов, описанный в гл. 5, может послужить источником идей относительно способа осуществления динамического назначения номеров виртуальных каналов.)

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

7.6. Следуя принципам, изложенным в гл. 6 при построении пакета М, спроектируйте соответствующий интерфейсный пакет обмена, обеспечивающий передачу и прием сообщений на верхних уровнях системы (т. е. выше уровня пакета, реализующего протокол Х.25). Примите во внимание тот факт, что пакет, обеспечивающий функционирование сетевого уровня обмена, не включает механизма ожидания разрешения на передачу. Напомним, что проект, изложенный в гл. 6, предполагает наличие такого механизма.

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

7.8. Напишите на псевдокоде программу тела задачи-диспетчера, схематически изображенной на рис. 7.5.

7.9. Начертите структурный граф, показывающий, каким образом в интерфейсном пакете обмена сообщениями (п. 7.6)

может использоваться схема регистрации событий, приведенная на рис. 7.7.

7.10. Начертите отличный от схемы рис. 7.5 структурный граф, описывающий организацию тела пакета, реализующего протокол X. 25, с использованием только одной главной задачи, управляющей работой всех виртуальных каналов.

7.11. Начертите структурный граф для тела пакета, реализующего протокол Х.25 (рис. 7.5), с использованием двух задач: одной - для управления обменом запросами по всем виртуальным каналам, а другой - для управления обменом данными.

7.12. Напишите на псевдокоде программу тела задачи-диспетчера (см. рис. 7.5) для случая, когда задачи VCM создаются в динамическом режиме при поступлении запросов (как предлагается в подразд. 7.4.3).

7.13. Разработайте альтернативную структуру пакета, реализующего сетевой уровень протокола X. 25, используя в качестве отправной точки каноническую структуру взаимодействий посредством буферизующих задач (рис. 6.4, в). Пусть, как и прежде, каждая задача VCM управляет работой одного виртуального канала. Строгий подход заключается в том, чтобы создать одну буферизующую задачу для всех задач VCM; кроме того, необходимо иметь семейство входов, на которых эти задачи смогут ожидать выделения им номеров обслуживаемых каналов. Требуется ли использование диспетчера в этом случае, или его функции могут быть переданы буферизующей задаче? Сравните ваше проектное решение со схемой, представленной на рис. 7.5. Выгодно ли при таком подходе реали-зовывать каждую из функций пакета с помощью отдельной процедуры? Должен ли интерфейс пакета быть изменен таким образом, чтобы его спецификация содержала две процедуры - одну для передачи, а другую для приема данных, что схематически изображено на рис. 6.4, в?

Литература

1. Booh G. Describing Software Design in Ada, ACM SIGPLAN Notices, pp. 42-47, September, 1981.

2. Bowen B. A., Buhr R. J. A. The Logical Design of Multiple Microprocessor Systems, Engiewood Cliffs, NJ, Prentice-Hall, Inc., 1980.

3. CCITT Recommendation X. 25.

4. Hansen Per Brinch, The Architecture of Concurrent Programming, Engiewood Cliffs, NJ, Prentice-Hall, Inc., 1977.

5. IAPX-432 Object Primer, Intel Corporation, January, 1981.

6. Myers G. J. Reliable Software Through Composite Design. New York, Petro-celli/Charter, 1975. [Имеется перевод: Майерс Г. Надежность программного обеспечения. - М.; Мир, 1980]

7. Ру!е I. С. The Ada Programming Language, Englewood Cliffs, NJ, Prentice-Hall, Inc., 1981. [Имеется перевод; Пайл Я. Ада -язык встроенных систем.-М.: Финансы и статистика, 1984.]

8. Reference Manual for the Ada Programming Language, Draft revised MIL -STD 1815, United States Department of Defence, July, 1982, ANSI/MII -STD-1815A, United States Department of Defence, January, 1983.

9. Wegner P. Programming with Ada: An Introduction by Means of Graduated Examples, Englewood Cliffs, NJ, Prentice-Hall, Inc., 1980. [Имеется перевод: Вегнер П. Программирование на языке Ада - М.: Мир, 1983.]

10. Yourdon е., Constantine L. Structured Design, Englewood Cliffs, NJ, Prentice Hall, Inc., 1979,

1 ... 28 29 30 31 32