Слайд 1Лекция 5
Алгоритмы планирования.
Прерывания
Слайд 2Вытесняющие и невытесняющие алгоритмы планирования
Всё множество алгоритмов планирования можно разделить
на два класса: вытесняющие и невытесняющие.
Невытесняющие алгоритмы основаны на том,
что активному потоку позволяется выполняться, пока он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы та выбрала из очереди другой готовый к выполнению поток.
Вытесняющие алгоритмы- способы планирования потоков, в которых решение о переключении процессора с выполнения одного потока на выполнение другого потока принимается операционной системой, а не активной задачей.
Слайд 3Основным различием между вытесняющими и невытесняющими алгоритмами является степень централизации
механизма планирования потоков. При вытесняющем мультипрограммировании функции планирования потоков целиком
сосредоточены в операционной системе. При этом ОС выполняет следующие функции: определяет момент снятия с выполнения активного потока, запоминает его контекст, выбирает из очереди готовых потоков следующий, запускает новый поток на выполнение, загружая его контекст.
Слайд 4При невытесняющем
мультипрограммировании механизм планирования распределен между ОС и
прикладными программами. Прикладная программа, получив управление от операционной системы, сама
определяет момент завершения очередного цикла своего выполнения и только затем передает управление ОС с помощью какого-либо системного вызова.
Слайд 5ОС формирует очереди потоков и выбирает в соответствии с некоторым
правилом следующий поток на выполнение. Такой механизм создает проблемы как
для пользователей, так и для разработчиков приложений.
Для пользователей это означает, что управление системой теряется на произвольный период времени, который определяется приложением (а не пользователем). Подобный метод разделения времени между задачами существенно затрудняет разработку программ и предъявляет повышенные требования к квалификации программиста.
Слайд 6Алгоритмы планирования, основанные на квантовании
В основе многих вытесняющих алгоритмов планирования
лежит концепция квантования, в соответствии с которой каждому потоку поочередно
для выполнения предоставляется ограниченный непрерывный период процессорного времени — квант.
Смена активного потока происходит, если:
поток завершился и покинул систему;
произошла ошибка;
поток перешел в состояние ожидания;
исчерпан квант процессорного времени, отведенный данному потоку.
Слайд 8Если в системе имеется n потоков, то время, которое поток
проводит в ожидании следующего кванта, можно грубо оценить как q(n-1),
где q- длина кванта времени каждого потока. Чем больше потоков в системе, тем больше время ожидания, тем меньше возможности вести одновременную интерактивную работу нескольким пользователям.
Слайд 10Если квант короткий, то суммарное время, которое проводит поток в
ожидании процессора, прямо пропорционально времени, требуемому для его выполнения.
Если потоки
с интенсивными обращениями к вводу-выводу используют только небольшую часть выделенного им процессорного времени, то алгоритмом планирования таким потокам назначаются привилегии при последующем обслуживании.
Слайд 12Алгоритмы планирования, основанные на приоритетах
Приоритетное обслуживание предполагает наличие у потоков
некоторой изначально известной характеристики — приоритета, на основании которой определяется
порядок их выполнения.
Приоритет — это число, характеризующее степень привилегированности потока при использовании ресурсов вычислительной машины, в частности процессорного времени: чем выше приоритет, тем меньше времени будет проводить поток в очередях.
Слайд 13В большинстве ОС, поддерживающих потоки, приоритет потока непосредственно связан с
приоритетом процесса, в рамках которого выполняется данный поток.
Приоритет процесса назначается
операционной системой при его создании. Значение приоритета включается в описатель процесса и используется при назначении приоритета потокам этого процесса.
Слайд 14Схема назначения приоритетов потокам в Windows NT
В системе определено 32
уровня приоритетов и два класса потоков — потоки реального времени
и потоки с переменными приоритетами.
Диапазон от 1 до 15 включительно отведен для потоков с переменными приоритетами, а от 16 до 31 — для потоков реального времени (приоритет 0 зарезервирован для системных целей).
Слайд 16При создании процесса он в зависимости от класса получает по
умолчанию базовый приоритет. Базовый приоритет процесса в дальнейшем может быть
повышен или понижен ОС.
Например, если, значение базового приоритета некоторого процесса равно К, то все его потоки получат базовые приоритеты из диапазона [К-2, К+2]. Изменяя базовый приоритет процесса, ОС может влиять на базовые приоритеты его потоков.
Слайд 17Существуют две разновидности приоритетного планирования:
обслуживание с относительными и абсолютными
приоритетами. В обоих случаях выбор потока на выполнение из очереди
готовых осуществляется одинаково: выбирается поток, имеющий наивысший приоритет.
Слайд 18В системах с относительными приоритетами активный поток выполняется до тех
пор, пока он сам не покинет процессор, перейдя в состояние
ожидания (произойдет ошибка, или поток завершится).
Слайд 19В системах с абсолютными приоритетами выполнение активного потока прерывается кроме
указанных выше причин, еще при одном условии: если в очереди
готовых потоков появился поток, приоритет которого выше приоритета активного потока.
Слайд 20Мультипрограммирование на основе прерываний
Система прерываний переводит процессор на выполнение потока
команд, отличного от того, который выполнялся до сих пор, с
последующим возвратом к исходному коду.
Прерывание возникает либо в зависимости от внешних по отношению к процессу выполнения программы событий, либо при появлении непредвиденных аварийных ситуаций в процессе выполнения данной программы.
Слайд 21В зависимости от источника прерывания делятся на три больших класса:
Внешние
(аппаратные) прерывания могут возникать в результате действий пользователя или оператора
за терминалом, или же в результате поступления сигналов от аппаратных устройств — сигналов завершения операций ввода-вывода, вырабатываемых контроллерами внешних устройств компьютера.
Слайд 22Внутренние прерывания, называемые также исключениями (exception), происходят синхронно выполнению программы
при появлении аварийной ситуации в ходе исполнения некоторой инструкции программы.
Примерами
исключений являются деление на ноль, ошибки защиты памяти, обращения по несуществующему адресу, попытка выполнить привилегированную инструкцию в пользовательском режиме и т. п.
Слайд 23Программное прерывание возникает при выполнении особой команды процессора, выполнение которой
имитирует прерывание, то есть переход на новую последовательность инструкций.
Прерываниям
приписывается приоритет, с помощью которого они ранжируются по степени важности и срочности.
О прерываниях, имеющих одинаковое значение приоритета, говорят, что они относятся к одному уровню приоритета прерываний.
Процедуры, вызываемые по прерываниям, обычно называют обработчиками прерываний, или процедурами обслуживания прерываний (Interrupt Service Routine, ISR).
Слайд 25Кэш память или просто кэш — это способ совместного функционирования
двух типов запоминающих устройств, отличающихся временем доступа и стоимостью хранения
данных, который за счет динамического копирования в «быстрое» ЗУ наиболее часто используемой информации из «медленного» ЗУ позволяет, с одной стороны, уменьшить среднее время доступа к данным, а с другой стороны, экономить более дорогую быстродействующую память.
Слайд 27Неотъемлемым свойством кэш-памяти является ее прозрачность для программ и пользователей.
Система не требует никакой внешней информации об интенсивности использования данных;
ни пользователи, ни программы не принимают никакого участия в перемещении данных из ЗУ одного типа в ЗУ другого типа, все это делается автоматически системными средствами.
Слайд 28Кэш-памятью, или кэшем, часто называют не только способ организации работы
двух типов запоминающих устройств, но и одно из устройств —
«быстрое» ЗУ.
Если кэширование применяется для уменьшения среднего времени доступа к оперативной памяти, то в качестве кэша используют быстродействующую статическую память.
Если кэширование используется системой ввода-вывода для ускорения доступа к данным, хранящимся на диске, то в этом случае роль кэш-памяти выполняют буферы в оперативной памяти, в которых оседают наиболее активно используемые данные.
Слайд 29Виртуальную память также можно считать одним из вариантов реализации принципа
кэширования данных, при котором оперативная память выступает в роли кэша
по отношению к внешней памяти — жесткому диску.
Слайд 30Содержимое кэш-памяти представляет собой совокупность записей обо всех загруженных в
нее элементах данных из основной памяти. Каждая запись об элементе
данных включает в себя:
значение элемента данных;
адрес, который этот элемент данных имеет в основной памяти;
дополнительную информацию, которая используется для реализации алгоритма замещения данных в кэше и обычно включает признак модификации и
признак действительности данных.
Слайд 31При каждом обращении к основной памяти по физическому адресу просматривается
содержимое кэш-памяти с целью определения, не находятся ли там нужные
данные.
Слайд 32Далее возможен один из двух вариантов развития событий:
если данные обнаруживаются
в кэш-памяти, то есть произошло кэш- попадание, они считываются из
нее и результат передается источнику запроса;
если нужные данные отсутствуют в кэш-памяти, то есть произошел кэш-промах, они считываются из основной памяти, передаются источнику запроса и одновременно с этим копируются в кэш-память.
Слайд 34Эффективность кэширования зависит от вероятности попадания в кэш. В большинстве
реализаций кэш-памяти процент кэш-попадания оказывается весьма высоким — свыше 90
%.
Такое высокое значение вероятности нахождения данных в кэш-памяти объясняется наличием у данных объективных свойств: пространственной и временной локальности.
Слайд 35Временная локальность. Если произошло обращение по некоторому адресу, то следующее
обращение по тому же адресу с большой вероятностью произойдет в
ближайшее время. Вначале работы системы, когда кэш-память еще пуста, почти каждый запрос к основной памяти выполняется «по полной программе»: просмотр кэша, констатация промаха, чтение данных из основной памяти, передача результата источнику запроса и копирование данных в кэш.
Слайд 36Затем, по мере заполнения кэша, в полном соответствии со свойством
временной локальности возрастает вероятность обращения к данным, которые уже были
использованы на предыдущем этапе работы системы, то есть к данным, которые содержатся в кэше и могут быть считаны значительно быстрее, чем из основной памяти.
Слайд 37Пространственная локальность. Если произошло обращение по некоторому адресу, то с
высокой степенью вероятности в ближайшее время произойдет обращение к соседним
адресам.
Слайд 38Проблема согласования данных
В процессе работы содержимое кэш-памяти постоянно обновляется, а
значит, время от времени данные из нее должны вытесняться.
Алгоритм замены
данных в кэш-памяти существенно влияет на ее эффективность. В идеале такой алгоритм должен, во-первых, быть максимально быстрым, чтобы не замедлять работу кэш-памяти, а во-вторых, обеспечивать максимально возможную вероятность кэш-попаданий.
Слайд 39Наличие в компьютере двух копий данных — в основной памяти
и в кэше — порождает проблему согласования данных.
Если происходит запись
в основную намять по некоторому адресу, а содержимое этой ячейки находится в кэше, то в результате соответствующая запись в кэше становится недостоверной. Рассмотрим два подхода к решению этой проблемы:
Слайд 40Сквозная запись. При каждом запросе к основной памяти, в том
числе и при записи, просматривается кэш.
Если данные по запрашиваемому адресу
отсутствуют, то запись выполняется только в основную память.
Если же данные, к которым выполняется обращение, находятся в кэше, то запись выполняется одновременно в кэш и основную память.
Слайд 41Обратная запись. Аналогично при возникновении запроса к памяти выполняется просмотр
кэша, и если запрашиваемых данных там нет, то запись выполняется
только в основную память. В противном же случае запись производится только в кэш-память, при этом в описателе данных делается специальная отметка (признак модификации), которая указывает на то, что при вытеснении этих данных из кэша необходимо переписать их в основную память, чтобы актуализировать устаревшее содержимое основной памяти.
Слайд 42Способы отображения основной памяти на кэш
При случайном отображении элемент оперативной
памяти в общем случае может быть размещен в произвольном месте
кэш-памяти. Для того чтобы в дальнейшем можно было найти нужные данные в кэше, они помещаются туда вместе со своим адресом, который данные имеют в оперативной памяти. При каждом запросе к оперативной памяти выполняется поиск в кэше, причем критерием поиска выступает адрес оперативной памяти из запроса.
Слайд 43Для кэшей со случайным отображением используется так называемый ассоциативный поиск,
при котором сравнение выполняется не последовательно с каждой записью кэша,
а параллельно со всеми его записями (рис. 5.26). Признак, по которому выполняется сравнение, называется тегом (tag).
Слайд 45Второй, детерминированный способ отображения предполагает, что любой элемент основной памяти
всегда отображается в одно и то же место кэш-памяти. В
этом случае кэш-память разделена на строки, каждая из которых предназначена для храпения одной записи об одном элементе данных и имеет свой номер.
Слайд 46Между номерами строк кэш-памяти и адресами оперативной памяти устанавливается соответствие
«один ко многим»: одному номеру строки соответствует несколько (обычно достаточно
много) адресов оперативной памяти.
Например, пусть в кэш-памяти может храниться 1024 записи, то есть кэш имеет 1024 строки, пронумерованные от 0 до 1023. Тогда любой адрес оперативной памяти может быть отображен на адрес кэш-памяти простым отделением 10 двоичных разрядов (рис. 5.27).
Слайд 47При поиске данных в кэше используется быстрый прямой доступ к
записи по номеру строки, полученному путем обработки адреса оперативной памяти
из запроса. Однако поскольку в найденной строке могут находиться данные из любой ячейки оперативной памяти, младшие разряды адреса которой совпадают с номером строки, необходимо выполнить дополнительную проверку.
Для этих целей каждая строка кэш-памяти дополняется тегом, содержащим старшую часть адреса данных в оперативной памяти. При совпадении тега с соответствующей частью адреса из запроса констатируется кэш-попадание.
