A Class of FIFO Queues Arising in Computer Systems

We model secondary memory devices as single-server queuing systems. The non-random access to data within these devices is explicitly accounted for as “set-up” times. Requests are typed by the location of the desired record. No distinction is made between “read” and “write” requests. Each request is assumed to be satisfiable from one location on the device (e.g., a single directory search may result in a number of distinct requests). Requests arrive according to a homogeneous Poisson process. The types of successive requests form a first-order Markov chain, which is an approximation of reality. Alternative computational procedures and closed expressions are given for queue length, waiting times, and device utilization. We present some specializations to disks and drums. Only FIFO service is considered.