Introduction Processes Inter Process Communication Deadlocks Memory Management

File Systems Protection and Security I/O Systems

To fight a disease after it has occurred is like trying to dig a well
when one is thirsty or forging a weapon once a war has begun.

						Chinese Medicine

1. Storage Systems
   

   Disks

   Disk Interleaving

   Tapes
   
   

2. Disk Space Management

   drive #, surface ( side ), the track and the sector

   all the tracks on one drive that can be accessed without being moved constitute a cylinder
   

   within a track, data are stored in sectors
   in general,

   a sector is 512 bytes
   4 - 32 sectors / track
   20 - 1500 tracks/disk surface
   block ~ one or more sectors Let s = # of sectors / track
   t = # of tracks / cylinder cylinder i, surface j, sector k

   block number b = k + s x ( j + i x t )

   File Control Block ( FCB ) -- storage structure consisting of information about a file

   Typical File Control Block
   file permissions
   file dates ( create, access, write )
   file owner, group, ACL ( access control list )
   file size
   file data blocks

   Allocation Methods -- an allocation method refers to how disk ` blocks are allocated for files:

   Contiguous Allocation
   Linked Allocation ( e.g. FAT )
   Indexed Allocation

   Studies of UNIX environment shows that median file size is about 1K

   if block size too large ( e.g. 32K ) => wasteful
   if too small => a file consists of many blocks
         => data transfer too slow

   

   in general, block size ~ 512, 1K, or 2K

   Contiguous Allocation

   • Reduce seek time for contiguous access
   • Access is easy
   • Supports both sequential and direct access
   • Dynamic allocation problem ( may use first fit, best fit, worst fit .. )
   • External fragmentation -- need compaction : expensive
   • Widely used in CD-ROMs, DVDs where final file sizes are known in advance and won't change

   
   

   Linked Allocation

   • Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk
   • simple -- need only starting address
   • free space management system -- no waste space
   • no external fragmentation
   • easy to create a file ( no allocation problem )
   • only better for sequential access
   • overhead -- pointers require space
   • reliability -- damaged pointers
     

   Indexed Allocation

   Bring all the pointers together into one location: the index block ( one for each file )

   • direct access
   • no external fragmentation
   • easy to create a file ( no allocation problem )
   • support both sequential and direct access
   • overhead: space for index blocks

   
   
   

   Free-space Management

   linked list, grouping, bit map, counting

   • Linked List
     link all free blocks, keep a pointer pointing to the first free list block in a special location on the disk and caching it in memory;
     

   • Grouping
     store the addresses of n free blocks in the first free block; the final block contains the addresses of another n free blocks, and so on

     16-bit block #

     1K block can have 512 16-bit entries

     Thus, it can hold 512 free block #

     Therefore, 128 M disk requires 256 blocks to hold all 128K disk block#

   • Bit Map

     each block is represented by 1 bit

     1 => block free
     0 => block allocated e.g. blocks 2, 3, 4, 5, 8, 9,10, 11, 12, 13, 17, 18, 25, 26, 27 are free, others are allocated 00111100111111000110000001110000

     A disk with n blocks requires n bits
     128 M disk with 1K blocks requires 128K bits or 16K bytes ( i.e. 16 blocks )

   • Counting

     makes use of the clustering properties of file blocks

3. Storage Systems

   File Allocation Table ( FAT ) -- MSDOS, OS/2

   • simple but efficient method
   • a variation used by DOS and OS/2
   • one entry for each disk block, indexed by block number
   • the table is used as a linked-list
     

   UNIX

   an i-node is associated with each file, containing information of the file
   

   each block is 4KB
   assume 4 bytes ( 32 bits ) pointers

   direct blocks

   can hold 12 x 4KB = 48K

   single indirect:

   ( 4KB / 4B ) x 4KB = 1K x 4KB = 4 MB

   double indirect:

   1K x 1K x 4KB = 4GB

   triple indirect:

   1K x 1K x 1K x 4KB = 1 TB

   #ls -i     -- displays inode numbers

   
   Information contained in an inode

4. Directory Structures
   The directory entry provides the information needed to find the disk blocks;
   it maps the the ASCII name of the file onto the information needed to locate the data

   CP/M

   only one directory ( thus only need to search one directory ), which contains fixed-size ( 32 bytes ) entries
   when the OS finds the entry, it also has the disk block numbers,
   if the file uses more disk blocks than fit in one entry ( max four disk block numbers; each 16-bit ), the file is allocated additional entry

   1 8 3 1 2 1 16
   owner id file name file type (extension) extent (multi dir) reserved block count disk block numbers

   
   block count -- tells how many bytes this file entry contains, measured in 128 bytes

   Hierarchical Directory

   

   MS-DOS

   
   32 bytes

   8 3 1 10 2 2 2 4
   filename extension attr- ibutes reserved time of last change date of last change first block # size

   A directory is just a file, so can have many

   contains filename and first block number ( cluster # ), indexed to FAT

   early UNIX

   a UNIX dirctory entry contains one entry for each file in that directory
   very simple
   16 bytes -- 14 bytes for filename, 2 bytes for inode

   2 14

   I-node number file name

   Example

   Suppose the root directory has node number #2.  Here is a small part of a Unix file system tree, showing hypothetical node numbers:

   Node #2 . (dot) 2 .. (dot dot) 2 home 123 bin 555 usr 654		Node #555 . (dot) 555 .. (dot dot) 2 rm 546 ls 984 cp 333 ln 333 mv 333		Node #123 . (dot) 123 .. (dot dot) 2 ian 111 stud0002 755 stud0001 883 stud0003 221
   Note how one directory (#555) has three name-to-number maps for the same node.   All three names (cp, ln, mv) refer to the same node number, in this case a file containing an executable program.  (This program looks at its name and behaves differently depending on which name you use to call it.)
   Node #111 . (dot) 111 .. (dot dot) 123 .profile 334 .login 335 .logout 433		Node #333 Disk blocks for the cp / ln / mv file (link count: 3)		Node #335 Disk blocks for the .login file (link count: 1)