2.2.3. "Swapping," Dynamic Memory Allocation, and Pagination

With respect to Box 4 of Figure 2, there are shown questions of dynamic memory allocation, pagination, and "swapping". These questions obviously involve highly interdependent relationships with the system design problems that are involved in inputoutput for multiple user systems, in the servicing of client-submitted processing requests, and in the effective management of hierarchies of storage.2.35

We have seen in the case of queuing and scheduling of client interchanges with a multipleaccess system that, in accordance with various processing specifications, one client's program is typically run for a certain interval and then replaced by that of the next client to be served. When this occurs, it is necessary to preserve the status of the first client's program, to make way for the requirements of the next client, and, at a later time, to restore the displaced client's program to active operation. This is the process known as "swapping." 2.36

It is noted that the size of the programs and data sets being interchanged between active and inactive status will have considerable effect upon the efficiency of the swapping process.2.37 Improved efficiency may result if both programs and data sets are effectively modularized so that only those parts actually needed for the new operation are loaded into main memory.2.38 For another example, at Wayne State University, Abramowich (1967) considers special problems of central core storage allocation in the case of iterative processes where input data items once chosen are never again needed. At Project MAC, an "onion skin algorithm' is used so that only those parts of memory are dumped as are actually necessary to make room for the incoming program. (Scherr, 1965, p. 36). The problems of pagination relate in particular to the size of the blocks (or pages) of information that may be swapped between various levels of storage and to the management of transfers of such

siderations.2.38d

con

A pioneering approach to these problems in terms of both pagination and of dynamic interchange with respect to both program and data-set accessibility was provided in the system design of Atlas.2.39 It is noted, in addition, that "pioneering work on the concepts of segmentation and the use of predictive information to control storage allocation was done in connection with project ACSI-MATIC." (Randell and Kuehner, 1968, p. 299). Such problems, in general, continue to occupy the attention of system designers.2.40 "Since the effectiveness of a system increases as the service facilities are shared, ': a major goal of future research is a system with multiple access to a vast common structure of data and program procedures; the achievement of multiple access to the computer processors is but a necessary subgoal of this broader objective.' (Corbató, "System Requirements . . .", n.d., p. 3).

In addition, hierarchies of storage as physical facts, but of virtually infinite file-memory access? from the user's point-of-view, are implied.2.41 ›. Problems of dynamic memory allocation and relocation, of "placement" and "fetching"2.41a are thus involved at a number of levels of storage.2.42 However, many current difficulties are to be noted. For example, Wagner and Granholm state that as of! 1965 no executive or software system has satisfactorily solved the problems of treating the storage. hierarchy as though there were only a single store.2.43

2.44

In general, dynamic storage allocation techniques' are intended to provide flexible means for antici-' pating demand on the part of either the client or the executive control mechanisms of the system itself, to optimize the utilization of primary access memory,2.45 and to provide for the calling up of programs, subroutines, and the data to be processed only when, and to the extent, that these are operationally required.2.46

An obvious problem arises in terms of variable data structures with respect to the flow of programs and data to and from the various levels of access.2.47, Such exchanges need also to be accomplished with minimum delay not only for overall system efficiency but also in terms of client patience with respect to the time-scale of response to his requirements.2.48

Specific system design suggestions include the' development of special processors operable in parallel with the main system 2.49 and the use of a' unified approach to the interlocking problems of allocation, relocation, address indexing, and protection devices.2.50 Ramamoorthy (1966) discusses "look ahead" considerations with specific reference' multiprogramming situations. Walter and Wallace (1967) discuss problems of program lengths. execution time requirements, average time to

to

rocess, and loading times in terms of operations t academic computer centers.

There will be, in addition, need for the most areful analyses of typical requirements for paginaon or segmentation both of data blocks and files nd of programs, including the use of grouped or lustered pages. 2.51 Again, we must consider and valuate the most effective lead-times and critical ath schedules for foresighted transfers of data nd programs between the various levels of orage.2.51a

For such reasons, Opler concludes: "the achieveent of dynamic flow through hierarchical storage ill not be easy. Interdevice channels and control echanisms must be developed. Requirements for evelopment of control programs will be heavy. he devising of new system analysis and description bols is also required." (Opler, 1965, p. 276).

Evans and Leclerc (1967) claim that interactive esponse systems are typically mere adaptations of onventional systems and techniques and are thus far from ideal in many respects". They are thereore concerned with developing improved mechnisms for protection, address mapping and suboutine linkages.

Problems of efficient storage allocations in terms f hierarchies of access and of dynamic flow etween levels of storage are interrelated in many ays.2.52 Nevertheless, while techniques of dynamic corage allocation and pagination as currently vailable solve certain problems of processor ystem management and control, they also raise ontinuing problems of more effective overall ystem design.2.53 For example, studies at System evelopment Corporation have shown that a variety f programs may require "considerable reorganizaon to operate efficiently in a demand-paging enironment." (Fine et al., 1966, p. 11).2.53a It may be oted further that "an examination of the 'spaceme' product for a program illustrates the dangers f demand paging in unsuitable environments." Randell and Kuehner, 1968, p. 303).

So, too, there are problems of "pagination contraints". With many of the systems so far designed or dynamic memory relocation applications, the pages" of either program-control or data constitutng fixed-length blocks used for rapid automatic ansfer between different levels of storage and rocessing-access are arbitrarily fixed, perhaps enerously. Thus, for many applications, a "page" f say 2,000 machine words is generally adequate for ubroutine callup or file subsection processing. lowever, requirements for certain types of experiental investigations and for many practical raphical data processing operations typically volve the processing of two-dimensional arrays of ata for immediate and simultaneous access of reas exceeding fixed pagination limitations.

For example, in the case of a 30,000 + quantized it scan of a 2 x 2" photograph, the input may well xceed the limitations of say, a 2,000-computer-word page". Perhaps the input may be judiciously iggled to fit within a 4-page reserved area (with both

programming and processing penalties), but, in other cases, nine of such pages would be required, with even more severe penalties. Beyond this, there is the question of the programming effort and computer processing time necessary to achieve, over pagination boundaries, bit manipulation tests and improvements for the total input image area.

Another area of current difficulty is discussed by Head as follows: "Often such read-in and relocation schemes divide core memory into fixed blocks which form a repository for programs of a standard size. This, of course, forces the programmer to make a rigid segmentation of his program into one or more chunks which will fit into the arbitrarily. defined core blocks at read-in time. In a higher-level language, each statement written by a programmer will produce a fairly large yet unknown number of actual machine instructions. This is almost certain to (1) aggravate the read-in problem by producing a greater total number of instructions than would onefor-one machine coding, and (2) prevent the preplanned division of programs into relocatable segments of standard length." (Head, 1963, p. 40). Finally we note that continuing R & D concern should be directed to the problems of providing adequate protective devices in multiple-access systems, to be considered next.

2.2.4. Client and System Protection

The R & D problems involved in the general area of development of processing specifications (Box 9 of Figure 2) will be considered in more detail in a later report in this series with respect to the complicated requirements of truly flexible information search, selection and retrieval procedures. Similarly, background considerations for system design involving problems of privacy, confidentiality, or security will be covered in a separate report. However, we may consider here as specialized processing specification requirements the provision of means to protect the system from the client, the client from the system, the system from its own malfunctioning, one client from another, and the client from himself.

Scheduling and priority-interrupt features come first to mind, but at a more advanced stage of system planning and design we need to look at very real requirements of protection from unauthorized access, as well as those of system efficiency.2.53b

In particular, multiple-user systems require the provision of adequate protective devices for individually owned files and data banks and programs and "custom" subroutines for shared data, programs, and program segments, and for the executive, supervisory control, and accounting programs of the system itself. First is the need to shield the system from inadvertent errors, clumsiness, and unauthorized access on the part of a particular client. Thus, regardless of the degrees of privacy required for different clients, the system itself needs protection. This type of situation is especially acute in situations involving user debugging of new pro

grams or, even more critically, the insertion of new routines into existing programs.

*

Then there are the questions not only of system protection from the user, but also of client protection from the system. We note that in the debugging situation, in particular,2.53c programs still under development by some users should not, by error, interfere with procedures being run, simultaneously, for other clients of the system.2.54

For the protection of the user from himself, on-line debugging programs require efficient supervisory and monitoring control programs (see, for example, Evans and Darley, 1965). In other cases, a combination of hardware and software techniques may be used. Thus, in a project at the University of Pennsylvania, “a small computer [PDP-5] has been used between the questioner and the central processor to act as a filter, so that before a question gets through to the big computers, it is stated correctly." (Electronics 38, No. 18, 36 (1965).)

Next, the various clients need reasonable assurance that the material they have stored in the system, both programs and data, will be retained without loss, or that it can be recaptured or restored. However, with respect to this aspect of the protection of the client from the system, it is noted that, for example at Project MAC, while system malfunctions have caused some losses of client programs (and even of data), this experience has not apparently discouraged continued use.2.55 In Kessler's applications of the M.I.T. system, monitoring programs have been developed to check the continuing integrity of the data on file.2.56 Typically, the client of a multiple-access system will also require protection from various types of on-line instrumentation techniques.2.5

2.57

Where several users' programs and/or data are simultaneously held in main memory, adequate measures of mutual memory protection must be employed.2.58 It is necessary that such measures should be extremely flexible because of the rapidity with which swappings and relocations can occur,2.5 and multi-level spheres of protection may be required.2.60

Beyond these questions are the problems of access to shared processor-systems and to multipleuse, consolidated program facilities, common-use and centralized data banks. "The most delicate aspect of the operation of a multiple-access system of the MAC type is the responsibility assumed by the system managers with respect to the users' programs and data that are permanently stored in the disc files. Elaborate precautions must be taken to protect the contents of the disc files against malfunctioning of the system, as well as against actions of the individual users." (Fano, 1964, p. 18). Notwithstanding the urgency of these requirements, however, much remains to be done. For example, "in present-day on-line systems, protection among processes performing different tasks is either

In this case, obviously, the "client" may well be a programmer on the staff of the processing system facility.

absent or confined to one level of object processes that run under the egis of a master control program." (Dennis and Glaser, 1965, p. 9).

2.3. System Control and Performance
Evaluation

Closely related to the problems of scheduling, dynamic memory management, and protection, mechanisms are the questions of effective supervisory control and performance evaluation of systems under various conditions of use. 2.60a In particular, "the total system should be designed to do its own bookkeeping and accounting func-1 tions-keeping track of usage, hours, volumes, times, etc.- both for evaluation of the system and management of costs." (Brown et al., 1967, p. 219).'

Concurrently, however, the client "needs control over the generation, revision, naming and execution of his job-oriented processing routines, as well as the storage and retrieval of such processing routines as part of his data base. He needs to be able to manipulate logical and arithmetical operators,, planning factors and parameters, models and projections of relevant job-oriented operations." (Bennett et al., 1965, p. 437.)

Special problems of system design and control,. including processor and program developments, on-line debugging and instrumentation, and system simulation will be reviewed in another report in this series (on overall system design considerations). We note here, however, that "the burden of establishing proper control procedures falls on the system designer who must in so doing use techniques of information theory, quality control, information redundancy control, error detection and correction, numerical analysis, queuing theory sampling theory, statistical reliability, data reduction, cross correlation, display theory, decision processes, etc." (Davis, 1964, p. 468). Further, "suitable provisions for performance monitoring, trouble detection, and quality control should be included as part of the system design." (Israel, 1967, p. 203).

Examples of various diagnostic and monitoring systems include QUIK TRAN as used in the interpretive mode,2.60b the General Electric GECOS II [General Comprehensive Operating System] programs,2 2.60€ the PILOT system at M.I.T.,2.60d and a computer "Time Monitor" available from Applied Logic Corporation of Princeton, New Jersey.2.6 Hornbuckle (1967) describes a combined hardware/ software monitoring system for graphic display applications in the Project Genie time-sharing. system of the University of California.

2.60€

Among the types of system performance factors of interest to system managers or users (or both) are measures of memory, paging, and subrouting activity,2.61 loop factors and trap activity,2.62 queue' length and work profiles.2.63 Coggan (1967) suggests other measures as well.2.64 Randell and Kuehner (1968) stress the significance of the "space-time.

o product".2.64a It is noted that “users very often want to know whether and how many channels or storage areas are available, how many other users there are, whether they can schedule use of the system at predetermined times, how much of their allotted time has been expended, etc." (Caffrey, in Brown jet al., 1967, p. 219).

n

An M.I.T. example is the TTPEEK command "which allows a user to inspect both the allotments and usage of his central processor time, as well tas his disc, drum, and tape records." (Corbató, 1967, p. 95). A monitor program described by Fiala (1966) displays for all users the size of programs, priority information, and information as to memory space activity, among other factors. 2.65 However, "it is generally agreed that, constrained by cost, the averrage response time is the single most objective performance measure to the user at present." (Estrin and Kleinrock, 1967, p. 86).

A simulation program developed by Blunt (1965) dealt primarily with first-come, first-served queue unloading strategy, but consideration was also given to selecting data units with the shortest servicing time, and other factors. 2.66 Other examples in the literature include the studies of Krishnamoorthi and Wood (1965) with respect to a limiting distribution of user congestion and of Kleinrock 6(1966) involving the use of a queuing theory model for the analysis of sequential processing machines,

3. Storage, File Organization, and Returning to Figure 2, it is to be noted that the development of efficient and economical storage techniques is the area of continuing R & D concern with respect to Box 6. Many of the specific problems of organization and input of material for storage, questions of file management, digital versus facsimile storage, and availability of improved storage media (including microforms) will be covered in other reports in this series (e.g., with respect to the domain of information storage, selection, and retrieval research, or, in the case of advanced developments in storage media, to overall system design considerations). Here, we shall emphasize some of those aspects of information storage functions and techniques that are most closely related to the prob"lems of management and use of multiple-access information processing systems. More particularly, we are concerned here with hierarchies of storage systems, with some of the factors in efficient file Horganization, and with questions of associative or "content-addressable") memory requirements. In general, the processing of large volumes of data to provide varied forms of efficient and economical storage is becoming more and more feasible technically, operationally, and economically. As a consequence, more attention needs to be paid to multilevel representations of the information contents of stored items as well as to suitable hierarchies of access, search, matching, selection, and retrieval procedures.

as well as his 1966 and 1967 theoretical studies of systems.

For his Ph. D. dissertation at UCLA, Coffman (1966) has investigated various stochastic models of multiple and time-shared computing operations. Elsewhere, Coffman and Wood (1966) have reported further on inter-arrival statistics for the SDC system and Coffman and Varian (1968) consider problems of page relocation algorithms.2.66a Wilkes (1967) reviews a variety of page turning and related problems.2.66b Chang (1966) provides a queuing model for non-priority time-sharing such that queue length and response time and their distributions can be readily estimated. Another theoretical investigation of both round-robin and priority scheduling systems is provided by Shemer (1967).

Then there are studies by Martin and Estrin (1967) showing that a priori estimates of computation times for given problems on given systems can be generated by modelling these computations with transitive directed graphs. Other theoretical models are exemplified by Kleinrock's (1967) treatment of time-shared computing facilities as stochastic queuing system under priority service discipline, and with the performance measure based upon the average time spent in the system. Nevertheless, many questions of comparative efficiency remain to be explored.2.66c

Associative Memory Requirements

As of 1968, magnetic core techniques are still the principal media for main-computer, rapid-access, information stores. Because of multiple-user demands, as we have seen in the previous section of this report, such "memories" (even although they may have typical capabilities of a million bits storage and cycle times of a microsecond or less), require considerable "swapping" and "pagination' requirements for time-shared, time-slicing usage. However, it is noted that "memory paging, or program segmentation, reduces the size of the main memory but increases that of the bulk storage", (Riley, 1965, p. 74) and that therefore increasing concern should also be directed to the management of such secondary storage. It is further to be noted that the effective management of secondary or auxiliary storage has been a recurrent problem for both system designers and programmers over the years.3.

3.1

Efficient and economical storage will involve the interdependence of a number of different factors. Among them are the following:

(1) The development and utilization of storage media at many levels of access, density of of information packing, and storage capacity.3.2 (2) The effective organization of multi-level storage in terms of hierarchical access provisions.3.3

(3) The effective organization of multi-level storage in terms of parallel processing.

(4) The integrated systems design of programming control, processor capabilities, and storage accessing for dynamic internal memory allocation and relocation.3.4

(5) The organization of the file or files at any given level of storage, with due consideration to the most harmonious balancing of maintenance and up-dating,3.4a indexing and cross-referencing, multiple copy deposits, statistical data on usage, usage-expectancy factors requirements, and the extent to which typical users require responses at such-and-such thresholds (immediacy of response, comprehensiveness versus pertinency, volume of response). (7) The provision of useful guides, indexes, delimitors (or restrictors) and identifiers, content-indicating clues, and access-priority scheduling, to various sections, compartments, or stratifications of the file or 3.5 files.3. (7) The provision of adequate memory protection devices, including write-protect, read-protect, and overwrite protection. * 3.5a

3.1. Hierarchies of Storage, Data Compression, and Data Consolidation

Just as dynamic memory allocation is increasingly demanded in processor systems involving multipleaccess usage, so dynamic space allocations between levels of storage require a new concentration of system design efforts.3.6 As of today, conflicting demands of fast access and retrievability on the one hand and of compact and economical storage of very large masses of data and recorded information, on the other hand, dictate compromises based upon multiple levels of storage.3.7

The trend toward more versatile and convenient means for man-machine interaction in time-sharing and remotely accessed systems where more than mere text-message processing is desired can be expected to continue its current momentum. New emphases in multiple-access systems planning are therefore being directed toward the problems of providing large capacity data storage banks or files organized in hierarchies of accessibility, especially where different users have differing need-to-know privileges.

It is likely in many potential applications that file organization strategies should be geared to either on-line and multiple-access or to batch operations and/or to suitable admixtures of client-controlled and job-shop-controlled priorities of access and processing. In such circumstances, Benner (1967) considers certain minimal file design considerations involving security, recovery, optimal location/ addressing, flexibility for meeting changing requirements, and compatibility with the programming system and language(s),3.7a

*See also the separate report in this series on some of the background considerations affecting problems of privacy, confidentiality, or security in information processing systems and networks.

notes

3.1.1. Hierarchical Memory Structure Hoagland 3.8 that hierarchical memory structures, with various levels set by access-time characteristics are needed to balance costs. capacities, and access requirements, that the "main" memory size is tied to processor rate in such way that the faster the latter, the larger and faster the memory must be to keep pace, and that economical mass-memory systems represent the key to many new applications.

We envisage, first, hierarchies of storage with appropriate balancing of capacities, access time considerations, and usage-demand probabilities The total storage facilities would be compart mentalized as appropriate by the various types of data to be stored, by usage considerations, and by other criteria conductive to effective maintenance and manipulation. They would be organized in such way as to enable adaptive change to new o modified processing requirements. An importan consideration here is that of the provision o "streaming", or equivalent techniques.3.9

Hierarchies of storage, especially those involving large bulk memory devices, also suggest the use of redundant recording techniques for improved random access. For example, if fully adequate techniques for machine translation were available it is not necessarily the case that significant improve. ments in either mass storage capacity or speed o access would be required before production us could become practical. First, advantage might b taken of Zipf's law respecting the distribution o word frequency possiblities, to organize a hierarchy of dictionary storage and access. Bowers (1966) discusses as one example a dictionary stored fo machine translation applications where perhaps 34 percent of the accesses might be to less than 20 of 100,000 entries. He suggests that "in most cases some combination of different redundancy fraction for several subsets of the store will achieve the minimum access time." (p. 44)

Again, hierarchies of storage may be used t improve the efficiency of list-processing operation as described, for example, by Cohen of the Un versity of Grenoble (1967). This investigator con cludes that the best strategy for selecting the leas active pages is that of time of inactivity. (See als Bobrow and Murphy (1967) for discussion of adapta tions of the LISP programming system to a two-leve store.)

Then there are questions of efficient and eco nomical storage with respect to the items then selves, including compression, truncation, use c the information contained in a record to determin automatically its proper storage address, and us of storage addresses as the surrogates for searc and retrieval of the stored item itself.

366-108 O-70-2