\documentstyle[12pt]{article}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{22cm}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\parskip}{5pt plus 2pt minus 3pt}

\def\thefootnote{\fnsymbol{footnote}}
\setcounter{footnote}{1}

\renewcommand{\baselinestretch}{1.4}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}

% to get nice proofs ...
\newcommand{\qedsymb}{\mbox{ }~\hfill~{\rule{2mm}{2mm}}}
\newenvironment{proof}{\begin{trivlist}
\item[\hspace{\labelsep}{\bf\noindent Proof: }]
}{\qedsymb\end{trivlist}}

\parskip 0.1in
\pagenumbering{arabic}    %  Start using 1,2,... as page numbers.
\pagestyle{plain}         %  Page numbers in middle bottom of page.
\setcounter{page}{1}
\setcounter{theorem}{1}

\begin{document}

\begin{center}
{\bf CIS 657 OPERATING SYSTEMS}
{\bf FALL 1995}

{\bf SEMESTER PROGRAMMING PROJECT REPORT}

{\bf Mehmet Sen }

{\bf Design and Implementation of LRU Paging System }
\end{center}

\section {\bf Why LRU System Implementation?}
Without any doubt when a page fault occurs, the ideal page replacement algorithm should intelligently 
replace the page in memory, which will be referenced in the furthest time in the future, or may not be 
referenced at all. However, it is nearly impossible 
in the reality to know which page in the memory will be used at what time. On the other hand, 
this unrealistic ideal page replacement algorithm's performance is always aimed to reach as close as 
possible by many realistic algorithms' approximations.

One important principle to regard while measuring performance of the page replacement algorithms is the 
locality of reference principle. Locality of reference says that processes show the
 tendency to re-reference pages they have referenced recently.  A common rule is that a process
 execute 90\% of the time in only 10\% of the code. For the data accesses, the locality of 
reference principle still works. Two locality of reference principle is defined for the data
 references. First, the temporal locality says 
that recently accessed items are likely to be accessed in the near future. Second locality principle,  
spatial locality, is that nearby items to the current reference will tend to be referenced soon.

Because LRU ( Least Recently Used ) page replacement algorithm exactly reflects the ideas of the locality of reference principles, in large set of page replacement algorithms, LRU has been accepted among the best approximation algorithms to the optimal on
e. As its name implies, when a page fault occurs, LRU always keep the recently accessed pages in memory  hoping to reuse it again and again as locality of reference principle inform. During the data references, temporal locality principle exactly fits to 
the idea of the LRU algorithm. A simple example to this  principle is a switch statement, for instance, control variable is checked twenty times. Again if we look from the perspective of the spatial locality principle, the items, which will be referenced 
soon, are in the same page or nearby page with a very high probability.  Therefore the least referenced page might be locally furthest page to the current referenced part of the program. Any reference to it is not expected unless it is rarely out of the princ
principle. As a result, LRU logic is a reflection of the spatial locality principle.

Additionally, LRU algorithm does not have Bleady's anomaly. When we increase the number of the page frames in memory by adding new memory, the  page fault rate does not increases because if we increase memory size by some number of page frames and re-execu
reexecute the input sequence on this memory, at each step of page references, all the pages of first run  present in memory will also be in memory with extra pages.  If Bleady's anomaly would occur with LRU algorithm, another algorithm would show a better perfor
mance by using less page frame with respect to the specific processes or some sequences of commands. To do the same job by modifying LRU would be obviously hard, i.e. how to find optimal number of page frames for the specific runnings before run them. For
tunately, LRU does not show the Bleady's anomaly and is easy to implement.

Finally, my LRU implementation is using global allocation of the process pages in memory. Therefore, processes can run without thrashing up to 8 pages of the working set sizes. Any local implementation would cause problems, i.e. thrashing, by larger working
 sets of processes than reservations for them. For example, if we allocate three page frame for a process, and processes' working sets consists of pages 3,4,5,7, it would cause a lot of page fault during the run of the process.

\section {\bf Further analysis of LRU}

Although LRU algorithm is a good approximation to the ideal algorithm, not every implementation of it exactly simulates a real LRU algorithm. Some LRU implementations try to approximate to optimal LRU logic.  For example, the aging algorithm can not detec
t which page is least recently used when two pages have the same lowest counter value. An aging system will randomly kick out one of the lowest clock pages from the memory.  In contrast, this implementation exactly  simulates LRU algorithm. At each step, 
all the page frames has a distinct reference number.

My implementation of the LRU algorithm is usually done by hardware. For n page frames in the machine, the LRU table consists of nxn bits, and other utility functions to keep track this table. Unfortunately, this bring a hardware dependency to the operatin
g system designers, which is usually not desired. Also, the cost for LRU registers and other functions of it makes LRU hardware implementation unattractive. On the other hand, this kind of hardware implementation can also be done in software, exactly in t
he same manner as I wrote the program. Again, software implementation causes two problems. Doing hardwares job in software slows down the machine, and for large number of page frames storage for LRU increases.  Despite all, the software implementation is
 easy and a couples of lines long as I did.

LRU algorithm gives good page fault rates because it corresponds to the locality of reference principles as mentioned in the previous section. For example, the following program sample executes for a long time without causing any page fault, because all t
he necessary program parts remains in the memory during the loop, a real example to this situation is represented as example 1  in System Runnings section ;

	
\begin{verbatim}	
                        PROGRAM	                        MEMORY
                        ......     reference	
                        part(1)    ----->page 1	        page 1
               loop:    part(2)    ----->page 2         page 2
                        part(3)	   ----->page 3	        page 3
                        part(4)	   ----->page 4	        page 4
                        loop_end;		 	
                        ......
                        ......
\end{verbatim}

One disadvantage of LRU algorithm occurs when pages are referenced in a loop larger than the page frames, as following example shows, for each part of the program a page faults occurs continuously for every iteration of the loop, which is called as trashi
ng. A thrashing real example is represented as example 2 in System Runnings section.  The main reason here for the thrashing is the working set of the process larger than the memory ;

\begin{verbatim}	
                        PROGRAM                           MEMORY
                        ......     reference	
                        part(1)    ----->page 1            ...
                  loop: do_F2()    ----->page 2           fault
                        do_F3()    ----->page 3           fault
                         ....      ............					
                        do_F11()   ----->page 11          fault
                        loop_end;                          ...
                        ......         ...                 ...
                        ......
\end{verbatim}	

Here, do\_F\# is a function call to another part of the program code. Such a loop causes different pages to be loaded.	

Another weakness of the LRU is that it replaces only one page when a page fault occurs. For the case of swapping every reference to pages of the new program will cause a page fault. In fact, several neighbor pages, spatial locality principle works, can be
 loaded to memory at once. This decreases clearly page fault rate. For instance, the following command sequence causes at least 24 page faults by this LRU implementation;

      W1 W2 W3 R1 1 2 3 4 5 6 7 8 W1 R2 1 2 3 4 5 6 7 8 W2 R3 1 2 3 4 5 6 7 8 R1...

Here every page of the working set of each process is loaded one by one to the memory. Resulting page faults are caused from the loading of working sets. Furthermore, a clever algorithm may load more than one pages to memory with respect to working set wh
en a page fault occurs even if the same process is running.  When a change of the working set is the manner, process will not wait for the loading of the working set on coming references. An example to changing of working sets can be compilers with multip
le passes, at each pass compiler may work on the different parts. The following command sequence illustrates this situation for one process, which is also  represented as example 3 in System Runnings section;

W1 R1 1 2 3 4 5 6 7 7 8 8 2 3 9 10 11 12 12 13 14 15 1 2 3 4 5 6 5 6 5 6 7 7 8  etc.
set:  1 1 1 1 1 1 1 1 1 1 1 1 2 2  2  2  2  2  2  2  1 1 1 1 1 1 1 1 1 1 1 1 1  etc.


One more weakness of LRU, so of my implementation, occurs with the following input sequence :

W0 W1 W2 R1 0 1 2 1 2 5 6 5 1 2 9 10 DM B1 R2 0 1 0 1 7 4 2 9 DM B2
W1 W2 R1 0 1 2 1 2 5 6 5 1 2 9 10 DM  ....

When process 2 finishes its run, there are some pages of process 1 in memory.  However, process 1 begin to replace them when a page fault occurs because they are least recently used. In other words in this implementation, a process may kick out its own pages from the memory, in fact it will need them a couple reference later because they are in its working set. This intermediate steps, starting just before running of process 1 again,  are as following:

\begin{verbatim}
Current MEMORY state:

Page Frame      :    0      1      2      3      4      5      6      7   
~~~~~~~~~~~~~~~~~~ ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~ 
Process#,Page#  :   2, 1   2, 2   2, 9   2, 4   2, 7   1, 9   1,10   2, 0 

Page Fault: (1,0) put in frame 5 replacing (1,9).
Page Fault: (1,1) put in frame 6 replacing (1,10).
Page Fault: (1,2) put in frame 7 replacing (2,0).
Page Fault: (1,5) put in frame 0 replacing (2,1).
Page Fault: (1,6) put in frame 4 replacing (2,7).
Page Fault: (1,9) put in frame 3 replacing (2,4).
Page Fault: (1,10) put in frame 1 replacing (2,2).

Current MEMORY state:

Page Frame      :    0      1      2      3      4      5      6      7   
~~~~~~~~~~~~~~~~~~ ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~ 
Process#,Page#  :   1, 5   1,10   2, 9   1, 9   1, 6   1, 0   1, 1   1, 2 


\end{verbatim}

On the other hand, many of the page replacement algorithms are implemented in the same fashion with the LRU.



\section {\bf Assumptions}
\normalsize 

Simulated machine has 8 page frames, numbered from 0 to 7.\\
There are at most 16 processes in the system at any time. They
are numbered from 0 to 15.\\
Each process has a virtual address space of 16 pages, which are numbered from
0 to 15.\\
I have done all the state transition controls and some checks on input sequence, so following commands will produce error messages; ( see example 4 in program runnings section) 

	GHS : Undefined command

	B7 R7 : Blocked process can not run

	R78 : process number out of range, ( caused by system )

	34 : Reference number out of range, ( caused by user program or system )\\
Commands are only printed on the screen, not into standard output file, if program runs in interactive mode,(see how to run program section).

\section {\bf Data Structures}

The main data structures for the ``pager'' are\\
Waiting Queue:

\hspace{1.0in}{\tt int WaitQ[MAX\_process];}	  /* Holds waiting list in an array*/\\
Blocked Queue:

\hspace{1.0in} {\tt int Blocked[MAX\_process];} /* Holds blocked processes in an array*/\\
Running process holder:

\hspace{1.0in} {\tt int Runner; }       /* initially no process is running */\\
Page Frame table: stores  process number and its page for each page frames in the memory.
\begin{verbatim}
           typedef struct frame_entry_type{
                int process;
                int page;
           }frame_entry;
           frame_entry PFrame[MAX_frame];
\end{verbatim}

LRU matrix: keeps 8x8 LRU matrix to simulate a LRU algorithm. 

\hspace{1.0in}        unsigned char LRUtable[MAX\_frame];



\section {\bf How to run the program }
\hspace{.5in}Correct usage of the program is as following:

\hspace{1.0in}	\% pager  [$-$f inputfilename ] [ $< stdinputfile ] [ > stdoutputfile]$

The program has three version of execution:\\
1. You can use simply standard input as following;

\hspace{1.0in} \% pager  $<$ inputfile$ [ > outputfile ] $

      Pager just read standard input and execute with respect to it.\\
2. You may prefer entering commands by keyboard, by not directing standard input to the executable file, as following

\hspace{1.0in} \% pager $ [ > an\_outputfile ]$\\
\hspace{.0in}3. You may run program in a semi$-$interactive fashion as following:

\hspace{1.0in}\% pager $-$f \space  inputfilename [ $> outputfile ]$

 In that case program wait until ``enter'' key is pressed in interactive mode. If input is not null, it execute this user command. However, if user gives a null command, this means to pager that pager must take the next command from the input file. By usi
ng this interactive mode, user can add any command among the commands ordered in a file, for example, one can reference extra pages and see the memory states.


\section {\bf System Runnings}

{\bf Example 1:}
\small
\begin{verbatim}
ortrud% cat ex1
W0 W1 R1 0 1 2 3 4 5 3 4 5 3 4 5 3 4 5 3 4 5 3 4 5 3 4 5 6 7 B1 DM R0 4 5 
6 7 8 7 8 7 8 7 8 7 8 9 13 13 13 13 13 13 14  DM
ortrud% pager < ex1
Page Fault: (1,0) put in frame 0.
Page Fault: (1,1) put in frame 1.
Page Fault: (1,2) put in frame 2.
Page Fault: (1,3) put in frame 3.
Page Fault: (1,4) put in frame 4.
Page Fault: (1,5) put in frame 5.
Page Fault: (1,6) put in frame 6.
Page Fault: (1,7) put in frame 7.

Current MEMORY state:

Page Frame      :    0      1      2      3      4      5      6      7   
~~~~~~~~~~~~~~~~~~ ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~ 
Process#,Page#  :   1, 0   1, 1   1, 2   1, 3   1, 4   1, 5   1, 6   1, 7 

Page Fault: (0,4) put in frame 0 replacing (1,0).
Page Fault: (0,5) put in frame 1 replacing (1,1).
Page Fault: (0,6) put in frame 2 replacing (1,2).
Page Fault: (0,7) put in frame 3 replacing (1,3).
Page Fault: (0,8) put in frame 4 replacing (1,4).
Page Fault: (0,9) put in frame 5 replacing (1,5).
Page Fault: (0,13) put in frame 6 replacing (1,6).
Page Fault: (0,14) put in frame 7 replacing (1,7).

Current MEMORY state:

Page Frame      :    0      1      2      3      4      5      6      7   
~~~~~~~~~~~~~~~~~~ ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~ 
Process#,Page#  :   0, 4   0, 5   0, 6   0, 7   0, 8   0, 9   0,13   0,14 


********************************
* Pager finished execution...  *
* Number of page faults is 16. *
********************************
ortrud%

\end{verbatim}

{\bf Example 2:}
\small
\begin{verbatim}
ortrud% cat ex2
W0 R0 0 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 2 3 4 
5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10
ortrud% pager < ex2 | more
Page Fault: (0,0) put in frame 0.
Page Fault: (0,1) put in frame 1.
Page Fault: (0,2) put in frame 2.
Page Fault: (0,3) put in frame 3.
Page Fault: (0,4) put in frame 4.
Page Fault: (0,5) put in frame 5.
Page Fault: (0,6) put in frame 6.
Page Fault: (0,7) put in frame 7.
Page Fault: (0,8) put in frame 0 replacing (0,0).
Page Fault: (0,9) put in frame 1 replacing (0,1).
Page Fault: (0,10) put in frame 2 replacing (0,2).
Page Fault: (0,2) put in frame 3 replacing (0,3).
Page Fault: (0,3) put in frame 4 replacing (0,4).
Page Fault: (0,4) put in frame 5 replacing (0,5).
Page Fault: (0,5) put in frame 6 replacing (0,6).
Page Fault: (0,6) put in frame 7 replacing (0,7).
Page Fault: (0,7) put in frame 0 replacing (0,8).
Page Fault: (0,8) put in frame 1 replacing (0,9).
Page Fault: (0,9) put in frame 2 replacing (0,10).
Page Fault: (0,10) put in frame 3 replacing (0,2).
Page Fault: (0,2) put in frame 4 replacing (0,3).
Page Fault: (0,3) put in frame 5 replacing (0,4).
Page Fault: (0,4) put in frame 6 replacing (0,5).
Page Fault: (0,5) put in frame 7 replacing (0,6).
Page Fault: (0,6) put in frame 0 replacing (0,7).
Page Fault: (0,7) put in frame 1 replacing (0,8).
Page Fault: (0,8) put in frame 2 replacing (0,9).
Page Fault: (0,9) put in frame 3 replacing (0,10).
Page Fault: (0,10) put in frame 4 replacing (0,2).
Page Fault: (0,2) put in frame 5 replacing (0,3).
Page Fault: (0,3) put in frame 6 replacing (0,4).
Page Fault: (0,4) put in frame 7 replacing (0,5).
Page Fault: (0,5) put in frame 0 replacing (0,6).
Page Fault: (0,6) put in frame 1 replacing (0,7).
Page Fault: (0,7) put in frame 2 replacing (0,8).
Page Fault: (0,8) put in frame 3 replacing (0,9).
Page Fault: (0,9) put in frame 4 replacing (0,10).
Page Fault: (0,10) put in frame 5 replacing (0,2).
Page Fault: (0,2) put in frame 6 replacing (0,3).
Page Fault: (0,3) put in frame 7 replacing (0,4).
Page Fault: (0,4) put in frame 0 replacing (0,5).
Page Fault: (0,5) put in frame 1 replacing (0,6).
Page Fault: (0,6) put in frame 2 replacing (0,7).
Page Fault: (0,7) put in frame 3 replacing (0,8).
Page Fault: (0,8) put in frame 4 replacing (0,9).
Page Fault: (0,9) put in frame 5 replacing (0,10).
Page Fault: (0,10) put in frame 6 replacing (0,2).
Page Fault: (0,2) put in frame 7 replacing (0,3).
Page Fault: (0,3) put in frame 0 replacing (0,4).
Page Fault: (0,4) put in frame 1 replacing (0,5).
Page Fault: (0,5) put in frame 2 replacing (0,6).
Page Fault: (0,6) put in frame 3 replacing (0,7).
Page Fault: (0,7) put in frame 4 replacing (0,8).
Page Fault: (0,8) put in frame 5 replacing (0,9).
--More--
Page Fault: (0,9) put in frame 6 replacing (0,10).
Page Fault: (0,10) put in frame 7 replacing (0,2).

********************************
* Pager finished execution...  *
* Number of page faults is 56. *
********************************
ortrud%


\end{verbatim}

\normalsize
{\bf Example 3:}
\small
\begin{verbatim}
ortrud% cat ex3
W0 R0 1 2 3 4 5 6 7 7 8 8 2 3 DM 9 10 11 12 12 13 14 15 DM 2 1 1 2 3 4 5 6 
5 6 5 6 7 7 8 8 DM  
ortrud% pager < ex3
Page Fault: (0,1) put in frame 0.
Page Fault: (0,2) put in frame 1.
Page Fault: (0,3) put in frame 2.
Page Fault: (0,4) put in frame 3.
Page Fault: (0,5) put in frame 4.
Page Fault: (0,6) put in frame 5.
Page Fault: (0,7) put in frame 6.
Page Fault: (0,8) put in frame 7.

Current MEMORY state:

Page Frame      :    0      1      2      3      4      5      6      7   
~~~~~~~~~~~~~~~~~~ ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~ 
Process#,Page#  :   0, 1   0, 2   0, 3   0, 4   0, 5   0, 6   0, 7   0, 8 

Page Fault: (0,9) put in frame 0 replacing (0,1).
Page Fault: (0,10) put in frame 3 replacing (0,4).
Page Fault: (0,11) put in frame 4 replacing (0,5).
Page Fault: (0,12) put in frame 5 replacing (0,6).
Page Fault: (0,13) put in frame 6 replacing (0,7).
Page Fault: (0,14) put in frame 7 replacing (0,8).
Page Fault: (0,15) put in frame 1 replacing (0,2).

Current MEMORY state:

Page Frame      :    0      1      2      3      4      5      6      7   
~~~~~~~~~~~~~~~~~~ ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~ 
Process#,Page#  :   0, 9   0,15   0, 3   0,10   0,11   0,12   0,13   0,14 

Page Fault: (0,2) put in frame 2 replacing (0,3).
Page Fault: (0,1) put in frame 0 replacing (0,9).
Page Fault: (0,3) put in frame 3 replacing (0,10).
Page Fault: (0,4) put in frame 4 replacing (0,11).
Page Fault: (0,5) put in frame 5 replacing (0,12).
Page Fault: (0,6) put in frame 6 replacing (0,13).
Page Fault: (0,7) put in frame 7 replacing (0,14).
Page Fault: (0,8) put in frame 1 replacing (0,15).

Current MEMORY state:

Page Frame      :    0      1      2      3      4      5      6      7   
~~~~~~~~~~~~~~~~~~ ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~ 
Process#,Page#  :   0, 1   0, 8   0, 2   0, 3   0, 4   0, 5   0, 6   0, 7 


********************************
* Pager finished execution...  *
* Number of page faults is 23. *
********************************
ortrud%

\end{verbatim} \normalsize
{\bf Example 4:}
\small
\begin{verbatim}
python% pager
W1
R23
 
ERROR: Process # is not recognized! : 23
Unrecognized command...'R23' 
R1
1
Page Fault: (1,1) put in frame 0.
ERT
Unrecognized command...'ERT' 
B1
R1
Error in Queue:Process #1 can not run; it is currently blocked..
 Command is skipped !!! 
W1
R1
34
Unrecognized command...'34' 
3
Page Fault: (1,3) put in frame 1.
4
Page Fault: (1,4) put in frame 2.
DM
 
Current MEMORY state:
 
Page Frame      :    0      1      2      3      4      5      6      7   
~~~~~~~~~~~~~~~~~~ ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~  ~~~~~ 
Process#,Page#  :   1, 1   1, 3   1, 4    X      X      X      X      X   
 
Q
 
********************************
* Pager finished execution...  *
* Number of page faults is 3. *
********************************
python% 

\end{verbatim}
\normalsize
\section {\bf Conclusion}
	
Although its some weaknesses mentioned above, the LRU algorithm gives the best results possible on the basis of page fault rate as long as the locality of reference principles work on executed program code. Since it is impossible to know how the programs 
to behave in the future, without looking old runnings of the programs, this LRU algorithm implementation shows a performance among the best possible page replacement algorithms to approximate the theoretically ideal page replacement algorithm.

\section {\bf References }

1. CIS 657 Operating System Course, and materials.\\
2. CIS 655 Computer architecture Course, and materials.
\section {\bf Program Code }



\end{document}







