Rashtreeya Sikshana Samithi Trust

RV Institute of Technology and Management ®

(Affiliated to VTU, Belagavi)

JP Nagar, Bengaluru – 560076

Department of Computer Science and Engineering

Course Name: Operating

Systems Course Code:
BCS303
III Semester
2022 Scheme
Usm

CPU

III Semester OPERATING SYSTEMS (BCS303)

2
 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

Module V
5.1 File System
The file system consists of two distinct parts: a collection of files, each storing related data, and a
directory structure, which organizes and provides information about all the files in the system.

5.1.1 File Concept

A file is a collection of related information that is recorded on secondary storage. A file is
a sequence of bits, bytes, lines, or records, the meaning of which is defined by the file's creator
and user.
[Link] File Attributes
A file is named, for the convenience of its human users, and is referred to by its name. A file's
attributes vary from one operating system to another. The attributes of a file are p-
o Name - The symbolic file name is the only information kept in human readable form.
Some special significance is given to names, and particularly extensions (.exe, .txt, etc.).
o Identifier – It is a unique number, that identifies the file within the file system.
o Type – Type of the file like text, executable, another binary, etc.
o Location -. location of the file on that device.
o Size - The current size of the file (in bytes, words, or blocks)
o Protection - Access-control information (reading, writing, executing).
o Time, date, and user identification –These data can be useful for protection,
security, and usage monitoring.

File Operations
The operating system provides system calls to create, write, read, reposition, delete,
and truncate files.
[Link].1 Creating a file - Two steps are necessary to create a file
 Find space in the file system for the file.
 Make an entry for the new file in the directory.
Writing a file - To write a file, the system call consists of both the name of the file and the information
to be written to the file. Given the name of the file, the system searches the directory to find the file's
location. The system must keep a write pointer to the location in the file where the next write is to take
place. The write pointer must be updated whenever a write occurs.
Reading a file - To read from a file, the system call that specifies the name of the file and where the
next block of the file should be put. The directory is searched for the file, and the system needs to keep
a read pointer to the location in the file where the next read is to take place. Once the read has taken
place, the read pointer is updated.
Repositioning within a file - The directory is searched for the file, and the file pointer is repositioned
to a given value. This file operation is also known as a file seek.
Deleting a file – To delete a file, search the directory for the file. Release all file space, so that it can be
reused by other files, and erase the directory entry.

Truncating a file - The user may want to erase the contents of a file but keep its attributes. Rather than
forcing the user to delete the file and then recreate it, this function allows all attributes to remain
unchanged –except for file length. The file size is reset to zero.

III Semester OPERATING SYSTEMS (BCS303) 3

 RV Institute of Technology & Management®

 Information about currently open files is stored in an open file table. It contains
information‘s like:
o File pointer - records the current position in the file, for the next read or write
access.
o File-open count - How many times has the current file been opened by different
processes, at the same time and not yet closed? When this counter reaches zero
the file can be removed from the table.
o Disk location of the file – The information needed to locate the file on disk is
kept in memory so that the system does not have to read it from disk for each
operation.
o Access rights – The file access permissions are stored on the per-process table so
that the operating system can allow or deny subsequent I/O requests.
 Some systems provide support for file locking.
o A shared lock is for reading only.
o An exclusive lock is for writing as well as reading.
o An advisory lock, it is up to the software developers to ensure that locks are acquired
or released.
o A mandatory lock, prevents any other process from accessing the locked file. (A
truly locked door.)

Fig. 5.22 Common file types.

5.1.2 File Types

 File name consists of two parts: name and extension

 The user and the operating system can identify the type of a file using the name.
 Most operating systems allow users to specify a file name as a sequence of
characters followed by a period and terminated by an extension. Example:
[Link], threads‘ etc. as shown in Fig. 5.22.
 The system uses the extension to indicate the type of the file and the type of
operations that can be done on that file.

III Semester OPERATING SYSTEMS(BCS303) 4

 RV Institute of Technology & Management®

 For instance, only a file with a ―. corn", ".exe", or ".bat‖, can be executed.

c) File Structure
 The study of different ways of storing files in secondary memory such that they can be
easily accessed.
 File types can be used to indicate the internal structure of the file. Certain files must be in
a particular structure that is understood by the operating system.
 For example, the operating system requires that an executable file have a specific
structure so that it can determine where in memory to load the file and the location of the
first instruction.
 UNIX treats all files as sequences of bytes, with no further consideration of the internal
structure.
 Macintosh files have two forks - a resource fork, and a data fork. The resource fork
contains information relating to the UI, such as icons and button images. The data fork
contains the traditional file contents-program code or data.

d) Internal File Structure

 Disk systems typically have a well-defined block size determined by the size of
a sector. A group of sectors form a group
 All disk I/0 is performed in units of one block, and all blocks are the same size.
 Logical records may even vary in length. Padding a number of logical records
into physical blocks is a common solution to this problem.
 The packing can be done either by the user's application program or by the
operating system. In either case, the file may be considered a sequence of
blocks.
 All the basic I/O functions operate in terms of blocks.
 Disk space is always allocated in terms of blocks. Some portion of last
block (while storing a file) is always wasted. This is called internal
fragmentation.

5.2 Access Methods

The file information is accessed and read into computer memory. The information in the file
can be accessed in several ways.

a) Sequential Access
 Here information in the file is processed in order, one record after the other.
 This mode of access is a common method; for example, editors and compilers
usually access files in this fashion.
 A sequential access file emulates magnetic tape operation, and generally supports a
few operations:
o read next - read a record and advance the file pointer to the next position.
o write next - write a record to the end of file and advance the file pointer to
the next position as shown in Fig. 5.23.
o skip n records - May or may not be supported. ‗n‘ may be limited to
positive numbers, or may be limited to +/- 1.
III Semester OPERATING SYSTEMS(BCS303) 5
 RV Institute of Technology & Management®

Fig. 5.23 Sequential-access file.

b) Direct Access
A file is made up of fixed-length logical records that allow programs to read and write
records randomly. The records can be rapidly accessed in any order.

Direct access is of great use for immediate access to large amount of information.
Eg: Database file. When a query occurs, the query is computed and only the selected rows are
access directly to provide the desired information.
Operations supported include:
 read n - read record number n. (position the cursor to n and then read the record)
 write n - write record number n. (position the cursor to n and then write the record)
 jump to record n – move to nth record (n- could be 0 or the end of file)
 If the record length is L, there is a request for record ‗N‘. Then the direct access
to the starting byte of record ‗N‘ is at L*(N-1)

Eg: if 3rd record is required and length of each record(L) is 50, then the starting
position of 3rd record is L*(N-1)
Address = 50*(3-1) = 100.

c) Other Access Methods (Indexed method)

 These methods generally involve the construction of an index for the file called index file.
 The index file is like an index page of a book, which contains key and address. To find a
record in the file, we first search the index and then use the pointer to access the record
directly and find the desired record.
 An indexed access scheme can be easily built on top of a direct access system.
For very large files, the index file itself is very large. The solution index for to this is to create an
index file. i.e. multi-level indexing as shown in Fig. 5.25.

Fig. 5.24 Example of index and relative files.

III Semester OPERATING SYSTEMS(BCS303) 6

 RV Institute of Technology & Management®

5.3Directory Structure
Directory is a structure which contains filenames and information about the files like
location, size, type etc. The files are put in different directories. Partitioning is useful for limiting
the sizes of individual file systems, putting multiple file-system types on the same device, or
leaving part of the device available for other uses.
Partitions are also known as slices or minidisks as shown in Fig. 5.25. A file system can
be created on each of these parts of the disk. Any entity containing a file system is generally
known as a volume.

Fig. 5.25 A typical file-system organization.

5.3.1 Directory Overview

The directory can be viewed as a symbol table that translates file names into their
directory entries.
Directory operations to be supported include:
[Link] Search for a file - search a directory structure
to find the entry for a particular file.
[Link] Create a file – create new files and add to
the directory
[Link] Delete a file - When a file is no longer needed, erase
it from the directory
[Link] List a directory - list the files in a directory
and the contents of the directory entry.
[Link] Rename a file – Change the name of the file.
Renaming a file may also allow its position
within the directory structure to be changed.
[Link] Traverse the file system - Access every directory and
every file within a directory structure.

5.3.2 Directory Structures

a) Single-Level Directory
 It is the simplest directory structure.
 All files are contained in the same directory, which is easy to support and understand.

The limitations of this structure are that -

 All files are in the same directory must have unique names.
 Even a single user on a single-level directory may find it difficult to remember the names

III Semester OPERATING SYSTEMS(BCS303) 7

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

of all the files as the number of files increases as shown in Fig. 5.26.

Fig. 5.26 Single-level directory

b) Two-Level Directory
 Each user gets their own directory space - user file directory (UFD)
 File names only need to be unique within a given user's directory.
 A master file directory (MFD) is used to keep track of each user‘s directory,
and must be maintained when users are added to or removed from the system.
 When a user refers to a particular file, only his own UFD is searched.
 All the files within each UFD are unique.
 To create a file for a user, the operating system searches only that user's UFD to
ascertain whether another file of that name exists.
 To delete a file, the operating system confines its search to the local UFD; thus, it
cannot accidentally delete another user's file that has the same name. The user
directories themselves must be created and deleted as necessary.
 This structure isolates one user from another. Isolation is an advantage when the
users are completely independent but is a disadvantage when the users want to
cooperate on some task and to access one another's files as shown in Fig. 5.27.

Fig. 5.27 Two-level directory structure

c) Tree-Structured Directories
 A tree structure is the most common directory structure.
 The tree has a root directory, and every file in the system has a unique path name.
 A directory (or subdirectory) contains a set of files or subdirectories.
 One bit in each directory entry defines the entry as a file (0) or as a subdirectory (1).
Special system calls are used to create and delete directories.
 Path names can be of two types: absolute and relative. An absolute path begins at the
root and follows a down to the specified file, giving the directory names on the path.
A relative path defines a path from the current directory (Fig. 5.28).
 For example, in the tree-structured file system of Fig. below if the current directory is
root/spell/mail, then the relative path name is prt/first and the files absolute path name
root/spell/mail/prt/jirst.

IV SEMESTER OPERATING SYSTEM (18CS43) 21

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 5.28 Tree-structured directory structure.

 Directories are stored the same as any other file in the system, except there is a bit
that identifies them as directories, and they have some special structure that the OS
understands.

 One question for consideration is whether or not to allow the removal of directories
that are not empty - Windows requires that directories be emptied first, and UNIX
provides an option for deleting entire sub-trees.

d) Acyclic-Graph Directories
 When the same files need to be accessed in more than one place in the directory
structure (e.g. because they are being shared by more than one user), it can be useful
to provide an acyclic-graph structure. (Note the directed arcs from parent to child. )

o UNIX provides two types of links (pointer to another file) for implementing the
acyclic-graph structure.

o A hard link (usually just called a link) involves multiple directory entries that
both refer to the same file. Hard links are only valid for ordinary files in the same
filesystem.

o A symbolic link, that involves a special file, containing information about where
to find the linked file. Symbolic links may be used to link directories and/or files
in other filesystems, as well as ordinary files in the current filesystem as shown in
Fig. 5.29.

 Windows only supports symbolic links, termed shortcuts.

 Hard links require a reference count, or link count for each file, keeping track of
how many directory entries are currently referring to this file. Whenever one of the
references is removed the link count is reduced, and when it reaches zero, the disk
space can be reclaimed.

IV SEMESTER OPERATING SYSTEM (18CS43) 22

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Fig. 5.29 Acyclic-graph directory structure.

 For symbolic links there is some question as to what to do with the symbolic
links when the original file is moved or deleted:

o One option is to find all the symbolic links and adjust them also.

o Another is to leave the symbolic links dangling, and discover that they are no
longer valid the next time they are used.

o What if the original file is removed, and replaced with another file having the
same name before the symbolic link is next used?

Another approach to deletion is to preserve the file until all references to it are deleted. To
implement this approach, we must have some mechanism for determining that the last
reference to the file has been deleted.

When a link or a copy of the directory entry is established, a new entry is added to the file-
reference list. When a link or directory entry is deleted, we remove its entry on the list. The
file is deleted when its file-reference list is empty.

e) General Graph Directory

 If cycles are allowed in the graphs, then several problems can arise:

o Search algorithms can go into infinite loops. One solution is to not follow links in
search algorithms. (Or not to follow symbolic links, and to only allow symbolic links
to refer to directories)

o Sub-trees can become disconnected from the rest of the tree and still not havetheir
reference counts reduced to zero. Periodic garbage collection is required to detect and
resolve this problem. (chkdsk in DOS and fsck in UNIX search for these problems,
among others, even though cycles are not supposed to be allowed in either system.
Disconnected disk blocks that are not marked as free are added back to the file
systems

IV SEMESTER OPERATING SYSTEM (18CS43) 23

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

with made-up file names, and can usually be safely deleted.)

o when we add links to an existing tree-structured directory, the tree structure is

destroyed, resulting in a simple graph structure (Fig. 5.30).

Fig. 5.30 General graph directory.

5.4 File-System Mounting

The basic idea behind mounting file systems is to combine multiple file systems into one
large tree structure.
The mount command is given a filesystem to mount and a mount point (directory) on which to
attach it.
Once a file system is mounted onto a mount point, any further references to that
directory actually refer to the root of the mounted file system.

Any files (or sub-directories) that had been stored in the mount point directory prior to
mounting the new filesystem are now hidden by the mounted filesystem, and are no longer
available. For this reason, some systems only allow mounting onto empty directories (Fig.
5.31 a).

Filesystems can only be mounted by root, unless root has previously conFig.d certain
filesystems to be mountable onto certain pre-determined mount points. (E.g. root may allow
users to mount floppy filesystems to /mnt or something like it) Anyone can run the mount
command to see what filesystems are currently mounted (Fig. 5.31 b).

Filesystems may be mounted read-only, or have other restrictions imposed.

The traditional Windows OS runs an extended two-tier directory structure, where the first tier
of the structure separates volumes by drive letters, and a tree structure is implemented below
that level.

IV SEMESTER OPERATING SYSTEM (18CS43) 24

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

Macintosh runs a similar system, where each new volume that is found is automatically mounted
and added to the desktop when it is found. More recent Windows systems allow filesystems to be
mounted to any directory in the filesystem, much like UNIX.

Fig. 5.32 shows the effects of mounting the volume residing on /device/dsk over /users. If the volume is
unmounted, the file system is restored to the situation depicted in Fig. 5.31.

Fig. 5.31 File system, (a) Existing system, (b) Unmounted volume. Fig. 5.32 Mount point

5.5 File Sharing

5.5.1 Multiple Users
On a multi-user system, more information needs to be stored for each
file: The owner (user) who owns the file, and who can control its access.
The group of other user IDs that may have some special access to the file.
What access rights are afforded to the owner (User), the Group, and to the rest of the
world (the universe, a.k.a. Others.)
Some systems have more complicated access control, allowing or denying
specific accesses to specifically named users or groups.

5.5.2 Remote File Systems

The advent of the Internet introduces issues for accessing files stored on remote
computers The original method was ftp, allowing individual files to be transported across
systems as needed. Ftp can be either account and password controlled, or anonymous,
not requiring any user name or password.
Various forms of distributed file systems allow remote file systems to be mounted onto
a local directory structure, and accessed using normal file access commands. (The actual
files are still transported across the network as needed, possibly using ftp as the
underlying transport mechanism.)
The WWW has made it easy once again to access files on remote systems without
mounting their filesystems, generally using (anonymous) ftp as the underlying file
transport

IV SEMESTER OPERATING SYSTEM (18CS43) 25

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module IV

mechanism.

a) The Client-Server Model

 When one computer system remotely mounts a filesystem that is physically located
on another system, the system which physically owns the files acts as a server, and
the system which mounts them is the client.
 User IDs and group IDs must be consistent across both systems for the system to
work properly. (I.e. this is most applicable across multiple computers managed by
the same organization, shared by a common group of users. )
 The same computer can be both a client and a server. (E.g. cross-linked file systems.
)
 There are a number of security concerns involved in this model:
o Servers commonly restrict mount permission to certain trusted systems only.
Spoofing (a computer pretending to be a different computer) is a potential
security risk.
o Servers may restrict remote access to read-only.
o Servers restrict which filesystems may be remotely mounted. Generally, the
information within those subsystems is limited, relatively public, and
protected by frequent backups.

o The NFS (Network File System) is a classic example of such a system.

b) Distributed Information Systems

 The Domain Name System, DNS, provides for a unique naming system across
all of the Internet.
 Domain names are maintained by the Network Information System, NIS, which
unfortunately has several security issues. NIS+ is a more secure version, but has
not yet gained the same widespread acceptance as NIS.
 Microsoft's Common Internet File System, CIFS, establishes a network login
for each user on a networked system with shared file access. Older
Windowssystems used domains, and newer systems (XP, 2000), use active
directories. User names must match across the network for this system to be
valid.
 A newer approach is the Lightweight Directory-Access Protocol, LDAP, which
provides a secure single sign-on for all users to access all resources on a
network. This is a secure system which is gaining in popularity, and which has
the maintenance advantage of combining authorization information in one central
location.

c) Failure Modes

 When a local disk file is unavailable, the result is generally known immediately,
and is generally non-recoverable. The only reasonable response is for the response
to fail.
 However, when a remote file is unavailable, there are many possible reasons, and
whether or not it is unrecoverable is not readily apparent. Hence most remote
access
IV SEMESTER OPERATING SYSTEM (18CS43) 26
 systems allow for blocking or delayed response, in the hopes that the remote
system (or the network) will come back up eventually.

5.5.3 Consistency Semantics

Consistency Semantics deals with the consistency between the views of shared files on
a networked system. When one user changes the file, when do other users see the
changes? The series of accesses between the open () and close () operations of a file is
called the file session.

Examples of consistency semantics -

a) UNIX Semantics

 The UNIX file system uses the following semantics:

o Writes to an open file are immediately visible to any other user who has the
file open.

o One implementation uses a shared location pointer, which is adjusted for

all sharing users.
 There is a single copy of the file, which may delay some accesses.

b) Session Semantics

 The Andrew File System, AFS uses the following semantics:

o Writes to an open file are not immediately visible to other users.
o When a file is closed, any changes made become available only to users who open
the file at a later time.
 According to these semantics, a file can be associated with multiple (possibly different)
views. Almost no constraints are imposed on scheduling accesses. No user is delayed
in reading or writing their personal copy of the file.
 AFS file systems may be accessible by systems around the world. Access control is
maintained through (somewhat) complicated access control lists, which may grant
access to the entire world (literally) or to specifically named users accessing the files
from specifically named remote environments.

c) Immutable-Shared-Files Semantics
 Under this system, when a file is declared as shared by its creator, then the name
 cannot be re-used by any other process and it cannot be modified.

IV SEMESTER OPERATING SYSTEM (18CS43) 1

 Secondary - Storage Structure

5.6 Overview
Magnetic disks provide a bulk of secondary storage. Disks come in various sizes and speed. Here
the information is stored magnetically. Each disk platter has a flat circular shape like CD. The
two surfaces of a platter are covered with a magnetic material. The surface of a platter is logically
divided into circular tracks, which are subdivided into sectors. Sector is the basic unit ofstorage.
The set of tracks that are at one arm position makes up a cylinder (Fig. 5.1).

The number of cylinders in the disk drive equals the number of tracks in each platter. There
maybe thousands of concentric cylinders in a disk drive, and each track may contain
hundreds

Fig. 5.1 Moving head disk mechanism

of sectors. The storage capacity of disk drives is measured in gigabytes. The head moves from
the inner track of the disk to the outer track. When the disk drive is operating the disks is rotating
at a constant speed. To read or write the head must be positioned at the desired track and at the
beginning of the desired sector on that track.

5.6.1 Seek Time: -Seek time is the time required to move the disk arm
to the required track.
5.6.2 Rotational Latency (Rotational Delay):-Rotational latency is the
time taken for the disk to rotate so that the required sector comes
under the r/w head.
5.6.3 Positioning time or random-access time is the summation of seek
time and rotationaldelay.
5.6.4 Disk Bandwidth: -Disk bandwidth is the total number of
bytes transferred divided by total
5.6.5 time between the first request for service and the completion of
last transfer.
5.6.6 Transfer rate is the rate at which data flow between the drive and
the computer.

IV SEMESTER OPERATING SYSTEM (18CS43) 2

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

As the disk head flies on an extremely thin cushion of air, the head will contact the disk surface.
Although the disk platters are coated with a thin protective layer, sometimes the head will
damage the magnetic surface. This accident is called a head crash.

5.6.1. Magnetic Tapes

Magnetic tape is a secondary-storage medium. It is a permanent memory and can hold large
quantities of data. The time taken to access data (access time) is large compared with that of
magnetic disk, because here data is accessed sequentially. When the nth data has to be read, the
tape starts moving from first and reaches the nth position and then data is read from nth position.
It is not possible to directly move to the nth position. So tapes are used mainly for backup, for
storage of infrequently used information.

5.7 Disk Structure

Each disk platter is divided into number of tracks and each track is divided into number of
sectors. Sectors is the basic unit for read or write operation in the disk.

Modern disk drives are addressed as a large one-dimensional array. The one-dimensional array of
logical blocks is mapped onto the sectors of the disk sequentially. Sector 0 is the first sector of
the first track on the outermost cylinder. The mapping proceeds in order through that track, then
through the rest of the tracks in that cylinder, and then through the rest of the cylinders from
outermost to innermost.

The disk structure (architecture) can be of two types –

5.7.1 Constant Linear Velocity (CLV)
5.7.2 Constant Angular Velocity (CAV)

i) CLV - The density of bits per track is uniform. The farther a track is from the center of
the disk, the greater its length, so the more sectors it can hold. As we move from outer
zones to inner zones, the number of sectors per track decreases. This architecture is
used in CD-ROM and DVD-ROM.
ii) CAV – There is same number of sectors in each track. The sectors are densely packed in
the inner tracks. The density of bits decreases from inner tracks to outer tracks to keep
the data rate constant.

5.8 Disk Attachment

Computers can access data in two ways.

5.8.1 via I/O ports (or host-attached storage)
5.8.2 via a remote host in a distributed file system (or network-attached storage)

i) Host-Attached Storage

III SEMESTER OPERATING SYSTEM (BCS303) 2

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

Host-attached storage is storage accessed through local I/O ports. Example: the typical
desktop PC uses an I/O bus architecture called IDE or ATA. This architecture supports a
maximum of two drives per I/O bus. The other cabling systems are – SATA (Serially Attached
Technology Attachment), SCSI (Small Computer System Interface) and fiber channel (FC).

SCSI is a bus architecture. Its physical medium is usually a ribbon cable. FC is a high-
speed serial architecture that can operate over optical fiber or over a four-conductor copper cable.
An improved version of this architecture is the basis of storage-area networks (SANs).

i) Network-Attached Storage

A network-attached storage (NAS) device is a special-purpose storage system that is

accessed remotely over a network as shown in the Fig. 5.2. Clients access network-attached
storage via a remote-procedure-call interface. The remote procedure calls (RPCs) are carried via
TCP or UDP over an IP network—-usually the same local-area network (LAN) carries all data
traffic to the clients.

Fig 5.2 Network attached Storage

Network-attached storage provides a convenient way for all the computers on a LAN to share a
pool of storage with the same ease of naming and access enjoyed with local host-attached
storage. However, it tends to be less efficient and have lower performance than some direct-
attached Storage options.

ii) Storage Area Network (SAN)

A storage-area network (SAN) is a private network connecting servers and storage units.
The power of a SAN lies in its flexibility. Multiple hosts and multiple storage arrays can attach to
the same SAN, and storage can be dynamically allocated to hosts. A SAN switch allows or
prohibits access between the hosts and the storage (Fig. 5.3). Fiber Chanel is the most common
SAN interconnect.

III SEMESTER OPERATING SYSTEM (BCS303) 3

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

Fig 5.3 Storage Area Network

5.9 Disk Scheduling

Different types of disk scheduling algorithms are as follows:

 FCFS (First Come First Serve)
 SSTF (Shortest Seek Time First)
 SCAN (Elevator)
 C-SCAN
 LOOK
 C-LOOK

5.9.1 FCFS scheduling algorithm: This is the simplest form of disk

scheduling algorithm. This service the request in the order they are
received. This algorithm is fair but do not provide fastest service. It
takes no special care to minimize the overall seek time. Eg: -consider
a disk queue with request for i/o to blocks on cylinders (Fig. 5.4). 98,
183, 37, 122, 14, 124, 65, 67.

Fig. 5.4 FCFS disk scheduling.

If the disk head is initially at 53, it will first move from 53 to 98 then to 183 and then to 37,

III SEMESTER OPERATING SYSTEM (BCS303) 4

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

122, 14, 124, 65, 67 for a total head movement of 640 cylinders. The wild swing from 122
to 14 and then back to 124 illustrates the problem with this schedule.

5.9.2 SSTF (Shortest Seek Time First) algorithm: This selects the request with
minimum seek time from the current head position. SSTF chooses the pending request
closest to the current head position. Eg:- consider a disk queue with request for i/o to
blocks on cylinders ( Fig. 5.5). 98, 183, 37, 122, 14, 124, 65, 67.

If the disk head is initially at 53, the closest is at cylinder 65, then 67, then 37 is closer
then 98 to 67. So, it services 37, continuing we service 14, 98, 122, 124 and finally 183.
The total head movement is only 236 cylinders. SSTF is a substantial improvement over
FCFS, it is not optimal.

Fig 5.5 SSTF disk scheduling.

5.9.3 SCAN algorithm: In this the disk arm starts moving towards
one end, servicing the request as it reaches each cylinder until it gets
to the other end of the disk. At the other end, the direction of the head
movement is reversed and servicing continues. The initial direction is
chosen depending upon the direction of the head. Eg: -:-consider a
disk queue with request for i/o to blocks on cylinders. 98, 183, 37,
122, 14, 124, 65, 67

If the disk head is initially at 53 and if the head is moving towards the outer track, it
services 65, 67, 98, 122, 124 and183. At cylinder 199 the arm will reverse and will move
towardsthe other end of the disk servicing 37 and then 15. The SCAN is also called as
elevator algorithm. (Fig 5.6).

If the disk head is initially at 53 and if the head is moving towards 0th track, it services 37
and then 15. At cylinder 0 the arm will reverse and will move towards the other end of the
disk servicing 65, 67, 98, 122, 124 and 183.

III SEMESTER OPERATING SYSTEM (BCS303) 5

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

Fig. 5.6 SCAN disk scheduling.

5.9.4 C-SCAN (Circular Scan) algorithm:

C-SCAN is a variant of SCAN designed to provide a more uniform wait time. Like SCAN, C-
SCAN moves the head from end of the disk to the other servicing the request along the way.
When the head reaches the other end, it immediately returns to the beginning of the disk,
without servicing any request on the return (Fig. 5.7). Eg: - consider a disk queue with request
for i/o to blocks on cylinders. 98, 183, 37, 122, 14, 124,65,67

Fig. 5.7 C-SCAN disk scheduling.

If the disk head is initially at 53 and if the head is moving towards the outer track, it services 65,
67, 98, 122, 124 and 183. At cylinder 199 the arm will reverse and will move immediately
towards

III SEMESTER OPERATING SYSTEM (BCS303) 6

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

the other end of the disk, then changes the direction of head and serves 14 and then 37.

Note: If the disk head is initially at 53 and if the head is moving towards track 0, it services 37
and 14 first. At cylinder 0 the arm will reverse and will move immediately towards the other end
of the disk servicing 65, 67, 98, 122, 124 and183.

5.9.5 Look Scheduling algorithm: Look and C-Look scheduling are different version of
SCAN and C-SCAN respectively. Here the arm goes only as far as the final request in each
direction. Thenit reverses, without going all the way to the end of the disk. The Look and C-Look
scheduling look for a request before continuing to move in a given direction (Fig. 5.8).

Eg: -:-consider a disk queue with request for i/o to blocks on cylinders. 98, 183, 37, 122,
14, 124, 65, 67

If the disk head is initially at 53 and if the head is moving towards the outer track, it services 65,
67, 98, 122, 124 and183. At the final request 183, the arm will reverse and will move towards the
first request 14 and then serves 37.

ii) C-Look Scheduling algorithm:

Fig 5.8 C-LOOK disk scheduling.

If the disk head is initially at 53 and if the head is moving towards the outer track, it services 65,
67, 98, 122, 124 and 183. At the last request, the arm will reverse and will move immediately
towards the first request 14 and then serves 37.

5.5.1 Selection of a Disk-Scheduling Algorithm

III SEMESTER OPERATING SYSTEM (BCS303) 7

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

SSTF is commonly used and it increases performance over FCFS.
SCAN and C-SCAN algorithm is better for a heavy load on disk.
SCAN and C-SCAN have less starvation problem.
Disk scheduling algorithm should be written as a separate module of the operating system.
SSTF or Look is a reasonable choice for a default algorithm.

SSTF is commonly used algorithms has it has a less seek time when compared with other
algorithms. SCAN and C-SCAN perform better for systems with a heavy load on the disk, (ie.
more read and write operations from disk).

Selection of disk scheduling algorithm is influenced by the file allocation method, if contiguous
file allocation is choosen, then FCFS is best suitable, because the files are stored in contiguous
blicks and there will be limited head movements required. A linked or indexed file, in contrast,
may include blocks that are widely scattered on the disk, resulting in greater head movement.

The location of directories and index blocks is also important. Since every file must be opened to
be used, and opening a file requires searching the directory structure, the directories will be
accessed frequently. Suppose that a directory entry is on the first cylinder and a file's data are on
the final cylinder. The disk head has to move the entire width of the disk. If the directory entry
were on the middle cylinder, the head would have to move, at most, one-half the width. Caching
the directories and index blocks in main memory can also help to reduce the disk-arm movement,
particularly for read requests.

Because of these complexities, the disk-scheduling algorithm is very important and is written
as a separate module of the operating system.

5.10 Disk Management

5.5.1 Disk Formatting

The process of dividing the disk into sectors and filling the disk with a special data structure is
called low-level formatting. Sector is the smallest unit of area that is read/written by the disk
controller. The data structure for a sector typically consists of a header, a data area (usually 512
bytes in size) and a trailer. The header and trailer contain information used by the disk controller,
such as a sector number and an error-correcting code (ECC).

When the controller writes a sector of data during normal I/O, the ECC is updated with a value
calculated from all the bytes in the data area. When a sector is read, the ECC is recalculated and
is compared with the stored value. If the stored and calculated numbers are different, this
mismatch indicates that the data area of the sector has become corrupted and that the disk sector
may be bad.

Most hard disks are low-level-forniatted at the factory as a part of the manufacturing process.
This formatting enables the manufacturer to test the disk and to initialize the mapping from
logical block numbers to defect-free sectors on the disk.

III SEMESTER OPERATING SYSTEM (BCS303) 8

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

When the disk controller is instructed for low-level-formatting of the disk, the size of data block
of all sector sit can also be told how many bytes of data space to leave between the header and
trailer of all sectors. It is of sizes, such as 256, 512, and 1,024 bytes. Formatting a disk with a
larger sector size means that fewer sectors can fit on each track; but it also means that fewer
headers and trailers are written on each track and more space is available for user data.

The operating system needs to record its own data structures on the disk. It does so in two steps.
partition and logical formatting.

Partition – is to partition the disk into one or more groups of cylinders. The operating system
can treat each partition as though it were a separate disk. For instance, one partition can hold a
copy of the operating system's executable code, while another holds user files.
logical formatting (or creation of a file system) - Now, the operating system stores the initial
file- system data structures onto the disk. These data structures may include maps of free and
allocated space (a FAT or modes) and an initial empty directory.

To increase efficiency, most file systems group blocks together into larger chunks, frequently
called clusters.

5.5.2 Boot Block

When a computer is switched on or rebooted—it must have an initial program to run. This
is called the bootstrap program. The bootstrap program –
 initializes the CPU registers, device controllers, main memory, and then starts the
operating system.
 Locates and loads the operating system from the disk
 jumps to beginning the operating-system execution.

The bootstrap is stored in read-only memory (ROM). Since ROM is read only, it cannot be
infected by a computer virus. The problem is that changing this bootstrap code requires changing
the ROM, hardware chips. So most systems store a tiny bootstrap loader program in the boot
ROM whose only job is to bring in a full bootstrap program from disk. The full bootstrap
program can be changed easily: A new version is simply written onto the disk. The full bootstrap
program is stored in ''the boot blocks" at a fixed location on the disk. A disk that has a boot
partition is called a boot disk or system disk.

The Windows 2000 system places its boot code in the first sector on the hard disk (master boot
record, or MBR). The code directs the system to read the boot code from, the MBR. In addition
to containing boot code, the MBR contains a table listing the partitions for the hard disk and a
flag indicating which partition the system is to be booted from.

Fig 1.9 Booting from disk in Windows 2000.

III SEMESTER OPERATING SYSTEM (BCS303) 9

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

Table

Fig. 5.9 Booting from disk in Windows 2000.

5.8.1 Bad Blocks

Disk are prone to failure of sectors due to the fast movement of r/w head. Sometimes the
whole disk will be changed. Such group of sectors that are defective are called as bad blocks.

Different ways to overcome bad blocks are –

 Some bad blocks are handled manually, eg. In MS-DOS.

 Some controllers replace each bad sector logically with one of the spare sectors (extra
sectors). The schemes used are sector sparing or forwarding and sector slipping.

In MS-DOS format command, scans the disk to find bad blocks. If format finds a bad block, it
writes a special value into the corresponding FAT entry to tell the allocation routines not to use
that block.
In SCSI disks, bad blocks are found during the low-level formatting at the factory and is updated
over the life of the disk. Low-level formatting also sets aside spare sectors not visible to the
operating system. The controller can be told to replace each bad sector logically with one of the
spare sectors. This scheme is known as sector sparing or forwarding.

A typical bad-sector transaction might be as follows:

[Link] The operating system tries to read logical block 87.
[Link] The controller finds that the sector is bad. It reports this finding to the operating system.
[Link] The next time the system is rebooted, a special, command is run
to tell the SCSI controller to replace the bad sector with a spare.
[Link] After that, whenever the system requests logical block 87, the request
is translated into the replacement sector's (spare) address by the controller.

Some controllers replace bad blocks by sector slipping. Here is an example: Suppose that logical
block 17 becomes defective and the first available spare follows sector 202. Then, sector slipping

III SEMESTER OPERATING SYSTEM (BCS303) 10

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

remaps all the sectors from 17 to 202, moving them all down one spot. That is, sector 202 is
copied into the spare, then sector 201 into 202, and then 200 into 201, and so on, until sector 18
is copied into sector 19. Slipping the sectors in this way frees up the space of sector 18, so sector
17 can be mapped to it.

5.9 Swap Space Management

The amount of swap space needed on a system can vary depending on the amount of
physical memory, the amount of virtual memory it is backing, and the way in which the virtual
memory is used. It can range from a few megabytes of disk space to gigabytes.

The swap space can overestimate or underestimated. It is safer to overestimate than to

underestimate the amount of swap space required. If a system runs out of swap space due to
underestimation of space, it may be forced to abort processes or may crash entirely.
Overestimation wastes disk space that could otherwise be used for files, but it does no other
harm.

5.9.1 Swap-Space Location

A swap space can reside in one of two places: It can be carved out of the normal
file system, or it can be in a separate disk partition. If the swap space is simply a large file
within the file system, normal file-system routines can be used to create it, name it, and allocate
its space. External fragmentation can greatly increase swapping times by forcing multiple seeks
during reading or writing of a process image. We can improve performance by caching the block
location information in physical memory.
Alternatively, swap space can be created in a separate raw partition. A separate swap-
space storage manager is used to allocate and deallocate the blocks from the raw partition.

5.9.2 Swap-Space Management: An Example

Solaris allocates swap space only when a page is forced out of physical memory, rather
than when the virtual memory page is first created.

Linux is similar to Solaris in that swap space is only used for anonymous memory or for
regions of memory shared by several processes (Fig. 5.10). Linux allows one or more swap areas
to be established. A swap area may be in either a swap file on a regular file system or a raw swap
partition. Each swap area consists of a series of 4-KB page slots, which are used to hold swapped
pages. Associated with each swap area is a swap map—an array of integer counters, each
corresponding to a page slot in the swap area. If the value of a counter is 0, the corresponding
page slot is available. Values greater than 0 indicate that the page slot is occupied by a swapped
page. The value of the counter indicates the number of mappings to the swapped page; for
example, a value of 3 indicates that the swapped page is mapped to three different processes. The
data structures for swapping on Linux systems are shown in below Fig..

III SEMESTER OPERATING SYSTEM (BCS303) 11

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

Fig. 5.10 The data structures for swapping on Linux systems.

5.10
Protection

5.10.1 Goals of Protection

Protection is a mechanism for controlling the access of programs, processes, or users to

the resources defined by a computer system. Protection ensures that only processes that have
gained proper authorization from the operating system can operate on the files, memory
segments, CPU, and other resources of a system.
Protection is required to prevent mischievous, intentional violation of an accessrestriction
by a user.

5.10.2 Principles of Protection

A key, time-tested guiding principle for protection is the ‗principle of least privilege‘.
It dictates that programs, users, and even systems be given just enough privileges to perform
their tasks. An operating system provides mechanisms to enable privileges when they are needed and
to disable them when they are not needed.

5.10.3 Domain of Protection

A computer system is a collection of processes and objects. Objects are both hardware
objects (such as the CPU, memory segments, printers, disks, and tape drives) and software
objects (such as files, programs, and semaphores). Each object (resource) has a unique name that
differentiates it from all other objects in the system.

The operations that are possible may depend on the object. For example, a CPU can only
be executed on. Memory segments can be read and written, whereas a CD-ROM or DVD-ROM
can only be read. Tape drives can be read, written, and rewound. Data files can be created,
opened, read, written, closed, and deleted; program files can be read, written, executed, and
deleted.
A process should be allowed to access only those resources
[Link] for which it has authorization
[Link] currently requires to complete process

5.10.4 Domain Structure

III SEMESTER OPERATING SYSTEM (BCS303) 12

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

A domain is a set of objects and types of access to these objects. Each domain is an
ordered pair of <object-name, rights-set>. Example, if domain D has the access right <file F,
{read, write}>, then all process executing in domain D can both read and write file F, and cannot
perform any other operation on that object.

Domains do not need to be disjoint (Fig. 5.11). They may share access rights. For
example, in below Fig., we have three domains: D1 D2, and D3. The access right < O4, (print}>
is shared by D2 and D3,it implies that a process executing in either of these two domains can
print object O5.

Fig. 5.11 System with three protection domains

A domain can be realized in a variety of ways:

Each user may be a domain. In this case, the set of objects that can be accessed depends
on the identity of the user. Domain switching occurs when the user is changed—generally when
one user logs out and another user logs in.
[Link] Each process may be a domain. In this case, the set of objects that can be
accessed depends on the identity of the process. Domain switching occurs when one process
sends a message to another process and then waits for a response.
[Link] Each procedure may be a domain. In this case, the set of objects that can be
accessed corresponds to the local variables defined within the procedure. Domain switching
occurs when a procedure call is made.

5.10 Access Matrix

Our model of protection can be viewed as a matrix, called an access matrix. It is a
general model of protection that provides a mechanism for protection without imposing a
particular protection policy. The rows of the access matrix represent domains, and the columns
represent objects. Each entry in the matrix consists of a set of access rights. The entry access(i,j)
defines the set of operations that a process executing in domain Di can invoke on object Oj.

Fig. 5.12 Access matrix

III SEMESTER OPERATING SYSTEM (BCS303) 13

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

In the above diagram (Fig, 5.12), there are four domains and four objects—three files (F1, F2, F3)
and one printer. A process executing in domain D1 can read files F1 and F3. A process executing in
domain D4 has the same privileges as one executing in domain D1; but in addition, it can also write
onto files F1 and F3.

When a user creates a new object Oj, the column Oj is added to the access matrix with the
appropriate initialization entries, as dictated by the creator.

The process executing in one domain and be switched to another domain. When we switch a
process from one domain to another, we are executing an operation (switch) on an object (the
domain). Domain switching from domain Di to domain Dj is allowed if and only if the access right
switch € access (i,j). Thus, in the given Fig. 5.13, a process executing in domain D2 can switch to
domain D3 or to domain D5. A process in domain D4 can switch to D1, and one in domain D1 can
switch to domain D2.

Fig. 5.13 Access matrix of with domains as objects

Allowing controlled change in the contents of the access-matrix entries requires three additional
operations: copy, owner, and control.

The ability to copy an access right from one domain (or row) of the access matrix to another is
denoted by an asterisk (*) appended to the access right. The copy right allows the copying of the
access right only within the column for which the right is defined. In the below Fig., a process
executing in domain D2 can copy the read operation into any entry associated with file F2. Hence,
the access matrix of Fig. 5.15. can be modified to the access matrix shown in Fig. (b). This scheme
has two variants: A right is copied from access (i, j) to access (k, j); it is then removed from access
(i,j). This action is a transfer of a right, rather than a copy.

1) Propagation of the copy right- limited copy. Here, when the right R* is copied from access (i,j)
to access(k,j), only the right R (not R*) is created. A process executing in domain Dk cannot
further copy the right R.

We also need a mechanism to allow addition of new rights and removal of some rights. The
owner right controls these operations. If access(i,j) includes the owner right, then a process
executing in domain Di, can add and remove any right in any entry in column j.

III SEMESTER OPERATING SYSTEM (BCS303) 14

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

For example, in below Fig. (a), domain D1 is the owner of F1, and thus can add and delete any
valid right in column F1. Similarly, domain D2 is the owner of F2 and F3 and thus can add and
remove any valid right within these two columns. Thus, the access matrix of Fig.(a) can be
modified to the access matrix shown in Fig.(b) as follows.

A mechanism is also needed to change the entries in a row. If access(i,j) includes the control
right, then a process executing in domain Di, can remove any access right from row j. For
example, in Fig., we include the control right in access(D3, D4). Then, a process executing in
domain D3 can modify domain D4

Fig. 5.14 Access matrix with owner rights

Fig. 5.15 Modified access matrix - 1

III SEMESTER OPERATING SYSTEM (BCS303) 15

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

Fig. 5.16 Modified access matrix - 2

5.11 Implementation of Access Matrix

Different methods of implementing the access matrix (which is sparse).

 Global Table
 Access Lists for Objects
 Capability Lists for Domains
 Lock-Key Mechanism

5.11.1 Global Table

This is the simplest implementation of access matrix. A set of ordered triples <domain,
object, rights-set> is maintained in a file. Whenever an operation M is executed on an object Oj,
within domain Di, the table is searched for a triple <Di, Oj, Rk>. If this triple is found, the
operation is allowed to continue; otherwise, an exception (or error) condition is raised.

Drawbacks -

The table is usually large and thus cannot be kept in main memory.
Additional I/O is needed
5.11.2 Access Lists for Objects

Each column in the access matrix can be implemented as an access list for one object.
The empty entries are discarded. The resulting list for each object consists of ordered pairs
<domain, rights-set>. It defines all domains access right for that object. When an operation M is
executed on object Oj in Di, search the access list for object Oj, look for an entry <Di, Rj > with
M e Kj. If the entry is found, we allow the operation; if it is not, we check the
default set. If M is in the default set, we allow the access. Otherwise, access is
denied, and an exception condition occurs. For efficiency, we may check the
default set first and then search the access list.

III SEMESTER OPERATING SYSTEM (BCS303) 16

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

5.11.2 Capability Lists for Domains

A capability list for a domain is a list of objects together with the operations allowed on
those objects. An object is often represented by its name or address, called a capability. To
execute operation M on object Oj, the process executes the operation M, specifying the capability
for object Oj as a parameter. Simple possession of the capability means that access is allowed.

Capabilities are usually distinguished from other data in one of two ways:
Each object has a tag to denote its type either as a capability or as accessible
data.
Alternatively, the address space associated with a program can be split into two parts. One part is
accessible to the program and contains the program's normal data and instructions. The other
part, containing the capability list, is accessible only by the operatingsystem.

5.11.3 A Lock-Key Mechanism

The lock-key scheme is a compromise between access lists and capability lists. Each
object has a list of unique bit patterns, called locks. Similarly, each domain has a list of unique
bit patterns, called keys. A process executing in a domain can access an object only if that
domain has a key that matches one of the locks of the object.

5.12 Access Control

Fig. 5.17 Rote-based access control in Solaris 10

Each file and directory are assigned an owner, a group, or possibly a list of users, and for
each of those entities, access-control information is assigned.

Solaris 10 advances the protection available in the Sun Microsystems operating system
by explicitly adding the principle of least privilege via role-based access control (RBAC). This
facility revolves around privileges. A privilege is the right to execute a system call or to use an
option within that system call (such as opening a file with write access). Privileges can be
assigned to processes, limiting them to exactly the access they need to perform their work.

Privileges and programs can also be assigned to roles. Users are assigned roles or can take

III SEMESTER OPERATING SYSTEM (BCS303) 17

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

roles based on passwords to the roles. In this way, a user can take a role that enables a privilege,
allowing the user to run a program to accomplish a specific task, as depicted in Fig.5.17. This
implementation of privileges decreases the security risk associated with super users and setuid
programs.

5.13 Revocation of Access Rights

Since the capabilities are distributed throughout the system, we must find them before we
can revoke them. Schemes that implement revocation for capabilities include the following:
5.13.1 Reacquisition. Periodically, all capabilities are deleted from each domain. If
a process wants to use a capability, it may find that that capability has been deleted. The
process may then try to reacquire the capability. If access has been revoked, the process
will not be able to reacquire the capability.

5.13.2 Back-pointers. A list of pointers is maintained with each object, pointing to

all capabilities associated with that object. When revocation is required, we can follow
these pointers, changing the capabilities as necessary.

5.13.3 Indirection. The capabilities point indirectly to the objects. Each capability
points to a unique entry in a global table, which in turn points to the object. We
implement revocation by searching the global table for the desired entry and deleting it.
Then, when an access is attempted, the capability is found to point to an illegal table
entry.

5.13.4 Keys. A key is a unique bit pattern that can be associated with a capability.
This key is defined when the capability is created, and it can be neither modified nor
inspected by the process owning the capability. A master key is associated with each
object; it can be defined or replaced with the set-key operation.

5.13.5 When a capability is created, the current value of the master key is associated
with the capability. When the capability is exercised, its key is compared with the
master key. If the keys match, the operation is allowed to continue; otherwise, an
exception condition is raised.

In key-based schemes, the operations of defining keys, inserting them into lists, and
deleting them from lists should not be available to all users.

5.14 Capability-Based System

Here, survey of two capability-based protection systems is done.

1) An Example: Hydra

Hydra is a capability-based protection system that provides considerable

flexibility. A fixed set of possible access rights is known to and interpreted by the system. These
rights include such basic forms of access as the right to read, write, or execute a memory
segment. In addition, a

III SEMESTER OPERATING SYSTEM (BCS303) 18

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

user (of the protection system) can declare other rights.

Operations on objects are defined procedurally. The procedures that implement such
operations are themselves a form of object, and they are accessed indirectly by capabilities. The
names of user-defined procedures must be identified to the protection system if it is to deal with
objects of the user defined type. When the definition of an object is made known to Hydra, the
names of operations on the type become auxiliary rights.

Hydra also provides rights amplification. This scheme allows a procedure to be certified
as trustworthy to act on a formal parameter of a specified type on behalf of any process that
holds a right to execute the procedure. The rights held by a trustworthy procedure are
independent of, and may exceed, the rights held by the calling process.

When a user passes an object as an argument to a procedure, we may need to ensure that
the procedure cannot modify the abject. We can implement this restriction readily by passing an
access right that does not have the modification (write) right.

The procedure-call mechanism of Hydra was designed as a direct solution to the problem
of mutually suspicious subsystems.

A Hydra subsystem is built on top of its protection kernel and may require protection of
its own components. A subsystem interacts with the kernel through calls on a set of kernel-
defined primitives that define access rights to resources defined by the subsystem.

2) An Example: Cambridge CAP System

A different approach to capability-based protection has been taken in the design of the
Cambridge CAP system. CAP's capability system is simpler and superficially less powerful than
that of Hydra. It can be used to provide secure protection of user-defined objects. CAP has two
kinds of capabilities.

The ordinary kind is called a data capability. It can be used to provide access to objects,
but the only rights provided are the standard read, write, and execute of the individual storage
segments associated with the object.
The second kind of capability is the software capability, which is protected, but not
interpreted, by the CAP microcode. It is interpreted by a protected (that is, a privileged)
procedure, which may be written by an application programmer as part of a subsystem. A
particular kind of rights amplification is associated with a protected procedure.

5.15 Case Study: The Linux Operating System

5.15.1 History

 Linux is a modem, free operating system based on UNIX standards.

III SEMESTER OPERATING SYSTEM (BCS303) 19

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

 First developed as a small but self-contained kernel in 1991 by Linus Torvalds, with
the major design goal of UNIX compatibility.
 Its history has been one of collaboration by many users from all around the world,
corresponding almost exclusively over the Internet.
 It has been designed to run efficiently and reliably on common PC hardware, but also
runs on a variety of other platforms.
 The core Linux operating system kernel is entirely original, but it can run much
existing free UNIX software, resulting in an entire UNIX-compatible operating system
free from proprietary code.

5.15.2 The Linux Kernel

 Version 0.01 (May 1991) had no networking, ran only on 80386-compatible Intel
processors and on PC hardware, had extremely limited device-drive support, and
supported only the Minix file system.
 Linux 1.0 (March 1994) included these new features:

[Link].1 Support for UNIX‘s standard TCP/IP networking protocols

[Link].2 BSD-compatible socket interface for networking programming
[Link].3 Device-driver support for running IP over an Ethernet
[Link].4 Enhanced file system
[Link].5 Support for a range of SCSI controllers for high-performance disk access
[Link].6 Extra hardware support

 Version 1.2 (March 1995) was the final PC-only Linux kernel.

5.15.3 Linux 2.0

 Released in June 1996, 2.0 added two major new capabilities:
[Link].1 Support for multiple architectures, including a fully 64-bit native Alpha port.
[Link].2 Support for multiprocessor architectures
 Other new features included:
[Link].1 Improved memory-management code
[Link].2 Improved TCP/IP performance
[Link].3 Support for internal kernel threads, for handling dependencies between
loadable modules, and for automatic loading of modules on demand.
[Link].4 Standardized configuration interface
 Available for Motorola 68000-series processors, Sun Sparc systems, and for PC and
PowerMac systems .

III SEMESTER OPERATING SYSTEM (BCS303) 20

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

5.15.4 The Linux System

 Linux uses many tools developed as part of Berkeley‘s BSD operating system,
MIT‘s X Window System, and the Free Software Foundation's GNU project.
 The min system libraries were started by the GNU project, with improvements
provided by the Linux community.
 Linux networking-administration tools were derived from 5.3BSD code;
recent BSD derivatives such as Free BSD have borrowed code from Linux in
return.
 The Linux system is maintained by a loose network of developers collaborating
over the Internet, with a small number of public ftp sites acting as de facto
standard repositories.

5.15.5 Linux Distributions

 Standard, precompiled sets of packages, or distributions, include the basic Linux
system, system installation and management utilities, and ready-to-install packages of
common UNIX tools.
 The first distributions managed these packages by simply providing a means of
unpacking all the files into the appropriate places; modern distributions include
advanced package management.
 Early distributions included SLS and Slackware. Red Hat and Debian are popular
distributions from commercial and noncommercial sources, respectively.
 The RPM Package file format permits compatibility among the various Linux
distributions.

5.15.6 Linux Licensing

 The Linux kernel is distributed under the GNU General Public License (GPL), the
terms of which are set out by the Free Software Foundation.
 Anyone using Linux, or creating their own derivative of Linux, may not make the
derived product proprietary; software released under the GPL may not be redistributed
as a binary- only product.
5.16 Design Principles

 Linux is a multiuser, multitasking system with a full set of UNIX-compatible tools..

 Its file system adheres to traditional UNIX semantics, and it fully implements the
standard UNIX networking model.
 Main design goals are speed, efficiency, and standardization.
 Linux is designed to be compliant with the relevant POSIX documents; at least two
Linux distributions have achieved official POSIX certification.

III SEMESTER OPERATING SYSTEM (BCS303) 21

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

 The Linux programming interface adheres to the SVR4 UNIX semantics, rather than
to BSD behavior.

5.17 Components of a Linux System

 Like most UNIX implementations, Linux is composed of three main bodies of code;
the most important distinction between the kernel and all other components.
 The kernel is responsible for maintaining the important abstractions of the
operating system.

Kernel code executes in kernel mode with full access to all the physical resources of
the computer.
All kernel code and data structures are kept in the same single address space (Fig. 5.18) .

Fig. 5.18 Components of the Linux system

 The system libraries define a standard set of functions through which applications
interact with the kernel, and which implement much of the operating-system functionality
that does not need the full privileges of kernel code.
 The system utilities perform individual specialized management tasks.

5.18 Kernel Modules

 Sections of kernel code that can be compiled, loaded, and unloaded independent of the
rest of the kernel.
 A kernel module may typically implement a device driver, a file system, or a
networking protocol.
 The module interface allows third parties to write and distribute, on their own terms,
device drivers or file systems that could not be distributed under the GPL.
 Kernel modules allow a Linux system to be set up with a standard, minimal kernel,
without any extra device drivers built in.

III SEMESTER OPERATING SYSTEM (BCS303) 22

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

 Three components to Linux module support:

 module management
 driver registration
 conflict resolution

5.18 Module Management

 Supports loading modules into memory and letting them talk to the rest of the kernel.
 Module loading is split into two separate sections:
 Managing sections of module code in kernel memory
 Handling symbols that modules are allowed to reference
 The module requestor manages loading requested, but currently unloaded, modules; it
also regularly queries the kernel to see whether a dynamically loaded module is still in
use, and will unload it when it is no longer actively needed.

5.19 Driver Registration

5.19.1 Allows modules to tell the rest of the kernel that a new driver has become available.
5.19.2 The kernel maintains dynamic tables of all known drivers, and provides a set
of routines to allow drivers to be added to or removed from these tables at any
time.
5.19.3 Registration tables include the following items:
[Link] Device drivers
[Link] File systems
[Link] Network protocols
[Link] Binary format

5.20 Conflict Resolution

5.20.1 A mechanism that allows different device drivers to reserve hardware
resources and to protect those resources from accidental use by another driver
5.20.2 The conflict resolution module aims to:
[Link] Prevent modules from clashing over access to hardware resources
[Link] Prevent autoprobes from interfering with existing device drivers
[Link] Resolve conflicts with multiple drivers trying to access the same hardware

5.21 Process Management

III SEMESTER OPERATING SYSTEM (BCS303) 23

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

5.21.1 UNIX process management separates the creation of processes and the running of
a new program into two distinct operations.
[Link] The fork system call creates a new process.
[Link] A new program is run after a call to execve.
5.21.2 Under UNIX, a process encompasses all the information that the operating
system must maintain t track the context of a single execution of a single program.
5.21.3 Under Linux, process properties fall into three groups: the
process‘s identity, environment, and context.

5.22 Process Identity

_ Process ID (PID). The unique identifier for the process; used to specify processes to the
operating system when an application makes a system call to signal, modify, or wait for another
process.
_ Credentials. Each process must have an associated user ID and one or more group IDs that
determine the process‘s rights to access system resources and files.

_ Personality. Not traditionally found on UNIX systems, but under Linux each process has an
associated personality identifier that can slightly modify the semantics of certain system calls.
Used primarily by emulation libraries to request that system calls be compatible with certain
specific flavors of UNIX.

5.23 Process Environment

5.23.1 The process‘s environment is inherited from its parent, and is composed of two null-
terminated vectors:

[Link] The argument vector lists the command-line arguments used to invoke the
running program; conventionally starts with the name of the program itself
[Link] The environment vector is a list of ―NAME=VALUE‖ pairs that associates
named environment variables with arbitrary textual values.

5.23.2 Passing environment variables among processes and inheriting variables by a

process‘s children are flexible means of passing information to components of the
user mode system

III SEMESTER OPERATING SYSTEM (BCS303) 24

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

software.
5.23.3 The environment-variable mechanism provides a customization of the operating
system that can be set on a per-process basis, rather than being conFig.d for the system
as a whole.

5.24 Process Context

5.24.1 The (constantly changing) state of a running program at any point in time.
5.24.2 The scheduling context is the most important part of the process context; it is the
information that the scheduler needs to suspend and restart the process.
5.24.3 The kernel maintains accounting information about the resources currently being
consumed by each process, and the total resources consumed by the process in its lifetime
so far.
5.24.4 The file table is an array of pointers to kernel file structures. When making file I/O
system calls, processes refer to files by their index into this table.
5.24.5 Whereas the file table lists the existing open files, the file-system context applies to
requests to open new files. The current root and default directories to be used for new file
searches are stored here.
5.24.6 The signal-handler table defines the routine in the process‘s address space to be
called when specific signals arrive.
5.24.7 The virtual-memory context of a process describes the full contents of the its private
address space.

5.25 Processes and Threads

5.25.1 Linux uses the same internal representation for processes and threads; a thread is
simply a new process that happens to share the same address space as its parent.
5.25.2 A distinction is only made when a new thread is created by the clone system call.
[Link] fork creates a new process with its own entirely new process context
[Link] clone creates a new process with its own identity, but that is allowed to
share the data structures of its parent
5.25.3 Using clone gives an application fine-grained control over exactly what is
shared between two threads.

5.26 Scheduling

5.26.1 The job of allocating CPU time to different tasks within an operating system.
5.26.2 While scheduling is normally thought of as the running and interrupting of
processes, in Linux, scheduling also includes the running of the various kernel tasks.
5.26.3 Running kernel tasks encompasses both tasks that are requested by a running process and

III SEMESTER OPERATING SYSTEM (BCS303) 25

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

tasks that execute internally on behalf of a device driver.

5.23.1 Kernel Synchronization

 A request for kernel-mode execution can occur in two ways:

 A running program may request an operating system service, either explicitly via
a system call, or implicitly, for example, when a page fault occurs.
 A device driver may deliver a hardware interrupt that causes the CPU to start
executing a kernel-defined handler for that interrupt.
 Kernel synchronization requires a framework that will allow the kernel‘s critical sections
to run without interruption by another critical section
 Linux uses two techniques to protect critical sections:
1. Normal kernel code is non preemptible
 when a time interrupt is received while a process is executing a kernel system
service routine, the kernel‘s need_resched flag is set so that the scheduler will
run once the system call has completed and control is about to be returned to
user mode.
2. The second technique applies to critical sections that occur in an interrupt service
routines.
 By using the processor‘s interrupt control hardware to disable interrupts during a critical
section, the kernel guarantees that it can proceed without the risk of concurrent access of
shared data structures.

 To avoid performance penalties, Linux‘s kernel uses a synchronization architecture that

allows long critical sections to run without having interrupts disabled for the critical
section‘s entire duration.

 Interrupt service routines are separated into a top half and a bottom half.
 The top half is a normal interrupt service routine, and runs with
recursive interrupts disabled.
 The bottom half is run, with all interrupts enabled, by a miniature scheduler that
ensures that bottom halves never interrupt themselves.
 This architecture is completed by a mechanism for disabling selected
bottom halves while executing normal, foreground kernel code.
5.23.2. Interrupt Protection Levels

III SEMESTER OPERATING SYSTEM (BCS303) 26

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

 Each level may be interrupted by code running at a higher level, but will never
be interrupted by code running at the same or a lower level.
 User processes can always be preempted by another process when a time-sharing
scheduling interrupt occurs ( Fig. 5.19).

Fig. 5.19 Interrupt protection levels

5.23.3 Process Scheduling

 Linux uses two process-scheduling algorithms:

 A time-sharing algorithm for fair preemptive scheduling between
multiple processes
 A real-time algorithm for tasks where absolute priorities are more important than
fairness
 A process‘s scheduling class defines which algorithm to apply.
 For time-sharing processes, Linux uses a prioritized, credit based algorithm.
 The crediting rule factors in both the process‘s history and its priority.
 This crediting system automatically prioritizes interactive or I/O-bound processes.
 Linux implements the FIFO and round-robin real-time scheduling classes; in both
cases, each process has a priority in addition to its scheduling class.
 The scheduler runs the process with the highest priority; for equal-priority
processes, it runs the longest-waiting one
 FIFO processes continue to run until they either exit or block
 A round-robin process will be preempted after a while and moved to the end of
the scheduling queue, so that round robing processes of equal priority
automatically

III SEMESTER OPERATING SYSTEM (BCS303) 27

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

time-share between themselves.

5.23.5. Symmetric Multiprocessing

Linux 2.0 was the first Linux kernel to support SMP hardware; separate processes or threads can execute in p
To preserve the kernel‘s non preemptible synchronization requirements, SMP imposes the restriction, via a s
kernel-mode code.

5.25. Memory Management

Linux‘s physical memory-management system deals with allocating and freeing pages, groups of pages, and s
It has additional mechanisms for handling virtual memory, memory mapped into the
address space of running processes.

Fig. 5.20 Splitting of memory in the buddy system

Splitting of Memory in a Buddy Heap

5.24.1 Managing Physical Memory

 The page allocator allocates and frees all physical pages; it can allocate ranges of

III SEMESTER OPERATING SYSTEM (BCS303) 28

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

physically-contiguous pages on request.
 The allocator uses a buddy-heap algorithm (Fig. 5.20) to keep track of available physical pages.
 Each allocatable memory region is paired with an adjacent partner.
 Whenever two allocated partner regions are both freed up they are combined to
form a larger region.
 If a small memory request cannot be satisfied by allocating an existing small free
region, then a larger free region will be subdivided into two partners to satisfy the
request.
 Memory allocations in the Linux kernel occur either statically (drivers reserve a
contiguous area of memory during system boot time) or dynamically (via the page
allocator).

5.24.2. Virtual Memory

 The VM system maintains the address space visible to each process: It creates pages of
virtual memory on demand, and manages the loading of those pages from disk or their
swapping back out to disk as required.
 The VM manager maintains two separate views of a process‘s address space:
 A logical view describing instructions concerning the layout of the address space.
The address space consists of a set of nonoverlapping regions, each representing a
continuous, page-aligned subset of the address space.
 A physical view of each address space which is stored in the hardware page tables
for the process.
 Virtual memory regions are characterized by:
 The backing store, which describes from where the pages for a region come;
regions are usually backed by a file or by nothing (demand-zero memory)
 The region‘s reaction to writes (page sharing or copy-onwrite).
 The kernel creates a new virtual address space
1. When a process runs a new program with the exec system call
2. Upon creation of a new process by the fork system call
 On executing a new program, the process is given a new, completely empty virtual-
address space; the program loading routines populate the address space with virtual
memory regions.
 Creating a new process with fork involves creating a complete copy of the existing
process‘s virtual address space.
 The kernel copies the parent process‘s VMA descriptors, then creates a new set

III SEMESTER OPERATING SYSTEM (BCS303) 29

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

of page tables for the child.
 The parent‘s page tables are copies directly into the child‘s, with the
reference count of each page covered being incremented.
 After the fork, the parent and child share the same physical pages of memory
in their address spaces.
 The VM paging system relocates pages of memory from physical memory out to
disk when the memory is needed for something else.
 The VM paging system can be divided into two sections:
 The page out-policy algorithm decides which pages to write out to disk,
and when.
 The paging mechanism actually carries out the transfer, and pages data back
into physical memory as needed.
 The Linux kernel reserves a constant, architecture dependent region of the virtual
address space of every process for its own internal use.
 This kernel virtual-memory area contains two regions:
 A static area that contains page table references to every available physical page
of memory in the system, so that there is a simple translation from physical to
virtual addresses when running kernel code.
 The reminder of the reserved section is not reserved for any specific purpose; its
page-table entries can be modified to point to any other areas of memory.
5.24.3 Executing and Loading User Programs

 Linux maintains a table of functions for loading programs; it gives each function
the opportunity to try loading the given file when an exec system call is made.
 The registration of multiple loader routines allows Linux to support both the ELF
and [Link] binary formats.
 Initially, binary-file pages are mapped into virtual memory; only when a program tries
to access a given page will a page fault result in that page being loaded into physical
memory.
 An ELF-format binary file consists of a header followed by several page-aligned
sections; the ELF loader works by reading the header and mapping the sections of the file
into separate regions of virtual memory.

5.24.4 Memory Layout for ELF Programs

Fig. 5.21 shows the typical layout of memory regions set up by the ELF loader. In a reserved
region at one end of the address space sits the kernel, in its own privileged region of virtual
memory inaccessible to normal user-mode programs. The rest of virtual memory is available to
applications, which can use the kernel's memory-mapping functions to create regions that map a
portion of a file or that are available for application data.

III SEMESTER OPERATING SYSTEM (BCS303) 30

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

Fig. 5.21 Slab allocator in Linux

The loader's job is to set up the initial memory mapping to allow the execution of the program to
start. The regions that need to be initialized include the stack and the program's text and data
regions. The stack is created at the top of the user-mode virtual memory; it grows downward
toward lower-numbered addresses.

5.24.5 Static and Dynamic Linking

 A program whose necessary library functions are embedded directly in the

program‘s executable binary file is statically linked to its libraries.
 The main disadvantage of static linkage is that every program generated must
contain copies of exactly the same common system library functions.
 Dynamic linking is more efficient in terms of both physical memory and disk-space usage
because it loads the system libraries into memory only once.

5.25. File Systems

 To the user, Linux‘s file system appears as a hierarchical directory tree obeying
UNIX semantics.
 Internally, the kernel hides implementation details and manages the multiple different
file systems via an abstraction layer, that is, the virtual file system (VFS).
 The Linux VFS is designed around object-oriented principles and is composed of
two components:

III SEMESTER OPERATING SYSTEM (BCS303) 31

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

 A set of definitions that define what a file object is allowed to look like

✔ The inode-object and the file-object structures represent individual files

✔ the file system object represents an entire file system

 A layer of software to manipulate those objects.

5.25.1 The Linux Ext2fs File System

 Ext2fs (Fig. 5.22) uses a mechanism similar to that of BSD Fast File System (ffs)
for locating data blocks belonging to a specific file.

 The main differences between ext2fs and ffs concern their disk allocation policies.
 In ffs, the disk is allocated to files in blocks of 8Kb, with blocks being subdivided
into fragments of 1Kb to store small files or partially filled blocks at the end of a
file.

 Ext2fs does not use fragments; it performs its allocations in smaller units. The
default block size on ext2fs is 1Kb, although 2Kb and 4Kb blocks are also
supported.

 Ext2fs uses allocation policies designed to place logically adjacent blocks of a file
into physically adjacent blocks on disk, so that it can submit an I/O request for
several disk blocks as a single operation.

Ext2fs Block-Allocation Policies

The Linux Proc File System

 The proc file system does not store data, rather, its contents are computed on
demand according to user file I/O requests.

 proc must implement a directory structure, and the file contents within; it must then define

III SEMESTER OPERATING SYSTEM (BCS303) 32

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

a unique and persistent inode number for each directory and files it contains.

Fig. 5.22 ext2fs block-allocation policies.

 It uses this inode number to identify just what operation is required when a user
tries to read from a particular file inode or perform a lookup in a particular
directory inode.
 When data is read from one of these files, proc collects the appropriate
information, formats it into text form and places it into the requesting process‘s
read buffer.

5.26. Input and Output

 The Linux device-oriented file system accesses disk storage through two caches:
 Data is cached in the page cache, which is unified with the virtual memory system
 Metadata is cached in the buffer cache, a separate cache indexed by the
physical disk block.

 Linux splits all devices into three classes:

 block devices allow random access to completely independent, fixed size

blocks of data
 character devices include most other devices; they don‘t need to support
the functionality of regular files.
 network devices are interfaced via the kernel‘s networking Subsystem

Device-driver Block Structure

III SEMESTER OPERATING SYSTEM (BCS303) 33

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

Linux splits all devices into three classes: block devices, character devices, and network devices. Fig.
5.23 illustrates the overall structure of the device-driver system.

Fig. 5.23 Device-driver block structure

5.27. Block Devices

 Provide the main interface to all disk devices in a system.

 The block buffer cache serves two main purposes:
 it acts as a pool of buffers for active I/O
 it serves as a cache for completed I/O
 The request manager manages the reading and writing of buffer contents to and from
a block device driver.

Character Devices
A device driver which does not offer random access to fixed blocks of data.
A character device driver must register a set of functions which implement the
driver‘s various file I/O operations.
The kernel performs almost no preprocessing of a file read or write request to a
character device, but simply passes on the request to the device.
The main exception to this rule is the special subset of character device drivers
which implement terminal devices, for which the kernel maintains a standard
interface.

5.28 Interprocess Communication

Like UNIX, Linux informs processes that an event has occurred via signals.
There is a limited number of signals, and they cannot carry information: Only the fact
that a signal occurred is available to a process.
The Linux kernel does not use signals to communicate with processes with are running in

III SEMESTER OPERATING SYSTEM (BCS303) 34

 RV Institute of Technology & Management®

OPERATING SYSTEMS Module V

kernel mode, rather, communication within the kernel is accomplished via
scheduling states and wait. Queue structures.

5.28.1 Passing Data Between Processes

 The pipe mechanism allows a child process to inherit a communication channel to its
parent, data written to one end of the pipe can be read a the other.
 Shared memory offers an extremely fast way of communicating; any data written by one
process to a shared memory region can be read immediately by any other process that has
mapped that region into its address space.
 To obtain synchronization, however, shared memory must be used in conjunction with
another Interprocess communication mechanism.

Shared Memory Object

 The shared-memory object acts as a backing store for shared-memory regions in the same
way as a file can act as backing store for a memory-mapped memory region.
 Shared-memory mappings direct page faults to map in pages from a persistent
shared- memory object.
 Shared-memory objects remember their contents even if no processes are
currently mapping them into virtual memory.

III SEMESTER OPERATING SYSTEM (BCS303) 35