Giáo trình Hệ điều hành (Dành cho sinh viên ngành Công nghệ thông tin) - Đặng Thanh Hải

h ghi giới hạn. 
- Khi tiến trình được tạo lập, nạp vào thanh ghi nền địa chỉ bắt đầu của phân 
vùng được cấp phát cho tiến trìnhvà nạp vào thanh ghi giới hạn kích thước 
của tiến trình 
- Sau đó mỗi đị chỉ bộ nhớ được phát sinh sẽ tự động được cộng với địa chỉ 
chứa trong thanh ghi nền để cho ra địa chỉ tuyệt đối trong bộ nhớ và các địa 
chỉ được đối chiếu với thanh ghi giới hạn để bảo đảm tiến trình không truy 
xuất ngoài phạm vi được cấp phát cho nó. 
VII.4 Quản lý bộ nhớ với những phân đọan động 
 Như tổ chức quản lý bộ nhớ trên gây ra lãng phí bộ nhớ vì vậy một phương pháp 
mới được đề xuất là cấp pháp cho tiến trình vùng nhớ vừa đủ kích thước của tiến 
trình. 
 Khi một tiến trình kết thúc vùng nhớ đã đã cấp cho nó sẽ được giải phóng và được 
cấp pháp cho tiến trình khác. 
 Với giải pháp này không còn hiện tượng phân mảnh nội vi nhưng lại xuất hiện 
phân mảng ngoại vi. Khi các tiến trình lần lượt vào ra khỏi hệ thống, dần dần xuất 
Khoa Công Nghệ Thông Tin Hệ Điều Hành 
 Trang 67 
hiện các khe hở giữa các tiến trình có thể dẫn đến tình huống tổng vùng nhớ còn 
trống đủ để thỏa mãn yêu cầu nhưng các vùng nhớ này không liên tục. 
- Có thể áp dụng kỹ thuật dồn bộ nhớ để kết hợp các mảnh bộ nhớ rời rạc 
thành một vùng nhớ lớn liên tục. 
- Một vấn đề khác nảy sinh khi kích thước của tiến trình tăng trưởng trong 
quá trình xử lý mà không còn vùng nhớ còn trống gần kề để mở rộng vùng 
nhớ cho tiến trình. 
 Quản lý các ô nhớ còn trống: Cần phải lưu trữ thông tin các ô nhớ còn trống để cấp 
phát cho các tiến trình, Có hai phương pháp chính: Bitmap và danh sách liên kết. 
 Phương pháp Bitmap: 
 Chia bộ nhớ thành từng đơn vị nhỏ (vài bytes) . Xây dựng bitmap, ứng với mỗi bit 
trong bitmap là một đơn vị bộ nhớ. 
- Bit được đánh dấu là 1 khi đơn vị bộ nhớ tương ứng đã được cấp phát 
- Bit được đánh dấu 0 khi đơn vị bộ nhớ tương ứng chưa được cấp phát. 
 Thao tác cấp phát bộ nhớ là : Giả sử tiến trình cần k đơn vị bộ nhớ, HĐH duyệt 
bitmap và tìm ra k bit liên tiếp bằng 0 
Hình 7.3 
 Quản vùng nhớ còn trống bằng danh sách liên kết 
 Tổ chức một danh sách liên kết, mỗi phần tử tương ứng với một tiến trình hay lỗ 
hổng. Mỗi phần tử trong danh sách có 4 trường : 
- Cờ biểu thị tiến trình (P) hay lỗ hổng (H) 
- Địa chỉ bắt đầu của vùng nhớ tương ứng 
- Kích thước của vùng nhớ 
- Con trỏ Next 
Hình 7.4 
Khoa Công Nghệ Thông Tin Hệ Điều Hành 
 Trang 68 
 Thao tác cấp phát bộ nhớ 
- First Fit : Xác định lỗ hổng đầu tiên trong danh sách có kích thước đủ lớn để 
cấp phát cho tiến trình và lỗ hổng này được chia làm 2 phần : 1 phần cho 
tiến trình và phần kia là lỗ hổng mới. 
- Best Fit : xác định lỗ hổng bé nhất có kích thước đủ lớn để cấp phát cho tiến 
trình. 
- Worst Fit : Cấp phát phân đoạn tự do lớn nhất đủ lớn để cấp phát cho riến 
trình. 
Có thể làm tăng tốc độ bằng cách cho cả 3 thuật toán trên bằng cách tổ chức 2 danh 
sách: 1 cho tiến trình và một cho lỗ hổng. Tuy nhiên lại làm chậm thao tác giải phóng bộ 
nhớ. 
 Thao tác giải phóng bộ nhớ 
- Khi thực hiện thao tác giải phóng chú ý cần xem xét các trường hợp khác 
nhau của 2 phần tử kề nhau. Nhờ đó thực hiện thao tác kết hợp hai lỗ hổng 
kề nhau một cách phù hợp: 
Hình 7.5 
 Quá trình Swapping 
 Trong hệ thống đa nhiệm nhiều người dùng thường là bộ nhớ không đủ chỗ để lưu 
trữ tất cả các tiến trình vì thế hệ thống dùng DSLK để lưu trữ tạm thời một số tiến trình 
nào đó chưa thật sự chạy, khi được cấp phát CPU thì hệ thống phải mang nó vào bộ nhớ 
chính . Việc di chuyển tiến trình từ bộ nhớ vào đĩa và ngược lại gọi là quá trình swapping. 
 Bộ nhớ ảo 
Bộ nhớ ảo được đưa ra nhằm khắc phục tình trạng kích thước chương trình vượt 
quá kích thước bộ nhớ vật lý. Hệ điều hành chia chương trình thành nhiều phần và giữa 
lại những phần chương trình đang chạy hiện thời vừa đủ chứa trong bộ nhớ , phần còn lại 
lưu trữ trên đĩa. HĐH theo dõi và quản lý tất cả công việc swapping giữa đĩa và bộ nhớ . 
Dĩ nhiên bộ nhớ ảo vẫn có thể thiết kế cho hệ thống đa nhiệm. 
 Sự phân trang (paging) 
Hầu hết những hệ thống có sử dụng bộ nhớ ảo đều sử dụng kỹ thuật phân trang. 
Địa chỉ ảo là địa chỉ tham khảo từ chương trình . Tập tất cả địa chỉ ảo gọi là vùng địa chỉ 
ảo, đối với những hệ thống không dùng bộ nhớ ảo , địa chỉ ảo cũng là địa chỉ vật lý. 
Khoa Công Nghệ Thông Tin Hệ Điều Hành 
 Trang 69 
Vùng địa chỉ ảo được chi thành nhiều trang (page) có kích thước bằng nhau tướng 
ứng với những khung trang (Page frame) trong bộ nhớ vật lý. Trang và khung trang luôn 
có kích thước bằng nhau. 
Ví dụ: có 32K bộ nhớ vật lý chia thành 8 khung trang có kích thước 4K và 64K bộ 
nhớ ảo chia thành 16 trang kích thước 4K. Trong bất kỳ thời điểm nào chỉ có 8 trang từ bộ 
nhớ ảo ánh xạ vào bộ nhớ vật lý như sau: 
Hình 7.6 
 Nếu lệnh nào đó trong chương trình tham khảo đến địa chỉ ảo không thuộc về bất 
kỳ trang nào đang được ánh xạ hiện thời gọi là lỗi trang. Trong trường hợp này 
HĐH tìm ra một khung trang nào ít sử dụng nhất trục xuất khỏi bộ nhớ và tìm 
kiếm trên đĩa trang nào chứa địa chỉ mà chương trình muốn tham khảo đến để 
chuyển vào bộ nhớ vật lý. Tiếp đến hệ thống cập nhật ánh xạ bộ nhớ cho trang 
mới. 
 Bảng trang 
Hệ thống phải duy trì một bảng trang thể hiện ánh xạ từ bộ nhớ ảo vào bộ nhớ vật 
lý và chứa thông tin trang nào hiện thời đang được ánh xạ. 
Khoa Công Nghệ Thông Tin Hệ Điều Hành 
 Trang 70 
Hình 7.7 
VII.5 Các thuật toán thay thế trang 
 Mỗi khi gặp lỗi trang HĐH phải chọn 1 trong các trang nào đó trục xuất ra khỏi bộ 
nhớ. Nếu nội dung trang đó bị thay đổi thì phải ghi nội dung mới của trang lên đĩa. Vấn 
đề là chọn trang nào để trục xuất để giảm tổn phí. 
Xét ví dụ một tiến trình truy xuất đến một dãy các trang sau: 
7, 0,1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 
giả sử có 3 khung trang và ban đầu cả 3 khung trang đều rỗng. 
VII.5.1 Thuật toán FIFO 
 Ghi nhận thời điểm 1 trang được mang vào bộ nhớ chính khi cần thay thế trang , 
thì trang lâu nhất sẽ được chọn để trục xuất. 
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 
7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7 
 0 0 0 0 3 3 3 2 2 2 2 1 1 1 1 1 1 0 0 
 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1 
* * * * * * * * * * * * * * * 
Hình 7.8 
 Với thuật toán này có thể có trang được chọn để thay thế có thể chứa nhiều dữ liệu 
cần thiết thường xuyên được nạp vào sớm , do vậy khi bị chuyển ra bộ nhớ phụ sẽ 
nhanh chóng gây ra lỗi trang. 
Khoa Công Nghệ Thông Tin Hệ Điều Hành 
 Trang 71 
VII.5.2 Thuật toán tối ưu 
 Thay thế trang sẽ lâu nhất được sử dụng trong tương lai 
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 
7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 
 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 
 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 
* * * * * * * * * 
Hình 7.9 
 Thuật toán này bảo đảm lỗi trang là ít nhất tuy nhiên thuật toán này không khả thi 
vì không thể biết trước dãy các trang được truy xuất theo thứ tự. 
VII.5.3 Thuật toán lâu nhất chưa sử dụng (LRU) 
 Với mỗi trang ghi nhận thời điểm cuối cùng trang được truy cập, trang được 
thay thế là trang lâu nhất chưa sử dụng. 
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 
7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1 
 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 
 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7 
* * * * * * * * * * * 
Hình 7.10 
 Thuật toán đòi hỏi một cơ chế xác định thứ tự các trang theo thời điểm truy xuất 
cuối cùng. Dùng stack 
- Cần tổ chức một stack lưu trữ số hiệu các trang 
- Mỗi khi thực hiện một truy xuất đến 1 trang , số hiệu của trang sẽ được xóa 
khỏi vị trí hiện hành trong stack và đưa lên đỉnh stack. 
- Trang ở đỉnh stack là trang được chọn để thay thế. 
VII.5.4 Thuật toán Not Recently Used (NRU) 
 Thuật toán dựa trên sự tồn tại 2 bit gắn liền với mỗi trang để chỉ ra trang đó có vừa 
mới được tham khảo hay là được ghi lên hay không. Những bit này chứa trong 
bảng trang 
Khoa Công Nghệ Thông Tin Hệ Điều Hành 
 Trang 72 
 Bit R =1: nếu trang đó truy cập ngược lại chưa được truy cập 
 Bit M =1 : Trang đó đã bị thay đổi ngược lại chưa bị thay đổi 
- Cứ mỗi lần truy cập bộ nhớ cần phải cập nhật lại các bit này 
- Khi một tiến trình bắt đầu cả 2 bit trong tất cả các trang được đặt bằng 0. theo 
một chu kỳ thời gian bit R được đặt lại bằng 0 để phân biệt những trang mới 
được truy cập với trang đã truy cập trước đó. 
- Khi xuất hiện một lỗi trang HĐH duyệt toàn bộ bảng trang và chia chúng thành 
4 lớp dựa vào các bit R, M như sau: 
Class 0 : R=0, M=0 
 Class 1: R=0, M=1 
 Class 2: R=1, M=0 
 Class 3: R=1, M=1 
Sau đó thuật toán chọn ra một trang để thay thế thuộc thuộc lớp thấp nhất khác 
rỗng. 
CÂU HỎI VÀ BÀI TẬP 
1. Trình bày hiện tượng phân mảnh nội vi và ngoại vi trong quá trình tổ chức quản lý 
bộ nhớ phân đoạn cố định và động ? 
2. Trình bày thuật toán cấp phát bộ nhớ (thuật toán first Fit, Best Fit, Worst Fit ) 
trong kỹ thuật quản lý bộ nhớ động bằng danh sách liên kết và kỹ thuật bitmap? 
3. Trình bày thuật toán giải phóng bộ nhớ trong kỹ thuật quản lý bộ nhớ động bằng 
danh sách liên kết ? 
4. Trình bày phương pháp chuyển đổi địa chỉ ảo sang địa chỉ vật lý trong phương 
pháp quản lý bộ nhớ ảo? Kích thước trang và khung trang, nội dung bảng trang 
như mục VII.4 ? 
5. Trong một thống cài đặt bộ nhớ ảo theo kỹ thuật phân trang, giả sử một chương 
trình truy cập đến các trang sau: 1, 0,4, 2, 1, 3, 1, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 3, 0, 1. 
Giả sử hệ thống có 3 khung trang lúc đầu còn trống. Có bao nhiêu lỗi trang xảy ra 
khi hệ thống sử dụng thuật toán thay thế trang LRU, FIFO ? 
---HẾT--- 
Khoa Công Nghệ Thông Tin Hệ Điều Hành 
 Trang 73 
TÀI LIỆU THAM KHẢO 
[1] Giáo trình hệ điều hành 1, Lê Khắc Nhiên Ân, Hoàng Kiếm 
[2] Giáo trình hệ điều hành 2, Lê Khắc Nhiên Ân, Hoàng Kiếm 
[3] Hỗ trợ kỹ thuật lập trình hệ thống, Nguyễn Tín 
[4] Virus tin học huyền thoại và thực tế, Ngô Anh Vũ 
[5] Operating Systems, Andrew S.Tanenbaum 
[6] Operating System Concepts, Abraham Siberschatz, Peter B. Galvin