Đề thi môn Hệ điều hành - Trường Đại học Sư phạm Kỹ thuật thành phố Hồ Chí Minh

Số hiệu: BM1/QT-KĐ-RĐTV/00 Trang 1 
 ĐỀ THI MÔN : HỆ ĐIỀU HÀNH 
 Mã môn học : 1180050 
 Đề số 01. Đề thi có 01 trang 
 Thời gian làm bài : 75 phút. 
 Không được phép sử dụng tài liệu. 
 -------------------------------------------------------- 
Câu 1: (2 điểm) Các trạng thái của 1 tiến trình và mối quan hệ giữa các trạng thái ? 
Câu 2: (2 điểm) 
Cho các tiến trình có bộ nhớ tương ứng A(300K), B(500K), C(200K), D(200K), E(300K). Sử dụng giải thuật Quick-
Fit với H giảm (trong kỹ thuật phân vùng động) cấp phát bộ nhớ theo trình tự : A→B→C→thu hồi A →D→thu hồi 
B→E với dung lượng bộ nhớ dùng để cấp phát là 2000k. Cho biết hiện trạng bộ nhớ và danh sách quản lý bộ nhớ ở 
các thời điểm cấp phát theo trình tự trên. 
Câu 3: (2 điểm) 
Điền số liệu (có giải thích) vào bảng sau. Có tồn tại chuỗi cấp phát an toàn hay không ?. Cho biết tài nguyên ban đầu 
của hệ thống. 
Allocation	
   Request	
   Available	
   Need	
  
R1	
   R2	
   R3	
   R4	
   R5	
   R1	
   R2	
   R3	
   R4	
   R5	
   R1	
   R2	
   R3	
   R4	
   R5	
   R1	
   R2	
   R3	
   R4	
   R5	
  
P1	
   1 2 1 1 2 3 3 2 4 2 1	
   2	
   1	
   1	
   2	
   	
   	
   	
   	
   	
  
P2	
   1 0 0 1 2 2 2 2 2 3 	
   	
   	
   	
   	
   	
   	
   	
   	
   	
  
P3	
   0 2 0 1 1 3 3 1 4 3 	
   	
   	
   	
   	
   	
   	
   	
   	
   	
  
P4	
   1 2 1 0 1 2 4 4 5 3 	
   	
   	
   	
   	
   	
   	
   	
   	
   	
  
P5	
   1 0 0 0 1 2 1 2 1 1 	
   	
   	
   	
   	
   	
   	
   	
   	
   	
  
P6	
   1 2 1 0 1 2 3 2 1 3 	
   	
   	
   	
   	
   	
   	
   	
   	
   	
  
P7	
   1 0 0 1 1 1 1 1 3 5 	
   	
   	
   	
   	
   	
   	
   	
   	
   	
  
P8	
   2 1 1 0 2 2 4 5 7 2 	
   	
   	
   	
   	
   	
   	
   	
   	
   	
  
P9	
   1 2 1 0 1 3 3 2 6 2 	
  	
  
P10	
   1 1 1 0 1 2 2 2 1 2 	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   	
   	
   	
   	
   	
  
Câu 4: (2 điểm) Trình bày giải pháp Semaphore đồng bộ tiến trình : định nghĩa Semaphore, ứng dụng trong truy 
xuất độc quyền và hoạt động phối hợp giữa 2 tiến trình (có giải thích). 
Câu 5: (2 điểm) Cho chuỗi truy xuất trang : 
1 3 0 1 2 1 3 2 1 4 2 5 6 3 1 4 3 6 5 2 
Tìm số lỗi trang phát sinh khi sử dụng giải thuật thay trang LRU-Stack với số khung trang trống là 5. 
Ghi chú: Cán bộ coi thi không được giải thích đề thi. Ngày 28 tháng 5 năm 2014 
 Trưởng BM 
ĐẠI HỌC SƯ PHẠM KỸ THUẬT TPHCM 
KHOA : CÔNG NGHỆ THÔNG TIN 
BỘ MÔN : MẠNG	
  
-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐-­‐	
  
Số hiệu: BM1/QT-KĐ-RĐTV/00 Trang 2 
ĐÁP ÁN GỢI Ý 
Câu 1: (2 điểm) 
(Thang điểm: nêu các trạng thái: 0,5 điểm, sơ đồ quan hệ: 1 điểm, giải thích sơ đồ: 0,5 điểm). 
New : mới tạo ra. 
Ready : sẳn sàng để hoạt động. 
Running : hoạt động. 
Watting (Blocked) : bị khóa. 
Terminated : kết thúc. 
1 : Lập lịch. 
2 : Cấp CPU và tài nguyên 
3 : Đợi I/O hoặc sự kiện của tiến trình. 
4 : Đáp ứng I/O hoặc sự kiện của tiến trình. 
5 : Interrupt hoặc sự kiện của hệ thống. 
6 : Hoàn tất hoạt động. 
Mối quan hệ giữa các trạng thái 
Các trạng thái: 
1 
2 
3 
5 
4 
6 
Số hiệu: BM1/QT-KĐ-RĐTV/00 Trang 3 
Câu 2: (2 điểm) (Thang điểm: trình tự cấp phát: 0,25 điểm, hiện trạng và danh sách: 0,25 điểm cho mỗi 
thời điểm cấp phát theo trình tự). 
Cấp phát bộ nhớ theo trình tự : A(300K) →B(500K) →C(200K) →thu hồi A →D(200K) →thu hồi B 
→E(300K) bằ Quick Fit với H giảm . Sơ đồ cấp phát : 
 2000K 2000K 2000K 2000K 2000K 2000K 2000K 
 1200K 1200K 1200K 
 D D D 
 1000K 1000K 1000K 1000K 1000K 
 C C C C C 
 800K 800K 800K 800K 800K 800K 
 B B B B 
 300K 300K 300K 300K 300K 300K 
A A A 
 E 
 0K 0K 0K 0K 0K 0K 0K 
Hiện trạng bộ nhớ và danh sách quản lý bộ nhớ ở thời điểm cấp phát A(300K) 
 2000K 
 300K 
A 0K 
Hiện trạng bộ nhớ và danh sách quản lý bộ nhớ ở thời điểm cấp phát B(500K) 
 2000K 
 800K 
B 
 300K 
A 0K 
A 0K 300K 
H 300K 1700K 
A 0K 300K 
B 300K 500K 
H 800K 1200 
Số hiệu: BM1/QT-KĐ-RĐTV/00 Trang 4 
Hiện trạng bộ nhớ và danh sách quản lý bộ nhớ ở thời điểm cấp phát C(200K) 
 2000K 
 1000K 
C 
 800K 
B 
 300K 
A 0K 
Hiện trạng bộ nhớ và danh sách quản lý bộ nhớ ở thời điểm thu hồi A(300K) 
 2000K 
 1000K 
C 
 800K 
B 
 300K 
 0K 
Hiện trạng bộ nhớ và danh sách quản lý bộ nhớ ở thời điểm cấp phát D(200K) 
 2000K 
 1200K 
D 
 1000K 
C 
 800K 
B 
 300K 
 0K 
A 0K 300K 
B 300K 500K 
C 800K 200K 
H 1000K 1000K 
H 0K 300K 
B 300K 500K 
C 800K 200K 
H 1000K 1000K 
H 0K 300K 
B 300K 500K 
C 800K 200K 
D 1000K 200K 
H 1200K 800K 
Số hiệu: BM1/QT-KĐ-RĐTV/00 Trang 5 
Hiện trạng bộ nhớ và danh sách quản lý bộ nhớ ở thời điểm thu hồi B(500K) 
 2000K 
 1200K 
D 
 1000K 
C 
 800K 
 0K 
Hiện trạng bộ nhớ và danh sách quản lý bộ nhớ ở thời điểm cấp phát E(300K) 
 2000K 
 1200K 
D 
 1000K 
C 
 800K 
 300K 
E 0K 
H 0K 800K 
C 800K 200K 
D 1000K 200K 
H 1200K 800K 
E 0K 300K 
H 300K 500K 
C 800K 200K 
D 1000K 200K 
H 1200K 800K 
Số hiệu: BM1/QT-KĐ-RĐTV/00 Trang 6 
Câu 3: (2 điểm) (Thang điểm: điền dữ liệu vào bảng: 0,5 điểm, giải thích: 0,5 điểm, kết luận: 0,5 điểm, tài 
nguyên ban đầu: 0,5 điểm). 
	
  	
   Allocation	
   Request	
   Available	
   Need	
   	
  	
  
	
  	
   R1	
   R2	
   R3	
   R4	
   R5	
   R1	
   R2	
   R3	
   R4	
   R5	
   R1	
   R2	
   R3	
   R4	
   R5	
   R1	
   R2	
   R3	
   R4	
   R5	
   TT	
  Cấp	
  
P1	
   1 2 1 1 2 3 3 2 4 2 1	
   2	
   1	
   1	
   2	
   2	
   1	
   1	
   3	
   0	
   (5)	
  
P2	
   1 0 0 1 2 2 2 2 2 3 2	
   4	
   2	
   1	
   3	
   1	
   2	
   2	
   1	
   1	
   (2)	
  
P3	
   0 2 0 1 1 3 3 1 4 3 3	
   4	
   2	
   2	
   5	
   3	
   1	
   1	
   3	
   2	
   (6)	
  
P4	
   1 2 1 0 1 2 4 4 5 3 4	
   4	
   2	
   2	
   6	
   1	
   2	
   3	
   5	
   2	
   (7)	
  
P5	
   1 0 0 0 1 2 1 2 1 1 5	
   4	
   2	
   3	
   7	
   1	
   1	
   2	
   1	
   0	
   (3)	
  
P6	
   1 2 1 0 1 2 3 2 1 3 6	
   6	
   3	
   4	
   9	
   1	
   1	
   1	
   1	
   2	
   (1)	
  
P7	
   1 0 0 1 1 1 1 1 3 5 6	
   8	
   3	
   5	
   10	
   0	
   1	
   1	
   2	
   4	
   (4)	
  
P8	
   2 1 1 0 2 2 4 5 7 2 7	
   10	
   4	
   5	
   11	
   0	
   3	
   4	
   7	
   0	
   *	
  
P9	
   1 2 1 0 1 3 3 2 6 2 	
  	
  
	
  	
   2	
   1	
   1	
   6	
   1	
   *	
  
P10	
   1 1 1 0 1 2 2 2 1 2 	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   1	
   1	
   1	
   1	
   1	
   (8)	
  
 10	
   13	
   6	
   5	
   14	
  
(1)Available	
  =	
  (1,2,1,1,2)	
  →	
  Need	
  =	
  ((1,1,1,1,2)	
  P6	
  
(2)Available	
  =	
  (1,2,1,1,2)	
  +	
  Allocation	
  P6(1,2,1,0,1)	
  =	
  (2,4,2,1,3)	
  →	
  Need	
  =	
  (1,2,2,1,1)	
  P2	
  
(3)Available	
  =	
  (2,4,2,1,3)	
  +	
  Allocation	
  P2(1,0,0,1,2)	
  =	
  (3,4,2,2,5)	
  →	
  Need	
  =	
  (1,1,2,1,0)	
  P5	
  
(4)Available	
  =	
  (3,4,2,2,5)	
  +	
  Allocation	
  P5(1,0,0,0,1)	
  =	
  (4,4,2,2,6)	
  →	
  Need	
  =	
  (0,1,1,2,4)	
  P7	
  
(5)Available	
  =	
  (4,4,2,2,6)	
  +	
  Allocation	
  P7(1,0,0,1,1)	
  =	
  (5,4,2,3,7)	
  →	
  Need	
  =	
  (2,1,1,3,0)	
  P1	
  
(6)Available	
  =	
  (5,4,2,3,7)	
  +	
  Allocation	
  P1(1,2,1,1,2)	
  =	
  (6,6,3,4,9)	
  →	
  Need	
  =	
  (3,1,1,3,2)	
  P3	
  
(7)Available	
  =	
  (6,6,3,4,9)	
  +	
  Allocation	
  P3(0,2,0,1,1)	
  =	
  (6,8,3,5,10)	
  →	
  Need	
  =	
  (1,2,3,5,2)	
  P4	
  
(8)Available	
  =	
  (6,8,3,5,10)	
  +	
  Allocation	
  P4(1,2,1,0,1)	
  =	
  (7,10,4,5,11)	
  	
  
Available	
  =	
  (7,10,4,5,11)	
  không	
  cấp	
  được	
  cho	
  Need=(0,3,4,7,0)P8,	
  Need(2,1,1,6,1)P9	
  
Kết	
  luận	
  :	
  không	
  tồn	
  tại	
  chuỗi	
  cấp	
  phát	
  an	
  toàn.	
  
Tài	
  nguyên	
  ban	
  đầu	
  :	
  (10,13,6,5,14).	
  
Câu 4: (2 điểm) (Thang điểm: định nghĩa Semaphore: 0,5 điểm, mỗi ứng dụng: 0,75(cấu trúc lại:0,25, 
giải thích: 0,5 điểm)). 
ĐN : Semaphore S là 1 số nguyên không âm. 
 S chỉ có thể bị thay đổi bởi 2 hàm 
 Signal(S)=S+1 
 S-1; S>0 
 Wait(S)= 
 Chờ khi S>0; S=0 
 Trong thời gian thay đổi S, không có sự tham gia của bất kỳ TT 
Số hiệu: BM1/QT-KĐ-RĐTV/00 Trang 7 
Hàm wait() và signal() 
wait(S) { 
 while S <= 0; // no-op 
 S=S-1; 
 } 
signal(S) { 
 S=S+1; 
 } 
*Ứng dụng Semaphore trong truy xuất độc quyền 
VD : P1, P2 cùng truy xuất Buffer 
 P1 đặt data vào Buffer 
 P2 lấy data từ Buffer 
Vấn đề : P1, P2 không thể cùng truy xuất Buffer 
Miền Găng P1 : đoạn CT đặt data vào Buffer 
Miền Găng P2 : đoạn CT lấy data từ Buffer 
S Semaphore truy xuất Buffer (S=1) 
Cấu trúc lại miền Găng P1, P2 : 
Giải thích: 
Kết luận : P1, P2 không thể truy xuất đồng thời. 
P1 
Wait(S); 
 đoạn CT đặt data vào Buffer; 
Signal(S); 
P2 
Wait(S); 
 đoạn CT lấy data từ Buffer; 
Signal(S); 
(GS P1 được cấp CPU trước) 
P1: 
Wait(s) : s=0 
Data→Buff 
→(PCB P1) 
Trả CPU 
----------------- 
P2: 
Wait(s) : chờ (vì s=0) 
→(PCB P2) 
Trả CPU 
----------------- 
P1: 
(PCB P1) → 
Data→Buff 
Signal(s) : s=1 
→(PCB P1) 
Trả CPU 
----------------- 
P2: 
(PCB P2) → 
Wait(s) : s=0 
Data←Buff 
→(PCB P2) 
Trả CPU 
----------------- 
P1: 
(PCB P1) → 
Wait(s) : chờ (vì s=0) 
→(PCB P1) 
Trả CPU 
----------------- 
P2: 
(PCB P2) → 
Data ←Buff 
Signal(s) : s=1 
→(PCB P2) 
Trả CPU 
----------------- 
P1: 
(PCB P1) → 
Wait(s) : s=0 
----------------- 
Số hiệu: BM1/QT-KĐ-RĐTV/00 Trang 8 
*Ứng dụng Semaphore trong hoạt động phối hợp 
VD : tác vụ X = tác vụ X1+tác vụ X2 
 (tác vụ X1 thực hiện trước, tác vụ X2 thực hiện sau để kết thúc tác vụ X) 
 P1 thực hiện tác vụ X1 
 P2 thực hiện tác vụ X2 
Vấn đề : tác vụ X1 thực hiện trước cho đến khi hoàn thành 
 thì mới thực hiện tác vụ X2 và khi thực hiện xong 
 tác vụ X2 thì kết thúc tác vụ X (không thực hiện lại tác vụ X1). 
Miền Găng : đoạn CT trong P1 thực hiện tác vụ X1, đoạn CT trong P2 
 thực hiện tác vụ X2. 
S Semaphore kiểm soát truy xuất đồng thời P1, P2 (S=1) 
Cấu trúc lại miền Găng P1, P2 : 
Giải thích: 
P1 
Wait(S); 
 Đoạn CT P1; 
Signal(S); 
P2 
Wait(S); 
 Đoạn CT P2; 
(GS P1 được cấp CPU trước) 
P1: 
Wait(s) : s=0 
Tác vụ X1 
→(PCB P1) 
Trả CPU 
----------------- 
P2 
Wait(s) : chờ (vì s=0) 
→(PCB P2) 
Trả CPU 
----------------- 
P1 
(PCB P1) → 
Tác vụ X1 
Signal(s) : s=1 
→(PCB P1) 
Trả CPU 
----------------- 
P2: 
(PCB P2) → 
Wait(s) : s=0 
Tác vụ X2 
→(PCB P2) 
Trả CPU 
----------------- 
P1 
(PCB P1) → 
Wait(s) : chờ (vì s=0) 
→(PCB P1) 
Trả CPU 
----------------- 
P2 
(PCB P2) → 
Tác vụ X2 
(Xong) 
→(PCB P2) 
Trả CPU 
----------------- 
P1 
(PCB P1) → 
Wait(s) : chờ (vì s=0) 
→(PCB P1) 
Trả CPU 
----------------- 
P2 
(PCB P2) → 
Wait(s) : chờ (vì s=0) 
→(PCB P2) 
Trả CPU 
----------------- 
(Hoàn thành tác vụ X) 
Số hiệu: BM1/QT-KĐ-RĐTV/00 Trang 9 
Câu 5: (2 điểm) (Thang điểm: Bảng LRU: 1 điểm, lỗi trang: 0,5 điểm, bảng Stack: 0,5 điểm). 
1 3 0 1 2 1 3 2 1 4 2 5 6 3 1 4 3 6 5 2 
1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 
 3 3 3 3 3 3 3 3 3 3 3 6 6 6 6 6 6 6 6 
 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5 5 5 5 
 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 
 4 4 4 4 4 1 1 1 1 1 2 
* * * * * * * * * * * 
 4 2 5 6 3 1 4 3 6 5 2 
 2 1 3 2 1 1 4 2 5 6 3 1 4 3 6 5 
 0 1 1 2 1 3 2 2 1 4 2 5 6 3 1 4 3 6 
 3 3 0 0 0 2 1 3 3 3 1 4 2 5 6 6 1 4 3 
1 1 1 3 3 3 0 0 0 0 0 3 1 4 2 5 5 5 1 4 
Số lỗi trang : 11