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

Lesson B: First Fit Algorithm, Best Fit Algorithm

First-Fit Algorithm

1 Set counter to 1
2 Do while counter <= number of blocks in memory
 

If job_size > memory_size(counter)
 

then counter = counter + 1
 

else
 

load job into memory_size(counter)
 

adjust free/busy memory lists
 

go to step 4
  End do
3 Put job into waiting queue
4 Go fetch next job

Apply this algorithm to job list from the previous lecture example:  
Job List  (Job ID, Arrival Time, Memory Required, Job Run Time Estimate):
(A0,2,2) (B0,1,5) (C0,3,3) (D3,1,4) (E3,3,3) (F3,3,2) (G7,2,4) (H7,2,1) (I8,1,4) (J8,3,2) (K12,1,2) (L13,4,1)
Assume memory has only 8 units of storage.

Time
Step		 Page
0		 Page
1		 Page
2		 Page
3		 Page
4		 Page
5		 Page
6		 Page
7		 Old Jobs
Processing		 New Jobs
Processing		 Jobs
Waiting
0 Z A A B C C C ABC
1 Z A A B C C C ABC
2 Z B C C C BC
3 Z D B E E E B DE F
4 Z D B E E E BDE F
5 Z D E E E DE F
6 Z D F F F D F
7 Z F F F G G F G H
8 Z H H I G G G HI J
9 Z I G G GI J
10 Z I G G GI J
11 Z I J J J I J
12 Z K J J J J K
13 Z K L L L L K L

Best Fit Algorithm

1 Initialize memory_block(0) = 99999
2 Compute initial_memory_waste = memory_block(0) - job_size
3 Initialize subscript = 0
4 Set counter to 1
5 Do while counter <= number of blocks in memory
  If job_size > memory_size(counter)
 

Then counter = counter + 1
  Else
 

Memory_waste = memory_size(counter) - job_size
 

If initial_memory_waste > memory_waste
 

Then subscript = counter
 

initial_memory_waste = memory_waste
 

counter = counter + 1
 

End do
6 If subscript = 0
 

Then put job in waiting queue
  Else
 

load job into memory_size(subscript)
 

adjust free / busy memory lists
7 Go fetch next job

Apply this algorithm to job list from the previous lecture example:  
Job List  (Job ID, Arrival Time, Memory Required, Job Run Time Estimate):
 (A0,2,2) (B0,1,5) (C0,3,3) (D3,1,4) (E3,3,3) (F3,3,2) (G7,2,4) (H7,2,1) (I8,1,4) (J8,3,2) (K12,1,2) (L13,4,1)
Assume memory has only 8 units of storage.

Time
Step		 Page
0		 Page
1		 Page
2		 Page
3		 Page
4		 Page
5		 Page
6		 Page
7		 Old Jobs
Processing		 New Jobs
Processing		 Jobs
Waiting
0 Z A A B C C C ABC
1 Z A A B C C C ABC
2 Z B C C C BC
3 Z D B E E E B DE F
4 Z D B E E E BDE F
5 Z D E E E DE
6 Z D F F F D F
7 Z F F F G G F G H
8 Z H H G G I G HI J
9 Z J J J G G I GI J
10 Z J J J G G I GIJ
11 Z I I
12 Z K K
13 Z K L L L L K L

As another, try the best fit algorithm again, except that during each scheduling slice, sort the jobs in the queue by decreasing size before considering memory allocation.  We then do best fit with the biggest piece first, and continue to the smaller ones.

Job List  (Job ID, Arrival Time, Memory Required, Job Run Time Estimate):
(A0,2,2) (B0,1,5) (C0,3,3) (D3,1,4) (E3,3,3) (F3,3,2) (G7,2,4) (H7,2,1) (I8,1,4) (J8,3,2) (K12,1,2) (L13,4,1)

Time
Step		 Page
0		 Page
1		 Page
2		 Page
3		 Page
4		 Page
5		 Page
6		 Page
7		 Old Jobs
Processing		 New Jobs
Processing		 Jobs
Waiting
0 Z C C C A A B ABC
1 Z C C C A A B ABC
2 Z C C C B BC
3 Z E E E B D B DE F
4 Z E E E B D BDE F
5 Z E E E F F F D DE F
6 Z F F F D DF
7 Z G G H H GH
8 Z G G J J J I G IJ
9 Z G G J J J I GIJ
10 Z G G I GIJ
11 Z I
12 Z K K
13 Z K L L L L K L

In the next try, we do it by eye, accounting for both job size and time.  What rules can you come up with to produce a good fit?  How do you measure a best algorithm?  What about maximizing contiguous available space after memory allocation?    

Job List  (Job ID, Arrival Time, Memory Required, Job Run Time Estimate):
(A0,2,2) (B0,1,5) (C0,3,3) (D3,1,4) (E3,3,3) (F3,3,2) (G7,2,4) (H7,2,1) (I8,1,4) (J8,3,2) (K12,1,2) (L13,4,1)

Time
Step		 Page
0		 Page
1		 Page
2		 Page
3		 Page
4		 Page
5		 Page
6		 Page
7		 Old Jobs
Processing		 New Jobs
Processing		 Jobs
Waiting
0 Z C C C A A B ABC
1 Z C C C A A B ABC
2 Z C C C B BC
3 Z E E E F F F B B DE F
4 Z E E E F F F B BDE F
5 Z E E E D DE F
6 Z D DF
7 Z G G H H D GH
8 Z G G J J J D G IJ
9 Z G G J J J I GIJ
10 Z G G I GIJ
11 Z I
12 Z K I K
13 Z K L L L L K L