1625914891-62d0978a4faa71912bcf30efde0ff3e3 (843827), страница 3
Текст из файла (страница 3)
Процесс,получивший в свое распоряжение процессор,занимает его до истечения текущего CPU burst.После этого для выполнения выбираетсяновый процесс из начала очереди.Алгоритмы планирования:Round Robin (RR)Модификацией алгоритма FCFS является алгоритм,получивший название Round Robin (Round Robin – этовид детской карусели в США) или сокращенно RR. Посути дела, это тот же самый алгоритм, толькореализованный в режиме вытесняющегопланирования.Алгоритмы планирования:Round Robin (RR)Реализуется такой алгоритм так же, как и предыдущий, с помощьюорганизации процессов, находящихся в состоянии готовность, вочередь FIFO. Планировщик выбирает для очередного исполненияпроцесс, расположенный в начале очереди, и устанавливает таймердля генерации прерывания по истечении определенного квантавремени.
При выполнении процесса возможны два варианта. Время непрерывного использования процессора, необходимоепроцессу (остаток текущего CPU burst), меньше или равнопродолжительности кванта времени. Тогда процесс по своей волеосвобождает процессор до истечения кванта времени, на исполнениепоступает новый процесс из начала очереди, и таймер начинаетотсчет кванта заново.Продолжительность остатка текущего CPU burst процесса больше,чем квант времени. Тогда по истечении этого кванта процесспрерывается таймером и помещается в конец очереди процессов,готовых к исполнению, а процессор выделяется для использованияпроцессу, находящемуся в ее начале.Алгоритмы планирования:Shortest-Job-First (SJF)При рассмотрении алгоритмов FCFS и RR видно, насколькосущественным для них является порядок расположения процессов вочереди процессов, готовых к исполнению. Если короткие задачирасположены в очереди ближе к ее началу, то общаяпроизводительность этих алгоритмов значительно возрастает.
Еслибы мы знали время следующих CPU burst для процессов,находящихся в состоянии готовность, то могли бы выбрать дляисполнения не процесс из начала очереди, а процесс с минимальнойдлительностью CPU burst. Если же таких процессов два или больше,то для выбора одного из них можно использовать уже известный намалгоритм FCFS. Квантование времени при этом не применяется.Описанный алгоритм получил название "кратчайшая работа первой"или Shortest Job First (SJF).Можно показать, что для заданного набора процессов (если в очередине появляются новые процессы) алгоритм SJF является оптимальнымс точки зрения минимизации среднего времени ожидания средикласса невытесняющих алгоритмов.Алгоритмы планирования:Гарантированное планированиеПри интерактивной работе N пользователей в вычислительной системеможно применить алгоритм планирования, который гарантирует, чтокаждый из пользователей будет иметь в своем распоряжении ~1/Nчасть процессорного времени.
Пронумеруем всех пользователей от 1до N. Для каждого пользователя с номером i введем две величины:Ti – время нахождения пользователя в системе и τi – суммарноепроцессорное время уже выделенное всем его процессам.Справедливым для пользователя было бы получение Ti/Nпроцессорного времени.Если τi<<Ti/N то i-й пользователь несправедливо обделенпроцессорным временем.Если же τi>>Ti/N то система явно благоволит к пользователю сномером i.Вычислим для процессов каждого пользователя значениекоэффициента справедливости τiN/Ti и будем предоставлятьочередной квант времени готовому процессу с наименьшейвеличиной этого отношения. Предложенный алгоритм называюталгоритмом гарантированного планирования.Алгоритмы планирования:Приоритетное планированиеАлгоритмы SJF и гарантированного планирования представляютсобой частные случаи приоритетного планирования.При приоритетном планировании каждому процессуприсваивается определенное числовое значение –приоритет, в соответствии с которым ему выделяетсяпроцессор.Процессы с одинаковыми приоритетами планируются в порядкеFCFS.
Для алгоритма SJF в качестве такого приоритетавыступает оценка продолжительности следующего CPU burst.Чем меньше значение этой оценки, тем более высокийприоритет имеет процесс. Для алгоритма гарантированногопланирования приоритетом служит вычисленныйкоэффициент справедливости. Чем он меньше, тем больше упроцесса приоритет.Алгоритмы планирования:Приоритетное планированиеПланирование с использованием приоритетовможет быть как вытесняющим, так иневытесняющим.При вытесняющем планировании процесс с болеевысоким приоритетом, появившийся в очередиготовых процессов, вытесняет исполняющийсяпроцесс с более низким приоритетом.В случае невытесняющего планирования он простостановится в начало очереди готовых процессов.Алгоритмы планирования:Приоритетное планированиеПриоритеты процессов, не изменяющиеся во времени,принято называть статическими+маленькие издержки,- не реагирует на изменение ситуации.Динамические приоритеты процессов, изменяют своизначения по ходу исполнения процессов (при рождениинового процесса, при разблокировке или блокированиипроцесса, по истечении определенного кванта времениили по завершении процесса)- Существенные накладные расходы,- Сложность реализации+Адаптивность к изменению состояния системы.Алгоритмы планирования:Многоуровневые очереди (MultilevelQueue)Алгоритмы планирования:Многоуровневые очереди с обратнойсвязью (Multilevel Feedback Queue)Дальнейшим развитием алгоритмамногоуровневых очередей являетсядобавление к нему механизма обратной связи.Здесь процесс не постоянно приписан копределенной очереди, а может мигрироватьиз одной очереди в другую в зависимости отсвоего поведения.Если при работе процесса появляется другойпроцесс в какой-либо более приоритетнойочереди, исполняющийся процесс вытесняетсяновым.Алгоритмы планирования:Многоуровневые очереди с обратнойсвязью (Multilevel Feedback Queue)Многоуровневые очереди с обратной связью представляют собойнаиболее общий подход к планированию процессов из числаподходов, рассмотренных нами.
Они наиболее трудны вреализации, но в то же время обладают наибольшей гибкостью.Понятно, что существует много других разновидностей такогоспособа планирования, помимо варианта, приведенного выше. Дляполного описания их конкретного воплощения необходимо указать:Количество очередей для процессов, находящихся в состоянииготовность. Алгоритм планирования, действующий между очередями.Алгоритмы планирования, действующие внутри очередей.Правила помещения родившегося процесса в одну из очередей.Правила перевода процессов из одной очереди в другую.Изменяя какой-либо из перечисленных пунктов, мы можемсущественно менять поведение вычислительной системы.Лекция окончена!Благодарю за внимание!40Системное и прикладноеПРОГРАММНОЕ ОБЕСПЕЧЕНИЕЛекция №3. Управление памятью.Гуськов Андрей Евгеньевичhttp://my.ict.nsc.ru/~guskov/courses/software/guskov (dog) ict.nsc.ru2008 г.1Лекция №3.
Содержание1.2.Принципы работы системы управленияпамятьюВиртуализация памяти2EMC Isilon, стенд, 16 петабайт (1015)Архитектура фон НейманаВычислительная машина должна запоминатьнекоторым образом не только цифровуюинформацию, необходимую для данноговычисления, но и промежуточные результатывычислений, а также и команды, управляющиеработой машины.Как сами данные, так икоманды машине необходимосвести к числовому коду,который должен хранитьсяв оперативной памяти иавтоматически распознаваться.Физическая организацияпамяти компьютераЗапоминающие устройства компьютера разделяют, какминимум, на два уровня: основную (главную,оперативную, физическую) и вторичную (внешнюю)память.Основная память представляет собой упорядоченныймассив однобайтовых ячеек, каждая из которыхимеет свой уникальный адрес (номер).Обычно основная память изготавливается с применениемполупроводниковых технологий и теряет своесодержимое при отключении питания.Физическая организацияпамяти компьютераВторичную память (это главным образом диски)также можно рассматривать как одномерноелинейное адресное пространство, состоящееиз последовательности байтов.В отличие от оперативной памяти, она являетсяэнергонезависимой, имеет существеннобольшую емкость и используется в качестверасширения основной памяти.Физическая организацияпамяти компьютераПринцип локальностиОказывается, при таком способе организации помере снижения скорости доступа к уровнюпамяти снижается также и частота обращенийк нему.Ключевую роль здесь играет свойство реальныхпрограмм, в течение ограниченного отрезкавремени способных работать с небольшимнабором адресов памяти.
Это эмпирическинаблюдаемое свойство известно как принциплокальности или локализации обращений.Логическая памятьАппаратная организация памяти в виде линейногонабора ячеек не соответствует представлениямпрограммиста о том, как организовано хранениепрограмм и данных.Большинство программ представляет собой набормодулей, созданных независимо друг от друга. Иногдавсе модули, входящие в состав процесса,располагаются в памяти один за другим, образуялинейное пространство адресов.
Однако чаще модулипомещаются в разные области памяти и используютсяпо-разному.Схема управления памятью, поддерживающая этотвзгляд пользователя на то, как хранятся программы иданные, называется сегментацией.СегментацияСегмент – область памяти определенногоназначения, внутри которойподдерживается линейная адресация.Сегменты содержат процедуры, массивы,стек или скалярные величины, нообычно не содержат информациюсмешанного типа.Сегментная организацияпамятиЛогическое адресное пространство разделяется на сегменты.Каждый сегмент имеет имя, размер и другие параметры(уровень привилегий, разрешенные виды обращений, флагиприсутствия).Каждый сегмент – линейная последовательность адресов,начинающаяся с 0. Размер сегмента может менятьсядинамически (например, сегмент стека).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
