nix

9.     Memory Management

• The memory unit sees only a stream of memory addresses; it does not know how they are generated (by the instruction counter, indexing, indirection, literal addresses, and so on) or what they are for (instructions or data).

9.1.1  Address Binding

• The collection of processes on the disk that is waiting to be brought into memory for execution forms the input queue.

• Addresses may be represented in different ways during compile, load, and execute steps.
• Addresses in the source program are generally symbolic. A compiler will typically bind these symbolic addresses to relocatable addresses (such as “14 bytes from the beginning of this module”).
• The linkage editor or loader will in turn bind these relocatable addresses to absolute addresses.
• The binding of instructions and data to memory addresses can be done at any of these steps.

• Compile Time: If the compiler knows the location a program will reside, the compiler generates absolute code. Example: compile-go systems and MS-DOS .COM-format programs.
• Load Time: A compiler may not know the absolute address. So, the compiler generates relocatable code. Address binding is delayed until load time.
• Execution Time: If the process may be moved in memory during its execution, then address binding must be delayed until run time. This is the commonly used scheme.

9.1.2  Logical- Versus Physical-Address Space

• Logical Address: the address generated by the CPU.
• Physical Address: the address seen and used by the memory unit.
• Virtual Address: Run-time binding may generate different logical address and physical address. In this case, logical address is also referred to as virtual address. (Logical = Virtual in this text).
• The compile-time and load-time address-binding methods generate identical logical and physical addresses. The execution-time address binding scheme results in differing logical and physical addresses, this logical address is refer to as virtual address.
• The run-time mapping from virtual to physical addresses is done by a hardware device called the memory-management unit (MMU).

9.1.3  Dynamic Loading

• Some routines in a program (e.g., error handling) may not be used frequently.
• With dynamic loading, a routine is not loaded until it is called.
• To use dynamic loading, all routines must be in a relocatable format.
• The main program is loaded and executes.
• When a routine A calls B, A checks to see if B is loaded. If B is not loaded, the relocatable linking loader is called to load B and updates the address table. Then, control is passed to B.

9.1.4  Dynamic Linking and Shared Libraries

• Dynamic loading postpones the loading of routines until run-time. Dynamic linking postpones both linking and loading until run-time.
• With dynamic linking, a stub is included in the image for each library-routine reference.
• A stub is added to each reference of library routine. A tub is a small piece of code that indicates how to locate and load the routine if it is not loaded.
• When a routine is called, its stub is executed. The routine is loaded, the address of that routine replaces the stub, and executes the routine.
• Dynamic linking usually applies to language and system libraries. A Windows DLL is a dynamic linking library.
• Shared libraries: More than one version of a library may be loaded into memory, and each program uses its version information to decide which copy of the library to use. Only programs that are compiled with the new library version are affected by the incompatible changes incorporated in it. Other programs linked before the new library was installed will continue using the older library.
• Dynamic linking generally requires help from the OS. OS can check to see whether the needed routine is in another process’ memory space, or that can allow multiple processes to access the same memory addresses.

9.1.5  Overlays

• Overlays: to enable a process to be larger than the amount of memory allocated to it.
• The idea of overlays is to keep in memory only those instructions and data that are needed at any given time.

• Roll out, roll in: The memory manager can swap out the lower-priority process so that it can load and execute the higher-priority process.
• A process that is swapped out will be swapped back into the same memory space that it occupied previously if binding is done at assembly or load time, then the process cannot be moved to different locations.
• If execution-time binding is being used, then a process can be swapped into a different memory space, because the physical addresses are computed during execution time.
• 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.

• Since the interrupt vector is often in low memory, programmers usually place the OS in low memory as well.

9.3.1  Memory Protection

• Because executables may run in any partition, relocation and protection are needed.
• Recall the base/limit register pair for memory protection.
• It could also be used for relocation.
• Linker generates relocatable code starting with 0. The base register contains the starting address.

• The relocation-register scheme provides an effective way to allow the OS size to change dynamically. A transient operating-system code can be loaded or unloaded dynamically.

9.3.2  Memory Allocation

• Major memory management schemes
  • Monoprogramming Systems: MS-DOS

• Multiprogramming Systems:
  • Fixed partitions
  • Variable Partitions
  • Paging
  • The degree of multiprogramming is bound by the number of partition.
• Why multiprogramming?
  • Suppose a process spends a fraction of p of its time in I/O wait state.
  • Then, the probability of n processes being all in wait state at the same time is pⁿ.
  • The CPU utilization is 1-pⁿ.
  • Thus, the more processes in the system, the higher the CPU utilizatio.
  • Well, since CPU power is limited, throughput decreases when n is sufficiently large.
• Multiprogramming with fixed partitions
  • Memory is divided into n (possibly unequal) partitions.
  • Partitioning can be done at the startup time and altered later on.
  • Each partition may have a job queue. Or, all partitions share the same job queue.

• Multiprogramming with variable partitions:
  • The OS maintains a memory pool. When a job comes in, the OS allocates whatever a job needs.
  • Thus, partition sizes are not fixed, the number of partitions also varies.

• When a memory request comes, we must search all free spaces (i.e., holes) to find a suitable one.
• There are some commonly seen methods (dynamic storage-allocation problem):
  • First fit: Search starts at the beginning of the set of holes and allocate the first large enough hole.
  • Next fit: Search starts from where the previous first-fit search ended.
  • Best-fit: Allocate the smallest hole that is larger than the request one.
  • Worst-fit: Allocate the largest hole that is larger than the request one.
  • Another factor is which end of a free block is allocated.
• If the hole is larger than the requested size, it is cut into two. The one of the requested size is given to the process; the remaining one becomes a new hole.
• When a process returns a memory block, it becomes a hole and must be combined with its neighbors.

• Statistical analysis of first fit reveals that even with some optimization, given N allocated blocks, another 0.5N blocks will be lost due to fragmentation. This property is known as the 50-percent rule.

9.3.3  Fragmentation

• Processes are loaded and removed from memory, eventually the memory will be cut into small holes that are not large enough to run any incoming process.
• Free memory holes between allocated ones are called external fragmentation.
• It is unwise to allocate exactly the requested amount of memory to a process, because of address boundary alignment requirements or the minimum requirement for memory management.
• Thus, memory that is allocated to a partition, but is not used, is called internal fragmentation.

• Compaction for external fragmentation, if processes are relocatable, we may move used memory blocks together to make a larger free memory block. Compaction is possible only if relocation is dynamic, and is done at execution time.

• Paging is memory-management scheme that permits the physical-address space of a process to be noncontiguous.

9.4.1  Basic Method

• The physical memory is divided into fixed-sized page frames, or frames.
• The virtual address space is also divided into blocks of the same size, called pages.
• When a process runs, its pages are loaded into page frames.
• A page table stores the page numbers and their corresponding page frame numbers, sorted by virtual address.
• The virtual address is divided into two fields: page number and offset (with that page).

• Paging schemes do not have external fragmentation, because un-used page frames can be used by the next process.
• Paging systems do have internal fragmentation, because the address space is divided into equal size pages, all but the last one will be filled completely. Thus, the last page contains internal fragmentation and may be 50% full.
• An important aspect of paging is the clear separation between the user’s view of memory and the actual physical memory.
• The frame table has one entry for each physical page frame, indicating whether the latter is free or allocated and, if it is allocated, to which page of which process or processes.

9.4.2  Hardware Support

• Page table may be stored in special registers if the number of pages is small.
• Page table may be stored in physical memory, and a special register, page-table base register, points to the page table.
• Use translation look-aside buffer (TLB). TLB stores recently used pairs (page #, frame #). It compares the input page # against the stored ones. If a match is found, the corresponding frame # is the output. Thus, no physical memory access is required.
• The comparison is carried out in parallel and is fast.
• TLS normally has 64 to 1024 entries.

• If the page number is not in the TLB (known as a TLB miss), a memory reference to the page table must be made.
• Replacement policies of TLB entries range from least recently used (LRU) to random; some TLBs allow entries to be wired down, meaning that they cannot be moved from the TLB.
• Some TLBs store address-space identifiers (ASIDs) in each entry of the TLB. An ASID uniquely identifies each process and is used to provide address space protection for that process.
• A TLB is usually shared by all processes, but a page table is usually allocated for one process.
• The percentage of times that a particular page number is found in the TLB is called the hit ratio.

9.4.3  Protection

• It is not required to protect among users in a paging system, because different processes use different page tables.
• However, we can use a page table length register that stores the length of a process’ page table. In this way, a process cannot access the memory beyond its region. Compare this with the base/limit register pair.
• We can also add read-only, read-write, or execute bits in page table to enforce r-w-e permission.
• We can also add a valid/invalid bit to each page entry to indicate if the page is in memory.

9.4.4  Structure of the Page Table

9.4.4.1         Hierarchical Paging (Multi-Level Page Table, Forward-Mapped Page Table)

• Page page-table.

9.4.4.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:
  • The virtual page number
  • The value of the mapped page frame
  • A pointer to the next element in the linked list
• Clustered page tables are similar to hashed page tables except that each entry in the hash table refers to several pages rather than a single page. Clustered page tables are particularly useful for sparse address spaces where memory references are noncontiguous and scattered throughout the address space.

9.4.4.3         Inverted Page Table

• In a paging system, each process has its own page table, which usually has many entries.
• To save space, we can build a page table which has one entry for each page frame. Thus, the size of this inverted page table is equal to the number of page frames.
• Each entry in an inverted page table has two items:
  • Process ID: the owner of this frame.
  • Page Number: the page number in this frame.
• Each virtual address has three sections:
  • <process-id, page #, offset>
• The inverted page table is sorted by a physical address, but lookups occur on virtual addresses. We can use hash table to limit the search to one-or at most a few-page-table entries.

9.4.5  Shared Pages

• Pages may be shared by multiple processes.
• If the code is a re-entrant (or pure) one, a program does not modify itself, routines can also be shared!

9.5.1  Basic Method

• Segmentation is a memory-management scheme that supports the user view of memory. A logical-address space is a collection of segments. Elements within a segment are identified by their offset from the beginning of the segment.
• A logical address consists of a two tuple: <segment-number, offset>

9.5.2  Hardware

• Each entry of the segment table has a segment base and a segment limit. The segment base contains the starting physical address where the segment resides in memory, whereas the segment limit specifies the length of the segment.
• The segment table is thus essentially an array of base-limit register pairs.

9.5.3  Protection and Sharing

• Because the segments represent a semantically defined portion of the program, it is likely that all entries in the segment will be used the same way.
• The memory-mapping hardware will check the protection bits associated with each segment-table entry to prevent illegal accesses to memory.
• By placing an array in its own segment, the memory-management hardware will automatically check that array indexes are legal and do not stray outside the array boundaries.
• Each process has a segment table associated with it, which the dispatcher uses to define the hardware segment table when this process is given the CPU. Segments are shared when entries in the segment tables of two different processes point to the same physical location.
• The sharing occurs at the segment level, any information can be shared if it is defined to be a segment.
• Code segments typically contain references to themselves. The segment number of the transfer address will be the segment number of the code segment. If we try to share this segment, all sharing processes must define the shared code segment to have the same segment number.
• Read-only data segments that contain no physical pointers may be shared as different segment numbers, as may code segments that refer to themselves not directly, but rather only indirectly.

9.5.4  Fragmentation

• Because segmentation is by its nature a dynamic relocation algorithm, we can compact memory whenever we want.

• Page the segment.
• Logical address (segmentation) -> linear address (paging) -> physical address.