The design of the unix operating system by Maurice J
| Вид материала | Реферат |
- Лекция 10. Файловые системы Unix, 116.79kb.
- Уровни рассмотрения, 314.07kb.
- Курс по операционным системам (на примере ос windows) Основан на учебном курсе Windows, 29.21kb.
- Выполнил ученик 11 «А» класса, 443.51kb.
- Ос лекция 1 (2-й семестр – временно), 101.4kb.
- Operating System, 7686.97kb.
- Unix-подобные операционные системы, характеристики, особенности, разновидности, 40.63kb.
- 1. ms sql server. Общие сведения, 66.03kb.
- Shanti ananda maurice, 89.84kb.
- Методические материалы, 3002.45kb.
устанавливает значения счетчика символов в списке и указате-
лей в блоке таким образом, чтобы последующие операции не вы-
бирали один и тот же символ. Если в результате операции выб-
ран последний символ блока, ядро помещает в список свободных
символьных блоков пустой блок и переустанавливает указатели в
символьном списке. Если в символьном списке отсутствуют сим-
волы, ядро возвращает пустой символ.
4. Ядро может поместить символ в конец символьного списка путем
поиска последнего символьного блока в списке, включения сим-
вола в него и переустановки адресов смещений. Если символьный
блок заполнен, ядро выделяет новый символьный блок, включает
его в конец символьного списка и помещает символ в новый
блок.
5. Ядро может удалять от начала списка группу символов по одному
блоку за одну операцию, что эквивалентно удалению всех симво-
лов в блоке за один раз.
6. Ядро может поместить блок с символами в конец символьного
списка.
Символьные списки позволяют создать несложный механизм буфе-
ризации, полезный при небольшом объеме передаваемых данных, ти-
пичном для медленных устройств, таких как терминалы. Они дают
возможность манипулировать с данными с каждым символом в отдель-
ности и с группой символьных блоков. Например, Рисунок 10.11 ил-
люстрирует удаление символов из символьного списка; ядро удаляет
по одному символу из первого блока в списке (Рисунок 10.11а-в) до
тех пор, пока в блоке не останется ни одного символа (Рисунок
символьный символьные
список блоки
--------┐ ----T---T---T---T---T---T---T---┐
------>│ 0 8 │ │ p │ i │ c │ │ f │ i │ l │ e │
│ LT------- L---+---+---+---+---+---+---+----
│ v
│ --------┐ ----T---T---T---T---T---T---T---┐
-----------T-┐ │ │ 0 8 │ │ * │ │ │ │ │ t │ b │ l │ │
│ 27 │ +--- LT------- L---+---+---+---+---+---+---+----
│ символов │ +--┐ v
L----------+-- │ --------┐ ----T---T---T---T---T---T---T---┐
│ │ 0 8 │ │ │ │ │ t │ r │ o │ f │ f │ │
│ LT------- L---+---+---+---+---+---+---+----
│ v
│ --------┐ ----T---T---T---T---T---T---T---┐
L----->│ 0 3 │ │ - │ m │ m │ │ │ │ │ │
L-------- L---+---+---+---+---+---+---+----
(а)
--------┐ ----T---T---T---T---T---T---T---┐
------>│ 1 8 │ │ │ i │ c │ │ f │ i │ l │ e │
│ LT------- L---+---+---+---+---+---+---+----
│ v
│ --------┐ ----T---T---T---T---T---T---T---┐
-----------T-┐ │ │ 0 8 │ │ * │ │ │ │ │ t │ b │ l │ │
│ 26 │ +--- LT------- L---+---+---+---+---+---+---+----
│ символов │ +--┐ v
L----------+-- │ --------┐ ----T---T---T---T---T---T---T---┐
│ │ 0 8 │ │ │ │ │ t │ r │ o │ f │ f │ │
│ LT------- L---+---+---+---+---+---+---+----
│ v
│ --------┐ ----T---T---T---T---T---T---T---┐
L----->│ 0 3 │ │ - │ m │ m │ │ │ │ │ │
L-------- L---+---+---+---+---+---+---+----
(б)
--------┐ ----T---T---T---T---T---T---T---┐
------>│ 2 8 │ │ │ │ c │ │ f │ i │ l │ e │
│ LT------- L---+---+---+---+---+---+---+----
│ v
│ --------┐ ----T---T---T---T---T---T---T---┐
-----------T-┐ │ │ 0 8 │ │ * │ │ │ │ │ t │ b │ l │ │
│ 25 │ +--- LT------- L---+---+---+---+---+---+---+----
│ символов │ +--┐ v
L----------+-- │ --------┐ ----T---T---T---T---T---T---T---┐
│ │ 0 8 │ │ │ │ │ t │ r │ o │ f │ f │ │
│ LT------- L---+---+---+---+---+---+---+----
│ v
│ --------┐ ----T---T---T---T---T---T---T---┐
L----->│ 0 3 │ │ - │ m │ m │ │ │ │ │ │
L-------- L---+---+---+---+---+---+---+----
(в)
--------┐ ----T---T---T---T---T---T---T---┐
------>│ 0 8 │ │ * │ │ │ │ │ t │ b │ l │ │
│ LT------- L---+---+---+---+---+---+---+----
-----------T-┐ │ v
│ 19 │ +--- --------┐ ----T---T---T---T---T---T---T---┐
│ символов │ +--┐ │ 0 8 │ │ │ │ │ t │ r │ o │ f │ f │ │
L----------+-- │ LT------- L---+---+---+---+---+---+---+----
│ v
│ --------┐ ----T---T---T---T---T---T---T---┐
L----->│ 0 3 │ │ - │ m │ m │ │ │ │ │ │
L-------- L---+---+---+---+---+---+---+----
(г)
Рисунок 10.11. Удаление символов из символьного списка
символьный символьные
список блоки
--------┐ ----T---T---T---T---T---T---T---┐
------>│ 0 8 │ │ p │ i │ c │ │ f │ i │ l │ e │
│ LT------- L---+---+---+---+---+---+---+----
-----------T-┐ │ v
│ 22 │ +--- --------┐ ----T---T---T---T---T---T---T---┐
│ символа │ +--┐ │ 0 8 │ │ * │ │ │ │ │ t │ b │ l │ │
L----------+-- │ LT------- L---+---+---+---+---+---+---+----
│ v
│ --------┐ ----T---T---T---T---T---T---T---┐
L----->│ 0 6 │ │ │ │ │ t │ r │ o │ f │ │ │
L-------- L---+---+---+---+---+---+---+----
(а)
--------┐ ----T---T---T---T---T---T---T---┐
------>│ 0 8 │ │ p │ i │ c │ │ f │ i │ l │ e │
│ LT------- L---+---+---+---+---+---+---+----
-----------T-┐ │ v
│ 23 │ +--- --------┐ ----T---T---T---T---T---T---T---┐
│ символа │ +--┐ │ 0 8 │ │ * │ │ │ │ │ t │ b │ l │ │
L----------+-- │ LT------- L---+---+---+---+---+---+---+----
│ v
│ --------┐ ----T---T---T---T---T---T---T---┐
L----->│ 0 7 │ │ │ │ │ t │ r │ o │ f │ f │ │
L-------- L---+---+---+---+---+---+---+----
(б)
--------┐ ----T---T---T---T---T---T---T---┐
------>│ 0 8 │ │ p │ i │ c │ │ f │ i │ l │ e │
│ LT------- L---+---+---+---+---+---+---+----
-----------T-┐ │ v
│ 24 │ +--- --------┐ ----T---T---T---T---T---T---T---┐
│ символа │ +--┐ │ 0 8 │ │ * │ │ │ │ │ t │ b │ l │ │
L----------+-- │ LT------- L---+---+---+---+---+---+---+----
│ v
│ --------┐ ----T---T---T---T---T---T---T---┐
L----->│ 0 8 │ │ │ │ │ t │ r │ o │ f │ f │ │
L-------- L---+---+---+---+---+---+---+----
(в)
--------┐ ----T---T---T---T---T---T---T---┐
------>│ 0 8 │ │ p │ i │ c │ │ f │ i │ l │ e │
│ LT------- L---+---+---+---+---+---+---+----
│ v
│ --------┐ ----T---T---T---T---T---T---T---┐
-----------T-┐ │ │ 0 8 │ │ * │ │ │ │ │ t │ b │ l │ │
│ 25 │ +--- LT------- L---+---+---+---+---+---+---+----
│ символов │ +--┐ v
L----------+-- │ --------┐ ----T---T---T---T---T---T---T---┐
│ │ 0 8 │ │ │ │ │ t │ r │ o │ f │ f │ │
│ LT------- L---+---+---+---+---+---+---+----
│ v
│ --------┐ ----T---T---T---T---T---T---T---┐
L----->│ 0 1 │ │ - │ │ │ │ │ │ │ │
L-------- L---+---+---+---+---+---+---+----
(г)
Рисунок 10.12. Включение символов в символьный список
10.11г); затем оно устанавливает указатель списка на следующий
блок, который становится первым блоком в списке. Подобно этому на
Рисунке 10.12 показано, как ядро включает символы в символьный
список; при этом предполагается, что в одном блоке помещается до
8 символов и что ядро размещает новый блок в конце списка (Рису-
нок 10.12г).
10.3.2 Терминальный драйвер в каноническом режиме
Структуры данных, с которыми работают терминальные драйверы,
связаны с тремя символьными списками: списком для хранения дан-
ных, выводимых на терминал, списком для хранения неструктуриро-
ванных вводных данных, поступивших в результате выполнения прог-
раммы обработки прерывания от терминала, вызванного попыткой
пользователя ввести данные с клавиатуры, и списком для хранения
обработанных входных данных, поступивших в результате преобразо-
вания строковым интерфейсом специальных символов (таких как сим-
волы стирания и удаления) в неструктурированном списке.
-------------------------------------------------------------┐
│ алгоритм terminal_write │
│ { │
│ выполнить (пока из пространства задачи еще поступают │
│ данные) │
│ { │
│ если (на терминал поступает информация) │
│ { │
│ приступить к выполнению операции записи данных │
│ из списка, хранящего выводные данные; │
│ приостановиться (до того момента, когда терми- │
│ нал будет готов принять следующую порцию дан- │
│ ных); │
│ продолжить; /* возврат к началу цикла */ │
│ } │
│ скопировать данные в объеме символьного блока из │
│ пространства задачи в список, хранящий выводные │
│ данные: строковый интерфейс преобразует символы │
│ табуляции и т.д.; │
│ } │
│ │
│ приступить к выполнению операции записи данных из спис-│
│ ка, хранящего выводные данные; │
│ } │
L-------------------------------------------------------------
Рисунок 10.13. Алгоритм переписи данных на терминал
Когда процесс ведет запись на терминал (Рисунок 10.13), тер-
минальный драйвер запускает строковый интерфейс. Строковый
интерфейс в цикле считывает символы из адресного пространства
процесса и помещает их в символьный список для хранения выводных
данных до тех пор, пока поток данных не будет исчерпан. Строковый
интерфейс обрабатывает выводимые символы, например, заменяя сим-
волы табуляции на последовательности пробелов. Если количество
символов в списке для хранения выводных данных превысит верхнюю
отметку, строковый интерфейс вызывает процедуры драйвера, пересы-
лающие данные из символьного списка на терминал и после этого
приостанавливающие выполнение процесса, ведущего запись. Когда
объем информации в списке для хранения выводных данных падает за
нижнюю отметку, программа обработки прерываний возобновляет вы-
полнение всех процессов, приостановленных до того момента, когда
терминал сможет принять следующую порцию данных. Строковый интер-
фейс завершает цикл обработки, скопировав всю выводимую информа-
цию из адресного пространства задачи в соответствующий символьный
список, и вызывает выполнение процедур драйвера, пересылающих
данные на терминал, о которых уже было сказано выше.
Если на терминал ведут запись несколько процессов, они неза-
висимо друг от друга следуют указанной процедуре. Выводимая ин-
формация может быть искажена; то есть на терминале данные, запи-
сываемые процессами, могут пересекаться. Это может произойти
из-за того, что процессы ведут запись на терминал, используя нес-
колько вызовов системной функции write. Ядро может переключать
контекст, пока процесс выполняется в режиме задачи, между после-
довательными вызовами функции write, и вновь запущенные процессы
могут вести запись на терминал, пока первый из процессов приоста-
новлен. Выводимые данные могут быть также искажены и на термина-
ле, поскольку процесс может приостановиться на середине выполне-
ния системной функции write, ожидая завершения вывода на терминал
из системы предыдущей порции данных. Ядро может запустить другие
процессы, которые вели запись на терминал до того, как первый
процесс был повторно запущен. По этой причине, ядро не гарантиру-
ет, что содержимое буфера данных, выводимое в результате вызова
системной функции write, появится на экране терминала в непрерыв-
ном виде.
-----------------------------------------------------------------┐
│ char form[]="это пример вывода строки из порожденного процесса"│ │
│ main() │
│ { │
│ char output[128]; │
│ int i; │
│ │
│ for (i = 0; i < 18; i++) │
│ { │
│ switch (fork()) │
│ { │
│ case -1: /* ошибка --- превышено максимальное чис-│
│ ло процессов */ │
│ exit(); │
│ │
│ default: /* родительский процесс */ │
│ break; │
│ │
│ case 0: /* порожденный процесс */ │
│ /* формат вывода строки в переменной output */ │
│ sprintf(output,"%%d\n%s%d\n",form,i,form,i); │
│ for (;;) │
│ write(1,output,sizeof(output)); │
│ } │
│ } │
│ } │
L-----------------------------------------------------------------
Рисунок 10.14. Передача данных через стандартный вывод
Рассмотрим программу, приведенную на Рисунке 10.14. Родитель-
ский процесс создает до 18 порожденных процессов; каждый из по-
рожденных процессов записывает строку (с помощью библиотечной
функции sprintf) в массив output, который включает сообщение и
значение счетчика i в момент выполнения функции fork, и затем
входит в цикл пошаговой переписи строки в файл стандартного выво-
да. Если стандартным выводом является терминал, терминальный
драйвер регулирует поток поступающих данных. Выводимая строка
имеет более 64 символов в длину, то есть слишком велика для того,
чтобы поместиться в символьном блоке (длиной 64 байта) в версии V
системы. Следовательно, терминальному драйверу требуется более
одного символьного блока для каждого вызова функции write, иначе
выводной поток может стать искаженным. Например, следующие строки
были частью выводного потока, полученного в результате выполнения
программы на машине AT&T 3B20:
this is a sample output string from child 1
this is a sample outthis is a sample output string from child 0
Чтение данных с терминала в каноническом режиме более сложная
операция. В вызове системной функции read указывается количество
байт, которые процесс хочет считать, но строковый интерфейс вы-
полняет чтение по получении символа перевода каретки, даже если
количество символов не указано. Это удобно с практической точки
зрения, так как процесс не в состоянии предугадать, сколько сим-
волов пользователь введет с клавиатуры, и, с другой стороны, не
имеет смысла ждать, когда пользователь введет большое число сим-
волов. Например, пользователи вводят командные строки для команд-
ного процессора shell и ожидают ответа shell'а на команду по по-
лучении символа возврата каретки. При этом нет никакой разницы,
являются ли введенные строки простыми командами, такими как
"date" или "who", или же это более сложные последовательности ко-
манд, подобные следующей:
pic file* │ tbl │ eqn │ troff -mm -Taps │ apsend
Терминальный драйвер и строковый интерфейс ничего не знают о
синтаксисе командного процессора shell, и это правильно, посколь-
ку другие программы, которые считывают информацию с терминалов
(например, редакторы), имеют различный синтаксис команд. Поэтому
строковый интерфейс выполняет чтение по получении символа возвра-
та каретки.
На Рисунке 10.15 показан алгоритм чтения с терминала. Предпо-
ложим, что терминал работает в каноническом режиме; в разделе
10.3.3 будет рассмотрена работа в режиме без обработки. Если в
настоящий момент в любом из символьных списков для хранения ввод-
ной информации отсутствуют данные, процесс, выполняющий чтение,
приостанавливается до поступления первой строки данных. Когда
данные поступают, программа обработки прерывания от терминала за-
пускает "программу обработки прерывания" строкового интерфейса,
которая помещает данные в список для хранения неструктурированных
вводных данных для передачи процессам, осуществляющим чтение, и в
список для хранения выводных данных, передаваемых в качестве эхо-
сопровождения на терминал. Если введенная строка содержит символ
возврата каретки, программа обработки прерывания возобновляет вы-
полнение всех приостановленных процессов чтения. Когда процесс,
осуществляющий чтение, выполняется, драйвер выбирает символы из
списка для хранения неструктурированных вводных данных, обрабаты-
вает символы стирания и удаления и помещает символы в каноничес-
кий символьный список. Затем он копирует строку символов в адрес-
ное пространство задачи до символа возврата каретки или до
исчерпания числа символов, указанного в вызове системной функции
read, что встретится раньше. Однако, процесс может обнаружить,
что данных, ради которых он возобновил свое выполнение, больше не
существует: другие процессы считали данные с терминала и удалили
их из списка для неструктурированных вводных данных до того, как
первый процесс был запущен вновь. Такая ситуация похожа на ту,
которая имеет место, когда из канала считывают данные несколько
процессов.
Обработка символов в направлении ввода и в направлении вывода
асимметрична, что видно из наличия двух символьных списков для
ввода и одного - для вывода. Строковый интерфейс выводит данные
из пространства задачи, обрабатывает их и помещает их в список
для хранения выводных данных. Для симметрии следовало бы иметь
-------------------------------------------------------------┐
│ алгоритм terminal_read │
│ { │
│ если (в каноническом символьном списке отсутствуют дан- │
│ ные) │
│ { │
│ выполнить (пока в списке для неструктурированных │
│ вводных данных отсутствует информация) │
│ { │
│ если (терминал открыт с параметром "no delay" │
│ (без задержки)) │
│ возвратить управление; │
│ если (терминал в режиме без обработки с использо-│
│ ванием таймера и таймер не активен) │
│ предпринять действия к активизации таймера │
│ (таблица ответных сигналов); │
│ приостановиться (до поступления данных с термина-│
│ ла); │
│ } │
│ │
│ /* в списке для неструктурированных вводных данных │
│ есть информация */ │
│ если (терминал в режиме без обработки) │
│ скопировать все данные из списка для неструктури-│
│ рованных вводных данных в канонический список; │
│ в противном случае /* терминал в каноническом ре- │
│ жиме */ │
│ { │
│ выполнить (пока в списке для неструктурированных │
│ вводных данных есть символы) │
│ { │
│ копировать по одному символу из списка для │
│ неструктурированных вводных данных в кано- │
│ нический список: │
│ выполнить обработку символов стирания и уда-│
│ ления; │
│ если (символ - "возврат каретки" или "конец │
│ файла") │
│ прерваться; /* выход из цикла */ │
│ } │
│ } │
│ } │
│ │
│ выполнить (пока в каноническом списке еще есть символы │
│ и не исчерпано количество символов, указанное в вызове │
│ функции read) │
│ копировать символы из символьных блоков канонического│
│ списка в адресное пространство задачи; │
│ } │
L-------------------------------------------------------------
Рисунок 10.15. Алгоритм чтения с терминала
только один список для вводных данных. Однако, в таком случае
потребовалось бы использование программы обработки прерываний для
интерпретации символов стирания и удаления, что сделало бы проце-
дуру более сложной и длительной и запретило бы возникновение дру-
гих прерываний на все критическое время. Использование двух сим-
вольных списков для ввода подразумевает, что программа обработки
прерываний может просто сбросить символы в список для неструкту-
рированных вводных данных и возобновить выполнение процесса, осу-
ществляющего чтение, который собственно и возьмет на себя работу
по интерпретации вводных данных. При этом программа обработки
прерываний немедленно помещает введенные символы в список для
хранения выводных данных, так что пользователь испытывает лишь
минимальную задержку при просмотре введенных символов на термина-
ле.
---------------------------------------------------------------┐
│ char input[256]; │