Bài giảng Hệ điều hành - Ôn tập cuối kỳ

HỆ ĐIỀU HÀNH
ÔN TẬP CUỐI KỲ
01/6/2017
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 1
Câu hỏi ôn tập chương 5
 Khi nào thì xảy ra tranh chấp race condition?
 Vấn đề Critical Section là gì?
 Yêu cầu của lời giải cho CS problem?
 Có mấy loại giải pháp? Kể tên?
11/2/2017 2Copyrights 2017 CE-UIT. All Rights Reserved.
Câu hỏi ôn tập chương 5 (tt)
 Semaphore là gì? Nêu cách hoạt động của semaphore và ứng
dụng vào một bài toán đồng bộ?
 Monitor là gì? Nêu cách hoạt động của monitor và ứng dụng
vào một bài toán đồng bộ?
11/2/2017 3Copyrights 2017 CE-UIT. All Rights Reserved.
BÀI TẬP CHƯƠNG 5
11/2/2017 4Copyrights 2017 CE-UIT. All Rights Reserved.
Bài tập 1
 Xét giải pháp phần mềm do Dekker đề nghị để tổ chức truy xuất độc quyền cho
2 tiến trình. Hai tiến trình P0 và P1 chia sẻ các biến sau:
 Var flag : array [0..1] of Boolean; (khởi động là false)
 Turn : 0..1;
 Cấu trúc một tiến trình Pi ( i=0 hay 1, và j là tiến trình còn lại như sau:
repeat
flag[i] := true;
while flag[j] do
if turn = j then
begin flag[i]:= false;
while turn = j do ;
flag[i]:= true;
end;
critical_section();
turn:= j;
flag[i]:= false;
non_critical_section();
until false;
11/2/2017 5Copyrights 2017 CE-UIT. All Rights Reserved.
Giải pháp này có thỏa 3 
yêu cầu trong việc giải 
quyết tranh chấp không?
Bài tập 2
 Xét giải pháp đồng bộ hóa sau:
while (TRUE) {
int j = 1-i;
flag[i]= TRUE;
turn = i;
while (turn == j && flag[j]==TRUE);
critical-section ();
flag[i] = FALSE;
Noncritical-section ();
}
11/2/2017 6Copyrights 2017 CE-UIT. All Rights Reserved.
Giải pháp này có thỏa yêu cầu độc quyền truy xuất không?
Bài tập 4
 Xét hai tiến trình sau:
process A {while (TRUE) na = na +1; }
process B {while (TRUE) nb = nb +1; }
a. Đồng bộ hóa xử lý của 2 tiến trình trên, sử dụng 2 semaphore
tổng quát, sao cho tại bất kỳ thời điểm nào cũng có nb <= na <=
nb +10
b. Nếu giảm điều kiện chỉ có là na <= nb +10, giải pháp của bạn sẽ
được sửa chữa như thế nào?
c. Giải pháp của bạn có còn đúng nếu có nhiều tiến trình loại A và
B cùng thực hiện?
11/2/2017 7Copyrights 2017 CE-UIT. All Rights Reserved.
Bài tập 5
 Một biến X được chia sẻ bởi 2 tiến trình cùng thực hiện đoạn
code sau :
do
X = X +1;
if ( X == 20) X = 0;
while ( TRUE );
 Bắt đầu với giá trị X = 0, chứng tỏ rằng giá trị X có thể vượt quá
20. Cần sửa chữa đoạn chương trình trên như thế nào để đảm bảo
X không vượt quá 10?
11/2/2017 8Copyrights 2017 CE-UIT. All Rights Reserved.
Bài tập 6
 Xét 2 tiến trình xử lý đoạn chương trình sau:
process P1 { A1 ; A2 }
process P2 { B1 ; B2 }
Đồng bộ hóa hoạt động của 2 tiến trình này sao cho cả A1 và
B1 đều hoàn tất trước khi A2 và B2 bắt đầu
11/2/2017 9Copyrights 2017 CE-UIT. All Rights Reserved.
Bài tập 7
 Tổng quát hóa câu hỏi 6 cho các tiến trình có đoạn chương
trình sau:
process P1 { for ( i = 1; i <= 100; i ++) Ai }
process P2 { for ( j = 1; j <= 100; j ++) Bj }
Đồng bộ hóa hoạt động của 2 tiến trình này sao cho với k bất kỳ
(2<=k<=100), Ak chỉ có thể bắt đầu khi B(k-1) đã kết thúc và Bk
chỉ có thể bắt đầu khi A(k-1) đã kết thúc.
11/2/2017 10Copyrights 2017 CE-UIT. All Rights Reserved.
Bài tập 8
 Sử dụng semaphore để viết lại chương trình sau theo mô
hình xử lý đồng hành:
w := x1 * x2
v := x3 * x4
y := v * x5
z := v * x6
x := w * y
z := w * z
ans := y + z
11/2/2017 11Copyrights 2017 CE-UIT. All Rights Reserved.
Câu hỏi ôn tập chương 6
 Deadlock là gì? Cho ví dụ trong thực tế?
 Một tiến trình khi nào gọi là bị deadlock? trì hoãn vô hạn
định?
 Khi nào sẽ xảy ra deadlock?
 Các phương pháp giải quyết deadlock?
 Làm gì để ngăn deadlock?
 Làm gì để tránh deadlock?
11/2/2017 12Copyrights 2017 CE-UIT. All Rights Reserved.
Câu hỏi ôn tập chương 6 (tt)
 Nêu điều kiện để thực hiện giải thuật Banker?
 Nêu các bước của giải thuật Banker?
 Nêu các bước của giải thuật yêu cầu tài nguyên?
 Nêu các bước giải thuật phát hiện deadlock?
 Khi deadlock xảy ra, hệ điều hành làm gì để phục hồi?
 Dựa trên yếu tổ nào để chấm dứt quá trình bị deadlock?
11/2/2017 13Copyrights 2017 CE-UIT. All Rights Reserved.
BÀI TẬP CHƯƠNG 6
11/2/2017 14Copyrights 2017 CE-UIT. All Rights Reserved.
Bài tập 1
 Cho 1 hệ thống có 4 tiến trình P1 đến P4 và 3 loại tài nguyên
R1 (3), R2 (2) R3 (2). P1 giữ 1 R1 và yêu cầu 1 R2; P2 giữ 2
R2 và yêu cầu 1 R1 và 1 R3; P3 giữ 1 R1 và yêu cầu 1 R2;
P4 giữ 2 R3 và yêu cầu 1 R1
 Vẽ đồ thị tài nguyên cho hệ thống này?
 Deadlock?
 Chuỗi an toàn? (nếu có)
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 15
Bài tập 2
 Tìm Need?
 Hệ thống có an toàn không?
 Nếu P1 yêu cầu (0,4,2,0) thì có thể cấp phát cho nó ngay không?
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 16
Bài tập 3
 Sử dụng thuật toán Banker xem các trạng thái sau có an toàn hay
không? Nếu có thì đưa ra chuỗi thực thi an toàn, nếu không thì
nêu rõ lý do không an toàn?
a. Available = (0,3,0,1)
b. Available = (1,0,0,2)
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 17
Bài tập 4
 Trả lời các câu hỏi sau sử dụng giải thuật Banker
a. Hệ thống có an toàn không? Đưa ra chuỗi an toàn nếu có?
b. Nếu P1 yêu cầu (1,1,0,0) thì có thể cấp phát cho nó ngay không?
c. Nếu P4 yêu cầu (0,0,2,0) thì có thể cấp phát cho nó ngay không
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 18
Câu hỏi ôn tập chương 7
 Chuyển đổi địa chỉ là gì? Địa chỉ nhớ được biểu diễn như thế
nào trong quá trình chạy 1 chương trình?
 Khi nào địa chỉ lệnh và dữ liệu được chuyển thành địa chỉ
thật?
 Thế nào là dynamic linking? Nêu ưu điểm?
 Thế nào là dynamic loading?
 Nêu cơ chế overlay? Swapping?
 Nêu các mô hình quản lý bộ nhớ?
11/2/2017 19Copyrights 2017 CE-UIT. All Rights Reserved.
Câu hỏi ôn tập chương 7 (tt)
 Thế nào là phân mảnh ngoại? Phân mảnh nội? Cho ví dụ?
 Fixed partitioning là gì? Các chiến lược placement?
 Dynamic partitioning là gì? Các chiến lược placement?
11/2/2017 20Copyrights 2017 CE-UIT. All Rights Reserved.
Câu hỏi ôn tập chương 7 (tt)
 Giả sử bộ nhớ chính được cấp phát các phân vùng có kích
thước là 600K, 500K, 200K, 300K (theo thứ tự), sau khi thực
thi xong, các tiến trình có kích thước 212K, 417K, 112K,
426K (theo thứ tự) sẽ được cấp phát bộ nhớ như thế nào, nếu
sử dụng: Thuật toán First fit, Best fit, Next fit, Worst fit?
Thuật toán nào cho phép sử dụng bộ nhớ hiệu quả nhất trong
trường hợp trên
11/2/2017 21Copyrights 2017 CE-UIT. All Rights Reserved.
Bài tập 1
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 22
Xét một không gian địa chỉ có 12 trang, mỗi trang có kích
thước 2K, ánh xạ vào bộ nhớ vật lý có 32 khung trang.
Địaa. chỉ logic gồm bao nhiêu bit?
Địab. chỉ physic gồm bao nhiêu bit?
Bảngc. trang có bao nhiêu mục? Mỗi mục trong bảng trang
cần bao nhiêu bit?
Bài tập 2
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 23
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à
200ns 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 hit-ratio là 75%, thời gian để tìm
tròn TLBs xem như bằng 0, tính thời gian truy xuất bộ nhớ
trong hệ thống
Bài tập 3
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 24
Xét bảng phân đoạn trong hình
Tính địa chỉ vật lý tương ứng với các địa chỉ logic sau đây:
a. 0.430
b. 1.10
c. 2.500
d. 3.400
e. 4.112
Bài tập 4
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 25
Xét một không gian có bộ nhớ luận lý có 64 trang, mỗi trang có
1024 từ, mỗi từ là 2 byte được ánh xạ vào bộ nhớ vật lý có 32
trang:
a) Địa chỉ bộ nhớ vật lý có bao nhiêu bit?
b) Địa chỉ bộ nhớ luận lý có bao nhiêu bit?
c) Có bao nhiêu mục trong bảng phân trang? Mỗi mục chứa bao
nhiêu bit?
Câu hỏi ôn tập chương 8
1. Tại sao cần phải có bộ nhớ ảo?
2. Có bao nhiêu kỹ thuật cài đặt bộ nhớ ảo? Mô tả sơ lượt các
kỹ thuật đó?
3. Các bước thực hiện kỹ thuật phân trang theo yêu cầu?
4. Mô tả các giải thuật thay thế trang FIFO, OPT, LRU?
5. Giải pháp tập làm việc hoạt động như thế nào?
11/2/2017 26Copyrights 2017 CE-UIT. All Rights Reserved.
BÀI TẬP CHƯƠNG 8
11/2/2017 27Copyrights 2017 CE-UIT. All Rights Reserved.
Bài tập 1
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 28
Xét chuỗi truy xuất bộ nhớ sau:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Có bao nhiêu lỗi trang xảy ra khi sử dụng các thuật toán thay
thế sau đây, giả sử có lần lượt là 2, 3, 4, 5 khung trang.
a. LRU
b. FIFO
c. Chiến lược tối ưu (OPT)
Bài tập 2
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 29
Một máy tính 32-bit địa chỉ, sử dụng một bảng trang 2 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, và còn lại cho offset. Cho biết kích
thước một trang trong hệ thống và địa chỉ ảo có bao nhiêu trang
Bài tập 3
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 30
Giả sử địa chỉ ảo 32-bit được phân tách thành 4 trường a, b, c,
d. 3 trường đầu tiên được dùng cho bảng trang 3 cấp, trường
thứ 4 dành cho offset. Số lượng trang có phụ thuộc vào kích
thước của cả 4 trường này không? Nếu không, những trường
nào ảnh hưởng đến số lượng trang, những trường nào không
ảnh hưởng?
Tóm tắt lại nội dung buổi học
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 31
 Deadlock
 Quản lý bộ nhớ
 Bộ nhớ ảo