Хардуерна реализация на стратегии за обслужване на опашки

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

5.4.3.1 Хардуерна реализация на стратегии за обслужване на опашки

Компютърните системи са дълбоко структурирани системи и протичащите в тях процеси се характеризират с изключителна сложност. При взаимодействието на отделните структурни елементи в системите се създават сложни ситуации, в случай че определени техни елементи се оказват недостатъчно производителни. За да се избегне срив на изчислителния процес, в такива места се организират така наречените опашки от чакащи за обслужване процеси. Предидущият пункт беше посветен на проблема избор на заявка. Някои от възможните решения бяха подсказани. Тук много по-конкретно са изложени две апаратни решения на проблема избор, отнасящи се до:

1. Опашки с фиксиран ред. В този случай, постъпилите в опашката елементи се подреждат според своята степен на значимост или още приоритет. Логиката за справедливото им обслужване изисква изборът да се извърши при спазване на този приоритет. При повторно постъпване в опашката на вече обслужен елемент обаче, същият се подрежда в реда на чакащите като последен, т.е. с най-нисък приоритет. Така той ще бъде обслужен повторно, след като бъдат обслужени всички елементи с по-нисък приоритет, чакащи преди него. Такива опашки са известни под наименованието FIFO-опашки. Наричат се още “опашки без пререждане”.

2. Опашки с нефиксиран ред или още “опашки с пререждане”. И тук разглеждането на постъпилите в опашката елементи се подчинява на присвоения към всяко място в опашката приоритет. Логиката за справедливото им обслужване обаче не допуска промяна на приоритета на елементите в опашката. Така винаги на поредно обслужване има право онзи елемент, който е успял да заеме най-значимото място в опашката в текущия момент, независимо от реда на регистрация на всички останали чакащи обслужване. При такъв ред, повторно регистрирал се високо приоритетен елемент, ще пререди в обслужването по-ниско приоритетните, които са се регистрирали преди него във времето. Последното определя опашката като "опашка с пререждане”.

Тук се разглежда поддържане на реда в опашките с апаратни средства. Това позволява да не се “натоварва” приложният софтуер със задачи, които нямат отношение към алгоритмите, които той реализира.

Еднотактна схема

Еднотактната схема е представена на фигура 5.4.3.1. Като пример, в тази схема са реализирани 8 входа за приемане на заявки

като при други нужди тя лесно може да бъде променена, т.е. удължена или скъсена. Схемата има един изход Request, оповестяващ за наличие на заявки; един вход на сигнал Choice, който стартира процеса за избор; един изход от регистъра RG_№REQ, съдържащ идентификационния код на избраната заявка; един вход за назначаване на режима на работа:

и няколко входа за управляващи сигнали.

Фиг. 5.4.3.1. Логическа структура за еднотактово обслужване на опашка

Опашката се представлява от регистъра на заявкита RG_Req. Останалите логически възли в схемата ще бъдат изяснени по хода на изложението.

1. Функционирането на схемата в режим “0” (с пререждане) се основава на така наречената Дейзи-верижка. Дейзи-верижката реализира еднотактно последователно претърсване на опашката, даващо име на схемата, в резултат на което се извършва избор на първия срещнат елемент. За да се постигне логиката на този режим следва да се приеме, че претърсването започва от най-приоритетното място – за схемата на верижката най-лявото. Затова сигналът Choice се разпространява отляво надясно. Изходната логическа комбинация за направения избор съдържа само една единица, стояща в мястото на избраната заявка, например 00100000. Тази комбинация се подава чрез шината Bus_CD на шифратора CD, който я преобразува в цяло 3-битово число n, съответстващо на номера на избраната заявка n. За да завърши преходният процес в тази част от схемата е необходим, условно казано, един такт. За надеждно записване на формирания код е необходим още един такт. От тук следва, че активната единица на сигнал Choice трябва да се поддържа в продължение на два такта. По време на втория такт, чрез импулса Strobe_2, в регистър RG_№REQ се записва кодът на избраната заявка. По същото време в регистър RG_CLR се установява тригерът TLn, който съответства на избора. Така се фиксира фактът, че именно този номер n е бил избран. Тази фиксация е необходима, защото в следващия момент, когато сигналът Choice изчезне, тригерът TLn в регистър RG_R, фиксирал избраната заявка, следва да бъде нулиран. С това той се подготвя възможно най-рано за следващо приемане на същата заявка. Нулирането на този тригер обаче трябва да стане в следващ такт, за да се предотвратят състезанията в образуваната обратна връзка. Алгоритъмът, по който функционира схемата в този режим, има следния вид:

Фиг. 5.4.3.1.2. Алгоритъм за обслужване на опашка с пререждане

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

2. Като алтернатива на режим “0”, при който споменатото пререждане може да забави неоправдано дълго обслужването на ниско приоритетните заявки, е разработен режим “1”. В този режим, при повторно постъпване на вече обслужената приоритетна заявка, същата временно губи тази си степен на значимост. При следващ избор логиката на обслужване изисква същата да се възприема като най-незначителна, т.е. като стояща последна в опашката. При нареждането й обаче в края на опашката, всички вече фиксирани преди нея заявки, следва да се възприемат с повишена степен на значимост. В този ред, заявката ще възстанови (ще постигне) своя пределно възможен приоритет, когато бъде повторно обслужена, при условие, че липсват други заявки. Обслужваната по този начин опашка се определя като опашка без пререждане.

Фиг. 5.4.3.1.3. Алгоритъм за обслужване на опашка без пререждане

С цел реализация на този режим, логиката на работа на Дейзи-верижката се променя с помощта на код, който се формира по време на текущия избор и се съхранява и използва при следващия избор, когато отново се формира и съхранява. За съхранение на този код, който е наречен “код за блокировка”, е предназначен регистърът за блокировка RG_B. Същността на кода за блокировка е следната: ако текущо е избрана заявка №n, към D входовете на тригерите в регистър RG_B се формира n-битова комбинация от вида (1...1110...000), в която всички разряди от 0-я до n-тия са единици, а останалите от (n+1)-я до k-я са нули. При следващ избор, иницииран от сигнала Choice, този код се подава в Дейзи верижката чрез мултиплексора MUX. При това лявостоящите единици на кода блокират възможните заявки с приоритет от 0 до n, пропускайки обаче сигнала Choice, който започва истинското претърсване от позиция №(n+1) надясно (вижте фигура 5.4.3.1.1). Ако в този участък не бъде намерена заявка, единичната стойност на сигнала Choice достига S-входа на тригер TL_B. Този тригер приема асинхронно тази единица, с което превключва мултиплексор MUX към шината на инверсните изходи на тригерите в регистъра на блокировката RG_B. От този момент нататък в Дейзи-веригата се подава логическата инверсия на блокиращия код, т.е. комбинацията (0...001...111). Подложен на този код, сигналът Choice осъществява претърсване на онези позиции в опашката, които първоначално са били прескочени. В края на този преходен процес чрез шината Bus_CD на изхода на шифратора CD е установен кодът на избраната заявка, а към D-входовете на тригерите в регистър RG_B е подведен новоформираният код за блокиране. От този момент нататък с помощта на импулсите Strobe_1, Strobe_2 и Strobe_3 се осъществяват вече описаните фиксации. Допълнителните микрооперации, които тези сигнали заповядват, са вписани в блоксхемата на алгоритъма, представена на фигура 5.4.3.1.3.

На фигура 5.4.3.1.4 е представено обслужване на заявка №5, след изходно състояние. След нулиране на тригерът, фиксирал тази заявка, същата се фиксира повторно.

Фиг. 5.4.3.1.4. Времедиаграма за двукратно обслужване на Req5 в режим “1”

Многотактна схема

Многотактната схема е представена на фигура 5.4.3.1.5. Като пример, в тази схема отново са реализирани 8 входа за приемане на заявки

като при други нужди тя лесно може да бъде променена. Схемата има един изход Request, оповестяващ за наличие на заявки; един вход на сигнала за избор Choice; един изход от регистъра RG_№REQ, който съдържа идентификационния код на избраната заявка; един вход Regime за назначаване на режима на работа, аналогично кодиран според (5.4.3.1.1), както и няколко входа за управляващи сигнали. Опашката се представлява от регистъра на заявките RG_Req. Останалите логически възли в схемата ще бъдат изяснени по хода на изложението.

Фиг. 5.4.3.1.5. Логическа структура за многотактово обслужване на опашка

Функционирането на схемата се основава на многоотактовото последователно “опипване” на опашката. За да се постигне логиката на този режим, опипването започва от най-приоритетния елемент, който за схемата е най-горния, т.е. №0. Опипват се последователно изходите на тригерите за регистиране на заявки в регистър RG_Req. Опипването се реализира чрез “бягащата” по изходите на дешифратора DC единица, следваща последователно комбинациите на състоянието на инкрементния брояч СТ2. Броячът е кръгов двоичен по модул S, където модулът е равен на броя на входовете Req. Процесът е многотактов, което дава име на схемата. В резултат на опипването се извършва избор на първия срещнат в опашката елемент. Представената структура работи в два режима, аналогично на тази от фигура 5.4.3.1.1.

1. Режим с пререждане, т.е. режим с нормален приоритет. Този режим се назначава от активната единица, стойност на сигнала not(Regime), в съответствие с кодировката (5.4.3.1.1). Структурата функционира по следния начин – в изходно състояние към нея постъпват и се фиксират заявки за обслужване Req. Съвкупността от фиксирани в регистър RG_Req заявки формират дезюнтивно изходния сигнал Request. В това състояние структурата очаква сигнала Choice. В изходно състояние тригерът за блокоране TL_B е нулиран. Така инверсният изход на този тригер поддържа входната схема И в готовност за отваряне. Съдържанието на брояча СТ2 е (СТ2)=S-1, което е осигурено от сигнал Reset или от сигнал Strobe_2. Регистър RG_CLR е нулиран, т.е. (RG_CLR)=0.

Когато в отговор на сигнала Request пристигне сигнал Choice=1, се разрешават схемите И на опипващите сигнали, както и входната схема И, през която преминават импулсите на сигнала CLK. В същото време се забранява фиксирането на нови заявки в регистър RG_Req. С това започва процесът на опипване. Входната схема И е отворена и броячът СТ2 се инкрементира от импулсите на тактовата последователност CLK, като преминава през комбинациите 0, 1, 2, 3 и т.н. Процесът на опипване спира от само себе си, когато първата срещната заявка (Tn=1), през общото ИЛИ, установи по вход S тригерът за блокировка TL_B, т.е. TL_B=1. Така инверсният изход на този тригер запушва входната схема И и въпреки че все още Choice=1, инкрементирането на брояча СТ2 се прекратява. Структурата “замръзва” в това състояние. Процесът на опипване и на избор е лавинообразен.

Възстановяването на структурата е процес, който преминава през няколко такта, аналогично на еднотактната структура. Този процес стартира в отговор на установяването на тригера TL_B=1. В структурата се изпълнява следната последователност от действия:

Фиг. 5.4.3.1.6. Алгоритъм за обслужване на многотактова опашка с пререждане

В резултат на трите последователни строба структурата се установява в изходно състояние. В регистъра на кода на избраната заявка RG_№REQ се съхранява кода на избраната заявка, който следва да се използва за нейното обслужване.

2. Алтернативният режим се назначава с активна нула not(Regime)=0, която предотвратява установяването на брояча СТ2 в изходно състояние чрез сигнала Strobe_2 (вижте фигура 5.4.3.1.5). По този начин, ако броячът СТ2 е достигнал до заявка №n, съдържанието му ще се запази след изпълнение на алгоритъма от фигура 5.4.3.1.6. Така при нов цикъл за избор на заявка, опипването на опашката ще започне от следващия номер №(n+1), с което се реализира логиката за обслужване без пререждане. Като цяло функционирането на структурата е същото.

На времедиаграмата от фигура 5.4.3.1.7 е показано обслужване на заявка №5, след изходно състояние. След нулиране на тригерът, фиксирал тази заявка, същата се фиксира повторно. Следващият цикъл за избор обаче започва от №6, превърта кръговия брояч СТ2 и едва след като достигне №5, тази заявка се избира повторно. Ако заедно с тази заявка се беше фиксирала по-приоритетна, например №3, то щеше да бъде избрана именно заявка №3, а №5 щеше да чака.

Фиг. 5.4.3.1.7. Времедиаграма за двукратно обслужване на Req5 в режим “1”

Описаното изследване изяснява изцяло възможностите за апаратно обслужване на опашки. Доказан е тритактовият цикъл за реализация на приоритетен избор на заявка. Синтезираните принципни схеми са оригинални, съвместяват възможността да обслужват и двата вида опашки и са основа за изграждане на опашки с различна дължина. Детайлната презентация на схемите и алгоритмите на функциониране дава възможност те да бъдат променяни и адаптирани съобразно необходимостите. Става дума за програмни маски, за ниво на приоритета и др.

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

5.4.4. Векторна система за прекъсване