OS2: Memory Management-Unit 3: Non-Contiguous Allocation

Paging

This is a memory-management scheme that permits the physical-address space of a process to be contiguous. Paging avoids the considerable problem of fitting the varying-sized memory chunks onto the backing store from which most of the previous memory- management schemes suffered.

Paging permits the logical address space to be mapped to a number of equal size blocks called page frames, by dividing the logical address space into pages of the same size. When a process is to be executed, its pages are loaded into any available memory frames from the backing store. The backing store is divided into fixed-sized blocks that are of the same as the memory frames.

The hardware support for paging is as illustrated in Figure 3.1 below. 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 based 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.

Figure 3.1: Paging Hardware

The paging model of memory is shown in Figure 3.2 below.

The page size, like the frame size, is defined by the hardware. The size of a page is of power 2 and it varies between 512 bytes and 16 MB per page, depending on the computer architecture.

Figure 3.2: Paging model of logical and physical memory

3.1.1 Translating the memory addresses

To minimize the performance penalty of address translation, most modern CPUs include an on-chip memory management unit (MMU), and maintain a table of recently used virtual-to- physical translations, called a Translation Lookaside Buffer (TLB). Addresses with entries

in the TLB require no additional memory references (and therefore time) to translate.

However, the TLB can only maintain a fixed number of mappings between virtual and physical addresses; when the needed translation is not resident in the TLB, action will have to be taken to load it in.

190

On some processors, this is performed entirely in hardware. The MMU has to do additional memory references to load the required translations from the translation tables, but no other action is needed. In other processors, assistance from the operating system is needed. An exception is raised, and the operating system handles this exception by replacing one of the entries in the TLB with an entry from the primary translation table, and the instruction which made the original memory reference is restarted.

3.1.2 Protected memory

Hardware that supports virtual memory almost always supports memory protection mechanisms as well. The MMU may have the ability to vary its operation according to the type of memory reference (for read, write or execution), as well as the privilege mode of the

CPU at the time the memory reference was made. This allows the operating system to protect its own code and data (such as the translation tables used for virtual memory) from corruption by an erroneous application program and to protect application programs from each other and (to some extent) from themselves (e.g. by preventing writes to areas of memory that contain code).

3.1.3 Issues with Paging

As you may have not iced, paging is a form of dynamic relocation. Every logical address is bounded by the paging hardware to some physical address. Using paging is similar to using a table of base/relocation registers, one for each frame.

When you use a paging scheme, you have no external fragmentation. However, internal fragmentation may occur since frames are allocated as units.

3.2

Segmentation

Users do not think of memory as a linear array of bytes with some containing instructions and other containing data. Instead users prefer to view memory as a collection of variable- sized segments with no necessary ordering among segments. See Figure 3.3 below.

User’s view of a program

Segmentation is a memory-management scheme that supports this user view of memory. A logical-address space is a collection of segments. Each segment has a name and a length.

The addresses specify both segment name and the offset within the segment. The user, therefore, specifies each address by two quantities: a segment name and an offset.

For implementation simplicity, segments are numbered and are referred to by a segment number rather than by a segment name. Therefore, a logical address consists of a two tuple: <segment-number, offset>.

Normally the user program is compiled and the compiler automatically constructs segments that reflects the input program.

3.2.1 Hardware Implementation

Although the user can now refer to objects in the program by a two-dimensional address, the actual physical memory is still a one-dimensional sequence of bytes. Hence, we must define an implementation to map two-dimensional user-defined addresses into one-dimensional physical addresses. This mapping is affected by segment table. Each entry of the segment table has 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.

The use of a segment table is as illustrated in Figure 3.4 below. A logical address consists of two parts: a segment number, s and an offset into that segment, d. The segment number is used as an index into the segment table. The offset d of the logical address must be between

Figure 3.4:

Segmentation hardware

0 and the segment limit. If it is not, we trap to the operating system (logical addressing attempt beyond end of segment). If this offset is legal, it is added to the segment base to produce the address in physical memory of the desired byte. The segment table is therefore essentially an array of base-limit register pairs.

3.2.2. Advantages and Problems of Segmentation

Advantages:

• Operating system may allow segments to grow and shrunk dynamically with unchanging addressing
• Protection on segment level of related data
• Sharing on segment level is easy.

Problems:

• Contiguous allocation of memory with all its attendant problems as you learnt from unit 2 of this module
• May cause external fragmentation
• Dynamic shrinking/growing is expensive. The operating system may have to move things around.

3.3

Segmentation with Paging

As you have learnt so far in this unit, both paging and segmentation have advantages and disadvantages. But the problems/disadvantages of these two can be solved by paging of the segments. In this combined technique, each segment has its own page table. Segment table entries now refer to base of the per segment page table and the offset within the segment is subdivided into page number and offset within page and used as earlier discussed.

This combination is the one used in the Intel 386 architecture.

4.0

Conclusion

In this concluding unit of this module and the course general, you have been further exposed to some memory-management algorithms. You should please note that the topics treated are not exhaustive. You therefore advised to refer to the references/further Reading sited at the end of each unit for more in-depth knowledge of the subject matter.