本章学习内容参考了清华大学陈渝老师所讲的操作系统(Operating System).
顶级会议: SOSP,USENIX
学术界：ACM,IEEE,USENIX,国内CCF

[TOC]

6.页面置换算法

(1) 功能与目标
(2) 局部页面置换算法
(3) Belay现象与其他几种算法对比
(4) 全局页面置换算法

6.1 页面置换算法功能与目标

功能：当缺页中断发生时,需要调入新的页面而内存已满时,需要选择哪个物理页面被置换。

目标：尽可能减少缺页中断 (页面的换入换出)次数,简单的说把未来不在使用和短期内较少使用的页面置换出去,在局部性原理下根据过去的数据统计预测

页面锁定(Frame locking): 用于描述必须常驻内存的操作系统的关键部分或时间关键的应用进程 (time-critical),前提是需要在页表中添加锁定标志位 (lock bit)。

如记录一个进程页访问的一个规矩：

#举例：(虚拟)地址跟踪(页号,位移) 序列
 (3,0)  (1,9)  (4,1) (2,1) (5,3) (2,0) (1,9) (2,4) (3,1)  (4,8)

#生成的轨迹页面采用字母进行替换：
3 1 4 2 5 2 1 2 3 4 
c a d b e b a b c d

#模拟一个页面置换的行为并且记录产生缺页的数量,越少性能越好。

6.2 局部页面置换算法

6.2.1)最优页面置换算法： (理论参考)

思路：宕缺页中断发生时,对于保存在内存当中的每一个逻辑页面,计算在它下一次访问之前,还需等待多长时间; 选择内存中等待时间最长的页作为置换页面。 (以将来预测将来)

注意：这是一种理想情况作为评价其他算法的标杆而已 (利用第一次的访问轨迹来使用最优算法),在实际操作系统中无法实现,因为无从知道每个页面需要等待多长实际以后才会再次被访问。

置换页面是将将来最长实际不需要的页面：

weiyigeek.top-置换页面案例

总结：

• 物理内存不足时需要换出内存中的数据
• 置换算法选择将哪些数据换出而且尽可能减少换入换出次数

6.2.2)先进先出算法 (FIFO)：

First-In First-out,fifo:换出在内存中驻留时间最长的页面并淘汰之,但存在时间久的数据有可能会被频繁访问导致缺页中断较多,而FIFO算法很少单独使用。

原理：OS 维护着一个链表,记录了所有位于内存中的逻辑页面。从链表的排列顺序来看,链首页面的驻留时间最长,链尾页面的驻留时间最短。当发生一个缺页中断时候,把链首页置换出去,将新加入的页面添加到链表尾部。

缺点：
1) 性能较差,调出的页面有可能是经常要访问的页面
2) 有Belady现象。( 如分配页帧越多[页容量变多],出现页缺失的情况反而越频繁)

FIFO belady现象：分配的物理页数增加缺页率反而提高,原因是FIFO忽视了进程访问的动态特征。

先进先出算法案例：
默认 a->b->c->d 存入的4个页帧时间节点长短,使用单一的指针存放。

weiyigeek.top-先进先出算法

6.2.3) 最近最久未使用算法 (Least Recently Used, LRU)：

基本思路: 当缺页中断发生时候,选择最近最久未使用的那个页面淘汰掉,
介绍：近似于最优置换算法的,不同的是以过去推未来。根据程序的局部性原理,如果最近一段时间内某些页面被频繁访问,那么在将来还可能被频繁访问。反之未被访问的将来也不会被访问。

优点：缺页较少
缺点：要记录每个数据的访问时间,开销较大
程序应具有较好的局部性,可以看出比FIFO算法好,只产生了三次缺页中断

weiyigeek.top-最近最久未使用算法链表表示

使用两种方法来实现LRU:
(1) 系统维护一个页面链表,最近刚使用的页面最为首节点,最久未使用的页面作为尾节点,每次访问内存动态更新头结点。缺页中断时,淘汰末位的页面。
(2) 采用栈来实现》访问某页时将此页号入栈,并去除栈内的重复页,并将其放入栈顶,如果站内不存在则淘汰栈底的页面然后同样放入栈顶。

Q：怎么push栈底？
A：栈是先进后出只有栈顶开口,动态更新 (插,删,内部调整)堆栈和链表要开销,注意平衡—不是最有效,我们说过系统要尽可能的简单高效。

weiyigeek.top-最近最久未使用算法栈表示

6.2.4)时钟算法 (Clock)：

描述：与LRU的近似,是对FIFO的改进,唯一不足缺页次数稍大但是却也节省空间,利用在环形链表中记录frame的access bit。把各个页面组成环形链表类似一个clock,指针指向最老的页面。

基本思路：

• 页表项当中的访问位,当页面被装入内存时候把该位初始化位0,如果这个页面被访问(R/w)则该位位1;
• 把各个页面组织成环形链表(类似钟表面),把指针指向最老的页面(最先进入的),所有bit定期归零
• 发生缺页时在环形链表中寻找最老的页面且access bit为0的frame,若used为1则置为0,若为0则换出。 (顺时针遍历查找直到淘汰某页)

注意： 这里Used置为0/1是硬件操作,无需软件接触(当然软件也能清空/置1)

维持一个环形页面链表保存在内存中：
(1) 每个页帧采用一个时钟(或者使用/引用)位来标记一个页面是否经常被访问。
(2) 当页面被引用的时候USED位置为1

在内存中维持一个环形页面链表更新并删除 used bit=0的页面,如下图：
替换的应该是page = 1,把需要的新页面放到物理帧号为5的位置

weiyigeek.top-环形页面链表clock

伪代码：

function Clock_rep
begin
//顺时针
while (victim page not fund) do   //置换页面没有被找到时候都为真
    if(currentpage use bit == 0) then
        //如果当前替换页面与新页面帧号相同,直接use id置为1即可,指针指向当前newpage
        if(currentpage == newpage)
        {
            repalce current page && set use bit = 1;
            break;  //不进行step
        }
         repalce current page && set use bit = 1
    else
         set use bit = 0
    endif
    step   //指向下一个目标
end while
end Clock_rep

clock耍实例替换图：

weiyigeek.top-环形页面链表clock

6.2.5)二次机会法 ：

这里有一个巨大的代价来替换 “脏” 页(dirty),读和写都是访问,dirty bit是写位如果写为1否则是0;修改clock算法使它允许脏页总是在一次时钟头扫描时保留下来,以减少写回硬盘的操作 (仅读的页可以直接释放)

原理：同时使用dirty bit脏位和 used bit使用位来指导置换;需要替换的页其访问位和脏位都是0,如果都是1则有两次机会才被淘汰,从而让更多使用频率的页有更多的机会留在内存中。

特点：较为接近LRU算法,尽量保存dirty page,更好地减少了访问外存.

二次机会算法,改进clock,(access bit, dirty bit) :

(1, 1) -> (0, 1) -> (0, 0)
(1, 0) -> (0, 0)
换出(0, 0),被修改过的frame换出开销大,指针经过两次才变为(0, 0)

weiyigeek.top-二次机会算法

二次机会算法案例：
a^w 代表是写位则使用的时候,这时候使用位于脏位分别是 11;替换后指针指向下一位页帧,如果页中存在该页帧直接根据是否写入,将使用位和写入位分别置为 1 0 或者 1 1。

weiyigeek.top-二次机会算法案例

6.2.6)最不常用算法

(least frequently used)LFU 基本思路：当一个缺页中断发生时候,选择访问的次数最少的那个页面并淘汰(将访问次数最少的数据换出)。
实现方法：对每个页面设置访问计数器count,每当一个页面被访问时++,淘汰数值最小的那个。
优缺点：硬盘计数器空间开销,排序查找时间开销；

Q:LRU/LFU区别是什么?
A:LRU考察的是多久未访问,时间越短越值得留在内存,LFU是访问次数/频度,次数越多越好。

优化思路：把时间也考虑进去,通过时间与次数结合进行考查,定期把次数寄存器右移一位。

取名最不常用算法是由于我们可以利用一个反例证明：一个页面在进程开始时使用的很多,但以后就不使用了,此时LFU就不适用了。

案例：

Time     0  1 2 3 4 5 6 7 8 9 
Requests    c a d b e b a
页        a c a d b e e e 
          b   c a d d b b
帧        c     c a a a a(次数最多)
          d       c c c c
----------------------------------------------
c++  => e
a++     a
d++     d
b++     b

6.3 Belay现象与其他算法对比

belady(一个科学家名字)60~70年代发生的现象：在采用FIFO算法,有时分配更多的物理页数增加,缺页率反而更多的现象。
Belady现象原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的,与置换方法的目标不是一致的(及替换较少使用的页面),因此它置换出去的页面并不一定是进程不会访问的。

FIFO的Belay案例1：

• 3个物理页帧,5个虚拟页,访问顺序：1,2,3,4,1,2,5,1,2,3,4,5; 使用list来记录访问虚拟页;

  

  weiyigeek.top-FIFO的Belay案例

FIFO的Belay案例2：

• 物理页帧为4,还是5个虚拟页

  

  weiyigeek.top-FIFO的Belay案例

对比总结：案例1发生了9次缺页中断,3次命中;而案例2发生了10次缺页中断,2次命中。

所以出现了LRU (替换算法)来替换：

weiyigeek.top-FIFO的Belay案例

Q：为什么会出现这样的情况?
A：LRU算法符合栈算法特征给它的物理页帧越多,产生的缺页次数就越少；而FIFO算法则不满足栈算法,所以则相反。

LRU/FIFO和Clock的比较：
(1) LRU和FIFO本质都是先进先出思路

• LRU是页面的最近访问时间排序而不是进入内存的时间,每次页面访问有动态调整各个页面先后次数,符合栈算法的特性,空间越大缺页越少。
• FIFP是针对页面进入内存的时间进行排序,这个时间是固定不变的,所以各页面之间的先后顺序是固定的。
• 如果内存当中的所有页面都未曾访问过,那么LRU算法就退化为FIFO算法。
• LRU算法性能较好,但是开销大;而FIFO开销小但是存在Belady现象。
  (2) Clock 和 Enhanced clock 也是类似于FIFO的算法
• 使用硬件的 use bit 位来模拟了访问时间和顺序参考。
• 比起LRU/FIFO开销较小,但是算法表现效果等同于LRU,但也会退化为FIFO。
• 而对于曾经访问过的页面,它不能像LRU算法那样,记住他们的准确位置。
  (3)都对程序的访问次序有局部性的要求,不然都会退化。
  (4)分配的物理页帧的数目对置换算法的效果有很大的影响

6.4 全局页面置换算法

描述：实现全局动态分配各个程序的内存,保持平衡,为了解决局部页替换算法的问题并效果好于局部算法。
程序的运行具有阶段性是动态变化的过程,开头结尾较多,中间较少,都分配固定的物理页帧则失去了灵活性,所以更要采用全局页面置换算法。

Q:前面介绍得的各种页面置换算法,都是基于程序的局部性原理,但此原理是否成立?
A:(1) 如果局部性原理不成立,那么各种置换算法就没有什么分别了,也没什么意义.(如单调递增,再物理页帧有限的前提下,不管采用何种置换算法,每次页面访问都必然导致缺页中断)
(2) 如果局部性原理是成立的,那么如何俩证明它的存在,所以就引出了工作集模型,利用工作集模型来表征局部性。

6.4.1 工作集模型

working set定义：一个进程当前使用的逻辑页面集合,可以使用一个二元函数W(t, Δ)来表示

• t 是当前的执行时刻
• Δ 是工作集窗口(working-set windows),即一个定长的页面访问的时间窗口.
• W(t,Δ) == 当前时刻t之前的Δ时间内所有访问页面组成的集合,集合随t不断的更新变化(t+Δ构成了一个时间段)
• | W(t,Δ)|是工作集的大小,即页面数目

工作集模型案例：页面访问顺序如下：
如果 Δ 时间窗口的长度为10,那么w(t1,Δ) = {1,2,5,6,7} 而 W(t2,Δ) = {3,4} ,从这里可以看出t2有很好的局部性操作,由于它重复的访问3和4。

weiyigeek.top-工作集模型案例

工作集大小的变化：
进程开始后,随着访问新页面逐步建立较稳定的工作集,当内存访问的局部性区域的位置大致稳定时,|W(t,Δ)|波动也大致稳定;在过渡阶段,局部性区域的位置发生改变时,工作集则会快速扩张和收缩过渡到下一个稳定值。

weiyigeek.top-工作集大小的变化

6.4.2 常驻集模型

定义：在当前时刻进程实际驻留在内存当中的页面集合。

• 工作集是进程运行中固有性质,常驻集取决于系统分配给进程的物理页面数目和所采用的置换算法。
• 如果一个进程的常驻集与工作集尽量重叠(常驻集包含工作集),则不会造成太多缺页中断(直到工作集发生剧烈变动,从而过渡到另一个状态)
• 当常驻集大小达到某个数目后,分配再多物理页帧缺页率也不会有明显下降,但此时可以把多出来的物理页帧分给其他程序了

工作集于常驻集的对比:
常驻集：当前运行的程序在内存中需要访问的页那些在内存中
工作集：在程序运行之中它所需要访问的页是那些(有可能在内存/但也可能不在内存中)

6.4.3 工作集缺页置换算法

思路：追踪之前的 t 个的引用,老的页会随着时间不断的换出(大于工作集窗口则抛弃),不管是否有缺页中断。确保物理页帧始终有空余的,给其他程序提供内存,让系统的缺页率降低。

原理：固定窗口大小随着时间窗口移动,换出窗口外的页,换出最久未访问的页,限制每个程序的可用内存。

工作集缺页置换算法案例：
在之前t个内存访问的页引用是工作集,t被称为窗口大小;
加入 Eg t = 4 工作集窗口,只要page达到了t=4则移除,即使没有产生缺页中断;

weiyigeek.top-工作集缺页置换算法案例

6.4.4 缺页率页面置换算法

(Page Fault Frequency, PFF) 上面的算法窗口是固定的,所以引出缺页率页面置换算法;用缺页发生的时间间隔评价缺页率,间隔短说明内存不足,加载页,间隔长说明内存过多,换出未访问的页。

可变分配策略：常驻集大小可变;每一个进程在刚开始运行的时候先根据程序大小给它分配一定的数目的物理页面,然后在进程运行过程中,再动态地调整常驻集的大小。

• 可采用全局页面置换的方式,当发生一个缺页中断时,被置换的页面可以在其他进程中,各个并发进程竞争地使用物理页面
• 缺页率算法 (PFF, page fault frequency)动态调整常驻集的大小
• 优缺点：性能较好,但是增加了系统开销。

缺页率：
缺页率表示 “ 缺页次数 / 内存访问次数”(比率) 或者 “缺页的平均时间间隔的倒数”;
影响缺页率的因素有:

• 页面置换算法
• 分配给进程的物理页面数目(越多越小)
• 页面本身的大小(分配物理页面大则会小)
• 编程方法(局部性好就会小)

若运行程序的缺页率高,则通过增加工作集(Δ)来分配更多物理页面,若过低则减少工作集(Δ)来减少其物理页面;使缺页率保持在一个合理的范围内,各个程序之间保持一个平衡。

一个交替的工作集计算明确的试图最小化页缺失:

• 缺页率高–增加工作集
• 缺页率低–减少工作集

具体机制：根据缺页的时间间隔来判断动态更新。
保持追踪缺失发生概率:当缺失发生时候,记录上次缺页到这次的时间间隔,Tlast是上次的页缺失的时间.

• IF 页缺失之间的时间是 “MAX” 的,之后减少工作集。

• IF 页缺失之间的时间是 “Min” 的,之后增加工作集。

• 如果 t(current) -t(last) > T,则从内存中移除[t(last),t(current)]时间内没有被引用的页。

• 如果 t(current) -t(last) <= T,之后增加缺失页到工作集中。

缺页率页面置换算法案例：
EG：windows SIZE = 2,按照上面的缺页中断来进行处理,判断是否大于T,如果大于则替换/移除,如果物理内存页中存在则直接更新T = 0 即可,其他页时间都加1。

weiyigeek.top-缺页率页面置换算法案例

总结：
局部置换算法：只有再物理内存页满的时候进行调整页替换/移除
全局置换算法：动态调整内存页面,即使再物理内存页没有满的时候,也将页进行移除或替换

6.5 抖动问题 (thrashing)

主要是对工作集和常驻集做一个讲解,如果分配给一个进程的物理页面太少不能包含整个工作集,这时出现常驻集属于工作集;那么进程将会造成很多的缺页中断,需要频繁地再内存与外存之间替换页面,从而使进程的运行慢,这种状态就变成为”抖动”;
原理： 内存严重不足时,大量时间耗费在换入换出操作上,程序运行效率大大降低的现象

产生原因：
随着驻留内存的进程数目增加,分配给每个进程的物理页面数不断减少,缺页率不断上升;因此OS要选择一个适当的进程数目和进程需要的帧数,在并发水平和缺页率中达到平衡。

抖动问题可能被本地的页面置换改善,加载控制 (better criteria for load control: adjust MPL so that):
[平均页缺失时间 mean time between page faults(MTBF)] = [页缺失服务时间 page fault service time (PFST)]
∑ WSi=内存的大小

示例图：我们想要的是运行程序多即找到交汇点,此时可以并发执行的程序个数和cpu利用率都较好;且CPU利用率高,而现实是让 MTBF(无限趋近于PFST) / PFST == 1 使总体达到平衡。
X轴 多程序运行 , Y轴 CPU利用率。

weiyigeek.top-抖动问题

总结：
1) 程序开的多,OS忙于换进换出的I/O操作,用于运行程序的cpu少了.
2) 虚拟内存使用这些算法来缓解内存不足的现象,同时保证OS的高效率。

---

7.进程与线程

(1) 进程的定义/组成/特点
(4) 进程控制结构

(5) 进程状态(state)/状态变化模型
(7) 进程挂起

(8) 线程管理(THREAD)/定义
(11) 线程的实现(进程间通信INTER-PROCESS COMMUNCATION),进程互斥与同步,死锁。

(12) 进程的上下文切换与控制

7.1 进程定义/组成/特点

OS系统由于CPU性能的提升从只能跑一个程序到能跑多个程序,进程可以描述程序的执行过程。
定义： 进程是一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。
产生进程的过程：源代码 (-Complie Link-) Executebale File (-Load 内存中-) 进程的地址空间

组成：
包含了正在运行的一个程序的所有状态信息

• 程序的代码
• 程序处理的数据
• 要知道现在执行哪条指令，程序计数器中的值指示下一条将运行的指令。
• CPU寄存器会动态变化，一组通用寄存器的当前值，堆，栈等；
• 各种系统资源，内存，外存，网络(如打开的文件)

进程与程序的联系：

• 程序是进程的基础
• 程序每次运行构成不同的进程
• 进程是程序功能的体现
• 多次执行——某一个程序对应多个进程
• 调用关系——某一个进程包括多个程序(子进程与父进程),多对多的映射关系

进程与程序的区别:

• 程序是静态的,进程是动态的;
• 程序是有序代码的结合,进程是程序的执行有核心态/用户态
• 程序是永久保存,进程是暂时的(一个状态变化的过程)
• 程序与进程组成不同; 进组成包括程序 , 数据（可能变化）,进程控制块（进程状态信息）

进程与程序的关系图：

weiyigeek.top-进程与程序的关系图

特点：
动态性：可以动态创建,结束进程;
并发性:（在一段时间内有多个程序在执行 不同于并行，是一个时间点有多个程序运行需多个CPU即多核，进程可以被独立调度并占用处理机运行）
独立性: 正确性不受影响（通过OS给不同的进程分配不同页表）, 及工作互不影响。
制约性: 因访问共享数据/资源或进程间同步产生制约，要同步互斥；

补充：进程与程序的特点图

weiyigeek.top-进程与程序的特点图

问题1:如果您设计一个OS如何实现其中的进程管理机制?
A:

7.2 进程控制结构

程序 = 算法 + 数据结构
描述进程的数据结构：进程控制块(PROCESS control block PCB),OS给每个进程都维护了一个PCB,保存与之有关的所有状态信息。

PCB进程控制块： 进程存在的唯一标识，OS管理控制进程运行所用的信息集合，描述进程的基本情况和运行变化的过程。

进程控制块使用：

• 进程创建生成一个PCB;
• 经常中止回收PCB;
• 组织管理来完成进程的创建、终止和管理;

PCB含有三大类信息：
(1) 进程标识

• 进程的标识如Windows上的PID,本进程产生者标识(父进程标识),用户标识。

(2) 状态信息
处理机状态信息保存区,保存进程的运行现场信息(主要就是寄存器)

• 用户可见寄存器，程序使用的数据，地址
• 控制和状态寄存器，程序计数器(pc)，程序状态字(PSW)
• 栈指针，过程调用/系统调用/中断处理和返回时需要用到它

(3) 控制信息

• 调度和状态信息，用于操作系统调度进程并占用处理机使用。运行状态？等待？进程当前的执行现状
• 进程间通信信息，各种标识、信号、信件等(存储在接收方的进程控制块中)
• 进程本身的存储管理信息，即指向本进程映像存储空间的数据结构，内存信息，占了多少？要不要回收？
• 进程所用资源，有进程打开使用的系统资源(如打开的文件)
• 有关数据结构连接信息，进程可以连接到一个进程队列，或链接到其他进程的PCB(父进程/子进程/构成一个链)

PCB实现方式：
链表：同一状态进程其PCB形成一链表,多个状态对应不同链表(如就绪链表,阻塞链表)
索引表：同一状态进程归入一个index表(指向PCB),多个状态对应不同的index表。

weiyigeek.top-PCB实现方式

7.3 进程生命周期及其变化模型

进程生命期管理： 进程创建—>进程运行—>进程等待/阻塞—>进程唤醒—>进程结束 分为这5个阶段;

进程生命周期：
(1) 进程创建
引起进程创建的3个主要事件：(源自系统、用户、进程自我调用)

• OS 初始化
• 用户请求创建一个新进程
• 正在运行的进程执行了创建进程的系统调用

(2) 进程运行
内核选择一个就绪的进程,让它占用处理机并执行(有特定的算法)

(3) 进程等待
进程只有自己能阻塞自己,因为只有进程自身才能知道何时需要等待某种事件的发生(注意此时不占用CPU,【阻塞，等待数据就绪、其他进程完成】)

• 请求并等待系统服务无法立即完成
• 启动某种操作也是无法立即完成
• 需要的数据没有到达

(4) 进程唤醒
注意：由于等待的进程不占用CPU,所以进程只能被别的进程或操作系统唤醒(由OS或其他进程完成，回到就绪态)。

• 被阻塞进程需要的资源可被满足
• 被阻塞进程等待的事件到达
• 该进程的PCB插入到就绪队列中

(5) 进程结束

• 自愿（正常退出，错误退出）
• 强制性的（致命错误，被其他进程所杀）

生命周期管理视图：

weiyigeek.top-生命周期管理视图

进程变化状态模型：
进程(线程)状态：new、ready、running、blocked、exit 等五个变化模型;
进程的三种基本状态：进程在生命结束前处于且处于三种基本状态之一,不同系统设置的进程状态数目是不同的。

• 运行状态(Running)：一个进程正在处理机上运行时候。
• 就绪状态(Ready)：一个进程获得了处理机之外的一切所需资源,一旦得到CPU即可运行。（分时占用CPU，OS管理时钟）

• 等待状态(Blocked/又叫阻塞)：一个进程正在等待某一件事件而暂停运行。(等待资源响应)

• 创建状态(NEW):一个进程正在被创建,还没转让到就绪态之前的状态。

• 结束状态(EXIT):一个进程正常系统中消失的状态,由于进程结束或由其他原因导致。

进程变化状态总结：

#init
NULL -> NEW : 一个新进程被产生出来执行某一个程序
NEW -> Ready：进程创建完成并初始化后,一切就绪准备运行时变为就绪状态

#载入CPU
Ready -> Running: 就绪态进程别进程调度程序选中后分配在处理器上来执行/运行
Running -> Exit : 当进程表示它已经完成回值因出错,当前运行进程会由操作系统做结束处理。
Running -> Ready: 处于运行状态的进程运行过程中,由于分配给它处理机事件片使用,切换到其他进程到运行态,当前进程转入就绪态,等待下一次时间片的分配处理。（这就是进程并发性特点）

#阻塞
Running -> Blocked : 当进程请求某样东西且必须等待时候.
Blocked -> Ready   : 当进程等待某事件/资源准备完成时候,它会从阻塞状态编程到就绪状态。

weiyigeek.top-进程变化状态视图

7.4 进程挂起模型

可以合理且充分地利用系统资,这里不同于进程阻塞(不占用CPU);挂起时没有占用该内存空间,而是映像在磁盘上（类似虚存中）,有的程序段被放到了硬盘上。

进程挂起(Suspend)：将内存中的数据换出到磁盘中；就绪或阻塞时可挂起，优先挂起阻塞进程；相反的过程：进程解挂/激活（activate）,简单得说就是把一个进程从内存转到外存。

挂起状态：

• 就绪挂起状态(Ready-suspend):进程在外存,只要进入内存即可运行。
• 阻塞挂起状态(Blocked-suspend):进程在外存并等待某事件得出现。

在内存中被挂起状态转换：

1. 阻塞到阻塞挂起(blocked to blocked suspend): 没有进程处于ready或ready进程要求更多内存资源，会提交新进程或运行就绪进程.
2. 就绪到就绪挂起(ready to ready suspend): 当有高优先级阻塞(OS认为很快就绪)进程和低优先就绪进程时,OS选中挂起低优先级就绪进程。
3. 运行到就绪挂起(running to ready suspend): 抢先式分时系统，空间不够或高优先级阻塞挂起进程进入就绪挂起时，OS可能会把正在运行的进转到就绪挂起状态。

在外存中被挂起状态转换：

1. 阻塞挂起到就绪挂起(blocked suspend to ready suspend): 当阻塞挂起进程因相关事件出现时,转变为ready suspend(就绪挂起)但还在硬盘上。

解挂/激活 activate：进程从外存到内存中,需要运行该进程时可能会有以下情况：

• 就绪挂起到就绪：没有就绪进程 或 挂起就绪进程优先级 高于 就绪进程时, 会进行转换。
• 阻塞挂起到阻塞：当一个进程释放足够内存时,系统会把一个高优先级阻塞挂起(OS认为很快出现所等待的事件)进程转换为阻塞进程。

weiyigeek.top-进程挂起状态

Q:OS怎么通过PCB和定义的进程状态来管理？
A:以进程观点来看待OS：用户进程,磁盘管理进程,终端进程。以进程为基本结构的OS，底层为CPU调度程序（执行哪个？中断处理等），下面一层一层各式各样的进程；

weiyigeek.top-基本结构

状态队列：

• OS要维护一组状态队列（重要的数据结构），表示系统中所有进程的当前状态
• 不同状态分不同队列表示(如就绪队列，各种类型的阻塞队列，挂起队列)
• 每个进程的PCB都根据它的状态加入到相应的队列中,当进程状态发生变化时,它的PCB从一个状态队列中脱离出来,加入到另外一个队列。

7.5 线程(Thread)管理

自从60年代提出进程概念以来,在操作系统中一直都是以进程作为独立运行的基本单位;但是在80年代中期,人们又提出了更小的能独立运行的基本单位——线程。

Q：为什么使用线程？
A：编写一个MP3播放软件,核心功能模块有三个(读取/解压缩/播放数据),如果不采用线程理论上同时进行,那播放的声音有可能时不连续的;(如果CPU能力不够强，排在前面的函数太慢，各个函数之间不能并发影响了资源的使用效率)。

多进程的变化方法(拆开函数，并发，轮着走),但是维护进程的OS开销较大

• 创建进程时:分配资源,建立PCB.
• 撤消进程时:回收资源,撤消PCB.
• 切换进程时:都要保存当前进程的状态信息.

Q：进程间如何通信,如何共享数据？
答：提出一种新的实体，满足实体间可以并发执行，实体之间共享相同的地址空间;而不是像进程，需要OS帮助通信和交换信息。

Q：什么是线程？
A：进程中的一条执行流程,进程中的更小的运行单位。
从两个方式来重新理解进程：

• 资源组合的角度,Process把一组相关的环境资源组合起来,构成一个资平台环境,包括地址控制（代码段,数据段），打开的文件等各种资源。
• 从运行的角度,代码在这个资源平台上的一条执行流程(线程)。

描述线程的数据结构：线程控制块（Thread Control Block，TCB）线程存在自己的TCB只负责这条流程的信息，包括PC程序计数器，SP堆栈，State状态，和寄存器。有不同的控制流，需要不同的寄存器register来表示控制流的执行状态，每个线程有独立的这些信息，但共享一个资源。

weiyigeek.top-线程与进程

线程 = 进程 - 共享资源
线程的优缺点：
1) 优点

• 进程中可以同时存在多个线程
• 各线程之间可以并发的执行
• 各线程之间可以共享地址空间和文件等资源

2) 缺点

• 一个线程崩溃,会导致其所属进程的所以线程崩溃。( 如果一个线程写错了崩溃，如破坏了数据，会导致这个进程的所有线程都崩溃。)

线程机制提高并发性能，但数据共享导致线程间容易发生互相干扰，安全性差。需要性能时使用线程（如科学计算），需要安全时使用进程（如chorme浏览器)

不同操作系统对于线程的支持:

# MS-DOS
单核单线程

#Unix
多核单线程

#windows NT
多核多线程

线程所需要的资源图：

weiyigeek.top-线程所需资源图

线程与进程的比较：

• 进程是资源分配单位,线程是CPU调度单位。
• 进程拥有一个完整的资源平台,而线程只独享必不可少的资源(寄存器/堆栈)
• 线程同样具有就绪，阻塞和执行三种基本状态和转换关系
• 线程能减少并发执行的时间与空间开销：
  (1) 线程的创建时间、终止时间、同一进程内线程的切换时间都比进程所需时间都更短。

  因为进程要创建一些对内存和打开的文件的管理信息，而线程可以直接用所属的进程的信息，因为同一进程内的线程有同一个地址空间，同一个页表，所有信息可以重用，无失效处理。
  
  而进程要切页表，开销大，访问的地址空间不一样，且cache，TLB等硬件信息的访问开销大。

  (2) 同一进程各线程间共享内存文件资源,可以直接进行不通过内核的通信,效率很高。

7.6 线程的实现

主要有三种线程实现方式：
用户线程：在用户空间实现(POSIX Pthreads,maxg C-threads,Solaris,Threads)
内核线程：在内核中实现(Windows,Solaris,Linux)
轻量级进程：在内核中实现,支持用户线程(Solaris,LightWeight Process)

用户线程与内核线程中对应的关系有三种：多对一,一对一,多对多。

用户线程详述：
在用户空间实现的线程机制，不依赖于OS内核，由一组用户级的线程库函数来完成线程的管理，包括创建、终止、同步和调度等。

weiyigeek.top-用户线程图

优点：

• 用户线程由用户线程库管理调度,不需要操作系统内核了解用户线程存在(对于OS来说是透明的,可用于不支持线程技术的多进操作系统)
• 每个进程由有自己私有的线程控制块（TCB）列表,来跟踪记录各个线程状态信息(PC,栈指针,寄存器),TCB由线程库函数来维护。
• 用户线程的切换也是由线程库函数完成,无需用户态/核心态的切换(速度快)
• 运行每个线程拥有自定义线程调度算法

缺点：

• 如果一个线程发起系统调用而阻塞,则整个进程在等待。
• 当线程开始运行后,除非主动交出CPU控制权,否则它所在的进程当中的其他线程将无法运行。
• 由于时间片分配给进程,每个线程得到的时间片较少,执行会比较慢。

内核线程详述：
指在操作系统的内核当中实现的一种线程机制,由OS内核来完成线程的创建终止和管理,粒度小。

• 支持内核线程的OS中,由内核来维护进程和线程的上下文信息(PCB/TCB)
• 线程创建/中止/切换都是通过系统调用/内核函数的方式进行,由内核完成(系统开销比较大)
• 时间片分给线程，多线程的进程自动获得更多CPU时间
• 在一个进程中,内核线程发起系统调用而被阻塞,并不会影响其他内核线程的运行
• 在一个进程中,某个内核线程阻塞不影响其他线程运行
• Windows NT/2000/XP 支持内核线程

weiyigeek.top-内核线程图

轻量级进程(LightWeight Process):
她是内核支持的用户线程,一个进程可有一个或者多个轻量级进程,每个量级进程由一个单独的内核线程来支持(Solaris/Linux)

weiyigeek.top-轻量级进程

7.7 进程的上下文切换

( context switch)开始其他进程/线程时，需要在PCB/TCB中保存当前线程的信息，读取下一个线程的信息这些信息称为上下文
定义：停止当前运行的进程/线程(从运行状态改变成其他状态),并调度其他进程(转变成运行状态)的切换叫做上下文切换。

• 必须切换前存储进程上下文
• 必须能够在之后恢复他们,所有进程不能显示它曾经被暂停过
• 必须快速（上下文转换时,非常频繁）,因为有时间开销所以也要尽量避免

Q：需要存储什么上下文？
答：上下文具体包括：寄存器信息（程序计数器PC：程序执行阶段，栈指针SP：调用关系和局部变量位置），CPU状态

进程执行中需要关注寄存器，PC（进程执行到了什么地方），栈指针（调用关系，相应的局部变量位置）等;这些信息要被保存到PCB中，进程挂起时要把PCB的这些值重置，恢复到寄存器中去，使接下来进程可以继续在CPU上执行。

Q:需要知道哪些进程能切换？
PC为活跃进程准备了进程控制块PCB，OS将不同PCB放在不同的状态队列链表里便于选择

• 就绪队列
• 等待I/O队列—-分为每个设备的队列
• 僵尸队列

weiyigeek.top-进程的上下文切换

注意： 上下文切换的开销越小越好，且所有信息都与硬件紧密相连，所以OS中实现是用汇编代码。

7.8 进程的控制

创建、加载和执行进程：
Windows - CreateProcess(); Linux - fork()复制进程
Linux - exec() / system() / popen() 加载新程序,取代当前进程
优化方式：vfork() 轻量级fork(),Copy On Write只复制元数据，其他数据只在写操作时进行复制;

等待和终止进程：
父进程的wait() 和 子进程的exit() 配合完成子进程资源的回收；子进程调用exit()后，资源完成回收前的状态称为Zombie(僵尸)态；root进程也会定期进行资源回收;

(1)等待：wait()系统调用是被父进程用来等待子进程的结束，一个子进程向父进程返回一个值，父进程必须接受这个值并处理。

• Wait使父进程睡眠，当子进程调用exit时操作系统解锁父进程，将通过exit传递得到的返回值作为wait调用的一个结果（连同子进程的pid一起）。
• 关闭所有打开的文件和连接，释放内存，释放大部分支持进程的OS结构，检查父进程是否存活。
• 如果父进程存活，它保留exit结果的值直到父进程需要它，进入zombie/defunct状态。
• 如果父进程先于子进程死掉了，它释放所有的数据结构，这个进程死亡,最后清理所有等待的僵尸进程。

注意：ROOT进程/主动进程/RIT进程会定期扫描PCB列表，找到僵尸状态的进程并清理，使OS中不会僵尸越积越多;如果这里没有子进程存活,wait立刻返回;如果有父进程的僵尸等待，WAIT立即返回其中一个值并解除僵尸状态。

Q:为什么要让父进程等？而不是直接结束?
答：当进程执行完毕退出后，几乎所有资源都回收到OS中。但有个资源很难回收，就是PCB是代表进程存在的唯一标识，OS要依据PCB执行回收，这个功能由父进程完成。

(2) 僵尸状态：

• 调用了exit()但还没有wait返回的时候,将死/还没死;无法正常工作，只是等待被父进程回收。
• 执行EXEC()时，进程可以处于不同的状态。首先是runnig,然后是加载、运行,如果加载时间长要等 running->blocked 这个过程。