Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

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

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

Сегментный способ организации виртуальной памяти

Первым среди разрывных методов распределения памяти был сегментный. Для этого метода программу необходимо разбивать на части и уже каждой такой части выделять физическую память. Естественным способом разбиения программы на части является разбиение её на логические элементы - так называемые сегменты. В принципе каждый программный модуль (или их совокупность, если мы того пожелаем) может быть воспринят как отдельный сегмент, и вся программа тогда будет представлять собой множество сегментов. Каждый сегмент размещается в памяти как до определенной степени самостоятельная единица. Логически обращение к элементам программы в этом случае будет представляться как указание имени сегмента и смещения относительно начала этого сегмента. Физически имя (или порядковый номер) сегмента будет соответствовать некоторому адресу, с которого этот сегмент начинается при его размещении в памяти, и смещение должно прибавляться к этому базовому адресу.

Преобразование имени сегмента в его порядковый номер осуществит система программирования, а операционная система будет размещать сегменты в память и для каждого сегмента получит информацию о его начале. Таким образом, виртуальный адрес для этого способа будет состоять из двух полей - номер сегмента и смещение относительно начала сегмента. Соответствующая иллюстрация приведена на рис. 1. На этом рисунке изображен случай обращения к ячейке, виртуальный адрес которой равен сегменту с номером 11 и смещением от начала этого сегмента, равным 612. Как мы видим, операционная система разместила данный сегмент в памяти, начиная с ячейки с номером 19 700.

Рис 1. Сегментный способ организации виртуальной памяти

Каждый сегмент, размещаемый в памяти, имеет соответствующую информационную структуру, часто называемую дескриптором сегмента. Именно операционная система строит для каждого исполняемого процесса соответствующую таблицу дескрипторов сегментов и при размещении каждого из сегментов в оперативной или внешней памяти в дескрипторе отмечает его текущее местоположение.

Если сегмент задачи в данный момент находится в оперативной памяти, то об этом делается пометка в дескрипторе. Как правило, для этого используется «бит присутствия» (present). В этом случае в поле «адрес» диспетчер памяти записывает адрес физической памяти, с которого сегмент начинается, а в поле «длина сегмента» (limit) указывается количество адресуемых ячеек памяти. Это поле используется не только для того, чтобы размещать сегменты без наложения один на другой, но и для того, чтобы проконтролировать, не обращается ли код исполняющейся задачи за пределы текущего сегмента. В случае превышения длины сегмента вследствие ошибок программирования мы можем говорить о нарушении адресации и с помощью введения специальных аппаратных средств генерировать сигналы прерывания, которые позволят фиксировать (обнаруживать) такого рода ошибки.

Если бит present в дескрипторе указывает, что сейчас этот сегмент находится не в оперативной, а во внешней памяти (например, на винчестере), то названные поля адреса и длины используются для указания адреса сегмента в координатах внешней памяти. Помимо информации о местоположении сегмента, в дескрипторе сегмента, как правило, содержатся данные о его типе (сегмент кода или сегмент данных), правах доступа к этому сегменту (можно или нельзя его модифицировать, предоставлять другой задаче), отметка об обращениях к данному сегменту (информация о том, как часто или как давно/недавно этот сегмент используется или не используется, на основании которой можно принять решение о том, чтобы предоставить место, занимаемое текущим сегментом, другому сегменту).

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

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

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

При поиске свободного места используется одна из вышеперечисленных дисциплин работы диспетчера памяти (применяются правила «первого подходящего» и «самого неподходящего» фрагментов). Если свободного фрагмента памяти достаточного объёма сейчас нет, но тем не менее сумма этих свободных фрагментов превышает требования по памяти для нового сегмента, то в принципе может быть применено «уплотнение памяти», о котором мы уже говорили в подразделе «Разделы с фиксированными границами» при рассмотрении динамического способа разбиения памяти на разделы.

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

Для решения проблемы замещения (определения того сегмента, который должен быть либо перемещен во внешнюю память, либо просто замещен новым) используются следующие дисциплины:

правило FIFO (first in - first out, что означает: «первый пришедший первым и выбывает»);

правило LRU (least recently used, что означает «последний из недавно использованных» или, иначе говоря, «дольше всего неиспользуемый»);

правило LFU (least frequently used, что означает: «используемый реже всех остальных»);

¦ случайный (random) выбор сегмента.

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

Алгоритм FIFO ассоциирует с каждым сегментом время, когда он был помещён в память. Для замещения выбирается наиболее старый сегмент. Учет времени необязателен, когда все сегменты в памяти связаны в FIFO-очередь и каждый помещаемый в память сегмент добавляется в хвост этой очерёди. Алгоритм учитывает только время нахождения сегмента в памяти, но не учитывает фактическое использование сегментов. Например, первые загруженные сегменты программы могут содержать переменные, используемые на протяжении работы всей программы. Это приводит к немедленному возвращению к только что замещенному сегменту.

Для реализации дисциплин LRU и LFU необходимо, чтобы процессор имел дополнительные аппаратные средства. Минимальные требования - достаточно, чтобы при обращении к дескриптору сегмента для получения физического адреса, с которого сегмент начинает располагаться в памяти, соответствующий бит обращения менял свое значение (скажем, с нулевого, которое установила ОС, в единичное). Тогда диспетчер памяти может время от времени просматривать таблицы дескрипторов исполняющихся задач и собирать для соответствующей обработки статистическую информацию об обращениях к сегментам. В результате можно составить список, упорядоченный либо по длительности не использования (для дисциплины LRU), либо по частоте использования (для дисциплины LFU).

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

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

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

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

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

Примером использования сегментного способа организации виртуальной памяти является операционная система для ПК OS/2 первого поколения, которая была создана для процессора i80286. В этой ОС в полной мере использованы аппаратные средства микропроцессора, который специально проектировался для поддержки сегментного способа распределения памяти.

OS/2 v.l поддерживала распределение памяти, при котором выделялись сегменты программы и сегменты данных. Система позволяла работать как с именованными, так и неименованными сегментами. Имена разделяемых сегментов данных имели ту же форму, что и имена файлов. Процессы получали доступ к именованным разделяемым сегментам, используя их имена в специальных системных вызовах. OS/2 v.l допускала разделение программных сегментов приложений и подсистем, а также глобальных сегментов данных подсистем. Вообще, вся концепция системы OS/2 была построена на понятии разделения памяти: процессы почти всегда разделяют сегменты с другими процессами. В этом состояло существенное отличие от систем типа UNIX, которые обычно разделяют только реентерабельные программные модули между процессами.

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

Если в результате компрессии памяти не удавалось создать необходимое свободное пространство, то супервизор выполнял операции фонового плана для перекачки достаточного количества сегментов из физической памяти, чтобы дать возможность завершиться исходному запросу.

Механизм перекачки сегментов использовал файловую систему для перекачки данных из физической памяти и в неё. Ввиду того, что перекачка и сжатие влияют на производительность системы в целом, пользователь может сконфигурировать систему так, чтобы эти функции не выполнялись.

Было организовано в OS/2 и динамическое присоединение обслуживающих программ. Программы OS/2 используют команды удаленного вызова. Ссылки, генерируемые этими вызовами, определяются в момент загрузки самой программы или её сегментов. Такое отсроченное определение ссылок называется динамическим присоединением. Загрузочный формат модуля OS/2 представляет собой расширение формата загрузочного модуля DOS. Он был расширен, чтобы поддерживать необходимое окружение для свопинга сегментов с динамическим присоединением. Динамическое присоединение уменьшает объём памяти для программ в OS/2, одновременно делая возможным перемещения подсистем и обслуживающих программ без необходимости повторного редактирования адресных ссылок к прикладным программам.

Страничный способ организации виртуальной памяти

Как мы уже сказали, при таком способе все фрагменты программы, на которые она разбивается (за исключением последней её части), получаются одинаковыми. Одинаковыми полагаются и единицы памяти, которые мы предоставляем для размещения фрагментов программы. Эти одинаковые части называют страницами и говорят, что память разбивается на физические страницы, а программа - на виртуальные страницы. Часть виртуальных страниц задачи размещается в оперативной памяти, а часть - во внешней. Обычно место во внешней памяти, в качестве которой в абсолютном большинстве случаев выступают накопители на магнитных дисках (поскольку они относятся к быстродействующим устройствам с прямым доступом), называют файлом подкачки или страничным файлом (paging file). Иногда этот файл называют swap-файлом, тем самым подчеркивая, что записи этого файла - страницы - замещают друг друга в оперативной памяти. В некоторых ОС выгруженные страницы располагаются не в файле, а в специальном разделе дискового пространства. В UNIX-системах для этих целей выделяется специальный раздел, но кроме него могут быть использованы и файлы, выполняющие те же функции, если объёма раздела недостаточно.

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

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

Рис 2. Страничный способ организации внутренней памяти

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

При обращении к виртуальной странице, не оказавшейся в данный момент в оперативной памяти, возникает прерывание и управление передаётся диспетчеру памяти, который должен найти свободное место. Обычно предоставляется первая же свободная страница. Если свободной физической страницы нет, то диспетчер памяти по одной из вышеупомянутых дисциплин замещения (LRU, LFU, FIFO, random) определит страницу, подлежащую расформированию или сохранению во внешней памяти. На её место он разместит ту новую виртуальную страницу, к которой было обращение из задачи, но её не оказалось в оперативной памяти.

Напомним, что алгоритм выбирает для замещения ту страницу, на которую не было ссылки на протяжении наиболее длинного периода времени. Дисциплина LRU (least recently used) ассоциирует с каждой страницей время последнего её использования. Для замещения выбирается та страница, которая дольше всех не использовалась.

Для использования дисциплин LRU и LFU в процессоре должны быть соответствующие аппаратные средства. В дескрипторе страницы размещается бит обращения (подразумевается, что на рис. 2 этот бит расположен в последнем поле), и этот бит становится единичным при обращении к дескриптору.

Если объём физической памяти небольшой и даже часто требуемые страницы не удается разместить в оперативной памяти, то возникает так называемая «пробуксовка». Другими словами, пробуксовка - это ситуация, при которой загрузка нужной нам страницы вызывает перемещение во внешнюю память той страницы, с которой мы тоже активно работаем. Очевидно, что это очень плохое явление. Чтобы его не допускать, желательно увеличить объём оперативной памяти (сейчас это стало самым простым решением), уменьшить количество параллельно выполняемых задач либо попробовать использовать более эффективные дисциплины замещения. В абсолютном большинстве современных ОС используется дисциплина замещения страниц LRU как самая эффективная. Так, именно эта дисциплина используется в OS/2 и Linux. Однако в такой ОС, как Windows NT, разработчики, желая сделать систему максимально независимой от аппаратных возможностей процессора, пошли на отказ от этой дисциплины и применили правило FIFO. А для того, чтобы хоть как-нибудь сгладить её неэффективность, была введена «буферизация» тех страниц, которые должны быть записаны в файл подкачки на диск или просто расформированы. Принцип буферирования прост. Прежде чем замещаемая страница действительно будет перемещена во внешнюю память или просто расформирована, она помечается как кандидат на выгрузку. Если в следующий раз произойдет обращение к странице, находящейся в таком «буфере», то страница никуда не выгружается и уходит в конец списка FIFO. В противном случае страница действительно выгружается, а на её место в «буфере» попадает следующий «кандидат». Величина такого «буфера» не может быть большой, поэтому эффективность страничной реализации памяти в Windows NT намного ниже, чем у вышеназванных ОС, и явление пробуксовки начинается даже при существенно большем объёме оперативной памяти.

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

Как и в случае с сегментным способом организации виртуальной памяти, страничный механизм приводит к тому, что без специальных аппаратных средств он будет существенно замедлять работу вычислительной системы. Поэтому обычно используется кэширование страничных дескрипторов. Наиболее эффективным способом кэширования является использование ассоциативного кэша. Именно такой ассоциативный кэш и создан в 32-разрядных микропроцессорах i80x86. Начиная с i80386, который поддерживает страничный способ распределения памяти, в этих микропроцессорах имеется кэш на 32 страничных дескриптора. Поскольку размер страницы в этих микропроцессорах равен 4 Кбайт, возможно быстрое обращение к 1 28 Кбайт памяти.

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

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

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

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

Сегментно-страничный способ организации виртуальной памяти

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



Рис 3. Сегментно-страничный способ организации виртуальной памяти

Из рисунка сразу видно, что этот способ организации виртуальной памяти вносит ещё большую задержку доступа к памяти. Необходимо сначала вычислить адрес дескриптора сегмента и прочитать его, затем вычислить адрес элемента таблицы страниц этого сегмента и извлечь из памяти необходимый элемент, и уже только после этого можно к номеру физической страницы приписать номер ячейки в странице (индекс). Задержка доступа к искомой ячейке получается по крайней мере в три раза больше, чем при простой прямой адресации. Чтобы избежать этой неприятности, вводится кэширование, причем кэш, как правило, строится по ассоциативному принципу. Другими словами, просмотры двух таблиц в памяти могут быть заменены одним обращением к ассоциативной памяти.

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

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

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

Заключение

В ходе выполнения курсовой работы были изучены принципы страничного и сегментного распределения. Было выяснено, что сегментно-страничное распределение представляет собой комбинацию страничного и сегментного распределения памяти и, вследствие этого, сочетает в себе достоинства обоих подходов.

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

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

Практическая часть

Исходные данные

сегментный страничный распределение память

Вычислительная система располагает оперативной памятью V и внешней H. Реализуется режим мультипрограммирования: процессорное время распределяется равномерно между выполняемыми задачами. В систему поступает поток из M заданий, очередное задание поступает через время t_i. Каждое задание состоит из одной задачи и требует v_i оперативной памяти и h_i внешней, а также процессорное время. Все задания используют внешнюю память только для ввода в течение времени q*h_i, после чего начинается счёт, но закреплённый внешний носитель освобождается лишь после завершения задания. Возможно параллельное использование внешней памяти без задержки заданиями друг друга.

Поступившие задания помещаются в очередь. Для выбора заданий из очереди на выполнения используются алгоритмы FIFO и SJF.

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

Где - время завершения задания, - время поступления задания в систему.

Для нормирования различных вариантов последовательностей заданий используется набор из 10 типов задач (см. таблицу 1). Каждое задание включает одну из этих 10 задач. В одном потоке заданий могут встретиться задания, содержащие одинаковые задачи. Номер задачи К_i для очередного задания определяется по формулам:

X_i = [7 * X_i-1 + 417] mod 1000;

K_i = [X_i / 7] mod 10, i=1M, X_o = N,

где [c] - целая часть числа с, y mod z - остаток от деления y на z,Xo = N =817. Значение используемых параметров: V=16, H=12, q=5, M=10, последовательность периодов времени (интервал поступления заданий) t_i=k_i.

Таблица 1. Исходный список задач

K	0	1	2	3	4	5	6	7	8	9
v	6	3	2	4	3	5	7	9	4	1
h	2	4	3	1	2	0	4	1	6	3
?	70	90	40	10	60	30	20	30	40	50

Исходные данные для раздела 1

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

Таблица 2. Задания для обработки системой

№ работы	Соответствие варианту из таблицы	Время поступления задания	ОП	Внешняя память	Процессорное время	Время ввода
0	6	6	7	4	20	20
1	9	15	1	3	50	15
2	2	17	2	3	40	15
3	0	17	6	2	70	10
4	9	26	1	3	50	15
5	8	34	4	6	40	30
6	4	38	3	2	60	10
7	2	40	2	3	40	15
8	6	46	7	4	20	20
9	4	50	3	2	60	10

Пример расчетов:

K₀ = [X₀ / 7] mod 10=[817/7] mod 10= 6;

X₁ = [7 * X₀ + 417] mod 1000=[7 * 817 + 417] mod 1000=136;

K₁ = [X₁ / 7] mod 10=[136/7] mod 10= 9;

X₂ = [7 * X₁ + 417] mod 1000=[7 * 136 + 417] mod 1000=369;

K₂ = [X₂ / 7] mod 10=[369/7] mod 10= 2;

Временная диаграмма дисциплины обслуживания FIFO

События, происходящие в системе, описываются в таблице 3.

Таблица 3. Описание временной диаграммы для ДО FIFO

Момент времени	Событие	Свободные ресурсы
0	Система начинает работу.	ОП=16, ВП=12
6	Поступает З1[7, 4]. Выделяются ресурсы для З1.	ОП=9, ВП=8
15	Поступает З2[1, 3]. Выделяются ресурсы для З2.	ОП=8, ВП=5
17	Поступает З3[2, 3] и З4[6, 2]. Выделяются ресурсы для З3 и З4.	ОП=0, ВП=0
26	Поступает З5 [1, 3], ресурсов недостаточно. З5 в очереди в состоянии ожидания.	ОП=0, ВП=0
34	Поступает З6[4, 6], ресурсов недостаточно. З6 в очереди в состоянии ожидания.	ОП=0, ВП=0
38	Поступает З7[3, 2], ресурсов недостаточно. З7 в очереди в состоянии ожидания.	ОП=0, ВП=0
40	Поступает З8[2, 3], ресурсов недостаточно. З8 в очереди в состоянии ожидания.	ОП=0, ВП=0
46	Поступает З9[7, 4], ресурсов недостаточно. З9 в очереди в состоянии ожидания.	ОП=0, ВП=0
50	Поступает З10[3, 2], ресурсов недостаточно. З10 в очереди в состоянии ожидания.	ОП=0, ВП=0
100	З1 завершена. Освобождаются ресурсы: [7, 4]. Этого достаточно для З5, З7, З8, З9, 39. По FIFO выбираем З5, пришедшую раньше. Оставшихся ресурсов [6, 1] не достаточно для запуска ещё одной задачи.	ОП=6, ВП=1
187	З3 завершена. Освобождаются ресурсы: [8, 4]. Этого достаточно для З7, З8, З9, 39. По FIFO выбираем З7, пришедшую раньше. Оставшихся ресурсов [5, 2] достаточно для запуска З10 Выделяются ресурсы для З10.	ОП=2, ВП=0
227	З2 завершена. Освобождаются ресурсы: [3, 3]. Этого достаточно только для З8. Выделяются ресурсы для З8.	ОП=1, ВП=0
316	З4 завершена. Освобождаются ресурсы: [7, 2]. Оставшихся ресурсов не достаточно для запуска какой-либо задачи.	ОП=7, ВП=2
332	З5 завершена. Освобождаются ресурсы: [8, 5]. Этого достаточно только для З9. Выделяются ресурсы для З9.	ОП=1, ВП=1
410	З8 завершена. Освобождаются ресурсы, свободно: [3, 4]. Оставшихся ресурсов не достаточно для запуска какой-либо задачи.	ОП=3, ВП=4
427	З9 завершено. Освобождаются ресурсы, свободно [10, 8]. Этого достаточно только для З6. Выделяются ресурсы для З6.	ОП=6, ВП=2
436	З7 и З10 завершены. Освобождаются ресурсы, свободно: [12, 6]. Очередь пуста.	ОП=12, ВП=6
497	З6 завершено. Освобождаются ресурсы. Очередь пуста. Все задания выполнены.	ОП=16, ВП=12

Рассчитаем средневзвешенное время обращений и общего времени ожидания. Результаты приведены в таблице 4:

Таблица 4. Расчёт средневзвешенного времени обращений и общего времени ожидания для ДО FIFO

№					tожид	tожид. общ
1	94	40	2,35	5,12	0	1226
2	212	65	3,26		0
3	170	55	3,09		0
4	299	80	3,74		0
5	306	65	4,71		74
6	463	70	6,61		393
7	398	70	5,69		149
8	370	55	6,73		187
9	381	40	9,53		286
10	386	70	5,51		137

Пример расчетов:

Временная диаграмма дисциплины обслуживания SJF

События, происходящие в системе, описываются в таблице 5.

Таблица 5. Описание временной диаграммы для ДО SJF

Момент времени	Событие	Свободные ресурсы
0	Система начинает работу.	ОП=16, ВП=12
6	Поступает З1 [7, 4]. Выделяются ресурсы для З1.	ОП=9, ВП=8
15	Поступает З2[1, 3]. Выделяются ресурсы для З2.	ОП=8, ВП=5
17	Поступает З3[2, 3] и З4[6, 2]. Выделяются ресурсы для З3 и З4.	ОП=0, ВП=0
26	Поступает З5 [1, 3], ресурсов недостаточно. З5 в очереди в состоянии ожидания.	ОП=0, ВП=0
34	Поступает З6[4, 6], ресурсов недостаточно. З6 в очереди в состоянии ожидания.	ОП=0, ВП=0
38	Поступает З7[3, 2], ресурсов недостаточно. З7 в очереди в состоянии ожидания.	ОП=0, ВП=0
40	Поступает З8[2, 3], ресурсов недостаточно. З8 в очереди в состоянии ожидания.	ОП=0, ВП=0
46	Поступает З9[7, 4], ресурсов недостаточно. З9 в очереди в состоянии ожидания.	ОП=0, ВП=0
50	Поступает З10[3, 2], ресурсов недостаточно. З10 в очереди в состоянии ожидания.	ОП=0, ВП=0
100	З1 завершена. Освобождаются ресурсы, свободно: [7, 4]. Этого достаточно для З5(50), З7(60), З8(40), З9(20), 310(60). По SJF выбираем З9,??9 =20. Выделяются ресурсы для З9. Оставшихся ресурсов не достаточно для запуска ещё одной задачи.	ОП=0, ВП=0
185	З3 завершена. Освобождаются ресурсы, свободно: [2, 3]. Этого достаточно для З5(50), З8(40). По SJF выбираем З8,??8 =40. Выделяются ресурсы для З8. Оставшихся ресурсов не достаточно для запуска ещё одной задачи.	ОП=0, ВП=0
196	З9 завершена. Освобождаются ресурсы, свободно: [7, 4]. Этого достаточно для З5(50), З7(60), З10(60). По SJF выбираем З5,??5 =50. Выделяются ресурсы для З8. Оставшихся ресурсов не достаточно для запуска ещё одной задачи.	ОП=6, ВП=1
211	З2 завершена. Освобождаются ресурсы, свободно: [7, 4]. Этого достаточно для З7(60), З10(60). ?7=?10, поэтому по FIFO выбираем З7, пришедшую раньше. Выделяются ресурсы для З7. Оставшихся ресурсов [4, 2] достаточно для запуска ещё одной задачи З10. Выделяются ресурсы для З10.	ОП=1, ВП=0
297	З4 завершена. Освобождаются ресурсы, свободно: [7, 2]. Оставшихся ресурсов не достаточно для запуска ни одной задачи.	ОП=7, ВП=2
369	З8 завершена. Освобождаются ресурсы, свободно: [9, 5]. Оставшихся ресурсов не достаточно для запуска ни одной задачи.	ОП=9, ВП=5
410	З5 завершена. Освобождаются ресурсы, свободно: [10, 8]. Оставшихся ресурсов [4, 2] достаточно для запуска задачи З6. Выделяются ресурсы для З6.	ОП=5, ВП=2
436	З7 и З10 завершены. Освобождаются ресурсы. Очередь пуста.	ОП=12, ВП=6
480	З6 завершено. Освобождаются ресурсы. Очередь пуста. Все задания выполнены.	ОП=16, ВП=12

Рассчитаем средневзвешенное время обращений и общего времени ожидания. Результаты приведены в таблице 6.

Таблица 6. Расчёт средневзвешенного времени обращений и общего времени ожидания для ДО SJF

№					tожид	tожид. общ
1	94	40	2,35	4,51	0	1080
2	196	65	3,02		0
3	168	55	3,05		0
4	280	80	3,50		0
5	384	65	5,91		170
6	446	70	6,37		376
7	398	70	5,69		173
8	329	55	5,98		146
9	150	40	3,75		54
10	386	70	5,51		161

Пример расчетов:

Сравнительный анализ двух диаграмм

Сравнивая средневзвешенное время обращений (4.51 для SJF, 5.12 для FIFO) и общее время ожидания (1080 для SJF, 1226 для FIFO) можно сказать, что для обработки данного набора заданий больше подходит дисциплина обслуживания SJF. Это объясняется тем, что в исходном списке задач задачи с меньшей трудоемкостью затрачивают большие ресурсы (например, задача № 9), поэтому при FIFO эти задачи выполнялись в последнюю очередь, так как им не хватало ресурсов, тем самым задерживая выполнение системы.

Исходные данные для раздела 2

Предлагается построить временную диаграмму диспетчера по таблице задач.

Таблица 7. Таблица задач диспетчера

№ работы	Соответствие варианту из таблицы	Время поступления задания	Процессорное время	Приоритет задачи
1	6	6	20	3
2	9	15	50	2
3	2	17	40	2
4	0	17	70	1
5	9	26	50	2
6	8	34	40	1
7	4	38	60	1
8	2	40	40	2
9	6	46	20	3
10	4	50	60	1

Временные диаграммы строятся для двух различных дисциплин обслуживания: «LIFO» и «абсолютный приоритет».

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

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

Временная диаграмма диспетчера с ДО - LIFO

Дополнительные данные, описывающие временную диаграмму, изображённую на рисунке 7 приведены в таблице 8.

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

Таблица 8. Таблица дополнительных данных для ДО LIFO

№	Время	Очередь	Описание
1	26 - 27	[1]	В очередь поступает З1 - выделяем квант времени.
2	27 - 30	[4 1]	В начало очереди поступает задача 4. Выделяем кв. З1 переходит в конец очереди и получает кв.
3	30 - 32	[2 4 1]	В начало очереди поступает задача 2. Выделяем кв. З4 получает кв. З1 получает кв.
4	32 - 100	[3 2 4 1]	В начало очереди поступает задача 3. Выделяем кв. З2 получает кв. З4 получает кв. З1 получает кв. и завершает выполнение.
5	100 - 115	[3 2 4]	З3 получает кв. З2 получает кв. З4 получает кв.
6	115 - 187	[5 3 2 4]	В начало очереди поступает задача 5. Выделяем кв. З3 получает кв. и завершает выполнение. З2 получает кв. З4 получает кв.
7	187 - 197	[5 2 4]	З5 получает кв. З2 получает кв. З4 получает кв.
8	197 - 227	[10 7 5 2 4]	В начало очереди поступает задача 10. Выделяем кв. В начало очереди поступает задача 7. Выделяем кв. З5 получает кв. З2 получает кв. и завершает выполнение. З4 получает кв.
9	227 - 242	[10 7 5 4]	З10 получает кв. З7 получает кв. З5 получает кв. З4 получает кв.

Временная диаграмма диспетчера с ДО - абсолютный приоритет

Дополнительные данные, описывающие временную диаграмму, изображённую на рисунке 8 приведены в таблице 9. При этом очереди описываются в следующем формате. Так как очередей может быть несколько, каждая из них заключается в квадратные скобки: []. Очереди представлены в порядке по возрастанию.

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

Таблица 9. Таблица дополнительных данных для ДО - абсолютный приоритет

№	Время	Очередь	Описание
1	26 - 27	[][][1]	З1 поступает в третью очередь. З1 получает квант, так как очереди 1 и 2 пусты.
2	27 - 30	[4][][1]	З4 поступает в первую очередь. З4 из более приоритетной очереди первой получает кв. З1 получает кв. из последней очереди.
3	30 - 32	[4][2][1]	З2 поступает в очередь 2. З4 из более приоритетной очереди первой получает кв. Из второй очереди получает квант З2. З1 получает свой кв. из последней очереди.
4	32 - 100	[4][2 3][1]	З3 поступает в конец очереди 2. З4 из более приоритетной очереди первой получает кв. Из второй очереди получает квант сперва З2, затем З3. З1 получает свой кв. из последней очереди и завершает выполнение.
5	100 - 115	[4] [2 3][]	З4 из более приоритетной очереди первой получает кв. Из второй очереди получает квант сперва З2, затем З3.
6	115 - 187	[4] [2 3 5][]	З5 поступает в конец очереди 2. З4 из более приоритетной очереди первой получает кв.. Из второй очереди получает квант сперва З2, затем З3 получает свой кв. и завершает выполнение, затем свой кв. получает З5.
7	187 - 197	[4] [2 5][]	З4 из более приоритетной очереди первой получает кв. Из второй очереди получает квант сперва З2, затем З5.
8	197 - 227	[4 7 10] [2 5][]	З7 поступает в конец очереди 1. З10 поступает в конец очереди 1. З4 из более приоритетной очереди первой получает кв., затем З7, затем З10. Из второй очереди получает квант сперва З2 и завершает свое выполнение, затем свой квант получает З5.
9	227 - 242	[4 7 10] [5][]	З4 из более приоритетной очереди первой получает кв., затем З7, затем З10. Из второй очереди получает квант З5.

Список использованной литературы

1) Л. А. Коршикова. Операционные системы как системы управления вычислительными ресурсами: Учеб. пособие. - Новосибирск: Изд-во НГТУ, 2001. - 63 с.

2) Л. А. Коршикова. Основы операционных систем: Учеб. пособие - Новосибирск: Изд-во НГТУ, 2008. - 356 с.

3) Гордеев А. В. Операционные системы: учебник. - 2004.

4) Википедия - свободная энциклопедия [Электронный ресурс] -- Электрон. дан. -- [2011] - URL: http://ru.wikipedia.org/wiki/Страничная_память

Размещено на Allbest.ru