Formula Sheets: File Systems | Operating System - Computer Science Engineering (CSE) PDF Download

 Page 1


File Systems F orm ula Sheet
File System Basics
• File Size : S
file
=S
disk
, whereS
disk
is disk capacit y .
• Blo c k Size : B = 2
n
, t ypically 512 B to 4 KB.
• Num b er of Blo c ks : N
blo c ks
=?
S
file
B
? .
• In ternal F ragmen tation : F
in ternal
=B-(S
file
modB) .
File A c cess Metho ds
• Sequen tial A ccess : T
access
= T
seek
+T
rot
+T
transfer
, where T
seek
is seek time, T
rot
is rotational
latency ,T
transfer
is data transfer time.
• Direct A ccess : T
direct
=T
seek
+T
rot
+
B
R
, whereR is disk transfer rate.
• Indexed A ccess :
– Index Blo c k Size: I =N
p oin ters
·E , whereE is p oin ter size (e.g., 4 b ytes).
– A ccess Time: T
indexed
=T
index-read
+T
direct
.
File Allo cation Metho ds
• Con tiguous Allo cation :
– External F ragmen tation: F
external
=S
total-free
-S
largest-blo c k
.
– A ccess Time: T
access
=T
seek
+
S
file
R
.
• Link ed Allo cation :
– P oin ter Ov erhead: O
p oin ter
=N
blo c ks
·E .
– A ccess Time: T
access
=N
blo c ks
·(T
seek
+T
rot
+
B
R
) .
• Indexed Allo cation :
– Num b er of Index Blo c ks: N
index
=?
N
blo c ks
N p oin ters
? .
– Max File Size: S
max
=N
p oin ters
·B .
Directory Structures
• Single-Lev el Directory : N
files
=N
en tries
, whereN
en tries
is directory capacit y .
• T w o-Lev el Directory : N
total-files
=N
users
·N
files-p er-user
.
• T ree-Structured Directory :
– Depth: D = log
k
N
files
, wherek is a v erage c hildren p er directory .
– Searc h Time: T
searc h
=O(D·T
disk-access
) .
• Directory En try Size : E
en try
=S
name
+S
metadata
, t ypically 32-64 b ytes.
1
Page 2


File Systems F orm ula Sheet
File System Basics
• File Size : S
file
=S
disk
, whereS
disk
is disk capacit y .
• Blo c k Size : B = 2
n
, t ypically 512 B to 4 KB.
• Num b er of Blo c ks : N
blo c ks
=?
S
file
B
? .
• In ternal F ragmen tation : F
in ternal
=B-(S
file
modB) .
File A c cess Metho ds
• Sequen tial A ccess : T
access
= T
seek
+T
rot
+T
transfer
, where T
seek
is seek time, T
rot
is rotational
latency ,T
transfer
is data transfer time.
• Direct A ccess : T
direct
=T
seek
+T
rot
+
B
R
, whereR is disk transfer rate.
• Indexed A ccess :
– Index Blo c k Size: I =N
p oin ters
·E , whereE is p oin ter size (e.g., 4 b ytes).
– A ccess Time: T
indexed
=T
index-read
+T
direct
.
File Allo cation Metho ds
• Con tiguous Allo cation :
– External F ragmen tation: F
external
=S
total-free
-S
largest-blo c k
.
– A ccess Time: T
access
=T
seek
+
S
file
R
.
• Link ed Allo cation :
– P oin ter Ov erhead: O
p oin ter
=N
blo c ks
·E .
– A ccess Time: T
access
=N
blo c ks
·(T
seek
+T
rot
+
B
R
) .
• Indexed Allo cation :
– Num b er of Index Blo c ks: N
index
=?
N
blo c ks
N p oin ters
? .
– Max File Size: S
max
=N
p oin ters
·B .
Directory Structures
• Single-Lev el Directory : N
files
=N
en tries
, whereN
en tries
is directory capacit y .
• T w o-Lev el Directory : N
total-files
=N
users
·N
files-p er-user
.
• T ree-Structured Directory :
– Depth: D = log
k
N
files
, wherek is a v erage c hildren p er directory .
– Searc h Time: T
searc h
=O(D·T
disk-access
) .
• Directory En try Size : E
en try
=S
name
+S
metadata
, t ypically 32-64 b ytes.
1
F ree Space Managemen t
• Bit V ector :
– Space: S
bit-v ector
=
N
blo c ks
8
b ytes.
– Searc h Time: O(N
blo c ks
) for linear scan.
• Link ed List :
– Ov erhead: O
p oin ter
=N
free-blo c ks
·E .
– Allo cation Time: O(1) for first free blo c k.
• Grouping : Storesn free blo c k addresses in one blo c k,T
searc h
˜O(
N
free
n
) .
• Coun ting : T rac ks con tiguous free blo c ks,S
coun t
=N
groups
·(E
address
+E
coun t
) .
Disk Sc h eduling Algorithms
• First-Come-First-Serv e (F CFS) :
– T otal Seek Time: T
seek-total
=
?
|S
curren t
-S
request
i
| , whereS is trac k p osition.
• Shortest Seek Time First (SSTF) :
– Seek Time: T
seeki
= min(|S
curren t
-S
request
j
|) .
– Risk of starv ation for distan t requests.
• SCAN (Elev ator) :
– T otal Seek Time: T
seek-total
= 2·(S
max
-S
min
) , whereS
max/min
are max/min trac k p ositions.
• C-SCAN (Circular SCAN) :
– Seek Time: T
seek-total
˜S
max
+
?
|S
i
-S
i+1
| , one-w a y tra v ersal.
• LOOK/C-LOOK : Similar to SCAN/C-SCAN but rev erses at last request,T
seek-total
< 2·S
max
.
• A v erage Seek Time : T
a vg-seek
=
T
seek-total
N requests
.
Secondary Memory
• Disk A ccess Time : T
access
=T
seek
+T
rot
+T
transfer
.
• Rotational Latency : T
rot
=
1
2· RPM
·60 s, where RPM is rotations p er min ute.
• T ransfer Time : T
transfer
=
B
R
, whereR is transfer r ate (MB/s).
• Disk Throughput : S =
N
blo c ks
·B
T
total-access
.
Sp o oling and Buffering
• Sp o ol Buffer Size : B
sp o ol
=D
max
, whereD
max
is max job data s ize.
• Sp o oling Ov erhead : T
sp o ol
=T
buffer-write
+T
device-write
, whereT
buffer-write
<T
device-write
.
• Sp o oling Throughput : S
sp o ol
=
N
jobs
T
sp o o l-total
.
• Buffer Size : B
buffer
=B , t ypically m ultiple of blo c k size.
• Buffering Ov erhead : T
buffer
=T
cop y-to-buffer
+T
cop y-from-buffer
, reducesT
disk-access
.
P erformance Metrics
• Storage Utilization : U =
S
used
S
disk
×100% .
• A v erage A ccess Time : T
a vg-access
=
1
N
?
(T
seeki
+T
roti
+T
transferi
) .
• I/O Throughput : S
IO
=
D
total
T
total
, whereD
total
is total data transferred.
• F ragmen tation Ov erhead : T
frag
=F
in ternal
·N
files
+F
external
·T
allo c
.
2