Виды ресурсов и возможности их разделения

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

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

• Основные виды ресурсов вычислительной системы:

• 1. Процессор, точнее — процессорное время. Процессорное время делится попеременно (параллельно).

• 2. Память. Оперативная память может делиться и одновременно, и попеременно. Внешняя память может разделяться и одновременно, а доступ к ней всегда разделяется попеременно.

• 3. Внешние устройства, как правило, могут разделяемыми и выделенными.

• 4. Программные модули (прежде всего, системные). Могут быть однократно и многократно используемыми. Однократно используемые могут быть правильно выполнены только один раз, являются неделимым ресурсом. Повторно используемые программные модули могут быть непривилегированными, привилегированными и реентерабельными.

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

• Существуют еще повторно входимые программные модули. Они состоят привилегированных секций.

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

Процессы и потоки.

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

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

• Понятие процесса было введено для реализации идей мультипрограммирования.

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

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

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

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

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

? В файловой системе FAT (File Allocation Table — таблица размещения файлов) дисковое пространство любого логического диска делится на две области: системную область и область данных.

? Системная область состоит из следующих компонентов (расположенных в логическом адресном пространстве друг за другом):

– загрузочной записи (BR);

– зарезервированных секторов (ResSec);

– таблицы размещения файлов (FAT);

– корневого каталога (Root Directory, RDir).

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

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

? В таблице FAT кластеры, принадлежащие одному файлу (или файлу-каталогу), связываются в цепочки. Для указания номера кластера в файловой системе FAT16 используется 16-разрядное слово, следовательно, можно иметь до 216 = 65 536 кластеров (с номерами от 0 до 65 535).

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

? Различают следующие элементы таблицы FAT, которые помечаются специальными кодами:

– Свободный кластер

– Зарезервированный кластер

– Плохой кластер

– Последний кластер в цепочке

– Номер следующего кластера в цепочке.

? При выделении нового кластера для записи файла берется первый свободный кластер, это приводит к фрагментации файлов.

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

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

? Корневой каталог помимо размещения в фиксированном месте логического диска имеет еще и фиксированное число элементов.

? Для каждого файла и каталога в файловой системе хранится информация:

– имя файла или каталога

– атрибуты файла

– резервное поле

– время создания

– дата создания

– дата последнего доступа

– зарезервировано

– время последней модификации

– дата последней модификации

– номер начального кластера в FAT

– размер файла

? Для работы с данными на магнитных дисках в системах DOS, которые имеют файловую систему FAT, удобно использовать утилиту Disk Editor из комплекта утилит Питера Нортона.

? Сектор, содержащий системный загрузчик DOS, является самым первым на логическом диске С:. На дискете системный загрузчик размещается в самом первом секторе; его физический адрес равен 0-0-1. Загрузочная запись состоит из двух частей: блока параметров диска и системного загрузчика. Блок параметров диска служит для идентификации физического и логического форматов логического диска, а системный загрузчик необходим в процессе загрузки DOS.

3. Файловые системы VFAT и FAT32

? Одной из важнейших характеристик исходной файловой системы FAT было использование имен файлов формата 8.3. К стандартной системе FAT добавились еще две разновидности, используемые в ОС от Microsoft (Windows 95 и Windows NT): VFAT (виртуальная система FAT) и система FAT32, используемая в одной из редакций ОС Windows 95 и Windows 98.

? Файловая система VFAT впервые появилась в Windows 3.11 (Windows for Workgroups). С выходом Windows 95 в VFAT добавилась поддержка длинных имен файлов. Наряду с длинными именами в ней поддерживаются имена формата 8.3, а также существует специальный механизм для преобразования имен 8.3 в длинные имена, и наоборот.

? VFAT поддерживается исходными версиями Windows 95, Windows NT 4, Windows 2000 и Windows XP. ? Основными недостатками файловых систем FAT и VFAT являются большие потери на кластеризацию при больших размерах логического диска и ограничения на сам размер логического диска. Поэтому в Microsoft Windows 95 на смену системе VFAT пришла файловая система FAT32.

? Самое принципиальное отличие – FAT32 намного эффективнее расходует дисковое пространство. Кластеры в этой системе меньше. FAT32 также может перемещать корневой каталог и использовать резервную копию FAT вместо стандартной. Расширенная загрузочная запись FAT32 позволяет создавать копии важных структур данных.

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

? Ранее требовалось, чтобы вся информация корневого каталога находилась на одном дисковом кластере. При этом каталог мог содержать не более 512 файлов.

? Для представления длинного имени в FAT32 стали использовать элементы каталога, в том числе и корневого, поэтому количество файлов увеличили с 512 до 2048.

Способ представления в VFAT длинного имени.

? Первые 11 байт элементов каталога DOS используются для хранения имени файла. Каждое имя разделяется на две части: первые 8 байтов – собственно имя, последние 3 – символы расширения.

? Если имя файла состоит менее чем из 8 символов, то в элементе каталога оно дополняется символами пробела. Аналогично, расширение может содержать от 0 до 3 символов.

? В 12-том байте элемента каталога хранятся атрибуты файла:

– А (Archive – архив);

– D (Directory – каталог);

– V (Volume – том);

– S (System – системный);

– H (Hidden – скрытый);

– R (Read Only – только для чтения).

? Файл может быть помечен одним или несколькими из указанных атрибутов.

? На дисках FAT12 или FAT16 следующие за именем 10 байт не используются (заполняются нулями и считаются резервными), а на диске с файловой системой FAT32 они содержат самую разную информацию о файле.

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

? Загрузочная запись для диска с FAT32 занимает не один сектор, как в FAT12 и FAT16, а три.

ХПФС

Высокопроизводительная файловая система HPFS (High Performance File System) была представлена фирмой IBM в 1989 году вместе с операционной системой OS/2 1.20. Файловая система HPFS также поддерживалась ОС Windows NT до версии 3.51 включительно. По производительности эта ФС существенно опережает FAT. HPFS позволяет использовать жесткие диски объемом до 2 Терабайт (первоначально до 4 Гбайт). Кроме того, она поддерживает разделы диска размером до 512 Гб и позволяет использовать имена файлов длиной до 255 символов (на каждый символ при этом отводится 2 байта). В HPFS по сравнению с FAT уменьшено время доступа к файлам в больших каталогах.

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

Для нумерации единиц распределения пространства диска HPFS использует 32 разряда, что дает 232, или более 4 миллиардов номеров. Однако HPFS использует числа со знаком, что сокращает число возможных номеров блоков до 2 миллиардов. Помимо стандартных атрибутов файла, HPFS поддерживает расширенные атрибуты файла (Extended Attributes, EA), которые могут содержать до 64 Кб различных дополнительных сведений о файле.

Диск HPFS имеет следующие три базовые структуры (рис. 3): загрузочный блок (BootBlock), дополнительный блок (SuperBlock) и резервный блок (SpareBlock).

Загрузочный блок в HPFS аналогичен загрузочному блоку в FAT. Он располагается в секторах с 0 по 15 и занимает на диске 8 Кб. Системные файлы, также как и в FAT, располагаются в корневом каталоге, но при этом физически могут находиться в любом месте на диске.

В 16 секторе размещается дополнительный блок, содержащий указатель на список блоков битовых карт (bitmap block list). В этом списке перечислены все блоки на диске, в которых расположены битовые карты, используемые для обнаружения свободных секторов. Также в дополнительном блоке хранится указатель на список дефектных блоков (bad block list), указатель на группу каталогов (directory band), указатель на файловый узел корневого каталога и дата последней проверки диска. Файловый узел (fnode) – это структура диска HPFS, которая содержит информацию о расположении файла и о его расширенных атрибутах.

В следующем секторе находится резервный блок, содержащий карту аварийного замещения (hotfix map), указатель на список свободных запасных блоков (directory emergency free block list) и ряд системных флагов. Резервный блок обеспечивает высокую отказоустойчивость HPFS и позволяет восстанавливать поврежденные данные на диске.

Остальное пространство диска разделено на группы (band) хранения данных. Каждая группа занимает 8 Мб и имеет свою собственную битовую карту свободного пространства, которая похожа на таблицу размещения файлов FAT. Каждому сектору группы соответствует один бит к ее битовой карте, показывающий занят ли соответствующий сектор. Битовые карты двух групп располагаются на диске рядом, также как располагаются и сами группы. Это дает возможность непрерывно разместить на жестком диске файл размером до 16 Мб.

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

В отличие от линейной структуры FAT, структура каталога в HPFS представляет собой сбалансированное дерево (так называемое B-дерево) с записями, расположенными в алфавитном порядке. Как показано на рисунке 4, сбалансированное дерево состоит из корневого (root block) и оконечных блоков (leaf block). Блоки занимают 4 последовательных сектора и в среднем могут содержать 40 записей. Каждая запись корневого блока указывает на один из оконечных блоков (если только в каталоге не меньше 40 файлов); в свою очередь, каждая запись в оконечном блоке указывает на файловый узел файла или на оконечный блок следующего уровня. Таким образом, двухуровневая структура может содержать 40 оконечных блоков по 40 записей в каждом и описывать до 1600 файлов. При поиске файловая система HPFS просматривает только необходимые ветви дерева.

Файловый узел имеет размер 512 байт и всегда по возможности располагается непосредственно перед первым блоком своего файла. Каждый файл и каталог диска HPFS имеет свой файловый узел. Информация, хранящаяся в файловом узле, включает в себя расширенные атрибуты файла, если они достаточно малы, чтобы поместится в один сектор диска, и сокращенное имя файла в формате 8.3. Если расширенные атрибуты не помещаются в файловый узел, то в него записывается указатель на них. Положение файла на диске описывается в файловом узле двумя 32-битными числами. Первое из чисел представляет собой указатель на первый блок файла, а второе - длину экстента. Если же файл фрагментирован, то его размещение описывается дополнительными парами 32-битных чисел. В файловом узле можно хранить информацию максимум о 8 экстентах файла. Если файл имеет больше число экстентов, то в его файловый узел записывается указатель на блок размещения (allocation block), который может содержать до 40 указателей на экстенты или на другие блоки размещения. Таким образом, двухуровневая структура блоков размещения может хранить информацию о 480 (12*40) секторах, что теоретически, позволяет работать с файлами размером до 7.68 Гб (12*40*16 Мб).

НТФС

NTFS (New Technology File System) - наиболее предпочтительная файловая система при работе с ОС Windows NT, поскольку она была специально разработана для данной системы. В состав Windows NT входит утилита convert, осуществляющая конвертирование томов с FAT и HPFS в тома NTFS. В NTFS значительно расширены возможности по управлению доступом к отдельным файлам и каталогам, введено большое число атрибутов, реализована отказоустойчивость, средства динамического сжатия файлов, поддержка требований стандарта POSIX. NTFS позволяет использовать имена файлов длиной до 255 символов, при этом она использует тот же алгоритм для генерации короткого имени, что и VFAT. NTFS обладает возможностью самостоятельного восстановления в случае сбоя ОС или оборудования, так что дисковый том остается доступным, а структура каталогов не нарушается.

Каждый файл на томе NTFS представлен записью в специальном файле – главной файловой таблице MFT (Master File Table). NTFS резервирует первые 16 записей таблицы (рис. 6) размером около 1 Мб для специальной информации. Первая запись таблицы описывает непосредственно саму главную файловую таблицу. За ней следует зеркальная запись MFT. Если первая запись MFT разрушена, NTFS считывает вторую запись, чтобы отыскать зеркальный файл MFT, первая запись которого идентична первой записи MFT. Местоположение сегментов данных MFT и зеркального файла MFT хранится в секторе начальной загрузки. Копия сектора начальной загрузки находится в логическом центре диска. Третья запись MFT содержит файл регистрации, применяемый для восстановления файлов. Семнадцатая и последующие записи главной файловой таблицы используются собственно файлами и каталогами на томе.

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

Схема распределения пространства на томе хранится в файле битовой карты (bitmap file). Атрибут данных этого файла содержит битовую карту, каждый бит которой представляет один кластер тома и указывает, свободен ли данный кластер или занят некоторым файлом.

В загрузочном файле (boot file) хранится код начального загрузчика Windows NT.

NTFS также поддерживает файл плохих кластеров (bad cluster file) для регистрации поврежденных участков на томе и файл тома (volume file), содержащий имя тома, версию NTFS и бит, который устанавливается при повреждении тома. Наконец, имеется файл, содержащий таблицу определения атрибутов (attribute definition table), которая задает типы атрибутов, поддерживаемые на томе, и указывает можно ли их индексировать, восстанавливать операцией восстановления системы и т.д.

NTFS распределяет пространство кластерами и использует для их нумерации 64 разряда, что дает возможность иметь 2⁶⁴ кластеров, каждый размером до 64 Кбайт. Как и в FAT размер кластера может меняться, но необязательно возрастает пропорционально размеру диска.

NTFS позволяет хранить файлы размером до 16 эксабайт (2⁶⁴ байт) и располагает встроенным средством уплотнения файлов в реальном времени. Сжатие является одним из атрибутов файла или каталога и подобно любому атрибуту может быть снято или установлено в любой момент (сжатие возможно на разделах с размером кластера не более 4 Кб). При уплотнении файла, в отличие от схем уплотнения используемых в FAT, применяется пофайловое уплотнение, таким образом, порча небольшого участка диска не приводит к потере информации в других файлах.

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

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

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

Начиная с версии Windows NT 5.0 (новое название Windows 2000) Microsoft поддерживает новую файловую систему NTFS 5.0. В новой версии NTFS были введены дополнительные атрибуты файлов; наряду с правом доступа введено понятие запрета доступа, позволяющее, например, при наследовании пользователем прав группы на какой-нибудь файл, запретить ему возможность изменять его содержимое. Новая система также позволяет:

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

Интересной возможностью новой версии Windows NT является динамическое шифрование файлов и каталогов, повышающее надежность хранения информации. В состав Windows NT 5.0 входит файловая система с шифрованием (Encrypting File System, EFS), использующая алгоритмы шифрования с общим ключом. Если для файла установлен атрибут шифрования, то при обращении пользовательской программы к файлу для записи или чтения происходит прозрачное для программы кодирование и декодирование файла.

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

? Борьба с тупиковыми ситуациями основывается на одной из трех стратегий:

? предотвращение тупика;

? обход тупика;

? распознавание тупика с последующим восстановлением.

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

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

? Условие взаимного исключения можно подавить путем разрешения неограниченного разделения ресурсов.

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

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

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

Обход тупиков

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

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

? Классическое решение этой задачи предложено Дейкстрой и известно как алгоритм банкира.

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