导图社区 第二章 进程与线程
- 48
- 2
- 1
- 举报
第二章 进程与线程
这样的话应用程序就可以执行多个线程并进行相应的控制。 线程和进程的区别三 通过了解逻辑角度我们可以得知,多线程这样的意义是相对于在一个应用程序里面的,能够同时的执行。
编辑于2022-09-12 00:35:22 浙江省- 考研操作系统
- 408操作系统第二章
- 相似推荐
- 大纲
第二章 进程与线程
进程与线程
进程的概念和特征
概念
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
组成
进程控制块（PCB）
PCB是进程存在的唯一标志
进程描述信息
进程标识符（PID）、用户标识符（UID）
进程控制和管理信息
进程当前状态、进程优先级、代码运行入口地址、程序的外存地址、进入内存时间、处理机占用时间、信号量使用
资源分配清单
代码段指针、数据段指针、堆栈段指针、文件描述符、键盘、鼠标
处理机相关信息
通用寄存器值、地址寄存器值、控制寄存器值、标志寄存器值、状态字
程序段
程序的代码（指令序列）
数据段
运行过程中产生的各种数据（如：程序定义的变量）
特征
动态性（进程最基本的特征）
进程是程序的一次执行，是动态地产生、变化和消亡的
并发性（是进程的重要特征，也是操作系统的重要特征）
多个进程实体同存与内存中，是进程能和其他进程并发执行
独立性
指进程实体是一个能独立运行、独立获得资源和接受调度的基本单位
异步性
异步性会导致执行结果非不可再现性（不确定性），为此在操作系统中必须配置相应的进程同步机制
由于进程的相互制约，使得进程按各自独立的、不可预知的速度向前推进
结构性
每个进程都会配置一个PCB，结构上看，进程由程序段、数据段、PCB组成
进程的组织方式
链接方式
将同一状态的PCB链接成一个队列，不同状态对应不同的队列，也可把处于阻塞态的进程的PCB，根据其阻塞原因的不同，排成多个阻塞队列，操作系统持有指向各个队列的指针
索引方式
将同一状态的进程组织在一个索引表中，索引表的表项指向相应的PCB，不同状态对应不同的索引表，如就绪索引表和阻塞索引表等，操作系统持有指向各个索引表的指针
进程的状态与转换
状态
运行态
CPU √ 其他所需资源 √
就绪态
CPU × 其他所需资源 √
阻塞态
CPU × 其他所需资源 ×
创建态
操作系统为新进程分配资源，创建PCB
结束态（终止态）
操作系统回收进程的资源、撤销PCB
进程间状态的转换
就绪态->运行态
进程被调度
运行态->就绪态
时间片到，或CPU被其他高优先级的进程抢占
运行态->阻塞态
等待系统分配资源，或等待某事件发生（主动行为）
阻塞态->就绪态
资源分配到位，等待的事件发生（被动行为）
创建态->就绪态
系统完成创建进程的相关操作
运行态->终止态
进程运行结果，或运行过程中遇到不可修复的错误
进程控制
基本概念
进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能
进程控制用原语实现
原语用开/关中断来实现
原语是一种特殊的程序
原语的执行必须一气呵成，不可中断
相关原语
进程的创建
创建原语
申请空白PCB
为新进程分配所需资源
初始化PCB
将PCB插入就绪队列
引起进程创建的事件
用户登录
分时系统中，用户登录成功，系统会为其建立一个新的进程
作业调度
多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程
提供服务
用户向操作系统提出某些请求时，会新建一个进程处理该请求
应用请求
由用户进程主动请求创建一个子进程
进程的终止
撤销原语
从PCB集合中找到终止进程的PCB
若进程正在运行，立即剥夺CPU，将CPU分配给其他进程
终止其所有子进程（进程间的关系是树形结构）
将该进程拥有的所有资源归还给父进程或操作系统
删除PCB
引起进程终止的事件
正常结束
进程自己请求终止（exit系统调用）
异常结束
整数除以0，非法使用特权指令，然后被操作系统强行杀掉
外界干预
Ctrl+Alt+delete，用户选择杀掉进程
进程的阻塞
阻塞原语（Block）
找到要阻塞的进程对应的PCB
保护进程运行现场，将PCB状态信息设置为“阻塞态”，暂时停止进程运行
将PCB插入相应事件的等待队列
引起进程阻塞的事件
需要等待系统分配某种资源
需要等待相互合作的其他进程完成工作
进程的唤醒
唤醒原语(Wakeup)
在事件等待队列中找到PCB
将PCB从等待队列移除，设置进程为就绪态
将PCB插入就绪队列，等待被调度
引起进程唤醒的事件
等待的事件发生
进程的切换
切换原语
将运行环境信息存入PCB
PCB移入相应队列
选择另一个进程执行，并更新其PCB
根据PCB恢复新进程所需的运行环境
引进进程切换的事件
当前进程时间片到
有更到优先级的进程到达
当前进程主动阻塞
当前进程终止
进程的通信
共享存储（P/V操作）
设置一个共享内存区域，并映射到进程的虚拟空间地址
要互斥地访问共享空间（由通信进程自己负责实现互斥）
两种方式
基于数据结构（低级）
基于存储区的共享（高级、速度快）
消息传递
传递结构化的消息（消息头/消息体）
系统提供“发送/接受原语”
两种方式
直接通信方式
消息直接挂到接收进程的消息队列里
间接（信箱）通信方式
消息先发到中间体（信箱）
管道通信
设置一个特殊的共享文件（管道），其实就是一个内存缓冲区
一个管道只能实现半双工通信
实现双向同时通信要建立两个管道
各进程要互斥访问管道（由操作系统负责实现互斥）
管道写满时，写进程阻塞。管道读空时，读进程阻塞
线程和多线程模型
一个基本的CPU执行单元，也是程序执行流的最小单元
线程的组成：线程ID、程序计数器、寄存器集合和堆栈
线程的实现方式
用户级线程
从用户视角能看到的线程，由线程库实现
内核级线程
从操作系统视角看到的进程，由操作系统实现（内核级线程才是处理机分配的单位）
组合方式
上述两种方式的结合
多线程模型
一对一模型
一个用户级线程映射到一个内核级线程
优点：各个线程可分配到多核处理机并行执行，并发度高
缺点：线程管理都需要操作系统支持，开销大
多对一模型
多个用户级线程映射到一个内核级线程
优点：线程管理开销小效率高
缺点：一个线程阻塞会导致整个进程都被阻塞（并发度低）
多对多模型
n个用户级线程映射到m个内核级线程（n≥m）
既克服了多对一模型并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点。此外，还拥有以上两种模型各自的优点
线程与进程的比较
调度
在传统的操作系统中，拥有资源和独立调度的基本单位都是进程，每次调度都要进行上下文切换，开销较大
在引入线程的操作系统中，线程是独立调度的基本单位，而线程切换的代价远低于进程
并发性
传统进程机制中，只能进程间并发
引入线程后，各线程间也能并发，提升了并发度
拥有资源
进程是系统中拥有资源的基本单位，而线程不拥有系统资源（仅有一点必不可少、能保证独立运行的资源），但线程可以访问其隶属进程的系统资源
独立性
每个进程都拥有独立的地址空间和资源，除了共享全局变量，不允许其他进程访问。某进程中的线程对其他进程不可见
同一进程中的不同线程是为了提高并发性及进行相互之间的合作而创建的，它们共享进程的地址空间和资源
系统开销
传统的进程间并发，需要切换进程的运行环境，系统开销很大
线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小
支持多处理机系统
对于传统单线程进程，不管由多少处理机，进程只能运行在一个处理机上
对于多线程进程，可以将进程中的多个线程分配到多个处理机上执行
线程的属性
线程是处理机的独立调度单位，多个线程是可以并发执行的。在单CPU的计算机系统中，各线程可交替地占用CPU；在多CPU的计算机系统中，各线程可同时占用不同的CPU。若各个CPU同时为一个进程内的各线程服务，则可缩短进程的处理时间
线程是一个轻型实体，它不拥有系统资源，但每个线程都应有一个唯一的标识符和一个线程控制块（TCB），线程控制块记录了线程执行的寄存器和栈等现场状态
不同的进程可以执行相同的程序，即同一个服务程序被不同的用户调用时，操作系统把它们创建成不同的线程
同一个进程中的各个线程共享该进程所拥有的资源
一个线程被创建后，便开始了它的生命周期，直至终止。线程在生命周期内会经历阻塞态、就绪态和运行态等各种状态变化
由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
同一进程中的线程切换，不会引起进程切换，系统开销很小
不同进程中的线程切换，会引起进程切换，系统开销较大
死锁
死锁的概念
什么是死锁
指多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进
死锁、饥饿、死循环的区别
死锁：至少是两个进程一起死锁，死锁进程处于阻塞态
饥饿，可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪
死循环：可能只有一个进程发生死循环，死循环的进程可上处理机
死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的
死锁产生的必要条件
互斥条件
对必须互斥使用的资源的争抢才会导致死锁
不剥夺条件
进程保持的资源只能主动释放，不可强行剥夺
请求和保持条件
保持着某些资源不放的同时，请求别的资源
循环等待条件
存在一种进程资源的循环等待链
循环等待未必死锁，死锁一定有循环等待
死锁产生的原因
系统资源的竞争
进程推进顺序非法
信号量使用不当
什么时候会发生死锁
对不可剥夺资源的不合理分配，可能导致死锁
死锁的处理策略
预防死锁
破坏死锁产生的四个必要条件
避免死锁
避免系统进入不安全状态（银行家算法）
死锁的检测和解除
允许死锁发生，系统负责检测出死锁并解除
死锁的处理
不允许死锁发生
静态策略：预防死锁
破坏互斥条件
将临界资源改造为可共享使用的资源（如SPOOLing技术）
缺点：可行性不高，很多时候无法破坏互斥条件
破坏不剥夺条件
方案一：申请的资源得不到满足时，立即释放拥有的所有资源
方案二：申请的资源被其他进程占用时，由操作系统协助剥夺（考虑优先级）
缺点：实现负杂；剥夺资源可能导致部分工作失效； 反复申请和释放导致系统开销大；可能导致饥饿
破坏请求和保持条件
运行前分配好所有需要的资源，之后一直保持
缺点：资源利用率低；可能导致饥饿
破坏循环等待条件
给资源编号，必须按编号从小到大的顺序申请资源
缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦
动态策略：避免死锁
避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配的安全性。若此次分配不会导致系统进入不安全状态，则允许分配；否则让进程等待
并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态
银行家算法
允许死锁发生
死锁的检测和解除
如何检测
数据结构：资源分配图
两种结点
进程结点（圆圈）
资源结点（方框）
两种边
请求边（进程结点->资源结点）
分配边（资源结点->进程结点）
死锁检测算法
依次消除与不阻塞进程相连的边，直到无边可消
注：所谓不阻塞进程是指其申请的资源数还足够的进程
死锁定理：若资源分配图是不可完全简化的，说明发生了死锁
如何解除
资源剥夺法
撤销进程法（终止进程法）
进程回退法
同步与互斥
同步与互斥的基本概念
进程同步（同步亦称直接制约关系）
并发性带来了异步性，有时需要通过进程同步解决这种异步问题 有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序
进程互斥（互斥也称间接制约关系）
对临界资源的访问，需要互斥的进行。即同一段时间内只能允许一个进程访问该资源
访问临界资源的四个部分
进入区（检查是否可进入临界区，若可进入，需要“上锁”）
临界区（访问临界资源的那段代码）
退出区（负责“解锁”）
剩余区（其余代码部分）
同步机制遵循原则
空闲让进
临界区空闲时，应允许一个进程访问
忙则等待
临界区正在被访问时，其他视图访问的进程需要等待
有限等待
要在有限时间内进入临界区，保证不会饥饿
让权等待
进不了临界区的进程，要释放处理机，防止忙等
子主题
进程互斥的软件实现方法
单标志法
在进入区只做“检查”，不“上锁”
在退出区把临界区的使用权转交给另一个进程 （相当于在退出区既给另一进程“解锁”，又给自己“上锁”）
主要问题：不遵循“空闲让进”原则
双标志法先检查
在进入区先“检查”后“上锁”，退出区“解锁”
主要问题：不遵循“忙则等待”原则
双标志法后检查
在进入区先“加锁”后“检查”，退出区“解锁”
主要问题：不遵循“空闲让进、有限等待”原则，可能导致“饥饿”
Peterson算法
在进入区“主动争取—主动谦让—检查对方是否想进、己方是否谦让”
主要问题：不遵循“让权等待”原则，会发生“忙等”
进程互斥的硬件实现方法
中断屏蔽方法
使用“开/关中断”指令实现
优点：简单高效
缺点：只适用于单处理机，只适用于操作系统内核进程，不适用于用户进程
硬件指令方法
指令
TestAndSet指令（TS指令/TSL指令）
Swap指令（XCHG指令）
优点：实现简单；适用于多处理机环境
缺点：进程等待进入临界区时要耗费处理机时间，不满足“让权等待”，会导致“饥饿”现象
互斥锁
需忙等，进程时间片用完才下处理机，违反“让权等待”
常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区；不太适用于单处理机系统，忙等的过程中不可能解锁
等待期间不用切换上下文，多处理器系统中，若上锁的时机较短，则等待代价很低
原子操作
acquire()（获得锁）
release()（释放锁）
信号量
整型信号量
用一个整数型变量作为信号量，数值表示某种资源数
整型信号量与普通整型变量的区别：对信号量只能执行初始化、P、V三种操作（P、V操作是一种低级进程通信原语）
整型信号量存在的问题：不满足让权等待原则
记录型信号量
S.value表示某种资源数，S.L指向等待该资源的队列
P操作中，一定是先S.value--，之后可能需要执行block原语
V操作中，一定是先S.value++，之后可能需要执行wakeup原语
注意：要能够自己推断在什么条件下需要执行block或wakeup
可以用记录型信号量实现系统资源的“申请”和“释放”
可以用记录型信号量实现进程互斥、进程同步
利用信号量实现同步
分析问题，确定临界区
设置互斥信号量，初值为1
临界区之前对信号量执行P操作
临界区之后对信号量执行V操作
利用信号量实现进程互斥
分析问题，找出哪里需要实现“一前一后”的同步关系
设置同步信号量，初始值为0
在“前操作”之后执行V操作
在“后操作”之前执行P操作
利用信号量实现前驱关系
分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题
为每一对前驱关系设置同步信号量，初值为0
在每个“前操作”之后执行V操作
在每个“后操作”之前执行P操作
分析进程同步和互斥问题的方法步骤
1.关系分析
2.整理思路
3.设置信号量
管程
为什么要引入管程
解决信号量机制编程麻烦、易出错的问题
组成
管程的名称
局部于管程内部的共享数据结构说明
对该数据结构进行操作的一组过程（或函数）
对局部于管程内部的共享数据设置初始值的语句
基本特征
局部于管程的数据只能被局部于管程的过程所访问
一个进程只有通过调用管程内的过程才能进入管程访问共享数据
每次仅允许一个进程在管程内执行某个内部过程
补充
各进程必须互斥访问管程的特性是由编译器实现的
可在管程中设置条件变量及等待/唤醒操作以解决同步问题
经典同步问题
生产者-消费者问题
读者-写者问题
哲学家进餐问题
吸烟者问题
处理机调度
调度的概念
基本概念
按某种算法选择一个进程将处理机分配给它
三个层次
高级调度（作业调度）
按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程
中级调度（内存调度）
按照某种规则，从挂起队列中选择合适的进程将其数据调回内存
低级调度（进程调度）
按照某种规则，从就绪队列中选择一个进程为其分配处理机
三层调度的联系、对比
高级调度
外存->内存（面向作业）
发生频率：最低
中级调度
外存->内存（面向进程）
发生频率：中等
低级调度（最基本，不可或缺）
内存->CPU
发生频率：最高
补充知识
为减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存从而变为“挂起态”
七状态模型：在五状态模型的基础上加入了“就绪挂起”和“阻塞挂起”两种状态
调度的评价指标
CPU利用率
指CPU“忙碌的”时间占总时间的比例
利用率=忙碌的时间/总时间
系统吞吐量
表示单位时间内CPU完成作业的数量
系统吞吐量=总共完成了多少道作业/总共花了多少时间
周转时间
指从作业提交到作业完成所经历的时间
周转时间=作业完成时间-作业提交时间
平均周转时间=各作业周转时间之和/作业数
带权周转时间=作业周转时间/作业实际运行的时间
平均带权周转时间=各作业带权周转时间之和/作业数
等待时间
进程/作业等待被服务的时间之和
平均等待时间即各个进程/作业等待时间的平均值
响应时间
从用户提交请求到首次产生响应所用的时间
调度的实现
调度程序（调度器）
操作系统中用于调度和分派CPU的组件
组成
排队器
分派器
上下文切换器
调度的时机
什么时候需要进程调度？
主动放弃处理机
进程正常终止
运行过程中发生异常而终止
主动阻塞（如等待I/O）
被动放弃处理机
分给进程的时间片用完
有更紧急的事情需要处理（如I/O中断）
有更高优先级的进程进入就绪队列
什么时候不能进行进程调度？
在处理中断的过程中
进程在操作系统内核临界区中
其他需要完全屏蔽中断的原子操作过程中
调度的切换与过程
狭义的“调度”和“切换”的区别
调度是指决定资源分配给哪个进程的行为，是一种决策行为
切换是指实际分配的行为，是执行行为
一般来说，先有资源的调度，然后才有进程的切换
切换过程
对原来运行进程各种数据的保存
对新的进程各种数据的恢复
重要结论：进程调度、切换是有代价的，并不是调度越频繁，并发度就越高
调度的方式
非剥夺调度方式（非抢占式）
只能由当前运行的进程主动放弃CPU
优点：实现简单、系统开销小
缺点：无法及时处理紧急任务，适合于早期的批处理系统
剥夺调度方式（抢占式）
可由操作系统剥夺当前进程的CPU使用权
优点：提高系统吞吐量和响应效率
缺点：“抢占”不是一种任意性行为，必须遵循一定的原则
闲逛进程
在进程切换时，如果系统中没有就绪进程，就会调度闲逛进程运行
闲逛进程不需要CPU之外的资源，它不会被阻塞
特性
优先级最低
可以是0地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）
能耗低
两种线程的调度
用户级线程调度
内核级线程调度
典型的调度算法
先来先服务（FCFS）调度算法
算法思想：主要从“公平”的角度考虑
算法规则：按照作业/进程到达的先后顺序进行服务
可以用于作业调度和进程调度
非抢占式的算法
优点：公平、算法实现简单
缺点：效率低，带权周转时间很大。对长作业比较有利，但对短作业不利；有利于CPU繁忙型作业，而不利于I/O繁忙型作业。
不会导致饥饿
短作业优先（SJF）调度算法
算法思想：追求最少的平均等到时间，最少的平均周转时间，最少的平均带权周转时间
算法规则：最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）
可以用于作业调度和进程调度
有非抢占式和抢占式版本（最短剩余时间优先算法（SRTN））
优点：“最短的”平均等待时间、平均周转时间
缺点：不公平，对短作业有利，对长作业不利，可能产生饥饿现象。完全未考虑作业的紧迫程度。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。
会导致饥饿
高响应比优先（HRRN）调度算法
算法思想：要综合考虑作业/进程的等待时间和要求服务的时间
算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务 响应比=（等待时间+要求服务时间）/要求服务时间
可以用于作业调度和进程调度
非抢占式的算法
优缺点：综合考虑了等待时间和运行时间 等待时间相同时，要求服务时间短的优先（SJF的优点） 要求服务时间相同时，等待时间长的优先（FCFS的优点） 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大从而避免了长作业饥饿的问题
不会导致饥饿
时间片轮转（RR）调度算法
算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队
用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）
抢占式算法，由时钟装置发出时钟中断来通知CPU时间片已到
优点：公平；响应快；适用于分时操作系统
缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度
不会导致饥饿
时间片太大，退化为先来先服务调度算法 时间片太小，开销增大，真正用于运行用户进程的时间将减少
优先级调度算法
算法思想：根据任务的紧急程度来决定处理顺序
算法规则：调度时选择优先级最高的作业/进程
可以用于作业调度和进程调度
有抢占式和非抢占式两个版本
优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度
缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
会导致饥饿
优先级
静态优先级（创建进程时确定，整个运行期间保持不变）
动态优先级（根据进程情况的变化动态调整优先级）
优先级设置参考原则
系统进程>用户进程
交互型进程>非交互型进程（或前台进程>后台进程）
I/O型进程>计算型进程
多级队列调度算法
多级反馈队列调度算法
算法思想：对其他调度算法的折中权衡
算法规则： 1.设置多级就绪队列，各级队列优先级从高到低，时间片从小到大 2.新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾 3.只有第k级队列为空时，才会为第k+1级队头的进程分配时间片
用于进程调度
抢占式算法
优缺点：对各类型进程都很公平（FCFS的优点）；每个新到达的进程都可以很快就得到响应（RR的优点）；短进程只用较少的时间就可完成（SPF的优点）；不必实现估计进程的运行时间（避免用户作假）；可灵活地调整对各类进程的偏好程度
会导致饥饿
进程切换
上下文切换（实质上是指处理机从一个进程的运行转到另一个进程上运行，只发生在内核态）
模式切换（用户态和内核态之间的切换）
第二章 进程与线程
进程与线程
进程的概念和特征
概念
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
组成
进程控制块（PCB）
PCB是进程存在的唯一标志
进程描述信息
进程标识符（PID）、用户标识符（UID）
进程控制和管理信息
进程当前状态、进程优先级、代码运行入口地址、程序的外存地址、进入内存时间、处理机占用时间、信号量使用
资源分配清单
代码段指针、数据段指针、堆栈段指针、文件描述符、键盘、鼠标
处理机相关信息
通用寄存器值、地址寄存器值、控制寄存器值、标志寄存器值、状态字
程序段
程序的代码（指令序列）
数据段
运行过程中产生的各种数据（如：程序定义的变量）
特征
动态性（进程最基本的特征）
进程是程序的一次执行，是动态地产生、变化和消亡的
并发性（是进程的重要特征，也是操作系统的重要特征）
多个进程实体同存与内存中，是进程能和其他进程并发执行
独立性
指进程实体是一个能独立运行、独立获得资源和接受调度的基本单位
异步性
异步性会导致执行结果非不可再现性（不确定性），为此在操作系统中必须配置相应的进程同步机制
由于进程的相互制约，使得进程按各自独立的、不可预知的速度向前推进
结构性
每个进程都会配置一个PCB，结构上看，进程由程序段、数据段、PCB组成
进程的组织方式
链接方式
将同一状态的PCB链接成一个队列，不同状态对应不同的队列，也可把处于阻塞态的进程的PCB，根据其阻塞原因的不同，排成多个阻塞队列，操作系统持有指向各个队列的指针
索引方式
将同一状态的进程组织在一个索引表中，索引表的表项指向相应的PCB，不同状态对应不同的索引表，如就绪索引表和阻塞索引表等，操作系统持有指向各个索引表的指针
进程的状态与转换
状态
运行态
CPU √ 其他所需资源 √
就绪态
CPU × 其他所需资源 √
阻塞态
CPU × 其他所需资源 ×
创建态
操作系统为新进程分配资源，创建PCB
结束态（终止态）
操作系统回收进程的资源、撤销PCB
进程间状态的转换
就绪态->运行态
进程被调度
运行态->就绪态
时间片到，或CPU被其他高优先级的进程抢占
运行态->阻塞态
等待系统分配资源，或等待某事件发生（主动行为）
阻塞态->就绪态
资源分配到位，等待的事件发生（被动行为）
创建态->就绪态
系统完成创建进程的相关操作
运行态->终止态
进程运行结果，或运行过程中遇到不可修复的错误
进程控制
基本概念
进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能
进程控制用原语实现
原语用开/关中断来实现
原语是一种特殊的程序
原语的执行必须一气呵成，不可中断
相关原语
进程的创建
创建原语
申请空白PCB
为新进程分配所需资源
初始化PCB
将PCB插入就绪队列
引起进程创建的事件
用户登录
分时系统中，用户登录成功，系统会为其建立一个新的进程
作业调度
多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程
提供服务
用户向操作系统提出某些请求时，会新建一个进程处理该请求
应用请求
由用户进程主动请求创建一个子进程
进程的终止
撤销原语
从PCB集合中找到终止进程的PCB
若进程正在运行，立即剥夺CPU，将CPU分配给其他进程
终止其所有子进程（进程间的关系是树形结构）
将该进程拥有的所有资源归还给父进程或操作系统
删除PCB
引起进程终止的事件
正常结束
进程自己请求终止（exit系统调用）
异常结束
整数除以0，非法使用特权指令，然后被操作系统强行杀掉
外界干预
Ctrl+Alt+delete，用户选择杀掉进程
进程的阻塞
阻塞原语（Block）
找到要阻塞的进程对应的PCB
保护进程运行现场，将PCB状态信息设置为“阻塞态”，暂时停止进程运行
将PCB插入相应事件的等待队列
引起进程阻塞的事件
需要等待系统分配某种资源
需要等待相互合作的其他进程完成工作
进程的唤醒
唤醒原语(Wakeup)
在事件等待队列中找到PCB
将PCB从等待队列移除，设置进程为就绪态
将PCB插入就绪队列，等待被调度
引起进程唤醒的事件
等待的事件发生
进程的切换
切换原语
将运行环境信息存入PCB
PCB移入相应队列
选择另一个进程执行，并更新其PCB
根据PCB恢复新进程所需的运行环境
引进进程切换的事件
当前进程时间片到
有更到优先级的进程到达
当前进程主动阻塞
当前进程终止
进程的通信
共享存储（P/V操作）
设置一个共享内存区域，并映射到进程的虚拟空间地址
要互斥地访问共享空间（由通信进程自己负责实现互斥）
两种方式
基于数据结构（低级）
基于存储区的共享（高级、速度快）
消息传递
传递结构化的消息（消息头/消息体）
系统提供“发送/接受原语”
两种方式
直接通信方式
消息直接挂到接收进程的消息队列里
间接（信箱）通信方式
消息先发到中间体（信箱）
管道通信
设置一个特殊的共享文件（管道），其实就是一个内存缓冲区
一个管道只能实现半双工通信
实现双向同时通信要建立两个管道
各进程要互斥访问管道（由操作系统负责实现互斥）
管道写满时，写进程阻塞。管道读空时，读进程阻塞
线程和多线程模型
一个基本的CPU执行单元，也是程序执行流的最小单元
线程的组成：线程ID、程序计数器、寄存器集合和堆栈
线程的实现方式
用户级线程
从用户视角能看到的线程，由线程库实现
内核级线程
从操作系统视角看到的进程，由操作系统实现（内核级线程才是处理机分配的单位）
组合方式
上述两种方式的结合
多线程模型
一对一模型
一个用户级线程映射到一个内核级线程
优点：各个线程可分配到多核处理机并行执行，并发度高
缺点：线程管理都需要操作系统支持，开销大
多对一模型
多个用户级线程映射到一个内核级线程
优点：线程管理开销小效率高
缺点：一个线程阻塞会导致整个进程都被阻塞（并发度低）
多对多模型
n个用户级线程映射到m个内核级线程（n≥m）
既克服了多对一模型并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点。此外，还拥有以上两种模型各自的优点
线程与进程的比较
调度
在传统的操作系统中，拥有资源和独立调度的基本单位都是进程，每次调度都要进行上下文切换，开销较大
在引入线程的操作系统中，线程是独立调度的基本单位，而线程切换的代价远低于进程
并发性
传统进程机制中，只能进程间并发
引入线程后，各线程间也能并发，提升了并发度
拥有资源
进程是系统中拥有资源的基本单位，而线程不拥有系统资源（仅有一点必不可少、能保证独立运行的资源），但线程可以访问其隶属进程的系统资源
独立性
每个进程都拥有独立的地址空间和资源，除了共享全局变量，不允许其他进程访问。某进程中的线程对其他进程不可见
同一进程中的不同线程是为了提高并发性及进行相互之间的合作而创建的，它们共享进程的地址空间和资源
系统开销
传统的进程间并发，需要切换进程的运行环境，系统开销很大
线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小
支持多处理机系统
对于传统单线程进程，不管由多少处理机，进程只能运行在一个处理机上
对于多线程进程，可以将进程中的多个线程分配到多个处理机上执行
线程的属性
线程是处理机的独立调度单位，多个线程是可以并发执行的。在单CPU的计算机系统中，各线程可交替地占用CPU；在多CPU的计算机系统中，各线程可同时占用不同的CPU。若各个CPU同时为一个进程内的各线程服务，则可缩短进程的处理时间
线程是一个轻型实体，它不拥有系统资源，但每个线程都应有一个唯一的标识符和一个线程控制块（TCB），线程控制块记录了线程执行的寄存器和栈等现场状态
不同的进程可以执行相同的程序，即同一个服务程序被不同的用户调用时，操作系统把它们创建成不同的线程
同一个进程中的各个线程共享该进程所拥有的资源
一个线程被创建后，便开始了它的生命周期，直至终止。线程在生命周期内会经历阻塞态、就绪态和运行态等各种状态变化
由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
同一进程中的线程切换，不会引起进程切换，系统开销很小
不同进程中的线程切换，会引起进程切换，系统开销较大
死锁
死锁的概念
什么是死锁
指多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进
死锁、饥饿、死循环的区别
死锁：至少是两个进程一起死锁，死锁进程处于阻塞态
饥饿，可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪
死循环：可能只有一个进程发生死循环，死循环的进程可上处理机
死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的
死锁产生的必要条件
互斥条件
对必须互斥使用的资源的争抢才会导致死锁
不剥夺条件
进程保持的资源只能主动释放，不可强行剥夺
请求和保持条件
保持着某些资源不放的同时，请求别的资源
循环等待条件
存在一种进程资源的循环等待链
循环等待未必死锁，死锁一定有循环等待
死锁产生的原因
系统资源的竞争
进程推进顺序非法
信号量使用不当
什么时候会发生死锁
对不可剥夺资源的不合理分配，可能导致死锁
死锁的处理策略
预防死锁
破坏死锁产生的四个必要条件
避免死锁
避免系统进入不安全状态（银行家算法）
死锁的检测和解除
允许死锁发生，系统负责检测出死锁并解除
死锁的处理
不允许死锁发生
静态策略：预防死锁
破坏互斥条件
将临界资源改造为可共享使用的资源（如SPOOLing技术）
缺点：可行性不高，很多时候无法破坏互斥条件
破坏不剥夺条件
方案一：申请的资源得不到满足时，立即释放拥有的所有资源
方案二：申请的资源被其他进程占用时，由操作系统协助剥夺（考虑优先级）
缺点：实现负杂；剥夺资源可能导致部分工作失效； 反复申请和释放导致系统开销大；可能导致饥饿
破坏请求和保持条件
运行前分配好所有需要的资源，之后一直保持
缺点：资源利用率低；可能导致饥饿
破坏循环等待条件
给资源编号，必须按编号从小到大的顺序申请资源
缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦
动态策略：避免死锁
避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配的安全性。若此次分配不会导致系统进入不安全状态，则允许分配；否则让进程等待
并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态
银行家算法
允许死锁发生
死锁的检测和解除
如何检测
数据结构：资源分配图
两种结点
进程结点（圆圈）
资源结点（方框）
两种边
请求边（进程结点->资源结点）
分配边（资源结点->进程结点）
死锁检测算法
依次消除与不阻塞进程相连的边，直到无边可消
注：所谓不阻塞进程是指其申请的资源数还足够的进程
死锁定理：若资源分配图是不可完全简化的，说明发生了死锁
如何解除
资源剥夺法
撤销进程法（终止进程法）
进程回退法
同步与互斥
同步与互斥的基本概念
进程同步（同步亦称直接制约关系）
并发性带来了异步性，有时需要通过进程同步解决这种异步问题 有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序
进程互斥（互斥也称间接制约关系）
对临界资源的访问，需要互斥的进行。即同一段时间内只能允许一个进程访问该资源
访问临界资源的四个部分
进入区（检查是否可进入临界区，若可进入，需要“上锁”）
临界区（访问临界资源的那段代码）
退出区（负责“解锁”）
剩余区（其余代码部分）
同步机制遵循原则
空闲让进
临界区空闲时，应允许一个进程访问
忙则等待
临界区正在被访问时，其他视图访问的进程需要等待
有限等待
要在有限时间内进入临界区，保证不会饥饿
让权等待
进不了临界区的进程，要释放处理机，防止忙等
子主题
进程互斥的软件实现方法
单标志法
在进入区只做“检查”，不“上锁”
在退出区把临界区的使用权转交给另一个进程 （相当于在退出区既给另一进程“解锁”，又给自己“上锁”）
主要问题：不遵循“空闲让进”原则
双标志法先检查
在进入区先“检查”后“上锁”，退出区“解锁”
主要问题：不遵循“忙则等待”原则
双标志法后检查
在进入区先“加锁”后“检查”，退出区“解锁”
主要问题：不遵循“空闲让进、有限等待”原则，可能导致“饥饿”
Peterson算法
在进入区“主动争取—主动谦让—检查对方是否想进、己方是否谦让”
主要问题：不遵循“让权等待”原则，会发生“忙等”
进程互斥的硬件实现方法
中断屏蔽方法
使用“开/关中断”指令实现
优点：简单高效
缺点：只适用于单处理机，只适用于操作系统内核进程，不适用于用户进程
硬件指令方法
指令
TestAndSet指令（TS指令/TSL指令）
Swap指令（XCHG指令）
优点：实现简单；适用于多处理机环境
缺点：进程等待进入临界区时要耗费处理机时间，不满足“让权等待”，会导致“饥饿”现象
互斥锁
需忙等，进程时间片用完才下处理机，违反“让权等待”
常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区；不太适用于单处理机系统，忙等的过程中不可能解锁
等待期间不用切换上下文，多处理器系统中，若上锁的时机较短，则等待代价很低
原子操作
acquire()（获得锁）
release()（释放锁）
信号量
整型信号量
用一个整数型变量作为信号量，数值表示某种资源数
整型信号量与普通整型变量的区别：对信号量只能执行初始化、P、V三种操作（P、V操作是一种低级进程通信原语）
整型信号量存在的问题：不满足让权等待原则
记录型信号量
S.value表示某种资源数，S.L指向等待该资源的队列
P操作中，一定是先S.value--，之后可能需要执行block原语
V操作中，一定是先S.value++，之后可能需要执行wakeup原语
注意：要能够自己推断在什么条件下需要执行block或wakeup
可以用记录型信号量实现系统资源的“申请”和“释放”
可以用记录型信号量实现进程互斥、进程同步
利用信号量实现同步
分析问题，确定临界区
设置互斥信号量，初值为1
临界区之前对信号量执行P操作
临界区之后对信号量执行V操作
利用信号量实现进程互斥
分析问题，找出哪里需要实现“一前一后”的同步关系
设置同步信号量，初始值为0
在“前操作”之后执行V操作
在“后操作”之前执行P操作
利用信号量实现前驱关系
分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题
为每一对前驱关系设置同步信号量，初值为0
在每个“前操作”之后执行V操作
在每个“后操作”之前执行P操作
分析进程同步和互斥问题的方法步骤
1.关系分析
2.整理思路
3.设置信号量
管程
为什么要引入管程
解决信号量机制编程麻烦、易出错的问题
组成
管程的名称
局部于管程内部的共享数据结构说明
对该数据结构进行操作的一组过程（或函数）
对局部于管程内部的共享数据设置初始值的语句
基本特征
局部于管程的数据只能被局部于管程的过程所访问
一个进程只有通过调用管程内的过程才能进入管程访问共享数据
每次仅允许一个进程在管程内执行某个内部过程
补充
各进程必须互斥访问管程的特性是由编译器实现的
可在管程中设置条件变量及等待/唤醒操作以解决同步问题
经典同步问题
生产者-消费者问题
读者-写者问题
哲学家进餐问题
吸烟者问题
处理机调度
调度的概念
基本概念
按某种算法选择一个进程将处理机分配给它
三个层次
高级调度（作业调度）
按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程
中级调度（内存调度）
按照某种规则，从挂起队列中选择合适的进程将其数据调回内存
低级调度（进程调度）
按照某种规则，从就绪队列中选择一个进程为其分配处理机
三层调度的联系、对比
高级调度
外存->内存（面向作业）
发生频率：最低
中级调度
外存->内存（面向进程）
发生频率：中等
低级调度（最基本，不可或缺）
内存->CPU
发生频率：最高
补充知识
为减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存从而变为“挂起态”
七状态模型：在五状态模型的基础上加入了“就绪挂起”和“阻塞挂起”两种状态
调度的评价指标
CPU利用率
指CPU“忙碌的”时间占总时间的比例
利用率=忙碌的时间/总时间
系统吞吐量
表示单位时间内CPU完成作业的数量
系统吞吐量=总共完成了多少道作业/总共花了多少时间
周转时间
指从作业提交到作业完成所经历的时间
周转时间=作业完成时间-作业提交时间
平均周转时间=各作业周转时间之和/作业数
带权周转时间=作业周转时间/作业实际运行的时间
平均带权周转时间=各作业带权周转时间之和/作业数
等待时间
进程/作业等待被服务的时间之和
平均等待时间即各个进程/作业等待时间的平均值
响应时间
从用户提交请求到首次产生响应所用的时间
调度的实现
调度程序（调度器）
操作系统中用于调度和分派CPU的组件
组成
排队器
分派器
上下文切换器
调度的时机
什么时候需要进程调度？
主动放弃处理机
进程正常终止
运行过程中发生异常而终止
主动阻塞（如等待I/O）
被动放弃处理机
分给进程的时间片用完
有更紧急的事情需要处理（如I/O中断）
有更高优先级的进程进入就绪队列
什么时候不能进行进程调度？
在处理中断的过程中
进程在操作系统内核临界区中
其他需要完全屏蔽中断的原子操作过程中
调度的切换与过程
狭义的“调度”和“切换”的区别
调度是指决定资源分配给哪个进程的行为，是一种决策行为
切换是指实际分配的行为，是执行行为
一般来说，先有资源的调度，然后才有进程的切换
切换过程
对原来运行进程各种数据的保存
对新的进程各种数据的恢复
重要结论：进程调度、切换是有代价的，并不是调度越频繁，并发度就越高
调度的方式
非剥夺调度方式（非抢占式）
只能由当前运行的进程主动放弃CPU
优点：实现简单、系统开销小
缺点：无法及时处理紧急任务，适合于早期的批处理系统
剥夺调度方式（抢占式）
可由操作系统剥夺当前进程的CPU使用权
优点：提高系统吞吐量和响应效率
缺点：“抢占”不是一种任意性行为，必须遵循一定的原则
闲逛进程
在进程切换时，如果系统中没有就绪进程，就会调度闲逛进程运行
闲逛进程不需要CPU之外的资源，它不会被阻塞
特性
优先级最低
可以是0地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）
能耗低
两种线程的调度
用户级线程调度
内核级线程调度
典型的调度算法
先来先服务（FCFS）调度算法
算法思想：主要从“公平”的角度考虑
算法规则：按照作业/进程到达的先后顺序进行服务
可以用于作业调度和进程调度
非抢占式的算法
优点：公平、算法实现简单
缺点：效率低，带权周转时间很大。对长作业比较有利，但对短作业不利；有利于CPU繁忙型作业，而不利于I/O繁忙型作业。
不会导致饥饿
短作业优先（SJF）调度算法
算法思想：追求最少的平均等到时间，最少的平均周转时间，最少的平均带权周转时间
算法规则：最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）
可以用于作业调度和进程调度
有非抢占式和抢占式版本（最短剩余时间优先算法（SRTN））
优点：“最短的”平均等待时间、平均周转时间
缺点：不公平，对短作业有利，对长作业不利，可能产生饥饿现象。完全未考虑作业的紧迫程度。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。
会导致饥饿
高响应比优先（HRRN）调度算法
算法思想：要综合考虑作业/进程的等待时间和要求服务的时间
算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务 响应比=（等待时间+要求服务时间）/要求服务时间
可以用于作业调度和进程调度
非抢占式的算法
优缺点：综合考虑了等待时间和运行时间 等待时间相同时，要求服务时间短的优先（SJF的优点） 要求服务时间相同时，等待时间长的优先（FCFS的优点） 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大从而避免了长作业饥饿的问题
不会导致饥饿
时间片轮转（RR）调度算法
算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队
用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）
抢占式算法，由时钟装置发出时钟中断来通知CPU时间片已到
优点：公平；响应快；适用于分时操作系统
缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度
不会导致饥饿
时间片太大，退化为先来先服务调度算法 时间片太小，开销增大，真正用于运行用户进程的时间将减少
优先级调度算法
算法思想：根据任务的紧急程度来决定处理顺序
算法规则：调度时选择优先级最高的作业/进程
可以用于作业调度和进程调度
有抢占式和非抢占式两个版本
优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度
缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
会导致饥饿
优先级
静态优先级（创建进程时确定，整个运行期间保持不变）
动态优先级（根据进程情况的变化动态调整优先级）
优先级设置参考原则
系统进程>用户进程
交互型进程>非交互型进程（或前台进程>后台进程）
I/O型进程>计算型进程
多级队列调度算法
多级反馈队列调度算法
算法思想：对其他调度算法的折中权衡
算法规则： 1.设置多级就绪队列，各级队列优先级从高到低，时间片从小到大 2.新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾 3.只有第k级队列为空时，才会为第k+1级队头的进程分配时间片
用于进程调度
抢占式算法
优缺点：对各类型进程都很公平（FCFS的优点）；每个新到达的进程都可以很快就得到响应（RR的优点）；短进程只用较少的时间就可完成（SPF的优点）；不必实现估计进程的运行时间（避免用户作假）；可灵活地调整对各类进程的偏好程度
会导致饥饿
进程切换
上下文切换（实质上是指处理机从一个进程的运行转到另一个进程上运行，只发生在内核态）
模式切换（用户态和内核态之间的切换）