导图社区 02进程
- 33
- 0
- 0
- 举报
02进程
操作系统，进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位，进程是动态的，进程实体是静态的。
编辑于2024-09-28 22:55:58- 进程
- 调度算法
- 相似推荐
- 大纲
02进程
01进程
概念
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位，进程是动态的，进程实体是静态的
组成
进程实体（进程映象）
操作系统使用
PCB（进程管理的数据结构）
用来描述进程的各种信息，是进程存在的唯一标识
进程描述信息
进程标识符PID
UID用户标识符
进程控制信息
进程当前状态
进程优先级
资源分配清单
程序段指针
数据段指针
处理机相关信息
各种寄存器的值
进程自己使用
程序段
程序代码
数据段
程序运行时的变量，常量
特征
动态性
动态产生，变化，消亡
并发性
并发执行
独立性
进程是资源分配，接收调度的基本单位
能独立运行，独立获得资源，独立接收调度的基本单位
异步性
各进程按照各自独立，不可预知的速度向前推进，可能导致运行结果不确定性
结构性
每个进程都会配置PCB，由程序段，数据段，PCB组成
02进程的状态与转换，组织方式
基本状态
创建态
进程正在被创建，操作系统为 其分配资源，初始化PCB
就绪态
已经具备运行条件，只欠CPU调度
运行态
占有CPU，并在CPU上运行，单核处理机只有一个进程
阻塞态
因等待某一事件而暂时不能运行
终止态
进程正在从系统中撤销，操作系统会回收进程拥有的资源，撤销PCB
exit系统调用
PCB中含有state标志位记录进程状态
转换
运行态->阻塞态
主动行为
阻塞态->运行态
被动行为
只能从运行态到阻塞态，不能从就绪态到阻塞态
创建态->就绪态
系统完成创建进程相关的工作
运行态->终止态
进程运行结束，或运行过程中遇到不可修复的错误
组织
链接方式
按进程状态将PCB分为多个队列
操作系统持有指向各个队列的指针
索引方式
根据进程状态不同，建立几张索引表
操作系统持有指向各个索引表的指针
03进程控制
概念
对系统中所有进程实施有效的管理，实现进程状态之间的转换
实现
原语
特权指令
关中断指令
CPU不会例行检查中断信号
开中断指令
才会恢复检查
过程
更新PCB的信息
将PCB插入到合适的队列
分配回收资源
分类
进程的创建
创建原语
申请空白PCB
为新进程分配所需资源
初始化PCB
将PCB插入到就绪队列
引起进程创建的事件
用户登录
作业调度
提供服务
应用要求
进程的终止
撤销原语
从PCB集合中找到终止进程的PCB
若正在运行，立即剥夺CPU将CPU分配给其他进程
终止其所有的子进程
将该进程所有资源归还给父进程或操作系统
删除PCB
引起进程终止的事件
正常结束
异常结束
外界干预
进程的阻塞和唤醒
进程的阻塞
阻塞原语
找到要阻塞的进程对应的PCB
保护进程运行现场，将PCB状态信息设置为“阻塞态"，暂时停止进程运行
将PCB插入相应事件的等待队列
引起阻塞的事件
需要等待系统分配某种资源
需要等待相互合作的其他进程完成工作
进程的唤醒
唤醒原语
在事件等待队列中找到PCB
将PCB从等待队列移除，设置进程为就绪态
将PCB插入就绪队列，等待被调度
引起唤醒的事件
等待的事情发生
进程的切换
切换原语
将运行环境信息存入PCB
PCB移入相应队列
选择另一个进程执行，并更新其PCB
根据PCB恢复新进程所需的运行环境
引起切换的事件
当前进程时间片到
有更高优先级的进程到达
当前进程主动阻塞
当前进程终止
04进程的通信
概念
指进程之间的信息交换
为了保证安全，一个进程不能直接访问另外一个进程的地址空间
分类
共享存储
共享空间
各个进程的访问是互斥的
P,V操作
基于存储区的共享
高级的通信方式
速度快
基于数据结构的共享
低级的通信方式
消息传递
以格式化的消息为单位，操作系统提供发送消息/接收消息两个原语来完成数据交换
直接通信
指明接收的ID
间接通信
通过信箱作为中间实体进行消息传递
管道通信
半双工通信，同一时间内只能一方通信
队列形式
读写先进先出
其实就是在内存中开辟一个大小固定的缓冲区
各进程只能互斥的访问
如果没写满，不能读，没读空，不能写
管道写满，写进程阻塞，管道读空，读进程阻塞
一旦读出，数据就会消失
一个管道有多个写进程，只能一个读进程
05线程
概念
轻量级的进程
线程是程序执行流的最小单位
是一个基本的CPU执行单元
线程是资源调度的基本单位
作用
并发性
线程间也能并发，并发度增大
系统开销减小
属性
线程ID
线程控制块TCB
线程几乎不拥有系统资源
切换
同一进程中的线程切换，不会引起进程切换
不同进程中的线程切换，会引起进程切换
线程的实现方式
用户级线程
调用线程库完成
用户态下完成
内核级线程
管理工作由操作系统完成
线程之间并发能力强
内核级线程才是处理机分配的单位
组合线程
多线程模型
多对一
一对一
多对多
总结
用户级线程是代码逻辑的载体
内核级线程是运行机会的载体
线程的状态与转换
三状态
就绪态
运行态
阻塞态
组织
线程控制块TCB
线程表
控制
06调度
处理机调度的概念，层次
基本概念
某种规则来决定处理这些任务的顺序
作业，一个具体的任务
三个调度层次
高级调度（作业调度）
调入建立PCB
调出撤销PCB
无->创建->就绪
中级调度（内存调度）
提高内存利用率和系统吞吐量
七状态模型
就绪挂起态
在外存中
阻塞挂起态
在外存中
挂起->就绪
低级调度（进程调度）
最基本调度
调度频率高
就绪->运行
进程调度的时机，方式，切换与过程
进程的调度时机
分类
进程主动放弃处理机
进程被动放弃处理机
不能进行调度与切换情况
处理中断过程中
进程在操作系统内核程序临界区
原子操作过程中
切换与过程
过程
对原来运行进程各种数据的保存
对新的进程各种数据的恢复
狭义的进程调度
从就绪队列选中一个运行的进程
广义的进程调度
包含一个进程和进程切换两个步骤
进程切换和调度有代价，消耗资源
调度方式
非剥夺调度方式（非抢占式）
剥夺式调度方式（抢占式）
调度器和闲逛程序
调度器
唤醒调度程序
调度程序
处理就绪态和运行态
闲逛程序
没有其他就绪进程时，运行闲逛进程
优先级最低
能耗低
07调度算法
调度算法的评价指标
CPU利用率
忙碌时间/总时间
系统吞吐量
单位时间完成了多少道作业
周转时间
作业从提交到完成耗费的时间
平均周转时间
各作业周转时间之和/作业数
带权周转时间
作业周转时间/作业实际运行的时间
平均带权周转时间
各作业带权周转时间之和/作业数
等待时间
平均等待时间
进程/作业等待时间的平均值
响应时间
从提交到首次产生响应所用的时间
调度算法一（交互性差，适用于早期批处理系统）
先来先服务FCFS
按照到达先后顺序进行服务
非抢占式
优点：公平，缺点：对长作业有利，对短作业不利
不会导致饥饿
导致了对短作业不友好的问题
短作业优先SJF
最短的优先得到服务
非抢占式
抢占式SRTN
最短剩余时间优先算法
每当有进程加入就绪队列改变时就需要调度
多个指标优于非抢占式
优点：指标更优，缺点：对短作业有利，对长作业不利，易导致饥饿现象
可能产生饥饿
导致了对长作业不友好的问题
高响应比优先HRRN
响应比
（等待时间+要求服务时间）/要求服务时间>=1
需要计算响应比，响应比最高上处理机
非抢占式
综合前连个算法优缺点
不会导致饥饿
调度算法二(适用于交互式系统)
时间轮转片算法RR
按照就绪队列顺序，轮流让其执行一个时间片
抢占式
由时间中断处理
如果时间片太大，本算法就会退化为先来先服务调度算法，会增大进程响应时间
如果时间片太小，会导致切换过于频繁，会花费大量的时间
不会导致饥饿
时间片要设置合理
适用于分时操作系统
优先级调度算法
调度优先级最高的进程
抢占式
优先数越高，优先级越高
就绪队列发生改变时也需要检查是否会发生抢占
非抢占式
选择当前已到达的优先级最高的，主动放弃时发生调度
优先级
分类
静态优先级
创建进程时确定，之后一直不变。
动态优先级
创建进程时有一个初始值，之后会根据情况动态地调整优先级
通常
系统进程优先级高于用户进程
前台进程优先级高于后台进程
操作系统更偏好IO型进程
适用于实时操作系统，按繁忙程度区分
会产生饥饿
多级反馈队列调度算法
设置多级队列，队列优先级从高到低，时间片从小到大，时间片+优先级
抢占式
相对公平
会导致饥饿
08进程同步，进程互斥
同步
进程具有异步性
互斥
两种资源共享方式
互斥共享
同时共享
一个时间段内只允许一个进程使用的资源称为临界资源
互斥访问临界资源
进入区
设置上锁操作
临界区
访问临界区的那段代码
退出区
设置解锁操作
剩余区
做其他处理
访问临界区四个原则
空闲让进
临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
忙则等待
当已有进程进入临界区时，其他试图进入临界区的进程必须等待
有限等待
对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿)
让权等待
当进程不能进入临界区时，应立即释放处理机，防止进程忙等待
实现
进程互斥的软件实现方法
单标志法
每个进程进入临界区的权限只能被另一个进程赋予
违背空闲让进原则
双标志先检查法
先检查后上锁
数组中各个元素用来标记进程想进入临界区的意愿
违背忙则等待原则
双标志后检查法
先上锁后检查
违背空闲让进，有限等待
易产生饥饿现象
Peterson算法
孔融让梨思想
主动争取
主动谦让
未遵循让权等待的原则，会发生忙等
进程互斥的硬件实现方法
中断屏蔽方法
过程
关中断
访问临界区
开中断
不适用于多处理机，只适用于操作系统内核进程
需要在内核态下使用
TestAndSet指令TSL
执行过程不允许被中断，只能一气呵成
适用于多处理机环境
不满足让权等待
Swap指令XCHG
执行过程不允许打断，只能一气呵成
不满足让权等待
互斥锁
需要忙等，违反让权等待
适用于多处理机系统
09信号量机制
概念
使用操作系统提供原语来对信号量进行操作
信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量）
用来表示系统中某种资源的数量
实现
使用原语来完成，执行只能一气呵成，不可被中断
一对原语
wait(S)P操作(通过)
signal(S)V操作(释放)
检查和上锁一气呵成
分类·
整型信号量
用整型变量来表示系统某种资源的数量
对信号量只能初始化，P操作，V操作
不满足让权等待
记录型信号量
用记录型数据结构表示(结构体)，整型变量+等待队列
wait(S)P操作
signal(S)V操作
block原语
阻塞
没有资源时
wakeup原语
唤醒
有资源时
解决忙等问题
信号量实现进程互斥，同步，前驱关系
实现进程互斥
过程
划定临界区
设置互斥信号量mutex,初值为1
在临界区之前执行P（mutex），申请资源
在临界区之后执行V（mutex)，释放资源
对不同的临界资源设置不同的信号量
PV操作是成对出现的
总结
临界区之前对信号量执行P操作
临界区之后对信号量执行V操作
实现进程同步
进程具有异步性造成
目标
要让各并发进程按要求有序地推进
保证一前一后执行两个操作
保证一前一后执行两个操作
设置同步信号量S，初始值为0
在前操作之后执行V操作
在后操作之前执行P操作
实现前驱关系
保证执行语句一前一后
要为每一对前驱关系设置一个同步信号量，初始值为0
本质上就是多级同步问题
保证一前一后执行两个操作
设置同步信号量S，初始值为0
在每个前操作之后执行V操作
在每个后操作之前执行P操作
10管程
概念
产生原因
信号量机制实现编写程序困难，易出错
一种高级的同步机制
用来实现进程的同步与互斥
组成
共享数据结构说明
对数据结构操作的一组过程
对局部于管程的数据结构设置初始化的语句
管程有一个名字
特征
管程内的数据只能被局部于管程的过程所访问
各外部进程/线程只有通过管程提供的特定入口才能访问共享数据
每次只能开放其中一个入口
每次仅允许一个进程在管程内执行某个内部过程
更方便的实现进程互斥和同步
管程解决生产者消费者问题
这种互斥特性是由编译器实现的
在管程中设置条件变量及等待/唤醒操作以解决同步和互斥问题问题
在Java中，使用synxhronized关键字来描述的函数
11互斥问题
生产者与消费者问题
多生产者多消费者问题
吸烟者问题
读者消费者问题
哲学家进餐问题
12死锁
什么是死锁
互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象
概念
操作系统问题
死锁
互相等待对方资源
至少有两个或两个以上
饥饿
长期得不到想要的资源
可能只有一个进程发生饥饿
死循环
某进程执行过程中一直跳不出某个循环的现象
是代码逻辑问题
可以上处理机运行
产生死锁的必要条件
互斥条件
不剥夺条件
只能主动释放
请求保和条件
已经保持一个资源，但又提出新的请求，请求资源被其他进程占有，请求被阻塞，但对自己有的资源保持不放
循环等待条件
存在一种进程资源的循环等待链
发生死锁时一定有循环等待，但是发生循环等待时未必死锁
发生死锁情况
对系统资源的竞争
进程推进非法
信号量的使用不当
对不可剥夺的资源分配不合理
死锁的处理策略
预防死锁
破坏死锁产生的四个必要条件的一个或几个
破坏互斥条件
对互斥资源的争抢才会导致死锁
SPOOLing技术，改成共享资源
破坏不剥夺条件
缺点
实现起来比较复杂
破坏请求和保持条件
采用静态分配方法
缺点
资源利用率低，会导致进程饥饿
破坏循环等待条件
采用顺序资源分配法
每个进程必须按编号递增的顺序请求资源
缺点
不方便增加新设备
使用资源顺序和编号不一致，导致系统资源浪费
用户编程麻烦
避免死锁
用某种方法防止系统进入不安全状态
银行家算法
安全序列
不会发生死锁的进程执行顺序序列
不同情况
只要能找出安全序列，系统就是安全状态
一定不会发生死锁
找不到安全序列，系统就进入不安全状态
不一定会发生死锁
发生死锁，系统进入不安全状态
数据结构
资源分配表
进程
最大需求
已分配
最多还需要
避免进入不安全状态
银行家算法
在进程提出资源申请时，先预判此次分配是否会导致进入不安全状态
检查申请是否超过声明的最大需求数
检查此时系统剩余的可用资源是否还能满足这次请求
试探分配，更改数据结构
用安全性算法检查此次分配是否会进入不安全状态
死锁的检测与解除
死锁检测
数据结构:资源分配图
资源分配图
两种结点
进程结点
资源结点
两种边
进程结点-->资源结点（请求边）
资源结点-->进程结点（分配边）
死锁检测算法
依次消除与不阻塞进程相连的边，直到无边可消
如果最终不能消除所有边，那么此时发生了死锁
如果最终能消除所有边，那么此时没有发生死锁
能找到一个安全序列
死锁定理
若资源分配图是不可完全简化的，说明发生了死锁
死锁解除
资源剥夺法
挂起后抢占资源
撤销进程法
强制撤销死锁进程
进程回退法
让进程回退，按优先级，执行时间，还需多久完成