Файл: А. В. Гордеев А. Ю. Молчанов системное программное обеспечение электронный вариант книги издательства Питер СанктПетербург Челябинск юургу каф. Автоматика и управление 2002 2 Предисловие Настоящий учебник.pdf

384
В этом случае К' = J, то есть тупик определён. Таблица заблокированных про- цессов (PWTBL) теперь имеет следующий вид.
Таблица 7.4, Таблица заблокированных процессов PWTBL
Процесс
Ресурс
1 3
2 2
3 5
Равенство J = К' означает, что существует замкнутая цепь взаимоисключаю- щих и ожидающих процессов, то есть выполняются все четыре условия существо- вания тупика.
Для описанного нами примера можно построить модель Холта; её изображе- ние приведено на рис. 7.14. На этом рисунке пронумерованы дуги запросов, кото- рые процессы последовательно генерировали в соответствии с нашим примером.
Из рисунка сразу видно, что в результате такой последовательности запросов обра- зовалась замкнутая цепочка: (8, 5, 6, 2, 7, 3), что и говорит о существовании тупика.
Рис. 7.14. Граф распределения ресурсов
Распознавание тупика требует дальнейшего восстановления.

385
Восстановление можно интерпретировать как запрет постоянного пребывания в опасном состоянии. Существуют следующие методы восстановления:
♦ принудительный перезапуск системы, характеризующийся потерей инфор- мации обо всех процессах, существовавших до перезапуска;
♦ принудительное завершение процессов, находящихся в тупике;
♦ принудительное последовательное завершение процессов, находящихся в тупике, с последующим вызовом алгоритма распознавания после каждого завер- шения до исчезновения тупика;
♦ перезапуск процессов, находящихся в тупике, с некоторой контрольной точки, то есть из состояния, предшествовавшего запросу на ресурс;
♦ перераспределение ресурсов с последующим последовательным перезапус- ком процессов, находящихся в тупике.
Основные издержки восстановления составляют потери времени на повторные вычисления, которые могут оказаться весьма существенными. К сожалению, в ряде случаев восстановление может стать невозможным: например, исходные данные,
поступившие с каких-либо датчиков, могут уже измениться, а предыдущие значе- ния будут безвозвратно потеряны.
Контрольные вопросы и задачи
Вопросы для проверки
1 Что такое тупиковое состояние? Перечислите условия, при которых возни- кает тупик.
2 Что является причиной возникновения тупиков на SR–pecypcax?
3 Приведите пример графа повторно используемых ресурсов. Что позволяет сделать эта модель Холта?
4 Приведите пример теоретико-множественного описания сети Петри.
5 Что такое маркировка сети Петри? Что представляет собой пространство возможных состояний сети Петри?
6 Приведите пример графического представления сети Петри.
7 Что представляет собой «предотвращение тупика»? Как его можно реализо- вать?

386 8 Что представляет собой «обход тупика»? Приведите алгоритм банкира
Дейкстры.
9 Что такое «опасное состояние»? Приведите пример опасного состояния на модели состояний системы.
10 Изложите метод обнаружения тупика посредством редукции графа повтор- но–используемых ресурсов.
11 Изложите алгоритм обнаружения тупика по наличию замкнутой цепочки запросов.
ГЛАВА 8 Современные операционные системы
В заключение первой части учебника кратко рассмотрим основные архитек- турные особенности современных ОС, которые используются на ПК типа IBM PC.
Прежде всего отметим тот общеизвестный факт, что наиболее популярными являются ОС семейства Windows компании Microsoft. Это и Windows 95/98, и Win- dows NT, и новое поколение Windows 2000. Однако, поскольку в настоящее время практически вся литература, связанная с программным обеспечением для ПК (в том числе и по системному программному обеспечению), в той или иной степени,
прежде всего, касается ОС этой компании, то в данном случае мы сделаем исклю- чение и не будем описывать ОС Windows. Желающие без труда найдут любую ли- тературу по этому вопросу.
Мы же кратко рассмотрим ОС UNIX (не Linux, по которому сейчас тоже появ- ляется немало монографий и учебников, а именно основы UNIX, которые в абсо- лютном своем большинстве относятся и к Linux), OS/2 (хотя эта система уже прак- тически всеми и забыта, но она была одной из первых, предоставивших пользова- телям ПК полноценную, мультипрограммную надёжную среду, и имеет много очень интересных и эффективных механизмов) и QNX (как наиболее известный и удачный вариант ОС для реализации систем реального времени).

387
Семейство операционных систем UNIX
Общая характеристика семейства операционных систем UNIX,
особенности архитектуры семейства ОС UNIX
UNIX является примером исключительно удачной реализации простой муль- типрограммной и многопользовательской операционной системы. В своё время она проектировалась как инструментальная система для разработки программного обеспечения. Своей уникальностью система UNIX обязана во многом тому обстоя- тельству, что она была, по сути, создана всего двумя разработчиками
1
, причём соз- дававшие её люди делали систему для себя, и первое время её использовали на ми- ни-ЭВМ с очень скромными вычислительными ресурсами. По этой причине UNIX,
прежде всего, обладает простым, но очень мощным командным языком и незави- симой от устройств файловой системой. Поскольку при создании этой ОС исполь- зовался язык высокого уровня, на котором пишутся не только системные, но и прикладные программы (речь идет о языке С), то система и приложения, выпол- няющиеся в ней, получились легко переносимыми (мобильными). Компилятор с языка С для всех оттранслированных программ дает реентерабельный и разделяе- мый код, что позволяет эффективно использовать имеющиеся в системе ресурсы.
Первой целью при разработке этой системы было стремление сохранить про- стоту и обойтись минимальным количеством функций. Все реальные сложности оставлялись пользовательским программам.
Второй целью была общность. Одни и те же методы и механизмы должны бы- ли использоваться во многих случаях. Поэтому общность в UNIX-системах прояв- ляется во многих аспектах, и в частности:
♦ обращения к файлам, устройствам ввода/вывода и буферам межпроцессных сообщений выполняются с помощью одних и тех же примитивов;
♦ одни и те же механизмы именования, присвоения альтернативных имен и защиты от несанкционированного доступа применяются к файлам с данными и ди- ректориями и устройствам;
1
Создателями системы UNIX считаются Кен Томпсон и Деннис Ритчи.

388
♦ одни и те же механизмы работают в отношении программно и аппаратно инициируемых прерываний.
Наконец, третья цель заключалась в создании операционной среды, в которой большие задачи можно было бы решать, комбинируя существующие небольшие программы, а не разрабатывая программы заново.
Важным, хотя и простым с позиций его реализации, является тот факт, что система UNIX предоставляет пользователям возможность направить выход одной программы непосредственно на вход другой (речь идет о программных каналах
(pipe). См. об этом ниже и в разделе «Конвейеры и очереди сообщений», глава 6). В
результате большие программные системы можно создавать путём композиции имеющихся небольших программ, а не путём написания новых, что в большинстве случаев упрощает задачу. UNIX-системы существуют уже 30 лет, и к настоящему времени имеется чрезвычайно большой набор легко переносимых из системы в систему отлично отлаженных и проверенных временем приложений.
UNIX-системы поставляются с большим набором системных и прикладных программ, включающим редакторы текстов, программируемые интерпретаторы командного языка, компиляторы с нескольких популярных языков программиро- вания, включая С, C++, ассемблер, PERL, FORTRAN и многие другие, компонов- щики (редакторы межпрограммных связей), отладчики, многочисленные библио- теки системных и пользовательских программ, средства сортировки и ведения баз данных, многочисленные административные и обслуживающие программы. Для абсолютного большинства этих программ имеется документация, включающая в себя такие важные документы, как исходные (как правило, снабженные хорошими комментариями) тексты программ. Кроме этого, описание и документация в боль- шей части доступны пользователю непосредственно за экраном в интерактивном режиме. Используется иерархическая файловая система с полной защитой, работа со съёмными томами, обеспечивается независимость от устройств.
Центральной частью системы UNIX является ядро (kernel).

389
Основные понятия системы UNIX
Одним из достоинств ОС UNIX является то, что система базируется на не- большом числе понятий; рассмотрим их вкратце. Необходимо заметить, что на- стоящий учебник не претендует на полноценное изложение основ работы в системе
UNIX и детальное описание её архитектуры. На эту тему имеется достаточное ко- личество специальной литературы, например отличная монография А. М. Робачев- ского [70]. Тем не менее, исходя из учебного плана и нашего опыта преподавания системного программного обеспечения, мы считаем полезным изложить здесь ми- нимальный набор основных понятий, который часто помогает студентам погру- зиться в мир UNIX, отличающийся от привычного всем окружения Windows.
Виртуальная машина
Система UNIX – многопользовательская. Каждому пользователю после реги- страции (входа в систему) предоставляется виртуальный компьютер, в котором есть все необходимые ресурсы: процессор (процессорное время выделяется на ос- нове «карусельной» диспетчеризации (RR – round robin) и с использованием дина- мических приоритетов с тем, чтобы обеспечить равенство в обслуживании), па- мять, устройства, файлы. Текущее состояние такого виртуального компьютера,
предоставляемого пользователю, называется образом. Можно сказать, что процесс
– это выполнение образа. Образ состоит из:
♦ образа памяти;
♦ значений общих регистров процессора;
♦ состояния открытых файлов;
♦ текущего директория (каталога файлов) и другой информации.
Образ процесса во время его выполнения размещается в основной памяти. В
старых версиях системы UNIX образ мог быть выгружен (откачан) на диск, если какому-либо более приоритетному процессу потребуется место в основной памяти.
В современных реализациях, поддерживающих, как правило, страничный меха- низм виртуальной памяти, прежде всего выгружаются неиспользуемые страницы.
Образ памяти делится на три логических сегмента:

390
♦ сегмент реентерабельных процедур (начинается с нулевого адреса в вирту- альном адресном пространстве процесса);
♦ сегмент данных (располагается следом за сегментом процедур и может рас- ти в сторону больших адресов);
♦ сегмент стека (начинается со старшего адреса и растет в сторону младших адресов по мере занесения в него информации при вызовах подпрограмм и при прерываниях).
Пользователь
Мы уже отмечали, что с самого начала ОС UNIX замышлялась как интерак- тивная многопользовательская система. Другими словами, UNIX предназначен для мультитерминальной работы. Чтобы начать работать, человек должен «войти» в систему, введя со свободного терминала свое учётное имя (account name) и, воз- можно, пароль (password). Человек, зарегистрированный в учётных файлах систе- мы и, следовательно, имеющий учётную запись (account), называется зарегистри- рованным пользователем системы. Регистрацию новых пользователей обычно вы- полняет администратор системы. Пользователь не может изменить своё учётное имя, но может установить и/или изменить свой пароль. Пароли хранятся в отдель- ном файле в закодированном виде.
Все пользователи ОС UNIX явно или неявно работают с файлами. Файловая система ОС UNIX имеет древовидную структуру [70]. Промежуточными узлами дерева являются каталоги со ссылками на другие каталоги или файлы, а листья де- рева соответствуют файлам или пустым каталогам. Каждому зарегистрированному пользователю соответствует некоторый каталог файловой системы, который назы- вается «домашним» (home) каталогом пользователя. При входе в систему пользо- ватель получает неограниченный доступ к своему домашнему каталогу и всем ка- талогам и файлам, содержащимся в нём. Пользователь может создавать, удалять и модифицировать каталоги и файлы, содержащиеся в домашнем каталоге. Потенци- ально возможен доступ и ко всем другим файлам, однако он может быть ограни- чен, если пользователь не имеет достаточных привилегий.

391
Интерфейс пользователя
Традиционный способ взаимодействия пользователя с системой UNIX осно- вывается на использовании командных языков (правда, поскольку в настоящее время всё большее распространение получают графические интерфейсы, то и в ОС
UNIX стали всё чаще работать в Х Window). После входа пользователя в систему для него запускается один из командных интерпретаторов (в зависимости от пара- метров, сохраняемых в файле /etc/passwd). Обычно в системе поддерживается не- сколько командных интерпретаторов с похожими, но различающимися своими возможностями командными языками. Общее название для любого командного интерпретатора ОС UNIX – shell (оболочка), поскольку любой интерпретатор представляет внешнее окружение ядра системы. Вызванный командный интерпре- татор выдает приглашение на ввод пользователем командной строки, которая мо- жет содержать простую команду, конвейер команд или последовательность ко- манд. После выполнения очередной командной строки и выдачи на экран термина- ла или в файл соответствующих результатов, shell снова выдает приглашение на ввод командной строки, и так до тех пор, пока пользователь не завершит свой се- анс работы и не выйдет из системы
Командные языки, используемые в ОС UNIX, достаточно просты, чтобы но- вые пользователи могли быстро начать работать, и достаточно мощны, чтобы мож- но было использовать их для написания сложных программ. Последняя возмож- ность опирается на механизм командных файлов (shell scripts), которые могут со- держать произвольные последовательности командных строк. При указании имени командного файла вместо очередной команды интерпретатор читает файл строка за строкой и последовательно интерпретирует команды.
Привилегированный пользователь
Ядро ОС UNIX идентифицирует каждого пользователя по его идентификатору
(UID – user identifier), уникальному целому значению, присваиваемому пользовате- лю при регистрации в системе. Кроме того, каждый пользователь относится к не- которой группе пользователей, которая также идентифицируется некоторым целым значением (GID – group identifier). Значения UID и GID для каждого зарегистриро-

392
ванного пользователя сохраняются в учётных файлах системы и приписываются процессу, в котором выполняется командный интерпретатор, запущенный при вхо- де пользователя в систему. Эти значения наследуются каждым новым процессом,
запущенным от имени данного пользователя, и используются ядром системы для контроля правомочности доступа к файлам, выполнения программ и т. д.
Очевидно, что администратор системы, который тоже является зарегистриро- ванным пользователем, должен обладать большими возможностями, чем обычные пользователи. В ОС UNIX эта задача решается путём выделения единственного нулевого значения UID. Пользователь с таким UID называется суперпользователем
(superuser) или root. Он имеет неограниченные права на доступ к любому файлу и на выполнение любой программы. Кроме того, такой пользователь имеет возмож- ность полного контроля над системой. Он может остановить её и даже разрушить.
Еще одним важным отличием суперпользователя от обычного пользователя
ОС UNIX является то, что на суперпользователя не распространяются ограничения на используемые ресурсы. Для обычных пользователей устанавливаются такие ог- раничения, как максимальный размер файла, максимальное число сегментов разде- ляемой памяти, максимально допустимое пространство на диске и т. д. Суперполь- зователь может изменять эти ограничения для других пользователей, но на него они не действуют.
Команды и командный интерпретатор
Оболочкой (shell) в системе UNIX называют механизм взаимодействия между пользователями и системой. По сути дела, это интерпретатор команд, который счи- тывает набираемые пользователем строки и запускает выполнение запрошенных системных функций. Полный командный язык, интерпретируемый оболочкой, бо- гат по возможностям и достаточно сложен, однако большинство команд просты в использовании и запомнить их не составляет труда.
Командная строка состоит из имени команды (то есть имени выполняемого файла), за которым следует список аргументов, разделённых пробелами. Оболочка разбивает командную строку на компоненты. Указанный в команде файл загружа- ется, и ему обеспечивается доступ к заданным в команде аргументам.

393
Любой командный язык семейства shell фактически состоит из трёх частей:
♦ служебных конструкций, позволяющих манипулировать с текстовыми стро- ками и строить сложные команды на основе простых команд;
♦ встроенных команд, выполняемых непосредственно интерпретатором ко- мандного языка;
♦ команд, представляемых отдельными выполняемыми файлами.
В свою очередь, набор команд последнего вида включает стандартные коман- ды (системные утилиты, такие как vi, cc и т. д.) и команды, созданные пользовате- лями системы. Для того чтобы выполняемый файл, разработанный пользователем
ОС UNIX, можно было запускать как команду shell, достаточно определить в од- ном из исходных файлов функцию с именем main (имя main должно быть глобаль- ным, то есть перед ним не должно указываться ключевое слово static). Если упот- ребить в качестве имени команды имя такого выполняемого файла, командный ин- терпретатор создаст новый процесс и запустит в нём указанную выполняемую про- грамму, начиная с вызова функции main.
Тело функции main, вообще говоря, может быть произвольным (для интерпре- татора существенно только наличие входной точки в программу с именем main), но для того, чтобы создать команду, которой можно задавать параметры, нужно при- держиваться некоторых стандартных правил. В этом случае каждая функция main должна определяться с двумя параметрами – argc и argv. После вызова команды параметру argc будет соответствовать число символьных строк, указанных в каче- стве аргументов вызова команды, а argv – массив указателей на переменные, со- держащие эти строки. При этом имя самой команды составляет первую строку ар- гументов (то есть после вызова значение argc всегда больше или равно 1). Код функции main должен проанализировать допустимость заданного значения argc и соответствующим образом обработать заданные текстовые строки.
Например, следующий текст на языке С может быть использован для создания команды, которая выводит на экран текстовую строку, заданную в качестве её ар- гумента:
#include