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

 
 
 

  Описание процедур окна статистики: 

1. FormActivate(Sender: TObject) – получение данных по последней и по всем проведенным сортировкам из главной программы при открытии статистики.
2. all_statChange(Sender: TObject) – процедура обработки изменения компонента all_stat. Выводит статистику по выбранной сортировке в отведенные ниже поля.
3. effectClick(Sender: TObject) – процедура поиска самой эффективной и малоэффективной из последний проведенных сортировок. Выводит статистику в поле «Результат».

 

   Глобальные переменные: 

1.  start, finish, res – переменные для замера времени работы сортировок.
2. i, j, k, w, v – счетчики циклов.
3. posled_sort – хранит значение ItemIndex последней сортировки и доступна в модальном окне статистики.
4. stat_massiv – массив, хранящий значения статистики сортировок, т.е. время, количество перестановок и сравнений, доступен в модальном окне статистики.
5. kolich_elem, kvant – хранят значения из полей «Количество потоков» и «Квант времени» соответственно.
6. bufer_1, bufer_2, buffer, bufer_str_1, bufer_str_2 – буферные переменные.
7. seredina, obmen_dlya_hoara – используются в сортировках для поиска середины массива и обмена элементов.
8. probely -  буфер для пробелов.
9. my_file – содержит путь к файлу при открытии или сохранении данных.
10. perestanovki, sravneniya – значения перестановок и сравнений.
11. file_otkr – файловая переменная (связывается с файлом при открытии/сохранении).
12. net – флаг для проверки условия.
13. ddd – своеобразный счетчик, увеличивающийся при выполнении определенного условия.
14. effect_massiv – массив, хранящий статистику по всем проведенным сортировкам.
15. effect_massiv_str – массив, хранящий названия всех проведенных сортировок под соответствующими номерами.

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

 
 

Пузырьковая сортировка. 
 

   Процедура BoobleSort(A: массив, min - начальный индекс, max - конечный индекс);

Начало

   цикл  для j от min до max

   цикл  для i от min до max-1

     если Ai больше чем Ai+1 то:

       1. обменять местами Ai и Ai+1

Конец процедуры 
 

Сортировка  выбором. 
 

   При сортировке массива a[1], a[2], ..., a[n] методом простого выбора среди всех элементов находится элемент с наименьшим значением a[i], и a[1] и a[i] обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a[2], a[3], ..., a[n], ... a[j], a[j+1], ..., a[n] до тех пор, пока мы не дойдем до подмассива a[n], содержащего к этому моменту наибольшее значение. 
 
 

Сортировка вставками. 
 

   Процедура BoobleSort(A: массив, min - начальный индекс, max - конечный индекс);

Начало

   Цикл  для i от min+1 до max

     j=i

     tmp=Ai; //запоминаем значение ещё неотсортированного элемента

     цикл пока (j>0 и Aj-1>tmp): //Сравниваем очередной отсортированный элемент, если он больше,

       1. Aj=Aj-1 //то сдвигаем его в большую сторону, освобождая место для вставки

       2. j=j-1 //Переходим к следующему элементу в отсортированной части массива

     Aj=tmp; //Место для нового элемента определено - вставляем его туда

Конец процедуры 
 

Сортировка  Хоара (быстрая сортировка). 
 

   Процедура QuickSort(A: массив, min - начальный индекс, max - конечный индекс);

Начало

   1. Выбрать supp - элемент со средним индексом (опорный):

   2. Начать просмотр с начала массива  и найти элемент, больший опорного  A[i]>supp

   3. Начать просмотр с конца массива  и найти элемент, меньший опорного  A[j]<supp

   4. Если предыдущие процессы ещё не пересеклись (i не больше j), то

        4.1. обменять найденные элементы  местами

        4.2. Перейти к п. 2. но не с  начала массива, а с места  предыдущей остановки

   5. Проанализировать индексы последнего  обмена.

        5.1 Если i меньше max, то запустить QSuickSort(A, i, max)

        5.2 Если j больше min, то запустить QSuickSort(A, min, j)

Конец процедуры 

Сортировка Шелла. 
 

   При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d (о выборе значения d см. ниже). После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше). 
 
 

Сортировка слиянием. 

   Сортировка слиянием выглядит так:

1. Сортируемый массив разбивается на две части примерно одинакового размера;
2. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
3. Два упорядоченных массива половинного размера соединяются в один.

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

   Нетривиальным этапом является соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем две стопки карт, лежащих рубашками вниз так, что в любой момент мы видим верхнюю карту в каждой из этих стопок. Пусть также, карты в каждой из этих стопок идут сверху вниз в неубывающем порядке. Как сделать из этих стопок одну? На каждом шаге мы берём меньшую из двух верхних карт и кладём её (рубашкой вверх) в результирующую стопку. Когда одна из оставшихся стопок становится пустой, мы добавляем все оставшиеся карты второй стопки к результирующей стопке.

  Заключение

 
 

В течение  работы над проектом было реализовано  следующее: 

1. Программа имеет современный интерфейс Windows-приложения.
2. Присутствует почти полный контроль ввода и оповещение пользователя в ошибочных ситуациях.
3. Присутствуют 6 видов сортировок: пузырьком, бинарными вставками, выбором, слиянием, метод Хоара (быстрая сортировка), метод Шелла. Все они полностью работоспособны.
4. Программа способна случайно генерировать либо читать данные из файла, или же предоставить пользователю возможность самому ввести значения ID и Time потоков.
5. Программа позволяет сохранять построенное расписание в файл.
6. Присутствует реализация подсчета времени работы каждой сортировки, количества перестановок и сравнений.

 

 

Литература

1. Turbo Pascal для студентов и школьников - Автор: Г. Г. Рапаков, С. Ю. Ружецкая, Издательство: БХВ-Петербург, ISBN 5-94157-240-3; 2007 г.
2. Свободное программное обеспечение. FREE PASCAL для студентов и школьников - Автор: Ю. Л. Кетков, А. Ю. Кетков, Издательство: БХВ-Петербург, Серия: Информатика и информационно-коммуникационные технологии, ISBN 978-5-9775-0604-5; 2011 г.
3. http://www.intuit.ru/department/pl/intdelphi/ - INTUIT.ru::Интернет-Университет Информационных Технологий - дистанционное образование, 2003-2011. Курс Введение в программирование на Delphi, Автор: В.Ю. Ачкасов.

Приложение. Фрагменты исходного кода программы

 

Приложение 1. 

Преобразование  текста и запись значений в массив. 

procedure TfMain.format;                   

begin                                       

for k := 0 to id_time.Lines.Count - 1 do // Цикл от 0 до количества строк в id_time – 1.                   

  begin                                                    

   bufer_str_1 := id_time.Lines[k];  // В буфер пишем k-ую строку из id_time.

    for i := 1 to length(bufer_str_1) do // Внутренний цикл от 1 до длины буфера.

     if bufer_str_1[i] = ' ' then // Проверка каждого символа буфера, если пробел, то:

      begin

       delete(bufer_str_1, pos(' ', bufer_str_1), 1); // удаляем пробел,

       n_probela := pos(' ', bufer_str_1); // запоминаем номер пробел.

      end;

   bufer := ' '; // Пишем в дополнительный буфер символ «пробел».

   insert(bufer_str_1, bufer, n_probela); // Вставляем в основной  буфер «пробел» с                                

                                               // запомненного номера пробела.

   bufer_str_2 := copy(bufer_str_1, pos(' ', bufer_str_1) + 1, 110); // Копируем в 

// третий  буфер строку из основного буфера с позиции пробела и до конца.

   delete(bufer_str_1, pos(' ', bufer_str_1), 110); // Удаляем из основного  буфера 

     // строку с позиции пробела и до конца.

   id_time_massiv[0, k] := StrToInt(bufer_str_1); // Преобразуем строки  из буферов в числовые 

   id_time_massiv[1, k] := StrToInt(bufer_str_2); // значения и записываем их в массив.

   end;

perestanovki := 0;         // Обнуляем  счетчик перестановок

sravneniya := 0;           // и  сравнений.

end; 
 

 

Чтение  из файла. 

procedure TfMain.otkryt; // Открывается диалоговое окно  для выбора файла для открытия.

begin

if OpenDialog1.Execute then     // Если файл выбран, то

  begin

   my_file := OpenDialog1.FileName;       // Запоминаем путь к файлу.

    if copy(my_file, length(my_file) - 3, 4) <> '.txt' then // Если путь к файлу не    

                                      // содержит расширения:

     my_file := my_file + '.txt';     // дописываем его.

   AssignFile(file_otkr, my_file);   // Связываем файл с  файловой переменной.

   Reset(file_otkr);        // Открываем для чтения.

   k := 0; // Счетчик.

    while not eof(file_otkr) do   // Пока не конец файла:

     begin

      Readln(file_otkr, bufer_str_1); // Читаем строку из файла в основной буфер.

      bufer_str_2 := copy(bufer_str_1, pos(' ', bufer_str_1) + 1, 110); // Копируем из 

// него в дополнительный буфер строку с позиции пробела и до конца,

      delete(bufer_str_1, pos(' ', bufer_str_1), 11); // Удаляем из основного буфера // строку с позиции                                                                   // пробела и до конца.

      id_time_massiv[0, k] := StrToInt(bufer_str_1);  // Записываем значения из буферов       

     id_time_massiv[1, k] := StrToInt(bufer_str_2);  // в массив.

      if length(bufer_str_1) <> 5 then // Если длина основного буфера не равна 5, то

       for v := 1 to 5 - length(bufer_str_1) do // цикл от 1 до разности 5 и длины  

  //буфера:

        bufer_str_1 := bufer_str_1 + '  '; // в буфер дописываем пробелы (для

// читабельности текста в программе).

      bufer_str_1 := bufer_str_1 + '  '; // Добавляем еще 2 пробела в качестве

// разделителя ID и Time.

      id_time.Lines.Add(bufer_str_1 + bufer_str_2); // Сливаем буферы в одну строку и

// пишем в id_time.

      inc(k); // Увеличиваем счетчик.

     end;

   CloseFile(file_otkr);                                 // Закрываем файл,