ЛР. Моделирование работы планировщика потоков ОС

Post date: Oct 2, 2010 11:40:32 AM

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

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

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

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

Технические требования:

1. Время работы потока - это число из диапазона от 0 до 255 (тип byte).
2. Программа должна поддерживать не менее 10000 потоков.

Каждому студенту необходимо реализовать не менее 3 сортировок. Полный список рассмотренных сортировок ниже:

1. Сортировка пузырьком.
2. Сортировка выбором.
3. Сортировка вставками.
4. Сортировка слиянием.
5. Сортировка Хоара.
6. Сортировка Шелла.
7. Сортировка подсчётом (визуализация).

Лучший источник информации по сортировкам: Дональд Кнут. Искусство программирования, том 3. Сортировка и Поиск.

Ищите свою фамилию в списке (81-02, 81-12), порядковый номер - соответствует набору сортировок, которые необходимо реализовать:

1. Сортировка пузырьком. Сортировка слиянием. Сортировка Хоара.
2. Сортировка выбором. Сортировка слиянием. Сортировка подсчётом.
3. Сортировка вставками. Сортировка слиянием. Сортировка подсчётом.
4. Сортировка пузырьком. Сортировка Хоара. Сортировка Шелла.
5. Сортировка выбором. Сортировка Хоара. Сортировка слиянием.
6. Сортировка вставками. Сортировка Хоара. Сортировка слиянием.
7. Сортировка пузырьком. Сортировка Шелла. Сортировка подсчётом.
8. Сортировка выбором. Сортировка Шелла. Сортировка Хоара.
9. Сортировка вставками. Сортировка Шелла. Сортировка подсчётом.
10. Сортировка пузырьком. Сортировка подсчётом. Сортировка слиянием.
11. Сортировка выбором. Сортировка подсчётом. Сортировка Шелла.
12. Сортировка вставками. Сортировка подсчётом. Сортировка Хоара.
13. Сортировка выбором. Сортировка слиянием. Сортировка Шелла.
14. Сортировка вставками. Сортировка Шелла. Сортировка Хоара.

По лабораторной работе необходимо предоставить отчёт (шаблон отчёта).

Сдача отчёта должна быть осуществлена не позднее, чем через неделю после сдачи программы.

На выполнение лабораторной работы отводится 4 недели.

Dead Line: 23:59 29.10.2010