Программа должна получить входные данные количество потоков, время потока, номер потока и расположить данные в порядке их обработки цп.
 Скачать 220.66 Kb.
|
|
Введение С помощью данной лабораторной работы можно понять, каким образом работает планировщик потоков операционной системы, как работает бинарный поиск и когда следует его применять. Благодаря данной лабораторной работе можно рассмотреть, как реализуются и работают сортировки подсчётом, Шелла и пузырьком. При реализации данной лабораторной работы было изучено много нового и необходимого для дальнейшего программирования, также, был получен опыт реализации серьезных задач. Постановка задачи Реализовать программу, эмулирующую работу планировщика потоков операционной системы. ОС распоряжается ресурсом ЦП и этот ресурс может быть выделен исполняемым сущностям – потокам. В ОС в каждый момент времени может быть несколько потоков ожидающих выполнения, поэтому возникает задача выбора очередного потока на исполнение. Прерывание выполнения потока не допускается. Ресурс ЦП представлен в виде непрерывного кванта времени, который может быть выделен потоку для его исполнения. Алгоритм выбора очередного потока на исполнение будет состоять в выборе потока который имеет наиболее близкое значение к выделенному кванту времени ЦП. Программа должна получить входные данные: количество потоков, время потока, номер потока и расположить данные в порядке их обработки ЦП. Вывод осуществляется в виде таблицы с полями:  Программа должна иметь интерфейс для реализации диалога с пользователем, который включает в себя: Возможность выбора количества потоков; Выбор способа задания времени потока: Ручной ввод; Генерация случайным образом; Чтение из файла; Выбор метода сортировки: Сортировка пузырьком; Сортировка Шелла (последовательность Хиббарда); Сортировка Подсчетом; Выбор способа задания времени ЦП: Ручной ввод; Генерация случайным образом; Чтение из файла; Если количество заданных потоков не превышает 21, то результат работы программы должен выводиться на экран, иначе в файл; Должна быть реализована проверка данных, введенных пользователем, на корректность. В случае ошибки необходимо известить об этом пользователя и предложить повторить ввод. Чтобы пользователь имел возможность сравнить эффективность сортировки разными алгоритмами, программа должна выводить на экран: Время выполнения процедуры сортировки; Число выполненных перестановок и сравнений; По окончанию выполнения сортировки, необходимо предложить пользователю применить другой алгоритм сортировки. Руководство пользователя Запуск программы осуществляется непосредственно с помощью исполняемого файла. После запуска программы, появится приветствие пользователя, и программа сразу же предложит на выбор 3 способа задания времени потоков операционной системы.  Ввод осуществляется с клавиатуры. Допустим, в качестве примера, введем 1.  Программа известит пользователя о подключенной процедуре и запросит ввести необходимое количество потоков. Введем, например, количество потоков = 10.000.000.  После выполнения указанной процедуры, программа известит пользователя о конце процедуры. Далее, программа предложит отсортировать данные несколькими способами, какими – видно на изображении. Выберем 3 для примера.  После выполнения сортировки программа выведет на экран количество сравнений, перестановок и время, затраченное на выполнение. Как видите, время затраченное на сортировку 10 миллионов потоков = 147 мс, что представляет собой очень хороший результат. (Прим. Intel Core i5-4670K - 3.40Ghz) Также, пользователю будет предложено применить другой алгоритм сортировки к исходным данным. Мы же выберем 2, и продолжим работу с программой.  Программа предложит пользователю выбрать способ задания времени ЦП. Выберем 1. Программа начнет располагать потоки в порядке их выполнения ЦП, если количество потоков не превышает 21, то результат работы выведется на экран. В нашем случае запись будет произведена в файл.  Когда программа закончит выполнение алгоритма и произведет запись результата работы в файл, на экране появится время, затраченное на работу. Также, программа предложит пользователю продолжить работу с ней с самого начала. Руководство программиста Описание структуры программы Программа состоит из следующих файлов: исполняемого файла (Лабораторная работа №1.exe); файла, содержащего время потоков (Input_Stream_LABA.txt); файла, содержащего время ЦП(Input_CP_LABA.txt); файла, в который сохраняется результат работы (Output_LABA.txt). В программе реализованы следующие процедуры: procedure PROTECTION_FOOL_STREAM; - процедура проверки ввода количества потоков, введенных пользователем (защита от введения символов и т.п). procedure PROTECTION_FOOL_MENU; - процедура проверки ввода в меню, выбор в котором представляется из 3 вариантов ответа. procedure PROTECTION_FOOL_MENU_1; - тоже самое, что PROTECTION_FOOL_MENU, но для меню, в котором только 2 варианта ответа. procedure Input_random; - генерация времени потоков случайным образом (random(255)). procedure Input_hand; ввод времени потоков вручную. procedure Input_file; - ввод времени потоков из файла Input_Stream_LABA.txt. Procedure Time_CP_Random; - генерация времени ЦП случайным образом. procedure SORT_bubble; - сортировка пузырьком. Procedure SORT_Shell; - сортировка Шелла (последовательность Хиббарда). Procedure SORT_Count; - сортировка подсчётом. procedure Copy_Arr; - процедура копирования массива (необходима для повторения сортировок над исходными данными). procedure Output_head; - вывод на экран «головы» таблицы, в которую будет записываться результат работы программы. Procedure Output_Body; - вывод на экран «тела» таблицы. procedure Output_End; - полоска, завершающая таблицу. Procedure Output_File_Head; - то же самое что и Output_head но, вывод происходит в файл. procedure Output_File_LAB; - то же самое что Output_Body но, вывод происходит в файл. procedure Output_File_End; - то же самое что Output_End но, вывод происходит в файл. procedure Output_Data_Entered; - вывод исходного массива на экран (выполняется, если количество элементов в массиве не превышает 21). procedure Tabl_data_Entered_Head; - «голова» таблицы для вывода промежуточных данных . Procedure Output_Sort_Data; - вывод сортированного массива на экран (выполняется, если количество элементов в массиве не превышает 21). Procedure Binary_Search; - процедура бинарного поиска. Procedure Shift_Array; - процедура сдвига массива, выполняется после бинарного поиска, и по сути «выкидывает» из массива найденный элемент. В программе можно выделить 5 блоков: Процедуры ввода времени потоков 3 разными способами: Input_random, Input_hand, Input_file. Процедуры сортировки массивов 3 разными способами и вспомогательная процедура для них: SORT_bubble, SORT_Shell, SORT_Count, Copy_Arr. Процедура бинарного поиска и вспомогательная процедура для нее: Binary_Search,Shift_Array. Процедуры вывода данных на экран\в файл: Output_head, Output_Body, Output_end, Output_File_Head, Output_File_LAB, Output_File_End,Tabl_data_Entered_Head, Output_Data_Entered, Output_Sort_Data. Процедуры защиты ввода: PROTECTION_FOOL_STREAM, PROTECTION_FOOL_MENU, PROTECTION_FOOL_MENU_1. Описание структур данных a,b: array of byte; – массивы для хранения времени потоков a – массив в который записываются исходные данные, b – массив в котором происходит сортировка; Number_El: array of integer; – массив в котором хранятся номера потоков; i – переменная в которую сохраняется количество введенных потоков; j – переменная используемая в циклах for; z – переменная используемая в процедуре сортировки пузырьком. Сохраняет значение b[j] а потом присваивает его значению b[j+1]; t1, t2 – переменные, используемые для измерения времени. Время выполнения высчитывается как t2 – t1; k – переменная используемая в процедуре сортировки пузырьком. Используется для сохранения номера элемента. Сохраняет значение Number_El [j] а потом присваивает его значению Number_El [j+1]; s – переменная в которую сохраняется длинна массива. Используется в бинарном поиске как правая граница массива; Time_CP – переменная в которую сохраняется выделенный квант времени ЦП; Menu_Input – переменная используемая в меню выбора; mid, left, right – переменные используемые в бинарном поиске. Left – левая граница поиска, Right – правая граница поиска, mid – середина выбранного участка поиска; Length_Arr – переменная в которую сохраняется длинна массива. Используется при чтении времени потоков из файла (определяет, массив какой длины нужен, чтобы все данные из файла в него уместились) Используется в циклах сортировки пузырьком, в которых принимает значение длины массива. С помощью этой переменной определяется, надо ли выводить результаты работы на экран (если ее значение не превышает 21, то результат работы выводится на экран). counter_per, counter_sr, counter_iter : integer; - счетчики перестановок, сравнений и итераций в сортировках. Number_Inter, Ost_Time_CP :integer; - счетчик итераций в алгоритме бинарного поиска, и переменная в которую сохраняется оставшийся квант времени ЦП после нахождения потока, время выполнение которого было наиболее близко к исходному кванту времени ЦП. str1, str2, str3, pr:string; str1 – строка-полоска разделяющая таблицу вывода результата работы. str2 – чистая строка, в которой нет никаких данных, ее значение присваивается str3 после нахождения всех потоков которые могут быть выполнены за заданный квант времени ЦП и вывода данных на экран; str3 – основная строка таблицы, выводящей результаты работы программы; pr – переменная используемая для заполнения str3. n1:byte; - переменная используемая в процедуре чтения данных из файла. F: Text;- файл из которого происходит чтение времени потоков; Cp_File:text; - файл из которого происходит чтение кванта ЦП; Q: Text; - файл, в который осуществляется вывод результата работы программы. Err_1, Sort_Repeat, Time_CP_GEN, Time_CP_HAND, Time_CP_FILE, CP, Output_File, Ex_Quit :boolean; Err_1 – переменная определяющая произошла ли ошибка при вводе данных пользователем; Sort_Repeat– переменная определяющая нужно ли повторить сортировку с исходным массивом; Time_CP_GEN, Time_CP_HAND, Time_CP_FILE – переменные определяющие то как должен генерироваться квант времени ЦП; Output_File – переменная определяющая должен ли быть осуществлен вывод данных в файл; Ex_Quit – переменная запрашивающая выход из программы; CP – переменная используемая в бинарном поиске. Описание алгоритмов Программа работает по следующему алгоритму: Запрашивается способ задания времени потоков; Запрашивается количество потоков; Запрашивается метод сортировки; Запрашивается способ задания времени ЦП; Выполняется бинарный поиск; Вывод результатов работы программы. Сортировка пузырьком (см. Приложение – Сортировка пузырьком). Или сортировка простыми обменами. Принцип действий: массив обходится от начала до конца, и в нем меняются местами не отсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим не отсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути не отсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Продолжая в том же духе, будем обходить всё уменьшающуюся не отсортированную часть массива, перемещая найденные максимумы в конец. Сортировка Шелла. (см. Приложение – Сортировка Шелла). Сортировка Шелла – алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии d друг от друга. Иными словами – это сортировка вставками с предварительными «грубыми» проходами. В лабораторной работе осуществлена сортировка Шелла последовательностью Хиббарда (длина промежутков dмежду сравниваемыми элементами равна d[n]:=2*d[n-1]+1) Получается последовательность вида 1,3,7,15… Сортировка подсчетом (см. Приложение – Сортировка подсчетом). Сортировка подсчётом – алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Для сортировки необходимо создание дополнительного массива из нулей, длина которого задается максимальным числом встречающимся в массиве. В нашем случае длина вспомогательного массива arr_sort_countбудет равна 256. Алгоритм сортировки следующий: Последовательно пройти по массиву B и записать в Arr_Sort_Count[B[i]] количество чисел равных B[i]; В цикле от I=1 до 255 пройти по массиву Arr_Sort_Count и записать число I в массив B arr_sort_count[i] раз. Бинарный поиск (см. Приложение – Бинарный поиск). Бинарный поиск – Алгоритм поиска элемента в отсортированном массиве. Сначала делим массив пополам и сравниваем элемент, который ищем с элементом в середине. Если они равны, то элемент, который мы ищем найден. Если же элемент, который мы ищем, меньше элемента в середине массива, то продолжим поиск в левой части массива (для массива сортированного по возрастанию), если элемент больше, то поиск следует продолжить в правой части. Далее, выбранную часть массива опять делим пополам и выполняем сравнение. Повторяем действия 2,3 до тех пор, пока искомый элемент не будет найден или пока не пройдем массив до конца. Если искомый элемент и элемент в массиве не совпали, выбирается первый элемент больше чем заданный. Заключение В программе реализован интерфейс осуществляющий общение с пользователем, программа умеет определять некорректный ввод и предлагать ввести данные заново. Также, реализована возможность выбора метода сортировки (сортировка пузырьком, сортировка Шелла (последовательность Хиббарда), сортировка подсчётом), способа задания времени потоков и кванта ЦП 3 разными способами (ручной ввод, генерация случайным образом, чтение из файла), реализован алгоритм бинарного поиска. Литература Сортировка Шелла - [https://ru.wikipedia.org/wiki/ Сортировка_Шелла] Методы сортировки -[http://habrahabr.ru/post/204968/] Пузырьковая сортировка и все-все-все - [http://habrahabr.ru/post/204600/] Алгоритмы сортировки. Часть 1 - [http://www.compdoc.ru/prog/pascal/algorithms_of_sorting_part1/] Алгоритмы сортировки. Часть 2 - [http://www.compdoc.ru/prog/pascal/algorithms_of_sorting_part2/] Бинарный поиск -[https://ru.wikipedia.org/wiki Двоичный_поиск] Я не могу написать бинарный поиск - [http://habrahabr.ru/post/146228/] Учебник по языку программирования Pascal -[http://pas1.ru/pascaltextbook] Приложения Сортировка пузырьком procedure SORT_bubble; var i, j: integer; begin counter_iter := 0; counter_sr := 0; counter_per := 0; Length_Arr := High(b); textcolor(10); Writeln; Writeln('<<Подключена процедура сортировки пузырьком>>'); Textcolor(7); t1 := milliseconds; for i := 0 to Length_Arr - 1 do begin counter_iter := counter_iter + 1; for j := 0 to (Length_Arr - 1) - i do begin counter_sr := counter_sr + 1; if b[j] > b[j + 1] then begin z := b[j]; b[j] := b[j + 1]; counter_per := counter_per + 1; b[j + 1] := z; k := Number_El[j]; Number_El[j] := Number_El[j + 1]; Number_El[j + 1] := k; end; end; end; textcolor(10); Writeln('<<Конец процедуры... >>'); Textcolor(7); t2 := milliseconds; end; Сортировка Шелла (Последовательность Хиббарда) procedureSORT_Shell; var d: array [0..29] of integer := (1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823); g, w: integer; c: boolean; begin counter_iter := 0; counter_sr := 0; counter_per := 0; t1 := 0; t2 := 0; textcolor(10); Writeln; Writeln('<< Подключена процедура сортировки Шелла >>'); Textcolor(7); t1 := milliseconds; while d[w + 1] <= Length(b) do inc(w); repeat g := d[w]; i := g; repeat j := i - g; if j + g >= Length(b) then break; c := True; repeat counter_sr := counter_sr + 1; if b[j] <= b[(j + g)] then c := False else begin z := b[j]; b[j] := b[j + g]; b[j + g] := z; k := Number_El[j]; Number_El[j] := Number_El[j + g]; counter_per := counter_per + 1; Number_El[j + g] := k; end; dec(j, g); until not ((j >= 0) and C); inc(i); until not (i <= Length(b)); dec(w); until not (w <> -1); t2 := milliseconds; textcolor(10); Writeln('<<Конец процедуры... >>'); Textcolor(7); end; Сортировка подсчётом procedure SORT_Count; var arr_sort_count, place: array of byte; i, j, k: integer; begin counter_iter := 0; counter_sr := 0; counter_per := 0; t1 := 0; t2 := 0; t1 := milliseconds; textcolor(10); Writeln; Writeln('<< Подключена процедура сортировки подсчётом >>'); Textcolor(7); setlength(arr_sort_count, 256); setlength(place, 257); setlength(Number_El, High(b) + 1); for i := 0 to High(b) do inc(Arr_sort_count[b[i]]); for i := 1 to 255 do place[i] := place[i - 1] + Arr_sort_count[i]; for i := 0 to High(b) do begin if place[b[i]] <>0 then //Если будет = 0 вылезет Outside index begin Number_El[place[b[i]] - 1] := i; dec(place[b[i]]); end end; for i := 1 to 255 do for j := 1 to Arr_sort_count[i] do begin b[k] := i; inc(k); end; textcolor(10); Writeln('<<Конец процедуры... >>'); Textcolor(7); t2 := milliseconds; arr_sort_count := nil; //Очистка памяти place := nil; end; Бинарный поиск procedure Binary_Search; begin cp := false; if Time_CP >= B[0] then begin cp := true; left := 0; right := s; while left <= right do begin mid := (left + right) div 2; if Time_CP < B[mid] then right := mid - 1 else if ((mid) <= S) and (Time_CP >= B[mid]) then left := mid + 1 else begin left := mid + 1; right := mid; if Time_CP = B[mid] then begin left := mid + 1; right := mid; end; end; if time_cp - b[mid] <0 then mid := mid - 1; end; end; end; |