Chapter 11, part 2
The lesson on chapter 11 continues with more discussion about memory. On page 428, the text describes single-tasking memory allocation, which might be best thought of as the kind of allocation that was done on systems before multitasking was practical.
The illustration on that page shows us that the operating system was loaded into memory first, a single application was loaded into available memory above that, and the remaining free memory was available to the needs of the running application. In this case, the concept of an offset is introduced for applications that assume they are running in low memory. The OS makes the allocation to the process, makes it look like the allocation is located in low memory, but uses an offset value that refers to the real starting memory address. The text refers to this value as the process offset for that process. Two techniques using this offset are described:
Multitasking memory allocation is different. A set of goals for an OS that supports multitasking appears on page 429:
Memory is divided into partitions for multitasking. Figure 11.15 on page 430 shows an OS loaded into the first five partitions in memory (0-4), The next three partitions are allocated to a process (5-6), the two after that are allocated to a second process (7-8), and the next five partitions (9-13) are allocated to a third process, although it does not fill its fifth partition. This is wasted space unless the process is expected to grow to fill it. The OS keeps track of partition allocation in a data table, which must be updated when allocations and deallocations take place.
The text remarks that smaller partition sizes can lead to less wasted space, and better memory utilization. This also leads to more overhead managing a larger number of partitions.
The text has given us the impression that memory is always allocated in sequential (contiguous) address ranges, but this is not always possible. Memory is allocated, used, and released for reallocation constantly, which leads to the state in which enough memory for a purpose is available, but it is only available in separate chunks. Figure 11.16 shows a picture of memory space changing in a system across time. In the first example, all partitions but one are filled. In the second, a process released its partitions, another was loaded in its place, and the new one did not take up all the memory the old one released. In the third example, another pair of partitions have been released by a process that has terminated. Another way this sort of thing can happen is if you load a process that takes more RAM when it is loaded than it needs once it is running.
The text tells us that the state this process of allocating, releasing, and reallocating leads to is called memory fragmentation. Fragmentation is when the allocation that must be made to a process will consist of memory partitions that are not contiguous. Some operating systems have a feature called garbage collection that harvests unused RAM, updates the tracking table for it, and makes it available to processes. This is a useful feature, but it is not as useful as compaction, which is moving all processes RAM from time to time, to put them in contiguous address spaces when possible.
The text confuses the issue by bringing up disk compaction on page 433. This is a separate function to make more economical use of hard drive space. It might be best to refer to the two processes as RAM/memory compaction and disk/file compaction.
On page 433, the text begins a short discussion of how allocation of noncontiguous memory typically functions. It is just a bit more complicated than using the process offset method discussed above, but it is also similar. When a process is loaded in several noncontiguous partitions, each partition that is used has its own entry and its own offset value that are stored in the tracking information (partition table) for that process.
The text also discusses virtual memory management, which uses storage device memory as swappable space for RAM. The text explains that the only parts of a process that must be in memory are the next instruction to be executed, (the current instruction being executed), and any values that the process is currently using (operands). Other parts of the process are eligible to be swapped out to temporary storage space on a hard drive, or in another section of RAM.
This is often done on devices running Windows. A process is divided into parts called pages. Space in RAM that holds a page (part of a process) is called a page frame. Pages that are not currently in use can be copied to space on a hard drive called swap space, swap files, or page files. This allows the OS to free up the page frame that the copied page was using, and to load a page that is needed next into that page frame.
As the process is executed, memory references in the process are checked to determine whether they reference something already in RAM (a page hit) or something the is in a swap file at present (a page fault). When a process requires a page to be loaded into RAM and all page frames are already in use, the OS must choose a page to dump to a swap file. That page is called a victim. The text lists two methods that might be used to choose a victim: find a page that is the least recently used, or find a page that is the least frequently used. Both methods are betting that the chosen victim page will not be needed next.