гуд работа. Курс лекций теория вычислительных процессов
 Скачать 1.54 Mb.
|
|
FIFO алгоритм. Выталкивание первой пришедшей страницы. Простейший алгоритм. Каждой странице присваивается временная метка. Реализуется это просто соз- данием очереди страниц, в конец которой страницы попадают, когда загружаются в физическую па- мять, а из начала берутся, когда требуется освободить память. Для замещения выбирается старейшая страница. К сожалению, эта стратегия с достаточной вероятностью будет приводить к замещению ак- тивно используемых страниц, например, страниц текстового процессора. Заметим, что при замещении активных страниц все работает корректно, но fault происходит немедленно. Аномалия Belady Интуитивно ясно, что чем больше страничных кадров имеет память, тем реже будут иметь место page fault'ы. Удивительно, но это не всегда так. Как установил Belady с коллегами, определенные последова- тельности обращений к страницам приводят в действительности к увеличению числа страничных нару- шений при увеличении кадров, выделенных процессу. Это явление носит название аномалии FIFO. Три кадра (9 faults) оказываются лучше чем 4 кадра (10 faults) для 012301401234 цепочки чередования страниц при выборе стратегии FIFO. Рис. 10.1 Аномалия Belady. (a) FIFO с тремя страничными кадрами. (b) FIFO с четырьмя страничными кадрами. 72 73 Аномалию FIFO следует считать скорее курьезом, чем фактором, требующим серьезного отношения, который иллюстрирует сложность ОС, где интуитивный подход не всегда приемлем. Оптимальный алгоритм Одно из последствий открытия аномалии Belady - поиск оптимального алгоритма. Этот алгоритм имеет минимальную частоту fault'ов среди всех алгоритмов. Он прост: замещай страницу, которая не будет использоваться в течение длительного периода времени. Каждая страница помечается числом инструкций, которые будут выполнены, прежде чем на эту стра- ницу будет сделана первая ссылка. Этот алгоритм нереализуем. ОС не знает, к какой странице будет следующее обращение. (Ранее такие проблемы были с планированием процессов - алгоритм SJF). Для второго обращения уже можно делать прогноз на основе информации собранной после первого обращения. Зато из этого можно сделать вывод, что для того, чтобы алгоритм замещения был максимально близок к идеальному алгоритму, система должна как можно точнее предсказывать будущие обращения процес- сов к памяти. Данный алгоритм применяется для оценки качества реализуемых алгоритмов. Выталкивание дольше всего не использовавшейся страницы. LRU (The Least Recently Used) Algo- rithm . Исходим из эвристического правила, что недавнее прошлое - хороший ориентир для прогнозирования ближайшего будущего. Ключевое отличие между FIFO и оптимальным алгоритмом в том, что один смотрит назад, а другой вперед. Если использовать прошлое, для аппроксимации будущего, имеет смысл замещать страницу, которая не использовалась в течение долгого времени. Такой подход называется least recently used (LRU) алгоритм. LRU часто используется и считается хорошим. Основная проблема - реализация. Необходимо иметь связанный список всех страниц в памяти, в начале которого будут часто используе- мые страницы. Причем он должен обновляться при каждой ссылке. Много времени нужно на поиск страниц в списке. Есть вариант реализации со специальным устройством. Например, - иметь 64-битный указатель, кото- рый автоматически увеличивается на 1 после каждой инструкции и в таблице страниц иметь соответст- вующее поле, в которое заносится значение указателя при каждой ссылке на страницу. При возникно- вении page fault'а выгружается страница с наименьшим указателем. Как оптимальный алгоритм, так и LRU не страдают от аномалии Белейди. Существует класс алгорит- мов, называемых стековыми (stack) алгоритмами, которые не проявляют аномалии Белейди. Это алго- ритмы, для которых множество страниц в памяти для n кадров всегда подмножество страниц для n+1 кадра. LRU таковым является. Заметим, что никакая реализация LRU неприемлема без специального оборудования помимо стандарт- ных регистров. Если, например, задействовать прерывание для модификации полей, то это будет замед- лять ссылку к памяти в 10 раз. Выталкивание редко используемой страницы. NFU (Not Frequently Used) алгоритм. Программная реализация алгоритма, близкого к LRU. Рассмотренные варианты LRU в принципе реализуемы, но, как уже отмечалось, они требуют специаль- ной аппаратной поддержки, которой большинство современных процессоров не предоставляет. Поэто- 74 му хотелось бы иметь алгоритм, достаточно близкий к LRU, но не требующий сложной специальной поддержки. Один из таких возможных алгоритмов - это алгоритм NFU. Для него требуются программные счетчики, по одному на каждую страницу, которые сначала равны нулю. При каждом прерывании по времени (а не после каждой инструкции) операционная система сканирует все страницы в памяти и у каждой страницы с установленным флагом обращения увеличивает на единицу значение счетчика, а флаг обращения сбрасывает. Таким образом, кандидатом на освобождение оказывается страница с наименьшим значением счетчика, как страница, к которой реже всего обращались. Главным недостатком алгоритма NFU является то, что он никогда ничего не забывает. Например, страница, к которой очень много обращались некоторое вре- мя, а потом обращаться перестали, все равно не будет удалена из памяти, потому что ее счетчик содер- жит большую величину. Например, в многопроходных компиляторах страницы, которые активно ис- пользовались во время 1-го прохода, могут надолго сохранить большие значения счетчика, мешая за- грузке полезных в дальнейшем страниц. К счастью, возможна небольшая модификация алгоритма, которая реализует "забывание". Достаточно, чтобы при каждом прерывании по времени содержимое каждого счетчика сдвигалось вправо на 1 бит, а уже затем производилось бы его увеличение для страниц с установленным флагом обращения (рис. 3-27 Таненбаум). Другим, уже не так просто устранимым недостатком алгоритма является длительность процесса скани- рования таблиц страниц. Другие алгоритмы Для полноты картины можно упомянуть еще несколько алгоритмов. Например, алгоритм Second-Chance - модификации FIFO, которая позволяет избежать потери часто ис- пользуемых страниц - анализ бита r (reference) для самой старой страницы. Если бит 1, то страница в отличие от FIFO не выталкивается, а очищается бит и страница становится в конец очереди. Если на все страницы ссылались, он превращается в FIFO. Данный алгоритм использовался в BSD Unix. В компьютере Макинтош использован алгоритм NRU(Not Recently-Used), где страница жертва выбира- ется на основе анализа битов модификации и ссылки. Имеется также и много других алгоритмов замещения. Объем этого курса не позволяет рассмотреть их подробно. Подробное описание различных алгоритмов замещения имеется в монографиях Дейтела, Цикритиса, Таненбаума и др. Заключение Описанная система управления памятью является совокупностью программно-технических средств, обеспечивающих производительное функционирование современных компьютеров. Успех реализации той части ОС, которая относится к управлению виртуальной памятью, определяется близостью архи- тектуры аппаратуры, поддерживающей виртуальную память, к абстрактной модели виртуальной памяти ОС. Для справедливости заметим, что в подавляющем большинстве современных компьютеров аппара- тура выполняет функции, существенно превышающие потребности модели ОС, так что создание аппа- ратно-зависимой части подсистемы управления виртуальной памятью ОС в большинстве случаев не яв- ляется чрезмерно сложной задачей. 75 10. Асинхронное программирование 10.1. Основные понятия В асинхронной модели вычислений предполагается, что программа выполняется на мультипроцессо- ре(несколько процессорных узлов над общей разделяемой памятью) или на мультикомпьютере (не- сколько процессорных узлов, каждый из которых состоит из процессора, собственной оперативной па- мяти, устройства управления и т п. Таким образом, каждый процессорный узел является полным ком- пьютером). Асинхронная программа представляет систему независимо исполняющихся взаимодейст- вующих процессов. Существует много различных воплощений этой модели вычислений в различных языках программирования. Мы рассмотрим эту модель в весьма общем виде. 10.1.1 Понятие асинхронной программы Асинхронная программа (А-программа) - это конечное множество А-блоков {A k | k ∈ {1, 2, ..., m}}, оп- ределенных над информационной IM и управляющей СМ памятями. Каждый А-блок A k = <tr(ak),ak, c(ak) > состоит из спусковой функции tr(ak) (trigger function), управляю- щего оператора c(ak) и операции ak, ak ∈ F. Памятью называется конечное множество всех ячеек, способных хранить значения переменных. Спусковая функция tr(ak) - это предикат, в программе обычно задается условным выражением либо ло- гической функцией. Как обычно, операция ak реализуется в программе одноименной процедурой, вы- числяющей функцию ƒa. Управляющий оператор c(ak) - оператор присваивания или процедура, меняющая значения ячеек управляющей памяти СМ (например, чтобы разрешить или запретить исполнение какого-нибудь А- блока). Каждой переменной из in(ak) ∪ out(ak) в памяти IМ соответствует ячейка, в которой хранится ее значе- ние. Выполнение А-программы состоит: • в вычислении значения спусковой функции tr(ak) для всех или части А-блоков; • выполнении одного, части или всех А-блоков A k так что (tr(ak) = true при текущем состоянии памяти IM ∪ СМ. Исполняющая система, таким образом, имеет право инициировать любое подмножество А-блоков, го- товых к исполнению (с истинной tr(ak)), в зависимости от имеющихся в наличии свободных на этот момент ресурсов. Понятно, что при разных исполнениях асинхронной программы на каждом этапе ис- полнения будут инициированы, вообще говоря, разные подмножества А-блоков. Это обстоятельство (недетерминизм) сильно усложняет отладку асинхронной программы. А-программа считается завершенной, когда ни один блок не выполняется и ни один А-блок не может быть инициирован, так как для всех к = 1, ..., m значение tr(ak) = false. Выполнение А-блока А k состоит в исполнении: • процедуры ak с теми значениями, которые имеют переменные из in(ak) в текущий момент, при этом вычисляются значения переменных из out(at); • управляющего оператора c(ak) Таким образом, спусковые функции и управляющие операторы - это те средства, с помощью которых задается управление в асинхронных программах. Пример 1 integer x, y, z; input (х,у,z) asynchronous_do % tr(ak) ak % x < yVx < z → x: = x + 1; y < zVy < x → y: = y + 1; z < xVz < y → z: = z + 1; end_do Программа "примера 1" позволяет в некотором порядке уравнять значения переменных x, у, z, доведя их с помощью прибавления единицы до значения наибольшей их них (рис. 10.1). Это программа макси- мальной непроцедурности, в ней нет ограничений, которые бы не были обусловлены наличием инфор- мационной зависимости между операторами. Рис 10.1 Пример 2 Большая непроцедурность часто мешает эффективно выполнить программу и в таких случаях требуется уменьшать непроцедурность программы (представления алгоритма). Для программы "примера 1" это можно сделать, убрав дизъюнктивные члены из спусковых функций, что усилит управление (увеличит множество ограничений в нем). integer x, y, z; input (х,у,z) asynchronous_do % tr(ak) ak % x < y → x: = x + 1; y < z → y: = y + 1; z < x → z: = z + 1; end_do Пример 3 Программа данного примера отличается от программы "примера 2" тем, что в спусковые функции до- бавлены новые конъюнктивные и дизъюнктивные члены. Они добавляют новые ограничения в управле- ние, и в результате получается почти последовательная программа. Параллельное выполнение двух А- блоков возможно лишь при условии равенства значений двух переменных (при равенстве значений всех трех переменных программа завершается). Попробуйте превратить эту программу в последовательную. input (x,y,z) asynchronous_do % ________tr(ak)_____________________ _ak _ % x < z & x < y V(x:=z&x Пример 4 В примерах 1...З А-блоки не имели управляющего оператора (более точно, был пустой управляющий оператор). Рассмотрим теперь организацию конвейерного исполнения А- блоков. Схема программы по- казана на рис. 10.2. Рис 10.2 Асинхронная программа, реализующая этот конвейер (в программе не показаны переменные, обрабаты- ваемые этой программой, программа демонстрирует только конструирование управления), может иметь вид integer x,y, z; asynchronous_do х: = 1; y: = z: = 0; % tr(ak) ak c(a k ) % x = 1 →ƒ1 [y: = 1; x: = 0]; y = 1 →ƒ2 [z: = 1; y: = 0]; P&z = 1 →ƒ3 [x: = 1; z: = 0]; end_do В этой программе операторы х:=1; y:=z:=0 присваивают значения управляющим переменным. Они раз- решают инициировать операцию ƒ1 и запрещают инициирование операций ƒ2 и ƒ3. Таким образом, в начальный момент времени сможет быть инициирован только А-блок ƒ1. После выполнения операции ƒ1 управляющий оператор с1 (здесь это оператор [у:=1; х:=0]) запретит исполнение А-блока ƒ1 и раз- решит исполнение А-блока ƒ2 и т.д. Цикл конвейера завершится, когда предикат Р станет ложным и не позволит инициировать А-блок ƒ3. Широко известным примером асинхронного программирования является message passing interface. Этот метод программирования определяет программу как систему взаимодействующих процессов и стандар- тизует обмен данными. Обмен всегда происходит через каналы, связывающие два процесса. Такой ка- нал реализуется очередью сообщений, каждый процесс сам определяет свою готовность начать испол- нение или завершить его. Асинхронное программирование оказалось весьма трудоемким делом, особенно отладка программы, в силу обилия возможностей совершить ошибки в синхронизации процессов. Рассмотрим некоторые про- блемы асинхронного программирования. 10.1.2. Некорректное вычисление данных Возникновение некорректных данных иллюстрирует следующий простой пример. Пусть необходимо начислить зарплату и вычислить сумму денег, подлежащих выдаче на руки. Оставляя в стороне излиш- ние здесь детали, будем предполагать, что зарплату составляют некоторая базисная зарплата N 0 плюс надбавки N 1 , N 2 , ..., N n (выражаются в процентах к базисной зарплате) минус налог N n-1 (выражаются в процентах к начисленной сумме). Пусть процессы Р 0 , P 1 , Р 2 , ... , Р n , Р n+1 соответственно выполняют эти операции. Понятно, что для вы- числения корректного результата процесс Р n-1 , вычисляющий сумму налога, должен выполняться по- 77 78 следним, процесс Р 0 -первым, а процессы P 1 , Р 2 , ..., Р n могут исполняться в любом порядке, в том числе и параллельно, хотя само суммирование должно, конечно, выполняться последовательно. Все другие варианты выполнения процессов приведут к некорректным результатам. Такого сорта ошибки асинхронных программ крайне неприятны, трудно локализуемы и неповторимы. Если позволить процессам Р 1 , P 2 ,..., Р n , Р n-1 выполняться асинхронно, то при разных выполнениях асин- хронной программы могут получаться разные результаты и повторить предшествующее тестирование удастся только случайным образом. Понятно, что (Р 0 + P 1 + P n-1 + P 2 + ... + Р n ) ≠ (Р 0 + P n-1 + P 1 + Р 2 + ... + Р n ), здесь имеется в виду, что процессы выполняются в написанном порядке. 10.1.3. Некорректное считывание данных Следующий пример иллюстрирует этот тип ошибки. Пусть в банке А есть счет acc1, на котором нахо- дится 500 тыс. руб., а в банке В - счет асс2, на котором находится 300 тыс. руб, и необходимо переслать 100 тыс. руб. со счета асc1 на счет асс2. Сумма денег на обоих счетах неизменна до и после выполнения пересылки и равна 800 тыс руб. Пусть процесс P 1 посылает деньги из банка А в банк В, а процесс Р 2 принимает посланные деньги в банке B. Процессы схематически могут быть описаны так: Первоначально А.асс1 = 500 тыс. руб. В.асс2 = 300 тыс. руб. Процесс Р 1 Процесс Р 2 А.асc1: = А.асc1 - 100; receive (x,A,y); x: = 100 send (x, B, y); B.acc2: = B.acc2 + y; Результат A.acc1 = 400 тыс. руб. B.acc2 = 400 тыс. руб. В процессе Р 1 счет А.асс1 вначале уменьшается на 100 тыс. руб., а затем 100 тыс.руб. посылаются в банк В. В процессе Р 2 сначала принимаются 100 тыс. руб. из банка A, а затем увеличивается сумма на счету В.асс2. Однако процесс Р, контролирующий перевод денег и проверяющий сохранение значения суммы А.асс1 + В.асс2, может считывать ошибочные данные. Понятно, что если Р будет считывать данные строго до или после выполнения операции перевода денег, то результат суммирования будет одинаков. Однако в ходе выполнения процессов P 1 и Р 2 при разных вариантах считывания значений А.асс1 и В.асс2 сумма А.асс1 + В.асс2 может равняться 700 тыс.руб. (если значение А.асс1 было считано после его изменения, а значение В.асс2 - до изменения) , 800 тыс. руб. и 900 тыс.руб. при других возможнык вариантах счи- тывания данных. 10.2. Сети Петри Сети Петри - это математическая модель, которая имеет широкое применение для описания поведения параллельных устройств и процессов. В настоящее время определены и изучены разнообразные классы сетей Петри. Мы рассмотрим самые общие понятия и возможности использования сетей Петри для за- дания прямого управления в параллельных программах. 10.2.1. Определение сети Петри |