Oперационни системи- лекции


Категория на документа: Информатика


P1 10 5 5
P2 9 3 6
P3 4 2 2

Тогава системата се намира в ненадеждно състояние. Действително, има 2 свободни ресурса. Системата ги разпределя на P3. След като P3 завърши и освободи заетите ресурси ще се получат общо 4 свободни ресурса, които не достигат нито на P1 нито на P2.

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

Откриване и възстановяване от дедлок

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

27. Планиране на процесите. Дисциплини.

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

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

Нива на планиране

В рамките на една операционна система може да има планировчици на различни нива. Досега в операционните системи се реализират
най-много три нива на планиране.
Високото ниво на планиране е характерно за по-старите операционни системи, където се реализира понятието задание (job). Затова още се нарича job scheduling. На това ниво планировчикът преценя кое от чакащите задания да започне работа. В модела на процесите на
UNIX/LINUX на това ниво планировчикът трябва да определя в какъв ред да се удоволетворяват заявките за създаване на нови процеси, ако те са повече от една.
Ниското ниво на планиране е най-използваното в съвременните операционни системи. На това ниво планировчикът се нарича scheduler.
Когато се освободи централният процесор, този планировчик управлява кой от процесите в състояние готов ще премине в състояние текущ.
Също така, той определя дали процесът, който е текущ трябва да бъде свален от централния процесор и да премине в състояние преразпределен. Този планировчик работи като част от превключването на контекста. От него зависи до голяма степен ефективността на цялата система.
Междинното ниво на планиране се използва за управление на swapping. Планировчикът на това ниво обикновено се нарича swapper. Той определя кога един процес да бъде прехвърлен върху swapping областта на диска и кога да се върне обратно в паметта.

Не всички операционни системи реализират и трите нива на планиране. Например, в UNIX/LINUX първото ниво на планиране е много слабо изразено, за разлика от другите две. В OS/360 липсва планиране на междинно ниво.

Цели на планиране

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



Сподели линка с приятел:





Яндекс.Метрика
Oперационни системи- лекции 9 out of 10 based on 2 ratings. 2 user reviews.