Очереди сообщений

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

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

Семафоры

Семафоры являются одним из классических примитивов синхронизации. Семафор (semaphore) - это целая переменная, значение которой можно опрашивать и менять только при помощи неделимых (атомарных) операций.

Двоичный семафор может принимать только значения 0 или 1. Считающий семафор может принимать целые неотрицательные значения.

В приложениях как правило требуется использование более одного семафора, ОС должна представлять возможность создавать множества семафоров.

Разделяемая память

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

Сокеты

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

47. Задачи дискретной оптимизации

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

1) Множество целых чисел – число людей, число датчиков, число самолетов и т.д.

2) Множество дискретных значений – это стандартные значения в производственных задачах, которые заранее зафиксированы (количество деталей в изделии, мощность электродвигателя и т.п.)

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

Такого рода задачи принадлежат классу задач дискретной оптимизации:

Задачей линейного целочисленного программирования (ЛЦП) называют

задачу вида:

Вместо последнего условия задача дискретной оптимизации может содержать условие

Тогда речь идет о задаче линейного булевского программирования (ЛБП).

Наиболее распространенные задачи дискретной оптимизации:

1) Задача о назначениях (о выборе).

Имеется n работ и n кандидатов на эти работы. Известен эффект того, что i-ая работа будет занята j-м работником c_ij. Необходимо распределить работы по работникам так, чтобы суммарный эффект был максимальным.

2) Задача о покрытии.

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

3) Задача о коммивояжёре.

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

4) Задача о ранце.

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

48. Целостность БД

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

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

Целостность обеспечивается путем задания ограничений. В зависимости от источника можно выделить инструментальные ограничения, структурные ограничения и бизнес-правила.

К инструментальным ограничениям относят проверку правильности данных при вводе. Например, поле числа не может содержать текстовые символы, а поле даты должно содержать допустимое значение даты. Средства реализации инструментальных ограничений встроены в СУБД.

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

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

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

Ограничения могут найти свое выражение:

– при описании атрибутов отношений в концептуальной схеме;

– в запросе к базе данных;

– в процедуре базы данных;

– в правиле (в триггере).

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

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

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

ПРототипом правил послужили триггеры (triggers), которые впервые появились в СУБД Sybase и впоследствии были реализованы в том или ином виде и под тем или иным названием в большинстве многопользовательских СУБД.

Транзакция – неделимая с точки зрения воздействия на БД последовательность операторов манипулирования данными (чтения, удаления, вставки, модификации), такая, что:
1) либо результаты всех операторов, входящих в транзакцию, отображаются в БД;
2) либо воздействие всех операторов полностью отсутствует.
При этом для поддержания ограничений целостности на уровне БД допускается их нарушение внутри транзакции так, чтобы к моменту завершения транзакции условия целостности были соблюдены.
Для обеспечения контроля целостности каждая транзакция должна начинаться при целостном состоянии БД и должна сохранить это состояние целостным после своего завершения. Если операторы, объединенные в транзакцию, выполняются, то происходит нормальное завершение транзакции, и БД переходит в обновленное (целостное) состояние. Если же происходит сбой при выполнении транзакции, то происходит так называемый откат к исходному состоянию БД.

Модели транзакций.: модель автоматического выполнения транзакций и модель управляемого выполнения транзакций, обе основаны на инструкциях языка SQL – COMMIT и ROLLBACK.

Автоматическое выполнение транзакций.
В стандарте ANSI/ISO зафиксировано, что транзакция автоматически начинается с выполнения пользователем или программой первой инструкции SQL. Далее происходит последовательное выполнение инструкций до тех пор, пока транзакция не завершается одним из двух способов:
• инструкцией COMMIT, которая выполняет завершение транзакции: изменения, внесенные в БД, становятся постоянными, а новая транзакция начинается сразу после инструкции COMMIT;
• инструкцией ROLLBACK, которая отменяет выполнение текущей транзакции и возвращает БД к состоянию начала транзакции, новая транзакция начинается сразу после инструкции ROLLBACK.
Такая модель создана на основе модели, принятой в СУБД DB2.
Управляемое выполнение транзакций.
Отличная от модели ANSI/ISO модель транзакций используется в СУБД Sybase, где применяется диалект Transact-SQL, в котором для обработки транзакций служат четыре инструкции:
• инструкция BEGIN TRANSACTION сообщает о начале транзакции, т.е. начало транзакции задается явно;
• инструкция COMMIT TRANSACTION сообщает об успешном выполнении транзакции, но при этом новая транзакция не начинается автоматически;
• инструкция SAVE TRANSACTION позволяет создать внутри транзакции точку сохранения и присвоить сохраненному состоянию имя точки сохранения, указанное в инструкции;
• инструкция ROLLBACK отменяет выполнение текущей транзакции и возвращает БД к состоянию, где была выполнена инструкция SAVE TRANSACTION (если в инструкции указана точка сохранения – ROLLBACK TO имя_точки_сохранения), или к состоянию начала транзакции.

49. Характеристики проводных линий связи (Ира)

50. Инструментальные средства проектирования АСОИУ

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

При разработке АСОИУ организационными объектами преимущественно используются так называемые CASE-средства (Computer Aided Software Engineering). Это программные средства, поддерживающие анализ и формулировку требований к системе, проектирование программного обеспечения и баз данных, тестирование, документирование и управление проектами. Большинство существующих CASE-средств применяют методологию структурного или объектно-ориентированного анализа и проектирования и представляют собой интегрированные системы из отдельных CASE- компонентов.

В качестве CASE-компонентов выступают:

– репозитарий (специальным образом организованное хранилище различных версий проектов);

– графические средства анализа и проектирования, обеспечивающие создание и редактирование иерархически взаимосвязанных диаграмм;

– средства разработки программ

– средства тестирования;

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

– средства управления проектом;

– средства интеграции с наиболее известными базами данных.

Примерами развитых CASE-систем могут служить система ERWIN, предназначенная для автоматизации проектирования баз данных и семейство объектно-ориентированных CASE-средств Rational Rose (RR), которые основаны на использовании языка моделирования UML. Система RR может генерировать коды разрабатываемых программ на языках С++, Small Talk, Java и ряде других. Кроме того, RR имеет средства для разработки проектной документации в виде диаграмм и спецификаций, а также имеет средства для реверсного инжиниринга программ. В состав RR входят следующие компоненты:

– репозитарий;

– графический интерфейс пользователя;

– средства просмотра проекта;

– средства контроля проекта;

– средства сбора статистики;

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

– средства генерации кода программ;

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

Разработка баз данных в ERWIN состоит из двух этапов: этапа составления логической модели базы данных и этапа разработки на ее основе физической модели базы данных. Логическая модель означает прямое описание фактов проблемной области задач АСОИУ, то есть реальных объектов этой области и их связей. Объекты именуются на естественном языке, при этом не указываются типы данных (например, целое, вещественное и так далее) и не рассматривается использование конкретной СУБД. Конкретная СУБД, ее таблицы и типы данных составляют физическую модель. ERWIN поддерживает ряд СУБД, таких как Microsoft SQL, Oracle, Sybase, Microsoft Access, FoxPro, INFORMIX и многие другие.

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

– работа в режиме реального времени;

– избыточность информации;

– сетевая архитектура открытых систем;

– модульность исполнения.

Современные SCADA-системы, и выполняют следующие функции:

· прием информации о контролируемых параметрах управляемых объектов;

· сохранение информации;

· обработка принятой информации;

· графическое представление хода технологического процесса;

· прием и передача команд оператора;

· регистрация событий;

· оповещение персонала об аварийных ситуациях;

· формирование сводок и других отчетов;

· обмен информацией с автоматизированной системой управления предприятием.

51. Язык SQL (Нурсиня)

52. Многокритериальные задачи

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

Формально М. з. задается множеством X «допустимых решений» и набором целевых функций на {X}, принимающих действительные значения. Сущность М. з. состоит в нахождении оптимального ее решения, т.е. такого , к-рое в том или ином смысле максимизирует значения всех функций Существование решения, буквально максимизирующего все целевые функции, является редким исключением. Поэтому в теории М. з. понятие оптимальности получает различные и притом нетривиальные истолкования. Содержание теории М. з. состоит в выработке таких концепций оптимальности, доказательстве их реализуемости (т. е. существования оптимальных в соответствующем смысле решений) и нахождении этих реализаций (т. е. в фактич. решении задачи).

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

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

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

53. Иерархическая модель данных

Иерархическая модель данных — это модель данных, где используется представление базы данных в виде древовидной (иерархической) структуры, состоящей из объектов (данных) различных уровней.

Организация данных в СУБД иерархического типа определяется в терминах: элемент, агрегат, запись (группа), групповое отношение, база данных.

Атрибут (элемент данных) – наименьшая единица структуры данных. Обычно каждому элементу при описании базы данных присваивается уникальное имя. По этому имени к нему обращаются при обработке. Элемент данных также часто называют полем.

Запись – именованная совокупность атрибутов. Использование записей позволяет за одно обращение к базе получить некоторую логически связанную совокупность данных. Именно записи изменяются, добавляются и удаляются. Тип записи определяется составом ее атрибутов. Экземпляр записи - конкретная запись с конкретным значением элементов

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

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

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

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

54. Спутниковые каналы связи (Ваня Семенов)

55. Типизация проектных решений АСОИУ (свободен)

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

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

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

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

Рис. 3.1. Подходы к построению АСОИП

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

2) Заказные системы. При данном подходе вы заказываете разработку АСОИП, как, например, заказывают нестандартную мебель. Это второй исторически сложившийся подход к построению АСОИП. В «чистом виде» он предполагает разработку системы, полностью соответствующей особенностям конкретного предприятия, что и является его основным преимуществом. В потенциале этот подход характеризуется сравнительно меньшей стоимостью и меньшими сроками реализации, чем самостоятельная разработка.