Сегментация при отключенном механизме управления страницами

Размер вирт сегмента: 2^32 = 4Гб.

Селектор предназначен для выбора дескриптора определённого сегмента из таблицы дескрипторов сегментов.

13	1	2
№ дескриптора	GDT – 0, LDT - 1	Ур привилегий: CPL=0-3

2 таблицы дескрипторов:

· GDT – глобальная для описания сегментов сегментов ОС и сегментов, доступным всем процессам.

· LDT – локальная для описания сегментов отдельных задач.

GDR одна, LDT столько, сколько в системе задач. Активной может быть только одна.

Количество сегментов определяется размером поля в сегментном регистре:

2^13 = 8К каждого типа. Всего 16 Кб сегментов.

Чтобы найти в ОП таблицу GDT используется регистр GDTR, в котором хранится:

32	16
Базовый адрес в физич памяти сегмента GDT	Размер сегмента в байтах

Каждый дескриптор в таблице GDT имеет размер 8 байт

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

Уровни привилегий:

0 – для ядра ОС

1,2 – утилиты ОС

3 – прикладные программы.

В дескрипторе вирт сегмента есть поле DPL – уровень прав сегмента. Т.о. доступ к вирт сегменту будет считаться законным, если уровень прав селектора меньше либо равен уровню прав сегмента: СPL <=DPL Байт прав доступа: Р – бит присутствия (1 – сегмент присутствует в ОП, 0 – отсутствует); DPL (Descriptor Privilege Level) – уровень привилегии дескриптора (0¸3, где 0 – самые большие привилегии, 3 – самые маленькие); S – признак системного – 0 или несистемного (т.е. сегмент ОП) – 1 дескриптора.

Сегментно-страничная адресация.

ВАП задачи имеет размер 4Гб. Селектор задачи определяет № виртуального сегмента, а смещение – смещение внутри сегмента.

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

Физич АП и ВАП разбиты на страницы по 4Кб.

Формат дескриптора страницы:

20	3	2	1	1	1	1	1	1	1
№ страницы	AVL	O	D	A	PCD	PWT	U	W	P

P – вид присутствия страницы в физич памяти

W – разрешение записи страницы

U – бит, реж польз или позльз

D – признак модификации страницы

PCW, PWT – управляют кэшированием

AVL – зарезервировано под нужды ОС

Используется деление всей таблицы страниц на разделы по 1024 дескриптора. Совокупность дескрипторов, описывающих состояние и характеристики виртуальных страниц разделов – каталог разделов. Вирт страница, хранящая содержание каталога всегда в физич памяти, № её физич страницы находится в регистре CR3.

Преобразование линейного виртуального адреса в физический:

Поле номера виртуальной страницы делится на 2 части (20 разрядов):

- поле номера раздела

- поле номера страницы в разделе.

Для ускорения преобразования блоки управления страницами используются специальная КЭШ-память.

Защита адресных пространств:

1. изоляция АП путём назначения им различных физических сраниц или сегментов.

2. защита сегментов от несанкционированного доступа с помощью привилегий 4-х уровней.

Работа с памятью в МП i486+: Пользовательская программа не может свободно обращаться по любому адресу пространства памяти. Программа не может обращаться к сегменту памяти, пока он для нее не описан. Каждый сегмент описывается специальной структурой данных, состоящей из 8-ми байт. В описание сегмента включается базовый адрес, размер, тип (код, данные), уровень привилегий и дополнительная информация о состоянии. Число таких структур – дескрипторов в системе практически не ограничено.

ГИП

DPL

Баз_адр 31¸24

Предел 16¸19

Баз_адр 23¸16

–––––– Базовый адрес 15¸0 –––––®

–––––– Предел 15¸0 –––––––®

Базовый адрес определяет начальный (линейный) адрес. Предел – двоичное поле, определяющее размер сегмента (в байтах или страницах). Байт прав доступа: Р – бит присутствия (1 – сегмент присутствует в ОП, 0 – отсутствует); DPL (Descriptor Privilege Level) – уровень привилегии дескриптора (0¸3, где 0 – самые большие привилегии, 3 – самые маленькие); S – признак системного – 0 или несистемного (т.е. сегмент ОП) – 1 дескриптора.

3. Технология Frame Relay.

Сети FR – новая технология.

В 1988 применялась как безымянная служба в рамках ASDN для реализации пакетного режима. В 92-93 была выделена как отдельная служба. FR специализируется для передачи пульсирующего трафика ЛВС. Но это преимущество хорошо заметно, если каналы связи имеют высокое качество (оптоволокно). Это преимущество обеспечивается за счет низкой протокольной избыточности и в дейтограмном режиме работы, что обеспечивает высокую пропускную способность и небольшие задержки передачи кадров. Надежную передачу кадров FR не обеспечивает. Основная ниша использования FR – общественные сети, используемые для соединения ЛВС. Скорость 2 Мбит/с. Протокольная избыточность – соотношение полезной и служебной информации.

Стек протокола FR

Структура похожа на ISDN

Стек протоколов для канала типа D.

Данный стек полностью соответствует подобному стеку ISDN, за исключением возможности использования протокола Q.933 вместо Q.931, Q.933 – более упрощенная модификация. Главная функция стека – установление виртуального соединения.

Стек протоколов для каналов типа D, B, H.

Данный стек вступает в работу после установления виртуального канала (либо скоммутированного либо постоянно проложенного).

Основа данного стека – протокол LAP-F. LAP-F работает на любых каналах ASDN, в том числе и на каналах типа T1/E1. LAP-F передает кадры в сеть в любой момент времени, считая, что виртуальный канал уже существует. LAP-F условно можно разделить на 2 части:

1) LAP-F core, который является упрощенной версией протокола LAP-D и представляет собой основу технологии FR.

2) LAP-F control, является необязательной надстройкой над LAP-F core и выполняющий функции контроля доставки кадров и управления потоком.

Формат кадра протокола LAP-F

За основу взят формат кадра HDLC, но изменен формат поля адреса и отсутствует поле управления.

- флаг (Flag) - указывает на начало фрейма;

- адрес (Address) - может иметь длину от 2 до 4 байтов;

- данные (Data) - содержит пользовательские данные, передаваемые по сети frame relay;

- контрольная последовательность кадра - для базового механизма обнаружения ошибок;

- флаг (Flag) - указывает на конец фрейма.

Флаг

Адрес

Данные

Контрольная последовательность кадра

Флаг

Флаг – для организации начала и конца кадра. Имеет размерность 8 бит. В HDLC – 01111110. Между двумя кадрами эта комбинация не должна повторяться. Если повторяется, то изменяется методом вставки бит. Каждая сторона после пяти единиц вставляет 0.

Особенности FR:

1) Гарантированная поддержка основных показателей качества транспортного обслуживания локальных сетей.

2) т.к. FR – заканчивается на канальном уровне она позволяет без особых проблем взаимодействовать с канальным уровнем любых сетей по средствам единого сетевого протокола, например IP.

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

Билет 23.

1. Методы хеширования для реализации доступа к данным по ключу.

Хеширование.

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

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

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

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

А0 – начальный адрес таблицы

R1 – длина заголовка

R – длина записи с информацией

A = A0 + R1 + номер_записи*R

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

2. Организация защиты памяти в микропроцессорах i286, i386, i486+: защита по привилегиям. Кольца защиты.

1) защита прог ОС от пользовательских

2) защита прог пользователей друг от друга

3) защита прог ОС друг от друга

4) защита пользовательских прог от внутренних ошибок

Схемы управления памятью обнаруживают большинство программных ошибок, таких, как:

· формирование неверных адресов;

· нахождение индекса за пределами массива;

· искажение стека и т. д.

Защита по привилегиям заключается в проверке возможности:

· выполнять некоторые команды;

· обращаться к данным других программ;

· передачи управления внешнему коду (FAR);

проверка осуществляется при выполнении каждоц команды.

Привилегия — это права или возможности, которыми не разрешается:

i286+ поддерживают 4 уровня привилегий или колец защиты:

уровни привилегий: 0 — ядро ОС 1 — ОС 2 — системы прграммирования 3 — прикладные программы уровень запрашиваемых привилегий процессора

Защита доступа к данным.

Правило защиты дрступа к данным:

CPL £ DPL

иначе формирование пррываний (особый случчай) общей защиты.

Контроль происходит в 2 этапа:

1) При загрузке селектора в сегментные регистры DS, ES, FS, GS, если DPL<CPL селектор не загружается и формируется особый случай общей защиты;

2) (если селектор загрузился). Проверка при фактическом использовании селектора. Т. е. проверяется возможность использования этого селектора для выполнения определенных операций: чтения, записи, выполнения.

Особенность: при загрузке SS (стекового сегментного регистра) CPL=DPL.

(Разрешается использовать только стек своего уровня). Кроме того, чтобы дескриптор сегментного стека позволял запись и считывание, и сегмент находится в ОП (р=1).

3. Чистая и синхронная ALOHA.

Этот методы доступа к среде, которые были впервые применены для доступа к общему радио каналу сотрудниками гавайского университета 1970-1972. На этих методах базируются более поздние методы доступа.

Чистая ALOHA

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

Эта обратная связь в среде ЛВС происходит почти мгновенно. Обнаружив конфликт, пользователь ожидает некоторый случайный отрезок времени, после чего повторяет попытку. Ожидание должно быть случайным, иначе конкуренты будут повторяться в одно и тоже время, что приведет к блокировке.

Оценка эффективности чистой ALOHA.

Рассмотрим следующую модель:

Есть неограниченное число пользователей. Все, что они могут: либо набирать текст, либо ждать, пока переданный текст передастся. Передача происходит в момент окончания строки. Система пытается передать строку, ожидает отклика и продолжает работу. Вводиться понятие время кадра – время необходимое для передачи кадра фиксированной длины.

Предположения:

1) число пользователей – не ограничено, и они передают кадры по закону Пуассона, со средним значением S кадра за время передачи кадра. При S>1 очередь на передачу будет только расти, то предполагается, что 0<S<1

2) Вероятность за время кадра послать за К попыток как новые, так и ранее не прошедшие кадры распределена по закону Пуассона со средним значением G>=S

3) Пропускная способность – число кадров, которые надо передать, умноженные на вероятность успешной передачи.

P0 – вероятность отсутствия коллизий при передачи кадра.

S = G*P0

Анализ:

Определяется время, необходимое отправителю для обнаружения коллизий. t0 – время начала передачи, t – время, необходимое для достижения самой отдаленной станции.

Тогда, если в тот момент, когда кадр достиг самой отдаленной станции, она начнет передачу, то отправитель узнает об этом во время t0+2t.

Вероятность появления К кадров при передачи при распределении Пуассона:

, поэтому вероятность, что появится 0 кадров = . А за двойное время кадра среднее число кадров будет 2G. т.о. вероятность передачи кадров без коллизии , т.к. , то

Это значит, что генерировать кадры при чистой ALOHA со скоростью >18% от скорости канала, то очередь переполниться и система заблокируется.

Синхронная ALOHA

В 1972 появилась модификация чистой ALOHA – синхронная (слотируемая).

Все время разделяют на интервалы – слоты (1 кадр – 1 слот).

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

Оценка эффективности синхронной ALOHA

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

Общая эффективность передачи 37%, что в 2 раза больше чем у чистой.

Билет 24.

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

Дата добавления: 2018-05-12; просмотров: 405; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 15 16 17 18 19 202122 23 24 Следующая ⇒

Мы поможем в написании ваших работ!