andrey

Путь к Файлу: /Организация ЭВМ / Лекции ВМ-91 / Glava_5.4_3.3_brigada8 / 5.4.doc

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   0
Пользователь:   andrey
Добавлен:   13.01.2015
Размер:   285.0 КБ
СКАЧАТЬ

5.4    Допустимые процедуры обработки прерываний

МЫ предназначаем прерываниям поведение, подобное вызовам процедур. Механизм предыдущего раздела определяет соответствующий механизм вызова и возврата. К сожалению, обработчики не генерируются компилятором, поэтому программист имеет много возможностей для хака, который создаст механизм, поведение которого не похоже на вызовы процедур. Очевидная точка атаки – поля IS.EHR. Очевидно, манипуляции с IS.TOP.EDPC допускают переход куда угодно.

Если стек прерываний не на постоянной странице памяти, каждое прерывание, включая прерывание отсутствия страницы (page fault) , может привести к прерыванию отсутствия страницы, и т.д. Можно указать множество таких ловушек. Тогда очевиден интересный вопрос: мы все это проигнорировали?

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

 

5.4.1    Ряд ограничений

Процедура обработки прерываний называется допустимой, если она выполняет следующий  ряд ограничений:

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

(a) Указатель стека прерываний ISP пишется только при save и restore.

(b) Сегменты кадра IS, которые зарезервированы для регистров EHR, обновляются только в save.

2. ISR должен писаться в соответствии со следующими ограничениями:

(a) Команда rfe используется только как последняя команда ISR.

(b) Кодовые сегменты save и restore избегают любых немаскируемых внутренних прерываний; в данной архитектуре DLX это прерывания j с 0 < j < 6.

(c) Каждый обработчик H(j) избегает любых немаскируемых внутренних прерываний i с приоритетом i >= j.

(d) Если обработчик H(j) использует специальное перемещение с исходным регистром R для обновления регистра состояния SR, тогда R[i] = 0 для любых i >= j.

Между прочим, условия b) и c) требуют, чтобы pages fault избегались в некоторых обработчиках. Это может быть обеспечено, только если стек прерываний IS и коды save и restore находятся на постоянных страницах, т.е., на страницах, которые не могут быть выгружены из основной памяти. Пусть jp означает уровень приоритета отсутствия страницы (page fault) pff. Для любого j <= jp  обработчик H(j) и все данные, к которым обращается H(j) также должны находиться на постоянных страницах.

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

3. Приоритеты прерываний назначаются так, что

(a) Не маскируемые внешние прерывания имеют тип abort и имеют наивысший приоритет j = 0.

(b) Маскируемые внешние прерывания имеют тип continue и имеют более низкий приоритет, чем любое внутреннее прерывание,

(c) Если команда может одновременно вызвать различные внутренние прерывания, наивысший приоритет из всех вызванных прерываний должен иметь тип repeat или abort.

Назначение приоритетов прерываний используемое нашей конструкцией DLX (таблица 5.2) удовлетворяет этим ограничениям.

Условия 1 и 2 должны выполняться независимо от того, прерывается или нет обработчик H(j). Этого трудно достигнуть, поскольку ISR другого прерывания могло исказить структуры данных и регистры используемые H(j). Как следствие, H(j) может вызвать обращение к памяти с нарушением границ или переписать поле EHR в стеке прерываний.

Следующий метод может, к примеру, защитить стек IS от незаконных изменений. Кроме регистров EHR кадр стека IS также возвращает данные, которые менее критичны, например, универсальные регистры. Следовательно, он пригоден для использования двух стеков, один для регистров EHR и один для оставшихся данных. Тогда стек EHR может быть размещен в специальной странице памяти, которая является страницей только для чтения для всех, кроме кода save.

 

5.4.2    Скобочные структуры

Кодовые сегменты save и restore могут быть интерпретированы как левая и правая скобка, соответственно. Прежде чем мы сможем установить, что допустимые процедуры обработки прерывания ведут себя подобно подпрограммам, мы должны рассмотреть концепцию скобочных структур.

Для последовательностей S = S1... St скобок '(' и ')' мы определяем

l(S)    =   число левых скобок в S

r(S)    =   число правых скобок в S.

Последовательность S называется скобочной структурой если

5.4

т.е, число левых скобок равно числу правых скобок, и в префиксах S правых скобок не больше чем левых.

Очевидно, если S и Т - скобочные структуры, тогда (S) и ST также скобочные структуры. В скобочных структурах S можно объединять скобки по следующему алгоритму:

Для всех правых скобок R слева направо делаем: { пара R с левой скобкой L непосредственно левее R;отмена R и L из S;}

Вышеупомянутый алгоритм выполняется по кругу k = 1,2,.... Пусть R(k) и L(k) - правая и левая скобка парные в круге k, и пусть S(k) - строка S перед кругом k. Мы имеем S(1) = S. Индукцией по k покажем

Лемма 5.1 

L          R(k) – самая левая правая скобка в S(k),

2.         L(k) существует, и

3.         часть Q принадлежащая S от L(k) до R(k) – скобочная структура.

Доказательство оставлено в качестве упражнения. Видно, что вплоть до круга k, вышеупомянутый алгоритм работает только с префиксом S1... R(k) строки S.

5.4.3    Свойства допустимых процедур обработки прерываний

Мы начнем с некоторых определений. Сначала мы определим уровень прерывания il в ситуации, когда последовательность save не прерывается:2

5.4

Последовательность команд SAVE H RESTORE называется образцом ISR(j) если в течении H уровень прерывания равен

         il = j.

Она называется не прерывающимся выполнением ISR(j) если уровень прерывания подчиняется

il   =   j   в течении save и restore

                                  il   <=   j   в течение H.

Таким образом, в течение выполнения ISR(j) обработчик H(j) может быть прерван. Мы не рассматриваем бесконечное выполнение.

Предположим, что H не заканчивается последовательностью restore уровня  прерывания j, тогда

save1 h SAVE2 H' restore

называется прерывающимся выполнением ISR(j) если

il          =         j           в течении SAVE1

il          <=       j           в течении H

il          <=       2          в течении SAVE2, H' и RESTORE.

 

Мы называем выполняющуюся процедуру обработки прерываний правильно вложенной или проще вложенной, если

1. прерван не кодовый сегмент save или restore,

2. последовательность кодовых сегментов save и restore формирует начальный сегмент соответствующей скобочной структуры, и если

3. парные скобки принадлежат примеру некоторого ISR(j) в следующем значении: Пусть L и R парные последовательности save и restore. Пусть H состоит из команд между L и R

(a) которые не принадлежат последовательностям save и restore, и

(b) которые не включаются парными скобками внутрь L и R.

Тогда L H R образец некоторого ISR(j).

Мы называем выполнения совершенно вложенными если они правильно вложены и последовательность saves и restores формирует соответствующую скобочную структуру. В следующих доказательствах мы установим, что

 

Теорема 5.2

Выполняющиеся допустимые процедуры обработки прерываний являются  правильно вложенными,

Сперва мы установим свойства вполне вложенных выполнений процедур обработки прерываний в лемме 5.3.  В лемме 5.4 мы докажем индукцией существование скобочной структуры. В шаге индукции мы применим лемму 5.3 к части скобочной структуры, чье существование уже гарантировано индукционной гипотезой.  В частности, нам нужны некоторые усилия для доказательства, что restores никогда не прерывается. Тогда теорема следует непосредственно из лемм 5.3 и 5.4.

Лемма 5.3

Пусть механизм прерывания подчиняется программным ограничениям 1 - 3. Рассмотрим совершенное вложенное выполнение ISR(j). Последовательность выполняемых команд имеет форму

5.4

тогда мы имеем:

1. Если выполнение ISR(j) не прервано, тогда стек прерываний IS хранит одно и то же количество кадров до и после ISR(j), и сегменты IS, зарезервированные для регистров HER, остаются неизменными, т.е.,

ISPa-1 = ISPd    и   IS.EHRa-1 = IS.EHRd .

5.42. Точность. Если ISR(j) не прервано, выполнение продолжается с

 

 

с масками

5.4
 

 

 


ДОКАЗАТЕЛЬСТВО

Доказательство индукцией по числу n прерываний, которые прерывают выполнение ISR(j).

n = 0. Выполнение ISR(j) непрерывно. Так как прерывание j является непрерывным, save размещает новый кадр на стеке IS а restore снимает один кадр. Обработчик H(j) сам не изменяет указатель стека (ограничение 1), таким образом

ISPa-1 = ISPd .

Согласно ограничению 1, поля EHR на стеке прерываний IS пишутся только SAVE. Однако SAVE просто модифицирует один кадр IS, который удаляется restore. Таким образом

IS.EHRa-1 = IS.EHRd ,

и требование 1 выполняется. Что касается требования 2, мы покажем только точность масок SR; точность PC может быть показана тем же путем.

            SRd   =   ESRd-1               по определению rfe

=   IS.TOP.ESRc-1                   по определению restore ,

где IS.TOP означает верхний кадр стека IS. Так как сам обработчик не модифицирует ни указатель стека ISP, ни поля EHR на стеке IS (ограничение 1), из этого следует

                        IS.TOP.ESRc-1    =   IS.TOP.ESRb

                     =   ESRa-1               по определению save ,

и по определению влияния JISR тогда следует, что

5.4

В шаге индукции мы решаем от n до n+ 1. Выполнение ISR(j) прерывается n+1 прерываниями, и коды SAVE и RESTORE соответствующих примеров ISR формируют надлежащую скобочную структуру. Так как save и restore непрерывны, существует m верхнеуровневых пар скобок в потоке команд обработчика H(j); каждая пара соответствует примеру ISR( jr ):

5.4

Каждый ISR( jr ) прерывается самое большее n раз, и из-за индукционной гипотезы они возвращают указатель ISP и поля EHR на стек неизмененными:

5.4

Так как команды обработчика H(j) не изменяют эти данные, из этого следует для указателя ISP, что

5.4
 

 


5.4Тоже верно для полей EHR стека прерываний:

 

 

Так как restore удаляет кадр, добавленный SAVE, и так как save

только обновляет поля EHR в верхнем кадре, требование 1 выполняется для n + 1. Точность ISR(j) может быть выражена подобно случаю n = 0, за исключением равенства

IS.TOP.EHRb = is.top.ehrc-1 .

Однако, это равенство действительно из-за уравнения 5.2.

Лемма 5.4

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

ДОКАЗАТЕЛЬСТВО

Мы выполним за три шага:

1. save никогда не прерывается: Согласно программному ограничению 2, коды save и restore избегают любого немаскируемого внутреннего прерывания. Сброс – единственное немаскируемое внешнее прерывание, но нас интересует только не прерывающееся выполнение. Таким образом, SAVE и RESTORE могут прерываться только маскируемыми прерываниями.

Если команда Ii вызывает прерывание, все маски очищаются, т.е., SRi = 0, и инициализируется переход на ISR: JISRi = 1. В коде save маски обновляются только последней командой. Так как новые маски применяются к более поздним командам, save также не может быть прервано маскируемыми прерываниями.

2. Код restore избегает немаскируемых прерываний, и только последняя команда обновляет регистр состояний. Таким образом, restore не может быть прервано, если оно начинается с SR = 0. Последняя команда любого non-aborting обработчика прерываний – специальное перемещение

SR := GPR[0] = 0.

Если это специальное перемещение не прерывается, тогда restore также не прерывается.

3. Пусть код restore включает команды R1 ... RS. Обратите внимание, что конструкция процедуры обработки прерываний каждого примера ISR стартует с save и – в случае если не прерывается - она выполняет позже точно одну первую команду R1 из последовательности restore. Поэтому, в выполняющейся процедурой обработки прерываний последовательности saves (которая никогда не прерывается) и команды R1 формируют начальный сегмент соответствующей скобочной структуры.

В не прерывающемся выполнении, мы обозначим через Rn1 энное нахождение R1. Мы докажем индукцией по n, что до Rn1

• кодовый сегмент restore всегда стартует с SR = 0 (следовательно, он не прерывается),

• кодовые сегменты save и restore формируют начальную последовательность соответствующей скобочной структуры,

• парные скобки принадлежат  выполнению некоторого ISR(j).

Для n = 1 save должно быть левее первого R1 . Рассмотрим сначала такое save слева от R11 . Тогда, эти save и R11 принадлежат к непрерывному примеру ISR(j). Таким образом, R11 стартует с SR = 0 и первый RESTORE является непрерывным.

Для шага индукции рассмотрим R1n+1. Есть n команд Ri1 слева. По индукционной гипотезе кодовые сегменты save и restore до Rn1 формируют начальную последовательность соответствующей скобочной структуры с парными скобками, принадлежащими выполнению этого ISR(j). По лемме 5.3, эти выполнения точны. Так как последовательность SAVES и R1s формируют начальный сегмент скобочной структуры, мы можем объединить R1n+1 с предшествующей save кодовой последовательностью L . Пусть H' – последовательность команд между L и R1n+1. Создадим H из H' отменив все выполнения соответствующего ISR(j). Поскольку эти выполнения точны, мы имеем в течении H постоянный уровень прерываний

il = i,

таким образом, обработчик H(i) выполняется в течение H.

Пусть ISR(jn) означает образец ISR, который принадлежит R1n. Тогда команда R1n+1 непосредственно предшествует

(a) специальному перемещению I с SR := 0, или

(b) специальному перемещению I сопровождаемому ISR(jn).

Первый случай легкий (смотри n = 1). Во втором случае, ISR(jn) прерывает специальное перемещение, и прерывание jn имеет тип continue. Из-за точности ISR(jn), R1n+1 начинается с маской SRum = 0, и (n+ l)  блок restore не прерывается.

 

Лемма 5.5

Приоритетный критерий. Для допустимых процедур обработки прерываний это означает:

1. В течении выполнения ISR(j), маскируемые прерывания i при i >= j маскируются все время.

2. ISR(j) может прерываться только прерываниями  i < j высшего приоритета.

ДОКАЗАТЕЛЬСТВО

Согласно лемме 5.4, коды save и RESTORE могут прерываться только сбросом. Таким образом, мы сосредотачиваемся на обработчиках прерываний. Для любого немаскируемого прерывания j < 6 второе требование следует непосредственно из ограничения 2. Для маскируемых прерываний j >= 6 мы докажем требования индукцией по числу n прерываний которые прерывают обработчик H(j).

• n = 0: ISR всегда начинается с SR = 0, из-за сигнала JISR. ISR модифицирует маски только специальным перемещением movi2s или командой rfe. Так как rfe используется только как последняя команда ISR (ограничение 2), у нее нет влияния на маски используемые самой ISR. В случае специального перемещения SR:= R, бит R[i] должен быть нулем для любых i >= j. Таким образом, маскируемые прерывания маскируются правильно. Из-за определения причины маскируемых прерываний команды Il

 

5.4

 

и определения уровня прерываний

ill = min{j' | MCA[j']l = 1},

ISR(j) не может быть прервано маскируемыми прерываниями j' >= j, и требование выполняется.

• n > 0: Обработчик H(j) прерывается n раз, и коды save и restore формируют соответствующую скобочную структуру. Таким образом, последовательность команд ISR(j) имеет следующую форму

 

Save... ISR( j1 ) ... ISR( jm ) ... Restore,

 

для любых m <= n. Команды, которые принадлежат коду обработчика H(j) не размаскируют прерывания j’ при j' <= j. Из-за точности ISR, любые ISR( jr ) возвращают маски SR поставленные этому регистру ESR. Индукцией по m тогда следует, что прерывание jr имеет более высокий приоритет, чем j,т.е., jr < j.

Так как любое ISR( jr ) прерывается самое большее n - 1 раз, применима индукционная гипотеза. ISR( jr ) сохраняет все прерывания j' с j' >= jr маскируемыми, в особенности, с j' >= j.

Теорема 5.2 и лемма 5.5 подразумевают:

Теорема 5.6

Не прерывающееся выполнения допустимой процедуры обработки прерываний – совершенно вложенные.

ДОКАЗАТЕЛЬСТВО

Пусть LHR – не прерывающееся выполнение ISR(j), где L – сохраняющая последовательность и R – восстанавливающая последовательность. По теореме 5.2, последовательности saves и restores в LHR – начальные сегменты скобочной структуры. Если скобки L и R - парные, тогда последовательности save и restore в H формируют скобочную структуру. Следовательно, скобки в LHR формируют скобочную структуру и LHR – совершенно вложен.

 Предположим, что R парен с левой скобкой L' правее L:

5.4

Тогда по лемме 5.5, уровень прерывания непосредственно перед L' – больше чем  j, и LHR – не непрерывающаяся последовательность.

Согласно лемме 5.5, ISR прерывания j > 0 может быть прервано только прерыванием более высокого приоритета. Таким образом, может быть самое большее один кадр на стеке IS для каждого уровня прерываний j > 0. Сброс может прервать даже ISR(0). Однако, при сбросе ISR не размещает новый кадр, стек IS вместо этого является очищенным. Следовательно, размер стека прерываний IS ограничен; ISR использует самое большее 32 кадра.

Лемма 5.7

Подобно многим программным протоколам, для механизма прерываний желательна справедливость. В этом контексте справедливость означает, что обрабатывается каждое прерывание. Из-за чисто приоритетной схемы это не может всегда достигаться. Рассмотрим случай, когда сигналы событий двух внешних прерываний ev[15] и ev[17] становятся активными в тоже время, когда внешнее прерывание ev[16] происходит всякий раз, когда покидаем ISR(15) и наоборот. При этих условиях, прерывание 17 обламывается прерываниями 15 и 16. Таким образом, справедливость и чисто приоритетная схема не идут вместе. Тем не менее, по крайней мере хотелось бы гарантировать, что ни одно внутреннее прерывание не потеряется.

Законченость Пусть механизм прерываний подчиняется программным требованиям. Каждое внутреннее прерывание j которое происходит в команде Ii и которое не маскируется, получает обслуживание в команде Ii+1 , или команда Ii повторяется после ISR , который начинается с команды Ii+1 .

 

ДОКАЗАТЕЛЬСТВО

 

Пусть команда Ii вызывает внутреннее прерывание j, т.е., ev[j]i = 1. тогда бит причины CA[j]i также активируется. Согласно предположению леммы, j - немаскируемое или размаскированое (SR[j]i-1 = 1). В любом случае, соответствующий бит MCA установлен и инициирован переход на ISR. Таким образом, Ii+1 – первая команда процедуры ISR(k), где k = ili означает уровень прерывания после Ii . Из-за определения уровня прерываний, k <= j. Для k = j, требование следует немедленно. Для k < j, прерывание k – внешнее или внутреннее. В случае внешнего прерывания, k должен быть сбросом (ограничение 3) который прерывает выполнение обслуживания любых рассматриваемых прерываний. Если k – внутреннее прерывание, оно имеет тип abort или repeat из-за требования 3. Таким образом, ISR(k) обслуживающее любое рассмотренное прерывание прерывает выполнение, или после ISR(k), выполнение продолжается с команды Ii .

 

Если ограничение 3 слабое, полнота механизма прерываний в значении леммы 5.7 не может быть гарантирована. Примем, что команда Ii является причиной двух внутренних прерываний j и j', и что j < j'. Если j имеет тип continue, ISR(j) обслужит только j и продолжит выполнение с команды, которая следует за Ii в случае JISRi = 0. Таким образом, прерывание j' потеряется. Если прерывание j имеет тип repeat, ISR(j) также не обслуживает прерывание j'. Однако, команда Ii повторится после ISR, и ошибка, которая соответствует прерыванию j' – может произойти снова.


2 Мы покажем позже, что это всегда так

Наверх страницы

Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

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

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика