System implementation
Among the selected classes, classes implementing the algorithms themselves will be omitted, which are described in the next section. Supporting classes will be described.
PageTable class
The PageTable class allows you to create a table of pages needed to present the algorithms. The constructor of this class accepts the number of frames that the table can hold.
def __init__(self, how_many_frames):The instance of this class also stores information about:
-
page errors page_faults (initially 0),
-
number of writing to disk writes_to_disk (initially 0),
-
total number of references to the memory, total_memory_accesses (initially 0).
In addition, it offers:
-
storage of the frame array frame_table (class Frame); initially each frame is marked as clean and not in use,
-
fast mapping Virtual Page Number to Physical Page Number, which is applicable in the optimal algorithm,
-
cyclic buffer (class instance CircularQueue), applicable in clock and aging algorithms.
Frame class
The Frame class represents a frame in a page table (the page table stores an array of frames).
Each frame is initialized in the following way:
-
vpn = 0, the virtual page number (Virtual Page Number) is set to zero,
-
ppn = 0, physical page number (Physical Page Number) is set to zero,
-
dirty = False, where dirty means Dirty bit, which is a modification bit, which says that before replacing the page you should save the contents of this frame to disk, because the frame has been modified,
-
in_use = False, which is a bit set each time a page is referenced.
Fields related to specific algorithms are also available, such as:
-
instructions_until_next_reference = None, i.e. a variable used only in the optimal algorithm, indicating the number of instructions remaining until the next reference to the page,
-
reference = False, or the reference bit used in the aging algorithm,
-
aging_value = 0, i.e. variable describing the value of the reference counter in the aging algorithm,
-
last_reference = 0, which is a variable used to mark references in the LRU algorithm.
Static methods:
- get_vpn(memory_address) - the method is used to draw a virtual page number (Virtual Page Number) based on the given memory address, assuming a 32-bit address space and 4k pages.
CircularQueue class
The CircularQueue class implements a cyclic buffer. This buffer is applicable in clock and aging algorithms.
All algorithms were placed in the algorithms package and each of them was devoted to a separate module with a class on which the instance can be run.
Clock algorithm
The implementation of the clock algorithm is in the clock.py module (Clock class) and uses the auxiliary class, CircularQueue.
Similarly to the rest of the algorithms, when creating an instance, two parameters should be passed to the class's constructor: a class object PageTable that stores a table of pages and a list of invariant lists (tuples) that stores pairs of subsequent addresses together with information about memory access mode (read or write).
def __init__(self, page_table: pt.PageTable, trace: list, keep_states: bool = False):
self.page_table: pt.PageTable = page_table
self.trace: list = trace
self.frame_queue: cq.CircularQueue = page_table.frame_queue
self.hit: bool = False
self.evict: bool = False
self.dirty: bool = False
self.keep_states: bool = keep_states
self.table_states: list = []The constructor is shown in the listing above, in which the variables are initialized. This was done analogously to the Aging class.
def run_algorithm(self) -> rt.ResultTuple:
"""
Performs clock page replacement algorithm
"""
# Keep track of our memory accesses
self.page_table.total_memory_accesses = 0
# Run the algorithm while we have items left in the trace
while self.trace:
self.hit = False
self.evict = False
self.dirty = False
# Pull out next item of the trace
next_address = self.trace[0]
next_vpn = self.page_table.get_vpn(next_address[0])
# Run it in our algorithm
self.add_page_or_update(next_address)
# Remove it from the trace, so it isn't processed a second time
self.trace.pop(0)
self.page_table.total_memory_accesses += 1
self.print_trace(next_address, next_vpn)
if self.keep_states:
self.table_states.append(copy.deepcopy(self.page_table))
self.print_results()
return rt.ResultTuple(len(self.page_table.frame_table), self.page_table.total_memory_accesses,
self.page_table.page_faults, self.page_table.writes_to_disk, 'N/A')As with other algorithms, the main method of the class is run_algorithm, in which an attempt is made to add further memory addresses to the page table. It is most important to call the add_page_or_update method, which is responsible for the algorithm's execution logic. Her body looks as follows:
def add_page_or_update(self, mem_address):
"""
Takes care of next page in trace
:param mem_address: page memory address
"""
# Try to add a page outright, and if it works, we're done
vpn = self.page_table.get_vpn(mem_address[0])
read_or_write = mem_address[1]
if not self.is_hit(vpn, read_or_write):
self.page_table.page_faults += 1
self.hit = False
else:
self.hit = True
if not self.frame_queue.add_or_update_successful(vpn, read_or_write):
self.evict = True
victim_frame = self.frame_queue.find_victim()
victim_frame = self.run_swap_demon(victim_frame)
self.frame_queue.remove(victim_frame)
# Add the frame in the newly freed space
self.frame_queue.add_or_update_successful(vpn, read_or_write)First, it is marked if the page is present in the page table. The page error counter, page_faults, is incremented if necessary. Next, the CircularQueue class method is performed, i.e. a dedicated structure that is a cyclic list. In it there is the method add_or_update_successful, which iterates over elements of the list (pages) in search of a free page or address that corresponds to the page that we want to add. The method returns information if it was possible to add a page to the list.
In the event of failure, please find the page to be removed. Again, the CircularQueue class provides a method to find the right page. find_victim first looks for a page with no reference bit marker and read mode. If the page does not meet these conditions, it means that the clock pointer must be moved to the next page, while also extinguishing the reference bit, which serves as the second chance marker.
def run_swap_demon(self, victim_frame):
"""
Runs swap demon for dirty and unreferenced pages, if necessary.
Happens when no victim frame is found on first run,
this also means we are going to write a dirty page to disk when we run the swap daemon.
:return victim_frame:
"""
while victim_frame is None:
# Run the swap daemon, and account for the number of writes to disk
num_disk_writes = self.frame_queue.flush_dirty_and_unreferenced_pages()
self.page_table.writes_to_disk += num_disk_writes
# If we write to disk, we did a dirty eviction
if num_disk_writes > 0:
self.dirty = True
# Get a victim page, since there must be one now that we've flushed
victim_frame = self.frame_queue.find_victim()
return victim_frameThe previously discussed method can return None when there is no page that meets the conditions in the entire list. This is a situation in which the table is filled with pages with write access mode. To remedy this situation, the run_swap_demon method was created, which prints all pages with the write mode and without the set reference bit to the disk, thus freeing space in the page table.
This solution involves the need to perform a more frequent write to disk operation, but this reduces the number of page errors.
For the LRU algorithm, the LRU class from the lru.py module is intended.
def __init__(self, page_table: pt.PageTable, trace: list, keep_states: bool = False):
self.page_table: pt.PageTable = page_table
self.trace: list = trace
self.frame_list: list = page_table.frame_table
self.initialize_ppns()
self.hit: bool = False
self.evict: bool = False
self.dirty: bool = False
self.keep_states: bool = keep_states
self.table_states: list = []
def get_table_states(self):
return self.table_states
def initialize_ppns(self):
"""
Assigns PPNs (Physical Page Numbers) to each frame from page_table.
"""
counter: int = 0
for elem in self.frame_list:
elem.ppn = counter
counter += 1The class stores a table of pages, a list with all memory addresses and 3 variables informing about the momentary evaluation of the page under investigation (hit, evict and dirty).
The main method used to run the algorithm for the created class instance is run_algorithm. Returns its result in an ResultTuple object.
def run_algorithm(self) -> rt.ResultTuple:
"""
Executes LRU algorithm
:return: tuple with algorithm final result
"""
# keep track of our memory accesses
self.page_table.total_memory_accesses = 0
# run the algorithm while we have items left in the trace
while self.trace:
# reset output variables
self.hit = False
self.evict = False
self.dirty = False
# pull out next item of the trace
next_address = self.get_next_address()
next_vpn = self.page_table.get_vpn(next_address[0])
next_read_or_write = next_address[1]
# run it in our algorithm
if not self.add_or_update_successful(next_vpn, next_read_or_write):
self.add_after_page_fault(next_vpn, next_read_or_write)
self.print_trace(next_address, next_vpn)
if self.keep_states:
self.table_states.append(copy.deepcopy(self.page_table))
self.print_results()
return rt.ResultTuple(len(self.page_table.frame_table), self.page_table.total_memory_accesses,
self.page_table.page_faults, self.page_table.writes_to_disk, 'N/A')In the function, further addresses in the memory are analyzed. The add_or_update_successful method attempts to add a page to the page table. In the event of failure, the add_after_page_fault method is started. The process is repeated until the addresses are exhausted.
def add_or_update_successful(self, vpn, read_or_write):
"""
Takes care of next page in trace
:param vpn: virtual page number
:param read_or_write: read or write action
:return: boolean: hit == true, evict == false
"""
if self.is_hit(vpn, read_or_write):
return True
self.evict = True
self.evict_page()
return FalseThe above method attempts to add a page to the page table. If it is not present in the table, then the function responsible for selecting the appropriate page to be deleted, i.e. the oldest used, is performed.
def is_hit(self, vpn, read_or_write):
"""
Checks if there is a hit in page.
If yes, marks page according to read_or_write.
:param vpn: virtual page number
:param read_or_write: access type
:return: was page in frame table
"""
for elem in self.frame_list:
# check for it a hit
if elem.vpn == vpn:
self.hit = True
elem.in_use = True
elem.vpn = vpn
if read_or_write == 'W':
elem.dirty = True
elem.last_reference = self.page_table.total_memory_accesses
return True
self.hit = False
return Falseis_hit checks if the specified virtual page address exists in the page table. If it exists, then the variable storing the number of the last reference to the page (last_reference) is updated, which determines when the page was last used.
def evict_page(self):
"""
Gets rid of last page
"""
lowest_value = None
lowest_value_ppn: int = 0
for elem in self.frame_list:
# index by the key to get a value
value = elem.last_reference
# find the lowest value overall, and get its PPN and VPN
if lowest_value is None or value < lowest_value:
lowest_value = value
lowest_value_ppn = elem.ppn
# remove the lowest value vpn
self.remove(lowest_value_ppn)
def remove(self, ppn: int):
"""
Removes selected ppn from page_table
:param ppn: physical page number (index)
"""
removal_page = self.frame_list[ppn]
# if the page is dirty, we need to do a disk write
if removal_page.dirty:
self.dirty = True
removal_page.in_use = False
removal_page.dirty = False
removal_page.vpn = NoneThe above methods are used to find and delete the page that you use most recently. A page is searched for with the lowest value of last_reference. Before the removal, it is checked whether the page should be saved to disk.
def add_after_page_fault(self, vpn: int, read_or_write: str):
"""
Adds to an empty space
:param vpn: virtual page number
:param read_or_write: read or write action
:return: boolean: true == page was added, false == all items are in use
"""
for elem in self.frame_list:
if not elem.in_use:
elem.in_use = True
elem.vpn = vpn
# if we're doing a write, need to set dirty bit
if read_or_write == 'W':
elem.dirty = True
elem.last_reference = self.page_table.total_memory_accesses
return True
# if we make it this far, then all items are in use, so return false
return FalseThe second function used in the main method is executed when a page error occurs. The previous method has already removed the last page, so this one just has to find a free frame and insert a new address into the page table.
The aging algorithm has been implemented in the Aging class in the aging.py module.
In the constructor, a previously created instance of PageTable class and parsed data from the text file (ADDRESS, R/W) are forwarded in the constructor subsequent addresses of the memory along with the type of operation to be performed (read/write).
def __init__(self, page_table, trace, refresh_rate, keep_states: bool = False):
self.page_table = page_table
self.trace = trace
self.frame_queue = page_table.frame_table
self.hit = False
self.evict = False
self.dirty = False
index = 0
for elem in self.frame_queue:
elem.ppn = index
index += 1
# refresh variables for aging
self.refresh_time_in_processed_instructions = refresh_rate
self.time_of_last_refresh = 0
self.keep_states: bool = keep_states
self.table_states: list = []Initialized variables are hit = False (the page is in the table of pages), evict = False (eviction of the page), dirty = False (modified page).
The numbering of frames in the frame array frame_queue is also created, the initialized variable refresh_time_in_processed_instructions responsible for the frequency of updating counters (counted in downloads of subsequent addresses) and variable time_of_last_refresh counting processed addresses from the previous update of counters.
The main method of Aging is the run_algorithm method.
The steps of the run_algorithm method are executed when subsequent memory addresses are available along with the R/W operation:
- resetting variables:
1. hit = False
2. evict = False
3. dirty = False
-
download the next pair (MEMORY ADDRESS, R/W) from memory and increase the counter of all memory references page_table.total_memory_accesses by one
-
calculating the virtual page number based on the memory address with the help of the static method get_vpn class PageTable
-
download the next type of operation (R/W) to the variable next_read_or_write
-
calling the function add_or_update_page
def add_or_update_page(self, vpn, read_or_write): """ Tries to add/update a page. If not possible, evicts a page. :param vpn: :param read_or_write: """ if self.is_hit(vpn, read_or_write): return if self.was_empty_page_used(vpn, read_or_write): return # otherwise page table is full and there is need to evict a page with lowest value lowest_value_page_number = 0 # higher than highest value in the COUNTER_LENGTH-bit counter lowest_value_overall = 2 ** Aging.COUNTER_LENGTH for elem in self.frame_queue: if elem.aging_value < lowest_value_overall: lowest_value_page_number = elem.ppn lowest_value_overall = elem.aging_value self.evict_lowest_value_page(lowest_value_page_number) if not self.was_empty_page_used(vpn, read_or_write): raise Exception("There should have been an empty page used!")
1. first checking if the page already exists in the table of pages: calling the function is_hit(vpn, read_or_write)
def is_hit(self, vpn, read_or_write):
"""
Checks if there is a hit in page.
If yes, marks page according to read_or_write.
:param vpn:
:param read_or_write:
:return:
"""
for elem in self.frame_queue:
# check for it a hit
if elem.vpn == vpn:
self.hit = True
if read_or_write == 'W':
elem.dirty = True
elem.reference = True
return True
return False2. if the page does not exist (page error), then check if any frame is not in use:
def was_empty_page_used(self, vpn, read_or_write):
"""
Looks for an empty page and if found, uses it
:return:
"""
for elem in self.frame_queue:
if not elem.in_use:
elem.in_use = True
elem.vpn = vpn
if read_or_write == 'W':
elem.dirty = True
elem.reference = True
return True
return False3. otherwise, find the frame with the smallest counter value aging_value
1. all frames are viewed and selected one whose counter aging_value is the smallest
2. the evict_lowest_value_page function is invoked which accepts as an index a frame index with the smallest counter value aging_value - it resets the frame, including aging_value
3. the function was_empty_page_used is called, which finds an empty frame and fills it
- calling the function collect_data_on_references_during_this_tick
1. increment of variable time_of_last_refresh
2. updating the oldest bit of the reference counter on the basis of the current reference bit of each page (OR the oldest bit of the counter with a reference bit), then reset each reference bit to False
3. if time_of_last_refresh >= refresh_time_in_processed_instructions
1. calling the function age_counter or dividing the counter by 2 (bitwise shift to the right by 1)
For each next address printed on the screen are information about the processed address depending on the result of the algorithm:
-
the page has been hit (no page error)
-
page error occurred, but you did not have to delete another page (the page table was not full)
-
page error occurred, another page was removed from the page table, but you did not have to write it to the disk (the modification bit was not set)
-
page error occurred, another page was removed from the page table, but you had to save it to the disk (the modification bit was set)
-
state of the page table
The optimal algorithm has been implemented in the Opt class in the opt.py module.
In the constructor, a previously created instance of PageTable class and parsed data from the text file (ADDRESS, R/W) are forwarded in the constructor subsequent addresses of the memory along with the type of operation to be performed (read/write).
def __init__(self, page_table, trace, keep_states: bool = False):
self.page_table = page_table
self.trace = trace
# KEY = VPN, VALUE = [NUM_LOADS_UNTIL_USED]
self.time_until_use_dict = {}
self.hit = False
self.evict = False
self.dirty = False
self.keep_states: bool = keep_states
self.table_states: list = []
self.initialize_ppns()
self.preprocess_trace()A time_until_use_dict dictionary is also created, which is filled in the preprocess_trace method. In this dictionary, the keys are virtual page numbers (Virtual Page Numbers), and list values that contain consecutive numbers of subsequent memory references, starting from reference number 0. After processing all memory references, None is added at the end of each list. that there are no further references to this virtual page number.
Initialized variables are hit = False (the page is in the table of pages), evict = False (eviction of the page), dirty = False (modified page).
The main method of the Opt class is the run_algorithm method.
The steps of the run_algorithm method are executed when subsequent memory addresses are available along with the R/W operation:
- resetting variables:
1. hit = False
2. evict = False
3. dirty = False
-
download the next pair (MEMORY ADDRESS, R/W) from memory and increase the counter of all memory references page_table.total_memory_accesses by one
-
calculating the virtual page number based on the memory address with the help of the static method get_vpn class PageTable
-
updating the counters with the update_counters method taking as the argument the virtual page number
1. retrieve a list of subsequent memory references for this page from the dictionary time_until_use_dict
2. getting the first item from this list (this is the current usage of this page)
3. do the following for each frame from the page table, provided it is in use - bit in_use
1. decrementing the meter instructions_until_next_reference
2. for frames with addresses just processed, find the next reference to the page with the find_time_until_next_access function accepting the number of the virtual page as an argument (Virtual Page Number)
1. retrieve the value of time before the next use of a page with a given number from the dictionary time_until_use_dict
2. if you encounter None, i.e. no further referrals to the page, return the content that is the incremented length of the list containing the remaining addresses to be processed (to simulate subsequent use of the page)
3. Otherwise, return the difference of the collected time value from the dictionary with the amount of all previous references to the memory
- calling the opt method on a pair containing address and operation read/write
1. retrieve the virtual page number function from the argument
2. getting the operation type function (R/W) from the argument
3. in the absence of a page error (function is_page_fault with argument being page number) – designation hit = True (hit)
1. additionally, in the case of write ('W'), finding a page index in the page table (find_vpn_in_page_table function) and marking the frame as modified - dirty bit
4. in case of page error - counter increment page_table.page_faults, no hit (hit = False) and function call add_vpn_to_page_table_or_update
1. the free frame is searched in the table of pages
def add_vpn_to_page_table_or_update(self, vpn, r_or_w):
"""
If there is a page fault:
- if page table isn't full, add next memory address
- if page table is full, go through the whole list of accesses, and find the VPN that's in memory,
which won't be used for the longest time in the future, pick that memory address and remove it
When going through the access list for each each page, assign it a value, how long until NEXT
use. Then, perform search only if it is unknown how long until next use,
for new otherwise subtract 1 from the values in the table each mem load
if dirty, write to disk, count a disk write
Checks if vpn is already in page_table.
If it is, iterate through all the frames in the page table, and if there's an empty space, use it.
:param vpn: virtual page number
:param r_or_w: read or write type of access
"""
if vpn not in self.page_table.fast_index:
page_added = False
index = 0
for frame in self.page_table.frame_table:
if not frame.in_use:
page_added = True
frame.in_use = True
frame.dirty = False
frame.vpn = vpn
frame.ppn = index
frame.instructions_until_next_reference = self.find_time_until_next_access(vpn)
self.page_table.fast_index[vpn] = frame.ppn
if r_or_w == 'W':
frame.dirty = True
break
index += 1
if not page_added:
self.evict_vpn_from_page_table()
self.add_vpn_to_page_table_or_update(vpn, r_or_w)
else:
raise Exception("VPN should not be in page_table!")however, if the page has not been added (no free frame), the evict_vpn_from_page_table function is started, iterates over the whole page table and finds the frame with the largest value instructions_until_next_reference
def evict_vpn_from_page_table(self):
"""
Iterates over all frames and finds frame with biggest instructions_until_next_reference value
as well as least needed PPN. Removes this page.
If page is dirty, increases disk writes by 1.
"""
least_needed = 0
most_instructions = 0
for frame in self.page_table.frame_table:
if frame.instructions_until_next_reference > most_instructions:
least_needed = frame.ppn
most_instructions = frame.instructions_until_next_reference
removal_frame = self.page_table.frame_table[least_needed]
self.page_table.fast_index.pop(removal_frame.vpn)
removal_frame.in_use = False
removal_frame.vpn = None
removal_frame.instructions_until_next_reference = None
if removal_frame.dirty:
self.page_table.writes_to_disk += 1
self.evict = True
self.dirty = True
else:
self.evict = True
self.dirty = False2. the next step is to call the function add_vpn_to_page_table_or_update again
For each next address printed on the screen are information about the processed address depending on the result of the algorithm:
-
the page has been hit (no page error),
-
page error occurred, but you did not have to delete another page (the page table was not full),
-
page error occurred, another page was removed from the page table, but you did not have to write it to the disk (the modification bit was not set),
-
page error occurred, another page was removed from the page table, but you had to save it to disk first (the modification bit was set),
-
state of the page table.
Reading the input data from the .trace file enables the input_parser.py module. The parse_trace_file function reads data from a pre-determined file format and creates a list of tuple objects, i.e. non-modifiable lists. In each of the tuple objects in the first index, there is a 32-bit memory address hexadecimal in the form of a string object, and in the second type of operation (R/W).
The function returns a list.
parse_trace_file function: // TODO:
The results that were obtained in CSV format, as described in Structure of results, have been imported into Microsoft Excel.
At the same time you can run all the steps necessary to generate results using a script written in bash:
// TODO:
The TRACES and FRAMES tables give numerical values for the number of addresses that should be generated and the number of frames that should be used by the algorithms.
The script is used to parameterize (from table data) two scripts written in Python. First, three files are generated with input data, and then, for each of the files, all algorithms are executed for each of the frame lengths.
Measurements were made for three different sizes of input files: 100000, 250000 and 500000. For each of them, the effect of different number of frames (16, 32 and 64) on the number of page errors and the number of writing to the disk and the operation time of the algorithm was examined.
As a result, 9 CSV files are obtained, which are subjected to further manual analysis.
The tree of described files after executing the script is as follows:
The results for the algorithms are presented in bulk, placing all their waveforms on a single graph to obtain the visualization of differences with the same input data.