Bài giảng Hệ điều hành - Chương 9: File-System Interface và hiện thực

.hcmut.edu.vn:/oscourse /home/osbook
– Khi file system đã được mount, mọi truy xuất đến file/thư mục trên
đó đều như bình thường, không phân biệt là local hay remote nữa.
8.25
Ví dụ mount remote file-system
/
home
paper osbook
/
oscourse
DFS DSM
Local Client Remote Server
export
mount
DFS DSM
/home/osbook/DSM
/oscourse/DSM
ditlab.hcmut.edu.vn
8.26
Bảo vệ (protection)
 Chủ nhân của một file phải được cung cấp khả năng kiểm soát,
điều khiển quá trình truy cập file
– Các tác vụ có thể thực hiện trên file?
– Những ai được quyền thực hiện thao tác trên file?
 Các kiểu truy xuất file
– Read
– Write
– Execute
– Append
– Delete
– List
 Để kiểm soát quá trình truy cập, cách tiếp cận thông thường là
gán kèm theo mỗi file một access-control list (ACL)
8.27
Access-control list và group
 Các chế độ truy cập: read, write, execute
 Ba nhóm user: owner, group, universe (hay public)
– User name và user identifier (user ID)
– Group name và group identifier (group ID)
 Ví dụ trong UNIX: có 3 field, mỗi field có 3 bits
– Field : read, write, execute
– Bit : r(4), w(2), x(1)
r w x
owner access 7  1 1 1
r w x
group access 6  1 1 0
r w x
public access 1  0 0 1
8.28
File-System Implementation
 Hiện thực hệ thống file
 Những phương pháp cấp phát (Allocation Methods)
 Hiện thực thư mục (Directory Implementation)
 Quản lý không gian trống (Free-Space Management)
 Sao lưu và phục hồi (Recovery)
8.29
Sơ đồ bố trí (layout) hệ thống file (1)
i-nodesPartition control block FCB’s
8.30
Sơ đồ bố trí (layout) hệ thống file (2)
 Partition control block:
– lưu số lượng block trong partition, kích thước block, số lượng free block
hiện thời và các con trỏ chỉ đến chúng,…
– lưu số lượng free FCB hiện thời và các con trỏ chỉ đến chúng,…
– Ví dụ, UNIX File System: “superblock”
 File control block (FCB): mỗi file được quản lý thông qua FCB
của nó
– lưu các thông tin về file , kể cả các con trỏ chỉ đến các data block của nó
– Ví dụ, UNIX File System: “i-node”
8.31
VFS–Virtual File System
disk
partition
disk
partition
ext2 file system FAT file system NFS file system
Ứng dụng
VFS
: gọi hàm/thủ tục
open, read, write, opendir,…
8.32
Hiện thực file
 Cấp phát không gian lưu trữ cho file/directory, mục tiêu:
– sử dụng không gian đĩa hữu hiệu
– truy cập file nhanh
 Các phương pháp cấp phát phổ biến
– Cấp phát liên tục (contiguous allocation)
– Cấp phát theo danh sách liên kết (linked list allocation)
– Cấp phát dùng chỉ mục (indexed allocation)
8.33
Cấp phát liên tục
 Seek time?
 Di chuyển đầu đọc?
 Có thể truy xuất ngẫu nhiên một block của file:
block nr = start + block offset
 Phân mảnh ngoại
 Vấn đề khi tạo file mới và khi cần thêm block
cho file
 Ứng dụng: ISO-9660 (CDROM)
8.34
Cấp phát theo danh sách liên kết (1)
-1
-1
pointer
data
layout của block
8.35
Cấp phát theo danh sách liên kết (2)
 Ưu điểm
– Dễ dàng thêm block cho file khi cần
– Quản lý không gian trống bằng danh 
sách
– Không có phân mảnh ngoại
 Nhược điểm
– Chỉ truy xuất hiệu quả đối với 
sequential-access file
– Tốn không gian lưu trữ các con trỏ
– Độ tin cậy: pointer trong block có thể bị
hỏng 
– Phân mảnh nội khi đơn vị cấp phát là
cluster (một hằng số các block)
8.36
Biến thể của cấp phát theo danh sách liên kết: FAT
 FAT (File Allocation Table)
– Mỗi block đĩa được tượng trưng bởi
một entry trong FAT
– Block với block nr i được tượng
trưng bởi entry với chỉ số (index) i
 Entry chứa block nr kế tiếp
trong file, nếu file gồm nhiều
block
FAT
number of disk blocks - 1
8.37
Cấp phát dùng chỉ mục (1)
 Bảng index (index block)
– chứa địa chỉ các block của file
– thứ tự các địa chỉ trên trong bảng
cũng là thứ tự các block trong file
8.38
Cấp phát dùng chỉ mục (2)
 Ưu điểm
– Random và sequential access
– Không có phân mảnh ngoại
 Khuyết điểm
– Tốn không gian lưu trữ bảng index khi file có kích thước chỉ vài block
 Vấn đề: kích thước index block bao nhiêu là phù hợp?
– Giải quyết: multilevel index
8.39
i-node
 UNIX v7 i-node: 13 pointers
 Linux ext2 i-node: 15 pointers
i-node
8.40
Hiện thực thư mục
MS-DOS UNIX, Linux
 Thư mục được dùng để chứa bảng ánh xạ từ tên file (chuỗi ký tự ASCII) đến
thông tin cần thiết để định vị các block dữ liệu của file
 Tổ chức thư mục
– Danh sách tuyến tính (array hay linear list), bảng băm,…
first block nr
8.41
FAT
 Ví dụ
8.42
Hệ thống file FAT
 FAT dùng để chỉ bảng FAT và cũng dùng để chỉ hệ thống file
 Layout của một partition chứa hệ thống file FAT
Boot sector FAT Root directory Data blocks
8.43
Hiện thực tên file dài
 Giải quyết vấn đề tên file dài (Win98, 2000, XP, *NIX,...)
(a) In-line
(b) Heap
8.44
i-node (1)
Ví dụ
8.45
i-nodes (2)
 Layout của một partition chứa hệ thống file UNIX
8.46
i-node: chia sẻ file (1)
8.47
i-node: chia sẻ file (2)
8.48
Duyệt path name để lấy block nr của file
 Ví dụ: Xác định các block dữ liệu của file /a/b/c
8.49
Quản lý không gian trống
• Các phương pháp
 Bit vector (bit map)
 Linked list
 Grouping
 Counting
8.50
Phương pháp bit vector (bit map)
 Đơn giản và hiệu quả khi cần tìm
khối trống đầu tiên hoặc chuỗi khối
trống liên tục
– Thao tác trên bit
 Cần không gian lưu trữ. Ví dụ
– Kích thước block = 212 bytes
– Kích thước đĩa = 230 bytes
– n = 230/212 = 218 bit (32KB)Ví dụ:
bit vector 00111100…

block 0, 1 trống
block 2, 3, 4, 5 đã được cấp
block 6, 7 trống
…
…
0 1 2 n - 1
bit[ i ] =


 0 block i còn trống
1 block i đã được cấp
8.51
Phương pháp dùng linked list
 Phương pháp
– Liên kết các khối trống với nhau
– Chỉ cần giữ con trỏ đến khối nhớ
trống đầu tiên trên đĩa hoặc cache
trong bộ nhớ chính để tăng tốc
 Ít lãng phí không gian đĩa
• Dò biết khoảng không gian trống liên tục?
 Không hiệu quả: trong trường hợp xấu nhất phải
duyệt toàn bộ đĩa để tìm không gian trống liên tục
8.52
Grouping và counting (1)
 Phương pháp grouping
– Địa chỉ của n khối trống được lưu trong khối nhớ đầu tiên.
– Khối nhớ thứ n chứa địa chỉ của n khối nhớ trống kế tiếp.
 Phương pháp counting
– Tổ chức bảng chỉ mục, trong đó mỗi phần tử của bảng chứa địa chỉ trên
đĩa của khối trống đầu tiên trong nhóm khối trống liên tục kèm theo một
số đếm (cho biết số khối trống trong nhóm).
– Có thể cấp phát hoặc thu hồi đồng thời nhiều khối nhớ liên tục
8.53
Grouping và counting (2)
Counting
2 4
8 6
17 2
25 3
Grouping
Block 2 3, 4, 5
Block 5 8, 9, 10
Block 10 11, 12, 13
Block 13 17, 28, 25
Block 25 26, 27
Ví dụ
8.54
Open file structures
 Thuộc tính toàn cục (global attributes)
– Disk location, size
– Times
– Buffers
– Open count
– Lock(s)
 Thuộc tính riêng của process
– File pointer
– Access permissions
System
open file table
P1
P2
P3
8.55
UNIX: open file structure
User space
Kernel space
data
blocks i-nodes
open file
table
swappable
r/w
file
descriptor
file structure
table
in-core
i-nodes
resident
8.56
Sao lưu và phục hồi dữ liệu
 Kiểm tra sự nhất quán dữ liệu (consistency checker) – so sánh dữ liệu trong
cấu trúc thư mục với các khối dữ liệu trên đĩa và sửa chữa các lỗi không nhất
quán dữ liệu giữa hai bên.
 Dùng chương trình hệ thống để sao lưu (backup) dữ liệu từ đĩa sang các thiết
bị lưu trữ phụ khác như đĩa mềm, đĩa quang, băng từ,... và phục hồi dữ liệu bị
mất từ bản sao lưu.
8.57
Day 3
Day 2
Các kiểu sao lưu dữ liệu
 Normal  Incremental
Data
Day 1 Data
Copied
Day 1
Day 2
Day 3
 Differential
Data
Copied
Day 1
Day 2
Day 3
8.58
Journaling file system
 Journaling file system
– Ghi nhận các lần cập nhật trên file system thành các giao tác (transaction)
– Mọi transaction đều phải được ghi nhận trong log file
– Một transaction được xem là hoàn tất (commit) đã được ghi nhận đầy
đủ trong log file (lúc này, file system có thể chưa được cập nhật)
– Khi file system được cập nhật với đầy đủ mọi tác vụ trong transaction thì
transaction sẽ được xóa đi trong log file.
– Nếu file system bị hỏng hệ điều hành dựa vào các transaction trong log
file để sửa chữa
 Tham khảo thêm Linux-ext3, JFS, NTFS
8.59
MỘT SỐ HỆ THỐNG QUẢN LÝ TẬP TIN
FAT (File Allocation Table)
 Đươïc sử duïng bơûi Ms-Dos, Windows.
 Theo phương phaùp baûng chỉ muïc.
 Coù 3 loaïi FAT : FAT12, FAT16, FAT32.
 Mỗi phaàn tử cuûa FAT quaûn lyù moät cluster.
 Phaàn tử đaàu tiên coù soá thứ tự laø2
 Thươøng bao goàm 2 baûng
 Đươïc định vị sau phaàn khơûi đoäng cuûa đĩa logic
8.60
FAT
FAT
0 X
1 X
2 EOF
3 13
4 2
5 9
6 8
7 FREE
8 Y
9 12
10 3
11 FREE
12 EOF
13 EOF
14 FREE
15 BAD
Kích thöôùc ñóa
Chöa caáp phaùt
Keát thuùc taäp tin
Khoái bò hoûng
Taäp tin A
Taäp tin B
Taäp tin C
6 8 4 2
5 96 12
10 3 13
8.61
FAT
0 Cluster coøn troáng
(0)002- (F)FEF Cluster chöùadöõ lieäucuûacaùc taäp tin
(F)FF0- (F)FF6 Daønhrieâng, khoângduøng
(F)FF7 Cluster hoûng
(F)FF8- (F)FFF Cluster cuoái cuøngcuûachuoãi
8.62
FAT12
Đĩa 1.44Mb sử duïng heä đieàu haønh MS-DOS
Boot Sector(1)
FAT 1(9)
FAT 2(9)
RDET(14)
DATA(2847)
Cluster 2
 1 Cluster = 1 sector
 Cluster 2 Sector logic 33
8.63
FAT12
Đĩa 1.44Mb sử duïng heä đieàu haønh MS-DOS
2
3
4
5
6
7
4
FF7
5
7
FF0
FFF
Kyù hieäu nhaän
dieän đĩa 1.44Mb
240 255 255 4 112 255 5 112 0 240 255 255
Giaù trị FAT
Giaù trị FAT lưu trưõ trong từng byte
từ byte 0
4 = 000000000100
FF7 = 111111110111
00000100 01110000 11111111
8.64
HỆ THỐNG TẬP TIN CỦA UNIX
 Đĩa logic
 Partition
 Block , 1 block = 1024 bytes
 Inode
 Kieåu
 Quyeàn truy xuaát
 Soá lươïng keát noái
Mã cuûa chuû nhân
 Kích thươùc taäp tin
 Ngaøy : caäp nhaät, thay đoåi, boå sung
8.65
HỆ THỐNG TẬP TIN CỦA UNIX
 Sơ đoà vị trí cuûa caùc I_node
Super block I_nodes
Data block
 Super block :
 Kích thươùc cuûa toaøn heä thoáng taäp tin
 Địa chỉ cuûa khoái dưõ lieäu đaàu tiên
 Soá lươïng vaø danh saùch block, I_node coøn troáng
 Ngaøy super block caäp nhaät