Mathematical Analysis of Page Fault Minimization for Virtual Memory Systems Using Working Set Strategy
Aslanbek Murzakhmetov, Gaukhar Borankulova, Arseniy Bapanov, Gabit Altybayev · Information · 2025
Poor code locality in virtual memory systems significantly contributes to page faults, leading to degraded system performance. Although many solutions aim to minimize page faults, most rely on clustering techniques that do not quantify the approximation error relative to the optimal solution. In this work, we develop a novel mathematical model based on the Working Set strategy combined with a geometric interpretation of the computational process via a Hasse diagram. This approach enables the reduction of the problem dimensionality and facilitates identification of critical control states under realistic constraints. We formalize the minimization of expected page faults as a discrete optimization problem with well-defined functionals and constraints. Experimental evaluation demonstrates that our model achieves lower average page faults and execution times compared to classical algorithms, especially under poor code locality conditions. Our method also provides a foundation for obtaining ε-optimal solutions and paves the way for designing efficient and cost-effective page replacement algorithms with provable guarantees. These contributions establish both theoretical and practical advances in virtual memory management.