Система двойников
Характеристика особенностей виртуальной памяти, основанной на страничной организации и сегментации. Анализ модифицированной версии системы двойников, которая используется для распределения памяти ядром unix. Изучение системного программного обеспечения.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 04.05.2016 |
Размер файла | 1,3 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
Введение
1. Постановка задачи
1.1 Теоретическое введение
1.1.1 Фиксированное распределение
1.1.2 Динамическое распределение
1.1.3 Простая страничная организация
1.1.4 Простая сегментация
1.1.5 Система двойников
1.2 Постановка задачи
2. Разработка
2.1 Диаграмм прецедентов
2.2 Диаграмм последовательности
2.4 Разработка архитектуры приложения
2.5 Разработка алгоритмов работы программы
2.6 Выбор структуры данных
3. Верификация и тестирование программы
3.1 Верификация программы
3.2 Тестируемые функции
3.3 Разработка тестовых случаев
4. Руководство оператора
4.1 Назначение программы
4.2 Условия выполнения программы
4.3 Выполнение программы
Выводы
Перечень ссылок
Приложения
Введение
Работа посвящена управлению памятью, являющейся фундаментальным вопросом в операционных системах. Память является очень важным ресурсом, поэтому требуется эффективное управление ею. Данную проблему можно решить при помощи алгоритма «Система двойников».
Примером одной из основных частей ОС является менеджер распределения памяти. Главной операцией управления памятью является размещение программы в основной памяти для ее выполнения процессором. Практически во всех современных многозадачных системах эта задача предполагает использование сложной схемы, известной как виртуальная память. Виртуальная память, в свою очередь, основана на использовании одной или обеих базовых технологий -- сегментов и страниц.
Система двойников представляет собой разумный компромисс для преодоления недостатков схем фиксированного и динамического распределения, но в современных операционных системах ее превосходит виртуальная память, основанная на страничной организации и сегментации. Однако система двойников нашла применение в параллельных системах как эффективное средство распределения и освобождения параллельных программ. Модифицированная версия системы двойников используется для распределения памяти ядром UNIX.
Поэтому необходимо разработать программу для изучения этого алгоритма, которая позволит моделировать его работу при выделении и освобождении памяти. Данная программа может применяться как пособие-пример студенту, моделирующая работу менеджера памяти.
Для разработки программы используется язык программирования C# поддерживающий спецификацию компании производителя Microsoft. Для проектирования используется среда разработки Microsoft Visual Studio 2013 и платформа .NET Framework 4.51.
В качестве дальнейших улучшений программы могут выступать изменения ее интерфейса для более гибкой настройки системы, возможность сохранения состояния памяти для дальнейшей работы с ними между запусками программы, добавления других алгоритмов распределения памяти, улучшения функции визуализации.
Результатом данной работы должна быть программа, которая сможет использоваться в процессе образования людьми, которым интересны основы системного программного обеспечения.
1. Постановка задачи
1.1 Теоретическое введение
Оперативная память - это важнейший ресурс любой вычислительной системы, поскольку без неё невозможно выполнение ни одной программы.
Процесс - программа во время выполнения.
Память является важнейшим ресурсом, требующим тщательного управления со стороны мультипрограммной операционной системы. Распределению подлежит вся оперативная память, не занятая операционной системой. Главной операцией управления памятью является размещение программы в основной памяти для ее выполнения процессором, выполнением данной функции занимается менеджер памяти, использующий определенные методы распределения. Существует различные способы распределения памяти.
1.1.1 Фиксированное распределение
Основная память разделяется на ряд статических разделов во время генерации системы. Процесс может быть загружен в раздел равного или большего размера. Сильной стороной данного метода являются простота реализации, малые системные накладные расходы. К минусам относятся неэффективное использование памяти из-за внутренней фрагментации, фиксированное максимальное количество активных процессов.
1.1.2 Динамическое распределение
Для преодоления сложностей, связанных с фиксированным распределением, был разработан альтернативный подход, известный как динамическое распределение. При динамическом распределении образуется переменное количество разделов переменной длины. При размещении процесса в основной памяти для него выделяется строго необходимое количество памяти, и не более. В данном методе отсутствует внутренняя фрагментация и более эффективное использование основной памяти, но в тоже время неэффективное использование процессора из-за необходимости уплотнения для противодействия внешней фрагментации.
1.1.3 Простая страничная организация
Основная память распределена на ряд кадров равного размера. Каждый процесс распределен на некоторое количество страниц равного размера и той же длины, что и кадры. Процесс загружается путем загрузки всех его страниц в доступные, но необязательно последовательные, кадры. Отсутствует внешняя фрагментация, но присутствует небольшой внутренней фрагментации.
1.1.4 Простая сегментация
Каждый процесс распределен на ряд сегментов. Процесс загружается путем загрузки всех своих сегментов в динамические (обязательно смежные) разделы. Отсутствует внутренняя фрагментация, улучшенное использование памяти и сниженные накладные расходы по сравнению с динамическим распределением.
1.1.5 Система двойников
Как фиксированное, так и динамическое распределение памяти имеют свои недостатки. Фиксированное распределение ограничивает количество активных процессов и неэффективно использует память при несоответствии между размерами разделов и процессов. Динамическое распределение реализуется более сложно и включает накладные расходы по уплотнению памяти. Интересным компромиссом в этом плане является система двойников.
В системе двойников память распределяется блоками размером 2к, L < К < U , где 2L - минимальный размер выделяемого блока памяти; 2U - наибольший распределяемый блок.
Вначале все доступное для распределения пространство рассматривается как единый блок размера 2U. При запросе размером S, таким, что 2U-l < S < 2U, выделяется весь блок. В противном случае блок разделяется на два эквивалентных двойника с размерами 2U-1. Если 2U-2 < S < 2U-l, то по запросу выделяется один из двух двойников; в противном случае один из двойников вновь делится пополам. Этот процесс продолжается до тех пору пока не будет сгенерирован наименьший блок.
Система двойников постоянно ведет список "дыр" (доступных блоков) для каждого размера 2L. Дыра может быть удалена из списка (I+1) разделением ее пополам и внесением двух новых дыр размера 2L-1 в список I. Когда пара двойников в списке i оказывается освобожденной, они удаляются из списка и объединяются в единый блок в списке (i+1).
На рисунке 1.1 приведен пример использования блока с начальным размером 1024 КБ. Первый запрос А - 70 КБ (для него требуется блок размером 128 КБ); Для этого начальный блок делится на два двойника по 512 КБ. Первый из них делится на двойники размером 256 КБ, и, в свою очередь, первый из получившихся при этом разделении двойников также делится пополам. Один из получившихся двойников размером 128 КБ выделяется запросу А. Следующий запрос В - 35 КБ. Наименьший блок - 128 КБ, разделяем его и один из получившихся блоков выделяем запросу B. Процесс продолжается с разделением и слиянием двойников при необходимости. Обратите внимание, что после освобождения блока D происходит слияние двойников по 64 КБ в один блок размером 128 КБ, который, в свою очередь, тут же сливается со своим двойником.
Рисунок 1.1 - Пример работы алгоритма системы двойников
Система двойников представляет собой разумный компромисс для преодоления недостатков схем фиксированного и динамического распределения, но в современных операционных системах ее превосходит виртуальная память, основанная на страничной организации и сегментации. Однако система двойников нашла применение в параллельных системах как эффективное средство распределения и освобождения параллельных программ. Модифицированная версия системы двойников используется для распределения памяти ядром UNIX.
1.2 Постановка задачи
Программа, полученная в результате этого проекта должна моделировать алгоритм распределения памяти Система двойников. Результаты работы программы должны выводиться на экран состояние памяти в виде последовательных занятых и свободных блоков.
Пользователю должна быть предоставлена возможность задавать параметры памяти, для этого в GUI присутствуют область для ввода параметров памяти, таких как размера памяти, минимальный размер блока, единицы измерения. виртуальный unix программный
Также пользователь может вводить параметры процесса, для этого в GUI присутствуют область для ввода параметров процесса: имя и размер. А также возможность выделить память для процесса и освободить память занятую процессом.
Пользователю так же должна быть предоставлена возможность загрузки списка процессов с файлов или сохранения текущего списка в файл.
Пользователю должна быть предоставлена возможность визуализации состояния памяти и списка процессов.
В том случае, если пользователь неправильно ввел значения, выбрал некорректный файл или задал слишком большой или маленький размер блока, программа должна вывести предупреждение об ошибке.
По умолчанию, размер памяти будет измеряться в КБ и будет равен 1024, минимальный размер выделяемого блока - 64 КБ.
Предполагаемая структура GUI изображена на рисунке 1.2.
Рисунок 1.2 - Интерфейс разрабатываемой Программы
2. Разработка
2.1 Диаграмм прецедентов
Проведя анализ поставленной задачи, были выявлены следующие активные актеры, работающий с разрабатываемой программой:
- Пользователь;
- файловая система.
Функции, которые могут использовать пользователь и файловая система, а также отношения между ними, можно визуализировать с помощью диаграммы прецедентов (рисунок 2.1).
Рисунок 2.1 - Диаграмма прецедентов
Прецедент <<Выделить память>> заключается в возможности выделить память под новый процесс.
Прецедент <<Освободить память>> заключается в возможности освободить выделенную память под процесс.
Прецедент <<Ввод параметров процесса >> заключается в возможности ввести параметры процесса.
Прецедент << Ввод параметров памяти>> заключается в возможности задать новые параметры памяти.
Прецедент <<Загрузить с файла>> заключается в возможности загрузить список процессов из выбранного файла.
Прецедент <<Сохранить в файл>> заключается в возможности сохранить список процессов в файл.
Прецедент <<Выбрать процесс>> заключается в возможности выбрать процесс из списка процессов.
Прецедент <<Выбрать файл>> заключается в возможности выбрать файл с данными.
Прецедент <<Ввести имя файла>> заключается в возможности ввести имя файл.
Прецедент <<Считывание с файла>> заключается в возможности считать данные с файла.
Прецедент <<Запись в файл>> заключается в возможности записать в новый файл данные.
Прецедент <<Настройка памяти>> заключается в возможности настроить память.
Прецедент <<Проверка корректности>>заключается в возможности проверить данные на корректность.
Прецедент <<Выполнение алгоритма>> заключается в возможности выполнения алгоритм распределения памяти.
Прецедент <<Визуализация>> заключается в возможности визуализации результатов действий пользователя и программы.
Прецедент <<Выход>> заключается в возможности завершения работы с программой.
Опишем варианты использования.
Прецедент<< Выделение памяти >>
Номер |
ID-1 |
|
Название |
Выделение памяти |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования пользователь выделяет память под процесс |
|
Предварительные условия |
1. Введены параметры процесса |
|
Выходные условия |
Блок памяти выделен |
|
Порядок действия |
1. Пользователь нажимает на кнопку «Выделить память» |
|
Альтернативный порядок действия |
1. Не выделять память. 2. Свободная память отсутствует |
|
Приоритет |
Высокий |
Прецедент<< Освободить память>>
Номер |
ID-2 |
|
Название |
Освободить память |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования пользователь освобождает выделенную память под процесс |
|
Предварительные условия |
1. Память выделена 2. Процесс выбран |
|
Выходные условия |
Блок памяти освобожден |
|
Порядок действия |
1. Пользователь выбирает из списка процесс 2. Пользователь нажимает на кнопку «Освободить память» |
|
Альтернативный порядок действия |
1. Выделить память 2. Не освобождать память |
|
Приоритет |
Высокий |
Прецедент << Ввод параметров процесса >>
Номер |
ID-3 |
|
Название |
Ввод параметров процесса |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования пользователь участвует во вводе данных |
|
Предварительные условия |
Программа запущена |
|
Выходные условия |
Новый процесс создан |
|
Порядок действия |
1. Пользователь вводит имя процесса в текст бокс 2. Пользователь вводит размер процесса в соответствующее поле ввода |
|
Альтернативный порядок действия |
1. Загрузить список процессов с файла 2. Не вводить данные о процессе |
|
Приоритет |
Высокий |
Прецедент <<Ввод параметров памяти >>
Номер |
ID-4 |
|
Название |
Ввод параметров памяти |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования пользователь может настроить конфигурации системы |
|
Предварительные условия |
Программа запущена |
|
Выходные условия |
Параметры введены |
|
Порядок действия |
1. Пользователь задает размер памяти 2. Пользователь задает размер минимального блока памяти 3. Пользователь выбирает единицы измерения 4. Пользователь подтверждает ввод |
|
Альтернативный порядок действия |
1.Использовать настройки по умолчанию |
|
Приоритет |
Низкий |
Прецедент << Загрузить из файла >>
Номер |
ID-5 |
|
Название |
Загрузить из файла |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования пользователь загружает список процессов из файла |
|
Предварительные условия |
Программа запущена |
|
Выходные условия |
Список даннях о процесах загружен |
|
Порядок действия |
1. Пользователь нажимает кнопку "Загрузить с файла" |
|
Альтернативный порядок действия |
1. Добавление процессов вручную |
|
Приоритет |
Высокий |
Прецедент << Выбор файла >>
Номер |
ID-6 |
|
Название |
Выбор файла |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования пользователь выбирает файл с данными |
|
Предварительные условия |
Пользователь нажал кнопку "Загрузить с файла" |
|
Выходные условия |
Путь к файлу задан. |
|
Порядок действия |
1. Пользователь выбирает файл в диалоговом окне 2. Пользователь нажимает кнопку «Ок» |
|
Альтернативный порядок действия |
Нет. |
|
Приоритет |
Высокий |
Прецедент << Сохранить в файл >>
Номер |
ID-7 |
|
Название |
Сохранить список процессов |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования пользователь сохраняет список процессов в файл |
|
Предварительные условия |
Список содержит хотя бы один процесс |
|
Выходные условия |
Файл с данными создан. |
|
Порядок действия |
1. Пользователь нажимает кнопку "Сохранить в файл" 2. Указать имя нового файла |
|
Альтернативный порядок действия |
1. Недостаточно места на диске 2. Ошибка при записи данных |
|
Приоритет |
Высокий |
Прецедент << Считывание с файла >>
Номер |
ID-8 |
|
Название |
Сохранить список процессов |
|
Участники |
Файловая система |
|
Описание |
При использовании данного варианта использования файловая система считывает данные из файла |
|
Предварительные условия |
Выполнение прецедента «Загрузить с файла» |
|
Выходные условия |
Список процессов считан |
|
Порядок действия |
Считывание данных с файла |
|
Альтернативный порядок действия |
1.Неудалось считать данные |
|
Приоритет |
Высокий |
Прецедент << Проверка корректности >>
Номер |
ID-9 |
|
Название |
Проверка корректности |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования происходит проверка данных |
|
Предварительные условия |
Выполнен один из прецедентов «Ввод параметров процесса», «Ввод параметров памяти», «Освободить память», «Выделить память», «Выбрать файл», «Ввести имя файла» |
|
Выходные условия |
Проверка на корректность пройдена |
|
Порядок действия |
1. Проверка корректности |
|
Альтернативный порядок действия |
Нет. |
|
Приоритет |
Высокий |
Прецедент << Выполнение алгоритма >>
Номер |
ID-10 |
|
Название |
Выполнение алгоритма |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования выполняется алгоритм выделения/освобождения памяти |
|
Предварительные условия |
Выполнен прецедент <<Проверка данных>> |
|
Выходные условия |
Результаты работы алгоритма |
|
Порядок действия |
Нет |
|
Альтернативный порядок действия |
Нет |
|
Приоритет |
Высокий |
Прецедент << Визуализация >>
Номер |
ID-11 |
|
Название |
Визуализация |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования происходит визуализация действий пользователя и программы |
|
Предварительные условия |
Выполнен один из прецедентов «Выполнение алгоритма», «Конфигурация системы», «Загрузка списка процессов», «Проверка данных» |
|
Выходные условия |
Результаты действий отображены |
|
Порядок действия |
Нет |
|
Альтернативный порядок действия |
Нет |
|
Приоритет |
Высокий |
Прецедент << Запись в файл >>
Номер |
ID -12 |
|
Название |
Очистить поля с данными |
|
Участники |
Файловая система |
|
Описание |
При использовании данного варианта использования создается файл с данными |
|
Предварительные условия |
Выполнение прецедента «Сохранить в файл» |
|
Выходные условия |
Новый файл с даннями создан |
|
Порядок действия |
1.Создание файла 2.Запись данных |
|
Альтернативный порядок действия |
1.Недостаточно места на диске 2.Ошибка при записи |
|
Приоритет |
Высокий |
Прецедент<< Выбрать процесс >>
Номер |
ID-13 |
|
Название |
Выбрать процесс |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования пользователь выбирает процесс |
|
Предварительные условия |
Процесс загружен |
|
Выходные условия |
Процесс выбран |
|
Порядок действия |
1. Пользователь выбирает процесс из списка |
|
Альтернативный порядок действия |
1. Нет |
|
Приоритет |
Высокий |
Прецедент<< Ввести имя файла >>
Номер |
ID-14 |
|
Название |
Ввести имя файла |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования пользователь вводит имя файла |
|
Предварительные условия |
Выполнен прецедент «Сохранить в файл» |
|
Выходные условия |
Имя файла введено |
|
Порядок действия |
1. Пользователь вводит имя файла |
|
Альтернативный порядок действия |
1. Нет |
|
Приоритет |
Высокий |
Прецедент<< Настройка памяти >>
Номер |
ID-15 |
|
Название |
Настройка системы |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования пользователь настраивает память |
|
Предварительные условия |
Выполнен прецедент «Ввод параметров памяти» |
|
Выходные условия |
Память настроена |
|
Порядок действия |
1. Пользователь вводит параметры памяти |
|
Альтернативный порядок действия |
1. Нет |
|
Приоритет |
Высокий |
Прецедент<< Выход >>
Номер |
ID-16 |
|
Название |
Выход |
|
Участники |
Пользователь |
|
Описание |
При использовании данного варианта использования пользователь завершает работу с программой |
|
Предварительные условия |
Программа запущена |
|
Выходные условия |
Программа закрыта |
|
Порядок действия |
1.Пользователь завершает работу с программой |
|
Альтернативный порядок действия |
1. Продолжить работу |
|
Приоритет |
Высокий |
2.2 Диаграмм последовательности
Проведя анализ поставленной задачи и диаграммы прецедентов, были выявлены следующие объекты:
- User - пользователь;
- FileSystem - файловая система;
- GUI - графический интерфейс;
- IMemoryManager - менеджер памяти;
- IVisualizator - визуализатор;
- Memory - память;
- IStorage - хранилище.
Рисунок 2.2 - Диаграмма последовательности
Рисунок 2.3 - Диаграмма последовательности
Пользователь выполняет ввод данных о процессе, данные проверяются и отображаются.
Пользователь выполняет ввод данных о памяти, данные проверяются и отображаются, происходит настройка памяти и IVisualzator визуализирует ее.
Пользователь выполняет сохранить в файл, создается объект _storage:IStorage, _storage управляет процессом сохранения данных, файловая система записывает данные в файл.
Пользователь выполняет загрузку из файл, _storage управляет процессом загрузки данных, файловая система считывает данные из файла, GUI отображение считанные данные.
Пользователь выполняет выделение памяти, происходит проверка данных, IMemoryManager ищет свободный блок, разделяет его и загружает в один из блоков процесс, IVisualzator визуализирует состояние памяти.
Пользователь выполняет освобождение памяти, IMemoryManager освобождает блок, соединяет два свободных соседних блока, IVisualzator визуализирует состояние памяти.
Пользователь выполняет выход.
2.3 Описание графического интерфейса
Исходя из анализа поставленной задачи, выяснилось, что графический интерфейс разрабатываемого программного продукта должен содержать: область для ввода параметров памяти, область для ввода параметров процесса, область для отображения списка процессов, панель для визуализации состояния памяти, кнопки «Выделить память», «Освободить память», «Загрузить с файла» «Сохранить в файл» (рисунок 1.2).
Уточненный графический интерфейс пользователя разрабатываемого программного продукта изображен на рисунке 2.4.
Рисунок 2.4 - Уточненный интерфейс разрабатываемой программы
В области для ввода параметров памяти расположены три поля для ввода размера памяти, размера минимального блока и единиц измерения.
В области для ввода параметров процесса расположены два поля для ввода имени процесса и его размера.
В области для визуализации результатов работы алгоритма должно отображаться текущей состояние памяти в виде блоков.
2.4 Разработка архитектуры приложения
Согласно поставленной задаче, была разработана трехуровневая архитектура приложения. Она состоит из следующих уровней: GUI, Model, Storage.
Исходя из анализа поставленной задачи, был выбран именно этот тип системной архитектуры. Это можно объяснить тем, что разрабатываемая программа должна реализовывать определенный алгоритм - Model, взаимодействовать непосредственно с пользователем - GUI, хранить данных - Storage.
Рисунок 2.5 - Системная архитектура приложения
Классы:
Пакет GUI:
MainWindow - Главное окно.
IVisualizator - Интерфейс описывающий поведение визуализатора.
VisualizationMemory - Визуализация состояния памяти, реализует IVisualizator
Пакет Model:
Memory - память
BlockMemory - блок памяти
Process - процесс
GenerateIdProcess - генератор Id процесса
Units - перечесления единиц измерения памяти
IMemoryManager - интерфейс описывает поведение менеджера памяти
Bma - реализация алгоритма «Buddy memory allocation», реализует IMemoryManager
Пакет Storage:
IStorage - интерфейс описывает поведение хранилища
StorageFileXml - класс, работающий с xml-файлами
Диаграмма классов, с помощью которой можно визуализировать все описанные выше классы, методы и поля, изображена на рисунке 2.6.
Рисунок 2.6 - Диаграмма классов разрабатываемой программы
2.5 Разработка алгоритмов работы программы
Пакет model. Класс Bma. Метод Allocate.
Данный метод принимает аргумент процесс. При его вызове процесс размещается в свободном блоке памяти.
Блок схема метода Allocate изображена на рисунке 2.7.
Рисунок 2.7 - Блок-схема метода Allocate. Класс Bma.
Проверяем размер процесса. Дальше в цикле ищем свободный блок минимального размера. Если нашли такой блок, удаляем его из списка свободных блоков. Разбиваем блок на два одинаковых блока, один добавляем в свободные, размер другой сравниваем с размером процесса и размером минимального блока памяти. Если процесс не помещается в половину блока или его половина меньше минимального, то загружаем процесс в этот блок, в противном случаи, снова разбиваем блок, пока не получим блок нужного размера.
Пакет model. Класс Bma. Метод Deallocate.
Данный метод принимает аргумент процесс. При его вызове процесс размещается в свободном блоке памяти.
Блок схема метода Allocate изображена на рисунке 2.6
Ищем блок, который хранит процесс с указанным id.Если нашли, освобождаем блок. Запускаем цикл для поиска близнецов по их адресу. Если блок имеет свободного близнеца, соединяем их и снова повторяем процедуру, в противном случаи, добавляем блок в список свободных.
Рисунок 2.8 - Блок-схема метода Deallocate. Класс Bma.
2.6 Выбор структуры данных
Систему двойников можно реализовать на нескольких структурах данных, основными являются: бинарное дерево и двухсвязный список.
Основным преимуществом двухсвязного списка является простая реализации, особенно, если разработка ведется с использованием языка программирования C#, так как в нем есть стандартный класс, реализующий двунаправленный связанный список.
В отличие от бинарного дерева список использует меньше памяти, так как при разбиении блока, он будет удаляться, в отличие от бинарного дерева, где старый блок сохраняется. Но за это преимущество двухсвязный список платит таким недостатком как скорость выполнение, так как будет потрачено время на удаление при разделении и создания блоков при соединении двойников.
Один из основных недостатков двухсвязного списка считается скорость поиска элемента в нем, его сложность будет равна O(n), тогда как в бинарном дереве сложность поиска элемента равна O(log n), но на самом деле этот недостаток легко решается при помощи бинарного поиска. Так как блоки в списке расположены последовательно, то их адреса отсортированы по возрастанию, что дает возможность применить бинарный поиск и получить сложность поиска элемента O(log n), как и у бинарного дерева.
Взвесив все за и против, я решил использовать двухсвязный список из-за простоты его реализации.
3. Верификация и тестирование программы
3.1 Верификация программы
Верификация - это процесс определения, выполняют ли программные средства и их компоненты требования, наложенные на них в последовательных этапах жизненного цикла разрабатываемой программной системы.
Основная цель верификации состоит в подтверждении того, что программное обеспечение соответствует требованиям.
Верификацию будем выполнять при помощи опросного листа, путём анализа из проектной документации (ТЗ, ПЗ), а также кодов программы.
Проверяться будет задача ввод данных при помощи web-интерфейса для десктопного приложения, функции которой: настройки параметров памяти, ввода параметров процесса, проверки данных на корректность; задача распределения памяти при помощи алгоритма системы двойников, функции которой: выделение памяти, освобождение памяти; задача визуализации, функции которой: отображать состояние памяти и списка процессов находящихся в памяти; задача сохранения списка процессов в файл, функции которой: запись в файл; задача чтения списка процессов из файла, функции которой: чтение с файла и проверка указанного файла.
Результаты верификации программы приведены в таблице.
Верификация и ее результаты
Требования в ТЗ |
Где реализован |
Вывод |
|
1a) Настройки параметров памяти |
Класс MainWindow Метод btnOkConfigMemory_Click |
Пройден |
|
1b) Ввод параметров процесса |
Визуально в графическом интерфейсе пользователя |
Пройден |
|
1c) Проверка данных на корректность |
Класс MainWindow Методы:IsCorrectNameProcess, IsCorrectSizeBlock, nUpDownSizeProccess_PreviewTextInput, tbNameNewProccess_PreviewTextInput При помощи настроек элементов графического интерфейса. |
Пройден |
|
2a) Выделение памяти |
Класс Bma Метод Allocate |
Пройден |
|
2b) Освобождение памяти |
Класс Bma Метод Deallocate |
Пройден |
|
3a) Визуализация состояния памяти |
Класс VisualizationMemory Метод Visualization |
Пройден |
|
3b) Визуализация список процессов находящихся в памяти |
Привязка данных к графическом интерфейсу |
Пройден |
|
4a) Запись в файл |
Класс StorageFileXml Метод Write |
Пройден |
|
5a) Чтение с файл |
Класс StorageFileXml Метод Read |
Пройден |
|
5b) Проверка указанного файла |
Класс MainWindow Метод OpenFile Класс StorageFileXml Метод Read |
Пройден |
3.2 Тестируемые функции
При разработке данного проекта были реализованы такие функции:
1а) функция для настройки параметров памяти;
Данная функция выполняется при настройке пользователем параметров памяти.
1b) функция для ввода параметров процесса;
Данная функция выполняется при вводе пользователем параметров процесса.
1c) функция для проверки данных на корректность;
Данная функция выполняется при проверке данных на корректность.
2a) функция выделения памяти;
Данная функция выполняется тогда, когда пользователь выделяет память.
2b) функция освобождения памяти;
Данная функция выполняется при освобождение блока от процесса.
3а) функция визуализации состояния памяти;
Данная функция выполняется после каждого изменения состояния памяти. Она выполняет визуализацию всех изменений происходящих с памятью.
3b) функция визуализации списка процессов находящихся в памяти;
Данная функция выполняется после выделения памяти под новый процесс. Она выполняет визуализацию всех процессов находящихся в памяти.
4а) функция записи в файл;
Данная функция выполняется при записи списка процессов в файл.
5а) функция чтения с файл;
Данная функция выполняется при чтении списка процессов из файл.
5b) функция проверки указанного файла;
Данная функция выполняется при проверки файла на корректность перед чтение из файла.
3.3 Разработка тестовых случаев
С целью проверки корректности работы программного обеспечения, разработанного в данном проекте, было проведено его тестирование. Тесты и результаты их выполнения приведены в таблице.
Тестирование и его результаты
Тестируемая функция |
№ |
Цель теста |
Полученный результат |
Результат теста |
|
1а) |
1 |
Проверка возможности настроить параметры памяти |
Рисунок 3.1 |
Пройден |
|
1b) |
2 |
Проверка возможности ввести параметры процесса |
Рисунок 3.2 |
Пройден |
|
1c) |
3 |
Проверка на возможность ввести пустое имя процесса |
Рисунок 3.3 |
Пройден |
|
4 |
Проверка на возможность ввести пустой размер процесса |
Рисунок 3.4 |
Пройден |
||
5 |
Проверка на возможность ввести отрицательный размер процесса |
Рисунок 3.4 |
Пройден |
||
6 |
Проверка на возможность ввести размер процесса больше размера памяти |
Рисунок 3.5 |
Пройден |
||
7 |
Проверка на возможность использовать в имени символы отличные от букв и цифр |
Рисунок 3.6 |
Пройден |
||
8 |
Проверка на возможность ввести имя уже существующего процесса |
Рисунок 3.7 |
Пройден |
||
2a) |
9 |
Проверка корректного выделения памяти |
Рисунок 3.8 |
Пройден |
|
10 |
Проверка попытки выделения памяти при отсутствии свободных блоков нужного размера |
Рисунок 3.9 |
Пройден |
||
2b) |
11 |
Проверка корректного освобождения памяти |
Рисунок 3.10 |
Пройден |
|
12 |
Проверка на возможность освободить память не выбрав процесс |
Рисунок 3.11 |
Пройден |
||
3a) |
13 |
Проверка корректности визуализации состояния памяти. |
Рисунок 3.8 |
Пройден |
|
3b) |
14 |
Проверка корректности визуализации списка процессов |
Рисунок 3.7 |
Пройден |
|
4a) |
15 |
Проверка корректности записи списка процессов в файл |
Рисунок 3.12 |
Пройден |
|
5a) |
16 |
Проверка корректности чтения списка процессов из файл |
Рисунок 3.13 |
Пройден |
|
17 |
Проверка возможности считать данные с некорректного файла. |
Рисунок 3.14 |
Пройден |
||
5b) |
18 |
Проверка на возможности выбрать файл с данными |
Рисунок 3.15 |
Пройден |
|
19 |
Проверка возможности выбрать не существующий файл. |
Рисунок 3.16 |
Пройден |
||
20 |
Проверка возможности выбрать некорректный файл. |
Рисунок 3.14 |
Не пройдена |
Рисунок 3.1 - Результат теста 1.
Рисунок 3.2 - Результат теста 2
Рисунок 3.3 - Результат теста 3
Рисунок 3.4 - Результат теста 4,5
Рисунок 3.5 - Результат теста 6
Рисунок 3.6 - Результат теста 7
Рисунок 3.7 - Результат теста 8,14
Рисунок 3.8 - Результат теста 9,13
Рисунок 3.9 - Результат теста 10
Рисунок 3.10 - Результат теста 11
Рисунок 3.11 - Результат теста 12
Рисунок 3.12 - Результат теста 15
Рисунок 3.13 - Результат теста 16
Рисунок 3.14 - Результат теста 17,20
Рисунок 3.15 - Результат теста 18
Рисунок 3.16 - Результат теста 19
4. Руководство оператора
4.1 Назначение программы
Программа предназначена для наглядного обучения студентов принципам работы распределения памяти между процессами. Программа относится к классу прикладных программ и не может использоваться в качестве реального компонента операционной системы. Ее задача - моделирования алгоритма «Системы двойников».
Программа поставляется в виде исполнимых кодов (.exe-файла), устанавливается на данный компьютер путем копирования в соответствующую директорию и не нуждается в обслуживании.
4.2 Условия выполнения программы
В состав технических средств должен входить IBM-совместимый персональный компьютер (ПЭВМ), включающий в себя:
В состав технических средств должен входить персональный компьютер (ПЭВМ), включающий в себя:
а)процессор с тактовой частотой, ГГц - 1.5, не менее;
б)материнскую плату с FSB, МГц - 133, не менее;
в)оперативную память объемом - 256 МБ, не менее;
г)свободного дискового пространства для хранения программы - 30 МБ, не менее;
д)дисплей и видеоадаптер такого типа, которые смогут отображать графическую информацию, являющуюся результатом выполнения программы;
е)клавиатуру;
з)мышь.
Для запуска программы на персональном компьютере необходимо наличие операционной системы Windows 7, .Net Framework 4.51.
4.3 Выполнение программы
Для инсталляции программы на персональный компьютер необходимо скопировать *.exe файл на жесткий диск. После чего программа готова к эксплуатации и может быть запущена путем двойного клика левой кнопки мыши на исполняемом файле. На рисунке 4.1 продемонстрирована запущенная программа.
Рисунок 4.1 - Внешний вид программы после запуска
После запуска программы пользователь может выполнять работу с ней с установленными по умолчанию значениями. Для того, чтобы можно было выделить память, необходимо:
1) ввести параметры процесса;
2) нажать кнопку «Allocate».
Выполняя такие действия, можно достичь результата, показанного на рисунке 4.2.
Рисунок 4.2 - Состояние программы после выделения памяти
Для освобождения памяти, необходимо:
1) выделить процесс из списка, как показано на рисунке 4.3;
2) нажать кнопку «Deallocate».
Выполнив эти действия, будет виден результат освобождения памяти (Рисунок 4.4).
Рисунок 4.3 - Выделение процесса в списке
Рисунок 4.4 - Результат освобождения памяти
Можно настраивать параметры памяти путем выполнения следующих действий:
1) выбрать нужные значения параметров при помощи выпадающих списков;
2) нажать кнопку «Ок»;
Выполнив эти действия, можно достичь результата, показанного на рисунке 4.5.
Рисунок 4.5 - Результат настройки системы
Сохранить список процессов можно следующим образом:
1) нажать кнопку «Save list»;
2) ввести имя файла.
Результат этого действия продемонстрирован на рисунке 4.6.
Рисунок 4.6 - Сохранение списка процессов в файл
Загрузить список процессов можно следующим образом:
1) нажать кнопку «Load list»;
2) выберите файл.
Результат этого действия продемонстрирован на рисунке 4.7.
Рисунок 4.7 - Загрузка списка процессов из файла
Выводы
Работа посвящена управлению памятью, являющейся фундаментальным вопросом в операционных системах. Память является очень важным ресурсом, поэтому требуется эффективное управление ею. Данную проблему можно решить при помощи алгоритма «Система двойников».
В проделанной работе было создано программное обеспечение, которое успешно прошло верификацию, то есть программа выполняет все задачи и функции указанные в техническом задании. Программа выполняет моделирование работы алгоритма и визуализирует результаты его работы.
Данное программное обеспечение написано для операционной системы Windows 7 и работает на основе платформы .Net Framework 4.51 при помощи Visual Studio 2013 на объектно-ориентированном языке C#.
Так же были разработаны диаграмма прецедентов диаграмма последовательности и диаграмма классов. Проектирование системы происходило постепенно: проектировка прототипа интерфейса, создание диаграммы прецедентов и на ее основе диаграммы последовательности. Одним из важнейших этапов был создание диаграммы классов. После разработка алгоритмов работы основных частей программы.
Проведенная верификация показала, что все требования, приведенные, в ТЗ выполнены. Их выполнение подтверждено документально. Таким образом, поставленная заказчиком задача выполнена в полном объеме. Функции, которые не прописаны в ТЗ программа не реализует.
Так же было проведенно тестирование программного обеспечения, разработанного в данном проекте, которое подтвердило работоспособность программы.
В качестве дальнейших улучшений программы могут выступать изменения ее интерфейса для более гибкой настройки системы, возможность сохранения состояния памяти для дальнейшей работы с ними между запусками программы, добавления других алгоритмов распределения памяти, улучшения функции визуализации.
Перечень ссылок
1. Jeffrey Richter. CLR via C# - 2012г;
2. C# 5.0 in a Nutshell, 5th Edition - O`REALLY, 2012г;
3. [електронный ресурс] http://studopedia.org/6-56822.html
4. [електронный ресурс] http://en.academic.ru/dic.nsf/enwiki/211388
5. [електронный ресурс] http://en.wikipedia.org/wiki/Buddy_memory_allocation
Приложения
Приложение А
Техническое задание
Наименование программы
Наименование программы - «Менеджер распределения памяти» (далее по тексту Программа)
Краткая характеристика области применения
Программа предназначена для наглядного обучения студентов принципам работы распределения памяти между процессами. Программа относится к классу прикладных программ и не может использоваться в качестве реального компонента операционной системы. Ее задача - моделирования алгоритма «Системы двойников».
Основание для разработки
Основание для проведения разработки
Основание для разработки Программы - задание на курсовой проект кафедры "Компьютерные системы и сети" (503) Национального аэрокосмического университета им. Н. Е. Жуковского "ХАИ", выдано 15.01.2015.
Наименование и условное обозначение темы разработки
Наименование темы разработки - «Разработка ПО для распределения памяти на основе алгоритма: система двойников» (сокр. «Двойники»).
Назначение разработки
Функциональное назначение программы
Данная программа предоставляет возможность распределять память между процессами. По введенным данным о процессе производится выделение для него памяти или ее освобождение, если данный процесс выполнен.
Эксплуатационное назначение. Программа предназначена для использования студентами, отдельными пользователями для моделирования работы алгоритма распределения памяти.
Программа запускается однократно оператором ПК с правами обычного пользователя. Программа должна быть разработана таким образом, чтобы после перекомпиляции иметь способность выполняться на ПК любого типа. Предназначена для эксплуатации на ПК, установленном в офисе или в домашних условиях.
Программа поставляется в виде исполнимых кодов (.exe-файлов), устанавливается на данный компьютер путем копирования в соответствующую директорию и не нуждается в обслуживании.
Требования к программе или программному изделию
Требования к функциональным характеристикам
Требования к составу выполняемых функций
Программа должна решать следующие задачи:
1) ввод данных при помощи web-интерфейса для десктопного приложения (далее по тексту Интерфейс);
2) распределение памяти при помощи алгоритма система двойников;
3) визуализация;
4) сохранение списка процессов в файл;
5) чтение списка процессов из файла.
Для того чтобы решить задачу 1), должна быть реализована:
a) функция для настройки параметров памяти;
b) функция для ввода параметров процесса;
c) функция для проверки данных на корректность;
Для того чтобы решить задачу 2), должна быть реализована:
a) функция выделения памяти;
b) функция освобождения памяти.
Для того чтобы решить задачу 3), должна быть реализована:
a) функция визуализации состояния памяти;
b) функция визуализации списка процессов находящихся в памяти;
Для того чтобы решить задачу 4), должна быть реализована:
a) функция записи в файл;
b) Функция проверки имени файла.
Для того чтобы решить задачу 5), должна быть реализована:
a) функция чтения с файла.
b) функция проверки указанного файла.
Требования к организации входных данных
Входные данные программы должны быть организованы в виде .xml файлов. Место расположения файлов: указывается пользователем. Данные поступают в программу путем чтения из файлов или вводятся пользователем при помощи Интерфейса.
Требования к организации выходных данных
В зависимости от входных данных пользователю будет показан результат работы алгоритма. Список текущих процессов можно сохранить.
Требования к временным характеристикам
Требования к временным характеристикам не предъявляются.
Требования к надежности
Данный программный продукт является прикладной программой, не работающей в системе реального времени или в области критических технологий, на выполнение запускается однократно и функционирует в течение короткого промежутка времени. Поэтому специальных требований к надежности программы не предъявляется.
Требования к обеспечению надежного (устойчивого) функционирования программы
Надежное (устойчивое) функционирование программы должно быть обеспечено выполнением Заказчиком совокупности организа...
Подобные документы
Архитектура компьютеров и возможности операционной системы по управлению памятью. Суть концепции виртуальной памяти. Аппаратно-независимые и аппаратно-зависимые средства управления виртуальной памятью. Сегментно-страничная организации виртуальной памяти.
презентация [355,2 K], добавлен 27.12.2010- Управление памятью. Страничная организация памяти. Сегментная организация памяти. Виртуальная память
Как осуществляется трансляция адресов при страничной организации. Что такое компактировка и как с ее помощью избавиться от внешней фрагментации. Что такое регистр таблицы страниц, сегментация. Методы распределения памяти в виде отдельных сегментов.
контрольная работа [236,2 K], добавлен 23.12.2016 Распределение виртуальной памяти. Страничная и сегментная организации виртуальной памяти. Сегментно-страничная организация виртуальной памяти. Преобразование виртуального адреса в физический. Упрощение адресации памяти клиентским программным обеспечением.
курсовая работа [440,7 K], добавлен 04.03.2014Понятие виртуальной памяти, ее реализация. Особенности страничной организации по требованию. Этапы обработки ситуации отсутствия страницы в памяти. Стратегии (алгоритмы) замещения страниц. Особенности некоторых операционных систем: Windows NT и Solaris.
презентация [2,2 M], добавлен 24.01.2014Объем двухпортовой памяти, расположенной на кристалле, для хранения программ и данных в процессорах ADSP-2106x. Метод двойного доступа к памяти. Кэш-команды и конфликты при обращении к данным по шине памяти. Пространство памяти многопроцессорной системы.
реферат [28,1 K], добавлен 13.11.2009Схема распределения памяти, соответствующая пользовательской трактовке распределения памяти. Перемещение с помощью таблицы сегментов. Аппаратная поддержка сегментного распределения памяти. Сегментно-страничная организация памяти с двухуровневой схемой.
лекция [1,5 M], добавлен 24.01.2014Стратегии размещения информации в памяти. Алгоритмы распределения адресного пространства оперативной памяти. Описание характеристик модели и ее поведения, классов и элементов. Выгрузка и загрузка блоков из вторичной памяти. Страничная организация памяти.
курсовая работа [708,6 K], добавлен 31.05.2013Динамическое распределение памяти. Анализ виртуальной памяти, алгоритм ее обращения, общие принципы защиты. Страничная организация. Особенности переключения в мультизадачный режим. Режим системного управления. Расширение размера адресного пространства.
презентация [1,3 M], добавлен 14.12.2013Память для вычислительных систем ее создание и характеристика особенностей. Создание устройств памяти и основные эксплуатационные характеристики. Функциональные схемы и способ организации матрицы запоминающих элементов. Виды магнитной и флеш памяти.
презентация [184,9 K], добавлен 12.01.2009Характеристика флэш-памяти, особого вида энергонезависимой перезаписываемой полупроводниковой памяти. Исследование особенностей организации флэш-памяти. Общий принцип работы ячейки. Обзор основных типов карт памяти. Защита информации на флеш-накопителях.
презентация [9,3 M], добавлен 12.12.2013История развития ОС UNIX, ее достоинства. Управление компьютером под управлением UNIX. Интерпретация командной строки и структура файловой системы. Команды управления процессами. Средства системного администрирования и учетные записи пользователей.
презентация [78,1 K], добавлен 12.05.2014Разработка структурной схемы и алгоритма функционирования микропроцессорного модуля программного обеспечения автоматизированной информатизационно-измерительной системы. Характеристика принципиальной схемы модуля, распределения памяти и задание портов.
курсовая работа [1,2 M], добавлен 28.08.2012Создание программы, которая создает набор данных в динамической памяти компьютера и позволяет корректировать его. Описание программного комплекса. Обзор особенностей реализации программы с использованием модулей. Добавление данных в конец текущего набора.
курсовая работа [455,2 K], добавлен 28.08.2017Описание файловой системы Unix. Работа основных команд ls, cmp, comm, их ключей. Разработка программного продукта, работающего в среде Windows и представляющего собой эмулятора командного процессора операционной системы Unix. Выбор средств реализации.
курсовая работа [183,0 K], добавлен 29.04.2015Разработка драйвера под Linux, отслеживающего выделение и освобождение процессами виртуальной памяти и выделение физических страниц при страничных отказах. Компиляция драйвера и работа с ним. Экспериментальная проверка работоспособности драйвера.
курсовая работа [43,5 K], добавлен 18.06.2009Внутренний кэш. Смешанная и разделенная кэш-память. Статическая и динамическая память. TLB как разновидность кэш-памяти. Организация кэш-памяти. Отображение секторов ОП в кэш-памяти. Иерархическая модель кэш-памяти. Ассоциативность кэш-памяти.
курсовая работа [229,1 K], добавлен 04.11.2006История появления операционной системы Unix. Перекомпиляция Unix в коды любой аппаратной платформы, ее многозадачность и многотерминальность. Основные отличия Unix от других операционных систем. Использование Unix в качестве сервера и рабочей станции.
реферат [28,1 K], добавлен 05.04.2010Сравнительный анализ статической и динамической памяти. Быстродействие и потребление энергии статической памятью. Объем памяти микросхем. Временные диаграммы чтения и записи памяти. Микросхемы синхронной и асинхронной памяти. Режимы модулей памяти.
презентация [114,2 K], добавлен 27.08.2013Распределение оперативной памяти фиксированными, динамическими и перемещаемыми разделами. Распределение с использованием внешней памяти. Принципы рaботы матричного принтера. Проектирование символов и разработка программы, реализующей их вывод на печать.
курсовая работа [241,3 K], добавлен 01.07.2011Понятие программного обеспечения, вопросы его разработки и использования. Общая характеристика системного программного обеспечения и работа операционной системы. Специфика процесса управления разработкой программного обеспечения и его особенности.
курсовая работа [636,2 K], добавлен 23.08.2011