Проектирование и Разработка Простейшей Электронной Таблицы с Использованием Механизма Проецирования Файла в Память

Введение

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

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

Цель настоящей работы состоит в теоретическом обосновании и архитектурном проектировании простейшего приложения электронной таблицы, в котором для управления данными и обеспечения их персистентности используется высокопроизводительный механизм Проецирования файла в память (Memory-Mapped Files, MMF). Мы продемонстрируем, как этот системный механизм позволяет интегрировать файловое хранение данных непосредственно в модель данных приложения, повышая эффективность операций ввода-вывода и упрощая логику работы с данными.

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

Архитектурные Основы Электронной Таблицы

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

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

1. Модель Данных (Data Model): Подсистема, отвечающая за структурированное хранение содержимого ячеек (числа, текст, формулы) и метаданных (форматирование, состояние).
2. Дисплейный Интерфейс (Display Interface): Отвечает за отрисовку матрицы ячеек, обработку пользовательского ввода и отображение результатов вычислений.
3. Механизм Пересчета (Recalculation Engine): Центральный логический элемент, который анализирует формулы, отслеживает зависимости между ячейками и выполняет вычисления в корректном порядке.

Функциональное Назначение и Структура Ячеек

Ячейка, расположенная на пересечении строки $R$ и столбца $C$, является минимальным элементом хранения и обработки данных в ЭТ. Каждая ячейка имеет уникальный адрес (например, A1, B5) и может содержать один из трех основных типов контента:

• Числовые данные: Целые, десятичные или даты, которые могут быть использованы в расчетах.
• Текст: Строки, используемые для меток, заголовков или комментариев.
• Формулы: Последовательность инструкций, начинающаяся со знака равенства ("="), которая предписывает выполнение вычислений с использованием математических операторов, функций и ссылок на другие ячейки.

Механизм Пересчета: Парсер и Граф Зависимостей

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

1. Парсер Формул (Formula Parser): Получает текстовое представление формулы (например, =A1+B2*SUM(C3:C5)) и преобразует его в машиночитаемую структуру, чаще всего в Абстрактное Синтаксическое Дерево (AST). Парсер также отвечает за идентификацию всех ссылок на другие ячейки, которые необходимы для построения графа зависимостей.
2. Менеджер Графа Зависимостей (Dependency Graph Manager): На основе информации, полученной от парсера, этот менеджер строит ориентированный граф, где каждая ячейка, содержащая формулу, является вершиной, а ссылка одной ячейки на другую — ориентированным ребром. Этот граф позволяет определить строгий порядок вычислений, гарантируя, что значение ячейки будет вычислено только после того, как будут доступны значения всех ячеек, от которых она зависит.

Теоретические Принципы Проецирования Файла в Память (MMF)

Механизм проецирования файла в память (Memory-Mapped Files, MMF) представляет собой технику, которая радикально меняет подход к работе с персистентными данными, интегрируя дисковое хранилище непосредственно в подсистему виртуальной памяти операционной системы. Как именно этот метод помогает избежать замедления работы с большими файлами?

Принцип Работы и Роль Виртуальной Памяти

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

1. Создание Объекта Проекции: Приложение запрашивает у операционной системы создание объекта проекции для существующего файла на диске.
2. Отображение в Адресное Пространство: Ядро ОС отображает (проецирует) этот объект на непрерывный участок виртуального адресного пространства процесса.

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

Механизм Загрузки по Требованию (Demand Paging): Фактическое считывание данных с диска в физическую память происходит не сразу, а только тогда, когда процесс впервые обращается к виртуальному адресу, принадлежащему отображенной области. Это вызывает ошибку страницы (Page Fault). Ядро ОС перехватывает ошибку, загружает соответствующую страницу данных с диска, обновляет Таблицу Страниц и возвращает управление процессу. Таким образом, MMF обеспечивает ленивую загрузку, используя дисковый файл как источник подкачки для виртуальной памяти.

Преимущества MMF в Контексте Системного Программирования

Использование MMF для персистентности данных в ЭТ обеспечивает значительные технические преимущества:

Критерий	Традиционный File I/O	Memory-Mapped Files (MMF)
Копирование данных	Двойное: Диск → Буфер ядра → Буфер приложения.	Отсутствует: Диск → Страница физической памяти.
Накладные расходы	Высокие, требуются частые системные вызовы read()/write().	Низкие, после отображения доступ осуществляется инструкциями CPU.
Синхронизация	Явная, требует вызова fsync() или аналогичной функции.	Полуавтоматическая, ядро ОС периодически сбрасывает измененные страницы на диск.
Доступ к данным	Последовательный или явный случайный доступ через seek()/lseek().	Прямой случайный доступ через арифметику указателей.
Межпроцессное взаимодействие (IPC)	Требует явных механизмов передачи данных.	Естественный механизм IPC, так как несколько процессов могут отобразить один и тот же объект проекции.

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

Детализированный Дизайн Модели Данных для MMF

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

Структура Ячейки (CellStructure) и Адресация

Модель данных в проецируемой области должна начинаться с Заголовка (Header), содержащего метаинформацию (например, количество строк $R$ и столбцов $C$, смещения до служебных структур), за которым следует область данных.

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

Представим структуру ячейки $\text{CellStructure}$ следующим образом:

Поле	Размер (Байт)	Назначение
DataTypeFlag	1	Флаг типа контента (0-Пусто, 1-Число, 2-Текст, 3-Формула).
Value	8	64-разрядное число с плавающей запятой двойной точности (IEEE 754) для хранения числового значения ячейки.
TextOffset	4	Смещение или индекс в отдельной строковой куче (если текст/формула длинные).
StatusFlags	1	Служебные флаги (например, "Изменена", "Ошибка вычисления").
Итого	14	Общий размер структуры (примерный).

Формула Адресации:
Если $\text{BaseAddress}$ — это указатель на начало области хранения ячеек, то адрес ячейки с координатами $(R, C)$ (строка $R$, столбец $C$, где нумерация начинается с 0) вычисляется как:

CellAddress = BaseAddress + $(R \times \text{ColumnCount} + C) \times \text{sizeof}(\text{CellStructure})$

Этот подход позволяет получить прямой указатель на любую ячейку за $O(1)$ время, что является идеальным для MMF.

Битовая Матрица Занятости: Оптимизация Доступа

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

Эта матрица располагается в начале проецируемой области, сразу после заголовка, и представляет собой компактный битовый массив, где каждый бит соответствует одной ячейке. Если бит установлен (1), ячейка содержит данные или формулу; если бит сброшен (0), ячейка пуста.

Преимущества Битовой Матрицы:

• Скорость: Позволяет мгновенно определить состояние ячейки с минимальными операциями (арифметический сдвиг и побитовое И).
• Компактность: Требует минимального пространства.

Расчет размера Битовой Матрицы:

Для таблицы с $R$ строками и $C$ столбцами общее количество ячеек равно $R \times C$. Поскольку каждый байт содержит 8 бит, общий размер матрицы $\text{Size}_{\text{Bitmap}}$ в байтах составит:

Size_Bitmap = $\lceil (R \times C) / 8 \rceil$

Например, для таблицы размером $1000 \times 1000$ ячеек (1 миллион ячеек) потребуется всего $\lceil 1000000 / 8 \rceil = 125000$ байт (около 122 КБ) для матрицы занятости, что является ничтожно малым объемом по сравнению с общим объемом данных, но обеспечивает критически важную оптимизацию.

Реализация Системных Вызовов Управления Проекцией

Управление проекцией файла в память требует использования специфических системных вызовов, которые различаются в зависимости от операционной системы (Windows или POSIX-совместимые ОС).

Использование WinAPI (Windows)

В среде Microsoft Windows (WinAPI) процесс проецирования файла в память включает три основных шага: открытие файла, создание объекта проекции и отображение проекции.

1. Создание Объекта Проекции (CreateFileMapping):
   Эта функция создает именованный или безымянный объект, который может быть использован для отображения файла в память.

HANDLE hFile = CreateFile(
    TEXT("spreadsheet.dat"), 
    GENERIC_READ | GENERIC_WRITE, 
    0, 
    NULL, 
    OPEN_ALWAYS, 
    FILE_ATTRIBUTE_NORMAL, 
    NULL
);

HANDLE hMapping = CreateFileMapping(
    hFile, 
    NULL, 
    PAGE_READWRITE, 
    dwMaximumSizeHigh, // Старшие 32 бита размера
    dwMaximumSizeLow,  // Младшие 32 бита размера
    NULL               // Имя объекта проекции
);

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

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

LPVOID lpBaseAddress = MapViewOfFile(
    hMapping, 
    FILE_MAP_WRITE, // Права доступа к отображенной области
    0, 
    0, 
    0               // Размер (0 означает весь объект)
);

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

Использование POSIX (Linux/Unix)

В POSIX-совместимых операционных системах (Linux, macOS, Unix) для работы с MMF используется системный вызов mmap().

1. Открытие или Создание Файла/Объекта:
   Для обычных файлов используется стандартный open(). Для объектов разделяемой памяти, которые часто служат основой для MMF, используется shm_open():

int fd = shm_open("/spreadsheet_shm", O_CREAT | O_RDWR, 0666);
// Установка размера файла:
ftruncate(fd, total_size);

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

void *addr = mmap(
    NULL,              // Предпочтительный адрес (NULL - выбирает ОС)
    total_size,        // Длина отображаемой области
    PROT_READ | PROT_WRITE, // Желаемая защита памяти
    MAP_SHARED,        // Флаг: изменения видны всем и записываются в файл
    fd,                // Файловый дескриптор
    0                  // Смещение
);

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

Алгоритм Пересчета Формул на Основе Топологической Сортировки

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

Построение и Анализ Графа Зависимостей

Граф Зависимостей $G = (V, E)$ — это ключевая структура, где:

• $V$ — множество вершин, представляющих ячейки, содержащие формулы.
• $E$ — множество ориентированных ребер, где ребро $(A \to B)$ означает, что ячейка $A$ зависит от значения ячейки $B$.

На этапе парсинга формулы для ячейки $A$, парсер идентифицирует все ячейки, на которые она ссылается, и добавляет соответствующие ребра в граф.

Проблема Циклических Зависимостей:
Электронная таблица не может быть корректно вычислена, если в графе зависимостей присутствует цикл (например, A1 зависит от B1, а B1 зависит от A1). Граф с циклами не является Ориентированным Ациклическим Графом (DAG). Выявление циклов является неотъемлемой частью анализа графа и обычно выполняется в процессе топологической сортировки. При обнаружении цикла приложение должно выдать ошибку, поскольку корректный порядок вычислений отсутствует.

Топологическая Сортировка и Порядок Вычислений

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

Топологическая сортировка позволяет найти линейный порядок вершин, такой что для каждого ориентированного ребра $(u \to v)$, вершина $u$ появляется в этом порядке раньше вершины $v$. Таким образом, мы получаем список ячеек, который гарантирует, что при вычислении значения каждой ячейки, значения всех ее зависимостей уже будут доступны.

Алгоритм на Основе Поиска в Глубину (DFS):

Наиболее распространенным методом для топологической сортировки является модифицированный поиск в глубину (DFS):

1. Создается стек или список для хранения результата сортировки.
2. Запускается DFS для каждой не посещенной вершины.
3. Во время обхода DFS для вершины $v$:
   • Помечаем $v$ как "посещаемую" (обнаруженную). Если мы встречаем уже "посещаемую" вершину, это означает наличие цикла.
   • Рекурсивно вызываем DFS для всех соседей $u$ вершины $v$.
   • После завершения обработки всех соседей $v$, помечаем $v$ как "посещенную" (завершенную) и добавляем ее в начало результирующего списка (или помещаем в стек).

Сложность Алгоритма:
Сложность алгоритма топологической сортировки, основанного на DFS, составляет $O(V+E)$, где $V$ — количество вершин (ячеек с формулами) и $E$ — количество ребер (зависимостей). Поскольку каждое ребро и каждая вершина посещаются только один раз, этот алгоритм является крайне эффективным даже для очень больших таблиц.

Сравнительный Анализ Персистентности Данных

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

Анализ Применимости MMF

В контексте приложения ЭТ, которое может содержать десятки тысяч ячеек и требует частых, н��предсказуемых операций чтения/записи (например, при пересчете после изменения одной ячейки), MMF обеспечивает высокую эффективность:

1. Производительность: MMF проявляет свое максимальное преимущество при работе с большими объемами данных и случайным доступом, так как устраняет узкое место, связанное с двойным копированием, и минимизирует накладные расходы системных вызовов.
2. Простота Кода: Логика работы с данными упрощается, поскольку нет необходимости вручную управлять буферами и смещениями в файле; данные обрабатываются как обычные структуры в памяти.
3. Естественная Персистентность: Изменения в памяти автоматически отражаются на диске, хотя и не мгновенно.

Риски и Необходимость Явной Синхронизации

Несмотря на преимущества, MMF не является панацеей, и его использование требует внимания к вопросам надежности и целостности данных:

Критерий	MMF	Традиционный File I/O
Обработка ошибок I/O	Неявная. Ошибки (например, сбой диска) могут проявляться как исключения SIGSEGV (POSIX) или Structured Exception (Windows) при доступе к памяти.	Явная. Функции возвращают код ошибки (например, -1 и errno), позволяя приложению восстановиться.
Гарантия записи на диск	Изменения сбрасываются асинхронно ядром ОС.	Требует явного вызова fsync() для гарантии сброса.
Начальные накладные расходы	Значительные на создание объекта проекции и отображение.	Низкие.

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

BOOL FlushViewOfFile(LPCVOID lpBaseAddress, SIZE_T dwNumberOfBytesToFlush)

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

Заключение

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

Мы определили ключевые архитектурные компоненты ЭТ, акцентируя внимание на необходимости построения Графа Зависимостей и использования алгоритма Топологической Сортировки $O(V+E)$ для обеспечения корректного порядка вычисления формул.

Было доказано, что MMF, основанный на подсистеме виртуальной памяти и механизме Page Fault, радикально оптимизирует операции ввода/вывода, устраняя неэффективное двойное копирование данных, характерное для традиционного File I/O.

Ключевым инженерным решением стала разработка оптимизированной Модели Данных, предназначенной для прямого отображения в MMF. Предложенная структура с использованием непрерывного массива CellStructure и критически важной Битовой Матрицы Занятости (размером $\lceil (R \times C) / 8 \rceil$ байт) обеспечивает быстрый $O(1)$ доступ к любой ячейке и минимизирует накладные расходы при проверке состояния таблицы. Были детализированы системные вызовы WinAPI (CreateFileMapping, MapViewOfFile) и POSIX (mmap с MAP_SHARED), необходимые для практической реализации MMF. В итоге, разработанная архитектура представляет собой системно-эффективное решение, которое идеально подходит для работы с большими объемами табличных данных, обеспечивая необходимую персистентность при минимальных накладных расходах на I/O, что полностью соответствует целям работы.

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

1. Архангельский А.Я. Delphi 7 Справочное пособие. — М.: Бином-Пресс, 2004. — 1024 с.
2. Delphi Basics. URL: http://www.delphibasics.ru/ (дата обращения: 28.10.2025).
3. Richter J. Win32/64 API. URL: http://art.xitona.com/Books/Jeffrey-Richter-WIN32-64/head15.htm (дата обращения: 28.10.2025).
4. Лабораторная работа № 3 управление памятью // Studfile.net: [сайт]. URL: https://studfile.net/preview/10188602/page:7/ (дата обращения: 28.10.2025).
5. Функция CreateFileMappingNumaW (memoryapi.h) — Win32 apps // Microsoft Learn: [сайт]. URL: https://learn.microsoft.com/ru-ru/windows/win32/api/memoryapi/nf-memoryapi-createfilemappingnumaw (дата обращения: 28.10.2025).
6. shm_overview(7) — Arch manual pages // Archlinux.org: [сайт]. URL: https://man.archlinux.org/man/shm_overview.7 (дата обращения: 28.10.2025).
7. Совместно используемая память POSIX // Algolist.manual.ru: [сайт]. URL: http://algolist.manual.ru/os/unixtheory/ipc/shm.php (дата обращения: 28.10.2025).
8. shm_open() // Kpda.ru: [сайт]. URL: http://www.kpda.ru/programm/book/api/posix/shm_open.htm (дата обращения: 28.10.2025).
9. Файлы, отображаемые в память / Хабр. URL: https://habr.com/ru/articles/55027/ (дата обращения: 28.10.2025).
10. Преимущества использования Memory Mapped Files перед традиционными методами // Ya.ru: [сайт]. (дата обращения: 28.10.2025).
11. Почему MMAP не лучший выход / Хабр. URL: https://habr.com/ru/articles/738360/ (дата обращения: 28.10.2025).
12. Электронные таблицы(эт), назначение, структура и функциональные возможности // Studfile.net: [сайт]. URL: https://studfile.net/preview/10188602/page:6/ (дата обращения: 28.10.2025).
13. MAXimal :: algo :: Топологическая сортировка // E-maxx.ru: [сайт]. URL: http://e-maxx.ru/algo/topological_sort (дата обращения: 28.10.2025).
14. Топологическая сортировка / Хабр. URL: https://habr.com/ru/articles/498418/ (дата обращения: 28.10.2025).
15. Использование обхода в глубину для топологической сортировки // Викиконспекты ИТМО: [сайт]. URL: https://wiki.ifmo.ru/index.php/%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D1%82%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 (дата обращения: 28.10.2025).