Рис 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. Имитационные модели систем (Ира)

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

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

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

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

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

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

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

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

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

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

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

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

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

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