Устройство для контроля распределения ресурсов Советский патент 1986 года по МПК G06F15/177 

1

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

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

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

Устройство для контроля распределения ресурсов содержит первый блок 1 регистров, второй 2,1-(Я +1)-й 2 h блоки регистров группы 2 блоков регистров, блок 3 синхронизации, первый 4, второй 5 и третий 6 распределители импульсов, первый управляющий мультиплексор 7, второй (И + 1)-й 8;h управляющие мультиплексоры группы 8 управляющих мультиплексоров, первый 9 и второй 10 мультиплексоры информации, схему 11 сравнения, первый триггер 12 управления, триггер 13 совпадения, триггер 14 тупика, второй триггер 15 управления триггер 16 анализа, че|твертый 17 и пятый 18 триггеры управления, первую группу блоков 19 элементов И, вторую 20, 1-(И+1)-й 20.-Ь группу блоков элементов И, блок 21 элементов И, восьмой 22, третий 23, одиннадцатый 24, первый 25, второй 26, шестой 27, четвертый 28, пятый 29, десятый 30, двенадцатый 31, девятый 32, тринадцатый 33 и седьмой 34 элементы И, пятый 35 и первый 36 элементы ИЛИ элемент ИЛИ-НЕ 37, четвертый 38, второй 39 и третий 40 элементы ИЛИ, элемент НЕ 41, информационный вход 42 устройства, вход 43 Пуск устройства и выход 44 устройства.

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

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

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

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

151122 . ,

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

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

Q сигналов.

Мультиплексор 10 предназначен для формирования на выходной шине одного из кодов, которые поступают на его входы (46.1-46.hi, 47.1-47.И,

5 в зависимости от групп управляющих сигналов.

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

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

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

для формирования сигнала тупика.

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

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

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

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

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

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

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

0

0

31

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

Элемент И 26 предназначен для формирования сигнала установки в единичное состояние триггера 14 тупика.

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

Элемент И 28 предназначен для формирования сигнала разретения нового цикла анализа.

Элемент И 29 предназначен для фор- мирования сигнала установки в единичное состояние триггера 16 анализа.

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

Элемент ШТИ-НЕ 37 предназначен дпя формирования сигнала, управляю- щего работой элемента И 25.

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

Элемент ИЛИ 39 предназначен для формирования сигнала установки в ноль распределителя 6 импульсов и триггера 17.

Элемент НЕ 41 предназначен для синхронизации работы распределителя 4 импульсов, мультиплексора 9 и распределителей 5 и 6 импульсов, а также мультиплексора 10.

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

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

Выход 44 устройства предназначен для вьщачи сигнала - признака тупиковой ситуации в вычислительной сиетеме.

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

В исходном состоянии все триггеры находятся в нулевом состоянии. Входы начальной установки на фигурах условно не показаны. Единичный сигнал с четвертого выхода блока 3 синхронизации разрешает прием инфор

Q

n

5

0

0

5

1124

мации через группы блоков элементов И 19 и 20 в блок 1 регистров и группу 2 блоков регистров. Этим же сигналом управляющий мультиплексор 7 и группа 8 управляющих мультиплексоров закрыты, запрещая тем самым взаимную установку в нулевое состояние регистров блока 1 и группы 2 блоков регистров соответственно.

По сигналу пуска (начало анализа); поступающему на вход 43 устройства, разрешается формирование управляющих последовательностей импульсов на выходах блока 3 синхронизации, блокируется прием информации в регистры блока 1 и группы 2 блоков регистров и разрешается перепись информации в : мультиплексор 7 и группу 8 мульти-ii плексоров из соответствующих, блоков регистров. Если i-й регистр блока 1 содержит нулевой код, то на выходе . i-го разряда группы выходов мультиплексора 7 вырабатывается единичный сигнал, являющийся сигналом установки в ноль всех регистров блока 2.1 группы 2 блоков регистров. Кроме того, единичный сигнал 1юрмируется на выходе мультиплексора B.j, для которого все регистры соответствующего блока 2.J группы 2 блоков регистров хранят нулевые коды.

Этот сигнал является сигналом установки в ноль j-ro регистра блока 1 регистров. Физическая сущность зтих операций состоит в удалении из дальнейшего рассмотрения процессов, которые заведомо могут быть завершены и вследствие этого не приведут к тупику. Далее производится переход к выявлению процессов, которые являются только владельцами некоторых ресурсов, а сами дополнительно никакие другие ресурсы не запрашивают. Если некоторый процесс является только владельцем ресурса, то его номер не должен быть записан ни в одном из регистров группы 2 блоков регис- ров. На проверке этого факта основы- вывается выявление процессов, которые только владеют ресурсами.

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

Если код процесса в первом регистре блока 1 регистров оказался нулевым, то элемент И 25 вырабатывает сигнал, инициирующий переход к исследованию содержимого следующего регистра в блоке 1 регистров. В противном счучае нулевой сигнал с выхода элемента И 25 инвертируется элементом НЕ 41 и через элементы ИЛИ 38 и 40 открьюает элементы И 30 и 33 соответственно. Импульсом с второго выхода блока 3 синхронизации через открытый элемент И 30 триггер 17 устанавливается в единичное состояние и открьюает элемент И 32,, Импульсом с третьего выхода блока 3 синхронизации через открытый элемент И 33 триггер 18 устанавливается в единичное состояние и открывает элемент И 34 Очередные импульсы с первого и второго выходов блока 3 синхронизации через открытые элементы И 32 и 34 соответственно поступают-, на счетные входы распределителей 6 и 5 импульсов. По сигналу с выхода элемента И 34 триггер 18 устанавливается в нулевое состояние и блокирует подачу тактовых импульсов на вход распределителя 5 импульсов. На первых выходах распределителей 6 и 5 импульсов появляются сигналы, которые поступают на входы мультиплексора.10, обеспечивая подключение через элементы выходов первого регистра блока 2,1 группы 2 блоков регистров к второй группе входов схемы 11 сравнения Если сравнения кодов не происходит, то далее работает распределитель 6. По каждому очередному импульсу первого блока 3 синхронизации на выходах распределителя последовательно вырабатываются разнесенные во времени сигналы, которые через вторую группу управляюпщх входов управляют работой мультиплексора 10. Мультиплексор 10 осуществляет выбор содержимого очередного регистра блока 2.1 регист0

5

0

5

0

5

0

5

5

ров запросов. Если все запросы к выбранному ресурсу исчерпались, а сравнения кодов не произошло, то на W+l) выходе распределителя 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 находится в нулевом состоянии и

присутствует сигнал с последнего выхода распределителя 5 импульсов, то срабатывает элемент И 27, который устанавливает триггер 15 в единичное состояние. Одновременно сигналом с выхода элемента И 27 открывается элемент И 21 блока, соответствующий исследуемому процессу, и своим выходом подключается к первой группе управляющих входов блока 1 регистров, устанавливая тем самым регистр, в котором хранится код исследуемого процесса, в нулевое состояние. Через мультиплексор 7 осуществляется коррекция содержимого соответствзшзщего блока группы 2 блоков регистров.

Аналогично описанному анализ продолжается до окончания исследования содержимого последнего регистра блока 1 регистров. Сигнал с выхода распределителя 4 импульсов поступает на элементы И 28 и 29. Если в данном цикле анализа были удаления процессов, то сигналом с единичного выхода триггера 15 открьшается элемент И 28, сигнал с которого устанавливае в ноль распределитель 4 импульсов, через элемент ШШ 35 распределитель 5 импульсов, через элементы ИЛИ 35 и 39 и И 31 - распределитель 6 импульсов, а также через элементы ИЛИ 35 и 36 открывает элемент И 22. импульсом с первого выхода блока 3 синхронизации триггер 12 устанавливается в единичное состояние и инициирует тем самым начало нового цикла анализа.

Если оказывается, что в очередном цикле анализа удалений процессов, которые могут завершиться, не было, то срабатывает элемент И 29, сигнал с которого устанавливает триггер 16 в единичное состояние. Сигнал окончания анализа с выхода триггера 16 поступает на вход Стоп блока 3 синхронизации. Кроме того, сигнал с выхода триггера 16 является разрешающим сигналом для элемента И 26.

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

0

5

0

5

0

5

0

5

0

5

В противном случае триггер 14 устанавливается в единичное состояние и с выхода 44 выдается сигнал обнаружения тупиковой ситуации в вы- числительной системе.

Формула изобретения

Устройство для контроля распределения ресурсов, содержащее первый и второй блоки регистров, первый и второй распределители импульсов, первый и второй управляющие мультиплексоры, первый и второй мультиплексоры информации, схему сравнения, первый и второй триггеры управления, триггер совпадения, триггер тупика, триггер анализа, первую и вторую группы блоков элементов И, блок элементов И, семь элементов И, первый элемент ИЩ, элемент ИЛИ-НЕ, причем :h групп выходов первого блока регистров (где h - число рес5Фсов в системе) соединены с группами информационных входов первого управляющего мультиплексора и первого мультиплексора информации, rpjnn- па выходов которого соединена с первой группой входов схемы сравнения и группой инверсных входов первого элемента И, Hi групп выходов Второго блока регистров (где hi - число единиц данного типа ресурса) соединены с группами информационных входов второго управляющего мультиплексора и с первой по hi - ю группами информационных входов второго мультиплексора информации, группа выходов которого соединена с второй группой входов схемы сравнения, выход которой соединен с единичным входом триггера совпадения, группы информационных входов блоков элементов И первой и второй групп образуют информационный вход устройства, группы выходов блоков элементов И первой и второй групп соединены соответ ственно с группами информационных входов первого и второго блоков регистров, группа выходов блока элементов И соединена с первой группой входов сброса первого блока регистров, вход началвной установки которого соединен с выходом второго Управляющего мультиплексора, вход сброса второго блока регистров соединен с первым выходом первого управляющего мультиплексора, второй выход

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

10

15

0

5

5 0 5 0

0

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

вторым входом десятого элемента И, первый выход группы выходов первого распределителя импульсов соединен с jTOpbiM входом одиннадцатого элемента И, выход которого соединен с нулевым входом второго триггера управл.ения, первые группы входов с третьей по +) групп блоков элементов И соединены с информационным входом устройства, единичный выход триггера совпадения соединен с первым входом пятого элемента ИЛИ, выход шестого элемента И - с вторым входом пятого элемента ИЛИ, выход которого соединен с третьим входом первого элемента ИЛИ, вторым входом второго элемента ИЛИ и входом сброса второго распределителя импульсов, выход второго

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

|Ж/7{Д/ Ih

LJ-1 L .J

20.П

2jj

iZu

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

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

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ПИП Патент, г.Ужгород, ул.Проектная, 4

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

Техред о. Неце-Корректор А. Тяско