CS604 - Operating Systems - Lecture Handout 44

User Rating:  / 0

Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems


  • File Protection
  • In-Memory Data Structures
  • Space Allocation Techniques
  • Contiguous, Linked, Index


The need to protect files is a direct result of the ability to access files. Systems that do not permit access to the files of other users do not need protection. Thus we could provide complete protection by prohibiting access. Alternatively we could provide free access with no protection. Both approaches are too extreme for general use. What is needed is controlled access. File owner/creator should be able to control

  • What can be done
  • By whom

Several types of operations may be controlled:

  • Read: read from the file
  • Write: write or rewrite to the file
  • Execute: Load the file into memory and execute it
  • Append: Write new information at the end of the file
  • Delete: Delete the file and free its space for possible reuse
  • List: List the name and attributes of the file

UNIX Protection

UNIX recognizes three modes of access: read, write, and execute (r, w, x). The execute permission on a directory specifies permission to search the directory.
The three classes of users are:

  • Owner: user is the owner of the file
  • Group: someone who belongs to the same group as the owner
  • Others: everyone else who has an account on the system

A user’s access to a file can be specified by an octal digit. The first bit of the octal digit specifies the read permission, the second bit specifies the write permission, and the third bit specifies the execute permission. A bit value 1 indicates permission for access and 0 indicates no permission. Here is an example:

UNIX Protection

Each user in a UNIX system belongs to a group of users as assigned by the system administrator when a user is allocated an account on the system. A user can belong to multiple groups, but a typical UNIX user belongs to a single group.
For a particular file or subdirectory, we need to set appropriate access permissions for proper protection.

Default Permissions

The default permissions on a UNIX/Linux system are 777 for executable files and directories and 666 for text files. You can use the umask command to set permission bits on newly created files and directories to 1, except for those bits that are set to 1 in the ‘mask’. You can use the chmod command to set permissions on existing files and directories. We give some examples of the chmod and umask commands below.

Default Permissions

Default Permissions 1

Sample commands

chmod 700 ~ ………….. Set permissions on home directory to 700
chmod 744 ~/file………. Set permissions on ~/file to 744
chmod 755 ~/directory… Set permissions on ~/directory 755
ls –l ~ ………………….. Display permissions and some other attributes for all files and
directories in your home directory
ls –ld ~ ………………… Display permissions and some other attributes for your home directory
ls –l prog1.c …………… Display permissions and some other attributes for prog1.c in your
current directory
ls –ld ~/courses ………... Display permissions and some other attributes for your home directory

The umask command sets default permissions on newly created files and directories as

(default permissions – mask value)

Here are some sample commands

umask ……… Display current mask value (in octal)
umask 022 …. Set mask value to octal 022 (turn off write permission for ‘group’ and ‘others’
touch temp1 .. Create an empty file called temp1
ls –l temp1 …. Display default permissions and some other attributes for the temp1 file

File Control Block

A file control block is a memory data structure that contains most of the attributes of a file. In UNIX, this data structure is called inode (for index node). Here are possible values in this data structure.

File Control Block

In-Memory Data Structures

The following upper-level data structures needed for file system support.

  • An in-memory partition table containing information about each mounted partition
  • An in-memory directory structure that holds the directory information of recently accessed directories
  • The system-wide open file table contains pointer to the FCB (UNIX inode) of each open file as well as read/write pointer
  • The FCB for each open file
  • The per process file descriptor table contains a pointer to the appropriate entry in the system wide open file table as well as other information

Here are the connections between various in-memory data structures. UNIX specific mappings follow this diagram.

In-Memory Data Structures

From File Descriptor to File Contents

The open call passes a file name to the file system. When a file is opened, the directory structure is searched for the given file name and file’s inode. An entry is made in the per process open-file table (aka the file descriptor table), with a pointer to the entry in the system wide open file table. The system wide open file table contains the pointer to the current location in the file and a pointer to file’s inode. The open call returns an index for the appropriate entry in the per-process file system table. All file operations are performed via this index, which is called the file descriptor in UNIX/Linux jargon.

Space Allocation Methods

We now turn to some file system implementation issues, in particular space allocation techniques and free space management methods. Here are the three commonly used methods for file space allocation.

  • Contiguous allocation
  • Linked allocation
  • Indexed allocation

Contiguous Allocation

The contiguous allocation method requires each file to occupy a set of contiguous blocks on the disk. The directory entry for each file contains starting block number and file size (in blocks). Disk addresses define a linear ordering on the disk. With this ordering, assuming only one job is accessing the disk, accessing b+1 block after block b normally
requires no head movement. When head movement is needed it is only one track. Both sequential and direct access can be supported by contiguous allocation. For direct access to block I of a file that starts at block b we can immediately access block b+i.

Best-fit, first-fit, or worst-fit algorithms are the strategies used to select a hole from the set of available holes. Neither first fit, nor best fit is clearly best in terms of both time and storage utilization, but first fit is generally faster.
These algorithms suffer from the problem of external fragmentation. As files are allocated or deleted, the free disk is broken into little pieces. This situation results in external fragmentation of disk (similar to external fragmentation of main memory due to segmentation). Disk defragmenter utility needs to be used for removing external fragmentation.
Determining how much space is needed for a file is another problem. User needs to declare file size, and estimating file size may be difficult. Also file growth is expensive in contiguous allocation. Worst-fit space allocation algorithm can be used to allow growth in a file’s size.
The following diagram shows an example of the contiguous allocation scheme.

Contiguous allocation

Linked Allocation

Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk.
The directory contains a pointer to the first and last blocks of the file. There is no external fragmentation with linked allocation, and any free block on the free-space list can be used to satisfy a request. There is no wastage of space. However, a major disadvantage with linked allocation is that it can be used only for sequential access files. To find the ith block of a file, we must start at the beginning of that file and follow the pointers until we get back to the ith block. Consequently it is inefficient to support a direct access capability for linked allocation files.
Here is an example of linked allocation.

Linked allocation

Index Allocation

Indexed allocation brings all the pointers to the block together into a disk block, known as the index block. Here is the logical view of the relationship between an index block and a file’s data blocks.

Index Allocation

Each file has its own index block, which is an array of disk block addresses. The ith entry in the index block points to the ith block of the file. The directory contains the address of the index block. To read the ith block, we use the pointer in the ith index-block entry to find and read the desired block Here is an example of index allocation.

Index Allocation 1