Tiểu luận Hệ tin học phân tán: Vấn đề bế tắc trong hệ tập trung và hệ phân tán

BáocáoHệtinhọcphântán LỜI MỞ ĐẦU Hệ tin học phân tán là hệ thống xử lý thông tin bao gồm nhiều bộ xử lý hoặc bộ vi xử lý nằm tại các vị trí khác nhau và được liên kết với nhau thông qua phương tiện viễn thông dưới sự điều khiển thống nhất của một hệ điều hành. Hệ tin học phân tán rất đa dạng, đa diện, phức tạp về mặt cấu trúc, tập hợp bao gồm các bộ xử lý hoặc bộ vi xử lý với bộ nhớ và đồng hồ nhịp độc lập, các bộ xử lý không sử dụng chung bộ nhớ và đồng hồ. Như vậy mỗi một hệ xử lý thông tin thành phần của hệ tin học phân tán bao gồm một hay nhiều bộ xử lý và bộ nhớ cục bộ. Trong hệ phân tán hệ xử lý thông tin thành phần phải được thiết kế sao cho về cấu trúc, số lượng và dung lượng có thể cho phép thực hiện một cách trọn vẹn các chức năng mà nó phải đảm nhận. Hệ tin học phân tán thực hiện hàng loạt các chức năng phức tạp, nhưng cơ bản nhất là đảm bảo cung cấp cho người sử dụng khả năng truy cập có kết quả đến các loại tài nguyên vốn có và rất đa dạng của hệ thống như là những tài nguyên dùng chung. Những ưu điểm căn bản của việc sử dụng chung tài nguyên so với hệ tập trung được phản ảnh như sau: 1. Tăng tốc độ bình quân trong tính toán­xử lý. 2. Cải thiện tình trạng luôn luôn sẵn sàng của các loại tài nguyên. 3. Tăng độ an toàn dữ liệu. 4. Đa dạng hóa các loại hình dịch vụ tin học. 5. Đảm bảo tính vẹn toàn của thông tin. Điều quan trọng là để đảm bảo các chức năng, yêu cầu nêu trên, hệ phân tán cần phải có các cơ chế kỹ thuật đủ mạng nhằm đồng bộ hóa hoạt động của các tiến trình và sự trao đổi thông tin với nhau sao cho hệ thống tránh được các trường hợp có thể dẫn đến bế tắc mà khi nghiên cứu hệ điều hành các máy tính chúng ta đã có dịp làm quen. Để tìm hiểu rõ hơn về vấn đề bế tắc và thuật toán dự phòng bế tắc của Lomet tôi chọn đề tài “Vấn đề bế tắc trong hệ tập trung và hệ phân tán” để nghiên cứu. Trong thời gian thực hiện đề tài, tôi đã nhận được sự hướng dẫn tận tình của PGS.TS Lê Văn Sơn, được sự động viên và giúp đỡ của đồng nghiệp trong cơ quan và các anh chị em lớp Cao học ­ Khoa học Máy tính Khóa 10 (2008 – 2011) để hoàn thành đề tài. Xin chân thành cảm ơn! Học viên: Nguyên Văn Việt Đức Trang 1 BáocáoHệtinhọcphântán Học viên: Nguyên Văn Việt Đức Trang 2 BáocáoHệtinhọcphântán Chương 1. BẾ TẮC TRONG HỆ TẬP TRUNG 1.1 Bếtắc Tất cả các hiện tượng bế tắc đều bắt nguồn từ sự xung đột về tài nguyên củahai hoặcnhiềutiến trìnhđang hoạt động đồng thời trên hệ thống. Tài nguyên ở đây có thể là một ổ đĩa, một mẫu tin trong cơ sở dữ liệu, hay một không gian địachỉtrênbộnhớchính.Sauđâylàmộtsốvídụminhhoạchođiềutrên. Ví dụ 1: Giả sử có hai tiến trình P1 và P2 hoạt động đồng thời trong hệ thống. Tiến trình P1 đang giữ tài nguyên R1 và xin được cấp R2 để tiếp tục hoạt động, trong khi đó tiến trình P2 đang giữ tài nguyên R2 và xin được cấp R1 để tiếp tục hoạt động. Trong trường hợp này cả P1 và P2 sẽ không tiếp tục hoạt động được. Như vậy, P1 và P2 rơi vào trạng thái bế tắc (minh hoạ bởi sơ đồ ở hình 1.1). Tài nguyên R2 Tiến trình 1 (P1) Tiến trình 2 (P2) Tài nguyên R1 Hình1.1. Chờđợivòngtròn Bế tắc thường xảy ra do xung đột về tài nguyên thuộc loại không phân chia được,mộtsốíttrườnghợpxảyravớitàinguyênphânchiađược.Vídụ sauđâylà trường hợp bế tắc do xung đột về tài nguyên bộ nhớ, là tài nguyên thuộc loại phânchiađược. Ví dụ 2: Giả sử không gian bộ nhớ còn trống là 200Kb, trong hệ thống có hai tiến trình P1 và P2 yêu cầu được sử dụng bộ nhớ như sau: P1 P2 …. …. Request1 80Kb …. Request2 30Kb …. Request1 70Kb …. Request2 40Kb …. Bế tắc xảy ra khi cả hai tiến trình cùng yêu cầu thêm bộ nhớ lần thứ hai. Tại thời điểm này, không gian bộ nhớ còn trống là 50Kb, lớn hơn lượng bộ nhớ mà mỗi tiến trình yêu cầu (30Kb và 40Kb), nhưng vì cả hai tiến tình Học viên: Nguyên Văn Việt Đức Trang 3 BáocáoHệtinhọcphântán đồng thời yêu cầu thêm bộ nhớ nên hệ thống không thể đáp ứng được, và bế tắc xảy ra. Ví dụ 3: Trong các ứng dụng cơ sở dữ liệu, một chương trình có thể khoá một vài record mà nó sử dụng để dành quyền điều khiển về cho nó. Nếu tiến trình P1 khoá record R1, tiến trình P2 khoá record R2, và sau đó mỗi tiến trình lại cố gắng khoá record của một tiến trình khác. Bế tắc sẽ xảy ra. Như vậy bế tắc là hiện tượng: Trong hệ thống xuất hiện một tập các tiến trình, mà mỗi tiến trình trong tập này đều chờ được cung cấp tài nguyên, mà tài nguyên đó đang được một tiến trình trong tập này chiếm giữ. Và sự đợi này có thể kéo dài vô hạn nếu không có sự tác động từ bên ngoài. Trong trường hợp của ví dụ 1 ở trên: hai tiến trình P1 và P2 sẽ rơi vào trạng thái bế tắc, nếu không có sự can thiệp của hệ điều hành. Để phá bỏ bế tắc này, hệ điều hành có thể cho tạm dừng tiến trình P1 để thu hồi lại tài nguyên R1, lấy R1 cấp cho tiến trình P2 để P2 hoạt động và kết thúc, sau đó thu hồi cả R1 và R2 từ tiến trình P2 để cấp cho P1 và tái kích hoạt P1 để P1 hoạt động trở lại. Như vậy, sau một khoảng thời gian cả P1 và P2 đều ra khỏi tình trạng bế tắc. Trong trường hợp của ví dụ 2 ở trên: Nếu hai tiến trình này không đồng thời yêu cầu thêm bộ nhớ thì bế tắc không thể xảy ra, hoặc khi cả hai tiến trình đồng thời yêu cầu thêm bộ nhớ thì hệ điều hành phải kiểm tra lượng bộ nhớ còn trống của hệ thống, nếu không đáp ứng cho cả hai tiến trình thì hệ điều hành phải có cơ chế ngăn chặn (từ chối) một tiến trình và chỉ cho một tiến trình được quyền sử dụng bộ nhớ (đáp ứng) thì bế tắc cũng không thể xảy ra. Tuy nhiên để giải quyết vấn đề bế tắc do thiếu bộ nhớ, các hệ điều hành thường sử dụng cơ chế bộ nhớ ảo. Bộ nhớ ảo là một phần quan trọng của hệ điều hành mà chúng ta sẽ khảo sát ở chương Quản lý bộ nhớ của tài liệu này. Khi hệ thống xảy ra bế tắc, nếu hệ điều hành không kịp thời phá bỏ bế tắc thì hệ thống có thể rơi vào tình trạng treo toàn bộ hệ thống. Như trong trường hợp bế tắc ở ví dụ 1, nếu sau đó tiến trình P3 đang giữ tài nguyên R3, cần R2 để tiếp tục thì P3 cũng sẽ rơi vào tập tiến trình bị bế tắc, rồi sau đó, nếu có tiến trình P4 cần tài nguyên R1 và R3 để tiếp tục thì P4 cũng rơi vào tập tiến trình bị bế tắc như P3, … cứ thể dần dần có thể dẫn đến một thời điểm tất cả các tiến trình trong hệ thống đều rơi vào tập tiến trình bế tắc. Và như vậy hệ thống sẽ bị treo hoàn toàn. 1.2 Điềukiệnhìnhthànhbếtắc Năm 1971, Coffman đã đưa ra và chứng tỏ được rằng, nếu hệ thống tồn tại đồngthờibốnđiềukiệnsauđâythìhệthốngsẽxảyrabếtắc: Học viên: Nguyên Văn Việt Đức Trang 4 BáocáoHệtinhọcphântán 1.2.1 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. 1.2.2 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. 1.2.3 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ó. Trong nhiều trường hợp các điều kiện trên là rất cần thiết đối với hệ thống. Sự thực hiện độc quyền là cần thiết để đảm bảo tính đúng đắn của kết quả và tính toán vẹn của dữ liệu (chúng ta đã thấy điều này ở phần tài nguyên găng trên đây). Tương tự, sự ưu tiên không thể thực hiện một cách tuỳ tiện, đặc biệt đối với các tài nguyên có liên quan với nhau, việc giải phóng từ một tiến trình này có thể ảnh hưởng đến kết quả xử lý của các tiến trình khác. Sự bế tắc 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 với ba điều kiện đó. Để chắc chắn bế tắc xảy ra cần phải có điều kiện thứ tư. 1.2.4 Đợi vòng tròn (Circular wait) Đây là trường hợp của ví dụ một 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. Ba điều kiện đầu là điều kiện cần chứ không phải điều kiện đủ để xảy ra bế tắc. Điều kiện thứ tư là kết quả tất yếu từ ba điều kiện đầu. 1.3 Cácphươngphápsửdụngtronghệtậptrungđểxửlýbếtắc: 1.3.1 Phương pháp dự phòng Phương pháp dự phòng đơn giản và thường hay sử dụng là phương pháp các nhóm sắp xếp Havender. Tư tưởng cơ bản của phương pháp này là các tài nguyên được sắp xếp theo các nhóm con C1, C2, …Cn. Một tiến trình nào đó có thể thu hồi tài nguyên của nhóm Ci với i>1, nếu trước đó nó đã thu hồi tất cả các tài nguyên của nhóm cần thiết cho nó C1, C2, …Ci­1. Như thế, trật tự duy nhất của việc thu hồi các tài nguyên được xác định sẽ tránh được bế tắc. Phương pháp này dẫn đến các tiến trình cần thu hồi trước (tạm ứng) các tài nguyên của chúng và do vậy làm giảm khả năng thực hiện song song của hệ. 1.3.2 Phương pháp phát hiện và chữa trị Phương pháp Holt sử dụng một đồ thị trạng thái định hướng mà các nút là các tài nguyên hay các tiến trình. Các cung tiến trình­ tiến trình thể hiện các Học viên: Nguyên Văn Việt Đức Trang 5 ... - tailieumienphi.vn