An initial attempt, including the change outlined above, is available for you. To ensure the code continues to compile, the argument order still exists but defaults to 0 and an assertion will fail if a non-zero argument is passed. This means that currently, the kernel aborts early during the boot process. Your improved kernel will work normally, but will preserve the ‘one frame only’ simplification, by modifying all places in the code that try to allocate more than one frame. (There are not very many, but it’s up to you to find them.)

You must pull changes from the cw2024resit branch and base your work on the commit c94576e.

One exception to ‘one frame at a time is enough’ rule is for the kernel’s own malloc implemen- tation. This does ask for large chunks of memory to parcel out to its clients, and for complex reasons, these must be physically contiguous even though they are addressed virtually. How- ever, you can ignore this for the purposes of this assignment: the same commit mentioned above includes a modified version of malloc that sidesteps this problem.

Making it faster or more memory-efficient

You can score up to the full 15 out of 15 for completing this task. You should attempt either this task or the previous one, as they are disjoint.

You should work from the cw2024 branch, not the resit branch. Your work should be based on commit 26343b9.

Although InfOS currently has no need to allocate larger-than-a-page blocks of physical memory, these would be useful in a slightly extended version of InfOS. For example, they are needed for DMA buffers; InfOS currently does not use DMA but could reasonably do so.

Therefore, in this task you will provide a more efficient implementation of frame allocation, in a way that continues to handle requests for any power-of-two number of frames.

The current algorithm does a linear search for a contiguous range of frame descriptors of sufficient size. These frame descriptors consume a significant amount of memory themselves, and the linear search is potentially very slow when searching for a larger block, especially under high (external) fragmentation.

How you go about improving the efficiency is up to you. However, the following are some ideas.

• You could replace the FrameDescriptor structure (currently three words per frame, or thereabouts) with a bitmap (one bit per frame). This will improve space-efficiency.
  
  

• You could implement a buddy allocator to replace the current simple frame allocator. A buddy allocator is so named because any large block can quickly be broken in half, yielding two smaller ‘buddies’, and conversely, any block has a neighbouring ‘buddy’ with which it can be combined, if both are free, to form a single large block. Such an allocator can quickly allocate contiguous regions of memory (here physical memory, in units of a page or any power-of-two number of pages), at the price of greater internal fragmentation (every block it allocates has a power-of-two size). You will have to do your own reading on buddy allocators, which are extensively documented (e.g. on Wikipedia). The main objective here is to improve speed (time-efficiency).
  
  

  • You could implement an alternative allocator of your own choosing, instead of a buddy allocator. There is a large design space, and the lecture materials covered some of this. The important thing is that it should be faster than the current allocator under plausible workloads.
  
  

  Up to 6 marks are available for any competently executed refactoring of InfOS which preserves its functionality and is meaningfully connected with the task. The remaining 9 marks are for a minor improvement in time (up to 3 marks) and/or minor improvement in space overhead (up to 3 marks), major improvement in either time or space (up to 3 further marks, to a maximum of 6), and up to 3 marks for documentation, tests, comments and other good practice. If you attempt this task, your code will be subject to automated performance testing as well as manual inspection. You can score up to the full 15 out of 15 for completing this version of the task. You should check whether a mark cap applies to you.