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

 

§ 4.3  Логическа структура на запомнящи устройства с последователен достъп – FIFO, LIFO

 

 

      Запомнящите устройства (ЗУ) с последователен метод на достъп се наричат (събирателно) още стекови или магазинни. Смисълът на този метод за достъп се състои в това, че инициаторът на дадено обръщение към ЗУ не подава адрес на желаната от него клетка. Адресът не е необходим, тъй като изборът на клетка е предопределен апаратно. В коя клетка ще бъде изпълнена заповяданата операция ЗУ определя само, чрез специален механизъм за достъп. Инициаторът на основната операция (четене или запис) подава само кода на желаната операция и има отношение единствено към входно/изходния поток от данни. В този смисъл тези запомнящи устройства се наричат още безадресни.

      Представата ни за вътрешния строеж на запомнящите устройства с последователен достъп е като тази, представена на фигура 4.1.1, т.е. може смело да се твърди, че те съдържат запомнящ масив от клетки, в които е поместена информацията. Съществуват два метода за организиране на последователния достъп до клетките от запомнящия масив:

·         Организация FIFO  (First Input / First Output) – пръв влязъл / пръв излязъл и

·         Организация LIFO  (Last Input / First Output) – последен влязъл / пръв излязъл.

      Уместен е въпросът – имат ли място запомнящите устройства с подобна организация на достъп до данните (до клетките)? Въпросът е резонен – ако произволният метод за достъп, който вече разгледахме, е напълно разбираем дори от самото си наименование и не предизвиква подобен въпрос, то тук наименованието на метода за достъп не е така прозорливо. Отговорът на поставения въпрос е положителен. Да, ЗУ с последователен метод за достъп има, защото в компютърните системи има необходимост от съхраняване на данни, които възникват и се консумират последователно в смисъла на споменатите по-горе организации. Бихме могли да твърдим, че организацията на изчислителния процес използва тези схеми на поведение на данните и за тях са необходими съответни технически решения. За да бъдем още по-ясни ще дадем следните примери.

      Ако данните от един източник възникват по-бързо отколкото друг може да ги приеме, то те следва да се наредят на опашка, очаквайки своята съдба, последователно в реда в който са пристигнали. За да не се загубят при това, те следва да се запомнят. Тази схема се нарича простичко опашка. А справедливото обслужване на опашката изисква първият на реда да бъде обслужен първи, последният – последен. Разбираемо е, че тук става въпрос за организацията FIFO. Мястото на тази памет е пояснено на фигура 4.3.1

Фиг. 4.3.1.  Използване на буферната памет като свързващо звено

      За буферната FIFO памет е характерно, че записът се извършва с бързодействието на подсистема №1, а четенето – с бързодействието на подсистема №2. Поради разликата в производителността буферната памет изпълнява ролята на еластична връзка между двете подсистеми (№1 и №2).

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

А)  Запомнящо устройство с организация FIFO

      Според описаната логика, можем да си мислим, че ЗУ с организация FIFO има един вход и един изход и че при запис данните се записват винаги в една и съща клетка, а при четене винаги се четат от друга клетка. Най-простият модел за техническа реализация на запомнящо устройство с такава организация може да бъде изместващият регистър. В такъв регистър информацията постъпва в единия край, представляващ вход, а се чете от другия, който е изход. При всеки запис, вътрешната информация, съдържаща се в регистъра, се измества с една позиция по посока на изхода. Запомнящият масив би могъл да бъде реализиран от множество изместващи регистри, работещи паралелно. По този начин, за четене е достъпна само информацията, намираща се в изходната клетка, а запис може да се осъществи само във входната клетка. Директният достъп до клетките в средата на масива е невъзможен. Данни, намиращи се в средата на масива, ще станат достъпни за четене само след определен брой последователни обръщения. Този начин на работа всъщност е основанието такъв достъп да се нарича последователен.

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

·         Какво има в клетките на ЗУ в началният момент ?

·         Кога може да започне четене на данни ?

·         Винаги ли е възможна операция запис, аналогично – операция четене ?

·         Какво става с изхвърлената на изхода информация при запис ?

·         Може ли да се изпълняват последователно няколко операции от един и същи вид ?

и много други.

      Ако читателят се постарае да даде отговор на тези въпроси, разглеждайки модела на изместващия регистър, той ще се убеди в тяхната актуалност и вероятно ще разбере, че техническата реализация на организацията FIFO е значително по-сложна. Към това ще добавим и съображението, че реализацията на изместването на данните в запомнящия масив на устройството изисква значителни апаратни разходи и вероятно съществени изменения в структурата на познатите ни вече RAM памети. Ето защо не е трудно да се разбере, че моделът на изместващия регистър не е практическото решение и може да послужи само за горните обяснения.

      Трябва да обобщим, че са известни следните три типа FIFO памети:

·         От тип изместващ регистър. Моделът представлява множество изместващи регистри с общо управление. Тази своеобразна памет е с неизменен обем на записаните данни (колкото е дължината на изместващите регистри). Тя се нуждае от едновременна синхронизация на операциите четене и запис, като при запис изходната дума задължително трябва да се прочете (пренесе), за да не се загуби. Това се дължи на необходимостта от изместване на данните при всяка от основните операции. Ако при четене не се записва нова дума, се явяват клетки без данни. Когато клетка без данни достигне изходната шина четенето трябва да е пусто. Следващата фигура представя структурния модел на регистровата памет.

 

Фиг. 4.3.2.  Буферната памет от тип “изместващ регистър”

Трябва да обърнем внимание на факта, че изместващите регистри се изграждат от тригери със сложна логическа структура (Edge или Master-Slave). За възможните логически схеми на споменатите тригери, както и за тяхното функциониране, четете подробно в раздел 3.1 на книга [3]. Казаното означава, че логическата схема на този вид памет е достатъчно сложна, а оттам и достатъчно скъпа.

 

·         Вторият тип FIFO памет се нарича  с транзитен пренос на данни (или още с непресичащи се операции запис и четене). Наименованието “с транзитен пренос” идва от транзитното преминаване на порцията данни при запис през свободните клетки на паметта, до достигане на свободната клетка, разположена непосредствено до вече заетите клетки, нареждайки се след тях като последна записана.

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

- запълнената с книги, която започва от дъното и достига последната поставена в кашона книга;

- и все още празната област, намираща се над запълнената.

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

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

 

·         Третият тип FIFO памет се нарича  с конкурентни операции. В логическата структура на тази FIFO памет е възможна асинхронност между операциите запис и четене, тъй като няма зависимост между двете операции. От това следва, че към памет от този тип могат да се подключат системи с различни скорости на работа и не е необходима синхронизация на тези системи. FIFO паметите с конкурентни операции се делят на два вида: синхронни и асинхронни. В логическата структура на този тип памет не се извършва изместване на данните при изпълнение на основните операции.

 

      След така изложената класификация ще илюстрираме техническите възможности за реализация на отделните модели FIFO памети. Ще се спрем първоначално на логическата структура на FIFO паметта от тип “с транзитен пренос”, която е представена на следващата фигура.

 

Фиг. 4.3.3.  Логическа структура на FIFO памет с транзитен пренос на данни

 

      Запомнящият масив е образуван от k на брой М-битови изместващи регистри с общо управление. Управлението се постига чрез М-битовия регистър за управление на движението на данните от входния към изходния регистър. Записът на данни се синхронизира с управляващия сигнал SI (shift in), а четенето – с управляващия сигнал SO (shift out). Записът на данни е възможен само ако е вдигнат флагът за готовност IR (input ready), а четенето – при готовност за извеждане OR (output ready). Управляващият сигнал R (reset) нулира всички тригери в регистъра за управление на движението.

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

      Поредното използване на буфера започва с подаване на сигнал R за нулиране на управляващите тригери. Така всички клетки се считат за свободни и се появява флагът IR. Чрез сигнал SI входната дума се зарежда в клетка №1, а управляващия й тригер се установява в 1. Флагът IR пада в 0. Връзката между клетките е реализирана така, че постъпилата в Кл1 дума “спонтанно” се копира във всички останали клетки и се появява на изхода. Така всички клетки в запомнящия масив съдържат едни и същи данни, управляващият тригер на най-дясната клетка с №М е установен в 1, а останалите управляващи тригери са нулирани при предаването на данните в съседните отдясно клетки. Състоянието на управляващия тригер №М е изведено на линията OR (признак “готови данни”). Операциите от тип запис могат да продължат до запълването на запомнящия масив, при което всички управляващи тригери се намират в състояние 1 и флагът IR=0.

      Операция четене започва с подаване на управляващия сигнал SO. При този сигнал управляващият тригер на най-дясната клетка КлМ се установява в 1, на изходната линия OR се появява 1 (признак “готови данни”), при което подсистема 2 трябва да приеме данните. След това управляващият тригер №М се нулира. Този процес се повтаря автоматично, при което данните се изместват от клетка в клетка в посока на изхода, а нулата в управляващия регистър – в обратна посока към входа.

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

      Разгледаната принципна организация на FIFO паметта допуска едновременно и независимо изпълнение на операциите четене и запис. Скоростта на запис се определя от временния интервал, който е необходим за предаване на съдържанието на клетка Кл1, а извеждането на данни се изпълнява със същата скорост. Единственото ограничение е времето за разпространение на данните през запомнящия масив, което е равно на времето за което входната дума достига изхода на незапълнения буфер. Това време може да се оцени с произведението (М.t), където с t е означено времето за превключване на запомнящия тригер в клетката. В това произведение се състои и основният недостатък на архитектурата с транзитен пренос – времето за закъснение на готовността нараства бързо с нарастване на обема на запомнящия масив.

      Като пример на изложената по-горе архитектура предлагаме на читателя да се запознае със следната реална схема:

SN74S225.pdf

http://www.ti.com/lit/ds/symlink/sn74s225.pdf

 

Фиг. 4.3.4.  Принципна логическа схема на FIFO памет с транзитен пренос на данни SN74S225 с обем 4х5

 

      Както се вижда от схемата (изобразена с някои ограничения), клетките на паметта са реализирани със синхронни RS-Latch тригери. Пренасянето на данните от клетка в клетка се управлява от сигналите С1,С2, .... Тези сигнали са формират последователно и лавинообразно в долната верига от последователни асинхронни RS-тригери. Левите тригери в тази верига съответстват на последователно свободните клетки, а десните – на последователно заетите с данни. Вътрешните състояния на отделните тригери се определят от последователно генерираните импулси, в отговор на съответно подадената заповед за запис или за четене. Процесите на двете операции са показани с времедиаграми на следващите две фигури. Управляващите импулси Ci се формират в отговор на външния импулс COMMAND WRITE, и съответстват на закъсненията във вътрешната последователна верига. Когато във FIFO се запише нова дума, тя “пропада" през цялата последователност от клетки и се съхранява в най-дясната свободна.

 

Фиг. 4.3.5.  Последователни операции запис във FIFO памет с транзитен пренос на данни

 

      Както се вижда от времедиаграмата, след всеки запис сигналите С4,С3, и т.н., затварят входовете на съответните клетки, като по този начин паметта се запълва. Минималната продължителност на командите за запис WRITE се определя от времето за превключване на динамичния тригер ТЕ, а максималната честота на запис се определя от продължителността на преходния процес за запис на всички клетки при празна памет, което както беше отбелязано по-рано е (М.t).

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

      На следващата фигура е представена времедиаграмата при изпълнение на команда READ четене.

 

Фиг. 4.3.6.  Последователни операции четене от FIFO памет с транзитен пренос на данни

 

      Сега ще се спрем на архитектурата, която беше наречена с "конкурентни операции". Отстраняването на споменатия в предидущата архитектура недостатък, както и желанието за увеличаване на обема на буферната памет, води към използването на RAM памет. Използването на адресируема RAM памет в качеството й на запомнящ масив във FIFO паметта е неизбежно – това е техническият елемент, без който желаното устройство не може да се създаде. Ако приемем казаното за неизбежно, то проблемът със специфичния метод за достъп се фокусира върху адресирането на клетките в RAM паметта. След като данните в клетките на RAM паметта не могат да се преместват, а достъпът се осъществява чрез подаване на адрес, то излиза, че изместването трябва да бъде отнесено към самия адрес. С други думи постоянни за достъп входна и изходна клетка, както и изместващи се данни в структурата няма. Вместо това в структурата с неподвижни данни е организирано изместващи се указатели за входната и изходната клетка на FIFO паметта. Или още – вместо изместване на данните при всяка основна операция, ще имаме модификация на адресите на клетките за вход и изход. Тъй като изместването на данните във FIFO паметта е в една и съща посока и за двете операции, то в новата интерпретация модификацията на адресите ще бъде също една и съща - инкрементна или декрементна.

      И така, след казаното стигаме до логическата структура за реализация на FIFO запомнящо устройство, представена на фигура 4.3.7.

 

Фиг. 4.3.7.  Логическа структура на FIFO ЗУ на базата на адресируема памет

 

      Адресирането на клетка от паметта с произволен достъп става чрез два адресни брояча – брояч за запис АБ ЗП и брояч за четене АБ ЧТ. Мултиплексирането на съответния адрес към адресната шина на RAM паметта се осъществява от MUX под управлението на кода на операцията R / not(W). Адресните броячи са кръгови и събиращи (инкрементни). Последното означава, че при съдържание на брояча равно на 111…11, след прибавяне на 1, ще се получи съдържание 000…00. При изпълнение на коя и да е от основните операции, в следствие на модифицирането с +1, това съдържание ще започне да расте и когато отново достигне максималната стойност съответният брояч отново ще се превърти в стойност нула (000…00).

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

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

      Всеки опит за изпълнение на основна операция, когато нейното изпълнение при горните условия не е възможно, трябва да се отбелязва със сигнал за грешка. Сигналът за грешка трябва да блокира изпълнението на операцията, при която е възникнал, най-малко до момента на изпълнение на противоположната операция. Например, ако при опит за запис е възникнал сигнал за грешка, това означава, че паметта е пълна и поредният запис е невъзможен. За да стане той възможен трябва да се освободи поне една клетка, а това е възможно след поне едно четене. Аналогично операция четене ще се окаже невъзможна, ако паметта е празна. Ще може да се чете, ако преди това се изпълни поне един запис.

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

 

Фиг. 4.3.8.  Кръгова представа за FIFO паметта в нормално (работно) състояние

 

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

      Описаното състояние на FIFO паметта може да се определи като нормално. В нормално състояние са възможни за изпълнение и двете основни операции. Не е трудно това състояние да се определи формално чрез адресите за четене и запис:

(АБ ЗП)   >   (АБ ЧТ)                                                              (4.3.1)

      В началният момент FIFO паметта е празна, а адресните броячи са нулирани. В този момент съдържанието на двата брояча е едно и също (АБ ЗП)=(АБ ЧТ). Операция четене е безсмислена. Може да се изпълнява операция запис. Ако предположим, че са изпълнени М на брой записа, то паметта ще се окаже пълна, а броячът за запис, преминавайки през всичките си състояния – 0, 1, 2, 3, 4, … (М-2), (М-1), в крайна сметка ще се окаже отново в състояние 0. Съдържанието на двата адресни брояча отново ще бъде едно и също, но за разлика от началния момент сега ще бъде възможна само операция четене.

      От казаното току що става ясно, че равенството на съдържанията в двата k-битови брояча, не е възможно да се вземе решение, която операция да бъде блокирана. Следва да разбираме още, че равенството може да настъпи при всяко едно от състоянията на броячите. Например, ако начално състояние се изпълнят 5 на брой записвания, то (АБ ЗП)=5, докато (АБ ЧТ)=0. Ако след това се изпълнят 5 на брой четения, то съдържанието на адресния брояч за четене ще стане равно на 5, т.е. (АБ ЗП)=(АБ ЧТ)=5. В този момент паметта е празна и следва да се блокира операция четене. Ако сега отново се изпълнят записвания и ако те бъдат М на брой, то адресния брояч за запис ще се превърти и ще достигне стойност 5. Така съдържанията на броячите ще се окажат отново равни, но сега паметта ще бъде пълна и следва да бъде блокирана операция запис.

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

      Допълнителният признак трябва да отчита превъртането на броячите, ето защо към адресните броячи се добавя по още един старши разряд № k. Този допълнителен бит bk не е част от адреса и не е включен в адресната шина на паметта. В този разряд може да бъде записана единица само ако възникне пренос p(k-1).

 

Фиг. 4.3.9.  Схема на допълнителния признак

 

      Допълнителният признак се реализира чрез логическата схема равнозначност, на която подаваме двата най-старши бита от броячите. Тази схема ще генерира стойност “1”, ако те имат еднакви стойности и “0” – в противен случай. Окончателното правило, по което следва да се управлява FIFO паметта, е следното:

а)  ако когато k-битовите младши съдържания на двата брояча съвпаднат (С=1), двата старши бита са еднакви, следва да се блокира операция четене. Преди да се изпълни ново четене трябва да се изпълни поне един запис;

б)  ако когато k-битовите младши съдържания на двата брояча съвпаднат (С=1), двата старши бита са различни, следва да се блокира операция запис. Преди да се изпълни нов запис трябва да се изпълни поне едно четене.

      Алгоритъмът за управление на логическата структура на FIFO паметта е вграден в управляващото устройство УУ. Показаният на фигура 4.3.7 набор сигнали е само примерен. С един реален пример, използващ описаната архитектура, читателят може да с запознае на следния адрес:

SN74ABT3612-etcTI.pdf

http://www.datasheet-pdf.com/PDF/SN74ABT3612-Datasheet-etcTI-1399760

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

      Съществуват практически случаи, когато за реализация на запомнящо устройство с последователен достъп тип FIFO не е изгодно или не е възможно използването на завършено адресируемо ЗУ. Последното се характеризира с това, че притежава входна адресна шина с вътрешен дешифратор. Случаите, които имаме предвид сега, се характеризират с това, че се разполага само с регистров файл, който може да играе ролята на запомнящия масив във FIFO паметта. За достъп до регистрите се предполага наличие на входове за разрешаващи управляващи сигнали за запис и четене. На тази база може да бъде организирано FIFO ЗУ с помощта на два циклически изместващи регистъра (регистри с “бягаща" единица), генериращи разрешаващи сигнали в необходимата последователност. Общият вид на такава структура е показан на следващата фигура 4.3.10.

 

Фиг. 4.3.10.  FIFO ЗУ с изместващи регистри

 

      В началния момент изместващите регистри РгЧТ и РгЗП се нулират, а указателните единици се поставят в най-горните им разряди. За нормална работа на показаната схема указателят за запис трябва да изпреварва указателя за четене (имаме предвид посоката, в която нарастват номерата на регистрите в ЗМ). Тъй като и в тази структура са възможни крайните състояния – пълен и празен запомнящ масив, то и за нея са необходими аналогични флагове и управляващи сигнали, както за предидущата структура. Разработването на подробния алгоритъм за управление на тази структура обаче оставяме като задача на читателя.

Б)  Запомнящо устройство с организация LIFO

      Според логиката за достъп (с организация LIFO) тези запомнящи устройства са също с последователен достъп. Тази логика може да се оприличи на предидущата, ако си представим запомнящия масив с общ вход и изход. Данните, които се записват последователно в LIFO паметта, се четат в обратен ред, което означава, че последното записано число ще бъде прочетено първо. Явно в разглеждания тип запомнящо устройство е достъпна само една точка - неговият вход (изход) или още връх. Такова ЗУ няма адресна шина – то е безадресно. Към устройството са подведени само даннова и управляваща шини.

      Като модел на организацията LIFO може да се приеме реверсивният изместващ регистър. Той има един вход, който в същото време е и изход. При всяко записване в регистъра, както и при всяко извличане от него, се извършва изместване на цялото му съдържание в права и обратна посока. Ако в предидущата организация (имаме предвид FIFO) данните в модела се изместваха само в едната посока, тук в модела LIFO те се изместват в двете посоки, в зависимост от операцията. Реализацията на запомнящия масив на LIFO паметта изисква наличието на поразрядни изместващи вериги, при това в двете посоки. Това силно затруднява построяването на логическата схема на запомнящия масив, ето защо моделът на реверсивния изместващ регистър е само теоретичен.

      Логическата структура на запомнящо устройство с LIFO организация на достъпа практически се реализира чрез адресируемо запомнящо устройство. Аналогично на предидущата организация и в настоящата, движението на данните спрямо входно-изходната клетка, се постига относително чрез адресен указател, т.е. не се местят данните, а техният указател.

 

Фиг. 4.3.11.  Логическа структура на LIFO ЗУ на базата на адресируема памет

 

      Както се вижда от горната фигура, адресният указател е реализиран чрез реверсивен брояч, началното състояние на който ((Адр.Бр.)=0) се постига чрез сигнала Reset. Дешифраторът Дш формира флаговете за състоянието на запомнящия масив Празен и Пълен, съответно при съдържание на брояча “000…00” и “111…11”. Ако е необходимо да се формира при обръщение към паметта сигнал Грешка, това може да се постигне чрез следната логическа функция:

(Write)Ç(Full Flag)   È   (Read)Ç(Empty Flag)  =  Error                            (4.3.2)

      Според структурната схема от фигура 4.3.7, в неактивно състояние, в запомнящия масив има клетки, в които е записана съществена информация, които формират така наречената заета област. На рисунката това са клетките с адреси 0, 1 и 2. Останалите клетки формират свободната област в запомнящия масив. В това състояние адресният указател сочи първата свободна клетка, най-близко стояща до заетата област, .те. клетката с адрес 3. По този начин казваме, че запомнящото устройство е винаги готово за запис. При изпълнение на запис подаваните по входната шина данни се записват в така подготвената клетка, след което закъснителният елемент на сигнала Write в схемата формира инкрементиращ импулс (+1) към адресния брояч (Адр.Бр.):= (Адр.Бр.)+1. Така към началото на следващ запис структурата е подготвена автоматично: (Адр.Бр.)=4.

      За разлика от операция запис, при операция четене най-напред е необходимо да се декрементира адресният брояч (Адр.Бр.):= (Адр.Бр.)-1. Указателят слиза от адрес 3 на адрес 2. Така се отваря клетката, в която последно е било записвано. Едва след това закъснителният елемент на сигнала Read подава разрешаващ сигнал на изходната даннова шина.

      Запомнящото устройство с организация LIFO често се нарича стек. От своя страна адресният брояч се нарича стеков указател. Ако стековият указател винаги сочи последната запълнена с данни клетка, то той се нарича винаги готов за четене. За да работи устройството от фигура 4.3.11 по този начин, закъснителните елементи в логическата структура следва да се преместят съответно в другите отклонения на сигналите Write и Read. Какъв да бъде стекът – винаги готов за запис или винаги готов за четене, зависи от приложението на устройството и от това, коя от основните операции изисква по-бързо трансфериране на данните. За тези нюанси на стека ще се говори и на други места в тази книга както и в книга [4].

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

      Стекът, който до момента обсъждаме, се нарича още апаратен.

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

      Тъй като събитието прекъсване е изключително важно и характерно за всеки процесор, то запомнящото устройство с последователен достъп от вида LIFO е задължителен архитектурен елемент във всеки процесор. Най-често това запомнящо устройство се реализира по структурата, показана на фигура 4.3.7, но в качеството на запомнящ масив конструкторите имат предвид определена област от оперативната памет на процесора. Изградена по този начин, структурата на стека улеснява неговото управление от страна на процесора. Удобството се изразява в това, че се работи с безадресни машинни команди от една страна и че запомнящият масив на стека може да се мести в адресното пространство на оперативната памет, от друга страна. Тъй като тази реализация обслужва преди всичко изпълняващите се в процесора програми, то тя се нарича програмен стек.

      Тъй като обикновено обемът на оперативната памет е много по-голям от обема на запомнящия масив на стека, поставянето на последния в изходно състояние (примерно при включване на захранването на компютъра) е свързано с автоматично установяване на съдържанието на стековия указател SP. За разлика от апаратния стек, където началното съдържание на указателя беше нула, и което се постигаше чрез сигнала Reset, при програмния стек това е задача на операционната система. По отношение на оперативната памет може да определим програмния стек като наемател а операционната система като хазаин. Операционната система определя коя част от оперативната памет ще предостави на програмния стек. В този смисъл тя определя началния адрес на запомнящия масив на стека и при началната подготовка на процесора го зарежда в стековия указател като негово начално съдържание. Така в началния момент стековият указател сочи клетка, която се нарича дъно на стековата област. Обикновено програмният стек не притежава апаратни средства за защита. Състоянията на стека могат да се контролират по програмен път.

 

 

 

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

4.4.  Запомнящи устройства с асоциативен достъп - Associative Memory