Введение 5

Глава 1. Анализ методов и машин логического вывода и систем обработки знаний 14

1.1 Методы и машины логического вывода 14

1.1.1 Классификация видов логического вывода 14

1.1.2 Классификация методов логического вывода 16

1.1.3 Метод деления дизъюнктов 19

1.1.4 Машины логического вывода 23

1.2 Системы обработки знаний (СОЗ) 25

1.2.1 Определение и структура 25

1.2.2 Классификация 29

1.2.3 Режимы функционирования 31

1.2.4 Оценка эффективности 33

1.3 Выводы по главе 1 35

Глава 2. Разработка метода логического вывода модифицируемых заключений 36

2.1 Формальные системы 36

2.2 Постановка задачи логического вывода 37

2.3 Расширение формулы заключения

2.3.1 Унификация литералов 39

2.3.2 Согласование решений 40

2.3.3 Согласование значений общих переменных в конъюнкциях дизъюнктов 43

2.3.4 Частичное деление дизъюнктов 45

2.3.5 Полное деление дизъюнктов 47

2.3.6 Процедура вывода 49

2.3.7 Построение абдуктивных объяснений

2.3.8 Метод параллельного вывода с расширением формулы заключения

2.4 Минимизация формулы заключения 65

2.4.1 Процедура минимизации заключения 65

2.4.2 Метод минимизации заключения

2.5 Выбор вариантов модификации 69

2.6 Особенности вывода в исчислении высказываний 72

2.7 Пример вывода 73

2.8 Выводы по главе 2 77

Глава 3. Разработка системы логического вывода модифицируемых заключений 80

3.1 Структура системы логического вывода 80

3.1.1 Обобщенная структура системы 80

3.1.2 Детализованная структура системы 82

3.2 Режимы работы системы логического вывода 85

3.2.1 Режим вывода модифицируемых заключений 86

3.2.2 Режим дедуктивного вывода 88

3.2.3 Режим абдуктивного вывода 88

3.2.4 Режим настройки 88

3.2.5 Режим непосредственного доступа к базам знаний 89

3.2.6 Создание базы знаний

3.3 Машина логического вывода модифицируемых заключений 90

3.4 Язык декларативного логического программирования

3.4.1 Структура логической программы 96

3.4.2 Идентификаторы и константы 99

3.4.3 Комментарии 100

3.4.4 Пример логической программы 101

3.5 Оценка эффективности систем логического вывода 102

3.5.1 Критерии оценки эффективности 102

3.5.2 Расчет времени вывода 103

3.5.3 Расчет степени модификации заключения 108

3.6 Выводы по главе 3 110

Глава 4. Применение систем логического вывода модифицируемых заключений ИЗ

4.1 Области применения 113

4.2 Интеллектуальные обучающие системы 114

4.3 Экспертные системы 119

4.4 Интеллектуальное управление вычислительными процессами 121

4.5 Модуль логического вывода модифицируемых заключений 1

4.5.1 Общая характеристика разрабатываемого программного обеспечения 127

4.5.2 Структура модуля вывода 128

4.5.3 Язык описания базы знаний и заключения 129

4.5.4 Реализация блоков модуля 130

4.6 Учебная программа логического вывода «Логика-В» 134

4.6.1 Структура программы 134

4.6.2 Язык описания исходных данных 135

4.6.3 Интерфейс пользователя 136

4.6.4 Пример использования программы 141

4.7 Выводы по главе 4 149

Заключение 152

Список сокращений 155

Библиографический список 156

Приложения 1

Введение к работе

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

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

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

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

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

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

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

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

Данные виды вывода известны достаточно давно и могут применяться для решения широкого круга задач. Однако существует класс задач, решить которые применением указанных видов вывода невозможно или затруднительно. Данный класс задач предполагает наличие корректной и полной БЗ для некоторой предметной области и недостоверное заключение, требующее преобразования. Следовательно, появляется принципиально новая постановка задачи логического вывода: модифицировать исходно невыводимое заключение с целью сделать его следствием исходных посылок. Данная задача решается посредством применения нового вида ЛВ - логического вывода модифицируемых заключений. В качестве областей применения данного вида вывода можно отметить следующие: - системы автоматического регулирования. Состояние объекта управления в такой системе описывается логической формулой заключения, а допустимый диапазон состояний задается в виде формул исходных посылок. Если состояние объекта выходит за допустимые пределы, производится модификация заключения для возвращения объекта в допустимое состояние;

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

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

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

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

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

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

Значительный вклад в разработку и исследование методов и средств логического вывода внесли М. Л. Цетлин, М. М. Бонгард, Я. 3. Цыпкин, Д. А. Поспелов, В. К. Финн, Г. С. Осипов, В. Н. Вагин, Т. А. Гаврилова, В. Ф. Хорошевский, П. Гаек, Т. Гавранек, С. Осуга (S. Osuga), Ю. Саэки (U. Saeki), А. Сэмюэль (A. Samuel), Э. Хант (Е. Hunt), Д. Марин (J. Marin), Ф. Стоун (P. Stone), Р. Михальски (R. Michalski), Д. Карбонелл (J. Carbonell), Т. Митчелл (Т. Mitchell), Д. Куинлан (J. Quinlan). Абдуктивный ЛВ исследовался в работах Ч. С. Пирса (С. S. Pierce), В. К. Финна, В. Н. Вагина, Е. Ю. Головиной, Д. А. Страбыкина, М. Л. Долженковой, Д. Габбая (D. Gabbay), П. Сметса (P. Smets), К. Бутилье (С. Boutilier), П. Флеча (P. Flach), А. Какаса (A. Kakas), К. Иноуэ (К. Inoue), Ч. Сакама (С. Sakama), Дж. Джозефсона (J. Josephson), С. МакИлрайта (S. Mcllraith), Дж. Пола (G. Paul) и др.

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

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

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

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

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

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

Научная новизна исследования состоит в следующем.

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

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

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

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

Практическая ценность исследования состоит в следующем:

1. Разработана система параллельного, логического вывода модифицируемых заключений, отличительными особенностями которой являются: использование методов и машины параллельного ЛВ, использование двухуровневой базы знаний, наличие блока интерпретации формул, что позволяет строить на основе разработанной системы логического вывода высокопроизводительные СОЗ различного назначения. Процесс вывода может быть распараллелен вплоть до уровня операций унификации литералов, что повышает скорость логического вывода на параллельных вычислительных платформах.

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

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

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

На защиту выносятся:

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

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

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

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

5. Параллельная система логического вывода модифицируемых заключений на основе машины параллельного логического вывода, способная выполнять основные виды логического вывода, а также логический вывод модифицируемых заключений. Внедрение результатов исследования. Полученные теоретические и практические результаты использованы в НИР «Теория и применение логического вывода с модификацией заключений» (грант Министерства Образования РФ Е02-2.0-93), в НИР «Разработка среды декларативного логического программирования для кластерной вычислительной системы» (ВятГУ, НИР №412). Учебная программа логического вывода внедрена в учебный процесс в Вятском государственном и Вятском государственном гуманитарном университетах.

Апробация работы. Основные положения и результаты исследования докладывались и обсуждались на 5-й международной конференции «Interactive Systems: The Problems of Human-Computer Interaction» («Интерактивные системы: Проблемы взаимодействия человек - компьютер»), Ульяновск, УлГТУ, 2003; 9-й «Национальной конференции по Искусственному Интеллекту КИИ-2004», Тверь, 2004; Всероссийской ежегодной научно-технической конференции ВятГУ «Наука-производство-технологии-экология», Киров (2004,2007,2008 гг.)

Методы вывода и поиска решений в продукционных системах.

Методы вывода на основе прямой и обратной цепочек.

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

Механизм вывода сопоставляет каждое правило, хранящееся в БЗ с фактами, содержащимися в БД. Когда часть правила если (условие) подходит факту, правило срабатывает и его часть тогда (действие) исполняется . Срабатывающее правило может изменить множество фактов путем добавления нового факта, как показано на рис.6.1. Буквы в БД и БЗ используются для представления ситуаций и понятий.

Рис.6.1. Цикл механизма вывода через процедуру «сопоставление – срабатывание»

Сопоставление частей если правил с фактами создает цепочку вывода. Цепочка вывода показывает как ЭС применяет правила для получения заключения. Для иллюстрации метода вывода на основе цепочки, рассмотрим простой пример.

Допустим, БД первоначально включает факты А,В,С,D и Е, а БЗ содержит только три правила:

Правило 1. Y&D → Z

Правило 2. X&B&E→Y

Правило 3. A→X

Цепочка вывода на рис. 6.2. показывает, как ЭС применяет правила для вывода факта Z.

Рис.6.2. Пример цепочки вывода.

Сначала срабатывает Правило 3 для вывода нового факта Х изданного факта A. Тогда Правило 2 выполняется для вывода факта Y из первоначально фактов В и Е, а также уже известного факта Х. И наконец, Правило 1 применяет первоначально известный факт D и только что полученный факт Y для прихода и заключению Z.

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

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

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

Продукционные системы, в которых сначала анализируется антецедентная часть (условия), имеют так называемую условно-выводимую архитектуру. Примером экспертной системы такой ар­хитектуры является META-DENDRAL.

Альтернативным типом архитектуры, которая достаточно час­то используется в экспертных системах, являются целе-выводимые (действие-выводимые или консеквент-выводимые) продукци­онные системы. Например, правило вида

может быть интерпретировано, как

«Логическая конъюнкция А, В и С влечет D» или

«Чтобы доказать D, необходимо установить А, В, С».

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

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

Правило 1: A&B&C→D

Правило 2: D&F→G

Правило 3:A&J→G

Правило 4: В→С

Правило 5: F→B

Правило 6: L→J

Правило 7: G→H

Предположим, цель состоит в том, чтобы вывести истинность Н. В первую очередь проверяется, находится ли Н в БД? Так как в данном случае это не так, то система пытается вывести истин­ность Н, используя правила, имеющие Н в правой части. Таким является правило 7. Теперь система пытается вывести истинность G, так как истинность последнего влечет за собой истинность Н. Снова проверяется БД: в БД нет G, следовательно, организуется полек правила, содержащего G в правой части. Таких правил несколько (два или три). В качестве стратегии «разрешения кон­фликта» будем считать, что правила упорядочены по приоритету, причем правилу с наименьшим номером соответствует больший приоритет.

В данном случае выбирается правило 2, поэтому целью теперь становится вывести истинность D и F. Для этого достаточно по­казать, что А - истинно (так как находится в БД), В - истинно (согласно правилу 5), С - истинно (согласно правилу 4). Так как истинность D и F доказана, то из правила 2 следует истинность G, а из истинности G - следует истинность Н (правило 7). Таким образом цель достигнута. Элементы, истинность которых доказана, добавляются в БД. В данном случае это - элементы Н, G, D, С. В. Примерами целе-выводимой архитектуры является MYCIN.

Выводы на фреймах и в семантических сетях.

Вывод на фреймах.

Структура данных фрейма.

Прежде, чем обсуждать вывод во фреймовой системе, рассмотрим подробнее структуру данных фрейма.

Фреймовая система – это иерархическая структура, узлами, которой являются фреймы с определенной структурой данных.

1. Имя фрейма. Это идентификатор, присваиваемый фрейму. Фрейм должен иметь имя, единственное в данной фреймовой системе (уникальное имя). Каждый фрейм состоит из произвольного числа слотов, причем несколько из них обычно определяются самой системой для выполнения специфических функций, а остальные определяются пользоватлем. В их число входят слот, показывающий фрейм – родитель данного фрейма; слот указателей дочерних фреймов, который является списком указателей этих фреймов; слот для ввода имени пользователя, даты определения, даты изменения, такста комментария и другие слоты. Каждый слот, в свою очередь, также представлен определенной структурой данных.

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

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

4. Указатель типа данных (атрибутов слотов). Указывается, что слот имеет численное значение численное значение, либо служит указателем другого фрейма (т.е. показывает имя фрейма). К типам данных относятся указатель, целый, действительный, булевый, присоединенная процедура, текст, список, таблица, выражение и др.

5. Значение слота. Здесь вводится значение слота. Значение слота должно совпадать с указанным типом данных этого слота, кроме того, должно выполняться условие наследоваия.

6. Процедура – демон. Существуют следующие типы процедур – демонов: если-необходимо, если-изменено, если-добавлено, если-удалено.

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

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

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

Вывод во фреймовой системе.

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

Таким образом, можно выделить три основных процесса, про­исходящих во фреймовых системах:

1. Создание экземпляра фрейма. Для создания экземпляра фрейма необходимо найти подходящий фрейм и заполнить его слоты информацией, описывающей специфику рассматриваемой ситуации. Для того чтобы заполнить слоты используется специ­альная информация о том, как найти потенциальные «заполните­ли» слотов. Эта информация часто хранится в процедурной форме.

2. Активация фреймов. В том случае, когда фрейм считается подходящим для описания данной ситуации, осуществляется его активация глобальным процессом. Если обнаруживается слишком много отличий содержимого фреймов от специфических особен­ностей рассматриваемой ситуации или они носят достаточно серь­езный характер, организуется поиск другого, более подходящего фрейма. При этом «отвергнутый» фрейм может содержать указа­ния на то, какие именно фреймы следует исследовать вместо дан­ного (например, более общие или наоборот, более специализиро­ванные). Часть данных, используемых для заполнения слотов «от­вергнутого» фрейма, может быть использована при рассмотрении новых кандидатов.

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

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

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

1. Когда активировать фрейм? Подобно «демонам» фреймы могут активировать сами себя в случае, если распознана соответ­ствующая ситуация.

3. Когда осуществлять заполнение слотов - в момент вызова или позднее, по мере необходимости?

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

Неопределенность.

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

В основном определяют четыре источника неопределенных знаний в интеллектуальных СПР: неизвестные данные, неточный язык, неявное смысловое содержание и трудности, связанные с сочетанием взглядов различных экспертов.

Хотя неопределенность широко распространена в реальном мире, ее обработка в практических системах ИИ является весьма ограниченной.

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

Поэтому необходимо улучшать методы работы с неопределенностью.

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

Вероятностный вывод.

Вероятностный подход.

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

Рассмотрим основные положения байесовского метода и правило Байеса.

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

Условная вероятность математически обозначается как Р(А |B) , в которой вертикальная черта изображает «имело место», а полное выражение вероятности интерпретируется как «Условная вероятность того, что произойдет событие А В ».

p(А |B)= (6.1)

Количество возможных совместный проявлений А и В , или вероятность того, что А и В произойдут совместно, называется совместной вероятностью А и В .

Математически это представляется Р(АÇВ) .

Количество способов возможного проявления В является вероятностью В , Р(В) , и тогда

(6.2)

Так же, условная вероятность того, что произойдет событие В при условии, что имело место событие А определяется

(6.3)

p(ВÇА) =p(В|А)´p(А) (6.4)

Совместная вероятность является коммутативной, таким образом

p(АÇВ)= p(ВÇ А)

Следовательно

p(АÇВ) =p(В|А)´Р(А) (6.5)

Подстановка (6.5) в (6.2) приводит к следующему уравнению:

(6.6)

p(А|В) А при условии, что имело место событие В ;

p(В|А) – условная вероятность того, что произойдет событие В при условии, что имело место событие А ;

p(А) А;

p(В) - вероятность того, что произойдет событие В .

Уравнение (6.6) известно как правило (или формула) Байеса, которое названо именем Томаса Байеса, британского математика XVIII века, который предложил это правило.

Понятие условной вероятности предлагается, когда считается, что событие А было зависимым от события В . Этот принцип может быть расширен на случай, когда событие А зависит от некоторого числа несовместимых событий В 1 , В 2 , …, В n .

Следующее множество уравнений может быть выведено из (6.2):

p(АÇВ 1) =p(А|В 1)´p(В 1)

p(АÇВ 2) =p(А|В 2)´p(В 2)

p(АÇВ n) =p(А|В n)´p(В n)

Или после объединения.

(6.7)

Если (6.7) просуммировано по всему полному перечню событий B i , мы получаем

(6.8)

Это приводит к следующему уравнению условной вероятности, т.е. Р(А) выражается с помощью формулы полной вероятности:

(6.9)

Если проявление события А зависит только от двух взаимно исключающих событий, например В и НЕ В , тогда (6.9) будет выглядеть так:

p(А)=p(А|B)´p(B)+p(A\ØB)´p(ØB) (6.10)

Где Ø - логическое НЕ.

p(В)=p(В|А)´p(А)+p(В\ØА)´p(ØА) (6.11)

Подставим теперь (6.11) в формулу Байеса (6.6), что приводит к

Уравнение (6.12) обеспечивает основу использования теории вероятности для управления неопределенностью в интеллектуальных системах.

Байесовский вывод.

Используя уравнение (6.12) мы можем теперь от теории вероятностей обратить наше внимание вновь к интеллектуальным системам . Допустим все правила в БЗ представлены в следующей форме:

Если Н истинно

Тогда С истинно {с вероятностью р }.

Это правило подразумевает, что если событие Н происходит, тогда вероятность, что событие С произойдет р .

Что будет, если событие С произошло, но мы не знаем, произошло ли событие Н ? Рассмотрим возможность вычисления вероятности того, что событие Н также произошло.

Уравнение (6.12) позволяет нам это сделать. Мы просто используем Н и С вместо А и В . В интеллектуальных системах Н обычно обозначает гипотезы, а С – свидетельства в поддержку этих гипотез.

Таким образом, уравнение (6.12), выраженное в терминах гипотез и свидетельств, выглядит так

p(Н) – априорная (безусловная) вероятность того, что гипотеза Н является истинной;

p(С|Н) – вероятность того, что гипотеза Н является истинной, будет результатом свидетельства С ;

p(ØН) - априорная (безусловная) вероятность того, что гипотеза Н является ложной;

p(С|ØН) – вероятность нахождения свидетельства С даже когда гипотеза Н ложна.

Уравнение (6.13) предполагает, что вероятность гипотезы Н , p(Н) должна быть определена перед тем, как проверены какие-либо свидетельства.

В интеллектуальных СПР вероятности требуются для решения задачи, которые ставят эксперты. Эксперт определяет априорные вероятности для возможной гипотезы p(Н) и p(ØН) , а также условные вероятности для наблюдаемого свидетельства С , если гипотеза Н истинна, p(С|Н) , и если гипотеза Н ложна, p(С|ØН) . Пользователи обеспечивают информацию о наблюдаемом свидетельстве и интеллектуальная система вычисляет p(С|Н) для гипотезы Н в свете представленного пользователем свидетельства С . Вероятность p(С|Н) называется апостериорной вероятностью гипотезы Н при наблюдаемом свидетельстве С .

Рассмотрим ситуации, когда эксперт, основываясь на простом свидетельстве С , не может выбрать простую гипотезу, но скорее обеспечивает многочисленные гипотезы Н 1 , Н 2 ,…, Н т. Или когда имеются многочисленные свидетельства С 1 , С 2 , …, С n и эксперт также выдает множество гипотез.

Мы можем обобщить уравнение (6.13) принимая во внимание и многочисленные гипотезы Н 1 , Н 2 , …, Н т и многочисленные свидетельства С 1 , С 2 , …, С n . Но гипотезы, так же как и свидетельства должны быть взаимно исключающими.

Для простого свидетельства С и многочисленных гипотез Н 1 , Н 2 , …, Н т следует:

(6.14)

Для многочисленных свидетельств С 1 , С 2 , …, С n и многочисленных гипотез Н 1 , Н 2 , …, Н т следует:

(6.15)

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

Поэтому в интеллектуальных СПР и ЭС, тонкости совместного влияния многочисленных свидетельств должны не учитываться, а допускаться условная независимость между различными свидетельствами.

Следовательно, вместо неосуществимого уравнения (6.15) мы получаем

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

Предположим, что эксперт, имея три условно независимых свидетельства С 1 , С 2 и С 3 , создает три взаимно исключающие гипотезы Н 1 , Н 2 и Н 3 и обеспечивает априорные вероятности для этих гипотез – p(Н 1) , p(Н 2) и p(Н 3) соответственно. Эксперт также определяет условные вероятности каждого отмеченного свидетельства для всех возможных гипотез.

В Таблице 6.1. показаны априорные и условные вероятности, обеспеченные экспертом.

Таблица 6.1.

Априорные и условные вероятности.

Допустим, что мы сначала наблюдаем свидетельство С 3 . Интеллектуальная система вычисляет апостериорные вероятности для всех гипотез по уравнению (6.14):

Таким образом

Как можно видеть, после того, как наблюдается свидетельства С 3 , доверие гипотезе Н 2 и становится равным доверию гипотезе Н 1 . Доверие гипотезе Н 3 также возрастает и даже приблизительно достигает доверию гипотезам Н 1 и Н 2 .

Предположим теперь, что мы наблюдаем свидетельство С 1 . Апостериорные вероятности рассчитываются по уравнению (6.16):

Таким образом

Гипотеза Н 2 теперь рассматривается как наиболее вероятная, т.к. доверие гипотезе резко уменьшается.

После наблюдения свидетельства С 2 интеллектуальная СПР также вычисляет последние апостериорные вероятности для всех гипотез:

Таким образом

Хотя первоначальное ранжирование, предложенное экспертом было Н 1 , Н 2 и Н 3 , только гипотезы Н 1 и Н 3 остались для рассмотрения после всех свидетельств (С 1 , С 2 и С 3 ), которые наблюдались. Гипотеза Н 2 теперь может быть полностью исключена.

Заметим, что гипотеза Н 3 теперь рассматривается как более предпочтительная, чем гипотеза Н 1 .

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

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

Дуда, Харт и Нильсон видоизменили формулы Байеса для выводов в инженерии знаний и предположили метод выводов, названный субъектным байесовским методом.

Основные цели этого метода были успешно реализованы ими в экспертной системе PROSPECTOR .

Приближенные рассуждения.

В классической теории исчисления высказываний выражение «Если А , Тогда В », где А и В – пропозициональные переменные (пропозициональная переменная – это переменная для предложений, которые рассматриваются лишь с точки зрения их истинности или ложности), записывается как А®В , где импликация (®) рассматривается как связка, смысл которой определяется таблицей истинности.

Таким образом А®ВºØАÚВ (6.17)

В том смысле, что А®В (А влечет В) и ØАÚВ (не А или В) имеют идентичные таблицы истинности. Более важным в нашем случае является неопределенное высказывание «Если А , Тогда В », коротко А®В , в котором А (антецедент) и В (консеквент) – нечеткие множества, а не пропозициональные переменные («пропозиция» означает предложение, выражение, высказывание).

Типичные примеры высказываний:

Если «большой», Тогда «малый»

Если «скользкий», Тогда «опасный;»

Они являются сокращениями предложений:

Если х-«большой», Тогда у-«малый»;

Если дорога «скользкая», Тогда езда «опасна».

В сущности предложения этого вида описывают отношения между двумя неопределенными переменными. Это означает что неопределенное высказывание следует скорее определить как нечеткое отношение в смысле (5.25), а не как связку в смысле (6.17).

Здесь целесообразно определить сначала декартово произведение двух нечетких множеств.

Пусть А -нечеткое подмножество области рассуждений U и пусть В - нечеткое подмножество другой области рассуждений V. Тогда декартово произведение А и В , обозначаемое А´В , определяется следующим образом

(6.18)

где U´V означает декартово произведение множеств U и V , т.е.

Заметим, что когда А и В – не нечеткие, (6.18) преобразовывается в обычное определение декартова произведения множеств.

Иными словами, (6.18) означает, что А´В нечеткое множество упорядоченных пар (u,v ), , со степенью принадлежности (u,v) к (А´В), задаваемой формулой . В этом смысле А´В есть нечеткое отношение U и V .

Пример 6.1. Пусть

U=1+2 (6.19)

V=1+2+3 (6.20)

A=1/1+0,8/2 (6.21)

B=0,6/1+0,9/2+1/3 (6.22)

А´В=0,6/(1,1)+0,9/(1,2)+1/(1,3)+0,6/(2,1)+0,8/(2,2)+0,8/(2,3) (6.23)

Отношение, определенное в (6.17) можно представить матрицей отношения

Смысл нечеткого высказывания вида «Если А , Тогда В » становится ясен, если рассматривать его как специальный случай условного высказывания «Если А , Тогда В , Иначе С », где А , В и С – нечеткие подмножества, возможно, различных областей U и V , соответственно.

В терминах декартова произведения последнее предложение определяется так:

Если А , Тогда В , Иначе С (6.25)

Где + означает объединение нечетких множеств А´В и (ØА´С).

Чтобы обобщить понятие материальной импликации на нечеткие множества, предположим, что U и V – два возможно различных универсальных множества, а А, В и С – нечеткие подмножества множеств U, V и V соответственно.

Сначала определим смысл высказывания

Если А , Тогда В , Иначе С , и затем определим

Если А , Тогда В как частный случай высказывания Если А , Тогда В , Иначе С .

Определение. Высказывание Если А , Тогда В , Иначе С есть бинарное нечеткое отношение в U´V , определяемое следующим образом:

Если А, Тогда В, Иначе С=А´В+ØА´С (6.26)

То есть, если А,В и С – унарные нечеткие отношения в U, V и V , тогда Если А , Тогда В , Иначе С – бинарное нечеткое отношение в U´V , которое является объединением декартова произведения А и В (см.(5.23)) и декартова произведения отрицания А и С .

Далее высказывание Если А , Тогда В можно рассматривать как частный случай высказывания Если А , Тогда В , Иначе С при допущении, что С – полное множество V .

Т.о. Если А , Тогда В Если А , Тогда В , Иначе V=А´В+ØА´V (6.27)

В сущности это равнозначно интерпретации высказывания Если А , Тогда В высказыванием Если А , Тогда В , Иначе безразлично.

Пример 6.2. Иллюстрация (6.26) и (6.27)

Предположим, что

А=малый=1/1+0,4/2

В=большой=0,4/2+1/3

С=не большой=1/1+0,6/2

Тогда Если А , Тогда В , Иначе С=(1/1+0,4/2)´(0,4/2+1/3)+(0,6/2+1/3)´ (1/1+0,6/2)=0,4/(1,2)+1/(1,3)+0,6/(2,1)+0,6/(2,2)+0,4/(2,3)+1/(3,1)+0,6/(3,2)

Что можно представить в виде матрицы отношения

Если А , Тогда В , Иначе С=

Аналогично

Если А , Тогда В=(1/1+0,4/2)´(0,4/2+1/3)+(0,6/2+1/3)´(1/1+1/2+1/3) =0,4/(1,2)+1/(1,3)+0,6/(2,1)+0,6/(2,2)+0,6/(2,3)+1/(3,1)+1/(3,2)+1/(3,3)

Или эквивалентно

Если А , Тогда В=

Вывод в нейронных сетях.

Сеть Хопфилда.

Хопфилд использовал функцию энергии как инструмент для построения рекуррентных сетей и для понимания их динамики . Формализация Хопфилда сделала ясным принцип хранения информации как динамически устойчивых аттракторов и популяризовала использование рекуррентных сетей для ассоциативной памяти и для решения комбинаторных задач оптимизации.

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

Ассоциативная память

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

Ассоциативная память обычно работает в двух режимах: хранения и восстановления. В режиме хранения веса связей в сети определяются так, чтобы аттракторы запомнили набор p n -мерных образцов {x 1 , x 2 ,..., x p }, которые должны быть сохранены. Во втором режиме входной пример используется как начальное состояние сети, и далее сеть эволюционирует согласно своей динамике. Выходной образец устанавливается, когда сеть достигает равновесия.

Сколько примеров могут быть сохранены в сети с n бинарными элементами? Другими словами, какова емкость памяти сети? Она конечна, так как сеть с n бинарными элементами имеет максимально 2n различных состояний, и не все из них являются аттракторами. Более того, не все аттракторы могут хранить полезные образцы. Ложные аттракторы могут также хранить образцы, но они отличаются от примеров обучающей выборки.

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

Некоторые другие обучающие алгоритмы из таблицы 6.3 описаны в следующих работах: Adaline и Madaline , линейный дискриминантный анализ , проекции Саммона , анализ главных компонентов .

Процесс развития ИНС.

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

Как показано на рис. 6.8., процесс развития приложения ИНС имеет девять шагов.

На шаге 1 собираются данные, которые должны использоваться для обучения и проверки сети.

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

На шаге 2 должны быть установлены обучающие данные и должен быть создан план для проверки выполнения сети.

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

Существующие модели нейронных сетей имеют параметры, которые настраивают сеть на желаемый уровень исполнения. Частью процесса на шаге 5 является инициализация весов и параметров сети, которая также следует после получения отклика об исполнении. Часто первоначальные значения важны для определения эффективности и продолжительности обучения. Следующая процедура на шаге 6 преобразует используемые данные в тип и формат, требуемые нейронной сетью. Это может означать использование программ для предварительной обработки данных. Хранение и манипулирование данными должно быть организовано для удобного и эффективного переобучения нейронной сети, когда это необходимо. Также способ представления и организации используемых данных часто определяет эффективность и, возможно, точность результатов, получаемы ИНС.

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

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

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

Рис.6.8. Последовательность процесса развития и настройки искусственной нейронной сети.

«Тема 4: Лекция 9: Методы вывода и поиска решений в продукционных системах. Методы вывода на основе прямой и обратной цепочек. При продукционном...»

Сахнюк П.А.

Тема 4:

Лекция 9: Методы вывода и поиска решений в продукционных системах.

Методы вывода на основе прямой и обратной цепочек.

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

продукционных правил а данные представляются множеством фактов о

ЕСЛИ ТОГДА,

текущей ситуации.

Механизм вывода сопоставляет каждое правило, хранящееся в БЗ с фактами,

Рис.1. Цикл механизма вывода через процедуру «сопоставление – срабатывание»

Сопоставление частей если правил с фактами создает цепочку вывода. Цепочка вывода показывает как ЭС применяет правила для получения заключения. Для иллюстрации метода вывода на основе цепочки, рассмотрим простой пример.

Допустим, БД первоначально включает факты А,В,С,D и Е, а БЗ содержит только три правила:

Правило 1. Y&D Z Правило 2.

X&B&EY Правило 3. AX Цепочка вывода на рис. 2. показывает, как ЭС применяет правила для вывода факта Z.

Сахнюк П.А.

Рис.2. Пример цепочки вывода.

Сначала срабатывает Правило 3 для вывода нового факта Х изданного факта A.

Тогда Правило 2 выполняется для вывода факта Y из первоначально фактов В и Е, а также уже известного факта Х. И наконец, Правило 1 применяет первоначально известный факт D и только что полученный факт Y для прихода и заключению Z.

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

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

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

Продукционные системы, в которых сначала анализируется антецедентная часть (условия), имеют так называемую условно-выводимую архитектуру. Примером экспертной системы такой архитектуры является META-DENDRAL.

Альтернативным типом архитектуры, которая достаточно часто используется в экспертных системах, являются целе-выводимые (действие-выводимые или консеквентвыводимые) продукционные системы. Например, правило вида А&В&СD может быть интерпретировано, как «Логическая конъюнкция А, В и С влечет D» или «Чтобы доказать D, необходимо установить А, В, С».

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

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

Сахнюк П.А.

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

БД: АF Правило 1: A&B&CD Правило 2: D&FG Правило 3:A&JG Правило 4: ВС Правило 5: FB Правило 6: LJ Правило 7: GH Предположим, цель состоит в том, чтобы вывести истинность Н.

В первую очередь проверяется, находится ли Н в БД? Так как в данном случае это не так, то система пытается вывести истинность Н, используя правила, имеющие Н в правой части. Таким является правило 7. Теперь система пытается вывести истинность G, так как истинность последнего влечет за собой истинность Н. Снова проверяется БД: в БД нет G, следовательно, организуется полек правила, содержащего G в правой части. Таких правил несколько (два или три). В качестве стратегии «разрешения конфликта» будем считать, что правила упорядочены по приоритету, причем правилу с наименьшим номером соответствует больший приоритет.

В данном случае выбирается правило 2, поэтому целью теперь становится вывести истинность D и F. Для этого достаточно показать, что А - истинно (так как находится в БД), В - истинно (согласно правилу 5), С - истинно (согласно правилу 4). Так как истинность D и F доказана, то из правила 2 следует истинность G, а из истинности G следует истинность Н (правило 7). Таким образом цель достигнута. Элементы, истинность которых доказана, добавляются в БД. В данном случае это - элементы Н, G, D, С. В.

Примерами целе-выводимой архитектуры является MYCIN.

Общие методы поиска решений в пространстве состояний.

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

Сахнюк П.А.

Задачу поиска в пространстве состояний можно сформулировать в общем виде так:

Пусть исходная задача описывается тройкой (S, F, T), где S – множество начальных состояний; F – множество операторов, отображающих одни состояния в другие; T – множество целевых состояний. Решение задачи состоит в нахождении (fi F), которые преобразуют начальные последовательности операторов f1,f2,…,fk состояния в конечные. Задача поиска в пространстве состояний описывается с помощью понятий теории графов . Задается начальная вершина (исходное состояние) и множество целевых вершин T. Для построения пространства состояний используются операторы F. Последовательно от корня к вершинам дерева применяются операторы, относящиеся к этому уровню, для построения вершин-преемников следующего уровня (раскрытие вершин). Дуги идентифицируются как операторы преобразования.

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

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

Поиск в ширину. Вершины раскрываются в последовательности их порождения.

Поиск идет по ширине дерева, т. к. раскрытие вершины происходит вдоль одного уровня.

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

Сахнюк П.А.

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

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

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

отрицательное влияние при реализации других путей. Т. о. много полезной информации отбрасывается и не используется при анализе дальнейших направлений поиска.

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

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

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

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

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

Кроме того, эвристический поиск с использование оценочной функции предполагает Сахнюк П.А.

достоверное знание пространства состояний. Однако в реальной практике при принятии решений сталкиваются с фактами и знаниями недостаточно полными и определенными.

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

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

Несмотря на то, что рассуждения здравого смысла являются довольно обыденными для людей, очень трудно достигнуть требуемого уровня реализации подобных рассуждений в ИИ. (Тем не менее, в некоторых классических ЭС, таких как MYCIN, PROSPECTOR, этот метод довольно успешно реализован для сокращения пространства поиска.

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

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

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

их в свою очередь, также сводят к подзадачам. Это продолжается до тех пор, пока каждая подзадача не будет иметь очевидное решение.

Сахнюк П.А.

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

Процесс поиска решения исходной задачи при таком описании представляет собой направленный граф редукции задач. Этот граф называется графом И/ИЛИ. Вершины этого графа представляют описания задач и подзадач. Граф И/ИЛИ содержит вершины двух типов. Тип “И” – соответствует задаче, решаемой при условии реализации всех ее подзадач в соответствующих вершинах – преемниках. Тип “ИЛИ” – соответствует задаче, решение которой возможно получить при решении одной из альтернативных подзадач в соответствующих вершинах – преемниках. На рис. 4. представлены фрогменты графов типа И/ИЛИ.

б) Рис. 4. Представление разбиения исходной задачи на подзадачи в виде графа И/ИЛИ (а) и преобразование графа И/ИЛИ (б).

Исходная задача S0 разбивается на группы подзадач. Она может быть решена путем решения подзадач либо S1 и S2; либо S3; S4 и S5. Вершины N, S3, M, S5 – это вершины типа “И”. Штриховой линией показан вариант решающего графа исходной задачи. Решения подзадач S2, S7, S9, S10, S11 - предполагают известными. Решения других подзадач неизвестны. В структуру обычно вводятся дополнительные вершины, чтобы каждое множество подзадач формировалось под своей собственной родительской вершиной.

Сахнюк П.А.

Вершина графа И/ИЛИ может принадлежать к типу И либо ИЛИ. Поэтому исходный граф преобразуется и вводятся дополнительные вершины N и M, которые служат отдельными родительскими вершинами для подзадач {S1, S2} и {S4, S5. Таким образом, вершина S0 преобразуется в вершину ИЛИ.

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

Процесс поиска на графе И/ИЛИ заключается в построении решающего графа (или дерева решений), который является подграфом графа редукции.

Методы поиска решений в больших пространствах состояний.

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

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

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

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

Сахнюк П.А.

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

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

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

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

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

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

Переход к более конкретному уровню осуществляется лишь после завершения решения на рассматриваемом уровне абстракции.

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

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

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

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

Классификация ошибок

Internet-ресурсы

План лекции

Отладка программного обеспечения

Лекция №8.

Тамбов 2011

Курс, группы БИС-11, БИС-12

Тема 6. Отладка программного обеспечения

Лекция 8

Дисциплина Технология программирования

Направление 230400 «Информационные системы и технологии»

Преподаватель: Минин Юрий Викторович

Цель лекции

Целью лекции является дать представление о процессе и методах отладки программного обеспечения.

1. Классификация ошибок

2. Методы отладки программного обеспечения

3. Методы и средства получения дополнительной информации об ошибке

4. Методика отладки программного обеспечения

Список литературы

Основная литература

1. Иванова Г.С. Технология программирования М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - 320 с.

2. Жоголев Е.А. Технология программирования М.: Научный мир, 2004. - 216 с.

3. Гагарина Л.Г., Кокорева Е.В., Виснадул Б.Д. Технология разработки программного обеспечения. М.: ИД "ФОРУМ" - ИНФРА-М, 2008. - 400с.

Дополнительная литература

1. Канер С., Фолк Д., Нгуен Е. Тестирование программного обеспечения. М.: ДиаСофт, 2001. - 544с.

2. Брауде Э. Технология разработки программного обеспечения. СПб.: Питер, 2004. - 655 с.

3. Баранов С.Н., Домарацкий А.Н., Ласточкин Н.К., Морозов В.П. Процесс разработки программных изделий. М.: ФИЗМАТЛИТ, Наука, 2000. - 176с.

1. www.intuit.ru - Интернет-университет информационных технологий.

2. http://citforum.ru/ - Центр информационных технологий.

3. http://www.tstu.ru/r.php?r=education - Электронная библиотека ТГТУ.

4. http://www.edu.ru/ - Библиотека Федерального портала «Российское образование»

Отладка программы - один их самых сложных этапов разработки программного обеспечения, требующий глубокого знания:

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

Операционной системы,

Среды и языка программирования,

Реализуемых процессов,

Природы и специфики различных ошибок,

Методик отладки и соответствующих программных средств.

Обсуждению последних двух вопросов и посвящается данная лекция.

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

В целом сложность отладки обусловлена следующими причинами:

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

Психологически дискомфортна, так как необходимо искать собственные ошибки и, как правило, в условиях ограниченного времени;

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

Отсутствуют четко сформулированные методики отладки.

В соответствии с этапом обработки, на котором проявляются ошибки, различают (рис. 1):

- синтаксические ошибки - ошибки, фиксируемые компилятором (транслятором, интерпретатором) при выполнении синтаксического и частично семантического анализа программы;

- ошибки компоновки - ошибки, обнаруженные компоновщиком (редактором связей) при объединении модулей программы;

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

Рисунок 1 - Классификация ошибок по этапу обработки программы

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

Следует иметь в виду, что чем лучше формализованы правила синтаксиса языка, тем больше ошибок из общего количества может обнаружить компилятор и, соответственно, меньше ошибок будет обнаруживаться на следующих этапах. В связи с этим говорят о языках программирования с защищенным синтаксисом и с незащищенным синтаксисом. К первым, безусловно, можно отнести Pascal, имеющий очень простой и четко определенный синтаксис, хорошо проверяемый при компиляции программы, ко вторым – C/C++ со всеми их модификациями. Чего стоит хотя бы возможность выполнения присваивания в условном операторе в С/С+, например:

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

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

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

Появление сообщения об ошибке, зафиксированной схемами контроля выполнения машинных команд, например, переполнении разрядной сетки, ситуации “деление на ноль”, нарушении адресации и т. п.;

Появление сообщения об ошибке, обнаруженной операционной системой, например, нарушении защиты памяти, попытке записи на устройства, защищенные от записи, отсутствии файла с заданным именем и т. п.;

- «зависание» компьютера, как простое, когда удается завершить программу без перезагрузки операционной системы, так и «тяжелое», когда для продолжения работы необходима перезагрузка;

Несовпадение полученных результатов с ожидаемыми.

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

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

Неверное определение исходных данных,

Логические ошибки,

Накопление погрешностей результатов вычислений (рис. 2).

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

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

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

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

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

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

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

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

Опосредованного проявления ошибок;

Возможности взаимовлияния ошибок;

Возможности получения внешне одинаковых проявлений разных ошибок;

Отсутствия повторяемости проявлений некоторых ошибок от запуска к запуску (стохастические ошибки);

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

Написания отдельных частей программы разными программистами.

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

Ручного тестирования;

Индукции;

Дедукции;

Обратного прослеживания.

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

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

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

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

Рисунок 3 - Схема процесса отладки методом индукции

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

В процессе доказательства пытаются выяснить, все ли проявления ошибки объясняет данная гипотеза, если не все, то либо гипотеза не верна, либо ошибок несколько.

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

Рисунок 4 - Схема процесса отладки методом дедукции

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

Лекция 9. Управление вводом-выводом данных

9.1 Принципы аппаратуры ввода-вывода

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

Рис. 1. Структура системы ввода-вывода

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

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

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

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

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

Подсистема ОС для управления вводом-выводом с точки зрения программных процессов является интерфейсом с ПУ. Различают три типа действий с ПУ:

1. операции чтения-записи данных;

2. операции управления ПУ;

3. операции по проверке состояния ПУ.

9.1.1 Устройства ввода-вывода

Устройства делят на две категории (некоторые не попадают ни в одну):

• блочные устройства - информация считывается и записывается по блокам, блоки имеют свой адрес (диски)
• символьные устройства - информация считывается и записывается посимвольно (принтер, сетевые карты, мыши)

9.1.2 Контроллеры устройств

Устройства ввода-вывода обычно состоят из двух частей:

• механическая (не надо понимать дословно) - диск, принтер, монитор
• электронная - контроллер или адаптер

Если интерфейс между контроллером и устройством стандартизован (ANSI, IEEE или ISO), то независимые производители могут выпускать совместимые как контроллеры, так и устройства. Например: диски IDE или SCSI.

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

9.1.3 Отображаемый на адресное пространство памяти ввод-вывод

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

У многих устройств есть буфер данных (например: видеопамять).

Реализации доступа к управляющим регистрам и буферам:

• номер порта ввода-вывода - назначается каждому управляющему регистру 8- или 16-рзрядное целое число. Адресные пространства ОЗУ и устройства ввода-вывода в этой схеме не пересекаются.
  Недостатки
  - для чтения и записи применяются специальные команды, например IN и OUT
  - необходим специальный механизм защиты от процессов
  - необходимо сначала считать регистр устройства в регистр процессора

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

• смешанная реализация - используется в х86 и Pentium,
  от 0 до 64К отводится портам,
  от 640 до 1М зарезервировано под буферы данных.

Способы реализации доступа к управляющим регистрам и буферам

9.1.4 Прямой доступ к памяти (DMA - Direct Memory Access)

Прямой доступ к памяти реализуется с помощью DMA - контроллера .

Контроллер содержит несколько регистров:

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

Без контроллера происходит следующее:

1. Процессор дает команду дисковому контроллеру прочитать данные в буфер,
2. Считываются данные в буфер, контроллер проверяет контрольную сумму считанных данных (проверка на ошибки). Процессор, до прерывания, переключается на другие задания.
3. Контроллер диска инициирует прерывание
4. Операционная система начинает работать и может считывать из буфера данные в память

Работа DMA - контроллера

С контроллером происходит следующее:

1. Процессор программирует контроллер (какие данные и куда переместить)
2. Процессор дает команду дисковому контроллеру прочитать данные в буфер
3. Считываются данные в буфер, контроллер диска проверяет контрольную сумму считанных данных, (процессор, до прерывания, переключается на другие задания).
4. Контроллер DMA посылает запрос на чтение дисковому контроллеру
5. Контроллер диска поставляет данные на шину, адрес памяти уже находится на шине, происходит запись данных в память
6. Когда запись закончена, контроллер диска посылает подтверждение DMA контроллеру
7. DMA контроллер увеличивает используемый адрес и уменьшает значение счетчика байтов
8. Все повторяется с пункта 4, пока значение счетчика не станет равной нулю.
9. Контроллер DMA инициирует прерывание

Операционной системе не нужно копировать данные в память, они уже там.

9.1.5 Прерывания

После того как устройство ввода-вывода начало работу, процессор переключается на другие задачи.

Чтобы сигнализировать процессору об окончании работы, устройство инициализирует прерывание, выставляя сигнал на выделенную устройству линию шины (а не выделенный провод).

Контроллер прерываний - обслуживает поступающие прерывания от устройств.

1. Если необработанных прерываний нет, прерывание выполняется немедленно.
2. Если необработанных прерываний есть, контроллер игнорирует прерывание. Но устройство продолжает удерживать сигнал прерывания на шине до тех пор, пока оно не будет обработано.

Работа прерываний

Алгоритм работы:

• Устройство выставляет сигнал прерывания
• Контроллер прерываний инициирует прерывание, указывая номер устройства
• Процессор начинает выполнять обработку прерывания, вызывая процедуру
• Эта процедура подтверждает получение прерывания контроллеру прерываний

9.2 Принципы программного обеспечения ввода-вывода

9.2.1 Задачи программного обеспечения ввода-вывода

Основные задачи, которые должно решать программное обеспечение ввода-вывода:

• Независимость от устройств - например, программа, читающая данные из файла не должна задумываться с чего она читает (CD, HDD и др.). Все проблемы должна решать ОС.
• Единообразное именование - имя файла или устройства не должны отличаться. (В системах UNIX выполняется дословно).
• Обработка ошибок - ошибки могут быть отловлены на уровне контроллера, драйвера и т.д.
• Перенос данных - синхронный и асинхронный (в последнем случае процессор запускает перенос данных, и переключается на другие задачи до прерывания).
• Буферизация
• Проблема выделенных (принтер) и невыделенных (диск) устройств - принтер должен предоставляться только одному пользователю, а диск многим. ОС должна решать все возникающие проблемы.

Три основных способа осуществления операций ввода-вывода:

• Программный ввод-вывод
• Управляемый прерываниями ввод-вывод
• Ввод-вывод с использованием DMA

Рассмотрим их подробнее.

9.2.2 Программный ввод-вывод

В этом случае всю работу выполняет центральный процессор.

Рассмотрим процесс печати строки ABCDEFGH этим способом.

Этапы печати строки ABCDEFGH

Алгоритм печати:

1. Строка для печати собирается в пространстве пользователя.
2. Обращаясь к системному вызову, процесс получает принтер.
3. Обращаясь к системному вызову, процесс просит распечатать строку на принтере.
4. Операционная система копирует строку в массив, расположенный в режиме ядра.
5. ОС копирует первый символ в регистр данных принтера, который отображен на памяти.
6. Символ печатается на бумаге.
7. Указатель устанавливается на следующий символ.
8. Процессор ждет, когда бит готовности принтера выставится в готовность.
9. Все повторяется.

При использовании буфера принтера, сначала вся строка копируется в буфер, после этого начинается печать.

9.2.3 Управляемый прерываниями ввод-вывод

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

Рассмотрим тот же пример, но с небольшим усовершенствованием.

Алгоритм печати:

1. До пункта 8 тоже самое.
2. Процессор не ждет готовности принтера, а вызывает планировщик и переключается на другую задачу. Печатающий процесс блокируется.
3. Когда принтер будет готов, он посылает прерывание процессору.
4. Процессор переключается на печатающий процесс.

9.2.4 Ввод-вывод с использованием DMA

Недостаток предыдущего метода в том, что прерывание происходит при печати каждого символа.

Алгоритм не отличается, но всю работу на себя берет контроллер DMA.

9.3 Программные уровни и функции ввода-вывода

Четыре уровня ввода-вывода:

Уровни ввода-вывода

9.3.1 Обработчики прерываний

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

Алгоритм:

1. Драйвер начинает операцию ввод-вывод.
2. Драйвер блокирует сам себя,
   - выполнив на семафоре процедуру down
   - выполнив на переменной состояния процедуру wait
   - выполнив на сообщении процедуру receive
3. Происходит прерывание
4. Обработчик прерываний начинает работу
5. Обработчик прерываний может разблокировать драйвер (например, выполнив на семафоре процедуру up)

9.3.2 Драйвера устройств

Драйвер устройства - необходим для каждого устройства. Для разных ОС нужны разные драйверы.

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

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

Логическое расположение драйверов устройств. На самом деле обмен данными между контроллерами и драйверами идет по шине.

Драйвера должны взаимодействовать с ОС через стандартные интерфейсы.

Стандартные интерфейсы, которые должны поддерживать драйвера:

• Для блочных устройств
• Для символьных устройств

Раньше для установки ядра приходилось перекомпилировать ядра системы.

Сейчас в основном ОС загружают драйверы. Некоторые драйверы могут быть загружены в горячем режиме.

Функции, которые выполняют драйвера:

• обработка запросов чтения или записи
• инициализация устройства
• управление энергопотреблением устройства
• прогрев устройства (сканера)
• включение устройства или запуска двигателя

9.3.3 Независимое от устройств программное обеспечение ввода-вывода

Функции независимого от устройств программного обеспечения ввода-вывода:

• Единообразный интерфейс для драйверов устройств,
• Буферизация
• Сообщения об ошибках
• Захват и освобождение выделенных устройств(блокирование)
• Размер блока, не зависящий от устройств

Единообразный интерфейс для драйверов устройств

Кроме интерфейса, в него также входят проблемы,

• именование устройств
• защита устройств

Буферизация

Рассмотрим несколько примеров буферизации.

a) Не буферизованный ввод - после ввода каждого символа происходит прерывание

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

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

d) Двойная буферизация в ядре - если один буфер заполнен, и пока он выгружается, символы пишутся во второй буфер.

Сообщения об ошибках

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

Захват и освобождение выделенных устройств

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

Независимый от устройств размер блока

Размер блока должен быть одинаковый для верхних уровней, и не зависеть от устройств (размеров секторов на диске).

9.4. Программное обеспечение ввода-вывода пространства пользователя

Функции этого обеспечения:

• Обращение к системным вызовам ввода-вывода (через библиотечные процедуры).
• Форматный ввод-вывод (меняют формат, например, в ASCII)
• Спулинг (для выделенных устройств) - создается процесс (например, демон печати) и каталог спулера.

Обобщение уровней и функций ввода-вывода

Уровни и основные функции системы ввода-вывода

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

Блокирующиеся, неблокирующиеся и асинхронные системные вызовы

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

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

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

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

Буферизация и кэширование

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

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

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

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

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

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

Spooling и захват устройств

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

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

В некоторых операционных системах вместо использования spooling для устранения race condition применяется механизм монопольного захвата устройств процессами. Если устройство свободно, то один из процессов может получить его в монопольное распоряжение. При этом все другие процессы при попытке осуществления операций над этим устройством будут либо блокированы (переведены в состояние ожидание ), либо получат информацию о невозможности выполнения операции до тех пор, пока процесс, захвативший устройство, не завершится или явно не сообщит операционной системе о своем отказе от его использования.

Обеспечение spooling и механизма захвата устройств является прерогативой базовой подсистемы ввода-вывода .

Обработка прерываний и ошибок

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

Одна и та же процедура обработки прерывания может применяться для нескольких устройств ввода-вывода (например, если эти устройства используют одну линию прерываний , идущую от них к контроллеру прерываний ), поэтому первое действие собственно программы обработки состоит в определении того, какое именно устройство выдало прерывание . Зная устройство, мы можем выявить процесс, который инициировал выполнение соответствующей операции. Поскольку прерывание возникает как при удачном, так и при неудачном ее выполнении, следующее, что мы должны сделать, – это определить успешность завершения операции, проверив значение бита ошибки в регистре состояния устройства. В некоторых случаях операционная система может предпринять определенные действия, направленные на компенсацию возникшей ошибки. Например, в случае возникновения ошибки чтения с гибкого диска можно попробовать несколько раз повторить выполнение команды. Если компенсация ошибки невозможна, то операционная система впоследствии известит об этом процесс, запросивший выполнение операции, (например, специальным кодом возврата из системного вызова). Если этот процесс был заблокирован до выполнения завершившейся операции, то операционная система переводит его в состояние готовность . При наличии других неудовлетворенных запросов к освободившемуся устройству операционная система может инициировать выполнение следующего запроса, одновременно известив устройство, что прерывание обработано. На этом, собственно, обработка прерывания заканчивается, и система может приступать к планированию использования процессора.

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

Планирование запросов

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

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

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

9. 5 . Принципы, заложенные в подсистему управления вводом-выводом в ОС UNIX

1. Эта подсистема построена единообразно с подсистемой управления данными (файловой системой). Пользователю предоставляется унифицированный способ доступа как к ПУ, так и к файлам. Под файлом в ОС UNIX понимают набор данных на диске, видеотерминале и т.д.; любое ПУ рассматривается как специальный файл. При запросе программного процесса о выводе данных в специальный файл ОС перехватывает запрос и направляет данные на соответствующее устройство. Аналогично организуется чтение данных из специального файла - это прием данных с ПУ. Таким образом, доступ, например, к файлу на диске и к специальному файлу дисплея обеспечивается одним и тем же набором системных вызовов.

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

3. Для управления ПУ в ОС UNIX используются 2 вида интерфейса с этими ПУ: байториентированный и блокориентированный. Блокориентированный интерфейс обеспечивает связь с ПУ, к которым можно адресоваться как к последовательности блоков по 512 байт. Такими ПУ в основном являются ВЗУ. Основой организации такого интерфейса является система буферизации, поддерживаемая в ОП. Байториентированный интерфейс используется для доступа к печатающему устройству, клавиатуре дисплея и некоторым другим устройствам, при этом буферизация не используется.

4. В состав системы управления вводом-выводом входят также драйверы и набор специальных таблиц для логического подключения ядра ОС к драйверам различных устройств. Каждый драйвер содержит 2 части и может обслуживать несколько устройств одного типа.

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

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

Некоторые из изложенных принципов построения системы ввода-вывода ОС UNIX были реализованы в ОС, созданных позднее, например, в MS DOS, функционирующей в ЭВМ IBM РС с МП типа 80х86.

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