Тема 11 – Стратегии за извеждане на страница

Тема 13 – Стратегии за извеждане на страници

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

1. 
   Оптимално извеждане [Биледии] – трябва да се извежда страницата, към която ще има най-късно обръщение. Обикновено за извеждане се избира немодифицирана страница, т.е. страница, в която не е бил извършван запис. Съществено е да няма големи системни разходи.
   

2^ра стратегия – Извеждане на случайна страница.

3^та стратегия – Извеждане на най-дълго неизползваната страница – LRU – Least Recently Used. Има много начини за реализиране на този метод:

1. 
   Чрез стек. При обръщение на страница тя се записва на върха. По този начин на дъното на стека се намира най-малко използваната
   
2. 
   Чрез брояч. При всяко обръщение към страница броячът увеличава стойността си. За извеждане се избира страницата с най-малка стойност в регистъра.
   

1. 
   Метод с допълнителни битове (регистър, байт) – за всяка страница се свързва един байт. През определени интервали се копира битът за използване на страницата в най-старшия бит на байта и се премества надясно. По този начин се получава историята на страницата. Страницата с най-малката стойност в байта е най-малко използваната и се извежда.
   
2. 
   При втори шанс се използва метода FIFO и допълнителния бит. Преглежда се бита за използване на страницата, която първа е въведена (тази за изхвърляне според FIFO). Ако той е 0, то страницата се извежда. Ако бита е 1, на страницата се дава втори шанс, т.е. Бита на страницата се нулира и тя се записва в началото на опашката, сякаш току-що е влязла.
   

Методът апроксимация на LRU се счита за ефективен и се използва в съвременните машини

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

6^та стратегия – LFU – Last Frequently Used. Най-често използваната страница. В случая се предполага че страницата е изконсумирана

7^ма стратегия – NRU – Not Recently Used. Страница, неизползвана в близко минало – в този случай страниците се разбиват на класове:

използвана модифицирана

клас 0 (0, 0) не не

клас 1 (0, 1) не да

клас 2 (1, 0) да не

клас 3 (1, 1) да да0

8^ма стратегия – Поддържане на група от свободни кадри. Често срещан метод.Когато настъпи странично прекъсване страницата се избира по някой от разгледаните алгоритми. Новата страница влиза в свободен кадър от групата свободни. Процесът може да започне работата си. Действителното изхвърляне на страницата става в по-късен момент. Ако се помни страницата и групата свободни то при странично прекъсване първо се проверява дали страницата не е в групата свободни. Съществува механизма заключване на кадри. Това е механизъм, който забранява извеждането на кадъра. За целта се използва отделен бит за блокировка. Буксуването (задръстването, trashing) – това е състоянието, когато производителността на системата пада рязко поради непрекъснато изхвърляне на еднакви страници. Най-важното е при разпределение на паметта е да бъде разпределено необходимият обем памет за да прочитат ефективно. Алгоритъм за борба с боксуването е ограничаване на опашката на готовите процеси чрез увеличаване на броя на активните процеси.

Тема 14 – Работно множество

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

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

По-конкретно, взаимодействието между процесора и контролерите протича по следния начин. Всеки контролер има няколко регистри за комуникация с процесора. В някои компютри регистрите са част от адресното пространство на паметта (например в М680хО) и не са необходими специални команди за вход/изход - използват се командите за работа с паметта. В други компютри се използва отделно адресно пространство за вход/изход (например I80x86) и всеки контролер има определени адреси. За да се изпълни входно-изходна операция, процесорът записва команда на съответния контролер, евентуално с параметри, в регистрите на контролера. Когато командата се приеме, процесорът може да продължи работата си паралелно с входно-изходната операция. След като командата се изпълни, контролерът изпраща прекъсване към процесора, което се обработва от процедура на ОС, която проверява резултата от операцията. Процесорът получава резултата и състоянието на устройството, като чете данните от съответните регистри на контролера. Ако например трябва да се прочете блок от буфера на дисковия контролер, е необходимо да се организира цикъл, в който при всяко повторение се чете байт или дума от блока.

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

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

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

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

Н
а фиг. 9.3 е показана типична дървовидна организация на входа/изхода, прилагана в големите компютърни системи. С паметта могат да бъдат свързани няколко канала, с всеки канал - няколко контролера и с всеки контролер - няколко устройства.

И тук се използват двата метода за синхронизация - прекъсване и проверка на готовност. Каналът може да генерира прекъсване към процесора, или процесорът да проверява периодично каналите, за да разбере кой от тях иска внимание. Повечето машини използват прекъсване, но има машини с проверка за готовност (например CDC 6000).

В гл. I подробно са разгледани различните типове ОС. Работата на една ОС може да се охарактеризира по следния начин. Процеси се създават, променят състоянието си и се унищожават. По време на съществуването си процесите обикновено имат нужда от общуване. Ресурсите непрекъснато се разпределят и освобождават. Интензивно се използват входно-изходните устройства и файловете с данни. Съществуват вътрешни процеси, изпълнявани от процесора (подробно разгледани в гл. II) и „външни" процеси, свързани с каналите за дании, периферните устройства и външната памет. Функциите на ОС могат да се обединят в няколко групи. Основната задача на ОС е управлението на процесите - създаване, унищожаване, преминаване между състоянията, взаимодействие, планиране, което е тясно свързано с използването на основния ресурс на ОС - процесора (респ. процесорите). Системата за управление на ресурсите се грижи за другите ресурси, като пространство на основна и вторична памети. Трета трупа е свързана с управлението на входа/изхода и файловете от данни.

Компонентите на ОС обикновено извикват чрез прекъсвания, тъй че тя трябва да включва и стандартни програми за обработка на прекъсвания. Обръщенията към функциите на ОС могат да бъдат явни, например чрез програмно прекъсване от вида „извикване на супервайзор" - SVC (Supervisor Call), или неявни, например при прекъсвания от таймера.

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

Елементите на ОС могат да бъдат транзитни и резидентни. Транзитните елементи временно се поместват в паметта и могат да се пазят в абсолютна или преместваема форма.

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

5.1. ЯДРО НА ОС

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

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

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

При този начин за извикване на примитивите лесно могат да се направят грешки и да се наруши целостта на системата. Затова той е ефективен в малките системи - в големите многопотребителски системи се прилага по-рядко. При тях, за да се гарантира работоспособността им, се вземат специални мерки за защита с използване на апаратни и програмни средства. Типичен пример е системата VAX/VMS [14]. Процесорът може да работи в четири режима на работа (ядро, организатор, супервайзор и потребител), които ОС използва, за да дефинира нива на защита чрез ограничаване на възможностите на процесите за достьп до страниците на виртуалната памет. Най-защитено и привилегировано е ниво „ядро" - в него се изпълняват драйверите на устройството, планиращата програма, управлението на страниците, както и привилегированите инструкции. Най-малко защитени са потребителските процеси, изпълнявани в ниво „потребител". Всеки процес има определени привилегии, които се проверяват при извикване на системни услуги чрез стандартния VAX-механизъм за извикване на подпрограмм

Използването на специални команди от вида SVC е по-разпространен начин за извикване на примитиви. Изпълнението на тези команди предизвиква специално прекъсване, означаващо заявка за обслужване. След анализа на причината за прекъсване, управлението се предава на съответния примитив (определен в параметьра на командата), който изпълнява необходимите действия. Очевидно е, че изпълнението на командата SVC e аналогия на извикване на подпрограма, както и командата за връщане от прекъсване може да се разглежда като връщане от подпрограма.

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

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

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

Освен функциите на ядрото, извиквани със синхронните сигнали за прекъсване (SVC-команди), ядрото включва и функции, извиквани чрез асинхронни сигнали за прекъсване (таймер, край на канална програма). Тези сигнали са извън зорното поле на пронесите и по същество се преобразуват в синхронизиращи сигнали.

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

В заключение може да се посочи, че в много случаи извикването на процеси напомня извикването на примитиви. Например, когато извикването е синхронизирано, обслужващият процес се държи като обща подпрограма. Основното различие е, че извикването на процес е no-сложно и се прилага за реализация на функции, който изискват много време за изпълнение и могат да се изпълняват паралелно с други процеси (могат да бъдат прекъсвани или да се обръщат към други процеси за обслужване). От друга страна, възможно е от някои функции на ядрото да се образуват служебни процеси. Достатъчно е в ядрото само да се реализират синхронизиращи примитиви и преобразуване на сигналите за прекъсване в синхронизиращи операции (естествено и превключване на процесора). Това е един начин за намаляване на ядрото, при което неговите функции се трансформират в комуникиращи процеси. На същия принцип е образувана системата THE (т. 5.4.2). Подобна е и идеята на микроядрото (т. 5.4.5).

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

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

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

- Идентификация на процеса (например име и вътрешен идентификатор).

- Състояние на процеса (готов, изпълняван, блокиран).

- Регистри на процесора (брояч на командите, общи регистри, статус и др.).

- Възможности на процеса (например режим на работа на процесора).

- Информация за връзките му с други процеси (вж. т. 5.2.3).

- Информация за планирането на процесора (например приоритет). –

- Информация за ресурсите, които процесорът владее или има право да получи - памет (база и гранични регистри или таблица на страниците, вж. гл. VII), устройства, отворени файлове и т.н.

- Статистически информация (използвано време на процесора, време на престой, брой породени процеси, отчетен номер и т.н.).

Съдържанието и организацията на дескрипторите до голяма степен зависи от особеностите на конкретната ОС. Те се изграждат при създаването на процеса и го определят по време на съществуването му. Дескрипторите обикновено се пазят в областта на ядрото (където са защитени), но могат да се поместят и в адресното пространство на процесите.

Примитиви за управление на процесите. В ОС непрекъснато се създават и унищожават процеси. Нагледен пример за това са процесите, определени от потребителските задания. Като процеси се изпълняват и много от функциите на ОС. Затова във всяка система трябва да има примитиви за създаване и унищожаване на процеси. Създаването на процес включва идентификация (определяне на вътрешния идентификатор и включването му в глобалния списък на известните на ОС процеси), определяне на начален приоритет, отделяне на началните ресурси (достатьчни да се изпълнява процеса, ако му бъде предоставен процесора), формиране на блок за управление. Създаденият процес се привежда в състояние на готовност, а ако е предвидено състояние на преустановяване (вж. фиг. 2.2) - в състояние „преустановен-готов".

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

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

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

При унищожаването на процес се освобождават неговите ресурси и идентификацията му се изважда от системните структура от данни.

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

Друга група са примитивите за организиране на взаимодействието между процесите. Те са разгледани подробно в гл.П.

Организация на процесите. Процесите могат да съществуват свързани или несвързани в някаква структура. Ако няма структурна организация, компонент на ОС е отговорен за създаването и унищожаването на процеси. Когато се появи заявка за извършване на някаква работа, той създава процес за нейното изпълнение, а след като работата бъде свършена - той го унищожава. Така всички процеси са „равни" в рамките на системата. Например за изпълнението на едно пакетно задание могат последователно да бъдат създадени и унищожени няколко процеса - компилация, свързване, зареждане и изпълнение. Необходимите ресурси се отделят или за цялото задание наведнъж, или на стьпки, а след изпълнението на процеса (заданието) те се освобождават. Подобно централизирано управление е доста усложнено, тъй като трябва да следи състоянието на всички процеси в системата. От друга страна, това допуска по-голяма свобода при разделянето на работата в сравнение със структурната организация.

В повечето ОС процесите образуват някаква структура, при която не всички процеси са равни. Например процесите могат да образуват дървовидна структура (вж. фиг. 5.3, т. 5.4.4). Процес може да създаде няколко нови процеса чрез съответния примитив. Вески от новосъздадените процеси може на свой ред да създаде други и т.н. Образуваното по този начин дърво показва подреждането (йерархията) на процесите в системата във всеки момент от времето.

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

Почти всяка ОС има някаква степен на структурност. Например, някои системи са изградени на йерархични нива, при което по-ниското ниво има по-малко права от пораждащото го. В т. 5.4 са дадени примери и дискутирани различните начини за структурна организация на ОС.

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

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

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

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

5.1.3. Управление на ресурсите

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

С всеки клас ресурси са свързани процедури за разпределение и за освобождаване на един или повече елементи на класа. Например памет може да се разпредели и освободи с операциите:

1. Request (размер, начален адрес)

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

Един еднороден механизъм за управление на ресурсите [10, 23] може да се изгради въз основа на семафорите на Дейкстра, като се предвидят четири примитива: създай семафор на ресурс, унищожи семафор на ресурс, разпредели ресурс и освободи ресурс. Двете основни операции над семафора на ресурс -разпредели и освободи, съответстват на операциите Р и V, но тяхната реализация е значително допълнена.

Всеки клас ресурси се представя със семафор. Блокът за управление на семафора включва: идентификация на семафора и родителя му по време на определянето (създаването) на ресурса; описание на ресурса (брой и идентификация на достъпните единици ресурс - например таблица на блоковете памет, списък на буфери или просто един бит, показващ наличие или отсъствие на събитие); опашка от блокирани процеси, очакващи да получат ресурса; адрес на програмата за разпределение на ресурса; допълнително поле (за съхранение на измерителни данни, текущо разпределение на ресурса и др.).

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

5.1.4. Поддръжка на входа и изхода

Устройствата се заемат и освобождават за индивидуално или за съвместно използване. Основните операции над устройствата са: четене, запас и управление. За изпълнението на тези три операции ядрото трябва да извърши действията: 1) иницииране на входно-изходните операции, и 2) обработка на прекъсванията по вход/изход, постъпили от канала (устройството) при завършване на операцията или при възникване на грешка.

Заявката към ядрото за изпълнение на входно-изходна операция може да има формата:

Изпълни вход/изход (канал, канална програма)

Нейното провеждане в ядрото може'да се опише със семафори по следния начин:

Р (разпредели [канал])

Старт на входа/изхода (канал, канална програма)

Р(край_на_операция [канал])

V (разпредели [канал])

Първата Р-операция включва извикване на програма за разпределение (планиране) на канала, а втората - очакване на прекъсване при завършване на входно-изходната операция. Това означава, че обработката на прекъсване включва операция V (край_на_операция [канал]).

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

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

Детайлите на реализацията зависят от конфигурацията на входно-изходната система и от особеностите на процесора и канала. Например в IBM/370 и ЕС ЕИМ са предвидени специални команди за вход/изход SIO (стартиране на вход/ изход), ТIO (проверка на вход/изход) и НIO (спиране на вход/изход), изпълнявани в привилегирован режим. В адресната част се съдържа номер на канал и номер на устройството. Адресът на каналната програма (CAW - адресната дума) винаги се пази на фиксирано място в паметта и затова тя трябва да се защити със семафор.

Възможен е и друг подход за реализиране на входно-изходните операции. Описаните no-горе функции се реализират чрез процеси за вход/изход [9, 10, 23,52]. За всяко входно-изходно устройство се определя процес, който управлява работата на устройството. Този процес, на който отговаря „зациклена програма", чака в изходна точка съобщение със заявка за операция с дадено устройство, изпратена от друг процес. Входно-изходният процес например анализира заявката, извиква съответните разпределители на канали и контролери, определя каналната програма, стартира входно-изходната операция, анализира прекъсванията по вход/изход, респективно за грешка и накрая изпраща отговор към извикалия го процес. В ядрото се поддържа информация за състоянието на апаратурата, планира се достъпа до нея, извършва се обработката на прекъсванията по вход/изход (на I ниво).

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

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

Работата с файловете наподобява тази с устройствата и файлът може да се разглежда като виртуално устройство. Това подобие е довело в много ОС (например в UNIX) до обединяване в една структура управлението на файловете и устройствата. В тези случаи устройствата се идентифицират със специални имена на файлове.

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

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

5.1.6. Обработка на прекъсванията

Прекъсванията са събития, при които се променя редът на изпълнение на командите от процесора. Прекъсванията се разделят на две категории: външни и вътрешни. Външните прекъсвания се предизвикват от събития, които произхождат извън прекъсвания процес и са асинхронны спрямо него (настъпват в произволен момент). Такива са прекъсванията от входно-изходната апаратура - всъщност основната функция на прекъсванията е синхронизацията на процесора с входа/изхода чрез сигнали за прекъсване, съобщаващи на процесора, че е настъпило изменение в състоянието на канал или устройство (завършена операция, възникнала е грешка, устройството е станало готово). Други подобни прекъсвания могат да се причинят от таймера, от пулта за управление, от друг процесор (в мултипроцесорна система).

Обработката на прекъсванията до голяма степей зависи от апаратната част на процесора, и в частност от системата за прекъсване. Има изключително голямо разнообразие от системи за прекъсване, които са и предмет на спор между конструкторите на апаратната и програмни части относно кои функции от обработката на прекъсванията как да се реализират. Действията по обработката на прекъсване, присъщи за повечето машини, са следните: 1) запомня се на определено място характеристиката на прекъсването, 2) запомня се състоянието (контекста) на прекъснатия процес (най-често в дескриптора на процеса), 3) определя се източникът на прекъсване и управлението се предава на съответната програма, 4) след изпълнение на програмата се възобновява нормалната работа.

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

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

Обслужващата програма извършва необходимите действия или само изпраща съобщения (събитие) към блокиран процес (вж. примера в т. 5.1.4). Преходът от изпълнение на една програма към друга се нарича превключване на контекста.

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

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

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

И накрая програмата за обработка на прекъсване трябва да възобнови нормалната работа. В зависимост от вида на прекъсване и дисциплината за планиране на процесите управлението може да бъде върнато: 1) на прекъснатия процес, 2) този процес може да е блокиран или записан в опашката на готовите процеси, а планиращата програма да избере процес за изпълнение от опашката.

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

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

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

• 
  Определения за ОС:
  

1. 
   ОС е набор от програми, осигуряващи възможност за нормално функциониране на КС
   
2. 
   ОС е съвкупност от програми, предназначени да организират изчислителния процес и да направят удобно общуването на потребителя и КС
   
3. 
   ОС е мениджър на ресурсите на КС
   
4. 
   ОС е множество от последователни процеси, които взаимодействат помежду си
   
5. 
   ОС е средство за създаване на виртуални машини
   
6. 
   ОС е средство, разширяващо функциите на апаратната част, създавайки т.нар. абстрактна машина
   
7. 
   ОС е съвкупност от програми, управляващи изпълнението на потребителските програми и предоставящи на потребителя средства за разработка на програмите
   

• 
  Функция на ОС
  

1. 
   Осигурява интерфейса с потребителя.
   
2. 
   ОС осигурява и осъществява ефективно управление на ресурсите на КС:
   

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

• 
  Данни – ОС осигурява възможността за работа с общи данни и колективното им ползване
  
• 
  Програми – ОС осигурява възможността за ползване на програмите от няколко потребителя
  
  
  

3. 
   Осигурява и управлява възможността за съвместно използване на ресурсите, тоест управлява прекъсванията и взаимодействията между процесите.
   
4. 
   Планира достъпа на потребителите до апаратните ресурси на КС (поддържани на опашки)
   
5. 
   Осъществява възстановяване на информацията и изчислителния процес след аварии (грешки)
   
   
   

• 
  ОС управлява следните ресурси: процесор, памет (външна и вътрешна), устройства за вход и изход, данни и програми
  
  
  
• 
  Задължителни качества на ОС
  

1. 
   Надеждност
   
2. 
   Защита – трябва да защитава потребителя от чужди грешки и от опити за влизане в програмата
   
3. 
   Ефективност
   
4. 
   Предказуемост – желателно е времето за изпълнение на една програма да е приблизително еднакво при различните натоварвания на КС
   
   
   
5. 
   Удобство
   

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

A – Флаг за присъствие на страницата в ОП

N – Начален адрес на страничен кадър в ОП

S – Адрес от външната памет

P – Поле за защита – определя вида на достъпа до страницата

R – Поле за обръщение – отразява използването на страницата като се обновява при всяко адресиране – четене и запис

M – поле за модификация (промяна в страницата) – това поле се обновява при всеки запис

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

Основна памет.

Multithreading, Multiprogramming и Multiprocessing.

Registry (регистратура) – Регистратурата е централната информационна база от данни, която Windows използва в работата си. Регистратурата е структурирана като йерархична база от данни от ключове, където всеки ключ може да съдържа други ключове или данни. Тя се съдържа в два файла – system.dat, съдържащ информацията за компютъра, и user.dat, съдържащ информация за потребителя. От стартирането на Windows до затварянето му той чете информация от регистратурата и я актуализира в зависимост от промените, които системата претърпява. Всичко, което се променя или конфигурира в Control Panel се превръща в настройки на регистратурата. Главната роля на регистратурата е да служи като главна система за съхранение . Използва се главно от системата Plug and Play. Когато се инсталира ново устройство системата проверява текущата конфигурация в регистратурата за да определи хардуерните , които не се използват. Така новото устройство може да бъде конфигурирано без конфликти с устройствата, инсталирани в системата. Естествено устройството трябва да е съвместимо с Plug and Play

1. 
   Линия за заявка на прекъсвания – IRQ – всяко устройство трябва да може да известява ЦП за завършване на операциите си
   
2. 
   DMA – канал за директен достъп
   
3. 
   Обкласти от паметта
   
4. 
   Адреси на в/и портове.
   

Поддръжката на Plug and Play се поддържа от мениджъра на конфигурацията. Той идентифицира всяка шина към устройствата към схемата както и конфигурационната среда на всяко устройство. На базата на това той осигурява на всяко устройство на КС да функционира без конфликти с другите устройства.

1. 
   Memory Paging
   
2. 
   Планиране на процесите (Process Scheduling)
   
3. 
   Поддръжка на MSDOS режим
   

Планировчика на процеса осигурява ресурсите на приложението и другите процеси, които се изпълняват като позволява съвместното им изпълнение. Windows осигурява механизма нишково изпълнение (multithreading). Този механизъм облекчава изпълнението на приложенията. В термините на ОС едно приложение е процес. Всеки процес се състои от поне една нишка, която отъждествява хода на изпълняваната програма. Бихме могли да твърдим че нишката е единица за код, която може да получи част от времето на процесора от ОС. Всяко приложение може да съдържа много нишки на даден процес, т.е. да сложи началото на много нишки. Така се увеличава количеството изпълняван код на приложението за дадена единица време. В случая се работи със заявка на страница при въвеждане. Страницата е 4k, а виртуалната й памет е 4Gb.

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

Системните и потребителските процеси се изграждат съгласно еднакви принципи, планират се от една и съща програма и имат подобни възможности. Трябва да се отбележи, обаче, че има и някои различия, произтичащи от по-големите права на системните процеси и техните функции (например процесите, управляващи ресурсите, не се състезават за достьп до тях, тъй като ги управляват; за другите системни процеси ресурсите са определени първоначално и еднозначно и т.н.).

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

• Изпълняван - процесорът е предоставен на процеса.

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

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

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

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

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

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

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

К
онцепцията може да се обобщи (фиг. 2.2). Процесът може да преустанови сам себе си или да бъде преустановен от друг процес (родител или ОС), с оглед да се спре изпълнението му. Преустановеният процес може да продължи изпълнението си, само ако друг процес го възобнови. При създаването на процес той не се предоставя веднага за изпълнение, а се поставя в преустановено състояние.

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

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

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

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