Đề thi cuối kỳ môn Hệ điều hành - Năm học 2015-2016 - Trường Đại học Công nghệ Thông Tin

Trường Đại học Công nghệ Thông Tin 
 KHOA KỸ THUẬT MÁY TÍNH 
ĐỀ THI CUỐI KỲ 
(NĂM HỌC 2015-2016) 
HỆ ĐIỀU HÀNH 
Thời gian: 90 phút 
(Sinh viên không được phép tham khảo tài liệu) 
Câu 1 (1,5 điểm): 
Hãy chứng minh thuật giải sau đây thoả mãn 3 yêu cầu bài toán đồng bộ process: 
- Mutual exclusion (0.5) 
- Progress (0.5) 
- Bounded-waiting (0.5) 
boolean waiting[n]; 
boolean lock; 
/* data structures are initialized to false */ 
do {
 
 waiting[i] = true;
 
 key = true;
 
 while (waiting[i] && key) 
 key = test and set(&lock); 
 waiting[i] = false; 
 /* critical section */ 
 j = (i + 1) % n; 
 while ((j != i) && !waiting[j]) 
 j = (j + 1) % n; 
 if (j == i) 
 lock = false; 
 else 
 waiting[j] = false; 
 /* remainder section */ 
 } while (true); 
Câu 2 (1 điểm): 
 Sử dụng semaphore để viết lại chương trình sau theo mô hình xử lý đồng hành: 
 A = x1 + x2; B = A*x3; C= A + x4; D= B + C; E = D*x5 + C; 
 Giả sử có 5 process mỗi process sẽ thực hiện 1 biểu thức. 
BG: Semaphore s1, s2, s3, s4, s5; 
 s1.value = s2.value = s3.value = s4.value = s5.value = 0; 
P1: { A; signal(s1); signal(s2) } 
P2: {wait(s1), B, signal(s3) } 
P3: {wait(s2); C; signal(s4) } 
P4: {wait(s3); wait(s4); D; signal(s5) } 
P5: {wait(s5); E} 
Câu 3 (2,5 điểm): 
 Cho biết hiện trạng của hệ thống: 
Allocation Max Available 
 ABCD ABCD ABCD 
 P0 0 0 1 2 0 0 1 2 1 5 2 0 
 P1 1 0 0 0 1 7 5 0
 
 P2 1 3 5 4 2 3 5 6
 
 P3 0 6 3 2 0 6 5 2
 
 P4 0 0 1 4 0 6 5 6 
 Sử dụng thuậtt giải banker, trả lời các câu sau: 
a. Tìm ma trận Need ? 
(0.5) 
b. Hệ thống có trong trạng thái an toàn không? 
(1.0)- Yes 
c. Nếu process P1 yêu cầu thêm tài nguyên (0,4,2,0), yêu cầu được đáp ứng tức thời không ? 
 
(1.0) – Yes 
Câu 4 (1 điểm): 
 Cho Bảng trang của Process P1, hãy cho biết: 
a. Địa chỉ vật lý 6578 sẽ được chuyển thành địa chỉ luận lý bao nhiêu? 
Biết rằng kích thước mỗi frame là 1KB. (0.5) - 434 
b. Địa chỉ luận lý 3654 sẽ được chuyển thành địa chỉ vật lý bao nhiêu? 
Biết rằng kích thước mỗi frame là 2KB. (0.5) – 9798 
Câu 5 (1,5 điểm): 
Cho 1 không gian luận lý có 64 bit, biết kích thước 1 trang 4KB. Biết bảng trang chia làm 3 
mức, mỗi mục trong bảng trang chiếm 4 byte. Tính kích thước của bảng phân trang cấp 3 (outer-
page 2) ? 
Câu 6 (2,5 điểm): 
 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 cấp 4 
khung trang ban đầu không trống? 
a. LRU (0.8) - 10 faults 
b. FIFO (0.7) - 14 faults 
c. Optimal (0.8) – 8 faults 
---o0o--- 
Giáo viên ra đề thi Phụ trách bộ môn