Сегментное распределение памяти.
При страничной организации виртуальное адресное пространство процесса делится механически на равные части. Это не позволяет дифференцировать способы доступа к разным частям программы (сегментам), а это свойство часто бывает очень полезным. Например, можно запретить обращаться с операциями записи и чтения в кодовый сегмент программы, а для сегмента данных разрешить только чтение. Кроме того, разбиение программы на "осмысленные" части делает принципиально возможным разделение одного сегмента несколькими процессами.
При сегментном распределении виртуальное адресное пространство процесса делится на сегменты, размер которых определяется программистом с учетом смыслового значения содержащейся в них информации. Отдельный сегмент может представлять собой подпрограмму, массив данных и т.п.
При загрузке процесса часть сегментов помещается в оперативную память (при этом для каждого из этих сегментов операционная система подыскивает подходящий участок свободной памяти), а часть сегментов размещается в дисковой памяти. Сегменты одной программы могут занимать в оперативной памяти несмежные участки. Во время загрузки система создает таблицу сегментов процесса (аналогичную таблице страниц), в которой для каждого сегмента указывается начальный физический адрес сегмента в оперативной памяти, размер сегмента, правила доступа, признак модификации, признак обращения к данному сегменту за последний интервал времени и некоторая другая информация.
Система с сегментной организацией функционирует аналогично системе со страничной организацией: время от времени происходят прерывания, связанные с отсутствием нужных сегментов в памяти, при необходимости освобождения памяти некоторые сегменты выгружаются, при каждом обращении к оперативной памяти выполняется преобразование виртуального адреса в физический. Кроме того, при обращении к памяти проверяется, разрешен ли доступ требуемого типа к данному сегменту.
Недостатком данного метода распределения памяти является фрагментация на уровне сегментов.
Сегментно-страничное распределение.
Виртуальное пространство процесса делится на сегменты, а каждый сегмент в свою очередь делится на виртуальные страницы, которые нумеруются в пределах сегмента. Оперативная память делится на физические страницы. Загрузка процесса выполняется операционной системой постранично, при этом часть страниц размещается в оперативной памяти, а часть на диске. Для каждого сегмента создается своя таблица страниц, структура которой полностью совпадает со структурой таблицы страниц, используемой при страничном распределении. Для каждого процесса создается таблица сегментов.
БАЗЫ ДАННЫХ.
База данных. СУБД.
База данных (БД) – совокупность специальным образом организованных данных, хранимых в памяти вычислительной системы и отражающая состояние объектов и их взаимосвязей в рассматриваемой предметной области. Логическую структуру данных называют моделью представления данных.К основным моделям представления данных относятся: иерархическая, сетевая, реляционная, объектно-ориентированная.
Система управления базами данных (СУБД) –совокупность программных средств, предназначенная для создания, сопровождения и совместного использования БД. Обычно СУБД различают по используемой модели данных. Также может выполнять функции словаря данных (хранение, защиту данных, ограничение доступа, связи и т.п.).
С точки зрения пользователя, СУБД реализует функции хранения, изменения (пополнения, редактирования и удаления) и обработки информации, а также разработки и получения различных выходных документов.
Основные функции СУБД:
1) Обеспечение зависимости данных и приложений (Все СУБД предоставляют программистам API для работы с БД без учета физического размещения элементов данных (например, SQL для реляционных БД)).
2) Обеспечение безопасности данных
3) Управление параллельным доступом (разграничение операций чтения и редактирования данных при одновременном доступе к базе)
4) Ведение журнала транзакций (для восстановления данных в случае сбоев и ошибочных операций)
5) Поддержка целостности БД
6) Обеспечение доступа к данным
Механизм транзакций используется в СУБД для поддержания целостности данных в базе. Транзакцией называется некоторая неделимая последовательность операций над данными БД, которая отслеживается СУБД от начала до конца. Если по каким-либо причинам транзакция окажется незавершенной, то она отменяется.
Классификация СУБД:
1) По модели данных:
§ Иерархические;
§ Сетевые;
§ Реляционные;
§ Объектно-ориентированные;
2) По степени распределенности:
§ Локальные СУБД (все части СУБД располагаются на одном компьютере)
§ Распределенные СУБД (части СУБД могут размещаться на одном и более компьютеров);
3) По способу доступа к БД:
§ Файл-серверные (Microsoft Access, Paradox, Visual FoxPro). Данные, СУБД целиком располагаются на сервере.
§ Клиент-серверные (Oracle, IBM DB2, MS SQL Server, PostgreSQL, MySQL)
§ Встраиваемые (SQLite, Microsoft SQL Server Compact). Как составная часть некоторого программного продукта, не требуя процедуры самостоятельной установки.
Модели данных.
Модель данных — это определение объектов, операторов и прочих элементов, в совокупности составляющих абстрактную машину доступа к данным, с которой взаимодействует пользователь. Таким образом, конкретная модель данных отражает структуру данных и способы взаимодействия с ними.
Каждая БД и СУБД строится на основе некоторой явной или неявной модели данных. Все СУБД, построенные на одной и той же модели данных, относят к одному типу.
Наиболее известными являются модели данных:
1) Иерархическая модель
2) Сетевая модель
3) Реляционная модель
4) Объектно-ориентированная модель
В иерархической модели связи между данными можно описать в виде упорядоченного графа (или дерева).
Иерархическая база данных представляет собой упорядоченную совокупность экземпляров данных типа «дерево», содержащих экземпляры типа «запись». Поля записей хранят собственно числовые или символьные значения, составляющие основное содержание базы данных.
Основное правило контроля целостности формулируется следующим образом: потомок не может существовать без родителя, а у некоторых родителей может не быть потомков.
К достоинствам иерархической модели относятся эффективное использование памяти ЭВМ и неплохие показатели времени выполнения основных операций над данными. Иерархическая модель удобна для работы с иерархически упорядоченной информацией.
Недостатком является громоздкость иерархической модели для обработки информации с достаточно сложными логическими связями, а также сложность понимания для обычного пользователя.
Можно сказать, что иерархической БД является файловая система, состоящая из корневой директории, в которой имеется иерархия поддиректорий и файлов.
Сетевая модель данных позволяет отображать различные взаимосвязи элементов в виде произвольного графа, обобщая тем самым иерархическую модель. Сетевая БД состоит из набора записей и связей. Особых ограничений на связи не накладывается.
Достоинства: эффективное использование памяти, скорость. В сравнении с иерархической моделью сетевая модель предоставляет большие возможности в смысле допустимости образования произвольных связей.
Недостаткисетевой модели: высокая сложность и жёсткость схемы базы данных, построенной на основе, а также слабый контроль целостности вследствие допустимости установления произвольных связей между записями.
Реляционная модель основывается на понятии отношение. Отношение представляет собой множество элементов, называемых кортежами. Наглядной формой представления отношения является привычная двумерная таблица. Таблица имеет строки (записи) и столбцы (колонки). Достоинства: простота, понятность и удобство. Недостатки: неэффективное использование памяти, меньшая скорость сложность описания иерархических и сетевых связей.
Объектно-ориентированная модель. В объектно-ориентированной модели при представлении данных имеется возможность идентифицировать отдельные записи базы данных. Между записями базы данных и функциями их обработки устанавливаются взаимосвязи с помощью механизмов, подобных соответствующим средствам в объектно-ориентированных языках программирования.
Структура объектно-ориентированной базы данных представима в виде дерева, узлами которого являются объекты. Свойства объектов описываются некоторым стандартным типом или типом, конструируемым пользователем (определяется как class).
Каждый объект – экземпляр класса принадлежит своему классу и имеет одного родителя. Родовые отношения в базе данных образуют связную иерархию объектов.
Основным достоинством объектно-ориентированной модели в сравнении с реляционной является возможность отображения информации о сложных взаимосвязях объектов. Объектно-ориентированная модель позволяет идентифицировать отдельную запись базы данных и определять функции их обработки.
Недостатками являются высокая понятийная сложность, неудобство обработки данных и низкая скорость выполнения запросов.
5.3. Реляционная модель данных.
| Номер пропуска | Фамилия | Имя | Отчество | Дата рождения |
| Романова | Валентина | Петровна | 12.01.1980 | |
| Пирогов | Василий | Иванович | 25.03.1975 | |
| …… | …… |
Реляционная модель опирается на систему понятий, важнейшие из которых: отношение, сущность, атрибут, домен, кортеж, первичный ключ, внешний ключ.
Все операции над реляционной базой данных сводятся к манипуляциям с таблицами. Таблица состоит из строк и столбцов и имеет имя, уникальное внутри базы данных. Таблица отражает тип объекта реального мира (сущность), а каждая ее строка - конкретный объект. Строки таблицы называются также кортежами. Таблица "Сотрудники отдела" содержит, например, сведения обо всех сотрудниках отдела, каждая ее строка - набор значений атрибутов конкретного сотрудника. Значения конкретного атрибута выбираются из домена – множества всех возможных значений атрибута объекта. Имя столбца должно быть уникальным в таблице. Столбцы расположены в таблице в соответствии с порядком следования их имен при ее создании. Любая таблица должна иметь по крайней мере один столбец. В отличие от столбцов строки не имеют имен. Порядок следования строк в таблице не определен, а количество логически не ограничено. Так как строки в таблице не упорядочены, невозможно выбрать строку по ее позиции - среди них не существует "первой" и "последней".
Любая таблица имеет один или несколько столбцов, значения в которых однозначно идентифицируют каждую ее строку. Такой столбец (или комбинация столбцов) называется первичным ключом. В таблице "Сотрудники отдела" первичным ключом служит столбец "Номер пропуска". В таблице не должно быть строк, имеющих одно и то же значение первичного ключа. Если таблица удовлетворяет этому требованию, она называется отношением.
Взаимосвязь таблиц в реляционной модели поддерживается внешними ключами. Внешним ключом называется поле таблицы, предназначенное для хранения значения первичного ключа другой таблицы с целью организации связи между этими таблицами.
Нормальные формы.
Нормальная форма — свойство отношения в реляционной модели данных, характеризующее его с точки зрения избыточности, которая потенциально может привести к логически ошибочным результатам выборки или изменения данных. Нормальная форма определяется как совокупность требований, которым должно удовлетворять отношение.
Процесс преобразования базы данных к виду, отвечающему нормальным формам, называется нормализацией. Нормализация предназначена для приведения структуры базы данных к виду, обеспечивающему минимальную избыточность, то есть нормализация не имеет целью уменьшение или увеличение производительности работы или же уменьшение или увеличение объёма БД. Конечной целью нормализации является уменьшение потенциальной противоречивости хранимой в БД информации (каждый неключевой атрибут встречается в отношениях по одному разу). Нормализация осуществляется путем разбиения отношения на 2 или более таким образом, чтобы в каждом отношении хранились только первичные факты (то есть факты, не выводимые из других хранимых фактов).
Процесс проектирования БД с использованием метода нормальных форм является итерационным и заключается в последовательном переводе отношения из первой нормальной формы в нормальные формы более высокого порядка по определенным правилам. Каждая следующая НФ ограничивает определенный тип функциональных зависимостей, устраняет соответствующие аномалии при выполнении операций над отношениями БД и сохраняет свойства предшествующих НФ.
Основные нормальные формы:
1) Первая нормальная форма.
Отношение находится в первой нормальной форме (1НФ) тогда и только тогда, когда в любом допустимом значении отношения каждый его кортеж содержит только одно значение для каждого из атрибутов.
В реляционной модели отношение всегда находится в первой нормальной форме по определению понятия отношение.
Вторая нормальная форма.
Отношение находится во второй нормальной форме (2НФ), если оно находится в первой нормальной форме, и при этом любой его неключевой атрибут функционально полно зависит от ключа. Таким образом, во 2НФ нет неключевых атрибутов, зависящих от части составного потенциального ключа.
Пример:
Отношение ПОСТАВКИ (N_ПОСТАВЩИКА, ТОВАР, ЦЕНА).
Поставщик может поставлять различные товары, а один и тот же товар может поставляться разными поставщиками. Тогда ключ отношения – <N_ПОСТАВЩИКА, ТОВАР>. Пусть все поставщики поставляют товар по одной и той же цене. Тогда имеем следующие функциональные зависимости:
<N_ПОСТАВЩИКА, ТОВАР> ЦЕНА
ТОВАР à ЦЕНА
Неполная функциональная зависимость атрибута "цена" от ключа приводит к следующей аномалии: при изменении цены товара необходим полный просмотр отношения для того, чтобы изменить все записи о его поставщиках. Данная аномалия является следствием того факта, что в одной структуре данных объединены два семантических факта.
Следующее разложение дает отношения во 2НФ:
ПОСТАВКИ (N_ПОСТАВЩИКА, ТОВАР)
ЦЕНА_ТОВАРА (ТОВАР, ЦЕНА)
Третья нормальная форма.
Отношение находится в 3НФ тогда и только тогда, когда оно находится во 2НФ и в нем отсутствуют транзитивные зависимости неключевых атрибутов от ключевых. Транзитивной зависимостью неключевых атрибутов от ключевых называется следующая: {A} → {B} и {B} → {C}, где {A} — потенциальный ключ, {B} и {С} — различные множества неключевых атрибутов. Таким образом, отношение в 3НФ содержит только такие неключевые атрибуты, которые находятся в прямой зависимости от ключевых атрибутов.
Пример:
Отношение (ГРУППА, СЕЦИАЛЬНОСТЬ, ФАКУЛЬТЕТ)
ГРУППАàСПЕЦИАЛЬНОСТЬ
СЕЦИАЛЬНОСТЬàФАКУЛЬТЕТ
После нормализации:
(ГРУППА, СПЕЦИАЛЬНОСТЬ),
(СПЕЦИАЛЬНОСТЬ, ФАКУЛЬТЕТ).
На практике приведение отношения к 3НФ оказывается достаточным и процесс нормализации на этом заканчивается. Избыточная нормализация может существенно усложнить запросы к базе данных и ее структуру, тем самым понизить ее эффективность.
5.5. Физическая организация данных.
Физические модели баз данных определяют способы размещения данных в среде хранения и способы доступа к этим данным, которые поддерживаются на физическом уровне.
В каждой СУБД по-разному организованы хранение и доступ к данным, однако существуют некоторые файловые структуры, которые имеют общепринятые способы организации и широко применяются практически во всех СУБД.
В системах баз данных файлы и файловые структуры, которые используются для хранения информации во внешней памяти, можно классифицировать следующим образом:
Файлы с прямым доступом обеспечивают наиболее быстрый способ доступа. Мы не всегда можем хранить информацию в виде файлов прямого доступа, но главное – это то, что доступ по номеру записи в базах данных весьма неэффективен. Чаще всего в базах данных необходим поиск по первичному или возможному ключам, иногда необходима выборка по внешним ключам, но во всех этих случаях мы знаем значение ключа, но не знаем номера записи, который соответствует этому ключу.
В подобных случаях применяют различные методы хэширования и создают специальные хэш- функции. Несмотря на высокую эффективность хэш-адресации, в файловых структурах далеко не всегда удается найти соответствующую функцию, с помощью которой можно было бы полностью избежать коллизий, поэтому при организации доступа по первичному ключу широко используются индексные файлы.
Индексные фaйлы можно представить как файлы, состоящие из двух частей: индексной области и области данных файла (записи БД). В зависимости от организации индексной и основной областей различают 2 типа файлов: с плотным индексом и с неплотным индексом.
В файлах с плотным индексом основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а индексная запись состоит из значения ключа и номера записи:
Здесь значение ключа - это значение первичного ключа, а номер записи - это порядковый номер записи в основной области, которая имеет данное значение первичного ключа.
Неплотный индекс строится именно для упорядоченных файлов. Для этих файлов используется принцип внутреннего упорядочения для уменьшения количества хранимых индексов. Структура записи индекса для таких файлов состоит из значения ключа первой записи блока и номера блока с этой записью.
В индексной области мы теперь ищем нужный блок по заданному значению первичного ключа. Так как все записи упорядочены, то значение первой записи блока позволяет нам быстро определить, в каком блоке находится искомая запись. Все остальные действия происходят в основной области.
Для обеспечения быстрого доступа к данным на запоминающих устройствах в современных БД используются древовидные структуры данных, хранящиеся во внешней памяти, такие, как B-деревья.
Построение В-деревьев связано с простой идеей построения индекса над уже построенным индексом. В общем случае получим некоторое дерево, каждый родительский блок которого связан с одинаковым количеством подчиненных блоков, число которых равно числу индексных записей, размещаемых в одном блоке. Количество обращений к диску при этом для поиска любой записи одинаково и равно количеству уровней в построенном дереве. Такие деревья называются сбалансированными (balanсed) именно потому, что путь от корня до любого листа в этом древе одинаков.
КОМПЬЮТЕРНАЯ ГРАФИКА.
6.1. Растровые (матричные) изображения.
Для представления графической информации на двумерной плоскости (например, экране монитора, странице книги и т.п.) в вычислительной технике применяются два основных подхода: растровый и векторный.
При векторном подходе графическая информация описывается как совокупность неких абстрактных геометрических объектов, таких как прямые, отрезки, кривые, прямоугольники и т.п.
Растровая графика же оперирует растровыми изображениями. Растровое изображение — изображение, представляющее собой матрицу пикселей или цветных точек (обычно прямоугольную).
Важными характеристиками изображения являются:
1) количество пикселей — разрешение. Может указываться отдельно количество пикселей по ширине и высоте (1024*768, 640*480,…) или же, редко, общее количество пикселей (часто измеряется в мегапикселях). При этом следует различать: разрешение оригинала; разрешение экранного изображения; разрешение печатного изображения;
2) количество используемых цветов или глубина цвета;
3) цветовое пространство (цветовая модель) RGB, CMYK и др.
По количеству цветов изображения могут быть:
§ Двухцветные (бинарные) – 1 бит на пиксел. Среди двухцветных чаще всего встречаются черно–белые изображения;
§ Полутоновые – градации серого или иного цвета. Например, 256 градаций (1 байт на пиксел);
§ Цветные изображения. От 2 бит на пиксел и выше. Глубина цвета 16 бит на пиксел (65 536 цветов) получила название High Со1ог,24 бит на пиксел (16,7 млн цветов) – True Со1ог.В компьютерных графических системах используют и большую глубину цвета – 32, 48 и более бит на пиксел.
Цвет любого пиксела растрового изображения запоминается с помощью комбинации битов. Чем больше битов для этого используется, тем больше оттенков цветов можно получить. Под градацию яркости обычно отводится 1 байт (256 градаций), причем 0 – черный цвет, а 255 – белый (максимальная интенсивность).
Растр – это порядок расположения точек (растровых элементов). Растр, элементами которого являются квадраты, называется прямоугольным, именно такие растры наиболее часто используются.
Растровое представление является естественным в тех случаях, когда нам не известна дополнительная информация об изображаемых объектах (например, цифровым фотоаппаратом можно снимать изображения произвольного содержания).
Достоинства растровых изображений:
§ Распространённость — растровая графика используется сейчас практически везде: от маленьких значков до плакатов.
§ Высокая скорость обработки сложных изображений, если не нужно масштабирование.
§ Растровое представление изображения естественно для большинства устройств ввода-вывода графической информации, таких как мониторы, матричные и струйные принтеры, цифровые фотоаппараты, сканеры.
Недостатки растровых изображений:
§ Большой размер файлов с простыми изображениями;
§ Невозможность идеального масштабирования;
§ Невозможность вывода на печать на плоттер.
Первым растровым стандартом был PCX (Z-Soft). Он получил широкое распространение для обмена монохромными моделями. Также он поддерживает 24-цветную и 256-цветную модель представления цвета. В отличие от других растровых стандартов, цветовая палитра данного стандарта записывается в конце файла.
Сжатие растро-информации происходит следующим образом: сначала идет байт с количеством пикселов с повторяющимся цветом. Далее – байт с цветом. Такой алгоритм эффективен для хранения черно-белого изображения (коэффициент сжатия может быть до 10% максимально).
Итак, достоинства данного стандарта:
· Это первый растровый стандарт
· Эффективный алгоритм хранения черно-белого изображения
А недостатком стандарта является недостаточное качество цветного изображения, и для цветных изображений большой размер растра.
Следующий растровый стандарт - BMP. Битовый образ памяти Windows. Алгоритм сжатия растра отсутствует (1:1). Так как существует много графических видеоадаптеров и графических режимов, то стандарт BMP может быть не отражен для конкретного монитора и конкретного графического режима. Достоинство стандарта – его простота. Недостаток – большой объем и невозможность отображения вида.
TIF (Microsoft). Это стандарт для обмена растровыми изображениями. Может работать с любой цветовой моделью. Используется для ввода изображения со сканера. Но есть недостаток данного стандарта – это множество версий и невозможность понимания одной версии другой.
GIF - Это стандарт для хранения растровых изображений с большим количеством цветов. Изображения хранятся в нескольких цветовых слоях за счет отдельного хранения различных картинок (эффект анимации). Итак, “плюсом” данного стандарта является возможность хранения высококачественного графического изображения. А “минусом” – средняя степень сжатия информации.
JPEG. Это растровый стандарт для хранения изображения с большим количеством цветов и высоким коэффициентом сжатия. Алгоритм сжатия следующий. Для каждой перекрывающейся области подсчитывается средний цвет. И в растре хранится именно средний цвет. Чем выше коэффициент сжатия, тем больше элементарная растровая область. При каждом сохранении средний цвет для области пересчитывается вновь. В конце концов, можно получить серую картинку. Следовательно, данный стандарт подходит для передачи, а не для хранения растрового изображения.
Достоинство стандарта – высокий коэффициент сжатия.
Недостаток – потеря качества при сжатии.
CDR - Это растровый стандарт для хранения многоцветных изображений фирмы Kodak. То есть для хранения профессиональных высококачественных изображений Алгоритм сжатия незначительный. Достоинство – очень высокое качество. Недостаток – большие объемы файлов.
MAC. Это растровый стандарт для компьютера Макинтош. Раньше использовался для передачи изображений с платформы на платформу. Данный стандарт примерно аналогичен стандарту TIF, но не имеет множество версий. “Плюс” стандарта – возможность передачи на другие платформы, а “минус” средние показатели по качеству и степени сжатия.