Bài giảng Hệ điều hành - Chương 7: Virtual memory - Lê Ngọc Minh

Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.29-
 Nhìn lại paging và segmentation
‰ Các tham chiếu đến bộ nhớ được chuyển đổi động
 thành địa chỉ thực lúc process đang thực thi
‰ Một process có thể được chi thành các phần nhỏ (page 
 hay segment); các phần này được nạp vào các vị trí
 không liên tục trong bộ nhớ chính
‰ Nhận xét quan trọng: không phải tất các các phần của
 một processs cần thiết phải được nạp vào bộ nhớ chính
 tại cùng một thời điểm
‰ Ví dụ
 – Đoạn mã điều khiển các lỗi hiếm khi xảy ra
 – Các arrays, list, tables được cấp phát bộ nhớ (cấp phát tĩnh) 
 nhiều hơn yêu cầu cần thiết
 – Một số tính năng ít khi được dùng của một chương trình
 – Ngay cả khi toàn bộ chương trình đều cần dùng thì  có thể
 không cần dùng toàn bộ cùng một lúc
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.30-
 15
 Quá trình thực thi của process
‰ OS nạp một số phần của chương trình vào bộ nhớ
‰ Mỗi bảng phân trang/đoạn có thêm một present bit cho
 biết phần tương ứng có nằm trong bộ nhớ chính hay 
 không.
‰ Khi có một tham chiếu nằm trong phần không có trong
 bộ nhớ chính (present bit = 0) thì một ngắt được kích
 hoạt gọi là memory fault
‰ Process chuyển về trạng thái Blocking 
‰ OS phát ra một yêu cầu đọc đĩa để nạp phần được
 tham chiếu vào bộ nhớ chính và trong khi đó, một
 process khác được chiếm quyền thực thi
‰ Sau khi I/O hoàn tất, một ngắt được kích hoạt, báo cho
 OS chuyển process tương ứng về trạng thái Ready 
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.31-
 Ưu điểm của bộ nhớ ảo
‰ Số lượng process trong bộ nhớ nhiều hơn
‰ Một process có thể thực thi ngay cả khi kích thước của
 nó lớn hơn bộ nhớ thực
‰ Bộ nhớ tham chiếu bởi một địa chỉ luận lý được gọi là
 bộ nhớ ảo (virtual memory)
 – Bao gồm bộ nhớ thực + một phần bộ nhớ thứ cấp (đĩa cứng,...)
 – Nhằm đạt hiệu quả cao, các dịch vụ file system thường được bỏ
 qua; đọc/ghi đĩa trực tiếp với các khối dữ liệu lớn hơn so với
 khối của hệ thống file.
 – Thông thường phần bộ nhớ ảo được lưu trữ ở một vùng đặc
 biệt gọi là không gian tráo đổi (swap space). Ví dụ file system 
 swap trong Unix/Linux, file pagefile.sys trong Windows2K
‰ Việc chuyển đổi từ địa chỉ luận lý thành địa chỉ thực được thực hiện
 với sự hỗ trợ của phần cứng (memory management hardware)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.32-
 16
 Yêu cầu đối với bộ nhớ ảo
‰ Phần cứng memory management phải hỗ trợ paging 
 và/hoặc segmentation 
‰ OS phải quản lý sự di chuyển của trang/đoạn giữa bộ
 nhớ chính và bộ nhớ thứ cấp
‰ Trong phạm vi chương này, chúng ta thảo luận về sự hỗ
 trợ cấp phần cứng trước, sau đó là các giải thuật của hệ
 điều hành
‰ Sự hỗ trợ của phần cứng đối với phân trang và phân
 đoạn đã được khảo sát ở chương 9. Chỉ có một điểm
 khác biệt là mỗi mục (entry) của bảng phân trang/đoạn
 có thêm các bit trạng thái đặc biệt
 – Present bit = 1⇒ hợp lệ và in-memory; = 0 ⇒ not-in-memory 
 hoặc không hợp lệ
 – Modified bit: trang/đoạn có thay đổi kể từ khi được nạp vào hay 
 không
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.33-
 Điều khiển page fault
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.34-
 17
 Kết hợp trang và đoạn
‰ Nhằm kết hợp các ưu điểm đồng thời hạn chế các khuyết điểm của
 hai mô hình phân trang và phân đoạn
‰ Có rất nhiều mô hình kết hợp. Sau đây là một mô hình đơn giản
‰ Mỗi process sẽ có: 
 – Một bảng phân đoạn
 – Nhiều bảng phân trang: mỗi phân đoạn có một bảng phân trang
‰ Một địa chỉ luận lý (địa chỉ ảo) bao gồm: 
 – segment number: là chỉ mục của một phần tử trong bảng phân đoạn, 
 phần tử này chứa địa chỉ cơ sở (base address) của bảng phân trang
 trong phân đoạn đó
 – page number: là chỉ mục trong bảng phân trang, dùng để tính ra chỉ số
 frame trong bộ nhớ thực tương ứng
 – offset: dùng để định vị một vị trí nhớ trong frame nói trên.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.35-
 Sơ đồ chuyển đổi địa chỉ
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.36-
 18
 Mô hình kết hợp đơn giản
‰ Segment Base: địa chỉ thực của bảng phân trang
‰ Present bit và modified bits chỉ tồn tại trong bảng phân
 trang
‰ Các thông tin bảo vệ và chia sẻ vùng nhớ thường nằm
 trong bảng phân đoạn
 – Ví dụ: read-only/read-write bit, ...
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.37-
 Các giải thuật của OS
‰ OS cung cấp các thư viện quản lý bộ nhớ ảo.
‰ Các chương trình quản lý bộ nhớ ảo của OS phụ thuộc
 vào sự hỗ trợ của phần cứng trong việc phân trang, 
 phân đoạn hoặc kết hợp cả hai.
‰ Rất ít hệ thống sử dụng cơ chế phân đoạn thuần túy mà
 thông thường sẽ sử dụng mô hình kết hợp trong đó các
 segment được áp dụng cơ chế phân trang. Như vậy, vấn
 đề cần giải quyết của các giải thuật nạp, thay thế,...chủ
 yếu hướng đến đối tượng là trang nhớ.
 – Fetch policy
 – Placement policy
 – Replacement policy
‰ Mục tiêu của các giải thuật này là giảm thiểu page fault
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.38-
 19
 Fetch & placement policy
‰ Fetch Policy
 – Xác định thời điểm nên nạp trang nhớ vào bộ nhớ. Có hai chiến
 lược thông dụng
 – Demand paging: chỉ nạp trang vào bộ nhớ chính khi và chỉ khi có
 tham chiếu đến trang đó (i.e.: chỉ nạp theo yêu cầu mà thôi)
 ƒ Khi process mới thực thi thì có nhiều page fault nhưng sau đó số
 page fault sẽ giảm dần
 – Pre-paging nạp trước các trang nhớ: dựa trên tính locality
‰ Placement policy
 – Xác định vị trí đặt một trang nhớ của process trong bộ nhớ thực
 – Với hệ thống segmentation thuần túy: first-fit, next fit... 
 – Với hệ thống paging hoặc kết hợp pagin/segmentation:
 ƒ Phần cứng quản lý bộ nhớ quyết định vị trí đặt trang, tuy
 nhiên vì các trang nhớ có kích thước như nhau nên không
 gặp phải khó khăn gì
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.39-
 Replacement Policy
 ‰ Giải quyết vấn đề chọn lựa một trang trong bộ nhớ
 chính sẽ bị thay thế khi có một trang mới cần nạp vào
 bộ nhớ chính. Tình huống này xảy ra khi bộ chính đầy
 (không còn frame trống nào)
 ‰ Không phải toàn bộ trang trong bộ nhớ đều có thể được
 thay, có một số frames bị locked 
 – Đa số các kernel lưu giữ các thông tin điều khiển và các cấu
 trúc dữ liệu quan trọng của hệ thống trong các locked frames 
 ‰ Các giải thuật thay thế trang
 – Least recently used (LRU)
 – First-in, first-out (FIFO)
 –Clock
 ‰ Các giải thuật thay thế trang phụ thuộc vào resident set
 (số frame cấp cho mỗi process)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.40-
 20
 Hai vấn đề chủ yếu
‰ Frame-allocation algorithm ‰ Thứ tự tham chiếu các địa chỉ
 – Cấp phát cho mỗi process bao nhớ (với page size = 100):
 nhiêu frame bộ nhớ thực? – 0100, 0432, 0101, 0612, 0102, 
 0103, 0104, 0101, 0611, 0102, 
 0103, 0104, 0101, 0610, 0102, 
‰ Page-replacement algorithm
 0103, 0104, 0101, 0609, 0102, 
 – Chọn frame sẽ được thay thế 0105
 trang nhớ
 ⇔ các trang nhớ sau được tham
 – Mong muốn có mức độ page- chiếu lần lượt = chuỗi tham
 fault nhỏ nhất
 chiếu bộ nhớ
 – Lượng giá một giải thuật bằng
 cách thực thi giải thuật trên – 1, 4, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 
 một chuỗi tham chiếu bộ nhớ 6, 1, 1, 1, 1, 6, 1, 1.
 (memory reference) và tính số
 lần xảy ra page fault
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.41-
 Quá trình thay thế trang nhớ
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.42-
 21
 Least Recently Used (LRU)
‰ Thay thế trang nhớ không được tham chiếu lâu nhất
‰ Ví dụ: một process có 5 trang; resident set = 3
‰ Mỗi trang được ghi nhận (trong bảng phân trang) thời điểm được 
tham chiếu ⇒ trang LRU là trang nhớ có giá trị thời gian tham chiếu 
nhỏ nhất (cần một chi phí tìm kiếm trang nhớ LRU này mỗi khi có page 
fault) 
‰ Do vậy, LRU cần sự hỗ trợ rất lớn của phần cứng và chi phí khá cao 
cho việc tìm kiếm. Tuy nhiên, rất ít hệ thống máy tính cung cấp đủ sự
hỗ trợ phần cứng cho chiến lược LRU
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.43-
 Giải thuật FIFO 
‰ Xem các frame được cấp phát cho process như là circular 
 buffer
 – Khi bộ đệm đầy, trang nhớ cũ nhất sẽ được thay thế: first-in, 
 first-out
 – Một trang nhớ hay được dùng thông thường sẽ là trang cũ nhất
 ⇒ hay bị thay thế bởi giải thuật FIFO
 – Hiện thực đơn giản: chỉ cần một con trỏ xoay vòng các frame 
 của process
‰ So sánh FIFO và LRU
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.44-
 22
 Belady’s Anomaly
 0Bất thường: số page-fault gia tăng khi resident set tăng
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.45-
 Giải thuật Clock (second-chance) 
‰ Resident set cấp cho mỗi process được xem như một bộ
 đệm xoay vòng (circular buffer)
‰ Khi một trang được thay, con trỏ sẽ chỉ đến frame kế
 tiếp trong buffer
‰ Mỗi frame có một use bit. Bit này được thiết lập trị 1 khi
 – Một trang được nạp lần đầu vào frame
 – Trang chứa trong frame được tham chiếu
‰ Khi cần thay thế một trang nhớ, trang nhớ nằm trên
 frame đầu tiên có use bit bằng 0 sẽ được thay thế.
 – Trong suốt quá trình tìm trang nhớ thay thế, tất cả use bit được
 reset về 0
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.46-
 23
 Ví dụ về giải thuật clock
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.47-
 So sánh Clock, FIFO và LRU
‰ Dấu *: use bit tương ứng được thiết lập trị 1
‰ Giải thuật Clock bảo vệ các trang thường được tham chiếu
 bằng cách thiết lập use bit bằng 1 với mỗi lần tham chiếu
‰ Một số kết quả thực nghiệm cho thấy clock có hiệu suất gần
 với LRU
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.48-
 24
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.49-
 Kích thước Resident Set 
‰ OS phải quyết định cấp cho mỗi process bao nhiêu
 frame bộ nhớ.
 – Nếu quá ít frame ⇒ nhiều page fault 
 – Cấp nhiều frame ⇒ giảm mức độ multi-programming
‰ Chiến lược cấp phát tĩnh (fixed-allocation)
 – Số frame cấp cho mỗi process không đổi, được xác định vào thời
 điểm loading và có thể tùy thuộc vào từng ứng dụng (kích
 thước,...)
‰ Chiến lược cấp phát động (variable-allocation)
 – Số frame cấp cho mỗi process có thể thay đổi
 ƒ Nếu tỷ lệ page-fault cao ⇒ cấp thêm frame
 ƒ Nếu tỷ lệ page-fault thấp ⇒ giảm bớt
 – OS phải mất chi phí để ước định các process
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.50-
 25
 Thrashing
‰ Nếu một process không có đủ số frame cần thiết thì tỉ
 suất page-fault rất cao. Điều này khiến giảm hiệu suất
 CPU rất nhiều
‰ Ví dụ một vòng lặp N lần, mỗi lần tham chiếu đến địa chỉ
 nằm trong 4 trang nhớ trong khi đó process chỉ được cấp
 3 frames.
‰ Thrashing ≡ hiện tượng một process bị hoán chuyển
 vào/ra liên tục các trang nhớ.
 1 1 2 3
 4 2 3
 2
 4 1 3
 3 4 1 2
 4 3 1 2
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.51-
 Thrashing Diagram
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.52-
 26
 Mô hình Locality
‰ Để hạn chế thrashing, chúng ta phải cung cấp cho
 process càng “đủ” frame càng tốt? 
 – Bao nhiêu frame thì đủ cho một process thực thi hiệu quả?
⇒ dựa trên mô hình locality 
 – Locality là một tập các trang thường hay được tham chiếu cùng
 nhau (chuỗi con tham chiếu các trang này thường xuất hiện)
 ƒ Trong ví dụ trước, locality sẽ bao gồm 4 trang
 – Một chương trình thường gồm nhiều locality và trong quá trình
 thực thi, process sẽ chuyển từ locality này sang locality khác
 ƒ Ví dụ khi một thủ tục được gọi thì sẽ có một locality mới. 
 Trong locality này, tham chiếu bộ nhớ bao gồm lệnh của thủ
 tục, biến cục bộ và một phần biến toàn cục. Khi thủ tục kết
 thúc, process sẽ thoát khỏi locality này (và có thể quay lại
 sau này).
‰ Vì sao hiện tượng thrashing xuất hiện ?
 Σ size of locality > memory size
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.53-
 Mô hình Working Set 
 ‰ Dựa trên giả thiết về locality
 ‰ Xác định xem process thực sự sử dụng bao nhiêu
 frame?
 ‰ Định nghĩa ∆≡working-set window ≡ số tham chiếu
 trang nhớ cố định. Ví dụ: 10,000 lệnh
 ‰ WSSi (working set of Process Pi) =
 tổng số trang được tham chiếu trong khoảng ∆ gần nhất
 – ∆ quá nhỏ ⇒ không đủ bao phủ toàn bộ locality.
 – ∆ quá lớn ⇒ bao phủ nhiều locality.
 – ∆ = ∞ ⇒ bao gồm toàn bộ chương trình.
 ‰ D = Σ WSSi ≡ tổng số frame yêu cầu
 – D > m (số frame của hệ thống) ⇒ xảy ra thrashing
 –NếuD > m ⇒ suspend một trong các process.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.54-
 27
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.55-
Minh họa mô hình Working-Set 
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.56-
 28
 Theo dõi các Working Set
 ‰ Dùng interval timer kết hợp với reference bit
 ‰ Ví dụ: ∆ = 10,000
 – Timer interrupt định kỳ 5000 đơn vị thời gian.
 – Giữ trong bộ nhớ 2 bit cho mỗi trang nhớ.
 – Khi timer interrupt xảy ra, copy và reset trị tất cả các reference 
 bits = 0.
 – Nếu 1 trong 2 bit trên = 1 ⇒ trang thuộc về working set.
 ‰ Cải tiến = 10 bit và interrupt timer định kỳ 1000 đơn vị
 thời gian.
 ‰ Tốn chi phí theo dõi working set và xử lý các timer định
 kỳ
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.57-
 Mô hình tần suất Page-Fault 
™ Dùng tần suất page-fault frequency để điều chỉnh mức độ page-
 fault rate.
 0 Tần suất quá thấp ⇔ process có quá nhiều frame, giảm bớt.
 0 Tần suất quá cao ⇔ process cần thêm frame.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -X.58-
 29