Нарушение условия кругового ожидания

Осталось одно условие. Циклического ожидания можно избежать несколькими путями.

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

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

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

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

Заключение.

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

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

Считается, что в будущих системах тупики станут более критичным фактором, так как системы будущего:

· будут в большей степени ориентированы на параллельную работу

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

· растет тенденция рассматривать данные как ресурс, в связи с чем количество ресурсов возрастет.

Более подробно данная тема рассмотрена в [9,12,22 и др.]

Часть III. Управление памятью.

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

Глава 8. Введение. Простейшие схемы управления памятью.

Введение.

Главная задача компьютерной системы - выполнять программы. Программы, в течение выполнения, вместе с данными, к которым они имеют доступ должны (по крайней мере, частично) находиться в главной (основной, оперативной) памяти. Таким образом, память (storage, memory) является важнейшим ресурсом, требующим тщательного управления. В недавнем прошлом память - самый дорогой ресурс.

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

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

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

И, наконец, идея локальности. Свойство локальности присуще природе. Пространственная локальность - соседние объекты характеризуются похожими свойствами (если в данной местности хорошая погода, то вероятнее всего, что в близкой окрестности также хорошая погода). Временная локальность - если в 15:00 была хорошая погода, то, вероятно, что и в 14:30 и в 15:30 также наблюдалась хорошая погода. Свойство локальности (скорее эмпирическое) присуще и работе ОС. Фактически свойство локальности объяснимо, если учесть, как пишутся программы и организованы данные, то есть обычно в течение какого-то отрезка времени ограниченный фрагмент кода работает с ограниченным набором данных. Понимание данной особенности позволяет организовать иерархию памяти, используя быструю дорогостоящую память для хранения минимума необходимой информации, размещая оставшуюся часть данных на устройствах с более медленным доступом и подкачивая их в быструю память по мере необходимости. Типичный пример иерархии: регистры процессора, кэш процессора, главная память, внешняя память на магнитных дисках (вторичная память).

Главная память - это массив слов или байт. Каждое слово имеет свой адрес. Использование вторичной памяти (хранение данных на дисках) в качестве расширения главной дает дополнительные преимущества. Во-первых, главная память слишком мала, чтобы содержать все необходимые программы и данные постоянно. Во-вторых, главная память есть изменчивое (volatile) устройство, которое теряет свое содержимое, когда питание отключено или по другим причинам. Одно из требований к вторичной памяти - умение хранить большие объемы данных постоянно.

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

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

• Механизм управления памятью или идеологию построения системы управления.
• Архитектурные особенности используемой системы.
• Структуры данных в ОС, используемые для управления памятью.
• Алгоритмы, используемые для управления памятью.

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

Связывание адресов.

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

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

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

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

Максимальный размер логического адресного пространства обычно определяется разрядностью процессора (например, 2**32) и в современных системах значительно превышает размер физического адресного пространства.

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

Обычно программа проходит нескольких шагов:

· текст на алгоритмическом языке,

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

Используемые программой адреса в каждом конкретном случае могут быть представлены различными способами. Например, адреса в исходных текстах обычно символические. Компилятор связывает эти символические адреса с перемещаемыми адресами (такими как n байт от начала модуля). Загрузчик или линкер, в свою очередь, связывают эти перемещаемые адреса с виртуальными адресами. Каждое связывание - отображение одного адресного пространства в другое.

Рис. 8.1 Этапы связывания адресов.

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

· Этап компиляции (Compile time). Когда на стадии компиляции известно точное место размещения процесса в памяти, тогда генерируются абсолютные адреса. Если стартовый адрес программы меняется, необходимо перекомпилировать код. В качестве примера можно привести .com программы MS-DOS, которые связывают ее с физическими адресами на стадии компиляции.

· Этап загрузки (Load time). Если на стадии компиляции не известно где процесс будет размещен в памяти, компилятор генерирует перемещаемый код. В этом случае окончательное связывание откладывается до момента загрузки. Если стартовый адрес меняется, нужно всего лишь перезагрузить код с учетом измененной величины.

· Этап выполнения (Execution time). Если процесс может быть перемещен во время выполнения из одного сегмента памяти в другой, связывание откладывается до времени выполнения. Здесь желательно специализированное оборудование, например регистры перемещения. Их значение прибавляется к каждому адресу, сгенерированному процессом. Например, MS-DOS использует четыре таких (сегментных) регистра.