Topic 3: SIMULATION: MEMORY ALLOCATION METHODS COMPARISON

Overview:


In this project, you'll implement and evaluate the following three different memory allocation methods by writing a MEMORY MANAGEMENT simulator.

Fixed partition with equal size
Divide memory into several fixed-sized partitions. Each partition may contain exactly one process. The size of the partitions are same.

Fixed partition with unequal size
Divide memory into several fixed-sized partitions. Each partition may contain exactly one process. The size of the partitions are different.

Dynamic partition with first fit
Initially, all memory is available for user processes and is considered one large block of available memory, a hole. When a process arrives and needs memory, we search for a hole large enough for this process. If we find one, we allocate only as much memory as is needed, keeping the rest available to satisfy future requests. If there is no enough space, compaction will be done. Compaction is to move the processes around to create one contiguous block of memory

First Fit: Allocate the first hole that is big enough.

Dynamic partition with best fit
Best Fit: Allocate the smallest hole that is big enough.

Dynamic partition with worst fit (next fit)
Worst Fit: Allocate the largest hole.


Your Task

Given a set of processes to be allocated space, your MEMORY ALLOCATION simulator should simulate the memory allocation of these processes based on a given memory allocation mothed. Your simulation should collect the following statistics: the average internal fragmentation, the average external fragment, the number of compaction for dynamic partition, the number of allocation fail, memory utilization.

In the end, you should compare the following memory allcation methods:

1. Fixed partition with equal size(FE)

2. Fixed partition with unequal size(FU)

3. Dynamic partition with first fit(DFF)

4. Dynamic partition with best fit(DBF)

5. Dynamic partition with worst fit(DWF)


Simulation Execution



Your simulation program will be invoked as: sim [-d] [-v] [-a algorithm] < input_file where -d stands for detailed information, -v stands for verbose mode, and -a stands for the execution of a given allcation method (only FE,FU,DEF,DBF,DWF should be acceptable input). You can assume only these flags will be used with your program, and that they will appear in the order listed. The output for the default mode (i.e., no flags), the detailed information mode, the verbose mode, and the allocation method mode is defined in the output format section. The -d, -v, and -a flags may be used separately or together.

Input Format


You should assume an maximum size of the memory, for example, 64MB. If the allcation cannot be satisfied for some process at some time, even after compaction for some methods, the number of allocation fail will be increased by 1 and this process will be killed. For fixed partition with equal size, you should assume the size of each partition, for example,8MB. The operating system will always take up 8MB. For fixed partition with unequal size, you should assume a size for each partition,for example,8MB(for OS),2MB,2MB,4MB,4MB, 4MB,4MB,6MB,6MB,8MB,8MB,8MB. Don't consider the case of overlay. That is, you should assume the size of space needed by any process is no more than 8MB.

The simulator input includes the number of processes that enters the system, for each process, the arrival time and the size of space it needs, the finishing time,

You should assume the processes listed in the input file will be in the order that the processes arrive. All these simulation parameters are integers. Your simulator obtains these parameters from the input file, which is in the following format.

   number_of_processes
   process_number arrival_time size_of_space finishing_time
   process_number arrival_time size_of_space finishing_time
   .
   .
   .  


The following is an example input file to the CPU simulation:

 
        4
        1 0 2 50
        2 12 8 80
        3 27 1 180
        4 28 7 100

You should create your own input file. Your program should generate at least 50 processes. You can assume the arrival interval of the processes is exponential distribution with the mean of 18 time units. The size of space needed by any process is no more than 8MB.

 

Output Format



In default mode (i.e., no flags are given), the output of the simulator consists of the total space required to allcate, internal fragmentation, external fradmentation and the memory utilization for each of the memory allcation methods at the time point that the allocation stops. As an example:



$sim < input_file


Fixed partition with equal size(FE):

Average Internal fragmentation is 15MB
Average External fragmentation is 6MB
the number of allocation fails is 20
Memory Utilization is 62.5%

Fixed partition with unequal size(FU):

Average Internal fragmentation is 10MB
Average External fragmentation is 2MB
the number of allocation fails is 16
Memory Utilization is 75%

If information on only one scheduling algorithm is desired, then the algorithm flag (i.e., -a) should be given with the name of the scheduling algorithm for which output is desired: FE or FU. As an example:



$sim -a FE< input_file


Fixed partition with equal size(FE):

Average Internal fragmentation is 15MB
Average External fragmentation is 6MB
the number of allocation fails is 16
Memory Utilization is 62.5%


In detailed information mode (i.e., -d flag is given), the output of the simulation consists of the total time required to execute the input processes to completion, the CPU utilization, and the arrival time, service time, I/O time, turnaround time, and finish time for each process. In the following example, this information is shown for SRTN only. If the scheduling algorithm is not specified, then detailed information should be given for each scheduling algorithm.



$sim -d -a SRTN < input_file


Fixed partition with equal size(FE):

Total space required is 140MB
memory Utilization is 62.5%

Process 1:

arrival time: 0
allocated space: 8MB
Internal fragmentation produced: 3MB
External franmentation decreased: 8MB
finish time: 45 units


Process 2:

arrival time: 5
allocated space: 8MB
Internal fragmentation produced: 5MB
External franmentation decreased: 8MB
finish time: 140 units


Process 3:

arrival time: 10
allocated space: 8MB
Internal fragmentation produced: 0MB
External franmentation decreased: 8MB
finish time: 55 units


.
.
.  

Process 9:

arrival time: 50
allocated space: 0MB(fail)

In verbose mode, the output of the simulation includes the memory allcation state changing after any event(process coming, process finishing). Specifically, the output includes every event that occurs, the time of the event, and the state transition:


At time 0: the initial state, the memory allocation state:

0-8: used by OS
8-64: hole

At time X: Process {id} comes, the memory changes the allocation state:

0-8: used by OS
8-16: used by process {1}
16-24: hole
24-32: used by process {id}
32-64: hole

Be sure to include events that occur at the same time.

Submit:

Write a 2-3 page paper describing your project, what problems you've faced and how you've overcome them. In your opinion, what is the best memory allocation methods? What are practical limitations on that method?

What to submit:

Submit your test data.

Submit ALL source code with detailed instructions on how and where to compile it, and how to make it run. You should submit a Makefile to build your code under GCC, Java, or whatever language you use. Note that Visual C++ also supports Makefiles, so if you use that, you can still export a makefile. I will test some of the code to make sure the numbers are not imagined.

Submit traces of execution (the trace of execution of each method; each method in separate files, etc.).

Submit your findings about each method; average numbers (internal fragmentation, etc.) (in addition to your 2-3 page paper)

Submit your paper describing the project.

Submit a file named: description.txt that describes what and where all the information is stored. (which file does what, which file contains results of which method, etc.). This is mostly so that I don't get lost in your project directory.

Note: All descriptions and text should be in TEXT format. If something "has" to be formated, use PDF.

You may use any language you wish, but you need to document what language you're using and how to compile code somewhere in your submission. Also comment your code! If I can't read it, it's wrong!

When submitting, you're very likely to have many files. You can compress them into a tar.gz or zip and submit that.

Tips: For many of you, this will be the biggest project you've ever worked on. It helps to organize the code from the start, to document everything, etc. Make the code readable (not just for you, but for me as well). Modularize your code. Work on 1 thing at a time. Start by generating the data and placing it in some file. Then implement basic algorithms and data structures like lists, sorting, etc. Then implement Fixed partition with equal size, make sure that works well, then implement Fixed partition with unequal size, probably reusing some parts of the Fixed partition with equal size code, etc.

And most importantly: Organize and design the project and know what you're doing before you start coding. (and don't wait until the last weekend to do it).

Good Luck!