Конкурентное программирование
Выполнение программы — это одна активность. Конкурентность — это множество активностей. Для начала рассмотрим несколько сценариев-примеров конкурентных процессов.
Сценарий: телефонная будка
Существует телефонная будка и люди, которые хотят позвонить. При этом одновременно звонить может только один человек. Обозначим телефонную будку как ресурс, а людей — процессами. Значит только один процесс может использовать ресурс одновременно. Это так называемое взаимное исключение(mutual exclusion/mutex), когда два и более процесса не могут быть активны одновременно.
Сценарий: в булочной
В булочной у кассы стоит продавец. Некоторое количество людей хочет купить хлеба. Одновременно обслуживается только один человек. Из-за скученности покупателей и из-за каких-либо персональных симпатий продавца, он может постоянно пропускать людей(процессы) вперед. Тогда возникает проблема равноправного распределения ресурса хлеб, ведь будет кто-то, кому придется вечно ждать. Такой процесс зависает(starvation). Чтобы этого не случилось следует выстраивать процессы в очередь.
Сценарий: счет в банке
На счету в банке лежат 100 рублей(ресурс). Банкоматы, магазины, банки(процессы) могут снять деньги с этого счета. Банкомат(процесс А) посылает запрос "есть 100 рублей?". Если получает ответ, что есть, то посылает запрос "дай 100 рублей". Но это плохая стратегия, так как возможно что некий процесс Б уже снял деньги и на счету пусто. Или если два процесса хотят одновременно снять деньги с счета — непонятно, какому процессу отдать предпочтение. Это явление называется недетерминизм(nondeterminism), когда неизвестно, какой именно процесс первым достигнет ресурса, изменит переменную money на нашем счету. Когда именно процесс достигнет русурса предугадать невозможно.
Сценарий: отдых в горах
Процесс А и процесс Б решили провести отпуск в горах. Для этого им необходима машина и лыжи(ресурсы). Есть возможность отдолжить только одни лыжи и одну машину. Если процесс получит машину и лыжи, то отправится в отпуск, а другой процесс будет ждать его возвращения, чтобы получить лыжи и машину. Если же один процесс получит лыжи, а другой машину, то оба будут ждать недостающего снаряжения и никто(никогда) не поедет в отпуск. Возникает взаимоблокировка(deadlock), когда каждый процесс ждет освобождения ресурса используемого другим процессом.
Другой пример конкурентных процессов — обедающие философы Дейкстры[Dijkstra1960]. За круглым столом сидят три философа(процессы) между каждыми двумя лежит по палочке для риса(ресурсы). Философы могут кушать рис двумя палочками или размышлять. Может случиться так что одному из философов не будет хватать палочки и он будет голодать(starvation). Либо философы одновременно возьмут по одной палочке и будут ждать другой. Это приведет в взаимной блокировке и зависанию процессов.
В операционных системах необходим более чем один процесс. ОС — это руководящая программа компьютера и она создает возможность запуска нескольких программ. Программа — это описание процесса. Запущенная программа — это процесс. Причем процесс можно запустить многократно. ОС предоставляет возможности коммуникации для процесссов, чтобы процессы могли обмениваться между собой данными. Также ОС предоставляет возможности обмена данными между процессами различных компьютеров.
Параллелизм означает одновременное выполнение операций. На компьютере с параллельным процессором программы могут выполнятся параллельно. Конкурентность это не параллелизм, так как у компьютера в основном только один процессор. Происходит очень быстрое переключение между процессами, потому и кажется что они выполняются параллельно. Для примера представим, что в классе 20 учеников(процессов) и один учитель(процессор). Учитель подходит к каждому ученику, отвечает на вопрос и переходит быстро к следующему. Это конкуррентная модель. В классе 20 учеников(процессы) и 20 учителей(процессоры). У каждого ученика свой учитель, который не покидает ученика. Это параллельная модель.
Нить(thread) — это последовательное выполнение внутри процесса. У каждого процесса есть хотя бы одна нить. Рассмотрим пример, когда робот принимает информацию от другого робота, тем временем в другой нити он посылает информацию, в третьей нити работает счетчик времени. У процессов различные области памяти. Нити одного процесса видят одну и туже область памяти. С помощью нитей отдельные части процесса выполняются конкурентно. Необходимо написание таких алгоритмов, которые позволят параллельное выполнение процессов.
Рассмотрим пару простейших концептов конкурентного программирования.
Фьючер(future) — это зарезервированная программная конструкция для еще неизвестного результата конкурентного вычисления. Рассмотрим пример, когда из главной нити вызываются другие нити которые подсчитывают некие значения. На месте результата каждой нити стоит фьючер, он замещает еще не подсчитанное значение каждой нити. Нить блокируется автоматически пока не будет подсчитано значение каждой дочерней нити. Когда результат нити вычеслен, то он сразу передается главной нити. Фьючер можно например передавать как аргумент функции, когда еще значение аргумента неизвестно. В любом случае фьючер используется тогда, когда необходимо зарезервировать место под некую переменную. Примером функциональный язык с конструкциями для параллельного выполнения и использованием фьючерсов является Multilisp.
Вычисления по востребованию(Lazy evaluation): выражение подсчитывается только в том случае если это действительно необходимо и только один раз. Ожидание до последнего момента, чтобы оптимировать алгоритм, который возможно не будет использовать значение выражения. Это особенно полезно если выражение очень сложно подсчитать, либо при бесконечных выражениях. Как пример: (повторяй x=x+2) — бесконечная структура. Подсчитано будет лишь в том случае когда это необходимо, то есть если понадобится 20 повторений, то и подсчитано будет только 20. Язык программирования Haskell является самым ленивым(lazy) функциональным языком программирования, поддерживающим вычисления по востребованию. Подобным образом работает и компиляция программ по востребованию(on-demand). Для этого существют так называемые Just-in-time-compilers(JIT), которые преобразуют код на лету в машинный язык специфической машины/ОС, при этом оптимизируя отдельные части программы. Например Java. Однако в JIT много и недостатков.
Мониторы
Это специальные синхронизирующие процедуры, которые гарантируют доступ только одной нити к какому-либо объекту. Доступ к объекту возможен только через методы монитора. Все другие нити направляются в очередь и ждут освобождения объекта. Освобожденный объект передается монитором следующей нити. Мониторы были предложены Хором(Hoare) в 1975 году.
Удаленный вызов процедуры(Remote procedure call)
Прооцесс А хочет вызвать процедуру п из процесса Б. При этом должен быть передан аргумент из А в Б, а назад — результат. Для этих целей используют прокси — специальную процедуру которая создается в вызывающем процессе и руководит коммуникацией между процессом А и процессом Б.
В конкурентном программировании существуют и более сложные технологии "распараллеливания" процессов и у конкурентного программирования есть будущее. Транзисторы процессора уже очень скоро некуда будет уменьшать и будут использоваться параллельные процессоры, а значит и технологии конкурентного программирования.
t4b, 15.2.2005,
http://traceproject.h14.ru/concurprog.shtml
Ссылки:
Язык Haskell:
http://www.haskell.org/
Язык Multilisp:
http://en.wikipedia.org/wiki/Multilisp
Djikstra's philisophers:
http://cs-exhibitions.uni-klu.ac.at/contentDining_main.php
Добавлено форматирование, чтобы было как в оригинале :) — Кодт
30.08.05 00:40: Перенесено модератором из 'Декларативное программирование' — VladD2
