- •Структуры и алгоритмы обработки данных
- •Логическая и физическая структуры данных
- •Классификация структур данных
- •Основные операции над структурами данных
- •Алгоритм и примеры задач, решаемых с помощью алгоритмов
- •Адресация и распределение памяти
- •Адресные пространства и модели оперативной памяти
- •Формирование физического адреса в реальном режиме
- •Особенности адресации в защищенном режиме
- •Кэширование
- •Анализ алгоритмов
- •Быстродействие – основной показатель эффективности алгоритма
- •Подсчет числа простейших операций
- •Лучший, средний и худший случаи
- •Алгоритмы и платформы
- •Виртуализация памяти
- •Использование кэша
- •Выравнивание данных
- •Рандомизированные алгоритмы
- •Общая характеристика записей и способы описания в Delphi
- •Многоуровневые записи
- •Выравнивание и упакованные записи
- •Записи с вариантной частью
- •Массивы
- •Общая характеристика массивов
- •Статические (стандартные) массивы
- •Многомерные статические массивы
- •Свойства статических массивов
- •Открытые массивы
- •Динамические массивы
- •Динамические векторы
- •Многомерные динамические массивы
- •Массивы типа Variant
- •Вставка и удаление в массиве
- •Связные списки и алгоритмы их обработки
- •Списки и их разновидности
- •Односвязный список
- •Общая характеристика односвязного списка
- •Структура элемента односвязного списка
- •Формирование односвязного списка
- •Просмотр односвязного списка
- •Вставка элемента в односвязный список
- •Удаление элемента из односвязного списка
- •Линейный двухсвязный список
- •Структура элемента двухсвязного списка
- •Реализация операций в линейном двухсвязном списке
- •Нелинейный двухсвязный список
- •Нелинейный трехсвязный список
- •Определение плекса и его общие признаки
- •Иерархическая списковая структура. Сетевая структура
- •Достоинства и недостатки связных списков
- •Функциональные и свободные списки
- •Общая характеристика функционального и свободного списка
- •Методы формирования свободного списка
- •Стеки, очереди, деки и операции в них
- •Общая характеристика
- •Очередь
- •Динамические множества и словари
- •Общая характеристика
- •Операции в динамических множествах
- •Деревья
- •Общая характеристика и некоторые определения
- •Представление дерева в памяти
- •Естественное представление дерева
- •Представление дерева с помощью вектора
- •Представление дерева с использованием списков сыновей
- •Методы обхода деревьев
- •Бинарное дерево
- •Структура бинарного дерева
- •Формирование бинарного дерева
- •Обход бинарного дерева
- •Преобразование любого дерева к бинарному дереву
- •Включение и исключение в дереве
- •Включение в дереве
- •Исключение в дереве
- •Поиск: определение и общая терминология
- •Линейный (последовательный) поиск
- •Последовательный поиск в упорядоченной таблице
- •Последовательный поиск при накоплении запросов
- •Индексно-последовательный поиск
- •Бинарный поиск
- •Поиск, использующий бинарное дерево
- •Сортировка
- •Общие сведения и некоторые определения
- •Внутренняя сортировка
- •Сортировка прямыми включениями
- •Сортировка бинарными включениями
- •Сортировка прямым выбором
- •Сортировка прямым обменом
- •Сортировка методом Шелла
- •Сортировка с помощью бинарного дерева
- •Пирамидальная сортировка
- •Быстрая сортировка разделением
- •Внешняя сортировка
- •Сортировка прямым слиянием
- •Сортировка естественным слиянием
- •Сортировка многопутевым слиянием
- •Многофазная сортировка
- •Хеширование и хеш-таблицы
- •Общие сведения и определения
- •Коллизии при хешировании
- •Разрешение коллизий при хешировании
- •Разрешение коллизий методом открытой адресации
- •Разрешение коллизий методом цепочек
- •Функции хеширования
- •Поисковые деревья
- •Бинарное дерево поиска
- •Структура бинарного дерева поиска и алгоритм поиска
- •Вставка элемента в бинарное дерево поиска
- •Удаление из бинарного дерева поиска
- •Красно-черные деревья
- •Определение красно-черного дерева, структура его элементов
- •Повороты
Формирование физического адреса в реальном режиме
Для формирования адреса в реальном режиме используется два компонента – сегмент адреса и смещение адреса, а сам адрес принято записывать парой этих значений, разделенных двоеточием:
segment : offset,
например, $0051:06А5 (здесь символ $ обозначает, что следующая за ним последовательность символов, кроме двоеточия, является шестнадцатеричным кодом). Значение «segment» хранится в специальном 16-битном сегментном регистре микропроцессора, а смещение «offset» — помещается в один из 16-битных регистров общего назначения (РОН). Физический адрес формируется на аппаратном уровне следующим образом:
значение 16-битового сегмента адреса сдвигается влево на 4 двоичных разряда (бита) с заполнением разрядов справа нулями; в результате получается 20-битовое значение;
к полученному 20-битовому значению прибавляется смещение, а значение суммы передается на шину адреса в качестве физического адреса.
Получаемое значение физического адреса является 20-разрядным. Следовательно, с его помощью можно адресовать (т. е. получить доступ) 1 Мбайт (220 байт) оперативной памяти. Здесь можно отметить несоответствие размеров шины адреса современных микропроцессоров (32 или 36 бит) и 20-битного значения физического адреса реального режима. Пока микропроцессор находится в реальном режиме, старшие 12 (или 16) линий шины адреса попросту недоступны.
Как известно, сдвиг двоичного числа на 4 битов влево (или, что то же самое, сдвиг шестнадцатеричного кода на одну шестнадцатеричную позицию влево) эквивалентен умножению этого числа на 24 = 16. Следовательно, физический адрес А определяется формулой
А = 16 segment + offset.
Величину 16segment часто называют базой сегмента или просто базой, а схему формирования адреса обозначают термином «база-смещение». Эта схема иллюстрируется рисунком 2.1.
Рисунок 2.1 – Формирование физического адреса в реальном режиме
Особенности адресации в защищенном режиме
Защищенный режим работы позволяет использовать все возможности, предоставляемые современным микропроцессором. Все современные многозадачные операционные системы работают только в этом режиме.
Реальный режим поддерживает выполнение всего одной программы. Для этого достаточно простых механизмов распределения оперативной памяти и нет потребности в организации защиты программы от влияния других программ. Все, что нужно знать программе, это адреса, по которым располагаются сегменты кода, данных и стека. Если возникает потребность в размещении в программно-аппаратной среде нескольких независимых программ, то автоматически встает вопрос об их защите от взаимного влияния. И процессор переходит в защищенный режим работы.
В отличие от реального режима, в защищенном режиме программа уже не может запросто обратиться по любому физическому адресу. В защищенном режиме используется виртуализация памяти (страничная модель). Каждой загруженной программе (задаче, процессу) операционная система выделяет 4 Гбайт виртуальной памяти, которая состоит из сегментов различного назначения и с разными правами доступа. Сегмент может иметь почти произвольный размер до 4 Гбайт, в отличие от сегмента реального режима, который не превышает 64 Кбайт. Из одних сегментов можно только читать данные, в другие возможна и запись.
Ключевым объектом защищенного режима является специальная структура – дескриптор сегмента, содержащий краткое описание непрерывной области памяти, которая может являться сегментом кода, данных или стека. Все дескрипторы программ, выполняемых в текущий момент, собираются в одну из трех дескрипторных таблиц.
Для программного кода выделяются специальные сегменты, команды могут выбираться и исполняться только из них. Процессору «безразлично» содержимое ячейки памяти, которой передается управление, он всегда пытается трактовать ее как код команды. Если ошибочно управление передалось на сегмент данных, то сработает защита и ошибочный процесс будет завершен.
Виртуальная логическая память, адресуемая программой в пределах выделенных ей сегментов, разбивается на страницы. В системах Win32 с процессорами Pentium размер одной страницы составляет 4 Кбайт, следовательно, Win32 разбивает блок памяти 4 Гбайт на страницы по 4 Кбайт. При этом в каждой странице содержится небольшой объем служебной информации, в частности, данные о том, занята страница или нет.
В служебную информацию страницы входит ссылка на таблицу перевода страниц. Эта таблица связывает отдельную виртуальную страницу программы с реальной страницей, доступной в ОЗУ. Таким образом операционная система выполняет перевод виртуального адреса в реальный (физический) адрес ОЗУ.
Если активировано несколько программ, то в физической оперативной памяти в каждый момент времени присутствует только часть виртуальных страниц. Остальные страницы хранятся на диске, откуда операционная система может «подкачать» их в физическую память, предварительно выгрузив на диск часть не используемых в данный момент страниц. Обращение процессора к ячейке виртуальной памяти, присутствующей в физической памяти, происходит обычным образом. Если затребованная область памяти в данный момент отсутствует в физической памяти, то операционная система организует замену страниц, называемую свопингом (swapping).