ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ. Теория вычислительных процессов
 Скачать 2.17 Mb.
|
|
Кратные ресурсы Выше мы описали, как некоторое число параллельных процессов с различным поведением могут совместно использовать один подчиненный процесс. Каждый процесс-пользователь соблюдает дисциплину чередования ввода и вывода или чередования сигналов занят/свободен с тем, чтобы в каждый момент времени разделяемым ресурсом пользовался не более чем один процесс. Такие ресурсы называют последовательно переиспользуемыми. В этом разделе вводятся массивы процессов, представляющие кратные ресурсы с одинаковым поведением; индексы в массиве обеспечивают тот факт, что каждый элемент достоверно взаимодействует только с использующим его процессом. Мы будем использовать индексы и операторы с индексами, смысл которых очевиден. Например: ; . В последнем примере мы требуем, чтобы f была взаимно однозначной для того, чтобы выбор между альтернативами осуществлялся обстановкой. Пример 3.28. Повторно входимая подпрограмма. Последовательно переиспользуемая общая подпрограмма может обслуживать вызывающие ее процессы только по одному. Если выполнение подпрограммы требует значительных вычислений, соответствующие задержки могут возникнуть и в вызывающем процессе. Если же для вычислений доступны несколько процессоров, нам ничто не мешает позволить нескольким экземплярам подпрограммы параллельно исполняться на различных процессорах. Подпрограмма, имеющая несколько параллельно работающих экземпляров, называется повторно входимой и определяется как массив параллельных процессов: yдв: (УДВ)) //…. Типичным вызовом этой подпрограммы будет (удв.3.лев!30 → удв.3.прав?у →ПРОПУСК). Присутствие индекса 3 гарантирует, что результат вызова получен от того же самого экземпляра удв, которому были посланы аргументы, даже несмотря на то, что в это же время некоторые другие параллельные процессы могут вызывать другие элементы массива, что приводит к чередованию сообщений типа: удв.3.лев.30,...удв.2.лев.20,... удв.3.прав.60,... удв.2.прав.40,... Когда процесс вызывает повторно входимую подпрограмму, на самом деле не имеет значения, какой из элементов массива ответит на этот вызов; годится любой в данный момент свободный процесс. Поэтому вместо того, чтобы указывать конкретный индекс 2 или 3, вызывающий процесс должен делать произвольный выбор, используя конструкцию: (удв.i.лев!30 → удв.i.прав?у → ПРОПУСК). При этом по-прежнему существенно требование, чтобы для передачи аргументов и (после этого) получения результата использовался один и тот же индекс. Различают локальные вызовы процедуры, поскольку предполагается, что выполнение процедуры происходит на том же процессоре, что и выполнение вызывающего процесса, и дистанционные вызовы общей процедуры когда предполагает исполнение на отдельном, возможно, удаленном процессоре. Так как эффект дистанционного и локального вызова должен быть одинаковым, причины для использования именно дистанционного вызова могут быть только организационными или экономическими. Например, для хранения кода процедуры в секрете или для исполнения его на машине, имеющей какие-то специальные средства, слишком дорогие для установки их на той машине, на которой исполняются процессы-пользователи. Типичным примером таких дорогостоящих устройств могут служить внешние запоминающие устройства большой емкости — такие, как дисковая или доменная память. Пример 3.29. Общая внешняя память. Запоминающая среда разбита на В секторов, запись и чтение с которых могут производиться независимо. В каждом секторе может храниться один блок информации, которая поступает слева и выводится направо. К несчастью, запоминающая среда реализована по технологии разрушающего считывания, так что каждый блок может быть считан только один раз. Дополнительная память в целом представляет собой массив таких секторов с индексами, не превосходящими В: ДОППАМ= i:КОПИР. Предполагается, что эта память используется как подчиненный процесс (доп: ДОППАМ //...). Внутри основного процесса доступ к этой памяти осуществляется взаимодействиями доп.i.лев!блок →... доп.i.прав?у →.... Дополнительная память может также совместно использоваться параллельными процессами. В этом случае действие  (доп.i.лев!блок →...)одновременно займет произвольный свободный сектор с номером i и запишет в него значение блок. Аналогично, доп.1.прав?х за одно действие считает содержимое сектора iвх и освободит этот сектор для дальнейшего использования, вероятно, уже другим процессом. Именно это упрощение и послужило истинной причиной использования КОПИРдля моделирования каждого сектора.Конечно, успешное совместное использование этой дополнительной памяти требует от процессов-пользователей строжайшего соблюдения дисциплины. Процесс может совершить ввод информации с некоторого сектора, только если именно этот процесс последним выводил туда информацию, причем за каждым выводом рано или поздно должен последовать такой ввод. Несоблюдение этого порядка приводит к тупиковой ситуации или к еще худшим последствиям. Планирование ресурсов Когда ограниченное число ресурсов разделено между большим числом потенциальных пользователей, всегда существует возможность того, что некоторым пользователям, стремящимся занять ресурс, приходится ждать, пока его освободит другой процесс. Если к моменту освобождения ресурса его хотят занять два или более процесса, выбор того, который из ожидающих процессов получит ресурс, во всех приводившихся примерах был недетерминированным. Само по себе это большого значения не имеет, но предположим, что к тому моменту, когда ресурс снова освободится, к множеству ожидающих присоединится еще один процесс. Поскольку выбор между ожидающими процессами по-прежнему недетерминирован, может случиться, что повезет именно вновь присоединившемуся процессу. Если ресурс сильно загружен, так может случиться снова и снова. В результате может оказаться, что некоторые процессы будут откладываться бесконечно или по крайней мере в течение полностью неопределенного времени. С этой проблемой, называемой бесконечным перехватом, мы уже знакомы (см. п. 3.2.3). Одним из решений проблемы является обеспечение того, чтобы все ресурсы были несильно загружены. Этого можно достигнуть либо введением дополнительных ресурсов, либо установлением высокой платы за предоставляемые услуги. Фактически это единственно приемлемые решения в случае постоянно загруженного ресурса. К сожалению, даже в среднем несильно загруженный ресурс достаточно часто оказывается сильно загруженным в течение длительных периодов (в часы пик). Иногда проблему удается сгладить введением дифференцированного тарифа в попытке регулирования спроса, но это не всегда помогает и даже не всегда удается. В течение таких пиков задержки процесса-пользователя в среднем неизбежны. Важно лишь следить за сообразностью и предсказуемостью таких задержек — вы, несомненно, предпочтете знать, что вас обслужат в течение часа, чем гадать, сколько еще придется ждать - одну минуту или целые сутки. Задача распределения ресурса между ожидающими пользователями известна как планирование ресурсов. Для успешного планирования необходимо знать, какие процессы в текущий момент ожидают получения ресурса. По этой причине получение ресурса отныне нельзя рассматривать как одно элементарное событие. Его необходимо разбить на два события: пожалуйста, осуществляющее запрос ресурса, спасибо, сопровождающее реальное получение ресурса. Период между пожалуйста и спасибо для каждого процесса является временем, в течение которого он ждет ресурс. Чтобы различать ожидающие процессы, каждое вхождение события пожалуйста, спасибо и свободен помечено отличным от других натуральным индексом. При каждом запросе ресурса процесс получает номер с помощью конструкции: (рес.i. пожалуйста; реc.i.спасибо;...; реc.i.свободен → ПРОПУСК). Простым и эффективным способом планирования ресурса является назначение его процессу, ожидавшему дольше всех. Такая политика называется «первым пришел — первым, обслужен» (FСFS) или «первым пришел — первым ушел»(FIFO) и представляет собой принцип очереди, соблюдаемый, к примеру, пассажирами на автобусной остановке. В заведении же типа поликлиники, где посетители не могут; или не хотят выстраиваться в очередь, для достижения того же результата действует другой механизм. Регистратура выдает талоны со строго возрастающими последовательными номерами. При входе в поликлинику посетитель берет талон. Когда врач освободился, он вызывает посетителя, имеющего талон с наименьшим номером, но еще не принятого. Этот алгоритм, называемый алгоритмом поликлиники, более строго описан ниже. Мы будем предполагать, что одновременно могут обслуживаться до Rпосетителей. Пример 3.30. Алгоритм поликлиники. Нам потребуются три счетчика: р — посетители, сказавшие пожалуйста, t— посетители, сказавшие спасибо, r— посетители, освободившие свои ресурсы. Очевидно, что в любой момент времени r  t р. Кроме того, р всегда будет номером, который получает очередной посетитель, приходящий в поликлинику, а t —номером очередного обслуживаемого посетителя; далее, р —t будет числом ожидающих посетителей, а R + r—t— числом ожидающих врачей. Вначале значения всех счетчиков равны нулю и могут быть вновь положены равными нулю в любой момент, когда их значения совпадают — например, вечером, после ухода последнего посетителя.Одной из основных задач алгоритма является обеспечение того, чтобы никогда не было одновременно свободного ресурса и ждущего посетителя; как только возникает такая ситуация, следующим событием должно стать спасибо посетителя, получающего ресурс. ПОЛИКЛИНИКА = B0,0,0 Вp,t,r = if 0 < r=t = р then ПОЛИКЛИНИКА elseif R+r – t > 0ANDр— t > 0 then t.спасибо→Вр,t+1,r еlse (р.пожалуйста→Вр+1,t, r | i.свободен → Вр,t,r+1)). Программирование параллельных вычислений Основные понятия Исполнение процессов типичной параллельной программы прерывается значительно чаще, чем процессов, работающих в последовательной среде, так как процессы параллельной программы выполняют еще действия, связанные с обменом данными между процессорами. Манипулирование полновесными процессами в мультипрограммной среде является дорогостоящим действием, поскольку это тесно связанно с управлением и защитой памяти. Вследствие этого большинство параллельных компьютеров использует легковесные процессы, называемые нитямиили потоками управления, а не полновесные процессы. Легковесные процессы не имеют собственных защищенных областей памяти (хотя могут обладать собственными локальными данными), а в результате очень сильно упрощается манипулирование ими. Более того, их использование более безопасно. В соответствии с возможностями параллельного компьютера процессы взаимодействуют между собой обычно одним из следующих способов: Обмен сообщениями. Посылающий процесс формирует сообщение с заголовком, в котором указывает, какой процессор должен принять сообщение, и передает сообщение в сеть, соединяющую процессоры. Если, как только сообщение было передано в сеть, посылающий процесс продолжает работу, то такой вид отправки сообщения, называется неблокирующим. Если же посылающий процесс ждет, пока принимающий процесс не примет сообщение, то такой вид отправки сообщения, называется блокирующим. Принимающий процесс должен знать, что ему необходимы данные, и должен указать, что готов получить сообщение, выполнив соответствующую команду приема сообщения. Если ожидаемое сообщение еще не поступило, то принимающий процесс приостанавливается до тех пор, пока сообщение не поступит. Обмен через общую память. В архитектурах с общедоступной памятью процессы связываются между собой через общую память - посылающий процесс помещает данные в известные ячейки памяти, из которых принимающий процесс может считывать их. При таком обмене сложность представляет процесс обнаружения того, когда безопасно помещать данные, а когда удалять их. Чаще всего для этого используются стандартные методы операционной системы, такие как семафоры или блокировки процессов. Однако это дорого и сильно усложняет программирование. Некоторые архитектуры предоставляют биты занято/свободно, связанные с каждым словом общей памяти, что обеспечивает легким и высокоэффективный способ синхронизации отправителей и приемников. Прямой доступ к удаленной памяти. В первых архитектурах с распределенной памятью работа процессоров прерывалась каждый раз, когда поступал какой-нибудь запрос от сети, соединяющей процессоры. В результате процессор плохо использовался. Затем в таких архитектурах в каждом процессорном элемент стали использовать пары процессоров - один процессор (вычислительный), исполняет программу, а другой (процессор обработки сообщений) обслуживает сообщения, поступающие из сети или в сеть. Такая организация обмена сообщениями позволяет рассматривать обмен сообщениями как прямой доступ к удаленной памяти, к памяти других процессоров. Эта гибридная форма связи, применяется в архитектурах с распределенной памятью, обладает многими свойствами архитектурах с общей памятью. Рассмотренные механизмы связи необязательно используются только непосредственно на соответствующих архитектурах. Так легко промоделировать обмен сообщениями, используя общую память, с другой стороны можно смоделировать общую память, используя обмен сообщениями. Последний подход известен как виртуальная общая память. Наиболее желательными (даже скорее обязательными) признаками параллельных алгоритмов и программ являются: параллелизм, масштабируемость, локальность, модульность. Параллелизм указывает на способность выполнения множества действий одновременно, что существенно для программ выполняющихся на нескольких процессорах. Масштабируемость - другой важнейший признак параллельной программы, который требует гибкости программы по отношению к изменению числа процессоров, поскольку наиболее вероятно, что их число будет постоянно увеличиваться в большинстве параллельных сред и систем. Локальность характеризует необходимость того, чтобы доступ к локальным данным был более частым, чем доступ к удаленным данным. Важность этого свойства определяется отношением стоимостей удаленного и локального обращений к памяти. Оно является ключом к повышению эффективности программ на архитектурах с распределенной памятью. Модульность отражает степень разложения сложных объектов на более простые компоненты. В параллельных вычислениях это такой же важный аспект разработки программ, как и в последовательных вычислениях. Код, исполняющийся в одиночном процессоре параллельного компьютера, находится в некоторой программной среде такой же, что и среда однопроцессорного компьютера с мультипрограммной операционной системой, поэтому и в контексте параллельного компьютера так же говорят опроцессах, ссылаясь на код, выполняющийся внутри защищенного региона памяти операционной системы. Многие из действий параллельной программы включают обращения к удаленным процессорам или ячейкам общей памяти. Выполнение этих действий может потребовать время, существенное, особенно, по отношению к времени исполнения обычных команд процессора. Поэтому большинство процессоров исполняет более одного процесса одновременно, и, следовательно, в программной среде отдельно взятого процессора параллельного компьютера применимы обычные методы мультипрограммирования. Многопоточная обработка Если L — метка некоторого места в программе, то команда fork L передает управление на метку L, а также и на следующую команду в тексте программы. В результате создается эффект, что с этого момента два процессора одновременно исполняют одну и ту же программу; каждый из них независимо обрабатывает свою последовательность команд. Поскольку каждая такая последовательность обработки может снова разветвиться, эта техника получила название многопоточной обработки. Введя способ разбиения одного процесса на два, мы нуждаемся и в способе слияния двух процессов в один. Проще всего ввести командуjoin, которая может выполниться только при одновременном исполнении ее двумя процессами. Первый достигший этой команды процесс должен ждать, когда ее достигнет другой. После этого уже только один процесс продолжает исполнение последующих команд. Разновидность команды ветвления до сих пор используется в операционной системе UNIХ™. При этом ветвление не подразумевает переход по метке. Его эффект заключается во взятии совершенно новой копии всей памяти программы и передачи этой копии новому процессу. Как исходный, так и новый процессы продолжают исполнение с команды, следующей за командой ветвления. У каждого процесса есть средство определить, является ли он порождающим (отец) или порождаемым (сын). Выделение процессам непересекающихся участков памяти снимает основные трудности и опасности многопоточной обработки, но может быть неэффективным как по времени, так и по объему памяти. Это означает, что параллелизм допустим только на самом внешнем (самом глобальном) уровне задания, а использование его в мелком масштабе затруднительно. |