Giáo trình Hệ điều hành - Chương 2: Quản lí tập tin

Nội dung text: Giáo trình Hệ điều hành - Chương 2: Quản lí tập tin

1. 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
2. [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
3. [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
4. [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
5. [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
6. [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
7. [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 fle type usual extension function executable exe, com, bin ready-to-run machine- or none language program object obj, o compiled, machine language, not linked source code c, cc, java, perl, source code in various asm languages batch bat, sh commands to the command interpreter markup xml, html, tex textual data, documents word processor xml, rtf, various word-processor docx formats library lib, a, so, dll libraries of routines for programmers print or view gif, pdf, jpg ASCII or binary fle in a format for printing or viewing archive rar, zip, tar related fles grouped into one fle, sometimes com- pressed, for archiving or storage multimedia mpeg, mov, mp3, binary fle containing mp4, avi audio or A/V information TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 7
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 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
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 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
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 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
11. [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
12. [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
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 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) current position beginning end rewind read or write TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 13
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 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 implementation for direct access reset cp 0; read_next read cp ; cp cp 1; write_next write cp; cp cp 1; TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 14
15. [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í logical record last name number Adams Arthur Asher smith, john social-security age • • • Smith index file relative file TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 15
16. [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
17. [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
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 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
19. [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
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 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
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 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
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á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
23. 11.3 Directory and Disk Structure 519 directory cat bo a test data mail cont hex records files Figure 11.9 Single-level directory. their data file test.txt,thentheunique-nameruleisviolated.Forexample, in one programming class, 23 students called the program for their second assignment prog2.c; another 11 called it assign2.c.Fortunately,mostfile 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 [HĐH] Ch2. Quảnfiles lý tập is a tin daunting task. Mô hình tổ chức và Quản lý tập tin Cấu trúc thư mục 11.3.4 Two-Level Directory As we have seen, a single-level directory often leads to confusion of file names Cấu Trúcamong different Thư users. Mục The standard 1 Cấp 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).TheUFDshavesimilarstructures,buteachlistsonlythe I Là cấufiles trúc of a đơn single giản user. Whennhất: a usertấtjob cả starts các or file a usernằm logs trong in, the cùng system’s 1 thư mục. master file directory (MFD) is searched. The MFD is indexed by user name or I Nhượcaccount điểm: 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 I trongwithin môi each trườngUFD are unique.nhiềuTo người create dùng a file forthì a khả user, năngthe operating trùng system tên cao. searches only that user’s UFD to ascertain whether another file of that name I ngayexists. cả To trong delete a môi file, the trường operating đơn system người confines dùng its, search nếu sốto the lượng local UFD tập; tin lớn thì khảthus, năng it cannot trùng accidentally tên cũng delete cao another và khó user’s quản file that lý has (không the same thể name. gom nhóm). master file user 1 user 2 user 3 user 4 directory user file cat bo a test a data a test x data a directory Figure 11.10 Two-level directory structure. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 23
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 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. directory cat bo a test data mail cont hex records files TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 24
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 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. root spell bin programs stat mail dist find count hex reorder p e mail prog copy prt exp reorder list find hex count TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 25
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 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
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 – 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:\ D:\ [Windows] [Program Files] [Borland] [Sun] [System32] [Security] [TurboC] [Java] sol.exe notepad.exe tc.exe tcc.exe javac.exe java.exe wordpad.exe appletviewer.exe TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 27
28. [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] [usr] [bin] [conf] cc ls awk [home] perl php httpd.conf [jack] [bill] httpd test.txt bird.jpg a.out script.sh TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 28
29. [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
30. [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
31. [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 open (file name) directory structure file-control block user space kernel memory secondary storage index data blocks read (index) per-process system-wide file-control block open-file table open-file table user space kernel memory secondary storage TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 31
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 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
33. [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 danh sách (liên kết) tuyến tính hello.c hello.exe gtrinhC.pdf . . . btap1.cpp bảng băm hello.c hello.exe hurt.jpg . . . TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 33
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 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
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 Kề Nhau directory I Dữ liệu tập tin được lưu trong các file start length count khối đĩa liên tục, kề nhau 0 1 2 3 count 0 2 f tr 14 3 I Đây là phương pháp tổ chức đơn 4 5 6 7 mail 19 6 list 28 4 giản. 8 9 10 11 tr f 6 2 12 13 14 15 I Cho phép truy cập tuần tự lẫn ngẫu nhiên. 16 17 18 19 mail 20 21 22 23 I Nhược điểm: 24 25 26 27 I Dễ gây phân mảnh ngoài. list 28 29 30 31 I Khó tăng kích thước tập tin. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 35
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 Liên Kết directory I Dữ liệu tập tin được lưu trong các file start end khối đĩa không liên tục. jeep 9 25 011 2 3 I Cuối mỗi khối là một con trỏ, trỏ 456 7 đến khối tiếp theo (trừ khối cuối). 8 91 102 11 I Đây cũng là phương pháp tổ chức 12 13 14 15 đơn giản và tránh phân mảnh ngoài. 16 17 18 19 I Nhược điểm: 20 21 22 23 I Không thể truy cập ngẫu nhiên. 24 25 -126 27 I Mất không gian cho các con trỏ. 28 29 30 31 I Áp dụng: hệ thống tập tin FAT. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 36
37. [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. directory file index block jeep I Tất cả các khối của tập tin được lưu 012 3 19 trữ trong 1 khối, gọi là khối chỉ mục. 4 5 6 7 891011 I Phần tử thứ i trong khối chỉ mục 9 12 13 14 15 16 1 trỏ tới khối dữ liệu thứ i của tập tin. 10 19 16 17 18 19 25 –1 I Cho phép truy xuất ngẫu nhiên. 20 21 22 23 –1 –1 24 25 26 27 I Tránh phân mảnh ngoài nhưng tốn thêm khối chỉ mục. 28 29 30 31 I Áp dụng: UFS với một số cải tiến. TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 37
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 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
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 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ữ: 12 I block size = 1MB (2 bytes) 30 I disk size = 1GB (2 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
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 Danh Sách Liên Kết free- space 012 3 list I Các khối trống được liên kết với head 456 7 nhau bằng một danh sách liên kết. 8 9 10 11 Lưu trữ một con trỏ trỏ đến khối I 12 13 14 15 trống đầu tiên trong danh sách (free-space list head). 16 17 18 19 20 21 22 23 I Nhược điểm: khó cấp phát liên tục. 24 25 26 27 28 29 30 31 TS. Trần Công Án [HĐH] Ch2. Quản lý tập tin 40
41. [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
42. [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