Pr1 (производитель) DO (TRUE) Подготовить «ЗАПИСЬ» P(ПУСТО) (ждать, пока ПУСТО станет=1) Запись в буфер V(ПОЛНО) OD | Pr2 (потребитель) DO (TRUE) P(ПОЛНО) (ждать, пока ПОЛНО станет=1) Читать из буфера V(ПУСТО) Использовать «ЗАПИСЬ» OD |
Алгоритм исполнения процессов "Производитель-Потребитель" с буфером на одну запись:
GLB буфер (глобальная
переменная)
Semaphore ПОЛНО, ПУСТО
ПОЛНО = 0
ПУСТО = 1
CO BEGIN (Corporation Begin)
CO{
Вызвать "Производитель";
Вызвать "Потребитель"
СО}
COEND
Рис. 33 Временная диаграмма синхронизации процессов "Производитель - Потребитель"с буфером на одну запись
Вопросы по лекции № 12:
Что такое двоичные семафоры? Что такое считающие семафоры? Алгоритм V(s) и P(s). Написать Алгоритм "Производитель-Потребитель" с буфером на одну запись Назовите достоинство синхронизации на основе семафорных операций?ЛЕКЦИЯ 13
Тупиковые ситуации
В многопользовательских системах процесс находится в состоянии тупика, если он ожидает некоторого события, которое никогда не произойдет.
Системная тупиковая ситуация - когда один или более процессов оказываются в состоянии тупика.
С тупиком связана проблема - "бесконечное откладывание" - когда процесс, даже не находящийся в состоянии тупика, ожидает события, которое может никогда не произойти из-за "необъективных" принципов, заложенных в системе планирования ресурсов.
Рис. 34 Схема тупиковой ситуации
Процесс 1 "владеет" ресурсом 1, а процесс 2 "владеет" ресурсом 2. В то же время оба процесса ждут выделения им дополнительного ресурса, которое не может произойти.
Условие возникновения тупиковых ситуаций
Процессы требуют предоставления им права монопольного управления ресурсами, которые им предоставляются (условие взаимоисключения). Процессы удерживают за собой ресурсы, выделенные им, в то же время ожидают выделения дополнительных ресурсов (условие ожидания ресурсов). Ресурсы нельзя отобрать у процесса, удерживающего их, пока эти ресурсы не будут использованы для завершения работы (условия неперераспределенности). Существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся следующему процессу цепи (условие кругового ожидания).На рисунке представлена временная диаграмма DEADLOCK'а.
Рис. 35 Временная диаграмма DEADLOCK'а
Представлены два соперничающих процесса Pr1 и Pr2, которые блокируют друг друга. Каждый пытается получить ресурс, монопольно занятый другим.
Предотвращение тупиковых ситуаций
1. На стадии написания программ. Программа так должна быть написана, чтобы тупик не мог возникнуть ни при каком соотношении взаимных скоростей процессов. Например, если бы процессы Pr1 и Pr2 запрашивали бы ресурсы в одинаковой последовательности, то тупик был бы не возможен.
2. Динамический подход к предотвращению тупика. Использование определенных правил при назначении ресурсов процессам, т. е. ресурсы могут выделяться процессам в определенной последовательности, общей для всех процессов.
3. Распознавание "тупиков". Существуют программные методы распознавания тупиков. Программные методы основаны на использовании таблиц распределения ресурсов и таблицы запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки.
4. Выход из тупика. Если тупиковая ситуация возникла, то не обязательно снимать с выполнения все заблокированные процессы.
4.1 Можно снять только часть из них, тогда освобождаемые ресурсы можно предоставить другим процессам, которые их ожидают.
4.2 Можно вернуть некоторые процессы в область свопинга.
4.3 Можно совершить так называемый "откат" некоторых процессов до "контрольной точки", в которой запоминается вся информация для восстановления выполнения программы с данного места. "Контрольные точки" расставляются в программах в местах, после которых возможны тупики.
Для того чтобы обеспечить написание корректных программ, было предложено высокоуровневое средство синхронизации - "монитор" - это набор процедур, переменных и структур данных. Процессы могут вызывать процедуры монитора, но не имеют доступа к внутренним данным монитора. Мониторы имеют свойства, позволяющие достичь взаимоисключения процессов, а именно: только один процесс может быть активным по отношению к монитору, это достигается не за счет программирования, а на уровне компилятора. Компилятор обрабатывает вызовы процедур монитора таким образом, что первые несколько инструкций этой процедуры проверяют - не активен ли какой-либо процесс по отношению к монитору. Если "ДА", то вызывающий процесс приостанавливается, пока другой не освободит монитор. Но когда процессы имеют собственную ОП, используется механизм семафорных операций. В таких системах синхронизация реализована с помощью обмена сообщениями.
Вопросы по лекции № 13:
Что такое тупиковые ситуации? Что такое отсрочка процесса? Нарисовать схемы тупиковых ситуаций. Назовите условия возникновения тупиковых ситуаций Как предотвратить тупиковую ситуацю?ЛЕКЦИЯ 14
Контекст процесса
Ядро в UNIX - это набор системных вызовов для порождения, уничтожения процессов. В UNIX ядро полностью пассивный набор программ и данных. Любая программа ядра может начаться только по инициативе пользователя (формирование пользовательского вызова по причине прерывания). Ядро всегда в контексте некоторого процесса.
Контекст процесса включает:
1. содержимое пользовательского адресного пространства;
2. регистровый контекст – содержимое регистров (RG счетчика команд, RG состояний CPU, РОН);
3. содержимое разделяемых сегментов и сегментов файлов, которые отображают виртуальную память;
4. контекст системного уровня.
Этот контекст состоит из 2-х частей.
Статической, которая включает: описатель процесса; U-область – индивидуально для каждого CPU область пространства ядра. Эта область располагается в отдельном месте ОП. Эта область содержит все данные из описанной ранее структуры(user-str, proc-str). Динамическая – один или несколько стеков, которые исполняются процессом при выполнении в режиме ядра. Число стеков соответствует числу уровней прерывания, которые поддерживаются конкретной аппаратурой.Контекст процесса – как бы мгновенная фотография процесса.
Образ процесса
Состав:
образ памяти; значения общих регистров; состояния открытых файлов; состояние текущей директории.При исполнении образ процесса размещается в ОП. При предоставлении ресурса более приоритетному процессу образ процесса предыдущего откачивается на диск.
Управление памятью
Цель управления оперативной памятью.
Уменьшить пустые пространства памяти (т. е. фрагментацию), возникающие из-за того, что программы пользователей имеют различные объемы и особенности. Повысить степень мультипрограммирования (в конечном счете - увеличить производительность ЭВМ).Алгоритмы управления памятью
Алгоритм связного выделения ОП – обязательное размещение всей задачи в смежных ячейках ОП. Алгоритм не связного выделение ОП – размещение задач в виде отдельных фрагментов, каждый из которых может занимать не смежные области в памяти.№ | Название | Характеристики | Использование |
1 | Одиночное непрерывное распределение | · Отсутствие очереди работ · Вся память в распоряжении одной задачи | Мониторные ОС |
2 | Распределение ОП фиксированными разделами | · Существует очередь работ · Связное выделение памяти · ОП делится на несколько независимых разделов · Количество и размеры разделов постоянное, устанавливаются при генерации ОС | Пакетные мультипрограммные ОС |
3 | Динамическое распределение ОП | · Связное выделение ОП · Размер участка ОП выделяемой, задаче определяется размером задачи, а не всего задания пользователя, как в п.2 · Возможно динамическое перемещение задач для уменьшения фрагментации | Мультипрограммные ОС, системы реального времени |
4 | Страничное распределение ОП (статическое) | · Несвязное выделение · ОП разбивается на страницы – блоки памяти (размер связан с типом ВС) · Все страницы одной задачи должны быть размещены в ОП (отсутствует перекачка страниц) | Мультипрограммные ОС, системы реального времени |
5 | Виртуальная память | · Несвязное выделение · Адресное пространство включает в себя реальную память ОП и часть дисковой · Все адресное пространство разбивается на страницы · В реальной памяти находятся только несколько страниц задачи (остальные на диске и подгружаются) | Мультипрограммные ОС, системы реального времени, многопроцессорные ОС и сетевые ОС. |
6 | Составная виртуальная память | · Существует очередь работ · Связное выделение памяти · ОП делится на несколько независимых разделов · Количество и размеры разделов постоянное, устанавливаются при генерации ОС | Мультипрограммные ОС, системы реального времени, многопроцессорные ОС и сетевые ОС. |
Табл. 5 Таблица алгоритмов управления.
1. Непрерывное одиночное распределение.
При одиночном непрерывном распределении пользователю выделяется вся память, кроме некоторой фиксированной, отведенной под ядро ОС.
Рис. 36. Схема карты памяти при одиночном непрерывном распределении памяти
Достоинство распределения:
- простота метода
Недостаток распределения:
- часть ОП свободна; наблюдаются простои ОП из-за неэффективного использования.
1’. Простое непрерывное распределение.
Пользовательские программы, ожидающие исполнения, хранятся в очереди работ.
Существует управляющая программа, которая определяет момент загрузки следующей работы.
Рис. 37 Схема простого непрерывного последовательного распределения ОП
Недостатки метода:
- невозможно использовать процессор, когда пользователь находится в режиме ожидания; часть ОП может быть не использована.
Достоинства метода:
- простая реализация; отказ от защиты памяти.
2. Статическое распределение разделами.
Задание пользователя состоит из нескольких задач. Каждой задаче выделяется постоянный раздел. Это выделение производится программой начальной загрузки, защита разделов производится по ключам. Должна существовать таблица разделов с указанием размера и его состояния (свободен или занят).
Алгоритм выделения памяти:
- по таблице запросов и ресурсов происходит просмотр требований и предложений; выбирается раздел, удовлетворяющий запросу; заполнение раздела происходит последовательно во времени исполнения задач.
Достоинство метода:
- простота реализации.
Недостатки метода:
- часть выделяемого раздела остается свободной; часть ОП незанята; может случиться отказ или задержка, если нет предложений, удовлетворяющих запрос.
Рассмотрим пример.
Таблица разделов:
Получено задание, которое требует:
- для трансляции (ассемблера)- 60К; для редактора связей -128К; на выполнение - 20К.
Происходит просмотр разделов - останавливаются на разделе 3, т. е. его объем памяти 128 соответствует максимально требуемому 120К. Действия происходят последовательно во времени, т. е. раздел 128К последовательно отводится для
- трансляции; редактора связей; выполнения.
На рисунке представлена временная диаграмма выделения оперативной памяти при статическом распределении разделами.
Рис. 38 Временная диаграмма выделения оперативной памяти при статическом распределении разделами
3. Динамическое распределение.
Память выделяется согласно заявке перед очередной задачей.
ПРИМЕР.
Дана фиксированная область памяти. Задача заключается в том, чтобы занимать и освобождать меньшие области памяти (имеющиеся в резерве) большей (приходящей по требованию) без выхода за границы памяти (отсюда может быть название - распределение разделами переменной длины или распределение перемещаемыми разделами). Задачи (от 1 до 6) требуют следующие объемы ОП:
Происходят действия:
- по таблице находится свободный участок памяти; если необходимо, разделяется найденный на 2 участка (модификация таблицы); слияние соседних свободных участков (модификация таблицы).
На рисунке 39 представлена таблица распределения памяти
Рис. 39 Таблица распределения памяти
Итак: при распределении памяти появляются небольшие свободные области. Эти области малы для размещения в них задач (если требуется большой объем), т. е. память становится фрагментарной.
Имеются следующие способы уменьшения фрагментарности:
а) первое возможное размещение (первый подходящий по размеру):
последовательно просматриваются области памяти, пока не будет найдена первая область, достаточная для размещения данных. Все области памяти организованы в связанный список, упорядоченный по адресам.
Поиск в этом списке осуществляется последовательно до тех пор пока не будет найдена достаточно большая область для размещения данных. Тогда эта область изымается из списка, а на этом месте списка помещается меньшая свободная область - оставшаяся незанятой.
Достоинства:
- с помощью этого способа легко освободить ранее занятые области памяти. С этой целью просматривается список, т. к. он упорядочен по адресам, то нетрудно найти место, чтобы поместить освобождаемую область, т. к. соседние адреса ЭВМ - смежные в списке, поэтому легко объединить две свободные области; простота.
Недостаток: т. к. осуществляется поиск только первой области для размещения данных, память становится (остается) фрагментарной.
б) наилучшее размещение ("самый подходящий" алгоритм):
" последовательно просматриваются все области;
" выбирается наименьшая область, размер которой больше или равен требуемому объему для размещения данных.
Пример.
Требуется 120К ОП для размещения задачи.
Карта свободных областей:
Остановились на 128К (список свободных областей просматривали до конца).
В этом случае области связываются друг с другом по размеру, а не по адресам. Алгоритм размещения-освобождения аналогичен предыдущему.
Достоинство - размещение приводит к меньшей фрагментарности (т. к. ищется из претендентов наиболее подходящий).
Недостаток - т. к. свободные области не упорядочены по адресам - алгоритм объединения двух свободных областей в одну достаточно сложен.
Вопросы по лекции № 14:
Какие существую 2 процесса управления памятью? Назовите цель управления памятью? Алгоритмы управления памятью? Назовите характеристики динамического распределение ОП (из таблицы алгоритмов управления).ЛЕКЦИЯ 15
Страничное распределение памяти (статическое распределение)
Это метод борьбы с фрагментацией (отказ от непрерывного адресного пространства для конкретной задачи)
Положение строго распределено.
1. ОП разбивается на блоки фиксированного размера (физ. ОП);
2. Адресное пространство задачи разбивается на страницы такого же размера;
3. Страницы одной задачи должны быть все одновременно в ОП, но можно занимать различные участки памяти (вразброс);
4. Страницы не перемещаются;
5. Для каждой задачи организуется таблица страниц, в которых отсутствует бит присутствия;
6. Используется RG адреса таблицы страниц для указания адреса таблицы страниц текущей задачи.
Рис.40 Схема адресации (генерация физического адреса) при статическом распределении ОП страницами
Таблица страниц устанавливает взаимосвязь между логическим страницами, с которыми работает процесс пользователя, и физическими страницами, с которыми работает центральный процессор.
С одной физической страницей могут быть связаны несколько логических (например: когда несколько процессов разделяют некоторую повторно входимую программу).
Логическое адресное пространство страницы - это источник информации для передачи данных (чему-либо - в наше случае - физической памяти).
Достоинства распределения:
- отсутствует внешняя фрагментация (а есть, например, внутри страницы); нет затрат на сжатие.
Недостатки распределения:
- двойное обращение к ОП - быстродействие понижается. Меры исключения этого недостатка: ассоциативная память, специальные регистры для всех таблиц страниц. накладные расходы на таблицы; внутренняя фрагментация ("усеченные страницы"); задачи, занимающие ОП, не все используются; возможны отказы.
Виртуальная память
Виртуальная память - это совокупность программно-аппаратных средств, позволяющих пользователям писать программы, размер которых превосходит имеющуюся оперативную память; для этого «ВИРТУАЛЬНАЯ ПАМЯТЬ» решает следующие задачи:
- размещает данные в запоминающих устройствах разного типа, например, часть программы в оперативной памяти, а часть на диске; перемещает по мере необходимости данные между запоминающими устройствами разного типа, например, подгружает часть с диска в оперативную память; преобразует виртуальные адреса в физические.
Перечень положений при распределением страниц ОП по запросам:
- ОП разбивается на блоки фиксированной длины; адресное пространство разбивается на страницы, такого же размера; для каждой задачи пользователя организуется таблица страниц; существует регистр адреса таблицы страниц, содержимое регистров меняется при переключении от одной задаче к другой.
Дополнение: каждая виртуальная страница находится либо на внешнем устройстве, либо в физической странице. Физическая страница должна занимать непрерывную область памяти. Непрерывность же логических страниц не требуется.
Рис. 41 Блок-схема алгоритма обращения к страничной памяти (виртуальная память)
Swapping.
ОС может обеспечить одновременную обработку нескольких работ - посредствам свопинга
, при этом наблюдается следующее
Система переключается на другую работу посредством
Перемещения текущей работы из ОП во вспомогательную. Загрузки выбранной работы из вспомогательной в основную.Свопинг (замещение) - вызов адресного пространства задач полностью в ОП с вытеснением адресного пространства других задач (синонимы: системный обмен, попеременная загрузка).
Достоинства свопинга:
- полезен тем, что позволяет заново распределять память для работы не запуская ее с самого начала; такое повторное распределение ранее выделенных и еще находящихся в использовании ресурсов, называется перераспределением, и его можно использовать для обслуживания высокоприоритетных работ, или для предотвращения тупиковых ситуаций (deadlock).
Недостаток свопинга: увеличивается неопределенность времени ответа пользователям из-за приоритета программы большого объема, из-за блокировки программы с интенсивным вводом/выводом.
Управление памятью в Unix
В ОС UNIX наряду с механизмом управления страницами используется и механизм свопинга. Свопинг в ОС UNIX применяется в предаварийных ситуациях, когда размер свободной ОП уменьшается до некоторого заданного порога, т. е. когда работа системы в целом становится затруднительной. Для вытеснения в ОС UINX используется несколько констант, которые описывают размер свободной памяти. Эти константы являются пороговыми значениями для действий по освобождению ОП.
Рис. 42 Диаграмма пороговых значений для действий по освобождению физической памяти
Pageout - специальный процесс ядра, ему нужно иметь информацию о текущем состоянии физической. памяти.
1. lostfree - если свободная память в системе превышает порог, то процесс Pageout не вызывается.
2. desfree - если размер свободной физической памяти в системе находится в промежутке между A и В, то pageout вызывается 4 раза в секунду.
3. minfree - если размер свободной ФП становится меньше B, т. е. от B до C, то Pageout вызывается при каждом цикле работы функции clock циклически.
4. grgslo - если свободная ФП становится меньше порога D, то в действие вступает процесс свопинга, который в UNIX (system V) называется Shеd.
Shеd - выбирает определенный процесс, а затем выгружает все его страницы на диск, освобождая сразу значительное место в ФП.
Процесс, выгруженный на диск, исключается из претендентов на выполнение. Через t процесс Shеd вызывается снова, и, если количество свободной ФП меньше GRGSLO (порога D), то выгруженный процесс перекачивается с диска в физическую память и помещается в очередь готовых к выполнению процессов.
ОС UNIX планирует процесс вытеснения виртуальных страниц. Процесс Pageout использует для вытеснения алгоритм NRU (Not Recently Used) - выбирает для вытеснения не используемые в последнее время страницы. Этот алгоритм использует признаки модификации и доступа страниц (бит изменения, обращения).
Pageout периодически очищает эти признаки у физических страниц, которые не свободны. Если при следующем вызове Pageout видит, что эти признаки = 0, то значит доступа к этим страницам с момента предыдущего вызова Pageout не было. Тогда эти страницы вытесняются на диск.
Pageout - циклически проверяет все блоки (физические страницы) ОП, поэтому он называется циклическим (часовым) алгоритмом.
Вопросы по лекции № 15:
Что такое Pageout? Что такое виртуальная память? Назовите достоинства статического распределения памяти. Назовите недостатки статического распределения памяти. Расскажите об управлении памятью в Unix.Оглавление
Аннотация. 2
ЛЕКЦИЯ 1. 3
Введение в операционные системы.. 3
Операционная система выполняет следующие основные функции. 3
Функции ОС. 3
Обзор ОС.. 4
Проблемы, которые возникают при многозадачности. 4
ЛЕКЦИЯ 2. 5
Планирование доступа к вычислительным ресурсам.. 5
Управление заданиями. 6
Особенности управления заданиями. 6
Схема функционирования ОС.. 7
Дисциплины обслуживания очередей.. 8
Беcприоритетные ДО... 9
Смешанный алгоритм.. 10
Приоритетные ДО... 11
Относительный приоритет (ОП) 11
ЛЕКЦИЯ 3. 12
Приоритетные дисциплины обслуживания. 12
Абсолютный приоритет (АП) 12
Адаптивное обслуживание. 12
ДО с динамическим приоритетом.. 12
Планирование по критерию MIN суммарного времени выполнения работы.. 13
Алгоритм ДЖОНСОНА.. 15
ЛЕКЦИЯ 4. 16
Управление задачами. 16
Функции SV.. 16
Блок схема работы SV.. 16
Прерывания. 17
Алгоритм обработки прерывания. 17
Продвижение задач в системе. 18
Выполнение. 18
Алгоритм функционирования диспетчера задач (DISPATCH) 19
ЛЕКЦИЯ 5. 20
Диспетчеризация задач.. 20
Общая схема супервизора. 20
Временные диаграммы диспетчеризации задач. 21
Алгоритм обслуживания по вводу/выводу. 21
Граф - схема алгоритма прерывания по в/в. 22
ЛЕКЦИЯ 6. 24
Системные задачи. Взаимодействие ядра и задач. 24
Ядро ОС.. 24
Состав ядра. 25
Функции ядра. 25
Структурная схема взаимодействия ядра и задач. 25
ЛЕКЦИЯ 7. 28
Организация цепочек связей между проблемными и системными задачами. 28
Алгоритм работы с очередью при завершении задачи. 30
ЛЕКЦИЯ 8. 31
Ядро ОС Unix. Структура ОС Unix. 31
Блок схема системного ядра ОС Unix. 32
Функции ОС Unix. 32
Управление процессами. 33
ЛЕКЦИЯ 9. 35
Управление процессами в ОС UNIX... 35
Примеры системных вызовов в Unix. 36
Жизненный цикл процесса. 37
Планирование и диспетчеризация процесса. 37
ЛЕКЦИЯ 10. 39
Планирование и диспетчеризация процессов. 39
Функции планировщика-диспетчера. 39
Приостановка процесса. 39
Схемы очередей блоков управления процессами до а. и после б. "приостановки": 39
Алгоритм "Приостановить процесс": 40
Отсрочка процесса. 40
Алгоритм "Возобновить процесс". 41
Алгоритм «АКТИВИЗИРОВАТЬ». 41
ВЫВОДЫ... 42
ЛЕКЦИЯ 11. 44
Взаимоисключение процессов без посредника. 44
Использование команды” ПРОВЕРИТЬ и УСТАНОВИТЬ” на примере временной диаграммы. 44
Взаимоисключения с участием посредников. 44
Алгоритм DOWN.. 45
Алгоритм UP. МЬЮТЕКСЫ. 45
ЛЕКЦИЯ 12. 46
Двоичные семафоры.. 46
Считающий семафор. Числовой семафор. 47
Алгоритм P(s) 47
Алгоритм V(s) 48
Семафоры как счетчики ресурсов и синхронизаторы. 48
Алгоритм "Производитель-Потребитель" с буфером на одну запись. 48
Алгоритм исполнения процессов "Производитель-Потребитель" с буфером на одну запись: 49
ЛЕКЦИЯ 13. 50
Тупиковые ситуации. 50
Условие возникновения тупиковых ситуаций. 50
ЛЕКЦИЯ 14. 53
Контекст процесса. 53
Образ процесса. 53
Управление памятью... 53
Алгоритмы управления памятью.. 53
1. Непрерывное одиночное распределение. 56
1’. Простое непрерывное распределение. 56
2. Статическое распределение разделами. 57
3. Динамическое распределение. 58
ЛЕКЦИЯ 15. 61
Страничное распределение памяти (статическое распределение) 61
Виртуальная память. 62
Swapping. 63
Управление памятью в Unix. 64
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 |
