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

ật lý giảm
 OS
 •Trade-off (thay thế) như 
 thế nào!
 Code
 •Cần hiểu đặc tính của các 
 Globals P0 Page Table
 ứng dụng
 Stack
 P1 Page Table •Bảng trang có thể rất lớn! 
 Giải pháp?
 Heap
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Một địa chỉ logic (máy 32-bit kích thước trang 
4K) được chia thành:
 Page number: 20 bits.
 Page offset: 12 bits.
Vì bảng trang lại được phân trang, page 
number lại được chia thành:
 10-bit: page number. 
 10-bit: page offset.
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Vậy, địa chỉ logic như sau:
 page number page offset
 pi p2 d
 10 10 12
Với pi là chỉ mục trong outer page table, và p2 là chỉ mục 
của một trang thuộc outer page table.
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Lược đồ chuyển đổi địa chỉ của kiến trúc phân 
trang 2 cấp 32-bit
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Vì mỗi cấp được lưu như một bảng phân biệt trong bộ nhớ, 
chuyển đổi địa chỉ logic thành địa chỉ vật lý tốn tới 4 lần truy cập 
bộ nhớ.
Caching cho phép các tính toán này khả thi.
Cache đạt 98% hit thì:
 effective access time = 0.98 x 120 + 0.02 x 520
 = 128 nanoseconds.
 Bị chậm lại chỉ có 28% trong việc truy cập bộ nhớ.
128-100 = 28 nanoseconds. Giả sử 1 truy cập bộ nhớ là 100 ns, thời gian tìm trên TLB là 
20 ns, nên nếu 1 hit trên LTB => tốn 120 ns. Còn nếu miss thì 4*100 + 20(search tren 
TLB) + 100 truy cập frame = 520ns
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
• Mục tiêu của bảng trang là để tìm ra trang vật lý tương
 ứng của từng trang ảo
• Tuy nhiên, số lượng trang ảo rất lớn kích thước bảng
 trang có thể chiếm một không gian lớn trên bộ nhớ
• Ví dụ hệ thống 64-bit địa chỉ, kích thước mỗi trang là
 4KB, vậy bảng trang cần 252 mẫu tin. Nếu mỗi mẫu tin 8
 bytes thì bảng trang chiếm 30 triệu GB.
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Mỗi mẫu tin dành cho 1 trang thật (frame) trên bộ 
nhớ.
Mỗi mẫu tin gồm địa chỉ ảo của trang, cùng với 
thông tin về tiến trình đang dùng trang này. <pid, 
p>
Giảm bộ nhớ cần thiết để lưu mỗi trang, nhưng 
tăng thời gian để tìm bảng trang.
Sử dụng CTDL bảng băm (hash table) để tăng tốc 
độ tìm kiếm.
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Nếu không gian địa chỉ ảo của một tiến trình nhỏ 
hơn bộ nhớ vật lý thì không có vấn đề gì
 Chỉ lo giải quyết vấn đề phân mảnh
Khi bộ nhớ ảo của một tiến trình lớn hơn bộ nhớ 
vật lý
 Một phần lưu trên bộ nhớ
 Một phần lưu trên đĩa
Giải quyết ntn?
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Để bắt đầu một tiến trình (chương trình), chỉ nạp trang 
chứa đoạn mã cho tiến trình bắt đầu thực thi
Khi tiến trình có yêu cầu tới vùng nhớ (chứa lệnh hay dữ 
liệu) nằm ngoài trang đã nạp, thì nạp trang đó lên
Làm sao biểu diễn một trang của máy ảo mà nó chưa nạp 
lên bộ nhớ?
 Paging Table Memory Disk
 0 A 0 1 v 0
 1 i B
 1 B 2 i 1 A
 3 C
 2 C 2
 VM
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Điều gì xảy ra khi tiến trình yêu cầu một trang bị 
đánh dấu lỗi?
 Trap lỗi trang
 Kiểm tra có phải truy xuất hợp lệ (có trang vật lý đúng)
 Tìm 1 frame bộ nhớ trống
 Đọc trang cần thiết từ bộ nhớ phụ (ổ đĩa)
 Đổi valid bit của trang thành v (hợp lệ)
 Bắt đầu lại lệnh bị ngắt bởi trap
Nếu không có frame trống thì sao?
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Các tình huống khi truy cập bộ nhớ?
 Nếu TLB miss đọc mẫu tin trong bảng trang
 Và nếu, lỗi trang (=>thay trang)
 Và nếu, tất cả các frames đang dùng cần thu hồi một 
 trang thay đổi giá trị trong bảng trang của tiến 
 trình
 Đọc trang cần thiết, cập nhật mẫu tin của bảng trang, 
 cập nhật TLB
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Trap, kiểm tra bảng trang, tìm frame trống (hoặc tìm 
trang thay thế)  khoảng 200 - 600 s
Tìm và đọc trên đĩa  khoảng 10 ms
Truy cập bộ nhớ  khoảng 100 ns
Lỗi trang làm chậm thực thi khoảng ~100,000 lần!!!!!
 Đó là chưa kể phát sinh có thể xảy ra trong các bước trên
Tốt nhất là không để xảy ra nhiều lỗi trang!
Nếu muốn sự ảnh hưởng ít hơn 10%, chỉ cho phép 1 lỗi 
trang trong 1,000,000 lần truy cập bộ nhớ
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
• Giả sử:
• 1. Có lỗi xảy ra thì tốn 8ms để thay trang
• 2. Nếu trang thay đổi nội dung thì tốn 
 20ms
• Giả sử 70% trang có thay nội dung
• Truy cập bộ nhớ tớn 100ns
• Hỏi tỉ lệ lỗi trang bao nhiêu để đảm bảo 
 EMAT không vượt quá 200ns 61
• EAT (EMAT) = (1 – p) x (thời gian truy cập 
 bộ nhớ)+ p ((thời gian phát hiện lỗi)
 + [swap page out ]
 + swap page in 
 + (thời gian restart quá trình xử lý)) 
 62
Không dễ dàng để tìm được chính sách thay thế trang tốt
 Khi thu hồi một trang, làm sao chúng ta biết là trang tốt nhất có 
 thể giảm thiểu lỗi trang sau này?
Có tồn tại thuật toán thay thế trang tối ưu?
Nếu có, thuật toán thay thế trang tối ưu là gì?
Xem ví dụ sau:
 Giả sử chúng ta có 3 frames và chạy chương trình theo mẫu sau
 7, 0, 1, 2, 0, 3, 0, 4, 2, 3
Giả sử chúng ta biết thứ tự yêu cầu trang
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Nếu không còn frame trống khi bị lỗi trang?
 Lấy lại một frame đang được sử dụng
 Chọn frame để thay thế (nạn nhân)
 Lưu trang nạn nhân vào ổ đĩa
 Cập nhật lại bảng trang (trang nạn nhân thành invalid)
 Đọc trang cần thiết vào frame vừa chọn
 Cập nhật lại bảng trang (trang vừa thay thế là valid)
 Bắt đầu lại lệnh đã gây ra lỗi trang
Tối ưu hóa: không phải ghi trang nạn nhân trở lại 
nếu như nó vẫn chưa bị thay đổi (cần thêm dirty 
bit cho mỗi trang).
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Giả sử chúng ta biết thứ tự yêu cầu trang như sau
 7, 0, 1, 2, 0, 3, 0, 4, 2, 3
Thuật toán tối ưu là thay thế trang sẽ không dùng lại 
lâu nhất
Vấn đề của thuật toán này là gì?
Giải pháp thực tế là dự đoán tương lai(sẽ yêu cầu trang 
nào) bằng quá khứ
 Có thể đúng vì tính cục bộ
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
First-in, First-out
 Công bằng, thời gian mỗi trang trên bộ nhớ gần như 
 tương đương nhau
Có vấn đề gì không?
 Có phù hợp với yêu cầu của một chương trình?
Có hiệu quả với ví dụ của chúng ta?
 7, 0, 1, 2, 0, 3, 0, 4, 2, 3
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
 Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
 3 frames (3 trang có thể đồng thờitrong bộ nhớ tại mỗi thời 
 điểm)
 1 1 4 5
 2 2 1 3 9 page faults
 3 3 2 4
 4 frames
 1 1 5 4
 2 2 1 5 10 page faults
 3 3 2
 4 4 3
 Belady’s Anomaly: more frames more page faults
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Least Recently Used (ít sử dụng gần đây nhất)
 Mỗi lần truy cập trang, dán nhãn thời gian lại
 Khi cần thu hồi một trang, chọn trang với nhãn thời 
 gian lâu nhất
LRU có phải tối ưu nhất?
 Trong thực tế, LRU là giải pháp tốt cho hầu hết chương 
 trình
Có dễ dàng cài đặt?
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Dùng 1 reference bit và bộ đếm cho mỗi trang (frame)
Mỗi ngắt đồng hồ, HĐH cộng reference bit vào biến counter rồi 
xóa reference bit (bật reference bit nếu trang được sử dụng)
Khi cần thay trang, chọn trang có số đếm ít nhất
Có vấn đề gì không?
 Lưu vết tất cả, khó thu hồi trang đã dùng rất nhiều trong quá khứ, 
 nhưng hiện tại không còn dùng nữa
 Chi phí cao để quản lý counter, bởi vì bộ nhớ ngày càng lớn
Có thể cải tiến bằng lược đồ độ tuổi: counter được shift qua phải 
trước khi cộng reference bit và reference bit được cộng vào bit 
trái nhất
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Sắp xếp các trang thành vòng tròn, và dùng 1 đồng hồ
Dùng 1 use bit cho mỗi frame. Bật use bit lên khi mà 
frame đó được dùng.
 Nếu use bit = 0, trang không sử dụng
Khi lỗi trang:
 Di chuyển kim đồng hồ
 Kiểm tra use bit
 If 1, mới sử dụng, xóa và tiếp tục
 If 0, chọn trang này để thay thế
Liệu chúng ta có thể luôn tìm được trang để thay thế?
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Tương tự ý tưởng trên nhưng,
Dùng 1 counter và 1 use bit
Khi lỗi trang:
 Dịch kim đồng hồ
 Kiểm tra use bit
 If 1, xóa use bit và đặt counter = 0
 If 0, tăng counter, if counter < N, tiếp tục, ngược lại chọn trang này để thay thế
Nhận xét
 N lớn gần giống kết quả với LRU
Nếu N quá lớn thì gặp vấn đề gì?
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Luôn giữ một danh sách n > 0 trang trống
 Khi lỗi trang, nếu danh sách trống có hơn n frames, 
 chọn 1 frame từ danh sách trống
 Nếu danh sách trống chỉ có n frames, chọn 1 frame từ 
 danh sách, rồi chọn một frame đang sử dụng để đặt 
 vào danh sách trống
Khi lỗi trang, nếu trang lỗi là trong danh sách 
trống, không phải đọc lại trang đó lên bộ nhớ.
Triển khai trên VAX  hiệu quả gần đạt LRU
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Vì sao?
 Tận dụng tốt hơn resource (CPU, disks, memory, etc.)
Bài toán?
 Caching – TLB?
 Sự công bằng?
 Bộ nhớ giới hạn
Các vấn đề có thể phát sinh?
 Mỗi tiến trình cần một tập các trang(working set) để thực thi
 Nếu quá nhiều tiến trình thực thi, có thể trì trệ vì thay trang 
 (thrash)
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
 Trì trệ (thrashing): hệ thống chỉ bận rộn cho việc 
 thay trang
 Khi nào xảy ra sự trì trệ?
 kích thước working sets > tổng kích thước bộ 
 nhớ
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Nhiều không gian địa chỉ tiến trình có thể được nạp lên bộ 
nhớ
Thanh ghi trỏ tới bảng trang hiện tại
HĐH phải cập nhật lại thanh ghi khi context switching giữa 
các tiểu trình khác tiến trình
Đa số TLBs có thể cache nhiều bảng trang
 Lưu thêm process id để phân biệt địa chỉ logic thuộc các tiến trình 
 khác nhau
Nếu TLB chỉ caches 1 bảng trang thì nó phải xóa hết bảng 
trang khi context switch.
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
 virtual address spaces
 p1 p2
 processes:
 v-to-p memory mappings
 physical memory:
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
 p1 p2 p1 p2
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Một tiến trình nên nạp bao nhiêu trang lên bộ nhớ ?
Số lượng trang thường trú này có thể cố định hoặc thay 
đổi
Miền thay thế là cục bộ hay toàn cục
Lược đồ hay được sử dụng:
 Thay trang toàn cục: đơn giản – kích thước tập trang thường 
 trú của tiến trình thay đổi mỗi lẫn thay trang
 Thay trang cục bộ: phức tạp hơn – kích thước tập trang 
 thường trú phải thay đổi xung quanh giá trị kích thước tập 
 trang thường trú của tiến trình (working set size)
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Là một tập các trang được sử dụng trong khoảng thời gian 
gần đây nhất
Kích thước của working set có thể thay đổi trong suốt quá 
trình thực thi của tiến trình
Nếu số lượng trang được cấp nhiều hơn working set thì số 
lỗi trang sẽ nhỏ
Chỉ điều phối cho tiến trình khi mà bộ nhớ đủ để nạp 
working set của nó
Làm sao để xác định/(xấp xỉ) kích thước của working set?
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
 working-set window số trang được gọi 
Ví dụ: = 10,000 lệnh
WSSi (working set của tiến trình Pi) =
tổng số trang được gọi trong khoảng tgian vừa rồi(có thể thay 
đổi)
 if quá nhỏ thì không đủ chứa tập trang thường trú.
 if quá lớn thì có thể chứa nhiều tập trang thường trú.
 if = sẽ chứa tập trang toàn chương trình.
D = WSSi tổng trang được yêu cầu 
if D > m Trì trệ (Thrashing)
Chính sách if D > m, thì dừng một tiến trình.
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Xấp xỉ khoảng thời gian + dùng một reference bit
Ví dụ: = 10,000
 Đồng hồ ngắt sau mỗi 5000 đơn vị.
 Dùng 2 reference bít cho mỗi trang.
 Mỗi lần đồng hồ ngắt, thì lưu lại và gán lại giá trị 0 cho cả 2 
 reference bit.
 Nếu 1 bit = 1 trang trong working set.
Tại sao không thật sự chính xác?
Cải tiến = dùng 10 bits và ngắt mỗi 1000 đơn vị.
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
 Xác định tầng suất lỗi trang chấp nhận được.
 Nếu tỉ lệ lỗi trang nhỏ, tiến trình bỏ bớt frame.
 Nếu tỉ lệ lỗi trang cao, tiến trình cấp thêm frame.
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Một bộ đếm cho mỗi trang để đếm “thời gian” giữa các lỗi 
trang(“thời gian” = có thể là số lần trang được truy cập)
Định nghĩa một ngưỡng trên cho biến “thời gian”
Nếu thời gian giữa 2 lỗi trang nhỏ hơn ngưỡng trên, thì 
trang được thêm vào tập thường trú
Và cũng cần một ngưỡng dưới để giảm bớt khung trang 
của tiến trình
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Cấu trúc chương trình
 Mãng A[1024, 1024] số nguyên
 Mỗi dòng lưu trên một trang
 Một frame 
 Chương trình 1 for j := 1 to 1024 do
 for i := 1 to 1024 do
 A[i,j] := 0;
 1024 x 1024 lỗi trang 
 Chương trình 2 for i := 1 to 1024 do
 for j := 1 to 1024 do
 A[i,j] := 0;
 1024 lỗi trang
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Lược đồ quản lý bộ nhớ cho phép người dùng thấy được bộ 
nhớ. 
Một chương trình là một tập các đoạn. Một đoạn là một 
đơn vị logic, như là:
 main program,
 procedure, 
 function,
 local variables, global variables,
 common block,
 stack,
 symbol table, arrays
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
 1
 4
 1
 2
 3 2
 4
 3
 Không gian người dùng Không gian vật lý
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Địa chỉ logic bao gồm 2 tham số: <segment-number, 
offset>
Segment table – ánh xạ địa chỉ vật lý; mỗi mục tin trên 
bảng lưu:
 base – lưu địa chỉ vật lý bắt đầu trên bộ nhớ.
 limit – xác định chiều dài của đoạn.
Segment-table base register (STBR) lưu vị trí của segment 
table trên bộ nhớ.
Segment-table length register (STLR) lưu số segment được 
sử dụng bởi người dùng; segment s là hợp lệ nếu s < 
STLR.
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Chia lại vùng nhớ.
 Động
 Thông qua segment table 
Chia sẻ.
 Chia sẻ các đoạn
 Cùng số segment 
Cấp phát.
 first fit/best fit
 Phân mảnh ngoài
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Bảo vệ. Mỗi mục tin trong segment table có thêm:
 validation bit = 0 segment không hợp lệ
 Quyền read/write/execute
Các bit bảo vệ gán với các segments
Bởi vì các đoạn độ dài khác nhau, cấp phát bộ nhớ 
là bài toán cấp phát vùng nhớ động.
Một ví dụ phân đoạn
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
The MULTICS giải quyết bài toán phân mảnh ngoại 
vi và tìm kiếm các đoạn bằng cách phân trang các 
đoạn.
Giải pháp là: mẫu tin của segment-table không lưu 
địa chỉ base của segment, mà lưu địa chỉ base của 
page table cho segment này.
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM
Bộ nhớ ảo tạo thành một lớp riêng biệt trong mô hình bộ nhớ đa
cấp của chúng ta, để biểu diễn dung lượng bộ nhớ thật sự của
hệ thống
 Điều này rất quan trọng “dễ dàng để lập trình”
 Hình dung bài toán phải kiểm tra cụ thể về kích thước vật lý của 
 bộ nhớ và quản lý nó cho mỗi chương trình cụ thể đang thực thi
Hữu dụng cho việc ngăn chặn phân mảnh trong môi trường đa 
chương
Có thể cài đặt bằng phân trang (phân đoạn, hoặc cả hai)
Lỗi trang chi phí khá lớn,
 Cần có chính sách thay thế trang thật tốt
Phải cẩn thận vấn đề trì trệ hệ thống (thrashing)!!
ĐH KHTN 
 TH 106: Hệ điều hành
TpHCM