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

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

1. Каждый поток (нить) представляет собой независимый программный модуль, для которого создается иллюзия чисто последовательного исполнения.
2. Нити не имеют разделяемых данных.
3. Все обмены данными и вообще взаимодействие происходят с использованием специальных примитивов, которые одновременно выполняют и передачу данных, и синхронизацию.
4. Синхронизация, не сопровождающаяся передачей данных, просто лит6" на смысла — нити, не имеющие разделяемых структур данных, совершенно независимы и не имеют ни критических точек, ни нереентерабельных модулей.

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

Примечание
Примечание

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

Гармоническое взаимодействие, строго говоря, не исключает проблему мертвой блокировки: замкнув гармонически взаимодействующие нити в кольцо (А получает информацию от В, В от С, С от А), мы можем получить классическую трехзвенную мертвую блокировку. Впрочем, в данном случае блокировка требует наличия циклической зависимости данных, которая свидетельствует о серьезных ошибках проектирования программы (и, возможно, о внутренней противоречивости требований к этой программе). Такая ошибка может быть относительно легко обнаружена посредством формального анализа спецификаций и потоков данных.
На практике, впрочем, гармоническое взаимодействие обходит основную массу проблем, возникающих при взаимоисключении доступа ко многим ресурсам — и блокировки, и "проблему голодного философа". Дело в том, что гармонически взаимодействующий поток имеет дело не с разделяемым ресурсом непосредственно, а с копией состояния этого ресурса. Если нам нужны два ресурса, мы (не обязательно одновременно) снимаем с них две копии — для этого нам не надо одновременно захватывать сами ресурсы.

В частности, поэтому групповые операции над примитивами гармонического взаимодействия (оператор select в Ada, системный вызов select в системах семейства Unix, команда alt в транспьютере) работают не по принципу транзакции, а возвращают управление и данные при условии, что хотя бы один из примитивов группы готов эти данные предоставить. Воспроизвести "проблему голодного философа" в этих условиях невозможно.
В современных системах реализован целый ряд средств, которые осуществляют передачу данных совместно с синхронизацией: почтовые ящики (mailboxes) в системах линии RSX-11 — VMS, трубы (pipes) (в русскоязычной литературе их часто называют программными каналами) в UNIX, рандеву (rendesvous — свидание) в языке Ada, линки (link — соединение) в микропроцессорах семейства Transputer и т. д. Большинство этих средств будет обсуждаться подробнее в разд. Примеры реализаций средств гармонического взаимодействия.
Примитивы синхронного обмена данными отличаются большим разнообразием. Основные принципы классификации таковы.

1. Примитивы могут быть двухточечные (допускающие только один прием, ник и один передатчик), либо многоточечные, допускающие несколько приемников и передатчиков. Многоточечность бывает как симметричная когда может быть несколько и приемников, и передатчиков, так и асимметричная: один передатчик и много приемников — широковещательная (broadcast) или групповая (multicast) передача — либо один приемник и много передатчиков.
2. Примитив может передавать неструктурированный поток байтов, либо структурированные данные, разбитые на сообщения определенного размера. В первом случае передатчик может порождать данные блоками одного размера, а приемник — считывать их блоками другого размера Во втором случае приемник всегда обязан прочитать сообщение целиком (возможно, отбросив какую-то его часть). Сообщения могут быть как фиксированного, так и переменного размера.
3. Примитив может быть синхронным, буферизованным или с негарантированной доставкой. В первом случае передатчик вынужден ждать, пока приемник не прочитает все переданные данные. Во втором, данные складываются в буфер и могут быть прочитаны приемником позднее. В третьем случае, если потенциальный приемник не был готов принять сообщение, оно просто игнорируется.

Синхронные примитивы могут использоваться не "только для гармонического взаимодействия, но и для реализации примитивов чистой синхронизации. В частности, в учебниках по языку Ada (например, [Василеску 1990]) и по программированию для транспьютеров (например, [Харп 1993]) почему-то любят приводить примеры реализации семафоров на основе, соответственно, рандеву и линков.
Буферизованные примитивы для синхронизации использованы быть не могут. Зато буферизация полезна, если нам надо согласовать скорости работы нитей, имеющих разные приоритеты — например, если нить реального времени должна быстро обработать событие и передать часть данных для отложенной обработки менее приоритетной нитью, не допустив при этом собственной блокировки.
Буферизованный примитив может быть легко реализован на основе пары синхронных примитивов и нити-монитора буфера (или очереди). В этом смысле, синхронные примитивы являются более низкоуровневыми, чем буферизованные.
Синхронные примитивы по природе своей всегда двухточечные. Да и в случае буферизованных примитивов многоточечное взаимодействие не всегда легко реализуемо, а иногда просто опасно, особенно в случае потоковой передачи данных: операция считывания данных из потока необратима, а естественного разбиения потока на сообщения нет, поэтому если один из приемников по ошибке захватит кусок сообщения, предназначенного не ему, то данные в потоке будут необратимо испорчены.
Впрочем, некоторые потоковые примитивы, например трубы (pipes) в системах семейства Unix, допускают (хотя документация и рекомендует пользо-яться этим с осторожностью) наличие нескольких передатчиков при одном приемнике.
Напротив, симметрично многоточечные очереди сообщений широко распространены. Часто такие примитивы позволяют потребителю отбирать сообщения из очереди по какому-то критерию, например по значению специального поля, называемому типом или тегом. Ряд широковещательных и групповых сервисов передачи данных относится к категории примитивов с негарантированной доставкой.
Второй и третий критерии нашей классификации (если пока отвлечься от сервисов с негарантированной доставкой) практически ортогональны друг другу: существуют все четыре варианта (табл. 7.1). Легко понять, что передавать поток неструктурированных данных в режиме негарантированной доставки бессмысленно: разрывы потока неизбежны, а мы не сможем даже узнать, произошел ли такой разрыв, и если произошел, то где. Все существующие сервисы с негарантированной доставкой передают только сообщения.

Содержание раздела