Использование методологии мониторов для реализации параллельных процессов

Размещено на http://www.allbest.ru/

Министерство образования и науки РФ

Государственное образовательное учреждение высшего профессионального образования

«Пензенский государственный университет»

Кафедра «Вычислительная техника»

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА БАКАЛАВРА

на соискание степени бакалавра техники и технологии на тему

«Использование методологии мониторов для реализации параллельных процессов»

по направлению подготовки 230100 - информатика и вычислительная техника

Автор работы С.В. Киселев

Группа 08ВВ1

Руководитель работы

к.т.н., профессор С.А. Зинкин

Нормоконтроль

к.т.н., доцент А.В. Кучин

Пенза 2012г.

Реферат

Пояснительная записка содержит 70 листов, 22 рисунка, 4 листа формата А1, 8 источников.

Объектом исследования является автоматное представление программных алгоритмов параллельных программ, в которых используются мониторы.

Цель работы - разработка ГСА и представление их в виде автоматных моделей для дальнейшей работы с ними в рамках теории автоматов.

В работе рассматриваются основы методологии мониторов и устройство жесткого диска. Описываются решения задач планирования доступа к накопителю на магнитных дисках с применением мониторов, алгоритмы представляются в виде ГСА и автоматных моделей.

Введение

Параллельное программирование возникло в 1962 г. с изобретением каналов -- независимых аппаратных контроллеров, позволявших центральному процессору выполнять новую прикладную программу одновременно с операциями ввода-вывода других (приостановленных) программ. Параллельное программирование (слово параллельное в данном случае означает "происходящее одновременно") первоначально было уделом разработчиков операционных систем. В конце 60-х годов были созданы многопроцессорные машины. В результате не только были поставлены новые задачи разработчикам операционных систем, но и появились новые возможности у прикладных программистов.

Первой важной задачей параллельного программирования стало решение проблемы так называемой критической секции. Эта и сопутствующие ей задачи ("обедающих философов", "читателей и писателей" и т.д.) привели к появлению в 60-ё годы огромного числа научных работ. Для решения данной проблемы и упрощения работы программиста были разработаны такие элементы синхронизации, как семафоры и мониторы. К середине 70-х годов стало ясно, что для преодоления сложности, присущей параллельным программам, необходимо использовать формальные методы.

На рубеже 70-х и 80-х годов появились компьютерные сети. Для глобальных сетей стандартом стал Arpanet, а для локальных-- Ethernet. Сети привели к росту распределенного программирования, которое стало основной темой в 80-х и, особенно, в 90-х годах. Суть распределенного программирования состоит во взаимодействии процессов путем передачи сообщений, а не записи и чтения разделяемых переменных.

Сейчас стала заметной необходимость обработки с массовым параллелизмом, при которой для решения одной задачи используются десятки, сотни и даже тысячи процессоров. Также видна потребность в технологии клиент-сервер, сети Internet и World Wide Web. Наконец, стали появляться многопроцессорные рабочие станции и ПК. Параллельное аппаратное обеспечение используется больше, чем когда-либо, а параллельное программирование становится необходимым.

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

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

При любом виде взаимодействия процессам необходима взаимная синхронизация. Существуют два основных вида синхронизации -- взаимное исключение и условная синхронизация. Взаимное исключение обеспечивает, чтобы критические секции операторов не выполнялись одновременно. Условная синхронизация задерживает процесс до тех пор, пока не выполнится определенное условие. Например, взаимодействие процессов производителя и потребителя часто обеспечивается с помощью буфера в разделяемой памяти. Производитель записывает в буфер, потребитель читает из него. Чтобы предотвратить одновременное использование буфера и производителем, и потребителем (тогда может быть считано не полностью записанное сообщение), используется взаимное исключение. Условная синхронизация используется для проверки, было ли считано потребителем последнее записанное в буфер сообщение.

1. Описание методологии мониторов

Мониторы являются механизмом абстракции данных. Монитор инкапсулирует представление абстрактного объекта и обеспечивает набор операций, с помощью которых оно обрабатывается. Монитор содержит переменные, хранящие состояние объекта, и процедуры, реализующие операции над ним. Процесс получает доступ к переменным в мониторе только путем вызова процедур этого монитора. Взаимное исключение обеспечивается неявно тем, что процедуры в одном мониторе не могут выполняться параллельно. Это похоже на неявное взаимное исключение, гарантируемое операторами await. Условная синхронизация в мониторах обеспечивается явно с помощью условных переменных (condition variable).

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

Благодаря своей полезности и эффективности мониторы применяются в нескольких языках программирования. Лежащие в основе мониторов механизмы синхронизации (неявное исключение и условные переменные для сигнализации), реализованы также в операционной системе Unix. Наконец, условные переменные поддерживаются несколькими библиотеками программирования.

1.1 Синтаксис и семантика

Монитор используется, чтобы сгруппировать представление и реализацию разделяемого ресурса (класса). Он состоит из интерфейса и тела. Интерфейс определяет предоставляемые ресурсом операции (методы). Тело содержит переменные, представляющие состояние ресурса, и процедуры, реализующие операции интерфейса.

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

monitor mname {

объявления постоянных переменных

операторы инициализации

процедуры

}

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

Монитор как представитель абстрактных типов данных обладает тремя свойствами. Во-первых, вне монитора видны только имена процедур -- они представляют собой одно единственное "окно в стене" объявления монитора. Таким образом, чтобы изменить состояние ресурса, представленное постоянными переменными, процесс должен вызвать одну из процедур монитора. Вызов процедуры монитора имеет следующий вид:

call mname.opname(arguments)

Здесь mname -- имя монитора, opname -- имя одной из его операций (процедур), вызываемой с аргументами arguments. Если имя opname уникально в области видимости вызывающего процедуру процесса, то часть "mname" в вызове процедуры не обязательна.

Во-вторых, операторы внутри монитора (в объявлениях и процедурах) не могут обращаться к переменным, объявленным вне монитора.

В-третьих, постоянные переменные инициализируются до вызова его процедур. Это реализовано путем выполнения инициализирующих операторов при создании монитора и, следовательно, до вызова его процедур.

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

Поэтому полезно определить предикат, истинный независимо от порядка выполнения вызовов. Инвариант монитора -- это предикат, определяющий "разумные" состояния постоянных переменных, когда процессы не обращаются к ним. Код инициализации монитора должен создать состояние, соответствующее инварианту, а каждая процедура должна его поддерживать. (Инвариант монитора аналогичен глобальному инварианту, но для переменных в пределах одного монитора.) Инварианты мониторов включены во все примеры главы. Строка инварианта начинается символами ##.

Монитор отличается от механизма абстракции данных в языках последовательного программирования тем, что совместно используется параллельно выполняемыми процессами. Поэтому, чтобы избежать взаимного влияния в процессах, выполняемых в мониторах, может по требоваться взаимное исключение, а для приостановки работы до выполнения определенного условия -- условная синхронизация. Рассмотрим, как процессы синхронизируются в мониторах.

1.1.1 Взаимное исключение

Синхронизацию проще всего понять и запрограммировать, если взаимное исключение и условная синхронизация выполняются разными способами. Лучше всего, если взаимное исключение происходит неявно, чем автоматически устраняется взаимное влияние. Кроме того, программы легче читать, поскольку в них нет явных протоколов входа в критические секции и выхода из них.

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

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

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

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

1.1.2 Условные переменные

Условная переменная используется для приостановки работы процесса, безопасное выполнение которого невозможно до перехода монитора в состояние, удовлетворяющее некоторому логическому условию. Условные переменные также применяются для запуска приостановленных процессов, когда условие становится истинным. Условная переменная объявляется следующим образом:

cond cv;

Таким образом, cond - это новый тип данных. Массив условных переменных объявляется, как обычно, указанием интервала индексов после имени переменной. Условные переменные можно объявлять и использовать только в пределах мониторов.

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

Процесс может запросить состояние условной переменной с помощью вызова:

empty(cv);

Если очередь переменной cv пуста, эта функция возвращает значение "истина", иначе -- "ложь".

Процесс блокируется на условной переменной cv с помощью вызова:

wait(cv);

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

Процессы, заблокированные на условных переменных, запускаются операторами signal. При выполнении вызова проверяется очередь задержки переменной cv. Если она пуста, никакие действия не производятся. Однако, если приостановленные процессы есть, оператор signal запускает процесс вначале очереди. Таким образом, операции wait и signal обеспечивают порядок сигнализации FIFO: процессы приостанавливаются в порядке вызовов операции wait, а запускаются в порядке вызовов операции signal.

1.1.3 Дисциплины сигнализации

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

* сигнализировать и продолжить: сигнализатор продолжает работу, а процесс, получивший сигнал, выполняется позже;

* сигнализировать и ожидать: сигнализатор ждет некоторое время, а процесс, получивший сигнал, выполняется сразу.

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

Порядок "сигнализировать и ожидать" имеет свойство прерывания обслуживания. Процесс, выполняющий операцию signal, передает управление блокировкой монитора запускаемому процессу, т.е. запускаемый процесс прерывает работу процесса-сигнализатора. В этом случае сигнализатор переходит в очередь процессов, ожидающих на блокировке монитора. (Возможен вариант, когда сигнализатор помещается в начало очереди ожидающих процессов; это называется "сигнализировать и срочно (urgent) ожидать".)

Рисунок 1 - Диаграмма состояний для синхронизации в мониторах

Диаграмма состояний на рисунке 1 иллюстрирует работу синхронизации в мониторах. Вызывая процедуру монитора, процесс помещается во входную очередь, если в мониторе выполняется еще один процесс; в противном случае вызвавший операцию процесс немедленно начинает выполнение в мониторе. Когда монитор освобождается (после возврата из процедуры или выполнения операции wait), один процесс из входной очереди может перейти к работе в мониторе. Выполняя операцию wait(cv), процесс переходит от работы в мониторе в очередь, связанную с условной переменной. Если процесс выполняет операцию signal(cv), то при порядке "сигнализировать и продолжить" (Signal and Continue - SC) процесс из начала очереди условной переменной переходит во входную. При порядке "сигнализировать и ожидать" (Signal and Wait - SW) процесс, выполняемый в мониторе, переходит во входную очередь, а процесс из начала очереди условной переменной переходит к выполнению в мониторе.

1.1.4 Дополнительные операции с условными переменными

До сих пор с условными переменными использовались три операции: empty, wait и signal. Полезны еще три: приоритетная wait, minrank и signal_all Все они имеют простую семантику и могут быть эффективно реализованы, поскольку обеспечивают лишь дополнительные действия над очередью, связанной с условной переменной.

Все шесть операций представлены в табл. 1.

Таблица 1. Операции над условными переменными

wait (cv) Ждать в конце очереди.

wait (cv, rank) Ждать в порядке возрастания значения ранга (rank).

signal (cv) Запустить процесс из начала очереди и продолжить.

signal_all (cv) Запустить все процессы очереди и продолжить.

empty (cv) Истина, если очередь ожидания пуста, иначе -- ложь.

minrank (cv) Значение ранга процесса в начале очереди ожиданий.

С помощью операций wait и signal приостановленные процессы запускаются в том же порядке, в котором они были задержаны, т.е. очередь задержки является FIFO-очередью. Приоритетный оператор wait позволяет программисту влиять на порядок постановки процессов в очередь и их запуска. Оператор имеет вид:

wait(cv, rank)

Параметр cv -- это условная переменная, а rank - целочисленное выражение. Процессы приостанавливаются на переменной cv в порядке возрастания значения rank и, следовательно, в этом же порядке запускаются. При равенстве рангов запускается процесс, ожидавший дольше всех. Во избежание потенциальных проблем, связанных с совместным применением обычного и приоритетного операторов wait для одной переменной, программист должен всегда использовать только один тип оператора wait.

Для задач планирования, в которых используется приоритетный оператор wait, часто полезно иметь возможность определить ранг процесса в начале очереди задержки. Из вызова:

minrank (cv)

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

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

signal_all(cv)

Выполнение оператора signal_all запускает все процессы, приостановленные на условной переменной cv. При порядке "сигнализировать и продолжить" он аналогичен коду:

while (!empty(cv)) signal(cv);

Запускаемые процессы возобновляют выполнение в мониторе через некоторое время в соответствии с ограничениями взаимного исключения. Как и оператор signal, оператор signal_all не дает результата, если нет процессов, приостановленных на условной переменной cv. Процесс, выработавший сигнал, также продолжает выполняться в мониторе.

Операция signal_all вполне определена, когда мониторы используют порядок "сигнализировать и продолжить", поскольку процесс, выработавший сигнал, всегда продолжает работать в мониторе. Но при использовании порядка "сигнализировать и ожидать" эта операция определена не точно, поскольку становится возможным передать управление более, чем одному процессу, и дать каждому процессу исключительный доступ к монитору. Это еще одна причина, по которой в операционной системе Unix, языке Java и библиотеке Pthreads используется порядок запуска "сигнализировать и продолжить".

2. Описание устройства жесткого диска

2.1 Компоненты дискового устройства

Дисковое устройство использует быстро перемещающийся для чтения и записи данных с плоского диска, покрытого магнитными частицами. Данные передаются с магнитного диска на компьютер через головку чтения/записи. Несколько собранных воедино магнитных дисков с головкой чтения/записи и контроллером, как правило, называются жестким диском (HDD). Данные можно записывать и стирать с магнитного диска сколько угодно раз. Ключевые компоненты жесткого диска: магнитный диск, шпиндель, головка чтения/записи, рычаг привода и контроллер (рисунок 2).

2.1.1 Магнитный диск

Типичный HDD состоит из одного или нескольких круглых дисков, называемых магнитными дисками (рисунок 3). Запись данных на эти магнитные диски происходит в виде двоичных кодов. Набор вращающихся магнитных дисков в герметичном контейнере называется блоком дисков с головками (HDA). Магнитный диск представляет собой жесткий круглый диск, покрытый магнетиком с обеих сторон. Данные кодируются путем поляризации магнитной поверхности диска. Запись или считывание возможны с обеих сторон диска.



Рисунок 2 - Компоненты жесткого диска

Рисунок 3 - Шпиндель и магнитный диск

2.1.2 Шпиндель

Шпиндель собирает все магнитные диски как представлено на рисунке 3 и подключается к двигателю. Двигатель шпинделя вращается с постоянной скоростью.

Магнитный диск вращается со скоростью несколько тысяч оборотов в минуту (rpm). Скорость вращения дисковых шпинделей составляет 7200б 10000 или 15000 оборотов в минуту. Диаметр дисков, используемых в современных устройствах хранения, составляет 3,5 дюйма (90 миллиметров). Скорость вращения магнитного диска увеличивается с развитием технологии, однако потенциал разгона у таких дисков ограничен.

2.1.3 Головка чтения/записи

Головки чтения/записи, изображенные на рисунке 4, считывают и записывают данные на магнитном диске. У каждого магнитного диска две головки чтения/записи - по одной для каждой из сторон диска. При записи данных головка меняет магнитную поляризацию поверхности диска. При чтении данных эта головка фиксирует магнитную поляризацию поверхности диска. При чтении и записи головка воспринимает магнитную поляризацию, но она никогда не касается поверхности магнитного диска. При вращении шпинделя образуется микроскопический воздушный зазор между головками чтения/записи и магнитными дисками, известный как высота зависания головки. Этот воздушный зазор исчезает, когда шпиндель прекращает вращение, а головки чтения/записи остаются на специальной области магнитного диска рядом со шпинделем. Эта область называется зоной парковки. Зона парковки покрывается смазочным материалом для снижения трения между головкой и магнитным диском.



Рисунок 4 - Рычаг привода

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

2.1.4 Рычаг привода

Головки чтения/записи крепятся к рычагу привода (рисунок 4), размещающего головку чтения/записи на то место магнитного диска, где нужно считать или записать данные. Головки чтения/записи всех магнитных дисков крепятся к одному рычагу привода и движутся по магнитным дискам одновременно. У каждого диска по две головки чтения/записи, по одной для каждой поверхности.

2.1.5 Контроллер

Контроллер - это печатная плата, расположенная в нижней части диска. Устройство состоит из микропроцессора, внутренней памяти, схем и встроенных программ.

Встроенные программы контролируют питание двигателя шпинделя и скорость двигателя. Они также управляют взаимодействием между диском и хостом. Кроме того, эти программы контролируют операции чтения/записи посредством передвижения рычага привода и переключения головок чтения записи и оптимизируют доступ к данным.

монитор жесткий диск микропроцессорный

3. Планирование работы дисков с использованием мониторов

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

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

Время доступа к диску состоит из трех частей: времени поиска (перемещение головки чтения-записи на соответствующий цилиндр), задержки вращения и времени передачи данных. Время передачи данных целиком определяется количеством байтов передаваемых данных, а другие два интервала зависят от состояния диска. В лучшем случае головка чтения-записи уже находится на нужном цилиндре, а требуемая часть дорожки как раз начинает проходить под ней. В худшем случае головку чтения-записи нужно переместить через весь диск, а требуемая дорожка должна совершить полный оборот. Для дисков характерно то, что время перемещения головки от одного цилиндра к другому прямо пропорционально расстоянию между цилиндрами. Важно также, что время перемещения головки даже на один цилиндр намного больше, чем период вращения пластины. Таким образом, наиболее эффективный способ сократить время обращения к диску -- минимизировать передвижения головки, сократив время поиска. (Можно сокращать и задержки вращения, но это сложно и неэффективно, поскольку они обычно очень малы.)

Предполагается, что диск используют несколько клиентов. Например, в мультипрограммной операционной системе это могут быть процессы, выполняющие команды пользователя, или системные процессы, реализующие управление виртуальной памятью. Если доступ к диску запрашивает всего один клиент, то ничего нельзя выиграть, не дав ему доступ немедленно, поскольку неизвестно, когда к диску обратится еще один клиент. Таким образом, планирование доступа к диску применяется, только когда приблизительно в одно время доступ запрашивают как минимум два процесса.

Напрашивается следующая стратегия планирования: всегда выбирать тот ожидающий запрос, который обращается к ближайшему относительно текущего положения головок цилиндру. Эта стратегия называется стратегией кратчайшего времени поиска (shortest-seek-time - SST), поскольку помогает минимизировать время поиска. Однако SST - несправедливая стратегия, поскольку непрерывный поток запросов для цилиндров, находящихся рядом с текущей позицией головки, может остановить обработку запросов к отдаленным цилиндрам. Хотя такая остановка обработки запросов крайне маловероятна, длительность ожидания обработки запроса здесь ничем не ограничена. Стратегия SST используется в операционной системе UNIX.

Еще одна, уже справедливая, стратегия планирования -- перемещать головки в одном направлении, пока не будут обслужены все запросы в этом направлении движения. Выбирается клиентский запрос, ближайший к текущей позиции головки в направлении, в котором она двигалась перед этим. Если для этого направления запросов больше нет, оно изменяется. Эта стратегия встречается под разными названиями -- SCAN (сканирование), LOOK (просмотр) или алгоритм лифта, поскольку перемещения головки похожи на работу лифта, который ездит по этажам, забирая и высаживая пассажиров. Единственная проблема этой стратегии -- запрос, которому соответствует позиция сразу за текущим положением головки, не будет обслужен, пока головка не пойдет назад. Это приводит к большому разбросу времени ожидания выполнения запроса.

Третья стратегия аналогична второй, но существенно уменьшает разброс времени ожидания выполнения запроса. Ее называют CSCAN или CLOOK (буква C взята от "circular" - циклический). Запросы обслуживаются только в одном направлении, например, от внешнего к внутреннему цилиндру. Таким образом, существует только одно направление поиска, и выбирается запрос, ближайший к текущему положению головки в этом направлении. Когда запросов в направлении движения головки не остается, поиск возобновляется с внешнего цилиндра. Это похоже на лифт, который только поднимает пассажиров. (Вероятно, вниз они должны были бы идти пешком или прыгать!) В отношении сокращения времени поиска стратегия CSCAN эффективна почти так же, как и алгоритм лифта, поскольку для большинства дисков перемещение головок через все цилиндры занимает примерно вдвое больше времени, чем перемещение между соседними цилиндрами. Кроме того, стратегия CSCAN справедлива, если только поток запросов к текущей позиции головки не останавливает выполнение остальных запросов (что крайне маловероятно).

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

Оба монитора-диспетчера реализуют стратегию CSCAN.

3.1 Использование отдельного монитора

Реализуем диспетчер монитором, который отделен от управляемого им ресурса, то есть диска (рисунок 5). В решении есть три вида компонентов: пользовательские процессы, диспетчер, а также процедуры или процессы, выполняющие обмен данными с диском. Диспетчер реализован монитором, чтобы данные планирования были доступны одновременно только одному процессу. Монитор поддерживает две операции: request (запросить) и release (освободить).

Рисунок 5 - Диспетчер доступа к диску как отдельный монитор

Для получения доступа к цилиндру cyl пользовательский процесс сначала вызывает процедуру request (cyl), из которой возвращается только после того, как диспетчер выберет этот запрос. Затем пользовательский процесс работает с диском, например, вызывает соответствующие процедуры или взаимодействует с процессом драйвера диска. После работы с диском пользователь вызывает процедуру release, чтобы диспетчер мог выбрать новый запрос. Таким образом, диспетчер имеет следующий пользовательский интерфейс.

Disk_Scheduler.request(cyl)

Работа с диском

Disk_Scheduler.release(cyl)

Монитор Disk_Scheduler играет двойную роль: он планирует обращения к диску и обеспечивает в любой момент времени доступ к диску только одному процессу.

Таким образом, пользователи обязаны следовать указанному выше протоколу.

Предположим, что цилиндры диска пронумерованы от 0 до MAXCYL, и диспетчер использует стратегию CSCAN с направлением поиска от 0 до MAXCYL. Как обычно, важнейший шаг в разработке правильного решения - точно сформулировать его свойства. Здесь в любой момент времени только один процесс может использовать диск, а ожидающие запросы обслуживаются в порядке CSCAN.

Пусть переменная position указывает текущую позицию головки диска, т.е. номер цилиндра, к которому обращался процесс, использующий диск. Когда к диску нет обращений, переменной position присваивается значение «-1». (Можно использовать любой неправильный номер цилиндра или ввести дополнительную переменную.)

Для реализации стратегии планирования CSCAN необходимо различать запросы, которые нужно выполнить за текущий и за следующий проход через диск. Пусть эти запросы хранятся в непересекающихся множествах C и N. Оба множества упорядочены по возрастанию значения cyl, запросы к одному и тому же цилиндру упорядочены по времени вставки в множество. Таким образом, множество C содержит запросы для цилиндров, номера которых больше или равны текущей позиции, а N - для цилиндров с номерами, которые меньше или равны текущей позиции. Это выражается следующим предикатом, который является инвариантом монитора.

DISK:С и N являются упорядоченными множествами

все элементы множества С >= position

все элементы множества N <= position

(position == -1) => (С == 0 ^ N == 0)

Ожидающий запрос, для которого cyl равно position, мог бы быть в любом из множеств, но помещается в N, как описано в следующем абзаце.

Вызывая процедуру request, процесс выполняет одно из трех действий.

Если переменная position имеет значение «-1», диск свободен; процесс присваивает переменной position значение cyl и работает с диском. Если диск занят и выполняется условие cyl > position, то процесс вставляет значение cyl в C, иначе (cyl <= position) - в N. При равенстве значений cyl и position используется N, чтобы избежать возможной несправедливости планирования, поэтому запрос будет ожидать следующего прохода по диску. После записи значения cyl в подходящее множество процесс приостанавливается до тех пор, пока не получит доступ к диску, т.е. до момента, когда значения переменных position и cyl станут равными.

Вызывая процедуру release, процесс обновляет постоянные переменные так, чтобы выполнялось условие DISK. Если множество C не пусто, то еще есть запросы для текущего прохода. В этом случае процесс, освобождающий доступ к диску, удаляет первый элемент множества C и присваивает это значение переменной position. Если C пусто, а N - нет, то нужно начать новый проход, который становится текущим. Для этого освобождающий процесс меняет местами множества C и N (N при этом становится пустым), затем извлекает первый элемент из C и присваивает его значение переменной position. Если оба множества пусты, то для индикации освобождения диска процесс присваивает переменной position значение «-1».

Последний шаг в разработке решения - реализовать синхронизацию между процедурами request и release. Между условиями ожидания есть статический порядок, поэтому для реализации упорядоченных множеств можно использовать приоритетный оператор wait. Запросы в множествах C и N обслуживаются в порядке возрастания значения cyl. Переменной position нужно присваивать значение того ожидающего запроса, который будет обработан следующим.

Для представления множеств C и N используем массив условных переменных scan[2], индексированный целыми C и N.

Когда запрашивающий доступ процесс должен вставить свой параметр cyl в множество C и ждать, пока станут равны position и cyl, он просто выполняет процедуру wait(scan[c], cyl). Аналогично процесс вставляет свой запрос в множество N и приостанавливается, выполняя wait(scan[n], cyl). Кроме того, чтобы определить, пусто ли множество, используется функция empty, чтобы вычислить наименьшее значение в множестве - функция minrank, а для удаления первого элемента с одновременным запуском соответствующего процесса -- процедура signal. Множества C и N меняются местами, когда это нужно, с помощью простого обмена значений C и N. (Именно поэтому для представления множеств выбран массив.)

Объединив перечисленные изменения, получим программу в листинге 1. В конце процедуры release значением c является индекс текущего множества обрабатываемых запросов, поэтому достаточно вставить только один оператор signal. Если в этот момент переменная position имеет значение «-1», то множество scan[c] будет пустым, и вызов signal не даст результата.

Листинг 1. Отдельный монитор диспетчера доступа к диску.

Monitor Disk_Scheduler{

int position = -1, c=0, n=1;

cond scan[2];

procedure request(int cyl) {

if(position == -1)

position = cyl;

elseif(position !=-1 && cyl > position)

wait (scan[c], cyl);

else

wait (scan[n], cyl);

}

procedure release() {

int temp;

if(!empty(scan[c]))

position = minrank(scan[c]);

elseif (empty(scan[c]) && !empty(scan[n])) {

temp = c; c=n; n= temp;

position = minrank(scan[c]);

}

else

position = -1;

signal(scan[c]);

}

}

Представим программу монитора в виде ГСА (Рисунок 6).



Рисунок 6 - ГСА отдельного монитора диспетчера

Заменим строки кода в блоках ГСА на логические переменные и операторы, получим следующую ГСА (рисунок 7).



Рисунок 7 - ГСА отдельного монитора диспетчера в формальном представлении

X1 - если условие истинно, то диск свободен и можно совершить операцию записи/чтения;

X2 - если условие истинно, то значение нужного цилиндра вставляется в множество C;

X3 - если условие истинно, то множество С не пустое и можно выбирать следующий элемент;

X4 - если условие истинно, то множество N не пустое, нужно поменять местами множества C и N и выбирать следующий элемент;

A0 - инициализация переменных;

A1 -перемещение головки диска к цилиндру с номером cyl;

A2 - диспетчер помещает значение cyl в множество C, а процесс, требующий доступа к диску, ожидает, пока головка диска окажется на нужной позиции;

A3 - диспетчер помещает значение cyl в множество N, а процесс, требующий доступа к диску, ожидает, пока головка диска окажется на нужной позиции;

A4 - множества C и N меняются местами;

A5 - выбирается минимальное значение из множества С;

A6 - запускается процесс, ожидающий доступа к цилиндру с номером position, а само это значение удаляется из множества;

A7 - выбирается минимальное значение из множества С.

3.2 Использование посредника

Чтобы привести структуру решения к задаче планирования и распределения, желательно реализовать монитор Disk_Scheduler или другой контроллер ресурсов в виде отдельного монитора. Поскольку диспетчер изолирован, его можно разрабатывать независимо от других компонентов. Однако чрезмерная изоляция обычно приводит к двум проблемам:

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

* все пользовательские процессы должны следовать необходимому протоколу: запрос диска, его использование, освобождение. Если хотя бы один процесс нарушает этот протокол, планирование невозможно.

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

Рисунок 8 - Диспетчер доступа к диску как посредник

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

Листинг 2.1 Схема монитора интерфейса диска

Monitor Disk_Interface {

постоянные переменные для состояния, планирования и передачи данных

procedure use_disk(int cyl, параметры передачи и результата){

ждать очереди использовать драйвер

сохранить параметры передачи в постоянных переменных

ждать завершения передачи

получить результаты из постоянных переменных

}

Procedure get_next_request (someType &results){

выбрать следующий запрос

ждать сохранения параметров передачи

присвоить переменной results параметры передачи

}

Procedure finished_transfer (someType results){

сохранить результаты в постоянные переменные

ждать получения клиентом значения results

}

}

Пользовательский процесс ждет очереди на доступ к диску, выполняя те же действия, что и процедура request монитора Disk_Scheduler. Аналогично процесс драйвера показывает, что он доступен, выполняя те же действия, что и процедура release монитора Disk_Scheduler. В начальном состоянии, однако, переменной position будет присваиваться значение -2, чтобы показать, что диск недоступен и не используется до того, как драйвер впервые вызовет процедуру get_next_request. Следовательно, пользователи должны ждать начала первого прохода.

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

Листинг 2.2 Монитор интерфейса диска

Monitor Disk_Interface{

int position = -2, c=0, n=1, args=0, results=0;

cond scan[2];

cond args_stored, results_stored, results_retrieved;

argType arg_area; resultType result_area;

procedure use_disk(int cyl, argType transfer_params,

resultType &result_params) {

if(position == -1)

position = cyl;

elseif(position !=-1 && cyl > position)

wait (scan[c], cyl);

else

wait (scan[n], cyl);

arg_area = transfer_params;

args = args+1; signal(args_stored);

while (results==0) wait (results_stored);

result_params = result_area;

results=results-1; signal(results_retrieved);

}

procedure get_next_request(argType &transfer_params) {

int temp;

if(!empty(scan[c]))

position = minrank(scan[c]);

elseif (empty(scan[c]) && !empty(scan[n])) {

temp = c; c=n; n= temp;

position = minrank(scan[c]);

}

else

position = -1;

signal(scan[c]);

while(args==0) wait(args_stored);

transfer_params=arg_area; args=args-1;

}

procedure finished_transfer(resultType result_vals) {

result_area = result_vals; results = results+1;

signal(results_stored);

while(results>0)wait results_retrieved);

}

}

Переменные args_stored, results_stored, results_retrieved сигнализируют о сохранении аргументов передачи, результатов передачи в постоянные переменные и получение результатов пользовательским процессом соответственно. В переменных args и results хранится количество аргументов (по сути это и есть количество запросов) и количество результатов, полученных от драйвера, в данный момент времени. Переменные arg_area и result_area являются глобальными переменными для передачи аргументов и результатов между процедурами монитора. Остальной код программы описан в листинге 2.1 (схема монитора интерфейса диска).

Представим программу монитора интерфейса диска в виде ГСА (Рисунок 9).



Рисунок 9 - ГСА монитора интерфейса диска

Заменим строки кода в блоках ГСА на логические переменные и операторы, получим следующую ГСА (рисунок 10).

Рисунок 10 - ГСА монитора интерфейса диска в формальном представлении

X1 - если условие истинно, то диск свободен и можно совершить операцию записи/чтения;

X2 - если условие истинно, то значение нужного цилиндра вставляется в множество C;

X3 - если условие истинно, то множество С не пустое и можно выбирать следующий элемент;

X4 - если условие истинно, то множество N не пустое, нужно поменять местами множества C и N и выбирать следующий элемент;

X5 - если условие истинно, то счетчик результатов равен нулю и процесс, запрашивающий доступ к диску ожидает, пока завершится передача и сохранение результатов;

X6 - если условие истинно, то счетчик аргументов равен нулю;

X7 - если условие истинно, то счетчик результатов больше нуля;

A0 - инициализация переменных;

A1 - перемещение головки диска к цилиндру с номером cyl;

A2 - диспетчер помещает значение cyl в множество C, а процесс, требующий доступа к диску, ожидает, пока головка диска окажется на нужной позиции;

A3 - диспетчер помещает значение cyl в множество N, а процесс, требующий доступа к диску, ожидает, пока головка диска окажется на нужной позиции;

A4 - множества C и N меняются местами;

A5 - выбирается минимальное значение из множества С;

A6 - запускается процесс, ожидающий доступа к цилиндру с номером position, а само это значение удаляется из множества;

A7 - выбирается минимальное значение из множества С;

A8 - результаты работы с диском сохраняются в переменной типа resultType;

A9 - увеличивается счетчик результатов;

A10 - запускается процесс, ожидающий завершения передачи (сохранения результатов передачи);

A11 - параметры передачи сохраняются в области аргументов;

A12 - увеличивается счетчик аргументов (по сути счетчик процесов, ожидающих обращения к диску);

A13 - запускается процесс, ожидающий сохранения аргументов передачи;

A14 - процесс, запрашивающий доступ к диску ожидает, пока завершится передача и сохранение результатов;

A15 - процесс считывает результаты передачи из переменной типа resultType ;

A16 - счетчик результатов уменьшается;

A17 - запускается процесс, ожидающий получения результатов;

A18 - процесс ожидает сохранения параметров передачи в переменную типа argType;

A19 - параметры передачи извлекаются из переменной типа argType;

A20 - счетчик аргументов уменьшается;

A21 - процесс (диспетчер) ожидает, пока процесс получит результаты передачи;

4. Сценарные и логико-алгебраические модели систем ВЗУ с централизованной архитектурой

Архитектура большинства современных систем и сетей хранения и обработки данных предусматривает не только параллельную работу центральных процессоров и каналов ввода-вывода, но и наличие параллельных режимов поиска и передачи данных. Обычные используемые средства моделирования дискретных систем с высоким уровнем параллельности, как правило, относятся к классу универсальных систем моделирования. К недостаткам подобного вида систем относятся неявное задание параллелизма, выявляемое лишь при семантическом анализе модели, трудоемкость составления и верификации моделей. В качестве средства описания и проектирования подсистем ввода-вывода с высоким уровнем параллельности предлагается использовать логико-алгебраические модели на основе базовых формализмов СеАМ. На основе данных моделей далее разрабатывается программное и микропрограммное обеспечение системы или сети ВЗУ. От логико-алгебраических моделей, построенных на основе формализмов СеАМ, можно перейти к сетевым имитационным, или поведенческим моделям для прогноза производительности проектируемой системы или сети ВЗУ. Построенные модели позволят также решить проблему выбора необходимого уровня параллельности при создании систем и сетей ВЗУ на магнитных дисках.

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

Рассмотрим параллельную работу подсистем ввода-вывода на примере подсистемы ВЗУ на магнитных дисках. Рассмотрим вначале централизованную архитектуру системы ВЗУ, представленную на рисунке 11 при обычном, наиболее распространенном режиме работы. Логико-алгебраическая модель данной системы будет базовой для двух других моделей систем и сетей ВЗУ с более сложными режимами работы. В состав системы входят блок-мультиплексные каналы, или сетевые интерфейсы chan(1), chan(2), …, chan(m), устройства управления, или контроллеры contr(1), contr(2), …, contr(k), модульные коммутаторы (или коммутирующие управляющие модули) cm(1), cm(2), …, cm(n), по одному коммутатору на каждый дисковый модуль disk(1), disk(2), …, disk(n). Модели позволяют оценить качество функционирования двух указанных подсистем ВЗУ и сравнить их по критерию пропускной способности. По результатам построения данных моделей можно осуществить простой переход к управляющим программам и микропрограммам для новых многофункциональных систем и сетей ВЗУ. Впоследствии будут рассмотрены более детализированные модели систем и сетей ВЗУ с учетом новой сетевой архитектуры. В данном разделе разработаны модели двух уровней: сценарные и на базе формализмов СеАМ.

Рисунок 11 - Традиционная централизованная архитектура системы хранения данных

Формульная запись сценарной модели СМ1 имеет следующий вид:

(1)

(2)

Сценарий первого уровня A0 описан выражением (1), где “” - символ операции конкурентного выполнения подсценариев, а каждый из входящих в данное выражение n подсценариев второго уровня A1, A2, …, An (по одному на каждый из n дисковых модулей) описан выражением вида (2). Условиям и подсценариям в сценарной модели СМ1 дана следующая интерпретация.

Интерпретация истинности условий:

- готовность к формированию очередного запроса;

- есть по крайней мере один запрос во входной очереди queue(i);

- завершена выборка запроса (команды записи или чтения данных) i-му дисковому модулю;

- есть по крайней мере один свободный канал;

- есть по крайней мере один свободный контроллер;

- i-й дисковый модуль свободен и готов к выполнению операции.

Интерпретация подсценариев второго уровня:

- задержка на время формирования очередного запроса;

- передача команды записи или чтения данных;

- занятие сетевого дискового модуля (disk(i)); анализ параметров команды записи-чтения данных парой “канал-контроллер”;

- задержка “перемещения” на время позиционирования головок в дисковом модуле;

- задержка “вращения” на время до подхода требуемого сектора, в котором начинается либо требуемый блок данных (при выполнении операции чтения), либо зона для записи блока данных (при выполнении операции записи);

- неуспешные попытки начать поиск записи внутри сектора (далее данный подсценарий будет реализован двумя модулями и сети СеАМ1); если канал или контроллер заняты, то должен выполниться подсценарий ;

- подключение канала и контроллера на поиск записи внутри сектора;

- ожидание полного оборота носителя информации для повторной попытки поиска записи внутри сектора;

- запись блока данных на диск или считывание блока данных с диска;

- завершение операции записи-чтения.

Представим сценарную модель в виде ГСА (рисунок 12 и рисунок 13).

Рисунок 12 - ГСА сценария первого уровня

Обозначения внутри блоков ГСА совпадают с обозначениями в выражении 1.