Билет 23.
Методы хеширования для реализации доступа к данным по ключу. Хеширование.
Этот метод используется тогда, когда все множество ключей заранее известно и на время обработки может быть размещено в оперативной памяти, и при этом множество ключей практически не изменяются.
В этом случае строится специальная функция, однозначно отображающая множество ключей на множество указателей, называемая хеш-функцией. Имея такую функцию можно вычислить адрес записи в файле по заданному ключу поиска. В общем случае ключевые данные, используемые для определения адреса записи организуются в виде таблицы, называемой хеш-таблицей.
Если множество ключей заранее неизвестно или очень велико, то от идеи однозначного вычисления адреса записи по ее ключу отказываются, а хеш-функцию рассматривают просто как функцию, рассеивающую множество ключей во множество адресов.
В последовательном файле содержится информация, состоящая из 2-х условных частей, 1-я несет функцию описания структуры файла, описание заголовка, 2-я представляет полезную информацию и состоит из записей одинаковой структуры. Ключами доступа информации являются номера записей.
А0 – начальный адрес таблицы
R1 – длина заголовка
R – длина записи с информацией
A = A0 + R1 + номер_записи*R
Если удается создать хэш-функцию, то обеспечивается наиболее быстрый доступ к информации.
Организация защиты памяти в микропроцессорах i286, i386, i486+: защита по привилегиям. Кольца защиты.
защита прог ОС от пользовательских
защита прог пользователей друг от друга
защита прог ОС друг от друга
защита пользовательских прог от внутренних ошибок
Схемы управления памятью обнаруживают большинство программных ошибок, таких, как:
формирование неверных адресов;
нахождение индекса за пределами массива;
искажение стека и т. д.
Защита по привилегиям заключается в проверке возможности:
выполнять некоторые команды;
обращаться к данным других программ;
передачи управления внешнему коду (FAR);
проверка осуществляется при выполнении каждоц команды.
Привилегия — это права или возможности, которыми не разрешается:
i286+ поддерживают 4 уровня привилегий или колец защиты:
уровни привилегий: 0 —
ядро ОС 1 —
ОС 2 —
системы прграммирования 3 —
прикладные программы
уровень
запрашиваемых привилегий процессора
Защита доступа к данным.
Правило защиты дрступа к данным:
CPL DPL
иначе формирование пррываний (особый случчай) общей защиты.
Контроль происходит в 2 этапа:
При загрузке селектора в сегментные регистры DS, ES, FS, GS, если DPL<CPL селектор не загружается и формируется особый случай общей защиты;
(если селектор загрузился). Проверка при фактическом использовании селектора. Т. е. проверяется возможность использования этого селектора для выполнения определенных операций: чтения, записи, выполнения.
Особенность: при загрузке SS (стекового сегментного регистра) CPL=DPL.
(Разрешается использовать только стек своего уровня). Кроме того, чтобы дескриптор сегментного стека позволял запись и считывание, и сегмент находится в ОП (р=1).