代写操作系统中的LRU内存管理算法，修改框架代码，通过测试。
Introduction
In this assignment, you are going to simulate a virtual memory manager. The (simulated) manager shall be implemented with a variant of LRU paging algorithm. First, the manager is instantiated with a hypothetical configuration (e.g., there are 8 pages, 4 frames, etc.). Then, we will access logical addresses through the manager. For each logical address, the manager shall return the corresponding (simulated) physical address based on the given hypothetical configuration.
The manager
On page fault, the manager shall choose a frame as follows:
- If there are several available frames, select the one with smallest frame id;
- If there is only one free frame, choose it;
- If all of the frames are occupied, swap out a victim page based on the paging algorithm.
The paging algorithm
The paging algorithm is a variant of the LRU algorithm, which keeps track of the timestamp of the last m references to each page, where m is a positive integer.
Let time(p, m) be the time of the mth-most recent reference to page p. If page p has less than m references, time(p, m) would be the time of the most recent reference to p.
Therefore, when choosing a victim page to swap out, the algorithm chooses the one with the earliest/smallest time(p, m). Note that when m = 1, this algorithm degrades back to the conventional LRU paging algorithm.
Your assignment
You are given the following files:
| Name | Description |
|---|---|
| /manager.c | Source code of a runnable but non-functioning manager.c (Work on it). |
| /manager.h | Header file of manager.c (Work on it). |
| /tester.c | We will run this program to grade your assignment (Don’t touch). |
| /Makefile | Makefile to compile tester (Don’t touch). |
| /testcase | Test cases used in tester (Don’t touch). |
| /testcase ans | Answer to the test cases in tester (Don’t touch). |
To begin
This time, we use CUnit to test your program. Please use the following command to install CUnit first:
sudo apt-get install libcunit1 libcunit1-doc libcunit1-dev
Then make and run tester, you shall see something like this.
Ignore other rows and focus on the row “tests”. Before you work on your assignment, you shall see it has run 10 test cases and 0 passed.
Your job
You should start from the given manager.c and manager.h. Read them carefully. The following is a brief introduction:
- manager_t, a structure defined in manager.h to represent the memory manager. The suffix “_t” of manager_t identifies this as a type. Currently there are four members in the structure manager_t:
- page num, the number of pages;
- frame num, the number of frame;
- frame size, the size of frame;
- lru parameter, the value of parameter m
The prefix “_“ means that this variable is a member of the structure. You can add other member variables to manager_t if necessary.
- manager_t* new memory manager(uint32_t page num, uint32_t frame num, uint32_t frame size, uint32_t lru parameter), this function instantiates a manager_t.
- void deconstruct manager(manager_t* self), this function frees the manager_t.
- uint32_t access(manager_t* self, uint32_t addr), return the physical address given the logical address addr. You have to handle the details here (e.g., extracting the page id and page offset from addr, which is introduced in 2.4. Note that here we take logical address as input and require to return physical address.)
You can add other functions to manager.c and manager.h. Do NOT change the name and usage of any existing functions.
Submission
Submit two files, manager.c and manager.h. Please compress them to asgn5-SID.tar.gz and submit it to eLearning. E.g., if your SID is 1155031234, please submit asgn5-1155031234.tar.gz to eLearning.
Warning: DON’T change the file names, otherwise you will get zero marks.
Assumptions
You can assume the following assumptions always hold in this assignment:
- The logical address, page id and frame id are of type uint32_t.
- The size of each frame equals to that of each page.
- All of the frame size, the amount of pages and the number of frames are power of 2.
- The rightmost bits of a logical address represent the page offset and the bits next to the page offset represent the page ID (page number). Consider a configuration with 256 pages and suppose the page size is 28 bytes. As shown in the following figure, only the rightmost 16 bits of each logical address matter:
Grading
- 10 test cases in total.
- Passing one test case will get 10 marks.
- Hardcoding won’t work. We use some other inputs to check if you have done any hardcoding.
- The grading will be fully automated. The grading platform is our course’s VM: Ubuntu 14.04 32-bit. Once we start the grading processing, we reserve the right to deduct marks from you for any request that requires TA’s extra manual effort.
Late Submission Policy
We follow the late submission policy specified in the course outline.
Questions
If you have doubts about the assignment, you are encouraged to ask questions on our Facebook group.