Department of Computer Science Course: CS 3725

Segmented memory management

In a segmented memory management system the blocks to be replaced in main memory are potentially of unequal length and correspond to program and data ``segments.'' A program segment might be, for example, a subroutine or procedure. A data segment might be a data structure or an array. In both cases, segments correspond to logical blocks of code or data. Segments, then, are ``atomic,'' in the sense that either the whole segment should be in main memory, or none of the segment should be there. The segments may be placed anywhere in main memory, but the instructions or data in one segment should be contiguous, as shown in Figure .

  
Figure: A segmented memory organization

Using segmented memory management, the memory controller needs to know where in physical memory is the start and the end of each segment. When segments are replaced, a single segment can only be replaced by a segment of the same size, or by a smaller segment. After a time this results in a ``memory fragmentation'', with many small segments residing in memory, having small gaps between them. Because the probability that two adjacent segments can be replaced simultaneously is quite low, large segments may not get a chance to be placed in memory very often. In systems with segmented memory management, segments are often ``pushed together'' occasionally to limit the amount of fragmentation and allow large segments to be loaded.

This organization appears to be efficient because an entire block of code is available to the processor. Also, it is easy for two processes to share the same code in a segmented memory system; if the same procedure is used by two processes concurrently, there need only be a single copy of the code segment in memory. (Each process would maintain its own, distinct data segment for the code to access, however.)

Segmented memory management is not as popular as paged memory management, however. In fact, most processors which presently claim to support segmented memory management actually support a hybrid of paged and segmented memory management, where the segments consist of multiples of fixed size blocks.

Paged memory management:

Paged memory management is really a special case of segmented memory management. In the case of paged memory management,

• all of the segments are exactly the same size (typically 256 bytes to 16 K bytes)
• virtual ``pages'' in auxiliary storage (disk) are mapped into fixed page-sized blocks of main memory with predetermined page boundaries.
• the pages do not necessarily correspond to complete functional blocks or data elements, as is the case with segmented memory management.

The pages are not necessarily stored in contiguous memory locations, and therefore every time a memory reference occurs to a page which is not the page previously referred to, the physical address of the new page in main memory must be determined. In fact, most paged memory management systems (and segmented memory management systems as well) maintain a ``page translation table'' using associative memory to allow a fast determination of the physical address in main memory corresponding to a particular virtual address. Normally, if the required page is not found in the main memory (i.e, a ``page fault'' occurs) then the CPU is interrupted, the required page is requested from the disk controller, and execution is started on another process.

The following is an example of a paged memory management configuration using a fully associative page translation table:

Consider a computer system which has 16 M bytes ( bytes) of main memory, and a virtual memory space of bytes. Figure  shows a sketch of the page translation table required to manage all of main memory if the page size is 4K bytes. Note that the associative memory is 20 bits wide ( 32 bits - 12 bits, the virtual address size -- the page size). Also to manage 16 M bytes of memory with a page size of 4 K bytes, a total of associative memory locations are required.

  
Figure: Paged memory management address translation

Some other attributes are usually included in a page translation table, s well, by adding extra fields to the table. For example, pages or segments may be characterized as read only, read-write, etc. As well, it is common to include information about access privileges, to help ensure that one program does not inadvertently corrupt data for another program. It is also usual to have a bit )the ``dirty'' bit) which indicates whether or not a page has been written to, so that the page will be written back onto the disk if a memory write has occurred into that page. (This is done only when the page is ``swapped'', because disk access times are too long to permit a ``write-through'' policy like cache memory.) Also, since associative memory is very expensive, it is not usual to map all of main memory using associative memory; it is more usual to have a small amount of associative memory which contains the physical addresses of recently accessed pages, and maintain a ``virtual address translation table'' in main memory for the remaining pages in physical memory. A virtual to physical address translation can normally be done within one memory cycle if the virtual address is contained in the associative memory; if the address must be recovered from the ``virtual address translation table'' in main memory, at least one more memory cycle must be used to retrieve the physical address from main memory.

There is a kind of trade-off between the page size for a system and the size of the page translation table (PTT). If a processor has a small page size, then the PTT must be quite large to map all of the virtual memory space. For example, if a processor has a 32 bit virtual memory address, and a page size of 512 bytes ( bytes), then there are possible page table entries. If the page size is increased to 4 Kbytes ( bytes), then the PTT requires ``only'' , or 1 M page table entries. These large page tables will normally not be very full, since the number of entries is limited to the amount of physical memory available. One way these large, sparse PTT's are managed is by mapping the PTT itself into virtual memory. (Of course, the pages which map the virtual PTT must not be mapped out of the physical memory!)

Note that both paged and segmented memory management provide the users of a computer system with all the advantages of a large virtual address space. The principal advantage of the paged memory management system over the segmented memory management system is that the memory controller required to implement a paged memory management system is considerably simpler. Also, the paged memory management does not suffer from fragmentation in the same way as segmented memory management. Another kind of fragmentation does occur, however. A whole page is swapped in or out of memory, even if it is not full of data or instructions. Here the fragmentation is within a page, and it does not persist in the main memory when new pages are swapped in.

One problem found in virtual memory systems, particularly paged memory systems, is that when there are a large number of processes executing ``simultaneously'' as in a multiuser system, the main memory may contain only a few pages for each process, and all processes may have only enough code and data in main memory to execute for a very short time before a page fault occurs. This situation, often called ``thrashing,'' severely degrades the throughput of the processor because it actually must spend time waiting for information to be read from or written to the disk.