Project #3 :: Memory Management (Paging)

Code Template

CIS343

 

Declarations

Option Explicit

Const memSize = 300

Const pageSize = 20

Const quantum = 25

Const pageFaultBlockTime = 200

Const syscallBlockTime = 100

Dim numFrames As Integer

Dim action(1 To 6, 1 To 136000) As Integer

Dim page1(1 To 6, 1 To 136000) As Integer

Dim page2(1 To 6, 1 To 136000) As Integer

Dim rangelo(1 To 6, 1 To 136000) As Integer

Dim rangehi(1 To 6, 1 To 136000) As Integer

Dim jobLen(1 To 6) As Long

Private Type anEvent

   time As Long

   pid As Integer

   whEvent As String * 8

End Type

Dim mtk(1 To 30) As anEvent

Private Type pageTableEntry

  resBit As Boolean

  frameNumber As Integer

End Type

Private Type job_pcb

  state As String * 7

  entryTime As Integer

  progNum As Integer

  pagetable(0 To 999) As pageTableEntry

  IC As Long

End Type

Private Type frameTableEntry

  modBit As Boolean

  refBit As Boolean

  jobID As Integer

  pageNumber As Integer

End Type

Dim frameTable(0 To 29) As frameTableEntry

Dim job(1 To 30) As job_pcb

Const isprime900 = 1

Const isprime9497 = 2

Const fact5 = 3

Const fact12 = 4

Const sieve50 = 5

Const sieve9500 = 6

Const jobexitFile = 7

Dim cpuJob As Integer

Dim ReadyQ(0 To 5) As Integer

Dim readyQHead As Integer

Dim readyQTail As Integer

Const rqSize = 6

Dim NewQ(0 To 25) As Integer

Dim newQHead As Integer

Dim newQTail As Integer

Const newqSize = 26

Dim availQ(0 To 30) As Integer

Dim availQHead As Integer

Dim availQTail As Integer

Const availQSize = 31

Dim jobsInSystem As Integer

Dim numberOfEvents

Dim sysClock As Long

'Dim currentTime As Long

Dim secondPhase As Boolean

Const showRun = 20

 

Code

Private Sub cmdExit_Click()

 End

End Sub

 

Private Sub cmdInit_Click()

 Call ReadTraces

 Call InitGlobals

End Sub

 

Public Sub ReadTraces()

Dim i As Long

Dim iNum As Long

Dim whatdo As Integer

Dim ref As Integer

Dim nxt As Long

Dim nxtVal As Long

Dim nxtMem As Integer

Dim fileNo As Integer

Dim fileNum As Integer

Dim numInstructions As Long

 For fileNo = 1 To 6

  Select Case fileNo

   Case 1:

     Open App.Path & "\I900.txt" For Input As #isprime900

     fileNum = isprime900

     Debug.Print "File is IsPrime 900"

   Case 2:

     Open App.Path & "\I9497.txt" For Input As #isprime9497

     fileNum = isprime9497

     Debug.Print "File is IsPrime 9497"

   Case 3:

     Open App.Path & "\F5.txt" For Input As #fact5

     fileNum = fact5

     Debug.Print "File is Fact 5"

   Case 4:

     Open App.Path & "\F12.txt" For Input As #fact12

     fileNum = fact12

     Debug.Print "File is Fact 12"

   Case 5:

     Open App.Path & "\S50.txt" For Input As #sieve50

     fileNum = sieve50

     Debug.Print "File is Sieve 50"

   Case 6:

     Open App.Path & "\S9500.txt" For Input As #sieve9500

     fileNum = sieve9500

     Debug.Print "File is Sieve 9500"

  End Select

   Input #fileNum, numInstructions

   jobLen(fileNum) = numInstructions

   Input #fileNum, iNum

   For i = 1 To numInstructions - 1

    If -iNum <> i Then

     Debug.Print "Error - iNum "; iNum; " does not match i "; i

     Stop

    End If

    Input #fileNum, whatdo, ref

    If whatdo <> 0 Then

      Debug.Print "Error - Should be read - is: "; whatdo

      Stop

    End If

    page1(fileNum, i) = ref \ pageSize

    Input #fileNum, nxt

    Select Case nxt

     Case Is < 0:

       action(fileNum, i) = 1

       iNum = nxt

     Case 0:

       Input #fileNum, ref

       page2(fileNum, i) = ref \ pageSize

       action(fileNum, i) = 2

       Input #fileNum, iNum

     Case 10000:

       Input #fileNum, ref

       page2(fileNum, i) = ref \ pageSize

       action(fileNum, i) = 3

       Input #fileNum, iNum

     Case 500:

       Input #fileNum, ref

       Select Case ref

        Case 1, 2:

          action(fileNum, i) = 4

          Input #fileNum, iNum

        Case 3:

          action(fileNum, i) = 5

          Input #fileNum, nxtVal, nxtMem

          If nxtVal <> 0 Then

            Debug.Print "Error - should be READ, i.e., 0 - is: "; nxtVal

            Stop

          End If

          rangelo(fileNum, i) = nxtMem \ pageSize

          Input #fileNum, nxtVal

          While nxtVal = 0

            Input #fileNum, nxtMem, nxtVal

          Wend

          rangehi(fileNum, i) = nxtMem \ pageSize

          iNum = nxtVal

        Case Else:

          Debug.Print "Error - No such syscall val "; ref; "at :"; i

       End Select

     Case Else:

       Debug.Print "Error - No such action val "; nxt; "at :"; i

    End Select

   Next i

   ' Process last instruction

    If -iNum <> i Then

     Debug.Print "Error - no match at "; i

     Stop

    End If

    Input #fileNum, whatdo, ref

    If whatdo <> 0 Then

      Debug.Print "Error - Should be read - is: "; whatdo

      Stop

    End If

    page1(fileNum, i) = ref \ pageSize

    action(fileNum, i) = 6

    Debug.Print whatdo, ref

   Close #fileNum

 Next fileNo

 lblMesg.Caption = "Done Loading!"

End Sub

 

Public Sub InitGlobals()

Dim i As Integer

 For i = 1 To 30

  job(i).IC = 1

  job(i).state = "null"

 Next i

 Call SetSubmissionTimes

 Call InitMTK

 Call InitQs

 jobsInSystem = 0

 cpuJob = 0

End Sub

 

Public Sub SetSubmissionTimes()

 Initializes program numbers and job entry times

 numberOfEvents = 30

End Sub

 

Public Sub InitQs()

 Initializes all queues; availQ also gets a list of all available page frames

End Sub

 

Public Sub sortMTK(ByVal numItemsIn As Integer)

 Sorts the MTK array when a new event is scheduled

End Sub

 

Public Function removeRQ() As Integer

 Removes item from ReadyQ and returns its value

End Function

 

Public Function nextSlotRQ(ByVal index As Integer) As Integer

  nextSlotRQ = (index + 1) Mod rqSize

End Function

 

Public Sub addItemRQ(ByVal addItem As Integer)

 Adds item to ReadyQ

 readyQTail = nextSlotRQ(readyQTail)

 ReadyQ(readyQTail) = addItem

 job(addItem).state = "Ready"

End Sub

 

Public Function removeAvQ() As Integer

 Removes item from ReadyQ and returns its value

Dim rItem As Integer

 rItem = availQ(availQHead)

 availQHead = nextSlotAvQ(availQHead)

 removeAvQ = rItem

End Function

 

Public Function nextSlotAvQ(ByVal index As Integer) As Integer

 nextSlotAvQ = (index + 1) Mod availQSize

End Function

 

Public Sub addItemAvQ(ByVal addItem As Integer)

 Adds item to ReadyQ

End Sub

 

Public Function removeNewQ() As Integer

 Removes item from NewQ and returns its value

End Function

 

Public Function nextSlotNewQ(ByVal index As Integer) As Integer

 nextSlotNewQ = (index + 1) Mod newqSize

End Function

 

Public Sub addItemNewQ(ByVal addItem As Integer)

 Adds item to NewQ

End Sub

 

Private Sub cmdRunSim_Click()

 The main simulation loop

 secondPhase = False

 sysClock = 0

 Open App.Path & "\ExitTimes.txt" For Output As #jobexitFile

 While Not (QuittingTime)

   While sysClock = mtk(1).time And numberOfEvents > 0

     Call doOneEvent

   Wend

   Call executeInstruction

   sysClock = sysClock + 1

 Wend

 Call closeUpShop

End Sub

 

Public Sub ihJobEnters(ByVal curTime As Long, ByVal pid As Integer)

 Interrupt handler for job entering the system

End Sub

 

Public Sub ihUnblock(ByVal curTime As Long, ByVal pid As Integer)

 Interrupt handler to unblock a job

   If cpuJob > 0 Then addItemRQ (pid) Else Call makeCPUJob(pid)

End Sub

 

Public Sub ihQuantumExpires(ByVal curTime As Long, ByVal pid As Integer)

 Interrupt handler for quantum expiration (not needed for FIFO)

End Sub

 

Public Sub makeCPUJob(ByVal pid As Integer)

 Assigns CPU to the job indicated by “pid”

End Sub

 

Public Sub RegisterEvent(ByVal eTime As Long, ByVal pid As Integer, ByVal regEvent As String)

 Places an event onto the MTK (schedule of events)

End Sub

 

Public Sub giveCPU()

 If ReadyQ is not empty, gives CPU to job at head of ReadyQ

End Sub

 

Public Function isEmptyAvQ() As Boolean

 Checks to see if AvailQ is empty

 If nextSlotAvQ(availQTail) = availQHead Then isEmptyAvQ = True Else isEmptyAvQ = False

End Function

 

Public Function isEmptyRQ() As Boolean

 Checks to see if ReadyQ is empty

End Function

 

Public Function isEmptyNewQ() As Boolean

 Checks to see if NewQ is empty

End Function

 

Private Sub Form_Load()

 Sets value of global variable numFrames and opens output file

 numFrames = memSize \ pageSize

  Open App.Path & "\ShowRun.txt" For Output As #showRun

End Sub

 

Public Sub showMTK()

 Displays contents of MTK array - used only for debugging

Dim i As Integer

 Print #showRun, "Contents of Array MTK"

 For i = 1 To numberOfEvents

   Print #showRun, "Time: "; mtk(i).time

   Print #showRun, "Job #"; mtk(i).pid; "  "; mtk(i).whEvent

 Next i

 Print #showRun,

End Sub

 

Public Sub Remove1stEvent()

 Removes 1st event from MTK array, decrementing the number of events

End Sub

 

Public Function ReWordEvent(ByVal cEvent As String) As String

 Used to generate more informative output

End Function

 

Public Function QuittingTime() As Boolean

 Returns True if simulation is finished

  If secondPhase And jobsInSystem < 5 Then QuittingTime = True Else QuittingTime = False

 Code below is used to limit number of iterations - for debugging

' If sysClock > 2000 Then

'  QuittingTime = True

'  Else

'  If secondPhase And jobsInSystem < 5 Then QuittingTime = True Else QuittingTime = False

' End If

End Function

 

Public Function IdentifyJob(ByVal pid As Integer) As String

 Used to generate more informative output

End Function

 

Public Sub executeInstruction()

 Executes one instruction - called by main simulation loop

Dim faultCode As Integer

 If cpuJob > 0 Then

  Select Case action(job(cpuJob).progNum, job(cpuJob).IC)

   Case 1:

     If onePageRef(page1(job(cpuJob).progNum, job(cpuJob).IC), "read") Then

       job(cpuJob).IC = job(cpuJob).IC + 1

     Else

       Call ihOnePageFault(page1(job(cpuJob).progNum, job(cpuJob).IC))

     End If

   Case 2:

     If twoPageRefs(page1(job(cpuJob).progNum, job(cpuJob).IC), "read", page2(job(cpuJob).progNum, job(cpuJob).IC), "read", faultCode) Then

       job(cpuJob).IC = job(cpuJob).IC + 1

     Else

       Select Case faultCode

        Case 1: Call ihOnePageFault(page2(job(cpuJob).progNum, job(cpuJob).IC))

        Case 2: Call ihOnePageFault(page1(job(cpuJob).progNum, job(cpuJob).IC))

        Case 3: Call ihTwoPageFaults(page1(job(cpuJob).progNum, job(cpuJob).IC), page2(job(cpuJob).progNum, job(cpuJob).IC))

        Case Else:

         Debug.Print "Invalid fault code"

         Stop

       End Select

     End If

   Case 3:

     If twoPageRefs(page1(job(cpuJob).progNum, job(cpuJob).IC), "read", page2(job(cpuJob).progNum, job(cpuJob).IC), "write", faultCode) Then

       job(cpuJob).IC = job(cpuJob).IC + 1

     Else

       Select Case faultCode

        Case 1: Call ihOnePageFault(page2(job(cpuJob).progNum, job(cpuJob).IC))

        Case 2: Call ihOnePageFault(page1(job(cpuJob).progNum, job(cpuJob).IC))

        Case 3: Call ihTwoPageFaults(page1(job(cpuJob).progNum, job(cpuJob).IC), page2(job(cpuJob).progNum, job(cpuJob).IC))

        Case Else:

         Debug.Print "Invalid fault code"

         Stop

       End Select

     End If

   Case 4:

     If onePageRef(page1(job(cpuJob).progNum, job(cpuJob).IC), "read") Then

       job(cpuJob).IC = job(cpuJob).IC + 1

       Call ihSysCall_1_2

     Else

       Call ihOnePageFault(page1(job(cpuJob).progNum, job(cpuJob).IC))

     End If

   Case 5:

     If onePageRef(page1(job(cpuJob).progNum, job(cpuJob).IC), "read") Then

       job(cpuJob).IC = job(cpuJob).IC + 1

       Call ihSysCall_3(rangelo(job(cpuJob).progNum, job(cpuJob).IC-1), rangehi(job(cpuJob).progNum, job(cpuJob).IC-1))

     Else

       Call ihOnePageFault(page1(job(cpuJob).progNum, job(cpuJob).IC))

     End If

   Case 6:

     If onePageRef(page1(job(cpuJob).progNum, job(cpuJob).IC), "read") Then

       Call ihJobFinish

     Else

       Call ihOnePageFault(page1(job(cpuJob).progNum, job(cpuJob).IC))

     End If

   Case Else:

     Debug.Print "Invalid action"

     Stop

  End Select

 End If

End Sub

 

Public Sub doOneEvent()

 Carries out an event scheduled on the MTK array, calling Remove1stEvent

End Sub

 

Public Sub closeUpShop()

 Bookkeeping after simulation is finished

 Print #showRun,

 Print #showRun, "*  *  *  *  *  *  *"

 Print #showRun,

 Print #showRun, "Execution halted at "; sysClock

 Close #showRun

 Close #jobexitFile

 lblMesg.Caption = "Sim Done!"

End Sub

 

Public Function onePageRef(ByVal pageNum As Integer, ByVal refType As String) As Boolean

 If page given by pageNum is not resident, returns False.  Otherwise sets bits, as needed

End Function

 

Public Function twoPageRefs(ByVal page1 As Integer, ByVal refType1 As String,  Same as above, but for two page references

End Function

 

Public Sub ihOnePageFault(ByVal pageNumber As Integer)

Processes a page fault, blocking the job in the process

   Calls getPageFrame

End Sub

 

Public Sub ihTwoPageFaults(ByVal page1 As Integer, ByVal page2 As Integer)

Processes two page faults, blocking the job in the process

   Calls getPageFrame

End Sub

 

Public Sub ihSysCall_1_2()

Processes Syscalls #1 & #2

 Call blockCPUJob(syscallBlockTime)

End Sub

 

Public Sub ihSysCall_3(ByVal pageLo As Integer, ByVal pageHi As Integer)

Processes Syscall #3

End Sub

 

Public Sub ihJobFinish()

Processes execution completion of a job; don't forget to return the resident set of that job

  to the AVAIL list.

End Sub

 

Public Sub blockCPUJob(ByVal amtBlock As Integer)

 Pseduo-places a job onto the blocked queue

 Schedules unblock time using “amtBlock”; calls giveCPU to find another job to run

End Sub

 

Public Function getPageFrame(ByVal pageNum As Integer) As Integer

Finds an open page frame - 1st looks on the AvailQ; if that fails, calls “modClock” to find a page to replace

   After that does bookkeeping needed for frameTable

End Function

 

Public Function modClock() As Integer

Calls “doStepOne” and “doStepTwo” functions to carry out the steps of the modified Clock page replacement alrorithm

End Function

 

Public Function doStepOne(ByRef frameNum As Integer) As Boolean

Carries out the first step of the modified clock algorithm

End Function

 

Public Function doStepTwo(ByRef frameNum As Integer) As Boolean

Carries out the second step of the modified clock algorithm

End Function

 

Public Sub simpPageFault(ByVal pageNumber As Integer)

Called by ihSysCall_3, since it does not block a job (or a job may be blocked a multiple of times)

End Sub