Распределение ресурсов и планирование

Распределение ресурсов — это задача решения, когда процесс может получить доступ к ресурсу. В параллельных программах ресурсом является все то, при попытке получения чего работа процесса может быть приостановлена. Сюда включается вход в критическую секцию, доступ к базе данных, ячейка кольцевого буфера, область памяти, использование принтера и тому подобное. Несколько частных случаев задачи о распределении ресурсов были рассмот­рены выше. В большинстве использовалась простейшая стратегия распределения ресурсов: если некоторый процесс ждет и ресурс свободен, то ресурс распределяется. Например, в ре­шении задачи критической секции (раздел 4.2) разрешение на вход дается какому-нибудь из ожидающих процессов; попытка определить, какой именно процесс получит разрешение на вход, не делается. Так же и в задаче о кольцевом буфере (раздел 4.2) не было попытки контро­лировать порядок получения доступа производителей и потребителей к буферу. Лишь в зада­че о читателях и писателях рассматривалась более сложная стратегия планирования. Но там целью было дать преимущество классу процессов, а не отдельным процессам.

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

150                                               Часть 1. Программирование с разделяемыми переменными

4.5.1. Постановка задачи и общая схема решения

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

Если опустить представление элементов ресурса, то общая схема операций request и release такова.

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

Эту общую схему решения можно реализовать с помощью метода передачи эстафеты (раздел 4.4). Операция request имеет вид обычного оператора await, поэтому реализуется следующим фрагментом программы.



Операция release тоже имеет вид простого неделимого действия и реализуется таким фраг­ментом программы.



Как и раньше, семафор е управляет входом в критическую секцию, а фрагмент кода SIGNAL запускает на выполнение приостановленные процессы (если ожидающий запрос может быть удовлетворен) или снимает блокировку семафора входа с помощью операции V (е). Код DELAY в операции request аналогичен фрагментам кода в начале протоколов входа процес­сов читателей и писателей (см. листинги 4.11 и 4.12). Он запоминает, что появился новый за­прос, который должен быть приостановлен, снимает блокировку с семафора входа с помо­щью операции V (е) и блокирует запрашивающий процесс на семафоре задержки.





Детали реализации кода SIGNAL в каждой конкретной задаче распределения ресурсов за­висят от условий задержки и их представления. В любом случае код DELAУ должен сохранять параметры, характеризующие приостановленный запрос для дальнейшего их использования кодом SIGNAL. Кроме того, для каждого условия задержки нужен один семафор условия.

Глава 4. Семафоры                                                                                                                         151

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

4.5.2. Распределение ресурсов по схеме "кратчайшее задание"

"Кратчайшее задание" (КЗ, Shortest-Job-Next — SJN) — это стратегия распределения ресурсов, которая встречается во многих разновидностях и используется для разных типов ресурсов. Предположим, что разделяемый ресурс состоит из одного элемента (общий слу­чай нескольких элементов рассмотрен в конце данного раздела). Тогда стратегия КЗ опре­деляется следующим образом.

(4.3) Распределение ресурсов по схеме "кратчайшее задание". Несколько процессов соперни­чают в использовании одного разделяемого ресурса. Процесс запрашивает ресурс, вы­полняя операцию request (time, id), где целочисленный параметр time определя­ет длительность использования ресурса этим процессом, а целое число id идентифи­цирует запрашивающий процесс. Если в момент выполнения операции request ресурс свободен, он выделяется для процесса немедленно, иначе процесс приостанав­ливается. После использования ресурса процесс освобождает его, выполняя операцию release. Освобожденный ресурс распределяется приостановленному процессу (если такой есть) с наименьшим значением параметра time. Если у нескольких процессов значения time равны, то ресурс отдается тому из них, кто дольше всех ждал.

Стратегию КЗ можно использовать, например, для распределения процессоров (параметр time будет означать время выполнения), для вывода файлов на принтер (time — время печа­ти) или для обслуживания удаленной передачи файлов по протоколу ftp (time — предпола­гаемое время передачи файла).



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

Если процесс выполняет запрос и ресурс свободен, то этот запрос может быть удовлетворен немедленно, поскольку других ожидающих запросов нет. Таким образом, стратегия КЗ "вступает в игру", только если есть несколько ожидающих запросов. Ресурс один, поэтому для хранения сведений о его доступности достаточно одной переменной. Пусть free — логическая переменная, которая истинна, когда ресурс доступен, и ложна, когда он занят. Для реализации стратегии КЗ нужно запоминать и упорядочивать ожидающие запросы. Пусть pairs — набор записей вида (time, id), упорядоченных по значениям поля time. Если две записи имеют одинаковые значения поля time, то они остаются во множестве pairs в порядке их появления. В соответствии с этим определением следующий предикат должен быть глобальным инвариантом. SJN: (pairs — упорядоченный набор) л (free => (pairs == 0) )

Расшифруем: набор pairs упорядочен, а если ресурс свободен, то pairs — пустое множест­во. Вначале free истинна, а множество pairs пусто, так что предикат SJN выполняется.

Без учета стратегии КЗ запрос может быть удовлетворен, как только ресурс станет доступ­ным. Отсюда получим следующее крупномодульное решение.



152                                               Часть 1. Программирование с разделяемыми переменными

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


Из второй части предиката SJN следует, что если пере­менная free истинна во время выполнения процессом операции request, то множество pairs пусто. Следовательно, приведенного выше условия достаточно для определения, мо­жет ли запрос удовлетворяться немедленно. Параметр time играет роль, только если запрос должен быть отложен — т.е. если переменная free ложна. На основе этих соображений мож­но реализовать операцию request таким образом.



В операции request предполагается, что операции Р над семафором входа е обслуживаются в порядке их появления, т.е. по правилу "первым пришел— первым обслужен". Если этого нет, то порядок обработки запросов может не соответствовать стратегии КЗ.

Осталось воплотить стратегию распределения ресурсов КЗ. Для этого используем множе­ство pairs и семафоры, реализующие фрагменты кода SIGNAL и DELAY. Если запрос не мо­жет быть удовлетворен, его следует сохранить, чтобы к нему можно было вернуться после ос­вобождения ресурса. Таким образом, во фрагменте кода DELA Yпроцесс должен:

•    вставить параметры запроса в набор pairs;

•    освободить управление критической секцией, выполнив операцию V (е);

•    остановиться на семафоре до удовлетворения запроса.

Если после освобождения ресурса множество pairs не пусто, то в соответствии со стратегией КЗ только один процесс должен получить ресурс. Таким образом, если есть приостановлен­ный процесс, который теперь может продолжить работу, он должен получить сигнал с помо­щью операции V для семафора задержки.

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



Предположим, что ресурс используют п процессов. Пусть b[n] — массив семафоров, ка­ ждый элемент которого имеет начальное значение 0. Будем считать, что значения идентифи­каторов процессов id уникальны и находятся в пределах от 0 до п-1. Тогда процесс id при­останавливается на семафоре b[id]. Дополнив операции request и release соответст­вующей обработкой множества pairs и массива Ь, получим решение задачи распределения ресурсов по схеме КЗ (листинг4.13).

В листинге 4.13 предполагается, что операция вставки помещает пару параметров в такое место последовательности pairs, которое сохраняет истинность первой части предиката SJN. Следовательно, предикат SJN действительно является инвариантом вне операций re­quest и release, т.е. он является истинным непосредственно после каждой операции Р(е) и перед каждой V (е). Если есть ожидающие запросы, т.е. множество pairs не пусто, опера­тор if кода выработки сигнала в операции release запускает только один процесс

Глава 4. Семафоры                                                                                                                         153

"Эстафетная палочка" переходит к этому процессу, а он присваивает переменной free зна­чение ложь. Этим гарантируется истинность второй части предиката SJN, когда множество pairs не пусто. Поскольку ресурс один, остальные запросы не могут быть удовлетворены, так что сигнальный код операции regues t состоит из одной операции V (е).



Элементы массива семафоров b в листинге 4.13 являются примером так называемых част­ных семафоров.

(4.4)   Частный семафор. Семафор s называется частным, если операцию Р над ним выпол­няет только один процесс.

Когда процесс в листинге 4.13 должен быть приостановлен, он выполняет операцию Р (b [ id]) для блокировки на собственном элементе массива Ь.

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


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

Решение в листинге 4.13 легко обобщить для использования ресурсов, состоящих из не­скольких элементов. В этой ситуации каждый элемент может быть свободен или занят, а опе­рации request и release должны использовать параметр amount, определяющий требуе­мое количество элементов ресурса. Изменим решение в листинге 4.13 следующим образом:

•    булеву переменную free заменим целочисленной переменной avail для хранения количества доступных элементов;

•    в операции request проверим условие amount <= avail. Если оно истинно, выде­лим amount элементов ресурса. Если нет, запомним, сколько элементов ресурса за­прошены перед приостановкой процесса;

154                                               Часть 1 Программирование с разделяемыми переменными

• в операции release увеличим значение avail на amount, после чего определим, можно ли удовлетворить запрос самого старого из отложенных процессов с минималь­ным значением параметра time. Если да — запустим его. Если нет, выполним V (е).

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


Содержание раздела

---

---