Assignment #9 Solution

$30.00

Description

What to submit: One zip file named <studentID>-hw9.zip(replace <studentID> with your own student ID). It should contain four files:

  • one PDF file namedhw9.pdffor Section 1.Write your answers inEnglish. Check your spelling and grammar. Include your name and studentID!

  • Section 2: Python source files. Include your name and student ID in the program comments ontop.

    • simplevm.py,typescript

  1. [40 points] ProblemSet

    1. [20 points]9.2A simplified view of thread states isReady,Running, andBlocked, where a thread is either ready and waiting to be scheduled, is running on the processor,orisblocked(forexample,waitingforI/O).ThisisillustratedinFigure

    1. Assuming a thread is in the Running state, answer the following questions, and explain youranswer:

      1. Will the thread change state if it incurs a page fault? If so, to what state will it change?

      2. Will the thread change state if it generates a TLB miss that is resolved in the page table? If so, to what state will itchange?

      3. Will the thread change state if an address reference is resolved in the page table? If so, to what state will itchange?

Fig. 9.30Thread state diagram for Exercise 9.2

    1. [10 points]9.4What is the copy-on-write feature, and under what circumstances is its use beneficial? What hardware support is required to implement thisfeature?

    2. [10 points]9.19What is the cause of thrashing? How does the system detect thrashing? Once it detects thrashing, what can the system do to eliminate this problem?

  1. [60 points] ProgrammingExercise

In this programming exercise, you are to implement paging algorithms for OPT, FIFO, LRU, and SecondChance in Python. To do this, create a SimpleVM class using the followingtemplateand rename itsimplevm.py.

classSimpleVM:

_ReplacementPolicies = [‘OPT’, ‘LRU’, ‘FIFO’, ‘SecondChance’]

definit(self, numPages, numFrames, replacementPolicy): self.numPages = numPages

self.numFrames = numFrames

if notreplacementPolicyinSimpleVM._ReplacementPolicies:

raiseValueError(‘Unknown replacement policy%s’ %replacementPolichy)

self.replacementPolicy=replacementPolicy self.pageTable=[Noneforiinrange(numPages)] self.valid=[‘i’foriinrange(numPages)]

self.frames=[Noneforiinrange(numFrames)]#storage self.dirty=[Falseforiinrange(numFrames)]

# weprefill swapspace content with chars ‘0’,’1′,’2′.. self.swapSpace=[chr(ord(‘0’)+i)foriinrange(numPages)]# aframeTable mapsaframeto thepage,ifany. self.frameTable=[Noneforiinrange(numFrames)]

# policy-specific code here

ifself.replacementPolicy == ‘LRU’:

# use a”stack” (really more likeaqueue)totrackage.self.stack= []

ifself.replacementPolicy in [‘FIFO’, ‘SecondChance’]:

#both FIFOandSecondChancearesomewhat like roundrobin# so youcould eitheruse acircular bufferorperhaps

#keepindex. Yourowncodehere!

ifself.replacementPolicy==’SecondChance’: self.reference=[Falseforiinrange(numFrames)]

defgetFreeFrame(self, pageNum):

#findafree frameifany,orreturn Noneif notfound.# seecommentintemplateformore info.

foriinrange(self.numFrames):

ifself.frames[i]isNone:

returni

returnNone

defpickVictim(self, future=None):

#findsapage whose frameis to beevictedtofulfill pagefault.#thisiscalled onlyifgetFreeFrame returns None

ifself.replacementPolicy == ‘OPT’:

# use future knowledge to pick victim

iffutureisNone:

raiseValueError(‘cannot pickOPTwithout future’)#Your code here!!!

#find page that won’tbeusedforlongest timeinfuture#Noteiffutureisempty list, thenanypageisok!

# in any case, return the victim page’s frame number.

ifself.replacementPolicy == ‘LRU’:

#Your code here!! pullthevictim fromthebottomof thestack# theassumptionis if wehave free framein thefirst place,# wewouldnotneedtoevictanybody.

ifself.replacementPolicy==’FIFO’:#Your code here!

# pick victim in FIFO order

ifself.replacementPolicy==’SecondChance’:#Your code here!!

# base on referenceBit

# if wehavenotreturnedbythen, it’sanunknownpolicy

raiseValueError(‘unknown poliy %s’ % self.replacementPolicy)

defpageIn(self, frameNum,pageNum):#Your code here!!

#calledtobringin apage from swap spaceto theframe.#pageNumisusedtofind locationinswap space.

# for simplicity, we use pageNum to index into swap space.

#Assume frameNumisfree,andthusnopageiscurrently usingit.#Updatethepage-to-frame tableandframe-to-page table,

# setvalidbit for thepage,andclear dirtybit for theframe.# incaseofSecondChance, also clear reference bit.

defpageOut(self, frameNum): # Your code here!!

#this flushesaframe (foragiven pageNum)toswapspace.#Note thatweonly markit asnot-dirty,but itdoesnot

#change stateofvalidbitbecause thatissomeone else’sdecision#whether they wanttoreclaimthepageorjust flushit.

#SimilartopageIn,weassume swap space usesthevirtualaddress# as wehave onlyoneprocess.

defgetFrame(self, pageNum, future=None):

#thisis autility thatmay behelpful,but notrequired.

# – see ifpageHit,if so,return valid frame# forread/write.# – ifpageFault,

# – see iffree frame available;if so,grabit;

# – but if nofree frame, pick victim, pageoutfirst,# fall thrutopage-in

# -page-inandreturntheframenumber

# -bookkeeping: lookup thepage# whose frame willbereassigned# – set itspageTable entrytoNone, clear that page’s validbit

# finally, return the frame number for caller to use.

defupdateAccess(self, frameNum, write=False):#Yourowncode!!indifferent casesbelow!ifself.replacementPolicy==’LRU’:

#Your code here!! find frameinstack;iffound,popit.# ineither case, push backonstack.

ifself.replacementPolicy==’SecondChance’:#Yourowncode!!-markthereferencebit

ifwrite: # forfuture use,ifsupportingwrite-accessself.dirty[frameNum]=True

defreadPage(self, pageNum,future=None):#Your code here!!

# get theframe number– cancallthegetFrame() methodforthis.# use theframe numberto get thedataso we canreturnit.

# do some bookkeeping by calling updateAccess

defwritePage(self, pageNum, data, future=None):#Your code here!!

#analogousto thereadPage, except# theframeiswrittentowithdata.# dobookkeeping with write=True

You will find the test cases in the template file. Here is a sample output of the program:

$python3 simplevm.py

————– policy (read): OPT————–

readPage(7)=’7′, pageTable=[None, None, None, None, None, None, None,0],valid=iiiiiiiv, frames=[‘7’, None, None]

readPage(0)=’0′, pageTable=[1, None, None, None, None, None, None,0],valid=viiiiiiv, frames=[‘7’, ‘0’, None]

readPage(1)=’1′, pageTable=[1,2,None, None, None, None, None,0],valid=vviiiiiv, frames=[‘7’, ‘0’,’1′]

readPage(2)=’2′, pageTable=[1,2, 0,None, None, None, None,None],valid=vvviiiii, frames=[‘2’, ‘0’,’1′]

readPage(0)=’0′, pageTable=[1,2, 0,None, None, None, None,None],valid=vvviiiii, frames=[‘2’, ‘0’,’1′]

readPage(3)=’3′, pageTable=[1, None,0, 2,None, None, None,None],valid=vivviiii, frames=[‘2’, ‘0’,’3′]

readPage(0)=’0′, pageTable=[1, None,0, 2,None, None, None,None],valid=vivviiii, frames=[‘2’, ‘0’,’3′]

readPage(4)=’4′, pageTable=[None, None, 0, 2, 1, None, None, None],

valid=iivvviii, frames=[‘2’, ‘4’, ‘3’]

readPage(2)=’2′, pageTable=[None, None, 0, 2, 1, None, None, None],

valid=iivvviii, frames=[‘2’, ‘4’, ‘3’]

readPage(3)=’3′, pageTable=[None, None, 0, 2, 1, None, None, None],

valid=iivvviii, frames=[‘2’, ‘4’,’3′]

readPage(0)=’0′, pageTable=[1, None,0, 2,None, None, None,None],valid=vivviiii, frames=[‘2’, ‘0’,’3′]

readPage(3)=’3′, pageTable=[1, None,0, 2,None, None, None,None],valid=vivviiii, frames=[‘2’, ‘0’,’3′]

readPage(0)=’0′, pageTable=[1, None,0, 2,None, None, None,None],valid=vivviiii, frames=[‘2’, ‘0’,’3′]

readPage(3)=’3′, pageTable=[1, None,0, 2,None, None, None,None],valid=vivviiii, frames=[‘2’, ‘0’,’3′]

readPage(2)=’2′, pageTable=[1, None,0, 2,None, None, None,None],valid=vivviiii, frames=[‘2’, ‘0’,’3′]

readPage(1)=’1′, pageTable=[1,2, 0,None, None, None, None,None],valid=vvviiiii, frames=[‘2’, ‘0’,’1′]

readPage(2)=’2′, pageTable=[1,2, 0,None, None, None, None,None],valid=vvviiiii, frames=[‘2’, ‘0’,’1′]

readPage(0)=’0′, pageTable=[1,2, 0,None, None, None, None,None],valid=vvviiiii, frames=[‘2’, ‘0’,’1′]

readPage(1)=’1′, pageTable=[1,2, 0,None, None, None, None,None],valid=vvviiiii, frames=[‘2’, ‘0’,’1′]

readPage(7)=’7′, pageTable=[1,2,None, None, None, None, None,0],valid=vviiiiiv, frames=[‘7’, ‘0’,’1′]

readPage(0)=’0′, pageTable=[1,2,None, None, None, None, None,0],valid=vviiiiiv, frames=[‘7’, ‘0’,’1′]

readPage(1)=’1′, pageTable=[1,2,None, None, None, None, None,0],valid=vviiiiiv, frames=[‘7’, ‘0’,’1′]

page faults= 9,pageins = 9,page outs=0

————– policy (write): OPT————–

writePage(7, ‘A’), frames=[‘A’, None, None], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘7’]

writePage(0, ‘B’), frames=[‘A’, ‘B’, None], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘7’]

writePage(1, ‘C’), frames=[‘A’, ‘B’, ‘C’], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘7’]

writePage(2, ‘D’), frames=[‘D’, ‘B’, ‘C’], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘A’]

writePage(0, ‘E’), frames=[‘D’, ‘E’, ‘C’], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’,’A’]

writePage(3, ‘F’), frames=[‘D’, ‘E’, ‘F’], swapSpace=[‘0’, ‘C’, ‘2’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(0, ‘G’), frames=[‘D’, ‘G’, ‘F’], swapSpace=[‘0’, ‘C’, ‘2’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(4, ‘H’), frames=[‘D’, ‘H’, ‘F’], swapSpace=[‘G’, ‘C’, ‘2’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(2, ‘I’), frames=[‘I’, ‘H’, ‘F’], swapSpace=[‘G’, ‘C’, ‘2’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(3, ‘J’), frames=[‘I’, ‘H’, ‘J’], swapSpace=[‘G’, ‘C’, ‘2’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(0, ‘K’), frames=[‘I’, ‘K’, ‘J’], swapSpace=[‘G’, ‘C’, ‘2’,‘3’,‘H’, ‘5’, ‘6’,’A’]

writePage(3, ‘L’), frames=[‘I’, ‘K’, ‘L’], swapSpace=[‘G’, ‘C’, ‘2’,‘3’,‘H’, ‘5’, ‘6’,’A’]

writePage(0, ‘M’), frames=[‘I’, ‘M’, ‘L’], swapSpace=[‘G’, ‘C’, ‘2’,‘3’,‘H’, ‘5’, ‘6’,’A’]

writePage(3, ‘N’), frames=[‘I’, ‘M’, ‘N’], swapSpace=[‘G’, ‘C’, ‘2’,‘3’,‘H’, ‘5’, ‘6’,’A’]

writePage(2, ‘O’), frames=[‘O’, ‘M’, ‘N’], swapSpace=[‘G’, ‘C’, ‘2’,‘3’,‘H’, ‘5’, ‘6’,’A’]

writePage(1, ‘P’), frames=[‘O’, ‘M’, ‘P’], swapSpace=[‘G’, ‘C’, ‘2’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(2, ‘Q’), frames=[‘Q’, ‘M’, ‘P’], swapSpace=[‘G’, ‘C’, ‘2’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(0, ‘R’), frames=[‘Q’, ‘R’, ‘P’], swapSpace=[‘G’, ‘C’, ‘2’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(1, ‘S’), frames=[‘Q’, ‘R’, ‘S’], swapSpace=[‘G’, ‘C’, ‘2’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(7, ‘T’), frames=[‘T’, ‘R’, ‘S’], swapSpace=[‘G’, ‘C’, ‘Q’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(0, ‘U’), frames=[‘T’, ‘U’, ‘S’], swapSpace=[‘G’, ‘C’, ‘Q’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(1, ‘V’), frames=[‘T’, ‘U’, ‘V’], swapSpace=[‘G’, ‘C’, ‘Q’,‘N’,‘H’, ‘5’, ‘6’,’A’]

page faults= 9,pageins = 9,page outs=6

————– policy (read):LRU————–

readPage(7)=’7′, pageTable=[None, None, None, None, None, None, None,0],valid=iiiiiiiv, frames=[‘7’, None, None]

readPage(0)=’0′, pageTable=[1, None, None, None, None, None, None,0],valid=viiiiiiv, frames=[‘7’, ‘0’, None]

readPage(1)=’1′, pageTable=[1,2,None, None, None, None, None,0],valid=vviiiiiv, frames=[‘7’, ‘0’,’1′]

readPage(2)=’2′, pageTable=[1,2, 0,None, None, None, None,None],valid=vvviiiii, frames=[‘2’, ‘0’,’1′]

readPage(0)=’0′, pageTable=[1,2, 0,None, None, None, None,None],valid=vvviiiii, frames=[‘2’, ‘0’,’1′]

readPage(3)=’3′, pageTable=[1, None,0, 2,None, None, None,None],valid=vivviiii, frames=[‘2’, ‘0’,’3′]

readPage(0)=’0′, pageTable=[1, None,0, 2,None, None, None,None],valid=vivviiii, frames=[‘2’, ‘0’,’3′]

readPage(4)=’4′, pageTable=[1, None, None,2, 0,None, None,None],valid=viivviii, frames=[‘4’, ‘0’,’3′]

readPage(2)=’2′, pageTable=[1, None,2,None,0,None, None,None],valid=viviviii, frames=[‘4’, ‘0’,’2′]

readPage(3)=’3′, pageTable=[None, None, 2, 1, 0, None, None, None],

valid=iivvviii, frames=[‘4’, ‘3’,’2′]

readPage(0)=’0′, pageTable=[0, None,2, 1,None, None, None,None],valid=vivviiii, frames=[‘0’, ‘3’,’2′]

readPage(3)=’3′, pageTable=[0, None,2, 1,None, None, None,None],valid=vivviiii, frames=[‘0’, ‘3’,’2′]

readPage(0)=’0′, pageTable=[0, None,2, 1,None, None, None,None],valid=vivviiii, frames=[‘0’, ‘3’,’2′]

readPage(3)=’3′, pageTable=[0, None,2, 1,None, None, None,None],valid=vivviiii, frames=[‘0’, ‘3’,’2′]

readPage(2)=’2′, pageTable=[0, None,2, 1,None, None, None,None],valid=vivviiii, frames=[‘0’, ‘3’,’2′]

readPage(1)=’1′, pageTable=[None, 0, 2, 1, None, None, None, None],

valid=ivvviiii, frames=[‘1’, ‘3’, ‘2’]

readPage(2)=’2′, pageTable=[None, 0, 2, 1, None, None, None, None],

valid=ivvviiii, frames=[‘1’, ‘3’,’2′]

readPage(0)=’0′, pageTable=[1,0, 2,None, None, None, None,None],valid=vvviiiii, frames=[‘1’, ‘0’,’2′]

readPage(1)=’1′, pageTable=[1,0, 2,None, None, None, None,None],valid=vvviiiii, frames=[‘1’, ‘0’,’2′]

readPage(7)=’7′, pageTable=[1,0,None, None, None, None, None,2],valid=vviiiiiv, frames=[‘1’, ‘0’,’7′]

readPage(0)=’0′, pageTable=[1,0,None, None, None, None, None,2],valid=vviiiiiv, frames=[‘1’, ‘0’,’7′]

readPage(1)=’1′, pageTable=[1,0,None, None, None, None, None,2],valid=vviiiiiv, frames=[‘1’, ‘0’,’7′]

page faults= 12,pageins = 12,page outs=0

————– policy (write): LRU————–

writePage(7, ‘A’), frames=[‘A’, None, None], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘7’]

writePage(0, ‘B’), frames=[‘A’, ‘B’, None], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘7’]

writePage(1, ‘C’), frames=[‘A’, ‘B’, ‘C’], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘7’]

writePage(2, ‘D’), frames=[‘D’, ‘B’, ‘C’], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘A’]

writePage(0, ‘E’), frames=[‘D’, ‘E’, ‘C’], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’,’A’]

writePage(3, ‘F’), frames=[‘D’, ‘E’, ‘F’], swapSpace=[‘0’, ‘C’, ‘2’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(0, ‘G’), frames=[‘D’, ‘G’, ‘F’], swapSpace=[‘0’, ‘C’, ‘2’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(4, ‘H’), frames=[‘H’, ‘G’, ‘F’], swapSpace=[‘0’, ‘C’, ‘D’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(2, ‘I’), frames=[‘H’, ‘G’, ‘I’], swapSpace=[‘0’, ‘C’, ‘D’,‘F’,‘4’, ‘5’, ‘6’,’A’]

writePage(3, ‘J’), frames=[‘H’, ‘J’, ‘I’], swapSpace=[‘G’, ‘C’, ‘D’,‘F’,‘4’, ‘5’, ‘6’,’A’]

writePage(0, ‘K’), frames=[‘K’, ‘J’, ‘I’], swapSpace=[‘G’, ‘C’, ‘D’,‘F’,‘H’, ‘5’, ‘6’,’A’]

writePage(3, ‘L’), frames=[‘K’, ‘L’, ‘I’], swapSpace=[‘G’, ‘C’, ‘D’,‘F’,‘H’, ‘5’, ‘6’,’A’]

writePage(0, ‘M’), frames=[‘M’, ‘L’, ‘I’], swapSpace=[‘G’, ‘C’, ‘D’,‘F’,‘H’, ‘5’, ‘6’,’A’]

writePage(3, ‘N’), frames=[‘M’, ‘N’, ‘I’], swapSpace=[‘G’, ‘C’, ‘D’,‘F’,‘H’, ‘5’, ‘6’,’A’]

writePage(2, ‘O’), frames=[‘M’, ‘N’, ‘O’], swapSpace=[‘G’, ‘C’, ‘D’,‘F’,‘H’, ‘5’, ‘6’,’A’]

writePage(1, ‘P’), frames=[‘P’, ‘N’, ‘O’], swapSpace=[‘M’, ‘C’, ‘D’,‘F’,‘H’, ‘5’, ‘6’,’A’]

writePage(2, ‘Q’), frames=[‘P’, ‘N’, ‘Q’], swapSpace=[‘M’, ‘C’, ‘D’,‘F’,‘H’, ‘5’, ‘6’,’A’]

writePage(0, ‘R’), frames=[‘P’, ‘R’, ‘Q’], swapSpace=[‘M’, ‘C’, ‘D’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(1, ‘S’), frames=[‘S’, ‘R’, ‘Q’], swapSpace=[‘M’, ‘C’, ‘D’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(7, ‘T’), frames=[‘S’, ‘R’, ‘T’], swapSpace=[‘M’, ‘C’, ‘Q’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(0, ‘U’), frames=[‘S’, ‘U’, ‘T’], swapSpace=[‘M’, ‘C’, ‘Q’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(1, ‘V’), frames=[‘V’, ‘U’, ‘T’], swapSpace=[‘M’, ‘C’, ‘Q’,‘N’,‘H’, ‘5’, ‘6’,’A’]

page faults= 12,pageins = 12,page outs=9

————– policy (read): FIFO————–

readPage(7)=’7′, pageTable=[None, None, None, None, None, None, None,0],valid=iiiiiiiv, frames=[‘7’, None, None]

readPage(0)=’0′, pageTable=[1, None, None, None, None, None, None,0],valid=viiiiiiv, frames=[‘7’, ‘0’, None]

readPage(1)=’1′, pageTable=[1,2,None, None, None, None, None,0],valid=vviiiiiv, frames=[‘7’, ‘0’,’1′]

readPage(2)=’2′, pageTable=[1,2, 0,None, None, None, None,None],valid=vvviiiii, frames=[‘2’, ‘0’,’1′]

readPage(0)=’0′, pageTable=[1,2, 0,None, None, None, None,None],valid=vvviiiii, frames=[‘2’, ‘0’,’1′]

readPage(3)=’3′, pageTable=[None, 2, 0, 1, None, None, None, None],

valid=ivvviiii, frames=[‘2’, ‘3’,’1′]

readPage(0)=’0′, pageTable=[2, None,0, 1,None, None, None,None],valid=vivviiii, frames=[‘2’, ‘3’,’0′]

readPage(4)=’4′, pageTable=[2, None, None,1, 0,None, None,None],valid=viivviii, frames=[‘4’, ‘3’,’0′]

readPage(2)=’2′, pageTable=[2, None,1,None,0,None, None,None],valid=viviviii, frames=[‘4’, ‘2’,’0′]

readPage(3)=’3′, pageTable=[None, None, 1, 2, 0, None, None, None],

valid=iivvviii, frames=[‘4’, ‘2’,’3′]

readPage(0)=’0′, pageTable=[0, None,1, 2,None, None, None,None],valid=vivviiii, frames=[‘0’, ‘2’,’3′]

readPage(3)=’3′, pageTable=[0, None,1, 2,None, None, None,None],valid=vivviiii, frames=[‘0’, ‘2’,’3′]

readPage(0)=’0′, pageTable=[0, None,1, 2,None, None, None,None],valid=vivviiii, frames=[‘0’, ‘2’,’3′]

readPage(3)=’3′, pageTable=[0, None,1, 2,None, None, None,None],valid=vivviiii, frames=[‘0’, ‘2’,’3′]

readPage(2)=’2′, pageTable=[0, None,1, 2,None, None, None,None],valid=vivviiii, frames=[‘0’, ‘2’,’3′]

readPage(1)=’1′, pageTable=[0,1,None,2,None, None, None,None],valid=vviviiii, frames=[‘0’, ‘1’,’3′]

readPage(2)=’2′, pageTable=[0,1, 2,None, None, None, None,None],valid=vvviiiii, frames=[‘0’, ‘1’,’2′]

readPage(0)=’0′, pageTable=[0,1, 2,None, None, None, None,None],valid=vvviiiii, frames=[‘0’, ‘1’,’2′]

readPage(1)=’1′, pageTable=[0,1, 2,None, None, None, None,None],valid=vvviiiii, frames=[‘0’, ‘1’,’2′]

readPage(7)=’7′, pageTable=[None, 1, 2, None, None, None, None, 0],

valid=ivviiiiv, frames=[‘7’, ‘1’,’2′]

readPage(0)=’0′, pageTable=[1, None,2,None, None, None, None,0],valid=viviiiiv, frames=[‘7’, ‘0’,’2′]

readPage(1)=’1′, pageTable=[1,2,None, None, None, None, None,0],valid=vviiiiiv, frames=[‘7’, ‘0’,’1′]

page faults= 15,pageins = 15,page outs=0

————– policy (write):FIFO————–

writePage(7, ‘A’), frames=[‘A’, None, None], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘7’]

writePage(0, ‘B’), frames=[‘A’, ‘B’, None], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘7’]

writePage(1, ‘C’), frames=[‘A’, ‘B’, ‘C’], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘7’]

writePage(2, ‘D’), frames=[‘D’, ‘B’, ‘C’], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘A’]

writePage(0, ‘E’), frames=[‘D’, ‘E’, ‘C’], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘A’]

writePage(3, ‘F’), frames=[‘D’, ‘F’, ‘C’], swapSpace=[‘E’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’,’A’]

writePage(0, ‘G’), frames=[‘D’, ‘F’, ‘G’], swapSpace=[‘E’, ‘C’, ‘2’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(4, ‘H’), frames=[‘H’, ‘F’, ‘G’], swapSpace=[‘E’, ‘C’, ‘D’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(2, ‘I’), frames=[‘H’, ‘I’, ‘G’], swapSpace=[‘E’, ‘C’, ‘D’,‘F’,‘4’, ‘5’, ‘6’,’A’]

writePage(3, ‘J’), frames=[‘H’, ‘I’, ‘J’], swapSpace=[‘G’, ‘C’, ‘D’,‘F’,‘4’, ‘5’, ‘6’,’A’]

writePage(0, ‘K’), frames=[‘K’, ‘I’, ‘J’], swapSpace=[‘G’, ‘C’, ‘D’,‘F’,‘H’, ‘5’, ‘6’,’A’]

writePage(3, ‘L’), frames=[‘K’, ‘I’, ‘L’], swapSpace=[‘G’, ‘C’, ‘D’,‘F’,‘H’, ‘5’, ‘6’,’A’]

writePage(0, ‘M’), frames=[‘M’, ‘I’, ‘L’], swapSpace=[‘G’, ‘C’, ‘D’,‘F’,‘H’, ‘5’, ‘6’,’A’]

writePage(3, ‘N’), frames=[‘M’, ‘I’, ‘N’], swapSpace=[‘G’, ‘C’, ‘D’,‘F’,‘H’, ‘5’, ‘6’,’A’]

writePage(2, ‘O’), frames=[‘M’, ‘O’, ‘N’], swapSpace=[‘G’, ‘C’, ‘D’,‘F’,‘H’, ‘5’, ‘6’,’A’]

writePage(1, ‘P’), frames=[‘M’, ‘P’, ‘N’], swapSpace=[‘G’, ‘C’, ‘O’,‘F’,‘H’, ‘5’, ‘6’,’A’]

writePage(2, ‘Q’), frames=[‘M’, ‘P’, ‘Q’], swapSpace=[‘G’, ‘C’, ‘O’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(0, ‘R’), frames=[‘R’, ‘P’, ‘Q’], swapSpace=[‘G’, ‘C’, ‘O’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(1, ‘S’), frames=[‘R’, ‘S’, ‘Q’], swapSpace=[‘G’, ‘C’, ‘O’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(7, ‘T’), frames=[‘T’, ‘S’, ‘Q’], swapSpace=[‘R’, ‘C’, ‘O’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(0, ‘U’), frames=[‘T’, ‘U’, ‘Q’], swapSpace=[‘R’, ‘S’, ‘O’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(1, ‘V’), frames=[‘T’, ‘U’, ‘V’], swapSpace=[‘R’, ‘S’, ‘Q’,‘N’,‘H’, ‘5’, ‘6’,’A’]

page faults= 15,pageins = 15,page outs=12

————– policy (read): SecondChance————–

readPage(7)=’7′, pageTable=[None, None, None, None, None, None, None,0],valid=iiiiiiiv, frames=[‘7’, None, None]

readPage(0)=’0′, pageTable=[1, None, None, None, None, None, None,0],valid=viiiiiiv, frames=[‘7’, ‘0’, None]

readPage(1)=’1′, pageTable=[1,2,None, None, None, None, None,0],valid=vviiiiiv, frames=[‘7’, ‘0’, ‘1’]

e, None,

None,

None,

None],

e, None,

None,

None,

None],

2, None,

None,

None,

None],

2, None,

None,

None,

None],

e, 2,

0,

None,

None,

None],

1, 2,

0,

None,

None,

None],

1, 2,

0,

None,

None,

None],

None,

0,

None,

None,

None],

readPage(2)=’2′, pageTable=[1, 2, 0, Non

valid=vvviiiii, frames=[‘2’, ‘0’, ‘1’]

readPage(0)=’0′, pageTable=[1, 2, 0, Non

0,

None,

None,

None,

None],

0,

None,

None,

None,

None],

0,

None,

None,

None,

None],

0,

None,

None,

None,

None],

0,

None,

None,

None,

None],

0,

None,

None,

None,

None],

valid=vvviiiii, frames=[‘2’, ‘0’, ‘1’] readPage(3)=’3′, pageTable=[1, None,0,valid=vivviiii, frames=[‘2’, ‘0’, ‘3’] readPage(0)=’0′, pageTable=[1, None,0,valid=vivviiii, frames=[‘2’, ‘0’, ‘3’] readPage(4)=’4′, pageTable=[1, None,Nonvalid=viivviii, frames=[‘4’, ‘0’, ‘3’] readPage(2)=’2′, pageTable=[None, None, valid=iivvviii, frames=[‘4’, ‘2’, ‘3’] readPage(3)=’3′, pageTable=[None, None, valid=iivvviii, frames=[‘4’, ‘2’, ‘3’] readPage(0)=’0′, pageTable=[2, None,1,valid=viviviii, frames=[‘4’, ‘2’, ‘0’] readPage(3)=’3′, pageTable=[2, None,1,valid=vivviiii, frames=[‘3’, ‘2’, ‘0’] readPage(0)=’0′, pageTable=[2, None,1,valid=vivviiii, frames=[‘3’, ‘2’, ‘0’] readPage(3)=’3′, pageTable=[2, None,1,valid=vivviiii, frames=[‘3’, ‘2’, ‘0’] readPage(2)=’2′, pageTable=[2, None,1,valid=vivviiii, frames=[‘3’, ‘2’, ‘0’] readPage(1)=’1′, pageTable=[2,1,None, valid=vviviiii, frames=[‘3’, ‘1’, ‘0’]

readPage(2)=’2′, pageTable=[None, 1, 2,

valid=ivvviiii, frames=[‘3’, ‘1’,’2′]

readPage(0)=’0′, pageTable=[0,1, 2,None, None, None, None,None],valid=vvviiiii, frames=[‘0’, ‘1’,’2′]

readPage(1)=’1′, pageTable=[0,1, 2,None, None, None, None,None],valid=vvviiiii, frames=[‘0’, ‘1’,’2′]

readPage(7)=’7′, pageTable=[0, None,2,None, None, None, None,1],valid=viviiiiv, frames=[‘0’, ‘7’,’2′]

readPage(0)=’0′, pageTable=[0, None,2,None, None, None, None,1],valid=viviiiiv, frames=[‘0’, ‘7’,’2′]

readPage(1)=’1′, pageTable=[0,2,None, None, None, None, None,1],valid=vviiiiiv, frames=[‘0’, ‘7’,’1′]

page faults= 14,pageins = 14,page outs=0

————– policy (write): SecondChance————–

writePage(7, ‘A’), frames=[‘A’, None, None], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘7’]

writePage(0, ‘B’), frames=[‘A’, ‘B’, None], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘7’]

writePage(1, ‘C’), frames=[‘A’, ‘B’, ‘C’], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘7’]

writePage(2, ‘D’), frames=[‘D’, ‘B’, ‘C’], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’, ‘A’]

writePage(0, ‘E’), frames=[‘D’, ‘E’, ‘C’], swapSpace=[‘0’, ‘1’, ‘2’, ‘3’,

‘4’, ‘5’, ‘6’,’A’]

writePage(3, ‘F’), frames=[‘D’, ‘E’, ‘F’], swapSpace=[‘0’, ‘C’, ‘2’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(0, ‘G’), frames=[‘D’, ‘G’, ‘F’], swapSpace=[‘0’, ‘C’, ‘2’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(4, ‘H’), frames=[‘H’, ‘G’, ‘F’], swapSpace=[‘0’, ‘C’, ‘D’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(2, ‘I’), frames=[‘H’, ‘I’, ‘F’], swapSpace=[‘G’, ‘C’, ‘D’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(3, ‘J’), frames=[‘H’, ‘I’, ‘J’], swapSpace=[‘G’, ‘C’, ‘D’,‘3’,‘4’, ‘5’, ‘6’,’A’]

writePage(0, ‘K’), frames=[‘H’, ‘I’, ‘K’], swapSpace=[‘G’, ‘C’, ‘D’,‘J’,‘4’, ‘5’, ‘6’,’A’]

writePage(3, ‘L’), frames=[‘L’, ‘I’, ‘K’], swapSpace=[‘G’, ‘C’, ‘D’,‘J’,‘H’, ‘5’, ‘6’,’A’]

writePage(0, ‘M’), frames=[‘L’, ‘I’, ‘M’], swapSpace=[‘G’, ‘C’, ‘D’,‘J’,‘H’, ‘5’, ‘6’,’A’]

writePage(3, ‘N’), frames=[‘N’, ‘I’, ‘M’], swapSpace=[‘G’, ‘C’, ‘D’,‘J’,‘H’, ‘5’, ‘6’,’A’]

writePage(2, ‘O’), frames=[‘N’, ‘O’, ‘M’], swapSpace=[‘G’, ‘C’, ‘D’,‘J’,‘H’, ‘5’, ‘6’,’A’]

writePage(1, ‘P’), frames=[‘N’, ‘P’, ‘M’], swapSpace=[‘G’, ‘C’, ‘O’,‘J’,‘H’, ‘5’, ‘6’,’A’]

writePage(2, ‘Q’), frames=[‘N’, ‘P’, ‘Q’], swapSpace=[‘M’, ‘C’, ‘O’,‘J’,‘H’, ‘5’, ‘6’,’A’]

writePage(0, ‘R’), frames=[‘R’, ‘P’, ‘Q’], swapSpace=[‘M’, ‘C’, ‘O’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(1, ‘S’), frames=[‘R’, ‘S’, ‘Q’], swapSpace=[‘M’, ‘C’, ‘O’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(7, ‘T’), frames=[‘R’, ‘T’, ‘Q’], swapSpace=[‘M’, ‘S’, ‘O’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(0, ‘U’), frames=[‘U’, ‘T’, ‘Q’], swapSpace=[‘M’, ‘S’, ‘O’,‘N’,‘H’, ‘5’, ‘6’,’A’]

writePage(1, ‘V’), frames=[‘U’, ‘T’, ‘V’], swapSpace=[‘M’, ‘S’, ‘Q’,‘N’,‘H’, ‘5’, ‘6’,’A’]

page faults= 14,pageins = 14,page outs=11