Transcript Files - Free

CE01000-3 Operating
Systems
Lecture 17
File systems – interface
and implementation
Overview of lecture

In this lecture we will look at:





File and directory concept
Directory Structure
Protection
Allocation Methods
Free-Space Management
Files - User view

As seen by User a File is a named collection of
related information held on non-volatile
backing storage with a contiguous logical
address space. (i.e. it appears to be in one
continuous block)
Files -Operating Systems
view


BUT for O/S file is identified by a reference to its
location on the hardware store and data in file
held in a number of small blocks
these blocks may be held non-contiguously in
hardware store (i.e. sequences of other data
blocks that belong to other files or that are empty
may exist between some or all of the data blocks
of the file)
Directories


a directory is a link between name of file that the user uses
and the file information and data block location information
and is normally maintained in a data structure.
this is simply a table of records where each record has the
name of the file, information about the location of the file,
and various file property information that is useful,


e.g. size, time/date of last modification/access, protection
information (who allowed to use file and how - read only, read/write,
etc.)
directories contain entries for files, but may also contain
entries for other directories (called sub-directories) - name
of directory, location of data block that holds directory
information.
Directories (Cont.)



using directories allows users to give
meaningful names to files and to group files
together
in windows systems users normally use the
name folder rather than directory - a folder is
a directory that has an icon associated with it
directories allow users and application
programs to list the information
OS Directory support

the operating system provides users and
application programs (via API calls) with a
number of operations that can be performed
on directories e.g.



list directory contents,
change some file properties like its name and
protection provided, search for given file,
delete a file (removes file entry in directory and
free up space used by file on disk), etc.
OS File operations


create file - allocate space for file, then create entry in directory for file
write to file - finds location of file from directory entry, then outputs to
file at location specified by a current position pointer - points to location in
file – location is relative to start of file i.e. logical location not physical) then updates pointer

read from file - finds location of file from directory entry, then inputs
from file at location specified by current position pointer - then updates
pointer


file seek - change value of current position pointer to new value
delete file - find directory entry - return space back to O/S, and then
delete entry in directory

also getting and setting various file attributes
Opening/closing files



instead of repeatedly searching directory for file entry for
every operation - O/S usually supplies a method for opening
a file
when file opened information about file including location
information, are placed in an open file table which is
accessed by some index value
alternatively you can have open file tables for each process
in which case open file table holds information relevant to
process’ use of file e.g. current position pointer and OS has
a separate open file table to hold process independent info
e.g. file location on disk
Opening/closing files
(Cont.)

open(Fi) – search the directory structure on disk for
entry Fi, and move the content of entry to open file table returning a pointer that points to entry in open file table

close (Fi) – move the content of entry Fi in open file
table to directory structure on disk.
Directory organisation

need to organise directories to obtain


Efficiency – can locate files 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 C programs, all games, …)
Directory structure
Directory structure (Cont.)




General modern directory structure is multi-level in a
tree like structure but one which does allow links
between different branches of tree hierarchy
can logically group together related files in
subdirectories
can allow duplicate file names by placing files in
different directories - use full path names to identify a
file uniquely
allow search path to be defined to specify directories to
be searched for file references not found in users
directory
Directory structure (Cont.)



allow concept of current directory (working directory) so
that complete pathname does not have to be used if file
in current directory
allow relative path names
can share subdirectories and files by having links to
file/directory using different file names to refer to same
file/directory - prevent deletion of file with multiple links
by keeping a count of number of links - only delete when
count = 0
File Allocation Schemes




File allocation allocates disk blocks to file, but also
defines translation of logical file address to physical
file address
logical file blocks are numbered from 0 so logical file
address specified by:
logical block number + offset within block
a number of file allocation schemes 1. contiguous
2. linked
3. indexed
Contiguous Allocation




Each file occupies a set of contiguous
blocks on the disk.
Simple to allocate – only starting location
(physical block #) and length (number of
blocks) are required.
Random access is possible
Wasteful of space - external
fragmentation of disk space - similar
problem to contiguous memory
allocation.
Contiguous Allocation
(Cont.)


Files cannot grow - without making new
copy in new location
mapping from logical address to
physical:


block to be accessed = starting address of
first block + (logical address / size of block)
 / is integer division i.e. no fractional part
offset into block = logical address % size of
block
 % is remainder operation
Linked Allocation

Each file is a linked list of disk blocks; blocks
may be scattered anywhere on the disk.
block
=
pointer
File Data
Linked Allocation (Cont.)
Linked Allocation (Cont.)



Allocate blocks as needed
link them together
in example in previous slide, file starts at block 9 and
simply follows links for file data

Simple to allocate – need only starting address of file
i.e. first physical block id.

no waste of space - all free space is available for
allocation to files i.e. no external fragmentation
Linked Allocation (Cont.)
 But
no random access - have to follow links
 Mapping

logical address / size of block


from logical address to physical:
specifies the block in the linked chain of blocks
representing file
logical address % size of block

specifies offset into block
Indexed Allocation


Brings all pointers to disk blocks together
into the index block.
Logical view.
index table
Example of Indexed
Allocation
Indexed Allocation (Cont.)

Need index table

Random access is OK

Dynamic access without external
fragmentation and files can grow, but have
overhead of index block.
Indexed Allocation –
Mapping


Mapping from logical to physical address
where there is only 1 block to hold index
table:

logical address / size of block = index into index
table giving address of physical block

logical address % size of block = offset into block
block size places upper limit on size of a file
= number of indices in block * size of a block
in bytes.
Indexed Allocation – Mapping
using multi-level index (Cont.)

outer-index
index table
file
Indexed Allocation – Mapping
using multi-level index (Cont.)
 multi-level
index
 lowest level gives address of blocks on disk
 higher level gives indices into lower level index
blocks
 logical address / number of indices in a block =
index of next lower index block
 this is repeated until you get index into lowest index
block where address of block is found
 logical address % size of block = offset into block
Free-Space Management

Bit vector scheme (n blocks)
0
1
2
n-1
…
bit[j] = 1 => block[j] free
= 0 => block[j] occupied

Block number of first free block =
(number of bits per word) *
(number of 0-value words) +
offset of first 1 bit
Free-Space Management (Cont.)
 Bit
map requires extra space. Example:
block size = 212 bytes
disk size = 230 bytes (1 gigabyte)
n = 230/212 = 218 bits (or 32K bytes)
 Easy
to get contiguous files
 Linked
list scheme of free space management (free
list) - just put free blocks on a linked list

Cannot get contiguous space easily

No waste of space
References

Operating System Concepts. Chapter 11.