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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИНМ 18 9) 4 С 06 Р 9/46 ЗОБ ТЕНИ ЬС СВИДЕ 5 СССР 979. ССР 980. ст 6,ОСУДАРСТВЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ОПИСАНК АВТОРСКОМУ(54)(57) УСТРОЙСТВО ДЛЯ ВЫЯВЛЕНИЯ ТУПИКОВЫХ СИТУАЦИЙ ПРИ ОБСЛУЖИВАНИИ ЗАПРОСОВ НА РЕСУРСЫ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ, содержащее регистр памяти, выходной элемент ИЛИ и М блоков оценки ситуации (М - число обслуживаемых процессов), каждый из которых содержит первый и второй регистры, элемент И, элемент ИЛИ, пять групп элементов ИПИ и две груп пы элементов И, первая группа элементов И и первая группа элементов ИЛИ-го блока оценки ситуации ( 1 щ 1М) состоят из 0 под групп ( ; - число альтернативных сочетаний ресурсов, требующихся 1-му процессу)по и элементов в каж)дой подгруппе (- число распределяемых ресурсов), выходы четных разрядов первого регистра соединены соответственно с первыми входами элементов И первой группы, вторые вход 3 -х элементов И всех подгрупп первой группы Ц = 1,Й ) соединены с выходом 1 -го элемента ИЛИ второй группы, выходы элементов и К-й подгруппы первой группы (К = 1 3; ) подключены соответственно к входам К-го элемента ИЛИ третьей группы, разрядные выходы второго регистра подключены соответственно к первым входам элементов И второй группы, вторые входы которых объединены и подключены к выходу элемента ИПИ, первые входы элементов ИЛИ всех блоков оценки ситуации объединены и являются установочным входом устройства, выходы элементов И всех блоков оценки ситуации подключены соответственно к входам выходного элемента ИЛИ, выход-го элемента И второй группы соединен с первыми входами 1 -х элементов ИЛИ четвертой и пятой групп, о т л и ч а ющ е е с я тем, что, с целью рас-,ширения функциональных возможностей за счет выявления тупиковых ситуаций при альтернативном запросе ресурсов коллективного и индивидуального пользования, 1 -й выход регистра памяти соединен с первым входом 1-го элемента ИЛИ каждой подгруппы первой группы в каждом блоке оценки ситуации и является ) -м информацион. ныл выходом устройства, а в каждом блоке оценки ситуации выходы нечетных разрядов первого регистра подключены соответственно к вторым вхо" дам элементов ИЛИ первой группы,. выходы которых соединены соответственно с третьими входами элементов И первой группы, выходы элементов ИЛИ третьей группы подключены соответственно к входам элемента И, выход которого соединен с вторымвходом элемента ИЛИ, выход 1 -гоэлемента ИЛИ пятой группы 1 -го блока оценки ситуации ( 1 = 1, М) соедьрен с первым входом 1 -го эле . мента ИЛИ второй группы и вторымвходом 1 -го элемента ИЛИ пятой группы ( 1 + 1)-го блока оценки ситуации, а выход 1 "го элемента ИЛИ четвертой группы-го блока (2, М) оценки еитуации подключен 1180890к второму входу - го элемента ИЛИ четвертой группы и второму входу-го элемента ИЛИ второй группы (- 1) -го блока оценки ситуации.1Изобретение относится к вычислительной техникеи может быть использовано в системах обработки информации в составе цифровых вычислительных машин в части централизо ванного управления вычислительной системой, рассматриваемой в качестве системы массового обслуживания.1.;лью изобретения является расширение Функциональных возможностей устройства эа счет выявления тупиковых ситуаций при альтернативном запросе ресурсов коллективного и индивидуального использования.На фиг. 1 приведена схема уст ройства, на Фиг. 2 - схема блока оценки ситуации.Устройство содержит регистр 1 памяти, М блоков 2 оценки ситуации, выходной элемент ИЛИ 3 и .управляю щий вход 4. Блок 2 оценки ситуации содержит первую группу элементов И 5; третью группу элементов ИЛИ 6, четвер тую 7, вторую 8 и пятую 9 группы элементов ИЛИ, вторую группу элементов И 10, элемент И 11, элемент ИЛИ 12, второй регистр 13, первую группу элементов ИЛИ 14, первый регистр 15, вход 16 и выход 17, выходы 18 элементов ИЛИ 7 и выходы 19 элементов ИЛИ 9. Число разрядов регистра 13 и число элементов ИЛИ в группах 7-9 равно и.35 30 Группа элементов И 5 и группа элементов ИЛИ 14 имеют Р; подгрупп по и элементов в каждой подгруп.пе. Число разрядов регистра 15равно 2 и 0;. Число обслуживаемых ф процессов М, число ресуроов и, число альтернативных сочетаний ресурсов для -го процесса 2;, пределы изменения переменных: 1 = 1, М,и К 1, 4 2Схема устройства на Фиг. 1 и 2соответствует случаю М, и = 4,Р =2.Устройство работает следующимобразом. Первоначально в регистры записывается следующая информация о состоянии вычислительной системы. В регистре 1 1-й разряд указывает, в какой форме пользования 1-й ресурс находится в настоящий момент: "1" - единоличная, "О" - коллективная. В 1 - М блоке 2 в регистре 15 единица в 2(1 + (К)и)-м разряде указывает, что 1-й процесс в будущем может потребовать себе 1-й ресурс в составе К-го альтернативного сочетания ресурсов в дополнение к тем ресурсам, которые у него уже есть, а в (2 (+ (К)и). -1)-м разряде указывается требуемая х-м процессом форма пользования 1-.м ресурсом в составе К-го альтернативного сочетания ресурсов: "1" - единоличная, "0" - коллективная. В регистре 1.3 единица в 1-м разряде указывает, что 1-й ресурс принадлежит -му процессу. Выходы 18 и 19 предназначены ддя того, чтобы по мере увеличения количества обслуживаемых процессов увеличивать количество блоков 2, путем их последовательного соединения. На управляющем входе 4 установлен уровень "1", который через элементы ИЛИ 12 открывает все элементы И 10. Последовательное соединение 1-х элементов ИЛИ 7 каждого блока 2 обеспечивает логическое суммирование сигналов принадлежности 1-го ресурса процессам, снимаемых через 1-е элементы И 10 каждого блока 2 с 1-х разрядных выходов регистров 13. На-м выходе элементов 7 при этом проявляется сиг3 11 нал занятости -го ресурса: 11 - занят, "0" - свободен. Такие же сигналы формируются на выходах элементов ИЛИ 9. Для процесса, обслуживаемого в данный момент, на основе анализа сигналов на выходах регистра 1 и элементов ИЛИ 7 и 9 программным путем производится первая проверка воэможности удовлетворения запроса на ресурсы пока без учета возможных тупиковых ситуаций: ресурс может быть выдан процессу в случаях, когда ресурс свободен или когда процесс требует себе ресурс, используемый в данный момент коллективно, также ч коллективное пользозание. Если 1 -й процесс, использующийся 1 -м ресурсом коллективно, хочет изменить форму пользования на единоличную, то проверка занятости ресурса производится без учета принадлежности 1-го ресурса 1-му процессу, т.е. при временно обнуленном-м разряде 1 -го регистра 13, Если процесс не получил отказ ,на его запрос при первой проверке, то производится вторая проверка, теперь уже с учетом предотвращения тупиковых ситуаций. Для этого в регистрах 1, 15, 13 информация обновляется так, как если бы обслуживаемый в данный момент процесс получил по его запросу все требуемые ресурсы в необходимой форме пользования. После этого производится обнуление управляющего входа 4, которое порождает моделирование последовательности состояний вычислительной системы в виде переходного процесса переключения логических элементов, заканчивающегося1устойчивым состоянием устройства, При этом на выходе выходного элемента ИЛИ 3 появляется сигнал, характеризующий анализируемое состояние вычислительной сйстемы: "1" означает опасность возникновения тупиковой ситуации, "0" - отсутствие такой опасности. Для обслуживаемого, в данный момент процесса это означает соответственно запрет и разрешение выдать ему ресурсы по его запросу.Рассмотренный цикл работы уст" рдйства относится только к одному из альтернативных сочетаний ресурсов в запросе обслуживаемого в данный момент процесса. Этот цикл 80890повторяется и для других сочетанш в порядке их предпочтительности.Рассмотрим моделирование последовательности состояний вычислительной системы более подробно.При наличии единицы на входе 4,открывающей элементы И 10, сигналс 1 -го разрядного выхода регистра 1013 1 -го блока 2 передается черезэлемент ИЛИ 7 на первые входы 1 -хэлементов ИЛИ 8 предшествующихблоков 2 и через элементы ИЛИ 9 -на вторые входы 1 -х элементов 15ИЛИ 8 последующих блоков 2. Этотсигнал не влияет на входы-гоэлемента ИЛИ 8 своего блока 2, который, следовательно, имеет на своем входе сигнал принадлежности1 -го ресурса всем процессам, кроме1-го процесса; "1" означает, что ресурс принадлежит хотя бы одному иэ1всех процессов, кроме-го процес 11 1са, 0 означает, что этот ресурссвободен или принадлежит 1 -му проЪ 51цессу. С помощью 1 -го элементаИЛИ 14 К-й подгруппы-го блока 2производится проверка конкуренции1-го процесса с другими процессамив части формы пользования-ым реЗо сурсом при формировании К-го альтернативного сочетания ресурсов, которое 1 -й процесс может запроситьв дальнейшем в дополнение к имеющимся у него ресурсам: на выходе это го элемента "0" означает, что если1-й процесс пожелает воспользовать 1ся-м ресурсом в К-м альтернативном сочетании ресурсов; то толькоприсоединившись к коллективу поль 40 зователей ) -м ресурсом, "1" соответствует остальным сочетаниямимеющейся и желаемой форм пользования этим ресурсом (коллективнаяединоличная, единоличная - единолич ная, единоличная - коллективная),которые являются конкуретными. Навыходе-го элемента И 5 К-й подЧгруппы-го блока 2 появляется уровень "0" в трех случаях отсутствия 50 конкуренции: когда-й ресурс свободен или принадлежит только 1 -мупроцессу, когда 1 -й процесс не будет запрашивать-й ресурс в составе К-го альтернативного сочета ния ресурсов или когда он будетзапрашивать этот ресурс, ислольэуемйй в данный момент коллективно,также в коллективное пользование, 1180890уровень "1" соответствует следующимслучаям конкуренции: когда-й процесс в К-м альтернативном сочетании ресурсовбудет требовать себе вФединоличное пользование 1 -й ре- сурс, занятый в настоящий момент другими процессами в любой форме пользования, или когда-й процесс в этом же сочетании будет требовать коллективную форму пользования 1 -м ресурсом, находящимся в данный момент в единоличном пользовании у одного из других процессов. При этом К-й элемент ИЛИ 6 1 -й группы проверяет наличие конкуренции-го процесса с другими процессами в отношении хотя бы одного из ресурсов, требуемых в К-м альтернативном сочетании ресурсов, а элемент И 11-го блока 2 проверяет наличие таких конкуренций во всех альтернативных сочетаниях ресурсов для-го процесса. Иначе говоря, уровень "1" сигнала на выходе элемента И 11 1 -го блока .2 означает, что свободных ресурсов или ресурсов, используемых коллективно, недостаточно, чтобы сформировать хотя бы одно из альтернативных сочетаний ресурсов, которые могут потребоваться-му процессу Уровень "0 этого сигнала означает возможность формирования хотя бы1одного такого набора для 1 -го процесса и, следовательно, возможность его завершения. После обнуления входа 4 этот сигнал через элемент ИЛИ 12-го блока 2 передается на входы элемента И 10-го блока 2. Если-й процесс имеет возможность получить все дополнительно требуемые ему ресурсы хотя бы в одномиз альтернативных сочетаний, тоуровень "0" этого сигнала закрывает элементы И 10 1 -го блока 2, какесли бы в регистре 13-го блока2 быпи .записаны все нули. Тем самым моделируется завершение 1 -го О процесса и освобождение всех принадлежащих ейу ресурсов единоличногопользования и прекращение его участия в коллективном пользовании ресурсами. Состав свободных ресурсов, 15 пополняясь освобождаемыми ресурса. ми, может оказаться достаточнымдля завершения других процессови т.д, Если имеется хотя бы одинвариант очередности завершения про цессов, то выходной элемент ИЛИ 3обнаруживает наличие уровней "0"на выходах всех элементов И 11.И наоборот, тупиковая ситуация проявляется в том, что для некоторых 25 процессов завершение оказываетсяневозможным, и элемент ИЛИ 3 обнаруживает уровни "1" на выходах элементов И 11, соответствующих этимпроцессам.30Моделирование последовательности состояний вычислительной системы (последовательности завершенияпроцессов и освобождения принадлежащих им ресурсов) происходит какасинхронный переходный процесс прохождения логических сигналов поцепи логических элементов. Следовательно, предлагаемое устройство по б быстродействию не уступает известномуел ППП Пете ВНИИОИ Заказ 5926/Фнлнит иУлгооол, ул.проектное,е