Bài giảng Hệ điều hành - Chương 4: Quản lý File

kiếm - search
14. Liệt kê – list, dir11
Tập tin – phương pháp truy cập
Giả thiết: có 1 tập tin lưu danh sách sinh viên
Đặt vấn đề: cần đọc thông tin của sinh viên thứ N
Kích thƣớc mỗi
record
Giải quyết Phƣơng pháp
khác nhau Phải đọc từ đầu Truy cập tuần tự
Giống nhau 1. Tính vị trí logic lưu SV thứ N là
p
2. Di chuyển đến vị trí p và đọc
Truy cập ngẫu
nhiên
Khác nhau
(Có 1 bảng lưu vị
trí lưu mỗi SV)
1. Tra bảng
2. Di chuyển đến vị trí p và đọc
Truy cập index
12
Thư mục
Là một tập tin đặc biệt. Trong nhiều hệ thống thư mục 
được coi như là tập tin
Giúp cho việc quản lý các tập tin dễ dàng hơn. 
Gom nhóm các tập tin vào trong các thư mục theo ý 
nghĩa và mục đích sử dụng của người dùng.
Giúp định vị các tập tin 1 cách nhanh chóng.
Có thể chứa thư mục con. root
bob sue
www fun3013
13
Thư mục - Đường dẫn (Path)
Dùng để xác định vị trí lưu tập tin khi hệ thống
được tổ chức thành cây thư mục:
Đường dẫn tuyệt đối:
Ví dụ: “C:\Downloads\software\baigiang.doc” 
Đường dẫn tương đối:
Ví dụ: “software\baigiang.doc” nếu thư mục hiện hành là
“C:\Downloads\”
Các thư mục đặc biệt:
Thư mục hiện hành (.)
Thư mục cha (..)
14
2. Tổ chức thông tin trên đĩa từ
Đĩa từ - cấu trúc
read-write head
track
sectors 
16
Đĩa từ - cấu trúc
Cấu trúc vật lý của đĩa từ:
Hình tròn, gồm nhiều mặt gọi là head.
Mỗi mặt có nhiều đường tròn đồng tâm gọi là
track.
Trên các đường tròn (track) được chia thành các
cung tròn gọi là sector.
Tập các track đồng tâm gọi là cylinder
Mỗi mặt có 1 đầu đọc để đọc ghi dữ liệu
Mỗi lần đọc/ghi ít nhất 1 cung tròn (512B).
17
Đĩa từ - cấu trúc
Vị trí của mỗi sector trong đĩa được thể hiện bằng
3 tham số : {sector, track, head}.
Head được đánh số từ trên xuống bắt đầu từ 0.
Track được đánh số 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.
Mỗi lần đọc ghi N sector
18
Đĩa từ - cấu trúc
Head 0 Head 2
19
Đĩa từ - dung lượng đĩa
Kích thước đĩa phụ thuộc vào các yếu tố sau:
Số mặt từ, head
Số track trên mỗi mặt từ
Số sector trên mỗi track
Kích thước (byte) trên mỗi track.
20
Đĩa từ - tổ chức đĩa
Các thông số trên đĩa mềm 1.44MB:
2 head, 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.4MB)
Sector logic: 0 đến 2879 và tương ứng với các
sector vật lý như sau:
Sector 0..17 tương ứng với sector vật lý (1,0,0)..(18,0,0)
Sector 18..35 tương ứng với sector vật lý (1,0,1)..(18,0,1)
…
Sector 2879 tương ứng với sector vật lý (18,79,1).
21
Đĩa từ - thuật toán đọc đĩa
First-Come-First-Serve (FCFS)
Shortest Seek Time First (SSTF)
SCAN, C-SCAN
Look, C-Look
…
22
TRUY XUAÁT ÑÓA CÖÙNG
3 yeáu toá aûnh höôûng thôøi gian truy xuaát ñóa
Seek time: thôøi gian di chuyeån ñaàu ñoïc tôùi track 
Latency: thôøi gian ñeå quay ñóa sao cho sector caàn ñoïc
naèm döôùi ñaàu ñoïc
Transfer time: thôøi gian ñoïc/ ghi döõ lieäu leân sector
Thöïc teá: 
Seek time >> latency time > transfer time 
Toái öu seek time  ñònh thôøi truy xuaát ñóa
Toái öu latency time:
Laøm ñóa nhoû, quay nhanh hôn, löu tröõ döõ lieäu lieân quan
gaàn nhau
Choïn kích thöôùc sector, nôi löu tröõ caùc file thöôøng duøng
hôïp lyù
23
CAÙC GIAÛI THUAÄT ÑÒNH THÔØI ÑÓA
Baøi toaùn: Coùù n yeâu caàu ñoïc ñóa ôû caùc track khaùc nhau
x1, x2, … , xN vaøo caùc thôøi ñieåm töông öùng t1, t2, …, tN
 phuïc vuï caùc yeâu caàu ñoù vaøo thôøi ñieåm naøo?
Tieâu chuaån ñaùnh giaù
Coâng baèng
Hieäu suaát cao
Thôøi gian ñaùp öùng trung bình thaáp
Döï ñoaùn ñöôïc thôøi gian phuïc vuï
Moät soá giaûi thuaät tieâu bieåu:
FCFS
SSTF 
SCAN, N-step-SCAN, C-SCAN
CLOOK
24
First Come First Serve - FCFS
Phục vụ theo thứ tự yêu cầu
Đơn giản nhưng không đáp ứng tốt dịch vụ
ti
m
e
cylinder number
1 5 10 15 20 25
12
Các khối cần đọc (đầu đọc hiện tại tại vị trí 11):
142721824
scheduling
queue
24
8
21
7
2
14
12
25
Shortest Seek Time First - SSTF
ti
m
e
cylinder number
1 5 10 15 20 25scheduling
queue
24
8
21
7
2
14
12
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ờ…
26
SCAN
 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.
12 14 2 7 21 8 24
Các khối cần đọc (đầu đọc hiện tại tại vị trí 11):
ti
m
e
27
SCAN vs. FCFS
Trong
trường
hợp này, 
SCAN tốt
hơn
FCFS vì
hạn chế
sự di
chuyển
của đầu
đọc đĩa
Sector number
1 5 10 15 20 25
ti
m
e
ti
m
e
28
C-SCAN
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.
12 14 2 7 21 8 24
Các khối cần đọc (đầu đọc hiện tại tại vị trí 11):
ti
m
e
29
LOOK – C-LOOK
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.
30
LOOK – C-LOOK
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
31
3. Hệ thống quản lý tập tin trên 
Windows
° Phaân hoaïch ñóa cöùng theo chuaån Basic Disk
(Toái ña 4 Primary Partitions hoaëc 3 Primary Partitions + 1 Extended 
Partition, trong soá ñoù coù 1 Active Partition)
Master Boot Record
MBR Partition 1 Partition 2 Partition 3 Partition 4
BR
Boot Record (Sector)
FAT1 FAT2 RootDir ...
Thö muïc Goác
Ñaàu muïc (Directory Entry) troû ñeán taäp tin hay thö muïc con
2 3
Caùc lieân cung (Cluster) 
döõ lieäu
1 Cluster= n Sector
1 Sector=512 Bytes
FAT File System
33
Basic type
Tối đa 4 phân vùng (partition)
Loại partition
Primary
Mỗi phân vùng: ấn định 1 ký tự
Extended
Có thể tạo nhiều logicial drive, ấn định 1 ký tự cho mỗi
logical drive
34
Dynamic type
Chia thành nhiều volume, Không bị giới hạn số
lượng
Loại Volume
Simple
Striped
Spanned
Mirrored (RAID-1)
Redundant Array of Independent Disks (RAID-5)
35
° OÅ ñóa NTFS trong Windows 2000/XP/2003
– Simple Volume: OÅ ñôn döïa treân 1 vuøng nhôù cuûa
Dynamic Disk (phaân bieät vôùi Basic Disk).
Moät ñóa cöùng coù theå phaân hoaïch thaønh nhieàu oå ñôn.
– Spanned Volume: OÅ gheùp traûi treân nhieàu oå ñôn.
– Striped Volume: OÅ song song. Noäi dung moãi taäp tin 
raûi treân nhieàu oå ñôn. Coøn goïi laø RAID-0.
– Mirrored Volume: OÅ aùnh xaï göông. Bao goàm 1 oå ñôn
ñöôïc aùnh xaï töï ñoäng sang 1 oå ñôn khaùc. Coøn goïi laø
RAID-1.
– RAID-5 Volume (Redundant Array of Inexpensive 
Disks): Traûi treân 3 hoaëc hôn oå ñóa ñôn. Döõ lieäu ñöôïc
raûi treân caùc oå ñóa thaønh phaàn cuøng vôùi thoâng tin chaün
leû (parity) ñeå ñaûm baûo khaû naêng khaùng loãi (fault 
tolerance) maø Striped Volume khoâng laøm ñöôïc.
36
Master Boot Record
STT Soá bytes Noäi dung
1 1 Chæ thò Partition (80h = Active, 00h = Khoâng Active)
2 1 Head baét ñaàu
3 2 Cylinder baét ñaàu (10 bits), Sector baét ñaàu (6 bits)
4 1 Chæ thò heä thoáng (Nhaän dieän HÑH)
5 1 Head keát thuùc
6 2 Cylinder keát thuùc (10 bits), Sector keát thuùc (6 bits)
7 4 Sector loâ-gic baét ñaàu (töông ñoái vôùi sector ñaàu tieân)
8 4 Toång soá sector cuûa Partition
– Chöùa chöông trình Khôûi ñoäng, Ñoïc baûng moâ taû caùc 
Partition treân ñóa, Tìm Active Partition, Choïn HÑH, 
Chuyeån ñieàu khieån cho chöông trình trong Boot Record
cuûa Partition vöøa choïn.
– Moãi Partition ñöôïc moâ taû baèng 16 bytes sau:
37
Boot Record
STT Soá bytes Noäi dung
1 3 Leänh nhaûy ñeán ñaàu ñoaïn maõ boot cuûa Boot Record
2 8 Teân vaø soá hieäu phieân baûn HÑH (ví duï: MS DOS 6.0)
3 2 Soá bytes / Sector (thöôøng laø 512 bytes)
4 1 Soá Sector / Cluster
5 2 Döï tröõ
6 1 Soá baûng FAT (thöôøng laø 2)
7 2 Soá ñaàu muïc (Directory Entry) trong Thö muïc goác
8 2 Toång soá sector cuûa Partition
9 1 Nhaän daïng thieát bò (ví duï: F8 h -> Ñóa cöùng)
10 2 Soá sector / baûng FAT
11 2 Soá sector / raõnh (track)
12 2 Soá ñaàu ñoïc (head)
13 4 Soá sector aån (hidden sectors)
14 4 Toång soá sector cuûa Partition
15 1 Soá ñóa vaät lyù
16 1 Döï tröõ
17 1 Kyù hieäu HÑH
18 4 Serial Number
19 11 Volume Label
20 1 Döï tröõ
21 450 Ñoaïn maõ cuûa Boot Record duøng naïp HÑH töø ñóa
38
Caáu truùc Directory Entry trong heä taäp tin 
FAT12 vaø FAT16
Neáu teân taäp tin baét 
ñaàu baèng maõ E5 h, 
taäp tin ñaõ bò loaïi boû
A D V S H R
A - Archive
D - Directory
V -Volume Label
S - System
H - Hidden
R - Read-Only
Soá hieäu 
Cluster 
ñaàu tieân 
cuûa taäp 
tin hay 
thö muïc 
con
Thôøi gian caäp nhaät gaàn nhaát:
- Giôø (5 bit), Phuùt (6 bit), Giaây (5 bit)
- Ngaøy (5 bit), Thaùng (4 bit), Naêm (7 bit)
39
Bytes
Caáu truùc Directory Entry trong heä taäp tin FAT32
Ngaøy truy caäp gaàn nhaát
Nöûa cuoái cuûa soá hieäu 
Cluster ñaàu tieân
Nöûa ñaàu cuûa soá hieäu 
Cluster ñaàu tieân
40
Bytes
Checksum
Caáu truùc Directory Entry duøng chöùa moät phaàn
teân daøi trong Windows 
Soá thöù töï
Toång kieåm 
tra
Caùc thuoäc tính
41
° Baûng FAT
...
12, 16 hoaëc 32 bits -> FAT12, FAT16, FAT32
2
1
0
3
4
5
6
7
8
9
10
11
12
File A.gif treân caùc Cluster: 6, 4, 2
A 6
4
2
EOF
BAD
Khoâng söû duïng cho 
vuøng döõ lieäu
°Moãi doøng trong FAT (keå töø doøng 2
trôû ñi) töông öùng vôùi 1 Cluster trong 
vuøng döõ lieäu.
°Moät soá maõ ñaëc bieät (trong FAT32):
– EOF coù maõ FFFFFFFF h
– BAD coù maõ FFFFFFF7 h
– Troáng öùng vôùi maõ 00000000 h
(cluster töông öùng chöa duøng) 
gif
42
Quá trình boot hệ thống
1. POST (Power-On-Self-Test)
2. Tải MBR để đọc thông tin bảng phân vùng.
3. Tìm phân vùng “active”.
4. Chuyển quyền điều khiển về cho đoạn mã chương
trình nằm trong Boot Record của phân vùng “active”
5. Tải HĐH tại phân vùng “active”. 
Power on
Reboot
Khởi tạo hệ thống
CPU, device controller, main memory, load đoạn code khởi động hđh
43