Введение
Данные, связанные с потоком или процессом. Активная структура данных — это структура данных, с которой связан поток или процесс, выполняющий внутренние операции. Более конкретно, активная структура данных связана с вычислительным ресурсом, содержащим один или несколько одновременно выполняющихся процессов и данные, связанные с этими процессами. Взаимодействие моделируется с использованием удалённых вызовов процедур, в отличие от разделяемой памяти или передачи сообщений. Внутреннее устройство активной структуры данных скрыто за её RPC-интерфейсом и может быть доступно одновременно. Типичные примеры включают базы данных и файловые системы. Активные структуры данных могут выполнять обслуживание в периоды простоя ресурсов и предоставлять множественные представления данных.
An active data structure is a data structure with an associated thread or process that performs internal operations. More specifically, an active data structure is associated with a computing resource, which contains one or more concurrently executing processes, and data associated with those processes. Communication is modeled using remote procedure calls, as opposed to shared memory or message passing. The active data structure's internals are hidden behind its RPC interface, and may be accessed concurrently. Common examples include databases and file systems. Active data structures can perform maintenance when resources would otherwise be idle, and present multiple views of the data.
Пример
Очередь, предоставляемая аппаратным обеспечением или операционной системой, как правило, не является безграничной, а имеет конечную емкость. Предположим, что приложение предъявляет жесткое требование к недопустимости потери элементов очереди. Тогда процесс записи должен быть модифицирован для сохранения элементов на носитель большой емкости, если очередь заполнена, а процесс чтения должен считывать эти элементы обратно. Используя концепцию активных структур данных, можно вместо этого рассмотреть "активную очередь", которая управляет сохранением и извлечением элементов из хранилища большой емкости. Хотя теперь вместо двух запущенных процессов три, что потенциально усложняет синхронизацию, высокоуровневая абстракция чтения-записи для использования активной очереди остается простой и понятной.
Формализация
Самокорректирующиеся вычисления — это техника создания инкрементальных вычислительных программ, которые поддерживают внутреннее состояние и могут адаптироваться к новым входным данным более эффективно, чем повторное вычисление с нуля. Это позволяет предположить, что активные структуры данных могут быть формализованы путем введения понятия времени в типичную алгебраическую характеристику структур данных. В частности, Канат Танвунгсан предлагает, что активная структура данных является алгеброй с тремя метаоперациями:
perform("operationi(·)", t) выполняет операцию operationi в момент времени t. Если operationi(·) возвращает значение ri, то метаоперация возвращает значение ri. Метаоперация undo(t) отменяет операцию, выполненную в момент времени t. Это используется для моделирования инкрементальных вычислений. Метаоперация update(t) сообщает структуре данных о необходимости "синхронизироваться" до момента времени t. Это позволяет учитывать информацию о других процессах.