ECE391- Computer
System Engineering
Lecture 16
Copyright By PowCoder代写 加微信 powcoder
Filesystems
University of Illinois at Urbana-
§ 1-302 RULES OF CONDUCT
• Students enrolling in the university assume an
obligation to conduct themselves in a manner
compatible with the university’s function as an
educational institution and suitable to members of
the academic community.
a. “…any verbal threat or physically threatening behavior
that would cause a reasonable person to fear for their
f. “Any conduct that substantially threatens or interferes
with the maintenance of appropriate order and discipline
in the operation of the university…”
https://studentcode.illinois.edu/article1/part3/1-302/
Syllabus Addendum
“Behavior that persistently or grossly interferes with
classroom activities is considered disruptive behavior
and may be subject to disciplinary action. Such
behavior inhibits other students’ ability to learn and
an instructor’s ability to teach. A student responsible
for disruptive behavior may be required to leave
class pending discussion and resolution of the
problem and may be reported to the Office for
Student Conflict Resolution for disciplinary action. “
Responding to Disruptive or Threatening Student Behavior: A Guide for Faculty and Staff
Stress management
• Avoid – Believe it or not, you can
simply avoid a lot of stress. Plan
ahead, rearrange your surroundings
and reap the benefits of a lighter
• Take control of your surroundings
• Learn to say no.
• Ditch part of your list.
• Alter -One of the most helpful things
you can do during times of stress is
to take inventory, then attempt to
change your situation for the better.
• Respectfully ask others to change their
• Communicate your feelings openly.
• Manage your time better.
• State limits in advance.
• Accept -Sometimes we may have no
choice but to accept things the way
they are. For those times try to:
• Talk with someone.
• Forgive.
• Practice positive self-talk.
• Learn from your mistakes.
• Adapt – Thinking you can’t cope is
one of the greatest stressors. That’s
why adapting — which often involves
changing your standards or
expectations — can be most helpful
in dealing with stress.
• Adjust your standards.
• Practice thought-stopping.
• Reframe the issue.
• Adopt a mantra.
• Create an assets column.
• Look at the big picture.
https://www.mayoclinic.org/healthy-lifestyle/stress-management/in-depth/stress-relief/art-20044476
Stress management
• Avoid – Believe it or not, you can
simply avoid a lot of stress. Plan
ahead, rearrange your surroundings
and reap the benefits of a lighter
• Take control of your surroundings
• Learn to say no.
• Ditch part of your list.
• Alter -One of the most helpful things
you can do during times of stress is
to take inventory, then attempt to
change your situation for the better.
• Respectfully ask others to change their
• Communicate your feelings openly.
• Manage your time better.
• State limits in advance.
• Accept -Sometimes we may have no
choice but to accept things the way
they are. For those times try to:
• Talk with someone.
• Forgive.
• Practice positive self-talk.
• Learn from your mistakes.
• Adapt – Thinking you can’t cope is
one of the greatest stressors. That’s
why adapting — which often involves
changing your standards or
expectations — can be most helpful
in dealing with stress.
• Adjust your standards.
• Practice thought-stopping.
• Reframe the issue.
• Adopt a mantra.
• Create an assets column.
• Look at the big picture.
https://www.mayoclinic.org/healthy-lifestyle/stress-management/in-depth/stress-relief/art-20044476
Quick Resources
• As always, if it is a true safety emergency, please
• The Counseling Center is open Monday through
Friday, 8 a.m. to 5 p.m. and can be reached at 217-
• The Student Assistance Center can be reached at
(217) 333-0050 or email
• Those needing mental health support after 5 p.m.
and on weekends please contact the Crisis Line at
217-359-4141 (TTY: 217-352-4217) to speak with a
counselor.
https://studentaffairs.illinois.edu/support-resources
Announcements
• Final Checkpoint: 5:59PM on 10/12
• Checkpoint 1: 5:59PM on Tuesday 10/19
• Teams scheduled be released by the end of
Tuesday 10/12
• End of Thursday 10/14
Virtualization
• Virtualization is the process of creating a software-
based, or virtual, representation of something, such
as virtual applications, servers, [memory, cpu, ]
storage and networks.
• How do we virtualize?
https://www.vmware.com/solutions/virtualization.html
• Time sharing is a basic technique used by an OS to
share a resource. By allowing the resource to be used
for a little while by one entity, and then a little while by
another, and so forth, the resource in question (e.g.,
the CPU, or a network link) can be shared by many.
• The counterpart of time sharing is space sharing,
where a resource is divided (in space) among those
who wish to use it.
• For example, disk space is naturally a spaceshared resource;
once a block is assigned to a file, it is normally not assigned to
another file until the user deletes the original file.
• What did we just share last lecture? How? What else
might we virtualize?
https://pages.cs.wisc.edu/~remzi/OSTEP/
• By the end of this sequence you should
understand:
• the role of a file system in an operating system
• user and applications view of the UNIX filesystem
• the virtual file system interface
• how the ext2 operating system works
• The ECE 391 MP 1 filesystem
Acknowledgements
• M. J. Dominus
• http://perl.plover.com/classes/ext2fs/samples/slide001.html
• . Antonelli
• http://www-personal.umich.edu/~cja/
• http://www.cs.uiuc.edu/class/fa07/cs423/overheads.html
• Remzi H. Arpaci-Dusseau and . Arpaci-Dusseau
• http://pages.cs.wisc.edu/~remzi/OSTEP/
• Understanding the Linux Kernel (ULK)
• Chapter 12, 15, 16, 18
Filesystems
the role of a file system in an operating system
Generic Files and Filesystems
• Must store large amounts of information
• Must survive termination of process using the
information
• Must allow other processes to access the
information
• OS abstracts from the physical properties of its
storage device to define a logical storage unit,
called file. Files are mapped by the OS onto physical
Differing Perspectives on Design
System Software
• Block oriented
• Physical sector #s
• No protection among
users of the system
• Data might be
corrupted if machine
Application Software
• Byte oriented
• Named files
• Users protected from
each other
• Robust to machine
Systems Software Challenges
• Workloads
• Files grow and shrink in pieces
• Little a priori knowledge
• Performance
• Overcoming disk, tape, SSD performance behavior
Application workloads and system
software design
• How are files organized by applications?
• Unstructured data – User program decides meaning (most common)
• Records – Fixed length
• Indexed data – Tree or other structure of records with keys
• How do applications access files?
• Sequential: bytes read in order (most common)
• Random: read/write element out of middle of arrays
• File characteristics (measurements of UNIX and NT)
• Most files are small (about 8KB)
• Most of the disk is allocated to large files – (90% of data is in 10% of
• Large files use up most of the disk space
• Large files account for most of the bytes transferred
• Bad news is we need everything to be efficient all the time
File System Design Considerations
• How will we organize the storage on the physical
device (layout)?
• How do we create new storage for a file
(allocation)?
• How do we keep track of what is used and free
(tracking of free blocks)?
• How do we organize files (directories)?
Example designs: allocation
• Contiguous blocks?
• Linked-List of blocks?
• Linked-List of blocks + Table?
• I-nodes?
Contiguous Allocation
• Simple: store 2 #ʼs
• Efficient: 1 seek
• Random Access
• Must know file size
• Fragmentation
Linked-List Allocation
• Index with address to first
• First word points to next
• Can grow files
dynamically
• Random Access is slow
• Internal Fragmentation
• Incomplete block sizes
• Unreliable: what if you
lose one Block in chain?
Linked-List + Table
• FAT in memory
• pointers stored in table
(block,next)
• next = -1 indicates eof
• Full block size available
• Random Access w/o disk
• Directory can store 1 #
• FAT must be stored in
• 20 GB disk
• 1 KB block
• 1 word per entry
• => 80 MB!
Example file: 4, 7, 2, 10, 12
Indexed Allocation
• Associate each file with
data structure: i-node
• table of fileʼs blocks
• Only need i-nodes in
memory for open files
• set max # of open files
Example designs: tracking free
• Must keep track of blocks that are free
Free Block List
• Block Contents:
• entries of other block addresses that are free
• last entry points to another block
• Pros/Cons:
• Can be large
• Can be stored on Free Blocks
• Can load one block into memory at a time
• 16 GB free, 1 KB blocks, 4 bytes per entry => 65,794
Free Bitmap
• 1 bit per block (1 = free, 0 not free)
• 16 GB free, 1 KB blocks, 1 bit per entry => 2,048 blocks
• Fixed in size
• Free list can be smaller if few free pages
• Can have 1 block in memory at a time
Filesystems
A brief primer on user and application software perspectives
UNIX File System
• UNIX File – a sequence of 0 or more bytes
containing arbitrary information
• Meaning of the bits is entirely up to the fileʼs owner
• File Names
• up to 255 characters (BSD, System V,…)
• Base name + extension
• A (regular) file is a linear array of bytes that can be
read or written starting at any byte offset in the file
• The size of the file offset determines the absolute
maximum size of any file
• E.g., 32b offset, 4,294,967,296B file
UNIX Filesystem Calls
UNIX Filesystem Concepts
• File names are stored in a file called a directory
• Directories may refer to other directories as well as
• A hierarchy of these directories is called a
filesystem
• Each filesystem tree (a connected graph with no
cycles) has a single topmost root directory
• Hardware devices are represented as special files
• A UNIX mantra: everything is a file
Important Directories in most
UNIX Systems
Absolute vs. relative path names
• A file is accessed using its path name
• Absolute path name
• /dir1/dir2/…/dirn/filename
• /opt/moab/etc/moab.cfg
• Relative path name
• current-working-directory/filename
• moab.cfg
• Every process maintains a notion of a current working
• Initialized at login from /etc/passwd home directory field
• Changed via chdir() system call
Soft Links
• A symbolic link, also termed a soft link, is a special kind
of file that points to another file, much like
a shortcut in Windows or a Macintosh alias.
• Unlike a hard link, a symbolic link does not contain the
data in the target file. It simply points to another entry
somewhere in the file system.
• Can soft link directories
• Now it’s a filesystem graph
• Can cross filesystem boundary
• Separate permissions for different links
• “Dangling softlink” if pointed-to file is deleted
https://kb.iu.edu/d/abbe
UNIX Filesystem Directory Calls
Filesystems
Virtual file systems
The UNIX Filesystem
• In the beginning, there were two
• UNIX™ File System (1971)
• Berkeley Fast File System (1983)
• After that, things got complicated
http://en.wikipedia.org/wiki/Berkeley_Software_Distribution
Virtual File System
• The role of the VFS is:
• Keep track of available filesystem types.
• Associate (and disassociate) devices with instances of
the appropriate filesystem.
• Do any reasonable generic processing for operations
involving files.
• When filesystem-specific operations become necessary,
vector them to the filesystem in charge of the file,
directory, or data structure (i.e., inode) in question.
http://www.tldp.org/LDP/khg/HyperNews/get/fs/vfstour.html
ECE391- Computer
System Engineering
Lecture 16
Filesystems (cont.)
University of Illinois at Urbana-
What is an infraction of academic
integrity?
• Cheating – using or attempting to use unauthorized
• Plagiarism – representing the words, work, or ideas of
another as your own
• Fabrication – the falsification or invention of any
information, including citations
• Facilitating Infractions of Academic Integrity – helping or
attempting to help another commit an infraction
• Bribes, Favors, and Threats – actions intended to affect a
grade or evaluation
• Academic Interference – tampering, altering or destroying
educational material or depriving someone else of access to
that material
https://provost.illinois.edu/policies/policies/academic-integrity/students-quick-reference-guide-to-academic-integrity/
Announcements
• Checkpoint 1: 5:59PM on Tuesday 10/19
• Teams scheduled be released by the end of
Tuesday 10/12
• End of Thursday 10/14
• 10/13/2021 (yesterday)
• 10/28/2021, 7-9 PM, ECEB 1002
• Conflicts by 10/22/2021
• No Class 10/28/2021
Filesystems
What’s ext2fs?
• It’s the Extended Filesystyem for Linux
• (Version 2)
• I don’t know what became of version 1
• Very common
• Probably most of your Linux system disks are ext2fs
http://perl.plover.com/classes/ext2fs/samples/slide001.html
Where’s the Code?
• Where’s the Code
• Unix filesystems all have certain structures in
• Generic Unix FS internals
• Generic code is in /usr/src/linux/fs
• Also /usr/src/linux/include/linux/fs.h and elsewhere
• Differences in ext2
• ext2-specific code is in /usr/src/linux/fs/ext2
• Also /usr/src/linux/include/linux/ext2*.h
Overview of Unix Filesystem
• There are three important parts:
• Superblock (only one of these)
• Inodes (one per file)
• Data blocks (the rest of the disk)
• The superblock represents the entire filesystem
• Each inode represents a single file
• These belong to the system—they have a fixed format
• You cannot read or write them directly
• The data blocks belong to the user
• That’s where the data is stored
• Typically, 8kb each
Overview of Unix Filesystem
• ext2fs is a little different
• There are some other structures between the superblock
and the inodes
• There are bitmaps recording which blocks are in use and
which inodes
• One bit per block or inode
• The disk is partitioned into ‘block groups’
• Each block group has a copy of the superblock and bitmaps,
some of the inodes, and some data blocks
• That way if the superblock or bitmaps are destroyed they
can be restored from a copy
• So the picture above shows a single block group instead of
the entire disk
struct file_system_type {
const char *name;
int fs_flags;
struct super_block *(*get_sb)(struct file_system_type *,
int, char *, void *, struct vfsmount *);
void (*kill_sb) (struct super_block *);
struct module *owner;
struct file_system_type *next;
struct list_head fs_supers;
struct lock_class_key s_lock_key;
struct lock_class_key s_umount_key;
Linux Virtual File System Objects
Superblocks
• The first block is the ‘superblock’
• Metainformation about the entire filesystem is
stored there
• What kind of filesystem is it?
• How many blocks are there? How many are free?
• (This must be stored somewhere, or else df would take forever)
• How big are the blocks?
• How many inodes are there? How many are free?
• Code for reading in the superblock is in super.c
• (That’s /usr/src/linux/fs/super.c)
struct super_block {
dev_t s_dev;
unsigned long s_blocksize;
struct file_system_type *s_type;
struct super_operations *s_op;
struct dentry *s_root;
struct super_operations {
struct inode *(*alloc_inode)(struct super_block *sb);
void (*destroy_inode)(struct inode *);
void (*read_inode) (struct inode *);
void (*dirty_inode) (struct inode *);
void (*write_inode) (struct inode *, int);
void (*put_inode) (struct inode *);
void (*drop_inode) (struct inode *);
void (*delete_inode) (struct inode *);
void (*put_super) (struct super_block *);
void (*write_super) (struct super_block *);
int (*sync_fs)(struct super_block *sb, int wait);
void (*write_super_lockfs) (struct super_block *);
void (*unlockfs) (struct super_block *);
int (*statfs) (struct super_block *, struct statfs *);
int (*remount_fs) (struct super_block *, int *, char *);
void (*clear_inode) (struct inode *);
void (*umount_begin) (struct super_block *);
int (*show_options)(struct seq_file *, struct vfsmount *);
https://www.win.tue.nl/~aeb/linux/lk/lk-8.html Linux Virtual File System Objects
Virtual File Systems
• Operations like read, mount, and so on are performed
differently for different kinds of file systems
• The code for reading a ramdisk is very different than for reading a
• The kernel deals with this by creating an abstraction layer
• Typically, the top layer will have a list of filesystem types
• Each filesystem type will have a virtual method table
• When you load in a kernel module:
• The module provides functions for the file system operations
• And it registers the method table in a global kernel data structure
• Usually a linked list
• There is a similar organization further down to handle
different kinds of physical devices
Virtual File Systems
• To mount:
• Look up the file system type in the list
• Find the method table for this file system type
• Invoke the read_super method for this file system type
• Actually the method tables in file_system_type list
have only this one method!
• That’s because you can’t do anything else until you’ve
loaded the superblock anyway
• Once the superblock is read in, you can do more
Superblocks
• Each time you mount a filesystem, the kernel builds
a struct super_block
• This struct contains a method table of superblock
operations
• The structs are linked into a list
• mount’s job is to build this struct and put it into the list
• Typical mount call:
• mount(“/dev/hdb2”, “/home”, “ext2”, …);
• In some sense, the inode is the most interesting structure on the
• More than any other single struct, the inode is what makes unix unix
• The inode represents a file
• i for index
• The inodes are addressed starting with 1
• Each inode’s number is its i-number
• The inode contains all the important information about the file:
• Who owns the file? What are the permissions?
• Is it a plain file, or a directory, or a symlink, or something else?
• When was it last modified? When was it last accessed?
• And, most important: Which data blocks hold its data?
• In fact, the only important property of a file that isn’t in the inode
is the name!
struct inode {
unsigned long i_ino;
umode_t i_mode;
uid_t i_uid;
gid_t i_gid;
kdev_t i_rdev;
loff_t i_size;
struct timespec i_atime;
struct timespec i_ctime;
struct timespec i_mtime;
struct super_block *i_sb;
struct inode_operations *i_op;
struct address_space *i_mapping;
struct list_head i_dentry;
Linux Virtual File System Objects
Directories
• Why isn’t the name of a file in the inode?
• Because on a Unix system, a file can be known by more than one name
• For example, /home/mjd/Mail/.., /home/mjd/., and /home/mjd are all
the same file
• It’s the directories that supply names, not the inodes
• Directories are stored as data block and referenced by an inode.
• A directory file is a linked list of directory entry structures.
• Each line is called a link. It has a name and an i-number
• Hence the link and unlink system calls
• The actual format of a link varies from version to version of Unix
• Originally, each link was ju
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com