UNIT-5

I/O Devices
I/O with computer systems can be roughly grouped into three categories:

 Human readable: Suitable for communicating with the computer user. Examples
include printers and terminals, the latter consisting of video display, keyboard, and
perhaps other devices such as a mouse.
 Machine readable: Suitable for communicating with electronic equipment. Examples
are disk drives, USB keys, sensors, controllers, and actuators.
 Communication: Suitable for communicating with remote devices. Examples are
digital line drivers and modems.

NOTE: I/O devices can also be categorised as:

 A block-oriented device stores information in blocks that are usually of fixed size,
and transfers are made one block at a time. Generally, it is possible to reference data
by its block number. Disks and USB keys are examples of block-oriented devices.
 A stream-oriented device transfers data in and out as a stream of bytes, with no block
structure. Terminals, printers, communications ports, mouse and other pointing
devices, and most other devices that are not secondary storage are stream oriented.

Parameters used to differentiate between I/O devices:

 Data rate: There may be differences of several orders of magnitude between the data
transfer rates.
 Application: Different devices have different use in the system.
 Complexity of control: A disk is much more complex whereas a printer requires a
relatively simple control interface.
 Unit of transfer: Data may be transferred as a stream of bytes or characters (e.g.,
terminal I/O) or in larger blocks (e.g., disk I/O).
 Data representation: Different data encoding schemes are used by different devices.
 Error conditions: The nature of errors, the way in which they are reported, their
consequences, and the available range of responses differ widely from one device to
another.

ORGANIZATION OF THE I/O FUNCTION

Techniques for performing I/O:

 Programmed I/O: The processor issues an I/O command, on behalf of a process, to

an I/O module; that process then busy waits for the operation to be completed before
proceeding.

1
  Interrupt-driven I/O: The processor issues an I/O command on behalf of a process.
There are then two possibilities. If the I/O instruction from the process is non-
blocking, then the processor continues to execute instructions from the process that
issued the I/O command. If the I/O instruction is blocking, then the next instruction
that the processor executes is from the OS, which will put the current process in a
blocked state and schedule another process.
 Direct memory access (DMA): A DMA module controls the exchange of data
between main memory and an I/O module. The processor sends a request for the
transfer of a block of data to the DMA module and is interrupted only after the entire
block has been transferred.
Table given below indicates the relationship among these three techniques.

The Evolution of the I/O Function:

1. The processor directly controls a peripheral device.
2. A controller or I/O module is added. The processor uses programmed I/O without
interrupts. With this step, the processor becomes somewhat divorced from the
specific details of external device interfaces.
3. The processor need not spend time waiting for an I/O operation to be performed, thus
increasing efficiency.
4. The I/O module is given direct control of memory via DMA. It can now move a
block of data to or from memory without involving the processor, except at the
beginning and end of the transfer.
5. The I/O module is enhanced to become a separate processor, with a specialized
instruction set tailored for I/O.
6. The I/O module has a local memory of its own and is, in fact, a computer in its own
right. With this architecture, a large set of I/O devices can be controlled, with
minimal processor involvement.

Direct Memory Access:

When the processor wishes to read or write a block of data, it issues a command to the DMA
module by sending to the DMA module the following information:

2
  Whether a read or write is requested, using the read or write control line between the
processor and the DMA module
 The address of the I/O device involved, communicated on the data lines
 The starting location in memory to read from or write to, communicated on the data
lines and stored by the DMA module in its address register
 The number of words to be read or written, again communicated via the data lines and
stored in the data count register

Fig: DMA Block Diagram

The processor then continues with other work. It has delegated this I/O operation to the DMA
module. The DMA module transfers the entire block of data, one word at a time, directly to
or from memory, without going through the processor. When the transfer is complete, the
DMA module sends an interrupt signal to the processor. Thus, the processor is involved only
at the beginning and end of the transfer.

DMA Operation: To initiate a DMA transfer, the host writes a DMA command block into
memory. This block contains

 a pointer to the source of a transfer,

 a pointer to the destination of the transfer,
 a count of the number of bytes to be transferred.

3
The CPU writes the address of this command block to the DMA controller, then goes on with
other work. The DMA controller proceeds to operate the memory bus directly, placing
addresses on the bus to perform transfers without the help of the main CPU.

Handshaking between the DMA controller and the device controller is performed via a pair of
wires called DMA-request and DMA-acknowledge. The device controller places a signal on
the DMA-request wire when a word of data is available for transfer. This signal causes the
DMA controller to seize the memory bus, place the desired address on the memory-address
wires, and place a signal on the DMA-acknowledge wire. When the device controller
receives the DMA-acknowledge signal it transfers the word of data to memory and removes
the DMA-request signal. When the entire transfer is finished, the DMA controller interrupts
the CPU.

Fig: Steps in DMA Transfer

NOTE: When the DMA controller seizes the memory bus, the CPU is momentarily prevented
from accessing main memory although it can still access data items in its primary and
secondary caches. This is known as cycle stealing which slow down the CPU computation.

I/O BUFFERING
Suppose that a user process wishes to read blocks of data from a disk .The simplest way
would be to execute an I/O command to the disk unit and then wait for the data to become
available. The waiting could either be busy waiting (continuously test the device status) or,
more practically, process suspension on an interrupt.

There are two problems with this approach.

4
First, the program is hung up waiting for the relatively slow I/O to complete.

The second problem is that this approach to I/O interferes with swapping decisions by the
operating system.

NOTE: There is a risk of single-process deadlock. If a process issues an I/O command, is

suspended awaiting the result, and then is swapped out prior to the beginning of the
operation, the process is blocked waiting on the I/O event, and the I/O operation is blocked
waiting for the process to be swapped in. To avoid this deadlock, the user memory involved
in the I/O operation must be locked in main memory immediately before the I/O request is
issued, even though the I/O operation is queued and may not be executed for some time.

To avoid these overheads and inefficiencies, it is sometimes convenient to perform input

transfers in advance of requests being made and to perform output transfers some time after
the request is made. This technique is known as buffering.

“ Buffering is a technique by which the device manager can keep slower I/O devices
busy (by transferring the data in advance) during times when a process is not requiring
I/O operations. ”

Types of I/O buffering schemes:

1. Single buffering
2. Double buffering
3. Circular buffering
4. No buffering

5
Single Buffer : When a user process issues an I/O request, the operating system assigns a
buffer in the system portion of main memory to the operation. Input transfers are made to the
system buffer. When the transfer is complete, the process moves the block into user space
and immediately requests another block. This is called reading ahead, or anticipated input; it
is done in the expectation that the block will eventually be needed.

This approach will generally provide a speedup compared to the lack of system buffering.

Double Buffer : An improvement over single buffering can be had by assigning two system
buffers to the operation. A process now transfers data to (or from) one buffer while the
operating system empties (or fills) the other. This technique is known as double buffering or
buffer swapping.

Circular Buffer : Double buffering may be inadequate if the process performs rapid bursts of
I/O. When more than two buffers are used, the collection of buffers is itself referred to as a
circular buffer, with each individual buffer being one unit in the circular buffer. This is
simply the bounded-buffer producer/consumer model.

DISK STRUCTURE
A magnetic disk is a circular plate constructed of metal or plastic coated with magnetized
material. Several disks are stacked to a spindle one below the other with read/write head to
make a disk pack. Information’s are stored on the surface of disk along concentric set of rings
called tracks. These tracks are divided into sections called sector. A set of corresponding
tracks in all surfaces of a disk pack is called cylinder.

6
One or both sides of the disks are used and several disks may be stacked on one spindle with
read/write heads available on each surface. In such units, the address bits can select a
particular track electronically through a decoder circuit. This type of unit is expensive.

Some units are use a single read/write head for each surface. In such units, the track
address bits are used by a mechanical assembly to move the head into the specified track
position before reading or writing. During a read/write operation the head is stationary while
the platter rotates.

Physical Characteristics:

Following are the major characteristics that differentiate among the various types of magnetic
disks.

7
 1. Head Motion:
 Fixed head (one per track)
 Movable head (One per surface)

2. Disk portability:
 Non-removable disk (hard disk)
 Removable disk (floppy disk)
3. Sides:
 Single sided
 Double sided
4. Platter:
 Single platter
 Multiple platter

Working Of Disk:

When the disk drive is operating, the disk is rotating at constant speed. To read/write, the
head must be positioned at the desired track and at the beginning of the desired sector on that
track. Address bits specifies the disk number, the disk surface, the sector number and the
track within the surface. Information transfer is very fast once the beginning of a sector has
been reached.

Disk performance parameters:

 Seek Time : The time it takes to position the head at the desired track is known as
seek time.
 Rotational delay/Rotational latency : Once the track is selected, the disk controller
waits until the appropriate sector rotates to reach under the head. The time it takes for
the beginning of the sector to reach the head is known as rotational delay or rotational
latency.

8
  Access Time : The time required to reach to a desired location and obtain its contents
is called the access time, i.e; the sum of seek time and rotational delay equals to the
access time.
 Transfer Time : The time of data transfer (for read/write operation) is referred as
transfer time. The transfer time to or from the disk depends on the rotation speed of
the disk in the following way:

T = b/rN
where, T = transfer time
B = number of bytes to be transferred
r = rotation speed
N = number of bytes on a track

Thus, the total average access time,

Ta = Ts + 1/2r + b/rN

where, Ts is average seek time.

 Disk Capacity : Let s bytes are stored per sector, p sectors are there per track, t tracks
per surface and m surfaces. Then the capacity of disk will be defined as,

Disk Capacity = (m × t × p × s) bytes

If d is the diameter of the disk, the density of recording is,

Density = (p × s / π × d) bytes/inch

Question: A certain magnetic disk has the following specification:

Number of surfaces = 10, Number of tracks/surfaces = 256, Number of sectors/track =

32, Number of bytes/sector = 128, Disk rotation speed = 2400 rpm. Calculate the
following:

1. Disk Capacity
2. Transfer Rate
3. Average Latency Time.

Solution:

1. Disk capacity = Number of surfaces × Number of tracks in each surface ×

Number of sectors in a track × Number of bytes in a sector

So, Disk capacity = 10 × 256 × 32 × 128

= 10 × 220
= 10 MB

9
2. Transfer rate = Number of sectors in a track × Number of bytes in a sector
So, Transfer rate = 32 × 128
= 212 bytes
Rotation speed = 2400 rpm
2400 rotation in 1 minute. So 1 rotation in 60/2400 sec = 1/40 sec
So, in 1 second data transfer = 212 × 40 bytes
= 160 × 210 bytes
= 160 K bytes
3. Avg. Latency Time = 1/2 × Time in one rotation
= 1/2 × 1/40
= 1/80 sec.

Question: A magnetic disk system has the following parameters:

TS = Average time to position the head over a track

R = Rotation speed of disk in revolutions per second
Nt = Number of bits per track
Ns = Number of bits per sector
Calculate the average time Ta that it will take to read one sector.

Solution:

Average time (Ta) = Ts + Time for half revolution + Time to read a sector
Ta = Ts +1/2R + Ns/Nt × 1/R

Question: A disk has 19456 cylinders, 16 heads and 63 sectors/track. The disk spins
5400 rpm. Seek time between adjacent tracks is 2 ms. Assuming the read/write head is
already positioned at track 0. How long does it take to read the entire disk?

Solution: Each track can be read in 1 rotation. Rotation speed = 5400 rpm
5400 rotation in 1 minute. So 1 rotation in 60/5400 sec = 0.01111 sec
= 11.11 ms
So, 11.11 ms requires to read one track.
Total number of tracks = 19456 × 16
= 311296
So, time required to read all tracks = 311296 × 11.11
= 3458498.56 ms
= 3459 sec (approximately)
Seek time = (19456 – 1) × 2
= 38910 ms
= 39 sec (approximately)
So, total time to read entire disk = 3459 + 39
= 3498 sec

10
 DISK SCHEDULING

Whenever a process needs I/0 to or from the disk, it issues a system call to the operating
system. The request specifies several pieces of information:
 Whether this operation is input or output
 What the disk address for the transfer is
 What the memory address for the transfer is
 What the number of sectors to be transferred is
If the desired disk drive and controller are available, the request can be serviced immediately.
If the drive or controller is busy, any new requests for service will be placed in the queue of
pending requests for that drive. For a multiprogramming system with many processes, the
disk queue may often have several pending requests. Thus, when one request is completed,
the operating system chooses which pending request to service next by using the following
Disk Scheduling algorithms.
First-come, first-served (FCFS)
 process request sequentially
 fair to all processes
 approaches random scheduling in performance if there are many processes
 Consider, for example, a disk queue with requests for I/O to blocks on cylinders
98, 183, 37, 122, 14, 124, 65, 67,

Illustration shows total head movement of 640 cylinders.

11
 Shortest seek time first (SSTF)
 Selects the request with the minimum seek time from the current head
position.
 SSTF scheduling is a form of SJF scheduling; may cause starvation of some
requests.
 Consider, for example, a disk queue with requests for I/O to blocks on
cylinders 98, 183, 37, 122, 14, 124, 65, 67.

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.
 Sometimes called the elevator algorithm.
 Consider, for example, a disk queue with requests for I/O to blocks on cylinders 98,
183, 37, 122, 14, 124, 65, 67.

12
 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.

13
LOOK and C-LOOK
 Both SCAN and C-SCAN move the disk arm across the full width of the disk. In
practice neither algorithm is often implemented this way. More commonly the arm
goes only as far as the final request in each direction. Then, it reverses direction
immediately without going all the way to the end of the disk.
 Versions of SCAN and C-SCAN that follow this pattern are called LOOK and C-
LOOK.

RAID

 Redundant Array of Independent Disks

 Consists of seven levels, zero through six

14
 RAID is a set of
physical disk drives
viewed by the
operating system as
a single logical drive

Design
architectures
share three
characteristics:
redundant disk data are
capacity is used to distributed
store parity across the
information, which physical drives of
guarantees data an array in a
recoverability in case scheme known
of a disk failure as striping

RAID Level-0
 Not a true RAID because it does not include redundancy to improve performance or
provide data protection
 User and system data are distributed across all of the disks in the array
 Logical disk is divided into strips

RAID Level-1
 Redundancy is achieved by the simple expedient of duplicating all the data
 There is no “write penalty”

15
  When a drive fails the data may still be accessed from the second drive
 Principal disadvantage is the cost

RAID Level-2
 Makes use of a parallel access technique
 Data striping is used
 Typically a Hamming code is used
 Effective choice in an environment in which many disk errors occur

RAID Level-3
 Requires only a single redundant disk, no matter how large the disk array
 Employs parallel access, with data distributed in small strips
 Can achieve very high data transfer rates

16
RAID Level-4
 Makes use of an independent access technique
 A bit-by-bit parity strip is calculated across corresponding strips on each data disk,
and the parity bits are stored in the corresponding strip on the parity disk
 Involves a write penalty when an I/O write request of small size is performed

RAID Level-5
 Similar to RAID-4 but distributes the parity bits across all disks
 Typical allocation is a round-robin scheme
 Has the characteristic that the loss of any one disk does not result in data loss

RAID Level-6
 Two different parity calculations are carried out and stored in separate blocks on
different disks
 Provides extremely high data availability
 Incurs a substantial write penalty because each write affects two parity blocks

17
 Disks Large I/O data
Category Level Description Data availability Small I/O request rate
required transfer capacity
Lower than single Very high for both read
Striping 0 Nonredundant N Very high
disk and write
Higher than single Up to twice that of a
Higher than RAID
disk for read; similar single disk for read;
Mirroring 1 Mirrored 2N 2, 3, 4, or 5; lower
to single disk for similar to single disk for
than RAID 6
write write
Much higher than
Redundant via Hamming single disk; Highest of all listed Approximately twice that
2 N+m
code comparable to alternatives of a single disk
RAID 3, 4, or 5
Parallel access
Much higher than
single disk; Highest of all listed Approximately twice that
3 Bit-interleaved parity N+1
comparable to alternatives of a single disk
RAID 2, 4, or 5
Similar to RAID 0
Much higher than
for read; Similar to RAID 0 for
single disk;
4 Block-interleaved parity N+1 significantly lower read; significantly lower
comparable to
than single disk for than single disk for write
RAID 2, 3, or 5
write
Independent Much higher than
Similar to RAID 0 Similar to RAID 0 for
access Block-interleaved distributed single disk;
5 N+1 for read; lower than read; generally lower
parity comparable to
single disk for write than single disk for write
RAID 2, 3, or 4
Similar to RAID 0 Similar to RAID 0 for
Block-interleaved dual Highest of all listed
6 N+2 for read; lower than read; significantly lower
distributed parity alternatives
RAID 5 for write than RAID 5 for write

N = number of data disks; m proportional to log N

FILE SYSTEMS
• A file is a named collection of related information that is recorded on secondary storage
• File is a logical storage unit: independent of actual storage device; mapped by OS onto
physical devices

18
• Generally persistent (e.g., across power failures); nonvolatile
• Referred to by name (for convenience of human users)
• May have types (e.g., source, data, object, executable)
• A file is an abstract data object with specific attributes and operations provided by the
system
 A file has a certain defined structure which depends on its types:
 A text file is a sequence of characters organized into lines.
 A source file is a sequence of subroutines and function.
 An object file is a sequence of bytes organized into blocks understandable by
the system’s linker.
 An executable file is a series of code sections that the loader can bring into
memory and execute.
In most applications, the file is the central element. From the user’s point of view, one of the
most important parts of an operating system is the file system.
The file system provides the resource abstractions typically associated with secondary
storage.
Desirable properties include
Long-term existence: Files are stored on disk or other secondary storage and do not
disappear when a user logs off.
Sharable between processes: Files have names and can have associated access permissions
that permit controlled sharing.
Structure: Depending on the file system, a file can have an internal structure that is
convenient for particular applications. In addition, files can be organized into hierarchical or
more complex structure to reflect the relationships among files.

FILE ATTRIBUTES

• Name: symbolic name; the only information kept in human-readable form

• Type: if supported by system (more later)
• Location: pointer to device & location of the file on device
• Size: current size and perhaps the maximum allowed size
• Protection: access-control information (e.g., reading, writing, executing, etc.)
• Time, date, and user identification: e.g., creation, last modification, last use

19
• Usage count, owner, etc

FILE OPERATIONS

• Create: allocate space, enter into directory

• Write: given name and information to be written (system keeps write pointer to file)
• Read: given file name and destination of information (system keeps read pointer)
• Reposition within a file (also known as file seek)
• Delete: release space and erase from directory
• Truncate: keeps directory entry/attributes but deletes contents (resets length to 0)
• Open/close file
FILE TYPE

FILE STRUCTURE

File structure uses following four terms:

1.Field 2.Record 3.File 4.Database

A field is the basic element of data.

20
  It is characterized by its length and data type (e.g. ASCII string, decimal).
 Depending on the file design, fields may be fixed length or variable length.

A record is a collection of related fields that can be treated as a unit by some application
program.
A file is a collection of similar records.
• The file is treated as a single entity by users and applications and may be
referenced by name.
• Files have file names and may be created and deleted.
• Access control restrictions usually apply at the file level.
A database is a collection of related data.
• Explicit relationships exist among elements of data
• The database itself consists of one or more types of files.
• Usually, there is a separate database management system that is independent
of the operating system, although that system may make use of some file
management programs.

FILE MANAGEMENT SYSTEM

 Provides services to users and applications in the use of files

 The way a user or application accesses files
 Programmer does not need to develop file management software
Objectives include:
 To meet the data management needs and requirements of the user,
 To guarantee, to the extent possible, that the data in the file are valid
 To optimize performance, both from the system point of view in terms of over-all
throughput and from the user’s point of view in terms of response time
 To provide I/O support for a variety of storage device types
 To minimize or eliminate the potential for lost or destroyed data
 To provide a standardized set of I/O interface routines to user processes
 To provide I/O support for multiple users, in the case of multiple-user systems
Requirements include:
1. Each user should be able to create, delete, read, write, and modify files.

21
2. Each user may have controlled access to other users’ files.
3. Each user may control what types of accesses are allowed to the user’s files.
4. Each user should be able to restructure the user’s files in a form appropriate to the
problem.
5. Each user should be able to move data between files.
6. Each user should be able to back up and recover the user’s files in case of damage.
7. Each user should be able to access his or her files by name rather than by numeric
identifier.

FILE SYSTEM ARCHITECTURE

Device drivers communicate at the lowest level directly with peripheral devices or their
controllers or channels.
 A device driver is responsible for starting I/O operations on a device and processing
the completion of an I/O request.
 For file operations, the typical devices controlled are disk and tape drives.
 Device drivers are usually considered to be part of the operating system.
Basic file system or the physical I/O level.

22
This is the primary interface with the environment outside of the computer system.
It deals with blocks of data that are exchanged with disk or tape systems.
 It is concerned with the placement of those blocks on the secondary storage device
and on the buffering of those blocks in main memory.
 It does not understand the content of the data or the structure of the files involved.
 The basic file system is often considered part of the operating system.
Basic I/O supervisor is responsible for all file I/O initiation and termination.
Control structures are maintained that deal with
 device I/O,
 scheduling,
 file status.

The basic I/O supervisor selects the device on which file I/O is to be performed, based on the
particular file selected.
It is also concerned with scheduling disk and tape accesses to optimize performance.
 I/O buffers are assigned and secondary memory is allocated at this level.
The basic I/O supervisor is part of the operating system.
Logical I/O enables users and applications to access records.
Whereas the basic file system deals with blocks of data,
 the logical I/O module deals with file records.
Logical I/O provides a general-purpose record I/O capability
 and maintains basic data about files.
The access method is the level of the file system closest to the user.
It provides a standard interface between applications and the file systems and devices that
hold the data. Different access methods reflect different file structures and different ways of
accessing and processing the data.

23
 ELEMENTS OF FILE MANAGEMENT

Users and application programs interact with the file system by means of commands for
creating and deleting files and for performing operations on files.
Before performing any operation, the file system must identify and locate the selected file.
 This requires the use of some sort of directory that serves to describe the location of
all files, plus their attributes.
 In addition, most shared systems enforce user access control
The basic operations that a user or application may perform on a file are performed at the
record level.
 The user or application views the file as having some structure that organizes the
records, such as a sequential structure
The secondary storage must be managed.
 This involves allocating files to free blocks on secondary storage and managing free
storage so as to know what blocks are available for new files and growth in existing
files.
 In addition, individual block I/O requests must be scheduled
Disk scheduling and file allocation are both concerned with optimizing performance.
The optimization will depend on the structure of the files and the access patterns

24
 FILE ORGANIZATION
“File organization” refers to the logical structuring of the records as determined by the way in
which they are accessed.
Criteria for File Organization
Important criteria include: Short access time, Ease of update, Economy of storage, Simple
maintenance, Reliability.
Priority will differ depending on the use (e.g. read-only CD vs Hard Drive)
The relative priority of these criteria will depend on the applications that will use the file.
 e.g. if a file is only to be processed in batch mode, with all of the records accessed
every time, then rapid access for retrieval of a single record is of minimal concern.
 A file stored on CD-ROM will never be updated, and so ease of update is not an
issue.
These criteria may conflict.
 E.g. for economy of storage, there should be minimum redundancy in the data, but
redundancy is a primary means of increasing the speed of access to data (such as
indexes.)
File organizations types:
 The pile
 The sequential file
 The indexed sequential file
 The indexed file
 The direct, or hashed, file

FILE ACCESS METHODS

The Pile

25
The least-complicated form of file organization may be termed the pile.
Data are collected in the order in which they arrive.
 Each record consists of one burst of data.
The purpose of the pile is simply to accumulate the mass of data and save it.
Records may have different fields, or similar fields in different orders.
 Thus, each field should be self-describing, including a field name as well as a value.
 The length of each field must be implicitly indicated by delimiters.
Because there is no structure to the pile file, record access is by exhaustive search.
 ie , to find a record that contains a particular field with a particular value, it is
necessary to examine each record in the pile until the desired record is found or the
entire file has been searched.
 to find all records that contain a particular field or contain that field with a particular
value, then the entire file must be searched.

Sequential Access

The most common form of file structure. A fixed format is used for records.
All records are of the same length, consisting of the same number of fixed-length fields in a
particular order.
 Because the length and position of each field are known, only the values of fields
need to be stored;
 the field name and length for each field are attributes of the file structure.
The key field uniquely identifies the record;

26
  thus key values for different records are always different.
 The records are stored in key sequence: alphabetical order for a text key, and
numerical order for a numerical key.

Information in the file is processed in order, one after the other (as in magnetic tape) .

Direct Access (or relative access).

Logical records can be read/written in no particular order. read/write must include a block
number as parameter

read n
write n
position to n
read next
write next
rewrite n
n = relative block number
cp: current position

27
Indexed Files

The index contains pointers to the various blocks. To find a record in the file, we first search
the index and then use the pointer to access the file directly and to find the desired record.

Indexed Sequential File

The indexed sequential file maintains the key characteristic of the sequential file:
 records are organized in sequence based on a key field.
Two features are added:
 an index to the file to support random access,
 and an overflow file.
The index provides a lookup capability to reach quickly the vicinity of a desired record.
The overflow file is similar to the log file used with a sequential file
 but is integrated so that a record in the overflow file is located by following a pointer
from its predecessor record.

28
 DISK STRUCTURE

 Disk can be subdivided into partitions

 Disks or partitions can be redundant arrays of independent disks (RAID) protected
against failure
 Disk or partition can be used raw – without a file system, or formatted with a file
system
 Partitions also known as minidisks, slices
 Entity containing file system known as a volume
 Each volume containing file system also tracks that file system’s info in device
directory or volume table of contents

29
 FILE SYSTEM ORGANIZATION

Each volume that contains a file system must also contain information about the files in the
system. This information is kept in entries in a device directory which records name,
location, size and type.

DIRECTORY STRUCTURE

• A collection of nodes containing information about all files

• Resides on disk, along with files
Information in a device directory
• Name
• Type
• Address
• Current length
• Maximum length
• Date last accessed (for archival)
• Date last updated (for dump)
• Owner ID (who pays)
• Protection information
Directory Operations
• Search for a file
• Create a file
• Delete a file
• List a directory
• Rename a file
• Traverse the file system (e.g., for backup purposes)
Goals in (logical) directory organization

30
• Efficiency--enable locating a file quickly
• Naming--convenient to users
– Two users (or two directories) can have the same name for different files
– The same file can have several different names
• Grouping--logical grouping of files by properties (e.g., extension, date changed, etc.)
LOGICAL DIRECTORY STRUCTURES
• Single-level Directory
• Two-level Directory
• Tree-structured Directory
• Acyclic-graph Directory
• General-graph Directory
1. Single-Level Directory
• Advantage: simple to support and understand
• Disadvantage: files must have unique names (multiple users may clash; names may be
limited in length; large directories may be hard to remember)

2. Two-Level Directory
• Each user has own user file directory (UFD)
• Master file directory (MFD) holds pointers to UFDs
• Disadvantage: discourages cooperation

3. Tree-Structured Directories
• Absolute path: begins at the root and follows a path down to the specified file.
root/spell/mail/prt/first

31
 • Relative path: defines a path from the current directory. prt/first given root/spell/mail
as current path.

 Efficient searching
 Grouping Capability
•It is a Natural generalization of two-level Directories. As in MS-DOS current directory,
change directory operation
• policy decision: how to handle requests to delete a (non-empty) directory .
 Creating a new file is done in current directory
 Delete a file
rm <file-name>
 Creating a new subdirectory is done in current directory
mkdir <dir-name>
Example: if in current directory /mail
mkdir count

4. Acyclic-Graph Directories
• Add to tree-structured directories, for example, Unix ln
• permits the sharing of files and subdirectories
• the same file/subdirectory exists in the file system in two or more places at the same time

32
  New directory entry type
 Link – another name (pointer) to an existing file
 Resolve the link – follow pointer to locate the file
Acyclic-graph directory structures
• File now has multiple absolute path names (aliasing problem). Can backup avoid copying
the same file twice?
• Deletion: when can the space be reclaimed? Reference counts, for example (or dangling
links as another possible solution)
• Who gets charged for file space?
• Ensuring the absence of cycles
– Allow links to file, not subdirectories (Unix hard links)

5. General Graph Directory

• As in acyclic-graph structure but also permits cycles!
• Self-referencing files create difficulties with reference counts. Garbage collection may be
required.

33
 FILE SHARING
In a multiuser system, there is almost always a requirement for allowing files to be shared
among a number of users.
Two issues arise:
 access rights and
 the management of simultaneous access
The file system should provide a number of options so that the way in which a particular file
is accessed can be controlled.
Typically, users or groups of users are granted certain access rights to a file.
A wide range of access rights has been used.
 These rights can be considered to constitute a hierarchy, with each right implying
those that precede it.

Access Rights:
None: User may not even know of the files existence
Knowledge: User can only determine that the file exists and who its owner is
Execution: The user can load and execute a program but cannot copy it
Reading: The user can read the file for any purpose, including copying and execution
Appending: The user can add data to the file but cannot modify or delete any of the file’s
contents
Updating: The user can modify, delete, and add to the file’s data.
Changing protection: User can change access rights granted to other users
Deletion: User can delete the file
The owner has all of the access rights listed above and may grant rights to others.
Specific user: Individual users who are designated by user ID.
User groups: A set of users who are not individually defined.
The system must have some way of keeping track of the membership of user groups.
All: All users who have access to this system. These are public files.
Simultaneous Access:
User may lock entire file when it is to be updated
User may lock the individual records during the update
Mutual exclusion and deadlock are issues for shared access

34
 FILE-SYSTEM STRUCTURE
 File structure
 Logical storage unit
 Collection of related information
 File system organized into layers
 File system resides on secondary storage (disks)
 Provides efficient and convenient access to disk by allowing data to be stored,
located retrieved easily
 File control block – storage structure consisting of information about a file
 Device driver controls the physical device

In-Memory File System Structures

DIRECTORY IMPLEMENTATION
 Linear list of file names with pointer to the data blocks.
 simple to program
 time-consuming to execute
 Hash Table – linear list with hash data structure.
 decreases directory search time
 collisions – situations where two file names hash to the same location
 fixed size

35
 ALLOCATION METHODS
An allocation method refers to how disk blocks are allocated for files:
 Contiguous allocation
 Linked allocation
 Indexed allocation

Contiguous Allocation of Disk Space

• Each file occupies a set of contiguous blocks on the disk
• Simple – only starting location (block #) and length (number of blocks) are required
• Random access
• This is a pre-allocation strategy, using variable-size portions.
• Contiguous allocation is the 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.
• Wasteful of space (dynamic storage-allocation problem). External fragmentation will
occur, making it difficult to find contiguous blocks of space of sufficient length.
• From time to time, it will be necessary to perform a compaction algorithm to free up
additional space on the disk.
• Also, with pre-allocation, it is necessary to declare the size of the file at the time of
creation
Files cannot grow

36
LINKED ALLOCATION
 Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk.
 Typically, allocation is on an individual block basis.
 Each block contains a pointer to the next block in the chain.
 The file allocation 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.
 The selection of blocks is now a simple matter: any free block can be added to a
chain.
 There is no external fragmentation to worry about because only one block at a time is
needed.
 To select an individual block of a file requires tracing through the chain to the desired
block.
 Free-space management system – no waste of space
 No random access

File-allocation table (FAT) – disk-space allocation used by MS-DOS and OS/2.

Each block is indexed by block number

37
INDEXED ALLOCATION
 Brings all pointers together into the index block
 Logical view

• Need index table

• Random access
• Dynamic access without external fragmentation, but have overhead of index block

38
 

Bit map requires extra space

 Example:
block size = 212 bytes
disk size = 230 bytes (1 gigabyte)
n = 230/212 = 218 bits (or 32K bytes)
 Easy to get contiguous files
 Linked list (free list)
 Cannot get contiguous space easily
 No waste of space

LINKED FREE SPACE LIST ON DISK

39
GROUPING: Grouping the used space together.

PROTECTION and SECURITY MECHANISMS

• Simple protection by access right lists
– read
– write
– execute
– append
– delete
– list
Access lists and groups
• Mode of access: read, write, execute
• Classes of users
– Owner
– Group (membership carefully controlled)
– Public / Universe
An Access Control Matrix or Access Matrix is an abstract, formal security model of
protection state in computer systems, that characterizes the rights of each subject with respect
to every object in the system. An access matrix can be envisioned as a rectangular array of
cells, with one row per subject and one column per object. The entry in a cell - that is, the
entry for a particular subject-object pair - indicates the access mode that the subject is
permitted to exercise on the object. Each column is equivalent to an access control list for the
object; and each row is equivalent to an access profile for the subject
In this matrix example there exists two processes, a file and a device. The first process has
the ability to execute the second, read the file and write some information to the device, while
the second process can only send information to the first.

Asset 1 Asset 2 file device

Role 1 read, write, execute, own execute read write

Role 2 read read, write, execute, own

40