操作系统OS笔记（未完）

2023-12-30 20:00:46

硬件所做的事情

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

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

软件（操作系统）

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

2.处理中断

3.消除中断标记

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

异常：

硬件：

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

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

软件（操作系统）

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

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

跨域操作系统边界的开销

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

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

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

地址安全检测过程

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)]

程序的局部性原理

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

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

例子：

操作系统OS笔记（未完）操作系统OS笔记（未完）

交换区的大小为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前面的数据替换出去

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

最近最久未使用算法

操作系统OS笔记（未完）

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

两种可能的实现方法是：

1.通过链表

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

2.通过堆栈

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

时钟页面置换算法

操作系统OS笔记（未完）

​

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

操作系统OS笔记（未完）

最左边的位代表是否在物理内存中存在，第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执行程序中一条条指令使得这个程序能够动态的执行起来这个过程称为进程

操作系统OS笔记（未完）

进程与程序的联系

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

操作系统OS笔记（未完）[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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)]

操作系统OS笔记（未完）[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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中会去切换进程去进行执行，我们不希望就是说当某个进程执行时切换了其他进程后此进程将前面进程的数据破坏掉导致前面的进程运行失败或者出错（在内存管理中，页这一个技术就可以实现，内存访问只能够在特定的页中去访问，不然就会出现缺页异常）

操作系统OS笔记（未完）

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

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

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

操作系统OS笔记（未完）操作系统OS笔记（未完）

问题：

1.PCB具体包含什么信息

2.PCB是如何组织的

3.进程的状态切换

操作系统OS笔记（未完）[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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.进程的创建

操作系统OS笔记（未完）

进程等待

操作系统OS笔记（未完）

进程唤醒

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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)]

进程状态变化模型

进程三种基本状态

操作系统OS笔记（未完）

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

五状态图

操作系统OS笔记（未完）

进程挂起

什么是进程挂起？

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

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

为什么要进程挂起？

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

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

挂起状态

操作系统OS笔记（未完）

与挂起相关的状态转换

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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)]

状态队列

操作系统OS笔记（未完）操作系统OS笔记（未完）

小结

操作系统OS笔记（未完）

线程管理

为什么使用线程？

为了解决性能瓶颈问题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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进程的资源是需要操作系统去进行一定的处理）

什么是线程

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

操作系统OS笔记（未完）

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

线程共享进程的资源

优点

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

缺点

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

线程与进程的比较

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

线程的实现

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

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

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

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

操作系统OS笔记（未完）

用户线程

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

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

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

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

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

缺点

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

内核线程

操作系统OS笔记（未完）

轻量级进程

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

上下文切换

什么是上下文切换

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

操作系统OS笔记（未完）

进程切换的过程

操作系统OS笔记（未完）

进程的创建

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

  • 子进程拥有自己的唯一进程ID，而这个PID与任何现有的进程组的ID都不同
操作系统OS笔记（未完）

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

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

wait()函数

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

加载和执行进程

操作系统OS笔记（未完）

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

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

操作系统OS笔记（未完）

等待和终止进程

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

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

操作系统OS笔记（未完）

僵尸（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先执行 t1t2这段时间，然后去访问了共享资源t2t3

此时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)]

解决：上锁（单例模式双检查

上一篇：typora


下一篇：Typora软件使用基础以及MarkDown学习