Рис 3. Связное хранение линейного списка. Пример реализации односвязного списка на Java

public class Node {

//содержимое текущего элемента списка

private int element;

//указатель на следующий элемент списка

private Node next;

//вывод содержимого текущего элемента

public int getElement(){

return element;

}

//установка содержимого для текущего элемента списка

public void setElement(int e){

element = e;

}

//получение указателя на следующий элемент списка

public Node getNext() {

return next;

}

//установка следующего элемента списка

public void setNext(Node n) {

next = n;

}

}

90. Анализ и интерпретация результатов моделирования на ЭВМ

Методы оценки результатов моделирования

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

,

а в качестве дисперсии – выборочная дисперсия

,

где N– число реализаций эксперимента

Требования, предъявляемые к качеству оценок

Несмещенность оценки, т.е. равенство математического ожидания оценки определяемому параметру:

Эффективность оценки. Несмещенная оценка параметраgназывается эффективной, если она имеет наименьшую дисперсию среди всех возможных несмещенных оценок параметраg, вычисленных по выборкам одного и того же объемаN, т.е.

M()² <=M, где

–рассматриваемая оценка

– другая рассматриваемая оценка

Состоятельность. Сходимость по вероятности оценки к оцениваемому параметру при N.

Статистические методы обработки результатов моделирования

Необходимо так организовать сбор и обработку результатов моделирования в процессе вычислений, чтобы оценки характеристик модели формировались постепенно по ходу моделирования без специального запоминания всей информации о состояниях модели M. Для оценки выборочного среднего необходимо накапливать сумму возможных значений случайной величиныy_i:

Для вычисления выборочной дисперсии необходимо накапливать две суммы: значений y_iи их квадратов:

Задачи обработки результатов моделирования

Определение эмпирического закона распределения случайной величины.

Проверка однородности распределения.

Сравнение средних значений и дисперсий переменных, полученных в результате моделирования.

С точки зрения математической статистики эти задачи являются типовыми задачами проверки статистических гипотез с помощью статистических критериев согласия, например, критериев Пирсона.

Виды методов анализа результатов моделирования

Корреляционный анализ

Позволяет определить тесноту связи между двумя (или более) случайными величинами, наблюдаемыми и фиксируемыми в процессе моделирования. Теснота связи оценивается с помощью коэффициента корреляции.

Различные случаи корреляции переменных показаны на рисунках (а) – (г).

Если коэффициент корреляции равнее 0 (случай (а) ), случайные величины независимы.

Если коэффициент корреляции по модулю равен 1 (случай (б) ) – имеет место функциональная (т. е. нестохастическая) линейная зависимость вида y=b₀+b₁x.

Если коэффициент корреляции заключен в диапазоне от 0 до 1, то наблюдается либо линейная корреляция с рассеянием (случай (в) ), либо нелинейная корреляция ( случай (г) ).

Регрессионный анализ результатов моделирования

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

=b₀+b₁x– величина, предсказываемая регрессионной моделью,

e_i=-y_i– величина ошибки,

²→min– функция ошибки.

Дисперсионный анализ результатов моделирования

Это метод, который устанавливает относительное влияние различных факторов на значение отклика.

Пусть при варьирования фактора Xбыла получена выборка значений случайной величиныYвидаy₁,y₂…y_k, гдеk– количество уровней фактораX. Влияние фактораXоценивается неслучайной величинойD_X, называемойфакторной дисперсией.

Анализ чувствительности модели

Анализ чувствительности модели – это проверка устойчивости результатов моделирования по отношению к возможным отклонениям параметров имитационной модели от истинных значений

Определим устойчивость модели как степень нечувствительности ее точности к изменению входных параметров.

Малым отклонениям параметров имитационной модели будут соответствовать изменения выходных параметров, частные производные первого и второго порядкаколичественно характеризуют чувствительность модели к изменению её параметров. Большие отклонения характеристикпри малых вариацияхсвидетельствуют о неустойчивости модели по отношению к этим вариациям. Т.к. исходные данные, на основе которых строится модель, часто бывают неточны, необходимо знать, при каком разбросе этих данных сохраняется справедливость основных результатов моделирования. Если отклик модели сравнительно малочувствителен к изменениям некоторых параметров, их точность является удовлетворительной. Если отклик модели оказывается высокочувствительным по отношению к некоторым её параметрам, следует получить более точные оценки этих параметров и более детально проработать модель.

Калибровка и проверка пригодности модели

Калибровка – это проверка пригодности модели для ограниченного числа входных условий, за которой при необходимости следует модификация модели, делающая её точность приемлемой. Если точность модели неудовлетворительна, модель должна быть изменена, а процесс проверки повторен.

Схема итеративной процедуры калибровки

Система Sпри множестве входных переменных Х имеет множество выходных переменныхY. Соответственно Х_М– множество входных переменных,S_M– модель,Y_M– множество выходных характеристик модели. Сравнение значений одноименных выходных переменных системыSи моделиS_Mпозволяет оценить точность модели. Если реальная системаSне существует или недоступна для эксперимента, вместо неё для калибровки используется аналитическая модель. При заданной точности модель считается адекватной исследуемой системе, если её выходные переменные удовлетворяют заданной точности. Чем ближе структура модели к структуре исследуемой системы и чем выше степень детализации модели, тем обширнее область её пригодности. Т.о. калибровку можно рассматривать, как итеративный процесс детализации модели, в котором показатель качества (точность модели) должен максимизироваться.

Визуализация результатов моделирования

Для визуализации результатов моделирования наиболее широко используются:

Гистограмма относительных частот выходной переменной модели – эмпирическая плотность распределения. Область предполагаемых значений выходной переменной разбивается на интервалы. В ходе эксперимента определяют число попаданий значений выходной переменной в каждый интервал и подсчитывают общее число измерений. После завершения эксперимента для каждого интервала вычисляют отношение числа попаданий значений выходной переменной к общему числу измерений и ширине интервала. Для построенной гистограммы можно попытаться подобрать теоретический закон распределения вероятностей.

Бегущая волна – зависимость выходной переменной модели от времени.

Фазовые портреты – зависимость одной выходной переменной от другой. Примеры фазовых портретов показаны на рисунках (а) – (в). Для выходных переменных F1 иF2 на рисунках (а) и (б) зависимость существует, а для выходных переменныхF1 иF2 на рисунке (в) зависимость не существует.

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

91. Детерминированные задачи исследования операций (=27)

92. Модульная структура построения ОС и их переносимость

Модульное ядро – современная, усовершенствованная модификация архитектуры монолитных ядер, в которой код ядра разделяется на отдельно компилируемые и загружаемые модули.

Модульные ядра предоставляют механизм загрузки модулей ядра, поддерживающих аппаратное обеспечение (например, драйверов). Загрузка модулей может быть как динамической (без перезагрузки операционной системы), так и статической (выполняемой при перезагрузке). Большинство современных ядер, такие как OpenVMS, Linux, FreeBSD, NetBSD и Solaris, позволяют во время работы динамически (по необходимости) подгружать и выгружать модули, выполняющие часть функций ядра.

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

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

Ключевым моментом в оценке переносимости является стоимость необходимых изменений.

При написании переносимой операционной системы нужно следовать перечисленным ниже правилам.

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

Необходимо учитывать аппаратную платформу, на которую операционная система должна быть перенесена.

Следует минимизировать или по возможности исключить части кода, которые непосредственно взаимодействуют с аппаратурой. Оставшийся после такой оптимизации аппаратно-зависимый код, который не может быть исключен, локализуется в отдельных модулях (HAL – hardware abstraction layer).

93. Общие принципы системной организации в системах управления (ТРЕБУЕТ ДОРАБОТКИ, Миша)

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

1) цель управления: что нужно получить, куда двигаться;

2) получение информации о состоянии объекта: что получаем, куда движемся;

3) определение отклонения желаемого от действительного и выработка управляющего воздействия;

4) отработка, исполнение управляющего воздействия.

Если все четыре шага реализуются автоматически, то система является автоматической, в противном случае - автоматизированной.

94. Уровни и протоколы в сетях (=24)

95. Имитационные модели систем

Методы имитационного моделирования основаны на представлении порядка функционирования системы в виде алгоритма, который называется имитационной (алгоритмической) моделью.

При построении имитационных моделей широко используется агрегатный подход. Для моделирования заданного класса систем создается набор агрегатов – модулей модели. Агрегаты могут соответствовать элементам систем, например, процессорам, ОЗУ, каналам ввода–вывода, каналам передачи данных и другим элементам, воспроизводя определенные аспекты их функционирования. В качестве агрегатов могут выступать математические объекты, с помощью которых генерируются и преобразуются необходимые процессы. Так, для моделирования систем на основе сетей массового обслуживания в качестве агрегатов представляются источники потоков заявок, систем массового обслуживания, узлы, управляющие распределением заявок по нескольким направлениям, и т.д. По существу агрегат является описанием функции некоторого объекта в аспектах, соответствующих цели моделирования – оценке производительности, надежности и т.д.

Функции агрегатов представляются в параметрической форме, то есть в записи функций используются параметры, характеризующие конкретный объект. Так, параметром процессора является производительность (быстродействие), оперативной памяти – емкость, системы массового обслуживания – дисциплина обслуживания, число каналов и распределение длительности обслуживания. Функция агрегата,представляется в алгоритмической форме – в виде процедуры, где параметры– определяют состояние входов агрегата, а– режим его функционирования,– состояние выходов агрегата. В модели агрегат выглядит как модуль (рис. 3.3 (а)), настраиваемый на заданный режим функционирования множеством параметрови преобразующий входные воздействияв выходные состоянияв соответствии с функцией агрегатаи значениями параметров. Множество агрегатов разного типасоставляет базис имитационных моделей заданного класса систем.

Рис. - Структура агрегатной модели

Имитационная модель собирается путем соединения выходов агрегатов с входами других агрегатов (рис. 3.3 (б)). На рисунке агрегаты обозначены , где – тип и– порядковый номер агрегата в модели. Агрегатыи – генераторы, формирующие воздействия в соответствии с параметрамии. Состав агрегатов, структура связей между ними и наборы параметров агрегатовопределяют модель. Процесс моделирования состоит в реализации процедурв необходимом порядке. При этом значения, формируемые на выходах агрегатов, переносятся на входы, связанных с ними агрегатов, в результате чего вычисляются значенияи. Путем обработки данных, наблюдаемых в характерных точках модели (на выходах модулей), получают оценки качества функционирования любого из агрегатов и системы в целом.

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

Исследование ВС имитационными методами включает несколько этапов. 1. Определение принципов построения модели.Цель этого этапа – сформировать общий замысел модели (состав характеристик и параметров, подлежащих отображению, область определения модели, требования к точности результатов моделирования, тип математической модели, программные и технические средства для описания и реализации модели). На этом этапе выдвигаются гипотезы о свойствах моделируемой системы, принимаются допущения для использования соответствующих математических методов и конкретизируются эксперименты, проводимые на модели. 2.Разработка модели. Цель этого этапа – создание программы моделирования для ЭВМ. При этом общий замысел модели преобразуется в конкретное алгоритмическое описание. Этап завершается проверкой работоспособности и адекватности модели. 3.Моделирование на ЭВМ. Цель этого этапа – получение с помощью модели данных о поведении исследуемой системы, обработка полученных данных, а при синтезе системы – выбор параметров, оптимизирующих заданные характеристики системы и удовлетворяющих заданным ограничениям.

Недостатки имитационных методов – большие затраты времени на моделирование и частный характер получаемых результатов. В имитационной модели процесс функционирования системы воспроизводится во всех, существенных для исследования, деталях за счет последовательного выполнения на ЭВМ операций над величинами. Поэтому для одного прогона модели требуются минуты и часы процессорного времени. При этом оцениваются характеристики системы только в одной точке, соответствующей значениям параметров, введенных в модель перед началом моделирования. Чтобы определить зависимость между характеристиками и параметрами, необходимы многократные прогоны модели, в результате которых значения характеристик определяются для многих наборов параметров. Возможности методов оптимизации параметров на имитационных моделях ограничиваются большими затратами времени на моделирование системы в одной точке.

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

96. Стохастические задачи исследования операций (=32)

97. Управление памятью

В программе можно выделить три типа адресов: символьные имена, виртуальные адреса и физические адреса. Символьные имена являются идентификаторами переменных в программе. Виртуальные адреса – это условные адреса, вырабатываемые транслятором исходного кода в объектный код. В простейшем случае транслятор может выполнять преобразование символьных имен непосредственно в физические адреса. Физические адреса – это номера ячеек в памяти. Данные номера выставляются центральным процессором на адресную шину при доступе к оперативной памяти.

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

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

Достоинством данного метода является простота реализации. Вместе с тем, присутствует недостаточная гибкость. Например, уровень мультипрограммирования жестко ограничен числом выделенных разделов. В современных операционных системах пользователь также может вручную управлять разделами внутри виртуального адресного пространства процесса.

Динамические разделы.При использовании динамических разделов распределение памяти по разделам заранее неизвестно. Операционная система ведет таблицы занятых и свободных разделов. При поступлении новой задачи для ее загрузки выбирается свободный раздел подходящего размера. Возможны разные стратегии выбора свободного раздела: первый по порядку подходящий, наименьший по размеру подходящий, наибольший по размеру подходящий раздел.

Достоинства способа - это большая гибкость по сравнению с методом фиксированных разделов и отсутствие зависимости уровня мультипрограммирования от начального разбиения на разделы. Недостатком является эффект фрагментации памяти. Он заключается в появлении с течением времени большого числа небольших несмежных сегментов. Суммарный объем свободной памяти, содержащийся в таких сегментах, может быть большим, однако малый размер каждого отдельного сегмента не позволяет загрузить программу. Варьирование стратегий выбора свободного раздела может уменьшить фрагментацию. В современных операционных системах такой способ используется для управления кучей (динамической памятью) процесса.

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

Остальные способы описаны в вопросе 112 «Механизмы реализации виртуальной памяти».

98. Устойчивость систем управления

Устойчивость систем управления

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

Критерий Гурвица

Для характеристического уравнения

— некратные корни характеристического уравнения

составим квадратную матрицу (таблицу) коэффициентов, содержащую п строк и п столбцов:

Эта таблица составляется следующим образом.

. Каждая строка дополняется коэффициентами

с нарастающими индексами слева направо так, чтобы чередовались строки с нечетными и четными индексами. В случае отсутствия данного коэффициента, а также если индекс его меньше нуля или больше п, на месте его пишется нуль.

должны быть больше

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

Определители Гурвица составяются по следующему правилу (см. (6.11)):

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

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

Первое условие соответствует границе устойчивости первого типа (апериодическая граница устойчивости) и второе — границе устойчивости второго типа (колебательная граница устойчивости).

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

порядка

Для этого уравнения критерий Гурвица дает

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

порядка

Для этого уравнения критерий Гурвица требует

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

Критерий Найквиста - частотный критерий, позволяющий по виду амплитудно-фазовой частотной характеристики разомкнутой системы оценить устойчивость работы замкнутой системы. АФЧХ может быть получена экспериментально или аналитически. Аналитическое построение АФЧХ производится обычными методами. Критерий Найквиста формулируется по разному в зависимости от того, устойчива разомкнутая система или нет.

Если разомкнутая система устойчивая, то для устойчивости замкнутой системы необходимо и достаточно, чтобы АФЧХ разомкнутой системы при изменении частоты от 0 до не охватывала точку с координатами -I, j0. Если АФЧХ разомкнутой системы проходит через точку с координатами -I, j0, то система будет нейтральной. На рис.4.4 представлены АФЧХ разомкнутых статических систем. Критерий Найквиста позволяет наглядно проследить влияние изменения параметров передаточной функции на устойчивость системы.

99. Эталонная модель взаимосвязи открытых систем (=29)

Сетевая модель OSI (англ. open systems interconnection basic reference model — базовая эталонная модель взаимодействия открытых систем, сокр. ЭМВОС) создана в 1978 году. В соответствии с ней процесс информационного взаимодействия между системами разделяется на уровни с четко разграниченными функциями. Выделяются семь уровней информационного взаимодействия:

7) Уровень приложения

6) Уровень представления

5) Сеансовый уровень

4) Транспортный уровень

3) Сетевой уровень

2) Канальный уровень

1) Физический уровень

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

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

7) Уровень приложения

Обеспечивает взаимодействие сети и пользователя. Уровень разрешает приложениям пользователя иметь доступ к сетевым службам, таким, как обработчик запросов к базам данных, доступ к файлам, пересылке электронной почты. Также отвечает за передачу служебной информации, предоставляет приложениям информацию об ошибках и формирует запросы к уровню представления.

6) Уровень представления

Этот уровень отвечает за преобразование протоколов и кодирование/декодирование данных. Запросы приложений, полученные с уровня приложений, он преобразует в формат для передачи по сети, а полученные из сети данные преобразует в формат, понятный приложениям.

5) Сеансовый уровень

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

4) Транспортный уровень

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

3) Сетевой уровень

Предназначается для определения пути передачи данных. Отвечает за трансляцию логических адресов и имён в физические, определение кратчайших маршрутов, коммутацию и маршрутизацию, отслеживание неполадок и заторов в сети. На этом уровне работает такое сетевое устройство, как маршрутизатор.

2) Канальный уровень

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

1) Физический уровень

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

100. Концептуальные модели систем

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