Содержание к диссертации
Введение
ГЛАВА I. Общие вопросы создания программного обеспечения систем обработки данных 7
1.1. Введение 7
1.2. Операционные системы для интеллектуальных терминалов II
1.3. Организация обменов с внешней памятью 18
1.4. Организация диалогового редактирования текстов 22
1.5. Обеспечение надежности систем обработки данных 23
1.6. Постановка задачи 25
ГЛАВА 2. Специализированная операционная система "МИКРОС" 27
2.1. Введение 27
2.2. Диспетчер 33
2.3. Супервизор очередей .1 37
2.4. Супервизор связей 41
2.5. Супервизор времени 42
2.6. Супервизор обменов 43
2.7. Оверлейный супервизор 46
2.8. Заключение 47
ГЛАВА 3. Организация диалогового редактирования текстов 50
3.1, Введение 50
3.2. Структура редактора и его распределение между ЭВМ 53
3.3. Организация работы с текстовыми файлами .57
3.4. Использование журналов изменений 67
3.5. Выводы 74
ГЛАВА 4. Организация обменов с внешней памятью произвольного доступа 76
4.1. Общие положения 76
4.2. Стратегия организации обменов 79
4.3. Подсистема обменов СУБД "ИНЕС" 82
4.4. Подсистема обменов с внешней памятью системы диалогового доступа " кО» 93
4.5. Сравнение описанных реализаций подсистемы обменов 96
4.6. Выводы 97
ГЛАВА 5. Обеспечение надежности в системах обработки данных 99
5.1. Основные источники ненадежности систем обработки данных 99
5.2. Обеспечение надежности в системах доступа к текстовым библиотекам 102
5.3. Обеспечение надежности в системе "RQ" .106
5.4. Выводы 114
Заключение 115
Литература
- Организация обменов с внешней памятью
- Супервизор связей
- Организация работы с текстовыми файлами
- Подсистема обменов СУБД "ИНЕС"
Введение к работе
Развитие вычислительной техники в настоящее время характеризуется широким внедрением средств распределенной обработки данных. Одной из сфер применения распределенной обработки является организация диалогового доступа многих пользователей к центральной ЭВМ. Использование терминальных ЭВМ (в составе интеллектуальных терминалов и терминальных станций) позволяет в таких системах повысить общую производительность и разгрузить центральную ЭВМ.
Программное обеспечение многотерминальных диалоговых систем предъявляет специальные требования к используемой на ЭВМ операционной среде. Стандартные операционные системы (ОС), используемые на ЭВМ, этим требованиям удовлетворяют не полностью.
Настоящая диссертация посвящена вопросам создания специализированной операционной среды для многотерлинальных диалоговых систем обработки данных и организации распределения программного обеспечения таких систем между центральной и терминальными ЭВМ.
В первой главе диссертации проведен анализ методов и программных средств, используемых для организации диалоговых систем обработки данных, и сформулированы задачи настоящей работы.
Вторая глава диссертации посвящена разработке стратегии организации и управления вычислительным процессом, ориентированным на обслуживание многих терминалов. Сформулированы основные требования, предъявляемые многотерминальными диалоговыми системами к используемой специализированной ОС. Предлагается стратегия управления вычислениями и структура типовой специализированной операционной системы, основанные на введении специальной дисциплины для прикладных процессов и обеспечиваю -5 щие выполнение многих взаимосвязанных параллельных процессов при минимальном использовании ресурсов ЭВМ.
В третьей главе диссертации исследуются проблемы организации экранного редактирования текстов. Показано, что традиционные методы доступа к текстовым файлам непригодны для экранного редактирования. Разработан полный и ортогональный набор операций доступа к текстовым файлам, обеспечивающий процесс экранного редактирования текстов с нескольких терминалов. Предложена структура распределенного варианта экранного редактора, при использовании которой набор операций доступа к текстовым файлам трансформируется в протокол связи между центральной и терминальными ЭВМ. Введены понятия построчных и посимвольных журналов изменений и показано, что использование предлагаемой структуры распределенного редактора с использованием журналов изменений позволяет повысить эффективность работы и разгрузить центральную ЭВМ. Разработаны структуры данных и схемы основных алгоритмов, реализующих предлагаемый набор операций.
Четвертая глава посвящена организации обменов с внешней памятью в системах диалоговой обработки данных.
Предлагаемая стратегия обменов сочетает преимущества как систем организации виртуальной памяти, так и обычных методов доступа за счет введения специальной дисциплины доступа к данным, из прикладных программ. Она может быть реализована на любой ЭВМ. Описаны две реализации подсистемы обменов на базе предлагаемой стратегии: подсистема обменов системы управления базами данных (СУЩ) "ИВЕС", работающая в среде ОС ЕС и подсистема обменов системы диалогового доступа " Кс])", работающая в среде специализированной ОС "МИКРОС", описанной в первой главе настоящей диссертации.
Пятая глава посвящена вопросам обеспечения надежности в диалоговых системах обработки данных. Проанализированы основные источники сбоев и отказов в таких системах и разработаны требования к надежным системам обработки данных.
Важным требованием является обеспечение минимальных потерь при сбое или отказе системы и обеспечение скорейшего восстановления ее работоспособности после отказа. Предложены принцгшы организации программного обеспечения, направленные на выполнение этого требования.
Для обеспечения высокой сохранности данных необходимо обеспечить быстрое отражение изменений в данных во внешней памяти и поддержку согласованности (корректности) данных в момент повторного пуска системы после ее отказа. Для этого вводится понятие частичной согласованности информационного объекта. Ссоормулированы требования для условий частичной согласованности, при выполнении которых достигается высокая надежность системы без снижения ее быстродействия и малое время восстановления после отказа.
Описана реализация разработанных принципов в системе диалогового редактирования текстов и приведены примеры используемых алгоритмов.
В заключении формулируются основные результаты диссертационной работы.
В приложении I приведены общие характеристики системы диалогового доступа "KtD" и некоторые сведения об ее внутренней структуре.
Приложение 2 содержит сведения об организациях, в которых внедрены результаты настоящей диссертации.
Организация обменов с внешней памятью
Из работ, посвященных вопросам взаимодействия и синхронизации параллельных процессов следует особенно отметить классические работы, посвященные организации мультипрограммирования и взаимодействия параллельных процессов [ 137,138,140,165,208, 209 1 , работы, посвященные организации распараллеливания программ Г129,147,148,149,191 , и работы, посвященные специфике ОС для задач реального времени и для микро-ЭВМ 15,57,62,104, 150,161,168,173,182,196,201,203] . В универсальных ОС время, затрачиваемое на синхронизацию и переключение процессов, обычно недопустимо велико для применений реального времени. Напри- -мер, в работ:е [І96І , описывающей ОС для микро-ЭВМ, приведено время, затрачиваемое на переключение задач: 5-8 милисекунд при типичном времени выполнения одной команды ЭВМ (микропроцессор Z-80 ) - 4 микросекунды, что соответствует выполнению около 1000 команд. Аналогичное по порядку время дают измерения других операционных систем [51,76,141,176] .
Другая важная санкция - это обеспечение эффективных средств структуризации программ. Принципы структурного проектирования программ и структурноно программирования требуют разбиения программ на небольшие компонены (блоки) 2,18,19,36,37] . Издержки на связь медцу ними в стандартных ОС обычно недопустимо велики - приходится разрабатывать специальные, экономные средства структуризации программ и вызова библиотечных подпрограмм [9,91,102] .
Создание подобной типовой специализированной операционной системы является актуальной задачей. Важно, чтобы такая система обладала еще и свойствами мобильности, облегчающими реализацию ее на новых ЭВМ. Мобильность такой ОС в полном объёме -задача трудно выполнимая по нескольким причинам. Во-первых, она обычно требует использования языка программирования высокого уровня, специально предназначенного для создания системного программного обеспечения [142,164,174,186,187,198,199,200] , что сказывается на быстродействии и объёме памяти. Во-вторых, некоторые части ОС неизбежно машинно-зависимы, из-за разнообразия архитектур ЭВМ Г199] . Однако, желательно удовлетворить некоторьш более слабым требованиям, которые значительно облегчат перенос специализированной ОС на новую ЭВМ и ее использование . 1. Компактность и ясность структуры программ.
Независимость средств, предоставляемых пользователю (разработчику прикладной системы) от архитектуры ЭВМ.
Эти требования (мы будем называть их требованиями частичной мобильности) важны еще и потому, что они позволят пользоваться одинаковыми средствами в разных ЭВМ, что существенно упростит проектирование и согласование программного обеспечения распределенных систем.
Организация обменов с внешней памятью - важнейшая функция любой программной системы, работающей с информацией большого объёма. Подсистема обменов является низшим уровнем соответствующего программного обеспечения и от нее зависит как бютродей-ствие, так и надежность в работе системы обработки данных.
Большинство операционных систем представляют для этих целей так называемые методы доступа к данным. Одна из наиболее мощных в этом отношении систем - ОС ЕС [45] предоставляет для работы с устройствами прямого доступа (магнитными дисками) следующие методы доступа [47,52,97] :
Методы доступа к данным из внешней памяти, предоставляемые другими операционными системами общего назначения}обычно составляют подмножество приведенного списка.Рассмотрим применимость перечисленных методов доступа для сложных систем обработки данных (например, СУБД или системы диалогового редактирования текстов).
Физический и прямой методы доступа наиболее близки к непосредственным возможностям оборудования буферизации обменов. Оптимизация обращении к дискам и распределение внешней памяти при их использовании - задача пользователя. Поэтому, при разработке систем обработки данных непосредственно использовать операции этих методов доступа затруднительно из-за их низкого уровня; приходится на их базе строить следующий слой -операции более высокого уровня, решающие (хотя бы частично) проблемы оптимизации и распределения памяти.
Супервизор связей
В соответствии с принципами блочного программирования [2,18,1 программы процессов представляют собой множества блоков (небольших подпрограмм), которые в процессе работы обращаются, одни к другим, причем глубина таких обращений может быть большой. Для обеспечения таких обращений используется супервизор связей. Передача управления от одного блока к другому при вызове или возврате - задача несложная, так как потенциальные связи между блоками в МИКРОС разрешаются статически на этапе редактирования связей (ди намические связи между программными компонентами поддерживаются в МИКРОС оверлейным супервизором). Сложнее дело обстоит с запомина нием и восстановлением регистров. Эта проблема решается с помощью стека, своего для каждого процесса. Но в случае использования про цессорных блоков таких, которые ни прямо, ни косвенно не содер жат операций, связанных с ожиданием, использование стека может ока заться слишком расточительным. Значительная потеря оперативной па мяти произойдет, если такой блок используется во многих параллельных процессах. В этом случае гораздо экономнее использо вать для сохранения регистров программную память. Нарушение фор мальной реентерабельности здесь не опасно благодаря квазиасинх -42 ронной стратегии управления процессами: переключение процессов при работе таких блоков произойти не может.
На ЕС ЭВМ, где нет аппаратно реализованного стека, его приходится моделировать программно. В этом случае сохранение регистров процессорных блоков в программной памяти приводит также и к уменьшению издержек процессорного времени.
Супервизор связей обеспечивает три макрокоманды:# INTO -для обращения к указанному блоку,-ff BLOCK для организации входа в блок H#BFKD - для выхода из блока. При описании блока в операндах макрокоманды # BLOCK указывается его тип (процессорный или стековый), а также информация о том, какие регистры нужно сохранить при входе в блок и восстановить при выходе из него. Некоторые регистры при этом сохраняются и восстанавливаются неявно - это, например, регистр возврата и базовый регистр модуля (последний только в МЖРОС-ЕС).
Супервизор времени предназначен для организации действий, связанных с отслеживанием временных интервалов. Примером использования супервизора времени является организация периодического опроса терминалов, подключенных к общей линии связи,или обнаружение потерянных концов операций - обработка тайм-аутов.
Супервизор времени обеспечивает единственную макрокоманду #WTIME , организующую ожидание конца временного интервала. Неличина интервала задается операндом этой макрокоманды. Особенностью операцииf WTIME"является то, что процесс может быть выведен из состояния ожидания не только в результате окончания заказанного интервала времени, но и при явном выполнении макрокоманды 4 РОST другим процессором или программой обработки прерываний - например, по случаю завершения операции ввода - вывода.
Функционирование супервизора времени основано на поддержании общей очереди запросов на ожидание, упорядоченной по величине требуемых интервалов. По макрокоманде# WTIME блок РЕ процесса включается в эту очередь, а сам процесс переводится в состояние ожидания Кроме того, если новый процесс является минимальным по величине интервала, то таймер настраивается на слежение за завершением этого интервала. Программа же обработки прерываний от таймера (в МИКРОС-ЕС это программа асинхронного выхода макрокоманды STXMER) корректирует очередь,-удаляя из нее процессы, для которых интервал завершении выдавая для них макрокоманду # POST .
Специальная программа супервизора времени удаляет из очереди процессы, которые стали активными раньше, чем завершился заказанный ими временной интервал. Это обеспечивает использование макрокоманды WTIME для обнаружения и обработки тайм-аутов.
Реализация супервизора времени в МИКРОС-ЕС включает в себя еще специальный процессор для задания нового временного интервала (через макрокоманду ОС ST1MER). Необходимость в этом процессе вытекает из следующего ограничения ОС ЕС: нельзя задавать новый временной интервал из программы асинхронного выхода по концу предыдущего интервала [51 52].
Организация работы с текстовыми файлами
И, наконец, эффективную скорость работы такого редактирующего терминала можно увеличить, организовав (мультипрограммно с основной работой) подкачку строк, окружающих фрагмент, отображаемый на экране. Такая подкачка будет осуществляться незаметно для пользователя, пока он просматривает и редактирует текущий фрагмент. Когда пользователь захочет сдвинуться по редактируемому тексту вперед или назад, соответствующие строки скорее всего будут находиться уже в терминальной ЭВМ и операция листания будет выполнена очень быстро.
Чтобы так использовать терминальную ЭВМ,нужны, конечно, еще и программы, обеспечивающие передачу данных по линии связи. Эта часть программного обеспечения должна поддерживать протокол связи между частями редактора, находящимися в разных ЭВМ. Заметим, что программы центральной ЭВМ предназначены для доступа к текстовым файлам и не зависят от характеристик, используемых для редактирования терминалов - соответствующий протокол становится универсальным протоколом для доступа к текстовым файлам. Он шире, чем традиционные протоколы работы с файлами, но это не мешает использовать его и для любых других видов работы с файлами.
Так как протокол линии связи при работе с терминальной ЭВМ определяется программным обеспечением, эффективную пропускную способность линии связи можно повысить введя уплотнение передаваемых текстов. На этом же уровне легко обеспечить шифрование передаваемых данных. Это является дополнительным преимуществом использования для редактирования терминальной микро-ЭВМ - специализированного (возможно, группового) интеллектуального терминала.
Из традиционных методов доступа к файлам, наиболее близкий набор операций (обычно, без возможности двигаться назад по файлу) представляют так называемые индексно-последовательные методы доступа, мало пригодные для наших целей из-за низкой эффективности и необходимости заранее планировать файл в терминах, для пользователей плохо понятных (основная область, область переполнения, индексы).
Непосредственно традиционные! входящие в состав операционных систем) методы доступа нам не подходят. Имеются два варианта организации доступа к текстам. Во-первых,для представления текстового файла можно использовать стандартный последовательный файл, а, во-вторых, организовать собственную файловую структуру, на которой необходимые операции реализуются просто и эффективно.
Использование стандартных последовательных файлов очень заманчиво, так и работают многие редакторы текстов. Основное преимущество такого подхода состоит в том, что при этом автоматически обеспечивается совместимость с другим программным обеспечением, например, текст программы, только что исправленный редактором, можно непосредственно подать на _вход транслятора.
Однако, при использовании последовательных файлов, (сложно реализовать набор операций, требуемый для непосредственного редактирования. Последовательный метод доступа предоставляет обычно следующий набор операций: 1. Встать на начало файла. 2. Прочитать запись и сдвинуться на одну запись вперед. 3. Записать новое значение только что прочитанной записи. Если файл расположен на диске, то, вступая в более тесный контакт с операционной системой (например, работая с последовательным файлом на физическом уровне), можно обеспечить произвольное движение по файлу вперед и назад, но непосредственное вставление и удаление записей в таком файле без полного переписывания всей части файла, следующей за текущей точкой, невозможно - это следует из того, что в последовательных файлах записи располагаются физически друг за другом.
Из этого положения имеется два выхода. Первый состоит в том, что в процессе редактирования на диск ничего не пишется, а информация о всех сделанных изменениях накапливается в оперативной памяти и переписывается на диск лишь в конце сеанса редактирования. Второй способ редактирования последовательного файла состоит в том, что редактирование производится в процессе переписывания текстового файла в файл новой версии. При необходимости сдвинуться назад завершается создание новой версии файла и требуемая запись ищемся уже в нем.
Оба способа использования последовательных файлов для целей редактирования сложны и во многих случаях неэффективны. Другим особенно существенным их недостатком является низкая надежность таких редакторов при сбоях аппаратуры: вся или значительная часть информации об исправлениях, сделанных во время текущего сеанса редактирования, находится в оперативной памяти; при выключении питания они,как правило, будут потеряны.
Решить перечисленные проблемы позволяет специализированная файловая система, ориентированная на работу с текстовыми библиотеками. Основные операции для работы с текстовыми файлами (будем называть их модулями, чтобы отличить их от файлов, поддерживаемых операционной системой) мы уже перечислили. Рассмотрим на примере соответствующей компоненты системы диалогового доступа RED как должна быть реализована такая файловая система. Отложим пока вопрос о способе организации индекса (оглавления) библиотеки, а займемся представлением одного текстового модуля.
Подсистема обменов СУБД "ИНЕС"
Рассмотрим, как выполняются перечисленные требования и решается проблема надежности в системе многотерминального доступа RED , основной компонентой которой является экранный редактор текстов. В систему RED входит специализированная файловая система, организующая текстовые библиотеки. Единицу хранения в такой библиотеке - текстовый файл - мы будем называть модулем, во избежание путаницы со стандартными файлами, обеспечиваемыми операционной системой ОС ЕС, в среде которой функционирует система RED . Отметим, что описанные ниже алгоритмы, разработанные для обеспечения надежности системы RED , применимы в любой файловой системе, ориентированной на мультидоступ и предоставляющей гибкие возможности для обновления файлов.
Прежде всего, при проектировании системы RED соображения надежности заставили отказаться от стандартной библиотечной организации файлов, принятой в ОС ЕС. Другая причина этого отказа - желание выиграть в объёме дисковой памяти за счет упакованного хранения текстов. Сокращенное кодирование последовательностей одинаковых символов в текстах (особенно последовательностей пробелов) на библиотеках исходных текстов программ дает примерно 3-х кратный выигрыш.
Для организации библиотек в системе RED используются дисковые файлы, состоящие из блоков одинакового размера (стандартно - 1024 байта), и физический метод доступа. Для обеспечения эффективной работы с такими файлами в систему RO входит подсистема доступа к дискам (макрокоманда #DI0 ), которая использует страничную память.
Для того, чтобы можно было немедленно вносить задаваемые пользователями изменения в тексты модулей и передвигаться по текстам как вперед, так и назад, модуль организован как дву-связный список дисковых блоков. Каждый блок модуля имеет заголовок, содержащий ссылки вперед и назад - к следующему и предыдущему блокам этого же модуля. Кроме того, в заголовок блока входит и собственный номер (адрес) блока - эта избыточность позволяет контролировать правильность обращения и во-время замечать сбои, связанные с неправильной адресацией. Это, главным образом, сбои из-за ошибок в программе, так как устройства управ -ления дисками осуществляют подобный контроль аппаратными средствами).
Заголовок первого блока модуля содержит также еще и ссылку на элемент оглавления, описывающий данный модуль. Использование этой ссылки будет описано ниже, когда мы перейдем к алгоритмам работы с оглавлением.
Пункт I перечисленных в начале раздела требований и соображения экономии памяти на диске привели к тому, что свободное место в библиотеке - множество свободных блоков - является общим для всех модулей. Для представления этого множества используется битовая шкала, в которой каждому блоку соответствует один бит, показывающий, занят или свободен данный блок.
Данные во внешней памяти можно разделить на служебные и пользовательские. Пользовательские данные - это записи (строки) текстов; остальные данные (заголовки блоков, оглавление, шкала свободных блоков) мы будем называть служебными. Согласованность пользовательских данных - понятие точно неопределяемое; мы лишь должны выполнить пункты 3 и 4 перечисленных требований. Это достигается двумя решениями: во-первых, при переносе текстов из блока в блок (например, при делении блока, когда не хватило места в блоке для вставления новой записи) сначала данные вставляются в новый блок, а лишь затем удаляются из старого. В худшем случае несколько строк файла при сбое сдублируютоя - очевидно, что для пользователя это гораздо лучше, чем потеря строки. Во-вторых, в подсистему обменов с внешней памятью системы RED включен специальный процесс, который раз в некоторый интервал времени (стандартно, в 5 секунд) записывает на диск все измененные блоки, которые там еще не записаны.
Со служебными данными дело обстоит сложнее. Во-первых, при использовании двухсвязных списков блоков нельзя обеспечить непрерывную согласованность ссылок вперед и назад: при вставлении и удалении блоков из модуля эта согласованность будет нарушаться. Во-вторых, для постоянной поддержки правильного состояния шкалы свободных блоков нужно записывать ее на диск при каждом изменении (и то правильность при этом будет не полная -иногда будут происходить потери блоков). В этом случае операции запроса и освобождения блоков будут занимать значительное время и эффективность системы снизится. Рассмотрим, как используемые в системе RED алгоритмы решают эти проблемы за счет введения частичной согласованности и применения алгоритма восстановления.
