Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

21

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

Кафедра 304

ЭЛЕМЕНТЫ ОПЕРАЦИОННЫХ СИСТЕМ ЭВМ

Лабораторные работы

Ю.А.Голубков

Москва, 2001

Лабораторная работа №10

АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ МУЛЬТИПРОГРАММНЫХ

ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

В данной лабораторной работе определение производительности мультипрограммной ВС с равномерным квантованием времени и учетом ввода-вывода будет рассмотрено по методу, описанному в работе Дрейка.

10.1. Анализ влияния параметров ВС на производительность

Предполагается, что в ОЗУ находится n процессов, которые обслуживаются равноправно с равномерным квантованием времени. Далее предполагается, что все процессы имеют одинаковый процент времени ожидания ввода-вывода - .

При моделировании системы используется аппарат цепей Маркова. Система может пребывать в следующих состояниях:

S₀ - все процессы_, кроме одного, находятся в состоянии готовности, один из них выполняется;

S_i - i процессов находятся в состоянии ожидания ввода-вывода;

S_n – все n процессов ожидают завершения обмена, т.е. процессы блокированы, процессор простаивает.

Требуется оценить вероятность P_n пребывания системы в состоянии S_n.

Диаграмма состояний и переходов аналогична модели марковского процесса размножения-гибели приведена на рис.10.1.

а) запрос

на вв/выв

dt dt dt … dt

S₀ S₁ S₂ S_n

dt 2dt 3dt ndt

завершение вв/выв

Рис. 10.1

Дуга перехода определена вероятностью этого перехода. Определим dt как вероятность блокировки обслуживаемого процесса вследствие выдачи им запроса на ввод-вывод к моменту следующего наблюдения (1/ - представляет средний интервал между запросами на ввод-вывод). Аналогично dt представляет вероятность завершения ввода-вывода к следующему моменту наблюдения (1/ - среднее время обслуживания запроса на ввод-вывод). Следует обратить внимание, что дуга перехода из S₂ в S₁ имеет вес 2dt. Это следует из предположения, что оба запроса на ввод-вывод независимо обслуживаются отдельными каналами и вероятность того, что к следующему моменту закончится выполнение хотя бы одного из запросов, равна

dt + dt = 2dt

По аналогии переходу из состояния i в (i-1) соответствует вероятность idt. Для систем без мультипрограммирования процент времени ожидания ввода-вывода

Для упрощения модели предполагается, что:

1) число переходов S_i  S_i+1 равно числу переходов S_i+1  S_i (выполняется условие стационарности P_i,i+1 P_i= P_i+1,i P_i+1 ).

Отсюда имеем:

dt P₀=dt P₁

dt P₁=2dt P₂ (7.1)

_{. . .}

dt P_n-1=ndt P_n

2) Сумма вероятностей по всем состояниям системы

Далее можно определить вероятность P_n пребывания системы в состоянии S_n (когда все процессы блокированы, а процессор простаивает).

Из приведенной системы (7.1) следует:

Так как

Поскольку

Отсюда имеем:

Из системы (7.2) имеем:

Используя выражение для P₀, получим:

Тем самым можно построить таблицу для различных значений n и 0.1    0.95. Заметим, что  определяет коэффициент загрузки процессор – канал – УВВ.

10.2.Анализ влияния синхронизации на производительность ВС

Предполагается, что в системе используется n процессоров, где n1 (от 10 и больше). При работе мультипроцессорной системы следует различать два различных типа блокировок процессоров. Они различаются по тому, как используется процессор, обслуживающий прерванный процесс. Если при использовании семафоров для ожидания завершения обмена процессор освобождается и может обслуживать другой процесс, то в других случаях это не так. При использовании процессором команд типа TS (Text and Set) процессор вынужден непрерывно повторять цикл проверки байта блокировки ресурса до тех пор, пока он не будет сброшен в 0. Тем самым процессор «связывается» с ресурсом и не может использоваться до освобождения ресурса. Поэтому первый тип блокировки ресурса, при котором процессор может переключаться на обслуживание другого процесса, называется «освобождающей», а второй – «связывающей».

Для оценки влияния связывающих блокировок на производительность системы рассмотрим следующую модель. Процессоры предполагаются независимыми в своей работе. В качестве ресурса выступает некоторая, часто используемая, база данных.

Пусть в ходе выполнения отдельного процесса интервалы времени между обращениями к базе данных подчиняются обратному экспоненциальному закону распределения с параметром 1/E (т.е. математическое ожидание интервала времени между обращениями равно Е). Пусть математическое ожидание продолжительности интервала блокировки процессора равно L. Тогда отношение L/(E+L) дает грубую оценку доли времени пребывания ресурса в состоянии блокировки в мультипрограммной системе с одним процессором, (блокировки процессора не происходит). В мультипроцессорной системе каждый процессор может быть в одном из состояний:

1. производить обслуживание процесса, обращающегося к базе через интервалы времени, определяемые параметров 1/Е;

2. заниматься обработкой ресурса, защитив его байтом блокировки на период времени, характеризуемый параметров 1/L;

3. циклиться на проверке байта состояния базы данных по причине его программной блокировки.

Н



а рис.10.2 каждое состояние S_i отвечает ситуации, когда i процессоров пытаются получить доступ к базе данных. Один из них работает с базой данных, остальные i-1 ожидают ее освобождения.

S₀ S₁ S₂ … S_n-1 S_n

Рис. 10.2

Вероятность перехода из состояния i в состояние i-1 за время dt равна (1/L)dt. Это означает, что время обработки процессором блокированного от посторонних воздействий базового ресурса не зависит от числа процессоров, ожидающих его освобождения. Вероятность перехода из состояния i в состояние i+1 на интервале dt равна (n-1)(1/E)dt. Это соответствует тому факту, что каждый из еще не заблокированных (n-i) процессоров может запрашивать доступ к блокированному ресурсу с вероятностью (1/E)dt. Повторяя рассуждения, приведенные ранее для стационарного процесса, получаем, что:

Критерием производительности системы является среднее ожидаемое число процессоров, «простаивающих» из-за программных блокировок

Из приведенных соотношений:

Задание 10.1.

Спроектировать программу для определения состояния простоя процессора и построить графики для n=115 c шагом 1 и двух значений 

Задание 10.2.

Спроектировать программу для определения таблицы значений E_пр при варьировании параметров:

Число процессоров n=5,10,20,30,40,50 и (L/E) = 0.025, 0.05, 0.10, 0.20.

Лабораторная работа №11

Предотвращение тупиков по методу Дейкстры

(алгоритм банкира)

Тупиковой ситуации при распределении ресурсов ВС можно избежать, если рационально распределить ресурсы. Алгоритм Дейкстры имитирует действия банкира, который, располагая капиталом, выдает ссуды и принимает платежи. Его трансформация для процессов может быть представлена в такой форме.

Предположим, есть совокупность (пул) идентичных ресурсов в количестве t (например, НМЛ). Есть некоторое число процессов n. Пусть заранее известна максимальная потребность каждого процесса в ресурсе m(i), где i=1,..,n, необходимая ему для завершения. Ресурсы не выделяются процессу заранее до начала выполнения, а лишь по запросу в рамках текущего выполнения.

Пусть l(i) - текущее количество ресурса, уже выделенное процессу i, i=1,...,n, c(i) - текущая потребность, которая равна:

c(i) = m(i) - l(i), i=1,...,n.

Очевидно, что если процессом выделены к данному моменту ресурсов, то в системе остается свободными A ресурсов:

.

Введем определение надежного состояния. Это состояние, при котором общая ситуация с распределением ресурсов такова, что все процессы могут завершить свою работу. Ненадежное состояние такое, при котором такой возможности нет, т.е. не хватает ресурсов для завершения процессов.

Пример надежного состояния

В системе t=12. Число процессов n=3. Состояние системы определено таблицей 11.1.

Таблица 11.1

В данном состоянии в резерве есть 2 единицы свободного ресурса. Если удовлетворить процесс 2, блокируя другие процессы, то он может завершить работу и освободить шесть единиц ресурса. Эти единицы ресурса можно отдать процессу 1 и процессу 3 для их завершения.

Пример ненадежного состояния системы приведен в таблице 11.2, где n=3, t=12.

Таблица 11.2

Здесь в данный момент из 12 единиц ресурса 11 в работе, в резерве 1. Независимо от того, какой процесс запросит резервное устройство, нет гарантии, что все три процесса завершат работу.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лабораторной работы