Operating System Programming Assignment

simulation of contiguous allocation Memory management

For This assignment, you are to write a program which simulate two memory allocation strategies under the MVT(Multiprogramming with Bariable number of Tasks) model: Best Fit and Worst Fit. These are described briefly in the textbook and references. This assignment is intended to give you more insight and understanding in two particular areas : first the operation of storage placement algorithms; second, the implementation of Operating Systems software. In addition of course this assignment should sharpen your valuable programming skills.

In assition to the straight-forward implementation of these algorithms your program implement coalescence of adjacent free memory blocks(which is possible whenever a memory block is freed) and compaction of fragmented memory (which is possible whenever no free block is of sufficient size to fulfill a request) Of course there may by occasions when a request cannot be fulfilled even memory if has been compacted

Finally your program must print a nicely formatted readable summary of the memory allocation activity for each strategy at the time of each request. in particular your program must report the address of each memory allocation/free request, you must also print a summary consisting of the total number of bytes free the number of contiguous blocks free and the average size of these blocks(this is easy : just divide the number of free bytes the number of free blocks)

INPUT

The input to this program is simple :  the fist line contains an integer giving the size of real memory in kilobytes. Following this are pairs of integers describing memory requests. The first integer in the pair is a request id, the second is the amount(in kilobytes) of memory requested If that amount is zero, then the request is to free memory previously requested under the same request id. No request id will request additional memory(i.e a request id N for S kilobytes cannot be followed later by a request id N for any non-zero kilobytes)

EXAMPLE

As a short examle, consider the following input :

256

1 64 2 64 3 32 4 16 1 0 3 0 5 32 2 0

This should prouce output similar to the following:

MEMORY　SIZE : 256K

REQUEST 1 : 64K

Best Fit : Allocated at address 0

192 free, 1 block(s), average size = 192K

Worst Fit : Allocatted at address 0

192 free, 1 block(s), aberage size =192K

REQUEST 2 : 64K

Best Fit : Allocated at address 64K

128 free, 1 block(s), average size = 128K

Worst Fit : Allocatted at address 64K

128 free, 1 block(s), aberage size =128K

REQUEST 3 : 32K

Best Fit : Allocated at address 128K

96 free, 1 block(s), average size = 96K

Worst Fit : Allocatted at address 128K

96 free, 1 block(s), aberage size =96K

REQUEST 4 : 16K

Best Fit : Allocated at address 160K

80K free, 1 block(s), average size = 80K

Worst Fit : Allocatted at address 160K

80K free, 1 block(s), aberage size = 80K

FREE REQUEST 1 : (64K)

Best Fit : Freed at address 0

144K free, 2 block(s), average size = 72K

Worst Fit : Freed at address 0K

144K free, 2 block(s), aberage size =72K

FREE REQUEST 3  (32K)

Best Fit : Freed at address 128K

176K free, 3 block(s), average size = 59K

Worst Fit : Freed at address 128K

176K free, 3 block(s), aberage size =59K

REQUEST 5 : 32K

Best Fit : Allocated at address 128K

144 free, 1 block(s), average size = 72K

Worst Fit : Allocatted at address 176K

144 free, 1 block(s), aberage size =48K

FREE　REQUEST ２ （64K)

Best Fit : Freed at address 64K

Coalescing blocks at addresses OK and 64K

208K free, 2 block(s), average size = 104K

Worst Fit : Freed at address 64K

Coalescing blocks at addresses 64K and 128K

Coalescing blocks at addresses OK and 64K

208K free, 2 block(s), average size = 104K