Алгоритмы со счетчиком

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

· - Алгоритм Least Frequently Used (LFU):замещать страницы с минимальным значением счетчика (к которым было меньше всего обращений);

· - Алгоритм Most Frequently Used (MFU):замещать страницы с максимальным значением счетчика. Данный алгоритм основан на соображении, что страница с минимальным счетчиком – возможно, лишь недавно загружена, и, видимо, в дальнейшем будет активно использоваться, поэтому она оставляется в памяти.

Выделение фреймов

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

Однако различные аппаратные платформы имеют свои особенности, что тоже приходится учитывать. Например, в системе IBM 370 требуется 6 (!) страниц, чтобы обработать команду MOVE (пересылки) формата SS (Storage-Storage). В самом деле, длина команды - 6 байтов, так что она может размещается на двух соседних страницах. Кроме того, максимум две страницы требуются для обработки источника и максимум две страницы – для обработки получателя. Разумеется, подобный казус не может произойти в RISC-системах.

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

Фиксированное выделение фреймов.Наиболее простой вариант - равномерное распределениефреймов процессам. Например, если имеется 100 фреймов и 5 процессов, каждому выделяется по 20 страниц. Используется также пропорциональное распределение– выделять фреймы в соответствии со следующим принципом: если общее число фреймов m, размер процесса – s, а общий размер всех процессов – S, то общее число фреймов, выделенных процессу, равно:

a = m * (s / S).

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

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

Thrashing

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

Неформально, thrashing означает катастрофическую нехватку фреймов в основной памяти. На практике для пользователя это выглядит следующим образом (автор сам неоднократно испытывал подобные ощущения, вынужденный работать на SPARC-станции с очень малым объемом памяти): жесткий диск буквально "надрывается" от непрерывных обращений, а процесс исполняется крайне медленно. Интересно отметить, чтоSPARC-станция с 32 мегабайтами памяти и ОС Solaris успешно выдерживали эти экстремальные нагрузки (причем на данной конфигурации пропускалась достаточно большая Java-программа). Это говорит о высокой надежности системы Solaris.

Другой реальный пример – использование ОС Windows XP (Service Pack 3) на компьютере с 512 мегабайтами памяти. При этом возникает почти такое же ощущение - сначала кажется, что неисправен жесткий диск, но затем сразу осознаешь, что все дело в нехватке памяти: самые простые программы, такие как Internet Explorer, Windows Explorer и др., будучи вызванными одновременно (что является обычной практикой) переполняют основную память и вынуждают операционную систему при любом дополнительном действии пользователя (даже при простом передвижении полосы прокрутки по именам файлов в Windows Explorer) непрерывной откачкой и подкачкой.

На рис.15 приведен график зависимости использования процессора от коэффициента мультипрограммирования. При очень большом числе обрабатываемых процессов полезность использования процессора резко падает из-за постоянных откачек и подкачек. Это и есть thrashing.

Рис. 15. График зависимости использования процессора от коэффициента мультипрограммирования