Фундаментальные алгоритмы и структуры данных в Delphi

Бакнелл Джулиан М.

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

для многопоточной обработки.

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

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

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

Разрабатываемый нами комплексный объект нуждается, по меньшей мере, в четырех методах. Поток считывания вызывает первый метод, чтобы начать считывание (обратите внимание, что внутри этой подпрограммы может происходить блокировка, обеспечивающая ожидание окончания работы потока записи). Иногда этот метод называют подпрограммой регистрации считывания (reader registration routine). Как только поток считывания завершает свою работу, он должен вызвать другую подпрограмму для прекращения использования объекта синхронизации и, возможно, предоставления свободы действий потоку записи (подпрограмма отмены регистрации считывания). Аналогично такие же две подпрограммы должны существовать и для потока записи. Назовем эти четыре подпрограммы, соответственно, StartReading, StopReadlng, StartWriting и StopWriting.

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

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

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

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

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

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

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