Б1В Задача оптимальной статической маршрутизации

Задача состоит в следующем: Для каждой пары узлов поток γjk распределяется между множеством маршрутов, идущих из j в k так, чтобы минимизировать задержку Т. α – локальный минимум, является глобальным При этом выполняются следующие ограничения: Сумма всех информационных потоков равно (p) ∑хр = γjk. Потоки удовлетворяющие это ограничение образуют выпуклые многогранники, вершиной которой обозначают потоки -> fi= Ci0 то время Т-> ∞ - перегрузка канала) Целевая функция носит в себе штрафную функцию, т.к. при превышении fi min является невозможным. Решение сформированной задачи основано на следующем утверждении: совокупность путевых потоков (х) минимизирует Т в том и только в том случае, если каждый маршрутный поток является кратчайшим в метрике длин каналов связи.

Мы исследуем скорость роста целевой функции при приращении КС Х – путь минимального приращения, Т стремится к мин Алгоритм решения данной задачи (алгоритм отклонения потоков)

Шаг 0

Шаг 1

Шаг 2 Решить задачу определения кратчайших маршрутов в метрике длин di И соответственно каждый поток γjk отправляем по кратчайшим маршрутам и определяем результирующие потоки в канале связи. Шаг 3 Надо определить время задержки с учетом полученного вектора пропускных способностей.

Шаг 4 Найти такое значении α от 0 до 1 так что (1-α)*f(n) + α*φ(n) чтобы Т = min
Шаг 5 Найденное значение α обозначаем как α*f(n+1) = (1- α*) * f(n) + α*φ(n) n=n+1 и переходим к шагу 1

15Б2В Многоочередная дисциплина обслуживания процессов с равными приоритетами в ОС.

В ЭВМ, в операционных системах широко используются многоочередные дисциплины. Схема одной из таких дисциплин приведена на рис. 2.4. Здесь организуется Nочередей. Все новые запросы поступают в конец первой очереди. Первый запрос из очереди i поступает на обслуживание лишь тогда, когда все очереди от 1 до (i—1)-й пустые. На обслуживание выделяется квант времени tk. Если за это время обслуживание запроса завершается полностью, то он покидает систему. В противном случае недообслуженный запрос поступает в конец очереди с номером i+l.

Схема многоочередной дисциплины обслуживания

После обслуживания из очереди i система выбирает для обслуживания запрос из непустой очереди с самым младшим номером. Таким запросом может быть следующий запрос из очереди i или из очереди i+l (при условии, что после обслуживания запроса из очереди i последняя оказалась пустой). Новый запрос поступает в первую очередь (i = l). В такой ситуации после окончания времени tk, выделенного для обслуживания запроса из очереди i, будет начато обслуживание запроса 1-й очереди. Если система выходит на обслуживание заявок из очереди N, то они обслуживаются либо по дисциплине FIFO (каждая заявка обслуживается до конца), либо по круговому циклическому алгоритму. Данная система наиболее быстро обслуживает все короткие по времени обслуживания запросы. Недостаток системы заключается в непроизводительных затратах времени на перемещение запросов из одной очереди в другую. Все рассмотренные дисциплины обеспечивают не только обслуживание очередей, но и их формирование. Для всех таких дисциплин характерно отсутствие приоритетности запросов при их поступлении в систему. Но после поступления каждый запрос приобретает приоритет, который изменяется в процессе обслуживания одной очереди или многих очередей

Существуют многоочередные дисциплины, в которые поступают запросы, имеющие определенный приоритет на обслуживание тем или иным ресурсом. Схема такой приоритетной дисциплины приведена на рис.2.5. Основу этой дисциплины представляет ранее рассмотренная многоочередная дисциплина. Поступающие в систему новые запросы не обязательно попадают в 1-ю очередь. Они попадают в очередь в соответствии с имеющимися приоритетами, которые определяются параметрами обслуживаемых процессов.

15Б3В Логическая основа построения сумматоров, способы организации переноса, пример практической реализации

Сумматор предназначен для арифметического сложения чисел, представленных в двоичном коде. Многоразрядные сумматоры строятся на основе одноразрядных, связанных между собой цепями переноса. Одноразрядный сумматор выполняет арифметическое сложение одноразрядных двоичных чисел ai и bi с учётом переноса сi из соседнего младшего разряда. УГО При подаче на входы сумматора сигналов ai, bi, ci на его выходах вырабатываются сигналы соответствующий значению суммы si и переноса в соседний старший разряд c i+1. По таблице истинности можно записать СДНФ функции: МДНФ:

Многоразрядный сумматор с последовательным переносом строится на основе одноразрядных сумматоров, последовательно соединив их по цепям переноса. Слагаемые А и В подаются на входы сумматора в параллельном коде, то есть одновременно. На выходах сумматора образуется сумма s=s0s1. Сигнал переноса последовательно распространяется от младшего разряда к старшему. На выходе с2 вырабатывается единица переноса в следующий разряд. УГО Время суммирования зависит от количества разрядов. УГО ИМС сумматор 555ИМ5 содержит в одном корпусе два независимых одноразрядных сумматора ИМС 133ИМ3 – четырёхразрядный сумматор с параллельным переносом. Для наращивания разрядности используются выводы С0 и С4 Сумматоры с параллельным переносом во всех разрядах результаты суммирования вырабатываются одновременно в помощью специальных схем CR (сагту-перенос), на входы которых поступают все необходимые переменных (внешний входной перенос Свх и значения всех разрядов слагаемых, младших относительно данного). Наибольшее быстродействие, но сложная структура. Для построения принципиального схемы сумматора для его произвольного разряда вводятся две вспомогательные функции: Генерации g принимает единичное значение, если перенос на выходе данного разряда появляется независимо от переноса из младшего разряда Функция прозрачности h принимает единичное значение, если перенос на выходе данного разряда появляется только при наличии переноса из младшего разряда Сигнал переноса в произвольном i-том разряде: , , , ,