Устройство для моделирования адаптивных вычислительных систем Советский патент 1988 года по МПК G06N7/06 

Изобретение относится к вычислительной технике и может быть использовано для статистического моделирования широкого класса вычислительных систем, в частности для моделирования мультипрограммных ЭВМ, работающих в режиме разделения времени с многошаговым алгоритмом адаптация, и является усовершенствованием устройства по авт. св. № 1020830.

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

На фиг. 1 представлена блок-схема устройства; на фиг, 2 - функциональная схема блока поиска свободных терминалов-, на фиг. 3 - схема управляемого регистра сдвига; на фиг. 4 - схема блока моделирования очереди на фиг. 5 - схема приоритетного блока; на фиг. 6 - схема блока сравнения; на фиг. 7 - схема блока управления, на фиг. 8 - схема пересчетной схемы.

Устро йство (фиг. 1 ) содержит блок 1 статистич.еской обработки, вкJдачaIoщий в себя счетчики 2-5,блок 6 индикации длины очереди и управ- ляемьш генератор 7 импульсов, генератор 8 случайного потока импульсов, генератор 9 произвольно распределенных случайных чисел, блок 10 поиска свободных терминалов, управляемый регистр 1 сдвига, блок 2 моделирования очереди, блок 13 управления приоритетный блок 14, блок 15 срав- нення, блок 16 измерения времени ответа , включающий в себя накапливающие сумматорь 17 и 18, суммирующий счетчик 19, генератор 20 фиксированного числа имульсов, группу элементов И 21 и злемент 22 задержки, вход 23 блок управления, элементы И 24-27, группу входов 28 устройства .

Блок поиска свободных терминалов (фиг, 2) содержит триггеры 29, первую группу элементов И 30, вторую группу элементов И 31, злемент И-ЫЕ 32, элемент ИЛИ 33; вход 34 запроса, управляющие выходы 35, 36, выход 37, группы входов 38, 39, группы вько- дов 40-43.

Управляемый регистр сдвига (фиг. 3) содержит триггеры 44, первую, вторую и третью группы злемен- тов И 45, 46, 47 соответственно, группу выходов 48, шину 49 сдвига. На фиг. 3 показаны также триггеры 29 блока 10 поиска свободных терминалов и группы выходов 41, 42 зтого блока, являющиеся входами управляемого регистра сдвига.

Блок моделирования очереди (фиг.4) содержит вычитающие счетчики 50, группу блоков элементов И 51, блок 52 элементов И, элемент ИЛИ 53, группы входов 54, управляющий вход 55, выход 56.

Приоритетный блок (фиг.5) содержит суммирующий 57 счетчик длительности интервалов, элементы ИЛИ 58, 59, группы элементов И 60-63, приоритетный регистр 64, управляющие входы 65,

66, вькод 67.

Блок сравнения (фиг. 6) содержит регистр 68, сумматор 69, блоки элементов И 70, 71, элементы И 72, группу элементов И 73, элементы И 74, 75,

76, элемент ИЛИ-НЕ 77, группу элемеН - тов ИЛИ 78, элементы ИЛИ 79-82, группу элементов ШИ 83, триггер 84, элементы 85, 86 и 87 задержки, кольцевой регистр 88 сдвига, группу регистров

89, управляющий генератор 90 заданного числа импульсов, группу элементов И 91, злемент И 92, вход 93, з прав- ляющий вход 94 и группу выходов95. Блок управления (фиг. 7) содержит

первый триггер 96, пересчетную схему 97, выход 98, входы 99 и J00 пересчетной схемы, переключатель lOJ, генератор 102 импульсов, второй триггер 103, второй 04, первый 105 и третий 106 элементы ИЛИ, элемент 107 задержки, вход 08, и выходы 09, ПО пересчетной схемы, выходы 11 и N2 блока.

Пересчетная схема (фиг. 8) содержит вход ПЗ начальной установки, вто- рой элемен™ ИЛИ П4, шифратор 115, регистр 116, группу элементов И 117, элемент 118 задержки, первый элемент ИЛИ 119, первый элемент 118 задержки,

первый .элемент Ш1И 19, первый элемент И 120, первый счетчик 12i, второй счетчик 122, второй элемент И 123.

Для моделирования вьмислительных систем с двухпараметрической адаптацией в блок 15 сравнения через входы 28 вводятся значения нескольких временных порогов (Т,, Т,...Т) качества обслз/ ивания заданий.

Качество обслуживания заданий оценивается средним текущим временем ответа вьгчис.чительной системы Т,, которое определяется за период наблгоде- ния Т. После окончания каждого периода наблюдения производится вычисление текущего времени ответа системы Т-р, сравнение его с заданными временными порогами (Т;,, Т,...), Т, Т ...iTj.. В зависимости от результатов сравнения блок управления вырабатывает сигналы для выбора длительности кванта на очередной период Т , а при достижении граничных значений Т или Т формируются сигналы Отключить терминал (. ) или Подключить терминал ( Т ) , которые поступают в приоритетный блок 4.

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

Моделирование обычньж вычислительных систем обеспечивается путем ввода в блок 15 сравнения нижнего порога эталонного времени ответа Т| макс ) где Тд,д.., - предельное значение времени ответа для моделируемо системы. В этом случае изменение длительности квантов не осуществляется и к системе постоянно подключены все терминалы

Блок i статистической обработки обеспечивает .накопление и частичную обработку статистических данных, характеризующих процесс функционирования моделируемой системы. Счётчики 2 и 3 подсчитывают соответственно суммарное количество заданий, поступающих в систему и принятых на об- служивание. Разность в показаниях этих счетчиков равна числу заданий, которые получили отказ вследствие занятости или блокировки терминалов. Счетчик 5 подсчитывает количество заданий, обработанных в течение одного интервала наблюдения. Длительность этого интервала определяется вр еменем заполнения счетчика 5.При завершении обряботки двух заданий счетчик 5 обнуляется, при этом на его выходе появляется импульс, обеспечивающий включен а в работу блоков 15. 16 и 13. Ре зрсивный счетчик 4 содержит значение текущего количест- вэ заданий, обрабатьтаемых системой в данный момент времени. Блок 6 индикации длины очереди служит для определения вероятностных .характерно

4

тик очереди заданий. Управляемьш генератор 7 и пульсов вырабатывает импульсы с частотой следования F nf, где f - базовая частота, определяющая точность измерения интервалов, времени пребывания заданий в системе. Импульсы поступают в накапливающий сумматор 17, работающий в режиме счетчика, при этом в нем накапливается значение суммарного времени пребывания заданий в системе. Гене- 8 случайного потока импульсов имитирует моменты поступления задан- ний на обработку. Генератор 9 произ- вольнЪ распределенных чисел обеспечивает выработку случайных чисел с перестраиваемым законом распределения. Эти числа характеризуют отрезки времени обслх живания отдельных заданий .

Блок 10 поиска свободных терминалов вьшолняет следующие функции. При наличии хотя бы одного свободного терминала блок 10 выдает сигнал, открывающий элемент И 24. Состояние терминалов (Свободен, Занят) моделируется триггерами 29 (фиг.2), которые последовательно устанавливаются в состояние 1 сигналами с выхода элемента И 24 и в состояние О сигналами с вычитающих счетчиков блока 12. По сигналу с выхода элеме} та И 24 (входная щина 34 блока 10) осуществляется поиск свободного и незаблокированного терминала путем последовательного опроса элементов И 30, 31, При наличии свободного и незаблокированного терминала приоритетным блоком 14 вырабатывается сигнал, открывающий элементы И 27, при этом генератор 9 вырабатывает случайное число, которое записьшается в один из вычитающих счетчиков блока 2.Блок счетчика осуществляется сигналом, поступающим по одному из выходов 43.Блок 10 выдает сигналы управления на уп- равляемьш регистр сдвига. При нали- 4Hii хотя бы одного занятого терминала блок 10 выдает на шину 36 сигнал, открывающий элементы И 25, 26.

Управляемый регистр 11 сдвига обеспечивает последовательное циклическое подключение заданий терминалов на обработку, при этом подключаются только задания занятых терминйлов. Если терминал свободен или заблокирован, то соответствующие триггеры 29 (фиг.3)

находятся в состоянии О и при сдвиге в управляемом регистре сдвига с помощью элементов И 45, 46, 47 пропускаются все разряды, связанные со свободными терминалами, и 1 попадает только в тот разряд, который связан с занятья терминалом. Сигналы с прямых выходов триггеров 44 поступают по выходам 48 в блок 12 и под- ключают на обработку задания соответствующих терминалов с помощью блока 52 элементов И (фиг. 4).

Блок 12 моделирования очереди (фиг,4) состоит из N вычитающих счетчиков 50. Количество счетчиков определяет максимальное число заданий, которые могут одновременно находиться в системе. Блок 12 моделирует процесс обработки заданий в ла- кетном режиме и в режиме разделения времени. Очередные задания в виде случайных двоичных чисел, значения которых соответствуют времени обработки задания, поступают по входным шинам 54 на все группы элементов И 51. Один из блоков элементов И 51 открывается сигналом, поступающим из блока -10 по одному из входов 43, и числом записывается в соответствующий счетчик 50, Вычитающие входы счетчиков 50 через бдок 52 элементов И, управляемых сигналами, поступающими по входам 48 из блока М (фиг, 1), соединены с входом 55. На этот вход из блока 13 управления через элемент И 26 поступают пачки импульсов, имитирующих кванты обслуживания. Счетчики 50 содержат текущее значение оставшегося времени обслуживания заданияi Когда обработка одного из заданий завершается, соответствующий счетчик 50 переходит в нулевое состояние и на его выходе формируется импульс. Этот импульс по одной из шин группы входов 38 (фиг, ) поступает в блок 0 и устанавливает соответствующий триггер 29 (фиг. 2) в нулевое состояние; через элемент ИЛИ 53 поступает на вы- ход 56 и далее - на вычитающий вход реверсивного счетчика 4 и суммирующий вход счетчика 5; с выхода 56 импульс поступает в блок 13 управления, прекращая поступление импуль- сов обслз живания в блок 12. .

Приоритетный блок 14 совместно с блоком 10 поиска свободных термина

лов и пересчетной схемой 97 выполня- ет функции корректирующего звена при моделировании адаптивных вычислительных систем, В г(роцессе адаптивной настройки системы ил заданное значение качества обслуживания приоритетных заданий с ростом нагрузки изменяется длительность кванта выделяемых для обработки заданий и корректируется структура системы,Сущность корректировки структуры системы заключается в том, что число терминалов, имеющих доступ к системе, изменяется в зависимости от текущего времени ответа системы Т-р , Уровень приоритета определяется номером терминала: наивысший приоритет имеют задания, поступающие в систему с терминала с.: наибольшим номером. Если текущее значение времени ответа системы Т, больше максимального порога эталонного времени ответа Т, т,е.

Т Т т N

то с блока 15 сравнения в

приоритетный блок 14 поступает оди- . ночный импульс по входу 65 на регистр 64. При этом один .лз триггеров регистра с наименьшим номером устанавливается в состояние i и соответствующий терминал блокируется, т.е. менее приоритетные задания с этого терминала в систему не поступают. Если в очередном интервале снова , Т то импульсом по входу 65 в единичное

состояние переводится еще один старший триггер регистра 64 и связанный с ним терминал блокируется. Этот процесс пошаговой блокировки терминалов с низшим приоритетом продолжается

постоянно, пока текущее значение времени ответа больше максимального порога Т . Если же Т Т , то с блока 15 сравнения на вход блока 14 поступает импульс,-при этом разблокируется наиболее приоритетный из заблокированных терминалов,

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

На входы 40 приоритетного блока 14 (фиг. 5) поступают импульсы неудовлетворенных запросов на термиия- лы вследствие их блокироки. Эти импульсы поступают черея соответствую71

оше элементы И 60, 1-ШИ 58 и подсчитываются суммр{рутощим счетчиком 57, в котором накапливается суммарное число заданий, не обслуженных вслед- ствие блокировки терминалов. Элементы И 61, ИЛИ 59, на которые поступаю

сигналы с нулевых выходов триггеров блоков 0 и 14, ооеспеч1шают выработ ку сигнала Есть свободные и незабло кированные терминалы.Этот сигнал поступает на выходную шину 67, обеспечивая доступ зада ний в систему путем открывания элемента И 27.

Блок 16 измерения времени ответа служит для оценки текущих значений времени ответа системы Т. Оценка осществляется в течение интервала наблюдения Т; длительность которого оп г зделяется временем заполнения счет- ч;;ка 5 (фиг, ). В нем подсчитывается количество обслуженных заданий. Ес.ии счетч ;;-: 5 содержит п разрядов,

т И

то после поступления 2 задании он устанавливается в состояние О, а на его ы-коде появляется И1 1пульс5 ко7 оры1-. подается на генератор 20 фиксированного числа импульсов и на эле--.;а1-1т 22 задер ск.

Генератор 20 Ь рабатывает п сдви- гающих импульсов, которые поступают Г ;акап,икваю1ций сумматор 17 и обес- лечивают сдвиг содержимого сумматора на п разрядов вправо. Так как в су 1маторе Г/ в течение интервала на- блюдения Т накапливается cy fMapHoe

.тП

время ответа / задании в системе, то после сдвига на п разрядов вправо содержимое сумматора 17 содержит среднее значение времени ответа Т.

Полученное значение Т импульсом выхода элемента 22 задержки через группу элементов И 21 переписывается я накапливающий сумматор 18, где накапливается сумма величин T(i 1,2 ...jK, К - число интервалов наблюде- НИН за время моделирования), и в блок 15 сравнения.В блоке 15 сравнения значение Т сравнивается с порогами эталонного значения. При этом по результатам сравнения осуществляется выбор дл; тельности кванта кг предстоящий гтериод наблюдения, а при ограничивается доступ в систему заданий с наименее приоритетных терминалов.

Блок 15 сравнения по сигналу, поступающему на вход 94 с выхода счетчика 5 через элемент 22 задержки по

63

окончании каждого интервала наблюдения, обеспечивает уравнение текуше- го значения времени ответа системы, вычисляемого в блоке 16 и записываемого в элемент 71 по входу 93, с рядом пороговых значений эталонного времени ответа, заранее введенных в регистры 89 блока сравнения по входам 28.

Сравнение текущего значения времени ответа Т. с величинами Т , Т.,,., .-. . , Т| осуществляется за N тактов, формируемых генератором 90 заданного числа и iпyльcoв (при вводе порогов обязательно соблюдение условия Т, Т, . . . ,Tfj),B результате сравнения на из выходов 95 блока 1 5 появляется импульс, поступающий затем на вход шифратора 115 пересчетной схемы блока управления.

Пересчетная схема 97 обеспечивает выбор длительности кванта обслуживания на каждь й предстоящий период наблюдения в зависимости от результатов Т с Т;. Перед нaчaлo i работы устройства на вход 1 1 3 выдается им пульс начальной установки. При этом регистр 116 записывается код, соответствующий минт- т-{-ально возможной длительности кванта (такая же длительность кванта устанавливается .при дальнейшей работе блока при поступлении сигнала pt-fT iT, ), который через элементы И по разрешающему сигналу с элемента 8 задержки заносится в счетчик 121. Вход счетчика 121 через элемент И 120 соедине с входом 108 бло ка, на который из блока 13 управления поступают тактовые импульсы с генератора 102 (фиг.7 Счетчик 121 в зависимости от кода, сформированного шифратором 1I5 при поступлении импульса на один из его входов с блока 15 сравнения и переписанного из регистра 116, определяет длительность кванта q. При установке счетчика 121 в нулевое состояние на выходе 109 формируется сигнал Конец кванта, который поступает в блок 13 управления.

Этот же сигнал через элемент ИЛИ 119 и элемент 118 задержки открывает группу элементов И 117 и разрешает перезапись кода из регистра в счетчик 121, переводит триггер 96 (фиг,7 в нулевое состояние, при этом закрывается элемент И 120 и поступление

У1

тактовых импульсов на вход счетчика 121 прекращается, открывается элемент И 23 и начинается заполнение суммирующего счетчика 122. Емкость счетчика определяет величину потерь 5 на переключение заданий. При переполнении счетчика 122 с выхода 110 импульс поступает в блок 13 управления, а также переводит триггер 96 в единичное состояние, разрешая формирование следующего кванта.

По окончании периода наблюдения на вход 23 поступает, импульс, стирающий хранящийся в регистре 116 код подготавливая регистр к записи нового кода длительности кванта на следующий период наблюдения.

Блок 13 управления (фиг. 7,1) выдает на блок 12 моделирования очере- ди пачки импульсов. Количество импулсов в пачках соответствует величине квантов обслуживания, последовательно вьщеляемых для обработки заданий в режиме разделения времени.

Интервалы между пачками моделируют временные потери на переключение программ. При работе в пакетном режиме блок управления выдает непрерывную последовательность импульсов на Бьсход П и далее на один из входов элемента И 26. Выбор режимов (разделение времени, пакетная обработка) осуществляется переключателем 101. Длительность кванта q и временные по тери на переключение программ S задаются с помощью пересчетной схемы. Триггер 103 блока управления вырабатывает сигнал, разрешающий вьщачу импульсов обслуживания через элемент И 26 в блок 1Z. Нормальное состояние триггера 113 - единичное. В нулевое состояние он переводится после окончания каждого кванта сигналом с выхода 109 блока 97 на время О и сигналом на входе 56 на время переходных процессов при.смене заданий (время определяется задержкой элемента 107).

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

Перед началом моделирования в блок 15 сравнения по входам 28 вводятся значения порогов эталонного времени ответа вычислительной сие- темы Т,, Tj,...,T и производится начальная установка элементов устройства. При этом обеспечивается доступ всех подключенных термина6iO

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

Импульсы с генератора 8 подсчитываются счетчиком 2 и поступают на элемент И 24 (фиг. ). Если в системе имеется хотя бы один свободный терминал, то импульс с выхода элемента И 24 поступает по входу 34 в блок 10. Этот импульс опрашивает цепочку элементов И 30, 31 и при наличии свободного и незаблокированного терминала подается на один из выходов 43 (фиг.2), разрешая запись случайного числа с генератора 9 в одном из счетчиков 50 блока 12 (фиг. 4). Генератор 9 вырабатьгоает сл - айное число только при наличии свободного незаблокированного терминала, что контролируется элементами И 61, ИЛИ 59 (фиг. 5) блока 14, на выходе 67 кторого при соблюдении указанных условий появляется разрешающий сигнал, открывающий элемент И 27.

Счетчик 3 подсчитывает число заданий, поступивших в систему, в счетчике 4 хранится текущее число задани в системе. По мере поступления заданий заполняются счетчики 50 блока 2 Обработка заданий моделируется путем выработки импульсов обслуживан я поступающих с блока 13 управления в блок 2 моделирования очереди. Порядок поступления этих импульсов регулируется элементом И 26. В зависимости от положения переключателя блока управления (фиг. 7) обработка заданий производится квантами или непрерывно до завершения обработки. В пе рвом случае моделируется режим разделения времени, во втором - пакетная обработка. Элемент И 26 управляется разрешающ1-гми сигналами, поступающими с блока 10 по шине 36 и с блока 13 по шине 98.

Переход от обработки одного задания к обработке очередного осуществляется по сигналу, выдаваемому на выход 112 блгжа 13. По этому сигналу сдвигается 1 в регистре М, при этом открывается очередной элемент И группы 52 и новая пачка импульсов выдается через этот элемент на соответствующий вычитающий счетчик 50 (фиг. 4). По завершении обработки задания соответствующий счетчик 50

1

устанавливается в состояние О. На его выходе появляется импульс, который по шине 56 поступает в блок 3, прерывая нп время гтер1еходных процес- сов (это время определяется задержкой в элементе 107 блока 13) поступление импульсов в блок 12. Импульс завершения обработки задания поступает также на счетчики 4 и 5.

Текущее значение длины очереди заданий, находящихся в системе, со счетчика 4 подается в блок индикации длины очереди и в управляемый генератор 7, который вырабатьгаает импульсы с частотой следования F п,где f - базовая частота генератора 1 п - число, хранимое в счетчике 4, Эти импульсы поступают в сумматор 17, работающий в режиме счетчика. В суммато- ре 11 образуется величина, равная суммарному времени пребывания заданий в системе. После поступления 2 заданий в систему (п- разрядность счетчика 5) с выхода счетчика 5 вы- дается и-:пульс, который поступает в блок 16 измерения времени ответа, обеспечивая вьгчисление текзпцего времени ответа системы Т за период наблюдения Т..

Величина Т с блока 16, в котором Т. сравнивается с Т,, Т, ..., Т,, поступает в блок 15 сравнения. В зависимости от результатов сравнения на одном из выходов 95 блока 15 появ- ляется импульс, который поступает в схему блока управления, где по этому сигналу устанавливается определенная для данного значения длительность кванта на предстоящий пё- риод наблюдения.

Если.по результатам сравнения текущее время ответа больше максимального порога эталонного времени отве- та (), то сигнал об этом вьвда- ется на вход блока 14 и изменяет состояние приоритетного регистра 64,обеспечивая тем самым временную блокировку терминала с наименьшим приори- тетом. Разблокировка заблокированного тер;- инала производится после окончания периода наблюдения,если по результатам сравнения текущее время ответа меньше минимального порога эта лонного времени ответа (Т.Т, ). В этом случае сигнал с выхода блока 15 сравнения поступает на вход 66 блока 14, обеспечивая разблокировку забло41612 .

кированного терминала с наибольшим приоритетом.

Изменение внешних условий функционирования вычислительной системы (вариации интенсивности входного потока заданий, изменения характеристик заданий) может привести к изменению качества-обработки приоритетных заданий . Внешние возмущения в предлагаемом устройстве моделируются путем вариации интенсивности потока заданий, вырабатываемого генератором 8, и характеристик времени обработки заданий кото1 ые задаются генератором 9.

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

Устройство для моделирования адаптивных вычислительных систем по авт. св. № 1020830, отличающее- с я тем, что, с целью расширения функциональных возможностей устройства за счет моделирования работы вычислительных систем с двухпараметри- ческой адаптацией, пересчетная схема блока управления дополнительно со- держит второй элемент И, первый и второй элементы ИЛИ, элемент задержки, группу элементов И, шифратор и регистр, разрядные входы которого соединены соответственно с выходами шифратора, а разрядные выходы регистра подключены соответственно к первым входам элементов И группы, выходы которых подключены соответственно к разрядным входам первого счетчика, вторые входы элементов И группы объединены и через элемент задержки подключены к выходу первого элемента ИЛИ, первый вход которого и первый вход второго элемента ВДИ объединены и являются входом начальной установки устройства, второй вход первого элемента ИЛИ подключен к выходу обнуления первого счетчика, первый вход второго элемента И соединен с инверсным выходом первого три1; гера блока управления а выход второго элемента И соединен с информационным входом второго счетчика пересчетной схемы, второй вход второго элемента И объединен с первым входом первого элемента И пересчетной схемы блока управления выход элемента ИЛИ блока моделирования очереди подключен к установочному входу регистра пересчетной схемы, выход второго элемента КПИ которой соединен с входом сброса шифратора, ин1314A14I6

формационные входы которого и второй соответственно.к вькодам сравнения вход второго элемента ИЛИ подключены устройства.

Изобретение относится к вычислительной технике и может быть использовано для статистического моделирования широкого класса вычислительных систем, в частности для моделирования мультипрограммных ЭВМ, работающих в режиме разделения времени с многошаговым алгоритмом адаптации. Цель изобретения - расширение функциональных возможностей устройства за счет моделирования работы вычислительных систем с двухпара- метрической адаптацией. Для достижения данной цели в пересчегНуто схему блока управления дополнительно введены второй элемент И; элемент ИЛИ, элемент задержки, группа элементов И, шифратор и регистр. Характерной особенностью устройства является его пригодность для моделирования широкого класса вычислительных систем, в частности обычных мультипрограммных систем в режиме разделения времени, а также адаптивных вычислительных систем с шаговой одно- параметрической и двухпараметриче- ской адаптациями. 8 ил. SS

Фае.1

Фие. 2

Физ.З

5

Фые.

Ус

40

65

66

W

39 Фие. 5

Фиг.7

Физ.