Algorithm to load job in single user system:

1. Store first memory location into base register
2. Set program counter to address of first memory location.
3. Get an instruction.
4. Increment program counter by # bytes in instruction.
5. Has the last instruction been reached?

   If yes, stop loading program
6. Is the program counter greater than memory size?

   If yes, stop loading the program
7. Load instruction into memory
8. Go to step 3

Memory management very easy – just needs to keep track of base address and value of accumulator. First computers (40’s and 50’s) had this type of memory management. Very uneconomical system $200,000 for equipment that could only be used by one person at a time.

First attempt to allow for multiprogramming. One fixed (or static) partition for each job. Partition size designated when machine started. To change has to power down.

Critical factor to protect the partition’s boundaries. Algorithm more complex:

Determine job’s requested memory size.
If job_size > largest partition
   Reject job – move to next job
set counter to 1
do while counter < = # partitions
   if job_size > partition[counter].size
      counter++
   else if partition[counter].status = "free"
      then load job into partition[counter]
      and change status of partition[counter] to busy.
         Else counter++;
End while
No partition available at this time – put job in queue
Get next job

This algorithm still requires that the entire program be stored contiguously in memory from the beginning to the end of execution. Memory manager must keep a table of partitions, their size, the job that is in them and their current status.

Job1 30K, Job2 50K, Job3 30K, Job4 25k. Job 3 must wait even though there is 70K space in partition 1. If partitions are set too small, larger jobs will be rejected or have a longer turnaround. If partitions set too big, space will be wasted. The creation of unused spaces within partitions because of too large partition size is called internal fragmentation.

With dynamic partitioning, available memory is still kept in contiguous blocks, but jobs are only given as much memory as they need. This is an improvement over fixed partitions, but still has problems.

When jobs first loaded in, memory fully utilized. When jobs are finished, a memory space the size of the previous job is freed up. These partitions can be allocated by best fit or first fit. Subsequent allocation creates fragments of free memory between blocks. This is called external fragmentation.

Job list (J1 10K, J2 20K, J3 30K, J4 10K)

Available 115K Used 40K

In this algorithm, a job is put into the first free space that it fits into, but you can see there can be problems. In example above there is 75 K of unused space, but Job 3 that needs 30K cannot be allocated 30K of contiguous space.

First fit requires memory manager to keep lists of busy blocks and free blocks. Size of each incoming job compared to block until large enough block is found.

if job_size > memory[counter].size
   then counter++
else
   load job into memory[counter]
   adjust status – change free list
if not loaded put job on queue
get next job

To show how free list would change...

Job list (J1 10K, J2 20K, J3 30K, J4 10K)

Available 115K Used 70K

Fragmentation has been reduced and J3 got to run faster, but the allocation process takes more time.

Algorithm for best fit.

Initialize Min_waste to 99999.
Set Good_spot to 0
Set counter to 0
Do while counter <= # blocks
   If job_size > memory[counter].size
      Then counter++
   Else
      Waste = memory[counter].size – job_size
      If Waste < Min_waste
         Min_waste = Waste
         Good_spot = counter
         counter++
end while
if Good_spot = 0
   then put job in queue
   else load job into memory[Good_spot]
      change free memory list
get next job>

Entire set of free memory blocks must be searched because they are stored in physical sequence. This takes time – they could be sorted but that would take time too.

To show how free list would change...

Best fit results in a better fit, but results in slivers of unused memory.

DEALLOCATION

1. when the block to be deallocated is adjacent to another free block.
2. When the block to be deallocated is between two free blocks
3. When the block to be deallocated is isolated from other free blocks.

In this approach to memory management, programs are relocated to put together all the empty space – a bit like defragging a disk. This is called "garbage collection".

The great difficulty with this approach is the overhead associated with the relocation of the instructions. A computer instruction is a series of binary codes that contain addresses and instruction codes. However, if the program is to be moved each address must be flagged so that later the amount of memory locations to which the program has been displaced can be accounted for. Particularly important for loops and branching, since this is done by address.

What has to be done by the memory manager to implement this approach?

1. Actually move all the programs to consolidate space.
2. Use special purpose registers that are available in some computers. There is a relocation register that contains the value that must be added to each address referenced in the program.
3. Update the free and busy list.

The overhead is so large in this approach that a crucial question is how often should it be done?

1. one approach is to do it when memory is getting full, say around 75%. However, if no jobs were waiting this would be unnecessary overhead.
2. Another is to compact when there are jobs waiting to get into the system
3. Thirdly do it after a prescribed amount of time. If amount to small – excessive overhead. If too large, compaction not effective, too many jobs in queue.

Common elements of all these early approaches to memory management is that they require the entire program

1. be loaded into memory
2. be stored contiguously
3. remain in memory until job is completed.

Later memory managers allow programs to not be stored contiguously – but can be divided into segments or pages. Each page or segment could be stored wherever there was an empty space. Furthermore, these pages or segments do not all have to reside in memory during the execution of the job.

Worked examples:

Given the following information:

1. Where will the jobs go under the best-fit algorithm?
2. Where will the jobs go with the first-fit algorithm?

Repeat with the following: