Bài giảng Hệ điều hành - Chương 7, Phần 1: Quản lý bộ nhớ - Trần Thị Như Nguyệt

cấp phát 
 cho nó ngay không? 
 4 Quản lý bộ nhớ 
 Mục tiêu 
 Hiểu được các khái niệm cơ sở về bộ nhớ 
 Hiểu được các kiểu địa chỉ nhớ và cách chuyển đổi 
 giữa các kiểu này 
 Hiểu được các cơ chế và mô hình quản lý bộ nhớ 
 5 Quản lý bộ nhớ 
 Nội dung 
 Khái niệm cơ sở 
 Các kiểu địa chỉ nhớ 
 Chuyển đổi địa chỉ nhớ 
 Overlay và swapping 
 Mô hình quản lý bộ nhớ 
 6 Quản lý bộ nhớ 
 Nội dung 
 Khái niệm cơ sở 
 Các kiểu địa chỉ nhớ 
 Chuyển đổi địa chỉ nhớ 
 Overlay và swapping 
 Mô hình quản lý bộ nhớ 
 7 Quản lý bộ nhớ 
 Khái niệm cơ sở 
 Chương trình phải được mang vào trong bộ nhớ và 
 đặt nótrong một tiến trình để được xử lý 
 Input Queue – Một tập hợp của những tiến trình 
 trên đĩa mà đang chờ để được mang vào trong bộ 
 nhớ để thực thi. 
 User programs trải qua nhiều bước trước khi được 
 xử lý (compiler – Linking – Loader – Exe) 
 8 Quản lý bộ nhớ 
 Khái niệm cơ sở (tt) 
 Quản lý bộ nhớ làcông việc của hệ điều hành với 
 sự hỗ trợ của phần cứng nhằm phân phối, sắp xếp 
 các process trong bộ nhớ sao cho hiệu quả. 
 Mục tiêu cần đạt được là nạp càng nhiều process 
 vào bộ nhớ càng tốt (gia tăng mức độ đa chương) 
 Trong hầu hết các hệ thống, kernel sẽ chiếm một 
 phần cố định của bộ nhớ; phần còn lại phân phối 
 cho các process. 
 9 Quản lý bộ nhớ 
 Khái niệm cơ sở (tt) 
 Các yêu cầu đối với việc quản lý bộ nhớ 
  Cấp phát bộ nhớ cho các process 
  Tái định vị (relocation): khi swapping, 
  Bảo vệ: phải kiểm tra truy xuất bộ nhớ có hợp lệ 
 không 
  Chia sẻ: cho phép các process chia sẻ vùng nhớ 
 chung 
  Kết gán địa chỉ nhớ luận lý của user vào địa chỉ 
 thực 
 10 Quản lý bộ nhớ 
 Nội dung 
 Khái niệm cơ sở 
 Các kiểu địa chỉ nhớ 
 Chuyển đổi địa chỉ nhớ 
 Overlay và swapping 
 Mô hình quản lý bộ nhớ 
 11 Quản lý bộ nhớ 
 Các kiểu địa chỉ nhớ 
 Địa chỉ vật lý(physical address) (địa chỉthự c) là một vị trí thực 
 trong bộ nhớ chính 
 Địa chỉ luận lý(logical address) là một vị trí nhớ được diễn tả 
 trong một chương trình (còn gọi là địa chỉ ảo virtual address). 
  Các trình biên dịch (compiler) tạo ra mã lệnh chương trình mà trong 
 đó mọi tham chiếu bộ nhớ đều là địa chỉ luận lý 
  Địa chỉ tương đối (relative address) (địa chỉ khả tái định vị, 
 relocatable address) là một kiểu địa chỉ luận lý trong đó các địa chỉ 
 được biểu diễn tương đối so với một vị trí xác định nào đótrong 
 chương trình. 
 Ví dụ: 12 byte so với vị trí bắt đầu chương trình, 
  Địa chỉ tuyệt đối (absolute address): địa chỉ tương đương với địa chỉ 
 thực. 
 12 Quản lý bộ nhớ 
 Nạp chương trình vào bộ nhớ 
 Bộlinker : kết hợp các object module thành một file nhị phân khả 
 thực thi gọi làload module. 
 Bộloader : nạp load module vào bộ nhớ chính 
 13 Quản lý bộ nhớ 
 Cơ chế thực hiện linking 
 0 0 
 Module A relocatable Module A 
 object modules 
 CALL B length L JMP “L” 
 L 1 Return L 1 Return 
 L Module B 
 0 Module B 
 load module JMP “L+M” 
 CALL C length M 
 L M 1 Return 
M 1 Return 
 L M Module C 
 0 Module C 
 length N 
 L M N 1 Return 
N 1 Return 
 14 Quản lý bộ nhớ 
 Các bước nạp chương trình vào bộ nhớ
 ABBOTT.C COSTELLO.C 
 int idunno; ... 
 ... int whosonfirst (int x) “SOURCE 
 whosonfirst(idunno); { 
 ... ... CODE” 
 } 
Khi mỗi file được biên 
dịch, các địa chỉ chưa 
 Compiler Compiler 
biết, vì thế các cờ 
được dùng để đánh ABBOTT.OBJ COSTELLO.OBJ 
dấu ... ... “OBJECT 
 MOVE R1, (idunno) ... 
 CALL whosonfirst whosonfirst: CODE” 
 ... ... 
Trình linker kết nối Linker Memory 
các files, vì thế nó có 
 HAHAHA.EXE 
thể thay thế các chỗ HAHAHA.EXE ... 
đánh dấu với địa chỉ ... MOVE R1, 22388 
thật MOVE R1, 2388 Loader/ CALL 21547 
 CALL 1547 locator ... 
 ... ... 
 ... Phải xác định địa 21547 MOVE R1, R5 
 1547 MOVE R1, R5 chỉ bộ nhớ bắt đầu ... 
 ... 22388 (value of idunno)) 
 2388 (value of idunno) để thực thi 
 Nội dung 
 Khái niệm cơ sở 
 Các kiểu địa chỉ nhớ 
 Chuyển đổi địa chỉ nhớ 
 Overlay và swapping 
 Mô hình quản lý bộ nhớ 
 16 Quản lý bộ nhớ 
 Chuyển đổi địa chỉ 
 Chuyển đổi địa chỉ:quá trình ánh xạ một địa chỉ từ không gian 
 địa chỉ này sang không gian địa chỉ khác. 
 Biểu diễn địa chỉ nhớ 
  Trong source code: symbolic (các biến, hằng, pointer,) 
  Trong thời điểm biên dịch: thường là địa chỉ khả tái định vị
 Ví dụ: a ở vị trí 12 byte so với vị trí bắt đầu module 
  Thời điểm liking/loading: có thể là địa chỉ thực. 
 Ví dụ: dữ liệu nằm tại địa chỉ bộ nhớ thực 2030 
 0 2000 
 int i; 
 goto p1; 
 p1 
 250 2250 
 symbolic address relocatable address 
 physical memory 
 17 Quản lý bộ nhớ 
 Chuyển đổi địa chỉ (tt) 
 Địa chỉ lệnh và dữ liệu được chuyển đổi thành địa chỉ thực có thể
 xảy ra tại ba thời điểm khác nhau. 
  Compile time: nếu biết trước địa chỉ bộ nhớ của chương trình thì có
 thể kết gán địa chỉ tuyệt đối lúc biên dịch 
 Ví dụ: chương trình .COM của MS-DOS 
 Khuyết điểm: phải biên dịch lại nếu thay đổi địa chỉ nạp chương 
 trình 
  Load time: vào thời điểm loading, loader phải chuyển đổi địa chỉ 
 khả tái định vị thành địa chỉ thực dựa trên một địa chỉ nền
 Địa chỉ thực được tính toán vào thời điểm nạp chương trình 
 phải tiến hành reload nếu địa chỉ nền thay đổi
 18 Quản lý bộ nhớ 
 Sinh địa chỉ tuyệt đối vào thời điểm dịch 
 Symbolic Absolute Physical memory 
 addresses addresses addresses 
 PROGRAM 1024 1024 
 JUMP i JUMP 1424 JUMP 1424 
i 1424 1424 
 LOAD j LOAD 2224 LOAD 2224 
 Compile Link/Load 
 DATA 
j 2224 2224 
 Source code Absolute load module Process image 
 19 Quản lý bộ nhớ 
 Sinh địa chỉ tuyệt đối vào thời điểm nạp 
 Relative 
 Symbolic (relocatable) Physical memory 
 addresses addresses addresses 
 PROGRAM 0 1024 
 JUMP i JUMP 400 JUMP 1424 
i 400 1424 
 LOAD j LOAD 1200 
 Compile Link/Load LOAD 2224 
 DATA 
j 1200 2224 
 Source code Relative Process image 
 load module 
 20 Quản lý bộ nhớ 
 Chuyển đổi địa chỉ (tt) 
 Excution time: khi trong quá trình 
 thực thi, process có thể được di Relative (relocatable) 
 chuyển từ segment này sang addresses 
 segment khác trong bộ nhớ thì quá 0 
 trình chuyển đổi địa chỉ được trì 
 hoãn đến thời điểm thực thi JUMP 400 
 Cần sự hỗ trợ của phần cứng 400 
 cho việc ánh xạ địa chỉ LOAD 1200 
 Ví dụ: Trường hợp địa chỉ 
 luận lý là relocatable thì có
 thể dùng thanh ghi base và 1200 
 limit,.. 
 Sử dụng trong đa số các OS đa MAX = 2000 
 dụng trong đó có các cơ chế 
 swapping, paging, segmentation 
 21 Quản lý bộ nhớ 
 Dynamic linking 
 Quá trình link đến một module ngoài (external module) được 
 thực hiện sau khi đã tạo xong load module (i.e. file có thể thực 
 thi, executable) 
  Ví dụtrong Windows: module ngoài là các file .DLL còn trong 
 Unix, các module ngoài là các file .so (shared library) 
 Load module chứa các stub tham chiếu (refer) đến routine của 
 external module. 
  Lúc thực thi, khi stub được thực thi lần đầu (do process gọi routine 
 lần đầu), stub nạp routine vào bộ nhớ, tựthay thế bằng địa chỉ của 
 routine vàroutine được thực thi. 
  Các lần gọi routine sau sẽ xảy ra bình thường 
 Stub cần sự hỗ trợ của OS (như kiểm tra xem routine đã được nạp 
 vào bộ nhớ chưa). 
 22 Quản lý bộ nhớ 
 Ưu điểm của dynamic linking 
 Thông thường, external module là một thư viện cung 
 cấp các tiện ích của OS. Các chương trình thực thi có 
 thể dùng các phiên bản khác nhau của external 
 module mà không cần sửa đổi, biên dịch lại. 
 Chia sẻ mã (code sharing): một external module chỉ 
 cần nạp vào bộ nhớ một lần. Các process cần dùng 
 external module này thì cùng chia sẻ đoạn mã của 
 external module ⇒ tiết kiệm không gian nhớ và đĩa. 
 Phương pháp dynamic linking cần sự hỗ trợ của OS 
 trong việc kiểm tra xem một thủ tục nào đó có thể 
 được chia sẻ giữa các process hay là phần mã của 
 riêng một process (bởi vì chỉ có OS mới có quyền 
 thực hiện việc kiểm tra này). 
 23 Quản lý bộ nhớ 
 Dynamic loading 
 Cơ chế: chỉ khi nào cần được gọi đến thì một thủ tục mới được 
 nạp vào bộ nhớ chính ⇒ tăng độ hiệu dụng của bộ nhớ bởi vì 
 các thủ tục không được gọi đến sẽ không chiếm chỗ trong bộ 
 nhớ 
 Rất hiệu quả trong trường hợp tồn tại khối lượng lớn mã 
 chương trình có tần suất sử dụng thấp, không được sử dụng 
 thường xuyên (ví dụ các thủ tục xử lý lỗi) 
 Hỗ trợ từ hệ điều hành 
  Thông thường, user chịu trách nhiệm thiết kế và hiện thực 
 các chương trình có dynamic loading. 
  Hệ điều hành chủ yếu cung cấp một số thủ tục thư viện hỗ 
 trợ, tạo điều kiện dễ dàng hơn cho lập trình viên. 
 24 Quản lý bộ nhớ 
 Nội dung 
 Khái niệm cơ sở 
 Các kiểu địa chỉ nhớ 
 Chuyển đổi địa chỉ nhớ 
 Overlay và swapping 
 Mô hình quản lý bộ nhớ 
 25 Quản lý bộ nhớ 
 Cơ chế phủ lắp (overlay) 
 Tại mỗi thời điểm, chỉ giữ lại trong bộ nhớ 
 những lệnh hoặc dữ liệu cần thiết, giải phóng các 
 lệnh/dữ liệu chưa hoặc không cần dùng đến. 
 Cơ chế này rất hữu dụng khi kích thước một 
 process lớn hơn không gian bộ nhớ cấp cho 
 process đó. 
 Cơ chế này được điều khiển bởi người sử dụng 
 (thông qua sự hỗ trợ của các thư viện lập trình) 
 chứ không cần sự hỗ trợ của hệ điều hành 
 26 Quản lý bộ nhớ 
 Cơ chế phủ lắp (tt) 
Pass 1 70K Đơn vị: byte 
Pass 2 80K symbol 20K 
Symbol table 20K table 
Common routines 30K 
 common 
 Assembler 30K 
 routines 
Total memory 
available = 150KB 
 overlay 10K 
 driver nap̣ va ̀ thực thi 
 pass 1 pass 2 
 70K 80K 
 27 Quản lý bộ nhớ 
 Cơ chế hoán vị (swapping) 
 Một process có thể tạm thời bị swap ra khỏi bộ nhớ 
 chính và lưu trên một hệ thống lưu trữ phụ. Sau đó, 
 process có thể được nạp lại vào bộ nhớ để tiếp tục quá 
 trình thực thi. 
 Swapping policy: hai ví dụ 
  Round-robin: swap out P1 (vừa tiêu thụ hết quantum 
 của nó), swap in P2 , thực thi P2, 
  Roll out, roll in: dùng trong cơ chế định thời theo độ 
 ưu tiên (priority-based scheduling) 
 Process có độ ưu tiên thấp hơn sẽ bị swap out 
 nhường chỗ cho process có độ ưu tiên cao hơn 
 mới đến được nạp vào bộ nhớ để thực thi 
 Hiện nay, ít hệ thống sử dụng cơ chế swapping trên 
 28 Quản lý bộ nhớ 
Minh họa cơ chế hoán vị 
 29 Quản lý bộ nhớ 
 Nội dung 
 Khái niệm cơ sở 
 Các kiểu địa chỉ nhớ 
 Chuyển đổi địa chỉ nhớ 
 Overlay và swapping 
 Mô hình quản lý bộ nhớ 
 30 Quản lý bộ nhớ 
 Mô hình quản lý bộ nhớ 
 Trong chương này, mô hình quản lý bộ nhớ là một mô 
 hình đơn giản, không có bộ nhớ ảo. 
 Một process phải được nạp hoàn toàn vào bộ nhớ thì 
 mới được thực thi (ngoại trừ khi sử dụng cơ chế 
 overlay). 
 Các cơ chế quản lý bộ nhớ sau đây rất ít (hầu như 
 không còn) được dùng trong các hệ thống hiện đại 
  Phân chia cố định (fixed partitioning) 
  Phân chia động (dynamic partitioning) 
  Phân trang đơn giản (simple paging) 
  Phân đoạn đơn giản (simple segmentation) 
 31 Quản lý bộ nhớ 
Mô hình quản lý bộ nhớ (tt) 
 32 Quản lý bộ nhớ 
 Phân mảnh (fragmentation) 
 Phân mảnh ngoại (external fragmentation) 
  Kích thước không gian nhớ còn trống đủ để thỏa 
 mãn một yêu cầu cấp phát, tuy nhiên không gian nhớ 
 này không liên tục ⇒ có thể dùng cơ chế kết khối 
 (compaction) để gom lại thành vùng nhớ liên tục. 
 Phân mảnh nội (internal fragmentation) 
  Kích thước vùng nhớ được cấp phát có thể hơi lớn 
 hơn vùng nhớ yêu cầu. 
 Ví dụ: cấp một khoảng trống 18,464 bytes cho một 
 process yêu cầu 18,462 bytes. 
  Hiện tượng phân mảnh nội thường xảy ra khi bộ nhớ 
 thực được chia thành các khối kích thước cố định 
 (fixed-sized block) và các process được cấp phát 
 theo đơn vị khối. Ví dụ: cơ chế phân trang (paging). 
 33 Quản lý bộ nhớ 
 Phân mảnh nội 
 operating yeâu caàu keá tieáp laø 
 system 18,462 bytes !!! 
 (used) 
hole kích thöôùc 
18,464 bytes caàn quaûn lyù khoaûng 
 troáng 2 bytes !?! 
 OS seõ caáp phaùt haún khoái 18,464 bytes 
 cho process dö ra 2 bytes khoâng duøng! 
 34 Quản lý bộ nhớ 
 Fixed partitioning 
 Khi khởi động hệ thống, bộ nhớ chính 
 được chia thành nhiều phần rời nhau 
 gọi là các partition có kích thước bằng 
 nhau hoặc khác nhau 
 Process nào có kích thước nhỏ hơn 
 hoặc bằng kích thước partition thì có 
 thể được nạp vào partition đó. 
 Nếu chương trình có kích thước lớn 
 hơn partition thì phải dùng cơ chế 
 overlay. 
 Nhận xét 
  Không hiệu quả do bị phân mảnh 
 nội: một chương trình dù lớn hay 
 nhỏ đều được cấp phát trọn một 
 partition. 
 35 Quản lý bộ nhớ 
 Chiến lược placement 
 Partition có kích thước bằng nhau 
  Nếu còn partition trống ⇒ process mới 
 sẽ được nạp vào partition đó 
  Nếu không còn partition trống, nhưng 
 trong đó có process đang bị blocked 
 ⇒ swap process đó ra bộ nhớ phụ 
 nhường chỗ cho process mới. 
 Partition có kích thước không bằng 
 nhau: giải pháp 1 
  Gán mỗi process vào partition nhỏ 
 nhất phù hợp với nó 
  Có hàng đợi cho mỗi partition 
  Giảm thiểu phân mảnh nội 
  Vấn đề: có thể có một số hàng đợi 
 trống không (vì không có process với 
 kích thước tương ứng) và hàng đợi 
 c dày đặ
 36 Quản lý bộ nhớ 
 Chiến lược placement (tt) 
 Partition có kích thước không 
 bằng nhau: giải pháp 2 
  Chỉ có một hàng đợi chung 
 cho mọi partition 
  Khi cần nạp một process 
 vào bộ nhớ chính ⇒ chọn 
 partition nhỏ nhất còn 
 trống 
 37 Quản lý bộ nhớ 
 Dynamic partitioning 
 Số lượng partition không cố định và partition có thể có 
 kích thước khác nhau 
 Mỗi process được cấp phát chính xác dung lượng bộ 
 nhớ cần thiết 
 Gây ra hiện tượng phân mảnh ngoại 
 38 Quản lý bộ nhớ 
 Chiến lược placement 
 Dùng để quyết định cấp phát khối 
 bộ nhớ trống nào cho một process 
 Mục tiêu: giảm chi phí compaction 
 Các chiến lược placement 
  Best-fit: chọn khối nhớ trống 
 nhỏ nhất 
  First-fit: chọn khối nhớ trống 
 phù hợp đầu tiên kể từ đầu bộ 
 nhớ 
  Next-fit: chọn khối nhớ trống 
 phù hợp đầu tiên kể từ vị trí 
 cấp phát cuối cùng 
  Worst-fit: chọn khối nhớ trống 
 lớn nhất 
 39 Quản lý bộ nhớ 
 Ôn tập 
 Khái niệm cơ sở 
 Các kiểu địa chỉ nhớ 
 Chuyển đổi địa chỉ nhớ 
 Overlay và swapping 
 Mô hình quản lý bộ nhớ
 40 Quản lý bộ nhớ 
 Bài tập 
 Cơ chế: 
 41 Quản lý bộ nhớ 
Kết thúc chương 7-1