Алгоритмы распределения памяти - раздел Образование, Основы теории операционных систем
Методы Распределения Памяти Должны Отвечать На Следующие Вопр...
Методы распределения памяти должны отвечать на следующие вопросы:
- Каждому процессу следует выделять непрерывную область физической памяти или можно «кусками»;
- Должны ли части программы находиться в одном месте памяти в течение всего времени выполнения процесса или их можно сдвигать;
- Что делать если программа не помещаются в свободную память;
- Если свободной памяти нет, какую программу или часть вытеснить на диск;
Классификация алгоритмов распределения памяти
|
| Алгоритмы распределения памяти
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Без использования внешней памяти
|
| С использованием внешней памяти
|
|
|
|
|
|
|
|
| Фиксированными разделами 1
|
|
| Страничное распределение 4
|
|
|
|
|
|
|
|
| Динамическими разделами 2
|
|
| Сегментное распределение 5
|
|
|
|
|
|
|
|
| Перемещаемыми разделами
|
|
| Сегментно- страничное распределение 6
|
1. Распределение памяти фиксированными разделаминаиболее простой способ управления памятью. Состоит в том, что вся ОП разбивается на несколько частей фиксированной величины (может быть не равные), разбиение может выполняться при установки ОС или старта системы оператором вручную. Очередной процесс, поступивший на выполнение, помещается дибо в общую очередь, либо в очередь к некоторому разделу.
Очереди к разделам
Очередь задач
Раздел 1 Раздел 1
Раздел 2 Раздел2
Недостатки – программа всегда будет занимать весь раздел, если процессу необходимо памяти больше, чем размер раздела, то его невозможно выполнить.
Функции ОС:
- Сравнить размер памяти, требуемый процессу, со свободными разделами и выбрать подходящий;
- Осуществить загрузку в один из разделов и настроить адреса
В настоящее время используется в специализированных ОС из-за своей простоты
2. Распределение памяти динамическими разделами. ОП заранее не делиться на разделы, сначала вся память, отводимая для приложений свободна. На этапе создания процесса ему отводится необходимый объем памяти, если достаточный объем памяти отсутствует, то процесс не создается. После завершения процесса память освобождается. Таким образом в произвольный момент времени, вся ОП представляет собой случайную последовательность свободных и занятых участков произвольного размера. Данный способ предполагает, что код программы не перемещается в памяти.
Функции ОС:
- Ведение таблиц свободных и занятых областей, с указанием начального адреса и размера;
- При создании нового процесса, просмотр таблиц свободных и занятых областей, и выбор подходящего;
- Загрузка в выбранный раздел и внесение изменений в таблицы учета;
- После завершения процесса внесения изменения в таблицы учета.
Основной недостаток – фрагментация памяти, то есть наличие большого числа несмежных участков свободной памяти маленького размера. Так, что ни один вновь поступающий процесс не может быть размещен в памяти, не смотря на то, что общий суммарный объем достаточный или превосходит требуемый.
3. Для борьбы с фрагментацией был разработан алгоритм распределения памяти перемещаемыми разделами. ОС проводит сжатие данных, то есть сдвигает их вверх, тем самым освобождая память. Сжатие может проводиться либо после завершения процесса, либо когда процессу не хватает места. Из-за перемещения данных не возможно выполнить настройку адресов во время загрузки процесса, требуется динамическое преобразование адресов. Процедура сжатия может потребовать значительного времени, хотя память расходуется более экономно.
В современных ОС используется механизм виртуальной памяти, который состоит в том, что при нехватке места в ОП часть данных выгружается на диск. Ключевой проблемой при использовании виртуальной памяти является преобразование виртуальных адресов в физические, так как местоположение данных в памяти постоянно изменяется. Это зависит от того, какой метод обмена данными принят в данной системе управления памятью. В настоящее время принято три способа обмена данными между ОП и диском.
Страничная виртуальная памятьорганизует перемещение данных между памятью и диском страницами – частями виртуального адресного пространства процесса фиксированного и сравнительно небольшого размера.
Сегментная виртуальная память – организует перемещение данных сегментами, частями виртуального адресного пространства процесса произвольного размера, полученными с учетом смыслового значения данных.
Сегментно-страничная виртуальная память использует двухуровневое деление: виртуальное адресное пространство делятся на сегменты, а затем сегменты делятся на страницы. Единицей перемещения является страница.
Для временного хранения сегментов и страниц на диске отводиться специальный файл.
4. Страничное распределение. Все виртуальное адресное пространство процесса делится на виртуальные страницы фиксированного и одинакового размера, последняя страница дополняется до целой страницы. ОП делится на части такого же размера – физические страницы. При создании процесса ОС загружает в память несколько виртуальных страниц процесса. Копия всего адресного пространства процесса находиться на диске. Смежные страницы процесса не обязательно находятся в смежных физических страницах. Для каждого процесса создается таблица страниц, которая содержит записи обо всех страницах процесса и включает:
- номер физической страницы, в которую загружена данная виртуальная страница;
- признак присутствия =1, если страница находится в ОП;
- признак модификации = 1, если данные были изменены, то была проведена операция записи для данной страницы;
- признак обращения к странице (бит доступа)= количеству обращений к странице.
Запись таблицы страниц называется дескриптор страницы. Признаки присутствия, модификации и обращения устанавливаются аппаратно, схемами процессора при выполнении операций с памятью.
|
| Виртуальное адресное пространство процесса 1
|
| Таблица страниц процесса 1
|
|
Физическая память
|
|
| Виртуальн страницы
|
|
|
| управ-
|
|
|
|
|
|
| ВП
| ляющая
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ВП
| инфор-
|
| Пр1. стр 3
|
|
|
|
| A
| мация
|
|
|
|
|
|
|
|
|
|
| Пр1. стр 5
|
|
|
|
|
|
|
|
|
|
|
| Виртуальное адресное пространство процесса 2
|
| Таблица страниц процесса 2
|
|
|
|
| Пр 2. стр 8
|
|
|
|
|
| Пр1. стр А
| A
|
| Виртуальные страницы
|
|
|
| управ-
|
|
| B
|
|
|
| ВП
| ляющая
|
|
| C
|
|
|
| D
|
|
| Пр 2. стр D
| D
|
|
|
| ВП
| инфор-
|
| Пр 2. стр E
| E
|
|
|
| ВП
| мация
|
|
| F
|
|
|
| Е
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Обмен
|
|
|
|
|
|
|
|
| с диском
|
|
|
| | | | | | | | | |
Алгоритм работы.
- При каждом обращении к памяти выполняется поиск номера виртуальной страницы, содержащей требуемый адрес;
- По этому номеру определяется соответствующий элемент таблицы страниц и считывается служебная информация для этой страницы;
- Анализируется признак присутствия, если данная виртуальная страница находиться в ОП, то определяется ее физический адрес и выполняется операция с данными;
- Если страница выгружена на диск, то происходит страничное прерывание – данный процесс переводиться в состояние ожидания;
- Другой процесс из очереди процессов начинает работать (активизируется);
- Параллельно ОС пытается загрузит требуемую страницу в ОП, если место есть, то загрузка выполняется;
- Если свободного места в ОП нет, то одна из страниц перемещается на диск, а на ее место загружается требуемая;
- При перемещение страницы на диск анализируется признак модификации, если он = 0, то есть страница не изменялась, то записи на диск не проводится, если = 1, то проводиться запись данных на диск;
Возникает вопрос: какую страницу вытеснять на жесткий диск.
Предсказать точно ход вычислительного процесса невозможно, поэтому невозможно точно определить страницу, которую следует выгрузить на диск. Применяются разные методы:
- Случайный выбор, на диск выгружается первая попавшая страница;
- Анализ числа обращений к странице по признаку обращения, чем меньше обращений, тем страница менее значима;
- Анализ времени обращения к странице, если к странице не было обращения долгое время, то и не будет в ближайшее время;
Интенсивность обмена может быть снижена за счет упреждающей загрузке, когда в память загружается не одна, а несколько прилегающих страниц. Используется эмпирическое правило: если есть обращение к одной странице, то будет и к соседним. Размер страницы должен быть оптимальным, если страница большая – то занимает много места в ОП, если маленькая – то происходит частый обмен. Процессор Intel – 4 кб
5. Сегментное распределение. Виртуальное адресное пространство процесса делиться на части – сегменты, размер которых определяется с учетом смыслового значения содержащийся в них информации. Отдельный сегмент может быть создан для подпрограмм, массива данных и т.д. Во время создания процесса в ОП ОС создает таблицу сегментов процесса, по аналогии с таблицей страниц.
Если виртуальные адресные пространства нескольких процессов включают один и тот же сегмент, то в таблицах сегментов этих процессов, делаются ссылки на один и тот же участок ОП, в который данный сегмент загружается в единственном экземпляре. Алгоритм работы тот же самый, что и при страничном распределении памяти.
Главный недостаток – дефрагментация ОП, которая возникает из-за разных размеров сегментов. Достоинство – возможность задать разные права доступа для разных сегментов.
6. Сегментно-страничное распределение сочетает достоинства обоих методов. Виртуальное адресное пространство делится на сегменты с учетом смысла данных, а сегменты и физическая память делится на страницы равного размера. Это позволяет сократить фрагментацию памяти и определять разные права доступа. Для каждого процесса создается своя таблица сегментов, а для каждого сегмента – своя таблица страниц. Обмен между ОП и диском проводится – страницами.
Все темы данного раздела:
Требования, предъявляемые к современным ОС
Основное требование - выполнение основных функций управления ресурсами и обеспечения удобного интерфейса пользователя и приложений.
Надежность и отказоустойчивость
Организация диалога пользователя
Средства взаимодействия пользователя с компьютером, а точнее с операционной системой, представляют собой интерфейс пользователя. Операционная система должна предоставить пользовател
Текстовый режим диалога пользователя
В текстовом режиме пользователь имеет в своем распоряжении систему команд ОС и вводит команды с клавиатуры в командной строке. Команда имеет строго определенный формат, изменение которого приводит
Архитектура операционной системы
Любая сложная система, к которым относиться и ОС компьютера, должна иметь понятную и рациональную структуру, которая может быть получена делением всей системы на отдельные модули. Каждый модуль име
Многослойная структура ОС
Вычислительную систему, работающую под управлением ОС на основе ядра, можно представить как систему , состоящую из трех слоев: нижний слой – аппаратура ПК, средний – ядро ос и верхний слой – вспомо
Режимы работы ОС
Для надежного управления ходом работы компьютера ОС должна иметь определенные привилегии по отношению к другим задачам (приложениям). Иначе некорректно работающее приложение может вмешаться в работ
Переносимость ОС
Если код ОС может быть сравнительно легко перенесен с процессора одного типа на процессор другого типа и с аппаратной платформы одного типа на аппаратную платформу другого типа, то
Файловая система ПК
Одной из главных задач ОС является обеспечение обмена данными между приложениями и периферийными устройствами компьютера. В современных ОС функции обмена данными с периферийными уст
Физическая организация FAT
Вся информация о размещении файлов на диске находится в Таблице Размещения Файлов (File Allocation Table, FAT). Разработана в 1981 году и используе
Работа с файлами и каталогами средствами командной строки Windows
ОС MS DOS была создана в 1981 году фирмой Microsoft по заказу фирмы IBМ для компьютеров IBМ PC и стала одной из самых распространенных ОС в мире. В настоящее время наиболее распрост
Ввести текст
выход Ctrl + z или F6
Объединение текстовых файлов
COPY имя_файла1 + имя_файла2+ .... имя_файла_результата
Если имя файла - резуль
Процессы
Основной задачей операционной системы является рациональное распределение ресурсов компьютера. В многозадачных (мультипрограммных) операционных системах, таких Windows, Linux, польз
Запрос пользователя на создание процесса.
3. Выполнение системного запроса на создание нового процесса уже работающим процессом. Во время работы процесс (приложение) может создавать один или несколько новых процессов, напр
Защищенность и отказоустойчивость ОС
Защищенность – это защита операционной системы и самого компьютера от внешних и внутренних воздействий. Отказоустойчивость – характеристика аппарат
Защита от компьютерных вирусов.
Защита от проблем, связанных с электропитанием – источники бесперебойного питания, стабилизаторы напряжения.
Защита от сбоев аппаратного обеспечения - про
RAID уровень 1
полоса 0
полоса 1
полоса 2
полоса 3
RAID уровень 2
Байт 1
Байт 2
Байт 3
Байт 4
Байт 5
Распределение ресурсов ПК
ПК имеет большое количество ресурсов, каждый из которых может в конкретный момент времени использоваться только одним процессом. К ресурсам ПК относиться оперативная память, жесткие
Разрешение конфликтов при распределении ресурсов
Конфликты при распределении ресурсов возникают между процессами. Как известно, в произвольный момент времени ресурс может использовать (владеть) только один процесс. Процесс, которо
Условия тупика
1. Условие взаимного исключения – каждый ресурс в данный момент времени или отдан одному процессу или свободен;
2. Условие удержания и ожидания
Вектор доступных ресурсов
B = { 0, 1, 0, ………0, 1 }, где 0 – ресурс свободен, 1 – ресурс занят
Матрица текущего распределения ресурсов( n, m ) - n – количество ресурсов
m - количество проце
Матрица запросов процессов на ресурсы
R1,1 ………. R1,m
R = Ri,j где Ri,j =1, если i – р
Управление процессами в интерактивных ОС
Важнейшей функцией операционной системы является организация рационального использования всех аппаратных и программных ресурсов компьютера. К основным ресурсам относятся процессор,
Алгоритмы планирования потоков (процессов)
Для планирования смены потоков разработаны специальные алгоритмы планирования,
Вытесняющие алгоритмы– при использовании таких алгоритмов ОС сама принимает
Синхронизация процессов и потоков
Необходимость в синхронизации процессов и потоков возникает в многозадачных операционных системах и связана с совместным использованием аппаратных и информационных ресурсов системы. Синхронизацией
Распределение ресурсов ПК
ПК имеет большое количество ресурсов, каждый из которых может в конкретный момент времени использоваться только одним процессом. К ресурсам ПК относиться оперативная память, жесткие
Разрешение конфликтов при распределении ресурсов
Конфликты при распределении ресурсов возникают между процессами. Как известно, в произвольный момент времени ресурс может использовать (владеть) только один процесс. Процесс, которо
Условия тупика
5. Условие взаимного исключения – каждый ресурс в данный момент времени или отдан одному процессу или свободен;
6. Условие удержания и ожидания
Вектор доступных ресурсов
B = { 0, 1, 0, ………0, 1 }, где 0 – ресурс свободен, 1 – ресурс занят
Матрица текущего распределения ресурсов( n, m ) - n – количество ресурсов
m - количество проце
Матрица запросов процессов на ресурсы
R1,1 ………. R1,m
R = Ri,j где Ri,j =1, если i – р
Управление памятью
Память компьютера подразделяется на два больших класса: внешняя и внутренняя.
В состав внутренний памяти входит оперативная память, постоянная память и регистры процессора.
Типы адресов
Для идентификации переменных и программ на разных этапах жизни программы используется три типа адресов.
Символьные адреса
Задачей ОС является отображение индивидуальных виртуальных адресных пространств всех одновременно выполняющихся процессов на общую физическую память.
Виртуальные адреса
Оперативная память
0000000016
Кэширование данных
Память компьютера представляет собой иерархию запоминающих устройств (ЗУ), которые отличаются друг от друга среднем временем доступа к данным, объемом памяти и стоимостью хранения о
Принципы действия КЭШ памяти
Содержимое КЭШ – памяти представляет собой совокупность записей обо всех загруженных в нее данных из основной памяти. Разработано много способов выбора данных из основой памяти, в том числе и алгор
История развития
В 1983 фирма Microsoft объявляет о выпуске оболочки Windows, дополняющей операционную систему MS DOS графическим интерфейсом.
В 1985 году появляется Windows 1.0 – пользователи могут одновр
Загрузка WINDOWS XP
При включении питания или перезагрузке компьютер проходит процедуру самотестирования при включении (Power On Self Test, POST), которая представляет собой набор тес
Архитектура Windows XP
ОС Windows XP построена по модульному принципу. Модули входят в состав основных компонентов, каждый компонент отвечает за определенный раздел ОС и выполняет свои функции. Между комп
Основные компоненты ОС Windows XP
Системная виртуальная машина
Базовая система
Компонент Базовая система содержит все внутренние службы ОС, специальные службы низкого уровня, в состав Базовой системы входят:
П
Технологические принципы ОС Windows
Для ОС Windows были разработаны новые (для того времени) принципы организации графического интерфейса:
1. Принцип Select – Выделить – фрагмент документа, объект или группу
Архитектура Plug and Play в Windows 2000
Приложения служебные
Процессы Win32
PnP программа
Менеджер setup
Режим пользователя
Физическая организация данных NTFS
Файловая система NTFS была разработана в качестве основной файловой системы для ОС WINDOWS NT в начале 90 – ых годов с учетом опыта разработки файловых систем FAT и HPFS (основная файловая система
Адресация файлов
Все файлы NFTS идентифицируются (определяются) номером файла, который соответствует позиции файла в таблице MFT. Идентификации файла с помощью номера похожа на определение файла в
Структура тома NFTS
Загрузочный блок
Содержит параметры необходимые для загрузки диска (BIOS)
16 стандартн
Типы файлов NTFS
Файлы в зависимости от способа размещения делятся на небольшие, большие, очень большие и сверхбольшие.
Небольшие файлы (small) целиком располагаются в
Каталоги NTFS
Каждый каталог представляет собой одну запись в таблице MFT, которая содержит атрибут Index Root. Этот атрибут содержит список файлов, входящих в каталог.
Имеется две форм
Архивирование данных
Большой объем данных на жестком диске, необходимость сохранять данные на внешнем носителе, передавать по компьютерным сетям, электронной почте приводит к необходимости уплотнения ин
Методы сжатия информации
Все методы сжатия информации можно разделить на два больших непересекающихся класса: сжатие с потерей информации и сжатие без потери информации.
Сжатие с потерей ин
Компьютерные вирусы
Компьютерным вирусом называется программа, способная выполнять на компьютере несанкционированные действия. Это специально написанная, как правило, небольшая по объе
Способы распространения вирусов
Классический вариант. Когда вирус создан, он помещается в какую-либо программу, как правило, игру или полезную утилиту. Затем эта программа распространяется, например через Web-сай
Обнаружение вирусов
Обнаружение по базе данных. Большинство антивирусных программ выявляют вирусы по известным образцам их программного кода. С этой целью создаются базы данных вирусов. Просматриваютс
Защита от заражения вирусом
1. Устанавливать чистое программное обеспечение, приобретенное у надежного производителя. Скачивать программы с Web – сайтов не рекомендуется;
2. Проверять дискеты перед тем, как загружать
Реестр Windows XP
Реестр – регистрационная (централизованная) база данных, которая хранит в себе всю информацию о конфигурации системы, а именно параметры настройки системы и настрой
Структура реестра
Логическая структура реестра похожа на логическую структуру файловой системы на диске. Реестр содержит ключи (корневые разделы), которые аналогичны папкам, и параметры, которые аналогичны файлам. К
Зарегистрированные типы файлов
Как известно, для того чтобы открыть документ в Windows, достаточно дважды щелкнуть по его имени мышью. При этом щелчке программа – обработчик определяет по типу файла приложение, к
Записи реестра для приложений Windows
При установке приложения должны быть внесены данные о типе данных, а также о местонахождении исполнимого файла .EXE и динамических библиотеках .DLL, используемых этим приложением. Стандарт
Цветовое оформление
Значение цвета записывается, как строка из трех чисел от 0 до 255 разделенных пробелом. Каждое число определяет интенсивность основного цвета: красный, зеленый, синий
FF0000 – чисто красны
Настройки устройств
Каждое устройство имеет свой подраздел, имя которого совпадает с именем устройства
Например, для «Мыши» - Mouse
HKEY_CURRENT_USER
Control Panel
desktop
настройки экрана
B
Озвучивание событий
Пользователь имеет возможность создать звуковое сопровождение определенным действиям, как системным, так и для конкретного приложения, например закрытие папки, вход, выход из системы.
Озву
Настройка отображения информации в папке
Вкладка «Вид» окна «Свойства папки» -содержит параметры отображение информации
эта информа
История создания и развития ОС LINUX
ОС LINUX появилась в конце 1960 г. В 1957 году в Laboratories Bell Telephone возникла необходимость новой операционной системы, которая удовлетворяла бы требованиям ЭВМ 2 – го покол
Диалог пользователя
Диалог пользователя может быть организован в двух режимах: текстовом и графическом.
В текстовом режиме пользователь вводит команды с клавиатуры после получения приг
Файловая система ОС LINUX
В ОС LINUX понятие файла имеет более общее значение. Файлом называют любой источник данных, из которого данные могут быть считаны, или любой объект, куда данные могут быть за
Типы файлов
В ОС LINUX определены шесть типов файлов:
1. Обычный файл ( regular file ) - имеет обозначение f или - ;
2. Каталог ( directory ) - d;
3. Специальный файл устройства ( sp
Атрибуты файлов
ОС LINUX – многопользовательская ОС, поэтому должно быть обеспечено ограничение на действия пользователя с файлами (данными). Это реализуется с помощью прав доступа к файлам, которые приписываются
Физическая организация данных
Физическая организация данных Linux file System ( UFS ) была разработана на основе файловой системы S5 ( одной из ранних версий LINUX ) и расширяет возможности S5 по поддержке больших дисков и файл
Процессы
Процесс – основное понятие ОС. Операционная система создает процесс, когда пользователь запускает программу на выполнение. ОС руководит всеми процессами в системе,
Просмотр текущего каталога
# ls - l - расширенный формат вывода информации - на экране таблица
Тип файла
Права доступа
Кол. жестк. связей
Копирование файлов
# cp < имя_файла1 > < имя_файла2 >
Если действия над файлами выполняются в текущем каталоге, то указывается только имя файла, если нет, то следует указывать полный путь к файлу
Изменение прав доступа
# chmod < пользователь > < режим доступа > < право > <имя_файла>
пользователь
u - владелец; g - группа; o - остальные пользователи; a – все
Выделение части подстроки
# cut - b < список > < имя_файла >
список – определяет позиции для выделения подстроки
- - n - от начала строки до n – го символа
- n - - от n – го символа до
Фильтрация файлов
Фильтрацией файлов называют определение файлов, которые содержат данные согласно некоторому критерию ( образцу ). Список файлов может быть перенаправлен в другой файл для последующей работы.
Логические выражения
- name < шаблон_имен_файлов > - можно использовать метасимволы
Пример # find . - name a*
- perm < права_доступа > - поиск по атрибутам файлов
Пример # find .
Архивирование и сжатие файлов
Архивирование данных – получение файла специального формата, архивного файла, который позволяет сохранить файлы вместе с характерной для них информацией:
- Имя файл
Физические устройства LINUX
В ОС LINUX все физические устройства представлены в виде специальных файлов, каждому устройству соответствует свой специальный файл, работой устройств управляют программы – драйверы.
Со вс
Монтирование файловых систем
Каждый диск или раздел диска имеет свою иерархическую структуру со своим корневым каталогом, подкаталогами и файлами. В ОС LINUX отдельные файловые системы могут присоединяться ( монтироваться ) к
Чтение с дискеты
# cp / mnt / floppy < имена_файлов >
SHELL – сценарии
SHELL – сценарий - это текстовый файл, который содерж
Mkdir fd
cp *.tx /fd
Пример 2. Составить сценарий, который позволяет переместить файлы текущего каталога с суффиксом tx в каталог fd и удалить их.
Echo строка
Строка заключается в двойные кавычки, можно использовать управляющий символ /n – переход на новую строку.
echo “ all ready “
Архитектура сетевой операционной системы
Компьютерная сеть – совокупность компьютеров, связанных коммуникационным оборудованием, работающих под управлением сетевой операционной системы. Операционна
Трехзвенная модель
Компьютер 1
Компьютер 2
Компьютер 3
Интерфейс пользователя
Новости и инфо для студентов