Физическая организация FAT

Файлу выделяется память в виде связанного списка кластеров. Номер первого кластера запоминается в записи каталога, где хранятся характеристики этого файла. Остальная адресная информация отделена от кластеров файла. С каждым кластером диска связывается некоторый элемент — индекс. Индексы располагаются в отдельной области диска — в MS-DOS это таблица FAT (Fife Allocation Table), занимающая один кластер. Когда память свободна, все индексы имеют нулевое значение.

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

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

§ Основная копия FA T содержит информацию о размещении файлов и каталогов на диске.

§ Резервная копия FAT.

§ Корневой каталог занимает фиксированную область размером в 32 сектора (16 Кбайт), что позволяет хранить 512 записей о файлах и каталогах, так как каждая запись каталога состоит из 32 байт.

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

Загрузочный сектор

FAT

Копия FAT

Корневой каталог

Область данных

Системная область

Рис. 6. Структура FAT.

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

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

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

§ кластер свободен (не используется);

§ кластер используется файлом и не является последним кластером файла; в этом случае индексный указатель содержит номер следующего кластера файла;

§ последний кластер файла;

§ дефектный кластер;

резервный кластер.

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

Существует несколько разновидностей FAT, отличающихся разрядностью индексных указателей, которая и используется в качестве условного обозначения: FAT12, FAT16 и FAT32.

В файловой системе FAT12 используются 12-разрядные указатели, что позволяет поддерживать до 4096 кластеров в области данных диска;

в FAT16 — 16-разрядные указатели для 65 536 кластеров;

в FAT32 — 32-разрядные для более чем 4 миллиардов кластеров

Имя файла 8байт	Расширение 3байта	Атрибуты	Резервные
R	A	S	H
Резервные	Время 2байта	Дата 2байта	№ первого кластера 2байта	Размер 4байта

Рис. 7.Структура записи в каталоге MS DOS (32 байта).

Планирование заданий

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

Задача – одна или несколько программ, связанных общим назначением, ресурсами.

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

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

Все потоки в рамках одного процесса имеют одно и то же адресное пространство.

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

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

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

§ Невытесняющие (non-preemptive) алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы она выбрала из очереди другой, готовый к выполнению поток. (Невытесняющее планирование используется, например, в MS Windows 3.1 и ОС Apple Macintosh.)

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

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

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

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

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

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

· поток завершился и покинул систему,

· произошла ошибка,

· поток перешел в состояние ожидания,

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

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

Рис.8. Алгоритмы планирования, основанные на квантовании.

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

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

Квант исчерпан

Рис. 9. Квантование с предпочтением потоков, интенсивно обращающихся к вводу - выводу

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

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

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

Во многих ОС предусматривается возможность изменения приоритета в течение жизни потока:

1. либо по инициативе самого потока, когда он обращается с соответствующим вызовом к ОС;

2. либо директивно администратором системы в зависимости от важности работы,

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

Существует 2 вида приоритетного планирования: обслуживание с относительными приоритетами и обслуживание с абсолютными приоритетами.

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

Рис.10. Алгоритмы планирования, основанные на относительных приоритетах.

Поток завершен или ошибка

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

Рис. 11. Алгоритмы планирования, основанные на абсолют н ых приоритетах.

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

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

Смешанные алгоритмы планирования.

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

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

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

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

Распределение ресурсов

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

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

Управление ресурсами включает решение следующих задач:

§ Планирование ресурса – т.е. определение, какому процессу, когда и в каком количестве следует выделить ресурс;

§ Удовлетворение запросов на ресурсы;

§ Отслеживание состояния и учет использования ресурса – т.е. поддержание оперативной информации занят или свободен ресурс и какая доля ресурса уже распределена;

§ Разрешение конфликтов между процессами.

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