Operating Systems Lecture Notes (2024-2025) PDF

Year: 2024-2025 Fall Semester Operating Systems Dr. Wafaa Samy Dr. Hanaa Eissa Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.1 Modified by Dr. Wafaa Samy ...

Year: 2024-2025 Fall Semester Operating Systems Dr. Wafaa Samy Dr. Hanaa Eissa Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.1 Modified by Dr. Wafaa Samy  Chapter 9: Main Memory (Part 2) Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 Modified by Dr. Wafaa Samy  Chapter 9: Memory Management  Background  Contiguous Memory Allocation  Segmentation  Paging  Swapping Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.3 Modified by Dr. Wafaa Samy  Contiguous Allocation  Main memory must support both OS and user processes.  Limited resource, must allocate efficiently. We therefore need to allocate main memory in the most efficient way possible.  Contiguous memory allocation is one early method.  Main memory is usually divided into two partitions: one for the operating system and one for the user processes. Resident operating system, usually held in low memory with interrupt vector. User processes then held in high memory. We usually want several user processes to reside in memory at the same time. Each process contained in single contiguous section of memory.  We therefore need to consider how to allocate available memory to the processes that are waiting to be brought into memory.  In contiguous memory allocation, each process is contained in a single section of memory that is contiguous to the section containing the next process. Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.4 Modified by Dr. Wafaa Samy  Variable Partition  Variable partition: One of the simplest methods of allocating memory is to assign processes to variably sized partitions in memory, where each partition may contain exactly one process. The OS 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, a hole. Eventually, memory contains a set of holes of various sizes.  As processes enter the system, 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, where it can then compete for CPU time.  When a process terminates, it releases its memory, which the operating system may then provide to another process. Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.5 Modified by Dr. Wafaa Samy  Variable Partition (Cont.)  For Example: Initially, the memory is fully utilized, containing processes 5, 8, and 2. After process 8 leaves, there is one contiguous hole. Later on, process 9 arrives and is allocated memory. Then, process 5 departs, resulting in two noncontiguous holes. Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.6 Modified by Dr. Wafaa Samy  Variable Partition (Cont.)  Multiple-partition allocation: Degree of multiprogramming limited by number of partitions. Variable-partition sizes for efficiency (sized to a given process’ needs). Hole – block of available memory; holes of various size are scattered throughout memory. When a process arrives, it is allocated memory from a hole large enough to accommodate it. Process exiting frees its partition, adjacent free partitions combined (merged) to form one larger hole. Operating system maintains information about: a) allocated partitions. b) free partitions (holes). Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.7 Modified by Dr. Wafaa Samy  Dynamic Storage-Allocation Problem  How to satisfy a request of size n from a list of free holes?  There are many solutions to this problem. The first-fit, best-fit, and worst-fit strategies are the most commonly used to select a free hole from the set of available holes. 1. First-fit: Allocate the first hole that is big enough. We can stop searching as soon as we find a free hole that is large enough. 2. Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size. This method produces the smallest leftover hole. 3. Worst-fit: Allocate the largest hole; must also 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.  Note: Simulations have shown that both first-fit and best-fit are better than worst-fit in terms of speed and storage utilization. First-fit and best-fit: first fit is generally faster. Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.8 Modified by Dr. Wafaa Samy  Example (1)  Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)?  Which algorithm makes the most efficient use of memory? memory partitions 100 500 200 300 600 Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.9 Modified by Dr. Wafaa Samy  Example (1): First-Fit Algorithm  Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)?  Which algorithm makes the most efficient use of memory? memory partitions 100 500 200 300 600 Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.10 Modified by Dr. Wafaa Samy  Example (1): Best-Fit Algorithm  Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)?  Which algorithm makes the most efficient use of memory? memory partitions 100 500 200 300 600 Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.11 Modified by Dr. Wafaa Samy  Example (1): Worst-Fit Algorithm  Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)?  Which algorithm makes the most efficient use of memory? Best-fit algorithm. memory partitions 100 500 200 300 600 Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.12 Modified by Dr. Wafaa Samy  Example (2) Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.13 Modified by Dr. Wafaa Samy  Example (2) Solution Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.14 Modified by Dr. Wafaa Samy  Example (2) Solution (Cont.) Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.15 Modified by Dr. Wafaa Samy  Fragmentation  Memory fragmentation can be internal as well as external. 1. External Fragmentation – total memory space exists to satisfy a request, but it is not contiguous. Storage is fragmented into a large number of small holes. This fragmentation problem can be severe. If all these small pieces of memory were in one big free block instead, we might be able to run several more processes. Both the first-fit and best-fit strategies for memory allocation suffer from external fragmentation. 2. Internal Fragmentation – allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used. Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.16 Modified by Dr. Wafaa Samy  Fragmentation (Cont.)  One solution: Reduce external fragmentation by compaction: Shuffle memory contents to place all free memory together in one large block. Compaction is possible only if relocation is dynamic, and is done at execution time.  Another possible solution to the external-fragmentation problem is to permit the logical address space of processes to be noncontiguous, thus allowing a process to be allocated physical memory wherever such memory is available. This is the strategy used in paging, the most common memory- management technique for computer systems. Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.17 Modified by Dr. Wafaa Samy  Segmentation  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 System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.18 Modified by Dr. Wafaa Samy  User’s View of a Program Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.19 Modified by Dr. Wafaa Samy  Logical View of Segmentation 1 4 1 2 3 2 4 3 user space physical memory space Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.20 Modified by Dr. Wafaa Samy  Paging  Physical address space of a process can be noncontiguous; process is allocated physical memory whenever the latter is available:  The basic method for implementing paging involves: 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. Backing store likewise split into pages (fixed-sized blocks). 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 per-process page table to translate logical to physical addresses.  Advantages: Avoids external fragmentation. Avoids problem of varying sized memory chunks.  Disadvantage: Still have Internal fragmentation.  Because it offers numerous advantages, paging in its various forms is used in most operating systems. Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.21 Modified by Dr. Wafaa Samy  Address Translation Scheme  The logical 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. page number page offset p d m -n n For given logical address space 2m and page size 2n # means number  Paging Arithmetic laws: Page size = frame size = 2n (where n is the # of bits in offset part). Logical address space (size) = 2m (where m the # of bits in logical address). Logical address space (size) = # of pages x page size Physical address space (size) = 2x (where x is the # of bits in physical address). Physical address space (size) = # of fames x frame size # of pages = # of entries (records) in page table = # of pages Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.22 Modified by Dr. Wafaa Samy  Example (3)  Consider a logical address space of 64 pages of 1024 words each, mapped onto a physical memory of 32 frames. a) How many bits are there in the logical address? b) How many bits are there in the physical address? page number page offset  Answer: p d a) m =? m -n n Size of logical address space = 2m = # of pages × page size  2m = 64 × 1024 = 26 × 210 =216  Number of required bits in the physical address = m = 16 bits b) Let (x) is number of bits in the physical address , x =?  Size of physical address space = 2x  Size of physical address space = # of frames × frame size  (frame size = page size )  Size of physical address space = 32 × 1024  2x =25 × 210 = 215  Number of required bits in the physical address = x = 15 bits Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.23 Modified by Dr. Wafaa Samy  Paging Hardware  The steps taken by the MMU to translate a logical address generated by the CPU to a physical address: 1. Extract the page number p and use it as an index into the page table. 2. Extract the corresponding frame number f from the page table. 3. Replace the page number p in the logical address with the frame number f. The page number is used as an index into a per-process page table. The page table contains the base address of each frame in physical memory, and the offset is the location in the frame being referenced. Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.24 Modified by Dr. Wafaa Samy  Paging Model of Logical and Physical Memory Example: In the logical address, n=2 and m=4. Using a page size of 4 bytes and a physical memory of 32 bytes (8 frames). Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.25 Modified by Dr. Wafaa Samy Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018 8.26 Modified by Dr. Wafaa Samy