Transcript CENG334 Introduction to Operating Systems

CENG334
Introduction to Operating Systems
Filesystems and their interface
Topics:
Erol Sahin
Dept of Computer Eng.
Middle East Technical University
Ankara, TURKEY
Acknowledgements: The following are adapted from slides that were originally
prepared by Matt Welsh, Andrew Tanenbaum (MOS3e) and others that I may have lost
track of. I search the web for the best content out there and try to improve the slides
both in form and content as much as possible as well as to complement them with my
own. If your slides are among them, and not acknowledged, feel free to drop me an
email. If you object to their use as such, let me know and I’ll exclude them..
1
Filesystems
A filesystem provides a high-level application access to disk
 As well as CD, DVD, tape, floppy, etc...
Masks the details of low-level sector-based I/O operations
Provides structured access to data (files and directories)
Caches recently-accessed data in memory
Adapted from Matt Welsh’s (Harvard University) slides.
2
Filesystems
Essential requirements for long term storage:
It must be possible to store a very large amount of information.
The information must survive the termination of the process using it.
Multiple processes must be able to access the information concurrently.
Think of a disk as a linear sequence of fixed-size blocks and
supporting reading and writing of blocks.
How do you find information?
How do you keep one user from reading another’s data?
How do you know which blocks are free?
Slide adapted from: Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
3
Filesystem Operations
Filesystems provide a standard interface to files and directories:






Create a file or directory
Delete a file or directory
Open a file or directory – allows subsequent access
Read, write, append to file contents
Add or remove directory entries
Close a file or directory – terminates access
What other features do filesystems provide?






Accounting and quotas – prevent your classmates from hogging the disks
Backup – some filesystems have a “$HOME/.backup” containing automatic snapshots
Indexing and search capabilities
File versioning
Encryption
Automatic compression of infrequently-used files
Adapted from Matt Welsh’s (Harvard University) slides.
4
File Concept
File is a logical storage unit abstraction provided by the
operating system.
Files are mapped by the operating system onto physical
devices (disks, tapes, CDs, etc..)
From the user point of view, file is the only unit through
which data can be written onto storage devices.
The information in a file as well as the attributes of the
file is determined by its creator.
 Data
 Numeric/character/binary
 Program
When a file is created, it becomes independent of the
process, the user and even the system that created it.
5
File Operations
OS provides a number of minimal operations on a file.
 Create
 Allocate space and then make an entry in the directory
 Write
 Requires name of the file, and the information to be written
 Search the directory to find file’s location.
 Keep a write-pointer to the location in the file
 Update the pointer after each write
 Read
 Requires name of the file, and the information to be read
 Search the directory to find file’s location.
 Keep a read-pointer to the location in the file
 Update the pointer after each read
 Reposition within file
 Change the value of the file-position pointer
 Delete
 Deallocate the space and remove the entry
 Truncate
 Change the allocated space to zero, and deallocate its space
6
File Attributes
Name – only information kept in human-readable form
Identifier – unique tag (number) identifies file within file system
Type – needed for systems that support different types
Location – pointer to file location on device
Size – current file size
Protection – controls who can do reading, writing, executing
Time, date, and user identification – data for protection, security, and usage
monitoring
Information about files are kept in the directory structure, which is maintained on the
disk
7
File Types – Name, Extension
The file type provides information on
what can be done with that file to the
OS.
Typically implemented as the extension
of the filename.
In UNIX systems, a crude “magic
number” is stored at the beginning
of some files to indicate the type of
the file (executable/shell script..)
In Mac OS X, each file has a type
TEXT/APPL. Each file also has a
creator attribute that is set to the
program that created it.
8
File Structure
None - sequence of words, bytes
 This is the structure supported by UNIX systems
Simple record structure
 Lines
 Fixed length
 Variable length
Complex Structures
 Formatted document
 Relocatable load file
Can simulate last two with first method by inserting appropriate control
characters
Who decides:
 Operating system
 Program
9
Access Methods
Sequential Access
read next
write next
reset
no read after last write
(rewrite)
Direct Access (available when the file is
made up of fixed-length logical records,
useful in databases)
read n
write n
position to n
read next
write next
rewrite n
n = relative block number
10
Open Files
Most file operations require searching the directory for the entry
associated with the file. To avoid this constant search, most
systems require that file be “open”ed, before its use.
 open(Fi) – search the directory structure on disk for entry Fi, and move the content of
entry to memory
 close (Fi) – move the content of entry Fi in memory to directory structure on disk
Several pieces of data are needed to manage open files:
 File pointer: pointer to last read/write location, per process that has the file open
 File-open count: counter of number of times a file is open – to allow removal of data
from open-file table when last processes closes it
 Disk location of the file: cache of data access information
 Access rights: per-process access mode information
11
Directories
•
•
•
A directory is effectively a
symbol table that translates
file names into their
directory entries.
A directory is simply
another file that needs to
be treated in a special way.
Both the directory structure
and the files reside on disk
12
Operations Performed on Directory
 Search for a file
 Given a name or a pattern of names, we should be able to find all the files that use
it.
 Create a file
 touch assignment3.c
 Delete a file
 rm assignment3.c
 List a directory
 ls
 Rename a file
 mv assignment3.c odev3.c
 Traverse the file system
 cd include
13
Organize the Directory (Logically) to Obtain
Efficiency – locating a file quickly
Naming – convenient to users
 Two users can have same name for different files
 The same file can have several different names
Grouping – logical grouping of files by properties, (e.g., all Java
programs, all games, …)
14
Tree-Structured Directories
A directory is simply another file that needs to be treated in a
special way.
15
Acyclic-Graph Directories
Have shared subdirectories and files
What would happen if we rm /dict/count?
16
Access Lists and Groups
Mode of access: read, write, execute
Three classes of users
RWX
a) owner access
RWX
b) group access
RWX
c) public access
7
=> 1 1 1
6
=> 1 1 0
1
=> 0 0 1
Ask manager to create a group (unique name), say G, and add some users to the
group.
For a particular file (say game) or subdirectory, define an appropriate access.
owner
chmod
group
761
public
game
Attach a group to a file
chgrp
G
game
17
CENG334
Introduction to Operating Systems
Filesystem implementation
Topics:
•File implementation
•Directory implementation
Erol Sahin
Dept of Computer Eng.
Middle East Technical University
Ankara, TURKEY
URL: http://kovan.ceng.metu.edu.tr/~erol/Courses/CENG334
18
File System Layout
A possible file system layout with a Unix partition
1
19
Disk Space Organization
Disk can be partitioned
Each partition can have a different OS and/or different file system
One partition can be swap space for main memory
First block of disk has master boot record specifying primary partition
Each partition has
Boot block (loads OS in kernel space)
Superblock (contains key info about file system which is read into memory at boot
time)
Free space management
List of I-nodes (or other data structure) giving info about all files
Directories and Files
2
20
Implementing Files
21
File Space Allocation
Goals
Fast sequential access
Fast random access
Ability to dynamically grow
Minimum fragmentation
Standard schemes
Contiguous allocation (fixed)
Linked list allocation
Linked list with file allocation table (FAT)
Linked list with Indexing (I-nodes)
22
Contiguous Allocation
(a) Contiguous allocation of disk space for 7 files.
(b) The state of the disk after files D and F have been removed.
Slide adapted from: Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
23
Contiguous Allocation
Each file occupies a contiguous region of blocks
Fast random access (only one seek needed)
Useful when read-only devices or small devices
CD-ROMs, DVD-ROMs and other optical media
Embedded/personal devices
Management is easy
Directory entry of a file needs to specify its size and start location
Fragmentation is a problem if deletes are allowed, or if files grow in
size
After disk is full, new files need to fit into holes  advanced
declaration of size at the time of creation
2
24
Linked List Allocation
Storing a file as a linked list of disk blocks.
Slide adapted from: Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
25
Linked List Allocation
Natural choice: maintain a linked list of blocks that contain each file
Directory entry of a file points to first block, and each block begins
with a pointer to next block
No external fragmentation
Speed of random access is slow
Accessing nth block requires n disk accesses, i.e. n-1 accesses for pointers
Data size in a block is no longer power of 2 because of pointer
storage
2
26
Linked List Allocation with FAT
Linked list allocation using a file allocation table in main
memory. Will be discussed more in detail in FAT.
Slide adapted from: Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
27
Linked List with FAT
So pointers are trouble, don’t store them in blocks!
Solution: Maintain a File Allocation Table in main memory
FAT is an array indexed by blocks
Each array entry is a pointer to next block
Accessing nth block would still require traversing the chain of
pointers, however, they are in main memory and no disk I/O is
needed
Problem: the entire FAT must be in memory, and as disk size
increases, so does FAT
20GB disk with 1k block size needs 20 million entries, which requires entry sizes
of minimum 3 bytes, which is results a FAT of 60MB
2
28
I-nodes (Unix*) for File Indexing
Slide adapted from: Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
29
Indexing with i-nodes
Each file has an associated fixed length record called an i-node
i-node maintains all attributes of the file
i-node also keeps addresses of fixed number of blocks
Additional levels of indexing possible to accommodate larger files
last address reserved for pointer to another block of addresses
Space required is much less than FAT
only i-nodes of open files need to be in memory
an array of i-node numbers, whose size is proportional to the max # of open files
allowed by the system, not disk size
Time required to access specific block can vary
3
30
Implementing Directories
31
Directories
A directory entry provides the info needed to find the disk data blocks
of a file
disk address of first block and size
address of first block
number of associated i-node
File attributes can be stored in the directory entry (Windows) or in its
i-node (Unix)
File name and support of variable length and long file names (255
chars)
3
32
Implementing Directories (1)
(a)
(b)
A simple directory containing fixed-size entries with the disk addresses and
attributes in the directory entry.
A directory in which each entry just refers to an i-node.
Slide adapted from: Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
33
Sharing Files
File system containing a shared file.
Slide adapted from: Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
35
Sharing Files with Links
Convenient solution to file sharing
Hard link
pointer to i-node added to the directory entries
link counter in the i-node linked to incremented
i-node can only be deleted (data addresses cleared) if counter goes down to 0, why?
original owner can not free disk quota unless all hard links are deleted
Soft link (symbolic)
new special file created of type LINK, which contains just the path name
new file also has its own i-node created
How about the shortcuts in Windows?
3
36
Sharing Files through hard links in Unix
(a) Situation prior to linking. (b) After the link is created. (c) After the
original owner removes the file.
37
Keeping track of Free Space
38
Keeping track of Free Blocks -1
Linked list of disk blocks, with each
block filled with free disk block
numbers.
With 1KB block size, and 32 bit
disk block number, each block
can hold the numbers for 255 free
blocks. The 256th slot points to
the next block holding free disk
blocks.
Example:
 500 GB disk has approx. 488 million
blocks.
 If the disk is empty: storing the free
blocks requires 488 million/255 = 1.9
million blocks.
 If the disk is nearly full, then the
linked list requires small.
Storage is essential free.. Free
blocks are used.
39
Cont’d
The free list method can be enhanced..
Instead of keeping track of each free block, we can keep track of
consecutive free blocks represented by:
The address of the first free block
The count of free blocks
In the free list method, only one block of pointers need to be stored in
the memory. When it runs out, another one can be brought into the
memory.
40
Keeping track of Free Blocks -2
One bit for keeping the state of each block.
1 : free blocks
0 : allocated blocks
500 GB disk, 1KB blocks
488 million bits = 60000 1KB blocks
For an empty disk:
Less space than linked list method, since we use
1-bit instead of 32-bits for each free block
43
Managing Free Disk Space
How to keep track of free blocks?
Linked List Method
Maintained as a list of blocks containing addresses of free blocks
Each block address is 32 bits or 4 Bytes
A 1KB block used can hold addresses of 255 free blocks and an address of the next
block in the list for free space management
Note: This list is stored in free blocks themselves
Bitmap method:
Keep an array of bits, one per block indicating whether that block is free or not
A 16-GB disk has 16 million 1 KB blocks
Storing the bitmap requires 16 million bits, or 2048 blocks
How do the two methods compare in terms of space requirements?
44
CENG334
Introduction to Operating Systems
Filesystems – Case studies
Topics:
FAT
UNIX V7
Erol Sahin
Dept of Computer Eng.
Middle East Technical University
Ankara, TURKEY
45
FAT (MS-DOS) Filesystems
Originally invented as a method for storing data on floppy disks, first
version has single directory
Later used by MS-DOS with supports for a hierarchical directory
structure, and fixed disks as well as floppy disks
Still supported in Windows NT, XP, Vista
Its use has been shifted towards embedded devices such as
Digital cameras
MP3 playes
iPod (the default filesystem)
46
FAT Directories
Filenames are limited to 8+3 characters.. Smaller ones are left justified and padded
with space.
Attributes: read-only, archive, hidden, system
Time represented with 2 bytes: correct upto +-2 second
Date: Counts in three fields: day (5 bit), month (4 bits), year (7 bits).
 Contains: Y2108 problem
File size: 2 bytes. Theoretically 4GB limit, but the limit is 2GB due to other reasons.
10 bits reserved for future use.
47
File Allocation Table
MS-DOS keeps track of files through
FAT table hold in memory.
First block number (2 bytes) used as
the index to the FAT table which
has 64K entries.
Block size can be set as multiple of
512 byes.
Three versions of FAT depending on
the number of bits a disk address
contains:
 FAT-12
 FAT-16
 FAT-32 (actually should be called as
FAT-28)
FAT is also used for keeping track of
free blocks.
48
FAT-12
Block size: 512 bytes
(2^12-10) X 512 bytes =~ 2MB
10 disk addresses are used as
special markers.
FAT table size: 4096 entries
with 2 bytes each.
Worked well for floppy disks.
The limit was extended using
larger block sizes: 1KB, 2KB,
4KB providing support for
partitions 16MB.
Limited for hard disks.
49
Block Sizes and FAT Sizes
Disk Size
FAT-12
FAT-16
FAT-32
FAT entry
12 bits
16 bits
28 bits
Max # of
blocks
4086
65526
268435456
~212
~216
~228
Block size
0.5KB to 4KB
2KB to 32KB
4KB to 32KB
FAT size
8KB
128KB
1GB
50
The MS-DOS File System
Maximum partition size for different block sizes. The empty boxes
represent forbidden combinations.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
51
The Classic Unix File System
Each disk partition has 4 Regions
block 0: boot block
block 1: super block. Contains the size of the disk and the boundaries of the other
regions
 i-nodes: list of i-nodes, each is a 64-byte structure
free storage blocks for the contents of files.
52
The Classic Unix File System
There are four types of “files” in Unix File System
Super block. Contains the size of the disk and the boundaries of the other regions
Dentry: Directory entries
i-nodes: list of i-nodes, each is a 64-byte structure
Files:
53
Directory Entry in Unix
A directory is accessed exactly as an ordinary file.
It contains 16 byte entries consisting of a 14-byte name and an inumber (index or ID of an i-node). The root of the file system
hierarchy is at a known i-number (2).
Each directory entry has file name and an i-node number
i-node has all the attributes
Restriction: File name size is bounded (14 chars)
54
Unix i-node - attributes
Each i-node contains owner, protection bits, size, directory/file and 13
disk addresses.
55
i-node
Each i-node contains owner, protection bits, size, directory/file and 13
disk addresses.
The first 10 of these addresses point directly at the first 10 blocks of a
file. If a file is larger than 10 blocks (5,120 bytes), the 11th points at
a block for secondary indexing – single indirect block
Second-level index block contains the addresses of the next 128
blocks of the file (70,656 bytes)
Two levels of indirection:12th entry (double indirect block) points at
up to 128 blocks, each pointing to 128 blocks of the file (8,459,264
bytes)
Three levels of indirection: 13th address (triple indirect block) is for a
three layered indexing of 1,082,201,087 bytes.
56
Unix i-node - data blocks
57
Traversing Unix Directory Structure
Suppose we want to read the file /usr/ast/mbox
Location of a i-node, given i-number, can be computed
i-number of the root directory known, say, 2
Read in the i-node 2 from the disk into memory
Find out the location of the root directory file on disk, and read the directory
block in memory
If directory spans multiple blocks, then read blocks until usr found
Find out the i-number of directory usr, which is 6
Read in the i-node 6 from disk
Find out the location of the directory file usr on disk, and read in the block
containing this directory
Find out the i-number of directory ast (26), and repeat
58
Traversing Unix Directory Structure
The steps in looking up /usr/ast/mbox
59
The Big picture: Accessing a File in UNIX
60
CD-ROM
In 1985 a standard for the storage of computer data by Sony and
Philips, CD-ROM (Compact Disc Read Only Memory)
61
CD-ROM and the ISO 9660 filesystem
The CD has one single track, starts at the center of the
disk and spirals out to the circumference of the disk
This track is divided into sectors of equal size
The base standard defines three levels of compliance
• Level 1 limits file names to 8+3 format. Many special
characters (space, hyphen, equals, and plus) are
forbidden
• Level 2 and 3 allow longer filenames (up to 31) and
deeper directory structures (32 levels instead of 8)
• Level 2 and 3 are not usable on some systems, special
MS-DOS
62
ISO 9660 Extensions
Rock Ridge
Extensions to ISO-9660 file system
Favored in the Unix world
Lifts file name restrictions, but also allows Unix-style permissions and special files to
be stored on the CD
Machines that don't support Rock Ridge can still read the files because it's still an
ISO-9660 file system (they won't see the long forms of the names)
UNIX systems and the Mac support Rock Ridge
DOS and Windows currently don't support it
. Joliet
Favored in the MS Windows world
Allows Unicode characters to be used for all text fields (including file names and the
volume name)
Disk is readable as ISO-9660, but shows the long filenames under MS Windows
HFS (Hierarchical File System)
 Used by the Macintosh in place of the ISO-9660, making the disk unusable on
systems that don't support HFS
63
Virtual File System
Manages kernel level file abstractions in one format for all file
systems.
Receives system call requests from user level (e.g. write, open, stat,
link)
Interacts with a specific file system based on mount point traversal
Receives request from other parts of the kernel, mostly from memory
management.
64
Virtual File Systems
VFS: another layer of
abstraction
Upper interface: for processes
implementing POSIX
interface
Lower interface: for concrete
file systems
VFS translates the POSIX calls
to the calls of the filesystems
under it.
65
File System Mounting
A file system must be mounted before it can be accessed
A unmounted file system is mounted at a mount point
66
VFS- 2
At boot time, the root filesystem is registered with VFS.
When other filesystems are mounted, they must also register with VFS.
When a filesystem registers, it provides the list of addresses of the functions that
the VFS demands, such as reading a block.
After registration, when one opens a file:
open(“/usr/include/unistd.h”, O_RDONLY)
VFS creates a v-node and makes a call to the concrete filesystem to return all the
information needed.
The created v-node also contains pointers to the table of functions for the concrete
filesystem that the file resides.
67
Virtual File Systems (2)
A simplified view of the data structures and code used by the VFS and concrete
file system to do a read.
68