Глава 4 (Методическое пособие по Операционным системам)

139

Глава 4

Управление памятью

Память представляет собой важный ресурс, требующий тщательного управления. Несмотря на то что в наши дни память среднего домашнего компьютера в тысячи раз превышает ресурсы IBM 7094 — машины, бывшей в начале 60-х годов самой мощной в мире, — программы все равно увеличиваются в размере быстрее, чем намять. Перефразированный закон Паркинсона гласит: «Программы расширяют­ся, стремясь заполнить весь объем памяти, доступный для их поддержки». В этой главе мы рассмотрим, как операционная система управляет памятью.

В идеале каждый программист хотел бы иметь неограниченную в размере и ско­рости память, при этом также являющуюся энергонезависимой, то есть сохраняю­щую свое содержимое при выключении электричества — отключении от источ­ников питания Раз уж мы взялись за эту тему, то почему бы заодно не помечтать o дешевой памяти? К сожалению, технологии не могут обеспечить подобную па­мять. Вследствие этого память в компьютерах имеет иерархическую структуру. Небольшая часть ее представляет собой очень быструю, дорогую, энергозависи­мую (то есть теряющую информацию при выключении питания) кэш-память. Кро­ме того, компьютеры обладают десятками мегабайт среднескоростной, имеющей среднюю цену, также энергозависимой оперативной памяти ОЗУ (RAM) и десят­ками или сотнями гигабайт медленного, дешевого, энергонезависимого простран­ства на жестком диске. Одной из задач операционной системы является коорди­нация использования всех этих составляющих памяти.

Часть операционной системы, отвечающая за управление памятью, называется Модулем управления памятью или менеджером памяти. Он следит за тем, какая Часть памяти используется в данный момент, а какая — свободна; при необходимос­ти выделяет память процессам и по их завершении освобождает ресурсы; управляет обменом данных между оперативной памятью и диском, если память слишком мала для того, чтобы вместить все процессы.

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

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

Основное управление памятью

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

С другой стороны, выше уже упоминалось, что программное обеспечение растет еще быстрее, чем память, поэтому вполне возможно, что потребность в рациональ­ном и эффективном управлении памятью будет существовать всегда. В 80-е годы многие университеты использовали системы разделения времени для работы десятков (более-менее довольных) пользователей на машинах VAX с объемом памяти 4 Мбайт. Сейчас компания Microsoft рекомендует для индивидуальной работы в системе Windows 2000 устанавливать на компьютер, по меньшей мере, 64 Мбайт оперативной памяти. Дальнейшее развитие в сторону мультимедийных систем накладывает еще большие требования на память. Таким образом, весьма вероятно, что качество управления этой частью компьютера будет актуальным по крайней мере в течение следующего десятилетия.

Однозадачная система без подкачки на диск

Самая простая из возможных схем управления памятью заключается в том, что в каждый конкретный момент времени работает только одна программа, при этом память разделяется между программами и операционной системой. На рис. 4.1 показаны три варианта такой схемы. Операционная система может находиться в нижней части памяти, то есть в ОЗУ (оперативное запоминающее устройство)- RAM (Random Access Memory — память с произвольным доступом) — см. рис. 4.1,a. Или же операционная система может располагаться в самой верхней части памя­ти—в ПЗУ (постоянное запоминающее устройство, ROM (Read-Only Memory — память только для чтения)), как продемонстрировано на рис. 4.1, б. И третий спо­соб: драйверы устройств могут находиться наверху в ПЗУ, а остальная часть сиcтемы — в ОЗУ, расположенной ниже, как показано на рис. 4.1, в. Первая модель раньше применялась на мэйнфреймах и мини-компьютерах, но в настоящее время практически не употребляется. Вторая схема сейчас используется на некоторых карманных компьютерах и встроенных системах, а третья модель устанавливалась на ранних персональных компьютерах (например, работающих с MS-DOS), при этом часть системы в ПЗУ носила название BIOS (Basic Input Output System — базовая система ввода-вывода).

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

0xFFF

а б в

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

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

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

Самый легкий способ достижения многозадачности представляет собой про­стое разделение памяти на n (возможно, не равных) разделов. Такое разбиение можно выполнить, например, вручную при запуске системы. Cтановится очевидным, когда к большому разделу нет очереди, в то время как к маленькому выстроилось довольно много задач; в нашем примере на рис. 4.2, а это разделы 1 и 3.

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

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

Рис. 4.2. Фиксированные разделы памяти с отдельными входными

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

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

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

Подобная схема, где утром оператор задает фиксированные разделы и пос­ле этого они не изменяются, в течение многих лет использовалась в системах OS/360 на больших мэйнфреймах компании IBM. Она носила название MFT (Multiprogramming with a Fixed number of Tasks — мультипрограммирование с фик­сированным количеством задач, или OS/MFT). Она легка для понимания и не менее проста в исполнении: входящее задание стоит в очереди до тех пор, пока не станет доступным соответствующий раздел, затем оно загружается в этот раздел памяти и там работает до завершения процесса. Сейчас очень мало (если они вооб­ще сохранились) операционных систем, поддерживающих такую модель.

Моделирование многозадачности

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

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

Степень загрузки центрального процессора = 1 – рⁿ.

На рис. 4.3 показана зависимость степени использования центрального про­цессора от числа n, называемого степенью многозадачности.

Рис. 4.3. Зависимость степени загрузки центрального процессора от количества процессов в памяти

Из рисунка понятно, что если процессы проводят 80 % своего времени в ожи­дании завершения операции ввода-вывода, то для того, чтобы получить потерю времени процессора ниже 10 %, в памяти должны одновременно находиться, по меньшей мере, 10 процессов. Когда вы представляете себе, что интерактивный процесс, ожидая, пока пользователь напечатает что-либо на терминале, находится в состоянии ожидания ввода-вывода, должно быть ясно, что время ожидания ввода-вывода, равное 80 % и больше, не является необычным. Но даже в системах па­кетной обработки процессы, выполняющие ввод-вывод в основном с диска, часто имеют такой же или больший процент.

Нужно отметить, что описанная выше вероятностная модель является доволь­но грубым приближением. Она неявно предполагает, что все n процессов незави­симы, то есть допустима следующая ситуация: в памяти находятся пять процес­сов, из них три работают, а два ждут. Но когда в системе присутствует один единственный центральный процессор, он не может одновременно обрабатывать три процесса, поэтому уже готовый к работе процесс обязан ждать освобождения процессора. Таким образом, в реальности процессы не являются независимыми. Более аккуратную модель можно построить с использованием теории организа­ции очередей, но общая идея, на которую мы обратили внимание - многозадач­ность позволяет процессам использовать центральный процессор тогда, когда при других обстоятельствах он бы бездействовал, - конечно, останется в силе, даже если кривые на рис. 4.3 немного изменятся.

Хотя модель на рис. 4.3 очень проста, тем не менее она позволяет сделать оп­ределенный, хотя и приблизительный, прогноз относительно производительно­сти центрального процессора. Например, предположим, что компьютер имеет 32 Мбайт памяти, 16 Мбайт отдано операционной системе, а каждая программа пользователя занимает по 4 Мбайт. При таких заданных размерах одновременно можно загрузить в память четыре пользовательские программы. При 80 % време­ни на ожидание ввода-вывода в среднем мы получим загруженность процессо­ра (игнорируя издержки операционной системы) равной 1-0,8⁴, или около 60 %. Добавление еще 16 Мбайт памяти позволит системе повысить степень многоза­дачности от четырех до восьми и таким образом повысить степень загрузки процессора до 83 %. Другими словами, дополнительные 16 Мбайт увеличат про­изводительность на 38 %.

Еще 16 Мбайт могли бы повысить загрузку процессора с 83 до 93 %, таким об­разом, увеличив производительность всего лишь на 12 %. С помощью этой модели владелец компьютера может решить, что первые 16 Мбайт оперативной памяти - это хорошее вложение капитала, а вторые - нет.

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