自学自用 = B站(操作系统_清华大学(向勇、陈渝)) 未完待续。。

时间:2024-01-23 21:26:47

视频地址

https://www.bilibili.com/video/av6538245

介绍

本篇博客,旨在记录视频学习的要点,所以格式随意, 方便本人日后自考和回忆,有兴趣的朋友可以评论讨论。

原文地址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 硬盘启动

硬盘启动分为三种情况:

  1. 卷引导记录(Win)
  2. 扩展分区和逻辑分区(不常见)
  3. 启动管理器(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应用程序,但此时该程序还存放在硬盘上。
  • 加载:将上一步中,硬盘上的应用程序,通过一定的偏移量加载到内存中。此时的地址依然是逻辑地址。

具体流程如下图:
image

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. 应用程序启动,运行栈加载到内存的时候,分配一块连续的内存空间
  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 非连续内存分配

优点:

  1. 内存分配在物理地址空间是非连续的
  2. 可以更好,最大化的利用物理内存和管理
  3. 允许共享代码和数据(贡献库等、、)
  4. 支持动态加载和动态链接

缺点:

  1. 内存管理本身的一些维护开销
  2. 硬件的配合和支持(分段和分页)

3.5.1 分段(Segmentation)

为了更好的分离和管理。

使用分断管理机制后,在逻辑地址层面,地址看上去是连续的,而在物理地址层面,可以将不同的代码段分离出来管理,从而实现共享,管理,权限保护等。

image

分断寻址方案

image

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

image

3.5.3 页表的缺点

每个运行程序都有一个页表,属于程序的运行状态,会动态的发生改变。

缺点:

  1. 通过分页实现的内存映射,需要进行两次查询(页表查询,物理地址访问)
  2. 页表会占用额外的内存,假如64bit机器的每页大小为1024byte,则最大会有2^54个页号
  3. 每个应用都有一份页表,对于问题2,就更加麻烦了

上述问题,可以使用缓存间接访问两种方式解决。

3.5.4 页表的优化

TLB(Translation Look-aside Buffer)

image

TLB是一块特殊的快表,可以更快的获得物理帧号,且TLB的miss几率可以忽略不计。
页表有个特殊的概念叫驻留位(上图标红的地方),驻留位为0的表示物理帧号不存在,也就是本页映射无效。

多级页表

image

反向页表

页寄存器方案:

页表反向设计,页表索引以帧号为index,因为物理内存是固定的,而逻辑空间是无限增长的,因此大大减少了页表大小。

优:

  • 占用空间小
  • 转换表只与物理内存有关,与逻辑内存无关

弊:

  • 信息对调,无法根据页号找到帧号
关联内存方案:。。。
Hash方案:。。。

四、虚拟内存管理

4.1 起因

希望有个很大、很快、很便宜的存储器,最好掉电数据不丢失。因此,贪心的人类想到了利用硬盘。

早期的计算机由于硬件限制,经常会出现内存不够的情况,当时主要通过覆盖技术(只把需要的指令和数据存在内存中)交换技术(把暂时不用的指令和数据存到swap中)

4.2 覆盖技术

产生于20世纪80年代,一般用于多道程序系统的DOS操作系统。当时计算机的内存容量大多只有640kb。

目的:

在较小的内存容量下运行较大的应用程序,与分区存储管理配合使用。

实现:

如下图所示,A程序为常驻应用,但BC程序不会相互调用,DEF程序也不会相互调用,所以就可以让之后调用程序内存覆盖之前调用的内存空间。(以模块为粒度覆盖)

image

缺点:

  1. 由程序员来考虑把一个大程序,划分为若干小的功能模块,并确定各个模块之间的依赖,覆盖关系。增加了系统复杂性和编程难度。
  2. 覆盖模块从外存装入内存,是典型的时间换空间。

4.3 交换技术

一般用于Unix操作系统。

目的:

让正在运行或需要运行的程序可以获得更多内存资源。

实现:

将暂时没有运行的程序移到外部swap,从而获得更多的物理内存。(以程序为粒度交换)

image

注意:

  1. 何时进行换入(swap in)好换出(swap out)操作? 尽量少,内存不够再换出
  2. 交换分区(swap)的空间要设置多大?必须足够大,可以存放所用用户进程的内存拷贝。
  3. 内存换入时的地址重定向问题?要采用动态地址映射法。

4.4 虚存技术

在有限容量的内存中,以更小的页粒度为单位装入更多更大的程序(对覆盖技术和交换技术的一次融合)。

目的:

  1. 像覆盖技术一样,不将应用全部载入内存,而是载入部分,以此来运行比物理内存大很多的应用程序。但不需要程序员维护。
  2. 像交换技术一样,能够实现应用在内存和外存之间的交换。但不以程序为粒度交换。

要求:

局部性原理:

指程序在执行过程的一个较短时间内,所执行的指令地址和指令操作数地址,分别局限在一小块区域。

  • 时间局部性:一条指令的一次执行和下次执行,数据的一次访问和下次访问都集中在较短时间内;(类似缓存、预加载,增加命中率)
  • 空间局部性:当前指令和临近的几条指令,当前访问数据和临近的数据都集中在一块较小的区域内;(减少swap次数,同上)

举例: 对于一个二维数组[1024 * 1024], 对于横向打印和竖向打印,效率差异还是相当大的!

特征:

  1. 充分利用CPU寻址能力,获得更大的可用物理内存(主存+虚存)
  2. 部分交换
  3. 不连续性:逻辑地址也可以不连续

虚拟页式内存管理:

这种管理方式,是大多数虚拟存储设备的选择,即在页式存储的基础上,增加了请求调页和页面置换功能。

请求调页:应用程序装入内存时,不是一次性载入全部的页片到内存,而是用到哪个页片载入哪个帧。(局部加载)
页面置换:在应用运行过程中,如果发现需要的页片不在内存中,就会发生“断页中断请求”,系统处理这个中断,就会将虚拟内存中的帧加载到物理内存中。(延迟调用)

页表项结构

image

缺页中断处理过程

image

后备存储(Backing Store)

在何处保存未加载的帧?

  1. 能够简单的识别在二级存储器中的页
  2. 交换空间(磁盘或者文件)

后备存储可以有哪些?

  1. 一个虚拟地址空间的页:可以被映射到一个文件的某个位置
  2. 代码段:可以映射到可执行的二进制文件
  3. 动态共享程序段:映射到动态调用的库文件
  4. 其他段:映射到交换文件中

虚拟内存性能

有效存储访问时间(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 页面置换算法

缺页几率,是严重影响虚拟内存效率的一个因素,而缺页几率与页面置换算法息息相关。

功能:当缺页中断发生,需要加载新的帧页到内存,但当应用内存已满时,需要选择淘汰物理内存中的帧来给新的帧资源。

目标:尽可能的减少页面换进换出次数。
对于常驻内存(如操作系统或其他关键应用)添加锁定标志位,避免换出。

分类:分为局部页面置换和全局页面置换两大类

  • 局部页面置换:
    1. 最优页面置换算法(OPT)(最晚重用被淘汰)(理想状态,无法实现,可为依据)
    2. 先进先出算法(FIFO)(存活久的被淘汰)(利用链表即可实现,最差情况下性能较差)
    3. 最近最久未使用算法(LRU)(最久没用被淘汰)(链表、堆栈可实现,但开销较大)
    4. 时钟页面置换算法(Clock)(利用FIFO优化的LRU)(环形链表选最老)
    5. 二次机会法(??)(Clock脏页版)(两条命的命中高,有了脏位换出少)
    6. 最不常用算法(LFU)(有的最少被抛弃)(表中加个计数器)
  • 全局页面置换:
    1. 工作集页面置换算法(??)(利用工作集的LRU)(无须缺页就淘汰,利用时刻来换出)
    2. 缺页率页面置换算法(PFF)(动态改变常驻集的工作集算法)(根据缺页频率,淘汰多个页面)

4.5.1 最优页面置换算法(OPT)

基本思路:当一个缺页中断发生,需要进行页面置换时,对于当前内存中的每一个逻辑页面,计算它下一次被访问时还需等待的时间,从中选择等待时间最长的页面,作为置换页。

评价:该算法无法实现或者说很难实现,因为OS无法预知每个页面下次访问需要的等待时间,但该算法可以作为其他算法评定的依据。

例图:
image

4.5.2 先进先出算法(FIFO)

基本思路:对于当前内存中的每一个逻辑页面,计算它载入内存的时间,从中选择驻留时间最长的页面,作为置换页。

评价:利用链表实现,载入向链尾加,换出删除链表头即可。

例图:
image

4.5.3 最近最久未使用算法(LRU)

基本思路:选择最久未被使用的帧页,作为置换页。

评价:时间轴上与最优算法相反,符合局部性原理。在最近一段区间内,找到最久未使用的帧。对于记录各页面调用的先后顺序,开销较大,可以利用链表或堆栈实现。

例图:
image

4.5.4 时钟页面置换算法(Clock)

基本思路:与LRU相似,是FIFO的一种改进。是二者之间的一种平衡。实现是在页面中加入一个访问位,一个页面载入时,由硬件初始化为0(软件也可以),如果页面被访问,则相应页表项置为1。将各页表项组成一个环形链表,发生缺页中断时,指针循环判断环形链表,若判断的页表项为0,选为置换页,置换并访问新页后,新页表项置为1,指针下移;若判断的页表项为1,则改为0,指针下移。

image

评价:时间轴上与最优算法相反,符合局部性原理。在最近一段区间内,找到最久未使用的帧。对于记录各页面调用的先后顺序,开销较大,可以利用链表或堆栈实现。

例图:
image

4.5.5 二次机会法()

基本思路:对Clock算法的一个改进,优化Clock算法对修改页面的写入逻辑,引入新位dirty bit(脏位)来标识内存修改过与虚存不一致。对于脏位为0的页面,不必进行同步回虚存的一步。而对于脏位为1的页面,多了一次存活机会,与访问位用法一样。

image

评价:优化Clock算法的换出效率,并利用两个标识位拥有两条命,来增加存活率,加大命中次数。

例图:
image

4.5.6 最不常用算法(LFU)

基本思路:选择访问次数最少的页为置换页。所以要维护一张表,对每个页都有个访问计数器。

评价:LRU关注访问过去时间,久的淘汰;LFU关注访问次数,少的淘汰。

4.5.7 局部页面置换算法总结:

Belady现象:

Belady(笔勒滴,一个科学家名)在采用FIFO算法时,有时会出现分配的物理页面数增加,缺页率反而提高(命中率反而下降)的反常现象。

例图:
image
image

解决: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实际驻留在内存中(物理页面)的页面集合。(某时刻访问的页面集合)
常驻集 <= 工作集。

缺页率:“缺页次数” / “内存访问次数”,影响因素:

  1. 页面置换算法
  2. 分配的物理页帧数(常驻集大小)
  3. 页面本身大小
  4. 编写的程序(是否符合局部性)

4.5.9 工作集页面置换算法

基本思路:类似LRU最久未用被淘汰,但不同的是触发事件不同,当时刻改变时(而非缺页时)就会清理物理页面,准备物理页帧。

例图:
image

4.5.10 缺页率页面置换算法(PFF)

基本思路:在工作集页面置换算法基础上,动态改变时刻窗口(△)大小,即常驻集大小。当缺页率上升时,提高常驻集大小,反之减少。(淘汰的触发时间是缺页时,一次可能淘汰多个页面)

评价:性能好,开销大。

例图:
image

4.5.11 抖动问题

什么是抖动?
当分配的常驻集小于工作集,使进程产生很多缺页中断,频繁进行换进换出,从而使运行速度变慢的现象叫做抖动问题。

产生原因?
随着驻留内存中应用的增加,分配给每个应用的物理页帧(常驻集)持续减少,缺页率随之提高。所以OS要选择运行适当的进程数量,及每个进程所需页帧数,使并发水平和缺页率达到一定平衡。

五、进程管理

5.1 进程描述(静)

5.1.1 进程的定义

一个具有一定独立功能的程序在一个数据集合上的一次动态执行。(将程序加载到内存并运行的过程)

5.1.2 进程的组成

  1. 程序代码
  2. 程序处理的数据
  3. 运行指令的计数器
  4. 一组通用的寄存器中保存的当前值,堆、栈、、、
  5. 一组系统资源(打开的文件,连接的服务)

5.1.3 程序和进程的关系

  1. 程序是产生进程的基础。(程序是永久的,是类模板;进程是临时的,是实例)
  2. 进程是程序运行的体现。(程序是静态的、进程是动态的)
  3. 每次运行相同程序会产生不同的进程。(进程号,输入数据,启动时间)
  4. 程序的一次运行可能产生多个进程。(相互依赖和调用)
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实现进程管理

image

5.3 线程(Thread)

轻量版的进程,也可以并发执行,并且共享相同的地址空间,以此实现通信和交互。

5.3.1 什么是线程

线程是进程中的一条执行流程。
抽象一下,进程只管理资源和线程,线程是进程的执行流程,负责应用的执行逻辑。

5.3.2 线程的优缺点

线程的优点

  • 线程让进程的数据与业务分离
  • 一个进程可以同时存在多个线程
  • 线程也可以并发执行
  • 各线程可以共享地址空间和资源

线程的缺点

  • 一个线程的崩溃会导致所属进程的崩溃。

5.3.3 进程和线程的比较

进程 线程
资源分配单位 CPU调度单位
独享完整的资源平台 只独享寄存器和运行栈
具有状态和转换 具有状态和转换
并发执行时间和空间开销多 开销少

5.3.4 线程的实现

  • 用户线程:在用户空间实现;(用户级线程库来管理)
  • 内核线程:在内核空间实现;(OS内核感知和管理)
  • 轻量级进程:在内核空间实现;

六、CPU调度算法

从就绪队列中选择一个进程/线程,在之后可以获得CPU资源。

6.1 调度条件

  1. 进程的状态从运行切换到等待
  2. 一个进程被终止了

6.2 调度原则

基本概念

  1. CPU使用率:CPU处于忙状态所占时间的百分比
  2. 吞吐量:在单位时间内完成的进程数量
  3. 周转时间:一个进程从初始化到结束所需时间(包括等待时间)
  4. 等待时间:进程在就绪队列中的总时间(就绪到运行状态所需时间)
  5. 响应时间:进程从提交到第一次响应所花费的时间

“更快”的服务

更快 = 高带宽(吞吐量) + 低延迟(响应时间)

目标

  1. 减少等待时间
  2. 减少响应时间
  3. 减少平均响应时间的波动,越平稳越好
  4. 增加吞吐量

6.3 调度算法

  1. 先来先服务算法(FCFS)()()
  2. 短进程优先(SPN)()()
  3. 短作业优先(SJF)(Shortest Job First)(同SPN)
  4. 短剩余时间优先(SRT)(Shortest Remaining Time)(同SPN)
  5. 最高响应比优先(HRRN)()()
  6. 时间片轮循(Round Robin)()()
  7. 多级反馈队列(Multilevel Feedback Queues)()()
  8. 公平共享调度(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)