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