Chương 8: Tổ chức bộ nhớ ảo

8.1 Mở đầu

Thuật ngữ virtual memory thường gắn liền với khả năng đánh địa chỉ cho không gian nhớ lớn hơn nhiều dung lượng bộ nhớ vật lý. Virtual memory xuất hiện (ứng dụng) lần đầu vào năm 1960 tại trường đại học Manchester và sau đó nhanh chóng được phổ biến.

Có hai phương pháp được chấp nhận một cách tự nhiên khi thực hiện (tổ chức) bộ nhớ ảo: đó là tổ chức theo trang (page) và theo phân đoạn (segment). Trong một số hệ thống, ứng dụng một trong hai phương pháp đó còn trong một số khác thì áp dụng tổ hợp cả hai phương pháp.

Tất cả các cơ chế bộ nhớ ảo đều đặc trưng bởi tính chất rằng địa chỉ được tính bởi chương trình, không nhất thiết phải trùng với địa chỉ bộ nhớ (vật lý). Trong thực tế địa chỉ ảo thể hiện không gian lớn hơn nhiều so với thực tế bộ nhớ vật lý.

8.2 Quá trình phát triển các dạng tổ chức bộ nhớ

H.8.1 biểu diễn quá trình phát triển từ các hệ thống bộ nhớ thực đơn nhiệm (1 user) đến các hệ thống bộ nhớ ảo sử dụng tổ hợp cả hai phương pháp page và segment. Vì tổ chức bộ nhớ ảo phức tạp hơn nhiều nên có hai chương: C8: tổ chức bộ nhớ ảo và C9: điều khiển bộ nhớ ảo

Hình 8.1

8.3 Bộ nhớ ảo: các khái niệm cơ bản

Cốt lõi các khái niệm về bộ nhớ ảo là ở chỗ địa chỉ mà process có thể truy nhập gọi là không gian địa chỉ ảo V của process đó, còn vùng địa chỉ thực tồn tại trong bộ nhớ gọi là không gian địa chỉ thực R.

Dù rằng process làm việc với địa chỉ ảo thì thật sự chúng phải làm việc với bộ nhớ. Do đó vào thời gian thực hiện process, các địa chỉ ảo cần phải biến đổi thành địa chỉ thực, ngoài ra việc xử lý phải nhanh chóng vì nếu không thì hiệu quả của máy tính có thể giảm tới mức không chấp nhận được và lợi ích của tổ chức bộ nhớ ảo không thể ứng dụng được.

Hình vẽ: ánh xạ các ô nhớ từ bộ nhớ vật lý sang bộ nhớ ảo

Để xác định ánh xạ giữa địa chỉ thực và ảo, người ta đ• thiết kế các phương pháp khác nhau. Cơ chế biến đổi địa chỉ động (DAT-dynamic address translation) đảm bảo sự biến đổi địa chỉ ảo sang địa chỉ ảo vào thời gian thực hiện process. Tất cả các hệ thống đó đều có tính chất chung: đó là các địa chỉ ảo liền nhau chưa chắc đ• tương ứng với các địa chỉ thực liền nhau (h.8.3). Như thế user không cần phải quan tâm đến việc nạp chương trình hay dữ liệu của mình trong bộ nhớ (vật lý). Anh ta có được khả năng viết chương trình một cách tự nhiên hơn, chỉ phải quan tâm đến các vấn đề thiết kế chương trình, thuật toán mà không cần để ý đến chi tiết cụ thể của thíêt bị. Khi đó máy tính (có thể) được coi như là một cài gì đó trừu tượng hơn- một công cụ logic nào đó để chạy chương trình chứ không phải như một cái máy vật lý với các chi tiết cần để ý, làm khó khăn cho quá trình thiết kế chương trình.

Hình 8.3

8.4 Tổ chức bộ nhớ nhiều lớp

Nếu như chúng ta đề ra rằng không gian địa chỉ ảo của user sẽ lớn hơn không gian địa chỉ thực, và nếu chúng ta định hướng rằng hệ thống sẽ làm việc tốt trong chế độ đa nhiệm và tài nguyên bộ nhớ được chia sẻ (dùng chung), thì chúng ta cần có môi trường, công cụ lưu trữ chương trình, dữ liệu trong bộ nhớ thứ cấp. Thường thì người ta sử dụng mô hình bộ nhớ hai cấp (h.8.4). Lớp thứ nhất- bộ nhớ vật lý, tại đó cần nạp các chương trình đựơc thực hiện và các dữ liệu cần truy cập. Lớp thứ hai- bộ nhớ ngoài có dung lượng lớn để lưu trữ các chương trình, dữ liệu lúc đó chưa cần nạp.

Để chạy chương trình, code và dữ liệu của nó cần được đưa vào bộ nhớ

Hình 8.4

Bởi vì bộ nhớ thực hiện được chia sẻ giữa nhiều chương trình và mỗi chương trình (process) có thể có không gian địa chỉ ảo lớn hơn không gian địa chỉ thực do đó vào thời gian thực hiện, chỉ có một phần m• (code) và dữ liệu của mỗi process nằm trong bộ nhớ thực. Trên h.8.5 thể hiện cấu trúc bộ nhớ hai lớp, trong bộ nhớ thực lưu chỉ một phần bộ nhớ ảo của các chương trình.

Hình 8.5

8.5 Blocking mapping: ánh xạ theo khối

Cơ chế biến đổi địa chỉ động (DAT) phải sử dụng các bảng ánh xạ - chỉ rằng các ô nhớ ảo nào tại thời điểm hiện thời nằm trong bộ nhớ và ở ô nhớ thực nào. Nếu như ánh xạ được thực hiện theo từng byte hay word thì rõ ràng thông tin về ánh xạ còn lớn hơn bản thân bộ nhớ thực. Do đó để có thể áp dụng bộ nhớ ảo, cần có phương pháp cho phép giảm kích thước của bảng ánh xạ.

Vì ánh xạ từng ô nhớ là không thể chấp nhận, chúng ta phải gộp theo các khối - block, và hệ thống theo dõi xem các block của bộ nhớ ảo nằm đâu trong bộ nhớ. Kích thước block càng lớn thì thông tin về ánh xạ càng nhỏ, nhưng các block lớn lại cần nhiều thời gian nạp hơn và ngoài ra với xác suất lớn còn hạn chế số process có thể chia sẻ chung bộ nhớ vật lý.

Khi thiết kế cơ chế bộ nhớ ảo xuất hiện câu hỏi là các block có kích thước như nhau hay khác nhau. Nếu các block có kích thước như nhau thì chúng (block) được gọi là các trang (page), còn tổ chức bộ nhớ ảo tương ứng gọi là tổ chức theo trang. Nếu các block có thể có kích thước khác nhau thì chúng được gọi là các đoạn (segment), tổ chức bộ nhớ ảo  là tổ chức theo đoạn. Trong một số hệ thống cả hai cách được tổ hợp tức là các segment được tạo thành từ các page có kích thước như nhau.

Các địa chỉ trong các hệ thống ánh xạ theo khối là các địa chỉ gồm hai thành phần (hai chiều). Để truy nhập đến một dữ liệu cụ thể, program chỉ ra block và offset của dữ liệu trong block của dữ liệu trong block đó (h.8.6)

Địa chỉ ảo V được chỉ ra với cặp số v=(b,d) trong đó b- số block (số thứ tự) còn d- offset (độ lệch) tương đối so với đầu block.

Sự biến đổi từ địa chỉ ảo v=(b,d) thành địa chỉ thực r được thực hiện như trên hình 8.7. Mỗi process có bảng ánh xạ block của mình (nằm trong bộ nhớ thực). Địa chỉ thực a của bảng này được nạp vào thanh ghi riêng của BXL gọi là thanh ghi địa chỉ (đầu) của bảng ánh xạ (block table origin register). Mỗi dòng của bảng ánh xạ chứa ánh xạ của một block của process, ngoài ra các dòng được sắp xếp theo thứ tự số block, từ block 0, block 1. Số block b được cộng với địa chỉ cơ sở của bảng ánh xạ a, ta được địa chỉ thực của dòng chứa ánh xạ của block b. Dòng này chứa địa chỉ thực b' của block b. Sau đó cộng thêm vào địa chỉ b' này với offset d ta được địa chỉ thực cần tìm r=b'+d. Tất cả các phương pháp block mapping dùng trong các hệ thống tổ chức theo trang, segment hay tổ hợp được thể hiện trên h.8.7

Hình 8.7

Cần phải để ý rằng block mapping được thực hiện động (dynamic) ngay trong thời gian thực hiện process. Nếu cơ chế biến đổi địa chỉ DAT không đủ hiệu quả, thì chi phí của nó có thể làm giảm hiệu suất của hệ thống tới mức vượt quá ưu thế mà bộ nhớ ảo mang lại.

8.6 Tổ chức theo trang: các khái niệm cơ bản

Chúng ta xem xét ánh xạ theo khối với kích thước cố định tức là tổ chức bộ nhớ theo trang. Trong phần này chúng ta chỉ xem xét tổ chức theo trang thuần tuý.

Địa chỉ ảo trong hệ thống theo trang được thể hiện bằng cặp v=(p,d) trong đó p- số thứ tự trang trong bộ nhớ ảo còn d-offset trong trang p (h.8.8)

Hình 8.8

Process có thể được thực hiện tiếp nếu trang hiện thời cần đến của nó nằm trong bộ nhớ thực. Các trang được ghi từ bộ nhớ ngoài vào bộ nhớ thực, theo các block gọi là page frame và có kích thước đúng bằng kích thước trang. Các page frame bắt đầu từ các địa chỉ (trong bộ nhớ thực) là bội số của kích thước trang (h.8.9). Các trang có thể được nạp vào bất kỳ page frame trống nào.

Hình 8.9

Biến đổi địa chỉ động trong hệ thống tổ chức theo trang, thực hiện theo cách sau: Process truy nhập đến địa chỉ ảo v=(p,d). Cơ chế ánh xạ trang thể hiện trên h.8.10, đầu tiên tìm số trang p trong bảng ánh xạ trang và xác định được page frame p' tương ứng với trang p. Địa chỉ thực được tính bằng tổng của p' và d.

Hình 8.10

Chúng ta sẽ xem xét quá trình này kỹ hơn. Trong thực tế, thường thì không phải tất cả các page của process đều nằm trong bộ nhớ, do đó bảng ánh xạ phải chỉ ra là trang cần truy nhập có nằm trong bộ nhớ không và nằm ở đâu, còn nếu không thì nó nằm đâu trong bộ nhớ ngoài. Trên h.8.11 biểu diễn một dòng dữ liệu trong bảng ánh xạ trang. Bit flag r chỉ ra sự hiện diện của trang trong bộ nhớ: nếu r=1 tức là trang nằm trong bộ nhớ thực, còn nếu r=0 thì trang đó hiện không có trong bộ nhớ thực. Nếu như trang đó không có trong bộ nhớ thì s là địa chỉ (vị trí) của trang trong  bộ nhớ ngoài, còn nếu nó nằm trong bộ nhớ thì p' là số page frame. Chú ý rằng p' không phải là địa chỉ thực thật sự. Địa chỉ thực a -  của page frame p' được tính bằng a=(p)*(p') (số trang p có giá trị từ 0.1.2.3...)

Hình 8.11

Để tiết kiệm bộ nhớ (giảm kích thước của bảng ánh xạ) thì mỗi dòng có thể không cần chứa thông tin địa chỉ của trang trong bộ nhớ ngoài.

8.6.1 Biến đổi địa chỉ, ánh xạ trực tiếp

Chúng ta sẽ xem xét một số phương pháp biến đổi địa chỉ trang. Đầu tiên chúng ta sẽ xem xét biến đổi (ánh xạ) trực tiếp, được biểu diễn trên h.8.12

Hình 8.12

Process đưa yêu cầu truy cập địa chỉ ảo v=(p,d). Trước khi process tiếp tục thực hiện, OS nạp địa chỉ thực của bảng ánh xạ trang vào thanh ghi. Địa chỉ cơ sở b này được cộng với số trang p, thu được địa chỉ thực b+p của dòng chứa ánh xạ trang p. Dòng này chỉ ra page frame p' của p. Sau đó page frame được cộng với offset d và ta có địa chỉ thực r. Cách tính này gọi là phương pháp biến đổi trực tiếp (ánh xạ trực tiếp), bởi vì bảng ánh xạ trang chứa  từng dòng cho mỗi trang bộ nhớ ảo của process. Nếu process có n trang bộ nhớ ảo thì bảng ánh xạ trong phương pháp ánh xạ trực tiếp chứa n dòng liên tiếp cho các trang từ 0 đến n-1

Địa chỉ ảo cần tính và địa chỉ bảng ánh xạ đều chứa trong các thanh ghi của BXL do đó các thao tác với chúng có thể thực hiện rất nhanh trong vòng xử lý lệnh. Nhưng còn bảng ánh xạ, kích thước khá lớn, thường nằm trong bộ nhớ, do đó để truy nhập nó cần một thao tác đọc bộ nhớ. Vì thời gian đọc dữ liệu từ bộ nhớ lớn hơn nhiều thời gian xử lý lệnh và chúng ta cần thêm một lần đọc bộ nhớ để lấy được dòng cần thiết của bảng anhý xạ, điều đó có nghĩa là phương pháp ánh xạ trực tiếp có thể làm giảm tốc độ của hệ thống khi thực hiện chương trình gần hai lần. Điều đó tất nhiên không chấp nhận được, do đó cần có các phương pháp biến đổi địa chỉ nhanh hơn. Nhưng điều đó cũng không có nghĩa là phương pháp này hoàn toàn không thể áp dụng, ví dụ như trong một số hệ thống đ• sử dụng phương pháp này thành công bằng cách lưu toàn bộ bảng ánh xạ trong cache memory có tốc độ rất cao.

8.6.2 Biến đổi địa chỉ trang dùng bộ nhớ kết hợp associative memory

Một trong số các phương pháp cải thiện tốc độ của DAT là lưu toàn bộ bảng ánh xạ trang trong associative memory (bộ nhớ kết hợp)- với associative memory thời gian truy nhập (access cycle) nhỏ hơn nhiều lần so với bộ nhớ thông thường. Trên h.8.13 biểu diễn quá trình thực hiện biến đổi địa chỉ động chỉ dùng associative memory. Chương trình truy nhập đến địa chỉ ảo v=(p,d). Tất cả các dòng (record) của bảng (nằm trong associative memory) được so sánh đồng thời với p. Associative memory trả lại giá trị p' - địa chỉ của page frame của p. Sau đó cộng p' với offset d ta có địa chỉ thực r.

Hình 8.13

Chúng ta để ý rằng các mũi tên đi đi tới associative memory tới tất cả các bản ghi (dòng) của bảng. Điều đó có nghĩa là mỗi phần tử của associative memory được phân tích đồng thời với địa chỉ p. Cũng vì tính chất này mà bộ nhớ kết hợp rất đắt.

ở đây chúng ta lại gặp vấn đề kinh tế: để có thể ứng dụng thành công bộ nhớ ảo cần có cơ chế biến đổi địa chỉ động (DAT) tốc độ cao. Nhưng dù sao sử dụng cache memory hay associative memory thì đều quá đắt. Chúng ta cần có một giải pháp trung gian nào đó vẫn đảm bảo tốc độ nhưng giá cả phải chăng.

8.6.3 Biến đổi địa chỉ trang sử dụng kết hợp associative với ánh xạ trực tiếp.

Đến lúc này chúng ta luôn định hướng đến các công cụ phần cứng để thực hiện bộ nhớ ảo. Nhưng chúng ta sẽ xem xét các thiết bị một cách logic (trừu tượng) hơn là vật lý. Chúng ta quan tâm không phải là một thiết bị cụ thể (vật lý) mà là tổ chức, chức năng và tốc độ của chúng.

Vì giá của cache memory và associative mrmory quá đắt so với RAM do đó chúng ta cần giải pháp trung gian để thực hiện ánh xạ trang. Trong giải pháp này chúng ta sử dụng associative memory để lưu giữ một phần của bảng ánh xạ (h.8.14). Trong bảng đó chỉ chứa các ánh xạ trang được truy nhập gần nhất (về thời gian)- điều đó xuất phát từ kết quả tương đối là trang đ• được truy nhập trong thời gian gần nhất hoàn toàn có thể (với xác suất lớn) lại được truy nhập tiếp. Trong các hệ thống hiện xđại sử dụng phương pháp kết hợp này, chỉ số tốc độ đạt tới 90% hoặc hơn nữa so với khi hoàn toàn chỉ dùng associative memory.

Hình 8.14

Sự biến đổi địa chỉ động được thực hiện theo cách sau: Chương trình cần truy nhập theo địa chỉ ảo v=(p,d). Cơ chế biến đổi địa chỉ đầu tiên sẽ thử tìm ánh xạ của trang ảo p trong phần bảng ánh xạ nằm trong associative memory. Nếu như ánh xạ trang p có ở đó thì bảng ánh xạ trong associative memory trả lại kết quả số page frame p' tương ứng với trang ảo p và giá trị p' này được cộng với offset d, ta có được địa chỉ thực r tương ứng với  địa chỉ ảo v=(p,d).

Để đảm bảo chỉ số tốc độ cao, bảng ánh xạ trong asociative memory phải không lớn quá. Thật vậy, trong thực tế, với các hệ thống sử dụng chỉ 8 hoặc 16 thanh ghi asociative memory, có thể đạt được 90% hoặc hơn nữa tốc độ khi sử dụng hoàn toàn associative memory (khi đó kích thước associative memory có thể lớn gấp hàng chục đến 100 lần). Có được kết quả đó là nhờ tính chất đặc biệt của các process hoạt động, gọi là tính địa phương - locality, hiện tượng này chúng ta sẽ xem xét sau.

Sử dụng cơ chế kết hợp đó là lời giải kỹ thuật dựa trên các thông số kinh tế của các thiết bị hiện có.

8.6.4 Chia sẻ (dùng chung) chương trình và dữ liệu trong hệ thống tổ chức trang

Trong các hệ đa nhiệm, đặc biệt các hệ phân chia thời gian, thường xảy ra trường hợp nhiều user cùng chạy các chương trình giống nhau. Nếu mỗi user đều dùng riêng một bản copy của chương trình thì một phần đáng kể bộ nhớ bị l•ng phí. Rõ ràng có một giải pháp- đó là sử dụng chung (chia sẻ) các trang có thể chia sẻ.

Sử dụng chung cần phải xử lý , theo dõi cẩn thận để ngăn chặn tình huống khi một process cố thay đổi dữ liệu mà cùng lúc đó process khác đang đọc. Trong nhiều hệ thống tiên tiến, có sử dụng chung bộ nhớ, thường các chương trình cấu tạo từ hai phần riêng biệt- vùng chương trình (procedure) và vùng dữ liệu (data). Các procedure cố định (không thay đổi) hay còn gọi là reentrant procedure, có thể dùng chung. Các dữ liệu tĩnh (ví dụ bảng thông tin cố định nào đó)- có thể dùng chung. Các procedure động (thay đổi) cũng không thể dùng chung.

Tất cả điều đó nói lên rằng mỗi trang bộ nhớ cần xác định xem có thể dùng chung hoặc không. Sau khi các trang của mỗi process được chia ra hai loại, trong hệ thống tổ chức theo trang thuần tuý việc chia sẻ bộ nhớ được biểu diễn trên h.8.15. Việc chia sẻ bộ nhớ làm giảm dung lượng bộ nhớ sử dụng và hệ thống có thể phục vụ số lượng user lớn hơn.

Hình 8.15

8.7 Tổ chức theo đoạn (segment)

Trong chương trước nói về bộ nhớ thực, chúng ta đ• thấy rằng trong các hệ thống đa nhiệm với phân đoạn thay đổi, việc phân bố bộ nhớ thường thực hiện theo các thuật toán 'first suitable', 'most suitable' hay 'least suitable' theo tương quan về kích thước các vùng trống. Nhưng vẫn có hạn chế là chương trình phải nạp vào một vùng liên tục.

Trong các hệ thống tổ chức theo segment, sự hạn chế đó có thể vượt qua, và cho phép chương trình (và dữ liệu) có thể nằm trong nhiều khối nhớ không liên tục (h.8.16); Tuy rằng bản thân các khối nhớ là một vùng nhớ liên tục nhưng chúng có thể có kích thước khác nhau.

Hình 8.16

Trong giải pháp này xuất hiện một số vấn đề thú vị. Ví dụ như vấn đề bảo vệ chương trình, bộ nhớ. Sử dụng cặp thanh ghi biên không còn tác dụng nữa. Vấn đề tương tự như thế với việc kiểm soát việc truy nhập bộ nhớ của một chương trình nào đó. Một trong những phương pháp thực hiện bảo vệ bộ nhớ trong các hệ thống tổ chức theo segment- đó là sử dụng khoá bảo vệ, như trên h.8.17

Hình vẽ: Bảo vệ bộ nhớ dùng khoá trong các hệ đa nhiệm với phân bố bộ nhớ thành các block. Khi giá trị khoá trong BXL được đặt bằng hai- tương ứng với user B, chương trình của user B chỉ có thể truy nhập đến các block bộ nhớ có cùng khoá (2) Việc điều khiển khoá bảo vệ được thực hiện bởi OS.

Địa chỉ ảo trong các hệ thống segment- là cặp số v=(s,d) trong đó s- số segment của bộ nhớ ảo, còn d- offset trong đoạn đó.

Hình 8.18: dạng địa chỉ ảo

Process có thể tiếp tục chỉ trong trườngh hợp segment hiện tại nằm trong bộ nhớ. Segment được nạp từ bộ nhớ ngoài vào bộ nhớ vật lý theo cả segment, và segment phải được nạp vào một vùng nhớ liên tục. Segment có thể được nạp vào bất kỳ vùng trống liên tục nào đủ lớn. Các chiến lược phân bố segment cũng giống như trong các hệ thống đa nhiệm với phân đoạn thay đổi, thường thì các thuật toán ' first suitable' và 'most suitable' hay được áp dụng.

Quá trình biến đổi địa chỉ động được thực hiện như h.8.19. Process truy nhập theo địa chỉ ảo v=(s,d). Cơ chế ánh xạ segment tìm và (nếu có) thì xác định địa chỉ đầu segment s'. Sau đó địa chỉ thực r được tính bằng tổng s' và d. Các chi tiết của quá trình biến đổi địa chỉ chúng ta sẽ xem xét sau.

Hình 8.19 

8.7.1 Điều khiển truy nhập trong hệ thống tổ chức segment

Cho phép mỗi process truy nhập không hạn chế đến segment bất kỳ là không thực tế. một trong những ưu thế của hệ thống tổ chức theo segment là khả năng kiểm soát truy nhập chặt chẽ. Mỗi process được trao một số quyền truy nhập xác định đối với một số segment nào đó còn phần lớn segment khác là hoàn toàn không được truy nhập.

Trong bảng 8.20 có liệt kê những dạng quyền truy nhập phổ thông nhất được áp dụng trong các hệ thống tiên tiến. Nếu process có quyền read thì nó có thể đọc (truy nhập) đến bất kỳ ô nhớ nào trong segment và khi cần nó có thể copy toàn bộ cả segment.

Nếu như process có quyền write thì nó có thể thay đổi nội dung của bất kỳ ô nhớ nào trong segment, và có thể thêm thông tin bổ sung vào segment. Khi cần nó cũng có thể xoá toàn bộ segment. Process có quyền execute thì nó có thể làm việc với segment như là với chương trình. Còn quyền truy nhập đến các segment dữ liệu thường là bị cấm.

Khi process có quyền append thì nó có thể thêm thông tin vào cuối segment, nhưng không được phép thay đổi thông tin đ• có.

Bảng 8.20

Quyền    Ký hiệu    Giải thích

Read    R    có quyền đọc thông tin

Write    W    có quyền thay đổi nội dung

Execute    E    có quyền thực hiện (chương trình)

Append    A    có quyền thêm thông tin vào cuối block

Trong bảng hệ thống có phân biệt 4 loại quyền truy nhập như trên, có thể có 16 chế độ điều khiển truy nhập- cho phép hay cấm mỗi loại. Tuy nhiên một số trong chúng là không có ý nghĩa, còn một số khác thì có. Để đơn giản chúng ta xem xét 8 tổ hợp quyền truy nhập đối với các quyền read, write và execute- như trong bảng 8.21

Hình 8.21

Trong chế độ 0 tất cả các hình thức truy nhập đều bị cấm. Chế độ này ngăn chặn sự truy nhập bất hợp pháp, process sẽ không thể truy nhập đến segment. Chế độ 1 chỉ cho phép thực hiện. Chế độ này cần thiết khi process chỉ cần được phép sử dụng chương trình trong segment nhưng không được thay đổi nó hay copy.

Chế độ 2 và 3 thực tế không áp dụng- không có logic khi cho phép process thay đổi nội dung của segment mà không cho pép đọc.

Chế độ 4 chỉ cho phép đọc. Chế độ này cần cho các quá trình tìm kiếm thông tin, nhưng không cho phép thay đổi chúng.

Chế độ 5 cho phép đọc và thực hiện. Chế độ này áp dụng trong các TH process được phép thực hiện chương trình trong segment nhưng không được thay đổi nó. Tuy nhiên process có thể copy segment và sau đó có thể thay đổi bản copy của mình.

Chế độ 6 cho phép đọc và ghi. Chế độ này thường áp dụng với segment chứa dữ liệu mà process có thể đọc hoặc ghi và dữ liệu cần tranghs TH vô tình cố thực hiện (vì segment đó không chứa chương trình)

Chế độ 7 không hạn chế quyền truy nhập. Chế độ này cần để cho phép process có toàn quyền làm việc với các segment của mình, hoặc khi user khác tin tưởng hoàn toàn -cho phép toàn quyền truy nhập segment của anh ta.

Các chế độ kiểm soát quyền truy nhập là cơ sở của việc bảo vệ segment và được áp dụng trong nhiều hệ thống.

8.7.2 Biến đổi địa chỉ segment-ánh xạ trực tiếp

Cũng như trong tổ chức theo trang, trong các hệ tổ chức segment có nhiều chiến lược thực hiện biến đổi địa chỉ của segment. Việc biến đổi địa chỉ có thể là ánh xạ trực tiếp, dùng associative memory hay kết hợp. Chúng ta sẽ xem xét biến đổi trực tiếp và toàn bộ bảng ánh xạ nằm trong  cache memory.

Dạng của bản ghi trong bảng ánh xạ thường có như h.8.22

Hình 8.22

Đầu tiên chúng ta xét TH khi quá trình biến đổi diễn ra bình thường và sau đó là một số TH có thể khác.

Process truy nhập theo địa chỉ ảo v=(s,d) trong đó s là số segment. Số segment s được cộng với địa chỉ cơ sở b- địa chỉ đầu của bảng ánh xạ- nằm trong thanh ghi. Ta có được địa chỉ thực của bảng ghi ánh xạ của segment s. Từ bảng ánh xạ ta có địa chỉ thực s', cộng s' với offset d ta được địa chỉ thực r=s'+d là địa chỉ thực tương ứng với địa chỉ ảo v=(s,d).

Trên h.8.22 chúng ta thấy dạng của một ánh xạ.

Bit dấu hiệu tồn tại r cho biết thời điểm đó segment có nằm trong bộ nhớ hay không. Nếu như có, thì s' là địa chỉ đầu của nó, còn nếu không có trong bộ nhớ thì a là địa chỉ bộ nhớ ngoài theo đó HĐH nạp segment để process có thể tiếp tục. Tất cả các thao tác truy nhập segment được kiểm soát theo độ dài segment l để luôn chắc chắn rằng chúng không vượt ra ngoài segment. Mỗi thao tác truy nhập segment còn được kiểm soát theo các bit bảo vệ để xác định xem thao tác đo có được phép hay không. Như thế, khi thực hiện biến đổi địa chỉ động, sau khi tìm đến dòng ánh xạ của một segment cụ thể s đầu tiên sẽ kiểm tra bit r để xác định xem lúc đó segment có nằm trong bộ nhớ hay không. Nếu không nằm trong bộ nhớ thì sinh ra một ngắt missing segment fault, theo đó OS nhận quyền điều khiển và nạp segment đó từ bộ nhớ ngoài (theo địa chỉ a). Sau khi nạp xong quá trình xử lý địa chỉ tiếp tục, offset d sẽ đựơc so sánh với độ dài l của segment. Nếu d>l thì sinh ra ngắt segment over flow fault, và OS không cho phép thực hiện. Nếu d nằm trong giới hạn thì tiếp tục kiểm tra theo các bit bảo vệ để xem tác vụ truy nhập có được phép hay không. Nếu đựơc phép thì mới cộng địa chỉ thực s' của segment với offset d và có được địa chỉ thực r=s'+d tương ứng với địa chỉ ảo v=(s,d). Còn nếu thao tác không được phép thì sẽ sinh ra ngắt segment protection fault và OS không cho thực hiện.

8.7.3 Chia sẻ (dùng chung) chương trình và dữ liệu trong các hệ thống tổ chức theo segment.

Một trong những ưu thế cơ bản của tổ chức theo segment so với tổ chức theo trang là ở chỗ tổ chức theo segment mang tính logic hơn là tính vật lý. Tổng quát thì các segment không bị giới hạn bởi kích thước cố định nào.  Chúng có thể có kích thước tuỳ TH cần thiết khác nhau. Ví dụ segment để lưu một bảng nào đó sẽ có kích thước tương ứng với bảng đó. Kích thước của segment chứa cấu trúc dữ liệu thay đổi, có thể thay đổi theo dữ liệu....

Hình 8.23: Chia sẻ bộ nhớ trong tổ chức theo segment

Chia sẻ chương trình, dữ liệu trong hệ thống tổ chức theo segment cũng đơn giản hơn hệ thống tổ chức trang. Ví dụ trong hệ thống tổ chức trang, có một bảng dữ liệu dùng chung nào đó có kích thước 3,5 trang, thì thay vì một con trỏ nói rằng 'bảng này dùng chung' chúng ta cần các con trỏ cho mỗi trang. Mặt khác làm việc với một phần của trang khó hơn nhiều. Tình trạng còn phức tạp hơn trong trường hợp cấu trúc dữ liệu động. Nếu dữ liệu mở rộng thêm một trang thì dấu hiệu sử dụng chung trang cần thay đổi ngay trong thời gian hoạt động của process. Còn trong hệ thống tổ chức segment, sau khi segment đ• được đánh dấu dùng chung, thì dữ liệu có thể thay đổi kích thước tuỳ ý mà không làm thay đổi dấu hiệu logic là segment đó được dùng chung.

Trên h.8.23 biểu diễn sự chia sẻ chương trình, dữ liệu trong hệ thống tổ chức segment, hai process dùng chung segment nếu trong các bảng ánh xạ segment có các bản ghi trỏ tới cùng một segment trong bộ nhớ.

8.8 Hệ thống kết hợp tổ chức trang -segment

Hệ thống tổ chức trang hay segment đều có những ưu điểm của mình trong hệ thống với bộ nhớ ảo. Từ giữa những năm 60, cụ thể hơn là bắt đầu từ hệ thống Multics của trường MIT, hệ TSS của IBM và nhiều hệ thống khác người ta đ• áp dụng kết hợp tổ chức theo trang- segment. Nhờ đó có được các ưu điểm của cả hai loại mô hình tổ chức bộ nhớ ảo. Các segment thường chứa nhiều trang, ngoài ra không nhất thiết là tất cả các trang của một segment nằm trong bộ nhớ cùng lúc và các trang liền nhau trong bộ nhớ ảo chưa chắc đ• ánh xạ lên các trang liền nhau trong bộ nhớ thực.

Các hệ thống tổ chức trang- segment sử dụng đánh địa chỉ gồm ba thành phần, tức là địa chỉ ảo v gồm 3 số v=(s,p,d) trong đó s- số segment, p- số trang trong segment và d- offset trong trang (h.8.24)

Hình 8.24: địa chỉ ảo v=(s,p,d)

8.8.1 Biến đổi địa chỉ động trong hệ thống kết hợp trang- segment

Bây giờ chúng ta xem xét sự biến đổi địa chỉ động trong các hệ thống tổ chức trang-segment sử dụng kết hợp ánh xạ trực tiếp và associative memory (h.8.25)

Process truy nhập theo địa chỉ ảo v=(s,p,d). Phần bảng ánh xạ trong associative memory chứa ánh xạ các trang truy nhập gần nhất. Hệ thống đầu tiên tìm kiếm bản ghi với tham số (s,p) trong associative memory. Nếu như kết quả là dương thì ta có địa chỉ page frame p' theo đó trang p nằm trong bộ nhớ thực. Cộng thêm offset d ta có địa chỉ thực r tương ứng với địa chỉ ảo v.

Thông thường thì phần lớn số yêu cầu biến đổi địa chỉ đều đạt được khi tìm trong associative memory. Nếu như không có địa chỉ cần tìm trong bộ nhớ kết hợp thì dùng phương pháp ánh xạ trực tiếp như sau: địa chỉ cơ sở b của bảng ánh xạ segment được cộng với số segment s,, ta có được địa chỉ b+s của bản ghi ánh xạ cho segment s trong bảng ánh xạ (trong RAM). Trong bản ghi này có chứa địa chỉ cơ sở s' của bảng ánh xạ trang của segment s. Sau đó cộng s' với số trang p, tạo thành địa chỉ p+ s' của bản ghi ánh xạ trang đối với trang p của segment s. Bảng này cho phép xác định trang ảo p tương ứng với số page frame p'. Cuối cùng cộng p' với offset d ta có địa chỉ thực r tương ứng với địa chỉ ảo v=(s,p,d).

Hình 8.25

Thuật toán trên thực hiện được tất nhiên là với điều kiện rằng tất cả các thông tin cần thiết phải nằm đúng chỗ của chúng. Nhưng tấ nhiên có nhiều lúc không phải như vậy. Việc tìm kiến trong bảng ánh xạ segment có thể chỉ ra rằng segment s không có trong bộ nhớ, lúc đó sinh ra ngắt missing segment fault; OS tìm segment trong bộ  nhớ ngoài, tạo cho nó bảng ánh xạ trang và nạp trang tương ứng vào bộ nhớ vào chỗ có thể là của một trang của process khác hay của process đó.Ngay cả khi segment nằm trong bộ nhớ, việc tìm kiến trong bảng ánh xạ trang có thể chỉ ra rằng trang cần thiết không có trong bộ nhớ, lúc đó sinh ra ngắt mising page fault, OS tìm trang cần thiết trong bộ nhớ ngoài và nạp nó vào bộ nhớ (hoàn toàn có thể vào chỗ của một trang khác- trang thứ hai sẽ bị đưa ra khỏi bộ nhớ)

Cũng như trong TH tổ chức segment thuần tuý, địa chỉ ảo có thể vượt ra ngoài giới hạn segment, khi đó sinh ra ngắt segment overflow fault. Hoặc khi kiểm tra các bit bảo vệ thì thấy rằng thao tác truy nhập đó bị cấm, lúc đó sinh ra ngắt segment protection fault và OS phải xử lý tất cả các tình huống này.

Bộ nhớ kết hợp (associative memory) hoặc hình thức bộ nhớ tốc độ cao khác (ví dụ cache) đóng vai trò rất quan trọng trong việc đảm bảo hiệu quả (về tốc độ) của cơ chế biến đổi địa chỉ động (DAT). Nếu như chỉ sử dụng ánh xạ trực tiếp tức là chỉ có bảng ánh xạ nằm trong bộ nhớ thì để truy nhập được đến ô nhớ cần thiết, ta phải thực hiện 3 lần thao tác đọc bộ nhớ:

Lần 1 để truy nhập đến bảng ánh xạ segment

Lần 2 để đọc ánh xạ trong bảng ánh xạ trang

Lần 3 mới là truy nhập ô nhớ mong muốn

Như vậy để truy nhập bộ nhớ cần 3 thao tác đọc bộ nhớ tức là tốc độ giảm gần 3 lần trong khi chỉ cần 8-16 thanh ghi bộ nhớ kết hợp để chứa các ánh xạ mới nhất là ta đ• có thể đạt 90% hoặc hơn về mặt tốc độ.

Trên h.8.26 biểu diễn cấu trúc các bảng cần trong hệ thống kết hợp page-segment. ở mức trên cùng là bảng các process, nó chứa các bản ghi thông tin địa chỉ bảng ánh xạ segment của process tương ứng, mỗi process (đang được hệ thống quản lý) có một bản ghi trong bảng process. Các bảng ánh xạ segment của các process chứa các bản ghi có số segment và địa chỉ bảng ánh xảtang của segment đó, còn mỗi bản ghi của bảng ánh xạ trang chỉ tới page frame của bộ nhớ thực- tại đó có trang bộ nhớ ảo tương ứng, hoặc địa chỉ bộ nhớ ngoài nơi có thể tìm đến trang đó.

Trong hệ thống có nhiều process, segment và trang, thì cấu trúc thông tin ánh xạ bộ nhớ có thể chiếm phần đáng kể bộ nhớ. Chúng ta lưu ý rằng quá trình biến đổi địa chỉ động thực hiện ngay trong quá trình hoạt động của process do đó các cấu trúc thông tin ánh xạ đều nằm trong bộ nhớ. Mặt khác các cấu trúc thông tin ánh xạ càng lớn thì bộ nhớ còn lại càng nhỏ và do đó số process hệ thống có thể phục vụ giảm, điều đó có thể dẫn tới giảm hiệu quả của hệ thống (giảm băng thông). Vì vậy người ta thiết kế OS cần phải chú ý đến rất nhiều nhân tố ảnh hưởng trái ngược nhau, phân tích để có được giả pháp cân bằng, có thể đảm bảo hiệu quả của hệ thống.

Hình 8.26

8.8.2 Chia sẻ chương trình, dữ liệu trong hệ thống tổ chức page-segment

Trong các hệ thống tổ chức trang-segment, các ưu thế của việc chia sẻ chương trình và dữ liệu dễ nhận hơn. Việc chia sẻ được thực hiện bằng cách trong các bảng ánh xạ segment của các process khác có các bản ghi chứa các con trỏ tới cùng một bảng ánh xạ trang (h.8.27)

Hình 8.27