CSCI 360: Introduction to Operating System
1 | P a g e
Assignment 5: Virtual Memory Manage
Objectives
1. Learn how virtual memory management work.
2. Learn how demand paging can be implemented using page table and backing store.
3. Learn how page look up is expedited using translation look-aside buffer (TLB).
4. Learn how page replacement strategy work.
5. Implement Virtual Memory Manager in C programming language.
Specifications
This assignment is about developing an application that translates logical (virtual) addresses into physical
addresses for a virtual address space of size 216 = 65,536 bytes. Your application will read 16-bit logical
addresses from a file. Will translate each logical address into its co
esponding physical address using a
Translation Look-aside Buffer (TLB) and a Page Table. Your application will then output the value of the
yte stored at the physical address. The goal behind this assignment is to simulate the steps that involved
in translating logical to physical addresses in a Memory Management Unit (MMU) of an Operating System.
You will use a smaller (16,384 bytes) physical memory space and a larger (65,536 bytes) virtual memory
address space. Since the physical memory space is smaller than the virtual memory address space, it will
e fully occupied often. You will need to use a page replacement strategy to deal with a page fault when
the physical memory space is full. Although, there are many page-replacement strategies in the literature.
You will implement FIFO page-replacement strategy in this assignment.
Your program will read the virtual addresses from a file. The virtual addresses are represented by 32-bit
integer numbers in the file. You will need only the least significant 16-bit of these 32-bit integer numbers
to treat them as 16-bit virtual addresses, so you must mask the rightmost 16 bits of each virtual address
ead from the file. These 16-bits are divided into two components of a logical address:
1. An 8-bit page number and
2. An 8-bit page offset.
Hence, each address in the file is structured as shown in following figure.
CSCI 360: Introduction to Operating System
2 | P a g e
Other specifics of the VMM include the following:
Page size, 28 = 256 bytes.
Frame size, 28 = 256 bytes.
The number of entries in the TLB is 16.
The number of entries in Page-table is 28 = 256.
Physical memory 64 frames, i.e., 16,384 bytes (64 frames×256-byte frame size).
Your program need only be concerned with reading logical addresses and translating them into their
co
esponding physical addresses. You will also need to read the contents or values from the physical
memory pointed by the translated physical addresses. You do not need to support writing into the address
space.
Address Translation
1 2
TLB
Hit
TLB
Miss
1 2
0
1
2
.
.
15
TLB
Page Number Frame numbe
2
0
Page Frame numbe
1
2
255
.
.
.
Page Table
Frame 0
Frame 1
Frame 2
Frame 63
Physical
Memory
Page Number Offset
Logical address
Frame Number Offset
Physical address
CSCI 360: Introduction to Operating System
3 | P a g e
Your program will translate logical into physical addresses using a TLB and a Page Table. At first, the page
number should be extracted from the logical address. The TLB should be consulted with the extracted
page number. In the case of a TLB-hit, the frame number is obtained from the TLB. In the case of a TLB-
miss, the page table must be consulted. In the latter case, either the frame number is obtained from the
page table or a page fault occurs. Mechanism to handle page fault is described in the next section. A visual
epresentation of the address-translation process appears in above figure.
Handling Page Faults
Your program will implement demand paging as described in the text books. Here, the backing store is
epresented by the file BACKING_STORE.bin, a binary file of size 65,536 bytes. When a page fault occurs,
you will read in a 256-byte page from the file BACKING_STORE.bin and store it in an available page frame
in physical memory. For example, if a logical address with page number 15 resulted in a page fault, your
program would read in page 15 from BACKING STORE and store it in a page frame in physical memory.
Once this frame is stored (and the Page Table and TLB are updated), subsequent accesses to page 15 will
e resolved by either the TLB or the page table. You will need to treat BACKING STORE.bin as a random-
access file so that you can randomly seek to certain positions of the file for reading. You can use the
standard C li
ary functions for performing I/O, including fopen(), fread(), fseek(), and fclose().
As mentioned before, you will use a smaller, 64 frames, of physical memory for a larger, 256 pages, virtual
address space. A page-replacement strategy will be required during a page fault. You will use FIFO page-
eplacement strategy. TLB has only 16 entries, so you will need to use a TLB replacement strategy when
you update a full TLB. You will also use FIFO replacement strategy for TLB update.
Outputs
Your program will read in the file addresses.txt, which contains 1,000 logical addresses ranging from 0 to
65535. Your program will translate each logical address into a physical address and get the value of the
signed byte stored at the translated physical address. Your program loads the pages from the backing
store represented by BACKING_STORE.bin on demand into the physical memory frames.
Your program must output the signed byte value stored at each physical address in a separate line.
Your program must compute the followings and print them in separate lines.
(1) Page-hits.
(2) Page-faults.
(3) TLB-hits.
(4) TLB-faults.
Tasks
1. You will submit this assignment using GIT submission system. A central repository
named ‘assignment5” has been created for this assignment.
2. Create your own fork of assignment5 on the central GIT repository using following
command:
http:
csci.viu.ca/~kabirh
CSCI 360: Introduction to Operating System
4 | P a g e
ssh csci fork csci360/assignment5 csci360/$USER/assignment5
3. Go into your csci360 folder that you have created in assignment1 and create a clone of
your forked assignment5 repository using following command:
git clone csci:csci360/$USER/assignment5
4. Repository assignment5 has been organized as follows:
assignment5
in
uild
include
esource
src
Makefile
README
example
in
A README file template has been placed in the root of the application development folder. The
README file gives a general idea of the application, technologies used in developing the application,
how to build and install the application, how to use the application, list of contributors to the
application, and what type of license is given to the users of the application. You will need to complete
the README file before your final submission.
The specifications or header files (pmemory.h, ptable.h, tlb.h, and vmm.h) have been placed in
include sub folder.
All source codes (pmemory.c, ptable.c, tlb.c, and vmm.c) go into src sub folder. You will implement
functions specified in the header files pmemory.h, ptable.h, tlb.h, and vmm.h in the source code
files pmemory.c, ptable.c, tlb.c, and vmm.c) respectively.
All object files will be placed in build sub folder and executable files in bin sub folder by make.
CSCI 360: Introduction to Operating System
5 | P a g e
Two data files BACKING_STORE.bin and addresses.txt have been placed in resource folder.
A Makefile has been placed in the root of the application development folder. The Makefile does the
followings and you don’t need to and must not modify Makefile:
a) Defines and uses macros for each GCC flag that you are going to use to compile the codes
and objects.
) Defines and uses macros for each sub folder of the application, e.g., src, include, resource,
uild, and bin.
c) Uses GCC debug flag to facilitate debugging using gdb.
d) Uses GCC include flag to specify the path of application’s custom header files so that the
code does not need to specify relative path of these header files in #include pre-processor
macro.
e) Creates individual object file (*.o) into build folder from each source (*.c) file of src folder.
f) Links the necessary object files from the build folder into a single executable file in bin
folder.
g) Runs the main executable of the application from bin folder.
h) Cleans or removes files from both build and bin folders using PHONY target named clean.
5. One example executable (vmm) of this application has been placed in the example
in folder. You
can run this executable to get an idea what is expected from you in this assignment. To run the
example executable type the following:
make run-example
To run the example executable with a large address file type the following:
make run-example-large
This example executable has been built and tested in Linux Debian machines available in the labs. Run
this executable in other kind of machines at your own risks. Make clean command will not delete this
example executable and you should not delete it either.
6. Type following at the command prompt to clean previously built artefacts (binary and object files) of
the application:
make clean
7. Type following at the command prompt to build the application from your own source code:
make
8. Type following at the command prompt to run your own application:
make run
To run your own application with a large address file type the following:
CSCI 360: Introduction to Operating System
6 | P a g e
make run-large
9. Make sure you can compile, link, run, and test this application e
or and warning free.
10. Complete the README file. Therefore, you need to give the general description of the application,
technologies that are used in the application, how a user can build (compile and link) and install the
application, how a user can run the application after the installation. Mention instructor’s name and
your name in the list of contributors. Give GPL license to the users to use the application. You can
google to find README examples if you are not sure how to write one.
11. Organize and comment your code to make it easy to understand. Make sure you have typed your
name and student number in the top comment section in each .c file. Make sure you have deleted all
debugging print codes that you were using to debug your code during your development time but not
necessary in the final code. Also, make sure you have deleted all commented out codes from your
final submission.
12. Continue your work in your cloned or local assignment5 repository and commit and push
your work to your central assignment5 repository as it progresses.
Deadline and Submission
The deadline to demonstrate this assignment in the lab is December 08, 2022 and the deadline to
submit the code of this assignment is 11:00 PM on December 08, 2022. This assignment will be
evaluated to zero without lab demonstration and code submission.
Commit and push your work from your local repository to your remote repository regularly.
Use following git commands to commit and push your work from your local repository to your
emote repository from your project’s root folder:
git add --all
git commit –am”Commit message”
git push origin master
Remember ‘git add --all’ has double dashes before ‘all’. You can also use ‘git add .’ dot option
instead of ‘all’ option. Both options do the same, add all the new and the modified files into the
commit index. If you want to add only a specific file into the commit index, you can specify the
elative path of the file instead of dot or ‘all’ option. For example, if you want to add only prog.cpp
file of the src folder into the commit index, you can use ‘git add src/prog.cpp’ command. You can
CSCI 360: Introduction to Operating System
7 | P a g e
also include multiple files or paths separated by space in the same ‘git add’ command instead of
using multiple ‘git add’ commands. Command ‘git add’ is necessary before each ‘git commit’
command. If you skip ‘git add’ command before a ‘git commit’ command, it does not perform the
actual commit of the new and modified