Đề tài Nghiên cứu lập trình thread và ứng dụng

Tách (detaching) Thủ tục pthread_detach() có thể được sử dụng để tách một thread thậm chí thread đó được tạo ra với thuộc tính là có thể nối được.Không có thủ tục ngược lại. Ví dụ về nối thread: #include #include #include #define NUM_THREADS 4 void *BusyWork(void *t) { int i; long tid; double result=0.0; tid = (long)t; printf("Thread %ld starting...\n",tid); for (i=0; i<1000000; i++) { result = result + sin(i) * tan(i); } printf("Thread %ld done. Result = %e\n",tid, result); pthread_exit((void*) t); } int main (int argc, char *argv[]) { Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 25 Lớp : K51CHTTT pthread_t thread[NUM_THREADS]; pthread_attr_t attr; int rc; long t; void *status; /* Initialize and set thread detached attribute */ pthread_attr_init(&attr); pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE); for(t=0; t<NUM_THREADS; t++) { printf("Main: creating thread %ld\n", t); rc = pthread_create(&thread[t], &attr, BusyWork, (void *)t); if (rc) { printf("ERROR; return code from pthread_create() is %d\n", rc); exit(-1); } } /* Free attribute and wait for the other threads */ pthread_attr_destroy(&attr); for(t=0; t<NUM_THREADS; t++) { rc = pthread_join(thread[t], &status); if (rc) { printf("ERROR; return code from pthread_join() is %d\n", rc); exit(-1); } printf("Main: completed join with thread %ld having a status of %ld\n",t,(long)status); } printf("Main: program completed. Exiting.\n"); pthread_exit(NULL); } Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 26 Lớp : K51CHTTT 2.2.7. Quản lý stack 2.2.7.1. Những thủ tục ƒ Pthread_attr_getstacksize(attr, stacksize) ƒ Pthread_attr_setstacksize(attr, stacksize) ƒ Pthread_attr_getstackaddr(attr, stackaddr) ƒ Pthread_attr_setstackaddr(attr, stackaddr) 2.2.7.2. Ngăn ngừa những vấn đề với stack Chuẩn POSIX không quy định kích thước stack của một thread. Điều này phụ thuộc và thực hiện khác nhau. Vượt giới hạn mặc định của stack rất dễ làm, với một kết quả bình thường: chương trình chấm dứt hoặc dữ liệu bị hỏng. Một chương trình an toàn và di động không phụ thuộc vào giới hạn mặc định của stack, nhưng thay vào đó, rõ ràng stack bố trí đủ cho mỗi thread bằng cách sử dụng thủ tục pthread_attr_setstacksize. Các thủ tục pthread_attr_getstackaddr và pthread_attr_setstackaddr có thể được sử dụng bởi những ứng dụng trong một môi trường mà ở đó stack cho mỗi thread phải đặt ở một vài vùng cụ thể của bộ nhớ. 2.3. Biến Mutex 2.3.1. Khái niệm mutex Mutex là viết tắt của “mutual exclusion”. Biến mutex là một trong những phương tiện chính để thực hiện việc đồng bộ thread và cho việc bảo vệ việc chia sẻ dữ liệu khi xảy ra nhiều lời viết. Một biến mutex hoạt động như một “khóa” bảo vệ quyền truy cập vào một nguồn dữ liệu được chia sẻ. Khái niệm cơ bản của một mutex được sử dụng trong Pthread là chỉ có một thread có thể khóa (hoặc sở hữu) một biến mutex tại bất kỳ thời điểm nào. Vì vậy, ngay cả khi nếu một vài thread cố khóa một mutex thì chỉ một thread sẽ thành công. Không có thread khác có thể sở hữu mutex đó cho tới khi thread sở hữu mở khóa mutex đó. Những thread phải thay phiên nhau tuy cập dữ liệu được bảo vệ. Mutex có thể được sử dụng để ngăn chặn điều kiện tương tranh. Một ví dụ về điều kiện tương tranh liên quan đến một giao dịch ngân hàng được chỉ ra dưới đây: Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 27 Lớp : K51CHTTT Trong ví dụ trên, một mutex nên được sử dụng để khóa “balance” trong khi một thread đang sử dụng nguồn dữ liệu được chia sẻ này. Rất thường xuyên các hành động được thực hiện bởi một thread sở hữu một mutex là cập nhật các biến toàn cục. Đây là một cách an toàn để đảm bảo rằng khi một vài thread cập nhật cùng biến này, giá trị cuối cùng là giống như những gì nó sẽ được nếu chỉ có một thread thực hiện cập nhật. Các biến đang được cập nhật thuộc về “critical section”. Một trình tự thông thường trong việc sử dụng một mutex là như sau: [1] Tạo ra và khởi tạo một biến mutex. [2] Một vài thread thử khóa mutex. [3] Chỉ một thread thành công và thread đó sỡ hữu mutex. [4] Thread sở hữu thực hiện một vài tập các hành động. [5] Thread sở hữu mở khóa mutex. [6] Một thread khác giành được mutex và lặp lại quá trình trên. [7] Cuối cùng mutex bị phá hủy. Khi bảo vệ dữ liệu được chia sẻ, đó là trách nhiệm của người lập trình để đảm bảo mọi thread có nhu cầu sử dụng một mutex. Ví dụ, nếu bốn thread đang được cập nhật cùng dữ liệu, nhưng chỉ có một sử dụng mutex, dữ liệu vẫn có thể bị hỏng. 2.3.2. Tạo ra và phá hủy mutex 2.3.2.1. Những thủ tục ƒ Pthread_mutex_init(mutex, attr) ƒ Pthread_mutex_destroy(mutex) Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 28 Lớp : K51CHTTT ƒ Pthead_mutexattr_init (attr) ƒ Pthread_mutexattr_destroy(attr) 2.3.2.2. Cách sử dụng Biến mutex phải được khia bảo với kiểu pthread_mutex_t và phải được khởi tạo trước khi nó được sử dụng. Có hai cách để khởi tạo một biến mutex: ƒ Theo cách tĩnh, khi nó được khai báo. Ví dụ: Pthread_mutex_t mymutex = PTHREAD_MUTEX_INITIALIZE. ƒ Theo cách động, với thủ tục pthread_mutex_init(). Phương thức này cho phép thiết lập đối tượng thuộc tính mutex, attr. Đối tương attr được sử dụng để thiết lập thuộc tính cho đối tượng mutex và phải là kiểu pthead_mutexattr_t nếu được sử dụng (có thế để là NULL nếu thiết lập mặc định). Chuẩn Pthread định nghĩa 3 thuộc tính tùy chọn cho mutex: ƒ Protocol: Chỉ định giao thức được sử dụng để ngăn chặn sự đảo lộn ưu tiên cho một mutex. ƒ Prioceiling: chỉ định trần ưu tiên của một mutex. ƒ Process-shared: chỉ định quá trình chia sẻ một mutex. Chú ý rằng không phải tất cả các thực hiện có thể cung cấp ba thuộc tính mutex tùy chọn. Các thủ tục pthead_mutexattr_init() và pthread_mutexattr_destroy() được dùng để tạo ra và phá hủy đối tượng thuộc tính mutex tương ứng. Pthead_mutexattr_destroy() nên được dùng để giải phóng đối tượng mutex khi nó không còn cần thiết. 2.3.3. Khóa và mở khóa mutex 2.3.3.1. Các thủ tục ƒ Pthread_mutex_lock(mutex) ƒ Pthead_mutex_trylock(mutex) ƒ Pthead_mutex_unlock(mutex) 2.3.3.2. Cách sử dụng Thủ tục pthread_mutex_lock() được sử dụng bởi một thread để thu được một khóa trên một biến mutex xác định. Nếu biến mutex đã được khóa bởi một thread khác, lời gọi này sẽ chặn lời gọi thread cho tới khi mutex được mở khóa. Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 29 Lớp : K51CHTTT Thủ tục pthread_mutex_trylock() sẽ cố thử khóa một mutex. Tuy nhiên, nếu mutex đã được khóa, thủ tục này sẽ ngay lập tức trả về lỗi code “busy”. Thủ tục này có thể có ích trong việc ngăn ngừa điều kiện bế tắc, như trong hoàn cảnh ưu tiên đảo ngược ( priority-inversion ). Thủ tục pthread_mutex_unlock() sẽ mở khóa một mutex nếu được gọi bởi thread đang sở hữu mutex đó. Việc gọi thủ tục này được yêu cầu sau khi một thread hoàn thành việc sử dụng dữ liệu được bảo vệ nếu thread khác giành được mutex cho công việc của chúng với dữ liệu được bảo vệ. Một lỗi sẽ được trả về nếu: ƒ Mutex này đã được mở khóa. ƒ Mutex được sở hữu bởi thread khác. Không có gì gọi là “ma thuật” về mutexes… trong thực tế, chúng na ná như một “thỏa thuận của quý ông (gentlement’s agreement)” giữa các thread tham gia. Đây là thiết lập của người viết chương trình để đảm bảo rằng những thread cần thiết làm cho các mutex khóa và mở khóa một cách chính xác. Kịch bản sau đây thể hiện một lỗi logic: Ví dụ sau đây minh họa cho cách sử dụng một biến mutex trong một chương trình thread . Dữ liệu chính luôn sẵn sàng cho tất cả các thread thông qua một biến struct toàn cục. Mỗi thread làm việc trên một phần dữ liệu khác nhau. Thread chính đợi cho đến khi tất cả các thread khác hoàn thành xong việc tính toán của chúng, và sau đó in kết quả tổng: ********************************************************************* #include #include #include /* The following structure contains the necessary information Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 30 Lớp : K51CHTTT to allow the function "dotprod" to access its input data and place its output into the structure. */ typedef struct { double *a; double *b; double sum; int veclen; } DOTDATA; /* Define globally accessible variables and a mutex */ #define NUMTHRDS 4 #define VECLEN 100 DOTDATA dotstr; pthread_t callThd[NUMTHRDS]; pthread_mutex_t mutexsum; /* The function dotprod is activated when the thread is created. All input to this routine is obtained from a structure of type DOTDATA and all output from this function is written into this structure. The benefit of this approach is apparent for the multi-threaded program: when a thread is created we pass a single argument to the activated function - typically this argument is a thread number. All the other information required by the function is accessed from the globally accessible structure. */ void *dotprod(void *arg) { /* Define and use local variables for convenience */ Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 31 Lớp : K51CHTTT int i, start, end, len ; long offset; double mysum, *x, *y; offset = (long)arg; len = dotstr.veclen; start = offset*len; end = start + len; x = dotstr.a; y = dotstr.b; /* Perform the dot product and assign result to the appropriate variable in the structure. */ mysum = 0; for (i=start; i<end ; i++) { mysum += (x[i] * y[i]); } /* Lock a mutex prior to updating the value in the shared structure, and unlock it upon updating. */ pthread_mutex_lock (&mutexsum); dotstr.sum += mysum; pthread_mutex_unlock (&mutexsum); pthread_exit((void*) 0); } /* The main program creates threads which do all the work and then Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 32 Lớp : K51CHTTT print out result upon completion. Before creating the threads, the input data is created. Since all threads update a shared structure, we need a mutex for mutual exclusion. The main thread needs to wait for all threads to complete, it waits for each one of the threads. We specify a thread attribute value that allow the main thread to join with the threads it creates. Note also that we free up handles when they are no longer needed. */ int main (int argc, char *argv[]) { long i; double *a, *b; void *status; pthread_attr_t attr; /* Assign storage and initialize values */ a = (double*) malloc (NUMTHRDS*VECLEN*sizeof(double)); b = (double*) malloc (NUMTHRDS*VECLEN*sizeof(double)); for (i=0; i<VECLEN*NUMTHRDS; i++) { a[i]=1.0; b[i]=a[i]; } dotstr.veclen = VECLEN; dotstr.a = a; dotstr.b = b; dotstr.sum=0; pthread_mutex_init(&mutexsum, NULL); /* Create threads to perform the dotproduct */ pthread_attr_init(&attr); Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 33 Lớp : K51CHTTT pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE); for(i=0; i<NUMTHRDS; i++) { /* Each thread works on a different set of data. The offset is specified by 'i'. The size of the data for each thread is indicated by VECLEN. */ pthread_create(&callThd[i], &attr, dotprod, (void *)i); } pthread_attr_destroy(&attr); /* Wait on the other threads */ for(i=0; i<NUMTHRDS; i++) { pthread_join(callThd[i], &status); } /* After joining, print out the results and cleanup */ printf ("Sum = %f \n", dotstr.sum); free (a); free (b); pthread_mutex_destroy(&mutexsum); pthread_exit(NULL); } 2.4. Biến điều kiện 2.4.1. Khái niệm về biến điều kiện Biến điều kiện cung cấp một cách nữa cho thread để đồng bộ hóa. Trong khi mutexes thể hiện sự đồng bộ bằng cách điều khiển thread truy cập tới dữ liệu thì biến điều kiện cho phép thread đồng bộ dựa trên giá trị thực của dữ liệu. Nếu không có biến điều kiện, người lập trình sẽ cần phải có thread polling một cách liên tục (có Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 34 Lớp : K51CHTTT thể trong một phần quan trọng), để kiểm tra xem nếu điều kiện được đáp ứng. Điều này có thể rất tốn tài nguyên kể từ khi thead bận rộn liên tục trong hoạt động này. Một biến điều kiện là một cách để đạt được cùng một mục tiêu mà không cần polling. Một biến điều kiện sẽ luôn được sử dụng cùng với một khóa mutex. Một chuỗi đại diện cho việc sử dụng các biến điều kiện được hiển thị trong bảng sau: Thread chính: - Khai báo và khởi tạo dữ liệu/biến toàn cục cần đồng bộ hóa (ví dụ “count”). - Khai bảo và khởi tạo biến điều kiện. - Khai bảo và khởi tạo mutex liên quan. - Tạo thread A và B để làm việc Thread A - Làm việc tới khi một điều kiện nhất định phải xảy ra.(ví dụ khi biến count đạt được một giá trị cụ thể nào đấy) - Khóa mutex liên quan và kiểm tra giá trị của biến toàn cục. - Gọi thủ tục pthead_cond_wait() để thực hiện việc ngăn chặn đợi tín hiệu từ thread B. Chú ý rằng, một lời gọi tới hàm pthead_cond_wait() sẽ tự động mở khóa cho mutex liên quan để nó có thể được sử dụng bởi thread B. - Khi đã nhận được tín hiệu,thread A sẽ “wake up”. Mutex sẽ tự động bị khóa. - Mở khóa mutex. Thread B - Làm việc - Khóa mutex liên quan. - Thay đổi giá trị của biến toàn cụng để thread A chờ. - Kiểm tra giá trị của biến toàn cục mà thread A chờ. Nếu nó thỏa mãn điều kiện mong muốn, tín hiệu cho thread A. - Mở khóa mutex. - Tiếp tục Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 35 Lớp : K51CHTTT - Tiếp tục. Thread chính: - Nối / Tiếp tục 2.4.2. Tạo ra và phá hủy 1 biến điều kiện 2.4.2.1. Các thủ tục ƒ Pthread_cond_init (condition, attr) ƒ Pthread_cond_destroy(condition) ƒ Pthead_condattr_init(attr) ƒ Pthread_condattr_destroy(attr) 2.4.2.2. Cách sử dụng Biến điều kiện phải được khai báo với kiểu pthread_cond_t, và phải được khởi tạo trước khi chúng được sử dụng. Có hai cách để khởi tạo biến điều kiện: ƒ Theo cách tĩnh, khi chúng được khai báo: pthread_cond_t myconvar = PTHREAD_COND_INITIALIZER; ƒ Theo cách động, với thủ tục pthread_cond_init. ID của biến điều kiện được tao ra được trả về với lời gọi thread thông qua tham số condition. Phương thức này cho phép thiết lập thuộc tính cho biến điều kiện, attr. Đối tượng tùy chọn attr được sử dụng để thiết lập thuộc tính cho biến điều kiện. Chỉ có một thuộc tính được định nghĩa cho biến điều kiện là process-shared, cho phép biến điều kiện được nhìn bởi các thread trong tiến trình khác. Đối tượng thuộc tính, nếu được sử dụng, phải có kiểu pthread_condattr_t (để là NULL nếu chấp nhận thuộc tính mặc định). Chú ý rằng không phải tất cả các thể hiện đểu có thể cung cấp thuộc tính này. Các thủ tục pthead_condattr_init() và pthread_condattr_destroy() được sử dụng để tạo ra và phá hủy đối tượng thuộc tính của biến điều kiện. Thủ tục pthread_cond_destroy() nên được sử dụng để giải phóng biến điều kiện nếu nó không còn cần thiết nữa. 2.4.3. Waiting và signaling trên biến điều kiện Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 36 Lớp : K51CHTTT 2.4.3.1. Các thủ tục ƒ Pthread_cond_wait (condition, mutex) ƒ Pthread_cond_signal(condition) ƒ Pthread_cond_broadcast(condition) 2.4.3.2. Cách sử dụng Thủ tục pthread_cond_wait() ngăn chắn lời gọi thread cho tới khi điểu kiện (condition) xác định được báo hiệu. Thủ tục này nên được gọi trong khi mutex bị khóa và nó sẽ tự động mở khóa mutex trong khi chờ đợi. Sau khi tín hiệu nhận được và thread tiếp tục, mutex sẽ tự động bị khóa để sử dụng bởi thread. Người lập trình sau đó chịu trách nhiệm mở khóa khi thread hoàn thành với nó. Thủ tục pthead_cond_singal() được dùng để báo hiệu (hoặc đánh thức) thread khác đang đợi trên biến điều kiện. Nó nên được gọi sau khi biến mutex bị khóa, và phải mởi khóa mutex theo thứ tự cho thủ tục pthread_cond_wait() được hoàn thành. Thủ tục pthread_cond_broadcast() nên được sử dụng thay vì pthread_cond_signal () nếu có nhiều hơn một thread đang ở trong trạng thái chờ. Sẽ có một lỗi logic nêu gọi pthread_cond_signal trước khi gọi pthread_cond_wait(). Ví dụ đơn giản để làm rõ cách sử dụng của một vài biến điều kiện Pthread. Trong hàm main() tạo ra ba thread. Hai trong số đó thực hiện việc và cập nhật biến. Thread thứ ba đợi cho đến khi biến count nhận được giá trị xác định. #include #include #include #define NUM_THREADS 3 #define TCOUNT 10 #define COUNT_LIMIT 12 int count = 0; int thread_ids[3] = {0,1,2}; pthread_mutex_t count_mutex; Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 37 Lớp : K51CHTTT pthread_cond_t count_threshold_cv; void *inc_count(void *t) { int i; long my_id = (long)t; for (i=0; i<TCOUNT; i++) { pthread_mutex_lock(&count_mutex); count++; /* Check the value of count and signal waiting thread when condition is reached. Note that this occurs while mutex is locked. */ if (count == COUNT_LIMIT) { pthread_cond_signal(&count_threshold_cv); printf("inc_count(): thread %ld, count = %d Threshold reached.\n", my_id, count); } printf("inc_count(): thread %ld, count = %d, unlocking mutex\n", my_id, count); pthread_mutex_unlock(&count_mutex); /* Do some "work" so threads can alternate on mutex lock */ sleep(1); } pthread_exit(NULL); } void *watch_count(void *t) { long my_id = (long)t; printf("Starting watch_count(): thread %ld\n", my_id); /* Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 38 Lớp : K51CHTTT Lock mutex and wait for signal. Note that the pthread_cond_wait routine will automatically and atomically unlock mutex while it waits. Also, note that if COUNT_LIMIT is reached before this routine is run by the waiting thread, the loop will be skipped to prevent pthread_cond_wait from never returning. */ pthread_mutex_lock(&count_mutex); if (count<COUNT_LIMIT) { pthread_cond_wait(&count_threshold_cv, &count_mutex); printf("watch_count(): thread %ld Condition signal received.\n", my_id); count += 125; printf("watch_count(): thread %ld count now = %d.\n", my_id, count); } pthread_mutex_unlock(&count_mutex); pthread_exit(NULL); } int main (int argc, char *argv[]) { int i, rc; long t1=1, t2=2, t3=3; pthread_t threads[3]; pthread_attr_t attr; /* Initialize mutex and condition variable objects */ pthread_mutex_init(&count_mutex, NULL); pthread_cond_init (&count_threshold_cv, NULL); /* For portability, explicitly create threads in a joinable state */ pthread_attr_init(&attr); pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE); pthread_create(&threads[0], &attr, watch_count, (void *)t1); Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 39 Lớp : K51CHTTT pthread_create(&threads[1], &attr, inc_count, (void *)t2); pthread_create(&threads[2], &attr, inc_count, (void *)t3); /* Wait for all threads to complete */ for (i=0; i<NUM_THREADS; i++) { pthread_join(threads[i], NULL); } printf ("Main(): Waited on %d threads. Done.\n", NUM_THREADS); /* Clean up and exit */ pthread_attr_destroy(&attr); pthread_mutex_destroy(&count_mutex); pthread_cond_destroy(&count_threshold_cv); pthread_exit(NULL); } 2.5. Dữ liệu riêng của Thread(Thread – specific data) 2.5.1. Khái niệm dữ liệu riêng của thread Trong cơ chế dữ liệu thread cụ thể, chúng ta có khái niệm về các khóa và giá trị. Mỗi khóa có một tên, và trỏ tới một vài vùng nhớ. Những khóa với cùng tên trong hai thread đồng thời luôn luôn trỏ tới những vùng nhớ khác nhau, điều này được quản lý bởi thư viện các hàm để bố trí các khối bộ nhớ để truy cập thông qua các khóa này. Chúng ta có một hàm để tạo ra khóa (được gọi một lần mỗi tên khóa trong toàn bộ quá trình), một hàm để cấp phát bộ nhớ (được gọi đồng thời trong mỗi thread), các hàm để ngừng cấp phát bộ nhớ cho các thread cụ thể và một hàm để phá hủy khóa. Chúng ta cũng có những hàm để truy cập tới dữ liệu được trỏ bởi một khóa, cũng như thiết lập giá trị, hoặc trả về giá trị mà nó trỏ tới. 2.5.2. Cấp phát dữ liệu riêng của thread Hàm pthread_key_create() được dùng để cấp phát một khóa mới. Khóa này bây giờ sẽ trở nên có giá trị cho tất cả các thread trong tiến trình. Khi một khóa được tạo ra, giá trị mặc định là NULL. Sau đó trong mỗi thread có thể thay đổi giá trị như nó mong muốn. Sau đây là cách sử dụng của hàm này: Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 40 Lớp : K51CHTTT /* rc được dùng để lưu giá trị trả về của hàm pthread_key_create() */ int rc; /* định nghĩa 1 biến để nắm giữ khóa, tạo ra 1 lần */ pthread_key_t list_key; /* cleanup_list là một hàm có thể làm sạch dữ liệu */ extern void* cleanup_list(void*); /* Tạo ra khóa */ rc = pthread_key_create(&list_key, cleanup_list); Chú ý sau khi hàm pthread_key_create() trả về, biến list_key sẽ trỏ tới cái khóa vừa mới được tạo ra. Con trỏ hàm trong tham số thứ hai của hàm pthread_key_create() sẽ tự động được gọi bởi thư viện Pthread khi thoát ra khỏi thread, với một con trỏ trỏ đến giá trị của khóa như là một tham số. Chúng ta cũng có thể dùng con trỏ NULL và khi đó sẽ không có hàm nào được trả về cho khóa. Chú ý rằng, các hàm được gọi một lần trong mỗi thread, kể cả khi chúng ta tạo ra khóa này chỉ một lần, trong một thread. Nếu chúng ta tạo ra vài khóa, hàm destructor liên quan sẽ được gọi theo một trật tự tùy ý, bất kể thứ tự của các khóa tạo ra. Nếu hàm pthread_key_create() thành công, nó sẽ trả về giá trị 0. Ngược lại, nó sẽ trả về vài dòng lỗi. Có một giới hạn PTHREAD_KEYS_MAX() có thể tồn tại trong quá trình tại bất kỳ thời điểm nào. Mọi cố gắng để tạo ra khóa sau khi thoát PTHREAD_KEYS_MAX sẽ gặp phải một giá trị trả về là EAGAIN từ hàm pthread_key_create(). 2.5.3. Truy cập vào dữ liệu riêng của thread Sau khi tạo ra một khóa, chúng ta có thể truy cập vào giá trị của chúng bằng cách sử dụng hai hàm: pthread_getspecific() và pthread_setspecific() . Hàm đầu tiên được dùng để lấy giá trị của một khóa được đưa ra còn hàm sau được dùng để thiết lập giá trị của khóa được đưa ra. Giá trị của một khóa chỉ là một con trỏ kiểu void (void*), do đó chúng ta có thể lưu bất cứ thứ gì chúng ta muốn. Hãy xem cách sử Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 41 Lớp : K51CHTTT dụng của những hàm này. Giả sử rằng ‘a_key’ là một biến khởi tạo kiểu pthread_key_t để chứa khóa được tạo ra trước: /* biến này được sử dụng để lưu giá trị trả về của hàm */ int rc; /* định nghĩa một biến mà chúng ta sẽ lưu vào đó một vài dữ liệu, ví dụ là 1 số nguyên */ int* p_num = (int*)malloc(sizeof(int)); if (!p_num) { fprintf(stderr, "malloc: out of memory\n"; exit(1); } /* khởi tạo giá trị */ (*p_num) = 4; /* bây giờ lưu giá trị này vào khóa */ /* chú ý rằng chúng ta không lưu ‘p_num’ vào khóa */ /* chúng ta chỉ lưu giá trị mà p_num trỏ tới */ rc = pthread_setspecific(a_key, (void*)p_num); . /* lấy giá trị của khóa a_key và in ra */ { int* p_keyval = (int*)pthread_getspecific(a_key); if (p_keyval != NULL) { Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 42 Lớp : K51CHTTT printf("value of 'a_key' is: %d\n", *p_keyval); } } Chú ý rằng, nếu chúng ta thiết lập giá trị cho khóa trong một thread, và cố thử lấy giá trị trong thread khác, chúng ta sẽ nhận được giá trị NULL, giá trị này là khác biệt cho mỗi thread. Cũng có hai trường hợp mà hàm pthread_getspecific() trả về NULL: - Khóa được cung cấp như tham số không hợp lệ ( ví dụ như khóa chưa được tạo). - Giá trị của khóa là NULL. Điều này có thể là nó chưa được khởi tạo, hoặc được đặt là NULL bởi lời gọi pthread_setspecific() trước. 2.5.4. Xóa dữ liệu trong thread Hàm pthread_key_delete() có thể được dùng để xóa khóa. Nhưng không được nhầm lẫn với tên của hàm này: nó không xóa được vùng nhớ liên quan tới khóa, cũng không gọi hàm hủy được định nghĩa trong khi khóa được tạo ra. Vì vậy, vẫn cần giải phóng vùng nhớ nếu cần thiết. Sử dụng hàm này rất đơn giản. Giải sử list_key là một biến kiểu pthread_key_t trỏ tới một khóa đã được tạo, sử dụng hàm này như sau: Int rc = pthread_key_delete(key); Hàm này sẽ trả về 0 nếu thành công, hoặc EINVAL nếu có lỗi. Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 43 Lớp : K51CHTTT CHƯƠNG 3: BÀI TOÁN CLOSEST_PAIR TRONG KHÔNG GIAN HAI CHIỀU SỬ DỤNG MULTITHREADING 3.1. Giới thiệu bài toán Cho trước N điểm trong hệ tọa độ Đề-các hai chiều. Tìm cặp điểm gần nhau nhất trong N điểm nói trên. (Trong khóa luận này, tôi mới chỉ ra được khoảng cách ngắn nhất giữa hai điểm trong N điểm trên nhưng chưa chỉ ra được cặp điểm đó). Để giải quyết bài toán này, có 2 thuật toán được đưa ra. Thuật toán thứ nhất, đó là ta đi duyệt tất cả các cặp điểm trong N điểm trên, so sanh khoảng cách rồi chọn ra hai điểm gần nhau nhất. Thuật toán này khá đơn giản, nhưng có độ phức tạp lớn: O(n2). Thuật toán thứ hai, còn được gọi là thuật toán chia để trị. Ý tưởng của thuật toán này là, ta chia N điểm cho trước thành hai nửa, trái và phải, với số điểm tương đương nhau rồi ta tính toán đệ qui khoảng cách ngắn nhất trên mỗi nửa đó. So với thuật toán thứ nhất, thuật toán này có độ phức tạp nhỏ hơn rất nhiểu: O(nlogn). Cùng với cách cài đặt hai thuật toán trên, trong khóa luận tốt nghiệp này tôi đã cài đặt song song hóa thuật toán thứ hai để làm tăng hiệu năng tính toán. Cách song song hóa thuật toán là, sau khi chia tập N điểm thành hai phần trái và phải, tôi tạo một thread để tính toán nửa bên trái, như vậy, cùng với thread chính(của hàm main()), sẽ có một thread tính toán nửa bên trái chạy song song cùng với nó. Điều này làm tăng đáng kể hiệu năng tính toán của chương trình. Cụ thể các cách cài đặt được nêu rõ ở phần tiếp theo. 3.2. Các thuật toán khác nhau để giải bài toán tìm khoảng cách ngắn nhất giữa các cặp điểm trong N điểm cho trước. - Thuật toán 1: ta duyệt tất cả các cặp điểm trong N điểm cho trước, so sánh khoảng cách giữa các cặp điểm đó rồi chọn ra khoảng cách ngắn nhất. Thuật toán này có độ phức tạp tính toán O(n2). Mã lệnh thực hiện thuật toán: #include #include #include #define N 8000 struct coordinate{ float x; float y; }; Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 44 Lớp : K51CHTTT /*--------------------------------------------------------- --------------------- Ham tinh khoang cach giua 2 diem ----------------------------------------------------------- -------------------*/ float distance(struct coordinate point1, struct coordinate point2){ float temp1, temp2; temp1 = point2.x - point1.x; temp2 = point2.y - point1.y; return sqrt(temp1*temp1 + temp2*temp2); }; /*--------------------------------------------------------- --------------------- Ham tim gia tri nho nhat ----------------------------------------------------------- -------------------*/ float min(float a, float b) { if (a < b) return a; else return b; }; /*--------------------------------------------------------- --------------------- Ham truyen gia tri cho cac diem ----------------------------------------------------------- -------------------*/ void input(struct coordinate point[]) { int i = 0; float temp1,temp2; FILE *fp; if((fp=fopen("input.txt","r")) == NULL) { printf("Cannot open file.\n"); } while(fscanf(fp, "%f %f", &point[i].x, &point[i].y) != eof()) i++; }; /*--------------------------------------------------------- -------------------- Ham chinh ----------------------------------------------------------- -------------------*/ int main() { int i,j; float result,temp; struct coordinate point[N],point2[2]; input(point); result = distance(point[0],point[1]); point2[0] = point[0]; point2[1] = point[1]; for(i = 0; i < N; i++) for(j = i + 1; j < N; j++) { Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 45 Lớp : K51CHTTT temp = distance(point[i],point[j]); if(temp < result){ point2[0] = point[i]; point2[1] = point[j]; result = temp; } } printf("Ket qua la :%2.2f",result); printf("\nCap diem la: (%2.2f,%2.2f) va (%2.2f,%2.2f)", point2[0].x,point2[0].y,point2[1].x, point2[1].y); } - Thuật toán 2: ta thực hiện bài toán theo phương pháp chia để trị. ƒ Bước 1: Sắp xếp tăng dần tập N điểm cho trước theo tọa độ x. Ở đây tác giả khóa luận sử dụng thuật toán quicksort để sắp xếp. ƒ Bước 2: Gọi tập N điểm cho trước là tập S. Ta chia S thành hai tập con S1 và S2 (S1 gọi là nửa trái, S2 gọi là nửa phải) sao cho số điểm trong mỗi tập là tương đương nhau bằng đường thẳng L. Đường thẳng L được xác định bằng phương trình x = x_mid, với x_mid là tọa độ điểm chính giữa trong tập S. ƒ Bước 3: Thực hiện tính toán đệ qui closest_pair đối với hai nửa trái và phải. Giả sử tìm được khoảng cách ngắn nhất ở nửa trái là dL và ở nửa phải là dR. ƒ Bước 4: Tìm khoảng cách ngắn nhất delta giữa hai cặp điểm mà trong đó một điểm nằm bên trái đường thẳng L và một điểm nằm bên phải đường thằng L. Phần này là phần khó nhất trong bài toán. Giả sử ∂ = min(dL,dR). Ta chọn tất cả những điểm ở S1 và S2 mà khoảng cách từ điểm đó tới đường thẳng L nhỏ hơn hoặc bằng ∂. Ta lưu những điểm thỏa mãn điều kiện đó trong tập S1 vào mảng tempL[], trong tập S2 vào mảng tempR[]. Bây giờ ta đi tìm khoảng cách ngắn nhất giữa 2 điểm, với điều kiện trong 2 điểm này, 1 điểm thuộc tempL[] và 1 điểm thuộc tempR[]. Cách thực hiện là, với mỗi điểm p thuộc tempL[], ta chỉ xét những điểm ở tempR[] nằm trong hình chữ nhật có kích thước (∂,2*∂) với p là điểm góc trên trái của hình chữ nhật. Ta có thể chỉ ra rằng nhiều nhất là có 6 điểm thuộc tempR[] thỏa mãn điều kiện này. ƒ Kết quả cuối cùng là giá trị nhỏ nhất của dL,dR và delta. Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 46 Lớp : K51CHTTT Khi thực hiện cài đặt bằng phương pháp này, độ phức tạp tính toán của thuật toán là O(nlogn). Mã lệnh thực hiện thuật toán: #include #include #include #include #include #include #define N 8000 /*--------------------------------------- Struct luu toa do (x,y) cua 1 diem ---------------------------------------*/ struct coordinate{ float x; float y; }; /*--------------------------------------- Struct luu tham so truyen vao cho ham closest_pair ---------------------------------------*/ struct thamso{ int left ; int right ; struct coordinate point[N]; }; /*--------------------------------------- Ham truyen gia tri cho cac diem ---------------------------------------*/ void input(struct coordinate point[]) { int i = 0; char s[81]; FILE *fp; fp = fopen("input.txt","r"); if(fp == NULL) { printf("Cannot open file.\n"); } while(fgets(s,80,fp)!= NULL) { sscanf(s,"%f %f" ,&point[i].x,&point[i].y); i++; } }; /*--------------------------------------Ham lay thoi gian hien thoi toi mili giay ---------------------------------------*/         Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 47 Lớp : K51CHTTT double gettime() { struct timeval x; gettimeofday(&x, NULL); double t = (double)(x.tv_sec + x.tv_usec / 1000000.0); return (t); }; /*--------------------------------------- Ham tinh khoang cach giua 2 diem --------------------------------------*/ float distance(struct coordinate point1, struct coordinate point2){ float temp1,temp2; temp1 = point2.x - point1.x; temp2 = point2.y - point1.y; return sqrt(temp1*temp1 + temp2*temp2); }; /*--------------------------------------- Ham tinh min cua 2 gia tri --------------------------------------*/ float min(float a, float b) { if (a < b) return a; else return b; }; /*--------------------------------------- Ham sap xep cac diem tang dan theo toa do x --------------------------------------*/ void quicksortX(struct coordinate arr[], int low, int high) { int i = low; int j = high; float x = 0.0; float y = 0.0; float z = arr[(i + j) / 2].x; do { while(arr[i].x < z) i++; while(arr[j].x > z) j--; if(i <= j) { x = arr[i].x; y = arr[i].y; arr[i].x = arr[j].x; arr[i].y = arr[j].y; arr[j].x = x; arr[j].y = y; i++; j--; } } while(i <= j); if(low < j) quicksortX(arr, low, j); if(i < high) quicksortX(arr, i, high); };         Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 48 Lớp : K51CHTTT /*--------------------------------------- Ham sap xep cac diem tang dan theo toa do y --------------------------------------*/ void quicksortY(struct coordinate arr[], int low, int high) { int i = low; int j = high; float x = 0.0; float y = 0.0; float z = arr[(low + high) / 2].y; do { while(arr[i].y < z) i++; while(arr[j].y > z) j--; if(i <= j) { x = arr[i].x; y = arr[i].y; arr[i].x = arr[j].x; arr[i].y = arr[j].y; arr[j].x = x; arr[j].y = y; i++; j--; } } while(i <= j); if(low < j) quicksortY(arr, low, j); if(i < high) quicksortY(arr, i, high); }; /*-------------------------------------*/ void sortX(struct coordinate toado[], int n) { quicksortX(toado,0,n-1); }; /*---------------------------------*/ void sortY(struct coordinate toado[], int n) { quicksortY(toado,0,n-1); }; /*--------------------------------------- Tao 1 stack luu gia tri tra ve cua ham closest_pair Ham push() day 1 gia tri vao stack Ham pop() lay gia tri ra khi stack --------------------------------------*/ float stack[100]; int ip=-1; void push(float v) { ip++; stack[ip] = v; return; } float pop() {         Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 49 Lớp : K51CHTTT if (ip >= 0) { float v = stack[ip]; ip--; return v; } else { printf("error: ip = %d\n", ip); return -11; } } /*--------------------------------------- Ham tinh toan khoang cach ngan nhat --------------------------------------*/ void closest_pair(void* args) { struct thamso* temp = (struct thamso*) args; int i,j,mid, countL = 0,countR = 0,tempLeft,tempRight; float midX,dL,dR,temp1,delta; struct coordinate tempL[N],tempR[N]; tempLeft = temp->left; tempRight = temp->right; mid = (temp->left + temp- >right)/2.0; midX = temp->point[mid].x; if((temp->right - temp->left) == 1 ) { push(distance(temp- >point[temp->right],temp- >point[temp->left])); return; } //de qui ben trai,gan lai left =0, right = mid temp->left = tempLeft; temp->right = mid; closest_pair(temp); dL = pop(); //de qui ben phai,gan lai left = mid, right = N -1 temp->left = mid; temp->right = tempRight; closest_pair(temp); dR = pop(); delta = min(dL,dR); // Lay ra nhung phan tu nam trong khoang delta ben trai for(i = tempLeft; i < mid; i++) { if(abs(temp->point[i].x - midX) <= delta) { tempL[countL] = temp- >point[i]; countL ++;         Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 50 Lớp : K51CHTTT } } // Lay ra nhung phan tu nam trong khoang delta ben phai for (i = mid; i < tempRight; i++) { if(abs(temp->point[i].x - midX) <= delta) { tempR[countR] = temp- >point[i]; countR ++; } } // Sap xep nhung phan tu trong khoang delta theo toa do Y sortY(tempL,countL); sortY(tempR,countR); temp1 = delta; // Kiem tra xem trong khoang delta co ton tai cap diem nao co khoang cach nho hon delta hay khong for(i = 0; i < countL; i ++) { j = 0; while((j < countR) && (abs(tempR[j].y - tempL[i].y) <= 2*delta)) { j++; temp1 = min(temp1,distance(tempL[i], tempR[j])); } } delta = min(temp1,delta); push(delta); return ; }; /*--------------------------------------- Ham chinh --------------------------------------*/ int main(){ float result; double time1,time2; struct thamso temp; temp.left = 0; temp.right = N-1; input(&temp); time1 = gettime(); sortX(temp.point,N); closest_pair_top(&temp); result = pop(); time2 = gettime(); printf("Thoi gian chay: %lf\n",time2 - time1); printf("khoang cach ngan nhat la : %2.2f \n",result); return 0;         Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 51 Lớp : K51CHTTT } - Song song hóa thuật toán 2 sử dụng pthread để làm tăng hiệu năng tính toán. Cụ thể ở đây, thời gian thực hiện giảm đi khoảng một nửa so với thuật toán 2. Các vấn đề đặt ra khi cài đặt bài toán theo phương pháp này: ƒ Cách tạo thread và truyền tham số cho thread. Với hàm closest_pair để tính đệ qui, ta tạo một thread để tính toán đệ qui nửa bên trái chạy song song với thread chính. Ta tạo một struct thamso lưu các giá trị left,right và tập các điểm để truyền vào hàm closest_pair. ƒ Khi nào thì join các thread. Ta phải join thread trên trước khi lấy ra giá trị trả về của hàm closest_pair. Cụ thể ở đây, ta phải join thread trên trước khi lấy giá trị ra khỏi ngăn xếp. ƒ Điều kiện tương tranh. Ta phải tạo một biến mutex để tránh xảy ra điều kiện tương tranh, vì có thể hai thread cùng tác động tơi biến đếm trong stack. Cụ thể ở đây, ta phải khóa biến mutex ở đầu hàm push và pop và mở khóa ở cuối mỗi hàm. Mã lệnh của chương trình: #include #include #include #include #include #include #define N 8000 /*----------------------------------------------- Struct luu toa do (x,y) cua 1 diem -----------------------------------------------*/ struct coordinate{ float x; float y; }; /*----------------------------------------------- Struct luu tham so truyen vao cho ham closest_pair -----------------------------------------------*/ struct thamso{ int left ; int right ; struct coordinate point[N]; }; /*-----------------------------------------------         Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 52 Lớp : K51CHTTT Ham truyen gia tri cho cac diem -----------------------------------------------*/ void input(struct coordinate point[]) { int i = 0; char s[81]; FILE *fp; fp = fopen("input.txt","r"); if(fp == NULL) { printf("Cannot open file.\n"); } while(fgets(s,80,fp) != NULL) { sscanf(s,"%f %f",&point[i].x,&point[i].y); i++; } }; /*----------------------------------------------- Ham lay thoi gian hien thoi toi mili giay -----------------------------------------------*/ double gettime() { struct timeval x; gettimeofday(&x, NULL); double t = (double)(x.tv_sec + x.tv_usec / 1000000.0); return (t); }; /*----------------------------------------------- Ham tinh khoang cach giua 2 diem -----------------------------------------------*/ float distance(struct coordinate point1, struct coordinate point2){ float temp1,temp2; temp1 = point2.x - point1.x; temp2 = point2.y - point1.y; return sqrt(temp1*temp1 + temp2*temp2); }; /*----------------------------------------------- Ham tinh min cua 2 gia tri -----------------------------------------------*/ float min(float a, float b) { if (a < b) return a; else return b; }; /*----------------------------------------------- Ham sap xep cac diem tang dan theo toa do x -----------------------------------------------*/ void quicksortX(struct coordinate arr[], int low, int high) { int i = low; int j = high; float x = 0.0; float y = 0.0; float z = arr[(i + j) / 2].x; do { while(arr[i].x < z) i++; while(arr[j].x > z) j--; if(i <= j) {         Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 53 Lớp : K51CHTTT x = arr[i].x; y = arr[i].y; arr[i].x = arr[j].x; arr[i].y = arr[j].y; arr[j].x = x; arr[j].y = y; i++; j--; } } while(i <= j); if(low < j) quicksortX(arr, low, j); if(i < high) quicksortX(arr, i, high); }; /*----------------------------------------------- Ham sap xep cac diem tang dan theo toa do y -----------------------------------------------*/ void quicksortY(struct coordinate arr[], int low, int high) { int i = low; int j = high; float x = 0.0; float y = 0.0; float z = arr[(low + high) / 2].y; do { while(arr[i].y < z) i++; while(arr[j].y > z) j--; if(i <= j) { x = arr[i].x; y = arr[i].y; arr[i].x = arr[j].x; arr[i].y = arr[j].y; arr[j].x = x; arr[j].y = y; i++; j--; } } while(i <= j); if(low < j) quicksortY(arr, low, j); if(i < high) quicksortY(arr, i, high); }; /*----------------------------------------*/ void sortX(struct coordinate toado[], int n) { quicksortX(toado,0,n-1); }; /*---------------------------------------------*/ void sortY(struct coordinate toado[], int n) { quicksortY(toado,0,n-1); }; /*----------------------------------------------- Tao 1 stack luu gia tri tra ve cua ham closest_pair Ham push() day 1 gia tri vao stack Ham pop() lay gia tri ra khi stack -----------------------------------------------*/ Float stack[100];         Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 54 Lớp : K51CHTTT Int ip=-1; pthread_mutex_t mutex; void push(float v) { pthread_mutex_lock(&mutex); /* Critical section: Lock */ ip++; stack[ip] = v; pthread_mutex_unlock(&mutex); /*Critical section: Unlock */ return; } float pop() { pthread_mutex_lock(&mutex); /* Critical section: Lock */ if (ip >= 0) { float v = stack[ip]; ip--; pthread_mutex_unlock(&mutex); /*Critical section: Unlock */ return v; } else { printf("error: ip = %d\n", ip); pthread_mutex_unlock(&mutex);/* Critical section: Unlock */ return -11; } } /*----------------------------------------------- Ham tinh toan khoang cach ngan nhat -----------------------------------------------*/ void closest_pair(void* args) { struct thamso* temp = (struct thamso*) args; int i,j,mid, countL = 0,countR = 0,tempLeft,tempRight; float midX,dL,dR,temp1,delta; struct coordinate tempL[N],tempR[N]; tempLeft = temp->left; tempRight = temp->right; mid = (temp->left + temp->right)/2.0; midX = temp->point[mid].x; if((temp->right - temp->left) == 1 ) { push(distance(temp->point[temp- >right],temp->point[temp->left])); return; } //de qui ben trai,gan lai left =0, right = mid temp->left = tempLeft; temp->right = mid; closest_pair(temp); dL = pop(); //de qui ben phai,gan lai left = mid, right = N - 1 temp->left = mid; temp->right = tempRight; closest_pair(temp); dR = pop(); // printf("dL = %f dR = %f\n", dL, dR); delta = min(dL,dR);         Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 55 Lớp : K51CHTTT // Chon nhung phan tu nam trong khoang delta ben trai for(i = tempLeft; i < mid; i++) { if(abs(temp->point[i].x - midX) <= delta) { tempL[countL] = temp->point[i]; countL ++; } // Chon nhung phan tu nam trong khoang delta ben phai for (i = mid; i < tempRight; i++) { if(abs(temp->point[i].x - midX) <= delta) { tempR[countR] = temp->point[i]; countR ++; } } // Sap xep nhung phan tu trong khoang delta theo toa do Y sortY(tempL,countL); sortY(tempR,countR); temp1 = delta; // Kiem tra xem trong khoang delta co ton tai cap diem nao // co khoang cach nho hon delta hay khong for(i = 0; i < countL; i ++) { j = 0; while((j < countR) && (abs(tempR[j].y - tempL[i].y) <= 2*delta)) { j++; temp1 = min(temp1,distance(tempL[i],tempR[j])); } } delta = min(temp1,delta); push(delta); return ; }; Int run_thread=1; void* closest_pair_top(void *args) { extern int run_thread; struct thamso *temp = (struct thamso *)args; int i,j,mid, countL = 0,countR = 0,tempLeft,tempRight,rc; float dL,dR,temp1,delta,midX; struct coordinate tempL[N],tempR[N]; pthread_t tid1=-2 , tid2=-2; tempLeft = temp->left; tempRight = temp->right; mid = (N - 1)/2; midX = temp->point[mid].x; //de qui ben trai,gan lai left =0, right = mid temp->left = 0; temp->right = (N - 1)/2; if (run_thread) { rc = pthread_create(&tid1,NULL,(void *) closest_pair,temp);         Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 56 Lớp : K51CHTTT printf("tid1 = %d\n", tid1); pthread_join(tid1,NULL); } else closest_pair(temp); //de qui ben phai,gan lai left = mid, right = N - 1 temp->left = (N - 1)/2; temp->right = N - 1; closest_pair(temp); dR = pop(); dL = pop(); delta = min(dL,dR); // Chon nhung phan tu nam trong khoang delta ben trai for(i = 0; i < (N - 1)/2; i++) { if(abs(temp->point[i].x - midX) <= delta) { tempL[countL] = temp->point[i]; countL ++; } } // Chon nhung phan tu nam trong khoang delta ben phai for (i = (N - 1) /2; i < N - 1; i++) { if(abs(temp->point[i].x - midX) <= delta) { tempR[countR] = temp->point[i]; countR ++; } } // Sap xep nhung phan tu trong khoang delta theo toa do Y sortY(tempL,countL); sortY(tempR,countR); temp1 = delta; // Kiem tra xem trong khoang delta co ton tai cap diem nao // co khoang cach nho hon delta hay khong for(i = 0; i < countL; i ++) { j = 0; while((j < countR) && (abs(tempR[j].y - tempL[i].y) <= 2*delta)) { j++; temp1 = min(temp1,distance(tempL[i],tempR[j])); } } delta = min(temp1,delta); push(delta); return NULL; }; /*----------------------------------------------- Ham chinh -----------------------------------------------*/ int main(){ float result; double time1,time2;         Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 57 Lớp : K51CHTTT struct thamso temp; /* Khoi tao bien mutex */ pthread_mutex_init(&mutex, NULL); /* Khoi tao gia tri left,right ban dau*/ temp.left = 0; temp.right = N-1; /*Truyen gia tri cho cac diem*/ input(&temp); time1 = gettime(); sortX(temp.point,N); closest_pair_top((void *)&temp); result = pop(); time2 = gettime(); printf("Thoi gian chay: %lf\n",time2 - time1); printf("khoang cach ngan nhat la : %2.2f \n",result); pthread_mutex_destroy(&mutex); return 0; } Dưới đây là biều đồ so sánh hiệu năng của 3 thuật toán với số các điểm lần lượt là 1000, 4000 và 8000 điểm. Thời gian được tính bằng giây. N  O(n2)  O(nlogn)  multi‐thread  1000  0.012  0.005  0.003  4000  0.081  0.015  0.007  8000  0.68  0.21  0.012  Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 58 Lớp : K51CHTTT 0.012 0.081 0.68 0.005 0.015 0.21 0.003 0.007 0.012 0.001 0.01 0.1 1 1000 4000 8000 O(n2) O(nlogn) multi- thread Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 59 Lớp : K51CHTTT KẾT LUẬN Trong khóa luận tốt nghiệp này, tôi đã tìm hiểu về thread, multithread và các lợi thế của thread và multithread so với tiến trình và đa tiến trình. Cùng với đó, tôi cũng tìm hiểu về lập trình posix thread trên hệ điều hành linux để nắm được cách tạo thread – pthread_create(), ngắt thread – pthread_exit(), đồng bộ hóa các thread sử dụng biến mutex. Ngoài ra, tôi cũng đồng thời cài đặt bài toàn closest_pair theo thuật toán chia để trị và quan trọng nhất, song song hóa thuật toán này để thấy được hiệu quả của việc sử dụng multi thread. Biều đồ so sánh trong chương ba đã chỉ rõ rằng, với số điểm cho trước ban đầu càng lớn, thì hiệu năng tính toán của việc sử dụng multi thread càng lớn so với việc không sử dụng multi thread. TÀI LIỆU THAM KHẢO [1] Clay Breshears , The Art of Concurrency: A Thread Monkey's Guide to Writing Parallel Applications, Nxb O’Reilly, 2009 [2] Mikhail J. Atallah and Marina Blanton. Algorithms and Theory of Computation Handbook. Nxb CRC press, 2009. [3] Multi-Threaded programming with posix thread. Địa chỉ: thread.html#thread_create_stop. [4] Multithreading. Địa chỉ: [5] Posix thread programming. Địa chỉ: https://computing.llnl.gov/tutorials/pthreads/. Khóa luận tốt nghiệp Nghiên cứu lập trình thread và ứng dụng Sinh viên: Cấn Việt Dũng 60 Lớp : K51CHTTT