Transcript 6006639 - Middle East Technical University

CENG334
Introduction to Operating Systems
Filesystems and their interface
Topics:
Erol Sahin
Dept of Computer Eng.
Middle East Technical University
Ankara, TURKEY
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. Questions that quickly
arise:



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
File-position
pointer
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
Example: File copy using File System Calls
13
Example Program Using File System Calls (2)
14
Directory Concept
A collection of nodes containing information
about all files
Directory
Files
F1
F2
F3
F4
Fn
Both the directory structure and the files reside on disk
Backups of these two structures are kept on tapes
15
Operations Performed on Directory
A directory is effectively a symbol table that translates file names
into their directory entries.






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
16
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, …)
17
Single-Level Directory
A single directory for all users
Naming problem:
Who will use the name assignment3.c?
Each student has to use a different name: e123456assignment3.c
Grouping problem
Listing would be very crowdy.
18
Two-Level Directory
Separate directory for each user

Path name

In MS-DOS, C:\userx\test.bat

In VMS, volume:[userx.home]test.bat;1

Can have the same file name for different user

Efficient searching

No grouping capability
19
Tree-Structured Directories
A directory is simply another file that needs to be treated in a
special way.
20
Tree-Structured Directories (Cont)
Efficient searching
directory entry sizes would be manageable
Grouping Capability
Current directory (working directory)

cd /spell/mail/prog

type list
21
Tree-Structured Directories (Cont)
Absolute or relative path name
Creating a new file is done in current directory
Delete a file
rm <file-name>
Creating a new subdirectory is done in current directory
mkdir <dir-name>
Example: if in current directory /mail
mkdir count
mail
prog
copy prt exp count
Deleting “mail”  deleting the entire subtree rooted by “mail”
22
Acyclic-Graph Directories
Have shared subdirectories and files
What would happen if we rm /dict/count?
23
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
 111
6
 110
1
 001
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
24
Disk Quotas
Quotas are kept track of on a per-user basis in a quota table.
25
CENG334
Introduction to Operating Systems
Filesystem implementation
Topics:
•OS Boot sequence
•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
26
Boot sequence
27
OS Boot Sequence Step 1: Boot ROM
I/O Device
(e.g., HDD)
Mother Board
Processor
Are you there?
BIOS Codes
(Disk I/O Subroutines)
I/O Device
(e.g., HDD)
Boot ROM
Are you there?
• POST
Are you there?
• Device polling
I/O Device
(e.g., HDD)
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
Results of
POST
OS Boot Sequence Step 1: Boot ROM
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
Results of
device polling
OS Boot Sequence Step 1: Boot ROM
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
OS Boot Sequence Step 2: Load & Execute MBR
Execute the program
(instructions) in the MBR
Mother Board
Processor
Bootable
Device
Memory
BIOS Codes
(Disk I/O Subroutines)
Boot ROM
Track
Load MBR
MBR (Master Boot Record)
The very first physical sector
of this physical drive
Sector
Drive spindle hole
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
OS Boot Sequence Step 2: Load & Execute MBR
• Scan the partition table
• Find which partition has OS
• Jump to the OS (to OS boot sector)
Program Code Area
MBR
(Boot Strap Loader)
Partition Information
• The type of partition (OS bootable?)
• Where in this drive this partition starts
Partition Information
• The type of partition (OS bootable?)
• Where in this drive this partition starts
Partition Information
• The type of partition (OS bootable?)
• Where in this drive this partition starts
Partition Information
• The type of partition (OS bootable?)
• Where in this drive this partition starts
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
Partition table
OS Boot Sequence Step 2: Load & Execute MBR
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
OS Boot Sequence Step 3: Load & Execute OS Boot Loader
Mother Board
Processor
Bootable
Device
Memory
BIOS Codes
(Disk I/O Subroutines)
Boot ROM
Track
OS Boot Sector
MBR (Master Boot Record)
The very first physical sector, located at
cylinder 0, head 0, sector 1, of this physical drive
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
OS Boot Sequence Step 3: Load & Execute OS Boot Loader
0000
OS Boot Sector
XXXX
“JUMP XXXX” instruction
• File system type
• Size of the root directory
• Number of sectors available
• Other information
Logical disk parameter block
- Cluster size
• Load OS to memory
• Initialize OS
• Start the OS
OS Loader
(IPL: Initial Program Loader)
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
OS Boot Sequence Step 3: Load & Execute OS Boot Loader
• OS has been loaded to the memory
• The loaded OS is being initialized
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
File System Implementation
 Structure of a file system
Physical Drive Capacity
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
Disk (Disk Platter)
Disk structure
Physical Drive Capacity
MBR
Code
Partition
Table
Partition #1
  
Logical Drive
Logical Drive
“BOOT-strap Loader”
Partition #N
• Size of a partition
• The first sector for a partition
• The last sector for a partition
• Type of file system used for this partition
• Jump to the first bootable partition
• Information if a partition is “bootable”
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
Partition structure
• IPL: Initial Program Loader
(“Boot Strap”)
Physical Drive Capacity
MBR
Partition
Table
Partition #1
  
Partition #N
Logical Drive
Boot Super Free Space File Allocation The Root
Block Block Management Information Directory
Other files &
directories
Logical Drive
A.K.A. “Boot Sector”
• Read (load) drive parameters
• Load OS kernel files & execute them
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
System Boot Sequence
 You turn on power
 CPU jumps to the beginning of BIOS ROM
 CPU executes POST and initializes hardware
- Memory access latency, initialize video card, etc.
 CPU executes BIOS routine to load MBR
 CPU jumps to the routine in MBR
 MBR contains a routine (“Boot Strap Loader”) to check the partition table
- Find out which logical drive is the system boot drive
- Load the boot block (“Boot Strap”) of the boot drive
and CPU jumps to it
- The boot block contains a routine to start OS
(= start loading OS system files & drives)
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
File System Implementation
 Structure of a file system
Power-On
Physical Drive Capacity
MBR
Partition
Table
Partition #1
  
Partition #N
Logical Drive
Boot Super Free Space File Allocation The Root
Block Block Management Information Directory
Logical Drive
Slide adapted from: Hiroshi Fujinoki of Southern Illinois University Edwardsville
Other files &
directories
Implementing Files
42
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
43
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
44
Linked List Allocation Using a Table in Memory
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
45
I-nodes (Unix*)
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
46
Implementing Directories
47
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
48
Implementing Directories (2)
Two ways of handling long file names in a directory. (a) In-line. (b)
In a heap.
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
49
Shared Files (1)
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
50
Shared Files (2)
(a) Situation prior to linking. (b) After the link is created. (c) After the
original owner removes the file.
51
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.
52
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.
53
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
56
Disk Space Management Block Size (1)
Percentage of files smaller than a given size (in bytes).
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
57
Disk Space Management Block Size (2)
The solid curve (left-hand scale) gives the data rate of a disk. The dashed curve (righthand scale) gives the disk space efficiency. All files are 4 KB.
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
58