Последовательный доступ

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

Основные характеристики

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

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

Устройства с последовательным доступом

Магнитная лента

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

Другие примеры

• Перфолента — носитель информации, использовавшийся в ранних вычислительных машинах и телетайпах. Данные считывались последовательно по мере протягивания ленты через считывающий механизм.
• Бубонный накопитель — устройство, в котором данные хранились на вращающемся барабане, но доступ к ним был организован последовательно через фиксированные головки чтения/записи.
• Очереди (FIFO) — структуры данных, реализующие принцип «первым пришёл — первым ушёл», где доступ к элементам возможен только в порядке их добавления.

Структуры данных с последовательным доступом

Связный список

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

Файлы последовательного доступа

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

Применение

Резервное копирование и архивирование

Основная область применения последовательного доступа — системы резервного копирования. Магнитные ленты позволяют хранить огромные объёмы данных (до десятков терабайт на одну кассету) с минимальными затратами. Восстановление данных с ленты происходит последовательно, что приемлемо для сценариев аварийного восстановления, где скорость доступа не является критичной.

Потоковая передача данных

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

Журналирование и аудит

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

Сравнение с произвольным доступом

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

Преимущества:

• Низкая стоимость хранения: Устройства последовательного доступа (ленты) значительно дешевле в пересчёте на гигабайт по сравнению с жёсткими дисками или твердотельными накопителями.
• Высокая надёжность: Магнитные ленты менее подвержены механическим повреждениям и имеют длительный срок хранения (до 30 лет).
• Энергоэффективность: Ленточные накопители не требуют постоянного электропитания для хранения данных.

Недостатки:

• Низкая скорость произвольного доступа: Время доступа к случайному элементу может составлять минуты.
• Сложность модификации: Для изменения данных в середине последовательности часто требуется перезапись всего носителя.
• Ограниченная параллельность: Одновременный доступ к разным участкам данных затруднён.

Историческое значение

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

Интересные факты

• В 1950-х годах компания IBM выпустила первый коммерческий накопитель на магнитной ленте IBM 726, который мог хранить до 1,4 мегабайта данных на одной катушке.
• Современные технологии LTO (Linear Tape-Open) позволяют достигать скорости передачи данных до 400 МБ/с при последовательном чтении, что сравнимо с показателями жёстких дисков.
• В некоторых суперкомпьютерах для хранения промежуточных результатов вычислений используются ленточные библиотеки, способные вмещать до 100 петабайт данных.

Источники

1. Таненбаум Э., Бос Х. «Современные операционные системы». — 4-е изд. — СПб.: Питер, 2015. — 1120 с.
2. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ». — 3-е изд. — М.: Вильямс, 2013. — 1328 с.
3. Хеннесси Дж., Паттерсон Д. «Архитектура компьютера и проектирование компьютерных систем». — 4-е изд. — СПб.: Питер, 2012. — 784 с.
4. Документация по стандарту LTO Ultrium. — Linear Tape-Open Consortium, 2021.
5. ГОСТ 33707-2016 «Информационная технология. Системы хранения данных. Термины и определения».