Chapter 4. Memory Management
- Unit 4.1 Memory Overview
- Unit 4.2 Paging
- Unit 4.3 Paging Replacement
- Unit 4.4 Segmentation
Unit 4.1
Memory Overview
Presenter Notes
内存是计算机中重要的部件之一，与CPU进行沟通做数据交换，计算机中所有程序的运行都是在内存中进行的
Memory overview
Objectives
- Memory Hierarchy
- Memory Cache
- Types of Memory
- The Memory Manager (MM)
Memory Hierarchy
- Example of Intel Core 2 Duo E7200 at 2.53 GHz
Presenter Notes
分层存储存储管理是将数据存储在不同层级的介质中，在不同的介质之间进行自动或者手动的数据迁移，复制等。在不同的层级之间使用有差别的存储介质，可以在相同成本下既满足性能的需要又满足容量的需要。
Memory Cache
Questions when dealing with cache:
- When to put a new item into the cache.
- Which cache line to put the new item in.
- Which item to remove from the cache when a slot is needed.
- Where to put a newly evicted item in the larger memory.
Presenter Notes
在计算机系统中 CPU 的运行速度往往要比内存速度快上好几百倍甚至更多，为了更多地榨取 CPU 的计算能力，就需要在访问数据的速度上进行提升，否则内存的速度将成为整个系统的性能短板
Types of Memory
Primary Memory (a.k.a. RAM)
- Holds data and programs used by a process that is executing
- Only type of memory that a CPU deals with
Secondary Memory (i.e. hard disk)
- Non-volatile memory used to store data when a process is not executing
Presenter Notes
越靠近 CPU 的存储器成本越高、速度越快、容量越小。比如寄存器通常在16、32、64、128位之间，而缓存则在几十个字节及到几 M 字节之间，内存容量当前通常都在几百 M 字节以上，服务器级的内存也上几十个 G 字节
The Memory Manager (MM)
Purpose
- to manage the use of primary and secondary memory.
Responsible for
- Allocating primary memory to processes
- Moving processes between primary and secondary memory
- Optimizing memory usage
Presenter Notes
分层存储其实是一种在高速小容量层级的介质层与低速大容量层级的介质层之间进行一种自动或者手动数据迁移、复制、管理等操作的一种存储技术及方案
Summary
- Memory Hierarchy
- Memory Cache
- Types of Memory
- The Memory Manager (MM)
Process and memory
Objectives
- Process Memory Layout
- Relocation
Process Memory Layout
- Stack used for local/automatic variables and for passing parameters to function calls. It grows towards heap.
- Heap grows towards stack for dynamic memory allocation
Presenter Notes
程序段(Text): 程序代码在内存中的映射，存放函数体的二进制代码。
初始化过的数据(Data): 在程序运行初已经对变量进行初始化的数据。
未初始化过的数据(BSS): 在程序运行初未对变量进行初始化的数据。
栈: 存储局部、临时变量，函数调用时存储函数的返回指针，用于控制函数的调用和返回。在程序块开始时自动分配内存，结束时自动释放内存，其操作方式类似于数据结构中的栈。
堆: 存储动态内存分配，需要程序员手工分配，手工释放。它与数据结构中的堆是两回事，分配方式类似于链表。
Relocation
- Illustration of the relocation problem.
- (a) (b) logical address (c) physical address
Presenter Notes
物理地址是外部连接使用的、唯一的，它是与地址总线相对应；
逻辑地址是内部和编程使用的、并不唯一，表达形式为“段基地址:偏移地址”
Base and Limit Registers
- Base and limit registers can be used to give each process a separate address space.
Presenter Notes
在程序进行内存读写时内 (MMU) 将虚拟地址映射到物理地址进行读写
Summary
- Process Memory Layout
- Relocation
Memory Partition
Objectives
- Single-Partition
- Fixed-Partition
- Variable-Partition
- Partition Placement Strategies
Single-Partition
- Three simple ways of organizing memory with an operating system and one user process.
Presenter Notes
内存被分为两个区域：系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。其特点是简单，适用于单用户、单任务的操作系统。
Fixed-Partition
|
- Placement Strategies: First Fit, Next Fit, Best Fit.
Presenter Notes
对于固定式分区存储管理来说，其分区大小是固定的，而一个作业的大小不可能与固定的分区大小刚好相等，所以容易产生内部碎片问题，即已分配给某作业的固定分区中有作业使用不到的空闲内存区域。
内碎片是占用分区内未被利用的空间，如图中所示
Fixed-Partition Strategies
- Memory divided into fixed-size regions
- Size of each region usually not equal
- MM will allocate a region to a process that best fits it
- Unused memory within an allocated partition called internal fragmentation
Multiprogramming with Fixed Partitions
Fixed memory partitions
- (a) separate input queues for each partition
- (b) single input queue
Presenter Notes
固定式分区易于实现，开销小。但是缺点有内碎片造成浪费、分区总数固定会限制并发执行的程序数目。
Variable-Partition
- Placement Strategies: First Fit, Next Fit, Best Fit, Worst Fit
Presenter Notes
在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。与固定分区相比较其优点是没有内碎片。但它引入了外碎片，即占用分区之间难以利用的空闲分区(通常是小空闲分区)。
可变分区的分区释放过程会将相邻的空闲分区合并成一个大的空闲分区。
Variable-Partition Strategies :
- MM allocates regions equal to the memory requirements of a process at any given time
- As processes die, holes develop in the memory
- MM inserts new processes into holes
- Results in external fragmentation
- After a while, only small processes will be able to run due to too much external fragmentation
- MM must compact the memory to make more space available for larger processes
Storage Placement Strategies :
- First Fit
- Scan; use the first available hole whose size is sufficient to meet the need.
- Problem: Creates average size holes; more fragementation closer to scan start.
最先适配法 按分区在内存的先后次序从头查找，找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分会产生较多小分区，每次分配时查找时间开销便会增大。
- Next Fit
- Minor variation of first fit: keep track of where last search ended, restart from there.
- Problem: slightly worse performance than first fit.
下次适配法 按分区在内存的先后次序，从上次分配的分区起查找，到最后区时再从头开始，找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大空闲分区不易保留。
- Best Fit
- Use the hole whose size is equal to the need, or if none is equal, the smallest hole that is large enough.
- Problem: Creates small holes that can't be used.
最佳适配法 按分区在内存的先后次序从头查找，找到其大小与要求相差最小的空闲分区进行分配。从个别来看，外碎片较小；但从整体来看，会形成较多外碎片优点是较大的空闲分区可以被保留。
- Worst Fit
- Use the largest available hole.
- Problem: Gets rid of large holes, making it difficult to run large processes.
最坏适配法 按分区在内存的先后次序从头查找，找到最大的空闲分区进行分配。基本不留下小空闲分区，不易形成外碎片。但由于较大的空闲分区不被保留，当对内存需求较大的进程需要运行时，其要求不易被满足。
- Quick Fit
- maintains separate lists for some of the more common sizes requested.
- When a request comes for placement, it finds the closest fit.
- This is a very fast scheme, but a merge is expensive. If merge is not done, memory will quickly fragment into a large number of holes.
Summary
- Single-Partition
- Fixed-Partition
- Variable-Partition
- Partition Placement Strategies
Free Space Management
Objectives
- Bitmaps
- Linked Lists
Memory Management with Bitmaps
- (a) A part of memory with five processes and three holes. The tick marks show the memory allocation units. The shaded regions (0 in the bitmap) are free.
- (b) The corresponding bitmap.
- (c) The same information as a list.
Presenter Notes
位图标记法的思路：假设总的待分配内存的大小为N字节，管理内存的粒度为M字节，并且N=M×K。为了记录这K个内存单元的使用情况，位图标记法将使用一个共有K位的位图，其中每一位的值（0 或者1）用来说明这一位所对应的内存单元是否空闲。由于位图精确地记录了每一个内存单元的空闲或已被使用的情况，所以，当内存管理器接收到一个新的内存申请时，只须扫描位图，就能确定是否有合适的空闲内存可以满足此请求
Memory Management with Linked Lists
- Four neighbor combinations for the terminating process, X.
Presenter Notes
在初始时整个内存块被当做一个大的空闲块加入到空闲链表中。以后当内存管理器接收到一个内存分配请求时，将从空闲链表中找到一个合适的、能提供足够内存的空闲块，并从该空闲块中分离出足够多的内存，交给客户，剩下的内存（如果还有的话）仍然是一个空闲块，而已分配的内存则加入到已分配内存链表中。
Memory Manager Strategies
- Since most OSs offer multiprogramming, we study multiple-partition MM strategies
- We want to maximize the number of (active) processes that can be “in memory” at the same time
- Makes use of “secondary storage”
Summary
- Bitmaps
- Linked Lists
Memory Expansion
Objectives
- Overlaying
- Swapping
Overlaying
- Split process space into multiple, sequentially runnable parts.
- Load one overlay at a time.
- Overlaying is NOT transparent to the programmer.
Presenter Notes
覆盖(overlaying)原理：一个程序的几个代码段或数据段按照时间先后来占用公共的内存空间。将程序必要部分(常用功能)的代码和数据常驻内存；可选部分(不常用功能)平时存放在外存(覆盖文件) 中，在需要时才装入内存。不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。
Swapping
- When a process is blocked, it does not need to be in memory.
- Thus, it is possible to save the memory of blocked process to disk.
- Swapping is transparent to the programmer.
Presenter Notes
交换技术增加并发运行的程序数目，并给用户提供适当的响应时间；与覆盖技术相比，交换技术另一个显著的优点是不影响程序结构。
- Comes from the basis that when a process is blocked, it does not need to be in memory
- Thus, it is possible to save a process’ entire address space to disk
Saving to a “swap file” or a “swap partition”
Pros/Cons
- Simple strategy that does not need much extra hardware (process relocation)
- Inefficient to swap large address spaces for short times!
交换(swapping)技术: 在多个程序并发执行时可以将暂时不能执行的程序(进程)送到外存中，从而获得空闲内存空间来装入新程序(进程)，或读入保存在外存中而处于就绪状态的程序。
- (a) Allocating space for growing data segment.
- (b) Allocating space for growing stack, growing data segment.
暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中(swap out)，而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列(swap in)
Summary
- Overlaying
- Swapping
Reference
- Chapter 3: Memory management, Modern Operating Systems . Forth Edition, Andrew S. Tanenbaum