A partial solution to that internal fragmentation is to not make the partitions fixed in size or in number. Instead, we use as much memory as we need to run a program. We require that a programmer estimate in advance of running the program the maximum amount of primary memory that the program will need. When we start the program we allocate that much memory to the program. multiple processes with a variable number of processes If the program tries to use more memory than the programmer said it would, then the OS will end it with an error. .When a program ends the OS will again make that memory available to run another program. This space is normally referred to as a whole, or sometimes an
A block of memory that we are currently not using at all. A situation where the system is currently running four applications. In Figure 10.8b we see that applications two and four have ended, so the holes where they were running are now available for use in running other programs. The OS usually keeps a list of the holes available. In we see that the OS has started application 5 in a part of the hole left where application 2 was running. There is now a smaller hole left over.
Now suppose that the OS has another program to run and there are many holes available to choose from. Which hole should the OS choose? As with most of the algorithm classes we study in this book, the first algorithm is simply to scan through the list of holes and use the first one we find that is big enough to run the program. This algorithm is called first fit. It has the advantage of being simple. But this may not be the best choice. Another algorithm is to use the hole that is the smallest that will fit the program we want to run. This algorithm is called best fit. It has an intuitive appeal—we waste the smallest amount of primary memory. Unfortunately, this algorithm requires that we either scan the entire list or keep the list in order by size. Either requires extra processing.
A slight variation on the first fit algorithm is called next fit. In this variation we do not start each search from the front of the list. We do not keep the list sorted, and we always start the next search from where the last one left off. The first fit algorithm will tend to break up the holes at the front of the list the most, so we will end up with a bunch of small holes that we keep looking through but can seldom use. multiple processes with a variable number of processes The next fit variation will tend to distribute this fragmentation through the list. In practice, worst fit turns out to be worst. Either best fit or next fit are better, and next fit is very easy to implement.
Now we can appreciate why the relocation hardware uses a length for an upper bound instead of using the upper end of the program. If it used the upper address then when we relocated a program we would also have to recompute the upper bound. This is not an overwhelmingly complicated calculation, and it does not need to be done all that often, but if the hardware can work just as well the other way then we are lucky not to have to do it.
With overlays, we do not load the entire program into primary memory at one time. Instead, the programmer explicitly decides when to load the overlays and when to call the routines that are in the overlay. It is also possible for the system to do something similar. When the OS loads a program into main memory it might load into memory only the main body of the program. multiple processes with a variable number of processes To access various subroutines it might make use of a table that shows which routines are already loaded into memory and which are not. Many programs follow roughly the “80-20” rule—80% of the code of a program is for situations that only happen 20% of the time.
So if we don’t load the subroutines when the program first starts we might never need to load them at all. Therefore, the program starts somewhat faster. If the program later calls the routine then we can load it at that time and we will have paid the very little penalty for waiting a small bit of RAM for the table and a few extra instructions executed whenever we first call the routine.