INDEX

  1. Сравнение между мултипрограмна и мултипроцесорна ОС 
  2. Прилики и разлики между мултипрограмна пакетна система и мултипрограмна система с времеделене
  3. Дефиниция за процес
  4. Състояния на процеса
  5. Условия за вазимно изключване на процеси
  6. Прилики и разлики между процес и примитив 
  7. Устройства и процеси
  8. Реализиране на семафор
  9. Реализация на монитор със семафор
  10. Решения на класически проблеми и примери с буфери
  11. Еквивалентност на средства за взаимодействие (Реализация на съобщения със семафори)
  12. Процеси и потоци – прилики и разлики
  13. Съпрограми
  14. Мъртва хватка
  15. Проблемът с безкрайното отлагане
  16. RAID контролери
  17. Справочници като ациклични графи
  18. Стратегии за извеждане на страници
  19. По-подробно за LRU ( Апроксимации на LRU)
  20. Клъстери – примери за Windows и Unix
  21. Модел клиент-сървър
  22. Буферипране
  23. Аномалия на Belady
  24. Управление на процесора на ниско ниво (сравнение на алгоритми)
  25. Методи за управление на паметта





Сравнение между мултипрограмна и мултипроцесорна ОС


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

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

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

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

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

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

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


Прилики и разлики между мултипрограмна пакетна система и мултипрограмна система с времеделене


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

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

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

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

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

Дефиниция за процес


Понятието последователен процес (или само процес) се смята за изходна точка в теорията на ОС. Използват се и други термини, като задача и действие. Едно разпространено, неформално определение на процес е: последователният процес е работа, извършвана от последователен процесор при изпълнението на програмата с нейните данни [23]. Други подобни определения са: програма в етап на изпълнение, програмна единица, изпълняваща независима работа, асинхронна работа. От логическа гледна точка всеки процес има собствен процесор и програма. В действителност няколко процеси могат да делят един и същ процесор (тогава може да се говори за виртуален процесор) или една и съща програма (тогава те се смятат за различни последователности за изпълнение). Процесът не е еквивалентен на програмата - той е активен обект, докато програмата е пасивен обект. Процесът е двойката „процесор програма" при изпълнение. Процесът, за разлика от програмата, още влючва стек, текущите стойности на брояча на команди и другите регистри на процесора, структури от данни, поддържани от ОС за управление на изпълнението му.


Състояния на процеса


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

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

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

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

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

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

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

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

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

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


Условия за вазимно изключване на процеси

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

Коректното решаване на проблема на взаимното изключване трябва да отговаря на следните критерии:

  1. Само един процес може да използва ресурса в даден момент.
  2. Ако няколко процеса едновременно желаят ресурса, той трябва да бъде предоставен на един от тях в крайно време.
  3. Ако процес получи ресурс, той трябва да го освободи в крайно време. Никакви други предположения относно относителните скорости на процесите не се правят - дори през времето, когато не използват ресурса, те могат да се блокират.

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

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


Прилики и разлики между процес и примитив

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

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

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

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


Устройства и процеси

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

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


Реализиране на семафор

Реализирането на критични секции с помощта на блокировка на паметта или на команди TS [TS (Test and Set -провери и установи). Командата TS(a,b) има два параметъра от логически тип. Действието й се свежда до следното. Командата чете стойността на логическата променлива Ь, записва я в а (а:=Ь) и установява b:=true. ] осигурява взаимно изключване, но е сложно и неефективно, особено при повече от два процеса. За преодоляване на горните трудности Дейкстра въвежда две примитивни операции Р и V, които оперират над цели променливи, наречени семафори. Различават се двоични семафори, приемащи стойности само 0 и 1, и общи (броячни) семафори, приемащи цели, неотрицателни стойности. Класическата дефиниция на Р и е: 

1. P(s): while s = 0 do skip ; s = s - 1;

Извиквайки P(s), процесът чака при стойност на семафора s=0 (изпълнява празен цикъл), докато друг процес не го освободи чрез V(s). Тогава стойността на се намалява и процесът продължава.


2. V(s):s = s+ 1;

Стойността на семафора се увеличава и процесът продължава. време да модифицира същия семафор. Единствено по време на празната операция skip може да се направи модификация

Освен това трябва да има инициализация на семафора 5 чрез операция

s := < цяла константа >.

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

Семафорните примитиви лесно могат да бъдат реализирани чрез командата TS(wait, s), където wait и са локална и глобална променливи (инициализирани съответно с true и false):

P(s): while wait do TS(wait, s); V(s): s := false;

Главният недостатък на взаимното изключване, решено по описаните дотук начини и при дефиницията на Р и Ve, че те изискват активно очакване. Когато процес е в критична секция, другите процеси са принудени да изпадат в цикъл на очакване, докато получат възможност да влязат в критичната си секция. При това те напразно изразходват ресурси - процесорно време и т.н.

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

За да се отстрани този недостатък, трябва да се модифицира дефиницията на Р и V. Когато процес изпълнява операция P(s) и открие, че s = 0, той се блокира (вместо да чака), след което се избира друг процес за изпълнение. За разлика от активното очакване 5 не се проверява непрекъснато, тъй като процесът чака в опашка на блокирани процеси, а вместо него се изпълняват други процеси. Блокираният процес може да бъде стартиран отново чрез изпълнение на V(s) от друг процес, при което блокираният процес става готов.

Примерна реализация на Р и V, съгласно горната дефиниция, е дадена на фиг. 2.10. Необходимо е семафорите да се дефинират като запис.

Процедурата за инициализация initialize трябва да установява начално състояние на сем. стойност и на сем. опашка. Обикновено се прилага дисциплина FIFO (FCFS) за управление на опашката, но се използват и други дисциплини. Коректното използване на семафорите не зависи от стратегията на опашката.

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



Реализация на монитор със семафор


Реализацията на мониторите със семафори е следната (за монитора на Хансен). Тъй като мониторните процедури образуват критични секции, въвежда се семафор взаимно_изключване (инициализиран с 1). Входът във всяка процедура се реализира с Р(взаимно изключване). Всяка променлива - условие х се реализира с променлива чакащи_х и семафор семафор_х, които имат начални стойности нула. Операцията wait(x) се реализира така:

чакащих := чакащи_х + 1;

У(взаимно_изключване);

Р(семафор_х);

чакащих := чакащи_х - 1;

Операцията signal(x) се реализира по следния начин: if чакащих Ф 0 then У(семафорх) else V (взаимноизключване);

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

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

Тази ситуация е показана на фиг. 3.4. Предполага се, че мониторните процедури се извикват от процесите А, Б, В в реда: M.pl, М.р2, М.рЗ, при което извикването на М.рЗ се прави преди процес Б да е напуснал мо¬нитора. Числата на фиг. 3.4 показват показват реда на изпълнението на процедурите.

Вижда се, че М.рЗ трябва да се

изпълни след M.pl. Операцията wait(x)

представлява очакване на условие х,

Монитор М

което е функция на общите променливи vl,..., vn. Процесът Б сигнализира чрез signal{x), че условието е изпълнено. Ако не се продължи в процеса А и се остави В да влезе в монитора, възможно е с извикването на рЗ да се наруши валидността на условието.

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


Решения на класически проблеми и примери с буфери


Безкраен буфер. Предполага се, че процесите производител и потребител са свързани чрез буфер, който се състои от безкраен брой елементи с еднакъв размер - всеки съдържащ един запис от данни. Буферът може да е организиран във вид на опашка. Производителят добавя записи в края на опашката, като винаги има на разположение празен елемент, а потребителят чете от началото на опашката, като може да чака за нов запис. Синхронизация е необходима, за да не може потребителят да чете от празна опашка. Ето защо е необходимо сведение за пълните елементи. Затова се въвежда семафор брой, инициализиран с 0. Втори семафор вз_изкл, инициализиран с 1, ще служи за взаимно изключване при работа с буфера буфер - предполага се, че е критична секция.

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

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

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

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

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

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

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

Първият проблем с решен с конструкцията if..Alien Р(запис). Всички читатели трябва да свършат, за да започне писател работа. Ако писател е в критична секция, те. :ншис=--0, един читател ще чака. Останалите читатели ще чакат пред семафор взаимно изкл.

Безкрайното отлагане на писател се решава с подреждането на опашката пред семафор чипис. Когато писател направи У(запис), процесорът може да се предостави или на читател, или на писател. Друг подход е изборът да се прави от програмата за планиране на ниско ниво (ni.VI).

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

Обядващите философи се смятат за класически проблем на синхронизация, но не поради неговата практическа важност, а защото е пример за широк клас проблеми на паралелността. Например, те са полезни за моделиране на процеси, които се състезават за монополен достъп до ограничен брой ресурси (магнитни ленти и др.). Едно негово решение е да се представи всяка вилица със семафор (фиг. 2.196). Философът се опитва да вземе вилица чрез Р-операция, а я освобождава чрез F-операция.

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

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

Други възможни изходи от мъртвата хватка са:

  1. Да се позволи най-много на четири философа да седят на масата. Решението изисква допълнителен броячен семафор за допускане до масата.
  2. Да се позволи на философ да вземе вилица, само ако и двете са на разположение (това трябва да се извърши в критичната секция).
  3. Да се използва асиметрично решение. То е, че четен философ вдига първо лявата си вилица и след това дясната, докато нечетен философ вдига първо дясната, а след това лявата.

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

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

За да се синхронизират процесите, в решението на фиг. 2.20 се използват: броячен семафор клиенти - брои чакащите клиенти (без подстригвания в момента), двоичен семафор бръснар - за заетост на бръснаря и двоичен семафор вз_изкл за взаимно изключване по отношение на променливата чакащи, която брои клиентите (предполага се, че стойността на семафор клиенти не може да се прочете). Инициализирани са съответно с 0, 0, 1,0.

Проблемът може да се задълбочи по следния начин:

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


Еквивалентност на средства за взаимодействие

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

Операцията send(npueник, съобщение) работи с дескриптора на получателя и семафорите се използват по следния начин:

Р{вз_изкл); запис на съобщението в списъка; У(получено); У(вз_изкл).

Операцията receive{източник, съобщение) също работи с дескриптора на получателя и семафорите се използват така:

Р{получено); Р(вз_изкл); предаване на първото съобщение от списъка, като в източник се записва идентификатора на подателя и в съобщение - текста на съобщението; У{вз_изкл).

Индиректна комуникация може да се реализира, като с всеки процес се свърже семафор (инициализиран с 0), пред който процесът се блокира, когато send и receive трябва да чакат [93]. Обща буферна област се използва за пазене на пощенските кутии, всяка съдържаща гнезда за съобщения, две опашки от процеси - чакащи за изпращане (кутията е пълна) и чакащи за получаване (кутията е празна), различни броячи. Буферната област е също защитена със семафор за взаимно изключване.

Действията на send и receive при празна, респ. пълна, пощенска кутия са очевидни и няма да се обсъждат.

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

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

Когато send не може да завърши поради пълна пощенска кутия, името на подателя се записва в опашката на пощенската кутия, освобождава се чрез семафора буферната област и се прави Р над семафора на подателя. По-късно, когато получател извади съобщение и забележи, че има процес в опашката за изпращане в тази кутия, подателят ще бъде събуден чрез V.

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

Реализация на семафори чрез съобщения. Ако е на разположение система със съобщения, възможна е реализация чрез въвеждане на нов процес - синхронизиращ процес [93]. Той включва брояч и свързан списък от чакащи процеси за всеки семафор. За да направи Р или V, желаещият процес извиква съответна библиотечна процедура, която изпраща съобщение към синхронизиращия процес, специфицирайки желаната операция и семафора. Процедурата след това прави receive, за да получи отговор от синхронизиращия процес.

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


Процеси и потоци – прилики и разлики


Всеки процес е дефиниран със системни ресурси и адресно пространство, в което се изпълнява, и има единичен поток на управление. В много случай е изгодно ресурсите на процеса да се споделят и използват паралелно. Типичен пример е файловият сървър, където, с оглед на ефективност, трябва едновременно да се обслужват на няколко заявки. Затова в някои нови системи е включена възможност за поддръжка на няколко потока (threads, буквално нишки) в единичен процес. Понякога потоците се наричат олекотени процеси (LWP, Lightweight Processes), а процесите с много потоци - задачи (task).

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

В много отношения потоците приличат на процесите [28, 66, 69, 88, 93]. Всеки поток протича последователно, изпълнявайки собствена кодова последователност, има собствен брояч на командите, свои регистри и стек, може да създава деца. Потоците, подобно на процесите, се планират и делят процесора. Обаче, усилията за преключване на контекста на два потока са много по-малки в сравнение с превключването на контекста на два процеса. Това е, преди всичко, защото потоците в процеса споделят едни и същи области на паметта и управляващи структури от данни. Потоците също преминават през различни състояния, например, когато поток се блокира, друг поток на същия процес може да се активизира.

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

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

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

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

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


Съпрограми


За разлика от подпрограмите, които са подчинени на извикващия ги модул, съпрограмите не са подчинени модули и позволяват симетрично предаване на управлението. Превключването на процесора от една съпрограма към друга става явно с оператор от вида resume x.

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




Мъртва хватка


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

Кофман формулира необходимите условия, които трябва да се изпълнят едновременно, за да настъпи мъртва хватка:

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


Проблемът с безкрайното отлагане

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

Когато в ОС ресурсите се разпределят по приоритетен принцип, същото явление ще настъпи с постоянното идване на по-високо приоритетни процеси. В някои системи се използва „стареене" на процесите, т.е. с течение на времето техният приоритет се увеличава.

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

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


RAID контролери

Това представляват масиви с излишък от независими (или евтини) дискове (RAID, Redundant Array of Independent (Inexpensive) Disks), които повишават производителността и надеждността. Информационният излишък може да се реализира по различни начини. Най-простата организация (RAID, ниво 1) се състои в дублиране на всеки диск, създавайки му огледален образ (mirroring, shadowing). Решението, разбира се, е скъпо.

В по-сложните организации данните са разпределени по масива от дискови устройства - те се записват по отделните дискове на „отрязъци" (блокове, сектори, байтове или други единици), съгласно кръгова дисциплина. Освен това, за еквивалентните отрязъци на всеки диск се създава съответен отрязък, съдържащ контролни разреди за коригиране на единични неизправности. Например, ако масивът има 5 диска, тогава за сектор 0 на дисковете 1, 2, 3, 4 се изчисляват и запомнят в диск 5 контролни разреди. Изчислението се извършва на ниво „бит" за всеки байт.

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

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

В RAID 4 и RAID 5 се използват големи отрязъци (например блокове) и независим достъп, което позволява едновременно да се обслужват няколко заявки. При RAID 4 се използва един допълнителен диск за контролните разреди, докато при RAID 5 те са разпределени по всички дискове.


Справочници като ациклични графи


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

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

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

Тази структура на справочника е по-гъвкава в сравнение с обикновената дървовидна структура, но създава някои проблеми:

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

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

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

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

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




Стратегии за извеждане на страници

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

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

Извеждане на случайна страница. Лесна за реализация стратегия, която не дискриминира потребители - страница се избира равновероятно. Очевидно е, че често се изхвърлят необходими страници. Тъй като тук се подхожда съгласно принципа „господар или пропаднал", в реалните системи рядко се прилага.

Извеждане на първата въведена страница (FIFO). C всяка страница се свързва моментът на постъпването й в основната памет и при необходимост се извежда най-старата страница. Алгоритъмът е прост, но дава лоши резултати, особено при натоварване на системата, тъй като често се изхвърлят нужни страници. Най-стара страница не означава най-малко необходима. За този алгоритъм е характерна аномалията на Биледи, която се свежда до увеличаване на броя на прекъсванията с увеличаване на броя на кадрите, отделени на процеса.

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

Извеждане на най-рядко използвана страница (LFU). LFU поддържа брояч на обръщанията към всяка страница. Извежда се страница с най-малка стойност на брояча, т.е. най-рядко използваната. Мотивацията е, че активно използваната страница има голяма стойност на брояча. Но може да се получи така, че в началната фаза на програмата страницата много активно се използва, но после изобщо да не трябва. Едно решение е през определен интервал броячът да се премества надясно на 1 бит, оформяйки експоненциално среден брой на обръщанията. Съществуват много подобни реализации на този алгоритъм [93].

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

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

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

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


По-подробно за LRU

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

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

Реализацията на всеки от LRU-алгоритмите изисква апаратна поддръжка, тъй като стекът или регистърът трябва да се обновяват при всяко обръщане към паметта. Програмно решение, реализирано чрез прекъсване при обръщане към паметта, би намалило бързодействието многократно. Затова в малко ОС се прилага програмното решение. Много системи използват различни апроксимации на LRU, които изискват минимална апаратна поддръжка и дават задоволителна производителност.

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

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

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

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

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

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

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

Клас 0 (0, 0): не е използвана и не е модифицирана;

Клас 1 (0, 1): не е използвана, но е модифицирана;

Клас 2 (1, 0): използвана е, но не е модифицирана;

Клас 3 (1, 1): използвана е и е модифицирана.

Алгоритъмът (наричан още NRU - Not Recently Used) изхвърля страница от най-ниския непразен клас. Ако има повече страници в един клас, се прилага FIFO или случаен избор. Клас 1 изглежда нереален (няма обръщане), но това се дължи на периодичното нулиране на битовете на използване. Неявно в алгоритъма се приема, че е по-добре да се изхвърли модифицирана страница, която не е използвана поне един интервал, отколкото немодифицирана, но често използвана страница.

Алгоритъмът обикновено се реализира като разширение на часовниковия с една стрелка. Най-напред се търси страница от клас 0. Ако няма, сканирането се повтаря отначало и се търси страница от клас 1 (при това се нулира битът на използване на всяка проверена страница). Ако няма страница и от този клас, сканира се отново за клас 0, и т.н. 


Клъстери – примери за Windows и Unix

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

Конфигурация. Клъстерите могат да се класифицират по различни начини. Hewlett Packard дава следната класификация.

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

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

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

За да се намали комуникационното натоварване чрез елиминиране на копирането, могат да се използват сървъри, свързани към общи дискове. Най-често дисковата подсистема използва дублиране или масив от дискове (RAID), за да се компенсира риска от повреда.

Един вариант на тази схема се нарича никакво съвместно използване (shared nothing). Общите дискове са разделени на томове, всеки притежаван от отделен компютър. Ако компютър се повреди, клъстерът трябва да се преконфигурира, така че друг компютър да получи неговия том. 

Възможно е да се използват много сървъри, едновременно имащи достъп до едни и същи дискове, т.е. всеки компютър има достъп до всички томове на всички дискове. Този подход се нарича съвместно използван диск (shared disk). Изисква се да има някакво заключване, така че достъп до определени данни да има само един компютър в даден момент.

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

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

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

Примери. Solaris МС е разпределена ОС, изградена на базата на Solaris UNIX на SUN. Тя предоставя клъстер, който се явява на потребителя и на приложенията като единичен компютър, работещ под Solaris. Главните особености на МС са:

  • Използва се обектният модел на CORBA за дефиниране на обекти и отдалечено извикване на процедури.
  • Прилага се глобално управление на процесите, така че мястото на процесите е прозрачно за потребителя.
  • Използват се различни методи за управление на мрежовия трафик, включително и за възлите на клъстера.
  • Файловата система е глобална и използва концепцията за виртуалната файлова система и v-възли, както и файлова система proxy, разположена над съществуващата файлова система на Solaris. Процес може да отвори файл, намиращ се в произволен възел - при това процесите от всички възли използват едно и също име-пътека.

Wolfpack е клъстерна технология, разработена за Windows NT (2000). Тя е от вида „никакво съвместно използване" - всеки дисков том и други ресурси се притежават от единичен компютър. При проектирането на Wolfpack са използвани следните концепции:

  • Услугите на клъстер се осигуряват от комплект програми, управляващи всички специфични за клъстера дейности.
  • Всички ресурси са обекти, представящи актуалните ресурси на системата, включително физическите устройства и логическите единици (логически дискови томове, IP адреси, приложения, бази от данни). Това се управлява от услугите на клъстера.
  • Набор от ресурси, управлявани като една отделна единица е група. Обикновено тя включва всички елементи, необходими за изпълнението на специфично приложение и за системата-клиент (за да се включи към услугата, предоставена от приложението).
  • Ресурс е „на разположение" във възел, когато предоставя услуга в този възел.


Модел клиент-сървър

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

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

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

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

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

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

Буфериране

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

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

Известни са много дисциплини за управление-на буферите [9,10,18,23,25, 88]. При простото буфериране се отделят един входен и един изходен буфер -по време на работата с файла те се прикрепят към устройството и изпълняват само една функция. Възможно е съвместяване на работната област с един от буферите. Методът е прост за реализация, но е приемлив само при много малък обем на прехвърляните данни.

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

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

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

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

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


Аномалия на Belady


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

За този алгоритъм е характерна аномалията на Биледи, която се свежда до увеличаване на броя на прекъсванията с увеличаване на броя на кадрите, отделени на процеса. Тя е илюстрирана на фиг. за програма с 5 виртуални страници, използвани в реда: 123412512345. Броят на прекъсванията (10) за 4 кадъра е по-голям от броя на прекъс¬ванията (8)за 3 кадъра.

Има клас от алгоритми, наречени стекови алгоритми, които не страдат от аномалията на Биледи (оптималният и LR.U са такива). За тях може да се покаже, че множеството страници в паметта за п кадри е винаги подмножество на множеството страници, които биха били в паметта за и+1 кадри. За LRU множеството страници в паметта включва п страници, използвани последни. Ако броят на кадрите се увеличи с 1, тези п страници ще останат в паметта (те все още са последните използвани) и няма да има допълнителни прекъсвания.


Управление на процесора на ниско ниво (сравнение на алгоритми)

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

Ново разпределение на процесора е принципно възможно, когато: изпълняваният процес доброволно се отказва от продължаването на своята работа (изпълнил се е или се е самоблокирал, например пред входно-изходна операция) или се блокира от системен механизъм; в резултат на настъпило събитие блокиран процес е преминал в състояние на готовност; процесът е изменил приоритета си (в приоритетните системи) или е постъпил по-високоприоритетен процес; изменен е броят на процесорите (ако е многопроцесорна система). 

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

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

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

Най-краткото задание първо (SJF). Дисциплината е известна още като най-краткият процес - следващ (SPN), т.е. процесът с най-краткото предполагаемо време за обработка е следващият избран. Тази дисциплина снижава в сравнение с FCFS общото средно време за чакане, като средното време за чакане на кратките процеси е по-малко, отколкото на дългите процеси, но това се постига с голяма цена. Дисперсията на времето за чакане нараства, оттук намалява предсказуемостта на обслужването (за много потребители предсказуемостта е почти толкова важна, колкото и скоростта на изпълнение).

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

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

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

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

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

Най-кратко оставащо време (SRT). По-разумно процесорът може да се разпределя по най-кратко оставащо време. „Оставащо време" е разликата между времето, заявено от потребителя и времето, което вече е използвано от процеса (измерва се от системата с часовник). При SRT кратките процеси още повече са облагодетелствани за сметка на дългите. По-дългите задания даже ще имат по-дълго време за чакане и по-голяма дисперсия в сравнение с SJF.

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

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

Друга стратегия, използваща информацията, получена по време на пребиваването на процеса в системата, се дава от правилата на Клейнрок. В тях се прилага линейно нарастващ приоритет. При влизане в системата процесът получава някакъв приоритет, който нараства с коефициент а по време на чакане в опашката на готовите процеси и с коефициент Ъ по време на изпълнение. В зависимост от избора на а и Ъ се получават различни правила. Ако 0 < а < Ь, опашката се обслужва в ред FCFS. Ако 0 > Ъ > а, получава се ред LCFS. Могат да се измислят много варианти, например а и Ъ да зависят от външния приоритет, т.е. от загубите, които потребителите смятат за приемливи. Могат да се изберат и нелинейни функции. Може да се направи така, че приоритетът да намалява по линеен закон с времето. Когато достигне някое максимално време, приоритетът скача до някаква голяма стойност. Това благоприятства кратките процеси, като при това се спазва условието, че нито един процес няма да чака безкрайно дълго. По подобен начин може да се допълни правилото SJF, така че дългите процеси след известно време в система получават допълнителен приоритет.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Методи за управление на паметта

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

Паметта се дели на две части - една за резидентната част на ОС и една за потребителската програма. ОС може да се въведе в горната или в долната част - главният фактор за избор е къде са векторите на прекъсване.

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

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

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


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

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

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

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

Фиксирани раздели

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

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

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

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

Разпределението на фиксирани раздели може да се допълни с размяна. Ако се използва приоритетна политика, при постъпването на по-високоприоритетно задание програмата за управление на паметта може да изхвърли върху диск по-нископриоритетно задание, което след изпълнение на високоприоритетното задание се връща отново в паметта за изпълнение.

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

Обикновено заданията се въвеждат отново в едни и същи раздели. Това ограничение се диктува от метода за преместване и от политиката за разпределение на разделите. Ако се използва динамично преместване, например с помощта на базов и граничен регистър, е възможно да се организира размяна в различни раздели. Описаните решения са използвани сполучливо например в MULTIJOB (ICL 4-72) за интерактивни задачи.

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

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

Променливи раздели

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

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

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

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

Преместваеми раздели

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

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

Проблемът, който възниква при преместването на раздели е, че трябва да бъдат коригирани не само адресите на премествания раздел, но и адреси в регистрите на процесора или изпратени към подпрограми. Също така не трябва да се извършва сгьстяване по време на входно-изходна операция, която работи с някакъв раздел. Ако процес е породил няколко подпроцеса, трябва да се изчака завършването им.

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

Управление на паметта

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

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

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

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

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

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

За пълнота трябва да се споменат още два алгоритъма. Среща се и стратегията за избор на най-малко подходящ блок. Обосновката е, че остават по-големи дупки памет, които могат да се окажат по-полезни в сравнение с малките дупки при „най-подходящ". Направените моделирания показват, че това не е удачна стратегия.

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

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

Използване на системата на „близнаците" (buddy system). Този подход ускорява сливането на освободените блокове, като се използва фактът, че адресите са двоични. Памет се предоставя на блокове с дължина, представляваща степен на 2. Освен това се използват отделни списъци за блоковете с еднакви размери. Всеки адрес, завършващ на к нули, се разглежда като начален адрес на блок с дължина 2к. За всяка стойност на к в интервала от 0 до п, където 2к е обемът на цялата памет, се създава отделен списък на всички свободни блокове с размер 2к. Нека например е необходим блок с дължина 2к и такъв няма. Тогава се преглежда списъкът на блоковете с дължина 2k+1, намира се блок (ако има) и се разцепва на два „близнака" с дължина 2к (единият блок се използва, а другият се включва в съответния списък). Ако няма блок с дължина 2k+1, търси се и евентуално се разцепва на четири блок с дължина 2к+2, и т.н.

При освобождаването на блок най-напред се проверява дали е свободен неговият „близнак". Ако е свободен, те се обединяват в един, който на свой ред може да се обедини с близнака си и т.н. Алгоритмите на работа при тази стратегия са прости и се изпълняват малко по-бързо в сравнение с „първи подходящ блок". Но тук се губи памет, тъй като обемът на отделяната област трябва да се закръгля до най-близката степен на 2.

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

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

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

Деленето на страници се осъществява при транслацията на програмите, като указаните в командите адреси се състоят от две компоненти - номер на страница (р) и отместване (d) спрямо началото на страницата. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

За простота на реализация сегментите се означават с номера вместо с имена. Обикновено потребителската програма се транслира, като компилаторът автоматично   създава сегментите, отразявайки структурата на първичнатапрограма. Адресацията в сегментираната програма е двуразмерна - номер на сегмент и отместване спрямо началото на сегмента. Достъпът до оперативната памет може да се реализира подобно на този при страничната организация (фиг. 7.3). С всяко задание (процес) се свързва таблица на сегментите. Всеки неин елемент съдържа базов адрес на сегмент и неговата дължина (може да включва и друга информация, например за защита). Адресът на самата таблица, заедно с нейната дължина, се пази в регистър. При изпълнението на програмата абсолютните адреси се определят динамично, като с помощта на таблицата номерът на сегмента се превръща в базов адрес на сегмента (номерът на сегмента служи като индекс), към който се прибавя отместването. Подобно на страничната организация и тук са необходими две обръщания към паметта за всеки>логйчески адрес със същите неприятни последствия. Затова в много системи описаните действия по изчисление на адреса, както и проверката на дължината на сегмента, се извършват апаратно (регистри, буферна памет, асоциативна памет). С малка асоциативна памет (с 8 или 16 регистъра) може да се намали закъснението на времето за достъп до 10-15% увеличение в сравнение с директния достъп до паметта. 

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

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

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

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

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

Програмата за планиране на заданията трябва да намери памет за всички сегменти на потребителската програма. Разпределението на паметта се решава подобно на схемата с променливи раздели, например първи подходящ или най-подходящ. Ако вследствие на фрагментацията няма достатъчно памет, може да се приложи сгъстяване или просто заданието ще чака. По същество при използването на сегментация възникват същите проблеми, разгледани при разпределение с преместваеми раздели. Пример за подобна машина е UNIVAC 1100 с два регистъра - за команди и за данни.

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

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

Достъпът до дума от паметта става по следния начин :

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