Chapter 8: Memory Management Strategies (3721)

Chapter 8: Memory Management Strategies (3721)

1. many algorithms require hardware support, leading many systems to have closely integrated hardware and operating-system memory management.

2. 8.1 Background

   • Memory consists of a large array of bytes, each with its own address
   • We are interested only in the sequence of memory addresses generated by the running program.
   • A typical instruction-execution cycle, for example, first fetches an instruction from memory. The instruction is then decoded and may cause operands to be fetched from memory. After the instruction has been executed on the operands, results may be stored back in memory
   • several issues that are pertinent to managing memory:
     • basic hardware, the binding of symbolic memory addresses to actual physical addresses
     • the distinction between logical and physical addresses.
   • 8.1.1 Basic Hardware
     • Main memory and the registers built into the processor itself are the only general-purpose storage that the CPU can access directly.
     • Registers that are built into the CPU are generally accessible within one cycle of the CPU clock
     • Completing a memory access may take many cycles of the CPU clock. (Need to use system bus)
       • In such cases, the processor normally needs to stall, since it does not have the data required
     • For proper system operation we must protect the operating system from access by user processes.On multiuser systems, we must additionally protect user processes from one another.
       • This protection must be provided by the hardware because the operating system doesn’t usually intervene between the CPU and its memory accesses
         • we outline one possible implementation
           • We first need to make sure that each process has a separate memory space.
             • protects the processes from each other
           • To separate memory spaces, we need the ability to determine the range of legal addresses that the process may access
             • provide this protection by using two registers
               • The base register holds the smallest legal physical memory address
               • limit register specifies the size of the range
           • Protection of memory space is accomplished by having the CPU hardware compare every address generated in user mode with the registers
             • A trap occurs when a process attempts to access unauthorised memory
           • The base and limit registers can be loaded only by the operating system, which uses a special privileged instruction
           • The operating system, executing in kernel mode, is given unrestricted access to both operating-system memory and users’ memory.
   • 8.1.2 Address Binding
     • Usually, a program resides on a disk as a binary executable file. To be executed, the program must be brought into memory and placed within a process
     • The processes on the disk that are waiting to be brought into memory for execution form the input queue.
     • Most systems allow a user process to reside in any part of the physical memory.
     • A compiler typically binds these symbolic addresses to relocatable addresses (such as “14 bytes from the beginning of this module”). The linkage editor or loader in turn binds the relocatable addresses to absolute addresses (such as 74014). Each binding is a mapping from one address space to another
     • Classically, the binding of instructions and data to memory addresses can be done at any step along the way:
       • • Compile time. If you know at compile time where the process will reside in memory, then absolute code can be generated
         • The MS-DOS .COM-format programs are bound at compile time.
       • • Load time. If it is not known at compile time where the process will reside in memory, then the compiler must generate relocatable code.
       • • Execution time. If the process can be moved during its execution from one memory segment to another, then binding must be delayed until run time.
         • Most general-purpose operating systems use this method.
   • 8.1.3 Logical Versus Physical Address Space
     • An address generated by the CPU is commonly referred to as a logical address, whereas an address seen by the memory unit—that is, the one loaded into the memory-address register of the memory—is commonly referred to as a physical address.
     • The compile-time and load-time address-binding methods generate identical logical and physical addresses.
     • execution-time address-binding scheme results in differing logical and physical addresses
       • we usually refer to the logical address as a virtual address.
     • logical addresses generated by a program is a logical address space.
     • physical addresses corresponding to these logical addresses is a physical address space.
     • The run-time mapping from virtual to physical addresses is done by a hardware device called the memory-management unit (MMU).
     • The base register is now called a relocation register
     • The value in the relocation register is added to every address generated by a user process at the time the address is sent to memory
     • For example, if the base is at 14000, then an attempt by the user to address location 0 is dynamically relocated to location 14000; an access to location 346 is mapped to location 14346.
   • 8.1.4 Dynamic Loading
     • To obtain better memory-space utilization, we can use dynamic loading.
     • All routines are kept on disk in a relocatable load format. The main program is loaded into memory and is executed. When a routine needs to call another routine, the calling routine first checks to see whether the other routine has been loaded. If it has not, the relocatable linking loader is called to load the desired routine into memory and to update the program’s address tables to reflect this change. Then control is passed to the newly loaded routine.
     • Dynamic loading does not require special support from the operating system
     • advantage of dynamic loading is that a routine is loaded only when it is needed.
   • 8.1.5 Dynamic Linking and Shared Libraries
     • Dynamically linked libraries are system libraries that are linked to user programs when the programs are run
     • Some operating systems support only static linking
     • With dynamic linking, a stub is included in the image for each libraryroutine reference. The stub is a small piece of code that indicates how to locate the appropriate memory-resident library routine or how to load the library if the routine is not already present.

3. 8.2 Swapping

   • A process must be in memory to be executed. A process, however, can be swapped temporarily out of memory to a backing store and then brought back into memory for continued execution
   • Swapping makes it possible for the total physical address space of all processes to exceed the real physical memory of the system, thus increasing the degree of multiprogramming in a system.
   • 8.2.1 Standard Swapping
     • The system maintains a ready queue consisting of all processes whose memory images are on the backing store or in memory and are ready to run.
     • Whenever the CPU scheduler decides to execute a process, it calls the dispatcher. The dispatcher checks to see whether the next process in the queue is in memory. If it is not, and if there is no free memory region, the dispatcher swaps out a process currently in memory and swaps in the desired process. It then reloads registers and transfers control to the selected process.
     • The context-switch time in such a swapping system is fairly high.
     • Swapping is constrained by other factors as well. If we want to swap a process, we must be sure that it is completely idle. Of particular concern is any pending I/O.
     • There are two main solutions to this problem: never swap a process with pending I/O, or execute I/O operations only into operating-system buffers.
     • Standard swapping is not used in modern operating systems
   • 8.2.2 Swapping on Mobile Systems
     • typically do not support swapping in any form.
     • Mobile devices generally use flash memory as their persistent storage
       • resulting space constraint is one reason why mobile operating-system designers avoid swapping
       • limited number of writes that flash memory can tolerate before it becomes unreliable and the poor throughput between main memory and flash memory in these devices

4. 8.3 Contiguous Memory Allocation

   • The main memory must accommodate both the operating system and the various user processes.
   • The memory is usually divided into two partitions: one for the resident operating system and one for the user processes.
   • We can place the operating system in either low memory or high memory
     • The major factor affecting this decision is the location of the interrupt vector.
     • Since the interrupt vector is often in low memory, programmers usually place the operating system in low memory as well.
   • In contiguous memory allocation, each process is contained in a single section of memory that is contiguous to the section containing the next process.
   • 8.3.1 Memory Protection
     • a system with a relocation register (Section 8.1.3), together with a limit register (Section 8.1.1), we accomplish our goal.
     • The relocation register contains the value of the smallest physical address; the limit register contains the range of logical addresses (for example, relocation = 100040 and limit = 74600)
   • 8.3.2 Memory Allocation
     • divide memory into several fixed-sized partitions
     • Each partition may contain exactly one process. Thus, the degree of multiprogramming is bound by the number of partitions.
     • In this multiple-partition method, when a partition is free, a process is selected from the input queue and is loaded into the free partition.
     • In the variable-partition scheme, the operating system keeps a table indicating which parts of memory are available and which are occupied.
     • In general, as mentioned, the memory blocks available comprise a set of holes of various sizes scattered throughout memory. When a process arrives and needs memory, the system searches the set for a hole that is large enough for this process. If the hole is too large, it is split into two parts. One part is allocated to the arriving process; the other is returned to the set of holes
       • This procedure is a particular instance of the general dynamic storageallocation problem, which concerns how to satisfy a request of size n from a list of free holes.
         • The first-fit, best-fit, and worst-fit strategies are the ones most commonly used to select a free hole
           • • First fit. Allocate the first hole that is big enough.
             • Searching can start either at the beginning of the set of holes or at the location where the previous first-fit search ended.
           • • Best fit. Allocate the smallest hole that is big enough
             • search the entire list, unless the list is ordered by size.
           • • Worst fit. Allocate the largest hole
             • Again, we must search the entire list
             • This strategy produces the largest leftover hole, which may be more useful than the smaller leftover hole from a best-fit approach.
   • 8.3.3 Fragmentation
     • Both the first-fit and best-fit strategies for memory allocation suffer from external fragmentation
     • As processes are loaded and removed from memory, the free memory space is broken into little pieces. External fragmentation exists when there is enough total memory space to satisfy a request but the available spaces are not contiguous: storage is fragmented into a large number of small holes.
     • Another factor is which end of a free block is allocated.
       • Which is the leftover piece—the one on the top or the one on the bottom?
     • given N allocated blocks, another 0.5 N blocks will be lost to fragmentation
       • That is, one-third of memory may be unusable! This property is known as the 50-percent rule.
     • Memory fragmentation can be internal as well as external.
       • Eg. multiple-partition allocation scheme with a hole of 18,464 bytes. Suppose that the next process requests 18,462 bytes. If we allocate exactly the requested block, we are left with a hole of 2 bytes.
         • break the physical memory into fixed-sized blocks and allocate memory in units based on block size. With this approach, the memory allocated to a process may be slightly larger than the requested memory. The difference between these two numbers is internal fragmentation—unused memory that is internal to a partition.
     • One solution to the problem of external fragmentation is compaction.
       • goal is to shuffle the memory contents so as to place all free memory together in one large block.
       • If relocation is static and is done at assembly or load time, compaction cannot be done (only if relocation is dynamic)
       • The simplest compaction algorithm is to move all processes toward one end of memory; all holes move in the other direction, producing one large hole of available memory.
     • Another possible solution to the external-fragmentation problem is to permit the logical address space of the processes to be noncontiguous, thus allowing a process to be allocated physical memory wherever such memory is available.

5. 8.4 Segmentation

   • hardware provide a memory mechanism that map the programmer’s view to the actual physical memory
   • 8.4.1 Basic Method
     • A logical address space is a collection of segments.
     • Each segment has a name and a length. The addresses specify both the segment name and the offset within the segment.
     • Thus, a logical address consists of a two tuple: <segment-number, offset>
   • 8.4.2 Segmentation Hardware
     • we must define an implementation to map two-dimensional programmer-defined addresses into one-dimensional physical addresses
     • This mapping is effected by a segment table. Each entry in the segment table has a segment base and a segment limit.
     • A logical address consists of two parts: a segment number, s, and an offset into that segment, d. The segment number is used as an index to the segment table. The offset d of the logical address must be between 0 and the segment limit. If it is not, we trap to the operating system (logical addressing attempt beyond end of segment)
     • When an offset is legal, it is added to the segment base to produce the address in physical memory of the desired byte. The segment table is thus essentially an array of base–limit register pairs.
     • We have five segments numbered from 0 through 4. The segments are stored in physical memory as shown. The segment table has a separate entry for each segment, giving the beginning address of the segment in physical memory (or base) and the length of that segment (or limit) . E.g reference to byte 53 of segment 2 is mapped onto location 4300 + 53 = 4353
   • Segmentation permits the physical address space of a process to be noncontiguous. But doesn't prevent external fragmentation

6. 8.5 Paging

   • Paging is another memory-management scheme that offers non contiguous physical memory allocation
   • paging avoids external fragmentation and the need for compaction
   • paging in its various forms is used in most operating systems
   • Paging is implemented through cooperation between the operating system and the computer hardware.
   • 8.5.1 Basic Method
     • breaking physicalmemory into fixed-sized blocks called frames and breaking logical memory into blocks of the same size called pages.
     • When a process is to be executed, its pages are loaded into any available memory frames from their source
       • The backing store is divided into fixed-sized blocks that are the same size as the memory frames or clusters of multiple frames.
     • Every address generated by the CPU is divided into two parts: a page number (p) and a page offset (d)
     • The page number is used as an index into a page table.
     • The page table contains the base address of each page in physical memory. This base address is combined with the page offset to define the physical memory address that is sent to the memory unit
     • The page size (like the frame size) is defined by the hardware. The size of a page is a power of 2, varying between 512 bytes and 1 GB per page
   • If the size of the logical address space is 2m, and a page size is 2n bytes, then the high-order m − n bits of a logical address designate the page number, and the n low-order bits designate the page offset.
   • Here, in the logical address, n = 2 and m = 4. Using a page size of 4 bytes and a physical memory of 32 bytes (8 pages)
   • Logical address 0 is page 0, offset 0. Indexing into the page table, we find that page 0 is in frame 5. Thus, logical address 0 maps to physical address 20 [= (5 × 4) + 0]. Logical address 3 (page 0, offset 3) maps to physical address 23 [= (5 × 4) + 3]. Logical address 4 is page 1, offset 0; according to the page table, page 1 is mapped to frame 6. Thus, logical address 4 maps to physical address 24 [= (6 × 4) + 0]. Logical address 13 maps to physical address 9.
   • When we use a paging scheme, we have no external fragmentation: any free frame can be allocated to a process that needs it. However, we may have some internal fragmentation.
   • paging itself is a form of dynamic relocation
   • Notice that frames are allocated as units. If the memory requirements of a process do not happen to coincide with page boundaries, the last frame allocated may not be completely full. For example, if page size is 2,048 bytes, a process of 72,766 bytes will need 35 pages plus 1,086 bytes. It will be allocated 36 frames, resulting in internal fragmentation of 2,048 − 1,086 = 962 bytes. In the worst case, a process would need n pages plus 1 byte. It would be allocated n + 1 frames, resulting in internal fragmentation of almost an entire frame.
   • Each page of the process needs one frame. Thus, if the process requires n pages, at least n frames must be available in memory. If n frames are available, they are allocated to this arriving process. The first page of the process is loaded into one of the allocated frames, and the frame number is put in the page table for this process. The next page is loaded into another frame, its frame number is put into the page table, and so on (Figure 8.13).
   • The logical addresses are translated into physical addresses. This mapping is hidden from the programmer and is controlled by the operating system
   • Since the operating system is managing physical memory, it must be aware of the allocation details of physical memory—which frames are allocated, which frames are available, how many total frames there are, and so on. This information is generally kept in a data structure called a frame table.
   • 8.5.2 Hardware Support
     • In the simplest case, the page table is implemented as a set of dedicated registers.
     • Every access to memory must go through the paging map, so efficiency is a major consideration. The CPU dispatcher reloads these registers, just as it reloads the other registers. Instructions to load or modify the page-table registers are, of course, privileged, so that only the operating system can change the memory map
       • The use of registers for the page table is satisfactory if the page table is reasonably small (for example, 256 entries)
       • For large page tables the page table is kept in main memory, and a page-table base register (PTBR) points to the page table
         • Changing page tables requires changing only this one register, substantially reducing context-switch time.
         • The problem with this approach is the time required to access a user memory location. It required 2 memory accesses. 1 to get the frame and another to go to the actual offset location
           • The standard solution to this problem is to use a special, small, fastlookup hardware cache called a translation look-aside buffer (TLB).
             • Each entry in the TLB consists of two parts: a key (or tag) and a value.
             • It is typically between 32 and 1,024 entries in size
             • The TLB is used with page tables in the following way. The TLB contains only a few of the page-table entries. When a logical address is generated by the CPU, its page number is presented to the TLB. If the page number is found, its frame number is immediately available and is used to access memory.
             • If the page number is not in the TLB (known as a TLB miss), a memory reference to the page table must be made
             • some TLBs allow certain entries to be wired down, meaning that they cannot be removed from the TLB. Typically, TLB entries for key kernel code are wired down.
             • Some TLBs store address-space identifiers (ASIDs) in each TLB entry. An ASID uniquely identifies each process and is used to provide address-space protection for that process.
             • If the TLB does not support separate ASIDs, then every time a new page table is selected (for instance, with each context switch), the TLB must be flushed (or erased) to ensure that the next executing process does not use the wrong translation information.
             • The percentage of times that the page number of interest is found in the TLB is called the hit ratio. An 80-percent hit ratio, for example, means that we find the desired page number in the TLB 80 percent of the time. If it takes 100 nanoseconds to access memory, then a mapped-memory access takes 100 nanoseconds when the page number is in the TLB. If we fail to find the page number in the TLB then we must first access memory for the page table and frame number (100 nanoseconds) and then access the desired byte in memory (100 nanoseconds), for a total of 200 nanoseconds.
             • To find the effective memory-access time, we weight the case by its probability:
   • The operating system maintains a copy of the page table for each process, just as it maintains a copy of the instruction counter and register contents. This copy is used to translate logical addresses to physical addresses whenever the operating system must map a logical address to a physical address manually. It is also used by the CPU dispatcher to define the hardware page table when a process is to be allocated the CPU. Paging therefore increases the context-switch time.
   • 8.5.3 Protection
     • accomplished by protection bits associated with each frame. Normally, these bits are kept in the page table.
     • Every reference to memory goes through the page table to find the correct frame number. At the same time that the physical address is being computed, the protection bits can be checked to verify that no writes are being made to a read-only page. An attempt to write to a read-only page causes a hardware trap to the operating system (or memory-protection violation).
     • One additional bit is generally attached to each entry in the page table: a valid–invalid bit. When this bit is set to valid, the associated page is in the process’s logical address space and is thus a legal (or valid) page. When the bit is set to invalid, the page is not in the process’s logical address space. Illegal addresses are trapped by use of the valid–invalid bit
     • Suppose, for example, that in a system with a 14-bit address space (0 to 16383), we have a program that should use only addresses 0 to 10468. Given a page size of 2 KB, we have the situation shown in Figure 8.15.
     • Addresses in pages 0, 1, 2, 3, 4, and 5 are mapped normally through the page table. Any attempt to generate an address in pages 6 or 7, however, will find that the valid–invalid bit is set to invalid
     • Notice that this scheme has created a problem. Because the program extends only to address 10468, any reference beyond that address is illegal. However, references to page 5 are classified as valid, so accesses to addresses up to 12287 are valid. Only the addresses from 12288 to 16383 are invalid
       • problem is a result of the 2-KB page size and reflects the internal fragmentation of paging.
       • It would be wasteful in these cases to create a page table with entries for every page in the address range. Most of this table would be unused but would take up valuable memory space.
       • Some systems provide hardware, in the form of a page-table length register (PTLR). Holds size of page table. Checks logical address vs size. Must be in range
   • 8.5.4 Shared Pages
     • An advantage of paging is the possibility of sharing common code.
     • If the text editor consists of 150 KB of code and 50 KB of data space, we need 8,000 KB to support the 40 users.
     • each page 50 KB in size (the large page size is used to simplify the figure). Each process has its own data page
     • Only one copy of the editor need be kept in physical memory. Each user’s page table maps onto the same physical copy of the editor, but data pages are mapped onto different frames.
     • Reentrant code is non-self-modifying code: it never changes during execution.
     • The sharing of memory among processes on a system is similar to the sharing of the address space of a task by threads, described in Chapter 4. Furthermore, recall that in Chapter 3 we described shared memory as a method of interprocess communication

7. 8.6 Structure of the Page Table

   • hierarchical paging, hashed page tables, and inverted page tables.
   • 8.6.1 Hierarchical Paging
     • Most modern computer systems support a large logical address space (232 to 264)
     • For example, consider a system with a 32-bit logical address space. If the page size in such a system is 4 KB (212), then a page table may consist of up to 1 million entries (232/212).
     • Assuming that each entry consists of 4 bytes, each process may need up to 4 MB of physical address space for the page table alone.
     • One way is to use a two-level paging algorithm, in which the page table itself is also paged (Figure 8.17). For example, consider again the system with a 32-bit logical address space and a page size of 4 KB. A logical address is divided into a page number consisting of 20 bits and a page offset consisting of 12 bits.
     • Because we page the page table, the page number is further divided into a 10-bit page number and a 10-bit page offset. Thus, a logical address is as follows:
     • p1 is an index into the outer page table and p2 is the displacement within the page of the inner page table.
     • also known as a forward-mapped page table.
   • 8.6.2 Hashed Page Tables
     • A common approach for handling address spaces larger than 32 bits is to use a hashed page table, with the hash value being the virtual page number.
     • Each entry in the hash table contains a linked list of elements that hash to the same location (to handle collisions). Each element consists of three fields: (1) the virtual page number, (2) the value of the mapped page frame, and (3) a pointer to the next element in the linked list.
     • The algorithm works as follows:
   • 8.6.3 Inverted Page Tables
     • Usually, each process has an associated page table. The page table has one entry for each page that the process is using (or one slot for each virtual address, regardless of the latter’s validity). This table representation is a natural one, since processes reference pages through the pages’ virtual addresses. The operating system must then translate this reference into a physical memory address.

Images and files in the map