Лабник по СПО
.pdfДля того чтобы определить внутри потока метод, который нужно вызвать, добавим в заголовочный файл класса TNewThread переменную Box1 типа int.
public:
__fastcall TNewThread(bool CreateSuspended); int Box1;
};
Значение переменной Box1 определяет метод, вызываемый главным потоком. Логика работы главного потока определяется его основным методом Execute, который необходимо переопределить.
void __fastcall TNewThread::Execute()
{
while (!Terminated) switch (Box1)
{
case 1: Synchronize(MainForm->Paint1) ; break;
case 2: Synchronize(MainForm->Paint2) ; break;
case 3: Synchronize(MainForm->Paint3) ; break;
}
}
Напишем обработчик нажатия кнопки Пуск, запускающий потоки. Поток создаётся с помощью конструктора, который имеет один параметр. Параметр необходимо установить равным true, если поток должен начинать работу после вызова метода Resume, или false, если поток должен начинать работу сразу после его создания.
Процедуры ComboBox1Change, ComboBox2Change и ComboBox3Change задают приоритеты потокам. Пока эти процедуры не написаны, их вызовы нужно закомментировать.
Для наглядности работы потоков перед их запуском очищаем поверхность холстов командой, заполняющей поверхность холстов случайным цветом.
void __fastcall TMainForm::bbRunClick(TObject *Sender)
{
bbRun->Enabled = false; bbAbort->Enabled = true;
211
PDF created with pdfFactory Pro trial version www.pdffactory.com
n1=0;
n2=0;
n3=0;
St=1;
Abrt=0; PaintBox1->Canvas->Rectangle(0,0,150,150); PaintBox2->Canvas->Rectangle(0,0,150,150); PaintBox3->Canvas->Rectangle(0,0,150,150); T1 = new TNewThread(true); T1->FreeOnTerminate=true;
T1->Box1 = 1;
T2 = new TNewThread(true);
T2->FreeOnTerminate = true;
T2->Box1 = 2;
T3=new TNewThread(true);
T3->FreeOnTerminate=true;
T3->Box1=3;
T1->Resume();
T2->Resume();
T3->Resume(); ComboBox1Change(Sender); ComboBox2Change(Sender); ComboBox3Change(Sender);
}
Пишем обработчик нажатия кнопки Стоп, останавливающий потоки и восстанавливающий действие кнопки Пуск.
void __fastcall TMainForm::bbAbortClick (TObject *Sender)
{
bbAbort->Enabled=false; bbRun->Enabled=true; T1->Terminate(); T2->Terminate(); T3->Terminate();
St=0;
212
PDF created with pdfFactory Pro trial version www.pdffactory.com
}
Создаём процедуры задания приоритетов потокам. void __fastcall TMainForm::ComboBox1Change (TObject *Sender)
{
switch (ComboBox1->ItemIndex)
{
case 0: T1->Priority=tpIdle; break;
case 1: T1->Priority=tpLowest; break;
case 2: T1->Priority=tpLower; break;
case 3: T1->Priority=tpNormal; break;
case 4: T1->Priority=tpHigher; break;
case 5: T1->Priority=tpHighest; break;
case 6: T1->Priority=tpTimeCritical; break;
}
}
void __fastcall TMainForm::ComboBox2Change (TObject *Sender)
{
switch (ComboBox2->ItemIndex)
{
case 0: T2->Priority=tpIdle; break;
case 1: T2->Priority=tpLowest; break;
case 2: T2->Priority=tpLower; break;
case 3: T2->Priority=tpNormal;
213
PDF created with pdfFactory Pro trial version www.pdffactory.com
break;
case 4: T2->Priority=tpHigher; break;
case 5: T2->Priority=tpHighest; break;
case 6: T2->Priority=tpTimeCritical; break;
}
}
void __fastcall TMainForm::ComboBox3Change (TObject *Sender)
{
switch (ComboBox3->ItemIndex) {case 0: T3->Priority=tpIdle; break;
case 1: T3->Priority=tpLowest; break;
case 2: T3->Priority=tpLower; break;
case 3: T2->Priority=tpNormal; break;
case 4: T2->Priority=tpHigher; break;
case 5: T2->Priority=tpHighest; break;
case 6: T3->Priority=tpTimeCritical; break;
}
}
При создании формы задаём начальные значения приоритетов. void __fastcall TMainForm::FormCreate(TObject *Sender)
{
ComboBox1->ItemIndex=3;
ComboBox2->ItemIndex=3;
ComboBox3->ItemIndex=3;
214
PDF created with pdfFactory Pro trial version www.pdffactory.com
}
В обработчик нажатия кнопки Выход вводим вызов процедур, создающих и удаляющих потоки. Если этого не сделать, то при закрытии программы до запуска потоков может возникнуть системная ошибка. Свойство Kind кнопки Выход должно иметь значение bkCustom, иначе при работающих потоках кнопка не закроет программу. Команда остановки потоков должна вызываться раньше, чем будет вызвана команда закрытия программы.
void __fastcall TMainForm::bbCloseClick (TObject *Sender)
{
if (St==0) bbRunClick(Sender);
if (Abrt==0) bbAbortClick(Sender); Application->ProcessMessages(); Close();
}
Контрольные вопросы
1.Объясните понятия потока и процесса.
2.Объясните цели и способы синхронизации потоков.
3.Что такое приоритет и как его присвоить потоку?
4.Можно ли тот же процесс рисования с тремя холстами создать, используя один поток?
5.Что изменится в работе программы, если рисование на трёх холстах выполнить, используя один поток?
6.Что подразумевается под параллельной работой потоков в однопроцессорной системе?
7.Как запустить поток?
8.Как остановить поток?
9.Какие операции выполняет процедура Randomize?
215
PDF created with pdfFactory Pro trial version www.pdffactory.com
Лабораторная работа № 10. Сортировка массивов в параллельных потоках
Задание
Цель работы:
1.Изучение методов сортировки массивов по значениям.
2.Освоение приёмов создания и обработки массивов в управляемых параллельных потоках.
3.Закрепление навыков создания, закрытия и управления потоками в многопоточных приложениях.
4.Сравнение быстродействия методов сортировки массивов.
Содержание работы:
Разработка приложения для сортировки трёх массивов в управляемых потоках.
Технические требования к приложению:
Число массивов: 3.
Методы сортировки: метод пузырька, сортировка вставкой, быстрая сортировка. Отображаемая информация: процесс сортировки в трёх массивах одновременно. Способ отображения значения элемента массива - длиной линии.
Способ выделения отсортированных элементов массива - цветом линий.
Вводимые команды: начало сортировки, прекращение сортировки, продолжение сортировки и перекрашивание элементов массивов.
Форма отчёта:
Электронная форма в папке с именем Work10 на диске Н:.
Содержание отчёта:
Файлы проекта и исполняемый файл.
Алгоритмы сортировки
Каждый объект массива, подлежащего сортировке, должен обладать номером и
значением параметра, по которому необходимо производить сортировку. Параметр
216
PDF created with pdfFactory Pro trial version www.pdffactory.com
сортировки должен быть выражен переменной порядкового типа. Целью сортировки обычно является перемещение элементов массива таким образом, чтобы размер элемента увеличивался с увеличением его номера, хотя можно переставлять элементы и в обратном порядке.
Самым простым методом сортировки является "метод пузырька". Алгоритм метода показан на рис.10.1.
1
Начало
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
Цикл |
|
|
|
|
3 |
Цикл |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
по I = 1 g Nэ |
|
|
|
|
|
по J = (Nэ – 1) g I |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
Нет |
4 |
? |
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
Эл[J]>Эл[J–1] |
|
|
|
||||||||||||||
|
8 |
|
Цикл |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
5 |
|
|
|
|
Да |
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
по J = (Nэ – 1) g I |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
Т := Эл[J] |
|
|
|
|
|||||||||||
|
|
|
|
J = I |
|
|
|
|
|
|
|
|
|
|||||||||
|
9 |
|
Цикл |
|
|
|
6 |
|
|
|
|
|
|
|
|
|
Перестановка |
|||||
|
|
|
|
|
|
|
Эл |
[J+1] := Эл[J] |
|
|
|
элементов |
||||||||||
|
|
по I = 1 g Nэ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
I = Nэ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
Эл[J] := Т |
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Конец |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис.10.1. Схема работы системы сортировки по весу: Nэ - число элементов в массиве
Метод основан на сравнении значений двух соседних элементов массива. Если значение элемента массива с индексом J больше значения элемента массива с индексом J+1, то элементы меняют местами.
Если начать сравнение с конца массива, то получится, что элементы с меньшим размером, т.е. более "легкие", всплывают или перемещаются снизу вверх, если элементы массива расположить в виде столбца. Если начать сравнение с начала массива, то получится, что элементы с большим размером, т.е. более "тяжёлые", опускаются. Этот алгоритм следовало бы назвать "сортировкой по весу", но исторически сложилось так, что за данным алгоритмом закрепилось название "метод пузырька". Процедура сортировки, показанная на рис.10.1, опускает "тяжёлые" элементы.
Алгоритм сортировки по весу легко реализуется, но требует много времени для выполнения, так как нужно сравнить каждый элемент со всеми остальными. Более
217
PDF created with pdfFactory Pro trial version www.pdffactory.com
быстрым является алгоритм сортировки, называемый "сортировкой вставками". Алгоритм сортировки вставкой приведён на рис.10.2.
1
Начало
2
Цикл
по I = 1 g Nэ
3
Цикл по J = Nэ g I
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
4 |
? |
|
|
Нет |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
Эл[I]>Эл[J] |
||||||||||
|
|
|
|
|
|
|
8 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Цикл |
||
|
|
|
|
5 |
|
|
|
|
Да |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
по J = Nэ g I |
|||||
|
|
|
|
|
|
|
|
Т := Эл[J] |
|
|
|
J = I |
||||
Перестановка |
|
|
6 |
|
|
|
|
|
|
|
9 |
|
Цикл |
|||
элементов |
|
|
|
Эл[J] := Эл[I] |
|
|
|
|||||||||
|
|
|
|
по I = 1 g Nэ |
||||||||||||
|
|
|
|
|
7 |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I = Nэ |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
Эл[I] := Т |
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
10 |
Конец |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис.10.2. Схема работы системы сортировки вставками
В алгоритме сортировки вставками на каждом I-м этапе цикла I-й элемент Эл[I] вставляется в нужную позицию среди элементов, позиции которых уже упорядочены. На следующих этапах между уже упорядоченными элементами вставляются элементы, взятые из неупорядоченной области массива. Сортировка вставкой работает быстрее сортировки по весу потому, что не требуется сравнивать каждый элемент со всеми остальными.
Ещё быстрее работает алгоритм, который называют "быстрой сортировкой". Алгоритм быстрой сортировки показан на рис.10.3.
218
PDF created with pdfFactory Pro trial version www.pdffactory.com
1
Начало
2
Ввод границ Nн := Nэн; Nк := Nэк;
3
Расчёт
Mid := Эл[(Nн+Nк)/2]
4
Цикл Mid
10
Т:=Эл[Nн]
11
Эл[Nн] := Эл[Nк]
12
Эл[Nк] := Т
16
Ввод границ Nн:=Nэн;
18
Ввод границ Nк := Nэк;
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
? |
||
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|||
|
|
|
|
|
|
Inc(Nн) |
|
|
Да |
|
|
Эл[Nн]<Mid |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
Нет |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
? |
||
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|||
|
|
|
|
|
|
Dec(Nк) |
|
|
Да |
|
|
Эл[Nк]>Mid |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
Нет |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
? |
|||
|
|
|
|
|
|
|
|
|
|
Да |
9 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
Nн < Nк |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нет |
|||
|
|
Перестановка |
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
элементов |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
13 |
|
|
|
|
|
14 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
Inc(Nн) |
|
|
|
|
|
Цикл Mid |
||||||
|
|
|
|
|
|
Dec(Nr) |
|
|
|
|
|
Nн:>=Nк |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
|
Nк >?Nэн |
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Да |
|
|
|
19 |
|
|
||||||||||||
Нет |
|
|
|
|
|
|
|
Конец |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
17 |
|
? |
Нет |
|
|
|
|
|
|
|
||||||
Да |
Nн < Nэк |
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис.10.3. Схема работы системы быстрой сортировки
Поскольку все значения в первом множестве меньше, чем значения во втором множестве, то исходный массив будет отсортирован.
Nэн, Nэк - исходные границы подмножеств на начало цикла. При первом входе в процедуру это номера первого и последнего элементов массива. Nн, Nк - текущие границы подмножеств внутри цикла. Реально алгоритм нужно оформлять как рекурсивную процедуру, вызывающую саму себя с изменёнными границами подмножеств. Сортировка завершится, когда отдельные частичные подмножества, на которые разбивается исходный массив в процессе рекурсивных вызовов процедуры, будут содержать одинаковые значения. Для каждого частичного подмножества выбирается своё значение Mid. Затем элементы в этих подмножествах переставляются с выбранным значением Mid, тем самым вновь разбиваясь ещё на два подмножества, к которым снова рекурсивно применяется процедура сортировки.
219
PDF created with pdfFactory Pro trial version www.pdffactory.com
Схема программы для реализации на языке Delphi
Сравнительный анализ быстродействия трёх алгоритмов сортировки произведём одновременной сортировкой одинаковых исходных массивов в трёх параллельных потоках. Схема программы показана на рис.10.4. Первый поток выполняет быструю сортировку, второй - сортировку вставкой, третий - сортировку по весу.
|
|
|
1 |
|
|
|
|
|
|
|
Начало |
|
|
|
|
|
7 |
|
2 |
? |
Да |
|
|
|
Останов |
|
|
||||
|
Выход |
|
|
|
|||
|
потоков |
16 |
|
|
|||
|
|
Нет |
|
|
|||
|
|
|
3 |
Конец |
|
||
|
|
Да |
? |
|
|
|
|
|
|
|
Потоки действ. |
|
|
||
|
4 |
? |
|
Нет |
|
|
|
Да |
Стоп |
8 |
|
|
|
||
? |
Нет |
|
|
||||
|
Нет |
|
|
||||
|
|
|
Пуск |
9 |
|
|
|
|
5 |
? |
10 |
Да |
? |
Нет |
|
|
|
|
|||||
|
Закрасить |
|
Продолжить |
||||
Нет |
Создание массивов |
|
|
||||
|
|
Да |
|
|
Да |
|
|
|
|
|
|
|
|
|
|
|
6 |
|
11 |
|
|
|
|
|
Окраска |
Создание потоков |
|
|
|||
|
линий |
|
|
||||
|
|
|
|
|
|
||
|
|
|
12 |
|
|
|
|
|
|
|
Запуск потоков |
|
|
|
|
|
13 |
|
14 |
|
15 |
|
|
|
Поток 1 |
Поток 2 |
|
Поток 3 |
Рис.10.4. Схема программы сортировки, реализуемой на языке Delphi
Для управления потоками сортировки используем набор кнопок: Пуск, Стоп, Продолжить, Закрасить и Выход. Кнопка Пуск должна вызвать операторы для создания трёх одинаковых массивов случайных чисел, вывода на экран начальных значений элементов, созданных массивов и запустить три потока сортировки. Кнопка Стоп должна остановить потоки с возможностью их продолжения с того места, на котором они были остановлены. Продолжение сортировки, без создания новых массивов, должно происходить после нажатия кнопки Продолжить.
220
PDF created with pdfFactory Pro trial version www.pdffactory.com