The memory-management scheme that permits the physical-address space of a process to be noncontiguous. Paging avoids the considerable problem of fitting the varying-sized memory chunks onto the backing store.
The paging in its various forms is commonly used in most operating systems.
Frames Vs. Paging
Frame
Physical memory is broken into fixed-sized blocks called frame
Pages
Logical memory is broken into blocks of the same size called pages
When a process is to executed, it’s pages are loaded into any available memory frames from the blocking store. The backing store is divided into fixed-sized blocks that are of the same size as the memory frames.
Paging itself is a form of dynamic relocation. Every logical address is bound by the paging hardware to some physical address. Using paging is similar to using a table of base (or relocation) register, one for each frame of memory.
Page Table
Every address generated by the CPU is divided into two parts: a page numberp and a page offsetd
page number
The page number is used as an index into a page table.
page table contains the base address of each page in physical memory. The base address is combined with the page offset to define the physical memory address that is sent to the memory unit.
page size
The page size (like the frame size) is defined by the hardware. The size of a page is typically a power of 2, varying between 512 bytes and 16 MB per-page, depending on the computer architecture.The high-order m-n bits of a logical address designed the page number, and the n low-order bits designed the page offset.If process size is independent of page size, we expect internal fragmentation to average one-half page per process. This consideration suggests that small page sizes are desirable.However, overhead is involved in each page-table entry, and this overhead is reduced as the size of the pages increases. Also, disk I/O is more efficient when the number of data being transferred is larger.
Generally, page sizes have grown over time as processes, data sets, and main memory have become larger. Today pages typically are between 4KB and 8KB, and some systems support even larger page size.
Each page-table entry is usually 4 bytes long, but that size can vary as well.
overhead: Work or information that provides support – possible critical support – for a computing process but is not an intrinsic part of the operation or data. Overhead often adds to processing time but is generally necessary.
Advantage and disadvantage Advantage no external fragmentation
When we use a paging scheme, we have no external fragmentation:
Any free frame can be allocated to a process that needs it.
Disadvantage have internal fragmentation
We may have some internal fragmentation. Notice that frames are allocated as units. If the memory requirements of a process do not happen to fall on page boundaries, the last frame allocated may not be completely full.
In the worst case, a process would need n pages plus one byte. It would be allocated n+1 frames, resulting in an internal fragmentation of almost an entire frame ( extra need a frame, only add the 1 byte)
The produce from the page to frame
When a process arrives in the system to be executed, its size, expressed in pages, is examined.Each page of the process needs one frame. Thus if the process require n pages, at least n frames must be available in memory. If n frames are available, they are allocated to this arriving process.The fist page of the process is loaded into one of the allocated frames, and the frame number is put in the page table for this process. The next page is loaded into another frame, and its frame number is put into the page table
User aspect and operating system aspect
User aspect
The user program views that memory as one single contiguous space, containing only this one program.
System aspect
System view the actual physical memory. In fact, the user program is scattered throughout physical memory, which also holds other programs.
The difference between the user’s view of memory and the actual physical memory is reconciled by the address-translation hardware. The logical addresses are translated into physical address.
This mapping is hidden from the user and is controlled by the operating system.
The user process by definition is unable to access memory it does not own. It has no way of addressing memory outside of its page table, and the table includes only those pages that the process owns.
The things managed by operating system
Frame table
The frame table has one entry for each physical page frame, indicating whether the latter is free or allocated and, if it is allocated, to which page of which process or processes.
Operation of the user process in user space
If a user makes a system call (to do I/O, for example) and provides an address as a parameter(a buffer for instance), that address must be mapped to produce the correct physical address.The operating system maintains a copy of the page table for each process, just as it maintains a copy of the instruction counter and register contents. This copy is used to translate logical address to physical addresses whenever the operating system must map a logical address to a physical address manually. It is also used by the CPU dispatcher to define the hardware page table when a process is to be allocated the CPU. Paging therefore increases the context-switch time.
The hardware support in paging
Each operating system has its own methods for storing page tables.
A pointer to the page table is stored with the other register values (like the instruction counter) in the process control block. When the dispatcher is told to start a process, it must reload the user registers and define the correct hardware page-table values from the stored user page table.
The different way storing the page-table
A set of dedicated register
A the simplest case, the page table is implemented as a set of dedicated registers.
These registers should be built with very high-speed logic to make the paging-address translation efficient. Every access to memory must go through the paging map, so efficiency is a major consideration.
The CPU dispatcher reload these registers, just as it reloads the other registers. Instructions to load or modify the page-table register are, of course, privileged, so that only the operating system can change the memory map.
This scheme only satisfy the the page table is small. When the page table to be very large (for example 1 million entries), the use of fast registers to implement the page table is not feasible.
A page-table base register (PTBR)
The page table is kept in main memory, and a page-table base register (PTBR) points to the page table. Changing page table requires changing only this one register, substantially reducing context-switch time.
The problem with this approach is the time required to access a user memory location.
First, finding the page-table with PTBR need to access a user memory location
Second, accessing the desired place in memory also need to access a user memory locations
Translation look-aside buffer (TLB)
To use a special, small, fast-lookup hardware cache, called translation look-aside buffer (TLB).
The TLB is associative, high-speed memory.
Each entry in the TLB consists of two parts: a key( or tag) and a value.
When the associative memory is presented with an item, it is compared with all keys simultaneously.
If the item is found:
The corresponding value field is returned. The search is fast; the hardware, however, is expensive
Typically, the number of entries in a TLB is small, often numbering between 64 and 1,024
The mechanism of the TLBThe TLB contains only a few of the page-table entries.
When a logical address is generated by the CPU, its page number is presented to the TLB.
If the page number is found
its frame number is immediately available and is used to access memory. The whole task is very fast.
If the page number is not in the TLB
known as a TLB miss
A memory reference to the page table must be made. When the frame number is obtained, we can use it to access memory. In addition, we add the page number and frame number to the TLB, so that they will be found quickly on the next reference.
If the TL is already full of entries
The operating system must select one for replacement.
Replacement policies ranger from leat recently used (LRU) to random.
Furthermore, some TLBs allow entries to be wired down, meaning that they cannot be removed from the TLB, TLB entries for kernel code are often wired down.
The protection method of the TLB
support address-space identifiers (ASIDs)
Some TLBs store address-space identifiers (ASIDs) in each entry of the TLB. An ASID uniquely identifies each process and is used to provide address space protection for that process.
When the TLB attempts to resolve virtual page numbers, it ensures the ASID for the currently running process matches the ASID associated with the virtual page.
If the ASIDs do not match, they are treated as a TLB miss.
In addition to providing address-space protection, an ASID allows the TLB to contain entries for several different processes simultaneously. not support ASIDs
every time a new page table is selected (for instace, each context switch), the TLB must be flushed (or erased) to ensure that the next executing process does not use the wrong translation information.
Otherwise, there could be old entries in the TLB that contain vaild virtual addresses but have incorrect or invalid physical addresses left over from the previous process.
The percentage of times that a particular page number is found in the TLB is called the hit ratio.
Operating System – Page I
yinquanThe memory-management scheme that permits the physical-address space of a process to be noncontiguous. Paging avoids the considerable problem of fitting the varying-sized memory chunks onto the backing store.
Physical memory is broken into fixed-sized blocks called frame
Logical memory is broken into blocks of the same size called pages
When a process is to executed, it’s pages are loaded into any available memory frames from the blocking store. The backing store is divided into fixed-sized blocks that are of the same size as the memory frames.
Every address generated by the CPU is divided into two parts: a page number
pand a page offsetdThe page number is used as an index into a page table.
The page size (like the frame size) is defined by the hardware. The size of a page is typically a power of 2, varying between 512 bytes and 16 MB per-page, depending on the computer architecture.The high-order m-n bits of a logical address designed the page number, and the n low-order bits designed the page offset.If process size is independent of page size, we expect internal fragmentation to average one-half page per process. This consideration suggests that small page sizes are desirable.However, overhead is involved in each page-table entry, and this overhead is reduced as the size of the pages increases. Also, disk I/O is more efficient when the number of data being transferred is larger.
Generally, page sizes have grown over time as processes, data sets, and main memory have become larger. Today pages typically are between 4KB and 8KB, and some systems support even larger page size.
Each page-table entry is usually 4 bytes long, but that size can vary as well.
Advantage
no external fragmentation
When we use a paging scheme, we have no external fragmentation:
Any free frame can be allocated to a process that needs it.
Disadvantage
have internal fragmentation
We may have some internal fragmentation. Notice that frames are allocated as units. If the memory requirements of a process do not happen to fall on page boundaries, the last frame allocated may not be completely full.
In the worst case, a process would need n pages plus one byte. It would be allocated n+1 frames, resulting in an internal fragmentation of almost an entire frame ( extra need a frame, only add the 1 byte)
The produce from the page to frame
When a process arrives in the system to be executed, its size, expressed in pages, is examined.Each page of the process needs one frame. Thus if the process require n pages, at least n frames must be available in memory. If n frames are available, they are allocated to this arriving process.The fist page of the process is loaded into one of the allocated frames, and the frame number is put in the page table for this process. The next page is loaded into another frame, and its frame number is put into the page table
User aspect and operating system aspect
User aspect
The user program views that memory as one single contiguous space, containing only this one program.
System aspect
System view the actual physical memory. In fact, the user program is scattered throughout physical memory, which also holds other programs.
The difference between the user’s view of memory and the actual physical memory is reconciled by the address-translation hardware. The logical addresses are translated into physical address.
This mapping is hidden from the user and is controlled by the operating system.
The frame table has one entry for each physical page frame, indicating whether the latter is free or allocated and, if it is allocated, to which page of which process or processes.
If a user makes a system call (to do I/O, for example) and provides an address as a parameter(a buffer for instance), that address must be mapped to produce the correct physical address.The operating system maintains a copy of the page table for each process, just as it maintains a copy of the instruction counter and register contents. This copy is used to translate logical address to physical addresses whenever the operating system must map a logical address to a physical address manually. It is also used by the CPU dispatcher to define the hardware page table when a process is to be allocated the CPU. Paging therefore increases the context-switch time.
Each operating system has its own methods for storing page tables.
A pointer to the page table is stored with the other register values (like the instruction counter) in the process control block. When the dispatcher is told to start a process, it must reload the user registers and define the correct hardware page-table values from the stored user page table.
A set of dedicated register
A the simplest case, the page table is implemented as a set of dedicated registers.
These registers should be built with very high-speed logic to make the paging-address translation efficient. Every access to memory must go through the paging map, so efficiency is a major consideration.
The CPU dispatcher reload these registers, just as it reloads the other registers. Instructions to load or modify the page-table register are, of course, privileged, so that only the operating system can change the memory map.
A page-table base register (PTBR)
The page table is kept in main memory, and a page-table base register (PTBR) points to the page table. Changing page table requires changing only this one register, substantially reducing context-switch time.
Translation look-aside buffer (TLB)
To use a special, small, fast-lookup hardware cache, called translation look-aside buffer (TLB).
The TLB is associative, high-speed memory.
Each entry in the TLB consists of two parts: a key( or tag) and a value.
When the associative memory is presented with an item, it is compared with all keys simultaneously.
The corresponding value field is returned. The search is fast; the hardware, however, is expensive
When a logical address is generated by the CPU, its page number is presented to the TLB.
If the page number is found
its frame number is immediately available and is used to access memory. The whole task is very fast.
If the page number is not in the TLB
known as a TLB miss
A memory reference to the page table must be made. When the frame number is obtained, we can use it to access memory. In addition, we add the page number and frame number to the TLB, so that they will be found quickly on the next reference.
If the TL is already full of entries
The operating system must select one for replacement.
Replacement policies ranger from leat recently used (LRU) to random.
Furthermore, some TLBs allow entries to be wired down, meaning that they cannot be removed from the TLB, TLB entries for kernel code are often wired down.
The protection method of the TLB
support address-space identifiers (ASIDs)
Some TLBs store address-space identifiers (ASIDs) in each entry of the TLB. An ASID uniquely identifies each process and is used to provide address space protection for that process.
When the TLB attempts to resolve virtual page numbers, it ensures the ASID for the currently running process matches the ASID associated with the virtual page.
If the ASIDs do not match, they are treated as a TLB miss.
In addition to providing address-space protection, an ASID allows the TLB to contain entries for several different processes simultaneously.
not support ASIDs
every time a new page table is selected (for instace, each context switch), the TLB must be flushed (or erased) to ensure that the next executing process does not use the wrong translation information.
Otherwise, there could be old entries in the TLB that contain vaild virtual addresses but have incorrect or invalid physical addresses left over from the previous process.
You might also like
Operating System – Page III
Structure of the Page Table The most common techniques for structuring the page table Hierarchical Paging...
Operating System – Page II
Protection Memory protection in a paged environment is accomplished by protection bits that are associated...
Operating System MM IV
In the contiguous memory allocation,each process is contained in a single continuous section of memory....