Operating Systems: Three Easy Pieces Ch. 16

Segmentation

• Why not have a base and bounds pair per logical segment
• Segment independently in physical memory
• Sparse address spaces
• What we need to first do is extract the offset into the heap
• Illegal address → segmentation fault
• Which Segment are we referring to?
• Explicit approach
  • upper two bits heap indicates which offset
  • next 12 bits as the offset into the segment
  • By adding the base register to the offset, the hardware arrives at the final physical space
• Implicit approach
  • hardware determines the segment by noticing how the address was formed
  • address is within the code segment
• Stack
  • one critical difference, it grows backward
  • hardware must now translate such virtual addresses slightly differently
  • We simply add the negative offset to the base
• Sharing
  • Code sharing
  • Protection bit → extra support from the hardware
• Fine-grained vs Coarse-grained Segmentation
  • Coarse-grained
    • chops up the address space into relatively large
  • Fine-grained
    • allowed for address space to consist of a large number smaller segment
• Segment table
  • usually support the creation of a very large number
• OS Support
  • OS must make sure to set up these registers correctly before letting the process run again.
  • The second, and more important, issue is managing free space in physical memory.
  • External fragmentation
    • The general problem that arises is that physical memory quickly becomes full of little holes of free space, making it difficult to allocate new segments, or to grow existing ones.
    • One solution to this problem would be to compact physical memory by rearranging the existing segments.
    • best fit
    • worst fit
    • first fit
    • buddy algorithm
• Overall
  • Segmentation solves a number of problems, and helps us build a more effective virtualization of memory. Beyond just dynamic relocation, segmentation can better support sparse address spaces, by avoiding the huge potential waste of memory between logical segments of the address space.
  • Problems
    • External fragmentation
    • Segmentation is not flexible