Lab 3: Memory Management


Memory Management

The goal of this lab is to write a simple memory manager based on the topics covered in class. This lab has two parts.

  1. (75 pts) Write a memory manager that supports contiguous memory allocation. Implement both first-fit and best-fit policies in your memory manager. For simplicity, assume that processes do not grow or shrink, and that no compaction is performed by the memory manager. You should consider the following issues while designing your memory manager:
  2. (25 pts) Implement compaction in your memory manager. It is sufficient to implement compaction for the best-fit policy. Your memory manager should compact memory every time it sees external fragmentation (this will occur when a new process asks for memory and your memory manager is unable to allocate it due to fragmentation). A simple compaction policy that moves all currently running processes to the start of main memory and creating one hole at the high region of memory will get you full credit.

Getting Started

Unlike Lab 2, this assignment does not require you to use any special (e.g., synchronization) features of Java. Use the following template as a starting point:

class MemoryManager

public MemoryManager(int bytes, int policy)
{  // intialize memory with these many bytes.
    // Use first-fit if policy==0, best-fit if policy ==1


public int allocate(int bytes, int pid)
{ // allocate these many bytes to the process with this id
  //  assume that each pid is unique to a process
  // return 1 if successful
  // return -1 if unsuccessful; print an error indicating
  // whether there wasn't sufficient memory or whether 
  // there you ran into external fragmentation


public int deallocate(int pid)
{ //deallocate memory allocated to this process
  // return 1 if successful, -1 otherwise with an error message


public void printMemoryState()
{ // print out current state of memory 
  // Example: 
  // Memory size = 1024 bytes, allocated bytes = 24, free = 1000
  // There are currently 10 holes and 3 active process
  // Hole list:
  // hole 1: start location = 0, size = 202
  // ...
  // Process list:
  // process  id=34, start location=203, size=35
  // ...



Data structures

Your memory manager class should maintain two lists: a holeList and a processList The holeList is a list of holes, with the start location and size of each hole. The processList is the list of currently active process containing the process Id, the start location and size of each process. You are free to use any data structures (arrays, linked list, doubly linked list, etc) to implement these lists. This decision will also affect the use of search algorithms to search through these lists.

Input file

You program should take input from a input file and perform actions specified in the file, while printing out the result of each action. The format of the input file is as follows:

memorySize policy    //initialize memory to this size and use this policy
A  size pid          // allocate so much memory to this process
D   pid                // deallocate memory for this process
P                        // print current state of memory

An actual file may look as follows

8192 1
A 234 1
A 458 2
A 30  3
D 1
A 890 4
D 3
A 70 5
D 2
D 5
D 4

Note: We will strictly enforce policies on cheating. Remember that we routinely run similarity checking programs on your solutions to detect cheating. Please make sure you turn in your own work.