Устройство для выявления тупиковых ситуаций при обслуживании запросов на ресурсы вычислительной системы

 

УСТРОЙСТВО ДЛЯ ВЫЯВЛЕНИЯТУЛИКОВЫХ СИТУАЦИЙ ПРИ ОБСЛУЖИВАНИИ ЗАПРОСОВ НА РЕСУРСЫ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ, содержащее регистр памяти , выходной элемент ИЛИ и М блоков оценки ситуации (М - число обслуживаемых процессов), каждьй из которых содержит первый и второй регистры , элемент И, элемент ИЛИ, пять групп элементов ИЛИ и две группы элементов И, первая группа элементов И и первая группа элементов ИЛИ i -го блока оценки ситуации ( 1 1, ..., М) состоят из 6j подгрупп ( -. число альтернативных сочетаний ресурсов, требующихся i-му процессу по п элементов в каждой подгруппе ( 1 - число распределяемых ресурсов), выходы четных разрядов первого регистра соединены соответственно с первыми входами элементов И первой группы, вторые входы J-X элементов И всех подгрупп первой группы ( 1,Л ) соединены с выходом j -го элементу ИЛИ второй группы , выходы элементов и К-й подгруппы первой группы (К 1,6,- ) подключены соответственно к входам К-го элемента ИЛИ третьей группы, разрядные выходы второго регистра подключены соответственно к первым входам элементов И второй группы, вторые входы которых объединены и подключены к выходу элемента ИЛИ, первые входы элементов ИЛИ всех блоков оценки ситуации объединены и являются установочным входом устройства , выходы элементов И всех блоков оценки ситуации подключены соответственно к входам выходного элемента ИЛИ, выход i -го элемента И второй группы соединен с первыми входами « -X элементов ИЛИ четвертой и пятой групп, отличающееся тем, что, с целью расширения функциональных возможностей (Л за счет выявления тупиковьгх ситуаций при альтернативном запросе ресурсов коллективного и индивидуального пользования, j -и выход регистра памяти соединен с первым входом j-ro элемента ИЛИ каждой подгруппы первой группы в каждом блоке оценки эо ситуации и является j -м информационО ЭО ным выходом устройства, а в каждом блоке оценки ситуации выходы нечет;о ных разрядов первого регистра подключены соответственно к вторым входам элементов ИЛИ первой группы,, выходы которых соединены соответственно с третьими входами элементов И первой группы, выходы элементов ИЛИ третьей группы подключены соответственно к входам элемента И, выход которого соединен с вторым :входом элемента ИЛИ, выход j -го элемента ИЛИ пятой группы j -го блока оценки ситуации ( j 1, M-l-) соад1 ен с первым входом j -го элемента ШШ второй грУппы и вторым

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (! 9) (1)) (5))4 G 06 F 9/46

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ 4Ъ-,.

ОПИСАНИЕ ИЗОБРЕТЕНИ

К ABTOPCKOMY СВИДЕТЕЛЬСТВУ (21) 3720149/24-24 (22) 02.04.84 (46) 23.09.85. Бюл. № 35 (72) А.С. Ильин (53) 681.3(088.8) (56) Авторское свидетельство СССР № 807292, кл. G 06 F 9/46, 1979.

Авторское свидетельство СССР № 972512, кл. С 06 F 9/46, 1980. (54) (57) УСТРОЙСТВО ДЛЯ ВЬИВЛЕНИЯ

ТУПИКОВЫХ СИТУАЦИЙ ПРИ ОБСЛУЖИВАНИИ

ЗАПРОСОВ НА РЕСУРСЫ ВЫЧИСЛИТЕЛЬНОЙ

СИСТЕМЫ, содержащее регистр памяти, выходной элемент ИЛИ и М блоков оценки ситуации (М вЂ” число обслуживаемых процессов), каждый из которых содержит первый и второй регистры, элемент И, элемент ИЛИ, пять групп элементов ИПИ и две группы элементов И, первая группа элементов И и первая группа элементов

ИЛИ i --ro блока оценки ситуации (i = 1, °, И) состоят из 0; подгрупп ((; — число альтернативных сочетаний ресурсов, требующихся

1-му процессу) по и элементов в каж) дой подгруппе ()) — число распределяемых ресурсов), выходы четных разрядов первого регистра соединены соответственно с первыми входами элементов И первой группы, вторые входы

J -х элементов И всех подгрупп первой группы () = 1,И ) соединены с выходом 1 -го элемента ИЛИ второй группы, выходы элементов и К-й подгруппы первой группы (К = 1, g; ) подключены соответственно к входам

К-го элемента ИЛИ третьей группы, разрядные выходы второго регистра подключены соответственно к первым входам элементов И второй группы, вторые входы которых объединены и подключены к выходу элемента ИПИ, первые входы элементов KIN всех блоков оценки ситуации объединены и являются установочным входом устройства, выходы элементов И всех блоков оценки ситуации подключены соответственно к входам выходного элемента ИЛИ, выход j -ro элемента

И второй группы соединен с первыми входами j --х элементов ИЛИ четвертой и пятой групп, о т л и ч а ющ е е с я тем, что, с целью рас-, ширения функциональных возможностей за счет выявления тупиковых ситуаций при альтернативном запросе ресурсов коллективного и индивидуального пользования, 1 -й выход регистра памяти соединен с первым входом

j-ro элемента ИЛИ каждой подгруппы первой группы в каждом блоке оценки ситуации и является j -м информационmm выходом устройства, а в каждом блоке оценки ситуации выходы нечетных разрядов первого регистра подключены соответственно к вторым вхо" дам элементов ИЛИ первой группы,. выходы которых соединены соответственно с третьими входами элементов

И первой группы, выходы элементов

HJIH третьей группы подключены соответственно к входам элемента И, выход которого соединен с вторым ! входом элемента ИЛИ, выход 1 -го элемента ИЛИ пятой группы 1 -го блока оценки ситуации (j = 1, М-1) соединен с первым входом 1 -го эле» мента ИЛИ второй группы и вторым входом j -го элемента ИЛИ пятой группы (j + 1)-ro блока оценки ситуации, а выход j -"го элемента ИЛИ четвертой группы -ro блока (2, M) оценки еитуации подключен

1180890 к второму входу 1 в ro элемента ИЛИ . четвертой группы и второму входу

1 -ro элемента ИЛИ второй группы (0 — 1) -го блока оценки ситуа- ° ции.

Изобретение относится к. вычислительной технике и может быть использовано в системах обработки информации в составе цифровых вычислительных машин в части централизо- 5 ванного управления вычислительной системой, рассматриваемой в качестве системы массового обслуживания.

I„.ëüþ изобретения является расширение функциональных возможностей устройства эа счет выявления тупиковых ситуаций при альтернативном запросе ресурсов коллективного и индивидуального использования.

На фиг. 1 приведена схема уст- 15 ройства, на фиг. 2 — схема блока оценки ситуации.

Устройство содержит регистр 1 памяти, М блоков 2 оценки ситуации, выходной элемент ИЛИ 3 и .управляю- 20 щий вход 4.

Блок 2 оценки ситуации содержит первую группу элементов И 5; третью группу элементов ИЛИ 6, четвер- 25 тую 7, вторую 8 и пятую 9 группы элементов ИЛИ, вторую группу элементов И 10, элемент И 11, элемент

ИЛИ 12, второй регистр 13, первую группу элементов ИЛИ 14, первый регистр 15, вход 16 и выход 17, выходы 18 элементов ИЛИ 7 и выходы

19 элементов ИЛИ 9. Число разрядов регистра 13 и число элементов.ИЛИ в группах 7-9 равно и.

ЗО

Группа элементов И 5 и группа элементов ИЛИ 14 имеют 7; подгрупп по и элементов в каждой подгруп.пе. Число разрядов регистра 15 равно 2п Р;. Число обслуживаемых процессов М, число ресуроов и число альтернативных сочетаний ресурсов для i-ro процесса 2;, пределы изменения переменных: i = 1, М, р. 45

Схема устройства на фиг. 1 и 2 соответствует случаю М, п = 4, Р„= 2.

Устройство работает следующим образом.

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

"1" — единоличная, "0" — коллективная. В i — М блоке 2 в регистре

15 единица в 2(j + (К-1)n)-м разряФ де указывает, что i-й процесс в будущем может потребовать себе

j --й "ресурс в составе К-ro альтернативного сочетания ресурсов в дополнение к тем ресурсам, которые у него уже есть, а в (2 (j+ (К-1)п)— 1) -м разряде указывается требуемая i-м процессом форма пользования j-,ì ресурсом в составе К-го альтернативного сочетания ресурсов:

"1" — единоличная, "0" — коллективная. В регистре 1.3 единица в j-м разряде указывает, что j-й ресурс принадлежит -му процессу. Выходы

18 и 19 предназначены ддя того, чтобы по мере увеличения количества обслуживаемых процессов увеличивать количество блоков 2, путем их последовательного соединения.

На управляющем входе 4 установлен уровень "1", который через элементы ИЛИ 12 открывает все элементы

И 10. Последовательное соединение

j-х элементов ИЛИ 7 каждого блока

2 обеспечивает логическое суммирование сигналов принадлежности

j-ro ресурса процессам, снимаемых через j-e элементы И 10 каждого блока 2 с j-х разрядных выходов регистров 13. На 1 -м выходе элементов 7 при этом проявляется сиг3 11 нал занятости -го ресурса: занят, "0" — свободен. Такие же сигналы формируются на выходах элементов ИЛИ 9. Для процесса, обслуживаемого в данный момент, на основе анализа сигналов на выходах регистра 1 и элементов ИЛИ 7 и 9 программным путем производится первая проверка воэможности удовлетворения запроса на ресурсы пока без учета возможных тупиковых ситуаций: ресурс может быть выдан процессу в случаях, когда ресурс свободен .или когда процесс требует себе ресурс, используемый в данный момент коллективно, также ч коллективное пользозание. Если 1 -й процесс, использующийся j -м ресурсом коллективно, хочет изменить форму пользования на единоличную, то проверка занятости ресурса производится без учета принадлежности j-ro ресурса 1-му процессу, т.е. при временно обнуленном j -м разряде i -го регистра

13. Если процесс не получил отказ ,на его запрос при первой проверке, то производится вторая проверка, теперь уже с учетом предотвращения тупиковых ситуаций. Для этого в регистрах 1, 15, 13 информация обновляется так, как если бы обслуживаемый в данный момент процесс получил по его запросу все требуемые ресурсы в необходимой форме пользования. После этого производится обнуление управляющего входа 4, которое порождает моделирование последовательности состояний вычислительной системы в виде переходного процесса переключения логических элементов, заканчивающегося

I устойчивым состоянием устройства.

При этом на выходе выходного элемента ИЛИ 3 появляется сигнал, характеризующий анализируемое состояние вычислительной сйстемы: "1" означает опасность возникновения тупиковой ситуации, "0" — отсутствие такой опасности. Для обслуживаемого, в данный момент процесса это означает соответственно запрет и разрешение выдать ему ресурсы по его запросу.

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

80890 повторяется и для других сочетаи ш в порядке их предпочтительности.

Рассмотрим моделирование последовательности состояний вычислительной системы более подробно.

При наличии единицы на входе 4, открывающей элементы И IO, сигнал

e ) -ro разрядного выхода регистра

13 1 -го блока 2 передается через элемент ИЛИ 7 на первые входы 1 -х элементов ИЛИ 8 предшествующих блоков 2 и через элементы ИЛИ 9— на вторые входы j --х элементов

ИЛИ 8 последующих блоков 2. Этот сигнал не влияет на входы -го элемента ИЛИ 8 своего блока 2, который, следовательно, имеет на своем входе сигнал принадлежности

1 -го ресурса всем процессам, кроме

1-го процесса: "1" означает, что ресурс принадлежит хотя бы одному иэ

% всех процессов, кроме -ro процес11 са, 0 означает, что этот ресурс свободен или принадлежит 1 -му про25 цессу. С помощью 1 -го элемента

ИЛИ 14 К-й подгруппы i --ro блока 2 производится проверка конкуренции

q-го процесса с другими процессами в части формы пользования -ым ресурсом при формировании К-го альтернативного сочетания ресурсов, которое s --й процесс может запросить в дальнейшем в дополнение к имеющимся у него ресурсам: на выходе это35 ro элемента "0". означает, что если

1-й процесс пожелает воспользоватьс ся 1 -м ресурсом в К-м альтернативном сочетании ресурсов; то только присоединившись к коллективу поль40 зователей 1 -м ресурсом, "1" соответствует остальным сочетаниям имеющейся и желаемой форм пользования этим ресурсом (коллективная единоличная, единоличная — единолич45 ная, единоличная — коллективная), которые являются конкуретными. На выходе -го элемента И 5 К-й подЧ ° группы i -го блока 2 появляется уровень "0" в трех случаях отсутствия

S0 кKоoнHк у р е нHц ии: когда j -й ресурс свободен или принадлежит только 1 -му

I процессу, когда -й процесс не будет запрашивать j -й ресурс в составе К-го альтернативного сочета55 ния ресурсов или когда он будет запрашивать этот ресурс, ислольэуемйй в данный момент коллективно, также в коллективное пользование, 1180890 уровень "1" соответствует следующим случаям конкуренции: когда -й процесс в К-м альтернативном сочетании ресурсов будет требовать себе в единоличное пользование 1 -й ре- сурс, занятый в настоящий момент другими процессами в любой форме пользования, или когда -й процесс в этом же сочетании будет требовать

В коллективную форму пользования 1 -м ресурсом, находящимся в данный момент в единоличном пользовании у одного из других процессов. При этом К-й элемент ИЛИ 6 1 -й группы проверяет наличие конкуренции i -ro процесса с другими процессами в отношении хотя бы одного из ресурсов, требуемых в К-м альтернативном сочетании ресурсов, а элемент

И 11 -ro блока 2 проверяет наличие таких конкуренций во всех альтернативных сочетаниях ресурсов для i --ro процесса. Иначе говоря, уровень "1" сигнала на выходе элемента И 11 j -го блока .2 означает, что свободных ресурсов или ресурсов, используемых коллективно, недостаточно, чтобы сформировать хотя бы одно из альтернативных сочетаний ресурсов, которые могут потребоваться -му процессу1 уровень "0" этого сигнала означает возможность формирования хотя бы

1 одного такого набора для -ro процесса и, следовательно, возможность его завершения. После обнуления входа 4 этот сигнал через элемент

ИЛИ 12 i -го блока 2 передается на входы элемента И 10 j -го блока 2.

Если -й процесс имеет возможность получить все дополнительно требуемые ему ресурсы хотя бы в одном из альтернативных сочетаний, то уровень "0" этого сигнала закрывает элементы И 10 -ro блока 2, как если бы в регистре 13 < --ro блока

2 быпи .записаны все нули. Тем самым моделируется завершение 1 -го !

О процесса и освобождение всех принадлежащих ейу ресурсов единоличного пользования и прекращение его участия в коллективном пользовании ресурсами. Состав свободных ресурсов, 15 пополняясь освобождаемыми ресурса. ми, может оказаться достаточным для завершения других процессов и т.д. Если имеется хотя бы один вариант очередности завершения про20 цессов, то выходной элемент ИЛИ 3 обнаруживает наличие уровней "0" на выходах всех элементов И 11.

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

25 процессов завершение оказывается невозможным, и элемент ИЛИ 3 обнаруживает уровни "1" на выходах элементов И 11, соответствующих этим процессам.

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

1180890

Фию. Г щцщдц Заказ 5926/47 Тираж 709 Подписное

Е,оо,ел mm детеит, r. Удгород, ул Проекте.4