-Поиск по дневнику

Поиск сообщений в Ольга__Александровна

 -Подписка по e-mail

 

 -Статистика

Статистика LiveInternet.ru: показано количество хитов и посетителей
Создан: 13.01.2016
Записей: 43
Комментариев: 1
Написано: 43


многозадачность в случае изменяемых разделов. многозадачность в случае свопинга

Среда, 13 Января 2016 г. 06:44 + в цитатник

Многозадачность в случае изменяемых разделов. Разработчики ОС приняли к сведению проблемы, возникшие при эксплуатации систем с фиксированным размером разделов и решили, что можно позволить зада- чам занимать места столько, сколько они потребуют. Поэтому никаких границ реали- зовано не было. Напротив, задачам давалось стольком места, сколько они потребуют. Такая схема называется многозадачность с изменяемыми разделами. Обратите внимание, что мы все еще рассматриваем подход непрерывного раз- мещения – задача занимает соседние области хранилища. Если диспетчер ставит за- дачу на исполнение, она должна получить такой объем памяти, какой ей нужен. Од- нако, хотя причины фрагментации из-за фиксированных размеров разделов устране- ны, в каждом методе есть свои недостатки. В данном методе фрагментация возникает по иной причине. После завершения исполнения задача выгружается из хранилища и оставляет после себя дыру. Строго говоря, эта дыра может быть использована другими задачами, меньшими по размеру. Однако после этого дыра разделится на несколько дыр, меньших по размеру. Так мо- жет продолжаться достаточно долго, до тех пор, пока дыры не станут настолько малы, что не смогут вмещать задачи. Это приведет к резкому уменьшению произво- дительности системы.(схема15)

Объединение дыр. При завершении задачи в случае изменяемых разделов для устранения фрагментации памяти мы должны выполнить операцию объединения дыр. Она заключается в следующем. После выгрузки задачи следует проверить, гра- ничит ли высвобождаемое пространство с дырой. По результатам проверки мы мо- жем либо записать в список свободных областей новую дыру, либо изменить в уже существующей записи о дыре ее новые границы. Этот процесс показан на рисунке. Уплотнение хранилища. Однако даже после объединения дыр они, будучи рас- пределенными по хранилищу, покрывали существенный объем хранилища. Поэтому часто задачам не хватало непрерывного свободного объема памяти, хотя совокупный объем памяти в дырах значительно его превосходил. Для решения этой проблемы использовался метод уплотнения хранилища. Он заключался в перемещении всех задач так, чтобы все дыры оказались в одном конце хранилища (обычно в старшем). Таким образом получалась одна большая дыра вме- сто множества мелких. Такая методика иногда называется сборкой мусора и реализу- ется в языках с автоматическим управлением памятью. Система, выполняющая это действие, носит название мусорщика. Однако у данной методи- ки также есть недостатки: • активно потребляет ресурсы системы; • система в целом практиче- ски останавливается на вре- мя сборки мусора – чтобы эта операция успешно за- вершилась, ни одна задача не должна изменить состоя- ние памяти; • уплотнение требует перемещения задач в хранилище. Это означает, что в каждой задаче должна храниться вся информация об ее размещении; • если система активно работает с процессами, процесс уплотнения вызывается на- столько часто, что очень трудно превысить потери производительности. Стратегии размещения в хранилище. Для определения места в хранилище, в котором следует разместить программу, следует использовать стратегию выбора. Наиболее популярными стратегиями выбора в случае непрерывного размещения программ в памяти были: • Стратегия лучшего выбора – задача размещается в дыре в основном хранилище, в которой она оставляет наименьшее свободное место. Для большинства людей эта стратегия интуитивно кажется наилучшим выбором для реализации. • Стратегия первого выбора – задача размещается в первой дыре, достаточно большой для ее размещения. По сравнению с предыдущей стратегией она работает быстрее. • Стратегия худшего выбора – задача размещается в дыре, в которой она оставляет наибольшее свободное пространство. Звучит не очень разумно, однако по зрелом размышлении окажется, что это разумный выбор – в новой дыре, может быть, смо- жет разместиться другая задача. Однако в случае стратегии лучшего выбор это ма- ловероятно. Вариант стратегии первого выбора, называемый стратегией следующего выбо- ра, начинал поиск с точки, где остановился предыдущий поиск.

 

 

 

 

 

 

Многозадачность в случае свопинга. В каждом из методов, обсуждавшихся выше, программа оставалась в хранили- ще до своего завершения. Метод, называемый свопированием, или обменом, устра- няет это требование. В первых системах обмена задача занимала память целиком. Она исполнялась до тех пор, пока могла. После этого она останавливалась и целиком высвобождала процессор и основное хранилище, перемещаясь на вторичное хранилище. Другая за- дача перемещалась со вторичного хранилища в первичное и целиком занимала си- стему. То есть происходил обмен задачами. Как правило, до своего завершения зада- ча проходила такую процедуру много раз. В большинстве систем с разделением времени реализовывалась как раз такая методика. Она позволяла обеспечить разумное время отклика для нескольких поль- зователей, однако для большого количества пользователей требовалось что-то более изощренное. Более совершенные методы будут рассмотрены позднее. Однако дальнейшим совершенствованием этой методики была возможность об- разам задач оставаться в основном хранилище и осуществлять обмен не между пер- вичным и вторичным хранилищами, а между различными областями основного хра- нилища. 


многозадачность в случае фиксиров разделов

Среда, 13 Января 2016 г. 06:40 + в цитатник

Многозадачность в случае фиксированных разделов. Однако даже при использовании пакетного режима производительность одно- пользовательских систем была низкой. Это показано на рисунке Режим работы с активными вычислениями:(схема13)Режим работы с активным вводом-выводом:(схема14)Пока программа интенсивно считала, ресурсы ЭВМ не пропадали. Однако если программа активно выполняла операции ввода-вывода, машина существенную часть времени простаивала. Поэтому в целях повышения эффективности разработчики си- стемы приняли решение организовать многозадачность. Если программа ожидала за- вершения операции ввода-вывода, она могла передать управление другой програм- ме, готовой для выполнения вычислений, если, конечно, такая была в системе. Это позволяло одновременно выполнять операции ввода-вывода и вычисления, что су- щественно повысило производительность систем. Однако для обеспечения многозадачности следовало обеспечить присутствие нескольких программ в основном хранилище одновременно. Это было нужно для быстрого переключения между программами. В противном случае повышения бы- стродействия не было. Таким образом, многозадачность требует больше памяти. Од- нако эти затраты компенсируются ростом производительности.

Абсолютная трансляция и загрузка. Ранние многозадачные системы исполь- зовали фиксированные разделы. Память делилась на несколько разделов фиксиро- ванного размера. Каждый раздел мог быть одной занят задачей. Процессор быстро переключался между разделами для создания иллюзии одновременного выполнения программ. Задачи компилировались абсолютными компиляторами и ассемблерами. Это означало, что программы могли испол- няться только в «своих» разде- лах. Если раздел, нужный про- грамме был занят, она стави- лась в очередь ожидания этого раздела, даже если остальные разделы были свободны. Это влекло потерю производи- тельности, однако такая схема очень легко реализуется. Перемещающая трансляция и загрузка. Усовершенствованием абсолютной загрузки было перемещение задач. Перемещающие компиляторы, ассемблеры и за- грузчики создавали перемещаемые программы, которые могли быть размещены в любом достаточно большом свободном разделе. Этот метод уменьшал потери произ- водительности по сравнению с абсолютной компиляцией, однако вел к усложнению ПО. Для организации защиты в системах с фиксированными разделами использова- лись граничные регистры – при любой попытке выйти за пределы адресов, указан- ных в качестве нижней и верхней границы задачи срабатывала защита. Для получе- ния доступа к функциям ОС, которая находилась вне этой области, программа долж- на была пользоваться специальными системными вызовами. Данный подход моги привести к фрагментации памяти. Причиной этому могло послужить либо неполное занятие раздела задачей, либо слишком малый размер раз- дела. 


однопользовательское непрерывное распределение первичного хранилища

Среда, 13 Января 2016 г. 06:37 + в цитатник

Однопользовательское непрерывное распределение хранилища. Как уже говорилось, ранние системы позволяли единовременно работать только одному человеку. Поэтому все ресурсы машины были в его полном распоряжении. Учет использования ресурсов был прост – раз все ресурсы отданы кому-то, то этот кто-то их полностью оплачивает, независимо от того, работает ли его задача, или нет. В действительности, системы учета того времени были построены на подсчете обычного (плоского) затраченного времени системы. Пользователь того времени должен был реализовать все операции ввода-вывода самостоятельно. Это привело к возникновению IOCS, что и положило начало современным ОС. Такой подход к си- стеме позволял организовать распределение хранилища примерно таким образом:

схема(11)

Программы ограничивались объемом хранилища. Однако быстро разработали методику оверлеев для преодоления этого ограничения. Концепция оверлеев: (схема 12)

Если какая-то часть программы не нужна на протяжении всего периода выпол- нения процесса, то ее можно загружать и выгружать по мере необходимости. Посто- янное присутствие в основном хранилище требуется только тем данным и коду, ко- торые требуются на протяжении всего исполнения процесса. В примере выше в па- мяти постоянно находится часть кода и данных. Помимо прочего, код в памяти должен последовательно загружать, запускать и выгружать части программы: код ини- циализации, код обработки и код вывода. Эта методика позволяла преодолеть ограничения на объем основного хранили- ща, однако требовала от программиста длительного и тщательного планирования по разбиению программы на оверлеи. Кроме того, в программу, в полной мере исполь- зующую оверлеи, достаточно трудно вносить изменения. Поэтому реализация вирту- альных хранилищ вытеснила этот метод. Защита. При таком распределении хранилища пользователь получает полный доступ к главному хранилищу. В таком случае возникает вопрос: как защитить об- ласть, занимаемую ОС от пользователя. Если программа пользователя пойдет враз- нос, она способна повредить информацию или даже оборудование. В случае полного уничтожения ОС пользователь сможет понять, что что-то не так, и просто перезапу- стит систему. Однако как быть в случае «мягкой» порчи ОС. Например, случайного изменения кода функций ввода-вывода. В этом случае программа будет продолжать работать, однако в лучшем случае не будет выводиться ее результат, а в худшем произойдет порча данных в хранилищах. Защита может быть реализована с помощью специального ограничивающего регистра – он содержит адрес, ниже которого все запросы пользовательской про- граммы отвергаются. Для того, чтобы пользователь мог обращаться к функциям ОС, в таком случае реализовался механизм вызовов ее функций – т.н. системных вызо- вов. В них пользователь передавал действия, которые он хотел бы выполнить, и необходимые для этого параметры. По мере усложнения ОС механизм защиты также усложнялся. Однопотоковая пакетная обработка. Ранние однопользовательские системы занимались одной задачей дольше, чем она выполнялась. Перед исполнением задачи тратилось время на настойку системы – время загрузки ОС, установки магнитных лент и дисков, загрузки бумаги в принтер, считывания перфокарт и т.п. По заверше- нии задачи тратилось время на остановку системы – извлечение лент, дисков, бумаги из принтера, извлечение перфокарт и т.п. Во время загрузки и остановки системы компьютер в целом простаивал. Это вело к большим денежным потерям. Разработчики систем решили, что если удастся сократить время на переход между задачами (то есть время на остановку системы после одной задачи и время на загрузку системы перед другой задачей), то это уменьшит время простоя системы. Это привело, как мы уже говорили, к появлению пакетного режима работы. В одно- потоковой пакетной системе задачи формировались в пакеты – последовательность программ на перфокартах или ленте. Специальный процессор задач считывал ко- манды на специальном языке управления задачами и выполнял загрузку или оста- новку системы, а также запуск задач. Также он сообщал оператору ЭВМ о необходи- мых действиях. Это позволило автоматизировать действия, выполнявшиеся до этого вручную. По завершении задачи процессор задач выполнял очистку системы, а затем выполнял действия по переходу к следующей задаче. Именно процессоры обработки задач продемонстрировали необходимость управления ресурсами машины.  


стратегии управления хранилищами.непрерывное и прерывное размещение

Среда, 13 Января 2016 г. 06:31 + в цитатник

Стратегии управления хранилищами. Дорогими ресурсами для достижения оптимальной производительности следу- ет активно управлять. Таким образом, задачей при разработке стратегии использова- ния главного хранилища является достижения наилучшего использования этого ре- сурса. Стратегии можно разделить на категории. Стратегии получения определяют порядок получения следующей части инфор- мации из вторичного хранилища при ее извлечении из вторичного хранилища. Изна- чально применялось извлечение по требованию. В этом случае извлечение части ин- формации производилось по запросу от системы. В основе стратегии лежала идея о том, что в общем нельзя предугадать, какая именно информация потребуется систе- ме, поэтому потери от угадывания покроют возможный выигрыш от опережающего чтения. Однако в наше время широко применяется именно упреждающее получение. Стратегии размещения применяются при определении места размещения в хра- нилище полученной информации. В лекции мы рассмотрим стратегии «первое подо- шедшее», «лучшее подошедшее» и «худшее подошедшее». Стратегии замещения применяются для определения места в хранилище, кото- рое требуется освободить для размещения полученной части информации в храни- лище.

 

 

 

Непрерывное и прерывное распределение хранилищ. Ранние системы использовали непрерывное распределение хранилищ – каждая программа занимала один непрерывный блок в хранилище. Так было до разработки изменяемых разделов, которые продемонстрировали свою пользу в случае многоза- дачности. В прерывном распределении хранилищ программа размещается в несколь- ких сегментах памяти, не обязательно последовательных. Хотя для ОС труднее управлять таким распределением, это уравновешивается возникновением множества маленьких промежутков вместо одного большого, что позволяет убрать необходи- мость постоянного перемещения программ между первичным и вторичными храни- лищами. 


физ организация хранилищ.иерархия

Среда, 13 Января 2016 г. 06:30 + в цитатник

. Организация хранилищ. Так сложилось, что основное хранилище всегда являлось самым дорогим ресур- сом. Поэтому оно требовало повышенного внимания со стороны системных разра- ботчиков, пытающихся оптимизировать использование системой ресурсов. Хотя цена первичного хранилища сильно упала за последнее десятилетие, однако по срав- нению со вторичными хранилищами оно существенно дороже. Кроме того, совре- менные приложения также повысили свои требования к предоставляемым объемам этого ресурса. Под организацией хранилища мы подразумеваем точку зрения, с которой рассматривается главное хранилище. Будет ли к нему иметь доступ только один пользователь, или возможны несколько пользователей в одно время? Если возможно наличие нескольких процессов в памяти в одно время, выделять ли им одинаковый объем памяти, или выделять каждому процессу части хранилища, называемые разде- лами, разной длины? Будут ли разделы фиксированы по времени, или система может динамически управлять ими, подстраиваясь под потребности исполняемых задач? Будут ли процессы требовать от системы исполнения в конкретных разделах, или мы можем позволить системе самой распределять разделы процессам? Должны ли мы требовать исполнение процесса в непрерывной области памяти, состоящей из нескольких разделов, или процесс может быть размещен в любых свободных разде- лах? Далее рассмотрим некоторые из этих схем организации хранилища.

 

 

 

Иерархия хранилищ. В середине 50-ых и 60-ых основная память, обычно на магнитных сердечниках, была очень дорогой. Поэтому решение об общем объеме памяти в системе принима- лось очень тщательно. С одной стороны, не следовало покупать больше памяти для машины, чем было по карману. С другой стороны, объема памяти должно было хва- тать для выполнения ОС и задач определенного количества пользователей. Задачей было выбрать оптимум между бюджетом покупателя системы и потребностями пользователей системы. Программы и данные, которые нужны в данный момент, размещены в основном хранилище. Если они не нужны в данный момент, их можно хранить во вторичном хранилище. Если в хранящейся на вторичных хранилищах информации возникнет необходимость, ее можно загрузить в первичное хранилище. Вторичные хранилища стоят гораздо дешевле первичного, и обладают гораздо большей емкостью. Однако первичное хранилище гораздо дороже вторичного. Если система состоит из нескольких уровней хранилищ, большое значение име- ет метод перемещения информации между уровнями хранилища. Это перемещение требует системных ресурсов и выполняется часто. В результате в случае ошибок ди- зайнеров общая эффективность системы существенно снизится. В середине 60-ых годов было выяснено, что добавление к указанным выше двум уровням хранилищ третьего существенно повышает эффективность системы. Этот дополнительный уровень в иерархии хранилищ получил название кэш. Кэш – это объем памяти, еще более быстродействующий, чем основное хранилище. В ре- зультате кэш чрезвычайно дорогостоящ, что ведет к использованию относительно малых объемов кэш-памяти. На рисунке показана общепринятая иерархия хранилищ в общем случае: Время доступа к инфор- мации уменьшается Скорость доступа к ин- формации увеличивается Цена бита информации увеличивается Емкость уменьшается →Кэш ↑ ↓ Основное хранилище Процессор имеет непосредственный доступ к программам и данным ↑ ↓ Вторичное хранилище Программы и данные перед использованием должны быть перемещены в основное хранилище Кэш предназначен для хранения непосредственно исполняемых программ: перед исполнением программы перемещаются из основного хранилища в кэш. Там скорость их исполнения существенно превышает таковую в случае обычной памяти. Затем они возвращаются обратно в память. Основной задачей дизайнеров при такой иерархии является обеспечение превышения выигрыша от скорости исполнения программ в кэше над проигрышем от перемещения информации из памяти в кэш-па- мять. 

 

 


первичное хранилище

Среда, 13 Января 2016 г. 06:28 + в цитатник

Как правило, термины память и хранилища используются в качестве сино- нимов. Однако хранилище более емко и общепринято. Программы и данные должны быть размещены имеено в основном хранилище для их запуска или осуществления прямого доступа к ним.


методы выявления и выхода из взаимоблокировок

Среда, 13 Января 2016 г. 06:26 + в цитатник

Выявление взаимоблокировок. Главной задачей механизма выявления взаимоблокировок является выяснение существования замкнутого ожидания и, при наличии, процессов и ресурсов, в нее вовлеченных. Однако следует отметить, что перед нами снова встает вопрос – сопо- ставим ли выигрыш от устранения взаимоблокировок от проигрыша при проведении проверок на наличие взаимоблокировок? Пока оставим этот вопрос, и сосредото- чимся на алгоритме.

 

 

Выход из взаимоблокировки. В случае появление в системе взаимоблокировки ее можно разрешить путем устранения одного или нескольких необходимых условий. Обычно это ведет к по- тере одним или несколькими процессами рабочих данных. Это может оказаться при- емлемой платой по сравнению с потерями от сохранения взаимоблокировки в систе- ме. Возможность выхода из взаимоблокировки определяется следующими фактора- ми: • не сразу можно выяснить, что система содержит взаимоблокированные процессы; • в большинстве ОС неразвиты или отсутствуют службы, позволяющие приостано-вить процесс на неопределенное время, а затем восстановить его. Кроме того, в си- стеме присутствует большое количество процессов, например, т.н. процессы ре- ального времени, которые должны исполнятся непрерывно; • даже если такие службы присутствуют, они могут требовать квалифицированного оператора, которые редки даже в наши дни. Попытки разработать алгоритмы, поз- воляющие автоматически решать такие проблемы, к успеху не привели; • восстановление процессов после взаимоблокировки может потребовать много вре- мени. Так, восстановление после взаимного блокирования из нескольких сотен процессов потребовало пары дней труда операторов. В современных системах ситуация взаимоблокировки разрешается путем устра- нения процесса и возврата всех его процессов системе. Как правило, процесс теряет- ся безвозвратно, однако другие процессы могут продолжать работу. Иногда может понадобиться устранить несколько процессов. Строго говоря, термины «выход» и «разрешение» здесь не очень применимы – процессы приносятся в жертву к выгоде всех остальных процессов. Выбор процессов, убиваемых системой, обычно производиться по какой-то стратегии. Однако здесь есть свои сложности: • приоритет взаимоблокированных процессов равный, поэтому в выбор вовлекается оператор системы; • приоритет процессов может быть вычислен неверно (например, временное повы- шение приоритета у долго ждавшего процесса); • оптимальный выбор процесса для устранения может потребовать значительные усилия и ресурсы системы в ситуации, когда их не хватает. Таким образом, наилучшим методом устранения взаимоблокировок является метод приостановления/восстановления процессов, которые позволяли бы приоста- новку процессов с высвобождением их ресурсов без потери рабочих данных. Воз- можным компромиссом может служить понятие контрольной точки: многие ОС способны приостановить процесс, однако будут потеряны данные только начиная с последней контрольной точки.  


методы избегания взаимоблокировок

Среда, 13 Января 2016 г. 06:22 + в цитатник

Избежание взаимоблокировок. Алгоритм банкира. Если в системе присутствуют все четыре предпосылки для взаимоблокировки процессов, то, соблюдая осторожность при выделении процессов, можно попытаться избежать взаимоблокировок. Самым известным алгоритмом избегания взаимоблоки- ровок является алгоритм Дейкстры, известный как алгоритм банкира. Алгоритм был выведен как руководство к действию для банкира, выдающего ссуды и получающего прибыль от ограниченного капитала. Алгоритм банкира. Далее мы рассматриваем случай ресурсов одного типа. Алгоритм легко обобщается на случай набора ресурсов разных типов. Пусть общее ко- личество ресурсов равно r. Операционная система разделяет это фиксированное ко- личество ресурсов среди n задач. В начале каждая задача указывает максимальное количество ресурса, которое ей потребуется для завершения. Очевидно, что ОС при- нимает на исполнение только те задачи, максимальная потребность которых в ресур- се не превышает доступного системе вообще. Задача может получить или высвобо- дить занимаемые ресурсы. Если задача запросит дополнительный ресурс, она может быть поставлена на ожидание, но система гарантирует выделение ресурса за конеч- ное время. Общее количество ресурсов, выделенных задаче, не превысит указанного ей максимально необходимого количества. Если запросы задачи удовлетворены, она гарантирует возврат ресурсов системе за конечное время. Текущее состояние систе- мы называется безопасным, если она способна удовлетворить запросы задач за ко- нечное время. В противном случае это небезопасное состояние. Пусть loan(i) – это одолженные i задаче ресурсы, а max(i) – ее максимальная по- требность в ресурсах. Тогда claim(i) – количество ресурсов, необходимых задаче для успешного завершения. Очевидно, что claim(i) = max(i) – loan(i). Алгоритм банкира, предложенный Дейкстрой, требует проводить выделение ресурсов только для тех за- дач, которые находятся в безопасном состоянии. 

 

Эта таблица описывает систему с 12 единицами ресурса, 10 из которых выделе- ны задачам, а 2 свободны. Это состояние безопасно, потому что допускает успешное завершение всех трех задач. Система должна прежде выделить ресурсы задаче 2 – ей не хватает для завершения только 2 единиц ресурса. По завершении выполнения за- дачи 2 она высвободит 6 единиц ресурсов. Высвободившиеся ресурсы можно раз- дать задачам 1 и 3, которым в совокупности не хватает для успешного завершения как раз 6 единиц ресурсов. Пример небезопасного состояния. Рассмотрим другое состояние системы:

В этом состоянии системы видно, что ресурсов может не хватить для успешного завершения все трех задач. Стоит задаче 1 потребовать 1 единицу ресурсов, как воз- никнет трехпроцессная взаимоблокировка. Важно отметить, что небезопасное состояние не влечет обязательного возник- новения взаимоблокировки. Небезопасное состояние системы просто означает, что в случае неблагоприятного стечения обстоятельств в системе может появиться взаи- моблокировка. Пример перехода безопасного состояния к небезопасному. Если система на- ходится в данный момент в безопасном состоянии, это не означает, что ее будущие состояния также будут безопасными. Предположим, что система находилась в состо- янии 1 и задача 3 запросила дополнительный ресурс. Если ОС удовлетворит запрос, система перейдет в Это состояние небезопасно. Еще раз обратите внимание, что данное состояние вовсе не обязательно ведет к появлению взаимоблокировки процессов. Однако си- стема в таком состоянии не может гарантировать успешного завершения всех трех задач. Выделение ресурсов алгоритмом банкира. Таким образом, показан порядок выделения системой ресурсов по алгоритму банкира. Обратите внимание, что могут быть выполнены все четыре условия взаимоблокировки. Однако идея алгоритма со- стоит в том, чтобы запросы от задач, переводящие систему небезопасное состояние, отклонять, ставя такие процессы на ожидание. По мере высвобождения ресурсов за- вершившимися задачами запросы ожидающих процессов могут быть выполнены. Это означает, что за конечное (но, вообще говоря, заранее неизвестное время) систе- ма удовлетворит запросы всех задач. Недостатки алгоритма банкира. Несмотря на полное устранение взаимобло- кировок, этот алгоритм распределения ресурсов не лишен крупных недостатков: • алгоритм требует фиксированного количества ресурсов. Для большинства персо- нальных ЭВМ это не существенное ограничение, однако в случае возможности «горячей» замены ресурсов (памяти, винчестеров и т.д.) это важно; • алгоритм требует неизменного количества процессов. Однако в современных ОС это требование невыполнимо; • алгоритм гарантирует выделения ресурсов за конечное время. Однако на практике требуются более строгие гарантии. Особенно в случае систем реального времени; • алгоритм требует от задач гарантии возврата ресурсов за конечное время. На прак- тике это неприемлемо; • алгоритм требует от задач заранее определить максимальную потребность в ресур- се. На практике крайне трудно заранее знать максимальный объем потребных ре- сурсов. Гораздо полезнее на практике использовать динамическое выделение ре- сурсов «по потребностям».

 

 

 

(таблицы 1,2,3) 


методы предотвращения взаимоблокировок

Среда, 13 Января 2016 г. 06:17 + в цитатник

Предотвращение взаимоблокировок. Среди разработчиков систем наиболее популярна методика предотвращения взаимоблокировок. Далее мы рассмотрим несколько таких методов, а также рассмотрим их эффективность как с точки зрения пользователя, так и эффективности работы системы. Как уже отмечалось выше, если не выполнено хотя бы одно из условий разви- тия взаимоблокировки, она возникнуть не может. Поэтому возможны следующие стратегии для устранения взаимоблокировок в системе: • каждый процесс должен сразу запросить все ресурсы, необходимые ему для вы- полнения, и не должен продолжать исполнение, пока не получит все запрошенное; • если процессу, уже владеющими какими-то ресурсами, отказано в запросе на до- полнительное выделение ресурсов, то этот процесс должен освободить свои ресур- сы до удовлетворения запроса. После удовлетворения запроса он должен повторно запросить все необходимые ему ресурсы; • введение линейной упорядоченности типов ресурсов. То есть процесс, запросив- ший некие ресурсы, имеет право запросить в следующий раз только ресурсы млад- ших (или старших, зависит от упорядочивания) типов. Обратите внимание, что стратегий три, а не четыре. Каждая из них, как будет показано далее, устраняет одно условие. Дело в том, что условие взаимного исклю- чения мы устранить не можем. Устранение условия ожидания. Первая стратегия устранения взаимоблокиро- вок требует, чтобы процесс сразу запрашивал все необходимые ему ресурсы. ОС должна выделять их по принципу «все или ничего». Если ОС может выдать все запрошенное процессом, то она выделяет эти ресурсы и процесс продолжает выпол- няться. Иначе процесс должен дождаться возможности выделения ему всего запро- шенного в полном объеме. Однако в данном случае во время ожидания процесс не удерживает никакие ресурсы. Это значит, что условие ожидания устранено и взаи- моблокировки в системе возникнуть не могут. Однако, несмотря на простоту, эта стратегия ведет к настоящему разбазарива- нию ресурсов. Предположим, что программе требуется устройство записи дисков. Если это просто процесс записи дисков, то ничего страшного в этом нет: он все вре- мя своего исполнения использует это устройство для записи заранее подготовлен- ных данных. Но если это просто файловая оболочка, то тогда возникает проблема – все другие процессы не смогут прочитать данные на этой устройстве, и любой про- цесс, который обладает возможностью читать содержимое компакт-диска, долженбудет дождаться завершения файловой оболочки. Для устранения этого недостатка разработчики часто применяются методику деления программы на участки. Ресурсы разрешено выделять при входе на новый участок. В этом случае простой оборудования сокращается, однако возникает потеря производительности разрабатываемой системы, также как и возрастает ее слож- ность. Обратите внимание, что эта стратегия может привести к неопределенной за- держке процессов, поскольку процесс ожидает выделения запрошенных ему ресур- сов. Не факт, что они вообще освободятся. Устранение условия невытеснения. Вторая стратегия устраняет условие не- вытеснения. Предположим, что некая система позволяет процессам удерживать ре- сурсы во время ожидания дополнительно запрошенных ресурсов. До тех пор, пока оставшихся ресурсов хватает для выполнения запросов других процессов, все в по- рядке. Однако как только запрос еще одного процесса не может быть удовлетворен (причем эти ресурсы удерживаются ожидающим процессом), возникла взаимоблоки- ровка. Рассматриваемая стратегия требует, чтобы процесс при неудовлетворении запроса на дополнительное выделение ресурсов высвобождал все свои ресурсы на время ожидания. После удовлетворения запроса процесс должен запросить свои прежние ресурсы повторно. Явным недостатком такого подходя является возмож- ность потери части или всех данных при высвобождении ресурсов. Однако более важным является ответ на вопрос «Как часто это нужно делать?». Если такое дей- ствие выполняется процессом достаточно редко, то получено дешевое решение проблемы взаимоблокировок процесса. Однако в противном случае цена решения слишком велика, особенно с учетом наличия в системе высокоприоритетных и не- прерывных процессов. Другим серьезным недостатком данной стратегии является ее подверженность неопределенной задержке процессов. При выделении дополнительного ресурса про- цесс должен повторно запросить все свои ресурсы. Однако может так случиться, что другой процесс захватил их. В этом случае наш процесс опять будет ждать выполне- ния запроса (уже на свои исходные ресурсы), и так до бесконечности.Устранение условия замкнутого ожидания. Третья страте- гия направлена на устранение условия замкнутого ожидания. По- скольку все ресурсы пронумерованы и процесс может запраши- вать ресурсы только в линейном порядке, замыканию неоткуда взяться. Эта стратегия также реализуется в системах, но с опре- деленными затруднениями. • ресурсы запрашиваются по своему уникальному номеру. Номе- ра ресурсам назначаются при установке и настройке системы, и система должна жить с ними значительные промежутки време- ни. При добавлении ресурсов нового типа может потребоваться провести переобозначение устройств, перекомпиляция или даже переписывание ОС и ПО. • назначенные номера устройств должны отражать порядок их использования большинством задач. Если же выполняется зада- ча, использующая ресурсы не в предполагаемом порядке, то требуемые ресурсы она должна запросить сразу, что ведет к неэффективному их использованию. • одной из задач ОС является поддержание программной оболочки над оборудова- нием, маскирующем от пользователей все подробности о системе. Реализация этой стратегии устраняет возможность возникновения взаимоблокировок процессов, однако взамен на самый верхний уровень поднимается необходимость учета по- рядка следования ресурсов. Это усложняет работу пользователей системы по со- зданию ПО.


понятие о ресурсах системы.условия возникновения тупика

Среда, 13 Января 2016 г. 06:16 + в цитатник

Концепция ресурсов. Как уже упоминалось выше, ОС в первую очередь менеджер ресурсов. Она от- ветственна за выделение большого набора ресурсов различных типов. Именно раз- нообразие ресурсов делает ОС интересным объектом изучения. Ресурсы бывают вы- тесняемыми, например, процессор или основная память: программа, занимающая какую-то область памяти в данный момент, в следующий момент может быть вытес- нена оттуда другой программой. Пользовательская программа, долго ожидающая за- вершения запросов операций ввода-вывода не может эффективно в это время ис- пользовать память. Процессор, по-видимому, самый используемый вытесняемый ре- сурс из всех имеющихся в компьютере. Он должен постоянно и очень быстро переключаться между большим количеством процессов, исполняющихся в системе, для поддержания скорости выполнения этих процессов на приемлемом уровне. Если процесс в своем исполнении достигает такого момента, что он не способен далее эф- фективно использовать процессор, то контроль над процессором должен быть пере- дан другому процессу. Таким образом, вытеснение является важным свойством многозадачных систем. Некоторые ресурсы не вытесняемые и не могут быть переданы другому процес- су, если предыдущий процесс их не освободил. К подобным ресурсам можно отне- сти накопитель на магнитной ленте, устройство записи оптических дисков или прин- тер. Ресурсы могут разделяться между несколькими процессами или быть выделены только одному процессу. Например, винчестеры могут выделяться только одному процессу, а могут содержать файлы различных процессов. Память и процессор раз- деляются между многими процессами; процессор, который единовременно принад- лежит только одному процессу, за счет быстрого переключения между процессами создает иллюзию разделения. Данные и программы также являются важным видом ресурса, который требует выделения, учета и контроля. Например, в многозадачных многопользовательских системах множество пользователей может одновременно использовать один и тот жетекстовый редактор. Если каждому пользователю запустить индивидуальную копию этого редактора, это будет напрасной тратой памяти. Вместо этого следует использо- вать одну копию редактора, которая будет работать с разными наборами данных, по одному для каждого пользователя. Однако в этой ситуации редактор должен быть на- писан таким образом, чтобы его машинный код не изменялся во время выполнения. Такие программы называются перегружаемыми. Если код программы меняется во время выполнения, но каждый раз при запуске инициализируется, то такие програм- мы называются последовательно загружаемыми. Перегружаемые программы могут разделяться между несколькими процессами одновременно. Последовательно пере- гружаемые программы процесс может использовать только в виде своей личной ко- пии. Когда мы говорим о ресурсе, что он разделяемый, это означает что он может быть использован несколькими процессами одновременно. Процессы используют такой ресурс либо вместе, либо по одному за раз. Именно последний вариант ис- пользования и способствует возникновению ситуаций взаимоблокировки.

 

 

 

 

 

Четыре необходимых условия тупика. Для возникновения взаимоблокировки требуется выполнение следующих четырех необходимых условий: • процессы захватывают эксклюзивный контроль над ресурсами, которые они полу- чают (условие взаимного исключения); • процессы удерживают полученные ресурсы во время ожидания дополнительно запрошенных ресурсов (условие ожидания); • ресурсы не могут быть затребованы от удерживающего процесса до тех пор, пока он не завершит работу с ними (условие невытеснения); • существует цепь процессов, в которых каждый процесс удерживает ресурсы и ожидает освобождения ресурсов другим процессом в этой цепи (условие замкну- того ожидания). Эти условия необходимы, то есть при наличии взаимоблокировки все они вы- полняются. Как будет показано позднее, на этом основании строятся методы предот- вращения взаимоблокировок. Интересен вопрос, являются ли эти условия достаточными? То есть, если эти условия выполнены, произойдет ли взаимоблокировка? 


тупик и неопределенная задержка.примеры

Среда, 13 Января 2016 г. 06:14 + в цитатник

Говорят, что процесс зашел в тупик, если он ждет наступления определенного события, которое никогда не наступит.

 

Примеры тупиков. Тупики могут возникнуть по множеству причин. Например, если процессу дана задача ожидания какого-то события, причем в системе отсутствуют средства сигна- лизации о наступлении этого процесса, то в системе появился однопроцессый тупик. Тупики такого рода крайне трудно выявить. В большинстве реальных ситуаций тупики захватывают несколько процессов. Далее рассмотрим несколько примеров ту- пиковых ситуаций. Дорожный тупик. Начнем издалека. Всем вам наверняка знакома дорожная пробка. Однако в Волгограде пробки маленькие. Те, кто был в Москве или Петербур- ге, наверняка видели настоящую пробку – когда машины заблокировали обе полосы движения, и, будучи зажатыми такими же пробками по пересекающим эту дорогу улицам как впереди, так и сзади, будут стоять часами на одном месте. Для того, что- бы эта пробка исчезла, ГИБДД сначала разберет пробки на перекрестках с пересе- кающимися улицами, после чего движение успешно восстановится само. Простой ресурсный тупик. Большинство тупиков в системе возникает из-за т.н. последовательно выделяемых ресурсов (ресурсов, которые может использовать только один пользователь единовременно). Эта ситуация показана на рисунке: На этом графе выделения ресур- сов показаны два процесса в виде пря- моугольников и два ресурса в виде кругов. Стрелки от ресурса к процессу указывают, что ресурс принадлежит (был выделен) данному процессу. Стрелки от процесса к ресурсу пока- зывают, что процессом был послан запрос на выделение ресурса, однако выделения еще не произошло. Как нетрудно заметить, этот граф показывает систему в состоя- нии взаимной блокировки: процесс А держит ресурс 1 и ждет выделения ресурса 2; ресурс 2 принадлежит процессу В, который ждет выделения ресурса 1. Каждый про- цесс ждет высвобождения ресурсов, принадлежащих другому процессу, и оба не мо- гут освободить свой ресурс. Такое замкнутое ожидание является характеристиче- ской чертой тупика. Тупик спулера. Спулеры часто ответственны за развитие тупика. Многие си- стемы спулеров (в силу особенностей периферии) требуют, чтобы данные, которые программа посылает спулеру, были полностью сформированы перед тем, как спулер начнет работу с устройством вместо программы. Если вернуться к нашему примеру – спулеру печати – то для успешной работы PostScript принтеру требуется полно- стью сформированный PostScript-файл. Поэтому при одновременной на печатьнескольких больших документов возможна ситуация, когда место на винчестере за- кончится до того, как будет завершено формирование хотя бы одного документа (та- кие ситуации часто возникали в больших учреждениях с одним большим устрой- ством печати). Восстановление из такого тупика довольно просто, хотя и болезненно – это простой перезапуск спулера (а вовсе не всей ОС). Однако все нераспечатанные данные, скорее всего, будут потеряны. Если оператор сохранил контроль над систе- мой, то он, скорее всего, просто вручную снимет с печати пару задач, чтобы спулер смог распечатать остальные документы. Размеры файлов спулеров можно задать при настройке системы. Как показала практика, жестко регламентировать этот раздел в бинарных файлах нецелесообраз- но. «Жадным» вариантом устранения таких тупиков может быть выделение места под файлы спулеров на порядок больше, чем по всем прикидкам может понадобить- ся. Более разумным решением является построение спулера таким образом, чтобы он не принимал данные от программ в случае, если уже данные ему задачи превос- ходят некий критический объем, например, 75% от доступного спулеру про- странства. Это несколько ухудшит систему с точки зрения пользователей, однако од- новременно с этим резко уменьшится и риск взаимоблокировки. Современные спулеры достаточно умны, чтобы самостоятельно избегать тупи- ков, используя при этом лучшие алгоритмы, чем приведенные здесь. 

 

 

 

Неопределенная задержка. Ранее мы уже рассматривали проблему неопределенной задержки. С точки зре- ния взаимоблокировки, это частный вид тупика: процесс запросил доступ к какому- то ресурсу, однако в силу недостатков системной политики выделения ресурсов он находится в состоянии ожидания, в то время как остальные процессы продолжают нормально исполняться. В ОС с разделением процессов по приоритету это часто возникает вследствие постоянных запросов на ресурс от процессов с более высоким, чем у ожидающего, приоритетом. Для решения такой ситуации во многие системы введено понятие возраста процесса: время в ожидании. Приоритет процесса тогда определяется на основании его начального приоритета и возраста. Таким образом, наступает такой момент, когда эффективный приоритет долго ожидавшего процесса окажется выше, чем у процессов, запросивших ресурс в данный момент.Формально эта проблема исследована в теории очередей, которая будет рассмотрена позднее.


методы диспетчеризации:многоуровневая очередь....

Среда, 13 Января 2016 г. 06:09 + в цитатник

SJF диспетчеризация. Это невытесняющая политика, при которой направляется на исполнение про- цесс или задача с наименьшим ожидаемым временем завершения (Shortest Job First). Эта политика уменьшает время ожидания задач по сравнению с FIFO. Од- нако предсказуемость этой политики по сравнению с FIFO ухудшается. SJF отдает предпочтение коротким задачам. То есть она выбирает задачи таким образом, что- бы выбранная на исполнение задача завершилась как можно быстрее. Это мини- мизирует время простоя задач в очереди. Однако очевидной проблемой SJF является то, что требуется знать точное время завершения задачи. А эта информация не всегда доступна. Поэтому SJF предполагает, что пользователь сообщит примерное время работы задачи. В слу- чае промышленной эксплуатации, когда известно среднее время выполнения зада- чи, пользователь способен дать эти сведения. Однако в случае исследовательских работ, когда точное время завершения работы неизвестно в принципе, пользова- тель может только предполагать. В результате в худшем случае политика SJF све- дется к политике FIFO. Однако в этой политике можно предусмотреть механизм защиты от злонамеренного занижения времени исполнения задачи. Например, если задача выполняется намного дольше указанного пользователем времени, ее можно приостановить, а возобновить при наличии свободных ресурсов.

 

 

 

. SRT диспетчеризация. Эта политика является вытесняющим аналогом SJF. Она ставит на исполне- ние задачу с наименьшим временем, оставшимся до завершения (Shortest Remaining Time, SRT). В отличие от SJF в SRT исполняющийся в данный момент процесс может быть вытеснен возникшим процессом с меньшим временем до за- вершения. Однако, как и в случае SJF, пользователь должен сообщить системе примерное время на выполнение процесса. SRT имеет большие накладные расходы по сравнению с SJF. Это связано с вытесняемым характером системы. К ее достоинствам следует отнести то, что за- дачи с малым временем исполнения ставятся на исполнение практически сразу. Однако длительные задачи будут ждать и исполняться дольше. Таким образом, эта политика оказывает предпочтение коротким задачам. При реализации SRT следует решить одну задачу. Предположим, что длинная задача почти завершилась. Однако в этот момент возникает задача с очень ко- ротким сроком исполнения. Следует ли SRT вытеснить длинную задачу короткой, и не произойдет ли в этом случае потери в связи двойной сменой контекста про- цесса. Эту проблему можно решить путем введения нижнего предела – задачи, ко- торым осталось исполняться меньше этой величины, не вытесняются. Аналогич- ную задачу следует решить для случая, когда к SRT поступает новая задача, лишь ненамного короче исполняемой. Эти ситуации – пример того, что разработчик ОС должен тщательно сбалан- сировать все накладные расходы с возможным выигрышем. Причем не следует за- бывать о том, что усложнение механизма диспетчеризации также повышает на- кладные расходы.

 

 

 

HRN диспетчеризация. Невытесняющая стратегия HRN является модификацией стратегии SJF, кото- рая позволяет уменьшить время простоя длинных задач в очереди на ожидание. В этой стратегии приоритет процесса динамически меняется по формуле вида (вре- мя исполнения + время ожидания) / время исполнения. Чем дольше задача стоит в очереди ожидания, тем выше ее приоритет.

 

 

Многоуровневые очереди. Когда процесс впервые отправляется на исполнение на процессор, диспетчер не может предположить, какое именно процессорное время потребит этот про- цесс. Интерактивные процессы используют процессор короткое время, а затем ге- нерируют запрос на операцию ввода-вывод. Вычислительные процессы могут за- нимать процессор часами в случае невытесняющей диспетчеризации. Таким образом, механизм диспетчеризации должен: • предпочитать короткие задачи; • предпочитать интерактивные задачи для обеспечения нормальной загрузки устройств ввода-вывода; • определять суть процесса так быстро, как только можно и организовывать его диспетчеризацию соответственно. Механизм многоуровневых очередей решает эти вопросы путем ввода особой структуры: Новый процесс поступает в начало очереди первого уровня. Он движется по стеку FIFO, пока не попадает на процессор. Затем он либо завершается, либо вытесняется в очередь второго уровня как в связи с окончанием кванта, так и в связи с его блоки- ровкой. Это повторяется до тех пор, пока процесс либо не завер- шится, либо не достигнет самого нижнего уровня, на котором реализована какая- то иная политика, например, RR. Во многих многоуровневых очередях величина кванта по мере его движения вниз возрастает. Однако одновременно по мере сни- жения он реже передается на исполнение, поскольку процессам из верхних уров- ней нашей системы предоставляется приоритет над процессами из нижних уров- ней. Обычно процессы из нижних уровней запускаются только при отсутствии процессов в верхних уровнях. Также возможно вытеснение процессов из нижнего уровня новым процессом из верхнего уровня. Рассмотрим работу этого механизма на примере процессов различного типа. Интерактивный процесс попадет в очередь первого уровня, дойдет до процессора. Во время исполнения он с очень большой долей вероятности заблокируется и по- кинет очередь на исполнение. Таким образом, интерактивным процессам оказы- вается повышенное внимание. Теперь рассмотрим вычислительный процесс. Он также попадет на процессор из первой очереди. Однако он, в отличии от интерак- тивного процесса, будет вытеснен по истечении кванта времени. Затем он перейдет в очередь следующего уровня. И так далее. По мере спуска процессу бу- дет даваться все больший квант времени, который будет им полностью использо- ваться. В конце-концов вычислительный процесс дойдет до очереди нижнего уровня, где и останется до завершения. Система многоуровневых очередей идеальна для разделения процессов на группы по потребности в процессорном времени. Например, каждый раз, когда процесс уходит из нашей очереди на исполнение (например, в связи с блокиров- кой или в связи с завершением), он может быть помечен уровнем очереди, откуда он вышел. При следующем попадании в очередь на исполнение процесс можно сразу переместить на этот уровень. Это решение диспетчера опирается на эври- стику о схожести поведения процесса во время разных запусков. Это позволит вычислительному процессу сразу оказаться на нижнем уровне иерархии в обход верхних, где он будет мешать работе интерактивных процессов. Однако это поме- шает системе отреагировать на изменение в поведении процессов, например, в преобразовании вычислительного процесса в интерактивный. Эту проблему мож- но решить, если помещать процесс не на прежний уровень, а на один уровень вы- ше. Многоуровневые очереди – хороший пример адаптивного механизма. В от- личие от неадаптивного, он реализует изменение контроля системы в зависимо- сти от характера процессов. Как правило, адаптивные механизмы требуют повы- шенных накладных расходов по сравнению с неадаптивными. Однако это компен- сируется улучшенным поведением системы. Очевидным улучшением является организация очередей RR вместо FIFO. Это позволит процессу совершить несколько циклов на одном уровне, прежде чем опуститься на следующий. Как правило, количество циклов возрастает по мере увеличения уровня.  


методы диспетчеризации:по сроку....

Среда, 13 Января 2016 г. 06:06 + в цитатник

Диспетчеризация по сроку. При таком виде диспетчеризации некоторые задачи должны быть завершены к определенному времени. Эти задачи имеют высокую цену до срока и бессмыс- ленны после него. Как правило, такой вид диспетчеризации достаточно сложен: • пользователь должен предоставить точные требования задачи к ресурсам. Это требование обычно невыполнимо; • система должна исполнять такую задачу без существенного ущерба для задач остальных пользователей; • до завершения срока исполнения такой задачи система должна тщательно пла- нировать все распределение ресурсов. Это очень трудно реализовать; • если в системе может быть активными несколько задач со сроком завершения, то механизм диспетчеризации станет крайне сложным как в разработке, так и в реализации; • интенсивное управление ресурсами ведет к значительным накладным расходам. В результате общая производительность системы может существенно понизить- ся

 

 

FIFO диспетчеризация. Вероятно, самым простым принципом диспетчеризации служит принцип стека FIFO (First In First Out). Процессы направляются на исполнение в порядке их прибытия в очередь ожидания. Когда процесс был направлен на исполнение, он занимает процессор до добровольного высвобождения. FIFO, таким образом, невытесняющая политика. Эта политика в целом честная, однако у нее есть некоторые нечестности: она заставляет длительные задачи ждать коротких задач, и важные задачи ждут неважных задач. Однако FIFO дает малое время отклика и поэтому, в отличии от других политик, хорошо предсказуема. Правда, она беспо- лезна в случае диспетчеризации интерактивных пользователей, поскольку не мо- жет предоставить им приемлемое время отклика. FIFO редко используется в ОС, однако она часто реализуется в других политиках как их составная часть. К при- меру, системы могут применять разные методы для процессов с разными приори- тетами и назначением, но внутри каждой такой группы будет применяться FIFO.

 

 

 

RR диспетчеризация. Диспетчеризация по методу круговой подписи (Round Robin) аналогична FIFO, однако это вытесняющая политика. Если процесс не освободил процессор добровольно до истечения кванта времени, он снимается с процессора и ставится в конец очереди на исполнение. Эта политика обеспечивает хорошее время отклика, и при этом реализауется при малых накладных расходах. Однако ей требуется хорошая реализация переключения контекста процессов, и достаточный объем основного хранилища. Был предложен вариант политики RR, в котором введена очередь на удержа- ние задачи. Процесс сначала попадает в очередь на удержание. Там его эффектив- ный приоритет растет, пока не достигает нижней границы. После этого он попа- дает в очередь на исполнение, где его приоритет также постепенно растет, хотя и с меньшей скоростью.


вытесняющая и невытесняющая диспетчеризация.приоритеты.

Среда, 13 Января 2016 г. 06:05 + в цитатник

Вытесняющая и невытесняющая диспетчеризация. Диспетчеризация называется невытесняемой, если процессор, отданный про- цессу, не может быть затребован обратно. В противном случае диспетчеризация называется вытесняемой. Вытесняемая диспетчеризация полезна в системах, в которых процессы с вы- соким приоритетом требуют быстрой реакции системы. Так, потеря прерывания в системе реального времени будет катастрофической. Однако вытеснение требует накладных расходов – на переключение контекста задачи. Для повышения ее эф- фективности в основном хранилище следует держать много процессов, что также увеличивает накладные расходы.В невытесняющих системах короткие задачи вынуждены ждать длинные за- дачи, однако отношение ко всем процессам более честное. Время отклика систе- мы более предсказуемое, поскольку высокоуровневые процессу не могут суще- ственно изменить время работы низкоуровневых процессов. При разработке вытесняющего механизма диспетчеризации требуется тща- тельно проработать практически все схемы приоритетов. Поскольку мы можем построить очень сложный механизм, который в итоге окажется бессмысленным из-за непродуманного назначения приоритетов процессам.

 

 

 

Приоритеты. Приоритеты могут назначаться процессам автоматически самой системой, или устанавливаться извне. Они могут быть достигнуты или присвоены. Они мо- гут быть статическими или динамическими. Они могут назначаться по каким-то соображениям, или они могут назначаться случайно. Статические приоритеты не изменяются с течением времени. Такие приори- теты легко реализуются и не ведут к чрезмерным накладным расходам. Однако они неспособны реагировать на необходимость изменения приоритетов процес- сов в ходе их исполнения. Динамические приоритеты, напротив, способны реагировать. Начальный приоритет, установленный при запуске процесса, сохранится лишь какое-то время, после чего он изменится на более подходящее системе значение. Такая схема более сложна в реализации и обладает повышенными накладными расходами. Но в то же время проигрыш может компенсироваться в дальнейшем повышением эф- фективности исполнения процессов системой. С другой стороны, операционная система должна обслуживать большое ко- личество различных пользователей. К некоторым из них должно быть особое от- ношение. Пользователь со срочным заданием может получить какие-то привиле- гии, то есть приобретенный приоритет (причем он может быть приобретенным в самом прямом смысле слова). Однако это означает, что этот пользователь оттянет на себя часть ресурсов системы. Без ограничений все пользователи могли бы по- требовать предоставления себе повышенного приоритета.


понятие диспетчера процессов. уровни диспетчеризации,задачи и критерии диспетчеризации.

Среда, 13 Января 2016 г. 06:03 + в цитатник

проблемы, возникающие при определении, как и когда следует назна- чить процессу процессор. Это называется диспетчеризацией процессов.

 

 

Уровни диспетчеризации. Различают три уровня диспетчеризации: • высокоуровневая диспетчеризация – иногда называется диспетчеризация задач. Опреде- ляет, какой задаче разрешено активно со- ревноваться за контроль над ресурсами си- стемы. Если задача получила одобрение, она становится процессом или группой процес- сов в системе. • среднеуровневая диспетчеризация – опреде- ляет, какой процесс должен получить доступ к процессору. Диспетчер среднего уровня ре- агирует на изменения в нагрузке системы приостановкой и возобновлением процессов системы для сохранения возможности выпол- нять системные задачи. Таким образом, это буфер между разрешением задачи выполняться и назначением процессора этим задачам. • низкоуровневая диспетчеризация – определяет, какой из готовых к исполнению процессов следует отправить на процессор для исполнения, и направляет про- цесс на процессор. Этот уровень выполняется диспетчером. Диспетчер выпол- няется много раз в секунду, поэтому он всегда должен оставаться в основном хранилище системы. В этой лекции мы рассмотрим различные политики диспетчеризации, а так- же механизмы их реализации. Некоторые из этих политик подходят как для задач, так и для процессов.

 

 

 

Задачи диспетчеризации. При разработке диспетчеризации должны приниматься во внимание множе- ство задач. Среди них: • честность – диспетчеризация честная, если все процессы рассматриваются оди- наково, и ни один из процессов не попадет в состояние неопределенной задерж- ки; • максимизация выхода – диспетчеризация должна вести к обслуживанию как можно большего количества процессов за единицу времени; • уменьшение времени отклика – пользователь не должен долго ждать реакции системы на свои действия; • предсказуемость – одинаковая задача должна выполняться за примерно одина- ковое время или за примерно одинаковую цену каждый раз, независимо от за- грузки системы (с учетом количества запущенных процессов); • минимизация накладных расходов – характерно, что это не рассматривается в качестве основных задач. Обычно накладные расходы рассматриваются как бес- цельный расход ресурсов. Однако возможно направить часть ресурсов системы на накладные расходы и тем самым повысить производительность системы; • сбалансированность использования ресурсов – механизм диспетчеризации дол- жен поддерживать загрузку всех ресурсов системы. Поэтому должно быть пред- почтение процессам, использующим незагруженные ресурсы; • достижение баланса между откликом и загрузкой системы – наилучший вариант гарантировать приемлемый отклик системы – это не использовать часть ресур- сов с тем, чтобы они были свободны при необходимости. Однако это ведет к не- эффективному использованию ресурсов системы в целом. Хотя в системах ре- ального времени важен именно быстрый отклик, в других видах систем следует придерживаться баланса между откликом и стоимостью системы. • избегать неопределенной задержки – во многих случаях неопределенная за- держка также плоха, как и взаимоблокировка процессов. Избежать такой ситуа- ции можно с помощью введения возраста процесса – то есть роста приоритета процесса по мере ожидания им ресурсов. Приоритет процесса рано или поздно возрастет настолько, что процесс будет отправлен на исполнение. • ведение приоритетов – механизм диспетчеризации должен предпочитать про- цессы с высокими приоритетами. • отдавать предпочтение процессам, удерживающим важные ресурсы – даже низ- коприоритетный процесс может получить важный ресурс в свое распоряжение. В этом случае такой процесс должен обслуживать наравне с процессами более высокого приоритета для скорейшего освобождения ресурса. Если ресурс невы- тесняемый, то механизм диспетчеризации должен уделить процессу особое вни- мание. • предоставлять лучшее обслуживание процессам с желательным поведением (например, низким уровнем смены страниц) • не проседать под большой нагрузкой – механизм диспетчеризации не должен коллапсировать под тяжелой нагрузкой. Он должен либо предотвратить такую ситуацию отказом в создании новых процессов, либо снизить уровень обслужи- вания всех процессов системы. Большинство этих задач конфликтуют друг с другом, что делает разработку механизма диспетчеризации сложной задачей.

 

 

 

. Критерии диспетчеризации. Для решения задач диспетчеризации этот механизм ОС должен соблюдать: • ограничения ввода-вывода процесса – когда процесс получил в свое распоряже- ние процессор, должен ли он какое-то время использовать процессор перед ге- нерацией запроса на ввод-вывод? • процессорные ограничения процесса – когда процесс получил в свое распоря- жение процессор, должен ли он использовать процесс весь квант времени? • является процесс интерактивным или нет – интерактивный процесс генерирует «простые» запросы, но требует быстрого времени отклика системы, в то время как неинтерактивный процесс генерирует «сложные» запросы, но некритичен к времени отклика системы. • насколько важен быстрый отклик – исполняемый в полночь неинтерактивный процесс не требует немедленной реакции системы. Однако процесс мониторин- га процесса переработки нефти требует немедленного отклика системы незави- симо от времени суток. • Приоритет процессов – процессы с высоким приоритетом должны получать преимущество перед процессами с низким приоритетом. • частоту генерации процессом промахов страниц – если процесс редко генериру- ет исключения доступа к странице, то он, скорее всего, собрал свой рабочий на- бор в основном хранилище. Процессы, часто генерирующие промахи, находятся в процесс сбора своего набора. Имеет смысл давать таким процессам больше процессорного времени, поскольку они занимают процессор на короткое время перед генерацией запроса на операцию ввода-вывода (чтение страницы). • как часто процесс вытесняется другим, высокоуровневым процессом – если процесс часто вытесняется другими процессами, то ему следует выделять ма- лое количество процессорного времени, поскольку каждое переключение про- цессов требует накладных расходов, а вытесняемый процесс в итоге работает малое количество времени. • сколько реально процессорного времени получил процесс – многие разработчи- ки полагают, что процессам с малым эффективным процессорным временем следует давать предпочтение. Другие, напротив, полагают, что процессы с большим эффективным процессорным времени могут завершиться в бли- жайшем будущем, поэтому выгодно дать им поскорее завершиться. • сколько процессу требуется времени на завершение – если процесс завершится быстро, то общее время работы всех процессов уменьшится, если такие процес- сы пропустить вперед.


загрузка по требованию и опережающая загрузка.выгрузка страниц.размер страниц

Среда, 13 Января 2016 г. 05:59 + в цитатник

Загрузка по требованию. Очевидно, что страницы процесса должны загружаться в первичное храни- лище не позднее, чем произошла ссылка на них. Однако можно принять страте- гию загрузки страниц по требованию – ни одна страница не должна переместить- ся из вторичного в первичное требование без явной ссылки на нее. Причины для принятия такой стратегии могут быть следующие: • Известно, что точный путь исполнения программы, ее трассу, точно пресказать нельзя. Таким образом, любая попытка заранее загрузить страницу в надежде,что она окажется полезной, обречена на провал. • Загрузка страниц по требованию гарантирует, что в памяти окажутся только те страницы, которые действительно используются. • Нет никаких затрат ресурсов на определение тех страниц, что нужно загрузить в память. В то время как стратегии упреждающей загрузки тратят ресуры на предсказание. Однако у стратегии загрузки по требованию есть и свои недостатки. Предпо- ложим, что процесс выполняется последовательно, и ссылка на новые страницы происходит по порядку, но по одной за раз. Тогда при каждой ссылке на новую страницу процесс будет ждать ее загрузки. Затраты ресурсов могут стать доста- точно велики по мере увеличения количества страниц процесса. Эта ситуация характеризуется постоянным ростом результата произведения пространства процесса на время использования этого пространства процессом. Уменьшение этой величины за счет сокращения времени ожидания процессом своих страниц является главной задачей стратегии загрузки страниц. Очевидно, что загрузка страниц по требованию это не решает.

 

Опережающая загрузка. Основной концепцией в управлении ресурсами системы является идея о том, что цена ресурса напрямую определяет интенсивность управления им. Поскольку цена оборудования падает уже много лет, приходится принимать во внимание от- носительную стоимость машинного часа и человека-часа. Поэтому основная зада- ча разработчиков в наше время – это сократить время простоя человека, работаю- щего с системой. Опережающая загрузка – это один из методов решения задачи уменьшения времени отклика системы. При такой стратегии ОС пытается предсказать, какие страницы могут пона- добиться процессу в ближайшем будущем, и загружает их предварительно при условии наличия свободного места в основном хранилище. Если система угадала верно, то время выполнения процесса существенно уменьшается. В то время, как процесс выполняет загруженные ранее страницы, система продолжит угадывание. Некоторые ОС пользуются свойством пространственной локальности для осуществления предсказания – при загрузке страницы по требованию они подгру- жают сразу несколько страниц, соседних с требуемой. Стратегия опережающей загрузки имеет целый ряд преимуществ: • Если было сделано верное предположение в большинстве случаев, выигрыш в скорости выполнения процесса покрывает с лихвой все затраты на предсказа- ние. Поэтому механизмы предсказания имеет смысл использовать, даже несмот- ря на невозможность достижения 100% точности. • Часто можно принять несколько точных решений. Если принять решение, реа- лизуемое с наименьшими затратами, то выполнение этого процесса ускорится без существенных затрат. • С учетом удешевления оборудования последствия неверного предсказания ста- новятся менее серьезными. Мы просто потратим больше места в памяти зря.

 

 

Выгрузка страниц. В описанных выше методиках загрузки страниц ясно, что неиспользуемые процессом страницы какое-то время еще будут оставаться в памяти системы. За- тем система принудительно выгрузит их во вторичное хранилище. Если пользователь знает, что какая-то страница ему больше не понадобится, он может выгрузить ее добровольно с помощью команды выгрузки страницы. Это позволит уменьшить расход пространства и времени. Проблема в том, что пользо- ватель, как правило, либо не знает, что такое страница вообще, либо просто не знает, какая именно страница процесса не нужна в данный момент. Внедрение в программы команд выгрузки страниц способно существенно замедлить их выпол- нение, поскольку возможно нарушение работы механизма выгрузки страниц ОС. Единственным вариантом разрешения этой проблемы является как можно более быстрое обнаружение неиспользуемой или высвобождаемой страницы и ее последующая выгрузка.

 

 

Размер страниц. При страничной организации виртуального хранилища выбор размера стра- ницы достаточно важен. Каким должен быть размер страницы? Нужно ли исполь- зовать несколько разных размеров страниц? Если да, то нужно ли делать размер больших страниц кратным размерам меньших? К сожалению, общего ответа на эти вопросы дать невозможно. Требуется детально знать возможности оборудова- ния, ПО и предполагаемых приложений системы. Однако можно сформулировать несколько рекомендаций: • Чем меньше размер страницы, тем больше будет кадров страниц в памяти си- стемы и тем больше будет таблица трансляции страниц. Если система хранит таблицу в первичной памяти, это означает желательность больших размеров страниц. Однако при чрезмерно большом размере будет происходит потеря па- мяти. Правда, это соображение не очень существенно из-за дешевой памяти в наше время. • Если размер страницы велик, она будет оставаться в памяти из-за небольшого объема информации, на который будут происходить ссылки. Это ведет к умень- шению размера страницы. • При выполнении операций ввода-вывода мы бы хотели минимизировать коли- чество прерываний. Это означает, что под буфер мы должны отводить больше места. То есть размер страницы следует увеличивать. • Программы проявляются пространственную локальность в достаточно малом диапазоне адресов. Поэтому малые размеры страницы позволяют сформировать достаточно точный и малый рабочий набор. • Поскольку данные и код редко занимают целое количество страниц, при стра- ничной организации наблюдается внутренняя фрагментация памяти. Чем мень- ше размер страниц, тем меньше потери памяти. На практике было выявлено, что все-таки при меньших размерах страницы эффективность системы выше. Большинство систем тяготеют к размеру страницы в 4К. Конечно, в будущем с удешевлением памяти размер страницы может возра- сти до 1Мб или 1Гб.


принцип локальности.рабочие наборы процесс.частота промахов

Среда, 13 Января 2016 г. 05:56 + в цитатник

Локальность. Основой для большинства стратегий управления хранилищем является кон- цепция локальности – ссылки процесса на хранилище происходят по неоднород- ной, но сильно локализованной последовательности. Локальность может проявляться как в пространстве, так и во времени. Вре- менная локальность характеризуется по времени. Так, если было солнечно в 15:00, то с высокой степенью вероятности можно сказать, что было солнечно и в 14:30, и в 15:30. Пространственная локальность означает, что соседние элементы ведут себя схожим образом. По аналогии с временной локальностью можно ска- зать, что если было солнечно у нас, то с высокой степень вероятности в этот мо- мент было солнечно и в 10 километрах от нас. Это свойство часто проявляется и в компьютерных системах. Однако это свойство скорее эмпирического, чем теоретического характера. Его выполнение нельзя гарантировать, но скорее всего оно будет выполняться. Например, при страничной организации хранилища мы можем утверждать, что процесс будет ча- сто ссылаться только на часть своих страницы, и что эти страницы скорее всего будут близко расположены друг к другу в адресном пространстве процесса. Обратите внимание, что мы не утверждаем отсутствия ссылок на другие страницы процесса. Мы утверждаем, что с высокой степенью вероятности про- цесс в течении какого-то промежутка времени будет ссылаться только на конкрет- ный набор своих страниц. Характер локальности определяется, как правило, характером данных или кода процесса. Так, временная локальность обычно наблюдается в случае: а) цикла; б) подпрограмм; в) стеков, списков, очередей; г) глобальных переменных для подсчета, суммирования и т.п. А пространственная локальность проявляется, как правило, в случае: а) просмотре массивов; б) последовательном выполнении кода; Локальность представляет интерес только по одной причине: программа мо- жет эффективно выполняться только в том случае, если все страницы из текущего набора локальности размещены в первичном хранилище. То есть, если мы знаем страницы, образующие локальность программы в данный момент, и загрузим их в первичное хранилище, процессу вряд ли потребуется подгружать другие страни- цы. Эта идея была подтверждена практикой. Признаком того, что в первичном хранилище находится не вся текущая локальность программы, служит факт роста количества промахов при поиске страницы в таблице трансляции страниц. Заме- тим, что этот принцип полностью идентичен тому, что и как происходит в кэше процессора.

 

Рабочие наборы. Деннинг разработал теорию рабочих наборов поведения программы. Рабо- чим набором называется набор страниц процесса, к которым происходит актив- ное обращение. Деннинг показал, что для эффективного выполнения программы ее рабочий набор должен находиться в первичном хранилище. Иначе произойдет процесс замусоривания, который заключается в активной загрузке и выгрузке страниц из первичного хранилища, что приведет к падению производительности. Удобным методом для устранения замусоривания является сохранение в первичном хранилище, например, половины виртуального пространства процесса. К сожалению подобные методы ведут к ограничению количества процессов, разме- щенных в памяти системы. Политика управления хранилищем рабочими наборами заключается в сохра- нении рабочих наборов активных процессов в первичном хранилище. Возможно, это будет за счет рабочих наборов неактивных процессов. Решение добавления процесса в набор активных процессов, особенно в случае новых процессов, часто должно приниматься на основе эвристик, поскольку в общем случае система не- способна предположить, как именно в будущем будет вести себя процесс. С формальной точки зрения рабочий набор страниц W(t, w) в момент време- ни t – это набор страниц, на которые ссылался процесс в промежуток времени ис- полнения [t-w, t]. Здесь w – это окно размер окна рабочего набора. Выбор пра- вильного значения размера окна – критически важный параметр, определяющий эффективность работы системы в целом. Обратите внимание, что рабочий набор процесса – это не истинный рабочий набор. Истинным рабочим набором процес- са называется такой набор страниц, который должен находиться в первичном хра- нилище для наиболее эффективного выполнения процесса. Мы в общем случае можем лишь надеяться, что, выбрав хороший рабочий набор, сумеем приблизить- ся к эффективности, достигаемой при истинном рабочем наборе. По мере выполнения процесса рабочие наборы изменяются. Иногда происхо- дит только добавление или удаление страниц. Иногда происходит полное измене- ние набора. Поэтому любые выводы и предположения о текущем рабочем наборе в общем случае нельзя распространить на следующие рабочие наборы (равно как и на наборы с другим размером окна). Это усложняет управление поведением хранилища. При всех попытках предсказать следующие рабочие наборы процесса следует учитывать возможность полного изменения рабочего набора. Однако с тем же успехом рабочий набор процесса может и не меняться вообще. Полная реализация теории рабочих наборов довольно сложна и ресурсоемка. Однако разработаны аппаратные решения по поддержке части функций. Также можно реализовать упрощенные варианты.

 

 

Замена страниц по частоте промахов. Одним из методов оценки того, находится ли рабочий набор процесса в па- мяти, является частота промахов. Если уровень промахов процесса достаточно ве- лик из-за малого количества страниц процесса в первичном хранилище, процесс может замусориться. С другой стороны, процессы практически без промахов со- держат все страницы в памяти, но это может означать, что в первичном хранили- ще системы находится лишние страницы процесса, вовсе не входящие в его рабо- чий набор. Это также замедляет работу системы. В идеале процесс должен гене- рировать количество промахов, расположенное где-то между этими двумя крайни- ми точками. Алгоритм частоты промахов страниц процесса (Page Fault Frequency, PFF) управляет размещенным набором страниц процесса (то есть теми страницами процесса, что загружены в память) исходя из частоты генерации исключений ошибок обращения. Возможен и другой вариант этого алгоритма – использовать промежутки времени между промахами хранилища. PFF проверяет количество промахов за промежуток времени. Если это коли- чество меньше, чем нижний параметр алгоритма, то все страницы, к которым не было обращения за промежуток времени, исключаются из размещенного набора. Если больше, чем верхний параметр, то все страницы, загруженные за промежу- ток времени в память, включаются в набор. Аналогично можно описать и вариант с временем. Достоинство этого алгоритма в том, что он динамически подстраивает набор страниц процесса под текущее поведение программы. Если процесс переключил- ся на больший рабочий набор, PFF даст ему требуемое пространство. Если рабо- чий набор процесса уменьшился, PFF освободит неиспользуемые в данный мо- мент процессом страничные кадры. Достоинство PFF заключается в том, что в от- личие от рабочих наборов он должен выполнять действие только после промаха процесса, вместо простого обращения. Однако выбор параметров PFF является самостоятельно задачей, решение которой способно существенно повлиять на эф- фективность всей системы.


стратегии управления виртуальными хранилищами.стратегии замены страниц

Среда, 13 Января 2016 г. 05:52 + в цитатник

. Стратегии управления виртуальными хранилищами. На позапрошлой лекции, посвященной физическим, или реальным, хранили- щам, мы рассмотрели стратегии управления хранилищем при извлечение данных, размещении и замене. Эта лекция будет посвящена аналогичным вопросам. • Стратегии выборки – используются при перемещении страницы или сегмента из вторичного хранилища в первичное. Выборка по требованию производит за- грузку блока только при появлении ссылок на его элементы. Опережающая вы- борка загружает страницы, которые, по мнению алгоритма опережения, могут понадобиться процессу в будущем. • Стратегии размещения – используются при выборе конкретного места размеще- ния загруженной страницы или сегмента в первичном хранилище. Стратегии размещения при страничной организации очевидны, поскольку страница может быть размещена в любом свободном страничном кадре. Размещение при сег- ментной организации намного сложнее и идентично размещению блоков в слу- чае реального хранилища с изменяемыми разделами. • Стратегии замещения – используются при принятии решения о выгрузке стра- ницы или сегмента для высвобождения места под загружаемые блоки. 9.3. Стратегии замены страниц. Как правило, при страничной организации виртуального хранилища исполь- зуются все страничные кадры. Однако в таком случае к функциям подсистемы управления страницами ОС относится принятие решения, какую страницу следу-ет выгрузить во вторичное хранилище для высвобождения места. Рассмотрим следующие популярные стратегии: • принцип оптимальности; • случайная выгрузка; • FIFO; • наиболее давно использованная; • наиболее редко используемая; • неиспользованная в последнее время; • второй шанс; • часы; • рабочие наборы; • частота промахов. Принцип оптимальности. Заключается в выгрузке той страницы, которая не будет использоваться в ближайшем будущем. Однако для реализации такой стратегии нам надо уметь предсказывать будущее. Если нет никаких общих дан- ных о потребности страниц, такую стратегию лучше не применять. Случайная выгрузка. Если нам требуется стратегия, которая нересурсоемка и не дискриминирует конкретных пользователей, то подходящим вариантом мо- жет оказаться случайная выгрузка страниц. В этой стратегии каждая страница из главного хранилища должна обладать равными шансами на выгрузку. Решение о выгрузке принимается практически мгновенно. Правда, выгруженной может ока- заться и та страница, которая потребуется в следующий цикл исполнения, однако при очень большом количестве страничных кадров в первичном хранилище эта вероятность очень мала. Однако из-за своей непредсказуемости данная стратегия применяется редко. FIFO. При такой стратегии выбора страницы на выгрузку мы запоминаем время загрузки каждой страницы в первичное хранилище, или просто ставим ее в FIFO-очередь. При поиске кандидата на выгрузку выбирается та страница, кото- рая дольше всех на данный момент пробыла в первичном хранилище, или нахо- дится в начале стека. К сожалению, очень часто причиной, по которой страница надолго «застряла» в первичном хранилище является ее активное использование. Например, такая страница может содержать код разделяемой библиотеки. В ре- зультате после выгрузки эта страница будет загружена обратно практически сразу. У этой стратегии есть еще одна проблема. Очевидно, что чем больше стра- ниц из адресного пространства процесса находится в первичном хранилище, темменьше возникает исключений ошибки страницы. Однако было обнаружено, что стратегия FIFO в некоторых случаях приводит к обратному – чем больше страниц процесса загружено в память, тем чаще у этого процесса возникает исключение ошибки страницы. Это называется аномалией FIFO-стратегии. На практике такие ситуации встречаются крайне редко, однако не стоит забывать, что компьютерные системы – крайне сложные системы, и интуиция здесь подводит. Наиболее давно использованная. (Least-Recently-Used, LRU). Эта стратегия определяет, какую страницу выгрузить, по времени отсутствия обращений к ней. То есть в качестве критерия мы выбираем историю обращения к странице. То есть стратегия LRU требует, чтобы при каждом обращении к странице вы запоминали время обращения. Это вызывает некоторое снижение производительности систе- мы. По этой причине эта стратегия используется сравнительно редко. LRU можно эффективно реализовать в виде списка. При обращении к стра- нице она переводится в начало списка, а остальные страницы смещаются к концу списка. При необходимости выгрузки страницы выгружается та, которая находит- ся в этот момент в конце списка. Вновь загруженная страница помещается в нача- ло списка. Данная стратегия не лишена недостатка – выгруженная страница мо- жет сразу же загрузиться обратно. Наиболее редко используемая. (Least-Frequently-Used, LFU). Эта стратегия заключается в использовании частоты использования страниц. То есть выгружает- ся та страница, которая использовалась по сравнению со всеми остальными наи- менее редко. Однако у этой стратегии есть одна особенность – выгруженной мо- жет оказаться та страница, которая только-что была загружена в память – она была использована лишь раз, в то время как остальные страницы использовались многократно. Неиспользованная в последнее время. (Not-Recently-Used, NRU). Эта стра- тегия выбирает для выгрузки те страницы, к которым давно не было обращения. Делается это следующим образом. Каждой странице ставится в соответствие флаг чтения и флаг модификации. Эти флаги поднимаются, когда происходит обраще- ние соответствующего типа к странице, и регулярно обнуляются по таймеру. Та- ким образом все страницы можно разделить на 4 группы: класс 0: не было чтения и записи; класс 1: не было чтений, страница изменена; класс 2: было чтение, страница не изменена; класс 3: было чтение, и страница изменена.Класс 1 получается из класса 3 при сбросе флага на чтение по таймеру. Стра- тегия NRU заключается в выгрузке случайной страницы из непустого класса с наименьшим номером. Эта стратегия может как использовать аппаратную под- держку, так и быть реализованной только программно. Причем снижение произ- водительности достаточно мало. Модификации к FIFO: «часы» и «второй шанс». Очевидной проблемной FIFO является то, что она может выбрать страницу, к которой произойдет обраще- ние в следующий момент времени. Эту проблему можно решить с помощью мо- дификаций. Стратегия второго шанса заключается в том, что перед выгрузкой страницы, находящейся в конце очереди, происходит опрос флага обращения к странице. Если он был снят, то страница выгружается. Если он был поднят, то страница перемещается в начало очереди с опущенным флагом – ей дается второй шанс остаться в первичном хранилище. Если эта страница окажется в конце очереди, а флаг все еще будет опущен, то она выгрузиться из хранилища. Поскольку актив- ные страницы окажутся в конце очереди с поднятым флагом обращения, они останутся в первичном хранилище. Страницы неактивные, к которым не было об- ращения за один оборот очереди в стеке, выгружаются. Стратегия «часы» являет- ся вариантом стратегии второго шанса, в которой вместо очереди организуется за- мкнутый список.

 

 

 

 

 

 

Замена страниц по частоте промахов. Одним из методов оценки того, находится ли рабочий набор процесса в па- мяти, является частота промахов. Если уровень промахов процесса достаточно ве- лик из-за малого количества страниц процесса в первичном хранилище, процессможет замусориться. С другой стороны, процессы практически без промахов со- держат все страницы в памяти, но это может означать, что в первичном хранили- ще системы находится лишние страницы процесса, вовсе не входящие в его рабо- чий набор. Это также замедляет работу системы. В идеале процесс должен гене- рировать количество промахов, расположенное где-то между этими двумя крайни- ми точками. Алгоритм частоты промахов страниц процесса (Page Fault Frequency, PFF) управляет размещенным набором страниц процесса (то есть теми страницами процесса, что загружены в память) исходя из частоты генерации исключений ошибок обращения. Возможен и другой вариант этого алгоритма – использовать промежутки времени между промахами хранилища. PFF проверяет количество промахов за промежуток времени. Если это коли- чество меньше, чем нижний параметр алгоритма, то все страницы, к которым не было обращения за промежуток времени, исключаются из размещенного набора. Если больше, чем верхний параметр, то все страницы, загруженные за промежу- ток времени в память, включаются в набор. Аналогично можно описать и вариант с временем. Достоинство этого алгоритма в том, что он динамически подстраивает набор страниц процесса под текущее поведение программы. Если процесс переключил- ся на больший рабочий набор, PFF даст ему требуемое пространство. Если рабо- чий набор процесса уменьшился, PFF освободит неиспользуемые в данный мо- мент процессом страничные кадры. Достоинство PFF заключается в том, что в от- личие от рабочих наборов он должен выполнять действие только после промаха процесса, вместо простого обращения. Однако выбор параметров PFF является самостоятельно задачей, решение которой способно существенно повлиять на эф- фективность всей системы.


странично-сегментная организация

Среда, 13 Января 2016 г. 05:48 + в цитатник

Оказалось возможным без особых сложностей объединить сегментную и страничную организацию виртуального хранилища. Просто сегменты в таких си- стемах рассматриваются как несколько соседних страниц. Хотя это и хуже чистой сегментной организации, однако основные достоинства обоих систем сохраняют- ся, в то время как основные недостатки устраняются. Виртуальный адрес при та- кой организации памяти можно представить в виде тройки v = (s, p, d), где s – это номер сегмента, p – номер страницы в сегменте, а d – смещение внутри страницы сегмента. Трансляция адресов. Логическая схема трансля- ции адресов в системе со странично-сегментной орга- низацией показана на ри- сунке. Процесс ссылается на виртуальный адрес v = (s, p, d). Прежде всего, следует выполнить поиск в ассоциативном хранилище. В случае успеха реальный адрес начала страницы p' увеличивается на смещение d, что дает реальный адрес. Как правило, большинство операций трансляции адре- сов завершается на этом этапе. Однако в случае от- сутствия соответствующей записи в ассоциативном хранилище следует выполнить полный поиск. В таблице трансляции сегментов нашего процесса следует найти адрес начала сегмента s'. Затем в таблице трансляции страниц нашего сегмента следует найти адрес начала страницы p'. Рассмотренные выше процессы трансляции адресов предполагают, что все данные расположены именно там, где они должны быть. Однако в них есть много шагов, на которых возможно возникновение ошибки. Например, сегмент s может отсутствовать в таблице трансляции сегментов. Это вызовет возникновение ис- ключения отсутствующего сегмента, что приведет к необходимости загрузки ОС нужного сегмента из вторичного хранилища, что, в свою очередь, скорее всего по- требует выгрузки данных из первичного хранилища. Если сегмент был найден, аналогичная ситуация возможна со страницей. Виртуальный адрес может выйти за пределы сегмента или страницы, тем самым также вызвав исключение. Обратите внимание, что в случае сегментно-страничной организации ис- пользование ассоциативного хранилища особенно важно. В случае использования только первичного хранилища один цикл доступа к памяти нужен для получения данных о странице сегмента, еще один цикл – для получения доступа к странице, и еще один – для доступа к данным. Таким образом, программа замедлится в три раза (по крайней мере скорость ее доступа к памяти). Основным недостатком виртуальных хранилищ является то, что система ра- ботает быстрее в случае нахождения всех системных таблиц в памяти. Однако в таком случае остается меньше памяти для процессов. Задачей разработчиков яв- ляется достижение баланса между скоростью и эффективностью использования памяти. Разделение данных в страничных/сегментных системах. В системах, объединяющих страничную и сегментную организацию виртуального хранилища, разделение данных следует организовывать с учетом достоинств сегментной ор- ганизации.


сегментная организация

Среда, 13 Января 2016 г. 05:47 + в цитатник

В системах с непрерывным размещением в памяти программа должна была занимать непрерывную область памяти – блок. Использованием изменяемых раз- делов позволило увеличить эффективность использования памяти, однако про- грамма все равно должна была занимать в памяти один блок. Реальные сегментированные системы устранили и это требование. В них программа и данные для нее могут занимать несколько различных блоков, причем не обязательно соседних. Это приводит к возникновению нескольких интересных проблем. Например, задача о защите данных пользователя от деструктивных дей- ствий другого пользователя становится более сложной. Использование пары гра- ничных регистров становится неэффективным. Кроме того, становится более сложным вообще определение адресного пространства программы. Одним из ме- тодов решения этой проблемы является метод использования ключа защиты. Каж- дому сегменту присваивается ключ, соответствующий пользователю или задаче. При попытке доступа в другой сегмент ключи сегментов сравниваются, и в слу- чае их различия доступ запрещается. В случае виртуального сегментированного хранилища виртуальный адрес представляется парой v = (s, d), где s – это номер сегмента, а d – смещение внутри сегмента. Как и в случае страничной организации виртуального хранилища, про- цесс может быть исполнен, если его текущий сегмент находится в первичном хра- нилище. Сегменты могут перемещаться между первичным и вторичным хранили- щем, причем они рассматриваются как единое целое. Содержимое сегмента раз- мещается в памяти в виде непрерывной последовательности ячеек. Загружаемый сегмент может быть размещен в любой подходящей по размеру области реальной памяти. Стратегии размещения сегментов аналогичны стратегиям, применяемым в случае рассмотренных на прошлой лекции физических хранилищ. Процесс трансляции адресов полностью аналогичен трансляции в случае страничной орга- низации хранилища. Контроль прав при сегментной организации. Очевидно, что предостав- лять процессу права доступа ко всем сегментам системы нельзя. Вместо этого следует организовать выборочный доступ к некоторым требуемым сегментам. Бо- лее того, сегментирование хранилища позволяет тщательно выбирать права до- ступа к памяти для процесса. В таблице приведены общие права доступа:($)Если процессу дано право чтения сегмента, то процесс может получить со- держимое любой ячейки хранилища в этом сегменте, то есть он может создать полную копию сегмента. Право записи означает, что процесс способен изменить содержимое любой ячейки хранилища в этом сегменте, а также добавить данные в сегмент. То есть процесс может полностью изменить информацию сегмента. Право на исполнение означает, что процесс интерпретирует данные в сегменте как код и может выполнить его как программу. Это право имеет смысл только для сегментов кода. Право на исполнение на сегмент данных игнорируется. Право на дополнение сегмента позволяет процессу дописать новую информацию в конец сегмента, однако изменить уже существующие данные сегмента он не сможет. Права на доступ к сегменту можно хранить в таблице трансляции сегментов (или страниц). В системах, которые разрешают или запрещают эти права, можно организо- вать 42 = 16 групп контроля за доступом. Часть из них не имеет смысла. В таблице приведены 8 таких групп: ($$).

Мы рассмотрели основу механизма защиты памяти в ОС. Отображение сегментов в память. Как и при страничной организации вир- туального хранилища, существует много вариантом отображения сегментов в фи- зическую память. В целом, принципиальные отличия по сравнению со странич- ной организацией отсутствуют. Однако в таблице трансляции сегментов потребу- ется дополнительно хранить длину сегмента. При каждой операции с виртуаль- ным адресом требуется проводить проверку на выход за пределы сегмента. В слу- чае выхода за пределы блока ОС должна выполнить исключение нарушения прав доступа к памяти. Разделение памяти при сегментной организации. Одним из преимуществ сегментной организации памяти является то, что разделение блоков памяти имеет здесь скорее логический характер, чем физический. В общем случае сегмент мо- жет быть такого размера, какого требуется. Сегмент для хранения массива можно сделать по величине равным массиву. В случае хранения в сегменте динамиче- ской структуры данных сегмент может изменять свой раздел по необходимости. При загрузке программы сегмент примет такой размер, какой требуется для за- грузки этой программы В случае страничной организации памяти при разделении страниц мы долж- ны для каждой страницы учесть признак разделения. Причем разделить только половину страницы невозможно. В случае динамической структуры данных это становится еще более затруднительным. В случае же сегментной организации данных мы разделяем ровно то, что нам нужно. Причем изменение размера разде- ляемых данных не изменит факт их нахождения в разделяемом сегменте.  


страничная организация

Среда, 13 Января 2016 г. 05:38 + в цитатник

Страничная организация памяти: концепция. Учитывая сложность виртуальных хранилищ, начнем с простого варианта – блоков фиксированного размера, иначе называемых страницами. Виртуальный ад- рес представляется парой чисел (p, d) – номер страницы и смещение с начала страницы. Очевидно, что процесс может быть исполнен, если его текущая стра- ница (то есть страница, в которой расположена команда на исполнение и операн- ды для нее) находится в основном хранилище. Если это не так, то страницу следу- ет загрузить. Загрузка страницы из вторичного хранилища в первичное осуще- ствляется в блоки – т.н. страничные кадры – того же размера, что и страницы. За- груженные страницы могут быть размещены в любом свободном блоке. Поскольку не каждая страница процесса находится в памяти, таблица транс- ляции процесса должна отражать состояние страниц – загружена или нет, и если загружена, то куда. В общем виде трансляция происходит следующим образом. Процесс ссылается на виртуальный адрес v = (p, d). Механизм трансляции ищет страницу в таблице отображения страниц. В случае неудачи он должен загрузить ее. В случае успеха он определяет адрес начала страницы в реальной памяти. За- тем он вычисляет адрес ячейки с виртуальным адресом v путем смещения от на- чала страницы в памяти на d. Обратите внимание, что желательно в таблице трансляции страниц помимо адреса начала таблицы в реальной памяти хранить и адрес страницы во вторичном хранилище – это позволяет быстро определить, откуда и как получить доступ к странице. Теперь рассмотрим варианты отображе- ния страниц в реальную память. Прямое отображение. Перед началом исполнения процесса, во время переключения контекста, ОС загружает адрес начала таблицы в специальный регистр процессора. Адрес начала этой таблицы b суммируется с номером стра- ницы в таблице p. Это дает возможность получить адрес в памяти p' записи о странице в таблице отображения страниц. Затем p' суммируется со смещением для получения адреса ячейки в реальной памяти. Этот вариант отображения называется прямым, поскольку в таблице отображения хранятся данные обо всех стра- ницах в виртуальном хранилище процесса. Если у процесса есть n страниц, то та- блица отображения страниц процесса будет содержать n вхождений. Виртуальный адрес и адрес смещения таблицы следует располагать в кэше, что позволяет быстро выполнить их сложение. Однако достаточно большую та- блицу отображения разместить там трудно. Но в случае расположения ее в пер- вичном хранилище извлечение оттуда данных занимает один цикл доступа к па- мяти. То есть для обращения к ячейке виртуального хранилища таким методом в случае размещения таблицы отображения страниц в памяти понизить производи- тельность программы вдвое. Поэтому ОС при таком методе должны хранить та- блицу в кэше. С учетом постоянного роста объема кэша процессора это достаточ- но просто. Ассоциативное отображение. Другим вариантом отображения является раз- мещение таблицы в ассоциативном хранилище. Время доступа к такому достаточ- но дорогостоящему хранилищу на порядок меньше времени доступа как к основ- ному хранилищу, так и к кэшу. Единственным отличием от предыдущего вариан- та является то, что ассоциативное хранилище обеспечивает возможность одновре- менного поиска страница. То есть исчезает необходимость вычисления смещения в таблице. Вместо этого ассоциативное хранилище позволяет сразу получить ис- комый адрес начала страницы в основном хранилище. Как и в большинстве других случаев, перед разработчиками встает дилемма обеспечения баланса между производительностью и стоимостью. Для ее решения можно организовать комбинацию из двух рассмотренных вариантов. Смешанное отображение. Обратите внимание – мы не рассматриваем физи- ческую организацию компьютерных систем и оборудования. Это область интере- сов инженеров-электронщиков и т.п. Вместо этого мы сосредотачиваемся на логи- ческой структуре различных организаций системы и ее подсистем. Именно такие сведения должны иметь разработчики ОС (но это не означает, что вам не понадо- биться углублять эти знания – для этого есть другие предметы). Итак, с одной стороны кэш и ассоциативное хранилище обеспечивают гораз- до большую скорость работы, чем первичное хранилище. С другой стороны, они и стоят гораздо дороже. Поэтому для обеспечения баланса между скоростью и производительностью можно разделить страницы на несколько групп – та часть, что используется процессом наиболее активно, должна рассматриваться отдельно от редко используемых страниц. Тогда схему трансляции виртуального адреса в реальный можно представить таким образом (обратите внимание на отличие от первого варианта, вызванное наличием ассоциативного хранилища). Поиск производит- ся сначала в ассоциа- тивном хранилище. Если страница там от- сутствует, то поиск про- водится в основном хранилище. Активно использу- емые страницы можно выбрать таким образом: если процесс использо- вал страницу на протя- жении нескольких цик- лов исполнения, то, ско- рее всего, она потребу- ется ему и в будущих циклах. Аналогично можно выбрать и неактивные страницы. При изменении статуса страницы ее сле- дует внести в ассоциативное хранилище, убрав оттуда запись о ставшей неактив- ной странице. Практика показала, что для повышения производительности не требуется большого объема ассоциативного хранилища. Использование пары десятков реги- стров в ассоциативном хранилище позволяло увеличить производительность си- стемы до 90% от величины, достигаемой при полном хранении таблицы трансля- ции в ассоциативном хранилище. Разделение памяти при страничной организации. В многозадачных или многопользовательских системах обычной ситуацией является запуск одной и той же программы. Если при этом каждая копия программы будет уникальна, будет неэффективно использоваться первичное хранилище. Вместо этого имеет смысл организовать разделение тех страниц, которые можно разделить. Однако при совместном использовании страниц памяти следует соблюдать осторожность. Прежде всего, следует разделить код и данные. Кроме того, следу- ет различать модифицируемые данные или код и немодифицируемые. Страницы памяти с немодифицируемыми процедурами, а также немодифицируемые данные можно разделять между различными воплощениями программы. Модифицируе- мые процедуры разделять не следует. Модифицируемые данные при необходимо- сти возможно разделять, однако при этом следует тщательно контролировать вза- имное исключение на этих данных. Отсюда следует необходимость вводить в описание страницы памяти и при- знак ее разделяемости (в тех ОС, которые поддерживают эту возможность). Если страница совместно используется несколькими процессами, то ссылки на нее просто будут размещены в таблицах трансляции этих процессов. Эта возмож- ность позволяет существенно экономить память при запуске нескольких одина- ковых процессов.


отображение блоков

Среда, 13 Января 2016 г. 05:36 + в цитатник

Механизм динамической трансляции адресов должен обеспечивать т.н. карты трансляции адресов, содержащих информацию о том, какие именно диапазоны виртуальных адресов загружены в реальную память, и где именно они расположе- ны. Если эту информацию организовать на основе байт-в-байт, то суммарный объем такой информации был бы столь велик, что потребовалось бы столько же или даже больше реальной памяти, чем требуется процессу для исполнения. Для успешной реализации виртуального хранилища требуется использовать меньшее количество информации об отображении адресов. Поскольку мы не можем хранить данные о каждом адресе индивидуально, следует делать это иначе. То есть следует группировать эту информацию в блоки и отслеживать уже блоки адресов. Чем больше размер блока, тем меньшая доля реального адресного пространства будет занята информацией об отображении пространств. Однако увеличение размера блоков помимо снижения затрат памяти повышают время перемещения блоков между уровнями хранилищ, а также потребляют большее количество реальных адресов. Тем самым потенциально может уменьшиться количество процессов, единовременно размещенных в памяти. Также требуется решить вопрос о размере блоков – все одинаковые, или раз- личных размеров. Если все блоки одного размера, они называются страницами и такое виртуальное хранилище называется страничным (со страничной организа- цией). Если блоки различного размера, они называются сегментами (сегментная организация). Адресация блоков двумерная. Для получения конкретного элемента внутри блока требуется указать сам блок, а также смещение выбранного элемента отно- сительно начала блока. Таким образом, виртуальный адрес v соотвествует паре (b, d), где b – номер блока и d – смещение. Трансляция виртуального адреса v = (b, d) в реальный адрес r происходит следующим образом У каждого процесса есть его собственная табли- ца трансляции, хранящаяся системой в физическом хра- нилище. В управляющем устройстве (например, в ЦП) есть специальный регистр, который указывает на начало этой таблицы. При смене контекста он за- гружается адресом начала таблицы трансляции адре- сов в физическом хранилище. Эта таблица содержит по одному элементу на каж- дый блок, занятый процессом, упорядоченные по возрастанию. Эти элементы со- держат реальные адреса начала блоков в физическом хранилище. При трансляции виртуального адреса требуется сначала найти реальный адрес блока (путем сме- щения в таблице до адреса блока), а затем сместить его на смещение в блоке вир- туального адреса. Важно отметить, что процесс трансляции адреса происходит динамически при выполнении процесса. Если он реализован неэффективно, то произойдет су- щественное снижение производительности. Например, при трансляции требуется выполнить два сложения: одно при поиске адреса блока в таблице, и другое при смещении адреса от начала блока в реальном хранилище. Если эти сложения бу- дут выполняться с помощью обычных ассемблерных операций сложения, то поте- ря производительности составит порядок. Требуется проводить трансляцию бы- стрее, чем скорость выполнения машинных инструкций, то есть обеспечить аппа- ратную поддержку механизма ДТА. Кроме того, требуется существенно умень- шить время доступа к таблице размещения блоков. С этой целью ее можно разме- стить в специальной памяти, например, внутри процессора.  


эволюция хранилищ.концепция виртуальных хранилищ

Среда, 13 Января 2016 г. 05:35 + в цитатник

Эволюция хранилищ.

На рисунке приведена эволюция организации хранилищ: (/)

Физические хранилища были рассмотрены ранее. Из-за сложности вирту- альных хранилищ их обсуждение будет разделено на две части: на следующей лекции мы рассмотрим стратегии и методы для управления виртуальными хранилищами.

Виртуальные хранилища: концепция.

Основной идеей в виртуальных хранилищах является разделение адресов, используемых в программах, и адресации физического хранилища. Адреса, ис- пользуемые в программах, называются виртуальными адресами. Адреса, исполь- зуемые для адресации ячеек памяти, называются реальными адресами. Диапазон доступных виртуальных адресов называется виртуальным адресным про- странством, и обозначается как V. Аналогично, диапазон реальных адресов назы- вается реальным адресным пространством и обозначается как R. Количество ад- ресов в V равно |V|, а в R – |R|. Как правило, |V|>>|R|. Однако были созданы системы, в которых |V|<|R|. Хотя программа работает с виртуаль- ными адресами, они должны быть как-то согласованы с реальными адресами. То есть по мере выполнения процесса проис- ходит отображение виртуальных адресов в реальные адреса. Это должно быть вы- полнено как можно быстрее, иначе произойдет существенное снижение производительности, тем самым умаляя все достоинства такой схемы организации хранилищ. Механизмы, обеспечиваю- щие такое преобразование по мере исполнения процесса, на- зываются динамическими трансляторами адресов. Эти ме- ханизмы не требуют, чтобы об- ласть, непрерывная в виртуаль- ном адресном пространстве, была непрерывна в реальном адресном пространстве. Это на- зывается искусственной непре- рывностью. Благодаря ей программист может не заботиться о том, где именно будут размещены команды и данные его программы во избежание проблем с рабо- той или даже загрузкой. Таким образом, компьютер можно рассматривать как ис- полнитель алгоритмов, а не как устройство с уникальными характеристиками



Поиск сообщений в Ольга__Александровна
Страницы: [2] 1 Календарь