Segmented Paging and Buddy System

Segmented Paging 

To take the advantages of best features of paging and segmentation, we combined both that is known as segmented paging. That means, we combined fixed sized pages within variable sized segments. There are some advantages of segmented paging that are memory uses reduced. There is external fragmentation, however, internal fragmentation still possible. The size of page table is limited by segment size, however page table still need to be contiguous. Segment table has only one entry per segment. Each segment has a its own page table. Average size of segments are greater than average page size. The virtual address contains segment number and offset. Each offset contains page number and page offset. In other words, virtual address contains segment number, page number and page offset.




Buddy System

When we used fixed partition schemes that may suffers from segmentation. In other words, usages of space may not be optimal. So, we use a memory allocation technique that divides memory into partitions to try to satisfy a memory request as suitably as possible. This technique is called Buddy system that recursively divide the block equally and test the condition at each time; when it satisfies, allocated the block and get out of the loop. Buddy system is easy to implement and allocates block of correct size. Buddy system is fast and best memory allocation technique. However, there is still suffers from internal fragmentation and it requires every allocation units to be power of two.



Logical address consists segment number and offset in the segmentation. Segments are variable length chunks of a program that corresponds to logical units of the program. Pages are equal sized but segments are variable sized. Mapping from logical address to physical address is done with the help a table which maintains segment number and offset. That means segment table.

Since, segments are variable length so we have limit of a segment that specify length of the segment with the help of base that is a starting address of a segment.




There are some advantages of segmentation over paging: there is no internal fragmentation, but external fragmentation is possible. In paging, there is no external fragmentation but internal fragmentation is possible. Since, segments are variable sized and pages are fixed sized, so average segment size is larger than average page size. Segmentation has efficient translation but it costly. Operating system is responsible for paging, but user/compiler is responsible for segmentation.



Paging is static memory allocation technique in which memory is divided into fixed size pages. Size of pages are the same size and defined by the hardware. Operating system stores and retrieves data from secondary memory using paging technique. When a process arrives in n pages in logical memory then it must have n frames in the physical address.


Operating system maintains job table, page table, and frame table to support paging. Paging can be suffer with internal fragmentation. Processes are used physical memory which is non-contiguous and virtual memory which is used as contiguous manner.  






Logical addresses are consisting page number and size of page that coverts into physical frame number and frame size, frame size is always equals to page size. This address translation takes support from page table.  Page number is an index id of page table.


Every new process creates a separate page table that is stored in main/physical memory. Page table stores frame number and optional valid/invalid status bits. These entries in the page table are called page table entries. Page table can be single level, multilevel, and, inverted page table.


Multilevel Paging

A process has only one page table in single level paging. However, mapping from virtual to physical address is costly or less. Therefore, we use multilevel paging, where page tables are split into two or more levels.

In multilevel paging, the first level has base address of second address, which has base address of third level and so on. The last level has page frame number. Generally, page size is same for all the processes. Since all the page tables are stored in the main memory, so we need more than one memory access to get page frame number and it is one access for each level. This causes translation process is slow which is main disadvantage of multilevel paging.




Paging with TLB ( Translation Look-aside Buffer )


TLB(Translation look-aside buffer) or address translation cache is a hardware cache. TLB is a part of memory management unit. TLB access is much faster than a memory access. In multilevel paging, we access level by level. Since, page table and TLB is different from each other and TLB can cache only a few of page table entries. A fully associative cache allows parallel access of TLB entries.


        52 (1).jpg


During virtual to physical address translation, if page number is found in TLB ( that is hit ) then it’s frame number is accessed from the TLB without memory reference. If the page number is missed in the TLB (i.e., not found), then one extra memory reference is needed to access frame number. Gerenary, a TLB contains page numbers and frame numbers.


Performance of Paging with TLB and without TLB

Assume that TLB hit ratio is ‘h’, TLB access time is ‘c’ and page table access time is ‘m’ which is same as memory access time because all page tables are stored in memory.

Therefore, effective access time in single level paging:

  • Without TLB; effective access time
    = Page table access time + Memory access time = m +m = 2m

  • With TLB; effective access time
    = Hit ratio * (TLB access time + memory access time) + (1 - hit ratio)*(TLB access time + Page table access time + memory access time)
    = h * (c+m) + (1 - h) * (c + m + m) = h * (c+m) + (1 - h) * (c + 2*m)


And, effective access time in multilevel(i.e., n - level) paging, here we need to access page table in ‘n’ times :


  • Without TLB; effective access time
    = (n+1)*m

  • With TLB; effective access time
    = h * (c+m) + (1 - h) * (c + (n+1)*m)


Inverted Page Table

Inverted page table is global structure which contain an entry for each physical frame, but not for each logical page.  The physical page number is not stored, since the in the table corresponds to it. The advantages of the inverted page table are only one inverted page table per system, there is no problem with virtual sparsity etc. However, lookup time is increased and there is no information about the pages that are not in the memory.




The above diagram of inverted page table. There is another type of page table is hash page table, which contains a chain of elements hashing to the same location.