1
1
Nguyên lý hệđiềuhành
NguyễnHải Châu
Khoa Công nghệthông tin
Trường Đạihọc Công nghệ
2
Quản lý bộnhớ
3
Giới thiệu
zChương trình được HĐH đưa vào bộnhớ,
sau đótạo tiến trình để thực hiện
zInput queue – Là hàng chờcác tiến trình trên
đĩa đang chờ được đưa vào bộnhớ để thực
hiện
zCác chương trình của NSD phải qua một số
bước chuẩn bị trước khi được thực hiện
4
Các bước xử lý chương trình NSD
5
Chuyển đổi địa chỉ
zKhi dịch chương trình (compile-time):Sinh mã
có địa chỉcố định; phải dịch lại nếu cần thay đổi
địa chỉ.
zKhi nạp chương trình (load-time):Phải sinh
mã có thể định vịlại nếu như địa chỉbộnhớ
không được biết ởthời điểm dịch chương trình
zKhi thực hiện chương trình (execution-time):
Ánh xạ địa chỉ khi chương trình được thực hiện
nếu như tiến trình có thểchuyển giữa các
segment bộnhớ. Cần có hỗtrợtừphần cứng (ví
dụthanh ghi base và limit)
Có 3 cách chuyển đổi địa chỉlệnh và dữliệu của chương trình vào bộnhớ:
6
Không gian địa chỉlogic (ảo)
và địa chỉvật lý (địa chỉthật)
zĐể quản lý bộnhớmột cách hoàn chỉnh, cần
có hai cách nhìn địa chỉkhác nhau:
zĐịa chỉlogic (Logical address) – sinh bởiCPU;
còn gọi là địa chỉảo (virtual address).
zĐịa chỉvật lý (Physical address); còn gọi là địa chỉ
thật – sinh bởi đơn vịquản lý bộnhớ
zĐịa chỉthật và ảo giống nhau trong lược đồ
ánh xạ địa chỉ“compile-time” và “load-time”
và khác nhau trong “execution-time”.
2
7
Đơn vịquản lý bộnhớ(MMU)
zLà thiết bịphần cứng dùng để ánh xạ địa chỉ
ảo sang địa chỉvật lý
zTrong MMU, có thanh ghi relocation (định vị
lại) dùng để tính toán địa chỉthực (vật lý) từ
địa ảo của một tiến trình của NSD
zChương trình của NSD làm việc trên địa chỉ
ảo và không bao giờbiết địa chỉvật lý
8
Sửdụng thanh ghi relocation
9
Nạp chương trình động
(Dynamic loading)
zCác hàm, thủtục không được nạp cho đến
khi được sửdụng (được gọi đến)
zCách nạp động này sửdụng bộnhớhiệu quả
hơn: Các hàm, thủtục không dùng đến
không bao giờ được nạp vào bộnhớ
zHữu ích khi có một đoạn mã lớn được sử
dụng với tần suất thấp
zKhông cần có các đặc điểm đặc biệt từhệ
điều hành vềphần cứng/phần mềm
10
Liên kết động (dynamic linking) và
thư viện chung (shared library)
zLiên kết chương trình được thực hiện khi chương
trình được thực hiện.
zMột đoạn mã ngắn (stub) được dùng để định vịcác
hàm tương ứng đã được nạp sẵn trong bộnhớ
zStub được thay thếbằng địa chỉcủa hàm/thủtục
cần thiết, sau đóthực hiện hàm/thủtục đó
zHĐH cần kiểm tra các hàm/thủtục đã được nạp
chưa
zLiên kết động rất có lợi khi xây dựng các thư viện
chung, khi sửa lỗi (các miếng vá – patch)
11
Overlays
zChỉ lưu trong bộnhớcác phần lệnh và dữ
liệu phải sửdụng trong suốt quá trình thực
hiện
zSửdụng khi tiến trình có yêu cầu bộnhớlớn
hơn dung lượng được cấp phát.
zCài đặt bởi người sửdụng, lập trình overlays
rất phức tạp
12
Ví dụvềoverlays
3
13
Swapping
zSwapping: Đưa một tiến trình ra backing store để
lưu trữtạm thời, sau đó đưa trởlại bộnhớ trong để
thực hiện.
zBacking store – Vùng đĩa có tốc độ truy cập cao, đủ lớn để
chứa được nhiều tiến trình của NSD, có thểtruy cập trực
tiếp
zRoll out, roll in –Phương án swap dành cho lập lịch
có ưu tiên: Tiến trình ưu tiến thấp: roll out, ưu tiên
cao: roll in để tiếp tục thực hiện
zThời gian swap tỷlệthuận với dung lượng bộnhớ
được swap vào/ra
zUNIX, Linux, and Windows sửdụng swapping
14
Minh họa swapping
15
Cấp phát liên tục
(Contiguous allocation)
16
Cấp phát bộnhớliên tục
zBộnhớ trong thường được chia thành 2 phần:
zPhần dành cho hệ điều hành (resident) thường
dùng phần thấp của bộnhớvới các ngắt
zNSD dùng phần cao của bộnhớ. Mỗi tiến trình
được cấp phát một vùng liên tục của bộnhớ
zThanh ghi relocation dùng để bảo vệcác tiến
trình của NSD và để tránh thay đổi mã và dữ
liệu của HĐH
zThanh ghi relocation chứa giá trịnhỏnhất của
địa chỉvật lý, thanh ghi limit chứa độ lớn của
miền địa chỉảo (địa chỉảo < limit)
17
Minh họa thanh ghi relocation, limit
18
Cấp phát liên tục (tiếp): MFT
zBộnhớ được chia thành các khối với cỡcố
định, mỗi tiến trình được cấp phát một khối
zKhi tiến trình kết thúc, khối bộnhớ đã cấp
phát cho tiến trình được giải phóng để cấp
phát cho tiến trình khác
zMức độ đa chương trình bịhạn chếbởi các
khối
zCỡcủa tiến trình bịhạn chếbởi cỡcủa khối
zCác HĐH/máy tính sửdụng MFT: IBM/360
4
19
Cấp phát liên tục (tiếp): MVT
zCấp phát MVT
zHole –khối bộnhớrỗi; các khối rỗi với kích cỡkhác
nhau rải rác trong bộnhớ
zMột tiến trình sẽ được cấp phát một khối bộnhớ đủ
lớn để thực hiện
zHĐH có thông tin vềcác khối đã cấp phát và khối rỗi
HĐH
Tiến trình 5
Tiến trình 8
Tiến trình 2
HĐH
Tiến trình 5
Tiến trình 2
HĐH
Tiến trình 5
Tiến trình 2
HĐH
Tiến trình 5
Tiến trình 9
Tiến trình 2
Tiến trình 9
Tiến trình 10
20
Các chiến lược cấp phát
zFirst-fit: Cấp phát khối nhớ đầu tiên thỏa
mãn điều kiện.
zBest-fit: Cấp phát khối nhớbé nhất thỏa
mãn điều kiện: Phải duyệt toàn bộdanh sách
khối nhớ
zWorst-fit: Cấp phát khối nhớlớn nhất thỏa
mãn điều kiện: Phải duyệt toàn bộdanh sách
khối nhớ
zFirst-fit và best-fit tốt hơn worst-fit theo nghĩa
tốc độ và tận dụng bộnhớ
21
Vấn đề phân mảnh
zExternal Fragmentation (Phân mảnh ngoài): Tổng
dung lượng đáp ứng được nhu cầu cấp phát nhưng
các khối không liên tục
zInternal Fragmentation (Phân mảnh trong)–
Dung lượng bộnhớ đã cấp phát cho tiến trình
không được sửdụng hết
zGiảm phân mảnh ngoài: Compaction
zXáo trộn các khối để các khối nhớrỗi nằm liên tục
zCompaction chỉthực hiện được khi relocation là động, và
được thực hiện ởexecution-time
zVí dụ: Tiện ích Defragmentation của Windows 22
Phân trang (Paging)
23
Phân trang (paging)
zPhân trang là chiến lược cấp phát bộnhớcho phép không
gian địa chỉlogic của một tiến trình có thểkhông liên tục;
tiến trình được cấp phát bộnhớvật lý khi có bộnhớrỗi
zBộnhớvật lý được chia thành các frame cỡcố định, nhỏ
(là lũy thừa của 2, ví dụ512, 1024, 8192)
zChia bộnhớảo thành các khối cùng cỡgọi là trang (page)
zHĐH có danh sách các frame rỗi
zĐể thực hiện một chương trình cỡntrang, cần tìm nframe
rỗi để nạp chương trình
zCó một bảng trang để ánh xạtrang→frame
zBảng trang: chung trong HĐH, mỗi tiến trình có một copy 24
Cách đánh địa chỉtheo trang
zĐịa chỉ được đánh một cách phân cấp:
zSốhiệu trang (Page number -p)–Được sửdụng làm chỉsố
đến phần tửtrong bảng trang chứa địa chỉ cơ sởcủa các
frame trong bộnhớvật lý
zOffset trang (Page offset - d) – Địa chỉ tương đối trong trang
zĐịa chỉảo có mbit, sửdụng m-nbit cao làm sốhiệu
trang và nbit thấp làm offset
zKhông có phân mảnh ngoài, có phân mảnh trong:
zGiảm cỡtrang→Giảm phân mảnh trong→Giảm hiệu năng
zTăng cỡtrang→Tăng hiệu suất→Tăng phân mảnh trong
5
25
Chuyển đổi địa chỉ
26
Ví dụphân trang 1
27
Ví dụphân trang 2
Cỡcủa
một trang
là 4 bytes
28
Bảng frame rỗi
Trước cấp phát Sau cấp phát
29
Cài đặt bảng trang
zBảng trang được lưu ởbộnhớtrong
zThanh ghi cơ sởbảng trang (page-table base
register)(PTBR) trỏ đến bảng trang
zThanh ghi độ dài bảng trang (page-table
length register)(PTLR) lưu cỡbảng trang
zSửdụng bảng trang, mọi thao tác truy cập
dữliệu/lệnh cần tới 2 lần truy cập bộnhớ(1
cho bảng trang, 1 cho dữliệu/lệnh)
30
Cài đặt bảng trang (tiếp)
zTruy cập bộnhớhai lần: Giảm tốc độ
zGiải quyết vấn đề 2 lần truy cập bộnhớ: Sử
dụng phần cứng cache có tốc độ truy cập
cao gọi là bộnhớkết hợp (associative
memory) hoặc vùng đệm hỗtrợchuyển đổi
(translation look-aside buffers -TLB)
zMỗi phần tửtrong TLB có hai phần: khóa và
giá trị
zSố lượng các phần tửcủa TLB thường từ 64
đến 1024