Курсовая работа Моделирование файловой системы Типовая курсовая работа представляет собой разработку
Работа добавлена на сайт samzan.net:
Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Операционные системы. Курсовая работа
Моделирование файловой системы
Типовая курсовая работа представляет собой разработку системы управления файлами с заданным набором параметров.
-
Физический уровень. Распределение носителя:
- разделами (блоками переменной размерности)
- кластерами (блоками фиксированной размерности)
Структура данных свободных блоков:
- Битовая карта
- Список свободных кластеров (разделов)
- Список с массивом указателей на кластеры (разделы)
- Упорядоченный по длине список разделов
- Дерево с массивами указателей на кластеры (разделы)
- FAT
Базовый уровень. Наличие индексного файла
- Индексный файл имеется (содержит дескрипторы файлов, каталогов, файла свободного пространства, индексного файла (самого себя). Начальная запись носителя содержит смещение начала индексного файла.
- Индексный файл отсутствует. Начальная запись носителя содержит параметры файла (описания) свободного пространства и корневого каталога.
Размещение файла:
- FAT
- Список кластеров (разделов)
- Список с массивом указателей на кластеры (разделы)
- Дерево с массивами указателей на кластеры и их размеры.
- Дерево UNIX
Логический уровень. Система каталогов (папок).
- Неупорядоченный список имен файлов
- Упорядоченный по алфавиту список имен файлов.
Символьный уровень. Спецификация пути файла. Функции open,close,seek,read,write записей произвольный длины с буферизацией. Функции remove, rename, create_dir, remove_dir для файлов и каталогов.
Прикладной уровень. Утилита управления носителем:
- Форматирование (создание файловой структуры). Просмотр каталогов и файлов.
- Экспорт/импорт файлов, папок, носителя.
- Дефрагментация и сжатие файлов.
Моделирование структур данных операционных систем
Базовый класс объектов ОС. Производные классы объектов ОС –процессов, потоков, семафоров, файлов. Классы драйверов, физических и логических устройств, запросов ввода-вывода, отложенных прерываний (процедур).
- Каждый процесс имеет описатель, содержащий двухуровневый динамический массив указателей на связанные с ним объекты ОС (файлы, семафоры и т.п.). Объект идентифицируется 16-разрядным handle. Старший байт handle представляет собой смещение в массиве указателей верхнего уровня, младший байт –нижнего. Свободные handle обозначены NULL-указателями. Функция связывания заданного объекта с процессом с выделением ему handle и функция освобождения объекта по заданному handle. Каждый объект имеет счетчик связей. Если объект ОС не имеет больше связей с процессами, то он уничтожается. main моделирует фиксированную последовательность установления и освобождения связей между объектами и процессами (и производит трассировку текущего состояния системы).
- Каждый процесс (поток) может ожидать событий от нескольких объектов одновременно. С каждым объектов может быть связано несколько ожидающих процессов. Смоделировать структуру связей «процессы-объекты» с использованием в каждом процессе динамического массива указателей на объекты и в каждом объекте –динамического массива указателей на ожидающие процессы. Реализовать действия: установить ожидание процессом заданного события, смоделировать наступление события в объекте с деблокированием связанных процессов, для которых это событие –единственное (последнее).
- Задание аналогичное предыдущему, каждый процесс содержит заголовок списка объектов, на которых он ожидает событие, каждый объект содержит список ожидающих процессов. Факт «процесс ожидает событие» реализован элементом, имеющим 4 указателя и включенным одновременно в список процесса и в список объекта.
- Описатель потока (процесса) представляет собой элемент односвязного списка, содержащего базовый и максимальный приоритеты (в диапазоне 0-255). Диспетчер поддерживает 256 приоритетных очередей (массив указателей на списки процессов). Модель поддерживает также список блокированных (ожидающих) процессов. Каждый процесс имеет две случайные характеристики: количество квантов работы и количество квантов блокировки. Диспетчер моделирует поведение процессов и собственный алгоритм. Если время блокировки процесса истекло, то диспетчер извлекает описатель процесса из очереди ожидающих и помещает его в конец очереди в соответствии с его максимальным приоритетом. Затем ищет очередь с максимальным приоритетом, выбирает из нее первый описатель и «выполняет процесс», после чего переносит его в очередь с более низким приоритетом, если его текущий приоритет выше базового. Если количество квантов работы процесса истекло, он переносится в список блокированных, и для него устанавливаются новые случайные значения квантов.
- Задание аналогичное предыдущему, но диспетчер поддерживает единственную общую очередь всех процессов - двусвязный список, из которого извлекается первый процесс с максимальным приоритетом.
- Драйвер устройства содержит таблицу функций (в том числе, инициализация ввода-вывода и обработки прерывания ввода-вывода) и заголовок очереди запросов ввода-вывода. Функция инициализации ввода-вывода устанавливает случайное значение времени работы устройства. main моделирует появление операции ввода-вывода и формирует случайный интервал времени до следующей операции. Диспетчер ввода-вывода создает запрос ввода-вывода и помещает его в очередь драйвера, если она была пуста, вызывает функцию инициализации ввода-вывода в драйвере. Обработчик прерывания в драйвере вызывает функцию завершения ввода-вывода в диспетчере. Диспетчер удаляет запрос из очереди, и, если она не пуста, вызывает функцию инициализации для следующего запроса.
- Система динамического распределения памяти (системный пул), включающая функции _malloc, _free, _realloc. Свободные области –двусвязный список, элемент списка содержит два указателя, размерность и саму выделяемую память. Выделение по принципу: если есть блок, совпадающий по размеру с выделенным –то выделяется он, если есть больший его не более чем на n процентов –выделяется минимальный из таких, иначе «отрезается» от элемента списка максимальной размерности. Функция free «склеивает» рядом стоящие свободные блоки. Функция _realloc пытается расширить существующую область, если вслед за ней есть свободный блок, иначе перераспределяет память через _malloc и _free. Функция _malloc возвращает адрес памяти «вслед за» заголовком элемента списка, функция _free перемещает указатель с возвращенной области на заголовок.
- Модель древовидной структуры именованных объектов в памяти. Базовый класс объектов содержит имя объекта и ссылки в списке. Производный класс объектов –каталогов содержит заголовок списка включенных в него объектов, а также указатель на каталог-предок. Имеются также производные классы объектов –процессы, файлы, семафоры и т.д.. Разработать редактор дерева объектов и функцию поиска объекта по спецификации <имя>/<имя>/<имя>.
- Задание аналогичное предыдущему, но объект-каталог использует динамический массив указателей на объекты, включенные в каталог.
Моделирование процессов и обработка прерываний
При решении задач, связанных с обработкой прерывания необходимо разрешить проблемы, связанные с синхронизацией доступа к общим данным. В частности, нужно использовать функции enable() и disable() для разрешения и запрещения прерывания процессора.
- Очередь отложенных прерываний реализована в виде односвязного списка. Заголовок списка представляет собой два указателя на первый и последний элементы. Элемент списка содержит указатель на «отложенную» функцию, которую следует выполнить по завершении прерывания на низком приоритете (при разрешенном прерываний). Функция генерации отложенного прерывания создает элемент списка, помещает в него указатель и ставит его в очередь. Если очередь была пуста, то входит в режим обслуживания очереди прерываний на низком приоритете (при разрешенном прерывании). Поведение системы рассмотреть на основе источника отложенных прерываний –таймера, а в сами функции отложенного прерывания внести случайную программную задержку.
- Ввод по прерыванию с буферизацией. Имеется список свободных буферов (элементов списка). По прерыванию от таймера генерируется очередное случайное число и записывается в массив (сам массив находится в элементе списка). При заполнении массива буфер помещается в очередь накопленных данных. main производит периодический опрос очереди (используя случайную задержку –функция delay) , выводит полученные данные и освобождает буфер.
- Модель процессов в DOS –функции, запускаемые событиями. Система поддерживает список: элемент списка содержит указатель на запускаемую функцию, ее фактические параметры и значение задержки перед запуском. Опрос клавиатуры и мыши приводят к планированию фиксированных функций. С помощью модели реализовать игровую интерактивную программу. Функция может также рассылать сообщение всем стоящим в очереди функциям.
- Модель процессов –классы, обрабатывающие сообщения. Базовый класс программных объектов, обрабатывающих сообщения имеет статический список, в который они включаются конструктором и исключаются деструктором, а также виртуальную функцию обслуживания сообщений и функцию –послать сообщение. Класс сообщений содержит указатель на элемент в списке сообщений и ряд параметров, в том числе –код класс –источник сообщения. Класс «программа» поддерживает очередь сообщений и имеет доступ к очереди объектов. Метод run опрашивает таймер, клавиатуру и мышь и генерирует сообщения от них. Полученные сообщения «пропускает» через все программные объекты. Объект, принимающий сообщение, сообщает об этом, после чего обработка сообщения прекращается. С помощью модели реализовать игровую интерактивную программу.
Анализ эффективности алгоритмов в использовании ресурсов памяти
- Оценить влияние размера рабочего набора физической памяти на эффективность алгоритмов сортировки в виртуальной памяти (вытеснение страниц при замещении). Сортировать массив случайных данных размерностью 1,2,4…1024 Mb, используя алгоритм простой обменной сортировки, Шейкер-сортировки, сортировки выбором и однократным слиянием. Для однократного слияния использовать разбиение линейного массива на части, проанализировать влияние на эффективность количества частей разбиения. Для каждого эксперимента измерить общее время выполнения программы с помощью функции clock.
- Оценить эффективность алгоритмов замещения страниц (оптимальный, LRU, FIFO) на имитационной модели. Моделируется программа, имеющая N виртуальных страниц и R физических. Моделируется случайная последовательность обращений к виртуальным страницам (равномерное распределение, равномерное обращение к диапазону из M страниц, со сменой диапазона через S обращений). Структура данных модели содержит для каждой виртуальной страницы номер последнего обращения к ней и признак ее нахождения в памяти (можно использовать значение -1 номера обращения). Для оптимального алгоритма вытеснения необходимо предварительно сгенерировать и запомнить всю последовательность обращений (для выбора страницы с максимальным интервалом обращения «в будущем»). Результат моделирования –процент страничных прерываний для различных значений параметров N,R,S,M.