Bài giảng chương 7: Bộ nhớ chính main memory

CHƯƠNG 7: BỘ NHỚ CHÍNH Main Memory 8.2 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 NỘI DUNG „ Background „ Swapping „ Cấp phát bộ nhớ kề (Contiguous Memory Allocation) „ Phân trang (Paging) „ Cấu trúc của bảng trang (Structure of the Page Table) „ Phân đoạn (Segmentation) „ Ví dụ: Intel Pentium 8.3 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 MỤC TIÊU „ Cung cấp mô tả chi tiết các phương pháp tổ chức phần cứng bộ nhớ. „ Thảo luận các kỹ thuật quản trị bộ nhớ bao gồm phân trang, phân đoạn. 8.4 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Background „ Chương trình phải được mang (từ đĩa) vào trong bộ nhớ và được sắp xếp bên trong một quá trình để chạy „ Chỉ có bộ nhớ chính và các thanh ghi là các lưu trữ mà CPU có thể truy xuất trực tiếp. „ Truy xuất thanh ghi mất một xung đồng hồ (hoặc ít hơn). „ Truy xuất bộ nhớ chính có thể mất nhiều xung đồng hồ „ Cache ở giữa bộ nhớ chính và các thanh ghi CPU. „ Bộ nhớ đòi hỏi phải được bảo vệ để đảm bảo hoạt động đúng. 8.5 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 THANH GHI CƠ SỞ VÀ THANH GHI GIỚI HẠN Base and Limit Registers „ Một cặp thanh ghi cơ sở và thanh ghi giới hạn xác định không gian địa chỉ logic 8.6 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 SỰ GẮN KẾT CÁC CHỈ THỊ & DỮ LIỆU VỚI BỘ NHỚ „ Gắn kết địa chỉ chỉ thị và dữ liệu với địa chỉ bộ nhớ xảy ra trong ba giai đoạn khác nhau z Thời gian biên dịch (compile time): nếu vị trí bộ nhớ được biết trước, mã tuyệt đối (absolute code) có thể được sinh ra; phải biên dịch lại nếu vị trí khởi đầu thay đổi. z Thời gian nạp (Load time): phải sinh ra mã có thể định vị lại (relocatable code) nếu vị trí bộ nhớ không được biết trước khi biên dịch z Thời gian thực hiện (Execution time): sự gắn kết bị làm trễ đến tận khi thời gian chạy nếu quá trình có thể được di chuyển trong khi thực hiện từ một đoạn bộ nhớ sang một đoạn khác. Cần hỗ trợ phần cứng cho các ánh xạ địa chỉ (các thanh ghi cơ sở và giới hạn) 8.7 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 XỬ LÝ NHIỀU BƯỚC CỦA MỘT CHƯƠNG TRÌNH NGƯỜI DÙNG 8.8 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 KHÔNG GIAN ĐỊA CHỈ LOGIC vs. KHÔNG GIAN ĐỊA CHỈ VẬT LÝ „ Quan niệm của một không gian địa chỉ logic gắn kết với một không gian địa chỉ vật lý tách biệt là tâm đối với quản trị bộ nhớ z Địa chỉ logic (Logical address) – được sinh ra bởi CPU; cũng được tham khảo như địa chỉ ảo. z Địa chỉ vật lý (Physical address) – địa chỉ được nhìn thấy bởi đơn vị bộ nhớ (memory unit) „ Các địa chỉ logic và vật lý là như nhau trong các sơ đồ gắn kết địa chỉ thời gian biên dịch và thời gian nạp; các địa chỉ logic và vật lý khác nhau trong sơ đồ gắn kết địa chỉ thời gian thực hiện 8.9 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 ĐƠN VỊ QUẢN TRỊ BỘ NHỚ Memory-Management Unit (MMU) „ Thiết bị phần cứng ánh xạ địa chỉ ảo với địa chỉ vật lý „ Trong sơ đồ MMU, giá trị trong thanh ghi tái định vị được cộng với mỗi địa chỉ được sinh ra bởi một quá trình người dùng tại thời điểm nó được gửi đến bộ nhớ. „ Chương trình người dùng giao tiếp với các địa chỉ logic, không bao giờ nhìn thấy các địa chỉ thực 8.10 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 TÁI ĐỊNH VỊ ĐỘNG DÙNG MỘT THANH GHI TÁI ĐỊNH VỊ 8.11 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 NẠP ĐỘNG Dynamic Load „ Thủ tục (Routine) không được nạp đến tận khi được gọi „ Sử dụng không gian bộ nhớ tốt hơn, thủ tục không được dùng đến không bao giờ được nạp „ Hữu dụng khi các lượng lớn code cần thiết cho quản lý các trường hợp không thường xuyên xảy ra „ Không có hỗ trợ đặc biệt từ HĐH được yêu cầu được thực thi qua thiết kế chương trình 8.12 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 LIÊN KẾT ĐỘNG Dynamic Linking „ Liên kết bị trì hoãn đến tận thời gian thực hiện „ Mảnh code nhỏ, stub, được dùng để định vị thủ tục thư viện thường trú trong bộ nhớ thích hợp. „ Stub tự sắp đặt lại với địa chỉ thủ tục và thực hiện thủ tục „ HĐH cần kiểm tra thủ tục nằm trong không gian địa chỉ quá trình „ Liên kết động đặc biệt hữu dụng đối với các thư viện „ Hệ thống được biết như các thư viện chia sẻ (shared libraries) 8.13 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Swapping „ Một quá trình có thể được hoán chuyển tạm thời ra khỏi bộ nhớ lên lưu trữ ngoài, và sau đó được mang trở lại vào bộ nhớ để tiếp tục thực hiện. „ Lưu trữ ngoài – đĩa nhanh, đủ lớn để chứa được các bản sao của tất cả các ảnh bộ nhớ người dùng; phải cung cấp truy xuất trực tiếp đến các ảnh bộ nhớ này „ Roll out, roll in – biến thể của swapping được dùng cho các thuật toán lập lịch biểu dựa trên ưu tiên; quá trình độ ưu tiên thấp bị chuyển ra, quá trình có độ ưu tiên cao được nạp vào và được thực hiện „ Phần lớn thời gian swap là thời gian truyền; tổng thời gian truyền tỷ lệ với lượng bộ nhớ được swapped „ Các phiên bản được sửa đổi được tìm thấy trên nhiều HĐH (UNIX, Linux, và Windows) „ Hệ thống duy trì một hàng đợi sẵn sàng (ready queue) các quá trình sẵn sàng chạy có ảnh bộ nhớ trên đĩa 8.14 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Hình ảnh Swapping 8.15 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Cấp phát kề „ Bộ nhớ chính thông thường chia thành hai phần: z HĐH thường trú, thường được lưu trong bộ nhớ thấp với vector interrupt z Các quá trình người dùng được lưu trong bộ nhớ cao „ Các thanh ghi tái định vị được dùng để bảo vệ các quá trình người dùng z Thanh ghi cơ sở (base register) chứa giá trị của địa chỉ vật lý nhỏ nhất (của vùng nhớ được cấp phát) z Thanh ghi giới hạn (limit register) chứa khoảng địa chỉ logic (độ dài đoạn bộ nhớ được cấp phát) z MMU ánh xạ địa chỉ logic → vật lý 8.16 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Bảo vệ bộ nhớ với base register và limit register 8.17 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Cấp phát kề (Cont.) „ Cấp phát đa ngăn (multiple-partition allocation) z Lỗ (Hole) – khối bộ nhớ sẵn có; các lỗ kích cỡ khác nhau và trải ra trên bộ nhớ z Khi quá trình đến nó được cấp phát một lỗ đủ lớn để chứa quá trình z Hệ điều hành duy trì thông tin về : a) các ngăn được cấp phát b) các ngăn tự do (hole) OS process 5 process 8 process 2 OS process 5 process 2 OS process 5 process 2 OS process 5 process 9 process 2 process 9 process 10 8.18 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Cấp phát lưu trữ động „ First-fit: Cấp phát lỗ đầu tiên phù hợp „ Best-fit: Cấp phát lỗ nhỏ nhất trong các lỗ phù hợp „ Worst-fit: Cấp phát lỗ lớn nhất Làm thế nào thỏa mãn yêu cầu kích cỡ n từ một danh sách các lỗ tự do First-fit và best-fit tốt hơn worst-fit về tốc độ và sử dụng lưu trữ 8.19 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Phân mảnh (Fragmentation) „ Phân mảnh ngoài (External Fragmentation) – Tổng không gian bộ nhớ đủ để đáp ứng yêu cầu nhưng không kề (gồm những mảnh nhỏ nằm rải rác trong bộ nhớ) „ Phân mảnh trong (Internal Fragmentation) – Bộ nhớ được cấp phát cho quá trình lớn hơn bộ nhớ được yêu cầu, phần bộ nhớ “dư” trở nên “lãng phí” „ Giảm sự phân mảnh ngoài bởi “dồn nén” - compaction z Dồn nội dung bộ nhớ đã được cấp phát về một phía bộ nhớ, như vậy các “mảnh” nhỏ bộ nhớ tự do sẽ được “dổn về phía ngược lại, hợp lại thành một khối lớn z “Dồn nén” - Compaction chỉ có thể thực hiện với tái định vị động và được tiến hành ở thời gian chạy 8.20 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Phân trang - Paging „ Bộ nhớ vật lý được chia thành các khối kích thước cố định, được gọi là các khung - frames (kích thước là lũy thừa của 2, thường nằm trong khoảng 512 bytes đến 8,192 bytes) „ Bộ nhớ logic (của quá trình) được chia thành các khối cùng kích thước, được gọi là các trang - pages „ Lưu vết tất cả các khung tự do „ Bảng trang được sử dụng để dịch địa chỉ logic sang địa chỉ vật lý „ Có thể dẫn đến hiện tượng phân mảnh trong 8.21 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Sơ đồ dịch địa chỉ „ Địa chỉ được sinh ra bởi CPU được chia thành hai phần: z Số trang - Page number (p) – được dùng như chỉ số trong bảng trang, “ô” ở chỉ số đó lưu địa chỉ cơ sở của khung chứa trang z Độ dời trang - Page offset (d) – Được tổ hợp với địa chỉ cơ sở để xác định địa chỉ vật lý z Đối với không gian địa chỉ logic 2m và kích thước trang 2n page number page offset p d m - n n 8.22 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Phần cứng phân trang 8.23 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Mô hình phân trang của bộ nhớ logic và bộ nhớ vật lý 8.24 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Ví dụ phân trang Bộ nhớ 32-byte và kích thước trang 4-byte 8.25 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Các khung tự do Trước khi cấp phát Sau khi cấp phát 8.26 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Thực thi bảng trang „ Bảng trang được duy trì trong bộ nhớ chính „ Thanh ghi cơ sở bảng trang - Page-table base register (PTBR) trỏ tới bảng trang „ Thanh ghi độ dài bảng trang - Page-table length register (PRLR) chỉ ra kích thước của bảng trang „ Theo sơ đồ này, mỗi truy xuất data/instruction đòi hỏi hai truy xuất bộ nhớ: Một cho bảng trang và một cho data/instruction. „ Vấn đề hai truy xuất bộ nhớ có thể được giải quyết bởi sử dụng cache phần cứng tìm kiếm nhanh đặc biệt được gọi là bộ nhớ kết hợp (associative memory or translation look-aside buffers - TLBs) „ Một vài TLBs lưu bộ định danh không gian địa chỉ - address-space identifiers (ASIDs) trong mỗi đầu vào TLB – xác định duy nhất mỗi quá trình để cung cấp bảo vệ không gian địa chỉ cho quá trình đó 8.27 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Bộ nhớ kết hợp „ Bộ nhớ kết hợp – Tìm kiếm song song Dịch địa chỉ (p, d) z Nếu p có trong thanh ghi kết hợp lấy ra số khung z Nếu không lấy số khung từ bảng trang trong bộ nhớ Page # Frame # 8.28 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Phần cứng phân trang với TLB 8.29 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Thời gian truy xuất hiệu quả „ Tìm kiếm kết hợp (Associative Lookup) = ε (đơn vị thời gian) „ Giả sử thời gian chu kỳ bộ nhớ là 1 microsecond „ Hit ratio – phần trăm thời gian một số trang được tìm thấy trong các thanh ghi kết hợp; tỷ số này liên quan đến số các thanh ghi kết hợp „ Hit ratio = α „ Effective Access Time (EAT) EAT = (1 + ε) α + (2 + ε)(1 – α) = 2 + ε – α 8.30 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Bảo vệ bộ nhớ „ Bảo vệ bộ nhớ được thực thi bởi kết hợp bit bảo vệ với mỗi khung „ Bit Valid-invalid được gắn với mỗi đầu vào bảng trang: z “valid” chỉ ra rằng trang kết hợp là trong không gian địa chỉ logic của quá trình, và như vậy là một trang hợp lệ z “invalid” chỉ ra rằng trang không ở trong không gian địa chỉ của quá trình 8.31 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Bit Valid (v) / Invalid (i) trong một bảng trang 8.32 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Các trang chia sẻ „ Code chia sẻ z Một bản sao của code chỉ đọc được chia sẻ giữa các quá trình (text editors, compilers, window systems). z Code chia sẻ phải xuất hiện trong cùng vị trí trong không gian địa chỉ logic của tất cả các quá trình „ Code riêng và Data riêng (Private code and data) z Mỗi quá trình giữ một bản sao code và dữ liệu tách biệt z Các trang của code riêng và data riêng có thể xuất hiện bất kỳ nơi nào trong không gian địa chỉ logic 8.33 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Ví dụ các trang chia sẻ 8.34 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Cấu trúc bảng trang „ Bảng trang phân cấp „ Bảng trang băm „ Bảng trang nghịch đảo 8.35 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Bảng trang phân cấp „ Bảng trang được xem như “không gian địa chỉ logic” được phân trang và có bảng trang tương ứng „ Một kỹ thuật đơn giản là bảng trang hai mức 8.36 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Two-Level Page-Table Scheme 8.37 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Ví dụ phân trang hai mức „ Địa chỉ logic (trên máy 32-bit với kích thước trang 1K) được chia thành: z Số trang gồm 22 bits z Độ dời trang gồm 10 bits „ Vì bảng trang được phân trang, số trang được chia thành : z Số trang 12-bit z Độ dời 10-bit „ Như vậy, một địa chỉ logic như sau: trong đó p1 là chỉ số cho bảng trang ngoài, p2 là độ dời của bảng trang trong page number page offset pi p2 d 12 10 10 8.38 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Sơ đồ dịch địa chỉ 8.39 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Sơ đồ phân trang đa mức 8.40 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Bảng trang băm „ Thông thường dùng trong không gian địa chỉ > 32 bits „ Số trang ảo được băm vào một bảng trang. Bảng trang này chứa một danh sách các phần tử băm đến cùng vị trí. „ Số trang ảo được so sánh với các số trang trong danh sách. Nếu tương thích, khung vật lý tương ứng được trích ra. 8.41 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Bảng trang băm 8.42 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Bảng trang nghịch đảo „ Một đầu vào cho một trang bộ nhớ thực (khung) „ Đầu vào gồm địa chỉ ảo của trang được được chứa trong trang thực tương ứng, với thông tin về quá trình sở hữu trang „ Giảm bộ nhớ cần thiết để lưu trữ bảng trang nhưng tăng thời gian tìm kiếm 8.43 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Kiến trúc bảng trang nghịch đảo 8.44 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Phân đoạn - Segmentation „ Sơ đồ quản trị bộ nhớ hỗ trợ góc nhìn người dùng „ Một chương trình là một bộ các đoạn. Một đoạn là một đơn vị logic: main program, procedure, function, method, object, local variables, global variables, common block, stack, symbol table, arrays 8.45 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Góc nhìn người dùng về một chương trình 8.46 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Góc nhìn Logic về phân đoạn 1 3 2 4 1 4 2 3 user space physical memory space 8.47 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Kiến trúc phân đoạn „ Địa chỉ logic gồm: „ Bảng đoạn - Segment table – ánh xạ địa chỉ vật lý hai chiều; mỗi đầu vào bảng đoạn gồm: z base – chứa địa chỉ vật lý đầu đoạn z limit – Xác định chiều dài đoạn „ Thanh ghi cơ sở bảng đoạn - Segment-table base register (STBR) trỏ tới vị trí bảng đoạn trong bộ nhớ „ Thanh ghi độ dài bảng đoạn - Segment-table length register (STLR) chỉ ra số đoạn được dùng bởi một chương trình Số doạn s là hợp lệ nếu s < STLR 8.48 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Kiến trúc phân đoạn (Cont.) „ Bảo vệ z Kết hợp với mỗi dầu vào bảng đoạn:  Bit validation (= 0 ⇒ đoạn bất hợp lệ) Quyền read/write/execute „ Các bít bảo vệ được kết hợp với các đoạn; chia sẻ code xảy ra ở mức đoạn „ Độ dài đoạn thay đổi, nên cấp phát bộ nhớ là vấn đề cấp phát lưu trữ động 8.49 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Phần cứng phân đoạn 8.50 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Ví dụ phân đoạn 8.51 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Example: The Intel Pentium „ Supports both segmentation and segmentation with paging „ CPU generates logical address z Given to segmentation unit Which produces linear addresses z Linear address given to paging unit Which generates physical address in main memory  Paging units form equivalent of MMU 8.52 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Logical to Physical Address Translation in Pentium 8.53 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Intel Pentium Segmentation 8.54 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Pentium Paging Architecture 8.55 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Linear Address in Linux Broken into four parts: 8.56 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 22, 2005 Three-level Paging in Linux End of Chapter 7