Очередь. Логическое описание и физическое представление (файл): долговременное хранение и его цена

Модуль "Очередь и дек" • урок 2 из 7 • ~6 минут

Зачем очереди файл

Все реализации из прошлой темы жили в оперативной памяти. Но у ОЗУ два ограничения: объем и энергозависимость. Файловая очередь решает обе проблемы:

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

Очередь. Логическое описание и физическое представление (файл): отображение на файловый тип

Очередь отображается на файловый тип: file of T в Паскале, FILE* в C. Вспомните урок о файле: классический файл Паскаля открывается либо только на чтение (reset), либо только на запись с очисткой (rewrite). Из-за этого обе операции очереди становятся дорогими:

• Enqueue: скопировать весь файл во временный, дописать новый элемент в конец, скопировать обратно.
• Dequeue: скопировать файл во временный начиная со второго элемента (пропустив голову), затем заменить исходный.

В C есть послабление: режим "ab" (append binary) дописывает в конец без копирования, поэтому Enqueue дешевеет до одной операции записи. А вот удалить первый элемент файла по-прежнему нельзя иначе, чем переписав весь хвост.

Внешняя память и ее цена

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

Реализация на C

#include <stdio.h>

/* Enqueue: в C файл можно открыть на дозапись -
   копировать его целиком не нужно */
void PushFileQueue(const char* filename, int t) {
    FILE* q = fopen(filename, "ab"); /* append binary */
    if (q) {
        fwrite(&t, sizeof(int), 1, q);
        fclose(q);
    }
}

/* Dequeue: удалить голову можно только переписав хвост */
void PopFileQueue(const char* filename) {
    FILE* q = fopen(filename, "rb");
    FILE* temp = fopen("temp.bin", "wb");
    int item;

    if (q && temp) {
        fread(&item, sizeof(int), 1, q); /* пропускаем первый элемент */
        while (fread(&item, sizeof(int), 1, q) == 1) {
            fwrite(&item, sizeof(int), 1, temp); /* копируем остаток */
        }
        fclose(q);
        fclose(temp);
        remove(filename);
        rename("temp.bin", filename);
    }
}