Giáo trình Hệ điều hành (Phần 2)

Nội dung text: Giáo trình Hệ điều hành (Phần 2)

1. BÀI 6 :QUẢN LÝ BỘ NHỚ I. Bối cảnh Thông thường, một chương trình được lưu trữ trên đĩa như một tập tin nhị phân có thể xử lý. Để thực hiện chương trình, cần nạp chương trình vaò bộ nhớ chính, tạo lập tiến trình tương ứng để xử lý . Hàng đợi nhập hệ thống là tập hợp các chương trình trên đĩa đang chờ được nạp vào bộ nhớ để tiến hành xử lý. Các địa chỉ trong chương trình nguồn là địa chỉ tượng trưng , vì thế, một chương trình phải trải qua nhiều giai đoạn xử lý để chuyển đổi các địa chỉ này thành các địa chỉ tuyệt đối trong bộ nhớ chính. Có thể thực hiện kết buộc các chỉ thị và dữ liệu với các địa chỉ bộ nhớ vào một trong những thời điểm sau : Thời điểm biên dịch: nếu tại thời điểm biên dịch, có thể biết vị trí mà tiến trình sẽ thường trú trong bộ nhớ, trình biên dịch có thể phát sinh ngay mã với các địa chỉ tuyệt đối. Tuy nhiên, nếu về sau có sự thay đổi vị trí thường trú lúc đầu của chương trình, cần phải biên dịch lại chương trình. Thời điểm nạp : nếu tại thời điểm biên dịch, chưa thể biết vị trí mà tiến trình sẽ thường trú trong bộ nhớ, trình biên dịch cần phát sinh mã tương đối (translatable). Sự liên kết địa chỉ được trì hoãn đến thời điểm chương trình được nạp vào bộ nhớ, lúc này các địa chỉ tương đối sẽ được chuyển thành địa chỉ tuyệt đối do đã biết vị trí bắt đầu lưu trữ tiến trình. Khi có sự thay đổi vị trí lưu trữ, chỉ cần nạp lại chương trình để tính toán lại các địa chỉ tuyệt đối, mà không cần biên dịch lại. Thời điểm xử lý : nếu có nhu cầu di chuyển tiến trình từ vùng nhớ này sang vùng nhớ khác trong quá trình tiến trình xử lý, thì thời điểm kết buộc địa chỉ phải trì hoãn đến tận thời điểm xử lý. Để thực hiện kết buộc địa chỉ vào thời điểm xử lý, cần sử dụng cơ chế phần cứng đặc biệt. II. Không gian địa chỉ và không gian vật lý Một trong những hướng tiếp cận trung tâm nhằm tổ chức quản lý bộ nhớ một cách hiệu qủa là đưa ra khái niệm không gian địa chỉ được xây dựng trên không gian nhớ vật lý, việc tách rời hai không gian này giúp hệ điều hành dễ dàng xây dựng các cơ chế và chiến lược quản lý bộ nhớ hữu hiệu : Địa chỉ logic – còn gọi là địa chỉ ảo , là tất cả các địa chỉ do bộ xử lý tạo ra. Địa chỉ vật lý - là địa chỉ thực tế mà trình quản lý bộ nhớ nhìn thấy và thao tác. Không gian địa chỉ – là tập hợp tất cả các địa chỉ ảo phát sinh bởi một chương trình. Không gian vật lý – là tập hợp tất cả các địa chỉ vật lý tương ứng với các địa chỉ ảo. Địa chỉ ảo và địa chỉ vật lý là như nhau trong phương thức kết buộc địa chỉ vào thời điểm biên dịch cũng như vào thời điểm nạp. Nhưng có sự khác biệt giữa địa chỉ ảo và địa chỉ vật lý trong phương thức kết buộc vào thời điểm xử lý. MMU (memory-management unit) là một cơ chế phần cứng được sử dụng để thực hiện chuyển đổi địa chỉ ảo thành địa chỉ vật lý vào thời điểm xử lý. Chương trình của người sử dụng chỉ thao tác trên các địa chỉ ảo, không bao giờ nhìn thấy các địa chỉ vật lý . Địa chỉ thật sự ứng với vị trí của dữ liệu trong bô nhớ chỉ được xác định khi thực hiện truy xuất đến dữ liệu. III. Cấp phát liên tục III.1. Mô hình Linker_Loader 49
2. Ý tưởng : Tiến trình được nạp vào một vùng nhớ liên tục đủ lớn để chứa toàn bộ tiến trình. Tại thời điểm biên dịch các địa chỉ bên trong tiến trình vẫn là địa chỉ tương đối. Tại thời điểm nạp, Hệ điều hành sẽ trả về địa chỉ bắt đầu nạp tiến trình, và tính toán để chuyển các địa chỉ tương đối về địa chỉ tuyệt đối trong bộ nhớ vật lý theo công thức địa chỉ vật lý = địa chỉ bắt đầu + địa chỉ tương đối. Thảo luận: Thời điểm kết buôc địa chỉ là thời điểm nạp, do vậy sau khi nạp không thể dời chuyển tiến trình trong bộ nhớ . Không có khả năng kiểm soát địa chỉ các tiến trình truy cập, do vậy không có sự bảo vệ. III.2. Mô hình Base &Bound Ý tưởng : Tiến trình được nạp vào một vùng nhớ liên tục đủ lớn để chứa toàn bộ tiến trình. Tại thời điểm biên dịch các địa chỉ bên trong tiến trình vẫn là địa chỉ tương đối. Tuy nhiên bổ túc vào cấu trúc phần cứng của máy tính một thanh ghi nền (base register) và một thanh ghi giới hạn (bound register). Khi một tiến trình được cấp phát vùng nhớ, nạp vào thanh ghi nền địa chỉ bắt đầu của phân vùng được cấp phát cho tiến trình, và nạp vào thanh ghi giới hạn kích thước của tiến trình. Sau đó, mỗi địa chỉ bộ nhớ được phát sinh sẽ tự động được cộng với địa chỉ chứa trong thanh ghi nền để cho ra địa chỉ tuyệt đối trong bộ nhớ, các địa chỉ cũng được đối chiếu với thanh ghi giới hạn để bảo đảm tiến trình không truy xuất ngoài phạm vi phân vùng được cấp cho nó. Thảo luận: Một ưu điểm của việc sử dụng thanh ghi nền là có thể di chuyển các chương trình trong bộ nhớ sau khi chúng bắt đầu xử lý, mỗi khi tiến trình được di chuyển đến một vị trí mới, chỉ cần nạp lại giá trị cho thanh ghi nền, các địa chỉ tuyệt đối sẽ được phát sinh lại mà không cần cập nhật các địa chỉ tương đối trong chương trình 50
3. Chịu đựng hiện tượng phân mảnh ngoại vi( external fragmentation ) : khi các tiến trình lần lượt vào và ra khỏi hệ thống, dần dần xuất hiện các khe hở giữa các tiến trình. Đây là các khe hở được tạo ra do kích thước của tiến trình mới được nạp nhỏ hơn kích thước vùng nhớ mới được giải phóng bởi một tiến trình đã kết thúc và ra khỏi hệ thống. Hiện tượng này có thể dẫn đến tình huống tổng vùng nhớ trống đủ để thoả mãn yêu cầu, nhưng các vùng nhớ này lại không liên tục ! Người ta có thể áp dụng kỹ thuật « dồn bộ nhớ » (memory compaction ) để kết hợp các mảnh bộ nhớ nhỏ rời rạc thành một vùng nhớ lớn liên tục. Tuy nhiên, kỹ thuật này đòi hỏi nhiều thời gian xử lý, ngoài ra, sự kết buộc địa chỉ phải thực hiện vào thời điểm xử lý, vì các tiến trình có thể bị di chuyển trong quá trình dồn bộ nhớ. Hai thanh ghi hổ trợ chuyển đổi địa chỉ Vấn đề nảy sinh khi kích thước của tiến trình tăng trưởng trong qúa trình xử lý mà không còn vùng nhớ trống gần kề để mở rộng vùng nhớ cho tiến trình. Có hai cách giải quyết: Dời chỗ tiến trình : di chuyển tiến trình đến một vùng nhớ khác đủ lớn để thỏa mãn nhu cầu tăng trưởng của tiến trình. Cấp phát dư vùng nhớ cho tiến trình : cấp phát dự phòng cho tiến trình một vùng nhớ lớn hơn yêu cầu ban đầu của tiến trình. Một tiến trình cần được nạp vào bộ nhớ để xử lý. Trong các phương thức tổ chức trên đây, một tiến trình luôn được lưu trữ trong bộ nhớ suốt quá trình xử lý của nó. Tuy nhiên, trong trường hợp tiến trình bị khóa, hoặc tiến trình sử dụng hết thời gian CPU dành cho nó, nó có thể được chuyển tạm thời ra bộ nhớ phụ và sau này được nạp trở lại vào bộ nhớ chính để tiếp tục xử lý. Các cách tổ chức bộ nhớ trên đây đều phải chịu đựng tình trạng bộ nhớ bị phân mảnh vì chúng đều tiếp cận theo kiểu cấp phát một vùng nhớ liên tục cho tiến trình. Như đã thảo luận, có thể sử dụng 51
4. kỹ thuật dồn bộ nhớ để loại bỏ sự phân mảnh ngoại vi, nhưng chi phí thực hiện rất cao. Một giải pháp khác hữu hiệu hơn là cho phép không gian địa chỉ vật lý của tiến trình không liên tục, nghĩa là có thể cấp phát cho tiến trình những vùng nhớ tự do bất kỳ, không cần liên tục. Phân mảnh ngoại vi IV. Cấp phát không liên tục IV.1. Phân đoạn (Segmentation) Ý tưởng: quan niệm không gian địa chỉ là một tập các phân đoạn (segments) – các phân đoạn là những phần bộ nhớ kích thước khác nhau và có liên hệ logic với nhau. Mỗi phân đoạn có một tên gọi (số hiệu phân đoạn) và một độ dài. Người dùng sẽ thiết lập mỗi địa chỉ với hai giá trị : . Hình 4.17 Mô hình phân đoạn bộ nhớ Cơ chế MMU trong kỹ thuật phân đoạn: Cần phải xây dựng một ánh xạ để chuyển đổi các địa chỉ 2 chiều được người dùng định nghĩa thành địa chỉ vật lý một chiều. Sự chuyển đổi này được thực hiện qua một bảng phân đoạn. Mỗi thành phần trong bảng phân đoạn bao gồm một thanh ghi nền và một thanh ghi giới hạn. Thanh ghi nền lưu trữ địa chỉ vật lý nơi bắt đầu phân đoạn trong bộ nhớ, trong khi thanh ghi giới hạn đặc tả chiều dài của phân đoạn. Hình 4.18 Cơ chế phần cứng hổ trợ kĩ thuật phân đoạn Chuyển đổi địa chỉ: Mỗi địa chỉ ảo là một bộ : 52
5. số hiệu phân đoạn s : được sử dụng như chỉ mục đến bảng phân đoạn địa chỉ tương đối d : có giá trị trong khoảng từ 0 đến giới hạn chiều dài của phân đoạn. Nếu địa chỉ tương đối hợp lệ, nó sẽ được cộng với giá trị chứa trong thanh ghi nền để phát sinh địa chỉ vật lý tương ứng. Cài đặt bảng phân đoạn: Hình 4.19 Hệ thống phân đoạn Có thể sử dụng các thanh ghi để lưu trữ bảng phân đoạn nếu số lượng phân đoạn nhỏ. Trong trường hợp chương trình bao gồm quá nhiều phân đoạn, bảng phân đoạn phải được lưu trong bộ nhớ chính. Một thanh ghi nền bảng phân đoạn (STBR) chỉ đến địa chỉ bắt đầu của bảng phân đoạn. Vì số lượng phân đoạn sử dụng trong một chương trình biến động, cần sử dụng thêm một thanh ghi đặc tả kích thước bảng phân đoạn (STLR). Với một địa chỉ logic , trước tiên số hiệu phân đoạn s được kiểm tra tính hợp lệ (s <STLR). Kế tiếp, cộng giá trị s với STBR để có được địa chỉ địa chỉ của phần tử thứ s trong bảng phân đoạn (STBR+s). Điạ chỉ vật lý cuối cùng là (STBR+s + d) Hình 4.20 Sử dụng STBR, STLR và bảng phân đoạn Bảo vệ: Một ưu điểm đặc biệt của cơ chế phân đoạn là khả năng đặc tả thuộc tính bảo vệ cho mỗi phân đoạn. Vì mỗi phân đoạn biễu diễn cho một phần của chương trình với ngữ nghĩa được người dùng xác định, người sử dụng có thể biết được một phân đoạn chứa đựng những gì bên trong, do vậy họ có thể đặc tả các thuộc tính bảo vệ thích hợp cho từng phân đoạn. 53
6. Cơ chế phần cứng phụ trách chuyển đổi địa chỉ bộ nhớ sẽ kiểm tra các bit bảo vệ được gán với mỗi phần tử trong bảng phân đoạn để ngăn chặn các thao tác truy xuất bất hợp lệ đến phân đoạn tương ứng. Chia sẻ phân đoạn: Hình 4.21 Chia sẻ code trong hệ phân đoạn Một ưu điểm khác của kỹ thuật phân đoạn là khả năng chia sẻ ở mức độ phân đoạn. Nhờ khả năng này, các tiến trình có thể chia sẻ với nhau từng phần chương trình ( ví dụ các thủ tục, hàm), không nhất thiết phải chia sẻ toàn bộ chương trình như trường hợp phân trang. Mỗi tiến trình có một bảng phân đoạn riêng, một phân đoạn được chia sẻ khi các phần tử trong bảng phân đoạn của hai tiến trình khác nhau cùng chỉ đến một vị trí vật lý duy nhất. Thảo luận: Phải giải quyết vấn đề cấp phát động: làm thế nào để thỏa mãn một yêu cầu vùng nhớ kích thước N ? Cần phải chọn vùng nhớ nào trong danh sách vùng nhớ tự do để cấp phát ? Như vậy cần phải ghi nhớ hiện trạng bộ nhớ để có thể cấp phát đúng. Có hai phương pháp quản lý chủ yếu : Quản lý bằng một bảng các bit : bộ nhớ được chia thành các đơn vị cấp phát, mỗi đơn vị được phản ánh bằng một bit trong bảng các bit, một bit nhận giá trị 0 nếu đơn vị bộ nhớ tương ứng đang tự do, và nhận giá trị 1 nếu đơn vị tương ứng đã được cấp phát cho một tiến trình. Khi cần nạp một tiến trình có kích thước k đơn vị, cần phải tìm trong bảng các bit một dãy con k bit nhận giá trị 0. Đây là một giải pháp đơn giản, nhưng thực hiện chậm nên ít được sử dụng. Hình 4.5 Quản lý bộ nhớ bằng bảng các bit Quản lý bằng danh sách: Tổ chức một danh sách các phân đoạn đã cấp phát và phân đoạn tự do, một phân đoạn có thể là một tiến trình (P) hay vùng nhớ trống giữa hai tiến trình (H). Hình 4.6 Quản lý bộ nhớ bằng danh sách Các thuật toán thông dụng để chọn một phân đoạn tự do trong danh sách để cấp phát cho tiến trình là : First-fit: cấp phát phân đoạn tự do đầu tiên đủ lớn. 54
7. Best-fit: cấp phát phân đoạn tự do nhỏ nhất nhưng đủ lớn để thõa mãn nhu cầu. Worst-fit : cấp phát phân đoạn tự do lớn nhất. Trong hệ thống sử dụng kỹ thuật phân đoạn , hiện tượng phân mảnh ngoại vi lại xuất hiện khi các khối nhớ tự do đều quá nhỏ, không đủ để chứa một phân đoạn. IV.2. Phân trang ( Paging): Ý tưởng: Phân bộ nhớ vật lý thành các khối (block) có kích thước cố định và bằng nhau, gọi là khung trang (page frame). Không gian địa chỉ cũng được chia thành các khối có cùng kích thước với khung trang, và được gọi là trang (page). Khi cần nạp một tiến trình để xử lý, các trang của tiến trình sẽ được nạp vào những khung trang còn trống. Một tiến trình kích thước N trang sẽ yêu cầu N khung trang tự do. Hình 4.8 Mô hình bộ nhớ phân trang Cơ chế MMU trong kỹ thuật phân trang: Cơ chế phần cứng hỗ trợ thực hiện chuyển đổi địa chỉ trong cơ chế phân trang là bảng trang (pages table). Mỗi phần tử trong bảng trang cho biết các địa chỉ bắt đầu của vị trí lưu trữ trang tương ứng trong bộ nhớ vật lý ( số hiệu khung trang trong bộ nhớ vật lý đang chứa trang ). p d m-n n Chuyển đổi địa chỉ: Mỗi địa chỉ phát sinh bởi CPU được chia thành hai phần: số hiệu trang (p): sử dụng như chỉ mục đến phần tử tương ứng trong bảng trang. địa chỉ tương đối trong trang (d): kết hợp với địa chỉ bắt đầu của trang để tạo ra địa chỉ vật lý mà trình quản lý bộ nhớ sử dụng. Kích thước của trang do phần cứng qui định. Để dễ phân tích địa chỉ ảo thành số hiệu trang và địa chỉ tương đối, kích thước của một trang thông thường là một lũy thừa của 2 (biến đổi trong phạm vi 512 bytes và 8192 bytes). Nếu kích thước của không gian địa chỉ là 2m và kích thước trang là 2 n, thì m-n bits cao của địa chỉ ảo sẽ biễu diễn số hiệu trang, và n bits thấp cho biết địa chỉ tương đối trong trang. Cài đặt bảng trang: Trong trường hợp đơn giản nhất, bảng trang một tập các thanh ghi được sử dụng để cài đặt bảng trang. Tuy nhiên việc sử dụng thanh ghi chỉ phù hợp với các bảng trang có kích thước nhỏ, nếu bảng trang có kích thước lớn, nó phải được lưu trữ trong bộ nhớ chính, và sử dụng một thanh ghi để lưu địa chỉ bắt đầu lưu trữ bảng trang (PTBR). 55
8. Theo cách tổ chức này, mỗi truy xuất đến dữ liệu hay chỉ thị đều đòi hỏi hai lần truy xuất bộ nhớ : một cho truy xuất đến bảng trang và một cho bản thân dữ liệu! Hình 4.10 Mô hình bộ nhớ phân trang Hình 4.11 Sử dụng thanh ghi nền trỏ đến bảng trang Có thể né tránh bớt việc truy xuất bộ nhớ hai lần bằng cách sử dụng thêm một vùng nhớ đặc biệt , với tốc độ truy xuất nhanh và cho phép tìm kiếm song song, vùng nhớ cache nhỏ này thường được gọi là bộ nhớ kết hợp (TLBs). Mỗi thanh ghi trong bộ nhớ kết hợp gồm một từ khóa và một giá trị, khi đưa đến bộ nhớ kết hợp một đối tượng cần tìm, đối tượng này sẽ được so sánh cùng lúc với các từ khóa trong bộ nhớ kết hợp để tìm ra phần tử tương ứng. Nhờ đặc tính này mà việc tìm kiếm trên bộ nhớ kết hợp được thực hiện rất nhanh, nhưng chi phí phần cứng lại cao. Trong kỹ thuật phân trang, TLBs được sử dụng để lưu trữ các trang bộ nhớ được truy cập gần hiện tại nhất. Khi CPU phát sinh một địa chỉ, số hiệu trang của địa chỉ sẽ được so sánh với các phần tử trong TLBs, nếu có trang tương ứng trong TLBs, thì sẽ xác định được ngay số hiệu khung trang tương ứng, nếu không mới cần thực hiện thao tác tìm kiếm trong bảng trang. Tổ chức bảng trang: 56
9. Mỗi hệ điều hành có một phương pháp riêng để tổ chức lưu trữ bảng trang. Đa số các hệ điều hành cấp cho mỗi tiến trình một bảng trang. Tuy nhiên phương pháp này không thể chấp nhận được nếu hệ điều hành cho phép quản lý một không gian địa chỉ có dung lượng quá (232, 264): trong các hệ thống như thế, bản thân bảng trang đòi hỏi một vùng nhớ qúa lớn! Có hai giải pháp cho vấn đề này: Phân trang đa cấp: phân chia bảng trang thành các phần nhỏ, bản thân bảng trang cũng sẽ được phân trang Bảng trang nghịch đảo: sử dụng duy nhất một bảng trang nghịch đảo cho tất cả các tiến trình . Mỗi phần tử trong bảng trang nghịch đảo phản ánh một khung trang trong bộ nhớ bao gồm địa chỉ logic của một trang đang được lưu trữ trong bộ nhớ vật lý tại khung trang này, cùng với thông tin về tiến trình đang được sỡ hữu trang. Mỗi địa chỉ ảo khi đó là một bộ ba Trong đó : idp là định danh của tiến trình p là số hiệu trang d là địa chỉ tương đối trong trang Mỗi phần tử trong bảng trang nghịch đảo là một cặp . Khi một tham khảo đến bộ nhớ được phát sinh, một phần địa chỉ ảo là được đưa đến cho trình quản lý bộ nhớ để tìm phần tử tương ứng trong bảng trang nghịch đảo, nếu tìm thấy, địa chỉ vật lý sẽ được phát sinh. Trong các trường hợp khác, xem như tham khảo bộ nhớ đã truy xuất một địa chỉ bất hợp lệ. Bảo vệ: Cơ chế bảo vệ trong hệ thống phân trang được thực hiện với các bit bảo vệ được gắn với mỗi khung trang. Thông thường , các bit này được lưu trong bảng trang , vì mỗi truy xuất đến bộ nhớ đều phải tham khảo đến bảng trang để phát sinh địa chỉ vật lý, khi đó, hệ thống có thể kiểm tra các thao tác truy xuất trên khung trang tương ứng có hợp lệ với thuộc tính bảo vệ của nó không. Ngoài ra, một bit phụ trội được thêm vào trong cấu trúc một phần tử của bảng trang : bit hợp lệ-bất hợp lệ (valid-invalid). Hợp lệ : trang tương ứng thuộc về không gian địa chỉ của tiến trình. Bất hợp lệ: trang tương ứng không nằm trong không gian địa chỉ của tiến trình, điều này có nghĩa 57
10. tiến trình đã truy xuất đến một địa chỉ không được phép. Hình 4.15 Cấu trúc một phần tử trong bảng trang Chia sẻ bộ nhớ trong cơ chế phân trang: Một ưu điểm của cơ chế phân trang là cho phép chia sẻ các trang giữa các tiến trình.Trong trường hợp này, sự chia sẻ được thực hiện bằng cách ánh xạ nhiều địa chỉ logic vào một địa chỉ vật lý duy nhất. Có thể áp dụng kỹ thuật này để cho phép có tiến trình chia sẻ một vùng code chung: nếu có nhiều tiến trình của cùng một chương trình, chỉ cần lưu trữ một đoạn code của chương trình này trong bộ nhớ, các tiến trình sẽ có thể cùng truy xuất đến các trang chứa code chung này. Lưu ý để có thể chia sẻ một đoạn code, đoạn code này phải có thuộc tính reenterable (cho phép một bản sao của chương trình được sử dụng đồng thời bởi nhiều tác vụ). Thảo luận: Kỹ thuật phân trang loại bỏ được hiện tượng phân mảnh ngoại vi : mỗi khung trang đều có thể được cấp phát cho một tiến trình nào đó có yêu cầu. Tuy nhiên hiện tượng phân mảnh nội vi vẫn có thể xảy ra khi kích thước của tiến trình không đúng bằng bội số của kích thước một trang, khi đó, trang cuối cùng sẽ không được sử dụng hết. Một khiá cạnh tích cực rất quan trọng khác của kỹ thuật phân trang là sự phân biệt rạch ròi góc nhìn của người dùng và của bộ phận quản lý bộ nhớ vật lý: - Góc nhìn của người sử dụng: một tiến trình của người dùng nhìn thấy bộ nhớ như là một không gian liên tục, đồng nhất và chỉ chứa duy nhất bản thân tiến trình này. - Góc nhìn của bộ nhớ vật lý: một tiến trình của người sử dụng được lưu trữ phân tán khắp bộ nhớ vật lý, trong bộ nhớ vật lý đồng thời cũng chứa những tiến trình khác. Phần cứng đảm nhiệm việc chuyển đổi địa chỉ logic thành địa chỉ vật lý . Sự chuyển đổi này là trong suốt đối với người sử dụng. Để lưu trữ các thông tin chi tiết về quá trình cấp phát bộ nhớ, hệ điều hành sử dụng một bảng khung trang, mà mỗi phần tử mô tả tình trạng của một khung trang vật lý : tự do hay được cấp phát cho một tiến trình nào đó . Lưu ý rằng sự phân trang không phản ánh đúng cách thức người sử dụng cảm nhận về bộ nhớ. Người sử dụng nhìn thấy bộ nhớ như một tập các đối tượng của chương trình (segments, các thư viện ) và một tập các đối tượng dữ liệu (biến toàn cục, stack, vùng nhớ chia sẻ ). Vấn đề đặt ra là cần tìm một cách thức biễu diễn bộ nhớ sao cho có thể cung cấp cho người dùng một cách nhìn gần với quan điểm logic của họ hơn và đó là kỹ thuật phân đoạn Kỹ thuật phân đoạn thõa mãn được nhu cầu thể hiện cấu trúc logic của chương trình nhưng nó dẫn đến tình huống phải cấp phát các khối nhớ có kích thước khác nhau cho các phân đoạn trong bộ nhớ vật lý. Điều này làm rắc rối vấn đề hơn rất nhiều so với việc cấp phát các trang có kích thước tĩnh.Một giải pháp dung hoà là kết hợp cả hai kỹ thuật phân trang và phân đoạn : chúng ta tiến hành phân trang các phân đoạn. 58
11. IV.3. Phân đoạn kết hợp phân trang (Paged segmentation) Ý tưởng: Không gian địa chỉ là một tập các phân đoạn, mỗi phân đoạn được chia thành nhiều trang. Khi một tiến trình được đưa vào hệ thống, hệ điều hành sẽ cấp phát cho tiến trình các trang cần thiết để chứa đủ các phân đoạn của tiến trình. Cơ chế MMU trong kỹ thuật phân đoạn kết hợp phân trang: Để hỗ trợ kỹ thuật phân đoạn, cần có một bảng phân đoạn, nhưng giờ đây mỗi phân đoạn cần có một bảng trang phân biệt. Hình 4.22 Mô hình phân đoạn kế hợp phân trang Chuyển đổi địa chỉ: Mỗi địa chỉ logic là một bộ ba: số hiệu phân đoạn (s): sử dụng như chỉ mục đến phần tử tương ứng trong bảng phân đoạn. số hiệu trang (p): sử dụng như chỉ mục đến phần tử tương ứng trong bảng trang của phân đoạn. địa chỉ tương đối trong trang (d): kết hợp với địa chỉ bắt đầu của trang để tạo ra địa chỉ vật lý mà trình quản lý bộ nhớ sử dụng. Tất cả các mô hình tổ chức bộ nhớ trên đây đều có khuynh hướng cấp phát cho tiến trình toàn bộ các trang yêu cầu trước khi thật sự xử lý. Vì bộ nhớ vật lý có kích thước rất giới hạn, điều này dẫn đến hai điểm bất tiện sau : Kích thước tiến trình bị giới hạn bởi kích thước của bộ nhớ vật lý. Khó có thể bảo trì nhiều tiến trình cùng lúc trong bộ nhớ, và như vậy khó nâng cao mức độ đa chương của hệ thống. 59
12. BÀI 7: BỘ NHỚ ẢO I. Dẫn nhập Nếu đặt toàn thể không gian địa chỉ vào bộ nhớ vật lý, thì kích thước của chương trình bị giới hạn bởi kích thước bộ nhớ vật lý. Thực tế, trong nhiều trường hợp, chúng ta không cần phải nạp toàn bộ chương trình vào bộ nhớ vật lý cùng một lúc, vì tại một thời điểm chỉ có một chỉ thị của tiến trình được xử lý. Ví dụ, các chương trình đều có một đoạn code xử lý lỗi, nhưng đoạn code này hầu như rất ít khi được sử dụng vì hiếm khi xảy ra lỗi, trong trường hợp này, không cần thiết phải nạp đoạn code xử lý lỗi từ đầu. Từ nhận xét trên, một giải pháp được đề xuất là cho phép thực hiện một chương trình chỉ được nạp từng phần vào bộ nhớ vật lý. Ý tưởng chính của giải pháp này là tại mỗi thời điểm chỉ lưu trữ trong bộ nhớ vật lý các chỉ thị và dữ liệu của chương trình cần thiết cho việc thi hành tại thời điểm đó. Khi cần đến các chỉ thị khác, những chỉ thị mới sẽ được nạp vào bộ nhớ, tại vị trí trước đó bị chiếm giữ bởi các chỉ thị nay không còn cần đến nữa. Với giải pháp này, một chương trình có thể lớn hơn kích thước của vùng nhớ cấp phát cho nó. Một cách để thực hiện ý tưởng của giải pháp trên đây là sử dụng kỹ thuật overlay. Kỹ thuật overlay không đòi hỏi bất kỳ sự trợ giúp đặc biệt nào của hệ điều hành , nhưng trái lại, lập trình viên phải biết cách lập trình theo cấu trúc overlay, và điều này đòi hỏi khá nhiều công sức. Để giải phóng lập trình viên khỏi các suy tư về giới hạn của bộ nhớ, mà cũng không tăng thêm khó khăn cho công việc lập trình của họ, người ta nghĩ đến các kỹ thuật tự động, cho phép xử lý một chương trình có kích thước lớn chỉ với một vùng nhớ có kích thước nhỏ . Giải pháp được tìm thấy với khái niệm bộ nhớ ảo (virtual memory). I.1. Định nghĩa Bộ nhớ ảo là một kỹ thuật cho phép xử lý một tiến trình không được nạp toàn bộ vào bộ nhớ vật lý. Bộ nhớ ảo mô hình hoá bộ nhớ như một bảng lưu trữ rất lớn và đồng nhất, tách biệt hẳn khái niệm không gian địa chỉ và không gian vật lý. Người sử dụng chỉ nhìn thấy và làm việc trong không gian địa chỉ ảo, việc chuyển đổi sang không gian vật lý do hệ điều hành thực hiện với sự trợ giúp của các cơ chế phần cứng cụ thể. Thảo luận: Cần kết hợp kỹ thuật swapping đển chuyển các phần của chương trình vào-ra giữa bộ nhớ chính và bộ nhớ phụ khi cần thiết. Nhờ việc tách biệt bộ nhớ ảo và bộ nhớ vật lý, có thể tổ chức một bộ nhớ ảo có kích thước lớn hơn bộ nhớ vật lý. Bộ nhớ ảo cho phép giảm nhẹ công việc của lập trình viên vì họ không cần bận tâm đến giới hạn của vùng nhớ vật lý, cũng như không cần tổ chức chương trình theo cấu trúc overlays. Hình 2.24 Bộ nhớ ảo I.2. Cài đặt bộ nhớ ảo 60
13. Bộ nhớ ảo thường được thực hiện với kỹ thuật phân trang theo yêu cầu (demand paging). Cũng có thể sử dụng kỹ thuật phân đoạn theo yêu cầu ( demand segmentation) để cài đặt bộ nhớ ảo, tuy nhiên việc cấp phát và thay thế các phân đoạn phức tạp hơn thao tác trên trang, vì kích thước không bằng nhau của các đoạn. Phân trang theo yêu cầu ( demand paging) Một hệ thống phân trang theo yêu cầu là hệ thống sử dụng kỹ thuật phân trang kết hợp với kỹ thuật swapping. Một tiến trình được xem như một tập các trang, thường trú trên bộ nhớ phụ ( thường là đĩa). Khi cần xử lý, tiến trình sẽ được nạp vào bộ nhớ chính. Nhưng thay vì nạp toàn bộ chương trình, chỉ những trang cần thiết trong thời điểm hiện tại mới được nạp vào bộ nhớ. Như vậy một trang chỉ được nạp vào bộ nhớ chính khi có yêu cầu. Với mô hình này, cần cung cấp một cơ chế phần cứng giúp phân biệt các trang đang ở trong bộ nhớ chính và các trang trên đĩa. Có thể sử dụng lại bit valid-invalid nhưng với ngữ nghĩa mới: valid : trang tương ứng là hợp lệ và đang ở trong bộ nhớ chính . invalid : hoặc trang bất hợp lệ (không thuộc về không gian địa chỉ của tiến trình) hoặc trang hợp lệ nhưng đang được lưu trên bộ nhớ phụ. Một phần tử trong bảng trang mộ tả cho một trang không nằm trong bộ nhớ chính, sẽ được đánh dấu invalid và chứa địa chỉ của trang trên bộ nhớ phụ. Cơ chế phần cứng : Cơ chế phần cứng hỗ trợ kỹ thuật phân trang theo yêu cầu là sự kết hợp của cơ chế hỗ trợ kỹ thuật phân trang và kỹ thuật swapping: Hình 2.24 Bảng trang với một số trang trên bộ nhớ phụ Bảng trang: Cấu trúc bảng trang phải cho phép phản ánh tình trạng của một trang là đang nằm trong bộ nhớ chính hay bộ nhớ phụ. Bộ nhớ phụ: Bộ nhớ phụ lưu trữ những trang không được nạp vào bộ nhớ chính. Bộ nhớ phụ thường được sử dụng là đĩa, và vùng không gian đĩa dùng để lưu trữ tạm các trang trong kỹ thuật swapping được gọi là không gian swapping. Lỗi trang Truy xuất đến một trang được đánh dấu bất hợp lệ sẽ làm phát sinh một lỗi trang (page fault). Khi dò tìm trong bảng trang để lấy các thông tin cần thiết cho việc chuyển đổi địa chỉ, nếu 61
14. nhận thấy trang đang được yêu cầu truy xuất là bất hợp lệ, cơ chế phần cứng sẽ phát sinh một ngắt để báo cho hệ điều hành. Hệ điều hành sẽ xử lý lỗi trang như sau : o Kiểm tra truy xuất đến bộ nhớ là hợp lệ hay bất hợp lệ o Nếu truy xuất bất hợp lệ : kết thúc tiến trình o Ngược lại : đến bước 3 o Tìm vị trí chứa trang muốn truy xuất trên đĩa. o Tìm một khung trang trống trong bộ nhớ chính : . Nếu tìm thấy : đến bước 5 . Nếu không còn khung trang trống, chọn một khung trang « nạn nhân » và chuyển trang « nạn nhân » ra bộ nhớ phụ (lưu nội dung của trang đang chiếm giữ khung trang này lên đĩa), cập nhật bảng trang tương ứng rồi đến bước 5 o Chuyển trang muốn truy xuất từ bộ nhớ phụ vào bộ nhớ chính : nạp trang cần truy xuất vào khung trang trống đã chọn (hay vừa mới làm trống ) ; cập nhật nội dung bảng trang, bảng khung trang tương ứng. o Tái kích hoạt tiến trình người sử dụng. Hình 2.26 Các giai đoạn xử lý lỗi trang II. Thay thế trang Khi xảy ra một lỗi trang, cần phải mang trang vắng mặt vào bộ nhớ . Nếu không có một khung trang nào trống, hệ điều hành cần thực hiện công việc thay thế trang – chọn một trang đang nằm trong bộ nhớ mà không được sử dụng tại thời điểm hiện tại và chuyển nó ra không gian swapping trên đĩa để giải phóng một khung trang dành chỗ nạp trang cần truy xuất vào bộ nhớ. Như vậy nếu không có khung trang trống, thì mỗi khi xảy ra lỗi trang cần phải thực hiện hai thao tác chuyển trang : chuyển một trang ra bộ nhớ phụ và nạp một trang khác vào bộ nhớ chính. Có thể giảm bớt số lần chuyển trang bằng cách sử dụng thêm một bit cập nhật (dirty bit). Bit này được gắn với mỗi trang để phản ánh tình trạng trang có bị cập nhật hay không : giá trị của bit được cơ chế phần cứng đặt là 1 mỗi lần có một từ được ghi vào trang, để ghi nhận nội dung trang có bị sửa đổi. số hiệu trang bit valid-invalid dirty bit Hình 4.27 Cấu trúc một phần tử trong bảng trang Sự thay thế trang là cần thiết cho kỹ thuật phân trang theo yêu cầu. Nhờ cơ chế này, hệ thống có thể hoàn toàn tách rời bộ nhớ ảo và bộ nhớ vật lý, cung cấp cho lập trình viên một bộ nhớ ảo rất lớn trên một bộ nhớ vật lý có thể bé hơn rất nhiều lần. II.1. Sự thi hành phân trang theo yêu cầu 62
15. Việc áp dụng kỹ thuật phân trang theo yêu cầu có thể ảnh hưởng mạnh đến tình hình hoạt động của hệ thống. Gỉa sử p là xác suất xảy ra một lỗi trang (0 p 1): p = 0 : không có lỗi trang nào p = 1 : mỗi truy xuất sẽ phát sinh một lỗi trang Thời gian thật sự cần để thực hiện một truy xuất bộ nhớ (TEA) là: TEA = (1-p)ma + p (tdp) [+ swap out ] + swap in + tái kích hoạt Trong công thức này, ma là thời gian truy xuất bộ nhớ, tdp thời gian xử lý lỗi trang. Có thể thấy rằng, để duy trì ở một mức độ chấp nhận được sự chậm trễ trong hoạt động của hệ thống do phân trang, cần phải duy trì tỷ lệ phát sinh lỗi trang thấp. Hơn nữa, để cài đặt kỹ thuật phân trang theo yêu cầu, cần phải giải quyết hai vấn đề chính yếu : xây dựng một thuật toán cấp phát khung trang, và thuật toán thay thế trang. II.2. Các thuật toán thay thế trang Vấn đề chính khi thay thế trang là chọn lựa một trang « nạn nhân » để chuyển ra bộ nhớ phụ. Có nhiều thuật toán thay thế trang khác nhau, nhưng tất cả cùng chung một mục tiêu : chọn trang « nạn nhân » là trang mà sau khi thay thế sẽ gây ra ít lỗi trang nhất. Có thể đánh giá hiệu qủa của một thuật toán bằng cách xử lý trên một chuỗi các địa chỉ cần truy xuất và tính toán số lượng lỗi trang phát sinh. Ví dụ: Giả sữ theo vết xử lý của một tiến trình và nhận thấy tiến trình thực hiện truy xuất các địa chỉ theo thứ tự sau : 0100, 0432, 0101, 0162, 0102, 0103, 0104, 0101, 0611, 0102, 0103,0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105 Nếu có kích thước của một trang là 100 bytes, có thể viết lại chuỗi truy xuất trên giản lược hơn như sau : 1, 4, 1, 6, 1, 6, 1, 6, 1 Để xác định số các lỗi trang xảy ra khi sử dụng một thuật toán thay thế trang nào đó trên một chuỗi truy xuất cụ thể, còn cần phải biết số lượng khung trang sử dụng trong hệ thống. Để minh hoạ các thuật toán thay thế trang sẽ trình bày, chuỗi truy xuất được sử dụng là : 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 II.2.1. Thuật toán FIFO Tiếp cận: Ghi nhận thời điểm một trang được mang vào bộ nhớ chính. Khi cần thay thế trang, trang ở trong bộ nhớ lâu nhất sẽ được chọn Ví dụ : sử dụng 3 khung trang , ban đầu cả 3 đều trống : 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1 * * * * * * * * * * * * * * * Ghi chú : * : có lỗi trang Thảo luận: Để áp dụng thuật toán FIFO, thực tế không nhất thiết phải ghi nhận thời điểm mỗi trang được nạp vào bộ nhớ, mà chỉ cần tổ chức quản lý các trang trong bộ nhớ trong một danh sách FIFO, khi đó trang đầu danh sách sẽ được chọn để thay thế. Thuật toán they thế trang FIFO dễ hiểu, dễ cài đặt. Tuy nhiên khi thực hiện không phải lúc nào cũng có kết qủa tốt : trang được chọn để thay thế có thể là trang chức nhiều dữ liệu cần thiết, thường xuyên được sử dụng nên được nạp sớm, do vậy khi bị chuyển ra bộ nhớ phụ sẽ nhanh chóng gây ra lỗi trang. 63
16. Số lượng lỗi trang xảy ra sẽ tăng lên khi số lượng khung trang sử dụng tăng. Hiện tượng này gọi là nghịch lý Belady. Ví dụ: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Sử dụng 3 khung trang , sẽ có 9 lỗi trang phát sinh 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 4 4 4 5 5 5 5 5 5 2 2 2 1 1 1 1 1 3 3 3 3 3 3 2 2 2 2 2 4 4 * * * * * * * * * Sử dụng 4 khung trang , sẽ có 10 lỗi trang phát sinh 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 1 1 1 5 5 5 5 4 4 2 2 2 2 2 2 1 1 1 1 5 3 3 3 3 3 3 2 2 2 2 4 4 4 4 4 4 3 3 3 * * * * * * * * * * II.2.2. Thuật toán tối ưu Tiếp cận: Thay thế trang sẽ lâu được sử dụng nhất trong tương lai. Ví dụ : sử dụng 3 khung trang, khởi đầu đều trống: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 * * * * * * * * * Thảo luận: Thuật toán này bảo đảm số lượng lỗi trang phát sinh là thấp nhất , nó cũng không gánh chịu nghịch lý Belady, tuy nhiên, đây là một thuật toán không khả thi trong thực tế, vì không thể biết trước chuỗi truy xuất của tiến trình! II.2.3. Thuật toán « Lâu nhất chưa sử dụng » ( Least-recently-used LRU) Tiếp cận: Với mỗi trang, ghi nhận thời điểm cuối cùng trang được truy cập, trang được chọn để thay thế sẽ là trang lâu nhất chưa được truy xuất. Ví dụ: sử dụng 3 khung trang, khởi đầu đều trống: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7 * * * * * * * * * * * * Thảo luận: Thuật toán FIFO sử dụng thời điểm nạp để chọn trang thay thế, thuật toán tối ưu lại dùng thời điểm trang sẽ được sử dụng, vì thời điểm này không thể xác định trước nên thuật toán LRU phải dùng thời điểm cuối cùng trang được truy xuất – dùng quá khứ gần để dự đoán tương lai. 64
17. Thuật toán này đòi hỏi phải được cơ chế phần cứng hỗ trợ để xác định một thứ tự cho các trang theo thời điểm truy xuất cuối cùng. Có thể cài đặt theo một trong hai cách : Sử dụng bộ đếm: thêm vào cấu trúc của mỗi phần tử trong bảng trang một trường ghi nhận thời điểm truy xuất mới nhất, và thêm vào cấu trúc của CPU một bộ đếm. mỗi lần có sự truy xuất bộ nhớ, giá trị của counter tăng lên 1. Mỗi lần thực hiện truy xuất đến một trang, giá trị của counter được ghi nhận vào trường thời điểm truy xuất mới nhất của phần tử tương ứng với trang trong bảng trang. thay thế trang có giá trị trường thời điểm truy xuất mới nhất là nhỏ nhất. Sử dụng stack: tổ chức một stack lưu trữ các số hiệu trang mỗi khi thực hiện một truy xuất đến một trang, số hiệu của trang sẽ được xóa khỏi vị trí hiện hành trong stack và đưa lên đầu stack. trang ở đỉnh stack là trang được truy xuất gần nhất, và trang ở đáy stack là trang lâu nhất chưa được sử dụng. II.2.4. Các thuật toán xấp xỉ LRU Có ít hệ thống được cung cấp đủ các hỗ trợ phần cứng để cài đặt được thuật toán LRU thật sự. Tuy nhiên, nhiều hệ thống được trang bị thêm một bit tham khảo ( reference): một bit reference, được khởi gán là 0, được gắn với một phần tử trong bảng trang. bit reference của một trang được phần cứng đặt giá trị 1 mỗi lần trang tương ứng được truy cập, và được phần cứng gán trở về 0 sau từng chu kỳ qui định trước. Sau từng chu kỳ qui định trước, kiểm tra giá trị của các bit reference, có thể xác định được trang nào đã được truy xuất đến và trang nào không, sau khi đã kiểm tra xong, các bit reference được phần cứng gán trở về 0 . với bit reference, có thể biết được trang nào đã được truy xuất, nhưng không biết được thứ tự truy xuất. Thông tin không đầy đủ này dẫn đến nhiều thuật toán xấp xỉ LRU khác nhau. số hiệu trang bit valid-invalid dirty bit bit reference Hình 4.28 Cấu trúc một phần tử trong bảng trang a) Thuật toán với các bit reference phụ trợ Tiếp cận: Có thể thu thập thêm nhiều thông tin về thứ tự truy xuất hơn bằng cách lưu trữ các bit references sau từng khoảng thời gian đều đặn: với mỗi trang, sử dụng thêm 8 bit lịch sử (history)trong bảng trang sau từng khoảng thời gian nhất định (thường là100 millisecondes), một ngắt đồng hồ được phát sinh, và quyền điều khiển được chuyển cho hệ điều hành. Hệ điều hành đặt bit reference của mỗi trang vào bit cao nhất trong 8 bit phụ trợ củatrang đó bằng cách đẩy các bit khác sang phải 1 vị trí, bỏ luôn bit thấp nhất. như vậy 8 bit thêm vào này sẽ lư u trữ tình hình truy xuất đến trang trong 8 chu kỳ cuối cùng. nếu gía trị của 8 bit là 00000000, thì trang tương ứng đã không được dùng đến suốt 8 chu kỳ cuối cùng, ngược lại nếu nó được dùng đến ít nhất 1 lần trong mỗi chu kỳ, thì 8 bit phụ trợ sẽ là 11111111. Một trang mà 8 bit phụ trợ có giá trị11000100 sẽ được truy xuất gần thời điểm hiện tại hơn trang có 8 bit phụ trợ là 01110111. nếu xét 8 bit phụ trợ này như một số nguyên không dấu, thì trang LRU là trang có số phụ trợ nhỏ nhất. Ví dụ : 0 0 1 0 0 0 1 1 1 0 HR =11000100 65
18. HR =11100010 HR =01110001 Thảo luận: Số lượng các bit lịch sử có thể thay đổi tùy theo phần cứng, và phải được chọn sao cho việc cập nhật là nhanh nhất có thể. b) Thuật toán « cơ hội thứ hai » Tiếp cận: Sử dụng một bit reference duy nhất. Thuật toán cơ sở vẫn là FIFO, tuy nhiên khi chọn được một trang theo tiêu chuẩn FIFO, kiểm tra bit reference của trang đó : Nếu giá trị của bit reference là 0, thay thế trang đã chọn. Ngược lại, cho trang này một cơ hội thứ hai, và chọn trang FIFO tiếp theo. Khi một trang được cho cơ hội thứ hai, giá trị của bit reference được đặt lại là 0, và thời điểm vào Ready List được cập nhật lại là thời điểm hiện tại. Một trang đã được cho cơ hội thứ hai sẽ không bị thay thế trước khi hệ thống đã thay thế hết những trang khác. Hơn nữa, nếu trang thường xuyên được sử dụng, bit reference của nó sẽ duy trì được giá trị 1, và trang hầu như không bao giờ bị thay thế. Thảo luận: Có thể cài đặt thuật toán « cơ hội thứ hai » với một xâu vòng. Hình 2.29 Thuật toán thay thế trang > c) Thuật toán « cơ hội thứ hai » nâng cao (Not Recently Used - NRU) Tiếp cận : xem các bit reference và dirty bit như một cặp có thứ tự . Với hai bit này, có thể có 4 tổ hợp tạo thành 4 lớp sau : (0,0) không truy xuất, không sửa đổi: đây là trang tốt nhất để thay thế. (0,1) không truy xuất gần đây, nhưng đã bị sửa đổi: trường hợp này không thật tốt, vì trang cần được lưu trữ lại trước khi thay thế. (1,0) được truy xuất gần đây, nhưng không bị sửa đổi: trang có thể nhanh chóng được tiếp tục được sử dụng. (1,1) được truy xuất gần đây, và bị sửa đổi: trang có thể nhanh chóng được tiếp tục được sử dụng, và trước khi thay thế cần phải được lưu trữ lại. Lớp 1 có độ ưu tiên thấp nhất, và lớp 4 có độ ưu tiên cao nhất. 66
19. Một trang sẽ thuộc về một trong bốn lớp trên, tuỳ vào bit reference và dirty bit của trang đó. Trang được chọn để thay thế là trang đầu tiên tìm thấy trong lớp có độ ưu tiên thấp nhất và khác rỗng. d) Các thuật toán thống kê Tiếp cận: sử dụng một biến đếm lưu trữ số lần truy xuất đến một trang, và phát triển hai thuật toán sau : Thuật toán LFU: thay thế trang có giá trị biến đếm nhỏ nhất, nghĩa là trang ít được sử dụng nhất. Thuật toán MFU: thay thế trang có giá trị biến đếm lớn nhất, nghĩa là trang được sử dụng nhiều nhất (most frequently used). III. Cấp phát khung trang Vấn đề đặt ra là làm thế nào để cấp phát một vùng nhớ tự do có kích thước cố định cho các tiến trình khác nhau? Trong trường hợp đơn giản nhất của bộ nhớ ảo là hệ đơn nhiệm, có thể cấp phát cho tiến trình duy nhất của người dùng tất cả các khung trang trống. Vấn đề nảy sinh khi kết hợp kỹ thuật phân trang theo yêu cầu với sự đa chương : cần phải duy trì nhiều tiến trình trong bộ nhớ cùng lúc, vậy mỗi tiến trình sẽ được cấp bao nhiêu khung trang. Số khung trang tối thiểu: Với mỗi tiến trình, cần phải cấp phát một số khung trang tối thiểu nào đó để tiến trình có thể hoạt động. Số khung trang tối thiểu này được quy định bởi kiến trúc của của một chỉ thị.Khi một lỗi trang xảy ra trước khi chỉ thị hiện hành hoàn tất, chỉ thị đó cần được tái khởi động, lúc đó cần có đủ các khung trang để nạp tất cả các trang mà một chỉ thị duy nhất có thể truy xuất. Số khung trang tối thiểu được qui định bởi kiến trúc máy tính, trong khi số khung trang tối đa được xác định bởi dung lượng bộ nhớ vật lý có thể sử dụng. Các thuật toán cấp phát khung trang Có hai hướng tiếp cận: Cấp phát cố định: Cấp phát công bằng: nếu có m khung trang và n tiến trình, mỗi tiến trình được cấp m /n khung trang. Cấp phát theo tỷ lệ: tùy vào kích thước của tiến trình để cấp phát số khung trang : si = kích thước của bộ nhớ ảo cho tiến trình pi S = si m = số lượng tổng cộng khung trang có thể sử dụng Cấp phát ai khung trang cho tiến trình pi : ai = (si / S) m Cấp phát theo độ ưu tiên : sử dụng ý tưởng cấp phát theo tỷ lệ, nhưng nhưng số lượng khung trang cấp cho tiến trình phụ thuộc vào độ ưu tiên của tiến trình, hơn là phụ thuộc kích thước tiến trình: Nếu tiến trình pi phát sinh một lỗi trang, chọn một trong các khung trang của nó để thay thế, hoặc chọn một khung trang của tiến trình khác với độ ưu tiên thấp hơn để thay thế. Thay thế trang toàn cục hay cục bộ Có thể phân các thuật toán thay thế trang thành hai lớp chính: Thay thế toàn cục: khi lỗi trang xảy ra với một tiến trình , chọn trang « nạn nhân » từ tập tất cả các khung trang trong hệ thống, bất kể khung trang đó đang được cấp phát cho một tiến trình khác. Thay thế cục bộ: yêu cầu chỉ được chọn trang thay thế trong tập các khung trang được cấp cho tiến trình phát sinh lỗi trang. Một khuyết điểm của thuật toán thay thế toàn cục là các tiến trình không thể kiểm soát được tỷ lệ phát sinh lỗi trang của mình. Vì thế, tuy thuật toán thay thế toàn cục nhìn chung cho phép hệ thống có nhiều khả năng xử lý hơn, nhưng nó có thể dẫn hệ thống đến tình trạng trì trệ toàn bộ (thrashing). III.1. Trì trệ toàn bộ hệ thống (Thrashing) Nếu một tiến trình không có đủ các khung trang để chứa những trang cần thiết cho xử lý, thì nó sẽ thường xuyên phát sinh các lỗi trang , và vì thế phải dùng đến rất nhiều thời gian sử dụng CPU để thực hiện thay thế trang. Một hoạt động phân trang như thế được gọi là sự trì trệ ( 67
20. thrashing). Một tiến trình lâm vào trạng thái trì trệ nếu nó sử dụng nhiều thời gian để thay thế trang hơn là để xử lý ! Hiện tượng trì trệ này ảnh hưởng nghiêm trọng đến hoạt động hệ thống, xét tình huống sau : Hệ điều hành giám sát việc sử dụng CPU. Nếu hiệu suất sử dụng CPU quá thấp, hệ điều hành sẽ nâng mức độ đa chương bằng cách đưa thêm một tiến trình mới vào hệ thống. Hệ thống có thể sử dụng thuật toán thay thế toàn cục để chọn các trang nạn nhân thuộc một tiến trình bất kỳ để có chỗ nạp tiến trình mới, có thể sẽ thay thế cả các trang của tiến trình đang xử lý hiện hành. Khi có nhiều tiến trình trong hệ thống hơn, thì một tiến trình sẽ được cấp ít khung trang hơn, và do đó phát sinh nhiều lỗi trang hơn. Khi các tiến trình phát sinh nhiều lỗi trang , chúng phải trải qua nhiều thời gian chờ các thao tác thay thế trang hoàn tất, lúc đó hiệu suất sử dụng CPU lại giảm Hệ điều hành lại quay trở lại bước 1 Theo kịch bản trên đây, hệ thống sẽ lâm vào tình trạng luẩn quẩn của việc giải phóng các trang để cấp phát thêm khung trang cho một tiến trình, và các tiến trình khác lại thiếu khung trang và các tiến trình không thể tiếp tục xử lý. Đây chính là tình trạng trì trệ toàn bộ hệ thống. Khi tình trạng trì trệ này xảy ra, hệ thống gần như mất khả năng xử lý, tốc độ phát sinh lỗi trang tăng cao khủng khiếp, không công việc nào có thể kết thúc vì tất cả các tiến trình đều bận rộn với việc phân trang ! Để ngăn cản tình trạng trì trệ này xảy ra, cần phải cấp cho tiến trình đủ các khung trang cần thiết để hoạt động. Vấn đề cần giải quyết là làm sao biết được tiến trình cần bao nhiêu trang? Mô hình cục bộ ( Locality) : theo lý thuyết cục bộ, thì khi một tiến trình xử lý, nó có khuynh hướng di chuyển từ nhóm trang cục bộ này đến nhóm trang cục bộ khác . Một nhóm trang cục bộ là một tập các trang đang được tiến trình dùng đến trong một khoảng thời gian. Một chương trình thường bao gồm nhiều nhóm trang cục bộ khác nhau và chúng có thể giao nhau. III.1.1. Mô hình « tập làm việc » (working set) Tiếp cận : Mô hình working set đặt cơ sở trên lý thuyết cục bộ. Mô hình này sử dụng một tham số , để định nghĩa một cửa sổ cho working set. Giả sử khảo sát đơn vị thời gian (lần truy xuất trang) cuối cùng, tập các trang được tiến trình truy xuất đến trong lần truy cập cuối cùng này được gọi là working set của tiến trình tại thời điểm hiện tại. Nếu một trang đang được tiến trình truy xuất đến, nó sẽ nằm trong working set, nếu nó không được sử dụng nữa , nó sẽ bị loại ra khỏi working set của tiến trình sau đơn vị thời gian kể từ lần truy xuất cuối cùng đến nó. Như vậy working set chính là một sự xấp xỉ của khái niệm nhóm trang cục bộ. Hình 2.30 Mô hình working set Một thuộc tính rất quan trọng của working set là kích thước của nó. Nếu tính toán kích thước working set, WSSi, cho mỗi tiến trình trong hệ thống, thì có thể xem như : D = ∑ WSSi 68
21. với D là tổng số khung trang yêu cầu cho toàn hệ thống. Mỗi tiến trình sử dụng các trang trong working set của nó, nghĩa là tiến trình i yêu cầu WSSi khung trang. Nếu tổng số trang yêu cầu vượt quá tổng số trang có thể sử dụng trong hệ thống (D > m), thì sẽ xảy ra tình trạng trì trệ toàn bộ. Sử dụng: Hệ điều hành giám sát working set của mỗi tiến trình và cấp phát cho tiến trình tối thiểu các khung trang để chứa đủ working set của nó. Như vậy một tiến trình mới chỉ có thể được nạp vào hệ thống khi có đủ khung trang tự do cho working set của nó. Nếu tổng số khung trang yêu cầu của các tiến trình trong hệ thống vượt quá các khung trang có thể sử dụng, hệ điều hành chọn một tiến trình để tạm dừng, giải phóng bớt các khung trang cho các tiến trình khác hoàn tất. Thảo luận: Chiến lược working set đã loại trừ được tình trạng trì trệ trong khi vẫn đảm bảo mức độ đa chương của hệ thống là cao nhất có thể, cho phép sử dụng tối ưu CPU. Điểm khó khăn của mô hình này là theo vết của các working set của tiến trình trong từng thời điểm. Có thể xấp xỉ mô hình working set với một ngắt đồng hồ sau từng chu kỳ nhất định và một bit reference: phát sinh một ngắt đồng hồ sau từng T lần truy xuất bộ nhớ. khi xảy ra một ngắt đồng hồ, kiểm tra các trang có bit reference là 1, các trang này được xem như thuộc về working set. Một hệ thống sử dụng kỹ thuật phân trang theo yêu cầu thuần túy (một trang không bao giờ được nạp trước khi có yêu cầu truy xuất) để lộ một đặc điểm khá bất lợi : một số lượng lớn lỗi trang xảy ra khi khởi động tiến trình. Tình trạng này là hậu quả của khuynh hướng đạt tới việc đưa nhóm trang cục bộ vào bộ nhớ. Tình trạng này cũng có thể xảy ra khi một tiến trình bị chuyển tạm thời ra bộ nhớ phụ, khi được tái kích hoạt, tất cả các trang của tiến trình đã được chuyển lên đĩa phải được mang trở lại vào bộ nhớ, và một loạt lỗi trang lại xảy ra. Để ngăn cản tình hình lỗi trang xảy ra quá nhiều tại thời điểm khởi động tiến trình, có thể sử dụng kỹ thuật tiền phân trang (prepaging) : nạp vào bộ nhớ một lần tất cả các trang trong working set của tiến trình. III.2. Tần suất xảy ra lỗi trang Tiếp cận: Tần suất lỗi trang rất cao khiến tình trạng trì trệ hệ thống có thể xảy ra. Khi tần suất lỗi trang quá cao, tiến trình cần thêm một số khung trang. Khi tần suất lỗi trang quá thấp, tiến trình có thể sỡ hữu nhiều khung trang hơn mức cần thiết. Có thể thiết lập một giá trị chặn trên và chặn dưới cho tần suất xảy ra lỗi trang, và trực tiếp ước lượng và kiểm soát tần suất lỗi trang để ngăn chặn tình trang trì trệ xảy ra : Nếu tần suất lỗi trang vượt quá chặn trên, cấp cho tiến trình thêm một khung trang Nếu tần suất lỗi trang thấp hơn chặn dưới, thu hồi bớt một khung trang từ tiến trình 69
22. BÀI 8 HỆ THỐNG QUẢN LÝ TẬP TIN I. CÁC KHÁI NIỆM CƠ BẢN I.1 Bộ nhớ ngoài Máy tính phải sử dụng thiết bị có khả năng lưu trữ trong thời gian dài (long-term) vì : Phải chứa những lượng thông tin rất lớn (giữ vé máy bay, ngân hàng ) Thông tin phải được lưu giữ một thời gian dài trước khi xử lý Nhiều tiến trình có thể truy cập thông tin cùng lúc. Giải pháp là sử dụng các thiết bị lưu trữ bên ngoài gọi là bộ nhớ ngoài. I.2 Tập tin và thư mục Tập tin Tập tin là đơn vị lưu trữ thông tin của bộ nhớ ngoài. Các tiến trình có thể đọc hay tạo mới tập tin nếu cần thiết. Thông tin trên tập tin là vững bền không bị ảnh hưởng bởi các xử lý tạo hay kết thúc các tiến trình, chỉ mất đi khi user thật sự muốn xóa. Tập tin được quản lý bởi hệ điều hành. Thư mục Để lưu trữ dãy các tập tin, hệ thống quản lý tập tin cung cấp thư mục, mà trong nhiều hệ thống có thể coi như là tập tin. I.3 Hệ thống quản lý tập tin Các tập tin được quản lý bởi hệ điều hành với cơ chế gọi là hệ thống quản lý tập tin. Bao gồm : cách hiển thị, các yếu tố cấu thành tập tin, cách đặt tên, cách truy xuất, cách sử dụng và bảo vệ tập tin, các thao tác trên tập tin. Cách tổ chức thư mục, các đặc tính và các thao tác trên thư mục. II. MÔ HÌNH TỔ CHỨC VÀ QUẢN LÝ CÁC TẬP TIN II.1 Mô hình Tập tin Thư mục Tập tin : Tên tập tin : Tập tin là một cơ chế trừu tượng và để quản lý mỗi đối tượng phải có một tên. Khi tiến trình tạo một tập tin, nó sẽ đặt một tên, khi tiến trình kết thúc tập tin vẫn tồn tại và có thể được truy xuất bởi các tiến trình khác với tên tập tin đó. Cách đặt tên tập tin của mỗi hệ điều hành là khác nhau, đa số các hệ điều hành cho phép sử dụng 8 chữ cái để đặt tên tập tin như ctdl, caycb, tamhghau v.v , thường thường thì các ký tự số và ký tự đặc biệt cũng được sử dụng như baitap2 , Hệ thống tập tin có thể có hay không phân biệt chữ thường và chữ hoa. Ví dụ : UNIX phân biệt chữ thường và hoa còn MS-DOS thì không phân biệt. Nhiều hệ thống tập tin hỗ trợ tên tập tin gồm 2 phần được phân cách bởi dấu ‘.’ mà phần sau được gọi là phần mở rộng. Ví dụ : vidu.txt. Trong MS-DOS tên tập tin có từ 1 đến 8 ký tư, phần mở rộng có từ 1 đến 3 ký tự. Trong UNIX có thể có nhiều phân cách như prog.c.Z. Một số kiểu mở rộng thông thường là : .bak, .bas, .bin, .c, .dat, .doc, .ftn, .hlp, .lib, .obj, .pas, .tex, .txt. Trên thực tế phần mở rộng có hữu ích trong một số trường hợp, ví dụ như có những trình dịch C chỉ nhận biết các tập tin có phần mở rộng là .C Cấu trúc của tập tin : Gồm 3 loại : Dãy tuần tự các byte không cấu trúc : hệ điều hành không biết nội dung của tập tin:MS-DOS và UNIX sử dụng loại này. Dãy các record có chiều dài cố định. 70
23. Cấu trúc cây : gồm cây của những record, không cần thiết có cùng độ dài, mỗi record có một trường khóa giúp cho việc tìm kiếm nhanh hơn. Kiểu tập tin : Nếu hệ điều hành nhận biết được loại tập tin, nó có thể thao tác một cách hợp lý trên tập tin đó. Các hệ điều hành hỗ trợ cho nhiều loại tập tin khác nhau bao gồm các kiểu như : tập tin thường, thư mục, tập tin có ký tự đặc biệt, tập tin khối. Tập tin thường : là tập tin text hay tập tin nhị phân chứa thông tin của người sử dụng. Thư mục : là những tập tin hệ thống dùng để lưu giữ cấu trúc của hệ thống tập tin. Tập tin có ký tự đặc biệt : liên quan đến nhập xuất thông qua các thiết bị nhập xuất tuần tự như màn hình, máy in, mạng. Tập tin khối : dùng để truy xuất trên thiết bị đĩa. Tập tin thường được chia làm hai loại là tập tin văn bản và tập tin nhị phân. Tập tin văn bản chứa các dòng văn bản cuối dòng có ký hiệu enter. Mỗi dòng có độ dài có thể khác nhau. Ưu điểm của kiểu tập tin này là nó có thể hiển thị, in hay soạn thảo với một editor thông thường.Đa số các chương trình dùng tập tin văn bản để nhập xuất, nó cũng dễ dàng làm đầu vào và đầu ra cho cơ chế pipeline. Tập tin nhị phân : có cấu trúc khác tập tin văn bản. Mặc dù về mặt kỹ thuật , tập tin nhị phân gồm dãy các byte , nhưng hệ điều hành chỉ thực thi tập tin đó nếu nó có cấu trúc đúng. Ví dụ một một tập tin nhị phân thi hành được của UNIX. Thường thường nó bao gồm năm thành phần : header, text, data, relocation bits, symbol table. Header bắt đầu bởi byte nhận diện cho biết đó là tập tin thi hành. Sau đó là 16 bit cho biết kích thước các thành phần của tập tin, địa chỉ bắt đầu thực hiện và một số bit cờ. Sau header là dữ liệu và text của tập tin. Nó được nạp vào bộ nhớ và định vị lại bởi những bit relocation. Bảng symbol được dùng để debug. Một ví dụ khác là tập tin nhị phân kiểu archive. Nó chứa các thư viện đã được dịch nhưng chưa được liên kết. Bao gồm một header cho biết tên, ngày tạo, người sở hữu, mã bảo vệ, và kích thước 71
24. Truy xuất tập tin : Tập tin lưu trữ các thông tin. Khi tập tin được sử dụng, các thông tin này được đưa vào bộ nhớ của máy tính. Có nhiều cách để truy xuất chúng. Một số hệ thống cung cấp chỉ một phương pháp truy xuất, một số hệ thống khác, như IBM chẳng hạn cho phép nhiều cách truy xuất. Kiểu truy xuất tập tin đơn giản nhất là truy xuất tuần tự . Tiến trình đọc tất cả các byte trong tập tin theo thứ tự từ đầu. Các trình soạn thảo hay trình biên dịch cũng truy xuất tập tin theo cách này. Hai thao tác chủ yếu trên tập tin là đọc và ghi. Thao tác đọc sẽ đọc một mẫu tin tiếp theo trên tập tin và tự động tăng con trỏ tập tin. Thao tác ghi cũng tương tự như vậy. Tập tin có thể tự khởi động lại từ vị trí đầu tiên và trong một số hệ thống tập tin cho phép di chuyển con trỏ tập tin đi tới hoặc đi lui n mẫu tin. Truy xuất kiểu này thuận lợi cho các loại băng từ và cũng là cách truy xuất khá thông dụng. Truy xuất tuần tự cần thiết cho nhiều ứng dụng. Có hai cách truy xuất. Cách truy xuất thứ nhất thao tác đọc bắt đầu ở vị trí đầu tập tin, cách thứ hai có một thao tác đặc biệt gọi là SEEK cung cấp vị trí hiện thời làm vị trí bắt đầu. Sau đó tập tin được đọc tuần tự từ vị trí bắt đầu. Một kiểu truy xuất khác là truy xuất trực tiếp. Một tập tin có cấu trúc là các mẫu tin logic có kích thước bằng nhau, nó cho phép chương trình đọc hoặc ghi nhanh chóng mà không cần theo thứ tự. Kiểu truy xuất này dựa trên mô hình của đĩa. Đĩa cho phép truy xuất ngẫu nhiên bất kỳ khối dữ liệu nào của tập tin. Truy xuất trực tiếp được sử dụng trong trường hợp phải truy xuất một khối lượng thông tin lớn như trong cơ sở dữ liệu chẳng hạn. Ngoài ra còn có một số cách truy xuất khác dự trên kiểu truy xuất này như truy xuất theo chỉ mục Thuộc tính tập tin : Ngoài tên và dữ liệu, hệ điều hành cung cấp thêm một số thông tin cho tập tin gọi là thuộc tính. Các thuộc tính thông dụng trong một số hệ thống tập tin : Tên thuộc tính Ý nghĩa Bảo vệ Ai có thể truy xuất được và bằng cách nào Mật khẩu Mật khẩu cần thiết để truy xuất tập tin Người tạo Id của người tạo tập tin Người sở hữu Người sở hữu hiện tại Chỉ đọc 0 là đọc ghi, 1 là chỉ đọc Aån 0 là bình thường, 1 là không hiển thị khi liệt kê Hệ thống 0 là bình thường, 1 là tập tin hệ thống Lưu trữ 0 đã đuợc backup, 1 cần backup ASCII/binary 0 là tập tin văn bản, 1 là tập tin nhị phân Truy xuất ngẫu 0 truy xuất tuần tự, 1 là truy xuất ngẫu nhiên nhiên Temp 0 là bình thường, 1 là bị xóa khi tiến trình kết thúc Khóa 0 là không khóa, khác 0 là khóa Độ dài của record Số byte trong một record Vị trí khóa Offset của khóa trong mỗi record Giờ tạo Ngày và giờ tạo tập tin 72
25. Tên thuộc tính Ý nghĩa Thời gian truy Ngày và giờ truy xuất tập tin gần nhất cập cuối cùng Thời gian thay Ngày và giờ thay đổi tập tin gần nhất đổi cuối cùng Kích thước hiện Số byte của tập tin thời Kích thước tối đa. Số byte tối đa của tập tin Hình 8.3 Một số thuộc tính thông dụng của tập tin Thư mục : HỆ THỐNG THƯ MỤC THEO CẤP BẬC : Một thư mục thường thường chứa một số entry, mỗi entry cho một tập tin. Mỗi entry chứa tên tập tin, thuộc tính và địa chỉ trên đĩa lưu dữ liệu hoặc một entry chỉ chứa tên tập tin và một con trỏ, trỏ tới một cấu trúc, trên đó có thuộc tính và vị trí lưu trữ của tập tin. Khi một tập tin được mở, hệ điều hành tìm trên thư mục của nó cho tới khi tìm thấy tên của tập tin được mở. Sau đó nó sẽ xác định thuộc tính cũng như địa chỉ lưu trữ trên đĩa và đưa vào một bảng trong bộ nhớ. Những truy xuất sau đó thực hiện trong bộ nhớ chính. Số lượng thư mục trên mỗi hệ thống là khác nhau. Thiết kế đơn giản nhất là hệ thống chỉ có thư mục đơn(còn gọi là thư mục một cấp), chứa tất cả các tập tin của tất cả người dùng, cách này dễ tổ chức và khai thác nhưng cũng dễ gây ra khó khăn khi có nhiều người sử dụng vì sẽ có nhiều tập tin trùng tên. Ngay cả trong trường hợp chỉ có một người sử dụng, nếu có nhiều tập tin thì việc đặt tên cho một tập tin mới không trùng lắp là một vấn đề khó. Cách thứ hai là có một thư mục gốc và trong đó có nhiều thư mục con, trong mỗi thư mục con chứa tập tin của người sử dụng (còn gọi là thư mục hai cấp), cách này tránh được trường hợp xung đột tên nhưng cũng còn khó khăn với người dùng có nhiều tập tin. Người sử dụng luôn muốn nhóm các ứng dụng lại một cách logic. Từ đó, hệ thống thư mục theo cấp bậc (còn gọi là cây thư mục) được hình thành với mô hình một thư mục có thể chứa tập tin hoặc một thư mục con và cứ tiếp tục như vậy hình thành cây thư mục như trong các hệ điều hành DOS, Windows, v. v Ngoài ra, trong một số hệ điều hành nhiều người dùng, hệ thống còn xây dựng các hình thức khác của cấu trúc thư mục như cấu trúc thư mục theo đồ thị có chu trình và cấu trúc thư mục theo đồ thị tổng quát. Các cấu trúc này cho phép các người dùng trong hệ thống có thể liên kết với nhau thông qua các thư mục chia sẻ. ĐƯỜNG DẪN : 73
26. Khi một hệ thống tập tin được tổ chức thành một cây thư mục, có hai cách để xác định một tên tập tin. Cách thứ nhất là đường dẫn tuyệt đối, mỗi tập tin được gán một đường dẫn từ thư mục gốc đến tập tin. Ví dụ : /usr/ast/mailbox. Dạng thứ hai là đường dẫn tương đối, dạng này có liên quan đến một khái niệm là thư mục hiện hành hay thư mục làm việc. Người sử dụng có thể quy định một thư mục là thư mục hiện hành. Khi đó đường dẫn không bắt đầu từ thư mục gốc mà liên quan đến thư mục hiện hành. Ví dụ, nếu thư mục hiện hành là /usr/ast thì tập tin với đường dẫn tuyệt đối /usr/ast/mailbox có thể được dùng đơn giản là mailbox. Trong phần lớn hệ thống, mỗi tiến trình có một thư mục hiện hành riêng, khi một tiến trình thay đổi thư mục làm việc và kết thúc, không có sự thay đổi để lại trên hệ thống tập tin. Nhưng nếu một hàm thư viện thay đổi đường dẫn và sau đó không đổi lại thì sẽ có ảnh hưởng đến tiến trình. Hầu hết các hệ điều hành đều hỗ trợ hệ thống thư mục theo cấp bậc với hai entry đặc biệt cho mỗi thư mục là "." và " ". "." chỉ thư mục hiện hành, " " chỉ thư mục cha. II.2 Các chức năng Tập tin Thư mục Tập tin : Tạo : một tập tin được tạo chưa có dữ liệu. Mục tiêu của chức năng này là thông báo cho biết rằng tập tin đã tồn tại và thiết lập một số thuộc tính. Xóa :khi một tập tin không còn cần thiết nữa, nó được xóa để tăng dung lượng đĩa. Một số hệ điều hành tự động xoá tập tin sau một khoảng thời gian n ngày. Mở : trước khi sử dụng một tập tin, tiến trình phải mở nó. Mục tiêu của mở là cho phép hệ thống thiết lập một số thuộc tính và địa chỉ đĩa trong bộ nhớ để tăng tốc độ truy xuất. Đóng : khi chấm dứt truy xuất, thuộc tính và địa chỉ trên đĩa không cần dùng nữa, tập tin được đóng lại để giải phóng vùng nhớ. Một số hệ thống hạn chế tối đa số tập tin mở trong một tiến trình. 74
27. Đọc : đọc dữ liệu từ tập tin tại vị trí hiện thời của đầu đọc, nơi gọi sẽ cho biết cần bao nhiêu dữ liệu và vị trí của buffer lưu trữ nó. Ghi : ghi dữ liệu lên tập tin từ vị trí hiện thời của đầu đọc. Nếu là cuối tập tin,kích thước tập tin sẽ tăng lên, nếu đang ở giữa tập tin, dữ liệu sẽ bị ghi chồng lên. Thêm : gần giống như WRITE nhưng dữ liệu luôn được ghi vào cuối tập tin. Tìm :dùng để truy xuất tập tin ngẫu nhiên. Khi xuất hiện lời gọi hệ thống, vị trí con trỏ đang ở vị trí hiện hành được di chuyển tới vị trí cần thiết. Sau đó dữ liệu sẽ được đọc ghi tại vị trí này. Lấy thuộc tính :lấy thuộc tính của tập tin cho tiến trình Thiết lập thuộc tính :thay đổi thuộc tính của tập tin sau một thời gian sử dụng. Đổi tên :thay đổi tên của tập tin đã tồn tại. Thư mục : Tạo : một thư mục được tạo, nó rỗng, ngoại trừ "." và " " được đặt tự động bởi hệ thống. Xóa :xoá một thư mục, chỉ có thư mục rỗng mới bị xóa, tư mục chứa "." và " " coi như là thư mục rỗng. Mở thư mục :thư mục có thể được đọc. Ví dụ để liệt kê tất cả tập tin trong một thư mục, chương trình liệt kê mở thư mục và đọc ra tên của tất cả tập tin chứa trong đó. Trước khi thư mục được đọc, nó phải được mở ra trước. Đóng thư mục :khi một thư mục đã được đọc xong, phải đóng thư mục để giải phóng vùng nhớ. Đọc thư mục :Lệnh này trả về entry tiếp theo trong thư mục đã mở. Thông thường có thể đọc thư mục bằng lời gọi hệ thống READ, lệnh đọc thư mục luôn luôn trả về một entry dưới dạng chuẩn . Đổi tên :cũng như tập tin, thư mục cũng có thể được đổi tên. Liên kết :kỹ thuật này cho phép một tập tin có thể xuất hiện trong nhiều thư mục khác nhau. Khi có yêu cầu, một liên kết sẽ được tạo giữa tập tin và một đường dẫn được cung cấp. Bỏ liên kết :Nếu tập tin chỉ còn liên kết với một thư mục, nó sẽ bị loại bỏ hoàn toàn khỏi hệ thống, nếu nhiều thì nó bị giảm chỉ số liên kết. 75
28. BÀI 9: CÁC PHƯƠNG PHÁP CÀI ĐẶT HỆ THỐNG QUẢN LÝ TẬP TIN I.BẢNG QUẢN LÝ THƯ MỤC, TẬP TIN I.1 Khái niệm Trước khi tập tin được đọc, tập tin phải được mở, để mở tập tin hệ thống phải biết đường dẫn do người sử dụng cung cấp và được định vị trong cấu trúc đầu vào thư mục (directory entry). Directory entry cung cấp các thông tin cần thiết để tìm kiếm các khối. Tuỳ thuộc vào mỗi hệ thống, thông tin là địa chỉ trên đĩa của toàn bộ tập tin, số hiệu của khối đầu tiên, hoặc là số I-node. II.2 Cài đặt Bảng này thường được cài đặt ở phần đầu của đĩa. Bảng là dãy các phần tử có kích thước xác định, mỗi phần tử được gọi là một entry. Mỗi entry sẽ lưu thông tin về tên , thuộc tính, vị trí lưu trữ của một tập tin hay thư mục. Ví dụ quản lý thư mục trong CP/M : II. BẢNG PHÂN PHỐI VÙNG NHỚ II.1 Khái niệm Bảng này thường được sử dụn phối hợp với bảng quản lý thư mục tập tin, mục tiêu là cho biết vị trí khối vật lý của một tập tin hay thư mục nào đó nói khác đi là lưu giữ dãy các khối trên đĩa cấp phát cho tập tin lưu dữ liệu hay thư mục. Có một số phương pháp được cài đặt. II.2 Các phương pháp Định vị liên tiếp : Lưu trữ tập tin trên dãy các khối liên tiếp. Phương pháp này có 2 ưu điểm : thứ nhất, dể dàng cài đặt. Thứ hai, dể dàng thao tác vì toàn bộ tập tin được đọc từ đĩa bằng thao tác đơn giản không cần định vị lại. Phương pháp này cũng có 2 khuyết điểm : không linh động trừ khi biết trước kích thước tối đa của tập tin. Sự phân mảnh trên đĩa, gây lãng phí lớn. 76
29. Định vị bằng danh sách liên kết : Mọi khối đều được cấp phát, không bị lãng phí trong trường hợp phân mảnh và directory entry chỉ cần chứa địa chỉ của khối đầu tiên. Tuy nhiên khối dữ liệu bị thu hẹp lại và truy xuất ngẫu nhiên sẽ chậm. Danh sách liên kết sử dụng index : Tương tự như hai nhưng thay vì dùng con trỏ thì dùng một bảng index. Khi đó toàn bộ khối chỉ chứa dữ liệu. Truy xuất ngẫu nhiên sẽ dễ dàng hơn. Kích thước tập tin được mở rộng hơn. Hạn chế là bản này bị giới hạn bởi kích thước bộ nhớ. I-nodes : Một I-node bao gồm hai phần. Phần thứ nhất là thuộc tính của tập tin. Phần này lưu trữ các thông tin liên quan đến tập tin như kiểu, người sở hữu, kích thước, v.v Phần thứ hai chứa địa chỉ của khối dữ liệu. Phần này chia làm hai phần nhỏ. Phần nhỏ thứ nhất bao gồm 10 phần tử, mỗi phần tử chứa địa chỉ khối dữ liệu của tập tin. Phần tử thứ 11 chứa địa chỉ gián tiếp cấp 1 (single indirect), chứa địa chỉ của một khối, trong khối đó chứa một bảng có thể từ 210 đến 232 phần tử mà mỗi phần tử mới chứa địa chỉ của khối dữ liệu. Phần tử thứ 12 chứa địa chỉ gián tiếp cấp 2 (double indirect), chứa địa chỉ của bảng các khối single indirect. Phần tử thứ 13 chứa địa chỉ gián tiếp cấp 3 (double indirect), chứa địa chỉ của bảng các khối double indirect. Cách tổ chức này tương đối linh động. Phương pháp này hiệu quả trong trường hợp sử dụng để quán lý những hệ thống tập tin lớn. Hệ điều hành sử dụng phương pháp này là Unix (Ví dụ : BSD Unix) III. TẬP TIN CHIA SẺ 77
30. Khi có nhiều người sử dụng cùng làm việc trong một đề án, họ cần chia sẻ các tập tin. Cách chia sẻ thông thường là tập tin xuất hiện trong các thư mục là như nhau nghĩa là một tập tin có thể liên kết với nhiều thư mục khác nhau. Để cài đặt được, khối đĩa không được liệt kê trong thư mục mà được thay thế bằng một cấu trúc dữ liệu, thư mục sẽ trỏ tới cấu trúc này. Một cách khác là hệ thống tạo một tập tin mới có kiểu LINK, tập tin mới này chỉ chứa đường dẫn của tập tin được liên kết, khi cần truy xuất sẽ dựa trên tập tin LINK để xác định tập tin cần truy xuất, phương pháp này gọi là liên kết hình thức. Mổi phương pháp đều có những ưu và khuyết điểm riêng. Ở phương pháp thứ nhất hệ thống biết được có bao nhiêu thư mục liên kết với tập tin nhờ vào chỉ số liên kết. Ở phương pháp thứ hai khi loại bỏ liên kết hình thức, tập tin không bị ảnh hưởng. Hình 9.5 IV. QUẢN LÝ ĐĨA Tập tin được lưu trữ trên đĩa, do đó việc quản trị đĩa là hết sức quan trọng trong việc cài đặt hệ thống tập tin. Có hai phương pháp lưu trữ : một là chứa tuần tự trên n byte liên tiếp, hai là tập tin được chia làm thành từng khối. Cách thứ nhất không hiệu quả khi truy xuất những tập tin có kích thước lớn, do đó hầu hết các hệ thống tập tin đều dùng khối có kích thước cố định. IV.1 Kích thước khối Một vấn đề đặt ra là kích thước khối phải bằng bao nhiêu. Điều này phụ thuộc vào tổ chức của đĩa như số sector, số track, số cylinder. Nếu dùng một cylinder cho một khối cho một tập tin thì theo tính toán sẽ lãng phí đến 97% dung lượng đĩa. Nên thông thường mỗi tập tin thường được lưu trên một số khối. Ví dụ một đĩa có 32768 byte trên một track, thời gian quay là 16.67 msec, thời gian tìm kiếm trung bình là 30msec thì thời gian tính = msec để đọc một khối kích thước k byte là : 78
31. 30 + 8.3 + (k/32768) x 16.67 Từ đó thống kê được kích thước khối thích hợp phải < 2K . Thông thường kích thưóc khối là 512, 1K hay 2K. IV.2 Lưu giữa các khối trống Có hai phương pháp. Một là sử dụng danh sách liên kết của khối đĩa. Mỗi khối chứa một số các địa chỉ các khối trống. Ví dụ một khối có kích thước 1 K có thể lưu trữ được 511 địa chỉ 16 bit. Một đĩa 20M cần khoảng 40 khối. Hai là, sử dụng bitmap. Một đĩa n khối sẽ được ánh xạ thành n bit với giá trị 1 là còn trống, giá trị 0 là đã lưu dữ liệu. Như vậy một đĩa 20M cần 20K bit để lưu trữ nghĩa là chỉ có khoảng 3 khối. Phương pháp thứ hai này thường được sử dụng hơn. V. ĐỘ AN TOÀN CỦA HỆ THỐNG TẬP TIN Một hệ thống tập tin bị hỏng còn nguy hiểm hơn máy tính bị hỏng vì những hư hỏng trên thiết bị sẽ ít chi phí hơn là hệ thống tập tin vì nó ảnh hưởng đến các phần mềm trên đó. Hơn nữa hệ thống tập tin không thể chống lại được như hư hòng do phần cứng gây ra, vì vậy chúng phải cài đặt một số chức năng để bảo vệ. V.1 Quản lý khối bị hỏng Đĩa thường có những khối bị hỏng trong quá trình sử dụng đặc biệt đối với đĩa cứng vì khó kiểm tra được hết tất cả. Có hai giải pháp : phần mềm và phần cứng. Phần cứng là dùng một sector trên đĩa để lưu giữ danh sách các khối bị hỏng. Khi bộ kiểm soát tực hiện lần đầu tiên, nó đọc những khối bị hỏng và dùng một khối thừa để lưu giữ. Từ đó không cho truy cập những khối hỏng nữa. Phần mềm là hệ thống tập tin xây dựng một tập tin chứa các khối hỏng. Kỹ thuật này loại trừ chúng ra khỏi danh sách các khối trống, do đó nó sẽ không được cấp phát cho tập tin. V.2 Backup Mặc dù có các chiến lưọc quản lý các khối hỏng, nhưng một công việc hết sức quan trọng là phải backup tập tin thường xuyên. Tập tin trên đĩa mềm được backup bằng cách chép lại toàn bộ qua một đĩa khác. Dữ liệu trên đĩa cứng nhỏ thì được backup trên các băng từ. 79
32. Đối với các đĩa cứng lớn, việc backup thường được tiến hành ngay trên nó. Một chiến lược dể cài đặt nhưng lãng phí một nữa đĩa là chia đĩa cứng làm hai phần một phần dữ liệu và một phần là backup. Mỗi tối, dữ liệu từ phần dữ liệu sẽ được chép sang phần backup. V.3 Tính không đổi của hệ thống tập tin Một vấn đề nữa về độ an toàn là tính không đổi. Khi truy xuất một tập tin, trong quá trình thực hiện, nếu có xảy ra những sự cố làm hệ thống ngừng hoạt động đột ngột, lúc đó hàng loạt thông tin chưa được cập nhật lên đĩa. Vì vậy mỗi lân khởi động ,hệ thống sẽ thực hiện việc kiểm tra trên hai phần khối và tập tin. Việc kiểm tra thực hiện , khi phát hiện ra lỗi sẽ tiến hành sữa chữa cho các trường hợp cụ thể: Hình 9.8 Trạng thái của hệ thống tập tin 80
33. BÀI 10 HỆ THỐNG QUẢN LÝ NHẬP/XUẤT I.KHÁI NIỆM VỀ HỆ THỐNG QUẢN LÝ NHẬP/XUẤT Hệ thống quản lý nhập/xuất được tổ chức theo từng lớp, mỗi lớp có một chức năng nhất định và các lớp có giao tiếp với nhau như sơ đồ sau : CÁC LỚP CHỨC NĂNG NHẬP/XUẤT Xử lý của người Tạo lời gọi nhập/xuất, định dạng dùng nhập/xuất Phần mềm độc lập Đặt tên, bảo vệ, tổ chức khối, bộ đệm, thiết bị định vị Điều khiển thiết bị Thiết lập thanh ghi thiết bị, kiểm tra trạng thái Kiểm soát ngắt Báo cho driver khi nhập/xuất hoàn tất Phần cứng Thực hiện thao tác nhập/xuất Ví dụ: Trong một chương trình ứng dụng, người dùng muốn đọc một khối từ một tập tin, hệ điều hành được kích hoạt để thực hiện yêu cầu này. Phần mềm độc lập thiết bị tìm kiếm trong cache, nếu khối cần đọc không có sẵn, nó sẽ gọi chương trình điều khiển thiết bị gửi yêu cầu đến phần cứng. Tiến trình bị ngưng lại cho đến khi thao tác đĩa hoàn tất. Khi thao tác này hoàn tất, phần cứng phát sinh một ngắt. Bộ phận kiểm soát ngắt kiểm tra biến cố này, ghi nhận trạng thái của thiết bị và đánh thức tiến trình bị ngưng để chấm dứt yêu cầu I/O và cho tiến trình của người sử dụng tiếp tục thực hiện.[TAN] II. PHẦN CỨNG NHẬP/XUẤT Có nhiều cách nhìn khác nhau về phần cứng nhập/xuất. Các kỹ sư điện tử thì nhìn dưới góc độ là các thiết bị như IC, dây dẫn, bộ nguồn, motor v.v .Các lập trình viên thì nhìn chúng dưới góc độ phần mềm - những lệnh nào thiết bị chấp nhận, chúng sẽ thực hiện những chức năng nào, và thông báo lỗi của chúng bao gồm những gì, nghĩa là chúng ta quan tâm đến lập trình thiết bị chứ không phải các thiết bị này hoạt động như thế nào mặc dù khía cạnh này có liên quan mật thiết với các thao tác bên trong của chúng. Phần này chúng ta đề cập đến một số khái niệm về phần cứng I/O liên quan đến khía cạnh lập trình. II.1 Thiết bị I/O Các thiết bị nhập xuầt có thể chia tương đối thành hai loại là thiết bị khối và thiết bị tuần tự. Thiết bị khối là thiết bị mà thông tin được lưu trữ trong những khối có kích thước cố định và được định vị bởi địa chỉ. Kích thước thông thường của một khối là khoảng từ 128 bytes đến 1024 bytes. Đặc điểm của thiết bị khối là chúng có thể được truy xuất (đọc hoặc ghi) từng khối riêng biệt, và chương trình có thể truy xuất một khối bất kỳ nào đó. Đĩa là một ví dụ cho loại thiết bị khối. Một dạng thiết bị thứ hai là thiết bị tuần tự. Ở dạng thiết bị này, việc gửi và nhận thông tin dựa trên là chuỗi các bits, không có xác định địa chỉ và không thể thực hiện thao tác seek được. Màn hình, bàn phím, máy in, card mạng, chuột, và các loại thiết bị khác không phải dạng đĩa là thiết bị tuần tự. Việc phân chia các lớp như trên không hoàn toàn tối ưu, một số các thiết bị không phù hợp với hai lớp trên, ví dụ : đồng hồ, bộ nhớ màn hình v.v không thực hiện theo cơ chế tuần tự các bits. Ngoài ra, người ta còn phân loại các thiết bị I/O dưới một tiêu chuẩn khác: Thiết bị tương tác được với con người : dùng để giao tiếp giữa người và máy. Ví dụ : màn hình, bàn phím, chuột, máy in Thiết bị tương tác trong hệ thống máy tính là các thiết bị giao tiếp với nhau. Ví dụ : đĩa, băng từ, card giao tiếp Thiết bị truyền thồng : như modem Những điểm khác nhau giữa các thiết bị I/O gồm : Tốc độ truyền dữ liệu , ví dụ bàn phím : 0.01 KB/s, chuột 0.02 KB/s 81
34. Công dụng. Đơn vị truyền dữ liệu (khối hoặc ký tự). Biểu diễn dữ liệu, điều này tùy thuộc vào từng thiết bị cụ thể. Tình trạng lỗi : nguyên nhân gây ra lỗi, cách mà chúng báo về II.2 Tổ chức của chức năng I/O Có ba cách để thực hiện I/O : Một là, bộ xử lý phát sinh một lệnh I/O đến các đơn vị I/O, sau đó, nó chờ trong trạng thái "busy" cho đến khi thao tác này hoàn tất trước khi tiếp tục xử lý. Hai là, bộ xử lý phát sinh một lệnh I/O đến các đơn vị I/O, sau đó, nó tiếp tục việc xử lý cho tới khi nhận được một ngắt từ đơn vị I/O báo là đã hoàn tất, nó tạm ngưng việc xử lý hiện tại để chuyển qua xử lý ngắt. Ba là, sử dụng cơ chế DMA (như được đề cập ở sau) Các bước tiến hóa của chức năng I/O : Bộ xử lý kiểm soát trực tiếp các thiết bị ngoại vi. Hệ thống có thêm bộ điều khiển thiết bị. Bộ xử lý sử dụng cách thực hiện nhập xuất thứ nhất. Theo cách này bộ xử lý được tách rời khỏi các mô tả chi tiết của các thiết bị ngoại vi. Bộ xử lý sử dụng thêm cơ chế ngắt. Sử dụng cơ chế DMA, bộ xử lý truy xuất những dữ liệu I/O trực tiếp trong bộ nhớ chính. II.3 Bộ điều khiển thiết bị Một đơn vị bị nhập xuất thường được chia làm hai thành phần chính là thành phần cơ và thành phần điện tử. Thành phần điện tử được gọi là bộ phận điều khiển thiết bị hay bộ tương thích, trong các máy vi tính thường được gọi là card giao tiếp. Thành phần cơ chính là bản thân thiết bị. Một bộ phận điều khiển thường có bộ phận kết nối trên chúng để có thể gắn thiết bị lên đó. Một bộ phận điều khiển có thể quản lý được hai, bốn hay thậm chí tám thiết bị khác nhau. Nếu giao tiếp giữa thiết bị và bộ phận điều khiển là các chuẩn như ANSI, IEEE hay ISO thì nhà sản xuất thiết bị và bộ điều khiển phải tuân theo chuẩn đó, ví dụ : bộ điều khiển đĩa theo chuẩn giao tiếp của IBM. Giao tiếp giữa bộ điều khiển và thiết bị là giao tiếp ở mức thấp. Chức năng của bộ điều khiển là giao tiếp với hệ điều hành vì hệ điều hành không thể truy xuất trực tiếp với thiết bị. Việc thông tin thông qua hệ thống đường truyền gọi là bus. Công việc của bộ điều khiển là chuyển đổi dãy các bit tuần tự trong một khối các byte và thực hiện sửa chửa nếu cần thiết. Thông thường khối các byte được tổ chức thành từng bit và đặt trong buffer của bộ điều khiển. Sau khi thực hiện checksum nội dung của buffer sẽ được chuyển vào bộ nhớ chính. Ví dụ : bộ điều khiển cho màn hình đọc các byte của ký tự để hiển thị trong bộ nhớ và tổ chức các tín hiệu để điều khiển các tia của CRT để xuất trên màn ảnh bằng cách quét các tia dọc và ngang. Nếu không có bộ điều khiển, lập trình viên hệ điều hành phải tạo thêm chương trình điều khiển tín hiệu analog cho đèn hình. Với bộ điều khiển , hệ điều hành chỉ cần khởi động chúng với một số tham số như số ký tự trên một dòng, số dòng trên màn hình và bộ điều khiển sẽ thực hiện điều khiển các tia. 82
35. Mỗi bộ điều khiển có một số thanh ghi để liên lạc với CPU. Trên một số máy tính, các thanh ghi này là một phần của bộ nhớ chính tại một địa chỉ xác định gọi là ánh xạ bộ nhớ nhập xuất. Hệ máy PC dành ra một vùng địa chỉ đặc biệt gọi là địa chỉ nhập xuất và trong đó được chia làm nhiều đoạn, mỗi đoạn cho một loại thiết bị như sau : Bộ điều khiển Địa chỉ nhập/xuất Vectơ ngắt nhập/xuất Đồng hồ 040 - 043 8 Bàn phím 060 - 063 9 RS232 phụ 2F8 - 2FF 11 Đĩa cứng 320 - 32F 13 Máy in 378 - 37F 15 Màn hình mono 380 - 3BF - Màn hình màu 3D0 - 3DF - Đĩa mềm 3F0 - 3F7 14 RS232 chính 3F8 - 3FF 12 Hệ điều hành thực hiện nhập xuất bằng cách ghi lệnh lên các thanh ghi của bộ điều khiển. Ví dụ : bộ điều khiển đĩa mềm của IBMPC chấp nhận 15 lệnh khác nhau như : READ, WRITE, SEEK, FORMAT, RECALIBRATE, một số lệnh có tham số và các tham số cũng được nạp vào thanh ghi. Khi một lệnh đã được chấp nhận, CPU sẽ rời bộ điều khiển để thực hiện công việc khác. Sau khi thực hiện xong, bộ điều khiển phát sinh một ngắt để báo hiệu cho CPU biết và đến lấy kết quả được lưu giữ trong các thanh ghi. II.4 DMA (Direct Memory Access) Đa số các loại thiết bị, đặc biệt là các thiết bị dạng khối, hỗ trợ cơ chế DMA (direct memory access). Để hiểu về cơ chế này, trước hết phải xem xét quá trình đọc đĩa mà không có DMA. Trước tiên, bộ điều khiển đọc tuần tự các khối trên đĩa, từng bit từng bit cho tới khi toàn bộ khối được đưa vào buffer của bộ điều khiển. Sau đó máy tính thực hiện checksum để đảm bảo không có lỗi xảy ra. Tiếp theo bộ điều khiển tạo ra một ngắt để báo cho CPU biết. CPU đến lấy dữ liệu trong buffer chuyển về bộ nhớ chính bằng cách tạo một vòng lặp đọc lần lượt từng byte. Thao tác này làm lãng phí thời gian của CPU. Do đó để tối ưu, người ta đưa ra cơ chế DMA. Cơ chế DMA giúp cho CPU không bị lãng phí thời gian. Khi sử dụng, CPU gửi cho bộ điều khiển một số các thông số như địa chỉ trên đĩa của khối, địa chỉ trong bộ nhớ nơi định vị khối, số lượng byte dữ liệu để chuyển. Sau khi bộ điều khiển đã đọc toàn bộ dữ liệu từ thiết bị vào buffer của nó và kiểm tra checksum. Bộ điều khiển chuyển byte đầu tiên vào bộ nhớ chính tại địa chỉ được mô tả bởi địa chỉ bộ nhớ DMA. Sau đó nó tăng địa chỉ DMA và giảm số bytes phải chuyển. Quá trình này lập cho tới khi số bytes phải chuyển bằng 0, và bộ điều khiển tạo một ngắt. Như vậy không cần phải copy khối vào trong bộ nhớ, nó đã hiện hữu trong bộ nhớ. 83
36. III. PHẦN MỀM NHẬP/XUẤT Mục tiêu chung của thiết bị logic là dể biểu diễn. Thiết bị logic được tổ chức thành nhiều lớp. Lớp dưới cùng giao tiếp với phần cứng, lớp trên cùng giao tiếp tốt, thân thiện với người sử dụng. Khái niệm then chốt của thiết bị logic là độc lập thiết bị, ví dụ : có thể viết chương trình truy xuất file trên đĩa mềm hay đĩa cứng mà không cần phải mô tả lại chương trình cho từng loại thiết bị. Ngoài ra, thiết bị logic phải có khả năng kiểm soát lỗi. Thiết bị logic được tổ chức thành bốn lớp : Kiểm soát lỗi, điều khiển thiết bị, phần mềm hệ điều hành độc lập thiết bị, phần mềm mức người sử dụng. III.1 Kiểm soát ngắt Ngắt là một hiện tượng phức tạp. Nó phải cần được che dấu sâu trong hệ điều hành, và một phần ít của hệ thống biết về chúng. Cách tốt nhất để che dấu chúng là hệ điều hành có mọi tiến trình thực hiện thao tác nhập xuất cho tới khi hoàn tất mới tạo ra một ngắt. Tiến trình có thể tự khóa lại bằng cách thực hiện lệnh WAIT theo một biến điều kiện hoặc RECEIVE theo một thông điệp. Khi một ngắt xảy ra, hàm xử lý ngắt khởi tạo một tiến trình mới để xử lý ngắt. Nó sẽ thực hiện một tín hiệu trên biến điều kiện và gửi những thông điệp đến cho các tiến trình bị khóa. Tổng quát, chức năng của ngắt là làm cho một tiến trình đang bị khóa được thi hành trở lại. III.2 Điều khiển thiết bị (device drivers) Tất cả các đoạn mã độc lập thiết bị đều được chuyển đến device drivers. Mỗi device drivers kiểm soát mỗi loại thiết bị, nhưng cũng có khi là một tập hợp các thiết bị liên quan mật thiết với nhau. Device drivers phát ra các chỉ thị và kiểm tra xem chỉ thị đó có được thực hiện chính xác không. Ví dụ, driver của đĩa là phần duy nhất của hệ điều hành kiểm soát bộ điều khiển đĩa. Nó quản lý sectors, tracks, cylinders, head, chuyển động, interleave, và các thành phần khác giúp cho các thao tác đĩa được thực hiện tốt. Chức năng của device drivers là nhận những yêu cầu trừu tượng từ phần mềm nhập/xuất độc lập thiết bị ở lớp trên, và giám sát yêu cầu này thực hiện. Nếu driver đang rảnh, nó sẽ thực hiện ngay yêu cầu, ngược lại, yêu cầu đó sẽ được đưa vào hàng đợi. Ví dụ, bước đầu tiên của yêu cầu nhập/xuất đĩa là chuyển từ trừu tượng thành cụ thể. Driver của đĩa phải biết khối nào cần đọc, kiểm tra sự hoạt động của motor đĩa, xác định vị trí của đầu đọc đã đúng chưa v.v Nghĩa là device drivers phải xác định được những thao tác nào của bộ điều khiển phải thi hành và theo trình tự nào. Một khi đã xác định được chỉ thị cho bộ điều khiển, nó bắt đầu thực hiện bằng cách chuyển lệnh vào thanh ghi của bộ điều khiển thiết bị. Bộ điều khiển có thể nhận một hay nhiều chỉ thị liên tiếp và sau đó tự nó thực hiện không cần sự trợ giúp của hệ điều hành. Trong khi lệnh thực hiện. Có hai trường hợp xảy ra : Một là device drivers phải chờ cho tới khi bộ điều khiển thực hiện xong bằng cách tự khóa lại cho tới khi một ngắt phát sinh mở khóa cho nó. Hai là, hệ điều hành chấm dứt mà không chờ, vì vậy driver không cần thiết phải khóa. Sau khi hệ điều hành hoàn tất việc kiểm tra lỗi và nếu mọi thứ đều ổn driver sẽ chuyển dữ liệu cho phần mềm độc lập thiết bị. Cuối cùng nó sẽ trả về thông tin về trạng thái hay lỗi cho nơi gọi và nếu có một yêu cầu khác ở hàng đợi, nó sẽ thực hiện tiếp, nếu không nó sẽ khóa lại chờ đến yêu cầu tiếp theo. III.3 Phần mềm nhập/xuất độc lập thiết bị Mặc dù một số phần mềm nhập/xuất mô tả thiết bị nhưng phần lớn chúng là độc lập với thiết bị. Ranh giới chính xác giữa drivers và phần mềm độc lập thiết bị là độc lập về mặt hệ thống, bởi vì một số hàm mà được thi hành theo kiểu độc lập thiết bị có thể được thi hành trên drivers vì lý do hiệu quả hay những lý dó khác nào đó. Giao tiếp đồng nhất cho device drivers Đặt tên thiết bị Bảo vệ thiết bị 84
37. Cung cấp khối độc lập thiết bị Tổ chức buffer Định vị lưu trữ trên thiết bị khối Cấp phát và giải phóng thiết bị tận hiến Báo lỗi Chức năng cơ bản của phần mềm nhập/xuất độc lập thiết bị là những chức năng chung cho tất cả các thiết bị và cung cấp một giao tiếp đồng nhất cho phần mềm phạm vi người sử dụng. Trước tiên nó phải có chức năng tạo một ánh xạ giữa thiết bị và một tên hình thức. Ví dụ đối với UNIX, tên /dev/tty0 dành riêng để mô tả I-node cho một file đặc biệt, và I-node này chứa chứa số thiết bị chính, được dùng để xác định driver thích hợp và số thiết bị phụ, được dùng để xác định các tham số cho driver để cho biết là đọc hay ghi. Thứ hai là bảo vệ thiết bị, là cho phép hay không cho phép người sử dụng truy xuất thiết bị. Các hệ điều hành có thể có hay không có chức năng này. Thứ ba là cung cấp khối dữ liệu độc lập thiết bị vì ví dụ những đĩa khác nhau sẽ có kích thước sector khác nhau và điều này sẽ gây khó khăn cho các phần mềm người sử dụng ở lớp trên. Chức năng này cung cấp các khối dữ liệu logic độc lập với kích thước sector vật lý. Thứ tư là cung cấp buffer để hỗ trợ cho đồng bộ hóa quá trình hoạt động của hệ thống. Ví dụ buffer cho bàn phím. Thứ năm là định vị lưu trữ trên các thiết bị khối. Thứ sáu là cấp phát và giải phóng các thiết bị tận hiến. Cuối cùng là thông báo lỗi cho lớp bên trên từ các lỗi do device driver báo về. III.4 Phần mềm nhập/xuất phạm vi người sử dụng Hầu hết các phần mềm nhập/xuất đều ở bên trong của hệ điều hành và một phần nhỏ của chúng chứa các thư viện liên kết với chương trình của người sử dụng ngay cả những chương trình thi hành bên ngoài hạt nhân. Lời gọi hệ thống, bao gồm lời gọi hệ thống nhập/xuất thường được thực hiện bởi các hàm thư viện. Ví dụ khi trong chương trình C có lệnh count = write(fd, buffer, nbytes) ; Hàm thư viện write được địch và liên kết dưới dạng nhị phân và nằm trong bộ nhớ khi thi hành. Tập hợp tất cả những hàm thư viện này rõ ràng là một phần của hệ thống nhập/xuất. Không phải tất cả các phần mềm nhập/xuất đều chứa hàm thư viện, có một loại quan trọng khác gọi là hệ thống spooling dùng để khai thác tối đa thiết bị nhập/xuất trong hệ thống đa chương. Các hàm thư viện chuyển các tham số thích hợp cho lời gọi hệ thống và hàm thư viện thực hiện việc định dạng cho nhập và xuất như lệnh printf trong C. Thư viện nhập/xuất chuẩn chứa một số hàm có chức năng nhập/xuất và tất cả chạy như chương trình người dùng. Chức năng của spooling là tránh trường hợp một tiến trình đang truy xuất thiết bị, chiếm giữ thiết bị nhưng sau đó không làm gì cả trong một khoảng thời gian và như vậy các tiến trình khác bị ảnh hưởng vì không thể truy xuất thiết bị đó. Một ví dụ của spooling device là line printer. Spooling còn được sử dụng trong hệ thống mạng như hệ thống e-mail chẳng hạn. 85
38. BÀI 11: BẢO VỆ VÀ AN TOÀN HỆ THỐNG 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 đó. Ví dụ : 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ẽ 5.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 86
39. 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. Ma trận quyền truy xuất ( Access matrix) Một cách trừu tượng, có thể biểu diễn mô hình bảo vệ trên đây như một ma trận quyền truy xuất ( access matrix). Các dòng của ma trận biễu diễn các miền bảo vệ và các cột tương ứng với các đối tượng trong hệ thống. Phần tử acess[i,j] của ma trận xác định các quyền truy xuất mà một tiến trình hoạt động trong miền bảo vệ Di có thể thao tác trên đối tượng Oj. object F1 F2 F3 Máy in domain D1 đọc đọc D2 in D3 đọc xử lý D4 đọc đọc ghi ghi Hình 5.2 Ma trận quyền truy xuất Cơ chế bảo vệ được cung cấp khi ma trận quyền truy xuất được cài đặt ( với đầy đủ các thuộc tính ngữ nghĩa đả mô tả trên lý thuyết), lúc này người sử dụng có thể áp dụng các chiến lược bảo vệ bằng cách đặc tả nội dung các phần tử tương ứng trong ma trận _ xác định các quyền truy xuất ứng với từng miền bảo vệ , và cuối cùng, hệ điều hành sẽ quyết định cho phép tiến trình hoạt động trong miền bảo vệ thích hợp. Ma trận quyền truy xuất cũng cung cấp một cơ chế thích hợp để định nghĩa và thực hiện một sự kiểm soát nghiêm nhặt cho cả phương thức liên kết tĩnh và động các tiến trình với các miền bảo vệ : Có thể kiểm soát việc chuyển đổi giữa các miền bảo vệ nếu quan niệm miền bảo vệ cũng là một đối tượng trong hệ thống, và bổ sung các cột mô tả cho nó trong ma trận quyền truy xuất. Khi đó tiến trình được phép chuyển từ miền bảo vệ Di sang miền bảo vệ Dj nếu phần tử access(i,j) chứa đựng quyền « chuyển » ( switch). object F1 F2 F3 Máy in D1 D2 D3 D4 domain 87
40. D1 đọc đọc chuyển D2 in chuyển chuyển D3 đọc xử lý D4 đọc đọc chuyển ghi ghi Hình 5.3 Ma trận quyền truy xuất với domain là một đối tượng Có thể kiểm soát việc sửa đổi nội dung ma trận (thay đổi các quyền truy xuất trong một miền bảo vệ) nếu quan niệm bản thân ma trận cũng là một đối tượng. Các thao tác sửa đổi nội dung ma trận được phép thực hiện bao gồm : sao chép quyền ( copy), chuyển quyền ( transfer), quyền sở hữu (owner), và quyền kiểm soát (control) Copy: nếu một quyền truy xuất R trong access[i,j] được đánh dấu là R* thì có thể sao chép nó sang một phần tử access[k,j] khác ( mở rộng quyền truy xuất R trên cùng đối tượng Oj nhưng trong miền bảo vệ Dk ). Transfer : nếu một quyền truy xuất R trong access[i,j] được đánh dấu là R+ thì có thể chuyển nó sang một phần tử access[k,j] khác ( chuyển quyền truy xuất R+ trên đối tượng Oj sang miền bảo vệ Dk ). Owner : nếu access[i,j] chứa quyền truy xuất owner thì tiến trình hoạt động trong miền bảo vệ Di có thể thêm hoặc xóa các quyền truy xuất trong bất kỳ phần tử nào trên cột j (có quyền thêm hay bớt các quyền truy xuất trên đối tượng Oj trong những miền bảo vệ khác). Control : nếu access[i,j] chứa quyền truy xuất control thì tiến trình hoạt động trong miền bảo vệ Di có thể xóa bất kỳ quyền truy xuất nào trong các phần tử trên dòng j (có quyền bỏ bớt các quyền truy xuất trong miền bảo vệ Dj). object F1 F2 F3 domain D1 xử lý ghi+ D2 xử lý đọc* xử lý D3 xử lý (a) object F1 F2 F3 domain D1 xử lý D2 xử lý đọc* xử lý D3 xử lý đọc ghi+ (b) Hình 5.4 Ma trận quyền truy xuất với quyền copy , transfer (a) trước, (b) sau cập nhật object F1 F2 F3 domain D1 owner ghi xử lý D2 đọc* đọc* owner owner ghi* D3 xử lý Hình 5.5 (a) 88
41. object F1 F2 F3 domain D1 owner xử lý D2 owner đọc* đọc* owner ghi* ghi* D3 ghi (b) Hình 5.5 Ma trận quyền truy xuất với quyền owner (a) trước, (b) sau cập nhật object F1 F2 F3 Máy in D1 D2 D3 D4 domain D1 đọc đọc chuyển D2 in chuyển control chuyển D3 đọc xử lý D4 ghi ghi chuyển Hình 5.6 Ma trận quyền truy xuất đã sửa đổi nội dung so với H5.3 nhờ quyền control IV. Cài đặt ma trận quyền truy xuất IV.1. Bảng toàn cục Cách đơn giản nhất để cài đặt ma trận truy xuất là sử dụng một bảng bao gồm các bộ ba thứ tự . Mỗi khi thực hiện thao tác M trên đ&#ÿ889;i tượng Oj trong miền bảo vệ Di, cần tìm trong bảng toàn cục một bộ ba mà M Rk. Nếu tìm thấy, thao tác M được phép thi hành, nếu không, xảy ra lỗi truy xuất. IV.2. Danh sách quyền truy xuất ( Access control list _ ACL) Có thể cài đặt mỗi cột trong ma trận quyền truy xuất như một danh sách quyền truy xuất đối với một đối tượng. Mỗi đối tượng trong hệ thống sẽ có một danh sách bao gồm các phần tử là các bộ hai thứ tự , danh sách này sẽ xác định các quyền truy xuất được qui định trong từng miền bảo vệ có thể tác động trên đối tượng. Mỗi khi thực hiện thao tác M trên đối tượng Oj trong miền bảo vệ Di, cần tìm trong danh sách quyền truy xuất của đối tượng Oj một bộ hai mà M Rk. Nếu tìm thấy, thao tác M được phép thi hành, nếu không, xảy ra lỗi truy xuất. Ví dụ : Một miền bảo vệ trong hệ thống UNIX được xác định tương ứng với một người sử dụng (uid) trong một nhóm (gid) nào đó. Giả sử có 4 người dùng : A,B,C,D thuộc các nhóm tương ứng là system, staff, student, student. Khi đó các tập tin trong hệ thống có thể có các ACL như sau : File0 : ( A,*,RWX) File1 : ( A,system,RWX) File2 : ( A,*,RW-),(B,staff,R ),(D,*,RW-) File3 : ( *,student,R ) File4 : (C,*, ),(*,student,R ) Thực tế, hệ thống tập tin trong UNIX được bảo vệ bằng cách mỗi tập tin được gán tương ứng 9 bit bảo vệ , từng 3 bit sẽ mô tả quyềntruy xuất R(đọc), W(ghi) hay X(xử lý) của các tiến trình trên tập tin này theo thứ tự : tiến trình sỡ hữu các tiến trình cùng nhóm với tiến trình sỡ hữu, các tiến trình khác. Đây là một dạng ACL nhưng được nén thành 9 bit. IV.3. Danh sách tiềm năng của miền bảo vệ (Capability list – C_List) Mỗi dòng trong ma trận quyền truy xuất tương ứng với một miền bảo vệ sẽ được tổ chức thành một danh sách tiềm năng (capabilities list) : 89
42. Một danh sách tiềm năng của một miền bảo vệ là một danh sách các đối tượng và các thao tác được quyền thực hiện trên đối tượng khi tiến trình hoạt động trong miền bảo vệ này. Một phần tử của C-List được gọi là một tiềm năng (capability) là một hình thức biễu diển được định nghĩa một cách có cấu trúc cho một đối tượng trong hệ thống và các quyền truy xuất hợp lệ trên đối tượng này. kiểu đối quyền truy con trỏ đến đối tượng tượng xuất Hình 5.7 Tiềm năng Ví dụ : Tiến trình chỉ có thể thực hiện thao tác M trên đối tượng Oj trong miền bảo vệ Di, nếu trong C_List của Di có chứa tiềm năng tương ứng của Oj. Danh sách tiềm năng được gán tương ứng với từng miền bảo vệ, thực chất nó cũng là một đối tượng được bảo vệ bởi hệ thống, và tiến trình của người sử dụng chỉ có thể truy xuất đến nó một cách gián tiếp để tránh làm sai lạc C_List. Hệ điều hành cung cấp các thủ tục cho phép tạo lập, hủy bỏ và sửa đổi các tiềm năng của một đối tượng, và chỉ các tiến trình đóng vai trò server (thường là tiến trình hệ điều hành) mới có thể sửa đổi nội dung C_List. IV.4. Cơ chế khóa và chìa Đây là cách tiếp cận kết hợp giữa danh sách quyền truy xuất và danh sách khả năng. Mỗi đối tượng sỡ hữu một danh sách các mã nhị phân , được gọi là « khoá » (lock). Cũng như thế, mỗi miền bảo vệ sẽ sỡ hữu một danh sách mã nhị phân gọi là « chìa » (key). Một tiến trình hoạt động trong một miền bảo vệ chỉ có thể truy xuất đến một đối tượng nếu miền bảo vệ sỡ hữu một chìa tương ứng với một khóa trong danh sách của đối tượng. Cũng như C_List, danh sách « khóa » và « chìa » được hệ điều hành quản lý, người sử dụng không thể truy xuất trực tiếp đến chúng để thay đổi nội dung. IV.5. Thu hồi quyền truy xuất Trong một hệ thống bảo vệ động, đôi khi hệ điều hành cần thu hồi một số quyền truy xuất trên các đối tượng được chia sẻ giữa nhiều người sử dụng. Khi đó đặt ra một số vấn đề như sau : Thu hồi tức khắc hay trì hoãn, trì hoãn đến khi nào ? Nếu loại bỏ một quyền truy xuất trên một đối tượng, thu hồi quyền này trên tất cả hay chi một số người sử dụng? Thu hồi một số quyền hay toàn bộ quyền trên một đối tượng ? Thu hồi tạm thời hay vĩnh viển một quyền truy xuất ? Đối với các hệ thống sử dụng danh sách quyền truy xuất, việc thu hồi có thể thực hiện dễ dàng : tìm và hủy trên ACL quyền truy xuất cần thu hồi, như vậy việc thu hồi được htực hiện tức thời, có thể áp dụng cho tất cả hay một nhóm người dùng, thu hồi toàn bộ hay một phần, và thu hồi vĩnh viễn hay tạm thời đều được. Tuy nhiên trong các hệ sử dụng C_List, vấn đề thu hồi gặp khó khăn vì các tiềm năng được phân tán trên khắp các miền bảo vệ trong hệ thống, do vậy cần tìm ra chúng trước khi loại bỏ. Có thể giải quyết vấn đề này theo nhiều phương pháp : Tái yêu cầu (Reacquisiton): loại bỏ các tiềm năng ra khỏi mỗi miền bảo vệ sau từng chu kỳ, nếu miền bảo vệ vẫn còn cần tiềm năng nào, nó sẽ tái yêu cầu tiềm năng đó lại. 90
43. Sử dụng các con trỏ đến tiềm năng (Back-pointers) : với mỗi đối tượng, lưu trữ các con trỏ đến những tiềm năng tương ứng trên đối tượng này. Khi cần thu hồi quyền truy xuất nào trên đối tượng, lần theo các con trỏ để cập nhật tiềm năng tương ứng. Sử dụng con trỏ gián tiếp (Indirection) : các tiềm năng không trực tiếp trỏ đến các đối tượng, mà trỏ đến một bảng toàn cục do hệ điều hành quản lý. KHi cần thu hồi quyền, sẽ xoá phần tử tương ứng trong bảng này. Khóa ( Key) : nếu sử dụng cơ chế khóa và chìa, khi cần thu hồi quyền, chỉ cần thay đổi khóa và bắt buộc tiến trình hay người dùng yêu cầu chìa mới. V. 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 . V.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. V.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ên những tài nguyên nào. Cách tiếp cận phổ biến nhất để giải quyết vấn đề là sử dụng password để kiểm định đúng danh tính của người dùng. Mỗi khi người dùng muốn sử dụng tài nguyên, hệ thống sẽ kiểm tra password của người dùng nhập vào với password được lưu trữ, nếu đúng, người dùng mới được cho phép sử dụng tài nguyên. Password có thể đuợc để bảo vệ từng đối tượng trong hệ thống, thậm chí cùng một đối tượng sẽ có các password khác nhau ứng với những quyền truy xuất khác nhau. Cơ chế password rất dễ hiểu và dễ sử dụng do vậy được sử dụng rộng rãi, tuy nhiên yếu điểm nghiêm trọng của phương pháp này là khả năng bảo mật password rất khó đạt được sự hoàn hảo, những tác nhân tiêu cực có thể đoán ra password của người khác nhờ nhiều cách thức khác nhau. V.3. Mối đe dọa từ các chương trình Trong môi trường mà một chương trình được tạo lập bởi người này lại có thể được người khác sử dụng, có thể xảy ra các tình huống sử dụng không đúng, từ đó dẫn đến những hậu qủa khó lường. Hai trường hợp điển hình là : V.3.1. Ngựa thành Troy Khi một người dùng A cho một chương trình do B viết hoạt động dưới danh nghĩa của mình ( trong miền bảo vệ được gán tương ứng cho người dùng A), chương trình này có thể trở thành một « con ngựa thành Troy » vì khi đó các đoạn lệnh trong chương trình có thể thao tác trên các tài nguyên với những quyền tương ứng của người A (mà có thể người B vốn bị cấm!), nhiều chương trình như thế đã « lợi dụng hoàn cảnh » để gây ra các tác hại đáng tiếc. 91
44. V.3.2. Cánh cửa nhỏ ( Trap-door) Một mối đe dọa đặc biệt nguy hiểm và khó chống đỡ đến từ sự vô tình hay ý nghĩ bất chính của các lập trình viên. Khi xây dựng chương trình, các lập trình viên có thể để lại một « cánh cửa nhỏ » trong phần mềm mà chỉ có họ là có khả năng sử dụng , qua đó thâm nhập và phá hoại hệ thống ( ví dụ làm tròn các số lẻ trong những tài khoản, và thu lợi riêng từ phần dư này ). Vấn đề này rất khó đối phó vì cần phải tiến hành phân tích chương trình nguồn để tìm ra chỗ sơ hở. V.4. Mối đe dọa từ hệ thống Hầu hết các hệ điều hành đều cung cấp phương tiện cho phép các tiến trình khi hoạt động có thể tạo ra (spawn) những tiến trình khác. Trong các môi trường như thế, tài nguyên hệ thống và các tập tin của người dùng có thể bị sử dụng sai lạc để gây tác hại. Hai phương pháp phổ biến để phá hoại hệ thống theo phương thức này là : V.4.1. Các chương trình « sâu bọ » ( Worm) Một chương trình « sâu bọ » là chương trình lợi dụng cơ chế phát sinh tiến trình của hệ thống để đánh bại chính hệ thống. Tiến trình « sâu bo »ï có khả năng tự động phát sinh các phiên bản ngay cả trên môi trường mạng, lan tràn trên nhiều máy tính khác nhau, sau đó chiếm dụng các tài nguyên hệ thống và làm ngừng trệ hoàn toàn hoạt động của các tiến trình khác trên hệ thống mạng . Ví dụ : chương trình của Robert Tappan Morris, 11/1988 lan truyền trên Internet V.4.2. Các chương trình Virus Virus là một dạng phá hoại nguy hiểm khác đối với các hệ thống thông tin. Khác với « sâu bọ » là những chương trình hoàn chỉnh, virus chỉ là những đoạn code có khả năng lây truyền vào các chương trình chính thống khác và từ đó tàn phá hệ thống. Virus thường hoành hành trên các máy đơn, và chủ yếu lây truyền giữa các máy qua việc trao đổi đĩa mềm. V.5. Giám sát các mối đe doạ Nhìn chung việc bảo đảm an toàn hệ thống là rất khó do có các yếu tố con người. Hệ điều hành chỉ có thể áp dụng một số kỹ thuật để giảm bớt khả năng bị phá hoại như ghi nhận các sự kiện như : cố gắng nhập nhiều lần password sai sử dụng các password dễ đoán các tiến trình với định danh nghi ngờ không được ủy quyền các tiến trình không được ủy quyền trong những thư mục hệ thống các chương trình kéo dài xử lý một cách đáng ngờ bảo vệ các tập tin và thư mục không hợp lý thay đổi kích thước của các chương trình hệ thống Việc kiểm tra thường kỳ và ghi nhận các thông tin này giúp hệ thống phát hiện kịp thời các nguy cơ, và cho phép phân tích , dự đoán các cách đối phó về sau. VI. Tóm tắt Các đối tượng trong hệ thống ( có thể là phần cứng như CPU, bộ nhớ chính ; hay phần mềm như tập tin, chương trình) cần phải được bảo vệ khỏi sự sử dụng sai trái. Điều này có thể thực hiện được bằng cách đặt các đối tượng vào những miền bảo vệ thích hợp với các quyền truy xuất được định nghĩa trên đó. Quyền truy xuất trên một đối tượng là thao tác đượcphép thực hiện trên đối tượng đó. Miền bảo vệ là tập các quyền truy xuất trên một số các đối tượng. Mỗi tiến trình sẽ hoạt động trong một miền bảo vệ tại một thời điểm. Ma trận quyền truy xuất là mô hình tổng quát cho bài toán bảo vệ hệ thống. Ma trận này có thể được cài đặt như một mảng, các danh sách quyền truy xuất hoặc các danh sách tiềm năng. Mô hình bảo vệ động cho phép tiến trình có thể chuyển đổi miền bảo vệ trong thời gian xử lý. Có thể tổ chức mô hình bảo vệ động nếu xem các miền bảo vệ và bản thân ma trận quyền truy xuất cũng là các đối tượng trong hệ thống. An toàn hệ thống không chỉ quan tâm đến các nguy cơ nội bộ hệ thống, mà phải đối phó với cả các nguy cơ từ môi trường ngoài. 92