Course Code Course Title L T P C QP

BCSPC3020 Operating System 3 0 0 3 A

UNIT-IV

UNIT:4 (11
Hours)
File System Interface - The Concept of a File, Access
methods, Directory Structure, File System Mounting, File
Sharing, Protection, File System Implementation - File System
Structure, File System Implementation, Allocation methods,
Free-space Management, Directory Implementation,
Efficiency and Performance. Mass Storage Structure -
Overview of Mass Storage Structure, Disk Structure, Disk
Attachment, Disk Scheduling, Disk Management, Swap space
Management.
Protection - System Protection, Goals of Protection, Principles
of Protection, Domain of Protection, Access Matrix,
Implementation of Access Matrix, Access Control, Revocation
of Access Rights, Capability-Based Systems, Language-
Based Protection.
File
A file is a named collection of related information that is recorded on secondary storage such
as magnetic disks, magnetic tapes and optical disks. In general, a file is a sequence of bits,
bytes, lines or records whose meaning is defined by the files creator and user.

File Structure
A File Structure should be according to a required format that the operating system can
understand.

 A file has a certain defined structure according to its type.

 A text file is a sequence of characters organized into lines.
 A source file is a sequence of procedures and functions.
 An object file is a sequence of bytes organized into blocks that are understandable by
the machine.
 When operating system defines different file structures, it also contains the code to
support these file structure. Unix, MS-DOS support minimum number of file
structure.

File Type
File type refers to the ability of the operating system to distinguish different types of file such
as text files source files and binary files etc. Many operating systems support many types of
files. Operating system like MS-DOS and UNIX have the following types of files −

Ordinary files

 These are the files that contain user information.

 These may have text, databases or executable program.
 The user can apply various operations on such files like add, modify, delete or even remove
the entire file.

Directory files

 These files contain list of file names and other information related to these files.

Special files

 These files are also known as device files.

 These files represent physical device like disks, terminals, printers, networks, tape drive etc.

These files are of two types −

 Character special files − data is handled character by character as in case of

terminals or printers.
  Block special files − data is handled in blocks as in the case of disks and tapes.

File Access Mechanisms

File access mechanism refers to the manner in which the records of a file may be accessed.
There are several ways to access files −

 Sequential access
 Direct/Random access
 Indexed sequential access

Sequential access

A sequential access is that in which the records are accessed in some sequence, i.e., the
information in the file is processed in order, one record after the other. This access method is
the most primitive one. Example: Compilers usually access files in this fashion.

Direct/Random access

 Random access file organization provides, accessing the records directly.

 Each record has its own address on the file with by the help of which it can be directly
accessed for reading or writing.
 The records need not be in any sequence within the file and they need not be in
adjacent locations on the storage medium.

Indexed sequential access

 This mechanism is built up on base of sequential access.

 An index is created for each file which contains pointers to various blocks.
 Index is searched sequentially and its pointer is used to access the file directly.

Space Allocation
Files are allocated disk spaces by operating system. Operating systems deploy following
three main ways to allocate disk space to files.

 Contiguous Allocation
 Linked Allocation
 Indexed Allocation

Contiguous Allocation

 Each file occupies a contiguous address space on disk.

 Assigned disk address is in linear order.
 Easy to implement.
 External fragmentation is a major issue with this type of allocation technique.
Linked Allocation

 Each file carries a list of links to disk blocks.

 Directory contains link / pointer to first block of a file.
 No external fragmentation
 Effectively used in sequential access file.
 Inefficient in case of direct access file.

Indexed Allocation

 Provides solutions to problems of contiguous and linked allocation.

 A index block is created having all pointers to files.
 Each file has its own index block which stores the addresses of disk space occupied by the
file.
 Directory contains the addresses of index blocks of files.

File Systems | Operating System

A file is a collection of related information that is recorded on secondary storage. Or file is a
collection of logically related entities. From user’s perspective a file is the smallest allotment
of logical secondary storage.

Attributes Types Operations

Name Doc Create
Type Exe Open
Size Jpg Read
Creation Data Xis Write
Author C Append
Last Modified Java Truncate
protection Class Delete
Close

File type Usual extension Function

Executable exe, com, bin Read to run machine language program

Object obj, o Compiled, machine language not linked

Source Code C, java, pas, asm, a Source code in various languages

Batch bat, sh Commands to the command interpreter

Text txt, doc Textual data, documents

 File type Usual extension Function

Word Processor wp, tex, rrf, doc Various word processor formats

Archive arc, zip, tar Related files grouped into one compressed file

Multimedia mpeg, mov, rm For containing audio/video information

FILE DIRECTORIES:
Collection of files is a file directory. The directory contains information about the files, including
attributes, location and ownership. Much of this information, especially that is concerned with
storage, is managed by the operating system. The directory is itself a file, accessible by various file
management routines.

Information contained in a device directory are:

 Name
 Type
 Address
 Current length
 Maximum length
 Date last accessed
 Date last updated
 Owner id
 Protection information

Operation performed on directory are:

 Search for a file

 Create a file
 Delete a file
 List a directory
 Rename a file
 Traverse the file system

Advantages of maintaining directories are:

 Efficiency: A file can be located more quickly.

 Naming: It becomes convenient for users as two users can have same name for different
files or may have different name for same file.
 Grouping: Logical grouping of files can be done by properties e.g. all java programs, all
games etc.

SINGLE-LEVEL DIRECTORY
In this a single directory is maintained for all the users.

 Naming problem: Users cannot have same name for two files.
  Grouping problem: Users cannot group files according to their need.

TWO-LEVEL DIRECTORY
In this separate directories for each user is maintained.

 Path name:Due to two levels there is a path name for every file to locate that file.
 Now,we can have same file name for different user.
 Searching is efficient in this method.

TREE-STRUCTURED DIRECTORY :
Directory is maintained in the form of a tree. Searching is efficient and also there is grouping
capability. We have absolute or relative path name for a file.
FILE ALLOCATION METHODS
1. Continuous Allocation: A single continuous set of blocks is allocated to a file at the time
of file creation. Thus, this is a pre-allocation strategy, using variable size portions. The file
allocation table needs just a single entry for each file, showing the starting block and the
length of the file. This method is best from the point of view of the individual sequential file.
Multiple blocks can be read in at a time to improve I/O performance for sequential
processing. It is also easy to retrieve a single block. For example, if a file starts at block b,
and the ith block of the file is wanted, its location on secondary storage is simply b+i-1.

Disadvantage

 External fragmentation will occur, making it difficult to find contiguous blocks of space of
sufficient length. Compaction algorithm will be necessary to free up additional space on disk.
 Also, with pre-allocation, it is necessary to declare the size of the file at the time of creation.

2. Linked Allocation(Non-contiguous allocation) : Allocation is on an individual block

basis. Each block contains a pointer to the next block in the chain. Again the file table needs
just a single entry for each file, showing the starting block and the length of the file. Although
pre-allocation is possible, it is more common simply to allocate blocks as needed. Any free
block can be added to the chain. The blocks need not be continuous. Increase in file size is
always possible if free disk block is available. There is no external fragmentation because
only one block at a time is needed but there can be internal fragmentation but it exists only in
the last disk block of file.
Disadvantage:

 Internal fragmentation exists in last disk block of file.

 There is an overhead of maintaining the pointer in every disk block.
 If the pointer of any disk block is lost, the file will be truncated.
 It supports only the sequencial access of files.

3. Indexed Allocation:
It addresses many of the problems of contiguous and chained allocation. In this case, the file
allocation table contains a separate one-level index for each file: The index has one entry for
each block allocated to the file. Allocation may be on the basis of fixed-size blocks or
variable-sized blocks. Allocation by blocks eliminates external fragmentation, whereas
allocation by variable-size blocks improves locality. This allocation technique supports both
sequential and direct access to the file and thus is the most popular form of file allocation.

Disk Free Space Management

Just as the space that is allocated to files must be managed ,so the space that is not currently
allocated to any file must be managed. To
perform any of the file allocation
techniques,it is necessary to know what
blocks on the disk are available. Thus we
need a disk allocation table in addition to a
file allocation table.The following are the
approaches used for free space
management.

1. Bit Tables : This method uses a vector

containing one bit for each block on
the disk. Each entry for a 0 corresponds
to a free block and each 1 corresponds
to a block in use.
For example: 00011010111100110001

In this vector every bit correspond to

a particular vector and 0 implies
that, that particular block is free and
1 implies that the block is already
occupied. A bit table has the
advantage that it is relatively easy to
find one or a contiguous group of
free blocks. Thus, a bit table works
well with any of the file allocation
methods. Another advantage is that
it is as small as possible.

2. Free Block List : In this method, each block is assigned a number sequentially and the list of
the numbers of all free blocks is maintained in a reserved block of the disk.
Free Space Management
A file system is responsible to allocate the free blocks to the file therefore it has to keep track
of all the free blocks present in the disk. There are mainly two approaches by using which,
the free blocks in the disk are managed.

1. Bit Vector
In this approach, the free space list is implemented as a bit map vector. It contains the number
of bits where each bit represents each block.

If the block is empty then the bit is 1 otherwise it is 0. Initially all the blocks are empty
therefore each bit in the bit map vector contains 1.

LAs the space allocation proceeds, the file system starts allocating blocks to the files and
setting the respective bit to 0.

2. Linked List
It is another approach for free space management. This approach suggests linking together all
the free blocks and keeping a pointer in the cache which points to the first free block.

Therefore, all the free blocks on the disks will be linked together with a pointer. Whenever a
block gets allocated, its previous free block will be linked to its next free block.

Blocks and records

--------------------------------
• Records are the logical unit of access of a structured file
– But blocks are the unit for I/O with secondary storage
• Three approaches are common
– Fixed length blocking
– Variable length spanned blocking
– Variable-length unspanned blocking

Fixed Blocking
----------------------------
• Fixed-length records are used, and an integral number of records are stored in a
block.
• Unused space at the end of a block is internal fragmentation Fixed Blocking
Variable Length Spanned Blocking
-------------------------------------------------
• Variable-length records are used and are packed into blocks with no unused space.
• Some records may span multiple blocks – Continuation is indicated by a pointer to
the successor block.

Variable-length unspanned blocking

-----------------------------------------------------
• Uses variable length records without spanning
• Wasted space in most blocks because of the inability to use the remainder of a
block if the next record is larger than the remaining unused space.
 Mass-Storage Systems
Overview of Mass Storage Structure

Magnetic disks provide bulk of secondary storage of modern

computers:

 Drives rotate at 60 to 200 times per second

 Transfer rate is the rate at which data flow between drive and
computer
 Positioning time (random-access time) is time to move disk
arm to desired cylinder (seek time)
 and time for desired sector to rotate under the disk head
(rotational latency)
 Head crash results from disk head making contact with the
disk surface
 Disks can be removable
 Disk drives are addressed as large 1-dimensional arrays of
logical blocks,
where the logical block is the smallest unit of transfer
 The 1-dimensional array of logical blocks is mapped into the
sectors of the disk sequentially.
Sector 0 is the first sector of the first track on the outermost
cylinder.
Mapping proceeds in order through that track, then the rest of
the tracks in that cylinder and
then through the rest of the cylinders from outermost to
innermost.

Disk Scheduling Algorithms

The operating system is responsible for using hardware

efficiently.
For the disk drives, this means having a fast access time & disk
bandwidth.

 Access time has two major components:

Seek time is the time for the disk to move the heads to the
cylinder containing the desired sector Rotational latency
time waiting for the disk to rotate the desired sector to the
disk head
We like to minimize seek time.

 Disk bandwidth is the total number of bytes transferred

divided by the total time between the first request for service
and the completion of the last transfer.
Several algorithms exist to schedule the servicing of disk I/O
requests.
We illustrate them with a Request Queue (cylinder range 0-
199):
 98, 183, 37, 122, 14, 124, 65, 67

Head pointer: cylinder 53

FCFS
Illustration shows total head movement of 640
cylinders

SSTF
Selects the request with the minimum seek time from the
current head position SSTF scheduling may cause starvation
of some requests Illustration shows total head movement of
236 cylinders
SCAN
The disk arm starts at one end of the disk, and moves
toward the other end, servicing requests until it gets to the
other end of the disk, where the head movement is reversed
and servicing continues. SCAN algorithm sometimes called
the elevator algorithm. Illustration shows total head
movement of 208 cylinders

C-SCAN
Provides a more uniform wait time than SCAN
 The head moves from one end of the disk to the other,
servicing requests as it goes
  When it reaches the other end, however, it immediately
returns to the beginning of the disk,
without servicing any requests on the return trip.

Treats the cylinders as a Circular list that wraps around from

the last cylinder to the first one

C-LOOK

 Version of C-SCAN
 Arm only goes as far as the last request in each direction,
then reverses direction immediately, without first going all
the way to the end of the disk.
Selecting a Disk-Scheduling Algorithm

 SSTF is common and has a natural appeal

 SCAN and C-SCAN perform better for systems that place a
heavy load on the disk

Network-Attached Storage
 Network-attached storage (NAS) is storage made available over
a network
rather than over a local connection (such as a bus)
 Implemented via remote procedure calls (RPCs) between host
and storage

Storage Area Network

RAID (Redundent Arrays of Independent Disks) Structure
 multiple disk drives provides reliability via redundancy
Increases the mean time to failure
 improve performance and reliability of the storage system by
storing redundant data
 Mirroring or shadowing keeps duplicate of each disk
 small number of hot-spare disks are left unallocated,
automatically replacing a failed disk and having data rebuilt
onto them.

Stable-Storage Implementation

To implement stable storage:

 Replicate information on more than one nonvolatile storage
media with independent failure modes
 Update information in a controlled manner to ensure that we can
recover the stable data after any failure during data transfer or
recovery.

Tertiary Storage Devices

 Low cost is the defining characteristic of tertiary storage

 Generally, tertiary storage is built using removable media
 Common examples of removable media are floppy disks and
CD-ROMs; other types are available

Removable Disks

 Floppy disk — thin flexible disk coated with magnetic material,

enclosed in a protective plastic case
Most floppies hold about 1 MB;
 Removable magnetic disks can be nearly as fast as hard disks,
but they are at a greater risk of damage from exposure
 Magneto-optic disk records data on a rigid platter coated with
magnetic material
The magneto-optic head flies much farther from the disk surface
than a magnetic disk head,
and the magnetic material is covered with a protective layer of
plastic or glass; resistant to head crashes
  Optical disks do not use magnetism; they employ special
materials that are altered by laser light

WORM Disks
 The data on read-write disks can be modified over and over
 WORM (“Write Once, Read Many Times”) disks can be
written only once
 Thin aluminum film sandwiched between two glass or plastic
platters
 To write a bit, the drive uses a laser light to burn a small hole
through the aluminum;
information can be destroyed by not altered
 Very durable and reliable
 Read-only disks, such as CD-ROM and DVD, come from the
factory with the data pre-recorded

Magnetic tape

 Was early secondary-storage medium

 Relatively permanent and holds large quantities of data
 Access time slow
 Random access ~1000 times slower than disk
 Mainly used for backup, storage of infrequently-used data,
transfer medium between systems
 Once data under head, transfer rates comparable to disk
 20-200GB typical storage
 Compared to a disk, a tape is less expensive and holds more
data, but random access is much slower
 Large tape installations typically use robotic tape changers that
move tapes between tape drives and storage slots in a tape
library

Tape Drives Application Interface

 The basic operations for a tape drive differ from those of a disk
drive
 locate() positions the tape to a specific logical block,
 The read_position() returns the logical block number where the
tape head is
  The space() operation enables relative motion
 Tape drives are “append-only” devices; updating a block in the
middle of the tape also effectively erases everything beyond that
block
 An EOT mark is placed after a block that is written

Hierarchical Storage Management (HSM)

 A hierarchical storage system extends the storage hierarchy

beyond primary memory and secondary storage to incorporate tertiary
storage — usually implemented as a jukebox of tapes or removable
disks
 Small and frequently used files remain on disk
 Large, old, inactive files are archived to the jukebox
 HSM are found in supercomputing centers that have enormous
volumes of data.

Speed

 Two aspects of speed in tertiary storage are bandwidth and

latency
Sustained bandwidth – average data rate during a large
transfer;
Effective bandwidth – average over the entire I/O time,
including seek() or locate(), and cartridge switching
Access latency – amount of time needed to locate data

 Access time for a disk – move the arm to the selected cylinder and
wait for the rotational latency; < 35 milliseconds

 Access on tape requires winding the tape reels until the selected block
reaches the tape head;

tens or hundreds of seconds

 Generally random access within a tape cartridge is about a thousand

times slower than random access on disk
 Reliability

 A fixed disk drive is likely to be more reliable than a removable

disk or tape drive
 An optical cartridge is likely to be more reliable than a
magnetic disk or tape
 A head crash in a fixed hard disk generally destroys the data,
whereas the failure of a tape drive or optical disk drive often
leaves the data cartridge unharmed

Cost

 Main memory is much more expensive than disk storage

 The cost per megabyte of hard disk storage is competitive with

magnetic tape.

Protection
14.1 Goals of Protection

 Obviously to prevent malicious misuse of the system by users or programs. See chapter 15
for a more thorough coverage of this goal.
 To ensure that each shared resource is used only in accordance with system policies, which
may be set either by system designers or by system administrators.
 To ensure that errant programs cause the minimal amount of damage possible.
 Note that protection systems only provide the mechanisms for enforcing policies and
ensuring reliable systems. It is up to administrators and users to implement those
mechanisms effectively.

14.2 Principles of Protection

 The principle of least privilege dictates that programs, users, and systems be given just
enough privileges to perform their tasks.
 This ensures that failures do the least amount of harm and allow the least of harm to be
done.
 For example, if a program needs special privileges to perform a task, it is better to make it a
SGID program with group ownership of "network" or "backup" or some other pseudo group,
rather than SUID with root ownership. This limits the amount of damage that can occur if
something goes wrong.
 Typically each user is given their own account, and has only enough privilege to modify their
own files.
 The root account should not be used for normal day to day activities - The System
Administrator should also have an ordinary account, and reserve use of the root account for
only those tasks which need the root privileges
14.3 Domain of Protection

 A computer can be viewed as a collection of processes and objects ( both HW & SW ).

 The need to know principle states that a process should only have access to those objects it
needs to accomplish its task, and furthermore only in the modes for which it needs access
and only during the time frame when it needs access.
 The modes available for a particular object may depend upon its type.

14.3.1 Domain Structure

 A protection domain specifies the resources that a process may access.

 Each domain defines a set of objects and the types of operations that may be invoked on
each object.
 An access right is the ability to execute an operation on an object.
 A domain is defined as a set of < object, { access right set } > pairs, as shown below. Note
that some domains may be disjoint while others overlap.

Figure 14.1 - System with three protection domains.

 The association between a process and a domain may be static or dynamic.

o If the association is static, then the need-to-know principle requires a way of
changing the contents of the domain dynamically.
o If the association is dynamic, then there needs to be a mechanism for domain
switching.
 Domains may be realized in different fashions - as users, or as processes, or as procedures.
E.g. if each user corresponds to a domain, then that domain defines the access of that user,
and changing domains involves changing user ID.

14.3.2 An Example: UNIX

 UNIX associates domains with users.

 Certain programs operate with the SUID bit set, which effectively changes the user ID, and
therefore the access domain, while the program is running. ( and similarly for the SGID bit. )
Unfortunately this has some potential for abuse.
 An alternative used on some systems is to place privileged programs in special directories, so
that they attain the identity of the directory owner when they run. This prevents crackers
from placing SUID programs in random directories around the system.
 Yet another alternative is to not allow the changing of ID at all. Instead, special privileged
daemons are launched at boot time, and user processes send messages to these daemons
when they need special tasks performed.
14.3.3 An Example: MULTICS

 The MULTICS system uses a complex system of rings, each corresponding to a different
protection domain, as shown below:

Figure 14.2 - MULTICS ring structure.

 Rings are numbered from 0 to 7, with outer rings having a subset of the privileges of the
inner rings.
 Each file is a memory segment, and each segment description includes an entry that
indicates the ring number associated with that segment, as well as read, write, and execute
privileges.
 Each process runs in a ring, according to the current-ring-number, a counter associated with
each process.
 A process operating in one ring can only access segments associated with higher ( farther
out ) rings, and then only according to the access bits. Processes cannot access segments
associated with lower rings.
 Domain switching is achieved by a process in one ring calling upon a process operating in a
lower ring, which is controlled by several factors stored with each segment descriptor:
o An access bracket, defined by integers b1 <= b2.
o A limit b3 > b2
o A list of gates, identifying the entry points at which the segments may be called.
 If a process operating in ring i calls a segment whose bracket is such that b1 <= i <= b2, then
the call succeeds and the process remains in ring i.
 Otherwise a trap to the OS occurs, and is handled as follows:
o If i < b1, then the call is allowed, because we are transferring to a procedure with
fewer privileges. However if any of the parameters being passed are of segments
below b1, then they must be copied to an area accessible by the called procedure.
o If i > b2, then the call is allowed only if i <= b3 and the call is directed to one of the
entries on the list of gates.
  Overall this approach is more complex and less efficient than other protection schemes.

14.4 Access Matrix

 The model of protection that we have been discussing can be viewed as an access matrix, in
which columns represent different system resources and rows represent different protection
domains. Entries within the matrix indicate what access that domain has to that resource.

Figure 14.3 - Access matrix.

 Domain switching can be easily supported under this model, simply by providing "switch"
access to other domains:

Figure 14.4 - Access matrix of Figure 14.3 with domains as objects.

 The ability to copy rights is denoted by an asterisk, indicating that processes in that domain
have the right to copy that access within the same column, i.e. for the same object. There
are two important variations:
o If the asterisk is removed from the original access right, then the right is transferred,
rather than being copied. This may be termed a transfer right as opposed to a copy
right.
 o If only the right and not the asterisk is copied, then the access right is added to the
new domain, but it may not be propagated further. That is the new domain does not
also receive the right to copy the access. This may be termed a limited copy right, as
shown in Figure 14.5 below:

Figure 14.5 - Access matrix with copy rights.

 The owner right adds the privilege of adding new rights or removing existing ones:
 Figure 14.6 - Access matrix with owner rights.

 Copy and owner rights only allow the modification of rights within a column. The addition of
control rights, which only apply to domain objects, allow a process operating in one domain
to affect the rights available in other domains. For example in the table below, a process
operating in domain D2 has the right to control any of the rights in domain D4.

Figure 14.7 - Modified access matrix of Figure 14.4

14.5 Implementation of Access Matrix

14.5.1 Global Table

 The simplest approach is one big global table with < domain, object, rights > entries.
 Unfortunately this table is very large ( even if sparse ) and so cannot be kept in memory
( without invoking virtual memory techniques. )
 There is also no good way to specify groupings - If everyone has access to some resource,
then it still needs a separate entry for every domain.

14.5.2 Access Lists for Objects

 Each column of the table can be kept as a list of the access rights for that particular object,
discarding blank entries.
 For efficiency a separate list of default access rights can also be kept, and checked first.

14.5.3 Capability Lists for Domains

 In a similar fashion, each row of the table can be kept as a list of the capabilities of that
domain.
 Capability lists are associated with each domain, but not directly accessible by the domain or
any user process.
 Capability lists are themselves protected resources, distinguished from other data in one of
two ways:
o A tag, possibly hardware implemented, distinguishing this special type of data.
( other types may be floats, pointers, booleans, etc. )
o The address space for a program may be split into multiple segments, at least one of
which is inaccessible by the program itself, and used by the operating system for
maintaining the process's access right capability list.

14.5.4 A Lock-Key Mechanism

 Each resource has a list of unique bit patterns, termed locks.

 Each domain has its own list of unique bit patterns, termed keys.
 Access is granted if one of the domain's keys fits one of the resource's locks.
 Again, a process is not allowed to modify its own keys.

14.5.5 Comparison

 Each of the methods here has certain advantages or disadvantages, depending on the
particular situation and task at hand.
 Many systems employ some combination of the listed methods.

14.6 Access Control

 Role-Based Access Control, RBAC, assigns privileges to users, programs, or roles as

appropriate, where "privileges" refer to the right to call certain system calls, or to use
certain parameters with those calls.
  RBAC supports the principle of least privilege, and reduces the susceptibility to abuse as
opposed to SUID or SGID programs.

Figure 14.8 - Role-based access control in Solaris 10.

14.7 Revocation of Access Rights

 The need to revoke access rights dynamically raises several questions:

o Immediate versus delayed - If delayed, can we determine when the revocation will
take place?
o Selective versus general - Does revocation of an access right to an object affect all
users who have that right, or only some users?
o Partial versus total - Can a subset of rights for an object be revoked, or are all rights
revoked at once?
o Temporary versus permanent - If rights are revoked, is there a mechanism for
processes to re-acquire some or all of the revoked rights?
 With an access list scheme revocation is easy, immediate, and can be selective, general,
partial, total, temporary, or permanent, as desired.
 With capabilities lists the problem is more complicated, because access rights are distributed
throughout the system. A few schemes that have been developed include:
o Reacquisition - Capabilities are periodically revoked from each domain, which must
then re-acquire them.
o Back-pointers - A list of pointers is maintained from each object to each capability
which is held for that object.
o Indirection - Capabilities point to an entry in a global table rather than to the object.
Access rights can be revoked by changing or invalidating the table entry, which may
affect multiple processes, which must then re-acquire access rights to continue.
 o Keys - A unique bit pattern is associated with each capability when created, which
can be neither inspected nor modified by the process.
 A master key is associated with each object.
 When a capability is created, its key is set to the object's master key.
 As long as the capability's key matches the object's key, then the capabilities
remain valid.
 The object master key can be changed with the set-key command, thereby
invalidating all current capabilities.
 More flexibility can be added to this scheme by implementing a list of keys
for each object, possibly in a global table.

14.8 Capability-Based Systems ( Optional )

14.8.1 An Example: Hydra

 Hydra is a capability-based system that includes both system-defined rights and user-
defined rights. The interpretation of user-defined rights is up to the specific user programs,
but the OS provides support for protecting access to those rights, whatever they may be
 Operations on objects are defined procedurally, and those procedures are themselves
protected objects, accessed indirectly through capabilities.
 The names of user-defined procedures must be identified to the protection system if it is to
deal with user-defined rights.
 When an object is created, the names of operations defined on that object become auxiliary
rights, described in a capability for an instance of the type. For a process to act on an object,
the capabilities it holds for that object must contain the name of the operation being
invoked. This allows access to be controlled on an instance-by-instance and process-by-
process basis.
 Hydra also allows rights amplification, in which a process is deemed to be trustworthy, and
thereby allowed to act on any object corresponding to its parameters.
 Programmers can make direct use of the Hydra protection system, using suitable libraries
which are documented in appropriate reference manuals.

14.8.2 An Example: Cambridge CAP System

 The CAP system has two kinds of capabilities:

o Data capability, used to provide read, write, and execute access to objects. These
capabilities are interpreted by microcode in the CAP machine.
o Software capability, is protected but not interpreted by the CAP microcode.
 Software capabilities are interpreted by protected ( privileged ) procedures,
possibly written by application programmers.
 When a process executes a protected procedure, it temporarily gains the
ability to read or write the contents of a software capability.
 This leaves the interpretation of the software capabilities up to the
individual subsystems, and limits the potential damage that could be caused
by a faulty privileged procedure.
 Note, however, that protected procedures only get access to software
capabilities for the subsystem of which they are a part. Checks are made
when passing software capabilities to protected procedures that they are of
the correct type.
  Unfortunately the CAP system does not provide libraries, making it harder
for an individual programmer to use than the Hydra system.

14.9 Language-Based Protection (Optional )

o As systems have developed, protection systems have become more powerful, and
also more specific and specialized.
o To refine protection even further requires putting protection capabilities into the
hands of individual programmers, so that protection policies can be implemented on
the application level, i.e. to protect resources in ways that are known to the specific
applications but not to the more general operating system.
14.9.1 Compiler-Based Enforcement
 In a compiler-based approach to protection enforcement, programmers directly specify the
protection needed for different resources at the time the resources are declared.
 This approach has several advantages:
1. Protection needs are simply declared, as opposed to a complex series of procedure
calls.
2. Protection requirements can be stated independently of the support provided by a
particular OS.
3. The means of enforcement need not be provided directly by the developer.
4. Declarative notation is natural, because access privileges are closely related to the
concept of data types.
 Regardless of the means of implementation, compiler-based protection relies upon the
underlying protection mechanisms provided by the underlying OS, such as the Cambridge
CAP or Hydra systems.
 Even if the underlying OS does not provide advanced protection mechanisms, the compiler
can still offer some protection, such as treating memory accesses differently in code versus
data segments. ( E.g. code segments cant be modified, data segments can't be executed. )
 There are several areas in which compiler-based protection can be compared to kernel-
enforced protection:

o Security. Security provided by the kernel offers better protection than that provided
by a compiler. The security of the compiler-based enforcement is dependent upon
the integrity of the compiler itself, as well as requiring that files not be modified
after they are compiled. The kernel is in a better position to protect itself from
modification, as well as protecting access to specific files. Where hardware support
of individual memory accesses is available, the protection is stronger still.
o Flexibility. A kernel-based protection system is not as flexible to provide the specific
protection needed by an individual programmer, though it may provide support
which the programmer may make use of. Compilers are more easily changed and
updated when necessary to change the protection services offered or their
implementation.
o Efficiency. The most efficient protection mechanism is one supported by hardware
and microcode. Insofar as software based protection is concerned, compiler-based
systems have the advantage that many checks can be made off-line, at compile time,
rather that during execution.
 The concept of incorporating protection mechanisms into programming languages is in its
infancy, and still remains to be fully developed. However the general goal is to provide
mechanisms for three functions:
 1. Distributing capabilities safely and efficiently among customer processes. In
particular a user process should only be able to access resources for which it was
issued capabilities.
2. Specifying the type of operations a process may execute on a resource, such as
reading or writing.
3. Specifying the order in which operations are performed on the resource, such as
opening before reading.
14.9.2 Protection in Java
 Java was designed from the very beginning to operate in a distributed environment, where
code would be executed from a variety of trusted and untrusted sources. As a result the Java
Virtual Machine, JVM incorporates many protection mechanisms
 When a Java program runs, it load up classes dynamically, in response to requests to
instantiates objects of particular types. These classes may come from a variety of different
sources, some trusted and some not, which requires that the protection mechanism be
implemented at the resolution of individual classes, something not supported by the basic
operating system.
 As each class is loaded, it is placed into a separate protection domain. The capabilities of
each domain depend upon whether the source URL is trusted or not, the presence or
absence of any digital signatures on the class ( Chapter 15 ), and a configurable policy file
indicating which servers a particular user trusts, etc.
 When a request is made to access a restricted resource in Java, ( e.g. open a local file ), some
process on the current call stack must specifically assert a privilege to perform the
operation. In essence this method assumes responsibility for the restricted access. Naturally
the method must be part of a class which resides in a protection domain that includes the
capability for the requested operation. This approach is termed stack inspection, and works
like this:
o When a caller may not be trusted, a method executes an access request within a
doPrivileged( ) block, which is noted on the calling stack.
o When access to a protected resource is requested, checkPermissions( ) inspects the
call stack to see if a method has asserted the privilege to access the protected
resource.
 If a suitable doPriveleged block is encountered on the stack before a domain
in which the privilege is disallowed, then the request is granted.
 If a domain in which the request is disallowed is encountered first, then the
access is denied and a AccessControlException is thrown.
 If neither is encountered, then the response is implementation dependent.
 In the example below the untrusted applet's call to get( ) succeeds, because the trusted URL
loader asserts the privilege of opening the specific URL lucent.com. However when the
applet tries to make a direct call to open( ) it fails, because it does not have privilege to
access any sockets.

Figure 14.9 - Stack inspection.