On the relative dominance of paging algorithms

In this paper, we give a finer separation of several known paging algorithms using a new technique called relative interval analysis. This technique compares the fault rate of two paging algorithms across the entire range of inputs of a given size, rather than in the worst case alone. Using this technique, we characterize the relative performance of LRU and LRU-2, as well as LRU and FWF, among others. We also show that look-ahead is beneficial for a paging algorithm, a fact that is well known in practice but it was, until recently, not verified by theory.     

Binary trees paging

A dynamic page allocation technique for binary search trees is proposed. The method is based on page splitting, like the B-tree construction procedure, and on balanced bunch allocation into the pages. An analysis of the paged index structure resulting from the proposed allocation technique is performed. Furthermore the resulting index can be considered as a modification of B-trees in order to give a flexible structure to the keys in a page. A comparison with B-trees is then carried on, pointing out the field of application of the proposed approach.     

Exploiting the optimal paging algorithms

Paging, optimal algorithms     

一种船用气象要素相对湿度传感器

针对陆地用气象要素相对湿度传感器难以适应海洋高湿、高盐雾、高腐蚀环境的问题,研制了一船用气象要素相对湿度传感器。采用高精度湿敏元件,设计出频率发生电路,将空气相对湿度的变化量转换为频率信号;通过设计的频率电压转换电路将频率信号转换为电压信号;设计的线性化调理电路将变化的电压信号进行线性化处理,使电压的变化能够线性化地对应于空气相对湿度的变化。通过特殊结构和可靠性设计,满足了气象要素相对湿度传感器的海洋环境适应性。测试结果表明:研制的船用气象要素相对湿度传感器测量精度高、线性化好,能够适应于海洋环境。     

The iterated extended set membership filter applied to relative localization between autonomous vehicles based on GNSS and UWB ranging

This paper presents a novel Iterated Extended Set Membership Filter (IESMF) with an application to relative localization. For safe operation of formations of automatic vehicles, consistent uncertainty estimates are of crucial importance. Here, a localization filter that provides ellipsoidal regions that are guaranteed to contain another vehicles position is presented. The proposed iterative update step can appreciably reduce the size of the a posteriori state ellipsoid. The idea of using SIVIA as a baseline to quantify conservativeness is introduced. Another novelty is that we take into account parametric uncertainty of the observation equation. The proposed filter is applied to a two unmanned aircraft systems (UAS) localization problem in simulation with observation noise obtained from real sensors. Simulation results illustrate the effective reduction of filter conservativeness by a small number of iterative updates.     

Software paging in an interpretive environment

A simple software paging scheme for the interpretive language BALM is described. BALM, a high level extensible language, is extended to BALMSETL by adding the primitives of SETL, a very high-level set-theoretic language. BALMSETL is then used to execute SETL programs. Since these runs required large amounts of core memory (170K_Band up) the need for a paging system arose. The paging system implemented is completely automatic and hidden from the user to whom it appears that he has 200K_B words of additional core memory. Code blocks of varying size constitute pages which are rolled in on demand. Pages to be rolled out are selected on the basis of whether they are active or not and how long they have not been active. The algorithm for selecting pages to be rolled out is invoked by the garbage collector, which uses bit tables to identify code blocks and uses patterns within code blocks to select the appropriate number of pages.     

A strongly competitive randomized paging algorithm

Thepaging problem is that of deciding which pages to keep in a memory ofk pages in order to minimize the number of page faults. We develop thepartitioning algorithm, a randomized on-line algorithm for the paging problem. We prove that its expected cost on any sequence of requests is within a factor ofH _k of optimum. (H _k is thekth harmonic number, which is about ln(k).) No on-line algorithm can perform better by this measure. Our result improves by a factor of two the best previous algorithm.Partial support for D. D. Sleator was provided by DARPA, ARPA Order 4976, Amendment 20, monitored by the Air Force Avionics Laboratory under Contract F33615-87-C-1499, and by the National Science Foundation under Grant CCR-8658139.     

The paging drum queue: A uniform perspective and further results

Summary A uniform perspective for the performance analysis of drums organised around the sector concept under Poisson input is presented which allows further results on their operating characteristics to be naturally derived. Closed-form expressions are provided for (i) the mean device service time, (ii) the device utilisation, (iii) the drum efficiency, (iv) the mean device busy period, and (v) the mean number of page transfers per busy period. Both the FCFS and SLTF scheduling disciplines are studied. When the number of sectors per track is large, it is shown that some of the above quantities could be approximated by extremely simple asymptotic formulae if a suitable time unit is adopted. Generalisations of some of these results which are applicable to the performance analysis of solid-state secondary memory and certain computer communications systems — the polling server and the token ring — are also presented.     

A strongly competitive randomized paging algorithm

Thepaging problem is that of deciding which pages to keep in a memory ofk pages in order to minimize the number of page faults. We develop thepartitioning algorithm, a randomized on-line algorithm for the paging problem. We prove that its expected cost on any sequence of requests is within a factor ofH _k of optimum. (H _k is thekth harmonic number, which is about ln(k).) No on-line algorithm can perform better by this measure. Our result improves by a factor of two the best previous algorithm.     

Thek-server dual and loose competitiveness for paging

Weighted caching is a generalization ofpaging in which the cost to evict an item depends on the item. We study both of these problems as restrictions of the well-knownk-server problem, which involves moving servers in a graph in response to requests so as to minimize the distance traveled.We give a deterministic on-line strategy for weighted caching that, on any sequence of requests, given a cache holdingk items, incurs a cost within a factor ofk/(k–h+1) of the minimum cost possible given a cache holdingh items. The strategy generalizes least recently used, one of the best paging strategies in practice. The analysis is a primal-dual analysis, the first for an on-line problem, exploiting the linear programming structure of thek-server problem.We introduceloose competitiveness, motivated by Sleator and Tarjan's complaint [ST] that the standard competitive ratios for paging strategies are too high. Ak-server strategy isloosely c(k)-competitive if, for any sequence, foralmost all k, the cost incurred by the strategy withk serverseither is no more thanc(k) times the minimum costor is insignificant.We show that certain paging strategies (including least recently used, and first in first out) that arek-competitive in the standard model are looselyc(k)-competitive providedc(k)/Ink and bothk/c(k) andc(k) are nondecreasing. We show that the marking algorithm, a randomized paging strategy that is (Ink)-competitive in the standard model, is looselyc(k)-competitive providedk–2 In Ink and both 2 Ink–c(k) andc(k) are nondecreasing.This paper is the journal version of On-line Caching as Cache Size Varies, which appeared in theProceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (1991). Details beyond those in this paper may be found in Competitive Paging and Dual-Guided Algorithms for Weighted Caching and Matching, which is the author's thesis and is available as Technical Report CS-TR-348-91 from the Computer Science Department at Princeton University.This research was performed while the author was at the Computer Science Department, Princeton University, Princeton, NJ 08544, USA, and was supported by the Hertz Foundation.     

A decomposable model of program paging behaviour

Summary Existing models of program behaviour are shown to give an incomplete account of program locality. A model based on the distinction between short- and long-run equilibrium states in nearly completely decomposable systems is proposed to overcome this deficiency. This distinction leads to the combined use of a Markovian model of the transitions between localities and of separate models for the locality short-term behaviours. This combination is shown to give better estimations of the page fault rate and of the working set size distribution. The conditions under which this distribution is approximately normal and under which the assumptions of independent page references are valid are also clarified. The approach is illustrated by a numerical example, showing in particular that other models presented in the literature may have computer time and space requirements which are beyond practical possibilities.     

Programming and compiling strategies for paging systems

Designers of paging systems have tended to believe that programmers can influence system performance, but usually for the worse, rather than for the better. Their efforts to find operating system solutions to poorly styled programs may have discouraged efforts to produce paging-oriented compilers, to educate programmers in techniques to use under paging, and to open communication channels between the programmer and the paging system—all of which now promise to give increased satisfaction with paging systems.     

The decomposition method applied to stiff systems

The decomposition method is applied to a stiff system of differential equations to obtain a converging series which is summed for an analytic solution. Advantages over fourth- and fifth- order Runge-Kutta methods are shown.     

An experimentally validated model of the paging drum

Summary The behaviour of the paging drum or disc has a significant impact on the performance of multiprogrammed, paging systems. A study is made of such devices using the three tools of performance evaluation: an analytical model, a simulation model and empirical measurements. The models extend previous studies by including non-exponential arrival times and a comparison is made between the proposed analytical model and standard models using Poisson arrivals.     

Factorial experimental design applied to DRIE for optimised process in power electronics applications requiring high-aspect ratio trenches

A reliable factorial experimental design was applied to DRIE for specifically producing high-aspect ratio trenches. These trenches are to be used in power electronics applications such as active devices: deep trench superjunction MOSFET (DT-SJMOSFET) and passive devices: 3D integrated capacitors. Analytical expressions of the silicon etch rate, the verticality of the profiles, the selectivity of the mask and the critical loss dimension were extracted versus the process parameters. The influence of oxygen in the passivation plasma step was observed and explained. Finally, the analytical expressions were applied to the devices objectives. A perfectly vertical trench 100-μm deep was obtained for DT-SJMOSFET. Optimum conditions for reaching high-aspect ratio structures were determined in the case of high-density 3D capacitors.