Loading....
Coupon Accepted Successfully!

 

Memory management techniques

 
Various memory management techniques exist such as partitioning memory into various fixed sized partitions or dynamic memory allocation. Also, overlays and swapping is also used as part of memory management. But the two most important and widely used strategies are paging and segmentation.

Paging

Paging is a memory management scheme that permits the physical address space of a process to be non-contiguous. The physical memory is broken into fixed-sized blocks called frames. Logical memory is also broken into blocks of the same size called pages. When a process is to be executed, its pages are loaded into any available memory frames from the backing store. The backing store, swap space on disk, 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 (p) and a page offset (d). The page number is used as an index into a page table. The page table contains the base address of each page in physical memory. This base address is combined with the page offset to define the physical memory address that is sent to the memory unit.
The page size (like the frame size) is defined by the hardware. The size of a page is typically a power of 2. The selection of a power of 2 as a page size makes the translation of a logical address into a page number and page offset particularly easy. If the size of logical address space is 2m and a page size is 2n addressing units (bytes or words), then the high-order m - n bits of a logical address designate the page number, and the n loworder bits designate the page offset. Thus, the logical address is as follows:
 
Page number page offset
m – n n
Example – consider a memory unit of 32 bytes and page size of 4 bytes. Thus memory is divided into 8 frames. Now a process has size of 4 pages. The page table for this process is
CPU
f
p d f d
p d
Logical memory physical memory page table
0
1
2
3
According to page table page 0 is mapped to frame 1, page 1 to frame 4 and so on.
 
Now with increase in memory size, the size of page table also increases considerably. Having such large page tables, maintaining them for each page is quite difficult. Thus various kinds of page tables have come up according to the needs. Some of them are hierarchical paging, where instead of one, 2 or more page tables exist.
 
Outer page table points to inner page table, which finally has the frame address. Then there are hashed page tables, inverted page tables.
 
Although paging solves the problem of external fragmentation but the problem of internal fragmentation still exists as the size of the program may not be proportional to the page size. Example – if the page size if 4 bytes and the size of the process is 5 bytes, then 2 pages are needed to run this process. The second page having 3 bytes of memory unused causing internal fragmentation.

Translation Lookaside Buffer

Each operating system has its own methods for storing page tables. Most allocate a page table for each process and store a pointer to it in the process control block. The hardware implementation of this page table can be done in several ways. In the simplest case, the page table is implemented as a set of dedicated registers. The use of registers for the page table is satisfactory if the page table is reasonably small (for example, 256 entries). Most contemporary computers, however, allow the page table to be very large (for example, 1million entries). For these machines, the use of fast registers to implement the page table is not feasible. Rather, the page table is kept in main memory, and a page-table base register (PTBR) points to the page table. The problem with this approach is the time required to access a user memory location.
 
Page 0
Page 1
Page 2
Page 3
Page 0
Page 2
Page 1
Page 3
1
4
3
7
The standard solution to this problem is to use a special, small, fast-lookup hardware cache, variously called associative registers or translation look-aside buffers (TLBs). A set of associative registers is built of especially high-speed memory. Each register consists of two parts: a key and a value. When the associative registers are presented with an item, it is compared with all keys simultaneously. If the item is found, the corresponding value field is output. The search is fast; the hardware, however, is expensive. Typically, the number of entries in a TLB varies between 8 and 2048.
 
The percentage of times that a page number is found in the associative registers is called the hit ratio. An 80-percent hit ratio means that we find the desired page number in the associative registers 80 percent of the time. If it takes 20 nanoseconds to search the associative registers and 100 nanoseconds to access memory, then a mapped memory access takes 120 nanoseconds when the page number is in the associative registers. If we fail to find the page number in the associative registers (20 nanoseconds), then we must first access memory for the page table and frame number (100 nanoseconds), and then access the desired byte in memory (100 nanoseconds), for a total of 220 nanoseconds. To find the effective memory-access time, we must weigh each case by its probability:
Effective access time = 0.80 x 120 + 0.20 x 220 = 140 nanoseconds.

Segmentation

Even though the memory is like a linear array of bytes, some containing instructions and some data, users prefer to view it as a collection of variable sized segments with no necessary ordering among them. Segmentation is a memory-management scheme that supports this user view of memory. In this scheme, logical address space is a collection of segments. Each segment has a name and a length. The addresses specify both the segment name and the offset within the segment.
 
For simplicity of implementation, segments are numbered and are referred to by a segment number, rather than by a segment name. Thus, a logical address consists of a two tuple:
Although the user can now refer to objects in the program by a two-dimensional address, the actual physical memory is still, of course, a one-dimensional sequence of bytes. Thus, we must define an implementation to map two dimensional user-defined addresses into one-dimensional physical addresses. This mapping is affected by a segment table. Each entry of the segment table has a segment base and a segment limit. The segment base contains the starting physical address where the segment resides in memory, whereas the segment limit specifies the length of the segment.
0
1
2
3
4
Segment table




Test Your Skills Now!
Take a Quiz now
Reviewer Name