Bài giảng Nguyên lí hệ điều hành - Chương 8: Bộ nhớ chính - Phạm Quang Dũng

Nội dung text: Bài giảng Nguyên lí hệ điều hành - Chương 8: Bộ nhớ chính - Phạm Quang Dũng

1. Nội dung chương 8 BÀI GIẢNG NGUYÊN LÝ HỆ ĐIỀU HÀNH „ Kiến thức cơ bản „ Swapping „ Phân phối bộ nhớ liên tiếp - Contiguous Allocation Chương 8: Bộ nhớ chính „ Phân trang - Paging „ Phân đoạn - Segmentation Phạm Quang Dũng „ Kết hợp phân đoạn với phân trang Bộ môn Khoa học máy tính Khoa Công nghệ thông tin - Segmentation with Paging Trường Đại học Nông nghiệp Hà Nội „ Ví dụ: Intel Pentium DĐ: 0979784189 Website: fita.hua.edu.vn/pqdung Bài giảng Nguyên lý Hệ điều hành 8.2 Phạm Quang Dũng ©2008 Mục tiêu 8.1. Kiến thức cơ bản 8.1.1. Về phần cứng „ Cung cấp mô tả chi tiết các cách tổ chức phần cứng bộ nhớ. „ Chương trình phải được đưa từ đĩa vào bộ nhớ chính và được đặt vào một tiến trình để nó có thể chạy. „ Thảo luận các kỹ thuật quản lý bộ nhớ khác nhau, bao gồm phân trang và phân đoạn. „ Bộ nhớ chính, cache, các thanh ghi là bộ nhớ mà CPU có „ Cung cấp mô tả chi tiết về Intel Pentium, bộ xử lý hỗ trợ thể truy nhập trực tiếp. cả phân đoạn đơn thuần và phân đoạn kết hợp với phân „ Yêu cầu bộ nhớ phải được bảo vệ để đảm bảo sự hoạt trang. động đúng đắn. Bài giảng Nguyên lý Hệ điều hành 8.3 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.4 Phạm Quang Dũng ©2008 1
2. Các thanh ghi base và limit Bảo vệ bộ nhớ với các thanh ghi base & limit „ Cặp thanh ghi base và limit xác định không gian địa chỉ hợp lệ mà tiến trình của người sử dụng được phép truy nhập. Sự bảovệ bộ nhớđượcthựchiệnbằng cách so sánh mọi địachỉ trong user mode với các thanh ghi base và limit. Nếu địachỉđónằm ngoài khoảng địachỉ xác định bởi 2 thanh ghi thì mắcbẫy chuyển sang monitor mode. Bài giảng Nguyên lý Hệ điều hành 8.5 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.6 Phạm Quang Dũng ©2008 Sử dụng 2 thanh ghi base và limit (tiếp) 8.1.2.Liên kết các lệnh và dữ liệu tới bộ nhớ Sự liên kết địa chỉ của các lệnh và dữ liệu (của tiến trình) tới các „ Các lệnh nạp các thanh ghi base và limit là các lệnh địa chỉ bộ nhớ có thể xảy ra 3 giai đoạn khác nhau: đặcquyền. „ Compile time: Nếu vị trí bộ nhớ được biết trước, mã chính xác (absolute code) có thể được sinh ra; phải biên dịch lại m㠄 Khi thựchiện trong monitor mode, HĐH không hạn nếu vị trí bắt đầu thay đổi. vd chương trình .COM của MS DOS. chế truy nhậpbộ nhớ. „ Load time: Phải sinh ra mã có thể tái định vị (relocatable ⇒ cho phép HĐH nạpchương trình củangườisử code) nếu vị trí bộ nhớ không được biết ở giai đoạn biên dịch. dụng vào bộ nhớ, đưacácchương trình đó ra ngoài „ Execution time: Sự liên kết bị hoãn lại đến giai đoạn chạy nếu trong quá trình thực hiện tiến trình có thể bị chuyển từ một khi có lỗi. đoạn bộ nhớ đến đoạn khác. Cần có sự hỗ trợ phần cứng để ánh xạ địa chỉ (ví dụ, base và limit registers). Hầu hết các HĐH đa năng sử dụng phương pháp này. Bài giảng Nguyên lý Hệ điều hành 8.7 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.8 Phạm Quang Dũng ©2008 2
3. Các bước xử lý chương trình người sử dụng 8.1.3. Logical vs. Physical Address Space „ Khái niệm không gian địa chỉ logic (logical address space) được tách riêng với không gian địa chỉ vật lý (physical address space) để quản lý bộ nhớ thích hợp. z Logical address – được tạo ra bởi CPU; còn được gọi là địa chỉảo (virtual address). z Physical address – địa chỉ được nhận biết bởi đơn vị quản lý bộ nhớ (memory unit). „ Các địa chỉ logic (ảo) và vật lý là như nhau trong các giai đoạn liên kết địa chỉ compile-time và load-time; chúng khác nhau trong execution-time. Bài giảng Nguyên lý Hệ điều hành 8.9 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.10 Phạm Quang Dũng ©2008 Memory-Management Unit (MMU) Định vị động sử dụng thanh ghi định vị „ Là thiết bị phần cứng ánh xạ địa chỉảo tới địa chỉ vật lý. „ Trong lược đồ MMU, giá trị trong thanh ghi định vị (relocation register) được cộng với tất cả địa chỉ được sinh ra bởi tiến trình của người sử dụng tại thời điểm nó được gửi tới bộ nhớ. „ Chương trình của người sử dụng làm việc với các địa chỉ logic; nó không bao giờ nhận ra các địa chỉ vật lý thực. Bài giảng Nguyên lý Hệ điều hành 8.11 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.12 Phạm Quang Dũng ©2008 3
4. 8.1.4. Dynamic Loading 8.1.5. Dynamic Linking „ Tiến trình chỉ được nạp vào bộ nhớ khi nó được gọi. „ Việc liên kết hoãn lại đến execution time. „ Đoạn mã nhỏ, stub, được sử dụng để định vị thường trình thư viện „ Sử dụng không gian bộ nhớ tốt hơn; tiến trình không cư trú trong bộ nhớ (memory-resident library routine) thích hợp, hoặc dùng đến thì không bao giờ được nạp. để nạp thư viện nếu thường trình hiện tại chưa sẵn sàng. „ Khi được thực hiện, stub kiểm tra thường trình cần đến có trong bộ „ Hữu ích trong trường hợp số lượng lớn mã cần xử lý nhớ của tiến trình chưa, nhưng hiếm khi xuất hiện. z nếu chưa thì chương trình nạp thường trình vào bộ nhớ; „ Không yêu cầu sự hỗ trợ đặc biệt từ HĐH, được thực z nếu rồi: stub tự thay thế chính nó bởi địa chỉ của thường trình rồi thực hiện thường trình đó. hiện thông qua thiết kế chương trình. „ Liên kết động đặc biệt hữu dụng đối với các thư viện chương trình, nhất là trong việc cập nhật thư viện (vd sửa lỗi) Bài giảng Nguyên lý Hệ điều hành 8.13 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.14 Phạm Quang Dũng ©2008 8.2. Swapping Giản đồ Swapping „ Một tiến trình có thể được tạm thời đưa ra khỏi bộ nhớ tới backing store (swap out), và sau đó được đưa trở lại bộ nhớ để thực hiện tiếp (swap in). „ Backing store – đĩa tốc độ nhanh, đủ lớn để lưu trữ bản sao của tất cả hình ảnh bộ nhớ cho tất cả người sử dụng; phải cung cấp sự truy nhập trực tiếp tới các hình ảnh bộ nhớ này. „ Hệ thống duy trì 1 ready queue chứa các tiến trình sẵn sàng chạy có ảnh bộ nhớ được chứa trên backing store hoặc trong bộ nhớ. „ Khi trình lập lịch CPU quyết định thực hiện 1 tiến trình, nó gọi trình điều vận. „ Trình điều vận kiểm tra tiến trình tiếp theo trong queue có trong bộ nhớ chưa, nếu chưa có và không còn vùng nhớ rỗi đủ lớn, nó đưa 1 tiến trình trong bộ nhớ ra backing store và đưa tiến trình mong muốn vào. Bài giảng Nguyên lý Hệ điều hành 8.15 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.16 Phạm Quang Dũng ©2008 4
5. Swapping (tiếp) 8.3. Phân phối bộ nhớ liên tiếp „ Phần lớn thời gian hoán đổi là thời gian chuyển dữ liệu; tổng thời gian chuyển tỷ lệ thuận với dung lượng bộ nhớ hoán đổi. „ Bộ nhớ chính được chia thành 2 phần: z Vd: giả sử dung lượng tiến trình người sử dụng là 10 MB z Nơi HĐH cư trú, thường ở vùng nhớ thấp, chứa bảng vector ngắt. backing store là đĩa cứng có tốc độ truyền dữ liệu là 40 MB/s z Các tiến trình của người sử dụng được chứa trong vùng nhớ cao. Thời gian truyền 1 chiều từ/đến bộ nhớ = 1/4 s = 250 ms „ Phân phối đơn partition (Single-partition allocation) giả sử trễ trung bình = 8 ms ⇒ Tổng truyền 1 chiều = 258 ms z Các thanh ghi định vị được sử dụng để bảo vệ các tiến ⇒ Tổng swap in + swap out = 258 x 2 = 516 ms. trình của người sử dụng không ảnh hưởng lẫn nhau và „ Roll out, roll in – biến thể hoán đổi được sử dụng cho thuật giải không thay đổi dữ liệu và mã HĐH. lập lịch dựa trên mức ưu tiên (priority-based scheduling); tiến z Relocation register chứa giá trị địa chỉ vật lý nhỏ nhất; limit trình có mức ưu tiên thấp hơn bị thay ra để tiến trình có mức register chứa dải các địa chỉ logic - mỗi địa chỉ logic phải ưu tiên cao hơn có thể được nạp và thực hiện. nhỏ hơn limit register. „ Sự hoán đổi khác nhau ở các HĐH UNIX, Linux, Windows. z MMU ánh xạ địa chỉ logic theo cách động. Bài giảng Nguyên lý Hệ điều hành 8.17 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.18 Phạm Quang Dũng ©2008 Ví dụ các thanh ghi Relocation và Limit Phân phối liên tiếp (tiếp) „ Phân phối đa partition (Multiple-partition allocation) z Hole –khối bộ nhớ khả dụng; các hole có kích thước khác nhau nằm rải rác khắp bộ nhớ. z Khi một tiến trình đến, nó được phân phối cho một hole đủ lớn. z HĐH duy trì thông tin về: a) các vùng nhớ đã được phân phối - allocated partitions b) các vùng nhớ còn tự do - free partitions (hole) OS OS OS OS process 5 process 5 process 5 process 5 process 9 process 9 process 8 process 10 process 2 process 2 process 2 process 2 Bài giảng Nguyên lý Hệ điều hành 8.19 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.20 Phạm Quang Dũng ©2008 5
6. Bài toán phân phối vùng nhớ động Sự phân mảnh - Fragmentation Làm thế nào để đáp ứng một yêu cầu kích thước n từ danh sách „ External Fragmentation –tổng không gian bộ nhớ tự do thực các free holes. tế đủ đáp ứng yêu cầu, nhưng nó không nằm kề nhau. „ Internal Fragmentation –bộ nhớ được phân phối có thể lớn „ First-fit: Phân phối hole đầu tiên có đủ độ lớn. hơn không đáng kể so với bộ nhớ được yêu cầu; sự khác biệt „ Best-fit: Phân phối hole nhỏ nhất có đủ độ lớn; phải tìm kiếm kích thước này là bộ nhớ bên trong một partition, nhưng không toàn bộ danh sách, trừ khi DS được sắp xếp theo dung lượng. được sử dụng. z Tạo ra các hole còn lại nhỏ nhất „ Có thể làm giảm external fragmentation bằng cách nén lại (compaction) „ Worst-fit: Phân phối hole lớn nhất;cũng phải tìm kiếm toàn bộ z Di chuyển các nội dung bộ nhớ để đặt tất cả các vùng nhớ tự do danh sách. lại với nhau thành một khối lớn. z Tạo ra các hole còn lại lớn nhất z Kết khối chỉ có thể tiến hành nếu sự tái định vị là động, và nó được thực hiện trong execution time. First-fit và best-fit tốt hơn worst-fit về mặt tốc độ và sử dụng „ 1 phương pháp khác là phân phối bộ nhớ không liên tục. bộ nhớ. Bài giảng Nguyên lý Hệ điều hành 8.21 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.22 Phạm Quang Dũng ©2008 8.4. Phân trang - Paging Lược đồ biên dịch địa chỉ „ Không gian địa chỉ logic của một tiến trình có thể không kề „ Địa chỉ được tạo ra bởi CPU được chia thành: nhau; tiến trình được phân phối bộ nhớ vật lý bất kỳ lúc nào sau đókhi bộ nhớ sẵn có. z Page number (p) – được sử dụng làm index tới page table, chứa địa chỉ cơ sở (base address) của mỗi trang trong bộ nhớ vật lý. „ Chia bộ nhớ vật lý thành những khối có kích thước cố định là bội số của 2 (512 bytes - 16 MB),được gọi là các frame. z Page offset (d) –kết hợp với địa chỉ cơ sở để xác định địa chỉ bộ nhớ vật lý. „ Chia bộ nhớ logic thành các khối cùng kích thước - các page. „ Luôn theo dõi tất cả các frame còn trống. page number page offset p „ Để chạy một chương trình có kích thước n pages, cần phải tìm d n frames còn trống và nạp chương trình. m - n n „ Thiết lập một bảng phân trang (page table) để biên dịch z 2n = kích thước của 1 page (byte hoặc word) (translate) các địa chỉ logic thành địa chỉ vật lý. z 2m = kích thước không gian địa chỉ logic „ Sự phân đoạn diễn ra bên trong (Internal fragmentation). Bài giảng Nguyên lý Hệ điều hành 8.23 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.24 Phạm Quang Dũng ©2008 6
7. Lược đồ dịch địa chỉ (tiếp) Mô hình phân trang Bài giảng Nguyên lý Hệ điều hành 8.25 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.26 Phạm Quang Dũng ©2008 Ví dụ phân trang Các Frame rỗi Vd: Địa chỉ logic 4 (page 1, offset 0); theo bảng phân trang, trang 1 được ánh xạ tới frame 6 ⇒ địa chỉ logic ánh xạ tới địa chỉ vật lý = 6 x 4 + 0 = 24 Trước khi phân phối Sau khi phân phối 32-byte memory and 4-byte pages Bài giảng Nguyên lý Hệ điều hành 8.27 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.28 Phạm Quang Dũng ©2008 7
8. Sự thực thi của Page Table Phân trang với TLB „ Page table được lưu trong bộ nhớ chính. „ Page-table base register (PTBR) chỉ tới page table. „ Page-table length register (PRLR) cho biết kích thước của page table. „ Trong lược đồ phân trang, mọi sự truy nhập lệnh/dữ liệu yêu cầu 2 lần truy nhập bộ nhớ:một cho page table và một cho lệnh/dữ liệu → truy nhập chậm hơn. „ Vấn đề 2 lần truy nhập bộ nhớ có thể được giải quyết bằng cách sử dụng một bộ nhớ cache tra cứu nhanh đặc biệt gọi là bộ nhớ liên kết - associative memory (TLB). Bài giảng Nguyên lý Hệ điều hành 8.29 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.30 Phạm Quang Dũng ©2008 Bảo vệ bộ nhớ Valid (v) - Invalid (i) Bit trong bảng phân trang „ Sự bảo vệ bộ nhớ được thực thi bằng cách kết hợp protection bit với mỗi frame „ Mỗi phần tử trong bảng phân trang được gắn thêm một valid–invalid bit z “valid” (=1) cho biết trang tương ứng ở trong không gian địa chỉ logic của tiến trình, và do đólàmột trang hợp lệ. z “invalid” (=0) cho biết rằng trang không có trong không gian địa chỉ logic. Bài giảng Nguyên lý Hệ điều hành 8.31 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.32 Phạm Quang Dũng ©2008 8
9. Các trang chia sẻ Shared Pages Example „ Một lợi điểm của phân trang là khả năng chia sẻ mã chung, Vd: hệ thống hỗ trợ 40 đặc biệt quan trọng trong môi trường chia sẻ thời gian. user, mỗi user thực hiện „ Shared code một text editor gồm 150KB z Một bản copy của read-only code được chia sẻ giữa các tiến mã và 50KB dữ liệu. trình (i.e., text editors, compilers, window systems). -Nếu không chia sẻ dữ z Mã chia sẻ phải xuất hiện tại cùng vị trí trong không gian địa chỉ liệu, cần 8000KB. logic của tất cả các tiến trình. -Nếu chia sẻ 150KB mã, „ Private code and data chỉ tốn 150 + 40 x 50 = 2150 KB bộ nhớ. z Mỗi tiến trình giữ một bản copy mã và dữ liệu riêng. z Các trang của mã và dữ liệu riêng có thể xuất hiện tại bất kỳ đâu trong không gian địa chỉ logic. Bài giảng Nguyên lý Hệ điều hành 8.33 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.34 Phạm Quang Dũng ©2008 8.5. Phân đoạn - Segmentation Chương trình dưới góc nhìn của người sử dụng „ Là lược đồ quản lý bộ nhớ hỗ trợ cách nhìn của người sử dụng đối với bộ nhớ: „ Mỗi chương trình là một tập hợp các đoạn. Mỗi đoạn là một đơn vị logic như: main program, procedure, function, method, object, local variables, global variables, common block, stack, symbol table, arrays Bài giảng Nguyên lý Hệ điều hành 8.35 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.36 Phạm Quang Dũng ©2008 9
10. Góc nhìn logic của sự phân đoạn Kiến trúc phân đoạn „ Địa chỉ logic gồm 2 thành phần: 1 , 4 1 „ Segment table –tương tự bảng phân trang, mỗi mục của bảng 2 gồm có: z base –chứa địa chỉ vật lý đầu tiên của đoạn trong bộ nhớ. 3 2 z limit –xác định độ dài của đoạn. 4 „ Segment-table base register (STBR): trỏ tới vị trí của bảng 3 phân đoạn trong bộ nhớ. „ Segment-table length register (STLR): xác định số đoạn mà một chương trình sử dụng; user space physical memory space segment number s là hợp lệ nếu s < STLR. Bài giảng Nguyên lý Hệ điều hành 8.37 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.38 Phạm Quang Dũng ©2008 Kiến trúc phân đoạn (tiếp) Lược đồ phân đoạn „ Phân đoạn z các đoạn có kích thước khác nhau (khác với phân trang) „ Định vị z động z được thực hiện bởi bảng phân đoạn „ Phân phối bộ nhớ z giải quyết bài toán phân phối bộ nhớ động z first fit/best fit z có sự phân mảnh ngoài Bài giảng Nguyên lý Hệ điều hành 8.39 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.40 Phạm Quang Dũng ©2008 10
11. Ví dụ phân đoạn 8.6. Kết hợp phân đoạn với phân trang MULTICS „ Bộ nhớ được phân thành các đoạn, sau đómỗi đoạn lại được phân trang. „ Hệ thống MULTICS giải quyết được vấn đề phân mảnh ngoài và thời gian tìm kiếm dài. „ Giải pháp khác so với phân đoạn ở chỗ mỗi mục của bảng phân đoạn không chứa địa chỉ cơ sở của đoạn mà chứa địa chỉ cơ sở của bảng phân trang của đoạn đó. Bài giảng Nguyên lý Hệ điều hành 8.41 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.42 Phạm Quang Dũng ©2008 Lược đồ MULTICS Lược đồ MULTICS của Intel 80386 Bài giảng Nguyên lý Hệ điều hành 8.43 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.44 Phạm Quang Dũng ©2008 11
12. 8.7. Example: The Intel Pentium Sự biên dịch địa chỉ logic thành địa chỉ vật lý trong Pentium „ Hỗ trợ cả 2 cách quản lý bộ nhớ: phân đoạn, phân đoạn kết hợp với phân trang „ CPU sinh ra các địa chỉ logic z địa chỉ này được đưa tới segmentation unit (đơn vị phân đoạn) segmentation unit tạo ra 1 địa chỉ tuyến tính ứng với mỗi địa chỉ logic. z Địa chỉ tuyến tính được đưa tới paging unit (đơn vị phân trang) paging unit sinh ra địa chỉ vật lý trong bộ nhớ chính segmentation unit và paging unit tạo thành sự tương ứng của MMU. Bài giảng Nguyên lý Hệ điều hành 8.45 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.46 Phạm Quang Dũng ©2008 Intel Pentium Segmentation Pentium Paging „ Kích thước trang bằng 4 KB hoặc 4 MB. „ cờ Page Size (trong page directory): z = 1: kích thước page frame là 4 MB phân chia địa chỉ tuyến tính 32 bit: = z = 0: kích thước page frame là chuẩn 4 KB Sử dụng lược đồ phân trang 2 mức, phân chia địa chỉ tuyến tính 32-bit như sau: Bài giảng Nguyên lý Hệ điều hành 8.47 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.48 Phạm Quang Dũng ©2008 12
13. Pentium Paging Architecture Linear Address in Linux Được chia thành 4 phần: Bài giảng Nguyên lý Hệ điều hành 8.49 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 8.50 Phạm Quang Dũng ©2008 Three-level Paging in Linux End of Chapter 8 Bài giảng Nguyên lý Hệ điều hành 8.51 Phạm Quang Dũng ©2008 13