Memory Spaces for the RHODOS Multi-threaded Microkernel System
- 格式：pdf
- 大小：52.43 KB
- 文档页数：21
Memory Spaces for the RHODOSMulti-threaded Microkernel System*M. Hobbs, G. Wickham, D. De Paoli, A. Goscinski{mick, gjw, ddp, ang}@.auSchool of Computing and MathematicsDeakin University, GeelongVictoria 3217, Australia.AbstractEnhancing the RHODOS microkernel to provide the benefits of multithreading required a number of areas to be redesigned and redeveloped. A major component of the RHODOS system that required careful planning, study and development was the RHODOS unit of memory man-agement termed a ‘space’. The concept of a ‘space’ is used to arbitrarily identify and manage (in an architecture independent fashion) an area of memory which may or may not be shadowed to a file on disk. This report introduces the requirements and design issues that the RHODOS multi-threaded microkernel imposes on the memory management subsystem. The differences between this implementation and the original implementation are also highlighted.*This work was partly supported by the Australian Research Council under Grant A49232429 and theDeakin University Research Grant 0504010151.CONTENTS1Introduction (1)1.1Background to the RHODOS Project (2)1.2Goal and Outline of this Report (3)2RHODOS Memory Management (3)2.1Concept of a RHODOS Memory Space (3)2.2Initial Space Design (4)2.3New Space Design (6)3Use and Linking of the Space Components (7)3.1Mapping in a space (7)3.2Use of Segments in the RHODOS Space (7)3.3Example Space Interaction (8)3.3.1Space Elements of a Process (8)3.3.2Hierarchy of the RHODOS Space (9)3.3.3Copy-on-Write Sharing (10)4RHODOS Memory Management Data Structures (12)4.1Process Oriented Data Structure (12)4.2Memory Oriented Data Structures (13)4.2.1Space Structures (14)4.2.2Page Structures (15)4.3Segment Oriented Data Structures (16)5Conclusion (17)6Acknowledgments (18)7References (18)1IntroductionEfficient and effective memory management is one of the primary issues of any operating system. With a distributed operating system the memory management component is required to perform additional tasks not expected from traditional centralised operating system implementa-tions. The extra responsibilities of memory management in distributed operating systems relate to the naming and sharing of memory resources over an entire distributed system. As with any oper-ating system the memory management system is a vital component in the provision of support to users and the processes or tasks created by the users. It is vital that an efficient level of perfor-mance be provided by the memory management system, as with any operating system.Memory management systems based around the concept of paging are commonplace in cur-rent computer architectures. However, modern operating systems running on page based machines require more than just efficiency and improved performance with the management of a computers memory resources. These added requirement expected include:•providing an environment for the execution of processes (secure from the influence of other processes);• a consistent interface between the processing entities and the memory system regard-less of the underlying hardware;•efficient management of physical memory resources both in the allocation and sharing of memory;•flexible protection and locking mechanisms for shared spaces;•the ability to support a variety of memory page management algorithms (paging);•transparent interface to the file system for file mapping;•the ability to transfer data between processes; and•the ability to distribute memory throughout a distributed system.A number of modern system including Unix [Gingell, et al. 88], Mach [Rashid, et al. 88], Chorus [Abrosimov, et al. 89] and Spring [Khalidi, et al. 93] provide most of the requirements for the memory management system within their design, as identified in the above list. The RHODOS Space also provides these requirements but with added emphasis on modularity. The overall objective of the RHODOS project [Gerrity, et al., 91] is to provide a testbed system for the devel-opment of the policies and mechanisms for distributed operating systems. Thus a modular and flexible memory interface is fundamental to the RHODOS project.1.1Background to the RHODOS ProjectThe RHODOS system has undergone a number of extreme modifications over the past few months. The changes made to the system relate directly to the overall structure and interaction of the RHODOS components, including modifications to the microkernel as well as the kernel serv-ers, system servers and user processes. Observed from a high level, there have been two main enhancements achieved from this work. The first enhancement includes the multi-threading of the microkernel allowing full preemptive scheduling in either user or supervisor mode to occur. The second enhancement to the RHODOS system relates to the strict separation of system objects from their respective kernel servers. This implies increased library intelligence and a well defined kernel interface. Although not readily apparent, these changes were a requirement of the advance-ment of the RHODOS project as a whole, which surpassed the ability of the previous single threaded microkernel to provide. It was therefore agreed that the serious modifications (that these entailed) be implemented to fulfil the overall advancement of the project. The modifications were divided into two separate stages, which will be discussed briefly in the following sections.The first stage required for the improvement of the RHODOS system, focussed on the multi-threading of the Nucleus. A considerable amount of effort was devoted to ensuring that the final product resulted in a microkernel that provided all that was necessary, not only for the present but also for the near future. Research into this area and the logical design of such a system are pre-sented in [Wickham, et al. 94a] and [Wickham, et al. 94b] respectively, whilst the implementation aspects are reported in [Wickham, et al. 94c].With the foundations of the RHODOS system firmly in place, the second and more involved stage was undertaken. This stage was primarily concerned with the improvement and enhance-ment of the RHODOS environment, both for the kernel and system server processes as well as for the user processes. This involved the separation and clarification of which system objects (pro-cesses, spaces, mbufs, etc.) and entities were managed and controlled by either the microkernel, a kernel server or a system server process. Although the technical content of this stage was not as complex as that of the multi-threading of the microkernel, the scope and extent of this stage cer-tainly surpasses the first stage modifications.The initial implementation of the RHODOS space [Toomey 90] suffered from an over sim-plification of the process entities, and therefore the restrictions this imposed on them. The most obvious restriction imposed was the maximum size and number of spaces a process could contain.Thus the dynamic sizing and allocation of memory spaces to processes was also one of the major tasks of the second stage. Memory spaces and the enhancement gained by RHODOS is the pri-mary topic of discussion in this report.1.2Goal and Outline of this ReportAs is the objective of the RHODOS system to act as a testbed for the investigation, testing and comparison of distributed system components, it is important to learn the effects various memory management strategies and mechanisms will have on the overall flexibility and perfor-mance of a distributed operating system. The goal of this report is to present the requirements expected from the memory management system of a modern operating system focusing specifi-cally on those of a distributed system. The memory management system of RHODOS will be used as a sample implementation.Section 2 introduces the expectations that RHODOS has from the memory management facilities, by describing the initial and new designs of the RHODOS Space. Use and interaction of the space components are given in Section 3. The data structures and their linking which support the RHODOS Spaces are presented in Section 4.2RHODOS Memory ManagementThe concept of memory spaces was developed for RHODOS to provide the requirements of naming, shareability and protection [Toomey 90]. A secondary requirement was to ensure a sepa-ration between the underlying hardware and the interface provided by RHODOS spaces, which allows simple portability over different memory architectures whilst the higher level view from kernel, system and user processes, are that they have remained unchanged.The following section provides a description of how memory management is provided in the RHODOS system. This is achieved by presenting the RHODOS ‘Space’ concept in conjunction with the data structures and algorithms used to support ‘Spaces’.2.1Concept of a RHODOS Memory SpaceProcesses executing in a multi-user operating systems are composed of regions of memory resources. Because these memory regions (e.g. Text, Data, BSS and Stack) perform different tasks within the processing entity, therefore require different attributes and management details. To simplify the construction of a memory management component of an operating system, it is com-mon for these objects (memory regions) to be referenced through the one set of data structures. In the RHODOS system, a memory region is referenced through the concept of a ‘Space’. The RHO-DOS Space forms an extremely flexible and rich structure for the management of memory resources not only within an operating system, but also for extension over a distributed system.Spaces provide the foundations for building a flexible memory management system upon. The flexibility (and therefore extensibility) of this system is achieved by separating the entire sys-tem into three layers of abstraction:• a hardware dependent level;• a kernel management level; and• a user interface level.Spaces are identified through the use of a RHODOS SName [Goscinski, et al. 94] (System Name). This identifying entity, defined as a structure, also contains fields for protection mecha-nisms to be utilised such as capability techniques. Therefore, RHODOS Spaces can be shared throughout the system by the passing around of their identifying SNames. From a technical point of view, a space is used to provide a mapping (and thus management and control) of a virtual memory region through to the physical memory pages that comprise this region.2.2Initial Space DesignRHODOS Spaces were initially designed as a single level reference structure which con-tained all the relevant details associated with this space, including such elements as size, location, protection, mapping, physical pages and linked list fields (as shown in Block 1). The spaces were attached to a process through the Process Control Block in an array of pointers [De Paoli, et al. 94], with the location in the array determining the type of space that the pointer points to (either a Text, Data or Stack space).The link from the space (Text, Data, etc.) to the underlying physical pages which comprise the space, is performed through an array of page entry pointers (one page entry per physical page). This implies a maximum size limitation of the original spaces as the size of the array is static and had to be determined at time of compiling the microkernel. A maximum size of 2Mb has satisfied the current experiments and development, but is now proving to be a limitation as our experimentation matures.The initial data structure for the RHODOS space is shown in Block 1. Contained in this structure are the three sets of elements required for the implementation of the original space con-cept. The first section contained the default attributes of the space relating to the address, length, protections; and direction of the space.The second set of elements contained within the space structure relate to the shareability attributes of the space including: statistics on the number of entities sharing this space; whether the space is marked copy-on-write; and how many times this space is shared.Block 1: Original Space StructureThe third set of elements relate to the physical pages and backing file, where the backing file SName was also overloaded to also be used as the naming attribute of the space (this has over-loading has been removed in the current version). Finally, we have the doubly linked lists pointers for maintaining the lists of spaces and their association in the used and free lists of spaces.The space details were separated from the page elements (which mapped to the physical hardware pages) thus providing a single level of abstraction presented to the user. The pages asso-ciated for the space were located in an array of page elements (of a maximum size). These pages were ordered from zero through to the last page element.Block 2: Original Page Entry StructureThe details relating to the physical pages are found in the page entry structure, Block 2. The page entry structure was basically used to manage the mapping between the physical pages (actual memory) and the virtual pages used in constructing an address space. The page entry structure is composed of a number of elements including the physical page number represented by this structure, the number instance that this page is shared with other spaces and linked list vari-ables for maintaining lists of used and free page entries.A main problem encountered with this design relate primarily with the difficulty in imple-menting efficient sharing of pages between spaces. This is due to the lack of knowledge contained within the page entries and space structures to indicate which pages as shared and which aren’t given two spaces. This problem is evident when a space is shared copy-on-write and pages are duplicated one at a time as they are written to, instead of copying the entire space after the single write.2.3New Space DesignThe new design of the RHODOS spaces has four main differences to the original design:•Two level space reference hierarchy — highest level for representing the location and defaults of the space and the second level for representing the actual memory details(such as pages).•Sets of spaces are associated through a Process ID structure, separating it from the PCB structure. Therefore the space manager is able to manage the spaces on behalf of aprocess without needing to know the details of the PCB;•Linked lists are used to provide dynamic sizing and numbers of spaces; and•Reference links from the pages back to the owner spaces, to allowing paging and shar-ing to be implemented.The new version of the RHODOS memory management system is made up a suite of space structures representing the hierarchical abstraction levels. These space structures include the space structure, space units, page groups and page entries, and finally page reference structures.Under the new version of RHODOS (the multi-threaded microkernel version), the two limi-tations of the original implementation were removed:•size limit of a space — this allows a process to execute in a more flexible environment;•static number of spaces that could be associated to a process — this allows both the implementation of a multi-threaded microkernel to be achieved in a flexible fashion,and gaining such features as shared memory, dynamically linked libraries and file map-ping.3Use and Linking of the Space Components3.1Mapping in a spaceThe spaces that combine to form a complete process include the Text, Data and Stack spaces. All details relating to process spaces, such as size, base address, protections etc., are located within their set space structures. A mechanism is required to transpose this space information onto the address space of the architecture (also known as a context). This is achieved through the space_map() function which is usually called at the time of a context switch. Initially all spaces of a process are unmapped and are not physically located in an address space. Depending on the pol-icy used either: all spaces owned by the process are mapped in when first executed (context switched in); or mapped in at a page at a time when using a paging strategy. The second policy would mean only pages accessed or referenced would be mapped in, thus optimizing the utiliza-tion of memory resources.3.2Use of Segments in the RHODOS SpaceSegments are a hardware specific term used generally to reference groups of physical pages. In the case of the Sun 3/50, segments are groups of 16 pages which can be mapped in and out as an entire block. Therefore they reduce significantly the number of memory management calls [Toomey 90]. This allows an extremely quick mapping in and out of processes from an address space (or context). Since segments are hardware specific, they have to be kept separate from the space elements themselves. Segments used by a process (all the spaces mapped into an address space) form a linked list attached to the process ID structure. The segment reference structures contain the base address of the segment and the physical segment that is mapped into that address. This system allows the same physical segment to be mapped into multiple virtual addresses, for use in space sharing.The primary benefit obtained from utilising the segment structures occurs when a context switch is issued. If the next process to be executed has executed before, then it must already have been mapped into segments. When time comes to map this process back in, the segments them-selves can be mapped in rather than mapping in every individual page that goes to make up the process, thus decreasing the overall time of a context switch.3.3Example Space InteractionAs stated in Section 2.3 the new RHODOS spaces are based on a two level references hierar-chy that allows the separation of the logical identification of a space from the actual physical memory that the space maps to. This increases the complexity of the RHODOS space suite, but also provides the required flexibility and modularity. This sub-section is dedicated to providing some examples of how the RHODOS space elements interact to provide the functions and ser-vices required.The term ‘space elements’ means all the data structures that combine to form the space suite. These structures include:•Process ID structure — identification structure used as the link between processes and the spaces that the process owns;•Space structure — contains the logical information relating to a memory space;•Space Unit structure — second level space structure which allows two spaces (proc-esses) to share the one memory region with the least overhead;•Page Group structure — used to identify a group of pages, or page set;•Page Element structure— contains the details relating to a physical page;•Page-Space Reference structure — used to find the space or spaces that own/share a given physical page;•Segment Reference structure — allows the logical reference of a segment and also allows the segment to be shared with other processes; and•Segment Element structure — contains the details relating to a physical segment.The examples given in the following sections range from the simple interconnections of these space elements when a process owns a number of space, through to the steps involved in sharing memory between different processes.3.3.1Space Elements of a ProcessA sample of the implementation and association of the new RHODOS space elements is shown in Figure 1. This is a simple instance of a process, identified by a Process ID (refer to Block 3 for the Process ID data structure), which has two spaces allocated to it. The space struc-ture then points to a space unit which in turn points to groups of page pointers. Each page pointerreferences a page entry structure which maps to a given physical page. Each page has a link back to the owning spaces through the page reference structures.Figure 1: Layout of the RHODOS Space Elements3.3.2Hierarchy of the RHODOS SpaceThe next example, shown in Figure 2, demonstrates the two level hierarchy of the RHODOS spaces, where two separate processes share a memory space (the same physical memory pages). This would be the case where two process share a space with both processes granted read and write privileges.Figure 2: Example of Physical Page Sharing (Read/Write)In this example from the space units down the data structures are identical. Only the Space structure is required per process, which is the logical identifier of the memory region and it is this structure that identifies the base address and the default protections of the space. Therefore dupli-cation of referencing the memory region is avoided by sharing the Space Unit structure between the two owning Spaces.The usefulness of the having the separate Space structures becomes apparent if the spaces are both mapped in at different addresses. Normally the spaces are mapped in at the same addresses in memory, this allows the segments on which the spaces are mapped to be shared through the Pro-cesses ID structures via segment reference structures. This enables the segments to be mapped in different address spaces rather than mapping the relevant pages in.The ability to have a shared space mapped into two address spaces at two different virtual addresses can be achieved with the RHODOS memory management system. In this case, the spaces base addresses would be different in Space structures, with the restriction that the addresses must differ by a multiple of the underlying page size. This is due to the fact that the Space Units work on ‘pages’ as their base mappable unit, therefore all access to the page must be relative to the start of the page. This ability allows the implementation of such things as shared memory and dynamically linked libraries which are required to be linked into a processes address space at various locations, depending on the size and positions of their spaces.3.3.3Copy-on-Write SharingSharing of spaces or duplication of spaces can be implemented in a variety of ways, ranging from very inefficient implementations where pages are duplicated on receipt of the request, through to efficient implementations where pages are shared up until the point where a shared page is written to. The second way of memory sharing is known as copy-on-write. Since a mem-ory region marked as copy-on-write will in time become two separate spaces, this method of shar-ing is implemented using the RHODOS memory management system as shown in Figures 3, the before situation’, and Figure 4, the ‘after situation’.Once a space has been duplicated using the copy-on-write service, all the pages are shared between both the original space and the newly duplicated space, as shown in Figure 3. Since at a later stage the pages will most likely be duplicated, then each space has it own space structure, space unit structure, and page group structures. Each page entry has a link back to the owning spaces through the page reference structures, and the initial state (shown in Figure 3) is wherenone of the pages have been written to and therefore each page entire is still shared with the two owning spaces. This reference will be broken when the page is written to and thus duplicated.Figure 3: Copy-on-write space sharing (initial state)A copy-on-write implementation was extremely difficult to implement in the old version of the RHODOS space as there was no way to determine which spaces owned a given page, without an exhaustive search through all known spaces. The benefits obtained from the new implementa-tion include the simplification in the management of shared pages. As pages are only duplicated on writing to a page, the relevant owning spaces can be found quickly and efficiently. The new version also allows the ability to have spaces sharing subsets of pages with other spaces.Figure 4: Copy-on-write space sharing (after writing to a page) When a write fault occurs on the pages shared between the two (or more) spaces, a new free page is allocated to the faulted process. The page contents is copied across, the link from the orig-inal page to the faulted process space is broken and a new page reference structure is created. The duplication of the page (the fourth page) is shown in Figure 4.The ability to implement ‘paging’ effectively was not possible in the previous version of RHODOS due to the microkernel being single threaded [Wickham, et al. 94a] and the space struc-tures not being as rich and flexible as required. The new space structures, in combination with the multi-threaded microkernel allows the implementation of paging. All physical pages used by pro-cesses on a given host are all contained within a list of ‘used pages’. This list can then be searched to find the least recently used page (or some other policy such as random or a more complex algo-rithm) as a candidate for paging to disk. The page is then disassociated from the spaces that use it, leaving null entries in the page lists (where a null entry does not map to a physical page but con-tains the information on the page that was there). When a page fault occurs, the space manager can determine which page was in error and thus return the page from disk if required.Paging is an example of the benefits obtained by separating the physical pages from the space structures themselves. The paging routine can then be implemented as a component of the Space Manager or as an independent and separate entity, therefore being able to be changed and modi-fied without altering the other components of the memory management system (which match well the design objectives of the RHODOS project).4RHODOS Memory Management Data Structures In the following sections, the data structures which form the RHODOS memory management system are presented. The data structures comprising the RHODOS memory management system can be divided into three logical sets of data structures. The first is the primary management struc-ture used to link a process entity to the memory resources used by that process (including spaces and segments). The second set form the bulk of the memory management structures used with RHODOS. These include the pages, spaces and page-space reference structures. The final set of data structures are required for the management of segments used by a process once it has been mapped into an address space.4.1Process Oriented Data StructureA requirement of the multi-threaded version of RHODOS, was to separate resources into clearly defined sets of system objects and their managing kernel servers, i.e., spaces with the Space Manager, processes with the Process Manager. This required the full use of the RHODOS naming system. As stated in Section 2.1, the RHODOS SName is used for this purpose and both processes, and their spaces are allocated a system name [Goscinski, et al. 94].The process itself may have a dynamic number of spaces associated to it. Therefore spaces are attached to the process/space identification structure using a linked list. Block 3 shows this data structure. The first and most important element of this structure is the process name. This is used by the Space Manager in its maintenance of the process hierarchy (child/sibling relation-ships).Block 3: Process—Space ID StructureAlso contained in this data structure are fields specific to the context switching module of the Nucleus [De Paoli, et al. 94], indicating whether the process (and its’ spaces) required to be re-installed into a given address space. The next fields of the Process ID structure are the head and tail pointers to the singly linked list that combine to form this process. As the segment mapping is disassociated from the spaces themselves and only relate to the process as a whole, the list of seg-ments presently mapped in for this process is found from the process/space id structure.4.2Memory Oriented Data StructuresThe separation of resources in the multi-threaded microkernel along with the need for the number and size of spaces to be dynamic, has led to five data structures being utilised for memory management. These data structures provide the representation and management information for a memory region. There are three levels of abstraction used within the RHODOS spaces: space, space unit and pages. They range from the highest level with the concept of a ‘memory space’itself down to the lowest level where the physical pages are represented.。
