Analysis of

Project #3 :: Paging

CIS343

 

Some Notes

 

Number of instructions executed:

          Factorial-5 :: 110

          Factorial-12 :: 208

          Isprime-900 :: 28

          Isprime-9497 :: 47,500

          Sieve-50 :: 653

          Sieve-9500 :: 135,100

Therefore, array size of 136,000 should suffice.

 

Pointers:

  w If we place the number of instructions as the first entry in the file, we can use for

     loop for reading.  It also gives us, useful for accounting purposes, a count of the

     number of instructions this process will execute.

 

Considerations:

  w We seek a compact representation that will allow us to use the instruction

     execution count as an index into an array of structures holding the execution trace

     information for each process.

 

Notice:

  w The first “action” taken on each instruction execution is a read.

  w Following that, we have exactly 4 possibilities:

      v No further action.

      v A second read.

      v A write.

      v A system call

  w System calls can be divided into two categories:

      v Syscall requesting service #1 or service #2.

      v Syscall requesting service #3.

  w The trace does not indicate the point of job termination, other than that it is the

     last instruction executed.  We have several options for dealing with this:

      v Alter the program that produces the execution trace.

      v Use text editor to alter the execution trace file produced.

      v Since we have a count of the number of instructions executed, write code to

          take that into account.  It turns out this is not hard to do.

 

Further points:

  w We can compute the page accessed when loading the file

  w If we record the action set, then we only need to record the page numbers to be

     referenced.

  w Syscall #3 requires special consideration

      v There are pages accessed

      v But the pages are accessed by the OS, while the process itself is blocked

      v There are multiple memory references Ž IDEA

            X Record the range of pages to be accessed

            X Since all the accesses are to sequential memory locations, record:

                Y First page to be referenced - as pageRange - low

                Y Last page to be referenced - as pageRange - high

  w In summary, we have identified 6 possible actions and 5 data items that need to be

     recorded for each instruction execution.

 

One Possible Solution

 

Overview:

  w Record, as an integer, for each instruction which action (or series of actions) is

     taking place.

      v #1 :: One read only

      v #2 :: Two reads

      v #3 :: One read and one write

      v #4 :: One read & syscall #1 or #2

      v #5 :: One read & syscall #3

      v #6 :: One read & program completion

  w Record for each instruction associated data.

      v Action

      v Page #1

      v Page #2

      v pageRange - low

      v pageRange - high

 

Particulars:

In addition to the action number - which is recorded for every instruction - here is what is to be recorded for each action type:

  w #1 - one read only

      v Page #1

  w #2 - two reads

      v Page #1

      v Page #2

  w #3 - one read, one write

      v Page #1

      v Page #2

  w #4 - syscall #1 or #2

      v Page #1

  w #5 - syscall #3

      v Page #1

      v pageRange - low

      v pageRange - high

  w #6 - job completion

      v Page #1

 

One Possible Simulation Algorithm

 

Overview:

  w While much of the program structure from Project #2 can be retained, the main

     loop has to be rewritten.

  w In addition some new interrupt handlers have to be written.

  w Main loop overview:

      v Check to see if any events are scheduled

            X If so, carry them out

      v If cpu has an executing job:

            X Simulate execution of one instruction

            X Otherwise, do nothing

      v Increment the system clock

 

Main loop:

  w Initialize system clock

  w While not quitting time:

      v If event time has arrived:

            X Call interrupt handler for scheduled event

      v Call simExecute

      v Increment system clock

 

simExecute:

  w If there is a CPUjob, carry out action for appropriate case:

      v Action #1

                   If OnePageRef(pageNum, "read") then

                             IC++

                   Else

                             call ihOnePageFault(pageNum)

      v Action #2

                   Let result = TwoPageRefs(pageNum1, "read",  pageNum2, "read")

                   If  result is 0 (no page faults) Then

                             IC++

                   Else

                             depending of value of results, call either

                                      ihOnePageFault, or

                                      ihTwoPageFaults with appropriate arguments

      v Action #3

                   Let result = TwoPageRefs(pageNum1, "read",  pageNum2, "write")

                   If  result is 0 (no page faults) Then

                             IC++

                   Else

                             depending of value of results, call either

                                      ihOnePageFault, or

                                      ihTwoPageFaults with appropriate arguments

      v Action #4

                   If OnePageRef(pageNum, "read") then

                             IC++

                             Call ihSyscall-1-2

                   Else

                             call ihOnePageFault(pageNum)

      v Action #5

                   If OnePageRef(pageNum, "read") then

                             IC++

                             Call ihSyscall-3(pageRangeLo, pageRangeHi)

                   Else

                             call ihOnePageFault(pageNum)

      v Action #6

                   If OnePageRef(pageNum, "read") then

                             Call ihJobFinish

                   Else

                             call ihOnePageFault(pageNum)