# MULTIPLE PROCESSES WITH A VARIABLE NUMBER OF PROCESSES 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

### External fragment

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. (a) There is enough RAM for Application 6 but the holes are not contiguous (b) Application 3 is relocated to bring the two holes together

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.