1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n  J



страница8/29
Дата11.01.2018
Размер5.91 Mb.
#44141
1   ...   4   5   6   7   8   9   10   11   ...   29
    Навигация на страницата:
  • Памет

централен процесор;

  • основна памет;

  • входно-изходни устройства.

    Взаимовръзката между основните компоненти определя логическата организация на съответната компютърна система.

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



    1. Индивидуални информационни канали.

    2. Обща информационна шина.

    При първата организация основните компоненти се свързват по схемата на пълен граф, т.е. по схемата “всеки-всеки”.

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



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

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

    По-нататък ще разглеждаме само втората организация (обща информационна шина).

    Централният процесор е основен компонент в архитектурата на персоналния компютър. Всяка задача, която се изпълнява от компютъра, директно или индиректно се изпълнява и контролира от централния процесор. Централният процесор осъществява реализирането на машинните команди (инструкции). Някои негови съставни части са:


    • управляващо устройство;

    • аритметично-логическо устройство;

    - регистри;

    - блок за работа с числа с плаваща точка и др.



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

    • регистри с общо предназначение – в тях се записват междинни резултати или се използват за адресация;

    • регистри за работа с плаваща аритметика;

    • служебни регистри – използват се за специални системни функции, към тях се включват флагов регистър (съдържа информация за препълване, пренос, посока на обработка на низове, маскиране на прекъсвания и др.), PC (програмен брояч, сочи към следващата инструкция за изпълнение), SP (стеков указател, сочи към върха на програмния стек), MSW (съдържа управляващи флагове, служещи за синхронизация на работата на централния процесор с входно-изходните устройства и с операционната система).

    Централният процесор изпълнява една машинна команда чрез следната последователност от елементарни стъпки, която наричаме основен цикъл на изпълнение на командата:



    1. Адресиране и извличане на предстоящата за изпълнение команда (адресирането става по съдържанието на PC).

    2. Обновяване на PC (съдържанието на PC се увеличава с дължината на извлечената команда).

    3. Дешифриране на командата (определят се вида на операцията, броя на операндите, типа на данните и размера на данните).

    Тези три стъпки се изпълняват от управляващото устройство.

    1. Адресиране на операндите (на базата на информацията от полето на командата по определени методи на адресация се определя местоположението на клетките от паметта, които съдържат операндите).

    2. Извличане на операндите.

    3. Изпълняване на операцията върху операндите с помощта на аритметично-логическото устройство.

    4. Записване на резултата (определя се местоположението на резултата и той се занася в съответната клетка на паметта).

    5. Проверява се има ли постъпил сигнал от някоя от сигналните линии за прекъсване. Ако да, управлението се предава на хардуерния механизъм за обработка на прекъсването. След обработване на прекъсването (ако е имало такова) се преминава към стъпка 1. (започва изпълнение на следващата команда).

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

    Първият тип команди са аритметично-логическите команди, които се изпълняват върху операнди, които са цели числа със или без знак. Част от тях изчисляват булевите функции конюнкция, дизюнкция, отрицание, сума по модул 2 и т.н. Друга част са операциите за сравнение – равно, различно, по-голямо, по-малко, по-голямо или равно, по-малко или равно и т.н. Последната част са аритметичните операции събиране, изваждане, умножение, целочислено деление и модул.

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

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

    Четвъртият тип команди са транспортни и те служат за прехвърляне на данни. Основните са команда за прехвърляне на данни от едно място на паметта в друго, команда за прехвърляне на данни от паметта в регистрите и команда за прехвърляне на данни от регистрите в паметта.

    Има и други типове команди – например операции върху числа с плаваща точка (събиране, изваждане, умножение, деление, степенуване, коренуване и др.), операции върху низове (прехвърляне, сравнение, конкатенация), мултимедийни операции MMX (специални векторни операции, които имат голямо приложение при обработката на изображения).
    Устройствата в персоналния компютър като централен процесор, основна памет, твърд диск, видеоконтролер и т.н. обменят помежду си данни и контролна информация по така наречените шини. Шината представлява магистрала, по която може да бъде обменяна информация между две или повече устройства.

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

    Шината има следните характеристики:


    • ширина на подшината за данни – количествена мярка за броя битове, които могат да преминават едновременно по подшината за данни;

    • ширина на подшината за адреси – определя максималният размер на основната памет, например чрез 16-битова адресна подшина могат да се адресират 64KB памет, с

    32-битова шина могат да се адресират 4GB памет;

    - скорост – определя колко пъти шината може да бъде използвана (заемана) в рамките на една секунда,

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


    • четене – подаване на адрес и извеждане съдържанието на съответния байт;

    • писане – подаване на адрес и на байт, който се записва на този адрес.

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

    С помощта на n-битово поле могат да се представят точно 2n различни стойности.

    Първият начин за представяне на целите числа е чрез прав код.

    При него най-старшият бит в n-битовото поле е знаков –

    0 означава положително число, 1 означава отрицателно число. Останалите n-1 бита представят абсолютната стойност на числото в двоична бройна система. По този начин при прав код диапазонът от цели числа, който може да се представи с n-битово поле е -2n-1+1 …2n-1-1. При това нулата има две представяния – 000…0 и 100…0. Недостатъкът на правия код е, че събирането и изваждането на цели числа се реализират трудно апаратно.

    Вторият начин за представяне на целите числа е чрез обратен код. Отново най-старшият бит е знаков. Разликата от правия код е в представянето на отрицателните числа – то се образува чрез инвертиране на двоичното представяне на абсолютната стойност на числото. Диапазонът при n-битово поле отново е -2n-1+1 …2n-1-1.

    Нулата отново има две представяния – 00…0 и 11…1. При обратния код събирането и изваждането се реализират

    по-ефективно – числата, независимо от знака си, се събират като числа в двоична бройна система, при това, ако има пренос от

    най-старшия бит навън, то към резултата се добавя 1.

    Третият начин за представяне на целите числа е чрез допълнителен код. Отново най-старшият бит е знаков. Разликата от правия код е в представянето на отрицателните числа – то се образува чрез инвертиране на двоичното представяне на абсолютната стойност на числото (както при обратния код) и след това добавяне на 1. Диапазонът при n-битово поле е -2n-1 …2n-1-1. Нулата вече има единствено представяне – 00…0. При допълнителния код събирането и изваждането се реализират

    най-ефективно – числата, независимо от знака си, се събират като числа в двоична бройна система, при това преносът от

    най-старшия бит навън се игнорира.

    Има още един за представяне на числата – така наречените двоично-десетични числа. При тях всяка десетична цифра се представя с уникална двоична последователност. Предимството е, че се дава възможност за лесно извеждане на числа. Недостатъкът е, че се усложняват аритметичните операции. Една цифра обикновено се представя с четири бита, които в общия случай представят стойностите/цифрите/символите 0-9. Така 6 комбинации остават неизползвани. Тъй като компютрите съхраняват данни под формата на байтове има два начина за съхраняване на четири битовите цифри: всяка цифра се съхранява в отделен байт (непакетирана форма) или в един байт се съхраняват две цифри (пакетирана форма). Едно n-байтово пакетирано двоично-десетично число може да се състои от най-много 2.n-1 цифри, едната е резервирана за знак.

    Реалните числа в паметта се представят чрез рационални апроксимации.

    Първият подход е рационалните апроксимации да са с фиксирана точка. С други думи, в n-битово поле, първите m бита представят цялата част на числото, а останалите n-m бита представят дробната част на числото – десетичната точка е на фиксирана позиция. Проблемът на този подход е, че не винаги се използват всички битове.

    Вторият подход е рационалните апроксимации да са с плаваща точка. Всяко число с плаваща точка има вида m.2p, където m е цяло число, което се нарича мантиса, а p е цяло число, което се нарича порядък. Казваме, че едно число с плаваща точка е в нормализирана форма, ако най-старшият бит на мантисата е 1.

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

    За универсално представяне на символите в паметта се постъпва по следния начин : съставя се кодова таблица, в която всеки символ от дадена азбука се асоциира с битова поредица с определена дължина. Съществуват различни кодови таблици. Примери са EBCDIC – 8-битова кодова таблица на IBM, UNICODE – 16-битова универсална кодова таблица, ASCII – първоначално замислена като 7-битова таблица, но впоследствие разширена до 8-битова за нуждите на различни националности. В различните ASCII таблици символите, кодирани с 0 до 127 са едни и същи, а символите, кодирани със 128 до 255 могат да бъдат различни.


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

    Схемата е следната: (в централния процесор) регистри  кеш на първо ниво ($L1 кеш)  кеш на второ ниво (L2 кеш)  (извън централния процесор) кеш на трето ниво (L3 кеш)  основна памет  виртуална памет (swap-файлове върху диск).

    Естествено, в схемата се включва и входно-изходната система, която действа с данни извън адресното пространство и обменя информация с основната памет и със swap-файловете.
    До регистрите има паралелен достъп от процесора. L1 кешът е разделен на две независими части – в едната се пазят само инструкции, в другата само данни. Знакът $ пред L1 означава, че тази структура работи невидимо за програмата. L2 кешът се намира в процесора и е част от общото адресно пространство, с което работят инструкциите. L3 кешът е извън процесора и той е по-голям от L2 кешът по обем памет. Основната памет не съдържа всички адреси от общото адресно пространство, реално всички адреси могат да се поместят само върху диска.
    Йерархията на паметта се базира на общото положение, че за малък период от време са нужни малко адреси. Нейната задача е да се реализира бърза памет чрез двете концепции за локалност:


    • темпорална локалност – най-вероятно, последно използваните данни ще бъдат използвани пак скоро, така всяко ниво помни последно използваните блокове от по-долното ниво;

    • пространствена локалност – най-вероятно съседите в адресното пространство на последно използваните данни ще бъдат използвани скоро, така блоковете от по-ниските нива в йерархията са по-големи, тъй като освен че обхващат последно използваните блокове, те обхващат техните съседи.

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


    по-малък от размера на основната памет и те оперират приблизително със скоростта на процесора.

    Kешът представлява структура като множество от рамки. Всяка

    рамка се състои от данни, етикет и състояние. Етикетът е характеристика на рамката, която е съществена при търсене на данни в кеша. Състоянието е два бита – бит, който показва дали данните в рамката са валидни и бит, който показва дали в рамката са били писани данни.

    Основната логическа организация на кеша е рамките да се групират в множества. Кешът се реализира като матрица, всеки ред на която представлява едно множество от рамки.

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

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

    Съществените характеристики на кешовете са следните:


    • асоциативност;

    • размер на блока – ако размерът на блока е малък се губи принципа за пространствена локалност, ако е много голям може да имаме излишно прехвърляне на байтове;

    • капацитет – по-големите кешове работят по-бавно, докато при по-малките се губи темпоралната локалност;

    • механизъм за изхвърляне на блокове от данни – ако търсеният блок от данни не бъде намерен, коя рамка да бъде изхвърлена, за да се освободи място за търсената рамка, която ще се изтегли от по-долно ниво в йерархията, стратегиите са следните – LRU (изхвърляне на рамката, която не е използвана най-отдавна), LFU (изхвърляне на рамката, която е използвана най-рядко), random (изхвърляне на произволна рамка), NMRU (изхвърляне на произволна рамка, която е различна от най-често използваната);

    • начин на записване на блок от данни в кеша – когато се записват данни в кеша стои въпросът дали тези данни да се записват и в основната памет, двете стратегии са

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

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

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

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

    Виртуалната памет има следните предимства:


    • защита - процесите са изцяло отделени един от друг;

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

    Основен недостатък на виртуалната памет – какво става при ненамиране на физическата страница в паметта. Характерното за виртуалната памет е, че на магнитен диск се отделя файл

    (swap-file), в който се помества образ на пълното виртуално адресно пространство. В реалната памет се поместват само някои активни страници. При ненамиране липсващата страница трябва да се прехвърли от диска в реалната памет. Това прехвърляне е твърде бавно и поради тази причина, реалната памет винаги е write-back, т.е. никога от процесора не се записват данни в диска, така се поддържа връзка само между процесора и реалната памет.

    Транслацията се извършва по следния начин: при заявка за достъп до дадена страница, първо се проверява дали тя се намира във физическата памет – ако да, връща адреса на страницата,

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


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

    В машините PENTIUM при сегментацията адресът се получава от 16-битов сегментен регистър и 32-битово отместване.

    Всеки сегментен регистър съдържа индекс, който показва отместване в глобална или локална дескрипторна таблица.

    Дескрипторните таблици съдържат сегментни дескриптори, като всеки сегментен дескриптор описва един сегмент чрез адреса на началото на сегмента, размера на сегмента и различни битове за състояние. Глобалната дескрипторна таблица е единствена и се използва най-вече за дескриптори на системни сегменти. Локалнатa дескрипторна таблица не е единствена и се използва най-вече за дескриптори на приложни сегменти. В даден момент може да се използва точно една локална дескрипторна таблица.

    Получаването на адреса при сегментацията става по следния начин: (зададени са сегментен регистър и отместване)


    • първо се определя в глобалната или в локална дескрипторна таблица да се търси сегментния дескриптор;

    • след като е определен сегментният дескриптор се взима адресът на началото на сегмента и към него се прибавя отместването.

    Полученият адрес след сегментацията се нарича линеен адрес и той е част от линейното адресно пространство.

    Възможни са два случая:



    • линейното адресно пространство директно се изобразява върху физическото адресно пространство;

    • линейното адресно пространство е виртуално – извършва се странична преадресация.

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


    Сподели с приятели:
  • 1   ...   4   5   6   7   8   9   10   11   ...   29




    ©obuch.info 2024
    отнасят до администрацията

        Начална страница