With reference to a distributed environment consisting of nodes connected in an arbitrary network topology, we propose the organization of a protection system in which a set of subjects, e.g. processes, generates access attempts to memory segments. One or more primary passwords are associated with each node. An access to a given segment can be successfully accomplished only if the subject attempting the access holds an access privilege, certified by possession of a valid protected pointer (p-pointer) referencing that segment. Each p-pointer includes a local password; the p-pointer is valid if the local password descends from a primary password by application of a universally known, parametric one-way generation function. A set of protection primitives makes it possible to manage the primary passwords, to reduce p-pointers to include less access rights, to allocate new segments, to delete existing segments, to read the segment contents and to overwrite these contents. The resulting protection environment is evaluated from a number of viewpoints, which include p-pointer forging and revocation, the network traffic generated by the execution of the protection primitives, the memory requirements for p-pointer storage, security, and the relation of our work to previous work. An indication of the flexibility of the p-pointer concept is given by applying p-pointers to the solution of a variety of protection problems.

With reference to a distributed system consisting of nodes connected by a local area network, we present a new formulation of the password capability paradigm that takes advantage of techniques of symmetric-key cryptography to represent password capabilities in memory. We assign a cryptographic key to each application; the password capabilities held by a process of a given application are encrypted by using the key of this application. Passwords are associated with object types; two or more objects of the same type, which are allocated to the same node, share the same set of passwords. Our password capability paradigm preserves all the advantages concerning simplicity in access right representation and administration (distribution, verification, review and revocation) that characterize the classical paradigm, while keeping the memory requirements for password storage low and solving the problems connected with password capability stealing and forging.

We consider the problem of access privilege management in a classical protection environment featuring subjects attempting to access the protected objects. We express an access privilege in terms of an access right and a privilege level. The privilege level and a protection diagram associated with each given object determine whether a nominal access privilege for this object corresponds to an effective, possibly weaker access privilege, or is revoked. We associate a password system with each object; the password system takes the form of a hierarchical bidimensional one-way chain. A subject possesses a nominal access privilege for a given object if it holds a key that matches one of the passwords in the password system of this object; the protection diagram determines the extent of the corresponding effective access privilege. The resulting protection environment has several interesting properties. A key reduction mechanism allows a subject that holds a key for a given object to distribute keys for weaker access rights at lower privilege levels. A subject that owns a given object can review or revoke the passwords for this object by simply modifying the protection diagram. The memory requirements to represent a protection diagram are negligible; as far as password storage is concerned, space–time trade-offs are possible.

We consider a single-address-space system which implements a form of segmentation with paging within the framework of the multithreaded model of program execution. A salient problem of a system of this type is the definition of the set of mechanisms enforcing memory protection. We present a paradigm for the protection system design that is based on the well-known concepts of protection domains and access rights. The resulting environment guarantees an effective separation of the memory resources of the different processes, whose loosely coupled interactions correspond to explicit actions of information sharing. Within the boundaries of a single multithreaded process, a less-stringent protection requirement is to confine the consequences of a programming error in the thread that originated the error. These results are obtained by taking advantage of techniques of symmetric-key cryptography to represent access privileges in memory at the level of the single pages that form a segment.

A salient aspect of protection system design is the set of the mechanisms for the representation, distribution, verification and revocation of access privileges. With reference to a segmented virtual memory space, we present an approach that is based on the use of symmetric-key cryptography to represent segment pointers, including access right specifications. Our design effort has been guided by three main objectives: (i) to maintain the simplicity of access privilege representation that characterizes classical capability and password-capability systems; (ii) to keep the memory requirements low even in the case of complex access privileges expressed in terms of several access rights; and (iii) to allow an easy implementation of effective techniques for access privilege review and revocation.

We present a thorough analysis of the memory behaviour of page caching and prefetching algorithms. The analysis is restricted to programs whose execution consists of iteration of a sequence of page accesses. Program activity is characterized in terms of utilization of system resources. A graphical model of program execution is used to describe both page placement in the primary memory and the actions of page fetch and replacement. The algorithms are compared from the point of view of a number of performance indexes that include program response time and utilization of the secondary memory system. Special attention is paid to transient program behaviour and the effects of the time necessary for the processor to control the disk activities of page fetch. The results of a large set of measurement experiments are used to validate the analytical model and acquire significant indications concerning the extent of the simplifying assumptions made in the theoretical analysis. The discussion of the relation to previous work makes special reference to two classes of algorithms that received much attention in the past, aggressive prefetching and informed prefetching.

A distributed, persistent memory system is considered, which implements a form of segmentation with paging within the framework of the single-address-space paradigm of memory reference. A peculiar problem of a system of this type is the lack of protection of the private information items of any given process against unauthorized access attempts possibly performed by the other processes. We present a set of mechanisms able to enforce access control over the private virtual space areas. These mechanisms guarantee a degree of protection comparable to that typical of a multiple-address-space system, while preserving the advantages of ease of information sharing, typical of the single-address-space model. The resulting environment is evaluated from a number of salient viewpoints, including ease of distribution and revocation of access rights, strategies for virtual space reuse, and the storage requirements of the information for memory management.

With reference to a distributed context consisting of computers connected by a local area network, we present the organization of a memory management system giving physical support to a uniform, persistent vision of storage according to a single address space paradigm. Our system implements a two-layer storage hierarchy in which the distributed secondary memory stores the valid data items and the primary memory supports a form of data caching, for fast processor access. The proposed system defines a small, powerful set of operations that allow application programs to exert explicit control over the memory management activities at the levels of physical storage allocation, data migration across the network, and the data movements between the secondary memory and the primary memory. The system, that has been implemented in prototype form, is assessed from a number of viewpoints. We show that the storage requirements of the information for memory management are negligible. Moreover, the number of messages necessary to determine the network location of a given data item is low and independent of both the network size and the past movements of this data item in the distributed storage.Copyright © 2000 John Wiley & Sons, Ltd.

Abstract The exploitation of the salient features of capability‐based addressing environments leads to a high number of small objects existing in memory at the same time. It is thus necessary to enhance the efficiency of the mechanisms for object relocation, and to avoid congestion of input/output devices due to swapping. In this paper, we present an approach to the management of a large virtual memory space aimed at solving these problems. We insert partial information concerning the physical allocation of each object into the virtual identifier of this object. Objects are grouped into large swapping units, called pages. The page size is independent of the average object size. This results in enhanced efficiency in managing the relocation information both with regard to memory requirements and access times. The allocation of objects into pages, and the movement of pages through the memory hierarchy, are controlled by user processes. This means that programs which have knowledge of their own use of virtual memory can increase their locality of reference, diminish the number of swap operations and reduce fragmentation.

The architecture of a cache memory is presented, aimed at reducing the memory bandwidth requirements of programs written in block-structured, high-level languages. At any given time, the cache contains two portions of the stack area of the running program, corresponding to the global and the local activation records. With respect to traditional cache architectures, the proposed architecture is characterized by increased performance and a reduced complexity of the logic for cache space addressing and management. These results have been obtained by controlling the cache activity at the software level to take advantage of the stack paradigm.

Abstract A high level of complexity is involved in program dynamics. A number of tools have been developed to assist the programmer in mastering this complexity in the various phases of software development. However, these tools are specifically oriented towards the monitoring of particular aspects of program behaviour. This paper presents the results of a systematic attempt at defining the user interface to an environment for program debugging, program performance evaluation and program structure analysis. This environment can be used to implement many common debugging techniques, and to evaluate important program performance indexes and program structure statistics. It supports both sequential and concurrent block‐oriented high‐level languages.

In the event-action model of interactions between the debugging system and the program being debugged, an event will occur on the evaluation of a conditional defined in terms of the program activity if the evaluation yields the value true, and an action is an operation performed by the debugging system on the occurrence of an event. This paper presents a set of mechanisms for expressing conditionals at different levels of abstraction. At the lowest level, the authors have the simple conditionals, which can be expressed in terms of the values of the program entities and of the execution of the program statements. Simple conditionals can be grouped to form higher-level compound conditionals, which can be expressed in terms of the state and flow histories. The paper shows that the proposed abstraction mechanisms are powerful tools for monitoring program activity. They adequately support different debugging techniques, and offer the user a considerable degree of control over the debugging experiment.>

A virtual address cache memory, whose operation is controlled explicitly by software, is presented. Ad hoc hardware mechanisms, including machine instructions and an operand addressing mode, reduce the complexity of cache management logic in favor of the capacity of the cache, and solve the major problem of virtual address cache organization: two or more virtual addresses mapping into the same real address.>

The problem of implementing abstract objects in a system having a capability based addressing is analysed in some detail. Hardware features needed to support a classical capability environment are first pointed out, and a simple implementation of abstract objects is presented. Then a generalization of the classical capability environment is given, which allows one to solve the stated problem in a more efficient way.

Abstract In this paper a capability addressing environment is presented, based on the concept of extended capability. First of all it is shown that such an environment is well suited for implementing objects of abstract type. Then the problem of distributing and revoking access authorizations on abstract objects is considered and an efficient solution is presented. The revocation mechanism results in being selective, transitive and deferred.

An architecture is presented which incorporates capability based addressing and memory tagging features. It defines three kinds of mechanisms for the implementation of object types, which correspond to as many different levels of abstraction. At the lower level, there are the machine types, the operations of which are implemented by machine instructions. At the upper level, there are user types, the operations of which are concretized by means of software routines. The intermediate level is that of predefined types; in this case, too, the operations are supported by software routines, but their efficiency of execution is much greater than is usually to be found in operations of user types. However, one drawback is that these routines should be proved to be correct, as they have a potential for corrupting the integrity of the whole protection system.