1625914891-62d0978a4faa71912bcf30efde0ff3e3 (843827), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Номер записи втаблице страниц соответствует номерувиртуальной страницы.Из этой записи в таблице страниц находитсяномер кадра для данной виртуальнойстраницы, затем прибавляется смещение иформируется физический адрес.Структура таблицы страницКроме того запись в таблице страниц содержитинформацию об атрибутах страницы: биты присутствия; бит защиты (например, 0 – read/write, 1 – read only...); бит модификации (устанавливается, если содержимоестраницы модифицировано, и позволяетконтролировать необходимость перезаписи страницына диск); бит ссылки (помогает выделить малоиспользуемыестраницы); бит, разрешающий кэширование; …Таблица страниц: проблемаобъема адресных пространствПодсчитаем примерный размер таблицы страниц.В 32-битном адресном пространстве приразмере страницы 4 Кбайт (Intel) получаем232/212=220, то есть приблизительно миллионстраниц, а в 64-битном и того более.Таким образом, таблица должна иметь примерномиллион строк, причем запись в строкесостоит из нескольких байтов.Таблица страниц: проблемаобъема адресных пространствДля того чтобы избежать размещения в памяти огромнойтаблицы, ее разбивают на ряд фрагментов.

Воперативной памяти хранят лишь некоторые,необходимые для конкретного момента исполненияфрагменты таблицы страниц. В силу свойствалокальности число таких фрагментов относительноневелико.Наиболее распространенный способ разбиения страницна части – организация так называемоймногоуровневой таблицы страниц. Для примерарассмотрим двухуровневую таблицу с размеромстраниц 4 Кбайт, реализованную в 32-разряднойархитектуре Intel.Таблица страниц: проблемаобъема адресных пространствТаблица, состоящая из 220 строк, разбивается на210 таблиц второго уровня по 210 строк. Этитаблицы второго уровня объединены в общуюструктуру при помощи одной таблицы первогоуровня, состоящей из 210 строк.32-разрядный адрес делится на 10-разрядноеполе p1, 10-разрядное поле p2 и 12-разрядноесмещение d.

Поле p1 указывает на нужнуюстроку в таблице первого уровня, поле p2 –второго, а поле d локализует нужный байтвнутри указанного страничного кадра.Ассоциативная памятьПоиск номера кадра, соответствующего нужнойстранице, в многоуровневой таблице страництребует нескольких обращений к основнойпамяти, поэтому занимает много времени.В соответствии со свойством локальностибольшинство программ в течение некоторогопромежутка времени обращаются кнебольшому количеству страниц, поэтомуактивно используется только небольшая частьтаблицы страниц.Ассоциативная памятьЕстественное решение проблемы ускорения – снабдитькомпьютер аппаратным устройством для отображениявиртуальных страниц в физические без обращения ктаблице страниц, то есть иметь небольшую, быструю кэшпамять, хранящую необходимую на данный момент частьтаблицы страниц.Это устройство называется ассоциативной памятью,иногда также употребляют термин буфер поискатрансляции (translation lookaside buffer – TLB).Одна запись таблицы в ассоциативной памяти (один вход)содержит информацию об одной виртуальной странице: ееатрибуты и кадр, в котором она находится.

Эти поля вточности соответствуют полям в таблице страниц.Ассоциативная памятьКонструкция ассоциативной памяти должна организовыватьзаписи таким образом, чтобы можно было принятьрешение о том, какая из старых записей должна бытьудалена при внесении новых.Число удачных поисков номера страницы в ассоциативнойпамяти по отношению к общему числу поисков называетсяhit (совпадение) ratio (пропорция, отношение). Такимобразом, hit ratio – часть ссылок, которая может бытьсделана с использованием ассоциативной памяти.Обращение к одним и тем же страницам повышает hitratio. Чем больше hit ratio, тем меньше среднее времядоступа к данным, находящимся в оперативной памяти.Ассоциативная памятьПредположим, например, что для определенияадреса в случае кэш-промаха через таблицустраниц необходимо 100 нс, а для определенияадреса в случае кэш-попадания черезассоциативную память – 20 нс.С 90% hit ratio среднее время определения адреса –0,9x20+0,1x100 = 28 нс.Высокое значение вероятности нахождения данныхв ассоциативной памяти связано с наличием уданных объективных свойств: пространственной ивременной локальности.Ассоциативная памятьЗамечание.

При переключении контекстапроцессов нужно добиться того, чтобы новыйпроцесс «не видел» в ассоциативной памятиинформацию, относящуюся к предыдущемупроцессу, например очищать ее. Таким образом,использование ассоциативной памяти увеличиваетвремя переключения контекста.Рассмотренная двухуровневая (ассоциативнаяпамять + таблица страниц) схема преобразованияадреса является ярким примером иерархиипамяти, основанной на использовании принципалокальностиТрешинг (trashing, пробуксовка)Трешинг – высокая частота страничных нарушений.Сколько кадров нужно процессу?Рабочее множество W(t,T) – это набор страниц (P1, P2, ... Pn),активно использующихся вместе, который позволяет процессу вмомент времени t в течение некоторого периода T работать,избегая большого количества page faults.Число страниц в рабочем множестве определяется параметромТ, является неубывающей функцией T и относительно невелико.Принцип локальностиЕсли в период времени (t-T, t) программаобращалась к страницам W(t,T),то при надлежащем выборе Tс большой вероятностью эта программабудет обращаться к тем же страницамв период времени (t, t+T).Размер страницы памятиПри выборе размера страницы памяти нужно учитывать, чточем больше размер страницы, тем: Меньше будет размер структур данных, обслуживающихпреобразование адресов (в т.ч.

таблицы страниц); Больше будут потери, связанные с тем, что память можновыделять только постранично (в среднем половинапоследней страницы процесса пропадает ); Меньше количество операций ввода-вывода привзаимодействии с внешней памятью;Размер страницы памятиОбычно размер страницы – это степеньдвойки от 29 до 214 байт.В некоторых архитектурах размер страницможет быть не постоянным. Например вPentium размер страницы колеблется от4 Кбайт до 8 Кбайт.Лекция окончена!Благодарю за внимание!51Системное и прикладноеПРОГРАММНОЕ ОБЕСПЕЧЕНИЕЛекция №4.

Файловые системыГуськов Андрей Евгеньевичhttp://my.ict.nsc.ru/~guskov/courses/software/guskov (dog) ict.nsc.ru2008 г.1Лекция №4. Содержание1.2.3.4.Общее устройство файловой системыУправление внешней памятьюСтруктура файловых системВопросы реализации файловых систем2Файловая системаФайловая система - это частьоперационной системы,назначение которой состоит в том,чтобы организовать эффективнуюработу с данными, хранящимися вовнешней памяти, и обеспечитьпользователю удобный интерфейспри работе с такими данными.Основные функции ФС1.2.3.4.5.6.Идентификация файловРаспределение внешней памяти междуфайламиОбеспечение надежности иотказоустойчивостиОбеспечение защиты от НСДОбеспечение совместного доступа к файламОбеспечение высокой производительностиЖесткий дискСхема жёсткого дискаЗагрузка ОСОбщая структураФС• Логическая подсистемауправления файлами• Базовая подсистемауправления файлами• Система ввода-вывода• ОборудованиеМетоды выделения дисковогопространства1.2.3.4.Выделение непрерывнойпоследовательности блоковСвязный списокТаблица отображения файловИндексные узлыFAT: File Allocation TableИндексные узлы (UNIX V7)Этапы поиска файла поабсолютному пути /usr/sbin/mcУправление свободным и занятымдисковым пространством1.2.3.Битовый векторСвязный списокСпециальный индексный узел (файл«свободное пространство»)Структура ФС на дискеФС состоит из:1.Суперблока2.Структуры данных, описывающиесвободное дисковое пространство3.Массива индексных узлов4.Блоков данных файловРеализация ФС1.2.3.4.Директории в ОС MS DOSДиректории в ОС UnixМонтирование файловых систем(связывание файловой системы ссуществующей иерархией файловыхсистем)Связывание файлов: hard link, symboliclinkМетоды повышениянадежности ФС1.2.3.4.5.Оптимальный порядок выполненияоперацийЖурнализацияПроверка целостности«Зеркалирование» дисковРезервированиеМетоды повышенияпроизводительности ФС1.КэшированиеАлгоритмы вытеснения:FIFO, Second Chance, LRUСинхронизация кэша2.3.Оптимальное размещение на дискеРазмещение на средних дорожкахЗапись в последовательные блокиДефрагментацияПланирование запросов к дискуАлгоритмы:FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOKАлгоритм планированияFirst Come First Served (FCFS)Пусть у нас на диске из 100 цилиндров (от 0до 99) есть следующая очередь запросов: 23,67, 55, 14, 31, 7, 84, 10 и головки в начальныймомент находятся на 63-м цилиндре.Тогда положение головок будет менятьсяследующим образом:63 → 23 → 67 → 55 → 14 → 31 → 7 → 84 → 10Всего: 329 цилиндровАлгоритм планированияShort Seek Time First (SSTF)В каждом случае выбирается запрос, которыйближе всего к текущему положению головки.63 → 67 → 55 → 31 → 23 → 14 → 10 → 7 → 84Всего: 141 цилиндровАлгоритмы планированияSCAN, LOOKSCAN – головки постоянно перемещаютсяот одного края диска до другого, по ходуобслуживая все встречающиеся запросы.63 → 55 → 31 → 23 → 14 → 10 → 7 → 0 → 67 → 84Всего: 147 цилиндровLOOK – не доходим до крайних цилиндров:63 → 55 → 31 → 23 → 14 → 10 → 7 → 67 → 84Всего: 133 цилиндровАлгоритмы планированияC-SCAN, C-LOOKВ этих модификациях алгоритмовсчитывания происходит при движенииголовки в одну сторону; при достиженииконца диска, головка (быстро)перемещается в начало.Это позволяет более равномернообслуживать запросы.Лекция окончена!Благодарю за внимание!22Системное и прикладноеПРОГРАММНОЕ ОБЕСПЕЧЕНИЕЛекция №5.

Характеристики

Список файлов лекций