Гармонически взаимодействующие последовательные потоки
В разд. "Формулировка задачи" мы видели, что проблемы взаимоисключения и синхронизации возникают тогда и только тогда, когда несколько нитей разделяют один и тот же ресурс. Взаимоисключение доступа к разделяемым данным приводит к необходимости вводить дополнительные сущности (семафоры и другие примитивы взаимоисключения и синхронизации) и усложнять программу.
Необоснованное расширение участков исключительного доступа приводит к росту времени реакции системы и снижению производительности, а стремление сократить их может привести к ошибкам соревнования. Поэтому разделяемые структуры данных являются предметом ненависти теоретиков и источником серьезных ошибок при разработке программ.
Желание устранить эти проблемы привело в свое время Э. Дейкстру к концепции, известной как гармонически взаимодействующие последовательные потоки. Эта концепция состоит в следующем.
- Каждый поток (нить) представляет собой независимый программный модуль, для которого создается иллюзия чисто последовательного исполнения.
- Нити не имеют разделяемых данных.
- Все обмены данными и вообще взаимодействие происходят с использованием специальных примитивов, которые одновременно выполняют и передачу данных, и синхронизацию.
- Синхронизация, не сопровождающаяся передачей данных, просто лит6" на смысла – нити, не имеющие разделяемых структур данных, совершенно независимы и не имеют ни критических точек, ни нереентерабельных модулей.
Третье требование является ключевым. Поток, модифицирующий (в данном случае генерирующий) данные, исполняет примитив передачи данных тогда и только тогда, когда порожденные им данные уже целостны, или передает их такими блоками, каждый из которых целостен сам по себе.
Примечание
Важно подчеркнуть, что гармоническое взаимодействие не исключает критических секций из алгоритма. Оно лишь сосредотачивает критические секции и связанные с ними примитивы взаимоисключения внутри примитивов передачи данных.
Гармоническое взаимодействие, строго говоря, не исключает проблему мертвой блокировки: замкнув гармонически взаимодействующие нити в кольцо (А получает информацию от В, В от С, С от А), мы можем получить классическую трехзвенную мертвую блокировку. Впрочем, в данном случае блокировка требует наличия циклической зависимости данных, которая свидетельствует о серьезных ошибках проектирования программы (и, возможно, о внутренней противоречивости требований к этой программе). Такая ошибка может быть относительно легко обнаружена посредством формального анализа спецификаций и потоков данных.
На практике, впрочем, гармоническое взаимодействие обходит основную массу проблем, возникающих при взаимоисключении доступа ко многим ресурсам – и блокировки, и "проблему голодного философа". Дело в том, что гармонически взаимодействующий поток имеет дело не с разделяемым ресурсом непосредственно, а с копией состояния этого ресурса. Если нам нужны два ресурса, мы (не обязательно одновременно) снимаем с них две копии – для этого нам не надо одновременно захватывать сами ресурсы.
В частности, поэтому групповые операции над примитивами гармонического взаимодействия (оператор select в Ada, системный вызов select в системах семейства Unix, команда ALT в транспьютере) работают не по принципу транзакции, а возвращают управление и данные при условии, что хотя бы один из примитивов группы готов эти данные предоставить. Воспроизвести "проблему голодного философа" в этих условиях невозможно.
В современных системах реализован целый ряд средств, которые осуществляют передачу данных совместно с синхронизацией: почтовые ящики (mailboxes) в системах линии RSX-11 – VMS, трубы (pipes) (в русскоязычной литературе их часто называют программными каналами) в UNIX, рандеву (rendesvous – свидание) в языке Ada, линки (link – соединение) в микропроцессорах семейства Transputer и т. д. Большинство этих средств будет обсуждаться подробнее в разд. "Примеры реализаций средств гармонического взаимодействия".
Примитивы синхронного обмена данными отличаются большим разнообразием. Основные принципы классификации таковы.
- Примитивы могут быть двухточечные (допускающие только один прием, ник и один передатчик), либо многоточечные, допускающие несколько приемников и передатчиков. Многоточечность бывает как симметричная когда может быть несколько и приемников, и передатчиков, так и асимметричная: один передатчик и много приемников – широковещательная (broadcast) или групповая (multicast) передача – либо один приемник и много передатчиков.
- Примитив может передавать неструктурированный поток байтов, либо структурированные данные, разбитые на сообщения определенного размера. В первом случае передатчик может порождать данные блоками одного размера, а приемник – считывать их блоками другого размера Во втором случае приемник всегда обязан прочитать сообщение целиком (возможно, отбросив какую-то его часть). Сообщения могут быть как фиксированного, так и переменного размера.
- Примитив может быть синхронным, буферизованным или с негарантированной доставкой. В первом случае передатчик вынужден ждать, пока приемник не прочитает все переданные данные. Во втором, данные складываются в буфер и могут быть прочитаны приемником позднее. В третьем случае, если потенциальный приемник не был готов принять сообщение, оно просто игнорируется.
Синхронные примитивы могут использоваться не "только для гармонического взаимодействия, но и для реализации примитивов чистой синхронизации. В частности, в учебниках по языку Ada (например, [Василеску 1990]) и по программированию для транспьютеров (например, [Харп 1993]) почему-то любят приводить примеры реализации семафоров на основе, соответственно, рандеву и линков.
Буферизованные примитивы для синхронизации использованы быть не могут. Зато буферизация полезна, если нам надо согласовать скорости работы нитей, имеющих разные приоритеты – например, если нить реального времени должна быстро обработать событие и передать часть данных для отложенной обработки менее приоритетной нитью, не допустив при этом собственной блокировки.