 |
|
Выталкивание редко используемой страницы. NFU (Not Frequently Used) алгоритм.
Другое название этого алгоритма - LFU (The Least Frequently Used).
Программная реализация алгоритма, близкого к LRU.
Рассмотренные варианты LRU в принципе реализуемы, но, как уже отмечалось, они требуют специальной аппаратной поддержки, которой большинство современных процессоров не предоставляет. Поэтому хотелось бы иметь алгоритм, достаточно близкий к LRU, но не требующий сложной специальной поддержки.
Один из таких возможных алгоритмов - это алгоритм NFU.
Для него требуются программные счетчики, по одному на каждую страницу, которые сначала равны нулю. При каждом прерывании по времени (а не после каждой инструкции) операционная система сканирует все страницы в памяти и у каждой страницы с установленным флагом обращения увеличивает на единицу значение счетчика, а флаг обращения сбрасывает.
Таким образом, кандидатом на освобождение оказывается страница с наименьшим значением счетчика, как страница, к которой реже всего обращались. Главным недостатком алгоритма NFU является то, что он никогда ничего не забывает. Например, страница, к которой очень много обращались некоторое время, а потом обращаться перестали, все равно не будет удалена из памяти, потому что ее счетчик содержит большую величину. Например, в многопроходных компиляторах страницы, которые активно использовались во время 1-го прохода, могут надолго сохранить большие значения счетчика, мешая загрузке полезных в дальнейшем страниц.
К счастью, возможна небольшая модификация алгоритма, которая реализует "забывание". Достаточно, чтобы при каждом прерывании по времени содержимое каждого счетчика сдвигалось вправо на 1 бит, а уже затем производилось бы его увеличение для страниц с установленным флагом обращения (рис. 3-27 Таненбаум).
Другим, уже не так просто устранимым недостатком алгоритма является длительность процесса сканирования таблиц страниц.
Другие алгоритмы
Для полноты картины можно упомянуть еще несколько алгоритмов.
Например, алгоритм Second-Chance - модификации FIFO, которая позволяет избежать потери часто используемых страниц - анализ бита r (reference) для самой старой страницы. Если бит 1, то страница в отличие от FIFO не выталкивается, а очищается бит и страница становится в конец очереди. Если на все страницы ссылались, он превращается в FIFO. Данный алгоритм использовался в BSD Unix.
В компьютере Макинтош использован алгоритм NRU(Not Recently-Used), где страница жертва выбирается на основе анализа битов модификации и ссылки.
Имеется также и много других алгоритмов замещения. Объем этого курса не позволяет рассмотреть их подробно. Подробное описание различных алгоритмов замещения имеется в монографиях Дейтела, Цикритиса, Таненбаума и др.
13. Файлы с точки зрения пользователя.
История систем управления данными во внешней памяти начинается еще с магнитных лент, но современный облик они приобрели с появлением магнитных дисков. До этого каждая прикладная программа сама решала проблемы именования данных и структуризации данных во внешней памяти. Это затрудняло поддержание на внешнем носителе нескольких архивов долговременно хранимой информации. Историческим шагом явился переход к использованию централизованных систем управления файлами. Система управления файлами берет на себя распределение внешней памяти, отображение имен файлов в адреса внешней памяти и обеспечение доступа к данным.
Файловая система - это часть операционной системы, назначение которой состоит в том, чтобы организовать эффективную работу с данными, хранящимися во внешней памяти и обеспечить пользователю удобный интерфейс при работе с этими данными. Организовать хранение информации на магнитном диске непросто. Это требует хорошего знания устройства контроллера диска, особенностей работы с его регистрами и.т. д. (этим обычно занимается компонент системы ввода-вывода ОС, называемый драйвером диска). Для того чтобы избавить пользователя компьютера от сложностей взаимодействия с аппаратурой и была придумана ясная абстрактная модель файловой системы. Операции записи или чтения файла концептуально проще, чем низкоуровневые операции работы с устройствами.
Основная идея использования внешней памяти состоит в следующем. ОС делит ее на блоки фиксированного размера, например, 4096 байт. С точки зрения пользователя каждый файл состоит из набора индивидуальных элементов, называемых записями (например, характеристика какого-нибудь объекта). Каждый файл хранится в виде определенной последовательности блоков (не обязательно смежных); каждый блок хранит целое число записей. В некоторых ОС (MS-DOS) адреса блоков, содержащих данные файла, могут быть организованы в связный список и вынесены в отдельную таблицу в памяти. В других ОС (Unix), адреса блоков данных файла хранятся в отдельном блоке внешней памяти (так называемом индексе или индексном узле). Этот прием называется индексацией и является наиболее распространенным для приложений, требующих произвольного доступа к записям файлов. Индекс файла состоит из списка элементов, каждый из которых содержит номер блока в файле и указание о местоположении данного блока. В современных ОС файлы обычно представляют собой неструктурированную последовательность байтов (длина записи равна 1) и считывание очередного байта осуществляется с так называемой текущей позиции, которая характеризуется смещением от начала файла. Зная размер блока, легко вычислить номер блока, содержащего текущую позицию. Адрес же нужного блока диска можно затем извлечь из индекса файла. Базовой операцией, выполняемой по отношению к файлу, является чтение блока с диска и перенос его в буфер, находящийся в основной памяти.
Файловая система позволяет при помощи системы справочников (каталогов, директорий) связать уникальное имя файла с блоками вторичной памяти, содержащими данные файла. Иерархическая структура каталогов, используемая для управления файлами, является другим примером индексной структуры. В этом случае каталоги или папки играют роль индексов, каждый из которых содержит ссылки на свои подкаталоги. С этой точки зрения вся файловая система компьютера представляет собой большой индексированный файл.
Понятие «файловая система» включает [30]:
§ совокупность всех файлов на диске,
§ наборы структур данных, используемых для управления файлами, такие, например, как каталоги файлов, дескрипторы файлов, таблицы распределения свободного и занятого пространства на диске,
§ комплекс системных программных средств, реализующих управление файлами, в частности: создание, уничтожение, чтение, запись, именование, поиск и другие операции над файлами.
Файлы управляются ОС. То, как они структурированы, поименованы, используются, защищены, реализованы – одна из главных тем проектирования ОС.
Перечислим основные функции файловой системы:
1. Идентификация файлов. Связывание имени файла с выделенным ему пространством внешней памяти.
2. Распределение внешней памяти между файлами. Для работы с конкретным файлом не требуется иметь информацию о местоположении этого файла на внешнем носителе информации. Например, для того, чтобы загрузить документ в редактор с жесткого диска нам не требуется знать на какой стороне какого магнитного диска и на каком цилиндре и в каком секторе находится требуемый документ.
3. Обеспечение надежности и отказоустойчивости. Стоимость информации может во много раз превышать стоимость компьютера.
4. Обеспечение защиты от НСД.
5. Обеспечение совместного доступа к файлам, не требуя от пользователя специальных усилий по обеспечению синхронизации доступа.
6. Обеспечение высокой производительности.
Иногда говорят, что файл - поименованный набор связанной информации, записанной во вторичную память. Для большинства пользователей файловая система - наиболее видимая часть ОС. Она предоставляет механизм для он-лайнового хранения и доступа, как данным, так и программам ОС для всех пользователям системы. С точки зрения пользователя файл - минимальная величина внешней памяти, то есть данные, записанные на диск должны быть в составе какого-нибудь файла.
Важный аспект организации файловой системы – учет стоимости операций взаимодействия с вторичной памятью. Процесс считывания блока диска состоит из позиционирования считывающей головки над дорожкой, содержащей требуемый блок, ожидания, пока требуемый блок сделает оборот и окажется под головкой и собственно считывания блока. Для этого требуется значительное время (десятки миллисекунд). В современных компьютерах обращение к диску примерно в 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 терминалов эта идея утратила популярность.
Третий способ представления файлов - последовательность записей переменной длины, каждая из которых содержит ключевое поле в фиксированной позиции внутри записи. Базисная операция в данном случае - считать запись с каким-либо значением ключа. Записи могут располагаться в файле последовательно (например, будучи отсортированы по значению ключевого поля) или в более сложном порядке.
Рис. 11.. Файл, как последовательность записей переменной длины
Использование индексов файлов, хранящих адреса записей, позволяет обеспечить быстрый доступ к отдельной записи (индексно-последовательная организация, см. также раздел 11.5). При добавлении новой записи в файл, место, куда ее поместить будет определено не пользователем, а операционной системой. Такой способ применяется в больших мэйнфреймах для коммерческих процессов обработки данных.