Luận Văn Nghiên cứu lập trình thread và ứng dụng

LỜI CẢM ƠN

Lời đầu tiên tôi xin được gửi lời cảm ơn chân thành tới các thầy cô giáo Trường Đại
Học Công Nghệ - Đại Học Quốc Gia Hà Nội, đặc biệt là các thầy cô trong khoa Công
Nghệ Thông Tin, những người đã trực tiếp chỉ bảo tôi những kiến thức trong suốt bốn
năm học vừa qua trên ghế giảng đường.
Đặc biệt tôi xin được bày tỏ lòng kính trọng và biết ơn tới TS. Nguyễn Hải Châu
người đã trực tiếp hướng dẫn, giúp đỡ tôi hoàn thành khóa luận này.
Xin được gửi lời chúc sức khỏe và hạnh phúc tới tất cả các thầy cô. Xin chúc thầy cô
đạt được nhiều thành tựu hơn nữa trong sự nghiệp đào tạo tri thức cho đất nước cũng như
trong các công việc nghiên cứu khoa học.

Trân trọng cảm ơn!
Hà Nội, Ngày 20 Tháng 05 năm 2010
Sinh viên thực hiện
Cấn Việt Dũng



TÓM TẮT KHÓA LUẬN

Trong khóa luận này, tôi sẽ trình bày lý thuyết về Thread, lập trình posix thread
và cài đặt một bài toán sử dụng posix thread để thấy được hiệu quả của việc sử dụng
chúng. Phần đầu tiên,tôi giới thiêu lý thuyết về Thread, Multi thread và các vấn đề
liên quan. Tiếp theo, tôi trình bày về lập trình posix thread trên hệ điều hành linux,
bao gồm cách tạo, ngắt thread và đồng bộ các thread trong chương trình. Cuối cùng,
là cách cài đặt bài toán “tìm cặp điểm gần nhau nhất trong tập N điểm cho trước”( qui
ước bài toán này là bài toán closest_pair) sử dụng posix thread trên ngôn ngữ C để
thấy được sự hiệu quả của việc sử dụng multithread trong việc nâng cao hiệu năng
của chương trình, ở đây cụ thể là tốc độ tính toán tăng lên rõ rệt.




MỤC LỤC

CHƯƠNG 1: GIỚI THIỆU VỀ THREAD VÀ MULTI THREAD. 7
1.1. Tổng quan về thread 7
1.2. So sánh thread với tiến trình 7
1.3. Đa thread: những lợi thế 8
1.4. Tiến trình, thread nhân, thread người dùng, fiber 9
1.5. Vấn đề đưa ra của thread và fiber 10
1.5.1.Truy cập đồng thời và cấu trúc dữ liệu . 10
1.5.2.Vào/ ra và bộ lập lịch 11
1.6. Các mô hình .12
1.6.1. Mô hình 1:1 (thread cấp nhân) . 12
1.6.2. Mô hình N:1 (thread cấp người dùng) . 12
1.6.3. Mô hình N:M (thread tích hợp) . 12
1.7. Ngôn ngữ hỗ trợ .13

CHƯƠNG 2: POSIX THREAD PROGRAMMING .14
2.1. Tổng quan về Pthread 14
2.1.1. Khái niệm Pthread . 14
2.1.2. Tại sao lại sử dụng Pthread? . 14
2.1.3. Pthread API . 16
2.1.4. Biên dịch chương trình Threaded . 17
2.2. Quản lý Thread 18
2.2.1. Các thủ tục chính . 18
2.2.2. Tạo Thread 18
2.2.3. Thiết lập các thuộc tính cho Thread . 19
2.2.4. Hủy thread . 19
2.2.5. Truyền tham số cho Thread 21
2.2.6. Nối và tách Thread 22
2.2.6.1. Những thủ tục chính 23
2.2.6.2. Nối Thread .23
2.2.6.3. Có thể nối được hay không? 23
2.2.6.4. Tách (detaching) 24
2.2.7. Quản lý stack 26
2.2.7.1. Những thủ tục 26
2.2.7.2. Ngăn ngừa những vấn đề với stack .26
2.3. Biến Mutex 26
2.3.1. Khái niệm mutex . 26
2.3.2. Tạo ra và phá hủy mutex . 27
2.3.2.1. Những thủ tục 27
2.3.2.2. Cách sử dụng .28
2.3.3. Khóa và mở khóa mutex 28
2.3.3.1. Các thủ tục .28
2.3.3.2. Cách sử dụng .28
2.4. Biến điều kiện 33
2.4.1. Khái niệm về biến điều kiện . 33

2.4.2. Tạo ra và phá hủy 1 biến điều kiện 35
2.4.2.1. Các thủ tục .35
2.4.2.2. Cách sử dụng .35
2.4.3. Waiting và signaling trên biến điều kiện 35
2.4.3.1. Các thủ tục .36
2.4.3.2. Cách sử dụng .36
2.5. Dữ liệu riêng của Thread(Thread – specific data) .39
2.5.1. Khái niệm dữ liệu riêng của thread 39
2.5.2. Cấp phát dữ liệu riêng của thread . 39
2.5.3. Truy cập vào dữ liệu riêng của thread . 40
2.5.4.Xóa dữ liệu trong thread . 42

CHƯƠNG 3: BÀI TOÁN CLOSEST_PAIR TRONG KHÔNG GIAN HAI CHIỀU SỬ
DỤNG MULTITHREADING .43
3.1. Giới thiệu bài toán .43
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 .43





GIỚI THIỆU
Thread là một mô hình lập trình phổ biến cho phép nhiều thread đơn có thể
chạy trên cùng một tiến trình, và các thread này có thể chia sẻ tài nguyên của tiến
trình cũng như có thể tính toán độc lập. Và ứng dụng hữu ích nhất của mô hình này
là khi nó được áp dụng cho một tiến trình đơn lẻ để cho phép tính toán song song
trên một hệ thống đa xử lý. Trong khóa luận này, tôi sẽ trình bày mô hình này trên
chuẩn IEEE POSIX 1003.1c, được gọi là POSIX thread hay Pthread. Lý do tôi chọn
Pthread, là để nhận ra hiệu quả tiềm năng của chương trình, việc tạo ra một thread
sử dụng ít tài nguyên và chi phí của hệ điều hành hơn rất nhiều so với việc tạo ra
một tiến trình.
Nội dung chính của khóa luận bao gồm 3 chương, nội dung cụ thể như sau:
Chương I: Giới thiệu về thread và multi thread. Chương này tập trung giới thiệu
về thread và multi thread, so sánh giữa thread với tiến trình và cùng với đó là những
lợi thế khi sử dụng multi thread. Cuối cùng là các mô hình thread và các ngôn ngữ
hỗ trợ.
Chương II: Lập trình POSIX thread. Chương này sẽ đề cập tới các vấn đề cơ bản
trong lập trình POSIX thread (Pthread). Các vấn đề được đề cập bao gồm việc quản
lý thread, tạo, hủy, tách và nối thread. Các biến mutex, biến điều kiện và cách sử
dụng. Mỗi phần đều có những ví dụ minh họa.
Chương III: Bài toán closest_pair. Chương này tôi sẽ cài đặt bài toán closest_pair
hai chiều bằng các phương pháp thông thường, đệ qui và đệ qui sử dụng multi thread
để thấy được hiệu quả của việc sử dụng multi thread.