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

Министерство  образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное  
учреждение высшего профессионального образования

Нижегородский государственный университет им. Н.И. Лобачевского 
 

Факультет вычислительной математики и кибернетики 
 
 
 
 
 
 
 
 
 

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

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

Выполнил: студент группы 8111

___________________ Пьянников А.А.

            Подпись 

Научный руководитель:

___________________ Сысоев А.В.

            Подпись 
 
 
 
 
 
 
 
 
 

Нижний  Новгород

2011

 

Содержание 
 

 

Введение

 
 
 

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

   Подсистема управления процессами и потоками ответственна за обеспечение процессов необходимыми ресурсами. ОС поддерживает в памяти специальные информационные структуры, в которые записывает, какие ресурсы выделены каждому процессу. Она может назначить процессу ресурсы в единоличное пользование или в совместное пользование с другими процессами. Некоторые из ресурсов выделяются процессу при его создании, а некоторые — динамически по запросам во время выполнения. Ресурсы могут быть приписаны процессу на все время его жизни или только на определенный период. При выполнении этих функций подсистема управления процессами взаимодействует с другими подсистемами ОС, ответственными за управление ресурсами, такими как подсистема управления памятью, подсистема ввода-вывода, файловая система.  

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

   Каждый раз, когда процесс завершается,  ОС предпринимает шаги, чтобы  «зачистить следы» его пребывания  в системе. Подсистема управления  процессами закрывает все файлы,  с которыми работал процесс, освобождает области оперативной памяти, отведенные под коды, данные и системные информационные структуры процесса. Выполняется коррекция всевозможных очередей ОС и списков ресурсов, в которых имелись ссылки на завершаемый процесс.

Постановка задачи

 
 
 

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

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

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

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

  Время работы потока - число из диапазона от 1 до 40000.

  Программа должна поддерживать не менее 20000 потоков.

 

Руководство пользователя

Основная  функция программы – моделирование  работы планировщика потоков ОС.

Чтобы начать работу, нужно запустить файл StreamOS.exe. 
 

 

Рис. 1. Вид  главного окна программы. 

Описание  компонентов главного окна программы StreamOS 

1.    Поля «Количество потоков» и «Квант времени» предназначены для ввода                                                             количества потоков и значения кванта времени соответственно.

 

   При нажатии клавиши Enter в «Количество потоков» будут сгенерировано введенное количество потоков и вывод их в поле «Первоначальные потоки» в формате ID и Time построчно. Диапазон значений количества потоков – от 1 до 20000, кванта времени – от 1 до 1000. 

2.    Компоненты «Случайная генерация», «Ручной ввод» и «Чтение из файла» необходимы для формирования самих потоков.

 

               При клике на «Случайная генерация» программа сгенерирует

            введенное количество потоков и выведет их в поле «Первоначальные потоки» в   

            формате ID Time построчно. Значения ID и Time колеблются в диапазонах от 1 

            до 20000 и от 1 до 40000 соответственно. 

               При клике на «Ручной ввод» станут доступны для ввода поля ID и Time. Чтобы             

            сформировать поток, необходимо ввести сначала ID (значение от 1 до 20000), затем     

            нажать клавишу Enter, ввести Time (значение от 1 до 40000) и снова нажать Enter.

            В результате введенные значения будут добавлены в поле «Первоначальные потоки». 

               При клике на «Чтение из  файла» откроется окно для выбора файла с первоначальными потоками формата .txt. После того, как файл будет выбран, программа выведет все данные в поле «Первоначальные потоки» в соответствующем формате.

    

3.    После того, как был сформирован хотя бы один поток (сгенерирован, прочитан из файла или введен вручную), для продолжения работы необходимо сообщить программе, что ввод был завершен. Для этого нужно кликнуть на кнопку «Ввод закончен». В результате чего станет доступным выбор типа построения расписания. Затем необходимо выбрать нужный тип и кликнуть на кнопку «Построить расписание». После фактического построения будет выведено затраченное время в секундах и результат отобразится, если количество потоков не больше 150 – в поле «Расписание», или же будет сохранен в выбранный вами файл.

 

4.    Компоненты «Сбросить введенные данные» и «Сбросить расписание» предназначены для очистки полей «Первоначальные потоки» и «Расписание» соответственно.

 

5.    Компонент  «Статистика» предназначен для  просмотра статистики по последнему  и по всем проведенным построениям  расписания.

 
 
 
 

 

Рис. 2. Вид окна статистики.

Описание  компонентов окна статистики программы  StreamOS: 

   При клике на кнопку «Статистика» откроется второе окно программы. В верхней части окна приведена статистика по последнему построению расписания, т.е. тип построения, время работы, количество перестановок и сравнений. Ниже можно выбрать любое проведенное построение и посмотреть его статистику. Внизу окна находится кнопка «Сравнить эффективность типов построения», при клике на которую в поле «Результат сравнения» будет выведена информация о самом эффективном и малоэффективном типах построения из всех проведенных на данный момент. 

   
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Руководство программиста

Описание  структуры программы

 

   В программе StreamOS используются некоторые стандартные модули среды Delphi: Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, ExtCtrls, ComCtrls и содержится дополнительное модальное окно для вывода статистики.

Описание  структур данных

 

   В программе StreamOS использованы объекты таких классов, как: TForm, TEdit, TLable, TButton, TMemo, TSaveDialog, TOpenDialog, TRadioGroup; стандартные процедуры обработки событий и собственные процедуры. 

   Описание процедур главного окна программы: 

1.  ruch_vvodClick(Sender: TObject) - активация полей ID и Time для ручного ввода при клике на кнопку «Ручной ввод».
2. kol_potokovKeyPress(Sender: TObject; var Key: Char) – контроль ввода в поле «Количество потоков» и случайная генерация ID и Time при нажатии клавиши Enter.
3. edit_idKeyPress(Sender: TObject; var Key: Char) – контроль ввода в поле «ID».
4. edit_timeKeyPress(Sender: TObject; var Key: Char) – контроль ввода в поле «Time».
5. kol_potokovChange(Se
6. nder: TObject) – контроль изменения поля «Количество потоков».
7. id_timeKeyPress(Sender: TObject; var Key: Char) – запрет ввода в поле «Первоначальные потоки».
8. generClick(Sender: TObject) – случайная генерация ID и Time при клике на кнопку «Случайная генерация».
9. from_fileClick(Sender: TObject) – открытие окна выбора файла при клике на кнопку «Чтение из файла» и последующая занесение данных в поле «Первоначальные потоки».
10. sbros_vved_dannyhClick(Sender: TObject) – очистка поля «Первоначальные потоки».
11. finish_clickClick(Sender: TObject) – активация компонента vid_sort («Тип построения расписания»).
12. kol_potokovClick(Sender: TObject), kvant_vremClick(Sender: TObject),  edit_idClick(Sender: TObject), edit_timeChange(Sender: TObject) – деактивация компонента vid_sort («Тип построения расписания»).
13. kvant_vremKeyPress(Sender: TObject; var Key: Char) – контроль ввода в поле «Квант времени».
14. kvant_vremChange(Sender: TObject) – контроль изменения поля «Квант времени».
15. begin_sortClick(Sender: TObject) – запуск построения расписания (сортировка значений ID и  Time из поля «Первоначальные потоки»), подсчет времени работы сортировки, количества перестановок и сравнений.
16. id_timeChange(Sender: TObject) – контроль изменения поля «Первоначальные потоки».
17. оtkryt – процедура обработки диалога с пользователем при открытии файла. Если диалог завершен успешно – загрузка данных в «Первоначальные потоки» из файла, иначе – предупреждение о том, что файл не выбран и закрытие диалога.
18. sohranit – процедура обработки диалога с пользователем при сохранении файла (эта процедура вызывается, когда количество потоков больше 150 и необходимо сохранение в файл). Если диалог завершен успешно – сохранение отсортированных данных в файл, иначе – предупреждение и вывод данных в поле «Расписание».
19. zapis_v_memo – процедура проверки – если количество потов больше 150 – вызов процедуры sohranit, иначе вывод отсортированных данных в «Расписание».
20. attention – предупреждение о неверно введенных в поля «Количество потоков» и «Квант времени» данных.
21. format – процедура построчно считывает построчно ID и Time из поля «Первоначальные потоки», удаляет пробелы, преобразует значения в числовые и записывает в массив.
22. proverka_kol_elem – если больше 150 потоков – вывод оповещения об этом и вызов процедуры sohranit, иначе вывод в поле «Расписание».
23. sbros_sortClick – процедура очистки поля «Расписание».
24. puzyrek, vybor, vstavka, merge, sliyanie, shell, qick_sort – процедуры сортировок.
25. stat_clickClick(Sender: TObject) – передача управления окну статистики при клике на кнопку “Статистика».