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

Основные функции ОС

Начиная с ЭВМ второго поколения, встала задача полной и эффективной загрузки ЭВМ. Решение – в перекладывании на ЭВМ некоторых стандартных действий человека.

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

Можно выделить следующие функции или подсистемы ОС, хотя жесткого разделения этих подсистем нет:

1.    система управления процессами,

2.    система распределения ресурсов,

3.    система распределения оперативной памяти,

4.    система управления вводом – выводом,

5.    файловая система,

6.    интерфейс с пользователем.

Процесс – некоторая логически связанная последовательность действий, не обязательно линейная.

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

Виды ОС: DOS, Windows (версии), UNIX, MAC OS, Novel NetWare и т.п.

Общие черты ОС:

Ø  модульность,

Ø  наличие ядра,

Ø  функциональная избыточность,

Ø  защита,

Ø  привилегированный и непривилегированный режим работы процессора,

Ø  применение паролей,

Ø  принцип независимости программ от внешних устройств

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

Постоянно активный процесс называется резидентным. В Windows такие процессы называют службами, в UNIX – демонами.

Способы построения ОС

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

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

Машинно-зависимые свойства ОС

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

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

Последовательные и параллельные структуры программ

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

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

Вычислительный процесс и его реализация с помощью ОС

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

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

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

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

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

Сохранность и защита программных систем

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

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

Интерфейсы и основные стандарты в области системного программного обеспечения

Познакомиться со всем комплексом системных программ можно в справочниках (например, MSDN)  и на сайте производителя.

В RFC документах мы также можете найти подробные описания стандартов.

Сетевые ОС и  ОС автономного компьютера

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

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

Особенности алгоритмов управления ресурсами

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

Поддержка многозадачности.

По числу одновременно выполняемых задач операционные системы могут быть разделены на два класса:

однозадачные (например, MS-DOS, MSX) и

многозадачные (OC EC, OS/2, UNIX, Windows 95-98).

Под задачей можно понимать некоторую прикладную программу, приложение (например, MS Word, MS Excel и т.п.)

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

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

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

Поддержка многопользовательского режима.

По числу одновременно работающих пользователей ОС делятся на:

·         однопользовательские (MS-DOS, Windows 3.x, ранние версии OS/2);

·         многопользовательские (UNIX, Windows более старших версий).

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

Например, Windows 3.1 является многозадачной, но однопользовательской ОС. В более старших версиях Windows появилась команда «RUN AS», позволяющая запустить некоторый процесс (задачу) от имени другого пользователя. В результате такого запуска на компьютере будут активны уже два пользователя: тот, от имени которого был произведен вход в систему, и тот, от имени которого запущен процесс командой «RUN AS».

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

Вытесняющая и невытесняющая многозадачность.

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

не вытесняющая многозадачность (NetWare, Windows 3.x);

вытесняющая многозадачность (Windows NT, OS/2, UNIX).

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

Поддержка многонитевости.

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

Многопроцессорная обработка.

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

В наши дни становится общепринятым введение в ОС функций поддержки многопроцессорной обработки данных. Такие функции имеются в операционных системах Solaris с версии 2.x фирмы Sun, Open Server с версии 3.x компании Santa Crus Operations, OS/2 фирмы IBM, Windows фирмы Microsoft, начиная с  NT, и NetWare 4.1 фирмы Novell.

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

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

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

Особенности аппаратных платформ

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

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

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

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

Другие требования предъявляются к операционным системам кластеров. Кластер - слабо связанная совокупность нескольких вычислительных систем, работающих совместно для выполнения общих приложений, и представляющихся пользователю единой системой. Наряду со специальной аппаратурой для функционирования кластерных систем необходима и программная поддержка со стороны операционной системы, которая сводится в основном к синхронизации доступа к разделяемым ресурсам, обнаружению отказов и динамической реконфигурации системы. Одной из первых разработок в области кластерных технологий были решения компании Digital Equipment на базе компьютеров VAX. Этой компанией было заключено соглашение с корпорацией Microsoft о разработке кластерной технологии, использующей Windows NT. Несколько компаний предлагают кластеры на основе UNIX-машин.

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

Особенности областей использования

Многозадачные ОС подразделяются на три типа в соответствии с использованными при их разработке критериями эффективности:

системы пакетной обработки (например, OC EC),

системы разделения времени (UNIX, VMS),

системы реального времени (QNX, RT/11).

Системы пакетной обработки

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

Системы разделения времени

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

Системы реального времени

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

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

Особенности методов построения

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

К таким базовым концепциям относятся:

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

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

Наличие нескольких прикладных сред дает возможность в рамках одной ОС одновременно выполнять приложения, разработанные для нескольких ОС. Многие современные операционные системы поддерживают одновременно прикладные среды MS-DOS, Windows, UNIX (POSIX), OS/2 или хотя бы некоторого подмножества из этого популярного набора. Концепция множественных прикладных сред наиболее просто реализуется в ОС на базе микроядра, над которым работают различные серверы, часть которых реализуют прикладную среду той или иной операционной системы.

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

Управление процессами. Распределение ресурсов.

Управление процессами

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

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

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

Очевидно, что процессы не могут выполняться одновременно (процессор-то один), но подсистема управления процессами старается распределить процессорное время между процессами. Если какой-то процесс приостановился, ожидая от Вас ввода данных с клавиатуры, то резонно отдать процессор другому процессу!

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

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

Состояние процесса, контекст и дескриптор процесса

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

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

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

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

Дескриптор процесса:

идентификатор

приоритет

номер кодового сегмента

номер байта в кодовом сегменте

…

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

Контекст процесса:

состояние регистров процессора

указатели на открытые файлы

режим работы процессора

коды необработанных ошибок

….

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

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

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

§  создать информационные структуры, описывающие данный процесс, то есть его дескриптор;

§  включить дескриптор нового процесса в очередь готовых процессов;

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

Алгоритмы планирования процессов

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

§  определение момента времени для смены выполняемого процесса;

§  выбор процесса на выполнение из очереди готовых процессов;

§  переключение контекстов "старого" и "нового" процессов.

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

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

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

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

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

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

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

Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты.

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

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

1.    процесс завершился,

2.    процесс передал управление ОС,

3.    произошла ошибка,

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

5.    закончился квант времени.

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

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

Вытесняющие и не вытесняющие алгоритмы планирования

Существует два основных типа процедур планирования процессов - вытесняющие (preemptive) и не вытесняющие (non-preemptive).

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

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

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

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

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

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

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

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

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

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

Однако почти во всех современных операционных системах, ориентированных на высокопроизводительное выполнение приложений (UNIX, Windows NT, OS/2, VAX/VMS), реализована вытесняющая многозадачность. В последнее время дошла очередь и до ОС класса настольных систем, например, OS/2 Warp и Windows 95. Возможно, в связи с этим вытесняющую многозадачность часто называют истинной многозадачностью.

Организация доступа к ресурсам

Проблема синхронизации

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

Процесс R				TNF
команды …			1	c.doc
К = NEXT			2	Dfg.xls
TNF(K)=”a.txt”			3
NEXT=NEXT+1		NEXT	4
команды …		3	5
			6
Процесс S			7
команды …			8
К = NEXT			9
TNF(K)=”в.txt”			10
NEXT=NEXT+1			11
команды …			12
			13

 

Рисунок 2 - Пример необходимости синхронизации

Пренебрежение вопросами синхронизации процессов, выполняющихся в режиме мультипрограммирования, может привести к их неправильной работе или даже к краху системы. Рассмотрим, например (рисунок 2), программу печати файлов (принт-сервер). Эта программа печатает по очереди все файлы, имена которых последовательно в порядке поступления записывают в специальный общедоступный список "заказов" (TNF) другие программы. Особая переменная NEXT, также доступная всем процессам-клиентам, содержит номер первой свободной для записи имени файла позиции таблицы "заказов". Процессы-клиенты читают эту переменную (то есть запоминают ее значение в своей памяти), записывают в соответствующую позицию таблицы "заказов" имя своего файла и наращивают значение NEXT на единицу. Предположим, что в некоторый момент процесс R решил распечатать свой файл, для этого он прочитал значение переменной NEXT, значение которой для определенности предположим равным 3. Процесс запомнил это значение в своей внутренней переменной, но поместить имя файла не успел, так как его выполнение было прервано вследствие исчерпания кванта.

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

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

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

Критическая секция

Из-за чего произошла путаница в предыдущем примере? Очевидно, что из-за того, что процесс прервали тогда, когда он еще не закончил работу с разделяемым ресурсом. Что же делать? Первый ответ – не прерывать процесс во время работы с разделяемым ресурсом. Действительно, проблема, описанная выше, в таком случае не возникнет, но могут возникнуть другие (ведь мы не случайно только что решили, что более защищенной является система с вытесняющей многозадачностью!).

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

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

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

Другим способом является использование блокирующих переменных. С каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не находится в данный момент в критической секции, связанной с данным процессом), и значение 0, если ресурс занят. На рисунке 3 показан фрагмент алгоритма процесса, использующего для реализации взаимного исключения доступа к некоторому разделяемому ресурсу блокирующую переменную РЕСУРС_1. Перед входом в критическую секцию процесс проверяет, свободен ли ресурс РЕСУРС_1. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной РЕСУРС_1 устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом, значение переменной РЕСУРС_1 снова устанавливается равным 1.

Процесс А (не совсем верная реализация блокирующих переменных):

если не определена РЕСУРС_1 то    определить глобальную переменную РЕСУРС_1    РЕСУРС_1 = 1 конец если повторять пока РЕСУРС_1<>1 конец повтора РЕСУРС_1 = 0 ‘ так нельзя – операция проверки и установки должна быть неделимой, то есть предыдущий цикл и текущая операция присваивания должны выполняться как единая операция «проверка-занятие» Критическая секция: работа с разделяемым ресурсом РЕСУРС_1 = 1

 

Процесс А (правильный способ – пользуемся системной операцией ПРОВЕРКА_ЗАНЯТИЕ:

если не определена РЕСУРС_1 то    определить глобальную переменную РЕСУРС_1    РЕСУРС_1 = 1 конец если повторять пока не ПРОВЕРКА_ЗАНЯТИЕ (РЕСУРС_1) конец повтора Критическая секция: работа с разделяемым ресурсом РЕСУРС_1 = 1

Рисунок 3 - Реализация критических секций с использованием блокирующих переменных

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

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

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

Для устранения таких нежелательных потерь может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по-своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. На рисунке 4 показан фрагмент алгоритма процесса, использующего эти функции. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса d. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс d, после выхода из критической секции вызывает системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.

Рассмотрим пример. Пусть два процесса пишут поочередно сообщения в «почтовый ящик». Ящик считаем безразмерным. Сообщение может быть и длинным и коротким, очевидно, что два сообщения нельзя перемешивать. Заводим блокирующую переменную «МОЖНОПИСАТЬ», сигнализирующую о том, можно ли писать в настоящий момент в «почтовый ящик» (1 – можно писать, 0 – ящик занят). Процессы вводят сообщения от пользователя. Признаком конца сообщения является нажатие клавиши ENTER. Почтовым ящиком сделаем файл Р. Признаком конца всех сообщений F10.

Описание процессов А и В приведены ниже (они одинаковы!)

Процесс А (или В):

если не определена МОЖНОПИСАТЬ то    определить глобальную переменную МОЖНОПИСАТЬ    МОЖНОПИСАТЬ = 1 конец если S = ввод очередного символа с клавиатуры SL =”” повторять     повторять пока S<>F10 и S<>ENTER         SL = SL+S         S = ввод очередного символа с клавиатуры     конец ввода символов     WAIT(МОЖНОПИСАТЬ)         открыть файл P      записать в файл P сообщение SL      закрыть файл P      POST (МОЖНОПИСАТЬ) конец повтор пока S<>F10

Рисунок 4 - Реализация критической секции с использованием системных функций WAIT(D) и POST(D)

Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел два новых примитива. В абстрактной форме эти примитивы, обозначаемые P и V, оперируют над целыми неотрицательными переменными, называемыми семафорами. Пусть S такой семафор. Операции определяются следующим образом:

V(S): переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.

P(S): уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией.

В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную. Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией P (сравните эти операции с системными функциями WAIT и POST).

Применение семафоров необходимо тогда, когда требуется определить степень занятости некоторого ресурса, а не просто получить ответ на вопрос «занят ресурс или свободен». Рассмотрим использование семафоров на классическом примере взаимодействия двух процессов, выполняющихся в режиме мультипрограммирования, один из которых пишет данные в буферный пул (список) в конец, а другой считывает их из буферного пула с первой записи списка и удаляет. Пусть буферный пул состоит из N записей. Процесс "писатель" должен приостанавливаться, когда все записи буфера оказываются занятыми, и активизироваться при освобождении хотя бы одной записи. Напротив, процесс "читатель" приостанавливается, когда все записи пусты, и активизируется при появлении хотя бы одной записи.

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

 

#define N 256    /* Глобальные переменные

int e = N, f = 0, b = 1;

 

void Writer (){

  while(1){

    PrepareNextRecord(); /* подготовка новой записи   */

    P(e);           /* Уменьшить число свободных буферов, если они есть */

                       /* в противном случае - ждать, пока они освободятся */

    P(b);           /* Вход в критическую секцию  */

    AddToBuffer();  /* Добавить новую запись в буфер */

    V(b);           /* Выход из критической секции   */

    V(f);           /* Увеличить число занятых буферов */

  }

}

 

void Reader (){

  while(1){

      P(f);             /* Уменьшить число занятых буферов, если они есть */

                        /* в противном случае ждать, пока они появятся    */

      P(b);             /* Вход в критическую секцию                      */

      GetFromBuffer();  /* Взять запись из буфера                         */

       V(b);             /* Выход из критической секции                    */

       V(e);             /* Увеличить число свободных буферов              */

       ProcessRecord();  /* Обработать запись                              */

    }

}

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

Рассмотрим еще пример. Пусть Вам надо запрограммировать следующую задачу: пусть процесс ВВОД вводит с клавиатуры очередное слово на русском языке, конец слова определяется по символу ENTER. Признаком завершения ввода является ввод подряд двух ENTER. Это слово заносится в некоторый буфер, например, текстовый файл. Процесс ПЕРЕВОД выбирает по одному слова из файла, переводит их на английский язык и показывает на экране пользователя. Запись в файл сделаем ограниченной, то есть разрешим записывать не более чем N слов. Тогда процесс писатель должен приостановиться, если файл уже заполнен. Процесс перевод, выбирающий слова из файла, наоборот, должен приостановиться, если слов в файле не осталось. Таким образом, нам потребуется два семафора: «КВОСЛОВ» (количество слов) и «КВОСВМЕСТА» (количество свободного места).

Процесс ВВОД:

Процесс ПЕРЕВОД:

если не определено КВОСЛОВ то    определить семафор КВОСЛОВ    КВОСЛОВ = 0 конец если если не определено КВОСВМЕСТА то    определить семафор КВОСВМЕСТА    КВОСВМЕСТА = N конец если открыть файл P S = ввод очередного символа с клавиатуры SL =”” повторять     повторять пока S<>ENTER         SL = SL+S     конец повтора ввода символов     если SL<>”” то           начало_крит_секции           уменьшить(КВОСВМЕСТА)           увеличить(КВОСЛОВ)           перейти в конец файла           записать в файл P слово SL          конец_крит_секции      конец если конец повтора пока SL<>”” закрыть файл P

если не определено КВОСЛОВ то    определить семафор КВОСЛОВ    КВОСЛОВ = 0 конец если если не определено КВОСВМЕСТА то    определить семафор КВОСВМЕСТА    КВОСВМЕСТА = N конец если открыть файл P повторять пока ИСТИНА    начало_крит_секции    уменьшить(КВОСЛОВ)    увеличить(КВОСВМЕСТА)    перейти в начало файла    прочесть слово    передвинуть слова в файле вверх    конец_крит_секции    перевести слово    вывести на экран конец повтора закрыть файл P

Тупики

Приведенный выше пример поможет нам проиллюстрировать еще одну проблему синхронизации - взаимные блокировки, называемые также дедлоками (deadlocks), клинчами (clinch) или тупиками. Если переставить местами операции P(e) и P(b) в программе "писателе", то при некотором стечении обстоятельств эти два процесса могут взаимно заблокировать друг друга. Действительно, пусть "писатель" первым войдет в критическую секцию и обнаружит отсутствие свободных буферов; он начнет ждать, когда "читатель" возьмет очередную запись из буфера, но "читатель" не сможет этого сделать, так как для этого необходимо войти в критическую секцию, вход в которую заблокирован процессом "писателем".

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

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

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

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

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

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

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

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

Пример. Попробуем провести анализ заданных таблиц:

 

Таблица распределения ресурсов (какой процесс, какие ресурсы занимает)			Таблица запросов к ресурсам (какой процесс, какой ресурс ожидает)
MS WORD Outlook Express MS EXEL Explorer Win Commander	файл А сетевая карта файл В Принтер дисковод а:		Access MS WORD MS EXEL Explorer	сетевая карта файл В Принтер файл А

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

2.        Теперь точно так же рассуждаем для следующего процесса из очереди ожидания - MS WORD.  MS WORD ожидает файл В. В таблице распределения отыскиваем процесс, занимающий файл В. Это - MS EXEL. Теперь ищем MS EXEL в таблице запросов. Оказывается, он ждет принтер. Далее ищем в таблице распределения, кто занимает принтер. Это – Explorer. Снова по таблице ожидания ищем, что ожидает Explorer. Он ждет файл А. Наконец, по таблице распределения смотрим, какой процесс занимает файл А и обнаруживаем, что это - MS WORD. Так как вернулись к исходному процессу, делаем вывод о наличии тупика.

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

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

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

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

Итак, методы решения проблемы синхронизации:

1.    запрет прерываний процесса во время работы с ресурсом;

2.    блокирующие переменные;

3.    функции WAIT(ресурс) POST(ресурс);

4.    семафоры;

5.    мониторы.

Нити

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

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

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

Для этих целей современные ОС предлагают использовать механизм многонитевой обработки (multithreading). При этом вводится новое понятие "нить" (thread), а понятие "процесс" в значительной степени меняет смысл.

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

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

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

Нити иногда называют облегченными процессами или мини-процессами или потоками. Действительно, нити во многих отношениях подобны процессам. Каждая нить выполняется строго последовательно и имеет свой собственный программный счетчик и стек. Нити, как и процессы, могут, например, порождать нити-потомки, могут переходить из состояния в состояние. Подобно традиционным процессам (то есть процессам, состоящим из одной нити), нити могут находиться в одном из следующих состояний: ВЫПОЛНЕНИЕ, ОЖИДАНИЕ и ГОТОВНОСТЬ. Пока одна нить заблокирована, другая нить того же процесса может выполняться. Нити разделяют процессор так, как это делают процессы, в соответствии с различными вариантами планирования.

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

Итак, нити имеют собственные:

программный счетчик, стек, регистры, нити-потомки, состояние.

Нити разделяют (то есть имеют в общем пользовании):

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

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

Широкое применение находит многонитевая обработка в распределенных системах. Об этом будет сказано позже.

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

Другой пример использования нитей - это управление сигналами, такими как прерывание с клавиатуры (del или break). Вместо обработки сигнала прерывания, одна нить назначается для постоянного ожидания поступления сигналов. Таким образом, использование нитей может сократить необходимость в прерываниях пользовательского уровня. В этих примерах не столь важно параллельное выполнение, сколь важна ясность программы.

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

Вопросы и задачи:

·         Назовите возможные состояния процесса, какие очереди организует ОС?

·         Что такое контекст и дескриптор? Когда появляются контекст и дескриптор процесса?

·         Преимущества и недостатки вытесняющей и не вытесняющей многозадачности.

·         Причины, по которым процесс покидает процессор в случае вытесняющей многозадачности и не вытесняющей?

·         Приведите пример, показывающий проблему синхронизации.

·         Что такое критическая секция, приведите пример некоторой программы, укажите к ней критическую секцию.

·         Сколько критических секций одновременно может поддерживать одна ОС.

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

·         Чем плох метод блокирующих переменных, на что предлагается его заменить?

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

·         Чем отличается метод семафоров в общем случае от метода блокирующих переменных. Приведите примеры.

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

·         Приведите пример возможного тупика.

·         Что такое монитор, его отличие от семафоров.

·         Методы борьбы с тупиками.

·         Составьте алгоритм распознавания тупика.

·         Что такое нити. В какой ситуации применение нитей приводит к повышению производительности, а в какой – к понижению.

·         Какова, по-вашему, причина того, что применение нитей не является широко распространенным?

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

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

Файловые системы FAT16,  FAT32, NTFS, NFS и другие. 

Определение

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

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

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

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

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

В MSDOS файловая система носит название FAT, в операционной системе Unix файловая система называется NFS, хотя эта ОС допускает одновременную работу нескольких файловых систем, в Windows может быть установлена одна или несколько из файловых систем – NTFS, FAT32, в Windows 2000 можно установить EFS.

Имена файлов

Файлы идентифицируются именами. Пользователи дают файлам символьные имена, при этом учитываются ограничения ОС как на используемые символы, так и на длину имени. В файловой системе FAT16 (MS-DOS)  длина имен ограничивается: 8 символов - собственно имя, 3 символа - расширение имени, а в ОС UNIX System V имя не может содержать более 14 символов.

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

Например, Windows NT в своей файловой системе NTFS устанавливает, что имя файла может содержать до 255 символов, не считая завершающего нулевого символа.

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

Типы файлов

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

Обычные файлы в свою очередь условно подразделяются на выполняемые и файлы данных. Выполняемые файлы часто имеют сложную внутреннюю структуру, например, объектный код программы или архивный файл. Файлы данных не содержат программный код. Подчеркнем, что такое деление условно. Например, традиционные динамические библиотеки могут содержать один выполняемый файл, который запускается по умолчанию и помогает просмотреть содержимое библиотеки. Еще интереснее становится вопрос "является ли файл выполняемым?" для файла-документа, содержащего программы на скрипт языках (программа на VBA в документе MS Word или MS Excel, а также программы на Jscript в документе на HTML).

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

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

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

В разных файловых системах могут использоваться в качестве атрибутов разные характеристики, например: информация о разрешенном доступе, пароль для доступа к файлу, владелец файла, создатель файла, признак         "только для чтения",            "скрытый файл", «системный файл»,  "архивный файл",             "двоичный/символьный", "временный" (удалить после  завершения процесса), признак блокировки, длина записи, указатель на ключевое поле в записи, длина ключа, времена создания,    последнего доступа,         последнего изменения,  текущий размер файла,  максимальный размер файла.

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

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

Записи могут быть фиксированной длины или переменной длины. Записи могут быть расположены в файле последовательно (последовательная организация). Это выполняемые файлы - EXE, COM, DLL, а также многие файлы с данными -  BMP, TXT, DOC, XLS и т.п.

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

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

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

Первая попытка

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

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

Очевидный вывод состоит в том, что надо где-то расположить перечень имен файлов с адресами  (номер кластера диска) начала файла. Так как на диске не может быть ничего, кроме файлов, то это тоже файл, файл особой структуры. Этот файл – каталог. Требуется его расположить в заранее известном ОС месте (иначе ОС требуется искать этот файл, а как это сделать?)!  Таким образом, мы решаем проблему поиска файлов. Но проблема изменения размеров и удаления файлов при этом не решается!

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

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

Вторая попытка

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

Можно организовать дело так, что файлу будет выделяться место «кусочками», а эти «кусочки» будут связываться в единый список для каждого файла. Минимальная дисковая память, выделяемая операционной системой файлу, называется кластером. Итак, наш кусочек – кластер. Какого размера кластер? Об этом еще позже. Пока скажем только то, что размер кластера = 2^n (два в степени n байт).

На рисунке изображена часть диска. В верхней части стоят номера кластеров диска (просто подписи для удобства, ясно, что на диске никаких номеров нет!). Ниже – собственно диск. Пусть сначала потребовалось разместить на диске файл А размером 1,7 кластера. ОС выделяет два кластера, заносит запись в каталог, содержащую имя файла и номер первого кластера. Куда теперь записать номер кластера, в котором файл продолжается? Можно выделить часть первого кластера для этого. Итак, в первый кластер занесется ссылка на продолжение файла, то есть на кластер 2, и начало данных файла, а во втором кластере на месте ссылки будет записан признак конца файла.

Диск

1		2			3		4		5		6		7		8		9
2	A	#	A

 

Каталог
А	1

 

Пусть позже потребовалось выделить место для файла B размером менее 1 кластера. По тем же правилам занесется запись в каталог (В 3), а на месте ссылки будет поставлен признак конца файла. Далее потребовалось выделить кластер для файла С (все аналогично).

Диск

1		2			3		4		5		6		7		8		9
2	A	#	A	#	B	#	C

 

Каталог
А	1
B	3
C	4

 

Теперь – самое интересное: сначала файл В, а затем файл А потребовалось расширить. Для файла В ОС нашла свободное место в 5 кластере, этот кластер отдается файлу В, а ссылка в кластере 3 переписывается с «конец файла» на 5. В 5 кластере, очевидно, ставится на месте ссылки «конец файла». В каталоге ничего не изменяется.

Аналогично выделяется фрагмент, длиной два кластера, для файла А. Картина получится следующая:

Диск

1		2			3		4		5		6		7		8		9
2	A	6	A	5	B	#	C	#	B	7	A	#	A

 

Каталог
А	1
B	3
C	4

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

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

В связи с указанными недостатками эта полученная нами схема практически не применяется.

Заметим, что в приведенном примере неверно то, что каталог изображен в виде отдельной структуры. Напомним, что каталог – это тоже файл, следовательно, он тоже должен занимать место на диске. А где тогда записана информация о файле – каталоге? Проблемы нет для подкаталогов, так как информация о них содержится в родительском каталоге, а вот как быть с корневым? Интересно, что в FAT16 корневой каталог не является обычным файлом, он всегда расположен в начале диска и размер его фиксирован. Но уже в FAT32 придумали, как разрешить изменять размер корневого каталога, хотя он по-прежнему располагается в начале диска.

Третья попытка

Чтобы избавиться от недостатков второго способа, попробуем  список ссылок вынести в заранее определенное место – некоторую таблицу. В результате у нас получится принцип организации  файловой системы FAT!

В файловой системе FAT используется системная структура – таблица FAT. С каждым блоком диска (кластером) связывается одна запись таблицы FAT (номер записи = номеру кластера). Если кластер с номером К распределен некоторому файлу, то в К-той записи таблицы  FAT содержится номер следующего кластера данного файла (это число является также и номером той записи таблицы FAT, в которой содержится информация о продолжении файла!).

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

Итак, FAT – таблица, содержащая столько строк, сколько кластеров на диске. В каждой строке содержатся данные одного из четырех типов: свободный кластер (на рисунке пусто), сбойный кластер (на рисунке отмечен буквой b), ссылка на следующий кластер файла (на рисунке числа), признак конца файла (на рисунке #).

Таблица FAT

1	2	3	4	5	6	7	8	9
2	6	5	#	#	7	#		b

 

Диск

1	2	3	4	5	6	7	8	9
A1	A2	B1	C1	B2	A3	A4

 

Каталог
А	1
B	3
C	4

 

Т.к. нам надо записать в строку FAT  номер кластера, то количество бит, выделяемых под номер должно быть достаточным для представления самого большого возможного на данном диске номера. Пусть на диске 4 кластера, тогда для адресации достаточно 2 бит (2²=4), если на диске 2000 кластеров, то требуется 11 бит (2¹¹=2048). Было принято решение выделять под адрес на диске 16 битов, позволивший адресовать 65532 кластера. Так родилась FAT16. На дискетах принято выделять под адрес 12 бит (FAT12).

С течением времени емкость жестких дисков возрастала, и потребовалось адресовать большее количество кластеров. И потому появилась FAT32, адресующая 2³²=4,294,967,296 кластеров.

Другое решение – перечисление всех занимаемых файлом кластеров.

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

В NTFS принято следующее решение: действительно запись в MFT – файле имеет достаточно большой размер (1 Кб = 1024 байт). Кроме того, различаются начальные записи и записи продолжений, и если файл занимает очень много места, ему может быть выделена одна запись начальная и несколько записей – продолжений. В начальной записи стоит ссылка на запись продолжение. А в записи – продолжении перечисляются номера следующих кластеров файла и стоит ссылка на запись-продолжение (возможно, пустая). Таким образом, информация о занимаемых кластерах может занять несколько записей в файле MFT. Эти записи в общем случае располагаются не рядом (так как они занимаются по мере необходимости).

Проведем достаточно грубый подсчет. NTFS является 32-разрядной файловой системой, следовательно под номер кластера выделяется 32 бита (4 байта), размер кластера принято брать равным 8 секторов, то есть 8сек = 8*512 = 4096 байт (далее будем приближенно брать 4000 байт). Если файл имеет размер 2 мегабайта, то он занимает 2 000 000 байт = 2000000 байт : 4000 байт/кластер = 500 кластеров.  В одной записи MFT – файла помещается не более 1000 байт: 4 байта = 250 номеров, очевидно, что в начальной записи еще меньше. Следовательно, в MFT – файле потребуется занять 500 : 250 = 2, а с учетом особенностей начальной записи – 3 записи MFT – файла. Так как ссылка на продолжение содержится в записи MFT – файла, то чтобы добраться до конца файла приходится последовательно читать все MFT – записи (некоторое замедление!).

NTFS фрагмент MFT- файла
31	…
32	имя атрибуты дата время  37 38 … 57 112…190  начальная        33
33	191 192 235 2 3 4 5 300 301 302 303 304…503   продолжение       нет
34	…

Другое решение – перечисление с дополнительными полями.

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

Заметим, что полная информация о файлах в NFS (файловая система в UNIX) содержится в таблице индексных дескрипторов. Одна запись этой таблицы в два раза меньше от записи MFT – файла: 0.5 кб. Поэтому здесь при простом перечислении потребовалось бы занять в два раза больше записей,  и путь к конечным кластерам был бы в два раза дольше. Разработчики файловой системы NFS попытались улучшить систему простого перечисления кластеров.

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

Рассмотрим пример, как будут записаны номера кластеров, занимаемых файлом в NFS для файла А длиной в 300 кластеров, причем кластеры, которые он занимает, это:  37-57, 112-192, 235, 2-5, 300-503. Фрагмент в таблице индексных дескрипторов выбран для примера.

NFS фрагмент таблицы индексных дескрипторов
134	…
135	имя атрибуты дата время 37 38 39 40 41 42 43 44 45 46 136 137 0   начальная
136	47 48 49 … 57 112 113 … 192 235 2 3 4 5 300 301 …330               продолжение
137	138 139 … 0
138	331 332 333 … 459
139	460 461 … 503

Каталоги. Иерархия каталогов.

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

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

В каталоге FAT16, FAT32 содержится следующая информация (размер записи =32 байта):

·                     Имя файла

·                     Расширение

·                     Базовые атрибуты

·                     Время последнего изменения

·                     Дата последнего изменения

·                     Размер.

·                     Номер первого кластера (номер записи в таблице FAT)

 

В каталоге NTFS содержится следующая информация (размер записи = 1024 байт):

·                     Имя файла

·                     Расширение

·                     Базовые атрибуты

·                     Время последнего изменения

·                     Дата последнего изменения

·                     Размер.

·                     Номер записи в MFT-файле, в которой подробная информация об этом файле

 

В каталоге NFS (UNIX) содержится следующая информация (размер записи около 500 байт):

·                     Имя файла

·                     Индексный дескриптор, который является по существу номером записи в таблице индексных дескрипторов.

 

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

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

Рассуждения о размере кластера.

Какой размер кластера лучше – большой или маленький. Если кластеры большие, то для каждого файла их будет меньше, следовательно, файл получается менее фрагментированным, и, следовательно, он быстрее считается с диска (так как не требуется перемещать читающую головку с места на место). Но, с другой стороны, в среднем половина последнего кластера файла остается незанятой с точки зрения файла, но занятой с точки зрения файловой системы. Следовательно, дисковая память, занятая под "хвосты" файлов пропадает! Для каждого файла пропадает в среднем половина одного кластера, таким образом, пропадает дисковая память объемом "количество файлов"  * "объем половины кластера".

Подумайте,  как связаны потери на "хвосты" с размером файлов.

Переменный или фиксированный размер блока или как найти свободное место

А почему кластеры одинакового размера? Не лучше ли выделять файлу ровно столько места, сколько необходимо?

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

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

адрес = начальный_адрес +(номер_кластера -1)*размер_кластера

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

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

??? Особенности NTFS

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	имена файлов
имена пользователей		win.exe	class.dbf	modem.txt	pict.jpg
	nataly	выполнить	создать, писать, читать	читать	читать
	kira	-	-	читать	читать
	serg	-	читать	читать	читать, писать, переименовывать, удалять
	victor	выполнить		читать, писать, удалять	читать

 

В Windows NT можно организовывать сколько угодно поименованных групп пользователей и каждую группу наделять особыми правами.

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

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

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

В Windows NT приняты названия: доступ «по ресурсам» и «по пользователям».

Файлы и потоки

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

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

Каждый файл в NTFS, вообще говоря, не имеет данных как таковых, а имеет потоки (streams). Один из потоков - данные файла. Но большинство атрибутов файла - тоже потоки! Таким образом, получается, что базовая сущность у файла только одна - номер в MFT, а всё остальное опционально.

Такой подход может использоваться для создания довольно удобных вещей - например, файлу можно "прилепить" еще один поток, записав в него любые данные - например, информацию об авторе и содержании файла, как это сделано в Windows 2000 (самая правая закладка в свойствах файла, просматриваемых из проводника). Интересно, что эти дополнительные потоки не видны стандартными средствами, поэтому наблюдаемый размер файла - это лишь размер основного потока, содержащего традиционные данные. Можно, к примеру, иметь файл нулевой длины, при стирании которого освободится 1 Гбайт свободного места - просто потому, что какая-нибудь хитрая программа или технология прилепила к нему дополнительный поток (альтернативные данные) гигабайтового размера.

Имя файла может содержать любые символы, включая полый набор национальных алфавитов, так как данные представлены в Unicode - 16-битном представлении, которое дает 65535 разных символов. Максимальная длина имени файла - 255 символов.

Каталоги

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

Внутренняя структура каталога в NTFS представляет собой В-дерево.

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

Вывод - для поиска одного файла среди 1000, например, FAT16 придется осуществить в среднем 500 (половина от длины каталога) сравнений, а системе на основе дерева - всего 11 (2^10 = 1024). Экономия времени поиска налицо.

Не стоит, однако думать, что в традиционных системах (FAT) всё так запущено: во-первых, поддержание списка файлов в виде бинарного дерева довольно трудоемко, а во-вторых - даже FAT32 в исполнении современной системы (Windows2000 или Windows98) использует сходную оптимизацию поиска. Хочется также развеять распространенное заблуждение о том, что добавлять файл в каталог в виде дерева труднее, чем в линейный каталог: Это достаточно сравнимые по времени операции. Дело в том, что для того, чтобы добавить файл в каталог, нужно сначала убедится, что файла с таким именем там еще нет.  Тут-то в линейной системе у нас будут трудности с поиском файла, описанные выше, которые с лихвой компенсируют саму простоту добавления файла в каталог.

В NTFS используется структура В-дерева, оптимизированная для работы с медленными внешними запоминающими устройствами. Поскольку время доступа к диску происходит медленнее по сравнению со временем доступа к оперативной памяти примерно в 100000 раз (!), то хотелось бы за одно чтение с диска прочесть максимальное количество нужной информации. Таким образом, за одно чтение с диска нам надо отнести имя не к одной из двух групп, а к одной из K  групп. Как это сделать? Хранить в узле дерева не одно ключевое значение, а несколько. Например, если мы храним в узле дерева 4 значения, то искомое может либо совпасть с одним из них (это - совсем хорошо). Либо мы можем проверить, к какому интервалу искомое значение относится: «меньше первого значения», «больше первого, но меньше второго», «больше второго, но меньше третьего», «больше третьего, но меньше четвертого», «больше четвертого». При применении такой структуры количество возможных обращений к диску вычисляется как log по основанию K от количества записей каталога. В нашем примере для расчета K требуется определить, сколько записей каталога уместятся в блок, читаемый за одно аппаратное обращение к диску. Предположим, что размер кластера равен 4 Кб, а размер записи каталога 400 байт (это близко к правде). Тогда K=10. Таким образом, для поиска файла по каталогу из 1000 записей нам потребуется не более log₁₀1000=3 чтений.

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

Еще одно замечание о способе хранения номеров кластеров, занимаемых файлом.

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

Журналирование

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

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

Пример 2: более сложный случай - идет запись данных на диск. Вдруг, отключается питание и система перезагружается. На какой фазе остановилась запись, где есть данные, а где чушь? На помощь приходит журнал транзакций. Дело в том, что система, осознав свое желание писать на диск, пометила в метафайле $LogFile это свое состояние. Далее в этот журнал помещаются записи о начале и завершении каждой операции. При перезагрузке это файл изучается с целью поиска незавершенных транзакций,  которые были прерваны аварией и результат которых непредсказуем. Все эти транзакции отменяются, место, в которое осуществлялась запись, помечается снова как свободное, индексы и элементы MFT приводятся в состояние, в котором они были до сбоя. Таким образом, система в целом остается стабильна. Ну а если отключение электричества произошло при записи в журнал? Тоже ничего страшного: очередная операция транзакции либо еще и не начиналась (идет только попытка записать намерения её произвести), либо уже закончилась - то есть идет попытка записать, что транзакция на самом деле уже выполнена. В последнем случае при следующей загрузке система сама разберется, что на самом деле всё и так записано корректно (по записям об операциях), и исправит запись в журнале о "незаконченной" транзакции.

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

Замечание. Какую информацию надо записать в журнал транзакций, чтобы можно было восстановить корректность файловой системы в примере 2? Попробуем догадаться. Для того, чтобы записать файл на диск, надо сначала записать данные о нем в MFT – файл. Так как это файл (фиксированной структуры), то может потребоваться сначала его расширить. Затем надо записать данные в обычный каталог. При этом тоже может потребоваться изменить размеры файла-каталога, то есть тоже надо искать свободное место, изменять данные в MFT-файле (добавлять номер кластера в список, изменять размер, дату последнего изменения и т.д.). Затем следует найти свободное место для собственно записываемого файла. Наконец, начать запись файла. В конце в журнал транзакций следует занести запись о завершении физической записи на диск.

Сжатие

Файлы NTFS имеют один довольно полезный атрибут - "сжатый". Дело в том, что NTFS имеет встроенную поддержку сжатия дисков. Любой файл или каталог в индивидуальном порядке может храниться на диске в сжатом виде - этот процесс совершенно прозрачен для приложений. Сжатие файлов имеет очень высокую скорость и только одно большое отрицательное свойство - огромная виртуальная фрагментация сжатых файлов, которая, правда, никому особо не мешает. Сжатие осуществляется блоками по 16 кластеров и использует так называемые "виртуальные кластеры" - опять же предельно гибкое решение, позволяющее добиться интересных эффектов - например, половина файла может быть сжата, а половина - нет. Это достигается благодаря тому, что хранение информации о сжатии определенных фрагментов очень похоже на обычную фрагментацию файлов. Например, типичная запись физической раскладки для реального, несжатого, файла: 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431.

Физическая раскладка типичного сжатого файла: 400, 401, 402, 403, 404, 405, 406, 407, 408,  , , , , , , , 409, 410, , , , , , , , , , , , , , ,.

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

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

Безопасность

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

Права файловой системы NTFS неразрывно связаны с самой системой - то есть они, вообще говоря, необязательны к соблюдению другой системой, если ей дать физический доступ к диску. Для предотвращения чтения данных в случае наличия физического доступа в Windows2000 (NT5) всё же ввели стандартную возможность – шифрование файлов и папок. Подробно о системе прав будет в курсе «Безопасность ИС».

Hard Links

Эта возможность была в NTFS с незапамятных времен, но использовалась очень редко - и тем не менее: Hard Link - это когда один и тот же файл имеет два имени (несколько указателей файла-каталога или разных каталогов указывают на одну и ту же MFT запись). Допустим, один и тот же файл имеет имена 1.txt и 2.txt: если пользователь сотрет файл 1, останется файл 2. Если сотрет 2 - останется файл 1, то есть оба имени, с момента создания, совершенно равноправны. Файл физически стирается лишь тогда, когда будет удалено его последнее имя.

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

Symbolic Links (NT5)

Гораздо более практичная возможность, позволяющая делать виртуальные каталоги, виртуальные файлы - ярлыки. (Виртуальные диски в DOSе делаются командой subst.) Применения достаточно разнообразны: во-первых, упрощение системы каталогов. Если вам не нравится каталог Documents and settings\Administrator\Documents, вы можете прилинковать его в корневой каталог - система будет по-прежнему общаться с каталогом с дремучим путем, а вы - с гораздо более коротким именем, полностью ему эквивалентным. Для создания таких связей можно воспользоваться программой junction (junction.zip (15 Kb), 36 кб), которую написал известный специалист Mark Russinovich (http://www.sysinternals.com/). Программа работает только в NT5 (Windows 2000), как и сама возможность.

Шифрование (в Windows 2000 – EFS)

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

Особенности дефрагментации NTFS

Рассмотрим один достаточно интересный вопрос - фрагментация и дефрагментация NTFS. Дело в том, что ситуация, сложившаяся с этими двумя понятиями в Windows NT, никак не может быть названа удовлетворительной. В самом начале утверждалось, что NTFS не допускает фрагментации файлов. Это оказалось не совсем так, и утверждение сменили - NTFS препятствует фрагментации. Оказалось, что и это не совсем так. То есть она, конечно, препятствует, но толк от этого близок к нулю... Сейчас уже понятно, что NTFS - система, которая как никакая другая предрасположена к фрагментации, что бы ни утверждалось официально. Важно только то, что логически она не очень от этого страдает. Все внутренние структуры построены таким образом, что фрагментация не мешает быстро находить фрагменты данных. Но от физического последствия фрагментации – лишних движений головок – NTFS, конечно, не спасает.

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

Диск NTFS поделен на две зоны. В начала диска идет MFT зона - зона, куда растет MFT, Master File Table. Зона занимает при форматировании 12% диска, и запись данных в эту зону при нормальной работе невозможна. Это сделано для того, чтобы не фрагментировался хотя бы MFT. Но когда весь остальной диск заполняется - зона сокращается ровно в два раза. Это может произойти и повторно. Таким образом, мы сталкиваемся с ситуацией заполнения диска несколько раз.  Фрагментация файлов при этом усиливается. В результате  диск, заполненный более чем на 88%, дефрагментировать почти невозможно - даже API дефрагментации не может перемещать данные в MFT зону, следовательно, программе дефрагментации некуда переписать данные даже временно.

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

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

В NT существует стандартное API дефрагментации, которое использует тот же механизм поиска свободного места, что и при нормальной работе системы, и, следовательно,  свободное место ищется в виде кусков, размер которых кратен 16 кластерам. Файл, будучи перемещенный в другое место, оставляет на новом месте "временно занятое место", дополняющее его по размеру до кратности 16 кластерам. "Временно занятое место" служит для облегчения восстановления системы в случае аппаратного сбоя и освобождается через некоторое время, обычно где-то через пол минуты. Это время не достаточно быстро заканчивается (дефрагментатор перейдет уже к другому месту диска), и в карту свободного места заносятся небольшие куски (менее 16 кластеров) уже после работы дефрагментатора.

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

Допустим, мы хотим положить файлы подряд в начало диска. Кладем один файл. Он оставляет хвост занятости дополнения до кратности 16. Кладем следующий - после хвоста, естественно. Через некоторое время, по освобождению хвоста, имеем дырку <16 кластеров, которую потом невозможно заполнить через API дефрагментации! В результате, до оптимизации картина свободного места выглядела так: много дырок примерно одинакового размера. После оптимизации - одна дыра в конце диска, и много маленьких <16 кластеров дырок в заполненном файлами участке. Какие места в первую очередь заполняются? Правильно, находящиеся ближе к началу диска мелкие дырки <16 кластеров. Любой файл, плавно созданный на прооптимизированном диске, будет состоять из большого числа фрагментов. Таким образом, имеется два примерно равнозначных варианта. Первый - часто оптимизировать диск таким дефрагментатором, смиряясь при этом с сильной фрагментацией заново созданных файлов. Второй вариант - вообще ничего не трогать, и смириться с равномерной, но гораздо более слабой фрагментацией всех файлов на диске.

Существовал всего один дефрагментатор, который игнорировал API дефрагментации и работал напрямую - Norton Speeddisk 5.0 для NT4. Когда его пытаются сравнить со всеми остальными - Diskeeper, O&O defrag, т.д. - не упоминают этого главного, самого принципиального, отличия. Просто потому, что эта проблема тщательно скрывается, по крайней мере, уж точно не афишируется на каждом шагу. Speeddisk - единственная на сегодняшний день программа, которая может оптимизировать диск полностью, не создавая маленьких незаполненных фрагментов свободного места.

К сожалению, в Windows 2000 поместили дефрагментатор, который работает через API, и, соответственно плодит дырки <16 кластеров. Так что как только появится (если еще не появился) - так сразу надо устанавливать Speeddisk для W2k.

Что выбрать?

Любая из представленных ныне файловых систем уходит своими корнями в глубокое прошлое - еще к 80-м годам. Да, NTFS, как это не странно - очень старая система! Дело в том, что долгое время персональные компьютеры пользовались лишь операционной системой DOS, которой и обязана своим появлением FAT. Но параллельно разрабатывались и существовали системы, нацеленные на будущее.

NTFS же долго не могла завоевать персональные компьютеры из-за того, что для организации эффективной работы с её структурами данных требовались значительные объемы оперативной памяти. Системы с MFT-записями размером 4 или 8 Мбайт (стандарт 95-96 годов) были просто не способны получить хоть какой-либо плюс, поэтому за ней закрепилась не очень правильная репутация медленной и громоздкой системы. На самом деле это не соответствует действительности - современные компьютеры с памятью более 64 Мб получают просто огромный прирост производительности от использования NTFS.

В данной таблице сведены воедино все существенные плюсы и минусы распространенных в наше время систем, таких как FAT32, FAT и NTFS. Вряд ли разумно обсуждать другие системы, так как в настоящее время 97% пользователей делают выбор между Windows98, Windows NT4.0 и Windows 2000 (NT5.0), а других вариантов там просто нет.

	FAT	FAT32 (vFAT)	NTFS
Системы, её поддерживающие	DOS, Windows9Х, NT всех версий	Windows98, NT5	NT4, NT5
Максимальный размер тома	2 Гбайт	практически неограничен	практически неограничен
Макс. число файлов на томе	примерно 65 тысяч	практически не ограничено	практически не ограничено
Имя файла	с поддержкой длинных имен - 255 символов, системный набор символов	с поддержкой длинных имен - 255 символов, системный набор символов	255 символов, любые символы любых алфавитов (65 тысяч разных начертаний)
Возможные атрибуты файла	Базовый набор	Базовый набор	всё, что придет в голову производителям программного обеспечения
Безопасность	нет	нет	да (начиная с NT5.0 встроена возможность физически шифровать данные)
Сжатие	нет (возможно при использовании дополнительных программ)	нет	да
Устойчивость к сбоям	средняя (система слишком проста и поэтому ломаться особо нечему )	плохая (средства оптимизации по скорости привели к появлению слабых по надежности мест)	полная - автоматическое восстановление системы при любых сбоях (не считая физические ошибки записи, когда пишется одно, а на самом деле записывается другое)
Экономичность	минимальная (огромные размеры кластеров на больших дисках)	улучшена за счет уменьшения размеров кластеров	максимальна. Очень эффективная и разнообразная система хранения данных
Быстродействие	высокое для малого числа файлов, но быстро уменьшается с появлением большого количества файлов в каталогах. Результат - для слабо заполненных дисков - максимальное, для заполненных - плохое	полностью аналогично FAT, но на дисках большого размера (десятки гигабайт) начинаются серьезные проблемы с общей организацией данных	система не очень эффективна для малых и простых разделов (до 1 Гбайт), но работа с огромными массивами данных и внушительными каталогами организована как нельзя более эффективно и очень сильно превосходит по скорости другие системы

Хотелось бы сказать, что если ваша операционная система - NT (Windows 2000), то использовать какую-либо файловую систему, отличную от NTFS - значит существенно ограничивать свое удобство и гибкость работы самой операционной системы. NT, а особенно Windows 2000, составляет с NTFS как бы две части единого целого - множество полезных возможностей NT напрямую завязано на физическую и логическую структуру файловой системы, и использовать там FAT или FAT32 имеет смысл лишь для совместимости - если у вас стоит задача читать эти диски из каких-либо других систем. А с учетом того, что подавляющее большинство современных ОС способны, по меньшей мере, читать разделы NTFS, смысла отказываться от ее использования вообще нет.

В заключении хочется отметить, что существенных изменений в файловой системе, используемой в Windows старше 2000, пока не произошло.

Сравнение быстродействие FAT и NTFS.

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

Любая файловая система хранит данные файлов в неких объемах - секторах, которые используются аппаратурой и драйвером как самая маленькая единица полезной информации диска. Размер сектора в подавляющем числе современных систем составляет 512 байт, и все файловые системы просто читают эту информацию и передают её без какой либо обработки приложениям. Исключений здесь практически нет. Если файл хранится в сжатом или закодированном виде - как это возможно, к примеру, в системе NTFS - то, конечно, на восстановление или расшифровку информации тратится время и ресурсы процессора. В остальных случаях чтение и запись самих данных файла осуществляется с одинаковой скоростью, какую файловую систему вы не использовали бы. Скорость чтения сектора с диска не зависит от файловой системы, а зависит только от диска.

Поиск физических кластеров файла

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

На что влияет этот параметр: на скорость навигации по файлу (доступ к произвольному фрагменту файла).

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

FAT32, из-за большой области самой таблицы размещения будет испытывать огромные трудности, если фрагменты файла разбросаны по всему диску. Дело в том, что FAT (File Allocation Table, таблица размещения файлов) представляет собой мини-образ диска, куда включен каждый его кластер. Для доступа к фрагменту файла в системе FAT16 и FAT32 приходится обращаться к соответствующей частичке FAT. Если файл, к примеру, расположен в трех фрагментах - в начале диска, в середине, и в конце - то в системе FAT нам придется обратиться к фрагменту FAT также в его начале, в середине и в конце. В системе FAT16, где максимальный размер таблицы FAT составляет 128 Кбайт, это не составит проблемы - вся таблица FAT просто хранится в памяти, или же считывается с диска целиком за один проход и буферизируется. FAT32 же, напротив, имеет типичный размер области FAT порядка сотен килобайт, а на больших дисках - даже несколько мегабайт, поэтому таблица не помещается в оперативной памяти. Если файл расположен в разных частях диска - это вынуждает систему совершать движения головок винчестера столько раз, сколько групп фрагментов в разных областях имеет файл, а это сильно замедляет процесс поиска фрагментов файла.

Вывод: Абсолютный лидер - FAT16, он никогда не заставит систему делать лишние дисковые операции для данной цели. Затем идет NTFS - эта система также не требует чтения лишней информации, по крайней мере, до того момента, пока файл имеет разумное число фрагментов. FAT32 испытывает огромные трудности, вплоть до чтения лишних сотен килобайт из таблицы FAT, если файл разбросан разным областям диска. Стоит отметить, что если файл фрагментирован, но лежит компактной кучей фрагментов - FAT32 всё же не испытывает больших трудностей, так как физический доступ к таблице FAT будет также компактен и буферизован.

Поиск свободного места на диске

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

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

Для определения того, свободен ли данный кластер или нет, системы на основе FAT должны просмотреть одну запись FAT, соответствующую этому кластеру. Размер одной записи FAT16 составляет 16 бит, одной записи FAT32 - 32 бита. Для поиска свободного места на диске может потребоваться просмотреть почти всю FAT - это 128 Кбайт (максимум) для FAT16 и до нескольких мегабайт (!) - в FAT32. Для того чтобы не превращать поиск свободного места в катастрофу (для FAT32), операционной системе приходится использовать различные ухищрения.

NTFS имеет битовую карту свободного места – битовый массив, в котором одному кластеру соответствует 1 бит. Значение этого бита отвечает на вопрос «свободен кластер?». Для поиска свободного места на диске приходится оценивать объемы во много раз меньшие, чем в системах FAT и FAT32 (по сравнению  с FAT16 в 16, а с FAT32 – в 32 раза).

Вывод: NTFS имеет наиболее эффективную систему нахождения свободного места. Стоит отметить, что действовать "в лоб" на FAT16 или FAT32 очень медленно, поэтому для нахождения свободного места в этих системах применяются различные методы оптимизации, в результате чего и там достигается приемлемая скорость.

Работа с каталогами и файлами

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

FAT16 и FAT32 (первых версиях) имеют очень компактные каталоги, размер записи каталога небольшой – 32 байта. Более того, из-за сложившейся исторически системы хранения длинных имен файлов (более 11 символов), в каталогах систем FAT используется не очень эффективная и на первый взгляд неудачная, но зато очень экономная структура хранения этих самих длинных имен файлов. Это – так называемые LFN–записи. Работа с каталогами FAT производится достаточно быстро, так как в подавляющем числе случаев каталог (файл данных каталога) не фрагментирован и находится на диске в одном месте.
Единственная проблема, которая может существенно понизить скорость работы каталогов FAT - большое количество файлов в одном каталоге (порядка тысячи или более). Система хранения данных - линейный массив - не позволяет организовать эффективный поиск файлов в таком каталоге, и для нахождения данного файла приходится перебирать большой объем данных (в среднем - половину файлов каталога).

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

Стоит заметить, однако, что сам каталог NTFS представляет собой гораздо менее компактную структуру, нежели каталог FAT - это связано с гораздо большим (в несколько раз только за счет увеличения длины имени от 8 до 255 байт, обычно размер записи – около 450 байт) размером одной записи каталога. Данное обстоятельство приводит к тому, что каталоги на томе NTFS в подавляющем числе случаев сильно фрагментированы. Размер типичного каталога на FAT-е укладывается в один кластер, тогда как сотня файлов (и даже меньше) в каталоге на NTFS уже приводит к размеру файла каталога, превышающему типичный размер одного кластера. Это, в свою очередь, почти гарантирует фрагментацию файла каталога, что, к сожалению, довольно часто сводит на нет все преимущества гораздо более эффективной организации самих данных.

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

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

Практика

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

Требуемый объем оперативной памяти

Очень многие данные современных файловых систем кэшируются или буферизируются в памяти компьютера, что позволяет избежать лишних операций физического чтения данных с диска. Для нормальной (высокопроизводительной) работы системы в кэше приходится хранить следующие типы информации. Данные о физическом местоположении всех открытых файлов. Это, прежде всего, позволит обращаться к системным файлам и библиотекам, доступ к которым идет буквально постоянно, без чтения служебной (не относящейся к самим файлам) информации с диска. Это же относится к тем файлам, которые исполняются в данный момент - т.е. к выполняемым модулям (.exe и .dll) активных процессов в системе. В эту категорию попадают также файлы системы, с которыми производится работа (прежде всего реестр и виртуальная память, различные .ini файлы, а также файлы документов и приложений). Наиболее часто используемые каталоги. К таковым можно отнести рабочий стол, меню "пуск", системные каталоги, каталоги кэша Internet, и т.п. Данные о свободном месте диска - т.е. та информация, которая позволит найти место для сохранения на диск новых данных.

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

FAT16 имеет очень мало данных, отвечающих за организацию файловой системы. Из служебных областей можно выделить только саму область FAT, которая не может превышать 128 Кбайт (!) - эта область отвечает и за поиск фрагментов файлов, и за поиск свободного места на томе. Каталоги системы FAT также очень компактны. Общий объем памяти, необходимый для предельно эффективной работы с FAT-ом, может колебаться от сотни килобайт и до мегабайта-другого - при условии огромного числа и размера каталогов, с которыми ведется работа.

FAT32 отличается от FAT16 лишь тем, что сама область FAT может иметь более внушительные размеры. На томах порядка 5 - 10 Гбайт область FAT может занимать объем в несколько Мбайт, и это уже очень внушительный объем, надежно кэшировать который не представляется возможным. Тем не менее, область FAT, а вернее те фрагменты, которые отвечают за местоположение рабочих файлов, в подавляющем большинстве систем находятся в памяти машины - на это расходуется порядка нескольких Мбайт оперативной памяти.

NTFS, к сожалению, имеет гораздо большие требования к памяти, необходимой для работы системы. Прежде всего, кэширование сильно затрудняют большие размеры каталогов. Размер одних только каталогов, с которыми активно ведет работу система, может запросто доходить до нескольких Мбайт и даже десятков Мбайт! Добавьте к этому необходимость кэшировать карту свободного места тома (сотни Кбайт) и записи MFT для файлов, с которыми осуществляется работа (в типичной системе - по 1 Кбайт на каждый файл). К счастью, NTFS имеет удачную систему хранения данных, которая не приводит к увеличению каких-либо фиксированных областей при увеличении объема диска. Количество данных, с которым оперирует система на основе NTFS, практически не зависит от объема тома, и основной вклад в объемы данных, которые необходимо кэшировать, вносят каталоги. Тем не менее, уже этого вполне достаточно для того, чтобы только минимальный объем данных, необходимых для кэширования базовых областей NTFS, доходил до 5 - 8 Мбайт.

К сожалению, можно с уверенностью сказать: NTFS теряет огромное количество своего теоретического быстродействия из-за недостаточного кэширования. На системах, имеющих менее 64 Мбайт памяти, NTFS просто не может оказаться быстрее FAT16 или FAT32. Единственное исключение из этого правила - диски FAT32, имеющие объем десятки Гбайт. В остальных же случаях - системы с менее чем 64 мегабайтами памяти просто обязаны работать с FAT32 быстрее.

Типичный в настоящее время объем памяти в 64 Мбайта, к сожалению, также не дает возможности организовать эффективную работу с NTFS. На малых и средних дисках (до 10 Гбайт) в типичных системах FAT32 будет работать, пожалуй, немного быстрее. Единственное, что можно сказать по поводу быстродействия систем с таким объемом оперативной памяти - системы, работающие с FAT32, будут гораздо сильнее страдать от фрагментации, чем системы на NTFS. Но если хотя бы изредка дефрагментировать диски, то FAT32, с точки зрения быстродействия, является предпочтительным вариантом. Многие люди, тем не менее, выбирают в таких системах NTFS - просто из-за того, что это даст некоторые довольно важные преимущества, тогда как типичная потеря быстродействия не очень велика.

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

 Быстродействие накопителя

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

Время случайного доступа (random seek time). К сожалению, для доступа к системным областям на типичном диске более сложной файловой системы (NTFS) приходится совершать, в среднем, больше движений головками диска, чем в более простых системах (FAT16 и FAT32). Гораздо большая фрагментация каталогов, возможность фрагментации системных областей - всё это делает диски NTFS гораздо более чувствительными к скорости считывания произвольных (случайных) областей диска. По этой причине использовать NTFS на медленных (старых) дисках не рекомендуется, так как высокое (худшее) время поиска дорожки дает еще один плюс в пользу систем FAT.

Кэширование как чтения, так и записи на уровне жестких дисков (объем буфера HDD - от 128 Кбайт до 1-2 Мбайт в современных дорогих дисках) - фактор, который будет более полезен системам на основе FAT. NTFS из соображений надежности хранения информации осуществляет модификацию системных областей с флагом "не кэшировать запись", поэтому быстродействие системы NTFS слабо зависит от возможности кэширования самого HDD. Системы FAT, напротив, получат некоторый плюс от кэширования записи на физическом уровне. Стоит отметить, что, вообще говоря, всерьез принимать в расчет размер буфера HDD при оценке быстродействия тех или иных файловых систем не стоит.

Подводя краткий итог влиянию быстродействия диска и контроллера на быстродействия системы в целом, можно сказать так: NTFS страдает от медленных дисков гораздо сильнее, чем FAT.

 Размер кластера

Хотелось бы сказать пару слов о размере кластера - тот параметр, который в файловых системах FAT32 и NTFS можно задавать при форматировании практически произвольно. Прежде всего, надо сказать, что больший размер кластера - это практически всегда большее быстродействие (но и большие потери дискового пространства, особенно на маленьких файлах). Размер кластера на томе NTFS, однако, имеет меньшее влияние на быстродействие, чем размер кластера для системы FAT32.

Типичный размер кластера для NTFS - 4 Кбайта. Стоит отметить, что с большим размером кластера отключается встроенная в файловую систему возможность сжатия  файлов. Оптимальным с точки зрения быстродействия, по крайней мере, для средних и больших файлов, считается (самой Microsoft) размер 16 Кбайт. Увеличивать размер далее неразумно из-за слишком больших расходов на неэффективность хранения данных и из-за мизерного дальнейшего увеличения быстродействия. Если вы хотите повысить быстродействие NTFS ценой потери возможности сжатия - задумайтесь о форматировании диска с размером кластера, большим чем 4 Кбайта.

Быстродействие системы FAT32, напротив, можно довольно существенно повысить, увеличив размер кластера. Если в NTFS размер кластера почти не влияет на размер и характер данных системных областей, то в системе FAT увеличивая кластер в два раза, мы сокращаем область FAT в те же два раза. Вспомните, что в типичной системе FAT32 эта очень важная для быстродействия область занимает несколько Мбайт. Сокращение области FAT в несколько раз даст заметное увеличение быстродействия, так как объем системных данных файловой системы сильно сократиться - уменьшается и время, затрачиваемое на чтение данных о расположении файлов, и объем оперативной памяти, необходимый для буферизации этой информации. Типичный объем кластера для систем FAT32 составляет тоже 4 Кбайт, и увеличение его до 8 или даже до 16 Кбайт - особенно для больших (десяток и более гигабайт) дисков - достаточно разумный шаг.

Другие соображения

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

Диск NTFS был получен преобразованием раздела FAT16 или FAT32 (команда convert). Данная процедура в большинстве случаев представляет собой тяжелый случай для быстродействия, так как структура служебных областей NTFS, скорее всего, получится очень фрагментированной. Если есть возможность - избегайте преобразования других систем в NTFS, так как это приведет к созданию очень неудачного диска, которому не поможет даже типичный (неспециализированный) дефрагментатор, типа Diskeeper-а или встроенного в Windows 2000.

Активная работа с диском, заполненным более чем на 80% - 90%, представляет собой катастрофический для быстродействия NTFS случай, так как фрагментация файлов и, самое главное, служебных областей, будет расти фантастически быстро. Если ваш диск используется в таком режиме - FAT32 будет более удачным выбором при любых других условиях.

 Выводы

В данной заключительной части "одной строчкой" собраны ключевые особенности быстродействия этих трех файловых систем.

FAT - плюсы:

Для эффективной работы требуется немного оперативной памяти.

Быстрая работа с малыми и средними каталогами.

Диск совершает в среднем меньшее количество движений головок (в сравнении с NTFS).

Эффективная работа на медленных дисках.

FAT - минусы:

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

Сложности с произвольным доступом к большим (скажем, 10% и более от размера диска) файлам.

Очень медленная работа с каталогами, содержащими большое количество файлов.

NTFS - плюсы:

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

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

Быстрый доступ к произвольному фрагменту файла (например, редактирование больших .wav файлов).

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

NTFS - минусы:

Существенные требования к памяти системы (64 Мбайт - абсолютный минимум, лучше - больше).

Медленные диски и контроллеры сильно снижают быстродействие NTFS.

Работа с каталогами средних размеров затруднена тем, что они почти всегда фрагментированы.

Диск, долго работающий в заполненном на 80% - 90% состоянии, будет показывать крайне низкое быстродействие.

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

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

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

Вопросы и задачи:

·         Что такое файл, что такое каталог? Назовите файловые системы, которые Вы знаете. Какие могут быть имена файлов в разных файловых системах? Какие архитектуры каталогов Вы знаете.

·         Покажите возможные типы физической организации файлов, объясните, чем плоха та или иная организация.

·         Каким образом ОС хранит информацию о физическом расположении файла на диске в разных файловых системах. Приведите пример.

·         Рассчитайте размер FAT для диска объемом 40 Гб. Какую FAT  следует применить?

·         Можно ли на диске объемом 40 Гб создать FAT16? Рассчитайте средние потери дискового пространства на таком диске при хранении 100 файлов.

·         Что такое раздел диска. Какие программы разбивают диск на разделы.

·         Сколько логических дисков может быть на компьютере?

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

·         Оцените объем системных данных в FAT и в NTFS, расположенных на фиксированном месте диска. Какая система более устойчива к физическим повреждениям диска?

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

·         Каким образом организовано сжатие файлов в NTFS.

·         Сравнение файловых систем.

·         Сравнение быстродействия файловых систем.

·         Как связаны потери на "хвосты" с размером файлов?

·         Модель файловой системы (уровни файловой системы).

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

·         Посчитайте объем битовой карты свободного места в NTFS для диска в 40 Гбайт.

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

BIOS, CMOS

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

CMOS  (complementary metal-oxide semiconductor) – микросхема полупроводниковой памяти с очень низким потреблением электроэнергии, в ПК она питается от маленькой батареи или аккумулятора. Объем ее невелик (обычно, 64 байта), в ней содержатся данные, сохраняющиеся даже при отключении компьютера.

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

На современных компьютерах сохранность данных в CMOS обеспечивается применением никель-кадмиевых аккумуляторов, постоянно подзаряжаемого при работе компьютера. Раньше выход из строя батареи мог привести к катастрофическим последствиям. Но и  аккумулятор может сломаться. Скорее всего, Вы заметите, что что-то не в порядке, если начали барахлить системные часы (особенно если они стали отставать!). Трудно сказать почему, но часы – наименее устойчивая часть CMOS. Вероятно, это происходит потому, что часы «идут» при отключенном от сети компьютере, то есть изменяется состояние определенной ячейки памяти. Остальные ячейки не изменяются. Если компьютер стал показывать неверное время, смените аккумулятор! Для того чтобы оградить себя от неудач, обязательно сохраняйте копию всех данных, записанных в CMOS.

Содержащаяся в CMOS информация используется базовой системой ввода-вывода BIOS (Basic Input/Output System). Имеется несколько видов BIOS. Например, видео - BIOS обеспечивает интерфейс между процессором и видеоадаптером. Однако наиболее важные задачи обеспечивает системная BIOS. Физически она записана на микросхеме ROM (ПЗУ), расположенной на материнской плате, и копируется во время загрузки в сегмент верхней памяти ОЗУ объемом 64 Кбайт для быстрого доступа. В функции системной BIOS входят загрузка системы, распознавание имеющихся аппаратных устройств, поиск и запуск ОС. Когда ОС загружена, BIOS обеспечивает ей доступ к аппаратуре.

Работа в DOS обычно предполагает прямое обращение к BIOS, т.е. каждая программа непосредственно взаимодействует с ней. Однако в случае с Windows (начиная c 95) любые обращения к BIOS контролируются операционной системой при помощи стандартных функций ОС. Возможность прямого обращения к BIOS  сохраняется, но такая программа не может считаться работающей в системе Windows. В серии NT прямые обращения к BIOS запрещены.

Сразу после включения компьютера BIOS начинает процедуру тестирования (POST power-on self-test), затем проверяет и инициализирует аппаратные устройства системы. Ход процесса инициализации Вы все это наблюдаете на экране: сначала появляется информация о видеоадаптере, затем о версии BIOS, затем тестирование,…

За исключением устройств с собственными BIOS (например, видеоадаптеров и контроллеров SCSI) инициализация остальных устройств производится на основании данных, сохраняемых в CMOS.

CMOS SETUP

Пока идет тестирование, BIOS предоставляет доступ к небольшой утилите, обычно называемой Setup, которая дает возможность определить и изменить текущие параметры CMOS. На экране появляется сообщение, предлагающее для входа в Setup нажать определенную клавишу (обычно Del). Можно держать эту клавишу нажатой заранее.

Утилита Setup предлагает Вам несколько меню, конкретный вид которых зависит от используемой BIOS, но всегда есть нечто общее: меню стандартных параметров CMOS и меню (одно или несколько) расширенных (дополнительных) параметров.

Любые изменения в установках CMOS требуют особой осторожности – можно легко добиться того, что компьютер перестанет загружаться. К счастью, для работы с CMOS не требуется загрузки компьютера, достаточно заново включить компьютер и снова войти в Setup.

На моделях компьютеров, начиная с Pentium-2 и Celeron, появились средства автоконфигурирования и так называемая "безджамперная конфигурация", при которой параметры процессора (например, коэффициент умножения) устанавливаются тоже в CMOS. В случае ошибки, Вы даже в Setup войти не сможете, но обычно резервируется некоторая комбинация клавиш, по которой автоматически осуществляется сброс установок на умалчиваемые, после чего Вы можете продолжить попытки изменения параметров. Очевидно, что перед тем, как сделать изменения в BIOS, обязательно ознакомьтесь с документацией.

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

Обычно описание BIOS и CMOS дается в руководстве к системной (материнской) плате.

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

В CMOS можно произвести установку системного времени и даты, задать тип монитора (BIOS надо знать, как выводить информацию на монитор). Варианты - VGA, EGA (16 цветов), CGA (черно-белый), MDA (только текст). Необходимо задать параметры накопителей на гибких магнитных дисках (НГМД), если какого-то нет, то сообщить системе об этом. Предлагаются варианты  до 1,44 мгб. Другие накопители, на 100 мгб и более не обслуживаются через BIOS, для них требуются драйверы.

Большинство нынешних систем имеют контроллер EIDE (enhanced Integrated Drive Electronics) для подключения жестких дисков. Схема адресации на диске такого типа называется LBA (logical block addressing). В режиме LBA каждому сектору жесткого диска присваивается некоторый номер. Для дисков SCSI схема LBA использовалась с самого начала, а для дисков IDE она появилась, начиная с 1994 года. Причина – появление дисков емкостью >504 мгб (это максимально адресуемый объем для BIOS с предыдущей системой адресации – CHS). В настоящее время LBA стала стандартом отрасли. Технология LBA позволяет использовать диски емкостью до 128 Гб. Контроллер EIDE позволяет присоединять до 4 устройств, в том числе накопитель CD-ROM.  Таким образом, на вашем компьютере может быть не более 4 дисковых устройств.

Если на компьютере установлен жесткий диск с интерфейсом SCSI (очень хороший, быстрый надежный, но дорогой),  конфигурация этого диска определяется контроллером SCSI, а не BIOS. Обычно контроллер SCSI позволяет присоединять до 8 дисков. Вы можете встретить и разновидности White SCSI и SCSI 2, отличающиеся скоростью работы.

В последние время завоевывает сердца пользователей интерфейс USB. Он отличается тем, что, во-первых, позволяет подключать до 128 устройств, причем последовательно, что заметно снижает количество проводов! Во-вторых, интерфейс USB позволяет производить "горячее подключение" устройств, что категорически запрещено для LPT - порта и IDE. Горячим подключением называется подключение или отключение устройства без останова компьютера и отключения его от электрической сети. На EIDE разъемах при таких манипуляциях могли возникать броски напряжения, приводящие к поломке устройства или всего компьютера. Различают активные USB и пассивные. Активные USB отличаются тем, что они передают не только информационный сигнал, но и питание.

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

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

Поиск НГМД при загрузке требуется включить, только в том случае, когда Вы хотите загрузиться с дискеты. Кроме этого в CMOS задается последовательность поиска системных файлов. Для нормальной работы лучше задать С:, А:.  Так как иначе при загрузке будет потрачено время на ожидание дискеты, к тому же, если у вас в компьютере стоит дискета, зараженная вирусом в boot-секторе, то при попытке загрузиться с нее происходит заражение компьютера.

Загрузить с дискеты Windows в полном объеме конечно невозможно. Но если Ваш компьютер не загружается обычным способом (например, если испорчены или удалены системные файлы), то можно восстановить системные файлы с загрузочной дискеты, либо если дело обстоит еще хуже, попытаться на уровне команд ДОС "вытащить" с жесткого диска все, что получится. Второй пример, когда требуется загрузка с дискеты - это случай с зараженным вирусами компьютером. Рекомендуется позаботиться заранее о том, чтобы у Вас была загрузочная дискета с антивирусной программой или (еще лучше!) загрузочный CD – диск.

Установка (включение) кэш внутреннего и внешнего (1 и 2 уровня). На процессорах выше Pentium  кэш 2 уровня тоже на самом деле внутренний. Кэш повышает скорость передачи данных между процессором и оперативной пямятью (ОП). Если Вам кажется, что компьютер стал работать медленнее, проверьте, не отключился ли в CMOS кэш, что может произойти в результате сбоя при тесте памяти во время загрузки. При неустойчивой работе компьютера (зависаниях) можно попробовать отключить кэш. В некоторых BIOS можно задавать алгоритм кэширования: Write back или Write thru (с обратной или с прямой (сквозной) записью). Второй алгоритм повышает быстродействие, но несколько увеличивает вероятность потери данных при отключении питания.

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

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

Подсистема организации ввода-вывода.

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

Физическая организация устройств ввода-вывода. Блок-ориентированные устройства и байт-ориентированные.

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

В качестве примера рассмотрим низкоуровневую структуру жесткого диска. Диск разбивается на небольшие части – сегменты. Размер сегмента иногда может задаваться пользователем при форматировании. Возможные варианты определяет производитель. Стандартный размер равен 521 байту, из которых 512 байт (4096 бит) – отводятся под данные, а оставшиеся байты образуют заголовок сектора. О заголовке мы расскажем чуть позже.

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

Операционная система обычно имеет дело не с устройством, а с контроллером. Контроллер, как правило, выполняет простые функции, например, преобразует поток бит в блоки, состоящие из байт, и осуществляют контроль и исправление ошибок.  Вернемся к нашему сектору диска. Пусть требуется прочесть некоторый файл, занимающий некоторый кластер, тогда контроллер рассчитывает по номеру кластера номер сектора, определяет, сколько времени следую подождать, чтобы читающая головка расположилась над нужным сектором, и генерирует соответствующие аппаратные команды. В заголовке сектора содержится необходимая для контроллера устройства информация. Например, номер сектора, по которому контроллер определяет, не промахнулся ли он. Очень важна контрольная сумма (или ECC - Error Correcting Code). Контроллер при чтении сектора рассчитывает контрольную суму, и если рассчитанная сумма не совпадает с записанной в заголовке сектора суммой, то регистрируется ошибка. После этого контроллер может попытаться прочесть сектор еще раз. При нескольких неудачах (их число задает производитель), информация об ошибке передается драйверу и операционной системе, а, возможно, и пользователю, если никто не найдет способа замаскировать ошибку. Уточним, для особо любопытных, что в действительности проверка контрольной суммы происходит не так, как описано выше, подробности будут рассказаны в курсе «Надежность информационных систем».

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

Связь контроллера и центрального процессора может быть реализована двумя разными способами: 1) отображаемый на память ввод-вывод (теневые адреса памяти); 2) порты ввода-вывода.

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

ОС выполняет ввод-вывод, записывая команды в регистры контроллера. Например, контроллер гибкого диска IBM PC принимает 15 команд, таких как READ, WRITE, SEEK, FORMAT и т.д. Когда команда принята, процессор оставляет контроллер и занимается другой работой. При завершении команды контроллер организует прерывание для того, чтобы передать управление процессором операционной системе, которая должна проверить результаты операции. Процессор получает результаты и статус устройства, читая информацию из регистров контроллера.

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

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

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

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

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

Синхронные и асинхронные передачи. Разделяемые и выделенные устройства.

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

ОС выполняет операции ввода-вывода асинхронно, но представляет их для пользовательских программ в синхронной форме.

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

Для решения поставленных проблем целесообразно разделить программное обеспечение ввода-вывода на четыре слоя:

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

·         Драйверы устройств,

·         Независимый от устройств слой операционной системы,

·         Пользовательский слой программного обеспечения.

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

Прерывания должны быть скрыты как можно глубже в недрах операционной системы, чтобы как можно меньшая часть ОС имела с ними дело. Наилучший способ состоит в разрешении процессу, инициировавшему операцию ввода-вывода, блокировать себя до завершения операции и наступления прерывания. Процесс может блокировать себя, используя, например, вызов DOWN для семафора, или вызов WAIT для переменной условия, или вызов RECEIVE для ожидания сообщения. При наступлении прерывания процедура обработки прерывания выполняет разблокирование процесса, инициировавшего операцию ввода-вывода, используя вызовы UP, SIGNAL или посылая процессу сообщение. В любом случае эффект от прерывания будет состоять в том, что ранее заблокированный процесс теперь продолжит свое выполнение.

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

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

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

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

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

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

Независимый от устройств слой операционной системы

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

Типичными функциями для независимого от устройств слоя являются:

обеспечение общего интерфейса к драйверам устройств,

именование устройств,

защита устройств,

обеспечение независимого размера блока,

буферизация,

распределение памяти на блок-ориентированных устройствах,

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

уведомление об ошибках.

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

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

Пользовательский слой программного обеспечения

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

count = write (fd, buffer, nbytes),

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

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

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

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

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

 

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

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

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

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

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

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

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

Современные архитектуры файловых систем

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

Новая файловая система имеет многоуровневую структуру, на верхнем уровне которой располагается так называемый переключатель файловых систем (в Windows 95, например, такой переключатель называется устанавливаемым диспетчером файловой системы - installable filesystem manager, IFS). Он обеспечивает интерфейс между запросами приложения и конкретной файловой системой, к которой обращается это приложение. Переключатель файловых систем преобразует запросы в формат, воспринимаемый следующим уровнем - уровнем файловых систем.

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

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

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

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

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

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

Логическая структура диска

Сектор, кластер

Физически жесткий диск представляет из себя «слоеный пирог»: несколько дисков-пластин собраны в пакет.

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

Кластер равен 2ⁿ (степень двойки) секторов. n -  константа для логического диска. Значение n может выбираться автоматически и задаваться вручную при форматировании диска. 

Рассмотрим логическую структуру диска для файловой системы FAT. Мы установили, что таблица FAT должна располагаться в определенном месте диска. Логично предположить, что она занимает начало диска. Каталог тоже должен легко находиться, поэтому поместим его вслед за FAT. Если ограничить размер основного каталога (точнее задать для него фиксированный размер), то достаточно легко посчитать, сколько занимает места таблица FAT, где начинается корневой каталог, а где начинается «область данных», т.е. свободное дисковое пространство, отдаваемое под файлы.

Структура раздела (тома)

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

Кроме того, нужно еще где-то записать данные о самой FAT (например, о ее разрядности!). С этой целью выделили в начале диска один сектор, в который поместили так называемую boot record (загрузочную запись).  Таким образом, получаем следующую структуру:

 

BR

FAT1

FAT2

Корн. каталог

01

02 – n

n –2n

2n – m-1

m

m+1

m+2

m+3

m+4

m+5

m+6

m+7

m+8

m+9

m+10

m+11

1кластер

2 кластер

3 кластер …

Это еще не все!

Разделы, MBR, IPL, BR, PL

Мы видим, что адресное пространство FAT16 по современным меркам невелико. Так каким же образом обходились таким количеством? Оказывается, есть два решения данной проблемы. Первое – увеличить размер кластера, тогда их общее количество останется прежним (и нам хватит 16 разрядов для адресации). Этот способ приводит к большим потерям дисковой памяти в «хвостах» файлов.  Так как файлу место выделяется целыми кластерами, то всегда часть последнего кластера будет оставаться свободной от данных. В среднем потери на «хвост» составляют половину размера кластера. Отсюда очевидно, что при большем размере кластера и средние потери большие.

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

Рассмотрим подробнее содержимое BR. Для этого вернемся к вопросу о последовательности загрузки компьютера. Итак, при включении электричества начинает работать BIOS – программа на микросхеме. Эта программа выбирает из специальной памяти CMOS некоторые характеристики компьютера. Если в CMOS  задано, что загрузочным является диск «С:», то BIOS должна найти ОС на диске «С:». Следовательно, она должна знать, в какую часть диска обратиться и как прочесть то, что там написано. Очевидно, что простейшим решением является следующее: в самом начале диске всегда храним специальную запись - MBR (master boot record). Эта запись состоит из двух частей: таблицы разделов (Partition table) и начального загрузчика (IPL Initial Program Loader).  BIOS передает управление IPL.

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

Загрузчик IPL начинает работу по загрузке ОС. Для этого он отыскивает в таблице разделов загружаемый раздел и передает управление загрузчику из BR – записи загружаемого раздела.

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

Повторим в заключение последовательность программ, работающих при загрузке компьютера, и отметим данные, с которыми эти программы работают:

BIOS – CMOS

IPL – Partition Table

PL – BR

ОС

Программы логического структурирования диска

Теперь рассмотрим вопрос о том, кто и когда структурирует диск, то есть разбивает диск на разделы. Это делается несколькими программами. В списке стандартных программ находим FDISK – программа, разбивающая диск на разделы. Основной ее недостаток в том, что она не может изменить границы ранее заполненных разделов. Несколько больше возможностей у программы PARTM. Обе они могут разбить диск на разделы, то есть создать и заполнить MBR. Одну из этих программ  следует запустить на вновь купленном диске.

Затем следует запустить программу FORMAT. Она продолжит структурирование диска: в каждый раздел занесет BR, FAT1, FAT2  и корневой каталог. Программы форматирования могут, кроме того,  переписывать заголовки секторов, что повышает надежность работы диска. Рекомендуется неустойчиво работающую дискету отформатировать заново. Format  затирает всю информацию на диске!

Есть программы, совмещающие оба действия по структурированию диска. Такова PQMagic, она и разбивает диск на разделы и сразу форматирует эти разделы. Более того, она делает это аккуратно, поэтому ее можно запускать даже на диске с информацией (данные будут сохранены!). PQMagic показывает также потери в хвостах «файлов» на заполненном диске, предлагает изменить размер кластера.

Заметим, что на дискете невозможно создать несколько разделов. А один раздел оформлен обычным способом.

Разделы могут быть двух видов: загрузочный (primary) и нет (extended). А в extended разделе можно выделить место под один и более логический диск (D:, E:, F:, …).

Итак, диск может быть поделен не более чем на 4 раздела (4 строки в MBR). В свою очередь, раздел, объявленный, как расширяемый (extended) можно разбить на несколько логических дисков.

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

MBR

Раздел 1

BAD

Раздел 2

Раздел 3

Служебные программы: проверка диска (Scandisk), дефрагментация (Defrag), восстановление удаленных файлов (Unerase), низкоуровневое редактирование дисковых структур (DiskEdit.).

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

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

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

Перекрестные ссылки – на кластер есть две и более ссылок в FAT или в каталогах. 

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

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

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

Заметим, что Windows поддерживает еще один этап: удаляемый файл вместе с информацией о прежнем местоположении сначала просто перемещается в  корзину (специальная системная папка). Из корзины файл можно восстановить, то есть переместить в любую обычную папку. Если файл удален и из корзины, то тогда требуется восстановление специальными средствами типа  Unerase.

Восстановление удаленных файлов не всегда возможно, так как на месте этого файла уже мог быть размещен другой файл!

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

Раздел NTFS

Раздел NTFS, теоретически, может быть размером 16 Экзобайт. Максимальный размер раздела NTFS на практике в данный момент ограничен лишь размерами жестких дисков. NT4, правда, будет испытывать проблемы при попытке установки на раздел, если хоть какая-нибудь его часть отступает более чем на 8 Гб от физического начала диска, но это – ограничение только для  загрузочного раздела.

При установке NT4.0  если Вы укажете, что желаете отформатировать диск в NTFS, максимальный размер, который она вам предложит, будет всего 4 Гб. Почему так мало, если размер раздела NTFS на самом деле практически неограничен? Дело в том, что установочная секция просто не знает этой файловой системы. Программа установки форматирует диск в обычный FAT, максимальный размер которого в NT составляет 4 Гбайт (с использованием не совсем стандартного огромного кластера 64 Кбайта (2 в 16 степени)), и на этот FAT устанавливает NT. И только в процессе первой загрузки самой операционной системы (еще в установочной фазе) производится быстрое преобразование раздела в NTFS. Так пользователь ничего и не замечает, кроме странного "ограничения" на размер NTFS при установке.

Структура раздела - общий взгляд

Как и любая другая система, NTFS делит все полезное место на кластеры - блоки данных, используемые единовременно. NTFS поддерживает почти любые размеры кластеров - от 512 байт до 64 Кбайт,  практическим стандартом считается кластер размером 4 Кбайт.

Диск NTFS условно делится на две части. При форматировании первые 12% диска отводятся под так называемую MFT зону - пространство, в которое растет метафайл MFT (об этом ниже). Запись каких-либо данных в эту область невозможна. MFT-зона всегда держится пустой - это делается для того, чтобы самый главный, служебный файл (MFT) не фрагментировался при своем росте. Остальные 88% диска представляют собой обычное пространство для хранения файлов.

BR

MFT –зона

данные

 

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

MFT – зона, MFT – файл, метафайлы.

Все элементы системы представляют собой файлы - даже служебная информация, в отличие от FAT, у которой собственно таблица FAT – не файл. Самый главный файл в NTFS называется MFT, или Master File Table - общая таблица файлов. Именно он размещается в MFT зоне и представляет собой централизованный каталог всех остальных файлов диска, включая себя самого. MFT поделен на записи фиксированного размера (обычно 1 Кбайт), и каждая запись соответствует какому либо файлу (в общем смысле этого слова).

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

Первые 16 файлов NTFS (метафайлы) носят служебный характер. Каждый из них отвечает за какой-либо аспект работы системы.

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

Метафайлы находятся корневом каталоге NTFS диска - они начинаются с символа имени "$", хотя получить какую-либо информацию о них стандартными средствами сложно. Любопытно, что и для этих файлов указан вполне реальный размер - можно узнать, например, сколько операционная система тратит на каталогизацию всего вашего диска, посмотрев размер файла $MFT. В следующей таблице приведены используемые в данный момент метафайлы и их назначение.

Вопросы и задачи:

·         CMOS и BIOS, их назначение. Установки в CMOS.

·         Блок-ориентированные устройства и байт-ориентированные устройства.

·         Драйверы, контроллеры, что это, их основные задачи.

·         Организация программного обеспечения.

·         Разделяемые и выделенные устройства.

·         Синхронные и асинхронные передачи.

·         Уровни организации ввода – вывода.