учет участков свободной памяти с помощью связного списка свободных занятых
Управление памятью с помощью связанных списков. Алгоритмы предоставления памяти
Управление памятью с помощью битовых массивов
правление памятью с помощью связных списков
Другой способ отслеживания состояния памяти заключается в поддержке связных списков занятых или свободных фрагментов памяти, где фрагментом является либо процесс, либо участок между двумя процессами. Запись состоит из:
— адреса начала фрагмента;
— указателя на следующую запись.
Так же для модификации удобнее иметь список с двумя связями, одна из которых указывает на предыдущую запись. В случае сортировки списка по адресам имеется несколько алгоритмов предоставления памяти процессу:
Все алгоритмы можно ускорить, если поддерживать отдельные списки для свободных и занятых областей. В таком случае увеличится скорость поиска свободного участка, однако увеличится время модификации списков при освобождении памяти. Если, в случае двух списков, список свободных участков отсортировать по размеру, то быстрее всего будет работать алгоритм «самый подходящий участок», а алгоритм «следующий подходящий участок» не имеет смысла.
В менеджере памяти можно реализовать алгоритм «быстрый подходящий участок», если поддерживать отдельные списки для областей с наиболее часто запрашиваемыми размерами. Алгоритм позволяет быстро выделять память, однако приводит к сильной фрагментации и является проблемным при освобождении памяти.
Управление памятью с помощью связных списков
Primary tabs
Forums:
Управление памятью с помощью связных списков
Память, показанная на рис. 4.7, а,
представлена в виде связного списка сегментов на рис. 4.7, в.
(на рисунке ниже вы можете видеть, что каждый элемент списка действительно разделён на 4 секции)
В нашем примере список отсортирован по адресам. Такая сортировка имеет
следующее преимущество: когда процесс завершается или скачивается(«выгружается») на диск,
изменение списка представляет собой несложную операцию. Закончившийся про-
цесс обычно имеет двух соседей (кроме тех случаев, когда он находится на самом
верху или на дне памяти). Соседями могут быть процессы или свободные фрагмен-
ты, что приводит к четырем комбинациям, показанным на рис. 4.8=
Так как ячейка таблицы процессов для завершившегося процесса обычно будет непосредственно указывать на запись
в списке для этого процесса, возможно, удобнее иметь список с двумя связями, чем
с одной (последний показан на рис. 4.7, в). Такая структура упрощает поиск предыдущей записи и оценку возможности соединения.
Рис. 4.8- четыре комбинации соседей для завершения процесса Х
Если процессы и свободные участки хранятся в списке, отсортированном по
адресам, существует несколько алгоритмов для предоставления памяти процессу,
создаваемому заново (или для существующих процессов, скачиваемых с диска).
Допустим, менеджер памяти знает, сколько памяти нужно предоставить. Простей-
ший алгоритм представляет собой выбор первого подходящего участка. Менед-
жер памяти просматривает список областей до тех пор, пока не находит достаточ-
но большой свободный участок. Затем этот участок делится на две (не обязательно равных) части:
Так происходит всегда,
кроме статистически нереального случая точного соответствия свободного участ-
ка и процесса. Это быстрый алгоритм, потому что поиск уменьшен настолько, на-
сколько возможно.
Алгоритм «следующий подходящий участок» действует с минимальными от-
личиями от правила «первый подходящий». Он работает так же, как и первый ал-
горитм, но всякий раз, когда находит соответствующий свободный фрагмент, он
запоминает его адрес. И когда алгоритм в следующий раз вызывается для поиска,
он стартует с того самого места, где остановился в прошлый раз вместо того, чтобы
каждый раз начинать поиск с начала списка, как это делает алгоритм «первый под-
ходящий».
Моделирование работы алгоритма, произведенное Бэйсом, показало,
что производительность схемы «следующий подходящий» немного хуже, чем
«первый подходящий».
Другой хорошо известный алгоритм называется «самый подходящий учас-
ток». Он выполняет поиск по всему списку и выбирает наименьший по размеру
подходящий свободный фрагмент. Вместо того чтобы делить большую незанятую
область, которая может понадобиться позже, этот алгоритм пытается найти учас-
ток, близко подходящий к действительно необходимым размерам.
Чтобы привести пример работы алгоритмов «первый подходящий» и «самый
подходящий», снова обратимся к рис. 4.7. Если необходим блок размером 2, пра-
вило «первый подходящий» предоставит область по адресу 5, а схема «самый под-
ходящий» разместит процесс в свободном фрагменте по адресу 18.
Алгоритм «самый подходящий» медленнее «первого подходящего», потому что
каждый раз он должен производить поиск во всем списке. Но, что немного удиви-
тельно, он выдает еще более плохие результаты, чем «первый подходящий» или
«следующий подходящий», поскольку стремится заполнить память очень малень-
кими, бесполезными свободными областями, то есть фрагментирует память. Алго-
ритм «первый подходящий» в среднем создает большие свободные участки.
Пытаясь решить проблему разделения памяти на практически точно совпада-
ющие с процессом области и маленькие свободные фрагменты, можно задуматься
об алгоритме «самый неподходящий участок». Он всегда выбирает самый боль-
шой свободный участок, от которого после разделения остается область достаточ-
ного размера и ее можно использовать в дальнейшем. Однако моделирование по-
казало, что это также не очень хорошая идея.
Все четыре алгоритма можно ускорить, если поддерживать отдельные списки
для процессов и свободных областей. Тогда поиск будет производиться только
среди незанятых фрагментов. Неизбежная цена, которую нужно заплатить за уве-
личение скорости при размещении процесса в памяти, заключается в дополнитель-
ной сложности и замедлении при освобождении областей памяти, так как ставший
свободным фрагмент необходимо удалить из списка процессов и вставить в спи-
сок незанятых участков.
Если для процессов и свободных фрагментов поддерживаются отдельные спис-
ки, то последний можно отсортировать по размеру, тогда алгоритм «самый подхо-
дящий» будет работать быстрее. Когда он выполняет поиск в списке свободных
фрагментов от самого маленького к самому большому, то, как только находит
подходящую незанятую область, алгоритм уже знает, что она — наименьшая из тех,
в которых может поместиться задание, то есть наилучшая. В отличие от схемы
с одним списком, дальнейший поиск не требуется. Таким образом, если список
свободных фрагментов отсортирован по размеру, схемы «первый подходящий»
и «самый подходящий» одинаково быстры, а алгоритм «следующий подходящий»
не имеет смысла.
При поддержке отдельных списков для процессов и свободных фрагментов воз-
можна небольшая оптимизация. Вместо создания отдельного набора структур дан-
ных для списка свободных участков, как это сделано на рис. 4.7, е, можно исполь-
зовать сами свободные области. Первое слово каждого незанятого фрагмента
может содержать размер фрагмента, а второе слово может указывать на следую-
щую запись. Узлы списка на рис. 4.7, в, для которых требовались три слова и один
бит (Р/Н), больше не нужны.
Еще один алгоритм распределения называется «быстрый подходящий», он
поддерживает отдельные списки для некоторых из наиболее часто запрашиваемых
размеров. Например, могла бы существовать таблица с п записями, в которой пер-
вая запись указывает на начало списка свободных фрагментов размером 4 Кбайт,
вторая запись является указателем на список незанятых областей размером
8 Кбайт, третья — 12 Кбайт и т. д. Свободный фрагмент размером, скажем, 21 байт,
мог бы располагаться или в списке областей 20 Кбайт или в специальном списке
участков дополнительных размеров.
При использовании правила «быстрый подходящий» поиск фрагмента требуемого размера происходит чрезвычайно быстро.
Но этот алгоритм имеет тот же самый недостаток, что и все схемы, которые сорти-
руют свободные области по размеру, а именно: если процесс завершается или вы-
гружается на диск, поиск его соседей с целью узнать, возможно ли их соединение,
является дорогой операцией. А если не производить слияния областей, память
очень скоро окажется разбитой на огромное число маленьких свободных фрагмен-
тов, в которые не поместится ни один процесс.
В. выделять участки памяти произвольных размеров
А, Взаимодействие связанных между собой компьютеров
В. Программных каналов между разными компьютерами
С.Обмена сигналами между выполняющимися на разных компьютерах программами
D.Прямого доступа к оперативной памяти другого компьютера
2. Одна операционная система может поддерживать несколько…
В. Микропрограммных систем
С. Операционных систем
D. Операционных сред
3. Термин «маскирование» означает запрет отдельных …
А. Сигналов прерывания
В. Команд процессора
С. Процессов пользователя
4. Для реализации синхронизации на уровне языка программирования используются высокоуровневые примитивы, названные …
С. Семафорами
5. Относительный путь к файлу состоит из списка каталогов, которые нужно…
А.Пройти от корневого каталога, чтобы добраться до файла
В. Добавить в переменную PATH операционной среды
С. Пройти от рабочего каталога, чтобы добраться до файла
D. Открыть в корневом процессе, чтобы добраться до файла
6. Свопингом сегментов называется перемещение …
А.Сегментов между оперативной и внешней памятью
В.Блоком данных между процессом и ядром операционной системы
С. Сегментов данных между стеком и оперативной памятью
D. Блоков файла между каталогами файловой системы
7. Идентификатор пользователя представляет собой уникальное ______________ значение
С. Целое
8.Мультитерминальный режим работы предполагает совмещение …
А. Аналогового режима работы и режима микропрограммирования
В.Многопроцессорного режима работы и режима ввода-вывода
С. Диалогового режима работы и режима мультипрограммирования
D. Привилегированного режима работы и режима пользователя
9. Последовательная трансляция двух исходных программ является …
А.Одним последовательным процессом
В.Двумя одинаковыми процессами
С. Одной последовательной задачей
D. Двумя разными процессами
10. Идентификатор процесса является частью _______________ процесса (допустио несколько ответов)
С. Описателя
D. Дескриптора
11. В ОС Unix каждый новый процесс может быть образован (порожден) только …
А.Одним из существующих процессов
В.Несколькими родительскими процессами
С.Двумя из существующих процессов
D. Четным количеством родительских процессов
12. Основное различие между долгосрочным и краткосрочным планированием (диспетчеризацией) заключается в…
А. Длительности выполнения
В. Очередности выполнения
D.Частоте выполнения
13. Приоритет, меняющийся во время исполнения процесса, называется ____________ приоритетом
А.Динамическим
14. При совместном использовании процессами аппаратных и информационных ресурсов вычислительной системы возникает потребность в …
С.Синхронизации
15. В операционной системе UNIX сигналы можно рассматривать как простейшую форму взаимодействия между…
В.Процессами
16. Область эффективного применения событийного программирования начинается там, где возникают … (укажите не менее двух вариантов)
А. Трудности декомпозиции решаемой задачи, при которой генерация и обработка рассматриваются как объединенные процессы
В.Необходимость использования графа переходов между состояниями
С.Возможности декомпозиции решаемой задачи, при которой генерация и обработка рассматриваются как объединенные процессы
D. Неудобство использования графа переходов между состояниями
17. Два параллельных процесса могут быть …
В. Независимыми
18.Главной целью мультипрограммирования в системах пакетной обработки является …
А. Обеспечение реактивности системы
В. Минимизация времени выполнения одной задачи
С. Обеспечение удобства работы пользователя
D. Минимизация простоев всех устройств компьютера
19. Учет участков свободной памяти с помощью связного списка свободных/занятых блоков позволяет
А. находить в памяти наиболее долго занятые участки
В. выделять участки памяти произвольных размеров
С. освобождать память, занятую неактивными процессами
D. перемещать процессы в памяти
20. Использование виртуальной памяти в однопрограммном режиме приводит к … процесса, если размер программы существенно больше объема доступной оперативной памяти
А. аварийному завершению
С.замедлению выполнения
D.перезапуску
21. Виртуальная память позволяет … (возможно несколько вариантов ответа)
А. отказаться от предоставления прикладным процессам оперативной памяти
В.загружать множество небольших программ, суммарный объем которых больше объема физической памяти
С.загружать программы, размер которых превышает объем доступной физической памяти
D. загружать программы, скомпилированные для другого процессора
22. Сегментная организация памяти … отдельно скомпилированных процедур.
В.упрощает компоновку
D. усложняет компоновку
23. При страничной организации памяти таблица страниц может размещаться в …
А. только в оперативной памяти
В. в оперативной памяти и на диске
С. только в процессоре
D.в специальной быстрой памяти процессора и в оперативной памяти
24. Страничная организация предназначена для …
А. облегчения совместного использования процедур, библиотек и массивов данных
В. повышения уровня защиты программ и данных
С.получения большого адресного пространства без приобретения дополнительной физической памяти
D. логического разделения программ и данных
25. При страничном сбое и отсутствии свободных блоков физической памяти операционная система должна …
С. выбрать страницу, которая не изменялась, и сохранить удаляемую страницу на диске
D. выбрать страницу-кандидат на удаление из памяти и сохранить копию удаляемой страницы в таблице страниц
26. Полная реализация алгоритма LRU (Least Recently Used) …
А. теоретически невозможна
В. возможна при использовании стековой организации таблицы страниц
С. возможна при условии построения таблицы страниц в виде бинарных деревьев
D.практически невозможна
27. Запросы на ввод-вывод от супервизора задач или от программных модулей самой операционной системы получает _____________ ввода-вывода
С.супервизор
28. Мыши (в качестве устройства-указателя) относятся к _____________ устройствам ввода-вывода.
В.символьным
29. Любые операции по управлению вводом-выводом объявляются …
А.привилегированными
30. Супервизор ввода-вывода инициирует операции ввода-вывода и в случае управления вводом-выводом с использованием прерываний предоставляет процессор …
А. супервизору прерываний
В.диспетчеру задач
С. задаче пользователя
D. супервизору программ
31. В режиме обмена с опросом готовности устройства ввода-вывода используется _____________ центрального процессора.
А. рационально время
В. нерационально память
С.нерационально время
D. рационально память
32. Понятия «виртуального устройства» по отношению к понятию «спулинга» …
А.соотносится как часть и целое
В.является более широким
С. является более узким
33. Каждый элемент таблицы оборудования условно называется …
А.UCB
34. Для увеличения скорости выполнения приложений при необходимости предлагается использовать _____________ ввод-вывод.
А.асинхронный
35. Программа, расположенная в главной загрузочной записи, называется _____________ загрузчиком.
В.внесистемным
36. Простейшим вариантом ускорения дисковых операций чтения данных можно считать использование двойной …
В.буферизации
37.Операционная система реального времени должна обеспечивать …
Взаимодействия связанных между собой компьютеров
Взаимодействия связанных между собой компьютеров
программных каналов между разными компьютерами
2. Одна операционная система может поддерживать несколько …
Операционных сред
3. Термин «маскирование» означает запрет отдельных …
Сигналов прерывания
4. Для реализации синхронизации на уровне языка программирования используются высокоуровневые примитивы, названные …
Мониторами
5. Относительный путь к файлу состоит из списка каталогов, которые нужно …
добавить в переменную PATH операционной среды
пройти от корневого каталога, чтобы добраться до файла
открыть в корневом процессе, чтобы добраться до файла
Пройти от рабочего каталога, чтобы добраться до файла
6. Свопингом сегментов называется перемещение …
сегментов данных между стеком и оперативной памятью
блоков данных между процессом и ядром операционной системы
блоков файла между каталогами файловой системы
Сегментов между оперативной и внешней памятью
7. Идентификатор пользователя представляет собой уникальное _______ значение
Целое
8. Мультитерминальный режим работы предполагает совмещение …
привилегированного режима работы и режима пользователя
Диалогового режима работы и режима мультипрограммирования
аналогового режима работы и режима микропрограммирования
многопроцессорного режима работы и режима ввода-вывода
9. Последовательная трансляция двух исходных программ является
двумя одинаковыми процессами
Двумя разными процессами
одной последовательной задачей
одним последовательным процессом
10. Идентификатор процесса является частью _____________ процесса.
Дескриптора
Описателя
11. В OS UNIX каждый новый процесс может быть образован (порожден) только …
Одним из существующих процессов
четным количеством родительских процессов
несколькими родительскими процессами
двумя из существующих процессов
12. Основное различие между долгосрочным и краткосрочным планированием (диспетчеризацией) заключается в …
Частоте выполнения
13. Приоритет, меняющейся во время исполнения процесса, называется _____________ приоритетом.
Динамическим
14. При совместном использовании процессами аппаратных и информационных ресурсов вычислительной системы возникает потребность в …
Синхронизации
15. В операционной системе UNIX сигналы можно рассматривать как простейшую форму взаимодействия между …
Процессами
16. Область эффективного применения событийного программирования начинается там, где возникают …
возможности декомпозиции решаемой задачи, при которой генерация и обработка рассматриваются как объединенные процессы
Неудобство использования графа переходов между состояниями
Трудности декомпозиции решаемой задачи, при которой генерация и обработка рассматриваются как объединенные процессы
необходимость использования графа перехода между состояниями
17. Два параллельных процесса могут быть …
Независимыми
18. Главной целью мультипрограммирования в системах пакетной обработки является …
обеспечение реактивности системы
минимизация времени выполнения одной задачи
Минимизация простоев всех устройств компьютера
обеспечение удобства работы пользователей
19. Учет участков свободной памяти с помощью связного списка свободных/занятых блоков позволяет …
перемещать процессы в памяти
освобождать память, занятую неактивными процессами
Выделять участки памяти произвольных размеров
находить в памяти наиболее долго занятые участки
20. Использование виртуальной памяти в однопрограммном режиме приводит к … процесса, если размер программы существенно больше объема доступной оперативной памяти
Замедлению выполнения
21. Виртуальная память позволяет …
Упрощает компоновку
23. При страничной организации памяти таблица страниц может размещаться в …
в оперативной памяти и на диске
только в оперативной памяти
Практически невозможна
возможна при условии построения таблицы страниц в виде бинарных деревьев
возможна при использовании стековой организации таблицы страниц
27. Запросы на ввод-вывод от супервизора задач или от программных модулей самой операционной системы получает _____________ ввода-вывода
Супервизор
28. Мыши (в качестве устройства-указателя) относятся к _____________ устройствам ввода-вывода.
Символьным
29. Любые операции по управлению вводом-выводом объявляются …
Привилегированными
30. Супервизор ввода-вывода инициирует операции ввода-вывода и в случае управления вводом-выводом с использованием прерываний предоставляет процессор …
Диспетчеру задач
31. В режиме обмена с опросом готовности устройства ввода-вывода используется _____________ центрального процессора.
Нерационально время
32. Понятия «виртуального устройства» по отношению к понятию «спулинга» …
Является более широким
соотносится как часть и целое
является более узким
33. Каждый элемент таблицы оборудования условно называется …
34. Для увеличения скорости выполнения приложений при необходимости предлагается использовать _____________ ввод-вывод.
Асинхронный
35. Программа, расположенная в главной загрузочной записи, называется _____________ загрузчиком.
Внесистемным
36. Простейшим вариантом ускорения дисковых операций чтения данных можно считать использование двойной …
Буферизации
37. Операционная система реального времени должна обеспечивать …
Наследование приоритетов
38. К невыгружаемым относятся такие ресурсы, которые не могут быть …
загружены в память
отобраны у процессора
выгружены из памяти
Отобраны у процесса
39. Интерфейс прикладного программирования предназначен для использования прикладными программами …
регистров общего назначения процессора
интерпретатора команд пользователя
адресного пространства процесса
Однопрограммный
Мультипрограммный
41. Угроза зомби реализуется с помощью … и заставляет компьютер выполнять приказания других лиц.
вызова утилит операционной системы
Вредоносных программ
42. Недостаток систем шифрования с секретным ключом состоит в том, что …
Программы
устройства отображения информации
Руководителей подразделений
45. Защита зашифрованных паролей в UNIX взламывается путем …
вычисления пароля путем свертки идентификатора пользователя
взаимодействия связанных между собой компьютеров
программных каналов между разными компьютерами
2. Одна операционная система может поддерживать несколько …
Операционных сред
3. Термин «маскирование» означает запрет отдельных …
Сигналов прерывания
4. Для реализации синхронизации на уровне языка программирования используются высокоуровневые примитивы, названные …
Мониторами
5. Относительный путь к файлу состоит из списка каталогов, которые нужно …
добавить в переменную PATH операционной среды
пройти от корневого каталога, чтобы добраться до файла
открыть в корневом процессе, чтобы добраться до файла
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим.
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций.