©2016-2024 Matools All rights reserved,
粤ICP备17059708号
视频地址
https://www.bilibili.com/video/av6538245
<https://www.bilibili.com/video/av6538245>
介绍
本篇博客，旨在记录视频学习的要点，所以格式随意， 方便本人日后自考和回忆，有兴趣的朋友可以评论讨论。
原文地址https://www.cnblogs.com/clockq/p/10318639.html
<https://www.cnblogs.com/clockq/p/10318639.html>
一、操作系统（OS）描述
1.1 什么是操作系统
OS = Kernel + Shell，是介于底层硬件和应用软件之间的一层软件架构。
* Shell 主要提供与Users的交互工作（Windows的GUI和Linux的Terminal）
* Kernel 主要负责管理计算机的硬件资源
* CPU调度器
* 内存管理 = 物理内存 + 虚拟内存
* 文件系统管理
* 中断和设备驱动
Kernel 特征
* 并发（也并行）
* 共享
* 虚拟化（cpu,内存 => 进程, 硬盘 => 文件）
* 异步
1.2 操作系统的发展历史
* 纸带+人工操作系统
* 多道操作系统
* 分时操作系统（1/1000 s一次分时）
* 单用户操作系统
* 分布式操作系统
计算机的快速发展与各个底层硬件的快速发展是分不开的（CPU的计算能力，IO的读写能力和网络带宽）
二、OS的启动、中断、异常和系统调用
2.1 计算机系统启动流程
BIOS = Basic Input/Output System
graph LR A[BIOS]-->B[Bootloader] B --> C[OS]
2.1.1 BIOS启动流程
POST = Power-On Self-Test
graph LR A[POST]-->B[启动顺序] B-->C[主引导记录]
2.1.2 主引导记录
主引导记录（MBR）= Master Boot Record
graph LR A[MBR]-->B[分区表] B-->C[活动分区]
2.1.3 硬盘启动
硬盘启动分为三种情况：
* 卷引导记录（Win）
* 扩展分区和逻辑分区（不常见）
* 启动管理器（Linux的Grub）
卷引导记录（VBR）= Volume boot record
graph LR A[活动分区]-->B[VBR] B-->C[OS]
启动管理器模式：
graph LR A[MBR]-->B[Grub]
2.1.4 操作系统启动
graph LR A[Load /boot/kernel]-->B[run /sbin/init]
2.2 中断、异常、系统调用
* 中断：不同硬件设备的计时器或网络中断（外设发起）（异步）
* 异常：非法指令或其他失败的处理状态（应用程序发起）（同步）
* 系统调用：应用程序主动向操作系统发出的服务请求（应用程序发起）（同步或异步）
2.2.1 中断处理流程
graph LR A[外设设置中断标记] --> B[保存现场] B --> C[中断程序处理] C --> D[清除中断标记] D --> E[恢复现场]
2.2.2 异常处理流程
graph LR A[保存现场] --> B[异常处理] B --> C[杀死异常程序] B --> D[重启发生异常的程序] C --> E[恢复现场]
D --> E[恢复现场]
2.2.3 系统调用处理流程
应用程序无法直接操作硬件，需要OS提供的服务接口来间接调用，例：
C语言的printf()函数，执行时会调用OS的write()接口
三、内存管理
3.1 计算机体系结构
计算机基本硬件结构 = CPU + 内存 + 外设
CPU = 运算器 + 寄存器 + 控制器 + Cache（L1 + L2）+ 存储管理单元（MMU）
3.2 内存分层体系
越是靠近CPU的内存，读取速度越快，由近及远依次是：
CPU寄存器 => Cache => 主存 => 虚拟内存
操作系统在内存管理上要完成的任务：
* 抽象
* 逻辑地址空间 != 实际地址空间
* 保护（隔离）
* 同时运行多个应用，每个应用有一片独立的地址空间
* 共享
* 进程间可以使用共享内存进行交互和数据的传递
* 虚拟
* 内存不足可以利用硬盘获得更多的地址空间
3.3 地址空间和地址生成
*
逻辑地址空间：一个运行程序所拥有的内存范围。该地址是相对于当前进程数据段的地址，不和绝对物理地址相干。一个逻辑地址，是由一个段标识符加上一个指定段内相对地址的偏移量，表示为
[段标识符：段内偏移量]。
* 线性地址：是逻辑地址到物理地址变换之间的中间层。
* 物理地址空间：硬件支持的地址空间。
逻辑地址------（段机制）------->线性地址------（页机制）------->物理地址。
既然逻辑地址最终要转换为物理地址，那么为何还需要逻辑地址呢？
逻辑地址提供了权限检查功能：比如我们设置逻辑地址和物理地址之间的映射关系时，可以设置某块地址是只读的，只写的，只有CPU处于管理模式时才能访问等。这些功能可以让系统的内核，用户程序的运行空间相互独立：用户程序即使出错，也无法破坏内核；用户程序A崩溃了，也无法影响到用户程序B。
3.3.1 逻辑地址生成过程
graph LR A[C程序.c] --> |编译| B[编译程序.s] B --> |汇编| C[汇编程序.o] C --> |链接|
D[执行程序.exe] D --> |加载| E[应有载入内存]
各个步骤的作用：
* 编译：C程序代码中，每个指针（变量名、函数名）就代表着一个逻辑地址，但该地址对硬件而言是不友好的，因此先经过编译，将代码转为语法树，通过符号来描述地址。
* 汇编：经过汇编，将上一步的语法树转为机器语言，使用一段相对连续的，从零开始的地址描述程序。更加接近底层硬件语言。
*
链接：一个大的程序，可能通过多个.o文件组成，所以通过链接，将多个从零开始描述的.o文件组合到一起，并且使之不发生内存冲突。由此组成成为一个.exe应用程序，但此时该程序还存放在硬盘上。
* 加载：将上一步中，硬盘上的应用程序，通过一定的偏移量加载到内存中。此时的地址依然是逻辑地址。
具体流程如下图：
3.3.2 物理地址生成过程
graph LR A[CPU加载逻辑地址内容] --> B{查看MMU中是否映射了物理地址} B --> |有| L[获得物理地址] B --> |没有|
C{到主存中查找是否有物理地址映射表} C --> |有| L L--> D[读取物理地址的内容]
3.4 连续内存分配
3.4.1 内存碎片
* 外部碎片：在分配单元间未使用的内存
* 内部碎片：在分配单元中未使用的内存
3.4.2 分区的动态分配
什么时候分配？
* 应用程序启动，运行栈加载到内存的时候，分配一块连续的内存空间
* 应用程序加载数据时
内存分配算法
1. 首次适配
如要分配N byte，在内存中查找第一个可用（>=N）的空闲块，以满足最快分配。
需求：1. 按照地址排序； 2. 分配需要寻找合适的空闲块； 3. 内存回收后，要将相邻块进行合并。
优势：实现简单； 易于产生更大数据块。
劣势：会产生外部碎片； 不确定性。
2. 最优适配
如要分配N byte，在内存中查找第一个可用（>=N）的且最小的空闲块，以满足最快分配。更大的利用小空间。
需求：1. 按照剩余空间大小排序； 2. 分配需要寻找 最 合适的空闲块； 3. 内存回收后，要将相邻块进行合并。
优势：实现简单； 适合大量分配小内存。
劣势：重分配慢； 易产生大量微小的外部碎片。
3. 最差适配
如要分配N byte，在内存中查找第一个可用（>=N）的且最大的空闲块，以满足最快分配。避免出现大量微小空间。
需求：1. 按照剩余空间大小排序（倒序排列）； 2. 分配需要寻找 最 合适的空闲块； 3. 内存回收后，要将相邻块进行合并。
优势：适合大量分配中等大小内存。
劣势：重分配慢； 易产生外部碎片； 会破坏大的空闲块，使更大的应用无法分配。
3.4.3 压缩式碎片整理
将非运行时应用占用的内存移动到相邻的一处内存，以减少应用间的外部碎片
3.4.4 交换式碎片整理
利用虚拟内存，将非运行时应用占用的内存移动到虚拟内存，以使的运行时应用有更大的空闲空间使用。
3.5 非连续内存分配
优点：
* 内存分配在物理地址空间是非连续的
* 可以更好，最大化的利用物理内存和管理
* 允许共享代码和数据（贡献库等、、）
* 支持动态加载和动态链接
缺点：
* 内存管理本身的一些维护开销
* 硬件的配合和支持（分段和分页）
3.5.1 分段（Segmentation）
为了更好的分离和管理。
使用分断管理机制后，在逻辑地址层面，地址看上去是连续的，而在物理地址层面，可以将不同的代码段分离出来管理，从而实现共享，管理，权限保护等。
分断寻址方案
3.5.2 分页（Paging）
先划分物理内存至固定大小的帧（Frame），用二元组(f,o)表示帧号和帧内偏移；划分逻辑地址空间至相同大小的页（Page），用二元组(p,o)表示页号和页内偏移。帧更像是相框，里面啥也没有，放了照片（逻辑页面）才有意义。
物理寻址方式例题：
16-bit的地址空间，512byte大小的页帧大小，则物理地址为（3，6）的实际地址是多少？
解：
512 = 2^9 // 页帧需要使用9bit表示 16-9 = 7 // 页号需要使用7bit表示 所以实际物理地址的二进制表示为 0000011
000000110 转为十进制为1542，也可以用 3 * 512 + 6 = 1542
3.5.3 页表的缺点
每个运行程序都有一个页表，属于程序的运行状态，会动态的发生改变。
缺点：
* 通过分页实现的内存映射，需要进行两次查询（页表查询，物理地址访问）
* 页表会占用额外的内存，假如64bit机器的每页大小为1024byte，则最大会有2^54个页号
* 每个应用都有一份页表，对于问题2，就更加麻烦了
上述问题，可以使用缓存和间接访问两种方式解决。
3.5.4 页表的优化
TLB（Translation Look-aside Buffer）
TLB是一块特殊的快表，可以更快的获得物理帧号，且TLB的miss几率可以忽略不计。
页表有个特殊的概念叫驻留位（上图标红的地方），驻留位为0的表示物理帧号不存在，也就是本页映射无效。
多级页表
反向页表
页寄存器方案：
页表反向设计，页表索引以帧号为index，因为物理内存是固定的，而逻辑空间是无限增长的，因此大大减少了页表大小。
优：
* 占用空间小
* 转换表只与物理内存有关，与逻辑内存无关
弊：
* 信息对调，无法根据页号找到帧号
关联内存方案：。。。
Hash方案：。。。
四、虚拟内存管理
4.1 起因
希望有个很大、很快、很便宜的存储器，最好掉电数据不丢失。因此，贪心的人类想到了利用硬盘。
早期的计算机由于硬件限制，经常会出现内存不够的情况，当时主要通过覆盖技术(只把需要的指令和数据存在内存中)和交换技术(把暂时不用的指令和数据存到swap中)。
4.2 覆盖技术
产生于20世纪80年代，一般用于多道程序系统的DOS操作系统。当时计算机的内存容量大多只有640kb。
目的：
在较小的内存容量下运行较大的应用程序，与分区存储管理配合使用。
实现：
如下图所示，A程序为常驻应用，但BC程序不会相互调用，DEF程序也不会相互调用，所以就可以让之后调用程序内存覆盖之前调用的内存空间。（以模块为粒度覆盖）
缺点：
* 由程序员来考虑把一个大程序，划分为若干小的功能模块，并确定各个模块之间的依赖，覆盖关系。增加了系统复杂性和编程难度。
* 覆盖模块从外存装入内存，是典型的时间换空间。
4.3 交换技术
一般用于Unix操作系统。
目的：
让正在运行或需要运行的程序可以获得更多内存资源。
实现：
将暂时没有运行的程序移到外部swap，从而获得更多的物理内存。（以程序为粒度交换）
注意：
* 何时进行换入（swap in）好换出（swap out）操作？ 尽量少，内存不够再换出
* 交换分区（swap）的空间要设置多大？必须足够大，可以存放所用用户进程的内存拷贝。
* 内存换入时的地址重定向问题？要采用动态地址映射法。
4.4 虚存技术
在有限容量的内存中，以更小的页粒度为单位装入更多更大的程序（对覆盖技术和交换技术的一次融合）。
目的：
* 像覆盖技术一样，不将应用全部载入内存，而是载入部分，以此来运行比物理内存大很多的应用程序。但不需要程序员维护。
* 像交换技术一样，能够实现应用在内存和外存之间的交换。但不以程序为粒度交换。
要求：
局部性原理：
指程序在执行过程的一个较短时间内，所执行的指令地址和指令操作数地址，分别局限在一小块区域。
* 时间局部性：一条指令的一次执行和下次执行，数据的一次访问和下次访问都集中在较短时间内；（类似缓存、预加载，增加命中率）
* 空间局部性：当前指令和临近的几条指令，当前访问数据和临近的数据都集中在一块较小的区域内；（减少swap次数，同上）
举例： 对于一个二维数组[1024 * 1024], 对于横向打印和竖向打印，效率差异还是相当大的！
特征：
* 充分利用CPU寻址能力，获得更大的可用物理内存（主存+虚存）
* 部分交换
* 不连续性：逻辑地址也可以不连续
虚拟页式内存管理：
这种管理方式，是大多数虚拟存储设备的选择，即在页式存储的基础上，增加了请求调页和页面置换功能。
请求调页：应用程序装入内存时，不是一次性载入全部的页片到内存，而是用到哪个页片载入哪个帧。（局部加载）
页面置换：在应用运行过程中，如果发现需要的页片不在内存中，就会发生“断页中断请求”，系统处理这个中断，就会将虚拟内存中的帧加载到物理内存中。（延迟调用）
页表项结构
缺页中断处理过程
后备存储（Backing Store）
在何处保存未加载的帧？
* 能够简单的识别在二级存储器中的页
* 交换空间（磁盘或者文件）
后备存储可以有哪些？
* 一个虚拟地址空间的页：可以被映射到一个文件的某个位置
* 代码段：可以映射到可执行的二进制文件
* 动态共享程序段：映射到动态调用的库文件
* 其他段：映射到交换文件中
虚拟内存性能
有效存储访问时间（EAT）= Effective Memory Access Time
EAT = 访问时间 * 页表命中率 + 缺页处理时间 * 缺页几率
例子：
访问时间： 10ns 磁盘访问时间：5ms = 5 * 10^6 ns page fault rate：p dirty page
rate（页内容改变，同步到虚拟内存概率）：q EAT = 10 * (1 - p) + 5 * 10^6 * p * (1 + q)
由上述例子可以看出，变量p对于整体EAT的影响最重要。
4.5 页面置换算法
缺页几率，是严重影响虚拟内存效率的一个因素，而缺页几率与页面置换算法息息相关。
功能：当缺页中断发生，需要加载新的帧页到内存，但当应用内存已满时，需要选择淘汰物理内存中的帧来给新的帧资源。
目标：尽可能的减少页面换进换出次数。
对于常驻内存（如操作系统或其他关键应用）添加锁定标志位，避免换出。
分类：分为局部页面置换和全局页面置换两大类
* 局部页面置换：
* 最优页面置换算法（OPT）（最晚重用被淘汰）（理想状态，无法实现，可为依据）
* 先进先出算法（FIFO）（存活久的被淘汰）（利用链表即可实现，最差情况下性能较差）
* 最近最久未使用算法（LRU）（最久没用被淘汰）（链表、堆栈可实现，但开销较大）
* 时钟页面置换算法（Clock）（利用FIFO优化的LRU）（环形链表选最老）
* 二次机会法（？？）（Clock脏页版）（两条命的命中高，有了脏位换出少）
* 最不常用算法（LFU）（有的最少被抛弃）（表中加个计数器）
* 全局页面置换：
* 工作集页面置换算法（？？）（利用工作集的LRU）（无须缺页就淘汰，利用时刻来换出）
* 缺页率页面置换算法（PFF）（动态改变常驻集的工作集算法）（根据缺页频率，淘汰多个页面）
4.5.1 最优页面置换算法（OPT）
基本思路：当一个缺页中断发生，需要进行页面置换时，对于当前内存中的每一个逻辑页面，计算它下一次被访问时还需等待的时间，从中选择等待时间最长的页面，作为置换页。
评价：该算法无法实现或者说很难实现，因为OS无法预知每个页面下次访问需要的等待时间，但该算法可以作为其他算法评定的依据。
例图：
4.5.2 先进先出算法（FIFO）
基本思路：对于当前内存中的每一个逻辑页面，计算它载入内存的时间，从中选择驻留时间最长的页面，作为置换页。
评价：利用链表实现，载入向链尾加，换出删除链表头即可。
例图：
4.5.3 最近最久未使用算法（LRU）
基本思路：选择最久未被使用的帧页，作为置换页。
评价：时间轴上与最优算法相反，符合局部性原理。在最近一段区间内，找到最久未使用的帧。对于记录各页面调用的先后顺序，开销较大，可以利用链表或堆栈实现。
例图：
4.5.4 时钟页面置换算法（Clock）
基本思路：与LRU相似，是FIFO的一种改进。是二者之间的一种平衡。实现是在页面中加入一个访问位
,一个页面载入时，由硬件初始化为0（软件也可以），如果页面被访问，则相应页表项置为1。将各页表项组成一个环形链表，发生缺页中断时，指针循环判断环形链表，若判断的页表项为0，选为置换页，置换并访问新页后，新页表项置为1，指针下移；若判断的页表项为1，则改为0，指针下移。
评价：时间轴上与最优算法相反，符合局部性原理。在最近一段区间内，找到最久未使用的帧。对于记录各页面调用的先后顺序，开销较大，可以利用链表或堆栈实现。
例图：
4.5.5 二次机会法（）
基本思路：对Clock算法的一个改进，优化Clock算法对修改页面的写入逻辑，引入新位dirty bit
（脏位）来标识内存修改过与虚存不一致。对于脏位为0的页面，不必进行同步回虚存的一步。而对于脏位为1的页面，多了一次存活机会，与访问位用法一样。
评价：优化Clock算法的换出效率，并利用两个标识位拥有两条命，来增加存活率，加大命中次数。
例图：
4.5.6 最不常用算法（LFU）
基本思路：选择访问次数最少的页为置换页。所以要维护一张表，对每个页都有个访问计数器。
评价：LRU关注访问过去时间，久的淘汰；LFU关注访问次数，少的淘汰。
4.5.7 局部页面置换算法总结：
Belady现象：
Belady（笔勒滴，一个科学家名）在采用FIFO算法时，有时会出现分配的物理页面数增加，缺页率反而提高（命中率反而下降）的反常现象。
例图：
解决：LRU算法
FIFO、LRU、Clock三者比较？
* FIFO、LRU都有先进先出思想，但LRU对于访问算作一次新的进入，有局部性思想。
* FIFO、LRU相比，LRU性能虽好，但开销较大；而FIFO有Belady现象
* LRU、Clock很相似，但Clock加入访问位模拟LRU的访问顺序，而不用动态维护顺序链表，开销更小，但性能较LRU略有不足
局部页面置换算法的问题：
对应用分配了固定的物理页帧，一定程度上限制了系统灵活性，比如同时运行多个程序，但高峰期正好交错开。所以可以根据应用运行的不同阶段，调整分配的物理页帧，最大化利用系统资源。
4.5.8 工作集和常驻集
工作集：一个进程p当前执行时刻t前，在之前的定长的页面访问工作集窗口△阶段，使用的逻辑页面集合，用二元函数 W(t, △) 表示；随时刻t变化，集合也在变化。
| W(t, △) |表示集合大小，即页面数目。（一段时间内访问的页面集合）
常驻集：一个进程p在当前时刻t实际驻留在内存中（物理页面）的页面集合。（某时刻访问的页面集合）
常驻集 <= 工作集。
缺页率：“缺页次数” / “内存访问次数”，影响因素：
* 页面置换算法
* 分配的物理页帧数（常驻集大小）
* 页面本身大小
* 编写的程序（是否符合局部性）
4.5.9 工作集页面置换算法
基本思路：类似LRU最久未用被淘汰，但不同的是触发事件不同，当时刻改变时（而非缺页时）就会清理物理页面，准备物理页帧。
例图：
4.5.10 缺页率页面置换算法（PFF）
基本思路：在工作集页面置换算法基础上，动态改变时刻窗口（△）大小，即常驻集大小。当缺页率上升时，提高常驻集大小，反之减少。（淘汰的触发时间是缺页时，一次可能淘汰多个页面）
评价：性能好，开销大。
例图：
4.5.11 抖动问题
什么是抖动？
当分配的常驻集小于工作集，使进程产生很多缺页中断，频繁进行换进换出，从而使运行速度变慢的现象叫做抖动问题。
产生原因？
随着驻留内存中应用的增加，分配给每个应用的物理页帧（常驻集）持续减少，缺页率随之提高。所以OS要选择运行适当的进程数量，及每个进程所需页帧数，使并发水平和缺页率达到一定平衡。
五、进程管理
5.1 进程描述（静）
5.1.1 进程的定义
一个具有一定独立功能的程序在一个数据集合上的一次动态执行。（将程序加载到内存并运行的过程）
5.1.2 进程的组成
* 程序代码
* 程序处理的数据
* 运行指令的计数器
* 一组通用的寄存器中保存的当前值，堆、栈、、、
* 一组系统资源（打开的文件，连接的服务）
5.1.3 程序和进程的关系
* 程序是产生进程的基础。（程序是永久的，是类模板；进程是临时的，是实例）
* 进程是程序运行的体现。（程序是静态的、进程是动态的）
* 每次运行相同程序会产生不同的进程。（进程号，输入数据，启动时间）
* 程序的一次运行可能产生多个进程。（相互依赖和调用） graph LR A>程序] -.-> B[食谱] C>CPU] -.-> D[厨师] E>数据]
-.-> F[原料] G>进程] -.-> H[制作蛋糕] B ==> D F ==> D D ==> H
5.1.4 进程的特点
* 动态性：动态创建，终止进程
* 并发：看上去多个进程同时执行
* 并行：真的在同时执行
* 独立性：非共享情况下，不同进程工作不互相影响（页表的功劳）
* 制约性：多个进程同时访问共享数据或同步是相互制约
5.1.5 进程控制结构
进程控制块
进程控制块（PCB） = Process Control
Block，用来描述进程的数据结构，保存与该进程有关的各种状态信息以及运行变化的过程，是进程存在的唯一标识。
进程控制块的功能
使用PCB可以：
* 创建进程
* 终止进程
* 组织管理进程
进程控制块内容
* （一）进程标识信息：如本进程的标识、父进程标识、用户标识
* （二）处理器状态信息：使用寄存器保存进程的运行现场信息
* 用户可见寄存器：用户程序可以使用的数据，地址等寄存器
* 控制和状态寄存器：如程序寄存器（PC），程序状态字（PSW）
* 栈指针：过程调用、系统调用、中断处理和返回时需要用到它
* （三）进程控制信息：状态的控制
* 调度和状态信息：操作系统调度进程并占用处理机使用，描述进程的执行现状
* 进程间通讯信息：通信相关的标识、信号、信件
* 存储管理信息：包含指向本进程映像存储空间的数据结构
* 进程所用信息：进程打开使用的资源，如文件等
* 数据结构连接信息：进程可以连接到一个进程队列或其他进程的PCB中，描述进程之间的关系，如父进程、子进程
PCB的组织方式
* 链表：同一状态的进程其PCB组成一条链表（运行表、就绪表、阻塞表）
* 索引表：同上，数据结构使用数组
5.2 进程状态（动）
5.2.1 进程的生命周期管理
graph LR New(创建状态) -->|进入就绪队列| Ready[就绪状态] Ready -->|被调度| Running[运行状态]
Running -->|时间片结束| Ready Running -->|等待事件| JudgeBlocked{是否阻塞} JudgeBlocked
-->|是| Blocked[等待状态] Blocked -->|事件发生| JudgeWakeup{是否唤醒} JudgeWakeup -->|是|
Ready Running -->|终止| Done(结束状态)
创建状态：一个进程刚被创建但并未就绪。（PCB初始化）
就绪状态：操作系统选择就绪进程，获得除CPU以外的所有资源。（PCB初始化完成）
运行状态：获得CPU并运行。
等待状态（阻塞状态）：等待某一事件而暂停运行。
结束状态：一个进程正在从系统中消失。（PCB删除）
创建事件：系统初始化；用户创建新进程；运行中进程执行系统调用。
阻塞事件：等待系统调用；等待异步调用；数据未就位。（进程只能自己阻塞自己）
唤醒事件：系统调用完成；异步调用完成；数据就位。（只能别的进程唤醒自己）
结束事件：自愿的；异常的警告；致命的错误；别其他进程杀死。
5.2.2 进程挂起
为了充分且合理的利用系统资源将进程挂起，并将挂起的进程映像从内存放到外存上。
分为阻塞挂起和就绪挂起：
graph LR Blocked[等待状态] -->|就绪进程要求更多资源时| BlockedSuspend[等待挂起状态] Ready[就绪状态]
-->|被高优先级进程阻塞| ReadySuspend[就绪挂起状态] Running[运行状态] -->|分时系统中被高优先级进程阻塞|
ReadySuspend BlockedSuspend -->|事件发生| ReadySuspend BlockedSuspend -.有足够资源时.->
Blocked ReadySuspend -.没有高优先级进程阻塞.-> Ready
5.2.3 PCB实现进程管理
5.3 线程（Thread）
轻量版的进程，也可以并发执行，并且共享相同的地址空间，以此实现通信和交互。
5.3.1 什么是线程
线程是进程中的一条执行流程。
抽象一下，进程只管理资源和线程，线程是进程的执行流程，负责应用的执行逻辑。
5.3.2 线程的优缺点
线程的优点
* 线程让进程的数据与业务分离
* 一个进程可以同时存在多个线程
* 线程也可以并发执行
* 各线程可以共享地址空间和资源
线程的缺点
* 一个线程的崩溃会导致所属进程的崩溃。
5.3.3 进程和线程的比较
进程 线程
资源分配单位 CPU调度单位
独享完整的资源平台 只独享寄存器和运行栈
具有状态和转换 具有状态和转换
并发执行时间和空间开销多 开销少
5.3.4 线程的实现
* 用户线程：在用户空间实现；(用户级线程库来管理)
* 内核线程：在内核空间实现；（OS内核感知和管理）
* 轻量级进程：在内核空间实现；
六、CPU调度算法
从就绪队列中选择一个进程/线程，在之后可以获得CPU资源。
6.1 调度条件
* 进程的状态从运行切换到等待
* 一个进程被终止了
6.2 调度原则
基本概念
* CPU使用率：CPU处于忙状态所占时间的百分比
* 吞吐量：在单位时间内完成的进程数量
* 周转时间：一个进程从初始化到结束所需时间（包括等待时间）
* 等待时间：进程在就绪队列中的总时间（就绪到运行状态所需时间）
* 响应时间：进程从提交到第一次响应所花费的时间
“更快”的服务
更快 = 高带宽（吞吐量） + 低延迟（响应时间）
目标
* 减少等待时间
* 减少响应时间
* 减少平均响应时间的波动，越平稳越好
* 增加吞吐量
6.3 调度算法
* 先来先服务算法（FCFS）（）（）
* 短进程优先（SPN）（）（）
* 短作业优先（SJF）（Shortest Job First）（同SPN）
* 短剩余时间优先（SRT）（Shortest Remaining Time）（同SPN）
* 最高响应比优先（HRRN）（）（）
* 时间片轮循（Round Robin）（）（）
* 多级反馈队列（Multilevel Feedback Queues）（）（）
* 公平共享调度（Fair Share Scheduling）（）（）
6.3.1 先来先服务（FCFS）
FCFS = First Come First Served
6.3.2 短进程优先（SPN）
SPN = Shortest Process Next
6.3.3 最高响应比优先（HRRN）
HRRN = Highest Response Ratio Next
6.3.4 时间片轮循（Round Robin）
6.3.5 多级反馈队列（Multilevel Feedback Queues）
6.3.6 公平共享调度（Fair Share Scheduling）
热门工具 换一换