A2 Marking Scheme


Both questions were marked on correctness, style, and the accompanying reports.  Each of these three criteria were marked out of 100, and then weighted 0.6, 0.2, and 0.2, respectively, to yield a final mark out of 100.  Both questions were weighted equally.


The following are general problems encountered in either question.  Marks were deducted according to the severity of the error:


Common style problems



Common report problems




Here are some problems specific to Q1, along with the quantified penalty:


Common correctness problems for Q1



Here are some problems specific to Q2, along with the quantified penalty:


Common report problems for Q2


Common correctness problems for Q2



Q1 answers/commentary:


The correct output for test cases #1 and #2 of Q1 is as follows:


CPUs            Algorithm         Mean               Variance            Maximum

1          FCFS               35.90               643.83             77.74

1          SRTF               11.81               526.94             83.32

1          RR                   29.65               630.29             83.32

1          HRRN             18.95               283.10             62.09

2          FCFS               3.71                 53.73               22.72

2          SRTF               0.76                 4.62                 8.28

2          RR                   1.24                 1.71                 4.01

2          HRRN             3.71                 53.73               22.72


Test cases #3 and #4 were not marked; they were simply used to help diagnose problems with your implementations when marking.


FCFS was generally very well done by all students.  Almost no one had any problems.


Many people lost marks on SRTF for 2 CPUs since their program did not preempt the largest process.  If you don't preempt the largest process, you end up having to possibly preempt again immediately in order to ensure that the two smallest processes are running.  This isn't such a big deal with 2 CPUs, but consider the case with n CPUs -- you would have to preempt possibly n times!  This would introduce significant overhead in real life.  True, the assignment specified that you could consider there to be no scheduling overhead, but you should not have expected that claim to exempt you from writing an efficient algorithm.


Many people had problems with RR.  Some people left the CPU idle after a process finished executing before its quantum had expired.  Others failed to insert new processes at the end of the job queue.  Still others preempted processes at times other than quanta expiry.


A few people had problems with HRRN, most of which I expect simply result from a lack of understanding of the algorithm.  Many people on the newsgroup thought they could get away with altering the method or interval of priority recomputation, though this almost invariably led to incorrect results.


Q2 answers/commentary:


Because such a great emphasis was placed on the efficiency of your program, style was not marked as severely for Q2.  However, the report was more heavily scrutinized, and program correctness was of great concern.


Almost no one had problems with FIFO.  The correct numbers of page faults were 517, 408, and 356, in that order.  FIFO, as you know from the textbook, is not a stack algorithm, and therefore you needed three passes of the reference string.


LFU is a stack algorithm, since the n most recently used pages are part of the n+1 most recently used pages.  There is no single correct set of page fault numbers for LFU, for two reasons:  first, you were given the option of specifying which tie-breaking rule you used.  Second, due to a peculiarity of the ways you could choose to maintain data structures in a stack algorithm, it is possible to get minutely different results even when using the same tie-breaking rule.  Generally speaking, the numbers of page faults were around 618, 515, and 400, in that order.


PFF is not a stack algorithm.  While for memory sizes m and n such that m < n, the pages in m are a subset of the pages in n, the memory size is not necessarily the same at the same time for different thresholds.  That is, for thresholds a and b such that a < b, sometimes the memory size for a is smaller than the memory size for b, sometimes it's the same, and sometimes it's larger.  Any group which claimed to have successfully implemented PFF as a stack algorithm requiring just one pass of the reference string either did something that does not work in the general case, or really used more than one pass of the reference string as defined in the tutorials and newsgroup discussions.  The correct number of page faults for PFF for thresholds 6, 10, and 16 were 341, 280, and 250, respectively.  The numbers of faults per frame size were 21.1, 14.3, and 11.4, in that order.