Chapter 7 Memory Management

Chapter 7 Memory Management

CS 345 Stalling’s Chapter # Project 1: Computer System Overview 2: Operating System Overview 4 P1: Shell 3: Process Description and Control 4: Threads 4 P2: Tasking 5: Concurrency: ME and Synchronization 6: Concurrency: Deadlock and Starvation 6 P3: Jurassic Park 7: Memory Management 8: Virtual memory 6 P4: Virtual Memory 9: Uniprocessor Scheduling 10: Multiprocessor and Real-Time Scheduling 6 P5: Scheduling 11: I/O Management and Disk Scheduling 12: File Management 8 P6: FAT Student Presentations 6 BYU CS 345 Memory Management 2

Chapter 7 Learning Objectives After studying this chapter, you should be able to: Discuss the principal requirements for memory management. Understand the reason for memory partitioning and explain the various techniques that are used. Understand and explain the concept of paging. Understand and explain the concept of segmentation. Assess the relative advantages of paging and segmentation. Summarize key security issues related to memory management. Describe the concepts of loading and linking. BYU CS 345 Memory Management 3

Requirements Memory Management Requirements Relocation Protection Allow processes to share data/programs Logical Organization Prevent processes from interfering with the O.S. or other processes Often integrated with relocation Sharing Users generally don’t know where they will be placed in main memory May swap in at a different place (pointers?) Generally handled by hardware Support modules, shared subroutines Physical Organization Main memory verses secondary memory Overlaying BYU CS 345 Memory Management 4

Address Binding A process must be tied to a physical address at some point (bound) Binding can take place at 3 times Compile time Load time Always loaded to same memory address relocatable code stays in same spot once loaded Execution time BYU CS 345 may be moved during execution special hardware needed Memory Management source Compiler/Assembler object Linker load module Loader Executable 5

Memory Management Techniques 1. Fixed Partitioning Divide memory into partitions at boot time, partition sizes may be equal or unequal but don’t change Simple but has internal fragmentation 2. Dynamic Partitioning Create partitions as programs loaded Avoids internal fragmentation, but must deal with external fragmentation 3. Simple Paging Divide memory into equal-size pages, load program into available pages No external fragmentation, small amount of internal fragmentation BYU CS 345 Memory Management 6

Memory Management Techniques 4. Simple Segmentation Divide program into segments No internal fragmentation, some external fragmentation 5. Virtual-Memory Paging Paging, but not all pages need to be in memory at one time Allows large virtual memory space More multiprogramming, overhead 6. Virtual Memory Segmentation Like simple segmentation, but not all segments need to be in memory at one time Easy to share modules More multiprogramming, overhead BYU CS 345 Memory Management 7

Fixed Partitioning 1. Fixed Partitioning Main memory divided into static partitions Simple to implement Inefficient use of memory Small programs use entire partition Maximum active processes fixed Internal Fragmentation Operating System 8M 8M 8M 8M 8M BYU CS 345 Memory Management 8

Fixed Partitioning Fixed Partitioning Variable-sized partitions assign smaller programs to smaller partitions lessens the problem, but still a problem Placement 2M 4M 6M 8M Which partition do we use? Operating System 8M Want to use smallest possible partition What if there are no large jobs waiting? Can have a queue for each partition size, or one queue for all partitions 8M 12 M Used by IBM OS/MFT, obsolete Smaller partition by using overlays BYU CS 345 Memory Management 9

Fixed Partitioning Placement Algorithm w/Partitions Equal-size partitions because all partitions are of equal size, it does not matter which partition is used Unequal-size partitions can assign each process to the smallest partition within which it will fit queue for each partition processes are assigned in such a way as to minimize wasted memory within a partition BYU CS 345 Memory Management 10

Fixed Partitioning Process Queues When its time to load a process into main memory the smallest available partition that will hold the process is selected Operating System New Processes BYU CS 345 Operating System New Processes Memory Management 11

2. Dynamic Partitioning Partitions are of variable length and number Process is allocated exactly as much memory as required Eventually get holes in the memory. Dynamic Partitioning external fragmentation Must use compaction to shift processes so they are contiguous and all free memory is in one block BYU CS 345 Memory Management 12

Dynamic Partitioning Allocation Strategies First Fit Best Fit Search through all the spots, allocate the spot in memory that most closely matches requirements. Next Fit Allocate the first spot in memory that is big enough to satisfy the requirements. Scan memory from the location of the last placement and choose the next available block that is large enough. Worst Fit The largest free block of memory is used for bringing in a process. BYU CS 345 Memory Management 13

Dynamic Partitioning Which Allocation Strategy? The first-fit algorithm is not only the simplest but usually the best and the fastest as well. The next-fit algorithm will more frequently lead to an allocation from a free block at the end of memory. May litter the front end with small free partitions that must be searched over on subsequent first-fit passes. Results in fragmenting the largest block of free memory. Compaction may be required more frequently. Best-fit is usually the worst performer. Guarantees the fragment left behind is as small as possible. Main memory quickly littered by blocks too small to satisfy memory allocation requests. BYU CS 345 Memory Management 14

Dynamic Partitioning Dynamic Partitioning Placement Algorithm 8K 8K 12K 12K Allocate 18K 22K First Fit Last allocated 18K block (14K) Next Fit 6K 2K Best Fit 8K 8K 6K 6K 14K 14K 36K 20K Allocated block Free block BYU CS 345 Before After Memory Management 15

Dynamic Partitioning Memory Fragmentation As memory is allocated and deallocated fragmentation occurs External Enough space exists to launch a program, but it is not contiguous Internal Allocate more memory than asked for to avoid having very small holes BYU CS 345 Memory Management 16

Dynamic Partitioning Memory Fragmentation Statistical analysis shows that given N allocated blocks, another 0.5 N blocks will be lost due to fragmentation. On average, 1/3 of memory is unusable (50-percent rule) Solution – Compaction. Move allocated memory blocks so they are contiguous Run compaction algorithm periodically How often? When to schedule? BYU CS 345 Memory Management 17

Dynamic Partitioning Buddy System Tries to allow a variety of block sizes while avoiding excess fragmentation Blocks generally are of size 2k, for a suitable range of k Initially, all memory is one block All sizes are rounded up to 2s If a block of size 2s is available, allocate it Else find a block of size 2s 1 and split it in half to create two buddies If two buddies are both free, combine them into a larger block Largely replaced by paging Seen in parallel systems and Unix kernel memory allocation BYU CS 345 Memory Management 18

Address Translation

Address Types Programmers refer to a memory address (address space) as the way to access a memory cell (addressability). Logical (relative) Linear (virtual) Reference to a memory location independent of the current assignment of data to physical memory Consists of a segment and an offset Address expressed as a location relative to some known base address Mapped via segmentation Physical (memory bus) BYU CS 345 The absolute address or actual memory location Mapped via paging Memory Management 20

Hardware Support for Relocation Logical address Process Control Block Base Register Adder Physical address Program Comparator Bounds Register Interrupt to operating system Data / Stack Kernel Stack Process image in main memory BYU CS 345 Memory Management 21

Base/Bounds Relocation Base Register Bounds Register Used to detect accesses beyond the end of the allocated memory May have length instead of end address Provides protection to system Easy to move programs in memory Holds beginning physical address Add to all program addresses These values are set when the process is loaded and when the process is swapped in Largely replaced by paging BYU CS 345 Memory Management 22

Simple Paging 3. Simple Paging Partition memory into small equal-size chunks and divide each process into the same size chunks The chunks of a process are called pages and chunks of memory are called frames Operating system maintains a page table for each process contains the frame location for each page in the process memory address consist of a page number and offset within the page BYU CS 345 Memory Management 23

Simple Paging Paging (continued ) Page size typically a power of 2 to simplify the paging hardware Example (16-bit address, 1K pages) 010101 011011010 Top 6 bits (010101) page # Bottom 10 bits (011011010) offset within page Common sizes: 512 bytes, 1K, 4K A 0 1 2 3 BYU CS 345 B - C 7 8 9 10 D Free 4 13 5 14 6 11 12 Memory Management 24

Simple Paging Paging Frame Number 0 A.0 0 0 1 A.1 1 2 A.2 3 A.3 B.0 D.0 4 6 B.1 D.1 B.2 D.2 7 C.0 8 9 C.1 C.2 10 C.3 11 D.3 D.4 5 12 7 13 1 0 1 8 14 2 2 2 9 3 3 3 10 Process C Process A 0 4--- 0 4 1 5--- 1 5 2 6--- 2 6 3 11 4 12 Process B Free Frame List Process D 13 14 BYU CS 345 Memory Management 25

Simple Segmentation 4. Simple Segmentation Program views memory as a set of segments of varying sizes Supports user view of memory Easy to handle growing data structures Easy to share libraries, memory Privileges can be applied to a segment Programs may use multiple segments Implemented with segmentation tables Array of base-limit register pairs BYU CS 345 Beginning address (segment base) Size (segment limit) Status bits (Present, Modified, Accessed, Permission, Protection) Memory Management 26

Simple Segmentation Simple Segmentation A logical address consists of two parts: a segment identifier and an offset that specifies the relative address within the segment. The segment identifier is The a 16-bit the Segment cs register field includescalled a 2-bit field the field. Current Privilege Selector, while the offset That is aspecifies 32-bit Level (CPL) of the CPU. To make it easy to retrieve segment selectors quickly, the processor provides segmentation registers whose only purpose is to hold Segment Selectors. cs: points to a segment containing program instructions ss: points to a segment containing the current program stack ds: points to a segment containing global and static data es: \ fs: points to a segment containing user data gs: / BYU CS 345 Memory Management 27

Simple Segmentation Segmentation/Paging In Pentium systems CPU generate logical addresses Segmentation unit produces a linear address Paging unit generates physical address in memory (Equivalent to an MMU) logical address CPU BYU CS 345 Segmentation Unit linear address Paging Unit Memory Management physical address Physical Memory 28

BYU CS 345 Memory Management 29