IV Международная студенческая научная конференция Студенческий научный форум - 2012

Введение

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

Большинство систем виртуальной памяти использует технологию под названием страничная организация памяти (paging). «Однако программисты обычно не знают,  какие страницы находятся в рабочем множестве, поэтому операционная система  периодически должна показывать это множество» [1, с. 234].

Рабочее множество имеет ограниченный размер, и все страницы, необходимые для работы программы, не могут храниться в нем. «Если программа обращается к странице, которая отсутствует в основной памяти, ее нужно вызвать с диска. Однако  чтобы освободить для нее место, на диск нужно отправить какую-нибудь другую  страницу.  Поэтому выбирать страницу для выгрузки просто наугад нельзя. Большинство операционных систем стараются предсказать, какие из страниц  в памяти наименее полезны в том смысле, что их отсутствие не повлияет сильно на  ход программы. Иными словами, вместо того чтобы удалять страницу, которая  скоро понадобится, необходимо выбрать такую страницу, которая не будет нужна долгое время» [там же, с. 238].

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

Обзор существующих учебных продуктов

Наиболее распространенным электронным ресурсом, демонстрирующим алгоритмы замещения страниц при страничной организации памяти, является  «Модель замещения страниц при страничной и сегментно-страничной организации памяти» (рис. 1) [3].

Преимущества данного учебного ресурса:

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

Недостатки:

• В интерфейсе много избыточности, наличие лишних полей для заполнения. Для различных категорий пользователей в зависимости от уровня их подготовки можно было бы использовать умолчания или давать возможность настраивать параметры замещения.
• Интерфейс не является интуитивно понятным. Например, кнопка «Запуск» может быть не понятна пользователю, так как не поясняется запуск чего произойдет при нажатии этой кнопки.
• Строку запросов нельзя создать меньшего размера. Программа генерирует запрос фиксированного размера (20 запросов). Для того, чтобы избавиться от данного недостатка нужно менять код программы.

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

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

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

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

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

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

Программа может быть использована при изучении курсов «Операционные среды, системы, оболочки», «Системное программное обеспечение», «Информационные среды, системы и сети» при проведении лабораторных работ, для демонстрации на лекционных занятиях для различных направлений подготовки в области ИТ («Бизнес-информатика», «Программная инженерия», «Прикладная математика и информатика» и др.). Удобство работы с  данной программой обеспечивается простотой и понятностью интерфейса.

Основные операции и допущения

Работа с программой начинается с запуска exe файла «Project2» (рис. 2). Главная форма позволяет выполнить работу с различными запросами страниц для алгоритмов FIFO, LRU, OPT (Оптимальный), NFU и улучшенный NFU.

Элементы главной формы:

• Число страниц не должно превышать 32.
• Число кадров не должно превышать 32.
• Запрос страниц содержит последовательность номеров страниц, перечисленных через запятую.
• Для задействования алгоритма замещения число кадров должно быть меньше числа страниц.
• В начальном состоянии среды эмулятора оперативная память не содержит ни одну страницу, в поле "Номер страницы" вставляется первый номер страницы из поля "Запрос страниц", очищаются счетчики NFU, устанавливаются счетчики OPT (подсчитывается количество вхождений номера каждой страницы в строку запроса).
• Номера страниц соответствуют порядковому номеру страницы в виртуальной памяти.
• Счетчики OPT и NFU показываются только в случае выбора соответствующего алгоритма замещения.
• В поле "Номер страницы" вы всегда можете ввести номер страницы, которую хотите запросить из виртуальной памяти, в независимости от того, что подставляется из поля "Запрос страниц".
• Поле "Частота проверки NFU" становится видимым только при выборе какой-либо из реализации NFU. Частота измеряется в количестве совершённых запросов к страницам. К примеру, если частота равна 2, то счетчик будет проверяться при 2м, 4м, 6м, 8м и т.д. запросе страницы.
• PF (page faults) - это «страничное нарушение» или исключительная ситуация.

Работа с программой

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

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

По нажатию на кнопку Запросить:

• - в случае нехватки свободных кадров происходит вытеснение из оперативной памяти страницы в соответствии с выбранным алгоритмом замещения;
• - производится вставка страницы в оперативную память;
• - добавляется запись в таблицу "Добавленные страницы" (в столбце "Результат" отображается, было ли Page Fault или нет);
• - если количество запросов страниц кратно частоте проверки NFU, то производится подсчёт счетчиков NFU;
• - производится уменьшение на 1 единицу счетчика OPT той страницы, которая была запрошена;
• - для каждого алгоритма выявляется, какая следующая страница будет замещена (результат выдаётся в списке "Следующая замещаемая страница");
• - в списке "Следующая замещаемая страница" показывается номер страницы, содержащейся в оперативной памяти, которая будет замещена;
• - в поле "Номер страницы" подставляется очередной номер страницы из поля "Запрос страниц" (если были взяты уже все номера страниц из этого поля, то поле "Номер страницы" очищается).

Алгоритм FIFO («First In First Out» - «Первым вошёл - первым вышел»). Выгружается страница, которая была загружена раньше всех. В качестве аналогии можно рассматривать очередь. При загрузке страницы, она помещается в конец очереди. Замещается та страница, которая находится в начале очереди (рис. 3) [2, с. 3].

Аномалия Билэди (аномалия FIFO). Явление, демонстрирующее следующий факт: не всегда больший размер оперативной памяти (количество кадров) приводит к меньшему количеству страничных нарушений (PF). Пример. Строка запрашиваемых страниц: 0,1,2,3,0,1,4,0,1,2,3,4. Стратегия замещения: FIFO. Результаты данной аномалии для системы с

• 3 кадрами - 9 page faults.
• 4 кадрами - 10 page faults [2, с 3].

Несмотря на то, что данный алгоритм является самым простым и наиболее понятным, у него есть существенный недостаток: в процессе его использования можно заменить активно использующуюся страницу, которая содержит важную информацию. Поэтому был разработан другой алгоритм - Оптимальный. Наиболее успешный алгоритм решения задачи замещения страниц. Выгружается страница, которая дольше всего не будет использоваться. Его реализация возможна, когда точно известна последовательность загружаемых страниц. В общем случае спрогнозировать эту последовательность невозможно [2, с. 4]. На рис. 5 показано диалоговое окно, в котором представлены результаты применения Оптимального алгоритма в системе с 4 кадрами.

Алгоритм LRU. («Least Recently Used» - «Наиболее давно использовавшаяся»). Он является противоположностью Оптимальному алгоритму и вытесняет страницу, которая дольше всего не использовалась (рис. 6) [2, с. 4].

Алгоритм NFU. («Not Frequently Used» - «редко использовавшаяся страница»). Для каждой страницы хранится флаг обращения и счётчик. Изначально (при загрузке) флаг сброшен и счётчик равен нулю. Периодически этот флаг проверяется у всех страниц. Если он установлен, значение счётчика у страницы увеличивается на единицу и флаг сбрасывается (рис. 7) [2, с. 4].

Алгоритм Улучшенный NFU («Not Frequently Used» - «редко использовавшаяся страница»). То же, что и NFU, но при наступлении времени проверки флагов значения счётчиков у всех страниц сдвигаются вправо на 1 бит (целочисленное деление пополам). Это нужно для того, чтобы «забывать» страницы, которые ранее использовались часто, но теперь не используются (рис. 8) [2, с. 4].

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

Предлагаемая программа позволяет увидеть результаты выполнения различных стратегий управления памятью и проанализировать результаты выполнения следующих алгоритмов замещения страниц: FIFO, LRU, OPT (Оптимальный), NFU и улучшенный NFU.

Заключение

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

Библиографический список

1. Основы операционных систем. Курс лекций. Учебное пособие / В.Е.Карпов, К.А.Коньков / Под ред. В.П. Иванникова. - М: ИНТУИТ.РУ, 2004. - 632 с.
2. Рекламно-техническое описание «Модель замещения страниц при страничной организации памяти» .48411971.00001-01 99 01, 9 л.
3. Сайт студентов факультета ФИПМ ПСТГУ [Электронный ресурс]. URL: http://pstgu-math.narod2.ru/JAVA_applets/OS_i_obolochki__2_kurs_/ZameshenieStranits.html (дата обращения: 28.01.2012).
4. Интернет-Университет Информационных Технологий [Электронный ресурс]. URL: http://www.natalka1122.com/rkt/Modern_OS/question_44.html (дата обращения: 28.01.2012).