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

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

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

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

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

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

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

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

Таблица 7.1. Примитивы синхронизованной передачи данных

На первый взгляд, вообще непонятно, почему кому-то может быть полезен сервис с негарантированной доставкой. Но под это описание подходят многие низкоуровневые сетевые протоколы (Ethernet, IP) и некоторые относительно высокоуровневые сетевые сервисы, так называемые дейтаграммные протоколы. Примером такого сервиса является UDP (User Datagram Protocol), входящий в семейство протоколов TCP/IP.
В сетевых протоколах отсутствие гарантии доставки сообщения имеет двоякий смысл — сообщение может быть потеряно не только по невниманию получателя, но и из-за физических ошибок передачи или перегрузки маршрутизаторов и/или каналов связи по дороге от передатчика к приемнику. В этом смысле можно сказать, что разработчики сетевых протоколов вынуждены использовать негарантированную доставку не потому, что им нужна Именно она, а потому, что других средств-то и нет.
В чистом виде негарантированная доставка приемлема для реализации одиночных запросов, на которые должен последовать одиночный же ответ. Если ответа за определенный протоколом интервал времени нет, передатчик повторяет запрос, а после некоторого количества попыток приходит к выводу, что приемник не функционирует, либо вообще отсутствует.
Для реализации надежной связи на основе сервисов с негарантированной доставкой используются различного рода подтверждения, так называемое квитирование. Понятно, что при реализации квитирования необходимо принимать во внимание возможность потери не только самого подтверждаемого сообщения, но и пакета-подтверждения. Понятно также, что в большинстве случаев посылка подтверждения на каждое пришедшее сообщение нецелесообразна. Поэтому реальные протоколы такого рода относительно сложны (см. например [RFC 0793]) и их обсуждение заслуживает отдельной книги. Накладные расходы при реализации таких протоколов значительны, поэтому часто оказывается целесообразно смириться с негарантированной доставкой.
Концепция гармонически взаимодействующих процессов очень привлекательна с теоретической точки зрения и позволяет легко писать правильные программы. Однако все примитивы синхронизованной передачи данных плохи именно тем, что требуют передачи, копирования данных. И передатчик, и приемник вынуждены иметь по буферу, в котором данные следует хранить (в случае буферизованных примитивов данные хранятся трижды). Накладные расходы при копировании данных большого объема также могут оказаться значительными.
Если нити исполняются на разных компьютерах, не имеющих общей памяти и соединенных лишь относительно (по сравнению с системной шиной) низкоскоростными сетевыми каналами, мы так или иначе не можем обойтись без передачи и двойного хранения данных. Впрочем, даже и в этом случае иногда имеет смысл подумать о применении многопортовой памяти или реализаций NUMA или СОМА-архитектуры.
При исполнении же нитей на одной машине, по соображениям производительности и экономии памяти нередко оказывается нецелесообразно отказываться от разделяемой памяти и полностью переходить на примитивы гармонического взаимодействия. Чаще всего это происходит, когда к ресурсу выполняется много обращений для чтения, а модификации относительно редки, и при этом данные имеют большой объем. Даже в этом случае бывает целесообразно заменить прямое разделение памяти на мониторный процесс. а при доступе к данным получать у него лишь непосредственно необходимое их подмножество. Однако ситуации бывают разные, и не всегда такое решение оказывается оптимальным.
В этом смысле разделяемая память напоминает другой предмет ненависти структурных программистов — оператор goto. И то, и другое при неразумном использовании является потенциальным источником ошибок и проблем, но иногда без них оказывается нельзя обойтись.