Giáo trình Hệ điều hành (Operating System)

i câu hỏi tương tự câu a 
int A [100][100] ; 
for (j=0; j<100; j++) 
for (i=0; i<100; i++) A[i][j]= 0; 
HD: 
a) mỗi dòng một trang nên có 100 lỗi 
b) 10000 lỗi 
3. Trong một hệ thống sử dụng kỹ thuật phân trang theo yêu cầu, kích thước mỗi trang là 2K , xét 
đoạn chương trình C sau đây: 
int n = 3*1024; int A[n], B[n]; 
for (i=0; i<n;i++) A[i]=i; 
for (i=0 ;i<n;i++) B[A[i]]=i; 
 194
a) Nếu số khung cấp cho tiến trình là không hạn chế và giả sử khung trang thứ nhất luôn dùng để 
chưá tiến trình, các khung trang còn lại được khởi động ở trạng thái trống thì tiến trình có bao 
nhiêu lỗi trang. 
b) Nếu số khung cấp cho tiến trình là 2 khung và giả sử khung trang thứ nhất luôn dùng để chưá 
tiến trình, khung trang thứ hai được khởi động ở trạng thái trống thì tiến trình có bao nhiêu lỗi 
trang. 
HD: 
a) Mảng A có kích thước là 6K => cần 3 trang, mỗi trang chứa 1024 phần tử liên tiếp. 
Cứ truy xuất 1024 pt của mảng A sẽ sinh ra một lỗi trang => vòng for thứ 1 sinh ra 3 lỗi trang. Lý 
luận tương tự vòng for thứ 2 sinh ra 3 lỗi trang. Vậy tiến trình có 6 lỗi trang 
b) Số lỗi trang là: 3+2*3*1024= 6147 lỗi trang 
4. Một máy tính có 4 khung trang. Thời điểm nạp, thời điểm truy cập cuối cùng, và các bit 
Reference (R), Dirty (D) của mỗi trang trong bộ nhớ được cho trong bảng sau : 
Trang Thời điểm nạp Thời điểm truy cập cuối cùng R D 
0 126 279 0 0 
1 230 260 1 0 
2 120 272 1 1 
3 160 280 1 1 
Trang nào sẽ được chọn thay thế theo : 
a) thuật toán NRU 
b) thuật toán FIFO 
c) thuật toán LRU 
d) thuật toán " cơ hội thứ 2" 
HD: 
trang 0 
trang 2 
trang 1 
trang 0 
 195
5. Tính kích thước dãy bít dùng để quản lý RAM 512 MB, giả sử địa chỉ đánh theo byte. 
HD: 512 MB=512*1024*1024 bytes = 229 bytes. Mỗi một byte dùng 1 bit để quản lý => kích 
thứơc dãy bít sử dụng là 229/8/1024/1024 MB = 64 MB. 
6. Xét một không gian địa chỉ có 8 trang, mỗi trang có kích thước 1K, ánh xạ vào bộ nhớ vật lý có 
32 khung trang. 
a) Địa chỉ logic gồm bao nhiêu bit ? 
b) Địa chỉ physic gồm bao nhiêu bit ? 
HD: 
a) 8 trang => p= 3 bit. Kích thước trang 1 K =>d=10 bit=> đc logic= p+d=13 bit 
b) đc vật lý có 32 khung => đcvl=32 K= 215 bytes => dcvl=15 bit 
7. Xét một hệ thống sử dụng kỹ thuật phân trang, với bảng trang được lưu trữ trong bộ nhớ chính. 
a) Nếu thời gian cho một lần truy xuất bộ nhớ bình thường là 200 nanoseconds, thì mất bao nhiêu 
thời gian cho một thao tác truy xuất bộ nhớ trong hệ thống này ? 
b) Nếu sử dụng TLBs với tỉ lệ tìm thấy (hit-ratio) là 75%, thời gian để tìm trong TLBs xem như 
bằng 0, tính thời gian truy xuất bộ nhớ trong hệ thống ( effective memory reference time) 
HD: 
a) 200+200=400 nanoseconds 
b) 200*0.25+200= 250 nanoseconds 
8. Xét bảng phân đoạn sau: 
Segment Base Length
1 2300 14 
2 90 100 
Cho biết địa chỉ vật lý tương ứng với các địa chỉ ảo sau đây : 
a. (1,10) 
b. (2,500) 
HD: đc logic=(s,d) 
s=1, d=10, base(1)=2300 => đcvl=2300+10=2310 
s=2, d=500, d>length(2)=100 => lỗi truy xuất đc không hợp lệ 
9. Một máy tính 32-bit địa chỉ, sử dụng một bảng trang nhị cấp. Địa chỉ ảo được phân bổ như sau: 
9 bit dành cho bảng trang cấp 1, 11 bit cho bảng trang cấp 2, còn lại dành cho offset. Cho biết 
kích thước một trang trong hệ thống, và không gian địa chỉ ảo có bao nhiêu trang ? 
HD: 
 196
Đc ảo = (p1,p2,d) =32 bit 
p1=9, p2=11 => d=12 bit => kt 1 trang= 212 bytes = 4 KB 
Số trang trong kg đc ảo = 29 x 211 = 220 trang 
10. Một máy tính có 48-bit địa chỉ ảo, và 32-bit địa chỉ vật lý, kích thước một trang là 8K. Có bao 
nhiêu phần tử trong một bảng trang thông thường và trong bảng trang nghịch đảo? 
HD: 
a) Bảng trang thông thường 
kt trang = 8 K = 213 bytes => d=13 bit => p=35 bit 
=> một bảng trang thông thường có 235 phần tử 
b) Bảng trang nghịch đảo 
1 khung trang = 8K =213 bytes 
ktbnvl = 232 bytes => số khung trang của bnvl= 232/213 = 219 khung 
=> số phần tử trong bảng trang nghịch đảo là 219 
11. Giả sử có một máy tính đồ chơi sử dụng 7-bit địa chỉ, hệ thống sử dụng một bảng trang nhị 
cấp, dùng 2-bit làm chỉ mục đến bảng trang cấp 1, 2-bit làm chỉ mục đến bảng trang cấp 2. Xét 
một tiến trình sử dụng các địa chỉ ảo trong những phạm vi sau : 0..15, 21..29, 94..106, và 
115..127. 
a) Vẽ chi tiết toàn bộ bảng trang cho tiến trình này 
b) Phải cấp phát cho tiến trình bao nhiêu khung trang, giả sử tất cả đều nằm trong bộ nhớ chính? 
c) Bao nhiêu bytes ứng với các vùng phân mảnh nội vi trong tiến trình này? 
d) Cần bao nhiêu bộ nhớ cho bảng trang của tiến trình này? 
HD: 
đc ảo = (p1,p2,d)=7 bit 
p1=p2=2 bit=> d=3 bit => kt trang=8 bytes 
a) vẽ bảng trang : goi fi là số hiệu khung trang chứa trang pi 
b) cấp 9 khung + 4 =13 khung 
C1 
f0 
f1 
f2 
f3 
C2 
f11 
C2 
f12 
f13 
f14 
f15 
C2 
p13 
p14 
p0 
p3 
p11 
p2 
p12 
p1 
p15 
bnvl 
0 00.00.000 (0,0,0) 
15 00.01.111 (0,1,7) 
21 00.10.101 (0,2,5) 
29 00.11.101 (0,3,5) 
94 10.11.110 (2,3,6) 
106 11.01.010 (3,1,2) 
115 11.10.011 (3,2,3) 
127 11.11.111 (3,3,7) 
Tiến trình sử dụng các địa chỉ ảo trong các 
phạm vi sau: 
(0,0,0)..(0,1,7); (0,2,5)..(0,3,5); 
(2,3,6)..(3,1,2); (3,2,3)..(3,3,7) 
 197
c) tính phân mảnh nội vi: 
khung trang cấp cho trang 0 và trang 1 được sử dụng hết 
khung trang cấp cho trang 2 dư 21-16 byte=5 byte đầu 
tương tự tính phân mảnh cho các trang còn lại 
kích thước bảng trang cho tiến trình này 
d) dùng 1 bảng trang cấp 1, 3 bảng trang cấp 2 => kích thước bảng trang = 4 khung trang = 32 
bytes 
12. Giả sử có một máy tính sử dụng 16-bit địa chỉ. Bộ nhớ ảo được thực hiện với kỹ thuật phân 
đoạn kết hợp phân trang, kích thước tối đa của một phân đoạn là 4096 bytes. Bộ nhớ vật lý được 
phân thành các khung trang có kích thước 512 bytes. 
a) Thể hiện cách địa chỉ ảo được phân tích để phản ánh segment, page, offset 
b) Xét một tiến trình sử dụng các miền địa chỉ sau, xác định số hiệu segment và số hiệu page 
tương ứng trong segment mà chương trình truy cập đến : 
350..1039, 3046..3904, 7100..9450, 33056..39200, 61230..63500 
c) Bao nhiêu bytes ứng với các vùng phân mảnh nội vi trong tiến trình này? 
d) Cần bao nhiêu bộ nhớ cho bảng phân đoạn và bảng trang của tiến trình này ? 
HD: 
a) đc ảo= (s,d)=(s,p,d’)=16 bit, với d=p+d’ 
kt khung trang=512 => d’=9 bit 
kích thước tối đa của 1 phân đoạn là 4096 bytes => một phân đoạn được chia tối đa thành 
4096/512 = 8 trang =>p=3 bit =>d=12 bit => s=4 bit => dc ảo=(s,p,d’)=(4,3,9) 
b) Tiến trình sử dụng các miền địa chỉ ảo sau: 
350 0000.000.101011110 (0,0,350) 
1039 0000.010.000001111 (0,2,15) 
3046 0000.101.111100110 (0,5,486) 
3904 0000.111.101000000 (0,7,320) 
7100 0001.101.110111100 (1,5,444) 
9450 0010.010.011101010 (2,2,234) 
33056 1000.000.100100000 (8,0,288) 
39200 1001.100.100100000 (9,4,288) 
61230 1110.111.100101110 (14,7,302) 
63500 1111.100.000001100 (15,4,12) 
c) tính phân mảnh nội vi: 
s=0,p=0 dư: 350 byte đầu 
s=0, p=2 dư: 512-15=497 byte cuối 
vv… 
(0,0,350)..(0,2,15);(0,5,486)..(0,7,320); 
(1,5,444)..(2,2,234); 
(8,0,288)..(9,4,288); (14,7,302)..(15,4,12) 
=> 
s=0: p=0,1,2,5,6,7 
s=1: p=5,6,7 
s=2: p=0,1,2 
s=8: p=0,1,2,3,4,5,6,7 
s=9: p=0,1,2,3,4 
s=14: p=7 
s=15: p=0,1,2,3,4 
 198
d) Tiến trình dùng 1 bảng phân đoạn => bộ nhớ dành cho bảng phân đoạn= 512 byte. 
Tiến trình có 16 phân đoạn =>số bảng trang tiến trình sử dụng là 16=> bộ nhớ dành cho bảng 
trang= 16*512 (giả sử một bảng trang chiếm 1 khung trang) 
 TÀI LIỆU THAM KHẢO 
[1]. Gary J. Nutt, University of Colorado. Centralized And Distributed Operating Systems. 
Second Edition, 2000. 
[2]. Robert Switzer. Operating Systems, A Practical Approach. Prentice-Hall International, Inc. 
1993. 
[3]. Andrew S. Tanenbaum. Modern Operating Systems. Prentice-Hall International, Inc. Second 
Edition, 2001. 
[4]. Abraham Silberschatz & Peter Baer Galvin. Operating System concepts. John Wiley & Sons, 
Inc. Fifth Edition, 1999. 
[5]. H. M. Deitel. Operating Systems. Addison-Wesley Inc. Second Edition, 1999. 
[6]. Trần Hạnh Nhi & Lê Khắc Nhiên Ân & Hoàng Kiếm. Giáo trình hệ điều hành (tập 1 & 2). 
ĐHKHTN 2000. 
 199
MỤC LỤC 
CHƯƠNG I: GIỚI THIỆU VỀ HỆ ĐIỀU HÀNH Trang 
1.1 Hệ điều hành là gì, các khái niệm của hệ điều hành. 3 
1.2 Lịch sử phát triển của hệ điều hành 4 
1.3 Các loại hệ điều hành 4 
1.4 Các dịch vụ của hệ điều hành 8 
1.5 Cấu trúc của hệ điều hành 11 
1.6 Nguyên lý thiết kế hệ điều hành 14 
CHƯƠNG II: QUẢN LÝ NHẬP/XUẤT VÀ QUẢN LÝ HỆ THỐNG TẬP TIN 
2.1. Quản lý nhập/xuất 16 
2.1.1 Phân loại và đặc tính của thiết bị nhập/xuất 16 
2.1.2 Bộ điều khiển thiết bị nhập/xuất 17 
2.1.3 Các chương trình thực hiện nhập/xuất và tổ chức hệ thống nhập/xuất 18 
2.1.4 Cơ chế nhập/xuất và cơ chế DMA 20 
2.1.5 Các thuật toán lập lịch di chuyển đầu đọc 20 
2.1.6 Hệ số đan xen và ram disk 22 
2.2 Quản lý hệ thống tập tin 23 
2.2.1 Các khái niệm về đĩa cứng, tập tin, thư mục, bảng thư mục 23 
2.2.2 Các phương pháp cài đặt hệ thống tập tin. 28 
2.2.3 Phương pháp quản lý danh sách các khối trống 32 
2.2.4 Phương pháp quản lý sự an toàn của hệ thống tập tin 33 
2.2.5 Giới thiệu một số hệ thống tập tin: MSDOS/Windows, UNIX. 34 
CHƯƠNG III: QUẢN LÝ TIẾN TRÌNH 
3.1 Các khái niệm vể tiến trình 44 
3.2 Điều phối các tiến trình 53 
3.3 Liên lạc giữa các tiến trình 61 
3.4 Đồng bộ các tiến trình 66 
3.5 Tính trạng tắc nghẽn (deadlock) 80 
CHƯƠNG IV: QUẢN LÝ BỘ NHỚ 
4.1 Các vấn đề phát sinh khi quản lý bộ nhớ. 99 
4.2 Các mô hình cấp phát bộ nhớ. 101 
4.3 Bộ nhớ ảo 116 
 200
CHƯƠNG V: QUẢN LÝ PROCESSOR 
5.1 Processor Vật lý và Processor logic 130 
5.2 Ngắt và xử lý ngắt 131 
5.3 Xử lý ngắt trong IBM-PC 136 
CHƯƠNG VI: HỆ ĐIỀU HÀNH NHIỀU BỘ VI XỬ LÝ 
6.1 Cấu hình nhiều processor 140 
6.2 Các loại hệ điều hành hỗ trợ nhiều bộ vi xử lý 146 
6.3 Đồng bộ trong hệ thống đa xử lý 149 
6.4 Điều phối trong hệ thống đa xử lý 152 
- HẾT -