Đề tài Thiết kế các hệ điều hành phân tán

PHẦN I: TỔNG QUAN VỀ HỆ PHÂN TÁN. HỆ PHÂN TÁN Mở đầu Hệ phân tán là tập hợp nhiều máy tính độc lập kết nối với nhau qua mạng và được cài đặt phần mềm của hệ phân tán. Các phần mềm của hệ phân tán được thiết kế để giúp cho các máy phối hợp hoạt động với nhau, cùng sử dụng những tài nguyên chung của hệ như phần cứng, phần mềm và dữ liệu. Khi sử dụng một hệ phân tán có thiết kế tốt có thể nhận được một tiện ích tính toán thong nhất, ngay cả khi tiện ích đó được sử dụng ở nhiều máy tính đặt ở những vị trí khác nhau. Các hệ phân tán được lắp đặt trên cơ sở các phần cứng với phạm vi khác nhau, từ một số ít trạm làm việc kết nối bằng mạng LAN vào INTERNET, đến tập hợp các mạng LAN và WAN rộng khắp thế giới kết nối hàng triệu máy tính với nhau. Hệ phân tán có phạm vi ứng dụng rất rộng, từ cung cấp các tiện ích tính toán dung cho mục đích chug của nhiều nhóm người sử dụng đến các hệ thống tryền thông đa phương tiện, hệ thống thu ngân ngân hang tự động, và hầu như chúng chứa đựng hầu hết các ứng dụng kỹ thuật và thương mại về máy tính. Hiện nay, chúng ta đã có nhiều nghiên cứu phát triển về thiết kế các hệ điều hành phân tán và những nguyên tắc cơ sở của chùng. Nhiều hệ điều hành phân tán đã ra đời và các ứng dụng của chúng ngày càng có hiệu quả hơn. Những đặc trưng chủ yếu của hệ phân tán Hệ phân tán mang tính hữu dụng là nhờ có đặc tính chủ yếu, đó là: chia sẻ tài nguyên, tính mở, tính đồng thời, tính quy mô, tính chịu lỗi, và tính trong suốt. Trong phần này ta sẽ xét từng đặc tính cụ thể. Cần lưu ý rằng, những đặc tính đó không phải là kết quả tự nhiên của sự phân tán, mà là do thiết kế của hệ thống và phần mềm ứng dụng. Chia sẻ tài nguyên Tài nguyên bao gồm những thành phần phần cứng như: đĩa, máy in, và những thành phần phần mềm như: file, cơ sở dữ liệu và những đối tượng dữ liệu khác.Lợi ích của viêc truy cập vào hệ thống chứa các cơ sở dữ liệu, chương trình, tài liệu vào những thông tin chung khác được thể hiện rõ trong hệ thống chia sẻ thời gian hoặc hệ thống nhiều người sử dụng vào đầu những năm 1960, vào các hệ thống UNIX MultiUser vào những năm 1970. Tài nguyên của máy tính nhiều người dung thường được dùng chung cho tất cả những người sử dụng nó, những người làm việc trong các máy trạm đơn lẻ vào của các máy tính cá nhân không có đặc tính hữu ích này. Các tài nguyên chung trong hệ phân tán được đóng gói vật lý trong một máy tính của hệ, và từ các máy khác chỉ có thể truy cập vào bằng con đường truyền thông. Để dùng chung một cách hiệu quả, tài nguyên phải được quản lý bằng một chương trình cung cấp giao diện truyền thông cho phép truy cập vào tài nguyên chung, sử dụng và cập nhật tài nguyên thường xuyên và chắc chắn. Thuật ngữ quản lý tài nguyên đôi khi dung để biểu thị module phần mềm quản lý những tài nguyên thộc một dạng đặc biệt. Mỗi dạng tài nguyên đòi hỏi có phương thức và biện pháp quản lý riêng, nhưng cũng có những cái chung. Đó là việc cung cấp sơ đồ đặt tên cho mỗi nhóm tài nguyên, giúp truy cập vào các tài nguyên riêng lẻ từ bất kỳ vị trú nào, việc đưa tài nguyên vào địa chỉ truyền thông và việc phối hơp các truy cập đồng thời làm thay đổi trạng thái của các tài nguyên chung, bảo đảm tính nhất quán của chúng. Hệ phân tán gồm tập hợp các quản lý tài nguyên và tập hợp chương trình sử dụng tài nguyên. Những người sử dụng tài nguyên liên lạc với bộ quản lý tài nguyên để truy cập vào tài nguyên chung của hệ. Chúng ta có thể phát triển phối cảnh này để tạo ra 2 mô hình rất thú vị cho các hệ phân tán, mô hình khách-chủ( client-Server model ) và mô hình dựa trên đối tượng (object- based model). Mô hình khách chủ: Hiện nay nó là mô hình nổi tiếng nhất và sử dụng rộng rãi nhất cho các hệ phân tán. Máy chủ có nhiều tiến trình, mỗi tiến trình đóng vai trò là một trình quản lý tài nguyên của nhiều tài nguyên thuộc một dạng nhất định, máy khách ( client ) cũng có nhiều tiến trình, mỗi tiến trình thực hiện một nhiệm vụ, đòi hỏi phải truy cập vào tài nguyên chung mà tiến trình khác quản lý, do đó một só tiến trình vừa là trình khách, vừa là trình chủ. Trong mô hình khách - chủ, tất cả các tài nguyên chung đều được lưu giữ và quản lý bởi các trìh chủ. Trình khách đưa ra yêu cầu cho Server mỗi khi chúng cần truy cập vào một trong những tài nguyên của Server. Nếu yêu cầu hợp lệ, thì Server thực hiện yêu cầu và gửi phúc đáp cho trình khách. Trong mô hình khách chủ mỗi trình chủ có thể coi là nơi cung cấp tập trung tài nguyên mà nó quản lý. Việc cung cấp tài nguyên là bất đắc dĩ trong các hệ phân tán với nhiều lý do. Một trong những lý do đó là sự phân biệt giữa các dịch vụ cung cấp tài nguyên cho client và Server cung cấp dịch vụ đó. Dịch vụ được coi là một thực thể trừu tượng cung cấp từ nhiều trình chủ chạy ở nhiều máy riêng lẻ liên kết qua mạng. Mô hình khách chủ được khai thác rất hiệu quả trong hệ thống hiện nay, chúng có nhiều dịch vụ quản lý các dạng tài nguyên chung khác nhau: thư tín điện tử (email), các thông báo (message ), file, giờ đồng bộ toàn mạng, lưu trữ lên đĩa, máy in, truyền thông diện rộng và thậm chí cả không gian hiển thị cửa sổ trên màn hình các máy nối mạng. Nhưng không thể quản lý và dung chung tất cả các tài nguyên trong hệ phân tán theo cách này. Để hoạt động có hiệu quả hơn, một số loại tài nguyên phụ giữ nguyên tại chỗ của mỗi máy. Bộ nhớ truy cập ngẫu nhiên, bộ xử lý trung tâm và giao diện mạng LAN thường được coi là tập hợp tối thiểu những tài nguyên đó. Những tài nguyên chủ chốt này được quản lý riêng biệt trong hệ điều hành của mỗi máy, chúng chỉ được dùng chung cho các tiến trình trong cùng một máy. Trong một số ứng dụng đòi hỏi sự phối hợp trực tiếp giữa các máy khách, mô hình khách-chủ không đáp ứng được tất cả các yêu cầu, nhưng nó lại đáp ứng được hầu hết các ứng dụng hiện tại và là cơ sở cho các hệ điều hành phát triển mục đích chung. Mô hình dựa trên đối tượng: Mô hình này không giống mô hình lập trình hướng đối tượng truyền thống, ở mô hình lập trình hướng đối tượng truyền thống mỗi thực thể trong chương trình thực hiện đều được coi là một đối tượng có giao diện xử lý thông báo co phép truy cập vào các hoạt động của nó. Còn trong mô hình dựa trên đối tượng dùng cho các hệ phân tán, mỗi tài nguyên chung được coi là một đối tượng. Đối tượng được xác định là duy nhất và di chuyển đến mọi chỗ trên mạng không cần thay đổi tính nhận dạng của chúng. Mỗi khi chương trình dung tài nguyên muốn truy cập vào tài nguyên phải gửu đi thông báo yêu cầu đến đối tượng tương ứng. Thông báo được chuyển đến cho thủ tục hoặc tiến trình thích hựp thực hiện yêu cầu đó và gửi thông báo trả lời cho tiến trình yêu cầu nếu cần thiết. Nó nổi trội hơn ở tính đơn giản và tính linh hoạt. Nó giúp người sử dụng xem xét tài nguyên theo một chá thông nhất. Cũng như trong mô hình khách chủ, các đối tượng có thể đóng vài trò vừa là người sử dụng tài nguyên, vừa là trình quản lý tài nguyên. Tài nguyên mô hình khách chủ, sơ đồ đặt tên dùng cho tài nguyên theo một cách thống nhất. Việc ứng dụng mô hình dựa trên đối tượng làm nảy sinh một số vấn đề khó khăn. Vì các đối tượng bao hàm cả sự biểu diễn trạng thái của chúng, nên để trình quản lý mỗi đối tượng có thể truy cập trạng thái của đối tượng đó, thì nó phải được định vị ở nơi mà đối tượng đó định vị. Điều này thể hiện rất rõ ràng, khi các đối tượng không thể di chuyển tự do chỉ mới ứng dụng trong các hệ thử nghiệm như Arjuna(1989), Clouds và Êmerald (1987 ). Trong mô hình đó các đối tượng được định vị bằng một tập hợp các trình quản lý đối tượng ở dạng tương ứng, và bộ quản lý đối tượng tương ứng được sao chép lại ở vị trí mới mỗi khi có một đối tượng di chuyển. Tính mở Tính mở của hệ thống máy tính là đặc trưng để xác định xem hệ thống có thể mở rộng theo nhiều cấp độ khác nhau hay không. Tính mở hoặc đóng của hệ thống được xét dựa theo khả năng hỗ trợ việc mở rộng của thiết bị phần cứng (ví dụ: bổ sung các thiết bị ngoại vi, bộ nhớ và các giao diện truyền thông ) và hỗ trợ việc mở rộng các phần mềm, như: bổ sung thêm các tính năng của hệ điều hành, các giao thức truyền thông và các dịch vụ chia sẻ tài nguyên. Tính mở của các hệ phân tán được đánh giá theo mức độ bổ sung các dịch vụ chía sẻ tài nguyên mà không phá vỡ hoặc lặp lại các dịch vụ hiện có. Tính mở được thể hiện nhờ những giao diện phần mềm chủ chốt của hệ thống giao diện đó được xác định rõ và lập thành tài liệu sẵn cho những người phát triển phần mềm. Về mặt lịch sử, các hệ máy tính đã từng mang tích chất đóng. Chúng thực hiện các chương trình trong phạm vi các ngôn ngữ lập trình, nhưng không cho phép những người phát triển trình ứng dụng mở rộng ngữ nghĩa để khai thác các phần cứng hoặc các tính năng mới của hệ điều hành. UNIX là hệ thống có thiết kế mang tính mở đầu tiên. Ngôn ngữ lập trình C mà nó cung cấp cho phép người lập trình truy cập vào ttất cả các tài nguyên mà hệ điều hành quản lý. C là ngôn ngữ cấp cao, cho phép các chương trình có thể biên dịch và thực hiện trên nhiều máy tính khác nhau. Việc truy cập tài nguyên của hệ điều hành UNIX được thực hiện thông qua một tập hợp thủ tục gọi là các lời gọi hệ thống, tập hợp thủ tục này được lập thành tài liệu sẵn dùng cho các chương trình viết bằng ngôn ngữ C và những ngôn ngữ khác hỗ trợ các tiện ích theo thủ tục thông thường. Khi có một thiết bị ngoại vi mới được cài đặt vào UNIX, hệ điều hành có thể được mở rộng để giúp cho các chương trình ứng dụng có thể truy cập được tới thiết bị này bằng việc bổ sung thêm các lời gọi hệ thống mới hoặc phổ biến hơn là bằng việc cài đặt một số giá trị tham số bổ sung cho các lời gọi hệ thống hiện có. So với các hệ thống trước, UNIX có tích chất mở hơn vì : Đối với những người phát triển ứng dụng : chúng có thể truy cập tới toàn bộ những tiện ích mà hệ thống cung cấp. Đối với những người cung cấp phần cứng và những người quản lý hệ thống: hệ điều hành có thể mở rộng để bổ sung các thiết bị ngoại vi mới hoặc trình điều khiển mạng tương đối dễ dàng. Đối với người bán phần mềm và người sử dụng: Do hệ điều hành không phụ thộc phần cứng, nên những người phát triển phần mềm có thể tạo ra những chương trình chạ được ở nhiều máy thuộc các hãn sản xuất khác nhau, mà không cần thay đổi gì. (Điều này chỉ đúng khi các nhà sản xuất máy tính thống nhất hoàn toàn về phiên bản UNIX mà họ sẽ cung cấp). Tính mở thông qua truyền thông: Những tài nguyên mà lõi của UNIX đầu tiên cung cấp là file và tiến trình. File với cấu trúc đặt tên của chúng rất hữu dụng cho việc lưu trữ cố định và chúng còn được dung để truy cập trực tiếp vào một số loại thiết bị ngoại vi khác. Các tiến trình cung cấp cơ chế thực hiện đồng thời các chương trình. Tính sẵn dùng của truyền thông giữa các tiến trình trong UNIX và các hệ điều hành khác cùng tính sẵn dụng của các giao thức chuẩn trong truyền thông đã mở ra nhiều cơ hội để đạt được tính mở trong thiết kế hệ thống máy tính. Nhờ đó, các tiến trình chủ chạy được ở bất kỳ máy nào, bất kỳ hệ điều hành nào. Tính đồng thời Khi một số tiến trình cùng tồn tại trong một máy tính, ta nói rằng, chúng được thực hiện đồng thời. Nếu máy tính chỉ có một bộ xử lý trung tâm, thì tính đồng thời xảy ra khi thực hiện xen kẽ, các phần của một tiến trình. Nếu máy có n bộ xử lý thì sẽ có n tiến trình được thực hiện đồng thời, tăng hiệu xuất tính toán lên n lần. Trong hệ phân tán thường có nhiều máy, mỗi máy co một hoặc nhiều bộ xử lý trung tâm. Nếu có m máy, mỗi máy có một bộ xử lý trung tâm, thì sẽ có tới m tiến trình chạy song song, miễn là các tiến trình định vị ở các máy khác nhau. Hệ phân tán dựa trên mô hình chia sẻ tài nguyên như mô tả ở trên có nhiều cơ hội để thực hiện song song với 2 lý do: Nhiều người sử dụng đồng thời gọi tới lệnh hoặc tương tác với các chương trình ứng dụng. Nhiều trình chủ chạy đồng thời, mỗi trình chủ đáp ứng với yêu cầu mà trình khách đưa ra. Trường hợp một xuất hiện do một hoặc nhiều tiến trình ứng dụng đang chạy đại diện cho một người sử dụng đang hoạt động. Trong phần lớn các kiến trúc của hệ phân tán, các tiến trình ứng dụng chạy trong trạm làm việc của người sử dụng và chúng không xung đột với tiến trình ứng dụng của những người sử dụng khác để xử lý tài nguyên. Nếu trạm làm việc chỉ có một bộ xử lý nhưng có nhiều tiến trình ứng dụng, thì các tiến trình đó được thực hiện theo cách xen kẽ. Trạm làm việc có nhiều bộ xử lý cho phép người sử dụng thực hiện các phép tính một cách song song hoặc cho phép thực hiện các trình ứng dụng có khả năng khai thác nhiều bộ xử lý. Trường hơp 2: là nảy sinh do mỗi loại tài nguyên đều có một hoặc nhiều tiến trình chủ. Các tiến trình chủ được xử lý song song với nhau và với các tiến trình khách đang chạy trên các trạm làm việc. Những yêu cầu truy cập tài nguyên của một Server và được giải quyết một cách tuần tự hoặcgiải quyết đông thời một số yêu cầu bằng tiến trình quản lý tài nguyên. Khi một số chương trình sử dụng tài nguyên đồng thời truy cập cùng một tài nguyên, thì trình chủ phải đông bộ hoá các hoạt động của chúng, để chúng không xung đột với nhau.Việc đồng bộ hoá phải được lập kế hoạch cẩn thận, không làm mất đi tính hữu ích của việc thực hiện đồng thời. Tóm lại tính đồng thời náy sinh một cách tự nhiên trong các hệ phân tán, xuất phát từ các hoạt động riêng biệt của người sử dụng, tính độc lập của tài nguyên và vị trí của các trình chủ nằm ở các máy khác nhau. Sự tách biệt của các hoạt động cho phép việc xử lý được tiến hành song song ở các máy khác nhau. Việc truy cập đồng thời và cập nhật tài nguyên chung phải được đồng bộ hoá. Tính quy mô Hệ phân tán hoạt động hiệu quả ở nhiều quy mô khác nhau. Hệ phân tán nhỏ nhất chỉ gồm 2 trạm làm việc và một file Server, trong khi đó hệ phân tán xây dựng từ một mạng LAN có thể bao gồm vài trăm trạm làm việc và một số file Server, print Server và các Server có mục đích đặc biệt khác nhau. Một số mạng LAN thường được kết nối với nhau thành các liên mạng và liên mạng có thể bao gồm hàng nghìn máy, nhưng chúng chỉ tạo thành một hệ phân tán nhờ khả năng chia sẻ tài nguyên của chúng. Phần mềm hệ thống và phần mềm ứng dụng không cần thay đổi khi quy mô của hệ thống tăng lên. Đặc tính này có được nhờ khả năng mở rộng của hầu hết các hệ phân tán hiện nay và các thành phần của chúng. Tuy nhiên, cần có những nghiên cứu sâu hơn về lĩnh vực này trong sự phát triển các hệ thống và các phần mềm có quy mô rất rộng, hoặc khi xuất hiện các mạng hiệu suất cao. Nhu cầu về tính quy mô không chỉ là vấn đề của phần cứng hay hoạt động của mạng. Vấn đề này sẽ xuyên suốt toàn bộ các mặt thiết kể của hệ phân tán. Trong các hệ máy tính tập trung, những tài nguyên chung cố định như bộ nhớ, bộ xử lý, kênh vào ra, đều thuộc tài nguyên cung cấp hạn chế và không thể thay thế một cách vô định. Hệ phân tán không bị hạn chế về vấn đề đó vì chúng có tiềm năng không hạn chế về số máy tính, mỗi máy đều có bộ nhớ, có một hoặc nhiều bộ xử lý trung tâm và kênh vào ra. Nhưng chúng có thể có hạn chế khác nếu thiết kế của hệ thống không nhận thấy rõ nhu cầu về tính quy mô. Yêu cầu về tính quy mô trong các hệ phân tán đòi hỏi một thiết kế mà trong đó không có tài nguyên nào (phần cứng hoặc phần mềm) bị coi là tài nguyên cung cấp hạn chế. Như vậy phải mở rộng hệ thống để đáp ứng yêu cầu phát triển tài nguyên. Có thể phải bổ sung các Server để tránh tình trạng tắc nghẽn xảy ra khi một file Server phải xử lý tất cả các yêu cầu truy cập file. Một số file có thể được truy cập thường xuyên đến mức chỉ xử lý những yêu cầu truy cập file cũng có thể gây ra tắc nghẽn. Trong trường hợp đó, các file phải được sao chép lạị ở nhiều Server và hệ thống phải được thiết kế để sao cho khi các file sao chép được cập nhật thì cập nhật đó được áp dụng cho toàn bộ các bản sao. Khi quy mô và độ phức tạp của mạng máy tính tăng lên, thì thách thức chủ yếu là việc thiết kế các phần mềm hệ phân tán có hiệu lực đối với các cấu hình mới của mạng. Hiện nay, Internet đã kết nối hàng triệu máy tính. Yêu cầu là phải thiết kế những dịch vụ phân tán có khả năng hoạt động hiệu quả với hàng nghìn hoặc hàng triệu khách hàng. Việc xử lý bất kỳ yêu cầu truy cập nguồn tài nguyên chung nào cũng cần phải độc lập, gần như không phụ thuộc vào kích cỡ của mạng. Tính chịu lỗi Các hệ máy tính đôi khi vẫn bị hỏng. Khi phần cứng hoặc phần mềm xuất hiện hư hỏng, các chương trình sẽ cho kết quả sai, hoặc bị dừng trước khi hoàn thành phép xử lý đã định. Các thiết kế của các hệ máy tính chịu lỗi hiện nay thường sử dụng các phương pháp sau: Dùng dư phần cứng (hardware redundancy): sử dụng các thành phần dư để khác phục lỗi. Khôi phục bằng phần mềm: thiết kế các phần mềm sử dụng. Để tăng khả năng của các hệ thống có khả năng chịu lỗi bằng phần cứng, người ta thường sử dụng hai máy cho một ứng dụng, một trong hai máy đóng vai trò là máy dự phòng cho 2 máy kia. Đây là giải pháp khá tốn kém để có thể cung cấp gấp đôi phần cứng, giá thành sẽ tăng gấp đôi. Trong các hệ phân tán, phần dư dự trữ như vậy có rất ít chỉ những Server dạng riêng lẻ cần thiết cho việc hoạt động của các ứng dụng quan trọng mới thường có phần dư để có thể thay thế. Một điểm cần lưư ý là cần phải thiết kế việc cấp phát phần cứng dư, sao cho phần cứng khác có thể khai thác được cho các hoạt động tới hạn, không nguy kịch (non critical) những lúc không bị lỗi. Ví dụ, có thể thay thế cơ sở dữ liệu trong một số Server để bảo đảm có thể truy cập được sau khi bị lỗi ở bất kì Server nào. Các Server được thiết kế để phát hiện lỗi ở cấp của chúng: Mỗi khi phát hiện thấy lỗi ở một Server, các khách hàng sẽ được chỉ những Server còn lại. Vớí những kỹ thuật này, các hệ phân tán có khả năng chịu được của một số loại lỗi phần cứng với giá thành tương đối thấp. Việc khôi phục lỗi bằng phần mềm đòi hỏi thiết kế phần mềm, sao cho chúng có thể phục hồi được của trạng thái dữ liệu thường có khi thấy lỗi. Nói chung các phép xử lý của chương trình sẽ thực hiện không hoàn tất khi có lỗi, và dữ liệu mà đang dùng chưa được cập nhật (file và các dữ liệu lưu thường xuyên lâu dài) không còn ở trạng thái nhất quán nữa. trong phần sau sẽ mô tả một cách số cơ chế làm cho file và các dữ liệu lâu dài khác có thể tái lưu lại trạng thái ban đầu của chúng. Các hệ phân tán có tính sẵn dùng cao, mặc dù có các lỗi phần cứng. Tính sẵn dùng của hệ thống là phép đo tỉ lệ thời gian mà chúng sẵn sàng cho sử dụng. Một lỗi trong hệ thống máy tính đa người dùng thường dẫn đến việc hệ thống không sẵn sàng cho tất cả những người sử dụng nó. Khi một trong các thành phần của hệ thống phân tán bị lỗi, thì chỉ hành động đó ảnh hưởng. Người sử dụng có thể di chuyển đến trạm làm việc mới nếu trạm của họ bị hỏng, tiến trình của một Server cũng có thể khởi động lại được ở máy tính khác. Trong các mạng thành phần của hệ phân tán thường không có phần dư, do đó lỗi của mạng sẽ làm cho các chương trình sử dụng mạng phải cho tạm dừng cho đến khi khôi phục lại thông tin, làm gián đoạn các dịch vụ của người sử dụng. Sự quá tải của mạng làm suy thái các hoạt động và làm cho các hoạt động của mạng trở nên không trong cậy. Do đó, người ta thường cố gắng những mạng tin cậy và chịu lỗi. Để đáp ứng các yêu cầu thực tế, cần phải thiết kế các phần mềm đặc biệt để xử lý tính năng đồng thời một cách đầy đủ và có khả năng chịu lỗi cao hơn so với hệ khách chủ thông thường. Mô hình lý tưởng dể xây dựng các chương trình đồng thời liên quan đến việc thay thế là mô hình nhóm tiến trình. Mô hình này giúp cho nhiều tiến trình đồng thời hợp tác với nhau bằng cách có chung một cơ chế thông tin “mạng máy tính thực” gồm một tập hợp những tiến trình có thể được tạo lập, mở rộng hoặc thu nhỏ kích cỡ theo yêu cầu. Tính trong suốt Tính trong suốt chính là việc che dấu không cho người sử dụng hoặc người lập trình ứng dụng thấy sự tách biệt giữa các thành phần trong hệ phân tán, và như vậy người sử dụng chỉ thấy hệ phân tán như một tổng thể, chứ không phải là tập hợp các thành phần độc lập. Tính trong suốt có ảnh hưởng lớn đến thiết kế các phần mềm của hệ phân tán. Sự tách biệt giữa các thành phần là một đặc tính cố hữư của các hệ phân tán. Sổ tay tra cứu của ANSA (ANSA 1989) và mô hình tham khảo của tổ chức tiêu chuẩn quốc tế về xử lý phân tán mở RM-ODP (ISO 1992) đã định rõ 8 dạng của tính trong suốt đó là: Truy cập trong suốt: cho phép truy cập vào các đối tượng thông tin cục bộ và các thông tin từ xa sử dụng các thao tác thống nhất. Định vị trong suốt: cho phép các đối tượng thông tin có thể truy cập, mà không cần biết đến vị trí của nó. Tính tương tranh: Cho phép một số tiến trình hoạt động đồng thời sử dụng những đối tượng thông tin chung mà không gây trở ngại cho nhau. Thay thế trong suốt: Cho phép sử dụng thường xuyên nhiều đối tượng thông tin để tăng độ tin cậy và hiệu suất hoạt động, không cần biết các thay thế mà người sử dụng thực hiện hay các chương trình ứng dụng thực hiện. Lỗi trong suốt: giúp che dấu các lỗi, cho phép người sử dụng và các chương trình ứng dụng hoàn tất công việc của mình mặc dù có lỗi ở các thành phần phần cứng hoặc phần mềm. Tính trong suốt di trú: Cho phép các đối tượng thông tin di chuyển trong hệ thống mà không ảnh hưởng đến hoạt động của người sử dụng hoặc các chương trình ứng dụng. Thực hiện trong suốt: Cho phép cấu hình lại hệ thống để cải tiến việc thực hiện, khi lượng nạp thay đổi. Tính quy mô trong suốt: Cho phép mở rộng hệ thống và các ứng dụng không cần thay đổi cấu trúc hệ thống hay các thuật toán ứng dụng. Hai thuộc tính trong suốt quan trọng nhất là: Truy cập trong suốt và định vị trong suốt. Đôi khi chúng được xem là tính trong suốt của mạng. Tính trong suốt của mạng cung cấp mức độ che dấu tài nguyên tương tự như trong các hệ tập trung. Một số kết luận Hệ phân tán đã trở thành điển hình về tổ chức các tiện ích tính toán. Chúng được dùng để khai thác các hệ máy tính tương tác lẫn nhau vì mục đích chung theo kiểu UNIX, khai thác các ứng dụng thương mại và công nghiệp của các máy tính ở một phạm vi lớn. Chúng càng ngày càng được sử dụng nhiều hơn, làm cơ sở cho các ứng dụng mới trong các lĩnh vực như: các dịch vụ thông tin nối mạng và các ứng dụng đa phương tiện, trong đó việc truyên thông là một yêu cầu cơ bản Vấn đề phối hợp thời gian trong hệ phân tán Một số khái niệm Thời gian là một vấn đề thú vị và quan trọng và thú vị trong hệ phân tán, nó là một đại lượng mà ta luôn luôn đo được chính xác. Muốn biết biến cố đã xẩy ra ở thời điểm nào đó. Việc này được gọi là đồng bộ hoá ngoài. Nếu đồng hồ trong các máy tính được đồng bộ hoá lẫn nhau theo một mức độ chính xác nhất định, thì sẽ đo được khoảng thời gian giữa hai biến cố xảy ra ở hai máy khác nhau, căn cứ theo đồng hồ tại chỗ của chúng: điều này được gọi là đồng bộ hoá trong. Khi các máy được đồng bộ hoá trong thì không cần đồng bộ hoá ngoài, ví chúng có thể bị lệch so với thời gian bên ngoài. Cần chú ý là nhiều thuật toán dựa trên đồng bộ hoá đồng hồ để giải quyết những vấn đề phân tán như: vấn đề duy trì tính nhất quán của dữ liệu phân tán(ví dụ sử dụng nhãn thời gian để sắp xếp thứ tự các giao dịch), vấn đề kiểm tra tính xác thực của các yêu cầu gửi đến máy chủ (như trong giao thức xác nhận tính xác thực-kerberos) dựa vào các đồng hồ đồng bộ hoá, vấn đề không xử lý những gì được cập nhật hai lần... Khái niệm thời gian vật lý vẫn còn là một vấn đề cần bàn trong hệ phân tán. Vấn đề không phải là do hiệu ứng không đáng kể của tính tưng đối trong máy tính thường( trừ khi tính đến cả những máy đang di chuyển trên tàu vũ trụ), mà là các vấn đề liên quan đến khả năng hạn chế trong việc truyền thông tin từ máy này đến máy khác. Bởi vì, trong phần lớn các trường hợp, đồng hồ ở các máy khác nhau chỉ có thể đồng bộ hoá bằng con đường truyền thông mạng. Thông báo truyền đi bị hạn chế bởi tốc độ, nhưng điều đó không quan trọng nếu ta biết việc chuyển thông báo mất bao nhiêu thời gian. Vấn đề là ở chỗ ta không thể đoán biết được thời gian cần để gửi thông báo đi. Phần sau nêu những phưng pháp đồng bộ hoá xấp xỉ các đồng hồ máy tính bằng cách chuyển thông báo. Song trong nhiều trường hợp vẫn không thể xác định chính xác trật tự của các biến cố ở các máy khác nhau, Một điều may mắn là chúng ta có thể xác lập trật tự của mọt số biến cố căn cứ theo luồng giữ liệu giữa các tiến trình trong hệ phân tán. Trong phần này xem xét đến những đồng hồ logic dùng để xác định trật tự biến cố không cần đo thời gian vật lý mà chúng xẩy ra. Đồng bộ hoá các đồng hồ vật lý Mỗi máy đều có một đồng hồ vật lý riêng: đó là một thiết bị điện tử đếm số dao động trong tinh thể với tần số xác định, và chỉ số giao động đếm được, đồng thời lưu kết quả vào thanh ghi đếm. Có thể lập trình cho đồng hồ để tạo ra những quãng ngắt đều đặn, tuy nhiên ta sẽ không đi sâu vào phương tiện hoạt động này. Có thể đọc đồng hồ bằng phần mềm và có giá trị đọc được này dùng để dán nhãn thời gian cho bất cứ biến cố nào của tiến trình thực hiện ở máy này. ở đây ta hiểu “biến cố” là hoạt động đột nhiên xảy ra không chia tách được- như gửi hoặc nhận thông báo. Các biến cố kế tiếp nhau chỉ tương ứng với các nhãn thời gian khác nhau nếu độ phân giải của đồng hồ( quãng thời gian giữa lần cập nhật cho thanh ghi giờ) nhỏ hơn tốc độ xẩy ra biến cố. Trong những ứng dụng, chỉ cần quan tâm đến trật tự biến cố, chứ không cần qua tâm đến thời gian tuyệt đối mà biến cố xẩy ra, tức là, chỉ đòi hỏi giá trị trong bộ đếm để dán nhãn cho biến cố. Tuy nhiên có thể tính được cả ngày và thời gian trong ngày từ giá trị của bộ đếm, miễn là đã biết một vái giá trị thời gian gần đây của bộ đếm. Độ lệch giờ: Đồng hồ tinh thể trong máy tính, cũng như các đồng hồ khác, đều bị lệch giờ, tức là chúng ta đếm giờ với tốc độ khác nhau và do đó lệch nhau. Những thiết kế hiện có đều cố gắng khắc phục sự biến đổi này, nhưng vẫn không triệt để. Sự khác biệt về chu kỳ dao động sẽ dấn đến khác biệt rõ ràng trong thanh ghi đếm mà hai đồng hồ ghi được, dù chúng khởi động cùng giá trị. Độ lệch giờ chính là sự thay đổi từng đối giữa một đồng hồ với đồng hồ tham chiếu trong một đn vị thời gian của đồng hồ tham chiếu. Trong những đồng hồ tinh thể Quartz, độ lệch này khong 10-6 tức là cứ 1.000.000 giây hay 11,6 ngày thì lệch 1 giây. Phối hợp thời gian toàn cầu: Nững đồng hồ vật lý nối tiếp chính xác nhất đều dùng bộ tạo giao động nguyên tử, độ chính xác của chúng khong 10-13. Đầu ra của đồng hồ nguyên tử được dùng để làm chuẩn cho thời gian thực, gọi là thời gian nguyên tử quốc tế. Từ năm 1967, một giây chuẩn được xác định là 9.192.631.770 chu kỳ dịch chuyển giữa hai mức trạng thái siêu mịn của caseium-133. Thời gian phối hợp toàn cầu ( viết tắt là UTP ) là một tiêu chuẩn quốc tế dựa trên thời gian nguyên tử, nhưng dôi khi phi chèn thêm hoặc xoá di một giây dể bằng với thời gian thiên văn.Tín hiệu UTC được dồng bộ hoá và truyền qung bá thường xuyên từ các dài radio mặt dất và vệ tinh trên khắp thề giới.Ví dụ, ở Mỹ, đài radio WWV phát tín hiệu thời gian trên một tần số sóng ngắn. Các nguồn vệ tinh gồm có vệ tinh môi trường hoạt động địa tĩnh (GOES) và hệ thống định vị toàn cầu (GPS Global Positioning System). Sóng radio có tồc độ gần bằng tốc độ ánh sáng (3 108 m/s ), vì vậy trễ truyền chúng khá bé.Ví dụ, thời gian để truyền thời gian suốt dọc chiều dài nước Mỹ (khoảng 1000km ) chỉ mất khong 3 miligiây. Trễ truyền dẫn có thể tính được nếu biết chính xác tốc độ chuyền tín hiệu radio và khoảng cách từ nguồn. Rủi thay tốc độ truyền lại thay đổi theo điều kiện khí quuyển và do đó làm tang sai số. Nói chung, sự chính xác của tín hiệu thu được là mọt hàm bao gồm cả sự chính xác của nguồn, và khoảng cách của nguồn qua khí quyển. Đài thu có sẵn trên thị trường. So sánh với UTC “hoàn hảo”, tín hiệu thu được từ các đài mặt đất có độ chính xác từ 0, 1-10 miligiây, tuỳ theo vị trí của đài. Tín hiệu thu từ vệ tinh GOES có độ chính xác khoảng 0,1 miligiay. Những máycó đài thu gắn liền có thể đồng bộ các đồng hồ của chúng với những tín hiệu thời gian này. Đáng tiếc là đài thu đắt tiền hơn so với trạm làm việc đặc biệt là những đài thu dùng để đồng bộ hoá với nguồn thời gian vệ tinh. Cần chú ý rằng: độ đo thời gian có độ chính xác 10 miligiây rất hạn chế trong việc cho biết chật tự từng đối của biến cố xẩy ra ở nhiều máy khác nhau trong hệ phân tán. Trong 10 miligiay với bộ sử lý tôc độ10 triệu lệnh/giâycó thể thục hiện 100000 lệnh, và thời gian đó có thể chuyển đưc một số thông báo ngắn. Bù vì lệch giờ: Nếu thời gian nhận được từ một dịch vụ thời gian (chẳng hạn dịch vụ tín hiệu thời gian phối hợp toàn cầu ), lớn hơn thời gian của máy cần đồng bộ, thì chỉ cần để đồng hồ trong máy bằng thời gian của dịch vụ, bởi vì làm như vậy sẽ gây ra sự đo lộn những ứng dụng dựa trên giả thuyết là thời gian luôn tăng. Giải pháp cho trường hợp này không phải là chỉnh lại đồng bộ, mà là làm cho nó chạy chậm hơn trong các chu kỳ tiếp theo, cho đến khi nó phù hợp với thời gian cập nhật cho các ứng dụng bằng phần mềm, mà không cần thay dổi tốc độ của đồng hồ phần cứng (một việc không phải lúc nào cũng làm được với các đồng hồ phần cứng). Ta gọi thời gian cung cấp cho các ứng dụng (số ghi của đồng hồ phần mềm) là S và thời gian trong đồng hồ phần cứng là H. Giả sử hệ số bù là d, như vậy S(t)=H(t) + d(t) (*). Dạng đơn giản nhất để d làm cho S thay đổi liên tục là: d làm hàm tuyến tính của đồng hồ phần cứng: d(t)=aH(t)=b, trong đó a và b là những hằng số tìm được. Khi đó, thay thế giá trị của d vao biểu thức (*) ta có: S(t)= (1+ a) H(t) +b Giả sử giá trị của đồng hồ phần mềm là Tskew khi H=h, giả sử thời gian thực tế ở thời điểm đó là Treal. Ta có Tskew > Treal hoặc Tsaw <Treal. Nếu S cho biết thời gian thực tế sau N tích tắc tiếp theo, ta sẽ có: Tsew = (1+a)h+b và Treal + N=(1+a)(h+N)+b Giải phươg trình ta có: a = (Treal - Tsew)/N và b = Tsew-(1+a)h. Phương pháp đồng bộ hoá đồng hồ của Christian : một cách khác để đồng bộ hoá giữa các máy trong hệ phân tán là để tiến trình dịch vụ thời gian trung tâm cung cấp thời gian theo đồng hồ của nó vào lúc có yêu cầu, như trong hình 1.4. Máy cung câp dịch vụ thời gian có thể lắp thêm một máy thu phù hợp để đồng hồ bộ hoá với UTC. Nếu một tiến trình P yêu cầu thời gian trong thông báo mn, và nhận được giá trị thời gian T trong thông báo mt, thì theo nguyên tắc, nó có thể chỉnh đồng hồ ở thời gian t + Ttrans, trong đó Ttrans là thời gian chuyển mt từ S - P (t được chèn vào mt vào điểm cuối trước khi truyền từ máy S ). Điều không may là Ttrans là đại lượng biến đổi : nó phụ thuộc vào số lượng các tiến trình khác đang cạnh tranh với S và P về tài nguyên trong mỗi máy, và những thông báo khác cạnh tranh với mt về mạng. nói chung, các tham số này không thể dự đoán và thực tế không thể đo chính xác trong các cài đặt. Nói chung, ta có thể xem Ttrans = min + x, trong đó x>= 0. Giá trí nhỏ nhất min chỉ có thể có được nếu không có tiến trình khác thực hiện và không có giao thông mạng nào khác diễn ra, min có thể đo được hoặc ước lượng được. Giá trị x trong trường hợp cụ thể không nhận biết được, mặc dù có thể đo các giá trị phân tán cho một cài đặt cụ thể. Cristian đề xuất sử dụng dịch vụ thời gian nối với thiết bị thu tín hiệu UTC để đồng bộ hoá các máy tính. Việc đồng bộ hoá giữa dịch vụ thời gian và đài thu UTC của nó có thể thực hiện bằng phương pháp tương tự như thủ tục đồng bộ hoá giữa các máy tính. Tiến trình P muốn biết thời gian của S có thể ghi lại tổng thời gian round-trip Tround (thời gian từ khi gửi yêu cầu mr và nhận phúc đáp mt ) nó có thể đo thời gian này với mức độ chình xác hợp lý nếu như độ lệch đồng hồ của nó khá nhỏ.Ví dụ, thời gian round-trip là trong khoảng 1-10 miligiây trên LAN, trong thời gian đó một đồng hồ bị lệch 10-6 chỉ khác biệt đi nhiều nhất là 10-5 miligiây. Giả sử thời gian trở về trong thông báo mt của S là t. Một ước lượng đơn giản về thời gian mà P phải chỉnh đồng hồ là t + Tround/ 2. Gi sử rằng thời gian giữa việc gửi thông báo mr và thời gian nhận thông báo mt tương ứng là min + x và min+ y. Nếu giá trị min đã biết hoặc có thể ước lượng gần đúng, thì ta có thể xác định độ chính xác của kết quả có được theo lập luận sau: Thời điểm sớm nhất mà S có thể đưa giá trị thời gian vào trong mt là min, sau khi P gủi mr đi. Thời điểm muộn nhất mà nó thưc hiện xong là min, trước khi mt đến P. Do đó,thời gian thông báo phúc đáp đến nơi tính theo đồng hồ của S là nằm trong khoảng [t + min, t+ Tround - min]. Độ rộng của khoảng này là Tround- 2*min, do đó độ chính xác là (Tround- 2*min). Sự biến đổi có liên quan đến việc mở rộng một số yêu cầu cho T và lấy giá trị nhỏ nhất của Tround để ước lượng với độ chính xác cao nhất. Độ chính xác của các yêu cầu càng lớn, thì khả năng thực hiện được nó càng nhỏ. Bởi vì những kết qu chính xác nhất chỉ có thể có được khi chuyển các thông báovào thời gian gần min nhất- tức là biến cố không thể xẩy ra khi mạng đang bận. Thuật toán của Christian: Như đã nói trên, phương pháp của cristian còn phải nghiên cứu đến trường hợp tất cả các dịch vụ được thực hiện bởi một máy chủ, mà dịch vụ thời gian của nó bị hỏng dẫn tới việc không thể đồng bộ hoá tạm thời. Christian đưa ra giải pháp cung cấp thời gian bằng một nhóm dịch vụ thời gian đã được đồng bộ hoá, mỗi dịch vụ có một máy thu các tín hiệu thời gian UTC. Ví dụ, một khách hàng có thể gửi yêu cầu đến mọi Server và chỉ sử dụng phúc đáp nào nhận được đầu tiên. Nếu dịch vụ thời gian bị trục trặc thì nó sẽ phúc đáp với giá trị thời gian không xác thực, điều này có thể gây ra nỗi tiến trình: trong hệ máy tính. Marzullo(1984) đã tìm được phương pháp phân biệt những dịch vụ tốt với những dịch vụ cho thời gian không xác thực, miễn là những dịch vụ không xác thực đó chỉ là thiểu số (không vượt quá 1/3 tổng số các dịch vụ ). Vấn đề liên quan đến đồng hồ hỏng được xử lý từng phần bằng thuật toán Berkeley mô tả dưới đây. Vấn đề đồng bộ hoá thời gian, được xử lý bằng các kĩ thuật xác nhận. Một Server kỹ thuật xác nhận về phía mình, cũng phụ thuộc vào độ chính xác của việc đồng bộ hoá. Thuật toán Berkeley: Guslla và Zatti (1989) mô tả thuật toán đồng bộ hoá bên trong dùng cho những máy chạy UNIX Berkeley. Theo thuật toán, máy điều vận (coodinator computer) được chọn làm máy chủ (master). Không giống như giao thức của Cristian, máy này thăm dò định kì những máy khác có đồng hồ được đồng bộ hoá (gọi là các slave). các máy slave gửi các giá trị đồng hồ của chúng cho máy chủ, máy chủ ước tính đồng hồ thời gian tại chỗ của nó, bằng cách quan sát thời gian round-trip (tưng tự như kỹ thuật của Cristian ) và nó tính đến giá trị trung bình của các giá trị nhận được (kể c đọc giờ tại chỗ của nó ). Server cân bằng các khả năng chính là ở chỗ giá trị trung bình này đã chặn ngang xu hướng chạy nhanh hoặc chậm của các đồng hồ. Độ chính xác của giao thức phụ thuộc vào thời gian round-trip lớn nhất đã nhận được giữa máy chủ và máy slave. Máy chủ ngăn ngừa mọi trường hợp đọc thời gian lớn hơn giá trị lớn nhất đã nhận ra này. Thay vì gửi thời gian cập nhật mới nhất cho những máy khác( những máy này có thể báo thời gian không chắc chắn do thời gian chuyển trường hợp thông báo) - máy chủ sẽ gửi giá trị thời gian mà đồng hồ trong mỗi máy slave yêu cầu điều chỉnh. Giá trị thời gian này có thể dương hoặc âm. Thuật toán nhằm loại bỏ kết quả đọc ở những đồng hồ chạy lệch qua nhiều, những đồng hồ hỏng và loại bỏ kết quả đọc không xác thực. Máy chủ chỉ tính giá trị trung bình của những đồng hồ không lệch nhau quá một lượng thời gian xác định nào đó. Gusella và Zatti đã thí nghiện trên 15 máy tính có đồng hồ đồng bộ hoá trong khoảng 20->25 miligiây sử dụng giao trường hợp phức của chúng. Mức lệch tại chỗ của các đồng hồ đo được nhỏ hơn 2x10-5và thời gian round-trip tối đa là 10 miligiây. Thời gian logic và đồng hồ logic Trong trường hợp máy chủ bị hỏng, một máy khác sẽ được chọn để thực hiện chức năng của máy đó. Trong phần sau sẽ mô tả một số thuật toán dùng cho việc lựa chọn máy chủ thay thế nói trên, tuy nhiên các thuật toán này không bảo đảm được chọn được máy chủ mới trong thời gian tới hạn. Giao thức thời gian mạng: (NTP) NTP là một kiến trúc cho dịch vụ thời gian và là một giao thức để phân tán các thông tin về thời gian trên nhiều mạng liên kết. NTP được thừa nhận như là một tiêu chuẩn để đòng bộ hóa đồng hồ trên Internet. Thiết kế NTP nhằm thực hiện các mục đích sau: Cung cấp các dịch vụ giúp các khách hàng trên Internet đồng bộ hóa chính xác theo UTC, dù có thể gặp giá trị trễ lớn hoặc trễ biến đổi trong truyền thông Internet. NTP áp dụng kỹ thuật thống kê để lọc giữ liệu thời gian và phân biệt chất lượng giữ liệu thời gian với các server khác. Cung cấp các dịch vụ tin cậy, tránh bị mất kết nối lâu dài: Cần có những server dư và đường dẫn dư giữa các server. Các server có thể cấu hình lại để vẫn cung cấp được dịch vụ nếu một trong số chúng không dùng được. Giúp các client (máy khác) tái đồng bộ hóa một cách thường xuyên và hiệu quả, nhằm điều chỉnh tốc độ lệch trong hầu hết các máy tính. Dịch vụ được thiết kế phục vụ cho số lượng lớn các client và server. Để bảo vệ dịch vụ thời gian, không cho chỉnh lại dịch vụ thời gian các dịch vụ thời gian luôn sử dụng các kỹ thuật xác nhận để kiểm tra dữ liệu thời gian từ các nguồn ủy thác yêu cầu và xác nhận địa chỉ gửi thông báo cho nó. Dich vụ giao thức thời gian mạng được cung cấp bởi mạng cáacServer định vị qua Internet. Các Server quan trọng nhất được kết nối trực tiếp tới nguồn thời gian như máy thu thời gian UTC. Các Server phụ được đồng bộ hóa dựa trên Server thứ nhất. Các Server được kết nối theo thứ bậc logic gọi là mạng con đồng bộ (hình 1.5), các cấp được gọi là “giai tầng”. Server chủ chiếm giai tầng 1: chính là gốc của cây. Các Server giai tầng 2 là dịch vụ phụ, chúng được đồng bộ hóa trực tiếp từ Server chủ, các Server giai tầng 2 được đồng bộ hóa dựa trên Server giai tầng 1, và tiếp tục như vậy cho các mức thấp hơn Server mức thấp được Server Server thấp nhất được thực hiện trong các trạm của người Server sử dụng. Các đồng hồ có quan hệ với các Server có Server số hiệu giai tầng cao có khả năng không chính xác bằng các đồng hồ có quan hệ với các dịch vụ có Server số hiệu giai tầng thấp hơn, do lỗi này sinh ở các mức đồng bộ. NTP cũng tính đến tổng thời gian trễ thông báo round-trip tới gốc trong việc đánh giá chất lượng của dữ liệu đồng hồ, được cất giữ trong các dịch vụ riêng biệt. 3 2 1 3 3 2 Hình I.1 Một mạng con đồng bộ hóa đơn giản Server sử dụng trong cài đặt NTP (hướng mũi tên chỉ hướng điều khiển đồng bộ, các Server biểu thị các cấp) Mạng con đồng bộ hóa cũng có thể cấu hình lại như trong trường hợp các dịch vụ bị lỗi. Nếu như nguồn UTC trong dịch vụ chủ bị lỗi, thì nó có thể trở thành dịch vụ phụ của giai tầng một. Nếu tài nguyên dùng cho việc đồng bộ hóa trong dịch vụ phụ lỗi thì nó có thể đồng bộ với các dịch vụ khác. Dịch vụ NTP được đồng bộ nhờ một trong ba chế độ : Multicast, gọi thủ tục(procedure call) và đối xứng (Symmetric). Chế độ Multicast thường dùng trong các mạng LAN, tốc độ cao. Một hoặc một số các dịch vụ định kỳ truyền bá (Multicast) thời gian tới các dịch vụ chạy trong các máy tính khác kết nối với nó qua LAN, các đồng hồ của máy tính này xem như có trễ khá nhỏ. Chế độ này chỉ thực hiện được với độ chính xác tương đối thấp, tuy nhiên chúng có khả năng duy trì một số mục đích. Chế độ gọi thủ tục tưng tự như thuật toán xử lý của Christian mô tả trên đây. Trong chế độ này một máy chủ sẽ nhận các yêu cầu từ máy tính khác, các yêu cầu đó sẽ được đáp ứng thông qua việc phuc đáp với nhãn thời gian của nó. Chế độ này thích hợp cho các mạng đòi hỏi độ tin cậy cao và do đó nó có thể thực hiện trong trường hợp Multicast hoặc ở những mạng phần cứng không hỗ trợ Multicast. Ví dụ, các file Server trong cùng mạng hoặc trong mạng LAN khác kết nối với nó, cần phải lưu giữ các thông tin về thời gian cho những lần truy cập file một cách chính xác, chúng cũng có thể giao tiếp với Server chủ cục bộ trong chế độ gọi thủ tục. Cuối cùng, chế độ đối xứng thường được Serverử dụng trong các Server chủ( những máy cung cấp các thông tin thời gian trong các mạng LAN) và các con đồng bộ hóa mức cao ( giai tầng thấp ), những nơi đòi hỏi tới độ chính xác cao nhất. Mỗi cặp máy chủ hoạt động trong chế độ đối xứng trao đổi các thông báo mang thông tin thời gian với nhau. Dữ liệu thời gian được giữ lại như một phần của Server kết hợp giữa các máy chủ, và được duy trì nhằm làm tăng độ chính xác của việc đồng bộ hóa thời gian của chúng. Trong tất cả các chế độ nêu trên, các thông báo được chuyển phát không đáng tin cậy như trong Server sử dụng giao thức truyền thông Internet chuẩn UDP. Trong chế độ gọi thủ tục và trong chế độ đối xứng các thông báo được trao dổi theo từng cặp. Mỗi thông báo mang một nhãn thời gian của biến cố thông báo hiện tại bao gồm: các giá trị thời hạn cục bộ khi gửi và nhận thông báo NTP trước đó, và thời điểm truyền thông báo hiện tại. Người nhận thông báo NTP sẽ ghi lại thời gian cục bộ khi nhận được thông báo. Bốn đơn vị thời gian Ti-3, Ti-2, Ti-1 và Ti của các thông báo m được gửi giữa các Server A và B, được mô tả như trong hình 1.6. Chú ý rằng, không giống như thuật toán Christian, chế độ đối xứng có thể có trễ khá lớn từ lúc thông báo tới khi gửi thông báo tiếp theo. Vì vậy, các thông báo có thể bị mất, nhưng các nhãn thời gian mang theo trong mỗi thông báo vẫn có giá trị. Máy chủ A Ti-2 Ti-1 thời gian Máy chủ B Ti-3 Ti Hình 1.6 Truyền dẫn các thông báo giữa các cặp NTP ngang hàng Với mỗi cặp các thông báo được gửi giữa hai Server, giao thức thời gian mạng NTP sẽ tính giá trị ước lượng độ lệch thực tế Oi giữa hai đồng hồ, và tổng trễ thời gian truyền dẫn hai thông báo di. Nếu độ lệch của đồng hồ trong B đối với A là O, và nếu thời gian truyền dẫn cho các thông báo m và m* tương ứng là t và t*, thì ta có: Ti-2 = Ti-3 + O và Ti = Ti-1+ t* - O đặt a=Ti-2-Ti-3 và b=Ti-1- Ti ta có: d1= t + t* = a- b Tương tự: O= Ti-2, Ti-3 = Oi + ( t*- t )/2, trong đó Oi=(a+b)/2; Trên thực tế t, t* >=0, nên ta có Oi + di/2 >= 0 >=(Oi -di/2). Biểu thức này chứng tỏ Oi là một ước lượng của độ lệch, và di là một phép đo chính xác của giá trị ước tính này. Các dịch vụ NTP áp dụng thuật toán lọc dữ liệu cho các cặp kế tiếp (Oi,di), các cặp này ước tính độ lệch O và tính toán chất lượng ước tính đó bằng hàng loạt các thống kê gọi là phân toán học. Độ phân tán lọc cao biểu thị dữ liệu có độ tin cậy thấp. Cũng như thuật toán Christian, giá trị của Oi tương ứng với giá trị nhỏ nhất của dj được chọn làm giá trị ước lượng O. Tuy nhiên, giá trị độ lệch nhận được được từ truyền thông với một nguồn không cần thiết phải dùng để điều chỉnh đồng hồ địa phương. Nói chung, một NTP Server trao đổi thông báo với một dịch vụ ngang hàng với nó. Ngoài việc lọc dữ liệu để trao đổi với từng dịch vụ ngang hàng, NTP còn áp dụng thuật toán chọn ngang hàng. Khảo sát những giá trị nhận được từ việc trao đổi với các dịch vụ ngang hàng này, sẽ tìm ra được những giá trị không tin cậy. Đầu ra của thuật toán này có thể làm cho dich vụ phi thay đổi các dịch vụ ngang hàng mà lúc đầu nó đã dùng để đồng bộ hóa. Những dịch vụ ngang hàng có chỉ số giai tầng thấp ưa chuộng hơn nhưng dịch vụ ngang hàng ở giai tầng cao, vì chúng “gần” với các nguồn thời gian cấp 1 hơn. Tương tự, nhưng dịch vụ ngang hàng có độ phân tán đồng bộ hóa thấp nhất được ưa chuộng hơn. Đây chính là tổng của bộ phân tán của bộ lọc đảo được giữa dịch vụ và gốc của mạng đồng bộ con, (độ phân tán đồng bộ hóa trao đổi ngang hàng trong các thông báo, cho phép tính được tổng này). Theo Mill, trong năm 1991, khong 20->30 Server cấp 1 và hơn 2000 Server cấp 2 hoạt động trên Internet, gồm ở Mỹ, Canada, Anh và Na uy. Server cấp 1 thường trao đổi thông báo với hầu hết các Server cấp 1 khác. Server cấp 2 đặc biệt thường thông tin với 1 Server ngang hàng ở cùng giai tầng và hai Server ngang hàng khác ở giai tầng thấp nhất tiếp theo. Các phép đo cho thấy lỗi đồng bộ hóa không quá 30 mili giây, nhưng chỉ 1% giá trị thời gian mẫu lấy từ các Server được đồng bộ hóa bởi NTP. Hơn nữa, bằng việc c chế vòng lặp đồng hồ để điều chỉnh tần số của các đồng hồ cục bộ trong việc đáp ứng với giữ liệu bù thêm, có thể đạt được độ chính xác ở mức 1 mili giây bằng việc thực hiện nhiều chu kỳ trong một giờ. Tuy nhiên không bảo đảm có giới hạn nào về sự khác nhau giữa hai đồng hồ. Mô hình vồng lặp đồng hồ pha đã được Mills đưa ra vào năm 1991. Mô hình này bao hàm cả việc chỉnh tần số đồng hồ địa phưng theo sự quan sát tốc độ lệch của nó. Xét ví dụ đơn giản, nếu thấy một đồng hồ luôn chạy nhanh 4 giây trong 1 giờ thì tần số của nó có thể giảm nhẹ (bằng phần mềm hoặc bằng phần cứng) để bù cho việc chạy nhanh này. Do đó, độ lệch đồng hồ trong các khoảng thời gian giữa các lần đồng bộ hóa sẽ giảm đi. Người ta quan niệm rằng bất kì một tiến trình đơn, một biến cố nào đều có thể sắp xếp một cách duy nhất theo thời gian của đồng hồ địa phương. Tuy nhiên, vì chúng ta không thể đồng bộ hóa một cách hoàn hảo các đồng hồ cục bộ trong hệ phân tán, nên nói chung ta không thể sử dụng thời gian vật lý để tìm ra trật tự của cặp biến cố bất kỳ nào xẩy ra trong nó. Nói chung, ta có thể sử dụng một sơ đồ tương tự tính nhân quả vật lý, nhưng nó chỉ được áp dụng trong hệ phân tán, để sắp xếp một biến cố xảy ra ở các tiến trình khác nhau. Việc sắp xếp này dựa trên hai điểm sau: Nếu hai biến cố xẩy ra trong cùng một tiến trình thì chúng xẩy ra theo trật tự mà tiến trình quan sát chúng. Khi thông báo được gửi giữa các tiến trình, biến cố gửi thông báo bao giờ cũng xẩy ra trước biến cố nhận thông báo. Lamport gọi trật tự nhận được nhờ việc khái quát hóa của hai mối quan hệ trên là quan hệ xẩy ra trước. Đôi khi nó còn được coi là trật tự nhân quả hay trật tự nhân quả tiềm tàng. Ta sẽ viết X->p Y nếu hai biến cố X và Y xẩy ra trong cùng một tiến trình p,và X xy ra trước Y. Sử dụng trật tự giới hạn này ta có thể xác định mối quan hệ xảy ra trước, biểu thị bằng kí hiệu->p như sau: HB1: nếu tồn tại tiến trình p: X->p Y, thì X->Y. HB2: đối với thông báo m bất kỳ: gửi(m)->nhận (m) Trong đó: gửi(m) là biến cố gửi thông báo, và nhận (m) là biến cố nhận thông báo. HB3: nếu X,Y và Z là những biến cố mà Y->Yvà Y->Z, thì X->Z. Do đó, nếu X->Y thì ta có thể tìm được một dãy các biến cố e1, e2, e3,.. en xảy ra trong một hoặc một số tiến trình mà x=e1 và y=en, và với i=1,2..n-1, HB1 hoặc HB2 áp dụng được giữa ei và ei+1, điều này có nghĩa là chúng xảy ra liên tiếp trong cùng tiến trình, hoặc có một thông báo m nào đó mà ei=gửi(m) và ei+1=nhận(m). dãy các biến cố e1, e2, e3…en không cần thiết phải duy nhất. PHẦN II: TIẾN TRÌNH HỆ ĐIỀU HÀNH PHÂN TÁN. I. TỔNG QUAN VỀ HỆ ĐIỀU HÀNH. Hệ điều hành là một chương trình hay một hệ chương trình hoạt động giữa người sử dụng (user) và phần cứng của máy tính. Mục tiêu của hệ điều hành là cung cấp một môi trường để người sử dụng có thể thi hành các chương trình. Nó làm cho máy tính dể sử dụng hơn, thuận lợi hơn và hiệu quả hơn.  Hệ điều hành là một phần quan trọng của hầu hết các hệ thống máy tính. Một hệ thống máy tính thường được chia làm bốn phần chính : phần cứng, hệ điều hành, các chương trình ứng dụng và người sử dụng.  Các bộ xử lý thông tin với nhau thông qua các đường truyền thông như những bus tốc độ cao hay đường dây điện thoại.  Các bộ xử lý trong hệ phân tán thường khác nhau về kích thước và chức năng. Nó có thể bao gồm máy vi tính, trạm làm việc, máy mini, và những hệ thống máy lớn. Các bộ xử lý thường được tham khảo với nhiều tên khác nhau như site, node, computer v.v.... tùy thuộc vào trạng thái làm việc của chúng. Các nguyên nhân phải xây dựng hệ thống phân tán là: Chia xẻ tài nguyên : Một người sử dụng A có thể sử dụng máy in laser của người sử dụng B và người sử dụng B có thể truy xuất những tập tin của A. Tổng quát, chia xẻ tài nguyên trong hệ thống phân tán cung cấp một cơ chế để chia xẻ tập tin ở vị trí xa, xử lý thông tin trong một cơ sở dữ liệu phân tán, in ấn tại một vị trí xa, sử dụng những thiết bị ở xa đểõ thực hiện các thao tác. Tăng tốc độ tính toán : Một thao tác tính toán được chia làm nhiều phần nhỏ cùng thực hiện một lúc. Hệ thống phân tán cho phép phân chia việc tính toán trên nhiều vị trí khác nhau để tính toán song song. An toàn : Nếu một vị trí trong hệ thống phân tán bị hỏng, các vị trí khác vẫn tiếp tục làm việc. Thông tin liên lạc với nhau :Có nhiều lúc, chương trình cần chuyển đổi dữ liệu từ vị trí này sang vị trí khác. Ví dụ trong hệ thống Windows, thường có sự chia xẻ và chuyển dữ liệu giữa các cửa sổ. Khi các vị trí được nối kết với nhau trong một hệ thống mạng, việc trao đổi dữ liệu diễn ra rất dễ. Người sử dụng có thể chuyển tập tin hay các E_mail cho nhau từ cùng vị trí hay những vị trí khác. Trong thời gian hiện tại đồng thời phát triển một số loại hệ điều hành theo các yêu cầu và các giải pháp khác nhau nhằm hỗ trợ cho việc đáp ứng yêu cầu của từng người sử dùng đến một tập thể và toàn bộ những người sử dụng máy vi tính. Vì vậy, theo những yêu cầu khác nhau thì việc phát triển hệ điều hành theo các hướng khác nhau là điều đương nhiên. Để phân loại hệ điều hành chúng tôi phân loại theo yêu cầu của người sử dụng chúng ta có thể chia làm ba loại hệ điều chính như sau: Hệ điều hành tập trung: Các hệ điều hành này có thể là đơn xử lý hoặc đa xử lý. Hệ thống này cung cấp các khả năng tốt nhất dùng để cho một người hay một số lượng nhỏ người sử dụng yêu cầu xử lý có độ phức tạp về việc quản lý file, bộ nhớ và các bộ vi xử lý. Hệ điều hành mạng: cấu trúc cũng giống như hệ điều hành trên nhưng chúng tập trung quản lý về việc chia sẻ tài nguyên, các giao dịch từ xa, anh ninh mạng,….. nói chung tập trung vào các giao tiếp trên mạng về các tài nguyên. Hệ điều hành phân tán: hệ điều hành phân tán nhìn qua thì cũng tương tự như hệ điều hành mạng nhưng có điểm khác là tính chất trong suốt. Do đó, chúng ta khi sử dụng hệ điều hành hệ phân tán chúng ta không hề cảm thấy khó khăn bởi vì toàn bộ hệ thống phân tán đều được che dấu đối với người sử dụng. Trong hệ điều hành này, đối với người sử dụng không có sự phân biệt giữa truy nhập từ xa hay ngay trong hệ thống của các tài nguyên được truy nhập đến. II. TIẾN TRÌNH HỆ ĐIỀU HÀNH PHÂN TÁN. Trước khi chúng ta nghiên cứu về các tiến trình trong hệ điều hành phân tán chúng ta cần xem kiến trúc nói chung của một hệ phân tán. Qua đó, chúng ta thấy được các chức năng, vai trò của hệ điều hành phân tán. Từ đó, chúng ta có thể phân tích các tiến trình trong hệ điều hành phân tán. Các cổng truyền thông Trạm làm việc Trạm làm việc máy khách Máy chủ chuyên trách Hình 2.1 Kiến trúc mạng phân tán. Kiến trúc của mạng của một hệ phân tán với thành phần là hệ điều hành hệ phân tán với hệ trung gian: Hình 2.2 Kiến trúc hệ phân tán và middleware. Mục đích hệ điều hành phân tán. Ngoài các mục đích cơ bản của hệ điều hành đó là: độ tin cậy cao, an toàn, hiệu quả trong xử lý, tính kế thừa, thuận tiện cao. Thì trong hệ điều hành phân tán còn phải đáp ứng các tính chất mà chúng ta luôn cần đến đó là tính bền vững. Tính bền vững ở đây chính là khả năng chụi lỗi có nghĩa là hệ thống có khả năng tự khởi động lại tới trạng thái mà ở đó tính toàn vẹn của hệ thống được duy trì với một số hiệu năng bị giảm sút. Chính nhờ khả năng này mà nó giúp cho hệ điều hành phân tán tăng cường độ tin cậy, an toàn và điều khiển truy nhập do chính nó thực hiện. Kiến trúc hệ điều hành phân tán. Hệ điều hành phân tán gồm hai thành phần chính đó là: các tiến trình và các file. Khi có mạng, chúng ta phải thêm thành phần thứ ba: các đường truyền thông. Phần cứng là các trạm làm việc và mạng. Tuy nhiên, người ta không dùng liên quan tới các thành phần vật lý ngoại trừ chi phí, sự xuất hiện của hiệu năng hệ thống. Trong đó người ta chia thành hai mô hình chính đó là mô hình trạm làm việc -máy chủ và mô hình xử lý nhóm tuỳ theo vào yêu cầu và mục đích của mạng phân tán. Hình 2.3 Kiến trúc hệ điều hành phân tán. Như vậy các kiến trúc của hệ điều hành phân tán có 5 thành phân chính Process manager: quản lý tiến trình đặt ở mức cao nhất là thành phần giao tiếp trực tiếp với người sử dụng. Communication manager: Quản lý truyền thông đóng vai trò như một thành phần giao tiếp giữa các tiến trìn các luồng cũng như quản lý tài nguyên tại máy và các máy khác nhau trong hệ thống. Thread manager: quản lý các tiểu tiến trình. Memory manager: quản lý tài nguyên hệ thống. Supervisor: Thực hiện quản lý mức thấp nhất của hệ điều hành. Kiến trúc của tiến trình trong hệ điều hành phân tán. a. Tiến trình hệ điều hành phân tán. Tiến trình là một chương trình đang xử lý, sỡ hữu một con trỏ lệnh, tập các thanh ghi và các biến. Để hoàn thành tác vụ của mình, một tiến trình có thể cần đến một số tài nguyên – như CPU, bộ nhớ chính, các tập tin và thiết bị nhập/xuất… Cần phân biệt hai khái niệm chương trình và tiến trình. Một chương trình là một thực thể thụ động, chứa đựng các chỉ thị điều khiển máy tính để tiến hành một tác vụ nào đó ; khi cho thực hiện các chỉ thị này, chương trình chuyển thành tiến trình, là một thực thể hoạt động, với con trỏ lệnh xác định chỉ thị kế tiếp sẽ thi hành, kèm theo tập các tài nguyên phục vụ cho hoạt động của tiến trình. Trong hầu hết các hệ điều hành, mỗi tiến trình có một không gian địa chỉ và chỉ có một dòng xử lý. Tuy nhiên, có nhiều tình huống người sử dụng mong muốn có nhiều dòng xử lý cùng chia sẻ một không gian địa chỉ, và các dòng xử lý này hoạt động song song tương tự như các tiến trình phân biệt (ngoại trừ việc chia sẻ không gian địa chỉ). b. Tiểu tiến trình( threads_Luồng của tiến trình). Trong hầu hết các hệ điều hành, mỗi tiến trình có một không gian địa chỉ và chỉ có một dòng xử lý. Tuy nhiên, có nhiều tình huống người sử dụng mong muốn có nhiều dòng xử lý cùng chia sẻ một không gian địa chỉ, và các dòng xử lý này hoạt động song song tương tự như các tiến trình phân biệt (ngoại trừ việc chia sẻ không gian địa chỉ). Ví dụ : Một server quản lý tập tin thỉnh thoảng phải tự khóa để chờ các thao tác truy xuất đĩa hoàn tất.Nếu server có nhiều dòng xử lý, hệ thống có thể xử lý các yêu cầu mới trong khi một dòng xử lý bị khoá. Như vậy việc thực hiện chương trình sẽ có hiệu quả hơn. Điều này không thể đạt được bằng cách tạo hai tiến trình server riêng biệt vì cần phải chia sẻ cùng một vùng đệm, do vậy bắt buộc phải chia sẻ không gian địa chỉ. Chính vì các tình huống tương tự, người ta cần có một cơ chế xử lý mới cho phép có nhiều dòng xử lý trong cùng một tiến trình. Ngày nay đã có nhiều hệ điều hành cung cấp một cơ chế như thế và gọi là tiểu trình (threads). c. Nguyên lý chung :  Một tiểu trình là một đơn vị xử lý cơ bản trong hệ thốn. Mỗi tiểu trình xử lý tuần tự đoạn code của nó, sỡ hữu một con trỏ lệnh, tập các thanh ghi và một vùng nhớ stack riêng. Các tiểu trình chia sẻ CPU với nhau giống như cách chia sẻ giữa các tiến trình: một tiểu trình xử lý trong khi các tiểu trình khác chờ đến lượtù. Một tiểu trình cũng có thể tạo lập các tiến trình con, và nhận các trạng thái khác nhau như một tiến trình thật sự. Một tiến trình có thể sỡ hữu nhiều tiểu trình. Các tiến trình tạo thành những thực thể độc lập. Mỗi tiến trình có một tập tài nguyên và một môi trường riêng (một con trỏ lệnh, một Stack, các thanh ghi và không gian địa chỉ ). Các tiến trình hoàn toàn độc lập với nhau, chỉ có thể liên lạc thông qua các cơ chế thông tin giữa các tiến trình mà hệ điều hành cung cấp. Ngược lại, các tiểu trình trong cùng một tiến trình lại chia sẻ một không gian địa chỉ chung, điều này có nghĩa là các tiểu trình có thể chia sẻ các biến toàn cục của tiến trình. Một tiểu trình có thể truy xuất đến cả các stack của những tiểu trình khác trong cùng tiến trình. Cấu trúc này không đề nghị một cơ chế bảo vệ nào, và điều này cũng không thật cần thiết vì các tiểu trình trong cùng một tiến trình thuộc về cùng một sỡ hữu chủ đã tạo ra chúng trong ý định cho phép chúng hợp tác với nhau. Hình 2.4 Các tiểu trình trong cùng một tiểu trình d. Phân bổ thông tin lưu trữ. Hình 2.5 Cấu trúc mô tả tiến trình và tiểu trình Trong một số trường hợp tiểu tiến trình có thẻ gọi là “lightweight” của tiến trình. Đó là do hệ điều hành sẽ chỉ biết đến khái niệm tiến trình, do vậy cận có cơ chế để liên kết các tiểu trình cùng một tiến trình với tiến trình cha trong kernel_ đối tượng này đôi lúc được gọi là LWP (lightweight process). Hình 2.6 Tiểu tiển trình là một “lightweight proccess” 4. Các vấn đề trong quản lý tiến trình của. a. Sự loại trừ lẫn nhau trong hệ phân tán. Sự loại trừ lẫn nhau trong hệ phân tán xảy ra khi nhiều tiến trình đồng thời thực hiện một sự truy nhập nối tiếp để chia sẻ tài nguyên và dữ liệu ( ví dụ như cập nhật dữ liệu hay gửi các tín hiệu đến các thiết bị vào ra. Vấn đề ở đây là trong các trường hợp đó chúng ta cần phải làm gì để sự tương xảy ra là công bằng theo các tiêu chuẩn cho trước. Trong đó, các tiêu chuẩn này bao gồm: thời gian yêu cầu, thứ tự yêu tiên của yêu cầu hay sự lựa chọn. Chúng ta có một số thuật toán để giải quyết tranh chấp khi xảy ra tương tranh. Người dùng có thể dựa vào đó để có thể lấy quyền ưu tiên. Trong đó có một số phương pháp và dạng xảy ra tương tranh dưới đây: Loại trừ lẫn nhau dựa vào tranh chấp: là sự tranh chấp cho các phần tới hạn có thể quyết định bằng bất cứ tiêu chí vào để phá vỡ các dàng buộc khi các yêu cầu thực hiện xảy ra cùng một thời điểm. Cách tốt nhất cho phép yêu cầu tới các tiến trình được hỏi đầu tiên hoặc tiển trình được dưa ra nhiều nhất từ các tiến trình khác chúng ta sẽ gọi hai cách tiếp cận khác nhau này là các sơ đồ yêu tiên nhãn thời gian và bầu cử. Loại trừ dựa vào việc chuyển Token: Đây là sự tranh chấp dựa vào thuật toán. Cơ chế của thuật toán dựa trên việc cung cấp các Token cho các thành viên xảy ra tranh chấp làm sao đảm bảo chỉ có một Token. Có ba thuật toán chính để phân chia các Token theo kiến trúc mạng là : cấu trúc vòng, cây và quảng bá. b. Lập lịch xử lý hệ điều hành phân tán. Để tạo sự đồng bộ và thuận lợi trong truyền thông, các hệ thống hệ phân tán cần thiết phải có sự hỗ trợ cho việc giải quyết tương tranh của các tiến trình tương tác. Trước khi thực hiện, các tiến trình cần lập lịch và phân phối tài nguyên. Đối tượng được lập lịch chính là để nâng cao toàn bộ hiệu năng hệ thống như thời gian hoàn thành tiến trình và sự tận dụng các bộ xử lý. Sự tồn tại nhiều nút xử lý trong các hệ thống phân tán đưa ra vấn đề thách thức để lập lịc các tiến trình như ccs xử lý và ngược lại. Tiến trình lập lịch phân tán được tổ chức thành hai thành phần: tiến trình lập lịch tĩnh, phân chia và cân bằng tải động. c. Truyền thông liên tiến trình. Trong các hệ điều hành, tương tác giữa các tiến trình và luồng thông tin giữa các đối tượng phụ thuộc vào truyền thông. Tại mức thấp nhất, truyền thông báo chỉ có nghĩa truyền thông trong các hệ phân tán. Truyền thông liên tiến trình có thể được hoàn thành bằng cách dùng truyền thông báo đơn giản. Tuy nhiên, nó muốn có sự trong suốt trong truyền thông bằng cách cung cấp các phương thức truyền thông logic mức cao hơn để che các chi tiết vật lý của việc truyền thông báo. Hai khái niệm quan trọng để thực hiện kết quả này là mô hình khách/chủ (client/server) và gọi thủ tục từ xa (RPC). Mô hình client/server là mô hình lập trình cho các tiến trình cấu trúc trong hệ phân tán. Trong mô hình này, tất cả các tương tác hệ thống được thấy như một cặp thông báo trao đổi trong tiến trình client gửi thông báo yêu cầu tới server và đợi cho server trả lời với thông báo trả lời. Thông báo hỏi đáp (request/repply) trao đổi giữa client và server do vậy có thể được biểu diễn như gọi thủ tục đến server ở xa. Truyền thông gọi thủ tục từ xa (RPC) xây dựng trên mô hình client/server và truyền thông báo cho đã được đưa ra như một kỹ thuật truyền thông liên tiến trình chuẩn cho tất cả các hệ phân tán. c.1 Mô hình RPC. Các tiến trình là các đơn vị xử lý cơ bản trong hệ điều hành. Một tiến trình là một chương trình thực hiện. Một tiến trình là tuần tự nếu chuỗi điều chỉnh hoạt động của nó. Chúng ta dùng thuật ngữ tiến trình tương tranh (concurrent process) để mô tả các tiến trình giả lập tương tác tuần tự. Các tiến trình xảy ra là không đồng bộ và mỗi tiến trình có không gian địa chỉ logic của chính nó. Giữa hai tiến trình, một số thành phần trong các tiến trình được tách ra có thể được thực hiện đồng thời. Số khác cần để truyền thông hay đồng bộ giữa chúng. Cho phép nhiều nhánh điều khiển trong tiến trình đưa ra mức tương tranh mới trong hệ thống. Tiến trình mới có thể sinh ra tiến trình mới, do vậy tạo ra nhiều nhánh hoạt động. Trường hợp quan tâm đặc biệt khi các tiến trình con được nhóm lại với nhau để chia sẻ không gian địa chỉ chung, nhưng mỗi trạng thái lại có trạng thái cục bộ của nó. Tiến trình này được gọi là tiến trình nhánh hay là các tiến trình không quan trọng. Quá trình tương tranh trong hệ phân tán được chia làm hai mức của tiến trình và nhánh. Trong mức thấp hơn, các tiểntình xảy ra đồng thời thực hiện không đồng bộ trên hệ điều hành. Mỗi tiến trình xảy ra đồng thời chạy như một máy ảo để hỗ trợ việc thực hiện đồng thời các nhánh, tạo thành mức tương tranh thứ hai. Tiến trình chỉ là không gian địa chỉ logic trong lúc các nhánh hoạt động. Chúng ta dùng thuật ngữ khối điều khiển tiển trình ( PCB_Process Control Block) bao gồm các thông tín sau: bộ đếm chương trình, nội dung thanh ghi, con trỏ, ngăn xếp, các cổng truyền thôngm và các file mô tả. Khối điều khiển các nhánh (TCB_ Thread Control Block) chúng được sinh ra nhờ lời gọi của các tiến trình. Hình 2.7 Tương tranh hai mức của các tiến trình và các nhánh. c.2 Mô hình client/server. Một cách tiếp cận phổ biến là kiểu client/server. Kiểu client/server là mô hình lập trình biểu diễn các tiến trình và các cấu trúc hệ thống. Các tiến trình yêu cầu dịch vụ là các client, các tiến trình cung cấp dịch vụ là các server. Trong bất cứ trường hợp nào, một tiến trình là một client hay là một server hoặc cũng có thể là cả hai vai trò. Client và server tương tác thông qua một chuỗi các yêu cầu và đáp ứng trên cơ sở đồng bộ hoá các vấn đề truyền thông. Truyền thông liên tiến trình và quá trình xử lý tương tranh Trong mạng phân tán, chúng ta tập trung xử lý truyền thông trong đó việc nhận hay gửi là một phần chính của chúng. Ngoài ra, chúng còn có một số biến thể của nó. Tuy nhiên việc gửi và nhân là chức năng chính của truyền thông cơ bản. Truyền thông cơ bản chính là việc nhận và gửi thông báo trong đó bao gồm ba thành phần chính là địa chỉ đến và đi và nội dung cần gửi đi. Trong quá trình truyền đi,chúng ta thấy sự tồn tại một vùng đệm để lưu trữ dữ liệu. Bộ đệm này ngoài mang ý nghĩa giúp người dùng tạo cảm giác liên tục đồng đều. Chúng còn có vai trò quan trọng trong việc đồng bộ giữa bên nhận và bên gửi, giữa nhân và nhân. 5. TỔ CHỨC QUẢN LÝ TIẾN TRÌNH 5.1. Các trạng thái của tiến trình Trạng thái của tiến trình tại một thời điểm được xác định bởi hoạt động hiện thời của tiến trình tại thời điểm đó. Trong quá trình sống, một tiến trình thay đổi trạng thái do nhiều nguyên nhân như : phải chờ một sự kiện nào đó xảy ra, hay đợi một thao tác nhập/xuất hoàn tất, buộc phải dừng hoạt động do đã hết thời gian xử lý … Tại một thời điểm, một tiến trình có thể nhận trong một các trạng thái sau đây : Mới tạo : tiến trình đang được tạo lập. Running : các chỉ thị của tiến trình đang được xử lý. Blocked : tiến trình chờ được cấp phát một tài nguyên, hay chờ mộtsự kiện xảy ra. Ready : tiến trình chờ được cấp phát CPU để xử lý. Kết thúc : tiến trình hoàn tất xử lý. Hình 2.7Sơ đồ chuyển trạng thái giữa các tiến trình Tại một thời điểm, chỉ có một tiến trình có thể nhận trạng thái running trên một bộ xử lý bất kỳ. Trong khi đó, nhiều tiến trình có thể ở trạng thái blocked hay ready. Các cung chuyển tiếp trong sơ đồ trạng thái biễu diễn sáu sự chuyển trạng thái có thể xảy ra trong các điều kiện sau : Tiến trình mới tạo được đưa vào hệ thống Bộ điều phối cấp phát cho tiến trình một khoảng thời gian sử dụng CPU Tiến trình kết thúc Tiến trình yêu cầu một tài nguyên nhưng chưa được đáp ứng vì tài nguyên chưa sẵn sàng để cấp phát tại thời điểm đó ; hoặc tiến trình phải chờ một sự kiện hay thao tác nhập/xuất. Bộ điều phối chọn một tiến trình khác để cho xử lý. Tài nguyên mà tiến trình yêu cầu trở nên sẵn sàng để cấp phát ; hay sự kiện hoặc thao tác nhập/xuất tiến trình đang đợi hoàn tất. 5.2. Cấu trúc dữ liệu khối quản lý tiến trình Hệ điều hành quản lý các tiến trình trong hệ thống thông qua khối quản lý tiến trình (process control block -PCB). PCB là một vùng nhớ lưu trữ các thông tin mô tả cho tiến trình, với các thành phần chủ yếu bao gồm : Định danh của tiến trình (1) : giúp phân biệt các tiến trình Trạng thái tiến trình (2): xác định hoạt động hiện hành của tiến trình. Ngữ cảnh của tiến trình (3): mô tả các tài nguyên tiến trình đang trong quá trình, hoặc để phục vụ cho hoạt động hiện tại, hoặc để làm cơ sở phục hồi hoạt động cho tiến trình, bao gồm các thông tin về: Trạng thái CPU: bao gồm nội dung các thanh ghi, quan trọng nhất là con trỏ lệnh IP lưu trữ địa chỉ câu lệnh kế tiếp tiến trình sẽ xử lý. Các thông tin này cần được lưu trữ khi xảy ra một ngắt, nhằm có thể cho phép phục hồi hoạt động của tiến trình đúng như trước khi bị ngắt. Bộ xử lý: dùng cho máy có cấu hình nhiều CPU, xác định số hiệu CPU mà tiến trình đang sử dụng. Bộ nhớ chính: danh sách các khối nhớ được cấp cho tiến trình. Tài nguyên sử dụng: danh sách các tài mguyên hệ thống mà tiến trình đang sử dụng. Tài nguyên tạo lập: danh sách các tài nguyên được tiến trình tạo lập. Thông tin giao tiếp (4): phản ánh các thông tin về quan hệ của tiến trình với các tiến trình khác trong hệ thống : Tiến trình cha: tiến trình tạo lập tiến trình này. Tiến trình con: các tiến trình do tiến trình này tạo lập. Độ ưu tiên : giúp bộ điều phối có thông tin để lựa chọn tiến trình được cấp CPU. Thông tin thống kê (5): đây là những thông tin thống kê về hoạt động của tiến trình, như thời gian đã sử dụng CPU,thời gian chờ. Các thông tin này có thể có ích cho công việc đánh giá tình hình hệ thống và dự đoán các tình huống tương lai. Hình 2.8 Khối mô tả tiến trình 5.3. Thao tác trên tiến trình Hệ điều hành cung cấp các thao tác chủ yếu sau đây trên một tiến trình : tạo lập tiến trình (create) kết thúc tiến trình (destroy) tạm dừng tiến trình (suspend) tái kích hoạt tiến trình (resume) thay đổi độ ưu tiên tiến trình 5.3.1. Tạo lập tiến trình Trong quá trình xử lý, một tiến trình có thể tạo lập nhiều tiến trình mới bằng cách sử dụng một lời gọi hệ thống tương ứng. Tiến trình gọi lời gọi hệ thống để tạo tiến trình mới sẽ được gọi là tiến trình cha, tiến trình được tạo gọi là tiến trình con. Mỗi tiến trình con đến lượt nó lại có thể tạo các tiến trình mới…quá trình này tiếp tục sẽ tạo ra một cây tiến trình. Các công việc hệ điều hành cần thực hiện khi tạo lập tiến trình bao gồm : định danh cho tiến trình mới phát sinh đưa tiến trình vào danh sách quản lý của hệ thống xác định độ ưu tiên cho tiến trình tạo PCB cho tiến trình cấp phát các tài nguyên ban đầu cho tiến trình Khi một tiến trình tạo lập một tiến trình con, tiến trình con có thể sẽ được hệ điều hành trực tiếp cấp phát tài nguyên hoặc được tiến trình cha cho thừa hưởng một số tài nguyên ban đầu. Khi một tiến trình tạo tiến trình mới, tiến trình ban đầu có thể xử lý theo một trong hai khả năng sau  : Tiến trình cha tiếp tục xử lý đồng hành với tiến trình con. Tiến trình cha chờ đến khi một tiến trình con nào đó, hoặc tất cả các tiến trình con kết thúc xử lý. Các hệ điều hành khác nhau có thể chọn lựa các cài đặt khác nhau để thực hiện thao tác tạo lập một tiến trình. 5.3.2. Kết thúc tiến trình Một tiến trình kết thúc xử lý khi nó hoàn tất chỉ thị cuối cùng và sử dụng một lời gọi hệ thống để yêu cầu hệ điều hành hủy bỏ nó. Đôi khi một tiến trình có thể yêu cầu hệ điều hành kết thúc xử lý của một tiến trình khác. Khi một tiến trình kết thúc, hệ điều hành thực hiện các công việc : thu hồi các tài nguyên hệ thống đã cấp phát cho tiến trình hủy tiến trình khỏi tất cả các danh sách quản lý của hệ thống hủy bỏ PCB của tiến trình Hầu hết các hệ điều hành không cho phép các tiến trình con tiếp tục tồn tại nếu tiến trình cha đã kết thúc. Trong những hệ thống như thế, hệ điều hành sẽ tự động phát sinh một loạt các thao tác kết thúc tiến trình con. 5.4. Cấp phát tài nguyên cho tiến trình Khi có nhiều người sử dụng đồng thời làm việc trong hệ thống, hệ điều hành cần phải cấp phát các tài nguyên theo yêu cầu cho mỗi người sử dụng. Do tài nguyên hệ thống thường rất giới hạn và có khi không thể chia sẻ, nên hiếm khi tất cả các yêu cầu tài nguyên đồng thời đều được thỏa mãn. Vì thế cần phải nghiên cứu một phương pháp để chia sẻ một số tài nguyên hữu hạn giữa nhiều tiến trình người dùng đồng thời. Hệ điều hành quản lý nhiều loại tài nguyên khác nhau (CPU, bộ nhớ chính, các thiết bị ngoại vi …), với mỗi loại cần có một cơ chế cấp phát và các chiến lược cấp phát hiệu qủa. Mỗi tài nguyên được biễu diễn thông qua một cấu trúc dữ liệu, khác nhau về chi tiết cho từng loại tài nguyên, nhưng cơ bản chứa đựng các thông tin sau : Định danh tài nguyên Trạng thái tài nguyên : đây là các thông tin mô tả chi tiết trạng thái tài nguyên : phần nào của tài nguyên đã cấp phát cho tiến trình, phần nào còn có thể sử dụng ? Hàng đợi trên một tài nguyên : danh sách các tiến trình đang chờ được cấp phát tài nguyên tương ứng. Bộ cấp phát  : là đoạn code đảm nhiệm việc cấp phát một tài nguyên đặc thù. Một số tài nguyên đòi hỏi các giải thuật đặc biệt (như CPU, bộ nhớ chính, hệ thống tập tin), trong khi những tài nguyên khác (như các thiết bị nhập/xuất) có thể cần các giải thuật cấp phát và giải phóng tổng quát hơn. Hình 2.9 Khối quản lý tài nguyên Các mục tiêu của kỹ thuật cấp phát : Bảo đảm một số lượng hợp lệ các tiến trình truy xuất đồng thời đến các tài nguyên không chia sẻ được. Cấp phát tài nguyên cho tiến trình có yêu cầu trong một khoảng thời gian trì hoãn có thể chấp nhận được. Tối ưu hóa sự sử dụng tài nguyên. Để có thể thõa mãn các mục tiêu kể trên, cần phải giải quyết các vấn đề nảy sinh khi có nhiều tiến trình đồng thời yêu cầu một tài nguyên không thể chia sẻ.  5.5. Xử lý tiểu tiến trình tại server. hình 2.10. Mô hình xử lý các luồng tại Server. Xử lý threads tại server. Khi nhận được yêu cầu của client thì server sẽ dựa vào các thuật toán để đáp ứng các yêu cầu của client gồm có 3 phương pháp chính sau: Server lúc nào cũng có tạo ra các vòng lặp để tìm xem có yêu cầu nào của server gửi đến hay không trong các hành đợi. Đồng thời server chụi trách nhiệm phân quyền nếu có thể. Server có thể nhận các yêu cầu thông qua ba phương pháp chính đó là: Phương pháp worker: là phương pháp mà client kết nối vào cổng và tập trung tạo ra các thread để sử lý theo từng yêu cầu Phương pháp thread per connection: Tức là một yêu cầu của client gửi đến đều được sử lý song song vào các cổng truyền thông và xử lý tập trung. Phương pháp thread per object: là các yêu cầu được đưa vào hàng đợi và đưa ra xử lý song song. Trong môi trường đa chương, một tiến trình không đơn độc trong hệ thống, mà có thể ảnh hưởng đến các tiến trình khác, hoặc bị các tiến trình khác tác động. Nói cách khác, các tiến trình là những thực thể độc lập, nhưng chúng vẫn có nhu cầu liên lạc với nhau để: Chia sẻ thông tin: nhiều tiến trình có thể cùng quan tâm đến những dữ liệu nào đó, do vậy hệ điều hành cần cung cấp một môi trường cho phép sự truy cập đồng thời đến các dữ liệu chung. Hợp tác hoàn thành tác vụ: đôi khi để đạt được một sự xử lý nhanh chóng, người ta phân chia một tác vụ thành các công việc nhỏ có thể tiến hành song song. Thường thì các công việc nhỏ này cần hợp tác với nhau để cùng hoàn thành tác vụ ban đầu, ví dụ dữ liệu kết xuất của tiến trình này lại là dữ liệu nhập cho tiến trình khác …Trong các trường hợp đó, hệ điều hành cần cung cấp cơ chế để các tiến trình có thể trao đổi thông tin với nhau. Do mỗi tiến trình sỡ hữu một không gian địa chỉ riêng biệt, nên các tiến trình không thể liên lạc trực tiếp dễ dàng mà phải nhờ vào các cơ chế do hệ điều hành cung cấp. Khi cung cấp cơ chế liên lạc cho các tiến trình, hệ điều hành thường phải tìm giải pháp cho các vấn đề chính yếu sau : Liên kết tường minh hay tiềm ẩn (explicit naming/implicit naming) : tiến trình có cần phải biết tiến trình nào đang trao đổi hay chia sẻ thông tin với nó ? Mối liên kết được gọi là tường minh khi được thiết lập rõ ràng, trực tiếp giữa các tiến trình, và là tiềm ẩn khi các tiến trình liên lạc với nhau thông qua một qui ước ngầm nào đó. Liên lạc theo chế độ đồng bộ hay không đồng bộ (blocking / non-blocking): khi một tiến trình trao đổi thông tin với một tiến trình khác, các tiến trình có cần phải đợi cho thao tác liên lạc hoàn tất rồi mới tiếp tục các xử lý khác ? Các tiến trình liên lạc theo cơ chế đồng bộ sẽ chờ nhau hoàn tất việc liên lạc, còn các tiến trình liên lạc theo cơ chế nonblocking thì không. Liên lạc giữa các tiến trình trong hệ thống tập trung và hệ thống phân tán: cơ chế liên lạc giữa các tiến trình trong cùng một máy tính có sự khác biệt với việc liên lạc giữa các tiến trình giữa những máy tính khác nhau? Do mỗi tiến trình sỡ hữu một không gian địa chỉ riêng biệt, nên các tiến trình không thể liên lạc trực tiếp dễ dàng mà phải nhờ vào các cơ chế do hệ điều hành cung cấp. Khi cung cấp cơ chế liên lạc cho các tiến trình, hệ điều hành thường phải tìm giải pháp cho các vấn đề chính yếu sau : Liên kết tường minh hay tiềm ẩn (explicit naming/implicit naming) : tiến trình có cần phải biết tiến trình nào đang trao đổi hay chia sẻ thông tin với nó ? Mối liên kết được gọi là tường minh khi được thiết lập rõ ràng, trực tiếp giữa các tiến trình, và là tiềm ẩn khi các tiến trình liên lạc với nhau thông qua một qui ước ngầm nào đó. Liên lạc theo chế độ đồng bộ hay không đồng bộ (blocking / non-blocking): khi một tiến trình trao đổi thông tin với một tiến trình khác, các tiến trình có cần phải đợi cho thao tác liên lạc hoàn tất rồi mới tiếp tục các xử lý khác ? Các tiến trình liên lạc theo cơ chế đồng bộ sẽ chờ nhau hoàn tất việc liên lạc, còn các tiến trình liên lạc theo cơ chế nonblocking thì không. Liên lạc giữa các tiến trình trong hệ thống tập trung và hệ thống phân tán: cơ chế liên lạc giữa các tiến trình trong cùng một máy tính có sự khác biệt với việc liên lạc giữa các tiến trình giữa những máy tính khác nhau? Trao đổi thông điệp (Message) Giới thiệu: Hệ điều hành còn cung cấp một cơ chế liên lạc giữa các tiến trình không thông qua việc chia sẻ một tài nguyên chung, mà thông qua việc gởi thông điệp. Để hỗ trợ cơ chế liên lạc bằng thông điệp, hệ điều hành cung cấp các hàm IPC chuẩn (Interprocess communication), cơ bản là hai hàm: Send(message)  : gởi một thông điệp Receive(message)  : nhận một thông điệp Nếu hai tiến trình P và Q muốn liên lạc với nhau, cần phải thiết lập một mối liên kết giữa hai tiến trình, sau đó P, Q sử dụng các hàm IPC thích hợp để trao đổi thông điệp, cuối cùng khi sự liên lạc chấm dứt mối liên kết giữa hai tiến trình sẽ bị hủy. Có nhiều cách thức để thực hiện sự liên kết giữa hai tiến trình và cài đặt các theo tác send /receive tương ứng : liên lạc trực tiếp hay gián tiếp, liên lạc đồng bộ hoặc không đồng bộ, kích thước thông điệp là cố định hay không … Nếu các tiến trình liên lạc theo kiểu liên kết tường minh, các hàm Send và Receive sẽ được cài đặt với tham số : Send(destination, message)  : gởi một thông điệp đến destination Receive(source,message)  : nhận một thông điệp từ source 5.6. Sockets Giới thiệu: Một socket là một thiết bị truyền thông hai chiều tương tự như tập tin, chúng ta có thể đọc hay ghi lên nó, tuy nhiên mỗi socket là một thành phần trong một mối nối nào đó giữa các máy trên mạng máy tính và các thao tác đọc/ghi chính là sự trao đổi dữ liệu giữa các ứng dụng trên nhiều máy khác nhau. Sử dụng socket có thể mô phỏng hai phương thức liên lạc trong thực tế : liên lạc thư tín (socket đóng vai trò bưu cục) và liên lạc điện thoại (socket đóng vai trò tổng đài). Các thuộc tính của socket: Type: định nghĩa các đặc điểm liên lạc: Sự tin cậy Sự bảo toàn thứ tự dữ liệu Lặp lại dữ liệu Chế độ nối kết Bảo toàn giới hạn thông điệp Khả năng gởi thông điệp khẩn Để thực hiện liên lạc bằng socket, cần tiến hành các thao tác : Tạo lập hay mở một socket Gắn kết một socket với một địa chỉ Liên lạc : có hai kiểu liên lạc tùy thuộc vào chế độ nối kết:     a) Liên lạc trong chế độ không liên kết : liên lạc theo hình thức hộp thư: Hai tiến trình liên lạc với nhau không kết nối trực tiếp Mỗi thông điệp phải kèm theo địa chỉ người nhận. Hình thức liên lạc này có đặc điểm được : người gởi không chắc chắn thông điệp của học được gởi đến người nhận, Một thông điệp có thể được gởi nhiều lần, Hai thông điệp đượ gởi theo một thứ tự nào đó có thể đến tay người nhận theo một thứ tự khác. Một tiến trình sau khi đã mở một socket có thể sử dụng nó để liên lạc với nhiều tiến trình khác nhau nhờ sử hai primitive send và receive.     b) Liên lạc trong chế độ nối kết:      Một liên kết được thành lập giữa hai tiến trình. Trước khi mối liên kết này được thiết lập, một trong hai tiến trình phải đợi có một tiến trình khác yêu cầu kết nối.Có thể sử dụng socket để liên lạc theo mô hình client-serveur. Trong mô hình này, server sử dụng lời gọi hệ thống listen và accept để nối kết với client, sau đó, client và server có thể trao đổi thông tin bằng cách sử dụng các primitive send và receive. Hủy một socket  Ví dụ : Trong nghi thức truyền thông TCP, mỗi mối nối giữa hai máy tính được xác định bởi một port, khái niệm port ở đây không phải là một cổng giao tiếp trên thiết bị vật lý mà chỉ là một khái niệm logic trong cách nhìn của người lập trình, mỗi port được tương ứng với một số nguyên dương. Hình 2.11. Các socket và port trong mối nối TCP. Hình trên minh họa một cách giao tiếp giữa hai máy tính trong nghi thức truyền thông TCP. Máy A tạo ra một socket và kết buộc (bind) socket nầy với một port X (tức là một số nguyên dương có ý nghĩa cục bộ trong máy A), trong khi đó máy B tạo một socket khác và móc vào (connect) port X trong máy A. PHẦN III:NGHIÊN CỨU CÁC GIẢI THUẬT PHÂN TÁN Các khái niệm cơ bản: Các giao thức dùng để gửi thông báo điều khiển. Thông báo điều khiển chỉ rõ hoạt động mà bộ xử lý gửi đi muốn nhận lại để thực hiện và đặt tham số. Một bộ xử lý có thể gửi một thông báo kiểu action tới bộ xử lý với các tham số p bằng các câu lệnh sau: Send (d,action;p); Thông báo gửi đi không bị chặn và tin cậy. Các giao thức trả lời các ngắt bên trong và thời gian timeout như các thông báo bên ngoài. Bộ xử lý phải có khả năng quản lý sự việc tại bất cứ lúc nào, nó phải thực hiện một chuỗi khai báo để quản lý sự việc. Một bộ xử lý khai báo rằng nó đang đợi các sự việc A1,…,An bằng cách thực hiện mã lệnh sau: Wait for A1,A2,…,An A1(source;p) Code to handle A1 ….. An (source;p) Code to handle An Khi bộ xử lý p thực hiện send(q,A1;p) và bộ xử lý q thực hiện mã lệnh như trên, q sẽ thông báo gửi bởi p. Biến source sẽ chứa tên bộ xử lý p và các tham số mà p gửi sẽ được mở bởi q. Các lỗi thường xuyên được phát hiện bởi thời gian timeout. Chúng ta dùng cấu trúc cho dưới đây để chỉ ra rằng giao thức phải đợi thông báo kiểu sự kiện từ P tới T giây và xác định thời gian timeout hoạt động nếu không có thông báo như vậy được nhận: Wait until P sends (event;p),timeout=T on timeout timeout action Thường chúng ta muốn thực hiện một hoạt động chỉ nếu chúng ta đã nhận được trả lời và không thực hiện hoạt động trong thời gian timeout. Trong trường hợp này, chúng ta sẽ dùng đến cấu trúc như sau để chỉ ra hoạt động thực hiện thông báo nếu thông báo quay lại được nhận: Wait until P sends(event;p),timeout=T on timeout; If no timeout occurred (successful response actions) Lúc khác, giải thuật không cần đợi trả lời từ bộ xử lý đặc biệt nhưng phải đợi các trả lời từ tập các bộ xử lý. Trong cấu trúc đã cho, bộ xử lý phải đợi mất T giây để trả lời. Có nghĩa là, nếu bộ xử lý tìm thấy rằng không có trả lời được xử lý tại thời gian T giây sau khi bắt đầu đợi, tiến trình đợi kết thúc và giao thức sẽ tiếp tục. Như rút gọn, giao thức có thể dừng tiến trình đợi khi tất cả các trả lời mong đợi đến. Quan hệ nhân quả. Giả sử rằng hệ phân tán gồm một tập các bộ xử lý P={p1,…,pM}. Ta coi mỗi việc gửi đi và nhận thông báo là một sự kiện. Hơn nữa, một số hoạt động bên trong bộ xử lý được coi là một sự kiện. Chúng ta định nghĩa e là một tập tất cả các sự kiện bên trong hệ thống của chúng ta và ep là tất cả các sự kiện trong e xảy ra tại bộ xử lý p. Chúng ta xác định thứ tự giữa các sự kiện khác nhau. Nếu chúng ta biết rằng sự kiện e1 xảy ra trước sự kiện e2, chúng ta viết e1<e2. Như vậy, nếu nguồn thông tin I cho chúng ta biết e1 đến trước e2 thì chúng ta viết e1<Ie2. Chúng ta xác định quan hệ xảy ra trước là sự đóng kín bên ngoài của thứ tự bộ xử lý và thông báo qua các thứ tự: Nếu e1<pe2 thì e1<He2. Nếu e1<me2 thì e1<He2. Nếu e1<He2 và e2<He3 thì e1<He3. Hình 3.1– Quan hệ xảy ra trước 3.Truyền thông nhân quả. Chúng ta thấy rằng tất cả các thông báo kiểu điểm tới điểm (point-to-point) được phân chia và gửi đi theo thư tự, có thể sử dụng nhãn thời gian duy trì liên kết nhân quả. Kết quả là giữ lại thông báo m gửi từ bộ xử lý p cho đến khi chúng ta đảm bảo rằng không có thông báo m’<Hm sẽ được phân chia từ bất cứ bộ xử lý nào. Mỗi một bộ xử lý p giữ một mảng earliest[1…M] cất trong phạm vi thấp nhất trong nhãn thời gian của các thông báo mà có thể được phân chia ra từ các bộ xử lý khác nhau. Mỗi bộ xử lý giữ một mảng các khối hàng đợi thông báo blocked[1…M] và một hàng đợi FIFO cho các thông báo từ mỗi bộ xử lý khác. Giải thuật để phân chia thông báo nhân quả được thấy trong giải thuật dưới đây: Giải thuật 1: Phân phát thông báo nhân quả Initially, each earliest[k] is set to the 1k timestamp, k=1…M each bloked[k] is set to {},k=1…M On the receipt of message m from processor p delivery_list={} if (blocked[p] is empty) earliest[p]=m.timestamp Add m to the tail of blocked[p] while (there is a k such that blocked[k] is not empty), and for every i=1…M, except for k and Seft, not_earlier(earliest[i],earliest[k],i)) remove the message at the head of blocked[k], put it in delivery_list if blocked[k] is not empty set earliest[k] to m’.timestamp, where m’ is at the head of blocked[k] else increment earliest[k] by 1k Deliver the message in delivery_list, in causal order Nhãn thời gian của thông báo sớm nhất có thể được phân chia từ bộ xử lý k được nạp trong earliest[k]. Biến earliest[k] được bắt đầu từ lk là nhãn thời gian nhỏ nhất mà bộ xử lý pk có thể được gắn vào một thông báo. Khi một bộ xử lý nhận thông báo m từ bộ xử lý p, thông báo được đặt vào hàng đợi blocked[p] và giữ ở đó cho tới khi nó an toàn để phân chia. Nếu không có thông báo trong blocked[p] thì earliest[p] là tập m.timestamp, bởi vì chúng ta bây giờ biết rằng không có thông báo sớm hơn được phân chia từ p. Một thông báo không bị chặn chỉ nếu không có thông báo với nhãn thời gian sớm hơn có thể được phân chia từ các bộ xử lý khác. Có nghĩa là, thông báo m tại đầu của blocked[p] không bị chặn chỉ nếu không có earliest[i] mà nhỏ hơn m.timestamp=earliest[k]. Từ khi m có thể được phân chia, chúng ta cần cập nhật earliest[k]. Nếu blocked[k] là không trống, thông báo sớm nhất có thể được phân chia từ k là thông báo tiếp theo trong blocked[k]. Cách khác, thông báo sớm nhất có thể tới từ bộ xử lý k phải có nhãn thời gian tại ít nhất lk lớn hơn m.timestamp = earliest[k]. 4.Quản lý bản sao dữ liệu. Quản lý bản sao dữ liệu là xây dựng các khối cơ bản cho các hoạt động của hệ phân tán. Các cơ sở dữ liệu phân tán có mục đích quản lý dữ liệu là chính. Nhiều thành phần hệ thống như dịch vụ tên hay dịch vụ file được thiết kế để cất giữ và xây dựng lại dữ liệu một cách phù hợp. Các thành phần của việc tính toán cần duy trì kết quả trạng thái hiện thời của việc tính toán. Có các kỹ thuật cơ sở dữ liệu để quản lý dữ liệu bản sao sau: Đăng ký và khôi phục cơ sở dữ liệu. Xác nhận hai giai đoạn. Xác nhận ba giai đoạn. 5. Quản lý và chọn lọc lỗi. Để quản lý các lỗi tốt nhất xảy ra, chúng ta thường đề cập đến hai giải thuật chính của Garcia-Molina. Hai giải thuật chính đó là: giải thuật bắt buộc(Bully) và giải thuật được mời (invitation). Giải thuật bắt buộc (bully). Giải thuật bao gồm hai giai đoạn chính: Hệ thống con phân chia thông báo phân chia tất cả các thông báo trong Tm giây của việc gửi thông báo. Các nút trả lời trong Tp giay phân phát chúng Dựa vào nguyên tắc trên chúng ta có thể phát hiện lỗi tại các máy dựa vào thời gian trả lời là: T>2 Tm+ Tp. Dựa vào đó ta có thể phát hiện và khôi phục. Giải thuật được mời (Invitation). Nếu chúng ta thừa nhận khả năng mà mạng và các bộ xử lý phải trải qua các độ trễ tuỳ ý, nó không hiểu hơn để nói về bộ xử lý khởi tạo toàn cục. Nếu có phân chia mạng, bộ xử lý khởi tạo sẽ xuất hiện trong cả hai phần. Hai bộ xử lý trong cùng một phần có thể không liên kết với nhau và như vậy cả hai tự khai báo. Nếu một bộ xử lý không thể tạo ra sự đảm nhận an toàn về điều chỉnh các sự kiện hệ thống, một bộ xử lý đang triển các giải thuật cho hệ thống không đồng bộ. Từ khi khai báo người dẫn dầu toàn bộ chứa đầy nguy hiểm, chúng ta cần xem xét lại những gì chúng ta giải thích bằng bộ xử lý khởi tạo. Bộ xử lý khởi tạo cần hướng dẫn một nhóm bộ xử lý qua việc tính toán phân tán. Sau đây, nó cảm thấy ràng buộc xử lý khởi tạo tới nhóm mà nó phân phối. Hơn nữa để dẫn đầu, bộ xử lý khởi tạo đảm bảo rằng những bộ xử lý khác trong nhóm đang thực hiện cùng một sơ đồ. Bộ xử lý khởi tạo sẽ tạo ra nhưng bộ đôi nhưng với sơ đồ khác quanh thời gian thứ hai. Đối với nguyên nhân này, nó thuận lợi tạo ra những nhóm giống nhay rõ rành với số nhóm. Sau đây là một số kết quả giống nhau và khác nhau giữa hai giả thuật trên: Cấu trúc logic: giải thuật bắt buộc đơn giản và hiệu quả bởi vì nó bắt phải chịu cấu trúc logic trên các bộ sử lý. Có lẽ mất thời gian cho các nhóm liên kết hợp khi dùng giải thuật được mời bởi vì không có định nghĩa cấu trúc phù hợp trên chúng. Đồng bộ chống lại không đồng bộ: giả thuật bắt buộc dùng kỹ thuật thúc đẩy thông tin từ tất cả các bộ xử lý khác, như vậy nó cảm thấy giống với giải thuật chọn động phân tán. Nó thực hiện hiệu quả việc đưa ra đường bao thời gian đáp ứng để xây dựng giải thuật đơn giản. Giải thuật được mời làm việc chính xác trong sự xuất hiện thời gian lỗi và đó là giải thuật thực tế. Sự chắc chắn trong liên kết: từ khi có thể có vài nhóm, sự chắc chắn là lquan hệ tới nhóm. Các bộ xử lý không liên kết có thể bị loại bỏ một cách an toàn. Giải thuật được mời đưa ra việc sử dụng hiệu quả các số liên tiếp. Giải thuật rất đơn giản- bộ xử lý khởi tạo mời các nút khác tham gia nhóm của nó. 6. Đồng bộ và chọn lọc a. Sự loại trừ lẫn nhau phân tán Loại trừ lẫn nhau cần thiết cho các hoạt động như là truy nhập dữ liệu dùng chung và phân phối chương trình phân tán. Nghiên cứu các giải thuật loại trừ phân tán giúp cho việc nghiên cứu kỹ thuật thiết kế giải thuật phân tán. b. Giải thuật nhãn thời gian Giải thuật nhãn thời gian dùng nhãn thời gian của Lamport đảm bảo truy nhập chính xác tới phần tới hạn. Giao thức thực hiện bởi vì có một phương pháp ưu tiên của các yêu cầu có thể được sắp xếp toàn cục. Có một bộ xử lý cho phép từ các bộ xử lý khác đi vào phần tới hạn, và bộ xử lý này sẽ từ chối cho phép tới tất cả các bộ xử lý khác. Nhãn thời gian Lamport phục vụ như 1 đồng hồ toàn cục. Vì nó là thứ tự tuyệt đối, có sự sắp xếp toàn cục giữa tất cả các bộ xử lý đã yêu cầu phần tới hạn. Một cách chuyển giải thuật dễ thấy trong giao thức là để mỗi bộ xử lý báo yêu cầu của nó đi vào phần tới hạn. Tất cả các bộ xử lý khác phải trả lời, đưa ra các yêu cầu hiện thời. Các trả lời này mang nhãn thời gian tại bên trả lời yêu cầu phần tới hạn hay giá trị không nếu bên trả lời không đợi hay sử dụng phần tới hạn. Khi bộ xử lý đi ra phần tới hạn, nó báo cho tất cả các bộ xử lý khác. Bằng cách xem xét các thông tin này, mỗi bộ xử lý có thể đặt hàng đợi ưu tiên giống nhau của các bộ xử lý đợi đi vào phần tới hạn. Khi bộ xử lý tìm thấy hàng đợi ưu tiên, nó biết rằng không có bộ xử lý khác nghĩ rằng nó ở đầu của hàng đợi ưu tiên, như vậy nó an toàn đi vào phần tới hạn. Các biến dùng trong giải thuật Ricarat và Agrawala timestamp currentime Thời gian Lamport hiện thời timestamp my_timestamp Nhãn thời gian yêu cầu integer reply_count Số hiệu cho phép cần tập hợp trước khi vào phần tới hạn CS(critical section). boolean is_requesting Đúng nếu đang yêu cầu hay dùng CS boolean reply_deffered[M] reply_deffered[i] đúng nếu trì hoãn trả lời yêu cầu của bộ xử lý j Giả sử bộ xử lý p gửi yêu cầu đến bộ xử lý q. Bộ xử lý p sẽ bị chặn ít nhất chođến khi có trả lời của q.Nếu q có yêu cầu ưu tiên cao hơn p, p sẽ bị chặn cho đến khi q tách ra khỏi phần tới hạn. Bộ xử lý q biết quan hệ ưu tiên của các yêu cầu; do vậy không cần đến vòng liên kết. Giải thuật 2 vòng thực hiện như sau : Khi bộ xử lý muốn đi vào phần tới hạn, nó ghi lại nhãn thời gian hiện thời và gửi yêu cầu tới tất cả bộ xử lý khác. Khi bộ xử lý nhận yêu cầu mà nó sẽ cấp, nó gửi trả lời tới bên yêu cầu. Khi bộ xử lý nhận một yêu cầu muộn hơn chủ của nó, nó sẽ từ chối yêu cầu. Khi đó bộ xử lý chỉ cần làm trễ việc gửi trả lời tới bên yêu cầu mà không cần gửi thông báo bắt đầu. Khi bộ xử lý nhận các trả lời của tất cả các yêu cầu của nó, nó biết yêu cầu của nó sớm hơn tất cả các người khác và nó đi vào phần tới hạn. Khi rời khỏi phần tới hạn, nó gửi các yêu cầu mà nó đã chậm lại. Dưới đây là các giải thuật yêu cầu token, giám sát phần tới hạn Giải thuật yêu cầu phần tới hạn Request_CS() my_timestamp= current_timestamp is_requesting=TRUE reply_pending=M-1 for every other processor j, send(j,REMOTE_REQUEST;my_timestamp) wait until reply_pending is 0 Giải thuật cho nhánh giám sát phần tới hạn CS_Monitor(): wait until a REMOTE_REQUEST or a REPLY message is received REMOTE_REQUEST (sender;request_time): let j be the sender of the REMOTE_REQUEST message. if( not is_requesting or my_timestamp>request_timestamp) send(j,REPLY) else reply_deffered[j]=TRUE REPLY(sender): reply_pending=reply_pending-1 Để tách ra khỏi phần tới hạn,bộ xử lý xử lý tất cả các trả lời trì hoãn của nó. Sau đây là giải thuật Giải thuật giải phóng phần tới hạn Release_CS() is_requesting=FALSE for j=1 through M if reply_deffered[j]=TRUE send (j,REPLY) reply_deffered[j]=FALSE c. Cấu trúc vật lý cố định Cách tiếp cận khác đầy đủ hơn để đồng bộ hoá là sự truyền token giữa các bộ xử lý. Token đưa ra sự cho phép đồng bộ. Nếu bộ xử lý có được token, nó được phép đi vào phần tới hạn. Token có thể tới tất cả các bộ xử lý góp phần vào sự đồng bộ hoá trong thưòi gian hợp lý sau khi bộ xử lý yêu cầu token. Một cách để đảm bảo token có thể đi tới tất cả các bộ xử lý là đặt cấu trúc vật lý trong các bộ xử lý và yêu cầu token đi theo cấu trúc vật lý. Cấu trúc vật lý là một ring có sự lan truyền token. Nếu bộ xử lý giữ token nó được phép đi vào phần tới hạn. Nếu bộ xử lý muốn thường xuyên đi vào phần tới hạn khi token đi tới, token truyền trong ring là một giải thuật đồng bộ. Token có thể đi qua hơn M lần trước khi bộ xử lý đi vào phần tới hạn. Tiếp theo ta cần giải quyết 2 vấn đề để yêu cầu thông qua token như thế nào và để token thông qua bộ xử lý tiếp theo như thế nào để vào phần tới hạn. Khi bộ xử lý yêu cầu cho phép đi vào phần tới hạn, nó gửi yêu cầu trong hướng current_dir. Khi bộ xử lý nhạn được yêu cầu đi vào phần tới hạn, nó gửi tiếp yêu cầu đi vào phần tới hạn theo hướng current_dir nếu chưa sẵn sàng. Các bộ xử lý trong đường dẫn từ bên yêu cầu tới token phải ghi đường dẫn quay lại cho token. Bộ xử lý nhận được yêu cầu, đặt yêu cầu vào trong hàng đợi FIFO. Chú ý đầu hàng đợi FIFO chỉ rõ đường dẫn quay lại. Khi bộ xử lý giải phóng token, nó kiểm tra thấy nếu có bất cứ yêu cầu từ chối cho token. Các yêu cầu này sẽ được cất trong hàng đợi FIFO. Nếu có yêu cầu từ chối, token được gửi tới láng giềng tại đầu FIFO. Nếu có yêu cầu khác trong FIFO, bộ xử lý bắt đầu thoả mãn yêu cầu bị từ chối. Các biến dùng bởi giải thuật cấu trúc vật lý cố định Token_hldr Đúng nếu bộ xử lý giữ lệnh bài. Incs Đúng nếu bộ xử lý đang dùng phần tới hạn current_dir Bên cạnh là gốc của cây con giữ lệnh bài requestQ FIFO cất giứ tên của các bộ xử lý bên cạnh. Các phép toán trên requestQ Nq(neighbor) Thêm bộ xử lý bên cạnh vào requestQ Dq() Di chuyển và quay lại đầu của requestQ ismt() Quay lại đúng nếu requestQ. Giao thức bao gồm các thủ tục yêu cầu và giải phóng token. Mỗi bộ xử lý thực hiện 1 luồng để trả lời các thông báo REQUEST và TOKEN. Giải thuật yêu cầu và giải phóng phần tới hạn Request_CS() if not Token_hldr if ismt() send (current_dir,REQUEST) Nq(self) wait until Token_hldr Incs=True Release_CS() Incs=False if not ismt() current_dir=Dq() send(current_dir, TOKEN) Token_hldr=False if not ismt() send (current_dir,REQUEST) Giải thuật thực hiện bằng nhánh giám sát phần tới hạn Monitor_CS() while (True) wait for a REQUEST or a TOKEN message. REQUEST : If Token_hldr if Incs Nq(sender) else if ismt() send(current_dir, TOKEN) Token_hldr =False else send (current_dir,REQUEST) Nq(sender) TOKEN: current_dir=Dq() current_dir = self Token_hldr =True else send(current_dir, TOKEN) if not ismt() send (current_dir,REQUEST). PHẦN IV:  BẢO VỆ VÀ AN TOÀN HỆ THỐNG An toàn và bảo vệ hệ thống là chức năng không thể thiếu của các hệ điều hành hiện đại phân tán. Trong bài học này, chúng ta sẽ làm quen với các khái niệm về tổ chức an toàn hệ thống, cũng như các cơ chế bảo vệ hỗ trợ việc triển khai các chiến lược này. I. mỤC TIÊU BẢO VỆ HỆ THỐNG (Protection). Mục tiêu của việc bảo vệ hệ thống là: Bảo vệ chống lỗi của tiến trình : khi có nhiều tiến trình cùng hoạt động, lỗi của một tiến trình j phải được ngăn chặn không cho lan truyền trên hệ thống làm ảnh hưởng đến các tiến trình khác. Đặc biệt, qua việc phát hiện các lỗi tiềm ẩn trong các thành phần của hệ thống có thể tăng cường độ tin cậy hệ thống ( reliability). Chống sự truy xuất bất hợp lệ : Bảo đảm các bộ phận tiến trình sử dụng tài nguyên theo một cách thức hợp lệ được qui định cho nó trong việc khai thác các tài nguyên này. Vai trò của bộ phận bảo vệ trong hệ thống là cung cấp một cơ chế để áp dụng các chiến lược quản trị việc sử dụng tài nguyên. Cần phân biệt khái niệm cơ chế và chiến lược: Cơ chế : xác định làm thế nào để thực hiện việc bảo vệ, có thể có các cơ chế phần mềm hoặc cơ chế phần cứng. Chiến lược: quyết định việc bảo vệ được áp dụng như thế nào : những đối tượng nào trong hệ thống cần được bảo vệ, và các thao tác thích hợp trên các đối tượng này Để hệ thống có tính tương thích cao, cần phân tách các cơ chế và chiến lược được sử dụng trong hệ thống. Các chiến lược sử dụng tài nguyên là khác nhau tùy theo ứng dụng, và thường dễ thay đổi. Thông thường các chiến lược được lập trình viên vận dụng vào ứng dụng của mình để chống lỗi truy xuất bất hợp lệ đến các tài nguyên, trong khi đó hệ thống cung cấp các cơ chế giúp người sử dụng có thể thực hiện được chiến lược bảo vệ của mình. II. MIỀN BẢO VỆ (Domain of Protection ) II.1. Khái niệm Một hệ thống máy tính được xem như một tập các đối tượng (objects). Một đối tượng có thể là một bộ phận phần cứng ( CPU, bộ nhớ, ổ đĩa...) hay một thực thể phần mềm ( tập tin, chương trình, semaphore...). Mỗi đối tượng có một định danh duy nhất để phân biệt với các đối tượng khác trong hệ thống, và chỉ được truy xuất đến thông qua các thao tác được định nghĩa chặt chẽ và được qui định ngữ nghĩa rõ ràng. Các thao tác có thể thực hiện được trên một đối tượng được xác định cụ thể tùy vào đối tượng. Để có thể kiểm soát được tình hình sử dụng tài nguyên trong hệ thống, hệ điều hành chỉ cho phép các tiến trình được truy xuất đến các tài nguyên mà nó có quyền sử dụng, hơn nữa tiến trình chỉ được truy xuất đến các tài nguyên cần thiết trong thời điểm hiện tại để nó hoàn thành tác vụ (nguyên lý need-to-know) nhăm hạn chế các lỗi truy xuất mà tiến trình có thể gây ra trong hệ thống. Mỗi tiến trình trong hệ thống đều hoạt động trong một miền bảo vệ (protection domain) nào đó. Một miền bảo vệ sẽ xác định các tài nguyên ( đối tượng) mà những tiến trình hoạt động trong miền bảo vệ này có thể sử dụng, và các thao tác hợp lệ các tiến trình này có thể thực hiện trên những tài nguyên đó. II.2. Cấu trúc của miền bảo vệ Các khả năng thao tác trên một đối tượng được gọi là quyền truy xuất (access right). Một miền bảo vệ là một tập các quyền truy xuất, mỗi quyền truy xuất được định nghĩa bởi một bộ hai thứ tự . Các miền bảo vệ khác nhau có thể giao nhau một số quyền truy xuất : Hình vẽ 4.1 Hệ thống với 3 miền bảo vệ Mối liên kết giữa một tiến trình và một miền bảo vệ có thể tĩnh hay động : Liên kết tĩnh : trong suốt thời gian sống của tiến trình, tiến trình chỉ hoạt động trong một miền bảo vệ. Trong trường hợp tiến trình trải qua các giai đoạn xử lý khác nhau, ở mỗi giai đoạn tiến trình có thể thao tác trên những tập tài nguyên khác nhau bằng các thao tác khác nhau. Tuy nhiên, nếu sử dụng liên kết tĩnh, rõ ràng là ngay từ đầu miền bảo vệ đã phải đặc tả tất cả các quyền truy xuất qua các giai đoạn cho tiến trình, điều này có thể khiến cho tiến trình có dư quyền trong một giai đoạn nào đó, và vi phạm nguyên lý need-to-know. Để có thể tôn trọng nguyên lý này, khi đó cần phải có khả năng cập nhật nội dung miền bảo vệ để có thể phản ánh các quyền tối thiểu của tiến trình trong miền bảo vệ tại một thời điểm! Liên kết động : cơ chế này cho phép tiến trình chuyển từ miền bảo vệ này sang miền bảo vệ khác trong suốt thời gian sống của nó. Để tiếp tục tuân theo nguyên lý need-to-know, thay vì sửa đổi nội dung của miền bảo vệ, có thể tạo ra các miền bảo vệ mới với nội dung thay đổi qua từng giai đoạn xử lý của tiến trình, và chuyển tiến trình sang hoạt động trong miền bảo vệ phù hợp theo từng thời điểm. Một miền bảo vệ có thể được xây dựng cho: Một người sử dụng : trong trường hợp này, tập các đối tượng được phép truy xuất phụ thuộc vào định danh của người sử dụng, miền bảo vệ được chuyển khi thay đổi người sử dụng. Một tiến trình : trong trường hợp này, tập các đối tượng được phép truy xuất phụ thuộc vào định danh của tiến trình, miền bảo vệ được chuyển khi quyền điều khiển được chuyển sang tiến trình khác. Một thủ tục : trong trường hợp này, tập các đối tượng được phép truy xuất là các biến cục bộ được định nghĩa bên trong thủ tục, miền bảo vệ được chuyển khi thủ tục được gọi. III. An toàn hỆ THỐNG (Security) Bảo vệ hệ thống (protection) là một cơ chế kiểm soát việc sử dụng tài nguyên của các tiến trình hay người sử dụng để đối phó với các tình huống lỗi có thể phát sinh từ trong hệ thống. Trong khi đó khái niệm an toàn hệ thống (security) muốn đề cập đến mức độ tin cậy mà hệ thống duy trì khi phải đối phó không những với các vấn đề nội bộ, mà còn cả với những tác hại đến từ môi trường ngoài. 1. Các vấn đề về an toàn hệ thống Hệ thống được gọi là an toàn nếu các tài nguyên được sử dụng đúng như quy ước trong mọi hoàn cảnh. Kém may mắm là điều này hiếm khi đạt được trong thực tế ! Thông thường, an toàn bị vi phạm vì các nguyên nhân vô tình hay cố ý phá hoại. Việc chống đỡ các phá hoại cố ý là rất khó khăn và gần như không thể đạt hiệu quả hoàn toàn. Bảo đảm an toàn hệ thống ở cấp cao chống lại các tác hại từ môi trường ngoài như hoả hoạn, mất điện, phái hoại...cần được thực hiện ở 2 mức độ vật lý (trang bị các thiết bị an toàn cho vị trí đạt hệ thống...) và nhân sự (chọn lọc cẩn thận những nhân viên làm việc trong hệ thống...). Nếu an toàn môi trường được bảo đảm khá tốt, an toàn của hệ thống sẽ được duy trì tốt nhờ các cơ chế của hệ điều hành (với sự trợ giúp của phần cứng). Lưu ý rằng nếu bảo vệ hệ thống có thể đạt độ tin cậy 100%, thì các cơ chế an toàn hệ thống được cung cấp chỉ với hy vọng ngăn chặn bớt các tình huống bất an hơn là đạt đến độ an toàn tuyệt đối. 2. Kiểm định danh tính (Authentication) Để đảm bảo an toàn, hệ điều hành cần giải quyết tốt vấn đề chủ yếu là kiểm định danh tính (authentication). Hoạt động của hệ thống bảo vệ phụ thuộc vào khả năng xác định các tiến trình đang xử lý. Khả năng này, đến lượt nó, lại phụ thuộc vào việc xác định được người dùng đang sử dụng hệ thống để có thể kiểm tra người dùng này được cho phép thao tác tr