Основы многопоточного и распределенного программирования

       

мых аппаратных контроллеров, позволявших центральному


Предисловие
Параллельное программирование возникло в 1962 г. с изобретением каналов — независи­ мых аппаратных контроллеров, позволявших центральному процессору выполнять новую прикладную программу одновременно с операциями ввода-вывода других (приос­тановленных) программ. Параллельное программирование (слово параллельное в данном слу­чае означает "происходящее одновременно"') первоначально было уделом разработчиков операционных систем. В конце 60-х годов были созданы многопроцессорные машины. В ре­зультате не только были поставлены новые задачи разработчикам операционных систем, но и появились новые возможности у прикладных программистов.
Первой важной задачей параллельного программирования стало решение проблемы так называемой критической секции. Эта и сопутствующие ей задачи ("обедающих философов", "читателей и писателей" и т.д.) привели к появлению в 60-е годы огромного числа научных работ. Для решения данной проблемы и упрощения работы программиста были разработаны такие элементы синхронизации, как семафоры и мониторы. К середине 70-х годов стало яс­но, что для преодоления сложности, присущей параллельным программам, необходимо ис­пользовать формальные методы.
На рубеже 70-х и 80-х годов появились компьютерные сети. Для глобальных сетей стан­дартом стал Arpanet, а для локальных— Ethernet. Сети привели к росту распределенного программирования, которое стало основной темой в 80-х и, особенно, в 90-х годах. Суть рас-пределенног9 программирования состоит во взаимодействии процессов путем передачи со­общений, а не записи и чтения разделяемых переменных.
Сейчас, на заре нового века, стала заметной необходимость обработки с массовым парал­лелизмом, при которой для решения одной задачи используются десятки, сотни и даже тыся­чи процессоров. Также видна потребность в технологии клиент-сервер, сети Internet и World Wide Web. Наконец, стали появляться многопроцессорные рабочие станции и ПК. Парал­лельное аппаратное обеспечение используется больше, чем когда-либо, а параллельное про­граммирование становится необходимым.


Это моя третья книга, в которой предпринята попытка охватить часть истории парал­лельного программирования. Первая книга — Concurrent Programming: Principles and Practice, опубликованная в 1991 г., — дает достаточно полное описание периода между 1960 и 1990 годами. Основное внимание в ней уделяется новым задачам, механизмам программирова­ния и формальным методам.
Вторая книга — The SR Programming Language: Concurrency in Practice, опубликованная в 1993 году, —-подводит итог моей работы с Роном Одеоном (Ron Olsson) в конце 80-х и нача­ле 90-х годов над специальным языком программирования, который может использоваться при написании параллельных программ для систем как с разделяемой, так и с распределен­ной памятью. Книга о языке SR является скорее практическим руководством, чем формаль­ным описанием языка, поскольку демонстрирует пути решения многих проблем с использо­ванием одного языка программирования.
Данная книга выросла из предыдущих и является отражением моих мыслей о том, что важно сейчас и в будущем. Многое почерпнуто из книги Concurrent Programming, но полно­стью переработан каждый раздел, взятый из нее, и переписаны все примеры программ на псевдоС вместо языка SR. Все разделы дополнены новым материалом; особенно это каса-
1 Слово "параллельный" в большинстве случаев является переводом английского "concurrent". При­менительно к программам, вычислениям и программированию его смысл, возможно, лучше передавался бы словом "многопроцессный", но этого термина в русскоязычной литературе нет. Перевод английского "parallel" связан с синхронным параллелизмом, и его смысл определяется в разделах 1.3 и 3.5 и уточняется в самом начале части 3. Отметим, что смысл слова "concurrent" шире, чем "parallel". — Прим. ред.
14                                                                                                                                    Предисловие
ется параллельного научного программирования.


Также добавлены учебные примеры по наиболее важным языкам программирования и библиотекам программ, содержащие завер­шенные учебные программы. И, наконец, я по-новому вижу использование этой книги — в аудиториях и личных библиотеках.
Новое видение и новая роль


Идеи параллельных и распределенных вычислений сегодня распространены повсеме­стно. Как обычно в вычислительной технике, прогресс исходит от разработчиков аппарат­ного обеспечения, которые создают все более быстрые, большие и мощные компьютеры и коммуникационные сети. Большей частью, они достигают успеха, и лучшее доказатель­ство тому — фондовая биржа!
Новые компьютеры и сети создают новые проблемы и возможности, а разработчики программного обеспечения по-прежнему не отстают. Вспомните Web-броузеры, Internet-коммерцию, потоки Pthread, язык Java, MPI, и вновь доказательством служит фондовая бир­жа! Эти программные продукты разрабатываются специально для того, чтобы использовать все преимущества параллельности в аппаратной и программной части. Короче говоря, боль­шая часть мира вычислительной техники сейчас параллельна!
Аспекты параллельных вычислений — многопоточных, параллельных или распределен­ных — теперь рассматриваются почти в каждом углубленном курсе по вычислительной тех­нике. Отражая историю, курсы по операционным системам охватывают такие темы, как многопоточность, протоколы взаимодействия и распределенные файловые системы. Курсы по архитектуре вычислительной техники — многопроцессорность и сети, по компиляторам — вопросы компиляции для параллельных машин, а теоретические курсы — модели параллель­ной обработки данных. В курсах по алгоритмам изучаются параллельные алгоритмы, а по ба­зам данных — блокировка и распределенные базы данных. В курсах по графике используется параллелизм при визуализации и трассировке лучей Этот список можно продолжить. Кроме того, параллельные вычисления стали фундаментальным инструментом в широкой области научных и инженерных дисциплин.


Главная цель книги, как видно из ее названия, — заложить основу для программирования многопоточных, параллельных и распределенных вычислений. Частная цель — создать текст, который можно использовать в углубленном курсе для студентов и магистров. Когда некото­рая тема становится распространенной, как это произошло с параллелизмом, вводятся учеб­ные курсы по ее основам. Аналогично, когда тема становится хорошо изученной, как сейчас параллелизм, она переносится в нормативный курс.
Я пытался охватить те вопросы параллельной и распределенной обработки данных, кото­рые, по моему мнению, должен знать любой студент, изучающий вычислительную технику. Сюда включены основные принципы, методы программирования, наиболее важные прило­жения, реализации и вопросы производительности. Я добавил также материал по важнейшим языкам программирования и библиотекам программ — потоки Pthread (три главы), язык Java (три главы), CSP, Linda, MPI (две главы), языки Ада, SR и ОрепМР. В каждом примере сна­чала описаны соответствующие части языка программирования или библиотеки, а затем представлена полная программа. Исходные тексты программ доступны на Web-сайте этой книги. Кроме того, в главе 12 приведен обзор нескольких дополнительных языков, моделей и инструментов для научных расчетов.
С другой стороны, ни в одной книге нельзя охватить все, поэтому, возможно, студенты и преподаватели захотят дополнить данный текст. Исторические справки и списки литературы в конце каждой главы описывают дополнительные материалы и содержат указания для даль­нейшего изучения. Информация для дальнейшего изучения и ссылки на соответствующие материалы представлены на Web-сайте этой книги.
Предисловие                                                                                                                  15
Обзор содержания
Эта книга состоит из 12 глав. В главе 1 дается обзор основных идей параллелизма, аппарат­ной части и приложений. Затем рассматриваются пять типичных приложений: умножение мат­риц, адаптивная квадратура, каналы ОС Unix, файловые системы и распределенное умножение матриц.


Каждое приложение просто, но, тем не менее, полезно: вместе они иллюстрируют не­который диапазон задач и пять стилей программирования многократных вычислений. В по­следнем разделе главы 1 резюмируется программная нотация, использованная в книге.
Оставшиеся главы разделены на три части. Часть 1 описывает механизмы параллельного программирования, которые используют разделяемые переменные и поэтому непосредст­венно применяются к машинам с разделяемой памятью. В главе 2 представлены базовые по­нятия процессов и синхронизации; основные моменты иллюстрируются рядом примеров. За­канчивается глава обсуждением формальной семантики параллелизма. Понимание семанти­ческих концепций поможет вам разобраться в некоторых разделах последующих глав. В главе 3 показано, как реализовать и использовать блокировки и барьеры, описаны алгорит­мы, параллельные по данным, и метод параллельного программирования, называемый "портфель задач". В главе 4 представлены семафоры и многочисленные примеры их исполь­зования. Семафор был первым механизмом параллельного программирования высокого уровня и остается одним из важнейших. В главе 5 подробно описаны мониторы. Они появи­лись в 1974г.; в 80-е и в начале 90-х годов внимание к ним несколько угасло, но появление языка Java возобновило интерес к ним. Наконец, в главе 6 представлена реализация процес­сов, семафоров и мониторов на одно- и многопроцессорных машинах.
Часть 2 посвящена распределенному программированию, в котором процессы взаимо­действуют и синхронизируются, используя сообщения. В главе 7 описана передача сооб­щений с помощью элементарных операций send и receive. Демонстрируется, как ис­пользовать эти операции для программирования фильтров (программ с односторонней связью), клиентов и серверов (с двусторонней связью), а также взаимодействующих рав­ных (с передачей в обоих направлениях). В главе 8 рассматриваются два дополнительных примитива взаимодействия: удаленный вызов процедуры (RPC) и рандеву.


Процесс- клиент инициирует связь, посылая сообщение call (неявно оно является последователь­ностью сообщений send и receive). Взаимодействие обслуживается или новым процес­сом (RPC), или с помощью рандеву с существующим процессом. В главе 9 описано не­сколько моделей взаимодействия процессов в распределенных программах. Три из них обычно используются в параллельных вычислениях— "управляющий-рабочие", алгоритм пульсации и конвейер. Еще четыре возникли в распределенных системах — зонд-эхо, опо­вещение (рассылка), передача маркера и дублируемые серверы. Наконец, в главе 10 описа­на реализация передачи сообщений, RPC и рандеву. Показано, как реализовать так назы­ваемую распределенную разделяемую память, которая поддерживает модель программиро­вания с разделяемой памятью в распределенной среде.
Часть 3 посвящена синхронному параллельному программированию, особенно его при­менению к высокопроизводительным научным вычислениям. (Многие другие типы син­хронных параллельных вычислений рассмотрены в предыдущих главах и в упражнениях к не­скольким из них.) Цель параллельной программы — ускорение, т.е. более быстрое решение задачи с помощью большого числа процессоров. Синхронные параллельные программы пи­шутся с использованием разделяемых переменных или передачи сообщений, следовательно, в них применяется методика, описанная в частях 1 и 2. В главе 11 рассматриваются три ос­новных класса приложений для научных вычислений: сеточные, точечные и матричные. Они возникают при моделировании физических и биологических систем; матричные вычисления используются и для таких задач, как экономическое прогнозирование. В главе 12 дан обзор наиболее важных инструментов для написания научных параллельных вычислительных программ: библиотеки (Pthread, MPI, OpenMP), распараллеливающие компиляторы, языки и модели, а также такие инструменты более высокого уровня, как метавычисления.
16                                                                                                                             Предисловие


В конце каждой главы размещены историческая справка, ссылки на литературу и упраж­нения. В исторической справке резюмируются происхождение, развитие и связи каждой те­мы с другими темами, а также описываются статьи и книги из списка литературы. В упражне­ниях представлены вопросы, поднятые в главе, и дополнительные приложения.
Использование в учебном процессе
Я использую эту книгу каждой весной в университете штата Аризона, читая курс пример­но для 60 студентов. Около половины из них — магистры; остальные — студенты старших курсов. В основном это студенты специальности "computer science". Данный курс для них не обязателен, но большинство студентов его изучают. Также каждый год курс проходят не­сколько аспирантов других отделений, интересующихся вычислительной техникой и парал­лельными вычислениями. Большинство студентов одновременно проходят и наш курс по операционным системам.
В наших курсах по ОС, как и везде, рассматриваются потребности ОС в синхронизации и изучается реализация синхронизации, процессов и других элементов ОС, в основном, на од­нопроцессорных машинах. Мой курс демонстрирует, как использовать параллельность в ка­честве общего инструмента программирования для широкого диапазона приложений. Я рас­сматриваю методы программирования, концепции высокого уровня, параллельную и распре­деленную обработку данных. По существу, мой курс относится к курсу по ОС примерно так же, как сравнительный курс языков программирования относится к курсу по компиляторам.
В первой половине моего курса я подробно излагаю главу 2, а затем быстро прохожу по остальным главам первой части, акцентируя внимание на темах, не рассматриваемых в курсе по ОС, — протокол "проверить-проверить-установить" (Test-and-Test-and-Set), алгоритм билета, барьеры, передача эстафеты для семафоров, некоторые способы про­граммирования мониторов и многопроцессорное ядро. В дополнение к этому студенты са­мостоятельно изучают библиотеку Pthread, потоки языка Java и синхронизированные ме­тоды.


После лекций по барьерам они выполняют проект по синхронным параллельным вычислениям (на основе материала главы 11).
Во второй половине курса я использую многое из материала части 2 книги, касающегося распределенного программирования. Мы рассматриваем передачу сообщений и ее использо­вание в программировании как распределенных систем, так и распределенных параллельных вычислений. Затем мы изучаем RPC и рандеву, их воплощение в языках Java и Ada и прило­жения в распределенных системах. Наконец, мы рассматриваем каждую парадигму из гла­вы 9, вновь используя для иллюстрации и мотивировки приложения из области синхронных параллельных и распределенных систем. Самостоятельно студенты изучают библиотеку MPI и снова используют язык Java.
В течение семестра я даю четыре домашних задания, два аудиторных экзамена, проект по параллельным вычислениям и заключительный проект. (Примеры представлены на Web-сайте книги.) Каждое домашнее задание состоит из письменных упражнений и одной или двух задач по программированию. Магистры должны выполнить все упражнения, другие сту­денты — две трети задач (по своему выбору). Экзамены проводятся аналогично: магистры решают все задачи, а остальные выбирают вопросы, на которые хотят отвечать. В Аризонском университете начальные задачи по программированию мы решаем с помощью языка SR, ко­торый студенты могут использовать и в дальнейшем, но поощряется использование таких языков и библиотек, как Pthreads, Java и MPI.
Проект по синхронному параллельному программированию связан с задачами из главы 11 (обычно это сеточные вычисления). Студенты пишут программы и экспериментируют на не­большом мультипроцессоре с разделяемой памятью. Магистры реализуют более сложные алгоритмы и обязаны написать подробный отчет о своих опытах. Заключительный проект — это статья или программный проект по какому-либо вопросу распределенного программиро­вания. Студенты выбирают тему, которую я утверждаю. Большинство студентов выполняют
Предисловие                                                                                                                                      17


проекты по реализации, многие из них работают парами. Студенты создают разнообразные интересные системы, в основном, с графическим интерфейсом.
Несмотря на то что студенты, изучающие мой курс, имеют различную подготовку, поч­ти все оценивают его отлично. Студенты часто отмечают, насколько хорошо курс согласу­ется с их курсом по ОС; им нравится взгляд на параллельность с другой точки зрения, изу­чение многопроцессорных систем, им интересно рассматривать широкий спектр приложе­ний и инструментов. Магистры отмечают, что курс связывает воедино разные вещи, о которых они уже что-то слышали, и вводит их в область параллельного программирова­ния. Однако многим из них было бы интересно изучить параллельные вычисления более подробно Со временем мы надеемся сделать отдельные курсы для магистров и студентов. Я не буду значительно изменять курс для студентов, но в нем будет меньше углубленных тем. В курсе для магистров я буду тратить меньше времени на материал, с которым они уже знакомы (часть 1), и больше времени посвящать синхронным параллельным приложениям и инструментарию синхронных вычислений (часть 3).
Эта книга идеально подходит для курса, который охватывает область механизмов парал­лельного программирования, средств и приложений. Почти все студенты смогут использо­вать что-то из рассмотренного здесь, но не все будут заниматься только параллельной обра­боткой данных, только распределенными системами или программировать только на языке Java. Тем не менее книгу можно использовать и как пособие в более специализированных курсах, например, в курсе синхронных параллельных вычислений, вместе с книгами по па­раллельным алгоритмам и приложениям.
Информация в Internet
"Домашняя страничка" этой книги находится по адресу:
http://www.cs.arizona.edu/people/greg/mpdbook
На этом сайте есть исходные тексты программ из книги, ссылки на программное обеспече­ние и информацию о языках программирования и библиотеках, описанных в примерах; большое число других полезных ссылок.


Также сайт содержит обширную информацию о моем курсе в Аризонском университете, включая программу курса, конспекты лекций, копии домашних заданий, проектов и экзаменационных вопросов. Информация об этой книге также доступна по адресу:
http://www.awlonline.com/cs
Несмотря на мои усилия, книга, без сомнения, содержит ошибки, так что по этому адресу поя­вится (уверен, что скоро) их список. Безусловно, в будущем добавятся и другие материалы.
Благодарности
Я получил множество полезных замечаний от читателей чернового варианта этой книги. Марте Тиенари (Martti Tienary) и его студенты из университета Хельсинки обнаружили не­сколько неочевидных ошибок. Мои последние аспиранты, Вине Фрих (Vince Freeh) и Дейв Ловентал (Dave Lowenthal), прокомментировали новые главы и за последние несколько лет помогли отладить если не мои программы, то мои мысли. Студенты, изучавшие мой курс весной 1999 г., служили "подопытными кроликами" и нашли несколько досадных ошибок. Энди Бернат (Andy Bernat) предоставил отзыв о своем курсе в университете в Эль-Пасо, Те­хас, который он провел весной 1999 г. Благодарю следующих рецензентов за их бесценные от­зывы: Джаспал Субхлок (Jaspal Subhlok) из университета Carnegy Mellon, Болеслав Жимански (Boleslaw Szymansky) из политехнического института Rensselaer, Дж. С. Стайлс (G. S. Stiles) из Utah State University, Нарсингх Део (Narsingh Deo) из Central Florida University, Джанет Харт-ман (Janet Hartman) из Illinois State University, Нэн Шаллер (Nan С. Schaller) из Технологиче­ского института Рочестера и Марк Файнап (Mark Fineup) из университета Северной Айовы.
В течение многих лет организация National Science Foundation поддерживает мои иссле­дования, в основном по грантам CCR-9415303 и ACR-9720738. Грант от NSF (CDA-9500991) помог обеспечить оборудование для подготовки книги и проверки программ.
И главное — я хочу поблагодарить мою жену Мэри, еще раз смирившуюся с долгими ча­сами, которые я провел, работая над этой книгой (несмотря на клятвы вроде "больше нико­гда" после завершения книги о языке SR).




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