Khóa luận Nghiên cứu lập trình Thread và ứng dụng

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 1 Lớp : K51CHTTT 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 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 2 Lớp : K51CHTTT 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. 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 3 Lớp : K51CHTTT 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  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 4 Lớp : K51CHTTT 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  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 5 Lớp : K51CHTTT 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  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 6 Lớp : K51CHTTT 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. 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 7 Lớp : K51CHTTT CHƯƠNG 1: GIỚI THIỆU VỀ THREAD VÀ MULTI THREAD 1.1. Tổng quan về thread Trong khoa học máy tính, một chuỗi các tính toán kết quả từ một fork của một chương trình máy tính chia thành hai hoặc nhiều nhiệm vụ chạy đồng thời. Sự thể hiện của các thread và tiến trình (process) là khác nhau trong một hệ điều hành, nhưng trong hầu hết các trường hợp, một thread được nằm bên trong một tiến trình. Nhiều thread có thể tồn tại cùng trong một tiến trình và chia sẻ tài nguyên như bộ nhớ, trong khi những tiến trình khác nhau không thế chia sẻ tài nguyên. Trên một bộ xử lý đơn, multi thread thường xảy ra bởi sự phân chia thời gian ghép (như trong multitasking): bộ xử lý chuyển giữa những thread khác nhau. Ngữ cảnh chuyển thường xảy ra một cách thường xuyên đủ để người dùng nhận thấy được nhiều thread hoặc nhiệm vụ đang chạy tại cùng một thời điểm. Trên một bộ đa xử lý hoặc hệ thống nhiều nhân, những thread hoặc nhiệm vụ sẽ chạy cùng lúc, với mỗi một bộ xử lý hoặc nhân chạy một thread hoặc nhiệm vụ riêng. Nhiều hệ điều hành hiện đại hỗ trợ trực tiếp sự phân chia thời gian hoặc đa thread với một bộ lập lịch tiến trình. Nhân của hệ điều hành cho phép người lập trình tính toán thread bằng các giao diện lời gọi hệ thống. Một vài thể hiện được gọi là thread nhân, trong khi một tiến trình nhẹ (lightweight process) là một kiểu xác định của thread nhân để chia sẻ trạng thái và thông tin. Chương trình có thể có thread không gian người dùng khi lập trình thread với thời gian, tín hiệu hoặc những phương thức khác để làm gián đoạn thực hiện riêng của họ để thực hiện một sắp xếp ad-hoc hoặc chia thời gian. 1.2. So sánh thread với tiến trình Thread khác với tiến trình trong hệ điều hành đa nhiệm truyền thống ở các điểm sau: - Các tiến trình thường được độc lập, còn các thread thì tồn tại như là các tập con của một tiến trình. - Tiến trình có trạng thái thông tin đáng kể, trong khi nhiều thread trong một tiến trình chia sẽ trạng thái tiến trình cũng như bộ nhớ và các tài nguyên khá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 8 Lớp : K51CHTTT - Tiến trình có vùng địa chỉ riêng biệt, trong khi thread chia sẽ không gian địa chỉ của chúng. - Các tiến trình chỉ tương tác thông qua cơ chế liên tiến trình do hệ thống cung cấp. - Ngữ cảnh chuyển giữa các thread trong cùng một tiến trình thường sẽ nhanh hơn chuyển giữa các tiến trình. 1.3. Đa thread: những lợi thế Multi thread như là một mô hình lập trình phổ biến và cho phép thực hiện nhiều thread tồn tại trong một tiến trình đơn. Những thread này chia sẻ tài nguyên của tiến trình nhưng cũng có thể tính toán độc lập. Mô hình lập trình thread cung cấp cho người phát triển những sự hữu ích của việc tính toán đồng thời. Tuy nhiên, có lẽ ứng dụng thú vị nhât cho công nghệ 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ý. Lợi thế này của lập trình multi thread cho phép nó tính toán nhanh hơn trên hệ thống máy tính có nhiều CPU, CPU với nhiều nhân hoặc qua một cụm máy – bởi vì những thread của chương trình cho vay chính bản thân nó để thực hiện sự đồng thời. Trong trường hợp này, người lập trình cần phải cẩn thận để tránh lỗi chạy điều kiện (race condition), và những đối xử không thuộc trực giác. Để các dữ liệu được thao tác chính xác, những thread sẽ quy thời gian để xử lý dữ liệu theo thứ tự đúng. Thread có thể yêu cầu hoạt động độc quyền (thường được thực hiện bằng cách sử dụng semaphore) để ngăn chặn dữ liệu không bị đồng thời sửa đổi hoặc đọc trong khi quá trình đang bị sửa đổi. Một lợi thế khác của multi thread, kể cả đối với hệ thống đơn CPU, là có khả năng cho một ứng dụng vẫn đáp ứng được nhu cầu đầu vào. Trong một chương trình thread đơn, nếu khối thread tính toán chính trên một nhiệm vụ lớn, toàn bộ ứng dụng có thể xuất hiện để đóng băng. Bằng cách di chuyển nhiệm vụ lớn này tới một thread worker để chạy đồng thời với thread tính toán chính, nó có thể cho các ứng dụng đáp ứng đầu vào của người dùng trong khi vẫn thực hiện nhiệm vụ tính toán. Hệ điều hành sắp xếp các thread theo một trong hai cách sau: 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 9 Lớp : K51CHTTT - Chế độ lập lịch ưu tiên(preemptive) thường được coi là phương pháp tốt hơn, vì nó cho phép hệ điều hành xác định khi nào một chuyển trạng thái xảy ra. Sự bất lợi của phương pháp này là hệ điều hành có thể làm cho bối cảnh chuyển đổi tại một thời gian không thích hợp, gây đảo ngược ưu tiên hoặc các hiệu ứng tiêu cực nào khác mà có thể tránh bằng cooperative multithreading. - Cooperative multithreading, mặt khác,dựa vào bản thân các thread để từ bỏ kiểm soát sau khi tới một điểm dừng. Điều này có thể tạo ra vấn đề nếu một thread đang đợi cho tới khi một tài nguyên trở nên sẵn sàng. Phần cứng máy tính truyền thống không có nhiều hỗ trợ cho multi thread, vì chuyển đổi giữa các thread nói chung đã nhanh hơn chuyển đổi giữa các tiến trình. Bộ xử lý trong hệ thống nhúng, có nhiều yêu cầu cao hơn đói với xử lý thời gian thực, có thể hỗ trợ multi thread bằng cách giảm thời gian chuyển đổi giữa các thread, có lẽ bằng cách cấp phát một tập tin đăng ký chuyên biệt dành riêng cho mỗi thread thay vì lưu trữ hoặc khôi phục lại một tập tin đăng ký phổ biến. Vào cuối nhữn năm 90, ý tưởng thực hiện các tính toán đồng thời đã được biết đến như là multi thread đồng thời. Tính năng này đã được giới thiệu trong bộ vi xử lý Pentium 4 của Intel, có tên là Hyper Threading. 1.4. Tiến trình, thread nhân, thread người dùng, fiber Một tiến trình là đơn vị nặng nhất của lập lịch nhân. Tiến trình sở hữu tài nguyên được cấp phát bởi hệ điều hành. Tài nguyên bao gồm bộ nhớ, xử lý tập tin, socket, thiết bị xử lý, và window. Tiến trình không chia sẻ không gian địa chỉ hoặc tài nguyên tập tin ngoại trừ thông qua phương pháp rõ ràng như thừa kế tập tin xử lý hoặc các phân đoạn chia sẻ bộ nhớ, hoặc lập bản đồ cùng một tập tin tron một cách đã được chia sẻ. Tiến trình thường là đa nhiệm phòng ngừa (preemptively multitasked). Một thread nhân là thành phần nhẹ nhất của bộ nhân lập lịch. Ít nhất một thread nhân tồn tại trong một tiến trình. Nếu nhiều thread nhân tồn trại trong một tiến trình, sau đó chúng chia sẻ bộ nhớ và tài nguyên tập tin. Thread nhân là đa nhiệm phòng ngừa (preemptively multitasked) nếu quá trình lập lịch của hệ điều hành là “phòng ngừa”. Thread nhân không sử hữu tài nguyên cho riêng nó ngoại trừ 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 10 Lớp : K51CHTTT một ngăn xếp, một bản sao đăng ký bao gồm bộ đếm chương trình, và lưu trữ thread địa phương (thread-local). Hạt nhân có thể chỉ định một thread cho mỗi lõi (core) trong một hệ thống (bởi vì mỗi core tự chia nó thành nhiều core logic nếu nó hỗ trợ multi thread, hoặc chỉ hỗ trợ một core logic với mỗi core vật lý nếu không hỗ trợ multi thread) và có thể đổi chỗ thread để được chặn. Tuy nhiên, thread nhân mất nhiều thời gian hơn thread người dùng khi đổi chỗ. Thread đôi khi được thể hiện trong thư viện không gian người dùng (userspace), do đó được gọi là user thread. Kernel không phải để ý tới chúng, chúng được quản lý và lập lịch bởi userspace. User thread như được thực hiện bởi máy ảo nên cũng được gọi là green thread. User thread thường tạo ra và quản lý nhanh chóng, nhưng không thể tận dụng lợi thế của multi thread hay đa xử lý và bị chặn nếu tất cả các thread nhân liên quan bị chặn ngay cả khi có một số user thread đã sẵn sàng để chạy. Fibers là thành phần thậm chí còn nhẹ hơn cả đơn vị của bộ lập lịch dự kiến hợp tác: một fiber đang chạy phải rõ ràng “năng suất” để cho phép những fiber khác chạy, mà làm cho sự thể hiện của chúng dễ dàng hơn nhiều so với thread nhân hay thread người dùng. Một fiber có thể được lập lịch để chạy trong bất kỳ thread nào trong cùng một tiến trình. Điều này cho phép những ứng dụng đạt được những hiệu suất cải tiến bằng cách quản lý sự lập lịch, thay vì dựa vào bộ lập lịch của nhân (mà có thể không được điều chỉnh cho ứng dụng). Môi trường lập trình song song như OpenMP thường thể hiện nhiệm vụ của chúng thông qua fiber. 1.5. Vấn đề đưa ra của thread và fiber 1.5.1. Truy cập đồng thời và cấu trúc dữ liệu Những thread trong cùng một tiến trình chia sẻ cùng không gian địa chỉ. Điều này cho phép đồng thời chạy các đoạn mã thành từng cặp để trao đổi dữ liệu một cách thuận t