Поэтому исследования направлены на архитектуры, которые имеют несколько узлов памяти, подсоединенных к процессорам через интерсеть. Такая интерсеть может быть построена, например, из траспьютеров.
(3) Балансировка загрузки. Вычислительная мощь параллельного компьютера эксплуатируется только, если рабочая нагрузка вычислений распределена равномерно по процессорам; концентрация работы на одном узле понижает производительность до производительности одного узла. Если все шаги вычислений могут быть определены во время компиляции, то возможно распределить их статически. Более трудный случай возникает, когда блоки работы создаются динамически во время вычисления; в этом случае требуются сложные методы. Очереди задач процессоров должны регулярно сравниваться, после чего задачи должны мигрировать от одной к другой. Для обзора некоторых методов и алгоритмов для балансировки загрузки см. Гочинский [Gos91, глава 9] или Харгет и Джонсон [HJ90].
(4) Робастость против необнаруживаемых сбоев (часть 3). В репликационной системе должен быть механизм для преодоления сбоев в одном или нескольких процессорах. Конечно, компьютерные сети должны также продолжать их функционирование, несмотря на сбои узла, но обычно предполагается, что такой сбой может быть обнаружен другими узлами (см., например, алгоритм сетевого обмена в разделе 4.3). Предположения, при которых репликационные системы должны оставаться правильными, более строгие, т.к. процессор может производить ошибочный ответ, и то же время кооперироваться с другими при помощи протоколов как правильно работающий процессор. Должен быть внедрен механизм голосования, чтобы отфильтровывать результаты процессоров, так, что только правильные ответы передаются во все время, пока большинство процессоров работает правильно.
1.1.6 Взаимодействующие процессы
Разработка сложных программных систем может быть зачастую упрощена организацией программы как набора (последовательных) процессов, каждый с хорошо определенной, простой задачей.
Классический пример для иллюстрации этого упрощения это преобразование записей Конвея. Проблема состоит в том, чтобы читать 80 символьные записи и записывать ту же информацию в 125 символьные записи. После каждой входной записи должен вставляться дополнительный пробел, и каждая пара звездочек («**») должна заменяться на восклицательный знак («!»). Каждая выходная запись должна завершаться символов конца записи (EOR). Преобразование может быть проведено одной программой, но написание этой программы очень сложно. Все функции, т.е. замена «**» на «!», вставка пробелов, и вставка символов EOR, должны осуществляться за один цикл.
Программу лучше структурировать как два взаимодействующих процесса. Первый процесс, скажем р1, читает входные карты и конвертирует входной поток в поток печатных символов, не разбивая на записи. Второй процесс, скажем р2, получает поток символов и вставляет EOR после 125 символов. Структура программы как набор двух процессов обычно предполагается для операционных систем, телефонных переключающих центров, и, как мы увидим в подразделе 1.2.1, для коммуникационных программ в компьютерных сетях.
Набор кооперирующих процессов становится причиной того, что приложение становится локально распределенным, но абсолютно возможно выполнять процессы на одном компьютере, в этом случае приложение не является физически распределенным. Конечно, в этом случае достигнуть физической распределенности легче именно для систем, которые логически распределены. Операционная система компьютерной системы должна управлять конкурентным выполнением процессов и обеспечить средства коммуникации и синхронизации между процессами.
Процессы, которые выполняются на одном компьютере, имеют доступ к одной физической памяти, отсюда – естественно использование этой памяти для коммуникации. Один процесс пишет в определенное место памяти, и другой процесс читает из этого места. Эта модель конкурирующих процессов была использована Дейкстрой [Dij68] и Овицким и Грайсом [OG76]. Проблемы, которые рассматривались в этом контексте, включают следующие.
(1) Атомичность операций с памятью. Часто предполагается, что чтение и запись одного слова памяти атомичны, т.е. чтение и запись выполняемые процессом завершается перед тем как другая операция чтения или записи начнется. Если структуры большие, больше чем одно слово обновляется, операции должны быть аккуратно синхронизированы, чтобы избежать чтения частично обновленной структуры. Это может быть осуществлено, например, применением взаимного исключения [Dij68] в структуре: пока один процесс имеет доступ к структуре, ни один другой процесс не может начать чтение или запись. Применение взаимного исключения с использованием разделяемых переменных усложнено из-за возможности нескольких процессов искать поле в этой структуре в это же время.
Условия ожидания, налагаемые доступом со взаимным исключением к разделяемым данным, могут понизить производительность процессов, например, если «быстрый» процесс должен ждать данные, в настоящее время используемые «медленным» процессом. В недавние годы внимание концентрировалось на применении разделяемых переменных, которые являются wait-free, что значит, что процесс может читать или писать данные без ожидания любых других процессов. Чтение и запись могут перекрываться, но только при тщательной проработке алгоритмов чтения и записи, которые должны обеспечить атомичность. Для обзора алгоритмов для wait-free атомичных разделяемых переменных см. Киросис и Кранакис [KK89].
(2) Проблема производитель-потребитель. Два процесса, один из которых пишет в разделяемый буфер и другой и которых читает из буфера, должны быть скоординированы, чтобы предупредить первый процесс от записи, когда буфер полон и второй процесс от чтения, когда буфер пуст. Проблема производитель-потребитель возникает, когда решение проблемы преобразования Конвея выработано; р1 производит промежуточный поток символов, и р2 потребляет его.
(3) Сборка мусора. Приложение, которое запрограммировано с использованием динамических структур данных может производить недоступные ячейки памяти, называемые мусором. Формально, приложение должно бы прерваться, когда у системы памяти кончается свободное место, для того чтобы позволить специальной программе, называемой сборщиком мусора, идентифицировать и вернуть недоступную память. Дейкстра и другие [DLM78] предложили сборщик мусора на-лету, который может работать как отдельный процесс, параллельно с приложением.
Требуется сложное взаимодействие между приложением и сборщиком, т.к. приложение может модифицировать структуры указателей в памяти, в то время как сборщик решает какие ячейки являются недоступными. Алгоритм должен быть тщательно проанализирован, чтобы показать, что модификации не обусловят ошибочный возврат доступным ячеек. Алгоритм для сбора мусора на-лету с упрощенным доказательством правильности был предложен Бен-Ари [BA84].
Решения проблем, перечисленных здесь, демонстрируют, что могут быть решены очень трудные проблемы взаимодействия процессов для процессов, которые сообщаются посредством разделяемой памяти. Однако, решения часто исключительно усложнены и иногда очень незначительное перемешивание шагов различных процессов дает ошибочные результаты для решений, которые кажутся правильными на первый и даже на второй взгляд. Поэтому, операционные системы и языки программирования предлагают примитивы для более структурной организации межпроцессовых коммуникаций.
(1) Семафоры. Семафор [Dij68] это неотрицательная переменная, чье значение может быть прочитано и записано за одну атомичную операцию. V операция приращает ее значение, а Р операция уменьшает ее значение, когда оно положительно ( и подвешивает выполнение процесса на этой операции, пока значение переменной нулевое).
Семафоры – подходящее средство для применения взаимного исключения над разделяемой структурой данных: семафор инициализируется в 1, и доступ к структуре предваряется операцией Р и завершается операцией V. Семафоры накладывают большую ответственность на каждый процесс за правильное использование; целостность разделяемых данных нарушается, если процесс манипулирует данными неправильно или не выполняет требуемых Р и V операций.
(2) Мониторы. Монитор [Hoa74] состоит из структуры данных и набора процедур, которые могут выполняться над этими данными, с помощью их вызова процессами способом, использующим взаимное исключение. Т.к. к данным доступ осуществляется полностью через процедуры, объявленные в мониторе, гарантируется правильное использование данных, если монитор объявлен корректно. Монитор, таким образом, предотвращает не позволенный доступ к данным и синхронизирует доступ различных процессов.
(3) Каналы. Канал [Bou83] это механизм, который передает поток данных от одного процесса к другому и синхронизирует два коммутирующих процесса; это заранее запрограммированное решение проблемы производитель-потребитель.
Канал это основной механизм коммуникаций в операционной системе UNIX. Если программа р1 выполняет процесс р1 преобразования Конвея и р2 выполняет р2 , команда UNIX р1 | р2 вызывает две программы и соединяет их каналом. Вывод р1 буферизируется и становится вводом р2 ; р1 подвешивается, когда буфер полон, и р2 подвешивается, когда буфер пуст.
(4) Передача сообщений. Некоторые языки программирования, такие как OCCAM и ADA, обеспечивают передачу сообщений, как механизм для межпроцессовой коммуникации. Проблемы синхронизации относительно легко решаются с использованием передачи сообщений; т.к. сообщение не может быть получено до его передачи, возникает временное отношение между событиями благодаря обмену сообщениями.