<< Chapter < Page Chapter >> Page >

(The last two alternatives are kludges used for machines with such small addresses that there is not room for both a segmentnumber and an offset)

 Segment table holds the bases and bounds for all the segments of a process.

 Show memory mapping procedure, involving table lookup + add + compare. Example: PDP-10 with high and low segments selected byhigh-order address bit.

Segmentation example: 8-bit segment number, 16-bit offset.

  • Segment table (use above picture -- all numbers in hexadecimal):
  • Code in segment 0 (addresses are virtual):
  • 0x00242:mov 0x60100,%r1
  • 0x00246:st %r1,0x30107
  • 0x0024A:b 0x20360
  • Code in segment 2:
  • 0x20360:ld [%r1+2],%r2
  • 0x20364:ld [%r2],%r3
  • ...
  • 0x203C0:ret

Advantage of segmentation: segments can be swapped and assigned to storage independently.

Problems:

  • External fragmentation: segments of many different sizes.
  • Segments may be large, have to be allocated contiguously.
  • (These problems also apply to base and bound schemes)

Example: in PDP-10's when a segment gets larger, it may have to be shuffled to make room. If things get really bad it may benecessary to compact memory.

Paging

Goal is to make allocation and swapping easier, and to reduce memory fragmentation.

  • Make all chunks of memory the same size, call them pages. Typical sizes range from 512-8k bytes.
  • For each process, a page table defines the base address of each of that process' pages along with read/only and existence bits.
  • Page number always comes directly from the address. Since page size is a power of two, no comparison or addition is necessary. Just do tablelookup and bit substitution.
  • Easy to allocate: keep a free list of available pages and grab the first one. Easy to swap since everything is the same size, which is usually thesame size as disk blocks to and from which pages are swapped.
  • Problems:
    • Internal fragmentation: page size does not match up with information size. The larger thepage, the worse this is.
    • Table space: if pages are small, the table space could be substantial. In fact, this is a problem even for normal pagesizes: consider a 32-bit address space with 1k pages. What if the whole table has to be present at once? Partial solution: keep base and bounds for pagetable, so only large processes have to have large tables.
    • Efficiency of access: it may take one overhead reference for every real memory reference (page table is so big it has to be kept in memory).

Two-level (multi-level) paging

Use two levels of mapping to make tables manageable.

Segmentation and paging

Use two levels of mapping, with logical sizes for objects, to make tables manageable.

  • Each segment contains one or more pages.
  • Segment correspond to logical units: code, data, stack. Segments vary in size and are often large. Pages are for the use of the OS; they arefixed size to make it easy to manage memory.
  • Going from paging to P+S is like going from single segment to multiple segments, except at a higher level. Instead of having a single pagetable, have many page tables with a base and bound for each. Call the material associated with each page table a segment.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Operating systems. OpenStax CNX. Aug 13, 2009 Download for free at http://cnx.org/content/col10785/1.2
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Operating systems' conversation and receive update notifications?

Ask