Есть у нас такой предмет в ВУЗ`е, называется Системное Программное Обеспечение. В рамках этого предмета нам предлагается ознакомится с программными моделями, демонстрирующими работу реального железа и процессов, протекающих в нем. Модели, предлагаемые преподавателем мне показались не оптимальными, тем более их графическая составляющая была заточена под Windows, поэтому я решил писать все модели самостоятельно, насколько хватит ума. Как итог хочу представить вам эти лабораторные работы, может быть кому-то понадобятся или помогут понять принцип работы того или иного процесса. Всего 8 лабораторных работ, выкладывать буду по 1. В некоторых содержатся ошибки, но они, как правило, не принципиальны.
Темы лабораторных:
1 Моделирование структуры данных “очередь FIFO”.
2 Моделирование структуры данных “стек”.
3 Планирование потоков в однопроцессорной системе.
4 Планирование потоков в мультипроцессорной системе.
5 Оптимальное планирование процессов в операционной системе при параллельной
организации вычислений.
6 Синхронизация потоков в мультипрограммной операционной системе.
7 Преобразование виртуального адреса в физический при сегментной организации
виртуальной памяти.
8 Преобразование виртуального адреса в физический при страничной организации
виртуальной памяти.
Не претендую на звание Бога Кода или что-то подобное, просто делюсь своей реализацией.
Лабораторная № 1 Моделирование структуры данных “очередь FIFO”.
Теоретическая часть.
Очередью FIFO (First - In - First- Out - «первым пришел - первым исключается») называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой
очереди).
Основные операции с очередью:
1 - Создание очереди (вектора).
2 - Добавление элемента в начало очереди.
3 - Удаление элемента из конца очереди.
4 - Очистка очереди (разрушение).
5 - Вывод всех элементов очереди на экран.
6 - Построение гистограммы, демонстрирующей принцип работы FIFO. 0 - Выход из программы.
Машинное представление очереди FIFO и реализация операций.
При включении элемента в очередь последний записывается по адресу, определяемому указателем на конец, после чего этот указатель увеличивается на единицу. При исключении элемента из очереди выбирается элемент, адресуемый указателем на начало, после чего этот указатель уменьшается на единицу. Очевидно, что со временем указатель на конец очереди при очередном включении элемента достигнет верхней границы той области памяти, которая выделена для очереди. Однако, если операции включения чередовались с операциями исключения элементов, то в начальной части, отведенной под очередь памяти, имеется свободное место. Для того, чтобы места, занимаемые исключенными элементами, могли быть повторно использованы, очередь замыкается в кольцо: указатели (на начало и на конец), достигнув конца выделенной области памяти, переключаются на ее начало. Такая организация очереди в памяти называется кольцевой очередью.
Если в процессе работы с кольцевой очередью число операций включения превышает число операций исключения, то может возникнуть ситуация, в которой указатель конца "догонит" указатель начала. Это ситуация заполненной очереди и попытки записи в нее блокируются.
Использования типа данных «очередь».
Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.
Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нём и на первый незанятый элемент.
Выполнение работы.
Исходный код программы:
Запускаем программу, "создаем"(а на деле просто меняем флаг) очередь и заполняем ее элементами
и т.д. затем выводим содержимое очереди на экран
строим диаграмму, демонстрирующую состояние очереди при ее заполнении и удалении элементов из нее
Удалим несколько элементов и выведем содержимое очереди вновь
Вывод: Принцип FIFO широко используется не только в повседневной жизни, но и в IT, например очередь к HDD или МФУ на ввод-вывод информации. Я в данной лабораторной работе решил использовать не тип данных «очередь», а тип данных «вектор», это обусловлено возможностью обращения к элементам типа «вектор» по индексу, у типа данных «очередь» такая возможность отсутствует (можно вывести только первый и конечный элементы очереди).
