Introduction
Computer Science 4500 Operating Systems Spring 2020 Programming Assignment 3
Due on Thursday, April 30, 2020
For this programming assignment, you have to write a C/C++ program that demonstrates the processing of memory allocation and deallocation requests when the best-fit algorithm is being used. The input data will begin with a single positive integer called MSIZE. This is the size of the simulated memory that will be used to satisfy allocation requests. You should assume the memory region extends from memory location 0 through memory location MSIZE – 1. You may assume that no memory allocation request will ever require more than MSIZE units of memory.
The remainder of the input will contain a sequence of allocation and deallocation requests, each on a line by itself. Each allocation request will include a unique integer ID which may be later specified in a request to deallocate the memory. Examples of allocation and deallocation requests are provided below, and sample input is provided on the odin server. Your program is to demonstrate your understanding of the best-fit memory management algorithm (and your programming prowess) by displaying the address associated with each requested memory allocation at the time it succeeds.
All allocations and deallocations in this assignment are simulated. Your program is only to keep track of the addresses associated with the simulated allocations.
The Best-Fit Algorithm
The principal data structure used in the best-fit system is a linked list of unused memory regions; this list is traditionally called the free list. Each entry on this list will identify the address of the unused region and the size1 of the unused region, and will also identify the next entry on the free list. In this program the entries on the free list are to be ordered by address. That is, each entry on the free list will have a larger address than its predecessor2.
As noted earlier, other than initialization, there are two basic operations to be performed: allocation and deallocation. The details of how these operations are to be implemented will now be described.
Allocation of a request for N units of memory is performed by searching the free list for the best entry that has a size R ≥ N. If no such entry is found, then the allocation request is deferred (this is discussed later). If R = N, then the entry is removed from the free list and, in a real system, would be used to satisfy the allocation request3. Otherwise, we have R > N. In this case, the best N units of
1 We use the generic term “unit” for the smallest memory item that can be allocated. For many systems this may be a byte, but other systems have other smallest memory allocation sizes.
2 Recall that there are variations of the best-fit algorithm in which the entries on the list are ordered in other ways. In particular, remember the discussions of best-fit, worst-fit, and next-fit from the text and the lectures.
3 To facilitate later deallocation of a region, your program must maintain some data structure that records successful allocations, including the allocation ID, the size, and the address of each allocated region.
Programming Assignment 3
1
memory4 in the region are used to satisfy the allocation request (in the real system). The second part of the region5, of size R – N, remains on the free list.
Deallocation of a previously allocated region of size N at address A is more steps than allocation. The first step is to find the correct location on the free list for the region of memory being deallocated. Recall that the free list is ordered by address, so the correct location will be after an entry with a smaller address (or the beginning of the list) and before an entry with a larger address (or the end of the list).
Once the correct location on the free list is found, the memory being deallocated (N units at address A) is either
● added to the region identified by the previous free list entry P if A is the address immediately after the the region identified by P, or
● added to the free list as a new entry.
Regardless of which of these two actions is taken, the free list entry now associated with the deallocated memory must then be coalesced with the following block if it exists and the memory regions are adjacent.
Deferred Requests are those allocation requests that could not be completed immediately. When this happens, information about the request (the request ID and the number of memory units requested) is added to the end of a list of such deferred requests. Of course, this list is initially empty at the beginning of the program. Each time a deallocation is performed, then each entry on the deferred list should be examined to see if the memory it originally requested can now be allocated. If it can, then the entry should be removed from the deferred request list and the allocation action performed, as usual. The deferred request list is maintained in FIFO order. That is, the first deferred request essentially has priority over later deferred requests.
An Example
An illustration with real numbers will aid your understanding of these actions. Specifically, let’s assume we have a region with 1024 bytes to use in satisfying allocation requests. Then, assume we have the following allocation and deallocation requests to process, in the order given.
ID
Action
1
Allocate 200 bytes
2
Allocate 399 bytes
3
Allocate 500 bytes
4
Allocate 100 bytes
5
Allocate 300 bytes
6
Allocate 75 bytes
4
Deallocate
1
Deallocate
5
Deallocate
7
Allocate 75 bytes
4 If the free list entry indicates the R units of memory start at address A, then these N units of memory will have addresses from A to A + N – 1.
5 If the entire region of size R started at address A, then this remaining part of the region will start at address A + N.
Programming Assignment 3
2
Initially the free list has a single entry for a region of size 1024 at address 0.
The first request (ID 1, allocate 200 units) is easy since the only one entry on the free list is larger than 200. That region is split into two parts. The region from 0 to 199 is used to satisfy the allocation request, and the region starting at address 200 with size 824 remains on the free list.
The second request (ID 2, allocate 399 units) is also easily satisfied. A region of size 399 from address 200 to address 598 is used to satisfy the request, and the region starting at address 599 of size 425 remains on the free list.
The third request (ID 3, allocate 500 units) cannot be immediately satisfied because there are no entries on the free list with a sufficient size. The request is therefore deferred. It is added to the end of a list of deferred requests, and will be considered again after each deallocation.
The fourth request (ID 4, allocate 100 units) can be easily satisfied by splitting the free region at address 599 into two parts: 100 units at address 599 (as per the request) and the single free list region at address 699 of size 325.
The fifth request (ID 5, allocate 300 units) is satisfied using memory starting at address 699, leaving a region of size 25 units on the free list starting at address 999.
The sixth request (ID 6, allocate 75 units) cannot be satisfied immediately, so it is deferred. Remember that this deferred request is to be recorded in such a way that the first deferred request (ID 3) will be considered before this one when additional memory becomes available (that is, after each deallocation).
The seventh request (ID 4, deallocate) asks for the 100 unit block at address 599 to be freed. Once this has been done, deferred requests must be considered. The first deferred request (ID 3) cannot be satisfied. But sufficient memory is available to complete the next deferred allocation request (ID 6); it’s given 75 units at address 599, with the 25 unused units at address 674 being placed in a new node on the free list.
The eighth request (ID 1, deallocate) asks for the 200 unit block at address 0 to be freed.
The ninth and tenth request (ID 5, deallocate) frees the 300 byte block at address 699. Note that this region is adjacent to the region with 25 unused units starting at address 674, so those two regions are joined to yield a single region of size 350 units at address 674. There is only one deferred request pending (ID 3 for size 500 units), but there is still insufficient memory to satisfy that request.
The final request (ID 7, allocate 75 units) is satisfied using memory starting at address 0, leaving a region of size 125 units on the free list starting at address 75.
Details and Limits
After reading MSIZE (1 ≤ MSIZE ≤ 22 0) and initializing the free list and any other data structures needed, your program should read and process requests for allocation or deallocation, one at a time, until the end of input (end of file on the standard input) is encountered. Each request will be on a single line that begins with a unique positive integer ID (1 ≤ ID) used to identify the request in the input and in the output. No two allocation requests will ever have the same ID, but each
Programming Assignment 3
3
deallocation request must contain the ID of a previously successful allocation. The input data used to test your solution will never attempt to deallocate an allocation that is currently deferred, but your solution should detect this case if it should exist, since that would indicate either an error in the input data or your solution! Although the IDs used in the earlier example’s allocation requests were sequential, this need not be the case in actual test data.
After the ID in a request there will appear some whitespace – blanks and/or tab characters – and either ‘+’ or ‘–’ to indicate an allocation request or a deallocation request, respectively. In the allocation case, there will also be additional whitespace and a positive integer ASIZE (1 ≤ ASIZE ≤ MSIZE) that specifies the size of the region to be allocated.
After reading each request, your program should display a line that indicates the request that is being processed; these should look like this:
Request ID 52: allocate 73 bytes.
Request ID 35: deallocate.
Each line for an allocation request should be followed by
Success; addr = 0x00001000. Total allocated size = 128
or
Request deferred. Total allocated size = 128
as appropriate. Note that the address in the “Success” message should be the address at which the region allocated for the request begins.
After each deallocation request you should display a line that says
Success. Total allocated size = 3072
Additionally, for each deferred request that can be successfully accommodated as a result of a deallocation, display a line that says
Deferred request with ID 59 allocated; addr = 0x00001800.
Total allocated size = 4096
If multiple deferred requests can be performed as the result of a deallocation, then the messages announcing their successful allocations should be given in the order the requests were deferred.
Of course, the IDs and address values in each of these are just examples. But do note that the addresses in the output should be displayed as 8-digit hexadecimal numbers preceded by 0x (that is, they should be C/C++-style hexadecimal constants).
Keep in mind that the addresses used in the program for free blocks and allocations are not real memory addresses – they are simulated memory addresses. Your program should not be doing dynamic memory allocation for blocks of the sizes used in the program. Naturally you may use dynamically-allocated data structures to represent the nodes in the free list and other data structures as needed by your solution.
Programming Assignment 3
4
Sample Input and Output
The instructor’s solution to this assignment and files containing sample input are available on odin in the directory /home/phuang/csci4500/prog3. After each input request has been completed, the program will display the status of each request that has been encountered (active – that is, still allocated, deferred, or freed), and the identification of the regions on the free list. Your solution need not include this feature.
The sample shown below is the input used in the earlier discussion, and is found in the file prog3.input1 on odin. Here’s what it looks like:
1150
1 + 400 2 + 50 3 + 300 4 + 50 5 + 200 6 + 50 7 + 100 5-
3-
8 + 100
The expected output for this input is as follows:
Request ID 1: allocate 400 units.
Success; addr = 0x00000000. Total allocate size = 400
Request ID 2: allocate 50 units.
Success; addr = 0x00000190. Total allocate size = 450
Request ID 3: allocate 300 units.
Success; addr = 0x000001c2. Total allocate size = 750
Request ID 4: allocate 50 units.
Success; addr = 0x000002ee. Total allocate size = 800
Request ID 5: allocate 200 units.
Success; addr = 0x00000320. Total allocate size = 1000
Request ID 6: allocate 50 units.
Success; addr = 0x000003e8. Total allocate size = 1050
Request ID 7: allocate 100 units.
Success; addr = 0x0000041a. Total allocate size = 1150
Request ID 5: deallocate.
Success. Total allocated size = 950
Request ID 3: deallocate.
Success. Total allocated size = 650
Request ID 8: allocate 100 units.
Success; addr = 0x00000320. Total allocate size = 750
prog3.input2 on Loki. Here’s what it looks like: Programming Assignment 3
5
1024
1 + 200 2 + 399 3 + 500 4 + 100 5 + 300 6 + 75 4-
1- 5–
7 + 75
The expected output for this input is as follows:
Request ID 1: allocate 200 units.
Success; addr = 0x00000000. Total allocate size = 200
Request ID 2: allocate 399 units.
Success; addr = 0x000000c8. Total allocate size = 599
Request ID 3: allocate 500 units.
Request deferred. Total allocate size = 599
Request ID 4: allocate 100 units.
Success; addr = 0x00000257. Total allocate size = 699
Request ID 5: allocate 300 units.
Success; addr = 0x000002bb. Total allocate size = 999
Request ID 6: allocate 75 units.
Request deferred. Total allocate size = 999
Request ID 4: deallocate.
Success. Total allocated size = 899
Deferred request 6 allocated; addr = 0x00000257. Total allocate
size = 974
Request ID 1: deallocate.
Success. Total allocated size = 774
Request ID 5: deallocate.
Success. Total allocated size = 474
Request ID 7: allocate 75 units.
Success; addr = 0x00000000. Total allocate size = 549
Requirements
Your program performs the tasks associated with the best-fit memory management system as described above. Your solution should be a single file of C source code named prog3.c and a Makefile (ATTENTION: The generated executable file name should be prog3). To submit your solution, create a directory named csci4500-prog3-s20 at the top level of your home directory on loki and place the two required files in it. That is, if your username is phuang, then you will create a directory named /home/phuang/csci4500-prog3-s20 and place the files prog3.c and Makefile in that directory. Please carefully read the instructions and rules; otherwise, you will lose some points. There
Programming Assignment 3
6
should be no other files in that directory, and the files you place there should not be changed or removed until you have received a grade report for the assignment.
A “template” (partial solution) for a C solution to this assignment can be found in the csci4500/prog3 directory. It is named prog3_temp.c. You are free to use this source code as the basis for your solution if you wish. However, you are not required to use this partial solution. Locations in the code that are marked “XXX – WORK NEEDED” obviously will require additional work. There may also be other modifications required to the code.
As always, please contact the instructor if you have questions, and periodically check the class web site for any additions or corrections to this assignment.
Programming Assignment 3
7