【清华大学】操作系统全集公开课

  • 名称:【清华大学】操作系统全集公
  • 分类:操作系统  
  • 观看人数:加载中
  • 时间:2022/10/6 20:00:03

1 冯诺伊曼体系

1.1 冯诺伊曼体系简介

现代计算机之父冯诺伊曼最先提出程序存储的思想,并成功将其运用在计算机的设计之中,该思想约定了用二进制进行计算和存储,还定义计算机基本结构为 5 个部分,分别是中央处理器(CPU)、内存、输入设备、输出设备、总线。

存储器:代码跟数据在RAM跟ROM中是线性存储, 数据存储的单位是一个二进制位。最小的存储单位是字节。

总线:总线是用于 CPU 和内存以及其他设备之间的通信,总线主要有三种:

地址总线:用于指定 CPU 将要操作的内存地址。

数据总线:用于读写内存的数据。

控制总线:用于发送和接收信号,比如中断、设备复位等信号,CPU 收到信号后响应,这时也需要控制总线。

输入/输出设备:输入设备向计算机输入数据,计算机经过计算后,把数据输出给输出设备。比如键盘按键时需要和 CPU 进行交互,这时就需要用到控制总线。

CPU:中央处理器,类比人脑,作为计算机系统的运算和控制核心,是信息处理、程序运行的最终执行单元。CPU用寄存器存储计算时所需数据,寄存器一般有三种:

通用寄存器:用来存放需要进行运算的数据,比如需进行加法运算的两个数据。

程序计数器:用来存储 CPU 要执行下一条指令所在的内存地址。

指令寄存器:用来存放程序计数器指向的指令本身。

在冯诺伊曼体系下电脑指令执行的过程:

CPU读取程序计数器获得指令内存地址,CPU控制单元操作地址总线从内存地址拿到数据,数据通过数据总线到达CPU被存入指令寄存器。

CPU分析指令寄存器中的指令,如果是计算类型的指令交给逻辑运算单元,如果是存储类型的指令交给控制单元执行。

CPU 执行完指令后程序计数器的值通过自增指向下个指令,比如32位CPU会自增4。

自增后开始顺序执行下一条指令,不断循环执行直到程序结束。

CPU位宽:32位CPU一次可操作计算4个字节,64位CPU一次可操作计算8个字节,这个是硬件级别的。平常我们说的32位或64位操作系统指的是软件级别的,指的是程序中指令多少位。

线路位宽:CPU操作指令数据通过高低电压变化进行数据传输,传输时候可以串行传输,也可以并行传输,多少个并行等于多少个位宽。

1.2 CPU 简介

Central Processing Unit 中央处理器,作为计算机系统的运算和控制核心,是信息处理、程序运行的最终执行单元。

CPU

CPU核心:一般一个CPU会有多个CPU核心,平常说的多核是指在一枚处理器中集成两个或多个完整的计算引擎。核跟CPU的关系是:核属于CPU的一部分。

寄存器:最靠近CPU对存储单元,32位CPU寄存器可存储4字节,64位寄存器可存储8字节。寄存器访问速度一般是半个CPU时钟周期,属于纳秒级别,

L1缓存:每个CPU核心都有,用来缓存数据跟指令,访问空间大小一般在32~256KB,访问速度一般是2~4个CPU时钟周期。

cat /sys/devices/system/cpu/cpu0/cache/index0/size # L1 数据缓存

cat /sys/devices/system/cpu/cpu0/cache/index1/size # L1 指令缓存

L2缓存:每个CPU核心都有,访问空间大小在128KB~2MB,访问速度一般是10~20个CPU时钟周期。

cat /sys/devices/system/cpu/cpu0/cache/index2/size # L2 缓存容量大小

L3缓存:多个CPU核心共用,访问空间大小在2MB~64MB,访问速度一般是20~60个CPU时钟周期。

cat /sys/devices/system/cpu/cpu0/cache/index3/size # L3 缓存容量大小

内存:多个CPU共用,现在一般是4G~512G,访问速度一般是200~300个CPU时钟周期。

固体硬盘SSD:现在台式机主流都会配备,上述的寄存器、缓存、内存都是断电数据立马丢失的,而SSD里不会丢失,大小一般是128G~1T,比内存慢10~1000倍。

机械盘HDD:很早以前流行的硬盘了,容量可在512G~8T不等,访问速度比内存慢10W倍不等。

访问数据顺序:CPU在拿数据处理的时候几乎也是按照上面说得流程来操纵的,只有上面一层找不到才会找下一层。

Cache Line :  CPU读取数据时会按照 Cache Line 方式把数据加载到缓存中,每个Cacheline = 64KB,因为L1、L2是每个核独有到可能会触发伪共享,就是 所以可能会将数据划分到不同到CacheLine中来避免伪共享,比如在JDK8 新增加的 LongAdder 就涉及到此知识点。

伪共享:缓存系统中是以缓存行(cache line)为单位存储的,当多线程修改互相独立的变量时,如果这些变量共享同一个缓存行,就会无意中影响彼此的性能,这就是伪共享。

JMM: 数据经过种种分层会导致访问速度在不断提升,同时也带来了各种问题,多个CPU同时操作相同数据可能会造成各种BU个,需要加锁,这里在JUC并发已详细探讨过。

1.3 CPU 访问方式

CPU访问方式

内存数据映射到CPU Cache 时通过公式Block N % CacheLineMax决定内存Block数据放到那个CPU Cache Line 里。CPU Cache 主要有4部分组成。

Cache Line Index :CPU缓存读取数据时不是按照字节来读取的,而是按照CacheLine方式存储跟读取数据的。

Valid Bit : 有效位标志符,值为0时表示无论 CPU Line 中是否有数据,CPU 都会直接访问内存,重新加载数据。

Tag:组标记,用来标记内存中不同BLock映射到相同CacheLine,用Tag来区分不同的内存Block。

Data:真实到内存数据信息。

CPU真实访问内存数据时只需要指定三个部分即可。

Cache Line Index :要访问到Cache Line 位置。

Tag:表示用那个数据块。

Offset:CPU从CPU Cache 读取数据时不是直接读取Cache Line整个数据块,而是读取CPU所需的数据片段,称为Word。如何找到Word就需要个偏移量Offset。

1.4 CPU 访问速度

访问耗时对比

如上图所示,CPU访问速度是逐步变慢,所以CPU访问数据时需尽量在距离CPU近的高速缓存区访问,根据摩尔定律CPU访问速度每18个月就会翻倍,而内存的访问每18个月也就增长10% 左右,导致的结果就是CPU跟内存访问性能差距逐步变大,那如何尽可能提高CPU缓存命中率呢?

1. 数据缓存:遍历数据时候按照内存布局顺序访问,因为CPU Cache是根据Cache Line批量操作数据的,所以你顺序读取数据会提速,道理跟磁盘顺序写一样。

指令缓存:尽可能的提供有规律的条件分支语句,让 CPU 的分支预测器发挥作用,进一步提高执行的效率,因为CPU是自带分支预测器,自动提前将可能需要的指令放到指令缓存区。

线程绑定到CPU:一个任务A在前一个时间片用CPU核心1 运行,后一个时间片用CPU核心2 运行,这样缓存L1、L2就浪费了。因此操作系统提供了将进程或者线程绑定到某一颗 CPU 上运行的能力。如 Linux 上提供了 sched_setaffinity 方法实现这一功能,其他操作系统也有类似功能的 API 可用。当多线程同时执行密集计算,且 CPU 缓存命中率很高时,如果将每个线程分别绑定在不同的 CPU 核心上,性能便会获得非常可观的提升。

1.5  操作系统

计算机结构

有了冯诺伊曼计算机体系后,电脑想要为用户提供便捷的服务还需要安装个操作系统Operation System,操作系统是覆盖在硬件上的一层特殊软件,它管理计算机的硬件和软件资源,为其他应用程序提供大量服务。可以理解为操作系统是日常应用程序跟硬件之间的接口。日常你经常在用Windows/Linux 系统,操作系统给我们提供了超级大的便利,但是你了解操作系统么?操作系统是如何进行内存管理、进程管理、文件管理、输入输出管理的呢?

2 内存管理

你的电脑是32位操作系统,那可支持的最大内存就是4G,你有没有好奇为什么可以同时运行2个以上的2G内存的程序。应用程序不是直接使用的物理地址,操作系统为每个运行的进程分配了一套虚拟地址,每个进程都有自己的虚拟内存地址,进程是无法直接进行物理内存地址的访问的。至于虚拟地址跟物理地址的映射,进程是感知不到的!操作系统自身会提供一套机制将不同进程的虚拟地址和不同内存的物理地址进行映射。

虚拟内存

2.1  MMU

Memory Management Unit 内存管理单元是一种负责处理CPU内存访问请求的计算机硬件。它的功能包括虚拟地址到物理地址的转换、内存保护、中央处理器高速缓存的控制。现代 CPU 基本上都选择了使用 MMU。

当进程持有虚拟内存地址的时候,CPU执行该进程时会操作虚拟内存,而MMU会自动的将虚拟内存的操作映射到物理内存上。

MMU

这里提一下,Java操作的时候你看到的地址是JVM地址,不是真正的物理地址。

2.2  内存管理方式

操作系统主要采用内存分段和内存分页来管理虚拟地址与物理地址之间的关系,其中分段是很早前的方法了,现在大部分用的是分页,不过分页也不是完全的分页,是在分段的基础上再分页。

2.2.1 内存分段

JVM内存模型

我们以上图的JVM内存模型举例,程序员会认为我们的代码是由代码段、数据段、栈段、堆段组成。不同的段是有不同的属性的,用户并不关心这些元素所在内存的位置,而分段就是支持这种用户视图的内存管理方案。逻辑地址空间是由一组段构成。每个段都有名称和长度。地址指定了段名称和段内偏移。因此用户段编号和段偏移来指定不同属性的地址。而虚拟内存地址跟物理内存地址中间是通过段表进行映射的,口说无凭,看图吧。

内存分段管理

如上虚拟地址有 5 个段,各段按如图所示来存储。每个段都在段表中有一个条目,它包括段在物理内存内的开始的基地址和该段的界限长度。例如段 2 为 400 字节长,开始于位置 4300。因此对段 2 字节 53 的引用映射成位置 4300 + 53 = 4353。对段 3 字节 852 的引用映射成位置 3200 + 852 = 4052。

分段映射很简单,但是会导致内存碎片跟内存交互效率低。这里先普及下在内存管理中主要有内部内存碎片跟外部内存碎片。

内部碎片:已经被分配出去的的内存空间不经常使用,并且分配出去的内存空间大于请求所需的内存空间。

外部碎片:指可用空间还没有分配出去,但是可用空间由于大小太小而无法分配给申请空间的新进程的内存空间空闲块。

以上图为例,现在系统空闲是1400 +  800 + 600 = 2800。那如果有个程序想要连续的使用2000,内存分段模式下提供不了啊!上述三个是外部内存碎片。当然可以使用系统的Swap空间,先把段0写入到磁盘,然后再重新给段0分配空间。这样可以实现最终可用,可是但凡涉及到磁盘读写就会导致内存交互效率低。

swap空间利用

2.2.2 内存分页

内存分页,整个虚拟内存和物理内存切成一段段固定尺寸的大小。每个固定大小的尺寸称之为页Page,在 Linux 系统中Page = 4KB。然后虚拟内存跟物理内存之间通过页表来实现映射。

采用内存分页时内存的释放跟使用都是以页为单位的,也就不会产生内存碎片了。当空间还不够时根据操作系统调度算法,可能将最少用的内存页面 swap-out换出到磁盘,用时候再swap-in换入,尽可能的减少磁盘刷写量,提高内存交互效率。

分页模式下虚拟地址主要有页号跟页内偏移量两部分组成。通过页号查询页表找到物理内存地址,然后再配合页内偏移量就找到了真正的物理内存地址。

分页内存寻址

32位操作系统环境下进程可操作的虚拟地址是4GB,假设一个虚拟页大小为4KB,那需要4GB/4KB = 2^20 个页信息。一行页表记录为4字节,2^20等价于4MB页表存储信息。这只是一个进程需要的,如果10个、100个、1000个呢?仅仅是页表存储都占据超大内存了。

为了解决这个问题就需要用到 多级页表,核心思想就是局部性分配。在32位的操作系统中将将4G空间分为 1024 行页目录项目(4KB),每个页目录项又对应1024行页表项。如下图所示:

32位系统二级分页

控制寄存器cr3中存放了页目录的物理地址,通过cr3寄存器可以找到页目录,而32位线性地址中的Directory部分决定页目录中的目录项,而页目录项中存放了要找的页表的物理基地址,再结合线性地址中的中间10位页表项,就可以找到页框的页表项。线性地址中的Offset部分占12位,因此页框的物理地址 + 线性地址Offset部分 = 页框中的任何一个字节。

分页后一级页就等价于4G虚拟地址空间,并且如果一级页表中那些地址没有就不需要再创建二级页表了!核心思想就是按需创建,当系统给每个进程分配4G空间,进程不可能占据全部内存的,如果一级目录页只有10%用到了,此时页表空间 = 一级页表4KB + 0.1 * 4MB  。这比单独的每个进程占据4M好用多了!

多层分页的弊端就是访问时间的增加。

使用页表时读取内存中一页内容需要2次访问内存,访问页表项 + 并读取的一页数据。

使用二级页表的话需要三次访问,访问页目录项 + 访问页表项 + 访问并读取的一页数据。访存次数的增加也就意味着访问数据所花费的总时间增加。

而对于64位系统,二级分页就无法满足了,Linux 从2.6.11开始采用四级分页模型。

Page Global Directory 全局页目录项

Page Upper Directory 上层页目录项

Page Middle Directory 中间页目录项

Page Table Entry 页表项

Offset 偏移量。

64位寻址

2.2.2 TLB

Translation Lookaside Buffer 可翻译为地址转换后援缓冲器,简称为快表,属于CPU内部的一个模块,TLB是MMU的一部分,实质是cache,它所缓存的是最近使用的数据的页表项(虚拟地址到物理地址的映射)。他的出现是为了加快访问数据(内存)的速度,减少重复的页表查找。当然它不是必须要有的,但有它,速度就更快。

TLB

TLB很小,因此缓存的东西也不多。主要缓存最近使用的数据的数据映射。TLB结构如下图:

TLB查询

如果一个需要访问内存中的一个数据,给定这个数据的虚拟地址,查询TLB,发现有hit,直接得到物理地址,在内存根据物理地址取数据。如果TLB没有这个虚拟地址miss,那么只能费力的通过页表来查找了。日常CPU读取一个数据的流程如下:

CPU读取数据流程图

当进程地址空间进行了上下文切换时,比如现在是进程1运行,TLB中放的是进程1的相关数据的地址,突然切换到进程2,TLB中原有的数据不是进程2相关的,此时TLB刷新数据有两种办法。

全部刷新:很简单,但花销大,很多不必刷新的数据也进行刷新,增加了无畏的花销。

部分刷新:根据标志位,刷新需要刷新的数据,保留不需要刷新的数据。

2.2.3 段页式管理

内存分段跟内存分页不是对立的,这俩可以组合起来在同一个系统中使用的,那么组合起来后通常称为段页式内存管理。段页式内存管理实现的方式:

先对数据不同划分出不同的段,也就是前面说的分段机制。

然后再把每一个段进行分页操作,也就是前面说的分页机制。

此时 地址结构 = 段号 + 段内页号 + 页内位移。

每一个进程有一张段表,每个段又建立一张页表,段表中的地址是页表的起始地址,而页表中的地址则为某页的物理页号。

段页式管理

同时我们经常看到两个专业词逻辑地址跟线性地址。

逻辑地址:指的是没被段式内存管理映射的地址。

线性地址:通过段式内存管理映射且页式内存管理转换前的地址,俗称虚拟地址。

目前 Intel X86 CPU 采用的是内存分段 +  内存分页的管理方式,其中分页的意思是在由段式内存管理所映射而成的的地址上再加上一层地址映射。

X86内存管理方式

2.2.4 Linux 内存管理

先说结论:Linux系统基于X86 CPU 而做的操作系统,所以也是用的段页式内存管理方式。

我们知道32位的操作系统可寻址范围是4G,操作系统会将4G的可访问内存空间分为用户空间跟内核空间。

内核空间:操作系统内核访问的区域,独立于普通的应用程序,是受保护的内存空间。内核态下CPU可执行任何指令,可自由访问任何有效地址。

用户空间:普通应用程序可访问的内存区域。被执行代码会受到CPU众多限制,进程只能访问映射其地址空间的页表项中规定的在用户态下可访问页面的虚拟地址。

那为啥要搞俩空间呢?现在嵌入式环境跟以前的WIN98系统是没有区分俩空间的,须知俩空间是CPU分的,而操作系统是在上面运行的,单一用户、单一任务服务的操作系统,是没有分所谓用户态和内核态的必要。用户态和内核态是因为有多用户,多任务的需求,然后在CPU硬件厂商配合之后,产生的一个操作系统解决多用户多任务需求的方案。方案就是限制,通过硬件手段(也只能硬件手段才能做到),限制某些代码,使其无法控制整个物理硬件,进而使各个不同用户,不同任务的代码,无权修改整个物理硬件,再进而保护操作系统的核心底层代码和其他用户的数据不被无意或者有意地破坏和盗取。

后来研究者根据CPU的运行级别,分成了Ring0~Ring3四个级别。Ring0是最高级别,Ring1次之,Rng2更次之,拿Linux+x86来说,  操作系统内核的代码运行在最高运行级别Ring0上,可以使用特权指令,控制中断、修改页表、访问设备等。 应用程序的代码运行在最低运行级别上Ring3上,不能做受控操作,只能访问用户被分配的空间。如果要做访问磁盘跟写文件等操作,那就要通过执行系统调用函数,执行系统调用的时候,CPU的运行级别会发生从Ring3到Ring0的切换,并跳转到系统调用对应的内核代码位置执行,这样内核就为你完成了设备访问,完成之后再从Ring0返回Ring3。这个过程也称作用户态和内核态的切换。

用户态想要使用计算机设备或IO需通过系统调用完成sys call,系统调用就是让内核来做这些操作。而系统调用是影响整个当前进程上下文的,CPU提供了个软中断来是实现保护线程,获取系统调用号跟参数,交给内核对应系统调用函数执行。

Linux系统结构

可以看到每个应用程序都各自有独立的虚拟内存地址,但每个虚拟内存中对应的内核地址其实是相同的一大块,这样当进程切换到内核态后可以很方便地访问内核空间内存。比如Java代码创建线程new Thread调用start方法后跟踪JVM源码你会发现是调用pthread_create来创建线程的,这就涉及到了用户态到内核态的切换。

3 进程管理

3.1 进程基础知识

进程是程序的一次执行,是一个程序及其数据在机器上顺序执行时所发生的活动,是具有独立功能的程序在一个数据集合上的一次运行过程,是系统进行资源分配和调度的一个基本单位。进程的调度状态如下:

状态变化图

重点说下挂起跟阻塞:

阻塞一般是当系统执行IO操作时,此时进程进入阻塞状态,等待某个事件的返回。

挂起是指进程没有占有物理内存,被写到磁盘上了。这时进程状态是挂起状态。

阻塞挂起:进程被写入硬盘并等待某个事件的出现。

就绪挂起:进程被写入硬盘,进入内存可直接进入就绪状态。

3.2 PCB

为了描述跟控制进程的运行,系统为每个进程定义了一个数据结构——进程控制块 Process Control Block,它是进程实体的一部分,是操作系统中最重要的记录型数据结构。

PCB 的作用是使一个在多道程序环境下不能独立运行的程序,成为一个能独立运行的基本单位,一个能与其它进程并发执行的进程 :

作为独立运行基本单位的标志

实现间断性的运行方式

提供进程管理所需要的信息

提供进程调度所需要的信息

实现与其他进程的同步与通信

3.2.1 PCB 信息

PCB为实现上述功能,内部包含众多信息:

进程标识符:用于唯一地标识一个进程,一个进程通常有两种标识符:

内部进程标识符:标识各个进程,每个进程都有一个并且唯一的标识符,设置内部标识符主要是为了方便系统使用。

外部进程标识符:它由创建者提供,可设置用户标识,以指示拥有该进程的用户。往往是由用户进程在访问该进程时使用。一般为了描述进程的家族关系,还应设置父进程标识及子进程标识。

处理机状态:由各种寄存器组成。包含许多信息都放在寄存器中,方便程序restart。

通用寄存器、指令计数器、程序状态字PSW、用户栈指针等信息。

进程调度信息

进程状态:指明进程的当前状态,作为进程调度和对换时的依据。

进程优先级:用于描述进程使用处理机的优先级别的一个整数,优先级高的进程应优先获得处理机

进程调度所需的其它信息:与所采用的进程调度算法有关,如进程已等待CPU的时间总和、进程已执行的时间总和等。

事件:指进程由执行状态转变为阻塞状态所等待发生的事件,即阻塞原因。

资源清单

有关内存地址空间或虚拟地址空间的信息,所打开文件的列表和所使用的 I/O 设备信息。

3.2.2 PCB 组织方式

操作系统中有太多 PCB,如何管理是个问题,一般有如下方式。

线下数组

线性方式:

将系统所有PCB都组织在一张线性表中,将该表首地址存在内存的一个专用区域

实现简单,开销小,但是每次都需要扫描整张表,适合进程数目不多的系统

索引方式

索引方式:

将同一状态的进程组织在一个索引表中,索引表项指向相应的 PCB,不同状态对应不同的索引表。

链表方式

链接方式:

把同一状态的PCB链接成一个队列,形成就绪队列、阻塞队列、空白队列等。对其中的就绪队列常按进程优先级的高低排列,优先级高排在队前。

因为进程创建、销毁、调度频繁,所以一般采用此模式。

3.3 进程控制

进程控制是进程管理最基本的功能,主要包括创建新进程,终止已完成的进程,将发生异常的进程置于阻塞状态,将进程唤醒等。

3.3.1 进程创建

父进程可创建子进程,父进程终止后子进程也会被终止。子进程可继承父进程所有资源,子进程终止需将自己所继承的资源归还父进程。接下来看下创建的大致流程。

为新进程分配唯一进件标识号,然后创建一个空白PCB,需注意PCB数量是有限的,所以可能会创建失败。

尝试为新进程分配所需资源,如果资源不足进程会进入等待状态。

初始化PCB,有如下几个操作。

标识信息:将系统分配的标识符和父进程标识符填入新PCB

处理机状态信息:使程序计数器指向程序入口地址,使栈指针指向栈顶

处理机控制信息:将进程设为就绪/静止状态,通常设为最低优先级

如果进程调度队列能接纳新进程,就将进程插入到就绪队列,等待被调度运行。

3.3.2 进程终止

进程终止情况一般分为正常结束、异常结束、外界干预三种。

正常结束

异常结束

越界错:访问的存储区越出该进程的区域

保护错:试图访问不允许访问的资源,或以不适当的方式访问(写只读)

非法指令:试图执行不存在的指令(可能是程序错误地转移到数据区,数据当成了指令)

特权指令出错:用户进程试图执行一条只允许OS执行的指令

运行超时:执行时间超过指定的最大值

等待超时:进程等待某件事超过指定的最大值

算数运算错:试图执行被禁止的运算(被0除)

I/O故障

外界干预

操作员或OS干预(死锁)

父进程请求,子进程完成父进程指定的任务时

父进程终止,所有子进程都应该结束

终止过程:

根据被终止进程的标识符,从PCB集合中检索出该PCB,读取进程状态

若处于执行状态则立即终止执行,将CPU资源分配给其他进程。

若进程有子孙进程则将其所有子孙进程终止。

全部资源还给父进程或操作系统。

该进程的PCB从所在队列/链表中移出。

3.3.3 进程阻塞

意思是该进程执行半路被阻塞,必须由某个事件进程唤醒该进程。常见的就是IO读取操作。常见阻塞时机/事件如下:

请求共享资源失败,系统无足够资源分配

等待某种操作完成

新数据尚未到达(相互合作的进程)

等待新任务

阻塞流程:

找到要被阻塞进程标识号对应的 PCB。

将该进程由运行状态转换为阻塞状态。

将该 进程PCB 插入的阻塞队列中去。

3.3.4 进程唤醒

唤醒 原语 wake up,一般和阻塞成对使用。唤醒过程如下:

从阻塞队列找到所需PCB。

PCB从阻塞队列溢出,然后变为就绪状态。

从阻塞队列溢出该PCB然后插入到就绪状态队列等待被分配CPU资源。

3.4 进程调度

进程数一般会大于CPU个数,进程状态切换主要由调度程序进行调度。一般情况下CPU调度时主要分为抢占式调度跟非抢占式调度。

非抢占式:让进程运行直到结束或阻塞的调度方式, 容易实现,适合专用系统。

抢占式:每个进程获得时间片才可以被CPU调度运行, 可防止单一进程长时间独占CPU 系统开销大。

3.4.1 进程调度原则

CPU 利用率

CPU利用率 = 忙碌时间 / 总时间。

调度程序应该尽量让 CPU 始终处于忙碌的状态,这可提高 CPU 的利用率。比如当发生IO读取时候,不要傻傻等待,去执行下别的进程。

系统吞吐量

系统吞吐量 = 总共完成多少个作业 / 总共花费时间。

长作业的进程会占用较长的 CPU 资源导致降低吞吐量,相反短作业的进程会提升系统吞吐量。

周转时间

周转时间 = 作业完成时间 - 作业提交时间。

平均周转时间 = 各作业周转时间和 / 作业数

带权周转时间 = 作业周转时间 / 作业实际运行时间

平均带权周转时间 = 各作业带权周转时间之和 / 作业数

尽可能使周转时间降低。

等待时间

指的是进程在等待队列中等待的时间,一般也需要尽可能短。

响应时间

响应时间 = 系统第一次响应时间 - 用户提交时间,在交互式系统中响应时间是衡量调度算法好坏的主要标准。

3.4.2 调度算法

FCFS 算法

First Come First Severd 先来先服务算法,遵循先来后端原则,每次从就绪队列拿等待时间最久的,运行完毕后再拿下一个。

该模式对长作业有利,适用 CPU 繁忙型作业的系统,不适用 I/O 型作业,因为会导致进程CPU利用率很低。

SJF 算法

Shortest Job First 最短作业优先算法,该算法会优先选择运行所需时间最短的进程执行,可提高吞吐量。

跟FCFS正好相反,对长作业很不利。

SRTN 算法

Shortest Remaining Time Next 最短剩余时间优先算法,可以认为是SJF的抢占式版本,当一个新就绪的进程比当前运行进程具有更短完成时间时,系统抢占当前进程,选择新就绪的进程执行。

有最短的平均周转时间,但不公平,源源不断的短任务到来,可能使长的任务长时间得不到运行。

HRRN 算法

Highest Response Ratio Next 最高响应比优先算法,为了平衡前面俩而生,按照响应优先权从高到低依次执行。属于前面俩的折中权衡。

优先权 = (等待时间 + 要求服务时间) / 要求服务时间

RR 算法

Round Robin 时间片轮转算法,操作系统设定了个时间片Quantum,时间片导致每个进程只有在该时间片内才可以运行,这种方式导致每个进程都会均匀的获得执行权。

时间片一般20ms~50ms,如果太小会导致系统频繁进行上下文切换,太大又可能引起对短的交互请求的响应变差。

HPF 算法

Highest Priority First 最高优先级调度算法,从就绪队列中选择最高优先级的进程先执行。

优先级的设置有初始化固定死的那种,也有在代码运转过程中根据等待时间或性能动态调整 这两种思路。

缺点是可能导致低优先级的一直无法被执行。

MFQ 算法

Multilevel Feedback Queue 多级反馈队列调度算法 ,可以认为是 RR 算法 跟 HPF 算法 的综合体。

系统会同时存在多个就绪队列,每个队列优先级从高到低排列,同时优先级越高获得是时间片越短。

新进程会先加入到最高优先级队列,如果新进程优先级高于当前在执行的进程,会停止当前进程转而去执行新进程。新进程如果在时间片内没执行完毕需下移到次优先级队列。

多级反馈队列调度算法

3.5 线程

3.5.1 线程定义

早期操作系统是没有线程概念的,线程是后来加进来的。为啥会有线程呢?那是因为以前在多进程阶段,经常会涉及到进程之间如何通讯,如何共享数据的问题。并且进程关联到PCB的生命周期,管理起来开销较大。为了解决这个问题引入了线程。

线程是进程当中的一个执行流程。同一个进程内的多个线程之间可以共享进程的代码段、数据段、打开的文件等资源。同时每个线程又都有一套独立的寄存器和栈来确保线程的控制流是独立的。

进程有个PCB来管理,同理操作系统通过 Thread Control Block线程控制块来实现线程的管控。

3.5.2 线程优缺点

优点

一个进程中可以同时存在1~N个线程,这些线程可以并发的执行。

各个线程之间可以共享地址空间和文件等资源。

缺点

当进程中的一个线程奔溃时,会导致其所属进程的所有线程奔溃。

多线程编程,让人头大的东西。

线程执行开销小,但不利于资源的隔离管理和保护,而进程正相反。

3.5.3 进程跟线程关联

进程:

是系统进行资源分配和调度的一个独立单位.

是程序的一次执行,每个进程都有自己的地址空间、内存、数据栈及其他辅助记录运行轨迹的数据

线程:

是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位

所有的线程运行在同一个进程中,共享相同的运行资源和环境

线程一般是并发执行的,使得实现了多任务的并行和数据共享。

进程线程区别:

一个线程只能属于一个进程,而一个进程可以有多个线程,但至少有一个线程。

线程的划分尺度小于进程(资源比进程少),使得多线程程序的并发性高。

进程在执行过程中拥有独立的内存单元,而多个线程共享内存,从而极大地提高了程序的运行效率。

资源分配给进程,同一进程的所有线程共享该进程的所有资源。

CPU分配资源给进程,但真正在CPU上运行的是线程。

线程不能够独立执行,必须依存在进程中。

线程快在哪儿?

线程创建的时有些资源不需要自己管理,直接从进程拿即可,线程管理寄存器跟栈的生命周期即可。

同进程内多线程共享数据,所以进程数据传输可以用zero copy技术,不需要经过内核了。

进程使用一个虚拟内存跟页表,然后多线程共用这些虚拟内存,如果同进程内两个线程进行上下文切换比进程提速很多。

3.5.4 线程实现

在前面的内存管理中说到了内核态跟用户态。相对应的线程的创建也分为用户态线程跟内核态线程。

3.5.4.1 用户态线程

在用户空间实现的线程,由用户态的线程库来完成线程的管理。操作系统按进程维度进行调度,当线程在用户态创建时应用程序在用户空间内要实现线程的创建、维护和调度。操作系统对线程的存在一无所知!操作系统只能看到进程看不到线程。所有的线程都是在用户空间实现。在操作系统看来,每一个进程只有一个线程。