Homework 10🔗

Due Date: Saturday April 5, 9pm

Purpose Part 3 of Project, plus more practice with lambda, multiple complex inputs, and binary trees

Expectations

• You should have a single file with your solutions to all of the exercises. Please label where your solution for each exercise begins very, VERY clearly! You should then submit this common file to each of the HW10-related entries on the Handin Server; the file should be named "HW10.rkt". We accept NO email submissions. Failure to submit a .rkt file will result in a 0 for that part.

• You are only allowed to use the language specified at the top of this page: failure to do so will result in a 0. For this assignment, you must use ISL+Lambda. (remember to correctly set the mode in DrRacket). Using the wrong language will invalidate your submission and result in a score of 0, so please be careful.

• Your code must conform to the guidelines outlined in the style guide on the course website. Pay particular attention to the list of prohibited functions in the guide. The style guide may be updated as the semester progresses so please remember to read it before submitting each assignment.

• Unless otherwise stated, all data and functions you design must be designed according to the data and function design recipes (DR), resp., following all four steps in each case, with the exception of functions that call big-bang, for which you need no check-expects, as justified in class, and local functions, which need example comments in place of check-expects. All functions used inside big-bang must have check-expects, along with the other three steps of the design recipe.

-----------------------------------------------------------------------------

Introduction

For this assignment, you will be implementing the final part of the 3-part project for the course. This document is a summary synopsis of what you must implement for this project. It is not a deep explanation of the motivations and design; that will be covered in class.

For HW8, you developed the code to manage a hierarchical bitmap set (HBS), which allows you to efficiently manage space to allow for contiguous allocations of chunks of various power-of-2 sizes. The underlying data design involved a list of list-of-booleans, one per chunk size that you were managing. You also learned about the unique-bit-at-highest-level normalized minimal form we were using to make allocations and deallocations efficient.

In this homework, you will be reimplementing those functions to work on a completely different data design: a binary tree. In this data design, each level of the tree across all branches will represent the chunks at that level. Because we want a single tree, that means our representation will always have to start at the very top–the root of the tree–with a single bit representing a chunk spanning the entire storage space. Then, its child nodes will represent each of the two half-sized chunks that the parent node can be divided into. This division process keeps going until you reach nodes in each branch representing single-block chunks. Each node will contain a Boolean value that represents a single bit, #true if that chunk is free. So, if the space being managed is 16 blocks, the node at the root will represent a 16-block chunk, and its child nodes will represent the two chunks with blocks {0 - 7} and {8 - 15}, respectively. Note that at the bottom of the tree, all nodes will represent a single block, with null child node fields (#false, actually).

That’s pretty much the only change from HW8. Of course, this change in the underlying representation has design consequences for pretty much all of the functions we originally designed in HW8, so they will all have to be reimplemented, and retested. The saving grace is that with binary trees, the functions are all much simpler. Also, the signature and purpose statements should not have to change at all.

To keep this document short, the data design will be reviewed in class. Also, we will provide our canonical solution for HW8 separately. This document will just re-state the functions that you need to (re)design and submit. Good luck!

Provided Data Designs We are providing the following data definitions which you mush use exactly as given to represent your underlying bitmaps:

(define-struct hbs [bit left right])

; A HierarchicalBitmapSet (HBS) is one of:

; - #false

; - (make-hbs Boolean HBS HBS)

; representing a bit at some level of a hierarchical tree of bits,

; or a sentinel value representing an empty tree/subtree

(define (hbs-temp hbs)

(...

(cond [(boolean? hbs) ...]

[(hbs? hbs) (... (hbs-bit hbs) ...

(hbs-temp (hbs-left hbs)) ...

(hbs-temp (hbs-right hbs)) ...)])))

The same simplifying restrictions from HW8 on the underlying storage and the user’s requests apply here: every request from the user will be for a chunk of some power-of-2 size, and the total number of blocks in your drive will be a power of 2. This guarantees that your binary tree representation will be what is referred to as a perfect binary tree, and will make your design much simpler.

IMPORTANT: Same rules apply as in HW8 about which chunk you should allocate: you must allocate chunks in such a way as to avoid unnecessarily disrupting larger free chunks. For example, assume you have an 8-block drive, numbering from 0, and blocks 4 and 5 are currently allocated (marked #false). If the user requests a 2-chunk, the requirement is that you must allocate the 2-chunk {6, 7}, because if you instead allocated either {0, 1} or {2, 3}, it would unnecessarily disrupt the 4-chunk {0, 1, 2, 3}, meaning you wouldn’t subsequently be able to honor a request for a 4-chunk.

Also, the same rules about keeping the HBS in normalized minimal form still apply. The only thing that has changed is the internal representation as a binary tree.

The following data definition might be useful as the return type for several of your functions:

(define-struct hbs-chunk [block size])

; A HBSChunk is one of:

; - #false

; - (make-hbs-chunk NatNum PosInt)

; Represents the result of a chunk query, where:

; - block is the starting block number for the chunk that was allocated;

; - size is the size chunk that is being taken or split

; or a sentinal value to indicate there was no eligible chunk

(define HBSC-1 (make-hbs-chunk 2 2))

(define (hbs-chunk-temp chunk)

(...

(cond [(boolean? chunk) ...]

[(hbs-chunk? chunk) (... (hbs-chunk-block chunk) ...

(hbs-chunk-size chunk) ...)])))

The following data definition, copied over from HW8, must be used as the return type for several of your functions. Note that though the field hbs is still an HBS, since the definition of that data type is different in HW10, the examples must change.

(define-struct hbs-alloc [block hbs])

; A HBSAllocResult is a (make-hbs-alloc Integer HBS)

; Represents the result of an allocation call, where:

; - block is the starting block number for the chunk that was allocated;

;   or -1 if no space available

; - hbs is the updated HBS after the allocation

(define HBSAR-1 (make-hbs-alloc 1

(make-hbs #f

(make-hbs #f

(make-hbs #t #f #f)

(make-hbs #f #f #f))

(make-hbs #t

(make-hbs #f #f #f)

(make-hbs #f #f #f)))))

; OLD VERSION:

(define HBSAR-1-OLD (make-hbs-alloc 2

(list (list #f #t)

(list #t #f #f #f))))

(define (hbsar-temp hbsar)

(... (hbs-alloc-block hbsar) ...

(hbs-temp (hbs-alloc-hbs hbsar) ...)))

Exercise 1 Support Functions: For this part of the assignment, you will design functions to support status queries about the underlying storage:

• Design the function blocks-remaining that consumes a HBS and produces a count of the total number of free blocks (not chunks) available on the drive.

• Design the function find-chunk that consumes a HBS and a chunk size (which will always be a power-of-2) and produce the index of the first block of a free chunk of the requested size. Note that this function only returns a Integer, since it does not modify the HBS. This should report the exact same chunk of blocks as what a true allocation would return, but without actually making any changes to the HBS. Return -1 if no chunk of the appropriate size could be found.

  HINT: for the recursive implementation of this functionality, we suggest that you return a value of type HBSChunk or some such, since you will need both information about the block to allocate as well as what size chunk it is being taken from (this will be explained in class). Of course, this would violate the signature of find-chunk, but that’s simple to fix: you can just create a helper that implements the real recursive logic and returns the HBSChunk type, and your find-chunk would just be a shell function that consists of a simple call to this real recursive function.

• Design the function initialize-hbs that consumes a single bitmap of the free blocks on a drive, and produces the corresponding HBS, set up according to the representation described earlier in this document. So, the signature for this should be:

  initialize-hbs : [List-of Boolean] -> HBS

  NOTE: This function is slightly different from the version in HW8: it should now produce a tree where the top level represents a single bit spanning the entire space. The previous version stopped at the level where each chunk spanned half the space. This was to make the code design simpler because every bitmap was an even length; that is no longer a concern with trees.

Exercise 2 Allocation Function: For this part of the assignment, you will design the function that allocates a chunk and updates the map appropriately.

Design the function alloc-chunk that consumes a HBS and a chunk size (which will always be a power-of-2) and produces an HBSAllocResult (given above), which includes index of the first block of the free chunk of the requested size that was allocated, as well as the resulting HSB modified to reflect the current allocation. If the allocation fails because no appropriate chunk could be found, the block number in the result structure should be -1, and the HBS should be returned unmodified.

IMPORTANT: as before, this function must return first available chunk of the appropriate size, given the restriction that it will only return aligned chunks, and the requirement that you should not unnecessarily break up bigger chunks. For example, if you have a 16-block drive, and blocks 0, 3, 12, and 13 are currently allocated, you must return the 2-chunk {14, 15}, for the following reasons: While the user would be happy with being allocated blocks {1, 2}, your system would not return it because they do not belong to the same 2-chunk (block 1 is part of the 2-chunk {0, 1}, and block 2 is part of {2, 3}). And while the chunk {8, 9} would again make the user and our chunk-based system happy, it would unnecessarily break up the 4-chunk {8, 9, 10, 11}. Allocating {14, 15} is ideal because it is not needlessly breaking up a larger chunk: the 4-chunk {12, 13, 14, 15} is already broken up because {12, 13} is already allocated.

Exercise 3 Freeing (i.e., Deallocation): For this part, you will design a function that frees a chunk back up, updating the map appropriately.

Design the function free-chunk that consumes a HBS, a chunk size, and the starting block of the chunk, and produces an updated HBS that reflects the deallocation. Again, the chunk size will be a power-of-2, and the starting block will be appropriately aligned (i.e., a multiple of chunk size). You can assume the chunk being freed is valid.

Final Thoughts As stated in class multiple times, this is the first real thinking assignment. The more you actually work out the design in your head, the less code you will find you need to write, and surprisingly, the simpler it will be, too. Good luck!