14. Метод близнецов и метод чисел Фибоначчи для управления памятью

Метод близнецов.

A

B

C

…

A

Пусто

C

…

Объём выделяемой памяти кратен 2^N.

Всегда процессу выделяется кусок памяти наименьшего

Числа Фибоначчи

последовательность целых чисел, в которой F_i+1 = F_i + F_i-1. В этом случае, если нам нужно F_i байт, а в наличии есть только блок размера F_i+1, мы легко можем получить два блока — один требуемого размера, а другой — F_i-1, который тоже не пропадет.

Например

1 1 2 3 5.

A=(+40,-20,+10);

+ - выделить память, - освободить.

15. Алгоритм Банкира

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

Банкир считает что для С достаточно ресурсов при условии что А не будет получать дополнительную память.

Процесс В можно записать поскольку дальний тег требованию с учётов 30 единиц будет хватать.

Банкир смотрит хватит ли памяти А чтобы завершится.

Процесс получает память банкира, если ему хватит её чтобы завершится.

16. Виды памяти и их назначение.

Важную роль играет стековая память (стек)

Основная задача стека: передача и сохранение параметров при вызове подпрограмм.

Регистр SP –

Регистр BB –

SP – Stack pointer(указатель на вершину стека)

BB – Base Pointer (указатель на основание стека)

Стек всегда растёт вверх.

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

Другое важное назначение стека: используется в режиме компиляции программы.

17. Использование стека для получения польской записи

B(*C+5)+A

*

B

(

*

BC

+

(

*

BC5

+

*

Скобки выгружаются из стека.

BC5+*

+

BC5+*A+

19. Управление процессами

Процесс – исполняемая программа которая занимает определённую область памяти и используется для выполнения любых задач используя системные ресурсы. В области памяти занимаемой процессом, других процессов нету.

Процессы имеют приоритеты.

Наивысший приоритет – системные процессы.

Бывают оконные процессы и безоконные(фоновые процессы).

Состояние процесса 1) активен, 2) ожидание (заблокирован, но работает), 3) приостановленные (не работает)

CreateProcess создать процесс, TerminateProcess удалить процесс.

19. Обнаружение и предупреждение тупиков

Тупик(Deadlock) – происходит когда 2 процесса пытаются обратиться к одному и тому же ресурсу. Один блокируется пока другой не завершит работу с ресурсом.

2 способа борьбы: Недопущение тупиков( недоиспользование системных ресурсов), Обнаружение и развязка(связано с потерей времени. Обнаружение не простая задача и не решается в реальных системах)

Предупреждение тупиков. Дейкстра предложил метод критических зон.

Инициализация, вход, выход, удаление критической секции.

19. Классификация систем параллельной обработки процессов

1. Одиночный поток команд, одиночный поток данных.

2. Матричные ЭВМ. (Матричные процессоры предназначены для обработки многомерных данных)

3. Конвейерная обработка

Каждая команда проходит фазы, стадии обработки:

1. Команда считывается из оперативной памяти через шину в процессорный блок

2. Распаковка команды (выделение команды (ADD) и выделение операндов(A,B)

3. Выполняется загрузка первого операнда. Из оперативной памяти. Считывается второй операнд.

4. Выполняется команда на АЛУ.

5. Запись результата в оперативную память.

4. Системы MKMD – представляют собой универсальные параллельные системы (супер ЭВМ)

Распараллеливание независимых заданий выполняется в 2-ух режимах: с прерыванием и без него.

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

Метод укладки. Метод параллельной обработки с квантованием времени.