background

基本硬件

CPU可直接访问的存储器只有 内存 和 处理器内的寄存器

​ CPU内置寄存器可在一个CPU时钟周期内完成访问，对于寄存器中的内容，CPU可以在一个周期内解析并执行多个指令

​ 对于内存，访存可能需要多个时钟周期。没有数据时，要暂停(stall)

协调速度差异，在CPU和内存之间，增加高速缓存cache

instruction-execution cycle: Fetch an instruction, decode instruction, fetch operands, execute, store results back into memory

为了确保正确操作，需要保护内存。

每个进程有独立空间。两个寄存器：

• base register: 最小的合法物理地址
• limit register: 范围的大小

CPU硬件对user mode产生的每一个地址与寄存器的地址进行比较，实现内存空间的保护。

只有OS可以通过特殊的特权指令加载base register和limit register

地址绑定 address binding

进程在执行时可以在磁盘和内存之间移动，在磁盘上等待调入内存以便执行的进程形成input queue

许多系统允许用户进程放在物理内存的任意位置，用户进程开始地址不必为0

源程序中的地址用符号表示，compiler将symbolic address绑定到relocatable address(如从本模块开始的第14字节)，linker或loader将可重定位地址绑定成absolute address。每次绑定都是从一个地址空间到另一个的映射。

将指令与数据绑定到内存地址有几种情况：

• compile time

  编译时就知道进程将在内存中的驻留地址，可以生成absolute code

  如果将来地址发生变化，必须重新编译代码

• load time

  编译时不知道。编译器生成relocatable code

  绑定延迟到加载时

  如果开始地址发生变化，只需重新加载用户代码引入改变值

• execution time

  进程在执行时可以从一个内存段移到另一个内存段

  绑定延迟到执行时

  需要硬件(如base and limit registers)

logical vs. physical address space

logical address: CPU生成的地址，virtual adderss

physical address: 内存单元看到的地址，即加载到memory-address register的地址

compile-time和load-time的address binding生成相同的逻辑地址和物理地址，但execution-time生成不同的，这种情况称逻辑地址为virtual address

logical address space: 程序所生成的所有逻辑地址的集合

physical address space: 与这些逻辑地址相对应的物理地址的集合

运行时完成从虚拟到物理的地址映射的硬件：MMU(memory-management unit)

relocation register: 用户进程所生成的地址送交内存前，加上relocation register的值

用户程序绝不会看到真正的物理地址(execution-binding只发生在它作为内存地址引用时(比如间接加载和存储时))

用户程序处理逻辑地址，内存映射硬件将逻辑地址映射为物理地址

swapping

进程可以暂时从内存swap到backing store上，需要再次执行时再调入内存

backing store通常是fast disk，容纳所有用户的memory images，提供对这些内存镜像的直接访问。

ready queue包括在backing store和在内存中准备运行的所有进程

如果绑定是在汇编时或加载时所定的，一个交换出的进程必须交换回原来的内存空间，如果绑定是在运行是所定，可以移到不同的位置

roll in, roll out: 交换策略的变种被用在基于优先级的调度算法中

Dispatcher is called whenever the CPU scheduler decides to execute a process

交换系统的context switch time比较长

为了有效使用CPU，需要每个进程的执行时间比交换时间长

交换时间主要是transfer time, 和所交换的内存空间成正比(进程10MB，备份存储是40MBps的硬盘，传入或传出：10MB/40MBps)

如果要换出进程，必须确保该进程完全处于空闲状态

solution to 待处理IO(pending IO)

• 不能换出有待处理IO的进程
• IO操作的执行只能使用OS buffers. double buffering

交换空间通常作为磁盘的一整块，且独立于文件系统。

标准交换使用不多，一些交换的变种得到应用。(不如通常不执行交换，许多进程运行且内存吃紧，开始交换，若系统负荷降低，停止交换)

contiguous memory allocation

内存通常分为两部分，一部分驻留OS，一部分用于用户进程。操作系统通常位于低内存。

连续内存分配：每个进程位于一个连续的内存区域

内存映射和保护

relocation-register scheme:

• relocatio/base register

• limit register

  每个逻辑地址必须小于limit register

MMU动态地将逻辑地址加上relocation register的值后映射成物理地址

relocation-register scheme允许OS动态改变。如果某驱动程序不常用，不必再内存保存数据和代码，transient kernel code根据需要调入或调出，使用这类代码可以在程序运行时动态改变OS大小

memory allocation

• fixed partitioning (MFT)

  多道程序的程度受分区数限制

  internal fragmentation: 进程所分配的内存比所需要大

  • equal-size partitions

  • unequal-size partitions

    queue for each partition

• variable partitioning (MVT)

  variable length and number

  hole: a block of available memory

  OS维护一个表，记录哪些内存可用/已被占用

  recaim的时候如果新孔与其他孔相邻，将这些孔合并成大孔

  从一组可用孔选择一个：fisrst-fit, best-fit, worst-fit

  fisrt fit: 50% rule N个可分配快，0.5N个块为外部碎片，1/3内存不可用

  first和best在时间和利用空间好于worst，first和best利用空间差不多，first更快。

  external fragmentation: 所有可用内存之和可以满足要求，但并不连续

解决外部碎片：

• 紧缩(compaction)

  把所有空闲空间合并成一整块

  紧缩仅在重定位是动态并在运行时可采用

• 允许物理地址空间非连续

  分页/分段

paging 分页

允许进程物理地址空间非连续

帧(frame): 物理内存划分为固定大小的块

页(page): 逻辑内存分为同样大小的块

backing store也划分为固定大小的块(block)

页大小由硬件决定，通常为2的幂(power of 2)，512B~16MB

When a process is to be executed, its pages are loaded into any available memory frames from the blocks.

OS为每个进程维护一个page table, contains the frame location for each page in the process, page table used to translate logical to physical addresse

有internal fragmentation(进程要求内存大小不是页大小的整数倍)

由CPU生成的地址分为两部分：page number(used as an index into a page table), page offset

逻辑地址页号位数：进程可以有多少页决定

物理地址页号位数：帧数决定

分页特定：用户视角的内存与物理内存分离。用户程序将内存作为一整块处理，只包括这一个进程。逻辑地址到物理地址的映射由硬件完成，用户不知道。

分页的硬件支持

每个进程一个页表。页表的指针与其他寄存器的值存入PCB。启动进程时，首先装入用户寄存器。

<256 entries, 页表可作为一组专用寄存器实现；大的页表存在内存中。

• PTBR(Page-table base register)
• PTLR(Page-table length register)

装入或修改页表寄存器的指令是特权级的

访问一个字节需要2次访存(一次页表条目，一次字节)

TLB

解决这个问题：TLB(translation look-aside buffer / associative memory)

The given page number is compared with all keys simultaneously.

page # 和 frame #

• a hit

• a miss

  the page number is used to index the process page table

有的TLB允许有些条目固定下来 wired down(e.g. entries for kernel code)

有的TLB在在每个TLB条目中保存ASID(address-space identifier)，可唯一地标识进程，为进程提供地址空间保护，允许TLB同时包含多个不同进程的条目

EAT(Effective Access Time)

hit ratio: 页号在TLB中被查找到的百分比率

内存保护

分页环境下，内存保护通过与每个帧相关联的保护位实现。这些位保存在页表里。

RW bit: read-write or read-only

valid-invalid bit: 在不在进程的逻辑地址空间中。有点浪费，所以有时用PTLR看页表长度

Any violations result in a trap to the kernel.

页表结构

层次页表 Hierarchical

forward-mapped page table

e.g. VAX(virtual address extension)体系结构支持一种两层分页的变种

页表项长度是页面的地址。页表大小=页面个数*页表项长度 。

哈希页表 Hashed Page Tables

Common in address spaces > 32 bits

哈希页表每一条目包括一个链表的元素，每个元素3个域：1虚拟页码 2所映射的帧号 3指向链表中下一元素的指针

群集页表(clustered page table)类似于哈希页表，不过每一条目包括多页，对于稀疏地址空间有用

反向页表 Inverted Page Table

Rather than each process having a page table and keeping track of all possible logical pages, track all physical pages.

One entry for each real frame of memory.

每个条目包含 保存在真正内存位置的页的虚拟地址 和 拥有该页的进程的信息

整个系统只有一个页表。

Often requires an address-space identifier (ASID) stored in each entry of the page table.

Ensures the mapping of a logical page for a particular process to the corresponding physical page frame.

< process-id, page-number, offset >

减少存储空间，但增加了查找时间。

可以通过哈希页表将查找限制在较少的条目中。访问哈希表时先访问TLB

反向页表实现共享内存困难。共享内存通常作为被映射到一个物理地址的多虚拟地址实现。而反向页表，每个物理页只有一个虚拟页条目。

解决办法：允许页表包含one mapping of a virtual address to the shared physical address

分段 segmentation

用户视角的内存管理方案

每个段有名称和长度。地址指定了段名称和段偏移。

分段：用户通过两个量指定地址，段名称和段偏移；分页：用户只指定一个地址，该地址通过硬件分为页码和偏移，对用户透明

<segment-number, offset>

二维用户定义地址映射为一维物理地址，通过段表(segment table)实现，段表每个条目有segment base和segment limit

STBR(segment-table base register): points to the segment table’s location in memory

STLR(segment-table limit register): indicates number of segments used by a program

最后修改于 2020-02-28