Разделяемые ресурсы

Обозначение (m://S) мы использовали для именованного подчиненного процесса (m:R), единственной обязанностью которого является удовлетворение потребностей главного процесса S. Предположим теперь, что S состоит из двух параллельных процессов (P || Q) и они оба нуждаются в услугах одного и того же подчиненного процесса (m:R). К сожалению, P и Q не могут взаимодействовать с R по одним и тем же каналам, потому что тогда эти каналы должны содержаться в алфавитах обоих процессов, и, значит, согласно определению оператора ||, взаимодействия с (m: R) могут происходить, только когда P и Q одновременно посылают одно и то же сообщение, что далеко не соответствует желаемому результату. Нам же требуется своего рода чередование взаимодействий между P и (m:R) с взаимодействиями между Q и (m:R). В этом случае (m:R) служит как ресурс, разделяемый P и Q; каждый из них использует его независимо, и их взаимодействия с ним чередуются.

Когда все процессы-пользователи известны заранее, можно организовать работу так, чтобы каждый процесс-пользователь имел свой набор каналов для взаимодействий с совместно используемым ресурсом. Эта техника применялась в задаче об обедающих философах: каждая вилка совместно использовалась всеми пятью. Общий метод разделения ресурсов дает множественная пометка, которая является эффективным средством создания достаточного числа каналов для независимого взаимодействия с каждым процессом-пользователем. Отдельные взаимодействия по этим каналам произвольно чередуются. Однако при таком методе необходимо знать заранее имена всех процессов-пользователей, и поэтому он не подходит для подчиненного процесса, предназначенного для обслуживания главного процесса, который разбивается на произвольное число параллельных подпроцессов.

3.4.1. Поочередное использование

Проблему, вызванную использованием комбинирующего оператора ||, можно избежать, используя параллелизм в форме чередования (P

Q). Здесь P и Q имеют одинаковые алфавиты, а их взаимодействия с совместно используемыми внешними процессами произвольно чередуются. Пример 3.25. Совместно используемая подпрограмма: удв: УДВ // (P Q). Здесь и P, и Q могут содержать вызов подчиненного процесса (удв.лев!v → удв.прав?х → ПРОПУСК), где ПРОПУСК – процесс, который ничего не делает, но благополучно завершается. Пример 3.26. Совместно используемое алфавитно-цифровое печатающее устройство: АЦПУ = занят → µХ.(лев?s → h!s → X | свободен → АЦПУ) Здесь h – канал, соединяющий АЦПУ с аппаратной частью устройства. После наступления события занят АЦПУ копирует в аппаратную часть последовательно поступающие по левому каналу строки, пока сигнал свободен не приведет его в исходное состояние, в котором он доступен для использования другими процессами. Этот процесс используется как разделяемый ресурс: ацпу: АЦПУ // … (P

Q)… Внутри P или Q вывод последовательности строк, образующей файл, заключен между событиями ацпу.занят и ацпу.свободен: ацпу.занят → … ацпу.лев!”Вася” →… ацпу.лев!следстр → … ацпу.свободен 3.4.2. Общая память Цель этого раздела – привести ряд аргументов против использования общей памяти. Поведение систем параллельных процессов без труда реализуется на обыкновенной ЭВМ с хранимой программой с помощью режима разделения времени, при котором единственный процессор поочередно выполняет каждый из процессов, причем смена выполняемого процесса происходит по прерыванию, исходящему от некоторого внешнего или синхронизирующего устройства. При такой реализации легко позволить параллельным процессам совместно использовать общую память, выборка и загрузка которой осуществляется каждым процессом. Ячейка общей памяти – это разделяемая переменная: (счет: ПЕРЕМ // (счет.лев!0 → (P Q))). Произвольное чередование присваиваний в ячейку общей памяти различными процессами является следствием многочисленных опасностей. Пример 3.27. Взаимное влияние. Разделяемая переменная счет используется для подсчета числа исполнений некоторого важного события. При каждом наступлении этого события соответствующий процесс Р или О пытается изменить значение счетчика парой взаимодействий счет.прав?х; счет. лев! (х + 1) К сожалению, эти два взаимодействия могут перемежаться аналогичной парой взаимодействий от другого процесса, в результате чего мы получим последовательность счет.прав?х → счет.прав?у → счет.лев!(у + 1) → счет.лев!(х+ 1) →... В итоге значение счетчика увеличится лишь на единицу, а не на два. Такого рода ошибки известны как взаимное влияние и часто допускаются при проектировании процессов, совместно использующих общую память. Кроме того, проявление такой ошибки недетерминировано; ее воспроизводимость очень ненадежна, и поэтому ее практически невозможно диагностировать обычными методами тестирования. Возможным решением этой проблемы может быть контроль за тем, чтобы смена процесса не происходила при совершении последовательности действий, нуждающихся в защите от чередования. Такая последовательность называется критическим участком. При реализации с одним процессором требуемое исключение обычно достигается запрещением всех прерываний на протяжении критического участка. Нежелательным эффектом такого решения является задержка ответа на прерывание; но хуже всего то, что оно оказывается полностью несостоятельным, как только к машине добавляется второй процессор. Рисунок 4.1. А, В, С – разделяемый ресурс, Р1 Р2 – процессы. Более приемлемое решение было предложено Э. Дейкстрой, которому принадлежит идея использования двоичных семафоров. Семафор можно описать как процесс, поочередно выполняющий действия с именами Р и V; СЕМ = (Р → V → СЕМ) Он описывается как совместно используемый ресурс (взаискл: СЕМ //...). При условии, что все процессы подчиняются этой дисциплине, каждый из двух процессов не сможет влиять на изменение счетчика — произвести действие взаискл.V. Таким образом, критический участок, на котором происходит увеличение счетчика, должен иметь вид взаискл. Р → счет.прав?х → счет.лев!(х + 1) → взаискл.V →... При условии, что все процессы подчиняются этой дисциплине, каждый из двух процессов не сможет влиять на изменение счетчика своим партнером. Но если какой-нибудь процесс пропустит Р или V или выполнит их в обратном порядке, результат будет непредсказуемым и может привести к катастрофической или (что, возможно, еще хуже) неуловимой ошибке. Избежать взаимного влияния гораздо более надежным способом можно, встроив необходимую защиту в саму конструкцию общей памяти, воспользовавшись знанием о предполагаемом способе ее использования. Если, например, переменная будет использоваться только как счетчик, то ее увеличение можно задать одной элементарной операцией счет.вверх, а соответствующий разделяемый ресурс определить как СТ0: счет:СТ0 //(...Р.Q..) На самом деле, есть все основания рекомендовать, чтобы каждый совместно используемый ресурс заранее проектировался для своих целей и, чтобы в разработке системы с элементами параллелизма универсальная память не использовалась совместно. Этот метод не только предупреждает серьезную опасность случайного взаимного влияния, но и позволяет получать конструкции, поддающиеся эффективной реализации на сетях распределенных процессорных элементов, а также на одно- и многопроцессорных ЭВМ с физически общей памятью. 3.4.3. Кратные ресурсы Выше мы описали, как некоторое число параллельных процессов с различным поведением могут совместно использовать один подчиненный процесс. Каждый процесс-пользователь соблюдает дисциплину чередования ввода и вывода или чередования сигналов занят/свободен с тем, чтобы в каждый момент времени разделяемым ресурсом пользовался не более чем один процесс. Такие ресурсы называют последовательно переиспользуемыми. В этом разделе вводятся массивы процессов, представляющие кратные ресурсы с одинаковым поведением; индексы в массиве обеспечивают тот факт, что каждый элемент достоверно взаимодействует только с использующим его процессом. Мы будем использовать индексы и операторы с индексами, смысл которых очевиден. Например: В последнем примере мы требуем, чтобы 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.4.4. Планирование ресурсов Когда ограниченное число ресурсов разделено между большим числом потенциальных пользователей, всегда существует возможность того, что некоторым пользователям, стремящимся занять ресурс, приходится ждать, пока его освободит другой процесс. Если к моменту освобождения ресурса его хотят занять два или более процесса, выбор того, который из ожидающих процессов получит ресурс, во всех приводившихся примерах был недетерминированным. Само по себе это большого значения не имеет, но предположим, что к тому моменту, когда ресурс снова освободится, к множеству ожидающих присоединится еще один процесс. Поскольку выбор между ожидающими процессами по-прежнему недетерминирован, может случиться, что повезет именно вновь присоединившемуся процессу. Если ресурс сильно загружен, так может случиться снова и снова. В результате может оказаться, что некоторые процессы будут откладываться бесконечно или по крайней мере в течение полностью неопределенного времени. С этой проблемой, называемой бесконечным перехватом, мы уже знакомы (см. п. 3.2.3.5). Одним из решений проблемы является обеспечение того, чтобы все ресурсы были несильно загружены. Этого можно достигнуть либо введением дополнительных ресурсов, либо установлением высокой платы за предоставляемые услуги. Фактически это единственно приемлемые решения в случае постоянно загруженного ресурса. К сожалению, даже в среднем несильно загруженный ресурс достаточно часто оказывается сильно загруженным в течение длительных периодов (в часы пик). Иногда проблему удается сгладить введением дифференцированного тарифа в попытке регулирования спроса, но это не всегда помогает и даже не всегда удается. В течение таких пиков задержки процесса-пользователя в среднем неизбежны. Важно лишь следить за сообразностью и предсказуемостью таких задержек — вы, несомненно, предпочтете знать, что вас обслужат в течение часа, чем гадать, сколько еще придется ждать—одну минуту или целые сутки. Задача распределения ресурса между ожидающими пользователями известна как планирование ресурсов. Для успешного планирования необходимо знать, какие процессы в текущий момент ожидают получения ресурса. По этой причине получение ресурса отныне нельзя рассматривать как одно элементарное событие. Его необходимо разбить на два события: пожалуйста, осуществляющее запрос ресурса, спасибо, сопровождающее реальное получение ресурса. Период между пожалуйста и спасибо для каждого процесса является временем, в течение которого он ждет ресурс. Чтобы различать ожидающие процессы, каждое вхождение события пожалуйста, спасибо и свободен помечено отличным от других натуральным индексом. При каждом запросе ресурса процесс получает номер с помощью конструкции: (рес.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 ПОЛИКЛИНИКА else if R+r – t > 0 AND р — t > 0 then t.спасибо → Вр,t+1,r еlse (р.пожалуйста → Вр+1,t, r | i.свободен → Вр,t,r+1)).