›
›

Đề thi cuối kỳ môn Hệ điều hành - Đề số 01 - Đại học Sư phạm Kỹ thuật thành phố Hồ Chí Minh (Có đáp án)

Download
ĐỀ 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.  
--------------------------------------------------------  
ĐẠI HỌC SƯ PHẠM KỸ THUẬT TPHCM  
KHOA : CÔNG NGHỆ THÔNG TIN  
BỘ MÔN : MẠNG  
-----------------------------------------------------  
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  
P2  
P3  
P4  
P5  
P6  
P7  
P8  
P9  
P10  
1
1
0
1
1
1
1
2
1
1
2
0
2
2
0
2
0
1
2
1
1
0
0
1
0
1
0
1
1
1
1
1
1
0
0
0
1
0
0
0
2
2
1
1
1
1
1
2
1
1
3
2
3
2
2
2
1
2
3
2
3
2
3
4
1
3
1
4
3
2
2
2
1
4
2
2
1
5
2
2
4
2
4
5
1
1
3
7
6
1
2
3
3
3
1
3
5
2
2
2
1
2
1
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  
Số hiệu: BM1/QT-KĐ-RĐTV/00  
Trang 1  
ĐÁ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).  
Các trạng thái:  
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.  
Mối quan hệ giữa các trạng thái  
5
2
6
1
3
4
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.  
Số hiệu: BM1/QT-KĐ-RĐTV/00  
Trang 2  
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  
1000K  
800K  
1200K  
1000K  
800K  
1200K  
1000K  
800K  
D
C
D
C
D
C
1000K  
800K  
1000K  
800K  
C
B
C
B
800K  
B
A
B
300K  
0K  
300K  
0K  
300K  
0K  
300K  
0K  
300K  
0K  
300K  
0K  
A
A
E
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  
A
H
0K  
300K  
300K  
1700K  
300K  
0K  
A
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  
A
B
H
0K  
300K  
800K  
300K  
500K  
1200  
800K  
B
A
300K  
0K  
Số hiệu: BM1/QT-KĐ-RĐTV/00  
Trang 3  
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  
A
B
C
H
0K  
300K  
500K  
200K  
1000K  
300K  
800K  
1000K  
1000K  
800K  
C
B
A
300K  
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  
H
B
C
H
0K  
300K  
500K  
200K  
1000K  
300K  
800K  
1000K  
1000K  
800K  
C
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  
H
B
C
D
H
0K  
300K  
500K  
200K  
200K  
800K  
300K  
800K  
1000K  
1200K  
1200K  
1000K  
800K  
D
C
B
300K  
0K  
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 thu hồi B(500K)  
2000K  
H
C
D
H
0K  
800K  
200K  
200K  
800K  
800K  
1000K  
1200K  
1200K  
1000K  
800K  
D
C
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  
E
H
C
D
H
0K  
300K  
500K  
200K  
200K  
800K  
300K  
800K  
1000K  
1200K  
1200K  
1000K  
800K  
D
C
300K  
0K  
E
Số hiệu: BM1/QT-KĐ-RĐTV/00  
Trang 5  
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  
1
2
0
2
2
0
2
0
1
2
1
1
0
0
1
0
1
0
1
1
1
1
1
1
0
0
0
1
0
0
0
2
2
1
1
1
1
1
2
1
1
3
2
3
2
2
2
1
2
3
2
3
2
3
4
1
3
1
4
3
2
2
2
1
4
2
2
1
5
2
2
4
2
4
5
1
1
3
7
6
1
2
3
3
3
1
3
5
2
2
2
P1  
P2  
P3  
P4  
P5  
P6  
P7  
P8  
P9  
P10  
1
2
3
4
5
6
6
7
2
4
1
2
2
2
2
3
3
4
1
1
2
2
3
4
5
5
2
3
2
1
3
1
1
1
0
0
2
1
1
2
1
2
1
1
1
3
1
1
1
2
1
3
2
1
1
4
1
1
3
1
3
5
1
1
2
7
6
1
0
1
2
2
0
2
4
0
1
1
(5)  
(2)  
(6)  
(7)  
(3)  
(1)  
(4)  
*
1
0
1
1
1
1
2
1
1
4
5
4
6
4
7
6
9
8
10  
11  
10  
*
(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 6  
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 :  
P1  
P2  
…
…
Wait(S);  
Wait(S);  
đoạn CT đặt data vào Buffer;  
đoạn CT lấy data từ Buffer;  
Signal(S);  
Signal(S);  
…
…
Giải thích:  
(GS P1 được cấp CPU trước)  
P1:  
Wait(s) : s=0  
P2:  
P1:  
(PCB P1) →  
Wait(s) : s=0  
…
-----------------  
(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  
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) →  
Data ←Buff  
Signal(s) : s=1  
→(PCB P2)  
Trả CPU  
-----------------  
-----------------  
Kết luận : P1, P2 không thể truy xuất đồng thời.  
Số hiệu: BM1/QT-KĐ-RĐTV/00  
Trang 7  
*Ứ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 :  
P2  
P1  
…
…
Wait(S);  
Đoạn CT P2;  
…
Wait(S);  
Đoạn CT P1;  
Signal(S);  
…
Giải thích:  
(GS P1 được cấp CPU trước)  
P1:  
P2:  
P1  
(PCB P2) →  
Wait(s) : s=0  
Tác vụ X2  
→(PCB P2)  
Trả CPU  
-----------------  
P1  
(PCB P1) →  
(PCB P1) →  
Wait(s) : s=0  
Tác vụ X1  
→(PCB P1)  
Trả CPU  
-----------------  
P2  
Wait(s) : chờ (vì s=0)  
→(PCB P2)  
Trả CPU  
Wait(s) : chờ (vì s=0)  
→(PCB P1)  
Trả CPU  
-----------------  
P2  
(PCB P2) →  
Wait(s) : chờ (vì s=0)  
Wait(s) : chờ (vì s=0) →(PCB P2)  
→(PCB P1)  
Trả CPU  
-----------------  
P2  
(PCB P2) →  
Tác vụ X2  
(Xong)  
Trả CPU  
-----------------  
…
-----------------  
P1  
(PCB P1) →  
Tác vụ X1  
Signal(s) : s=1  
→(PCB P1)  
Trả CPU  
(Hoàn thành tác vụ X)  
→(PCB P2)  
Trả CPU  
-----------------  
-----------------  
Số hiệu: BM1/QT-KĐ-RĐTV/00  
Trang 8  
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
1
3
0
1
2
1
3
2
1
4
2
5
6
3
1
4
3
6
5
2
1
3
1
3
0
1
3
0
1
3
0
1
3
0
1
3
0
1
3
0
1
3
0
1
3
0
1
3
0
1
3
5
1
6
5
3
6
5
3
6
5
3
6
5
3
6
5
3
6
5
3
6
5
3
6
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
1
2
3
0
2
4
1
3
0
5
2
4
1
3
6
5
2
4
1
3
6
5
2
4
1
3
6
5
2
4
1
3
6
5
3
4
1
6
5
6
3
4
1
5
5
6
3
4
1
2
5
6
3
4
2
1
3
1
2
0
2
3
1
0
1
2
3
0
0
3
1
1
0
3
1
2
3
1
0
3
0
3
1
Số lỗi trang : 11  
Số hiệu: BM1/QT-KĐ-RĐTV/00  
Trang 9  
pdf 9 trang yennguyen 23480 Free
Download
Bạn đang xem tài liệu "Đề thi cuối kỳ môn Hệ điều hành - Đề số 01 - Đại học Sư phạm Kỹ thuật thành phố Hồ Chí Minh (Có đáp án)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfde_thi_cuoi_ky_mon_he_dieu_hanh_de_so_01_dai_hoc_su_pham_ky.pdf