操作系统

补充

链式存储

顺序存储

多级索引顺序文件(其实就是多次分组)

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

只支持顺序访问，不支持随机访问，查找效率低，指向下一个指针也需要耗费内存空间

很方便文件扩展，不会有碎片问题，外存利用率高，并且<b>支持随机访问</b>。相比隐式连接来说，<b>地址装换不需要访问磁盘，因此文件的访问效率跟高</b>

以<b>盘块</b>为单位组成一条空闲链

分配时从链头依次取出空闲块，回收时将空闲块查到链尾

以<b>盘区</b>为单位组成一条空闲链

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

（字号，位号）→盘块号

盘块号→（字号，位号）

二进制0/1到底那个代表空闲，那个代表不空闲

字号、位号、盘块号到底从0开始还是从1开始

SCAN算法的改进，只有在磁头移动方向上不在有请求，就立即改变磁头方向，返回的过程会处理请求

C-SCAN的改进，只有在磁头移动方向上不在有请求，就立即改变磁头方向，移动到有请求的位置，返回的过程不会处理请求，会和C-SCAN类似，返回到了最前面有请求的磁道开始向后扫描

联机命令接口

脱机命令接口

区别: 联机(交互)命令：用户输入一个命令，操作系统执行一个. ----- 联机(批处理)命令：批量执行多个命令

即系统调用（部分教材说广义指令）：通过陷入指令(非特权指令，它是一种特殊的指令)让处理器进入内核态，让系统执行对应的指令，再变为用户态，这也是应用程序请求操作系统的唯一办法

例如导弹系统

例如12306

内中断：cpu执行指令时会检查是否有异常<br>

外中断：Cpu每执行完指令周期末尾，都会检查是否有中断指令需要处理<br>

通过‘’中断向量表“实现<br>

进程标识符PID

用户标识符UID

CPU、磁盘、网络流量使用情况统计.....

进程当前状态：就绪态/阻塞态/运行态.....

正在使用那些文件

正在使用那些内存区域

正在使用那些I/O设备

如PSW、PC等等寄存器的值（用于实现进程的切换）

子主题

子主题<br>

子主题

会导致用户程序一直运行在CPU上<br>

创建的原语<br>

引进进程创建的事件

撤消原语(就绪态/阻塞态/运行态→终止态→无)<br>

引进进程终止的事件

进程的阻塞

进程的唤醒

切换原语<br>

引起进程切换的事件<br>

消息会直接放入消息缓冲队列<br>

消息放入到消息信箱中，在通过发送/接受 原语获取<br>

管道只能是半双工的，也就是单一时间内只能单方向传送数据

管道是互斥的

数据以字符流的形式进入管道，到管道满了，写进程的Write()系统调用被阻塞，等待管道内的数据变空，当管道空了，读进程的Read()会阻塞<br>

如果没空 不允许写，若不满，不允许读

数据一旦被读出，就从管道被抛弃，为了防止数据被读错，所以读进程必须只有一个<br>

传统进程机制中、进程是资源分配、调度的基本单位

引入线程后，进程是资源分配(CPU外部)的基本单位，线程是调度的基本单位

传统进程机制中，只能进程间并发

引入线程后，各个线程间也能并发，提升了并发度

传统的进程间并发，需要切换进程的运行环境，系统开销很大

线程间并发，若果是同一进程内的线程切换，则不需要切换进程环境，系统开销小

引入线程后，并发所带来的的系统开销减小

例图

用户级线程的切换在用户空间即可完成，不用切换到核心态，线程管理开销小，效率高

当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高，多个线程不可以在多个处理机上并行运行

例图

当一个线程被阻塞的时候，别的线程可以继续运行，他们相互独立，可在多核处理器并行<br>

一个用户进程会占用多个内核级线程，线程切换有操作系统进入到内核态完成，管理成本高，开销大

优点

缺点

例图

优点<br>

缺点

例图

例图

补充：线程才是处理器分配到最小单位，一个核跑一个线程，如上图<br>

就绪挂起<br>

阻塞挂起<br>

进程正常终止

运行过程中发生异常而终止

进程主动请求阻塞（如：等待I/O完成）

分给进程的时间片用完

有更紧急的事情要处理 (I/O中断)

有更高优先级的进程进入就绪队列

一个时间段只允许一个进程使用的资源。各进程<b>互斥</b>地访问临界资源

临时访问临界区资源的那些代码

例如：进程进入到<b>内核程序临界区中访问就绪队列的</b>时候，操作系统会给就绪队列资源上锁（<b>保证互斥性，只有当前的交互进程可以访问</b>） ，这个时候是不可以进行进程调度，因为你的进程还<b>内核程序临界区</b>内，就绪队列还在上锁，所以<b>这个访问内核程序临界区的过程很快完成</b>否则极有可能影响到操作雄的其他管理工作，也因此表明了，<b>访问内核程序临界区期间不可以进行调度和切换</b><br>

例如：进程访问打印机的时候，打印机会被上锁，由于打印机对于CPU来说是慢速设备，此时如果一直保持，则会让CCPU一直保持空闲状态，而且PCB状态序列也没有被锁住，所以我们可以进行进程调度和切换，当前进程进入阻塞状态，让其他进程和我们并发运行。所以这表明<b> 访问不同临界区时，不会直接影响到系统内核的管理工作，因此可以进行进程的调度和切换</b><br>

公平，算法实现简单

排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即FCFS算法对<b>长作业有利，对短作业不利</b>

公平，算法实现简单

排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即FCFS算法对<b>长作业有利，对短作业不利</b>

非抢占式SJF

抢占式最短作业优先（SRTN）

综合考虑了等待时间和运时间(要求服务时间)，等待时间一样时，要求服务时间最短的优点(SLF的优点)，要求服务的时间一样时，等待时间长的优先(FCFS的优点)

公平，响应快，适用于分时操作系统

由于高频的进程切换，因此一定开销：不区分任务的紧急程度

用优先级区分紧急程度、重要程度，使用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度

若源源不断的有高优先级的进程到来，则可能导致饥饿

静态优先级

动态优先级

&nbsp;如何合理的设置各类进程的优先级

如果采用动态调整的优先级，应该在什么时候调整<br>

对各类型进程都相对公平点(FSFC)；对每个新到达的进程都可以很快的得到响应(RR的优点)；短进程只用较少的事件就可完成(SPF的优点)；不必实现估计进程的运行时间(避免用户作假)；可灵活的调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程(拓展：可以将因I/O阻塞的进程重新放原队列，这样I/O型进程就可以保持较高优先级了)

检查是否可进入临界区。若可进入，则应设置<b>正在访问临界资源标志</b>(可理解为“上锁”)，以阻止其他进程同时进入临界区<br>

访问临界资源的那段代码

负责解除<b>正在访问临界资源的标志</b>(可理解为“解锁”)

作其他处理

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

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

要在有限的时间内进入临界区，保证不会饥饿

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

子主题

<br>

补充：①其中增加一个产品，使用产品都可以加入到临界区，但是这样会增加访问临界区的访问时间，会导致整体效率降低②实现互斥和实现同步的两个P操作的先后顺序（互斥的P操作必须在同步的P操作后，否则会导致死锁问题，上面的实例有）

当缓存区为2时<br>

当缓存区为1时

在生产者-消费者问题在，若果缓存区大小为1，那么优肯不需要设置互斥信号量就可以实现互斥访问缓存区的功能，但是这不绝对，所以我们自己写题，需要时就用上互斥信号量

不要去思考单个进程行为，要去思考进程抽象出来的时间，例如上述，儿子 女儿进程都会导致盘子（缓存区）变空，让父母，从而导致父母去放水果，这样就会出现四个一前一后关系了，我们应该去思考“事件的前后关系”儿子，女儿进程都会做的一个是事情就是让盘子变空：也就是盘子变空事件；而父母都会去放入水果：也就是放入水果时间。说白了就是 进程都要做到是行为，抽象出来就是事件<br>

吸烟者问题为我们解决“可以生成多个产品的单生产者问题”

轮流提供服务，使用一个整形变量I实现“轮流”这个过程

核心思想

子主题

解决办法

每当之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程需要同时持有两个临界资源，因此就会有“死锁”的问题的隐患<br>

如果在考试遇到一个进程同时持有多个临界资源的情况，应该参考哲学家问题，分析是否会有循环等待，死锁问题

总结：如果同类资源树大于1，则即使有循环等待，也未必会发生死锁。但如果系统中每类资源都只有一个，那循环的古代就是死锁的充分必要条件

将互斥资源变成不互斥资源

缺点：可行性不高，很多时候操作系统为了保证安全，很多资源不允许这样

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

方案二：申请的资源被其他进程占用时，由操作系统协助剥夺(根据优先级)

缺点：①实现复杂；②如方案二剥夺了资源可能导致部分工作失效；反复申请和释放导致系统开销大②如方案一，得不到就一直放弃，可能会导致饥饿

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

缺点：资源利用率低；可能导致饥饿，例如：一个进程用的资源1只用2秒，而这个进程却运行50秒，造成长时间的空闲，还会让其他需要资源1的进程饥饿

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

缺点：增加新设备不方便；会导致资源浪费(要先用大进程，就必须把无关的小进程申请/访问)；用户编程麻烦(不同的机子，编号不同，就要对待更改操作)

如果系统按照一种序列分配资源，则每个进程都会顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，<b>安全序列可能有多个</b>

若系统找不到一个安全序列，系统就进入<b>不安全状态</b>。当然，若有进程现在归还了资源，系统有可能重回安全状态

若系统处于<b>安全状态</b>，那么<b>一定不会</b>发生<b>死锁（当前已经分配完资源）</b>。如果系统进入<b>不安全状态(当前并没有分配资源)</b>，就<b>可能</b>发生<b>死锁（处于不安全状态可能发生死锁，发生了死锁一定处于不安全状态）</b>

<b>在系统资源分配之前先判断这次是否会导致系统进入不安全状态，这也是银行家算法的核心</b>

核心思想

数据结构：资源分配图

死锁检测算法(有可能和数据结构一起考察)

例子

资源剥夺法

撤销进程法(终止进程法)

进程回退法

如何决定对谁动手

<b>支持多道程序</b>；在单一连续分配方式中，内存被分为<b>系统区</b>和<b>用户区</b>。系统区通常位于内存的低地址部分，用于存放操作系统给的相关数据；用户区用于存放用户进程的相关数据，内存中<b>只能有一道用户程序</b>，用户程序独占整个用户区空间<br>

优点

缺点

<b>将整个用户区划分为若干个固定大小的分区，在每个分区中只装入一道作业</b>

分区大小相等

分区大小不等

来实现各个分区的分配和回收。每个表对应着一个分区，通常安分区大小排列。每个表项包括对应分区的<b>大小、起始地址、状态（是否以及分配）</b>

图例

优点

缺点

也称为<b>可变分区分配</b>，这个分配方式<b>不会预先划分内存分区</b>，而是在进程装入内存时，<b>根据进程的大小动态的建立分区</b>，并使分区大小正好适合进程的需要。因此系统分区的大小和数目是可变的

系统采用什么样的数据结构记录内存使用情况

系统如何进行内存的分配和回收<br>

内部碎片

外部碎片

子主题

首次适应算法

最佳适应算法

最坏适应算法

邻近适应

图例

<b></b><b></b>页框和页框号

页面和页号

关系

图例

页表<br>

&nbsp;每个页表项多大？占多少字节

如何通过页表实现逻辑地址到物理地址的转换

页表寄存器的作用

地址变换过程

补充细节

什么是快表

引入快表后的地址变换过程<br>

局部性原理<br>

具有块表和不具有块表的地址变换机构的区别与联系

单级页表存在什么问题？如何解决？

两集页表的原理、逻辑地址结构

如何实现地址变换

两级页表问题需要注意的几个细节

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

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

逻辑地址结构：(段号，段内地址)

图例

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

每个段对应一个段表项。各段表项长度相同，由段号(隐含)、段长、基址组成

图例

由逻辑地址得到段号、段内地址

段号与段表寄存器中的段长度比较，检查是否越界

由段表始址、段号找到对应段表项

根据段表中记录的段长，检查段内地址是否越界

由段表中“基址+段内地址”得到的最终物理地址

访问目标单元

图例

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

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

分段更容易实现信息共享和保护(纯代码/可重入代码可以共享)

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

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

将内存空间分为与页面大小相等的一个个内存块(就是页框)，系统以块为单位为进程分配内存

逻辑地址结构：(段号，页号，页内偏移量)

图

每个段对应一个页表项。各段页表项长度相同，有段号(隐含)、页表长度、页表存放地址组成

每个页对应一个页表项。各页表项长度相同，由页号(隐含)、存放的内存块号 组成

由逻辑地址得到段号、页号、页内偏移量

段号与段表寄存器中的段长度比较，检查是否越界

由段表始址、段号找到对应端表项，检查页号是否越界

根据段表中记录的页表长度，检查页号是否越界

由段表中的页表地址、页号得到查询页表，找到相应页表项

由页面存放的内存块号、页内偏移量得到最终的物理地址

访问目标单元

第一次--查段表、第二次--查页表、第三次--访问目标单元

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

因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断

固定分配:操作系统为每个进程分配一组固定数目的物理块。在进程运行期间不再改变。即，驻留级大小不变

可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少，即，驻留级大小可变

局部置换：发生缺页时只能选进程自己的物理块进行置换

全局置换：可以将操作系统保留的空闲物理块分给却也经常，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程