June 1972 - Vol. 15 No. 6

A simulation model of a time-sharing system with a finite noncontiguous store and an infinite auxiliary store is used to study the variation of system parameters such as store size, number of jobs allowed to execute simultaneously, job-scheduling algorithm, etc. The effects of these variations on a measure of system performance is used to ascertain which of the parameters controllable by the job-scheduling algorithm, including the scheduling itself, require optimization, and which of the parameters not normally controllable by the scheduling algorithm have a marked effect on system performance. System performance is based upon the mean cost of delay to all jobs processed. It is shown that significant improvements in the measure of system performance can be obtained by using variable time-slice techniques and by selecting the optimum round-robin cycle time. It appears that these features would benefit from optimization whereas other parameters controllable by the scheduling algorithm affect system performance in a predictable manner and would not benefit from optimization. Features not normally under the control of the scheduling algorithm can also have a marked effect on the measure of performance; in particular, supervisor overheads, the size of the store, and the speed of the CPU. A comparison is made between the results of the simulation model and two analytical equations for quantum-oriented nonpreemptive time-sharing systems. The comparison is found to be very favorable.

Many computer systems solve executable storage size problems for large programs by using overlays. However, it appears that no one overlay scheme contains a well-balanced combination of the most useful capabilities which are found in various existing techniques. A proposal is presented which utilizes several of the best capabilities from existing schemes and is complemented by several additional features, e.g. writable overlays. The writable overlay capability provides a virtual memory effect, although the programmer may still be required to design the overlay configuration. Since overlay structuring is a complex task, several tools (including a graphic display) are included in the proposal in order to aid the programmer in the design. The content of overlays is briefly discussed, and it is noted that many of the details of the final overlay configuration may be decided after the fact.

Various kinds of interference between communicating parallel processes have been examined by Dijkstra, Knuth, and others. Solutions have been given for the mutual exclusion problem and associated subproblems, in the form of parallel programs, and informal proofs of correctness have been given for these solutions. In this paper a system of parallel processes is regarded as a machine which proceeds from one state S (i.e. a collection of pertinent data values and process configurations) to a next state S′ in accordance with a transition rule S ⇒ S′. A set of such rules yields sequences of states, which dictate the system's behavior. The mutual exclusion problem and the associated subproblems are formulated as questions of inclusion between sets of states, or of the existence of certain sequences. A mechanical proof procedure is shown, which will either verify (prove the correctness of) or discredit (prove the incorrectness of) an attempted solution, with respect to any of the interference properties. It is shown how to calculate transition rules from the “partial rules” by which the individual processes operate. The formation of partial rules and the calculation of transition rules are both applicable to hardware processes as well as to software processes, and symmetry between processes is not required.

A new datatype, called a block, has been implemented for SNOBOL4. A block is a three-dimensional aggregate of characters in the form of a right parallelepiped, best thought of as a three-dimensional extension to a string. (The third dimension is used for overstriking.) Blocks may be printed, concatenated in any of three dimensions, and merged on the basis of program-defined connection points. Some blocks adapt in size and shape to their environment. Blocks and their operations are mainly used for composing printable output. A variety of graphical problems (including flowcharting, bargraphs, logic diagrams, mathematical-equation formation, and text justification and preparation) have been programmed on a printer in what appears to be an easy and natural way. In addition to these somewhat specialized applications, blocks appear to be a good general purpose device-independent output formation mechanism especially suitable for nonnumerical work. The concept of a block is largely language independent. That is, blocks require little in the way of specialized syntax and could readily be absorbed into the external structure of most programming languages.

A modified version of Bell's Boolean matrix method for the computation of linear precedence functions associated with a conflict-free matrix of precedence relations is given. This algorithm not only detects when the precedence functions do not exist, but also provides an indication of why they do not exist, so that corrective action can be taken if possible. Necessary and sufficient conditions for the existence of precedence functions are given. The use of Boolean matrices to prove the existence of precedence functions associated with classes of conflict-free grammars is illustrated through an example.