Bài toán năm triết gia

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN ĐỒ ÁN MÔN HỌC NGUYÊN LÝ HỆ ĐIỀU HÀNH ĐỀ TÀI : BÀI TOÁN NĂM TRIẾT GIA Người hướng dẫn : NGUYỄN VĂN NGUYÊN Sinh viên thực hiện : BÙI VŨ NHẬT HOÀNG Lớp : 06T3 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH Đà nẵng, 01/2010 GVHD : Th.S. NGUYỄN VĂN NGUYÊN 2/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH LỜI CẢM ƠN Những kiến thức cơ bản cũng như nâng cao về hệ điều hành, nắm bắt được nguyên tắc hoạt động. Nguyên lý hệ điều hành là học phần rất quan trọng và bắt buộc đối với tất cả sinh viên chuyên ngành công nghệ thông tin. Nguyên lý hệ điều hành cung cấp cho sinh viên động cơ bản của hệ điều hành trên máy tính. Hệ điều hành được xem là thành phần trung gian hay là cầu nối cho sự giao tiếp của người sử dụng và máy tính. Thông qua hệ điều hành người sử dụng dễ dàng làm việc và khai thác hiệu quả thiết bị phần cứng máy tính, quản lý phần mềm ứng dụng. Người sử dụng chỉ cần thao tác các lệnh, các sự kiện và chờ các tiến trình của hệ điều hành thực hiện. Với một Hệ điều hành có tiềm năng như thế, chúng ta phải có sự nghiên cứu, hiểu biết về nó, để có thể nắm bắt tốt về các khái niệm chuyên ngành về Hệ điều hành. Em xin cảm ơn sự hướng dẫn tận tình của thầy th.S. Nguyễn Văn Nguyên đã giúp em hoàn thành đề tài này. Sinh viên thực hiện Bùi Vũ Nhật Hoàng GVHD : Th.S. NGUYỄN VĂN NGUYÊN 3/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH LỜI MỞ ĐẦU Nếu không có phần mềm, máy tính chỉ là một thiết bị điện tử thông thường. Với sự hỗ trợ của phần mềm, máy tính có thể lưu trữ, xử lý thông tin và người sử dụng có thể gọi lại được thông tin này. Phần mềm máy tính có thể chia thành nhiều loại: chương trình hệ thống, quản lý sự hoạt động của chính máy tính. Chương trình ứng dụng, giải quyết các vấn đề liên quan đến việc sử dụng và khai thác máy tính của người sử dụng. Hệ điều hành thuộc nhóm các chương trình hệ thống và nó là một chương trình hệ thống quan trọng nhất đối với máy tính và cả người sử dụng. Hệ điều hành điều khiển tất cả các tài nguyên của máy tính và cung cấp một môi trường thuận lợi để các chương trình ứng dụng do người sử dụng viết ra có thể chạy được trên máy tính. Một máy tính hiện đại có thể bao gồm: một hoặc nhiều processor, bộ nhớ chính, clocks, đĩa, giao diện mạng, và các thiết bị vào/ra khác. Tất cả nó tạo thành một hệ thống phức tạp. Để viết các chương trình để theo dõi tất cả các thành phần của máy tính và sử dụng chúng một cách hiệu quả, người lập trình phải biết processor thực hiện chương trình như thế nào, bộ nhớ lưu trữ thông tin như thế nào, các thiết bị đĩa làm việc (ghi/đọc) như thế nào, lỗi nào có thể xảy ra khi đọc một block đĩa, … đây là những công việc rất khó khăn và quá khó đối với người lập trình. Nhưng rất may cho cả người lập trình ứng dụng và người sử dụng là những công việc trên đã được hệ điều hành hỗ trợ nên họ không cần quan tâm đến nữa. chúng ta cần tiềm hiểu về hệ điều hành để có một cái nhìn tổng quan về những gì liên quan đến việc thiết kế cài đặt cũng như chức năng của hệ điều hành để hệ điều hành đạt được mục tiêu: Giúp người sử dụng khai thác máy tính dễ dàng và chương trình của người sử dụng có thể chạy được trên máy tính. "Bài toán bữa tối của các triết gia" (Dining Philosophers), một bài toán kinh điển về tương tranh và chia sẻ tài nguyên. Việc nghiên cứu bài toán sẽ cho chúng ta hiểu rõ hơn về khía cạnh này của hệ điều hành. GVHD : Th.S. NGUYỄN VĂN NGUYÊN 4/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH PHỤ LỤC CHƯƠNG I BÀI TOÁN ....................................................................................6 I.1 Đề tài ........................................................................................................6 I.2 Mô tả vấn đề .............................................................................................6 I.3 Yêu cầu bài toán .......................................................................................6 CHƯƠNG II CƠ SỞ LÝ THUYẾT ...................................................................7 II.1 Tiến trình (proccess) ...............................................................................7 II.1.1 Khái niệm ........................................................................................7 II.1.2 Định nghĩa tiến trình ........................................................................7 II.1.3 Các loại tiến trình .............................................................................7 II.1.4 Tuyến (Thred) ..................................................................................7 II.2 Tài nguyên găng và đoạn găng ................................................................8 II.2.1 Tài nguyên găng (Critical Resource) ...............................................8 II.2.2 Đoạn găng (Critical Section) ............................................................9 II.2.3 Yêu cầu đối với đoạn găng ..............................................................9 II.3 Giải pháp Semaphore ..............................................................................9 II.4 Deadlock ...............................................................................................10 II.4.1 Giới thiệu vấn đề ............................................................................10 II.4.2 Điều kiện hình thành tắt nghẽn ......................................................11 II.4.3 Ngăn chặn tắc nghẽn (Deadlock Prevention) .................................11 CHƯƠNG III CÁCH GIẢI QUYẾT BÀI TOÁN ............................................12 III.1 Quản lý vùng găng ...............................................................................12 III.2 Giải pháp xử lý deadlock .....................................................................14 III.3 Chương trình ........................................................................................14 III.3.1 Class Philosopher .........................................................................15 III.3.2 Class Chopstick ............................................................................16 III.3.3 Class Diner ...................................................................................16 III.3.4 Class PhilCanvas ..........................................................................16 CHƯƠNG IV KẾT QUẢ CHƯƠNG TRÌNH ..................................................17 IV.1.1 Chương trình tạm dừng ................................................................17 IV.1.2 Chương trình được reset ...............................................................18 CHƯƠNG V KẾT LUẬN ...............................................................................19 V.1.1 Đạt được ........................................................................................19 V.1.2 Chưa đạt ........................................................................................19 GVHD : Th.S. NGUYỄN VĂN NGUYÊN 5/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH CHƯƠNG I BÀI TOÁN I.1 Đề tài Viết chương trình giải quyết bài toán “Năm triết gia ăn tối”. Chương trình tạo ra năm quá trình con mô phỏng hoạt động của năm triết gia. Sử dụng Semaphore để đồng bộ hoạt động của năm triết gia này. I.2 Mô tả vấn đề Đây là bài toán cổ điển về hệ điều hành. Bài toán bữa tối của các triết gia được đưa ra bởi nhà toán học E. W. Dijkstra. Bài toán được mô tả như sau : Có năm triết gia cùng ngồi ăn tối quanh một chiếc bàn tròn, trước mặt mỗi người có một đĩa mì Ý, giữa 2 triết gia thì có một chiếc nĩa. Mỗi triết gia dành toàn bộ thời gian để suy nghĩ hoặc ăn khi đói. Mỗi triết gia chỉ có thể ăn khi có được 2 chiếc nĩa bên cạnh mình. Đói : một triết gia có thể chết đói nếu ông ta không có cách nào để ăn được Tắc nghẽn : các triết gia phải đợi lẫn nhau nên không có ai ăn được. I.3 Yêu cầu bài toán Phải đặt ra thuật toán sao cho khi một triết gia bị đói thì ông ta sẽ được ăn và đảm bảo không có triết gia nào bị chết đói. Bài toán đặt ra vấn đề “đồng bộ giữa các tiến trình”, giải quyết vấn đề tắc nghẽn có thể xảy ra. Thuật toán được đưa ra là thuật toán Semaphore. GVHD : Th.S. NGUYỄN VĂN NGUYÊN 6/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH CHƯƠNG II CƠ SỞ LÝ THUYẾT II.1 Tiến trình (proccess) II.1.1 Khái niệm Tiến trình là một bộ phận của một chương trình đang thực hiện, đơn vị thực hiện tiến trình là processer. Vì tiến trình là một bộ phận của chương trình nên tương tự như chương trình tiến trình cũng sở hữu một con trỏ lệnh, một con trỏ stack, một tập các thanh ghi, một không gian địa chỉ trong bộ nhớ chính và tất cả các thông tin cần thiết khác để tiến trình có thể hoạt động được. II.1.2 Định nghĩa tiến trình Định nghĩa của Saltzer: Tiến trình là một chương trình do một processor logic thực hiện. Định nghĩa của Horning & Rendell: Tiến trình là một quá trình chuyển từ trạng thái này sang trạng thái khác dưới tác động của hàm hành động, xuất phát từ một trạng thái ban đầu nào đó. II.1.3 Các loại tiến trình Các tiến trình trong hệ thống có thể chia thành hai loại: tiến trình tuần tự và tiến trình song song. Tiến trình tuần tự là các tiến trình mà điểm khởi tạo của nó là điểm kết thúc của tiến trình trước đó. Tiến trình song song là các tiến trình mà điểm khởi tạo của tiến trình này mằn ở thân của các tiến trình khác, tức là có thể khởi tạo một tiến trình mới khi các tiến trình trước đó chưa kết thúc. Tiến trình tuần tự xuất hiện trong các hệ điều hành đơn nhiệm như hệ điều hành MSDOS Các tiến trình song song xuất hiện trong hệ điều hành đa nhiệm. Các tiến trình song song II.1.4 Tuyến (Thred) Tuyến là một thành phần của tiến trình sở hữu ngăn xếp và thực thi độc lập ngay trong mã lệnh của tiến trình. Nếu như hệ điều hành có nhiều tiến trình thì trong mỗi tiến trình bạn có thể tạo ra nhiều tuyến hoạt dộng song song với nhau tương tự như các tiến trình hoạt động song song trong hệ điều hành. Ưu điểm của tuyến là chúng hoạt động trong cùng một không gian địa chỉ của tiến trình. Tập hợp một nhóm các tuyến có thể sử dụng chung biến toàn cục, vùng nhớ heap, bảng mô tả file… của GVHD : Th.S. NGUYỄN VĂN NGUYÊN 7/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH tiến trình, cơ chế liên lạc giữa các tuyến đơn giản và hiệu quả hơn cơ chế liên lạc giữa các tiến trình với nhau ( nếu hệ điều hành của bạn chạy trên phần cứng nhiều bộ xử lí thì tuyến thực sự chạy song song chứ không phải giả lập kiểu xoay vòng ). Ưu điểm của sử dụng tuyến trong tiến trình đơn giản hơn lập trình tuần tự. Nhiều thao tác xuất nhập hoặc hiển thị dữ liệu có thể tách rời và phân cho các tuyến chạy độc lập thực thi. Ví dụ trong môi trường đồ họa, khi bạn copy một file có kích thước lớn, chương trình sẽ được thiết kế sao cho một tuyến thực hiện đọc ghi dữ liệu từ đĩa, tuyến khác sẽ đảm trách việc hiển thị phần trăm hoàn thành công việc cho người dùng theo dõi tiến độ. Đối với hệ điều hành chi phí để chuyển đổi giữa ngữ cảnh của tiến trình cao và chậm hơn chi phí chuyển đổi ngữ cảnh dành cho tuyến ( với tiến trình hệ điều hành phải cất thông số môi trường, thanh ghi trạng thái, hoán đổi vùng nhớ…) Tuy nhiên, điểm yếu của việc dùng tuyến đó là khả năng đổ vở của một tuyến sẽ ảnh hưởng đến tất cả các tuyến khác và toàn bộ tiến trình đang hoạt động. Lí do là các tuyến dùng chung vùng nhớ và không gian địa chỉ của tiến trình. Ngược lại, một tiến trình bị đổ vỡ luôn được hệ điều hành cô lập hoàn toàn không gây ảnh hưởng đến các tiến trình khác. Tiến trình có thể chạy trên nhiều máy khác nhau trong khi tuyến chỉ được thực thi trên một máy và trong một tiến trình. II.2 Tài nguyên găng và đoạn găng II.2.1 Tài nguyên găng (Critical Resource) Trong môi trường hệ điều hành đa nhiệm - đa chương – đa người sử dụng, việc chia sẻ tài nguyên cho các tiến trình của người sử dụng dùng chung là cần thiết, nhưng nếu hệ điều hành không tổ chức tốt việc sử dụng tài nguyên dung chung của các tiến trình hoạt động đồng thời, thì không những không mang lại hiệu quả khai thác tài nguyên của hệ thống mà còn làm hỏng dữ liệu của các ứng dụng. Và nguy hiểm hơn là việc hỏng dữ liệu này có thể hệ điều hành và ứng dụng không thể phát hiện được. Việc hỏng dữ liệu của ứng dụng có thể làm sai lệch ý nghĩa thiết kế của nó. Đây là điều mà cả hệ điều hành và người lập trình đều không mong muốn. Các tiến trình hoạt động đồng thời thường cạnh tranh với nhau trong việc sử dụng tài nguyên dùng chung. Hai tiến trình hoạt động đồng thời cùng ghi vào một không gian nhớ chung (một biến chung) trên bộ nhớ hay hai tiến trình đồng thời cùng ghi dữ liệu vào một file chia sẻ, đó là những biểu hiện của sự cạnh tranh về việc sử dụng tìa nguyên dùng chung của các tiến trình. Để các tiến trình hoạt động đồng thời không cạnh tranh hay xung đột với nhau khi sử dụng tài nguyên dùng chung hệ điều hành phải tổ chức cho các tiến trình này được độc quyền truy xuất/sử dụng trên các tài nguyên dùng chung này. Những tài nguyên được hệ điều hành chia sẻ cho nhiều tiến trình hoạt động đồng thời dùng chung, mà có nguy cơ dẫn đến sự tranh chấp giữa các tiến trình này khi sử dụng chúng, được gọi là tài nguyên găng. Tài nguyên găng có thể là tài nguyên phần cứng hoặc tài nguyên phần mền, có thể là tài nguyên phân chia được hoặc không phân chia được, nhưng đa số thường là tài nguyên phân chia được như là: các biến chung, các file chia sẻ. GVHD : Th.S. NGUYỄN VĂN NGUYÊN 8/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH II.2.2 Đoạn găng (Critical Section) Đoạn code trong các tiến trình đồng thời, có tác động đến các tài nguyên có thể trở thành tài nguyên găng được gọi là đoạn găng hay miền găng. Tức là, các đoạn code trong các chương trình dùng để truy cập đến các vùng nhớ chia sẻ, các tập tin chia sẻ được gọi là các đoạn găng. Trong ví dụ 1 ở trên có hai đoạn găng là: { L1 := Count và Count := L1 } Để hạn chế các lỗi có thể xảy ra do sử dụng tài nguyên găng, hệ điều hành phải điều khiển các tiến trình sao cho, tại một thời điểm chỉ có một tiến trình nằm trong đoạn găng, nếu có nhiều tiến trình cùng muốn vào (thực hiện) đoạn găng thì chỉ có một tiến trình được vào, các tiến trình khác phải chờ, một tiến trình khi ra khỏi (kết thúc) đoạn găng phải báo cho hệ điều hành và/hoặc các tiến trình khác biết để các tiến trình này vào đoạn găng, vv. Các công tác điều khiển tiến trình thực hiện đoạn găng của hệ điều hành được gọi là điều độ tiến trình qua đoạn găng. Để công tác điều độ tiến trình qua đoạn găng được thành công, thì cần phải có sự phối hợp giữa vi xử lý, hệ điều hành và người lập trình. Vi xử lý đưa ra các chỉ thị, hệ điều hành cung cấp các công cụ để người lập trình xây dựng các sơ đồ điều độ hợp lý, để đảm bảo sự độc quyền trong việc sử dụng tài nguyên găng của các tiến trình. II.2.3 Yêu cầu đối với đoạn găng Đoạn găng phải thỏa các yêu cầu sau : • Tại một thời điểm không thể có hai tiến trình nằm trong đoạn găng. • Nếu có nhiều tiến trình đồng thời cùng xin được vào đoạn găng thì chỉ có một tiến trình được phép vào đoạn găng, các tiến trình khác phải xếp hàng chờ trong hàng đợi. • Tiến trình chờ ngoài đoạn găng không được ngăn cản các tiến trình khác vào đoạn găng. • Không có tiến trình nào được phép ở lâu vô hạn trong đoạn găng và không có tiến trình phải chờ lâu mới được vào đoạn găng (chờ trong hàng đợi). • Nếu tài nguyên găng được giải phóng thì hệ điều hành có nhiệm vụ đánh thức các tiến trình trong hàng đợi ra để tạo điều kiện cho nó vào đoạn găng. Các vấn đề có thể gặp phải đối với đoạn găng • Có thể dẫn đến tắc nghẽn (Deadlock) trong hệ thống. • Các tiến trình có thể bị đói (Stravation) tài nguyên. II.3 Giải pháp Semaphore Semaphore là một đóng góp quan trọng khác của nhà toán học E. W. Dijkstra. Có thể xem Semaphore như là một mở rộng của Mutex locks. Semaphore (sự đánh tín hiệu bằng cờ) S là một biến nguyên, khởi gán bằng một giá trị không âm, đó là khả năng phục vụ của tài nguyên găng tương ứng với nó. Ứng với S có một hàng đợi F(s) để lưu các tiến trình đang bị blocked trên S. Chỉ có hai thao tác Down và Up được tác động đến semaphore (sự đánh tín hiệu bằng cờ) S. Down giảm S xuống một đơn vị, Up tăng S lên một đơn vị. Mỗi tiến trình trước khi vào đoạn găng thì phải gọi Down để kiểm tra và xác lập quyền vào đoạn găng. GVHD : Th.S. NGUYỄN VĂN NGUYÊN 9/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH Mỗi tiến trình ngay sau khi ra khỏi đoạn găng phải gọi Up để kiểm tra xem có tiến trình nào đang đợi trong hàng đợi hay không, nếu có thì đưa tiến trình trong hàng đợi vào đoạn găng. Khi tiến trình gọi Up thì hệ thống sẽ thực hiện. Ở đây chúng ta cần lưu ý rằng: Down và Up là các thủ tục của hệ điều hành, nên hệ điều hành đã cài đặt cơ chế độc quyền cho nó, tức là các lệnh bên trong nó không thể tách rời nhau. II.4 Deadlock II.4.1 Giới thiệu vấn đề Trong môi truờng đa chương, nhiều quá trình có thể cạnh tranh một số giới hạn tài nguyên. Một quá trình yêu cầu tài nguyên, nếu tài nguyên không sẳn dùng tại thời điểm đó, quá trình đi vào trạng thái chờ. Quá trình chờ có thể không bao giờ chuyển trạng thái trở lại vì tài nguyên chúng yêu cầu bị giữ bởi những quá trình đang chờ khác. Trường hợp này được gọi là deadlock (khoá chết). Trong trường hợp bài toán là khi tất cả các triết gia đều đói cùng một lúc, họ ngồi vào bàn và tất cả cùng nhấc chiếc nĩa bên tay phải của mình, và cùng chờ đợi chiếc nĩa từ hàng xóm bên tay trái dẫn đến các tiến trình bị khóa chết. GVHD : Th.S. NGUYỄN VĂN NGUYÊN 10/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH II.4.2 Điều kiện hình thành tắt nghẽn Năm 1971, Coffman đã đưa ra và chứng tỏ được rằng, nếu hệ thống tồn tại đồng thời bốn điều kiện sau đây thì hệ thống sẽ xảy ra tắt nghẽn: • Loại trừ lẫn nhau (mutual excution) hay độc quyền sử dụng: Đối với các tài nguyên không phân chia được thì tại mỗi thời điểm chỉ có một tiến trình sử dụng được tài nguyên. • Giữ và đợi (hold and wait): Một tiến trình hiện tại đang chiếm giữ tài nguyên, lại xin cấp phát thêm tài nguyên mới. • Không ưu tiên (No preemption): Không có tài nguyên nào có thể được • giải phóng từ một tiến trình đang chiếm giữ nó. Sự tắc nghẽn có thể tồn tại với ba điều kiện trên, nhưng cũng có thể không xảy ra chỉ với 3 điều kiện đó. Để chắc chắn tắc nghẽn xảy ra cần phải có điều kiện thư tư. • Đợi vòng tròn (Circular wait): Đây là trường hợp của ví dụ 1 mà chúng ta đã nêu ở trên. Tức là, mỗi tiến trình đang chiếm giữ tài nguyên mà tiến trình khác đang cần. II.4.3 Ngăn chặn tắc nghẽn (Deadlock Prevention) Ngăn chặn tắc nghẽn là thiết kế một hệ thống sao cho hiện tượng tắc nghẽn bị loại trừ. Các phương thức ngăn chặn tắc nghẽn đều tập trung giải quyết bốn điều kiện gây ra tắc nghẽn, sao cho hệ thống không thể xảy ra đồng thời bốn điều kiện tắc nghẽn: • Đối với điều kiện độc quyền: Điều kiện này gần như không tránh khỏi, vì sự độc quyền là cần thiết đối với tài nguyên thuộc loại phân chia được như các biến chung, các tập tin chia sẻ, hệ điều hành cần phải hỗ trợ sự độc quyền trên các tài nguyên này. • Đối với điều kiện giữ và đợi: Điều kiện này có thể ngăn chặn bằng cách yêu cầu tiến trình yêu cầu tất cả tài nguyên mà nó cần tại một thời điểm và tiến trình sẽ bị khoá (blocked) cho đến khi yêu cầu tài nguyên của nó được hệ điều hành đáp ứng. Phương pháp này không hiệu quả. Thứ nhất, tiến trình phải đợi trong một khoảng thời gian dài để có đủ tài nguyên mới có thẻ chuyển sang hoạt động được, trong khi tiến trình chỉ cần một số ít tài nguyên trong số đó là có thể hoạt động được, sau đó yêu cầu tiếp. Thứ hai, lãng phí tài nguyên, vì có thể tiến trình giữa nhiều tài nguyên mà chỉ đến khi sắp kết thúc tiến trình mới sử dụng, và có thể đây là những tài nguyên mà các tiến trình khác đang rất cần. Ở đây hệ điều hành có thể tổ chức phân lớp tài nguyên hệ thống. Theo đó tiến trình phải trả tài nguyên ở mức thấp mới được cấp phát tài nguyên ở cấp cao hơn. • Đối với điều kiện No preemption: Điều kiện này có thể ngăn chặn bằng cách, khi tiến trình bị rơi vào trạng thái khoá, hệ điều hành có thể thu hồi tài nguyên của tiến trình bị khoá để cấp phát cho tiến trình khác và cấp lại đầy đủ tài nguyên cho tiến trình khi tiến trình được đưa ra khỏi trạng thái khoá. • Đối với điều kiện chờ đợi vòng tròn: Điều kiện này có thể ngăn chặn bằng cách phân lớp tài nguyên của hệ thống. Theo đó, nếu một tiến trình được cấp phát tài nguyên ở lớp L, thì sau đó nó chỉ có thể yêu cầu các tài nguyên ở lớp thấp hơn lớp L. GVHD : Th.S. NGUYỄN VĂN NGUYÊN 11/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH CHƯƠNG III CÁCH GIẢI QUYẾT BÀI TOÁN III.1 Quản lý vùng găng Chương trình xem mỗi triết gia là 1 tiến trình, chopstick là tài nguyên chung cần được bảo vệ. Biến taken được xây dựng trong class Chopstick để quả lý tài nguyên dùng chung là các chopsticks, mỗi chopsticks được tạo ra sẽ có 1 biến khóa taken để đánh dấu : • taken = true chopstick đã được sử dụng. • taken = false chopstick chưa được sử dụng. Class Chopstick đóng vai trò quản lý vùng găng với 2 phương thức synchronized put() và get() để mở và đóng vùng găng. synchronized void put() { taken=false; display.setChopstick(identity,taken); notify(); } Phương thức này tương ứng với hành động một triết gia đặt Chopstick xuống (giải phóng Chopstick) để các triết gia khác có thể sử dụng tài nguyên chung này. synchronized void get()throws java.lang.InterruptedException { while (taken) wait(); taken=true; display.setChopstick(identity,taken); } Nếu tài nguyên chung (Chopstick) đang được sử dụng thì triết gia phải đợi (wait) cho đến khi tài nguyên được giải phóng, lúc đó triết gia sử dụng tài nguyên này đồng thời thiết lập taken = true để khóa các tiến trình khác. Như vậy biến taken đóng vai trò khóa vùng tài nguyên dùng chung khi nó đang được sử dụng bởi một tiến trình. GVHD : Th.S. NGUYỄN VĂN NGUYÊN 12/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH Xét trường hợp cụ thể sau Chương trình tạo ra 5 tiến trình tương ứng với 5 triết gia và 5 tài nguyên dùng chung tương ứng 5 chopsticks public void start() { for (int i =0; i<display.NUMPHILS; ++i) chopstick[i] = new Chopstick(display,i); for (int i =0; i<display.NUMPHILS; ++i){ phil[i] = makePhilosopher(this,i, chopstick[(i-1+display.NUMPHILS)% display.NUMPHILS], chopstick[i]); phil[i].start(); } } Xét trạng thái cụ thể của các chopsticks ta có chopsticks[0].taken == false chopsticks[1].taken == false chopsticks[2].taken == false chopsticks[3].taken == true chopsticks[4].taken == false GVHD : Th.S. NGUYỄN VĂN NGUYÊN 13/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH III.2 Giải pháp xử lý deadlock Vấn đề deadlock có thể được tránh khỏi bằng viêc xây dụng phương thức Wait() và Signal() sao cho vòng tròn đợi không xảy ra Ở đây các phương thức được cài đặt như sau public void Wait()throws java.lang.InterruptedException{ if(identity%2==0){ view.setPhil(identity,view.HUNGRY); right.get(); //gotright chopstick view.setPhil(identity,view.GOTRIGHT); sleep(500); left.get(); } else{ view.setPhil(identity,view.HUNGRY); left.get(); //gotleft chopstick view.setPhil(identity,view.GOTLEFT); sleep(500); right.get(); } } public void Signal(){ right.put(); left.put(); } Phương thức Wait() và Signal() được xây dựng để quản lí tiến trình ra vào vùng găng. Với cách xây dựng như trên thì 2 tiến trình cạnh nhau có số thứ tự chẳn lẽ khác nhau sẽ có thứ tự lấy các chopstick theo thứ tự khác nhau. III.3 Chương trình Chương trình được xây dựng gồm 4 class Class Diners : đây là class chính khởi tạo và liên kết các class khác Class PhilCanvas : quản lí giao diện Class Philosopher : class tạo các tiến trình Class Chopstick : tài nguyên dùng chung (chopstick ) GVHD : Th.S. NGUYỄN VĂN NGUYÊN 14/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH Các class quan hệ như sơ đồ sau III.3.1 Class Philosopher Các biến cần xét • private int indentity : dùng để đánh chỉ số (định id) cho từng tiến trình • private Chopstick left, right : đây là 2 tài nguyên dùng chung mà mỗi tiến trình được phép sử dụng. Phương thức Wait() và Signal() quản lí tiến trình vào vùng găng và giải quyết vấn đề tắc nghẽn. Phương thức run() : chạy tiến trình while (true) { 1. view.setPhil(identity,view.THINKING); 2. sleep(controller.sleepTime()); 3. Wait(); 4. view.setPhil(identity,view.EATING); 5. sleep(controller.eatTime()); 6. Signal(); } 1 và 2 tiến trình đang chờ đợi để vào vùng găng. 3 tiến trình gọi phương thức Wait() để kiểm tra điều kiện vào vùng găng. 4 và 5 tiến trình được thực thi. GVHD : Th.S. NGUYỄN VĂN NGUYÊN 15/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH 6 thoát khỏi vùng găng và giải phóng tài nguyên. III.3.2 Class Chopstick Các biến cần xét • private boolean taken : đánh dấu trạng thái của chopstick đã được sử dụng hay chưa, taken == true là tài nguyên đã được sử dụng, taken == false chưa được sử dụng. • private int indentity : định danh cho chopstick. Phương thức get() được gọi khi một tiến trình muốn sử dụng tài nguyên. Phương thức put() được gọi để giải phóng tài nguyên. III.3.3 Class Diner Khởi tạo giao diện, khởi tạo các tiến trình, tạo môi trường cho các tiến trình hoạt động. III.3.4 Class PhilCanvas Quản lí giao diện. GVHD : Th.S. NGUYỄN VĂN NGUYÊN 16/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH CHƯƠNG IV KẾT QUẢ CHƯƠNG TRÌNH IV.1.1 Chương trình tạm dừng Từ kết quả demo ta có : • Triết gia số 0 và số 3 đang đói • Triết gia sô 1 và số đang suy nghĩ • Triết gia số 4 đang ăn GVHD : Th.S. NGUYỄN VĂN NGUYÊN 17/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH IV.1.2 Chương trình được reset Khởi động lại các tiến trình được tạm dừng, reset lại băng thông báo trạng thái. GVHD : Th.S. NGUYỄN VĂN NGUYÊN 18/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH CHƯƠNG V KẾT LUẬN V.1.1 Đạt được Chương trình đạt được chức năng mô tả bài toán bằng giao diện trực quan sinh động, sử dụng giao diện swing trên nền applet. Tạo các tiến trình mô phỏng dựa trên lớp Thread. Bằng cách sử dụng slider cho phép người dùng tùy chỉnh thời gian cung cấp cho các tiến trình, giúp dễ dàng nắm bắt và kiểm soát. Bằng cách xây dựng phương thức Wait() chương trình đã xử lý được vấn đề deadlock. Chương trình được phân thành các class với các chức năng rõ ràng tạo thuận lợi cho việc mở rộng và phát triển sau này, đặc biệt phát triển giao diện một cách dễ dàng mà không ảnh hưởng đến phần lõi của chương trình. Chương trình có thể được phát triển mở rộng cho n tiến trình tùy ý. V.1.2 Chưa đạt Phần giao diện chương trình chưa được bắt mắt. GVHD : Th.S. NGUYỄN VĂN NGUYÊN 19/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH TÀI LIỆU THAM KHẢO [1] Đặng Vũ Tùng, Giáo trình Nguyên Lý Hệ Điều Hành, NXB Hà Nội(2005) [2] [3] Đồ án mẫu khóa 05 GVHD : Th.S. NGUYỄN VĂN NGUYÊN 20/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH PHỤ LỤC // import java.awt.*; import java.awt.event.*; import java.applet.*; import java.awt.*; import java.awt.geom.AffineTransform; import javax.swing.*; public class Diners extends JApplet { PhilCanvas display; Thread[] phil= new Thread[PhilCanvas.NUMPHILS]; Chopstick[] chopstick = new Chopstick[PhilCanvas.NUMPHILS]; JScrollBar slider; JButton restart; JButton freeze; TextArea txtMes; public void init() { setLayout(new BorderLayout()); display = new PhilCanvas(this); display.setSize(300,320); add("Center",display); slider = new JScrollBar(Scrollbar.HORIZONTAL, 50, 5, 0, 100); restart = new JButton("Restart"); restart.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { if (display.deadlocked()) { stop(); slider.setValue(50); start(); } display.thaw(); } }); freeze = new JButton("Freeze"); freeze.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { display.freeze(); } }); GVHD : Th.S. NGUYỄN VĂN NGUYÊN 21/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH Panel p2 = new Panel(); p2.setLayout(null); p2.setSize(150,400); Label l0,l1,l2,l3,l4,l5,l6; l1 = new Label("EATING"); l2 = new Label(""); l2.setBackground(Color.GREEN); l3 = new Label("HUNGRY"); l4 = new Label(""); l4.setBackground(Color.BLUE); l5 = new Label("THINKING"); l6 = new Label(""); l6.setBackground(Color.YELLOW); l1.setBounds(10,220,60,30); p2.add(l1); l2.setBounds(80,220,50,30); p2.add(l2); l3.setBounds(10,260,60,30); p2.add(l3); l4.setBounds(80,260,50,30); p2.add(l4); l5.setBounds(10,300,60,30); p2.add(l5); l6.setBounds(80,300,50,30); p2.add(l6); p2.setBackground(Color.WHITE); txtMes = new TextArea(); txtMes.setBounds(0,0,150,200); p2.add(txtMes); Panel p1 = new Panel(); p1.setLayout(new BorderLayout()); p1.add("Center",slider); p1.add("East",restart); p1.add("West",freeze); add("South",p1); add("West",p2); setSize(600,400); } Thread makePhilosopher(Diners d, int id, Chopstick left, Chopstick right) { return new Philosopher(d,id,left,right); } public int sleepTime() { return (slider.getValue()*(int)(100*Math.random())); } GVHD : Th.S. NGUYỄN VĂN NGUYÊN 22/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH public int eatTime() { return (slider.getValue()*(int)(50*Math.random())); } public void start() { for (int i =0; i<display.NUMPHILS; ++i) chopstick[i] = new Chopstick(display,i); for (int i =0; i<display.NUMPHILS; ++i){ phil[i] = makePhilosopher(this,i, chopstick[(i-1+display.NUMPHILS)% display.NUMPHILS], chopstick[i]); phil[i].start(); } } public void stop() { for (int i =0; i<display.NUMPHILS; ++i) { phil[i].interrupt(); } } } class Philosopher extends Thread { private int identity; private PhilCanvas view; private Diners controller; private Chopstick left; private Chopstick right; Philosopher(Diners ctr, int id, Chopstick l, Chopstick r) { controller = ctr; view = ctr.display; identity = id; left = l; right = r; } public void Wait()throws java.lang.InterruptedException{ if(identity%2==0){ view.setPhil(identity,view.HUNGRY); right.get(); //gotright chopstick view.setPhil(identity,view.GOTRIGHT); sleep(500); left.get(); } GVHD : Th.S. NGUYỄN VĂN NGUYÊN 23/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH else{ view.setPhil(identity,view.HUNGRY); left.get(); //gotright chopstick view.setPhil(identity,view.GOTLEFT); sleep(500); right.get(); } } public void Signal(){ right.put(); left.put(); } public void run() { try { while (true) { //thinking view.setPhil(identity,view.THINKING); sleep(controller.sleepTime()); //hungry Wait(); //eating view.setPhil(identity,view.EATING); sleep(controller.eatTime()); Signal(); } } catch (java.lang.InterruptedException e) {} } } class Chopstick { private boolean taken=false; private PhilCanvas display; private int identity; Chopstick(PhilCanvas disp, int id){ display = disp; identity = id; } synchronized void put() { taken=false; display.setChopstick(identity,taken); GVHD : Th.S. NGUYỄN VĂN NGUYÊN 24/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH notify(); } synchronized void get()throws java.lang.InterruptedException { while (taken) wait(); taken=true; display.setChopstick(identity,taken); } } class PhilCanvas extends Canvas { Diners controller; Image offscreen; Dimension offscreensize; Graphics offgraphics; static final int NUMPHILS = 5; static final int THINKING = 0; static final int HUNGRY = 1; static final int GOTRIGHT = 2; static final int EATING =3; static final int GOTLEFT = 4; Image[] imgs = new Image[5]; AffineTransform [] philPlace = new AffineTransform[NUMPHILS]; int [] state = new int [NUMPHILS]; double [] chopX = new double[NUMPHILS]; double [] chopY = new double[NUMPHILS]; double [] disX = new double[NUMPHILS]; double [] disY = new double[NUMPHILS]; boolean[] untable= new boolean[NUMPHILS]; boolean frozen = false; String Message = ""; PhilCanvas(Diners controller) { super(); this.controller = controller; MediaTracker mt; mt = new MediaTracker(this); imgs[0] = controller.getImage(controller.getDocumentBase(), "image/thinking.gif"); mt.addImage(imgs[0], 0); imgs[1] = controller.getImage(controller.getDocumentBase(), "image/hungry.gif"); mt.addImage(imgs[1], 1); GVHD : Th.S. NGUYỄN VĂN NGUYÊN 25/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH imgs[2] = controller.getImage(controller.getDocumentBase(), "image/gotright.gif"); mt.addImage(imgs[2], 2); imgs[3] = controller.getImage(controller.getDocumentBase(), "image/eating.gif"); mt.addImage(imgs[3], 3); imgs[4] = controller.getImage(controller.getDocumentBase(), "image/gotleft.gif"); mt.addImage(imgs[4], 4); try { mt.waitForID(0); mt.waitForID(1); mt.waitForID(2); mt.waitForID(3); mt.waitForID(4); } catch (java.lang.InterruptedException e) { System.out.println("Couldn't load one of the images"); } initPlacing(); } void backdrop() { Dimension d = getSize(); if ((offscreen == null) || (d.width != offscreensize.width) || (d.height != offscreensize.height)) { offscreen = createImage(d.width, d.height); offscreensize = d; offgraphics = offscreen.getGraphics(); offgraphics.setFont(new Font("Helvetica",Font.BOLD,18)); Graphics2D g2D = (Graphics2D) offgraphics; g2D.translate(d.width/2, d.height/2); } offgraphics.setColor(Color.WHITE); offgraphics.fillRect(-d.width/2, -d.height/2, d.width, d.height); } void drawtable() { offgraphics.setColor(Color.red); offgraphics.fillOval(-80,-80,160,160); offgraphics.setColor(Color.black); for(int i=0; i<NUMPHILS; i++) { if(untable[i]){ offgraphics.setColor(Color.black); offgraphics.fillRect((int)chopX[i],(int)chopY[i],5,30); } GVHD : Th.S. NGUYỄN VĂN NGUYÊN 26/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH offgraphics.setColor(Color.black); offgraphics.drawString(String.valueOf(i),(int)disX[i],(int)disY[i]); offgraphics.setColor(Color.WHITE); offgraphics.fillOval((int)disX[i],(int)disY[i],25,25); } } public void paint(Graphics g) { update(g); } public void update(Graphics g) { backdrop(); for (int i = 0; i < NUMPHILS; i++) { philPaint(offgraphics,i); if(state[i]==EATING) Message += "Philosopher "+i+" EATING"; } controller.txtMes.setText(Message); drawtable(); if (deadlocked()) { offgraphics.setColor(Color.black); offgraphics.drawString("DEADLOCKED",-60,0); } g.drawImage(offscreen, 0, 0, null); } void philPaint(Graphics g,int i) { Graphics2D g2D = (Graphics2D)g; g2D.drawImage(imgs[state[i]],philPlace[i],this); } synchronized void setPhil(int id,int s) throws java.lang.InterruptedException{ while (frozen) wait(); state[id] = s; repaint(); } synchronized void freeze(){ frozen = true; } synchronized void thaw() { frozen = false; notifyAll(); Message = ""; GVHD : Th.S. NGUYỄN VĂN NGUYÊN 27/28 BÁO CÁO ĐỒ ÁN NGUYÊN LÝ HỆ ĐIỀU HÀNH } synchronized void setChopstick(int id, boolean taken) { untable[id]= !taken; } boolean deadlocked(){ int i=0; while(i<NUMPHILS && state[i]==GOTRIGHT) ++i; return i==NUMPHILS; } void initPlacing() { double radius = 130.0; double philWidth = imgs[0].getWidth(this); double philHeight = imgs[0].getHeight(this); double radians; for (int i = 0; i < NUMPHILS; i++) { philPlace[i] = new AffineTransform(); radians = 2.0 * Math.PI*(1.0 - (double) i/(double)NUMPHILS); philPlace[i].rotate(radians); philPlace[i].translate(0,-radius); philPlace[i].translate(-philWidth/2,-philHeight/2); } radius = 55; for (int i = 0; i < NUMPHILS; i++) { radians = (double)i * 2.0 * Math.PI / (double)NUMPHILS + Math.PI/ (double)NUMPHILS; chopX[i] = -Math.sin(radians) * radius; chopY[i] = -Math.cos(radians) * radius; untable[i] = true; } radius = 65; for (int i = 0; i < NUMPHILS; i++) { radians = (double)i * 2.0 * Math.PI / (double)NUMPHILS; disX[i] = -Math.sin(radians) * radius-12; disY[i] = -Math.cos(radians) * radius-12; } } } GVHD : Th.S. NGUYỄN VĂN NGUYÊN 28/28