Project Three :: Virtual Memory Management
CIS343|510 Toward a Demand Paged Alg
Overview:

Below is the outline of one possible algorithm for implementing a demand paged memory management system within the context of Project #3. No claim is made as to its accuracy or completeness, since it has not been implemented. Nor is it the most efficient or elegant in design. In other words, this is not prescriptive. It is given only in the hopes that it may clarify exactly what the program is supposed to do and give some idea of how it may be written. I expect you will find many ways in which this can be improved or even corrected.

It is presupposed that you have a running version of Project #2 using Round Robin scheduling. Discussion of those data structures and algorithms is not repeated here. Since the abbreviated trace cannot be used, some adjustments to that program have to be made.

Adjustments to Project #2:

Trace::

Since a full trace must be used, that is what must be stored in memory when a job is being pseudo-executed. Since the trace consists of a mix of characters and integers, you may want to come up with a way of representing ‘r’, ‘w’ and ‘s’ as integers. For example, let ‘r’ be represented by -2, ‘w’ by -3, and ‘s’ by -4. This would allow you to store the trace as an integer array, as was the case in Project #2.

Data Holders

Constants::

PageSize - how many memory locations make up a page, and therefore also a page frame. You choose this value.

MemSize - how much memory is available in the system for user programs?

MultPDegree - what is the degree of multiprogramming of your system?

NumFrames - how many page frames are available? = MemSize/PageSize

MaxJobLen - What is the most number of instruction executions? Used to

determine the size of the job trace array.

Arrays::

JobTrace - a 2-dimensional array used to hold the job traces of currently active jobs.

dimension1 - MultPDegree active jobs

dimension2 - MaxJobLen*2 execution trace items

[Assuming each instruction is represented by 2 integers]

Linked Lists::

AvailFrames - which page frames are unoccupied? Can be a stack.

ReadyQ - Ready Queue

IOBQ - I/O Blocked Queue

PFBQ - PageFault Blocked Queue

Arrays of Structures::

[Note: arrays of structures can also be implemented as parallel arrays.]

MemFrame - page frames available for user programs

For each MemFrame( i ):

Occupied - is the frame occupied (Y/N)?

JobNum - if occupied, whose page?

PageNum - if occupied, which page?

RefBit - has this frame been referenced?

ModBit - has this frame been modified?

JobInfo - information about an active job

For each JobInfo( i ):

Pid - what is the job ID?

Status, etc. - if needed, what is the job’s status; etc.

Page - array of pages

For each Page( i ):

ResBit - is the page resident (in main memory)?

FrameNum - in which page frame is this page?

initialize

Set up the global structures and inital values needed

initialize as for Project #2

For i = 0 to NumFrames-1

Push i onto AvailFrames stack

main

Run the simulation. As for Project #2, except that each instruction must be pseudo-executed individually. Each time through the loop:

initialize

Project #2 Stuff

Loop:

If CPU is empty, then SysClock++

Else

Call Pseudo-execute(action,memloc,cpuJob)

Check IOBQ and PFBQ; if needed unblock jobs

As in Project #2, check if job is needs to come

into the system

If CPU is empty at this point then

If ReadyQ is nonempty, place job into CPU

EndLoop

Pseudo-Execute(action,memloc,JobNum)

Process one instruction execution.

Local Variables::

RefPage - which page is being referenced?

If action is syscall, then process as in Project #2

Else

RefPage = CalcPageNum(memloc,JobNum)

If RefPage of JobNum is resident then

Call PseudoRef(GetFrame(RefPage,JobNum),action)

Else

Generate a page fault (which includes placing

the job onto the PFBQ)

Call PagePlacementAlg(page,JobNum,action)

CalcPageNum(memloc,JobNum)

Calculate which page of the job is being referenced.

Notes::

JobNum can be the process id (pid) or it can be an index (0 to 4) into the array JobInfo. If it is the former, then you must store somewhere, possibly in the PCB of the job, that index.

Since the calculation is simple, this need not be a separate subroutine.

GetFrame(PageNum,JobNum)

Find out in which frame the page resides.

Notes::

This is actually just a retrieval from the JobInfo structure and need not be a separate subroutine. The retrieval code would look something like this:

JobInfo(JobNum).Page(PageNum).FrameNum

PagePlacementAlg(page,JobNum,action)

Find a page frame into which to place the page

Local Variables::

FrameNum - which page frame will be written into?

If AvailFrames is nonempty then

FrameNum = pop AvailFrames

Else

FrameNum = PageReplacementAlg( )

EndIf

Call ReadIntoMem(FrameNum,page,JobNum,action)

ReadIntoMem(FrameNum,page,JobNum,action)

Pseudo-read a page into a page frame by doing necessary bookkeeping

& charging overhead for the task

Mark these fields of MemFrame(FrameNum):

MemFrame(FrameNum).Occupied = True

MemFrame(FrameNum).JobNum = JobNum

Call PseudoRef(FrameNum,action)

PseudoRef(FrameNum,action)

Mark the appropriate fields of MemFrame for a page reference

MemFrame(FrameNum).RefBit = True

If action = “write” then

MemFrame(FrameNum).ModBit = True

PageReplacementAlg( )

Find a page to kick out. The pseudoCode below implements global replacement, with no fixed allocation for each job. The use of other replacement strategies would require some changes.

Local Variables::

FrameNum - which page frame was chosen for replacement

FrameNum = Clock( )

If MemFrame(FrameNum).ModBit = True Then

Pseudo-WriteToDisk(FrameNum)

MarkNonRes(FrameNum)

Return FrameNum

Pseudo-WriteToDisk(FrameNum)

Simulate writing a page frame back to disk.

If needed, update bookkeeping information

Charge overhead time for writing to disk

MarkNonRes(FrameNum)

Update JobInfo.

Find out which job the page frame belongs to and update the appropriate fields of JobInfo.

Clock( )

Implement the Clock algorithm. Return the number of the chosen page frame.

Suggestions::

Charging OS overhead

+ To simplify matters, charge a uniform amount for responding to syscalls

+ Charge for running the page placement algorithm

+ Charge for choosing a page to replace

+ Charge for writing a page to disk

+ Charge for reading a page from disk

Things to watch out for:

+ When a page fault occurs, the read or write cannot take place until the

desired page becomes resident. Since another job began to run in the

meantime, the instruction that caused the page fault must be executed

again, from scratch