Transcript csci19f1

Chapter 6 : File Systems
•
•
•
•
•
•
•
What is a file system?
Objectives & user requirements
Characteristics of files & directories
File system implementation
Directory implementation
Free blocks management
Increasing file system performance
CS19D - Operating Systems
6-1
File System
• The collection of algorithms and
data structures which perform the
translation from logical file
operations (system calls) to actual
physical storage of information
CS19D - Operating Systems
6-2
Objectives of a File System
• Provide storage of data and manipulation
• Guarantee consistency of data and minimise
errors
• Optimise performance (system and user)
• Eliminate data loss (data destruction)
• Support variety of I/O devices
• Provide a standard user interface
• Support multiple users
CS19D - Operating Systems
6-3
User Requirements
• Access files using a symbolic name
• Capability to create, delete and change files
• Controlled access to system and other users’
files
• Control own access rights
• Capability of restructuring files
• Capability to move data between files
• Backup and recovery of files
CS19D - Operating Systems
6-4
Files
• Naming
– Name formation
– Extensions (Some typical extensions are shown below)
CS19D - Operating Systems
6-5
Files (Cont.)
• Structuring
– (a) Byte sequence (as in DOS, Windows & UNIX)
– (b) Record sequence (as in old systems)
– (c) Tree structure (as in some mainframe Oses)
CS19D - Operating Systems
6-6
Files (Cont.)
• File types
–
–
–
–
Regular (ASCII, binary)
Directories
Character special files
Block special files
• File access
– Sequential access
– Random access
CS19D - Operating Systems
6-7
Files (Cont.)
• File attributes
– Read, write, execute, archive, hidden, system etc.
– Creation, last access, last modification
CS19D - Operating Systems
6-8
Files (Cont.)
• File operations
1. Create
2. Delete
3. Open
4. Close
5. Read
6. Write
CS19D - Operating Systems
7. Append
8. Seek
9. Get attributes
10.Set Attributes
11.Rename
6-9
Directories
• Where to store attributes
– In directory entry (DOS, Windows)
– In a separate data structure (UNIX)
• Path names
– Absolute path name
– Relative path name
– Working (current) directory
• Operations
– Create, delete, rename, open directory, close
directory, read directory, link (mount), unlink
CS19D - Operating Systems
6-10
Directories & Files (UNIX)
Root Directory
Disk A
d1
f1
d2
f2
/
Linked Branch
d3
f4
Working Directory
f3
f5
d4
Disk B
d5
f6
d6
f7
• Working directory : d2
• Absolute path to file f2 : /d1/d2/f2
• Relative path to file f2 : f2
CS19D - Operating Systems
6-11
Physical Disk Space Management
Sector
Track
Cylinder
Heads
• Each plate is composed of sectors or physical
blocks which are laid along concentric tracks
• Sectors are at least 512 bytes in size
• Sectors under the head and accessed without a
head movement form a cylinder
CS19D - Operating Systems
6-12
File System Implementation
• Contiguous allocation
• Linked list allocation
• Linked list allocation using an index (DOS
file allocation table - FAT)
• i-nodes (UNIX)
CS19D - Operating Systems
6-13
Contiguous Allocation
• The file is stored as a contiguous block of data
allocated at file creation
(a) Contiguous allocation of disk space for 7 files
(b) State of the disk after files D and E have been removed
CS19D - Operating Systems
6-14
Contiguous Allocation (Cont.)
• FAT (file allocation table) contains file
name, start block, length
• Advantages
– Simple to implement (start block & length is
enough to define a file)
– Fast access as blocks follow each other
• Disadvantages
– Fragmentation
– Re-allocation (compaction)
CS19D - Operating Systems
6-15
Linked List Allocation
• The file is stored as a linked list of blocks
CS19D - Operating Systems
6-16
Linked List Allocation (Cont.)
• Each block contains a pointer to the next block
• FAT (file allocation table) contains file name, first
block address
• Advantages
– Fragmentation is eliminated
– Block size is not a power of 2 because of
pointer space
• Disadvantages
– Random access is very slow as links have to be
followed
CS19D - Operating Systems
6-17
Linked list allocation using an
index (DOS FAT)
FAT (File allocation table)
0
Disk size
1
EOF
2
Free
3
5
4
Free
5
7
6
Bad
7
1
…..
n
Free
CS19D - Operating Systems
3
5
7
1
File blocks
First block address is in
directory entry
6-18
Linked list allocation using an
index (Cont.)
• The DOS (Windows) FAT is arranged this
way
• All block pointers are in FAT so that don’t
take up space in actual block
• Random access is faster since FAT is
always in memory
• 16-bit DOS FAT length is (65536+2)*2 =
131076 bytes
CS19D - Operating Systems
6-19
Problem
• 16-bit DOS FAT can only accommodate
65536 pointers (ie., a maximum of 64 MB
disk)
• How can we handle large disks such as a 4
GB disk?
CS19D - Operating Systems
6-20
i (index)-nodes (UNIX)
File mode
Number of links
UID
GID
File size
Time created
Time last accessed
Time last modified
10 disk block numbers
Single indirect block
Double indirect block
Triple indirect block
Indirect blocks
CS19D - Operating Systems
Data blocks
6-21
i-nodes (Cont.)
• Assume each block is 1 KB in size and 32 bits (4
bytes) are used as block numbers
• Each indirect block holds 256 block numbers
• First 10 blocks : file size <= 10 KB
• Single indirect : file size <= 256+10 = 266 KB
• Double indirect : file size <= 256*256 +266 =
65802 KB = 64.26 MB
• Triple indirect : file size <= 256*256*256 +
65802= 16843018 KB = ~16 GB
CS19D - Operating Systems
6-22
Directory Implementation
• DOS (Windows) directory structure
• UNIX directory structure
CS19D - Operating Systems
6-23
DOS (Windows) Directory
Structure (32 bytes)
8 bytes
3 1
File name Ext A
10
Reserved
2 2 2
T D P
4
Size
Attributes (A,D,V,S,H,R)
Time of creation
Date of creation
Pointer to first data block
CS19D - Operating Systems
6-24
UNIX Directory Structure
(16 bytes)
2 bytes
I-node #
CS19D - Operating Systems
14 bytes
File name
6-25
The Windows 98 Directory Structure
•Extended MS DOS Directory Entry
•An entry for (part of) a long file name
CS19D - Operating Systems
6-26
The Windows 98 Directory Structure
An example of how a long name is stored in Windows 98
CS19D - Operating Systems
6-27
Path Name Lookup : /usr/ast/mbox
Root (/) i-node
245
Root directory
file block 245
1
.
1
..
4
bin
7
dev
14
lib
9
etc
6
usr
i-node 60 of
/usr/ast/mbox
Blocks of
file
CS19D - Operating Systems
i-node 6 of /usr
132
/usr/ast directory
file block 406
26
.
6
..
60
mbox
92
books
81
src
/usr directory
file block 132
6
.
1
..
19
prog
30
stu
51 html
26
ast
45
genc
i-node 26 of /usr/ast
406
6-28
Two ways of handling long file names in a
Directory
In-line
CS19D - Operating Systems
In a heap
6-29
Shared Files
/
d1
f1
d2
f2
f3
• File f2 is shared by two paths (users!) and there is
one physical copy.
• The directories d1 & d2 point to the same i-node
with link count equal to 2
• Deletion is done by decrementing the link count.
When it reaches zero the file is deleted physically
CS19D - Operating Systems
6-30
Disk Space Management
Block size
• Dark line (left hand scale) gives data rate of a disk
• Dotted line (right hand scale) gives disk space efficiency
• All files 2KB
CS19D - Operating Systems
6-31
How to Keep Track of Free Disk
Blocks
• Linked list of disk blocks
• Bit maps
• Indexing as used in DOS FAT
CS19D - Operating Systems
6-32
Linked List of Disk Blocks
•Allocation is simple.
•Delete block number from free blocks list
CS19D - Operating Systems
6-33
Bit Maps
• The bit map is implemented by
reserving a bit string whose
length equals the number of
blocks
• A ‘1’ may indicate that the block
is used and ‘0’ for free blocks
• If the disk is nearly full then the
bit map method may not be as
fast as the linked list method
CS19D - Operating Systems
6-34
Increasing File System
Performance
• Disks (floopies, hard disks, CD ROMS) are
still slow when compared to the memory
• Use of a memory cache may speed the disk
transfers between disk and process
• Blocks are read into the cache first.
Subsequent accesses are through the cache
• Blocks are swapped in & out using
replacement algorithms such as FIFO, LRU
• System crashes may cause data loss if
modified blocks are not written back to disk
CS19D - Operating Systems
6-35
Where to Put the Current “File
Position” Field
• The file position field is a 16 or 32 bit
variable which holds the address of the next
byte to be read or written in a file
– Put it in the i-node
– Put it in process table
CS19D - Operating Systems
6-36
File Position Field in i-node
• If two or more processes share the same
file, then they must have a different file
position
• Since i-node is unique for a file, the file
position can not be put in the i-node
CS19D - Operating Systems
6-37
File Position Field in Process Table
• When a process forks, both the parent and
the child must have the same file position
• Since the parent and the child have different
process tables they can not share the same
file position
• So, we can not put in process table
CS19D - Operating Systems
6-38
Solution
• Use an intermediate table for file positions
Process tables
File positions table
parent
position
child
CS19D - Operating Systems
i-node
of
file
6-39