Virtual Storage Concepts
This section introduces concepts common to virtual memory systems. A virtual storage system (or virtual memory system) is a system where executing (active) programs reside in auxiliary storage (i.e., on disk) and selected portions of the program are placed in real storage as needed.
micsrm140cd
This section introduces concepts common to virtual memory systems. A virtual storage system (or virtual memory system) is a system where executing (active) programs reside in auxiliary storage (i.e., on disk) and selected portions of the program are placed in real storage as needed.
The need for memory management arises from the development of hardware and software architecture to support multiprocessing and time-sharing systems. The earliest computer systems ran one job at a time in serial order. Thus, there was no sharing of resources. As computers and peripheral devices became faster, the desire to use these resources more efficiently led to the introduction of multiprogramming systems. A multiprogramming system allows several jobs to be in memory concurrently. This allows one job to use CPU resources while another is waiting on I/O and vice versa.
The next level of development occurred as people costs started to approach hardware costs. The desire to increase programmer productivity led to the introduction of time-sharing systems where many users shared memory for short periods of time. An interactive time-sharing system gave individual programmers access to computing power through terminals when they needed it. When a given terminal was not active, the system could occupy itself with other users or other tasks.
The development of virtual systems stemmed from the creation of these systems. Memory was a very expensive resource and the memory demands of the time-sharing systems greatly exceeded the capacity of the existing computer systems. This began the attempts to deal with the issue of real storage management.
The type of address resolution used by the hardware was the major factor determining what type of memory sharing scheme was used for managing real storage. The three types of addressing used by the various systems and some of the design implications for sharing memory are briefly discussed in Overview of Expanded Storage section below. The purpose of describing these early systems is to develop the logical progression of these concepts for the reader not familiar with virtual systems.
Two critical issues arise from the time-sharing of real memory that are only mentioned in this chapter. They are data security and system integrity. Early systems largely ignored these subjects. In all time-shared systems, the real storage management methodology must have data security as a primary goal.
Address Resolution Schemes
The resolution of addresses is a central issue to virtual systems for two reasons. First, memory may not be shared unless the code and data of one user is protected against unauthorized modification by the other users (be it accidental or malicious). Second, the address resolution mechanism largely dictates the manner in which users may be moved in and out of real storage.
If a virtual system is to provide more apparent (virtual) storage than is actually available, the system must be able to allocate the real memory it has in an efficient manner. One method of moving users in and out of real storage is paging.
This section briefly traces the development of address resolution by the IBM operating systems in order to provide a conceptual basis for discussing MVS real storage issues.
In general, there are three kinds of address resolution used:
- Absolute addressing
- Relative addressing
- Dynamic addressing
There are three times in the life of a program when addresses may be assigned: when the program is written or compiled (absolute addressing), when the program is loaded into memory (relative addressing), and when the program is executed (dynamic addressing). Of these schemes, only dynamic addressing requires hardware to support the resolution of an address. In this section, we discuss each of these addressing schemes in terms of the problems they impose or solve for a virtual memory system.
Absolute Addressing
The early computers did not have any hardware to support memory sharing, such as memory protection features or dynamic address resolution. These computers had an instruction format something like that shown in Figure 2-19:
Figure 2-19. Computer Instruction Format
ooooxxxaaaaaaaa | | | | | | | | +--- address field | | | +-------- register specification | +------------ instruction op-code
Where the instruction had an op-code (o) and a general register specification (x), and the remainder of the bits comprised the address (a). The amount of real memory was limited by the number of bits in the address portion of the instruction format. Programs were prevented from accessing or altering the data of other programs because real memory was not shared concurrently. Only one task was present in memory at one time. There was no effective protection for the resident operating system code.
In terms of memory management, the only virtual memory allocation scheme possible for implementing a time-sharing system on these machines was swapping. Swapping involves moving an entire program into real storage from auxiliary storage in order to make it active, or moving an active program out of real storage into auxiliary storage, making it inactive.
Relative Addressing (Address Resolution At Program Load)
Nothing in the instruction format shown in Figure 2-19 precluded address resolution at the time the program was loaded. However, without memory protection facilities such as the protect keys used by the IBM S/360 series, there was no reason to develop the program loaders and linkage editors to implement load time address resolution. In the IBM S/360 series, there are two levels of address constants and the instruction format is designed to make load time address resolution more efficient. The S/360 instruction formation shown in Figure 2-20 provides two other advantages for program load address resolution.
Figure 2-20. S/360 RX Instruction Format
oorxbaaa | |||| | |||| | |||+---- address offsets (12 bits) | ||| | ||+----- Base Register (4 bits) | || | |+------ Index register (4 bits) | | | +------- General Register (4 bits) | +--------- Instruction op-code (8 bits)
The instruction length of an RX instruction is 32 bits (one full word). The address field of the instruction is defined by the baaa portion, which is 16 bits in length. This address is resolved as a displacement (aaa) from the base register (b), which contains a 24-bit address. This defines a 24-bit address with only 16 bits in the instruction. Also, because all addresses are relative to a base register set by the program, the object code is relocatable in its executable format. Thus, less overhead is involved during the program load, as only address constants must be resolved at this time.
However, in the S/360, once a program is loaded it may not be moved. The loader resolves address constants with absolute addresses and the program execution places absolute addresses in the required base registers. From that point on, the program is fixed in the real memory locations where it was loaded. Thus, for swapping to work, a program would have to be swapped back into these same storage locations.
IBM developed two multiprogramming systems on the S/360 series. The first, MFT, divided memory into a number of fixed partitions. The second, MVT, dynamically assigned real memory to jobs as they were started.
Neither of these system designs was flexible enough for a time-sharing environment. In MFT, the fixed partitions made swapping a possibility but required a preallocation of memory, which severely constrained the batch workload. In MVT, swapping was not practical because a job had to be swapped back into exactly the same real memory it was first loaded into, and that memory had to be contiguous.
The first IBM time-sharing system combined ideas from each of these systems. The first Time-Sharing Option (TSO), released with MVT in the early 1970s, allocated a number of fixed time-sharing partitions, with the remainder of real storage dedicated to batch.
Figure 2-21 shows a memory allocation for an MVT system. The System Control Program (SCP) occupied the high and low addresses, with the area in between dynamically assigned to jobs.
In MVT, the memory between the executing programs was available for execution. Eventually, 50 percent of the available memory is lost to the type of memory fragmentation shown in Figure 2-21. This type of fragmentation is called EXTERNAL FRAGMENTATION. In MVT and in other similar systems, the real memory lost to external fragmentation was shown to average around 33 percent. This represented a serious constraint on throughput, as well as requiring a substantial effort for the installation in trying to minimize the occurrence and impact of this fragmentation.
Figure 2-21. An MVT Real Memory Allocation
--------------------------- | | | System Queue Area | | | |-------------------------| | PROGRAM 2 | |-------------------------| | ////////////////////// | | ////// not used ////// | | ////////////////////// | |-------------------------| | | | | | PROGRAM 1 | | | | | |-------------------------| | ////// not used ////// | |-------------------------| | | | PROGRAM 4 | | | |-------------------------| | ////////////////////// | | ////////////////////// | | ////// not used ////// | | ////////////////////// | | ////////////////////// | |-------------------------| | PROGRAM 3 | |-------------------------| | | | Nucleus | | | ---------------------------
Dynamic Address Resolution
This discussion of dynamic addressing outlines the benefits of using a dynamic scheme in implementing a virtual system. Address resolution performed as each instruction is executed solves the problem of code and data relocation. Two schemes were implemented: segmentation systems and paging systems. A segmentation system divides each program into a number of parts called segments. Segments of a program may be relocated in real memory. The number of segments a program could be divided into was small. On the GE635, for example, there were seven segmentation registers. As this scheme still had the external fragmentation problem illustrated by Figure 2-21, it never gained wide use.
In a paging system, all real memory is divided into equal parts (pages) of a fixed length. Each active program in virtual storage is "paged in" to real storage in order to gain access to the CPU. A paging system allows the virtual pages making up a job to be placed anywhere in real memory. In a paging system, there can be no external fragmentation, because each program in memory occupies an integral number of pages. Each program has some wasted space because allocation is by pages. This is called internal fragmentation. This problem is minimized for a given system by the selection of a page size and by the techniques used for dynamic storage allocation within a program. Early work in this area with IBM virtual systems is described in the IBM Journal of Research and Development.
One of the goals of a virtual system is to relieve application programs of memory management concerns. In non-dynamic systems such as MVT, a great deal of system design went into making a program use memory more efficiently through the use of overlay structures and dynamic loading facilities. In a virtual memory system, a program is given a large amount of virtual memory to use. The operating system then allocates real storage to jobs as required. Figure 2-22 shows a simplified view of the virtual storage allocation in an MVS/370 (pre-MVS/XA) system running four programs. To each program, it appears as if the entire virtual storage of 16 megabytes is available to it (less the areas used by the control program).
Figure 2-22. MVS/370 Virtual Memory Allocation
------------- | | |Common Area| | | |-----------| ------------- ------------- | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | PROGRAM 1 | | PROGRAM 2 | ... | PROGRAM 4 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |-----------| ------------- ------------- | | | Nucleus | | | -------------
An implication of the MVS/370 24-bit addressing scheme is that the size of a user application program is constrained by the limitations of 16 megabytes minus the size of the control program. As user application programs grew larger and larger, it became evident that an addressing scheme that allowed only 16 megabytes of virtual storage addressability was inadequate.
To provide the necessary virtual storage constraint relief, allowing users to write applications that are substantially larger than those possible in MVS/370 systems, MVS/XA (extended addressing) was developed. By expanding the size of the address to 31 bits, jobs can address up to 2 billion bytes (2 gigabytes) of virtual storage. To maintain compatibility with MVS/370 and yet provide the expanded addressability, MVS/XA provides regions of virtual storage that are defined below the 16 megabyte line and "extended" portions of these regions are defined above the 16MB line.
Figure 2-22 shows conceptually how this is done. MVS/XA treats both the portion below the 16MB line and the extended portion above the 16MB line as one logical area. As with the example in Figure 2-22, each job running in an MVS/XA system would have its own copy of the Private and Extended Private areas.
Figure 2-23. MVS/XA Virtual Memory Allocation
2Gb ------------- ------------- ------------- | | | | | | | PROGRAM 1 | | PROGRAM 2 | | PROGRAM 4 | | Extended | | Extended | | Extended | | Private | | Private | ... | Private | | Area | | Area | | Area | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |-----------| ------------- ------------- | Extended | | Common | | Area | 16MB ------------- | | |Common Area| | | |-----------| ------------- ------------- | | | | | | | PROGRAM 1 | | PROGRAM 2 | | PROGRAM 4 | | Private | | Private | | Private | | Area | | Area | | Area | | | | | ... | | | | | | | | | | | | | | |-----------| ------------- ------------- |Common Area| 0K -------------
You can determine whether the program or modules, use 24 bit or 31 bit addressing via the AMODE attribute which is specified to the assembler or the linkage editor. The default if the AMODE attribute is not specified is 24 bit addressing.
You can also determine whether the modules are to be loaded into the User Region (below the 16MB line) or the Extended User Region (above the 16MB line) via the RMODE attribute for the assembler or linkage editor. The default if the RMODE attribute is not specified is to load the module into the User Region below the 16MB line. This allows programs written for MVS/370 to run in MVS/XA with generally no modification.
Figure 2-24 shows how real memory might be allocated to the four jobs concurrently executing in Figure 2-22. First, no real memory is lost to external fragmentation. If another job starts and no real memory is available, either some pages may be taken from other jobs to make real memory available, or one or more of the active jobs may be removed from memory (in MVS, swapped out).
Real memory is more efficiently used because idle portions of the program (either code or data) are not kept in real memory. In Figure 2-24, the page numbering indicates the page number in the program's virtual storage. Thus, in MVS, where the page size is 4096 bytes, page 1 is the first 4K of the program, page 2 the second 4K, and page n is the nth 4K section of the program.
We see from Figure 2-24 that only referenced parts of the program need to be resident and that these need not be contiguous in real memory. In theory, a program could be executing (efficiently) with only one page in memory at a given time.
Figure 2-24. An MVS Real Memory Allocation
--------------------------- | PROGRAM 3, Page 9 | --------------------------- . . . . --------------------------- | PROGRAM 2, Page 7 | |-------------------------| | PROGRAM 1, Page 1 | |-------------------------| | PROGRAM 4, Page 4 | |-------------------------| | PROGRAM 3, Page 6 | |-------------------------| | PROGRAM 2, Page 1 | |-------------------------| | PROGRAM 1, Page 4 | |-------------------------| | PROGRAM 1, Page 5 | |-------------------------| | PROGRAM 3, Page 2 | |-------------------------| | PROGRAM 2, Page 4 | |-------------------------| | PROGRAM 1, Page 3 | |-------------------------| | PROGRAM 4, Page 3 | |-------------------------| | PROGRAM 1, Page 9 | |-------------------------| | | | Nucleus | | | ---------------------------
Paging Concepts
Having settled on paging as the method of providing virtual storage, three issues that have a large impact on the final design must be considered. These are page size, the method of mapping a virtual to a real address, and the determination of which pages should remain in real storage.
Page Size Determination
In MVS, to remain compatible with S/360 and S/370 storage protection features and existing storage allocation software, a page size that was a multiple of 2 KB was dictated. MVS chose a page size of 4 KB, accepting that potentially 4095 bytes of storage could be wasted.
The choice of page size is a compromise between the amount of storage lost to internal fragmentation and the size of the tables that translate virtual addresses to real addresses (the Page Tables).
Another issue in considering the page size is the page transport time, that is, the time required to write the page to auxiliary storage. With the 16 MB virtual address space provided by MVS through SP1.3, the 4 KB page size has worked well. In later systems, even though the amount of virtual storage has been increased to 2 GB, the page size has remained 4 KB. This size remains in use today with z/OS.
The remainder of this chapter uses the terms page, frame, and slot in a very specific manner as defined below:
Page
A unit of virtual storage (4 KB or 4096 bytes in MVS).
Frame
A 4 KB unit of real storage that contains data for some virtual address (a page).
Slot
A 4 KB unit of space (on a direct access storage device) that holds the data contents of a page when it is not occupying a frame in real storage.
Virtual Address Translation
The second issue to be considered is the mapping of virtual to real storage addresses. A simple structure would be to have each virtual address be a page number and displacement within the page. The problem with this implementation is that it requires the entire page table to be allocated at all times. In MVS/370, the page table would have been 4096 pages for each active task; in later operating systems the number would have become 128 times greater.
The solution to this problem is to divide the virtual address into fixed segments. In MVS/370, there are 256 segments, each representing 64 KB of the virtual address space. Each segment then is defined by 16 pages. In MVS/XA and later systems, to accommodate the much larger virtual storage, there are 2048 segments, each representing 1 MB of address space. Each segment is divided into 256 pages.
In all systems, the virtual address is a triplet (s,p,d), that is, a segment number, page within the segment, and displacement within the page. The control program then only needs to have page tables for active segments. The page tables define all valid pages belonging to the program. If the page is in real memory, the page table contains the starting address of the page. If the page is not currently in real storage, the page table contains a status bit that indicates this fact. A complete description of the hardware supporting virtual address translation is found in the Principles of Operation.
Figure 2-36 shows how the segment and page tables map virtual addresses to real addresses. In MVS, if we do not consider the extended virtual addressing schemes, a virtual address is 24 bits or 6 hexadecimal digits of the form:
sspddd
Where:
ss
segment number (0 - 255)
p
page number (0 - 15)
ddd
page offset (0 - 4095)
If the 31-bit addressing scheme is used, a virtual storage address is of the form:
sssppddd
Where:
sss
segment number (0 - 2047)
pp
page number (0 - 255)
ddd
page offset (0 - 4095)
Note:
The leftmost bit of the sss field is not used.Starting with MVS/SP 1.3, support was added for real addresses greater than 24 bits in length. This is accomplished by adding two bits to the real addresses in the page tables. The changed support thus provides for 64 MB of real storage. When frames are assigned to pageable storage areas, an available frame from either below or above 16 MB (the maximum 24-bit address) can be used. However, when a page is fixed (usually for I/O to be done), if the page is currently occupying a frame above the 16 MB address, it must be moved to a frame below 16 MB, because the channels only support 24-bit addressing.
Figure 2-25. MVS/370 Virtual to Real Address Translation
PAGE REAL TABLES MEMORY FRAMES ----------- | page 255|--\ ------- |---------| \ |PGM 2| SEGMENT | | \ |-----| TABLE +--->| : | ---->|PGM 1| | | : | |-----| --------------- | | | |PGM 4| | Segment 2047|----+ |---------| |-----| |-------------| | page 0 |--+ |PGM 4| | | ----------- | |-----| | : | | |PGM 3| | : | | |-----| Virt__| : | | |PGM 2| Adrs | | | |-----| | | | +--->|PGM 1| |-------------| | | |-----| | Segment 2 | +--+--->|PGM 1| |-------------| | |-----| | Segment 0 |----+ | |PGM 3| --------------- | ----------- | |-----| | | page 255|-----+ |PGM 2| | |---------| |-----| | | : | -->|PGM 1| | | : | / |-----| +--->|---------| / |PGM 4| | page 1 |--\ / |-----| |---------| X----->|PGM 1| | page 0 |--/ ------- -----------
Page Management Strategies
The final issue is to determine which pages should be in real storage. There are two parts to this question: how should pages be brought into real memory, and which pages should be replaced when more real memory is required? These algorithms are called fetch and replacement strategies.
Several fetch strategies have been used in various systems. Some of these are:
- To load all pages of a program before execution.
- To try to predict which pages will be used and to fetch these pages in advance of their reference.
- To bring in pages as they are needed.
In MVS, a combination of these ideas is used. When a program is initiated, all of its pages are brought into real memory by the program load facility (fetch). This process works in the following manner:
- Virtual storage is allocated for the program with the MVS virtual storage management component (VSM), that is, GETMAIN.
- Assignment of real storage frames to back up the virtual storage is done by the real storage management component (RSM).
- The virtual storage (that is, the range of virtual addresses to be occupied by the program) is page-fixed to prevent page stealing during the loading process.
- The program is now brought into real storage from the load library (a direct access data set such as SYS1.LINKLIB) into its assigned virtual locations.
- After the I/O to read the program into virtual storage is completed, the pages are freed, that is, the normal demand paging process is now allowed to operate on the program just loaded.
At this point, the pages are subject to the normal page replacement process. However, under normal circumstances, some time must pass before this will occur, since all the pages are "recently referenced" at this point.
Once execution begins, pages that have been paged out are brought into real memory as they are referenced. This scheme is called demand paging, that is, pages are brought into memory as they are "demanded."
The idea of bringing in the entire program initially is to avoid forcing the program to establish its initial set of necessary pages by repeatedly demand paging until it can get down to work. It also serves to provide a means of getting the program backed up in auxiliary storage through the existing page replacement facilities, rather than directly allocating Auxiliary Storage Manager (ASM) slots and writing the program to them.
As part of the MVS page replacement process, a queue of free frames is maintained by RSM. This queue, called the Available Frame Queue (AFQ), serves several functions:
- It reduces the time required to resolve a page fault since page fault resolution does not (normally) have to wait on a page-out to complete.
- The length of the AFQ determines how often page replacement processing is done.
- By maintaining a reservoir of free frames, MVS can more easily meet sudden demands for relatively large numbers of pages (such as that of the program load process just described and for the swap-in process.)
When all the frames comprising real memory are allocated and a program requires a page that is not currently in memory, a page must be selected to be written back to auxiliary storage to make room for the new page. The goal of the page replacement process is to select a page for replacement that will not be referenced again for a relatively long time. Historically, several methods have been tried:
- First In, First Out
- Select the oldest page in the system for replacement.
- Working Set
- Only replace pages that a program has not used for a given period of time.
- Least Recently Used
- Replace the page that has not been referenced for the longest period of time.
Modified pages that are selected for replacement must be written to the auxiliary storage to preserve the changes. If a page that is queued to be written is referenced again before the actual I/O occurs, the page is said to be reclaimed. A high reclaim rate indicates a problem since this means the page replacement strategy is not working properly (that is, it is selecting pages to write out that are being quickly and/or frequently rereferenced).
MVS uses a global Least Recently Used (LRU) algorithm. Theory and practice have shown that this method also gives a good approximation to the ideal: to replace a page that is not likely to be referenced again soon. It turns out that the application of this strategy also gives a practical definition of a program's "working set."
The concept of a working set was created to explain a particular problem. Early virtual systems were subject to a phenomenon called "thrashing," which occurred when the page replacement strategy broke down. This happens when replaced pages are immediately referenced (and therefore must immediately be brought back into real storage).
Peter Denning explained thrashing in terms of a program's working set. That is, at any point in time, each program has a minimal number of pages that it requires to run in a virtual environment. When the program's working set is available, all is well. According to the theory, when pages are stolen from a program's working set, paging increases exponentially until the system is doing nothing else. Thus, thrashing is characterized by an excessive amount of CPU time being expended by the RSM and ASM components of the operating system.
The MVS real storage management algorithms do a good job of preventing thrashing from occurring. When it does occur in MVS, it is usually because the system minimum multiprogramming level (MPL) as specified in the Installation Performance Specifications is too large.