Bài giảng Hệ điều hành - Chương 3: Hệ thống quản lý tập tin - Phạm Tuấn Sơn

Nội dung text: Bài giảng Hệ điều hành - Chương 3: Hệ thống quản lý tập tin - Phạm Tuấn Sơn

1. Chương 3 Hệ thống quản lý tập tin Phạm Tuấn Sơn Email: ptson@fit.hcmuns.edu.vn 1
2. Mục tiêu n Trình bày cấu tạo đĩa từ n Trình bày các khái niệm về hệ thống tập tin n Trình bày một số vấn đề khi cài đặt hệ thống quản lý tập tin trên đĩa và trong bộ nhớ n Trình bày mô hình tổ chức hệ thống tập tin của một số hệ điều hành thông dụng 2
3. Phân cấp hệ thống lưu trữ Tốc độ Volatile truy xuất Non-volatile Dung lượng 3
4. Đĩa từ n Đĩa từ -là những đĩa phẳng bằng thủy tinh hay bằng kim loại cứng được phủ từ để ghi dữ liệu 4
5. Cấu trúc vật lý n Gồm nhiều lớp hình tròn, mỗi lớp phủ từ 1 hoặc cả 2 mặt (side) n Mỗi mặt có tương ứng 1 đầu đọc (head) để đọc hoặc ghi dữ liệu n Mỗi mặt có nhiều đường tròn đồng tâm (track) n Mỗi đường tròn được chia nhỏ thành các cung tròn (sector), thông thường mỗi cung chứa 4096 điểm từ (~ 4096 bit = 512 byte) n Mỗi lần đọc/ ghi ít nhất 1 sector (512 byte) 5
6. Truy xuất mức vật lý n Để truy xuất 1 sector cần phải chỉ ra vị trí của sector đó. Vị trí sector được thể hiện bằng 3 thông số: chỉ số sector, track và head q Head được đánh số từ trên xuống bắt đầu từ 0 q Track được đánh số theo thứ tự từ ngoài vào bắt đầu từ 0 q Sector được đánh số bắt đầu từ 1 theo chiều ngược với chiều quay của đĩa n Địa chỉ sector vật lý có ký hiệu: (sector, track, head) n Hàm truy xuất mức vật lý trong C for DOS: int biosdisk (int cmd, int drive, int head, int track, int sector, int nsects, void *buffer) n Hàm truy xuất mức vật lý trong C for Windows ??? 6
7. Cơ chế đọc đĩa n Access time = Seek time + Rotational time + Read time 7
8. Tổ chức logic n Do truy xuất mức vật lý phải dùng đến 3 tham số rất bất tiện nên tổ chức logic được đưa ra để dễ hiểu, dễ thao tác, dễ tính toán hơn n Cylinder: là tập các track có cùng bán kính (cùng số hiệu) trên tất cả các mặt à Nhận xét: truy xuất sector theo từng cylinder sẽ đảm bảo sau khi truy xuất sector K thì truy xuất sector K+1 là nhanh hơn so với tất cả các sector khác n Tổ chức logic là một dãy sector được đánh chỉ số theo theo từng cylinder, bắt đầu từ 0 0 1 2 3 4 N-1 n Mỗi lần truy xuất (đọc/ ghi đĩa) chỉ có thể thực hiện trên N sector liên tiếp (N>=1) n Hàm truy xuất mức logic trong C for DOS: int absread (int drive, int nsects, long lsect, void *buffer). int abswrite (int drive, int nsects, long lsect, void *buffer); n Hàm truy xuất mức logic trong C for Windows ??? 8
9. Sector vật lý « Sector logic n Sector vật lý ® Sector logic l = t*st*side + h*st + s -1 n Sector logic ® Sector vật lý s = (l mod st) + 1 t = l div (st * side) h = (l div st) mod side Trong đó: l : chỉ số sector logic st : số sector /track h: chỉ số head th : số track /side (head) t : chỉ số track side : tổng số side (head) s: chỉ số sector vật lý 9
10. Đĩa mềm 1.44 MB n Có 2 head /disk, 80 track /head, 18 sector /track n Dung lượng đĩa: 2 head/disk * 80 track/head * 18 sector/track = 2880 sector/disk = 0.5 KB/sector * 2880 sector/disk = 1440 KB/disk (~ 1.44 MB) n Sector logic có chỉ số từ 0 đến 2879 và tương ứng với sector vật lý như sau: Sector Logic Sector vật lý (Sector, Track, Head) 0 (1, 0, 0) 1 (2, 0, 0) 17 (18, 0, 0) 18 (1, 0, 1) 19 (2, 0,1) 35 (18, 0, 1) 36 (1, 1, 0) 37 (2, 1,0 ) 10
11. Bài tập 1. Một đĩacứngcó16head,684track,vàmỗitrack có18sectorthìsẽcókíchthướclàbaonhiêu Megabyte?Hãychobiếtsectorvậtlýtương ứng vớisectorlogic2008 2. Chobiếtsectorvậtlý(head0,track19,sector6) tương ứngvớisectorlogicnàotrên đĩamềm 1.44MB a. 347 b. 348 c. 689 d. 690 11
12. Một số khái niệm n Tập tin n Thư mục 12
13. Bộ nhớ ngoài & Tập tin n Một số hạn chế của bộ nhớ trong q Không lưu trữ dữ liệu lâu dài q Không chứa lượng thông tin lớn. à Cần các thiết bị lưu trữ ngoài(bộ nhớ ngoài) để lưu trữ dữ liệu n Tuy nhiên, có nhiều loại thiết bị lưu trữ ngoài (đĩa từ, CD/DVD, USB, thẻ nhớ, ); đa dạng về cấu trúc, khả năng lưu trữ, phương thức truy xuất, tốc độ truy xuất n HĐH cung cấp cái nhìn logic và đồng nhất về việc lưu trữ thông tin q Trừu tượng hóa thông tin vật lý thành đơn vị lưu trữ logic – tập tin 13
14. Tập tin n Tập tin là gì ? q Lưu trữ tập hợp các thông tin có liên quan với nhau q Là một đơn vị lưu trữ luận lý che tổ chức vật lý của các thiết bị lưu trữ ngoài 14
15. Thuộc tính tập tin n Thuộc tính của tập tin trên các hệ thống tập tin khác nhau sẽ khác nhau, nhưng thường gồm các thuộc tính sau: q Tên (tên + phần mở rộng) q Người sở hữu q Thuộc tính trạng thái: chỉ đọc, ẩn, hệ thống, q Kích thước q Ngày giờ (tạo, truy cập, thay đổi) q Thuộc tính bảo vệ q Vị trí lưu trữ trên đĩa 15
16. Cơ chế bảo vệ tập tin n Người tạo /sở hữu tập tin có quyền kiểm soát: q Ai (người dùng /nhóm người dùng) có quyền thao tác trên tập tin q Thao tác như thế nào n Đọc n Ghi n Thực thi n Thêm n Xóa n Liệt kê n Một số quyền đặc biệt khác 16
17. Thao tác trên tập tin n Một số thao tác cơ bản trên tập tin (tương ứng với các lời gọi hệ thống) q Tạo q Xóa q Mở q Đóng q Đọc q Ghi q Định vị q Nối thêm dữ liệu q Lấy thuộc tính q Đặt thuộc tính n Một số thao tác khác: sao chép, di chuyển, đổi tên, 17
18. Một số tính chất khác của tập tin n Cấu trúc tập tin –do HĐH hay chương trình ứng dụng quyết định q Không cấu trúc q Có cấu trúc n Loại tập tin q Tập tin văn bản (text file): chứa các dòng văn bản, cuối dùng có ký hiệu kết thúc dòng (end line) q Tập tin nhị phân (binary file): là tập tin có cấu trúc. n Truy xuất tập tin q Tuần tự -Phải đọc từ đầu tập tin đến vị trí mong muốn, có thể quay lui (rewind) q Ngẫu nhiên -Có thể di chuyển (seek) đến đúng vị trí cần đọc 18
19. Thư mục n Thư mục là một loại tập tin đặc biệt, giúp tổ chức có hệ thống các tập tin hệ hệ thống lưu trữ ngoài n Thuộc tính của thư mục tương tự của tập tin n Nội dung của thư mục là danh sách các tập tin, thư mục con của nó n Một số thao tác trên thư mục q Tạo q Xóa q Mở q Đóng q Liệt kê nội dung thư mục q Tìm kiếm tập tin q Duyệt hệ thống tập tin 19
20. Một số vấn đề tổ chức hệ thống tập tin n Tổ chức tập tin n Tổ chức thư mục n Quản lý đĩa trống n Tổ chức hệ thống tập tin trên đĩa từ n Tổ chức hệ thống tập tin trong bộ nhớ n Kết buộc hệ thống tập tin 20
21. Vấn đề Thiết bị lưu trữ ??? Block 21
22. Tổ chức tập tin n Mỗi tập tin lưu nội dung trên một số block (khối lưu trữ) của thiết bị lưu trữ à Làm sao biết được tập tin đang chiếm những block nào ? n Phương pháp cấp phát mô tả cách thức cấp phát các block cho các tập tin n Có 3 phương pháp cấp phát chính: q Cấp phát liên tục q Cấp phát theo kiểu danh sách liên kết q Cấp phát theo kiểu chỉ mục 22
23. Cấp phát liên tục 23
24. Cấp phát liên tục (tt) n Mỗi tập tin chiếm các block liên tục trên đĩa n Đơn giản, chỉ cần quản lý vị trí (chỉ số) block bắt đầu và chiều dài (số block) n Hỗ trợ truy xuất tuần tự & truy xuất trực tiếp n Vấn đề External fragmentation n Vấn đề khi kích thước tập tin tăng 24
25. Cấp phát liên tục (tt) n Hệ thống tập tin cấp phát theo extent: q Extent là một tập các block liên tục q Cấp phát cho tập tin theo từng extent q Một tập tin có thể chiếm một hoặc nhiều extent không liên tục nhau q Kích thước các extent có thể khác nhau q Cần quản lý 3 thông tin: vị trí block bắt đầu, số block và một con trỏ trỏ tới block đầu tiên của extent kế tiếp q Vấn đề Internal fragmentation và External fragmentation 25
26. Cấp phát theo kiểu danh sách liên kết 26
27. Cấp phát theo kiểu danh sách liên kết (tt) n Mỗi tập tin chiếm một tập các block theo kiểu danh sách liên kết. n Mỗi block sẽ chứa thông tin về địa chỉ của block kế tiếp n Các block có thể nằm rãi rác trên đĩa n Chỉ hỗ trợ truy xuất tuần tự n Đơn giản, chỉ cần quản lý vị trí (chỉ số) block bắt đầu n Không bị External fragmentation n Tốn chi phí lưu địa chỉ block kế tiếp 27
28. Cấp phát theo kiểu chỉ mục 28
29. Cấp phát theo kiểu chỉ mục (tt) n Gồm một hoặc nhiều block làm bảng chỉ mục chứa địa chỉ của các block dữ liệu n Hỗ trợ truy xuất tuần tự & truy xuất trực tiếp n Tốn không gian đĩa để lưu các block chỉ mục n Không bị External fragmentation n Một số mô hình mở rộng q Mô hình chỉ mục nhiều cấp q Mô hình chỉ mục kết hợp danh sách liên kết q Mô hình chỉ mục nhiều cấp kết hợp danh sách liên kết 29
30. Mô hình chỉ mục nhiều cấp 30
31. Mô hình chỉ mục kết hợp danh sách liên kết 31
32. Mô hình chỉ mục nhiều cấp kết hợp danh sách liên kết index index index index 32
33. Tổ chức thư mục n Thường được tổ chức thành một bảng các phần tử (directory entry), gọi là bảng thư mục n 2 cách tổ chức directory entry: q Entry chứa tên và các thuộc tính q Entry chứa tên và một con trỏ trỏ tới 1 cấu trúc chứa các thuộc tính 33
34. Vấn đề tên dài (long file name -LFN) 34
35. Một số mô hình tổ chức thư mục n Các mô hình tổ chức q Cấu trúc 1 cấp q Cấu trúc 2 cấp q Cấu trúc cây q Cấu trúc đồ thị n Một số vấn đề cần xem xét q Hiệu quả n Định vị tập tin một cách nhanh chóng q Vấn đề đặt tên n Hai người dùng có thể đặt cùng tên cho các tập tin khác nhau n Thuận tiện cho người sử dụng q Vấn đề gom nhóm n Gom nhóm các tập tin theo một mục đích nào đó n Ví dụ: tất cả chương trình Java, tất cả trò chơi, q Độ phức tạp khi cài đặt bảng thư mục 35
36. Cấu trúc 1 cấp n Một cấp thư mục duy nhất cho tất cả các người dùng (+) Đơn giản, dễ cài đặt (–) Hiệu quả tìm kiếm giảm đối với lượng tập tin lớn (–) Vấn đề đặt tên (–) Vấn đề gom nhóm 36
37. Cấu trúc 2 cấp n Mỗi người dùng 1 thư mục riêng n Nếu có quyền truy cập vào tập tin của người dùng khác phải sử dụng tên đường dẫn đầy đủ (+) Các người dùng khác nhau có thể có tập tin có tên trùng nhau (+) Tìm kiếm hiệu quả (–) Không có khả năng gom nhóm 37
38. Cấu trúc cây n Tên đường dẫn tương đối & đường dẫn tuyệt đối n Vấn đề xóa 1 thư mục n Được sử dụng phổ biến trên các hệ điều hành hiện nay (+) Tìm kiếm hiệu quả (+) Có khả năng gom nhóm 38
39. Cấu trúc đồ thị n Có cho phép có thư mục con và tập tin chia sẻ hay không à Loại tập tin mới q Liên kết (link) -một tên khác (con trỏ) tới 1 tập tin đã tồn tại à Phân giải liên kết –dùng con trỏ để định vị tập tin à Tổ chức thư mục theo dạng đồ thị không lặp có hướng (Directed Acyclic Graph -DAG) n Xóa tập tin gốc à Vấn đề “con trỏ treo” (dangling pointer) Giải pháp: q Tùy người dùng xử lý n Ví dụ: symbolic link (Linux), link (Windows) q Duy trì một danh sách các tham chiếu tới tập tin à vấn đề khi danh sách này lớn q Duy trì biến đếm số tham chiếu tới tập tin n Ví dụ: hard link (Linux) 39
40. Cấu trúc đồ thị (tt) n Duyệt toàn bộ hệ thống tập tin Làm sao để đảm bảo không có liên kết vòng q Không cho phép liên kết tới thư mục, chỉ cho phép liên kết tới tập tin q Cơ chế thu gom rác (Garbage collection) q Mỗi lần thêm 1 liên kết à sử dụng thuật toán phát hiện chu trình 40
41. Cài đặt bảng thư mục n 2 cách cài đặt bảng thư mục q Danh sách tuyến tính (Linear List) (+) Dễ cài đặt (–) Chi phí tìm kiếm cao q Bảng băm (Hash Table) (+) Giảm thời gian tìm kiếm (–) Vấn đề đụng độ (–) Kích thước bảng thư mục cố định 41
42. Quản lý không gian đĩa trống n Bit vector (Bit map) q Mỗi block được biểu diễn bằng 1 bit 01 2 n-1 0 Þ block[i] trống bit[i] = 1 Þ block[i] đã dùng q Bit vector tốn không gian đĩa. Ví dụ: kích thước 1 block = 212 bytes kích thước đĩa = 230 bytes (1 gigabyte) à n = 230/212 = 218 bits (or 32K bytes) q HĐH Macintosh 42
43. Quản lý không gian đĩa trống (tt) n Danh sách liên kết q Chi phí duyệt danh sách cao q Không tốn không gian đĩa n Grouping q Chứa danh sách các block trống q Dễ tìm một lượng lớn các block trống n Counting q Chứa địa chỉ block trống đầu tiên và số lượng các block trống liên tục tiếp theo 43
44. Hệ thống tập tin FAT (12, 16, 32) Fat Allocation Table 0000 Cluster 0 1 2 3 4 5 0001 0002 3 File1 File1 File1 File2 0003 4 0004 EOF 6 7 8 9 10 11 0005 6 File2 File3 File2 empty empty empty 0006 8 0007 EOF 0008 EOF 12 13 14 15 16 17 0009 0000 empty empty empty empty empty empty 44 44
45. Hệ thống tập tin NTFS New Technology File System 45
46. Hệ thống tập tin trên Unix /Linux Cấu trúc I-node boot block super block I-node files and directories n Gián tiếp cấp 1: cấp này trỏ tới 256 địa chỉ. Tổng 256KB n Gián tiếp cấp 2: 256*256 = 65 MB n Gián tiếp cấp 3: 256*256*256 = 16GB 46
47. Hệ thống tập tin trên UNIX V7 47
48. Tổ chức hệ thống tập tin trên đĩa từ n Master Boot Record (MBR): thường nằm tại sector logic 0, kích thước 512 bytes n Phân vùng (Partition): q Primary q Extended Tối đa 4 phân vùng n Boot block + Super block (Boot sector) q Chứa các thông số quan trọng của phân vùng q Chứa một đoạn chương trình nhỏ để nạp HĐH khi khởi động máy 48
49. n Đoạn chương trình để giúp khởi Master Boot Record động hệ thống n Bảng mô tả thông tin các phân vùng logic q TYPE-ID = 0x07 : Windows q TYPE-ID = 0x83 : Linux q TYPE-ID = 0x00 : Không sử dụng. n Thông tin nhận diện MBR 49
50. Quá trình khởi động hệ thống từ đĩa từ 1. POST (Power-On Self-Test) 2. Tải MBR để đọc thông tin bảng phân vùng. Tìm phân vùng “active”. Nếu không tìm thấy phân vùng “active”, MBR có thể tải một boot loader và chuyển điều khiển cho nó. Boot loader này sẽ cho phép chọn HĐH trên một phân vùng 3. Chuyển quyền điều khiển về cho đoạn mã chương trình nằm trong Boot Sector của phân vùng được chọn 4. Tải HĐH tại phân vùng được chọn CT trong CT trong các CT còn lại Baät CMOS FDD maùy ROM BIOS Boot Sector của HĐH HDD CT trong Master Boot 50
51. Tổ chức hệ thống tập tin trong bộ nhớ chính n Vấn đề: q Thao tác với nhiều tập tin tại một thời điểm ? q Thao tác trên cùng một tập tin tại một thời điểm ? n Các thông tin cần lưu trữ trong bộ nhớ: q Mounted Volume Table –Danh sách các volume được sử dụng trên hệ thống q Directory Structure –Thông tin các thư mục mới được sử dụng n Con trỏ trỏ tới volume tương ứng q System-wide open-file Table –Danh sách các tập tin đang được mở trên hệ thống n Con trỏ tập tin, định vị tập tin trên đĩa n Quyền truy cập n Biến đếm tập tin đang mở q Per-process open-file Table –Danh sách các tập tin mà tiến trình đang thao tác n Con trỏ trỏ tới tập tin đang mở tương ứng trong system-wide open-file table 51
52. Tổ chức hệ thống tập tin trong bộ nhớ chính 52
53. Kết buộc (Mount) hệ thống tập tin n Một hệ thống tập tin phải được kết buộc (mount) trước khi có thể truy xuất (giống như tập tin phải được mở trước khi sử dụng) n Các HĐH thường phát hiện và tự động kết buộc các hệ thống tập tin tồn tại trên hệ thống q Windows kết buộc hệ thống tập tin vào ổ đĩa q Linux kết buộc hệ thống tập tin vào một thư mục n Một số HĐH cung cấp lệnh để thực hiện việc kết buộc hệ thống tập tin q Ví dụ: lệnh mount (Linux) 53
54. Ví dụ kết buộc hệ thống tập tin mount /dev/sda1 /users 54