硬件所做的事情

1.产生某种标记，比如中断标记

2.cpu得到这种标记后就会找到对应的中断处理然后告知操作系统

软件（操作系统）

1.保存当前程序状态，比如当前寄存器数据等等，以便中断结束后恢复

2.处理中断

3.消除中断标记

4.恢复程序之前保存的状态

异常：

硬件：

1.产生异常标记，告知cpu在某处产生了异常，cpu就得到异常的数据

比如产生异常指令的地址等

软件（操作系统）

1.通过cpu告知异常信息，先保存当前异常时的现场和状态

2. 根据异常编号进行处理（让程序退出执行，或者异常原因是由于操作系统服务不到位导致，就恢复现场然后重新执行异常时的指令

跨域操作系统边界的开销

1.在操作系统中，应用程序和操作系统内核所拥有的堆栈信息是不同的，当从应用程序切换到操作系统内核的时候需要进行对堆栈信息的保存，然后再对堆栈进行切换，这就需要开销，当然开销换回来的就是安全与可靠

2.当应用程序需要进行系统调用的时候，操作系统会对应用程序发出来的参数进行一个验证，这也需要开销，因为操作系统是不信任应用程序的

3. 当操作系统需要将数据从内核态传递到用户态时需要进行内存拷贝，要一个拷贝开销

地址安全检测过程

1.cpu中的alu寄存器会带着指令的逻辑地址告知cpu需要那个地址中的指令，然后将逻辑地址按照映射关系得到物理地址然后告知对应的寄存器，逻辑地址在映射成物理地址的时候是映射的一段物理地址空间，然后当逻辑地址映射在这一段物理地址空间的时候就是ok的

操作系统中内存的分配

1.按照内存地址从0开始进行寻找，当寻找到合适的内存空间的时候就进行分配

优点：实现简单，

缺点：容易产生空闲的内存块；当内存中空闲的块不多时分配时间较长

2.最优分配

按照内存块中和程序需要内存大小最匹配的机制来进行分配

优点：可以避免产生过多空余内存块的情况

缺点：会导致某块内存块被切割之后剩余一个很小的内存块然后不便于使用

3.最差分配

按照程序所需内存和系统内存块中相差最大的内存块进行分配

优点：避免了切割内存块后剩余内存块过小导致之后不方便使用的问题

缺点：将大的内存块进行了切分，当需要大内存的程序执行的时候系统不方便分配内存

4.内碎片和外碎片

内碎片：内存分块大于进程或线程所需的内存大小从而剩余的碎片

外碎片：指的是还没有被系统中进程或线程所使用的碎片

对于内存分配后产生的碎片处理（目的：消除碎片或者减少碎片的产生）

1.对内存进行拷贝，相当于将程序段紧凑的排列起来，从而产生多余的内存块

2.将系统中等待执行进程所占用的内存先暂时移动到磁盘中进行存储，从而空出程序段让下一个程序能够执行

内存分段管理

1.将程序中各各代码段分开来，不再全部放在同一个连续的物理地址上，但是在逻辑地址上是连续的，这时就需要一个对应的映射关系

内存分页管理

1.首先页帧的大小是固定的，逻辑上的页和物理上的页帧大小是相同的，方便硬件的实现

2.组成：1.页帧号、2.页帧号内的偏移地址

物理地址：页帧号占：F位、页帧的大小占：S位

=>能够有2F次方这么多的页帧 、 同时每一页的大小为2S次方

总结：（跟x86段基址寻址差不多）比如16位地址，高6位放页帧号（告知有多少页帧）低9位就是页帧的大小（S）然后偏移量就是说从某一个页帧开始低9位全0开始进行偏移所指向的那个地址就是我们需要的地址（也就是把偏移量化成2进制写入低9位中计算）

TLB一个缓存近期访问的页帧转换表项，存储方式是以key-value的方式存储的，（类似于告诉cache）如果命中能够很快的访问到对应的物理地址中，当表项未命中的时候会将其写入缓存中（x86中由cpu执行写入过程、Linux的系统由操作系统完成）

二级页表…（多级页表…）

为了解决页表过大内存中无法存放庞大页表的问题

在逻辑地址中增加一个字段p1存放的是一级页表的信息，找到之后将一级页表中数据+p2字段作为二级页表的索引然后就寻找到对应的地址信息

优点：节省了空间，对于不存在的物理地址空间在一级页表中就可以判断出来了，就不需要在二级页表中再次存储了节省了空间

缺点：需要进行多次寻址，消耗增加

反向页表

解决问题：即使再多级页表的情况下，在寻址能力强的计算机内还是需要很多的存储空间去存储页表

反向页表就是将物理页帧作为索引，通过映射关系将物理页帧号的索引映射到逻辑地址中。

优点：页表的大小会变的比较小

​ 并且页表的大小与逻辑地址的空间大小无关

缺点：需要的信息索引对换了，如何去建立一个合适且正确的映射关系

关联页表

设计可以做到很好（类似于页表缓存的设计key-value）但是开销太大

哈希+反向页表

通过哈希表，将逻辑地址中的pagenumber得到一个输出值再去搜索每页对应的物理帧号

问题:哈希存在碰撞问题，一个input可能会产生多个output

虚拟内存

1.覆盖技术

原理：当某段程序还没执行或者是执行完成，将这段内存空间用其他程序的数据进行一个覆盖，这样就可以实现用小内存跑大程序，

当然程序中是有调用关系的，在程序中没用被调用的代码段，或者是调用其他函数的代码的会放在内存段中，称为常驻区

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xVT2yk92-1636014347135)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211026100835497.png)]

比如A先调用B在调用C，在调用的时候访问的时间是不同的，我们就可以先将B段代码从磁盘中写入内存（覆盖区0），执行完成后再将B写回磁盘，之后再将C从磁盘中写入（覆盖区0）这样子就实现了内存的复用

缺点：开销问题，程序员需要去设计覆盖关系、并且cpu还有多次进行读写会导致时间的开销过大

交换技术（操作系统完成、程序员不需要了解过程）

将管理权限交给操作系统，在多个程序运行的情况下，如果内存空间不够，操作系统会把暂时不会运行的程序交换到硬盘中去（以整个程序为单位（覆盖技术是以程序某一部分为单位））

换出（swap out）：将整个进程从内存中导出到硬盘中

换入（swap in）：将整个进程从硬盘中导入到内存中

考虑问题：

1.什么时候交换

如果频繁的交换的话，硬盘读写的开销会很大

2.交换的大小（将内存中某个区域划分为交换的空间，称为交换区）

需要避免出现不够换入换出的情况

3.地址映射的问题（动态的地址映射）

有可能当内存中某个程序换出的时候，那一部分的内存已经被占用，此时该程序想进行换入操作但此时换入的地址已经不是当初的地址，可能会导致寻址异常

解决：通过类似页表对逻辑地址和物理地址进行一个映射，无论换入的位置是否改变都能够正常寻址

虚存技术（交换技术+覆盖技术）

解决问题：交换技术和覆盖技术还是不太满足我们的需求；

像覆盖技术那样只将程序中的一部分放入内存中，由操作系统完成，无需程序员干涉；

像交换技术那样能够实现进程在内存与外存中进行切换，但不是全部换出只将进程中不需要的那部分进行换出

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ryDuojyj-1636014347139)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211026135940248.png)]

程序的局部性原理

空间局部性：程序中当前指令和临近几条的指令和访问的数据都在临近的内存单元中

时间局部性：一条指令或数据的下次执行或访问都处于一个较短的时期内

例子：

交换区的大小为4K，第一次需要a0.0这个数据从硬盘中读取4k也就是a0.0~a0.1023但下次访问的是a1.0所以系统需要再次向磁盘中读取以此类推…

​ 解法1访问的数据在空间上离的很远并且在时间上也指令与指令之间也不是一个短的周期，不具备空间局部性和时间局部性

基本特征

大的空间：通过将物理内存和外存进行结合，使得内存大于实际的物理空间

部分交换：与交换技术相比，虚拟存储的调入调出是按照页或者段进行交换

不连续性：在程序运行的时候对于逻辑地址来说是连续的，但是在虚拟内存中有可能存在当访问某个逻辑地址时但此时地址中是没有数据的会造成访问异常，但操作系统会对这个异常进行处理使得程序能正常运行

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Fl1xHSoE-1636014347142)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211026151153037.png)]

虚存技术–虚拟页式内存管理

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lYpetWqC-1636014347145)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211026152520697.png)]

操作流程：

1.执行程序的时候去寻找驻留位如果驻留位为1说明此时内存中含有次页的信息那么直接访问即可

2.如果此时驻留为为0，产生异常（缺页中断），交由操作系统处理，操作系统先看内存中是否有空余的页，以页为单位将外存中的数据写入内存中，同时处理逻辑地址与物理地址的映射关系，让程序能够正确找到对应的地址，然后重新运行产生异常的指令

3.如果内存中没有空余的空间，操作系统会根据某种置换算法将内存中近期不经常使用的空间给释放出去/写入磁盘后释放（通过修改位判断，如果与外存中的数据相同，那么直接释放即可）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mX9eLRx8-1636014347148)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211026154202161.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-flTJ8xuf-1636014347149)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211026154609371.png)]

页面置换算法 （虚存技术）

页面最优置换算法

思路：当缺页发生时将系统中在未来很长一段时间都不使用的进程进行一个替换

做法：对某个进程进行一次模拟，将模拟出来的结果作为最优解进行算法设计

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kBwdcqPk-1636014347150)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211026155517565.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ybQO046X-1636014347151)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211026155744047.png)]

先进先出算法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QFn5LRIS-1636014347153)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211026191251531.png)]

通过list，将list前面的数据替换出去

虽然说实现简单，但是产生的缺页中断的情况会比较多

最近最久未使用算法

此算法需要记录各个页面的使用时间的先后顺序，开销会比较大

两种可能的实现方法是：

1.通过链表

当需要访问某个页面时，先查找链表中是否拥有这个页如果拥有，那么将该节点插入到链表的头节点中，如果没有，就将链表的头节点设置成该页，然后摘除尾节点

2.通过堆栈

先访问的页进行压栈,然后看栈中是否有与该页相同的页，如果有将其抽出，通过栈底指针来将最长未访问的节点出栈

时钟页面置换算法

​

在页表中除了保存页帧号的数据，还有些控制信息的数据，其中有一位代表的是这个页帧近期是否被访问（1是近期被访问）这位置1的过程是由硬件完成的，在寻找”老“页的时候就是通过这个位来去判断的，当然操作系统会定期的对这个位进行清零

最左边的位代表是否在物理内存中存在，第2位就是访问位

当有程序需要空间时，此时指针指向的虚拟页0，访问访问位是否为1，为1说明该页近期被访问过，然后将该位清零，指针指向下一个重复上述步骤，知道找到访问位未0的虚拟页

二次机会法

优化了上面的时钟算法，通过一个“脏”位来告知操作系统是否需要将页写入磁盘，减少了操作系统访问磁盘的次数，提高执行效率

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-egqDrmZE-1636014347154)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027212851314.png)]

只有当两个bit都为0的时候才会将该页替换出去（优先换出只读的页，对于经常被写的页让它尽可能的保存在内存中）（替换规则：先替换used_bit再替换dirty_bit）

最不常用法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Q5gyuLaM-1636014347155)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027213530257.png)]

Belady现象

进程的定义

一段静态的程序通过操作系统放入内存中通过cpu执行程序中一条条指令使得这个程序能够动态的执行起来这个过程称为进程

进程与程序的联系

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-g6mKcD8Q-1636014347157)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027094726509.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Od6dtT8r-1636014347158)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027094726509.png)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tMM2U7QB-1636014347159)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027095040334.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uY7CTwtP-1636014347160)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027094726509.png)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bNIWBzvv-1636014347160)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027095040334.png)]

进程的特点

首先先说明两个概念

并发：指的是在一段时间内有多个进程在执行（当时间短的时候，看起来就像在并行）

并行：指的是在一个时刻有多个进程在执行

独立性：不同的进程的工作不相互影响。

这里的不相互影响是指某个进程正确的执行结果

例子：在cpu中会去切换进程去进行执行，我们不希望就是说当某个进程执行时切换了其他进程后此进程将前面进程的数据破坏掉导致前面的进程运行失败或者出错（在内存管理中，页这一个技术就可以实现，内存访问只能够在特定的页中去访问，不然就会出现缺页异常）

描述进程的数据结构：进程控制块PCB

操作系统对每个进程都维护了一个PCB，用来保存进程的各种状态信息

（ps:操作系统也是一个程序）

问题：

1.PCB具体包含什么信息

2.PCB是如何组织的

3.进程的状态切换

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sv1uSkda-1636014347161)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027101000333.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yPqGcyQh-1636014347163)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027101000333.png)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4TLHv2RV-1636014347164)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027101213542.png)]

PCB的组成方式，根据操作系统的不同，也会有所不同

进程管理

1.进程的创建

进程等待

进程唤醒

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-laKnqBjV-1636014347165)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027102015820.png)]

进程结束

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uJVoBlP2-1636014347166)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027102050243.png)]

进程状态变化模型

进程三种基本状态

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TGwH4vPd-1636014347167)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027102430737.png)]

五状态图

进程挂起

什么是进程挂起？

（进程没有占用内存空间称为进程挂起）

进程没有占用内存空间，（在虚拟内存中）也就是说明该进程被暂时从内存中换出到磁盘中去

为什么要进程挂起？

当内存不足以去运行其他高优先级的进程时，或者用户希望对进程进行观察和调试为了满足这些从而引入了进程挂起

https://blog.csdn.net/weixin_39713763/article/details/111011326

挂起状态

与挂起相关的状态转换

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eFKslTfL-1636014347168)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027152855457.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5cUSDGUo-1636014347169)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027153002963.png)]

状态队列

小结

线程管理

为什么使用线程？

为了解决性能瓶颈问题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WB1ZJfHx-1636014347170)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027154942562.png)]

当cpu在运行这个程序的时候有可能会因为read的时候执行io操作导致产生了阻塞

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-U2ZwgcW5-1636014347171)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027155045409.png)]

一开始为了解决上面的问题，提出了多进程的实现方法，当程序在read遭到阻塞时，cpu就去运行其他的进程

问题：理论上是可以实现，但是如何让这三个进程之间实现通信呢

2.cpu在切换进程的时候需要切换上下文信息，开销很大（创建进程时：分配资源、建立PCB；撤销进程时：回收资源、撤销PCB）

至此，我们就希望引入一个新的实体（线程）

特征：1.实体之间可以并发的执行

​ 2.实体之间共享相同的地址空间和相同的资源（也就是实现了上述的进程间通信）（进程是相对独立的，一个进程拥有自己的空间和资源，如果A进程希望获取B进程的资源是需要操作系统去进行一定的处理）

什么是线程

定义：线程中的一条执行流程

进程的组成：1.线程、2.资源管理

线程共享进程的资源

优点

• 一个进程中可以拥有多个线程
• 各个线程之间可以并发的执行
• 线程能够共享地址空间和文件等资源

缺点

• 由于线程共同拥有进程的资源，当某一线程破环了资源中的数据时可能会导致进程的崩溃

线程与进程的比较

• 进程是资源分配的单位，线程是CPU调度单位
• 进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈
• 线程同样具有就绪、阻塞和执行三种基本状态，同样具有状态之间的转换关系
• 线程能减少并发执行的时间和空间开销
  • 线程的创建时间比进程短（因为在创建进程的时候需要为进程分配和管理资源，而对于进程来说只需要使用所属进程管理好的资源即可）
  • 线程的终止时间比进程短（不需要考虑资源释放等问题）
  • 同一进程内线程的切换比进程短（因为进程中的线程所拥有的地址空间相同，也就是同用一个页表，在切换的时候就在页中切换，而对于进程来说，切换进程需要去处理其他页中的cache、PCB等信息）
  • 由于同一进程的各线程间共享内存和文件资源，可直接进行不通过内核的通信

线程的实现

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DZZBxTAs-1636014347172)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027163655522.png)]

用户线程：操作系统看不见的线程

内核线程：由操作系统管理起来的线程

用户线程与内核线程的对应关系

用户线程

用户线程中有一个用户线程库，由这个库来对进程中的线程进行一个管理，操作系统不管理线程

当然线程控制块(TCB)列表和线程的各种状态信息都是由线程库函数来维护

用户线程的切换也是由库来实现，无需切换用户态/核心态 所以速度块

允许每个进程拥有自定义的线程调度算法

（ps：由于操作系统无法控制线程，当进程被挂起或者等待的时候，线程当然也无法执行）

缺点

• 当一个线程开始运行后，除非它主动交出CPU的使用权，否则该进程中的其他线程将无法执行（库不具有主动停止线程执行的功能）
• 如果一个线程发起系统调用而阻塞，则整个进程在等待
• 由于时间片是分配给进程的，在多线程执行时，每个线程的时间片可能会比较短

内核线程

轻量级进程

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xhYjQG8f-1636014347173)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027191859537.png)]

上下文切换

什么是上下文切换

在系统中会进行进程的一个切换，这个切换的过程叫做进程的上下文切换 （上文：切换进程之前保存的状态信息；下文：即将要调用的进程的状态信息）（各种寄存器信息）

进程切换的过程

进程的创建

通过fork（）函数去复制调用的进程从而来创建一个新的进程，这个新的进程称为子进程，并且与父进程为副本关系，除了下面几点

• 子进程拥有自己的唯一进程ID，而这个PID与任何现有的进程组的ID都不同

问题：为什么子进程中fork（）的返回值为0

首先在程序开始时候，进程被创建，然后当fork（）函数被调用，创建了子进程，那么在子进程中代码段的运行情况是什么样的呢，（子进程的执行进度与父进程的相同）那么就是说明此时子进程也是调用fork（）函数，所以为了不继续创建新的子进程，0是有意义的

wait()函数

wait（）函数是在父进程中等待子进程结束并回收子进程

加载和执行进程

当pid==0的时候进入到判断语句内部，执行exec方法，会将calc中的代码覆盖掉当前进程的代码，所以当exec（）函数正常执行的时候是不会执行输出语句（“Why would I execute”）的

（在执行exec（）函数之后进程的信息也会发生变化）

等待和终止进程

wait（）函数，会等待子进程结束后在执行父进程

作用：当子进程完成时，返回给父进程一些信息，让父进程帮助子进程释放PCB等资源

僵尸（zombie）态：

指的是当子进程执行完成exit（）后，父进程还是在执行wait（）函数，此时父进程还没有完全将子进程的资源进行释放，且子进程也没有死亡，但子进程是无法在回到用户态去进行执行了，只是等待着被父进程回收

情况：当子进程还未执行完之前，父进程先死亡了，那么是否子进程的PCB就无法进行回收了呢？

针对这一情况，操作系统会定期的去扫描进程队列，看看是否有子进程处于僵尸状态，操作系统会代理父进程去对子进程进行一个回收

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O7x9VTDJ-1636014347174)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211027211649181.png)]

处理器调度/CPU调度

进程抢占：

情况：当占用cpu的某个线程发生了阻塞时候，如果没有抢占机制，会导致其他线程必须等待这个线程完成之后才能够使用cpu资源

用户态抢占和内核态抢占（使操作系统更加灵活）

进程调度

调度算法

一些调度的指标

• CPU使用率 ：CPU处于忙状态所占时间的百分比
• 吞吐量 ：在单位时间内完成的进程数量
• 周转时间 ：一个进程启动（创建）到这个进程完成它的工作这个时间（两部分组成：等待时间（需要等待分配cpu时间片）+执行时间）
• 等待时间 ：进程在就绪队列中的总时间（进程从就绪态到执行态所等的时间）
• 响应时间 ：发送一个请求，到这个请求被进程处理完毕

调度原则、指标

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ahU2ljuk-1636014347175)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028093406260.png)]

希望调度算法达到的效果

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-g83ng8hs-1636014347176)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028093637804.png)]

（波动：越平稳越好，不要一会慢一会块）

（矛盾：我们是很难做到既要响应时间短并且吞吐量还高的所以在设计的时候要么只顾及一边，要么就对两个指标进行折中选择）

对于不同场合会侧重不同的指标

公平：

确保操作系统中每个进程所拥有的CPU的占有时间、等待时间等大体上相差不多，通常公平会增加平均响应时间

调度算法

1.常用的基本调度算法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Oste5nPy-1636014347178)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028100511227.png)]

轮循

• 对于公平性有一定的考虑

多级反馈队列

• 及考虑的公平也考虑了动态变化
• 动态变化：进程的执行时间、等待时间、根据进程的动态过程去调整

公平共享调度：cpu的等待时间和执行时间能够公平的共享

先来先服务

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gSX9ZHDd-1636014347179)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028101020492.png)]

优点：简单

缺点：

• 平均等待时间和周转时间波动会较大（因为时间长的进程位置不确定）
• 响应时间较长
• 没有考虑抢占

短任务优先

通过先来先服务的算法，当短进程先执行的时候系统的效率还不错

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sKEwprIZ-1636014347180)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028101407432.png)]

抢占：

假设当前一个进程运行到某个时间片，此时还需要5个时间片去完成进程，此时来了个进程A，A只需要3个时间片，那么就会发生抢占，将5的进程挂起到就绪队列中，然后执行进程A

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Fc2sNKJV-1636014347181)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028101928655.png)]

Ci指的是i进程的执行时间

缺点

• 连续的短任务可能会导致长任务产生饥饿
• 需要知晓进程的执行时间（我们很难知道进程在什么时候结束）

执行时间：通过一种公式对之前历史的执行时间对于进程的执行时间进行一个推断出下一次执行的大概时间

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EKxTjCfl-1636014347185)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028102318987.png)]

最高响应比优先

相比前面的算法多考虑了一个进程的等待时间

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9tl5hCrq-1636014347188)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028102546046.png)]

R越大，说明等待时间越长，且执行时间s短（也不一定）优先执行R大的进程

存在问题：很难知道s 执行时间，第二抢占问题，只不过把短时间换成了R（当然相对于前面短进程优先多考虑了等待时间的问题，对于饥饿现象有一定的解决）

轮循调度算法

特点：进程可以轮流占用cpu去执行

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VkhHyOWX-1636014347197)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028103103202.png)]

执行流程

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qvC9PAHM-1636014347200)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028103418050.png)]

我们通过设置一个时间片，让每个进程轮流的占用cpu

优点

每个进程都有占用CPU执行的机会

缺点

平均等待时间会较长

（ps：时间片大小的设置非常关键,设置的不好可能就与前面的FCFS算法相同了）

目标

• 设置一个好的合适的时间片（早期linux 1/100 s ; 现在linux 1/1000s）
• 维持上下文的开销处于1%以内

那么有没有能够较好的权衡轮循和FCFS算法的算法？

多级反馈队列

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EIdjIXZH-1636014347201)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028155312455.png)]

总结

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JLNbqCOq-1636014347202)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028155816664.png)]

实际上系统的调度算法是非常复杂的，但是基本的原理是相同的

实时调度

作用：用来确保某些任务必须要在规定的时间内完成

分为 硬实时 和 软实时两类

硬实时

任务如果不能再设定好的时间片段完成的话会造成灾难性的后果，（任务都必须在规定的时间内完成）

软实时

要求重要的进程优先级更高，尽量完成，并不是在规定时间内必须完成

如何去描述一个进程是否能完成实时性的需求？

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YxxZ6LIg-1636014347204)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028161550994.png)]

Released: 进程就绪

Execution time ：执行时间

执行时间一定不能够操作截至时间，不然实时性就没有得到满足

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4WFW5ukC-1636014347205)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028161845637.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0cP2y2EP-1636014347206)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028161909867.png)]

实时调度算法特点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EKQ2aeGG-1636014347208)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028161958908.png)]

2个经典调度算法

RM（一开始就会根据程序的执行周期设置好了优先级）

• 最佳静态优先级调度
• 通过周期安排优先级
• 周期越短优先级越高
• 执行周期最短的任务

EDF

• 最佳的动态优先级调度
• Deadline越早优先级越高
• 执行Deadline最早的任务

多cpu调度和优先级反转

如何通过多个CPU来有效的完成多处理器的调度？

考虑的问题：1.如何让系统的cpu达到负载平衡 ，2.如何选择cpu去执行进程

优先级反转

起因：NASA发射了一个火星的探测器，探测器上有一个操作系统，但是在探测的过程中操作系统老是重启

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HuTicMYL-1636014347209)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028163503616.png)]

一开始T3先执行 t1_{t2这段时间，然后去访问了共享资源t2}t3

此时T1进程进来了，抢占了CPU资源，执行一段时间后T1需要T3线程所访问的共享资源（此时这个资源被T3占用），那么T1就去等待T3去执行t4~t5，此时T2进程进来，抢占了CPU资源，那么此时出现了优先级反转的现象，T3是优先级最低的，T1是优先级最高的，但是由于低优先级的问题导致T1高优先级的进程无法及时的完成，导致操作系统认为此时处于一个不稳定的状态，所以就一直重启

解决办法

优先级继承：

当T1需要访问T3所占用的系统资源的时候将T3的优先级提高与T1相同，这一当T2再来的时候就无法去抢占cpu资源

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xyh8Oa7D-1636014347211)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211028164001602.png)]

2.优先级天花板： 操作系统根据线程所需要那些资源，将资源之间也分配了优先级（与最高优先级线程的优先级相同）

当某个线程访问了共享资源之后，这个资源就会赋予了一个优先级，当下一个进程访问这个共享资源时除非优先级比上一个高，否则无法访问

同步

为了解决在某种并发的情况下，执行结果的不确定性

原子操作

• 原子操作是在执行过程中是不可以被中断或者失败的

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-42JAt2Ut-1636014347212)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211030091846767.png)]

情况1：A赢 / B赢

情况2：根据调度算法的不同，AB两个线程可能会一直处于执行状态

为了解决上面的问题

一些必要的概念：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VQZaeGXE-1636014347213)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211030092341313.png)]

• 临界区：访问共享资源的那段代码称之为临界区
• 互斥：访问临界区的进程只能有1个

概念二

买面包问题（类似于单例模式）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vq5mTcx8-1636014347214)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211030092728426.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0EsgzKII-1636014347216)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211030093320321.png)]

上述的便签情况类似与单例模式的第一种情况，就是当进程A访问冰箱的时候没有便签，此时cpu切换到线程B，发现也没有便签那么就会出现问题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-x59Vk1Ek-1636014347217)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211030093450315.png)]

结果：

• 偶尔情况下还是会购买多的面包
• 并且上述问题是不可重现的，因为cpu每一次的调度顺序是不一样的，使得难以调试

情况2：谁也不会去买面包

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ExFhivsR-1636014347218)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211030093804812.png)]

解决：上锁（单例模式双检查🔒）（在这边叫做临界区和互斥）

解决2

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tBO4sHEb-1636014347220)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211030094840392.png)]

但是这种解决方式线程A会进行忙等，会消耗cpu的时间

临界区

• 互斥：同一时间临界区最多存在一个线程
• Progress：如果一个线程想要进入临界区，那么它最终会成功
• 有限等待：如果一个线程此时想要进入临界区，但临界区内中有进程正在访问，那么这个线程只需要等待有限的时间就可以进入临界区
• 无忙等待（可选属性）：希望等待进入临界区的线程尽量不要做忙等带（donothing）会很消耗cpu资源，可以在进入之前被挂起

基于上述属性，通过方法实现对临界区进行保护（也就是上锁）

屏蔽硬件中断（方法1）

产生面包问题的原因是什么？，在执行某段（临界区）代码的时候系统通过中断调用了其他的进程，那么我们只需要让进程进入临界区的时候将中断给暂时关闭，那么就会得到一个确定的结果，之后再将中断恢复就可以解决

缺点

• 中断是操作系统用来应对某些情况而产生的机制，比如说外设信息或者是网络的数据包，长时间的屏蔽中断会出问题
• 这个方式只适合临界区较小的程序去使用，因为不能长时间将中断给屏蔽
• 对于多cpu还是有问题

基于软件的解决办法 （方法2）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gHnl18y6-1636014347221)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211031085720355.png)]

通过turn来判断那个进程能够进入临界区，当进程i离开临界区时候将其他线程的值j赋值给turn

问题：可能会导致某个想进入临界区的线程无法进入临界区

情形：进程1进入临界区并且执行完成后将turn赋值为0，此时线程0获得进入临界区的资格，但线程0不进入临界区而是去干别的事情了，此时1又想重新进入到临界区执行但是turn 为0 它无法进去，而线程0有不执行临界区代码，就出现了问题

解决上面的问题，想到了用一个数组

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IeInOWEF-1636014347222)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211031091543483.png)]

但依然存在问题

解决：

• 使用了两个共享数据项 turn（指示那个线程进入临界区） 和 flag[]（指示线程是否准备好进入临界区）
• 通过借鉴上面的解法将turn和flag同时进行使用

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xd9L3E9a-1636014347223)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211031091825775.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YuYLvfzz-1636014347225)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211031091843745.png)]

针对n个进程的算法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6aJTCZBV-1636014347226)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211031092542420.png)]

当线程i希望进入临界区的时候需要等待前一个希望进入临界区的线程或者是已经进入临界区的进程执行完之后才能进入临界区

Bakery算法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rrmTjmgc-1636014347227)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211031092913522.png)]

更高级的抽象（方法三）

由于软件的成本高并且逻辑复杂

通过硬件中一些原子操作去完成互斥、前进等临界区属性

同步（背景）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QD3yIOir-1636014347228)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211031093855152.png)]

有时候可能会想进入临界区的线程多一些，并不只是一个线程

信号量

问题：有时候有些线程进入临界区可能只是执行一些读操作，这时候就可以不用只限制一个线程

解决：通过信号量来解决控制

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HOL2NZYT-1636014347231)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211031100149956.png)]

信号量的使用

在信号量中有P操作和V操作，分别为+1和-1，通过判断信号量>0或者是<0来判断当前是否能够支持线程执行某些操作

生产者消费者问题的直线（信号量）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bMa8TrsO-1636014347232)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211031214008194.png)]

mutex:互斥操作

思考：对应的P V 操作的顺序能否互换， 比如mutex->V()能否与fullBuffers->V()操作进行互换，会有什么后果

V操作能够互换，P操作不能互换

管程

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZaIOuaO8-1636014347233)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211031203520154.png)]

用来管理线程的执行的一个抽象的概念，类似于信号量的升级

首先就是有一个进程队列来申请进入到管程中执行，（在管程中只允许有一个线程在执行），管程中还有2个条件队列（x,y），当某个线程需要挂起时就会放到条件队列中（其中有两个变量 wait：表示当前条件队列中等待的线程数，signal：表示提示信息，比如某个值变化的时候去告知管程看看是否需要唤醒相应的线程来进入管程中进行执行）（类似于信号量的P V 操作）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wBxwLty3-1636014347234)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211031205414689.png)]

生产者和消费者实现（管程）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oxNDeaf8-1636014347235)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211031205510379.png)]

在这里，我想问大家一个问题就是这个while在目前看来能否使用if判断去将其替代？（在后面我们会讲到）

有个问题，当某个线程需要执行别的线程的唤醒操作之后，我们是马上执行那个被唤醒的线程，还是等该线程执行完之后在去执行唤醒的线程。

两个解决思路：1.先等该线程执行完成之后在执行被唤醒的线程，2.直接执行唤醒的线程

现在我们回到之前将的while if那个问题上，

方法1

对于方法1 我们使用while，为什么？，当我们唤醒线程的条件达到的时候，我们继续往下执行，知道释放，此时条件队列中可能会有多个线程去抢占cpu执行，这样可能会导致条件队列中没有抢占到cpu的线程进行误判，因为此时条件count值有可能被别的线程所修改，从而导致到真正对应应该被唤醒线程在执行的时候由于count值的不同而出现错误。

方法2

对于方法2我们可以直接使用if，因为当线程唤醒的时候，对应的线程是确定的，此时count的值一定不为n，因为此时cpu的控制权一定会被交到被唤醒线程的手中，不会因为一些别的线程抢占cpu所导致问题的产生

ps：下面是笔者在学习的时候产生的疑问，(已解决,如上)

（可能这里我的理解会有问题，我的理解是这种方法的情况下，管程中这个线程能够找到对应1个线程去唤醒，不然我认为还是会出现上面方法1的抢占情况，也有可能这种情况并不是抢占所导致的，而是类似与ABA问题所导致的）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lvjlT3m1-1636014347237)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211031211945481.png)]

同步问题笔者暂时没有做笔记，日后再来完成

死锁

死锁的系统模型

首先思考一个问题，为什么会产生死锁这种现象？

由于由于系统进程对应资源的请求的不合理，导致出现一种环状的资源请求，2.由于资源具有互斥性

（ps：在操作系统中，进程使用资源的时间是有限的，在进程使用完资源后需要将资源进行一个释放）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yeq3zxfW-1636014347238)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103162829376.png)]

死锁

资源闭环不一定产生死锁，死锁的产生一定有资源闭环

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pxsKk1eQ-1636014347239)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103162902715.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5rPUgPYO-1636014347240)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103162913001.png)]

死锁特征

死锁出现的时候会出现下列4个条件（ps:下列四个条件出现不一定出现死锁）

1.互斥：在一个时间内只能有1个进程使用资源

2.产生了资源请求的闭环，并且闭环中的进程均不会释放所拥有的资源，并会请求其他的资源

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-w3skfKd6-1636014347248)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103163342529.png)]

死锁的处理办法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ADG5xl9h-1636014347251)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103163551902.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-a6izvUGO-1636014347252)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103163720817.png)]

有些操作系统会忽略死锁，原因是检测死锁和恢复死锁所耗费的资源开销太大，操作系统不愿意去做

死锁预防

1.互斥：将本来互斥访问的资源变成不互斥（不太好，1.不好实现，2.就算实现了很可能导致进程执行的不确定性）

2.占用并等待-对于进程来说要么拥有全部的资源之后再执行，要么就sleep

（这种确实能够解决死锁的问题，但是对于资源的利用率过低，进程在执行的过程中对于资源的需求是不同的，有可能执行某段程序的时候只需要一小部分资源便可执行，并且可能会产生饥饿现象）

3.无抢占-前面说到，资源是互斥的，当一个进程拥有一个资源的时候其他进程就不能够去访问这个资源，那么如何来做到无抢占就去获取到资源呢，就是将当前拥有这个线程的资源kill掉，

4.循环等待-对资源进行排序，并要求进程申请资源的时候要按照资源编号递增或递减来申请资源（这样可以让资源申请形不成环）

（ps：其实解决死锁就是看如何能够合理的打破四个条件之一）

死锁避免

当某个进程想申请资源的时候，操作系统会进行判断，如果给你了这个资源有可能会导致死锁的发生，那么不管此时这个资源是否被占用，都不会分配给这个进程

（那么操作系统如何去知道某个进程申请资源之后会发生死锁？）

操作系统需要一些信息来去完成上面的步骤

• 首先需要得知进程所需要的某个类型资源的最大数量
• 进程申请的资源数量一定不会超过最大数量（比如某个进程的最大数量为10，第一次申请7ok，第二次申请4就不ok了，因为超过了最大数量）
• 通过算法来动态的检查资源分配的状态来确保不会出现环形等待的情况，如果将资源分配给你后可能出现环形等待的情况，那么就不分配
• 当进程请求资源，系统判断分配后是否能够处于安全状态，那么就分配

（什么是安全状态？）

存在一个安全序列，里面有程序p0_{pi，操作系统会按照顺序来执行，当执行到达pn的时候，pn能够使用的资源为p0}pn-1 和系统此时所拥有的资源，那么就是安全状态，所以的进程都能够执行且不用等其他资源

（考虑：如何寻找安全序列的算法？）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sWx46kLf-1636014347253)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103171520876.png)]

（关系图）

（一些概念名词）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-88lmetyD-1636014347254)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103171655683.png)]

银行家算法

背景：1965年为T.H.E系统设计的避免死锁的算法，以银行借贷系统的分配策略为基础，保证系统的安全运行

• 前提条件

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vApT9I7j-1636014347255)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103185527166.png)]

数据结构

• n = 进程数量， m = 资源类型数量

• Max（总需求量） ： n×m矩阵。 如果Max[i，j] = k ，表示进程Pi最多请求资源类型Rj的k个实例

• Available（剩余空闲量）：长度为m的向量。如果Available [j] =k，意思就是有剩余k个类型为Rj的资源可以使用

• Allocation（已分配量）：n×m矩阵。如果Allocation[i，j] = k，则表示进程Pi当前被分配了k个类型资源为Rj的实例

• Need（未来需求量）：n×m矩阵，Need[i，j] = k表示在未来进程Pi可能需要k个Rj实例来完成

总量= 已分配+未来需求

算法设计

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xc47l84D-1636014347256)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103191023877.png)]

Finish[i] = false 表示当前线程i处于sleep态或者其他状态

Finish[i] = true 标称线程i现在拥有了所需要的全部资源，能够正常的执行结束

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-evQ4QUaj-1636014347259)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103191525079.png)]

1个线程与这个线程所需要的资源组成一个向量（1行）

n个线程就会形成一个矩阵，

将矩阵中的第i行与Work（系统空余资源）的i行去比较 如果<=说明系统中有满足线程i所需要的资源，那么i能够正常的执行并结束

（注意Need 和 Work是两个向量）[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vdXXfDin-1636014347260)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103192003218.png)]

当Finish中有一个i为false并且无法为true ，那么就是一个非安全状态

那么系统就不会去分配资源给线程

银行家算法的具体原理（跟上面差不多）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aDxVGB7x-1636014347261)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103193426116.png)]

例子

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kIjalbJ6-1636014347262)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103200506068.png)]

首先先进行步骤2，在矩阵中寻找need<= available的向量（p2）

找到之后，将Finish[i]置为true，执行并回收p2所占用的资源后加回available向量中去，接着继续寻找

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0rWfjl4O-1636014347263)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103200737109.png)]

找到p1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WKRifI8k-1636014347264)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103200755241.png)]

同理p3、p4

这样我们就找到一个序列使得全部进程都能够满足正常的执行

那么这样一个序列就称为save序列，那么操作系统就会为其分配资源

那么什么情况下是不安全的呢？

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-16MDkyew-1636014347265)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103202154262.png)]

一开始Available vector的值为112 ，此时p1向其request资源101，此时need<work，系统会分配给p1资源，此时pi所拥有的（Allocation）为201，此时Available vector的值为011，此时将这个数据提交给银行家算法，由于此时没有一个need满足，need<=Available所以此时序列是不安全的

死锁检测和死锁恢复

与死锁避免和死锁预防的区别：前者：即使你没有发生死锁，但只要检测出有可能死锁那么久不让你走，后者：允许系统进入死锁状态，当某个时间会进行检测，如果检测出死锁就执行恢复机制，如果没有就继续

1.对进程资源分配图进行简化（将资源节点去除只留下进程节点）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4bbTAhux-1636014347266)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103203233133.png)]

连线规则：（当发出资源请求的进程A向拥有资源的进程B建立一个连线（有向图））

2.通过算法判断有向图是否有环

资源类型的实例（和银行家算法拥有的一样）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-T9mX14dW-1636014347268)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103203714081.png)]

数据结构

• 上图 + Request：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8u6DER7G-1636014347269)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103203754915.png)]

死锁检测算法（大致原理）

与银行家算法前三步大差不差这里就不赘述了，唯一不同的是最后一步

是判断此时系统可能处于死锁 ，时间复杂度为O（m×n平方）（ps：由于笔者目前对时间复杂度没有进行复习，日后再填坑）

由于进程在执行过程中所需要的资源信息很难获取到，并行执行上述两个算法需要的开销较大，在一般的操作系统中不会经常的使用

例子的话参照银行家算法，两者非常类似

该算法的话大部分是用在开发阶段用来检测

死锁恢复

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GzHQ0G8A-1636014347270)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103212729550.png)]

reboot！能解决100%的问题

方法2：资源抢占

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-p58gWmjV-1636014347271)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103212852449.png)]

进程通信

IPC进程间通信

为什么需要这个？

首先，每个进程间是不能够相互访问内存地址等信息的，是为了保证进程执行的正确性，然后，在实际的问题中我们可能希望进程能够相互的交互来完成一定的工作（比如买面包问题）

通信方式

通信方式有两种

1.直接通信：两个进程之间直接进行通信

2.间接通信：两个进程之间先经过操作系统内核，由操作系统内核来进行转发

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UssF6INu-1636014347273)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103213605658.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lwwFC3hh-1636014347274)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103213619798.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1kIuzMu9-1636014347275)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103213730579.png)]

角度2来分类：阻塞与否

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QFStn9Id-1636014347276)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211103213849304.png)]

我们会通过具体的需求来选择一个合适的通信方式，并不是说角度2的方式更好

管道

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L2ibjV2T-1636014347277)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211104091621900.png)]

用来作为某两个进程之间进行输入输出的渠道，dos命令的话就是 |类似于管道的字符，

实际上这个管道是处于内核中的一个缓冲区，ls和more进程并不知道自己是向这块区域输入/输出数据的

流程：Shell创建两个子进程 ls 和 more，并且将ls的输出送至buffer

more的输入也设置为buffer，但进程ls和more并不知道，同时两个子进程共享父进程Shell的文件资源（类似与buffer）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CvKg2PkC-1636014347278)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211104092138868.png)]

消息队列

本质上也是一种数据传送的机制，那么与管道有什么区别？

管道的缺点：管道是父进程通过一定的机制帮助子进程建立好一个连接的通道，一旦进程中没有这种父子关系，那么管道就不能发挥作用。

其二，管道中传送数据的格式是一种字节流，不能是结构化的数据，比较不便

那么消息队列肯定能够比较好的解决上面的问题（不然出来干啥）

其一：对于多个毫不相干的进程也能够通过消息队列来传输数据

其二：消息队列中允许传送和接受结构化的数据，当我们在编写比较复杂的程序的时候可以方便编程

要注意的是：消息队列中的buffer和管道中的buffer一样，当buffer满的时候进程会睡眠

（ps：消息队列和管道都是一种间接通信的方式）

共享内存

这是一种直接通信的方式，系统在分配资源的时候会开辟一块内存空间来作为共享内存的地址，进程能够直接获取到其中的数据

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zXo3jRcK-1636014347279)(C:\Users\xiangz\AppData\Roaming\Typora\typora-user-images\image-20211104093628837.png)]

那么，如何实现？

回忆内存管理，1个虚拟的内存地址映射到1块真实的物理内存地址，说到这里可能大家已经想到解决的办法了，我们只需要将两个进程的虚地址的映射映射到这一块地址空间中去就可以完成，也就是2——>1的关系

文件系统