Program is run
   . loaded in its entirety into memory
   . allocated contiguous space in memory
   . minimal work by the Memory Manager
   . store the base address & keep track of program size

Disadvantages of Single-User Contiguous Scheme:
   . no multiprogramming
   . not cost effective - Poor use of resources
   . very large programs??  (explain overlays)
   . what do you do when you have to run a different program?

Terminate and Stay Resident (TSR) in DOS
   . primitive multitasking: small utility programs (calculator, contacts)
   . normally, only one program could run, then return control to OS
   . if a program ended with the system call INT 21H/31H, OS did not
     reuse a certain, specified, part of the program's memory.
   . could run another program and the return control to original prog

Protection 
   . files: leave files open when another program runs => problems?
   . memory: if OS is in high 4k of 12k system then
                mod all program address request mod 8k
 

Main memory is partitioned in advance
   .one partition/job (overlays)
   .allows multiprogramming - makes better use of what resource?
   .partition sizes remain static unless system is shut down,
    reconfigured, and restarted ("gen" the system)
   .requires protection of the job’s memory space
       limit registers: compare addresses to start/stop of partition








Disadvantages:
   .Requires entire program to be stored contiguously
   .Job allocated space on basis of first available
    partition of required size (called what??)
   .Works well only if  all of the jobs are of the same size or
    if the sizes are known ahead of time
   .Too small a partition: large jobs having long turnaround time
   .Too large a partition: memory waste within partition (internal frag)

Deallocation: For fixed-partition system: EASY
   .When job completes, Memory Manager resets job’s memory block to “free”

 ? How could allocation be improved?
   

Jobs are given only as much memory as they request when loaded
Available memory is kept in contiguous blocks
Memory waste is comparatively small
Disadvantages:
   Fully utilizes memory only when the first jobs are loaded
   Subsequent allocation leads to memory waste or external fragmentation

Free partitions are allocated on the following basis:
   First-fit: First partition fitting the requirements
      Advantage: Faster in making allocation
      Disadvantage: Leads to memory waste

   Best-fit: Smallest partition fitting the requirements
      Advantage: Makes the best use of memory space
      Disadvantage: Slower in making allocation

FIRST FIT
=========
   each job is given the first available partition 


Algorithm for First-Fit: (2 lists: free and busy)
While jobs in queue
   Get job size
   Loop through blocks in free list
      If block size >= job size
         found = true
   Until found or no more blocks
   If found
      Store job into block of memory
      Update busy list with job info
   Else
      Put job back into job queue
End while


Request:job 200 blocks (what memory is it given?)





BEST FIT
========
   each job is given the partition closest in size


Algorithm for Best-Fit:(2 lists: free and busy)
   Goal: find the smallest memory block into which the job will fit
   If job fits exactly, can stop
   Otherwise, entire table must be searched before allocation

While jobs in queue
   Get job size
   Set difference to -1
   Loop through blocks in free list
      If block size >= job size
         Calculate difference
         If difference is smallest so far
            Save that difference as smallest so far 
            Save that index
            If difference = 0 then 
               Break from loop
   Until no more blocks

   If difference > -1
      Store job into block at saved index
      Update busy list with job info
   Else
      Put job back into job queue
End while

Best fit request = 200 blocks




Hypothetical allocation schemes:
================================
   NEXT-FIT:
      Like First Fit
      Starts searching from last allocated block
      
   WORST-FIT:
      Allocates the largest free available block
      Opposite of best-fit
      Why would you do this?
 

Try to combine free areas of memory whenever possible
Three cases:
   Case 1: When deallocated block is adjacent to another free block
   Case 2: When deallocated block is between two free blocks
   Case 3: When deallocated block is isolated from other free blocks

Case 1: Joining Two Adjacent Free Blocks
=======
   Change list must reflect starting address of the new free block
   In example, 7600 was the address of the job that just released memory
   Memory block size for the new free space must be changed to show its
     new size — that is, the combined total of the two free partitions
   In the example, (200 + 5)





Case 2: Joining Three Free Blocks.
=======
   Deallocated memory space is between two free memory blocks
   Change list to reflect the address of the new free block (7580)
   In the example, 7560 and 7600 were adjacent to the new free block
   The three free partitions must be combined
      In the example, (20 + 20 + 205)
  In the example, 7560 will mark beginning of free block size 245





Case 3: Deallocating an Isolated Block.
=======
   Space to be deallocated is isolated from other free areas
   not adjacent to any free blocks of memory, it is
   Must search the free list for a null entry
   Null entry in the busy list occurs when a memory block between
     two other busy memory blocks is returned to the free list










 

Relocatable Dynamic Partitions:
===============================
   Memory Manager relocates programs to gather together all empty blocks
   Compacts the empty blocks to make one large block of memory
   Reclaims fragmented sections of the memory space
   Programs in memory must be relocated so they are contiguous
                              ^^^^^^^^^

   Adjust every address to account for program’s new location
   OS must distinguish between addresses and data values
   Data values left alone, Addresses must be changed
   How does it know??

   
   HARDWARE: Special-purpose registers are used for relocation:
      Relocation register
      Contains value that must be added to each address referenced in program  
      If program isn’t relocated
            value stored in program's relocation register is zero
   increases overhead!!



   
   Relocate Job 4
   ==============
     will move to a spot 12,288 bytes "up" in RAM
     simply put that value in relocation register
     

      

      
What lists have to be updated?
===============================
   Free list will show the partition for the new block of free memory
   Busy list  will show the new locations for all jobs that were relocated
   Each job will have a new address (except those at lowest memory locations)

When Compaction??
=================
    1. set time
    2. set % of memory used
    3. whenever new job enters