Устройство для контроля распределения ресурсов

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИК 19) 011 А 1 Р 11/00 ОПИСАНИЕ ИЗОБРЕТЕНИЯ ИДЕТЕЛЬСТВ АВТОРСК ерко,483,ое свидетельство ССС кл, 6 06 Р 11/00, 1(54) .УСТРОЙСТВОДЕЛЕНИЯ РЕСУРСОВ НТР АСПРЕ(57) Изо лительно пользова етение относитстехнике и можетв современных к вычисть исраллельОСУДАРСТВЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(56) 1 пСегпаТдопа 1 Лотпа 1 Бувешас 1 епсе, 1979 ч. 10, У 5, р. 477 Рщ 3.Авторск РУ 1015385, 9 ных вычислительных системах для обнаружения тупиковьх ситуаций, Цель изобретения - повышение быстродействия, Сущность изобретения состоит в том, что новая совокупность конструктивных признаков позволяет повысить оперативность контроля путем сокращения числа необходимых для обнаружения тупика рабочих циклов, а также реализации возможности контроля систем с ресурсами, емкость которых более единицы, При этом конструкция устройства позволяет регистрировать и хранить для каждого ресурч са множество кодов номеров процессов (по числу единиц ресурса каждого ти". д па), владеющих ресурсом, а также множество кодов номеров процессов, запрашивающих ресурс. 9 ил.1129 дом второго триггера управления единичный выход которого соединен с первым входом шестого элемента И,выход седьмого элемента И, соединен с синхровходом второго распределителя импульсов, ш-выходов которого соединены с соответствующим управляющим входом второго информационного мультиплексора, (ш+1)-й выход второго распределителя импульсов соединен с вторым входом второго элемента И, выход первого элемента ИЛИ-НЕ соединен с (1+1)-м инверсным входом первого элемента И (где 1 - разрядность кода, указывающего на номер процесса функционирующего в системе), прямой и инверсный выходы первого триггера управления соединены с вторыми входами соответственно четвертого и пя того элементов И, выход третьего элемента И соединен с единичным входом триггера тупика, прямой выход которого является выходом признака тупика устройства, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, в устройство вве" дены (2 щ) блоков регистров, блок синхронизации, третий и четвертый распределители импульсов,(2 ш) управляющих мультиплексоров, регистр единиц ресурсов, шифратор, вторая схема сравнения, третий, четвертый и пятый триггеры управления, (2 щ) блоков элементов И, коммутатор, четырнадцать элементов И, семь элементов ИЛИ и второй элемент ИЛИ-НЕ, причем группы выходов блоков регистров с третьего по (ш+1)-ый соединены с второй группой входов первого информационного мультиплексора и с информационными входами соответствующих управляющих мультиплексоров с третьего по (щ+1)-ый группы выходов блоков регистров с (щ+2)-го по 2 щ-ый соединены с второй группой информационных входов второго информационного мультиплексора и с группами информационных входов соответственно с (щ+2)-го по 2 щ-ый управляющих мультиплексоров, выходы которых соединены с первыми входами начальной установки с третьего по (щ+1)-ый блоков регистров, первые выходы управляющих мультиплексоров с третьего по (щ+1)-ый соединены с входами начальной установки с (ш+2)- го по 2 щ-ый блоков регистров, вторые выходы управляющих мультиплексоров 7051 18с первого по (ш+1)-ый соединены ссоответствующими входами восьмогоэлемента И, инверсный выход которого соединен с вторым входом третьегоэлемента И, вход пуска устройствасоединен с входом запуска блока синхронизации, с первым входом второгоэлемента ИЛИ, с нулевыми входамитриггеров тупика и анализа, первый 10 выход блока синхронизации соединенс управляющими входами всех управляющих мультиплексоров, с вторымивходами первого и второго блоковэлементов И, второй выход блока 15 синхронизации соединен с первымивходами девятого, десятого, одиннадцатого и тринадцатого элементов Итретий выход блока синхронизациисоединен с первыми входами четырнад цатого, пятнадцатого, шестнадцатогои семнадцатого элементов И, четвертый выход блока синхронизациисоединен с вторым входом шестого идевятнадцатого элементов И, выходседьмого элемента И соединен с входом установки в "О" третьего триггера управления, прямой выход которогосоединен с вторым входом седьмогоэлемента И, группа выходов третьего ЗО распределителя импульсов соединенас тактовыми входами первого информационного мультиплексора, с входамипервого элемента ИЛИ-НЕ и входамишифратора, выход которого соединен 35 с первым входом второй схемы сравнения, первый выход первого распределителя импульсов соединен с вторымвходом тринадцатого элемента И,выходкоторого соединен с нулевым входом 40 первого триггера управления, группатактовых выходов четвертого распределителя импульсов соединена с второй группой тактовых входов второгоинформационного мультиплексора и вхо дами второго элемента ИЛИ-НЕ,выходкоторого соединен с инверсным входомдвадцатого элемента И, выход четвертого распределителя импульсов соединен с первыми входами третьего и 50 четвертого элементов ИЛИ, выходы которых соединены с вторыми входамисоответственно шестнадцатого и двенадцатого элементов И, группа выходов второго информационного мульти плексора соединена с группой входовчетвертого блока элементов И и группой инверсных входов двадцатого элемента И, прямой выход которого сое 19 1297051 20динен с вторыми входами третьего ичетвертого элементов ИЛИ, с первымивходами пятого и шестого элементовИЛИ, инверсный выход двадцатого элемента И соединен с вторым входом четвертого блока элементов И, выход которого соединен с вторым входом первой схемы сравнения, выходы регистра единиц ресурсов соединены синформационными входами коммутатора,выходы которого соединены с вторыми входами второй схемы сравнения, выходкоторой соединен с первым входомседьмого элемента ИЛИ, выход которого соединен с первым входом восьмого элемента ИЛИ, с третьим входомпервого элемента ИЛИ и с вторым входом четырнадцатого элемента И, выход восьмого элемента ИЛИ соединенс третьим входом второго элементаИЛИ, вторым входом шестого элемента ИЛИ, третьим входом третьего элемента ИЛИ вторым входом семнадцатого элемента И, выход второго элемента ИЛИ соединен с вторым входом девятого элемента И, выход которогосоединен с единичным входом четвертого триггера управления, единичныйвыход которого соединен с вторымвходом восемнадцатого элемента И,выход которого соединен с нулевымвходом четвертого триггера управления, с тактовым входом третьего распределителя импульсов и нулевымвходом триггера совпадения, выходпятого элемента ИЛИ соединен с вторым входом одиннадцатого элементаИ, выход которого соединен с единичным входом пятого триггера управления,выход шестого элемента ИЛИ соединен с первым входом двадцать первого элемента И, выход которого соединен с нулевым входом пятого триггера управления, единичный выходкоторого соединен с вторым входомдевятнадцатого элемента И,выход семнадцатого элемента И соединен с единичным входом третьего триггерауправления,входы единиц ресурсов устройства соединены с информационнымивходами регистра единиц ресурсов устройства, единичный выход триггерасовпадения соединен с вторым входоМвосьмого элемента ИЛИ, выход второго элемента И соединен с третьимвходом восьмого элемента ИЛИ,выходчетвертого элемента И соединен свторым входом седьмого элемента ИЛИи вторым входом пятнадцатого элемента И, выход которого соединен свходом останова первого распределителя импульсов, инверсный выход первого элемента И соединен с вторымвходом пятого элемента ИЛИ и третьим входом четвертого элемента ИЛИ,четвертый выход блока синхронизациисоединен с вторым входом двадцатьпервого элемента И,выход которогосоединен с нулевым входом пятоготриггера управления, выход первогоэлемента ИЛИ соединен с вторым входом десятого элемента И, выход которого соединен с единичным входомвторого триггера управления, выходчетырнадцатого элемента И соединенс входом начальной установки третьего распределителя импульсов, выходыдевятнадцатого, щестнадцатого исемнадцатого элементов И соединенысоответственно с тактовым входомчетвертого распределителя импульсов,с входом начальной установки четвертогоо распределителя импульсов и входом начальной установки второгораспределителя импульсов, группа выходов первого распределителя импульсов соединена с управляющими входамикоммутатора, единичный выход тригге"ра анализа соединен с входом останова блока синхронизации, выходы блоковэлементов И . третьего по 2 ш-ый соединены с информационными входамисоответствующих блоков регистров,входы кодов номеров процессов, владеющих ресурсами устройства, соединеныс первой группой входов блоков эле 5 1 О 15 20 25 30 35 40 45 ментов И, начиная с третьего по 50 2 щ-й,первый выход блока синхронизациисоединен с вторыми входами блоков элементов И,начиная с 3 - го по 2 в-й.(ш+2)-й,входы кодов номеров процессов затрачивающих ресурсы устройствасоединены с первой группой входовблоков элементов И,начиная.с(в+3)-го по1297051 Составитель И.Сигаловактор Т.Парфенова Техред М.Ходанич Корректор. Г.Решетник Зака г.о ий Ужгород, ул, Проектная, 4 оизводственно-полиграфическое предприятие 2 Тираж 67 НИИПИ Государственпо делам изобрет 113035, Москва, Ж Подписноекомитета СССРи открытийРаушская наб., д. 4зовано в современных параллельных вычислительных системах для обнаружения тупиковых ситуаций. 5Целью изобретения является повышение быстродействия.На фиг, 1 представлена функцио- нальная схема предлагаемого устройства для контроля распределения ресур сов; на фиг. 2 - функциональная схема блока 1.1 регистров; на фиг. 3 Функциональная схема блока 2. регистров; на фиг, 4, - Функциональная схема блока синхронизации; на фиг. 5 - функциональная схема распределителя импульсов; на фиг. 6 - Функциональная схема управляющего иультинлексо" ра 8,х; на Фиг. 7 - Функциональная схема управляющего мультиплексора 20 9,х; на фиг. 8 - Функциональная схема информационного мультиплексора; на фиг. 9 - временные диаграимы функционирования устройства.Устройство для контроля распределения ресурсов (фиг. 1) содержит первый (1.1) - (ш+1)-ый (1.ш) блоки регистров, второй (2,1) - 2.ш-ый (2.ш) блоки регистров, блок 3 синхронизации, третий распределитель 4 импульсов, первый распределитель 5 импульсов, четвертый распределитель 6 импульсов, второй распределитель 7 импульсов, первый (8.1) - (ш+1)-й (8.ш) управляющие мультиплексоры второй 9.1 - 2.ш-й 9.ш управляющие мультиплексоры, первый информационный мультиплексор 10, второй информационный мультиплексор 11, регистр 12 единиц ресурсов, первую схему 13 40 сравнения, шифратор 14,вторую схему 15 сравнения, четвертый 16, второй 17, пятый 18, третий 19 триггеры управления, триггер 20 совпадения, триггер 21 тупика, первый триггер 45 22 управления, триггер 23 анализа, блоки элементов И 24.1 - 24,п, блоки элементов И 25.1 - 25.п, блоки элементов И 26, 1 - 26.1 с; 27.1 - 27,К, где п - максимально возможное число 50 единиц ресурса данного типа, а 1 - число запросов к ресурсу данного типа, коммутатор 28, блок 29 элементов И, восьмой 30, девятый 31, десятый 32, восемнадцатый 33, четырнадцатый 55 34, шестой 35, пятнадцатый 36, тринадцатый 37, первый 38, третий 39, второй 40, четвертый 41, пятый 42,35 1 12970Изобретение относится к вычислительной технике и может быть исполь 51 2одиннадцатый 43, двадцатый 44, двенадцатый 45 девятнадцатый 46, шест надцатый 47, седьмой 48, семнадцатый 49, двадцатый 50 элементы И,блок 51 элементов И, седьмой 52, восьиой 53, второй 54, первый 55, элемент ИЛИ-НЕ 56, пятый 57, шестой 58,третий 59, четвертый 60 элементы ИЛИ, второй 61 элемент ИЛИ-НЕ,вход пуска 62 устройства, первую группу 63 и вторую 64 информационных входов устройства, третью группу 65 информационных входов устройства, выход бб устройства.На фиг, 4 приняты обозначения: первый 67,второй 68,третий 69 и четвертый 70 выходы блока 3 синхрониза- ции.Кроме того на чертежах приняты обозначения:выходы 71.1 - 71.ш и 72.1- 72,ш мультиплексоров 8,1 - 8.п,выходы 73.1 - 73,ш мультиплексоров 9,1 - 9.ш, группа выходов 74.1 74.п распределителя импульсов 4, группа выходов 75.1 - 75.ш распределителя импульсов 5, выход 76 распределителя 5, группа выходов 77.1 77.Е распределителя 6, выход 78 распределителя б,группа выходов 79,1 79.ш распределителя б,группа выходов 79,1 - 79.ш распределителя импульсов 7, выход 80 распределителя импульсов 7, выходы 811 - 81,ш блока элементов И 29, информационные выходы 82.1 - 82.ш регистров 1.1 - 1.ш,инФормационные выходы регистров 83,1 83.ш регистров 2. 1 - 2,ш, вход 84 останова блока 3 синхронизации;Блок 1 регистров (фиг. 2) содержит регистры 85.1 - 85.п, элемент ИЛИ 86, первую (87. 1) - и-ю (87.п) группы информационных входов, первый 81, и второй 73, управляющие входы, группу 82, выходов, состоящую из первой (88. 1) - и"ой (88.п) групп выходов соответственно первого (85.1) - и-го (85.п) регистров.Блок 2.х регистров (фиг. 3) содержит регистры 89.1 - 89.К, первую 90.1 1-ю 90,; группы информационных входов, управляющий вход 72.2.,группу 83. выходов, состоящую из первой 91.1 - 1-ой 91.к групп выходов соответственно первого 89.1 - Е-го 89,1 с регистров.Блок 3 синхронизации (фиг. 4) содержит триггер 92 режима, генератор 93 последовательностей импульсов, элемент И 94, вход 62 пуска,13 12управляющий вход 84, первый 67,второй 68, третий 69 и четвертый 70выходы.Единичный выход триггера 92 режима соединен с управляющим входомгенератора 93 последовательностейимпульсов, а также с первым входомэлемента И 94, выход которого соединен с нулевым входом триггера92 режима.Распределители 4 - 7 импульсовимеют идентичную функциональнуюсхему (фиг. 6) .Причем (и+1)-й выходраспределителя 4 импульсов не используется, В скобках на фиг, 5 обозначены номера соответствующих входови выходов соответственно распределителей 5 - 7 импульсов,Распределитель 4 (5 - 7) импульсов содержит счетчик 95 с входом установки в ноль, дешифратор 96 с синхровходом. Вход 97 - счетный входраспределителя импульсов, вход 98 -останова распределителя.Управляющий мультиплексор 8.(107) группы блоков элементов И,блок108 элементов ИЛИ.Регистр 12 (фиг. 1) единиц ресурсов предназначен для приема, хранения и выдачи количества единиц ресурсов для каждого типа ресурса.Причем, регистр 12 условно разбит наш полей по числу типов ресурсов.В-ое поле в момент запуска системыс группы 65 входов заносится кодмаксимального количества единиц -го типа ресурса.Схема 13 сравнения предназначенадля сравнения кодов номеров процессоров запрашивающих ресурсы и владеющих ими, Шифратор 14 предназначендля формирования текущего кода единицы ресурса данного типа. Схема 15сравнения предназначена для сравнения текущего кода единицы ресурсаданного типа с кодом количества единиц ресурса данного типа. Триггеры16 - 19 управления предназначены дляуправления работой распределителей4 - 7 импульсов соответственно.Триг 97051 4 гер 20 совпадения предназначен для фиксации наличия номера анализируемого процесса, владеющего ресурсом среди множества процессов, запрашивающих ресурсы, а также для формирования "игнала разрешения выбора следующего кода номера процесса, владеющего каким-либо ресурсом.Триггер 21 тупика предназначен для фиксирования сигнала тупика.Триггер 22 управления предназначен для фиксирования сигнала, указывающего на факт удаления хотя бы одного процесса в результате анализа. Триггер 23 анализа предназначен для фиксации сигнала окончания анализа.. Группы (24.1 - 24.п) - (25,1 25.п) блоков элементов И предназначен для одновременной передачи информации о кодах номеров процессов, владеющих ресурсами, с входа 63 устройства в регистры блоков 1,1 - 1.ш регистров, Группы (26.1 - 26.1 с) (27.1 - 27,К) блоков элементов И 5 1 О 15 20 дачи информации о кодах номеров процессов, запрашивающих ресурсы,с входа 64 устройства в регистры блоков2.1 - 2.ш регистров,Коммутатор 28 предназначен дляформирования на выходной шине кода,выбранного одним из управляющих сигналов. Элементы 29.1 - 29.ш предназначены для формирования сигналов ус-тановки в ноль регистров блоков1.1 - 1.т регистров,Элемент И 30 предназначен дляформирования сигнала-идентификаторанулевого состояния регистров 1. 11.ш. Элементы И 31 - 36,43 - 49 предназначены для синхронизации работыэлементов устройства, Элемент И 37предназначен для формирования сигнала установки в нулевое состояниетриггера 22 управленияЭлемент И 38(50) предназначен для формированиясигнала разрешения выбора следующего кода номера процесса, владеющего (запрашивающего) как тм-либо ресурсом системы. Элемент И 39 предназначен для формирования сигнала тупика. Элемент И 40 предназначен дляформирования сигнала-признака того,что при анализе были удаления прЬцессов. Элемент И 41 предназначендля формирования сигнала разрешениянового цикла анализа. Элемент И 42предназначен для формирования сигна 30 35 40 45 -50 55 25 предназначены для одновременной перела установки в единичное состояниетриггера 23 анализа. Блок 51 элементов И предназначен для одновременной передачи кода с выхода мультиплексора 11 на вторую группу входов схемы 13 сравнения.Элементы ИЛИ 52 - 55 предназначены для формирования сигналов разрешения первой и последующих выбороккодов номеров процессов,владеющихресурсами, а также для управленияработой распределителей 6 и 7 импульсов.Элементы ИЛИ-НЕ 56 и 61 предназначены для формирования сигналов,правляющих работой элементов И 38и 50 соответственно. Элементы ИЛИ57 - 60 предназначены для формирования сигналов разрешения выбора кодовномеров процессов, запрашивающих ресурсы.Вход 62 пуска предназначен дляприема сигнала пуска устройства.Первая группа 63 информационных входовпредназначены для приема кодов номеров процессов, владеющих единицамиресурсов. Вторая группа 64 информационных входов предназначена для приема кодов номеров процессов, запрашивающих единицы ресурсов. Третьягруппа 65 информационных входов предназначена для приема информации омаксимальном количестве единиц ресурсов х-го типа ( = 1,ш).Выход бб устройства предназначендля выдачи сигнала-признака тупиковой ситуации в вычислительной системе,Рассмотрим функциональное назначение элементов блока 1, регистров (фиг. 2).Регистр 85.3 предназначен дляприема, хранения и выдачи информации о коде процесса, владеющего 3-ойединицей -го ресурса. Элемент ИЛИ86 предназначен для формированиясигнала установки в нуль регистров86.1 - 86.п. Группа 87,3 информационных входов предназначена для приема в регистр 85.3-го кода номера процесса, владеющего единицами ресурса1-го типа,Рассмотрим функциональное значение элементов блока 2 регистров(фиг, 3).Регистр 89.3 предназначен дляприема, хранения и выдачи информациио коде номера процесса, запрашиваю 5 10 15 20 25 30 35 40 щего 3-ю единицу -го типа ресур-са, Группа 90.3 информационных входов предназначена для приема в регистр 89.1 кода номера процесса,запрашивающего 3-ю единицу -го ресурса, Вход 72. предназначен дляустановки в нуль всех регистров блока 2. регистров. Группа 83, выходов предназначена для выдачи информации о кодах номеров процессов,запрашивающих единицы ресурса х-готипа,Рассмотрим функциональное назначение элементов блока 3 синхронизации (фиг, 4).Триггер 92 режима предназначендля формирования сигнала запуска генератора 93. Генератор 93 предназначен для формирования трех последовательностей импульсов на выходах67 - 70 (фиг, 9) блока 3, ЭлементИ 94 предназначен для формированиясигнала установки в ноль триггера 92режима, Вход 62 пуска предназначендля приема сигнала пуска устройства.Вход 84 предназначен для приема сигнала окончания анализа. Выход 67предназначен для выдачи сигнала управления работой управляющих мультиплексоров 8.1 - 8.ш, 9.1 - 9.щ, атакже для управления приемом информации в регистры всех блоков.Функциональное назначение элементов распределителя 4 (5 - 7) импульсов следующее,Счетчик 95 предназначен для формирования кода .выбора очередного процесса. Дешифратор 96 предназначендля формирования сигнала выбора кода очередного процесса для анализа,Счетный вход 97 предназначен дляприема импульсов на одноименный входсчетчика 97, Вход 98 установки предназначен для приема сигнала установки в ноль счетчика 95, Группа выходов 74.1 - 74.п (75.1 - 75,ш; 76;77.1 - 7.1 с; 78 у 79.1 - 79.ш, 80)предназначена для выдачи распределенных во времени импульсов.Рассмотрим функциональное назначение элементов управляющего мультиплексора 8.д (фиг. 6).Элемент 99.д предназначен для формирования сигнала разрешения в случае нулевого входного кода.Элемент 100 предназначен для формирова ния сигнала управления, если все сигналы разрешения положительные,1297051 т,е, все регистры блока 1. регистров находятся в нулевом состоянии. Элемент ИЛИ 101 предназначен для формирования сигнала управления работой блока 2.х регистров. Группа 82. информационных входов предназначена для приема кодов номеров процессов, владеющих единицами ресурса -го типа с целью дальнейшего анализа. Вход 68 предназначен для 10 приема сигнала разрешения работы мультиплексора. Выходы 71. и 72. предназначены для выдачи сигналов управления.Элементы управляющего мультиплек сора 9. имеют следующие функциональные значения (фиг. 7).Элемент 102.3 предназначен для формирования признака отсутствия запроса на 3-ю единицу х-го ресурса. 20 , Элемент 103 предназначен для формирования сигнала установки в нуль регистров соответствующег блока 1.д регистров. Группа 83. информационных входов предназначена для приема 25 кодов номеров процессов, запрашивающих -й ресурс, Вход 68 предназначен для приема сигнала разрешения работы мультиплексора, Выход 73.д предназначен для управления раба той соответствующего блока 1.х регистров.Рассмотрим функциональное назначение элементов мультиплексора 10 (11) (фиг, 8), 35 Блоки 104 (105) - 106 (107) элементов И соответственно первой ш-ой групп предназначены для выбора кодов номеров процессов, владеющих (запрашивающих) соответствующими единицами ресурсов различных типов. Элементы ИЛИ 108, 1 - 108.1 предназначены для формирования кодов номеров процессов, владеющих (запрашивающих) ресурсами (ресурсы). Группа 82 (83) информационных входов предназначена для приема кодов номеров процессов, владеющих (запрашивающих) ресур" сами (ресурсы). Группы 74 (77) и 75 50 (79) входов предназначены для приема сигналов управления работой мультиплексора.Группа 109 выходов предназначена для выдачи на вторую группу входов схемы 13 сравнения кода йоме ра процесса, владеющего (запрашивающего) соответствующей единицей какого-либо типа ресурса,8Работа устройства происходит в соответствии со следующим алгоритмом.В тупиковую ситуацию могут быть вовлечены только те процессы, которые владеют какими-либо ресурсами и дополнительно их запрашивают.В свою очередь, в тупик могут быть вовлечены только те ресурсы, которыми процессы владеют (все единицы ресурса заняты) и на них есть запросы от других процессов (хотя бы один запрос). Ресурсы, на которые нет за росов, либо свободна хотя бы одна единица ресурса из дальнейшего анализа удаляются, так как в анализируемый момент времени С они в тупик вовлечены не будут. Удаление (обнуление соответствующего блока 1., 2. регистров) производится по сигналам с выходов управляющих мультиплексоров 8.х и 9. (1 = 1,ш).Принцип действия устройства основан на последовательном поиске номеров тех процессов, которые и владеют, ресурсамй (единицами ресурсов) и запрашивают их, Причем, при обнаружении факта совпадения кодов (процесс не только владеет, но и запрашивает ресурсы) анализ по данному процессу прекращается и осуществляется выбор очередного владельца по сигналу с единичного выхода триггера .20 совпадения.Процедуру полного просмотра и сравнения кодов номеров процессов, владеющих ресурсами, с кодами номеров процессов, запрашивающих их по всем типам ресурсов, назовем циклом анализа.Тогда, если в результате анализа владельца единицы ресурса определенного типа по просителям всех типов ресурсов не обнаружено искомого кода, то данный процесс из дальнейшего ана" лиза необходимо удалять, Следователь" но, ресурс, единицей которого владел анализируемый процесс, в тупик также вовлечен не будет. Поэтому производится обнуление соответствующего блока 1. регистров и с помощью управляющего мультиплексора 8.д блока 2. регистров. Кроме того, триггером 22 фиксируется факт удаления" процесса в цикле анализа.Если текущий цикл анализа завершен и в нем были удаления процессов, то процедура анализа продолжается.9 129Сигналом с выхода элемента И 41 инициируется очередной цикл анализа,Впротивном случае работа устройствапрекращается и анализируется сосгояние блоков 1,д регистров (д = 1,ш),в которых записываются коды номеровпроцессов, владеющие соответствующими типами ресурсов. Если они нулевые,то тупика в системе нет,иначе - тупик. Причем, оставшиеся кодыномеров процессов по соответствующимресурсам и составляют тупиковоемножество процессов и ресурсов.Предлагаемое устройство функционирует следующим образом,В исходном состоянии все триггеры находятся в нулевом состоянии(входы начальной установки не показаны). Единичный потенциал с первого выхода 67 блока 3 (нулевого выхода триггера 92 блока 3 (фиг. 4).Синхронизации разрешает прием информации через блоки 24 - 27 элементов И о состоянии распределения ресурсов системы и запросов на них врегистры соответствующих блоков 1,1и 2, регистров (1,щ, где ш -число типов ресурсов в системе).Этим же сигналом управляющие мультиплексоры 8. и 9.1 (х1,ш) закрыты. Взаимная установка в нулевоесостояние регистров соответствующихблоков 1.д и 2,1 регистров (1,щ) запрещенаПо сигналу пуска (начала анализа),поступающему на вход 62 устройства(фиг. 1), триггер 92 блока 3 (фиг. 4)устанавливается в единичное состояние. Включается генератор 93 потенциалом с единичного выхода этоготриггера и начинается формированиепоследовательностей импульсов на выходах генератора 93 блока 3 синхронизации в соответствии с временнымидиаграммами, приведенными на (фиг, 9)Нулевым сигналом с выхода 67 блокируется прием информации в регистрыблоков 1.1 и 2. регистров и открываются мультиплексоры 8. и 9,1.Если хотя бы один регистр блока1,1 регистров содержит нулевой код-го типа свободна), то на выходе72.1. управляющего мультиплексора8.1 формируется единичный сигнал,который является сигналом установкив нуль всех регистров блока 2. регистров. Кроме того, единичный сиг 7051 10нал цармируется на выходе 73.3 мультиплексора 9,1, для которого всерегистры соответствующего блока2.3 регистров имеют нулевые кодыЗтот сигнал является сигналом установки в нуль регистров блока 1,1регистров.Сущность этих операций состоит висключении из дальнейшего рассмотреЮ ния процессов, которые заведомо могут быть завершены и, вследствиеэтого,к тупику не приведут. Далее производится переход к выявлению процессов, которые являются только владель 15 цами некоторых единиц ресурсов, асами дополнительно никакие другиеединицы ресурсов не запрашивают. Еслинекоторый процесс является тольковладельцем какой-либо единицы ресур 20 са определенного типа, то его номерне должен быть записан ни в одномиз блоков 2, 1 - 2,ш . регистров,Напроверке этого факта основываетсявыявление процессов, которые только25 владеют ресурсами,Одновременно сигнал пуска с входа62 устройства через элементы ИЛИ 54и 55 поступает соответственно навходы элементов И 31 и 32 и импуль 3 О сом с выхода 68 блока 3 синхронизации эти элементы открываются. Третий16 и первый 17 триггеры управленияпри этом устанавливаются в единичное состояние. Сигналы с единичных35 выходов триггеров 16 и 17 поступаютна входы элементов И 33 и 35 соответственно,Импульс с выхода 65 блока 3 синхронизации открывает элементы И 3340 и 35 и поступает на счетные входыраспределителей 4 и 5 импульсов(фиг, 5) соответственно.Сигналы с первых выходов соответственно 74.1 и 75. 1 распределителей45 4 и 5 через первую группу 104 блоковэлементов И, а также блок 108 элементов ИЛИ мультиплексора 10 (фиг 8)разрешают подключение выходов первого регистра 85.1 блока 1.1 регистров50 (фиг. 2) к первой группе входов схемы 13 сравнения (фиг. 1).Если кодпроцесса в первом 85,1 регистре(фиг, 2) оказывается нулевым,то элемент И 38 (фиг. 1) на прямом выходе55 вырабатывает сигнал, инициирующийпереход к исследованию содержимогоследующего регистра в блоке 1,1 регистров, Таким образом организуется11 1процесс анализа по всем единицам ресурса первого типа,Если же, выбранный код процессане нулевой, то на инверсном выходеэлемента И 38 формируется сигнал,разрешающий выбор кода номера процесса среди запросов для дальнейшего анализа.Импульсом с выхода элемента И 33триггер 20 совпадения устанавливается в нулевое состояние. Сигналс первого выхода 75.1 распределителя 5 импульсов подается на вход элементаИ 37. Код с выходов 74.174.п распределителя 4 импульсов(фиг, 1 и 5) поступает на шифратор14, с выходов которого в модифицированном виде подается на первуюгруппу входов второй схемы 15 сравнения.По заднему фронту импульса с выходов элементов И 33 и 35 триггерысоответственно 16 и 17 устанавливаются в нулевое состояние, блокируятем самым счетные входы распределителей 4 и 5 импульсов соответственно.Итак, если выбранный код владельца единицы ресурса первого типа оказался отличным от нуля, то сигналс инверсного выхода элемента И 38через элементы ИЛИ 57 и 60 поступаетна входы элементов И 43 и 45 соответственно. Импульс с выхода 68 блока3, синхронизации (фиг. 4) открываетэлементы И 43 и 45 и поступает наединичные входы триггеров 18 и 19управления, устанавливая их в единичное состояние,Положительные потенциалы с единичных выходов этих триггеров поступают на входы элементов И 46 и48 соответственноИмпульс с выхода70 блока 3 синхронизации, открываяэлементы И 46 и 48, поступает насчетные входы распределителей 6 и7 импульсов соответственно.Сигналы с первых выходов 77,1 и79.1 распределителей 6 и 7 черезпервую группу 105 блоков элементовИ,а также блок 108 элементов И мультиплексора 11 (фиг. 8) осуществляют коммутацию выходов первого регистра 89.1 блока 2,1 регистров навыходы мультиплексора.Если код процесса в этом регистре нулевой, то на прямом выходе элемента И 50 формируется положитель 29705112ный сигнал, который инициирует выбор очередного запроса ресурса того же типа.На инверсном выходе элемента И50 (фиг, 1) вырабатывается низкий потенциал, который запрещает передачу кода номера процесса на вторуюгруппу входов схемы 13 сравнения. Если же код выбранного процесса10не нулевой, то на инверсном выходе элемента И 50 формируется сигнал разрешения, по которому код номерапроцесса, запрашивающего единицу ресурса первого типа, подается на15вторую группу входов схемы 13 сравнения.По заднему фронту импульса с выхода элемента И 48 триггер 19 управления устанавливается в нулевое состояние. Выходные коды с распределителей 4 и 6 импульсов во время выборки кодов номеров процессов для анализа подаются соответственно на элементы ИЛИ-НЕ 5 б и 61, которые управ 25 ляют работой элементов И 38 и 50 соответственно,Если сравниваемые коды не равны,то далее распределитель б импульсовобеспечивает выбор кОдов номеров за 30 просов в пределах одного типа ресурса. По каждому очередному импульсус выхода 70 блока 3 синхронизации(фиг. 4) на выходах распределителя6 последовательно вырабатывается пос 35 ледовательность сигналов, которыеуправляют работой мультиплексора 11.Этот мультиплексор осуществляет выбор содержимого очередного регистра блока 2.1 регистров.40 Процедура выбора просителей можетзавершиться при выполнении одногоиз трех условий: исчерпались все коды номеров процессов, запрашивающихданный тип ресурса (код очередного45 процесса в регистре - нулевой);просмотрены все коды номеров процессов,запрашивающие данный ресурса (на(к+1)-ом выходе распределителя 6 импульсов Формируется положительный50 сигнал); равны кодов номеров процессов.При выполнении первого условиянулевым сигналом с инверсного выхода элемента И 50 блок элементов И 5155 закрывается, а на прямом выходеэлемента И 50 формируется положительный потенциал, который поступает навходы элементов ИЛИ 57 - 60.Поэтому13 12по заднему фронту импульса с выхода70 блока 3 синхронизации (фиг, 4)триггер 18 устанавливается в нуле-.вое состояние.Импульсом с выхода 69 блока 3синхронизации распределитель 6 импульсов устанавливается в исходноесостояние. По импульсу с выхода 68блока 3 синхронизации триггеры 18и 19 устанавливаются в единичныесостояния, открывая тем самым счетные входы распределителей 6 и 7 импульсов. Таким образом производитсяпереход к анализу запросов очередного типа ресурса.В случае выполнения второго условия на (1+1)-ом 78 выходе распределителя 6 импульсов формируется сигнал, инициирующий переход к анализузапросов очередного ресурса,При этомсигнал через элементы ИЛИ 60 и И 50по импульсу с выхода 68 блока 3 син 1хронизации устанавливает триггер 19в единичное состояние, а через элементы ИЛИ 59 и И 47 импульсом с выхода 69 блока 3 синхронизации устанавливает распределитель 6 импульсовв исходное состояние.Очередной импульс с выхода 70блока 3 синхронизации поступает насчетные входы распределителей 6 и 7импульсов,Таким образом, процесс анализапродолжается аналогично описанному.Если во время последовательногосравнения кода номера процесса,вла- .деющего единицей ресурса определенного типа, с кодами номеров процессов, хранящихся в регистрах блоков2,1 - 2,ш регистров, происходит хотя бы одно совпадение (исследуемыйпроцесс не только владеет ресурсами,но и запрашивает их), то срабатывает триггер 20 совпадения и устанавливается в единичное состояние.По этому сигналу производитсявыбор содержимого очередного регистра в пределах исследуемого ресурса,т,е. очередного регистра блока 1.1регистров (1 = 1, ш). Кроме того,осуществляется установка в исходноесостояние распределителей 6 и 7 импульсов. Если же их в результатеанализа всех запросов для выбранноговладельца совпадений не произошло(исследуемый процесс дополнительноне затрачивает ресурсы), т.е. триггер 20 находится в нулевом состоянии97051 14 5 10 15 20 25 30 35 40 45 50 55 и присутствует сигнал с последнеговыхода 80 распределителя 7 импульсов,то срабатывает элемент И 40. Приэтом триггер 22 устанавливается вединичное состояние. Одновременносигналом с выхода элемента И 40 открывается соответствующий элементблока 29 элементов И, и сформированный сигнал поступает на первый управляющий вход соответствующего блока1,д регистров, устанавливая тем самым все регистры в нулевое состояние.Описанные действия позволяютучесть тот факт, что если свободнахотя бы одна единица ресурса данного типа, то в анализируемый моментвремени по данному ресурсу тупика неможет быть.Через соответствующий управляющиймультиплексор 8.1 происходит коррекция содержимого соответствующегоблока 2, регистров.Если все коды номеров процессов,владеющие единицами ресурса данноготипа, проанализированы,то на выходесхемы 15 сравнения формируется положительный сигнал. Это происходит врезультате совпадения кодов, поступающих на ее входы. При этом на первую группу входов поступает код номера анализируемой единицы ресурса(анализ процесса, владеющего даннойединицей ресурса определенного типа),а на вторую - код максимального количества единиц в исследуемом типересурса.Сигнал с выхода схемы 15 сравнения инициирует переход к анализуочередного типа ресурса с предварительной установкой в исходное состояние распределителей 4 - 7 импульсов,Аналогично описанному анализ продолжается до тех пор, пока не исчерпаются все щ типов ресурсов (блоки1,д, д = 1,т). Сигнал с выхода 76распределителя 5 импульсов поступаетна элементы И 41 и 42Если в данном цикле анализа былиудаления процессов, то сигналом сединичного выхода триггера 22 открывается элемент И 41, сигнал с выхода которого но тактовому импульсу свыхода 69 блока 3 через соответствующие элементы И 34, 36, 47 и 49устанавливает и распределители 4 - 7импульсов в исходное состояние и инициирует начало следующего цикла анализа, 15161297051Если в очередном цикле анализа не было удалений процессов, которые могут завершиться, то срабатывает элемент И 42, сигнал с выхода которого устанавливает триггер 23 в единичное состояние. Сигнал окончания анализа с единичного выхода триггера 23 поступает на управляющий вход 84 блока 3 синхронизации и через элемент И 94 по импульсу с выхода 68 устанавливает триггер 92 режима в нулевоесостояние. На этом функционирование устройства прекращается и производится идентификация состояния системы.Сигнал с выхода триггера 23 открывает элемент И 39. Если в результате анализа все процессы в системе могут быть завершены, то все регистры блоков 1.1 - 1.ш регистров установятся в нулевое состояние. Следовательно, на выходе элемента И 30 формируется низкий потенциал и элемент И 39 остается закрытым. Триггер 21 остается в нулевом состоянии, С выхода 66 устройства сигнал тупика не вьдается.В противном случае триггер 21 устанавливается в единичное состояние и с выхода 66 устройства выдается сигнал обнаружения тупиковой ситуации в вычислительной системе.Формула изобретенияУстройство для контроля распределения ресурсов, содержащее первый и второй блоки регистров, первый и второй распределители импульсов,первый и второй управляющие мультиплексоры, первый и второй информационные мультиплексоры, первую схему сравнения, первый и второй триггеры управления, триггер совпадения,триггер анализа, триггер тупика, первый, второй и третий блоки элементов И, первый, второй, третий, четвертый, пятый, шестой и седьмой элементы И, первый элемент ИЛИ и первый элемент ИЛИ-НЕ, причем информационные выходы первого блока регистров соединены с информационными входами первого управляющего мультиплексора и первой группой информационных входов первого информационного мультиплексора, группа выходов которого соединена с первой группой информационных входов первой схемы сравнения и с группой инверсных входов первого элемента И, информационные выходы второ о оло.ка регистров соединены с информационными входами второго управляющегомультиплексора и первой группой информационных входов второго информационного мультиплексора, выход равенства первой схемы сравнения соединенс единичным входом триггера совпадения, инверсный выход которого соеди О нен с первым входом второго элемента И, входы кодов номеров процессоввладеющих ресурсами устройства соединены с первой группой входов первого блока элементов И, входы кодов но меров процессов, запрашивающих ресурсы устройства, соединены с первойгруппой входов второго блока элементов И, выходы первого блока элементов И соединены с информационными 20 входами первого блока регистров,выходы второго блока элементов И соединены с информационными входамивторого блока регистров, выход третьего блока элементов И соединен спервым входом начальной установкипервого блока регистров, выход второго управляющего мультиплексора соединен с вторым входом начальной установки первого блока регистров, 30 первый выход первого управляющегомультиплексора соединен с входом начальной установки второго блока регистров, вход пуска устройства соединен с первым входом первого элемента 35 ИЛИ и с нулевыми входами триггеровтупика и анализа, выход которого соединен с первым входом третьего элемента И, выход второго элемента Исоединен с единичным входом первого 40 триггера управления и первой группой входов третьего блока элементов И, первые ш выходов первогораспределителя импульсов (где ш -число типов ресурсов в системе) сое динен с второй группой входов третьего блока элементов И, с соответствующими управляющими входами первогоинформационного мультиплексора,(в+1)-ый выход первого распределите ля импульсов соединен с первымивходами четвертого и пятого элементов И, выход которого соединен с единичным входом триггера анализа,прямой выход первого элемента И соединен с вторым входом первого элемента ИЛИ, выход шестого элемента Исоединен с синхровходом первого распределителя импульсов и нулевым вхо