Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 9
Текст из файла (страница 9)
1. Введение: распределенные системы125 символов. При этом после каждой входной строки нужно поставить пробели каждую пару звездочек («**») нужно заменить восклицательным знаком («!»).Каждая строка выходного текста должна завершаться признаком конца строки(EOR8)). Это преобразование может быть выполнено и одной программой, нонаписать такую программу весьма непросто. Ведь все функции, включая замену«**» на «!», вставку дополнительных пробелов и признаков конца строки, нужновыполнять в теле одного единственного цикла.Лучше всего представить такую программу в виде двух взаимодействующихпроцессов.
Первый из этих процессов (назовем его р\) прочитывает подаваемыена вход перфокарты и преобразует прочитанные данные в поток символов, который уже не будет разбит на строки. Второй процесс (назовем его р 2 ) получаетпоток символов и вставляет признак EOR после каждой серии из 125 символов.Удобное представление в виде систем взаимодействующих процессов допускаютоперационные системы, автоматические телефонные станции и, как будет показано в п. 1.2.1, коммуникационное программное обеспечение в вычислительныхсетях.Если в основу проекта положено представление программы в виде семействавзаимодействующих процессов, то полученная в результате программная система будет логически распределенной, хотя вполне возможно, что процессы приэтом будут выполняться на одном и том же вычислительном устройстве, и в этомслучае такая система не будет физически распределенной.
Конечно же, логически распределенную систему проще сделать физически распределенной. Операционная система вычислительного устройства должна управлять параллельнымвыполнением процессов и обеспечивать коммуникацию и синхронизацию процессов.Процессы, которые выполняются на одном процессоре, имеют доступ к одному и тому же запоминающему устройству, поэтому именно это устройство памятицелесообразно использовать для связи между процессорами. Один процесс проводит запись в определенную область памяти, а другой процесс считывает данныеиз этой области.
Такая модель параллельных процессов использовалась в работах Дейкстры [60], а также Овицкого и Гриса [155]. В рамках этой модели былизучен ряд следующих задач.1.Атомарность операций записи и чтения. Считается само собой разумеющимся, что при записи или считывании информации из одного машинногослова совершается атомарная операция, т.
е. считывание или запись, которуюсовершает один процесс, завершается до того, как другой процесс приступаетк считыванию или записи. В том случае, когда проводится обновление данныхв области памяти, состоящей из нескольких слов, нужно проводить тщательнуюсинхронизацию во избежание считывания из частично обновленных областей памяти. Этого можно добиться, воспользовавшись, например, механизмом взаимноисключенного доступа к областям памяти [60]: до тех пор пока один процессимеет доступ к какой-то области памяти, никакой другой процесс не может проводить считывание или запись в эту область.
Реализация взаимно исключенного8>End Of Record. — Прим, перев.1.1. Что такое распределенная система?29доступа на основе разделяемых переменных представляется довольно затруднительной из-за возможности того, что сразу несколько процессов могут одновременно претендовать на доступ к одной и той же области памяти.Проверка условий ожидания, которые возникают при использовании взаимно исключенного доступа к совместно используемым данным, может понизитьпроизводительность процессов; это происходит, например, в тех случаях, когда«быстрый» процесс вынужден ожидать разрешения на доступ к тем данным, к которым сейчас обращается «медленный» процесс. В последние годы все большеевнимание уделяется разработке разделяемых атомарных переменных, не требующих ожидания; эти переменные позволяют процессу проводить считывание и запись данных, не ожидая других процессов.
Считывание и запись теперь могутперекрываться, но при аккуратной реализации алгоритмов считывания и записиатомарность операций может быть тем не менее сохранена. Обзор алгоритмовдля разделяемых атомарных переменных, не требующих ожидания, можно найтив работах Кироузиса и Кранакиса [116], а также Аттьи и Велча [12].2. Задача «производитель—потребитель».
Два процесса, один из которых проводит запись в совместно используемый буфер, а другой проводит считывание из этого буфера, должны координировать свои действия, чтобы избежатьситуаций, когда первый процесс пытается записывать данные в переполненныйбуфер или когда второй процесс пытается считывать данные из пустого буфера. Задача «производитель—потребитель» возникает, например, в схеме Конвеяпреобразования строк: процесс р\ порождает поток символов, а процесс р 2 «потребляет» их.3.
Сборка «мусора». Прикладные программы, в которых используются динамические структуры данных, могут занимать ячейки памяти, доступ к которымвпоследствии утрачивается; такие области памяти называются мусором. Раньше выполнение прикладной программы должно было прерываться по исчерпаниисвободной памяти, чтобы позволить специальной программе, которая называетсясборщиком мусора, обнаружить и восстановить неиспользуемую память.
Дейкстра и др. в работе [64] придумали, как проводить сборку мусора оперативно(on-the-fly): сборщик мусора реализуется в виде отдельного процесса, которыйвыполняется параллельно с прикладной программой.Взаимодействие между прикладной программой и сборщиком мусора оказывается весьма замысловатым, потому что прикладная программа может изменятьв памяти структуру указателей, пока сборщик выясняет, какие из ячеек памятиоказываются недоступными. Нужно провести тщательный анализ алгоритма, чтобы убедиться в том, что исключены ситуации, когда доступные ячейки ошибочноутилизируются при модификации структуры.
Алгоритм оперативной сборки мусора, имеющий простое доказательство корректности, был предложен в работеБен-Ари [27].Решения всех тех задач, которые были перечислены выше, свидетельствуюто том, что даже очень трудные проблемы взаимодействия процессов могут бытьрешены для процессов, связь между которыми осуществляется при помощи совместно используемой памяти.
Однако решения эти часто оказываются чрезвычайно изощренными и порой даже небольшие изменения порядка выполнения30Гл. 1. Введение: распределенные системыдействий разными процессами приводят к тому, что решения, которые на первый(и даже на второй) взгляд казались правильными, приводят к ошибочным результатам. Поэтому в операционных системах и языках программирования заложенынекоторые простые базовые средства для более структурированной организациивзаимосвязи между процессами.1. Семафоры. Семафором (см. [60]) называется переменная, принимающая неотрицательные целые значения, запись и считывание значений которойосуществляется при помощи одной атомарной операции.
Операция V служит дляувеличения ее значения, а операция Р — для уменьшения ее значения в том случае, когда это значение оказывается положительным (если значение оказываетсяотрицательным, то эта операция приостанавливает выполнение процесса, до техпор пока это значение не станет положительным).Семафоры являются подходящим инструментальным средством для реализации взаимно исключенного доступа к совместно используемым структурам данных: начальное значение семафора полагается равным 1, перед тем как осуществить доступ к структуре данных, выполняется операция Р, а после завершения работы с данными выполняется операция V.
Семафоры возлагают на каждый процесс значительную ответственность за их правильное использование; целостность совместно используемых данных будет нарушена, если процесс будетнеправильно преобразовывать данные или будет некорректно выполнять операции Р и V.2.
Мониторы. Монитор (см. [107]) представляет собой структуру данныхи семейство процедур, выполняемых на этих данных путем взаимно исключающих вызовов. Доступ к данным осуществляется исключительно посредствомпроцедур, определенных в мониторе, и это гарантирует корректное использованиеданных в том случае, когда монитор описан корректно. Таким образом, мониторпредотвращает неограниченный доступ к данным и позволяет синхронизироватьдоступ разных процессов к этим данным.3.
Трубки. Трубкой (см. [34]) называется механизм перемещения потокаданных от одного процесса к другому и синхронизации двух взаимосвязанныхпроцессов; по сути дела трубка — это предварительно запрограммированное решение задачи «производитель—потребитель». Трубка — это основной механизмсвязи в операционной системе UNIX. Если программы p i и р2 представляют собой реализации процессов р\ и р 2 в схеме Конвея преобразования строк, то припомощи команды p i | р2 в системе UNIX осуществляется вызов этих программи установление связи между ними посредством трубки.
Выходные данные программы p i поступают в буфер и становятся входными данными для программыр2; программа p i приостанавливает свое выполнение, если буфер переполнен,а программа р2 приостанавливает свое выполнение, если буфер опустошен.4. Обмен сообщениями. В некоторых языках программирования (к их числу относятся языки программирования Occam или Ada) в качестве средств межпроцессного взаимодействия используются операторы обмена сообщениями. Припомощи обменов сообщениями сравнительно легко решаются проблемы синхронизации: поскольку сообщение нельзя получить прежде, чем оно было отправле1.2. Архитектура и языки31но, в результате проведенного обмена сообщениями между событиями возникаеттемпоральное отношение предшествования.Обмен сообщениями можно реализовать при помощи мониторов или трубок;это естественный способ организации связи в программных системах, которыевыполняются на распределенных вычислительных устройствах без совместногоиспользования памяти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
