UNIT-IV

Memory Management: Swapping, Contiguous Memory Allocation, Segmentation, Paging, Structure of

Page Table

As a result of CPU scheduling, we can improve both the utilization of the CPU and the speed of the computer’s
response to its users. To realize this increase in performance, however, we must keep several processes in
memory—that is, we must share memory. We discuss various ways to manage memory.

Background:
Memory is central to the operation of a modern computer system. Memory consists of a large array of bytes,
each with its own address. The CPU fetches instructions from memory according to the value of the program
counter. These instructions may cause additional loading from and storing to specific memory addresses.

Basic Hardware
Main memory and the registers built into the processor itself are the only general-purpose storage that the
CPU can access directly. If the data are not in memory, they must be moved there before the CPU can operate
on them.

Registers that are built into the CPU are generally accessible within one cycle of the CPU clock. Most CPUs
can decode instructions and perform simple operations on register contents at the rate of one or more
operations per clock tick

Completing a memory access may take many cycles of the CPU clock. In such cases, the processor normally
needs to stall, since it does not have the data required to complete the instruction that it is executing. The
remedy is to add fast memory between the CPU and main memory, typically on the CPU chip for fast access.

For proper system operation we must protect the operating system from access by user processes. This
protection must be provided by the hardware because the operating system doesn’t usually intervene between
the CPU and its memory accesses.

We can provide this protection by using two registers, usually a base and a limit, as illustrated in below Figure.
The base register holds the smallest legal physical memory address; the limit register specifies the size of
the range. For example, if the base register holds 300040 and the limit register is 120900, then the program
can legally access all addresses from 300040 through 420939 (inclusive).

Figure: A base and a limit register define a logical addresss space

Protection of memory space is accomplished by having the CPU hardware compare every address generated
in user mode with the registers. Any attempt by a program executing in user mode to access operating- system
memory or other users’ memory results in a trap to the operating system, which treats the attempt as a fatal
error(below figure)

Figure: Hardware address protection with base and limit registers

The operating system, executing in kernel mode, is given unrestricted access to both operating-system
memory and users’ memory.

Address Binding
• User programs typically refer to memory addresses with symbolic names such as "i", "count", and
"average Temperature". These symbolic names must be mapped or bound to physical memory
addresses, which typically occurs in several stages:
o Compile Time - If it is known at compile time where a program will reside in physical memory,
then absolute code can be generated by the compiler, containing actual physical addresses.
However if the load address changes at some later time, then the program will have to be
recompiled. DOS .COM programs use compile time binding. o Load Time - If the location at
which a program will be loaded is not known at compile time, then the compiler must generate
relocatable code, which references addresses relative to the start of the program. If that starting
address changes, then the program must be reloaded but not recompiled.
o Execution Time - If a program can be moved around in memory during the course of its
execution, then binding must be delayed until execution time. This requires special hardware, and
is the method implemented by most modern OSes. Figure shows the various stages of the binding
processes and the units involved in each stage:
 Figure- Multistep processing of a user
program Logical Versus Physical Address
Space

• The address generated by the CPU is a logical address, whereas the address actually seen by the
memory hardware is a physical address.
• Addresses bound at compile time or load time have identical logical and physical addresses.
• Addresses created at execution time, however, have different logical and physical addresses.
o In this case the logical address is also known as a virtual address, and the two terms are used
interchangeably by our text.
o The set of all logical addresses used by a program composes the logical address space, and the
set of all corresponding physical addresses composes the physical address space.
• The run time mapping of logical to physical addresses is handled by the memory-management unit,
MMU.
o The MMU can take on many forms. One of the simplest is a modification of the base-register
scheme described earlier. o The base register is now termed a relocation register, whose value is
added to every memory request at the hardware level.
• Note that user programs never see physical addresses. User programs work entirely in logical address
space, and any memory references or manipulations are done using purely logical addresses. Only
when the address gets sent to the physical memory chips is the physical memory address generated.

Figure- Dynamic relocation using a relocation register

Dynamic Loading
Rather than loading an entire program into memory at once, dynamic loading loads up each routine as
it is called. The advantage is that unused routines need never be loaded, reducing total memory usage
and generating faster program startup times. The downside is the added complexity and overhead of
checking to see if a routine is loaded every time it is called and then then loading it up if it is not
already loaded.

Dynamic Linking and Shared Libraries

• With static linking library modules get fully included in executable modules, wasting both disk space
and main memory usage, because every program that included a certain routine from the library would
have to have their own copy of that routine linked into their executable code.
• With dynamic linking, however, only a stub is linked into the executable module, containing
references to the actual library module linked in at run time.

o This method saves disk space, because the library routines do not need to be fully included in
the executable modules, only the stubs. o We will also learn that if the code section of the
library routines is reentrant, ( meaning it does not modify the code while it runs, making it
safe to re-enter it ), then main memory can be saved by loading only one copy of dynamically
linked routines into memory and sharing the code amongst all processes that are concurrently
using it.
o An added benefit of dynamically linked libraries ( DLLs, also known as shared libraries
or shared objects on UNIX systems ) involves easy upgrades and updates.
o In practice, the first time a program calls a DLL routine, the stub will recognize the fact and
will replace itself with the actual routine from the DLL library.

Swapping
• A process must be loaded into memory in order to execute.
• If there is not enough memory available to keep all running processes in memory at the same time,
then some processes who are not currently using the CPU may have their memory swapped out to a
fast local disk called the backing store.

Standard Swapping
• If compile-time or load-time address binding is used, then processes must be swapped back into the
same memory location from which they were swapped out. If execution time binding is used, then the
processes can be swapped back into any available location.
• Swapping is a very slow process compared to other operations. For example, if a user process occupied
10 MB and the transfer rate for the backing store were 40 MB per second, then it would take 1/4
second ( 250 milliseconds ) just to do the data transfer. Adding in a latency lag of 8 milliseconds and
ignoring head seek time for the moment, and further recognizing that swapping involves moving old
data out as well as new data in, the overall transfer time required for this swap is 512 milliseconds, or
over half a second.
• To reduce swapping transfer overhead, it is desired to transfer as little information as possible, which
requires that the system know how much memory a process is using, as opposed to how much it might
use. Programmers can help with this by freeing up dynamic memory that they are no longer using.
 • It is important to swap processes out of memory only when they are idle, or more to the point, only
when there are no pending I/O operations. ( Otherwise the pending I/O operation could write into the
wrong process's memory space. ) The solution is to either swap only totally idle processes, or do I/O
operations only into and out of OS buffers, which are then transferred to or from process's main
memory as a second step.

Figure - Swapping of two processes using a disk as a backing store

Most modern OSes no longer use swapping, because it is too slow and there are faster alternatives
available. ( e.g. Paging. ) However some UNIX systems will still invoke swapping if the system gets
extremely full, and then discontinue swapping when the load reduces again.

Swapping on Mobile Systems

• Swapping is typically not supported on mobile platforms, for several reasons:

o Mobile devices typically use flash memory in place of more spacious hard drives for
persistent storage, so there is not as much space available.
o Flash memory can only be written to a limited number of times before it becomes unreliable.
o The bandwidth to flash memory is also lower.
• Apple's IOS asks applications to voluntarily free up memory o Read-only data, e.g.
code, is simply removed, and reloaded later if needed. o Modified data, e.g. the stack, is
never removed, but . . .
o Apps that fail to free up sufficient memory can be removed by the OS Android follows a
similar strategy. o Prior to terminating a process, Android writes its application state to
flash memory for quick restarting.

Contiguous Memory Allocation

One approach to memory management is to load each process into a contiguous space. The operating
system is allocated space first, usually at either low or high memory locations, and then the remaining
available memory is allocated to processes as needed. ( The OS is usually loaded low, because that is
where the interrupt vectors are located, but on older systems part of the OS was loaded high to make
more room in low memory ( within the 640K barrier ) for user process

Memory Protection
The system shown in Figure below allows protection against user programs accessing areas that they
should not, allows programs to be relocated to different memory starting addresses as needed, and
allows the memory space devoted to the OS to grow or shrink dynamically as needs change.
 Figure-Hardware support for relocation and limit registers

Memory Allocation
• One method of allocating contiguous memory is to divide all available memory into equal sized
partitions, and to assign each process to their own partition.
• An alternate approach is to keep a list of unused ( free ) memory blocks ( holes ), and to find a hole of
a suitable size whenever a process needs to be loaded into memory. There are many different strategies
for finding the "best" allocation of memory to processes, including the three most commonly
discussed:
1. First fit - Search the list of holes until one is found that is big enough to satisfy the request, and
assign a portion of that hole to that process. Whatever fraction of the hole not needed by the
request is left on the free list as a smaller hole. Subsequent requests may start looking either from
the beginning of the list or from the point at which this search ended.
2. Best fit - Allocate the smallest hole that is big enough to satisfy the request. This saves large holes
for other process requests that may need them later, but the resulting unused portions of holes
may be too small to be of any use, and will therefore be wasted. Keeping the free list sorted can
speed up the process of finding the right hole.
3. Worst fit - Allocate the largest hole available, thereby increasing the likelihood that the remaining
portion will be usable for satisfying future requests.
• Simulations show that either first or best fit are better than worst fit in terms of both time and storage
utilization. First and best fits are about equal in terms of storage utilization, but first fit is faster.

Fragmentation
• All the memory allocation strategies suffer from external fragmentation, though first and best fits
experience the problems more so than worst fit. External fragmentation means that the available
memory is broken up into lots of little pieces, none of which is big enough to satisfy the next memory
requirement, although the sum total could.
• The amount of memory lost to fragmentation may vary with algorithm, usage patterns, and some design
decisions such as which end of a hole to allocate and which end to save on the free list.
• Statistical analysis of first fit, for example, shows that for N blocks of allocated memory, another 0.5
N will be lost to fragmentation.
• Internal fragmentation also occurs, with all memory allocation strategies. This is caused by the fact
that memory is allocated in blocks of a fixed size, whereas the actual memory needed will rarely be
that exact size. For a random distribution of memory requests, on the average 1/2 block will be wasted
per memory request, because on the average the last allocated block will be only half full.
 o Note that the same effect happens with hard drives, and that modern hardware gives us
increasingly larger drives and memory at the expense of ever larger block sizes, which
translates to more memory lost to internal fragmentation.
o Some systems use variable size blocks to minimize losses due to internal fragmentation.
• If the programs in memory are relocatable, ( using execution-time address binding ), then the external
fragmentation problem can be reduced via compaction, i.e. moving all processes down to one end of
physical memory. This only involves updating the relocation register for each process, as all internal
work is done using logical addresses.
• Another solution as we will see in upcoming sections is to allow processes to use non-contiguous
blocks of physical memory, with a separate relocation register for each block.

Paging

• Paging is a memory management scheme that allows processes physical memory to be discontinuous,
and which eliminates problems with fragmentation by allocating memory in equal sized blocks known
as pages.
• Paging eliminates most of the problems of the other methods discussed previously, and is the
predominant memory management technique used today.

Basic Method
• The basic idea behind paging is to divide physical memory into a number of equal sized blocks called
frames, and to divide a programs logical memory space into blocks of the same size called pages.
• Any page ( from any process ) can be placed into any available frame.
• The page table is used to look up what frame a particular page is stored in at the moment. In the
following example, for instance, page 2 of the program's logical memory is currently stored in frame
3 of physical memory:

Figure - Paging hardware

 Figure - Paging model of logical and physical memory

• A logical address consists of two parts: A page number in which the address resides, and an offset
from the beginning of that page. ( The number of bits in the page number limits how many pages a
single process can address. The number of bits in the offset determines the maximum size of each
page, and should correspond to the system frame size. )
• The page table maps the page number to a frame number, to yield a physical address which also has
two parts: The frame number and the offset within that frame. The number of bits in the frame number
determines how many frames the system can address, and the number of bits in the offset determines
the size of each frame.
• Page numbers, frame numbers, and frame sizes are determined by the architecture, but are typically
powers of two, allowing addresses to be split at a certain number of bits. For example, if the logical
address size is 2m and the page size is 2n, then the high-order m-n bits of a logical address designate
the page number and the remaining n bits represent the offset.

• Consider the following micro example, in which a process has 16 bytes of logical memory, mapped
in 4 byte pages into 32 bytes of physical memory.
 Figure - Paging example for a 32-byte memory with 4-byte pages

• There is no external fragmentation with paging. All blocks of physical memory are used, and there
are no gaps in between and no problems with finding the right sized hole for a particular chunk of
memory.
• There is, however, internal fragmentation. Memory is allocated in chunks the size of a page, and on
the average, the last page will only be half full, wasting on the average half a page of memory per
process.
• Larger page sizes waste more memory, but are more efficient in terms of overhead. Page table entries
( frame numbers ) are typically 32 bit numbers, allowing access to 232 physical page frames. If those
frames are 4 KB in size each, that translates to 16 TB of addressable physical memory. ( 32 + 12 = 44
bits of physical address space. )
• When a process requests memory ( e.g. when its code is loaded in from disk ), free frames are allocated
from a free-frame list, and inserted into that process's page table.

• The operating system must keep track of each individual process's page table, updating it whenever
the process's pages get moved in and out of memory, and applying the correct page table when
processing system calls for a particular process. This all increases the overhead involved when
swapping processes in and out of the CPU.

Figure - Free frames (a) before allocation and (b) after allocation
Hardware Support
• Page lookups must be done for every memory reference, and whenever a process gets swapped in or
out of the CPU, its page table must be swapped in and out too, along with the instruction registers, etc.
It is therefore appropriate to provide hardware support for this operation, in order to make it as fast as
possible and to make process switches as fast as possible also.
• One option is to use a set of registers for the page table. For example, the DEC PDP-11 uses 16-bit
addressing and 8 KB pages, resulting in only 8 pages per process. ( It takes 13 bits to address 8 KB of
offset, leaving only 3 bits to define a page number. )
• An alternate option is to store the page table in main memory, and to use a single register ( called the
page-table base register, PTBR ) to record where in memory the page table is located.
o Process switching is fast, because only the single register needs to be changed.
o However memory access just got half as fast, because every memory access now requires two
memory accesses - One to fetch the frame number from memory and then another one to access
the desired memory location.
o The solution to this problem is to use a very special high-speed memory device called the
translation look-aside buffer, TLB.

Figure - Paging hardware with TLB

▪ The benefit of the TLB is that it can search an entire table for a key value in parallel, and if it is found
anywhere in the table, then the corresponding lookup value is returned.
▪ The TLB is very expensive, however, and therefore very small. It is therefore used as a cache device.
▪ Addresses are first checked against the TLB, and if the info is not there ( a TLB miss ), then the frame
is looked up from main memory and the TLB is updated.
▪ If the TLB is full, then replacement strategies range from least-recently used, LRU to random.
▪ Some TLBs allow some entries to be wired down, which means that they cannot be removed from the
TLB. Typically these would be kernel frames.
▪ Some TLBs store address-space identifiers, ASIDs, to keep track of which process "owns" a particular
entry in the TLB. This allows entries from multiple processes to be stored simultaneously in the TLB
without granting one process access to some other process's memory location. Without this feature the
TLB has to be flushed clean with every process switch.
▪ The percentage of time that the desired information is found in the TLB is termed the hit ratio.
▪ For example, suppose that it takes 100 nanoseconds to access main memory, and only 20 nanoseconds
to search the TLB. So a TLB hit takes 120 nanoseconds total ( 20 to find the frame number and then
another 100 to go get the data ), and a TLB miss takes 220 ( 20 to search the TLB, 100 to go get the
 frame number, and then another 100 to go get the data. ) So with an 80% TLB hit ratio, the average
memory access time would be:

0.80 * 120 + 0.20 * 220 = 140 nanoseconds

for a 40% slowdown to get the frame number. A 98% hit rate would yield 122 nanoseconds average
access time ( you should verify this ), for a 22% slowdown.

▪ The ninth edition ignores the 20 nanoseconds required to search the TLB, yielding

0.80 * 100 + 0.20 * 200 = 120 nanoseconds

for a 20% slowdown to get the frame number. A 99% hit rate would yield 101 nanoseconds average
access time ( you should verify this ), for a 1% slowdown.

Protection
• The page table can also help to protect processes from accessing memory that they shouldn't, or their
own memory in ways that they shouldn't.
• A bit or bits can be added to the page table to classify a page as read-write, read-only, read-write-
execute, or some combination of these sorts of things. Then each memory reference can be checked
to ensure it is accessing the memory in the appropriate mode.
• Valid / invalid bits can be added to "mask off" entries in the page table that are not in use by the current
process, as shown by example in Figure below.
• Note that the valid / invalid bits described above cannot block all illegal memory accesses, due to the
internal fragmentation. ( Areas of memory in the last page that are not entirely filled by the process,
and may contain data left over by whoever used that frame last. )
• Many processes do not use all of the page table available to them, particularly in modern systems with
very large potential page tables. Rather than waste memory by creating a full-size page table for every
process, some systems use a page-table length register, PTLR, to specify the length of the page table.
 Figure - Valid (v) or invalid (i) bit in page table

Shared Pages
• Paging systems can make it very easy to share blocks of memory, by simply duplicating page numbers
in multiple page frames. This may be done with either code or data.
• If code is re-entrant or pure code that means that it does not write to or change the code in any way (
it is non self-modifying ), and it is therefore safe to re-enter it. More importantly, it means the code
can be shared by multiple processes, so long as each has their own copy of the data and registers,
including the instruction register.
• In the example given below, three different users are running the editor simultaneously, but the code
is only loaded into memory ( in the page frames ) one time.

Figure - Sharing of code in a paging environment

Structure of the Page Table

Hierarchical Paging

• Most modern computer systems support logical address spaces of 232 to 264.
• With a 232 address space and 4K ( 212 ) page sizes, this leave 220 entries in the page table. At 4 bytes per
entry, this amounts to a 4 MB page table, which is too large to reasonably keep in contiguous memory.
( And to swap in and out of memory with each process switch. ) Note that with 4K pages, this would
take 1024 pages just to hold the page table!
• One option is to use a two-tier paging system, i.e. to page the page table.
• For example, the 20 bits described above could be broken down into two 10-bit page numbers. The first
identifies an entry in the outer page table, which identifies where in memory to find one page of an
inner page table. The second 10 bits finds a specific entry in that inner page table, which in turn
identifies a particular frame in physical memory. ( The remaining 12 bits of the 32 bit logical address
are the offset within the 4K frame. )

Figure- A two-level page-table scheme

 Figure - Address translation for a two-level 32-bit paging architecture

• VAX Architecture divides 32-bit addresses into 4 equal sized sections, and each page is 512 bytes,
yielding an address form of:

• With a 64-bit logical address space and 4K pages, there are 52 bits worth of page numbers, which is
still too many even for two-level paging. One could increase the paging level, but with 10-bit page
tables it would take 7 levels of indirection, which would be prohibitively slow memory access. So some
other approach must be used.

64-bits Two-tiered leaves 42 bits in outer table

Going to a fourth level still leaves 32 bits in the outer table.

The 64-bit UltraSPARC would require seven levels of paging—a prohibitive number of memory
accesses—to translate each logical address.

Hashed Page Tables

A common approach for handling address spaces larger than 32 bits is to use a hashed page table,
with the hash value being the virtual page number. Each entry in the hash table contains a linked list of
elements that hash to the same location (to handle collisions). Each element consists of three fields:

(1) the virtual page number,

(2) the value of the mapped page frame, and
(3) a pointer to the next element in the linked list.

The algorithm works as follows: The virtual page number in the virtual address is hashed into the hash table.
The virtual page number is compared with field 1 in the first element in the linked list. If there is a match, the
corresponding page frame (field 2) is used to form the desired physical address. If there is no match,
subsequent entries in the linked list are searched for a matching virtual page number. This scheme is shown
in Figure.

A variation of this scheme that is useful for 64-bit address spaces has been proposed. This variation uses
clustered page tables, which are similar to hashed page tables except that each entry in the hash table refers
to several pages (such as 16) rather than a single page. Therefore, a single page-table entry can store the
mappings for multiple physical-page frames. Clustered page tables are particularly useful for sparse address
spaces, where memory references are noncontiguous and scattered throughout the address space.

Figure - Hashed page table

Inverted Page Tables

Page tables may consume large amounts of physical memory just to keep track of how other physical memory
is being used. To solve this problem, we can use an inverted page table. An inverted page table has one entry
for each real page (or frame) of memory. Each entry consists of the virtual address of the page stored in that
real memory location, with information about the process that owns the page. Thus, only one page table is in
the system, and it has only one entry for each page of physical memory. Figure shows the operation of an
inverted page table.

Figure - Inverted page table

Inverted page tables often require that an address-space identifier be stored in each entry of the page table,
since the table usually contains several different address spaces mapping physical memory.

Storing the address-space identifier ensures that a logical page for a particular process is mapped to the
corresponding physical page frame. Examples of systems using inverted page tables include the 64-bit
UltraSPARC and PowerPC.

A simplified version of the inverted page table used in the IBM RT. For the IBM RT, each virtual address in
the system consists of a triple:
<process-id, page-number, offset>.
Each inverted page-table entry is a pair <process-id, page-number> where the process-id assumes the role of
the address-space identifier. When a memory reference occurs, part of the virtual address, consisting of
<process-id, page number>, is presented to the memory subsystem. The inverted page table is then searched
for a match. If a match is found—say, at entry i—then the physical address <i, offset> is generated. If no
match is found, then an illegal address access has been attempted.
address access has been attempted.

Although this scheme decreases the amount of memory needed to store each page table, it increases the
amount of time needed to search the table when a page reference occurs. Because the inverted page table is
sorted by physical address, but lookups occur on virtual addresses, the whole table might need to be searched
before a match is found. This search would take far too long. To alleviate this problem, we use a hash table,
to limit the search to one—or at most a few—page-table entries.

Virtual Memory: Demand Paging, Page Replacement, Allocation of Frames, Thrashing, Memory Mapped
Files, Allocating kernel memory

Background
• Preceding sections talked about how to avoid memory fragmentation by breaking process memory
requirements down into smaller bites ( pages ), and storing the pages non-contiguously in memory.
However the entire process still had to be stored in memory somewhere.
• In practice, most real processes do not need all their pages, or at least not all at once, for several
reasons:
1. Error handling code is not needed unless that specific error occurs, some of which are quite
rare.
2. Arrays are often over-sized for worst-case scenarios, and only a small fraction of the arrays
are actually used in practice.
3. Certain features of certain programs are rarely used, such as the routine to balance the federal
budget. :-)
• The ability to load only the portions of processes that were actually needed ( and only when they were
needed ) has several benefits:
o Programs could be written for a much larger address space ( virtual memory space ) than
physically exists on the computer.
o Because each process is only using a fraction of their total address space, there is more memory
left for other programs, improving CPU utilization and system throughput.
o Less I/O is needed for swapping processes in and out of RAM, speeding things up.
• Figure shows the general layout of virtual memory, which can be much larger than physical memory:
 Figure - Diagram showing virtual memory that is larger than physical memory

• The following figure shows virtual address space, which is the programmers logical view of process
memory storage. The actual physical layout is controlled by the process's page table.
• Note that the address space shown in Figure below is sparse - A great hole in the middle of the address
space is never used, unless the stack and/or the heap grow to fill the hole.

Figure - Virtual address space

Virtual memory also allows the sharing of files and memory by multiple processes, with several benefits:
o System libraries can be shared by mapping them into the virtual address space of more than
one process. o Processes can also share virtual memory by mapping the same block of memory
to more than one process.
o Process pages can be shared during a fork( ) system call, eliminating the need to copy all of
the pages of the original ( parent ) process.
 Figure - Shared library using virtual memory

Demand Paging

The basic idea behind demand paging is that when a process is swapped in, its pages are not swapped
in all at once. Rather they are swapped in only when the process needs them. ( on demand. ) This is
termed a lazy swapper, although a pager is a more accurate term.

Figure - Transfer of a paged memory to contiguous disk space

Basic Concepts
• The basic idea behind paging is that when a process is swapped in, the pager only loads into memory
those pages that it expects the process to need ( right away. )
• Pages that are not loaded into memory are marked as invalid in the page table, using the invalid bit.
• If the process only ever accesses pages that are loaded in memory ( memory resident pages ), then the
process runs exactly as if all the pages were loaded in to memory.

Figure - Page table when some pages are not in main memory.

• On the other hand, if a page is needed that was not originally loaded up, then a page fault trap is
generated, which must be handled in a series of steps:
1. The memory address requested is first checked, to make sure it was a valid memory request.

2. If the reference was invalid, the process is terminated. Otherwise, the page must be paged in.
3. A free frame is located, possibly from a free-frame list.
4. A disk operation is scheduled to bring in the necessary page from disk. ( This will usually
block the process on an I/O wait, allowing some other process to use the CPU in the meantime.
)
5. When the I/O operation is complete, the process's page table is updated with the new frame
number, and the invalid bit is changed to indicate that this is now a valid page reference.
6. The instruction that caused the page fault must now be restarted from the beginning, ( as soon
as this process gets another turn on the CPU. )
 Figure - Steps in handling a page fault

• In an extreme case, NO pages are swapped in for a process until they are requested by page faults.
This is known as pure demand paging.
• In theory each instruction could generate multiple page faults. In practice this is very rare, due to
locality of reference.
• The hardware necessary to support virtual memory is the same as for paging and swapping: A page
table and secondary memory.
• A crucial part of the process is that the instruction must be restarted from scratch once the desired page
has been made available in memory.
• Obviously there is some slowdown and performance hit whenever a page fault occurs and the system
has to go get it from memory, but just how big a hit is it exactly?
• There are many steps that occur when servicing a page fault ( see book for full details ), and some of
the steps are optional or variable. But just for the sake of discussion, suppose that a normal memory
access requires 200 nanoseconds, and that servicing a page fault takes 8 milliseconds. ( 8,000,000
nanoseconds, or 40,000 times a normal memory access. ) With a page fault rate of p, ( on a scale from
0 to 1 ), the effective access time is now:

( 1 - p ) * ( 200 ) + p * 8000000

= 200 + 7,999,800 * p

which clearly depends heavily on p! Even if only one access in 1000 causes a page fault, the effective access
time drops from 200 nanoseconds to 8.2 microseconds, a slowdown of a factor of 40 times. In order to keep
the slowdown less than 10%, the page fault rate must be less than 0.0000025, or one in 399,990 accesses.
Page Replacement

• In order to make the most use of virtual memory, we load several processes into memory at the same
time. Since we only load the pages that are actually needed by each process at any given time, there
is room to load many more processes than if we had to load in the entire process.
• However memory is also needed for other purposes ( such as I/O buffering ), and what happens if
some process suddenly decides it needs more pages and there aren't any free frames available? There
are several possible solutions to consider:
1. Adjust the memory used by I/O buffering, etc., to free up some frames for user processes. The
decision of how to allocate memory for I/O versus user processes is a complex one, yielding
different policies on different systems.
2. Put the process requesting more pages into a wait queue until some free frames become
available.
3. Swap some process out of memory completely, freeing up its page frames.
4. Find some page in memory that isn't being used right now, and swap that page only out to disk,
freeing up a frame that can be allocated to the process requesting it. This is known as page
replacement, and is the most common solution. There are many different algorithms for page
replacement, which is the subject of the remainder of this section.

Figure - Ned for page replacement.

Basic Page Replacement
• The previously discussed page-fault processing assumed that there would be free frames available on
the free-frame list. Now the page-fault handling must be modified to free up a frame if necessary, as
follows:

1. Find the location of the desired page on the disk, either in swap space or in the file system.
2. Find a free frame:
a. If there is a free frame, use it.
b. If there is no free frame, use a page-replacement algorithm to select an existing frame
to be replaced, known as the victim frame.
c. Write the victim frame to disk. Change all related page tables to indicate that this page
is no longer in memory.
3. Read in the desired page and store it in the frame. Adjust all related page and frame tables to
indicate the change. 4. Restart the process that was waiting for this page.

Figure - Page replacement.

• Note that step 3c adds an extra disk write to the page-fault handling, effectively doubling the time
required to process a page fault. This can be alleviated somewhat by assigning a modify bit, or dirty
bit to each page, indicating whether or not it has been changed since it was last loaded in from disk.
If the dirty bit has not been set, then the page is unchanged, and does not need to be written out to
disk. Otherwise the page write is required
• There are two major requirements to implement a successful demand paging system. We must develop
a frame-allocation algorithm and a page-replacement algorithm. The former centers around how
many frames are allocated to each process ( and to other needs ), and the latter deals with how to select
a page for replacement when there are no free frames available.
• The overall goal in selecting and tuning these algorithms is to generate the fewest number of overall
page faults. Because disk access is so slow relative to memory access, even slight improvements to
these algorithms can yield large improvements in overall system performance.
• Algorithms are evaluated using a given string of memory accesses known as a reference string,
which can be generated in one of ( at least ) three common ways:
 1. Randomly generated, either evenly distributed or with some distribution curve based on
observed system behavior. This is the fastest and easiest approach, but may not reflect real
performance well, as it ignores locality of reference.
2. Specifically designed sequences. These are useful for illustrating the properties of comparative
algorithms in published papers and textbooks, ( and also for homework and exam problems. :-
))
3. Recorded memory references from a live system. This may be the best approach, but the
amount of data collected can be enormous, on the order of a million addresses per second. The
volume of collected data can be reduced by making two important observations:
1. Only the page number that was accessed is relevant. The offset within that page does
not affect paging operations.
2. Successive accesses within the same page can be treated as a single page request,
because all requests after the first are guaranteed to be page hits. ( Since there are no
intervening requests for other pages that could remove this page from the page table. )
▪ So for example, if pages were of size 100 bytes, then the sequence of address requests (
0100, 0432, 0101, 0612, 0634, 0688, 0132, 0038, 0420 ) would reduce to page requests
( 1, 4, 1, 6, 1, 0, 4 )
• As the number of available frames increases, the number of page faults should decrease, as shown in
Figure :

Figure - Graph of page faults versus number of frames.

FIFO Page Replacement

• A simple and obvious page replacement strategy is FIFO, i.e. first-in-first-out.
• As new pages are brought in, they are added to the tail of a queue, and the page at the head of the
queue is the next victim. In the following example, 20 page requests result in 15 page faults:

Figure - FIFO page-replacement algorithm.

 • Although FIFO is simple and easy, it is not always optimal, or even efficient.
• An interesting effect that can occur with FIFO is Belady's anomaly, in which increasing the number
of frames available can actually increase the number of page faults that occur! Consider, for example,
the following chart based on the page sequence ( 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ) and a varying number
of available frames. Obviously the maximum number of faults is 12 ( every request generates a fault
), and the minimum number is 5 ( each page loaded only once ), but in between there are some
interesting results:

Figure - Page-fault curve for FIFO replacement on a reference string.

Optimal Page Replacement

• The discovery of Belady's anomaly lead to the search for an optimal page-replacement algorithm,
which is simply that which yields the lowest of all possible page-faults, and which does not suffer
from Belady's anomaly.
• Such an algorithm does exist, and is called OPT or MIN. This algorithm is simply "Replace the page
that will not be used for the longest time in the future."
• For example, the below figure shows that by applying OPT to the same reference string used for the
FIFO example, the minimum number of possible page faults is 9. Since 6 of the page-faults are
unavoidable ( the first reference to each new page ), FIFO can be shown to require 3 times as many (
extra ) page faults as the optimal algorithm.
• Unfortunately OPT cannot be implemented in practice, because it requires foretelling the future, but
it makes a nice benchmark for the comparison and evaluation of real proposed new algorithms.

Figure - Optimal page-replacement algorithm

LRU Page Replacement

• The prediction behind LRU, the Least Recently Used, algorithm is that the page that has not been used
in the longest time is the one that will not be used again in the near future. ( Note the distinction
 between FIFO and LRU: The former looks at the oldest load time, and the latter looks at the oldest
use time. )

• Some view LRU as analogous to OPT, except looking backwards in time instead of forwards. ( OPT
has the interesting property that for any reference string S and its reverse R, OPT will generate the
same number of page faults for S and for R. It turns out that LRU has this same property. )
• Figure illustrates LRU for our sample string, yielding 12 page faults, ( as compared to 15 for FIFO
and 9 for OPT. )

Figure - LRU page-replacement algorithm.

• LRU is considered a good replacement policy, and is often used. The problem is how exactly to
implement it. There are two simple approaches commonly used:
1. Counters. Every memory access increments a counter, and the current value of this counter is
stored in the page table entry for that page. Then finding the LRU page involves simple
searching the table for the page with the smallest counter value. Note that overflowing of the
counter must be considered.
2. Stack. Another approach is to use a stack, and whenever a page is accessed, pull that page
from the middle of the stack and place it on the top. The LRU page will always be at the bottom
of the stack. Because this requires removing objects from the middle of the stack, a doubly
linked list is the recommended data structure.
• Neither LRU or OPT exhibit Belady's anomaly. Both belong to a class of page-replacement algorithms
called stack algorithms, which can never exhibit Belady's anomaly.

Figure - Use of a stack to record the most recent page references.

LRU-Approximation Page Replacement
• Unfortunately full implementation of LRU requires hardware support, and few systems provide the
full hardware support necessary.
• However many systems offer some degree of HW support, enough to approximate LRU fairly well.
• In particular, many systems provide a reference bit for every entry in a page table, which is set anytime
that page is accessed. Initially all bits are set to zero, and they can also all be cleared at any time. One
bit of precision is enough to distinguish pages that have been accessed since the last clear from those
that have not, but does not provide any finer grain of detail.

Additional-Reference-Bits Algorithm
• Finer grain is possible by storing the most recent 8 reference bits for each page in an 8-bit byte in the
page table entry, which is interpreted as an unsigned int.
o At periodic intervals ( clock interrupts ), the OS takes over, and right-shifts each of the reference
bytes by one bit. o The high-order ( leftmost ) bit is then filled in with the current value of the
reference bit, and the reference bits are cleared.
o At any given time, the page with the smallest value for the reference byte is the LRU page.
• Obviously the specific number of bits used and the frequency with which the reference byte is updated
are adjustable, and are tuned to give the fastest performance on a given hardware platform.

Second-Chance Algorithm
The second chance algorithm is essentially a FIFO, except the reference bit is used to give pages a
second chance at staying in the page table.
o When a page must be replaced, the page table is scanned in a FIFO ( circular queue ) manner.
o If a page is found with its reference bit not set, then that page is selected as the next
victim.
o If, however, the next page in the FIFO does have its reference bit set, then it is given a second
chance:
▪ The reference bit is cleared, and the FIFO search continues.
▪ If some other page is found that did not have its reference bit set, then that page will
be selected as the victim, and this page ( the one being given the second chance ) will
be allowed to stay in the page table.
▪ If , however, there are no other pages that do not have their reference bit set, then this
page will be selected as the victim when the FIFO search circles back around to this
page on the second pass.
 Figure - Second-chance ( clock ) page-replacement algEnhanced Second-Chance Algorithm

The enhanced second chance algorithm looks at the reference bit and the modify bit ( dirty bit ) as
an ordered page, and classifies pages into one of four classes:

1. ( 0, 0 ) - Neither recently used nor modified.

2. ( 0, 1 ) - Not recently used, but modified.
3. ( 1, 0 ) - Recently used, but clean.
4. ( 1, 1 ) - Recently used and modified.
• This algorithm searches the page table in a circular fashion ( in as many as four passes ), looking for
the first page it can find in the lowest numbered category. I.e. it first makes a pass looking for a ( 0, 0
), and then if it can't find one, it makes another pass looking for a ( 0, 1 ), etc.
• The main difference between this algorithm and the previous one is the preference for replacing clean
pages if possible.

Counting-Based Page Replacement

• There are several algorithms based on counting the number of references that have been made to a
given page, such as:
o Least Frequently Used, LFU: Replace the page with the lowest reference count. A problem
can occur if a page is used frequently initially and then not used any more, as the reference
count remains high. A solution to this problem is to right-shift the counters periodically,
yielding a time-decaying average reference count.
o Most Frequently Used, MFU: Replace the page with the highest reference count. The logic
behind this idea is that pages that have already been referenced a lot have been in the system
a long time, and we are probably done with them, whereas pages referenced only a few times
have only recently been loaded, and we still need them.
• In general counting-based algorithms are not commonly used, as their implementation is expensive
and they do not approximate OPT well.

Page-Buffering Algorithms
• There are a number of page-buffering algorithms that can be used in conjunction with the afore-
mentioned algorithms, to improve overall performance and sometimes make up for inherent
weaknesses in the hardware and/or the underlying page-replacement algorithms:
• Maintain a certain minimum number of free frames at all times. When a page-fault occurs, go ahead
and allocate one of the free frames from the free list first, to get the requesting process up and running
again as quickly as possible, and then select a victim page to write to disk and free up a frame as a
second step.
 • Keep a list of modified pages, and when the I/O system is otherwise idle, have it write these pages out
to disk, and then clear the modify bits, thereby increasing the chance of finding a "clean" page for the
next potential victim.
• Keep a pool of free frames, but remember what page was in it before it was made free. Since the data
in the page is not actually cleared out when the page is freed, it can be made an active page again
without having to load in any new data from disk. This is useful when an algorithm mistakenly replaces
a page that in fact is needed again soon.

Applications and Page Replacement

• Some applications ( most notably database programs ) understand their data accessing and caching
needs better than the general-purpose OS, and should therefore be given reign to do their own memory
management.

• Sometimes such programs are given a raw disk partition to work with, containing raw data blocks and
no file system structure. It is then up to the application to use this disk partition as extended memory
or for whatever other reasons it sees fit.

Allocation of Frames

We said earlier that there were two important tasks in virtual memory management: a page-replacement
strategy and a frame-allocation strategy. This section covers the second part of that pair.

Minimum Number of Frames

• The absolute minimum number of frames that a process must be allocated is dependent on system
architecture, and corresponds to the worst-case scenario of the number of pages that could be touched
by a single ( machine ) instruction.
• If an instruction ( and its operands ) spans a page boundary, then multiple pages could be needed just
for the instruction fetch.
• Memory references in an instruction touch more pages, and if those memory locations can span page
boundaries, then multiple pages could be needed for operand access also.
• The worst case involves indirect addressing, particularly where multiple levels of indirect addressing
are allowed. Left unchecked, a pointer to a pointer to a pointer to a pointer to a . . . could theoretically
touch every page in the virtual address space in a single machine instruction, requiring every virtual
page be loaded into physical memory simultaneously.

Allocation Algorithms
• Equal Allocation - If there are m frames available and n processes to share them, each process gets
m / n frames, and the leftovers are kept in a free-frame buffer pool.
• Proportional Allocation - Allocate the frames proportionally to the size of the process, relative to the
total size of all processes. So if the size of process i is si, and S is the sum of all si, then the allocation
for process Pi is ai = m * si / S.
• Variations on proportional allocation could consider priority of process rather than just their size.
• Obviously all allocations fluctuate over time as the number of available free frames, m, fluctuates, and
all are also subject to the constraints of minimum allocation. ( If the minimum allocations cannot be
met, then processes must either be swapped out or not allowed to start until more free frames become
available. )
Global versus Local Allocation
• One big question is whether frame allocation ( page replacement ) occurs on a local or global level.
• With local replacement, the number of pages allocated to a process is fixed, and page replacement
occurs only amongst the pages allocated to this process.
• With global replacement, any page may be a potential victim, whether it currently belongs to the
process seeking a free frame or not.
• Local page replacement allows processes to better control their own page fault rates, and leads to more
consistent performance of a given process over different system load levels. Global page
replacement is overall more efficient, and is the more commonly used approach.

Non-Uniform Memory Access

The above arguments all assume that all memory is equivalent, or at least has equivalent access times.

• This may not be the case in multiple-processor systems, especially where each CPU is physically
located on a separate circuit board which also holds some portion of the overall system memory.
• In these latter systems, CPUs can access memory that is physically located on the same board much
faster than the memory on the other boards.
• The basic solution is akin to processor affinity - At the same time that we try to schedule processes on
the same CPU to minimize cache misses, we also try to allocate memory for those processes on the
same boards, to minimize access times.
• The presence of threads complicates the picture, especially when the threads get loaded onto different
processors. Solaris uses an lgroup as a solution, in a hierarchical fashion based on relative latency.

Thrashing

• If a process cannot maintain its minimum required number of frames, then it must be swapped out,
freeing up frames for other processes. This is an intermediate level of CPU scheduling.
• But what about a process that can keep its minimum, but cannot keep all of the frames that it is
currently using on a regular basis? In this case it is forced to page out pages that it will need again in
the very near future, leading to large numbers of page faults. A process that is spending more time
paging than executing is said to be thrashing.

Cause of Thrashing
• Early process scheduling schemes would control the level of multiprogramming allowed based on
CPU utilization, adding in more processes when CPU utilization was low.
• The problem is that when memory filled up and processes started spending lots of time waiting for
their pages to page in, then CPU utilization would lower, causing the schedule to add in even more
processes and exacerbating the problem! Eventually the system would essentially grind to a halt.
• Local page replacement policies can prevent one thrashing process from taking pages away from other
processes, but it still tends to clog up the I/O queue, thereby slowing down any other process that
needs to do even a little bit of paging ( or any other I/O for that matter. )
 Figure - Thrashing

• To prevent thrashing we must provide processes with as many frames as they really need "right now",
but how do we know what that is?
• The locality model notes that processes typically access memory references in a given
locality, making lots of references to the same general area of memory before moving periodically to
a new locality, as shown in Figure 9.19 below. If we could just keep as many frames

as are involved in the current locality, then page faulting would occur primarily on switches from one
locality to another. ( E.g. when one function exits and another is called. )

Figure - Locality in a memory-reference pattern.

 Working-Set Model
• The working set model is based on the concept of locality, and defines a working set window, of length
delta. Whatever pages are included in the most recent delta page references are said to be in the
processes working set window, and comprise its current working set, as illustrated in Figure:

Figure - Working-set model.

• The selection of delta is critical to the success of the working set model - If it is too small then it does
not encompass all of the pages of the current locality, and if it is too large, then it encompasses pages
that are no longer being frequently accessed.
• The total demand, D, is the sum of the sizes of the working sets for all processes. If D exceeds the
total number of available frames, then at least one process is thrashing, because there are not enough
frames available to satisfy its minimum working set. If D is significantly less than the currently
available frames, then additional processes can be launched.
• The hard part of the working-set model is keeping track of what pages are in the current working set,
since every reference adds one to the set and removes one older page. An approximation can be made
using reference bits and a timer that goes off after a set interval of memory references:

Page-Fault Frequency
A more direct approach is to recognize that what we really want to control is the page-fault rate, and to
allocate frames based on this directly measurable value. If the page-fault rate exceeds a certain upper
bound then that process needs more frames, and if it is below a given lower bound, then it can afford
to give up some of its frames to other processes.

Figure - Page-fault frequency.

COPY ON WRITE:

Copy on Write or simply COW is a resource management technique. One of its main use is in the
implementation of the fork system call in which it shares the virtual memory(pages) of the OS.
In UNIX like OS, fork() system call creates a duplicate process of the parent process which is called as the
child process.
The idea behind a copy-on-write is that when a parent process creates a child process then both of these
processes initially will share the same pages in memory and these shared pages will be marked as copy-on-
write which means that if any of these processes will try to modify the shared pages then only a copy of these
pages will be created and the modifications will be done on the copy of pages by that process and thus not
affecting the other process.
Suppose, there is a process P that creates a new process Q and then process P modifies page 3.
The below figures shows what happens before and after process P modifies page 3.

STORAGE MANAGEMENT

Overview of Mass-Storage Structure

1. Magnetic disks

• Magnetic disks provide the bulk of secondary storage for modern computer systems

• Each disk platter has a flat circular shape, like a CD

• Common platter diameters range from 1.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

• The storage capacity of common disk drives is measured in gigabytes.

• 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 fibre channel (FC)

• The data transfers on a bus are carried out by special electronic processors called disk
controllers

2. Solid-State Disks
• SSDs use memory technology as a small fast hard disk.

• Specific implementations may use either flash memory or DRAM chips protected by
a battery to sustain the information through power cycles

• Because SSDs have no moving parts they are much faster than traditional hard drives,
and certain problems such as the scheduling of disk accesses simply do not apply

• However SSDs also have their weaknesses: They are more expensive than hard drives,
generally not as large, and may have shorter life spans

• SSDs are especially useful as a high-speed cache of hard-disk information that must
be accessed quickly

3. Magnetic Tapes
• Magnetic tapes were once used for common secondary storage before the days of hard
disk drives, but today are used primarily for backups
 • Accessing a particular spot on a magnetic tape can be slow, but once reading or writing
commences, access speeds are comparable to disk drives

• Capacities of tape drives can range from 20 to 200 GB, and compression can double that
capacity

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 lowlevel
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

• The 1-dimensional array of logical blocks is mapped into the sectors of the disk
sequentially o Sector 0 is the first sector of the first track on the outermost cylinder

o 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

o outermost to innermost

Disk Scheduling
• The operating system is responsible for using hardware efficiently — for the disk drives,
this means having a fast access time and disk bandwidth.

• 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

• Whenever a process needs I/O 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

• Several algorithms exist to schedule the servicing of disk I/O requests.

Disk Scheduling Algorithms

1. FCFS

2. SSTF

3. SCAN

4. C-SCAN

5. C-LOOK

FCFS (First-Come, First-Served)

• The simplest form of disk scheduling is, of course, the first-come, firstserved
(FCFS) algorithm.

• This algorithm is intrinsically fair, but it generally does not provide the fastest

service Example queue = 98, 183, 37, 122, 14, 124, 65, 67 head starts at 53

Total head movement = (65-53)+(67-65)+(67-37)+(37-14)+(98-14)+(122-98)+(124-

122)+(183-124) = 236 cylinders

SSTF (Shortest-Seek-Time-First)
• 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
Total head movement = (65-53)+(67-65)+(67-37)+(37-14)+(98-14)+(122-98)+(124122)+(183-
124) = 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

Total head movement = (53-37)+(37-14)+(14-0)+(65-0)+(67-65)+(98-67)+(122-98)+ (124-

122)+(183-124) = 236 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

Total head movement = (65-53)+ (67-65)+(98-67)+(122-98)+(124-122)+(183-124)

+(199-183)+(199-0)+(14-0)+(37-14) = 382 cylinders

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

Total head movement = (65-53)+ (67-65)+(98-67)+(122-98)+(124-122)+(183-124)

+(183-14)+(37-14) = 322 cylinders

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

• Performance depends on the number and types of requests

 • Requests for disk service can be influenced by the file-allocation method

• The disk-scheduling algorithm should be written as a separate module of the operating

system, allowing it to be replaced with a different algorithm if necessary

• Either SSTF or LOOK is a reasonable choice for the default algorithm

Disk Management

The operating system is responsible for several other aspects of disk management such as disk
initialization, booting from disk, and bad-block recovery

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.

• 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

• The first step is to partition the disk into one or more groups of cylinders.

• The second step is logical formatting, or creation of a file system

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

Boot Block
• The full bootstrap program is stored in the “boot blocks” at a fixed location on the disk.
A disk that has a boot partition is called a boot disk or system disk.

• The code in the boot ROM instructs the disk controller to read the boot blocks into
memory (no device drivers are loaded at this point) and then starts executing that code.

Bad Blocks
• More frequently, one or more sectors become defective. Most disks even come from the
factory with bad blocks.

• The controller can be told to replace each bad sector logically with one of the spare
sectors. This scheme is known as sector sparing or forwarding.