Bài Tập Các Chiến Lược điều Phối Process - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (16 trang)

Trang chủ

Công Nghệ Thông Tin

Hệ điều hành

Bài tập các chiến lược điều phối process

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (259.5 KB, 16 trang )

Giảng viên: Lương Trần Hy Hiến – Trang 1 BÀI TẬP LÝ THUYẾT CHỦ ĐỀ 1: CÁC CHIẾN LƯỢC ĐIỀU PHỐI PROCESS Các trạng thái tiến trình: • new: Tiến trình vừa được tạo (chạy chương trình) • ready: Tiến trình sẵn sàng để chạy • running: Tiến trình đang chạy (thi hành lệnh) • waiting: Tiến trình chờ đợi một sự kiện • terminated: Tiến trình kết thúc thi hành lệnh Có nhiều hàng đợi: • ready queue: hàng đợi chứa các tiến trình sẵn sàng chạy • I/O queue: hàng đợi chứa các tiến trình sẵn sàng thi hành I/O FCFS hiện đại Ví dụ 1: Cho tiến trình A(10, 3, 2), 10: tổng thời gian hoạt động, 3: Thời điểm bắt đầu I/O, 2: Trong I/O bao lâu. 1 2 3 4 5 6 7 8 9 10 AR AR AR AIO AIO AR AR AR AR AR AR: Arunning (A đang giữ CPU) AIO: AInput/Output (A đang I/O) Ví dụ 2: Cho A(10, 2, 2)  AR AR AIO AIO AR AR AR AR AR AR B(8, 2, 2)  BR BR BIO BIO BR BR BR BR. (Khi sắp lên cột thời gian thì không có 2 cái giống nhau, tức là AR thì trạng thái của B không thể là BR, hoặc trạng thái của A là AIO thì trạng thái của B không thể là BIO. Do đó: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 AR AR AIO AIO AR AR AR AR AR AR BR BR BIO BIO BR BR BR BR Vậy tại thời điểm t = 9,32 thì A running, B ready (tiến trình B vẫn chưa hết thời gian hoạt động). Giảng viên: Lương Trần Hy Hiến – Trang 2 Round Robin hiện đại 2 quy tắc để thực hiện RR có I/O: • Tại thời điểm m có 2 tiến trình: A running xong q (vừa hết thời gian q) và B IO xong (vừa hết thời gian I/O) thì thứ tự đưa vào hàng đợi ready queue là B trước A sau. • Tại thời điểm m nếu A running xong q (vừa hết thời gian q) và đến thời điểm bắt đ ầu IO thì thời điểm IO sẽ đưa vào chu kỳ sau (A sẽ được đưa vào Ready queue và A sẽ đi I/O vào lần cấp phát CPU kế tiếp cho nó). Cần chú ý: • Tại thời điểm m nào đó mà tiến trình A running xong mà chưa hết thời gian quantum q thì tiến trình A đi I/O ngay. • Thời gian quantum q chỉ có tác dụng đối với việc giữ CPU (tức là tiến trình chỉ được giữ CPU trong thời gian tối đa là q), không có tác dụng đối với thời gian I/O (tiến trình đã bắt đầu I/O thì thực hiện hết khoảng thời gian I/O bất chất q) Bài 1. Cho 3 process và bảng sau: Tên process Tổng thời gian Thời điểm I/O Thời gian I/O A 10 5 3 B 8 2 3 C 6 0 2 Vẽ sơ đồ điều phối 3 process này và cho biết trạng thái của các trạng thái tại thời điểm t = 10.5s: a. Theo chiến lược FIFO có I/O. b. Theo chiến lược Round Robin có I/O với q = 2. Bài 2. Cho 4 process và bảng sau: Tên process Tổng thời gian Thời điểm I/O Thời gian I/O A 10 2 5 B 6 1 1 C 10 2 1 D 9 2 2 Vẽ sơ đồ điều phối 4 process này và cho biết trạng thái của các trạng thái tại thời điểm t = 10.5s: a. Theo chiến lược FIFO có I/O. b. Theo chiến lược Round Robin có I/O với q = 3. Bài 3. Cho 4 process và bảng sau: Tên process Tổng thời gian Thời điểm I/O Thời gian I/O A 7 3 1 B 6 2 2 C 5 2 2 D 6 2 1 Vẽ sơ đồ điều phối 4 process này và cho biết trạng thái của các trạng thái tại thời điểm t = 10.5s: a. Theo chiến lược FIFO có I/O. b. Theo chiến lược Round Robin có I/O với q = 3. Bài 4. Cho 3 process và bảng sau: Tên process Tổng thời gian Thời điểm I/O Thời gian I/O A 10 3 3 B 9 2 2 C 10 4 5 Giảng viên: Lương Trần Hy Hiến – Trang 3 Vẽ sơ đồ điều phối 3 process này và cho biết trạng thái của các trạng thái tại thời điểm t = 13.5s: a. Theo chiến lược FIFO có I/O. b. Theo chiến lược Round Robin có I/O với q = 3. Bài 5. Cho 3 process và bảng sau: Tên process Tổng thời gian Thời điểm I/O Thời gian I/O A 10 3 3 B 7 2 3 C 11 5 5 Vẽ sơ đồ điều phối 3 process này và cho biết trạng thái của các trạng thái tại thời điểm t = 6.5s: a. Theo chiến lược FIFO có I/O. b. Theo chiến lược Round Robin có I/O với q = 2. Bài 6. Cho 3 process và bảng sau: Tên process Tổng thời gian Thời điểm I/O Thời gian I/O A 11 3 4 B 10 3 4 C 7 1 2 Vẽ sơ đồ điều phối 3 process này và cho biết trạng thái của các trạng thái tại thời điểm t = 11.5s: a. Theo chiến lược FIFO có I/O. b. Theo chiến lược Round Robin có I/O với q = 3. Bài 7. Cho 3 process và bảng sau: Tên process Tổng thời gian Thời điểm I/O Thời gian I/O A 12 4 3 B 9 2 4 C 6 1 3 Vẽ sơ đồ điều phối 3 process này và cho biết trạng thái của các trạng thái tại thời điểm t = 9.5s: a. Theo chiến lược FIFO có I/O. b. Theo chiến lược Round Robin có I/O với q = 3. Bài 8. Cho 3 process và bảng sau: Tên process Tổng thời gian Thời điểm I/O Thời gian I/O A 6 2 1 B 12 5 3 C 6 0 2 Giảng viên: Lương Trần Hy Hiến – Trang 4 Vẽ sơ đồ điều phối 3 process này và cho biết trạng thái của các trạng thái tại thời điểm t = 9.5s: a. Theo chiến lược FIFO có I/O. b. Theo chiến lược Round Robin có I/O với q = 3. Bài 9. Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau: Tiến trình Thời điểm đến (ms) CPU-Burst (ms) Độ ưu tiên P1 3 9 3 P2 5 5 1 P3 7 14 4 P4 15 10 2 Hãy tính thời gian chờ trung bình và vẽ biểu đồ Gantt trong với các chiến lược sau: a. FIFO (FCFS) b. Phân phối xoay vòng (Round-Robin) với thời lượng quantum là 10 ms. c. Công việc ngắn nhất (SJFS) (không độc quyền). d. Độ ưu tiên (không độc quyền). Bài 10. Cho 4 tiến trình và thời gian đến (Arrival Time) tương ứng : Arrival Time CPU Burst Time P1 0 10 P2 2 6 P3 3 1 P4 5 3 Vẽ sơ đồ Gannt và tính thời gian chờ trung bình (average wait time) và thời gian xoay vòng (average turnaround time) trung bình cho các giải thuật định thời a. First Come First Serve (FCFS) – FIFO. b. Công việc ngắn nhất (SJFS) c. Round Robin (RR) với quantum = 4. Giảng viên: Lương Trần Hy Hiến – Trang 5 CHỦ ĐỀ 2: DEADCLOCK Một số thuật ngữ: • Max: Yêu cầu ban đầu (ma trận mxn, với m là số dòng - ứng với số lượng tiến trình, n là cột - ứng với số lượng tài nguyên). Trong một số tài liệu, người ta thường dùng từ Request thay cho Max. • Allocation: Đã cấp phát (ma trận mxn) • Available: Tài nguyên còn lại (ma trận 1xn) • Need: Nhu cầu còn lại (ma trận mxn, xác định như sau: Need[i,j] = Max[i,j] – Allocation[i,j]) • Số tài nguyên từng loại: Allocation[j] + Available[j] • Hãy tìm một trạng thái an toàn: Có nhiều cách, do đó kết quả các cách làm sẽ không giống nhau tùy thuộc vào cách tìm, thuờng so sánh bảng Need với Available, xem Pi nào nhỏ chọn cái đó trước). Bài 1. Cho hệ thống có 5 tiến trình và 3 loại tài nguyên (A, B, C). Giả sử hệ thống đang ở trạng thái sau: Yêu cầu ban đầu (Request) Đã cấp phát (Allocation) Tài nguyên rãnh (Available) A B C A B C A B C P1 4 6 5 1 1 2 2 7 3 P2 6 8 5 2 2 1 P3 3 2 2 1 0 0 P4 3 6 4 0 1 1 P5 2 3 2 0 0 1 a. Tính nhu cầu còn lại của mỗi tiến trình và số tài nguyên mỗi loại của hệ thống. b. Hãy tìm một trạng thái an toàn (safe state). c. Nếu tiến trình P2 có yêu cầu thêm tài nguyên (A: 1, B: 2, C: 1), hãy cho biết yêu cầu này có thể đáp ứng mà bảo đảm không xảy ra tình trạng deadlock hay không? Bài 2. Cho hệ thống có 5 tiến trình và 3 loại tài nguyên (A, B, C). Giả sử hệ thống đang ở trạng thái sau: Yêu cầu ban đầu (Request) Đã cấp phát (Allocation) Tài nguyên còn lại (Need) Tài nguyên rãnh (Available) A B C A B C A B C A B C P1 2 3 2 0 1 2 2 2 0 2 3 3 P2 3 7 5 0 0 1 3 7 4 P3 3 4 3 2 0 0 1 4 3 P4 2 2 2 1 1 1 1 1 1 P5 2 9 0 2 4 0 0 5 0 a. Tính số tài nguyên mỗi loại của hệ thống. b. Hãy tìm một trạng thái an toàn (safe state). Giảng viên: Lương Trần Hy Hiến – Trang 6 c. Nếu tiến trình P3 có yêu cầu thêm tài nguyên (A: 0, B: 0, C: 3), áp dụng giải thuật nhà băng (Banker’s Algorithm), xét xem có nên cấp phát cho P3 hay không? Tại sao? Bài 3. Cho hệ thống có 5 tiến trình và 3 loại tài nguyên (A, B, C). Giả sử hệ thống đang ở trạng thái sau: Yêu cầu ban đầu (Request) Đã cấp phát (Allocation) Tài nguyên còn lại (Need) Tài nguyên rãnh (Available) A B C A B C A B C A B C P1 3 4 3 2 0 0 1 4 3 2 3 3 P2 3 7 5 0 0 1 3 7 4 P3 2 3 2 0 1 0 2 2 2 P4 2 9 0 2 4 0 0 5 0 P5 2 2 2 1 1 1 1 1 1 a. Tính số tài nguyên mỗi loại của hệ thống. b. Hãy tìm một trạng thái an toàn (safe state). c. Nếu tiến trình P3 có yêu cầu thêm tài nguyên (A: 1, B: 2, C: 0), áp dụng giải thuật nhà băng (Banker’s Algorithm), xét xem có nên cấp phát cho P3 hay không? Tại sao? Bài 4. Cho hệ thống có 5 tiến trình và 4 loại tài nguyên (A, B, C, D). Giả sử hệ thống đang ở trạng thái sau: Yêu cầu ban đầu (Request) Đã cấp phát (Allocation) Tài nguyên rãnh (Available) A B C D A B C D A B C D P1 0 0 1 2 0 0 1 1 1 5 2 0 P2 1 7 5 0 1 0 0 0 P3 2 3 5 6 1 3 5 4 P4 0 6 5 2 0 6 3 2 P5 0 9 5 6 0 0 1 4 a. Tính số tài nguyên mỗi loại của hệ thống. b. Tính nhu cầu còn lại (Need) của hệ thống. c. Hãy tìm một trạng thái an toàn (safe state). d. Nếu tiến trình P2 có yêu cầu thêm tài nguyên (A: 0, B: 4, C: 2, D: 0), áp dụng giải thuật nhà băng (Banker’s Algorithm), xét xem có nên cấp phát cho P2 hay không? Tại sao? Bài 5. Cho hệ thống có 5 tiến trình và 3 loại tài nguyên (A, B, C). Giả sử hệ thống đang ở trạng thái sau: Yêu cầu ban đầu (Request) Đã cấp phát (Allocation) Tài nguyên còn lại (Need) Tài nguyên rãnh (Available) A B C A B C A B C A B C P1 7 7 3 2 1 0 5 6 3 3 3 2 P2 9 0 2 3 0 2 6 0 0 P3 4 3 3 0 0 2 4 3 1 P4 5 2 2 1 1 0 4 1 2 P5 2 2 2 1 1 1 1 1 1 a. Tính số tài nguyên mỗi loại của hệ thống. b. Hãy tìm một trạng thái an toàn (safe state). Giảng viên: Lương Trần Hy Hiến – Trang 7 c. Nếu tiến trình P3 có yêu cầu thêm tài nguyên (A: 0, B: 0, C: 2), áp dụng giải thuật nhà băng (Banker’s Algorithm), xét xem có nên cấp phát cho P3 hay không? Tại sao? Bài 6. Cho hệ thống có 5 tiến trình và 3 loại tài nguyên (A, B, C). Giả sử hệ thống đang ở trạng thái sau: Yêu cầu ban đầu (Request) Đã cấp phát (Allocation) Tài nguyên còn lại (Need) Tài nguyên rãnh (Available) A B C A B C A B C A B C P1 7 5 3 2 1 0 5 4 3 3 3 2 P2 9 0 2 3 0 2 6 0 0 P3 4 3 3 0 0 2 4 3 1 P4 3 2 2 1 0 0 2 2 2 P5 2 2 2 1 1 1 1 1 1 a. Tính số tài nguyên mỗi loại của hệ thống. b. Hãy tìm một trạng thái an toàn (safe state). c. Nếu tiến trình P3 có yêu cầu thêm tài nguyên (A: 3, B: 1, C: 0), áp dụng giải thuật nhà băng (Banker’s Algorithm), xét xem có nên cấp phát cho P3 hay không? Tại sao? Bài 7. Một hệ thống có 3 ổ băng từ và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên ở thời điểm Ti thể hiện bằng véc-tơ Allocation = (1, 0, 1) và Max = (1, 2, 2): Dùng giải thuật nhà băng để: a. Chứng minh trạng thái này an toàn. b. Xác định có nên đáp ứng hay không yêu cầu xin thêm 1 ổ nữa của của P3? Bài 8. Một hệ thống có 5 tiến trình và 4 loại tài nguyên (A, B, C, D) với tình trạng như sau: - A có 3 thể hiện. - B có 14 thể hiên - C có 12 thể hiện - D có 12 thể hiện Process Allocation Max Available A B C D A B C D A B C D 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 Dùng giải thuật nhà băng để: a. Chứng minh trạng thái này an toàn. b. Xác định có nên đáp ứng yêu cầu (0, 4, 3, 0) của P1 ? Bài 9. Một hệ thống có 4 tiến trình P1, P2, P3, P4 và 5 loại tài nguyên R1, R2, R3, R4, R5. Trong đó: - R1 có 1 thể hiện - R2 có 2 thể hiện - R3 có 1 thể hiện Giảng viên: Lương Trần Hy Hiến – Trang 8 - R4 có 3 thể hiện - R5 có 2 thể hiện - P1 đang giữ 1 thể hiện của R2 và yêu cầu 1 thể hiện của R1 - P2 đang giữ 1 thể hiện của R1 và yêu cầu 1 thể hiện của R3 - P3 đang giữ 1 thể hiện của R3 và yêu cầu 1 thể hiện của R4 - P4 đang giữ 1 thể hiện của R4 và yêu cầu 1 thể hiện của R2. a. Hãy vẽ đồ thị cấp phát tài nguyên như mô tả trên. b. Trạng thái trên có xảy ra deadclock không? Tại sao? Bài 10. Trạng thái sau có xảy ra tình trạng deadclock không? Tại sao? Giảng viên: Lương Trần Hy Hiến – Trang 9 CHỦ ĐỀ 3: QUẢN LÝ BỘ NHỚ Bài 1. Chương trình A cần thực hiện các trang 2, 5, 2, 4, 2, 6, 3, 7, 3 với số khung trang k=3. Hãy thực hiện thay thế trang theo FIFO, LRU và tối ưu (ít sử dụng nhất trong tương lai). Cho biết cơ chế nào tốt hơn. HD GIẢI:  FIFO (vào trước được thay ra trước) 2 5 2 4 2 6 3 7 3 Kt1 2* 2 2 2 2 6* 6 6 6 Kt2 5* 5 5 5 5 3* 3 3 Kt3 4* 4 4 4 7* 7 Thay thế trang 6 lần.  Ít sử dụng nhất trong tương lai: (trang ít khả năng sử dụng nhất trong tương lai sẽ được thay ra  thuật toán tối ưu nhưng khó thực hiện) 2 5 2 4 2 6 3 7 3 Kt1 2* 2 2 2 2 6* 3* 3 3 Kt2 5* 5 5 5 5 5 7* 7 Kt3 4* 4 4 4 4 4 Thay thế trang 6 lần.  LRU (lâu nhất chưa sử dụng sẽ bị thay ra) 2 5 2 4 2 6 3 7 3 Kt1 2* 2 2 2 2 2 2 7* 7 Kt2 5* 5 5 5 6* 6 6 6 Kt3 4* 4 4 3* 3 3 Thay thế trang 6 lần. Bài 2. Cho bộ nhớ thực có 3 frame, bộ nhớ ảo có 6 page. Vẽ sơ đồ phân trang theo chiến lược FIFO và LRU. Biết thứ tự truy xuất các trang theo thời gian như sau: 5, 3, 0, 3, 1, 2, 4, 2, 4, 5. Bài 3. Cho bộ nhớ thực có 4 frame, bộ nhớ ảo có 8 page. Vẽ sơ đồ phân trang theo chiến lược FIFO và LRU. Biết thứ tự truy xuất các trang theo thời gian như sau: 5, 7, 6, 7, 4, 3, 4, 1, 6, 6, 2, 4, 0, 5, 1, 2, 6, 7, 6, 5. Bài 4. Cho bộ nhớ thực có 3 frame, bộ nhớ ảo có 8 page. Vẽ sơ đồ phân trang theo chiến lược FIFO và LRU. Biết thứ tự truy xuất các trang theo thời gian như sau: 7, 0, 5, 2, 0, 3, 0, 4, 6, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1. Bài 5. Cho bộ nhớ thực có 3 frame, bộ nhớ ảo có 6 page. Vẽ sơ đồ phân trang theo chiến lược FIFO và LRU. Biết thứ tự truy xuất các trang theo thời gian như sau: 0, 1, 0, 2, 3, 4, 5, 0, 1, 3. Bài 6. Cho bộ nhớ thực có 4 frame, bộ nhớ ảo có 8 page. Vẽ sơ đồ phân trang theo chiến lược FIFO và LRU. Biết thứ tự truy xuất các trang theo thời gian như sau: 7, 0, 5, 2, 0, 3, 0, 4, 6, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1. Giảng viên: Lương Trần Hy Hiến – Trang 10 Bài 7. Cho bộ nhớ thực có 3 frame, bộ nhớ ảo có 5 page. Vẽ sơ đồ phân trang theo chiến lược FIFO và LRU. Biết thứ tự truy xuất các trang theo thời gian như sau: 1, 2, 1, 0, 4, 1, 3, 4. Bài 8. Sử dụng 3 khung trang, khởi đầu đều trống: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 a. Thuật toán tối ưu. b. Thuật toán FIFO. c. Thuật toán lâu nhất chưa sử dụng. Bài 9. Chương trình A cần thực hiện nội dung các trang theo thứ tự sau: 2 7 6 2 5 4 3 7 5 3 7 với số khung trang k=3. Hỏi áp dụng chiến lược thay thế trang nào tốt hơn? Bài 10. Giả sử A cần đọc các trang 2 5 2 7 3 6 4 6 2 4 2 3 với số khung trang k=3. Thực hiện thay thế trang theo FIFO và ít sử dụng nhất trong tương lai. Giảng viên: Lương Trần Hy Hiến – Trang 11 CHỦ ĐỀ 4: HỆ THỐNG TẬP TIN Bài 1. Cho một volume có dung lượng 400MB. Mỗi blocks có 8 sectors. Kích thước mỗi bảng FAT là 160 sectors. Kích thước vùng ROOTDIR là 160 sectors. Hỏi volume này nên dùng bảng FAT loại mấy bit? HD GIẢI • Tổng số sector của volume: 400 x 210 x 210 / 29 = 400 x 210 (sector). • Tổng số sector vùng data: 400 x 210 – (1 + 2 * 160 + 160) = 818719 (sector). • Tổng số block của vùng data: 818719 / 8 = 102339.9 ≅ 102340 (block). • Mỗi fat-entry trong bảng FAT quản lý 01 block trong vùng data, có 2 fat-entry đầu tiên không sử dụng. Chọn k là số nguyên thỏa mãn điều kiện sau: 2k-1 ≤ 102340 + 2 ≤ 2k Chọn k = 17 vì 216=65536 ≤ 102340 + 2 ≤ 217=131072. Vậy ta nên dùng bảng FAT 17 bit. Bài 2. Cho biết loại bảng FAT của một volume có dung lượng 8GB với 400 sectors/FAT và 200 sectors/rootdicrectory, mỗi block là 8 sectors. Bài 3. Cho biết loại bảng FAT của một volume có dung lượng 16GB với 800 sectors/FAT và 400 sectors/rootdicrectory, mỗi block là 16 sectors. Bài 4. Tại sao dùng FAT12 cho đĩa mềm 1.44MB (1 ¼ inches)? Bài 5. Cho một volume có dung lượng 127.5MB. Mỗi vùng FAT có kích thước 260 sectors (2 vùng FAT, chỉ có 01 Fat-entry đầu tiên không được dùng vào việc quản lý). Vùng ROOTDIR có kích thước 600 sectors. Trên vùng DATA, mỗi blocks bằng 4 sectors. Hỏi volume này nên dùng bảng FAT loại mấy bit? Bài 6. Cho một volume có dung lượng 7.85MB. Mỗi vùng FAT có kích thước 12 sectors (2 vùng FAT, 2 Fat-entry đầu tiên không được dùng vào việc quản lý). Vùng ROOTDIR có kích thước 52 sectors. Trên vùng DATA, mỗi blocks bằng 4 sectors. Hỏi volume này nên dùng bảng FAT loại mấy bit? Bài 7. Cho đĩa USB có các thông số sau: – Sc = 4 SB = 1 – NF = 2 SF = 9 – NRDET = 224 Hãy cho biết các cluster sau trong vùng Data tương ứng chiếm những sector logic nào trên đĩa: 5, 2, 10, 20. Hướng dẫn: - SC = số sector / cluster. - SB = số sector trước vùng FAT. - NF = số bảng FAT - SF = kích thư ớc bảng FAT - SV = tổng số sector / volume. i = SB + NF*SF + SRDET + (k- 2)*SC SRDET = NRDET*32/512 Bài giải: • Từ giả thuyết ta suy ra: SRDET = NRDET*32/512 = 224*32/512 = 14 (sector) • K = 5  i = 1 + 2*9 + 14 + (5-2)*4 = 45  Cluster 5 trong Data chiếm 4 sector logic là 45, 46, 47, 48 • K = 2  i = 1 + 2*9 + 14 + (2-2)*4 = 33  Cluster 2 trong Data chiếm 4 sector logic là 33, 34, 35, 36 • K = 10  i = 1 + 2*9 + 14 + (10-2)*4 = 65 NHÓM 1 Giảng viên: Lương Trần Hy Hiến – Trang 12  Cluster 10 trong Data chiếm 4 sector logic là 65, 66, 67, 68 • K = 20  i = 1 + 2*9 + 14 + (20-2)*4 = 105  Cluster 20 trong Data chiếm 4 sector logic là 105, 106, 107, 108 Bài 8. USB 127MB có 112 entry trên bảng thư mục gốc, cluster chiếm 8 sector, boot sector chiếm 8 sector và 2 bảng FAT. a. Cần sử dụng hệ thống FAT nào (FAT12/16/32) cho đĩa mềm này ? b. Kích thước bảng FAT ? (Cần dùng bao nhiêu sector để lưu bảng FAT) Bài giải: • Ta có: – SB = 8 (theo giả thiết). – NF = 2 (theo giả thiết) • SV = 127 MB = 127*1024*2 (sector) = 260096 (sector) • Bảng thư mục gốc chiếm 112 entry = (112*32) / 512 = 7 (sector) a. Thay các giá trị đã có vào đẳng thức: SB + NF*SF +SR + SD = SV (trong đó SD: kích thước vùng dữ liệu)  8 + 2SF + 7 + SD = 260096, hay 2SF + SD = 260081 (sector) (*)  SD ~ 260081/8 = 32510.125 cluster (vì Sc = 8 sector)  Do FAT12 (212 = 1024*2*2 = 4096)chỉ có thể quản lý tối đa 4096 cluster ~ 4096*4 = 16384 sector nên vol này không thể định dạng theo FAT12 được. Do đó, vol sẽ được định dạng theo FAT16 b. Giả sử SF = 1 (sector): (*) − SD = 260081 - 2SF = 260079 (sector) = 32509.875 (cluster) − Vùng dữ liệu có 32510 cluster, nên bảng FAT phải có 32510 + 2 = 32512 phần tử, do đó SF = (32512 * 2) / 512 = 127 (sector) − SF = 127 sector. Mâu thuẫn với giả thiết SF = 1. Vậy kích thước bảng FAT của vol này không thể là 1 sector • Giả sử SF = 127 (sector): (*) − SD = 260081 - 2SF = 259827 (sector) = 32478.375 (cluster) − Vùng dữ liệu có 32479 cluster, nên bảng FAT phải có 32479 + 2 = 32481 phần tử, do đó SF = (32481 * 2) / 512 = 126.x (sector) − SF = 127 sector. Phù hợp với giả thiết SF = 127  Vậy kích thước bảng FAT của vol này là 127 sector Chú ý: − Fat 32 quản lý tối đa 232 phần tử mà mỗi phần tử cần 4 byte. Vậy Fat 32 có kích thước tối đa = 232 * 4 = ? byte = ? sector). − Fat 16 quản lý tối đa 216 phần tử mà mỗi phần tử cần 2 byte. Vậy Fat 16 có kích thước tối đa = 216 * 2 = 65536*2 = 131072 byte = 256 sector). − Fat 12 quản lý tối đa 212 phần tử mà mỗi phần tử cần 1.5 byte. Vậy Fat 12 có kích thước tối đa = 212 * 2 = 4096*2 = 8192 byte = 16 sector). Bài 9. Xét đĩa mềm 1.44MB (có 2880 sector), để các tập tin trên vol có thể truy xuất nhanh & an toàn hơn ta giả sử cho: – SC = 4 (sector) – SB = 1 (sector) – SR = 32 (entry) = 32 * 32 (byte) = 1024 (byte) = 2 (sector) – NF = 2 Giảng viên: Lương Trần Hy Hiến – Trang 13 a. Cần sử dụng hệ thống FAT nào (FAT12/16/32) cho đĩa mềm này? b. Kích thước bảng FAT? (Cần dùng bao nhiêu sector để lưu bảng FAT) Bài giải: Câu a: • Thay các giá trị trên vào đẳng thức SB + NF*SF + SR + SD = SV ta được 1 + 2SF +2 + SD = 2880 (sector), hay 2SF + SD = 2877 (sector) (*)  SD < 2877 (sector) = 719.25 (cluster) (vì SC = 4 sector).  Loại FAT tối ưu nhất (về kích thước) là FAT12, vì SD < 4096 (cluster) Câu b: • Giả sử SF = 1 (sector): (*) − SD = 2875 (sector) = 718.75 (cluster) − Vùng dữ liệu có 719 cluster, nên bảng FAT phải có 719 + 2 = 721 phần tử. − Do đó SF = (721*1.5)/512 = 2.1x (sector) − Bảng FAT phải chiếm 3 sector – mâu thuẫn với giả thiết SF = 1. Vậy kích thước bảng FAT của vol này không thể là 1 sector • Giả sử SF = 2 (sector): tương tự, ta vẫn thấy mâu thuẫn, tức kích thước bảng FAT phải lớn hơn 2 sector. • Giả sử SF = 3 (sector): (*) ◊ SD = 2871 (sector) = 717.75 (cluster). − Vùng dữ liệu có 718 cluster, nên bảng FAT phải có 718 + 2 = 720 phần tử, do đó SF = (720*1.5)/512 = 2.1x (sector)  Bảng FAT phải chiếm 3 sector – phù hợp với giả thiết SF = 3.  Vậy kích thước bảng FAT của vol này là 3 sector. Bài 10. Xét đĩa USB có dung lượng 256 MB, kèm các thông số trên đĩa: – SC = 4 (sector) – SB = 4 (sector) – NRDET = 256 (entry) – NF = 2 a. Cần sử dụng hệ thống FAT nào (FAT12/16/32) cho USB này b. Kích thước bảng FAT ? (Cần dùng bao nhiêu sector để lưu bảng FAT) Bài giải: Câu a: • Ta có: – SB = 4 (theo giả thiết). – NF = 2 (theo giả thiết) • SV = 256 MB = (256*1024*1024) / 512 (sector) = 524288 (sector) • Bảng thư mục gốc chiếm NRDET = 256 entry • SRDET = (256 * 32) / 512 = 16 (sector) • Thay các giá trị đã có vào đẳng thức: SB + NF*SF +SR + SD = SV − 4 + 2SF + 16 + SD = 524288, hay 2SF + SD = 524268 (sector) (*) − SD < 524268 (sector) / 4 = 131 067 (cluster) (vì Sc = 4 sector).  Vì 216 < 131 067 (cluster) < 232. Do đó, vol sẽ được định dạng theo FAT32 Câu b: • Giả sử SF = 1 (sector): (*) ◊ SD = 524268 - 2SF = 524266 (sector) = 131066.5 (cluster) − Vùng dữ liệu có 131067 cluster, nên bảng FAT phải có 131067 + 2 = 131069 phần tử, do đó SF = (131069 * 4) / 512 = 1023.9 (sector) Giảng viên: Lương Trần Hy Hiến – Trang 14 − SF = 1024 sector. Mâu thuẫn với giả thiết SF = 1. Vậy kích thước bảng FAT của vol này không thể là 1 sector • Giả sử SF = 1024 (sector): (*) ◊ SD = 524268 - 2SF = 522220 (sector) = 130555 (cluster) − Vùng dữ liệu có 130555 cluster, nên bảng FAT phải có 130555 + 2 = 130557 phần tử, do đó SF = (130557 * 4) / 512 = 1019.9 (sector) − SF = 1020 sector. Trái với giả thiết SF = 1024 Trạng thái của cluster k trên vùng dữ liệu Giá trị bảng FAT Ghi chú FAT12 FAT16 FAT32 Trống 0 0 0 = FREE Hư FF7 FFF7 0FFFFFF7 = BAD Cluster cuối của file FFF FFFF 0FFFFFFF = EOF Chứa nội dung file 2 … FEF 2 … FFEF 2 … 0FFFFFEF Truy xuất theo FAT16 (mỗi phần tử 2 bytes): Bài 11. Cho bảng FAT theo dạng số Hexa như sau: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 F0 FF FF 3 40 0 5 60 0 FF F 0 E B0 0 F7 F 0 0 A0 0 a. Vẽ bảng FAT cho dãy byte trên. b. Cho biết các block bị BAD, FREE. c. Khi thay giá trị (dạng số Hexa) ô[7]=C và ô[12]=FF7 vào bảng FAT trên thì dãy byte bị biến đổi như thế nào? d. Cho biết các Fat-entry của cùng một file (hay thư mục). Bài 12. Cho bảng FAT theo dạng số Hexa như sau: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 F0 FF FF 0 B0 0 5 40 0 F7 F 0 E B0 0 FF F 0 A C0 0 a. Vẽ bảng FAT cho dãy byte trên. b. Cho biết các block bị BAD, FREE. c. Khi thay giá trị (dạng số Hexa) ô[6]=10 và ô[11]=FF7 vào bảng FAT trên thì dãy byte bị biến đổi như thế nào? d. Cho biết các Fat-entry của cùng một file (hay thư mục). NHÓM 2 Giảng viên: Lương Trần Hy Hiến – Trang 15 Bài 13. Cho bảng FAT biểu diễn theo dạng mảng các byte (số Hexa) như sau: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 F0 FF FF 05 70 FF 00 70 00 0A 80 00 09 F0 FF 0B F0 FF F7 5F 0F a. Biểu diễn bảng FAT theo dạng mảng các Fat-entry. b. Cho biết các block bị BAD, FREE, cuối tập tin (hay thư mục). c. Nếu sửa Fat-entry[4]=FFF hexa và Fat-entry[9]=004 hexa, hãy cho biết byte nào của mảng các byte bị thay đổi, giá trị sau khi thay đổi là bao nhiêu? d. Cho biết các Fat-entry của cùng một file (hay thư mục). Bài 14. Cho bảng FAT biểu diễn theo dạng mảng các byte (số Hexa) như sau: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 F0 FF FF 03 40 00 06 00 00 08 A0 00 FF 5F 0F FF 7F FF F7 0F 00 a. Biểu diễn bảng FAT theo dạng mảng các Fat-entry. b. Cho biết các block bị BAD, FREE, cuối tập tin (hay thư mục). c. Nếu sửa Fat-entry[2]=A50 hexa và Fat-entry[9]=005 hexa, hãy cho biết byte nào của mảng các byte bị thay đổi, giá trị sau khi thay đổi là bao nhiêu? d. Cho biết các Fat-entry của cùng một file (hay thư mục). Bài 15. Cho bảng FAT biểu diễn theo dạng mảng các byte (số Hexa) như sau: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 F0 FF FF A 40 0 FF F 0 F7 7F FF B5 B1 0 F7 CF 0 FF F 9B a. Biểu diễn bảng FAT theo dạng mảng các Fat-entry. b. Cho biết các block bị BAD, FREE, cuối tập tin (hay thư mục). c. Nếu sửa Fat-entry[2]=BC0 hexa và Fat-entry[7]=42A hexa, hãy cho biết byte nào của mảng các byte bị thay đổi, giá trị sau khi thay đổi là bao nhiêu? d. Cho biết các Fat-entry của cùng một file (hay thư mục). Bài 16. Cho bảng FAT biểu diễn theo dạng mảng các byte (số Hexa) như sau: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 F0 FF FF CE 5 0 5 60 0 FF 8F 0 A C0 91 B F0 FF F7 7F FF a. Biểu diễn bảng FAT theo dạng mảng các Fat-entry. b. Cho biết các block bị BAD, FREE, cuối tập tin (hay thư mục). c. Nếu sửa Fat-entry[2]=12A hexa và Fat-entry[9]=8AC hexa, hãy cho biết byte nào của mảng các byte bị thay đổi, giá trị sau khi thay đổi là bao nhiêu? d. Cho biết các Fat-entry của cùng một file (hay thư mục). Giảng viên: Lương Trần Hy Hiến – Trang 16 CHỦ ĐỀ 5: CÁC THUẬT TOÁN ĐỌC ĐĨA • FCFS – đọc theo đúng thứ tự yêu cầu (FIFO) • SSTF – chọn yêu cầu ít di chuyển nhất từ vị trí hiện tại (tức seektime nhỏ nhất) • SCAN – di chuyển 2 phía, từ phía này sang phía kia rồi ngược lại (thông thường định hướng về 0, giảm dần trước về 0 rồi tăng dần lên) • C-SCAN – Tương tự như SCAN nhưng chỉ 1 phía (theo chiều tăng dần cho đến vị trí lớn nhất rồi giảm về 0, bắt đầu lại), có đụng biên. • LOOK, C-LOOK - giống SCAN, C-SCAN nhưng không cần đụng biên. Bài 1. Cho biết dãy cyclinder cần truy xuất lần lượt là: 9, 15, 21, 2, 25, 6, 12. Với vị trí hiện hành của đầu đọc đang đứng tại cyclinder 10. Hãy cho biết thứ tự truy xuất các cyclinder trên nếu dùng các thuật toán lần lượt là: a. FCFS. b. SSTF. c. SCAN. d. C-SCAN. e. LOOK. Bài 2. Cần đọc các khối 99, 195, 10, 50, 19 và 77. Giả sử đầu đọc đang ở vị trí 53. Đầu đọc sẽ lần lượt qua các khối nào và vẽ sơ đồ theo các thuật toán đọc đĩa: a. FCFS. b. SSTF. c. SCAN. d. C-SCAN. e. Trong trường hợp này thuật toán nào là tối ưu nhất? Bài 3. Một đĩa có 1950 cylinders được đánh số từ 0 đến 1949. Giả sử đầu đọc đang ở cylinder 410 (yêu cầu trước đó ở cylinder 125). Hàng đợi các yêu cầu đọc theo thứ tự 88, 1450, 923, 1674, 998, 1609, 1122, 1750, 136. Hãy tính tổng khoảng cách (bằng cylinder) cần di chuyển để thỏa mãn yêu cầu trên theo các thuật toán đọc đĩa sau: a. FCFS (ĐS: 6978) b. SSTF (ĐS: 1984) c. SCAN (ĐS: 3400) d. LOOK (ĐS: 3002) e. C-SCAN (ĐS: 3448) Bài 4. Một đĩa có 200 tracks được đánh số từ 0 đến 199. Giả sử đầu đọc đang ở track 143 (yêu cầu trước đó ở track 125). Hàng đợi các yêu cầu đọc theo thứ tự 86, 147, 91, 177, 94, 150, 102, 175, 130. Hãy tính tổng khoảng cách (bằng track) cần di chuyển để thỏa mãn yêu cầu trên theo các thuật toán đọc đĩa sau: a. FCFS (ĐS: 565) b. SSTF (ĐS: 162) c. SCAN (ĐS: 169) d. LOOK (ĐS: 125) e. C-SCAN (ĐS: 385) Hết

Tài liệu liên quan

Bài tập lập trình C++ (thầy Lương Trần Hy Hiến )
- 18
- 1
- 23
Bài giảng Phân tích thiết kế hệ điều hành: Chủ đề 2 - ThS. Lương Trần Hy Hiến
- 30
- 84
- 0
Bài giảng Phân tích thiết kế hệ điều hành: Chủ đề 3 - ThS. Lương Trần Hy Hiến
- 80
- 54
- 0
Bài giảng Phân tích thiết kế hệ điều hành: Chủ đề 4 - ThS. Lương Trần Hy Hiến
- 21
- 55
- 0
Bài giảng Phân tích thiết kế hệ điều hành: Chủ đề 8 - ThS. Lương Trần Hy Hiến
- 32
- 51
- 0
Bài giảng Phân tích thiết kế hệ điều hành: Chủ đề 6 - ThS. Lương Trần Hy Hiến
- 91
- 77
- 0
Bài giảng Phân tích thiết kế hệ điều hành: Chủ đề 5 - ThS. Lương Trần Hy Hiến
- 69
- 69
- 0
Bài giảng Hệ điều hành - Lương Trần Hy Hiến
- 374
- 51
- 0
Bài giảng Phân tích thiết kế hệ điều hành: Chủ đề 7 - ThS. Lương Trần Hy Hiến
- 22
- 37
- 0
Bài giảng Phân tích thiết kế hệ điều hành: Chủ đề 1 - ThS. Lương Trần Hy Hiến
- 89
- 98
- 0