Устройство диспетчеризации центрального узла вычислительной сети

 

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

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

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

РЕСПУБЛИН

„„SU„„1310 20 (so 4 С 06 Р 9/46

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

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4014348/24-24 (22) 23.01,86 (46) 15.05.87 . Бюл. 11 - 18 (71) Куйбышевский политехнический .институт им. В,В.Куйбышева (72) А,НЛаляров (53) 681.325 (088,8) (56) Якубайтис 3.А . Информационновычислительные сети. — М .: Финансы и статистика, 1984, стр, 232, Авторское свидетельство СССР

N - 1126964, кл, С.06 F 9/46, 1983. (54) УСТРОЙСТВО ДИСПЕТЧЕРИЗАЦИИ

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

СЕТИ.: (57) Изобретение относится к вычислительной технике и может быть использовано в информационно-вычислительных сетях для центрального упорядочи.вания доступов к распределенным информационным фондам, Цель.изобрете.ния — расширение области применения устройства эа счет распределения запросов в зависимости от их типов.

Устройство содержит группы из N элементов ИЛИ и ИЛИ-НЕ (N — наибольшее число запросов в очереди), коммутатор, N-разрядные регистры записи запросов и регистр типа запросов группы, группу из Н элементов И, группу иэ N формирователей импульса, счетчик, формирователь импульса, элемент

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

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

1 310820

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

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

Из всех запросов на использование информационного фонда в сети выделяются два типа ° К первому типу относятся запросы, не требующие изменения содержания фонда (запросы типа чтения). Ко второму типу относятся запросы, которые в результате использования фонда изменяют его содержание, обновляют фонд (запросы типа обновленияия), В случае органиэации дублированного в различных узлах сети фонда запросы — обновления должны выполняться во всех узлах сети, где хранятся дублированные данные. Дублирование в узлах сети осуществляется для приближения данных непосредственно к пользователю и для исключения необходимости осуществлять запросы типа чтения в удаленных узлах, Необходимость обновления дублированного фонда во всех узлах вытекает из требования непротиворечивости данных в узлах (целостности распределенного информационного фонда).

Конфликтующими являются запросы, выполнение которых в произвольном порядке в узлах сети может привести к потере непротиворечивости данных или к использованию противоречивых данных. Конфликтующими являются пары запросов: запрос типа чтения — запрос типа обновления или запрос типа обновления — запрос типа обновления, Пара запросов: запрос типа чтения запрос типа чтения не является конфликтующей, Конфликтующие запросы требуют общего упорядочивания на уровне всей сети для сохранения единого порядка выполнения во всех узлах сети.

Пусть в сети имеются 2 узла с дублированным фондом. В сети возникло два запроса А и В на обновление информационного фонда. Если в первом узле .запросы выполняются в порядке

А-В, а во втором — в порядке В-А, то в итоге единый информационный фонд в различных узлах будет иметь различ-. ное содержание. Имеет место потеря целостности дублированного информационного фонда, Если в сети возникли запрос А на обновление, а потом запрос С на чтение, то изменение порядка выполнения в каком-либо узле является недопустимым, поскольку будут считаны устаревшие данные. При поступлении запросов в сеть в порядке С-А изменение этого порядка выполнения запросов может быть также недопустимым (особенно если имеется одновременно с С поступивший второй запрос на чтение. тогда один запрос считывает новые данные1 другой — устаревшие). Запросы на чтение при отсутствии запросов на обновление между собой могут выполняться в любом порядке, так как рто не ведет к противоречивым результатам.

Для конфликтующих запросов должна

25 быть строгая и единая упорядочен. н 0с ть выполнения запр о сов, с облюда емая во всех узлах сети, Группа последовательно поступающих в центральное устройство запросов на чтение может выполняться параллельно в различных узлах сети, если отсуствуют требования обновления в сети. Порядок выполнения последовательно возникающих запросов на чтение в определенном узле сети определяется очередью ипри35 нятой дисциплиной обслуживания в этом узле.

Если в сеть поступили запросы на чтение (в первый узел Q, во второй в третий Дз) то они могут выг ° полняться параллельно, если только в сети не производится обновления информационного фонда. При выполнении обновления в сети запросы на чтение (и другие обновления) должны быть запрещены до момента окончания этого обновления, так как запросы на чтение и обновление конфликтуют ° Поступление следующего запроса на чтение после Ц», Цг, э также может выпол— няться без строгих требований к норядку по отношению к предыдущим запросам, Однако после поступления запроса на обновление он должен ожи55 дать завершения всех других запросов в сети..

Данное устройство выполняет централизованным образом одну из функций управления прикладными процессами

1310820 (в ерхнего уровня в заимодействия систем) . Этот уровень обеспечивается функциями и средствами поддержки на физическом, канальном, транспортном, сеансовом и представительном уровнях взаимодействия систем. Функции и средства этих нижних уровней выходят за рамки предлагаемого технического решения.

На чертеже приведена схема устрой- !О ства.

Устройство содержит (К-1) регистров 1 длиной N разрядов, коммутатор

2, группу из N К-входовых элементов

ИЛИ 3, группу иэ N элементов ИЛИ-НЕ !5

4, регистр 5 типа запросов длиной N разрядов, счетчик 6 опроса, дешифратор 7 опроса адреса строки, элемент

НЕ 8, двухвходовые элементы И 9 и 10, группу из элементов И 11, группу из 20 формирователей 12 импульсов, элемент

ИЛИ 13, формирователь 14 импульсов.

На входы 15 поступает код запроса длиной (К+1) разрядов. Он включает коды номера узла инициации, номера запроса в узле и разряд типа запроса (запрос с обновлением фонда имеет в этом разряде "0", а запрос без об— новления 1) .

На выходы 16 устройсгва поступает код запроса, получившего доступ к ресурсам. Разрешение на доступ по запросу с номером, содержащимся в коде запроса, пересылается затем в узел сети, инициировавший этот запрос. 35

Номер узла определяется по коду запроса.

На вход 17 устройства поступает сигнал завершения доступа и исполь- 40 зования общих ресурсов с одного из узлов сети, B исходном состоянии регистры 1 и 5 обнулены, счетчик 6 имеет состояние, определяющее адрес первого разряда 5-1 в регистре 5. На выходе

20-1 элемента ИЛИ 3-1 группы присутствует сигнал низкого уровня, на выходе 18-1 первого элемента ИЛИ-НЕ

4-1 группы — cHrHaa sbtcoKoro ypoaHa, g0

Поэтому на выходах 18 всех элементов

ИЛИ-НЕ 4 группы, кроме первого, устанавливаются низкие уровни. Только первые регистры 1 и .5 группы подготовлены для записи кода запроса. На выходе всех элементов И 11 группы присутствует нулевой сигнал, поскольку на выходах элементов ИЛИ 3 группы — нулевые сигналы.

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

Первый запрос поступает параллельным кодом на входы 15 и записывается в первый разряд регистров 1 и 5 соответственно, т.е. в первую строку, поскольку только на выходе элемента

ИЛИ-НЕ 4-1 группы присутствует разрешающий сигнал. После записи первого запроса на выходе первого элемента ИЛИ 3-! группы появляется единичный сигнал, на выходе элемента HE

4-1 группы — нулевой сигнал, на выходе, второго элемента ИЛИ 3-2 группы нулевой сигнал, на выходе второго элемента ИЛИ-НЕ 4-2 группы — единичный сигнал. Он разрешает последующую за поступившим вторым запросом запись кода этого запроса во вторые разряды регистров 1 и 5 группы, т,е, подготавливает запись запроса во вторую строку памяти. Одновременно он поступает на остальные элементы ИЛИНЕ 4 группы. На всех элементах ИЛИНЕ 4 группы, кроме второго, будут присуствовать нулевые сигналы, запрещающие запись в соответствующие разряды регистров 1 и 5.

После прихода второго запроса он записывается во вторую строку памяти.

Заполнение к одами запросов остальных разрядов происходит аналогично, I

После записи запроса в первую строку памяти появляется сигнал на входе 20-1 первого элемента И 11 — 1 группы. При отсутствии сигнала завер- шения на входе 17 открывается первый элемент И 11 — 1 группы, а первый фор мирователь 12-1 группы выдает разрешающий сигнал на выход 19-1 „который поступает на управляющие входы коммутатора 2 для разрешения передачи кода первого запроса в очереди на выходы 16 устройства. Таким образом первый запрос в очереди получает доступ к общему информационному ресурсу.

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

Если первый запрос включает только операции считывания данных, то единичный сигнал с выхода первого разряда регистра 5 при отсутствии сигнала завершения доступа на входы 17 разрешает прохождение через первый эле13 0820 мент И 11 — 1 группы единичного сигнала на первый формирователь 12-1 группы и с него на элемент ИЛИ 13, Состояние счетчика 6 увеличивается на единицу. В этом случае с выхода 23 5 дешифратора 7 на второй элемент И

11-2 группы поступает разрешающий сигнал, а первый элемент И 11 — 1 группы закрывается.

Если в i-ю ячейку (1. 1) записывается запрос, то на входе 20 i-го элемента И 11 группы появляется единичный сигнал . Элемент И 11-i группы открывается, если отсутствует сигнал завершения доступа на входе 17 устройствтв а, если з апр ос не содержит обновления и все запросы до i-го не включают обновления фонда.

В случае появления единичного сигнала с элемента И 11-i группы (1) соответствующий формирователь 12-i разрешает передачу кода i-го запроса с коммутатора 2 на выходы 16 устройства. Кроме того, состояние счетчика

6 в этом случае увеличивается на еди— ницу и подготовлен анализ следующей (i+1)-й заявки íà (i+1) — м элементе

И 11 группы, При завершении доступа по какому 30 либо запросу, которому ранее было выдано разрешение, сигнал завершения поступает на вход 17 устройства, Содержимое регистров 1 и 5 группы сдвигается на один разряд вправо, Если записано i запросов, то после сдвига для записи следующего запроса подгоговлены разряды регистров, соответ— ствующие не (i+1)-й, à i — и строке, В этом случае присутствует единичный сигнал на выходе элемента ИЛИ-НЕ 4-i группы, Сигнал с выхода элемента НЕ 8 запрещает срабатывание элементов И 11 группы. Сигнал с входа 17 также умень- 5 шает состояние счетчика 6 на единицу, однако поступает на счетчик 6 с задержкой> определяемой формирователем

14, Она должна быть достаточной для передачи сигнала с одного из формирователей 12 группы через элемент

ИЛИ 13 и для увеличения состояния счетчика 6 на единицу, если к моменту прихода сигнала на вход 17 и к моменту закрывания элементов И 11 группы один из этих элементов И 11 группы уже сработал и инициировал работу соответствующего формирователя 12 группы, Уменьшение состояния счетчика 6 происходит, если на элемент И 9 с дешифратора 7 поступает разрешающий сигнал. Дешифратор 7 выдает этот сигнал, если счетчик 6 не находится в состоянии, соответствующем адресу первой строки, Таким образом, состояние счетчика 6, определяющего адрес первой строки, не уменьшается.

После периода времени, достаточного для сдвига содержимого строк, для возможного срабатывания одного из формирователей 12 группы и увели-. чения состояния счетчика 6 по входу

21 и для возможного уменьшения состояния счетчика 6 по сигналу 22 с формирователя 14, сигнал 17 прекращается, на элементы И 11 группы с элемента НЕ 8 поступает разрешающий сигнал, 1

Таким образом, при появлении единичного сигнала на выходе элемента

И 9 формирователь 14 задерживает сигнал на время, достаточное для сдвига содержимого регистров и срабатывания элементов 12, 10, 13 и 6 устройства, а затем уменьшает состояние счетчика 6 до момента завершения сигнала с входа 17 о завершении доступа.

После этого предложен опрос разрядов регистра 5, если все предыдущие запросы, записанные в строках памяти, не содержат обновления фондов и если в очереди имеется очередной запрос, который также не содержит обновлений °

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

Устройство диспетчеризации центрального узла вычислительной сети, содержащее группу из К регистров (К вЂ” длина кода запроса), группу из

N элементов ИЛИ-НЕ (N — длина очереди запросов), группу из N элементов

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

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

1, (К-1)) регистра соединен с j-м входом i-го элемента ИЛИ группы и с

j-м входом д-й группы информационных входов коммутатора, группа выходов которого является группой выходов устройства, выход i-ro элемента ИЛИ группы соединен с первым входом i-го элемента ИЛИ-HE группы и с первым входом i-го элемента И группы, выход которого соединен с входом i-ro формирователя импульса группы, первый выход которого соединен с д-м управляющим входом коммутатора, вход использования общих ресурсов устройства соединен с первым входом первого элемента И и с входом элемента HE выход которого соединен с вторыми входами всех элементов И группы, 1-й кодовый вход устройства (y-1 K) соединен с информационными входами всех разрядов 1-го регистра группы, 10820 8 выход первого разряда К-ro регистра соединен с первьм входом второго элемента И, выход которого соединен с первым входом элемента ИЛИ, выход которого соединен с суммирующим входом счетчика, группа выходов которого соединена с группой входов дешифратора, первый выход которого соединен с третьими входами элементов И

f0 группы, второй выход дешифратора соединен с вторым входом первого элемента И, выход которого соединен с входом формирователя импульса, выход которого соединен с вычитающим входом

15 счетчика, выход m-го разряда (m=2, N)

К-го регистра группы соединен с четвертым входом m-го элемента И группы, выход первого формирователя импульса группы соединен с .вторым входом

20 второго элемента И, выход m-го формирователя импульса группы соединен с m-м входом элемента ИЛИ, m-й вход элемента ИЛИ-НЕ группы с m-ro no

N-й соединен с выходом (m-.1)-ro эле25 мента ИЛИ-НЕ группы.

131ОВ20

Составитель М,Сорочан

Редактор И.Дылын Техред Л.олийнык

Корректор А.Тяско

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

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул, Проектная, 4