Спец часть (часть 2) (3 поток) (2015) (by Кибитова) (1161602), страница 21
Текст из файла (страница 21)
ирежимов10-разрядноесмещениев соответствующейтаблицевторогоуровняиерархии.Преобразование виртуального адреса в физический имеет достаточно простуюорганизацию(Рис. 143).Наоснове виртуального адреса, посредством использованияВиртуальныйадресВиртуальныйадресинформации из таблиц LDT и GDT, получается 32-разрядный линейный адрес, которыйинтерпретируетсяв Использованиетерминахселекторадвухуровневойиерархическойстраничнойорганизации.Использованиеи содержимоготаблицLDTи GDTселектораи содержимоготаблицLDTи GDTПоследние 12 разрядов отводятся под смещение в физической странице, а первые 20разрядов интерпретируюткак 10-разрядный индекс во «внешней» таблице групп страницЛинейныйадресадресЛинейныйи 10-разрядное смещение в соответствующей таблице второго уровня иерархии.P110ДвухуровневаястраничнаяорганизацияДвухуровневаястраничнаяорганизацияВиртуальный адресP1P2 P2 offsetoffsetИспользование селектора и содержимого таблиц LDT и GDT1010 1012 12Линейный адресДвухуровневаястраничная организацияФизическийФизическийадресадресP1P2offsetРис.
143. Схема преобразования адресов.Рис. 143.Схема преобразования адресов.101210 Среди особенностей данной модели можно отметить, что можно «выключать»Среди особенностей данной модели можно отметить, что можно «выключать»страничную функцию, и тогда модель Intel начинает работать по сегментномустраничную функцию, и тогда модель Intel начинает работать по сегментномураспределению. А можно не использовать сегментную организацию процесса, и тогдараспределению. А можноне использоватьсегментную организацию процесса, и тогдаадрес по страничному распределению памяти.данная реализацияФизическийбудет работатьданная реализация будет работать по страничному распределению памяти. Рис.
143. Схема преобразования адресов.Среди особенностей данной модели можно отметить, что можно «выключать»страничную функцию, и тогда модель Intel начинает работать по сегментному Пусть имеется синтаксическое дерево выражения. Предположирегистров осуществляется по простейшей схеме сверху-вниз слгенерациикода для поддерева LR занято n регистров. Пусть по9. Алгоритм Сети-Ульмана оптимального распределения регистров и егоподдеревоR – nr регистров.
Если nl = nr, то при вычислении Lобоснование.9. Алгоритм Сети-Ульмана оптимального распределения регистров ипод результатбудетзанят (n+1)-й регистр. Еще nr(= nl)ирегистр9. АлгоритмСети-Ульмана оптимального распределения регистровегообоснование.его обоснование.вычисленииR. Таким образом, общее число использованных рЕсли nl > nr, то при вычислении L будет использованоnl регистПусть система командимеет неограниченноечислоуниверсальныхрегистров,использованоnr <машиныnl регистров,и всегобудетиспользованонеПустьсистемакомандмашиныимеетнеограниченноечислоуниверсальныхрегистров,в которых выполняются арифметические команды. Рассмотрим, как можнов которыхвыполняютсяарифметическиекоманды.Рассмотрим,выражениякак можнокод,используядля данногоарифметическогоnr,сгенерироватьтопослевычисленияL подрезультатбудетзанят один регисгенерироватькод,используядляданногоарифметическоговыраженияминимальное число регистров.регистровбудетиспользовано для вычисления R.
Всего будет иминимальноечисло регистров.Rn /\ \Rn /\ \||/ \/ \R1 /\ \18R1 /\ \-- /\-- /\R2 /\ \R2 /\ \-- /\-- /\-- \-- \/\LR/\LRL/\/\RL/\/\R------Рис. 8.13Рис. 8.13Предположим сначала,что распределениерегистров осуществляетсяпоОбоснованиеалгоритма(минимальностьчисла используемыхрПредположим сначала,что распределениерегистров осуществляетсяпопростейшей схеме слева-направо, как изображено на рис. 8.13. Тогда к моментупростейшей схеме слева-направо, как изображено на рис. 8.13. Тогда к моментуограничениях).генерациикодадляподдереватребует nlnlгенерации кода для поддереваLRLR занятозанятоnnрегистров.регистров. ПустьПусть поддеревоподдерево LL требуетрегистров,а аподдеревоRR- -nrnrрегистров.ЕслиLL будетбудет до порядкаВидно,чтодля деревьев,совпадающихс точностьюрегистров,поддереворегистров.Еслиnl=nr,nl=nr,тото припри вычислениивычислениииспользованоииподзанятn+1-йnr (=nl)(=nl)использованоnlnlрегистроврегистровподрезультатрезультатбудетбудетзанятn+1-й регистр.регистр.
ЕщеЕще nrминимальноечислорегистровприраспределенииихслева-напрегистровчислорегистровбудетбудетиспользованоиспользованоприпри вычислениивычисленииR.R. ТакимТаким образом,образом, общееобщее числокоторогов каждойвершинеслеварасположеноболее"сложноеиспользованныхбудетиспользованныхрегистроврегистровбудетбудетравноравноn+nl+1.n+nl+1.ЕслиЕслиnl>nr,nl>nr, тото припри вычислениивычислении LL будетиспользованоnlnlрегистров.ПриRR будетnr<nlрегистров,числарегистров.Такимобразом,еслииспользованодерево таково,чтоиспользованорегистров.При вычислениивычислениибудетиспользованоnr<nl регистров,ии в кажвсеговсегобудетбудетиспользованоиспользованоненеболееболее чемчем n+nln+nlрегистров.регистров.поддеревотребуетменьшегочисларегистров, чем левое, то, обЕсливычислениябудетрегистрЕслиnl<nr,nl<nr,тотопослепослевычисленияLLподподрезультатрезультатбудет занятзанятодинрегистроптимальнораспределитьрегистры.Безодинперестройкидерева эт(предположимR.
ВсегоВсего(предположимn+1-й)n+1-й) ииnrnrрегистроврегистров будетбудетиспользованоиспользовано длядля вычислениявычисления R.вершинедереваn+nr+1справарасположеноболее сложное поддерево,будетрегистров.будетиспользованоиспользованоn+nr+1регистров.Видно,Видно,чточто длядлядеревьев,деревьев, совпадающих сточностьюдодопорядкакаждойминимальноерегистров приприточностьюпорядкапотомковкаждой вершины,вершины,минимальное число регистровнего,а затемужепотомковдля левогоподдерева.распределениираспределенииихих слева-направослева-направо достигаетсядостигается нана дереве,дереве, уу которогокоторого в каждойРазметкадерева.вершинечиславершинеслеваслеварасположенорасположеноболееболее"сложное""сложное"поддерево,поддерево, требующеетребующее большего числа1) если вершина – правый лист или дерево состоит из единстввершину числом 1, если вершина – левый лист, помечаем еиспользованных регистров будет равно n+nl+1. Если nl>nr, то при вычислении L будетиспользовано nl регистров.
При вычислении R будет использовано nr<nl регистров, ивсего будет использовано не более чем n+nl регистров.Еслиnl<nr, то послевычисленияL под результатn+nбудетодин регистрвычисленияR. Всегобудет использованорегистров.r+1занятвычисленияВсегоиспользованоn+nrr+1+1регистров.вычисленияR.R.n+1-й)Всегобудетиспользованоn+n(предположимибудетnrдеревьев,регистровбудет использованодля вычисленияR.
ВсегоВидно,чтодлясовпадающихсрегистров.точностьюдо порядкабудетиспользованорегистров. совпадающихВидно,что для деревьев,совпадающихс приВидно,каждойчтоn+nr+1длявершины,деревьев,совпадающихточностьюдо порядкапорядкаВидно,чтодлядеревьев,ссчислоточностьюдопотомковминимальноерегистровпотомковдокаждойкаждойвершины,минимальноечислорегистровприточностьюпорядкакаждойвершины, минимальноечислорегистровпотомковвершины,минимальноеприраспределенииих потомковслева-направодостигаетсяначислодереве,регистрову котороговприраспределенииихслева-направодостигаетсяна "сложное"дереве,которогораспределенииихихслева-направодостигаетсянаболеедереве,у которогокаждой ввкаждойвершинеслева расположеноподдерево,распределениислева-направодостигаетсянадереве,уу вкоторогокаждой слевавершинеслеварасположеноболее "сложное""сложное"поддерево,вершинерасположено"сложное" поддерево,требующее большегочислатребующеебольшегочислаболеерегистров.каждойвершинеслеварасположеноболееподдерево,требующеебольшегочисларегистров.Такимобразом,еслидерево таково, что в каждой внутреннейтребующеебольшегочисларегистров.Такимобразом,еслидеревотаково,что вврегистров,каждой внутреннейвнутреннейрегистров.Такимобразом,еслитаково,что в каждойвнутреннейвершиневершинеправоеподдеревотребуетменьшегочислачемлевое,Такимобразом,еслидереводеревотаково,чтокаждойвершинеправоеподдеревотребуетменьшегочисларегистров,чемлевое,то, поддеревообходядеревослеватребуетнаправо,можночемоптимальнораспределитьправоетребуетменьшегочисламеньшегорегистров,левое,то, обходядеревовершинеправоеподдеревочисларегистров,чемлевое,то, обходяобходя можнодеревооптимальнослева направо,направо,можнооптимальнораспределитьрегистры.слеванаправо,распределитьрегистры.Без перестройкидеревато,деревослеваможнооптимальнораспределитьрегистры.Без перестройкидеревавершинеэто означает,еслив некоторойвершинерегистры.этоозначает,что если в некоторойдеревачтосправарасположеноболеесложноеБезперестройкидереваэтоозначает,чтоесливнекоторойвершинедеревасправаболеесложноеподдерево,то поддерева.сначалаБез топерестройкидерева этоозначает,есливершинеподдерево,сначаларасположеносгенерируемкоддля него,ачтозатемужев некоторойдля левогодеревасправарасположеноболеесложноеподдерево,тосначаласгенерируемдля него, образом.а затемужедлялевого поддерева.деревасправакодрасположеноболеесложноеподдерево,то сначалаАлгоритмработаетследующимСначалаосуществляетсяразметкасгенерируемкоддлядлянего,него,ааследующимзатемужеужедлядлялевогоподдерева.поддерева.Алгоритмработаетобразом.Сначалаосуществляетсясгенерируемкодзатемлевогосинтаксическогодеревапо следующимправилам.Алгоритмработаетследующимобразом.Сначалаосуществляетсяразметкасинтаксическогодеревапоследующимправилам.Алгоритм работает следующим образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
