The dynamic data structure management technique called hashing with lazy deletion (HwLD) is studied. A table managed under HwLD is built by a sequence of insertions and deletions of items. When hashing with lazy deletions, one does not delete items as soon as possible but keeps more items in the data structure than would be the case with immediate-deletion strategies. This deferral allows the use of a simpler deletion algorithm, leading to a lower overhead—in space and time—for the HwLD implementation. It is of interest to know how much extra space is used by HwLD. This paper investigates the maximum size and the excess space used by HwLD, under general probabilistic assumptions, by using the methodology of queueing theory. In particular, for the Poisson arrivals and general lifetime distribution of items, the excess space does not exceed the number of buckets in HwLD. As a byproduct of the analysis, the limiting distribution of the maximum queue length in an $M|G|\infty $ queueing system is also derived. The results generalize previous work in this area.

We study a data structure ${\bf L}$ referred to variously as a padded list, controlled density array or sparse table containing records $\{ R_i \} $ each uniquely identified by a key $\{ k(R_i )\} $. ${\bf L}$ is required to support the operations Search $({\bf L},k)$, Insert $({\bf L},k)$ and Delete $({\bf L},k)$ to search, insert and delete a record with key k. To optimize Search $({\bf L},k)$, records are stored with their keys in sorted order. If the order of the keys is to be maintained under insertion, records currently in ${\bf L}$ must be moved to free space. To improve the efficiency of Insert $({\bf L},k)$, records are stored in a circular buffer with “gaps” so that insertion necessitates moving only records up to the next gap. The array is expanded and contracted during a sequence of insertions and deletions depending upon the current number of gaps. In this paper we assess the amount of work required to insert a sequence of records.

Two queues are fed by independent, time-homogeneous Poisson arrival processes. One server is available to handle both. All service durations, in both queues, are drawn independently from the same distribution. A setup time is incurred whenever the server moves (switches) from one queue to the other. We prove that in order to minimize the sum of discounted setup charges and holdings costs, assumed linear in queue length and having the same rate at the two queues, the service at each queue should be exhaustive, A “threshold policy” is defined as a policy under which the server switches (from an empty queue) only when the other reaches a critical size. It is shown to be a likely candidate for the optimal policy, both for the discounted version and for the long-time average criterion. The steady-state performance of this policy (under somewhat more general distributional assumptions) and the optimal thresholds are determined for a number of cases.

Consider n transmission stations sharing a single communication channel. Packets arrive at the stations according tonindependent renewal processes, possibly with different rates. The transmitters are assumed to be able to store an unlimited number of packets in their buffers. The stations transmit packets during time slots allocated to them according to a given {\em conflict-free distributed protocol.} The cost criterion according to which protocols are evaluated is the long-run weighted average buffer occupancies. (The average waiting time is a special case of such a weighting.) A lower bound to the cost criterion under time division multiplexing (TDM) protocols is given, and the costs of two protocols are analyzed. The first protocol is the {\em random-control} policy, and the second is the {\em golden ratio} policy which is shown to achieve a cost close to the lower bound for realistic parameters.

Two related problems are analyzed and discussed: A queueing system that differs from the standard M/G/1 only in that at the end of a busy-period the server takes a sequence of vacations, inspecting the state of the queue at the end of each. When the length of the queue exceeds a predetermined level m it returns to serve the queue exhaustively.Two queues, with Poisson arrivals and general service-time distributions are attended by a single server. When the server is positioned at a certain queue it will serve the latter exhaustively, and at busy-period end will only switch to the other if the queue length there exceeds in size a predetermined threshold mi.The treatment combines analytic and numerical methods. Only steady-state results are presented.

An exact analysis is given of the main parameters that characterize the properties of the Capetanakis-Tsybakov-Mikhailov collision resolution algorithm with the free-access (continuous input) protocol. In particular, the distributions of the collision resolution interval, the delay experienced by a packet, and the state of the top level of the stack that is maintained by the algorithm are determined.

This paper describes and analyzes the SCAN policy, used to schedule read/write requests at a moving-arm disk device, when fast response over the entire disk area is at a premium. An analysis is presented which handles precisely the dependence structure between queues accumulated at different cylinders. The arrival process of requests to each cylinder is assumed Poisson and homogeneous in time. A relatively efficient algorithm for evaluating numerically the mean waiting time at each cylinder is presented and its complexity analyzed. We discuss further extensions intended to capture additional details of realistic situations. These include distributed record lengths, skipping unreferenced cylinders and letting successive arrivals’ target cylinders be dependent variables.

The history of modelling of the address sequences generated by computer programs (often termed “program behavior”) follows a familiar pattern: the better a hypothetical model fits experimental evidence, the less amenable it is for calculation. In this paper programs that generate successive page references that can be described by a first order Markov chain are considered. We produce a closed form expression for the distribution and usable expressions for the first moments of the steady state size of their working set of pages. These expressions are also specialized for the independent reference model and the Easton model. Only standard Markov chain theory is used.

A queueing-type model is used to analyze the storage requirements of a component of a real-time data entry system. The objectives and criteria of the buffer management procedure are identified and related to the variables of the model. Both infinite and finite buffers are considered. The analysis is done symbolically in part and numerically in part to accommodate input processes that are peculiar to the system. Techniques to obtain overflow probabilities are described in detail. It is shown that creating a pool of storage blocks for all the terminals is a better policy than maintaining a separate buffer for each station. The savings brought about by this policy are remarkably insensitive to the characteristics of the input process.

A demand-interrupting device is any attachment to a computer which, when busy, blocks a processor that reqmres further service from it In this paper there is considered a system with a processor rendering two types of serwce, so as to be able to take advantage of enforced idle times, which is connected to one or two demand-interrupting devices that feed back the programs to the processor.The dlstrzbution of the holding time in the processor and the utilization figures for all the components are computed under several assumptmns on the distributions of the serwces performed by the demand interrupting devices and the delay-type service performed by the processor The principal processor serwce duration is assumed to be exponentially distributed throughout the dlscussmn.

A scheduling rule is given for determining the processing order of tasks which have the precedence structure of chains. It is assumed that the service times follow known distributions, that they are all independent, that costs are accrued by tasks at a constant rate until their service requirements are satisfied, that all the tasks are available at time 0 and that the service is interruptible at task-specific sets of points. The rule consists of computing for each chain an “optimal assignment” for its tasks and a rank function which depends on this assignment. Choosing at each point in time the chain with the smallest rank produces an optimal schedule. It is proved that the “optimal assignments” have the desirable property that as long as a task does not exceed its allotted service time, no preemption should take place.

A simple computer system is described, which consists of a CPU and I/O unit and which works in a multiprogramming manner.The model assumes that the system works under heavy load so that the incoming queue is never empty, that the service times at the two units are exponentially distributed independent random variables, and that the number of iterations of the programs is geometrically distributed.Head of the line priority of programs which are being processed over newcomers is considered.Steady state distribution of the states of the system is numerically solved under the assumption of a finite waiting room.The suggested system is compared with one working in "batch mode" and with an equivalent multiprogramming system with a constant number of programs.The latter comparison shows that the suggested priority rule improves the expected response time without affecting the throughput and the utilizations of the CPU and the I/O unit.The model induces an interesting dependence phenomenon which is discussed at length.