Dynamic Spectrum Access systems exploit temporarily available spectrum ('white spaces') and can spread transmissions over a number of non-contiguous sub-channels. Such methods are highly beneficial in terms of spectrum utilization. However, excessive fragmentation degrades performance and hence off-sets the benefits. Thus, there is a need to study these processes so as to determine how to ensure acceptable levels of fragmentation. Hence, we present experimental and analytical results derived from a mathematical model. We model a system operating at capacity serving requests for bandwidth by assigning a collection of gaps (sub-channels) with no limitations on the fragment size. Our main theoretical result shows that even if fragments can be arbitrarily small, the system does not degrade with time. Namely, the average total number of fragments remains bounded. Within the very difficult class of dynamic fragmentation models (including models of storage fragmentation), this result appears to be the first of its kind. Extensive experimental results describe behavior, at times unexpected, of fragmentation under different algorithms. Our model also applies to dynamic linked-list storage allocation, and provides a novel analysis in that domain. We prove that, interestingly, the 50% rule of the classical (non-fragmented) allocation model carries over to our model. Overall, the paper provides insights into the potential behavior of practical fragmentation algorithms.

Our contribution in this paper is a scalable, easily implemented, self-organizing, energy conserving intrusion-detection sensor system applying concepts from cellular automata theory. The system self-assembles periodic wake-sensor barriers (waves) that sweep the sensor field; it is highly effective even in the case of frequent communication failures, sensor failures, large obstacles, and when intruders know sensor locations.

Cyclic Cellular Automata (CCAs) have been found to provide a natural, beguilingly simple, and elegant infrastructure for the design of sensor systems with sleep-wake scheduling to maximize system lifetime. The Greenberg-Hastings model (GHMZ) [3, 2] defined on the integer lattice Z2 is particularly appropriate and is described as follows. Each grid square of the integer lattice is a cell with a set of k ≫ 1 states and a neighborhood N; the neighborhoods of interest here are the von Neumann neighborhood and the Moore neighborhood. The von Neumann neighborhood Nx of cell x consists of just those cells to thenorth, east, south, and west of x, whereas the Moore neighborhood expands to that 3 £ 3 array of cells with x at its center, i.e., all cells that touch x at a side or vertex. All cells change state synchronously step by step according to aclock cycle and transition function common to all. The local rule for state changes is little more than a counter: The state »t+1(x) of cell x at time t + 1 is a simple mod k increment: »t+1(x) = »t(x) + 1 if »t(x) ≫ 0. But if »t(x) = 0;the state is incremented to 1 if and only if it has at least one neighbor in Nx which is currently in state 1.

While most transmission schemes in OBS networks relegate retransmission to higher protocol layers, the scheme proposed in this paper reduces retransmission delays by exploiting fiber delay lines at the optical layer. We present an analysis of the scheme that focuses not only on individual components but also on the end-to-end properties of the network. We also propose a facility location model suitable for optimizing the locations of sites with fiber delay lines when the number of such sites is limited. Evaluation of our proposed scheme on a common test network shows that major improvements in performance are possible.

No abstract available.

We consider the one-dimensional bin packing problem with unit-capacity bins and item sizes chosen according to the discrete uniform distribution U{j,k}, $1 < j \leq k,$ where each item size in {1/k,2/k,. . .,j/k} has probability 1/j of being chosen. Note that for fixed j,k as $m\rightarrow\infty$ the discrete distributions U{mj,mk} approach the continuous distribution U(0,j/k], where the item sizes are chosen uniformly from the interval (0,j/k]. We show that average-case behavior can differ substantially between the two types of distributions. In particular, for all j,k with j < k-1, there exist on-line algorithms that have constant expected wasted space under U{j,k}, whereas no on-line algorithm has even o(n 1/2 ) expected waste under U(0,u] for any $0 < u \leq 1$. Our U{j,k} result is an application of a general theorem of Courcoubetis and Weber [C. Courcoubetis and R.R. Weber, Probab. Engrg. Inform. Sci., 4 (1990), pp. 447--460] that covers all discrete distributions. Under each such distribution, the optimal expected waste for a random list of n items must be either $\Theta (n)$, $\Theta (n^{1/2} )$, or O(1), depending on whether certain"perfect" packings exist. The perfect packing theorem needed for the U{j,k} distributions is an intriguing result of independent combinatorial interest, and its proof is a cornerstone of the paper.

We consider N processors communicating unidirectionally over a closed transmission channel, or ring. Each message is assembled into a fixed-length packet. Packets to be sent are generated at random times by the processors, and the transit times spent by packets on the ring are also random. Packets being forwarded, i.e., packets already on the ring, have priority over waiting packets. The objective of this paper is to analyze packet waiting times under a greedy policy within a discrete Markov model that retains the overall structure of a practical system but is simple enough so that explicit results can be proved. Independent, identical Bernoulli processes model message generation at the processors, and independently and identically distributed (i.i.d.) geometric random variables model the transit times. Our emphasis is on asymptotic behavior for large ring sizes, N, when the respective rate parameters have the scaling $\lambda /N$ and $\mu /N$. Our main result shows that, if the traffic intensity is fixed at $\rho = \lambda / \mu < 1$, then as $N \to \infty$ the expected time a message waits to be put on the ring is bounded by a constant. This result verifies that the expected waiting time under the greedy policy is within a constant factor of that under an optimal policy.

Many complex proesses can be modeled by (countably) infinite, multidimensional Markov chains. Unfortunately, cnrnmt theoretical techniques for analyzing infinite Markov chains are for the most part limited to three or fewer dimensions. In this paper we propose a computer-aided approach to the analy-sis of higher-dimensional domains, using several open problems about the average-case behavior of the Best Fit bin packing algo-rithm as case studies. We show how to use dynamic and liiear programming to construct potential functions thal when applied to suitably modified multi-step versions of our original Markov chain, yield drifts that are bounded away fmm O. This enables us to completely classify the expected behavior of Best Fit under dis-crete uniform distributions U{J, K) when K is small. (Under U { J, K}, the allowed item sizes are i/K, 1 S i S J, with all J pos-sibilities equally likely.) In addition, we can answer yes to the long-standing open question of whether there exist distributions of this form for which Best Fit yields linearly-growing waste. The proof of the latter theorem relies on a 24-hour computation, and although its validity does not depend on the linear progra-mmingpackage we used, it does tely on the correctness of our dynamic progr smming code and of our computer’s implementation of the IEEE floating point standard.

We consider the classical scheduling problem in which a given collection of tasks with lengths tl.t2,..., t,, are to be run on two processors, subject to specified precedence constraints among the tasks, so as to minimize the completion time of the last-finishing task, the so-called makespan of the schedule.A schedule is said to be nonpreemptive if each task, once started, is run continuously until its completion t,time units later, whereas a preemptive schedule allows the running of a task to be temporarily suspended and resumed at a later time, that is, run in noncontiguous pieces whose lengths merely sum to the task length t,.A long-standing conjecture is that, for any set of tasks and precedence constraints among them, the least makcspan achievable by a nonpreemptive schedule is no more than 4/3 the least makespan achievable when preemptions are allowed.In this paper, we prove this conjecture.

The nonpreemptive scheduling of $n \geqslant 1$ stochastic jobs is considered to minimize the expected number of parallel machines needed to meet given waiting-time constraints. The number of machines available is unlimited. The running times of the jobs are denoted $T_1 , \ldots ,T_n $ and are taken to be independent samples of an exponentially distributed random variable T with mean 1. Job waiting times are to be bounded stochastically by a nonnegative random variable W, independent of $T_1 , \ldots ,T_n $. At time zero, a timer is started with an initial value W, and job scheduling begins. When the timer expires, all jobs still waiting for a machine are assigned to available machines. Only the distributions of W and the job durations $T_1 , \ldots ,T_n $ are known to the scheduler in advance. A scheduling policy is defined which is proven to be optimal when W has an exponential distribution, and is asymptotically optimal as $n \to \infty $, when W is a constant (hard-deadline). In the exponential case, an explicit formula for the cost function is derived. The uniqueness question is also resolved. The paper concludes with a partial analysis of the general hard-deadline problem, which leads to a policy that we think is optimal. A proof of optimality, however, remains an open problem.

This paper provides an examination of an abstract moving-server system that models several computer applications, including software debugging and accessing compressed data. In this model, the server moves on the unit interval $[0,1]$, serving requests where they are encountered. The locations of successive requests are not known in advance, but they are known to be independent samples from a given distribution F on $[0,1]$. Before serving a request, the server must be moved to a reset point to the left of the request. There is a choice of two reset points, one fixed at 0 and one, called the checkpoint, that can be moved in the course of serving requests. The cost of serving a request is proportional to the distance moved to the request from the chosen reset point. This paper formulates a stochastic optimization problem whose solution, for a wide class of distributions F, yields a policy for deciding the successive locations of the checkpoint so as to minimize the expected total cost of serving a sequence of requests. Results for both finite and infinite-horizon variations of the problem are presented, along with the properties required of the distribution F.

Messages arrive randomly at one end of a slotted communication channel. They are assigned to (packed in) packets of fixed duration which queue up for transmission in first-in-first-out order; the packets are sent one per time slot. In a stochastic setting, where message durations are also random, we analyze a model which yields statistics on message delays and the number of waiting messages, assuming that the assignment protocol is the well-known next-fit rule of one-dimensional bin packing. A stability condition is obtained as a function of general discrete message-length distributions. As a by-product, we contribute a new result to the literature on the probabilistic analysis of the static next-fit bin-packing rule, viz. the limiting expected bin occupancy for general discrete distributions. Specializations of the results to constant message lengths and to uniform message-length distributions are worked out in detail.>

A job is to be run on a machine subject to random failures. Failures are not self-evident. They must be detected by explicit tests, or checks. Checks detect failures to avoid wasting time working with a defective machine. After each successful check one has the option of saving the work just completed. Then, when failures occur, only the work done since the last save must be repeated. Effective use of checks and saves requires a compromise, since these procedures are themselves time-consuming. Scheduling saves alone, when failures are evident as soon as they occur, is often called checkpointing. The novelty of the model studied here stems from not assuming that failures are self-evident. This compounds the usual checkpointing problem by requiring schedules of failure checks as well as saves. This paper gives schedules of checks and saves that minimize the expected total time required to complete a given job. The most general failure mechanism considered is a renewal process. The Poisson process receives special emphasis, as it leads to the simplest results. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Abstract Finding short paths through mazes of rectangles has applications in VLSI wire‐routing and robotics. This paper introduces and analyzes heuristic algorithms for finding short paths, under the assumption that the algorithms have no information about rectangles not already encountered along a path. Tight worst‐case bounds are derived for the ratio of the length of these algorithms' paths to the lengths of shortest paths. A model of random mazes is defined for testing the typical or average‐case behavior of algorithms. Although specially designed mazes can force the heuristic algorithms to give long paths, simulations and analysis show that the better heuristics usually give paths nearly as short as possible.

We consider the average case behavior of onedmensional bin paekmg algorithms in the case where bins have unit capacity and item sizes are chosen according to the ' 'dficrete uniform" distribution U~; k), 1 s j < k, where each item size in the set {llk,21k,..., ji k) has probability 1/j of beiig chosen.Note that for fixed j,k the distributions U{?nj;mk]' approach the continuous distribution U(O, jlk] as m A W, where in U(O, jl k] the item sizes are chosen uniformly horn the half-open interval (O,jik].In this paper, we show that average case behavior can differ substantially under the two types of distributions.We show that for all j, k, j < k-1, there exist on-line algorithms that have constant expected waste under U~; k], whereas no on-line algorithm can have less than C2(n1'2) waste under U(O, U] for any u s 1. Conmariwise, although the First Fit Decreasing (off-line) algorithm has constant expected waste under U(O, u] for all u < 1/2,

Article Free Access Share on Proof of the 4/3 conjecture for preemptive vs. nonpreemptive two-processor scheduling Authors: E. G. Coffman AT&T Bell Labs., Murray Hill, NJ AT&T Bell Labs., Murray Hill, NJView Profile , M. R. Garey AT&T Bell Labs., Murray Hill, NJ AT&T Bell Labs., Murray Hill, NJView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 241–248https://doi.org/10.1145/103418.103447Online:03 January 1991Publication History 6citation231DownloadsMetricsTotal Citations6Total Downloads231Last 12 Months6Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The stochastic upright matching problem has had many important applications, most notably in statistics and the average-case analysis of algorithms. A problem instance is a set of n points chosen uniformly at random in the unit square. The points are labeled with signs; the signs are chosen independently and each is equally likely to be a plus or minus. An up-right matching of S is a matching of minus points to plus points such that if $( x,y )$ is a minus point matched to the plus point $( x',y' )$, then $x\leqq x'$ and $y\leqq y'$. The problem is to estimate the expected number of points left unmatched in a maximum upright matching of S. It is well known that if $U_n $ denotes the number of unmatched points, then $E[ U_n ] = \Theta ( \sqrt{n} \log^{3/4} n )$. Existing proofs of the upper bound $O( \sqrt{n} \log^{3/4} n )$ are quite long and difficult to follow. This paper presents a much simpler and more compact proof. A distinctive feature of the new proof is the use of Fourier expansions.

A stochastic model of buffering in a data communication system is considered, with source and sink transmission parameters depending on the number of active sources. For models in this control setting the authors analyze an effective numerical method for evaluating the equilibrium distribution of buffer content. The theoretical basis of the method is established first. Then, it is shown that the method has the same complexity, in terms of the total number of sources, as known analytical methods for the model with constant parameters. Asymptotics for tail probabilities at high buffer levels and under heavy load are also derived, and the complexity of their computation is compared with that of evaluating explicit formulas. In comparison to earlier results this approach reduces the complexity of computing the probability of overflow and its asymptotic estimates. The speed-up stems from the application of interpolation schemes.>

This paper gives a probabilistic performance analysis of simple algorithms for packing lists $L_n $, of n squares into a strip or a set of bins. It is assumed that the square sizes are drawn independently from the uniform distribution on,$[0,1]$. The strip-packing problem is to pack the squares into a strip of width 1 so as to minimize the height of the packing. Let ${\operatorname{OPT}}(L_n)$ denote the height of an optimal strip packing for list $L_n $. A simple $O(n\log n)$ approximation algorithm, called Algorithm A, is described and it is proven that the height $A(L_n )$ of a packing of list $L_n $ satisfies $A(L_n ) - {\operatorname{OPT}}(L_n ) \leqq \tfrac{1}{4}$ with probability $1 - O(e^{ - c_0 n} )$ for a positive constant $c_0 $. It is also shown that $E[{\operatorname{OPT}}(L_n )] = 3n/8 + \Theta (n^{{1 / 3}} )$. The bin-packing problem is to pack the squares into square bins of size 1 so as to minimize the number of bins. Let ${\operatorname{OPT}}_B (L_n )$ denote the number of bins in an optimal packing of list $L_n $. The authors present another $O(n\log n)$ approximation algorithm and show that the number of bins it needs to pack a list $L_n $ is precisely ${\operatorname{OPT}}_B (L_n )$ with probability $1 - O(e^{ - c_1 n} )$ for a positive constant $c_1 $. Finally, it is shown that $E[{\operatorname{OPT}}_B (L_n )] = {n / 2} + \Theta (1)$. These bounds for packing squares into strips and bins are much tighter than GTthose that have been obtained for packing rectangles.

The authors analyze a model of a movable-head disk system with two read/write heads maintained a fixed distance d apart on each arm. Successive request-addresses are assumed to be independent random variables, uniformly distributed over the set of cylinders. The purpose of the analysis is to find that value of d which minimizes the expected seek time per request, assuming that seek time varies linearly with the distance z traveled by the heads. The authors extend an earlier analysis of this model to more general seek-time characteristics which take into account nonlinear acceleration effects. Detailed results, combining both analysis and simulation experiments, are presented for seek times linear in z/sup alpha /, 0>

Two mathematical models dealing with optimal placement of directories on disk devices are analyzed. Storage addresses on the disk are approximated by points in the interval [0, 1]. Requests for information on the disk are represented by a sequence of file names. To process a request, a read-write head is first moved to a directory kept on the disk that specifies the address of the file, and then a head is moved to the specified address. The addresses are assumed to be independent and uniform on [0,1]. In the first model we consider a system of two heads separated by a fixed distance d and a directory situated at 0 ≤ x ≤ 1. In the second model we consider a system consisting of one head and n ≥ 2 directories at 0 ≤ x 1 < x 2 < … < x n ≤ 1. For both models we study the problem of finding those values of the parameters that minimize the expected head motion to process a request in statistical equilibrium.

A network is defined as an undirected graph and a routing which consists of a collection of simple paths connecting every pair of vertices in the graph. The forwarding index of a network is the maximum number of paths passing through any vertex in the graph. Thus it corresponds to the maximum amount of forwarding done by any node in a communication network with a fixed routing. For a given number of vertices, each having a given degree constraint, we consider the problem of finding networks that minimize the forwarding index. Forwarding indexes are calculated' for cube networks and generalized de Bruijn networks. General bounds are derived which show that de Bruijn networks are asymptotically optimal. Finally, efficient techniques for building large networks with small forwarding indexes out of given component networks are presented and analyzed.

In a flexible manufacturing system stations are arranged along a common conveyor that brings items for processing to the stations and also carries away the processed items. At each station specialized robots automatically load and unload items on and off the conveyor. We examine here a single station in such a system. A new kind of queueing problem arises, with input-output dependencies that result because the same conveyor transports items both to and from the station. The paper analyzes two models of a station. Model 1 has one robot that cannot return a processed item to the conveyor while unloading a new item for processing. Model 2 has two robots to allow simultaneous loading and unloading of the conveyor. A principal goal of the analysis is the proper choice of the distance separating the two points at which items leave and rejoin the conveyor.

The design and analysis of algorithms for on-line dynamic storage allocation has been a fundamental problem area in computer science for many years.In this paper we study the stochastic behavior of dynamic allocation algorithms under the natural assumption that files enter and leave the system according to a Poisson process.In particular, we prove that for any dynamic allocation algorithm and any distribution of file sizes, the expected wasted space (or fragmentation) in the system at any time is ~ (-v~'x/loglogN), where N is the expected number of items (or used space) in the system.This result is known to be tight in the special case when all files have the same size.More importantly, we also construct a dynamic allocation algorithm which for any distribution of file sizes wastes only O (x/~'log 3/4 N) space with very high probability.This bound is also shown to be tight for a wide variety of file-size distributions, including for example the uniform and normal distributions.

A server moves at a constant rate around a closed tour, stopping to perform services wherever requests are encountered. Requests appear according to a Poisson process at locations independently and uniformly distributed over the tour, and the service times are all taken to be one unit. Discrete versions of this model have applications ranging from machine repair to computer/communication polling systems. The distributions of the number served in a cycle and the number of waiting requests and their waiting times are calculated, and defections are studied. Because our continuous model is simpler than the discrete models, more easily interpreted formulas and some results that have yet to be obtained for discrete models are acquired.

In dynamic storage allocation, successive allocation and freeing of blocks normally leads to fragmentation of storage.When a new block is to.beallocated, fragmentation may prevent any single region of available storage from being large enough for the new block, even though the total amount of available space is sufftcient.When such a conflict arises, dynamic storage allocation systems typically require time-consuming garbage collection or they simply break down.This paper investigates strategies for maintaining storage that allow allocation of blocks to proceed in spite of fragmentation conflicts, at the cost of moving some blocks already allocated are investigated.Such a scheme is reasonable only if it can be guaranteed that the cost of moving blocks never becomes too large relative to the size of the.block to be allocated.Two such schemes are described.They are similar to the buddy system in that they always align the left end of a block of size n at a position that is a multiple of 2"005"'.The schemes differ in the criterion for choosing an interval to free up when no interval of the right size is empty: the Not Full (NF) scheme chooses an interval that is not full, while the Not Too Full (NTF) scheme chooses an interval that is at most as full as all of memory.Tight worst-case bounds are obtained for these schemes as a function of the proportion of memory tilled.The results show that the worst-case cost for NF, the simpler of the two schemes, can be much worse than that for NTF when memory is not too full.However, simulations suggest that the average cost may be much less than the worst-case.cost.

We consider a problem of scheduling file transfers in a network so as to minimize overall finishing time. Although the general problem is NP-complete, we identify polynomial time solvable special cases and derive good performance bounds for several natural approximation algorithms, assuming the existence of a central controller. We also show how these bounds can be maintained in a distributed regime.

We study a model of dynamic storage allocation in which requests for single units of memory arrive in a Poisson stream at rate $\lambda $ and are accommodated by the first available location found in a linear scan of memory. Immediately after this first-fit assignment, an occupied location commences an exponential delay with rate parameter $\mu $, after which the location again becomes available. The set of occupied locations (identified by their numbers) at time t forms a random subset $S_t $ of $\{ 1,2, \cdots \}$. The extent of the fragmentation in $S_t $, i.e. the alternating holes and occupied regions of memory, is measured by $\max (S_t ) - |S_t |$. In equilibrium, the number of occupied locations, $|S|$, is known to be Poisson distributed with mean $\rho = \lambda/ \mu$. We obtain an explicit formula for the stationary distribution of max $(S)$, the last occupied location, and by independent arguments we show that $(E\max (S) - E|S|) /E|S| \to 0$ as the traffic intensity $\rho \to \infty $. Moreover, we verify numerically that for any $\rho $ the expected number of wasted locations in equilibrium is never more than $\frac{1}{3}$ the expected number of occupied locations. Our model applies to studies of fragmentation in paged computer systems, and to containerization problems in industrial storage applications. Finally, our model can be regarded as a simple concrete model of interacting particles [Adv. Math., 5 (1970), pp. 246–290].

Suppose requests to store files arrive at a storage facility in a Poisson stream at rate 1. Each file is allocated storage space on arrival and each remains independently for an exponential time with mean l/p. The lengths of the files are assumed to be independent with common distribution F. Each file is placed in the lowest addressed contiguous sequence of locations large enough to accommodate the fre at its arrival time. This is the so-called first-fit storage discipline. We conjecture that first-fit is asymptotically optimal in the sense that the ratio of expected empty space to expected occupied space tends to zero as p → 0, i.e., as the occupied space tends to ∞. This conjecture seems very hard to prove, but it has been proved for constant file lengths [1], i.e., when F degenerates. We are unable to prove the conjecture but give a graphic display of the results of a Monte Carlo simulation which makes it very convincing.

A mathematical model of computer disk storage devices having two movable read/write heads is studied.Storage addresses are approximated by points in the continuous interval [0, 1], and requests for information on the disk are processed first-come-first-served.We assume that the disk heads are maintained a fixed distance d apart; that is, in processing a request, both heads are moved the same distance in the same direction.Assuming that successive requested locations are independently and uniformly distributed over [0, 1], we calculate the invariant measure of a Markov chain representing successive head positions under the nearer-server rule: Requests in [0, a t] are processed by the left head, those in [1 -d, 1] by the right head, and those in [d, 1 -d] by the nearer of the two heads.Our major objective is the equilibrium expected distance E(d) that the heads are moved in processing a request.For the problem of designing the separation distance d, we show that E (0.44657) ffi 0.16059 ffi mindE(d).Thus, a basic insight of the analysis is that a system with two heads performs more than twice as well as a system with a single head.The results are compared with those for other two-head disk systems.Finally, numerical results are presented that demonstrate that the nearer-server rule is very nearly optimal under the fixed head-separation constraint.

Among the more difficult combinatorial problems in computer science are those occurring in dynamic storage allocation. We investigate the handling of memory conflicts occurring when a request for a block of storage is received, but no one region of available space is large enough due to fragmentation of storage. For arbitrary block sizes, we show that it is NP-hard to find a minimal cost reallocation of memory that will allow insertion of a new block. Therefore, we focus on the “bay restaurant” model studied by Robson, in which requests are for only one or two units of memory. We give a polynomial time algorithm for minimal cost insertions of batches of blocks and for minimal cost memory compaction. We show that the cost of inserting p blocks one at a time, i.e. on-line, is no worse than \[ \left\lfloor 2\left( \frac{3}{2} \right)^{\lceil \log p \rceil } - 1 \right\rfloor \] times the minimal cost of inserting the blocks in one batch, i.e. off-line. For p a power of two, this bound is tight.

We consider a problem of scheduling file transfers in a network so as to minimize overall finishing time, which we formalize as a problem of scheduling the edges of a weighted multigraph. Although the general problem is NP-complete, we identify polynomial time solvable special eases and derive good performance bounds for several natural approximation algorithms. The above results assume the existence of a central controller, but we also show how the approximation algorithms, along with their performance guarantees, can be adapted to a distributed regime.

In this paper we focus on the storage resource. A basic model of the space time requirements of jobs in a computer system is described, and a number of its variations analyzed by means of diffusion approxmiations. Subject to the usual heavy traffic assumptions, the result of this analysis enable one to quantify the effects of limitations on both storage capacity and processing rates.

The evaluation of anthmeuc expressions on both register-oriented and stack-oriented machines can be stud~ed using the same model because registers can be treated as a stack during the evaluation of express~on trees, without loss m code efficiency The machine model in this paper has a hardware stack m which all computatmns take place.Reg~ster-regmer and regmer-memory instructions are modeled by considering four possible instrucuons for each binary operator, depending on whether one or two operands are taken from the stack and on whether the left or the right operand ~s on top of the stack.There is a cost assocJated wtth each operation code, as well as costs for accessing a value in a register or in memory.The mtmmum cost of computing an expression tree ~s used to compare machines.The comparisons fall into two classes (1) By keeping the instruction set fixed, the effect of increasing the number of registers is studied.(2) Various machines are compared with a machine that has all four kinds of operation instructmns and an arbitrarily deep stack.As part of the framework that allows the comparisons to be performed, a parametenzed algonthm for determining the number of stores that must occur in an optimal computation is developed This algorithm forms the basis of an opttmal code generation algorithm.

Motivated by potential applications to computer storage allocation, we generalize the classical one-dimensional bin packing model to include dynamic arrivals and departures of items over time. Within this setting, we prove close upper and lower bounds on the worst-case performance of the commonly used First Fit packing algorithm, and, using adversary-type arguments, we show that no on-line packing algorithm can satisfy a substantially better performance bound than that for First Fit.

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.

We consider the effect on system performance of the distribution of a data base in the form of multiple copies at distinct sites. The purpose of our analysis is to determine the gain in READ throughput that can be obtained in the presence of consistency preserving algorithms that have to be implemented when UPDATE operations are carried out on each copy. We show that READ throughput diminishes if the number of copies exceeds an optimal value. The theoretical model we develop is applied to a system in which consistency is preserved through the use of Ellis' ring algorithm.

We study the comparison between an m-processor (multiprocessor) system and a single-processor system whose processor is m times as fast as any in the multiprocessor system. The expected superiority of the single-processor system is measured in terms of mean and maximum flow times, using both combinatorial and probabilistic models.

We consider problems of packing an arbitrary collection of rectangular pieces into an open-ended, rectangular bin so as to minimize the height achieved by any piece. This problem has numerous applications in operations research and studies of computer operation. We devise efficient approximation algorithms, study their limitations, and derive worst-case bounds on the performance of the packings they produce.

We analyze several “level-oriented” algorithms for packing rectangles into a unit-width, infinite-height bin so as to minimize the total height of the packing. For the three algorithms we discuss, we show that the ratio of the height obtained by the algorithm to the optimal height is asymptotically bounded, respectively, by 2, 1.7, and 1.5. The latter two improve substantially over the performance bounds for previously proposed algorithms. In addition, we give more refined bounds for special cases in which the widths of the given rectangles are restricted and in which only squares are to be packed.

An $NP$-complete bin-packing problem is studied in which the objective is to maximize the number of pieces packed into a fixed set of equal capacity bins. Applications to processor and storage allocation in computer systems are discussed, and an efficient approximation algorithm is defined and studied. The main results are bounds on the complexity of the algorithm and on its performance.

We consider one of the basic, well-studied problems of scheduling theory, that of nonpreemptively scheduling n independent tasks on m identical, parallel processors with the objective of minimizing the “makespan,” i.e., the total timespan required to process all the given tasks. Because this problem is $NP$-complete and apparently intractable in general, much effort has been directed toward devising fast algorithms which find near-optimal schedules. The well-known LPT (Largest Processing Time first) algorithm always finds a schedule having makespan within $4/3 = 1.333 \cdots $ of the minimum possible makespan, and this is the best such bound satisfied by any previously published fast algorithm. We describe a comparably fast algorithm, based on techniques from “bin-packing,” which we prove satisfies a bound of 1.220. On the basis of exact upper bounds determined for each $m \leqq 7$, we conjecture that the best possible general bound for our algorithm is actually $20/17 = 1.176 \cdots $.

A combinatorial problem related to storage allocation is analyzed. The problem falls into a class of NP-complete, one-dimensional bin-packing problems. We propose an iterative approximation algorithm and show that it is superior to an earlier heuristic presented for this problem. The bulk of the paper is devoted to the proof of a worst-case performance bound.

In this paper we shall generalize Graham's result so as to include a parameter characterizing the number of tasks assigned to processors by the LPT rule. The new result will show that the worst-case performance bound for LPT sequencing approaches unity approximately as 1+1/k, where k is the least number of tasks on any processor, or where k is the number of tasks on a processor whose last task terminates the schedule. Thus, we shall have a result very similar to the parameterized bounds for bin-packing heuristics [JDUGG]. We shall also obtain out of the analysis an alternate proof of Graham's result.

This paper examines the problem of distributing a set of equal-size records among the sectors of a drum-like storage device in order to exploit known access frequencies and reduce the average access time. A simple catenated search model is defined for which, the problem is shown to be NP-complete. Heuristics are then defined and analyzed in terms of worst-case bounds. It is shown that easily implemented highest-access-frequency-first assignment rules provide an average access time very close to optimal.

No abstract available.

In this paper we study the problem of designing scheduling strategies when the demand on the system is known and waiting time requirements are pre-specified. This important synthesis problem has received little attention in the literature, and contrasts with the common analytical approach to the study of computer service systems. This latter approach contributes only in-directly to the problem of finding satisfactory scheduling rules when the desired (or required) response-time performance is specifiable in advance.

Considerable effort has been invested in devising and analyzing sequencing rules for multiprogrammed or time-shared systems. A much studied discipline of this kind is the so-called system with feedback to lower priority queues. This discipline contains many parameters, in general, which must be fixed in order to achieve the desired waiting-time performance of the discipline. In this paper the problem of synthesizing a system of the above type is solved, by setting parameter values so that prespecified waiting time criteria are satisfied, assuming Poisson arrival and general service time parameters are known.

A simple mathematical model of (time-varying), program demand for main memory is developed. The model is based on the use of the immigration-death process, and is particularly suited to modeling the total demand of several programs. The goal is to study the behavior of the system under various schemes of dynamically allocating main memory among the programs. In particular, given some sort of working-set storage management we study what margin of free space should be reserved when programs are moved in and out of main memory, so that the frequency of overflow-underflow events is kept reasonably low, while at the same time maintaining a reasonably high degree of multiprogrammig.

In this paper we study the problem of scheduling a set of independent tasks on m ≥ 1 processors to minimize the mean finishing-time (mean time in system). The importance of the mean finishing-time criterion is that its minimization tends to reduce the mean number of unfinished tasks in the system. In the paper we give a reduction of our scheduling problem to a transportation problem and thereby extend the class of known non enumerative scheduling algorithms [1]. Next we show that the inclusion of weights (weighted mean finishing-time) complicates the problem and speculate that there may be no non enumerative algorithm for this case. For the special case of identical processors we study the maximum finishing-time properties of schedules which are optimal with respect to mean finishing-time. Finally we give a scheduling algorithm having desirable properties with respect to both maximum finishing-time and mean finishing-time.

A combinatorial problem arising from the analysis of a model of interleaved memory systems is studied. The performance measure whose calculation defines this problem is based on the distribution of the number of modules in operation during a memory cycle, assuming saturated demand and an arbitrary but fixed number of modules. In general terms the problem is as follows. Suppose we have a Markov chain of n states numbered 0, 1, ···, n - 1. For each i assume that the one-step transition probability from state i to state ( i + 1) mod n is given by the parameter α and from state i to any other state is β = (1 - α )/( n - 1). Given an initial state, the problem is to find the expected number of states through which the system passes before returning to a state previously entered. The principal result of the paper is a recursive procedure for computing this expected number of states. The complexity of the procedure is seen to be small enough to enable practical numerical studies of interleaved memory systems.

A number of recent studies have examined techniques for sequencing disk accesses to minimize or reduce seek times. The principal methods proposed have been called scanning policies. In this paper we formulate and analyze simple mathematical models of head motion in disk systems in which two different scanning policies are implemented. Expressions for response times are derived, and the properties they imply are discussed.

This paper appears in the March, 1972, issue of the Communications of the ACM. Its abstract is reproduced below.Both fixed and dynamic storage partitioning procedures are examined for use in multiprogramming systems. The storage requirement of programs is modeled as a stationary Gaussian process. Experiments justifying this model are described. By means of this model dynamic storage partitioning is shown to provide substantial increases in storage utilization and operating efficiency over fixed partitioning.

Past studies of the performance of interleaved memory systems are extended in this note by adopting a more general model. The model assumes a system of N memory modules, each of which is made up of b submodules. Successive memory addresses are assigned to sequential submodules, modulo Nb. For increased effective memory bandwidth a so-called conflict buffer of size L + 1 is assumed to exist for storing address conflicts.

A basic probability model that has arisen in the study of time-shared or multiprogrammed systems is the so-called processor-sharing model.Ill this model it is assumed that the processor is shared simultaneously by each unit in the system (e.g.job or program in comput er systems, or message in communication systems).In particular, if there are n units in the system, then any given unit is being processed at a rate which is (1/n)-th the rate at which it would be processed if it had the system to itself.We make the assumptions of a Poisson arrival process and exponential service times and then derive an expression for the Laplace transform of the waiting time distribution of an arriving unit conditioned on the service it requires and the number it finds in the system oil arrival.From this result we obtain the first two moments of the waiting times, the Laplace transform of the equilibrium waiting time distribution, and the first two moments of this latter distribution.The paper concludes with a discussion of the results, especially as they compare with similar results for the first-come-first-served discipline.

The use of multiprocessor systems consisting of identical and autonomous processors is a promising approach to the practical solution of problems arising in real-time applications and large compute-bound problems in general.However, finding techniques for obtaining efficient solutions to the related multiprocessor scheduling problems is a little-understood problem.The authors study the problem of scheduling a set of tasks whose operational precedence structure is representable as an acyclic directed graph.In scheduling tasks it is assumed that preemptions are allowed.The major results consist of the statement and proof of an efficient algorithm for finding the minimal-length preemptive schedule for tree-structured computations.

Properly scheduling the usage of input output devices is an important aspect of the design of modern multiprogramming systems featuring a paged environment. In this paper magnetic drums in the role of auxiliary memories are studied in the context of these systems. It is the nature of the drum, its usage by the system, and the organization of information on the drum are discussed in the light of current system designs. Mathematical models are then defined such that two extremes in scheduling disciplines are represented in a system in which page requests are assumed to arrive singly and at random. The analysis leads to results for a measure of drum utilization, a generating function for the queue length probabilities in equilibrium, the mean queue length, and the mean waiting time. Finally, the significance of the results is discussed along with some examples.

No abstract available.

In computer operating systems where background jobs must occasionally be preempted in order to run high priority jobs, it is generally the case that efficient operation and rapid response to the high priority jobs are conflicting objectives. In this short paper a preemption scheme in which a delay is introduced is shown to provide the designer with the ability to trade off these two performance measures to any desired degree. A mathematical model is developed and results are derived for the mean high priority waiting time and a measure of operating efficiency. The paper concludes with a discussion of examples designed to illustrate how the above performance measures interact as a function of system parameters.

One of the important potentials of multiprocessor systems is the ability to speed the completion of a computation by concurrently processing independent portions of the job. In this paper we consider the static scheduling of computations for a system containing two indentical processors. The object is to complete the computation in the minimum amount of time. A computation is assumed to be specified as a partially ordered set of tasks and the execution time for each task. A solution for the two-machine case with preemptive scheduling is presented.

The necessity for swapping in the operation of modern time-sharing systems constitutes the major reason for the latter's inefficiency compared to batch-processing systems. Time-sharing algorithms are discussed which are designed primarily for the reduction of swapping without intolerable changes in the waiting time distributions. A particular class of such algorithms in which conventional procedures are modified by making the quantum allocation dependent on input activity is given a more detailed treatment. In particular, queueing models corresponding to these algorithms are devised and then analyzed for the purpose of obtaining the mean waiting times conditioned on the service required. These results are then compared to those obtained for the conventional models and the comparison subsequently measured against the swapping requirements of the two classes of algorithms.

Time-shared processing systems (e.g. communication or computer systems) are studied by considering priority disciplines operating in a stochastic queueing environment. Results are obtained for the average time spent in the system, conditioned on the length of required service (e.g. message lenght or number of computations). No chage is made for swap time, and the results hold only for Markov assumptions for the arrival and service processes. Two distinct feedback models with a single quantum-controlled service are considered. The first is a round-robin (RR) system in which the service facility processes each customer for a maximum of q sec. If the customer's service is completed during this quantum, he leaves the system; otherwise he returns to the end of the queue to await another quantum of service. The second is a feedback (FB N ) system with N queues in which a new arrival joins the tail of the first queue. The server gives service to a customer from the n th queue only if all lower numbered queues are empty. When taken from the n th queue, a customer is given q sec of service. If this completes his processing requirement he leaves the system; otherwise he joins the tail of the ( n + 1)-st queue ( n = 1, 2, · · ·, N - 1). The limiting case of N → ∞ is also treated. Both models are therefore quantum-controlled, and involve feedback to the tail of some queue, thus providing rapid service for customers with short service-time requirements. The interesting limiting case in which q → 0 (a “processor-shared” model) is also examined. Comparison is made with the first-come-first-served system and also the shortest-job-first discipline. Finally the FB ∞ system is generalized to include (priority) inputs at each of the queues in the system.

A simple probability model is defined that represents modular memory systems under saturation demand for storage. An analysis of the model based on the theory of finite Markov chains leads to results that demonstrate the effects of changes in loading times and the number of modules on system performance.

Abstract—A particular method for storage of first-in-first-out queues in random access memory is analyzed. The storage scheme gives minimum overhead costs at the expense of storage utilization. The resulting queue is analyzed as a Markov chain and the stationary, joint probability distribution is obtained for the queue length and the relative location of the head of the queue. Expressions for the mean length and the locations of the head and the tail of the queue are also derived.

Abstract—A probability model of queue storage allocation problems is devised and an analysis is provided based on the theory of random walks. Two types of queue storage allocation are discussed and analyzed, after which examples are given to illustrate their relative advantages and disadvantages.

This paper reports initial results from an empirical study directed at the measurement of program operating behavior in those multiprogramming systems in which programs are organized into fixed length pages. The data collected from the interpretive execution of a number of paged programs is used to describe the frequency of page faults; i.e. the frequency of those instants at which an executing program requires a page of data or instructions not in main (core) memory. These data are used also for the evaluation of two page replacement algorithms and for assessing the effects on performance of changes in the amount of storage allocated to executing programs.