Universitatea de Stat din Moldova
Facultatea de Fizică şi Inginerie
Departamentul Fizica Aplicată şi Informatica
Exercițiu practic
Tema: „Sincronizarea firelor”
Lucrarea a fost elaborată de
Lupu Dumitru, gr. TI221
Lucrarea a fost verificată de
Isacova C., conf. univ.
Chişinău, 2024
Condiția: Realizați sortarea ShellSort utilizând mai multe fire, astfel încât fiecare fir
să aibă pasul înjumătățit: N/2, N/4, N/8 etc.
Pentru a realiza acest exercițiu vom utiliza biblioteca windows.h, care permite
programarea obiectelor sistemului de operare windows.
Primul pas este să includem toate bibliotecile necesare:
#include <iostream>
#include <windows.h>
#include <vector>
#include <chrono>
Aceste biblioteci se utilizează pentru:
1. iostream – biblioteca pentru afișarea datelor pe ecran și înscrierea lor de la
tastatură.
2. windows.h – biblioteca ce permite crearea și dirijarea obiectelor windows cum
ar fi firele, procesele sau obiectele pentru sincronizare.
3. vector – biblioteca standart care permite crearea tablourilor unidimesionale și
dirijarea lor. Această bibliotecă o vom utiliza pentru comoditatea manipulării
cu masivul de date.
4. chrono – biblioteca care permite realizarea măsurarării timpului de execuție.
După ce am inclus toate bibliotecile necesare, urmează să declarăm variabilele
globale, și să definim careva valori, care le vom utiliza în programul nostru.
vector<int> arr; //Masivul de date
int gap; //Pasul sortării
HANDLE hMutex; //Obiectul pentru sincronizarea firelor
const int N = 30; //Marimea masivului de date
const int numThreads = 5; //Numarul de fire
Obiectul mutex este un obiect de sincronizare care nu permite unui alt fir să
acceseze resursele de memorie, atât timp cât celălalt fir nu a terminat toate
instrucțiunile.
În continuare vom avea nevoie de două funcții.
Funcția BOOL isSorted(int size) va verifica dacă masivul este sortat și este
realizată astfel:
BOOL isSorted(int size)
{
while (--size > 0)
if (arr[size] < arr[size - 1])
return FALSE;
return TRUE;
}
Funcția DWORD WINAPI ShellSortThread(LPVOID lpParam) va fi executată
de fiecare fir de execuție și va efectua sortarea utilizând algoritmul Shell Sort. Ea este
realizată în felul următor:
DWORD WINAPI ShellSortThread(LPVOID lpParam) {
int threadID = *(int*)lpParam;
// Așteaptă să obțină acces exclusiv la vectorul de numere
WaitForSingleObject(hMutex, INFINITE);
for (int j = gap; j < [Link](); j++)
{
int temp = arr[j];
int k;
for (k = j; k >= gap && arr[k - gap] > temp; k -= gap)
arr[k] = arr[k - gap];
arr[k] = temp;
}
gap /= 2;
cout << "Thread " << threadID << " finished sorting." << endl;
// Eliberează accesul exclusiv la vectorul de numere
ReleaseMutex(hMutex);
return 0;
}
După definirea și realizarea tuturor variabilelor, constantelor și funcțiilor
necesare, începem programarea funcției principale. Pentru început declarăm și
inițializăm variabila start care va păstra informația despre timpul la care a început
realizarea programului:
auto start = chrono::high_resolution_clock::now();
Apoi generăm un șir aleator de numere pentru masivul de date și inițializăm
variabila gap:
// Seed-ul generării aleatoare bazat pe timpul curent
srand(GetTickCount64());
for (int i = 0; i < N; ++i)
arr.push_back(rand() % 100);
gap = (int)[Link]() / 2;
Următorul pas este să declarăm și inițializăm firele de execuție și mutex-ul:
// Initializare fire de executie și mutex
hMutex = CreateMutex(NULL, FALSE, NULL);
int threadIndex[numThreads];
DWORD threadIDs[numThreads];
HANDLE threads[numThreads];
// Crearea și pornirea firelor de executie
for (int i = 0; i < numThreads; i++) {
threadIndex[i] = i;
threads[i] = CreateThread(NULL, 0, ShellSortThread,
&threadIndex[i], 0, &threadIDs[i]);
}
După ce firele au fost create, așteptăm ca toate firele să se execute, ca apoi să
putem închide firele și mutexul:
// Așteaptă ca toate firele de execuție să se termine
WaitForMultipleObjects(numThreads, threads, TRUE, INFINITE);
// Eliberarea resurselor
CloseHandle(hMutex);
for (HANDLE hThread : threads) {
CloseHandle(hThread);
}
Verificăm dacă masivul este sortat și afișăm mesajul corespunzător pe ecran:
if (isSorted([Link]()))
cout << "Masivul este sortat" << endl;
else
cout << "Masivul nu-i sortat" << endl;
Declarăm și inițializăm variabila end care va păstra informația despre timpul la
care a finisat executarea programului, apoi inițializăm variabila duration care va
păstra timpul de execuție a programului, egal cu diferența dintre timpul momentului
de start și momentului de sfârșit. Afișăm pe ecran durata de execuție:
auto end = chrono::high_resolution_clock::now();
chrono::duration<double> duration = end - start;
cout << "Timpul de executie: " << [Link]() << " secunde\n";
Codul complet al programului
#include <chrono>
#include <iostream>
#include <vector>
#include <windows.h>
using namespace std;
// Variabile și constantele globale pentru a comunica între firele de execuție
vector<int> arr; //Masivul de date
int gap; //Pasul sortării
HANDLE hMutex; //Obiectul pentru sincronizarea firelor
const int N = 30; //Marimea masivului de date
const int numThreads = 5; //Numarul de fire
// Functia care verifica daca masivul este sortat
BOOL isSorted(int size)
{
while (--size > 0)
if (arr[size] < arr[size - 1])
return FALSE;
return TRUE;
}
// Funcția care va fi executată de fiecare fir de execuție
// Sortarea folosind algoritmul Shell Sort
DWORD WINAPI ShellSortThread(LPVOID lpParam) {
int threadID = *(int*)lpParam;
WaitForSingleObject(hMutex, INFINITE); // Așteaptă să
obțină acces exclusiv la vectorul de numere
for (int j = gap; j < [Link](); j++)
{
int temp = arr[j];
int k;
for (k = j; k >= gap && arr[k - gap] > temp; k -= gap)
arr[k] = arr[k - gap];
arr[k] = temp;
}
gap /= 2;
cout << "Thread " << threadID << " finished sorting." << endl;
ReleaseMutex(hMutex); // Eliberează
accesul exclusiv la vectorul de numere
return 0;
}
int main() {
auto start = chrono::high_resolution_clock::now();
// Generare aleatoare a vectorului de numere
srand(GetTickCount64()); // Seed-ul
generării aleatoare bazat pe timpul curent
for (int i = 0; i < N; ++i)
arr.push_back(rand() % 100); // Generează
numere întregi aleatoare între 0 și 99
gap = (int)[Link]() / 2; // Setează spațiul
inițial între elemente
// Initializare fire de executie și mutex
hMutex = CreateMutex(NULL, FALSE, NULL);
int threadIndex[numThreads];
DWORD threadIDs[numThreads];
HANDLE threads[numThreads];
// Crearea și pornirea firelor de executie
for (int i = 0; i < numThreads; i++) {
threadIndex[i] = i;
threads[i] = CreateThread(NULL, 0, ShellSortThread, &threadIndex[i], 0,
&threadIDs[i]);
}
// Așteaptă ca toate firele de execuție să se termine
WaitForMultipleObjects(numThreads, threads, TRUE, INFINITE);
// Eliberarea resurselor
CloseHandle(hMutex);
for (HANDLE hThread : threads) {
CloseHandle(hThread);
}
if (isSorted([Link]()))
cout << "Masivul este sortat" << endl;
else
cout << "Masivul nu-i sortat" << endl;
auto end = chrono::high_resolution_clock::now();
chrono::duration<double> duration = end - start;
cout << "Timpul de executie: " << [Link]() << " secunde\n";
return 0;
}
Studierea execuției programului
Pentru început, să sortăm un masiv mic de 30 de elemete utilizân 5 fire:
Acum să mărim numărul de fire până la 7 cu același număr de elemetne în
masiv:
Observăm că, deși nu tare considerabil, însă timpul de execuție a crescut.
Să încercăm să mărim numărul de elemente până la 250000, iar numărul de fire
îl vom micșora înapoi la 5:
Observăm că 5 fire nu s-au descurcat cu sortarea msivului. Să mărim numărul
de fire până la 20:
Deși timpul de execuție a crescut, masivul nostru este sortat. Toate aceste
diferențe le vom analiza în concluzia care urmează.
Concluzie: O primă constatare evidentă este că firele de execuție funcționează
într-un mod aparent nesecvențial, dat de natura lor paralelă, deși acest
aspect este o iluzie determinată de logica sistemului de operare. Pe
măsură ce adăugăm mai multe fire, observăm că timpul de execuție
crește proporțional. Acest fenomen este explicat de utilizarea unui obiect
mutex pentru sincronizarea resurselor, care împiedică accesul unui fir la
resursele utilizate de altul până când acesta nu termină execuția.
Un alt aspect observat este că odată cu creșterea numărului de date
în masiv, timpul de execuție crește corespunzător. Acest lucru este
intuitiv, deoarece creșterea numărului de date implică mai multe operații
de comparație și interschimbare, afectând astfel timpul de execuție.
De asemenea, am remarcat că 5 fire de execuție nu au reușit să
sorteze un masiv de 250000 de elemente, din cauza algoritmului Shell
Sort. Limitarea la doar 5 fire a dus la un pas de sortare redus de 5 ori,
rezultând într-o distanță prea mare între elementele sortate la final.
Pentru a remedia această situație, am crescut numărul de fire la 20, ceea
ce a dus la o creștere a timpului de execuție, dar a permis sortarea
masivului datorită numărului mai mare de fire implicat în proces.