Hệ điều hành - Quản lý bộ nhớ

Quản lý bộ nhớOperating systems*PTIT, 2012Bối cảnhBộ nhớ của máy thì hữu hạn nhưng nhu cầu của chương trình thì vô hạn.Hệ thống thực hiện nhiều tiến trình cùng lúc, cần làm sao cho tiến trình này không ảnh hưởng đến tiến trình kia.Operating systems*PTIT, 2012Liên kết địa chỉKhi viết chương trình, lập trình viên chỉ quan tâm đến địa chỉ tượng trưng (tên biến, tên hàm, ). Khi thực thi, các địa chỉ này phải được ánh xạ thành địa chỉ thật. Có thể thực hiện việc ánh xạ tại các thời điểm: Lúc biên dịch chương trình Lúc nạp chương trình vào bộ nhớ Lúc thực thi chương trìnhOperating systems*PTIT, 2012Địa chỉ vật lý và địa chỉ luận lýĐịa chỉ luận lý (hay địa chỉ ảo) là địa chỉ mà CPU “nhìn thấy”. => Không gian địa chỉ ảo là tập hợp tất cả các địa chỉ mà CPU “nhìn thấy”.Địa chỉ vật lý là địa chỉ thật mà đơn vị quản lý bộ nhớ quản lý. => Không gian địa chỉ vật lý là khoảng địa chỉ mà đơn vị quản lý bộ nhớ “nhìn thấy”.Operating systems*PTIT, 2012Địa chỉ luận lý và địa chỉ vật lýBộ nhớ vật lýĐơn vị quản lý bộ nhớ Không gian luận lýKhông gian vật lýOperating systems*PTIT, 2012Đơn vị quản lý bộ nhớ (MMU)MMU (Memory Management Unit) là khối phần cứng thực hiện việc chuyển đổi giữa địa chỉ luận và địa chỉ vật lý.Có chức năng tách rời không gian vật lý với không gian luận lý.Chương trình chỉ nhìn thấy không gian luận lý.Operating systems*PTIT, 2012Đơn vị quản lý bộ nhớ (MMU)MMU được tích hợp bên trong CPUKhối CPUĐịa chỉ luận lýOperating systems*PTIT, 2012Cấp phát độngChỉ liên kết (link) chương trình khi chương trình được thực thi.Chỉ nạp chương trình con vào bộ nhớ khi nó chính thức được gọi.Cơ chế hóan đổi (swap): tạm thời chuyển phần tiến trình chưa sử dụng ra bộ nhớ ngòai (đĩa cứng), khi nào cần sẽ nạp vào lại.Operating systems*PTIT, 2012SwapOperating systems*PTIT, 2012Các cơ chế cấp phát bộ nhớCấp phát liên tục (contigous allocation)Cấp phát không liên tục: Phân đọan (segmentation) Phân trang (paging)Operating systems*PTIT, 2012Cấp phát liên tụcMô hình 1 (linker-loader): quản lý địa chỉ bắt đầu và kích thước tiến trìnhOperating systems*PTIT, 2012Cấp phát liên tụcMô hình 2 (base&limit) quản lý địa chỉ bắt đầu và địa chỉ kết thúc.Operating systems*PTIT, 2012Bảo vệ bộ nhớ trong cơ chế base&limitOperating systems*PTIT, 2012Hiện tượng phân mảnh bộ nhớCác tiến trình có kích thước khác nhau. Sau khi thực thi xong và ra khỏi bộ nhớ sẽ tạo ra các vùng trống không đều nằm rải rác trong bộ nhớ => phân mảnh.Operating systems*PTIT, 2012Hiện tượng phân mảnh bộ nhớPhân mảnh trong (internal fragmentation): Tiến trình được đưa vào vùng trống lớn hơn kích thước tiến trình => có một phần dư không dùng.Phân mảnh ngòai (external fragmentation): tổng cộng vùng nhớ trống còn nhiều nhưng không liên tục nên không cấp phát được.Operating systems*PTIT, 2012Các chiến lược cấp phát độngFirst-fit: Chọn vùng nhớ trống đầu tiên tìm thấy đủ rộng để chứa tiến trình.Best-fit: Chọn vùng nhớ trống nhỏ nhất đủ sức chứa tiến trình.Worst-fit: Chọn vùng nhớ trống lớn nhất để chứa tiến trình. Chiến lược nào tốt nhất???Operating systems*PTIT, 2012Phân đọanĐối với người sử dụng, một chương trình được chia thành nhiều phần khác nhau:Operating systems*PTIT, 2012Phân đọanMỗi phần được đưa vào một vùng nhớ riêng, có kích thước khác nhau và liên hệ luận lý với nhau gọi là một đọan (segment)13241423Operating systems*PTIT, 2012Phân đọanMỗi đọan bộ nhớ trong không gian địa chỉ luận lý được nhận diện bằng địa chỉ bắt đầu của đọan (base) và kích thước của đọan đó (limit).Cấu trúc địa chỉ luận lý có dạng trong đó s là số hiệu phân đọan, d là địa chỉ tương đối trong phân đọan.Operating systems*PTIT, 2012Chuyển đổi địa chỉ trong cơ chế phân đọanOperating systems*PTIT, 2012Một hệ thống phân đọanOperating systems*PTIT, 2012Dùng chung các phân đọanOperating systems*PTIT, 2012Phân trang (paging)Không gian bộ nhớ vật lý được chia thành các đọan có kích thước bằng nhau gọi là khung (frame)Không gian địa chỉ ảo cũng được chia thành nhiều đọan có kích thước bằng nhau và bằng với khung trang, gọi là các trang địa chỉ (page)Operating systems*PTIT, 2012Trang và khungOperating systems*PTIT, 2012Địa chỉ luận lý trong chế độ phân trangĐịa chỉ luận lý có dạng P: số hiệu trangD: địa chỉ tương đối trong trangOperating systems*PTIT, 2012Chuyển đổi địa chỉ ảo thành địa chỉ vật lýOperating systems*PTIT, 2012Truy xuất bộ nhớ với cơ chế phân trangLiên kết giữa trang và khung được chứa trong bảng trang (page table)Mỗi thao tác truy xuất bộ nhớ gồm 2 công đọan: Đọc bảng trang để tìm khung => tạo ra địa chỉ vật lý Đọc dữ liệu từ địa chỉ vật lýOperating systems*PTIT, 2012Tăng tốc độ truy xuất bộ nhớ trong cơ chế phân trangSử dụng bộ nhớ kết hợp TLB (Translation look aside buffer)Operating systems*PTIT, 2012Bảng trang nhiều cấpp1p2dCấu trúc địa chỉ trong bảng trang hai cấpOperating systems*PTIT, 2012Bài tập 1Giả sử bộ nhớ chính được phân thành các đọan có kích thước là 600K, 500K, 200K, 300K ( theo thứ tự ). Hãy cho biết các tiến trình có kích thước 212K, 417K, 112K và 426K ( theo thứ tự ) sẽ được cấp phát bộ nhớ như thế nào, nếu sử dụng : a) Chiến lược First fitb) Chiến lược Best fitc) Chiến lược Worst fitOperating systems*PTIT, 2012Bài tập 2Tại sao kích thước trang luôn là lũy thừa của 2?Xét một không gian địa chỉ có 8 trang, mỗi trang có kích thước 1K. Ánh xạ vào bộ nhớ vật lý có 32 khung. a) Địa chỉ luận lý gồm bao nhiêu bit ?b) Địa chỉ vật lý gồm bao nhiêu bit ?Operating systems*PTIT, 2012Bài tập 3Xét một hệ thống sử dụng kỹ thuật phân trang, với bảng trang được lưu trữ trong bộ nhớ chính. a) Nếu thời gian cho một lần truy xuất bộ nhớ bình thường là 200 ns, thì mất bao nhiêu thời gian cho một thao tác truy xuất bộ nhớ trong hệ thống này ?b) Nếu sử dụng TLBs với hit-ratio ( tỉ lệ tìm thấy) là 75%, thời gian để tìm trong TLBs xem như bằng 0, tính thời gian truy xuất bộ nhớ trong hệ thống ( effective memory reference time)Operating systems*PTIT, 2012Bài tập 40,430 1,10 2,500 3,400 4,112 Cho bảng phân đọan như hình dưới. Xác định địa chỉ vật lý ứng với các địa chỉ sau đây: