OS Unit 3 full.pdf

OPERATING SYSTEMS Compiled by M S Anand Department of Computer Science & Engineering OPERATING SYSTEMS Introduction Text Book(s): 1. “Operating System Concepts”, Abraham Silberschatz, Peter Baer Galvin, Greg Gagne 9th Edition, John Wiley & Sons, India Edition ,2016. 2. “Ad...

OPERATING SYSTEMS Compiled by M S Anand Department of Computer Science & Engineering OPERATING SYSTEMS Introduction Text Book(s): 1. “Operating System Concepts”, Abraham Silberschatz, Peter Baer Galvin, Greg Gagne 9th Edition, John Wiley & Sons, India Edition ,2016. 2. “Advanced Programming in the Unix Environment”, Richard Stevens and Stephen A Rago, Pearson, 3rd edition, 2017. Reference Book(s): 1. “Operating Systems, Internals and Design Principles”, William Stallings, 9th Edition, Pearson, 2018. 2. “Operating Systems”: Three Easy Pieces, RemziArpaci-Dusseau and Andrea Arpaci Dusseau, http://pages.cs.wisc.edu/~remzi/OSTEP/. 3. “Operating Systems”, Harvey Deitel, Paul Deitel, David Choffnes, 3rd Edition, Prentice Hall, 2004. 4. “Modern Operating Systems”, Andrew S Tanenbaum, 3rd edition, Pearson, 2007. OPERATING SYSTEMS Memory management OPERATING SYSTEMS Memory management Memory Management All data in memory before and after processing All instructions in memory in order to execute Memory management determines what is in memory and when Optimizing CPU utilization and computer response to users Memory management activities Keeping track of which parts of memory are currently being used and by whom Deciding which processes (or parts thereof) and data to move into and out of memory Allocating and de-allocating memory space as needed OPERATING SYSTEMS Memory management Memory management strategies Background Memory is central to the operation of a modern computer system. Memory consists of a large array of words or bytes, each with its own address. The CPU fetches instructions from memory according to the value of the program counter. These instructions may cause additional loading from and storing to specific memory addresses. How does a typical instruction-execution cycle look like? A typical instruction-execution cycle 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. OPERATING SYSTEMS Memory management What does the memory unit see? 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). Accordingly, we can ignore how a program generates a memory address. We are interested only in the sequence of memory addresses generated by the running program. Basic Hardware Main memory and the registers built into the processor itself are the only storage that the CPU can access directly. There are machine instructions that take memory addresses as arguments, but none that take disk addresses. Therefore, any instructions in execution, and any data being used by the instructions, must be in one of these direct-access storage devices. If the data are not in memory, they must be moved there before the CPU can operate on them. OPERATING SYSTEMS Memory management Registers that are built into the CPU are generally accessible within one cycle of the CPU clock. What does this mean? Most CPUs can decode instructions and perform simple operations on register contents at the rate of one or more operations per clock tick What about accessing memory? The same cannot be said of main memory, which is accessed via a transaction on the memory bus. Completing a memory access may take many cycles of the CPU clock. In such cases, the processor normally needs to stall, since it does not have the data required to complete the instruction that it is executing. This situation is intolerable because of the frequency of memory accesses OPERATING SYSTEMS Memory management What is the remedy? The remedy is to add fast memory between the CPU and main memory (cache). Not only are we concerned with the relative speed of accessing physical memory, but we also must ensure correct operation to protect the operating system from access by user processes and, in addition, to protect user processes from one another. This protection must be provided by the hardware. OPERATING SYSTEMS Memory management How can we achieve this objective? We first need to make sure that each process has a separate memory space. To do this, we need the ability to determine the range of legal addresses that the process may access and to ensure that the process can access only these legal addresses. How can this be implemented? We can provide this protection by using two registers, usually a base and a limit, as illustrated in Figure (next slide). The base holds the smallest legal physical memory address; the limit specifies the size of the range. For example, if the base register holds 300040 and the limit register is 120900, then the program can legally access all addresses from 300040 through 420939 (inclusive). OPERATING SYSTEMS Memory management A pair of base and limit registers define the logical address space. OPERATING SYSTEMS Memory management How is protection of memory space accomplished? Protection of memory space is accomplished by having the CPU hardware compare every address generated in user mode with the registers. Any attempt by a program executing in user mode to access operating-system memory or other users' memory results in a trap to the operating system, which treats the attempt as a fatal error (Figure next slide). This scheme prevents a user program from (accidentally or deliberately) modifying the code or data structures of either the operating system or other users. Who loads the relevant values to the base and limit registers? The base and limit registers can be loaded only by the operating system, which uses a special privileged instruction. Since privileged instructions can be executed only in kernel mode, and since only the operating system executes in kernel mode, only the operating system can load the base and limit registers. This scheme allows the operating system to change the value of the registers but prevents user programs from changing the registers' contents. OPERATING SYSTEMS Memory management Hardware Address Protection with Base and Limit Registers OPERATING SYSTEMS Memory management The operating system, executing in kernel mode, is given unrestricted access to both operating system memory and users' memory. This provision allows the operating system to load users' programs into users' memory, to dump out those programs in case of errors, to access and modify parameters of system calls, and so on. 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. Depending on the memory management in use, the process may be moved between disk and memory during its execution. The processes on the disk that are waiting to be brought into memory for execution form the input queue. The normal procedure is to select one of the processes in the input queue and to load that process into memory. As the process is executed, it accesses instructions and data from memory. Eventually, the process terminates, and its memory space is declared available. OPERATING SYSTEMS Memory management At what address can a process be loaded in memory? Most systems allow a user process to reside in any part of the physical memory. Thus, although the address space of the computer starts at 00000, the first address of the user process need not be 00000. This approach affects the addresses that the user program can use. How is this taken care of? In most cases, a user program will go through several steps-some of which may be optional-before being executed (Figure next slide). Addresses may be represented in different ways during these steps. OPERATING SYSTEMS Memory management Multi-step processing of a program OPERATING SYSTEMS Memory management How are the addresses represented in the source code, after compilation and after being loaded into memory? Addresses in the source program are generally symbolic (such as count). 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 the relocatable addresses to absolute addresses (such as 74014). Each binding is a mapping from one address space to another. OPERATING SYSTEMS Memory management 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. For example, if you know that a user process will reside starting at location R, then the generated compiler code will start at that location and extend up from there. If, at some later time, the starting location changes, then it will be necessary to recompile this code. 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. In this case, final binding is delayed until load time. If the starting address changes, we need only reload the user code to incorporate this changed value. OPERATING SYSTEMS Memory management 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. Special hardware must be available for this scheme to work. OPERATING SYSTEMS Memory management Logical v/s 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. However, the execution-time address binding scheme results in differing logical and physical addresses. In this case, we usually refer to the logical address as a virtual address. We use logical address and virtual address interchangeably. The set of all logical addresses generated by a program is a logical address space; the set of all physical addresses corresponding to these logical addresses is a physical address space. Thus, in the execution-time address-binding scheme, the logical and physical address spaces differ. OPERATING SYSTEMS Memory management The run-time mapping from virtual to physical addresses is done by a hardware device called the memory-management unit. (MMU) Dynamic relocation using a relocation register OPERATING SYSTEMS Memory management In the simplest scheme possible, we call the base register the 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. The MS-DOS operating system running on the Intel 80x86 family of processors used four relocation registers when loading and running processes. OPERATING SYSTEMS Memory management Is the user program aware of all this? The user program never sees the real physical addresses. The program can create a pointer to location 346, store it in memory, manipulate it, and compare it with other addresses-all as the number 346. Only when it is used as a memory address (in an indirect load or store, perhaps) is it relocated relative to the base register. The user program deals with logical addresses. The memory-mapping hardware converts logical addresses into physical addresses. This is execution-time binding. The final location of a referenced memory address is not determined until the reference is made. OPERATING SYSTEMS Memory management We now have two different types of addresses. What are they? logical addresses (in the range 0 to max) and physical addresses (in the range R+ 0 to R+ max for a base value R). The user program generates only logical addresses and thinks that the process runs in locations 0 to max. However, these logical addresses must be mapped to physical addresses before they are used. OPERATING SYSTEMS Memory management Dynamic loading A basic assumption which has been made so far is: the entire program and all data of a process are in physical memory for the process to execute. The size of a process has thus been limited to the size of physical memory. To obtain better memory-space utilization, we can use dynamic loading. How does this work? With dynamic loading, a routine is not loaded until it is called. 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. OPERATING SYSTEMS Memory management What is the advantage? The advantage of dynamic loading is that an unused routine is never loaded. This method is particularly useful when large amounts of code are needed to handle infrequently occurring cases, such as error routines. In this case, although the total program size may be large, the portion that is used (and hence loaded) may be much smaller. Do you need any support from OS for dynamic loading? Dynamic loading does not require special support from the operating system. It is the responsibility of the users to design their programs to take advantage of such a method. Operating systems may help the programmer, however, by providing library routines to implement dynamic loading. OPERATING SYSTEMS Memory management Dynamic Linking and Shared Libraries Figure (Slide #15) also shows dynamically linked libraries. Some operating systems support only static linking, in which system language libraries are treated like any other object module and are combined by the loader into the binary program image. Dynamic linking, in contrast, is similar to dynamic loading. Here, though, linking, rather than loading, is postponed until execution time. This feature is usually used with system libraries, such as language subroutine libraries. Without this facility, each program on a system must include a copy of its language library (or at least the routines referenced by the program) in the executable image. This requirement wastes both disk space and main memory. OPERATING SYSTEMS Memory management How is this actually implemented? With dynamic linking, a stub is included in the image for each library routine reference. What is stub? 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. When the stub is executed, it checks to see whether the needed routine is already in memory. If it is not, the program loads the routine into memory. Either way, the stub replaces itself with the address of the routine and executes the routine. Thus, the next time that particular code segment is reached, the library routine is executed directly, incurring no cost for dynamic linking. Under this scheme, all processes that use a language library execute only one copy of the library code. OPERATING SYSTEMS Memory management What other advantage(s) do you see with dynamic linking/loading? This feature can be extended to library updates (such as bug fixes). A library may be replaced by a new version, and all programs that reference the library will automatically use the new version. Without dynamic linking, all such programs would need to be relinked to gain access to the new library. So that programs will not accidentally execute new, incompatible versions of libraries, version information is included in both the program and the library. 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. Versions with minor changes retain the same version number, whereas versions with major changes increment the number. Thus, only programs that are compiled with the new library version are affected by any incompatible changes incorporated in it. Other programs linked before the new library was installed will continue using the older library. OPERATING SYSTEMS Memory management This system is also known as shared libraries. Unlike dynamic loading, dynamic linking generally requires help from the operating system. Why? If the processes in memory are protected from one another, then the operating system is the only entity that can check to see whether the needed routine is in another process's memory space or that can allow multiple processes to access the same memory addresses. We elaborate on this concept when we discuss paging. OPERATING SYSTEMS Memory management Swapping A process must be in memory to be executed. A process, however, can be temporarily swapped out of memory to a backing store and then brought into memory for continued execution. An example? Assume a multiprogramming environment with a round-robin CPU- scheduling algorithm. When a quantum expires, the memory manager will start to swap out the process that just finished and to swap another process into the memory space that has been freed (Figure next slide). In the meantime, the CPU scheduler will allocate a time slice to some other process in memory. When each process finishes its quantum, it will be swapped with another process. Ideally, the memory manager can swap processes fast enough that some processes will be in memory, ready to execute, when the CPU scheduler wants to reschedule the CPU. In addition, the quantum must be large enough to allow reasonable amounts of computing to be done between swaps. OPERATING SYSTEMS Memory management Schematic view of swapping OPERATING SYSTEMS Memory management How can swapping be implemented with priority-based scheduling? A variant of this swapping policy is used for priority-based scheduling algorithms. If a higher-priority process arrives and wants service, the memory manager can swap out the lower-priority process and then load and execute the higher-priority process. When the higher-priority process finishes, the lower-priority process can be swapped back in and continued. This variant of swapping is sometimes called roll out roll in. Normally, a process that is swapped out will be swapped back into the same memory space it occupied previously. This restriction is dictated by the method of address binding. If binding is done at assembly or load time, then the process cannot be easily moved to a different location. If execution-time binding is being used, however, then a process can be swapped into a different memory space, because the physical addresses are computed during execution time. OPERATING SYSTEMS Memory management Swapping requires a backing store. The backing store is commonly a fast disk. What kind of a disk is this? It must be large enough to accommodate copies of all memory images for all users, and it must provide direct access to these memory images. 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. What does the dispatcher do? 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. OPERATING SYSTEMS Memory management The context-switch time in such a swapping system is fairly high. To get an idea of the context-switch time, let us assume that the user process is 100 MB in size and the backing store is a standard hard disk with a transfer rate of 50MB per second. The actual transfer of the 100-MB process to or from main memory takes 100MB/50MB per second= 2 seconds. Assuming an average latency of 8 milliseconds, the swap time is 2008 milliseconds. Since we must both swap out and swap in, the total swap time is about 4016 milliseconds. The major part of the swap time is transfer time. The total transfer time is directly proportional to the amount of memory swapped. If we have a computer system with 4 GB of main memory and a resident operating system taking 1 GB, the maximum size of the user process is 3GB. OPERATING SYSTEMS Memory management However, many user processes may be much smaller than this-say, 100 MB. A 100-MB process could be swapped out in 2 seconds, compared with the 60 seconds required for swapping 3 GB. Clearly, it would be useful to know exactly how much memory a user process is using, not simply how much it might be using. Then we would need to swap only what is actually used, reducing swap time. For this method to be effective, the user must keep the system informed of any changes in memory requirements. Thus, a process with dynamic memory requirements will need to issue system calls (request memory and release memory) to inform the operating system of its changing memory needs OPERATING SYSTEMS Memory management What other factors constrain the swapping process? If we want to swap a process, we must be sure that it is completely idle. Of particular concern is any pending I/0 (Problem?) A process may be waiting for an I/0 operation when we want to swap that process to free up memory. However, if the I/0 is asynchronously accessing the user memory for I/0 buffers, then the process cannot be swapped. Assume that the I/0 operation is queued because the device is busy. If we were to swap out process P1 and swap in process P2, the I/0 operation might then attempt to use memory that now belongs to process P2. How do we solve this? There are two main solutions to this problem: never swap a process with pending I/0, or execute I/0 operations only into operating- system buffers. Transfers between operating-system buffers and process memory then occur only when the process is swapped in. OPERATING SYSTEMS Memory management Generally, swap space is allocated as a chunk of disk, separate from the file system, so that its use is as fast as possible. Currently, standard swapping is used in few systems. It requires too much swapping time and provides too little execution time to be a reasonable memory-management solution. Modified versions of swapping, however, are found on many systems. What modification you can think of? A modification of swapping is used in many versions of UNIX. Swapping is normally disabled but will start if many processes are running and are using a threshold amount of memory. Swapping is again halted when the load on the system is reduced. OPERATING SYSTEMS Memory management Early PCs-which lacked the sophistication to implement more advanced memory-management methods-ran multiple large processes by using a modified version of swapping. A prime example is the Microsoft Windows 3.1 operating system, which supports concurrent execution of processes in memory. If a new process is loaded and there is insufficient main memory, an old process is swapped to disk This operating system does not provide full swapping, however, because the user, rather than the scheduler, decides when it is time to preempt one process for another. Any swapped-out process remains swapped out (and not executing) until the user selects that process to run. Subsequent versions of Microsoft operating systems take advantage of the advanced MMU features now found in PCs (to be discussed later) OPERATING SYSTEMS Memory management Contiguous memory allocation The main memory must accommodate both the operating system and the various user processes. We therefore need to allocate main memory in the most efficient way possible. This section explains one common method, contiguous memory allocation. 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. Where do we place the OS? 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. Thus, we discuss only the situation in which the operating system resides in low memory. The development of the other situation is similar. OPERATING SYSTEMS Memory management We usually want several user processes to reside in memory at the same time. We therefore need to consider how to allocate available memory to the processes that are in the input queue waiting to be brought into memory. In. contiguous memory allocation, each process is contained in a single contiguous section of memory. OPERATING SYSTEMS Memory management Memory mapping and protection When the CPU scheduler selects a process for execution, the dispatcher loads the relocation and limit registers with the correct values as part of the context switch. Because every address generated by a CPU is checked against these registers, we can protect both the operating system and the other users‘ programs and data from being modified by this running process (Figure – next slide) How does the relocation-register scheme help the OS? This scheme provides an effective way to allow the operating system's size to change dynamically. Why should this happen? Example: the operating system contains code and buffer space for device drivers. If a device driver (or other operating-system service) is not commonly used, we do not want to keep the code and data in memory, as we might be able to use that space for other purposes. Such code is sometimes called transient operating-system code. Thus, using this code changes the size of the operating system during program execution. OPERATING SYSTEMS Memory management OPERATING SYSTEMS Memory management Memory allocation strategies Simplest method? Divide memory into several fixed-sized partitions. Each partition may contain exactly one process. 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. When the process terminates, the partition becomes available for another process. This method was originally used by the IBM OS/360 operating system; it is no longer in use. OPERATING SYSTEMS Memory management Variable partition scheme In the scheme, the operating system keeps a table indicating which parts of memory are available and which are occupied. Initially, all memory is available for user processes and is considered one large block of available memory. Eventually, memory contains a set of holes of various sizes. As processes enter the system, they are put into an input queue. The operating system takes into account the memory requirements of each process and the amount of available memory space in determining which processes are allocated memory. When a process is allocated space, it is loaded into memory, and it can then compete for CPU time. When a process terminates, it releases its memory which the operating system may then fill with another process from the input queue. OPERATING SYSTEMS Memory management At any given time, then, we have a list of available block sizes and an input queue. The operating system can order the input queue according to a scheduling algorithm. Memory is allocated to processes until finally, the memory requirements of the next process cannot be satisfied -that is, no available block of memory (or hole) is large enough to hold that process. What can the OS do now? The operating system can then wait until a large enough block is available, or it can skip down the input queue to see whether the smaller memory requirements of some other process can be met. OPERATING SYSTEMS Memory management General scheme for managing memory 1. In general, the memory blocks available comprise a set of holes of various sizes scattered throughout memory. 2. When a process arrives and needs memory, the system searches the set for a hole that is large enough for this process. 3. 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. 4. When a process terminates, it releases its block of memory, which is then placed back in the set of holes. If the new hole is adjacent to other holes, these adjacent holes are merged to form one larger hole. 5. At this point, the system may need to check whether there are processes waiting for memory and whether this newly freed and recombined memory could satisfy the demands of any of these waiting processes OPERATING SYSTEMS Memory management Problem – which free hole (from out of available holes) to select when a new process (of size n) is to be scheduled? There are many solutions to this problem. The first-fit, best-fit and worst-fit strategies are the ones most commonly used to select a free hole from the set of available holes. 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. We can stop searching as soon as we find a free hole that is large enough. Best fit Allocate the smallest hole that is big enough. We must search the entire list, unless the list is ordered by size. This strategy produces the smallest leftover hole. OPERATING SYSTEMS Memory management Worst fit Allocate the largest hole. Again, we must search the entire list, unless it is sorted by size. This strategy produces the largest leftover hole, which may be more useful than the smaller leftover hole from a best-fit approach. Comparison Simulations have shown that both first fit and best fit are better than worst fit in terms of decreasing time and storage utilization. Neither first fit nor best fit is clearly better than the other in terms of storage utilization, but first fit is generally faster. OPERATING SYSTEMS Memory management Example: Given six memory partitions of 300 KB, 600 KB, 350 KB, 200 KB, 750 KB, and 125 KB (in order), how would the first-fit, best- fit, and worst-fit algorithms place processes of size 115 KB, 500 KB, 358 KB, 200 KB, and 375 KB (in order)? Rank the algorithms in terms of how efficiently they use memory OPERATING SYSTEMS Memory management Processes and their sizes P1=115 KB P2=500 KB P3=358 KB P4=200 KB P5=375 KB OPERATING SYSTEMS Memory management Fragmentation Both the first-fit and best-fit strategies for memory allocation suffer from external fragmentation. What is 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. This fragmentation problem can be severe. In the worst case, we could have a block of free (or wasted) memory between every two processes. If all these small pieces of memory were in one big free block instead, we might be able to run several more processes. OPERATING SYSTEMS Memory management Whether we are using the first-fit or best-fit strategy can affect the amount of fragmentation. 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?) No matter which algorithm is used, however, external fragmentation will be a problem. The 50-percent rule Depending on the total amount of memory storage and the average process size, external fragmentation may be a minor or a major problem. Statistical analysis of first fit, for instance, reveals that, even with some optimization, 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. OPERATING SYSTEMS Memory management Memory fragmentation can be internal as well as external. Consider a 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. The overhead to keep track of this hole will be substantially larger than the hole itself. How do you avoid this problem? The general approach to avoiding this problem is to 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 memory that is internal to a partition. OPERATING SYSTEMS Memory management One solution to the problem of external fragmentation is compaction. The goal is to shuffle the memory contents so as to place all free memory together in one large block. Is this always possible? Compaction is not always possible, however. If relocation is static and is done at assembly or load time, compaction cannot be done; compaction is possible only if relocation is dynamic and is done at execution time. If addresses are relocated dynamically, relocation requires only moving the program and data and then changing the base register to reflect the new base address. OPERATING SYSTEMS Memory management When compaction is possible, we must determine its cost. What could be the simplest compaction algorithm? 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. This scheme can be expensive. Any other solution possible? 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. Two complementary techniques achieve this solution: paging and segmentation. These techniques can also be combined. OPERATING SYSTEMS Memory management Paging Physical address space of a process can be noncontiguous; process is allocated physical memory whenever the latter is available Divide physical memory into fixed-sized blocks called frames Size is power of 2, between 512 bytes and 16 Mbytes Divide logical memory into blocks of same size called pages Keep track of all free frames To run a program of size N pages, need to find N free frames and load program Set up a page table to translate logical to physical addresses Backing store likewise split into pages Still have Internal fragmentation OPERATING SYSTEMS Memory management Address Translation Scheme Address generated by CPU is divided into: Page number (p) – used as an index into a page table which contains base address of each page in physical memory Page offset (d) – combined with base address to define the physical memory address that is sent to the memory unit OPERATING SYSTEMS Memory management The hardware support for paging is shown in the figure below. The paging model is shown in the figure (next slide). OPERATING SYSTEMS Memory management Paging Model of Logical and Physical Memory OPERATING SYSTEMS Memory management Address Translation Scheme (cont …) If the size of the logical address space is 2m and a page size is 2n, 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. Thus the logical address is as follows: Here, p is an index into the page table and d is the displacement within the page. OPERATING SYSTEMS Memory management An example (figure – next slide) In the figure, 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), let us show how the programmer’s view of memory can be mapped into physical memory. 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 x 4) + 0], Logical address 3 (page 0, offset 3) maps to physical address 23 [(5 x 4) + 3] OPERATING SYSTEMS Memory management Paging example n=2 and m=4 32-byte memory and 4-byte pages OPERATING SYSTEMS Memory management Thus 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 x 4] + 0] Logical address 13 maps to physical address 9. Note: Paging itself is a form of dynamic relocation. Every logical address is bound by the paging hardware to some physical address. Using paging is similar to using a table of base (or relocation) registers, one for each frame of memory. OPERATING SYSTEMS Memory management When we use a paging scheme, there is no external fragmentation; any free frame can be allocated to a process that needs it. We may have some internal fragmentation. How? 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. OPERATING SYSTEMS Memory management Calculating internal fragmentation Page size = 2,048 bytes Process size = 72,766 bytes 35 pages + 1,086 bytes Internal fragmentation of 2,048 - 1,086 = 962 bytes In the worst case, a process would need n pages plus 1 byte. It would then be allocate n+1 frames resulting in internal fragmentation of almost an entire frame. If process size is independent of page size, we expect internal fragmentation to average one-half page per process (??) Does this mean that small page sizes are desirable? Not really; overhead is involved in each page-table entry, and this overhead is reduced as the size of the page increases. Today, page sizes are typically between 4KB and 8 KB. It can be larger. Solaris supports page sizes of 8KB and 4MB. OPERATING SYSTEMS Memory management Usually, each page-table entry is 4 bytes long, but that size can vary as well. A 32-bit entry can point to one of 232 physical page frames. If frame size is 4 KB, then a system with 4-byte entries can address 244 bytes (or 16 TB) of physical memory. When a process arrives in the system to be executed, its size, expressed in pages, is examined. Each page of the process needs one frame. If the process requires n pages, at least n frames must be available in memory. If n frames are available, they are allocated to the 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 of this process. The next page is loaded into another frame and its frame number is put into the page table … This is depicted in figure (next slide) OPERATING SYSTEMS Memory management Free Frames Free frames before allocation and after allocation OPERATING SYSTEMS Memory management 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. What information does the frame table hold? 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. In addition, the operating system must be aware that user processes operate in user space, and all logical addresses must be mapped to produce physical addresses. If a user makes a system call (to do I/0, for example) and provides an address as a parameter (a buffer for instance), that address must be mapped to produce the correct physical address. OPERATING SYSTEMS Memory management Paging increases the context-switch time. How? 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. OPERATING SYSTEMS Memory management Hardware support Each operating system has its own methods for storing page tables. Most allocate a page table for each process. A pointer to the page table is stored with the other register values (like the instruction counter) in the process control block. When the dispatcher is told to start a process, it must reload the user registers and define the correct hardware page-table values from the stored user page table. Hwardware implementation of the page table The hardware implementation of the page table can be done in several ways. In the simplest case, the page table is implemented as a set of dedicated registers. These registers should be built with very high-speed logic to make the paging-address translation efficient. 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. OPERATING SYSTEMS Memory management The DEC PDP-11 is an example of such an architecture. The address consists of 16 bits, and the page size is 8 KB. The page table thus consists of eight entries that are kept in fast registers. The use of registers for the page table is satisfactory if the page table is reasonably small (for example, 256 entries). Most contemporary computers, however, allow the page table to be very large (for example, 1 million entries). For these machines, the use of fast registers to implement the page table is not feasible. In such cases, 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. OPERATING SYSTEMS Memory management The problem with this approach is the time required to access a user memory location. If we want to access location i, we must first index into the page table, using the value in the PTBR offset by the page number for i. This task requires a memory access. It provides us with the frame number, which is combined with the page offset to produce the actual address. We can then access the desired place in memory. With this scheme, two memory accesses are needed to access a byte (one for the page-table entry, one for the byte). Thus, memory access is slowed by a factor of 2. This delay would be intolerable under most circumstances. We might as well resort to swapping! OPERATING SYSTEMS Memory management The standard solution to this problem is to use a special, small, fast lookup hardware cache, called a translation look-aside buffer (TLB). The TLB is associative, high-speed memory. Each entry in the TLB consists of two parts: a key (or tag) and a value. When the associative memory is presented with an item, the item is compared with all keys simultaneously. If the item is found, the corresponding value field is returned. The search is fast; the hardware, however, is expensive. Typically, the number of entries in a TLB is small, often numbering between 64 and 1,024. OPERATING SYSTEMS Memory management How is TLB useful? 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. The whole task may take less than 10 percent longer than it would if an unmapped memory reference were used. OPERATING SYSTEMS Memory management What if the page number is not found? If the page number is not in the TLB (known as a TLB miss), a memory reference to the page table must be made. When the frame number is obtained, we can use it to access memory (Figure next slide). In addition, we add the page number and frame number to the TLB, so that they will be found quickly on the next reference. What if the TLB is full? If the TLB is already full of entries, the operating system must select one for replacement. Replacement policies range from least recently used (LRU) to random. Furthermore, some TLBs allow certain entries to be meaning that they cannot be removed from the TLB. Typically, TLB entries for kernel code are wired down OPERATING SYSTEMS Memory management Paging hardware with TLB OPERATING SYSTEMS Memory management Some TLBs store address space identifiers (ASID) in each TLB entry. An ASID uniquely identifies each process and is used to provide address-space protection for that process. When the TLB attempts to resolve virtual page numbers, it ensures that the ASID for the currently running process matches the ASID associated with the virtual page. If the ASIDs do not match, the attempt is treated as a TLB miss. In addition to providing address-space protection, an ASID allows the TLB to contain entries for several different processes simultaneously. If the TLB does not support separate ASIDs, then every time a new 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. Otherwise, the TLB could include old entries that contain valid virtual addresses but have incorrect or invalid physical addresses left over from the previous process. OPERATING SYSTEMS Memory management The percentage of times that a particular page number 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 20 nanoseconds to search the TLB and 100 nanoseconds to access memory, then a mapped-memory access takes 120 nanoseconds when the page number is in the TLB. If we fail to find the page number in the TLB (20 nanoseconds), 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 220 nanoseconds. OPERATING SYSTEMS Memory management To find the effective memory access-time, we weight the case by its probability: effective access time = 0.80 x 120 + 0.20 x 220 = 140 nanoseconds. In this example, we suffer a 40-percent slowdown in memory-access time (from 100 to 140 nanoseconds). For a 98-percent hit ratio, we have effective access time = 0.98 x 120 + 0.02 x 220 = 122 nanoseconds. This increased hit rate produces only a 22 percent slowdown in access time. OPERATING SYSTEMS Memory management Memory Protection in a paged environment Memory protection in a paged environment is accomplished by protection bits associated with each frame. Normally, these bits are kept in the page table. One bit can define a page to be read-write or read-only. 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). OPERATING SYSTEMS Memory management We can easily expand this approach to provide a finer level of protection. We can create hardware to provide read-only, read-write, or execute-only protection; or, by providing separate protection bits for each kind of access, we can allow any combination of these accesses. Illegal attempts will be trapped to the operating system. 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. The operating system sets this bit for each page to allow or disallow access to the page. OPERATING SYSTEMS Memory management Valid or invalid bit in a page table OPERATING SYSTEMS Memory management 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 (previous slide). 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, and the computer will trap to the operating system (invalid page reference). 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. This problem is a result of the 2-KB page size and reflects the internal fragmentation of paging. OPERATING SYSTEMS Memory management Rarely does a process use all its address range. In fact many processes use only a small fraction of the address space available to them. 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 to indicate the size of the page table. This value is checked against every logical address to verify that the address is in the valid range for the process. Failure of this test causes an error trap to the operating system. OPERATING SYSTEMS Memory management Shared Pages An advantage of paging is the possibility of sharing common code. This consideration is particularly important in a time-sharing environment. Consider a system that supports 40 users, each of whom executes a text editor. 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. If the code is pure (or re-entrant) however, it can be shared, as shown in Figure (Slide #87). We see a three-page editor-each page 50 KB in size (the large page size is used to simplify the figure)-being shared among three processes. OPERATING SYSTEMS Memory management Each process has its own data page. Re-entrant code is non-self-modifying code: it never changes during execution. Thus, two or more processes can execute the same code at the same time. Each process has its own copy of registers and data storage to hold the data for the process's execution. The data for two different processes will of course, be different. OPERATING SYSTEMS Memory management Shared pages example OPERATING SYSTEMS Memory management 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. Thus, to support 40 users, we need only one copy of the editor (150 KB), plus 40 copies of the 50 KB of data space per user. The total space required is now 2150 KB instead of 8,000 KB-a significant savings. Other heavily used programs can also be shared -compilers, window systems, run-time libraries, database systems, and so on. To be sharable, the code must be re-entrant. The read-only nature of shared code should not be left to the correctness of the code; the operating system should enforce this property. OPERATING SYSTEMS Memory management Structure of the page table Memory structures for paging can get huge using straight-forward methods Consider a 32-bit logical address space as on modern computers Page size of 4 KB (212) Page table would have 1 million entries (232 / 212) If each entry is 4 bytes -> 4 MB of physical address space / memory for page table alone That amount of memory used to cost a lot Don’t want to allocate that contiguously in main memory Hierarchical Paging Hashed Page Tables Inverted Page Tables OPERATING SYSTEMS Memory management Hierarchical paging One simple solution to this problem - divide the page table into smaller pieces. We can accomplish this division in several ways. One way is to use a two-level paging algorithm, in which the page table itself is also paged (Figure next slide). 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: OPERATING SYSTEMS Memory management Two level page table scheme OPERATING SYSTEMS Memory management A logical address (on 32-bit machine with 1K page size) is divided into: a page number consisting of 22 bits a page offset consisting of 10 bits Since the page table is paged, the page number is further divided into: a 12-bit page number a 10-bit page offset Thus, a logical address is as follows: where p1 is an index into the outer page table, and p2 is the displacement within the page of the inner page table Known as forward-mapped page table The address translation scheme is shown in fig (next slide) OPERATING SYSTEMS Memory management Address translation for a two-level 32-bit paging architecture OPERATING SYSTEMS Memory management 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: The virtual page number in the virtual address is hashed into the hash table. The virtual page number is compared with field 1 in the first element in the linked list. If there is a match, the corresponding page frame (field 2) is used to form the desired physical address. If there is no match, subsequent entries in the linked list are searched for a matching virtual page number. This scheme is shown in Figure (next slide) OPERATING SYSTEMS Memory management OPERATING SYSTEMS Memory management 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. Since the table is sorted by virtual address, the operating system is able to calculate where in the table the associated physical address entry is located and to use that value directly. One of the drawbacks of this method is that each page table may consist of millions of entries. These tables may consume large amounts of physical memory just to keep track of how other physical memory is being used. OPERATING SYSTEMS Memory management To solve this problem, we can use an inverted page table. An inverted page table has one entry for each real page (or frame) of memory. Each entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns the page. Thus, only one page table is in the system, and it has only one entry for each page of physical memory. OPERATING SYSTEMS Memory management Figure (next slide) shows the operation of an inverted page table. Inverted page tables often require that an address-space identifier be stored in each entry of the page table, since the table usually contains several different address spaces mapping physical memory. Storing the address-space identifier ensures that a logical page for a particular process is mapped to the corresponding physical page frame. Examples of systems using inverted page tables include the 64-bit UltraSPARC and PowerPC. OPERATING SYSTEMS Memory management OPERATING SYSTEMS Memory management Each virtual address in the system consists of a triple:. Each inverted page-table entry is a pair where the process-id assumes the role of the address-space identifier. When a memory reference occurs, part of the virtual address, consisting of , is presented to the memory subsystem. The inverted page table is then searched for a match. If a match is found—say, at entry i—then the physical address is generated. If no match is found, then an illegal address access has been attempted. OPERATING SYSTEMS Memory management Although this scheme decreases the amount of memory needed to store each page table, it increases the amount of time needed to search the table when a page reference occurs. Because the inverted page table is sorted by physical address, but lookups occur on virtual addresses, the whole table might need to be searched before a match is found. This search would take far too long. To alleviate this problem, we use a hash table, to limit the search to one—or at most a few—page-table entries. Of course, each access to the hash table adds a memory reference to the procedure, so one virtual memory reference requires at least two real memory reads—one for the hash-table entry and one for the page table. OPERATING SYSTEMS Memory management Systems that use inverted page tables have difficulty implementing shared memory (?) Shared memory is usually implemented as multiple virtual addresses (one for each process sharing the memory) that are mapped to one physical address. This standard method cannot be used with inverted page tables; because there is only one virtual page entry for every physical page, one physical page cannot have two (or more) shared virtual addresses. A simple technique for addressing this issue is to allow the page table to contain only one mapping of a virtual address to the shared physical address. This means that references to virtual addresses that are not mapped result in page faults. OPERATING SYSTEMS Memory management Segmentation Memory-management scheme that supports user view of memory A program is a collection of segments A segment is a logical unit such as: main program procedure function method object local variables, global variables common block stack symbol table arrays OPERATING SYSTEMS Memory management User’s view of a program OPERATING SYSTEMS Memory management Logical view of segmentation OPERATING SYSTEMS Memory management Segmentation Architecture Logical address consists of a two tuple: , Segment table – maps two-dimensional physical addresses; each table entry has: base – contains the starting physical address where the segments reside in memory limit – specifies the length of the segment Segment-table base register (STBR) points to the segment table’s location in memory Segment-table length register (STLR) indicates number of segments used by a program; segment number s is legal if s < STLR OPERATING SYSTEMS Memory management Protection With each entry in segment table associate: validation bit = 0  illegal segment read/write/execute privileges Protection bits associated with segments; code sharing occurs at segment level Since segments vary in length, memory allocation is a dynamic storage-allocation problem A segmentation example is shown in the diagram (next slide) OPERATING SYSTEMS Memory management Segmentation Hardware OPERATING SYSTEMS Memory management Example of segmentation OPERATING SYSTEMS Memory management IA-32 Architecture Memory management in IA-32 systems is divided into two components—segmentation and paging—and works as follows: The CPU generates logical addresses, which are given to the segmentation unit. The segmentation unit produces a linear address for each logical address. The linear address is then given to the paging unit, which in turn generates the physical address in main memory. Thus, the segmentation and paging units form the equivalent of the memory-management unit (MMU). This scheme is shown in Figure (next slide). OPERATING SYSTEMS Memory management IA-32 Segmentation The IA-32 architecture allows a segment to be as large as 4 GB, and the maximum number of segments per process is 16 K. The logical address space of a process is divided into two partitions. The first partition consists of up to 8 K segments that are private to that process. The second partition consists of up to 8 K segments that are shared among all the processes. Information about the first partition is kept in the local descriptor table (LDT); information about the second partition is kept in the global descriptor table (GDT). Each entry in the LDT and GDT consists of an 8-byte segment descriptor with detailed information about a particular segment, including the base location and limit of that segment. OPERATING SYSTEMS Memory management The logical address is a pair (selector, offset), where the selector is a 16-bit number: in which s designates the segment number, g indicates whether the segment is in the GDT or LDT, and p deals with protection. The offset is a 32-bit number specifying the location of the byte within the segment in question. The machine has six segment registers, allowing six segments to be addressed at any one time by a process. It also has six 8-byte microprogram registers to hold the corresponding descriptors from either the LDT or GDT. This cache lets the Pentium avoid having to read the descriptor from memory for every memory reference. OPERATING SYSTEMS Memory management IA-32 segmentation. OPERATING SYSTEMS Memory management The linear address on the IA-32 is 32 bits long and is formed as follows. The segment register points to the appropriate entry in the LDT or GDT. The base and limit information about the segment in question is used to generate a linear address. First, the limit is used to check for address validity. If the address is not valid, a memory fault is generated, resulting in a trap to the operating system. If it is valid, then the value of the offset is added to the value of the base, resulting in a 32-bit linear address. This is shown in Figure (previous slide). IA-32 Paging The IA-32 architecture allows a page size of either 4 KB or 4 MB. For 4-KB pages, IA-32 uses a two-level paging scheme in which the division of the 32-bit linear address is as follows: OPERATING SYSTEMS Memory management The IA-32 address translation is shown in more detail in figure (next slide). The 10 high-order bits reference an entry in the outermost page table, which IA-32 terms the page directory. The page directory entry points to an inner page table that is indexed by the contents of the innermost 10 bits in the linear address. Finally, the low-order bits 0–11 refer to the offset in the 4-KB page pointed to in the page table. OPERATING SYSTEMS Memory management – Paging in the IA-32 architecture OPERATING SYSTEMS Memory management One entry in the page directory is the Page Size flag, which—if set— indicates that the size of the page frame is 4 MB and not the standard 4 KB. If this flag is set, the page directory points directly to the 4-MB page frame, bypassing the inner page table; and the 22 low-order bits in the linear address refer to the offset in the 4-MB page frame. To improve the efficiency of physical memory use, IA-32 page tables can be swapped to disk. In this case, an invalid bit is used in the page directory entry to indicate whether the table to which the entry is pointing is in memory or on disk. If the table is on disk, the operating system can use the other 31 bits to specify the disk location of the table. The table can then be brought into memory on demand. OPERATING SYSTEMS Memory management As software developers began to discover the 4-GB memory limitations of 32-bit architectures, Intel adopted a page address extension (PAE), which allows 32-bit processors to access a physical address space larger than 4 GB. The fundamental difference introduced by PAE support was that paging went from a two-level scheme to a three-level scheme, where the top two bits refer to a page directory pointer table. OPERATING SYSTEMS Memory management – IA-64 Support for a 64-bit address space yields an astonishing 264 bytes of addressable memory—a number greater than 16 quintillion (or 16 exabytes). However, even though 64-bit systems can potentially address this much memory, in practice far fewer than 64 bits are used for address representation in current designs. The x86-64 architecture currently provides a 48-bit virtual address with support for page sizes of 4 KB, 2 MB, or 1 GB using four levels of paging hierarchy. OPERATING SYSTEMS Memory management – virtual memory Code needs to be in memory to execute, but entire program rarely used Error code, unusual routines, large data structures Entire program code not needed at same time Consider ability to execute partially-loaded program Program no longer constrained by limits of physical memory Program and programs could be larger than physical memory OPERATING SYSTEMS Memory management – virtual memory Virtual memory is a technique that allows the execution of processes that are not completely in memory. Virtual memory – separation of user logical memory from physical memory Only part of the program needs to be in memory for execution Logical address space can therefore be much larger than physical address space Allows address spaces to be shared by several processes Allows for more efficient process creation More programs running concurrently Less I/O needed to load or swap processes Virtual memory can be implemented via: Demand paging Demand segmentation OPERATING SYSTEMS Memory management – virtual memory Virtual memory that is larger than physical memory OPERATING SYSTEMS Memory management – virtual address space OPERATING SYSTEMS Memory management We allow the heap to grow upward in memory as it is used for dynamic memory allocation. Similarly, we allow for the stack to grow downward in memory through successive function calls. The large blank space (or hole) between the heap and the stack is part of the virtual address space but will require actual physical pages only if the heap or stack grows. Virtual address spaces that include holes are known as sparse address spaces. Using a sparse address space is beneficial because the holes can be filled as the stack or heap segments grow or if we wish to dynamically link libraries (or possibly other shared objects) during program execution. OPERATING SYSTEMS Memory management – shared library using virtual memory OPERATING SYSTEMS Memory management In addition to separating logical memory from physical memory, virtual memory allows files and memory to be shared by two or more processes through page sharing. This leads to the following benefits: System libraries can be shared by several processes through mapping of the shared object into a virtual address space. Although each process considers the libraries to be part of its virtual address space, the actual pages where the libraries reside in physical memory are shared by all the processes. Typically, a library is mapped read-only into the space of each process that is linked with it. Similarly, processes can share memory. Virtual memory allows one process to create a region of memory that it can share with another process. Processes sharing this region consider it part of their virtual address space, yet the actual physical pages of memory are shared. * Pages can be shared during process creation with the fork() system call, thus speeding up process creation OPERATING SYSTEMS Memory management – demand paging Could bring entire process into memory at load time Or bring a page into memory only when it is needed Less I/O needed, no unnecessary I/O Less memory needed Faster response More users Page is needed  reference to it invalid reference  abort not-in-memory  bring to memory Lazy swapper – never swaps a page into memory unless page will be needed Swapper that deals with pages is a pager OPERATING SYSTEMS Memory management – virtual memory Transfer of a Paged Memory to Contiguous Disk Space OPERATING SYSTEMS Memory management – virtual memory With each page table entry a valid–invalid bit is associated (v  in-memory – memory resident, i  not-in-memory) Initially valid–invalid bit is set to i on all entries Example of a page table snapshot: Frame # Valid-invalid bit v v v i i Page table During address translation, if valid–invalid bit in page table entry is i  page fault OPERATING SYSTEMS Memory management – virtual memory Page table when some pages are not in memory OPERATING SYSTEMS Memory management – Page fault What happens if the process tries to access a page that was not brought into memory? Access to a page marked invalid causes a page fault. The paging hardware, in translating the address through the page table, will notice that the invalid bit is set, causing a trap to the operating system. This trap is the result of the operating system’s failure to bring the desired page into memory. The procedure for handling this page fault is straightforward OPERATING SYSTEMS Steps in handling page fault OPERATING SYSTEMS Procedure for handling page faults 1. Check an internal table (usually kept with the process control block) for this process to determine whether the reference was a valid or an invalid memory access. 2. If the reference was invalid, terminate the process. If it was valid but we have not yet brought in that page, page it in now. 3. Find a free frame (by taking one from the free-frame list, for example). 4. Schedule a disk operation to read the desired page into the newly allocated frame. 5. When the disk read is complete, modify the internal table kept with the process and the page table to indicate that the page is now in memory. 6. Restart the instruction that was interrupted by the trap. The process can now access the page as though it had always been in memory. OPERATING SYSTEMS Memory management – Demand paging In the extreme case, we can start executing a process with no pages in memory. When the operating system sets the instruction pointer to the first instruction of the process, which is on a non-memory-resident page, the process immediately faults for the page. After this page is brought into memory, the process continues to execute, faulting as necessary until every page that it needs is in memory. At that point, it can execute with no more faults. This scheme is pure demand paging: never bring a page into memory until it is required. OPERATING SYSTEMS Memory management – Locality of reference Theoretically, some programs could access several new pages of memory with each instruction execution (one page for the instruction and many for data), possibly causing multiple page faults per instruction. This situation would result in unacceptable system performance. Fortunately, analysis of running processes shows that this behavior is exceedingly unlikely. Programs tend to have locality of reference, which results in reasonable performance from demand paging.. OPERATING SYSTEMS Hardware support The hardware to support demand paging is the same as the hardware for paging and swapping: Page table. This table has the ability to mark an entry invalid through a valid–invalid bit or a special value of protection bits. Secondary memory. This memory holds those pages that are not present in main memory. The secondary memory is usually a high- speed disk. It is known as the swap device, and the section of disk used for this purpose is known as swap space. OPERATING SYSTEMS Memory management A crucial requirement for demand paging is the ability to restart any instruction after a page fault. Because we save the state (registers, condition code, instruction counter) of the interrupted process when the page fault occurs, we must be able to restart the process in exactly the same place and state, except that the desired page is now in memory and is accessible. In most cases, this requirement is easy to meet. A page fault may occur at any memory reference. If the page fault occurs on the instruction fetch, we can restart by fetching the instruction again. If a page fault occurs while we are fetching an operand, we must fetch and decode the instruction again and then fetch the operand OPERATING SYSTEMS Memory management Performance of Demand Paging Demand paging can significantly affect the performance of a computer system. Effective access time For most computer systems, the memory-access time, denoted ma, ranges from 10 to 200 nanoseconds. As long as we have no page faults, the effective access time is equal to the memory access time. If, however, a page fault occurs, we must first read the relevant page from disk and then access the desired word. Let p be the probability of a page fault (0 ≤ p ≤ 1). We would expect p to be close to zero—that is, we would expect to have only a few page faults. The effective access time is then effective access time = (1 - p) × ma + p × page fault time. OPERATING SYSTEMS Memory management To compute the effective access time, we must know how much time is needed to service a page fault. A page fault causes the following sequence to occur: 1. Trap to the operating system. 2. Save the user registers and process state. 3. Determine that the interrupt was a page fault. 4. Check that the page reference was legal and determine the location of the page on the disk. 5. Issue a read from the disk to a free frame: a. Wait in a queue for this device until the read request is serviced. b. Wait for the device seek and/or latency time. c. Begin the transfer of the page to a free frame. OPERATING SYSTEMS Memory management 6. While waiting, allocate the CPU to some other user (CPU scheduling, optional). 7. Receive an interrupt from the disk I/O subsystem (I/O completed). 8. Save the registers and process state for the other user (if step 6 is executed). 9. Determine that the interrupt was from the disk. 10. Correct the page table and other tables to show that the desired page is now in memory. 11. Wait for the CPU to be allocated to this process again. 12. Restore the user registers, process state, and new page table, and then resume the interrupt.. OPERATING SYSTEMS Memory management Not all of these steps are necessary in every case. For example, we are assuming that, in step 6, the CPU is allocated to another process while the I/O occurs. This arrangement allows multiprogramming to maintain CPU utilization but requires additional time to resume the page-fault service routine when the I/O transfer is complete. In any case, we are faced with three major components of the page- fault service time: 1. Service the page-fault interrupt. 2. Read in the page. 3. Restart the process. The first and third tasks can be reduced, with careful coding, to several hundred instructions. These tasks may take from 1 to 100 microseconds each. OPERATING SYSTEMS Memory management The page-switch time, however, will probably be close to 8 milliseconds. (A typical hard disk has an average latency of 3 milliseconds, a seek of 5 milliseconds, and a transfer time of 0.05 milliseconds. Thus, the total paging time is about 8 milliseconds, including hardware and software time.) Anyway, we are looking at only the device-service time. If a queue of processes is waiting for the device, we have to add device-queueing time as we wait for the paging device to be free to service our request, increasing even more the time to swap OPERATING SYSTEMS Memory management With an average page-fault service time of 8 milliseconds and a memory access time of 200 nanoseconds, the effective access time in nanoseconds is effective access time = (1 - p) × (200) + p (8 milliseconds) = (1 - p) × 200 + p × 8,000,000 = 200 + 7,999,800 × p. So, the effective access time is directly proportional to the page-fault rate. If one access out of 1,000 causes a page fault, the effective access time is 8.2 microseconds. The computer will be slowed down by a factor of 40 because of demand paging! If we want performance degradation to be less than 10 percent, we need to keep the probability of page faults at the following level: 220 > 200 + 7,999,800 × p, 20 > 7,999,800 × p, p < 0.0000025. OPERATING SYSTEMS Memory management That is, to keep the slowdown due to paging at a reasonable level, we can allow fewer than one memory access out of 399,990 to page-fault. In sum, it is important to keep the page-fault rate low in a demand- paging system. Otherwise, the effective access time increases, slowing process execution dramatically. OPERATING SYSTEMS Memory management An additional aspect of demand paging is the handling and overall use of swap space. Disk I/O to swap space is generally faster than that to the file system. It is a faster file system because swap space is allocated in much larger blocks, and file lookups and indirect allocation methods are not used. The system can therefore gain better paging throughput by copying an entire file image into the swap space at process startup and then performing demand paging from the swap space. Another option is to demand pages from the file system initially but to write the pages to swap space as they are replaced. This approach will ensure that only needed pages are read from the file system but that all subsequent paging is done from swap space.. OPERATING SYSTEMS Memory management Can the file system itself be used as the backing store? Some systems attempt to limit the amount of swap space used through demand paging of binary files. Demand pages for such files are brought directly from the file system. However, when page replacement is called for, these frames can simply be overwritten (because they are never modified), and the pages can be read in from the file system again if needed. Using this approach, the file system itself serves as the backing store. However, swap space must still be used for pages not associated with a file (known as anonymous memory); these pages include the stack and heap for a process. This method appears to be a good compromise and is used in several systems, including Solaris and BSD UNIX. OPERATING SYSTEMS Memory management Demand paging in mobile OS Mobile operating systems typically do not support swapping. Instead, these systems demand-page from the file system and reclaim read-only pages (such as code) from applications if memory becomes constrained. Such data can be demand-paged from the file system if it is later needed. Under iOS, anonymous memory pages are never reclaimed from an application unless the application is terminated or explicitly releases the memory OPERATING SYSTEMS Memory management Copy-on-Write We have already seen that a process can start quickly by demand- paging in the page containing the first instruction. However, process creation using the fork() system call may initially bypass the need for demand paging by using a technique similar to page sharing. This technique provides rapid process creation and minimizes the number of new pages that must be allocated to the newly created process. The fork() system call creates a child process that is a duplicate of its parent. Traditionally, fork() worked by creating a copy of the parent’s address space for the child, duplicating the pages belonging to the parent. OPERATING SYSTEMS Memory management Many child processes invoke the exec() system call immediately after creation. Hence, the copying of the parent’s address space may be unnecessary. Instead, we can use a technique known as copy-on-write, which works by allowing the parent and child processes initially to share the same pages. These shared pages are marked as copy-on-write pages, meaning that if either process writes to a shared page, a copy of the shared page is created. Copy-on-write is illustrated in figures (slides to follow), which show the contents of the physical memory before and after process 1 modifies page C. OPERATING SYSTEMS Memory management For example, assume that the child process attempts to modify a page containing portions of the stack, with the pages set to be copy-on-write. The operating system will create a copy of this page, mapping it to the address space of the child process. The child process will then modify its copied page and not the page belonging to the parent process. When the copy-on-write technique is used, only the pages that are modified by either process are copied; all unmodified pages can be shared by the parent and child processes. Only pages that can be modified need be marked as copy-on-write. Pages that cannot be modified (pages containing executable code) can be shared by the parent and child. Copy-on-write is a common technique used by several operating systems, including Windows XP, Linux, and Solaris OPERATING SYSTEMS Memory management Where does the free page come from? When it is determined that a page is going to be duplicated using copy-on- write, it is important to note the location from which the free page will be allocated. Many operating systems provide a pool of free pages for such requests. These free pages are typically allocated when the stack or heap for a process must expand or when there are copy-on-write pages to be managed. Before process 1 modifies page C OPERATING SYSTEMS Memory management After process 1 modifies page C OPERATING SYSTEMS Memory management Operating systems typically allocate these pages using a technique known as zero-fill-on-demand. Zero-fill-on-demand pages have been zeroed-out before being allocated, thus erasing the previous contents. Several versions of UNIX (including Solaris and Linux) provide a variation of the fork() system call—vfork() (for virtual memory fork)—that operates differently from fork() with copy-on-write. With vfork(), the parent process is suspended, and the child process uses the address space of the parent. Because vfork() does not use copy-on-write, if the child process changes any pages of the parent’s address space, the altered pages will be visible to the parent once it resumes. Therefore, vfork() must be used with caution to ensure that the child process does not modify the address space of the parent. OPERATING SYSTEMS Memory management vfork() is intended to be used when the child process calls exec() immediately after creation. Because no copying of pages takes place, vfork() is an extremely efficient method of process creation and is sometimes used to implement UNIX command-line shell interfaces. OPERATING SYSTEMS Memory management Page Replacement While a user process is executing, let a page fault occur. The operating system determines where the desired page is residing on the disk but then finds that there are no free frames on the free-frame list; all memory is in use (Figure next slide) The operating system has several options at this point. It could terminate the user process. However, demand paging is the operating system’s attempt to improve the computer system’s utilization and throughput. Users should not be aware that their processes are running on a paged system—paging should be logically transparent to the user. So this option is not the best choice. The operating system could instead swap out a process, freeing all its frames and reducing the level of multiprogramming. This option is a good one in certain circumstances. But, the most common solution is: page replacement. OPERATING SYSTEMS Memory management – Need for page replacement OPERATING SYSTEMS Memory management Page replacement takes the following approach. If no frame is free, we find one that is not currently being used and free it. We can free a frame by writing its contents to swap space and changing the page table (and all other tables) to indicate that the page is no longer in memory (Figure next slide). We can now use the freed frame to hold the page for which the process faulted. So, the page-fault service routine has to be modified to include page replacement: OPERATING SYSTEMS Memory management – Page Replacement OPERATING SYSTEMS Memory management 1. Find the location of the desired page on the disk. 2. Find a free frame: a. If there is a free frame, use it. b. If there is no free frame, use a page-replacement algorithm to select a victim frame. c. Write the victim frame to the disk; change the page and frame tables accordingly. 3. Read the desired page into the newly freed frame; change the page and frame tables. 4. Continue the user process from where the page fault occurred. If no frames are free, two page transfers (one out and one in) are required. This situation effectively doubles the page-fault service time and increases the effective access time accordingly OPERATING SYSTEMS Memory management We can reduce this overhead by using a modify bit (or dirty bit). When this scheme is used, each page or frame has a modify bit associated with it in the hardware. The modify bit for a page is set by the hardware whenever any byte in the page is written into, indicating that the page has been modified. When we select a page for replacement, we examine its modify bit. If the bit is set, we know that the page has been modified since it was read in from the disk. In this case, we must write the page to the disk. If the modify bit is not set, however, the page has not been modified since it was read into memory. In this case, we need not write the memory page to the disk: it is already there. This technique also applies to read-only pages (for example, pages of binary code). Such pages cannot be modified; thus, they may be discarded when desired. This scheme can significantly reduce the time required to service a page fault, since it reduces I/O time by one-half if the page has not been modified OPERATING SYSTEMS Memory management We must solve two major problems to implement demand paging: we must develop a frame-allocation algorithm and a page- replacement algorithm. That is, if we have multiple processes in memory, we must decide how many frames to allocate to each process; and when page replacement is required, we must select the frames that are to be replaced. Designing appropriate algorithms to solve these problems is an important task, because disk I/O is so expensive. Even slight improvements in demand-paging methods yield large gains in system performance. There are many different page-replacement algorithms. Every operating system probably has its own replacement scheme. How do we select a particular replacement algorithm? In general, we want the one with the lowest page-fault rate. OPERATING SYSTEMS Memory management We evaluate an algorithm by running it on a particular string of memory references and computing the number of page faults. The string of memory references is called a reference string. We can generate reference strings artificially (by using a random- number generator, for example), or we can trace a given system and record the address of each memory reference. The latter choice produces a large number of data (on the order of 1 million addresses per second). To reduce the number of data, we use two facts. 1. First, for a given page size (and the page size is generally fixed by the hardware or system), we need to consider only the page number, rather than the entire address. 2. Second, if we have a reference to a page p, then any references to page p that immediately follow will never cause a page fault. Page p will be in memory after the first reference, so the immediately following references will not fault. OPERATING SYSTEMS Memory management For example, if we trace a particular process, we might record the following address sequence: 0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105 At 100 bytes per page, this sequence is reduced to the following reference string: 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1 OPERATING SYSTEMS Memory management To determine the number of page faults for a particular reference string and page-replacement algorithm, we also need to know the number of page frames available. Obviously, as the number of frames available increases, the number of page faults decreases. For the reference string considered previously, for example, if we had three or more frames, we would have only three faults—one fault for the first reference to each page. In contrast, with only one frame available, we would have a replacement with every reference, resulting in eleven faults. In general, we expect a curve such as that in Figure (next slide). As the number of frames increases, the number of page faults drops to some minimal level. Of course, adding physical memory increases the number of frames. OPERATING SYSTEMS Memory management OPERATING SYSTEMS Memory management Using the following reference string and assuming three frames 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 FIFO Page Replacement The simplest page-replacement algorithm is a first-in, first-out (FIFO) algorithm. A FIFO replacement algorithm associates with each page the time when that page was brought into memory. When a page must be replaced, the oldest page is chosen. Notice that it is not strictly necessary to record the time when a page is brought in. We can create a FIFO queue to hold all pages in memory. We replace the page at the head of the queue. When a page is brought into memory, we insert it at the tail of the queue. OPERATING SYSTEMS Memory management For our example reference string, our three frames are initially empty. The first three references (7, 0, 1) cause page faults and are brought into these empty frames. The next reference (2) replaces page 7, because page 7 was brought in first. Since 0 is the next reference and 0 is already in memory, we have no fault for this reference. The first reference to 3 results in replacement of page 0, since it is now first in line. Because of this replacement, the next reference, to 0, will fault. Page 1 is then replaced by page 0. This process continues as shown in Figure (next slide). Every time a fault occurs, we show which pages are in our three frames. There are fifteen faults altogether. OPERATING SYSTEMS FIFO replacement algorithm reference string 7012030423071 OPERATING SYSTEMS FIFO replacement algorithm The FIFO page-replacement algorithm is easy to understand and program. However, its performance is not always good. On the one hand, the page replaced may be an initialization module that was used a long time ago and is no longer needed. On the other hand, it could contain a heavily used variable that was initialized early and is in constant use. Notice that, even if we select for replacement a page that is in active use, everything still works correctly. After we replace an active page with a new one, a fault occurs almost immediately to retrieve the active page. Some other page must be replaced to bring the active page back into memory. Thus, a bad replacement choice increases the page-fault rate and slows process execution. It does not, however, cause incorrect execution. OPERATING SYSTEMS Memory management To illustrate the problems that are possible with a FIFO page- replacement algorithm, consider the following reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Figure (next slide) shows the curve of page faults for this reference string versus the number of available frames. Notice that the number of faults for four frames (ten) is greater than the number of faults for three frames (nine)! This most unexpected result is known as Belady’s anomaly: for some page-replacement algorithms, the page-fault rate may increase as the number of allocated frames increases. We would expect that giving more memory to a process would improve its performance. In some early research, investigators noticed that this assumption was not always true. Belady’s anomaly was discovered as a result. OPERATING SYSTEMS Memory management OPERATING SYSTEMS Memory management Optimal Page Replacement One result of the discovery of Belady’s anomaly was the search for an optimal page-replacement algorithm—the algorithm that has the lowest page-fault rate of all algorithms and will never suffer from Belady’s anomaly. Such an algorithm does exist and has been called OPT or MIN. It is simply this: Replace the page that will not be used for the longest period of time. Use of this page-replacement algorithm guarantees the lowest possible pagefault rate for a fixed number of frames OPERATING SYSTEMS Memory management For example, on our sample reference string, the optimal page-replacement algorithm would yield nine page faults, as shown in Figure (next slide). The first three references cause faults that fill the three empty frames. The reference to page 2 replaces page 7, because page 7 will not be used until reference 18, whereas page 0 will be used at 5, and page 1 at 14. The reference to page 3 replaces page 1, as page 1 will be the last of the three pages in memory to be referenced again. With only nine page faults, optimal replacement is much better than a FIFO algorithm, which results in fifteen faults. (If we ignore the first three, which all algorithms must suffer, then optimal replacement is twice as good as FIFO replacement.) In fact, no replacement algorithm can process this reference string in three frames with fewer than nine faults. Unfortunately, the optimal page-replacement algorithm is difficult to implement, because it requires future knowledge of the reference string. OPERATING SYSTEMS Memory management OPERATING SYSTEMS Memory management LRU Page Replacement If the optimal algorithm is not feasible, perhaps an approximation of the optimal algorithm is possible. The key distinction between the FIFO and OPT algorithms (other than looking backward versus forward in time) is that the FIFO algorithm uses the time when a page was brought into memory, whereas the OPT algorithm uses the time when a page is to be used. If we use the recent past as an approximation of the near future, then we can replace the page that has not been used for the longest period of time. This approach is the least recently used (LRU) algorithm. OPERATING SYSTEMS Memory management LRU replacement associates with each page the time of that page’s last use. When a page must be replaced, LRU chooses the page that has not been used for the longest period of time. We can think of this strategy as the optimal page-replacement algorithm looking backward in time, rather than forward. OPERATING SYSTEMS Memory management The result of applying LRU replacement to our example reference string is shown in Figure (next slide). The LRU algorithm produces twelve faults. Notice that the first five faults are the same as those for optimal replacement. When the reference to page 4 occurs, however, LRU replacement sees that, of the three frames in memory, page 2 was used least recently. Thus, the LRU algorithm replaces page 2, not knowing that page 2 is about to be used. When it then faults for page 2, the LRU algorithm replaces page 3, since it is now the least recently used of the three pages in memory. Despite these problems, LRU replacement with twelve faults is much better than FIFO replacement with fifteen. The LRU policy is often used as a page-replacement algorithm and is considered to be good. The major problem is how to implement LRU replacement. An LRU page-replacement algorithm may require substantial hardware assistance. The problem is to determine an order for the frames defined by the time of last use. Two implementations are feasible: OPERATING SYSTEMS Memory management Counters. In the simplest case, we associate with each page-table entry a time-of-use field and add to the CPU a logical clock or counter. The clock is incremented for every memory reference. Whenever a reference to a page is made, the contents of the clock register are copied to the time-of-use field in the page-table entry for that page. In this way, we always have the “time” of the last reference to each page We replace the page with the smallest time value. This scheme requires a search of the page table to find the LRU page and a write to memory (to the time-of-use field in the page table) for each memory access. The times must also be maintained when page tables are changed (due to CPU scheduling). Overflow of the clock must be considered OPERATING SYSTEMS Memory management Stack. Another approach to implementing LRU replacement is to keep a stack of page numbers. Whenever a page is referenced, it is removed from the stack and put on the top. In this way, the most recently used page is always at the top of the stack and the least recently used page is always at the bottom (Figure –next slide). Because entries must be removed from the middle of the stack, it is best to implement this approach by using a doubly linked list with a head pointer and a tail pointer. Removing a page and putting it on the top of the stack then requires changing six pointers at worst. Each update is a little more expensive, but there is no search for a replacement; the tail pointer points to the bottom of the stack, which is the LRU page. This approach is par