Segmentation

Divide virtual space of the process into segments. Similar to paging except we can have segments match with needed sizes. See Fig 3-35, 3-37.

Address translation makes use of segment tables. A segment table contains an entry for each segment for a process. Entries contain:

pointer to start of segment in physical memory (base)
size of segment (bounds)
indication of whether or not segment is currently in memory
protection information (does process have permission to read, write, or execute the segment?)

Example: assume addresses have form xxyy, xx = segment number, yy = offset.

int n;

main(argc, argv)
int argc;
char **argv;
{
    n = argc;
}

Segment table:

Segment real length present permission

number base bit

0 100 77 yes rx

1 320 84 yes rw

2 15 80 yes rw

3 *** *** no ***

Physical memory layout:

address: 0-14 15-94 95-99 100-176 177-319 320-403

status: free alloc free alloc free alloc

Sample translations:

virtual address physical address

053 100 + 53 = 153

241 15 + 41 = 56

189 invalid offset (89 > 84)

423 invalid segment (4 > 3)

365 not present

The hardware performs the following address translation for every memory reference:

extract segment number from virtual address
if segment number is greater than max number of segments, trap with ``illegal segment''.
consult segment table entry:
- if segment not present in memory, trap ``missing segment''
- if segment offset is greater than segment size, trap ``offset out of range''
- if process does not have access permissions, trap ``protection violation''
(finally), return physical address (segment base + offset)

Sharing with Segmentation

Segmentation allows greater information sharing:

segments can be shared by different processes (shared libraries)
different processes can reference a shared segment with different segment numbers
multiple processes can have differing access rights to a segment

Process A: Process B:

Segment real length

number base

0 200 150

1 400 120

2 600 80

Segment real length

number base

0 350 44

1 0 150

2 400 120

status: B free A B A & B free A

address: 0-149 150-199 200-349 350-399 400-519 520-599 600-679

Physical memory layout:

Sample translations:

process virtual address physical address

B 123 350 + 23 = 373

A 123 400 + 23 = 423

B 223 400 + 23 = 423

Note: Although Process A & B share the same segment, they are referenced through different virtual addresses!

A shared-segment table manages all shared segments. The table is only needed to (rapidly) determine which processes are sharing a segment.

When a process references data in a missing segment, the hardware generates a segment fault that traps to the kernel. The fault handler:

tries to find a chunk of free memory into which it can place the missing segment
if no free chunk is available, it must first swap out an existing segment to make room
loads the new segment into memory
restarts the process that caused the fault

The problem of which segment to remove when no free chunk exists is a general problem of caching. We will discuss it later.

address in backing store kept in segment table (or parallel data structure)
segment need not be written if it is unmodified (check access permissions)
some machines include a dirty bit in the segment table that the hardware sets when it writes into the segment

Because virtual address are bound to physical address at access time, swapped-out segments can be swapped back in at any physical location.

The size of a segment can vary dynamically as the process requests and returns memory.

Like multiple level page tables. Select the segment and then have a page table for each segment. Look at example 3-39.

address:	0-14	15-94	95-99	100-176	177-319	320-403
status:	free	alloc	free	alloc	free	alloc

status:	B	free	A	B	A & B	free	A
address:	0-149	150-199	200-349	350-399	400-519	520-599	600-679