Ôn thi giữa kì hệ điều hành

Nội dung text: Ôn thi giữa kì hệ điều hành

1. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e ÔN THI GIỮA KÌ HỆ ĐIỀU HÀNH Vấn đề 1: Các phương pháp điều phối thời gian ngắn 1. Độ ưu tiên (Priorities). Mỗi Process có 1 độ ưu tiên. Process nào có độ ưu tiên cao nhất được thực thi. Process có độ ưu tiên thấp có thể chờ mãi mãi (không có bài tập) Đề: Bảng số liệu Process Thời điểm xuất hiện Thời gian thực thi P1 0 3 P2 2 6 P3 4 4 P4 6 5 P5 8 2 2. First – In – First – Out (FIFO) Dạng Non-Preemptive 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 P1 X P2 X P3 X P4 X P5 X Thời gian thực thi hiện thực: P1: 3 P2: 7 P3: 9 P4: 12 P5: 12 Tổng thời gian: 43 Thời gian trung bình: 8.5 3. Round Robin (RR) Dạng Preemptive quantum (q) = 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 P1 X P2 X P3 X P4 X P5 X 1 2 3 2 43 32 254 543 432 325 254 543 432 32 24 4 Thời gian thực thi hiện thực: P1: 4 P2: 16 P3: 13 P4: 14 P5: 7
2. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e Tổng thời gian: 54 Thời gian trung bình: 10.8 quantum (q) = 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 P1 X P2 X P3 X P4 X P5 X 1 1 32 2 24 43 435 352 352 524 524 24 24 4 4 Thời gian thực thi hiện thực: P1: 5 P2: 15 P3: 9 P4: 14 P5: 7 Tổng thời gian: 50 Thời gian trung bình: 10 4. Shortest Job First (SJF) Dạng Non-Preemptive 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 P1 X P2 X P3 X P4 X P5 X Thời gian thực thi hiện thực: P1: 3 P2: 7 P3: 11 P4: 14 P5: 3 Tổng thời gian: 38 Thời gian trung bình: 7.6 5. Shortest Remaining Time (SRT) Dạng Preemptive 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 P1 X P2 X P3 X P4 X P5 X Thời gian thực thi hiện thực: P1: 3 P2: 13
3. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e P3: 4 P4: 14 P5: 2 Tổng thời gian: 36 Thời gian trung bình: 7.2 6. Multi-level Feedback Queues (MFQ) Dạng Preemptive 2 queue: q0 = 1, q1 = 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 P1 X P2 X P3 X P4 X P5 X 1 2 2 3 32 24 243 435 352 524 243 43 32 24 4 2 4 Thời gian thực thi hiện thực: P1: 4 P2: 17 P3: 12 P4: 14 P5: 5 Tổng thời gian: 52 Thời gian trung bình: 10.4 3 queue: q0=1, q1=2, q2=4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 P1 X P2 X P3 X P4 X P5 X 2 4 2 3 3 3 34 45 45 5 5 2 2 2 2 23 23 234 34 34 34 4 Thời gian thực thi hiện thực: P1: 3 P2: 15 P3: 14 P4: 14 P5: 6 Tổng thời gian: 52 Thời gian trung bình: 10.4 Vấn đề 2: Giải thuật ngân hàng Dạng 1. Kiểm tra xem trạng thái có an toàn hay không? Cách giải: phải tìm cho được ít nhất C, R, A
4. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e Vd1: E=(6,3,4,2) A=(1,0,2,0) C = R = Kiểm tra xem trạng thái có an toàn hay không? Bài làm: R4 A Đáp ứng yêu cầu của P4 P4 thực thi hoàn tất và giao trả tài nguyên A=A+C4=(2,1,2,1) Mark(P4) R1 A Đáp ứng yêu cầu của P1 P1 thực thi hoàn tất và giao trả tài nguyên A=A+C1=(5,1,3,2) Mark(P1) R2 A Đáp ứng yêu cầu của P2 P2 thực thi hoàn tất và giao trả tài nguyên A=A+C2=(5,2,3,2) Mark(P2) R3 A Đáp ứng yêu cầu của P3 P3 thực thi hoàn tất và giao trả tài nguyên A=A+C3=(6,3,4,2) Mark(P3) R5 A Đáp ứng yêu cầu của P5 P5 thực thi hoàn tất và giao trả tài nguyên A=A+C5=(6,3,4,2) Mark(P5) Nhận xét: A = E Tồn tại một trình tự điều khiển để các process thực thi hoàn tất Kết luận: hệ thống ở trạng thái an toàn Vd2: 1 hệ thống có 12 ổ băng từ và 3 tiến trình với bảng cấp phát tài nguyên như sau: Tiến trình Đã được cấp (số ổ băng) Tối đa cần (số ổ băng) P1 5 10 P2 2 4 P3 2 9 Dùng giải thuật nhà băng xác định trạng thái có an toàn hay không? Bài làm Max =
5. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e C = R =Max – C = E = (12) A = E – C = (12) – ( 5 + 2 + 2 ) = (3) R2 A Đáp ứng yêu cầu của P2 P2 thực thi hoàn tất và giao trả tài nguyên A=A+C2=(5) Mark(P2) R1 A Đáp ứng yêu cầu của P1 P1 thực thi hoàn tất và giao trả tài nguyên A=A+C1=(10) Mark(P1) R3 A Đáp ứng yêu cầu của P3 P3 thực thi hoàn tất và giao trả tài nguyên A=A+C3=(12) Mark(P3) Vậy tồn tại một trình tự điều khiển để các process thực thi hoàn tất Kết luận: hệ thống ở trạng thái an toàn Cách trình bày khác: miêu tả trạng thái theo thời gian A R Process C 3 2 P2 2 5 5 P1 5 t 10 7 P3 2 Vd3: Một hệ thống có 5 tiến trình với tình trạng tài nguyên như sau: C Max A Process R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 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 Trạng thái có an toàn hay không? Bài làm:
6. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e R = Max – C = A R C Process R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 1 5 2 0 0 0 0 0 P0 0 0 1 2 1 5 3 2 1 0 0 2 P2 1 3 5 4 2 8 8 6 0 7 5 0 P1 1 0 0 0 3 8 8 6 0 0 2 0 P3 0 6 3 2 3 14 11 8 0 6 4 0 P4 0 0 1 4 Vậy tồn tại một trình tự điều khiển để các process thực thi hoàn tất Kết luận: hệ thống ở trạng thái an toàn Dạng 2: Cấp phát tài nguyên cho 1 process nào đó được hay không? Cách giải: giả định đã cấp phát, quy về dạng 1, nếu an toàn thì cấp được Vd1: Cho bảng số liệu. Loại tài nguyên Được các process yêu cầu Đã cấp cho các process R1 P2 P1 R2 P1 P2 Với tình trạng này thì có cấp phát R2 cho P2 hay không? Bài làm: Thông tin hệ thống khi giả định đã cấp R2 cho P2 E = (1, 1) A = (0, 0) C = R = Nhận xét: Kết luận: Hệ thống ở trạng thái không an toàn, nên không cấp R2 cho P2 được Dạng 3: Bài toán trên RAG (đồ thị cấp phát/phân phối tài nguyên) Cách giải: Vẽ hình và nhận xét Vd1: Cho bảng số liệu: Loại tài nguyên Số phiên bản Được các process yêu cầu Đã cấp cho các process Máy in kim 2 P1 P2, P3 Máy in laser 1 P3 Ổ băng từ 2 P2 P1, P3
7. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e Hãy thể hiện trạng thái này bằng Đồ thị cấp phát tài nguyên. Bài làm: Vd2: Cho bảng số liệu: Loại tài nguyên Số phiên bản Được các process yêu cầu Đã cấp cho các process R1 1 P1 P2 R2 2 P3 P1, P2 R3 1 P2 P3 Có deadlock hay không? Vì sao? Bài làm: RAG bị deadlock do tồn tại các chu trình và không có process nào có thể kết thúc Vấn đề 3: Thay thế trang trong bộ nhớ ảo dạng phân trang - Chọn phần tử thay thế
8. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e Vd: Cho trình tự các trang: 2 3 2 1 5 2 4 5 3 2 5 2 Optimal 2 3 2 1 5 2 4 5 3 2 5 2 2 2 2 2 2 2 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 1 5 5 5 5 5 5 5 5 F F F F F F 6 lỗi trang FIFO 2 3 2 1 5 2 4 5 3 2 5 2 20 21 22 23 50 50 51 52 30 31 32 33 30 31 32 33 20 21 22 23 24 50 51 10 11 12 40 41 42 43 44 20 F F F F F F F F F 9 lỗi trang LRU 2 3 2 1 5 2 4 5 3 2 5 2 20 21 20 21 22 20 21 22 30 31 32 33 30 31 32 50 51 52 50 51 52 50 51 10 11 12 40 41 42 20 21 20 F F F F F F F 7 lỗi trang Second Chance Clock NRU Vấn đề 4: Sơ đồ chuyển đổi địa chỉ 1. Bộ nhớ ảo dạng phân trang
9. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e 2. Tổ chức bảng trang dạng nhiều cấp 3. Tổ chức bảng trang dạng bảng băm
10. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e 4. Bảng trang nghịch đảo
11. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e 5. Sơ đồ chuyển đổi địa chỉ với TLB 6. Bộ nhớ ảo dạng phân đoạn 7. Bộ nhớ ảo dạng phân đoạn có phân trang
12. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e 8. Bộ nhớ ảo trên MULTICS 9. Bộ nhớ ảo trên Pentium
13. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e Vấn đề 5: Chuyển đổi địa chỉ Dạng 1: Cho dung lượng bộ nhớ ảo, kích thước trang, dung lượng bộ nhớ thực, cho số liệu 1 bảng trang. Xác định địa chỉ vật lí (nếu có) ứng với địa chỉ ảo Cách giải: Tìm cấu trúc địa chỉ ảo, cấu trúc địa chỉ vật lí, dựa theo cấu trúc tìm các thành phần. Tìm page# đối chiếu bảng trang để lấy ra frame# . điều kiện làm tiếp là present bit = 1. Ghép frame# với offset. Vd: Dung lượng bộ nhớ ảo Kích thước trong Dung lượng bộ nhớ thực 16MB 1KB 4MB Page# Frame# Present bit 0x68B 0x2FF 1 0x68A 0x2FE 0
14. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e 0x283 0x1FA 1 0x283 0x1FE 1 0x281 0x1AA 0 Áp dụng sơ đồ trình bày trên để xác định địa chỉ vật lí (nếu có) ứng với địa chỉ ảo Câu a. 0x0A0A0A Câu b. 0x1A2B3C Bài làm: - Cấu trúc địa chỉ ảo: Tìm kích thước địa chỉ ảo Ta có dung lượng bộ nhớ ảo là 16MB = 224 Byte Địa chỉ ảo dài 24 bit Tìm kích thước phần offset Ta có kích thước 1 trang là 1KB = 210 Byte Phần offset dài 10 bit Địa chỉ ảo dài 24 bit, offset dài 10 bit. Phần page# dài 24 – 10 = 14 bit Cấu trúc: page# | offset 14 bit 10 bit - Cấu trúc địa chỉ vật lí: Tìm kích thước địa chỉ vật lí Ta có dung lượng bộ nhớ vật lí là 4MB = 222 Byte Địa chỉ vật lí dài 22 bit Phần frame# dài: 22 – 10 = 12 bit Cấu trúc: frame# | offset 12 bit 10 bit
15. Đề cương ôn thi giữa kì hệ điều hànhCập nhật: 24/11/2010 b7@2e - Chuyển đổi địa chỉ: Câu a. Địa chỉ ảo:0x0A0A0A = 0000 1010 0000 1010 0000 10102 offset: 1000001010 page#: 00001010000010 = 0x282 Đối chiếu với bảng trang, ta có được frame# = 0x1FE , present bit = 1 Frame# = 0x1FE = 1111111102 Địa chỉ vật lí của 0x0A0A0A là : 1111111101000001010 = 0x7FA0A Câu b. Địa chỉ ảo: 0x1A2B3C = 0001101000101011001111002 offset: 1100111100 page#: 00011010001010 = 0x68A Đối chiếu với bảng trang, ta có được frame# = 0x2FE, present bit = 0 Vậy trang chưa được nạp vào bộ nhớ nên không tồn tại địa chỉ vật lí của 0x1A2B3C