正在播放：【清华大学】操作系统原理全集公开课

１　冯诺伊曼体系

１．１　冯诺伊曼体系简介

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

存储器：代码跟数据在ＲＡＭ跟ＲＯＭ中是线性存储，　数据存储的单位是一个二进制位。最小的存储单位是字节。

总线：总线是用于　ＣＰＵ　和内存以及其他设备之间的通信，总线主要有三种：

地址总线：用于指定　ＣＰＵ　将要操作的内存地址。

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

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

输入／输出设备：输入设备向计算机输入数据，计算机经过计算后，把数据输出给输出设备。比如键盘按键时需要和　ＣＰＵ　进行交互，这时就需要用到控制总线。

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

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

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

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

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

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

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

ＣＰＵ　执行完指令后程序计数器的值通过自增指向下个指令，比如３２位ＣＰＵ会自增４。

自增后开始挨次执行下一条指令，不竭循环执行直到程序结束。

ＣＰＵ位宽：３２位ＣＰＵ一次可操作计算４个字节，６４位ＣＰＵ一次可操作计算８个字节，这个是硬件级别的。平常我们说的３２位或６４位操作系统指的是软件级别的，指的是程序中指令多少位。

线路位宽：ＣＰＵ操作指令数据通过凹凸电压变化进行数据传输，传输时候可以串行传输，也可以并行传输，多少个并行等于多少个位宽。

１．２　ＣＰＵ　简介

Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ　中央处理器，作为计算机系统的运算和控制核心，是信息处理、程序运行的最终执行单元。

ＣＰＵ

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

寄存器：最靠近ＣＰＵ对存储单元，３２位ＣＰＵ寄存器可存储４字节，６４位寄存器可存储８字节。寄存器拜候速度一般是半个ＣＰＵ时钟周期，属于纳秒级别，

Ｌ１缓存：每个ＣＰＵ核心都有，用来缓存数据跟指令，拜候空间大小一般在３２～２５６ＫＢ，拜候速度一般是２～４个ＣＰＵ时钟周期。

ｃａｔ　／ｓｙｓ／ｄｅｖｉｃｅｓ／ｓｙｓｔｅｍ／ｃｐｕ／ｃｐｕ０／ｃａｃｈｅ／ｉｎｄｅｘ０／ｓｉｚｅ　＃　Ｌ１　数据缓存

ｃａｔ　／ｓｙｓ／ｄｅｖｉｃｅｓ／ｓｙｓｔｅｍ／ｃｐｕ／ｃｐｕ０／ｃａｃｈｅ／ｉｎｄｅｘ１／ｓｉｚｅ　＃　Ｌ１　指令缓存

Ｌ２缓存：每个ＣＰＵ核心都有，拜候空间大小在１２８ＫＢ～２ＭＢ，拜候速度一般是１０～２０个ＣＰＵ时钟周期。

ｃａｔ　／ｓｙｓ／ｄｅｖｉｃｅｓ／ｓｙｓｔｅｍ／ｃｐｕ／ｃｐｕ０／ｃａｃｈｅ／ｉｎｄｅｘ２／ｓｉｚｅ　＃　Ｌ２　缓存容量大小

Ｌ３缓存：多个ＣＰＵ核心共用，拜候空间大小在２ＭＢ～６４ＭＢ，拜候速度一般是２０～６０个ＣＰＵ时钟周期。

ｃａｔ　／ｓｙｓ／ｄｅｖｉｃｅｓ／ｓｙｓｔｅｍ／ｃｐｕ／ｃｐｕ０／ｃａｃｈｅ／ｉｎｄｅｘ３／ｓｉｚｅ　＃　Ｌ３　缓存容量大小

内存：多个ＣＰＵ共用，现在一般是４Ｇ～５１２Ｇ，拜候速度一般是２００～３００个ＣＰＵ时钟周期。

固体硬盘ＳＳＤ：现在台式机主流都会配备，上述的寄存器、缓存、内存都是断电数据立马丢失的，而ＳＳＤ里不会丢失，大小一般是１２８Ｇ～１Ｔ，比内存慢１０～１０００倍。

机械盘ＨＤＤ：很早以前流行的硬盘了，容量可在５１２Ｇ～８Ｔ不等，拜候速度比内存慢１０Ｗ倍不等。

拜候数据挨次：ＣＰＵ在拿数据处理的时候几乎也是按照上面说得流程来把持的，只有上面一层找不到才会找下一层。

Ｃａｃｈｅ　Ｌｉｎｅ　：　　ＣＰＵ读取数据时会按照　Ｃａｃｈｅ　Ｌｉｎｅ　方式把数据加载到缓存中，每个Ｃａｃｈｅｌｉｎｅ　＝　６４ＫＢ，因为Ｌ１、Ｌ２是每个核独有到可能会触发伪共享，就是　所以可能会将数据划分到不同到ＣａｃｈｅＬｉｎｅ中来避免伪共享，比如在ＪＤＫ８　新增加的　ＬｏｎｇＡｄｄｅｒ　就涉及到此知识点。

伪共享：缓存系统中是以缓存行（ｃａｃｈｅ　ｌｉｎｅ）为单位存储的，当多线程修改互相独立的变量时，如果这些变量共享同一个缓存行，就会无意中影响彼此的性能，这就是伪共享。

ＪＭＭ：　数据经过种种分层会导致拜候速度在不竭提升，同时也带来了各种问题，多个ＣＰＵ同时操作相同数据可能会造成各种ＢＵ个，需要加锁，这里在ＪＵＣ并发已详细探讨过。

１．３　ＣＰＵ　拜候方式

ＣＰＵ拜候方式

内存数据映射到ＣＰＵ　Ｃａｃｈｅ　时通过公式Ｂｌｏｃｋ　Ｎ　％　ＣａｃｈｅＬｉｎｅＭａｘ决定内存Ｂｌｏｃｋ数据放到阿谁ＣＰＵ　Ｃａｃｈｅ　Ｌｉｎｅ　里。ＣＰＵ　Ｃａｃｈｅ　主要有４部分组成。

Ｃａｃｈｅ　Ｌｉｎｅ　Ｉｎｄｅｘ　：ＣＰＵ缓存读取数据时不是按照字节来读取的，而是按照ＣａｃｈｅＬｉｎｅ方式存储跟读取数据的。

Ｖａｌｉｄ　Ｂｉｔ　：　有效位标识表记标帜符，值为０时表示无论　ＣＰＵ　Ｌｉｎｅ　中是否有数据，ＣＰＵ　都会直接拜候内存，重新加载数据。

Ｔａｇ：组标识表记标帜，用来标识表记标帜内存中不同ＢＬｏｃｋ映射到相同ＣａｃｈｅＬｉｎｅ，用Ｔａｇ来区分不同的内存Ｂｌｏｃｋ。

Ｄａｔａ：真实到内存数据信息。

ＣＰＵ真实拜候内存数据时只需要指定三个部分即可。

Ｃａｃｈｅ　Ｌｉｎｅ　Ｉｎｄｅｘ　：要拜候到Ｃａｃｈｅ　Ｌｉｎｅ　位置。

Ｔａｇ：表示用阿谁数据块。

Ｏｆｆｓｅｔ：ＣＰＵ从ＣＰＵ　Ｃａｃｈｅ　读取数据时不是直接读取Ｃａｃｈｅ　Ｌｉｎｅ整个数据块，而是读取ＣＰＵ所需的数据片段，称为Ｗｏｒｄ。如何找到Ｗｏｒｄ就需要个偏移量Ｏｆｆｓｅｔ。

１．４　ＣＰＵ　拜候速度

拜候耗时对比

如上图所示，ＣＰＵ拜候速度是逐步变慢，所以ＣＰＵ拜候数据时需尽量在距离ＣＰＵ近的高速缓存区拜候，按照摩尔定律ＣＰＵ拜候速度每１８个月就会翻倍，而内存的拜候每１８个月也就增长１０％　摆布，导致的结果就是ＣＰＵ跟内存拜候性能差距逐步变大，那如何尽可能提高ＣＰＵ缓存命中率呢？

１．　数据缓存：遍历数据时候按照内存布局挨次拜候，因为ＣＰＵ　Ｃａｃｈｅ是按照Ｃａｃｈｅ　Ｌｉｎｅ批量操作数据的，所以你挨次读取数据会提速，道理跟磁盘挨次写一样。

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

线程绑定到ＣＰＵ：一个任务Ａ在前一个时间片用ＣＰＵ核心１　运行，后一个时间片用ＣＰＵ核心２　运行，这样缓存Ｌ１、Ｌ２就浪费了。因此操作系统提供了将进程或者线程绑定到某一颗　ＣＰＵ　上运行的能力。如　Ｌｉｎｕｘ　上提供了　ｓｃｈｅｄ＿ｓｅｔａｆｆｉｎｉｔｙ　方法实现这一功能，其他操作系统也有类似功能的　ＡＰＩ　可用。当多线程同时执行密集计算，且　ＣＰＵ　缓存命中率很高时，如果将每个线程别离绑定在不同的　ＣＰＵ　核心上，性能便会获得非常可不雅观的提升。

１．５　　操作系统

计算机结构

有了冯诺伊曼计算机体系后，电脑想要为用户提供便捷的办事还需要安装个操作系统Ｏｐｅｒａｔｉｏｎ　Ｓｙｓｔｅｍ，操作系统是覆盖在硬件上的一层特殊软件，它办理计算机的硬件和软件资源，为其他应用程序提供大量办事。可以理解为操作系统是日常应用程序跟硬件之间的接口。日常你经常在用Ｗｉｎｄｏｗｓ／Ｌｉｎｕｘ　系统，操作系统给我们提供了超级大的便当，但是你了解操作系统么？操作系统是如何进行内存办理、进程办理、文件办理、输入输出办理的呢？

２　内存办理

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

虚拟内存

２．１　　ＭＭＵ

Ｍｅｍｏｒｙ　Ｍａｎａｇｅｍｅｎｔ　Ｕｎｉｔ　内存办理单元是一种负责处理ＣＰＵ内存拜候请求的计算机硬件。它的功能包罗虚拟地址到物理地址的转换、内存庇护、中央处理器高速缓存的控制。现代　ＣＰＵ　基本上都选择了使用　ＭＭＵ。

当进程持有虚拟内存地址的时候，ＣＰＵ执行该进程时会操作虚拟内存，而ＭＭＵ会自动的将虚拟内存的操作映射到物理内存上。

ＭＭＵ

这里提一下，Ｊａｖａ操作的时候你看到的地址是ＪＶＭ地址，不是真正的物理地址。

２．２　　内存办理方式

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

２．２．１　内存分段

ＪＶＭ内存模型

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

内存分段办理

如上虚拟地址有　５　个段，各段按如图所示来存储。每个段都在段表中有一个条目，它包罗段在物理内存内的开始的基地址和该段的边界长度。例如段　２　为　４００　字节长，开始于位置　４３００。因此对段　２　字节　５３　的引用映射成位置　４３００　＋　５３　＝　４３５３。对段　３　字节　８５２　的引用映射成位置　３２００　＋　８５２　＝　４０５２。

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

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

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

以上图为例，现在系统空闲是１４００　＋　　８００　＋　６００　＝　２８００。那如果有个程序想要连续的使用２０００，内存分段模式下提供不了啊！上述三个是外部内存碎片。当然可以使用系统的Ｓｗａｐ空间，先把段０写入到磁盘，然后再重新给段０分配空间。这样可以实现最终可用，可是但凡涉及到磁盘读写就会导致内存交互效率低。

ｓｗａｐ空间利用

２．２．２　内存分页

内存分页，整个虚拟内存和物理内存切成一段段固定尺寸的大小。每个固定大小的尺寸称之为页Ｐａｇｅ，在　Ｌｉｎｕｘ　系统中Ｐａｇｅ　＝　４ＫＢ。然后虚拟内存跟物理内存之间通过页表来实现映射。

采用内存分页时内存的释放跟使用都是以页为单位的，也就不会产生内存碎片了。当空间还不够时按照操作系统调度算法，可能将最少用的内存页面　ｓｗａｐ－ｏｕｔ换出到磁盘，用时候再ｓｗａｐ－ｉｎ换入，尽可能的减少磁盘刷写量，提高内存交互效率。

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

分页内存寻址

３２位操作系统环境下进程可操作的虚拟地址是４ＧＢ，假设一个虚拟页大小为４ＫＢ，那需要４ＧＢ／４ＫＢ　＝　２＾２０　个页信息。一行页表记录为４字节，２＾２０等价于４ＭＢ页表存储信息。这只是一个进程需要的，如果１０个、１００个、１０００个呢？仅仅是页表存储都占据超大内存了。

为了解决这个问题就需要用到　多级页表，核心思想就是局部性分配。在３２位的操作系统中将将４Ｇ空间分为　１０２４　行页目录项目（４ＫＢ），每个页目录项又对应１０２４行页表项。如下图所示：

３２位系统二级分页

控制寄存器ｃｒ３中存放了页目录的物理地址，通过ｃｒ３寄存器可以找到页目录，而３２位线性地址中的Ｄｉｒｅｃｔｏｒｙ部分决定页目录中的目录项，而页目录项中存放了要找的页表的物理基地址，再结合线性地址中的中间１０位页表项，就可以找到页框的页表项。线性地址中的Ｏｆｆｓｅｔ部分占１２位，因此页框的物理地址　＋　线性地址Ｏｆｆｓｅｔ部分　＝　页框中的任何一个字节。

分页后一级页就等价于４Ｇ虚拟地址空间，并且如果一级页表中那些地址没有就不需要再创建二级页表了！核心思想就是按需创建，当系统给每个进程分配４Ｇ空间，进程不成能占据全部内存的，如果一级目录页只有１０％用到了，此时页表空间　＝　一级页表４ＫＢ　＋　０．１　＊　４ＭＢ　　。这比单独的每个进程占据４Ｍ好用多了！

多层分页的弊端就是拜候时间的增加。

使用页表时读取内存中一页内容需要２次拜候内存，拜候页表项　＋　并读取的一页数据。

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

而对于６４位系统，二级分页就无法满足了，Ｌｉｎｕｘ　从２．６．１１开始采用四级分页模型。

Ｐａｇｅ　Ｇｌｏｂａｌ　Ｄｉｒｅｃｔｏｒｙ　全局页目录项

Ｐａｇｅ　Ｕｐｐｅｒ　Ｄｉｒｅｃｔｏｒｙ　上层页目录项

Ｐａｇｅ　Ｍｉｄｄｌｅ　Ｄｉｒｅｃｔｏｒｙ　中间页目录项

Ｐａｇｅ　Ｔａｂｌｅ　Ｅｎｔｒｙ　页表项

Ｏｆｆｓｅｔ　偏移量。

６４位寻址

２．２．２　ＴＬＢ

Ｔｒａｎｓｌａｔｉｏｎ　Ｌｏｏｋａｓｉｄｅ　Ｂｕｆｆｅｒ　可翻译为地址转换后援缓冲器，简称为快表，属于ＣＰＵ内部的一个模块，ＴＬＢ是ＭＭＵ的一部分，本色是ｃａｃｈｅ，它所缓存的是比来使用的数据的页表项（虚拟地址到物理地址的映射）。他的出现是为了加快拜候数据（内存）的速度，减少重复的页表查找。当然它不是必需要有的，但有它，速度就更快。

ＴＬＢ

ＴＬＢ很小，因此缓存的东西也不多。主要缓存比来使用的数据的数据映射。ＴＬＢ结构如下图：

ＴＬＢ查询

如果一个需要拜候内存中的一个数据，给定这个数据的虚拟地址，查询ＴＬＢ，发现有ｈｉｔ，直接得到物理地址，在内存按照物理地址取数据。如果ＴＬＢ没有这个虚拟地址ｍｉｓｓ，那么只能费力的通过页表来查找了。日常ＣＰＵ读取一个数据的流程如下：

ＣＰＵ读取数据流程图

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

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

部分刷新：按照标识表记标帜位，刷新需要刷新的数据，保留不需要刷新的数据。

２．２．３　段页式办理

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

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

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

此时　地址结构　＝　段号　＋　段内页号　＋　页内位移。

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

段页式办理

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

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

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

目前　Ｉｎｔｅｌ　Ｘ８６　ＣＰＵ　采用的是内存分段　＋　　内存分页的办理方式，其中分页的意思是在由段式内存办理所映射而成的的地址上再加上一层地址映射。

Ｘ８６内存办理方式

２．２．４　Ｌｉｎｕｘ　内存办理

先说结论：Ｌｉｎｕｘ系统基于Ｘ８６　ＣＰＵ　而做的操作系统，所以也是用的段页式内存办理方式。

我们知道３２位的操作系统可寻址范围是４Ｇ，操作系统会将４Ｇ的可拜候内存空间分为用户空间跟内核空间。

内核空间：操作系统内核拜候的区域，独立于普通的应用程序，是受庇护的内存空间。内核态下ＣＰＵ可执行任何指令，可自由拜候任何有效地址。

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

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

后来研究者按照ＣＰＵ的运行级别，分成了Ｒｉｎｇ０～Ｒｉｎｇ３四个级别。Ｒｉｎｇ０是最高级别，Ｒｉｎｇ１次之，Ｒｎｇ２更次之，拿Ｌｉｎｕｘ＋ｘ８６来说，　　操作系统内核的代码运行在最高运行级别Ｒｉｎｇ０上，可以使用特权指令，控制中断、修改页表、拜候设备等。　应用程序的代码运行在最低运行级别上Ｒｉｎｇ３上，不能做受控操作，只能拜候用户被分配的空间。如果要做拜候磁盘跟写文件等操作，那就要通过执行系统调用函数，执行系统调用的时候，ＣＰＵ的运行级别会发生从Ｒｉｎｇ３到Ｒｉｎｇ０的切换，并跳转到系统调用对应的内核代码位置执行，这样内核就为你完成了设备拜候，完成之后再从Ｒｉｎｇ０返回Ｒｉｎｇ３。这个过程也称作用户态和内核态的切换。

用户态想要使用计算机设备或ＩＯ需通过系统调用完成ｓｙｓ　ｃａｌｌ，系统调用就是让内核来做这些操作。而系统调用是影响整个当前进程上下文的，ＣＰＵ提供了个软中断来是实现庇护线程，获取系统调用号跟参数，交给内核对应系统调用函数执行。

Ｌｉｎｕｘ系统结构

可以看到每个应用程序都各自有独立的虚拟内存地址，但每个虚拟内存中对应的内核地址其实是相同的一大块，这样当进程切换到内核态后可以很便利地拜候内核空间内存。比如Ｊａｖａ代码创建线程ｎｅｗ　Ｔｈｒｅａｄ调用ｓｔａｒｔ方法后跟踪ＪＶＭ源码你会发现是调用ｐｔｈｒｅａｄ＿ｃｒｅａｔｅ来创建线程的，这就涉及到了用户态到内核态的切换。

３　进程办理

３．１　进程基础知识

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

状态变化图

重点说下挂起跟阻塞：

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

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

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

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

３．２　ＰＣＢ

为了描述跟控制进程的运行，系统为每个进程定义了一个数据结构——进程控制块　Ｐｒｏｃｅｓｓ　Ｃｏｎｔｒｏｌ　Ｂｌｏｃｋ，它是进程实体的一部分，是操作系统中最重要的记录型数据结构。

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

作为独立运行基本单位的标识表记标帜

实现间断性的运行方式

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

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

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

３．２．１　ＰＣＢ　信息

ＰＣＢ为实现上述功能，内部包含众多信息：

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

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

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

处理机状态：由各种寄存器组成。包含许多信息都放在寄存器中，便利程序ｒｅｓｔａｒｔ。

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

进程调度信息

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

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

进程调度所需的其它信息：与所采用的进程调度算法有关，如进程已等待ＣＰＵ的时间总和、进程已执行的时间总和等。

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

资源清单

有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的　Ｉ／Ｏ　设备信息。

３．２．２　ＰＣＢ　组织方式

操作系统中有太多　ＰＣＢ，如何办理是个问题，一般有如下方式。

线下数组

线性方式：

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

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

索引方式

索引方式：

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

链表方式

链接方式：

把同一状态的ＰＣＢ链接成一个队列，形成就绪队列、阻塞队列、空白队列等。对其中的就绪队列常按进程优先级的凹凸摆列，优先级高排在队前。

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

３．３　进程控制

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

３．３．１　进程创建

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

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

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

初始化ＰＣＢ，有如下几个操作。

标识信息：将系统分配的标识符和父进程标识符填入新ＰＣＢ

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

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

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

３．３．２　进程终止

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

正常结束

异常结束

越界错：拜候的存储区越出该进程的区域

庇护错：试图拜候不允许拜候的资源，或以不适当的方式拜候（写只读）

不法指令：试图执行不存在的指令（可能是程序错误地转移到数据区，数据当成了指令）

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

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

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

算数运算错：试图执行被禁止的运算（被０除）

Ｉ／Ｏ故障

外界干预

操作员或ＯＳ干预（死锁）

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

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

终止过程：

按照被终止进程的标识符，从ＰＣＢ集合中检索出该ＰＣＢ，读取进程状态

若处于执行状态则立即终止执行，将ＣＰＵ资源分配给其他进程。

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

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

该进程的ＰＣＢ从所在队列／链表中移出。

３．３．３　进程阻塞

意思是该进程执行半路被阻塞，必需由某个事件进程唤醒该进程。常见的就是ＩＯ读取操作。常见阻塞时机／事件如下：

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

等待某种操作完成

新数据尚未到达（彼此合作的进程）

等待新任务

阻塞流程：

找到要被阻塞进程标识号对应的　ＰＣＢ。

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

将该　进程ＰＣＢ　插入的阻塞队列中去。

３．３．４　进程唤醒

唤醒　原语　ｗａｋｅ　ｕｐ，一般和阻塞成对使用。唤醒过程如下：

从阻塞队列找到所需ＰＣＢ。

ＰＣＢ从阻塞队列溢出，然后变为就绪状态。

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

３．４　进程调度

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

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

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

３．４．１　进程调度原则

ＣＰＵ　利用率

ＣＰＵ利用率　＝　忙碌时间　／　总时间。

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

系统吞吐量

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

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

周转时间

周转时间　＝　作业完成时间　－　作业提交时间。

平均周转时间　＝　各作业周转时间和　／　作业数

带权周转时间　＝　作业周转时间　／　作业实际运行时间

平均带权周转时间　＝　各作业带权周转时间之和　／　作业数

尽可能使周转时间降低。

等待时间

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

响应时间

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

３．４．２　调度算法

ＦＣＦＳ　算法

Ｆｉｒｓｔ　Ｃｏｍｅ　Ｆｉｒｓｔ　Ｓｅｖｅｒｄ　先来先办事算法，遵循先来后端原则，每次从就绪队列拿等待时间最久的，运行完毕后再拿下一个。

该模式对长作业有利，适用　ＣＰＵ　繁忙型作业的系统，不适用　Ｉ／Ｏ　型作业，因为会导致进程ＣＰＵ利用率很低。

ＳＪＦ　算法

Ｓｈｏｒｔｅｓｔ　Ｊｏｂ　Ｆｉｒｓｔ　最短作业优先算法，该算法会优先选择运行所需时间最短的进程执行，可提高吞吐量。

跟ＦＣＦＳ正好相反，对长作业很不利。

ＳＲＴＮ　算法

Ｓｈｏｒｔｅｓｔ　Ｒｅｍａｉｎｉｎｇ　Ｔｉｍｅ　Ｎｅｘｔ　最短剩余时间优先算法，可以认为是ＳＪＦ的抢占式版本，当一个新就绪的进程比当前运行进程具有更短完成时间时，系统抢占当前进程，选择新就绪的进程执行。

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

ＨＲＲＮ　算法

Ｈｉｇｈｅｓｔ　Ｒｅｓｐｏｎｓｅ　Ｒａｔｉｏ　Ｎｅｘｔ　最高响应比优先算法，为了平衡前面俩而生，按照响应优先权从高到低依次执行。属于前面俩的折中权衡。

优先权　＝　（等待时间　＋　要求办事时间）　／　要求办事时间

ＲＲ　算法

Ｒｏｕｎｄ　Ｒｏｂｉｎ　时间片轮转算法，操作系统设定了个时间片Ｑｕａｎｔｕｍ，时间片导致每个进程只有在该时间片内才可以运行，这种方式导致每个进程都会均匀的获得执行权。

时间片一般２０ｍｓ～５０ｍｓ，如果太小会导致系统频繁进行上下文切换，太大又可能引起对短的交互请求的响应变差。

ＨＰＦ　算法

Ｈｉｇｈｅｓｔ　Ｐｒｉｏｒｉｔｙ　Ｆｉｒｓｔ　最高优先级调度算法，从就绪队列中选择最高优先级的进程先执行。

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

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

ＭＦＱ　算法

Ｍｕｌｔｉｌｅｖｅｌ　Ｆｅｅｄｂａｃｋ　Ｑｕｅｕｅ　多级反馈队列调度算法　，可以认为是　ＲＲ　算法　跟　ＨＰＦ　算法　的综合体。

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

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

多级反馈队列调度算法

３．５　线程

３．５．１　线程定义

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

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

进程有个ＰＣＢ来办理，同理操作系统通过　Ｔｈｒｅａｄ　Ｃｏｎｔｒｏｌ　Ｂｌｏｃｋ线程控制块来实现线程的管控。

３．５．２　线程优缺点

优点

一个进程中可以同时存在１～Ｎ个线程，这些线程可以并发的执行。

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

缺点

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

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

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

３．５．３　进程跟线程关联

进程：

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

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

线程：

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

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

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

进程线程区别：

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

线程的划分标准小于进程（资源比进程少），使得多线程程序的并发性高。

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

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

ＣＰＵ分配资源给进程，但真正在ＣＰＵ上运行的是线程。

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

线程快在哪儿？

线程创建的时有些资源不需要本身办理，直接从进程拿即可，线程办理寄存器跟栈的生命周期即可。

同进程内多线程共享数据，所以进程数据传输可以用ｚｅｒｏ　ｃｏｐｙ技术，不需要经过内核了。

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

３．５．４　线程实现

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

３．５．４．１　用户态线程

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