Paging
When paging ( cf. Engl. Seite " memory page " ) or German tile management refers to the method of memory management by Page Addressing by operating systems.
Occasionally, the term is used synonymously with paging the entire virtual memory management. This usage is imprecise, however, because the paging only one - makes aspect of virtual memory management - albeit central.
- 2.1 Thrashing and working set
Operation
When paging logical addresses and physical addresses are distinguished. The logical address space describes the organization of the main memory from the program point of view. The physical address space is given by the memory actually available. The translation of logical to physical addresses is done by the memory management unit that also for the - is responsible Memory protection - independent of the paging. Also not part of the paging is another address translation, which takes place in the memory controller and for sharing the memory banks and pop up the memory from external devices ( graphics memory, memory-mapped I / O, etc. ) is responsible.
When paging, the logical address space is divided into equal-sized pieces, which are called pages (English " pages" ). And the physical address space is divided in such a manner. This is called the individual pieces side frames or tiles (English " ( page ) frames" ). One side and the associated side frame usually have the same size; Alternative techniques to implement paging in a manner that the page size corresponds to an integer multiple of the size of the side frames - also in this case, it is not thereby external fragmentation of the main memory. Pages and page frames to be able to assign to each other, a page table is used. There is a separate page table for each process. The logical address space is contiguous, as a rule, while in the physical address space, the logically adjacent pages can be stored in widely separated side frame. The order of the side frame is arbitrary.
Page fault
Sides of the logical address space can be mapped to any physical page frame. Most sure there is a special flag in the page table or a particular page frame number is reserved for this purpose. Once a program is accessing such a page, the processor is automatically a " page fault " is triggered, the treatment is performed by the operating system. There are two general causes:
Address calculation when paging
In the terminology of the above graph corresponds to a logical memory address of the virtual address. The physical memory is called real address here. It extracts the graphics that the physical memory address calculated very easily into two parts: The first part is taken from the page table, the second part of the virtual address. It consists of two binary numbers. If these are concatenated, the result is a new binary number, which is precisely the physical memory address. Such calculations are performed by the memory management unit.
A buffer may be provided here hold a portion of the address mapping, so that the access time can be optimized. This buffer is called the Translation Lookaside Buffer.
Simple fictitious example
The address length in this example is 16 bits, the lower 8 bits of the offset and the upper 8 bits of the page numbers.
To be translated addresses:
Real example: IA32 architecture
Build the page tables
- P - present. Page is available in RAM, if bit is set to 1
- R / W - Read / write. Write access allowed only if bit is set to 1
- U / S - user / supervisor. Ring -3 code can only access the page if bit is set to 1
- PWT and PCD - is used for cache control
- A - Accessed. Is automatically set by the CPU as soon as the page is being accessed
- D - dirty. Is automatically set by the CPU, once it has been written in the page
- PAT - ...
- G - global. Features a global memory page
32-bit paging
Most architectures use a multi-level paging to small to hold the page tables. The IA32 architecture originally used a two-step paging. The 32 bits of the linear address are hereby divided as follows:
The page directory and page table, each consisting of 1024 entries of 4 bytes each and therefore demonstrate exactly one memory page.
( Etc. eg framebuffer for graphics cards ) and to reduce the administrative burden of memory management of the operating system to optimize large, contiguous memory areas, also support CPUs from the Pentium ( officially documented Pentium Pro) 4 MiB large pages. This feature is called Page Size Extension ( PSE). This marked a special bit in the corresponding page directory entry, that the second stage in the paging should be avoided for this address range. To give the bits 21-0 of the logical address directly the offset in the 4 MiB large memory page.
Physical Address Extension
From the Pentium Pro, it is possible to address (64 GiB =) physical memory up to 236 bytes. This technique is called Physical Address Extension. For the paging is extended to a third stage. The top two bits of the linear address now select one of four entries of the so-called page directory pointer table (in short: PDPT ) from.
The entries in the tables have been expanded to 8 bytes, but each of the tables contains only 512 entries, so that the total size is again at 4 KiB:
Even with PAE, it is possible to deactivate the last address translation stage of the paging file. The bits 20 to 0 of the logical address then form directly offset a 2 MiB large memory page.
64 -bit mode
With the introduction of 64 -bit mode, the AMD Athlon 64 this principle was applied again. The paging was about a fourth stage extended ( Page Map Level 4, short PML4 ) and PDPT was increased from 4 to 512 entries, so it is the same size as the following page tables.
In addition to the 32- bit mode available 4 KiB and MiB large 2 pages are in GiB 64 -bit mode also one large pages possible. In this reference the lower 22 bits of an entry in the Page Directory Pointer Table directly to the start address of a 1 - GiB - page:
Loading of pages into memory ( demand paging )
As already mentioned above, the paging mechanism is also utilized to the virtual memory management, so that the logical address space may be larger than the physical memory. The so-called demand paging must not be the same load at startup all parts of a program. Once the process is accessing a non- loaded page, the missing part of the file is loaded by the operating system.
It is also possible on many operating systems to have any file show the logical address space. When you create such a mapping only the file permissions are checked and reserved the required area in the logical address space of the process by the operating system. Only when the process accesses to this memory area ( = on demand), the relevant parts of the file will be loaded and displayed in the logical address space.
Thrashing and working set
However, this technique has its limits of the paging. If too many page faults occur in a computer system, such as a program often random accesses to different memory areas, the system is busy reloading and swapping pages mainly. The processor remains most of the time in the waiting state, the available computing power is significantly reduced. This condition is also called thrashing (English literally, threshing ) refers.
To avoid thrashing, memory in relation to the swap space must not be too small. At any given time should be at least one of the processes that has to process the system can be processed by the processor, that is: Its data or program instructions that are currently being processed, are located in memory. In this operating state, the processor does not wait for the loading of pages, but works in a process, while other processes are loaded in parallel sides. In addition, programs should access as locally as possible to their data and avoid random accesses to constantly changing memory pages.
The decisive factors are the following sizes:
- T: the time it takes for the processor to access a memory location
- T: the time required to reload a side
- S: The proportion of sites located in memory in relation to the total number of required for program execution pages ( 0
- P (s): the probability of a page fault, depending on S
Thrashing thus avoids must P (S ) ≤ t / T to be. The minimum fraction w of pages, which must be located in memory is determined by the equation
- P (W) = t / T.
He is referred to as the working set ( amount of work ).
Had the requests evenly to the memory, so would be p ( s) = 1 - p Fortunately, the memory accesses, however, occur more frequently locally: In most cases, a program step follows the next. And the data are usually handled in rows, for example, when arithmetic operations are applied to all the tables. Therefore, the probability is very high that the next program step and the next required data element on the same side as the currently processed step and the currently processed element.
On the other hand, the ratio T / t typically very large: RAM is more than 100 times as fast as disk space.
Experimental measurements and calculations have been carried out in the 1960's yield under these conditions for w has a value of not substantially less than 0.5. This means that the swap space must be greater than that of memory.
In practice, for example, on UNIX operating systems for most applications, a size of the swap space from two to three times the memory recommended ( depending on whether the particular system swap space in addition to the memory or the memory managed as a proper subset of paged ).
Page replacement strategies
The performance of a paging system is dependent on which pages in the main memory is repressed when loading new pages. If one displaces pages that are used little later again, then one generates effort for additional reload processes.
The following methods are known and studied: