Диспетчеризация задач с использованием динамических приоритетов
При выполнении программ может случиться ситуация, когда одна или несколько задач не могут быть выполнены в течение значительного времени из-за высокой нагрузки в вычислительной системе. Введение механизма динамических приоритетов позволяет реализовать быстрое выполнение коротких задач и гарантировать выполнение любых запросов. Эта дисциплина используется в ОС UNIX.
Каждый процесс имеет два атрибута приоритета, с учетом которого распределяется процессорное время между исполняющимися задачами:
- текущий приоритет, на основе которого осуществляется планирование;
- заказанный относительный приоритет (nice number).
Более высокому значению текущего приоритета может соответствовать более низкий фактический приоритет планирования.
Рассмотрим частный случай, когда текущий приоритет процесса варьируется в диапазоне от 0 (низкий приоритет) до 127 (высокий приоритет). Процессы, выполняющиеся в режиме задачи, имеют более низкий приоритет (0 – 65), чем в режиме ядра (66 – 95, системный диапазон). Приоритеты в диапазоне 96 – 127 относятся к процессам с фиксированным приоритетом.
Процессу, ожидающему недоступный в данный момент ресурс, система присваивает приоритет сна (sleep) из диапазона системных приоритетов и связанное с событием, вызвавшим это состояние. Когда процесс пробуждается, ему присваивается приоритет, равный приоритету сна, который находится в системной области, поэтому вероятность выбора такого процесса на выполнение велика. Такой подход позволяет быстро завершить системный вызов.
После завершения системного вызова восстанавливается приоритет режима задачи, сохраненный перед выполнением системного вызова. Это может привести к снижению приоритета и переключению контекста.
Для принятия решения о выборе следующего запускаемого процесса планировщику необходима информация об использовании процессора. Эта составляющая приоритета уменьшается обработчиком прерываний по таймеру по каждому тику таймера. Когда процесс выполняется в режиме задачи, его текущий приоритет линейно уменьшается.
Каждую секунду процессор пересчитывает приоритеты процессов, готовых к выполнению, что приводит к перемещению процессов в более приоритетные очереди и повышает вероятность их последующего запуска.
Данный алгоритм планирования обеспечивает:
- интересы низкоприоритетных процессов, так как в результате длительного ожидания их приоритет и вероятность выполнения увеличиваются;
- более вероятный выбор интерактивных процессов по сравнению с вычислительными.
Тема 3.2. Организация файловых систем. Типы файловых систем FAT16, FAT32, VFAT, NTFS и другие.
Часть 1 Основные понятия
Введение в ОС
Все компьютерные приложения нуждаются в хранении и обновлении информации. Возможности оперативной памяти для хранения информации ограничены. Во-первых, оперативная память обычно теряет свое содержимое после отключения питания, а во-вторых, объем обрабатываемых данных зачастую превышает ее возможности. Кроме того, информацию желательно иметь в виде, независимом от процессов. Поэтому принято хранить данные на внешних носителях (обычно это диски) в единицах, называемых файлами. В большинстве компьютерных систем предусмотрены устройства внешней (вторичной) памяти, большой емкости, на которых можно хранить огромные объемы данных. Однако характеристики доступа к таким устройствам существенно отличаются от характеристик доступа к основной памяти. Чтобы повысить эффективность использования этих устройств, был разработан ряд специфичных для них структур данных и алгоритмов
История систем управления данными во внешней памяти начинается еще с магнитных лент, но современный облик они приобрели с появлением магнитных дисков. До этого каждая прикладная программа сама решала проблемы именования данных и структуризации данных во внешней памяти. Это затрудняло поддержание на внешнем носителе нескольких архивов долговременно хранимой информации. Историческим шагом явился переход к использованию централизованных систем управления файлами. Система управления файлами берет на себя распределение внешней памяти, отображение имен файлов в адреса внешней памяти и обеспечение доступа к данным.
Файловая система - это часть операционной системы, назначение которой состоит в том, чтобы организовать эффективную работу с данными, хранящимися во внешней памяти и обеспечить пользователю удобный интерфейс при работе с этими данными. Организовать хранение информации на магнитном диске непросто. Это требует хорошего знания устройства контроллера диска, особенностей работы с его регистрами и.т. д. (этим обычно занимается компонент системы ввода-вывода ОС, называемый драйвером диска). Для того чтобы избавить пользователя компьютера от сложностей взаимодействия с аппаратурой и была придумана ясная абстрактная модель файловой системы. Операции записи или чтения файла концептуально проще, чем низкоуровневые операции работы с устройствами.
Основная идея использования внешней памяти состоит в следующем. ОС делит ее на блоки фиксированного размера, например, 4096 байт. С точки зрения пользователя каждый файл состоит из набора индивидуальных элементов, называемых записями (например, характеристика какого-нибудь объекта). Каждый файл хранится в виде определенной последовательности блоков (не обязательно смежных); каждый блок хранит целое число записей. В некоторых ОС (MS-DOS) адреса блоков, содержащих данные файла, могут быть организованы в связный список и вынесены в отдельную таблицу в памяти. В других ОС (Unix), адреса блоков данных файла хранятся в отдельном блоке внешней памяти (так называемом индексе или индексном узле). Этот прием называется индексацией и является наиболее распространенным для приложений, требующих произвольного доступа к записям файлов. Индекс файла состоит из списка элементов, каждый из которых содержит номер блока в файле и указание о местоположении данного блока. В современных ОС файлы обычно представляют собой неструктурированную последовательность байтов (длина записи равна 1) и считывание очередного байта осуществляется с так называемой текущей позиции, которая характеризуется смещением от начала файла. Зная размер блока, легко вычислить номер блока, содержащего текущую позицию. Адрес же нужного блока диска можно затем извлечь из индекса файла. Базовой операцией, выполняемой по отношению к файлу, является чтение блока с диска и перенос его в буфер, находящийся в основной памяти.
Файловая система позволяет при помощи системы справочников (каталогов, директорий) связать уникальное имя файла с блоками вторичной памяти, содержащими данные файла. Иерархическая структура каталогов, используемая для управления файлами, является другим примером индексной структуры. В этом случае каталоги или папки играют роль индексов, каждый из которых содержит ссылки на свои подкаталоги. С этой точки зрения вся файловая система компьютера представляет собой большой индексированный файл.
Понятие «файловая система» включает:
o совокупность всех файлов на диске,
o наборы структур данных, используемых для управления файлами, такие, например, как каталоги файлов, дескрипторы файлов, таблицы распределения свободного и занятого пространства на диске,
o комплекс системных программных средств, реализующих управление файлами, в частности: создание, уничтожение, чтение, запись, именование, поиск и другие операции над файлами.
Файлы управляются ОС. То, как они структурированы, поименованы, используются, защищены, реализованы - одна из главных тем проектирования ОС.
Перечислим основные функции файловой системы:
v Идентификация файлов. Связывание имени файла с выделенным ему пространством внешней памяти.
v Распределение внешней памяти между файлами. Для работы с конкретным файлом не требуется иметь информацию о местоположении этого файла на внешнем носителе информации. Например, для того, чтобы загрузить документ в редактор с жесткого диска нам не требуется знать на какой стороне какого магнитного диска и на каком цилиндре и в каком секторе находится требуемый документ.
v Обеспечение надежности и отказоустойчивости. Стоимость информации может во много раз превышать стоимость компьютера.
v Обеспечение защиты от НСД.
v Обеспечение совместного доступа к файлам, не требуя от пользователя специальных усилий по обеспечению синхронизации доступа.
v Обеспечение высокой производительности.
Иногда говорят, что файл - поименованный набор связанной информации, записанной во вторичную память. Для большинства пользователей файловая система - наиболее видимая часть ОС. Она предоставляет механизм для он-лайнового хранения и доступа, как данным, так и программам ОС для всех пользователям системы. С точки зрения пользователя файл - минимальная величина внешней памяти, то есть данные, записанные на диск должны быть в составе какого-нибудь файла.
Важный аспект организации файловой системы - учет стоимости операций взаимодействия с вторичной памятью. Процесс считывания блока диска состоит из позиционирования считывающей головки над дорожкой, содержащей требуемый блок, ожидания, пока требуемый блок сделает оборот и окажется под головкой и собственно считывания блока. Для этого требуется значительное время (десятки миллисекунд). В современных компьютерах обращение к диску примерно в 100000 медленнее, чем обращение к памяти. Таким образом, критерием вычислительной сложности алгоритмов, работающих с внешней памятью, является количество обращений к диску.
В данной главе рассмотрены вопросы структуры, именования, защиты файлов, операции, разрешенные над файлами, организация файлового архива. Проблемы выделения дискового пространства, обеспечения производительной работы файловой системы и ряд других, интересующие дизайнеров системы, вынесены в следующую главу.
Имена файлов
Файлы - абстрактные объекты. Они предоставляют пользователям возможность сохранять информацию, скрывая от него детали того, как и где она хранится и то, как диски в действительности работают. Вероятно, одна из наиболее важных характеристик любого абстрактного механизма - способ именования объектов, которыми он управляет. Когда процесс создает файл, он дает файлу имя. После завершения процесса файл продолжает существовать и через свое имя может быть доступен другим процессам.
Многие ОС поддерживают имена из двух частей (имя+расширение), например progr.c(файл, содержащий текст программы на языке Си) или autoexec.bat (файл, содержащий команды интерпретатора командного языка). Тип расширения файла позволяет ОС организовать работу с ним различных прикладных программ в соответствии с заранее оговоренными соглашениями.
Обычно ОС накладывают некоторые ограничения, как на используемые в имени символы, так и на длину имени. Например, в ОС Unix учитывается регистр при вводе имени файла (case sensitive), а в MS-DOS - нет. В популярной файловой системе FAT длина имен ограничивается известной схемой 8.3 (8 символов - собственно имя, 3 символа - расширение имени). Современные файловые системы, как правило, поддерживают более удобные для пользователя длинные символьные имена файлов. Так, в соответствии со стандартом POSIX, в ОС UNIX допускаются имена длиной до 255 символов, та же самая длина устанавливается для имен файлов и в ОС Windows NT для файловой системы NTFS.
Структура файлов
Как уже говорилось, программист воспринимает файл в виде набора логических записей. Логическая запись - это наименьший элемент данных, которым может оперировать программа при обмене с внешним устройством. Даже если физический обмен с устройством осуществляется большими единицами (обычно блоками), операционная система обеспечивает программисту доступ к отдельной логической записи.
ОС поддерживают несколько вариантов структуризации файлов.
Первый из них, файл, как неструктурированная последовательность байтов. Например, в файловых системах ОС UNIX и MS-DOS файл имеет простейшую логическую структуру - последовательность однобайтовых записей.
ОС не осуществляет никакой интерпретации этих байтов. Тем не менее, ОС с файловыми системами данного типа должны поддерживать, по крайней мере, одну структуру - выполняемый файл - для запуска программ. Этой схеме присущи максимальная гибкость и универсальность. Используя базовые системные вызовы (или функции библиотеки ввода/вывода), пользователи могут, как угодно структурировать файлы. В частности, многие СУБД хранят свои базы данных в обычных файлах.
Первый шаг в структурировании - хранение файла в виде последовательности записей фиксированной длины, каждая из которых имеет внутреннюю структуру. Центральная идея этой схемы - операция чтения проводится над записью и операция записи - переписывает или добавляет запись целиком. Ранее были записи по 80 байт (соответствовало числу позиций в перфокарте) или по 132 символа (ширина принтера). В ОС CP/M файлы были последовательностями 128-символьных записей. С введением CRT терминалов эта идея утратила популярность.
Третий способ представления файлов - последовательность записей переменной длины, каждая из которых содержит ключевое поле в фиксированной позиции внутри записи. Базисная операция в данном случае - считать запись с каким-либо значением ключа. Записи могут располагаться в файле последовательно (например, будучи отсортированы по значению ключевого поля) или в более сложном порядке.
Рис. 3.2.1. Файл, как последовательность записей переменной длины
Использование индексов файлов, хранящих адреса записей, позволяет обеспечить быстрый доступ к отдельной записи (индексно-последовательная организация, см. также раздел 11.5). При добавлении новой записи в файл, место, куда ее поместить будет определено не пользователем, а операционной системой. Такой способ применяется в больших мэйнфреймах для коммерческих процессов обработки данных.