Abstract A three‐dimensional surface is a useful graphic representation of a two‐dimensional function which has been sampled on a regular grid. Shading the surface to simulate the effects of direct lighting makes visible small changes in the surface orientation, and enhances realism when the data represents a physical surface such as terrain. Shading interpolation calculations and surface patch generation techniques require the specification of a surface normal vector (or related slope information) at each sample point. These normal vectors are usually generated by averaging local data such as the normal vectors of the surfaces of a triangular mesh connecting the points. This paper describes a technique which uses Fourier filtering to generate normal vectors for two‐dimensional sampled data. Images and analysis of frequency spectra are included to show how this technique preserves detail which is lost using the averaging method. Performance figures show that this enhancement of detail in the final image can be achieved for only a small increase in computation time.

Two new algorithms for the distributed static resource allocation problem are presented. The first algorithm, which shows excellent average case behavior in simulation requires the maintenance of a global queue. The second, which needs only local communication, has polynomial waiting time and exhibits better average case behavior than the only other known polynomial time algorithm. Both algorithms have polynomial message complexity.>

This paper describes a general method for classifying and solving graphical mutual exclusion problems in a potentially automatic way. We show how to compile undirected graph representations into code for the associated processes. Starvation-prone solutions are based on Dijkstra's weak binary semaphores, while starvation-free solutions employ blocked-queue binary semaphores. Both solutions take the form of simulations of problem-space specifications which prescribe queue disciplines amongst blocked processes. The Hoare monitor is also considered since it is easily implemented in semaphores and can simulate any reasonable queue discipline. All proofs are presented in English with the minimum of formality in order to attract the greatest readership. Some of the necessarily more formal proofs underlying the results given here have been collected into a separate paper.

A graphical form of the mutual exclusion problem is considered in which each vertex represents a process and each edge represents a mutual exclusion constraint between the critical sections of the processes associated with its endpoints. An edge semaphore solution for mutual exclusion problems is defined, and those graphs which are edge solvable are characterized in terms of both a forbidden subgraph and a graph grammar. Finally, an efficient algorithm is given which generates the entry and exit sections for all processes in an edge-solvable problem.>

This paper discusses ways of reducing fragmentation ion in buddy systems. Although internal fragmentation may be estimated for any buddy system, external fragmentation cannot be determined theoretically. It is suggested here that mean external fragmentation for any buddy system is directly related to the height of the associated binary tree. Simulation studies with a new buddy system support this conjecture. Attempts at reducing internal fragmentation have, in the past, increased the tree height covering the range of request sizes and given rise to a commensurate increase in external fragmentation. A new buddy system is described which supports a large number of buddy sizes without requiring a large tree height. The new scheme is a modified form of the weighted buddy method, entitled the dual buddy system. It provides the same set of block sizes as the weighted scheme but has the same tree height as the binary buddy system. Simulation results show that mean external fragmentation is within four percent of that of the binary system and much lower than that of the weighted scheme. The new system has better overall storage utilization han others for uniform random request sizes.

This paper considers a simple scheme for dynamic storage allocation and shows that an analysis is possible through use of probability theory and the theory of renewal point processes. A placement scheme is considered which attempts to keep storage highly compact and obviates the need for time consuming scanning of free storage lists. An analysis of the storage loss due to fragmentation is presented together with the results of simulation experiments. The study indicates that, although the chosen scheme is amenable to theoretical analysis, it is inferior in performance to other well known schemes for dynamic storage allocation. A modification to the scheme is presented which gives utilization comparable with first fit but has lower free list searching overheads.

The frequency with which the first fit placement policy chooses the best possible hole size is investigated, together with the mean time taken to scan the free store list. These results are compared with the performance of an optimal placement policy first proposed by Campbell. The results indicate that first fit performs better than the optimal policy in both respects. This is due to the tendency of first fit to arrange the segments in size order.

The picture scanning attachment consists of a high resolution optical reflective sensor and associated amplification stages, in the form of a small probe which replaces the pen and pen holder in an incremental plotter and thus allows shaded pictures to be scanned for subsequent processing by digital computer.

This paper discusses an empirical study of a moving head disc system which has two heads on each calliper arm, separated by a fixed number of tracks. The behaviour of the system was examined by means of a simulation model operating with a uniform random request sequence. Two derivatives of the shortest seek time algorithm were investigated and for each the optimal head separation was found as a function of request queue length. It was found that when both heads are constrained to remain within the recording region, the optimal head separation approximates to half the distance between the innermost and outermost tracks. If either head is allowed to go outside the recording region, the optimal head separation was found to be a linearly reducing function of queue length. The former algorithm gives the best performance in minimising seek times.