第二章 进程与线程

2.1线程的属性

①线程是处理机调动的单位。

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

③每个线程都有一个线程ID，线程控制块(TCB)

④线程也有就绪，阻塞运行三种基本状态

⑤线程几乎不拥有任何系统资源

⑥同一进程的不同线程间共享进程的资源。

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

⑧同一进程中的线程切换不会引起进程切换

⑨与⑧相反

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

⑪切换进程，系统开销很小。

2.2调度

三种调度的联系对比

调度方法 细节描述 数据流动方向 发生频率 状态转换
高级调度（作业调度） 按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程 外存->内存（面向作业） 发生频率最低 不存在->创建态->就绪态
中级调度（内存调度） 按照某种规则，从挂起队列中选择合适的进程将数据调回内存。 外存->内存（面向进程） 中等 挂起态->就绪态（阻塞挂起）->阻塞态
低级调度（进程调度） 按照某种规则从就绪队列中选择一个进程为其分配处理机 内存->CPU 最高 就绪态->运行态

需要进行切换的调度与切换状况

当前运行的进程主动放弃处理机 ①进程正常终止②运行过程中出现异常而终止③进程主动请求阻塞
当前运行的进程被动放弃处理机 ①分给进程的时间片用光②有更紧急的是需要处理（如优先级调度剥夺形式的短作业（进程）优先调度或者I/O中断)③有更高优先级的进程进入就绪队列

小知识点

进程在操作系统内核程序临界区中不能进行地调度与切换

临界资源：一个时间段内只允许一个进程使用的资源，各进程需要互斥的访问临界资源

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

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的PCB组成）

如果还没有退出临界区（还没解锁）就进行进程调度，但是进程调度相关的程序也需要访问就绪队列，但此时就绪队列被锁住了，因此又无法顺利地进行进程调度

内核程序临界区访问的临界资源如果不尽快释放的话，极有可能影响到操作系统内核的其他管理操作。因此访问内核程序临界区期间不能进行调度与切换。

在打印机打印完成之前，进程一直处于临界区内，临界资源不会解锁。但打印机又是慢速设备，此时如果一直不允许进程调度的话就会导致CPU一直空闲

普通临界区访问的临界资源不会直接影响操作系统内核的管理操作。因此在访问普通临界区时可以进行调度与切换。

2.2.1 习题

为什么说多级反馈队列调度算法能较好地满足各类用户的需要？

多级反馈队列调度算法能够较好的满足各种类型用户的需要。对终端型作业用户而言，由于他们所提交的作业大多属于交互性作业，作业通常比较短小，系统只要能使这类作业在第一梯队队列对规定的时间片内完成，便可使终端型作业用户得到满意：对于短批处理作业用户而言，他们与终端型作业用户一样，只要能在对应的给定的时间片内完成，便可获得与终端作业用户一样的响应时间。对于稍长的作业，通常也只需要在第二个队列与第三级队列中各运行一个时间片即可完成，其周转时间依旧较短。对于长批处理作业用户而言，他们的长作业将一次在1-n级队列完成，然后按照时间片轮转的方式运行，用户不必担心作业长期得不到处理。

2.3同步与互斥

2.3.1同步互斥

进程同步：并发性带来了异步性，有时需要通过进程同步解决这种异步问题。有的进程之间需要相互配合的完成工作，各进程之间的工作推进需要遵循一定的先后顺序。

进程互斥：对进程临界资源的访问，需要互斥的进行，即同一时间段内只允许一个进程访问该资源。

四个部分：

进入区：检查是否可进入临界区，若可进入则需“上锁”

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

退出区：负责解锁

剩余区：其余代码部分

需要遵循的原则：

空闲让进：临界区空闲时，应允许一个进程访问。

忙则等待：临界区正在被访问时，其他试图访问的进程需要等待

有限等待：要在有效时间内进入临界区，保证不会饥饿

让权等待：进不了临界区的进程，要释放处理机，防止忙等

2.3.1.1进程互斥的软件实现方法

单标志法：

在进入区只做“检查”，不上锁，在退出区把临界区的使用权转交给另一个进程（相当于在退出区既给另一进程解锁）

主要问题：不遵循空闲让进的原则。

该算法可以实现每次只允许一个进程进入临界区，但两个进程必须交替进入临界区，若某个进程在某一时刻不在进入临界区，则另一个进程也无法进入临界区（不遵循空闲让进的原则）这样很容易造成资源利用不充分。

通俗解释：若P0顺利进入临界区并从临界区离开，则此时临界区是空闲的，但P1并没有进入临界区的打算，而turn=1一直成立，则P0就无法再次进入临界区。

双标志先检查法：

在进入区先“检查”后“上锁”，退出区“解锁”（检查对方的标志，设置自己的标志）

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

主要问题：不遵循“忙则等待”原则。

缺点：P0和P1可能同时进入临界区。即检查对方标志后和设置自己的标志前可能发生进程切换，结果双方都被检查通过，会同时即进入临界区（不遵循“忙则等待”原则）原因是在于检查对方标志和设置自己标志两个过程不能一气呵成。

通俗解释：在进入临界区之后有可能在被上锁之前就会另一个进程可以避过另一个进程进入临界区的锁，直接两个进程全部使用临界资源。

双标志后检查法：

再进区先“加锁”后检查，退出区“解锁”

主要问题：不遵循“空闲让进，有限等待”原则，可能导致饥饿

即两个进程依次设置自己的标志，并依次检查对方的标志，发现对方也想进入临界区，双方都争着进入临界区，结果谁都进不了（违背“空闲让进”原则）于是各进程都长期无法访问临界区而导致“饥饿现象”（违背有限等待原则）

通俗解释：

你等我不想进去，我等你不想进去，最后谁都想去，谁也进不去

peterson算法：

在进入区“主动争取，主动谦让，检查对方是否想进，己方是否谦让”

主要问题：不遵循“让权等待”原则，会发生忙等

一般是最后一个表示意愿的就是最终两个人合作的意愿。

2.3.1.2进程互斥的硬件实现方法

中断屏蔽方法

使用“开关中断”指令实现

优点：简单高效

缺点：只适用于单处理机；只适用于操作系统内核进程。

这种方法的缺点：

①限制了CPU交替执行程序的能力，因此系统效率会明显降低

②对内核来说，在它执行更新变量的几条指令期间，关中断时很方便的，但将关中断权限交给用户则很不明智，若一个进程关中断后不再开中断，则系统可能会因此终止。

③不适用于多处理器系统，因为在一个CPU上关中断并不能防止进程在其他的CPU上执行相同的临界区代码。

Test and Set(TS/TSL指令)

old记录是否已经被上锁；

再将lock设为true；

检查临界区是否已经被上锁

（若已上锁，则循环重复前几步）

优点：实现简单，适用于多处理器环境

缺点：不满足“让权等待”

Swap指令（XCHG指令）

逻辑上和上面的指令一样。

信号量机制

整型信号量：用一个整数型变量作为信号量，数值表示某种资源数，整型信号量与普通整型变量区别：对信号量只能执行初始化,p,v,两种操作。

整型信号量的问题：不满足让权等待原则。

记录型信号量：S.value表示某种资源数，S.L指向等待该资源的队列,

P操作中一定是先S.value–,之后可能需要执行block原语。

V操作中一定是先S.value++,之后可能需要执行wake up原语。

注意要能够自己腿短在什么条件下需要执行block或wake up

可以用记录型信号量实现系统资源的“申请”和“释放”

可以用记录型信号量实现进程互斥，进程同步。

信号量机制实现进程同步互斥和前驱关系

2.3.1.3进程互斥同步的基本问题

实现进程互斥

分析问题：确定临界区

设置互斥信号量：初值为1

临界区之前对信号量执行P操作

临界区之后对信号量执行V操作

实现进程同步

分析问题：找出哪里需要实现“一前一后”的同步关系

设置同步信号量，初始值为0；

在“前操作”之后执行V操作

在“后操作”之前执行P操作

实现进程的前驱关系

分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题

为每对前驱关系设置同步信号量，初值为0

在“前操作”之后执行V操作

在“后操作”之前执行P操作

本质是多级同步问题。

除了互斥，同步关系之外，还会考察有多个资源的问题，有多少资源就把信号量初值设为多少。申请资源时进行P操作，释放资源时进行V操作即可

2.3.2常见的几个经典互斥同步问题

PV操作题目的解题思路

1.关系分析。找出题目中描述的各个进程，分析他们之间的同步、互斥关系

2.整理思路。根据各进程的操作流程确定PV操作的大致顺序

3.设置信号量：设置需要的信号量，并根据题目条件确定信号量初值。（互斥）信号量初值一般为1，同步信号量的初值要看对应资源的初始值是多少。

2.3.2.1生产者消费者问题

生产者消费者问题是一个互斥、同步的综合问题

对于初学者来说最难的是发现题目中隐含的两对同步关系

有时候是消费者需要等待生产者生产，有时候是生产者要等待消费者消费，这是两个不同的“一前一后”问题，因此需要设置两个同步信号量。

image-20240921174455888

易错点：实现互斥和实现同步的两个P操作的前后顺序（死锁问题）

自己理解：生产者只有满足缓冲区条件则可以开始生产，如果开始加锁之后在进行生产，又发现无法生产，而消费者也先检查互斥关系的锁导致消费者也没有办法进行消费，这样就既不能生产，也不能消费，死锁形成、

2.3.2.2多生产者—多消费者问题

解决”多生产者—多消费者问题”的关键在于理清复杂的同步关系

在分析同步问题（一前一后）问题的时候不能从单个进程行为的角度来分析要把“一前一后”发生的事看做是两种“事件”的先后关系

比如，如果从单个进程行为的角度来考虑的话，我们会有以下结论：

如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才可以放入水果

如果盘子里装有橘子，那么一定要女儿取走橘子后父亲或母亲才可以放入水果

这么看是否就意味着要设置四个同步信号量分别实现这四个“一前一后”的关系？

正确的分析方法应该是从“事件”的角度来考虑我们可以把上述四对“进程行为的前后关系”抽象为一对“时间的先后关系”

盘子变空事件–>放入水果事件“盘子变空事件即可以由儿子引发，也可以由女儿引发

“放水果事件”既可能是父亲执行，也可能是母亲执行，这样的话，就可以用一个同步信号量解决问题了

2.3.2.3吸烟者问题

吸烟者问题可以为我们解决“可以生产多个商品的单生产者”问题提供一个思路

值得吸取的精华是：“轮流让各个吸烟者吸烟”必然需要轮流的在桌子上放上组合1,2,3.注意体会我们是如何用一个整型变量；实现这个“轮流”过程的，若一个生产者要生产多种产品（或者说会引发多种前驱事件）那么各个V操作应该放在格子对应的“事件”发生之后的位置。

2.3.2.4读者写者问题

读者–写者问题为我们解决复杂的互斥问题提供了一个参考思路

其核心思想在于设置一个计数器count用来记录当前正在访问共享文件的读进程数。我们可以用count的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理

另外，对count的检查和赋值不能一气呵成导致了一个错误，如果需要实现“一气呵成”，必须要使用互斥信号量。最后，还要认真体会我们是如何解决“写进程饥饿”问题。绝大多数的考研PV操作大题都可以用之前介绍的几种生产者-消费者问题的思想来解决，如果遇到更复杂的问题，可以想想能否用读者写者问题的这几个思想来解决。

2.3.2.5哲学家进餐问题

哲学家进餐问题的关键在于解决进程死锁。

这些进程之间仅存在互斥关系，但是与之前接触到的互斥关系不同的是，每个

进程都需要同时执有两个临界资源，因此就有了“死锁”的问题的隐患。

如果考试中遇到了一个进程需要同时执有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁，可以参考哲学家问题解决死锁的三种思路

①五个哲学家只允许四个哲学家拿筷子，第五个哲学家拿筷子时会被阻塞，等禁食的某个哲学家结束进食放下筷子，第五个哲学家才可以不去思考去拿起筷子。

②使相邻的奇偶编号哲学家不去同时抢左侧或同时取右侧的一个筷子而造成死锁，只有（会造成无死锁的情况）

③当一名哲学家左右两边的筷子都可用时，才允许他抓取筷子，抓筷子的过程中不允许中断，两边筷子全要抓起来。

2.3.4管程

2.3.4.1为什么要引入管程？

解决信号量机制编程麻烦，易出错的问题。

2.3.4.2组成

共享数据结构，对数据结构初始化的语句，一组用来访问数据结构的过程（函数）

2.3.4.3基本特征

各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据。

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

2.3.4.4补充

各进程必须互斥访问管程的特性是由编译器实现的可在管程中设置条件变量及等待/唤醒操作以解决同步问题。

2.3.4.5拓展1 用管程解决生产者消费者问题

引入管程的目的无非就是要更方便地实现进程的互斥和同步

1.需要在管程中定义共享数据（如生产者消费者问题的缓冲区）

2.需要在管程中定义用于访问这些共享数据的“入口”–其实是就是一些函数（如生产者，消费者），问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数从缓冲区取出产品

3.只有通过这些特定的“入口”才能访问共享数据

4.管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或“线程进入（如生产者，消费者问题中，各进程需要互斥地访问共享缓冲区，管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意：这种互斥特性是由编译器负责实现的。

5.可在管程中设置条件变量及等待/唤醒操作以解决同步问题，可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出入口），可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

程序员可以用某种特殊的语法定义一个管程（比如monitor .producer,consumer,end monitor)之后其他程序员就可以使用这个管程提供的特定“入口”很方便地使用实现进程同步互斥了（封装思想）

2.4死锁

2.4.1什么是死锁？

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

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

死锁：至少是两个进程一起死锁，死锁进程处于阻塞态。

饥饿：可以只有一个进程饥饿，饥饿进程可能阻塞也可以是就绪态

死循环：可能有一个进程陷入死循环，死循环的进程可以上处理机

死锁和饥饿是操作系统要解决的问题，死循环是应用程序员来解决的

2.4.3死锁产生的必要条件

互斥条件：对必须互斥使用的资源的争抢才会导致思索

不剥夺条件：进程保持的资源只能主动释放，不可强行剥夺

请求和保持条件：保持着某些资源不放的同时，请求别的资源

循环等待条件：存在一种进程资源的循环等待链，循环等待未必死锁，死锁必然循环等待

2.4.4什么时候会发生死锁

对不可剥夺资源的不合理分配，可能导致死锁

2.4.5死锁的处理策略

预防死锁（破坏死锁产生的四个必要条件）

避免死锁（避免系统进入不安全状态）

死锁的检测和解除（允许死锁发生，系统负责检测出死锁后解除）

预防死锁

2.4.5.1预防死锁

破坏互斥条件

将临界资源改造为可共享的资源（如SPOOLing技术）

缺点：可行性不高，很多时候无法破坏互斥条件

破坏不剥夺条件

方案一：申请的资源得不到满足时，立即释放所拥有的全部资源

方案二：申请的资源被其他进程占用时，由操作系统协助剥夺资源（考虑优先级）

缺点：实现复杂；剥夺资源可能导致部分工作失效；反复申请和释放资源会导致系统开销大，可能导致饥饿

破坏请求和保持条件

运行前分配好所有需要的资源，之后一直保持。

缺点：资源利用率低；可能导致饥饿

破坏循环等待条件

给资源编号，必须按照编号从小到大的顺序申请资源

缺点；不方便添加新设备，会导致资源浪费用户编程困难。

2.4.5.2避免死锁

银行家算法

数据结构：

长度为m的一维数组Available表示还有多少可有资源

n*m矩阵Max代表各进程对资源的最大需求数

n*m矩阵Allocation表示已经给各进程分配了多少资源

Max-Allocation=Need矩阵表示各进程最多还需要多少资源

用长度为N的一位数组request表示进程此次申请的各种资源数。

银行家算法步骤

①检查此次申请是否超过了之前声明的最大需求数。

②检测此时系统剩余的可用资源是否还能满足这次请求。

③试探着分配，更改数据结构

④用安全性算法检查此次分配是否会导致系统进入不安全状态

安全型算法步骤：

检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程持有的资源全部回收

不断重复上述过程，看最终是否能让所有进程都加入安全序列

系统处于不安全状态未必死锁，但死锁时一定处于不安全状态，系统处于安全 状态一定不会产生死锁。

2.4.5.3死锁的检测和解除

如何检测：

数据结构（资源分配图）

两种节点：进程节点，资源节点

两种边：进程节点->资源节点（请求边），资源节点->进程节点（分配边）

死锁检测算法：依次消除与不阻塞进程相连的边，知道无边可消

注：所谓不阻塞进程是指其申请的资源数不足够进程

死锁定理：若资源分配图是不可完全简化的，说明发生了死锁（题中会给出资源分配图）

不过也要小心与数据及结构结合考察

如何解除死锁：

资源剥夺法，撤销进程法（终止进程法）进程回退法

第三章 内存管理

3.1内存管理

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

内存的基础知识

什么是内存，有何作用？

存储单元，内存地址的概念和联系。

按字节编址vs按字编址

指令的工作原理 操作码+若干参数（可能包含地址参数）

逻辑地址（相对地址）vs物理地址（绝对地址）

从写程序到程序运行

编译源代码文件

编译：由源代码文件生成目标模块（高级语言“翻译”为机器语言）

链接：由目标模块生成装入模块，链接后形成完整的逻辑地址

装入：将装入模块装入内存，装入后形成物理地址

三种链接方式

静态链接：装入前连接成一个完整装入模块

装入时动态链接：运行前边链接边装入

运行时动态链接：运行时需要目标模块才装入并链接

三种装入方式

绝对装入：编译时产生绝对地址

可重定位装入：装入时将编辑地址转换为物理地址

动态运行时装入：运行时将逻辑地址转换成物理地址，需重新设置重定位寄存器。。

内存管理的概念

内存空间的分配与回收

内存空间的扩充（实现虚拟性）

地址转换

操作系统负责实现逻辑地址到物理地址的转换

三种方式：

绝对装入：编译器负责地址转换（单道程序阶段，无操作系统）

可重定位装入：装入程序负责地址转换（早期多道批处理阶段）

动态运行时装入：运行时才进行地址转换（现代操作系统)

存储保护

保证各进程在自己的内存空间的运行，不会越界访问

两种方式：设置上下限寄存器

利用重定位寄存器（基址寄存器），界地址寄存器（限长寄存器）进行判断

进程的内存映像

微信图片_20240928173202

覆盖与交换

一个固定区：存放最活跃的程序段，固定区中的程序段在运行过程中不会调入调出

若干覆盖区：不可能同时被访问程序段可共享一个覆盖区，覆盖区中的程序段在运行过程中会根据需要调入调出

必须由程序员声明覆盖结构，操作系统完成自动覆盖

缺点：对用户不透明，增加了用户编程负担

交换技术

内存紧张时，换出某些进程以腾出内存空间，再换入某些进程

磁盘分为文件区和对换区换出的进程放在对换区

覆盖与交换的区别

覆盖是在同一个程序或进程中的

交换是在不同进程或作业之间的。

3.1.2连续分配管理方式

单一连续分配

只支持单道程序，内存分为系统区和用户区，用户程序放在用户区，（无外部碎片，有内部碎片）

固定分区分配

支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装一道作业（无外部碎片，有内部碎片）

两种分区方式分区大小相等，分区大小不等。

动态分区分配

支持多道程序，在进程装入内存时，根据进程大小动态地建立分区

（无内部碎片，有外部碎片）

外部碎片可用“紧凑”技术来解决

回收内存分区时，可能遇到四种情况（总之相邻的空闲分区要合并）

  1. 回收区之后有相邻的空闲分区
  2. 回收区前、后都有相邻的空闲分区
  3. 回收区之前有相邻的空闲分区
  4. 回收区前后没有相邻的空闲分区

动态适应算法

算法 算法思想 分区排列顺序 优点 缺点
首次适应算法 从头到尾找合适的分区 空闲分区以地址递增的次序排列 综合看性能最好，算法开销小，回收分区一般不需要对空闲分区队列进行重新排序 无明显缺点
最佳适应算法 优先使用更小的分区，以保留更多的大分区 空闲分区按容量递增的次序排列 会有更多的大分区被保留下来，更能满足大进程需求 会产生很多太小的难以利用的碎片；算法开销大，回收分区后可能需要对空闲分区对队列进行重新排序
最坏适应算法 优先使用更大的分区，以防止太小的不可用的碎片 空闲分区按容量递减的次序排列 可以减少难以利用的小碎片 大分区进程容易被用完，不利于大进程；算法开销大（原因同上）
邻近适应算法 由首次适应算法演变而来，每次从上次查找结束位置开始查找 空闲分区以地址递增的次序排列 不用每次都从低地址的小分区开始检索。算法开销小（原因同首次适应算法） 会使高地址的大分区也被用完

3.1.3基本分页存储管理

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

基本分页存储管理的思想：把进程分页，各个页面可离散地放到各个内存块中。

易混概念：“页框，页帧，内存块，物理块，物理页”VS“页，页面”

​ “页框号，页帧号，内存块号，物理块号，物理页号”vs“页号，页面号”

页表：页表记录了页面和实际存放的内存块之间的映射关系

一个进程对应一张页表，进程的每一页对应一个页表项，每个页表项由“页号”和“块号”组成

每个页表项的大小是相同的，页号是“隐含的”
$$
i号页表项存放地址=页表始址+i*页表项大小
$$
逻辑地址结构（可拆分为页号P页内偏移量w）
$$
页号=逻辑地址/页面大小
$$

$$
页内偏移量=逻辑地址mod页面大小
$$
如果页面大小刚好是2的整数次幂呢！

这样就可以根据二进制原理对应前多少位为页号，后多少位为页内偏移量。

如何实现地址转换

  1. 计算出逻辑地址对应的【页号，页内偏移量】
  2. 找到对应页面在内存中的存放位置（查页表）
  3. 找到物理地址=页面始址+页内偏移量

基本地址变换机构

页面寄存器的作用：
存放页表起始地址，存放页表长度
地址变换过程：
  1. 根据逻辑地址算出页号、页内偏移量
  2. 页号的合法性检查（与页表长度对比）
  3. 若页号合法，再根据页表起始地址、页号找到对应页表项。
  4. 根据页表项中记录的内存块号，页内偏移量得到最终的物理地址
  5. 访问物理内存对应的内存单元
其他小细节

页内偏移量位数与页面大小之间的关系（要能用其中一个条件推出另一个条件）

页式管理地址是一维的

实际应用中，通常使一个页框恰好能放入整个页表项

为了方便找到页表项，页表一般是放在连续的内存块中

具有快表的地址变换机构

  1. 算页号，页内偏移量
  2. 检查页号合法性
  3. 查快表。若命中，即可知道页面存放的内存块号，可直接进行5操作；若未命中则进行4
  4. 查页表，找到页面存放的内存块号并且将页表项复制到快表中
  5. 根据内存块号与页面的偏移量得到物理地址
  6. 访问目标内存单元

TLB与普通Cache的区别：

TLB只有页表项的副本，而普通Cache可能有各种数据副本。

两级页表

单级页表存在的问题：

所有页表项必须连续存放，页表过大时需要很大的连续空间

在一段时间内并非连续的所有页面都用得到，因此没有必要让整个页表常驻内存

两级页表

将长长的页表再分页。
$$
逻辑地址结构：（一级页号、二级页号、页内偏移量）
$$
注意几个术语:页目录表/外层页表/顶级页表

要能根据逻辑地址位数，页面大小，页表项大小，可以通过一个页表能容纳多少个页表项确定一级页表的位数。确定多级页表的逻辑地址结构。

如何实现地址变换

  1. 按照地址结构将逻辑地址拆分成三部分
  2. 从PCB中读出页目录表始址，根据一级页表查页目录表，找到下一级页表在内存中存放的位置
  3. 根据二级页号查表，找到最终想要访问的内存块号
  4. 结合页内偏移量得到物理地址

几个细节

多级页表中各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级

多级页表的访存次数（假设没有快表机构）–N级页表访问一个逻辑地址需要N+1次访存。

3.1.4基本分段存储管理

分段：

将地址空间按照程序自身的逻辑关系划分为若干个段，每段从0开始编址

每个段在内存中占据连续空间，但各段之间可以不相邻

逻辑地址结构：（段号，段内地址）

段表：

记录逻辑段到实际存储地址的映射关系

每个段对应一个段表项各段表项长度相同，由段号（隐含），段长，基址组成

地址变换：

  1. 由逻辑地址得到段号，段内地址
  2. 段号与段表寄存器中的段长度比较，检查是否越界
  3. 由段表始址，段号找到对应段表项
  4. 根据段表中记录的段长，检查段内地址是否越界
  5. 由段表中的“基址+段内地址”得到最终的物理地址
  6. 访问目标单元

分段vs分页

  1. 分页的页面长度相同，分段的页面长度不同
  2. 分页对于用户不可见，分段对于用户可见
  3. 分页的地址是一维的，分段的地址是二维的
  4. 分段更容易实现信息的共享和保护（纯代码，可重入代码，可共享）
  5. 分页（单级页表），分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构

3.1.5段页式管理

分段+分页

将地址空间按照程序的自身逻辑关系划分为若干段，再将各段分为大小相等的页面

将内存空间分为与页面相等的一个个内存块，系统以块为单位为进程分配内存
$$
逻辑地址=（段号，页号，页内偏移量）
$$
段表，页表

每个段对应一个段表项，各段表项长度相同，由段号（隐含）页表长度，页表存放地址组成

各个页对应一个页表项，各页表项长度相同，由页号（隐含）页面存放那个的内存块号组成

地址变换

  1. 由逻辑地址得到段号、页号、页内偏移量
  2. 段号与段表寄存器中的段长度比较，检查是否越界
  3. 由段表始址、段号找到对应段表项
  4. 根据段表中记录的页面长度，检查页号是否越界
  5. 由段表中的页表地址、页号得到查询页表，找到对应页表项
  6. 由页面存放的内存块号、页内偏移量得到最终的物理地址
  7. 访问目标单元

访问一个逻辑地址所需的访存次数

第一次：查段表，第二次：查页表，第三次：访问目标单元

可引入快表机构，以段号和页号为关键字查询快表，即可找到最终的目标页面，存放位置、引入快表后仅需要一次访存。

3.2虚拟内存

3.2.1虚拟内存的基本概念

3.2.1.1传统存储管理方式的特征（缺点）

一次性：作业数据必须一次全部调入内存

驻留性：作业数据在整个运行期间都会常驻内存

3.2.1.2局部性原理

时间局部性：现在访问的指令，数据在不久之后很可能会被再次访问。

空间局部性：现在访问的内存单元周围的内存单元，很可能在不久后会被访问。

高速缓存技术：使用频繁的数据放到更高速的存储器中。

3.2.1.3虚拟内存的定义和特征

定义：程序不需要全部装入即可运行，运行时根据需要动态调入数据。若内存不够，还需换出一些数据。

特征：

多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。

对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，讲作业换入换出。

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

3.2.1.4如何实现虚拟内存技术

访问的信息不在内存中，由操作系统负责将所需信息，从外存调入内存（请求调页功能）。

内存空间不够，将内存中暂时用不到的信息换出内存（页面置换功能）

虚拟内存的实现：

请求分页存储管理、请求分段存储管理、请求段页式存储管理。

3.2.2请求分页管理方式

页表机制：在基本分页的基础上增加了几个表项

状态位：标识页面是否已在内存中

访问字段：记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考。

修改位：表示页面调入内存后是否被修改过，只有修改过的页面才在需要置换时写入外存。

外存地址：页面在外存中存放的位置

缺页中断机构

找到页表项后检查页面是否已在内存，若没有在内存中，则产生缺页中断

缺页中断处理中，需要将目标页面调入内存，有必要时还要换出页面，缺页中断属于内中断，属于内中断中的“故障”，即可能被系统修复的异常，一条指令在执行过程中可能产生多次缺页中断

地址变换机构（重点关注与基本分页不同的地方）

找到页表项是需要检查页面是否在内存中。

若页面不在内存中，需要请求调页。

若内存空间不够，还需换出页面

页面调入内存中后，需要修改相应页表项

image-20241005105926343

3.2.3页框分配

**驻留集:**指的是请求分页存储管理中给进程分配的内存块的集合

页面分配置换策略：

固定分配VS可变分配：区别在于进程运行期间驻留集大小是否可变

局部置换VS全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出

固定分配局部置换：进程运行前就分配一定数量物理块，缺页时只能换出进程自己的某一页

可变分配全局置换：只要缺页就分配新物理块，可能来自空闲物理块，也可能需换出别的进程页面

**可变分配局部置换:**频繁缺页的进程，多分配一些物理块；缺页率很低的进程，回收一些物理块，直到缺页率合适

何时调入页面：

预调页策略：一般用于进程运行前

请求调页策略：进程运行时，发现缺页再调页

从何处调页：

对换区：采用连续存储方式，速度更快；文件区—采用离散存储方式，速度更慢

对换区足够大：运行将数据从文件区复制到对换区，之后所有的页面调入调出，都是在内存与对换区之前进行。

对换区不够大：不会修改的数据每次都从文件区调入；会修改的数据调出到对换区，需要时再从对换区调入。

Unix方式：第一次使用的页面都从文件区调入调出的页面都写会对换区，再次使用时从对换区调入。

抖动颠簸现象：页面频繁换入换出的现象。主要原因是分配给进程的物理块不够

工作集：在某段时间间隔里；进程实际访问页面的集合。驻留集大小一般不能小于工作集大小

3.2.4页面置换算法

算法 算法规则 优缺点
OPT 优先淘汰最长时间内不会被访问的页面 缺页率最小，性能最好但无法实现
FIFO 优先淘汰最先进入内存的页面 实现简单，但性能很差，可能出现贝拉迪异常
LRU 优先淘汰最近最久没访问的的页面 性能很好，但需要硬件支持，算法开销大
CLOCK(NRU) 循环扫描各页面，第一轮访问淘汰访问位=0的，并将扫描过的页面访问位改为1，若第一轮未选中，则进行第二轮扫描 实现简单，算法开销小。但未考虑页面是否被修改
改进型CLOCK(改进型NRU) 若用（访问位，修改位）的形式表述，第一轮淘汰（0,0），第二轮淘汰（0,1），并将扫描过的页面访问位都置为0，第三轮淘汰（1,0），第四轮淘汰（1,1）（优先级） 算法开销小，性能也不错

3.2.5内存映射文件

特性：进程可使用系统调用，请求操作系统将文件映射到进程的虚拟地址空间，以访问内存的方式读写文件。进程关闭文件时，操作系统负责将文件数据写回磁盘，以解除内存映射，多个进程可以映射同一个文件，方便共享。

优点：程序员编程更简单，已建立映射的文件，只需访问内存的方式读写即可。文件数据的读入写出完全由操作系统负责优化。

第四章 文件

4.1文件系统基础

①文件管理

文件的定义：一组有意义的信息的集合。

文件的属性：文件名，标识符，类型，位置，大小，保护信息

文件内部应该如何被组织起来（文件的逻辑结构）

文件之间该如何被组织起来（目录结构）

操作系统应向上提供哪些功能（create,delete,open,close,read,write系统调用）

文件应如何存放在外存中（文件的物理结构）

操作系统如何管理外存中的空闲块（存储空间的管理）

操作系统需要提供的其他文件管理功能（文件共享，文件保护）

②有结构文件

顺序文件

串结构：记录顺序与关键字无关。

顺序结构：记录按关键字顺序排列

可变长记录的顺序文件无法实现随机存取，定长记录可以。（可变长记录的顺序文件在每次查询时只能从头一次查找）

定长记录、顺序结构的顺序文件可以快速检索（根据关键字可快速找到记录）

最大缺点：不方便增加/删除记录。

索引文件

建立一张索引表，每个记录对应一个表项。各记录不用保持顺序，方便增加/删除记录。

索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录，因此索引文件可支持随机存取。

若索引表按关键字顺序排列，则可支持快速检索

解决了顺序文件不方便增删记录的问题，同时让不定长记录的文件实现了随机存取，但索引表可能占用很多空间。

索引顺序文件

将记录分组，每组对应一个索引表项

检索记录时先顺序查索引表，找到分组，再顺序查找分组（会 查 ，计算平均查找次数）

当记录过多时，可建立多级索引表。

③文件的基本操作

创建文件：分配外存空间，创建目录项

删除文件：回收外存空间，删除目录项

打开文件：

将目录项中的信息复制到内存中的打开文件表中，并将打开文件表的索引号返回给用户，打开文件后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作。

每个进程有自己的打开文件表，系统中也有一张总的打开文件表，进程打开文件表中特有的属性，读写指针，访问权限（只读？读写?)

系统打开文件表中特有的属性：打开计数器（有多少个进程打开了该文件）

**关闭文件:**将进程打开文件表中的相应表项删除，系统打开文件表的打开计数器减，若打开计数器为，则删除系统表的表项

读文件：根据读指针、读入数据量，内存位置将文件数据从外存读入内存

写文件：根据写指针，写出数据量，内存位置将文件数据从内存写出外存

“读写文件”用“文件描述符”即可，指明文件，不再需要用到“文件名”

打开文件时并不会把文件数据直接读入内存。“索引号”也称“文件描述符”

④文件的物理结构

连续分配（总结）

连续分配方式要求每个文件在磁盘上占有一组连续的块

优点：支持顺序访问和直接访问（即随机访问），连续分配的文件在顺序访问时速度最快

缺点：不方便文件拓展；存储空间利用率低，会产生磁盘碎片

链接分配（总结）

链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显示连接两种。

隐式链接—除文件的最后一个盘块之外，每个盘块中都存在指向下一个盘块的指针。文件目录包含文件第一块的指针和最后一块的指针

优点：很方便文件拓展，不会有碎片问题，外存利用率高

缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针，也需要耗费少量的存储空间

（考试题目中遇到未指明隐式/显式的“链接分配，默认指的是隐式链接的链接分配）

显式链接：把用于链接文件各物理块的指针显式的存放在一张表中，即文件分配表（FAT，File Allocation Table)一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。

优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。

缺点：文件分配表的需要占有一定的存储空间

​

索引分配（总结）

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块所对应的物理块（索引表的功能类似与内存管理中的页表–建立逻辑页面到物理页面的映射关系），索引表的存放的磁盘块称为索引块，文件数据存放的磁盘块称为数据块。

若文件太大、索引表项太多，可以采取以下三种方法解决：

①

链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块连接起来存放。

缺点：若文件很大，索引表很长，就需要将很多个索引块连接起来，想要找到i号索引块，必须献一次读入0-i-1号索引块，这就导致磁盘I/O次数过多，查找效率低下

②

多层索引：建立多层索引（原理类似于多级页表）是第一层索引块指向第二层的索引块。还可以根据文件大小的的要求在建立第三层，第四层索引块。采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作。缺点：即便是小文件，访问一个数据块依然需要K+1次读磁盘

③

混合索引：多次索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），有包含一级间接索引（指向单层索引表），还包含两级间接索引（指向两层索引表）

优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

超级超级超级重要考点：①要会根据多层索引，混合索引的结构计算出文件的最大长度（KEY：各级索引表最大不能超过一个块）②要能分析访问某个数据块所需要的读磁盘次数（KEY：FCB中会存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块，每次读入下一级的索引块都需要一次读磁盘操作，另外，要注意题目条件–顶级索引块是否已经调入内存）

顺序分配，链接分配与索引分配

分配方式 how? 目录项内容 优点 缺点
顺序分配 为文件分配的必须是连续的磁盘块 起始块号，文件长度 顺序存取速度快，支持随机访问 会产生碎片，不利于文件拓展
隐式链接 读文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针 起始块号，结束块号 可解决碎片问题，外存利用率高，文件拓展实现方便 只能顺序访问，不能随机访问
显式链接 建立一张文件分配表（FAT），显式记录盘块的先后关系（开机后FAT常驻内存） 起始块号 除了拥有隐式链接的优点之外，还可以通过查询内存中的FAT实现随机访问 FAT需要占用一定的存储空间
索引分配 为文件数据块建立索引表，若文件太大，可采用连接方案，多层索引，混合索引 连接方案记录的是第一个索引块的块号，多层混合索引记录的是顶级索引号的块号 支持随机访问，易于实现文件的拓展 索引表需要占用一定的存储空间访问数据块前需要读入索引块。若采用链接方案，查找索引块时需要很多次读磁盘操作

逻辑结构VS物理结构

逻辑结构：用户（文件创建者）的视角看到的样子，在用户看来，整个文件占有连续的逻辑地址空间文件内部的信息组织完全由用户自己决定，操作系统并不关心。

物理结构：由操作系统决定文件采用什么物理结构存储，操作系统负责将逻辑地址转变为（逻辑块号，块内偏移量）的形式，并负责实现逻辑块号到物理块号的映射。

4.2目录

4.2.1文件目录

文件目录的实现：

一个文件对应一个FCB，1个FCB就是一个目录项，多个FCB组成文件目录

对目录的操作：搜索，创建文件，删除文件，显示文件，修改文件

目录结构：

单级目录结构：一个系统只有一张目录表，不允许文件重名。

两级目录结构：不同用户的文件可以重名，但不能对文件进行分类

多级目录结构（树形）：

不同目录下的文件可以对文件进行分类，不方便文件共享

系统根据“文件路径”找到目标文件

从根目录出发的路径是“绝对路径”

从当前目录出发的路径是“相对路径”

无环图目录结构：

在树形目录结构的基础上，增加一些指向同一节点的有向性，使整个目录称为一个有向无环图

为共享节点设置一个共享计数器，计数器为0时才真正删除节点

索引节点：除了文件名之外的所有信息都放到索引节点中，每个文件对应一个索引节点，目录项中只包含文件名，索引节点指针，因此每个目录项的长度大幅减少，由于目录项长度减小，因此每个磁盘块可以存放更多个目录项，因此检索文件时的磁盘I/O的次数就少了很多。

4.2.2文件共享

硬链接：

各个用户的目录项指向同一个索引节点，索引节点中需要有链接计数count，某用户想删除文件时，只是删除该文件的目录项，且count–，只有count==0时才能真正删除文件数据和索引节点，否则会导致指针悬空

软链接：

在一个Link型的文件中记录共享文件的存放路径（windows快捷方式）操作系统根据路径一层层查找目录，最终找到共享文件。即使软链接指向的共享文件已被删除，link型文件依然存在，只是通过Link型文件中的路径会查找共享文件会失败（找不到对应目录项），由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O.

4.2.3文件保护

口令保护:

为文件设置一个“口令”，用户想要访问文件时需要提供口令，由系统验证口令是否正确，实现开销小，但“口令”一般存放在FCB或索引节点中（也就是存放在系统中）因此不太安全。

加密保护：

用一个“密码”对文件加密，用户想要访问文件时，需要提供相同的“密码”才能正确的解密。

安全性高，但加密/解密需要耗费一定的时间。

访问控制：

用一个访问控制表（ACL)记录各个用户（或各组用户）时文件的访问权限，对文件的访问类型可以分为读写执行删除等。实现灵活，可以实现复杂的文件保护功能。

如果对于某个记录进行了访问控制，那也要对目录下的所有文件进行相同的访问权限控制。

4.3文件层次结构

文件层次结构

  1. 用户需要通过操作系统提供的借口发出上述请求——用户接口。
  2. 由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项——文件目录结构
  3. 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限——存取控制模块（存取控制验证层）
  4. 验证用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址——逻辑文件系统与文件信息缓冲区
  5. 知道了目标记录对应的逻辑地址后，还需要转化成实际的物理地址——物理文件系统
  6. 要删除这条记录，必定要对磁盘设备发出请求——设备管理程序模块
  7. 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收——辅助分配模块

文件存储空间管理

存储空间的划分与初始化

文件卷（逻辑卷），目录区，文件区的概念

目录区包含文件目录，空闲区，位示图，超级块等用于文件管理的数据

空闲表法

空闲表中记录每个连续空闲区的起始盘块号，盘块数。

分配时可采用首次适用，最佳适应等策略；回收时注意表项的合并问题

空闲链表法

空闲盘块链：以盘块为单位组成一条空闲链。分配时从链头依次取出空闲块，回收时将空闲块查到链尾，以盘区为单位组成一条空闲链。

**空闲盘区链:**分配可采用首次适应，最佳适应等策略；回收时注意相邻空闲盘区合并的问题。

位示图法：

一个二进制位对应一个盘块（字号，位号）或（行号，列号）与盘块号一一对应，

重要考点：要能够自己推出盘块号——>（字号，位号）之间的相互转换公式。

需要注意的题目条件：二进制011到底哪个代表空闲，哪个代表不空闲，字号、位号、盘块号到底是从0开始，还是从1开始

成组链接法：UNIX采用的策略，适合大型文件系统，理解即可，不方便用文字描述的知识点也很难作为考题。

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

5.1 I/O管理概述

5.1.1I/O设备

什么是I/O设备？

将数据Input/Output(输入/输出)计算机的外部设备

按使用特性分类：

人机交互类外部设备，存储设备，网络通信设备

按传输速率分类：

低速设备，中速设备，高速设备

按信息交换的单位分类：

块设备（传输快，可寻址）

字符设备（传输慢，不可寻址）

I/O控制器

用于实现对I/O设备的控制，I/O设备由机械部件和电子部件组成。、

主要功能：

接受和识别CPU发出的命令（要有控制寄存器）

向CPU报告设备的状态（要有状态寄存器）

数据交换：要有数据寄存器，暂存输入和输出的数据

地址识别：（由I/O逻辑实现）

组成：

CPU与控制器之间的接口（实现控制器与CPU之间的通信）

I/O逻辑（负责识别CPU发出的命令，并向设备发出命令）

控制器与设备之间的接口（实现控制器与设备之间的通信）

两种寄存器编址方式：

内存映射I/O

控制器中的寄存器与内存统一编址，可以采用对内存进行操作的指令来对控制器进行操作

优点：

不需要专门的I/O指令，使得CPU访问I/O的操作更加灵活和方便，还使用端口具有较大的编址空间。I/O访问的保护机制可有虚拟存储管理系统来实现，无需专门设置。

缺点：

端口地址占用了部分主存地址空间，使主存的可用容量变小，此外，由于在识别I/O端口是全部地址线都要参加译码，使得译码电路更加复杂，降低了寻址速度。

寄存器独立编制：

控制器中的寄存器独立编制

需要设置专门的指令来操作控制器。

优点：

I/O端口数比主存单元少得多，只需要少量的地址线，使得I/O端口译码简单，寻址速度更快，使用专用的I/O指令，可使程序更加清晰，便于理解和检查。

缺点：

I/O指令少，只提供简单的传输操作，所以程序设计的灵活性较差，此外，CPU需要提供两组独立的存储器和设备的读写控制信号，增加了控制的复杂性。

5.1.2I/O控制方式

方式 完成读写的过程 CPU干预频率 每次I/O数据传输单位 数据流向
程序直接控制方式 CPU发出I/O命令后需要不断轮询 极高 字 设备–》CPU–》内存，内存–》CPU–》设备
中断驱动方式 CPU发出I/O命令后可以做其他事，本次I/O完成后设备控制器发出中断信号 高 字 设备–》CPU–》内存，内存–》CPU–》设备
DMA方式 CPU发出I/O命令后可以做其他事，本次I/O完成后DMA控制器发出中断信号 中 块 设备–》内存，内存–》设备
通道控制方式 CPU发出I/O命令后可以做其他事，通道会执行通道程序以完成I/O，完成后通道向CPU发出中断信号 低 一组块 设备–》内存，内存–》设备 
1
2
优缺点：
每个阶段的优点都是解决了上一阶段的最大缺点；总体来说：整个发展过程就是要减少CPU对I/O过程的干预，把CPU从繁杂的I/O控制事务中解脱出来，以便更多的去完成数据处理任务。

5.1.3I/O软件层次结构

I/O软件层次

用户层软件

实现与用户交互的接口，向上提供方便易用的库函数

设备独立性软件

①向上层提供统一的调用接口（如read/write系统调用）

②设备的保护

③差错处理

④设备的分配与回收

⑤数据存储区管理

⑥建立逻辑设备名到物理设备名的映射关系；根据设备类型选择调用相应的驱动程序

设备驱动程序

设置设备寄存器，检查设备状态

中断处理程序

进行中断处理

硬件

执行I/O操作，有机械部件，电子部件组成（参考I/O控制器）

理解并记住I/O软件各个层次之间的次序，要能够推理判断某个处理应该是在哪个层次完成的（最常考的是设备独立型软件，设备驱动程序这两层。只需理解一个特点即可。直接涉及到硬件具体细节，且与中断无关的操作肯定是在设备驱动程序层完成的，没有涉及硬件的，对各种设备都需要进行的管理工作都是在设备独立性软件层完成的）

5.1.4应用程序I/O接口

I/O接口的分类

字符设备接口，快设备接口，网络设备接口。

阻塞I/O

阻塞I/O是指当用户进程调用I/O操作时，进程就被阻塞，并移到阻塞队列，I/O操作完成后进程才被唤醒，移到就绪队列

例如：****你和女友去奶茶店买奶茶，点完单之后，因为不知道奶茶什么时候做好，所以只能一直等待，其他什么事也不能干。

优点：操作简单，实现难度低，适合并发量小的应用开发

缺点：I/O执行阶段进程会一直阻塞下去。

非阻塞I/O：

非阻塞I/O是指当前用户进程调用I/O操作时，不阻塞该进程但进程需要不断询问I/O操作是否完成，在I/O执行阶段，进程还可以做其他事情。

例如：你和女友去奶茶店买奶茶，汲取了上次的教训，点完单口顺便去逛逛商场，由于担心错过取餐，所以每隔一段时间就过来询问服务员

优点；进程在等待I/O期间不会阻塞，可以做其他事情，适合并发量大的应用开发

缺点：轮询方式询问I/O结果，会占用CPU的时间

5.2设备独立性软件

假脱机技术

SPOOLING

脱机技术：外围控制机+更高速的涉笔——磁带

作用：缓解设备与CPU的速度矛盾实现预输入，缓输出

假脱机技术：

又叫SPooling技术，用软件的方式模拟脱机技术

输入井和输出井：模拟脱机输入输出时的磁带

输入进程和输出进程：模拟脱机输入输出的外围控制机

输入缓冲区和输出缓冲区：内存中的缓冲区，输入输出时的“中转站”

共享打印机：

用假脱机技术将独占式的打印机“虚拟”成共享打印。

设备的分配与回收

应考虑的因素

固有属性：独占设备，共享设备，虚拟设备

分配算法：先来先服务，优先级高者优先，短任务优先

安全性：安全分配方式、不安全分配方式（死锁避免，银行家算法）

静态分配与动态分配：

静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源

动态分配：进程运行过程中动态申请设备资源（动态）

设备分配管理中的数据结构

**设备控制表（DCT)**每个设备对应一个DCT，关键字段：类型/标识符/状态/指向COCT的指针/等待队列指针

**控制器控制表（COCT)**每个控制器对应一个COCT，关键字段：类型/标识符/状态/指向CHCT的指针/等待队列指针

**通道控制表（CHCT)**每个控制器对应一个CHCT，关键字段：类型/标识符/状态/等待队列指针

系统设备表（SDT）记录整个系统中所有设备的情况，每个设备对应一个表目，关键字段：设备类型/标识符/DCT/驱动程序入口

设备分配的步骤：

①根据进程请求的物理设备名查找SDT

②根据SDT找到DCT并分配设备

③根据DCT找到COCT并分配控制器

④根据COCT找到CHCT并分配通道

注：只有设备，控制器，通道，三者都分配成功时，这次设备分配才算成功之后便可启动I/O设备进行数据传送。

缺点：用户编程时必须使用“物理设备名”若换了一个物理设备，则程序无法运行。若进程请求的物理设备正在忙碌，即使系统中还有同类型的设备，进程必须阻塞等待。

设备分配步骤的改进：用户编程时使用逻辑设备名申请设备，操作系统负责实现从逻辑设备名到物理设备名的映射（通过LUT）

逻辑设备表的设置问题：

整个系统只有一张LUT；各个用户所用的逻辑设备名不允许重复

每个用户一张LUT，各个用户的逻辑设备名可重复

缓冲区管理

缓冲区的概念：

一般利用内存作为缓冲区，缓解CPU与设备的速度矛盾，减少对CPU的中断频率，解决数据粒度不匹配的问题，提高CPU与I/O设备之间的并行性

单缓冲：

设备-（T）-缓冲区-（M）工作区-(C)处理

处理一块数据平均耗时Max(C,T)+M

分析问题的初始状态：工作区满，缓冲区空

双缓冲：

处理一块数据平均耗时max(T,C+M)

分析问题的初始状态；工作区空，一个缓冲区满，另一个缓冲区空

循环缓冲：

多个缓冲区连接成循环队列，in指针指向第一个空缓冲区，out指针指向第一个满缓冲区

缓冲池：

三个队列：空缓冲队列，输入队列，输出队列

四种工作缓冲区：用于收容输入数据的工作缓冲区，用于提取输入数据的工作缓冲区

用于收容输出数据的工作缓冲区，用于提取输出数据的工作缓冲区

5.3磁盘和固态硬盘

5.3.1磁盘的结构

磁盘、磁道、扇区的概念

磁盘由表面涂有磁性物质的圆形盘片组成

每个盘片被划分为一个个磁道，每个磁道又划分为一个个扇区

如何在磁盘中读写数据

磁头移动到目标位置，盘片旋转，对应盘区划过磁道才能完成读写

盘面，柱面的概念：

磁盘有多个盘片“摞起来”，每个盘片有两个盘面

所有盘面中相对位置的磁道组成柱面

磁盘的物理地址：

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

5.3.2磁盘的分类

根据磁头是否可移动

固定头磁盘（每个磁道有一个磁头）

移动头磁盘（每个盘面只有一个磁头）

根据盘面是否可以更换

固定盘磁盘，可换盘磁盘

5.3.3磁盘的调度算法

一次磁盘读写操作需要的时间

寻道时间：移动磁臂，移动磁头所需要的的时间

延迟时间：将目标扇区转到磁头下面所花的时间

传输时间：读写数据花费的时间

磁盘调度算法：

先来先服务（FCFS） ①按访问请求到达的先后顺序进行处理
最短寻找时间优先（SSTF） 每次都优先响应距离磁头最近的磁道的访问请求，贪心算法的思想，能保证眼前最优，但无法保证总的寻道时间最短，缺点，可能导致饥饿
扫描算法（电梯算法，SCAN） 只有磁头移动到最边缘的磁道时才可以改变磁头方向，缺点：对各个位置磁道的响应频率不平均
循环扫描算法（C-SCAN） 只有需磁头朝某个方向移动时才会响应请求，移动到边缘后立即让磁头返回起点，返回途中不响应任何请求
LOOK算法 SCAN算法的改进，只要在磁头移动方向上不再有请求，就立即改变磁头方向
C-LOOK算法 C-SCAN算法的改进 ，只要在磁头移动方向上不在有请求，就立即让磁头返回序号最小的磁头

若题目中无特别说明，则SCAN就是Look，C-SCAN就是C-LOOK

5.3.4减少延迟时间的方法

交替编号：

具体做法：让编号相邻的扇区在物理上不相邻

原理：读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区

错位命名：

具体做法：让相邻的盘面的扇区编号“错位”

原理：与“交替编号”的原理相同。”错位命名法“可以降低延迟时间

磁盘地址结构的设计：

理解为什么要用（柱面号，盘区号，扇区号）的结构

理解为什么不用（盘区号，柱面号，扇区号）的结构

原因：在读取地址连续的磁盘块时，前者更不需要移动磁头

5.3.5磁盘的管理：

磁盘初始化：

低级格式化/物理格式化：划分扇区

磁盘分区（C盘，D盘，E盘）

逻辑格式化：建立文件系统（建立根目录文件，建立用于存储空间管理的数据结构）

引导块：

计算机启动时需要运行初始化程序（自举程序）未完成初始化

ROM存放很小的自举装入程序

完整的自举程序存放在初始化块（引导块）中

坏块的管理：

简单的磁盘：逻辑格式化时将坏块标记出来

复杂的磁盘：磁盘控制器维护一个坏块链，并管理备用扇区。

5.3.6固态硬盘SSD

原理：基于闪存技术Flash Memory,属于可擦除ROM，即EEPROM

组成：闪存翻译层-负责翻译逻辑块号，找到对应页（Page)