代写操作系统中的内存分配部分。
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):
std::vector[uint8_t] memory;
—|—
Byte array that will contain the page frames to be managed
uint32_t page_frames_total;
—|—
A count of the total number of page frames in memory (memory size divided by
0x1000)
uint32_t page_frames_free;
—|—
The current number of free page frames
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 as
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 as
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 function
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:
1 1
0 1
1 5
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:
1 20
0 10
1 a0
0 b0
1 c0
1 3d
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.
