Project 5
Fall 2005
Extra Credit
Due Date: Beginning of class, Last day of classes.
References.
- "Understanding Unix/Linux Programming", Bruce Molay.
- Second part (malloclabB.html)
- The "make" demo from class (as a tarball): MakeDemo.tar
Requirements.
- In this lab you will be creating a memory allocator.
- This lab has three purposes:
- For you to gain experience and comfort in directly managing memory.
- For you to demonstrate mastery of several algorithms for memory management.
- For you to evaluate these algorithms.
- You will receive partial credit for each part that you complete.
- Your program must be user friendly.
Details
I am providing you with a first-fit memory allocator named "myAllocator" written in the 'C' programming language.
MyAllocator can be used as a replacement for malloc by linking it with "malloc.c"
Its "resizeRegion()" method (which allows an allocated memory region to be increased)
ineptly does not consider borrowing space from the successor block should it be free
(this is documented in resizeRegion's comments). For the first part of this assignment,
you should:
- Improve the implementation of resizeRegion().
- implement these altermative allocators:
- next-fit (name this method nextFitAllocRegion)
- best-fit (name this method bestFitAllocRegion)
You should test your modified memory arena mangers for proper function, both as
stand-alone allocators and as malloc() replacements. I encourage you to share these
test programs with each other.
My allocator is in the following tarball: myMalloc.tar. The files can be extracted to
a directory named "myMalloc" using the command "tar xf myMalloc.tar"
OS Lab -Memory Allocator Evaluation
In this lab, you should evaluate the three your memory allocators (first fit, next
fit, best fit) by constructing a program that allocates and frees memory for an
extended period of time. This program terminates and prints statistics on memory
utilization and execution cost at the first time a memory allocation request fails.
Your allocator should be dividing an arena whose initial size is 2MB, and does not
grow.
The program proceeds in rounds. In each round i, a random integer between 1 and 10 is
drawn, which indicates the number of regions to be allocated in round i. Each
region's size should be randomly selected in the range of 8..1008 as (x mod 1000) + 8
where x is a randomly generated integer read from an input file. Recall that % is the
mod operator in "c".
At the end of each round, the first region allocated for that round is freed.
I have provided a text file mallocLab-rands.txt that contains a pseudo-random
sequence of integers. When your program needs a random number in the range
[min..max], do so using a function udri(min, max) that
- reads the next integer from the file lab3-rands.txt to variable v
- returns (v mod (max-min)) + min
What you should report the first time a malloc fails.
- For internal and external fragmentation:
Amount of memory consumed by fragmentation of each type, and the fraction of memory lost to it.
- For Overhead:
total amount & fraction of memory consumed by overhead.
- For allocated regions
Total amount of memory & fraction of total arena size allocated to processes.
This might be a measure of efficiency.
- size of the allocation request that failed.
- average time to allocate one block, measured in user time. You must
also measure wall-clock time and
therefore be able to detect if your program was preempted (ready) or
blocked for a significant amount of time.
- You must also report
for each type of fragment & each allocated region: count, maximum & minimum sizes
Review of overhead and fragmentation
- External Fragmentation: (free blocks)
This is the available memory that could be allocated to user processes but is
not of use because the available "fragments" are smaller than the size requested.
- Internal Fragmentation
This is the memory provided to user processes that they didn't request and
therefore is wasted.
- Overhead:
The amount and fraction of memory consumed by the arena's control blocks. Unlike
fragments, this memory is not wasted since it is being used by the allocator.
This is the total size of prefixes & suffixes.
Debugging Hint: There is a systems program named strace that will trace all
of the signals and system calls that a program receives. See the man page.
Administrative concerns.
- Every file in your solution must contain a comment
giving your name and the assignment number. This comment must list every function
that is defined in the file and the purpose of each.
- There must also be a separate commnent before the main function. This
comment should briefly describe the purpose of the program, describe
how it is implemented, given the major interface elements, etc.
- Finally, each function (including the main function) must have a beginning
comment that includes the following components:
- The name of the function
- The function inputs and outputs
- Changes to any global variables or kernel data structures
- System calls made from the function
- Your program must also have appropriate comments. You do not have to comment each line
of the program, but you must comment each section, feature, and functional unit of the code.
- Your program must also be appropriately formatted with tabs, spaces, etc. You will be
penalized if your code is not easy to read.
Deliverables.
You must demonstrate your program to me.
You must hand in a hard copy of all code that you use in
your solution.
You must also put a copy of all source code that you use in
your solution on the Linux Server.
Revision History
| Date |
Revision |
| 14 November |
PS posted |
|
|
