导图社区考研计算机

考研计算机

考研计算机操作系统的知识思维导图，包括进程管理、内存管理、输入/输出（I/O）管理等内容，这是整体的思维体系，考研中的助力。

编辑于2021-10-17 16:50:42

秋刀笔记

考研计算机

社区模板帮助中心，点此进入>>

秋刀笔记

相似推荐
大纲

操作系统

第二章进程管理

进程与线程

进程的概念与特征

进程的概念

为了更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性

进程控制块（PCB）

为了更好地描述进程的基本情况和运行状态，进而控制和管理进程

注意：PCB是进程存在的唯一标志

进程的一些典型定义

进程是程序的一次执行过程

进程是一个程序及其数据在处理机上顺序执行时所发生的活动

进程是具有独立功能的程序在一个集合上运行的过程，是资源分配和调度的独立单位（没有引入线程）

进程的特征

动态性：动态性是进程最基本特征，进程有着创建、活动、暂停、终止等过程，具有生命周期

并发性：多个进程实体同时存在内存中，引入进程的目的就是为了程序能与其他进程的程序并发执行

独立性

进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位

注意：凡是没有建立PCB的程序，都不能作为一个独立的单位参与运行

异步性

进程相互制约，进程以不可预知的速度向前推进

系统中一定要配置相应的进程同步机制

结构性

每个进程都要配置一个PCB对其进行描述

进程实体由程序段、数据段、进程控制段组成

进程的状态与转换

五个状态

运行态：进程正在处理机上运行

就绪态：进程已处于准备运行状态

阻塞态（等待态）：进程正在等待某一事件而暂停运行

基本状态

创建态：进程正在被创建，尚未转到就绪态

结束态：进程正在从系统中消失，包括正常结束或异常终止

基本状态之间的转换

就绪态→运行态：处于就绪态的进程获得处理机进入运行态

运行态→就绪态：处于运行态的时间片用完后，让处理机进入就绪态

运行态→阻塞态：进程请求处理机外其它资源时，运行态进入阻塞态

阻塞态→就绪态：进程等待其它资源的获得，如I/O资源或中断结束

进程控制

进程的创建

允许一个进程创建另一个进程，创建者称为父进程，被创建者称为子进程

创建过程（创建原语）

为新进程分配唯一的标识号，申请PCB（PCB是有限的）

为进程分配资源，为程序和数据以及用户栈分配必要的内存空间

初始化PCB，包括初始化标志信息、初始化处理机状态信息、初始化处理机控制信息，设置进程的优先级

若进程就绪队列可以接纳新进程，进程就进入就绪态

进程的终止

结束分类

正常结束：进程的任务已经完成并且准备推出运行

异常结束：进程正在运行，出现了某些异常事件，导致程序无法继续运行

外界干预：进程应外界请求终止运行

结束过程（撤销原语）

根据被终止进程的标识符，检索PCB，读取进程状态

若进程处于运行态，终止运行，剥夺处理机

终止进程之下的子进程

子进程拥有的全部资源还给父进程或操作系统

将PCB从队列中删除

进程的阻止和唤醒

阻塞原语执行过程

找到要被阻塞进程标识号对应的PCB

若该进程处于运行态，保护其现场，将其状态转换为阻塞态，停止运行

将PCB插入相应时间的等待队列

阻塞是进程自身的主动行为，自我阻塞

唤醒原语的执行过程

找到等待队列中进程相应的PCB

将其从等待队列中移出，置其状态为就绪态

把该PCB插入就绪队列，等待调度程序调度

唤醒是被相互有联系的其它进程进行唤醒

进程切换

进程切换是在内核支持下实现的

过程

保存处理机上下文，包括程序计数器和其它寄存器

更新PCB信息

把进程的PCB移入相应的队列。如就绪、在某事件阻塞等队列

选择另一个进程执行，更新其PCB

更新内存管理的数据结构

恢复处理机上下文

进程的组织

进程是一个独立的运行单位，也是操作系统进行资源分配和调度的基本单位，由以下三部分构成

进程控制块

进程描述信息

进程标识符（PID）：标志进程

用户标识符（UID）：进程归属的用户，主要为共享和保护服务

进程控制和管理信息

进程当前状态：描述进程状态信息

进程优先级：描述进程抢占处理机优先级

代码运行入口地址

程序的外存地址

进入内存时间

处理机占用时间

信号量使用

资源分配清单

用以说明有关地址内存空间或者虚拟地址空间状况，所打开的文件的列表和所使用的输入/输出设备信息

代码段指针、数据段指针、堆栈段指针、文件描述符、键盘、鼠标

处理机相关信息

处理机中各寄存器的值

通用寄存器值、地址寄存器值、控制寄存器值、标志寄存器值、状态字

程序段：能被进程调度程序调度到CPU执行的程序代码段

数据段：进程对应的程序加工处理的原始数据或程序执行时产生的中间或者最终结果

进程的组织方式

连接方式

按照进程状态将PCB分为多个队列

操作系统持有指向各个队列的指针

索引方式

根据进程状态的不同，建立几张索引表

操作系统持有指向各个索引表的指针

进程的通信

共享存储

通信进程之间存在一块可以被直接访问的共享空间

低级方式：基于数据结构共享

高级方式：基于存储区共享

操作系统只负责为通信进程提供可共享使用的存储空间和同步互斥工具，数据交换则由用户自己安排读/写指令完成

消息传递

进程间的数据交换是以格式化的消息为单位的，进程通过系统提供的发送消息和接收消息两个原语进行数据交换

直接通信方式：发送进程直接发送消息给接受进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息

间接通信方式：发送进程把消息发送给某个中间实体，接收进程从中间实体中获得消息

例如电子邮件系统

管道通信

发送进程以字符流形式将大量数据送入写管道，接收进程从写管道中接收数据

当写管道写满时，写进程的write（）系统调用将被阻塞，等待读进程将数据取走

当读进程将数据全部取走后，管道变空，此时读进程的read（）系统调用将被阻塞

功能：互斥、同步、确定对方存在

半双工通信，不可以同时读和写

限制管道的大小

管道变空的时候阻塞读进程

管道中的数据被读取后会马上被丢弃

线程概念和多线程模型

线程的基本概念

减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能

引入线程后，进程只作为系统资源的分配单元，线程作为处理机的分配单元

线程与进程的比较

调度

传统中进程是资源和独立调动的基本单位

引入线程后，进程只作为系统资源的分配单元，线程作为处理机的分配单元

拥有资源

进程是拥有资源的基本单位

并发性

引入线程后，进程可以并发执行，多个线程之间也可以并发执行，提高了系统的吞吐量

系统开销

同一进程的线程切换要比进程切换开销小得多

地址空间和其他资源

进程的地址空间之间相互独立，同一进程的各线程之间共享进程的资源，某进程的线程对其它进程不可见

通信方面

进程间通信需要进程同步和互斥手段的辅助，保证数据的一致性

线程间可以直接读/写进程程序段来进行通信

线程属性

不拥有系统资源，拥有唯一标识符和线程控制块

不同的线程可以执行相同的程序，同一个服务程序被不同用户调用时，操作系统将其创建为不同线程

统一进程的线程共享该进程拥有的全部资源

线程是处理机的独立调度单位

线程也有生命周期，阻塞、就绪、运行等状态

多CPU计算机中，各个线程可占用不同的CPU

每个线程都有一个线程ID，线程控制块（TCB）

切换同进程内的线程，系统开销很小

切换进程，系统开销大

由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预

线程的实现方式

用户级线程：有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在

内核级线程：线程的管理工作全部由内核完成

多线程模型

多对一

将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成，用户级线程对操作系统不可见（即透明）

优点：线程管理是在用户空间进行的，效率比较高

缺点：一个线程阻塞全部线程都会阻塞，多个线程不能并行运行在多处理机上

一对一

每个用户级线程映射到一个内核级线程上

优点：并发能力强

缺点：创建线程开销大，影响应用程序的性能

多对多

n个用户级线程映射到m内核级线程上，要求：m≤n

结合上述两种，既可以提高并发性，又适当的降低了开销

处理机调度

调度的概念

调度的基本概念：合理地对进程进行处理机分配

调度的层次

作业调度（高级调度）：从外存中选择作业送入内存，每个作业只调入一次，调出一次

内存调度（中级调度）：提高内存利用率和系统吞吐量，将暂时不能运行的进程调至外存，使其进入挂起态；或者将已经具备运行条件的进程调入内存，修改其状态为就绪态

进程调度（低级调度）：按照某种策略或方法从就绪队列中选取一个进程，将处理机分配给它（最基本的调度，频率很高）

三级调度的联系

作业调度为进程活动做准备，进程调度使进程正常活动起来，中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间

作业调度次数少，中级调度次数略多，进程调度频率最高

进程调度是最基本，不可或缺的

调度的时机、切换与过程

不能切换的情况

处理中断过程

进程在操作系统内核程序临界区的时候

其它需要完全屏蔽中断的原子操作过程

可以切换的情况

发生引起调度条件且当前进程无法继续进行

中断处理结束或者自陷处理结束

进程调度方式

非剥夺调度方式（非抢占方式）

如果想将处理机分配给一个更高优先级的进程，必须要等待当前占用处理机的进程释放处理机后才能将处理机分配给更高优先级进程

优点：实现简单、系统开销小，适用于大多数批处理系统

缺点：不适用于分时系统和大多数的实时系统

剥夺调度方式（抢占方式）

如果有更高级进程请求处理机，暂停正在执行的进程，将处理机分配给更高级进程

提高系统吞吐率和响应效率

调度的基本准则

CPU利用率，尽可能保持CPU处于忙碌状态

系统吞吐量：单位时间内CPU完成作业的量，调度算法和方式会对吞吐量造成较大影响

周转时间：作业提交到作业完成的时间

周转时间=作业完成时间-作业提交时间

平均周转时间=总周转时间/N个作业

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

平均带权周转时间=总带权周转时间/N个作业

等待时间：作业等待处理机的时间，衡量一个算法优劣，只需要简单的考察等待时间

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

进程的挂起态与七状态模型

暂时调到外存等待的进程状态称为挂起态

就绪挂起

阻塞挂起

”挂起“和”阻塞“的区别

两种状态都是暂时不能获得CPU的服务，但挂起态是将进程映像调到外存去了，而阻塞状态下进程映像还在内存中

典型的调度算法

先来先服务算法（FCFS）

既可用于作业调度，又可用于进程调度

先来的先分配处理机

优点：算法简单，对长作业有利，有利于CPU繁忙型作业（计算型）

缺点：效率低，不利于短作业，不利于I/O型繁忙作业

不会导致饥饿

非抢占式的算法

短作业优先算法（SJF）

进程调度

优先选择预计运行时间最短的进程

优点：平均等待时间、平均周转时间最短

缺点：对长作业不利，造成饥饿现象，没有考虑作业的紧迫性，用户可能可以缩短作业预估时间，使得无法做到短作业优先

产生”饥饿“现象，如果一直得不到服务，则称为”饿死“

SJF与SPF（短进程优先算法）是非抢占式的算法，但是也有抢占式的版本——最短剩余时间优先算法

优先级调度算法

作业调度和进程调度

分类

剥夺型：立即停止当前运行进程，将处理机分配给更高优先级进程

非剥夺型：等待当前进程运行完成，然后将处理机分配给更高优先级进程

优先级分类

静态优先级：进程创建后无法对优先级进行修改

动态优先级：可以根据进程运行状态，对进程优先级进行动态调整

优先级设置原则

系统进程＞用户进程

交互型进程＞非交互型进程

I/O进程＞计算机型进程（CPU繁忙型）

产生”饥饿“现象

有抢占式的，也有非抢占式的

高响应比调度算法

响应比=（等待时间+要求服务时间）/要求服务时间=1+等待时间/要求服务时间

等待时间相同情况下，要求服务时间越短响应比越大，有利于短作业进程

要求服务时间相同，作业响应比由其等待时间决定，等待时间越长响应比越高，实现先来先服务

对于长作业，作业的响应比可以随等待时间的增加而提高，等待时间足够长时，其响应比可以升到很高，从而获得处理机

不会导致饥饿

非抢占式的算法

时间片轮转算法

适用于分时系统，使用时间片，就绪进程按照到达先后拍成队列，依次在时间片内占用处处理机时间片到达时就释放处理机

时间片选择很重要，过大就变成了先来先服务，过短又变成了短作业优先

时间片影响因素：系统响应时间，就绪队列中的进程数目和系统的处理能力

不会导致饥饿

抢占式算法

多级反馈队列调度算法（融合了前面几种算法的优点）

实现思想

设置多个就绪队列，为每个队列设置不同的优先级，优先级依次递减

每个队列中时间片各不相同，时间片依次递增

每个队列按照先来先服务原则进行进程排队，若规定时间片内没有完成，就将进程放入下一级队列

只有高级队列为空的时候，低等级队列才能开始调度

优点

终端型作业用户：短作业优先

短批处理作业用户：周转时间较短

长批处理作业用户：讲过前面几个队列得到部分执行，不会长期得不到处理

产生饥饿现象

抢占式算法

进程同步

基本概念

临界资源

一次只允许一个进程使用的资源（例如打印机、特殊变量、数据）

临界资源的访问过程

进入区：检查进程是否可以进入临界区

临界区：可以访问临界资源的代码

退出区：将正在访问临界区的标志清除

剩余区：代码中其余部分

同步

亦称直接制约关系，为了完成某种任务而建立的多个进程，相互合作，所以要相互进行通信同步

遵循的原则

空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区

忙则等待：已有进程进入临界区后，其它试图进入临界区的进程必须等待

有限等待：对于请求访问临界区的进程，在有限时间内进入临界区

让权等待：进程不能进入临界区的时候，应当立即释放处理机

互斥：间接制约关系，当一个进程访问临界资源的时候，其它进程不能访问

实现临界区互斥的基本方法

软件实现方法

单标志法

两个程序进程交替进入临界区

优点：实现简单

缺点：可能会违背空闲让进，造成资源无法充分利用

双标志法先检查

每个进程访问临界区资源前，先检查临界资源是否被访问，如果空闲才能进入

优点：不用交替进入，可以连续使用

缺点：两个进程可能同时进入临界区，违背忙则等待

双标志法后检查

先设置自己标志，表明自己想要进入，检查对方标志，如果对方也要进入，那么就等待否则就进入

优点：不会导致两个进程都进入临界区

缺点：双方可能会互相谦让，导致饥饿现象

皮特森法

防止两个进程无限期等待，在算法三的基础上增加一个标志位，从而防止饥饿

优点：解决了饥饿现象

缺点：算法复杂

硬件实现方法

中断屏蔽法

对中断进行屏蔽、关中断

优点：关中断非常方便

缺点：限制了处理机交替执行程序的能力

硬件指令法

读出指定标志后，将该标志置为真

优缺点

优点

适用于任意数目的进程

简单且容易验证正确性

支持进程内有多个临界区

缺点

不能实现让权等待

可能会导致饥饿现象

信号量

整型信号量

wait：资源-1 signal：资源+1

没有遵循让权等待机制，会导致进程处于忙等状态

记录型信号量

不存在”忙等“现象的进程同步机制

除了需要一个用于代表资源数目的整型变量vaule外，再增加一个进程表L，用于链接所有等待该资源的进程

利用信号量实现同步

设S为进程P1和P2同步的公共信号量，初值为0，通过设置S的值可以使得P1与P2按照一定的顺序执行

利用信号量实现互斥

通过设置S的值，可以实现进程对临界资源的互斥访问

利用信号量实现前驱关系

通过设置不同的进程运行结束后，产生不同的信号量，从而可以使得目标进程运行，从而实现前驱关系

管程

定义：一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程

组成

管程的名称

局部于管程的共享结构数据说明

对该数据结构进行操作的一组过程

对局部于管程的共享数据设置初始值的语句

基本特性

局部于管程的数据只能被局部于管程内的过程所访问

一个进程只有通过调用管程内的过程才能进入管程访问共享数据

每次仅允许一个进程在管程内执行某个内部过程

死锁

死锁的概念

死锁的定义：多个进程因竞争资源造成的一种僵局，没有外力作用，这些进程都无法向前继续推进

死锁产生的原因

系统资源的竞争

进程推进顺序非法

死锁产生的必要条件

互斥条件：进程对分配的资源进行排他性控制

不可剥夺条件：进程获得资源在未使用完之前，不能被其它进程强行夺走

请求并保持条件：进程已经至少保持了一个资源，提出新的资源请求，而该资源已经被其它进程占有，此时该进程被阻塞，但是自己已经获得的资源保持不放

循环等待条件：你等我释放，我等你释放

死锁的处理策略

死锁预防

破坏四个必要条件中的一个或几个，防止死锁

资源分配保守，宁可资源闲置

一次性请求所有资源，资源剥夺，资源按序分配

优点：适用于突发式处理的进程，不必进行剥夺

缺点：效率低，进程初始化时间长，剥夺次数过多，不便灵活申请资源

避免死锁

在资源的动态分配中，用某种方法防止系统进入不安全状态，避免死锁

运行过程中预测分配资源是否会死锁

寻找可能安全的序列

优点：不必进行剥夺

缺点：必须知道将来的资源需求，进程不能被长时间阻塞

死锁的检测及解除

允许进程死锁，通过检测及时的判断死锁，然后对其进行解除

宽松，只要允许就分配资源

定期检查是否死锁

优点：不延长初始化时间，允许对死锁进行现场处理

缺点：通过剥夺解除死锁，造成损失

死锁预防

破坏互斥条件：某些资源只能被互斥访问，并且某些情况下必须保护互斥性

破坏不剥夺条件

释放已经占有的资源

特点：增加系统开销，实现起来复杂，降低吞吐量

常用于状态易于保存和恢复的数据（例如CPU寄存器和内存资源）

破坏请求并保持条件

一次性申请完所需要的全部资源

特点：实现简单，但是资源被严重浪费，甚至可能导致进程饥饿

破坏循环等待条件

采用顺序资源法，对进程进行顺序推荐

特点：进程编号必须稳定，可能会导致资源浪费，并且不利于用户编程

死锁避免

系统安全状态

按照某种方式分配资源后，是否会导致死锁，如果会导致死锁，那么就是不安全状态，反之就是安全状态

银行家算法

思想：通过计算当前资源的不同分配方式，从而预测系统是否会进入不安全状态

死锁的检测和解除

资源分配图：圆圈表示进程，框表示一类资源，进程到资源的有向边称为请求边，资源到进程的边称为分配边

死锁定理

在资源分配图中找到分配满足的进程，然后消去其请求边和分配边

如果最后所有边都可以被消去，那么就是可以简化的，不存在死锁，反之存在死锁

死锁解除

资源剥夺法：挂起某些死锁进程，抢占资源，将这些资源分配给其它死锁进程，但要防止挂起时间过长

撤销进程法：强制撤销部分甚至全部死锁进程，并且剥夺它们的资源，撤销原则可以根据优先级和撤销进程的代价进行

进程回退法：让一个或多个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺；要求系统保持进程历史信息，设置还原点

死锁、饥饿、死循环的区别

死锁：各进程相互等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象

饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象

死循环：某些进程执行过程中一直跳不出某个循环的现象

第三章内存管理

内存管理概念

内存管理的基本原理和要求

程序执行前需要先放到内存中才能被CPU处理——缓和CPU与硬盘之间的速度矛盾

内存管理的功能

内存空间的分配与回收：操作系统完成主存储器空间的分配和管理

地址转换：逻辑地址转换为物理地址

内存空间的扩充：利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存

内存保护：保护各道作业在各自存储空间运行，互不干扰

程序的装入和链接

创建步骤

编译：由编译程序将用户源代码编译成若干目标模块

链接：由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起，形成一个完整的装入模块

装入：由装入程序将装入模块装入内存运行

链接的类型

静态链接：程序运行之前，将库函数连接成一个完整的可执行程序

装入时动态链接：将用户源程序编译后得到目标模块，装入内存时，采用边装入边链接的方式

运行时动态链接：对于某些目标模块的链接，程序需要时才会对其链接；便于修改和更新，便于实现对目标模块的共享

装入模式

绝对装入

装入时按照实际的内存地址，将程序和数据装入内存

优点：不需要对程序和数据的地址进行修改

缺点：只适用于单道程序环境

可重定位装入（静态重定位）

此时采用的是模块与模块的相对地址，然后将程序和数据装入内存

装入时对目标程序中的指令和数据的修改过程称为重定位，地址变换通常是在装入时一次完成的，又被称为静态重定位

特点：作业装入必须要一次性全部装入，并且运行中作业不能在内存中移动，也不能申请内存空间

动态运行时装入（动态重定位）

装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，当程序真正执行时才进行转换

特点

需要重定位寄存器，可以将程序分配到不连续的存储区中

便于程序段的共享

可以向用户提供更大的地址空间（地址空间大于存储空间）

逻辑地址空间与物理地址空间

逻辑地址空间：即相对地址，链接程序依次按照各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间

物理地址空间

内存中物理单元的集合，是地址转换的最终地址，进程在运行时执行指令和访问数据，最后要通过物理地址从主存中存取

地址重定位：逻辑地址转换成物理地址的过程

内存保护

CPU中设置上、下寄存器，存放用户作业在主存中的下限和上限地址，每当CPU要访问一个地址时，分别和两个寄存器的数据比较，判断是否越界

重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）：重定位寄存器中包含最小物理地址，界地址寄存器中包含逻辑地址的最大值

地址转换过程：逻辑地址→界地址寄存器→重定位寄存器→物理地址

覆盖与交换

覆盖

思想：将程序分为多个段（多个模块），常用的段常驻内存，不常用的段在需要时调入内存

将用户空间分为一个固定区和若干覆盖区，活跃部分放在固定区，即将访问的段放在覆盖区

特点：打破了必须将一个进程的全部信息装入主存后才能运行的限制，内存中能够更新的地方只有覆盖区的段，不在覆盖区的段会常驻内存

交换

思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）

换出：将处于等待状态的程序从内存中转移到辅存

换入：把准备好竞争CPU运行的程序从辅存转移到内存

结构：把磁盘空间分为文件区和对换区两部分

文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式

对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区，主要追求换入换出速度，因此通常对换区采用连续分配方式

交换存在的问题

备份存储，使用快速硬盘，要求存储空间足够大，并且能够对内存映像进行直接访问

转移时间和所交换的内存空间成正比

只有进程空闲状态才能将进程换出

交换空间通常作为磁盘的一整块，且独立于文件系统，因此使用起来会很快

交换通常在有许多进程运行且内存吃紧时开始启动，系统负荷降低就暂停

普通的交换使用不多，但交换策略的某些变体在许多系统中仍然发挥作用

注意：PCB会常驻内存，不会被换出外存

连续分配管理方式

单一连续分配

内存分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分，用户区为用户提供

优点

无需进行内存保护，不会出现越界异常

实现简单，无外部碎片，采用覆盖技术，不需要额外技术支持

缺点

只适用于单用户，单任务的操作系统

存在内部碎片，存储器利用率低

固定分区分配

种类

分区大小相等：用一台计算机去控制多个相同对象的场合，缺乏灵活性

分区大小不等：划分为多个较小的分区，适量的中等分区和大量少分区

优点

适用于多道程序的存储，无外部碎片

缺点

程序太大，无法放入任何一个分区

主存利用率低，存在内部碎片

不能实现多进程共享一个主存区

动态分区分配

在进程装入内存的时候，根据内存的大小动态地建立分区

优点：分区大小可以根据进程的实时情况进行分配

缺点：存在外部碎片，最后导致主存利用率下降

采用紧凑技术可以缓解这种缺陷

动态分配算法

首次适应算法

空闲分区按照地址递增的顺序进行查找，找到第一个满足要求的分区进行分配

优点：综合看性能最好，算法开销小，回收分区后一般不需要对空闲分区队列重新排序

最佳适应算法

按照容量递增的顺序形成分区链，找到第一个能满足要求的空闲分区

优点：可以尽可能地留下大片空闲区

缺点

性能较差，产生最多的外部碎片

回收分区后可能需要对空闲分区队列重新排序

最坏适应算法（最大适应算法）

空闲分区按照容量递减的次序查找，第一个满足条件的进行分配

优点：可以减少难以利用的小碎片

缺点

导致很快没有较大的内存块，性能很差

不利于大进程，算法开销大

邻近适应算法（首次适应算法）

分配内存时从上次查找结束的位置开始继续查找

优点：算法开销小

缺点：会使高地址的大分区也被用完

非连续分配管理方式

允许一个进程分散的装入不相邻的内存分区

基本分页存储管理方式

设计思想

将主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位，进程以块为单位进行空间申请

分页存储与固定分区技术很像，但是其分页相当于分区又很小，分页管理不会产生外部碎片，产生的内部碎片也非常小

分页存储的基本概念

页面和页面大小

进程中的块=页

内存中的块=页框（页帧）

进程申请主存空间，为每个页面分配主存中可用页框，即页与页框一一对应

页面大小要适中

页面太小：进程页面数过多，页表过程，增加内存占用，降低硬件地址转换效率

页面太大：页内碎片过多，降低内存利用率

地址结构

页号（有多少页的编号）+页内偏移（页内存了多少东西）

页表

为了便于在内存中找到进程的每个页面对应的物理块，系统为每个进程建立一张页表，记录页面在内存中对应的物理块号，页表一般放在内存中

页表项：页号+物理内存的块号（不要与地址结构搞混）

页表项的物理内存块号+地址结构中的页内偏移=物理地址

基本地址变换机构

计算方式

页号P=A/L，页内偏移量W=A％L

比较页号P和页表长度M，若P≥M，则产生越界中断

页表中页号P对应的页表项地址=页表始址F+页号P✖页表项长度，取出该页表项内容b，即为物理块号

计算E=b✖L+W，使用E去访问内存

页表项大小的设计应当尽量一页正好能装下所有页表项

分页管理存在的问题

地址变换过程必须足够快，否则访存速率会降低

页表不能太大，否则会降低内存利用率

组成

设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M

页表的始址和页表长度放在进程控制块（PCB）中

具有快表的地址变换机构

可优化方向：如果页表放在内存中，取地址访问一次内存，按照地址取出数据访问一次内存，共需要两次访问内存

优化：地址变换机构中增加一个具有并性查找能力的高速缓冲寄存器（快表），又称相联存储器（TLB）

相联存储器既可以按照地址查找，也可以按照内容查找

访问一个逻辑地址的访问次数

基本地址变换机构：两次访存

具有快表的地址变换机构

快表命中，只需一次访存

快表未命中，需要两次访存

变换过程

CPU给出逻辑地址后，先查询快表中是否命中

若快表命中，直接从快表中该页对应的页框号，与页内偏移量拼接成物理地址

若快表不命中，再按照正常方式从页表中查询相应页表项，并将该页表项存入快表中（按一定策略）

两级页表

如果页数过多，就会导致页表也过多，那么我们可以考虑设置一个用来储存页表的页表（套娃）

逻辑地址空间格式=一级页号+二级页号+页内偏移

设计多级页表的时候，最后一定要保证顶级页表一定只有一个

建立多级页表的目的在于建立索引，不必浪费主存空间去存储无用的页表项，也不用盲目式的查询页表项

基本分段存储管理方式

出发点

分页是从计算机角度考虑设计的，目的是为了内存的利用率，提高计算机性能，分页通过硬件机制实现，对用户完全透明

分段是从用户和程序员的角度提出，满足方便编程、信息保护共享、动态增长及动态链接等多方面的需求

分段

按照用户进程的自然段划分逻辑空间

地址结构=段号S+段内偏移量W

页式系统中，页号和页内偏移对用户透明

段式系统中，段号和段内偏移量必须由用户显式提供

段表

每个进程都有一张逻辑空间与内存空间映射的段表，其中每个段表项对应进程的一段，段表项记录该段在内存中的始址和长度

段表内容=段号+段长+本段在主存中的地址

地址变换机构

逻辑地址A中取出段号S和段内偏移量W

比较段号S和段表长度M，若S≥M，则产生越界中断，否则继续执行

段号S对应的段表项地址=段表始址F+段号S✖段表项长度，从该段表项中取出段长C，若段内偏移量≥C，则产生越界中断，否则继续执行

取出段表项中该段的始址b，计算E=b+W，用得到的物理地址E去访问内存

变换过程

段的共享与保护

共享

两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现

纯代码或者可重入代码以及不可修改的数据可以被共享

不能被修改的代码称为纯代码或可重入代码（不属于临界资源）

保护机制

存取控制保护

地址越界保护

段页式管理方式

页式存储管理能有效的提高内存利用率，分段存储管理能反映程序的逻辑结构并有利于段的共享，将两种方式结合起来，就得到了段页式存储管理方式

这二者结合的方法经常在计算机理论中遇到

思想

作业的地址空间首先被分为若干逻辑段，每段有自己的段号

每个段分成若干大小固定的页

对内存空间的管理仍然和分页存储管理一样

地址结构

段号S+页号P+页内偏移量W

为了实现地址变换，系统为每个进程建立了一张段表，每个分段有一个页表

一个进程中，段表只能有一个，页表可以有多个

补充

分段和分页的区别

分页对用户不可见，分段对用户可见

分页的地址空间是一维的，分段的地址空间是二维的

分页（单级页表）、分段访问一个逻辑地址都需要两次访存，分段存储中可以引入快表机构

分段更容易实现信息的共享和保护

分段与分页的优缺点

分页管理

优点：内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片

缺点：不方便按照逻辑模块实现信息的共享和保护

分段管理

优点：很方便按照逻辑模块实现信息的共享和保护

缺点

如果段长过大，为其分配很大的连续空间会很不方便

会产生外部碎片

虚拟内存管理

虚拟内存的基本概念

传统存储管理方式的特征

一次性

作业必须一次性全部装入内存后，才能开始运行

作业很大无法装入则无法运行

大量作业要求运行时，由于内存不足，只能一部分作业先运行，导致多道程序度的下降

产生的两种情况

驻留性：作业装入内存后，一直驻留在内存中，任何部分不会被换出

局部性原理

时间局部性

一条指令执行后，不久后该指令可能再次执行；数据被访问后，可能再次被访问

原因：程序中存在着大量的循环操作

时间局部性通过将最近使用的指令和数据存储在高速缓冲存储器中

空间局部性

一旦程序访问了某个存储单元，不久后，附近的存储单元也被访问

原因：指令通常是顺序存放，顺序执行的，数据一般也是以向量、数组、表等形式簇聚存储的

空间局部性使用较大的高速缓存，将预取机制继承到高速缓存控制逻辑中实现

虚拟存储器的定义和特征

基于局部性原理，程序的一部分装入内存，一部分留在外存，需要的时候将外存内容调入内存，就好像产生了一个巨大的内存空间

特征

多次性：作业在运行时，分多次调入内存运行

对换性：作业不必一直驻留内存，允许作业在运行过程中进行换进换出

虚拟性：从逻辑上扩充内存容量，使用户看到的内存容量远大于实际的内存容量

虚拟内存技术的实现

建立在离散分配的内存管理方式上

实现方式

请求分页存储管理

请求分段存储管理

请求段页式存储管理

硬件支持

一定容量的内存和外存

页表机制（或段表机制）

中断机制

地址变换机构

请求分页管理方式

系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能

页表机制

组成：页号、物理块号、状态位P、访问字段A、修改位M、外存地址

状态位：当前页是否已经调入内存

访问字段A：记录本页在一段时间内被访问的次数

修改位M：记录本页是否被修改过

外存地址：指出该页在外存上的位置（通常是物理块号）

缺页中断机制

当访问页面不存在内存时就会产生缺页中断

特点

指令执行期间产生中断，而不是指令执行之后产生中断和处理中断

一条指令在执行期间，可能产生多次缺页中断

地址变换机构

检索快表，找到访问页，修改页表项中的访问位，利用页表项中给出的物理块号和页内地址形成的物理地址

没有找到该页的页表项，去内存中查找页表，看该页是否已经调入内存，没有调入则产生缺页中断，请求从外存把该页调入内存

补充知识点

虚拟内存的最大容量是由计算机的地址结构（CPU寻址范围）确定的

虚拟内存的实际容量=min（内存和外存的容量之和，CPU寻址范围）

页面置换算法

最佳置换算法（OPT）

选择永不使用或者最长时间内不再访问的页面进行淘汰，但是现实中是无法预知的

优点：缺页率最小，性能最好

先进先出页面置换算法（FIFO）

优先淘汰最早进入的页面

优点：实现简单

缺点：与进程的实际运行规律不匹配

Belady异常：增大分配的物理块数但是故障数不减反增

只有先进先出算法会出现

最近最久未使用置换算法（LRU）

LRU是堆栈类算法

选择最近最长时间没有被访问的页面进行淘汰，每个页面设置一个访问字段，用来标识上次被访问到现在经历的时间

优点：性能好

缺点：实现复杂，需要寄存器和栈的硬件支持

时钟置换算法（CLOCK）

像一个时钟一样转圈，每个页面设置一个使用位（访问位），遇到没有被使用过的就会将页面换出，然后将使用位置为0，如果遇到使用的就会将使用位置为0，然后扫描下一个

优点：性能接近于最佳置换算法

缺点：实现复杂、开销大

改进型CLOCK算法

使用位（访问位）的基础上增加修改位

扫描过程

扫描缓冲区，选择第一个使用位和修改位都为0的页面换出

第一步失败后，查找使用位为0，修改位为1进行替换，对于每个跳过的帧，将使用位置为0

第二步失败后，指针回到初始地点且使用位（访问位）均为0，重复第一步

优点：相对于未改进型，节省了时间

页面分配策略

驻留集：给一个进程分配的物理页框的集合就是这个进程的驻留集

考虑因素

分配给一个进程的存储量越小，任何时候驻留在主存中的进程数就越多，可以提高处理机的时间利用率

一个进程在主存中的页数过少，页错误率就会相对较高

页数过多，对进程的错误率也不会产生过多的影响

分配策略

固定分配局部置换

每个进程分配固定物理块数，缺页的时候就进行换页

难以确定每个进程应该分配的物理块数

太少会频繁出现缺页中断，太多会使CPU和其它资源利用率下降

可变分配全局置换

进程分配一定物理块，系统自身保留一定空闲物理块，如果进程缺页，就对该进程分配新的物理块

优点：最容易实现，动态调整物理块分配

缺点：如果盲目分配物理块，就会导致多道程序并发能力下降

可变分配局部置换

根据进程的缺页情况，对物理块进行动态分配，如果频繁缺页，就对其多分配物理块，如果缺页率特别低，就减少其物理块

优点：保持了系统的多道程序并发能力

缺点：增大了开销，实现复杂

调入页面的时机

预调页策略：将预计不久后被访问的页面调入，成功率约为50％

请求调页策略

当进程提出缺页的时候，再按照一定策略进行调页

特点：一次调入一页，调入/调出页面数多时会花费过多的I/O开销

一般情况下，两种策略同时使用

从何处调入页

拥有足够的兑换空间：可以全部从对换区调入所需页面，提高调页速度

系统缺少足够的对换区空间

不会被修改的文件从文件去调入，可能被修改的部分换入对换区，以后再从对换区调入

原理：读速度比写速度快

UNIX方式：进程相关文件访问文件区，没有运行的页面从文件区调入，曾经运行过但又被换出的页面放在对换区

抖动

刚换出的页面又要换入内存

原因

主要原因：分配的物理页帧数不足

置换算法不当

工作集

某段时间内，进程要访问的页面集合

原理

操作系统跟踪每个进程的工作集，并未进程分配大于其工作集的物理块

落入工作集的页面需调入驻留集中，落在工作集外面的页面可以从驻留集中换出

若还有空闲物理块，可以再调入一个进程到内存以增加多道程序数

若所有进程的工作集之和超过了可用物理块的总数，操作系统就会暂停一个进程，将其页面调出并将其物理块分配给其它进程

第五章输入/输出（I/O）管理

I/O管理概述

I/O设备

人机交互的外部设备

用于与计算机用户之间交互的设备，如打印机、鼠标、键盘

交换速度相对较慢，以字节为单位进行数据交换

存储设备

用于存储程序和数据的设备，如磁盘、磁带、光盘

交换速度较快，以多字节组成的块为基本单位交换

网络通信设备

用于与远程设备通信的设备，如网络接口，调制解调器

速度介于前两类之间

按传输速率分类

低速设备：每秒进位几个字节到数百字节，如鼠标、键盘

中速设备：传输速率为每秒数千字节到数万字节，如行式打印机、激光打印机

高速设备：传输速率在数百千字节至千兆字节的一类设备，如磁带机、磁盘机、光盘机

按信息交换的单位分类

块设备

信息存取总是以数据块为基本单位，存储信息的设备称为块设备

传输速率高，可寻址，可以任意读写某块

字符设备

用于数据输入输出的设备为字符设备，传输的基本单位是字符，如交互式终端机、打印机

传输速率低，不可寻址，输入输出时常采用中断驱动方式

I/O控制方式

程序直接控制方式

计算机从外部设备读取数据到存储器，每次读一个字的数据，对读入的每个字，CPU都要对外设状态进行循环检查，直到确定该字已经在I/O控制器的数据寄存器中

读写单位：字

优点：容易实现，操作简单

缺点：CPU高速性和I/O设备的低速性的矛盾（降低了CPU的利用率），CPU和I/O设备只能串行工作

中断驱动方式

允许I/O设备主动打断CPU的运行并请求服务，进而解放CPU，使其向I/O控制器发送读命令后可以继续做其它有用的工作

读写单位：字

优点：比程序直接控制方式更有效

缺点：数据的传输必须要经过CPU，仍然会消耗较多的CPU时间

DMA驱动方式

在I/O设备和内存之间开辟直接的数据交换通路，彻底解放CPU

特点

读写单位：数据块

设备直接送入内存

只有当一个或多个数据块开始或结束的时候，CPU才会进行干预

寄存器

命令/状态寄存器（CR）：用于接受CPU发送的I/O命令和有关控制信息或设备状态

内存地址寄存器（MAR）：数据直接在设备与内存之间交互

数据寄存器（DR）：用于暂存从设备到内存或者从内存到设备的数据

数据计数器（DC）：存放本次要传送的字（节）数

通道控制方式

设置一个专门负责输入/输出的处理机（DMA方式的发展），实现对一组数块的读写以及相关控制和管理为单位干预

读写单位：一组块

优点：有效地提高了系统资源利用率

缺点：实现较为复杂

DMA与通道的区别

DMA需要CPU来控制传输数据块的大小、传输的内存位置，而通道方式中这些信息都是由通道控制的

DMA控制器对应一台设备与内存传递数据，通道可以控制多台设备与内存的数据交换

I/O子系统的层次结构

层次划分

用户层I/O软件：实现与用户交互的接口，用户可以直接调用在用户层提供的、与I/O操作有关的库函数，对设备进行操作

设备独立性软件

用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护及设备分配与释放，同时为设备管理与数据传送提供必要的存储空间

设备独立性也称为设备无关性，使得应用程序独立于具体使用的物理设备（使用逻辑设备名）

使用逻辑设备名的好处

增加设备分配的灵活性

易于实现I/O重定向

主要功能

执行所有设备的公有操作（设备的分配与回收、逻辑设备命映射为物理设备名、对设备进行保护、禁止用户直接访问设备），屏蔽设备之间信息交换单位大小与传输速率的差异

向用户层（文件层）提供统一接口，无论何种设备，它们向用户提供的接口都是相同的

设备驱动程序

与硬件直接相关，负责实现系统对设备发出的操作命令，驱动I/O设备工作的驱动程序

中断处理程序

用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完并恢复被中断进程的现场后，返回被中断进程

硬件设备

I/O设备通常包括一个机械部件和一个电子部件

设备控制的功能

接收和识别CPU或通道发来的命令

磁盘读写查找等命令

实现设备与控制器之间、控制器与主存之间的数据交换

发现和记录设备及自身的状态信息，供CPU处理使用

设备地址识别

设备控制器的组成

设备控制器与CPU的接口

信号线：数据线、地址线、控制线

设备控制器与设备的接口

每个接口存在数据、控制和状态三种类型的信号

I/O控制逻辑

用于实现对设备的控制；通过一组控制线与CPU进行交互，对从CPU收到的I/O命令进行译码

注意

一个I/O控制器可能会对应多个设备

数据寄存器、控制寄存器、状态寄存器可能有多个，且这些寄存器都要有相应的地址，才能方便CPU操作

有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O

一些计算器则采用I/O专用地址，即寄存器独立编址

I/O核心子系统

I/O子系统概述

提供的服务主要有I/O调度、缓冲与高速缓存、设备分配与回收、假脱机、设备保护和差错处理等

I/O调度概念

通过I/O调度改善系统整体性能，使得进程之间公平共享设备访问，减少I/O完成所需要的平均等待时间

使用主存或者磁盘上的存储空间的技术，如缓冲、高速缓存、假脱机等来改善计算机效率

高速缓存与缓冲区

磁盘高速缓存

使用磁盘高速缓存技术来提高磁盘的I/O速度，对高速缓存复制的访问要比原始数据访问更加高效

磁盘高速缓存，逻辑上属于磁盘，物理上属于驻留在内存中的盘块

在内存中的两种形式

在内存中开辟一个单独的存储空间作为磁盘高速缓存，大小固定

把未利用的内存空间作为一个缓冲池，供请求分页系统和磁盘I/O时共享

缓冲区

引入缓冲区的目的

缓和CPU与I/O之间的速度差异矛盾

减少对CPU的中断频率，放宽对CPU中断相应时间的限制

解决基本数据单元大小不匹配的问题

提高CPU和I/O设备之间的并行性

实现方法

采用硬件缓冲器（成本过高），除了关键位置，一般不使用硬件缓冲器

采用缓冲区（位于内存区域）

分类

单缓冲

设备和处理机之间设置缓冲区，设备和处理机交换数据的时候，先把交换的数据写入缓冲区，然后需要数据的设备或处理机从缓冲区中取走数据

使用时间为max（C，T）+M

双缓冲

设置两个缓冲区，当缓冲区1满时，向缓冲区2中注入数据，只有缓冲区满才能取出数据

提高了处理机和输入设备的并行操作程度

max（C+M，T）

循环缓冲

包含多个大小相等的缓冲区，每个缓冲区中有一个链接指针指向下一个缓冲区，最后一个缓冲区指针指向第一个缓冲区，多个缓冲区构成一个环形

缓冲池

缓冲区分为三个队列：空缓冲队列、装满输入数据的缓冲队列、装满输出数据的缓冲队列

四种缓冲区：收容输入数据的工作缓冲区、提取输入数据的工作缓冲区、收容输出数据的工作缓冲区、提取输出数据的工作缓冲区

注意

管道通信中的“管道”其实就是缓冲区，要实现数据的双向传输，必须设置两个管道

设备分配与回收

概述

根据用户I/O请求分配设备

原则：充分发挥设备的使用效率，避免进程死锁

设备类型分类

独占式使用设备：设备只能互斥使用，如打印机

分时共享使用设备：通过分时共享来提高设备的利用率

以SPOOLing方式使用外部设备：使用空间换时间，对I/O设备进行批处理

设备分配的数据结构

设备控制表（DCT）：一个设备控制表就表征一个设备，控制表中的表项就是设备的各个属性

控制器控制表（COCT）：COCT与DCT一一对应关系，DCT需要一个表项来表示控制器，即一个指向控制器控制表的指针

通道控制表（CHCT）：CHCT提供服务的那几个设备控制器

系统设备表（SDT）：记录已经连接到系统中的所有物理设备的情况

设备分配的策略

分配原则：充分发挥设备效率，避免进程死锁

分配方式

静态

系统一次性分配该作业要求的设备、控制器，直到作业结束

优点：没有死锁问题

缺点：降低了设备使用率

动态

进程执行过程中根据执行需要进行分配

优点：提高了设备利用率

缺点：分配算法不当可能导致死锁

设备分配算法

先请求先分配

优先级高者优先

独占设备一般使用静态分配，共享设备一般使用动态分配

I/O调度

设备分类

独占设备：一个时段只能分配给一个进程，如打印机

共享设备：可同时分配多个进程使用，如磁盘；各进程往往是宏观上同时共享使用设备，而微观上是交替使用

虚拟设备：采用SPOOLing技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用，如采用SPOOLing技术实现的共享打印机

设备分配的安全性

安全分配方式

进程发出I/O请求后便进入阻塞态，直到I/O结束才被唤醒

优点：设备分配安全

缺点：CPU和I/O设备串行工作

不安全分配方式

进程发出I/O请求后继续执行，需要时发出第二个、第三个I/O请求

优点：进程推进迅速

缺点：可能产生死锁

逻辑设备名到物理设备名的映射

目的

提高设备分配的灵活性和利用率

实现I/O重定向

引入设备独立性

实现方法：引入逻辑设备表（LUT），用来将逻辑设备名映射为物理设备名

建立方式

整个系统设置一张LUT，所有设备分配情况都记录在这张表上（单用户设备）

每个用户建立一张LUT，分别记录设备的分配情况

SPOOLing技术（假脱机技术）

目的

缓解CPU与I/O处理器的速度差异矛盾

要实现SPOOLing技术，必须要有多道程序技术的支持

输入井和输出井

输入井用来收容I/O设备的数据

输出井用来模拟输出时的磁盘

输入缓冲区和输出缓冲区

输入缓冲区：暂存由输入设备送来的数据

输出缓冲区：暂存从输出井送来的设备

输入进程和输出进程

输入进程：模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区送到输入井中，当CPU需要数据，直接将输出井中的数据送入内存

输出进程：模拟脱机输出时的外围控制机，把用户要求输出的数据先从内存送到输出井中，待输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备

特点

提高了I/O速度

独占设备变成了共享设备

实现了虚拟设备功能

通俗一点就是，如果设备被占用，我们就先把数据暂存一下，等到设备空闲了就把这些数据输送到设备中

高速缓存与缓冲区对比

相同点

都介于高速设备和低速设备之间

不同点

存放数据

高速缓存：存放的是低速设备上的某些数据的复制数据

缓冲区：存放的是低速设备传递给高速设备的数据，这些数据在低速设备上不一定有备份，这些数据再从缓冲区传到高速设备

目的

高速缓存：高速缓存存放的是高速设备经常要访问的数据，如高速缓存中数据不在，高速设备就要访问低速设备

高速设备和低速设备的通信都要经过缓冲区，高速设备永远不会去直接访问低速设备

第四章文件管理

文件系统基础

文件的相关概念