操作系统¶

0. 总结¶

0.2 进程

为什么要引入进程：在多道程序的背景下如果只有程序无法很好的实现并发，因为程序是静态的概念，无法描述程序在内存中的情况，所以引入进程。

什么是进程？进程的组成：进程是程序一次执行的动态过程；进程实体由程序段，数据段，PCB组成；

线程的概念：...

进程中使用特权指令要把 PSW 的一个状态位改成核心态，而线程的用户级线程和核心级线程分别对应用户空间和核心空间，是对内存的划分相关链接1 相关链接2

为什么要处理机调度：增加 CPU 的利用率，不同的调度算法可以满足不同的要求

普通的信号量机制（用 while）是不满足让权等待的，等待资源的进程任然会占用 CPU 资源；管程中 x.wait：将正在访问管程的进程放到 x 的等待队列上，并释放管程；x.signal：从阻塞队列中唤醒因 x 被阻塞的进程；这个队列是在管程中的，不同的 x 对应不同的队列

死锁：各个进程互相等待对方手里的资源；发生死锁的进程一定处于阻塞态；至少有 2 个或 2 个以上的进程同时死锁

死锁状态一定是不安全的；资源分配图没有环路一定不会出现死锁

0.3 内存管理

每个进程都有自己的页表，页表地址一开始放在 PCB 中，被调度时放到 PTR 中

1. 操作系统¶

1.1 操作系统的概念¶

裸机
操作系统
软件

操作系统的定义：（简单定义）控制和管理整个计算机系统的硬件和软件资源，并为用户和其他软件提供接口与环境的程序集合

1.2 操作系统的功能和目标¶

提供的功能：

作为系统资源的管理者
- 处理机管理
- 存储器管理
- 文件管理
- 设备管理
作为用户和计算机硬件之间的接口
- 命令接口：联机命令接口/交互式接口，脱机命令接口
- 程序接口：系统调用（系统调用的目的是请求系统服务，只能通过用户程序间接使用，是操作系统为应用程序使用内核功能提供的接口），GUI图形用户界面是当前最流行的
作为最接近硬件的层次，实现对硬件机器的扩展

1.3 操作系统的特征¶

并发: 宏观同时发生
共享: 资源共享：互斥共享，同时共享
虚拟: 指把一个物理实体变为逻辑上的对应物，时分复用技术（虚拟处理器），空分复用技术（虚拟存储器）
异步: 多道环境下允许多个程序并发执行，走走停停，以不可预知的速度前进

并发共享互为条件

并发和共享是操作系统的两个最基本的特征

1.4 操作系统的发展和分类¶

手工操作阶段：cpu利用率低，用户独占全机
批处理阶段：没有交互
- 单道批处理: 资源利用率提升，有很多事件等待I/O
- 多道批处理: 多道程序并发执行，共享计算机资源;没有人机交互，用户响应时间长
分时操作系统: 特点：同时性，交互性，独立性，及时性，缺点：不能优先处理一些紧急任务
实时操作系统: 能够优先响应一些紧急任务:硬实时，软实时

网络操作系统，分布式操作系统，个人计算机操作系统

1.5 OS 运行机制和体系结构¶

指令：特权指令，非特权指令

两种处理器状态：用户态（目态），核心态(管态)

两种程序：内核程序，应用程序

操作系统的内核

时钟管理
中断处理
原语
对系统资源进行管理的功能：进程，存储器，设备管理

1.6 中断和异常¶

中断的概念:

发生中断时，CPU进入核心态；操作系统对中断进行处理

用户态到核心态是通过中断实现的

核心态到用户态是通过执行一个特权指令，改变程序状态字

中断的分类：

内中断：异常、例外、陷入,与当前执行的指令有关
软件中断：故障，自陷
硬件中断：终止
外中断：中断, 来自CPU的外部

外中断的处理过程:

执行完每个指令后，检查是否有外部中断

如果有，保护被中断进程的CPU环境

进行中断处理

恢复原进程的CPU环境并退出中断，继续执行

1.7 系统调用¶

什么是系统调用，有什么作用？

用户通过软件间接使用系统调用，通过系统调用来管理资源

系统调用分类： - 设备管理 - 文件管理 - 进程管理 - 进程通信 - 内存管理

系统调用和库函数的区别：库函数是对系统调用的封装

系统调用在核心态执行

访管指令引起访管中断，操作系统转为核心态

系统调用背后的过程：传递系统调用参数->执行陷入指令（用户态）->执行系统调用相应服务程序（核心态）->返回用户程序

陷入指令只能在用户态下执行

1.8 操作系统结构，操作系统引导，虚拟机¶

结构：

分层法：单向依赖，优：便于调试和验证，劣：效率低
模块化：
宏内核：
微内核：只保留最基本的功能
微内核的基本功能：进程线程管理，低级存储器管理（如地址变换机构），中断和陷入处理
特点：扩展性和灵活性，可靠性和安全性，可移植性，分布式计算

引导：

激活CPU，读取ROM中的boot程序，将指令寄存器置为BIOS的第一条指令
硬件自检
加载带有操作系统的硬盘，（是加载硬盘
加载MBR
扫描硬盘分区表，MBR包含硬盘分区表，硬盘分区区分为活动分区和非活动分区
加载分区引导记录PBR，即活动扇区的第一个扇区
加载启动管理器
加载操作系统

虚拟机：

第一类虚拟机管理程序
第二类虚拟机管理程序

2 进程¶

2.1 进程¶

2.1.1 进程概述¶

定义：程序段、数据段、PCB三部分组成了进程实体；进程是程序的一次执行，是进行资源分配和调度的基本单位

进程实体是静态的，进程是动态的

PCB： - 进程描述信息 - 进程控制和管理信息 - 资源分配清单 - 处理机相关信息

进程的组织： - 链接方式：执行指针，就绪队列指针，阻塞队列指针 - 索引方式：执行指针，就绪表指针，阻塞表指针

进程的特征 - 动态性 - 并发性 - 独立性 - 异步性

2.1.2 进程的状态和转换¶

三态：运行态，就绪态，阻塞态五态：创建态，终止态

进程的转换：

2.1.3 进程控制¶

实现对进程状态的转换

用原语实现进程控制：通过关中断和开中断实现原语

关中断和开中断只可以在核心态下面执行

进程控制相关的原语做的3类事情： - 更新PCB信息 - 将PCB插入合适队列 - 分配、回收资源

进程的创建：创建原语 - 申请空白PCB - 为新进程分配所需资源 - 初始化PCB - 将 PCB插入就绪队列

进程终止：撤销原语 - 从PCB集合中找到终止进程的PCB - 若程序正在运行，立即剥夺CPU，将CPU分配给其他进程 - 终止其所有子进程 - 将该进程拥有的资源归还给父进程或操作系统 - 删除 PCB

进程的阻塞和唤醒：阻塞原语，唤醒原语

进程的切换：切换原语

2.1.4 进程通信¶

PV操作时低级通信，高级通信指以高效率传递大量数据

共享存储：对共享空间的访问是互斥的基于数据结构的共享：低级通信基于存储区的共享：高级通信
管道通信: 一个管道只能采用半双工通信,各进程互斥的访问管道；管道写满才允许读，读完才允许写
消息传递：直接通信方式，间接通信方式

2.1.5 线程¶

一个进程中同样有“同时“做很多事情

线程是基本的CPU执行单元

引入线程后，进程是资源分配的基本单位，线程是调度的基本单位

TCB

线程基本不拥有系统资源，同一进程的线程共享进程资源

同一进程的线程切换不会引起进程切换，切换线程的开销小

线程的实现方式： - 用户级线程：阻塞会导致整个进程的阻塞；切换代价小；允许每个进程自定义调度算法 - 内核级线程：同一进程的线程切换需要从用户态转到核心态，开销大；内核线程阻塞时不会导致整个进程阻塞； - 组合方式

多线程模型： - 多对一：多个用户级线程对一个内核级线程，缺点是并发度不高 - 一对一：缺点是占用内核级线程多 - 多对多：

2.2 处理机¶

2.2.3 处理机调度的概念¶

调度的三个层次： - 高级调度：作业调度 - 中级调度：挂起 - 低级调度：进程调度,是操作系统最基本的一种调度

七态模型：

2.2.3 进程调度的过程，实际，方式¶

进程调度的时机：当前运行进程主动或被动放弃处理机不能进行进程调度与切换的情况： - 处理中断过程中 - 进程在操作系统的内核程序临界区 - 原子操作过程中

进程在操作系统内核程序临界区中不能进行调度和切换正确进程处于临界区时不能进行处理机调度错误

临界资源临界区：访问临界资源的那段代码

进程调度的方式： - 非剥夺式，非抢占方式 - 剥夺式，抢占式

进程切换的过程： - 对原来运行的进程的各种数据的保护 - 对新的进程各种数据的恢复

2.2.4 调度算法的评价指标¶

CPU 利用率：忙率时间 / 总时间

系统吞吐量：总共完成了多少道作业 / 总共花了多少时间

周转时间：作业被提交给系统到完成的时间

平均周转时间：周转时间之和 / 作业数

带权周转时间：作业周转时间 / 作业实际运行时间 >= 1

平均带权周转时间

等待时间：处于等待处理机状态时间之和

平均等待时间

响应时间：用户提交请求到首次产生响应所用的时间

2.2.5 调度算法¶

下面的算法适合批处理系统：

先来先服务 FCFS: - 作业调度和进程调度都可以 - 非抢占，抢占式的等于最短剩余时间优先 - 对长作业有利，对短作业不利 - 不会导致饥饿

短作业优先 SJF / 短进程优先 SPF: - 作业调度和进程调度都可以 - 一般是非抢占式，也有抢占式的版本，最短剩余时间优先 SRTN - 一般来说，SJF / SRTN 的平均等待时间、平均周转时间最少 - 对短作业有利，长作业不利 - 会导致饥饿

高响应比优先 HRRN - 作业调度，进程调度都可以 - 响应比 = (等待时间+要求服务时间) / 要求服务时间 >= 1 - 非抢占式 - 不会导致饥饿

下面的算法适合交互式系统：

时间片轮转调度算法 RR - 分时操作系统 - 用于进程调度 - 属于抢占式算法 - 如果时间片没用完但是进程完成了会提前结束 - 如果时间片太大，会退化为 FCFS；时间片太小切换会过于频繁 - 不会导致饥饿

优先级调度算法 - 调度选择优先级最高的作业/进程 - 作业调度/进程调度都可以 - 抢占式和非抢占式都有 - 就绪队列未必只有一个 - 静态优先级和动态优先级 - 会导致饥饿

多级反馈队列调度算法 - 用于进程调度 - 抢占式；指如果在运行时优先级更高的队列中有进程了，会被抢占，且被抢占的进程还是放到原来的队尾，不会下放 - 每个队列设置的时间片不同 - 会导致饥饿

2.3 进程同步、进程互斥¶

为了实现临界资源的互斥访问，需要遵循以下原则： - 空闲让进 - 忙则等待 - 有限等待：对请求访问的进程要保证能在有限时间内进入临界区 - 让权等待：如果进程不能进入临界区需要立即释放处理机

2.3.1 进程互斥的实现方法¶

软件实现： - 单标志法：用一个标志表示几号进程可以进入临界区，两个进程轮流进入；如果某进程一直不进入临界区就违背“空闲让进”原则 - 双标志先检查法：先检查其他进程是否在临界区，违背“忙则等待”原则；可能会有2个进程同时访问临界区，因为检查和上锁不是一气呵成的 - 双标志后检查法：先上锁，后检查；会有死锁，都无法进入临界区； - Peterson 算法：用 flag 表示某进程想要进入临界区，并用 turn 表示先让几号进程进入临界区；在访问临界资源前 flag 置为 true，并把 turn 设为另一个进程

硬件实现： - 中断屏蔽：缺点是不适合多处理机，不适合用户进程 - TestAndSet/TS/TSL：while中调用一个函数给临界资源上锁，函数返回上锁前此资源是否被上锁；这个函数是原子操作；缺点是不满足让权等待，仍然占用处理机资源 - Swap/Exchange/XCHG：和 TSL 没区别；缺点是让权等待，仍然占用处理机资源

2.3.2 信号量机制¶

使用操作系统提供的原语对信号量进行操作: wait(S) signal(S) 或者 P V 操作

对信号量的操作只有：初始化，P，V

整型信号量：表示系统中的某种资源数量；不满足让权等待，仍会占用处理机资源；

记录型信号量：剩余资源数+等待队列；wait中先减一，再检查是否有资源，没有(<0)就阻塞；signal中先加一，然后检查是否有阻塞进程，有(<=0)就释放一个阻塞进程

2.3.3 信号量机制实现进程互斥，同步¶

实现互斥： - 设置同步信号量 semaphore mutex，初始值为 1 - 成对使用PV操作

实现同步： - 设置同步信号量semaphore S，初始值为0 - 在前操作之后执行V - 在后操作之前执行P

信号量机制实现前驱关系： - 为每一对前驱关系各设置一个同步变量 - 在前操作之后执行V，可能有多个V - 在后操作之前执行P，可能有多个P

2.3.4 生产者，消费者¶

对 mutex 的 P 操作需要在同步信号量 P 操作里面

2.3.5 多生产者，多消费者¶

吃水果问题

这种情况可以不需要互斥型号量 mutex,如果缓冲区的大小大于 1 就需要设置互斥信号量，否则可能发生缓冲区的覆盖问题

2.3.6 吸烟者问题¶

需要4个同步信号量: 分别表示三种组合的和表示抽烟是否完成的

2.3.7 读者、写者问题¶

用一个 mutex 来保证读进程的加锁解锁和修改count 是原子操作

下面的代码是读者优先，写者可能会饥饿

下面的代码是写者优先

2.3.8 哲学家进餐问题¶

防止死锁的方法： - 最多允许4个哲学家同时进餐，用一个初始值为 4 的同步信号量 - 奇数号哲学家先拿左边的筷子，而偶数号哲学家相反；用 if 来判断一下 - 仅当一个哲学家左右两只筷子可用时才允许他抓起筷子（这个表述不是很准确）；在2个拿筷子的 P 操作外面用一个 mutex 的 PV 操作包起来，如果有人没拿到 2 支筷子其他所有人都不可以拿，直到他拿到；代码看下图

2.3.9 管程¶

信号量机制编写程序困难，易出错；管程也是一种同步机制

管程的组成（类） - 共享数据结构 - 一组过程 - 对共享数据设置初始值的语句 - 管程有一个名字

通过直接调用管程的方法访问共享数据，互斥和共享的代码在管程中封装好了

只有通过管程特定的入口才能访问共享数据

管程有很多入口，但每次只能开放其中一个入口，并且只能让一个进程或者线程进入

如果一个进程进入管城后因为其他原因阻塞，那么其他进程就暂时无法访问此管程；可以在管程中设置条件变量condititon 以及等待/唤醒操作，让一个进程阻塞或者线程在条件变量上等待，此时进程会释放管程的使用权；通过唤醒操作将等待在条件变量上的进程或线程唤醒；x.wait：将正在访问管程的进程放到 x 的等待队列上，并释放管程；x.signal：从阻塞队列中唤醒因 x 被阻塞的进程

2.4 死锁¶

2.4.1 死锁的概念¶

死锁：各个进程互相等待对方手里的资源；发生死锁的进程一定处于阻塞态；至少有 2 个或 2 个以上的进程同时死锁

饥饿：由于长期得不到想要的资源而无法推进；一个进程也可能发生死锁

死循环：跳不出循环；可以是运行态

死锁的必要条件： - 互斥条件 - 不可剥夺条件 - 请求和保持条件：进程已经保持了一个资源，但又提出了新的资源请求 - 循环等待条件：存在一种进程资源的循环等待链；注意的是发生死锁一定有循环等待，但是发生循环等待不一定有死锁

什么时候会有死锁： - 对系统资源的竞争 - 进程推进顺序非法 - 信号量的使用不当

死锁的处理策略： - 预防死锁 - 避免死锁 - 死锁的检查和解除

2.4.2 预防死锁¶

破坏死锁的必要条件 - 破坏互斥条件：把互斥的进程改造为允许共享使用 - 破坏不可剥夺条件： - 当某进程请求资源得不到满足时需要立即释放保持的所有资源 - 某进程需要的资源被其他进程占有时可以由操作系统协助把想要的资源强行剥夺

破坏请求和保持条件：进程运行前一次申请完所需要的全部资源
破坏循环等待条件：采用顺序资源分配法

2.4.3 避免死锁¶

安全序列

处于安全状态一定不会发生死锁；如果进入不安全状态，可能发生死锁；发生死锁一定是在不安全状态

银行家算法： - 先判断 request 的资源是否小于等于 need 资源，大于认为出错 - 如果 available 资源小于 request 表示没有足够的资源； - 有足够资源就阐释分配资源，并执行安全性算法

2.4.4 死锁的检测和解除¶

死锁的检测，必须： - 用某种数据结构来保存资源的请求和分配信息，如资源分配图 - 提供一种算法，利用上述信息来检测系统是否已进入死锁状态

如果不能消除所有的边就是发生了死锁

死锁的解除： - 用死锁检测算法化简资源分配图后，还连着边的就是死锁进程 - 解除死锁的主要方法： - 资源剥夺法 - 撤销进程法 - 进程回退法

3 内存管理¶

3.1 内存¶

3.1.1 内存基础知识¶

程序执行前需要放到内存中才能被CPU处理

内存地址：按字节编址，按字长编址

逻辑地址 / 物理地址，逻辑地址->物理地址：重定位

程序变成在内存中执行的程序的步骤：编译，链接，装入

链接的方式：链接后形成完整的逻辑地址

静态链接
装入时动态链接：优点是便于修改和更新，便于实现对目标模块的共享
运行时动态链接：运行时需要某个模块再进行链接；优点是能够加快程序的装入过程，节省内存空间

装入的方式：装入后形成物理地址 - 绝对装入：装入时直接写成绝对地址；只适用于单道程序环境 - 可重定位装入：也叫静态重定位，在装入时对逻辑地址进行重定位，变成绝对地址；运行期间不能再移动；必须分配要求的全部内存空间 - 动态运行时装入：也叫动态重定位，地址转换会推迟到程序执行时进行；需要重定位寄存器的支持；允许程序在内存中发生移动

3.1.2 内存管理¶

内存空间的分配和回收
虚拟内存对内存进行扩充
- 覆盖技术
- 交换技术
- 虚拟存储技术
提供地址转换功能:三种装入方式
内存共享：只读区域才可以共享，比如可重入代码
内存保护：两种办法
- 上限寄存器和下限寄存器
- 重定位寄存器和界地址寄存器（界地址寄存器来判断逻辑地址的范围）

3.1.3 覆盖和交换¶

覆盖： - 程序分为多个段，常用的段常驻内存中 - 内存中分为一个固定区和若干个覆盖区 - 常驻的段放在固定区中，不常用的段放在覆盖区，需要时调入内存 - 缺点：对用户不透明，增加用户编程负担

交换技术 / 对换技术： - 内存紧张时将某些进程暂时换出外存或者把外存中某些已经具备运行条件的进程换入内存；被换出外存的进程的PCB还是在内存中的 - 中级调度：被替换到外存的进程状态为挂起

磁盘存储空间： - 对换区（I/O快，连续分配方式），文件区（离散分配） - 进程运行时发现内存吃紧时进行交换；如许多进程运行时发生缺页；如果缺页率明显下降，就暂停换出 - 优先换出阻塞进程，优先换出优先级低的进程

3.1.4 连续分配管理方式¶

内部碎片：分配给进程的内存区域有些没有用上外部碎片：内存中有些空闲区域太小而难以利用

单一连续分配分为系统区，用户区只能有一道用户程序优点：实现简单不一定需要内存保护；缺点：利用率低，只能用于单用户，单任务的操作系统有内部碎片，无外部碎片
固定分区分配将用户区分为若干分区，有分区大小相等和分区大小不同的方式分区说明表优点：实现简单；缺点：用户程序太大时需要用覆盖技术，会降低性能有内部碎片，无外部碎片

动态分区分配 / 可变分区分配不预先划分内存分区使用数据结构记录内存使用情况：空闲分区表，空闲分区链分配算法：下一节内容分区的分配和回收没有内部碎片，有外部碎片

解决外部碎片：紧凑

3.1.5 动态分区分配算法¶

首次适应算法 first fit 从低地址开始递增查找空闲分区表按照地址从小到大排
最佳适应算法 best fit 空闲分区表按分区大小从小到大排找到第一个满足要求的，即分区大小满足且大小最小的分区缺点：会产生很多外部碎片
最坏适应算法 worst fit 空闲分区表按分区大小从大到小排缺点：之后有大进程没有空间分配
邻近适应算法 next fit 空闲分区按照地址从小到大排空闲分区链需要设置为循环链表每次从上次查找结束的位置开始往后查找

3.1.6 基本分页存储管理的基本概念¶

非连续分配管理方式： - 基本分页存储管理 - 基本分段存储管理 - 段页式存储管理

将内存分为大小相等的分区： - 页框 / 页帧 / 内存块 / 物理块 - 页框号 / 内存块号 / 页帧号 / 物理块号

将用户进程也分为也页框大小一样的区域，称为页或页面（最后一个页可能没有满）

逻辑地址到物理地址的转换： - 计算逻辑地址对应的页号 - 该页号在内存中的起始地址 - 逻辑地址在内面内的偏移量 - 物理地址 = 起始地址 + 偏移量

逻辑地址结构：

页表：页号到块号的对应关系每个页表项需要的字节数为内存中块数需要的字节数

3.1.7 基本地址变换机构¶

页表寄存器 PTR，存放页表在内存中的起始地址F和页表长度M；

进程未执行时，页表起始地址和长度放在在 PCB 中，当进程被调度时才会放到页表寄存器中

页式管理中地址是一维的；地址变换过程需要访问2次内存：第一次查页表，第二次访问目标内存单元

如果一个页表项只需要要 3B 就可以表示，还是会让其使用 4B，这样做是为了让每个页面恰好可以装的下整数个页表项

3.1.8 具有快表的地址变换机构¶

局部性原理： - 时间局部性 - 空间局部性

快表：TLB - 内存中的页表被称为慢表 - 是页表的一部分副本 - 如果快表命中，则只需要一次访存;否则还是需要2次 - 有的系统支持快表和慢表同时查询

3.1.9 两级页表¶

单级页表的问题： - 页表必须连续存放，页表很大时需要占用多个连续的页框 - 没有必要让整个页表常驻内存；因为进程一段时间内可能只需要访问几个特定的页面

问题的解决： - 为离散分配的页表再建立一张页表，称为页目录表或外层页表或顶层页表 - 虚拟存储技术（后面的章节的内容）

需要注意的细节： - 采用多级页表时，各级页表的大小不能超过一个页面 - 假设没有快表，需要访存3次

3.1.10 基本分段存储管理方式¶

分段：按照程序的逻辑划分为若干段，每段从0开始编址

段表： - 段表项的内容：段号（不会占段表的空间），段长，基址 - 每个段表项的长度是相同的 - 段表的地址和长度存在在段表寄存器中

地址变化：

分段，分页的对比： - 页对用户是不可见的，段对用户是可见的 - 页的大小是固定的 - 对用户来说，分页地址空间是一维的，分段地址空间是二维的 - 分段比分页容易实现信息共享和保护（不能被修改的代码称为纯代码，不属于临界资源，可以共享） - 访存次数：无快表，单级页表要两次，分段要两次 - 分段系统中也可以引入快表机制

3.1.11 段页式管理¶

分页、分段的优缺点：

地址结构：

段表 + 页表：

一个进程对应一个段表（段号，段长，页表存放块号），一个段对应一个页表（页号，内存块号）；

段表的起始地址和长度存放在段表寄存器中

地址转换：如果没有快表需要三次访存；

快表命中只需要一次访存

3.2 虚拟内存¶

3.2.1 虚拟内存的基本概念¶

局部性原理： - 时间局部性 - 空间局部性

传统存储器管理方式的特点：

一次性
驻留性

虚拟内存特征：

多次性
对换性
虚拟性

虚拟内存的实现：请求调页功能，页面置换功能 - 请求分页存储管理 - 请求分段存储管理 - 请求段页式存储管理

3.2.2 请求分页管理方式¶

操作系统要提供的功能： - 请求调页功能 - 页面置换

请求分页管理方式： - 页表机制 - 缺页中断机构 - 地址变换机构

页表机制：请求分页的页表增加的内容 - 状态位：1 表示调入内存 - 访问字段：供置换算法参考 - 修改位：调入内存后是否被修改过 - 外存地址

缺页中断机构： - 要访问的页面不在内存中时，就产生缺页中断，此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列 - 如果有空闲块，就分配一个空闲块 - 如果没有空闲块就由页面置换算法选择一个页面淘汰；如果修改过要将其写回外存，没修改过不需要 - 缺页中断是内中断的故障 - 如果在快表中表示肯定在内存中 - 新增的步骤： - 请求调页 - 页面置换 - 修改更新页表

3.2.3 页面置换算法¶

页面置换算法：追求少的缺页率 - 最佳置换算法 OPT 每次淘汰的页面是以后最长时间内不再被访问的页面 - 先进先出置换算法 FIFO - 最近最久未使用置换算法 LRU 在访问字段中设置自上次被访问以来所经历的时间 - 时钟置换算法 CLOCK 也叫最近未用算法 NRU 要注意访问的时候时钟指针是不会变的如果访问位都是 1，则扫描完一轮后把所有访问位置 0 最多进行 2 轮扫描 - 改进型的时钟置换算法用（访问位，修改位）表示各页面的状态第一轮扫描找（0，0）第二轮扫描找（0，1），扫描时要把访问位置 0，如果没找到访问位全部置0 第三轮扫描找（0，0）第四轮扫描找（0，1）

Belady 异常：为进程分配的物理块数增大时，缺页的次数不减反增的异常现象；只有FIFO才会有

3.2.4 页面分配策略¶

驻留集：请求分页存储管理中给进程分配的物理块的集合；不能太大，也不能太小

页面分配： - 固定分配： - 可变分配：驻留集大小可变

置换策略： - 局部置换：发生缺页时只能选自己进程的物理块进行置换 - 全局置换：可以将空闲的物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程

不存在固定分配+全局置换可变分配全局置换：只要缺页就分配新的物理块可变分配局部置换：更具发生缺页的频率动态增加或减少进程的物理块

物理块调入算法：

平均分配算法：空闲块平均分配给各进程
按比例分配算法：按照进程大小按比例分配
优先权分配算法：优先级大的分配多一些的物理块

何时调入页面： - 预调页策略：运行前调入 - 请求调页策略：运行时调入

从何处调入页面：外存中对换区（连续分配）的速度比文件区（离散分配）快

3.2.5 抖动和工作集¶

抖动 / 颠簸：频繁的页面调度行为;原因：分配给进程的物理块不够；原因是同时运行的进程太多，从而分配给每个进程的物理块太少

工作集： - 某段时间间隔里，进程实际访问页面的集合; - 设定一个窗口尺寸，从当前访问的页面往前看窗口尺寸的大小个页面，这个集合就是工作集； - 工作集的大小可能小于窗口尺寸 - 一般来说，驻留集的大小不能小于工作集大小

虚拟存储器性能影响因素：

页面大：缺页率低，减小页表长度，但是碎片多

页面小：缺页率高，减少碎片，提高内存利用率，但是页表长

*地址翻译：与计组相关

4 文件管理¶

4.1 文件¶

4.1.1 初识文件管理¶

4.1.2 文件目录¶

FCB 的有序集合就是文件目录，一个 FCB 是文件目录项

文件目录：

文件控制块： FCB，目录文件中的一条记录就是一个 FCB 记录中最重要最基本的是文件名和文件存放的物理地址对目录的操作：搜索，创建文件，删除文件，显示目录，修改目录
目录结构单级目录结构：不允许文件重名；不适用多用户系统两级目录结构：主文件目录和用户文件目录多级目录结构：树形目录结构；绝对路径，相对路径；无环图目录结构：共享计数器；方便实现文件共享
索引结点：FCB的改进；把 FCB 除文件名之外的信息放在索引结点中，目录表只留文件名和指向索引结点的指针

4.1.3 文件的逻辑结构¶

文件的逻辑结构：用户视角的结构 - 无结构文件 / 流式文件：如 txt - 有结构文件 / 记录式文件：如数据库表，每条记录有一个数据项可以作为关键字定长记录可变长记录

有结构文件的逻辑结构： - 顺序文件 - 索引文件：建立索引表 - 索引顺序文件

4.1.4 文件的物理结构¶

OS 对磁盘块的管理： - 对非空闲磁盘块的管理：文件的物理结构/文件分配方式 - 对空闲磁盘块的管理：文件存储空间管理

文件块、磁盘块的大小和内存块/页面一样大;所以文件的逻辑地址可以表示为（逻辑块号，块内地址）

文件的物理结构 / 文件分配方式： - 连续分配：每个文件在磁盘上占有连续的块；物理块号=起始块号（查表）+逻辑块号；拓展文件不方便 - 链接分配隐式链接显示链接：文件分配表 FAT;因为只需要查找FAT，所以也算是支持随机访问；一个磁盘一张 FAT - 索引分配: 为每个文件建立一张索引表，是逻辑块号到物理块号的映射；索引表中的内容也存放在一个磁盘块中，叫索引块；目录中需要记录每个文件的索引块；如果一个磁盘块存不下某文件的索引表的解决方案：链接方案：一个文件需要的索引块特别多时效率低多层索引：目录中记录顶级索引表的磁盘块混合索引

连续分配：

链接分配：

索引分配：

总结：

4.1.5 文件存储空间管理¶

存储空间的划分与初始化：

管理方式： - 空闲表法 - 空闲链表法空闲盘块链:分配和回收的时候都是修改链头和链尾指针；适合离散分配空闲盘区链： - 位示图法：用二进制位表示；（字号，位号）和盘块号之间的相互转换 - 成组链接法

4.1.6 文件的基本操作¶

4.1.7 文件共享¶

文件共享：共享意味着只有一份文件 - 基于索引结点的共享方式（硬链接） - 基于符号链的共享方式（软链接）

4.1.8 文件保护¶

文件保护： - 口令保护 - 加密保护 - 访问控制：访问控制表，精简的访问控制表（分组）

4.1.9 文件系统的层次结构¶

4.2 磁盘¶

4.2.1 磁盘的结构¶

磁盘、磁道、扇区

盘面、柱面

（柱面号、盘面号、扇区号）

磁盘的分类： - 活动头磁盘、固定头磁盘 - 可换盘磁盘、固定盘磁盘

4.2.2 磁盘调度算法¶

寻找时间：启动磁头臂+移动磁头延迟时间：旋转磁盘到指定扇区，\(T_r=(1/2)*(1/r)=1/2r\)，r为磁盘转速传输时间：读入或写入时间，\(T_t=(1/r)*(b/N)=b/(rN)\)，b为读/写的字节数，N为磁道上的字节数

磁盘调度算法： - 先来先服务 / FCFS： - 最短寻找时间优先 / SSTF：可能会饥饿 - 扫描算法 / SCAN / 电梯算法：不会有饥饿 - LOOK 调度算法：扫描算法提前改变磁头移动方向 - C-SCAN算法：只有往某个方向移动才处理请求，即到头后里面回到起点，中途不处理 - C-LOOK算法：

4.2.3 减少磁盘延时时间的方法¶

磁盘地址的结构设计：（柱面号、盘面号、扇区号）；如果是（盘面号、柱面号、扇区号），在连续读取数据时移动磁头的次数会多

交替编号：如果编号是连续的，在到达下一个扇区时没法立即读好数据，就需要再转一圈
错位命名：不同的盘面是一起转的，和交替编号的原因类似，读取下一个盘面扇区时如果是错位命名的，可以少转一些就读到要读的数据

4.2.4 磁盘初始化¶

步骤：

低级格式化 / 物理格式化：头、数据区、尾
分区：
逻辑格式化：如创建位示图，空闲分区表

引导块：

坏块的管理：

IO¶

5.1 IO设备¶

5.1.1 IO设备的概念和分类¶

按使用特性分类： - 人机交互类外部设备 - 存储设备 - 网络通信设备

按传输速率： - 低速 - 中速 - 高速

按信息交换的单位： - 块设备：传输快，可寻址 - 字符设备：传输慢，不可寻址，常使用中断驱动方式

5.1.2 IO控制器¶

IO设备由机械部件和电子部件（IO控制器，设备控制器）组成

IO控制器的功能：

IO控制器的组成：

5.1.3 IO控制方式¶

程序控制：

中断驱动方式：

DMA方式：

通道控控制方式：

总结：

5.1.4 IO软件层次结构¶

用户层软件

设备独立性软件：又称设备无关性软件主要实现的功能： 1 向上层提供同一的调用接口如 read/write 2 设备的保护 / 文件的保护：访问权限 3 差错处理 4 设备的分配和回收 5 数据缓冲区处理 6 建立逻辑设备名到物理设备名的映射关系：逻辑设备表 LUT：整个系统设置一张LUT 或者为每个用户设置一张LUT
设备驱动程序
中断处理程序