Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


–аспределение ресурсов. ѕроблема тупиков




 

–ассматриваетс€ логическа€ задача, котора€ возникает при взаимодействии различных процессов, когда они должны делить ресурсы.

ѕод процессами понимаютс€ программы, описывающие некоторый вычислительный процесс, выполн€емый Ё¬ћ. ¬ыполнение такого вычислительного процесса требует времени, в течение которого в пам€ти Ё¬ћ хранитс€ информаци€.

ќ процессах известно следующее.

1. »х требовани€ к объему пам€ти не будут превышать определенного предела.

2.  аждый вычислительный процесс завершитс€ при условии, что требуемый процессу объем пам€ти будет предоставлен в его распор€жение. «авершение вычислительного процесса будет означать, что его требование к пам€ти уменьшилось до нул€.

»меюща€с€ пам€ть поделена на страницы фиксированного размера, эквивалентные с точки зрени€ программы.

‘актическое требование нужного процессу объема пам€ти €вл€етс€ функцией времени, то есть измен€етс€ по мере протекани€ процесса, но не превышает заранее заданную границу. ќтдельные процессы запрашивают и выдел€ют пам€ть единицами в одну страницу. ќднажды начатый процесс получает возможность рано или поздно завершитьс€, и исключаетс€ ситуаци€, когда процесс может быть уничтожен в ходе выполнени€, напрасно истратив свои ресурсы.

≈сли на вычислительной машине выполн€етс€ один процесс, или они последовательно следуют один за другим, единственным условием €вл€етс€ то, чтобы запрашиваемый процессом объЄм пам€ти не превышал доступный объЄм пам€ти вычислительной машины. ≈сли параллельно развиваютс€ несколько процессов, то могут возникнуть проблемы с выделением им ресурсов и надо предусмотреть выделение пам€ти таким образом, чтобы все начатые процессы смогли завершить свое выполнение.

—итуаци€, когда какой-либо из процессов может быть завершЄн лишь при условии уничтожени€ какого-либо другого процесса, называетс€ Ђсмертельными объ€ти€миї или тупиком.

–исунок - “упикова€ ситуаци€

 

—итуаци€, приведенна€ выше, €вл€етс€ тупиковой. »з этой ситуации невозможно выйти без уничтожени€ какого-либо из процессов.

–ешаема€ проблема состоит в том, как избежать попадани€ в тупик, не накладыва€ слишком больших ограничений.

 

јлгоритм банкира

 

Ѕанкир обладает конечным капиталом, например, талерами. ќн решает принимать клиентов, которые могут занимать у него талеры на следующих услови€х:

1.  лиент делает заем дл€ совершени€ сделки, котора€ будет завершена за определенный промежуток времени.

2.  лиент должен указать максимальное количество талеров дл€ этой сделки.

3. ѕока заем не превысит заранее установленную потребность, клиент может увеличивать или уменьшать свой заем.

4.  лиент, который просит увеличить свой текущий заем, без недовольства воспринимает ответ о том, что необходимо подождать с получением очередного талера, но через некоторое врем€ талер будет об€зательно выдан.

5. √аранти€ дл€ клиента, что такой момент наступит, основана на предусмотрительности банкира и на том факте, что остальные клиенты работают по таким же правилам.

ќсновными вопросами при решении такой задачи €вл€ютс€:

1. ѕри каких услови€х банкир может заключить контракт с новым клиентом?

2. ѕри каких услови€х банкир может выплатить (следующий) запрашиваемый талер клиенту, не опаса€сь попасть в тупик?

ќтвет на первый вопрос достаточно прост: банкир может прин€ть любого клиента на обслуживание, чь€ максимальна€ потребность не превышает капитал банкира. ќтвет на второй вопрос достаточно сложный. —начала нужно формализовать задачу.

потребность[i] ≤ капитал, дл€ всех i.

0 ≤ заем[i] ≤ потребность[i], дл€ всех i.

требование[i] = потребность[i] - заем[i], дл€ всех i.

наличные = капитал - ∑заем[i].

i

0 ≤ наличные ≤ капитал.

 

¬ такой ситуации алгоритм прин€ти€ решени€ о том, будет ли безопасной выдача следующего талера выгл€дит след образом:

Integer —в_ƒеньги;

Boolean Ѕезопасно;

boolean array «авершение_под_сомнением [1..N];

—в_ƒеньги:= наличные;

for i:= 1 step 1 until N do «авершение_под_сомнением[i]:= true;

L: for i:=1 step 1 until N do

Begin

if ((«авершение_под_сомнением [i]) and(“ребован[i] ≤ —в_ƒеньги))

Then

Begin

«авершение_под_сомнением [i]:= false;

—в_ƒеньги:= Cв_ƒеньги + «аем[i];

Goto L;

End;

End;

if (—в_ƒеньги = капитал) then Ѕезопасно:= true

else Ѕезопасно:= false;

 

ѕроверка возможности выплаты, то есть положение Ѕезопасно, означает, могут ли с гарантией быть завершены все сделки. јлгоритм начинаетс€ с проверки, имеет ли, по крайней мере, один клиент требование, не превышающее наличные деньги. ≈сли это так, то этот клиент может завершить свою сделку, и далее исследуютс€ оставшиес€ клиенты с учетом того, что первый клиент завершил свою сделку и возвратил свой заЄм полностью.

Ѕезопасность положени€ означает, что могут быть закончены все сделки, то есть банкир видит способ получени€ обратно всех своих денег.

¬ полном варианте алгоритма банкира эта ситуаци€ должна быть удовлетворена дл€ всех клиентов, прин€тых на обслуживание и если после завершени€ цикла, отмеченного меткой L окажетс€, что капитал банкира полностью восстановлен, то ситуаци€ считаетс€ безопасной, в противном случае она определ€етс€ как тупикова€ и, следовательно, удовлетвор€ть запрос клиента не представл€етс€ возможным.

≈сли более глубоко анализировать эту проблему, то можно показать, что решение о выделении следующего запрашиваемого талера клиенту будет прин€то тогда, когда хот€ бы дл€ одного клиента выполнитьс€ условие ((«авершение_под_сомнением[i]) and (“реб[i]<=—в_ƒеньги)) и это говорит о безопасности ситуации и проверку можно приостановить.

 





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-11-05; ћы поможем в написании ваших работ!; просмотров: 384 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ѕольшинство людей упускают по€вившуюс€ возможность, потому что она бывает одета в комбинезон и с виду напоминает работу © “омас Ёдисон
==> читать все изречени€...

1458 - | 1248 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.013 с.