Transcript document

CS 6560 Operating System
Design
Lecture 13
Finish File Systems
Block I/O Layer
VFS File Objects and Structures
• superblock object
– Represents an entire mounted filesystem
• inode object
– Represents a particular file in a mounted filesystem
• file object
– Represents an instance of an opened file
• dentry object
– Represents a path component = name, indoe
• vfsmount
– Represents a mount point
• file_system_type
– Represents a filesystem type
Process Descriptor
Scheduling info
Process hierarchy info
fs_struct
fs
files
mm
sig
files_struct
(Open Files)
…
Process Descriptor
mm_struct
(Memory Descriptor)
signal_struct
fs_struct
• This table specifies the dentry objects of the
process’ root and current directory.
• It also contains the process’ umask (a bit
mask used to automatically turn off
permissions when creating files).
Process Descriptor’s fs_struct
root
Scheduling info
dentry object
Process hierarchy info
fs
files
mm
sig
…
vfsmount
structure
superblock object
current
fs_struct
dentry object
Process Descriptor
vfsmount
structure
superblock object
files_struct
• This table specifies the opened files of a process
• It contains a pointer to an array of file objects,
indexed by the file descriptor, returned from
creating the file or inherited.
• It contains bit maps to indicate which file objects
are active and which are to be closed on exec.
• It also contains the current and max number of file
objects and the number of processes sharing this
table.
Open Files of a Process
Scheduling info
Process hierarchy info
fs
files
mm
sig
…
files_struct
(Open Files)
file object
dentry object
inode object
file object
dentry object
inode object
file object
dentry object
inode object
…
Process Descriptor
file object
dentry object
inode object
fd
open files
directory
represents
(has f_pos)
link
actual files
Relationships
• The open files table may be shared by several processes. This happens
when processes share their address space (threads).
• Each open files table has a list of open files (file objects), indexed by
file descriptor (returned from opening the file)
• Each open file (file object) can be shared by several open files tables
and hence by several processes. This happens when a process forks.
Parent and child share the same open files.
• Each open file (file object) has one dentry object.
• Each dentry object can be shared by several file objects. This happens
with dup and some redirection.
• Each dentry object has one inode object.
• Each inode object can be shared by several dentry objects. This
happens because of hard and symbolic links.
• Each inode has one superblock object, making it belong to one
mounted filesystem.
file_system_type objects
• The system maintains a (linked) list of valid file
types. Each file type is represented by a
file_system_type object.
• This object has a name for the file system type.
• This object has a method for creating a superblock
object.
• It also points to the module that governs this file
type (if modulerized)
• This object heads a list of superblock objects that
belong to this file type.
File system types
The file_system_type Structure
struct file_system_type {
struct super_block *(*read_super) (struct
super_block *, void *, int);
const char *name;
int requires_dev;
/* there's a linked list of types */
/* struct file_system_type * next; /*
}
Mounted Filesystems by Type
File_system_type
object
superblock
object
dentry
superblock
object
dentry
of
mount
of
mount
File_system_type
object
superblock
object
dentry
superblock
object
dentry
of
mount
of
mount
File_system_type
object
superblock
object
dentry
superblock
object
dentry
of
mount
of
mount
Block I/O
Block and Character Devices
• Character device
– Provides a stream of byte-sized data– Examples: keyboards and serial ports
• Block device
– Provides random access to blocks of data
– Example: hard disks and CDROMs
Physical Organization of Block Devices
– Physically organized in cylinders, tracks, and
sectors
•
•
•
•
•
Cylinder = one position of read/write head
Sector = one unit of data
Linear array of cylinders on device
2D array of sectors in each cylinder
Takes a long time to move read/write head among
cylinders (This is called head seeking.)
• Takes a shorter time to wait for sector transfer
within cylinder.
Abstraction of Block Devices
• The kernel abstracts block devices with an
“one size fits all” approach.
Components of the FS
Directory
Cache
VFS
EXT2
VFAT
EXT3
NFS
NTFS
Buffer Cache
Disk Driver
Disk Driver
proc
Inode
Cache
Sectors, Blocks, Pages
• Data granularity for physical devices, their
common abstraction in the kernel, and the
virtual memory management are:
– Sector = granularity of data on block device
– Block = granularity of data for kernel
abstraction of block devices (must be a multiple
of sector size)
– Page = granularity of data for virtual memory
(must be a multiple of block size)
Buffer Heads
• The block I/O system of the kernel maintains a pool of buffer that are
described by structs called buffer heads.
• Each buffer head serves as the representation of one block. It is a data
structure that has fields for
•
– State - bit flags in a long int (see page 238)
– Usage counter
– Reference to a page of virtual memory
– Logical block number
– Block size
– Pointer to the data in the block
– Pointer to a structure that represents the device where the block is stored
– And more
In previous versions of Linux, buffer heads were the primary unit for handling
buffer I/O.
The bio structure
• With Linux 2.5 the basic container structure for block I/O
is the bio.
• Each bio structure represents on I/O request (read a block
or write a block to storage device)
• The bio structures are organized in linked lists
• The bio structure contains
–
–
–
–
–
–
Sector identification
Reference to the next bio structure in the list
Reference to the structure representing the storage device
Status and command flags as bits in an unsigned int
Operation (read or write)
Management data
New and Old
• See page 242 for comparison
Request Queues
• Block devices maintain request queues
• Each request is represented by a structure
(called request) that references a set of bio
structures.
I/O Scheduling
• The I/O scheduler merges and sorts requests
to give optimal performance. (minimizing
head seeks).
• Job of scheduler (See page 244)
– Goals: optimal global throughput
• Minimize head seeks
– Operations: merge and sort
Linux Schedulers
• Linus Elevator (Linux 2.4)
• Four scheduler available in Linux 2.6
–
–
–
–
Deadline Scheduler
Anticipatory I/O Scheduler
Complete Fair Queuing I/O Scheduler
Noop Scheduler