Đề thi và đáp án đề thi học kỳ I năm 2014-2015 môn Hệ điều hành (Đề số 1) - ĐH Sư phạm Kỹ thuật

Chia sẻ: Đinh Y | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

58
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề thi và đáp án đề thi học kỳ I năm 2014-2015 môn Hệ điều hành giúp các bạn học sinh có thêm tài liệu ôn tập, luyện tập nhằm nắm vững được những kiến thức, kĩ năng cơ bản, đồng thời vận dụng kiến thức để giải các bài tập một cách thuận lợi.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi và đáp án đề thi học kỳ I năm 2014-2015 môn Hệ điều hành (Đề số 1) - ĐH Sư phạm Kỹ thuật

ĐỀ THI MÔN : HỆ ĐIỀU HÀNH Mã môn học : 1180050 ĐẠI HỌC SƯ PHẠM KỸ THUẬT TPHCM Đề số 01. Đề thi có 01 trang KHOA : CÔNG NGHỆ THÔNG TIN Thời gian làm bài : 75 phút. BỘ MÔN : MẠNG 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 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 1 5 6 2 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 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 A 0K 300K H 300K 1700K 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 A 0K 300K B 300K 500K H 800K 1200 800K B 300K A 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 0K 300K B 300K 500K C 800K 200K 1000K C H 1000K 1000K 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 H 0K 300K B 300K 500K C 800K 200K 1000K C H 1000K 1000K 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 H 0K 300K 1200K B 300K 500K D C 800K 200K 1000K D 1000K 200K C 800K H 1200K 800K 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 0K 800K 1200K C 800K 200K D D 1000K 200K 1000K C H 1200K 800K 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 E 0K 300K 1200K H 300K 500K D C 800K 200K 1000K D 1000K 200K C 800K H 1200K 800K 300K E 0K 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 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 * 1 1 1 0 1 2 2 2 1 2 P10 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 6
Hàm wait() và signal() wait(S) { while S
*Ứ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 : P1 P2 … … Wait(S); Wait(S); Đoạn CT P1; Đoạn CT P2; Signal(S); … … Giải thích: (GS P1 được cấp CPU trước) P1: P2: P1 Wait(s) : s=0 (PCB P2) → (PCB P1) → Tác vụ X1 Wait(s) : s=0 Wait(s) : chờ (vì s=0) →(PCB P1) Tác vụ X2 →(PCB P1) Trả CPU →(PCB P2) Trả CPU ----------------- Trả CPU ----------------- P2 ----------------- P2 Wait(s) : chờ (vì s=0) P1 (PCB P2) → →(PCB P2) (PCB P1) → Wait(s) : chờ (vì s=0) Trả CPU Wait(s) : chờ (vì s=0) →(PCB P2) ----------------- →(PCB P1) Trả CPU P1 Trả CPU ----------------- (PCB P1) → ----------------- … Tác vụ X1 P2 Signal(s) : s=1 (PCB P2) → (Hoàn thành tác vụ X) →(PCB P1) Tác vụ X2 Trả CPU (Xong) ----------------- →(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 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 Số hiệu: BM1/QT-KĐ-RĐTV/00 Trang 9