Question

1. Project Overview
In this project, we will examine Main memory management in systems without works will memory. The memory manager of such a system must maintain a list of free spaces, called holes. Processes can request and response a variable sizes are invoking the appropriate functions of the memory manager.
Your tasks are the following:
1. Design a memory manager that supports at least two different allocation strategies, such as first-fit, next-fit, best-bit, or worst -fit.
2. Evaluate the different strategies by comparing how well they maintain the available memory.

2. The Memory Manager
The memory manager is a set of functions and manages a hypothetical physical memory.

2.1 Main Memory
the memory manager is intended to manager linear physical memory. While developing the manager, we need no access to the actual physical memory of the system. Instead, we can emulate physical memory by allocating a sequence of consecutive bites, and develop all the necessary functions using this emulated main memory. The functions use pointers instead of physical addresses.
A main memory of size mem_size may be created in one of two ways:
1. by using a dynamic memory management function of the OS, such as mm = malloc(mem_size) in UNIX.
2. I declaring the character array, mm[mem_size], that represents the physical memory.
In both cases, we obtain a sequence of mem_size consecutive bytes—the simulated main memory. The pointer mm corresponds to physical address 0 of the actual physical memory. All holes and allocated blocks are maintained by the memory manager within this main memory array. (Note that type-casting must be used whenever the tag, size, and pointer fields, which are of different types, are written to or read from this memory.)

2.2 The User Interface
The memory manager must provide the following functions that can be invoked by other processes:
1. void *mm_request(int n)
This function requests a block of n consecutive bytes of memory. If the request can be satisfied, it returns a pointer to the first usable byte of the allocated block. It request cannot be specified—because there is no homework enough where the parameter n is illegal (e.g., a negative number)—it returns NULL. (Note that this function is analogous to the malloc function of UNIX.)
2. void mm_release(void *p)
This function replaces the previously allocated block of memory, pointed to by the pointer p. If the released block is adjacent to another hole, the function must coalesce the holes to prevent the fragmentation of memory into increasingly smaller holes. If released block is surrounded by allocated blocks, is simply appended to the list of holes. (Note that this function is analogous to the free function of UNIX.
3. void *mm_init(int mem_size)
This function initializes the memory to become a single hole by creating the appropriate tag, size, and pointer fields. It returns the pointer mm introduced in the previous section.

3. The Simulation Experiment
Implement two or more versions of the memory manager by varying the allocation strategy. The possible choices are first-fit, next-fit, best-bit, or worst -fit. Then design and carry out an experiment that will compare the performance of the chosen allocation strategies in terms of:
1. average memory utilization;
2. average number of steps needed to find an appropriate hole.
To set up the simulation experiment, let us make the following assumptions. Request and release calls arrive at the manager in two separate queues. Releases are always processed first. Since any release is immediately satisfiable, the queue of releases is always empty. The request may or may not be satisfiable, depending on whether there is a hole large enough to accommodate the request. If that is not the case, request remains on the queue until adequate space has been freed by subsequent release operations. The request queue is processed in FIFO order; otherwise, starvation could occur.
Under these assumptions, we can model the behavior of the memory manager as follows. We start in a state where memory already consists of occupied blocks and holes; there is no release request, and the request of the head of the queue cannot be satisfied. At this time, the manager cannot do anything but wait for the next release. During this time, the memory allocation does not change. When a release is processed, the manager attempts to satisfy the request at the head of the queue. If this fails, the manager again waits for the next release. If the request succeeds, the manager immediately attempts to satisfy the next request in the queue, and so on. Thus, following every release, zero or more pending requests are satisfied, depending on the size of the released block and the sizes of the pending requests.
To evaluate the effectiveness of different allocation strategies, we must assume that memory is always filled to maximum capacity. This means, we assume that the stream of request is unbounded, and the queue was never empty.
The following is a skeleton of the simulation experiment based on the above assumptions. It gathers the performance statistics for one chosen allocation strategy.
1. for (i=0; I < sim_steps; i++) {
2.    do {
3.       get size n of next request // see section 3.1
4.       mm_request(n)
5.    } while (request successful)
6.    record memory utilization // section 3.2
7.    select block p to be released // section 3.3
8.    release(p)
9. }
The program consists of a main loop (line 1), which is repeated for a number of simulation steps (sim_steps). For each iteration of the outer loop, the program performs the following tasks. The inner loop (lines 2-5) attempt to satisfy as many of the pending requests as possible. Each request is generated on the fly by getting a random number n, to represent the request size (line 3).
Once a request fails, the memory manager must wait until a block is released. Until then, the current memory allocation does not change, and we can record the current memory use. (Note that we are making the implicit assumption that the time during which a block resides in memory is independent of the block size. Thus, each iteration of the outer loop represents a constant interval of time during which the memory does not change.)
Next, one of the allocated blocks, p, is selected and released (lines 7-8). This frees some space that allows the simulation to proceed with the next iteration.

3.1 Generating Request Sizes
Let us assume that request sizes can be approximated using a Gaussian distribution. Thus, we can generate each new request size, n, using the function:
n = gauss (a, d)
where a is the average request size and d is the standard deviation. (Most math libraries will provide a set of such distribution functions.) Choosing a close to zero means that the average request will ask for just a few bytes of memory; a large a implies that processes typically request large blocks of memory. The standard deviation determines the shape of the Gaussian curve. A small d will result in a steep curve, implying that the majority of requests are clustered close to the mean; a large d implies that the distribution of sizes is more uniform.
Regardless of the values of a and d, the number n ranges from minus to plus infinity. Thus, we must truncate the range to reflect the physical size of memory. Means, whenever n exceeds mem_size, is discarded, because request exceeds total memory size could never be satisfied. You must also discard all negative values n (or use their absolute values) since all memory blocks are always greater than zero. (A block of size zero is, in principle, possible, but useless.)
3.2 Gathering Performance Data
There are two types of performance data we must gather. Memory utilization is expressed as the ratio of the allocated space to the total memory size. One such value is obtained during each duration of the simulation. These values may be accumulated to file and averaged at the end. Alternatively, a running average may be computed during each simulation run.
The second performance value is the average search time, i.e., number of steps needed to satisfy a request. This may be gathered by instrumenting the mm_request function for each memory allocation strategy. It must keep track of the number of holes that must be examined for each request, and compute average over the duration of the simulation run.
3.3 Choosing a Block to Release
if we assume that the time he given block stays in memory is independent of its size, we can select the block to be released during each iteration at random. The simulation program must keep track of all the allocated blocks; he linked list is the most appropriate data structure for that purpose. If there are k elements on the list of allocated blocks, we chose a random number, p, between one and k, and release the block at position p on the list.

4. Summary of Specific Tasks
1. Design and implement the three functions of the memory manager. Implement at these two different allocation strategies (i.e., first-fit, next-fit, best-bit, or worst –fit).
2. Design and implement a driver program that allows you to test and demonstrate the functionality of your memory manager.
3. Evaluate the performance of the chosen allocation strategies using the simulation experiment. Generate families of curves that show how the average memory utilization in the average search time (number of steps to satisfy a request) vary with the average request size. Repeat the experiments for different choices of the parameters a and d the gauss function.

5. Ideas for Additional Tasks
Experiment with the allocation strategies, e.g., different versions of an optimal fit, that take into account the size of the remaining hole after an allocation.
Use a different of request sizes. For example, try a uniform distribution, where all request sizes are equally likely, or a bimodal distribution, where sizes are clustered around two peaks ( each represtined by a Gaussian function.)

The Write-Up
The paper should be at most 8 pages (all inclusive), 12 point font, single-sided and 1-inch margins. In your write-up, you should not re-describe the assignment. Your paper must be written using correct English grammar and should have no spelling mistakes. (Run Word Spell and Grammar Checker. Have a friend read it.) The paper must contain the following parts:
• Title: The title should be descriptive and fit in one line across the page.
• Abstract: This is the paper in brief and should state the basic contents and conclusions of the paper. The abstract is not the introduction to the paper, but is a summary of everything. It is an advertisement that will draw the reader to your paper, without being misleading. It should be complete enough to understand what will be covered in the paper. This is a technical paper and not a mystery novel – don't be afraid of giving away the ending!
• Introduction: The introduction is a section of the main body of the paper. It should prepare the reader for the remainder of the paper, motivating the problem, and outlining the approach.
• Experiments: The rest of the paper should be split into reasonable sections. You should begin by describing your experimental platform (e.g., the hardware, operating system, and compiler with versions, options, and flags as necessary). For each experiment, you should briefly describe your methodology (such that it could be replicated by someone with a reasonable OS background). For each experiment, you should present your results concisely and in table or graph form when appropriate; you should identify those variables which you control (e.g., by placing them along the x-axis), and identify your performance metric especially their units. For each experiment, you should describe any conclusions that you can draw.
• Conclusions: This is a discussion of what the reader should have learned from the paper. You can repeat things stated earlier in the paper, but only to the extent that they contribute to the final discussion.
• Figures: A paper without figures, graphs, or diagrams is boring. This paper will certainly need several performance tables and graphs. Your paper must have figures.

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

Main Memory Management

This is only a preview of the solution. Please use the purchase button to see the entire solution

Assisting Tutor

Related Homework Solutions

C# Programming Problems With Books
Homework Solution
$40.00
Computer Science
Programming
C# Language
Books
Customers
Dates
Integers
Attributes
Data Types
Strings
Checkout
Abstract Methods
Calculations
Libraries
Products
Two Linked-Lists Using C++ Programming
Homework Solution
$40.00
Computer Science
C++ Programming
Two Linked Lists
Pointers
Parameters
Duplicate Items
Functions
Constructions
Equality
Number Processing in C#
Homework Solution
$50.00
Computer Science
Number Processing
C#
Text Boxes
Summation
Average Numbers
Sorting
Input Files
Variables
Forms
Randomization
Template Classes in C++
Homework Solution
$27.00
Computer Science
C++ Programming
Template Classes
Arrays
Grades
Integers
Objects
Execution
Statements
Mystery Class
Algorithms
Rock, Paper, Scissors Using C Programming
Homework Solution
$8.00
Computer Science
C Programming
Rock Paper Scissors
Game
Functions
Users
Parameters
Symbols
Randomization
Numbers
Output
Statements
Variables
Execution
Unix Environment
Shell Scripts
Data Uncrompress Using C Programming
Homework Solution
$20.00
Computer Science
C Programming
Data
Compression
Characters
Functions
Bytes
Tables
Strings
Spaces
Error Catching
Get help from a qualified tutor
Live Chats