Защищенный режим работы процессора как средство многозадачности

Защищенный режим работы процессора как средство многозадачности Режимы работы микропроцессора Впервые о различных режимах работы процессоров IA­32 стали говорить с появлением  процессора 80286. Это был первый представитель данного семейства процессоров, в  котором были реализованы многозадачность и защищенная архитектура. Чтобы  обеспечить совместимость с предыдущими представителями этого семейства (8086/88,  80186/188) в процессоре 80286 было реализовано два режима функционирования: режим  эмуляции 8086 (режим реального адреса) и защищенный режим, в котором используются  все возможности процессора. В последующих поколениях процессоров этого семейства  защищенный режим становится основным режимом работы. В новых поколениях процессоров Intel появился еще один режим работы ­ режим  системного управления. Впервые он был реализован в процессорах 80386SL и i486SL.  Начиная с расширенных моделей Intel486, этот режим стал обязательным элементом  архитектуры IA­32. С его помощью прозрачно даже для операционной системы на уровне  BIOS реализуются функции энергосбережения. Защищенный режим (Protected Mode) Основным режимом работы микропроцессора является защищенный режим. Ключевыми  особенностями защищенного режима являются: виртуальное адресное  пространство, защита и многозадачность. В защищенном режиме программа оперирует адресами, которые могут относиться к  физически отсутствующим ячейкам памяти, поэтому такое адресное пространство  называется виртуальным. Размер виртуального адресного пространства программы  может превышать емкость физической памяти и достигать 64Тбайт. Для адресации  виртуального адресного пространства используется сегментированная модель, в которой  адрес состоит из двух элементов: селектора сегмента и смещения внутри сегмента. С  каждым сегментом связана особая структура, хранящая информацию о нем, ­ дескриптор. Кроме "виртуализации" памяти на уровне сегментов существует возможность  "виртуализации" памяти при помощи страниц ­ страничная трансляция. Страничная  трансляция предоставляет удобные средства для реализации в операционной системе  функций подкачки, а кроме того в процессорах P6+ обеспечивает 36­битную физическую  адресацию памяти (64Гбайт). Встроенные средства переключения задач обеспечивают многозадачность в защищенном  режиме. Среда задачи состоит из содержимого регистров МП и всего кода с данными в  пространстве памяти. Микропроцессор способен быстро переключаться из одной среды  выполнения в другую, имитируя параллельную работу нескольких задач. Для некоторых  задач может эмулироваться управление памятью как у процессора 8086. Такое состояние  задачи называется режимом виртуального 8086 (Virtual 8086 Mode). О пребывании  задачи в таком состоянии сигнализирует бит VM в регистре флагов. При этом задачи  виртуального МП 8086 изолированы и защищены, как от друг друга, так и от обычных  задач защищенного режима. Защита задач обеспечивается следующими средствами: контроль пределов  сегментов, контроль типов сегментов, контроль привилегий, привилегированные  инструкции и защита на уровне страниц. Контроль пределов и типов сегментов  обеспечивает целостность сегментов кода и данных. Программа не имеет права  обращаться к виртуальной памяти, выходящей за предел того или иного сегмента.  Программа не имеет права обращаться к сегменту данных как к коду и наоборот.  Архитектура защиты микропроцессора обеспечивает 4 иерархических уровня привилегий, что позволяет ограничить задаче доступ к отдельным сегментам в зависимости от ее  текущих привилегий. Кроме того, текущий уровень привилегий задачи влияет на  возможность выполнения тех или иных специфических команд (привилегированных  инструкций). Функции страничной трансляции, впервые появившиеся в МП Intel386,  обеспечивают дополнительные механизмы защиты на уровне страниц. Реальный режим (Real Mode) В реальном режиме микропроцессор работает как очень быстрый 8086 с возможностью  использования 32­битных расширений. Механизм адресации, размеры памяти и обработка  прерываний (с их последовательными ограничениями) МП Intel386 в реальном  режиме полностью совпадают с аналогичными функциями МП 8086. В отличие от 8086  микропроцессоры 286+ в определенных ситуациях генерируют исключения, например,  при превышении предела сегмента, который для всех сегментов в реальном режиме ­  0FFFFh. Имеется две фиксированные области в памяти, которые резервируются в режиме  реальной адресации:  область инициализации системы  область таблицы прерываний Ячейки от 00000h до 003FFH резервируются для векторов прерываний. Каждое из 256  возможных прерываний имеет зарезервированный 4­байтовый адрес перехода. Ячейки от  FFFFFFF0H до FFFFFFFFH резервируются для инициализации системы. Режим системного управления (System Management Mode) Режим системного управления предназначен для выполнения некоторых действий с  возможностью их полной изоляции от прикладного программного обеспечения и даже  операционной системы. Переход в этот режим возможен только аппаратно. Когда  процессор находится в режиме SMM, он выставляет сигнал SMIACT#. Этот сигнал может служить для включения выделенной области физической памяти (System Management  RAM), так что память SMRAM можно сделать доступной только для этого режима. При  входе в режим SMM процессор сохраняет свой контекст в SMRAM (контекст  сопроцессора не сохраняется) по адресу SMM Base и передает управление процедуре,  называемой обработчиком System Management Interrupt, по адресу SMM Base+8000h (по  умолчанию SMM Base содержит значение 30000h). Состояние процессора в этот момент  точно определено: EFLAGS обнулен (кроме зарезервированных битов), сегментные  регистры содержат селектор 0000, базы сегментов установлены в 00000000, пределы ­  0FFFFFFFFh. Следует отметить, что в режиме SMM не предусмотрена работа с прерываниями и  особыми случаями: прерывания по IRQ и SMI# замаскированы, пошаговые ловушки и  точки останова отключены, обработка прерывания по NMI откладывается до выхода из  режима SMM. Если необходимо обеспечить работу с прерываниями или особыми  случаями, то надо инициализировать IDT и разрешить прерывания, выставив флаг IF в  регистре EFLAGS. Прерывания по NMI будут разблокированы автоматически после  первой же команды IRET. При возврате из SMM (по инструкции RSM) процессор восстанавливает свой контекст из  SMRAM. Обработчик может программно внести изменения в образ контекста процессора, тогда процессор перейдет не в то состояние, в котором произошло SMI. Если SMI было  получено во время выполнения инструкции HLT, то дальнейшие действия при выходе из  SMM определяются значением поля "Auto HALT Restart": процессор может снова  вернуться к инструкции останова или перейти к выполнению следующей команды. Если  SMI произошло при выполнении инструкции ввода­вывода, то в зависимости от значения  поля "I/O Instruction Restart" возможен рестарт инструкции ввода вывода. Эти особенности режима системного управления позволяют использовать его для  реализации системы управления энергосбережением компьютера или функций  безопасности и контроля доступа. Переключение между режимами После инициализации процессор находится в реальном режиме. Процессор может быть  переведен в защищенный режим установкой бита 0 (Protect Enable) в регистре CR0: MOV EAX,00000001h MOV CR0,EAX   или   MOV AX,0001h LMSW AX Второй вариант "достался в наследство" от 16­разрядной архитектуры 80286, для  совместимости с которой ее регистр MSW (Machine Status Word) отображается на  младшее слово регистра CR0. Вернуться в режим реального адреса процессор может по сигналу RESET или (в отличие  от 80286) сбросив бит PE: MOV EAX,00000000h MOV CR0,EAX Для совместимости с 80286 инструкция LMSW бит PE не сбрасывает. Режим системного управления изолирован от других режимов. Процессор переходит в  этот режим только аппаратно: по низкому уровню на контакте SMI# или по команде с  шины APIC (Pentium+). Никакой программный способ не предусмотрен для перехода в  этот режим. Процессор возвращается из режима системного управления в тот режим, при  работе в котором был получен сигнал SMI#. Возврат происходит по команде RSM. Эта команда работает только в режиме системного управления и в других режимах не  распознается, генерирую исключение #6 (недействительный код операции). Сравнение режимов Характеристика RM PM, VM=0 PM, VM=1 SMM Формирование линейного адреса без  дескрипторов с дескрипторами без  дескрипторов без  дескрипторов Предел сегментов 64К Размер адреса/данных по  умолчанию 16 бит Максимальный объем  доступной памяти  (виртуальной) Защита Страничное  преобразование Многозадачность 1M Нет* Нет Нет определяется  дескриптором определяется  дескриптором 64К 4Г 16 бит 16 бит 64T Да Да Да 1M Да Да Да 4Г Нет Нет Нет Обработка прерываний таблица  векторов дескрипторная таблица дескрипторная таблица Нет** * В реальном режиме контролируется предел сегментов. ** После определенных подготовительных действий возможна работа с прерываниями как  в реальном режиме. Средства аппаратной поддержки управления памятью и многозадачной среды в  микропроцессорах Intel 80386, 80486 и Pentium Процессоры Intel 80386, 80486 и Pentium с точки зрения рассматриваемых в данном  разделе вопросов имеют аналогичные средства, поэтому для краткости в тексте  используется термин "процессор i386", хотя вся информация этого раздела в равной  степени относится к трем моделям процессоров фирмы Intel. Процессор i386 имеет два режима работы ­ реальный (real mode) и защищенный (protected  mode). В реальном режиме процессор i386 работает как быстрый процессор 8086 с  несколько расширенным набором команд. В защищенном режиме процессор i386 может  использовать все механизмы 32­х разрядной организации памяти, в том числе механизмы  поддержки виртуальной памяти и механизмы переключения задач. Кроме этого, в  защищенном режиме для каждой задачи процессор i386 может эмулировать 86 и 286  процессоры, которые в этом случае называются виртуальными процессорами. Таким  образом, при многозадачной работе в защищенном режиме процессор i386 работает как  несколько виртуальных процессоров, имеющих общую память. В отличие от реального  режима, режим виртуального процессора i86, который называется в этом случае режимом  V86, поддерживает страничную организацию памяти и средства многозадачности.  Поэтому задачи, выполняющиеся в режиме V86, используют те же средства межзадачной  защиты и защиты ОС от пользовательских задач, что и задачи, работающие в защищенном  режиме i386. Однако максимальный размер виртуального адресного пространства  составляет 1 Мб, как и у процессора i86. Переключение процессора i386 из реального режима в защищенный и обратно  осуществляется просто путем выполнения команды MOV, которая изменяет бит режима в одном из управляющих регистров процессора. Переход процессора в режим V86  происходит похожим образом путем изменения значения определенного бита в другом  регистре процессора. Средства поддержки сегментации памяти Физическое адресное пространство процессора i386 составляет 4 Гбайта, что  определяется 32­разрядной шиной адреса. Физическая память является линейной с  адресами от 00000000 до FFFFFFFF в шестнадцатеричном представлении. Виртуальный  адрес, используемый в программе, представляет собой пару ­ номер сегмента и смещение  внутри сегмента. Смещение хранится в соответствующем поле команды, а номер сегмента ­ в одном из шести сегментных регистров процессора (CS, SS, DS, ES, FS или GS), каждый из которых является 16­битным. Средства сегментации образуют верхний уровень средств управления виртуальной памятью процессора i386, а средства страничной организации ­  нижний уровень. Средства страничной организации могут быть как включены, так и  выключены (за счет установки определенного бита в управляющем регистре процессора),  и в зависимости от этого изменяется смысл преобразования виртуального адреса, которое выполняют средства сегментации. Сначала рассмотрим случай работы средств  сегментации при отключенном механизме управления страницами. Рис. 2.19. Поддержка сегментов На рисунке 2.19 показано виртуальное адресное пространство процессора i386 при  отключенном механизме управления страницами. 32­битное смещение определяет размер  виртуального сегмента в 232=4 Гбайта, а количество сегментов определяется размером  поля, отведенного в сегментном регистре под номер сегмента. На рисунке 2.20,а показана  структура данных в сегментном регистре. Эта структура называется селектором, так как  предназначена для выбора дескриптора определенного сегмента из таблиц дескрипторов  сегментов. Дескриптор сегмента описывает все характеристики сегмента, необходимые  для проверки правильности доступа к нему и нахождения его в физическом адресном  пространстве. Процессор i386 поддерживает две таблицы дескрипторов сегментов ­  глобальную (Global Descriptor Table, GDT) и локальную (Local Descriptor Table, LDT).  Глобальная таблица предназначена для описания сегментов операционной системы и  сегментов межзадачного взаимодействия, то есть сегментов, которые в принципе могут  использоваться всеми процессами, а локальная таблица ­ для сегментов отдельных задач.  Таблица GDT одна, а таблиц LDT должно быть столько, сколько в системе выполняется  задач. При этом активной в каждый момент времени может быть только одна из таблиц  LDT. Рис. 2.20. Форматы селектора и дескрипторов данных и кода:  а ­ формат селектора; б ­ формат регистра GDTR;  в ­ формат дескриптора сегмента данных или кода Из рисунка 2.20 видно, что селектор состоит из трех полей ­ 13­битного поля индекса  (номера сегмента) в таблицах GDT и LDT, 1­битного поля ­ указателя типа используемой  таблицы дескрипторов и двухбитного поля текущих прав доступа задачи ­ CPL.  Разрядность поля индекса определяет максимальное число глобальных и локальных  сегментов задачи ­ по 8K (213) сегментов каждого типа, всего 16 K. С учетом  максимального размера сегмента ­ 4 Гбайта ­ каждая задача при чисто сегментной  организации виртуальной памяти работает в виртуальном адресном пространстве в 64  Тбайта. Теперь проследим, как виртуальное пространство отображается на физическое  пространство размером в 4 Гбайта при чисто сегментном механизме отображения. Итак,  когда задаче необходимо получить доступ к ячейке физической памяти, то для выбора  дескриптора виртуального сегмента используется значение селектора из  соответствующего (в зависимости от команды и стадии ее выполнения ­ выборка кода  команды или данных) сегментного регистра процессора. Значение поля типа таблицы указывает на то, какую таблицу нужно использовать ­ GDT или LDT. Рассмотрим сначала  случай использования таблицы GDT. Для хранения таблиц GDT и LDT используется  оперативная память (использование быстрой ассоциативной памяти процессора для  хранения элементов этих таблиц рассмотрим позже). Для того, чтобы процессор смог  найти в физической памяти таблицу GDT, ее полный 32­битный физический адрес (адрес  начала таблицы), а также размер (поле в 16 бит) хранятся в специальном регистре  процессора GDTR (рисунок 2.20, б). Каждый дескриптор в таблицах GDT и LDT имеет  размер 8 байт, поэтому максимальный размер этих таблиц ­ 64 К (8(8 К дескрипторов).  Для извлечения нужного дескриптора из таблицы процессор складывает базовый адрес  таблицы GDT из регистра GDTR со сдвинутым на 3 разряда влево (умножение на 8, в  соответствии с числом байтов в элементе таблицы GDT) значением поля индекса из  сегментного регистра и получает физический линейный адрес нужного дескриптора в  физической памяти. Таблица GDT постоянно присутствует в физической памяти,  поэтому процессор извлекает по этому адресу нужный дескриптор сегмента и помещает  его во внутренний (программно недоступный) регистр процессора. (Таких регистров  шесть и каждый из них соответствует определенному сегментному регистру, что  значительно ускоряет работу процессора). Дескриптор виртуального сегмента (рисунок 2.20,в) состоит из нескольких полей,  основными из которых являются поле базы ­ базового 32­разрядного физического адреса  начала сегмента, поле размера сегмента и поле прав доступа к сегменту ­ DPL (Descriptor  Privilege Level). Сначала процессор определяет правильность адреса, сравнивая смещение  и размер сегмента (в случае выхода за границы сегмента происходит прерывание типа  исключение ­ exсeption). Потом процессор проверяет права доступа задачи к данному  сегменту, сравнивая значения полей CPL селектора и DPL дескриптора сегмента. В  процессоре i386 мандатный способ определения прав доступа (называемый также  механизмом колец защиты), при котором имеется несколько уровней прав доступа, и  объекты какого­либо уровня имеют доступ ко всем объектам равного уровня или более  низких уровней, но не имеет доступа к объектам более высоких уровней. В процессоре  i386 существует четыре уровня прав доступа ­ от 0­го, который является самым высоким,  до 3­го ­ самого низкого. Очевидно, что операционная система может использовать  механизм уровней защиты по своему усмотрению. Однако предполагается, что нулевой  уровень будет использован для ядра операционной системы, а третий уровень ­ для  прикладных программ, промежуточные уровни ­ для утилит и подсистем операционной  системы, менее привилегированных, чем ядро. Таким образом, доступ к виртуальному сегменту считается законным, если уровень прав  селектора CPL выше или равен уровню прав сегмента DPL (CPL ( DPL). При нарушении прав доступа происходит прерывание, как и в случае несоблюдения границ сегмента.  Далее проверяется наличие сегмента в физической памяти по значению бита P  дескриптора, и если сегмент отсутствует в физической памяти, то происходит  прерывание. При наличии сегмента в памяти вычисляется физический линейный адрес  путем сложения базы сегмента и смещения и производится доступ к элементу физической памяти по этому адресу. В случае, когда селектор указывает на таблицу LDT, виртуальный адрес преобразуется в  физический аналогичным образом, но для доступа к самой таблице LDT добавляется еще  один этап, так как в процессоре регистр LDTR указывает на размещение таблицы LDT не  прямо, а косвенно. Сам регистр LDTR имеет размер 16 бит и содержит селектор  дескриптора таблицы GDT, который описывает расположение этой таблицы в физической памяти. Поэтому при доступе к элементу физической памяти через таблицу LDT  происходит двукратное преобразование виртуального адреса в физический, причем оба  раза по описанной выше схеме. Сначала по значению селектора LDTR определяется  физический адрес дескриптора из таблицы GDT, описывающего начало расположения  таблицы LDT в физической памяти, а затем с помощью селектора задачи вычисляется  смещение в таблице LDT и определяется физический адрес нужного дескриптора. Далее  процесс аналогичен преобразованию виртуального адреса с помощью таблицы GDT. Рис. 2.21. Типы дескрипторов Дескриптор сегмента содержит еще несколько полей. Однобитное поле G определяет  единицу измерения размера сегмента, при G = 0 размер определяется в байтах, и тогда сегмент не может быть больше 64 К, а при G = 1 размер определяется в 4К­байтных  страницах, при этом максимальный размер сегмента достигает указанных 4 Гбайт. Поле D определяет тип адресации сегмента: при D = 0 сегмент является 16­битным (для режима  эмуляции 16­битных процессоров i86 и i286), а при D = 1 сегмент является 32­битным.  Кроме этого в дескрипторе имеется поле типа сегмента, которое в свою очередь делится  на несколько полей (рисунок 2.21). Поле S определяет, является ли сегмент системным (S = 1) или пользовательским (S = 0). В свою очередь пользовательские сегменты делятся на  сегменты данных (E=0) и сегменты кода (E=1). Для сегмента данных определяются  однобитные поля: ED ­ направления распространения сегмента (ED = 0 для обычного сегмента данных,  распространяющегося в сторону увеличения адресов, ED = 1 для стекового сегмента  данных, распространяющегося в сторону уменьшения адресов), W ­ поле разрешения записи в сегмент (при W=1 запись разрешена, при W=0 ­ запрещена), A ­ поле доступа к сегменту (1 означает, что после очистки этого поля к сегменту было  обращение по чтению или записи, это поле может использоваться операционной системой  в ее стратегии замены страниц в оперативной памяти). Для сегмента кода используются однобитные признаки: A ­ имеет смысл, аналогичный полю A сегмента данных, R ­ разрешает или запрещает чтение из кодового сегмента, C ­ бит подчинения, разрешает или запрещает вызов данного кодового сегмента из другого кодового сегмента с более низкими правами доступа. В процессоре i386 существует большое количество системных сегментов, к которым в  частности относятся системные сегменты типа LDT, шлюзы вызова подпрограмм и задач и сегменты состояния задачи TSS. Таким образом, для использования чисто сегментного механизма процессора i386  операционной системе необходимо сформировать таблицы GDT и LDT, загрузить их в  память (для начала достаточно загрузить только таблицу GDT), загрузить указатели на  эти таблицы в регистры GDTR и LDTR и выключить страничную поддержку. Если же  операционная система не хочет использовать сегментную организацию виртуальной  памяти, то ей достаточно создать таблицу дескрипторов из одного входа (дескриптора) и  загрузить базовые значения сегмента в дескриптор. Виртуальное адресное пространство  задачи будет состоять из одного сегмента длиной максимум в 4 Гбайта. Сегментно­страничный механизм При включенной системе управления страницами работает как описанный выше  сегментный механизм, так и механизм управления страницами, однако при этом смысл  работы сегментного механизма меняется. В этом случае виртуальное адресное  пространство задачи имеет размер в 4 Гбайта, в котором размещаются все сегменты  (рисунок 2.22). По прежнему селектор задачи определяет номер виртуального сегмента, а  смещение в команде задачи ­ смещение внутри этого сегмента. Так как теперь все  сегменты разделяют одно адресное пространство, то возможно их наложение, но  процессор не контролирует такие ситуации, оставляя эту проблему операционной  системе. Первый этап преобразования виртуального адреса, связанный с преобразованием  смещения и селектора с использованием таблиц GDT и LDT, содержащих дескрипторы  сегментов, в точности совпадает с этапом преобразования этих данных при отключенном  механизме управления страницами. Все структуры данных этих таблиц такие же. Однако,  если раньше дескриптор сегмента содержал его базовый адрес в физическом адресном  пространстве, и при сложении его со смещением из команды программы получался  линейный искомый адрес в физической памяти, то теперь дескриптор содержит базовый  адрес сегмента в виртуальном адресном пространстве. Поэтому в результате его  сложения со смещением получается линейный виртуальный адрес, который на втором  этапе (страничном) преобразуется в номер физической страницы. Для реализации  механизма управления страницами как физическое, так и виртуальное адресное  пространства разбиты на страницы размером 4 К. Всего в этих адресных пространствах  насчитывается 1 М страниц. Несмотря на наличие нескольких виртуальных сегментов, все виртуальное адресное пространство задачи имеет общее разбиение на страницы, так что  нумерация виртуальных страниц сквозная. Линейный виртуальный адрес содержит в своих старших 20 разрядах номер виртуальной  страницы, а в младших 12 разрядах смещение внутри страницы. Для отображения  виртуальной страницы в физическую достаточно построить таблицу страниц, каждый  элемент которой ­ дескриптор виртуальной страницы ­ содержал бы номер  соответствующей ей физической страницы и ее атрибуты. В процессоре i386 так и  сделано, и структура дескриптора страницы показана на рисунке 2.23. 20­ти разрядов  номера страницы достаточно для определения физического адреса начала страницы, так  как при ее фиксированном размере 4 К младшие 12 разрядов этого адреса всегда равны  нулю. Дескриптор страницы также содержит следующие поля, близкие по смыслу  соответствующим полям дескриптора сегмента: P ­ бит присутствия страницы в физической памяти, W ­ бит разрешения записи в страницу, U ­ бит пользователь/супервизор A ­ признак того, был ли доступ к странице, D ­ признак модификации содержимого страницы, PWT и PCD ­ управляют механизмом кэширования страниц (введены, начиная с  процессора i486), AVL ­ резерв для нужд операционной системы (available for use). Рис. 2.22. Сегментно­страничный механизм Рис. 2.23. Формат дескриптора страницы При небольшом размере страницы процессора i386 относительно размеров адресных  пространств, таблица страниц должна занимать в памяти весьма значительное место ­ 4  байта ( 1М = 4 Мбайта. Это слишком много для нынешних моделей персональных компьютеров, поэтому в процессоре i386 используется деление всей таблицы страниц на  разделы по 1024 дескриптора. Размер раздела выбран так, чтобы один раздел занимал  одну физическую страницу (1024 ( 4 байта = 4 Кбайта). Всего получается 1024 раздела  (1024 ( 1024 = 1М). Для того, чтобы не хранить все разделы таблицы страниц  одновременно в физической памяти, используется каталог разделов таблицы страниц,  который использует такие же по структуре дескрипторы страниц, что и в таблице  страниц. Поэтому для хранения информации о дескрипторах 1024 разделов необходима  память 4 К, т.е. одна физическая страница. Совокупность дескрипторов, описывающих  состояние и характеристики виртуальных страниц разделов таблицы страниц, называется  каталогом разделов или таблиц. Виртуальная страница, хранящая содержимое каталога,  всегда находится в физической памяти, и номер ее физической страницы указан в  специальном управляющем регистре CR3 процессора (точнее, в одном из полей этого  регистра). Преобразование линейного виртуального адреса в физический происходит следующим  образом (рисунок 2.24). Поле номера виртуальной страницы (старшие 20 разрядов)  делится на две равные части по 10 разрядов ­ поле номера раздела и поле номера  страницы в разделе. С помощью номера физической страницы, хранящей каталог и  смещения в этой странице, задаваемого полем номера раздела, процессор находит  дескриптор виртуальной страницы раздела. В соответствии с атрибутами этого  дескриптора определяются права доступа к этой странице, а также наличие ее в  физической памяти. В случае ее отсутствия происходит страничное прерывание, и  операционная система должна в этом случае переместить ее в память. После того, как  нужная страница находится в памяти, для определения адреса элемента данных  используется смещение, определяемое полем номера страницы линейного виртуального  адреса. Таким образом, при доступе к странице в процессоре используется двухуровневая схема  адресации страниц, что замедляет преобразование, но позволяет использовать страничный механизм и для хранения самой таблицы страниц, и существенно уменьшить объем  физической памяти для ее хранения. Для ускорения страничных преобразований в блоке  управления страницами используется ассоциативная память, в которой кэшируется 32  комбинации "номер виртуальной страницы ­ номер физической страницы". Эта  специальная кэш­память (дополнительная по отношению к 8 Кбайтному кэшу данных  процессоров i486 и Pentium) значительно ускоряет преобразование адресов, так как в  случае попадания в кэш длительный процесс, описанный выше, исключается. Рис. 2.24. Преобразование линейного виртуального адреса в физический адрес Организация виртуальной памяти в процессоре i386 позволяет защитить адресные  пространства различных процессов за счет двух механизмов: 1. Изоляция адресных пространств процессов в физической памяти путем назначения  им различных физических страниц или сегментов (если страничный механизм  отключен). 2. Защита сегментов от несанкционированного доступа с помощью привилегий  четырех уровней. Средства вызова подпрограмм и задач Операционная система, как однозадачная, так и многозадачная, должна предоставлять  задачам средства вызова подпрограмм операционной системы, библиотечных  подпрограмм, а также иметь средства для запуска задач, а при многозадачной работе  средства быстрого переключения с задачи на задачу. Вызов подпрограммы отличается от  запуска задачи тем, что в первом случае адресное пространство остается тем же (таблица  LDT остается прежней), а при вызове задачи адресное пространство полностью меняется. Вызов подпрограмм без смены кодового сегмента в защищенном режиме процессора i386  производится аналогично вызову в реальном режиме с помощью команд JMP и CALL. Для вызова подпрограммы, код которой находится в другом сегменте (который может  принадлежать библиотеке, другой задаче или операционной системе), процессор i386  предоставляет 2 варианта вызова, причем оба используют защиту с помощью прав  доступа. Первый способ состоит в непосредственном указании в поле команды JMP или CALL  селектора сегмента, содержащего код вызываемой подпрограммы, а также смещение в  этом сегменте адреса начала подпрограммы. Рис. 2.25. Непосредственный вызов подпрограммы Схема такого вызова приведена на рисунке 2.25. Здесь и далее показан только этап  получения линейного адреса в виртуальном пространстве, а следующий этап  (подразумевается, что механизм поддержки страниц включен) преобразования этого  адреса в номер физической страницы опущен, так как он не содержит ничего  специфического по сравнению с доступом к сегменту данных, рассмотренному выше.  Разрешение вызова происходит в зависимости от значения поля C в дескрипторе сегмента  вызываемого кода. При C=0 вызываемый сегмент не считается подчиненным, и вызов  разрешается, только если уровень прав вызывающего кода не меньше уровня прав  вызываемого сегмента. При C=1 вызываемый сегмент считается подчиненным и допускает вызов из кода с любым уровнем прав доступа, но при выполнении подпрограмма  наделяется уровнем прав вызвавшего кода. Рис. 2.26. Формат дескриптора шлюза вызова подпрограммы Рис. 2.27. Вызов подпрограммы через шлюз вызова Очевидно, что первый способ непригоден для вызова функций операционной системы,  имеющей обычно нулевой уровень прав, из пользовательской программы, работающей, как правило, на третьем уровне. Поэтому процессор i386 предоставляет другой способ вызова подпрограмм, основанный на том, что заранее определяется набор точек входа в  привилегированные кодовые сегменты, и эти точки входа описываются с помощью  специальных дескрипторов ­ дескрипторов шлюзов вызова подпрограмм. Этот дескриптор принадлежит к системным дескрипторам, и его структура отличается от структуры  дескрипторов сегментов кода и данных (рисунок 2.26). Схема его использования  приведена на рисунке 2.27. Селектор из поля команды CALL используется для указания  на дескриптор шлюза вызова подпрограммы в таблицах GDT или LDT. Для использования этого дескриптора вызывающий код должен иметь не меньший уровень прав, чем  дескриптор, но если дескриптор шлюза доступен, то он может указывать на дескриптор  сегмента вызываемого кода, имеющий более высокий уровень, чем имеет шлюз, и вызов  при этом произойдет. При определении адреса входа в вызываемом сегменте смещение из  поля команды CALL не используется, а используется смещение из дескриптора шлюза,  что не дает возможности задаче самой определять точку входа в защищенный кодовый  сегмент. При вызове кодов, обладающих различными уровнями привилегий, возникает проблема  передачи параметров между различными стеками, так как для надежной защиты задачи  различного уровня привилегий имеют различные сегменты стеков. Селекторы этих  сегментов хранятся в контексте задачи ­ сегменте TSS (Task State Segment). Если  вызывается подпрограмма, имеющая другой уровень привилегий, то из текущего стека в  стек уровня доступа вызываемого сегмента копируется столько 32­разрядных слов,  сколько указано в поле счетчика слов дескриптора шлюза. Структура сегмента TSS задачи приведена на рисунке 2.28. Контекст задачи должен  содержать все данные для того, чтобы можно было восстановить выполнение прерванной  в произвольный момент времени задачи, то есть значения регистров процессора, указатели на открытые файлы и некоторые другие, зависящие от операционной системы,  переменные. Скорость переключения контекста в значительной степени влияет на  скоростные качества многозадачной операционной системы. Процессор i386 производит  аппаратное переключение контекста задачи, хранящегося в сегменте TSS. Как видно из  рисунка, сегмент TSS имеет фиксированные поля, отведенные для значений регистров  процессора, как универсальных, так и некоторых управляющих (например LDTR и CR3).  Для описания возможностей доступа задачи к портам ввода­вывода процессор использует  в защищенном режиме поле IOPL (Input/Output Privilege Level) в своем регистре EFLAGS  и карту битовых полей доступа к портам. Для получения возможности выполнять  команды ввода­вывода выполняемый код должен иметь уровень прав не ниже значения  поля IOPL. Если же это условие соблюдается, то возможность доступа к порту с  конкретным адресом определяется значением соответствующего бита в карте ввода­ вывода сегмента TSS (карта состоит из 64 Кбит для описания доступа к 65536 портам). Битовая карта ввода/вывода (БКВВ) Дополнительная информация ОС Относительный адрес БККВ 0 0 0 . . . . . . 0 0 Селектор LDT   ( (8 Кбайт   . . .0T64    60 GS    5C 0 0 0 0 0           . . . . . . . . . . . . . . . 0 0 0 0 0 EDI ESI EBP ESP EBX EDX ECX EAX EFLAGS EIP FS    58 DS    54 SS    50 CS    4C ES    48 44 40 3C 38 34 30 2C 28 24 20 CR3 0 ESP2 0 ESP1 0 ESP0 0 . . . . . . . . . . . . 0 0 0 0 SS уровня 2 SS уровня 1 SS уровня 0 Селектор TSS возврата 1C 18 14 10 C 8 4 0 Рис. 2.28. Структура сегмента TSS Кроме этого, сегмент TSS может включать дополнительную информацию, необходимую  для работы задачи и зависящую от конкретной операционной системы (например,  указатели открытых файлов или указатели на именованные конвейеры сетевого обмена).  Включенная в этот сегмент информация автоматически заменяется процессором при  выполнении команды CALL, селектор которой указывает на дескриптор сегмента TSS в  таблице GDT (дескрипторы этого типа могут быть расположены только в этой таблице).  Формат дескриптора сегмента TSS аналогичен формату дескриптора сегмента данных. Рис. 2.29. Непосредственный вызов задачи Как и в случае вызова подпрограмм, имеется две возможности вызова задачи ­  непосредственный вызов через указание селектора сегмента TSS нужной задачи в поле  команды CALL и косвенный вызов через шлюз вызова задачи. Как и при вызове подпрограмм, непосредственный вызов возможен только в случае, если вызывающий код  обладает уровнем привилегий, не меньшим, чем вызываемая задача. При вызове через  шлюз (который может располагаться и в таблице LDT) достаточно иметь права доступа к  шлюзу. Непосредственный вызов задачи показан на рисунке 2.29. При переключении задач процессор выполняет следующие действия: 1) Выполняется команда CALL, селектор которой указывает на дескриптор сегмента типа TSS. 2) В TSS текущей задачи сохраняются значения регистров процессора. На текущий  сегмент TSS указывает регистр процессора TR, содержащий селектор сегмента. 3) В TR загружается селектор сегмента TSS задачи, на которую переключается процессор. 4) Из нового TSS в регистр LDTR переносится значение селектора таблицы LDT в  таблице GDT задачи. 5) Восстанавливаются значения регистров процессора (из соответствующих полей нового  сегмента TSS). 6) В поле селектора возврата заносится селектор сегмента TSS снимаемой с выполнения  задачи для организации возврата к прерванной задаче в будущем. Вызов задачи через шлюз происходит аналогично, добавляется только этап поиска  дескриптора сегмента TSS по значению селектора дескриптора шлюза вызова. Использование всех возможностей, предоставляемых процессорами Intel 80386, 80486 и  Pentium, позволяет организовать операционной системе высоконадежную многозадачную  среду. Управление вводом­выводом Одной из главных функций ОС является управление всеми устройствами ввода­вывода  компьютера. ОС должна передавать устройствам команды, перехватывать прерывания и  обрабатывать ошибки; она также должна обеспечивать интерфейс между устройствами и  остальной частью системы. В целях развития интерфейс должен быть одинаковым для  всех типов устройств (независимость от устройств). Физическая организация устройств ввода­вывода Устройства ввода­вывода делятся на два типа: блок­ориентированные устройства  и байт­ориентированные устройства. Блок­ориентированные устройства хранят  информацию в блоках фиксированного размера, каждый из которых имеет свой собственный адрес. Самое распространенное блок­ориентированное устройство ­ диск.  Байт­ориентированные устройства не адресуемы и не позволяют производить операцию  поиска, они генерируют или потребляют последовательность байтов. Примерами  являются терминалы, строчные принтеры, сетевые адаптеры. Однако некоторые внешние  устройства не относятся ни к одному классу, например, часы, которые, с одной стороны,  не адресуемы, а с другой стороны, не порождают потока байтов. Это устройство только  выдает сигнал прерывания в некоторые моменты времени. Внешнее устройство обычно состоит из механического и электронного компонента.  Электронный компонент называется контроллером устройства или адаптером.  Механический компонент представляет собственно устройство. Некоторые контроллеры  могут управлять несколькими устройствами. Если интерфейс между контроллером и  устройством стандартизован, то независимые производители могут выпускать  совместимые как контроллеры, так и устройства. Операционная система обычно имеет дело не с устройством, а с контроллером.  Контроллер, как правило, выполняет простые функции, например, преобразует поток бит  в блоки, состоящие из байт, и осуществляют контроль и исправление ошибок. Каждый  контроллер имеет несколько регистров, которые используются для взаимодействия с  центральным процессором. В некоторых компьютерах эти регистры являются частью  физического адресного пространства. В таких компьютерах нет специальных операций  ввода­вывода. В других компьютерах адреса регистров ввода­вывода, называемых часто  портами, образуют собственное адресное пространство за счет введения специальных  операций ввода­вывода (например, команд IN и OUT в процессорах i86). ОС выполняет ввод­вывод, записывая команды в регистры контроллера. Например,  контроллер гибкого диска IBM PC принимает 15 команд, таких как READ, WRITE,  SEEK, FORMAT и т.д. Когда команда принята, процессор оставляет контроллер и  занимается другой работой. При завершении команды контроллер организует прерывание  для того, чтобы передать управление процессором операционной системе, которая  должна проверить результаты операции. Процессор получает результаты и статус  устройства, читая информацию из регистров контроллера. Организация программного обеспечения ввода­вывода Основная идея организации программного обеспечения ввода­вывода состоит в разбиении его на несколько уровней, причем нижние уровни обеспечивают экранирование  особенностей аппаратуры от верхних, а те, в свою очередь, обеспечивают удобный  интерфейс для пользователей. Ключевым принципом является независимость от устройств. Вид программы не должен  зависеть от того, читает ли она данные с гибкого диска или с жесткого диска. Очень близкой к идее независимости от устройств является идея единообразного  именования, то есть для именования устройств должны быть приняты единые правила. Другим важным вопросом для программного обеспечения ввода­вывода является  обработка ошибок. Вообще говоря, ошибки следует обрабатывать как можно ближе к  аппаратуре. Если контроллер обнаруживает ошибку чтения, то он должен попытаться ее  скорректировать. Если же это ему не удается, то исправлением ошибок должен заняться  драйвер устройства. Многие ошибки могут исчезать при повторных попытках выполнения операций ввода­вывода, например, ошибки, вызванные наличием пылинок на головках  чтения или на диске. И только если нижний уровень не может справиться с ошибкой, он  сообщает об ошибке верхнему уровню. Еще один ключевой вопрос ­ это использование блокирующих (синхронных) и  неблокирующих (асинхронных) передач. Большинство операций физического ввода­ вывода выполняется асинхронно ­ процессор начинает передачу и переходит на другую  работу, пока не наступает прерывание. Пользовательские программы намного легче  писать, если операции ввода­вывода блокирующие ­ после команды READ программа  автоматически приостанавливается до тех пор, пока данные не попадут в буфер  программы. ОС выполняет операции ввода­вывода асинхронно, но представляет их для  пользовательских программ в синхронной форме. Последняя проблема состоит в том, что одни устройства являются разделяемыми, а  другие ­ выделенными. Диски ­ это разделяемые устройства, так как одновременный  доступ нескольких пользователей к диску не представляет собой проблему. Принтеры ­  это выделенные устройства, потому что нельзя смешивать строчки, печатаемые  различными пользователями. Наличие выделенных устройств создает для операционной  системы некоторые проблемы. Для решения поставленных проблем целесообразно разделить программное обеспечение  ввода­вывода на четыре слоя (рисунок 2.30):  Обработка прерываний,  Драйверы устройств,  Независимый от устройств слой операционной системы,  Пользовательский слой программного обеспечения. Рис. 2.30. Многоуровневая организация подсистемы ввода­вывода Обработка прерываний Прерывания должны быть скрыты как можно глубже в недрах операционной системы,  чтобы как можно меньшая часть ОС имела с ними дело. Наилучший способ состоит в  разрешении процессу, инициировавшему операцию ввода­вывода, блокировать себя до  завершения операции и наступления прерывания. Процесс может блокировать себя,  используя, например, вызов DOWN для семафора, или вызов WAIT для переменной  условия, или вызов RECEIVE для ожидания сообщения. При наступлении прерывания  процедура обработки прерывания выполняет разблокирование процесса,  инициировавшего операцию ввода­вывода, используя вызовы UP, SIGNAL или посылая  процессу сообщение. В любом случае эффект от прерывания будет состоять в том, что  ранее заблокированный процесс теперь продолжит свое выполнение. Драйверы устройств Весь зависимый от устройства код помещается в драйвер устройства. Каждый драйвер  управляет устройствами одного типа или, может быть, одного класса. В операционной системе только драйвер устройства знает о конкретных особенностях  какого­либо устройства. Например, только драйвер диска имеет дело с дорожками, секторами, цилиндрами, временем установления головки и другими факторами,  обеспечивающими правильную работу диска. Драйвер устройства принимает запрос от устройств программного слоя и решает, как его  выполнить. Типичным запросом является чтение n блоков данных. Если драйвер был  свободен во время поступления запроса, то он начинает выполнять запрос немедленно.  Если же он был занят обслуживанием другого запроса, то вновь поступивший запрос  присоединяется к очереди уже имеющихся запросов, и он будет выполнен, когда наступит его очередь. Первый шаг в реализации запроса ввода­вывода, например, для диска, состоит в  преобразовании его из абстрактной формы в конкретную. Для дискового драйвера это  означает преобразование номеров блоков в номера цилиндров, головок, секторов,  проверку, работает ли мотор, находится ли головка над нужным цилиндром. Короче  говоря, он должен решить, какие операции контроллера нужно выполнить и в какой  последовательности. После передачи команды контроллеру драйвер должен решить, блокировать ли себя до  окончания заданной операции или нет. Если операция занимает значительное время, как  при печати некоторого блока данных, то драйвер блокируется до тех пор, пока операция  не завершится, и обработчик прерывания не разблокирует его. Если команда ввода­ вывода выполняется быстро (например, прокрутка экрана), то драйвер ожидает ее  завершения без блокирования. Независимый от устройств слой операционной системы Большая часть программного обеспечения ввода­вывода является независимой от  устройств. Точная граница между драйверами и независимыми от устройств программами определяется системой, так как некоторые функции, которые могли бы быть реализованы независимым способом, в действительности выполнены в виде драйверов для повышения  эффективности или по другим причинам. Типичными функциями для независимого от устройств слоя являются:  обеспечение общего интерфейса к драйверам устройств,  именование устройств,  защита устройств,  обеспечение независимого размера блока,  буферизация,  распределение памяти на блок­ориентированных устройствах,  распределение и освобождение выделенных устройств,  уведомление об ошибках. Остановимся на некоторых функциях данного перечня. Верхним слоям программного  обеспечения не удобно работать с блоками разной величины, поэтому данный слой  обеспечивает единый размер блока, например, за счет объединения нескольких различных  блоков в единый логический блок. В связи с этим верхние уровни имеют дело с  абстрактными устройствами, которые используют единый размер логического блока  независимо от размера физического сектора. При создании файла или заполнении его новыми данными необходимо выделить ему  новые блоки. Для этого ОС должна вести список или битовую карту свободных блоков  диска. На основании информации о наличии свободного места на диске может быть  разработан алгоритм поиска свободного блока, независимый от устройства и реализуемый программным слоем, находящимся выше слоя драйверов. Пользовательский слой программного обеспечения Хотя большая часть программного обеспечения ввода­вывода находится внутри ОС,  некоторая его часть содержится в библиотеках, связываемых с пользовательскими  программами. Системные вызовы, включающие вызовы ввода­вывода, обычно делаются  библиотечными процедурами. Если программа, написанная на языке С, содержит вызов count = write (fd, buffer, nbytes), то библиотечная процедура write будет связана с программой. Набор подобных процедур  является частью системы ввода­вывода. В частности, форматирование ввода или вывода  выполняется библиотечными процедурами. Примером может служить  функция printf языка С, которая принимает строку формата и, возможно, некоторые  переменные в качестве входной информации, затем строит строку символов ASCII и  делает вызов write для вывода этой строки. Стандартная библиотека ввода­вывода  содержит большое число процедур, которые выполняют ввод­вывод и работают как часть  пользовательской программы. Другой категорией программного обеспечения ввода­вывода является подсистема  спулинга (spooling). Спулинг ­ это способ работы с выделенными устройствами в  мультипрограммной системе. Рассмотрим типичное устройство, требующее спулинга ­ строчный принтер. Хотя технически легко позволить каждому пользовательскому  процессу открыть специальный файл, связанный с принтером, такой способ опасен из­за  того, что пользовательский процесс может монополизировать принтер на произвольное  время. Вместо этого создается специальный процесс ­ монитор, который получает  исключительные права на использование этого устройства. Также создается специальный  каталог, называемый каталогом спулинга. Для того, чтобы напечатать файл,  пользовательский процесс помещает выводимую информацию в этот файл и помещает его в каталог спулинга. Процесс­монитор по очереди распечатывает все файлы,  содержащиеся в каталоге спулинга. Файловая система Файловая система ­ это часть операционной системы, назначение которой состоит в том, чтобы обеспечить пользователю удобный интерфейс при работе с данными, хранящимися  на диске, и обеспечить совместное использование файлов несколькими пользователями и  процессами. В широком смысле понятие "файловая система" включает:  совокупность всех файлов на диске,  наборы структур данных, используемых для управления файлами, такие, например,  как каталоги файлов, дескрипторы файлов, таблицы распределения свободного и  занятого пространства на диске,  комплекс системных программных средств, реализующих управление файлами, в  частности: создание, уничтожение, чтение, запись, именование, поиск и другие  операции над файлами. Имена файлов Файлы идентифицируются именами. Пользователи дают файлам символьные имена, при  этом учитываются ограничения ОС как на используемые символы, так и на длину имени.  До недавнего времени эти границы были весьма узкими. Так в популярной файловой  системе FAT длина имен ограничивается известной схемой 8.3 (8 символов ­ собственно  имя, 3 символа ­ расширение имени), а в ОС UNIX System V имя не может содержать  более 14 символов. Однако пользователю гораздо удобнее работать с длинными именами,  поскольку они позволяют дать файлу действительно мнемоническое название, по  которому даже через достаточно большой промежуток времени можно будет вспомнить,  что содержит этот файл. Поэтому современные файловые системы, как правило,  поддерживают длинные символьные имена файлов. Например, Windows NT в своей новой файловой системе NTFS устанавливает, что имя файла может содержать до 255  символов, не считая завершающего нулевого символа. При переходе к длинным именам возникает проблема совместимости с ранее созданными  приложениями, использующими короткие имена. Чтобы приложения могли обращаться к  файлам в соответствии с принятыми ранее соглашениями, файловая система должна  уметь предоставлять эквивалентные короткие имена (псевдонимы) файлам, имеющим  длинные имена. Таким образом, одной из важных задач становится проблема генерации  соответствующих коротких имен. Длинные имена поддерживаются не только новыми файловыми системами, но и новыми  версиями хорошо известных файловых систем. Например, в ОС Windows 95 используется  файловая система VFAT, представляющая собой существенно измененный вариант FAT.  Среди многих других усовершенствований одним из главных достоинств VFAT является  поддержка длинных имен. Кроме проблемы генерации эквивалентных коротких имен, при реализации нового варианта FAT важной задачей была задача хранения длинных имен при  условии, что принципиально метод хранения и структура данных на диске не должны  были измениться. Обычно разные файлы могут иметь одинаковые символьные имена. В этом случае файл  однозначно идентифицируется так называемым составным именем, представляющем  собой последовательность символьных имен каталогов. В некоторых системах одному и  тому же файлу не может быть дано несколько разных имен, а в других такое ограничение  отсутствует. В последнем случае операционная система присваивает файлу  дополнительно уникальное имя, так, чтобы можно было установить взаимно­однозначное  соответствие между файлом и его уникальным именем. Уникальное имя представляет  собой числовой идентификатор и используется программами операционной системы.  Примером такого уникального имени файла является номер индексного дескриптора в  системе UNIX. Типы файлов Файлы бывают разных типов: обычные файлы, специальные файлы, файлы­каталоги. Обычные файлы в свою очередь подразделяются на текстовые и двоичные. Текстовые  файлы состоят из строк символов, представленных в ASCII­коде. Это могут быть  документы, исходные тексты программ и т.п. Текстовые файлы можно прочитать на  экране и распечатать на принтере. Двоичные файлы не используют ASCII­коды, они часто  имеют сложную внутреннюю структуру, например, объектный код программы или архивный файл. Все операционные системы должны уметь распознавать хотя бы один тип  файлов ­ их собственные исполняемые файлы. Специальные файлы ­ это файлы, ассоциированные с устройствами ввода­вывода,  которые позволяют пользователю выполнять операции ввода­вывода, используя обычные  команды записи в файл или чтения из файла. Эти команды обрабатываются вначале  программами файловой системы, а затем на некотором этапе выполнения запроса  преобразуются ОС в команды управления соответствующим устройством. Специальные  файлы, так же как и устройства ввода­вывода, делятся на блок­ориентированные и байт­ ориентированные. Каталог ­ это, с одной стороны, группа файлов, объединенных пользователем исходя из  некоторых соображений (например, файлы, содержащие программы игр, или файлы,  составляющие один программный пакет), а с другой стороны ­ это файл, содержащий  системную информацию о группе файлов, его составляющих. В каталоге содержится  список файлов, входящих в него, и устанавливается соответствие между файлами и их  характеристиками (атрибутами). В разных файловых системах могут использоваться в качестве атрибутов разные  характеристики, например:  информация о разрешенном доступе,  пароль для доступа к файлу,  владелец файла,  создатель файла,  признак "только для чтения",  признак "скрытый файл",  признак "системный файл",  признак "архивный файл",  признак "двоичный/символьный",  признак "временный" (удалить после завершения процесса),  признак блокировки,  длина записи,  указатель на ключевое поле в записи,  длина ключа,  времена создания, последнего доступа и последнего изменения,  текущий размер файла,  максимальный размер файла. Каталоги могут непосредственно содержать значения характеристик файлов, как это  сделано в файловой системе MS­DOS, или ссылаться на таблицы, содержащие эти  характеристики, как это реализовано в ОС UNIX (рисунок 2.31). Каталоги могут  образовывать иерархическую структуру за счет того, что каталог более низкого уровня  может входить в каталог более высокого уровня (рисунок 2.32). Рис. 2.31. Структура каталогов: а ­ структура записи каталога MS­DOS (32 байта);  б ­ структура записи каталога ОС UNIX Иерархия каталогов может быть деревом или сетью. Каталоги образуют дерево, если  файлу разрешено входить только в один каталог, и сеть ­ если файл может входить сразу  в несколько каталогов. В MS­DOS каталоги образуют древовидную структуру, а в UNIX'е ­ сетевую. Как и любой другой файл, каталог имеет символьное имя и однозначно  идентифицируется составным именем, содержащим цепочку символьных имен всех  каталогов, через которые проходит путь от корня до данного каталога. Рис. 2.32. Логическая организация файловой системы  а ­ одноуровневая; б ­ иерархическая (дерево); в ­ иерархическая (сеть) Логическая организация файла Программист имеет дело с логической организацией файла, представляя файл в виде  определенным образом организованных логических записей. Логическая запись ­ это  наименьший элемент данных, которым может оперировать программист при обмене с  внешним устройством. Даже если физический обмен с устройством осуществляется  большими единицами, операционная система обеспечивает программисту доступ к  отдельной логической записи. На рисунке 2.33 показаны несколько схем логической  организации файла. Записи могут быть фиксированной длины или переменной длины.  Записи могут быть расположены в файле последовательно (последовательная  организация) или в более сложном порядке, с использованием так называемых индексных  таблиц, позволяющих обеспечить быстрый доступ к отдельной логической записи  (индексно­последовательная организация). Для идентификации записи может быть  использовано специальное поле записи, называемое ключом. В файловых системах ОС UNIX и MS­DOS файл имеет простейшую логическую структуру ­ последовательность  однобайтовых записей. Рис. 2.33. Способы логической организации файлов Физическая организация и адрес файла Физическая организация файла описывает правила расположения файла на устройстве  внешней памяти, в частности на диске. Файл состоит из физических записей ­ блоков.  Блок ­ наименьшая единица данных, которой внешнее устройство обменивается с  оперативной памятью. Непрерывное размещение ­ простейший вариант физической  организации (рисунок 2.34,а), при котором файлу предоставляется последовательность  блоков диска, образующих единый сплошной участок дисковой памяти. Для задания  адреса файла в этом случае достаточно указать только номер начального блока. Другое  достоинство этого метода ­ простота. Но имеются и два существенных недостатка. Во­ первых, во время создания файла заранее не известна его длина, а значит не известно,  сколько памяти надо зарезервировать для этого файла, во­вторых, при таком порядке  размещения неизбежно возникает фрагментация, и пространство на диске используется не эффективно, так как отдельные участки маленького размера (минимально 1 блок) могут  остаться не используемыми. Следующий способ физической организации ­ размещение в виде связанного списка  блоков дисковой памяти (рисунок 2.34,б ). При таком способе в начале каждого блока содержится указатель на следующий блок. В этом случае адрес файла также может быть  задан одним числом ­ номером первого блока. В отличие от предыдущего способа,  каждый блок может быть присоединен в цепочку какого­либо файла, следовательно  фрагментация отсутствует. Файл может изменяться во время своего существования,  наращивая число блоков. Недостатком является сложность реализации доступа к  произвольно заданному месту файла: для того, чтобы прочитать пятый по порядку блок  файла, необходимо последовательно прочитать четыре первых блока, прослеживая  цепочку номеров блоков. Кроме того, при этом способе количество данных файла,  содержащихся в одном блоке, не равно степени двойки (одно слово израсходовано на  номер следующего блока), а многие программы читают данные блоками, размер которых  равен степени двойки. Рис. 2.34. Физическая организация файла  а ­ непрерывное размещение; б ­ связанный список блоков;  в ­ связанный список индексов; г ­ перечень номеров блоков Популярным способом, используемым, например, в файловой системе FAT операционной  системы MS­DOS, является использование связанного списка индексов. С каждым  блоком связывается некоторый элемент ­ индекс. Индексы располагаются в отдельной  области диска (в 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. Права доступа к файлу Определить права доступа к файлу ­ значит определить для каждого пользователя набор  операций, которые он может применить к данному файлу. В разных файловых системах  может быть определен свой список дифференцируемых операций доступа. Этот список  может включать следующие операции:  создание файла,  уничтожение файла,  открытие файла,  закрытие файла,  чтение файла,  запись в файл,  дополнение файла,  поиск в файле,  получение атрибутов файла,  установление новых значений атрибутов,  переименование,  выполнение файла,  чтение каталога, и другие операции с файлами и каталогами. В самом общем случае права доступа могут быть описаны матрицей прав доступа, в  которой столбцы соответствуют всем файлам системы, строки ­ всем пользователям, а на  пересечении строк и столбцов указываются разрешенные операции (рисунок 2.35). В  некоторых системах пользователи могут быть разделены на отдельные категории. Для  всех пользователей одной категории определяются единые права доступа. Например, в  системе UNIX все пользователи подразделяются на три категории: владельца файла,  членов его группы и всех остальных. Рис. 2.35. Матрица прав доступа Различают два основных подхода к определению прав доступа:  избирательный доступ, когда для каждого файла и каждого пользователя сам  владелец может определить допустимые операции;  мандатный подход, когда система наделяет пользователя определенными правами  по отношению к каждому разделяемому ресурсу (в данном случае файлу) в  зависимости от того, к какой группе пользователь отнесен. Кэширование диска В некоторых файловых системах запросы к внешним устройствам, в которых адресация  осуществляется блоками (диски, ленты), перехватываются промежуточным программным