|
Assigned |
|
|
Due |
|
|
Update |
Feb 28. An error in the illustrative example has been fixed. This affect the last two sets of figures (after “STOP 1”) where two free blocks (6000, 3000) and (9000, 1000) are now merged into (6000, 4000). See here for the corrected example. |
List is an important data structure with wide applications. This project will give you experience working with lists in the context of memory management in operating systems.
In this project you will implement dynamic memory management for a hypothetical operating system. The system allocates memory to processes upon their requests, and takes back memory released by the processes. The system therefore needs to keep inventory of the memory blocks as well as information of outstanding processes and the memory blocks allocated to them. The following are the details. Note that the policies are set for this exercise; they may or may not be the ones used in real world operating systems.
Memory:
The memory of size N consists of N units of memory (the actual unit size is not important), with addresses 0 through N – 1. Some units are allocated to processes; others are free and can be allocated upon request. Consecutive free units form free blocks, and consecutive allocated units form allocated blocks. Each block is identified with its beginning address and associated with the size of the block. Initially the memory consists of a single free block of size N and located with beginning address 0.
Memory allocation policies:
When process p makes a request for M units of memory:
1. Find the smallest free block whose size is equal to or greater than M, allocate the first M units of that block to p. The remaining fraction of that block (if any) forms a smaller free block.
2. If all free blocks are smaller than M, then allocate two or more free blocks from the front of the memory (i.e., with smallest addresses). Again, a smaller free block will be created if the total size of these free blocks is not equal to M.
3. If the total amount of free memory is less than M, then the process p is suspended and put on hold until the requested amount of free memory becomes available.
Memory release policies:
When process p releases M units of memory allocated to it back to the system:
1. Release of allocated blocks is selected on the “last in first out” basis (i.e., the latest allocated block is freed first, regardless its size). Similar to allocation policies, what will be released may be a fraction of a block, a single block or multiple blocks that p currently has.
2. If a newly released block is adjacent to some free block(s), they together form a larger free block.
3. If the total amount of free memory becomes large enough for some on hold processes, the system will allocate free memory to them on the “first come first serve” basis. If the memory request of the first process on the hold list is too large (i.e., more than all memory currently free in the system), then the second process on the list will be considered, and so forth.
Commands:
The following commands will be used:
· START<p-id>: create a process with an integer “p-id” as its ID.
· STOP<p-id>: the process with given ID will be terminated. When a process is stopped, it releases all memory blocks it still has back to the system.
· GET<p-id><amount>: process “p-id” requests for the “amount” units of memory.
· FREE<p-id><amount>: process “p-id” releases the “amount” units of memory. Of course the “amount” must not be larger than the total memory it currently has.
· SHOWPROCESS:
print all outstanding processes, including their ID, status (active or on
hold), and the amount of memory units each has. The print must be in the order
they were created.
· SHOWFREEMEMORY:
print the total amount of free memory and the size of the largest free block.
Notes:
· Only active processes (started but not yet stopped and not on hold list) can request and free memory.
· For each command that involves either freeing or allocating memory, you need to output all blocks that are freed or allocated as (address, size) pairs.
· Print appropriate message if a command cannot be carried out (for example, a GET command requesting too much memory puts the process on hold).
An example is provided here to illustrate the policies and the consequence of each command in different circumstances. The lists drawn in the example may be suggestive, but not mandatory for your implementation.
Command line and command file:
Project 2 will be invoked with a command line that consists of 2 arguments: the size of the memory and the name of a command file. For example:
proj2/Proj2 10000 command.txt
The commands in a command file shall be executed in the given sequence. You should echo each command before it is executed.
Submit the following files:
Submit the files using the procedure below.
Submission Tools
There are a number of tools available to you to check on your submittal. It is
your responsibility to ensure that the submittal is correct and will result in
a successful compilation of your project. Do not wait till the last minute to
submit your files. Give yourself enough time to check that your submittal is
correct.
If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.
Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/. The class name is cs341 and the project name is Proj2. One of the tools provided by the submit program is submitls. It lists the names of the files you have submitted.
Project grading is described in the Project
Policy handout.
Cheating in any form will not be tolerated. Please re-read the Project
Policy handout for further details on honesty in doing projects for this
course.
Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.