Назовите способы доступа к массивам информации охарактеризуйте их кратко

Обновлено: 05.07.2024

В предыдущем уроке мы ввели понятие структурированных данных.

Изучение данных структурированного типа начнем с регулярного типа данных — массивов.

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

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

Когда возникает необходимость использовать массивы?

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

Мы будем вынуждены ввести 30 имен переменных, что, естественно, очень неудобно. Как быть?

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

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

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

Элемент массива — отдельная переменная, входящая в массив.

Размерность массива — количество индексов, по которым определяется положение элемента в массиве.

Индексы элемента массива — совокупность номеров, определяющих его местоположение в массиве.

Чтобы лучше понять, что такое размерность массива, сравним их с таблицами.

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

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

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

Переходим к изучению массивов.

Описание массива

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

При описании массива используется зарезервированное слово array (массив), указываются диапазон изменения для индексов и тип компонентов массива.

Способ 1. Описание массива с определением типа.

Способ 2. Описание массива без определения типа.

Двумерный массив описывается так же, как и одномерный. Различие состоит в том, что вы должны указать диапазон для двух индексов массива — положение каждого элемента массива A[i, j] определяется номером строки и номером столбца.

Например, описание двумерного массива натуральных чисел размера N x М может быть задано следующей строкой:

Вернемся к нашей задаче. У нас 30 целых чисел, выделим для них 30 ячеек, объединим их общим именем А.

№	A	Имя А — это общее имя для всех элементов. Элементы массива — это числа, их 30
1	25
2	64
3	27
…	…
29	53
30	89

Опишем одномерный массив из 30 целых чисел для этой задачи следующим образом:

myarray — это имя нового типа;

[1..30] — в квадратных скобках указывается номер первого элемента, затем, после двух точек, номер последнего элемента массива, в этом примере первый элемент имеет номер 1, а последний — номер 30;

Integer — тип всех элементов массива.

Так как каждый элемент имеет свой номер, то к каждому элементу можно обращаться непосредственно. Для того чтобы получить доступ к i-му элементу этого массива, необходимо записать: A[i] — сначала имя массива, а в квадратных скобках указывается номер элемента, к которому обращаемся, — i.

Например, обращаемся к первому элементу массива А — А[1], а к пятому — А[5].

Тот же самый массив может быть задан и при определении соответствующей переменной:

Особенность языка Паскаль

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

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

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

Массив – это набор объектов одинакового типа, доступ к которым осуществляется по индексу в массиве. Массивы можно описывать следующим образом:

тип_данных имя_массива [размер массива];

Компилятор отводит под массив память размером (sizeof(тип)*размер_массива) байтов. Нумерация элементов любого массива всегда начинается с 0, т. е. индекс изменяется от 0 до N-1, где N – количество значений индекса.

Используя имя массива и индекс, можно адресоваться к элементам массива:

имя_массива [значение_индекса].

Примеры описания массивов:

float income [30];

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

Для доступа к элементам массива существует два различных способа. Первый способ связан с использованием обычных индексных выражений в квадратных скобках, например, array[16]=3 или array[i+2]=7. При таком способе доступа записываются два выражения, причем второе выражение заключается в квадратные скобки. Одно из этих выражений должно быть указателем, а второе - выражением целого типа. Последовательность записи этих выражений может быть любой, но в квадратных скобках записывается выражение следующее вторым. Поэтому записи array[16] и 16[array] будут эквивалентными и обозначают элемент массива с номером шестнадцать. Указатель используемый в индексном выражении не обязательно должен быть константой, указывающей на какой-либо массив, это может быть и переменная. В частности после выполнения присваивания ptr=array доступ к шестнадцатому элементу массива можно получить с помощью указателя ptr в форме ptr[16] или 16[ptr].

Второй способ доступа к элементам массива связан с использованием адресных выражений и операции разадресации в форме *(array+16)=3 или *(array+i+2)=7. При таком способе доступа адресное выражение равное адресу шестнадцатого элемента массива тоже может быть записано разными способами *(array+16) или *(16+array).

Указатель – это адрес памяти. Значение указателя сообщает о том, где размещен объект, но не говорит о самом объекте. Как и всякие переменные, указатели нужно определять и описывать. Символ операции ‘*’ используется для задания “указателя на” объект. Кроме разделителя ‘*’, в определения и описания указателя входят спецификации типов, задающих типы объектов, на которые ссылаются указатели.

Например: int *ptr;

Данное определение следует понимать как “ptr является указателем на целое”. Указатель на тип void совместим с любым указателем. Например, если задано

то допустимо следующее присваивание y=x;

В общем случае переменная типа указатель описывается так:

тип *переменная_указатель

Двумя наиболее важными операциями, связанными с указателями, является операция обращения по адресу * (иногда называется операцией снятия ссылки или разыменования) и операция определения адреса &.

Операция обращения по адресу * служит для присваивания или считывания значения переменной, размещенной по адресу переменная_указатель, при помощи лево-определенного выражения *переменная_указатель. Например,

что обозначает следующее: значение переменной value помещается в участок памяти, адрес которого определяет указатель ptr.

Массивы структур и указатели на структуры. Доступ к компонентам структур.

Определяются массивы структур так же, как и массивы других типов данных. Единственное отличие – служебное слово struct в названии структурного типа (если обозначение структурного типа не введено с помощью typedef), например:

struct film a[100];

Указатели на структуры

Указатели на структуры определяются, как и указатели на другие типы данных: struct film *ptr;

Указатели могут вводиться и для безымянных структурных типов:

/*поля структуры*/

>*ptr1, ptr2;

Если название структурного типа введено с помощью typedef, то при определении указателей название этого типа может использоваться без предшествующего служебного слова struct.

В языке СИ между указателями и массивами существует тесная связь. Например, когда объявляется массив в виде int array[25], то этим определяется не только выделение памяти для двадцати пяти элементов массива, но и для указателя с именем array, значение которого равно адресу первого по счету (нулевого) элемента массива, т.е. сам массив остается безымянным, а доступ к элементам массива осуществляется через указатель с именем array. С точки зрения синтаксиса языка указатель arrey является константой, значение которой можно использовать в выражениях, но изменить это значение нельзя.

Поскольку имя массива является указателем допустимо, например, такое присваивание:

Здесь указатель ptr устанавливается на адрес первого элемента масcива, причем присваивание ptr=arrey можно записать в эквивалентной форме ptr=&arrey[0].

При реализации на компьютере первый способ приводится ко второму, т.е. индексное выражение преобразуется к адресному. Для приведенных примеров array[16] и 16[array] преобразуются в *(array+16).

Для доступа к начальному элементу массива (т.е. к элементу с нулевым индексом) можно использовать просто значение указателя array или ptr. Любое из присваиваний

присваивает начальному элементу массива значение 2, но быстрее всего выполнятся присваивания *array=2 и *ptr=2, так как в них не требуется выполнять операции сложения.

1.7.2. Указатели на многомерные массивы

Указатели на многомерные массивы в языке СИ - это массивы массивов, т.е. такие массивы, элементами которых являются массивы. При объявлении таких массивов в памяти компьютера создается несколько различных объектов. Например при выполнении объявления двумерного массива int arr2[4][3] в памяти выделяется участок для хранения значения переменной arr, которая является указателем на массив из четырех указателей. Для этого массива из четырех указателей тоже выделяется память. Каждый из этих четырех указателей содержит адрес массива из трех элементов типа int, и, следовательно, в памяти компьютера выделяется четыре участка для хранения четырех массивов чисел типа int, каждый из которых состоит из трех элементов. Такое выделение памяти показано на схеме на рис.3.

в
а
а
а
а
Рис.3. Распределение памяти для двумерного массива.

Таким образом, объявление arr2[4][3] порождает в программе три разных объекта: указатель с идентификатором arr, безымянный массив из четырех указателей и безымянный массив из двенадцати чисел типа int. Для доступа к безымянным массивам используются адресные выражения с указателем arr. Доступ к элементам массива указателей осуществляется с указанием одного индексного выражения в форме arr2[2] или *(arr2+2). Для доступа к элементам двумерного массива чисел типа int должны быть использованы два индексных выражения в форме arr2[1][2] или эквивалентных ей *(*(arr2+1)+2) и (*(arr2+1))[2]. Следует учитывать, что с точки зрения синтаксиса языка СИ указатель arr и указатели arr[0], arr[1], arr[2], arr[3] являются константами и их значения нельзя изменять во время выполнения программы.

Размещение трехмерного массива происходит аналогично и объявление float arr3[3][4][5] порождает в программе кроме самого трехмерного массива из шестидесяти чисел типа float массив из четырех указателей на тип float, массив из трех указателей на массив указателей на float, и указатель на массив массивов указателей на float.

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

Например, обращение к элементу arr2[1][2] можно осуществить с помощью указателя ptr2, объявленного в форме int *ptr2=arr2[0] как обращение ptr2[1*4+2] (здесь 1 и 2 это индексы используемого элемента, а 4 это число элементов в строке) или как ptr2[6]. Заметим, что внешне похожее обращение arr2[6] выполнить невозможно так как указателя с индексом 6 не существует.

Для обращения к элементу arr3[2][3][4] из трехмерного массива тоже можнo использовать указатель, описанный как float *ptr3=arr3[0][0] с одним индексным выражением в форме ptr3[3*2+4*3+4] или ptr3[22].

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

1.7.3. Операции с указателями

Над указателями можно выполнять унарные операции: инкремент и декремент. При выполнении операций ++ и -- значение указателя увеличивается или уменьшается на длину типа, на который ссылается используемый указатель.

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

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

Значения двух указателей на одинаковые типы можно сравнивать в операциях ==, !=, , >= при этом значения указателей рассматриваются просто как целые числа, а результат сравнения равен 0 (ложь) или 1 (истина).

В данном примере значение ptr1 меньше значения ptr2 и поэтому оператор a[3]=4 не будет выполнен.

1.7.4. Массивы указателей

В языке СИ элементы массивов могут иметь любой тип, и, в частности, могут быть указателями на любой тип. Рассмотрим несколько примеров с использованием указателей.

Следующие объявления переменных

порождают программные объекты, представленные на схеме на рис.4.

При выполнении операции pp-p получим нулевое значение, так как ссылки pp и p равны и указывают на начальный элемент массива указателей, связанного с указателем p ( на элемент p[0]).

После выполнения операции pp+=2 схема изменится и примет вид, изображенный на рис.5.

Результатом выполнения вычитания pp-p будет 2, так как значение pp есть адрес третьего элемента массива p. Ссылка *pp-a тоже дает значение 2, так как обращение *pp есть адрес третьего элемента массива a, а обращение a есть адрес начального элемента массива a. При обращении с помощью ссылки **pp получим 12 - это значение третьего элемента массива a. Ссылка *pp++ даст значение четвертого элемента массива p т.е. адрес четвертого элемента массива a.

Если считать, что pp=p, то обращение *++pp это значение первого элемента массива a (т.е. значение 11), операция ++*pp изменит содержимое указателя p[0], таким образом, что он станет равным значению адреса элемента a[1].

Сложные обращения раскрываются изнутри. Например обращение *(++(*pp)) можно разбить на следующие действия: *pp дает значение начального элемента массива p[0], далее это значение инкременируется ++(*p) в результате чего указатель p[0] станет равен значению адреса элемента a[1], и последнее действие это выборка значения по полученному адресу, т.е. значение 11.

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

порождают в программе объекты представленные на схеме на рис.6.

Рис.6. Схема размещения указателей на двумерный массив.

Согласно этой схеме доступ к элементу a[0][0] получить по указателям a, p, pa при помощи следующих ссылок: a[0][0], *a, **a[0], *p, **pa, *p[0].

Рассмотрим теперь пример с использованием строк символов. Объявления переменных

можно изобразить схемой представленной на рис.7.

Рис.7. Схема размещения указателей на строки.

1.7.5. Динамическое размещение массивов

При динамическом распределении памяти для массивов следует описать соответствующий указатель и присваивать ему значение при помощи функции calloc. Одномерный массив a[10] из элементов типа float можно создать следующим образом

Для создания двумерного массива вначале нужно распределить память для массива указателей на одномерные массивы, а затем распределять память для одномерных массивов. Пусть, например, требуется создать массив a[n][m], это можно сделать при помощи следующего фрагмента программы:

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

Эффективность хранения;
Эффективность доступа.

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

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

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

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

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

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

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

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

Готовые работы на аналогичную тему

Индексно-последовательный метод доступа

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

Индексно-последовательный метод требует, чтобы файл данных был упорядочен по первичному ключу. Записи делятся на блоки. Далее создается индексный файл, который содержит ссылки на блоки записей. Обычно в него заносится либо наибольшее, либо наименьшее значение в блоке. Индексный файл также упорядочен, поэтому и для него можно создать другой индексный файл.

При добавлении новой записи выполняется один из двух алгоритмов:

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

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

Индексно-произвольный метод доступа

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

Эффективность доступа при этом методе очень высока, так как индекс содержит ссылки на сами записи, а не на блоки. Но индексные файлы по этой же причине имеют очень большой объем.

Инвертированный метод доступа

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

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

Прямой метод доступа

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

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

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

Доступ через хеширование

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

Записи, отображаемые в один адрес называются синонимами.

Алгоритм отображения ключа в физический адрес называется хешированием.

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

Модуль 8. Управление данными

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

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

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

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

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

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

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

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

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

Индексно-последовательный.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Инициализация тома (форматирование).
Выделение и освобождение памяти файлу.
Уплотнение внешней памяти (дефрагментация).
Копирование, восстановление томов для обеспечения целостности.

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

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

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

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

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

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