1.操作系统概述

操作系统主要特征：

并发，共享，虚拟，随机
并发：同时处理多个活动的能力活动切换，保护，相互依赖的活动间的同步
共享：共享有限的系统资源
互斥共享
同时共享
虚拟：一个物理实体映射为若干个逻辑实体
随机：对以不可预测的次序发生的事件进行相应并处理
SPOOLING系统（技术）
- 批处理系统的实现通常采用的技术
分时操作系统
实时操作系统

2.操作系统运行环境

处理器状态

两类寄存器：

用户可见寄存器：
- 高级语言编译器通过优化算法分配之，以减少程序访问内存次数
控制和状态寄存器：
- 用于控制处理器的操作，通常由操作系统代码使用
- 常见的有PC，IR，PSW
- PSW：程序状态字，记录处理器的运行状态如条件码、模式、控制位等信息

操作系统的需求-保护

从操作系统的特征考虑，并发、共享
硬件提供的机制
- 处理器具有特权级别，能在不同的特权级运行的不同指令集合
- 硬件机制可将OS与用户程序隔离

程序状态字寄存器PSW专门设置一位，根据运行程序对资源和指令的使用权限而设置不同的CPU状态

操作系统需要两种CPU状态

内核态（kernel mode）：运行操作系统程序
- 可使用全部指令
用户态（user mode）：运行用户程序
- 只可使用非特权指令

特权（privilege）指令：只能由操作系统使用，用户程序不能使用的指令非特权指令：用户程序可以使用的指令

privilege

x86支持4个处理器特权级别

从R0到R3,特权级别由高到低
R0相当于内核态，R3相当于用户态，R1、R2介于两者之间
大多数基于x86处理器的操作系统只用了R0和R3两个特权级别

用户态进入内核态的唯一途径

中断/异常/陷入机制
陷入指令：提供给用户程序的接口，用于调用操作系统的功能（服务）
- 例如：int，trap，syscall，sysenter/sysexit

内核态进入用户态

设置程序状态字PSW

中断与异常机制介绍

中断举例：I/O中断，时钟中断，硬件中断

异常举例：系统调用，页故障/页错误，保护性异常，断点指令，其他程序性异常

中断与异常机制的工作原理

若有中断，中断硬件将该中断触发器内容按规定编码送入PSW的相应位，称为中断码，通过查中断向量表引出中断处理程序

x86处理器对中断/异常的支持

中断控制器（PIC）

负责将硬件的中断信号转换为中断向量，并引发CPU中断

中断向量

存放程序状态字和中断处理程序入口地址的内存单元

实模式（中断向量表 Interrupt Vector）

存放中断服务程序的入口地址 = 段地址左移4位+偏移地址

保护模式（中断描述符表 Interrupt Descriptor Table）

采用门描述符数据结构表示中断向量
任务门
中断门：通过门后系统会自动禁止中断
陷阱门：通过门后系统不会禁止中断
调用门

通过IDTR和向量i找到IDT，通过中断描述符的段选择符，结合GDTR，找到GDT（全局描述符表）的段描述符，将其中的段基址与IDT中的偏移量相结合就得到了中断服务程序的入口地址
检查特权级是否发生了变化，如果是，则进行堆栈切换
压栈
如果是中断，清IF位
通过入口地址，执行第一条指令

系统调用机制(SYSTEM CALL)

系统调用是操作系统提供给用户的唯一接口

使CPU状态从用户态陷入内核态

每个操作系统提供几百种系统调用

进程控制，进程通信，文件使用，目录操作，设备管理，信息维护

系统调用，库函数，API，内核函数

系统调用机制的设计

中断/异常机制：支持系统调用服务的实现
选择一条特殊指令（陷入指令）：引发异常，完成用户态到内核态的切换
系统调用号和参数：每个系统调用都事先给定一个编号（功能号）
系统调用表：存放系统调用服务例程的入口地址

传递参数

由陷入指令自带参数
通过通用寄存器传递参数
在内存中开辟专用堆栈区

;write()函数
movl $4,%eax
int $0x80

;exit函数
movl $1,%eax
int $0x80

例子：LINUX系统调用实现

中断发生后OS底层工作步骤

硬件压栈：程序计数器等
硬件从中断向量装入新的程序计数器等
汇编语言过程保存寄存器值
汇编语言过程设置新的堆栈
C语言中断服务程序运行
进程调度程序决定下一个将运行的进程
C语言过程返回至汇编代码
汇编语言过程开始运行新的当前进程

3.进程线程模型

进程的基本概念

多道程序设计（MULTIPROGRAMMING）

允许多个程序同时进入内存并运行，其目的是为了提高系统效率

操作系统将CPU调度给需要的进程

进程控制块（PCB）

Process Control Block
又称进程描述符、进程属性
操作系统用于管理控制进程的一个专门数据结构
进程与PCB一一对应
进程表：所有进程PCB的集合
Linux：task_struct; Windows:EPROCESS、KPROCESS、PEB

进程描述信息
- 进程标识符（process id），唯一，通常是一个整数
- 用户标识符（user id）
- 进程名
- 进程组关系
进程控制信息
- 当前状态
- 优先级
- 代码执行入口地址
- 程序的磁盘地址
- 运行统计信息
- 进程间同步和通信
- 进程的队列指针
- 进程的消息队列指针
所拥有的资源和使用情况
- 虚拟地址空间的状况
- 打开文件列表
CPU现场信息
- 寄存器值
- 指向该进程页表的指针

进程的状态和状态转换

三种基本状态

运行态：占有CPU，并在CPU上运行
就绪态：已经具备运行条件，但无空闲CPU，而暂时不能运行
等待态：也叫阻塞态、封锁态、睡眠态，因等待某一时间而暂时不能运行
创建：已完成创建，但尚未同意执行该进程
终止：终止进程，资源回收
挂起：用于调节负载，其进程映像交换到磁盘上

LINUX状态示意图 LINUX

进程队列

伴随着进程的改变，其PCB从一个队列进入另一个队列

`进程控制`

进程控制操作完成进程各状态之间的转换，由具有特定功能的原语完成

进程创建原语，进程撤销原语，阻塞原语，唤醒原语，挂起原语，激活原语，改变进程优先级

原语（primitive）又叫原子操作（atomic）

完成特定功能的一段程序，具有不可分割或不可中断性
即原语的执行必须是连续的，在执行过程中不允许被中断

进程的创建
- 为新进程分配一个唯一标识以及PCB
- 为进程分配地址空间
- 初始化进程控制块
- 设置相应的队列指针
- UNIX: fork/exec; WINDOWS: CreateProcess
- exec: 通过用一段新的程序代码覆盖原来的地址空间，实现进程执行代码的转换
进程的撤销
- 结束进程
- 收回进程所占有的资源
  - 关闭打开的文件、断开网路连接、回收分配的内存
- 撤销该进程的PCB
- UNIX: exit; WINDOWS: TerminateProcess
进程的阻塞
- 等待某一事件发生，在其尚未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态
- UNIX: wait; WINDOWS: WaitForSingleObject

Fork的实现

为子进程分配一个空闲的进程描述符
- proc结构
分配给子进程唯一标识pid
以一次一页的方式复制父进程地址空间
- Linux采用了写时复制技术COW加快创建进程Copy-On—Write
从父进程处继承共享资源，如打开的文件和当前工作目录等
将子进程的状态设为就绪，插入到就绪队列
对子进程返回标识符0
向父进程返回子进程的pid

LINUX

`关于进程相关概念的讨论`

进程的分类

系统进程,用户进程；前台进程，后台进程；CPU密集型进程，I/O密集型进程

进程层次结构

UNIX：进程家族树；Windows：地位相同

进程映像（IMAGE）：对进程执行活动全过程的静态描述

上下文切换：将CPU硬件从一个进程换到另一个进程的过程称为上下文切换

进程不运行时，寄存器的值保存于PCB，要允许新进程时，PCB的相关值送到对应的寄存器

线程的引入

为什么在进程中再派生出线程

应用的考虑
开销的考虑
性能的考虑

THREAD

线程：进程中的一个运行实体，是CPU的调度单位，有时将线程称为轻量级进程

由标识符ID
有状态及状态转换 -> 需要提供一些操作
不运行时需要保存上下文
有自己的栈和栈指针
共享所在进程的地址空间和其他资源
可以创建、撤销另一个线程

线程机制的实现

用户级线程，核心(Kernel)级线程，混合-两者结合方法

用户级线程小结

优点：
- 线程切换快
- 调度算法是应用程序特定的
- 用户级线程可运行在任何OS上
缺点：
- 内核只能讲CPU分配给进程，同一进程中的两个线程不能同时运行于两个处理器上
- 大多数系统调用是阻塞的，因此由于内核阻塞进程，进程中的所有线程也被阻塞
  - 可以将系统调用改为非阻塞的
  - Jackeing/Wrapper

可再入程序

4.处理器调度

处理器调度的相关概念

CPU调度

其任务是控制、协调进程对CPU的竞争
即按一定的调度算法从就绪队列中选择一个进程，把CPU的使用权交给被选中的进程
如果没有就绪进程，系统会安排一个系统空闲进程或idle进程

调度算法、调度时机、调度过程

调度时机（内核对中断/异常/系统调用处理后返回用户态时）

进程正常终止或由于某种错误而终止
新进程创建或一个等待进程变就绪
当一个进程从运行态变阻塞态
当一个进程从运行态变就绪态

进程切换

切换全局页目录以加载一个新的地址空间
切换内核栈和硬件上下文

上下文切换开销（COST）

直接开销：保存和恢复寄存器、切换地址空间
间接开销：高速缓存、缓冲区缓存、TLB失效

调度算法

用户角度和系统角度考虑的问题是不一样的，设计算法时要在各种因素中做一个权衡

调度算法衡量指标

吞吐量 Throughout
- 每单位时间完成的进程数目
周转时间 TT（Turnaround Time）
- 每个进程从提出请求到运行完成的时间
响应时间RT（Response Time）
- 从提出请求到第一次回应的时间
CPU利用率（CPU Utilization）
- CPU做有效工作的时间比例
等待时间（Waiting Time）
- 每个进程在就绪队列（ready queue）中等待的时间

设计调度算法时要考虑的几个问题

进程优先级（数）

优先级队列

抢占与非抢占

可抢占式Preempive(可剥夺式)
- 可抢占优先级低进程的CPU
非可抢占式
- 与上相反

时间片 Time Slice或quantum

批处理系统的调度算法

先来先服务（FCFS-First Come First Serve）
- 谁先就绪，谁先上CPU
- 非抢占式
- 短时进程在长时进程后面，用户体验不够友好
最短作业优先（SJF-Shortest Job First）
- 具有最短完成时间的进程优先完成
- 非抢占式
- 源源不断的短任务到来，可能使长的任务长时间得不到运行，产生饥饿现象（Starvation）
最短剩余时间优先（SRTN-Shortest Remaining Time Next）
- 若新就绪的进程比当前进程具有更短的完成，系统抢占当前进程，选择新就绪的进程执行
最高响应比优先(HRRN-Highest Response Ratio Next)
- 调度时，首先计算每个计算的响应比R;之后总是选择R最高的进程执行

交互式系统的调度算法

轮转调度（RR-Round Robin）
- 时间片轮转
  - 每个进程分配一个时间片，周期性切换
  - 由于进程切换，时间片轮转算法要花费较高的开销
- 虚拟轮转
  - 因为I/O进程总是会进入阻塞状态，从而用不完它的时间片，等到事件完成，它会进入就绪队列的最尾端；而CPU进程总能充分的利用它的时间片。这就造成了不公平。
  - 所以单独为I/O进程设置辅助队列，CPU优先处理I/O进程，处理完后采取处理就绪队列。
最高优先级调度（HPF-Highest Priority First）
- 选择优先级最高的进程投入运行
- 系统进程高于用户进程；前台进程高于后台进程；操作系统更偏好I/O进程
- 饥饿现象
多级反馈队列（Multiple feedback queue）
最短进程优先（Shortest Process Next）

优先级翻转问题（Priority Inversion）

一个低优先级进程持有一个高优先级进程所需要的资源，使得高优先级进程等待低优先级进程运行
临界区
系统错误，高优先级进程停滞不前，导致系统性能降低
解决方案
- 设置优先级上限，使进入临界区的进程优先级最高
- 优先级继承
- 使用中断禁止，进入临界区的进程不响应中断

4.5 多级反馈队列调度算法、各种调度算法小结

Multilevel Feedback

多个就绪队列，队列的优先级从高到低
队列的时间片从小到大
第一级队列为空时，调度第二级队列，以此类推
各级队列按照时间片轮转方式进行调度
新创建的进程就绪后，进入第一级队列
时间片用完而放弃CPU，进入下一级就绪队列
由于阻塞而放弃CPU的进程进入相应的等待队列，一旦等待的事件发生，该进程回到原来的一级就绪队列

若允许抢占

当有一个优先级更高的进程就绪时，可以抢占CPU
- 被抢占的进程回到原来一级就绪队列末尾

algorithm

多处理器调度算法

算法设计

不仅要决定选择哪一个进程执行，还需要决定在哪一个CPU上执行
要考虑进程在多个CPU之间迁移时的开销
考虑负载均衡问题

Windows的线程调度算法

UNIX: 动态优先数法

5.3BSD: 多级反馈队列法

Linux: 抢占式调度

Solaris: 综合调度算法

Windows: 基于优先级的抢占式多任务调度

支持内核级线程，调度单位是线程
采用基于动态优先级的、抢占式调度，结合时间配额的调整

算法

就绪线程按优先队列进入相应队列
系统总是选择优先级最高的就绪线程运行
同一优先级的各线程按时间片轮转进行调度
多CPU系统中允许多个线程并行运行

引发线程调度的条件：

一个线程的优先级改变了
一个线程改变了它的亲和（Affinity）处理机集合
线程正常终止或由于某种错误而终止
新线程创建或一个等待线程变就绪
当一个线程从运行态变阻塞态
当一个线程从运行态变就绪态

Windows使用32个线程优先级，分成三类

实时优先级线程不改变其优先级
可变优先级线程：其优先级可以在一定范围内升高或降低
- 基本优先级和当前优先级
零页线程：用于对系统中空闲物理页面清零

线程的时间配额

不是时间，而是一个被称为配额单位（quantum unit）的整数
一个线程用完了自己的时间配额时，如果没有其他相同优先级的线程，Windows将重新给该线程分配一个新的时间配额，让它继续运行

抢占

线程被抢占时，会被放回队首
1. 若是实时优先级的线程被抢占，会被重新分配一个完整的时间配额
2. 若是可变优先级的线程被抢占，会继续使用剩余的时间配额

下列5中情况，Windows会提升线程的优先级

I/O操作完成 “Wdm.h”,”Ntddk.h”,IoCompleteRequest
信号量或事件等待结束
前台进程中的线程完成一个等待操作
由于窗口活动而唤醒窗口线程
线程处于就绪态超过了一定的时间还没有运行–“饥饿”现象平衡集管理器(balance set manager)

5.同步机制(1)

同步互斥机制

进程的并发执行
进程互斥
进程同步
信号量及PV操作
经典IPC问题

进程的并发执行

进程互斥

竞争条件（RACE CONDITION）

两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序

进程互斥（MUTUAL EXCLUSIVE）

各个进程竞争使用临界资源

临界资源（CRITICAL RESOURCE）

系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量

临界区（互斥区）：（CRITICAL SECTION）

各个进程中对某个临界资源实施操作的程序片段

临界区的使用原则

没有进程在临界区时，想进入临界区的进程可进入
不允许两个进程同时处于临界区中
临界区外运行的进程不得阻塞其他进程进入临界区
不得使进程无限期等待进入临界区

实现临界区互斥的方案

软件方案 Dekker解法，Peterson解法
硬件方案 屏蔽中断，TSL(XCHG)指令

进程互斥的软件解决方案

Dekker算法

1965年，第一个软件解法

Peterson算法

1981年

enter_region(i);
//code
leave_region(i);

5.4 进程互斥的硬件解决方案

硬件方法1–中断屏蔽方法

“开关中断”指令

算法

执行关中断指令
临界区操作
执行开中断指令

特点

简单，高效
代价高，限制CPU并发能力（临界区大小）
不适用于多处理器
适用于操作系统本身，不适用用户进程

硬件方法2–“测试并加锁”指令

TSL指令：TEST AND SET LOCK

TSL执行前把总线锁住，结束后把总线打开

enter_region:
    TSL REGISTER,LOCK   ;复制锁到寄存器并将锁置1
    CMP REGISTER,#0     ;判断寄存器内容是否是0
    JNE enter_region    ;若不是0，跳转到enter_region
    RET                 ;返回调用者，进入了临界区
leave_region:
    MOVE LOCK,#0        ;在锁中置0
    RET                 ;返回调用者

硬件方法3–“交换”指令

XCHG指令：EXCHANGE

类似于TSL指令

enter_region:
    MOVE REGISTER,#1    ;给寄存器存1
    XCHG REGISTER,LOCK  ;交换寄存器和锁变量的内容
    CMP REGISTER,#0     ;判断寄存器内容是否是0
    JNE enter_region    ;若不是0，跳转到enter_region
    RET                 ;返回调用者，进入了临界区
leave_region:
    MOVE LOCK,#0        ;在锁中置0
    RET                 ;返回调用者

忙等待（busy waiting）,自旋锁（spin lock）

优先级翻转

5.5 进程同步

进程同步（synchronization）

指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成某一项任务

生产者/消费者问题

5.6 信号量及PV操作

一种卓有成效的进程同步机制

1965年，由荷兰学者Dijkstra提出

定义如下

struct semaphore{
    int count;
    queueType queue;
}

对信号量可以实施的操作：初始化、P和V

P、V分别是荷兰语的test(proberen)和increment(verhogen)
P,down,semWait
V,up,semSignal
PV操作为原语操作（primitive or atomic action）

用PV操作解决进程间互斥问题

分析并发进程的关键活动，划定临界区
设置信号量mutex，初值为1
在临界区前实施P(mutex)
在临界区后实施V(mutex)

P(s){
    s.count--;
    if(s.count < 0){
        //该进程状态置为阻塞状态；
        //将该进程插入相应的等待队列s.queue末尾；
        //重新调度；
    }
}

V(s){
    s.count++;
    if(s.count <= 0){
        //唤醒相应等待队列s.queue中等待的另一个进程
        //改变其状态为就绪态，并将其插入就绪队列
    }
}

5.7 生产者消费者问题

信号量方法

void producer(void){
    int item;
    while(TRUE){
        item = produce_item();
        P(&empty);
        P(&mutex);
        insert_item(item);
        V(&mutex);
        V(&full);
    }
}

void consumer(void){
    int item;
    while(TRUE){
        P(&full);
        P(&mutex);
        item = remove_item();
        V(&mutex);
        V(&empty);
        consume_item(item);
    }
}

5.8 读者写者问题

问题描述：

多个进程共享一个数据区，这些进程分成两组
- 读者进程：只读数据区中的数据
- 写者进程：只往数据区写数据

要求满足条件：

允许多个读者同时执行读操作
不允许多个写者同时操作
不允许读者、写者同时操作

第一类读者写者问题：读者优先

void reader(void){
    while(TRUE){
        P(mutex);
        rc = rc + 1;
        if(rc == 1) P(w);
        V(mutex);

        P(mutex);
        rc = rc - 1;
        if(rc == 0) V(w);
        V(mutex);
    }
}

void writer(void){
    while(TRUE){
        P(w);
        写操作
        V(w);
    }
}

6. 同步机制（2）

管程 monitor
进程间通信 inter-process communication
典型操作系统的IPC机制

6.1 管程的基本概念

为什么会出现管程:

信号量机制存在不足：程序编写困难、易出错
解决：Brinch Hansen（1973），Hoare（1974）
在程序设计语言中引入管程成分，一种高级同步机制

进程与管程

进程只能通过调用管程中的过程来间接地访问管程中的数据结构

互斥

管程是互斥进入的
而互斥性是由编译器负责保证的

同步

管程中设置条件变量及等待/唤醒操作

场景：

当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权
当后面进入管程的进程执行唤醒操作时（例如P唤醒Q），管程中便存在两个同时处于活动状态的进程

解决方案：

P等待Q执行，Hoare
Q等待P继续执行，MESA
规定唤醒操作为管程中最后一个可执行的操作，Hansen

6.2 HOARE管程

因为管程是互斥进入的，所以当一个进程试图进入一个已被占用的管程时，应当在管程的入口处等待
- 为此，管程的入口处设置一个进程等待队列，称作入口等待队列。
如果进程P唤醒进程Q，则P等待Q执行；如果进程Q执行中又唤醒进程R，则Q等待R执行……，如此在管程内部可能会出现多个等待进程
- 在管程内需要设置一个进程等待队列，称为紧急等待队列，紧急等待队列的优先级高于入口等待队列的优先级。

wait(c):

如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程进入c链末尾

signal(c):

如果c链为空，则相当于空操作，执行此操作的进程继续执行；否则唤醒第一个等待者，执行此操作的进程进入紧急等待队列的末尾。

6.3 管程的应用

JAVA中的管程库

6.4 MESA管程

Hoare管程的一个缺点

两次额外的进程切换

解决：

signal->notify
notify:当一个正在管程中的进程执行notify(x)时，它使得x条件队列得到通知，发信号的进程继续执行

notify的结果：

位于条件队列头的进程在将来合适的时候且当处理器可用时恢复执行
由于不能保证在它之前没有其他进程进入管程，因而这个进程必须重新检查条件
- 用while循环取得if语句
导致对条件变量至少多一次额外的检测（但不再有额外的进程切换），并且对等待进程在notify之后何时运行没有任何限制

改进notify:

对notify的一个很有用的改进：
- 给每个条件原语关联一个监视计时器，不论是否被通知，一个等待时间超时的将被设为就绪态
- 当该进程被调度执行时，会再次检查相关条件，如果条件满足则继续执行
超时可以防止如下情况的发生：
- 当某些进程在产生相关条件的信号之前失败时，等待该条件的进程就会被无限制地推迟执行而处于饥饿状态。

引入broadcast:

使所有在该条件上等待的进程都被释放并进入就绪队列
当一个进程不知道由多少进程将被激活时，这种方式是非常方便的
当一个进程难以准确判定将激活哪个进程时，也可使用广播

mesa管程与hoare管程的比较

mesa管程优于hoare管程之处在于mesa管程错误比较少
在mesa管程中，由于每个过程在收到信号后都重新检查管程变量，并且由于使用了while结构，一个进程不正确地broadcast广播或发信号notify不会导致收到信号的程序出错
收到信号的程序将检查相关的变量，如果期望的条件没有满足，它会重新继续等待

6.5 PTHREAD中的同步机制

6.6 进程间通信IPC

信号量及管程的不足
不适用多处理器情况

消息传递

send & receive 原语

适用于：

分布式系统、基于共享内存的多处理机系统、单处理机系统，可以解决进程间的同步问题、通信问题

基本通信方式

消息传递
共享内存
管道
套接字
远程过程调用

6.7 典型操作系统中的IPC机制

Linux内核同步机制

原子操作、自旋锁、读写自旋锁、信号量、读写信号量、互斥体、完成变量、顺序锁、屏障

原子操作

atomic_t v = atomic_init(0);

atomic_set(&v,4);
atomic_add(2,&v);
atomic_inc(&v);
printk("%d\n",atomic_read(&v));

屏障 barrier

一组线程协同完成一项任务，需要所有线程都到达一个汇合点后再一起向前推进

7. 存储模型（1）

基本概念
物理内存管理
伙伴系统
基本内存管理方案
交换技术（Swapping）

7.1 基本概念-地址重定位

Relocation,Translation,Mapping

地址重定位，也叫地址转换、地址映射、地址翻译
程序装载到内存才可以运行
多道程序设计模型
每个进程由自己的地址空间
- 一个进程访问时不能访问另一个进程的地址空间
- 进程不能执行不适合的操作

因为

进程中的地址不是最终的物理地址
在进程运行前无法计算出物理地址
- 因为：不能确定进程被加载到内存什么地方

因此，需要地址重定位的支持

逻辑地址（相对地址，虚拟地址）
- 不能用逻辑地址在内存中读取信息
物理地址（绝对地址，实地址）
- 内存中存储单元的地址，可直接寻址

为了保证CPU执行指令时可正确访问内存单元，需要将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址，这一过程称为地址重定位

静态重定位

用户程序加载到内存时，一次性实现逻辑地址到物理地址的转换
通常软件可以完成

动态重定位

在进程执行过程中进行地址变换
- 即逐条指令执行时完成地址转换
需要硬件支持

MMU（内存管理单元）

Memory Management Unit

privilege

7.2 物理内存管理

空闲内存管理

位图
空闲区表，已分配区表
空闲块链表

内存分配算法

首次适配 first fit
下次适配 next fit
最佳适配 best fit
最差适配 worst fit

内存回收算法

当某一块归还后，前后空闲空间合并，修改内存空闲区表

7.3 伙伴系统

Linux底层内存管理采用

一种特殊的“分离适配”算法

一种经典的内存分配方案
主要思想：将内存按2的幂进行划分，组成若干空闲块链表；查找该链表找到能满足进程需求的最佳匹配块

算法：

首先将整个可用空间看作一块，2^u
假设进程申请的空间大小为s，如果满足
- ‘2^(u-1) < s <= 2^u’,则分配整个块
否则，将块划分为两个大小相等的伙伴，大小为2^(u-1)
一直划分下去直到产生大于或等于s的最小块

7.4 基本内存管理方案1

单一连续区->固定分区->可变分区->页式->段式->段页式->单一连续区

单一连续区

一段时间内只有一个进程在内存简单，内存利用率低

固定分区

把内存空间分割成若干区域，称为分区
每个分区的大小可以相同也可以不同
分区大小固定不变
每个分区装一个且只能装一个进程

可变分区

根据进程的需要，把内存空闲空间分割出一个分区，分配给该进程
剩余部分成为新的空闲区
外碎片，导致内存利用率下降

碎片问题解决

紧缩技术（memory compaction）
- 在内存移动程序，将所有小的空闲区合并为较大的空闲区
- 又称：压缩技术，紧致技术，搬家技术
- 要考虑的问题：系统开销，移动时机

7.5 基本内存管理方案2

页式存储管理方案

用户进程地址空间被划分为大小相等的部分，称为页（Page）或页面，从0开始编号
内存空间按同样大小划分为大小相等的区域，称为页框（Page Frame），从0开始编号；也称为物理页面，页帧，内存块
内存分配（规则）
- 以页为单位进行分配，并按进程需要的页数来分配；逻辑上相邻的页，物理上不一定相邻
典型页面尺寸：4K或4M

逻辑地址（假设32位机器）

20位页号，12位页内地址（偏移）

页表

页号
页表项
- 记录了逻辑页号与页框号的对应关系

逻辑地址->页表（mapping）->物理内存

空闲数据管理

位图

地址转换（硬件支持）

CPU取到逻辑地址，自动划分为页号和页内地址，用页号查页表，得到页框号，在与页内偏移拼接成物理地址
内碎片
- 比如进程需要5页加一条指令，由于这种内存分配方案，我们必须分配6页，这就造成了内存浪费

段式存储管理方案

设计思想

用户进程地址空间：按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名
内存空间被动态划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定
内存分配（规则）：以段为单位进行分配，每段在内存中占据连续空间，但各段之间可以不相邻

逻辑地址

段号，段内地址

段表

段号，段首地址，段长度

地址转换

CPU取到逻辑地址，用段号查段表，得到该段在内存的起始地址，与段内偏移地址计算出物理地址

段页式存储管理方案

产生背景
- 综合页式，段式方案的优点，克服二者的弱点
用户进程划分
- 先按段划分，每一段再按页面划分
逻辑地址
- 段号，页号，页内地址
内存划分：同页式存储管理方案
内存分配：以页为单位进行分配
数据结构及有关操作
- 段表，页表
- 段表：记录了每一段的页表始址和页表长度
- 页表：记录了逻辑页号与页框号的对应关系
  - 每一段有一张页表，一个进程有多个页表
- 空闲区管理：同页式管理
- 内存分配、回收：同页式管理

7.6 交换技术

内存不足时如何管理

一个大的进程地址空间如何装进一个小的物理内存里面

内存“扩充”技术

内存紧缩技术

覆盖技术 overlaying

主要用于早期系统
程序执行过程中，程序的不同部分在内存中相互替代
    * 按照其自身的逻辑结构，将那些不会同时执行的程序段共享同一块内存区域
    * 要求程序各模块之间有明确的调用结构
程序员声明覆盖结构，操作系统自动完成覆盖

交换技术 swapping

设计思想
    内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域（进程在内存及磁盘之间的动态调度）

问题
    1. 进程的哪些内容要交换到磁盘？会遇到什么困难？
        答：运行时创建或修改的内容：栈和堆
    2. 在磁盘的什么位置保存被换出的进程？
        答：交换区：一般系统会指定一块特殊的磁盘区域作为交换空间（swap space），包括连续的磁道，操作系统可以使用底层的磁盘读写操作对其高效访问
    3. 交换时机
        答：只要不用就换出（很少再用）；内存空间不够；有不够的危险
    4. 如何选择被换出的进程
        答：不应换出处等待于I/O状态的进程
    5. 如何处理进程空间增长
        答：同向增长，对向增长

虚拟存储技术 virtual memory

8 虚拟存储技术

8.1 虚拟存储技术

当进程运行时，现将其一部分装入内存，另一部分暂留在磁盘，当要执行的指令或访问的数据不在内存时，由操作系统自动完成将它们从磁盘调入内存的工作

虚拟地址空间

分配给进程的虚拟内存

虚拟地址

在虚拟内存中指令或数据的位置，该位置可以被访问，仿佛它是内存的一部分

虚存是对内存的抽象，构建在存储体系之上，由操作系统协调各存储器的使用

地址保护

确保每个进程有独立的地址空间
确保进程访问合法的地址范围
确保进程的操作是合法的

虚拟页式（PAGING）

虚拟存储技术 + 页式存储管理方案 -> 虚拟页式存储管理系统
基本思想：
    1.进程开始运行之前，不是装入全部页面，而是装入一个或零个页面
    2.之后，根据进程运行的需要，动态装入其他页面
    3.当内存空间已满，而又需要装入新的页面时，则根据某种算法置换内存中的某个页面，以便装入新的页面

有两种调页方式

请求调页（demand paging）
预先调页（prepaging）

以CPU时间和磁盘空间换取昂贵的内存空间

8.2 页表及页表项的设计

页表项

页框位
有效位
访问位
修改位
保护位

通常，页表项是硬件设计的

页目录

%cr3

反转（倒排）页表设计

从物理地址空间出发，系统建立一张页表
页表项记录进程i的某虚拟地址（虚页号）与页框号的映射关系

8.3 地址转换过程及TLB的引入

块表（TLB）的引入

一种随机存取型存储器，除连线寻址机制外，还有接线逻辑，能按特定的匹配标志在一个存储周期内对所有的字同时进行比较
页表 -> 两次或两次以上的内存访问
基于程序访问的局部性
Translation Look-aside buffer
相联存储器(associative memory)
- 特点：按内容并行查找

8.4 页错误(Page Fault)

具体原因

所访问的虚拟页面没有调入物理内存
页面访问违反权限
错误的访问地址

8.5 软件相关策略

驻留集

固定分配策略
可变分配策略

置换问题

置换范围
1. 局部置换
2. 全局置换
置换策略
1. 大部分策略是基于过去的行为来预测将来的行为

页框锁定

操作系统的核心代码、关键数据结构、I/O缓冲区
Windows中的VirtualLock和VirtualUnLock函数

清除策略

在系统中保存一定数目的空闲页框供给比使用所有内存并在需要时搜索一个页框有更好的性能
分页守护进程（paging daemon）
当进程需要使用一个已置换出的页框时，如果该页框还没有被新的内容覆盖，将它从空闲页框集合中移出即可恢复该页面
页缓冲技术
- 不丢弃置换出的页，将它们放入两个表之一：空闲页链表，修改页链表
- 将被修改的页定期写入磁盘
- 被置换的页仍然保留在内存中，一旦进程又要访问该页，可以迅速将它加入该进程的驻留集合（代价很小）

8.6 页面置换算法1

最佳页面置换算法（OPT）

设计思想
- 置换以后不再需要的或最远的将来才会用到的页面

先进先出算法（FIFO）

选择在内存中驻留时间最长的页并置换它
实现：页面链表法

第二次机会算法（SCR）

按照先进先出算法选择某一页面，检测其访问位R，如果为0，则置换该页；如果为1，则给第二次机会，并将访问位置0

时钟算法（CLOCK）

改进的第二次机会算法
用指针的移动代替页框的移动

最近未使用算法（NRU）

选择在最近一段时间内未使用过的一页并置换
根据R、M的情况分为4类
随机从编号最小的非空类中选择一页置换
时钟算法的实现
1. 从指针的当前位置开始，扫描页框缓冲区，选择遇到的第一个页框（r=0;m=0），用于置换（本次扫描过程中，对使用位不做任何修改）
2. 如果第1步失败，则重新扫描，选择第一个（r=0;m=1）的页框（本次扫描过程中，对每个跳过的页框，将其使用位设置成0）
3. 如果第2步失败，指针将回到它的最初位置，并且集合中所有页框的使用位均为0。重复第1步，并且，如果有必要，重复第2步。这样将可以找到供置换的页框

最近最少使用算法（LRU）

选择最后一次访问时间距离当前时间最长的一页并置换
实现：时间戳，维护一个访问页的栈
- 开销大
一种硬件实现方法

最不经常使用算法（NFU）

选择访问次数最少的页面置换

老化算法（AGING）

改进：计数器在加R前先右移一位，R位加到计数器的最左端

BELADY现象

FIFO页面置换算法会产生异常现象，即：当分配给进程的物理页面增加时，缺页次数反而增加

8.7 页面置换算法2-工作集算法

影响缺页次数的因素

页面置换算法
页面本身的大小
程序的编制方法
分配给进程的页框数量

颠簸（Thrashing,抖动）

虚存中，页面在内存与磁盘之间频繁调度，使得调度页面所需的时间比进程实际运行的时间还多，这样导致系统效率急剧下降，这种现象称为颠簸或抖动

页面尺寸

确定页面大小对于分页的硬件设计非常重要而对操作系统是个可选的参数
x86/Pentium 4096 或 4M
最优页面大小：P=根号下2se

程序编制方法对缺页次数的影响

工作集（working set）模型

根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断
一个进程当前正在使用的页框集合
访页序列特性、时刻t、工作集窗口长度
基本思路：
- 找出一个不在工作集中的页面并置换它

8.8 其他相关技术

内存映射文件

mmap
进程通过一个系统调用(mmap)讲一个文件映射到其虚拟地址空间的一部分，访问这个文件就像访问内存中的一个大数组，而不是对文件进行读写

支持写时复制技术

新复制的页面对执行写操作的进程是私有的，对其他共享写时复制页面的进程是不可见的

9 文件系统（1）

文件与文件系统
文件的存储介质
磁盘空间管理
文件控制块及文件目录
文件的物理结构
文件系统的实现
文件系统实例–UNIX

9.1 文件与文件系统

文件

是对磁盘的抽象
是指一组带标识（标识即文件名）的、在逻辑上有完整意义的信息项的序列

文件系统

统一管理磁盘空间，实施磁盘空间的分配与回收
实现文件的按名存取
- 名字空间->磁盘空间
实现文件信息的共享，并提供文件的保护、保密手段
向用户提供一个方便使用、易于维护的接口、并向用户提供有关统计信息
提高文件系统的性能
提供与I/O系统的统一接口

按文件性质和用途分类（UNIX）

普通文件；目录文件；特殊文件（设备文件）；管道文件；套接字

普通文件：包含了用户的信息，一般为ASCII或二进制文件

目录文件：管理文件系统的系统文件

特殊文件：字符设备文件；块设备文件

流式文件

文件是由逻辑意义、无结构的一串字符的集合

记录式文件

每条记录有其内部结构

顺序访问

随机访问

提供读写位置（UNIX的seek操作）

9.2 文件的存储介质

物理块（块block、簇cluster）

磁盘结构

物理地址形式：磁头号（盘面号）、磁道号（柱面号）、扇区号
扇区：标题（10字节）、数据（512字节）、ECC纠错信息（12-16字节）

一次访盘请求

读/写，磁盘地址（设备号，柱面号，磁头号，扇区号），内存地址（源/目）

完成过程由三个动作组成

寻道（时间）
- 磁头移动定位到指定磁道
旋转延迟（时间）
- 等待指定扇区从磁头上旋转经过
数据传输（时间）
- 数据在磁盘与内存之间的实际传输

9.3 磁盘空间管理

有关数据结构

位图
空闲块表
空闲块链表

磁盘地址与块号的转换

成组链接法

9.4 文件控制块及文件目录

文件控制块（File Control Block）

为管理文件而设置的数据结构，保存管理文件所需的所有有关信息

9.5 文件的物理结构

连续结构

优点
- 简单
- 支持顺序存取和随机存取
- 所需的磁盘寻道次数和寻道时间最少
- 可以同时读入多个块，检索一个块也很容易
缺点
- 文件不能动态增长
  - 预留空间：浪费或重新分配和移动
- 不利于文件插入和删除
- 外部碎片：紧缩技术

链接结构

一个文件的信息存在若干不连续的物理块中，各块之间通过直接连接，前一个物理块指向下一个物理块
优点
- 提高了磁盘空间利用率，不存在外部碎片问题
- 有利于文件插入和删除
- 有利于文件动态扩充
缺点
- 存取速度慢，不适于随机存取
- 可靠性，如指针出错
- 更多的寻道次数和寻道时间
- 链接指针占用一定的空间

文件分配表（FAT）

索引结构

保持了链接结构的优点，又解决了其缺点
- 优点
  - 既能顺序存取，又能随机存取
  - 满足了文件动态增长、插入删除的要求
  - 能充分利用磁盘空间
- 缺点
  - 较多的寻道次数和寻道时间
  - 索引表本身带来了系统开销

多级索引与综合模式

UNIX的三级索引结构

每个文件的主索引表有15个索引项（FCB中），每项2个字节
前12项直接存放文件的物理块号（直接寻址）
如果文件大于12块，则利用第13项指向一个物理块，在该块中存放的是一级索引表
- 假设扇区大小为512字节，物理块等于扇区块大小，一级索引表可以存放256个物理块号
对于更大的文件还可利用第14和第15项作为二级和三级索引表
- 二级索引表的每个索引项指向一个一级索引表
- 三级索引表的每个索引项指向一个二级索引表

采用这种结构，一个文件最大可达到多少个物理块？

12 + 256 + 256^2 + 256^3 个块

9.6 文件系统的实现

磁盘分区（partition）

文件卷（volume）

块（Block）和簇（Cluster）

格式化（format）

在一个文件卷上建立文件系统，即建立并初始化用于文件分配和磁盘空闲空间管理的管理数据