1 minute read


File structure is tree.

Non leaf nodes are directories. A directory contains information on all those files contained in that directory.

A directory entry contains the filename in the folder and inode number.

The inode number references an inode - a file descriptor.

An inode contains:

  • file owner
  • permissions
  • modify and access time
  • size of file
  • type of a file (regular, special)
  • location on disk

An inode file is just like an entry in a lookup table.

Some systems (windows) use file extensions to indicate applications.

Unix can try to execute any file you want.

Exec will ook for “magic number” at head of valid executable binary file.

If number is not present, exec looks for “#!” - “hashbang” followed by name of program to execute file.

Otherwise assumes file is shell script and creates instance of user#s prefered shell to process it.

Filestore allocation

Filestore divided into fixed-size blocks.

Blocks not currently allocated to files are maintained in a free list. The free list is just a list of all those blocks not currently being used.

Several strategies for allocationg blocks:

  • contiguous
  • linked
  • file allocation table (FAT)
  • indexed

Free List

Can be a simpel bit vector


where 1 = in use and 0 = free

Simple and efficient if kept in memory:

  • needs writing to disk every so often
  • can be huge - 80gb disk with 512-byte blocks needs 20MB free for list.

Contiguous allocation

Location information consists simply of start block then the number of blocks we have allocated to that file.

Advantagees: fast both for sequenetial and direct access


  • fragmentations
    • may need regular compaction
  • number of blocks to allocate
  • file growth

Linked allocation

Using link lists


  • easy to grow / shrink files
  • no fragmentation problems
  • blocks widely dispersed
  • sequential access less effcient
  • direct access even worse
    • requires n reads to get block n
  • danger of pointer corrupt

Can improve things by allocating blocks in clusters. But this worsens internal fragmentation as you may get some unused space in the cluster.


i said before that going back to the free list that the free list ca be a simple bit vector telling which are in used and which arent

suppose we have a portion of the file store expressed in hexadecimal as: 735A In that portion of the file store, how many stores are free if that is our free list information?

We convert this to binary so 7 is 0111 3 is 0011 5 is 0101 A is 1010

So 7 free blocks.