Билет 25.

1. Поиск информации в бд с использованием структуры типа «бинарное дерево».

Бин. дерево – степень которого = 2. Пример:

Ст-т	Балл							Правила построения бинарного дерева: Левая вершина – меньше. Правая вершина – больше. Корень – середина. Узел – середина от половины.
В	?				К
И	?
К	?			И		С
П	?
С	?		В		П		Т
Т	?

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

В структуре дерева выносится только та информация, которая содержится в индексных файлах.

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

2. Поддержка мультизадачности в микропроцессорах i486+. Использование сегмента состояния задачи.

МУЛЬТИЗАДАЧНОСТЬ - такой способ организации работы вычислительной системы, при котором в ее памяти содержатся программы и данные для выполнения нескольких процессов обработки информации (задач). При этом должна обеспечиваться взаимная защита программ и данных, относящихся к разным задачам, а также возможность перехода от выполнения одной задачи к другой.

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

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

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

Основные моменты реализации многозадачного режима:

1 РАЗМЕЩЕНИЕ ИНФОРМАЦИИ В ОП - В мультизадачной среде одновременно работают несколько программ. Эти программы должны постоянно находиться в ОП или должен существовать эффективный механизм загрузки модулей в память и выгрузки измененой информации при переключении задач. Если памяти достаточно для размещения всей информации, то должен существовать механизм защиты; если памяти мало, то на диске отводится непрерывная область для временного хранения "ненужной" информации.

2 ПЕРЕКЛЮЧЕНИЕ ЗАДАЧ - Инициатором переключения может быть таймер, если истек отведенный интервал времени или сама программа при возникновении определенной ситуации (не подготовлены данные, требуется дополнительный сегмент памяти, ситуация оговоренная в условиях отладки...). При переключении должен быть сохранен контекст программы (регисты процессора, сопроцессора...), для обеспечения возможности дальнейшей работы.

3 ВЗАИМОДЕЙСТВИЕ ПРОГРАММ - Программы должны иметь возможность получать доступ к аппаратным ресурсам компьютера и обмениваться информацией между собой. Для решения вопроса синхронизации программ и использования ресурсов служит система семафоров и буферов устройств.

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

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

Сегмент состояния задачи.

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

Эти самостоятельные части и называются ЗАДАЧАМИ или процессами. По прерываниям от таймера процессор переключается от одной задачи к другой, и таким образом осуществляется параллельное выполнение программ.

Информация о состоянии процессора i286, необходимая для восстановления контекста задачи, хранится в специальной области памяти, называемой СЕГМЕНТОМ СОСТОЯНИЯ ЗАДАЧИ (Task State Segment). Сегмент TSS, выполняемой задачи, адресуется процессором при помощи 16-ти битного регистра Task Register (TR), содержащий селектор соответствующего дескриптора TSS.

Формат TSS (указаны смещения от начала области в байтах):

• 0h LINK - Поле обратной связи, используемое для организации вложенных вызовов задач (организуется цепочка ссылок на вызвавший TSS);

• 2h STACK 0 - Хранит логический адрес стека для кольца 0 при межсегментном вызове через шлюз;

• 6h STACK 1 - Аналогично для кольца 1;

• Ah STACK 2 - Аналогично для кольца 2;

• Eh IP - Указатель каманд;

• 10h FLAGS - Регистр флагов;

• 12h AX - Аккумулятор;

• 14h CX - Счетчик;

• 16h DX - Регистр данных;

• 18h BX - Базовый регистр;

• 1Ah SP - Указатель стека;

• 1Ch BP - Указатель базы;

• 1Eh SI - Индекс источника;

• 20h DI - Индекс приемника;

• 22h ES - Дополнительный сегмент;

• 24h CS - Сегмент кода;

• 26h SS - Сегмент стека;

• 28h DS - Сегмент данных;

• 2Ah LDTR - Регистр локальной таблицы дескрипторов данной задачи;

• 2Ch Дополнительная область, используется ОС. Процессором не считывается

• и не модифицируется.

Переключение задач.

Переключить задачу можно тремя способами:

1. По команде JMP - В этом случае в качестве операнда указывается адрес сегмента TSS. Для возврата необходимо воспользоваться той же командой с адресам сегмента TSS исходной;

2. По команде CALL - В качестве операнда указывется адрес сегмента TSS, при переключении в регистре FLAGS устанавливается бит вложенной задачиNT, а в поле доступа дескриптора делается пометка "занятый TSS" что исключает возможность рекурсивного вызова. Однако возможен дальнейший вызов других вложенных задач. При возврате по команде IRET адрес возврата берется из поля LINK. В качестве операнда каманды CALL может быть указан шлюз вызова задачи: 16 бит - Не используется; 16 бит - Селектор TSS; 8 бит - Не используется; 8 бит - Доступ (тип вентиля задачи); 16 бит - Резерв. Вентили задач могут располагаться в таблицах GDT и LDT. Отличие вызова задачи от вызова подпрограммы заключается в необходимости переключения TSS, что связано с большими временными затратами и организацией возврата. При возврате из подпрограммы используется команда RET, а из задачи IRET. Это отличие приводит к тому, что повторный вход в задачу осуществляется по адресу следующему за IRET. При переключении задач привелигированность проверяется только при выполнении JMP или CALL, обратное переключение по IRET и остальные случаи (исключения, прерывания, шлюзы в LDT) без проверки, т.к. задачи работают в изолированных адресных пространствах. Отличие шлюза задачи от шлюза вызова заключается в отсутствии возможности передачи параметров.

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

Синхронизация задач.

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