On the Modeling of Paging Algorithm by Finite Automata

Abstract

Two finite automata are devised for modeling two classes of demand paging algorithms. The first one of one input and three outputs models the class of algorithms each with a constant amount of allocated space. The second one of one input and six outputs models the class of algorithms each with a variable amount of allocated space. Some evaluation techniques are developed following each model. The memory states of the first class algorithm with the LRU, FIFO or FILO replacement policy or of the second class algorithm like the working set model or the page-turning rate algorithm are recursively defined by strings of the loaded pages. The adopted replacement policy and the state string updating procedure are imbedded in the recursive definition of a memory state. The operations like loading, tagging,reutilizing, etc. are reflected and differentiated by different outputs. Properties of some algorithms are developed. Sime such properties confirm with previous results and some others are updated to fit the finiteness assumtion of a reference string.