Introducon
Page Frames
Next week we’ll be looking at virtual memory systems. These systems divide memory into fixed-size blocks, called page frames. We’ll use 4096 = 0x1000 bytes as the page frame size. Each process will have a list of page frames that are allocated to it (just one process for this assignment).
Free Page Frames
The free list can be maintained as a linked list of page frames. Links are page frame numbers, from 0 to the highest numbered page frame. Each page frame on the free list has, in its first 4 bytes, the number of the next page frame on the list. The last page frame on the free list has link 0xFFFFFFFF. The head “pointer” is just the number of the first page frame in the list (0xFFFFFFFF if the list is empty). This format allows a page frame to be allocated from the free list in constant time.
Allocated Page Frames
The OS also needs to keep track of page frames allocated to each process. Since the page contents are controlled by the running process, the OS needs to keep track of the pages elsewhere. For this assignment, use a std::vector[uint32_t] to store all the page numbers allocated to the single process.
Programming Task
PageFrameAllocator class
Create a class named PageFrameAllocator. This class will manage the allocation and deallocation of the page frames. No input or output should be done within the class.
Class Data Members
At a minimum, your class should have (at least) the following private data (must be declared as specified):1
std::vector[uint8_t] memory;
Byte array that will contain the page frames to be managed1
uint32_t page_frames_total;
A count of the total number of page frames in memory (memory size divided by 0x1000)1
uint32_t page_frames_free;
The current number of free page frames1
uint32_t free_list_head;
The page frame number of the first page frame in the free list (0xFFFFFFFF if list empty)
Constructor
The constructor should accept a single argument, the number of page frames in the memory. It should resize the memory vector to the number of page frames times 0x1000. The constructor should then build the free list consisting of all page frames in memory. It should initialize the other class member data variables as appropriate.
There should be no default constructor, and other constructors and assignments should be defined such that move and copy are not allowed. An empty destructor should be supplied.
Allocator
Define the public class method specified as1
bool Allocate(uint32_t count, std::vector[uint32_t] &page_frames);
This method takes as its first argument a count of the number of page frames to allocate from the free list. The method should push the numbers of all the allocated page frames onto the back of the vector page_frames specified as the second argument. If the number of free page frames is less than the count argument, then no page frames should be allocated, and the method should return false. If the page frames are successfully allocated, the method should return true.
Deallocator
Define the public class method specified as1
bool Deallocate(unit32_t count, std::vector[uint32_t] &page_frames);
The last count page frame numbers from the vector page_frames should be returned to the free list. These page frame numbers should be popped from the back of the page_frames vector as they are returned to the free list. Returns true if count <= page_frames.size(), otherwise returns false without freeing any page frames.
Accessing Data Members
All data member of the class must be private. You should supply public member functions to return values needed by users of this class (these are sometimes called “getters”). For example, to access the current number of free page frames, in the .h file you could define the public class member function1
uint32_t get_page_frames_free() const { return page_frames_free; }
Other Data and Class Member Funcons
You may define other private class data and function members as needed.
Main Program
Your main program should read input from the file specified by the first command line argument. Output should be written to standard output.
Input File Format
The first line of the input file will contain a single hex integer specifying the number of page frames. Your program should read this number from the input file and use the value to construct a PageFrameAllocator object.
Subsequent lines in the input file will contain one or two hex numeric values:
- The first value on each line will be a 1 to allocate page frames, 0 to deallocate page frames, 2 to print the contents of the free list
- The second hex value on each line will be a count of page frames to allocate or deallocate (not present when first value = 2)
Your program should read the input file a line at a time, and process the allocation or deallocation specified by each line in sequence.
Output Format
As you read each input file line (including the first line), write the line to output, preceded by the ‘]” character.
After processing each allocate or deallocate request, write a line in the following fomat:
S FC
The first character of the output line should be a blank. The S value should be T if Allocate returned true, and F if Allocate returned false. The FC value should be the hex value of the number of free page frames after the Allocate call is made.
For S = 2 (print free list), write a blank at the beginning of the line, followed by the hex numbers of all the pages in the free list. The exact output will vary depending on how you manage your free list, but you should have the same number of entries as the sample output.
Example Input and Output
Two sample input files (.txt files) and corresponding output files (.out files) can be found in Lab3Data.zip .
Here’s sample input sample0.txt:
5
2
1 1
2
0 1
2
1 5
2
1 1
1 2
0 6
0 7
0 1
0 1
0 1
0 1
0 1
0 1
1 6
The corresponding output should look like this (the print free list values may differ, but the number of free list entries should be the same):
>5
>2
0 1 2 3 4
>1 1
T 4
>2
1 2 3 4
>0 1
T 5
>2
0 1 2 3 4
>1 5
T 0
>2
>1 1
F 0
>1 2
F 0
>0 6
F 0
>0 7
F 0
>0 1
T 1
>0 1
T 2
>0 1
T 3
>0 1
T 4
>0 1
T 5
>0 1
F 5
>1 6
F 5
Here’s the second sample input, sample1.txt:
100
1 20
0 10
1 a0
0 b0
1 c0
1 3d
2
1 3
1 1
0 101
0 100
The corresponding output should look like this (the print free list values may differ, but the number of free list entries should be the same):
>100
>1 20
T e0
>0 10
T f0
>1 a0
T 50
>0 b0
T 100
>1 c0
T 40
>1 3d
T 3
>2
fd fe ff [note: will be 3 numbers, your values may differ]
>1 3
T 0
>1 1
F 0
>0 101
F 0
>0 100
T 100
More sample inputs and outputs will be provided by Friday.
Subming Your Lab
Export your project from NetBeans as a zip file called Lab3.zip, using File -> Export Project -> To ZIP…
Make sure your file is named with the .zip extension. The resulting zip file should be submitted through Canvas.