MODULE 4

Prototypical System Architecture

The picture shows a single CPU attached to the main memory of the system via some kind of memory bus
or interconnect. Some devices are connected to the system via a general I/O bus, which in many modern
systems would be PCI (or one of its many derivatives); graphics and some other higher-performance I/O
devices might be found here. Finally, even lower down are one or more of what we call a peripheral bus,
such as SCSI, SATA, or USB. These connect slow devices to the system, including disks, mice, and
keyboards.

Modern System Architecture

modern systems increasingly use specialized chipsets and faster point-to-point interconnects to
improve performance. Figure 36.2 (page 3) shows an approximate diagram of Intel’s Z270 Chipset [H17].
Along the top, the CPU connects most closely to the memory system, but also has a high-performance
connection to the graphics card (and thus, the display) to enable gaming (oh, the horror!) and other
graphicsintensive applications. The CPU connects to an I/O chip via Intel’s proprietary DMI (Direct Media
Interface), and the rest of the devices connect to this chip via a number of different interconnects. On the
right, one or more hard drives connect to the system via the eSATA interface; ATA (the AT Attachment, in
reference to providing connection to the IBM PC AT), then SATA (for Serial ATA), and now eSATA (for
external SATA) represent an evolution of storage interfaces over the past decades, with each step forward
increasing performance to keep pace with modern storage devices. Below the I/O chip are a number of
USB (Universal Serial Bus) connections, which in this depiction enable a keyboard and mouse to be
attached to the computer. On many modern systems, USB is used for low performance devices such as
these. Finally, on the left, other higher performance devices can be connected to the system via PCIe
(Peripheral Component Interconnect Express). In this diagram, a network interface is attached to the
system here; higher performance storage devices (such as NVMe persistent storage devices) are often
connected here.
Simple Device Model
• Block devices store a set of numbered blocks (disks)
• Character devices produce/consume stream of bytes (keyboard)
• Devices expose an interface of memory registers
– Current status of device
– Command to execute
– Data to transfer
• The internals of device are usually hidden

In the picture above, the (simplified) device interface is comprised of three registers: a status register,
which can be read to see the current status of the device; a command register, to tell the device to perform
a certain task; and a data register to pass data to the device, or get data from the device. By reading and
writing these registers, the operating system can control device behavior. Let us now describe a typical
interaction that the OS might have with the device in order to get the device to do something on its behalf.
The protocol is as follows:
The protocol has four steps. In the first, the OS waits until the device is ready to receive a command by
repeatedly reading the status register; we call this polling the device (basically, just asking it what is going
on). Second, the OS sends some data down to the data register; one can imagine that if this were a disk, for
example, that multiple writes would need to take place to transfer a disk block (say 4KB) to the device.
When the main CPU is involved with the data movement (as in this example protocol), we refer to it as
programmed I/O (PIO). Third, the OS writes a command to the command register; doing so implicitly
lets the device know that both the data is present and that it should begin working on the command.
Finally, the OS waits for the device to finish by again polling it in a loop, waiting to see if it is finished (it
may then get an error code to indicate success or failure).

Interrupts

• Polling wastes CPU cycles

• Instead, OS can put process to sleep and switch to another process

When I/O request completes, device raises interrupt, OS can switch back to original process after that
request has completed
• Note: context switch to original process need not be immediate

Interrupt handler

• Interrupt from I/O device causes trap, switches process to kernel mode
• Interrupt Descriptor Table (IDT) stores pointers (value of PC) to OS interrupt handlers (interrupt service
routines)
• Interrupt (IRQ) number identifies the interrupt handler to run for a device
• Interrupt handler processes notification from device, unblocks the process waiting for I/O (if any), and
starts next I/O request (if any pending)
• Handling interrupts imposes kernel mode transition overheads
• Note: polling may be faster than interrupts if device is fast

Direct Memory Access (DMA)

• In spite of interrupts, CPU cycles wasted in copying data to/from device

Instead, a special piece of hardware (DMA engine) copies from main memory to device and vice versa,
without involving CPU
• CPU gives DMA engine the memory location of data
• In case of disk read, device copies data via DMA to RAM and then raises interrupt
• In case of write, device copies data via DMA from RAM and then starts writing

Summary of disk read with interrupt + DMA

• Process P1 makes read system call to read data from disk

• OS gives command to disk via command register
• OS switches to another process P2 (P1 cannot run anymore, blocked)
• Disk completes reading data, copies data into main memory directly via DMA, then raises interrupt
• OS handles interrupts, disk data is ready, marks P1 as ready to run
• Interrupt handled in the kernel mode of P2
• OS scheduler switches back to P1 at a later time

I/O stack in the kernel

• Device driver: part of OS code that talks to specific device, gives commands, handles interrupts etc.
• Rest of OS code abstracts out the device-specific details
• I/O subsystems (file system / networking) built as layers: system calls, block read/write, device drivers
that communicates with I/O device

The diagram also shows a raw interface to devices, which enables special applications (such as a file-
system checker, described later [AD14], or a disk defragmentation tool) to directly read and write blocks
without using the file abstraction. Most systems provide this type of interface to support these low-level
storage management applications.
Storage Management
This session gives an overview of the physical structure of secondary and tertiary
storage devices.

Magnetic Disks

 Magnetic disks provide the bulk of secondary storage for modern computer
systems. Conceptually, disks are relatively simple each disk platter has a flat
circular shape, like a CD. Common platter diameters range from1.8 to 3.5 inches.
The two surfaces of a platter are covered with a magnetic material. We store
information by recording it magnetically on the platters.
 A read–write head “flies” just above each surface of every platter. The heads are
attached to a disk arm that moves all the heads as a unit. The surface of a platter
is logically divided into circular tracks, which are subdivided into sectors. The
set of tracks that are at one arm position makes up a cylinder. There may be
thousands of concentric cylinders in a disk drive, and each track may contain
hundreds of sectors. The storage capacity of common disk drives is measured in
gigabytes.
 When the disk is in use, a drive motor spins it at high speed. Most drives rotate
60 to 250 times per second, specified in terms of rotations per minute (RPM).
Disk speed has two parts. The transfer rate is the rate at which data flow between
the drive and the computer. The positioning time, or random-access time,
consists of two parts: the time necessary to move the disk arm to the desired
cylinder, called the seek time, and the time necessary for the desired sector to
rotate to the disk head, called the rotational latency.
  A disk drive is attached to a computer by a set of wires called an I/O bus.
Several kinds of buses are available, including advanced technology attachment
(ATA), serial ATA (SATA), e-SATA, universal serial bus (USB), and fiber
channel (FC). The data transfers on a bus are carried out by special electronic
processors called controllers.

Disk Structure
 Modern magnetic disk drives are addressed as large one-dimensional arrays of
logical blocks, where the logical block is the smallest unit of transfer. The size of a
logical block is usually 512 bytes, although some disks can be low-level formatted
to have a different logical block size, such as 1,024 bytes.

 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. By using this mapping, we an—at least in theory—
convert a logical block number into an old-style disk address that consists of a
cylinder number, a track number within that cylinder, and a sector number
within that track.
 In practice it is difficult to perform this translation because of the following
reasons
1. most disks have some defective sectors, but the mapping hides this by
substituting spare sectors from elsewhere on the disk.
 2. Second, the number of sectors per track is not a constant on some
drives.
 Arranging tracks in different manner , which includes

1. Constant Linear Velocity (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.
2. Constant Angular Velocity (CAV): Tracks in the outermost zone
typically hold 40 percent more sectors than tracks in the innermost
zone. The drive increases its rotation speed as the head moves from the
outer to the inner tracks to keep the same rate of data moving under
the head. This method is used in CD-ROM and DVD-ROM drives.
Alternatively, the disk rotation speed can stay constant; in this case,
the density of bits decreases from inner tracks to outer tracks to keep
the data rate constant. This method is used in hard disks and is known
as constant angular velocity (CAV).
 The number of sectors per track has been increasing as disk technology
improves, and the outer zone of a disk usually has several hundred sectors per
track. Similarly, the number of cylinders per disk has been increasing; large disks
have tens of thousands of cylinders.

Disk Scheduling
 The seek time is the time for the disk arm to move the heads to the cylinder
containing the desired sector.
 The rotational latency is the additional time for the disk to rotate the desired
sector to the disk head.
 The 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.
 We can improve both the access time and the bandwidth by managing the order
in which disk I/O requests are serviced.
 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. The operating
system makes this choice by any one of several disk-schedulingalgorithms.

FCFS Scheduling

 It is the simplest of the scheduling algorithms. Consider, for example, a disk

queue with requests for I/O to blocks on cylinder in that order.
 98, 183, 37, 122, 14, 124, 65, 67

 If the disk head is initially at cylinder 53, it will first move from 53 to 98, then to
183, 37, 122, 14, 124, 65, and finally to 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. If the requests for cylinders 37 and 14 could be serviced together,
before or after the requests for 122 and 124, the total head movement could be
decreased substantially, and performance could be thereby improved

SSTF Scheduling

 It seems reasonable to service all the requests close to the current head position
before moving the head far away to service other requests. This assumption is
the basis for the shortest-seek-time-first (SSTF) algorithm. The SSTF algorithm
selects the request with the least seek time from the current head position. In
other words, SSTF chooses the pending request closest to the current head
position.
 For our example request queue, the closest request to the initial head position
(53) is at cylinder 65. Once we are at cylinder 65, the next closest request is at
cylinder 67. From there, the request at cylinder 37 is closer than the one at 98, so
37 is served next. Continuing, we service the request at cylinder 14, thn 98, 122,
124, and finally 183 (Figure 10.5). This scheduling method results in a total head
movement of only 236 cylinders—little more than one-third of the distance
needed for FCFS scheduling of this request queue. Clearly, this algorithm gives a
substantial improvement in performance
 This scheduling algorithm has the disadvantages of starvation.
 Although it is not optimal ie.. In the example, we can do better by moving the
head from 53 to 37, even though the latter is not closest, and then to 14, before
turning around to service 65, 67, 98, 122, 124, and 183. This strategy reduces the
total head movement to 208 cylinders.

SCAN Scheduling

 In the SCAN algorithm, the disk arm starts at one end of the disk and moves
toward the other end, servicing requests as it reaches each cylinder, until it gets
to the other end of the disk.
 At the other end, the direction of head movement is reversed, and servicing
continues. The head continuously scans back and forth across the disk.
 The SCAN algorithm is sometimes called the elevator algorithm, since the disk
arm behaves just like an elevator in a building, first servicing all the requests
going up and then reversing to service requests the other way.

Example: 98, 183, 37, 122, 14, 124, 65, 67

 Before applying SCAN to schedule the requests on cylinders 98, 183, 37, 122, 14,
124, 65, and 67, we need to know the direction of head movement in addition to
the head’s current position.
 Assuming that the disk arm is moving toward 0 and that the initial head position
is again 53, the head will next service 37 and then 14.

 At cylinder 0, the arm will reverse and will move toward the other end of the
disk, servicing the requests at 65, 67, 98, 122, 124, and 183.
 If a request arrives in the queue just in front of the head, it will be serviced
almost immediately; a request arriving just behind the head will have to wait
until the arm moves to the end of the disk, reverses direction, and comes back.

C-SCAN Scheduling

 Circular SCAN (C-SCAN) scheduling is a variant of SCAN designed to provide a

more uniform wait time. Like SCAN, C-SCAN moves the head from one end of
the disk to the other, servicing requests along the way. When the head reaches
the other end, however, it immediately returns to the beginning of the disk
without servicing any requests on the return trip. The C-SCAN scheduling
algorithm essentially treats the cylinders as a circular list that wraps around from
the final cylinder to the first one
LOOK and C-LOOK Scheduling

 As we described them, 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 scheduling, because they look for a request before continuing to move in a
given direction
 Examples

[Link]
m
[Link]
m
[Link]
m
[Link]
m
[Link]
m
Disk Formatting

 A new magnetic disk is a blank slate: it is just a platter of a magnetic recording material.
Before a disk can store data, it must be divided into sectors that the disk controller can read
and write. This process is called low-level formatting,or physical formatting.
 Low-level formatting fills the disk with a special data structure for each sector. 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 the sector is read, the ECC is
recalculated and compared with the stored value. If the stored and calculated numbers are
different, the data area of the sector has become corrupted and that the disk sector may be
bad.
 The ECC is an error-correcting code. If only a few bits of data have been corrupted, ECC
enable the controller to identify which bits have been changed and calculate what their
correct values should be.
 It then reports a recoverable soft error. The controller automatically does the ECC
processing whenever a sector is read or written.
 For many hard disks, when the disk controller is instructed to low-level-format the disk, it
can also be told how many bytes of data space to leave between the header and trailer of
all sectors.
 It is usually possible to choose among a few 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.
 Some operating systems can handle only a sector size of 512 bytes.
 The first step 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.
 The second step is logical formatting, or creation of a file system. In this step, the
operating system stores the initial file-system data structures onto the disk.
 To increase efficiency, most file systems group blocks together into larger chunks,
frequently called clusters.
 Some operating systems give special programs the ability to use a disk partition as a
large sequential array of logical blocks, without any file-system data structures.
File System

• An organization of files and directories on disk

• An OS can implement one or more file systems
• Disks expose a set of blocks (usually 512 bytes)
• File system organizes files onto blocks
• System calls translated into reads and writes on blocks
• We will study the following concepts about file systems
• The file abstraction and system call API exposed to users
• Data structures to organize data and metadata on disk and memory
• Implementation of system calls like open, read, write using the data structures

File abstraction
• File: sequence of bytes, stored persistently on disk

• Directory: container for files and other sub-directories

• Steps to access a file
• Open a file using system call, get a file descriptor
• File descriptor is a handle to refer to file for read/write
• Close file when done accessing it
• Filesystem: OS subsystem that stores files and directories persistently
on secondary storage like hard disks
• File-related system calls are exposed to users to access files
Directory tree
• Files and directories arranged in a tree, starting with root (“/”)

Reading and writing a file

• After opening a file, process can read/write to a file as a stream
• File descriptor used as handle to refer to the open file stream
• Read system call reads specified number of bytes into a user-defined buffer,returns number of bytes read
• Write system call writes specified number of bytes from a user-defined buffer,returns number of bytes
written
• Read and write system calls update the offset into a file
• After reading N bytes, next read will return the next set of bytes
• Can also update the offset from which to read/write using a seek system call
• Every open file descriptor will read/write file as independent stream, with independent offsets

Sockets, pipes, …

• Opening sockets and pipes also returns file descriptor

• Serves as a handle for stream of data from socket or pipe
• Every process has array of file descriptors
• One file descriptor for every open file / socket / pipe
• First 3 entries are streams for stdin, stdout, stderr
• Several I/O streams handled via file-like interfaces (everything is a
file!)
Operations on directories

• Every file is identified by a unique inode number in filesystem

• Directory is a special file that contains mappings between filenames and
inode number of the file
• Directories can also be accessed like files, e.g., create, open, read, close
• For example, the “ls” program opens and reads all directory entries
• Directory entry contains file name, inode number, type of file (file/directory) etc

Hard links
• Hard linking creates another file that points to the same inode number (and hence,
same underlying data)
• If one file deleted, file data can be accessed through the other links
• Inode maintains a link count, file data deleted only when no further links to it
• You can only unlink, OS decides when to delete

Soft links or symbolic links

• Soft link is a file that simply stores a pointer to another filename

If the main file is deleted, then the link points to an invalid entry:
dangling reference

Mounting a file system

• Mounting a file system connects the files to a specific point in the

directory tree

Several devices and file systems are mounted on a typical machine, accessed with mount command
 File Concepts

➢ A file is a named collection of related information that is recorded on secondary

storage.
➢ files represent programs and data.
➢ The information in a file is defined by its creator.
➢ A file has a certain defined structure which depends on its type.
○ text file, source file, executable file

File Attributes

➢ A file is referred to by its name.

➢ A file's attributes vary from one operating system to another but typically consist
of these:

o Name: The symbolic file name is the only information kept in human readable
form.
o Identifier: This unique tag, usually a number, identifies the file within the file
system; it is the non-human-readable name for thefile.
o Type: This information is needed for systems that support different types of files.
o Location: This information is a pointer to a device and to the location of the file
on that device.
o Size: The current size of the file (in bytes, words, or blocks) and possibly the
maximum allowed size are included in this attribute.
o Protection: Access-control information determines who can do reading, writing,
executing, and so on.
o Time, date, and user identification: This information may be kept for creation,
last modification, and last use. These data can be useful for protection, security,
and usage monitoring.

File Operations

➢ A file is an abstract data type.

➢ To define a file properly, it needs to consider the operations that can be
performed on files.
Creating a file:Two steps are necessary to create a file. First, space in the
file system must be found for thefile.
Writing a file: To write a file, we make a system call specifying both the
Name of the file and the information to be written to the file. The system must
 keep a write pointer to the location in the file where the next write is to take
place.
o Reading a file: To read from a file, we use a system call that specifies the name of

the file and where (in memory) the next block of the file should be put.
o Repositioning within a file. The directory is searched for the appropriate
entry, and the current-file-position pointer is repositioned to a given value
(seek).
o Deleting a file. To delete a file, we search the directory for the named file.
Having found the associated directory entry, we release all file space, so that it
can be reused by other files, and erase the directoryentry.
o Truncating a file. The user may want to erase the contents of a file but keep
its attributes.
➢ Other common operations include
○ Appending, renaming and copy
○ Several pieces of information are associated with an open file.
○ File pointer.
○ File-open count.
○ Disk location of the file.
○ Access rights

File Types

➢ The operating system should recognize and support file types. If an operating
system recognizes the type of a file, it can then operate on the file in reasonable
ways.

➢ The system uses the extension to indicate the type of the file and the type of
operations that can be done on that file.

File Structure
 ➢ File types can be used to indicate the internal structure of the file.
➢ The operating requires that an executable file have a specific structure so that it can system
termine where in memory to load the file and what the location of

➢ None - sequence of words, bytes

➢ Simple record structure
○ Lines
○ Fixed length
○ Variable length
➢ Complex Structures
○ Formatted document
○ Relocatable load file
➢ Can simulate last two with first method by inserting appropriate control
characters

Internal File Structure

➢ Internally, locating an offset within a file can be complicated for the operating
system.
➢ Disk systems typically have a well-defined block size determined by the size of a
sector.
➢ All disk I/0 is performed in units of one block (physical record), and all blocks
are the same size.
➢ It is unlikely that the physical record size will exactly match the length of the
desired logical record. Logical records may even vary in length. Packing a
number of logical records into physical blocks is a common solution to this
problem.

Access Methods

➢ Files store information.

➢ When it is used, this information must be accessed and read into computer
memory.
➢ The information in the file can be accessed in several ways.
➢ Some systems provide only one access method for files while others provide
many access methods.
➢ A major design problem is choosing one among them.

1. Sequential Access

➢ Information in the file is processed in order, one record after the other.
 ➢ Sequential Access file operations
○ read_next() - Read next portion of file and automatically advances a file
pointer.
○ write_next() – Appends to the end of the file and advances to the end of
the newly written material.
○ Reset – Back to the beginning of file
○ no read after last write

2. Direct Access (Relative Accesses)

➢ A file is made up of fixed length logical records, that allow programs to read
and write records rapidly in no particular order.
➢ For direct access disk is viewed as numbered sequence of blocks or record.

➢ Direct access file operations

○ The file operations were modified to include the block number as a
parameter.
○ Read(n)
○ Write(n)
○ Position_file(n)
n = relative block number
3. Other Access Methods

➢ Can be built on top of basemethods

➢ General involve creation of an index for the file
➢ Keep index in memory for fast determination of location of data to be operated on
(consider UPC code plus record of data about thatitem)
➢ If too large, index (in memory) of the index (on disk)
➢ To find a record, we first search the index and then use pointer to access the file
directly and to find desired record.

TU
STUDENT

Example of index and relative files.

 Protection
➢ When information is stored in a computer system, it must be keep safe from
physical damage (the issue of reliability) and improper access (the issue of
protection).
➢ Reliability is generally provided by duplicate copies of files.
➢ Protection can be provided in many ways.
○ Types of Access
○ Access Control
➢ Other Protection Approaches

Types of Access
➢ Access is permitted or denied depending on several factors, one of which is the
type of access requested.
➢ Several different types of operations may becontrolled:
○ Read: Read from the file.
○ Write: Write or rewrite thefile.
○ Execute: Load the file into memory and execute it.
○ Append: Write new information at the end of the file.
○ Delete: Delete the file and free its space for possible reuse.
○ List: List the name and attributes of the file.

Access Control
➢ The most common approach to the protection problem is to make access
dependent on the identity of the user.
➢ Different users may need different types of access to a file or directory.
➢ To implement dependent access is to associate with each file and directory an
access control list (ACL)specifying user names and the types of access allowed
for each user.
➢ Mode of access: read, write, execute
➢ Many systems recognize three classifications of users in connection with each
file:
○ Owner: The user who created the file is the owner.
○ Group: A set of users who are sharing the file and need similar access is a group,
or work group.
○ Universe: All other users in the system constitute the universe.
File-System Implementation
 Several on-disk and in-memory structures are used to implement a file system.
 The file system may contain information about how to boot an operating system
 stored there, the total number of blocks, the number and location of free blocks, the
directory structure, and individual files.
 Boot control block contains info needed by system to boot OS from that volume

○ Needed if volume contains OS, usually first block of volume

 Volume control block (superblock, master file table) contains volume details
Total number of blocks, number of free blocks, blocks size, free blocks pointers
or array
 Directory structure organizes the files

○ Names and inode numbers, master file table

 Per-file File Control Block (FCB) contains many details about the file

○ inode number, permissions, size, dates

○ NFTS stores into in master file table using relational DB structures

A typical file-control block.

 The in-memory information is used for both file-system management and
performance improvement via caching.
 The data are loaded at mount time, updated during file-system operations, and
discarded at dismount.
 Several types of structures may be included.
○ An in-memory mount table contains information about each mounted volume.
○ An in-memory directory-structure cache holds the directory information of
recently accessed directories.
○ The system wide open file table contains a copy of the FCB of each open file, as
well as other information.
○ The per process open file table contains a pointer to the appropriate entry in the
system-wide open-file table, as well as other information.
○ Buffers hold file-system blocks when they are being read from disk or written to disk.
Partitions and Mounting

 Partition can be a volume containing a file system (“cooked”) or raw – just a

sequence of blocks with no file system
 Boot block can point to boot volume or boot loader set of blocks that contain
enough code to know how to load the kernel from the file system
○ Or a boot management program for multi-os booting
  Root partition contains the OS, other partitions can hold other Oses, other file
systems, or be raw
○ Mounted at boot time
○ Other partitions can mount automatically or manually
 At mount time, file system consistency checked
○ Is all metadata correct?
■ If not, fix it, try again
■ If yes, add to mount table, allow access

Virtual File Systems

 Virtual File Systems (VFS) on Unix provide an object-oriented way of
implementing file systems
 VFS allows the same system call interface (the API) to be used for different types
of file systems
○ Separates file-system generic operations from implementation details
○ Implementation can be one of many file systems types, or network file
system
■ Implements vnodes which hold inodes or network file details
○ Then dispatches operation to appropriate file system implementation
routines

Schematic view of a virtual file system.

Directory Implementation
➢ The selection of directory-allocation and directory-management
algorithms significantly affects the efficiency, performance, and
reliability of the file system

Linear List

➢ The simplest method of implementing a directory is to use a linear list of

file names with pointers to the data blocks.
➢ This method is simple to program but time-consuming toexecute.
➢ The real disadvantage of a linear list of directory entries is that finding a
file requires a linear search.

Hash Table

➢ With this method, a linear list stores the directory entries, but a hash
data structure is also used. The hash table takes a value computed from
the file name and returns a pointer to the file name in the linear list.
➢ Therefore, it can greatly decrease the directory search time.
➢ Insertion and deletion are also fairly straightforward, although some
provision must be made for collisions-situations in which two file names
hash to the same location.
➢ The major difficulties with a hash table are its generally fixed size and the
dependence of the hash function on that size.
➢ a chained-overflow hash table can be used.
➢ Each hash entry can be a linked list instead of an individual value, and
we can resolve collisions by adding the new entry to the linked list.
Allocation Methods
➢ An allocation method refers to how disk blocks are allocated
for files.

Contiguous Allocation
➢ requires that each file occupy a set of contiguous blocks on disk.
➢ Disk addresses define a linear ordering on the disk.
➢ Best performance in most cases
➢ Simple – only starting location (block number) and length (number of
blocks) are required
➢ Problems include finding space for file, knowing file size, external
fragmentation, need for compaction off-line (downtime) or on-
line

Linked Allocation

➢ With linked allocation, each file is a linked list of disk blocks; the
disk blocks may be scattered anywhere on the disk.
➢ The directory points to the first and last blocks of the file.
➢ File ends at nil pointer
➢ No external fragmentation
➢ Each block contains pointer to next block
➢ No compaction, external fragmentation
➢ Free space management system called when new block needed
➢ Improve efficiency by clustering blocks into groups but increases
internal fragmentation
➢ Reliability can be a problem
➢ Locating a block can take many I/Os and disk seeks
 Linked allocation
Indexed allocation
 Linked allocation solves the external-fragmentation and size-
declaration problems of contiguous allocation.
 Indexed allocation solves this problem by bringing all the pointers
together into one location: the index block.

 Each file has its own index block, which is an array of disk-block
addresses. The ith entry in the index block points to the ith block of the
file.
 The directory contains the address of the index block. To find and read
the ith block, we use the pointer in the ith index-block entry.
 When the file is created, all pointers in the index block are set to null.
When the ith block is first written, a block is obtained from the free-
space manager, and its address is put in the ith index-block entry.
 Indexed allocation supports direct access, without suffering from
external fragmentation, because any free block on the disk can satisfy
a request for more space. Indexed allocation does suffer from wasted
space, however.