OPERATING SYSTEMS-UNIT-4

UNIT-4

MEMORY MANAGEMENT.

Memory consists of a large array of words or bytes.

Each word has its own address.

The main memory and the registers built into the processor itself are the only storage that the cpu can access
directly.

Any instruction in execution and any data being used by the instructions must be in one of these direct access
storage devices.

If data is not in memory , they must be moved there before the cpu can operate.
We need to make sure that each process has a separate memory space.
We can provide this protection by using two registers as base register and limit registers.
The base register holds the smallest legal physical memory address.
The limit register specifies the size of the range.
The base and limit registers can be loaded only by os, which uses a special privileged instruction.
These instructions can be executed in kernel mode.

CSE@CMRCET G RAVIKUMAR Page 1

 OPERATING SYSTEMS-UNIT-4

Protection of memory space is accomplished by having the CPU hardware compare every address generated in
user mode with registers. An attempt by a program executing in user mode to access OS memory or others user’s
memory results in a trap to OS, which treats the attempt as a fatal error.

Address binding

Usually a program resides on a disk as a binary executable file.

To be executed the program must be brought in to memory and placed within a process.
Most systems allow a user process to reside in any part of the physical memory.
Before being executed a user program, the address may be represented in different ways.
Addresses in the source program are generally symbolic such as count.
A compiler will bind these symbolic addresses to relocatable addresses.
The linkage editor or loader will inturn point the relocatable addresses to absolute addresses .

CSE@CMRCET G RAVIKUMAR Page 2

 OPERATING SYSTEMS-UNIT-4

The binding of instructions and data to memory addresses can be done in the following way

i) Compile time

ii) Load time

iii) Execution time

Logical and physical address space

An address generated by CPU is referred to as a logical address or virtual address.

Where as an address seen by memory unit is referred to as a physical address.

The set of all logical addresses generated by a program is a logical address space.

The set of all physical addresses corresponding to logical addresses is a physical address space.

The run time mapping from virtual to physical address is done by a h/w device called the memory
management unit.

The base register is called a relocation register ,the value in the relocation register is added to every address
generated by a user process at the time the address is sent to memory.

For example if the base at 14000, then an attempt by the user to address location 0 is dynamically relocated to
location 14000.

An access to location 346 is mapped to location 14346.

Swapping
A process must be in memory to be executed

However it can be swapped temporarily out of memory to a backing store and then brought back into memory for
continued execution.

CSE@CMRCET G RAVIKUMAR Page 3

 OPERATING SYSTEMS-UNIT-4

For example

Assume a multiprogramming environment with a round robin cpu scheduling algorithm.

When a quantum expires, the memory manager will start to swap out the process that just finished and to swap
another process into memory space that has been fired.

When each process finishes its quantum, it will be swapped with another process.

A variant of this swapping policy is used for priority based scheduling algorithms.

If a higher priority process arrives and wants service, the memory manager can swap out the lower priority process
and then load and execute the higher priority process.

When the higher priority process finishes, the lower priority process can be swapped back in and continued.

This variant of swapping is sometimes called roll out, roll in.

Swapping requires a backing store.

The backing store is commonly a fast disk.

It must be large enough to accommodate copies of all memory images for all users, and it must provide direct
access to these memory images.

Swapping is used in many versions of UNIX.

[Link] memory allocation

The main memory must accommodate both the os and the various user processes.

The memory is divided into two partitions

One for the resident os and for the user processes.

CSE@CMRCET G RAVIKUMAR Page 4

 OPERATING SYSTEMS-UNIT-4

How to allocate available memory to the processes that are in the input queue waiting to be brought into memory
in Contiguous memory allocation, each process in a single contiguous section of memory.

i) Memory mapping and protection

We can provide by using a Relocation Register and Limit Register.

The relocation register contains the value of the smallest physical address

The limit register contains the range of logical addresses.

(For example relocation register=100040 and limit=74600)

logical address must be less than the limit register.

When the CPU scheduler selects a process for execution, the dispatcher
loads the relocation and limit registers with the correct values.

Because every address generated by a CPU is checked against these registers, we can protect both the operating
system and the other users'
programs and data from being modified by this running process.

The MMU maps the logical address dynamically by adding the value in the relocation register.

The mapped address is sent to memory.

CSE@CMRCET G RAVIKUMAR Page 5

 OPERATING SYSTEMS-UNIT-4

ii) Memory Allocation

One of the simplest methods for allocating memory is to divide memory into several fixed sized partitions.

Each partition may contain exactly one process.

Thus the degree of multiprogramming is bound by the number of partitions.

In this multiple partition method, when a partition is free, a process is selected from the input queue and is loaded
into the free partition.

When the process terminates the partition becomes available for another process.

In the variable partition scheme, the OS keeps a table indicating which parts of memory are available and which
are occupied.

Initially, all memory is available for user processes and is considered one large block of available of memory, a
hole.

Eventually, as you will see memory contains a set of holes of various sizes.

Memory is allocated to processes until, finally the memory requirements of the next process cannot be satisfied.

That is no available block of memory (or hole) is large enough to hold that process.

The OS can then wait until a large enough block is available or it can skip down the input queue to see whether
the smaller memory requirements of some other process can be met.

The system may need to check whether there are processes waiting for memory could satisfy the demands of any
of these waiting processes.

This procedure is Dynamic storage allocation problem.

Which concerns how to satisfy a request of size n from a list of free holes?

There are many solutions to this problem.

The First fit, Best fit, Worst fit strategies are used to select a free hole from the set of available holes.

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.

CSE@CMRCET G RAVIKUMAR Page 6

 OPERATING SYSTEMS-UNIT-4

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.

Simulations have shown that both first fit and best fit are better than worst fit in terms of decreasing time
and storage utilization. Neither first fit nor best fit is clearly better than the other in terms of storage utilization,
but first fit is generally faster.
Fragmentation

After some time that processes can not be allocated to memory because of small size and memory blocks
remains unused. This problem is called fragmentation.

Memory fragmentation can be internal as well as external.

First fit and best fit strategies for memory allocation suffer from external fragmentation.

As processes are loaded and removed from memory, the free memory space is broken into little pieces.

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.

Internal fragmentation

The memory allocated to a process may be slightly larger than the requested memory. The difference between
these two numbers is internal fragmentation.

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

Another solution is to the external fragmentation problem is to permit the logical address space of the processes
to be non contiguous.

[Link]
It is a Memory management scheme that permits the physical address space of a process to be non contiguous.

It avoids external fragmentation and the need for compaction.

The basic method for implementing paging involves breaking physical memory into fixed sized blocks called
frames(F) and breaking logical memory into blocks of same size called pages (P).

CSE@CMRCET G RAVIKUMAR Page 7

 OPERATING SYSTEMS-UNIT-4

When a process to be executed, its pages are loaded into any available memory frames from their source(Backing
Store).

The backing store is divided into fixed sized blocks that are of same size as the memory frames.

The hardware supports for paging is described in the following figure.

Every address generated by CPU is divided into two parts.

i) Page number(P)

ii) Page offset (d)

The page number is used as an index into page table .

The page table contains the base address of each page in physical memory.

This base address is combined with the page offset to define the physical memory address ie.. sent to memory
unit.

The paging model of memory is shown in figure.

CSE@CMRCET G RAVIKUMAR Page 8

 OPERATING SYSTEMS-UNIT-4

The page size or frame size is defined by the hardware.

The size of a page is typically a power of 2 varying between 512 bytes and 16 MB per page depending on
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
m
offset particularly easy. If the size of the logical address space is 2 , 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:

CSE@CMRCET G RAVIKUMAR Page 9

 OPERATING SYSTEMS-UNIT-4

CSE@CMRCET G RAVIKUMAR Page 10

 OPERATING SYSTEMS-UNIT-4

Paging hardware with TLB (Translation Look aside Buffer)

Hardware implementation of page table can be done several ways.

In the simplest case the page table is implemented as a set of dedicated registers.

The use of registers for page table is satisfactory if the page table is small.

If the page table is very large , we kept in main memory and page table base register(PTBR).

Points to the page table, with this scheme two memory access are needed to access a byte.

If we want to access location i, we must first index into the page table, using the value in the PTBR offset by
the page number for i. This task requires a memory access.

It provides us with the frame number, which is combined with the page offset to produce the actual address.
We can then access the desired place in memory.

With this scheme, two memory accesses are needed to access a byte (one for the page-table entry, one for
the byte). Thus, memory access is slowed by a factor of 2. This delay would be intolerable under most
circumstances.

To avoid this problem we use a special small, fast look up hardware cache called “Translation look aside buffer
(TLB)”.

TLB is high speed memory.

It consists of 2 parts a key(or Tag) and value.

CSE@CMRCET G RAVIKUMAR Page 11

 OPERATING SYSTEMS-UNIT-4

When the associative memory is presented with an item, the item is compared with all keys simultaneously. If the

item is found, the corresponding value field is returned.

It contains only a few of page table entries.

When a logical address is generated by CPU, its page number is presented to the TLB.

If page number is found (TLB Hit) its frame number is immediately available and is used to access memory.

If page number is not in the TLB (TLB miss) a memory reference to the page table must be made.

The percentage of times that a particular page number is found in the TLB is called the Hit Ratio.

Protection

Memory protection in a paged environment is accomplished by protection bits associated with each frame .

These bits are kept in page table.

We can create hardware to provide read only, read write or execute only protection.

One additional bit is generally attached to each entry in page table ie., valid or invalid bit.

When this bit is set to valid the associated page is in process logical address space.

When the bit is set to invalid the page is not in process logical address space.

CSE@CMRCET G RAVIKUMAR Page 12

 OPERATING SYSTEMS-UNIT-4

Shared pages

The advantage of paging is the possibility of sharing common code.

In a time sharing environment, consider a system that supports 40 users, each of whom executes a text
editor.

If the text editor consists of 150KB of code and 50 KB of data space, we need 8000 KB to support the 40 users.

Here we see three page editor ,each page 50KB in size,it is shared among three processes. Each process has
its own data page.

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(150KB) plus 40 copies of the 50 KB of data
space per user.

The total space required is now 2,150 KB instead of 8000 KB.

3. Segmentation
It is a memory management scheme that supports the user view of memory.

A logical address space is a collection of segments, each segment has a name and length.

CSE@CMRCET G RAVIKUMAR Page 13

 OPERATING SYSTEMS-UNIT-4

The address specify both segment name and the offset within the segment.

The user specifies each address by two quantities.

1. Segment name

2. Offset

< segmentname ,offset >

Normally the user program is compiled and the compiler automatically constructs segments reflecting the input
program.

A ‘c’ compiler might create separate segments for the following

i) The code

ii) Global variables

iii) The heap, from which memory is allocated

iv) The stacks, used by each thread

v) The standard ‘c’ library

Hardware

A logical address consists of two parts.

i) Segment number(s)

ii) Offset (d)

The segment no(s) is used as an index to the segment table.

CSE@CMRCET G RAVIKUMAR Page 14

 OPERATING SYSTEMS-UNIT-4

The offset(d) of the logical address must be between zero and limit of segment.

If it is not, we trap to the OS, when an offset is legal, it is added to segment based to produce the address in
physical memory of desired byte.

Example of segmentation

CSE@CMRCET G RAVIKUMAR Page 15

 OPERATING SYSTEMS-UNIT-4

[Link] Paging

A demand paging is similar to paging system, with swapping.

With demand paging a page is brought into main memory only when a reference is made to a location on
the page.

Lazy swapper concept is used in demand paging.

A lazy swapper never swaps a page into a memory unless that page will be needed.

Some form of h/w support is required to distinguish between those pages that are in memory and those
pages that are on the disk.

The valid, invalid bits scheme can be used for this purpose.

Each entry in the page table has a min of 2 fields ie., 1) page frame

2) Valid –Invalid bit

CSE@CMRCET G RAVIKUMAR Page 16

 OPERATING SYSTEMS-UNIT-4

If the process tries to access a page that was not brought into memory.

Access to page is marked invalid causes a page fault.

Steps in handling a page fault

1. Check an internal table for this process to determine whether the reference was a valid/invalid
memory access.

2. If the process was invalid then terminate the process. If it was valid but not yet brought into that
page.

3. Find a free frame.

4. Schedule a disk operation to read the desired page into newly allocated frame.

5. When the disk read is complete, modify the internal table kept with the process and the page table.

6. Restart the instruction that was interrupted the illegal address trap.

CSE@CMRCET G RAVIKUMAR Page 17

 OPERATING SYSTEMS-UNIT-4

Performance of Demand paging

Demand paging can significantly affect the performance of a computer system.

Let’s compute the effective access time for a demand paged memory.

Effective access time= (1-p) * ma + p * page fault time

ma denotes memory access ranges from 10 to 200 nano seconds.

p denotes probability of page fault(0 <=p<=1)

To compute the effective access time, we must know how much time is needed to service a page fault. A page
fault causes the following sequence to occur.

1. Trap to the os

2. Save the user registers and process state.

CSE@CMRCET G RAVIKUMAR Page 18

 OPERATING SYSTEMS-UNIT-4

[Link] Replacement

CSE@CMRCET G RAVIKUMAR Page 19

 OPERATING SYSTEMS-UNIT-4

6. Page replacement algorithms

1. FIFO(First in First out)

The simplest page replacement algorithm is FIFO algorithm. This algorithm associates with each page the
time when that page was brought into memory.

CSE@CMRCET G RAVIKUMAR Page 20

 OPERATING SYSTEMS-UNIT-4

When a page must be replaced, the oldest page is chosen.

We can create a FIFO queue to hold all pages in memory.

We replace the page at the head of the queue. When a page is brought into memory, we insert it at the
tail of queue.

We use the above reference string for a memory with 3 frames.

For our example reference string with 3 frame initially empty. The first 3 reference(7,0,1) cause page
faults and are brought into these empty frames.

The next reference (2) replaces page (7) because, page(7)was brought in first.

Since zero is the next reference and (0) is already in memory. We have no page fault for this reference.

This process continues as shown in figure.

Every time a fault occurs we show which pages are in our 3 frames.

There are 15 page faults all together.

2. Optimal page replacement algorithm

This algorithm which as the lowest page fault rate of all algorithms and will never suffer from belady’s
anomaly.

Such an algorithm doest exists and has been called OPT of MIN.

CSE@CMRCET G RAVIKUMAR Page 21

 OPERATING SYSTEMS-UNIT-4

Its simply “replaces the page that will not be used for the longest period of time.”

3. LRU (Least Recently Used) Page Replacement Algorithm.

CSE@CMRCET G RAVIKUMAR Page 22

 OPERATING SYSTEMS-UNIT-4

How to implement LRU replacement. An LRU page replacement algorithm may require hardware
assistance. The problem is to determine an order for the frames defined by the time of last use.

Two implementations are feasible.

1. Counters: In this 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 clock register are copied to time of use field in page table entry for that
page. In this way we always have the time of last reference to each page. We replace the page with
smallest time value. This scheme requires a search of the page table to find the LRU page and write to
memory for each memory access.

2. Stack: another approach to implement LRU replacement is to keep a stack of page number. Whenever a
page is referenced its removed from stack and put on the top. In this way the most recently used page is
always at the top of stack the LRU page is always at the bottom because entries must be removed from
the middle of stack its best to implement by using double linked list. Removing a page and putting it on
the top of stack. The tail pointer points to bottom of stack which is LRU page.

CSE@CMRCET G RAVIKUMAR Page 23