第二章、进程管理

1、进程与线程

1、进程的定义

1、程序的概念

1、一个指令序列，早期计算机（只支持单道程序）

2、进程的概念

1、进程是进程实体的运行过程，是系统进行资源飞陪喝调度的一个独立单位。

2、PCB（是一个数据结构，描述代码的各种信息）、程序段、数据段===进程实体。

3、一般也把进程实体成为进程

4、PCB是进程存在的唯一标识

3、进程和程序的区别

1、进程是动态的，程序是静态的

2、进程有独立性，能并发执行；程序不能并发执行

3、进程和程序没有对应关系

4、进程异步运行，相互制约；程序不具备此特征

5、进程与程序有密切联系：进程不能脱离具体程序虚设；程序规定了相应进程所要完成的动作

6、组成不同

①进程包含PCB、程序段、数据段

②程序包含数据和指令代码

7、程序包含了所有指令和数据的静态实体，不占用cpu和内存

8、进程由程序段、数据段和PCB构成，会占用系统的CPU和内存

9、程序可以启动多个进程共同完成

4、进程的特征

1、动态性

2、并发性

3、独立性：独立运行，独立获得资源

4、异步性：独自完成，按照不可预知的速度向前推进

5、结构性：有PCB

❗5、PCB

1、简介

1、PCB记录了操作系统所需的，描述进程当前情况，以及控制进程运行的全部信息

2、OS通过PCB来对并发执行的进程进行控制和管理

2、内容

1、进程描述信息：进程、用户标识符PID、UID

2、进程控制和管理信息：进程当前状态，进程的优先级

3、资源分配清单：程序段指针，数据段指针，鼠标，键盘

4、处理机相关信息：各种寄存器

2、进程的组织

1、系统有n个进程控制块（PCB），怎么让他们高效运行

1、链接方式

1、就是通过三个指针，控制三个队列

2、执行指针：执行队列

3、就绪队列指针：就绪队列

4、阻塞队列指针：阻塞队列

2、索引方式

1、三个指针，三个索引表

2、和上面对应

3、进程的状态

1、状态

1、就绪状态

2、运行状态

3、阻塞状态

4、创建状态

5、销毁状态

2、状态之间的转换

1、进程创建完毕——>进入就绪状态（当前CPU没有、IO资源就绪）——>进入运行态（当前进程被CPU调用，资源也到位）——>执行结束销毁状态（就是进程跑完了）

2、运行态（正在运行的进程）——>就绪状态（当前CPU没有、IO有）；是因为当前CPU被剥夺，抢走了

3、运行状态——>阻塞状态（CPU没有、IO也没有）；这种情况是因为进程自己做的决定，不想影响其他人

4、阻塞状态——>就绪状态：申请的资源得到了补充

5、图示

4、原语实现对进程的控制

1、原语概念

1、就是能对进程实现状态的转换

2、是一种特殊的程序

3、处于内核中，是操作系统的最底层，离硬件最近

4、原子程序运行有原子性，运行只能一气呵成，不可以中断

5、运行时间短，调度频繁

2、进程控制原语的相同点

1、更新PCB信息

2、将PCB放入合适的队列

3、分配、回收资源

3、原语控制进程操作

1、原语进程创建

1、申请空白PCB

2、分配资源

3、初始化PCB

4、插入就绪队列

2、原语销毁进程

1、操作类似

3、原语对进程的唤醒和阻塞

1、阻塞和唤醒必须成对的存在和使用

2、谁阻塞的进程，就由谁负责唤醒

4、原语对进程的切换

1、将运行环境信息存入PCB

2、PCB移入到要切换的队列

3、选择另外一个进程，然后更新PCB

4、根据PCB恢复新进程所需的运行环境运行

❗补充：考进程并发执行判断

1、利用公式套两个进程的R和W

2、R是=右边的变量

3、W是=左边的变量

4、R1∩R2 ∪R2∩R1 ∪W1∩W2

5、进程通信

1、是什么

1、就是进程之间的信息交换

2、每个进程的内存地址空间不一样，所以没有办法进程之间直接访问。

3、使用PV操作（低级通信方式）

4、使用、共享存储、消息传递、管道通信

❗补充：考试：进程的P、V操作描述工作过程

1、PV操作需要资源总量和信号量

2、P操作：会让信号量-1，如果信号量<=0就会阻塞

3、V操作：会让信号量+1

4、总结：P操作就是分配资源（信号资源就会减少-1），V操作就是释放、回收资源（信号量就会回来+1）

2、共享存储

1、顾名思义：就是有一块公共的空间，可以让任何进程访问

2、注意：这里的空间，只能一次进入一个进程，否则会有问题；我们使用PV同步互斥工具

1、通信等级

1、基于数据结构的共享——低级通信

2、基于存储区——高级通信

3、管道通信

1、半双工通信：某一个时间内只能实现单向传输；如果要双向同时进行（双端队列），就需要设置两个通道

2、如图

3、必须互斥访问通道

4、如果管道满了，就无法写了，write()就堵塞

5、如果管道空了，就无法读了，read()堵塞

6、没写满就不允许读，没有读就不允许写，和上面互斥呼应

7、只能一个进程，否则数据是谁的都不知道，就会读错

4、消息传递

1、有一格式化消息的单位（message）里面有消息头和消息体

2、消息头有：发送进程的ID，接收进程的ID，还有消息的类型，内容啥的

3、有两种消息传递的方式

1、直接通信方式

1、就是一个进程跑到另外一个进程，通过消息缓冲队列

2、间接通信方式

1、一个进程发消息了，要通过邮递员送信，另外一个进程才能收到

2、线程概念和多线程模型

1、为什么要引入线程？

1、要做很多事，但是线程只能执行一系列程序。所以引入线程帮忙分担

2、什么是线程

1、线程是一个基本的cpu执行单元

2、引入了线程，进程内的线程也可以并发。从而提高系统的并发

3、引入了线程，进程只需要管理线程内的资源分配单元（小弟）

3、引入线程带来的变化，线程的比较

1、图示

2、引入线程了，进程是资源分配的基本单位。线程是调度的基本单位

4、线程的属性

1、线程是处理机调度的单位

2、多CPU计算机，各个线程可以占用不同的CPU

3、线程也有：就绪、阻塞、运行

4、每个线程有ID，也有TCB

5、线程几乎不占用资源

6、、不同线程可以共享同一个进程的资源

7、线程切换不会引起进程的切换

8、切换线程开销小，切换进程开销大

5、线程的三种实现方式

1、用户级线程

1、通过线程库实现

2、用户态就可以切换

3、对用户透明，对操作系统不透明

4、用户的视角看，能看到的线程

2、内核级线程

1、通过操作系统内核完成

2、必须在核心态才能切换

3、操作系统内核视角看，能得到的线程

3、特殊组合方式

1、就是用户线程和内核级线程的综合

2、操作系统只“看得见”内核级线程，内核级线程才是处理机的分配的单位

3、看图理解

4、多线程的模型

1对1、1对多、多对多

1、一对一模型

1、如图

2、优点：并发强。可在多核处理机尚并行执行

3、缺点：一个进程会占用多个内核级线程，线程切换需要系统内核。但是成本高，开销大

2、一对多模型

1、如图

2、优点：用户线程在用户态就可以完成，不需要切换核心态。线程管理开销小，效率搞

3、缺点：只要一个用户级线程被阻塞，整个进程就堵塞了。并发不高，也不阔以在多核处理机上并行运行

3、多对多模型

1、效率最高

2、如图

3、克服了一对多的并发不高，克服一对一模型进程占用太多内核级线程，开销大。

❗根据习题和描述需要会画图

3、处理机的调度

1、处理机调度的概念及层次

1、概念

1、安装一定算法选择一个进程并将处理机分配给它

2、调度的三个层次

1、高级调度（作业调度）

1、按照规则，从外存上的后备队列挑选一个作业，给他们分配内存等必要资源。然后建立PCB、使该作业获得竞争处理机的权利

2、是外存和内存之间的调度。

3、作业调入会创建PCB，作业调出时会撤销PCB

4、图示

2、中级调度（内存调度）

1、将内存中暂时不用的进程，放到外存去，等要用了，再拿进来

2、目的：提高内存利用率，系统吞吐量

3、被掉到外存等待的进程状态叫：挂起状态

4、挂起状态的时候PCB不会一起走，会在常驻内存，因为操作系统通过PCB来对进程的监视

5、中级调度发生的次数会比高级调度高

6、图示

7、挂起状态是将进程映射到外存

3、低级调度（进程调度）

1、就是按照规则，从就绪队列取出一个进程，将处理机分配给它

2、最基本的一种调度

3、调度频率最高，几十毫秒调动一次

4、总结：三层调度的联系和对比

2、进程调度的时机

思维导图

1、时机

1、什么时候进行进程调度

1、需要进程切换的时候

2、当前运行最的进程主动放弃、或者被动放弃

2、什么时候不能进程调度

1、处理中断的过程中

2、操作系统内核程序的临界值

3、在原子操作过程中（一气呵成）

2、进程调度的方式

1、有剥夺式、和非剥夺式也叫抢占式、和非抢占式

1、剥夺式

1、一个进程正在运行，但有一个更重要的进程需要用处理机。处理机就被剥夺了

2、也可以实现时间片轮流执行的功能

3、可以理解为插队（但是插队有急事）

2、非剥夺式

1、只能正在执行的进程主动放弃处理机，否则都白搭

2、实现简单、系统开销小，无法及时处理紧急的任务

3、进程的切换

1、概念

1、一个进程让出处理机，让另一个进程使用

2、过程及作用

1、对让出进程的数据进行保存

2、对新的进程各种数据的准备（恢复）

3、注意

1、进程切换消耗系统资源，如果切换过多，一定会导致系统的效率降低。

4、调度的评价指标

1、CPU利用率

1、是CPu忙碌时间占总时间的比例

2、利用率：

2、系统吞吐量

1、单位时间内完成作业的数量

2、系统吞吐量：

3、周转时间

1、是作业被提交开始，到作业完成为止的时间总和

2、包括四个部分：作业调度（高级调度）时间、等待进程调度（低级调度）时间、进程在CPU中执行的时间、进程等待IO操作完成的时间

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

4、平均周转时间 =

5、带权周转时间 =

6、平均带权周转时间 =

4、等待时间

1、等待时间越长，用户越不满意

2、等待被服务的时间、等待建立进程后的时间、加上作业在外存后备队列中等待的时间

5、响应时间

1、用户提交请求到首次产生响应的时间

2、越早越好

5、作业/进程的调度算法

1、先来先服务算法（FCFS）

1、内容

1、按照进行、作业到达的先后顺序进行服务

2、非抢占式

3、优点：公平、简单

4、缺点：对长作业有利、对短作业不利

2、例子

2、短进程优先算法（SJF）

1、内容

1、这里的最短是指线程要服务的时间最短来进行排序

2、主要是追求最少平均等待时间、最少的平均周转时间等

3、是非抢占式

4、优点：追求最短平均等待时间、平均周转时间

5、缺点：不公平，对长作业不利，最短作业有利

2、例子

3、高响应比优先算法（HRRN）

1、内容

1、就是在先来先服务和短进程优先折中和吸收的一个算法

2、考虑进程的等待时间

3、响应比 =

4、等待时间就是线程到达了就绪队列在等待，一直到自己运行的那段时间

5、非抢占式

6、响应比：

• W：周转时间（完成时间-到达时间）

• T：该进程估计完成时间

7、缺点：吞吐连滴，不平衡。增加了系统的开销

2、例子

4、时间片轮转法（RR）

1、内容

1、公平的，轮流的执行n个时间片，当时间片用完，不管进程有没有执行完成，都得重新排队然后周而复始，直到完成。

2、是强占式，由时钟中断进行控制

❗考试要用

1、用一个表格进行计算

2、

5、优先级调度算法

1、内容

1、会有个优先级数，这个优先数越大，优先级别越高

2、第一个到达的时间如果优先级不高，其他级别的优先级还没到达，就会先执行第一个到达的进程

3、还有静态优先级和动态优先级之分。这里的意思见名知意

2、例子

1、例如

6、多级反馈队列调度算法

1、内容

1、这是对以上的算法的一种折中思想

2、设置了多级就绪队列，各个队列的优先级从高到低，时间片从小到大

3、先FCFS进行排队，然后时间片用完，就进入下一个队列级的队尾，就以此循环

2、例子

1、0时刻：P1进程进入第1级队列，运行时间为1，时间片为1，一个时间片结束，P1进程进入第2级队列。
1时刻：P2进程进入第1级队列，此时P1进程进入第2级队列；由于第1级队列大于第2级队列，所以P2进行在第1级队列运行一个时间片，然后进入第2级队列。此时第2级队列有P1进程和P2进程。
2、2-4时刻：第1级队列为空，则调度第2级队列中的进程。先调度P1进程，运行2个时间片，然后进入第3级队列。接着调度P2，此时只运行了1个单位的时间。时间片还没有用完的情况下，时刻5到了，P3进程进入第1级队列。
3、5时刻：此时P2只运行了1个单位的时间。时间片还没有用完，时刻5到了，P3进程进入第1级队列。第1级队列大于第2级队列，于是先让P3使用CPU一个时间片。P2重新回到第2级队列的队尾。
接下来就是第2级队列中的P2进程，运行一个单位的时间，调出内存。最后当第1级队列，第2级队列为空时，开始第3级队列的P1，分配处理机。运行结束，调出内存。

4、进程的同步与互斥

1、进程的同步与互斥

1、进程同步

1、同步=直接制约关系，并发带了问题，所以需要同步去解决。

2、异步：各并发执行的进程以各自独立的、不可预知的速度向前推进

2、进程互斥

1、互斥=间接制约关系。系统只有一个资源，但是很多进程都想用，所以就引出了互斥的概念，用互斥来管理进程对资源的调用。

2、临界资源：一段时间内只允许一个进程使用的资源

3、对临界资源的互斥访问分为四个部分

• 进入区
• 临界区
• 退出区
• 剩余区

1、进程进入临界区需要遵守的规则

1、空闲让进

2、忙则等待：这里的忙是指临界资源

3、有限等待：为了避免饥饿

4、让权等待：如果进程进入不了进阶区，就要立即释放处理机。

2、操作系统信号量（也叫信号灯）

1、什么是信号量机制

1、一对原语：P、V操作，来对信号量进行操作

2、这个机制是一气呵成，不能被中断

3、P：请求一个资源

4、V：释放一个资源