Bài giảng Tổ chức hệ thống tập tin trên volume

TỔ CHỨC HỆ THỐNG TẬP TIN TRÊN VOLUME 22/09/2009 Presented by: Dang Nhan Cach Khoa CNTT ĐH GTVT TP. HCM 2 Các nhận xét và phân tích cần thiết n Phải xác định các vị trí còn trống n Mỗi Sector (hoặc tồng quát hơn là mỗi block) chỉ thuộc một tập tin n Tên và các thuộc tính tập tin cần lưu riêng vào một vùng n Phải có thông tin của vị trí bắt đầu tập tin Khoa CNTT ĐH GTVT TP. HCM 3 Các nhận xét và phân tích cần thiết(tt) n Nội dung tập tin không bắt buộc phải lưu liên tục n Phải biết các vị trí chứa nội dung tập tin n Phải biết các vị trí hư n Nội dung tập tin nên lưu trự theo Cluster (là dãy N sector liên tiếp-để dễ quản lý và truy xuất nhanh hơn) Khoa CNTT ĐH GTVT TP. HCM 4 Cluster – Khái niệm nĐơn vị đọc ghi trên đĩa là sector, nhưng đơn vị lưu trự nội dung tập tin không phải là một sector mà là một cluster gồm N sector liên tiếp (N>=1) n Mỗi vị trí trong phân tích trên sẽ là 1 cluster n Cluster chỉ tồn tại trên vùng dữ liệu(DATA)- nơi chứa nội dung tập tin Khoa CNTT ĐH GTVT TP. HCM 5 Cluster – Lý do phát sinh n Nếu Sector trên vùng dữ liệu quá nhiều thì có thể sẽ khó hoặc không quản lý được. Khi đó quản lý trên Cluster sẽ dễ dàng và hiệu quả hơn n Nội dung tập tin thường chiếm nhiều Sector và có thể không liên tục nên đặc đơn vị lưu trữ là Cluster sẽ hạn chế được sự phân mảnh, đồng thời truy xuất một lần N Sector liên tiếp sẽ nhanh hơn so với truy xuất N lần mà mỗi lần là một Sector Khoa CNTT ĐH GTVT TP. HCM 6 Cluster- Hình thức tổ chức n Volume sẽ được chia thành 2 vùng: vùng dữ liệu(DATA) chứa nội dung tập tin và vùng hệ hống(SYSTEM) chứa các thông tin quản lý. n SYSTEM có kích thước nhỏ hơn nhiều so với DATA và phải truy xuất mỗi khi sử dụng Volume nên thường nằm ngay đầu Volume n Trên vùng DATA là dãy các Cluster liên tiếp được đánh chỉ số theo thứ tự tăng dần(bắt đầu từ 0,1 hay 2 … tùy theo HĐH) Khoa CNTT ĐH GTVT TP. HCM 7 Cluster-ví dụ Khoa CNTT ĐH GTVT TP. HCM 8 Cluster – kích thước Cluster n Phụ thuộc nhiều yếu tố: n Dung lượng Volume, n Tốc độ truy xuất một dãy Sector, n Kích thước của đa số tập tin sẽ trữ vào, n Số Cluster tối đa có thể quản lý, n Nhu cầu của người sử dụng n Kích thước Cluster càng lớn càng lãng phí đĩa, nhưng sẽ hạn chế sự phân mảnh tập tin và vì vậy có hể an toàn và truy xuất nhanh hơn Khoa CNTT ĐH GTVT TP. HCM 9 Cluster – kích thước Cluster (tt) n Trên các đĩa hiện tại thì Sector thường có kích thước 512B và Cluster thường có chiếm 4,8 hoặc 16 Sector ( thường mũ của 2 trên Window) n Trên các đĩa thẻ nhớ Flash thông dụng (dung lượng 128MB đến 2GB) kích thước Cluster nên 8 hoặc 16KB. Nếu có nhiều tập tin nhỏ thì nên ghép lại thành 1 tập tin lớn hơn Khoa CNTT ĐH GTVT TP. HCM 10 Bản quản lý Cluster- Khái niệm n Được đưa ra để xác định danh sách các Cluster chứa nội dung một tập tin và Cluster còn trống n Có thể dùng một bảng chung hoặc cũng có thể tổ chức nhiều bảng. Thông thường mỗi phần tử trên bảng quán lý một Cluster tương ứng trên vùng DATA Khoa CNTT ĐH GTVT TP. HCM 11 Bản quản lý Cluster- lý do phát sinh n Phải xác định Cluster còn trống để có thể chép tập tin vào Volume n Phải xác định được danh sách các Cluster chứa nội dung của 1 tập tin để đọc tập tin n Có thể lưu thông tin quản lý ngay trên Cluster nhưng khí đó quản lý và truy xuất rất chậm nên nhất thiết phải tạo ra bản này để truy xuất nhanh hơn Khoa CNTT ĐH GTVT TP. HCM 12 Bản quản lý Cluster- hình thức tổ chức n Quản lý Cluster hư: n Lưu một danh sách trực tiếp: giá trị mỗi phần tử là chỉ số của , một Cluster hư, vì Cluster hư rât ít nên danh sách này có thể quy định 1 hoặc vài Sector n Kết hợp với các trạng thái luận lý khác trong một bảng chỉ mục. n Quản lý Cluster trống: n Dùng hình thức Bitmap : mỗi bit quản lý một Cluster tương ứng, Cluster K trống khi giá trị bit K là 0. bit K nằm tại byte (K div 8) và là bit (K mod 8) trên byte đó. n Quản lý theo dạng chỉ mục : mỗi phần tử của bản quản lý là một con số, nói lên trạng thái của Cluster mang chỉ số tương ứng. n Quản lý vùng trống :tổ chức một danh sách các phần tử, mỗi phần tử chứa vị trí bắt đầu và kích thước của vùng trống tương ứng Khoa CNTT ĐH GTVT TP. HCM 13 Bản quản lý Cluster- hình thức tổ chức(tt) n Quản lý chuỗi các Cluster chứa nội dung tập tin : n Lưu nội dung tập tin trên dãy các Cluster liên tiếp (danh sách đặc). n Sử dụng cấu trúc danh sách liên kết (xâu) n Sử dụng cấu trúc sâu kết hợp với chỉ mục (index) n Sử dụng cấu trúc cây (kết hợp chỉ mục) Khoa CNTT ĐH GTVT TP. HCM 14 Khoa CNTT ĐH GTVT TP. HCM 15 Khoa CNTT ĐH GTVT TP. HCM 16 Khoa CNTT ĐH GTVT TP. HCM 17 Khoa CNTT ĐH GTVT TP. HCM 18 Khoa CNTT ĐH GTVT TP. HCM 19 Khoa CNTT ĐH GTVT TP. HCM 20 Khoa CNTT ĐH GTVT TP. HCM 21 Bản thư mục – khái niệm Khoa CNTT ĐH GTVT TP. HCM 22 Bản thư mục – lý do phát sinh Khoa CNTT ĐH GTVT TP. HCM 23 Khoa CNTT ĐH GTVT TP. HCM 24 Boot Sector – khái niệm n Chứa một đoạn chương trình nhỏ để nạp Hệ Điều Hành khi khởi động máy (Boot) n Chứa các thông số quan trọng của volume: loại volume, kích thước volume, kích thước Cluster, kích thước bản quản lý cluster …. n Vùng BootSector (chứa một số sector) nằm ngay đầu volume, BootSector là sector đầu tiên (trong trường hợp không thể tổ chức đủ thông tin trong sector đầu thì tổ chức tiếp trrên các sector còn lại trong vùng. Khoa CNTT ĐH GTVT TP. HCM 25 Khoa CNTT ĐH GTVT TP. HCM 26 Khoa CNTT ĐH GTVT TP. HCM 27 Boot Sector – Hình thức tổ chức n Đoạn chương trình Boot trong Sector này sẽ nạp và chạy tiếp các đoạn chương trình trong các Sector khác (vì đoạn ct trong 1 sector rất nhỏ) n Mỗi thông số được quy định nằm tại offset cụ thể cố định nào đó (Với kích thước lưu trữ và kiểu dữ liệu tương ứng) n Nếu cần thiết, có thể tổ chức các thông số trên các Sector khác trong vùng BootSector Tổ chức hệ thống tập tin MS-DOS Khoa CNTT ĐH GTVT TP. HCM 29 MS-DOS Khoa CNTT ĐH GTVT TP. HCM 30 Khoa CNTT ĐH GTVT TP. HCM 31 Bảng FAT n Tổ chức theo hình thức danh sách liên kết kết hợp chỉ mục n Được lưu thành nhiều bảng n Số lượng bản FAT của Volume được lưu trữ bằng số nguyên (NF) 1 byte tại offset 10h của BootSector n Lưu ý: Kích thước thực sự của bảng FAT có thể nhỏ hơn không gian dành cho bảng FAT Khoa CNTT ĐH GTVT TP. HCM 32 Bảng FAT- vị trí và kích thước n Vị trí bắt đầu của vùng FAT chính là kích thước vùng BootSector (viết tắt là SB) n SB được tính bằng đơn vị Sector lưu bằng số 2 byte tại offset Eh của BootSector n Số Sector của mỗi bảng FAT (SF) được lưu trự bằng số nguyên 2 byte tại offset 16h của BootSector =>Kích thước vùng FAT là NF*SF Khoa CNTT ĐH GTVT TP. HCM 33 Nội dung bảng FAT n Mỗi phần tử của bảng FAT được biểu diễn bằng số nguyên 12bit hoặc 16 bit tương ứng với bảng FAT12 hoặc FAT16 n Mỗi phần tử của FAT quản lý 1 cluster theo đúng giá trị chỉ số n Phần tử đầu của bảng phải mang chỉ số là 0 Khoa CNTT ĐH GTVT TP. HCM 34 Khoa CNTT ĐH GTVT TP. HCM 35 Khoa CNTT ĐH GTVT TP. HCM 36 Khoa CNTT ĐH GTVT TP. HCM 37 Khoa CNTT ĐH GTVT TP. HCM 38 Khoa CNTT ĐH GTVT TP. HCM 39 Khoa CNTT ĐH GTVT TP. HCM 40 Khoa CNTT ĐH GTVT TP. HCM 41 Khoa CNTT ĐH GTVT TP. HCM 42 Khoa CNTT ĐH GTVT TP. HCM 43 Khoa CNTT ĐH GTVT TP. HCM 44 Khoa CNTT ĐH GTVT TP. HCM 45 Khoa CNTT ĐH GTVT TP. HCM 46 Khoa CNTT ĐH GTVT TP. HCM 47 Khoa CNTT ĐH GTVT TP. HCM 48 Khoa CNTT ĐH GTVT TP. HCM 49 Thank You! Khoa CNTT ĐH GTVT TP. HCM 50