Goal: The minimal goal of this assignment is to implement one of two data structure for keeping track of free blocks on a disk. A more reasonable goal is to implement both data structures and compare their performance. High end goals are discussed below. The data structures are Bit-Map, and Linked-List. The completed project should provide Allocate, Deallocate, and Query functions (as described below).

Grading: You may program in groups of 1, 2, or 3 (submitting 1 copy of the program per group). The requirements and point values are the same regardless of your group size. If the size of your group is 2 or 3, include a short description of who did what for the project, including an approximate percentage breakdown of the work. This description needs to be signed by each member of the group (with the shared grade distributed appropriately).

This assignment will be graded on the basis of the functionality of your program. Several levels of functionality will be described for the assignment, and your grade will depend on which level of functionality your program achieves. Thus, you will know your grade before you turn in your program. This grading scheme assumes that your program uses the data structures required by the assignment, and that you write your program with good style and use good programming practices. Deviations from these principles will result in a substantial grading penalty, as will the use of egregiously inefficient algorithms. If you have any questions about this, talk to me or Kevin well before the assignment is due.

Overall Assignment: Implement the Bit-Map and Linked-List algorighms roughly as shown on pages 83-84 of the text. Assume there are 1024 blocks available, numbered 1-1024. Your program should start with all the blocks free, and then read in commands from an input file named "blocks.input". The name of your source file should be "blocks.c".

The commands in blocks.input will take the form given below (always with a valid character value (A,D,Q) in the first position, followed by a space, followed by a number, followed by a new-line):

command meaning
A n allocate n blocks
D n deallocate block number n (a single block)
Q n query block n, print a message if allocated or free
Q -1 query free blocks: print a list of all free blocks
Q -2 query allocated blocks: print a list of all allocated blocks

When not running in the silent mode (below) your program should display appropriate messages for successful and unsuccessful calls (allocating, deallocating, requesting more blocks than are available, freeing blocks that are not allocated, and any other situations you think are appropriate). Remember to think ahead to the next project where you will need functions that return useful error codes in addition to displaying messages on the screen. A sample list of output messages might look something like:

command printed result
A 4 allocated 4 blocks: 213 214 217 412
D 214 deallocated block: 214
A 4 allocation failed (4 blocks not available)
D 416 deallocation failed (block 416 not allocated)
Q 214 query block 214: not allocated
Q 213 query block 213: allocated
Q -2 all allocated blocks: 213 217 412

Your program should recognize the following command line switches:
-l use the linked list algorithm
-b use the bit map algorithm
-s run silently (no messages displayed, used when timing your program.)
-c contiguous allocation (optional)

Timing your programs: Use /bin/time to time your program. To use this program, type

where command is the name of an executable you want to run. This will run your command, and report three times in seconds: real, user and sys. The real time is the amount of elapsed time to run your program, including any time spent running other people's programs; the user time is the time spent executing your code; and the sys time is the time spent on operating system services to run your program. Record the user time for your program (for both algorithms if appropriate). It will be important to run your tests on equivalent machines so I will provide a list of equivalent machines before the program is due. Note: if you run /bin/time on your own test data, you will need to make the data sets large enough to values > 0. Also, don't confuse /bin/time with time.

Gradations:
70%- Implement either Bit-Map or Linked-List
80%- Implement both Bit-Map and Linked-List
85%- Support contiguous allocation for either Bit-Map or Linked-List
90%- Support contiguous allocation for both Bit-Map and Linked-List
95%- 90% plus coalesce all freed and allocated blocks for both implementations

In all cases you will need to have a completed implementation that correctly allocates, deallocates, and querries, and handles the error conditions mentioned above. In addition to the brief descriptions above, the comments below help identify what's required for each of the levels. Unless otherwise specified, all allocations should be taken from the lowest address possible.

If you select the 70% level and use Linked-List, all allocations should be from the head of the list and all deallocations should be returned to the head of the list. This may cause allocations to be made from other than the lowest memory address possible.

For the 80% level and above, the linked-list implementation should maintain a dynamically allocated list of nodes similar to the one shown on p.83 (except that the first block is #1, not #0, and freed blocks need not be coalesced with neighboring nodes of free blocks, allocated nodes need not be coalesced either).

For the 90% level, your program should support both contiguous and non-contiguous allocation (determined by the presence/absence of the -c command line option). For contiguous allocation, the blocks allocated must be consecutively numbered. You may or may not actually coalesce freed blocks, as long as your allocation scheme recognizes contiguous nodes of free space.

For the 95% level, your program should always maintain a minimal number of nodes in the linked-list implementation. In other words, after any call to Allocate or Deallocate there should not be any same-typed neighboring nodes (neighbors that both contain ALLOCATED blocks, or both contain FREE blocks).