билет 3

Концепция последовательно-параллельных процессов при построении программных систем реального времени.

Концепция процесса

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

Понятие процесса тесно связано с понятием задача:

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

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

Следует отличать понятия процесс и задача от понятий программа и задание.

Программа (для ЭВМ) - упорядоченная последовательность команд, подлежащих обработке.

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

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

Об отношении процесса и программы можно сказать, что процесс - это программа во время ее выполнения. Всякая программа становится процессом, когда начинает выполняться в ЭВМ.

В период своего существования процесс может находиться в одном из следующих основных состояний (рис.2.1):

порождение, во время которого подготавливаются условия для первого исполнения на центральном процессоре;

активное состояние (выполнение), когда процессу принадлежит центральный процессор;

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

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

ресурсы процессу больше не предоставляются.

Граф существования процесса

Порождение Готовность Активность Ожидание

Окончание

Рис.2.1.

Возможно также представление переходов между состояниями в таблицы - так называемой матрицей смежностей графа (см. табл.2.1).

Таблица 2.1.

Матрица существования процесса

Для построения средств управления процессами необходимо знать их свойства и классифицировать процессы в соответствии с этими свойствами (см. табл.2.2).

Таблица 2.2.

Классификация процессов

Вопрос 2

Математическое моделирование баз данных. Реляционная, Иерархическая, сетевая модель данных. Реляционная алгебра.

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

Основные задачи:

Обеспечение хранения в БД всей необходимой информации.

Обеспечение возможности получения данных по всем необходимым запросам. Сокращение избыточности и дублирования данных.

Обеспечение целостности базы данных. Концептуальное (инфологическое) проектирование

Концептуальное (инфологическое) проектирование — построение семантической модели предметной области, то есть информационной модели наиболее высокого уровня абстракции. Такая модель создаётся без ориентации на какую-либо конкретную СУБД и модель данных. Термины «семантическая модель», «концептуальная

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

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

Чаще всего концептуальная модель базы данных включает в себя:

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

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

Логическое (даталогическое) проектирование

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

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

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

Физическое проектирование

Физическое проектирование — создание схемы базы данных для конкретной СУБД.

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

Реляционная модель данных (РМД) — логическая модель данных,

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

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

Структурный аспект (составляющая) — данные в базе данных представляют собой набор отношений.

Аспект (составляющая) целостности — отношения (таблицы) отвечают определенным условиям целостности. РМД поддерживает декларативные ограничения целостности уровня домена (типа данных), уровня отношения и уровня базы данных.

Аспект (составляющая) обработки (манипулирования) — РМД поддерживает операторы манипулирования отношениями (реляционная алгебра, реляционное исчисление).

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

Термин «реляционный» означает, что теория основана на математическом

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

Для лучшего понимания РМД следует отметить три важных обстоятельства:

модель является логической, то есть отношения являются логическими (абстрактными), а не физическими (хранимыми) структурами; для реляционных баз данных верен информационный принцип: всё информационное

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

программирование и декларативное описание ограничений целостности, в дополнение

к навигационному (процедурному) программированию и процедурной проверке условий.

Принципы реляционной модели были сформулированы в 1969—1970 годах Э. Ф. Коддом (E. F. Codd). Идеи Кодда были впервые публично изложены в статье «A Relational Model of Data for Large Shared Data Banks»[1], ставшей классической.

Строгое изложение теории реляционных баз данных (реляционной модели данных) в современном понимании можно найти в книге К. Дж. Дейта. «C. J. Date. An Introduction to Database Systems» («Дейт, К. Дж. Введение в системы баз данных»).

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

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

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

Первые системы управления базами данных[уточнить] использовали иерархическую модель

данных.[источник не указан 170 дней]

Структурная часть иерархической модели

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

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

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

Управляющая часть иерархической модели

В рамках иерархической модели выделяют языковые средства описания данных (ЯОД) и средства манипулирования данными (ЯМД). Каждая физическая база описывается набором операторов, обусловливающих как её логическую структуру, так и структуру хранения БД. При этом способ доступа устанавливает способ организации взаимосвязи физических записей.