June 1973 - Vol. 16 No. 6

Although sometimes thought of as only a component of time-sharing operation, multiprogramming can involve broader questions of resource allocation, since fairness is not required to meet a response criterion. In a multiprogrammed system, it may serve maximal resource use to be unfair, for example by holding an input/output channel idle for a program while it completes a small amount of processor usage, enabling further use of the channel. Several applications of this principle are given, and it is suggested that a multiprogramming executive might dynamically adjust its allocation algorithms to gain efficiency. Allocation of resources is closely connected to accounting for those resources, raising the problems of repeatability, minimal uncharged overhead, and relative weighting of charges for dependent resources. Since weightings may depend on allocation algorithms, these are not arbitrary accounting parameters. Often the only repeatable accounting is one which omits an extensive overhead; this overhead can be multiple-charged to all programs which benefit from it, so that in the worst case the overhead will be paid, and should multiprogramming prove efficient, overcharges will result. Multiprogramming turns on allocation of the memory resource essential to control of other resources. The general suggestions for allocation and accounting are applied to this question, and some details provided for the case of a monitor which controls a virtual-memory machine.

A paged virtual memory system using a finite number of page sizes is considered. Two algorithms for assigning pages to segments are discussed. Both of these algorithms are simple to implement. The problem of choosing the page sizes to minimize the expected value of total wasted space in internal fragmentation and in a page table, per segment, is then solved for a probability density function of segment size which may be expressed as a convex combination of Erlang densities.

Implementations of the “Lock-Unlock” method of synchronizing processors in a multiprocessor system usually require uninterruptable, memory-pause type instructions. An interlock scheme called read-interlock, which does not require memory-pause instructions, has been developed for a dual DEC PDP-10 system with real-time requirements. The read-interlock method does require a special “read-interlock” instruction in the repertoire of the processors and a special “read-interlock” cycle in the repertoire of the memory modules. When a processor examines a “lock” (a memory location) with a read-interlock instruction, it will be interrupted if the lock was already set; examining a lock immediately sets it if it was not already set (this event sequence is a read-interlock cycle). Writing into a lock clears it. Having the processor interrupted upon encountering a set lock instead of branching is advantageous if the branch would have resulted in an effective interrupt.

For computer systems in which it is practical to determine the instantaneous drum position, a popular discipline for determining the sequence in which the records are to be accessed is the so-called shortest-latency-time-first, SLTF, discipline. When a collection of varying-length records is to be accessed from specified drum positions, it is known that the SLTF discipline does not necessarily minimize the drum latency time. However, we show that the total time to access the entire collection for any SLTF schedule is never as much as a drum revolution longer than a minimum latency schedule.