автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Разрешение конфликтных ситуаций при доступе к ресурсам информационно-вычислительных систем

а 3*9*1

Московский ордена Ленина,ордена Октябрьской Революции и ордена Трудового Красного Знамени государственный университет им.М.В. Ломоносова Научно-исследовательский вычислительный центр

На правах рукописи УДК 681.518

Сэруга Ян

РАЗРЕШЕНИЕ КОНФЛИКТНЫХ СИТУАЦИЙ ПРИ ДОСТУПЕ К РЕСУРСАМ ИНФОРМАЦИОННО-ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Специальность 05.13.11 - математическое и программное

обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1991

/'-7

/

1-;

Работа выполнена на кафедре электронных вычислительных машин Львовского политехнического института.

Научный руководитель : - доктор технических наук, профессор

Б.И.Швецкий

Официальные оппоненты: - доктор технических наук, с. н. с.

В А. Сухомлин - кандидат физ.-мат.наук, ст. преп. АА.Хасанов

Ведущая организация: - ВЦ АН СССР

Защита состоится " ^^ ^ 1991 года в ^ час. ^мйн.

на заседании специализированного совета К.053.05.84. в Московской государственном университете им. М.' В. Ломоносова по адресу: 119899 Москва МГУ НИВЦ .

С диссертацией можно ознакомиться в библиотеке НИВЦ МГУ.

1с

Автореферат разослан " ^ —"_1991 года

Ученый секретарь специализированного совета канд.физ.-мат.наук

М.Н.Киоса

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы

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

Актуальность разработки эффективных методов борьбы с тупиковыми ситуациями очевидна.

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

К основным задачам рассмотренным в работе относятся:

1. Анализ методов обнаружения и устранения тупиковых ситуаций.

2. Разработка алгоритма обнаружения и устранения тупиковых ситуаций в сети с локальный затравленней перегрузками.

3. Разработка алгоритма обнаружения и устранения тупиков промежуточного накопления в сети.

4. Разработка распределенного алгоритма взаимного исключения процессов в сети.

5. Определение условий создания среды многодоступных баз данных в сетях типа TRANSNET и D-LINK на персональном компьютере.

Методы исследования. Для решения поставленных задач в работе использованы методы теории систем, теории графов, теории множеств, теории массового обслуживания.

Научная новизна результатов работы заключается в следующем:

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

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

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

Апробация работы.

Основные положения и результаты диссертационной работы докладывались и обсуждались на:

1) Международной конференции - "15 Internationale Kolloquium uber Information und Dokumentation des Institute fiir

Informationswissenschaft Erfindungswesen und Recht, Erfurt (ГДР), ноябрь, 1987.

2) Международной конференции - "Miedzynarodowe Sympozjum. Zastosowanie mikrokomputerow w INTE - Katowice (Р.Польша), ноябрь, 1988.

3) научных семинарах, организованных в Международном центре научной и технической информации в Москве.

Личный вклад автора. Все основные результаты, изложенные в диссертации, получены автором лично.

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

Алгоритмы по разработанным в диссертации методам обнаружения и устранения тупиковых ситуаций при доступе к ресурсам информационно-вычислительных систем нашли применение в Главном центре информатики горной промышленности (Польша) при создании опытной вычислительной сети.

Структура и объем диссертации.

Диссертация состоит из введения, трех глав, заключения, списка литературы (36 наименований), двух приложений, содержит 91 страниц машинописного текста, 6 рисунков.

Публикации.

Основные результаты выполненных исследований опубликованы в 5-ти печатных работах.

Основные положения , выносимые на защиту.

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

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

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении показана актуальность темы работы, сформулированы цель и задачи исследования.

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

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

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

Стохастические методы заключаются в использовании статистической информации о функционировании процессов е распределении ресурсов для Предотвращения тупиковых ситуаций. Данные методы основаны на оценке вероятности возникновения тупиковых ситуаций.

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

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

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

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

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

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

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

Сетевая топология представляется направленным графом

0=(Х,У)

где, Х-множество узлов сети, а У-множество каналов.

В каждом узле п имеется Ьд нечетных буферов. Поступающие в узел пакеты классифицируются в соответствии с выходными очередями.

Множество всех классов для узла п обозначается через

Сц={ Сп2>—

При с= и Сп

тлх

Вводится функция Г, которая отображает любой класс

сеС для данного узла в X т.е. /\ /\ Цс) = П

т, псХ СеС п 1

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

Сбрасываемые пакеты передаются повторно, для чего передающий узел хранит копии переданных пакетов до их подтверждения . В сети допускается любая процедура маршрутизации. Любой маршрут из узла 8 Ь узел <1 может быть описав как упорядоченная последовательность классов {С8,...,С<1}.

В следующем алгоритме обнаружения и устранения тупиков в сети рассматривается тупик промежуточного накопления в сети.

Рис.1. Тз^пик передачи, порожденный принципом промежуточного накопления.

На рис.1 показан тупик, пораждаемый самим принципом "промежуточного накопления". Два соседних узла хотели бы принять пакеты друг от друга, но они не могут этого сделать из-за того, что оба переполнены. Если бы узел А мог послать один пакет узлу В, то в нем освободилось бы место для приема пакета от В, и тупик был бы ликвидирован.

Тупики промежуточного накопления могут привести всю сеть в неработоспособное состояние. Отсутствие таких тупиков может быть гарантировано при использовании специальных протоколов.

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

Выходной канал может находиться в одном из трех состояний: нормальном (Л), проверочном (Т) и устранения тупика (УТ) рис.2 а- устранение тупика ; Ь- отсутствие тупика с- обнаружение тупика ; <1- подтверждение тупика

Рис.2 Состояния Ьыходного канала

В зависимости от состояния канала формулируются различные заголовки выходных пакетов.

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

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

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

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

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

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

время каналы сети могут повреждаться, поэтому рассматриваются две ситуации, возникающие при передаче одного запроса взаимного исключения процессов:

1) поврежденный канал является минимальным сечением и его повреждение нарушает связность сети;

2) повреждение канала не нарушает связности сети

В третьей главе рассматриваются методы борьбы с тупиковыми ситуациами в распределенной системе управления баз данных (СУБД). Одной из основных особенностей распределенной СУБД является параллельное управление процессами.

Можно выделить четыре основных метода, идеи которых положены в основу подсистем управления транзакциями распределенных СУБД.

1) централизованного блокирования

2) децентрализованеного блокирования

3) децентрализованного голосования

4) "оптимистического подхода"

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

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

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

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

Распределенные базы данных типа dBASE, работающие в локальной сети, созданной на базе микроЭВМ (IBM PC) являются классическим примером систем с разделением ресурсов, в которых могут возникать конфликтные ситуации. В работе представлена схема работы, сети, созданной на базе IBM PC под управлением операционной системы PC DOS. Прикладное математическое обеспечение работает в специфической среде определенной следующими элементами:

- компьютер типа IBM XT/AT

- системное математическое обеспечение BIOS для обмена информации с внешними устройствами

- компилятор или прикладной пакет, с помощью которого создано данное прикладное математическое обеспечение.

В сети соединены микрокомпьютеры типа IBM XT/AT с вставленными платами расширения сети IBM PC Network. В процессе распределения логических соединений определяется совместное разделение таких сетевых объектов, как диски, печатающие устройства, а также подоглавления. Разработка соответствующих протоколов и включение их к сети D-LINK и TRANSNET позволяет расширить возможности этих сетей на одновременное использование одного ресурса пользователями.

Основные выводы и результаты работы:

1. Проведен анализ методов борьбы с тупиковыми ситуациами. Наиболее удобными при анализе оказались методы, основанные на графовых моделях доступа процессов к ресурсам.

2. Представлены особенности тупиковых ситуаций в информационно- вычислительных сетях.

3. Предложен алгоритм для тупиков типа "запоминания-продвижения", возникающих в сети при заполнении для дальнейшего продвижения пакетов в буферах.

4. Предложен алгоритм для тузиков, порожденных самим принципом "промежуточного накопления".

5. Предложен алгоритм взаимного исключения процессов к коллективно используемому ресурсу.

6. Предложены методы борьбы с тупиковыми ситуациами в распределенной системе баз данных.

7. Определены условия создания среды многодоступных баз данных в локальной сети на персональных компьютерах.

Список публикаций

1. Сэруга Я. Создание среды многодоступных баз данных в сетях типа TRANSNET и D-LINK на персональном компьютере. -Контрольно-измерительная техника, N 47 ,1990.

2. Seruga J. Entwicklungstendenzen von Informationsubertragugsnetzen-15 Internationale Kolloquium über Information und Dokumentation, November, 1987, Heft 70, pp.76-82.

3. Seruga J. Zastosowanie mikrokomputerow w sieciach informacyjnych-Miedzynarodowe Sympozjum. Zastosowanie mikrokomputerow w INTE. Katowice, Polska, 1988, zbior streszczen, str.132-133.

4. Сэруга Я. Преимущества вычислительных сетей Международная конференция: Автоматизация информационного обслуживания, Бургас (НРБ), 1987, сб.ч.З, стр.174-176.

5. Seruga J. Rozwoj sieci teledacji - APID, Warszawa, N 6, 1988, str.10-14.

6.Seruga J. Swiatowe bazy danych -Деп.в ЦИНТЭ Р.Польша , N