PURE Segmentation in Operating Systems | OS Tutorials

In an operating system, virtual memory is one-dimensional since the virtual addresses go from 0 to the maximum range. We may also implement more than one virtual address space rather than one for many problems. Consider an example of a compiler that has many tables that are built up as compilation proceeds, possibly including:

1. The source text being saved from the printed listing.
2. The symbol table, containing the names and attributes of variables.
3. The table containing all the integers and floating-point constants used.
4. The parse tree, containing the syntactic analysis of the program.
5. The stack used for procedure calls within the compiler.

Among these, the first four tables grow continuously as compilation proceeds, whereas the last table grows and shrinks in predictable ways during compilation. All these tables would have to be allocated as contiguous blocks of virtual address space, as shown in Figure 1. The chunk of address space allocated for the symbol table may fill up, but there may be lots of room in the other tables.

The compiler would simply issue a message saying that the compilation cannot continue due to too many variables. Another consideration is taking space from the tables with an excess of room and giving it to the tables with little room. It is important to free the programmer from having to manage the expanding and contracting tables. A general and effective solution is to provide the machine with many completely independent address spaces called segments.

Pure Segmentation

• Each segment consists of a linear sequence of addresses, from 0 to some maximum. The length of the segment may be anything from 0 to the maximum allowed.
• Segment length may change during execution time. The length of a stack segment may be increased whenever something is pushed onto the stack and decreased whenever something is popped off the stack.
• For simplicity of implementation, segments are numbered and are referenced by a segment number, rather than by a segment name.
• Thus, a logical address consists of a two-tuple.

<segment_number, offset>

• Because each segment constitutes a separate address space, different segments can grow or shrink independently without affecting each other.
• Figure 2 illustrates a segmented memory being used for the compiler table. Five independent segments are shown here

Implementation of Pure Segmentation

Implementation of segmentation differs from paging essentially:

Pages are fixed size and segments are not.

Consider an example: assume that physical memory initially contains five segments as shown in Figure 3(a).

Suppose segment 1 is removed from memory, and segment 7, which is smaller (5 K), is put in its place. Hence, the memory configuration looks like that shown in Figure 3(b).

The area between segment 7 and segment 2 is an unused area, usually called a hole. Then segment 4 is replaced by segment 5. This situation is shown in Figure 3(c), and similarly, segment 3 is replaced by segment 6 as shown in Figure 3(d).

After some time, when the system has been running, memory will be divided up into several chunks, some containing segments and some containing holes. This phenomenon is called checkerboarding or external fragmentation, which wastes memory in the holes. Hence, to reuse this memory, compaction is implemented. Hence, the total memory of 10K (3K + 4K + 3K) is compacted into one for the other segment. It is shown in Figure (e).

Hardware Support

• The user can refer to objects in the program by a two-dimensional address, since the physical memory is a one-dimensional sequence of bytes.
• Hence, mapping must be implemented to map two-dimensional user-defined addresses into a one-dimensional physical address.
• This mapping is effected by a segment table. Each entry of the segment table has a segment base and a segment limit.
• The segment base contains the physical address where the segment resides in memory, whereas the segment limit specifies the length of the segment.
• Figure 4 shows the implementation of the segment table.

Since logical addresses consist of two parts:

The segment number is used as an index into the segment table. The offset d of the logical address must be between 0 and the segment limit. If the offset is legal, it is added to the segment base to produce the physical memory address of the desired byte. The segment table is thus stated as an array of base-limit register pairs.

Example implementing segmentation:

Let us suppose we have five segments (0 to 4). All these segments are stored in physical memory as shown in Figure 6.

The segment table has a separate entry for each segment, giving the beginning address of the segment in physical memory (base) and the length of that segment (limit). Since segment 2 is 200 bytes long and begins at location 4100. Thus, a reference to byte 23 of segment 2 is mapped onto location 4100 + 23 = 4123. Similarly, others are implemented; a reference to byte 1500 of segment 0 would result in a trap to the operating system, since this segment is only 800 bytes long.