Subject Module 4 Prepared by: Dept.

of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Module IV
Memory Management
4.1 Background:
4.1.1 Basic Hardware:
Main memory and the registers built into the processor itself are the only storage that
the CPUcan access directly.
There are machine instructions that take memory addresses as arguments, but none
that takedisk addresses.
Therefore, any instructions in execution, and any data being used by the instructions,
must bein one of these direct-access storage devices.
Registers that are built into the CPU are generally accessible within one cycle of
the CPUclock.
Most CPUs can decode instructions and perform simple operations on register contents
at therate of one or more operations per clock tick.

Fig. 4.1 A base and limit register define a logical address space

We can provide the protection by using two registers, usually a base and a limit, as
illustratedin Figure 4.1.
The base register holds the smallest legal physical memory address; the limit register
specifiesthe size of the range.

For example, if the base register holds 300040 and limit register is 120900, then the
program can legally access all addresses from 300040 through 420940 (inclusive).
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 (Figure 4.2). This scheme prevents a user program from (accidentally or
deliberately) modifying the code or data structures of either the operating system or
other users.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Fig. 4.2 Hardware address protection with base and limit registers

4.1.2 Address Binding

Programs are stored on the secondary storage disks as binary executable file.
To be executed, the program must be brought into memory and placed within a
process.
Depending on the memory management in use, the process may be moved
between disk andmemory during its execution.
The normal procedure is to select one of the processes in the input queue and
to load thatprocess into memory.
As the process is executed, it accesses instructions and data from memory.
Eventually, theprocess terminates, and its memory space is declared available.
In most cases, a user program will go through several steps—some of which maybe
optional-—before being executed (Figure 4.3).
Classically, the binding of instructions and data to memory addresses can be done
at any stepalong the way:
1. Compile time. If you know at compile time where the process will reside in memory,
then absolute code can be generated. For example, if you know that a user process
will reside starting at location R, then the generated compiler code will start at that
location and extend up from there.
2. Load time. If it is not known at compile time where the process will reside in
memory, then the compiler must generate reloadable code. In this case, final binding
is delayed untilload time.
3. Execution time. If the process can be moved during its execution from one memory
segment to another, then binding must be delayed until run time. Most general-
purpose operating systems use this method.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Fig. 4.3 Multistep Processing of user Program

4.1.3 Logical versus Physical Address Space

An address generated by the CPU is commonly referred to as a logical address whereas an
address seen by the memory unit-that is, the one loaded into the memory address register
of the memory-is commonly referred to as a physical address.
The compile-time address-binding methods generate identical logical and physical addresses.
However, the execution-time and load-time address binding schemes results in differing
logicaland physical addresses.
The set of all logical addresses generated by a program is a logical address space; the set of
allphysical addresses corresponding to these logical addresses is a physical address space.

Figure 4.4 Dynamic relocation using a relocation register.

 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Figure 4.4 shows that dynamic re-location which implies mapping from virtual
(logical)addresses space to physical address space and is performed by the hardware at
run time.
The value in the relocation register is added to every address generated by a user
process at thetime the address is sent to memory
Re-location is performed by the hardware and is invisible to the user.
Dynamic relocation makes it possible to move a partially executed process from one
area ofmemory to another without affecting.

4.1.4 Dynamic Loading

For a process to be executed it should be loaded in to the physical memory.
The size of the process is limited to the size of the physical memory.
Dynamic loading is used to obtain better memory utilization.
In dynamic loading the routine or procedure will not be loaded until it is called.
Whenever a routine is called, the calling routine first checks whether the called routine
is already loaded or not. If it is not loaded it cause the loader to load the desired
program in to the memory and updates the programs address table to indicate the
change and control is passed to newly called routine.
Advantage:-
Gives better memory utilization.
Unused routine is never loaded. Do not need special operating system support.
This method is useful when large amount of codes are needed to handle in frequently
occurring cases.

4.1.5 Dynamic Linking and Shared Libraries

Static linking – system libraries and program code combined by the loader into
the binaryprogram image.
Dynamic linking –linking postponed until execution time
Small piece of code, stub, used to locate the appropriate memory-resident library routine.
Stub replaces itself with the address of the routine, and executes the routine
Operating system checks if routine is in processes’ memory address
If not in address space, add to address space
Dynamic linking is particularly useful for libraries
System also known as shared libraries
Consider applicability to patching system libraries
Versioning may be needed
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

4.2 Swapping

Figure 4.5 Swapping of two processes using a disk as a backing store.

 A process must be in memory to be executed.

 A process can be swapped temporarily out of memory to a backing store, and then
brought back into memory for continued execution
o Total physical memory space of processes can exceed physical memory
 Backing store – fast disk large enough to accommodate copies of all memory
images for all users; must provide direct access to these memory images
 Roll out, roll in – swapping variant used for priority-based scheduling algorithms;
lower-priority process is swapped out so higher-priority process can be loaded and
executed
 Major part of swap time is transfer time; total transfer time is directly proportional
to the amount of memory swapped
 System maintains a ready queue of ready-to-run processes which have memory
images on disk
 Does the swapped out process need to swap back in to same physical addresses?
o Depends on address binding method
o Plus consider pending I/O to / from process memory space
 Modified versions of swapping are found on many systems (i.e., UNIX, Linux,
and Windows)
o Swapping normally disabled
o Started if more than threshold amount of memory allocated
o Disabled again once memory demand reduced below threshold
 If next processes to be put on CPU is not in memory, need to swap out a process and
swap intarget process
 Context switch time can then be very high.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

4.3 Contiguous Memory Allocation

4.3.1 Memory Mapping and Protection
Main memory is usually divided into two partitions:
Resident operating system, usually held in low memory with interrupt vector
User processes then held in high memory
Each process contained in single contiguous section of memory
Relocation registers used to protect user processes from each other, and from changingoperating-
system code and data
Base register contains value of smallest physical address
Limit register contains range of logical addresses – each logical address must be less than thelimit
register
MMU maps logical address dynamically by adding the value in the relocation register.
This mapped address is sent to memory (as shown in figure 4.6)

Figure 4.6 Hardware support for relocation and limit registers

4.3.2 Memory Allocation

 One of the simplest methods for allocating memory is to divide memory into
several fixed- sized partitions (MFT-Multiprogramming with fixed number of
partitions).
 Each partition may contain exactly one process. Thus, the degree of
multiprogramming isbound by the number of partitions.
 In this multiple partition method when a partition is free, a process is selected
from the inputqueue and is loaded into the free partition.
 When the process terminates, the partition becomes available for another process.
 Generalization of the fixed-partition scheme called MVT (Multiprogramming
with variablenumber of partitions).
 In the variable partition scheme, the operating system keeps a table indicating
which parts ofmemory are available and which are occupied.
 Initially, all memory is available for user processes and is considered one
large block ofavailable memory a hole.
Eventually memory contains a set of holes of various sizes.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Figure 4.7 Contiguous Memory Allocation

As processes enter the system, they are put into an input queue.
The operating system takes into account the memory requirements of each process and
theamount of available memory space in determining which processes are allocated memory.
When a process is allocated space, it is loaded into memory, and it can then compete for CPU
time.
When a process terminates, it releases its memory which the operating system may then fill
with another process from the input queue.
When the memory has a set of holes the first fit, best fit and worst fit strategies are used to
select the free hole for the new process.
First fit. Allocate the first hole that is big enough. Searching can start either at the beginning
of the set of holes or at the location where the previous first-fit search ended. We can stop
searching as soon as we find a free hole that is large enough.
Best fit. Allocate the smallest hole that is big enough. We must search the entire list, unless the
list is ordered by size. This strategy produces the smallest leftover hole.
Worst fit. Allocate the largest hole. Again, we must search the entire list, unless it is sorted by
size. This strategy produces the largest leftover hole, which may be more useful than the
smaller leftover hole from a best-fit approach.
Eg: Given five memory partitions of 100Kb, 500Kb, 200Kb, 300Kb, 600Kb (in order), how would the
first-fit, best-fit, and worst-fit algorithms place processes of 212 Kb, 417 Kb, 112 Kb, and 426 Kb
(in order)? Which algorithm makes the most efficient use of memory?

First-fit:
212K is put in 500K partition
417K is put in 600K partition
112K is put in 288K partition (new partition 288K = 500K -
212K)
426K must wait
Best-fit:
212K is put in 300K partition
417K is put in 500K partition
112K is put in 200K partition
426K is put in 600K partition

Worst-fit:
212K is put in 600K partition
417K is put in 500K partition
112K is put in 388K partition
426K must wait
In this example, best-fit turns out to be the best.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

4.3.3 Fragmentation
As processes are loaded and removed from memory, the free memory space is broken into
littlepieces.
External fragmentation exists when there is enough total memory space to satisfy a
request but the available spaces are not contiguous; storage is fragmented into a large
number of small holes.
This fragmentation problem can be severe.
Depending on the total amount of memory storage and the average process size, external
fragmentation may be a minor or a major problem.
Statistical analysis of first fit, for instance, reveals that, even with some optimization,
given N allocated blocks, another 0.5 N blocks will be lost to fragmentation. That is, one-
third of memory may be unusable! This property is known as the 50-percent rule.
Memory fragmentation can be internal as well as external.
Consider a multiple-partition allocation scheme with a hole of 18,464 bytes. Suppose that
the next process requests 18,462 bytes. If we allocate exactly the requested block, we are
left witha hole of 2 bytes.
The overhead to keep track of this hole will be substantially larger than the hole itself.
The general approach to avoiding this problem is to break the physical memory into
fixed-sized blocks and allocate memory in units based on block size.
With this approach, the memory allocated to a process may be slightly larger than the
requested memory. The difference between these two numbers is internal fragmentation
that is unused memory that is internal to a partition.
One solution to the problem of external fragmentation is compaction. The goal is to
shuffle the memory contents so as to place all free memory together in one large block.
Compaction is not always possible.
Another possible solution to the external-fragmentation problem is to permit the logical
address space of the processes to be noncontiguous, thus allowing a process to be
allocated physical memory wherever such memory is available.

4.4 Non-Contiguous Memory Allocation

 Two techniques of non-contiguous memory allocation are paging and segmentation.

4.4.1 Paging
Basic Method
 Paging is a memory-management scheme that permits the physical address space of a
processto be noncontiguous.
 Paging avoids external fragmentation and the need for compaction.
 It also solves the considerable problem of fitting memory chunks of varying sizes onto the
backing store.
 The basic method for implementing paging involves breaking physical memory into
fixed- sized blocks called frames and breaking logical memory into blocks of the same
size called pages.
 When a process is to be executed, its pages are loaded into any available memory frames
from their source. The hardware support for paging is illustrated in Figure 4.8

 Every address generated by the CPU is divided into two parts: a page number (p) and a
page offset (d). The page number is used as an index into a page table.
 The page table contains the base address of each page in physical memory. This base
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

address is combined with the page offset to define the physical memory address that is
sent to thememory unit.

Figure 4.8 Paging Hardware

 The size of a page is typically a power of 2, varying between 512 bytes and 16 MB per
page, depending on the computer architecture.
 The selection of a power of 2 as a page size makes the translation of a logical address into
a page number and page offset particularly easy.
 If the size of logical address space is 2m and a page size is 2n addressing units (bytes or
words), then the high-order m – n bits of a logical address designate the page number, and
the n low- order bits designate the page offset.
 Thus, the logical address is as follows:

Example: Refer Fig 4.9

 Using a page size of 4 bytes and a physical memory of 32 bytes (8 pages).

 Logical address 0 is page 0, offset 0. Indexing into the page table, we find that page 0 is
inframe 5. Thus, logical address 0 maps to physical address 20 (= (5 x 4) + 0).
 Logical address 3 (page 0, offset 3) maps to physical address 23 (= (5x4) + 3).
 Logical address 4 is page 1, offset 0; according to the page table, page 1 is mapped to frame 6.
 Logical address 4 maps to physical address 24 (= (6x4) + 0).
 Logical address 13 maps to physical address 9.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Figure 4.9 Paging Example

Translation Look aside Buffer (TLB)

 Each operating system has its own methods for storing page tables. Most allocate a page
table for each process.
 A pointer to the page table is stored with the other register values (like the instruction
counter) in the process control block.
 The use of registers for the page table is satisfactory if the page table is reasonably small
(for example, 256 entries). Most contemporary computers, however, allow the page table
to be verylarge (for example, 1 million entries).
 For these machines, the use of fast registers to implement the page table is not feasible.
Rather, the page table is kept in main memory.
 The problem with this approach is the time required to access a user memory location. If
we want to access location i, we must first index into the page table.
 This task requires a memory access. It provides us with the frame number, which is
combined with the page offset to produce the actual physical address.
 With this scheme, two memory accesses are needed to access a byte (one for the page-
table entry, one for the byte).
 The standard solution to this problem is to use a special, small, fast lookup hardware
cache, called a translation look-aside buffer (TLB). Fig. 4.10.
 The TLB is used with page tables in the following way.
 The TLB contains only a few of the page-table entries. When a logical address is
generated by the CPU, page number is first searched in TLB.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

 If the page number is found, its frame number is immediately available and is used to
access memory.

 The whole task may take less than 10 percent longer than it would if an unmapped
memory reference were used.
 If the page number is not in the TLB (known as a TLB miss), a memory reference to the
page table must be made.

Figure 4.10 Paging hardware with TLB.

 The percentage of times that a particular page number is found in the TLB is called the hit
ratio.
 An 80-percent hit ratio means that we find the desired page number in the TLB 80 percent
of the time.
 If it takes 20 nanoseconds to search the TLB and 100 nanoseconds to access memory,
then a mapped-memory access takes 120 nanoseconds when the page number is in the
TLB.
 If we fail to find the page number in the TLB (20 nanoseconds), then we must first access
memory for the page table and frame number (100 nanoseconds) and then access the
desired byte in memory (100 nanoseconds), for a total of 220 nanoseconds.
 To find the effective memory-access time, we weight each case by its
probability: Effective access time = 0.80 * 120 + 0.20 * 220 = 140
nanoseconds.
 In this example, we suffer a 40-percent slowdown in memory-access time (from 100 to
140 nanoseconds).
 For a 98-percent hit ratio,
we have effective access time = 0.98 * 120 + 0.02 * 220 = 122 nanoseconds.

Protection
 Memory protection in a paged environment is accomplished by protection bits associated
witheach frame.
 Normally, these bits are kept in the page table.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

 One bit can define a page to be read-write or read-only.

 Every reference to memory goes through the page table to find the correct frame number.
 At the same time that the physical address is being computed, the protection bits
can bechecked to verify that no writes are being made to a read-only page.
 An attempt to write to a read-only page causes a hardware trap to the operating system.
 One additional bit is generally attached to each entry in the page table: a valid-invalid bit.
 When this bit is set to "valid," the associated page is in the process's logical address
space andis thus a legal (or valid) page.
 When the bit is set to "invalid,'" the page is not in the process's logical address space.

Figure 4.11 Protection bits

Shared Pages
 One of the advantages of paging is the possibility of sharing common code.
 This consideration is particularly important in a time-sharing environment.
 Example: Consider a system that supports 40 users, each of whom executes a text editor.
If the text editor consists of 150 KB of code and 50 KB of data space, we need 8,000 KB
to support the 40 users.
 If the code is reentrant code (or pure code), however, it can be shared, as shown in
Figure. 4.12. Here we see a three-page editor—each page 50 KB in size being shared
among three processes. Each process has its own data page.
 Reentrant code is non-self-modifying code; it never changes during execution. Thus, two
or more processes can execute the same code at the same time.
 Each process has its own copy of registers and data storage to hold the data for the
process's execution. The data for two different processes will, of course, be different.
 Only one copy of the editor need be kept in physical memory. Each user's page table maps
onto the same physical copy of the editor, but data pages are mapped onto different
frames. Thus, to support 40 users, we need only one copy of the editor (150 KB), plus 40
copies of the 50 KB of data space per user. The total space required is now 2,150 KB
instead of 8,000 KB - a significant savings.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Figure 4.12 Sharing of Code (Share Pages)

4.4.2 Segmentation
 Consider how you think of a program when you are writing it. You think of it as a main
program with a set of methods, procedures, or functions. (Figure 4.13)
 It may also include various data structures: objects, arrays, stacks, variables, and so on.
Each of these modules or data elements is referred to by name. You talk about "the stack,"
"the math library," ''the main program," without caring what addresses in memory these
elements occupy.

4.13 User view of Program

 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

 Segmentation is a memory-management scheme that supports this user view of memory.

 A logical address space is a collection of segments.
 Each segment has a name and a length. The addresses specify both the segment name
and theoffset within the segment.

 The user therefore specifies each address by two quantities: a segment name and an offset.
 (Contrast this scheme with the paging scheme, in which the user specifies only a single
address, which is partitioned by the hardware into a page number and an offset, all
invisible to the programmer.)
 For simplicity of implementation, segments are numbered and are referred to by a
segment number, rather than by a segment name.
 Thus, a logical address consists of a two tuple: < segment-number, offset >.
 Although the user can now refer to objects in the program by a two-dimensional
address, the actual physical memory is still, of course, a one-dimensional sequence of
bytes.
 This is done with the help of segment table. Each entry in the segment table has a
segmentbase and a segment limit.
 The segment base contains the starting physical address where the segment resides in
memory,whereas the segment limit specifies the length of the segment.
 The use of a segment table is illustrated in Figure 4.14. A logical address consists of two
parts: asegment number, s, and an offset into that segment, d.
 The segment number is used as an index to the segment table.
 The offset d of the logical address must be between 0 and the segment limit. If it is not,
we trap to the operating system. When an offset is legal, it is added to the segment base to
produce the address in physical memory of the desired byte.
 As an example, consider the situation shown in Figure 4.15.

Figure 4.14 Segmentation Hardware

 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Figure 4.15 Example of segmentation

 For example, segment 2 is 400 bytes long and begins at location 4300. Thus, a
reference tobyte 53 of segment 2 is mapped onto location 4300 + 53 = 4353.
 A reference to segment 3, byte 852, is mapped to 3200 (the base of segment 3) + 852 =
4052.A reference to byte 1222 of segment 0 would result in a trap to the operating system,
as this segment is only 1,000 bytes long.

4.5 Structure of Page Table

 Memory structures for paging can get huge using straight-forward methods
o Consider a 32-bit logical address space as on modern computers
o Page size of 4 KB (212)
o Page table would have 1 million entries (232 / 212)
o If each entry is 4 bytes -> 4 MB of physical address space / memory for page
tablealone
 That amount of memory used to cost a lot
 Don’t want to allocate that contiguously in main memory
 Three methods of representing Page Table
1. Hierarchical Paging
2. Hashed Page Tables
3. Inverted Page Tables
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

4.5.1 Hierarchical Paging

o Break up the logical address space into multiple page tables
o A simple technique is a two-level page table
o We then page the page table –Figure 4.16

Fig. 4.16 A two-level page table scheme

 A logical address (on 32-bit machine with 1K page size) is divided into:
o a page number consisting of 22 bits
o a page offset consisting of 10 bits
 Since the page table is paged, the page number is further divided into:
o a 12-bit page number
o a 10-bit page offset
 Thus, a logical address is as follows:

where p1 is an index into the outer page table, and p2 is the displacement within the page of
theouter page table
 Known as forward-mapped page table –Figure 4.17
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Figure. 4.17 Address Translation for two-level 32bit paging architecture

 Even two-level paging scheme not sufficient

 If page size is 4 KB (212)
o Then page table has 252 entries
o If two level scheme, inner page tables could be 210 4-byte entries
o Address would look like

o Outer page table has 242 entries or 244 bytes

o One solution is to add a 2nd outer page table
o But in the following example the 2nd outer page table is still 234 bytes in size
 And possibly 4 memory access to get to one physical memory location

4.5.2 Hashed Page Table

 Common in address spaces > 32 bits
 The virtual page number is hashed into a page table
 This page table contains a chain of elements hashing to the same location
 Each element contains (1) the virtual page number (2) the value of the mapped page
frame (3) a pointer to the next element
 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 4.18.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Figure 4.18 Hashed Page Table

4.5.3 Inverted Page Table

 Rather than each process having a page table and keeping track of all possible logical
pages,track all physical pages.
 One entry for each real page of memory.
 Entry consists of the virtual address of the page stored in that real memory location,
withinformation about the process that owns that page.
 Decreases memory needed to store each page table, but increases time needed to search
thetable when a page reference occurs.
 Use hash table to limit the search to one — or at most a few — page-table entries.
 TLB can accelerate access.
 But how to implement shared memory?
One mapping of a virtual address to the shared physical address

Figure 4.19 Inverted Page Table

 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Virtual Memory Management

4.6 Introduction /Background:
The memory-management algorithms are necessary because of one basic requirement: The
instructions being executed must be in physical memory. An examination of real programs
shows us that, in many cases, the entire program is not needed. For instance, consider the
following:
Programs often have code to handle unusual error conditions. Since these errors
seldom, ifever, occur in practice, this code is almost never executed.
Arrays, lists, and tables are often allocated more memory than they actually need. An
arraymay be declared 100 by 100 elements, even though it is seldom larger than 10 by
10 elements.
 Certain options and features of a program may be used rarely.
The ability to execute a program that is only partially in memory would confer many benefits:
A program would no longer be constrained by the amount of physical memory that is
available.
Because each user program could take less physical memory, more programs could be
run at the same time, with a corresponding increase in CPU utilization and throughput
Less I/O would be needed to load or swap each user program into memory, so each
user program would run faster.
Virtual memory involves the separation of logical memory as perceived by users from physical
memory. This separation, allows an extremely large virtual memory to be provided for
programmers when only a smaller physical memory is available (Figure 4.20).

Figure 4.20 Diagram showing virtual memory that is larger than physical memory.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

The virtual address space of a process refers to the logical (or virtual) view of how a process
is stored in memory. Typically, this view is that a process begins at a certain logical address—
say, addresses 0—and exists in contiguous memory, as shown in Figure 4.21. We allow for the
heap to grow upward hi memory as it is used for dynamic memory allocation. Similarly, we
allow for the stack to grow downward in memory through successive function calls. The large
blank space (or hole) between the heap and the stack is part of the virtual address space.

Figure 4.21 Virtual Address Space

Virtual memory also allows files and memory to be shared by two or more processes through
page sharing. This leads to the following benefits:
System libraries can be shared by several processes through mapping of the shared
object intoa virtual address space.
Virtual memory enables processes to share memory.
Virtual memory can allow pages to be shared during process creation with the fork( )
system call, thus speeding up process creation.

Figure 4.22 Shared library using virtual memory.

 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

4,6.1Demand Paging
 A demand-paging system is similar to a paging system with swapping where
processes reside in secondary memory.
 When we want to execute a process, we swap it into memory.
 Rather than swapping the entire process into memory, however, we use a lazy
swapper. A lazy swapper never swaps a page into memory unless that page will
be needed.

Figure 4.23 Transfer of a paged memory to contiguous disk space.

 When a process is to be swapped in, the pager guesses which pages will be used
beforethe process is swapped out again.
 Instead of swapping in a whole process, the pager brings only those
necessary pagesinto memory.
 In page table we maintain a extra bit called valid-invalid bit to know the
status ofpage.
 If it is set to 1 then page is valid and present in primary memory, then we
calculate thephysical address and continue execution.
 If it is set to 0, then page is not present in primary memory, such a state is
called pagefault. Following procedure is used to handle Page faults. (Fig. 4.24)
1. We check an page table for this process to determine whether the
reference was avalid or an invalid memory access.
2. If the reference was invalid, we terminate the process. Generate trap to
operatingsystems.
3. OS brings page from secondary storage.
4. Find a free frame if available, else use page replacement algorithm to
remove onepage from primary memory to make fare free.
5. We modify the page table to indicate that the page is now in memory.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

6. We restart the instruction that was interrupted by the trap. The process
can nowaccess the page as though it had always been in memory.

Figure 4.24 Steps in handling a page fault

Performance of Demand Paging

 Demand paging can significantly affect the performance of a computer system.
To see why, let's compute the effective access time for a demand-paged
memory. For most computer systems, the memory-access time, denoted ma,
ranges from 10 to 200 nanoseconds. As long as we have no page faults, the
effective access time is equal to the memory access time. If, however, a page
fault occurs, we must first read the relevant page from disk and then access the
desired word.
 Let p be the probability of a page fault (0 <= p <= 1). We would expect p to be
close to zero—that is, we would expect to have only a few page faults.
 The effective access time is = (1 - p) * ma + p * page fault time.
 If we take an average page-fault service time of 8 milliseconds and a memory-
access time of 200 nanoseconds, then the effective access time in nanoseconds
is

Effective access time = (1 - p) * (200) + p (8 milliseconds)

= (1 - p) * 200 + p * 8.00(1000000)
= 200 + 7,999,800 * p.

 If one access out of 1,000 causes a page fault, the effective access time is 8.2
microseconds. That is page fault is 1/10 or 0.1%.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

4.6.2 Copy-on-Write
 We know that the fork() system call creates a child process as a duplicate of its
parent.
 Traditionally, fork() worked by creating a copy of the parent's address space
for the child, duplicating the pages belonging to the parent. However,
considering that manychild processes invoke the exec() system call
immediately after creation, the copying of the parent's address space may be
unnecessary.
 Alternatively, we can use a technique known as copy-on-write, which works by
allowing the parent and child processes initially to share the same pages. These
shared pages are marked as copy-on-write pages, meaning that if either process
writes to a shared page, a copy of the shared page is created.
 Copy-on-write is illustrated in Figures 4.25 and Figure 4.26, which show the
contents of the physical memory before and after process 1 modifies page C.
 For example, assume that the child process attempts to modify a page
containing portions of the stack, with the pages set to be copy-on-write.
 The operating system will then create a copy of this page, mapping it to the
address space of the child process.
 The child process will then modify its copied page and not the page belonging
to the parent process.
 Obviously, when the copy-on-write technique is used, only the pages that are
modified by either process are copied; all unmodified pages can be shared by
the parent and child processes.

Figure 4.25 Before process 1 modifies page C.

Figure 4.26 After process 1 modifies page C.

 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

4.6.3 Page Replacement

 In demand paging or virtual memory management systems, we bring only those
pages into primary memory which is required at any time.

 If there is no free frame in primary memory and CPU wants to execute a page
which is not present in primary memory this is called page fault. Then we need
to remove one page from primary memory and bring new page from secondary
storage.
 Page replacement is process of selecting a page in primary memory to make a
way for new page.

Basic Page Replacement

 Page replacement takes the following approach. If no frame is free, we find one
that is notcurrently being used and free it.
 We can free a frame by writing its contents to swap space and changing the page table
(and allother tables) to indicate that the page is no longer in memory (Figure 4.27).
 We can now use the freed frame to hold the page for which the process faulted. We
modify thepage-fault service routine to include page replacement.

 Steps in Page replacement

1. Find the location of the desired page on the disk.
2. Find a free frame:
a. If there is a free frame, use it. If there is no free frame, use a page-
replacement algorithm to select a victim frame.
b. Write the victim frame to the disk; change the page and frame
tablesaccordingly.
c. Read the desired page into the newly freed frame; change the
page andframe tables.
3. Restart the user process.

 If no frames are free, two page transfers (one out and one in) are required. This
situation effectively doubles the page-fault service time and increases the
effective access time accordingly.
 We can reduce this overhead by using a modify bit (or dirty bit). When this
scheme is used, each page or frame has a modify bit associated with it in the
hardware.
 The modify bit for a page is set by the hardware whenever any word or byte in
the page is written into, indicating that the page has been modified.
 When we select a page for replacement, we examine its modify bit. If the bit is
set, we know that the page has been modified since it was read in from the disk.
In this case, we must write that page to the disk.
 If the modify bit is not set, however, the page has not been modified since it was
read into memory. Therefore, if the copy of the page on the disk has not been
overwritten (by some other page, for example), then we need not write the
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

memory page to thedisk: It is already there.

 This technique also applies to read-only pages (for example, pages of binary
code). Such pages cannot be modified; thus, they may be discarded when
desired. This scheme can significantly reduce the time required to service a
page fault, since it reduces I/O time by one-half if the page has not been
modified.

Figure 4.27 Page replacement

Page Replacement Algorithms

 We evaluate an algorithm by running it on a particular string of memory references and
computing the number of page faults. The string of memory references is called a
reference string.
 For example, if we trace a particular process, we might record the following address
sequence:
 0100, 0432, 0101,0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104,0101,0610,
0102,0103, 0104, 0101, 0609, 0102, 0105
 At 100 bytes per page, this sequence is reduced to the following reference string:
1,4,1,6,1,6,1,6,1,6,1
 For illustrating different page replacement algorithms, consider the following reference
string 7, 0,1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2,1, 2, 0, 1, 7, 0,1 for a memory with three frames.

FIFO Page Replacement

 The simplest page-replacement algorithm is a first-in, first-out (FIFO) algorithm. A
FIFO replacement algorithm associates with each page the time when that page was
brought into memory. When a page must be replaced, the oldest page is chosen.
 Figure 4.28 shows the FIFO place replacement algorithm.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Figure 4.28 FIFO page-replacement algorithm.

 To illustrate the problems that are possible with a FIFO page-replacement algorithm.,
we consider the following reference string: 1,2,3,4,1,2,5,1,2,3,4,5
 Figure 4.28 shows the curve of page faults for this reference string versus the number
of available frames. Notice that the number of faults for four frames (ten) is greater
than the number of faults for three frames (nine)! This most unexpected result is known
as Belady's anomaly: For some page-replacement algorithms, the page-fault rate may
increase as the number of allocated frames increases.

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

Optimal Page Replacement
 An optimal page-replacement algorithm has the lowest page-fault rate of all
algorithms andwill never suffer from Belady's anomaly.
 Use of this page-replacement algorithm guarantees the lowest possible page fault rate
for a fixed number of frames. For example, on our sample reference string, the optimal
page- replacement algorithm would yield nine page faults, as shown in Figure 4.29
 Replace the page that will not be used for the longest period of time.

Figure 4.29 Optimal page-replacement algorithm.

 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

LRU Page Replacement

 If the optimal algorithm is not feasible, perhaps an approximation of the optima]
algorithm is possible.
 The key distinction between the FIFO and OPT algorithms (other than looking
backward versus forward in time) is that the FIFO algorithm uses the time when
a page was brought into memory, whereas the OPT algorithm uses the time
when a page is to be used.

 If we use the recent past as an approximation of the near future, then we can
replace the page that has not been used for the longest period of time (Figure
4.30). This approach is the least-recently-used (LRU) algorithm.
 Replace the page that has not been used for the longest period of time

Figure 4.30 LRU page-replacement algorithm.

Counters: In the simplest case, we associate with each page-table entry a time-of-use field and
add to the CPU a logical clock or counter. The clock is incremented for every memory
reference. Whenever a reference to a page is made, the contents of the clock register are copied
to the time-of-use field in the page-table entry for that page. In this way, we always have the
"time" of the last reference to eachpage. We replace the page with the smallest time value.
Stack: Another approach to implementing LRU replacement is to keep a stack of page
numbers. Whenever a page is referenced, it is removed from the stack and put on the top. In this
way, the most recently used page is always at the top of the stack and the least recently used
page is always at the bottom (Figure 4.31).

Figure 4.31 Use of stack references.

 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

LRU-Approximation Page Replacement

• Few computer systems provide sufficient hardware support for true LRU page
[Link] systems provide no hardware support.
• Many systems provide some help, however, in the form of a reference bit.
• The reference bit for a page is set by the hardware whenever that page is referenced
(either aread or a write to any byte in the page).
• Reference bits are associated with each entry in the page table.
• Initially, all bits are cleared (to 0) by the operating system.
• As a user process executes, the bit associated with each page referenced is set (to 1)
by thehardware.
• After some time, we can determine which pages have been used and which have not
been usedby examining the reference bits, although we do not know the order of use.

Additional-Reference-Bits Algorithm
• We can gain additional ordering information by recording the reference bits at regular
intervals.
• We can keep an 8-bit byte for each page in a table in memory.
• At regular intervals (say, every 100 milliseconds), a timer interrupt transfers
control to theoperating system.
• The operating system shifts the reference bit for each page into the high-order bit of
its 8-bitbyte, shifting the other bits right by 1 bit and discarding the low-order bit.
• These 8-bit shift registers contain the history of page use for the last eight time periods.

Second-Chance Algorithm
• The basic algorithm of second-chance replacement is a FIFO replacement algorithm.
• When a page has been selected, however, we inspect its reference bit.
• If the value is 0, we proceed to replace this page; but if the reference bit is set to 1, we
give thepage a second chance and move on to select the next FIFO page.
• When a page gets a second chance, its reference bit is cleared, and its arrival time is
reset to thecurrent time.
• Thus, a page that is given a second chance will not be replaced until all other pages
have beenreplaced.

• One way to implement the second-chance algorithm (sometimes referred to as the

dock algorithm) is as a circular queue.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Figure 4.32 Second-Chance Algorithm

Enhanced Second-Chance Algorithm

We can enhance the second-chance algorithm by considering the reference bit and the modify bit as
anordered pair. With these two bits, we have the following four possible classes:
• (0, 0) neither recently used nor modified—best page to replace
• (0, 1) not recently used but modified—not quite as good, because the page will
need to bewritten out before replacement
• (1., 0) recently used but clean—probably will be used again soon
• (1,1) recently used and modified—probably will be used again soon, and the page
will beneed to be written out to disk before it can be replaced

Counting-Based Page Replacement:

There are many other algorithms that can be used for page replacement. For example, we can
keep a counter of the number of references that have been made to each page and develop the
following two schemes.
• The least frequently used (LFU) page-replacement algorithm requires that the page with
the smallest count be replaced. The reason for this selection is that an actively used page should
have a large reference count.

• The most frequently used (MFU) page-replacement algorithm is based on the argument that
the pagewith the smallest count was probably just brought in and has yet to be used.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

4.6.4 Page-Buffering Algorithms:

Other procedures are often used in addition to a specific page-replacement algorithm.
For example, systems commonly keep a pool of free frames.
When a page fault occurs, a victim frame is chosen as before.
The desired page is read into a free frame from the pool before the victim is written out.
This procedure allows the process to restart as soon as possible, without waiting for
the victimpage to be written out.
When the victim is later written put, its frame is added to the free-frame pool.

4.6.5Allocation of Frames
 How do we allocate the fixed amount of free memory among the various processes? If
we have93 free frames and two processes, how many frames does each process get?
 The simplest case is the single-user system. Consider a single-user system with 128 KB
of memory composed of pages 1 KB in size. This system has 128 frames.
 The operating system may take 35 KB, leaving 93 frames for the user process. Under
pure demand paging, all 93 frames would initially be put on the free-frame list. When a
user processstarted execution, it would generate a sequence of page faults.
 The first 93 page faults would all get free frames from the free-frame list. When the
free-framelist was exhausted, a page-replacement algorithm would he used to select one
of the 93 in- memory pages to be replaced with the 94th, and so on.
 When the process terminated, the 93 frames would once again be placed on the free-frame
list.

Minimum Number of Frames

 We must also allocate at least a minimum number of frames. Here, we look more
closely at thelatter requirement.
 One reason for allocating at least a minimum number of frames involves performance.
Obviously, as the number of frames allocated to each process decreases, the page-fault
rate increases, slowing process execution.
 In addition, remember that, when a page fault occurs before an executing instruction is
complete, the instruction must be restarted.
 Consequently, we must have enough frames to hold all the different pages that any
single instruction can reference.

Allocation Algorithms
 The easiest way to split m frames among n processes is to give everyone an equal share,
m/n
frames.
 For instance, if there are 93 frames and five processes, each process will get 18
frames. Theleftover three frames can be used as a free-frame buffer pool.
 This scheme is called equal allocation.
An alternative is to recognize that various processes will need differing
amounts of [Link] a system with a 1-KB frame size. If a small student
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

process of 10 KB and an interactive database of 127 KB are the only two processes
running in a system with 62 free frames, it does not make much sense to give each
process 31 frames. The student process does not need more than 10 frames, so the other
21 are, strictly speaking, wasted. To solve this problem, we can use proportional
allocation, in which we allocate available memory to each process according to its size.

Global versus Local Allocation

 Another important factor in the way frames are allocated to the various processes is
page replacement. With multiple processes competing for frames, we can classify page-
replacement algorithms into two broad categories: global replacement and local
replacement.
 Global replacement allows a process to select a replacement frame from the set of all
frames, even if that frame is currently allocated to some other process; that is, one
process can take a frame from another. Local replacement requires that each process
select from only its own set of allocated frames.
 For example, consider an allocation scheme where we allow high-priority processes to
select frames from low-priority processes for replacement. A process can select a
replacement from among its own frames or the frames of any lower-priority process.
This approach allows a high-priority process to increase its frame allocation at the
expense of a low-priority process.

4.7 Thrashing
 If the process does not have the number of frames it needs to support pages in active
use, it willquickly page-fault. At this point, it must replace some page.
 However, since all its pages are in active use, it must replace a page that will be
needed again right away. Consequently, it quickly faults again, and again, and again,
replacing pages that it must bring back in immediately.
 This high paging activity is called thrashing. A process is thrashing if it is spending
more timepaging than executing.
Cause of Thrashing
 Thrashing results in severe performance problems.
 The operating system monitors CPU utilization. If CPU utilization is too low, we
increase the degree of multiprogramming by introducing a new process to the system.
 A global page-replacement algorithm is used; it replaces pages without regard to the
process towhich they belong.
 Now suppose that a process enters a new phase in its execution and needs more frames.
It startsfaulting and taking frames away from other processes.
 These processes need those pages, however, and so they also fault, taking frames from
other processes. These faulting processes must use the paging device to swap pages in
and out. As they queue up for the paging device, the ready queue empties. As processes
wait for the pagingdevice, CPU utilization decreases.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Figure 5.17 Thrashing.

 We can limit the effects of thrashing by using a local replacement algorithm (or
priority replacement algorithm). With local replacement, if one process starts
thrashing, it cannot steal frames from another process and cause the latter to thrash as
well.

Working-Set Model
 The working-set model is based on the assumption of locality.
 This model uses a parameter, A, to define the working-set window.
 The idea is to examine the most recent A page references.
 The set of pages in the most recent A page references is the working set (Figure 9.20).

 If a page is in, active use, it will be in the working set.

 If it is no longer being used, it will drop from the working set A time units
after its lastreference.
 Thus, the working set is an approximation of the program's locality.
 The most important property of the working set, then, is its size.
 If we compute the working-set size, WSSj, for each process in the system, we can then
considerthat
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

where D is the total demand for frames. Each process is actively using the pages in its working set.

Page-Fault Frequency :
 The working-set model is successful, and knowledge of the working set can be
useful forprepaging but it seems a clumsy way to control thrashing.
 A strategy that uses the page-fault frequency (PFF) takes a more direct approach.
 Thrashing has a high page-fault rate.
 Thus, we want to control the page-fault rate.
 When it is too high, we know that the process needs more frames.
 Conversely, if the page-fault rate is too low, then the process may have too many frames.
 We can establish upper and lower bounds on the desired page-fault rate (Figure 9.21).
 If the actual page-fault rate exceeds the upper limit, we allocate the process another frame;
 If the page-fault rate falls below the lower limit, we remove a frame from the process.
 Thus, we can directly measure and control the page-fault rate to prevent thrashing.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

Problems:
1. Consider the following page reference string
8,1,2,3,1,4,1,5,3,4,1,4,3,2,3,1,2,8,1,2
Assuming there are 4 memory frames, how many page faults would occur in case of
i. FIFO
ii. Optimal algorithm,
Note that initially all frames are empty.
Sol:
i. FIFO Replacement

8 1 2 3 1 4 1 5 3 4 1 4 3 2 3 1 2 8 1 2

8 8 8 8 4 4 4 4 3 3
1 1 1 1 5 5 5 5 8
2 2 2 2 1 1 1 1
3 3 3 3 2 2 2

No. of Page faults = 10

ii. Optimal Replacement

8 1 2 3 1 4 1 5 3 4 1 4 3 2 3 1 2 8 1 2

8 8 8 8 4 4 2 2
1 1 1 1 1 1 1
2 2 2 5 5 8
3 3 3 3 3

No. of Page faults = 8

Question Bank
1. Describe the Segmentation technique.
2. What is Paging? Explain the Structure of Page Table.
3. What is Swapping? Does this increase OS overhead? Justify your answer.
4. What are Translation Load side Buffer(TLB)?Explain TLB in detail with a
simple paging system with a neat diagram.
5. Write a note on Contiguous memory allocation.
6. Module-4
7. Describe briefly about demand paging in memory management scheme.
8. Illustrate how demand paging affects system performance.
9. Describe the steps involved handling a page fault.
10. What is Thrashing? How it can be controlled?
11. 1. Consider the following page reference string
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
Assuming there are 2 memory frames, how many page faults would occur in case of
i) LRU
ii) ii) Optimal algorithm,
Note that initially all frames are empty.
 Subject Module 4 Prepared by: Dept. of ISE,
Operating Systems Memory Management DBIT
(BCS303)

12. Consider the following page reference string

8,1,2,3,1,4,1,5,3,4,1,4,3,2,3,1,2,8,1,2
Assuming there are 4 memory frames, how many page faults would occur in case if
Most Recently Used (MRU) Algorithm is used. Most recently is the page that
is used recently which is chosen for replacement assuming that it may not be
needed later for a longer time. Repeat the same with Least Recently used (LRU)
algorithm and calculate the hit ratio and miss ratio for both.

Important Questions from previous VTU Papers on Memory Management

1. Discuss the issues that are pertinent to the various techniques for managing memory.
2. Write a note on dynamic Loading and Linking.
3. What is swapping? Does this increase OS overhead? Justify your answer.
4. Write a note on Contiguous memory allocation.
5. What is internal & external fragmentation?
6. Bring out differences between internal & external fragmentation? How are they overcome?
7. Explain the buddy-system, used for managing free memory assigned to kernel process.
8. What is paging? Explain basic hardware of paging.
9. Why TLB is important. In simple paging what information is stored in TLB.
10. Write a note on shared pages.
11. Describe the Segmentation technique.