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

 

Изобретение относится к области вычислительной техники и может быть использовано в современных высокопроизводительных вычислительных системах . Целью изобретения является повышение быстродействия устройства и расширение области его применения. Устройство содержит; блоки регистров, блок синхронизации, распределители импульсов, мультиплексоры, схему сравнения, триггеры, группы блоков элементов И, элементы И, ИЛИ, ИЛИ- ВЕ. Устройство решает задачу распределения ресурсов между процессами и анализа тупиковых ситуаций. 1 ил.

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

WUNVHCI

РЕСПУБЛИК.„SU„„! 2 А (я) G 06 F 11/00

E опиолник изоьрятяния !, фч;. ! „

«»1 :ь" /

) н авто снов сеид»те»стим

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И 07НРЬПЪЙ (21) 3785594/24-24 (22) 27.08.84 (46) 28,02.86,Бюл. 9 8 (72) С.Н. Ткаченко, Г.Н.Тимонькин, В.С»Харченко и В,В.Герасименко (53) 681.3(088.8) (56) International journal of system

science. 1979, v 10, У 5, р, 477-483.

Авторское свидетельство СССР

У 1015384, кл. С 06 F 11/00, С 06«F 9!00, 1983. (54) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ (57) Изобретение относится к области вычислительной техники и может ьыть использовано в современных высокопроизводительных вычислительных системах. Целью изобретения является повышение быстродействия устройства . и расширение области его применения.

Устройство содержит блоки регистров, блок синхронизации, распределители импульсов, мультиплексоры, схему сравнения, триггеры, группы блоков элементов И, элементы И, ИЛИ, ИЛИНЕ. Устройство решает задачу распределения ресурсов между процессами и анализа тупиковых ситуаций. 1 ил.

1 1

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

Цель изобретения — повышение быстродействия устройства и расширение области его применения.

На чертеже приведена блок-схема предлагаемого устройства.

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

1 регистров, второй 2. 1-(и +1)-й 2 h блоки регистров группы 2 блоков регистров, блок 3 синхронизации, первый 4, второй 5 и третий 6 распредепители импульсов, первый управляю щий мультиплексор 7, второй 8ь1(11+1) -й 8. h управляющие мультиппексоры группы 8 управляющих мультиплексоров, первый 9 и второй 10 мультиплексоры информации, схему 11 сравнения, первый триггер 12 управления, триггер 13 совпадения, триггер 14 тупика, второй триггер 15 управления, триггер 16 анализа, четвертый 17 и пятый 18 триггеры управления, первую группу блоков 19 элементов И, вторую 20, 1-(h+f)-й 20 .11 группу блоков элементов И, блок 21 элементов

И, восьмой 22, третий 23, одиннадцатый 24, первый 25, второй 26,. mecтой 27, четвертый 28, пятый 29, десятый 30, двенадцатый 31, девятый 32, тринадцатый 33 и седьмой 34 элементы

И, пятый 35 и первый 36 элементы ИЛИ, элемент ИЛИ-НЕ 37, четвертый 38, второй 39 и третий 40 элементы ИЛИ, элемент НЕ 41, информационный вход

42 устройства, вход 43 "Пуск" устройства и выход 44 устройства.

Блок. 1 регистров предназначен для приема, хранения и выдачи кодов номеров процессов, которые владеют ре урсами, а блок 2.i регистров— для приема, хранения и выдачи кодов номеров процессов, которые запрашивают ресурсы.

Блок 3 синхронизации предназначен для синхронизации работы элементов устройства.

Распределитель 4 (6,5) импульсов предназначен для формирования на своих выходах последовательности из

h (1п,h) импульсов, распределенных во времени.

Управляющий мультиплексор 7 предназначен для формирования сигналов управления в зависимости от информации, которая поступает на его вход.

215112 2

Управляющий мультиплексор 8.i предназначен для формирования сигнала управления в зависимости от информации, поступающей на его вход.

Мультиплексор 9 предназначен для формирования на своих выходах одного из совокупности кодов, которые поступают на его входы 45. 1-45.6., в зависимости от группы управляющих

1О сигналов °

Мультиплексор 10 предназначен для формирования на выходной шине одного из кодов, которые поступают на его входы (46. 1-46. гп,. 47. 1-4?.61), в зависимости от групп управляющих сигналов.

Триггеры 12,17 и 18 управления предназначены для управления работой распределителей 4,6 и 5 импульсов соответственно.

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

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

Триггер 16 анализа предназначен для формирования сигнала окончания анализа.

Группа 19.1-19.1 блоков элементов

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

Группа 20. 1-20.Й блоков элементов.И предназначены для одновременной передачи информации о кодах номеров процессов, запрашивающих ресурсы, с входа устройства в регистры блоков 2. 1-2. h регистров.

Элементы 21. 1-21.h предназначены о для формирования сигналов установки в ноль регистров блока 1 регистров.

Элементы И 22,23,30,31,32,33 и 34 предназначены для синхронизации работы элементов устройства.

Элемент И 23 предназначен для формирования сигнала установки в нулевое состояние триггера 15 управления. з 12!5! 12 4

Элемент И 25 предназначен для фор- мации через группы блоков элементов мирования сигнала разрешения выбора И 19 и 20 в блок регистров и групследующего кода номера процесса, вла- пу 2 блоков регистров ° Этим же сиг.— деющего каким-либо ресурсом системы. налом управляющий мультиплексор 7

Элемент И 26 предназнн-.ен для фор- и группа 8 управляющих мультиплексомирования сигнала установки в единич- ров закрыты, запрещая тем самым взаное состояние триггера 14 тупика. имную установку в нулевое состояние

Элемент И 27 предназначен для регистров блока 1 и группы 2 блоков формирования сигнала, указывающего регистров соответственно. на то, что при анализе были удаления !О По сигналу пуска (начало анализа) поступающему на вход 43 устройства, процессов.

Элемент И 28 предназначен для фор- разрешается формирование управляющих мирования сигнала разрешения нового последовательностей импульсов на выцикла анализа. ходах блока 3 синхронизации, блокиЭлемент И 29 предназначен для фор- 5 руется прием информации в регистры мирования сигнала установки в единич- блока 1 и группы 2 б гр ппы локов регистров ное состояние триггера 16 анализа. и разрешается перепись ф репись информации вЧ

Элементы ИЛИ 35 и 36 предназначены мультиплексор 7 и группу 8 мульти- для формирования сигнала разрешения плексоров из соответствующих, блоков первого и последующих выборок кодов регистров. Если i-й.регистр блока 1 номеров процессов, владеющих ресурса- содержит нулевой код, то на выходе . ми, а также установки в ноль распреде- i-го разряда группы выходов мультилителей 5 и 6 имп льсов плексора 7 вырабатывается единичный

Элемент ипи-НЕ 37 е

37 предназначен сигнал, являющийся сигналом установдля формирования сигнала, управляю- 2 ки в ноль всех регистров блока 2. щего работой элемента И 25. группы 2 блоков регистров. Кроме

Элементы ИЛИ 38 и 40 предназначе- того, единичный сигнал рормируется ны для формирования сигналов разреше- на выходе мультиплекс а 8 ор .1, для ния выбора кодов номеров процессов, которого все регистры соответствующего блока 2.j группы 2 блоков реЭлемент ИЛИ 39 предназначен для гистров хранят нулевые коды. формирования сигнала установки в ноль Этот сигнал является сигналом распределителя 6 импульсов и тригге- установки в ноль ноль j-го регистра блока 1 регистров. Физическая сущность

Элемент НЕ 41 предназначен для этих операций состоит в удалении из рассмотрения процессов, синхронизации работы распределителя З5 дальнейшего рассм

4 импульсов, мультиплексора 9 и рас- которые заведомо могут быть завершепределителей 5 и 6 импульсов а так-. ны и вследствие

У этого не приведут же мультиплексора 10.

Г к тупику. Далее производится переход руппа 42 информационных входов к выявлению процессов, которые являпредназначена для приема кодов номе- 40 ются только вла ел о владельцами некоторых ров процессов, владеющих ресурсами ресурсов, а сами дополнительно нисистемы и запрашивающих .их. какие другие ресурсы не запрашивают.

Вход 43 пуска предназначен для по- Если некоторый процесс является толь дачи сигнала, осуществляющего нача- ко владельцем ресурса, то его номер ло работы предлагаемого устройства. 45 не должен быть записан ни в одном из регистров группы 2 блоков регисВыход 44 устройства предназначен ров. На проверке этого факта основыдля выдачи сигнала — признака тупи- вывается выявление процессов, котоковой ситуации в вычислительной сис- . рые только владеют ресурсами. теме.

S0 По сигналу начала анализа на вхоУстройство работает следующим де 43 устройства через элемент образом. ИЛИ 36 открывается элемент И 22, имВ исходном состоянии все тригге- пульс с первого выхода блока 3 синры находятся в нулевом состоянии.

Входы начальной установки на фигу- 5 в единичное состоян е ояние, сигнал с едирах условно не показаны. Единичный ничного выхода к ода которого открывает сигнал с четвертого выхода блока 3 .элемент И 23 Им пульс с третьего высинхронизации разрешает прием инфор- хода блока 3 синхронизации через от1215112 крытый элемент И 23 проходит на счетный вход распределителя 4 импульсов, сигнал с первого выхода которого разрешает через мультиплексор 9 подключение выходов первого регистра блока 1 регистров к первой группе входов схемы 11 сравнения. По сигналу с выхода элемента И 23 триггер 12 устанавливается в нулевое состояние и блокирует подачу импульсов на вход распределителя 4.

Если код процесса в первом регистре блока 1 регистров оказался нулевым, то элемент И 25 вырабатывает сигнал, инициирующий переход к исследованию содержимого следующего регистра в блоке 1 регистров. В противном случае нулевой сигнал с выхода элемента И 25 инвертируется элементом НЕ 41 и через элементы ИЛИ 38 и

40 открывает элементы И 30 и 33 соответственно. Импульсом с второго выхода блока 3 синхронизации через открытый элемент И 30 триггер 17 уста25 навливается в единичное состояние и открывает элемент И 32. Импульсом с третьего выхода блока 3 синхронизации через открытый элемент И 33 триггер 18 устанавливается в единичное

ЗО состояние и открывает элемент И 34.

Очередные импульсы с первого и второго выходов блока 3 синхронизации через открытые элементы И 32 и 34 соответственно поступают-.на счетные входы распределителей б и 5 импульсов. IIo сигналу с выхода элемента

И 34 триггер 18 устанавливается в нулевое состояние и блокирует подачу тактовых импульсов на вход распределителя 5 импульсов, На первых вы4О ходах распределителей 6 и 5 импульсов появляются сигналы, которые поступают на входы мультиплексора.10, обеспечивая подключение через элементы выходов первого регистра блока

2. 1 группы 2 блоков регистров к второй группе входов схемы 11 сравнения.

Если сравнения кодов не происходит, то далее работает распределитель 6.

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

®+1) -м выходе распределителя

6 импульсов вырабатывается сиг-. нал, инициирующий переход к анализу запросов очередного ресурса, который через элементы ИЛИ 39 и 40 открывает элементы И 31 и 33. Очередным импульсом с третьего выхода блока 3 синхронизации через открытый элемент

И 31 устанавливаются в ноль триггер

17 и распределитель 6 импульсов, а также через открытый элемент И 33 триггер 18 устанавливается в единичное состояние и открывает элемент

И 34. Очередной импульс с второго вы хода блока 3 синхронизации через открытый элемент И 34 поступает на вход распределителя 5 импульсов, на очередном выходе которого формируется импульс, который через первую группу управляющих входов поступает на мультиплексор 10. Одновременно но сигналу с выхода элемента И 34 триггег 18 устанавливается в нулевое состояние, а также через элемент

ИЛИ 38 и через открытый импульсом с второго выхода блока 3 синхронизации элемент И 30 он поступает на единичный вход триггера 17, который устанавливается в единичное состояние и открывает элемент И 32.

При поступлении импульсов с первого выхода блока 3 синхронизации возобновляет свою работу распределитель 6 импульсов, который совместно с распределителем 5 импульсов управляет выборкой запросов уже к следующему ресурсу, Если во время последовательного сравнения с кодами из регистров группы 2 блоков регистров запросов происходит хотя бы одно совпадение, т.е. исследуемый процесс не только владеет ресурсами, но и запрашивает их, то срабатывает триггер 13 и устанавливается в единичное состояние, По этому сигналу производится выбор содержимого очередного регистра блока 1 регистров, а также установка в ноль распределителей 5 и

6 импульсов. Если же в результате анализа всех просителей для выбранного владельца совпадений не произошло (исследуемый процесс не запрашивает ресурсы), т.е. триггер 13 находится в нулевом состоянии и

1215112 присУтствует сигнал с последнего В противном случае триггер 14 выхода распределителя 5 имп ля 5 импульсов, устанавливается в единичное состоято срабатывает элемент И 27 ент И 27, которыи ние и с выхода 44 выдается сигнал . станавливает т игге р р 15 в единичное обнаружения тупиковой ситуации в вы- состояние. О н д овременно сигналом с

5 числительной системе. выхода элемента И 27 открывается элемент И 21 блока, соответствующий ф ормула изобретения исследуемому процессу, и своим выходом подключается к первой гр ппе

Р руппе 10 устройство для контроля распредеуправляющих входов блока 1 регист- ления ресурсов, содержащее. первый и ров, устанавливая тем самым еги амым регистр, второй блоки регистров, первый и в котором хранится код исследуемого второй распределители импульсов, .процес"а, в нулевое состояние. Через первый и второй управляющие мультимультиплексор 7 осуществляется кор- 1 е соры, перв и второй мультирекция содержимого соответствую его ующ го плексоры информации, схему сравнения, блока группы 2 блоков регистров. первый и второй триггеры управления, Аналогично описанному анализ оу ализ про- триггер совпадения, триггер тупика, должается до окончания исследования триггер анализа, первую и вторую содержимого последнего регистра бло- группы блоков ем

20 оков элементов И, блок злека 1 регистров. Сигнал с выхода рас- ментов И, семь элементов И, первый пределителя 4 импульсов поступает элемент ИЛИ, элемент ИЛИ-НЕ, причем на элементы И 28 и 29. Если в дан-:h групп выходов е б групп выходов первого блока ре- ном цикле анализа были удаления про- гистров (где h — число ресурсов в цессов, то сигнало с единичного вы- 2 системе) соединены с группами инхода триггера 15 открывается элемент формационных входов первого управИ 28 сигнал с ко которого устанавливает ляющего мультиплексора и первого в ноль распределитель 4 импульсов, мультиплексора информации, групчерез элемент ИЛИ 35 распределитель па выходов которого соединена с пер5 импульсов, через элементы ИПИ 35 вой группой входов схемы сравнения и группой инверсных входов первого пульсов, а также через элементы ИЛИ элемента И,1т1 групп выходов второго

35 и Зб открывает элемент И 22. Им- блока регистров ( лока регистров (где rö — число едипульсом с первого выхода блока 3 син- ниц данного типа ресурса) соединехронизации триггер 12 устанавливает- ны с группами информационных входов ся в единичное состояние и ин и— яние и иниции- второго управляющего мультиплексора рует тем самым начало нового цикла и с первои по — ю группами инанализа. формационных входов второго мультиЕсли оказывается что в о что в очередном плексора информации, группа выходов цикле анализа удалений процессов, которого соединена с второй группой которые могут заве шитьс н 40 р т ся, не бьло, входов схемы сравнения, выход котото срабатывает элемент И 29, сигнал рой соединен с единично< входом с которого устанавливает триггер 16 в единичное состояние. Сигнал окон- мационных входов блоков элементов чания анализа с выхода триггера 16 И первой и второй групп образуют информационный вход устройства, групсинхрониза ии. К оме р ц и. Кроме того, сигнал пы выходов блоков элементов И первой с выхода триггера 16 является разре- и второй групп соединены соответшающим сигналом для элемента И 26. ственно с группами информационных

Если в результате анализа все входов первого и второго блоков репроцессы в системе могут быть реаль- гистров, группа выходов блока элено завершены, то все регистры блока ментов И соединена с первой группой

1 регистров устанавливаются в р У ливаются в ну- входов сброса первого блока регистлевое состояние. Сле ова е

Сл довательно. на ров, вход началвной установки котовыходе управляющего мультиплексора сигнал отсутствует и элемент 26 55 равляющего мульт равляющего мультиплексора, вход не сраб атывает. Т игге 1 4 риггер 14 остается . сброса второго блока регистров соев нулевом состоянии. С выхо а и. С выхода 44 динен с первым выходом первого управустройства сигнал тупика не выдается ляющего мультипле ксора, второи выход

1215112

10 которого соединен с первым входом второго элемента И, вход пуска устройства соединен с первым входом первого элемента ИЛИ, нулевыми входами триггера. тупика и триггера анализа, единичный выход которого соединен с вторым входом второго элемента И, вых од ко торо ro соединен с единичным входом триггера тупика, единичный выход которого является выходом устройства, единичный выход первого триггера управления соединен с первым входом третьего элемента И, выход которого соединен с нулевыми входами

15 первого -триггера управления, тригге-: ра совпадения и счетным входом первого распределителя импульсов, группа И. выходов которого соединена с группой входов элемента И-НЕ, груп20 пой управляющих входов первого мультиплексора информации и первой группой входов блока элементов И, (11+1)-й выход первого распределителя импульсов соединен с первыми входами четвертого и пятого элементов

И, а вход сброса — с выходом четвертого элемента И, выход пятого элемен та И вЂ” с единичным входом триггера анализа, выход элемента И-НŠ— с инверсным входом первого элемента И, выход которого .соединен с вторым входом первого элемента ИЛИ, нулевой выход триггера совпадения соединен с первым входом шестого элемента И, выход которого соединен с единичным Ç5 входом второго триггера управления и второй группой входов блока элементов И, выход седьмого элемента И соединен со счетным входом второго распределителя импульсов, группа 40 выходов которого соединена с первой группой управляющих входов второго мультиплексора информации, а (И+1)-й выход — с вторым входом шестого элемента И, единичный и нулевой 45 выходы второго триггера управления соединены соответственно с вторыми входами четвертого и пятого элементов И, о т л и ч а ю щ е е с я тем, что, с целью повышения быстро- 50 действия и расширения области применения устройства, в него введены третий — (И+1)-й блоки регистров; блок синхронизации, третий распределитель импульсов, третий — (И +1) -й 55 управляющие мультиплексоры, четвертый и пятый триггеры управления, третья — (h+1)-я группа блоков элементов И, шесть элементов И, четыре элемента ИЛИ, элемент HE причем YA груйп выходов каждого из блоков регистров с третьего по (17+1)-й соединены соответственно с фИ+1)-й по.h< — ю группами информационных входов второго мультиплексора информации и с группами информационных входов соответствующих управляющих мультиплексоров с третьего по (И+1) -й выходы которых соединены с группой входов начальной установки первого блока. регистров, первый выход блока синхронизации соединен с первыми входами восьмого и девятого элементов И, выход девятого элемента И соединен со счетным входом третьего распределителя импульсов, группа.1т1 выходов которого соединена с второй группой управляющих входов второго мультиплексора информации, (и+1)-й выход — с первыми входами второго и третьего элементов ИЛИ, второй выход блока синхронизации — с первыми входами седьмого и десятого элементов

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

И, выход которого соединен с нулевым входом пятого триггера управления и первым входом четвертого элемента ИЛИ, четвертый выход блока синхронизации соединен с управляющими входами с первого по (И +1)-й управляющих мультиплексоров и вторыми входами блоков элементов И с первой по (И+1)-ю групп, группы выходов с третьего по (h+1)-ю групп блоков элементов И соединены с группами информационных входов соответствующих блоков регистров с третьего по (И+1)-й, входы сброса которых соединены с третьего по (И+1)-й выходами первого управляющего мультиплексора, выход первого элемента И через элемент НЕ соединен с вторыми входами третьего и четвертого элементов ИЛИ, выход которого соединен с

1215112

Со с тави тель И. Хазов а

Техред О.Неце. Корректор А.Tacrco

Редактор А.Лежнина

Заказ 907/56 Тираж 673 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал IIIIII "Патент", г.Ужгород, ул.Проектная, 4 вторым входом десятого элемента И, первый выход группы выходов первого распределителя импульсов соединен с вторым входом одиннадцатого элемента

И, выход которого соединен с нулевым входом второго триггера управления, первые группы входов с третьей по

@+1)-ю групп блоков элементов И соединены с информационным входом, устройства, единичный выход триггера совпадения соединен с первым входом пятого элемента ИЛИ, выход шестого элемента И вЂ” с вторым входом пятого элемента ИЛИ, выход которого соединен с третьим входом первого элемента ИЛИ, вторым входом второго элемента ИЛИ и входом сброса второго распределителя импульсов, выход второго элемента ИЛИ соединен с вторым выходом двенадцатого элемента И, выход которого соединен с нулевым входом четвертого триггера управления и входом сброса третьего распределителя импульсов, выход третьего элемента ИЛИ соединен с вторым входом тринадцатого элемента И, выход четвер1п того элемента И вЂ” с третьим входом пятого элемента ИЛИ, выход триггера анализа соединен с входом "Стоп" блока синхронизации, вход Пуск" которого соединен с входом пуска устройства, выход первого элемента ИЛИ соединен с вторым входом восьмого элемента И, выход которого соединен с единичным входом первого триггера управления.