гуд работа. Курс лекций теория вычислительных процессов
 Скачать 1.54 Mb.
|
|
Алгоритм планирования процессов и нитей В Windows NT реализована вытесняющая многозадачность, при которой операционная система не ждет, когда нить сама захочет освободить процессор, а принудительно снимает ее с выполнения после того, как та израсходовала отведенное ей время (квант), или если в очереди готовых появилась нить с более высо- ким приоритетом. При такой организации разделения процессора ни одна нить не займет процессор на очень долгое время. В ОС Windows NT нить в ходе своего существования может иметь одно из шести состояний (рисунок 8.3). Жизненный цикл нити начинается в тот момент, когда программа создает новую нить. Запрос переда- ется NT executive, менеджер процессов выделяет память для объекта-нити и обращается к ядру, чтобы ини- циализировать объект-нить ядра. После инициализации нить проходит через следующие состояния: • Готовность. При поиске нити на выполнение диспетчер просматривает только нити, нахо- дящиеся в состоянии готовности, у которых есть все для выполнения, но не хватает только процессора. • Первоочередная готовность (standby). Для каждого процессора системы выбирается одна нить, которая будет выполняться следующей (самая первая нить в очереди). Когда условия позволяют, про- исходит переключение на контекст этой нити. • Выполнение. Как только происходит переключение контекстов, нить переходит в состояние выполнения и находится в нем до тех пор, пока либо ядро не вытеснит ее из-за того, что появилась более приоритетная нить или закончился квант времени, выделенный этой нити, либо нить завершится вообще, либо она по собственной инициативе перейдет в состояние ожидания. • Ожидание. Нить может входить в состояние ожидания несколькими способами: нить по сво- ей инициативе ожидает некоторый объект для того, чтобы синхронизировать свое выполнение; операцион- ная система (например, подсистема ввода-вывода) может ожидать в интересах нити; подсистема окружения может непосредственно заставить нить приостановить себя. Когда ожидание нити подойдет к концу, она возвращается в состояние готовности. • Переходное состояние. Нить входит в переходное состояние, если она готова к выполнению, но ресурсы, которые ей нужны, заняты. Например, страница, содержащая стек нити, может быть выгружена из оперативной памяти на диск. При освобождении ресурсов нить переходит в состояние готовности. • Завершение. Когда выполнение нити закончилось, она входит в состояние завершения. Нахо- дясь в этом состоянии, нить может быть либо удалена, либо не удалена. Это зависит от алгоритма работы менеджера объектов, в соответствии с которым он и решает, когда удалять объект. Если executive имеет ука- затель на объект-нить, то она может быть инициализирована и использована снова. Диспетчер ядра использует для определения порядка выполнения нитей алгоритм, основанный на приоритетах, в соответствии с которым каждой нити присваивается число - приоритет, и нити с более высо- ким приоритетом выполняются раньше нитей с меньшим приоритетом. В самом начале нить получает при- оритет от процесса, который создает ее. В свою очередь, процесс получает приоритет в тот момент, когда его создает подсистема той или иной прикладной среды. Значение базового приоритета присваивается про- цессу системой по умолчанию или системным администратором. Нить наследует этот базовый приоритет и может изменить его, немного увеличив или уменьшив. На основании получившегося в результате приорите- та, называемого приоритетом планирования, начинается выполнение нити. В ходе выполнения приоритет планирования может меняться. Рис. 8.3. Граф состояний нити Windows NT поддерживает 32 уровня приоритетов, разделенных на два класса - класс реального времени и класс переменных приоритетов. Нити реального времени, приоритеты которых находятся в диа- пазоне от 16 до 31, являются более приоритетными процессами и используются для выполнения задач, кри- тичных ко времени. Каждый раз, когда необходимо выбрать нить для выполнения, диспетчер прежде всего просматрива- ет очередь готовых нитей реального времени и обращается к другим нитям, только когда очередь нитей ре- ального времени пуста. Большинство нитей в системе попадают в класс нитей с переменными приоритета- 56 57 ми, диапазон приоритетов которых от 0 до 15. Этот класс имеет название "переменные приоритеты" потому, что диспетчер настраивает систему, выбирая (понижая или повышая) приоритеты нитей этого класса. Алгоритм планирования нитей в Windows NT объединяет в себе обе базовых концепции - квантова- ние и приоритеты. Как и во всех других алгоритмах, основанных на квантовании, каждой нити назначается квант, в течение которого она может выполняться. Нить освобождает процессор, если: • блокируется, уходя в состояние ожидания; • завершается; • исчерпан квант; • в очереди готовых появляется более приоритетная нить. Использование динамических приоритетов, изменяющихся во времени, позволяет реализовать адап- тивное планирование, при котором не дискриминируются интерактивные задачи, часто выполняющие опе- рации ввода-вывода и недоиспользующие выделенные им кванты. Если нить полностью исчерпала свой квант, то ее приоритет понижается на некоторую величину. В то же время приоритет нитей, которые пере- шли в состояние ожидания, не использовав полностью выделенный им квант, повышается. Приоритет не изменяется, если нить вытеснена более приоритетной нитью. Для того, чтобы обеспечить хорошее время реакции системы, алгоритм планирования использует на- ряду с квантованием концепцию абсолютных приоритетов. В соответствии с этой концепцией при появле- нии в очереди готовых нитей такой, у которой приоритет выше, чем у выполняющейся в данный момент, происходит смена активной нити на нить с самым высоким приоритетом. В многопроцессорных системах при диспетчеризации и планировании нитей играет роль их процес- сорная совместимость: после того, как ядро выбрало нить с наивысшим приоритетом, оно проверяет, какой процессор может выполнить данную нить и, если атрибут нити "процессорная совместимость" не позволяет нити выполняться ни на одном из свободных процессоров, то выбирается следующая в порядке приоритетов нить. 8. Управление памятью Память является важнейшим ресурсом, требующим тщательного управления со стороны мультипро- граммной операционной системы. Распределению подлежит вся оперативная память, не занятая операцион- ной системой. Обычно ОС располагается в самых младших адресах, однако может занимать и самые стар- шие адреса. Функциями ОС по управлению памятью являются: отслеживание свободной и занятой памяти, выделение памяти процессам и освобождение памяти при завершении процессов, вытеснение процессов из оперативной памяти на диск, когда размеры основной памяти не достаточны для размещения в ней всех процессов, и возвращение их в оперативную память, когда в ней освобождается место, а также настройка адресов программы на конкретную область физической памяти. Типы адресов Для идентификации переменных и команд используются символьные имена (метки), виртуальные адреса и физические адреса (рисунок 2.7). Символьные имена присваивает пользователь при написании программы на алгоритмическом языке или ассемблере. Виртуальные адреса вырабатывает транслятор, переводящий программу на машинный язык. Так как во время трансляции в общем случае не известно, в какое место оперативной памяти будет загружена про- грамма, то транслятор присваивает переменным и командам виртуальные (условные) адреса, обычно считая по умолчанию, что программа будет размещена, начиная с нулевого адреса. Совокупность виртуальных ад- ресов процесса называется виртуальным адресным пространством. Каждый процесс имеет собственное виртуальное адресное пространство. Максимальный размер виртуального адресного пространства ограни- чивается разрядностью адреса, присущей данной архитектуре компьютера, и, как правило, не совпадает с объемом физической памяти, имеющимся в компьютере. Физические адреса соответствуют номерам ячеек оперативной памяти, где в действительности рас- положены или будут расположены переменные и команды. Переход от виртуальных адресов к физическим может осуществляться двумя способами. В первом случае замену виртуальных адресов на физические дела- ет специальная системная программа - перемещающий загрузчик. Перемещающий загрузчик на основании имеющихся у него исходных данных о начальном адресе физической памяти, в которую предстоит загру- жать программу, и информации, предоставленной транслятором об адресно-зависимых константах про- граммы, выполняет загрузку программы, совмещая ее с заменой виртуальных адресов физическими. Второй способ заключается в том, что программа загружается в память в неизмененном виде в вир- туальных адресах, при этом операционная система фиксирует смещение действительного расположения программного кода относительно виртуального адресного пространства. Во время выполнения программы при каждом обращении к оперативной памяти выполняется преобразование виртуального адреса в физиче- ский. Второй способ является более гибким, он допускает перемещение программы во время ее выполнения, в то время как перемещающий загрузчик жестко привязывает программу к первоначально выделенному ей участку памяти. Вместе с тем использование перемещающего загрузчика уменьшает накладные расходы, так как преобразование каждого виртуального адреса происходит только один раз во время загрузки, а во втором случае - каждый раз при обращении по данному адресу. Рис. 2.7. Типы адресов В некоторых случаях (обычно в специализированных системах), когда заранее точно известно, в ка- кой области оперативной памяти будет выполняться программа, транслятор выдает исполняемый код сразу в физических адресах. Методы распределения памяти без использования дискового пространства Все методы управления памятью могут быть разделены на два класса: методы, которые используют перемещение процессов между оперативной памятью и диском, и методы, которые не делают этого (рису- нок 2.8). Начнем с последнего, более простого класса методов. 58 Рис. 2.8. Классификация методов распределения памяти Распределение памяти фиксированными разделами Самым простым способом управления оперативной памятью является разделение ее на несколько разделов фиксированной величины. Это может быть выполнено вручную оператором во время старта сис- темы или во время ее генерации. Очередная задача, поступившая на выполнение, помещается либо в общую очередь (рисунок 2.9,а), либо в очередь к некоторому разделу (рисунок 2.9,б). Подсистема управления памятью в этом случае выполняет следующие задачи: • сравнивая размер программы, поступившей на выполнение, и свободных разделов, выбирает подходящий раздел, • осуществляет загрузку программы и настройку адресов. При очевидном преимуществе - простоте реализации - данный метод имеет существенный недоста- ток - жесткость. Так как в каждом разделе может выполняться только одна программа, то уровень мульти- программирования заранее ограничен числом разделов не зависимо от того, какой размер имеют програм- мы. Даже если программа имеет небольшой объем, она будет занимать весь раздел, что приводит к неэф- фективному использованию памяти. С другой стороны, даже если объем оперативной памяти машины по- зволяет выполнить некоторую программу, разбиение памяти на разделы не позволяет сделать этого. 59 Рис. 2.9. Распределение памяти фиксированными разделами: а - с общей очередью; б - с отдельными очередями Распределение памяти разделами переменной величины В этом случае память машины не делится заранее на разделы. Сначала вся память свободна. Каждой вновь поступающей задаче выделяется необходимая ей память. Если достаточный объем памяти отсутству- ет, то задача не принимается на выполнение и стоит в очереди. После завершения задачи память освобожда- ется, и на это место может быть загружена другая задача. Таким образом, в произвольный момент времени оперативная память представляет собой случайную последовательность занятых и свободных участков (разделов) произвольного размера. На рисунке 2.10 показано состояние памяти в различные моменты вре- мени при использовании динамического распределения. Так в момент t0 в памяти находится только ОС, а к моменту t1 память разделена между 5 задачами, причем задача П4, завершаясь, покидает память. На осво- бодившееся после задачи П4 место загружается задача П6, поступившая в момент t3. 60 Рис. 2.10. Распределение памяти динамическими разделами Задачами операционной системы при реализации данного метода управления памятью является: • ведение таблиц свободных и занятых областей, в которых указываются начальные адреса и размеры участков памяти, • при поступлении новой задачи - анализ запроса, просмотр таблицы свободных областей и вы- бор раздела, размер которого достаточен для размещения поступившей задачи, • загрузка задачи в выделенный ей раздел и корректировка таблиц свободных и занятых облас- тей, • после завершения задачи корректировка таблиц свободных и занятых областей. Программный код не перемещается во время выполнения, то есть может быть проведена единовре- менная настройка адресов посредством использования перемещающего загрузчика. Выбор раздела для вновь поступившей задачи может осуществляться по разным правилам, таким, например, как "первый попавшийся раздел достаточного размера", или "раздел, имеющий наименьший дос- таточный размер", или "раздел, имеющий наибольший достаточный размер". Все эти правила имеют свои преимущества и недостатки. По сравнению с методом распределения памяти фиксированными разделами данный метод обладает гораздо большей гибкостью, но ему присущ очень серьезный недостаток - фрагментация памяти. Фрагмен- тация - это наличие большого числа несмежных участков свободной памяти очень маленького размера (фрагментов). Настолько маленького, что ни одна из вновь поступающих программ не может поместиться ни в одном из участков, хотя суммарный объем фрагментов может составить значительную величину, на- много превышающую требуемый объем памяти. Перемещаемые разделы Одним из методов борьбы с фрагментацией является перемещение всех занятых участков в сторону старших либо в сторону младших адресов, так, чтобы вся свободная память образовывала единую свобод- ную область (рисунок 2.11). В дополнение к функциям, которые выполняет ОС при распределении памяти переменными разделами, в данном случае она должна еще время от времени копировать содержимое разде- лов из одного места памяти в другое, корректируя таблицы свободных и занятых областей. Эта процедура называется "сжатием". Сжатие может выполняться либо при каждом завершении задачи, либо только тогда, когда для вновь поступившей задачи нет свободного раздела достаточного размера. В первом случае требу- ется меньше вычислительной работы при корректировке таблиц, а во втором - реже выполняется процедура 61 сжатия. Так как программы перемещаются по оперативной памяти в ходе своего выполнения, то преобразо- вание адресов из виртуальной формы в физическую должно выполняться динамическим способом. Рис. 2.11. Распределение памяти перемещаемыми разделами Хотя процедура сжатия и приводит к более эффективному использованию памяти, она может потре- бовать значительного времени, что часто перевешивает преимущества данного метода. Методы распределения памяти с использованием дискового пространства Понятие виртуальной памяти Уже достаточно давно пользователи столкнулись с проблемой размещения в памяти программ, раз- мер которых превышал имеющуюся в наличии свободную память. Решением было разбиение программы на части, называемые оверлеями. 0-ой оверлей начинал выполняться первым. Когда он заканчивал свое выпол- нение, он вызывал другой оверлей. Все оверлеи хранились на диске и перемещались между памятью и дис- ком средствами операционной системы. Однако разбиение программы на части и планирование их загрузки в оперативную память должен был осуществлять программист. Развитие методов организации вычислительного процесса в этом направлении привело к появлению метода, известного под названием виртуальная память. Виртуальным называется ресурс, который пользо- вателю или пользовательской программе представляется обладающим свойствами, которыми он в действи- тельности не обладает. Так, например, пользователю может быть предоставлена виртуальная оперативная память, размер которой превосходит всю имеющуюся в системе реальную оперативную память. Пользова- тель пишет программы так, как будто в его распоряжении имеется однородная оперативная память большо- го объема, но в действительности все данные, используемые программой, хранятся на одном или несколь- ких разнородных запоминающих устройствах, обычно на дисках, и при необходимости частями отобража- ются в реальную память. Таким образом, виртуальная память - это совокупность программно-аппаратных средств, позволяю- щих пользователям писать программы, размер которых превосходит имеющуюся оперативную память; для этого виртуальная память решает следующие задачи: • размещает данные в запоминающих устройствах разного типа, например, часть программы в оперативной памяти, а часть на диске; • перемещает по мере необходимости данные между запоминающими устройствами разного типа, например, подгружает нужную часть программы с диска в оперативную память; • преобразует виртуальные адреса в физические. Все эти действия выполняются автоматически, без участия программиста, то есть механизм вирту- альной памяти является прозрачным по отношению к пользователю. Наиболее распространенными реализациями виртуальной памяти является страничное, сегментное и странично-сегментное распределение памяти, а также свопинг. Страничное распределение На рисунке 2.12 показана схема страничного распределения памяти. Виртуальное адресное про- странство каждого процесса делится на части одинакового, фиксированного для данной системы размера, называемые виртуальными страницами. В общем случае размер виртуального адресного пространства не 62 63 является кратным размеру страницы, поэтому последняя страница каждого процесса дополняется фиктив- ной областью. Вся оперативная память машины также делится на части такого же размера, называемые физически- ми страницами (или блоками). Размер страницы обычно выбирается равным степени двойки: 512, 1024 и т.д., это позволяет упро- стить механизм преобразования адресов. При загрузке процесса часть его виртуальных страниц помещается в оперативную память, а осталь- ные - на диск. Смежные виртуальные страницы не обязательно располагаются в смежных физических стра- ницах. При загрузке операционная система создает для каждого процесса информационную структуру - таб- лицу страниц, в которой устанавливается соответствие между номерами виртуальных и физических страниц для страниц, загруженных в оперативную память, или делается отметка о том, что виртуальная страница вы- гружена на диск. Кроме того, в таблице страниц содержится управляющая информация, такая как признак модификации страницы, признак невыгружаемости (выгрузка некоторых страниц может быть запрещена), признак обращения к странице (используется для подсчета числа обращений за определенный период вре- мени) и другие данные, формируемые и используемые механизмом виртуальной памяти. При активизации очередного процесса в специальный регистр процессора загружается адрес табли- цы страниц данного процесса. При каждом обращении к памяти происходит чтение из таблицы страниц информации о виртуальной странице, к которой произошло обращение. Если данная виртуальная страница находится в оперативной памяти, то выполняется преобразование виртуального адреса в физический. Если же нужная виртуальная страница в данный момент выгружена на диск, то происходит так называемое страничное прерывание. Вы- полняющийся процесс переводится в состояние ожидания, и активизируется другой процесс из очереди го- товых. Параллельно программа обработки страничного прерывания находит на диске требуемую виртуаль- ную страницу и пытается загрузить ее в оперативную память. Если в памяти имеется свободная физическая страница, то загрузка выполняется немедленно, если же свободных страниц нет, то решается вопрос, какую страницу следует выгрузить из оперативной памяти. В данной ситуации может быть использовано много разных критериев выбора, наиболее популярные из них следующие: • дольше всего не использовавшаяся страница, • первая попавшаяся страница, • страница, к которой в последнее время было меньше всего обращений. В некоторых системах используется понятие рабочего множества страниц. Рабочее множество опре- деляется для каждого процесса и представляет собой перечень наиболее часто используемых страниц, кото- рые должны постоянно находиться в оперативной памяти и поэтому не подлежат выгрузке. После того, как выбрана страница, которая должна покинуть оперативную память, анализируется ее признак модификации (из таблицы страниц). Если выталкиваемая страница с момента загрузки была моди- фицирована, то ее новая версия должна быть переписана на диск. Если нет, то она может быть просто унич- тожена, то есть соответствующая физическая страница объявляется свободной. Рассмотрим механизм преобразования виртуального адреса в физический при страничной организа- ции памяти (рисунок 2.13). Виртуальный адрес при страничном распределении может быть представлен в виде пары (p, s), где p - номер виртуальной страницы процесса (нумерация страниц начинается с 0), а s - смещение в пределах вир- туальной страницы. Учитывая, что размер страницы равен 2 в степени к, смещение s может быть получено простым отделением k младших разрядов в двоичной записи виртуального адреса. Оставшиеся старшие раз- ряды представляют собой двоичную запись номера страницы p. При каждом обращении к оперативной памяти аппаратными средствами выполняются следующие действия: 1. на основании начального адреса таблицы страниц (содержимое регистра адреса таблицы стра- ниц), номера виртуальной страницы (старшие разряды виртуального адреса) и длины записи в таблице стра- ниц (системная константа) определяется адрес нужной записи в таблице, 2. из этой записи извлекается номер физической страницы, 3. к номеру физической страницы присоединяется смещение (младшие разряды виртуального адреса). Использование в пункте (3) того факта, что размер страницы равен степени 2, позволяет применить операцию конкатенации (присоединения) вместо более длительной операции сложения, что уменьшает вре- мя получения физического адреса, а значит повышает производительность компьютера. Рис. 2.12. Страничное распределение памяти На производительность системы со страничной организацией памяти влияют временные затраты, связанные с обработкой страничных прерываний и преобразованием виртуального адреса в физический. При часто возникающих страничных прерываниях система может тратить большую часть времени впустую, на свопинг страниц. Чтобы уменьшить частоту страничных прерываний, следовало бы увеличивать размер страницы. Кроме того, увеличение размера страницы уменьшает размер таблицы страниц, а значит умень- шает затраты памяти. С другой стороны, если страница велика, значит велика и фиктивная область в по- следней виртуальной странице каждой программы. В среднем на каждой программе теряется половина объ- ема страницы, что в сумме при большой странице может составить существенную величину. Время преоб- разования виртуального адреса в физический в значительной степени определяется временем доступа к таб- лице страниц. В связи с этим таблицу страниц стремятся размещать в "быстрых" запоминающих устройст- вах. Это может быть, например, набор специальных регистров или память, использующая для уменьшения времени доступа ассоциативный поиск и кэширование данных. Страничное распределение памяти может быть реализовано в упрощенном варианте, без выгрузки страниц на диск. В этом случае все виртуальные страницы всех процессов постоянно находятся в оператив- ной памяти. Такой вариант страничной организации хотя и не предоставляет пользователю виртуальной па- мяти, но почти исключает фрагментацию за счет того, что программа может загружаться в несмежные об- ласти, а также того, что при загрузке виртуальных страниц никогда не образуется остатков. |