Bài giảng Hệ điều hành - Chương 10: Hệ thống file (Phần 2)

Nội dung text: Bài giảng Hệ điều hành - Chương 10: Hệ thống file (Phần 2)

1. Cấp phát dùng chỉ mục (2) ☺ Ưu điểm – Random và sequential access – Không có phân mảnh ngoại  Khuyết điểm – Tốn không gian lưu trữ bảng index khi file có kích thước chỉ vài block ❑ Vấn đề: kích thước index block bao nhiêu là phù hợp? – Giải quyết: multilevel index Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.11
2. i-node i-node ❑ UNIX v7 i-node: 13 pointers ❑ Linux ext2 i-node: 15 pointers Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.12
3. Hiện thực thư mục ❑ Thư mục được dùng để chứa bảng ánh xạ từ tên file (chuỗi ký tự ASCII) đến thông tin cần thiết để định vị các block dữ liệu của file ❑ Tổ chức thư mục – Danh sách tuyến tính (array hay linear list), bảng băm, MS-DOS UNIX, Linux first block nr Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.13
4. FAT ❑ Ví dụ Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.14
5. Hệ thống file FAT ❑ FAT dùng để chỉ bảng FAT và cũng dùng để chỉ hệ thống file ❑ Layout của một partition chứa hệ thống file FAT Boot sector FAT Root directory Data blocks Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.15
6. Hiện thực tên file dài ❑ Giải quyết vấn đề tên file dài (Win98, 2000, XP, *NIX, ) (a) In-line (b) Heap Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.16
7. i-node (1) Ví dụ Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.17
8. i-nodes (2) ❑ Layout của một partition chứa hệ thống file UNIX Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.18
9. i-node: chia sẻ file (1) Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.19
10. i-node: chia sẻ file (2) Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.20
11. Duyệt path name để lấy block nr của file ❑ Ví dụ: Xác định các block dữ liệu của file /a/b/c Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.21
12. Quản lý không gian trống Các phương pháp ❑ Bit vector (bit map) ❑ Linked list ❑ Grouping ❑ Counting Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.22
13. Phương pháp bit vector (bit map) ☺ Đơn giản và hiệu quả khi cần 0 1 2 n - 1 tìm khối trống đầu tiên hoặc chuỗi khối trống liên tục – Thao tác trên bit 0 block i còn trống bit[ i ] = 1 block i đã được cấp  Cần không gian lưu trữ. Ví dụ  – Kích thước block = 212 bytes – Kích thước đĩa = 230 bytes Ví dụ: – n = 230/212 = 218 bit (32KB) bit vector 00111100 block 0, 1 trống block 2, 3, 4, 5 đã được cấp block 6, 7 trống Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.23
14. Phương pháp dùng linked list ❑ Phương pháp – Liên kết các khối trống với nhau – Chỉ cần giữ con trỏ đến khối nhớ trống đầu tiên trên đĩa hoặc cache trong bộ nhớ chính để tăng tốc ☺ Ít lãng phí không gian đĩa Dò biết khoảng không gian trống liên tục?  Không hiệu quả: trong trường hợp xấu nhất phải duyệt toàn bộ đĩa để tìm không gian trống liên tục Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.24
15. Grouping và counting (1) ❑ Phương pháp grouping – Địa chỉ của n khối trống được lưu trong khối nhớ đầu tiên. – Khối nhớ thứ n chứa địa chỉ của n khối nhớ trống kế tiếp. ❑ Phương pháp counting – Tổ chức bảng chỉ mục, trong đó mỗi phần tử của bảng chứa địa chỉ trên đĩa của khối trống đầu tiên trong nhóm khối trống liên tục kèm theo một số đếm (cho biết số khối trống trong nhóm). – Có thể cấp phát hoặc thu hồi đồng thời nhiều khối nhớ liên tục Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.25
16. Grouping và counting (2) Ví dụ Grouping Block 2 → 3, 4, 5 Block 5 → 8, 9, 10 Block 10 → 11, 12, 13 Block 13 → 17, 28, 25 Block 25 → 26, 27 Counting 2 4 8 6 17 2 25 3 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.26
17. Open file structures ❑ Thuộc tính toàn cục (global attributes) – Disk location, size – Times – Buffers – Open count – Lock(s) ❑ Thuộc tính riêng của process – File pointer – Access permissions P1 P2 System open file table P3 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.27
18. UNIX: open file structure swappable Kernel space file open file descriptor r/w table resident file structure in-core table i-nodes User space data blocks i-nodes Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.28
19. Sao lưu và phục hồi dữ liệu ❑ Kiểm tra sự nhất quán dữ liệu (consistency checker) – so sánh dữ liệu trong cấu trúc thư mục với các khối dữ liệu trên đĩa và sửa chữa các lỗi không nhất quán dữ liệu giữa hai bên. ❑ Dùng chương trình hệ thống để sao lưu (backup) dữ liệu từ đĩa sang các thiết bị lưu trữ phụ khác như đĩa mềm, đĩa quang, băng từ, và phục hồi dữ liệu bị mất từ bản sao lưu. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.29
20. Các kiểu sao lưu dữ liệu ❑ Normal ❑ Incremental Day 3 Day 3 Day 2 Day 2 Copied Day 1 Day 1 Data Data ❑ Differential Day 3 Day 2 Copied Day 1 Data Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.30
21. Journaling file system ❑ Journaling file system – Ghi nhận các lần cập nhật trên file system thành các giao tác (transaction) – Mọi transaction đều phải được ghi nhận trong log file – Một transaction được xem là hoàn tất (commit)  đã được ghi nhận đầy đủ trong log file (lúc này, file system có thể chưa được cập nhật) – Khi file system được cập nhật với đầy đủ mọi tác vụ trong transaction thì transaction sẽ được xóa đi trong log file. – Nếu file system bị hỏng → hệ điều hành dựa vào các transaction trong log file để sửa chữa ❑ Tham khảo thêm Linux-ext3, JFS, NTFS Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.31
22. Phụ lục
23. MS-DOS File System (1) MS-DOS directory entry Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.33
24. MS-DOS File System (2) ❑ Maximum partition for different block sizes ❑ The empty boxes represent forbidden combinations Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.34
25. Windows 98 File System (1) Bytes Extended MOS-DOS directory entry used in Windows 98 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.35
26. Windows 98 File System (2) Bytes Checksum An entry for (part of) a long file name in Windows 98 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.36
27. The Windows 98 File System (3) An example of how a long name is stored in Windows 98 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.37
28. UNIX V7 File System (1) i-node number A UNIX V7 directory entry Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.38
29. UNIX V7 File System (2) i-node A UNIX i-node Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.39
30. UNIX V7 File System (3) The steps in looking up /usr/ast/mbox Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.B.40