CS5102: FOUNDATIONS OF COMPUTER SYSTEMS

LECTURE 39: MEMORY MANAGEMENT - IV

DR. ARIJIT ROY
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
INDIAN INSTITUTE OF TECHNOLOGY PATNA

The slides are based on the book: Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013
PAGING
❏ Physical address space of a process can be noncontiguous; process is allocated physical
memory whenever the latter is available
❏ Avoids external fragmentation
❏ Avoids problem of varying sized memory chunks
❏ Divide physical memory into fixed-sized blocks called frames
❏ Size is power of 2, between 512 bytes and 16 Mbytes
❏ Divide logical memory into blocks of same size called pages
❏ Keep track of all free frames
❏ To run a program of size N pages, need to find N free frames and load program
❏ Set up a page table to translate logical to physical addresses
❏ Backing store likewise split into pages
❏ Still have Internal fragmentation
BACKGROUND
Code needs to be in memory to execute, but entire program rarely used

Error code, unusual routines, large data structures; are all seldom used
 Ex: declared array of size 100 cells but only 10 cells are used
Entire program code not needed (in main memory) at the same time Consider ability to execute

partially-loaded program

Program no longer constrained by limits of physical memory Each program takes less

memory while running

 Thus, more [partially-loaded] programs can run at the same time
 Increased CPU utilization and throughput with no increase in response
time or turnaround time; more multi-programming and time-sharing

Less I/O needed to load or swap programs into/from memory

 Thus, each user program would run faster
BACKGROUND
Virtual memory – separation of user logical memory from physical memory

 As perceived by users; that programs exist in contiguous memory

 Abstracts physical memory: need not worry about memory requirements

Only part of the program needs to be in memory for execution

Logical address space can therefore be much larger than physical address space

 Programmers can work as if memory is an unlimited resource Allows address spaces

to be shared by several processes

Allows for more efficient process creation

More programs running concurrently; increased multi-programming and/or time-sharing Less I/O needed to load

or swap processes; hence, faster program execution

BACKGROUND
Virtual address space – logical view of how process is stored in memory

Process starts at address 0 with contiguous addresses until end of its address space Meanwhile, physical

memory organized in page frames; not contiguous MMU maps logical pages to physical pages (i.e., frames) in

memory

Virtual memory can be implemented via:

Demand paging

Demand segmentation
VIRTUAL MEMORY THAT IS LARGER THAN PHYSICAL MEMORY
DEMAND PAGING

Could bring an entire process into memory at load time.

Or bring a process’s page into memory only when it is needed

Less I/O needed, no unnecessary I/O Less memory needed

Faster response More users

Similar to a paging system with swapping (diagram on right)

Lazy swapper – never swaps a page into memory unless page will be
needed

Swapper that deals with pages is a pager

Page is needed  reference it;

invalid reference  abort

not-in-memory  bring to memory

BASIC CONCEPTS
When swapping in a process, the pager guesses which pages will be used before swapping it out again
The pager brings in only those needed pages into memory
 Thus, decreases swap time and amount of needed physical memory

Need new MMU hardware support to implement demand paging;

If pages needed are already memory resident

Execution proceeds normally

If page needed and is not memory resident;

Need to find the needed page from the disk and load it into memory
 Without changing program behavior
 Without programmer needing to change code
VALID-INVALID BIT
A valid–invalid bit is associated with each page-table entry;
(v  in-memory – memory resident ;
i  not-in-memory)
Initially valid–invalid bit is set to i on
all entries Example of a page table
snapshot:

During MMU address translation:

if valid–invalid bit in page-table entry is
i  there is a page fault
PAGE TABLE WHEN SOME PAGES ARE NOT IN MAIN MEMORY
PAGE FAULT
What if the process refers to (i.e., tries to access) a page not in-memory ?
The [first] reference (i.e., address) to that invalid page will trap to operating system and causes a
page fault

Procedure for handling a page fault

1. OS checks an internal table to see if reference is valid or invalid memory access
2. If
Invalid reference  abort the process
 address is not in logical address space of process
Just not in memory  page in the referred page from the disk
 logical address is valid but page is simply not in-memory

3. Find a free frame

4. Read the referred page into this allocated frame via scheduled disk operation
5. Update both internal table and page-table by setting validation bit = v
6. Restart the instruction that caused the page fault and resume process execution
STEPS IN HANDLING A PAGE FAULT
WHAT HAPPENS IF THERE IS NO FREE FRAME?
Many pages need to be loaded but not enough free frames available fro them

Memory is being used up by process pages; both, user and kernel processes
Also memory is in demand from the kernel, I/O buffers, etc

How much memory to allocate to I/O buffers, kernel, processes, … , etc

Solution: Page replacement; when paging in pages of a process but no free frames

Terminate the process? Big fat no

Swap out some process? Yes, but not always a good option

Find currently un-used frame to free it; Page it out and page in process page
 Replacing the un-used memory page with the new page
Performance – want an algorithm which will result in minimum number of page faults
Same page may be brought into memory several times
NEED FOR PAGE REPLACEMENT
BASIC PAGE REPLACEMENT ALGORITHM
The page-fault service routine is modified to include page replacement

1. Find the location of the desired page on disk

2. Find a free frame:
1. If there is a free frame, use it
2. If there is no free frame, use a page-replacement algorithm to select a
victim frame
3. Write the victim frame to the disk [if dirty]; change the page and the frame
tables accordingly
3. Read the desired page into the newly freed frame; change the page and frame tables
4. Continue the user process from where the page fault occurred

We have potentially two page transfers to do – increasing EAT

Only if no frames are free; one page in required and one page out required
PAGE REPLACEMENT
PAGE REPLACEMENT …
Prevent over-allocation of memory by modifying page-fault service routine to include page replacement

Use modify (dirty) bit to reduce overhead of page transfers – only modified
pages are written to disk

Each page or frame is associated with a modify bit

Set by the hardware whenever a page is modified

Page replacement completes separation between logical memory and physical memory – large virtual
memory can be provided on a smaller physical memory

A user process of 20 pages can be executed in 10 frames simply by using demand-paging and using a
page-replacement algorithm to find a free frame whenever necessary
PAGE- REPLACEMENT AND FRAME-ALLOCATION ALGORITHMS
Two major demand-paging problems : frame allocation and page replacement

Frame-allocation algorithm determines

How many frames to allocate to each process
Which frames to replace; when page replacement is required

Page-replacement algorithm
We want an algorithm which yields the lowest page-fault rate

Evaluate an algorithm by running it on a particular string of memory references

(the reference string) and computing the number of page faults on that string
String is just page numbers p, not full addresses
Repeated access to the same page does not cause a page fault Results depend on number of
frames available
In all our examples, the reference string of referenced page numbers is
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
for a memory with three frames
GRAPH OF PAGE FAULTS VERSUS THE NUMBER OF FRAMES
 FIFO PAGE REPLACEMENT ALGORITHM
[REFERENCE STRING = 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1 AND MEMORY = 3 FRAMES]

Each page brought into memory is also inserted into a first-in first-out queue
Page to be replaced is the oldest page; the one at the head of the queue

Our example yields 15 page faults

Can vary by reference string: consider 1,2,3,4,1,2,5,1,2,3,4,5

Adding more frames can cause more page faults!

 Belady’s Anomaly
FIFO ILLUSTRATING BELADY’S ANOMALY
 OPTIMAL PAGE REPLACEMENT ALGORITHM
[REFERENCE STRING = 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1 AND MEMORY = 3 FRAMES]

Replace the page that will not be used for longest period of time

Our example yields 9 page faults

Unfortunately, OPR is not feasible to implement

Because: we can’t know the future; i.e., what is the next page?
 We have assumed that we know the reference string. No, we don’t

OPR is used only for comparing with new algorithms; how close to the optimal?
 LRU PAGE REPLACEMENT ALGORITHM
[REFERENCE STRING = 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1 AND MEMORY = 3 FRAMES]
Use the recent past as an approximation of the near future
Replace the page that has not been used for the longest period of time
That is, the least recently used page
Associate time of last use with each page

Our example yields 12 page faults – better than FIFO but worse than OPT
Generally good algorithm and frequently used
Algorithm is feasible but not easy to implement.
LRU algorithm may require substantial hardware support
THANK YOU!

24