Chapter 2: Memory Management: Early Systems, Flynn and McHoes, Understanding Operating Systems, Second Edition, PWS Publishing Co. (1997)

Association for Computing Machinery web site:
http://www.acm.org/

A nice history of small system operating systems can be found at U. California, Davis:
http://escher.cs.ucdavis.edu:1024/classnotes/ecs15/lect7.html

Lesson A:
Fixed Partitions
Conceptual Overview: Dynamic Partitions, Compaction, Relocation

Single-Program Contiguous Scheme

• Entire program loaded
• Contiguous memory allocation

Fixed Partitions

• Partition memory at system initialization.
• Jobs in each partition are
  • Loaded entirely
  • Loaded contiguously
• Fixed Partition Memory Table example for 512 kB machine with 64 kB reserved for operating system.

Dynamic Partitions

• Partition memory at job load time.
  • Memory is allocated in blocks.
    • The most compact (initially) uses block size = 1 byte.
    • Memory is accounted for in a memory map table or in lists.  Tables are faster to use, but sparse tables take up more space than corresponding lists.  Systems may also use a table that is indexed by lists.
    • Best block size is a trade-off which depends on hardware characteristics.
    • Larger block sizes permit use of tabled memory map rather than lists of free and occupied memory.  Larger block sizes produce smaller tables and lists.
  • Memory partitioned in pages corresponding to memory-protect page size.
• Jobs in each partition are
  • Allocated only the memory requested.
  • Loaded entirely.
  • Loaded contiguously.
• First-Fit Allocation
  • First partition fitting the requirements.
  • Faster than best-fit.
• Best-Fit Allocation
  • Closest fit, the smallest partition fitting the requirements.
  • Better use of memory.
• Memory becomes fragmented.
• Dynamic Partition Memory Table example for 512 kB machine with 64 kB reserved for operating system.

• Job List  (Job ID, Memory Required, Job Run Time Estimate, Arrival Time):
  A3.2.0, B1.1.0, C2.3.0, D1.5.0, E4.2.0, F3.3.4, G1.1.4, H2.2.6
• First Fit: 
  • Find next job in queue that will fit into memory.
  • Once a job enters memory, it remains in its assigned partitions until the job terminates.

• Best Fit:
  • Examine all jobs existing in queue.
  • Find that scheduling plan that will result in the last scheduled job completing the quickest compared to alternative schedules.
  • Once a job enters memory, it remains in its assigned partitions until the job terminates.
  • Favor large memory jobs over small memory jobs, subject to the restriction that memory usage is maximized at the time of memory allocation.  This stalls the onset of memory fragmentation.
  • Among choices equal based on memory size requirements and memory total usage, favor a combination that will terminate simultaneously in order to free up the most contiguous memory.
  • Among otherwise equal memory size and memory total usage measures, favor long-running jobs over short running jobs.

Memory Map

• A memory map is a table or lists that identify which memory is in use or is free.
• The reassigning of a block of memory from in-use status to free status is called deallocation.

Relocation and Compaction

• Without ability to relocate, you must wait until contiguous memory is free in order to compact memory.
• The process of relocation and compaction is called "garbage collection".
• Continuous garbage collection ensures best use of memory, at the (sometimes great) expense of total time required for the process.  Continuous garbage collection will appear to be a small overhead to users at any one point in time, but occurs frequently.  Periodic or condition-based garbage collection uses time more efficiently at the expense of missed opportunity to get another job into memory.