Системное программное обеспечение

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

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

8.4. Режимы управления вводом/выводом

Имеются два основных режима ввода/вывода: режим обмена с опросом готовности устройства ввода/вывода и режим обмена с прерываниями. Пусть, например, управление ввода/вывода осуществляет центральный процессор, который посылает контроллеру устройства ввода/вывода команду выполнить некоторое действие устройству ввода/выво­ да. Контроллер исполняет команду, транслируя сигналы, понятные ему и центральному процессору, в сигналы, понятные устройству ввода/вывода. Но быстродействие устрой­ ства ввода/вывода намного меньше быстродействия центрального процессора. Поэтому сигнал готовности, транслируемый или генерируемый контроллером и сигнализирующий процессору о том, что команда ввода/вывода выполнена и можно выдать новую команду для продолжения обмена данными, приходится очень долго ожидать, постоянно опраши­ вая соответствующую линию интерфейса на наличие или отсутствие нужного сигнала. Посылать новую команду, не дождавшись сигнала готовности, сообщающего об исполне­ нию предыдущей команды, бессмысленно. В режиме опроса готовности драйвер, управ­ ляющий процессом обмена данными с внешним устройством, как раз и выполняет в цикле команду «проверить наличие сигнала готовности». До тех пор, пока сигнал готовности не появится, драйвер ничего другого не делает. При этом нерационально используется время центрального процессора. Гораздо выгоднее, выдав команду ввода/вывода, на время за­ быть об устройстве ввода/вывода и перейти на выполнение другой программы, а появле­ ние сигнала готовности трактовать как запрос на прерывание от устройства ввода/вывода.

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

41

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

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

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

8.5. Кэширование операций ввода/вывода при работе с накопителями на магнитных дисках

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

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

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

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

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

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

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

42

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

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

В ряде ОС имеется возможность указать в явном виде параметры кэширования, в то время как в других за эти параметры отвечает сама ОС. Так, в системах Windows 95/98 та­ кая возможность имеется, но она предоставляет не слишком богатый выбор. Фактически мы можем указать только объем памяти, отводимый для кэширования, и объем порции данных, из которых набирается кэш. Для этого в файле Sistem.ini, в секции [VCACHE] необходимо прописать, например, следующие значения:

[VCACHE]

MinFileCache=4096

MaxFileCache=32768

ChunkSize=512

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

8.6. Алгоритмы оптимизации работы накопителей на магнитных дисках

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

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

43

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

-SSTF (shortest seek time – first) – с наименьшим временем поиска – первым. В со­ ответствии с этой дисциплиной при позиционировании магнитных головок следующим выбирается запрос, для которого необходимо минимальное перемещение с цилиндра на цилиндр, даже если этот запрос не был первым в очереди на вод/вывод. Для этой дисци­ плины характерна резкая дискриминация определенных запросов, а ведь они могут идти от высокоприоритетных задач. Обращения к диску проявляют тенденцию концентриро­ ваться, в результате чего запросы на обращение к самым внешним и самым внутренним дорожкам могут обслуживаться существенно дольше, и нет никакой гарантии обслужива­ ния. Достоинством такой дисциплины является максимально возможная пропускная способность дисковой подсистемы.

-Scan (сканирование). По этой дисциплине головки перемещаются то в одном, то в другом «привилегированном» направлении, обслуживая «по пути» подходящие запросы. Если при перемещении головок чтения/записи более нет попутных запросов , то движение начинается в обратном направлении.

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

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

9.ФАЙЛОВАЯ СИСТЕМА

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

Вшироком смысле понятие "файловая система" включает:

совокупность всех файлов на диске,

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

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

44

9.1. Имена файлов

Файлы идентифицируются именами. Пользователи дают файлам символьные имена, при этом учитываются ограничения ОС как на используемые символы, так и на длину имени. До недавнего времени эти границы были весьма узкими. Так в популярной файловой си­ стеме FAT длина имен ограничивается известной схемой 8.3 (8 символов – собственно имя, 3 символа – расширение имени), а в ОС UNIX System V имя не может содержать бо­ лее 14 символов. Однако пользователю гораздо удобнее работать с длинными именами, поскольку они позволяют дать файлу действительно мнемоническое название, по которо­ му даже через достаточно большой промежуток времени можно будет вспомнить, что со­ держит этот файл. Поэтому современные файловые системы, как правило, поддерживают длинные символьные имена файлов. Например, Windows NT в своей новой файловой си­ стеме NTFS устанавливает, что имя файла может содержать до 255 символов, не считая завершающего нулевого символа.

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

Длинные имена поддерживаются не только новыми файловыми системами, но и новыми версиями хорошо известных файловых систем. Например, в ОС Windows 95 используется файловая система VFAT, представляющая собой существенно измененный вариант FAT. Среди многих других усовершенствований одним из главных достоинств VFAT является поддержка длинных имен. Кроме проблемы генерации эквивалентных коротких имен, при реализации нового варианта FAT важной задачей была задача хранения длинных имен при условии, что принципиально метод хранения и структура данных на диске не должны были измениться.

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

9.2. Типы файлов

Файлы бывают разных типов: обычные файлы, специальные файлы, файлы-катало­

ги.

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

45

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

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

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

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

информация о разрешенном доступе,

пароль для доступа к файлу,

владелец файла,

создатель файла,

признак "только для чтения",

признак "скрытый файл",

признак "системный файл",

признак "архивный файл",

признак "двоичный/символьный",

признак "временный" (удалить после завершения процесса),

признак блокировки,

длина записи,

указатель на ключевое поле в записи,

длина ключа,

времена создания, последнего доступа и последнего изменения,

текущий размер файла,

максимальный размер файла.

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

Иерархия каталогов может быть деревом или сетью. Каталоги образуют дерево, если файлу разрешено входить только в один каталог, и сеть – если файл может входить

46

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

9.3. Логическая организация файла

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

9.4. Физическая организация и адрес файла

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

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

Популярным способом, используемым, например, в файловой системе FAT опера­ ционной системы MS-DOS, является использование связанного списка индексов. С каж­

47

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

В заключение рассмотрим задание физического расположения файла путем просто­ го перечисления номеров блоков, занимаемых этим файлом. ОС UNIX использует вариант данного способа, позволяющий обеспечить фиксированную длину адреса, независимо от размера файла. Для хранения адреса файла выделено 13 полей. Если размер файла меньше или равен 10 блокам, то номера этих блоков непосредственно перечислены в первых деся­ ти полях адреса. Если размер файла больше 10 блоков, то следующее 11-е поле содержит адрес блока, в котором могут быть расположены еще 128 номеров следующих блоков файла. Если файл больше, чем 10 + 128 блоков, то используется 12-е поле, в котором на­ ходится номер блока, содержащего 128 номеров блоков, которые содержат по 128 номе­ ров блоков данного файла. И, наконец, если файл больше 10 + 128 + 128×128, то использу­ ется последнее 13-е поле для тройной косвенной адресации, что позволяет задать адрес файла, имеющего размер максимум 10 + 128 + 128×128 + 128×128×128.

9.5. Права доступа к файлу

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

создание файла,

уничтожение файла,

открытие файла,

закрытие файла,

чтение файла,

запись в файл,

дополнение файла,

поиск в файле,

получение атрибутов файла,

установление новых значений атрибутов,

переименование,

выполнение файла,

чтение каталога,

идругие операции с файлами и каталогами.

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

48

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

Различают два основных подхода к определению прав доступа:

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

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

9.6.Общая модель файловой системы

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

Задачей символьного уровня является определение по символьному имени файла его уни­ кального имени. В файловых системах, в которых каждый файл может иметь только одно символьное имя (например, MS-DOS), этот уровень отсутствует, так как символьное имя, присвоенное файлу пользователем, является одновременно уникальным и может быть ис­ пользовано ОС. В других файловых системах, в которых один и тот же файл может иметь несколько символьных имен, на данном уровне просматривается цепочка каталогов для определения уникального имени файла. В файловой системе UNIX, например, уникаль­ ным именем является номер индексного дескриптора файла (i-node).

49

Рис. 9.1. Общая модель файловой системы

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

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

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

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

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

9.7. Файловая система FAT

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

В файловой системе FAT логическое дисковое пространство любого логического диска делится на две области: системную область и область данных (см. рис. 9.2).

50