2 Программирование на языке высокого уровня



страница8/29
Дата29.11.2016
Размер3.73 Mb.
Просмотров7050
Скачиваний0
1   ...   4   5   6   7   8   9   10   11   ...   29

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

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

  • Транзакция А создает общую блокировку строки 1.

  • Транзакция Б создает общую блокировку строки 2.

  • Транзакция А теперь запрашивает монопольную блокировку строки 2 и блокируется до того, как транзакция Б закончится и освободит общую блокировку строки 2.

  • Транзакция Б теперь запрашивает монопольную блокировку строки 1 и блокируется до того, как транзакция A закончится и освободит общую блокировку строки 1.

Транзакция А не может завершиться до того, как завершится транзакция Б, а транзакция Б заблокирована транзакцией А. Такое условие также называется цикличной зависимостью: транзакция А зависит от транзакции Б, а транзакция Б зависит от транзакции А и этим замыкает цикл.

Тупик возникает при перестановке местами операций P(e) и P(b) в примере с процессами “читатель” и “писатель”, рассмотренном выше – ни один из этих потоков не сможет завершить начатую работу и возникнет тупиковая ситуация, которая не может разрешиться без внешнего воздействия.


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

Однако очередь – неотъемлемый признак высокого коэффициента использования ресурсов при случайном поступлении запросов а тупик – “неразрешимая” ситуация.

Проблема тупиков требует решения следующих задач:

-распознавание тупиков,

-предотвращение тупиков,

-восстановление системы после тупиков.

Распознавание тупиков

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

Предотвращение тупиков

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

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

Восстановление системы после тупиков

При возникновении тупиковой ситуации не обязательно снимать с выполнения все заблокированные процессы, а можно:

  • снять только часть из них, при этом освобождая ресурсы, ожидаемые остальными процессами

  • вернуть некоторые процессы в область «свопинга»

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


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

  1. Простейшие схемы управления памятью. Связывание логических и физических адресных пространств.

Распределение памяти:

В однопрограммных ОС:

Непрерывное

Оверлейное

В мультипрограммных ОС:

Фиксированными разделами

Динамическими разделами

Перемещаемыми разделами



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

Область, занимаемая ОС

Область, в которой размещается исполняемый процесс

Свободная область памяти

Такая схема распределения влечет за собой два вида потерь вычислительных ресурсов:

Потерю процессорного времени, потому что процессор простаивает, пока задача ожидает завершения операций ввода-вывода

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

(+)


Недорогая реализация, которая позволяет отказаться от многих второстепенных функций ОС, например, защита памяти – единственное, что следует защищать - программные модули и области памяти самой ОС)

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

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

Поочередно можно загружать в память ветви А-В, А-С-D и А-С-Е программы



Мультипрограммные ОС

Для организации мультипрограммного режима необходимо обеспечить одновременное расположение в ОП нескольких задач (целиком или частями)

При решении этой задачи ОС должна учитывать целый ряд моментов:

Следует ли назначать каждому процессу одну непрерывную область физической памяти или фрагментами

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

Что следует предпринять, если сегменты программы не помещаются в имеющуюся память





Распределение памяти фиксированными разделами

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

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

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



Подсистема управления памятью в этом случае выполняет следующие задачи:

Сравнивает объем памяти, требуемый для вновь поступившего процесса, с размерами свободных разделов и выбирает подходящий раздел

Осуществляет загрузку программы в один из разделов и настройку и настойку адресов

(+): простота

(-):Существенные потери памяти от внутренней фрагментации

Учитывая то, что в каждом разделе может выполняться только один процесс, то уровень мультипрограммирования заранее ограничен числом разделов, так как независимо от размера программы она будет занимать весь раздел

Применялся в ранних мультипрограммных ОС, сейчас – в ОСРВ за счет детерминированности вычислительного процесса и небольших затрат на реализацию



Распределение памяти динамическими разделами

Чтобы уменьшить потери от внутренней фрагментации, целесообразно размещать в ОП задачи «плотно», одну за другой, выделяя ровно столько памяти, сколько задача потребует (распределение памяти динамическими разделами)

Обобщенный алгоритм:

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

После завершения процесса память освобождается, и на это место может быть загружен другой процесс

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

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

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

загрузка задачи в выделенный ей раздел и корректировка таблиц свободных и занятых областей,

после завершения задачи корректировка таблиц свободных и занятых областей.

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

"первый попавшийся раздел достаточного размера"(first fit)

"раздел, имеющий наименьший достаточный размер"(best fit)

"раздел, имеющий наибольший достаточный размер"(worst fit)

(+)

Значительная гибкость



(-)

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



Распределение памяти динамическими разделами

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



Дефрагментация может выполняться:

При каждом завершении задачи (меньше однократной вычислительной работы)

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

(+) более эффективное использование памяти

(-) требует значительных временных затрат



Задачи по управлению памятью

отслеживание свободной и занятой памяти

выделение и освобождение памяти процессам

вытеснение процессов из ОП на диск, когда размеры основной памяти не достаточны для размещения в ней всех процессов

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

настройка адресов программы на конкретную область физической памяти

зашита памяти (не позволит выполняемому процессу записывать или читать данные из памяти, назначенной другому процессу). Функция, как правило, реализуется программно – аппаратными средствами

Типы адресации

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

Возможны различные варианты перехода от символьных имен к физическим адресам.

Частным случаем отображения пространства имен является полная тождественность виртуального адресного пространства физической памяти (система программирования генерирует абсолютную двоичную программу)

Часть программных модулей любой ОС обязательно должны быть абсолютными двоичными программами (например, программы загрузки)


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

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

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



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

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

  • Объем ввода-вывода для выгрузки части программы на диск может быть меньше, чем в варианте классического свопинга, в итоге каждая программа будет работать быстрее.

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

Архитектурные средства поддержки виртуальной памяти делятся на сегментные, страничные и сегментно-страничные распределения памяти.

Сегментный

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

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

img00019

Логически обращение к элементам программы в этом случае будет состоять из имени сегмента и смещения относительно начала этого сегмента.

Вся информация о текущем размещении сегментов задачи в памяти сводится в таблицу сегментов (таблицу дескрипторов сегментов задачи), формируемую для каждого исполняемого процесса.

При размещении каждого из сегментов в оперативной или внешней памяти ОС отмечает в дескрипторе текущее местоположение сегмента.

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

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

Поэтому:

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

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

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

FIFO (First In First Out) первый пришёл – первый ушёл

LRU (Least Recently Used ) не используемый дольше других

LFU (Least Frequently Used) используемый реже других

Random-случайный выбор сегмента



Страничный способ при котором все фрагменты задач считаются равными, причем длина фрагмента в идеале должна быть кратна степени 2, чтобы операции сложения можно было заменить операциями конкатенации.

Часть виртуальных страниц задачи могут быть размещены в ОП, а часть – во внешней памяти.

Место во внешней памяти называют файлом подкачки, или страничным файлом(paging file). Иногда это файл называют swap – файлом, тем самым подчеркивая, что записи этого файла – страницы – замещают друг друга в ОП

img00017.gif

Разбиение всей ОП на страницы одинаковой величины, причем кратной степени двойки, приводит к тому, что вместо одномерного адресного пространства памяти можно говорить о двумерном. Первая координата адресного пространства – это номер страницы, вторая координата – номер ячейки внутри выбранной страницы (индекс).

Таким образом, физический адрес определяется парой (Рр, i), а виртуальный адрес – парой (Pv, i), где Pv – номер виртуальной страницы, Рр – номер физической страницы, i – индекс ячейки внутри страницы

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

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

Однако в ОС Windows NT/2000/XP разработчики, желая сделать их максимально независимыми от аппаратных возможностей процессора, отказались от этой дисциплины и применили правило FIFO. Поэтому, чтобы компенсировать ее неэффективность была введена «буферизация» тех страниц, которые должны быть записаны в файл подкачки на диск или просто расформированы. Принцип буферизации следующий: прежде чем замещаемая страница действительно окажется во внешней памяти или просто расформированной, она помечается как «кандидат на выгрузку».

Если в следующий раз произойдет обращение к странице, находящейся в таком «буфере», то страница никуда не выгружается и уходит в конец списка FIFO

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

Величина «буфера» не может быть большой, поэтому эффективность страничной реализации памяти в Windows NT/2000/XP намного ниже, чем в других ОС, и явление пробуксовки проявляется даже при относительно большом объеме ОП

Структура таблицы страниц

Многоуровневые таблицы страниц

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

В 32-битном адресном пространстве при размере страницы 4 Кбайт (Intel) получаем 232/212=220, то есть приблизительно 106 страниц – таблица должна иметь примерно 106 строк, а запись в строке состоит из нескольких байтов. Каждый процесс нуждается в своей таблице страниц.

Для того чтобы избежать размещения в памяти огромной таблицы, ее разбивают на ряд фрагментов.

В ОП хранят лишь некоторые, необходимые для конкретного момента исполнения фрагмента таблицы страниц.

В силу свойства локальности число таких фрагментов относительно невелико.



Локальность – способность в течение ограниченного отрезка времени работать с небольшим набором адресов памяти.

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

Одним из наиболее распространенных способов разбиения является организация так называемой многоуровневой таблице страниц.



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

Количество уровней в таблице страниц зависит от конкретных особенностей архитектуры.

Примером реализации одноуровневого (DEC PDP-11), двухуровневого (Intel, DEC VAX), трехуровневого (Sun SPARC, DEC Alpha) пейджинга, а также пейджинга с заданным количеством уровней (Motorola).

Инвертированная таблица страниц

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

Например, для Pentium с 256 Мбайт ОП нужна таблица размером 64 Кбайт строк.

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

Один из способов решения данной проблемы – использование хеш-таблицы виртуальных адресов.

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



Инвертированная таблица страниц

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

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

Ассоциативная память

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

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

Это устройство называют ассоциативной памятью или буфером поиска трансляции (translation lookaside buffer - TLB).

Высокое значение вероятности нахождения данных в ассоциативной памяти связано с наличием у данных объективных свойств: пространственной и временной локальности.




Поделитесь с Вашими друзьями:
1   ...   4   5   6   7   8   9   10   11   ...   29


База данных защищена авторским правом ©nethash.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал