21 Memory Management –Segmentation
Mary Anitha Rajam
24.1 Introduction
Paging divides a process into equal sized blocks called pages. Segmentation divides a process into segments which is similar to how users view a process. This module explains what segmentation is, how address translation is done when segmentation is the memory management technique, how sharing and protection of segments can be achieved and how segmentation and paging can be combined.
24.2 Segmentation
In paging, the user’s view of memory and actual physical memory are different. Users do not view the memory as a linear array of bytes. Users view the memory as a set of subroutines, procedures etc. In paging, the process is treated as just a sequence of bytes. It is not the case in segmentation. Segmentation is a memory-management scheme that supports user’s view of memory.
Any program is a collection of segments. A segment is a logical unit such as: main program, procedures, functions, objects, local variables, global variables, stack, symbol table, arrays etc. as shown in Figure 24.1. Each of these units is referred to by a name. Each of these segments is variable sized. The length of the segment is based on the purpose of the segment in the program
Fig.24.1 User’s view of a program (Source: [1])
24.3 Segmentation Architecture
The logical address-space is a collection of segments. Each segment has a name and a length. The logical address consists of a two tuple: <segment-number, offset>. That is, the logical address specifies both the segment number and the offset within the segment. Figure 24.2 shows a logical view of segments. There are 4 segments in the user space, which are of different sizes. Each of the segments can be placed at different places in the physical memory.
Fig. 24.2 Logical View of Segmentation (Source: [1])
Each segment can be placed anywhere in the physical memory. The information about where each segment is placed in the physical memory is stored in a table called the segment table. Each segment table entry has a segment base, which contains the starting physical address where the segments reside in memory and a segment limit which specifies the length of the segment. Each process has only one segment table and the number of entries in the segment table depends on the number of segments in that process.
Figure 24.3 shows an example of how mapping from logical address to physical address is done. There are five segments in the logical address space, numbered as 0, 1, 2, 3 and 4. Segment 0 is placed in the physical memory at a location starting at address 1400 and the length of the segment is 1000 bytes. Hence the first entry in the segment table, corresponding to segment 0, has a base value as 1400 and length value as 1000. Similarly, the other entries in the segment table are updated based on the location where the corresponding segments are placed in the main memory (physical memory).
Even though it is possible to refer to the process as segments in the user space, it is still a sequence of the bytes while stored in the physical memory. Hence, it is necessary to map the logical address to physical address. Now, we will learn how the mapping is done from the logical address to the physical address.
Fig. 24.3 Example of Segmentation (Source: [1])
Fig. 24.4 Segmentation Hardware (Source: [1])
As we have seen, the logical address is a segment number, offset pair. Figure 24.4 shows the segmentation hardware. The segment number is used as an index into the segment table to get the corresponding entry in the segment table. The limit value in the segment table entry is compared with the offset in the logical address. The offset should be less than the limit of the segment. This is to check if the given logical address is within the limits of the corresponding segment. If the offset is not less, then it is an illegal address and a trap is given to the operating system. If the offset is less, then the base address of the segment is taken from the segment table entry and is added with the offset in the logical address to get the corresponding physical address.
The segment table can also be stored in the main memory. Hence to find the location of the segment table in memory, a segment-table base register (STBR) is used which points to the segment table’s location in memory. A Segment-table length register (STLR) is also used which indicates the number of segments used by a process; segment number s is legal if s < STLR.
24.4 Protection with Segments
As we have seen, segments represent semantically defined portion of the program. For example, segments that represent the text region of a process, segments that has the stack, segments that have the data region and so on. Hence, different segments can be assigned different protection rights. For example, segments with only instructions (text region) can be marked as read-only or execute-only. With each entry in the segment table, bits for read/write/execute privileges can be associated. The memory mapping hardware will check and prevent illegal access to memory, such as attempts to write into a read-only segment, or to write into an execute-only segment and so on. Common programming errors can detected here without causing damage to the hardware.
24.5 Sharing of Segments
Sharing of segments is another advantage of segmentation. When entries in the segment tables of two different processes point to the same physical location, the segment is shared. Common subroutines can be shared among many users when they are read-only and sharable.
Figure 24.5 shows an example of how segments can be shared. Consider a text editor program that is shared by many users. The text region (instructions) of the program may comprise of many segments and these segments can be shared. The data region, which is local to each user cannot be shared. As seen in Figure 24.5, the segment table entries corresponding to the data part alone is different for both the processes.
Fig. 24.5 Sharing of segments in segmented memory system (Source: [1])
24.6 Fragmentation
With segmentation, external fragmentation is possible. It may be possible that all blocks of free memory are unable to accommodate a segment individually, but can accommodate if combined together. Hence, the process should wait until more memory becomes available or until compaction creates a big hole. The effect of fragmentation depends on the average segment size. At one extreme, a full process can be put in one segment. This will reduce to a variable-sized partition memory management scheme. At the other extreme, each byte is treated as a segment. But this will result in a large segment table. Thus if the average segment size is small, external fragmentation is also small.
Paging does not suffer from external fragmentation. Hence, to reduce the effect of fragmentation in segmentation memory management scheme, the segments are paged. That is, the segments are divided into pages.
24.7 Segmentation with Paging – Intel 386
Paging and segmentation have their own advantages and disadvantages. Hence, if these two methods are combined, it is possible to improve on each. In this section, we will learn how this combination of paging and segmentation is used in the Intel 80386 architecture.
Any process is divided into segments (Figure 24.6). The maximum number of segments per process is 16 KB. Figure 24.6 shows the first segment (S1), second segment (S2) and the 16KBth segment (S16KB). Each segment is 4 gigabytes. Segments are then divided into pages to avoid external fragmentation. The page size is 4 KB as shown in Figure 24.7.
Fig. 24.6 Process with segments
Fig. 24.7 Segment divided into pages
The logical address space is divided into two partitions: Up to 8KB segments that are private to the process and up to 8KB segments that are shared among all the processes. Information about the first partition (private segments) is kept in the local descriptor table (LDT). Information about the second partition is kept in the global descriptor table (GDT). Each entry in the LDT and GDT consists of 8 bytes. Each entry in the LDT and GDT has details about the segment base address and segment length. LDT and GDT are like segment tables (Figure 24.8).
Fig. 24.8 LDT, GDT
| s | g | p |
| 13 | 1 | 2 |
Fig. 24.9 Selector part of logical address
The logical address is a pair (selector, offset). The selector is a 16-bit number (Figure 24.9) where s is the segment number, g indicates whether GDT or LDT and p is used for protection. The offset part of the logical address is a 32-bit number showing the location of the word within the segment.
The 13 bit segment number in the selector is used to identify one of the 8 KB (213) segments, that is one of the 213 entries in the descriptor table. The base and limit information about each segment is present in the descriptor table (segment table) entry and is used to generate a linear address. The limit is used to check for address validity. If the limit is not valid, a trap is given to the OS. If the limit is valid, the offset in the logical address is added to the base address in the descriptor table to generate the 32-bit linear address. The linear address is then translated into a physical address.
Similar to how a process is divided into pages in paging, a segment is divided into pages. Figure 24.10 shows segment S1 being divided into pages. Each segment is of size 4GB and is divided into pages of size 4KB. Hence, there will 4GB/4KB = 232/212 = 220 pages for each segment. A page table needs to be allocated with 220 entries (an entry for each page). Each entry in the page table consists of 4 bytes. Hence, the size of the page table becomes 4 * 220 = 222 which is too large. Hence, the page table is also paged (divided into pages)
Fig. 24.10 Segment divided into pages
A two-level paging is used in this architecture. Since the page table is also divided into pages, to identify each page of the page table, an outer page table is created. This outer page table is called a page directory.
Fig. 24.11 Page table paged and page directory added
The 32-bit linear address is divided as shown in Figure 24.12: a 20 bit page number and a 12 bit offset.
page number | page offset
| p1 | p2 | d |
| 10 | 10 | 12 |
Fig. 24.11 Split of 32-bit linear address into page number and offset
Since the page table is paged, the page number is further divided into a 10-bit page directory pointer and a 10-bit page table pointer. Figure 24.12 shows the Intel 80386 address translation. The logical address is divided into a selector and an offset. The segment number in the selector is used as an index into the descriptor table. The base address in the descriptor table is combined with the offset in the logical address to form the linear address. The directory number is used as an index into the page directory. The page directory is used to identify the page table. The page number in the linear address is used as an index into the page table. The page table entry is used to identify the physical frame. The offset in the linear address is used as an index into the physical frame to get the physical memory location.
Fig. 24.12 Intel 80386 address translation
24.8 Summary
In this module, we learnt how address translation is done in segmentation and paged segmentation memory management schemes. Segmentation provides a user’s view of memory. In segmentation, a process is divided into variable sized segments and the segments are placed in the memory. This results in external fragmentation. To avoid external fragmentation, the segments are divided into pages. Page tables are hence added for all segments. When the size of a page table becomes large, the page table is also divided into pages and an outer page table is also added. This is called paged segmentation and is used in the Intel 80386 architecture.
References
- Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Sixth Edition, John Wiley & Sons Inc., 2003.
- Andrew S. Tanenbaum, Herbert Bos, “Modern Operating Systems”, Fourth Edition, Pearson Education, 2014.
- Gary Nutt, “Operating Systems”, Third Edition, Pearson Education