Способ прямой организации данных

Тема 15. Способы доступа и организации файлов. Распределение файлов на диске

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

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

Существует три способа доступа к данным, расположенным во внешней памяти:

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

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

Прямой — непосредственно по ключу или физическому адресу записи.

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

Записи располагаются в физическом порядке и обеспечивают доступ в физической последовательности. Таким образом, для обработки записи с номером N+1 необходимо последовательно обратиться к записям с номером 1, 2,….,N. Это универсальный способ организации файла периферийного устройства. Используется так же для организации входного/выходного потока.

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

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

Это организация, при которой осуществляется прямой доступ по порядковому номеру записи или по физическому адресу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 1. Коэффициент блокирования 7

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

1.Трековый, в котором весь диск подразделяется на треки (дорожки) фиксированной длины, на которых размещаются блоки переменного размера. Адресом блока является тройка:

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

2.Секторный, в котором диск разбивается на блоки фиксированного размера, обычно кратного 256 байтам. Адресом блока является его порядковый номер на носителе.

Работа с дисковой памятью включает в себя 4 основные процедуры:

Инициализация тома (форматирование).

Выделение и освобождение памяти файлу.

Уплотнение внешней памяти (дефрагментация).

Копирование, восстановление томов для обеспечения целостности.

форматирования диска на дорожки (сектора);

определения сбойных участков диска;

присвоения метки тому;

создания оглавления тома;

записи ОС, если это необходимо.

Выделение и освобождение места для файлов на томе аналогично стратегии размещения ОП.

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

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

Популярным способом, используемым, например, в файловой системе FAT операционной системы MS-DOS, является использование связанного списка индексов. С каждым блоком (кластером) связывается некоторый элемент — индекс. Индексы располагаются в отдельной области диска (в MS-DOS это таблица FAT). Если некоторый блок распределен файлу, то индекс этого блока содержит номер следующего блока данного файла. При этом для каждого файла в каталоге имеется поле, в котором отмечается номер начального индекса для кластера, входящего в файл. Последний индекс содержит специальный маркер конца файла. Такая физическая организация сохраняет все достоинства предыдущего способа и снимает отмеченный недостаток: для доступа к произвольному месту файла достаточно прочитать только блок индексов, отсчитать нужное количество блоков файла по цепочке и определить номер нужного блока.

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

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

Источник

6.3. Организация данных на устройствах с прямым и последовательным доступом

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

Рис. 6.1. Окно утилиты «Проводник»

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

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

По этому признаку ЗУ делятся на устройства с прямым, последовательным и ассоциативным доступом.

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

Последовательный доступ (sequential access) означает последовательный просмотр (чтение) существующих данных на ЗУ, чтобы осуществить операцию чтения этих данных или запись новых.

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

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

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

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

Регистровые ЗУ входят в состав микропроцессора или других устройств компьютера и предназначены для кратковременного хранения небольшого объема данных. Они участвуют в вычислительных процессах и процессах обмена данными в устройствах ввода-вывода компьютера.

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

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

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

В качестве внешних ЗУ в современном компьютере могут использоваться накопители информации:

• на гибких магнитных дисках (НГМД);

• на жестких магнитных дисках (НЖМД);

• на основе флэш-памяти (Flash-memory);

• на оптических дисках (CD – Compact Disk и DVD – Digital Versatile Disk);

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

Для сравнительной оценки приведенных выше способов доступа и самих ЗУ, реализующих эти способы, перечислим основные характеристики ЗУ, определяющие информационные и временные свойства таких устройств:

• информационный объем памяти (информационная емкость);

• время считывания и время записи информации или скорость считывания и записи информации.

Информационный объем памяти определяет максимально возможный объем хранимой информации и выражается в соответствующих единицах измерения – битах, байтах, килобайтах, мегабайтах и т. д. Например, информационный объем памяти накопителя на жестком магнитном диске равен 40 Гбайт, информационный объем памяти накопителя на гибком магнитном диске равен 1,44 Мбайт и т. д. Информационный объем памяти для различных типов ЗУ может быть различным, т. е. зависит от конкретного типа ЗУ и может варьироваться в достаточно широких пределах от единиц байт до сотен и тысяч гигабайт.

Время доступа (access time) определяется как усредненный интервал от выдачи запроса на передачу блока данных до фактического начала передачи и также различно для различных типов ЗУ (от долей микросекунд до сотен миллисекунд).

Скорость считывания и записи информации является скоростью передачи информации (transfer rate) и определяется как производительность обмена данными, измеряемая после выполнения поиска данных. Для различных ЗУ эта характеристика различна. В качестве единицы измерения скорости считывания и записи информации принята единица бит в секунду (бит/с, Кбит/с, Мбит/с и т. д.), однако часто используется в качестве единицы измерения скорости считывания и записи и байт в секунду (байт/с, Кбайт/с, Гбайт/с и т. д.). Скорость считывания и записи информации для различных ЗУ может варьироваться в пределах от десятков килобайт в секунду до гигабайт в секунду.

Существуют также и другие характеристики ЗУ – стоимость одного бита информации, потребляемая мощность и т. д.

Таким образом, если проводить различие между ЗУ с разными способами доступа к данным, то основное различие будет определяться временем доступа: для ЗУ с прямым и ассоциативным доступом оно минимально, для ЗУ с последовательным доступом – максимально.

Данный текст является ознакомительным фрагментом.

Продолжение на ЛитРес

Способ прямой организации данных

Способ прямой организации данных

6.3. Организация данных на устройствах с прямым и последовательным доступом

Читайте также

Информация об устройствах в реестре

Глава 4 Управление доступом

Средства управления доступом

Управление доступом к rlogind

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

14.6.1 Команды управления доступом

Группы с ограниченным доступом

11.1.8. Управление доступом к методам

Управление доступом

Игры на мобильных устройствах

СОФТЕРРА: Организация информации: Как не утонуть в море данных?

Глава 6 Компьютерная организация данных и их обработка

Логическая организация данных

Основные сведения об устройствах и драйверах