Последната актуализация на този раздел е от 2021 година.

6.4.1 Методи за преобразуване на виртуалните адреси

Въз основа на казаното в предидущия пункт вече можем да твърдим, че оптималното управление на паметта (управление с максимална ефективност) се търси чрез използване на възможно най-гъвкави структурни схеми. Търсенето и разработването на такива схеми продължава и до днес. Вероятно ще продължава и в бъдеще, тъй като компютърните системи се развиват изключителни динамично върху едно неизчерпаемо богатство от идеи. Това естествено задължава читателя да полага системни усилия за актуализация на своите познания. Ще отбележим, че като продължение на изложените вече структурни схеми за управление на паметта, понастоящем се практикуват два основни вида структуриране на адресното пространство:

· Странична организация на управлението ;

· Сегментна организация на управлението ;

както и смесената:

· Сегментно-странична организация на управлението.

За странична организация говорим когато размерът на структурната единица (блок от паметта) има фиксирана стройност. В противен случай, когато размерът на структурните единици е променлив и когато той се определя по някакво логическо правило (например от вида на съдържанието - програмен код или данни), структурната организация се нарича сегментна. Смесената организация се прилага с цел постигане на по-голяма гъвкавост при управление на физическите ресурси на компютърната система. В този случай например е възможно организиране на сегменти с променлив размер като съвкупност от различен брой, но еднакви по обем страници.

Страницирането или сегментирането на виртуалната памет (разбирайте го на текста на програмите) обикновено се реализира автоматично по програмен път, който се явява свойство на операционните системи. С други думи, не е задължение на програмиста.

За разлика от програмния път, проекторът на виртуалните адреси (mapper) се реализира изключително с апаратни средства. Тук е необходимо да кажем, че не всички процесори притежават устройството за управление на паметта MMU, където е мястото на тази апаратура (вижте фигура 6.4.3).

Основната функция на проектора беше пояснена в предидущия раздел и тук възниква въпросът как да се извършва преобразуването на виртуалния въпрос във физически, щото изпълнението на програмата да не се забавя безобразно. Повечето конструктори решават тази задача с помощта на прости даннови структури, наричани таблици на съответствието, осигуряващи висока скорост за достъп. Функционирането на проектора (вижте фигура 6.4.5) се базира на две главни таблици:

· Таблица (карта) на страниците ;

· Таблица (карта) на диска.

По-долу ще разгледаме споменатите структурни схеми като навлизаме в тяхната същност постепенно.

А) Странична организация на паметта

В най-разпространения вариант на тази схема за структуриране, както логическото така и физическото адресно пространство, се разделя на блокове с еднакъв обем (кратен на степените на 2), наричани страници. За да се различават по принадлежност, логическите структурни единици се наричат страници (page), а физическите – странични кадри или рамки (page frames). Тъй като структурните единици не могат да се застъпват (адресните пространства на отделните страници се конкатенират), външната фрагментация, която споменахме в предидущия пункт като недостатък, отсъства. В същото време загубите от вътрешна фрагментация са ограничени до част от последната страница, която процесът заема (той заема цяло число страници). Описаните в предидущия пункт 4 структурни схеми се характеризират с твърде неефективното използване на паметта, ето защо не е прието един процес да се помества в оперативната памет като един непрекъснат (неделим) блок.

При страничното структуриране формално всеки логически адрес представлява подредена двойка (P|D), в която P представлява номера на страницата във виртуалното адресно пространство, а D – отместване в рамките на страницата в брой адресируеми единици (L=P|D=P+D):

Така описваната схема позволява един процес да бъде зареден в оперативната памет, при това не изцяло, даже и да няма непрекъсната област от странични кадри.

Реалното съответствие, което проекторът реализира, е скрито от потребителя и се контролира от операционната система. Логическата структура (P|D) се преобразува в аналогична физическа (P’|D).

Страничната организация на виртуалното адресно пространство е била разработена с цел да удовлетвори потребностите от оперативна памет, без непосредствено тя да се разширява физически. В този смисъл, за разлика от сегментната, страничната организация в пълна степен съответства на концепцията за виртуална памет. За първи път тази организация е приложена през 1961 година в машината "Атлас" (Англия).

За преобразуване (проектиране) на виртуалния (логическия) адрес във физически са разработени два основни метода:

· Чрез таблици за пряко преобразуване ;

· Чрез асоциативни таблици за преобразуване.

По-надолу тук ще започнем с разглеждане на организацията за преобразуване с помощта на таблиците на страниците.

Пряко преобразуване

Таблица на страниците се създава за всеки зареден в оперативната памет процес, следователно таблиците са много и всяка една от тях съдържа описанието (картата) на разположението на заредените в оперативната памет страници, принадлежащи на дадения процес. Така можем да твърдим, че наборът от странични таблици е динамичен във времето, тъй като той съответства на броя на стартираните от операционната система процеси. От тук можем да направим още един извод, че създаването на нова странична таблица, е задача на операционната система.

А сега на въпроса “какво се съдържа в таблицата на страниците?”. Според представата за задачата на проектора, за установяване на съответствието между адресите, излиза, че в таблицата следва да се съдържа адресното описание на местоположението и състоянието на всяка отделна страница. Можем да си представяме, че описанието на една страница представлява един елемент (един ред) в таблицата на страниците. Описателният елемент още се нарича дескриптор, откъдето и таблицата може да се нарича дескрипторна. Обемът на страницата в различните реални процесори се движи в границите от 256[В] до 16[КiВ] и зависи от структурирането на физическата памет; от броя на тактовете в цикъла за обръщение на системната шина; от структурата на записа върху външния носител и от други фактори. Обемът на страницата представлява базова единица на информацията за трансфер между външната памет (диска) и оперативната памет, когато той бъде заявен от механизмите на виртуалната памет. Обемът на страниците не следва да бъде много малък, тъй като времето за достъп до магнитния диск (в порядъка на милисекунди) е много по-голямо от времето за достъп до оперативната памет. Идеалното съотношение между времето за трансфер на страницата и времето за достъп до диска е 1:1. При малки по обем страници ще има големи периоди на изчакване до началото на следващия трансфер, положение, което можем да оценим като крайно неефективно. Тогава, ако приемем за пример, че обемът на страницата да бъде 512[В] (512=2⁹), то в адресното пространство с обем 4[GiB] ще се съдържат 2²³=8.388.608 на брой страници. Съответно толкова на брой описателни елементи (реда) трябва да има таблицата на страниците. Когато например обемът на страницата е 4[КiВ], то броят на елементите (редовете) на тази таблица е 2²⁰=1.048.576=1[M], което е също твърде голямо число! В някои процесори обемът на страниците може да се управлява, от което произлизат допълнителни усложнения в структурните и алгоритмичните схеми. Обемът може да бъде например още 8[KiB], 64[KiB], 512[KiB], 4[MiB], дори 16[MiB]. Тези възможности са заложени в устройството за управление на паметта – MMU. В това направление ни предстои да разберем какво още ще ни предложи бъдещето. Определянето на страници с малък обем в приложения, които реално използват голям обем адресно пространство, може да доведе до повишена честота на TLB-пропуските, предвид на това, че обемът на TLB-буферите е малък (TLB – Translation Lookaside Buffer). Като цяло такъв избор може да се определи като неудачен.

Като имаме предвид и максималния брой процеси (вижте формула 6.4.2), които могат да се поддържат във виртуалното пространство, обемът на необходимата описателна информация наистина е огромен. За ранните процесори на Intel например беше казано, че дължината на индекса е V=14[b], което означава, че за този процесор са възможни S=2¹⁴=16384 на брой таблици на страници. Така общият обем описателна информация (при страница с обем 4[КiВ]) достига максимума от

(1048576).(16384) = 17.179.869.184 = 2³⁴

на брой реда – едно впечатляващо количество!

След всичко казано до момента следва да поясним каква е структурата на описателния елемент (дескриптора) на една страница. Като се абстрахираме от конкретиката на отделните процесори, обобщено минимално задължителните елементи в дескриптора са изобразени на следната рисунка:

Фиг. 6.4.1.1. Структура на дескрипторен елемент

Както се вижда от рисунката, 32-битовият елемент има две структурни части – поле на атрибутите на страницата и нейния физически базов адрес (page frame). Част от битовете атрибути имат следния смисъл и предназначение:

· Бит E (Exist) – признак за съществуване (създаване). Битът има стойност Е=1, когато такава страница съществува и в нея се съдържа актуална информация. Страницата има този признак независимо от това къде се намира – дали на диска или в оперативната памет. Ако при обръщение се установи, че Е=0, това означава, че такава страница не съществува и нейното съдържание е без значение. Празните страници могат да се използват за различни цели.

· Бит P (Present) – бит за присъствие. Комбинацията от битове Е=1 и P=1 показва, че страницата съществува и че е заредена в оперативната памет. Когато страницата се съдържа в оперативната памет, нейният начален (базов) физически адрес е този, който е записан в старшата част на дескриптора. Базовият адрес се допълва с необходимия брой незначещи нули до вида:

F_addr = bbb…bb½000…00.

Ако при обръщението се окаже комбинацията Е=1 и P=0, това означава, че страницата съществува, но не присъства (не е заредена) в оперативната памет.

Ситуацията се нарича page fault. В този случай, ако дадена команда заяви обръщение по виртуален адрес от такава липсваща страница, механизмът за преобразуване на виртуалния адрес (проекторът) ще генерира прекъсване, което операционната система обслужва, като зарежда в оперативната памет необходимата страница. Едва след това се изпълнява заявената основна операция. Тази ситуация е специална и е разгледана в отделен раздел.

Липсващата страница се търси върху диска според информацията съдържаща се в старшата част на дескриптора. В този случай там се намира специфично описание на местоположението на виртуалната страница върху диска. Това описание обикновено представлява следната даннова структура:

<№ на дисково устройство><№ на дискова глава><№ на цилиндър><брой на записите>.

Можем кратко да поясним, че след компилирането и свързването на една програма, нейният краен виртуален текст, структуриран по страници, се записва във файл върху диска. Съставената за тази програма таблица на страниците е запълнена с “дискови” адреси. Когато се стартира тази програма, нейната таблица на страниците се оказва в оперативната памет, където след зареждане на дадена виртуална страница от програмата в избрана физическа страница, нейният дескриптор се актуализира – актуализират се съответните атрибути, а дисковият адрес се заменя с физическия. Така при изпълнение на обръщения към паметта се случват по-горе описаните ситуации.

· Бит R/W (Read/Write) бит за защита от запис. Когато R/W=0 страницата е достъпна само за основна операция четене, а когато R/W=1, страницата е достъпна и за двете основни операции.

· Бит U/S (User/Supervisor) – бит за управление на привилегиите. Когато U/S=0, достъп до страницата има операционната система, а когато U/S=1 – достъпът е разрешен за потребителки програми и за данни.

· Бит PWT (Page Write Through) – бит за управление на кеширането на страницата. Когато PWT=1, тогава е разрешено кеширане с едновременен запис, а когато PWT=0, тогава едновременният запис е забранен.

· Бит PCD (Page Cache Disable) – втори бит за управление на кеширането. Когато PCD=1 кеширането на страницата е забранено, в противен случай – е разрешено.

· Освен представените атрибути, в различните процесори има още допълнителни, на които няма да се спираме, тъй като тяхното познаване не е от принципно значение.

Следва да отговорим още на въпроса “къде може да се съхранява наборът от странични таблици?”. Очевидно е, че да се съхранява тази информация в оперативната памет, е крайно неразумно – нейният обем е твърде голям. Ясно е още, че съхранението й не е възможно на друго място, освен в специален файл върху твърдия диск. За да се осигури обаче лелеяното бързодействие за достъп, съдържанието на този файл не може да се остави изцяло върху диска. Обикновено файлът също се разбива (структурира) на страници. Последното позволява във физическата памет да се съдържат само актуални части от този файл. Възниква въпросът – кои части от този файл следва да се зареждат в оперативната памет? По същество този въпрос трябва да даде операционната система. По-горе вече споменахме, че когато проекторът установи липсата на търсената страница в оперативната памет се генерира прекъсване, в отговор на което операционната система зарежда от диска търсената страница и заедно с нея и нейния дескрипторен елемент. Обикновено обемът на съхраняващата се в оперативната памет част от таблицата на страниците на даден процес има обема на самата страница. Например, ако страниците са с обем 4[KiB] и дескрипторният елемент на всяка страница е с дължина 4[B]=32[b], това означава, че в тази таблица-страница ще могат да се водят на отчет само 1024 страници от всички страници на програмата.

По-горе казахме, че при 4[G] обем на адресното пространство и обем на страницата от 4[KiB], то таблицата на страниците за едно задание има 2²⁰=1[M]=1.048.576 на брой реда! Малко по-горе казахме още, че ако в оперативната памет съхраняваме само една страница от тази таблица, това означава, че съхраняваме само 1024 4-байтови дескриптора, всеки от които описва една физическа страница, т.е. в оперативната памет на различни места могат да бъдат заредени максимум 1024 страници от заданието – това означава 1024.4[KiB]=4096[KiB] от програмния код на това задание. Дали този обем е достатъчен или не тук не сме в състояние да преценим, а и това не е наша задача.

За по-голяма яснота ще илюстрираме схемата за пряко преобразуване на виртуалния страничен адрес на следващата фигура 6.4.1.2

Фиг. 6.4.1.2. Схема за преобразуване на виртуален страничен адрес

Ще обсъдим факта, че таблицата на съответствието се намира в оперативната памет. Характерното за този случай е, че за реализацията на основната операция (четене или запис) се извършват 2 обръщения от процесора към паметта – първото до елемент в таблицата на съответствието, където виртуалният адрес се подменя с физически и след това второ, до реална клетка. В случай на йерархични таблици обръщенията са 3! Трябва да признаем, че методът на прякото съответствие е крайно неефективна организация на достъпа, ето защо се търси друго решение на този проблем чрез асоциативен метод за достъп, на който ще се спрем по-късно.

Пряко двустепенно преобразуване

Ще поясним един друг подход, който придава по-голяма гъвкавост и възможности за решаване на така поставения въпрос. Това е подходът на йерархичното структуриране на таблица на страниците. Този подход е приложен в архитектурата на процесорите на Intel. Таблицата на страниците се структурира на 2 нива – цялата таблица се разделя на 1024 директории, всяка от които от своя страна съдържа описателите на 1024 страници. Така онези 1.048.576 на брой реда от таблицата на страниците се подреждат в една квадратна матрица с размери 2¹⁰ по 2¹⁰. Забележете, че броят на елементите на тази матрица (на този 2-мерен масив) е точно същият:

1024.1024 = 2¹⁰.2¹⁰ = 2²⁰ = 1.048.576 !

Така в този случай преобразуването на виртуалния адрес във физически става с помощта на 2 таблици – таблицата с описания на директориите (Page Table Directory) – или още каталог на директориите, която заема само 4[KiB] и още една таблица със същия обем за дескриптори на страници – общо 8[KiB]. Схемата за преобразуване на виртуалния страничен адрес във физически е представена на следващата фигура 6.4.1.3.

Фиг. 6.4.1.3. Двустепенно преобразуване на виртуален страничен адрес във физически

Всяко задание има свой каталог на директориите. Виртуалният адрес на клетка от виртуалната памет има два указателя за принадлежност – той принадлежи на страница №m, която принадлежи на директория №n. Отместването на адреса спрямо началния (базовия) адрес на виртуалната страница се взема от най-младшото поле във виртуалния адрес, подаден от процесора (от програмата).

Инверсна таблица

Преобразуване на виртуалните странични адреси с помощта на методи на прякото преобразуване е допълнително затруднено в 64-битовите компютърни архитектури, по причина на техния огромен брой страници. Конкурент на метода на прякото преобразуване, е функционалното преобразуване. Функционалното преобразуване води до на така наречената обърната (inverted) таблица на съответствието, прилагана най-вече от фирмите IBM и HP. Същността на този метод се състои в това, че номерът на виртуалната страница не се използва за установяване на пряко съответствие в таблицата на страниците. В случая се изгражда таблица, която съдържа описание на виртуалната страница. Тъй като обаче броят на страниците във виртуалното адресно пространство е огромен, то изградената таблица има толкова елемента, колкото са страниците на реалната физическа памет, установен от операционната система. С други думи, обемът на тази таблица не зависи от обема на виртуалната памет, въпреки че съдържа описания на виртуални страници. Тази същност дава наименованието инверсна таблица на страниците.

За да се намали обемът на последната, се прилага така нареченото хеш-отражение, или просто хеширане на виртуалния номер. Хеш-отражението се постига с помощта на хеш-функция (функция за разсейване). Хеш-функцията много често се използва като модел на базова случайна величина с равномерен закон на разпределение (вижте публикацията

http://www.tyanev.com/resources/docs/Document_V_27.pdf ).

Основната идея на хеширането тук е да се реализира функционалното съответствие Y=h(X) между едно входно множество от голям брой възможни числа X (например 2²⁰) върху едно изходно множество числа Y с много по-малък обем (например 2⁸).

За да осъзнаете това преобразуване си представете например 1000 човека застанали пред вас в една редица. Вие стоите в средата срещу тях, а двата края на редицата се източват наляво и надясно от Вас някъде в далечината. Това Ви смущава – крайните са твърде далече и не Ви чуват, а тези в средата са твърде близко и си мислят че им крещите. Естествено стигате до командата за преподреждане, например в редици от по 50 човека – много по-обозримо, а в дълбочина – колонки с по 20 човека.

Една от най-лесно реализуемите технически хеш-функции има вида:

Като аргумент X на хеш-функцията се използва номерът на виртуалната страница, който представлява цяло число в интервала [0, (2²⁰-1)]. Физическата реализация на хеш-функцията по определение в случая се постига чрез целочисленото деление X/ω, като за стойността h(X) се взема остатъкът R от делението (вижте формула 3.2.6.2). Получената хеш-стойност се използва в качеството на адрес в едно адресируемо запомнящо устройство, наречено хеш-буфер (буфер на функцията) или още хеш-таблица. Хеш-функцията, предложена по-горе, при модул ω=256, генерира цели числа Y в интервала [0, 255], които се използват в качеството им на адреси за достъп в хеш-буфера. Всяка клетка от хеш-буфера съдържа адрес на физическа страница. Тъй като обемът на хеш-буфера е 256 клетки, то необходимата за съхраняване на физическото съответствие таблица, има същия обем. Разбира се операция деление, пък дори и целочислено, представлява крайно нежелана функционалност, тъй като е много бавна и скъпа операция, ето защо хеш-стойността се изчислява чрез циклични кодови М-последователности. Техническата реализация на последните е лесна, тъй като се свежда до поразрядни логически операции.

Благодарение на случайния характер на резултатите от функцията, едно и също изходно число, което тя генерира, е възможно да се получи при различни входни числа (аргументи). Така става възможна ситуацията, при която по заявен от процесора номер на виртуална страница X, същият да се преобразува във вече използван (зает) в таблицата на страниците адрес Y. Това несъответствие, (тази нееднозначност) разбира се е недостатък, но както показва статистиката, преодоляването му не изисква големи разходи. Към таблицата на страниците се добавя така наречената “област за препълване”. Винаги, когато заявеният виртуален номер се проектира върху заета клетка в таблицата на страниците, неговият описател се помества в областта за препълване, където всички различни описатели, натрупани в съответствие на една и съща изходна хеш-стойност, образуват свързан списък. Статистическите наблюдения показват, че дължините на тези списъци на практика достигат максимум до няколко единици.

Отнесено за метафоричния пример, даден по-горе, обемът на хеш-буфера е 50, а дължината на свързаните списъци (колонки) – 20.

По този начин, ако заявената страница бъде отнесена към вече заета клетка в таблицата на страниците, окончателното съответствие се определя чрез претърсване на свързания с нея списък. Описаното съответствие между виртуалния и физическия странични адреси е илюстрирано чрез схемата от следващата фигура 6.4.1.4.

Фиг. 6.4.1.4. Двустепенно преобразуване на виртуален страничен адрес във физически

Наименованието на таблицата на страниците в тази схема произлиза от характера на хеш-функцията, с която читателят ще трябва да се запознае допълнително.

Независимо от икономията на оперативна памет, която се постига при този метод, приложението на обърнатата таблица на страниците има един съществен недостатък – записите в нея (аналогично на тези в асоциативната памет) не са сортирани по възходящ ред на номерата на виртуалните страници (вижте първата колонка на таблицата), което усложнява преобразуването на адресите. Именно това налага изграждане на свързаните списъци.

Асоциативно преобразуване

Както вече отбелязахме по-горе, ефективността на разгледаните методи за преобразуване на виртуалния адрес във физически е ниска, което се дължи на междинните обръщения (1 или 2) към съответния вид таблици, намиращи се в оперативната памет. Ускоряването на тези механизми се търси най-напред чрез:

1. Изваждане на таблиците от оперативната памет и реализацията им с допълнителни апаратни средства ;

2. Подмяната на прякото адресно преобразуване с асоциативно.

Същността на метода на асоциативно преобразуване се състои в идеята за подмяна на таблицата на страниците с друга, значително по-малка по обем (от 8 до 128 реда), апаратно реализирана таблица, достъпът в която да бъде асоциативен. Основанието за прилагане на асоциативния метод за достъп е в принципа на локалното действие. Принципът на локалното действие е основание за разработване на механизмите на кеш паметта и беше подробно изяснен в предидущите раздели. Твърди се, че на това ниво в йерархичната запомняща система, което тук разглеждаме, задачите които се решават са аналогични по характер и по тази причина приложението на този принцип тук е напълно оправдано. Асоциативната памет, която ще съдържа дескрипторите на страниците, се нарича буфер за бърза транслация на адресите – TLB-буфер (Translation Look-aside Buffer). Ефективността от използването на TLB-буферите се оценява чрез честотата на успешните адресни преобразувания (hit ratio).

TLB-буферът представлява своеобразна кеш памет със структура, съответстваща на задачата, която той ще решава. За разлика от кеш паметта, която кешира данни, TLB-буферът кешира адреси. Този буфер не може да отмени категорично наличието в оперативната памет на таблица на страниците, чието използване е наложително в ситуациите от типа page fault. Мястото на TLB-буфера е непосредствено до процесора, в състава на устройството за управление на паметта (MMU), където като апаратна структура той работи непосредствено с кеш паметта на първо ниво, както е изобразено в схемата от фигура 6.4.3.

Според принципа на локалното действие се приема, че в страничната таблица, чиято роля ще се играе от TLB-буферът, трябва да се съхранява моментното съответствие на страниците от оперативната памет. За да се реализира това съответствие, TLB-буферът следва да поддържа във всяка отделна своя клетка следната даннова структура:

Фиг. 6.4.1.5. Структура на елемент от TLB-буфер

Левите две полета на горната структура съставят асоциативната част на буфера, т.е. справочника, а дясното поле – данновата част, което е в пълно съответствие с дефинирането на кеш структурата (вижте фигура 6.3.2.2). В полето атрибути се съдържа: 1 бит за достоверност и 3 бита за количествена оценка на използвания критерий за избор на кандидат за изхвърляне (обикновено по критерия LRU, шеговито наречен “критерий за изхвърляне на старците”).

Необходимо е да припомним, че броят на реално възможните за използване от потребителя физически страници е много по-малък от възможния за адресното пространство. Освен това TLB-буферът е свързан с кеш паметта на първо ниво, ето защо броят на TLB-линиите следва да съответства на броя на кеш-линиите. Като пример в пункт 6.3.2.1, дадохме процесор на Intel, кеш-линиите в който са 128 на брой. При съответния обем Q на кеш паметта и при съответната дължина L на кеш-линията, броят на кеш-линиите, т.е. на TLB-линиите, могат да се определя от отношението Q/L. В случая на дадения пример имаме 4096[B]/32[B]=128.

В съвременните компютърни архитектури TLB-буферите работят съвместно с кеш паметта на първо ниво. Това е неизбежно по причина на това, че софтуерът съдържа виртуални адреси и в този смисъл е виртуален, а информацията, която той достига представлява кеш-копие на тази, която се намира във физическата памет. Тъй като кеш паметта е наборно-асоциативна, съдържащият се в справочната част на TLB номер на виртуална страница (20 бита), се дели на две части – старша част тег (17 бита) и младша част № на блок (3 бита). Младшите битове са 3, ако кеша е с 8 кратна асоциация.

Следващата схема от фигура 6.4.1.6 илюстрира схемата за взаимодействие между TLB-кеша и кеш паметта.

Фиг. 6.4.1.6. Структурна схема за връзка на TLB-кеша с кеш паметта

Ще комплектоваме структурната илюстрация на обясненията с алгоритмичната, която е представена на следващата фигура 6.4.1.7.

Фиг. 6.4.1.7. Обобщен алгоритъм за доставка на данни

Прекъсването, в резултат на което се стартират процесите по доставка и подмяна на страниците, както и връщането от това прекъсване, е изключително и то подлежи на специално пояснение, което ще дадем по-късно в отделен пункт.

Както вече споменахме, TLB-буферите неизбежно работят съвместно с кеш паметта и по тази причина те наследяват както тяхната йерархия, така и степента им на асоциативност. TLB-буферът, работещ съвместно с кеша на първо ниво, в повечето процесори е с пълна асоциация, докато този, на второ ниво – обикновено е наборно-асоциативен. Освен това TLB-буферите на първо ниво са още и хоризонтално разделени – съответно единият за данни, а другият за команди. В многоядрените архитектури всичко казано по-горе се дублира за всяко отделно ядро.

При TLB-пропуск на първо ниво (TLB-miss) процесорът се задържа минимум на 4 такта. Ако се получи TLB-пропуск на второ ниво, задръжката може да бъде от 10 до 200 такта, в зависимост от броя на претърсванията в таблицата на страниците и възникващите при това ситуации his/miss в кешовете L2 и L3.

TLB-буферите се използват съвместно с други буфери, които се поддържат от операционната система, наречени буфери за предистория на преобразованията – TSB-буфери (Translation Storage Buffer).

Различните “сценарии", които могат да се разиграят при осъществяване на достъп до данните, са обобщени на следващата фигура.

Фиг. 6.4.1.8. Йерархичен сценарий за достъп

В различните процесори има машинни команди, които могат да се използват за явно изчистване съдържанието на TLB-буферите, а други команди могат да направят това неявно, като следствие от определени ситуации. В структурата на процесора съществуват програмно достъпни регистри, с чиято помощ могат да се изпълняват манипулации върху съдържанието както на TLB-буферите така и на кеш паметите. Тези манипулации се наричат тестови, но ние няма да ги разглеждаме тук.

Процесорно ядро Cortex-A8 на ARM

В подкрепа на разглежданата тук тема, като един от многото възможни примери, ще представим кратко архитектурата на масово използваното процесорно ядро Cortex-A8. Това е конфигурируемо ядро, което поддържа архитектурата на командната система на процесор ARMv7. Предоставя се като ядро на IP (Intellectual Property - интелектуална собственост). IP ядрата са доминиращата форма на доставка в технологии за вграждане.

Cortex-A8 може да издава по две инструкции на такт с честота до 1[GHz]. Ядрото поддържа двустепенна йерархия на кеш паметта, като първото ниво е с архитектура Харвард – за команди и за данни (вижте фигура 6.3.2.1.1). Всяка една от тези кеш памети може да бъде с обем 16[KiB] или 32[KiB], с 4-степенна асоциативна структура, използваща алгоритъма на случайното заместване. Целта е да има еднократна латентност на достъпа до кешовете, което позволява на Cortex-A8 да поддържа забавяне от един цикъл, по-лесно извличане на команди, както и по-ниско наказание за извличане на правилната команда, когато се получи пропуск след условен преход, причинен след неудачен ход на предварителното извличане на команди. Кешът от второ ниво не е задължителен, но когато присъства, е с 8-степенна асоциативна структура и може да бъде конфигуриран с обем от 128[KiB] до 1[MiB]. Тя е организирана в една или четири банки, което може да позволи едновременното извършване на няколко прехвърляния от паметта. Външната шина обработва заявките към паметта и е широка от 64 до 128 бита. Кешът от първо ниво е практически индексиран и физически маркиран, а кешът от второ ниво е физически индексиран и маркиран. И двете нива използват 64-байтов размер на блока. Данновият кеш (D-кеш) е с обем 32 [KiB] и размер на страницата от 4 [KiB]. Всяка физическа страница може да се преобразува в два различни кеш адреса. Такива псевдоними се избягват хардуерно при откриване на пропуск.

Управлението на паметта се извършва от двойка TLB (за команди и за данни), всеки от които е с пълна асоциативност с 32 записа и променлив размер на страницата (4, 16, 64[KiB], 1 или 16[MiB]). Заместването в TLB се обслужва от round robin алгоритъм. Пропуските на TLB и заместването на таблиците в основната памет се обработват хардуерно. Следващата фигура показва как 32-битовият виртуален адрес се използва за индексиране на TLB и кешовете, като се приемат 32[KiB] първични кешове и 512[KiB] вторичен кеш, с размер на страницата 16[KiB].

Фиг. 6.4.1.9. Архитектура за адресация в ARM Cortex-A8

В рисунката не са показани битовете за валидност, за защита и битовете за предсказване.

Виртуална памет в Intel Core i7

Този процесор поддържа и трите вида преобразуващи структури. Виртуалната памет се поддържа от две таблици:

· Локална дескрипторна таблица – LDT (Local Descriptor Table) ;

· Глобална дескрипторна таблица – GDT (Global Descriptor Table).

Под дескриптор разбираме описател. Всяка програма притежава собствена локална таблица с дескриптори на страниците. Локалните дескриптори идентифицират сегментите на отделна програма – код, данни, стек и пр.

Глобалната таблица с дескриптори е единствена и се използва от всички програми. Нейните дескриптори описват системните сегменти, включително и на ОС.

За да получи достъп до кода на определен сегмент, най-напред селекторът (вижте фигура 6.4.2) се зарежда в сегментентния регистър CS на процесора. За да има достъп до данните на този код, се зарежда селектора на данновия сегмент в данновия сегментен регистър DS. Селекторите имат дължина 16 бита:

Фиг. 6.4.1.10. Селектор Core i7

Един от битовете на селектора показва какъв е той – глобален или локален. Старшите 13 бита представляват индекса или с други думи – номера на елемента в съответната таблица. Тези таблици имат обем 2¹³=8 [KiB]. Младшите два бита определят нивото на защита. Дескриптор с индекс 0 е недействителен и опитите той да бъде използван генерират прекъсване (изключение).

По заредения селектор от съответната таблица (GDT или LDT) се извлича дескрипторът на указаната таблица на дескрипторите и се зарежда във вътрешните регистри на устройството за управление на паметта, след което може бързо да се получи достъп в оперативната памет. Този дескриптор е с дължина 64 бита (8[B]). В него се намира базовият адрес на сегмента, дължината му и друга информация, както е показано на фигурата по-долу.

Фиг. 6.4.1.11. Сегментен дескиптор за код в Core i7

Където:

· Бит G=0 означава, че числото в полето LIMIT показва брой байтове ;

· Бит G=1 означава, че числото в полето LIMIT показва брой страници ;

· Бит D=0 означава, че сегментът е 16 битов ;

· Бит D=1 означава, че сегментът е 32 битов ;

· Бит L=1 означава 64-битов кодов сегмент (L=0 само за режим IA-32) ;

· AVL Предлага се за използване от системен софтуер ;

· Бит P=0 означава, че сегментът не се съдържа в паметта ;

· Бит P=1 означава, че сегментът се съдържа в паметта ;

· Дву-битовето поле DPL означава нивото на защита ;

· Бит S означава тип на дескриптора (S=0 при системен, S=1 – кодов или даннов) ;

· Полето TYPE изразява типа на сегмента и защитата му.

След като се зареди селектора в сегментния регистър CS, той се копира във временен регистър на диспечера на паметта, където 3 младши бита се нулират. Така 13 битовото поле от селектора се интерпретира като умножено на числото 8. Към така полученото число се добавя адрес от локалната или от глобалната таблица на дескрипторите (който се съхранява във вътрешен регистър на диспечера на паметта). В резултат се получава указател на дескриптор.

От структурната двойка <селектор ; отместване> се получава физическият адрес по следния начин: според заредения сегментен регистър апаратурата намира във вътрешните регистри пълния дескриптор, съответстващ на дадения селектор. Ако този сегмент не съществува (селектор 0) или в дадения момент не се намира в паметта (Р=0) тогава се генерира изключение. В първия случай това е програмна грешка, а във втория се изисква от ОС да извика нужния сегмент.

След това апаратурата проверява дали отместването не излиза извън пределите на сегмента. Ако излиза, отново се генерира изключение. В дескриптора трябва да съществува 32-битово поле за размера на сегмента, но там са налични само 20 бита, което води до друга схема. Ако полето G в дескриптора (Granularity – степен на детайлизация) съдържа 0, то полето LIMIT (максимална стойност) определя максимален размер за сегмента в байтове (до 1[MiB]). Ако в полето G има 1, то полето LIMIT съдържа размера на сегмента в брой страници. Размерът на страницата в процесор Core i7 никога не е по-малък от 4[KiB], по която причина споменатите 20 бита са достатъчни за означаване на размера на сегменти, които имат до 2³² байта, което може да се покаже така:

4K = 4,096 ,

2²⁰ = 1,048,576 ;

2²⁰.4K = (1,048,576).( 4,096) = 4,294,967,296 = 2³² .

Ако сегментът се намира в паметта, и отместването не излиза извън неговите граници, тогава съдържанието на 32 битовото поле BASE (базов адрес) в дескриптора се събира с отместването, като в резултат се получава линейният адрес, схематично показано на следващата фигура.

Фиг. 6.4.1.12. Схема за изчисляване на линейния адрес в Core i7

32-битовият базов адрес се разделя на 3 части, които се поставят в дескриптора, както е показано на фигура 6.4.1.10. С това се осигурява съвместимост с по-старите модели на процесорите Intel, в които полето BASE има дължина 24 бита. Схемата на преобразуване осигурява за сегмента всеки един произволен адрес в 32 битовото адресно пространство да може да бъде начален, поради което той се нарича линеен.

Ако разделянето на страници е блокирано (това определя съответен бит в глобалния регистър за управление), линейният адрес се възприема като физически и се използва в оперативната памет за извършване на основна операция. Така при блокировка, се реализира “чиста” схема за сегментация, при която всеки базов адрес присъства в дескриптора. Схемата допуска припокриване на сегментите.

Ако разделянето на страници не е блокирано, линейният адрес се възприема като виртуален и се преобразува във физически при използване на таблицата на страниците. Виртуалният адрес се дели на три полета, както илюстрира следващата фигура.

Фиг. 6.4.1.13. Структура на виртуалния адрес

Всяка работеща програма има своя таблица на страниците, която се състои от 1024 елемента с дължина 32 бита. Нейният начален адрес се съдържа в глобалния регистър. Схемата за преобразуване на виртуалния адрес във физически е следната.

Фиг. 6.4.1.14. Формиране на физическия адрес

Както се вижда, съдържанието на полето DIR се използва като указател към началния адрес на нужната таблица на страниците. Полето PAGE се използва като отместване за да може да се извлече указател към съответния кадър на страница. С отместването OFF се формира окончателният физически адрес за достъп до съответната клетка в ОП.

Всеки елемент в таблицата на страниците има дължина 32 бита, 20 от които представляват номер на страничния кадър. Останалите 12 бита включват:

· Бит за достъп ;

· Битове за изменения, които се установяват от апаратурата в помощ на ОС ;

· Битове на защитата ;

· Други.

Всяка таблица на страниците съдържа 1024 елемента на страничните кадри, всеки от които е с обем от 4[KiB], така в резултат една таблица на страници описва 4[MiB] оперативна памет. Сегмент, който е по-къс от 4[MiB] ще има в каталога на страниците един елемент, който представлява указател на единствена таблица на страници. Така късите сегменти представляват само две страници.

За да се избегнат повторни обръщения към ОП, диспечерът на паметта съдържа вградена апаратура за поддържане на алгоритъм за търсене на наскоро използвани комбинации от полетата DIR-PAGE и тяхното отражение във физически адреси на съответния страничен кадър. Действията, показани на горната фигура 6.4.1.13, се изпълняват само в случаите, когато текущата комбинация е била използвана отдавна.

При разбиването на страници, в полето BASE на дескриптора е напълно възможно да бъде записана нула (0). Полето BASE е необходимо само да се получи неголямо отместване за достъп до елемент в средата на каталога. Това поле е включено в дескриптора за реализация единствено на чистата сегментация (без страници), както и за съвместимост с по-стари модели, в които няма разделяне на страници.

Разширен физически адрес

Ще добавим още малко конкретика за връзката между виртуалния и физическия адреси. Таблицата на разширените физически адреси PAE (Physical Address Extension) е внедрена в структурата на процесор Intel Pentium Pro за първи път през 1995 г., въпреки че придружаващите го чипсети обикновено не са поддържали необходимите допълнителни адресни битове. Таблицата на разширения физически адрес PAE се поддържа и от следващите (след 2003 година) поколения процесори на Intel, както и от тези на AMD.

След като AMD определи своето 64-битово разширение на процесорната стандартна индустриална архитектура x86 (AMD64 или x86-64), в нея, чрез използване на таблицата PAE, вече беше подобрена системата за странициране в "дълъг режим",. Така тези процесори поддържат 64-битови виртуални адреси (в които физическият адрес е с дължина 52 бита).

С използването на разширения физически адрес записът в таблицата на страниците в архитектурата x86 се увеличава от 32 на 64 бита. Това позволява по-голяма дължина (място) за същинския физически адрес на страницата или полето "номер на рамката на страницата", което поддържа таблицата на страниците (наречено по-горе индекс). В първоначалните реализации на PAE, полето за номер на рамката на страницата е разширено от 20 на 24 бита. Размерът на "отместването на байта" от адреса, който се превежда, все още е 12 бита, така че общият размер на физическия адрес се увеличава от 32 бита на 36 бита (т.е. от 20+12=32 на 24+12=36). Това позволява увеличаване обема на физическата памет, който теоретично може да достигне адресираното от CPU пространство до 64 [GiB].

При първите процесори, които поддържат разширения физически адрес (PAE), поддръжката за това е очевидна в изводите на съответната интегрална схема, в която обозначенията на адресните изводи стигат до A35, вместо да спират на A31. По-късните семейства процесори използват междусистемни връзки като Hypertransport или QuickPath Interconnect, при които липсват специални сигнали за адрес на паметта, така че тази връзка е по-малко очевидна.

32-битовият размер на виртуалния адрес не се променя, така че обикновеният приложен софтуер продължава да използва машинни команди с 32-битови адреси и (в модел с плоска памет), което ограничава обема на виртуално адресно пространство до 4 [GiB]. Операционните системи, поддържащи този режим, използват таблици на страници, за да картографират обикновеното виртуално адресно пространство от 4 [GiB] във физическата памет, което, в зависимост от операционната система и останалата хардуерна платформа, може да достигне до 64 [GiB]. Картографирането обикновено се прилага отделно за всеки процес, така че допълнителната RAM памет е полезна, въпреки че нито един процес не може да има достъп до всички едновременно. По-късно работата, свързана с разработването на архитектура x86-64 от AMD, позволи да бъде разширен теоретично възможния размер на физическите адреси до 52 бита.

Логическа структура на таблиците на страниците

В защитен режим с разрешен пейджинг (бит 31, наречен PG, в управляващия регистър CR0, е установен), но без PAE, процесорите x86 използват двустепенна схема за преобразуване. Управляващият регистър CR3 съдържа физическия адрес на каталога на страниците (page directory) с обем от 4 [KiB]. Таблицата, наречена каталог, съдържа 1024 четири байтови записи, които от своя страна, ако са валидни, съдържат подравнените базови физически адреси на създадените за процеса таблиците със страници, всяка с обем 4 [KiB]. По подобен начин и те се състоят от 1024 записа в таблица с четири байтови адреси на страници, които, от своя страна, ако са валидни, съдържат подравнените по страници физически адреси на 4 [KiB] дълги страници от физическа памет (RAM).

Активирането на разширения физически адрес PAE (чрез установяване на бит 5 (PAE) в системния регистър CR4) причинява големи промени в тази схема. По подразбиране размерът на всяка страница остава 4 [KiB]. Всеки запис в таблицата на страниците и директорията на страници става дълъг 64 бита (8 байта), вместо 32 бита, за да позволи допълнителни адресни битове. Размерът на всяка таблица обаче не се променя, така че и таблицата, и директорията вече имат само по 512 записа. Тъй като това позволява само една половина от вписванията на оригиналната схема, е добавено допълнително ниво на йерархия, така че CR3 да сочи физически към таблица с указатели на каталога на директориите на страници (Page Directory Pointer Table) (кратка таблица, съдържаща четири указателя към директории на страници).

Записите в каталога на страниците имат допълнителен флаг в бит 7, наречен PS (page size). Ако системата е установила този бит в 1, записът в каталога на страниците не сочи към таблица със страници, а към една голяма страница от 2 [MiB] (страница с разширен размер - Page Size Extension (PSE)). Това е режим за работа на вградения блок за управление на паметта на процесори х86, в които се използват страници с обем от 4 (32-битови странични таблици) или 2 мегабайтови (64-битови странични таблици с РАЕ) в допълнение към обикновените 4 килобайтови страници в архитектури от вида х86. Освен това съществува разширение PSE-36, което използва 4 от свободните младшите битове на указателя на каталога на страниците в качеството им на старши битове във физическия адрес. Така става възможно да се адресира оперативна памет с обем до 64 [GiB] без да се включва режим на разширен физически адрес РАЕ. При това в този режим могат да се създават само "големи" 4 [MiB] страници.

Във всички формати на таблиците на страници, поддържани от x86 и x86-64, 12-те най-младши бита от записа в таблицата на страниците или се интерпретират от блока за управление на паметта, или са запазени за използване от операционната система. В процесорите, които реализират функцията "no-execute" (без изпълнение) или "execution disable" (забрана за изпълнение), най-значимият бит (бит 63) е битът NX. Следващите единадесет (11) най-старши бита (битове от 52 до 62) са запазени за използване от операционната система на архитектурните спецификации на Intel и AMD. По този начин, от 64 бита в записа в таблицата на страниците, 12-те младши бита и 12-те старши бита, имат други приложения, оставяйки 40 бита (битове от 12 до 51) за физически адрес на страница. В комбинация с 12 бита "offset within page" (отместване в рамките на страница) от линейния адрес, са налични максимум 52 бита за адресиране на физическата памет. Това позволява максимална конфигурация на RAM в обем от 2⁵² байта или 4 [PiB] петабайта (около 4,5.10¹⁵ байта).

В процесори x86-64 в естествен дълъг режим (long mode), схемата за преобразуване на адресите използва PAE, но добавя четвърта таблица, която съдържа 512 записа с разпределение на страниците от ниво 4 и разширява таблицата с указател на директория на страници до 512 записа вместо оригиналните 4 записа, когато тя е в защитен режим. Обикновено се преобразуват 48 бита от номер на виртуална страница, което дава виртуално адресно пространство до 256 [TiB].  В записите в таблицата на страниците, в оригиналната спецификация, са внедрени 40 бита физически номер на страница.

Фиг. 6.4.1.15. Структура за преобразуване без РАЕ и 4 [KiB]-ви страници

Фиг. 6.4.1.16. Структура за преобразуване без РАЕ и 4 [MiB]-ви страници

Фиг. 6.4.1.17. Структура за преобразуване с РАЕ и 4 [KiB]-ви страници

Фиг. 6.4.1.18. Структура за преобразуване с РАЕ и 2 [MiB]-ви страници

Апаратна поддръжка

Софтуерът може да идентифицира чрез CPUID флаг PAE и да разбере дали процесорът поддържа режим на разширен физически адрес PAE или не. Съществува безплатна програма за Microsoft Windows, която ще изброява много възможности на процесора, включително поддръжка на PAE. В Linux команди като cat /proc/cpuinfo могат да открият наличието на флаг PAE, когато той присъства, както и други инструменти, като инструмента за откриване на хардуер SYSLINUX.

За да стартирате процесора в режим PAE, е необходима поддръжка от операционна система. За да използвате PAE за достъп до повече от 4 [GiB] RAM, е необходима допълнителна поддръжка в операционната система, в чипсета и на дънната платка. Някои чипсети не поддържат адреси на физическа памет над 4 [GiB] (FFFFFFFF в шестнадесетична форма), а някои дънни платки просто нямат достатъчно RAM гнезда, за да позволят инсталирането на повече от 4 [GiB] RAM. Независимо от това, дори ако не са налични и достъпни повече от 4 [GiB] RAM, процесор с PAE може да работи в режим PAE, например, за да позволи използването на функцията “No execute".

Ние приемаме, че изложеното до момента осветлява темата на този раздел достатъчно подробно, за да може Читателят да се справи самостоятелно както с други конкретни структури, така и с такива, които вероятно ще се появяват в бъдеще.

Следващият раздел е:

6.4.2. Алгоритми за заместване на страници