Задача теории расписаний

Лекция 1 Лекции 1 Задача теории расписаний План лекции: 1) Введение 2) Задача теории расписаний 3) Статические и динамические задачи теории расписаний 4) Классификация задач теории расписаний 5) Формы представления расписаний 6) Исходные данные и искомые величины при составлении расписаний 7) Критерий расписания. Понятие регулярного критерия. В наиболее общей формулировке задача теории расписаний состоит в следующем: с помощью некоторого множества ресурсов или обслуживающих устройств должна быть выполнена некоторая система заданий (работ). Цель заключается в том, чтобы при заданных свойствах заданий и ресурсов и наложенных на них ограничениях найти эффективные алгоритмы упорядочения заданий, оптимизирующий или стремящийся оптимизировать некоторую меру эффективности. Задача теории расписаний считается заданной, если определены: 1) подлежащие выполнению работы и операции, из которых состоит каждая работа; 2) количество и типы машин, выполняющих операции; 3) порядок прохождения машин; 4) критерий оценки расписания. Задачи теории расписаний различаются числом выполняемых в системе работ, порядком поступления их в систему и порядком участия отдельных машин в выполнении конкретной работы. В зависимости от характера поступления работ различаются два вида задач: статические и динамические. В статических задачах в систему одновременно поступает определенное количество (число) работ. После этого новые работы не поступают, и расписание составляется для вполне определенного и известного заранее числа работ. В динамических задачах выполнение работ происходит непрерывно. Работы поступают в систему в некоторые моменты времени, которые можно предсказать только в статистическом смысле. Поэтому моменты появления работ не определены. Очевидно, что составление расписаний в статических и динамических системах различно. Порядок выполнения операций одной работы определяет, является ли система машин конвейерной. В конвейерной системе последовательность прохождения машин одинакова для каждой из работ. В противоположном случае существуют системы со случайным порядком выполнения работ машинами. Здесь отсутствует направленность прохождения машин, и в этом случае любая операция любой работы может выполняться равновероятно любой машиной. Для классификации задач теории расписаний часто используется запись в виде А│В│С│D. Здесь А – характеризует процесс поступления работ. Для динамических задач А представляет собой функцию распределения времени между поступлениями. Для статических задач А соответствует числу одновременно поступивших работ. Если на месте А стоит n, то это означает произвольное, но конечное число работ в статическим случае. В – характеризует число машин в системе. Если на месте В стоит m, то это означает произвольное число машин. С характеризует порядок выполнения работ машинами. Если на месте С находится F, то это соответствует конвейерной системе; если R- случайной, если G – произвольной. Для системы, состоящей из одной машины, порядок теряет смысл и этот параметр не указывается. D - характеризует критерий оценки расписания. Общая задача теории расписаний, решение которой до сих пор не получено, записывается в виде n│m│G│Fmax – упорядочить и работ в произвольной системе из m машин, так, чтобы минимизировать максимальную длительность прохождения работ. Формы представления расписаний На практике используются различные способы представления расписаний. Наиболее наглядны из них графические представления: диаграммы Ганта, ленточные графики, планировочные графики, циклограммы, учетные графики, сетевые графики и т.д. Планировочный график представляет собой схематическое изображение производственного процесса. Планировочный график строится следующим образом: для каждой работы в графике отводится отдельная строка. В этой строке пишется наименование работы и проводится линия, которая в соответствующем масштабе времени указывает длительность выполнения работы и ее привязку к календарю. № п.п. Наименование работы Месяцы 1 2 3 4 5 6 1 Работа 1 2 Работа 2 3 Работа 3 Ленточный график предназначении для учета времени на одну работу. Поскольку на каждую операцию работы отводится строго определенное количество времени, на графике все операции выстраиваются последовательно и против каждой операции ставится время, необходимое для ее выполнения, в виде отрезка ленты. № п.п. Операция Время, часы 1 2 3 4 5 6 … 1 Операция 1 2 Операция 2 3 Операция 3 4 Операция 4 5 Операция 5 Диаграммы Ганта представляют хронограмму, но в отличии от ленточного графика, не одной, а полного набора работ. Сетевые графики. На сетевом графике работы обозначаются стрелками, а углы указывают на очередность выполнения работ. Узел означает событие – момент завершения всех работ – стрелок, входящих в этот узел. Событие отдаляет время выполнения этих работ от времени выполнения стрелок – работ, выходящих из узла. Обычно информация к сетевому графику задается в виде таблиц. Пример сетевого графика Как ни бывают наглядны формы графического представления расписаний, все они обычно сопровождаются некоторыми таблицами с численными характеристиками. Во многих случаях табличное представление является более предпочтительным, чем графические формы представления. В теории расписаний широко используется форма представления расписаний посредством задания вектор-функций времени. Исходные данные при составлении расписаний Постановка задачи в теории расписаний начинается с описания системы машин и множества работ. Для простейшего процесса обслуживания система машин полностью описывается их числом. Будем считать, что каждая из m машин определяется соответствующим индексам 1,2,3, … , m. Работы нумеруются числами от 1 до n. ri – момент готовности – эта величина характеризует момент поступления i-й работы из некоторого внешнего источника; di – плановый срок. Эта величина представляет собой момент, к которому i-я работа должна быть закончена. Допустимая длительность прохождения работы в системе равна ai = di - ri Работа i состоит из gi операций. Для каждой операции задается набор следующих величин: mi1 , pi1 mi2 , pi2 …….. migi , pigi где mij – номер машины, на которой выполняется операция j ; pij - длительность выполнения операции, т.е. длина интервала времени, требуемого машиной mi для выполнения операции j. Тогда - общая длительность всех операций работы i. Искомые величины при составлений расписаний Обозначим через Wij интервал времени между окончанием (j-i)-й операции и j-й операции i-й работы. Тогда общая длительность ожидания для i-й работы равна сумме длительностей ожидания всех ее операций: Результатом составления расписания всегда является задание множества чисел Wij. Часто в качестве критерия составления расписания используются величинами, являющихся функциями Wij: 1) момент окончания работы; 2) длительность прохождения работы в системе 3) разница между плановым сроком и моментом фактического окончания работы. 1). Момент окончания i-й работы, или момент окончания ее последней операции: ci = ri+wi1+pi1+wi2+pi2+…+wigi+pigi = ri++ = ri+pi+wi 2). Длительность прохождения i-й работы в системе Fi = wi1+pi1+wi2+pi2+…+wigi+pigi = += pi+wi = ci- ri 3). Временное смещение i-й работы Li = ci – di = Fi - ai 4). Запаздывание Ti и опережение Ei i-й работы определяется следующим образом: Ti = max (O;Li) ; Ei = max (O;-Li) Временное смещение, запаздывание и опережение оценивают фактические время окончания работы по сравнению с ее плановым сроком. Временное смещение каждой работы может иметь любой знак. Если оно положительно (т.е. работа завершается после планового срока), то оно дает значение запаздывания, а если отрицательно (т.е. работа завершается до планового срока), то модуль опережения дает значение опережения. Расписание полностью описывается множеством Wij. два расписания одной и той же задачи тождественны, если их множества Wi5 идентичны. Однако, существуют задачи, когда желательно считать эквивалентными расписания, которые, строго говоря, не тождественны. Например, можно считать эквивалентными все расписания, у которых совпадают моменты окончания работ. Вообще, установление критерия оценки в теории расписаний означает задание множества эквивалентных классов и отношения предпочтения среди них. Например, принятие среднего значения времени окончания работ в качестве критерия оценки расписания означает: 1) Все расписания, у которых средние времена окончания работы с', эквивалентны, так что безразлично, какие из них выбирать. 2) Расписание со средним c' предпочтительнее чем расписание с'', тогда и только тогда, когда c'< с''. Расписание 3 является оптимальным, относительно некоторого критерия, если оно принадлежит к эквивалентному классу {S'} такому, что не существует какого-либо не пустого класса, который предпочтительней {S'}. Критерий М называется регулярным, если он является возрастающей функцией моментов окончания каждой из n работ M = f (с1, с2 … сn ). Такие критерии как средние и максимальные моменты окончания, средняя длительность прохождения, среднее или максимальное временное смещение, а также запаздывание – являются регулярными критериями. Критерию регулярности удовлетворяют и более сложные величины: взвешенные средние, смесь средних или максимальных значений. Такие величины как среднее или максимальное значение опережения, разность между максимальным и вторым по величине значением моментов окончаний, не являются регулярными критериями. Литература Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. – М.: Наука, 1975 Португал В.М., Семенов А.И. Теория расписаний. - М.: Знание, 1972 Танаев В.С., Шкурба В.В. Введение в теорию расписаний. - М.: Наука, 1975 Лекция 2 УПОРЯДОЧЕНИЕ КОНЕЧНОГО ЧИСЛА РАБОТ ДЛЯ ОДНОЙ МАШИНЫ План лекции: 1) Постановка задачи 2) Искусственные простои и прерывания. 3) Минимизация среднего времени пребывания работ в системе n|1 4) Соотношение между длительностью прохождения и средним числом работ в системе Постановка задачи Конечный поток требований поступает на обслуживание, в общем виде, в заданные моменты времени и обслуживается одним прибором. В каждый момент времени прибор обслуживает не более одного требования. Известны времена обслуживания каждого требования. Порядок обслуживания может быть произвольным, либо регламентироваться заданным отношением частичного порядка. Необходимо так организовать процесс обслуживания, чтобы он в том или ином смысле был наилучшим. В более сложных случаях могут оказаться полезными расписания, допускающие прерывание (когда выполнение работы прерывается до ее завершения, а позднее возобновляется после выполнения некоторой другой работы или ее части) и искусственные простои (когда прибор простаивает при наличии ожидающей выполнения работы). Например, пусть есть работы 1 и 2. тогда они могут выполняться следующим образом Прерываний и искусственных простоев нет 2 1 1 2 1 1 1 2 Если такие дисциплины обслуживания допустимы, то для решения задачи составления оптимального расписания выполнения работ, должно быть рассмотрено часто бесконечное количество вариантов. Однако рассмотрения вариантов с прерыванием и искусственно вводимыми простоями часто можно избежать в силу следующей теоремы. Теорема 2.1 Для систем n|1 (n задач, 1 обслуживающий прибор) расписание, оптимальное относительно регулярного критерия, принадлежащий классу расписаний, исключающему прерывания или искусственные простои. Доказательство. 1) Случай искусственных простоев. Рассмотрим расписание S, содержащее простои на отрезке времени от t1 до t2, где o ≤ t1 < t2 ≤ cmax . Существует расписание S', отличающееся от расписания S лишь тем, что машина не простаивает на отрезке [t1 ; t2] и все события, происходящие после t2, опережают соответствующие события S на t1 - t2 . При этом, очевидно, не изменяются моменты окончания работ, происходящие до t1, а для работ, оканчивающихся после t2 моменты окончания для S сдвигаются на t1 - t2. Очевидно, что сi' ≤ сi ; I = 1,2, … n , [сi – момент окончания i-работы] Так что значение регулярного критерия для S' не превосходит его значения для S. Поэтому оптимальное расписание принадлежит S', т.е. классу без простоев. 2) Случай прерываний. Рассмотрим расписание S, при котором работа I начинает выполняться в момент t1 и в момент t2, предшествующий ее окончанию, прерывается работой J. Для упрощения доказательства будем считать, что работа J не прерывается. В момент t3 работа I возобновляется и продолжается до ее полного завершения. Расписание S I J I t1 t2 с3 t3 сI Теперь рассмотрим расписание S', которое отличается от S тем, что первой выполняется работа J. J I I t1 cy' t2 t3 сI' В результате получим, что в S' раньше окончится только работа J, а момент окончания остальных работ не изменятся. Поэтому значение любого регулярного критерия для S' не превосходит его значения для S(S’≤S). Если в расписании S' выполнение работы I прерывается другими работами, то можно повторять описанную процедуру перестановки прерывающих работ перед I до тех пор, пока работа I не будет выполняться без прерываний. В результате всех этих перестановок регулярный критерий не увеличится. Отсюда следует, что оптимальное расписание принадлежит классу S' , т.е. классу, не содержащему прерываний. Основным результатом теоремы 1 является то, что поиск оптимального расписания должен проводиться в классе перестановочных расписаний. Для перестановочных расписаний в системе n|1 максимальная длительность прохождения равна сумме длительностей соответствующих работ. Эта величина зависит только от известных заранее длительностей работ и одинакова для всех n! возможных упорядочиваний. В более сложных системах максимальная длительность прохождения является основным критерием для оценки расписаний, но в данном случае она не зависит от порядка выполнения работ. Минимизация среднего времени пребывания работ в системе n|1 Средняя длительность прохождения n работ определяется следующим образом: , где F[k] время завершения работы, которая выполняется k-ой по счету. Теорема 2. Среднее время пребывания работ в системе n|1 минимально, если после упорядочивания длительности работ не убывают: P[1] ≤ P[2] ≤ … ≤ P[n] и максимально, если после упорядочивания длительности работ не возрастают, т.е. P[1] ≥P[2] ≥ … ≥ P[n] Доказательство где: P[1] – повторяется n-раз, P[2] – n-1 раз, P[3] – n-2 раза, P[i] – n-i+1 раз поскольку рассматриваются только перестановочные расписания, то длительность прохождений для работы, выполняемой k-ой Известно, что сумма по парных произведений членов двух числовых последовательностей имеет минимальное значение, если одна из этих последовательностей возрастает, а другая убывает. Так как коэффициенты (n-i+1) уменьшаются с увеличением i , то минимум F достигается в том случае, если P[i] с ростом i возрастают, или, по крайней мере, не убывают. Сумма по парных произведений элементов двух последовательностей максимальна, если эти последовательности упорядочены одинаково (либо по возрастанию, либо по убыванию). Отсюда следует, что для максимизации F работы должны выполняться в порядке уменьшения их длительности, или по крайней мере в порядке их не возрастания. Соотношение между длительностью прохождения и средним числом работ в системе Под средним числом работ в системе в течение интервала времени (t1,t2) понимается величина . Физически это можно трактовать следующим образом. Пусть есть один обслуживающий прибор (машина, процессор). В начальный момент времени обслуживания на нем ожидает некоторое количество заявок. Время исполнения (обслуживания) каждой заявки известно и новые заявки поступать не будут. Далее заявки обслуживаются в соответствии с некоторым расписанием. Тогда процесс обслуживания может быть представлен следующим образом. [1] P[1] [2] P[2] [3] P[3] [4] P[4] [5] P[5] [6] P[6] [7] P[7] Рис.1. Последовательность прохождения работ в системе Будем считать, что работы поступают в момент времени t=0, тогда среднее количество заявок в системе за все время выполнения работ График зависимости N(t) (рис.2) представляет собой ломаную линию и меняет свое значение n+1 раз. Тогда Рис. 2. График количества работ (заявок) в системе Чтобы пояснить это равенство, рассмотрим следующий пример. Пусть в системе имеется 3 задачи, т.е. n=3. Тогда следовательно Поскольку , где F – средняя длительность прохождения заявок, то Таким образом, отношение среднего числа работ в системе к максимальному числу работ равно отношению средней длительности прохождения к максимальной. Следовательно, для заданного времени действия расписания Fmax среднее число работ пропорционально (прямо пропорционально) средней длительности прохождения. Полученное соотношение справедливо для любого числа работ n, n≥1 при условии их одновременного поступления в систему и не зависят от: - числа или способа расположения машин; - характера работ, порядка их выполнения, длительностей выполнения или какой-либо другой информации о длительностях работ; - способа составления расписания. Упорядочивание в случае критерия с учетом веса В большинстве случаев выполняемые работы имеют разную важность, что должно отражаться при составлении расписания. Предположим, что для каждой работы заданы величины Ui , характеризующие ее относительную важность. Используем эти величины в критерии оценки расписания. Тогда взвешенную среднюю длительность прохождения можно определить следующим образом: Теорема 3. Минимальное значение суммарной взвешенной длительности прохождения в системе n|1 достигается в расписании, для которого Доказательство Рассмотрим расписание S, не входящее в класс расписаний, сформированных в порядке возрастания отношения . Тогда в S существует такая позиция K, что . Пусть К и К' – номера работ, выполняемых соответственно в К-ой и К+1 позициях расписания S. Пусть S' – расписание, отличающееся от S только тем, что работы К и К' выполняются в S' соответственно в (К+1) и К-позициях. S К К' S' К' К Первые (К-1) и последние (n-K-1) работ оканчиваются в одно и тоже время в обоих расписаниях, и поэтому вносят одинаковый суммарный вклад в суммарную взвешенную длительность прохождения. Расписания S и S' отличаются только длительностями прохождения работ К и К'. Если , то эти длительности, взвешенные соответствующим образом, имеют следующий вид: Для расписания S: Для расписания S': . После исключения общих членов получаем, что член UK' , РK существует для S и отсутствует для S', а член UK РK’ существует для S' и отсутствует для S. Поскольку К и К' были выбраны так, что , то расписание S' лучше чем расписание S. Одним из естественных и часто используемых на практике правил при наличии весов является формирование очередности с учетом только весов: u[1]≥ u[2]≥… ≥ u[n]. Если в качестве критерия выбрана средняя взвешенная длительность прохождения, то такое упорядочивание приводит к следующим результатам: 1. Если длительности всех работ одинаковы, то упорядочивание в соответствии с весами совпадает с упорядоченностью в соответствии с отношением P/u и является оптимальным. 2. Если веса прямо пропорциональны длительностям, т.е. ui=KPi, то отношения P/u одинаковы для всех работ u, следовательно, все расписания эквивалентны. 3. упорядочивание в соответствии с уменьшением u приводит в общем случае к меньшему значению средней взвешенной длительности прохождения, чем случайное упорядочивание. Литература Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. – М.: Наука, 1975 Танаев В.С., Шкурба В.В. Введение в теорию расписаний. - М.: Наука, 1975 Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы. – М.: Наука, 1984 Лекция 3 Лекция 3 Упорядочение в соответствии с плановым сроком План лекции: 1) Понятие планового срока 2) Теорема Джексона 3) Резерв времени Из возможных критериев оценки расписания наиболее важным с точки зрения приложений является критерий своевременного выполнения работ. Плановым (директивным) сроком называется момент времени Dk к которому необходимо, или, по крайней мере, желательно, завершить обслуживание K=1…n требования (работы). В общем случае не удается построить такого расписания, при котором выполнение каждой работы завершается не позднее заданного планового срока Dk . Появляется объективная необходимость в нарушении отдельных директивных средств, что сопряжено с определенными потерями. Эти потери зависят от того, какие именно задачи и насколько задерживаются с выполнением. Иными словами, каждой задаче K=1…n ставится в соответствие кусочно-непрерывная функция штрафа φk(x) > 0, если X>Dk. Требуется определить расписание выполнения n-работ, при котором суммарный штраф наименьший. Поскольку оценкой расписания служит нарушение планового срока, естественно ожидать, что упорядочивание должно осуществляться с учетом информации о плановых сроках di. Теорема 3.1. (Джексон) Расписание, минимизирующее максимум временного смещения и максимум запаздывания работ в системе n|1| Lmax (максимум временного смещения) таково, что работы выполняются в порядке не убывания плановых сроков d[1]≤ d[2] ≤…≤ d[n]. Доказательство Рассмотрим расписание S, не принадлежащее классу расписания с неубывающими плановыми сроками. Тогда в S существует такое К, что d[К]≤ d[К+1]. Пусть К и К' – номера работ соответственно в К-й и (К+1) функциях расписания S. Теперь рассмотрим расписание S', которое отличается от S только перестановкой очередности работ К и К', т.е. в S' работа К' выполняется К-й, а работа К выполняется (К+1)-й. В обоих расписаниях порядок выполнения (К-1) первых и (n-к-1) последних работ один и тот же. Кроме того, очевидно, что в обоих расписаниях начало и окончание выполнения этих (n-1) работ совершенно одинаков. Поэтому временной смещение для них одно и тоже. Пусть максимум этого смещения L. Оба расписания отличаются лишь временными смещениями работ К и К'. Нам нужно показать, что max (L, Lk, Lk’) в S' меньше или равен максимуму тех же величин в S. Если max (L, Lk, Lk’)=L, то оба расписания будут эквивалентны. Поэтому предположим, что максимум равен LK или LK' , и докажем, что теорема верна в этом случае. Если эта величина одинакова в S и S', что соответствующие временные смещения имеют следующий вид: Временное смещение: Li = ci - di = Fi-ai ci - момент di - плановый срок, Fi -длительность прохождения работы, ai – допустимая прохождения работы в системе. Отсюда следует, что LK’(S) > LK(S’), т.к. dK > dK’ LK’(S) > LK’(S’), т.к. PK > 0 LK’(S) > max(LK(S’), LK’(S’); max {L, LK(S), LK’(S)}≥ max{L,LK(S’), LK’(S’)} Таким образом, для любого расписания S существует возможность его улучшения путем попарной перестановки соседних работ так, чтобы работы выполнялись в порядке, обратном их плановым срокам. Информацию, содержащуюся в наборе величин {d:} можно использовать иначе, а именно производить упорядочение в соответствии с резервом времени для каждой работы. Резерв времени работы i в момент t равен di-pi-t и представляет собой максимально допустимую длительность ожидания, при которой не произойдет задержки. Работа с минимальным резервом времени имеет, судя по всему, больше шансов быть задержанной, поэтому при установлении очередности она должна иметь преимущества. Поскольку время t является общим для всех работ, то упорядочивание должно быть следующим: d[1]-p[1] ≤ d[2]-p[2]≤ … ≤d[n]-p[n] Интуитивно кажется, что упорядочение такого вида является некоторым улучшением расписания, полученного в соответствии с плановыми сроками, и в ряде сложных случаев должно улучшать характеристики системы. Однако, имеет место несколько неожиданный результат, содержащийся в следующей теореме. Теорема 3.2. Расписание, максимизирующее минимальное временное смещение и минимальное запаздывание работ в системе n|1 таково, что работы выполняются в порядке не убывания резерва времени. Доказательство в точности повторяем доказательство предыдущей теоремы. Используя те же обозначения получим: LK(S) < LK'(S’), т.к. (dK –pk)> (dK’ –pK’) LK(S) < LK(S’), т.к. PK’>0 LK(S) < min{(LK’(S’), LK(S)}. Пусть L – минимальная задержка (n-2) работ. Тогда: min {L,LK(S) LK’(S)}≤ min{L,LK’(S’), LK(S’)}, т.е. теорема доказана. Используя доказанные теоремы можно строить расписания, минимизирующие максимальные значения запаздывания или максимизирующие минимальное запаздывание. Однако, ни одно из рассмотренных правил не минимизирует среднее запаздывание. Пусть упорядочение в соответствии с плановым сроком приводит к нулевому значению максимума запаздывания. Вообще говоря, для этой задачи может существовать другое расписание, при котором максимум запаздывания также равен 0, но которое по ряду причин предпочтительнее упорядочивания в соответствии с плановым сроком. В частности, если наряду с минимизацией максимального временного смещения стремятся минимизировать среднюю длительность прохождения, то упорядочение должно осуществляться в соответствии со следующей теоремой. Теорема 3.3. [Смит]. Если для системы n|1 существует такое упорядочение, что максимальное запаздывание работ равно 0 , то существует упорядочение с работой К в последней позиции, которое сохраняет нулевым максимальное запаздывание и одновременно минимизирует среднюю длительность прохождения тогда и только тогда, когда: а) ; в) Pk ≥ Pi , при таких I, что т.е. работа выполняется последней, если только это не приводит к ее запаздыванию и если ее длительность максимальна среди всех работ, выполнение которых в последнюю очередь приводит к запаздыванию. Доказательство. Рассмотрим расписание со следующими свойствами: 1) Максимальное запаздывание равно 0; 2) Работа К, выполняемая последней, удовлетворяет условиям теоремы 3.3. Теперь покажем, что всякое перемещение работы К с последнего места приводит к ее запаздыванию и (или) к увеличению средней длительности пребывания. Заметим, что не существует другой работы J, выполняемой раньше, чем К и удовлетворяющей условиям а) и в) теоремы, если только PJ ≠ Pk. Если PJ = Pk, то безразлично, какая из работ выбирается последней. Теперь, если J не удовлетворяет условию а) теоремы, то ее перестановка с К приводят к образованию не нулевого запаздывания для J, что противоречит предположениям теоремы. Если J не удовлетворяет условию в), т.е. PJ < Pk то перестановка J с K приводят к возрастанию суммарной длительности прохождения работ. Если J находилось в позиции (n-V), суммарная длительность прохождения увеличится на V(Pk - PJ). Окончательный вид расписания, минимизирующего среднюю длительность прохождения при наличии плановых сроков, получается рекуррентно, путем выбора последней, предпоследней и т.д. работ. Это происходит следующим образом. Из совокупности работ, для которых плановые сроки превосходят или равны суммарной длительности всех работ, выбирается работа с наибольшей длительностью. Эта работа выполняется последней. После того, как выбрана работа, время окончания работы [n-1] находится так: . Теперь из совокупности работ, для которых плановые сроки превосходят или равны С[n-1], выбирается работа максимальной длительности. Эта работа выполняется (n-1)-й и т.д. Пример. Рассмотрим систему G|1 Работа 1 2 3 4 5 6 di 24 21 8 5 10 23 Pi 4 7 1 3 2 5 Для этой системы упорядочение по плановым срокам приводит к нулевому значению максимального распознавания, но это упорядочение может быть улучшено с помощью теоремы 3.3. Суммарная длительность всех работ равна 22. из них только первая и шестая имеют плановый срок больший 22, поэтому последней должна быть выбрана одна из них. Это будет работа 6, т.к. Р6>Р1. исключив из рассмотрения работу 6, устанавливаем, что суммарная длительность оставшихся работ равна 17. из пяти работ только работы 1 и 2 могут быть выбраны последними. выбираем вторую работу. Продолжая описанную процедуру дальше, получим следующую последовательность работ: 3,4,5,1,2,6. d[1]≤d[2]≤d[3]≤…≤d[n] S не принадлежащее классу расписаний, определяемому теорией, тогда в нем существуют работы А и В, выполняющие в позициях К и К’, такие, что d[K]=dA>d[K+1]=dB S’ – отличается от S тем, что работа А выполняется на К-позиции, а В – в К+1 А В B A Очевидно, что не n-2 работы, кроме А и В в обоих расписаниях выполняются одинаково. Пусть L – максимальное временное смещение в n-2 работ. тогда max временное смещение в расписании S: max (L,LA(S),LB(S)), а в расписании S' max (L,LA(S'), LB(S’)), чтобы доказать теорему достаточно показать, что max (L,LA(S),LB(S)) > max (L,LA(S'), LB(S’)). Если: L > LA(S) и L > LB(S) и L >LA(S') и L1> LB(S’), то перестановка таких работ А и В ничего не изменяет и надо выбрать другую меру работ. Пусть в нашем случае это не так. Тогда: LA(S) = t + PA – dA S: LB(S) = t + PA + dB LB(S’) = t + PB – dB S’: LA(S’) = t + P3 + PA – dA LB(S) > max (LA(S'), LB(S’)) LB(S) > LA(S'), т.к. dB < dA LB(S) > LB(S'), т.к. PA > 0 Литература Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. – М.: Наука, 1975 Танаев В.С., Шкурба В.В. Введение в теорию расписаний. - М.: Наука, 1975 Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадиные системы. – М.: Наука, 1984 Лекция 4 Лекция 4 Упорядочение при наличии ограничений на возможные варианты расписаний План лекции: 1) Составление расписаний при частичной упорядочении работ 2) Составление расписания при заданном отношении предшествования Ранее предполагалось, что приемлема любая из возможных последовательностей выполнения работ, поэтому выбиралась та, которая обеспечивает лучшее обслуживание при заданном критерии качества. На практике чаще встречаются случаи, когда определенные последовательности выполнения работ запрещены по тем или иным обстоятельствам. Составление расписаний при частичном упорядочении Рассмотрим случай, когда составляется расписание для частично упорядоченных работ. Это частичное упорядочение могут быть обусловлено различными причинами. Например, оно может быть вызвано зависимостью длительности перенастройки оборудования от очередности выполнения работ. В этом случае работы разбиваются на группы с приблизительно равной настройкой, после чего для группы составляется расписание, минимизирующие некоторый критерий (например, среднюю длительность прохождения). Очередность внутри групп устанавливается таким образом, чтобы минимизировать общую длительность перенастройки машины. Предположим, что исходные n работ разбиты на К групп с числом работ n1,n2,…nK в каждой группе. Предположим также, что состав групп и очередность работ в группе фиксированы и что переход к следующей группе возможен только после того, как выполнены все работы предыдущей группы. Требуется выбрать один из возможных способов упорядочения групп. Введем следующие обозначения. Pij – длительность выполнения работы j в группе i; Fij – длительность прохождения работы j в группе i; - общая длительность всех работ i-группы; F’i = Fi,ni - длительность прохождения i-группы, равная длительности прохождения последней работы в ней. Если расписание должно минимизировать среднюю длительность прохождения группы, т.е. , то нужно рассматривать каждую группу как работу длительностью и применить алгоритм упорядочения в соответствии с минимальной длительностью. То есть группы упорядочиваются так: P’[1]≤ P’[2] ≤ …≤P[K]. Теорема 4.1. Если в системе n|1|F работы разбиты на К непересекающихся групп, и пусть выполнение работ внутри группы и переход от группы к группе осуществляется без настроек, а порядок выполнения работ внутри каждой группы фиксирован. Тогда средняя длительность прохождения работ минимальна, если порядок выполнения групп таков, что отношение суммарной длительности всех работ группы к числу работ в ней не убывает, т.е. Доказательство Обозначим через hij интервал времени между окончанием работы j из группы i и завершением всех работ i-й группы. Тогда и Для каждой работы величина hij постоянна и определяется условиями задачи, поскольку она зависит только от длительности работ и очередности работ внутри группы: Fij = Fi’ – hij Поскольку второй член в правой части – постоянная величина, не зависящая от очередности групп, а первый член минимизируется порядком, устанавливаемым теорией, то теорема доказана. Составление расписания при заданном отношении предшествования Частичное упорядочивание работ желательно задавать менее жестко, чем сделано ранее. Подобные отношения можно установить, используя понятия предшествования, непосредственного предшествования или преимущественного графа. Предположим, что нужно выполнить три работы а,b,с. Если не накладывать никаких ограничений на порядок их выполнения, то возможны 6 различных вариантов (3!). Если наложить ограничение, например, в форме «в предшествует с», то возможны следующие варианты (их 3): 1) а b с 2) b а с 3) b с а Рассмотрим более общий случай, когда n работ разбиты на К цепочек. Это значит, что отношения предшествования определяют для каждой работы не более одной предшествующей и не более одной последующей. Например: При наличии таких ограничений упорядочение, минимизирующие среднюю длительность прохождения, определяется следующей теоремой. Теорема 4.2. пусть для системы n|1|F без настроек заданы отношения предшествования между определенными парами работ так, что для каждой работы существует не более одной предшествующей и одной последующей. Пусть в результате этого множество разделяется на К непересекающихся цепочек, внутри каждой из которых задана последовательность выполнения работ, причем допускается прерывание цепочек. Тогда средняя длительность прохождения минимизируется упорядочением, устанавливаемым следующим образом: 1) для каждой работы j в i-цепочке вычисляется 2) для каждой цепочки вычисляется т.е. hi – второй индекс минимальной из величин ; 3) выбирается такая цепочка I, что yI(hI) ≤ yi(hi), для всех i и первые hI работ в цепочке I формируют начало очередности выполнения работ; 4) вычисляются заново величины yi без учета первых hI работ цепочки I; 5) третий и четвертый шаги повторяются до тех пор, пока не будут упорядочены все работы. Доказательство Алгоритм, сформулированный в теореме, упорядочивает, вообще говоря, К ≥ k частей цепочек. При этом механизм упорядочивания таков, что размещение в расписании второй части цепочки не производится, пока не установлено место первой ее части, гарантирующее соблюдение заданных соотношений предшествования внутри цепочки. Если бы части цепочек представляли собой группы, которые не прерываются, то оптимальный алгоритм задавался бы предыдущей теоремой. Поэтому нужно показать, что сформулированные частичные цепочки фактически можно рассматривать как группы работ, т.е. что прерывание любой из них не улучшает обслуживания. Рассмотрим часть ''b'' некоторой цепочки, сформированную по алгоритму теоремы и содержащую nb работ. Пусть , где - среднее время выполнения работы в подцепочке, - число работ в подцепочке, - время выполнения подцепочки. Работы в подцепочке b упорядочены следующим образом: (b,1), (b,2), … , (b,ub). Прерывание цепочки b означает ее разбиение на две более мелкие части b' и b'': b’ = (b,1), (b,2), … , (b,i) b’’ = (b,i+1), (b,i+2), … , (b,hb) каждая из этих новых частичных цепочек имеет свое отношение суммарной длительности работ к их числу ; и разместилась бы в упорядочении (по теореме 4.1) в соответствии со значениями и. Нужно показать, что подобное разбиение подцепочки ''b'' не разумно, поскольку частичная цепочка b' должна будет непосредственно предшествовать b'' и структура b останется неизменной, в силу чего b может рассматриваться как непрерываемая группа. Покажем что . Неравенство следует из построения в соответствии с алгоритмом теоремы: > Умножив обе части этого неравенства на , получим: . Прибавляя к обеим частям последнего неравенства величину получим: отсюда следует, что разбиение любой частичной цепочки, сформированной алгоритмом теоремы, на две приводит к тому, что полученные две частичные цепочки не удовлетворяют отношению порядка, устанавливаемому по минимуму величин y, а поменять их местами нельзя в силу условий предшествования работ в цепочке b. Покажем теперь, что перемещение b' вперед или b'' назад нецелесообразно. Пусть в исходном расписании a и c – частичные цепочки, первая из которых предшествует b, а вторая следует за b, т.е. . Ясно, что цепочка b' не может быть размещена перед а, т.к. . Она не может быть продвинута и дальше вперед, поскольку для любой частичной цепочки, предшествующей а, значение y не превосходит ya. b' - нельзя разместить и внутри а, разделив а на две более мелкие частичные цепочки, т.к. , и b' нельзя расположить впереди a''. Аналогично доказывается, что b'' нельзя разместить внутри или после с. Пример Составления расписания для частично-упорядоченных работ в системе n|1|F 1. Вычислим yi,j для каждой работы каждой цепочки. Для цепочки 1 Для цепочки 2 Для цепочки 3 2. Вычислим для каждой цепочки yi и xi 3. То есть в выходное расписание помещаем работу a из первой цепочки. Поскольку работу а в дальнейшем учитывать не будем, то перечитаем В выходное расписание помещаем работы с начала третьей цепочки до работы h (т.е. работы g и h). После исключения этих работ 3 цепочки – она заканчивается и в дальнейшем ее можно не рассматривать. В расписание помещаем работы из 1 цепочки до c включительно, т.е. работы в-с. Первая цепочка исчерпана. Поскольку осталась одна цепочка, последовательность работ в которой поменять нельзя, то выносим ее целиком в выходное расписание. Расписание Сравним полученное F c F какого-нибудь произвольного расписания, например, с расписанием что больше, чем F для оптимального расписания. Литература Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. – М.: Наука, 1975 Танаев В.С., Шкурба В.В. Введение в теорию расписаний. - М.: Наука, 1975 Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадиные системы. – М.: Наука, 1984 Лекция 5 Лекция 5 Расписания для систем конвейерного типа План лекции: 1) Конвейерные системы 2) Регулярный критерий и расписания для конвейерных систем 3) Минимизация максимальной длительности прохождения в конвейерной системе из двух машин (n|2|F|Fmax). Алгоритм Джонсона Довольно часто работа состоит из последовательности операций, каждая из которых выполняется соответствующим устройством. В этих случаях говорят, что совокупность устройств является системой конвейерного типа, если машины занумерованы так, что для каждой рассматриваемой работы операция К выполняется машиной с большим номером, чем операция J в том случае, если операция J предшествует операции К. Для конвейерной системы не обязательно, чтобы каждая работа состояла из операций, выполняемых на каждом устройстве, или все работы начинались или заканчивались определенными машинами. Существенно лишь, что все перемещения работы связанные с окончанием ее на одной машине и началом выполнения на другой, должны происходить в одном направлении. Определенная простота системы с одной машиной была обусловлена тем, что для нее рассматривались только перестановочные расписания. Такие расписания полностью определены, если задана подстановка индексов работ. В общем случае составление расписания наталкивается на значительные трудности, вызванные тем, что приходится рассматривать более широкие классы расписания. Конвейерная система занимает промежуточное положение, поскольку во многих случаях достаточно рассматривать только перестановочные расписания, а в других – расписания других классов. Теорема 5.1 Если составляется расписание для системы n|m|F и все работы доступны одновременно, то оптимальное с точки зрения регулярного критерия, расписание принадлежит классу расписаний, в которых одинаков порядок выполнения работ на первых двух машинах. Доказательство Если в расписании порядок выполнения работ на первых двух машинах различны, то найдется такая пара работ I и J что на первой машине I непосредственно предшествует J, а на второй I следует за J (причем между I и J возможны промежуточные работы). Машина 1 ……… I J …………… Машина 2 J … I … Очевидно, что порядок выполнения этих двух работ первой машиной можно изменить на обратный, не вызывая дополнительного временного сдвига в начале выполнения любой работы второй машиной и, следовательно, всех последующих. Такая перестановка не приводит к возрастанию времени окончания любой работы и не ухудшает регулярный критерий. Может случиться, что в результате такой перестановки начала выполнения некоторых работ второй машиной сместятся влево на временной оси и регулярный критерий улучшится. Однако, отсутствие ухудшения критерия уже достаточно для доказательства теоремы. Для конкретных критериев можно получить более строгий результат. Теорема 5.5. Если составляется расписание для системы n|mF|Fmax и все работы доступны одновременно, то оптимум ищется среди расписаний, в которых сохраняется порядок выполнения работ на двух первых (1,2) и двух последних машинах (m-1,m). Доказательство Первая часть теоремы является следствием теоремы 5.1 т.к. максимальная длительность прохождения Fmax является регулярным критерием. Предположим, что порядок прохождения работ различен для двух последних машин. Тогда найдется такая пара работ I и J, что для машины из I непосредственно следует за J, а для машины (m-1) работа I предшествует J (причем между I и J возможны другие работы). Машина m-1 I … J … Машина m … J I … Очевидно, что порядок выполнения работ J и I машиной m можно изменить на обратный, не увеличивая максимальной длительности прохождения этих работ и не изменяя длительности прохождения других работ. Кроме того, весьма вероятно, что изменение порядка выполнения работ J и I может привести к уменьшению максимальной длительности прохождения, что и доказывает теорему. Результаты теоремы 5.2 нельзя обобщить на случай произвольного регулярного критерия. Предположим, что составляется расписание для двух работ, выполняемых тремя машинами. Расписание должно минимизировать среднюю длительность прохождения. Машины 1 2 3 (I) Работа 1 4 1 1 (J) Работа 2 1 4 4 Существуют два расписания с одинаковым порядком работ на машинах 2 и 3 и одинаковыми средними длительностями прохождения – 9,5. Расписание 1 Машина 1 I J Машина 2 I J Машина 3 I J Расписание 2 Машина 1 J I Машина 2 J I Машина 3 J I Наряду с этим существует расписание с различным порядком прохождения работ на машинах 2 и 3 средней длительностью прохождения равной 9 Машина 1 J I Машина 2 J I Машина 3 I J Оказывается, что для произвольного регулярного критерия (например, средней длительности прохождения) конвейерная система из двух машин является единственным случаем, когда достаточно рассматривать перестановочные расписания. Минимизация максимальной длительности прохождения в конвейерной системе из двух машин (n|2|F|Fmax) Оценка нижней грани максимальной длительности прохождения. Расписание может быть представлено в следующем виде: Машина 1 А[1] A[2] … A[n] Машина 2 B[1] B[2] … B[n] т.к. B[n] не может прерываться с А[n], то последняя работа не может быть завершена до окончания всех работ машиной 1,т.к. С другой стороны работы B[n] не может закончиться раньше, чем прохождение всех работ на машине 2. поскольку А[1] не прерывается с B[1], то Заметим, что и не зависят от расписания, а определяются только по исходным данным. Поэтому уменьшить оценки Fmax можно только за счет уменьшения А[1] и B[n] с помощью соответствующего упорядочения. Для этого нужно наименьшее А из {Ai, i=1 … n} и наименьшее B из {Bi; i=1 … n}. Если A0, то X [2] = max(A[1]+A[2]-B[1]-X[1];0) X [3] = max(A[1]+A[2]+A[3]-B[1]-B[2]-X[1]-X[2];0)= Тогда в общем случае: Теперь будем последовательно находить частичные суммы X[i]. X[i] = A[1]; X[1]+X[2]= max(A[1]+A[2]-B[1]; A[1]); (т.к. если B[1]>A[1]+A[2] X[1]+X[2] не может быть меньше X[3], т.е. A[1]) X[1]+X[2]+ X[3]= max(A[1]+A[2]+A[3]-B[1] -B[2]; X[1]+X[2])= max(A[1]+A[2]+A[3]-B[1] -B[2]); max(A[1]+A[2]-B[1]; A[1])= ; Или в общем случае: Обозначим Тогда Поскольку в оптимальном расписании , то необходимо найти пусть теперь необходимо в позициях J и J+1 расположить задачи j и j+1. Тогда в соответствии с условием теоремы следовательно . Рассмотрим величиныи . Обе они не зависят от расписания. Следовательно, величина не зависит от расписания. Добавим значение этого выражения к левой и правой части неравенства (*). Левая часть неравенства если , то Если , Таким образом , если j стоит в позиции J. Правая часть неравенства , если если Тогда, если расписание составлено в соответствии с условиями теоремы, то: То есть минимум максимума Y достигается, если работы упорядочены в соответствии с теоремой. Транзитивность отношения В случае равенства все очевидно. Рассмотрим неравенства: Пусть S – некоторое расписание Машина 1 A[1] A[2] A[3] A[4] Машина 2 x1 B1 x2 B[2] A[3] B[4] Тогда , где X[i] – время простоя перед [i] работы второй машиной. Значение X[i] : X[1]=A[1] X[2]= max(A[1]+A[2]-B1-X[1];0); X [3] = max(A[1]+A[2]+A[3]-B1-B2-X1-X2;0); Рассмотрим суммы частичных сумм: X[1]=A[1] X[1]+ X[2]= max(A[1]+A[2]-B1-X[1]+ A[1]; A[1])= max(A[1]+A[2]-B[1]; A[1]); X[1]+ X[2]+X [3] = max(A[1]+A[2]+A[3]-B[1]-B[2; X[1]+ X[2])= ; - не зависит от того, какая из работ выполняется J: j или j+1 - не зависит от того, какая из работ выполняется на 3 месте. Следовательно * - не зависит от того, какая работа j или j+1 выполняется J-ой. (**) прибавим к левой части (**), тогда 1) Если :: = 2) Если : = При размещении работы на месте J работы j прибавим (*) к правой части (**) Если , то Если Определим при J=1 Y1=A1!! Тогда поскольку и не зависит от расписания, оптимальным будет расписание, для которого достигается . Предположим, что в формируемом расписании заполняются J и J+1. Причем на место J помещаются или работа j или работа j+1, а на место J+1 – оставшаяся работа. Если на J место помещается работа j, то в соответствии с теоремой , следовательно Рассмотрим величину . значение этой величины не зависит от того, какая работа j и j+1 выполняется в позиции J, а какая в J+1 и - еще не начались т.к. не зависят от расположения работ j и j+1, то и - не зависит от расстановки этих работ. (**) если на месте J размещается работа j, то прибавим (*) к левой и правой частям (**), т.е. (возможны два варианта)→ 1) 2) т.е. левая часть (**) может быть записана : при размещении работы j в позиции J. Литература Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. – М.: Наука, 1975 Танаев В.С., Шкурба В.В. Введение в теорию расписаний. - М.: Наука, 1975 Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадиные системы. – М.: Наука, 1984 Теория расписаний и вычислительные машины / под. ред. Э.Г. Коффмана. - М.: Наука, 1984. Лекция 6 Лекция 6 Оптимальные расписания для системы n|M|F|Fmax План лекции: 1) Система n|M|F|Fmax 2) Решение задачи с помощью метода ветвей и границ Задача построения оптимального по быстродействию расписания последовательного обслуживания n требований М приборами существенно усложняются при переходе к М>2. В этом случае последовательность обслуживания требований одним прибором при оптимальном расписании в общем случае отличается от последовательности их обслуживания другими приборами. В частности, если М=3, то оптимальное расписание можно искать в классе расписаний, когда каждый прибор обслуживает требования в одной и той же последовательности. Если М≥4, то требования в приборах могут обслуживаться в разных последовательностях. Ограничимся рассмотрением ситуаций, все требования обслуживаются каждым прибором в одной и той же последовательности. Если при этом потребовать, чтобы каждый прибор поступал к обслуживанию очередного поступающего к нему требования сразу же после завершения обслуживания предыдущего, то расписание однозначно определяется заданием последовательности π=([1],[2],…,[n]) обслуживания требований. Если требования обслуживаются каждым прибором в последовательности π , то момент начала обслуживания [1] прибором 1 равен , а требования . Аналогично: время начала обслуживания требования [1] L-прибором: . Тогда время начала обслуживания [k]-требования прибором L: , т.е. есть максимум между временем завершения предыдущим прибором [k] и завершением предыдущей задачи L-прибором. Здесь: - момент завершения обслуживания требования [k] прибором L. Обозначим через Т(π) наименьшее общее время обслуживания всех требований при обслуживании их каждым прибором в последовательности π. Очевидно, что . Зависимость Т(π) от t[k]L и π можно записать в виде: . Нас будут интересовать вопросы, связанные с построением последовательности π*, которой соответствует минимальное значение Т(π). Определенные практический интерес представляют ситуации, в которых необходимо соблюдать одно из двух дополнительных условий – каждый прибор должен обслуживать требования непрерывно одно за другим или каждое требование должно обслуживаться непрерывно одним прибором за другим. В первом случае общее время обслуживания равно Во втором случае время обслуживания равно Величину T''(π) можно рассматривать в качестве длины гамильтонова цикла (0;π;0) в полном графе с вершинами {0;1;…;n}, если длины lij его дуг (iij) положить: L0,j=0; . Следовательно, для построения последовательности с min T''(π) достаточно решить соответствующую задачу коммивояжера. Решение задачи с помощью метода ветвей и границ В основе методом последовательного конструирования, анализа и отсеивания вариантов лежит идея пошагового построения решения. Если при таком последовательном конструировании на основании некоторых свойств решения можно ввести понятие «доминирования» одних вариантов над другими, «перспективности» одних вариантов по сравнению с другими, оперируя отельными построенными частями этих вариантов, то тогда удается разработать относительно простые вычислительные схемы нахождения оптимального варианта. Процесс построения искомой последовательности π можно представить как процесс пошагового развития частичной (возможно пустой) последовательности σ обслуживание некоторых требований из N до некоторой последовательности π обслуживания всех требований N подобное развитие может проводиться по различным направлениям путем приписывания справа различных элементов из N. Естественно, что дальнейшему развитию должно подвергаться та из рассматриваемых на данном шаге частичных последовательностей, развитие которой представляется наиболее перспективным. Способы оценки перспективности частичных последовательностей в рассматриваемом случае весьма разнообразны. Они отличаются друг от друга как по сложности, так и по точности вычисляемых оценок. В схемах последовательного анализа вариантов выбор того или иного метода обусловлен двумя противоречивыми обстоятельствами. 1). Уточнение оценок позволяет, как правило, сократить процесс ветвления. 2). Всякое уточнение оценки сопряжено с увеличением объема вычислений, что может привести к компенсации выигрыша, получаемого от сокращения процесса ветвления. Описание одного из методов вычисления оценок приведем для М=3. Обобщение на случай M>3 не вызывает особых затруднений. Обозначим приборы через А, В и С. Каждая [k]- я задача обслуживается прибором a[K]L, b[K]L и c[K]L соответственно единиц времени. Если требования некоторого множества обслуживаются в последовательности , а остальные требования обслуживаются в последовательности , то общее обслуживание всех требований равно: Прибор А завершает обслуживание требований множества в момент времени Прибор В завершает обслуживание требований множества в момент времени Прибор С завершает обслуживание требований множества в момент времени Определим оценку γ(σ) следующим образом: В результате некоторого усложнения этих выражений можно получить и более точную оценку. Конструирование оптимальной последовательности включает построение частичных последовательностей, оценку этих последовательностей, выбор для последующего развития наиболее перспективной частичной последовательности и развитие по возможным направлениям. Этот процесс является, по существу, процессом последовательного разбиения множества всех n! Возможных перестановок на подмножестве и вычисления нижних оценок значений оптимизируемой функции на каждом из этих подмножеств. При этом к одному подмножеству относятся все перестановки, начинающиеся с одной и той же частичной перестановки. Конструирование оптимальной последовательности завершается поступлением ситуации, в которой окажется построенной некоторая перестановка π*, и значение Т(π*) будет не больше оценок γ(σ) для всех рассматриваемых на данном шаге множеств перестановок вида (σ';σ''). Пример Пусть требуется построить оптимальное Fmax расписание обслуживания пяти требований тремя приборами А, В, С. Времена обслуживания каждой задачи каждым прибором приведены в таблице. Прибор Задача 1 2 3 4 5 А 5 4 7 2 3 В 8 4 1 8 5 С 1 9 4 4 1 Рассмотрим 5 множеств перестановок вида σ' – произвольная перестановка элементов множества N\σ, где N={1,2,3,4,5}. Каждое из этих множеств содержит 4!=24 перестановки. Вычислим оценки для всех возможных задач. Если в качестве 1 элемента создаваемой последовательности выступает задача 1, то оценка для нее: (т.е. σ={1}): т.е. γ(σ) =32. Аналогично вычисляем оценки для других задач при размещении их в 1 позиции расписания: γ(2)=31; γ(3)=34; γ(4)=29; γ(5)=30 Выбираем перестановку с наименьшим значением оценки: σ(4). Построим текущее состояние дерева решений. Рассмотрим теперь четыре множества перестановок вида (σ;σ'): (4,1);(4,2);(4,3);(4,5). Каждое из этих множеств содержит 3!=6 перестановок. Вычислим γ(4,1). γ(4,2)=29. Аналогично: γ(4;,12)=36; γ(4,2)=29; γ(4,3)=29; γ(4,5)=30, следовательно, дальнейшему развитию можно подвергнуть перестановки (4;2) и (4;3). Выберем для определенности (4;2). Весь процесс ветвлений может быть представлен следующими рисунками: Найдена подстановка π*=(4;2;1;3;5), которой соответствует Т(π*) не большее нижних оценок значений Т(π) на остальных множествах перестановок. Следовательно, выполнение задач в последовательности π*дает оптимальное по быстродействию расписание. Диаграмму Ганта полученного π*составить самостоятельно. Литература Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. – М.: Наука, 1975 Танаев В.С., Шкурба В.В. Введение в теорию расписаний. - М.: Наука, 1975 Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадиные системы. – М.: Наука, 1984 Теория расписаний и вычислительные машины / под. ред. Э.Г. Коффмана. - М.: Наука, 1984. Лекция 7 Лекция 7 Параллельные устройства План лекции: 1) О сложности задачи построения расписаний для параллельных устройств 2) Система заданий с древовидной структурой Известно очень мало полиноминальных алгоритмов нахождения расписаний минимальной длины даже для тех случаев, когда наложены строчки ограничения на частичное упорядочение и времена выполнения заданий. Если считать, что все устройства (процессоры) идентичны, т.е. время выполнения задания Т на всех процессорах одно и тоже, то существуют два таких случая: 1) Когда граф заданий системы является деревом. 2) Когда в системе имеется только 2 процессора. Если требуется построить расписание без прерываний, то в обоих случаях накладывается дополнительное ограничение: все задания имеют одинаковое время выполнения. При изучении систем заданий, в которых все задания имеют одинаковые времена выполнения, можно без потери общности считать, что все эти времена равны 1. Такие системы называют UET-системами (unit-execution-time). Системы заданий с древовидной структурой Пусть на множестве работ, которые необходимо исполнить задано отношение частичного порядка «L», которое определяет ограничения на последовательность выполнения заданий. Запись [i]<[j] означает, что работа [i] должна быть завершена раньше, чем начнется j. Самым наглядным способом описания системы заданий является графовый способ. Отношение частичного порядка обычно представляется в виде ориентированного ациклического графа, у которого отсутствуют транзитивные дуги. Граф образует лес, если либо каждая вершина имеет не более одного предшественника, либо каждая вершина имеет не более одного последователей. Если лес в первом случае имеет ровно одну вершину без предшественников. А во втором – ровно одну вершину без последователей, то он называется деревом. Начальными называются вершины, не имеющие предшественников, а конечными – не имеющими последователей. Уровнем вершины называется сумма времен выполнения, приписанных вершинам, находящимся на таком пути от вершины к конечной вершине, на котором сумма имеет максимальное значение. Поскольку все задания имеют одинаковые времена выполнения, а прерывания запрещены, то удобно вместо непрерывного времени ввести дискретное. Выполнение расписания начинается в момент 0. Для всех целых i i-я единица времени (i-интервал) представляет собой интервал (i-1; i). Рассмотрим ранее построенное дерево задач. На пути от вершины 14 к конечной вершине расположены вершины 14;12;7;3 и 1. Поскольку 14<12< … <1, то независимо от количества процессоров, потребуется, по меньшей мере, 5 единиц времени, чтобы выполнить все задания. При наличии большого числа процессоров оптимальная стратегия будет заключаться в том, чтобы начать с наиболее удаленных заданий и продвигаться к конечной вершине. Назовем уровнем вершины х в орграфе максимальное число вершин (включая х), находящихся на пути от х к конечной вершине. В лесу имеется ровно один такой путь. Конечное задание имеет уровень 1. Назовем задание готовым, если выполнены все его предшественники. Можно показать, что следующая стратегия приводит к оптимальному расписанию при любом количестве процессоров. Уровневая стратегия: всякий раз, когда процессор освобождается, на него назначается невыполненное, но готовое задание из числа имеющих высший уровень (находящихся дальше всего от конечной вершины). Получаемое таким образом расписание называется уровневым расписанием. Пример. Применение уровневой стратегии для трех процессоров к системе заданий, изображенной на рисунке. Вначале назначаются задания 14 и 13, имеющие уровень 5. Задание 12 уровня 4 должно ожидать окончания выполнения заданий 14 и 13, поэтому на третий процессор в первую единицу времени назначается задание 11. Задания 12, 10, 9 уровня 4 выполняются в течение второй единицы времени и т.д. Полученное расписание приведено ниже. Процессор 1 14 12 8 6 3 1 Процессор 2 13 10 7 4 Процессор 3 11 9 5 2 Полученное расписание иллюстрирует важное свойство расписаний минимальное длины без прерываний. Задание 1, будучи единственной конечной вершиной, должно ожидать завершения всех других заданий, а для того, чтобы на 3 процессорах выполнить без прерываний 13 заданий, предшествующих заданию 1 требуется, по крайней мере, 5 единиц времени. Таким образом, длина любых расписаний для данной системы заданий должна быть, по крайней мере, равна 6. Можно показать, что уровневая стратегия приводит к оптимальному результату. Перейдем к алгоритму составления расписания. В этом алгоритме всем заданиям приписываются приоритеты. Задания более высоких уровней имеют более высокий приоритет. Поскольку уровни отсчитываются, начиная с конечных вершин, последовательно просматриваются все вершины на одном уровне. Затем на следующем и так далее, при этом каждой вершине приписывается метка. Для системы метка вершины представляет собой целое число от 1 до n. В нашей системе заданий конечная вершина помечена меткой 1, вершины 2 уровня имеют метки 2, 3, 4 и т.д. После того, как процесс расстановки меток завершен, составляется список заданий в порядке убывания меток. Расписание составляется следующим образом: всякий раз, когда некоторый процессор освобождается, список просматривается слева направо и первое еще не выполненное готовое задание назначается на процессор. Алгоритм расстановки меток. Временно будем считать, что система заданий имеет одну конечную вершину. 1. Если х – корневая вершина, пометим ее меткой 1. 2. Пусть пометки 1, 2, 3, … , j-1 уже расставлены. Если х есть задание, непосредственный приемник которого имеет минимальную метку, положим метку равной j. Процесс расстановки меток переходит от уровня к уровню, приписывая последовательные значения меток заданиям одного уровня. Временная сложность этого алгоритма зависит от структуры данных, используемой для представления графов. Матричное представление содержит O(n2) элементов и, следовательно, требуется O(n2) времени, чтобы выяснить какие элементы матрицы являются ненулевыми. Поэтому представление леса в виде матрицы нецелесообразно, т.к. он содержит O(n) ребер. Для описанного выше алгоритма удобно представлять данные в виде списка непосредственных предшественников каждой вершины. В дополнение к нему нужно иметь очередь Q заданий готовых к помечиванию. Алгоритма состоит из следующих шагов: 1). Начиная с пустой очереди Q, поместим в эту очередь все конечные вершины леса. В результате в очереди будут все задачи уровня 1. Ни одно задание еще не помечено 2). Предположим, что метки 1, 2, …, j-1 уже расставлены. Возьмем из очереди задание Х и присвоим ему метку j. Поместим всех непосредственных предшественников х в конец очереди Q. Останов, если очередь пуста. Легко показать, что с помощью данной процедуры расстановка меток в лесе происходит от уровня к уровню. Выполнение шагов займет линейное время от числа вершин O(n). Пример составления расписания для N процессоров с древовидно-упорядоченными задачами. Список непосредственных последователей Вершина 1 2 3 4 5 6 7 8 9 10 Ее непосредственный последователь 3 3 10 8 7 7 8 9 9 Очередь заданий, готовых к помечиванию 9 1. Помещаем в очередь конечные вершины (для них последователь равен ø). У нас это вершина 9. 2. В очереди 1 работа – 9. Присвоим ей метку «1», удалим из очереди и поместим в очередь всех ее непосредственных предшественников, т.е. работ, которые имеют последователя 9. Это работы 8 и 10. Метка U(9)=1. Состояние очереди 8 10 3. Присвоим работе 8 метку 2 , делим ее из очереди и поместим в очередь список ее непосредственных предшественников. U(8)=2 Состояние очереди 10 4 7 4. U(10)=3 4 7 3 5. U(4)=4 7 3 6. U(7)=5 3 5 6 7. U(3)=6 5 6 1 2 8. U(5)=7 6 1 2 9. U(6)=8 1 2 10. U(1)=9 2 11. U(2)=10 Очередь пуста – конец алгоритма. Исходное дерево с помеченными вершинами выглядит следующим образом: Теперь метки расставлены таким образом, что: если назначить на свободный процессор работу с наибольшей меткой из еще не выполненных и готовых к выполнению на текущем шаге, что все ее предшественники выполнены. Составим расписание минимальной длины для 3 процессоров Пр.1 2 5 4 9 Пр.2 1 3 10 Пр.3 6 7 8 Для 2 процессоров Пр.1 2 6 3 4 8 9 Пр.2 1 5 7 10 Для 4 процессоров Пр.1 2 3 8 9 Пр.2 1 7 Пр.3 6 4 Пр.4 5 10 Литература Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. – М.: Наука, 1975 Танаев В.С., Шкурба В.В. Введение в теорию расписаний. - М.: Наука, 1975 Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадиные системы. – М.: Наука, 1984 Теория расписаний и вычислительные машины / под. ред. Э.Г. Коффмана. - М.: Наука, 1984. Лекция 8 Лекция 8 Расписания для системы из двух устройств (процессоров) с произвольным частичным упорядочением заданий План лекции: 1) Постановка задачи 2) Алгоритм решения задачи В настоящее время не известны полиноминальные алгоритмы для составления расписания с произвольным частичным упорядочением при количестве процессоров большем 2. Для случая, когда число процессоров равно 2 может быть применена та же стратегия, как и при составлении расписания, когда частичное упорядочение заданий – лес, т.е.: каждому заданию приписываются метки, определяющие их приоритеты, на основе которых строится список, используемый для составления расписания. Ранее говорилось, что уровневая стратегия, т.е. «первым идет самый высокий уровень» является оптимальной для лесов. Поскольку деревья являются частным случаем ориентированных графов, следует ожидать, что и для произвольных ориентированных графов уровни играют определенную роль при составлении расписаний. Было бы хорошо, если бы удалось расставить приоритеты по уровням, после чего пришлось бы только заботиться о порядке, в котором должны выполняться задания одного уровня. Поэтому сформулируем желательное свойство процесса расстановки меток для ориентированных графов: Свойство 1. Если вершина Е имеет более высокий уровень, чем Т', то U(T)>U(T') (U(T) – метка вершины Т). Поскольку расписание будет строиться для 2 процессоров, заметим, что если на каждом уровне имеется четное число заданий, то все задания одного уровня будут завершаться до начала заданий следующего уровня, и, следовательно, свойство 1 является достаточным для того, чтобы расписание было оптимальным. Для того, чтобы выявить ряд факторов, существенных для оптимальной расстановки меток, рассмотрим следующую систему заданий: Свойство 2. Если множество непосредственных последователей задания Т содержит в себе множество непосредственных последователей задания Т', то U(T)>U(T'). Свойство 2 не является достаточным для составления оптимального расписания. Рассмотрим следующую ситуацию: Поскольку вершины 1 и 3 не имеют пересекающегося множества последователей, то они неразличимы по свойству 2. Отметим, что вершина 1 имеет уровень 1, и вершина 3 – уровень 2. Поскольку 7, как имеющая более высокий уровень, чем 5, возможно будет выполняться раньше, чем 5, будем присваивать 3 большую метку, чем 1. Выясняются два взаимосвязанных обстоятельства: 1). Необходим механизм для сравнения приемников заданий. 2). При сравнении необходимо принимать в расчет приоритеты приемников. Поскольку приоритеты задаются метками, то для сравнения можно использовать метки. Если собираемся для сравнения использовать метки, то вначале нужно помечать приемников (последователей), а затем предшественников. Алгоритмы расстановки меток 1). Пишем метку 1 одному из конечных заданий. 2). Предположим, что метки 1, 2,…, j-1 уже расставлены. Поскольку метки определяют приоритеты заданий, то метке j приписывается такому задании из множества заданий, готовых к помечиванию. Для того, чтобы выявить такое задание, сравним множества непосредственных приемников (последователей) заданий, готовых к помечиванию. Для каждого задания построим убывающую последовательность, используя метки его непосредственных приемников (последователей). Наименьшая лексиографически последовательность определяет задание, которое помечается меткой j. Пусть ν = ( ν1; ν2; …; νк) и μ = (μ1; μ2; …; μl) – последовательности целых чисел. K,l ≥ 0. Если К=0, последовательность ν – пуста. Говорят, что последовательность ν лексиографически меньше последовательности μ если: - существует такое i (1 ≤ i ≤ K), что для всех j (1 ≤ j ≤i) выполняется νj=μj и νi=μi ; - или νj=μj и К ≤ l . Последовательность (1,2,3)<(1,2,4); Последовательность (1,2,3)<(1,2,3,4). Пометим вершины графа следующим образом. Присвоим номер 1 одной из конечных вершин. Пусть присвоены номера 1,2, …, j-1 и Q – множество таких непронумерованных вершин, у которых нет непронумерованных потомков. Для каждой вершины построим последовательность a(i) всех прямых потомков, в которой элементы расположены по убыванию номеров. Присвоим номер j одному из требований с лексиографической наименьшей последовательностью a(i). Пусть - очередь вершин, готовых к присвоению номеров (эти вершины или конечные, или всем их потомкам присвоены метки). Первоначально в помещаются все конечные вершины графа. Образуем список L, в который будут записываться вершины, не получившие меток, не имеющие прямых потомков с метками. Каждая вершина в списке L встречается не более одного ряда. Первоначально список L пуст. Алгоритм присвоения меток состоит из n-шагов, каждый из которых соответствует присвоению номера некоторой вершине. На каждом шаге очередной номер присваивается первому элементу очереди . Пусть это элемент q. Исключаем q из . Произведем корректировку списка L следующим образом. Для каждого элемента i списка L с использованием матрицы смежности проверяем принадлежность множеству непосредственных предшественников q. Если i принадлежит этому множеству, помечаем этот элемент в списке L и в матрице смежности. Образуем последовательность L', состоящую из двух гостей. В первой части в произвольном порядке расположим элементы множества непосредственных предшественников q, не содержащих в L (для этого просматриваем столбец q матрицы смежности и удаляем одновременно пометки в этой матрице); во второй части расположим помеченные элементы списка L (в том же порядке, что и в списке L). Корректируем список L, исключая из него помеченные элементы и добавляя в конец L последовательность L'. Элементы i располагаются в списке L в порядке лексиографического возрастания последовательностей . - это упорядоченные по убыванию номера тех прямых потомков требования i, которым уже присвоены метки к данному шагу; если всем потомкам требования i присвоены метки. Указанное выше построение списка L не требует получения самих последовательностей a(i). Для каждого требования j, принадлежащего множеству непосредственных предшественников q уменьшаем на 1 число, расположенное в j-позиции списка QA. Просматривая с начала до конца список L, выбираем такие элементы i, что в i-позиции списка QA расположен ø, исключаем i из L и добавляем в . Проделая указанную процедуру для всех требований списков L, получим новый список L, новую очередь и переходим к следующему шагу. Пример. A B C D E F G H I Y 2 1 2 3 3 2 1 Первоначально и L=(ø) Шаг 1. Вершине 1 присваиваем метку 1. Множество непосредственных предшественников для вершины А – (F;G). Формируем список L’=(F;G). В первой части этого списка – в произвольной последовательности элементы множества прямых предшественников, не содержащихся в L', во второй части помеченные элементы списка L в той же последовательности, что и в списке L. У нас второй части сейчас нет, т.к. L=(ø). L=(F;G). После корректировки – исключаем помеченные элементы и добавляем в конец L последовательность L'. Корректировка списка QA: - уменьшаем на 1 число, расположенное в j-позиции QA. Литература Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. – М.: Наука, 1975 Танаев В.С., Шкурба В.В. Введение в теорию расписаний. - М.: Наука, 1975 Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадиные системы. – М.: Наука, 1984 Теория расписаний и вычислительные машины / под. ред. Э.Г. Коффмана. - М.: Наука, 1984. Лекция 9 Основы параллельного программирования Лекция 9 Структура аппаратного обеспечения многопроцессорных систем План лекции: 1) Однопроцессорные системы 2) Системы с разделяемой (общей) памятью 3) Проблема согласованности кэша в системах с общей памятью 4) Системы с распределённой памятью 5) Мультикомпьютеры и сетевые системы Современная однопроцессорная машина состоит из нескольких основных компонентов: центрального процессора, первичной (оперативной) памяти, одного или нескольких уровней кэш-памяти, дисковой памяти и набора периферийных устройств. Основными компонентами для выполнения программ являются процессор, кэш и оперативная память. Кэш – это небольшой по объему, но высокоскоростной модуль памяти, который используется для ускорения выполнения программ. В нем хранится содержимое областей памяти, часто используемых процессором. Причина использования кэш-памяти состоит в том, что для большинства программ наблюдается, так называемая, временная локальность, означающая, что если произошло обращение к некоторой области памяти, то, скорее всего, в ближайшее время к этой же области памяти программа обратиться вновь. Например, инструкции внутри циклов выбираются и повторяются многократно. Когда программа обращается к адресу памяти, процессор сначала ищет его содержимое в кэш. Если данные находятся там (происходит попадание в кэш), то они считываются из кэша. Если данных в кэше нет (промах), то данные считываются из оперативной памяти в кэш и процессор. Когда программа записывает данные, они помещаются в оперативную память и, возможно, к кэш. В сквозном кэше данные помещаются в память немедленно, в кэше с обратной связью – позже. Ключевой момент состоит в том, что после записи содержимое оперативной памяти может не соответствовать содержимому кэша. Чтобы ускорить передачу между КЭШем и оперативной памятью, элемент кэш-памяти обычно включает непрерывную последовательность слов из оперативной памяти. Эти элементы называются блоками или строками кэша. При промахе в кэш передается полная строка. Это оказывается весьма эффективным из-за наблюдающейся у большинства программ пространственной локальности. В современных процессорах обычно есть 2 типа кэша. Кэш 1 уровня находится ближе к процессору, а кэш второго уровня – между кэш 1 уровня и оперативной памятью. Кэш уровня 1 меньше по объему и быстрее, чем кэш второго уровня, и чаще всего иначе организован. Например, кэш 1 уровня обычно отображается непосредственно, а кэш второго уровня является множественно-ассоциативным. В непосредственно отображаемом кэше каждый адрес памяти отображается в один элемент кэша, а в множественно-ассоциативном – во множество элементов (2 или 4). Таким образом, если два адреса памяти отображаются в одну и ту же ячейку, в непосредственно отображаемом кэше может находиться только одна ячейка, к которой производилось самое последнее обращение, а в ассоциативном обе ячейки. С другой стороны непосредственно отображаемый кэш быстрее, поскольку проще выяснить, есть ли данное слово в кэше. Проиллюстрируем различия в скорости работы различных уровней иерархии памяти. Доступ к регистрам осуществляется за один такт работы процессора, к данным из кэш 1 уровня: 1 – 2 такта, к данным кэш 2 уровня: 10 тактов, к данным, хранящимся в оперативной памяти: 50 – 100 тактов. Мультипроцессорные системы с разделяемой памятью В мультипроцессорной системе (системе, состоящей из нескольких процессоров) с разделяемой памятью процессоры и модули памяти связаны с помощью соединительной сети. В небольших мультипроцессорных системах (2 – 25 процессоров) соединительная сеть реализуется в виде шины памяти или матричного коммутатора. Такие системы называются однородными, поскольку время доступа каждого процессора к любому участку памяти одинаково. Однородные системы называют также симметричными. В больших системах с разделяемой памятью (сотни процессоров) память организована иерархически. Соединительная сеть имеет вид древообразного набора переключателей и областей памяти. В такой структуре одна часть памяти ближе к определенному процессору, другая дальше от него. Такая организация памяти позволяет избежать перегрузки, возникающей при использовании одной шины или коммутатора, но приводит к неравным условиям доступа. Поэтому такие системы называют неоднородными. В системах обоего типа у каждого процессора есть собственный кэш. если два процессора ссылаются на разные области памяти, то их содержимое можно безопасно поместить в кэш каждого из них. Проблема возникает, когда 2 процессора обращаются к одной и той же области памяти одновременно. Если оба процессора только считывают данные, то в кэш каждого из них можно поместить копию данных. Но если один из процессоров записывает в память, то возникает проблема согласованности кэша: кэш другого процессора теперь содержит неверные данные. Следовательно, необходимо обновлять кэш другого процессора, либо признать содержимое кэша недействительным. В каждой системе протокол согласования кэш должен быть реализован аппаратно. Один из способов состоит в том, чтобы, чтобы кэш следил за адресной шиной, отлавливая ссылки на область памяти, содержащейся в нем. Запись в память также приводит к проблеме согласованности памяти: когда в действительности обновляется первичная память? Например, если один процессор выполняет запись в область памяти, а другой позже считывает данные из этой области памяти, будет ли считано обновленное значение? Существует несколько различных моделей согласованности памяти. Последовательная согласованность – наиболее сильная модель. Она гарантирует, что обновление памяти будет происходить в некоторой последовательности, причем каждому процессору будет видна одна и та же последовательность. Согласованность процессов – более слабая модель. Она обеспечивает, что записи в память, выполняемые каждым процессом, совершаются в том порядке, в котором их производит процессор, но записи, инициированные различными процессорами, для других процессоров могут выглядеть по-разному. Согласованное освобождение – еще более слабая модель, при которой оперативная память обновляется в указанных программистом точках синхронизации. Проблема согласования памяти демонстрирует противоречия между простотой программирования и расходами на реализацию. Программист интуитивно ожидает последовательного согласования, поскольку программа считывает и записывает переменные независимо от того, в какой части системы они хранятся в действительности. Когда процесс присваивает переменной значение, программист ожидает, что результаты присваивания станут немедленно известны всем процессам программы. С другой стороны, последовательное согласование очень дорого в реализации и замедляет работу системы. Дело в том, что при каждой записи аппаратная часть должна проверить все кэши и модифицировать оперативную память. В дополнение к этому – все выполняемые действия должны быть неделимыми. Поэтому в мультипроцессорных системах обычно реализуется более слабая модель согласования памяти, а программисту необходимо вставлять в программный код инструкции синхронизации памяти. Строки кэш-памяти часто содержат последовательности слов, которые передаются единым блоком из оперативной памяти и обратно. Пусть переменные X и Y занимают по одному слову и хранятся в соседних ячейках памяти, отображаемых на одну и туже строку кэш. Пусть некоторый процесс выполняется на процессоре 1 и производит записи и чтения переменной X. Допустим, что есть еще один процесс, выполняющийся на процессоре 2, который считывает и записывает переменную Y. Тогда при каждом обращении процессора 1 к переменной Х строка кэш-памяти этого процессора будет содержать и копию переменной Y. Аналогичная ситуация будет и в кэш процессора 2. Ситуация, описанная выше, называется ложным разделением: процессоры в действительности не разделяют переменные X и Y, поскольку аппаратная часть кэш-памяти интерпретирует обе переменные как один блок. Следовательно, когда процессор 1 обновляет переменную X, должна быть признана недействительной и, обновляться строка кэш в процессоре 2, содержащая X и Y. Таким образом, когда процессор 2 обновляет значение Y, строка кэш-памяти, содержащая X и Y, тоже должна быть обновлена или признана недействительной. Эти операции замедляют работу памяти, поэтому будет выполняться намного медленнее, чем тогда, когда две переменные попадают в разные строки кэш. Чтобы избежать ложного разделения, программист должен быть гарантирован, что переменные записываемые разными процессами, не будут находиться в смежных областях памяти. Одно из решений этой проблемы заключается в выравнивании, то есть резервировании фиктивных переменных, которые просто занимают место и отделяют реальные данные друг от друга. Системы с распределенной памятью В системах с распределенной памятью тоже есть связующая сеть, но каждый процессор имеет собственную память. Соединительная сеть поддерживает передачу сообщений, а не чтение и запись в память. Следовательно, процессоры взаимодействуют, передавая и принимая сообщения. У каждого процессора есть свой кэш, но из-за отсутствия разделения памяти нет проблем согласованности кэш и памяти. Мультикомпьютер (многомашинная система) – это многопроцессорная система с распределенной памятью, в котором процессор и сеть расположены физически близко (в одном помещении). Такие системы называют тесно связанными. Они одновременно используются небольшим количеством приложений. Соединительная сеть с большой пропускной способностью предоставляет высокоскоростной путь связи между процессорами. Обычно она организована в гиперкуб или матричную структуру. Сетевая система – это многомашинная система с распределенной памятью, узлы которой связаны с помощью локальной или глобальной сети. Сетевые системы называются слабо связанными. Здесь процессоры также взаимодействуют с помощью передачи сообщений, но время их доставки больше, чем в многомашинных системах. Сетевая система, состоящая из набора рабочих станций, называется кластером рабочих станций. Популярный сейчас способ построения недорогих систем с распределенной памятью – собрать так называемую машину Биовульфа. Она состоит из базового аппаратного обеспечения и операционной системы Linux. Литература Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования. – М.: Издательский дом «Вильямс», 2003. Воеводин В.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002 Гук М. Аппаратные средства IBM PC. Энциклопедия, 2-е изд. – СПб., Питер, 2003. Прангишвили И.В., Стецюра Г.Г. Микропроцессорные системы. – М.: Наука, 1980 Лекция 10 Лекция 10 Классификации параллельных систем План лекции: 1) О необходимости классификации параллельных систем 2) Классификация Флинна 3) Классификация Хокни 4) Классификация Скилликорна Существует достаточно большое количество способов организации параллельных систем. Вопрос о том, какие основные факторы характеризуют каждую из архитектур, приводит к необходимости их классификации. Классификация М. Флинна Это самая ранняя и наиболее известная классификация предложена в 1966 году. Классификация базируется на понятии «потока», под которым подразумевается последовательность команд или данных, обрабатываемых процессом. На основе числа потоков команд и потоков данных, Флинн выделяет 4 класса архитектур параллельных систем. SISD (Single Instruction stream / Single Data stream) – одиночный поток команд и одиночный поток данных. В системах такого класса есть только один поток команд. Все команды выполняются последовательно друг за другом и каждая команда инициализирует скалярную операцию. Тот факт, что для увеличения скорости выполнения команд может использоваться конвейерная обработка, значения не имеет. SIMD (Single Instruction stream / Multiple Data stream) – одиночный поток команд и множественный поток данных. В архитектурах этого типа сохраняется один поток команд, включающий, в отличие от SISD векторные команды. Это позволяет выполнять одну операцию сразу над многими данными, например, над элементами вектора. Поскольку способ выполнения векторных операций не оговаривается, то это может быть и процессорная матрица и конвейер. MISD (Multiple Instruction stream / Single Data stream) – множественный поток команд и одиночный поток данных. Определение подразумевает наличие многих процессоров, обрабатывающих один тот же поток данных. В настоящее время нет примеров реально существующих устройств подобного типа. MIMD (Multiple Instruction stream / Multiple Data stream) – множественный поток команд и множественный поток данных. Этот класс устройств предполагает, что в вычислительной системе есть несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных. Классификация Флинна до настоящего времени является самой применяемой в качестве начальной характеристики компьютеров. Если, например, говорят, что компьютер принадлежит классу SISD или MIMD, то сразу становится понятным принцип его работы. Классификации Р. Хокни Хокни разработал свой подход для более детальной систематизации устройств, подпадающих под класс MIMD классификации Флинна. Класс MIMD очень широк и объединяет множество различных типов архитектур. Пытаясь систематизировать архитектуры внутри этого класса, Хокни получил следующую иерархическую структуру. Основная идея классификации состоит в следующем. Множественный поток команд может быть обработан двумя способами. 1. Одним конвейерным устройством обработки, работающим в режиме разделения времени для отдельных потоков. 2. Каждый поток обрабатывается собственным устройством. Первая возможность используется в MIMD компьютерах, которые Хокни называет конвейерными. Архитектуры, использующие вторую возможность, делятся на два класса. В первый класс попадают MIMD компьютеры, в которых возможна прямая связь каждого процессора с каждым, реализуемая с помощью переключателя. Во втором классе находятся MIMD компьютеры, в которых прямая связь каждого процессора возможна только с ближайшими соседями, а взаимодействие отдаленных процессоров поддерживается с помощью специальной системы маршрутизации. Среди MIMD машин с переключателями Хокни выделяет те, в которых вся память распределена между процессорами, как локальная память. В этом случае общение процессоров реализуется с помощью сложного переключателя, составляющего значительную часть компьютера. Такие машины носят название MIMD-машин с распределенной памятью. Если память – это разделяемый ресурс, доступный всем процессорам через переключатель, то такие MIMD машины называются системами с общей памятью. Многие современные вычислительные системы имеют как общую разделяемую память, так и распределенную локальную. Такие системы Хокни рассматривает как гибридные с переключателем. При рассмотрении MIMD машин с сетевой архитектурой считается, что все они имеют распределенную память, а дальнейшая классификация проводится в соответствии с топологией сети: звездообразная сеть, регулярные решетки различной размерности, гиперкубы, сети с иерархической структурой (деревья), сети, изменяющие свою конфигурацию. Классификация Д. Скилликорна Предложена в 1989 году с целью расширения классификации Флинна. Скилликорн разработал подход, пригодный для описания многопроцессорных систем и некоторых нетрадиционных архитектур, например Dataflow. Предлагается рассматривать архитектуру любого компьютера как абстрактную структуру, состоящую из 4 компонентов. 1. Процессор команд – функциональное устройство, работающее как интерпретатор команд. В системе в общем случае может отсутствовать. 2. Процессор данных – функциональное устройство, работающее как преобразователь данных в соответствии с арифметическими операциями. 3. Иерархия памяти – запоминающее устройство, в котором хранятся данные и команды. 4. Переключатель – абстрактное устройство, обеспечивающее связь между процессорами и памятью. Функции процессора команд сводятся к следующему. На основании своего состояния и полученной от процессора данных информации, процессор команд выполняет следующие действия. - Определяет адрес команды, которая будет выполняться следующей. - Осуществляет доступ к памяти команд для выборки команды. - Получает и декодирует выбранную команду. - Сообщает процессору данных команду, которую надо выполнить. - Определяет адреса операндов и посылает их в процессор данных. - Получает от процессора данных информацию о результате выполнения команды. Функции процессора данных похожи на функции арифметических устройств традиционных процессоров. Процессор данных получает от процессора команд команду, которую надо выполнить, получает адреса операндов, выбирает операнды из памяти данных и возвращает процессору команд информацию о состоянии после выполнения команды. Скилликорн зафиксировал 4 типа переключателей без какой либо связи с типом устройств, которые они соединяют. 1. «1-1» - переключатель такого типа связывает пару функциональных устройств. 2. «n-n» - переключатель связывает каждое устройство из одного множества с соответствующим ему устройством из другого множества, то есть фиксирует попарную связь. 3. «1-n» - переключатель соединяет одно выделенное устройство со всеми функциональными устройствами из некоторого набора. 4. «n x n» - каждое функциональное устройство одного множества может быть связано с любым устройством другого множества и наоборот. Примеров подобных переключателей достаточно много. Все матричные процессоры имеют переключатель типа «1-n» для связи единственного процессора команд со всеми процессорами данных. В компьютерах семейства Connection Machine каждый процессор имеет свою локальную память, следовательно, такая связь будет описываться как «n - n». В тоже время, каждый процессор может связаться с другим процессором, что отвечает описанию «n x n». Классификации Скилликорна строится на следующих 8 характеристиках компьютера. 1. Количество процессоров команд. 2. Количество модулей памяти команд. 3. Тип переключателя между процессорами команд и модулями памяти. 4. Количество процессоров данных. 5. Число модулей памяти данных. 6. Тип переключателя между процессорами данных и модулями памяти данных. 7. Тип переключателя между процессорами команд и модулями памяти данных. 8. Тип переключателя между процессорами данных и процессорами команд. Литература Воеводин В.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002 Лекция 11 Лекция 11 Параллелизм План лекции: 1) Что такое «параллелизм» 2) Цель технологии параллелизма 3) Параллельное и распределённое программирование 4) Уровни программного параллелизма 5) Проблемы, связанные с параллельным программированием (проблемы координации, гонки данных, взаимоблокировка, трудности организации связи). Что такое параллелизм Два события называются одновременными, если они происходят в течении одного и того же временного интервала. Если несколько задач выполняются в течении одного и того же временного интервала, то говоря, что они выполняются параллельно. Термин «параллельно» необязательно означает «точно в один момент». Например, две задачи могут выполняться параллельно в течение одной и той же секунды, но при этом каждая из них выполняется в различные доли этой секунды, то есть последовательно. Таким образом, задачи могут выполняться по очереди, по поскольку продолжительность секунды с точки зрения человека достаточно коротка, то кажется, что задачи выполняются одновременно. Понятие одновременности (параллельности) можно распространить и на более длинные интервалы времени. Так, две программы, выполняющие некоторую задачу в течении одного и того же часа, постепенно приближаясь к своей конечной точке в течении этого часа могут работать точно в одни и те же моменты времени. Будем говорить, что две эти программы для этого часа выполняются параллельно. Другими словами, задачи, которые существуют в лдно и тоже время и выполняются в одно и то же время (в один и тот же интервал времени), являются параллельными. Параллельные задачи могут выполняться в одно- или многопроцессорной среде. В однопроцессорной среде параллельные задачи существуют в одно и тоже время и выполняются в течении одного и того же интервала времени за счёт так называемого «переключения контекста». В многопроцессорной среде, если свободно достаточное количество процессоров, параллельные задачи могут выполняться в одни и те же моменты времени в течение одного и того же периода времени. Цель технологии параллелизма – обеспечить условия, позволяющие компьютерным программам выполнять больший объём работ за тот же интервал времени. Поэтому проектирование программ должно ориентироваться не на выполнении одной задачи в некоторый промежуток времени, а на одновременное выполнение нескольких задач, на которые предварительно должна быть разбита программа. Возможны ситуации, когда целью является не выполнение большего объёма работы в течении одного и того же интервала времени, а упрощение решения задачи с точки зрения программирования. Иногда имеет смысл думать о проблеме как о множестве параллельно выполняемых задач. Например, если взять для сравнения вполне житейскую проблему, проблему снижения веса, то её лучше всего представить в виде двух параллельно выполняемых задач: диета и физическая нагрузка. Иначе говоря, для решения этой проблемы предполагается применение строгой диеты и физических нагрузок в течении одного и того же интервала времени (не обязательно в одни и те же моменты времени). Именно параллельность этих процессов даёт искомую форму решения этой проблемы. Два основных подхода к достижению параллельности Параллельное и распределённое программирование – это два базовых подхода к достижению параллельного выполнения программ. Они представляют собой две различные парадигмы, которые иногда пересекаются. Методы параллельного программирования позволяют разделить вычислительную работу между двумя и более процессами в рамках одного физического или виртуального компьютера. Методы распределённого программирования позволяют распределить работу программы между двумя или более вычислительными процессами, причём процессы могут существовать как на одном и том же компьютере, так и на различных компьютерах. Другими словами, части распределённой программы зачастую выполняются на разных компьютерах, связываемых по сети, или, по крайней мере, в различных процессах. Программа, содержащая параллелизм, выполняется на одном и том же физическом или виртуальном компьютере. Такую программу можно разбить на процессы или потоки. При чистом параллелизме одновременно выполняются части одной и той же программы. Части распределённого приложения обычно реализуются как отдельные программы. Типичные структуры параллельных и распределённых программ показаны на рисунках далее. Задачи параллельной программы более тесно связаны, чем задачи распределённого приложения. Существуют и гибридные архитектуры программного обеспечения - когда задачи в распределённых системах сами реализованы как параллельные программы. Параллельно выполняемые задачи приложения Распределённое приложение Преимущества параллельного и распределённого программирования 1) Качественно спроектированные параллельные программы работают быстрее, чем их последовательные эквиваленты, что повышает их рыночную стоимость. В таких случаях быстрее - означает лучше. 2) Иногда решение некоторых проблем представляется более естественным в виде коллекции одновременно выполняемых задач. Это характерно для таких областей как научное программирование и программирование задач искусственного интеллекта. 3) Методы распределённого программирования позволяют воспользоваться преимуществами ресурсов, размещённых в Internet, корпоративных и локальных сетях. Поэтому распределённое программирование всегда связано с сетевым программированием. Распределённое программирование подразумевает обращение одной программы к другой посредством сетевого оборудования. Отличительной чертой распределённых программ является то, что они разбиваются на части. Эти части обычно реализуются как отдельные программы, которые, как правило, выполняются на разных компьютерах. Например, распределённая программа, состоящая из Web-сервера и Web-клиента, может располагаться на компьютерах, которые физически расположены в разных концах земного шара. 4) Методы распределённого программирования предусматривают совместный доступ к дорогостоящим аппаратным и программным средствам. Например, высококачественный голографический принтер может обладать специальным ПО сервера печати, которое предоставляет соответствующие услуги для ПО клиентов. При этом ПО клиентов размещается на одном компьютере, а ПО сервера печати – на другом. 5) Распределённые вычисления можно использовать для создания определённого уровня избыточности вычислительных средств на случай аварии. Базовые уровни программного параллелизма Параллелизм может быть обеспечен на следующих уровнях: - уровень инструкций процессора; - уровень подпрограмм (функции и процедуры); - уровень объектов; - уровень приложений. Параллелизм на уровне инструкций Параллелизм на уровне инструкций возникает, если несколько частей одной инструкции выполняются параллельно. Пусть надо вычислить значение выражения x=(a+b)*(c-d). Это вычисление можно организовать по следующей схеме: Параллелизм на уровне подпрограмм Структуру программы можно представить в виде ряда функций (например, языка С++). Если эти функции выполнять на отдельном процессоре, то все функции смогут выполняться одновременного. Параллелизм на уровне объектов Программу можно реализовать как взаимодействие объектов (в языках, поддерживающих ООП, например С++ или Java). Объекты, реализованные в отдельных потоках или процессах, могут выполнять свои методы параллельно. Параллелизм на уровне приложений Несколько приложений сообща могут решать некоторую проблему. В таких случаях два отдельных приложения могут эффективно работать вместе подобно распределённому приложению. Например, буфер обмена не предназначен для работы ни с какими конкретными приложениями, но его успешно используют множество приложений. Сдвиг парадигмы программирования при переходе к параллельному программированию В базовой последовательной модели программирования инструкции компьютерной программы выполняются поочерёдно. Программа выглядит как кулинарный рецепт, в соответствии с которым для каждого действия компьютера задан порядок и объёмы используемых ингредиентов. Разработчики программы разбивают основную задачу на коллекцию подзадач. Все задачи выполняются по порядку, и каждая из них должна ожидать своей очереди. Все программы имеют начало, середину и конец. Разработчик представляет каждую программу в виде линейной последовательности. Эти задачи не обязательно должны находиться в одном файле, но их следует связать между собой так, чтобы, если первая задача по какой-то причине не завершила свою работу, то вторая вообще не начинала выполнение. Другими словами, каждая задача, прежде чем приступать к своей работе, должна ожидать до тех пор, пока не получит результатов выполнения предыдущей. Подобная последовательная модель настолько закрепилась в процессе проектирования и разработки ПО, что многие программисты считают её незыблемой и не допускают мысли о другом положении вещей. Решение каждой проблемы, разработка каждого алгоритма и планирование каждой структуры данных – всё это делалось с мыслью о последовательном доступа компьютера к каждой инструкции или ячейке данных. В мире параллельного программирования всё обстоит по другому. Здесь сразу несколько инструкций могут выполняться в один и тот же момент времени. Одна инструкция разбивается на несколько мелких частей, которые будут выполняться одновременно. Несколько задач могут одновременно начать выполняться на любом процессоре без какой-либо гарантии того, что задачи закреплены за определёнными процессорами, или какая-то задача завершится первой, или все они завершатся в некотором порядке. Помимо параллельного выполнения задач, возможно параллельное выполнение частей этой задачи. Проблемы координации Если программа содержит части (подпрограммы), которые выполняются параллельно, и эти подпрограммы совместно используют некоторые файлы, устройства или области памяти, то неизбежно возникают проблемы координации. Предположим, что у нас есть программа поддержки электронного банка, которая позволяет снимать деньги со счёта и класть их на депозит. Допустим, что эта программа разделена на три части, которые могут выполняться параллельно. Задача А получает запросы от задачи В на выполнение операций снятия денег со счёта. Задача А также получает запросы от задачи С, чтобы положить деньги на депозит. Задача А принимает запросы по принципу «первым пришёл – первым обслужен». Предположим, что на счёте имеется 1000 рублей, при этом задаче С требуется положить на депозит 100 рублей, а задача В желает снять со счёта 1100 рублей. Что произойдёт, если обе задачи В и С попытаются обновить один и тот же счёт одновременно? Каким будет остаток на счёте? Очевидно, что остаток на счёте в каждый момент времени не может иметь более одного значения. Задача А применительно к счёту должна выполнить только одну транзакцию, то есть мы сталкиваемся с проблемой координации задач. Если запрос задачи В будет выполнен на какую-то долю секунду быстрее, чем запрос задачи С, то счёт приобретёт отрицательный баланс. Но если задача С получит право на обновление счёта, то этого не произойдёт. Таким образом, остаток на счёте зависит от того, какой задаче (В или С) первой удаётся сделать запрос к задаче А. Более того, мы можем выполнить задачи В и С несколько раз с одними и теми же значениями, и при этом иногда запрос задачи В будет произведён на какую-то долю быстрее, чем запрос задачи С, а иногда наоборот. Очевидно, что необходимо организовать надлежащую координацию действий. Для координации задач, выполняемых параллельно, требуется обеспечить связь между ними и синхронизацию их работы. При некорректной связи или синхронизации обычно возникают четыре типа проблем: - гонка данных; - бесконечная отсрочка; - взаимоблокировка; - трудности организации связи. Гонка данных Если несколько задач одновременно попытаются изменить некоторую область данных, а конечное значение при этом будет зависеть от того, какая задача обратится к этой области первой, возникает ситуация, которая называется состоянием гонок. В случае, когда несколько задач попытаются обновить один и тот же ресурс данных, такое состояние называется «гонкой данных». Для предотвращения гонок данных нужна некоторая стратегия, например, если одновременно происходит добавление и снятие денег со счёта, то сначала должно быть выполнено добавление и только потом снятие. Бесконечная отсрочка Такое планирование, при котором одна или несколько задач должны ожидать до тех пор, пока не произойдёт некоторое событие или не создадутся определённые условия, может оказаться довольно простым для реализации. Во-первых, ожидаемое событие или условие должны отличаться регулярностью. Во-вторых, между задачами следует наладить связи. Если одна или несколько задач ожидают сеанса связи до своего выполнения, то в случае, если ожидаемый сеанс связи не состоится, состоится слишком поздно или не полностью, эти задачи могут так никогда и не выполниться. Также, если ожидаемое событие или условие, которое (по нашему мнению) должно произойти (наступить), но в действительности не происходит (не наступает), то приостановленные нами задачи будут вечно находиться в состоянии ожидания. Возникает ситуация, которую называют «бесконечная отсрочка». Взаимоблокировка Взаимоблокировка – это ещё одна ловушка, связанная с ожиданием. Взаимоблокировка возникает в том случае, когда задача А может выполниться только в том случае, когда задача Б выполнит свою часть работы, но Б не может выполняться, пока не выполнится А. При координации параллельно выполняемых задач необходимо помнить, что взаимоблокировка и параллельная отсрочка – самые опасные преграды, которые нужно предусмотреть и избежать. Трудности организации связи Многие распределённые параллельные среды (например, кластеры) зачастую состоят из гетерогенных компьютерных сетей. Гетерогенные компьютерные сети – это системы, которые состоят из компьютеров различных типов, работающих в общем случае под управлением различных операционных систем, использующих различные сетевые протоколы. Их процессоры могут иметь различную архитектуру, обрабатывать слова различной длины и использовать различные языки программирования. Могут использоваться и различные стратегии управления приоритетами. Всё это приводит к разнообразным трудностям, возникающим при организации связи. Лекция 12 Взаимодействие последовательных процессов. Задача о критической секции. План лекции: 1. Понятие последовательного процесса 2. Описание параллельных последовательных процессов 3. Задача о критической секции и неудачные попытки её решения. 4. Алгоритм Деккера Если двум или более последовательным процессам необходимо взаимодействовать друг с другом, то они должны иметь средства для обмена информацией. Будем полагать, что процессы связаны слабо, то есть кроме редких моментов явной связи эти процессы рассматриваются совершенно независимо друг от друга. В частности, не допускаются никакие предположения об относительных скоростях процессов. Рассмотрим два последовательных процесса «Процесс 1» и «Процесс 2», которые для удобства дальнейшего изложения будем считать циклическими. В каждом цикле существует «критическая секция». «Критическая» в том смысле, что, в любой момент времени только один из процессов может находиться внутри своей критической секции. Чтобы осуществить такое взаимодействие, оба процесса имеют доступ к некоторому числу общих переменных. Будем считать, что проверка текущего состояния общей переменной и присваивание нового значения общей переменной, рассматриваются как неделимые, то есть если два процесса осуществляют присваивание нового значения одной и той же переменной одновременно, то присваивания происходят друг за другом и окончательное значение общей переменной соответствует одному из присваиваемых значений и не является их смесью. Аналогично, если один процесс проверяет значение общей переменной одновременно с присваиванием ей значения другим процессом, то первый процесс обнаружит либо старое значение, либо новое, но никогда их смесь. Для написания параллельных программ будем использовать знакомый синтаксис языка программирования Паскаль, добавив к нему расширение, позволяющее описывать параллельное выполнение. Если последовательность операторов заключена в специальные операторные скобки «parbegin» и «parend», то это надо интерпретировать как параллельное выполнение составляющих конструкцию операторов. parbegin begin операторы процесса 1; end; begin операторы процесса 2; end; parend. Конструкция этого примера означает, что процессы 1 и 2 должны выполняться параллельно. Теперь можно рассмотреть первую попытку решения задачи критической секции. Несмотря на то, что использование операторов условного перехода не является приемлемым стилем разработки программ, мы будем использовать их, поскольку с их помощью описания процессов, происходящих в программах, становятся более понятными. Q: Integer; Begin Q:=1; parbegin begin {Процесс 1} L1: if Q=2 then goto L1; Критическая секция процесса 1 Q:=2; Остаток цикла goto L1; end; begin {Процесс 2} L2: if Q=1 then goto L2; Критическая секция процесса 2 Q:=1; Остаток цикла goto L2; end; parend End. Два процесса связываются друг с другом через общую переменную Q, значение которой показывает, какой из двух процессов первым закончит выполнение своей критической секции. Из программы видно, что после начального присваивания возможными значениями переменной Q являются значения 1 или 2. Условием входа в критическую секцию процесса 2 является Q=2. Но единственный способ для переменной Q получить это значение есть присваивание Q=2 в процессе 1. Так как процесс 1 выполнит это присваивание только по завершении своей критической секции, то процесс 2 может войти в свою критическую секцию только после завершения критической секции процесса 1. А критическая секция процесса 1 действительно может быть выполнена, поскольку начальное условие Q:=1. После присваивания Q:=2 роли процессов меняются. Такое решение, хотя и правильное, имеет излишнее ограничение: после завершения критической секции процесса 1 – Q=1, после этого Q=2, снова Q=1 и т.д. То есть единственной допустимой последовательностью выполнения критических секций является последовательность 1, 2, 1, 2… То есть процессы 1 и 2 оказываются синхронизированными. Для того чтобы четко определить нежелательность для нас такого явления, поставим следующее условие: если один из процессов остановился вне своей критической секции, то это не должно приводить к блокировке другого процесса. Следовательно, такое решение неприемлемо и надо искать новое. Введем две целочисленные переменные С1 и С2. С1=0, если процесс находится внутри своей критической секции с С1=1, если процесс не находится внутри собственной критической секции. Значения переменной С2 аналогичны, но для второго процесса. C1, C2 : integer; Begin C1:=1; C2:=1; parbegin {Процесс 1} Begin L1: if C2=0 goto L1; C1:=0; Критическая секция процесса 1; C1:=1; Остаток цикла процесса 1; goto L1; End; {Процесс 2} Begin L2: if C1=0 goto L2; C2:=0; Критическая секция процесса 2; C2:=1; Остаток цикла процесса 2; goto L2; End; parend; End. Первоначально С1=1 и С2=1, что соответствует тому факту, что оба процесса начинают выполняться вне своих критических секций. Во время выполнения критической секции процесса 1 сохраняется значение С1=0 и поэтому первая строка процесса 2, по существу, для ожидания, пока процесс 1 находится в своей критической секции. Такое решение отчасти предохраняет от одновременного выполнения критических секций, но оно неверно. Пусть сначала процесс 1 обнаружит, что С2=1. Пусть процесс 2 немедленно вслед за этим проверяет значение С1: тогда С1 еще равно 1. Следовательно, каждый из процессов, удостоверившись, что другой не находится в своей критической секции, решит, что он может безопасно войти в свою собственную критическую секцию. Требуется действовать более осторожно. Поменяем местами в самом начале процессов проверку чужого С и установку собственного. Получим следующую программу. C1, C2 : integer; Begin C1:=1; C2:=1; parbegin {Процесс 1} Begin А1: С1:=0; L1: if C2=0 goto L1; C1:=0; Критическая секция процесса 1; C1:=1; Остаток цикла процесса 1; goto А1; End; {Процесс 2} Begin А2: С2:=0; L2: if C1=0 goto L2; C2:=0; Критическая секция процесса 2; C2:=1; Остаток цикла процесса 2; goto А2; End; parend; End. Такое решение является совершенно безопасным. Сосредоточим внимание на моменте, когда процесс обнаруживает, что С2=1, и поэтому решает войти в свою критическую секцию. В этот момент можно заключить: 1. соотношение С1=0 уже установлено и будет сохраняться, пока процесс 1 не завершит выполнение своей критической секции; 2. так как процесс 2 находится вне своей критической секции, в который он не может войти пока сохраняется С1=0, то есть пока процесс 1 находится в своей критической секции. Следовательно, взаимное исключение критических секций гарантировано. Однако такое решение содержит опасность взаимной блокировки. Если после присваивания С1=0, но еще до проверки С2 (и то и другое в процессе 1), процесс 2 выполнит присваивание С2=0, то это значит, что С1=0 и С2=0, то есть процессы будут безрезультатно ждать друг от друга разрешения войти в критические секции. В свое время предлагалось довольно много вариантов решения задачи критической секции, но все они оказывались не корректными. Существовало также сомнение в том, что задача критической секции вообще имеет решение. Первое правильное решение этой задачи принадлежит голландскому математику Деккеру. Алгоритм Деккера для решения задачи критической секции С1, С2, Q: integer; Begin C1:=1; C2:=1; Q:=1; {Q можно сделать равным и 2} parbegin {Процесс 1} begin A1: C1:=0; L1: if C2=0 then begin if Q=1 then goto L1; C1:=1; B1: if Q=2 then goto B1; goto A1; end; Критическая секция процесса 1; Q:=2; C1:=1; Остаток цикла процесса 1; goto A1; end; {Процесс 2} begin A2: C2:=0; L2: if C1=0 then begin if Q=2 then goto L2; C2:=1; B2: if Q=1 then goto B2; goto A2; end; Критическая секция процесса 2; Q:=1; C2:=1; Остаток цикла процесса 2; goto A2; end; parend; End. Докажем корректность алгоритма Деккера. 1. Каждый процесс оперирует только с собственным «с». Из-за этого Процесс 1 проверяет С2 только при С1=0. Он войдет в критическую секцию только тогда, когда обнаружит, что С2=1. Процесс 2 ведет себя аналогично. 2. Теперь покажем, что выяснение вопроса, какому из двух процессов войти в критическую секцию, не может откладываться до бесконечности. Заметим, что изменение значения переменной Q происходит только при окончании критических секций и поэтому Q можно считать константой во время принятия решения о том, кому войти в критическую секцию. Если Q=1, то Процесс 1 может только циклится через метку L1 (при этом С1=0) и только до тех пор, пока он обнаруживает, что С2=0. Но если Q=1, то Процесс 2 может циклиться только через B2, а это состояние Процесса 2 означает, что С2=1, поэтому Процесс 1 не может циклиться и обязательно попадет в свою критическую секцию. Для случая Q=2 применяется симметричное относительно процессов и переменных рассуждение. 3. остановка Процесса 1 в «остатке цикла 1» не препятствует продвижению процесса 2. Тогда справедливо соотношение С1=1 и Процесс 2 может входить в свою критическую секцию независимо от значения переменной Q. Литература 1) Языки программирования / под. ред. Ф. Женюи. – М.: Мир, 1972. Лекция 13 Процессы и потоки План лекции 1) Процессы, виды процессов и их состояния 2) Переключение контекста процесса 3) Потоки и многопоточные процессы 4) Сходства и различия между потоками и процессами Процесс – это некоторая часть (единица) работы, создаваемая операционной системой. Важно отметить, что процессы и программы – не обязательно эквивалентные понятия. Одна программа может состоять из нескольких процессов. В некоторых ситуациях процесс может быть не связан с конкретной программой. Процессы – это артефакты операционной системы, а программы – артефакты разработчика. Такие операционные системы как Unix или Linux позволяют управлять сотнями и тысячами параллельно загруженных процессов. Чтобы некоторую часть работы можно было назвать процессом, она должна иметь адресное пространство, назначаемое операционной системой и идентификационный номер (id процесса), процесс должен обладать определённым статусом и иметь свой элемент в таблице процессов операционной системы. Процесс может содержать один или несколько потоков управления, выполняющихся в рамках его адресного пространства, и использовать системные ресурсы, требуемые для этих потоков. Процесс состоит из множества выполняющихся инструкций, размещённых в адресном пространстве этого процесса. Виды процессов При выполнении процесса операционная система назначает ему некоторый процессор. Процесс выполняет свои инструкции в течении некоторого момента времени. Затем он выгружается, освобождая процессор для другого процесса. Планировщик операционной системы переключается с кода одного процесса на код другого, предоставляя возможность каждому процессу выполнить свои инструкции. Различают пользовательские и системные процессы. Процессы, которые выполняют системный код, называются системными и применяются к системе в целом. Они занимаются решением таких системных задач как распределение памяти, обмен страницами между внутренними и внешними запоминающими устройствами и т.д. Они также выполняют некоторые задачи «по поручению» пользовательских процессов, например делают запросы на ввод-вывод данных, выделяют память и т.п. Пользовательские процессы выполняют свой собственный код и иногда обращаются к системным функциям. Выполняя собственный код, пользовательский процесс пребывает в пользовательском режиме. При вызове системных функций пользовательский процесс выполняет функции операционной системы. При этом пользовательский процесс удерживает процессор до тех пор, пока системный вызов не будет выполнен. Для выполнения системного вызова процесс обращается к ядру операционной системы. В это время пользовательский процесс пребывает в привилегированном режиме или режиме ядра и не может быть выгружен никаким другим пользовательским процессом. Процессы имеют характеристики, используемые для идентификации и определения их поведения. Когда операционная система переключается с одного процесса на другой, она сохраняет текущее состояние выполняемого процесса и его контекст в области хранения блока управления процессами (БУП), чтобы надлежащим образом возобновить выполнение этого процесса в следующий раз, когда ему снова будет выделен процессор. БУП содержит следующую информацию: - текущее состояние приоритета процесса; - идентификатор процесса, а также идентификаторы родительского и дочернего процессов; - указатели на выделенные ресурсы; - указатели на область памяти процесса; - процессор, занятый процессом; - регистры управления и состояния; - указатели стека. Адресное пространство делится на три логических раздела: - текстовый (для кода программы); - информационный (для данных программы); - стековый (для стеков программы). Адресное пространство процесса виртуально. Применение виртуальной памяти позволяет отделить адреса, используемые в текущем процессе, от адресов, реально доступных во внутренней памяти. Тем самым значительно увеличивается задействованное пространство адресов по сравнению с реально доступными адресами. Разделы виртуального адресного пространства представляют собой смежные блоки памяти. Каждый такой раздел и физическое адресное пространство разделены на участки, называемые страницами. При последовательных виртуальных адресах соответствующие им физические страницы не будут последовательными. Несмотря на то, что виртуальное адресное пространство каждого процесса защищено, то есть, приняты меры по предотвращению доступа к нему со стороны другого процесса, текстовый раздел может совместно использоваться несколькими процессами. Чтобы операционная система могла управлять всеми процессами, хранимыми во внутренней памяти, она создаёт и поддерживает таблицы процессов. Состояния процессов Во время выполнения процесса его состояние меняется. Под состоянием процесса понимается его текущий режим или статус. В среде UNIX процесс может принимать одно из следующих состояний: - выполнения; - работоспособности (готовности); - «зомби»; - ожидания (блокирования); - остановки. Состояние процесса меняется при определённых обстоятельствах. Под сменой состояний, или переходом из одного состояния в другое, понимают обстоятельства, которые заставляют процесс изменять своё состояние. Диаграмма состояний процесса показана на рисунке. Когда процесс только создаётся, он готов к выполнению своих инструкций, но должен ожидать «своего часа» до тех пор, пока процессор не освободится. Каждому процессу разрешается использовать процессор в течении некоторого интервала времени, называемого «квантом времени». Процессы, ожидающие использования процессора, помещаются в «очередь готовых процессов». Процессы, находящиеся в очередях готовых процессов, пребывают в состоянии работоспособности. Когда процесс становится доступным, диспетчер назначает его работоспособному (готовому) процессу, который занимает его в течении своего кванта времени. По истечении этого кванта времени процесс покидает процессор, независимо от того, выполнил он все свои инструкции или нет. Этот процесс вновь помещается в очередь готовых процессов. Тем временем, из очереди выбирается новый процесс. Если квант времени ещё не исчерпан, но процесс не в состоянии продолжить выполнение, он может добровольно отказаться от процессорного времени. Причины отказа могут быть различными. Например, процесс может сделать запрос на получение доступа к устройству ввода-вывода, вызвав системную функцию, или ему необходимо подождать освобождения объекта (переменной) синхронизации. Процессы, которые не могут продолжить выполнение из за необходимости дождаться совершения некоторого события, «засыпают», то есть переходят в состояние ожидания. Они помещаются в очередь ждущих процессов. После наступления ожидаемого события они удаляются из этой очереди и возвращаются в очередь готовых процессов. Текущий процесс, то есть процесс, занимающий процессорное время, может быть лишён его ещё до истечения кванта времени, если о своей готовности заявит процесс с более высоким приоритетом (например, системный процесс). Выгруженный досрочно процесс сохраняет статус работоспособного и поэтому снова помещается в очередь готовых процессов. Выполняющийся процесс может получить сигнал «остановить выполнение». Состояние останова отличается от состояния ожидания, потому что при этом не был исчерпан квант времени и процесс не делал никакого системного запроса. Процесс мог получить сигнал остановится либо по причине прерывания в режиме отладки, либо из-за возникновения особой ситуации в системе. Получив сигнал остановиться, процесс переходит из состояния выполнения в состояние останова. Позже процесс может быть «разбужен» или ликвидирован. Выполнив все свои инструкции, процесс покидает систему. В этом случае он удаляется из таблицы процессов и его БУП-блок разрушается; все занимаемые процессором ресурсы освобождаются. Процесс, который не способен продолжить выполнение, но при этом не может выйти из системы, считается «зомбированным». Зомбированный процесс не использует никаких системных ресурсов, но сохраняет свою структуру в таблице процессов. Если в таблице процессов ожидается слишком много зомбированных процессов, это негативным образом отражается на производительности системы и может вызвать её перезагрузку. Переключение контекста процесса Переключение контекста процесса происходит в момент, когда процессов переключается с одного процесса на другой. При переключении контекста система сохраняет контекст текущего процесса и восстанавливает контекст следующего процесса, выбранного для использования процессора. БУП-блок первого процесса при этом обновляется, а также изменяется значение поля состояния процесса (то есть признак состояния заменяется признаком другого состояния: готовности, блокирования или «зомби»). Сохраняется и обновляется содержимое регистров процессора, состояние стека, данные об идентификации и привилегиях пользователя и процесса, а также стратегии планирования и учётная информация. Переключение контекста происходит в тех случаях, когда: - процесс выгружается; - процесс добровольно отказался от процессора; - процесс делает запрос к устройству ввода-вывода и должен ожидать наступления события; - процесс переходит из пользовательского режима в режим ядра. Когда выгруженный процесс снова выбирается для использования процессора, его контекст восстанавливается, и выполнение продолжается с точки, на которой он был прерван в предыдущем сеансе. Завершение процесса Когда процесс завершается, его БУП-блок разрушается, а используемое им адресное пространство и ресурсы освобождаются. Процесс завершается, если соблюдены следующие условия: - все инструкции выполнены; - процесс явным образом передаёт управление родительскому процессу или вызывает системную функцию, которая завершает процесс; - дочерние процессы могут завершиться при завершении родительского процесса; - родительский процесс посылает сигнал о завершении своих дочерних процессов; - аварийное завершение процесса может произойти в случае, если процесс выполняет недопустимые действия; - процесс требует больше памяти, чем система может ему предоставить; - процесс пытается получить доступ к не разрешённым ресурсам; - процесс пытается выполнить некорректную инструкцию или запрещённые вычисления. Потоки в Unix и Linux Под потоком понимается часть выполняемого в процессе кода, которая регламентирована определённым образом. Затраты вычислительных ресурсов, связанные с созданием потока, его поддержкой и управлением у операционной системы значительно ниже по сравнению с аналогичными затратами у процессов, поскольку объём информации об отдельном потоке гораздо меньше, чем об отдельном процессе. Каждый процесс имеет основной или первичный поток. Под основным потоком процесса понимается программный поток управления или поток выполнения. Процесс может иметь несколько потоков выполнения и, соответственно, столько же потоков управления. Каждый поток имея собственную последовательность инструкций, выполняется независимо от других, а все они параллельны друг другу. Процесс с несколькими потоками называется многопоточным. Контекстные требования потока Все потоки одного процесса существуют в одном и том же адресном пространстве. Все ресурсы, принадлежащие процессу, разделяются потоками. Потоки не владеют никакими ресурсами. Потоки разделяют дескрипторы файлов и файловые указатели, но каждый поток имеет собственный программный указатель, набор регистров, состояние и стек. Все стеки потоков находятся в стековом разделе своего процесса. Поток может считывать и записывать информацию из области памяти своего процесса. Когда основной поток записывает данные в память, то любой дочерний поток может получить к ним доступ. Потоки могут создавать другие потоки в пределах того же процесса. Все потоки в одном процессе считаются равноправными. Потоки могут приостанавливать, возобновлять или завершать другие потоки в своём процессе. Потоки – это части программы, которые соревнуются за использование процессора с другими потоками того же самого процесса или других процессов. В многопроцессорной системе потоки одного процесса могут выполняться одновременно на различных процессорах. Однако, потоки конкретного процесса выполняются только на процессоре, который назначен этому процессу. Например, если процессоры 1,2 и 3 назначены процессу А, а процесс А имеет 3 потока, то любой из них может быть назначен любому процессору. В среде с одним процессором потоки конкурируют за его использование. Параллельность же достигается за счёт переключения контекста. Контекст переключается, если операционная система поддерживает многозадачность при наличии единственного процессора. Многозадачность позволяет на одном микропроцессоре одновременно выполнять несколько задач. Каждая задача выполняется в течении выделенного интервала времени. По истечении заданного интервала или при наступлении некоторого события, текущая задача снимается с процессора, а ему назначается другая задача. Когда потоки выполняются параллельно в одном процессе, то о таком процессе говорят, что он многопоточный. Каждый поток выполняет свою подзадачу таким образом, что подзадачи процесса могут выполняться независимо от основного потока управления. Сходства и различия между потоками и процессами Сходства: - оба имеют идентификационный номер, состояние, набор регистров, приоритет и привязку к определённой стратегии планирования; - и поток и процесс имеют атрибуты, которые описывают их особенности для операционной системы; - оба имеют информационные блоки; - оба разделяют ресурсы с родительским процессом; - оба функционируют независимо от родительского процесса; - создатель потока или процесса может им управлять; - и поток, и процесс могут изменять свои атрибуты; - оба могут создавать новые ресурсы; - как поток, так и процесс не имеют доступа к ресурсам другого процесса. Различия: - потоки разделяют адресное пространство процесса, который их создал; процессы имеют собственное адресное пространство; - потоки имеют прямой доступ к разделу данных своего процесса; процессы имеют собственную копию раздела данных родительского процесса; - потоки могут напрямую могут взаимодействовать с другими потоками своего процесса; процессы должны использовать специальный механизм межпроцессорного взаимодействия для связи с «братскими» процессами; - потоки почти не требуют системных затрат; на поддержку процессов требуются значительные затраты системных ресурсов; - новые потоки создаются легко; новые процессы требуют дублирования родительского процесса; - потоки могут в значительной степени управляться потоками того же процесса; процессы управляю только дочерними процессами; - изменения, вносимые в основной поток (отмена, изменение приоритета и т.п.) могут влиять на поведение других потоков процесса; изменения, вносимые в родительский процесс, не влияют на дочерние процессы. Преимущества использования потоков - Для переключения контекста требуется меньше системных ресурсов. - Достигается более высокая производительность приложения. - Для обеспечения взаимодействия между потоками не требует никакого специального механизма. - Программа имеет более простую структуру. Недостатки использования потоков - Потоки могут разрушить адресное пространство процесса. - Потоки необходимо синхронизировать при параллельном доступе (для чтения или записи) к памяти. - Один поток может ликвидировать целый процесс или программу. - Потоки существуют только в рамках единого процесса и, следовательно, не являются многократно используемым. Литература 1) Операционные системы / Д. Бэкон, Т. Харрис. – СПб.: Питер; Киев: Издательская группа BHV, 2004 2) МакКузик М.К., Невилл-Нил Д.В. FreeBSD: архитектура и реализация. – М.: КУДИЦ-ОБРАЗ, 2006. Лекция 14 Семафоры План лекции: 1) Понятие семафора, общие и бинарные семафоры 2) Операции над семафорами 3) Решение задачи критической секции с помощью семафоров 4) Задача о производителях и потребителях и её решение с помощью семафоров 5) Задача об обедающих философах Алгоритм Деккера, как и ряд других алгоритмов для решения задачи критической секции, относится к алгоритмам с активным ожиданием. Это означает, что каждый процесс, если он даже и не может войти в свою критическую секцию, постоянно активен и все время проверяет значения разделяемых переменных. Все такого рода алгоритмы достаточно сложны в реализации и неэффективны в большинстве случаев. Поскольку синхронизация является основой параллельных программ, то желательно иметь специальные средства, которые можно использовать для блокировки приостанавливаемых процессов. Первым таким средством синхронизации, не потерявшим актуальности до настоящего времени, стали семафоры. Они облегчают защиту критических секций и могут использоваться для организации планирования и сигнализации. Идея семафора взята из метода синхронизации движения поездов, принятого на железной дороге. Железнодорожный семафор – это сигнальный флажок, что путь впереди свободен или занят другим поездом. По мере движения поезда семафоры устанавливаются и сбрасываются. Семафор остается установленным на время, достаточное, чтобы при необходимости остановить другой поезд. Таким образом, железнодорожные семафоры можно рассматривать как устройства, которые сигнализируют об условиях, чтобы обеспечить взаимоисключающее прохождение поездов по критическим участкам пути. Семафоры в параллельных программах аналогичны – они представляют базовый механизм синхронизации и используются для реализации взаимного исключения и условной синхронизации. Семафор – это особый тип разделяемой переменной, которая обрабатывается только двумя неделимыми командами P и V. V-операция – это операция с одним аргументом, который должен быть семафором. Если S1 – семафор, то операция записывается как V(S1). Назначение этой операции состоит в увеличении значения аргумента на 1 (напомним – эта операция должна быть неделимой). Операция V(S1) не эквивалентна операции S1=S1+1. Предположим, что процессы А и В содержат оператор V(S1) и что оба они хотят выполнить этот оператор одновременно когда S1=3 (например). Процессы А и В выполнят каждый свой V-оператор в неопределенном порядке и S1 станет равен 5. Если S1 не семафор, а обычная общая переменная и если процессы А и В содержат команды S1=S1+1, то может случиться следующее. Процесс А вычисляет S1+1 и получает 4. До осуществления присваивания 4 переменной S1 процесс В тоже также вычисляет S1+1 и получает 4. После этого оба процесса присваивают 4 переменной S1 и одно из необходимых приращений теряется. Требование неделимости V-операции предназначено для того, чтобы не допустить такой ситуации. P-операция – операция с одним аргументом, который должен быть семафором. Назначение операции – уменьшить на 1 значение семафора-аргумента, если только результирующее значение не становится отрицательным. Завершение P-операции, то есть решение задачи о том, что настоящий момент является подходящим для выполнения уменьшения и последующее собственно уменьшение должны рассматриваться как неделимая операция. P-операция предоставляет потенциальную задержку: если процесс инициализирует P-операцию над семафором, который в этот момент равен 0, то P-операция не может завершиться, пока другой процесс не выполнит V-операцию над тем же семафором и не присвоит ему значение 1. Несколько процессов могут одновременно начать P-операцию над одним и тем же семафором. Тогда утверждение о том, что завершение P-операции есть неделимое действие, означает, что когда семафор получит значение 1, только одна из начавшихся P-операций над семафором завершится. Какая именно – не определено, или остается вне нашего контроля. Решение задачи критической секции с помощью семафоров Задачу о критической секции можно решить с помощью единственного двоичного семафора (то есть семафора, принимающего только значения 0 или 1). Семафоры, значения которых может быть равно любому неотрицательному числу, называются общими семафорами. Sem S; {Определим семафор с именем S} parbegin {Процесс 1} begin L1: P(S); Критическая секция процесса 1; V(S); Остаток цикла процесса 1; goto L1; end {Процесс 2} begin L2: P(S); Критическая секция процесса 2; V(S); Остаток цикла процесса 2; goto L2; end parend Условная синхронизация Кроме рассмотренного ранее способа взаимодействия последовательных процессов (задача о критической секции) важной для параллельного программирования является и, так называемая, задача условной синхронизации. Рассмотрим два процесса, связанных следующим образом: при достижении процессом А некоторой точки, он не может продолжить работу до тех пор, пока процесс B не выполнит некоторую задачу. Для такого рода условной синхронизации можно применить инициализированный значением 0 семафор, у которого А должен ждать в точке синхронизации, пока B не станет сигнализировать о том, что его задача выполнена. Решение задачи о производителях и потребителях с помощью семафора Рассмотрим два процесса, которые назовем «производитель» и «потребитель». Производитель является циклическим процессом, и при каждом циклическом повторении участка программы он производит отдельную порцию информации, которая должна быть обработана пользователем. Потребитель также является циклическим процессом. При каждом повторении он обрабатывает следующую порцию информации, выработанную производителем. Отношение производитель-потребитель подразумевает односторонний канал связи, по которому могут передаваться порции информации. Предположим, что процессы связаны через буфер неограниченной емкости, то есть произведенные порции не обязательно должны немедленно потребляться, а могут образовывать в буфере очередь. Sem S; {S=0} parbegin {Производитель} begin L1: Производство новой порции; Добавление порции к буферу; V(S); goto L1; end; {Потребитель} begin L2: Производство новой порции; Добавление порции к буферу; P(S); goto L2; end; parend Для решения этой задачи использовался общий семафор. Можно решить эту задачу и с использованием бинарного семафора. В общем случае общий семафоры являются избыточными, то есть, любую задачу, которую можно решить с помощью общего семафора, можно решить с помощью бинарного. Но, поскольку такие решения оказываются более сложными, общие семафоры используются до настоящего времени. Задача об обедающих философах Задача об обедающих философах скорее занимательная, чем практическая. Однако, она аналогична некоторым реальным задачам, в которых процессу необходим доступ более чем к одному ресурсу. Пять философов сидят возле круглого стола. Они проводят жизнь, чередуя приемы пищи и размышления. В центре стола находится большое блюдо с пищей. Пища такова (например, достаточно длинные макароны), чтобы, ее кушать необходимы одновременно две вилки (в каждой руке по одной). У философов имеется всего 5 вилок. Между каждой парой философов лежит одна вилка. Философы договорились, что они будут пользоваться вилками, которые лежат только непосредственно справа или слева от них. Задача – написать программу, моделирующую поведение философов. Программа должна избегать ситуации, в которой все философы голодны, но не один из них не может взять две вилки, например, каждый держит вилку в левой руке и не хочет ее отдавать. Очевидно, что два сидящих рядом философа, не могут есть одновременно. Кроме того, поскольку вилок 5 – одновременно не могут есть более двух философов. Предположим, что периоды раздумий и приема пищи различны – для их имитации в программе можно использовать датчик случайных чисел. Промоделируем поведение философов следующим образом. {Процесс – поведение философа} begin L1: Поразмыслить; Взять вилки; Поесть; Отдать вилки; goto L1; End Для решения задачи нужно запрограммировать операции «взять вилки» и «отдать вилки». Каждая вилка похожа на блокировку критической секции – ей в любой момент может владеть только один философ. Следовательно, вилки можно описать массивом семафоров, инициализированных 1. Взятие вилки при этом можно моделировать P-операцией над соответствующим семафором, освобождение V-операцией. Процессы, по существу, идентичны, поэтому естественно полагать, что они выполняют одинаковые действия. Например, каждый процесс может сначала взять левую вилку, а потом правую. Однако, это может привести к взаимной блокировке процессов. Например, если все философы возьмут свои левые вилки, то они навсегда останутся в ожидании правых вилок. Необходимое условие взаимной блокировки – возможность кругового ожидания, то есть когда один процесс ждет ресурс, занятый вторым процессом, который, в свою очередь, ждет ресурс, занятый третьим процессом и так далее. Таким образом, чтобы обеспечить невозможность взаимной блокировки, достаточно обеспечить невозможность кругового ожидания. Для этого можно заставить один из процессов взять сначала правую вилку. Решение задачи об обедающих философах Sem fork[5]=(1,1,1,1,1); {В начале процесса каждая вилка свободна} parbegin {Процесс 1 – первый философ} begin while(true) do begin P(fork[1]); P(fork[2]); {Взять сначала левую, потом правую} Поесть; V(fork[1]); V(fork[2]); {Отдать сначала левую, потом правую} Поразмыслить; end; end; {Процессы 2, 3 и 4 аналогичны процессу 1} {Процесс 5 – пятый философ} begin while(true) do begin P(fork[0]); P(fork[4]); {Взять сначала правую, потом левую} Поесть; V(fork[0]); V(fork[4]); {Отдать сначала правую, потом левую} Поразмыслить; end; end; parend. Счетчики событий и секвенсоры Как альтернатива семафорам, были предложены типы данных «счетчик событий» и «секвенсор». Для них разработаны операции, ориентированные на поддержку всех видов параллельного выполнения. Эти типы данных позволяют определить событие и подсчитать, сколько раз оно произошло, начиная с заданного момента времени. Человеку проще представить, что в мультипроцессорной системе событие произошло в 11-й или 12-й раз, чем интерпретировать следующее событие семафора: 1 (событие произошло в 11-й раз), 0 (событие обработано), 1 (событие произошло в 12-й раз) и т.д. Кроме того, значения счетчиков доступны процессам посредством операций соответствующего объекта, и могут использоваться, например, для определения порядка действий процесса. Счетчики событий могут быть представлены целым числом, значение которого изначально равно 0. Их методы определяются следующим образом: - advance() – увеличение значения счетчика на 1 и возвращение нового значение; - read() – возвращает текущее значение; - await(int value) – приостанавливает выполнение процесса до тех пор, пока значение счетчика не достигнет значения value. Секвенсоры используются для упорядочения действий параллельно выполняющихся процессов, и используется вместе со счетчиками событий. Их можно представить положительными целыми числами, изначально инициализированные 0. Для секвенсоров определена только одна операция ticket(), увеличивающая значение секвенсора на 1 и возвращающая результат. Достоинства и недостатки счетчиков событий и секвенсоров Тот факт, что значения счетчиков событий и секвенсоров, в отличие от семафоров, в процессе работы увеличиваются с каждым вызовом соответствующего метода, и не может быть уменьшен, облегчает их реализацию и использование. Дополнительным достоинством счетчиков событий является то, что процессы могут считывать его значение, но не могут его записывать. Однако, счетчики событий имеют одно слабое место: процессам доверяется задавать значение операции await(). Взаимодействующие процессы будут стараться задавать его правильно, но соревнующиеся процессы могут попытаться выполнить свои действия вне очереди, используя меньшее значение. Еще одну проблему представляет потенциальная задержка, и даже блокировка. Как и семафоры, счетчики событий и секвенсоры являются низкоуровневыми управляющими объектами, что приводит и к аналогичным проблемам. В настоящее время счетчики событий и секвенсоры используются крайне редко. Литература 1) Операционные системы / Д. Бэкон, Т. Харрис. – СПб.: Питер; Киев: Издательская группа BHV, 2004 2) Языки программирования / под. ред. Ф. Женюи. – М.: Мир, 1972. Лекция 15 Мониторы План лекции: 1) Понятие монитора 2) Операции над мониторами 3) Условная синхронизация Семафоры являются фундаментальным механизмом синхронизации. Однако семафоры – низкоуровневый механизм и при их использовании легко допустить ошибку. Например, программист должен следить за тем, чтобы случайно не пропустить вызовы P и V операций. Семафоры глобальны по отношению ко всем процессам, поэтому чтобы разобраться, как используется семафор, приходится просматривать всю программу. Наконец, при использовании семафоров взаимное исключение и условная синхронизация программируются одной и той же парой примитивов. Из-за этого трудно понять, для чего используются конкретные P и V операции, не просматривая другие операции с данными семафорами. Взаимное исключение и условная синхронизация - разные понятия, поэтому их желательно программировать разными способами. Мониторы – это программные модули, которые обеспечивают большую структурированность, чем семафоры. В первую очередь, мониторы являются механизмом абстракции данных. Монитор инкапсулирует представление абстрактного объекта и обеспечивает набор операций, с помощью которых объект обрабатывается. Монитор содержит переменные, хранящие состояние объекта, и процедуры, реализующие операции над ним. Процесс получает доступ к переменным в мониторе только путем вызова процедур этого монитора. Взаимное исключение обеспечивается неявно тем, что процедуры в одном мониторе не могут выполняться параллельно. Условная синхронизация в мониторах обеспечивается явно с помощью условных переменных. Они похожи на семафоры, но имеют и существенные отличия. Параллельная программа, использующая мониторы, содержит два типа модулей, активные процессы и пассивные мониторы. При условии, что все разделяемые переменные находятся внутри мониторов, два процесса взаимодействуют, вызывая процедуры одного и того же монитора. Получаемая модульность имеет два важных преимущества. 1. Процесс, вызывающий процедуру монитора, может ничего не знать о конкретной реализации процедуры. 2. Программист монитора может не заботиться о том, где и как используются процедуры монитора и свободно изменять их реализацию, не меняя при этом видимых процедур и результатов их работы. Эти преимущества позволяют разрабатывать процессы и мониторы относительно независимо, что облегчает создание и понимание параллельных программ. Благодаря своей полезности и эффективности, мониторы применяются в нескольких языках программирования, например в Java. Лежащие в основе мониторов механизмы синхронизации реализованы в операционной системе Unix. Монитор используется, чтобы сгруппировать представление и реализацию разделяемого ресурса (класса). Он состоит из интерфейса и тела. Интерфейс определяет представляемые ресурсом операции (методы). Тело содержит переменные, представляющие состояние ресурса, и процедуры, реализующие операции интерфейса. В разных языках программирования мониторы объявляются и создаются разными способами. Будем описывать монитор следующим образом. Monitor mname{ Объявление постоянных переменных; Операторы инициализации; Процедуры } Процедуры реализуют видимые операции, переменные разделяются всеми процедурами тела монитора. Переменные называются постоянными, поскольку существуют и сохраняют свое значение до тех пор, пока существует монитор. В процедурах, как и всегда, можно использовать локальные переменные, копии которых создаются при каждом вызове метода. Монитор, как представитель абстрактных типов данных, обладает следующими тремя свойствами. 1. Вне монитора видны только имена процедур. Чтобы изменит состояние ресурса, представленного постоянными переменными, процесс должен вызвать одну из процедур монитора. 2. Операторы внутри монитора (в объявлениях и процедурах) не могут обращаться к переменным, объявленным вне монитора. 3. Постоянные переменные монитора инициализируются до вызова его процедур. Это реализуется путем выполнения инициализирующих операторов при создании монитора и, следовательно, до вызова его процедур. Одно из привлекательных свойств монитора, как и любого абстрактного типа данных, заключается в возможности его относительно независимой разработки. Это означает, однако, что программист монитора не может знать заранее порядка вызова его процедур. Поэтому полезно определить предикат, истинный и независимый от порядка выполнения вызовов. Инвариант монитора – это предикат, определяющий «разумные» состояния постоянных переменных монитора. Код инициализации монитора должен создать состояние, соответствующее инварианту, а каждый метод должен его поддерживать. Монитор отличается от абстракции данных в последовательных языках программирования тем, что совместно используется параллельно выполняемыми процессами. Поэтому чтобы избежать взаимного влияния в процессах, выполняемых в мониторах, может потребоваться взаимное исключение, а для приостановки работы до выполнения определенного условия – условная синхронизация. Синхронизацию проще понимать и программировать, если взаимное исключение и условная синхронизация реализуется разными способами. Лучше всего, если взаимное исключение происходит не явно, что автоматически устраняет взаимное влияние. Кроме того, такие программы проще читать, поскольку в них нет явных протоколов входа в критические секции и выхода из них. Условную синхронизацию лучше программировать явно, поскольку разные программы могут потребовать различных условий синхронизации. В соответствии с этими замечаниями, взаимное исключение реализуется в мониторах неявно, а условная синхронизация программируется с использованием, так называемых, условных переменных. Внешний процесс вызывает метод монитора. Пока некоторый процесс выполняет операторы метода – он активен. В любой момент времени может быть активным только один экземпляр метода, то есть методы монитора по умолчанию выполняются с взаимным исключением. Это обеспечивается реализацией языка, библиотекой или операционной системой, но не программистом, реализующим монитор. Условная переменная используется для приостановки работы процесса в случае, когда продолжение работы процесса невозможно до перехода монитора в состояние, удовлетворяющее некоторому логическому условию. Условные переменные можно объявлять и использовать только в пределах мониторов. Значением условной переменной является очередь приостановленных процессов (очередь задержки). Вначале очередь пуста. Программист не может напрямую обращаться к значению условной переменной. Вместо этого он получает доступ к очереди с помощью нескольких специальных операций. Empty(cv) – если очередь условной переменной cv пуста, то возвращается TRUE, если не пуста – FALSE. Wait(cv) – заставляет рабочий процесс задержаться в конце очереди условной переменной cv. Чтобы другой процесс мог в конце концов войти в монитор для запуска приостановленного процесса, выполнение операции wait отбирает у процесса, вызвавшего эту операцию, исключительный доступ к монитору. Signal(cv) – запуск процесса, заблокированного на условной переменной cv. Проверяется очередь задержки условной переменной cv. Если она пуста, то никакие действия не производятся. Если приостановленные процессы есть, то оператор Signal(cv) запускает процесс, находящийся в начале очереди условной переменной cv. Таким образом, Wait и Signal обеспечивают порядок сигнализации FIFO: процессы приостанавливаются в порядке вызовов операции Wait, а запускаются в порядке вызова операции Signal. Дисциплины синхронизации При выполнении операции Signal, процесс работает в мониторе и, следовательно, может управлять блокировкой, неявно связанной с монитором. В результате возникает дилемма: если операция Signal запускает другой процесс, то получается, что могли бы выполняться два процесса – вызвавший операцию Signal и запущенный ею. Но следующим может выполняться только один из них (даже на многопроцессорных системах), так как только один процесс может иметь исключительный доступ к монитору. Таким образом, возможны два варианта. 1. «Сигнализировать и продолжить» - сигнализатор продолжает работу, а процесс, получивший сигнал, выполняется позже. 2. «Сигнализировать и ожидать» - сигнализатор ждет некоторое время, а процесс, получивший сигнал, выполняется сразу. Дисциплина (порядок) обслуживания «Сигнализировать и продолжить» не прерывает обслуживание. Процесс, вызвавший Signal, сохраняет исключительный доступ к монитору, а запускаемый процесс начинает работу позже, когда получит исключительный доступ к монитору. По-существу, операция Signal просто указывает запускаемому процессу на возможность выполнения, после чего он помещается в очередь процессов, ожидающих блокировки на мониторе. Диаграмма состояний, иллюстрирующая работу синхронизации в мониторах, показана на рисунке. Вызывая процедуру монитора, процесс помещается во входную очередь, если в мониторе выполняется другой процесс; в противном случае вызвавший операцию процесс немедленно начинает выполнение на мониторе. Когда монитор освобождается, один процесс из входной очереди может перейти к работе на мониторе. Выполняя операцию Wait(cv), процесс переходит от работы в мониторе в очередь, связанную с условной переменной. Если процесс выполняет операцию Signal(cv), то при дисциплине «Сигнализировать и продолжить», то процесс из начала очереди условной переменной переходит во входную очередь. При дисциплине «Сигнализировать и ожидать» процесс, выполняемый на мониторе, переходит во входную очередь, а процесс из начала очереди условной переменной переходит к выполнению в мониторе. Дополнительные операции с условными переменными Часто оказываются полезными следующие операции с условными переменными: приоритетная wait, minrank и signal-all. Все они имеют простую семантику и могут быть эффективно реализованы, поскольку обеспечивают лишь дополнительные действия над очередью, связанной с условной переменной. Wait(cv, rank) – ждать в порядке возрастания ранга (приоритета). Приоритетный wait. Minrank(cv) – значение ранга процесса в начале очереди ожидания. Signal-all(cv) – запустить все процессы очереди и продолжить. Приоритетная wait позволяет влиять на порядок постановки в очередь и их запуска. Процессы приостанавливаются на условной переменной cv в порядке возрастания rank и в том же порядке запускаются. При равенстве рангов запускается процесс, ожидавший дольше всех. Для избегания потенциальных проблем, связанных с совместным применением обычного и приоритетного wait для одной переменной, при программировании желательно использовать один тип оператора wait. Для задач планирования, в которых используется приоритетный wait, полезно иметь возможность определять ранг процесса, находящегося в начале очереди задержки. Вызов minrank(cv) возвращает ранг приостановленного процесса, расположенного в начале очереди задержки на условной переменной cv, при условии, что очередь не пуста и для процесса в начале очереди был использован приоритетный wait. В противном случае возвращается некоторое произвольное целое число. Оповещающая операция signal-all используется, если можно возобновить более одного приостановленного процесса или если процессор-сигнализатор не знает, какие из приостановленных процессов могли бы продолжить работу. Выполнение операции signal-all(cv) запускает все процессы, приостановленные на условной переменной cv. Операция signal-all вполне определена, когда монитор использует дисциплину «сигнализировать и продолжить», поскольку процесс, выработавший сигнал, всегда продолжает работать в мониторе. При использовании дисциплины «сигнализировать и ожидать» эта операция определена не точно, поскольку становится возможным передать управление более чем одному процессу и дать каждому из этих процессов исключительный доступ к монитору. Разработал – к.т.н., доцент Митрошин А.А.