Лабораторная работа Выполнила



Скачать 289.27 Kb.
Дата26.07.2014
Размер289.27 Kb.
ТипЛабораторная работа
ULIM

Факультет Экономических Знаний



«Вычислительные информационные системы»

Лабораторная работа



Выполнила: Науменко Юлия, мастерат

Научный руководитель

Профессор: С. Максимилиан

Кишинёв 2011

1. ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



2. ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ

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

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


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

  • разработка схем размещения файлов пользователя в памяти машины при наличии нескольких типов памяти;

  • разработка схем планирования заданий в многопрограммном режиме разделения времени.

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

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



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

Авторы (Абат, Дюбнер, Уэйнберг) работы «Анализ запоминающего устройства IBM 2314» применили теорию массового обслуживания для анализа функционирования внешнего запоминающего устройства в режиме реального времени. Изучалась зависимость между производительностью обслуживающего устройства, работающего в стохастическом режиме, и временем его реакции па каждую заявку, требующую обслуживания. При этом использовалось дисковое запоминающее устройство типа IBM 2314. Результаты анализа были представлены в виде серии графиков, демонстрирующих зависимость времени реакции системы файлов от производительности для различных распределений длины записи и заявок пользователей. Согласно полученным данным, работа любого накопителя на дисках, у которого характеристика времени поиска нужной информации аппроксимируется кусочно-линейной непрерывной функцией, может быть проанализирована предложенными методами.



Лауэр разработал аналитическую модель для сравнения ЭВМ типа IBM 360/67, в которой для организации постраничной виртуальной памяти используются магнитные барабаны, с такой же ЭВМ, но имеющей для этих целей запоминающее устройство большой емкости на магнитных сердечниках. В результате анализа было установлено, что магнитные барабаны обеспечивают необходимую интенсивность постраничного обмена, однако при этом резко возрастает стоимость системы.

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

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

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



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

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

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



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

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

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

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

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



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

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

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

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

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

3. СИСТЕМЫ ОБРАБОТКИ ДАННЫХ

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

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

Имитационные модели представляют собой пакеты специальных программ, которые имитируют различную нагрузку (программы и файлы) упомянутых выше вычислительных систем (аппаратных средств, операционной системы и, возможно, системы управления файлами). Гипотетическая рабочая нагрузка системы задается с помощью совокупности документов установленной формы или на языке спецификаций. Характеристики файлов включают такую информацию, как коэффициент блочности, количество записей, длина записей, плотность записей. Каждая отдельная программа, работающая в пакетном режиме или режиме реального времени, описывается в форме, которая не связана с техническими характеристиками какой-либо конкретной машины. Описание программ включает указание требуемого вида обработки и ожидаемой интенсивности использования формируемых файлов. Технические характеристики аппаратных и программных средств ряда машин организуются в виде библиотеки, которую можно использовать в рамках любой имитационной модели. Характеристики аппаратных средств содержат описание центрального процессора, внешних устройств и коммуникационного оборудования. Характеристики программных средств включают описание операционных систем, процессоров, проблемно-ориентированных языков, программ сортировки данных и генераторов отчетов. Эти данные вводятся в машинную модель, моделируется выбранная нагрузка и конфигурация, и затем печатаются выходные данные, которые содержат краткие сведения об интенсивности использования файлов, отдельных устройств и времени реакции системы.



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

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

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

Имитационная модель файла FOREM, написанная па Фортране, была предложена Сенком, Ламом и Оуэнсом. В качестве входных данных в ней используются таблицы, описывающие логические файлы, записи, зоны, параметры устройств и способы организации поиска информации. Заявки на обслуживание генерируются па основании спецификации запросов, а результаты ответов на запросы определяются описаниями, даваемыми в форме таблиц. В модели имеются имитационные блоки, отображающие специфические условия и функционирующие совместно с блоками имитации запросов. Время обработки оценивается при помощи соответствующих уравпений, введенных в блоки модели. Обширные материалы, касающиеся моделирования индексно-последовательного метода доступа, изложены Ламом, Линг, Сенко, Мартин рассмотрел использование языка GPSS (англ. General Purpose Simulation System — общецелевая система моделирования) для моделирования способа организации доступа к файлам.



Ниссен, Бихаймер провели сравнительную оценку достоинств индексно-последовательной и прямой организации файла как в случае пакетной обработки, так и при обработке в реальном масштабе времени. В работе «Анализ индексно-последовательной и прямой организации доступа к файлам» оценивался также эффективный метод актуализации файла прямого доступа в режиме пакетной обработки. Бихаймер и др. разработали имитационную модель для генерации таблиц, которые могут использоваться для выбора рационального способа организации файлов и режима обработки на основе спецификации требований пользователя и описаний файлов.

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

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

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

Эта модель включает точную спецификацию данных, действий пользователя и параметров памяти. Набор данных описывается путем указания числа записей, количества полей данных в каждой записи и конкретных полей, которые могут использоваться для однозначной идентификации записи. Например, набор данных о структурах какой-либо организации может содержать 1000 логических записей, состоящих каждая из 10 пар «признак — значение», которые составляют описание характеристик одного сотрудника. В каждой логической записи может присутствовать номер пропуска, принадлежащий только этому сотруднику.

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

Запоминающее устройство описывается посредством задания параметров, представляющих собой характеристики аппаратных средств (например, скорость вращения диска) и программных средств (например, способы установления логической связи двух элементов хранимых данных). Различные способы организации файлов оцениваются на основе анализа линейной комбинации следующих составляющих затрат: объема памяти, требуемого для размещения файлов; времени, необходимого для осуществления выборки из файлов; времени, необходимого для текущего обслуживания (ведения) системы файлов.



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

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

Яо разработал систему проектирования, обеспечивающую выбор наиболее рационального варианта организации файлов. Согласно этой системе, необходимые для проектирования параметры определяются на основе описаний данных, действий пользователя и характеристик ЭВМ. Выходом системы проектирования является целесообразная структура файлов; детали этой структуры могут уточняться посредством имитационного моделирования или иными способами. Работа модели основана на том, что при любом способе выборки осуществляются постепенное сужение поиска и иерархическая декомпозиция пространства поиска. Траектории доступа к информации базы данных для большинства структур файлов моделировались с помощью древовидной схемы выборки. Эта схема представляется двумя группами переменных: одна из них характеризует конфигурацию дерева, а другая — его ветви. Модель древовидной схемы выборки выполняет преобразование пространства структур файлов в n-мерное пространство переменных. Проектные требования учитываются в функции затрат, определяемой на этом множестве переменных. С помощью алгоритма нелинейного программирования определяется множество значений переменных, обеспечивающее минимум функции затрат, что в свою очередь приводит к структуре файлов минимальной стоимости.


4. ИНФОРМАЦИОННЫЕ СИСТЕМЫ

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



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

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



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

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

Модели, основанные на формализованном описании требований пользователя, создаются для того, чтобы помочь им в разработке машинных программ, файлов и баз данных. В частности, алгоритмы, предназначенные для группировки и представления требований пользователя в виде, соответствующем входным спецификациям моделей проектирования файлов, обсуждались в предыдущем разделе.
ЗАКЛЮЧЕНИЕ

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

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

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



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


Похожие:

Лабораторная работа Выполнила iconЛабораторная работа №1 Работа в Oracle Database Express Edition 1 Лабораторная работа №6
Лабораторная работа Выполнение расчетов с использованием программирования в среде Visual Basic for Applications
Лабораторная работа Выполнила iconЛабораторная работа №3. Знакомство с прерываниями. Лабораторная работа №4. Программная обработка клавиатуры
Лабораторная работа №1. Знакомство с общим устройством и функционированием ЭВМ. Изучение структуры процессора, организации памяти,...
Лабораторная работа Выполнила iconЛабораторная работа по теме: «ms doc. Основные команды.»
Мбоу «сош №8 г. Петровска Саратовской области» Лабораторная работа в среде ms dos
Лабораторная работа Выполнила iconЛабораторная работа 08 Изучение дифракции рентгеновских лучей на кристаллах Москва 2005 г. 1 лабораторная работа 08
Цель работы: определение расстояний между атомными плоскостями в кристалле по имеющейся рентгенограмме
Лабораторная работа Выполнила iconЛабораторная работа №1 3 Создание ситуационного плана миигаиК 3 Лабораторная работа №2 8 Оцифровка части карты и создание базы данных 8
«Геоинформационные технологии сбора и обработки информации» в среде MapInfo Professional
Лабораторная работа Выполнила iconИсследование изучение строения и физиологические процессы. Эксперимент серия опытов. Лабораторная работа
Совокупность относительно однородных приемов, операции освоения действительности ( теоретические- практические) подчиненных расширению...
Лабораторная работа Выполнила iconЛабораторная работа №17 по дисциплине " Методы и средства гидрометеорологических измерений". Устройство осциллографов
Устройство осциллографов. Лабораторная работа №17 по курсу “Гидрометеорологические измерения”. С. Петербург: рггму, 2002, 14 с
Лабораторная работа Выполнила iconЛабораторная работа по курсу «Физические основы микроэлектроники» Нижний Новгород, 2005
Операционный усилитель: Лабораторная работа по курсу «Микроэлектроника» / Сост. Н. В. Федосеева, С. М. Планкина. – Н. Новгород, ннгу,...
Лабораторная работа Выполнила iconЛабораторная работа 01 определение плотности твердых тел москва 2005 г. Лабораторная работа 101
Существуют методы анализа и учета влияния различных погрешностей на результаты измерений. Все погрешности (ошибки) измерений принято...
Лабораторная работа Выполнила iconЛабораторная работа №5 Анализ операций с ценными бумагами
Лабораторная работа №5 включает 5 заданий. Для выполнения этих заданий необходимо ознакомиться с теоретическим материалом, приведенным...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org