Алгоритм обнаружения и устранения дедлоков (deadlocks).

1. обнаружение дедлока (с помощью алгоритма Дейкстры или Габермана);

• В отличии от алгоритмов обхода эти алгоритмы включаются в некоторые единицы времени, а не при каждом принятии решения.

2. устранение дедлока;

2.1) перезапуск всей системы;

+ просто;

• теряется много данных.

2.2) перезапуск только тупиковых процессов;

+ данных теряется меньше;

• требуются дополнительные ресурсы для реализации перезапуска тупиковых процессов;

2.3) перезапуск по одному процессу (последовательно);

+ данных теряется еще меньше;

• дополнительных ресурсов требуется еще больше.

2.4) пережидание некоторого времени для возможного автоматического устранения тупика, а если не помогает – воспользование п.2.1)-2.3).

Управление памятью. Общие вопросы.

В IBM PC-совместимых машинах существует 3 типа ОЗУ:

СОЗУ

СОЗУ – сверхоперативное запоминающее устройство

ОП – оперативная память

ДП – память долговременного хранения

ОП

объем

скорость

ДП

- среднее время на одну операцию

i80386 – процессоры стали иметь кэш 1-го уровня, который и решил проблему с адресацией

Начиная с Pentium’ов, появился кэш 2-го уровня, где производятся вычисления.

Виртуальная (адресуемая) и физическая память.

ФП – обычная линейная память, измеряемая в байтах.

ФП характеризуется:

1. объемом;

2. возможностью адресации.

16-разрядный процессор   64 Кбайт

32-разрадный процессор   4 Гбайта

ВП – память адресуемая, “вращается” в программе.

Возможны 2 случая:

а)

б) - для 32-разрядных процессоров

Виртуальная память должна “сажаться” на физическую. Здесь возникают 2 аспекта:

а) на каком этапе? (см. далее)

б) как быстро? (в зависимости от организации ВП, см. далее)

пример (хотим считать порт LPT1):

mov ax, 40h 40h: 08h - LPT1

mov es, ax ; 40h в ES 09h – LPT2

mov bl, es:[08h]

mov bh, es:[09h] ; BX – номер порта LPT1

Система управления памятью (СУП).

СУП

Управление ФП Управление ВП

1. однозадачн. 1) плоская (линейная)

• простые; 2) сегментная

• с оверлейями (ovelays). 3) страничная организация памяти (самая быстрая)

2. многозадачн. 4) сегментно-страничная (начиная с i80386)

• с фиксированными разделами памяти (перемещаемые/неперемещаемые модули)

• с переменными разделами памяти

• динамическое распределение памяти

1. однозадачный режим;

а) простой

о

ОП

граничение:

Системные программы

Транзитная обл. памяти

ОС

б) с оверлейями

; программа разбивается на сегменты

сегмент перекр. 1

корневой сегмент сегмент перекр. 2

сегмент перекр. 3

- условие должно выполняться (КС – корневой сегмент, СП – сегмент перекр.)

2. многозадачный режим;

Т

очереди

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

Системные программы

1

а) разделы постоянной длины;

б) каждая задача решается своим разделом

2

3

ОС

Недостатки:

- неоптимальный расход ресурсов;

а) объемы разделены, как правило, неадекватно объемам соответствующих задач;

б) некоторые разделы могут простаивать, а некоторые могут быть переполнены  большая вероятность незадействования разделов.

Алгоритмы управления памятью.

Эти алгоритмы связаны с преобразованием ВП в ФП.

- число страниц

Вопросы:

а) когда загружать страницы задачи в память?

б) куда загружать?

в) какую страницу выгружать?

Рассмотрим 1-ый аспект:

1. по факту (в то время, когда необходима эта загрузка);

+ выигрыш в памяти;

- проигрыш в производительности.

2. впрок (при любом обращении к задаче загружать как можно больше страниц этой задачи).

+ выигрыш в производительности;

• проигрыш в памяти.

Рассмотрим 2-ой аспект:

1. в первое попавшееся (свободное место);

2. в наиболее подходящее место;

3. в наименее подходящее место.

Системные программы

1

2

(страницы задачи)

3

ОС

Рассмотрим 3-ий аспект:

1. первую попавшуюся страницу;

+ простая тактика, не требующая дополнительных ресурсов;

- проигрыш в быстродействии.

2. страницу, которой долго не было в обращении;

+ выигрыш в быстродействии (по сравнению с 1), по крайней мере);

• дополнительные ресурсы для обеспечения механизма;

• вероятность неоптимальной выборки выгружаемой страницы.

3. страницу, которая дольше всех находится в памяти;

 3)  2)

4. страницу с минимальным полем обращения;

 4)  2)  3)

5. страницу с битовым полем (значением 0 в нем, а если 1 – то не выталкиваем ее);

Выгрузка необходима в случае недостатка задачи в количестве необходимых ей страниц.

Число обращений

По количеству ресурсов зависимости расположены в порядке возрастания, т.е. 3, 1, 2

- доля страниц

Р

Для того, чтобы добавить к Wзагр еще 0.1, необходимо круто увеличить число рабочих страниц

абочее множество – это число страниц, которое необходимо задаче для ее решения в дискретный момент времени.

Число страниц

- вероятность загрузки (кривая на графике)

Связывание информации.

Информация рассматривается как объект.

Имя Цепь доступа Защита

(имя, переменнаяВАФА)

К сложным объектам цепь доступа лучше всего организовывать через дескриптор (указатель).

Преимущества:

а) дескриптор имеет фиксированный размер памяти;

б) дескриптор является точкой перевала и через него можно осуществлять контроль доступа;

в) дескриптор имеет косвенный доступ к объекту и поэтому позволяет изменять цепь доступа динамически (объект может быть один, а дескриптор у каждого пользователя может быть свой  дескрипторов может быть несколько);

г) можно реализовывать приоритеты для различных пользователей через дескрипторы.

Защита:

1. ликвидация цепи доступа;

2. проверка полномочий (через дескриптор в частности);

3. динамическая установка связей к объекту.

Связывание информации:

а) установление цепи доступа на этапе написания программы (программа пишется на машинном языке);

+ оптимальная программа;

• сложное написание;

• сложная отладка;

• немобильность программы.

б) на этапе компиляции (интерпретатором);

+ программа запускается сразу;

+ занимает меньший объем памяти;

+ более гибкая;

• интерпретации происходят перед каждым запуском;

• немобильность;

в) на этапе загрузки (run time);

ВП  ФП (ВП связывается с ФП)

+ мобильность.

г) динамическое связывание (по мере надобности);

+ гибкость;

• проигрыш в быстродействии (из-за связывания переменной с ее адресом).

Введение в Си