Bài giảng Hệ điều hành

Mỗi khi deadlock được phát hiện, hệ điều hành thực hiện một vài giải pháp để thoát khỏi deadlock. Sau đây là một vài giải pháp có thể: (1) Thoát tất cả các tiến trình bị deadlock. Đây là một giải pháp đơn giản nhất, thường được các hệ điều hành sử dụng nhất. (2) Sao lưu lại mỗi tiến trình bị deadlock tại một vài điểm kiểm tra được định nghĩa trước, sau đó khởi động lại tất cả các tiến trình. Giải pháp này yêu cầu hệ điều hành phải lưu lại các thông tin cần thiết tại điểm dừng của tiến trình, đặc biệt là con trỏ lệnh và các tài nguyên tiến trình đang sử dụng, để có thể khởi động lại tiến trình được. Giải pháp này có nguy cơ xuất hiện deadlock trở lại là rất cao, vì khi tất cả các tiến trình đều được reset trở lại thì việc tranh chấp tài nguyên là khó tránh khỏi. Ngoài ra hệ điều hành thường phải chi phí rất cao cho việc tạm dừng và tái kích hoạt tiến trình. (3) Chỉ kết thúc một tiến trình trong tập tiến trình bị deadlock, thu hồi tài nguyên của tiến trình này, để cấp phát cho một tiến trình nào đó trong tập tiến trình deadlock để giúp tiến trình này ra khỏi deadlock, rồi gọi lại thuật toán kiểm tra deadlock để xem hệ thống đã ra khỏi deadlock hay chưa, nếu rồi thì dừng, nếu chưa thì tiếp tục giải phóng thêm tiến trình khác. Và lần lượt như thế cho đến khi tất cả các tiến trình trong tập tiến trình deadlock đều ra khỏi tình trạng deadlock. Trong giả pháp này vấn đề đặt ra đối với hệ điều hành là nên chọn tiến trình nào để giải phóng đầu tiên và dựa vào tiêu chuẩn nào để chọn lựa sao cho chi phí để giải phóng deadlock là thấp nhất. (4) Tập trung toàn bộ quyền ưu tiên sử dụng tài nguyên cho một tiến trình, để tiến trình này ra khỏi deadlock, và rồi kiểm tra xem hệ thống đã ra khỏi deadlock hay chưa, nếu rồi thì dừng lại, nếu chưa thì tiếp tục. Lần lượt như thế cho đến khi hệ thống ra khỏi deadlock. Trong giải pháp này hệ điều hành phải tính đến chuyện tái kích hoạt lại tiến trình sau khi hẹ thống ra khỏi deadlock. Đối với các giải pháp (3) và (4), hệ điều hành dựa vào các tiêu chuẩn sau đây để chọn lựa tiến trình giải phóng hay ưu tiên tài nguyên: Thời gian xử lý ít nhất; Thời gian cần CPU còn lại ít nhất; Tài nguyên cần cấp phát là ít nhất; Quyền ưu tiên là thấp nhất. Nếu phương pháp kết thúc được dùng thì với một tập hợp các quá trình deadlock được cho, chúng ta phải xác định quá trình nào nên được kết thúc trước trong sự cố 150

gắng để phá vỡ deadlock. Quyết định này dựa vào chính sách kinh tế mà chúng ta nên hủy bỏ quá trình nào thì sự kết thúc của quá trình đó sẽ chịu chi phí tối thiểu. Tuy nhiên, thuật ngữ chi phí tối thiểu là không chính xác. Nhiều yếu tố có thể xác định quá trình nào được chọn bao gồm:  Độ ưu tiên của quá trình là gì.  Quá trình đã được tính toán bao lâu và bao lâu nữa quá trình sẽ tính toán trước khi hoàn thành công việc được chỉ định của nó.  Bao nhiêu và loại tài nguyên gì quá trình đang sử dụng.  Bao nhiêu tài nguyên nữa quá trình cần để hoàn thành  Bao nhiêu quá trình sẽ cần được kết thúc.  Quá trình là giao tiếp hay dạng bó. 2.9. TÓM TẮT Trong suốt chu trình sống, tiến trình chuyển đổi qua lại giữa các trạng thái ready, running và blocked. Bộ định thời biểu của hệ điều hành chịu trách nhiệm áp dụng một gỉai thuật định thời thích hợp để chọn tiến trình phù hợp được sử dụng CPU, và bộ phân phát sẽ chuyển giao CPU cho tiến trình này. Các giải thuật định thời biểu thông dụng: FCFS, Round Robin, định thời biểu với độ ưu tiên, SJF, định thời biểu phản hồi đa cấp. Một số tiến trình trong hệ thống có nhu cầu trao đổi thông tin để phối hợp hoạt động, do mỗi tiến trình có một không gian địa chỉ độc lập nên việc liên lạc chỉ có thể thực hiện thông qua các cơ chế do hệ điều hành cung cấp. Khi các tiến trình trao đổi thông tin, chia sẻ tài nguyên chung, cần phải đồng bộ hoá hoạt động của chúng chủ yếu do yêu cầu độc quyền truy xuất hoặc phối hợp hoạt động. Miền găng là đoạn lệnh trong chương trình có khả năng phát sinh mâu thuẫn truy xuất. Để không xảy ra mâu thuẫn truy xuất, cần đảm bảo tại một thời điểm chỉ có một tiến trình được vào miền găng. Trạng thái deadlock xảy ra khi hai hay nhiều quá trình đang chờ không xác định một sự kiện mà có thể được gây ra chỉ bởi một trong những quá trình đang chờ. Về nguyên tắc, có ba phương pháp giải quyết deadlock: 151

 Sử dụng một số giao thức để ngăn chặn hay tránh deadlock, đảm bảo rằng hệ thống sẽ không bao giờ đi vào trạng thái deadlock.  Cho phép hệ thống đi vào trạng thái deadlock, phát hiện và sau đó phục hồi.  Bỏ qua vấn đề deadlock và giả vờ deadlock chưa bao giờ xảy ra trong hệ thống. Giải pháp này là một giải pháp được dùng bởi hầu hết các hệ điều hành bao gồm UNIX. Trường hợp deadlock có thể xảy ra nếu và chỉ nếu bốn điều kiện cần xảy ra cùng một lúc trong hệ thống: loại trừ lẫn nhau, giữ và chờ cấp thêm tài nguyên, không ưu tiên, và tồn tại chu trình trong đồ thị cấp phát tài nguyên. Để ngăn chặn deadlock, chúng ta đảm bảo rằng ít nhất một điều kiện cần không bao giờ xảy ra. Một phương pháp để tránh deadlock mà ít nghiêm ngặt hơn giải thuật ngăn chặn deadlock là có thông tin trước về mỗi quá trình sẽ đang dùng tài nguyên như thế nào. Ví dụ, giải thuật Banker cần biết số lượng tối đa của mỗi lớp tài nguyên có thể được yêu cầu bởi mỗi quá trình. Sử dụng thông tin này chúng ta có thể định nghĩa giải thuật tránh deadlock. Nếu hệ thống không thực hiện một giao thức để đảm bảo rằng deadlock sẽ không bao giờ xảy ra thì lược đồ phát hiện và phục hồi phải được thực hiện. Giải thuật phát hiện deadlock phải được nạp lên để xác định deadlock có thể xảy ra hay không. Nếu deadlock được phát hiện hệ thống phải phục hồi bằng cách kết thúc một số quá trình bị deadlock hay đòi lại tài nguyên từ một số quá trình bị deadlock. Trong một hệ thống mà nó chọn các nạn nhân để phục hồi về trạng thái trước đó chủ yếu dựa trên cơ sở yếu tố chi phí, việc đói tài nguyên có thể xảy ra. Kết quả là quá trình được chọn không bao giờ hoàn thành công việc được chỉ định của nó. 152

Câu hỏi ôn tập 1. Phân biệt tiến trình và tiểu trình? 2. Phân biệt chương trình và tiến trình? 3. Tiến trình có thể có bao nhiêu trạng thái? 4. Chương trình có phải là tiến trình không? Tại sao? 5. Thuật ngữ PCB có nghĩa là gì?Chức năng của nó? 6. Kể ra các tiêu chí điều phối tiến trình như thế nào thì tối ưu? 7. Định nghĩa thời gian hoàn thành, thông lượng, thời gian chờ ? 8. Nhận xét về thời gian chuyển ngữ cảnh của CPU? Thời gian CPU bỏ ra để chuyển từ việc phục vụ cho quá trình này sang quá trình khác, lúc này CPU làm gì? Tại sao những lần chuyển ngữ cảnh phụ thuộc nhiều vào hỗ trợ phần cứng? 9. Nêu ý nghĩa các chiến lược định thời biểu tiến trình? Phân tích ưu, khuyết của các chiến lược định thời biểu? Chiến lược nào tối ưu nhất? 10. Phân biệt chiến lược định thời biểu độc quyền (không trưng dụng) và không độc quyền (trưng dụng)?Chiến lược nào tối ưu hơn? 11. Ý tưởng của giải thuật SJF trưng dụng và không trưng dụng, Ưu điểm và khuyết điểm của giải thuật SJF, khó khăn thật sự của giải thuật này là gì? 12. Nêu giải pháp giải quyết vấn đề chết đói (Starvation) trong giải thuật lập lịch biểu theo kiểu ưu tiên trưng dụng (không độc quyền). 13. Tại sao phổ thời gian q trong giải thuật Round Robin phải được chọn là đủ lớn? 14. Kể tên các chiến lược phân công công việc của hệ điều hành? 15. Thế nào là miền găng hay đoạn găng (Critical Section)?cho ví dụ? 16. Phân biệt tài nguyên găng (Critical Resouce) và đoạn găng (CS)?cho ví dụ để phân biệt? điều kiện cho các tiến trình muốn sử dụng đoạn găng là gì? 17. Tại sao phải đồng bộ hóa quá trình? Các giải pháp để đồng bộ hóa?Thế nào là chờ đợi tích cực?Giải pháp được hổ trợ bởi hệ điều hành là giải pháp gì?nó có ưu điểm gì? 153

18. Phân biệt Deadlock và Starvation?Cho ví dụ trong hệ điều hành? 19. Đồ thị cấp phát tài nguyên sau có xảy ra deadlock không? Tại sao? R1 P1 P2 R2 20. Phương pháp quản lý deadlock?có thể đòi lại tài nguyên từ quá trình đạng bị deadlock hay không?Nếu có đòi lại bằng cách nào? 21. Tại sao phải xử lý song song?Nêu một số phương pháp lập trình xử lý song song? 22. Thuật ngữ Monitor trong hệ điều hành là gì?dùng Monitor để làm gì? 23. Thuật ngữ Semaphore là gì?dùng semaphore để làm gì? định nghĩa 2 thao thác truy cập semaphore? 24. Thuật ngữ race condition là gì?Lấy ví dụ trong hệ điều hành? 25. Hiện tượng “dùng đúp” dữ liệu và “mất dữ liệu” ở bài toán Producer và Cunsumer diễn ra khi nào? Biện pháp khắc phục? 26. Nêu giải pháp tránh tắc nghẽn cho bài toán 5 nhà triết gia ăn tối? 27. Nêu Ý nghĩa 3 bài toán nguyên thủy trong hệ điều hành? 28. Vấn đề bỏ qua hoàn toàn deadlock và xem như nó không xảy ra trong hệ thống có gây ảnh hưởng gì đến hệ thống không? Tại sao? 29. Tìm hiểu tiến trình trong Windows NT? 154

30. Giả sử một hệ thống ở trong trạng thái không an toàn nhưng không bị deadlock. Hệ thống có nhất thiết đi vào trạng thái deadlock hay không? Giải thích? 31. Xét một hệ thống gồm 4 loại tài nguyên cùng loại. Hệ thống có 3 quá trình, mỗi quá trình cần tối đa 2 tài nguyên. Chứng tỏ hệ thống không bị deadlocked. 32. Ý nghĩa đồ thị chờ?Vẽ đồ thị chờ biết rằng đồ thị cấp phát tài nguyên như sau? R1 R2 P2 P1 R5 P3 P4 R4 R3 33. Xác định thời lượng q là một nhiệm vụ khó khăn. Giả sử chi phí trung bình cho một lần chuyển đổi ngữ cảnh là s, và thời gian trung bình một tiến trình hướng nhập xuất sử dụng CPU trước khi phát sinh một yêu cầu nhập xuất là t ( t>>s). Thảo luận các tác động đến sự thực hiện của hệ thống khi chọn q theo các quy tắc sau : a) q = s b) s < q < t c) q = t d) q > t 34. Giả sử một hệ điều hành áp dụng giải thuật định thời biểu multilevel feedback với 5 mức ưu tiên (giảm dần). Thời lượng q dành cho hàng đợi cấp 1 là 0,5s. Mỗi hàng đợi cấp thấp hơn sẽ có thời lượng q dài gấp đôi hàng đợi ứng với mức ưu tiên cao hơn nó. Một tiến trình khi vào hệ thống sẽ được đưa vào hàng đợi mức cao nhất, và chuyển dần xuống các hàng đợi bên dưới sau mỗi lượt sử dụng CPU. Một tiến trình chỉ có thể bị thu hồi CPU khi đã sử dụng hết thời 155

lượng q dành cho nó. Hệ thống có thể thực hiện các công việc xử lý theo lô hoặc tương tác, và mỗi công việc lại có thể hướng xử lý hay hướng nhập xuất. a) Giải thích tại sao hệ thống này hoạt động không hiệu quả? b) Cần phải thay đổi (tối thiểu) như thế nào để hệ thống điều phối các công việc với những bản chất khác biệt như thế tốt hơn? Bài tập Bài 1. Xét tập các tiến trình sau (với thời gian yêu cầu CPU và độ ưu tiên kèm theo) Tiến trình Thời điểm vào RL Thời gian CPU Độ ưu tiên P1 0 10 3 P2 1 11 P3 2 23 P4 3 14 P5 4 52 Giả sử các tiến trình cùng được đưa vào hệ thống tại thời điểm 0 a) Cho biết kết quả định thời biểu hoạt động của các tiến trình trên theo giải thuật FCFS; SJF độc quyền và không độc quyền; định thời biểu theo độ ưu tiên độc quyền (độ ưu tiên 1 cao nhất); và RR (q=2). b) Cho biết thời gian lưu lại trong hệ thống (Turnaround Time) của từng tiến trình trong từng giải thuật định thời biểu ở câu a. c) Cho biết thời gian chờ trong hệ thống (Waiting time) của từng tiến trình trong từng giải thuật định thời biểu ở câu a. d) Cho biết thời gian chờ trung bình trong hệ thống đối với mỗi giải thuật định thời biểu ở câu a. e) Giải thuật định thời biểu nào trong các giải thuật ở câu a cho thời gian chờ trung bình là cực tiểu? 156

Bài 2. Giả sử có các tiến trình sau trong hệ thống : Tiến trình Thời điểm vào RL Thời gian CPU P1 0.0 8 P2 0.4 4 P3 1.0 1 Sử dụng chiến lược định thời biểu độc quyền và các thông tin có được tại thời điểm ra quyết định để trả lời các câu hỏi sau đây: a) Cho biết thời gian lưu lại trung bình trong hệ thống (Turnaround Time) của các tiến trình trong giải thuật định thời biểu FCFS. b) Cho biết thời gian lưu lại trung bình trong hệ thống (Turnaround Time) của các tiến trình trong giải thuật định thời biểu SJF không độc quyền. c) Giải thuật SJF dự định cải tiến sự thực hiện của hệ thống, nhưng lưu ý chúng ta phải chọn định thời biểu P1 tại thời điểm 0 vì không biết rằng sẽ có hai tiến trình ngắn hơn vào hệ thống sau đó. Thử tính thời gian lưu lại trung bình trong hệ thống nếu để CPU nhàn rỗi trong 1 đơn vị thời gian đầu tiên và sau đó sử dụng SJF để định thời biểu. Lưu ý P1 và P2 sẽ phải chờ trong suốt thời gian nhàn rỗi này, do vậy thời gian chờ của chúng tăng lên. Giải thuật định thời biểu này được biết đến như định thời biểu dựa trên thông tin về tương lai. Bài 3. Cho tập hợp các tiến trình như trong bảng. Có 4 hàng đợi: Q0, Q1, Q2, Q3 với phổ thời gian phục vụ như trong hình dưới. Hãy lập biểu đồ Gannt để minh họa sự thực thi của các tiến trình với giải thuật: hàng đợi phản hồi đa cấp. Tính thời gian chờ trung bình và tổng số lần chuyển đổi ngữ cảnh? Tiến trình Thời điểm vào RL Thời gian CPU(ms) P1 0 100 P2 10 75 P3 20 15 P4 25 8 P5 30 20 P6 40 50 157

Q0 Q1 Q2 Q3 Bài 4. Cho tập hợp các quá trình, ma trận max, allocation và 3 loại tài nguyên A (có 10 thể hiện), B (có 7 thể hiện), C (có 6 thể hiện). Allocation Max Available ? Need ? ABCABCABCABC P0 5 2 4 5 3 5 P1 2 1 0 6 4 4 P2 1 0 0 4 2 2 P3 1 2 1 2 4 3 a) Hệ thống có ở trạng thái an toàn không? Dãy <P0, P3, P1, P2> có phải là một dãy an toàn hay không? Tại sao? Nếu quá trình P0 yêu cầu thêm 1 tài nguyên loại B và 1 tài nguyên loại C thì thứ tự <P0, P3, P1, P2> có an toàn không? Và P0 có được cấp phát ngay lập tức hay không?Nếu không, P0 có thể cấp phát theo tứ tự nào? b) Có tất cả bao nhiêu thứ tự an toàn và không an toàn? Liệt kê tất cả các thứ tự an toàn?Liệt kê tất cả các thứ tự không an toàn? Bài 5: Hãy nêu cách xử lý song song cho các biểu thức sau trong một máy tính có hổ trợ xử lý song song. a. (-a + (b * (c/2) + (d * d * 4 * c))) / (2 * a) b.(-b + sqrt(b * b – 4 * a * c)) / (2 * a) c. sqrt(p * (p - a) * (p - b) * (p - c)) vớp p = (a + b + c) * 0.5 Lập trình Chương trình 1. Viết chương trình đa luồng thực hiện tính tổng n số nguyên đầu tiên (n nhập từ bàn phím) 158

Chương trình 2. Viết chương trình đa luồng thực hiện tính tích phân từ a đến b của hàm f(x). Chương trình 3. Chương trình tính tích của 2 ma trận A và B kích thước nxm và giá trị các phần tử trong ma trận được khởi tạo là các số nguyên ngẫu nhiên từ 1 đến 100. Chương trình 4. Chương trình sắp xếp giá trị các phần tử trong ma trận tăng dần (giảm dần), giá trị các phần tử trong ma trận được khởi tạo là các số nguyên ngẫu nhiên từ 1 đến 100. Chương trình 5. Chương trình mô phỏng bài toán 5 nhà triết gia ăn tối. và giải quyết tình trạng deadlocked cho bài toán này. Chương trình 6. Một phòng máy tính gồm 40 máy, số lượng sinh viên cần sử dụng là nhiều hơn số máy. Hãy viết chương trình xử lý việc sử dụng máy tính sao cho mỗi máy chỉ có một sinh viên được sử dụng. Chương trình 7. Trong giảng đường có n ghế, sinh viên đăng ký vào học thông thường lớn hơn số ghế 10%. Hãy viết chương trình mô phỏng sinh viên vào lớp học, nếu có ghế thì vào học, ngược lại nghỉ. Ghi chú: Học viên có thể tự chọn bài toán có tính chất song song để lập trình. 159

TÀI LIỆU THAM KHẢO [3] Trần Hạnh Nhi, Giáo trình hệ điều hành nâng cao, Đại học Khoa học Tự nhiên TP.HCM, 2003. [4] [Lê Khắc Nhiên Ân, Hoàng Kiếm], Giáo trình Nhập môn hệ điều hành, Đại học Khoa học Tự nhiên TP.HCM, 2003. [5] Nguyễn Kim Tuấn, Giáo trình Hệ điều hành, Đại học Huế, 2004. [6] Nguyễn Phú Trường, Giáo trình Hệ điều hành, Đại học Cần Thơ,2005. 160

CHƯƠNG 3: QUẢN LÝ BỘ NHỚ 3.1. MỤC TIÊU Bài học này sẽ giúp các bạn hình dung những vấn đề cần quan tâm khi thiết kế thành phần quản lý bộ nhớ của hệ điều hành. Sau khi học xong chương này, người học nắm được những kiến thức sau:  Hiểu các cách khác nhau để quản lý bộ nhớ  Hiểu tiếp cận quản lý bộ dùng kỹ thuật phân trang và phân đoạn  Vận dụng một tiếp cận quản lý bộ nhớ phù hợp với hệ thống xác định Bộ nhớ chính là thiết bị lưu trữ duy nhất thông qua đó CPU có thể trao đổi thông tin với môi trường ngoài, do vậy nhu cầu tổ chức, quản lý bộ nhớ là một trong những nhiệm vụ trọng tâm hàng đầu của hệ điều hành. Bộ nhớ chính được tổ chức như một mảng một chiều các từ nhớ (word), mỗi từ nhớ có một địa chỉ. Việc trao đổi thông tin với môi trường ngoài được thực hiện thông qua các thao tác đọc hoặc ghi dữ liệu vào một địa chỉ cụ thể nào đó trong bộ nhớ. 3.2. NHIỆM VỤ QUẢN LÝ BỘ NHỚ Trong các hệ thống đơn chương trình (uniprogramming), trên bộ nhớ chính ngoài hệ điều hành, chỉ có một chương trình đang thực hiện. Trong các hệ thống đa chương (multiprogramming) trên bộ nhớ chính ngoài hệ điều hành, có thể có nhiều tiến trình đang hoạt động. Do đó nhiệm vụ quản lý bộ nhớ của hệ điều hành trong hệ thống đa chương trình sẽ phức tạp hơn nhiều so với trong hệ thống đơn chương trình. Trong hệ thống đa chương bộ phận quản lý bộ nhớ phải có nhiệm vụ đưa bất kỳ một tiến trình vào bộ nhớ khi có yêu cầu, kể cả khi trên bộ nhớ chính không còn không gian trống, ngoài ra nó phải bảo vệ chính hệ điều hành và các tiến trình trên bộ nhớ tránh các trường hợp truy xuất bất hợp lệ xảy ra. Như vậy việc quản lý bộ nhớ trong các hệ thống đa chương là quan trọng và cần thiết. Khi thiết kế thành phần quản lý bộ nhớ phải thực hiện các nhiệm vụ sau đây: Sự tương ứng giữa địa chỉ logic và địa chỉ vật lý: làm cách nào để chuyển đổi một địa chỉ dạng danh biểu tượng trưng (symbolic) trong chương trình người dùng thành một địa chỉ thực trong bộ nhớ chính? Nhiệm vụ này được thực hiện bởi đơn 161

vị quản lý bộ nhớ MMU (Memory Management Unit) được định nghĩa trong phần sau. Sự tái định vị (Relocation): Trong các hệ thống đa chương, không gian bộ nhớ chính thường được chia sẻ cho nhiều tiến trình khác nhau và yêu cầu bộ nhớ của các tiến trình luôn lớn hơn không gian bộ nhớ vật lý mà hệ thống có được. Vấn đề là không gian bộ nhớ là có hạn trong khi yêu cầu bộ nhớ của tiến trình là vô hạn. Do dó, một chương trình đang hoạt động trên bộ nhớ cũng có thể bị đưa ra đĩa (swap out) và nó sẽ được đưa vào lại (swap in) bộ nhớ tại một thời điểm thích hợp sau đó. Đây là cơ chế hoán vị (Swap). Bảo vệ bộ nhớ (Protection): làm thế nào để ngăn chặn các tiến trình xâm phạm đến vùng nhớ được cấp phát cho tiến trình khác? Mỗi tiến trình phải được bảo vệ để chống lại sự truy xuất bất hợp lệ vô tình hay có chủ ý của các tiến trình khác. Để thực hiện điều này hệ thống quản lý bộ nhớ phải biết được không gian địa chỉ của các tiến trình khác trên bộ nhớ và phải kiểm tra tất cả các yêu cầu truy xuất bộ nhớ của mỗi tiến trình khi tiến trình đưa ra địa chỉ truy xuất. Điều này khó thực hiện vì không thể xác định địa chỉ của các chương trình trong bộ nhớ chính trong quá trình biên dịch mà phải thực hiện việc tính toán địa chỉ tại thời điểm chạy chương trình. Hệ điều hành có nhiều chiến lược khác nhau để thực hiện điều này. Điều quan trọng nhất mà hệ thống quản lý bộ nhớ phải thực hiện là không cho phép các tiến trình của người dùng truy cập đến bất kỳ một vị trí nào của chính hệ điều hành, ngoại trừ vùng dữ liệu và các rountine mà hệ điều hành cung cấp cho chương trình người dùng. Chia sẻ thông tin: làm thế nào để cho phép hai tiến trình có thể chia sẻ thông tin trong bộ nhớ? Bất kỳ một chiến lược nào được cài đặt đều phải có tính mềm dẻo để cho phép nhiều tiến trình có thể truy cập đến cùng một địa chỉ trên bộ nhớ chính. Ví dụ, khi có nhiều tiến trình cùng thực hiện một chương trình thì việc cho phép mỗi tiến trình cùng truy cập đến một bản copy của chương trình sẽ thuận lợi hơn khi cho phép mỗi tiến trình truy cập đến một bản copy sở hữu riêng. Các tiến trình đồng thực hiện trên một vài công việc có thể cần để chia sẻ truy cập đến cùng một cấu trúc dữ liệu. Hệ thống quản lý bộ nhớ phải điều khiển việc truy cập đến không gian bộ nhớ được chia sẻ mà không vi phạm đến các yêu cầu bảo vệ bộ nhớ. Ngoài ra, trong môi 162

trường hệ điều hành đa nhiệm hệ điều hành phải chia sẻ không gian nhớ cho các tiến trình để hệ điều hành có thể nạp được nhiều tiến trình vào bộ nhớ để các tiến trình này có thể hoạt động đồng thời với nhau. Tổ chức bộ nhớ logic: Bộ nhớ chính của hệ thống máy tính được tổ chức như là một dòng hoặc một mảng, không gian địa chỉ bao gồm một dãy có thứ tự các Byte hoặc các word. Bộ nhớ phụ cũng được tổ chức tương tự. Mặc dù việc tổ chức này có sự kết hợp chặt chẽ với phần cứng thực tế của máy nhưng nó không phù hợp với các chương trình. Đa số các chương trình đều được chia thành các module, một vài trong số đó là không thể thay đổi (read only, execute only) và một vài trong số đó chứa dữ liệu là có thể thay đổi. Và không gian địa chỉ logic của chương trình này sẽ do CPU sinh ra tại thời điểm biên dịch. Nếu hệ điều hành và phần cứng máy tính có thể giao dịch một cách hiệu quả với các chương trình của người dùng và dữ liệu trong các module thì một số thuận lợi có thể thấy rõ sau đây:  Các module có thể được viết và biên dịch độc lập, với tất cả các tham chiếu từ một module này đến module khác được giải quyết bởi hệ thống tại thời điểm chạy.  Các mức độ khác nhau của sự bảo vệ, read-only, execute-only, có thể cho ra các module khác nhau.  Nó có thể đưa ra các cơ chế để các module có thể được chia sẻ giữa các tiến trình. Kỹ thuật đáp ứng cho yêu cầu này là sự phân đoạn (segmentation), đây là một trong những kỹ thuật quản lý bộ nhớ được trình bày trong chương này. Quản lý bộ nhớ vật lý: làm cách nào để mở rộng bộ nhớ có sẵn nhằm lưu trữ được nhiều tiến trình đồng thời? Tổ chức bộ nhớ vật lý (Physical organization): Như chúng ta đã biết bộ nhớ máy tính được tổ chức theo hai cấp: bộ nhớ chính và bộ nhớ phụ. Bộ nhớ chính cung cấp một tốc độ truy cập dữ liệu cao, nhưng dữ liệu trên nó phải được làm tươi thường xuyên và không thể tồn tại lâu dài trên nó. Bộ nhớ phụ có tốc độ truy xuất chậm và rẻ tiền hơn so với bộ nhớ chính nhưng nó không cần làm tươi thường xuyên. Vì thế bộ nhớ phụ có khả năng lưu trữ lớn và cho phép lưu trữ dữ liệu và chương trình trong một khoảng thời gian dài, trong khi đó bộ nhớ chính chỉ để giữ (hold) một khối lượng nhỏ các chương trình và dữ liệu đang được sử dụng tại thời 163

điểm hiện tại. Trong giản đồ hai cấp này, việc tổ chức luồng thông tin giữa bộ nhớ chính và bộ nhớ phụ là một nhiệm vụ quan trọng của hệ thống. Sự chịu trách nhiệm cho luồng này có thể được gán cho từng người lập trình riêng, nhưng điều này là không hợp lý và có thể gây rắc rối, là do hai nguyên nhân:  Không gian bộ nhớ chính dành cho các chương trình cùng với dữ liệu của nó thường là không đủ, trong trường hợp này, người lập trình phải tiến hành một thao tác phủ lắp (Overlaying), theo đó chương trình và dữ liệu được tổ chức thành các module khác nhau có thể được gán trong cùng một vùng của bộ nhớ, trong đó có một chương trình chính chịu trách nhiệm chuyển các module vào và ra khi cần.  Trong môi trường đa chương trình, người lập trình không thể biết tại một thời điểm xác định có bao nhiêu không gian nhớ còn trống hoặc khi nào thì không gian nhớ sẽ trống. Như vậy nhiệm vụ di chuyển thông tin giữa hai cấp bộ nhớ phải do hệ thống thực hiện. Đây cũng là nhiệm vụ cơ bản của thành phần quản lý bộ nhớ. Các giải pháp quản lý bộ nhớ phụ thuộc rất nhiều vào đặc tính phần cứng và trải qua nhiều giai đoạn cải tiến để trở thành những giảp pháp khá thỏa đáng như hiện nay. 3.3. KIẾN THỨC NỀN 3.3.1. Một chương trình qua nhiều bước xử lý Thông thường, một chương trình được lưu trữ trên đĩa (đĩa từ) 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 vào bộ nhớ chính, tạo lập tiến trình tương ứng để xử lý. Trong quá trình thực thi, tiến trình có thể được di chuyển giữa đĩa và bộ nhớ. 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 gọi là hàng đợi nhập (input queue). Các địa chỉ trong chương trình nguồn là địa chỉ danh biểu 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. Thủ tục thông thường là chọn một trong những quá trình trong hàng đợi nhập và nạp quá trình đó vào bộ nhớ. Khi một quá trình được thực thi, nó truy xuất các chỉ thị và dữ liệu từ bộ nhớ. Cuối cùng, một quá trình kết thúc và không gian bộ nhớ của nó được giải phóng. 164

Hình 3.1. Xử lý nhiều bước của chương trình người dùng16 Hầu hết các hệ thống cho phép một quá trình người dùng nằm ở bất cứ phần nào của bộ nhớ vật lý. Do đó, mặc dù không gian địa chỉ của máy tính bắt đầu tại 00000, nhưng địa chỉ đầu tiên của quá trình người dùng không cần tại 00000. Sắp xếp này ảnh hưởng đến địa chỉ mà chương trình người dùng có thể dùng. Trong hầu hết các trường hợp, một chương trình người dùng sẽ đi qua một số bước-một vài trong chúng có thể là tuỳ chọn-trước khi được thực thi (hình 3.1). Các địa chỉ có thể được hiện diện trong 16 Nguyễn Phú Trường, Giáo trình hệ điều hành, ĐH Cần Thơ, 2005, Tr.138 165

những cách khác trong những bước này. Các địa chỉ trong chương trình nguồn thường là những danh biểu. Một trình biên dịch sẽ gắn kết các địa chỉ danh biểu tới các địa chỉ có thể tái định vị (chẳng hạn như 14 Bytes từ vị trí bắt đầu của module này). Bộ soạn thảo liên kết hay bộ nạp sẽ liên kết các địa chỉ có thể tái định vị tới địa chỉ tuyệt đối (chẳng hạn 74014). Mỗi liên kết là một ánh xạ từ một không gian địa chỉ này tới một không gian địa chỉ khác. Có thể thực hiện gắn kết các chỉ thị và dữ liệu tới các địa chỉ bộ nhớ có thể được thực hiện tại bất cứ bước nào theo cách sau đây:  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. 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 gắn kết địa chỉ phải trì hoãn đến tận thời điểm xử lý. Để thực hiện gắn kết địa chỉ vào thời điểm xử lý, cần sử dụng cơ chế phần cứng đặc biệt. 3.3.2. Không gian địa chỉ luận lý và không gian địa chỉ 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ớ hiệu quả:  Địa chỉ logic : còn gọi là luận lý hay đị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ế của bộ nhớ chính mà trình quản lý bộ nhớ nhìn thấy và thao tác. 166

 Không gian địa chỉ luận lý: 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 gắn kết địa chỉ tại thời điểm biên dịch cũng như 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 gắn kết tại thời điểm thực thi. 3.3.3. Bộ quản lý bộ nhớ (MMU) 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ý tại thời điểm thực thi. Chương trình của người 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. 3.3.4. Phủ lắp (Overlay) Để cho phép một quá trình có kích thước lớn hơn không gian bộ nhớ được cấp phát cho nó, người lập trình sử dụng cơ chế phủ lắp. Ý tưởng phủ lắp là giữ trong bộ nhớ những chỉ thị và dữ liệu được yêu cầu tại bất kỳ thời điểm nào được cho. Khi những chỉ thị đó được yêu cầu, chúng được nạp vào không gian được chiếm trước đó bởi các chỉ thị mà chúng không còn cần nữa. Ví dụ, xét trình dịch hợp ngữ hai lần (two-pass assembler). Trong suốt lần thứ 1, nó xây dựng bảng danh biểu; sau đó, trong lần thứ 2, nó tạo ra mã máy. Chúng ta có thể phân chia trình dịch hợp ngữ thành mã lần 1, mã lần 2, bảng danh biểu, và những thủ tục hỗ trợ chung được dùng bởi lần 1 và lần 2. Giả sử kích thước của các thành phần này như sau: Lần 1: 70 KB Lần 2: 80 KB Bảng danh biểu: 20 KB Các thủ tục chung: 30 KB Để nạp mọi thứ một lần, chúng ta cần 200KB bộ nhớ. Nếu bộ nhớ chỉ còn trống 150KB, đáng lẻ chúng ta không thể chạy quá trình này. Tuy nhiên, chú ý rằng lần 1 và 167

lần 2 không cần ở trong bộ nhớ cùng một lúc. Do đó, chúng ta định nghĩa hai phủ lắp. Phủ lắp A là bảng danh biểu, các thủ tục chung, lần 1, và phủ lắp B là bảng danh biểu, các thủ tục chung, lần 2. Chúng ta bổ sung trình điều khiển phủ lắp (10 KB) và bắt đầu với phủ lắp A trong bộ nhớ. Khi chúng ta kết thúc lần 1, chúng ta nhảy tới trình điều khiển phủ lắp, trình điều khiển này sẽ đọc phủ lắp B vào trong bộ nhớ, viết chồng lên phủ lắp A và sau đó chuyển điều khiển tới lần 2. Phủ lắp A chỉ cần 120KB, ngược lại phủ lắp B cần 130KB (Hình 3.2). Bây giờ chúng ta có thể chạy trình hợp ngữ trong 150KB bộ nhớ. Nó sẽ nạp nhanh hơn vì rất ít dữ liệu cần được chuyển trước khi việc thực thi bắt đầu. Tuy nhiên, nó sẽ chạy chậm hơn do nhập/xuất phụ đọc mã cho phủ lắp A qua mã cho phủ lắp B. Hình 3.2. Các phủ lắp cho một bộ hợp ngữ dịch hai lần Mã cho phủ lắp A và mã cho phủ lắp B được giữ trên đĩa như những hình ảnh bộ nhớ tuyệt đối, và được đọc bởi trình điều khiển phủ lắp khi cần. Tái định vị đặc biệt và các giải thuật liên kết được yêu cầu để xây dựng các phủ lắp. 3.3.5. Hoán vị Một quá trình cần ở trong bộ nhớ để được thực thi. Tuy nhiên, một quá trình có thể được hoán vị (swapped) tạm thời khỏi bộ nhớ tới vùng lưu trữ phụ (backing store). Sau đó mang trở lại bộ nhớ để việc thực thi được tiếp tục. Ví dụ, một môi trường đa 168

chương với giải thuật điều phối RR (Round Robin). Khi định mức thời gian hết hạn, bộ quản lý bộ nhớ sẽ bắt đầu hoán vị ra (swap out) vùng lưu trữ phụ quá trình vừa bị hết hạn và hoán vị vào (swap in) một quá trình khác tới không gian bộ nhớ được trống (Hình 3.3). Hình 3.3. Hoán vị hai quá trình sử dụng đĩa như là backing store Hoán vị yêu cầu một vùng lưu trữ phụ (backing store). Vùng lưu trữ phụ này thường là một đĩa tốc độ cao. Nó phải đủ lớn để chứa các bản sao của tất cả hình ảnh bộ nhớ cho tất cả người dùng, và nó phải cung cấp truy xuất trực tiếp tới các hình ảnh bộ nhớ này. Hệ thống này duy trì một hàng đợi sẵn sàng chứa tất cả quá trình mà các hình ảnh bộ nhớ của nó ở trong vùng lưu trữ phụ hay trong bộ nhớ và sẵn sàng để thực thi. Bất cứ khi nào bộ định thời CPU quyết định thực thi một quá trình, nó gọi bộ phân phát (dispatcher). Bộ phân phát kiểm tra để thấy quá trình tiếp theo trong hàng đợi ở trong bộ nhớ không. Nếu không, và không có vùng bộ nhớ trống, bộ phân phát hoán vị ra một quá trình hiện hành trong bộ nhớ và hoán vị vào một quá trình mong muốn. Sau đó, nó nạp lại các thanh ghi và chuyển điều khiển tới quá trình được chọn. Trong các hệ hoán vị, thời gian chuyển đổi giữa các công việc cần được quan tâm. Mỗi quá trình cần được phân chia một khoảng thời gian sử dụng CPU đủ lớn để không thấy rõ sự chậm trễ do các thao tác hoán vị gây ra. Nếu không, hệ thống sẽ dùng phần lớn thời gian để hoán vị các quá trình vào ra bộ nhớ chính, CPU như vậy sẽ không sử dụng hiệu quả. 169

3.4. QUẢN LÝ BỘ NHỚ CHÍNH 3.4.1. Bộ nhớ cấp phát liên tục 3.4.1.1. Kỹ thuật phân vùng cố định Trong kỹ thuật này không gian địa chỉ của bộ nhớ chính được chia thành 2 phần cố định, phần nằm ở vùng địa chỉ thấp dùng để chứa chính hệ điều hành, phần còn lại, tạm gọi là phần user program, là sẵn sàng cho việc sử dụng của các tiến trình khi các tiến trình được nạp vào bộ nhớ chính. Hình 3.4. Hệ thống đơn chương với phân vùng cố định Trong các hệ thống đơn chương, phần user program được dùng để cấp cho chỉ một chương trình duy nhất, do đó nhiệm vụ quản lý bộ nhớ của hệ điều hành trong trường hợp này sẽ đơn giản hơn, hệ điều hành chỉ kiểm soát sự truy xuất bộ nhớ của chương trình người dùng, không cho nó truy xuất lên vùng nhớ của hệ điều hành. Để thực hiện việc này hệ điều hành sử dụng một thanh ghi giới hạn để ghi địa chỉ ranh giới giữa hệ điều hành và chương trình của người dùng, theo đó khi chương trình người dùng cần truy xuất một địa chỉ nào đó thì hệ điều hành sẽ so sánh địa chỉ này với giá trị địa chỉ được ghi trong thành ghi giới hạn, nếu nhỏ hơn thì từ chối không cho truy xuất, ngược lại thì cho phép truy xuất. Việc so sánh địa chỉ này cần phải có sự hỗ trợ của phần cứng và có thể làm giảm tốc độ truy xuất bộ nhớ của hệ thống nhưng bảo vệ được hệ điều hành tránh việc chương trình của người dùng làm hỏng hệ điều hành dẫn đến làm hỏng hệ thống. Trong các hệ thống đa chương, chương trình người dùng lại lại được phân ra thành nhiều phân vùng (partition) có kích thước bằng hoặc khác nhau. Việc phân phân chia bộ nhớ thành những phần cố định được thực hiện bởi một bộ thao tác lúc khở động máy. Trong trường hợp này một tiến trình có thể được nạp vào bất kỳ phân vùng 170

nào nếu kích thước của nó nhỏ hơn hoặc bằng kích thước của phân vùng và phân vùng này còn trống. Hình 3.5. Hệ thống đa chương với phân vùng có kích thước cố định Khi có một tiến trình cần được nạp vào bộ nhớ nhưng tất cả các phân vùng đều đã chứa các tiến trình khác thì hệ điều hành có thể chuyển một tiến trình nào đó, mà hệ điều hành cho là hợp lệ (kích thước vừa đủ, không đang ở trạng thái ready hoặc running, không có quan hệ với các tiến trình running khác, ...), ra ngoài (swap out), để lấy phân vùng trống đó nạp tiến trình vừa có yêu cầu. Đây là nhiệm vụ phức tạp của hệ điều hành, hệ điều hành phải tốn chi phí cao cho công việc này. Có hai trở ngại trong việc sử dụng các phân vùng cố định với kích thước bằng nhau:  Thứ nhất, khi kích thước của một chương trình là quá lớn so với kích thước của một phân vùng thì người lập trình phải thiết kế chương trình theo cấu trúc phủ lắp, theo đó chỉ những phần chia cần thiết của chương trình mới được nạp vào bộ nhớ chính khi khởi tạo chương trình, sau đó người lập trình phải nạp tiếp các module cần thiết khác vào đúng phân vùng của chương trình và sẽ ghi đè lên bất kỳ chương trình hoặc dữ liệu ở trong đó. Cấu trúc chương trình phủ lắp tiết kiệm được bộ nhớ nhưng yêu cầu trình độ ở người lập trình.  Thứ hai, khi kích thước của một chương trình quá nhỏ so với kích thước của một phân vùng nhưng không phải là bội số của kích thước một phân vùng thì dễ xảy ra hiện tượng phân mảnh bên trong (internal fragmentation) bộ nhớ, gây lãng phí bộ nhớ. Ví dụ, nếu có 2 không gian trống kích thước bằng nhau 20K nằm rãi rác trên bộ nhớ, quá trình A đến yêu cầu 11K, B đến yêu cầu 23K, thì cũng sẽ không nạp 171

được quá trình B cùng lúc với quá trình A, hiện tượng này được gọi là hiện tượng phân mảnh bên trong. Phân mảnh trong là phần không gian bộ nhớ đã cấp thừa cho quá trình A nhưng không thể lấy lại để cấp cho quá trình B tại thời điểm đó. Cả hai vấn đề trên có thể được khắc phục bằng cách sử dụng các phân vùng có kích thước không bằng nhau. Việc đưa một tiến trình vào phân vùng trong hệ thống đa chương với phân vùng cố định kích thước không bằng nhau sẽ phức tạp hơn nhiều so với trường hợp các phân vùng có kích thước bằng nhau. Với các phân vùng có kích thước không bằng nhau thì có hai cách để cài đặt khi đưa một tiến trình vào phân vùng:  Mỗi phân vùng có một hàng đợi tương ứng, theo đó mỗi tiến trình khi cần được nạp vào bộ nhớ nó sẽ được đưa đến hàng đợi của phân vùng có kích thước vừa đủ để chứa nó. Mỗi khi phân vùng trống, tiến trình đợi sẽ được đưa vào phân vùng đó để thực thi. Tuy nhiên cách tiếp cận này kém linh động vì có thể có một phân vùng đang trống với hàng đợi rỗng, trong khi đó có phân vùng khác đang bận với hàng đợi đầy, điều này gây lãng phí trong việc sử dụng bộ nhớ. Hơn nữa, tạo ra sự phân mãnh bên trong của các phân vùng: vì kích thước của các phân vùng là cố định nên cấp phát thừa cho quá trình gây lãng phí bộ nhớ. Cách khắc phục là nên chọn một hàng đợi chung. Hình 3.6. Mỗi Phân vùng có hàng đợi tương ứng 172

 Hệ thống dùng một hàng đợi chung cho tất cả các phân vùng, theo đó tất cả các tiến trình muốn được nạp vào phân vùng nhưng chưa được vào sẽ được đưa vào hàng đợi chung này. Sau đó nếu có một phân vùng trống thì hệ thống sẽ xem xét để đưa một tiến trình có kích thước vừa đủ vào phân vùng trống đó. Cách tiếp cận này linh động hơn so với việc sử dụng nhiều hàng đợi như ở trên, nhưng việc chọn một tiến trình trong hàng đợi để đưa vào phân vùng là một việc làm khá phức tạp của hệ điều hành vì nó phải dựa vào nhiều yếu tố khác nhau như: độ ưu tiên của tiến trình, trạng thái hiện tại của tiến trình, các mối quan hệ của tiến trình,... Hình 3.7. Một hàng đợi chung cho tất cả phân vùng 3.4.1.2. Kỹ thuật phân vùng động (Dynamic Partitioning) Kỹ thuật phân vùng động khắc phục được một vài hạn chế của kỹ thuật phân vùng cố định. Kỹ thuật này thường được sử dụng phổ biến trong hệ điều hành mainframe của IBM, hệ điều hành OS/MVT, ... Trong kỹ thuật phân vùng động, số lượng các phân vùng trên bộ nhớ và kích thước của mỗi phân vùng là có thể thay đổi. Tức là phần user program trên bộ nhớ không được phân chia trước. Ban đầu khi chưa có quá trình nào trong bộ nhớ phần chương trình người dùng chỉ có một phân vùng mà kích thước của nó sẽ thay đổi mỗi khi có một tiến trình được nạp vào bộ nhớ chính. Khi có một tiến trình được nạp vào bộ nhớ, hệ điều hành cấp cho nó không gian vừa đủ để chứa tiến trình, phần còn lại để sẵn sàng cấp cho tiến trình khác sau này. Khi một tiến trình kết thúc, không gian bộ nhớ tương ứng được giải phóng sẽ được hệ điều hành cấp cho tiến trình khác có có yêu cầu kích thước nhỏ hơn. 173

Hình 3.8. Kỹ thuật phân vùng động trong hệ thống đa chương 3.4.1.2.1. Các vấn đề kỹ thuật phân vùng động trong hệ thống đa chương Kỹ thuật phân vùng động trong hệ thống đa chương có ưu điểm là sử dụng bộ nhớ có hiệu quả, tránh được sự phân mãnh bên trong. Tuy nhiên, phức tạp trong các giải thuật cấp phát và thu hồi bộ nhớ, cũng như khó theo dõi các phần không gian trống. Bên cạnh đó, kỹ thuật này để lại bộ nhớ có nhiều không gian trống có kích thước nhỏ nằm rải rác, mỗi không gian không đủ để cấp phát cho quá trình đến. Hiện tượng này được gọi là hiện thượng phân mảnh bên ngoài (external fragmentation). Để chống lại sự lãng phí bộ nhớ do phân mảnh ngoài, thỉnh thoảng hệ điều hành phải thực hiện việc sắp xếp lại bộ nhớ còn gọi là phương pháp cô đặc bộ nhớ (Memory compaction), bằng cách di chuyển các tiến trình về một phía và các không gian trống về một phía khác tạo thành một khối nhớ có kích thước đủ lớn để chứa được một tiến trình mới. Công việc này làm chậm tốc độ của hệ thống, hệ điều hành phải tốn chi phí cao cho việc này, đặc biệt là việc tái định vị các tiến trình khi một tiến trình bị đưa ra khỏi bộ nhớ và được nạp vào lại bộ nhớ để tiếp tục hoạt động. Hình 3.9. Phân mãnh ngoài 174

Trong trường hợp quá trình có đoạn dữ liệu/stack phát triển trong khi thực thi, làm sao mở rộng không gian bộ nhớ đã cấp phát cho quá trình? Có hai cách giải quyết vấn đề này: Hình 3.10. Mở rộng không gian cho quá trình  Nếu, có sẵn một không gian trống liền kề với quá trình thì không gian đó sẽ được cấp phát cho quá trình phát triển. Ngược lại, quá trình sẽ phải di dời đến một không gian trống lớn hơn đủ cho quá trình phát triển, hoặc một hay nhiều quá trình khác sẽ phải hoán vị ra đĩa để tạo ra một không gian trống đủ lớn cho quá trình phát triển.  Nếu không có không gian trống đủ lớn và vùng đĩa hoán vị cũng đầy thì quá trình sẽ phải chờ đợi hoặc chấm dứt. 3.4.1.2.2. Phương pháp quản lý bộ nhớ với kỹ thuật phân vùng động trong hệ thống đa chương Trong kỹ thuật phân vùng động này hệ điều hành phải đưa ra các cơ chế thích hợp để quản lý các khối nhớ đã cấp phát hay còn trống trên bộ nhớ. Hệ điều hành sử dụng hai cơ chế: Bản đồ bit và danh sách liên kết. Trong cả hai cơ chế này hệ điều hành đều chia không gian nhớ thành các đơn vị cấp phát có kích thước bằng nhau, các đơn vị cấp phát liên tiếp nhau tạo thành một khối nhớ (block), hệ điều hành cấp phát các block này cho các tiến trình khi nạp tiến trình vào bộ nhớ. 3.4.1.2.2.1. Quản lý bằng bản đồ bit 175

Bộ nhớ được chia thành các đơn vị cấp phát, kích thước từ vài Words đến vài Kbytes. Mỗi đơn vị được ánh xạ tới một bit trong bản đồ bit (Hình 3.11). Giá trị bit này xác định trạng thái của đơn vị bộ nhớ đó: bit 0 đang tự do, bit 1 đã được cấp phát cho tiến trình. Khi cần nạp một quá trình có kích thước k đơn vị, hệ thống sẽ tìm trong bản đồ bit một dãy k bit có giá trị 0. a) Hiện trạng bộ nhớ có 4 quá trình A, B, C, D đã được cấp phát và 5 khối tự do b) Bản đồ bit tương ứng Hình 3.11. Quản lý bộ nhớ bằng bản đồ bit Kích thước của đơn vị cấp phát là vấn đề lớn trong thiết kế. Nếu kích thước đơn vị cấp phát nhỏ sẽ làm tăng kích thước của bản đồ bit. Ngược lại, nếu kích thước đơn vị cấp phát lớn có thể gây hao phí cho đơn vị cấp phát sau cùng. Đây là giải pháp đơn giản nhưng thực hiện chậm nên ít được dùng. 3.4.1.2.2.2. Quản lý bằng danh sách liên kết Một danh sách liên kết để quản lý các khối (Block) bộ nhớ đã cấp phát và các khối tự do. Mỗi khối tương ứng một phần tử trong danh sách liên kết. Phần tử có thể là một quá trình hay một vùng nhớ trống giữa hai quá trình. Mỗi phần tử gồm 1 bit đầu để xác định khối đó là lỗ trống (H) hay một quá trình (P), sau đó là 3 từ (word) để chỉ địa chỉ bắt đầu, chiều dài và con trỏ chỉ tới phần tử kế tiếp. Việc sắp xếp các khối theo địa chỉ hay theo kích thước tuỳ thuộc vào giải thuật quản lý bộ nhớ. Sơ đồ quản lý bằng danh sách liên kết tương ứng với sơ đồ quản lý bằng bản đồ bit được minh họa trong Hình 3.12. 176

a)Hiện trạng bộ nhớ gồm 4 quá trình và 5 khối trống H0 2 P 23 H 53 P8 2 H 10 4 P 14 3 H 17 1 P 18 2 H 20 2 b) Quản lý bộ nhớ bằng danh sách liên kết Hình 3.12. Quản lý bộ nhớ bằng danh sách liên kết Các chiến lược first-fit, best-fit, worst-fit và next-fit là những chiến lược phổ biến nhất được dùng để chọn một khối trống thích hợp từ tập hợp các khối trống trong bộ nhớ để cấp phát cho quá trình. Việc lựa chọn này sao cho dẫn đến việc sử dụng bộ nhớ chính là hiệu quả nhất.  First-fit: trong trường hợp này hệ điều hành sẽ bắt đầu quét qua các khối nhớ trống bắt đầu từ khối nhớ trống đầu tiên trong bộ nhớ, và sẽ chọn khối nhớ trống đầu tiên có kích thước đủ lớn để nạp tiến trình.  Best-fit: chọn khối nhớ trống có kích thước nhỏ nhất đủ lớn để cấp phát cho tiến trình. Hệ điều hành sẽ quét toàn bộ danh sách khối trống. Ngoại trừ danh sách khối trống được xếp theo thứ tự kích thước tăng dần.  Worst-fit: chọn khối nhớ trống có kích thước lớn nhất để cấp phát cho tiến trình. Hệ điều hành sẽ quét toàn bộ danh sách khối trống. Ngoại trừ danh sách khối trống được xếp theo thứ tự kích thước giảm dần.  Next-fit: tương tự như First-fit nhưng ở đây hệ điều hành bắt đầu quét từ khối nhớ trống kế sau khối nhớ vừa được cấp phát trước đó và chọn khối nhớ trống kế tiếp đầu tiên đủ lớn để nạp tiến trình. Khi một tiến trình kết thúc, một khối trống được tạo ra có thể kết hợp với các khối trống kế bên của nó (nếu có) để tạo ra khối trống lớn hơn. Một khối có hai láng giềng, trừ khối đầu tiên và cuối cùng chỉ có một láng giềng. 177

Ví dụ: Hiện trạng bộ nhớ có sẵn tập hợp các khối trống có kích thước lần lượt 8k, 12k, 22k, 18k, 8k, 6k, 14k, 36k. Giả sử tiến trình đến yêu cầu 16k cần được nạp vào bộ nhớ, thì hệ điều hành sẽ nạp nó vào:  Khối nhớ 22k nếu theo thuật toán First-fit, lãng phí 6k do phân mãnh trong và tốc độ cấp phát nhanh nhất.  Khối nhớ 18k nếu theo thuật toán Best-fit, lãng phí 2k do phân mãnh trong, phải dò tìm toàn bộ danh sách và tốc độ chậm nhất.  Khối nhớ 36k nếu theo giải thuật worst-fit, phải dò tìm toàn bộ danh sách nên tốc độ chấp phát chậm, phương án này được xem là hiệu quả vì để lại khối nhớ trống 20k không thể gọi là phân mãnh nhưng nếu cứ tiếp tục như thế sẽ gây ra phân mãnh lớn ở cuối bộ nhớ. Các hệ điều hành thường không cài đặt cố định trước một thuật toán nào, tuỳ vào trường hợp cụ thể mà nó chọn cấp phát theo một thuật toán nào đó, sao cho chi phí về việc cấp phát là thấp nhất và hạn chế được sự phân mảnh bộ nhớ sau này. Việc chọn thuật toán nào thường phụ thuộc vào thứ tự swap và kích thước của tiến trình. Thuật toán First-fit được đánh giá là đơn giản, dễ cài đặt và mang lại hiệu quả cao nhất đặc biệt là về tốc độ cấp phát. Về hiệu quả thuật toán Next-fit không bằng First-fit, nhưng nó thường xuyên sử dụng được các khối nhớ trống ở cuối vùng nhớ, các khối nhớ ở vùng này thường có kích thước lớn nên có thể hạn chế được sự phân mảnh. Thuật toán Best-fit, không như tên gọi của nó, đây là một thuật toán có hiệu suất thấp nhất, trong trường hợp này hệ điều hành phải duyệt qua tất các các khối nhớ trống để tìm ra một khối nhớ có kích thước vừa đủ lớn để chứa tiến trình yêu cầu, điều này làm giảm tốc độ cấp phát của hệ điều hành. Mặt khác với việc chọn kích thước vừa đủ lớn có thể dẫn đến sự phân mảnh lớn trên bộ nhớ, tức là có quá nhiều khối nhớ có kích thước quá nhỏ trên bộ nhớ, nhưng nếu xét về mặt lãng phí bộ nhớ tại thời điểm cấp phát thì thuật toán này làm lãng phí ít nhất. Tóm lại, khó có thể đánh giá về hiệu quả sử dụng của các thuật toán này, vì hiệu quả của nó được xét trong “tương lai” và trên nhiều khía cạnh khác nhau chứ không phải chỉ xét tại thời điểm cấp phát. Và hơn nữa trong bản thân các thuật toán này đã có các mâu thuẫn với nhau về hiệu quả sử dụng của nó. Như vậy khi cần nạp một tiến trình vào bộ nhớ thì hệ điều hành phải dựa vào bản đồ bit hoặc danh sách liên kết để tìm ra một khối thích hợp để nạp tiến trình. Sau khi thực hiện một thao tác cấp phát hoặc sau khi đưa một tiến trình ra khỏi bộ nhớ thì hệ 178

điều hành phải cập nhật lại bản đồ bit hoặc danh sách liên kết, điều này có thể làm giảm tốc độ thực hiện của hệ thống. Danh sách liên kết có thể được sắp xếp theo thứ tự tăng dần hoặc giảm dần của kích thước hoặc địa chỉ, điều này giúp cho việc tìm khối nhớ trống có kích thước vừa đủ để nạp các tiến trình theo các thuật toán dưới đây sẽ đạt tốc độ nhanh hơn và hiệu quả cao hơn. Một số hệ điều hành tổ chức 2 danh sách liên kết riêng để theo dõi các đơn vị cấp phát trên bộ nhớ, một danh sách để theo dõi các block đã cấp phát và một danh dách để theo dõi các block còn trống. Cách này giúp việc tìm các khối nhớ trống nhanh hơn, chỉ tìm trên danh sách các khối nhớ trống, nhưng tốn thời gian nhiều hơn cho việc cập nhật danh sách sau mỗi thao tác cấp phát, vì phải thực hiện trên cả hai danh sách. 3.4.1.2.2.3. Quản lý bằng hệ thống bạn thân (Buddy System) Việc quản lý danh sách các không gian trống được sắp xếp theo kích thước làm cho cấp phát bộ nhớ rất nhanh, nhưng lại làm chậm cho việc thu hồi bộ nhớ bởi vì ta phải chú ý đến các láng giềng. Hệ thống bạn thân (Buddy System) là một giải thuật quản lý bộ nhớ tận dụng thuận lợi của việc máy tính dùng những số nhị phân cho việc đánh địa chỉ để tăng tốc độ kết hợp những không gian trống sát nhau khi một quá trình kết thúc. Với phương pháp này, bộ quản lý bộ nhớ sẽ có một bảng liệt kê những khối còn tự do có kích thước 1, 2, 4, 16...Bytes, tức là có kích thước bằng 2n. Khi có một quá trình cần cấp phát bộ nhớ, một không gian trống có kích thước bằng 2n nhỏ nhất đủ lớn sẽ được cấp phát cho quá trình. Nếu không gian trống quá lớn sẽ được phân đôi cho đến khi có được không gian trống cần thiết. Khi một quá trình chấm dứt, các khối trống kế nhau có kích thước bằng nhau sẽ được nhập lại để tạo thành khối trống lớn hơn. Do đó, giải thuật này được gọi là hệ thống bạn thân. Ví dụ: với bộ nhớ 1M, cần phải có 21 bảng liệt kê sắp xếp từ 1 Byte (20) đến 20Bytes (220). Khởi đầu toàn bộ nhớ còn tự do và bảng liệt kê chỉ có một mục từ chứa một khối trống kích thước 1M, tất cả các bảng liệt kê khác đều rỗng. 179

Quá trình đến 1M = 1024 KBytes 1 lỗ trống yêu cầu A yêu cầu 70K A 128 256 512 3 B yêu cầu 35K A B 64 256 512 3 C yêu cầu 80K A B 64 C 128 512 3 A kết thúc 128 B 64 C 128 512 4 D yêu cầu 60K 128 B D C 128 512 3 B kết thúc 128 64 D C 128 512 4 D kết thúc 256 C 128 512 3 C kết thúc 1024 1 Bảng 3.1. Quản lý bộ nhớ bằng hệ thống bạn thân Hệ thống bạn thân có sự thuận lợi so với những giải thuật cùng sắp xếp theo kích thước của khối. Sự thuận lợi này là khi có một khối 2k Bytes tự do, bộ quản lý bộ nhớ chỉ cần tìm trong bảng liệt kê khối trống có kích thước 2k để xem chúng có khả năng kết hợp được hay không. Với những giải thuật khác mà trong đó cho phép các khối bộ nhớ được phân chia một cách tùy ý, việc tìm kiếm phải diễn ra trên tất cả các bảng liệt kê. Do dó, hệ thống bạn thân làm việc nhanh hơn. Đáng tiếc, nó lại cực kỳ kém hiệu quả trong việc sử dụng bộ nhớ. Một quá trình 35K phải được cấp phát đến 64K, hao phí đến 29K. Sự hao phí này được gọi là sự phân mảnh trong (internal fragmentation), bởi vì phần bộ nhớ hao phí nằm bên trong đoạn được cấp phát. 3.4.1.3. Tái định vị bộ nhớ và bảo vệ bộ nhớ Khi bộ nhớ trở nên khan hiếm, một tiến trình đang ở trên bộ nhớ có thể bị đưa ra ngoài (swap out) để dành chỗ nạp một tiến trình mới có yêu cầu, và tiến trình này sẽ được nạp vào lại (swap in) bộ nhớ tại một thời điểm thích hợp sau này. Vấn đề đáng quan tâm ở đây là tiến trình có thể được nạp vào lại phân vùng khác với phân vùng mà 180

nó được nạp vào lần đầu tiên. Có một lý do khác khiến các tiến trình phải thay đổi vị trí nạp so với ban đầu là khi có sự liên kết giữa các module tiến trình của một chương trình thì các tiến trình phải dịch chuyển ngay cả khi chúng đã nằm trên bộ nhớ chính. Sự thay đổi vị trị/địa chỉ nạp này sẽ ảnh hưởng đến các thao tác truy xuất dữ liệu của chương trình vì nó sẽ khác với các địa chỉ tương đối mà người lập trình đã sử dụng trong mã lệnh của chương trình. Ngoài ra khi một tiến trình được nạp vào bộ nhớ lần đầu tiên thì tất cả các địa chỉ tương đối được tham chiếu trong mã lệnh chương trình được thay thế bằng địa chỉ tuyệt đối trong bộ nhớ chính. Ví dụ trong chương trình có mã lệnh truy xuất đến địa chỉ tương đối 100k, nếu chương trình này được nạp vào phân vùng 1 có địa chỉ bắt đầu là 100k thì địa chỉ truy xuất là 200k, nhưng nếu chương trình được nạp vào phân vùng 2 có địa chỉ bắt đầu là 200k, thì địa chỉ truy xuất sẽ là 300k. Để giải quyết vấn đề này hệ điều hành phải thực hiện các yêu cầu cần thiết của công tác tái định vị một tiến trình vào lại bộ nhớ. Ngoài ra ở đây hệ điều hành cũng phải tính đến việc bảo vệ các tiến trình trên bộ nhớ tránh tình trạng một tiến trình truy xuất đến vùng nhớ của tiến trình khác. Giải pháp chung cho vấn đề tái định vị và bảo vệ bộ nhớ là hệ điều hành sử dụng hai thanh ghi đặc biệt:  Thanh ghi nền (base): lưu địa chỉ bắt đầu của phân vùng chứa tiến trình  Thanh ghi giới hạn (limit): lưu chiều dài của phân vùng chứa tiến trình Hình 3.13. Phần cứng hỗ trợ tái định vị và bảo vệ 181

Khi một tiến trình được nạp vào bộ nhớ thì hệ điều hành sẽ ghi địa chỉ bắt đầu của phân vùng được cấp phát cho tiến trình vào thanh ghi nền và địa chỉ cuối cùng của tiến trình vào thanh ghi giới hạn. Việc thiết lập giá trị của các thanh ghi này được thực hiện cả khi tiến trình lần đầu tiên được nạp vào bộ nhớ và khi tiến trình được swap in vào lại bộ nhớ. Theo đó mỗi khi tiến trình thực hiện một thao tác truy xuất bộ nhớ thì hệ thống phải thực hiện hai bước: Thứ nhất, cộng địa chỉ logic với giá trị địa chỉ trong thanh ghi nền để có được địa chỉ tuyệt đối của ô nhớ cần truy xuất sẽ giải quyết được vấn đề tái định vị. Thứ hai, địa chỉ kết quả ở trên sẽ được so sánh với giá trị địa chỉ trong thành ghi giới hạn để giải quyết vấn đề bảo vệ. Nếu địa chỉ nằm trong phạm vi giới hạn thì hệ điều hành cho phép tiến trình truy xuất bộ nhớ, ngược lại thì có một ngắt về lỗi truy xuất bộ nhớ được phát sinh và hệ điều hành sẽ cấm tiến trình truy xuất vào địa chỉ này. Giải pháp này có nhiều thuận lợi là dễ dàng di dời tiến trình trong bộ nhớ – vì chỉ cần thay đổi giá trị của hai thanh ghi nền và giới hạn. Trong hệ thống đa chương sử dụng sự phân vùng động, nếu có một tiến trình mới cần được nạp vào bộ nhớ, trong khi bộ nhớ không còn chỗ trống và tất cả các tiến trình phải đợi trên bộ nhớ ở trạng thái khoá (blocked) nhưng vẫn chiếm dụng bộ nhớ. Việc đợi này cho đến khi có một tiến trình kết thúc, bị đưa ra khỏi bộ nhớ chính tạo điều kiện cho hệ thống nạp tiến trình vừa có yêu cầu. Sự chờ đợi này làm lãng phí thời gian xử lý của CPU. Để tiết kiệm thời gian xử lý của CPU trong trường hợp này hệ điều hành chọn ngay một tiến trình đang ở trạng thái khoá để đưa ra ngoài (cơ chế suspend) lấy không gian nhớ trống đó cấp cho tiến trình vừa có yêu cầu mà không phải đợi như ở trên. Hệ điều hành sử dụng nhiều thuật toán khác nhau cho việc chọn một tiến trình để thay thế trong trường hợp này, tất cả các thuật toán này đều hướng tới mục đích: tiết kiệm thời gian xử lý của CPU, tốc độ thay thế cao, sử dụng bộ nhớ hiệu quả nhất và đặc biệt là không để dẫn đến sự trì trệ hệ thống. Chúng ta sẽ thảo luận rõ hơn về vấn đề này ở phần kế tiếp của chương này. Một nhược điểm lớn của các kỹ thuật ở trên là dẫn đến hiện tượng phân mảnh trong và phân mảnh ngoài gây lãng phí bộ nhớ nên hiệu quả sử dụng bộ nhớ kém. Để khắc phục hệ điều hành sử dụng các kỹ thuật phân trang hoặc phân đoạn bộ nhớ. 3.4.2. Cấp phát không liên tục 3.4.2.1. Phân trang (Paging) 182

Bộ nhớ vật lý được chia 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ỉ luận lý 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 3.14. Mô hình bộ nhớ phân trang 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). Mỗi tiến trình được nạp vào bộ nhớ sẽ sở hữu một số khung trang nhất định. Nếu kích thước của tiến trình không phải là bội số của kích thước một khung trang thì sẽ xảy ra hiện tượng phân mảnh nội ở khung trang chứa trang cuối cùng của tiến trình. Ở đây không xảy ra hiện tượng phân mảnh ngoài. Trên bộ nhớ có thể tồn tại các trang của nhiều tiến trình khác nhau. Khi một tiến trình bị swap out thì các khung trang mà tiến trình này chiếm giữ sẽ được giải phóng để hệ điều hành có thể nạp các trang của tiến trình khác. Trong kỹ thuật này hệ điều hành phải đưa ra các cơ chế thích hợp để theo dõi trạng thái của các khung trang (còn trống hay đã cấp phát) trên bộ nhớ và các khung trang đang chứa các trang của các tiến trình khác nhau trên bộ nhớ. Hệ điều hành sử dụng một danh sách để ghi số hiệu của các khung trang còn trống trên bộ nhớ, hệ điều hành dựa vào danh sách này để tìm các khung trang trống trước khi quyết định nạp một 183

tiến trình vào bộ nhớ, danh sách này được cập nhật ngay sau khi hệ điều hành nạp một tiến trình vào bộ nhớ, được kết thúc hoặc bị swap out ra bên ngoài. Hệ điều hành sử dụng các bảng trang (PCT: page control table) để theo dõi vị trí các trang tiến trình trên bộ nhớ, mỗi tiến trình có một bảng trang riêng. Bảng trang bao gồm nhiều phần tử, thường là bằng số lượng trang của một tiến trình mà bảng trang này theo dõi, các phần tử được đánh số bắt đầu từ 0. Phần tử 0 chứa số hiệu của khung trang đang chứa trang 0 của tiến trình, phần tử 1 chứa số hiệu của khung trang đang chứa trang 1 của tiến trình, … (a) Các trang của các (b) ánh xạ vào các khung trang trong bộ nhớ tiến trình trên bộ nhớ vật lý và cập nhật bảng trang, cập nhật danh luận lý sách khung trống Hình 3.15. Ánh xạ các trang vào các khung trang 3.4.2.1.1. Cơ chế quản lý bộ nhớ 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ý (tức số hiệu khung trang trong bộ nhớ vật lý đang chứa trang). 184

3.4.2.1.2. Chuyển đổi địa chỉ luận lý sang địa chỉ vật lý Mỗi tiến trình có một không gian địa chỉ riêng. Không gian này gọi là không gian địa chỉ luận lý, gồm tập hợp các địa chỉ luận lý (địa chỉ ảo) do CPU sinh ra tại thời điểm biên dịch. Mỗi địa chỉ luận lý được phát sinh bởi CPU được chia thành hai phần: P: d  P (Page): số hiệu trang, số thứ tự trang cần truy xuất  d (offset) : địa chỉ tương đối trong trang hay độ dời trong trang được xác định từ địa chỉ bắt đầu của trang đến vị trí ô nhớ cần tìm trong trang. Số hiệu trang (p) sẽ được tra trong bảng trang để xác định số thứ tự khung trang (f). f kết hợp với độ dời (d) sẽ xác định được địa chỉ vật lý. Nói cách khác, địa chỉ vật lý có dạng f:d. Địa chỉ này cũng được tính bằng số thứ tự khung trang nhân với kích thước trang và cộng thêm độ dời. Hình 3.16. Chuyển đổi địa chỉ luận lý sang địa chỉ vật lý Nếu kích thước của không gian địa chỉ luận lý 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 (P), và n bits thấp cho biết địa chỉ tương đối trong trang (d). 185

Ví dụ: Nếu một địa chỉ logic gồm 16 bit, kích thước của mỗi trang là 1K = 1024Byte (210), thì có 6 bit dành cho số hiệu trang, như vậy một chương trình có thể có tối đa 26 = 64 trang mỗi trang 1KB. Một quá trình A yêu cầu 3500Bytes sẽ cấp phát tương ứng 4 trang. Trong trường hợp này nếu CPU phát ra một giá trị địa chỉ 16 bit là: 0000010111011110 = 1502, thì thành phần số hiệu trang là 000001 = 1, thành phần offset là 0111011110 = 478. Free list 5 6 25 7 19 …. Hình 3.17. xác định địa chỉ vật lý 186

3.4.2.1.3. Cài đặt bảng trang Trong trường hợp đơn giản nhất, một tập hợ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 trữ địa chỉ bắt đầu nơi lưu trữ bảng trang, thanh ghi này được gọi là thanh ghi PTBR(page table base register). 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 3.18. 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 (Translation Look-aside Buffers). 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. 187

Hình 3.19. Phần cứng hỗ trợ phân trang với TLBs 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. 3.4.2.1.4. Tổ chức bảng trang 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: 188

Hình 3.20. Bảng trang hai cấp Hình 3.21. Sơ đồ dịch địa chỉ bảng trang hai cấp 189

 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 <idp, p, d > 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 <idp, p >. Khi một tham khảo đến bộ nhớ được phát sinh, một phần địa chỉ ảo là <idp, p > đượ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ý <i,d> 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ệ. Hình 3.22. Bảng trang đảo 190

3.4.2.1.5. 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ệ - không hợp lệ.  Hợp lệ (valid) : trang tương ứng thuộc về không gian địa chỉ của tiến trình.  Không hợp lệ (invalid): 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 tiến trình đã truy xuất đến một địa chỉ không được phép. Hình 3.23. Cơ chế bảo vệ trang 3.4.2.1.6. Chia sẻ bộ nhớ trong cơ chế phân trang 191

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 mã lệnh 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 mã lệnh 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 mã lệnh chung này. Lưu ý để có thể chia sẻ một đoạn mã lệnh, đoạn mã lệnh 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 công việc). Hình 3.24. Cơ chế chia sẻ trang17  Nhận xét:  Kỹ thuật phân trang loại bỏ được hiện tượng phân mảnh ngoài. Tuy nhiên hiện tượng phân mảnh trong vẫn có thể xảy ra khi kích thước của tiến trình 17 Nguyễn Phú Trường, Giáo trình hệ điều hành, ĐH Cần Thơ, 2005, Tr.165 192

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.  Khi cần truy xuất đến dữ liệu hay chỉ thị trên bộ nhớ thì hệ thống phải cần một lần truy xuất đến bảng trang, điều này có thể làm giảm tốc độ truy xuất bộ nhớ. Để khắc phục hệ điều hành sử dụng thêm một bảng trang cache, để lưu trữ các trang bộ nhớ vừa được truy cập gần đây nhất. Bảng trang cache này sẽ được sử dụng mỗi khi CPU phát ra một địa chỉ cần truy xuất.  Mỗi hệ điều hành có một cơ chế tổ chức bảng trang riêng, đa số các hệ điều hành đều tạo cho mỗi tiến trình một bảng trang riêng khi nó được nạp vào bộ nhớ chính. Bảng trang lớn sẽ tốn bộ nhớ để chứa nó.  Để bảo vệ các khung trang hệ điều hành đưa thêm một bit bảo vệ vào bảng trang. Theo đó mỗi khi tham khảo vào bảng trang để truy xuất bộ nhớ hệ thống sẽ 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ó hay không.  Một khía 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 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 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 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 đó . Sự phân trang không phản ánh đúng cách thức người dùng cảm nhận về bộ nhớ. Người 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à tìm một cách thức biểu diễn bộ nhớ sao cho nó gần với cách 193

nhìn nhận của người dùng hơn. Kỹ thuật phân đoạn bộ nhớ có thể thực hiện được mục tiêu này. 3.4.2.2. Phân đoạn (Segmentation) Trong kỹ thuật này không gian địa chỉ bộ nhớ vật lý được chia thành các phần cố định có kích thước không bằng nhau, được đánh số bắt đầu từ 0, được gọi là các phân đoạn (segment). Mỗi phân đoạn bao gồm số hiệu phân đoạn và kích thước của nó. Mỗi tiến trình có một không gian địa chỉ riêng gọi là không gian địa chỉ luận lý gồm tập hợp các địa chỉ luận lý (địa chỉ ảo) do CPU sinh ra tại thời điểm biên dịch. Không gian địa chỉ của các tiến trình kể cả các dữ liệu liên quan cũng được chia thành các đoạn khác nhau và không nhất thiết phải có kích thước bằng nhau, thông thường mỗi thành phần của một chương trình/tiến trình như: code, data, stack, subprogram, ..., là các đoạn riêng và chúng có liên hệ logic với nhau. Hình 3.25. Tầm nhìn người dùng về chương trình Khi một tiến trình được nạp vào bộ nhớ thì tất cả các đoạn của nó sẽ được nạp vào các phân đoạn còn trống khác nhau trên bộ nhớ vật lý. Các phân đoạn này có thể không liên tiếp nhau (hình 3.26). 194

Hình 3.26. Mô hình bộ nhớ phân đoạn 3.4.2.2.1. Cơ chế quản lý bộ nhớ trong kỹ thuật phân đoạn Để theo dõi các đoạn của các tiến trình khác nhau trên bộ nhớ, hệ điều hành sử dụng các bảng phân đoạn (SCT: Segment control Table) tiến trình, thông thường một tiến trình có một bảng phân đoạn riêng. Mỗi phần tử trong bảng phân đoạn gồm tối thiểu 2 trường: trường thứ nhất cho biết địa chỉ nền (địa chỉ cơ sở -base) của phân đoạn mà đoạn chương trình tương ứng được nạp, trường thứ hai cho biết độ dài/giới hạn (length/limit) của phân đoạn, trường này còn có tác dụng dùng để kiểm soát sự truy xuất bất hợp lệ của các tiến trình. 3.4.2.2.2. Chuyển đổi địa chỉ luận lý sang địa chỉ vật lý Mỗi địa chỉ ảo là một bộ <s,d>  s (segment): số hiệu phân đoạn cho biết số hiệu đoạn tương ứng cần truy xuất.  d (offset): độ dời 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 có một địa chỉ logic gồm n + m bit, thì n bit trái nhất là số hiệu phân đoạn, m bit phải nhất còn lại là độ dời. Trong ví dụ minh hoạ sau đây thì n = 4 và m = 12, như 195

vậy kích thước tối đa của một đoạn là 212 = 4096 Byte. Sau đây là các bước cần thiết của việc chuyển đổi địa chỉ:  Trích ra n bit trái nhất của địa chỉ logic để xác định số hiệu của phân đoạn cần truy xuất.  Sử dụng số hiệu phân đoạn ở trên để tham chiếu đến phần tử trong bảng phân đoạn của tiến trình, để tìm địa chỉ vật lý bắt đầu của phân đoạn.  So sánh thành phần offset của địa chỉ logic, được trích ra từ m bit phải nhất của địa chỉ logic, với thành phần length của phân đoạn. Nếu offset > length thì địa chỉ truy xuất là không hợp lệ.  Địa chỉ vật lý mong muốn là địa chỉ vật lý bắt đầu của phân đoạn cộng với giá trị offset. Ví dụ 1: Ta có địa chỉ logic là: 0001001011110000, Với n=4, m=12. Vậy số hiệu segment là 1, offset là 752, giả định segment này thường trú trong bộ nhớ chính tại địa chỉ vật lý là 0010000000100000, thì địa chỉ vật lý tương ứng với địa chỉ logic ở trên là: 0010001100010000 Địa chỉ bắt đầu của đoạn 1 là 0010000000100000 Độ dời 752 = 001011110000 Địa chỉ vật lý = 0010000000100000 + 001011110000 = 0010001100010000 Hình 3.27. Cơ chế phần cứng hỗ trợ kĩ thuật phân đoạn 196

Ví dụ 2: Địa chỉ logic có dạng 2,300. Địa chỉ vật lý là 4300 + 300 = 4600. Địa chỉ này hợp lệ vì d=300 nhỏ hơn chiều dài giới hạn của đoạn 2 là limit = 400. Hình 3.28. Hệ thống phân đoạn 3.4.2.2.3. Cài đặt bảng phân đoạn Các bảng phân đoạn có thể được chứa trong các thanh ghi nếu có kích thước nhỏ, nếu kích thước bảng phân đoạn lớn thì nó được chứa trong bộ nhớ chính, khi đó hệ điều hành sẽ dùng một thanh ghi để lưu trữ địa chỉ bắt đầu nơi lưu trữ bảng phân đoạn, thanh ghi này được gọi là thanh ghi STBR: Segment table base register. Ngoài ra vì số lượng các đoạn của một chương trình/tiến trình có thể thay đổi nên hệ điều hành dùng thêm thanh ghi STLR:Segment table length register, để ghi kích thước hiện tại của bảng phân đoạn. Hệ điều hành cũng tổ chức một danh sách riêng để theo dõi các segment còn trống trên bộ nhớ. 197

Với một địa chỉ logic <s,d>, 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ỉ 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 3.29. Sử dụng STBR, STLR và bảng phân đoạn 3.4.2.2.4. 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 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. 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. 3.4.2.2.5. Chia sẻ 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 (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 198

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. Hình 3.30. Chia sẻ segment 0  Nhận xét  Tương tự như trong kỹ thuật phân vùng động, kỹ thuật này cũng 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. Ở đây hệ điều hành thường dùng thuật toán best-fit hay first-fit.  Vì các đoạn có kích thước không bằng nhau nên sự phân đoạn tương tự như sự phân vùng động. Sự khác nhau là với sự phân đoạn một chương trình có thể chiếm giữ hơn một phân vùng, và các phân vùng này có thể không liền kề với nhau. Sự phân vùng loại trừ được sự phân mảnh nội vi, nhưng như sự phân vùng động nó vẫn xuất hiện hiện tượng phân mảnh ngoại vi.  Sự phân trang là không tường minh đối với người lập trình, trong khi đó sự phân đoạn là tường minh đối với người lập trình, và nó cung cấp một sự thuận lợi để người lập trình tổ chức chương trình và dữ liệu. Người lập trình 199