Class notes for CIS 345 - Class day 11 - Tanenbaum Chapter 4 - Memory 4.4 Page Replacement Algorithms After page fault, OS must choose a page to evict. Changed page must be rewritten to disk. Better to choose little-used page. 4.4.1 The Optimal Page Replacement Algorithm Easy to describe, impossible to increment. Label each page with number of instructions until it will next be used. Throw out page with highest number. Only realizable on second run after recording page references on first run. Useful for comparison purposes only as it is the best possible algorithm. 4.4.2 The Not Recently Used Page Replacement Algorithm 2 status bits used to collect useful statistics about which pages being used. R is set whenever the page is referenced (read or written). M is set when the page is written to (modified). Bits must be updated on every reference. Set by hardware, reset by software. RM bits can be simulated in software if not available in hardware. Start with no pages in memory, RM bits clear. Mark blocks read as Read Only and set R bit. Mark modified pages as Read/Write and set M. Clear R on each clock tick to distinguish recently used pages from not recently used ones. Divide pages into four categories according to current values of R & M bits. 0 = Not Referenced, Not Modified, 1 = Not Reference, Modified, 2=R!M, 3=RM. NRU algorithm removes page at random from lowest numbered nonempty class. Easy to understand, efficient, adequate, but not optimal. 4.4.3 The First-In, First-Out (FIFO) Page Replacement Algorithm Computer maintains a linked-list of all pages currently in memory, with the oldest always at the head of the list. After page fault, page at head is removed and new page placed at tail. Problem: might remove useful pages. FIFO rarely used in pure form. 4.4.4 The Second Chance Page Replacement Algorithm FIFO modified to check R bit for recent activity. Delete if old and unused. Otherwise, place recently referenced page back at tail of list with new load time and cleared reference bit. Degenerates into pure FIFO if all R bits set. 4.4.5 The Clock Page Replacement Algorithm Slight variant of second chance keeps pages on a circular list (ring buffer). When page fault occurs, page being pointed to is inspected as in second chnc. 4.4.6 The Least Recently Used (LRU) Page Replacement Algorithm When page fault occurs, throw out page that has been unused for longest time. Theoretically realizable but not cheap. Must maintain a linked list of all pages in memory, with most recently used at front and LRU at the rear. List must be updated on every memory reference. Expensive special HW needed. One way is to equip HW with a 64 bit counter, +1 after each memory reference, and put values into 64-bit field in each page table entry. Second way is to maintain LRU n x n matrix for n page frames starting all 0. At each reference of page frame k, set all of row k to 1, column k to 0. In this way, the row whose value is lowest is the least recently used. 4.4.7 Simulating LRU in Software Most computers don't have hardware LRU, so it maay be simulated in software. Not Frequently Used algorithm requires a software counter for each page used. OS scans all pages in memory on each clock tick, adds R bit to page's counter. Page fault causes page with the lowest counter to be chosen for replacement. Problem is that old pages have high counts while newer pages are removed. Modification shifts counters right one bit before R bit is added to leftmost. Aging scheme now ensures that older non-referenced pages have leading zeroes. 4.4.8 The Working Set Page Replacement Algorithm Demand paging loads pages as referenced, with common locality of reference. Once the working set of pages is in memory, program runs without thrashing. Model loads pages before process is run (prepaging) to reduce page faults. Class notes for CIS 345 - Class day 11 - Tanenbaum Chapter 4 - Memory 4.8 Segmentation Virtual addresses are one-dimensional, going from 0 to maximum address. Having several virtual address spaces has advantages. Example: Compiler 1. Source text 2. Symbol table 3. Constant table 4. Parse tree 5. Stack. Pure virtual addressing: different parts of above may fill at various rates. If one table fills up, it may bump into the beginning of the next table. Segments solve the problem by providing many independent address spaces. Each segment is linear address space from 0 to some maximum value in memory. Different segments may have various lengths, and may change during execution. Segments may grow and shrink without affecting each other; may fill up also. Specifying address consists of giving a segment number and address within it. Segments may contain procedures, arrays, stacks, variables, but not a mixture. Another advantage: Linking of procedures compiled separately is simplified. Procedure calls after linking use (n,0) to address segment n, word 0 to start. If procedure is modified and recompiled, no other procedures need be changed. In unsegmented system, changing a procedure size can affect other addresses. Segmentation allows use of shared library data between several processes. Example: graphical library for workstations can be put into segment & shared. Since each segment is a logical entity, each can have different protection. Procedure segment is execute only, floating-point array is read/write only. Comparison of paging and segmentation is shown in Figure 4-37 on page 252. 4.8.1 Implementation of Pure Segmentation Pages are fixed size, segments are not. When segments shrink, holes created. This phenomenon known as checkerboarding, can be dealt with by compaction. 4.8.3 Segmentation with Paging: The Intel Pentium Virtual memory on Pentium includes both segmentation and paging. P4 has 16k independent segments, each holding up to 1 billion 32-bit words. Fewer segments are present than in MULTICS, but individual segments larger. P4 VM uses LDT (Local Descriptor Table) and GDT (Global Descriptor Table). Each program has separate LDT, but only one GDT shared by all on computer. LDT describes segments local to each program (code, data, stack, etc.). GDT describes system segments, including operating system itself. To access segment, load selector for that segment into 1 of 6 segment regs. CS=Code Segment, DS=Data Segment, ES=Extra Segment, SS=Stack Segment, etc. Selector is a 16-bit number: 13 bits index, 1 bit GDT/LDT, 2 bits privilege. 13 bits can access 8K segment descriptors. Descriptor 0 forbidden; traps. 13 bit selector gets corresponding 8-byte descriptor from either GDT or LDT. P4 checks to see if offset is beyond the limit of segment; if so, trap out. Granularity bit in descriptor: 0 = # bytes if < 1MB, 1 = # 4k pages if > 1MB. If segment in memory and offset in range, P4 adds 32-bit base field in the descriptor to the offset to form a linear address (see figure 4-45, page 259). Base reg is broken into 3 pieces to be compatible with 286 (base = 24 bits). If paging disabled from global control register, linear address = phys addr. If paging enabled, linear address = virtual address, mapped using page tables. Running program has a page directory of 1024 32-bit entries, each of which points in turn to a page table containing 1024 32-bit entries (two-levels), which finally point to the actual page frames. Dir(10)+page(10)+offset(12). Page table 32 bits: page frame number(20), access, dirty, protection, util. Single page table can handle 4M of memory. Segment shorter than 4 MB has page directory with 1 entry to page table. Takes 2 pages (not 1M pages!). P4 has small associative memory to keep recently used Dir-Page combinations. Base field in descriptor is superfluous when using paging. Only necessary to allow for pure segmentation, and to allow 286 compatibility (no paging). For pure paging, set all segment to select same descriptor: Base=0, Limit=max. 4 protection levels in Pentium, 0 is most privileged, 3 is least. Each program has a level in its PSW, as does each segment in the system. One level may get data from a higher level, but not vice-versa. Procedures may be called at different levels by sending a selector (not addr). Selector identifies a call gate, giving address of procedure to be called. This forces code entry at official entry points, not at arbitrary locations. The MULTICS operating system used a similar concept, called protection rings. Class notes for CIS 345 - Class day 11 - Tanenbaum Chapter 10 - Memory 10.4 Memory Management in UNIX UNIX memory model is simple enough that it can run on a variety of computers. 10.4.1 Fundamental Concepts Each UNIX process has three segments: text, data, stack in its address space. Text segment: Machine instructions that form the program's executable code. Produced by compiler and assembler, read only, fixed size. Data segment: Storage for program's variables, strings, arrays, other data. Two parts: initialized data, uninitialized data (BSS). Initialized data are variables and compiler constants that need an initial value when the program is started. Uninitialized data default to 0 until given a value by program. UD follows ID; size is total of all unitialized variables. When stored on disk as executable file, compiled program is stored first, followed by initialized data, then just a number indicating the total size of all uninitialized data rather than a large block of 0's. This reduces stored size of executable. Data segment can change size. Malloc does this in C programs. Stack segment:Starts at top of virtual address space and grows down toward 0. Stack initially contains environment (shell) variables and all command line arguments. Argc and argv[] can be used to access. Shared text segments allow two or more users to run the same program. Data and stack segments are never shared, as these are written by a process. UNIX can use separate address spaces for instructions and data if supported. 10.4.2 Memory Management System Calls in UNIX No standard system calls for memory management, but programs needing dynamic memory management can use the malloc library procedure. BRK is available to specify data segment size. Mmap and unmap perform memory mapping functions. 10.4.3 Implementation of Memory Management in UNIX Memory full, early UNIX systems swapped entire processes in memory to disk. Swapper handled movement between memory and disk at upper level of scheduler. Swapping (memory to disk) initiated for one of the following reasons: 1. A FORK system call needed memory for a child process. 2. A BRK system call needed to expand a data segment 3. A stack became larger and ran out of the space allocated to it. When time to bring in a process from disk, chose a blocked process to evict. Paging scheduler checked for processes that had been on disk the longest. Easy swap just brought in the process when there was enough space in memory. Hard swap had to remove a process first before moving another in from disk. Repeated until all processes on disk were blocked or memory was full. Paging in UNIX Demand paging: a process need not be entirely in memory in order to run. Only requirement for running is the user structure and the page tables. Text, data and stack segments are brought in dynamically, as referenced. Page daemon checks number of free pages in memory, if low, free more pages. Core map contains info about contents of the page frames. Is <2% of memory. If page fault, OS takes first page frame on free list and reads page into it. If no free pages, process is suspended until page daemon can free page frame. The Page Replacement Algorithm Executed by the page daemon every 240 msec to see if enough free page frames. If not enough frames, daemon transfers pages from memory to disk, else sleep. Two-handed clock algorithm used to speed up normal clock search algorithm. Leading hand clears usage bit, back hand checks, then both hands advance. If hands close together, only heavily used pages won't get thrown out. If back hand just ahead of front hand, defaults to normal clock algorithm. If paging rate too high, swapper removes processes from memory. Swapper chooses processes with max idle time > 20 sec, or, if none, examines the four largest processes and takes the one that has been idle the longest. Swapper checks disk for ready processes and brings in one on disk longest.