CSCI4630 - Fall 2006 - Program 1
(Counts as two assignments)
Due Monday, December 4



We saw four algorithms for placing processes into holes in memory:  best fit, worst fit, next fit and first fit.  Your job is to write a simulator which will take processes of varying sizes, load them into memory according to each of those rules, and swap processes out as needed to create a larger hole.  Let us make the following assumptions:
  1. Memory is of size 128MB
  2. The size of each process will be some whole number of megabytes in the range 1..128
  3. Memory is initially empty.  (We will ignore the operating system.)
  4. The first line of the input file will specify the algorithm to use for this run.
  5. Processes are scheduled dynamically; requests are sent to the memory manager as a series of requests to make sure processes are in memory, or if not, to swap them in.  The sizes of the processes are given every time.
  6. Requests to kill processes will also arrive, always right after the process has been run.  In this case, its space needs to be deallocated.  See the sample file to the right for the format.
  7. If a process needs to be loaded but there is no hole large enough to accomodate it, then processes should be swapped out, one at a time, until there is a hole large enough to hold the process that needs to be loaded.
  8. If a process needs to be swapped out, then the process which had been last scheduled least recently should be the one to go.  That is, we use the Least Recently Used algorithm.

You can use whatever data structure you wish (eg. linked list, bitmap) to simulate memory usage, but please make sure that the comments in the file clearly indicate what data structure you are using and how it is implemented. 

Each time a process is requested to be in memory, print a line such as:
  Load F, #proc=5, #holes=3, %mem=41, Avg%mem=40
Thus one line should be printed for each line in the file except for the first line and the "kill" lines.

#proc is the number of processes in memory
#holes is the number of holes
%mem refers to the percent of memory that is currently occupied by processes
Avg%mem gives the average of all the %mems up until and including the current process load.

When the last process has been killed, which will also be the first time since the start that memory becomes empty, summary stats should be printed:
  #swaps=33, avg #proc=14.4, avg #holes=6.3, Avg%mem = 62
where #swaps is the number of times a process had to be swapped out of memory to make room for an incoming process.  For example, if you have to remove 4 processes from memory to make room for one large incoming process, that counts as 4 swaps.

This program should be called holes.c, and should take a single commandline argument as indicated above:  a.out testfile1
Sample Input File


ff
A 30
B 20
C 75
A 30
D 80
C 75
A 30
D 80
A 30
C 75
B 20
A 30
C 75
B 20
E 55
B 20
kill B
E 55
D 80
A 30
kill A
E 55
kill E
D 80
C 75
D 80
C 75
kill C
D 80
kill D
Sample Run

ff.txt   ff.out
bf.txt   bf.out
nf.txt   nf.out
wf.txt   wf.out

fits.h   skeleton.cpp
Notes

The first line in the file will be either ff, wf, bf nf or ma (see below)

For extra credit, design your own algorithm, including alternatives to LRU, if you wish, and see if you can consistently beat any or all of the four algorithms.  The better your algorithm does, the more extra credit, up to 10 points, you will get.  That's what the "ma" means up above.

To make it easier on me, if you elect not to implement your own algorithm for the extra credit, then please have your program print a message such as "Not implemented," and then gracefully exit, whenever a file starting with "ma" is encountered.