Skip to content

Main Memory

:material-circle-edit-outline: 约 1549 个字 :material-clock-time-two-outline: 预计阅读时间 5 分钟

内存管理基本概念：源程序的常规处理流程，地址绑定，逻辑地址空间与物理 地址空间；内存保护；MMU，动态加载，动态链接，交换，地址管理模型，模型指标。 交换技术。 连续分配管理方式：单一连续分配算法，基地址寄存器，界限寄存器；动态分区管理，动态存储分配算法，外部碎片，内部碎片。 分页管理方式：页，页帧，页表，地址映射流程，硬件支持，页表实现，TLB ，有效访问时间，页式管理的模型指标分析，页表结构，多级页表，哈希页表 ，反向页表

基本概念

process 看到的地址都是逻辑地址，逻辑地址要映射到物理地址

base and limit registers

A pair of base and limit registers （基址寄存器和限长寄存器）define the logical address space

前者存储当前正在运行的 process 在内存中的起始地址

后者存储末尾地址或使用的内存大小

能实现简单的内存保护，避免越界

Address binding

Address binding of instructions and data to memory addresses can happen at three different stages: compile, load, execution

Dynamic relocation（动态重定位）

Memory-Management Unit (MMU), hardware device that maps virtual to physical address

In MMU scheme, the value in the relocation register（重定位寄存器） is added to every address generated by a user process at the time it is sent to memory

image-20241121093855631

Dynamic Loading（动态装入）

Using dynamic loading, external libraries are not loaded when a process starts

Libraries are stored on disk in relocatable form, loaded into memory only when needed

在程序运行时，根据需要将程序的某部分代码或数据从磁盘加载到内存，而不是一次性将整个程序加载到内存中

只有当某个模块或函数被调用时，才会将其装入内存

Dynamic Linking（动态链接）

Using dynamic linking, external libraries can be preloaded into (shared) memory

When a process calls a library function, the corresponding physical address is determined

在程序运行时将库加载到内存，并为程序提供所需的功能，不是直接将库代码嵌入程序

Contiguous Allocation（连续分配）

单一连续区分配

Main memory usually into two partitions(单分区)

  1. Resident operating system, usually held in low memory
  2. User processes then held in high memory

image-20241121100938654

Relocation registers used to protect user processes from each other, and from changing operating-system code and dat(Base register，Limit register，MMU)

多分区分配

Multiple-partition allocation

基本思想是将内存划分成若干个连续区域，称为分区，每个分区只能存放一个进程，具体又分为以下几类：

Fixed Partitioning （固定分区）

Main memory is partitioned and allocated to the resident OS and processes

image-20241121101759430

Dynamic Partitions （动态分区）

在程序装入内存时把可用内存“切出”一个连续的区域分配给该进程，且分区 大小正好适合进程的需要

OS maintains information about allocated partitions & free partitions (hole)

image-20241121101917993

Dynamic Storage-Allocation Problem(动态分区分配方式)

ADS

How to satisfy a request of size n from a list of free holes

  1. First-fit: Allocate the first hole that is big enough

  2. Best-fit: Allocate the smallest hole that is big enough

    • must search entire list, unless ordered by size
    • Produces the smallest leftover hole

  3. Worst-fit: Allocate the largest hole

    • must also search entire list
    • Produces the largest leftover hole

First-fit and best-fit better than worst-fit in terms of speed and storage utilization

Next Fit（下次适应）：想象我们将内存首尾相接，然后总是从上次查找结束的地方开始，找一个足够大的空白区即可，这样开销很小

image-20241121102716984

Fragmentation

Memory is wasted due to fragmentation, which can cause performance problems

  • Internal fragmentation is wasted memory within a single process memory space
    • 分配给了 process，但 process 没有用完
  • External fragmentation can reduce the number of runnable processes
    • 所有 hole 加起来大小是够分配给新 process 的，但 hole 是零散分布，用不了

Reduce external fragmentation by compaction or defragmentation （紧缩，拼接），defragmentation is expensive

Paging

Divide physical memory into fixed-sized blocks called frames(帧、物理块、页框)

Divide logical memory into blocks of same size called pages(页)

Set up a page table（页表）to translate logical to physical addresses

Noncontiguous Allocation

OS 可以在 main mem 里选任意位置的 frames，只要总大小够了就行

当然，每个进程需要维护一张页表

下面这图黄色的括号和箭头线往下偏移了点，不要多想

process Pi requires 16 bytes of logical memory：

image-20241122154917397

右边的数字不是帧号，而是 byte 序号，帧号从上到下是 0~7

Address Translation Scheme

Address generated by CPU is divided into

  • Page number (p) （页号）
    • 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

image-20241122160558055

Implementation of Page Table

Page table is kept in main memory

  • Page-table base register (PTBR) points to the page table
  • Page-table length register (PRLR) indicates size of the page table

In this scheme every data/instruction access requires two memory accesses, one for the page table and one for the data/instruction

所以计算访问时间时，要两次内存访问时间

can be solved by associative memory or translation look-aside buffers (TLBs) ( 联想寄存器、快表），页表的 cache

image-20241122161323595

Effective Access Time（有效访问时间）

即平均访问时间

Effective Access Time (EAT) = \((t+\epsilon ) \alpha + ( t + t + \epsilon) (1 – \alpha)\)

  • $\epsilon $ time unit = Associative Lookup 快表访问时间
  • memory cycle time 内存访问时间 = \(t\)
  • \(\alpha\) = Hit ratio of TLB

Structure of the Page Table

Two-Level Paging Example

A logical address (on 32-bit machine with 4K page size) is divided into 20 bits page number & 10bits page offset

Since the page table is paged, the page number is further divided into 10-bit page number & 10-bit page offset

image-20241122163244598

Hashed Page Tables

Common in address spaces > 32 bits

The VPN is hashed into a page table, this page table contains a chain of elements hashing to the same location

VPNs are compared in this chain searching for a match

image-20241122163605889

Inverted Page Table

正常的页表：页表条目的数量等于虚拟页的数量。

倒置页表：每个物理页框对应一个页表条目，而不是每个虚拟页。

反向页表存储的是“哪个虚拟页被映射到该物理页框”以及“属于哪个进程”

image-20241205111452495

Segmentation

A program is a collection of segments

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

Segmentation with Paging

程序（逻辑内存）首先被划分成若干程序段，每一段给予不同的分段标识符， 每一分段又分成若干个固定大小的页

地址变换至少要访问主存三次：段表、页表、指令或数据

地址结构现在变为：<段号，页号，页内地址>

image-20241205114352127