Bài giảng Hệ thống quản lý tập tin

Môn học: Hệ điều hành
 1
• Trình bày cấu tạo đĩa từ
• Trình bày các khái niệm liên quan hệ thống tập tin
• 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
• 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
 Tốc độ 
 Volatile truy xuất
Non-volatile
 Dung 
 lượng
 3
• Đĩa từ - là những đĩa phẳng bằng thủy tinh hay 
 bằng kim loại cứng được phủ từ để lưu dữ liệu
 4
• Gồm nhiều lớp hình tròn, mỗi lớp phủ 
 từ 1 hoặc cả 2 mặt (side)
• Mỗi mặt có tương ứng 1 đầu đọc 
 (head) để đọc hoặc ghi dữ liệu
• Mỗi mặt có nhiều đường tròn đồng 
 tâm (track)
• 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)
• Mỗi lần đọc/ghi ít nhất 1 sector (512 
 byte)
 5
• Để 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
 – Head được đánh số từ trên xuống bắt đầu từ 0
 – Track được đánh số theo thứ tự từ ngoài vào bắt đầu từ 0
 – Sector được đánh số bắt đầu từ 1 theo chiều ngược với chiều 
 quay của đĩa
• Địa chỉ sector vật lý có ký hiệu: (sector, track, head)
• 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)
• Hàm truy xuất mức vật lý trong C for Windows ???
 6
• Access time = Seek time + Rotational time + Read time
 7
 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
 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
 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
 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)
 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);
 8
 Hàm truy xuất mức logic trong C for Windows ???
• Sector vật lý Sector logic
 l = t*st*hd + h*st + s -1
• Sector logic Sector vật lý
 s = (l mod st) + 1
 t = l div (st * hd)
 h = (l div st) mod hd
Trong đó:
 l : chỉ số sector logic st : số sector /track
 h : chỉ số head th : số track /side 
 (head)
 t : chỉ số track hd : tổng số side (head)
 s : chỉ số sector vật lý
 9
• Có 2 head /disk, 80 track /head, 18 sector /track
• 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)
• 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
1. Một đĩa cứng có 16 head, mỗi mặt có 684 track, và
 mỗi track có 18 sector thì sẽ có kích thước là bao
 nhiêu Megabyte ?
2. Cho biết sector vật lý (head 0, track 19, sector 6)
 tương ứng với sector logic nào trên đĩa mềm
 1.44MB
 a. 347
 b. 348
 c. 689
 d. 690
 11
• Tập tin
• Thư mục
 12
• Một số hạn chế của bộ nhớ trong
 – Không lưu trữ dữ liệu lâu dài
 – 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
• 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
• HĐH cung cấp cái nhìn logic và đồng nhất về việc 
 lưu trữ thông tin
 – Trừu tượng hóa thông tin vật lý thành đơn vị lưu trữ logic 
 – tập tin
 13
• Tập tin là gì ?
 – Lưu trữ tập hợp các thông tin có liên quan với nhau
 – 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
 – Thường bao gồm 2 thành phần:
 • Thuộc tính
 • Nội dung
 – Mỗi hệ thống tập tin có cách thức tổ chức tập tin 
 khác nhau
 14
• 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:
 – Tên (tên + phần mở rộng)
 – Người sở hữu
 – Thuộc tính trạng thái: chỉ đọc, 
 ẩn,
 – Kích thước
 – Ngày giờ (tạo, truy cập, thay đổi)
 – Thuộc tính bảo vệ
 – Vị trí lưu trữ trên đĩa
 15
• Người tạo /sở hữu tập tin có quyền 
 kiểm soát:
 – Ai (người dùng /nhóm người dùng) 
 có quyền gì trên tập tin
 • Đọc
 • Ghi
 • Thực thi
 • Thêm
 • Xóa
 • Liệt kê
 • Một số quyền đặc biệt khác
 16
• Một số thao tác cơ bản trên tập tin
 – Tạo
 – Xóa
 – Đọc
 – Ghi
 – Định vị (seek)
 – Xóa nội dung (truncate)
 – Mở
 – Đóng
• Một số thao tác khác: sao chép, di chuyển, đổi tên, 
 17
• Cấu trúc tập tin – do HĐH hay chương trình ứng 
 dụng quyết định
 – Không cấu trúc
 – Có cấu trúc
• Loại tập tin
 – 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)
 – Tập tin nhị phân (binary file): là tập tin có cấu trúc.
• Truy xuất tập tin
 – Tuần tự - Phải đọc từ đầu tập tin đến vị trí mong 
 muốn, có thể quay lui (rewind)
 – Ngẫu nhiên - Có thể di chuyển (seek) đến đúng vị trí 
 cần đọc
 18
• 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 trên hệ thống lưu trữ ngoài
 – Thuộc tính của thư mục tương tự của tập tin
 – Nội dung của thư mục: quản lý các tập tin,thư mục con của nó
 • Một cấp: đơn giản nhất, tất cả tập tin trên hệ thống cùng thư mục
 • Hai cấp: mỗi người dùng có 1 thư mục riêng
 • Cây phân cấp: được sử dụng phổ biến hiện nay
• Một số thao tác trên thư mục
 – Tạo
 – Xóa
 – Mở
 – Đóng
 – Liệt kê nội dung thư mục
 – Tìm kiếm tập tin
 – Duyệt hệ thống tập tin
 19
• Tổ chức thư mục
• Tổ chức tập tin
• Quản lý đĩa trống
• Tổ chức hệ thống tập tin trên đĩa từ
• Tổ chức hệ thống tập tin trong bộ nhớ
• Kết buộc hệ thống tập tin
 20
 Thiết bị lưu trữ
??? Block
 21
• 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
• 2 cách tổ chức directory entry:
 – Entry chứa tên và các thuộc tính
 – 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
 22
23
• 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 ?
• 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
• Có 3 phương pháp cấp phát chính:
 – Cấp phát liên tục
 – Cấp phát theo kiểu danh sách liên kết
 – Cấp phát theo kiểu chỉ mục
 24
25
• Mỗi tập tin chiếm các block liên tục trên đĩa
• Đơn giản, chỉ cần quản lý vị trí (chỉ số) block bắt 
 đầu và chiều dài (số block)
• Hỗ trợ truy xuất tuần tự & truy xuất trực tiếp
• Vấn đề External fragmentation
• Vấn đề khi kích thước tập tin tăng
 26
• Hệ thống tập tin cấp phát theo extent:
 – Extent là một tập các block liên tục
 – Cấp phát cho tập tin theo từng extent
 – Một tập tin có thể chiếm một hoặc nhiều extent không liên 
 tục nhau
 – Kích thước các extent có thể khác nhau
 – 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
 – Vấn đề Internal fragmentation và External fragmentation
 27
28
• Mỗi tập tin chiếm một tập các block theo kiểu danh 
 sách liên kết.
• Mỗi block sẽ chứa thông tin về địa chỉ của block kế 
 tiếp
• Các block có thể nằm rãi rác trên đĩa
• Chỉ hỗ trợ truy xuất tuần tự
• Đơn giản, chỉ cần quản lý vị trí (chỉ số) block bắt 
 đầu
• Không bị External fragmentation
• Tốn chi phí lưu địa chỉ block kế tiếp
 29
30
• 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
• Hỗ trợ truy xuất tuần tự & truy xuất trực tiếp
• Tốn không gian đĩa để lưu các block chỉ mục
• Không bị External fragmentation
• Một số mô hình mở rộng
 – Mô hình chỉ mục nhiều cấp
 – Mô hình chỉ mục kết hợp danh sách liên kết
 – Mô hình chỉ mục nhiều cấp kết hợp danh sách liên kết
 31
 DATA
 DATA
 INDEX
 DATA
 DATA
INDEX
 INDEX DATA
 DATA
 DATA
 INDEX
 DATA
 DATA 32
 DATA
INDEX DATA
 DATA
 INDEX DATA DATA
 INDEX DATA
 --- 33
 index
index
 index
 index
 34
• Bit vector (Bit map)
 – Mỗi block được biểu diễn bằng 1 bit
 0 1 2 n-1
 0 block[i] trống
 bit[i] =
 1 block[i] đã dùng
 – 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)
 – HĐH Macintosh
 35
• Danh sách liên kết FREE
 – Chi phí duyệt danh sách cao
 – Không tốn không gian đĩa
• Grouping
 – Chứa danh sách các block INDEX FREE
 trống
 – Dễ tìm một lượng lớn các FREE
 block trống
• Counting
 INDEX FREE
 – 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 INDEX
 36
 File allocation File allocation 
Boot sector Root directory Other directories and all files
 table 1 table 2 (duplicate)
 0000
 0001 Tên T.Tính Start
 0002 3 File 1  2
 0003 4 File 2  5
 0004 EOF File 3  7 2 3 4
 0005 6
 0006 8 File1 File1 File1
 0007 EOF
 0008 EOF 5 6 7
 0009 0000
  Cluster File2 File2 File3
  FAT12: 32MB 8 9 10
  FAT16: 4GB File2 empty empty
  FAT32: 8TB
 37
16 exabytes
(16 billion GB)
 Standard Security
 information Filename descriptor Data
 38
boot block super block I-node files and directories
 Gián tiếp cấp 1: 
 cấp này trỏ tới 256 
 địa chỉ. Tổng 256KB
 Gián tiếp cấp 2: 
 256*256 = 65 MB
 Gián tiếp cấp 3: 
 256*256*256 = 
 16GB 
 39
40
• Master Boot Record (MBR): thường nằm tại sector logic 0, kích 
 thước 512 bytes
• Phân vùng (Partition):
 – Primary
 – Extended
 Tối đa 4 phân vùng
• Boot block + Super block (Boot sector)
 – Chứa các thông số quan trọng của phân vùng
 – Chứa một đoạn chương trình nhỏ để nạp HĐH khi khởi động máy
 41
• Đoạn chương trình để giúp khởi động hệ 
 thống
• Bảng mô tả thông tin các phân vùng logic
 – TYPE-ID = 0x07 : Windows
 – TYPE-ID = 0x83 : Linux
 – TYPE-ID = 0x00 : Không sử dụng.
• Thông tin nhận diện MBR
 42
 Address Size in
 Description
Hex Oct Dec bytes
 440
0000 0000 0 Code Area
 (max. 446)
01B8 0670 440 Optional Disk signature 4
01BC 0674 444 Usually Nulls; 0x0000 2
 Table of primary partitions
01BE 0676 446 (Four 16-byte entries, IBM 64
 Partition Table scheme)
01FE 0776 510 55h MBR signature;
 [1] 2
01FF 0777 511 AAh 0xAA55
 MBR, total size: 446 + 64 + 2 = 512
 Nguồn: wikipedia 43
 Field length
Offset Description
 (bytes)
 0x00 1 status[7] (0x80 = bootable, 0x00 = non-bootable, other = invalid[8])
 CHS address of first block in partition.[9]
 0x01 3
 The format is described in the next 3 bytes.
 0x01 1 head[10]
 0x02 1 sector is in bits 5–0[11]; bits 9–8 of cylinder are in bits 7–6
 0x03 1 bits 7–0 of cylinder[12]
 0x04 1 partition type[13]
 CHS address of last block in partition.[14]
 0x05 3
 The format is described in the next 3 bytes.
 0x05 1 head
 0x06 1 sector is in bits 5–0; bits 9–8 of cylinder are in bits 7–6
 0x07 1 bits 7–0 of cylinder
 0x08 4 LBA of first sector in the partition
 0x0C 4 number of blocks in partition, in little-endian format
 44
 Nguồn: wikipedia
• Type:
 – 0x07 : Phân vùng chứa “Windows”
 – 0x83 : Phân vùng chứa “Linux”
 – 0x00 : Phân vùng không sử dụng.
Tham khảo thêm: 
 45
46
Partit Starting Ending Status Type First sector Sector#
 ion H T S H T S
1 1 0 1 254 1023 63 0x80 0x0C 63 78140097
2 0 1023 1 254 1023 63 0x00 0x0F 78140160 78156225
 47
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 
 48
• Vấn đề:
 – Thao tác với nhiều tập tin tại một thời điểm ?
 – Thao tác trên cùng một tập tin tại một thời điểm ?
• Các thông tin cần lưu trữ trong bộ nhớ:
 – Mounted Volume Table – Danh sách các volume được sử dụng 
 trên hệ thống
 – Directory Structure – Thông tin các thư mục mới được sử dụng
 • Con trỏ trỏ tới volume tương ứng
 – System-wide open-file Table – Danh sách các tập tin đang được 
 mở trên hệ thống
 • Con trỏ tập tin, định vị tập tin trên đĩa
 • Quyền truy cập
 • Biến đếm tập tin đang mở
 – Per-process open-file Table – Danh sách các tập tin mà tiến trình 
 đang thao tác
 • Con trỏ trỏ tới tập tin đang mở tương ứng trong system-wide open-
 file table 49
50
• 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)
• 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
 – Windows kết buộc hệ thống tập tin vào ổ đĩa
 – Linux kết buộc hệ thống tập tin vào một thư mục
• 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
 – Ví dụ: lệnh mount (Linux)
 51
• First-Come-First-Serve (FCFS)
• Shortest Seek Time First (SSTF)
• SCAN, C-SCAN
• Look, C-Look
 52
 • Phục vụ theo thứ tự yêu cầu
 • Đơn giản nhưng không đáp ứng tốt dịch vụ
Các khối cần đọc (đầu đọc hiện tại tại vị trí 11):
 24 8 21 7 2 14 12
 cylinder number
 scheduling 1 5 10 15 20 25
 queue
 12
 14
 2
 7
 21
 8
 24 53
 time
 Chọn nhu cầu gần với vị trí hiện hành nhất.
 Có nhiều yêu cầu chờ ..chờvà chờ
 cylinder number
 scheduling 1 5 10 15 20 25
 queue
12
14
2
7
21
8
24
 time
 54
• Di chuyển đầu đọc về 1 phía của đĩa đến block xa nhất sau đó di 
 chuyển về phía kia.
• Còn gọi là thuật toán thang máy.
 Các khối cần đọc (đầu đọc hiện tại tại vị trí 11):
 12 14 2 7 21 8 24
 time
 55
 Sector number
 1 5 10 15 20 25
• Trong 
 trường 
 hợp 
 này, 
 SCAN 
 tốt hơn 
 FCFS vì time
 hạn chế 
 sự di 
 chuyển 
 của đầu 
 đọc đĩa 
 56
 time
• Nguyên tắc:
 – Tương tự thuật toán SCAN.
 – Chỉ khác khi di chuyển đến 1 đầu của đĩa thì trở về vị trí bắt đầu của
 đĩa.
 Các khối cần đọc (đầu đọc hiện tại tại vị trí 11):
 12 14 2 7 21 8 24
 time
 57
• Nhận xét:
 – Hai thuật toán lập lịch SCAN và C-SCAN luôn 
 luôn di chuyển đầu đọc của đĩa từ đầu này 
 sang đầu kia và di chuyển đến khối cuối cùng 
 ở mỗi hướng.
• Nguyên tắc:
 – Giống SCAN và C-SCAN nhưng chỉ di chuyển 
 đầu đọc đến khối xa nhất chứ không đến 
 cuối.
 58
Các khối cần đọc (đầu đọc hiện tại tại vị trí 11):
 12 14 2 7 21 8 24
 59