0. 3.4. Отчет по лабораторной работе

Отчет по лабораторной работе должен содержать:

– тексты полученных заданий с номером варианта;

– тексты программ с комментариями (в комментариях отобразить изменения содержимого регистров и флагов по ходу выполнения программы).

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

4. Лабораторная работа №6.

ИСПОЛЬЗОВАНИЕ СВЯЗНЫХ СПИСКОВ ДЛЯ УПРАВЛЕНИЯ ПАМЯТЬЮ И ПРОЦЕССАМИ

0. 4.1. Общие методические указания по выполнению лабораторной работы

Цели работы:

– освежить и углубить навыки работы с динамическими списками, широко используемыми в ОС для реализации механизмов управления процессами и ресурсами.

– закрепить полученные в рамках лекционного курса знания об используемых ОС алгоритмах, реализуемых на базе динамических связных списков.

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

– разработать оконное приложение, реализующее заданный алгоритм и демонстрирующее работоспособность модуля.

– получить опыт распределения работы по разработке программы между членами рабочей группы (предполагается выполнение одного задания группами по 2-3 человека).

Среда разработки:

Visual C++.

Перед выполнением работы необходимо повторить следующие темы лекционных курсов «Операционные системы» и «Программирование на языках высокого уровня»:

– дисциплины выбора свободного участка памяти при распределении памяти динамическими разделами («первый подходящий», «самый подходящий», «самый неподходящий»).

– диспетчеризацию задач с использованием статических приоритетов, в т.ч. относительных и абсолютных.

– дисциплины диспетчеризации FCFS, SJN, SRT, RR, RR + статические относительные приоритеты.

– работу с указателями и динамическим выделением памяти.

– понятие линейного списка, в том числе последовательного и связного списков.

– реализация списков с использованием статических (последовательные списки) и динамических (связные списки) структур данных.

– понятия стека, очереди, односвязных, двусвязных и циклических списков. Их реализация на языке программирования C.

0. 4.2. Теоретические сведения

Связные списки

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

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

Реализация структуры данных в виде модуля

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

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

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