Тема 1 – Основни принципи на управление на паметта (УП)

Тема 7– Други методи за управление на паметта

3. 
   С битова карта на паметта. На всеки бит от битовата карта съответства участък от паметта. Ако участък е празен, бита е 0. Лесно е известието за заемане на памет.
   
   
   

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

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

2. Очакване на ресурсиr. Процесите държат вече отделените им ресурси, като в същото време очакват да получат допълнителни ресурси.

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

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

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

Хавендер [58] доказва, че ако бъде нарушено поне едно от горните условия, възникването на мъртва хватка е невъзможно. Той предлага три стратегически принципа за избягване на мъртвата хватка, които нарушават 2-то, 3-то и 4-то условия.

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

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

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

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

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

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

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

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

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

Един страничен ефект при прилагане на описания метод за предпазване от мъртви хватки е, че е възможна ниска използваемост на устройствата и намалена пропускателна възможност на системата. Безизходна ситуация може да се избегне, дори ако необходимите условия за възникването и не са нарушени. Достатьчно е рационално да се разпределят ресурсите, придържайки се към определени правила. Решението относно текущата заявка за ресурси се взема динамично - дали удовлетворяването на заявката потенциално води до мъртва хватка. Затова е необходима допълнителна информация относно последователностите от заявки и освобождаване на ресурси, свързани с всеки процес. Често пъти, обаче, последователността от заявки не е известна предварително. Но, ако е известна общата заявка за всеки тип ресурси (т.е. вески процес трябва да декларира необходим максимален брой ресурси от всеки тип), разпределението може да се контролира. Съществуват различии алгоритми, които се различават по множеството и типа на необходимата информация [40].

При този подход [23, 85, 88] процес не се стартира, ако изискванията му могат да водят до мъртва хватка. Нека система има п процеса и т типове на ресурси. Дефинирани са следните вектори и матрици:

Ресурси = (R1, R2,.. ,RM) - брой на ресурсите от всеки тип в системата

Наличии = (V1,V2 ,...,VM ) брой на неразпределени ресурси от всеки тип

С11, С12, , С1M

С21, С22, , С1M заявка на всеки процес

Заявки = ................... за всеки тип на ресурси

CN1, CN2, , CNM
A11, A12, , A1M брой на ресурсите от

A21, A22, , A1M всеки тип, текущо

Разпределение = ................... разпределени на всеки

AN1, AN2, , ANM процес
Матрицата Заявки дава максималните нужди на всеки процес от всеки тип на ресурс - ред отговаря на процес. Тази информация трябва да бъде декларирана от процеса предварително, за да сработи избягването на мъртва хватка. Подобно, матрицата Разпределение дава текущото разпределение на ресурси от всеки тип за всеки процес. Следните зависимости трябва да бъдат спазени:

n

1. 
   R_i = V_i + A_ki, за всички i;(всички ресурси са разпределени или налични)
   

3. A_ki<= C_ki, за всички k, i; (никой процес не получава повече ресурси

Оттук може да се дефинира политиката за избягване на мъртва хватка - нов процес не се стартира, ако изискванията му за ресурси могат да доведат до мъртва хватка. Нов процес P_n+1се стартира, само ако:

Предполага се, че системата е с фиксиран брой процеси и фиксиран брой ресурси. Състояние на системата е текущото разпределение на ресурсите между процесите. Така състоянието се състои от двата вектора и двете матрици, дефинирани no-горе. Може да се докаже, че системата е в безопасно (сигурно) състояние, ако съществува поне един път на изпълнение на процесите (вж. фиг. 4.1), който позволява да се обходи опасного (несигурното) състояние. Следователно, достатьчно е да се провери дали отделянето на ресурс не води до опасно състояние. За всяка заявка, при предположение, че е удовлетворена, трябва да се определи съществува ли сред общите заявки от всички процеси някаква последователност от заявки, която да доведе до опасно състояние. Ако да, заявката се отклонява. В противен случай тя се изпълнява. Класически пример за тази стратегия е алгоритьмът на банкера, предложен от Дейкстра [45]. Ще бъде разгледан по-простия вариант, когато се разпределя само един ресурс.

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

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

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

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

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

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

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

Нека трима клиента Л, Б и В да могат да използват 10 единици капитал (т.е. капитала на банкера), но общата им нужда да е 20 единици.

На фиг. 4.За е показано безопасно състояние. Клиент А иска 4 единици, Б - 1 и В - 7. Проверяват се клиентите и се търси този, чието желание не превишава наличността (ако са няколко, този, който е най-близо до заявения заем). Клиент Б може да получи една единица, да довърши своята транзакция и да върне заема от три единици (фиг. 4.36). По-нататък се проверяват останалите клиента и се сравняват показанията им с наличността, равна на 4. Сега може да бъде удовлетворен А. Накрая ще изпълни транзакцията си и клиент В (фиг. 4.3в) и банкерът може да възвърне капитала си, т.е. критерий за безопасно състояние е съществуването на такава последователност от действия, която да позволява на всички клиенти да завършат работата си.