Hệ điều hành - Chương 2: Quản lý tập tin - Trần Công Án

Hệ Điều Hành Chương 2. Quản lý tập tin Giảng viên TS. Trần Công Án tcan@cit.ctu.edu.vn Khoa Công Nghệ Thông Tin & Truyền Thông Đại học Cần Thơ 2018 [HĐH] Ch2. Quản lý tập tin Mục Tiêu Giúp sinh viên hiểu rõ tập tin là gì và các mô hình tổ chức, quản lý và cài đặt tập tin trong các Hệ điều hành. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 2 [HĐH] Ch2. Quản lý tập tin Nội Dung Các khái niệm cơ bản Các Phương Pháp Truy Cập Tập Tin Mô hình tổ chức và Quản lý tập tin Cài đặt hệ thống tập tin TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 3 [HĐH] Ch2. Quản lý tập tin Các khái niệm cơ bản Các khái niệm cơ bản TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 4 [HĐH] Ch2. Quản lý tập tin Các khái niệm cơ bản Giới Thiệu I Máy tính có thể lưu trữ thông tin trên các thiết bị lưu trữ không bay hơi như đĩa từ, băng từ, đĩa quang, . . . I Một trong những chức năng quan trọng của HĐH là cung cấp một giao diện đồng nhất để người dùng có thể lưu trữ và truy xuất dữ liệu trên các loại thiết bị này. I Hệ thống cung cấp chức năng trong các HĐH này được gọi là Hệ thống lưu trữ hay Hệ thống quản lý tập tin. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 5 [HĐH] Ch2. Quản lý tập tin Các khái niệm cơ bản Các Khái Niệm Cơ Bản I Tập tin: là một tập hợp thông tin có liên quan được đặt tên, được lưu trữ trên một thiết bị lưu trữ không bay hơi. I Một tập tin là một đơn vị lưu trữ luận lý, nằm trong một không gian địa chỉ luận lý liên tục. I Hệ thống quản lý tập tin (HĐH) sẽ ánh xạ các tập tin vào các thiết bị lưu trữ vật lý (không gian lưu trữ có thể không liên tục). I Thông thường, một tập tin chứa dữ liệu (văn bản, hình ảnh, . . . ) hoặc một chương trình máy tính. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 6 [HĐH] Ch2. Quản lý tập tin Các khái niệm cơ bản Các Loại Tập Tin file type usual extension function ready-to-run machine- language program executable exe, com, bin or none compiled, machine language, not linked object obj, o binary file containing audio or A/V information multimedia mpeg, mov, mp3, mp4, avi related files grouped into one file, sometimes com- pressed, for archiving or storage archive rar, zip, tar ASCII or binary file in a format for printing or viewing print or view gif, pdf, jpg libraries of routines for programmers library lib, a, so, dll various word-processor formats word processor docx commands to the command interpreter batch bat, sh textual data, documentsmarkup xml, html, tex source code in various languages source code c, cc, java, perl, asm xml, rtf, TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 7 [HĐH] Ch2. Quản lý tập tin Các khái niệm cơ bản Các thao tác trên tập tin Các Thao Tác Trên Tập Tin I Create: tạo mới tập tin I tìm không gian lưu trữ còn trống trên thiết bị lưu trữ I tạo một bản ghi tập tin trên cấu trúc thư mục sẽ lưu trữ tập tin I thông tin cần thiết cho thao tác này là tên tập tin và vị trí tập tin I Write: ghi tập tin I lưu dữ liệu của tập tin (từ bộ nhớ) lên thiết bị lưu trữ I thông tin cần thiết cho thao tác này là tên tập tin và dữ liệu cần ghi TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 8 [HĐH] Ch2. Quản lý tập tin Các khái niệm cơ bản Các thao tác trên tập tin Các Thao Tác Trên Tập Tin I Read: đọc tập tin I đọc dữ liệu của tập tin từ thiết bị lưu trữ ra một vùng đệm (buffer) I thông tin cần thiết cho thao tác này là tên tập tin cần đọc và vùng đệm lưu dữ liệu I Delete: xóa tập tin I xóa mẩu tin tập tin trong cấu trúc thư mục và giải phóng không gian lưu trữ đã cấp phát cho tập tin I thông tin cần thiết cho thao tác này là tên tập tin cần xóa I một số hệ điều hành cung cấp hai thao tác xóa: luận lý hay vật lý TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 9 [HĐH] Ch2. Quản lý tập tin Các khái niệm cơ bản Các thao tác trên tập tin Các Thao Tác Trên Tập Tin I Truncate: xóa nội dung tập tin I giải phóng toàn bộ không gian lưu trữ của tập tin, chỉ giữ lại bản ghi tập tin trên cấu trúc thư mục I thông tin cần cho thao tác này là tên tập tin cần được xóa nội dung I Seek/Reposition: di chuyển con trỏ vị trí hiện hành của 1 tập tin I các thao tác đọc/ghi trên tập tin được thực hiện thông qua con trỏ vị trí hiện hành của tập tin (current-file-position pointer), vị trí sẽ được truy xuất kế tiếp I thông tin cần cho thao tác này là vị trí cần di chuyển con trỏ đến (tương đối/tuyệt đối) TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 10 [HĐH] Ch2. Quản lý tập tin Các khái niệm cơ bản Các thao tác trên tập tin Các Thao Tác Trên Tập Tin I Open: mở tập tin I Các thao tác trên tập tin cần phải thông qua bước tìm kiếm tập tin ⇒ hao phí thời gian I Vì vậy, trước khi thao tác trên tập tin thì phải thực hiện mở tập tin I tìm kiếm tập tin I tạo một mục trong bảng các tập tin đang mở cho tập tin I trả về con trỏ đến mục của tập tin trong bảng các tập tin đang mở I Khi cần thao tác trên tập tin thì chỉ cần sử dụng con trỏ tập tin I Close: đóng tập tin I loại bỏ mục của tập tin tương ứng trong bảng các tập tin đang mở TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 11 [HĐH] Ch2. Quản lý tập tin Các Phương Pháp Truy Cập Tập Tin Các phương pháp truy cập tập tin TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 12 [HĐH] Ch2. Quản lý tập tin Các Phương Pháp Truy Cập Tập Tin Truy Cập Tuần Tự I Truy cập dữ liệu theo thứ tự, từng mẫu tin (record). I Các thao tác: read next (đọc phần tử kế tiếp), write next (ghi phía sau con trỏ vị trí hiện hành), reset (cho con trỏ hiện hành về đầu tập tin) beginning endcurrent position rewind read or write TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 13 [HĐH] Ch2. Quản lý tập tin Các Phương Pháp Truy Cập Tập Tin Truy Cập Trực Tiếp I Truy cập các mẫu tin bất kỳ, không theo thứ tự. I Thường áp dụng đối với các tập tin có kích thước mẫu tin cố định (để có thể tính được vị trí của mẫu tin cần truy xuất) I Các chỉ thị tương tương giữa hai phương pháp truy cập: sequential access reset read_next write_next cp 0; read cp ; cp cp 1; write cp ; cp cp 1; implementation for direct access TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 14 [HĐH] Ch2. Quản lý tập tin Các Phương Pháp Truy Cập Tập Tin Truy Cập Theo Chỉ Mục I Dựa trên phương pháp truy cập trực tiếp I Xây dựng thêm hệ thống chỉ mục (index) cho dữ liệu trên tập tin I Hệ thống chỉ mục bao gồm mục từ và vị trí của mục từ trong tập tin I Việc tìm kiếm trong tập tin sẽ dựa vào chỉ mục trước để tìm ra vị trí index file relative file Smith last name smith, john social-security age logical record number Adams Arthur Asher • • • TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 15 [HĐH] Ch2. Quản lý tập tin Mô hình tổ chức và Quản lý tập tin Mô hình tổ chức và Quản lý tập tin TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 16 [HĐH] Ch2. Quản lý tập tin Mô hình tổ chức và Quản lý tập tin Cấu trúc của một tập tin Cấu Trúc Của Một Tập Tin I Một tập tin là một dãy các bit, bytes, dòng, mẫu tin (records),. . . mang ý nghĩa được định nghĩa bởi người tạo ra. I Cấu trúc một tập tin: I đơn giản: bao gồm các dòng có chiều dài cố định hay thay đổi. I phức tạp: các tập tin có khuôn dạng là các bản ghi. I Yếu tố quyết định cấu trúc tập tin: người dùng (users) hay hệ điều hành. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 17 [HĐH] Ch2. Quản lý tập tin Mô hình tổ chức và Quản lý tập tin Các thuộc tính của một tập tin Các Thuộc Tính Của Một Tập Tin I Tên (name): thông tin dưới dạng người dùng có thể đọc được và có thể phân biệt chữ hoa, chữ thường (Linux, MacOS) I Kiểu (type): cho phép HĐH và người dùng xác định loại tập tin (văn bản, chương trình,. . . ). Thường xác định bằng phần mở rộng. I Vị trí (position): trỏ tới vị trí của tập tin trên thiết bị lưu trữ. I Kích thước (size): kích thước hiện hành của tập tin (bytes,. . . ). I Bảo vệ (protection): chỉ định ai có thể truy cập tập tin (đọc, ghi,...) I Thời gian (time): thời điểm tạo, sửa đổi, sử dụng lần sau cùng. I Người sở hữu (owner): định danh của người sở hữu tập tin TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 18 [HĐH] Ch2. Quản lý tập tin Mô hình tổ chức và Quản lý tập tin Các thuộc tính của một tập tin Các Thuộc Tính Của Một Tập Tin I Các thuộc tính của tập tin được lưu trong một cấu trúc được gọi là bản ghi tập tin (file record). I Thông thường, bản ghi tập tin chỉ lưu trữ tên và định danh tập tin. I Định danh tập tin sẽ xác định nơi lưu trữ các thuộc tính còn lại. I Các bản ghi tập tin được lưu trữ trong một cấu trúc thư mục (directory structure). I Cấu trúc thư mục cũng được lưu trữ trên thiết bị lưu trữ. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 19 [HĐH] Ch2. Quản lý tập tin Mô hình tổ chức và Quản lý tập tin Cấu trúc thư mục Tổ Chức Của Một Hệ Thống Tập Tin I Đĩa có thể được phân chia ra thành nhiều phân vùng (partition) I Hoặc ngược lại, nhiều đĩa có thể được kết hợp thành 1 phân vùng I Các tập tin có liên quan với nhau được tổ chức trong 1 thư mục TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 20 [HĐH] Ch2. Quản lý tập tin Mô hình tổ chức và Quản lý tập tin Cấu trúc thư mục Thư Mục I Thư mục là cấu trúc chứa các tập tin có liên quan với nhau. I Mỗi tập tin thuộc thư mục sẽ có 1 nút (node, chính là bản ghi tập tin) tương ứng trong cấu trúc thư mục để lưu trữ thông tin về tập tin. I Cấu trúc thư mục cũng được lưu trên thiết bị lưu trữ. I Mục tiêu: I tổ chức, quản lý tập tin hiệu quả I định vị tập tin nhanh chóng TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 21 [HĐH] Ch2. Quản lý tập tin Mô hình tổ chức và Quản lý tập tin Cấu trúc thư mục Các Thao Tác Trên Thư Mục I Search for a file: tìm kiếm một tập tin trong thư mục. I Create a file: tạo một tập tin trên thư mục I Delete a file: xóa một tập tin trên thư mục I List a directory: liệt kê nội dung thư mục (danh sách các tập tin) I Rename a file: thay đổi tên tập tin I Travel the file system: duyệt qua danh sách các tập tin trong thư mục TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 22 [HĐH] Ch2. Quản lý tập tin Mô hình tổ chức và Quản lý tập tin Cấu trúc thư mục Cấu Trúc Thư Mục 1 Cấp I Là cấu trúc đơn giản nhất: tất cả các file nằm trong cùng 1 thư mục. I Nhược điểm: I trong môi trường nhiều người dùng thì khả năng trùng tên cao. I ngay cả trong môi trường đơn người dùng, nếu số lượng tập tin lớn thì khả năng trùng tên cũng cao và khó quản lý (không thể gom nhóm). 11.3 Directory and Disk Structure 519 cat files directory bo a test data mail cont hex records Figure 11.9 Single-level directory. their data file test.txt, then the unique-name rule is violated. For example, in one programming class, 23 students called the program for their second assignment prog2.c; another 11 called it assign2.c. Fortunately, most file systems support file names of up to 255 characters, so it is relatively easy to select unique file names. Even a single user on a single-level directory may find it difficult to remember the names of all the files as the number of files increases. It is not uncommon for a user to have hundreds of files on one computer system and an equal number of additional files on another system. Keeping track of so many files is a daunting task. 11.3.4 Two-Level Directory As we have seen, a single-level directory often leads to confusion of file names among different users. The standard solution is to create a separate directory for each user. In the two-level directory structure, each user has his own user file directory (UFD). The UFDs have similar structures, but each lists only the files of a single user. W en a user job starts or a user logs in, the system’s master file directory (MFD) is searched. The MFD is indexed by user name or account number, and each entry points to the UFD for that user (Figure 11.10). When a user refers to a particular file, only his own UFD is searched. Thus, different users may have files with the same name, as long as all the file names within each UFD are unique. To create a file for a user, the operating system searches only that user’s UFD to ascertain whether another file of that name exists. To delete a file, the operating system confines its search to the local UFD; thus, it cannot accidentally delete another user’s file that has the same name. cat bo a test x data aa user 1 user 2 user 3 user 4 data a testuser filedirectory master file directory Figure 11.10 Two-level directory structure. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 23 [HĐH] Ch2. Quản lý tập tin Mô hình tổ chức và Quản lý tập tin Cấu trúc thư mục Cấu Trúc Thư Mục 2 Cấp I Mỗi người dùng sẽ có 1 thư mục riêng. I Thư mục của mỗi người dùng là thư mục 1 cấp. I Cho phép nhiều người dùng có thể dùng chung 1 tên tập tin. I Tuy nhiên, vẫn tồn tại vấn đề về gom nhóm và trùng tên tập tin khi số lượng tập tin của mỗi người dùng lớn. cat files directory bo a test data mail cont hex records TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 24 [HĐH] Ch2. Quản lý tập tin Mô hình tổ chức và Quản lý tập tin Cấu trúc thư mục Cấu Trúc Thư Mục Cây I Là sự tổng quát hóa của cấu trúc TM 2 cấp với số cấp không giới hạn. I Được sử dụng trong hầu hết các HĐH hiện nay. find count hex reorderstat mail dist root spell bin programs p e mail reorder list findprog copy prt exp hex count TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 25 [HĐH] Ch2. Quản lý tập tin Mô hình tổ chức và Quản lý tập tin Cấu trúc thư mục Cấu Trúc Thư Mục Cây I Mỗi thư mục, ngoài các tập tin, có thể chứa các thư mục khác, được gọi là các thư mục con. I Thư mục chứa các thư mục khác được gọi là thư mục cha. I Quan giữa các thư mục cha-con tạo thành 1 cây thư mục. I Khi thao tác trên hệ thống tập tin, luôn tồn tại 1 thư mục hiện hành. I Có 2 cách định vị 1 tập tin hay thư mục: I đường dẫn tương đối: tính từ vị trí của thư mục hiện hành. I đường dẫn tuyệt đối: tính từ gốc của cây thư mục (thư mục gốc) ⇒ không phụ thuộc vào vị trí thư mục hiện hành. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 26 [HĐH] Ch2. Quản lý tập tin Mô hình tổ chức và Quản lý tập tin Cấu trúc thư mục Cấu Trúc Thư Mục Cây – Windows I Một hệ thống lưu trữ bao gồm 1 hoặc nhiều phân vùng (partition). I Mỗi phân vùng được gán 1 tên gọi là tên ổ đĩa (drive), là 1 chữ cái. I Ký hiệu "\" được sử dụng để biểu diễn cho thư mục gốc của mỗi ổ đĩa. C:\ [Windows] [Program Files] [System32] [Security] sol.exe notepad.exe wordpad.exe D:\ [Borland] [Sun] [TurboC] tc.exe tcc.exe [Java] javac.exe java.exe appletviewer.exe TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 27 [HĐH] Ch2. Quản lý tập tin Mô hình tổ chức và Quản lý tập tin Cấu trúc thư mục Cấu Trúc Thư Mục Cây – Unix I Hệ thống cây thư mục chỉ có 1 gốc, ký hiệu là "/". I Tất cả các phân vùng đều được tổ chức trong cây thư mục này. I Thao tác ánh xạ một phân vùng vào một mục trên cây thư mục này được gọi là mount. / (root) [etc] [bin] [bin] [conf] perl php httpd [usr] httpd.conf cc ls awk [home] [jack] [bill] test.txt bird.jpg a.out script.sh TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 28 [HĐH] Ch2. Quản lý tập tin Cài đặt hệ thống tập tin Cài đặt hệ thống tập tin TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 29 [HĐH] Ch2. Quản lý tập tin Cài đặt hệ thống tập tin Khối Điều Khiển Tập Tin – FCB I Hiện có nhiều hệ thống tập tin được sử dụng bởi các HĐH (FAT, NTFS, UFS,...) I Các tập tin được quản lý bằng các khối điều khiển tập tin (file control block, FCB), chứa các thông tin về tập tin. file permissions file dates (create, access, write) file owner, group, ACL file size file data blocks or pointers to file data blocks TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 30 [HĐH] Ch2. Quản lý tập tin Cài đặt hệ thống tập tin Vai Trò Của Khối Điều Khiển Tập Tin directory structure directory structure open (file name) kernel memoryuser space index file-control block secondary storage data blocks per-process open-file table system-wide open-file table read (index) kernel memoryuser space file-control block secondary storage TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 31 [HĐH] Ch2. Quản lý tập tin Cài đặt hệ thống tập tin Cài đặt hệ thống thư mục Cài Đặt Hệ Thống Thư Mục I Có 2 phương pháp tổ chức và truy xuất các FCB trong một thư mục: 1. Danh sách tuyến tính các con trỏ tới các khối dữ liệu: I Cấu trúc cài đặt và xử lý đơn giản. I Chi phí thực hiện các thao tác trên thư mục cao. 2. Bảng băm (hash) hay bảng băm với danh sách tuyến tính: I Giảm chi phí duyệt thư mục. I Đòi hỏi có hàm băm hiệu quả (cân bằng). I Phải tổ chức lại hàm cấu trúc thư mục khi hàm băm thay đổi. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 32 [HĐH] Ch2. Quản lý tập tin Cài đặt hệ thống tập tin Cài đặt hệ thống thư mục Cài Đặt Hệ Thống Thư Mục hello.c hello.exe gtrinhC.pdf . . . btap1.cpp . . . hello.c hello.exe hurt.jpg bảng băm danh sách (liên kết) tuyến tính TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 33 [HĐH] Ch2. Quản lý tập tin Cài đặt hệ thống tập tin Các Phương Pháp Cấp Phát Đĩa Các Phương Pháp Cấp Phát Đĩa I Là cách thức lưu nội dung vào các khối đĩa như thế nào. I Có 3 phương pháp chính: 1. Cấp phát kề nhau. 2. Cấp phát kiểu liên kết. 3. Cấp phát kiểu chỉ mục. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 34 [HĐH] Ch2. Quản lý tập tin Cài đặt hệ thống tập tin Các Phương Pháp Cấp Phát Đĩa Pháp Cấp Kề Nhau I Dữ liệu tập tin được lưu trong các khối đĩa liên tục, kề nhau I Đây là phương pháp tổ chức đơn giản. I Cho phép truy cập tuần tự lẫn ngẫu nhiên. I Nhược điểm: I Dễ gây phân mảnh ngoài. I Khó tăng kích thước tập tin. directory 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 count f tr mail list start 0 14 19 28 6 length 2 3 6 4 2 file count tr mail list f TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 35 [HĐH] Ch2. Quản lý tập tin Cài đặt hệ thống tập tin Các Phương Pháp Cấp Phát Đĩa Pháp Cấp Kiểu Liên Kết I Dữ liệu tập tin được lưu trong các khối đĩa không liên tục. I Cuối mỗi khối là một con trỏ, trỏ đến khối tiếp theo (trừ khối cuối). I Đây cũng là phương pháp tổ chức đơn giản và tránh phân mảnh ngoài. I Nhược điểm: I Không thể truy cập ngẫu nhiên. I Mất không gian cho các con trỏ. I Áp dụng: hệ thống tập tin FAT. 0 1 2 3 4 5 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 15 6 file jeep start 9 directory end 25 1 1 -1 2 TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 36 [HĐH] Ch2. Quản lý tập tin Cài đặt hệ thống tập tin Các Phương Pháp Cấp Phát Đĩa Pháp Cấp Kiểu Chỉ Mục I Dữ liệu tập tin được lưu trong các khối đĩa không liên tục. I Tất cả các khối của tập tin được lưu trữ trong 1 khối, gọi là khối chỉ mục. I Phần tử thứ i trong khối chỉ mục trỏ tới khối dữ liệu thứ i của tập tin. I Cho phép truy xuất ngẫu nhiên. I Tránh phân mảnh ngoài nhưng tốn thêm khối chỉ mục. I Áp dụng: UFS với một số cải tiến. directory 0 1 2 3 4 5 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 15 6 9 16 1 10 25 –1 –1 –1 file jeep index block 19 19 TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 37 [HĐH] Ch2. Quản lý tập tin Cài đặt hệ thống tập tin Quản lý không gian trống Quản Lý Không Gian Trống I Là cách thức quản lý các khối đĩa còn trống. I Mục tiêu: dễ dàng tìm khối trống để cấp phát cho tập tin lẫn việc cập nhật danh sách các khối trống khi tập tin bị xóa. I Có 4 phương pháp chính: 1. Bản đồ bit (bit vector). 2. Danh sách liên kết (linked list). 3. Nhóm (grouping). 4. Bộ đếm (counter). TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 38 [HĐH] Ch2. Quản lý tập tin Cài đặt hệ thống tập tin Quản lý không gian trống Bản Đồ Bit I Dùng một vector các bit (gọi là bản đồ bit) để đánh dấu một khối còn trống hay không. 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 ... I Mỗi khối đĩa được đại diện bằng 1 bit trong vector (0: còn trống, 1: đã cấp phát). I Bản đồ bit yêu cầu thêm không gian lưu trữ: I block size = 1MB (212 bytes) I disk size = 1GB (230 bytes) ⇒ Kích thước bản đồ bit = 230/212 = 218 bytes (32KB) TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 39 [HĐH] Ch2. Quản lý tập tin Cài đặt hệ thống tập tin Quản lý không gian trống Danh Sách Liên Kết I Các khối trống được liên kết với nhau bằng một danh sách liên kết. I Lưu trữ một con trỏ trỏ đến khối trống đầu tiên trong danh sách (free-space list head). I Nhược điểm: khó cấp phát liên tục. 0 1 2 3 4 5 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 15 6 free- space list head TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 40 [HĐH] Ch2. Quản lý tập tin Cài đặt hệ thống tập tin Quản lý không gian trống Nhóm & Đếm I Nhóm (grouping): I Là một biến thể của danh sách liên kết. I Lưu trữ một danh sách liên kết các khối chỉ mục. I Mỗi khối chỉ mục lưu địa chỉ một số khối trống và có con trỏ đến khối chỉ mục chứa danh sách các khối trống tiếp theo. I Đếm (counting): I Dùng quản lý các khối trống kề nhau. I Gồm một số các mục từ (entry), mỗi mục từ lưu vị trí khối trống đầu tiên và số lượng n khối trống tiếp theo. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 41 [HĐH] Ch2. Quản lý tập tin Tổng Kết Tổng Kết Các khái niệm cơ bản Các Phương Pháp Truy Cập Tập Tin Mô hình tổ chức và Quản lý tập tin Cài đặt hệ thống tập tin TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 42