Description
1 Introduction
In this experiment, you will practice using binary search tree, unordered linked list and priority queue as heap tree data structures. You are expected to design and implement a program that will work like a basic page replacement scheme for memory management of operating systems. The algorithm that you are expected to implement will be a simpler version of FIFO(First In First Out) and Second Chance Page Replacement Algorithms.
2 Background
2.1 Virtual Memory
Virtual memory is a memory management technique of operating systems. It maps virtual adresses into physical adresses in computer memory. A memory management unit that is a hardware in CPU translates adresses to physical adresses and a software in OS provide a virtual adress space to use more memory than physically available memory space by using technique of paging.
2.2 Paging
The pages refer to the same-size data blocks in secondary storage and paging is to retrieve these pages to the main memory from secondary storage when a process wants to use specific data blocks i.e. pages. A program tries to to access pages that are not currently mapped to physical memory(RAM). This situation known as a page fault. The operating systems do the following steps to take page faults under the control: • Determine the location of the data in secondary storage. • Obtain an empty page frame in RAM. • Load data to the page frame. • Update the page table. • Return control to the program. If all page frames are non-empty, one of those frames must be chosen to empty for the following memory requirement. It is expected from an efficient page replacement algorithm that chosen frame must be least likely to be needed within a short time. There are various page replacement algorithms that try to do page replacement efficiently.
Page 1 of 6
Spring 2018 BBM 204: Software Laboratory II
2.3 Page Replacement Algorithms
When all frames is full and the data you have to read is not in the memory, then you have to replace data in a frame with the data required. The main problem regarding the memory replacement is de- ciding which frame is to be replaced. The FIFO page replacement algorithm use simple first in first out strategy to discard next frame on the queue when a page fault occurs so that the oldest frame is removed from memory to open place for latest data sequence. In order to recognize the FIFO page replacement algorithm, each item has to have a sequence number (seq no). Imagine we have a memory that can have 3 frames maximum and we have the following order of items that are read from the secondary storage:
Figure 1: First In First Out(FIFO) Page Replacement Algorithm
The structure of the memory flows as given in Figure 1. Once the all memory frames is full (after having 7, 0, 1), to make empty frame for the new item 2 the oldest used item 7 is removed from the memory and replaced with 2. The same process is repeated. The Second Chance Page Replacement Algorithm is called as the Clock Replacement algorithm in some books as well is a FIFO(First in First out) replacement algorithm. It works by looking at the front of the queue as FIFO does, but instead of immediately paging out that page, it checks to see if its referenced bit is set. If it is not set, the page is swapped out. Otherwise, the referenced bit is cleared, the page is inserted at the back of the queue (as if it were a new page) and this process is repeated.
Figure 2: Second Chance Page Replacement Algorithm
For same sequence in Figure 1, replacement procedure is shown in Figure 2 for Second Chance Page Replacement Algorithm. As can be seen on the Table 2, a second chance bit is set for each
Page 2 of 6
Spring 2018 BBM 204: Software Laboratory II
frame according to the following rules: • Each time a memory frame is referenced, set the ”second chance” bit to ONE (1) – this will give the frame a second chance… • A new page read into a memory frame has the second chance bit set to ZERO (0) • If the second chance bit is ONE, reset its second chance bit (to ZERO) and continue • If the second chance bit is ZERO, replace the page in that memory frame.
3 Problem Definition
In this experiment, you are expected to design a simpler version of the FIFO and Second Chance page replacement algorithms and to show efficiency of algorithms by comparing time complexity and the number of page faults. You will also implement binary search tree and unordered linked list data structures to search data that will be read from memory. Similarly you will show searching cost for these algorithms as well. Assume that you have a memory and it has variable number of frames. The CPU wants to read a stream of data items to memory from secondary storage. You can see an example in Figure 3 with memory with 4 frames.
Figure 3: Example Sequence and Memory Frames
3.1 Remarks About the Experiment • The data is read from Secondary Storage. • Your program must take input file path as argument. • You will consider alphabetic order for priority queue. • For main memory , an unordered linked list and a heap tree data structures have to be created for page replacement scheme. • Binary search tree will be used for searching the data items in the frames. • For second chance algorithm data structures must be modified with reference bit configuration.. • You must show number of page faults. • You must also show elapsed time for whole sequence).
Page 3 of 6
Spring 2018 BBM 204: Software Laboratory II
3.2 Scenario Samples
For example ,CPU wants to read data ’a’ from memory: • Check memory.(Binary search tree) • if ’a’ is not there(page fault) and memory have empty frame – Duplicate ’a’ to empty memory frame and adjust data structures(Binary Search Tree, Unordered List,Queue or Heap Tree) • if ’a’ is not there(page fault) and memory do not have empty frame – You have to empty a frame from memory – Use FIFO or Second Chance Page replacement algorithms on appropriate data structures – Remove data in front element of data structures.(Consider Reference bit for Second Chance algorithm) – Duplicate ’a’ to empty memory frame and adjust data structures. • if ’a’ is there, – Continue to sequences – Do not forget reference bit for Second Chance algorithm
3.3 Input and Output File
Consider example is given in Figure 4 and 5. We will supply codes for file operations to format output correctly.
Figure 4: Input-Output File Format(FIFO)
Page 4 of 6
Spring 2018 BBM 204: Software Laboratory II
Figure 5: Input-Output File Format(Second Chance)
Notes
• Do not miss the deadline. • Save all your work until the assignment is graded. • The assignment must be original, individual work. Duplicate or very similar assignments are both going to be considered as cheating. • YoucanaskyourquestionsviaPiazza. (https://piazza.com/hacettepe.edu.tr/spring2018/bbm204) and you are supposed to be aware of everything discussed in Piazza. • You will submit your work from https://submit.cs.hacettepe.edu.tr/index.php with the file hierarchy as below: