进程管理（处理机管理）
zKing 2018-11-19 专业知识
# 进程
# 定义
程序关于某个数据集合的一次执行过程
# 特征（与程序比较）
- 结构特征
- 进程控制块（PCB）+ 程序 + 数据 = 进程实体
- 不同的进程，其PCB也不同
- 动态性 --最基本的特征
- 进程：进程实体的一次执行过程，有生命周期
- 程序：程序是一组有序指令的集合，是静态的概念
- 示例
- 程序相当于菜谱里的步骤，进程则是按菜谱炒菜的过程
# 三种基本状态（必备）
# 就绪状态（Ready）
进程已获得除 CPU 外·的所有必需的资源，一旦得到 CPU 的控制权，立即可以运行
# 运行状态（Runing）
进程已获得运行所必需的资源，它正在处理机（CPU）上执行
# 阻塞状态（Blocked）
正在执行的进程由于发生某事件而暂时无法执行时，便放弃处理机而处于暂停状态，称该进程处于阻塞状态或等待状态
# 转换
- 就绪->[ 进程调度 ]->执行->[ I/O 请求 ]->阻塞 ->[ I/O 完成 ]->就绪
- 执行 ->[ 时间片完 ]->就绪 //时间片一般为100ms
# 就绪态有进程，执行态一定有进程
# 五种状态（了解）
- 引入了挂起状态（静止状态）到非挂起状态（活动状态）的转换，或相反
- 将就绪态和阻塞态分为静止的和活动的
- 活动就绪和活动阻塞在内存工作
- 静止就绪和静止阻塞在外存工作
# 进程互斥与同步
# 两种形式的制约关系
- 间接相互制约关系 -- 源于资源共享
- 直接相互制约关系 -- 源于进程合作
# 临界资源
把一段时间内只允许一个进程访问的资源称为临界资源或独占资源，比如:打印机
# 临界区
每个进程种访问临界资源的那段代码称为临界区
# 信号量机制
# 信号量是 OS 提供的管理公有资源的有效手段。信号量是一个整数，记为 S
- 当 S >=0 时，代表可供并发进程使用的资源数量
- 当 S <0 时，表示处于阻塞状态进程的个数
# Wait 操作（P 操作）
- 申请资源，减量操作，S.value:=S.value-1
- 当 S.value<0时，表示资源分配完，进行自我阻塞
# Signal 操作（V 操作）
- 释放资源，增量操作，S.value:=S.value+1
- 当 S.value>=0时，唤醒 S.L链表中的等待进程
# 信号量的应用
# 利用信号量实现进程互斥（模式）
- 为使多个进程互斥的访问某临界资源，须为该资源设置一个互斥信号量 mutex，并设其初始值为 1 ，然后将各进程访问资源的临界区 CS 置于wait（mutex）和 signal（mutex）之间
- wait（mutex）和 signal（mutex）必须成对出现，即需要等待申请临界资源和释放临界资源这两个过程
# 利用信号量实现前驱关系（模式）【上午必考题】
- 有多少条有向边就设置多少信号量，通常都赋初值为 0
- 进程前有多少有向边就写多少个 wait
- 进程后有多少有向边就写多少个 signal
# 利用记录型信号量实现同步（模式）
- 需设置两个信号量
- 两个进程因合作完成一项任务而共用一个变量
# 进程调度（短程调度）
# 定义
用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序把处理机分配给该进程。是最基本的一种调度，三种类型OS中都必须由进程调度
# 采用两种调度方式
# 非抢占方式
实现简单、系统开销小；适用于大多数的批处理OS，但在分时 OS 和实时 OS 中，不宜采用这种调度方式
# 抢占方式
允许调度程序根据某种原则去暂停某个正在执行的进程，将处理机重新分配给另一进程
# 抢占的原则
- 时间片原则
- 各进程按时间片运行，一个时间片用完时，停止该进程执行重新进行调度
- 短作业（短进程）优先原则
- 优先权原则 // VIP，2333
# 调度算法
# 先来先服务（FCFS）
比较有利于长作业（长进程），而不利于短作业（短进程）
# 短作业（短进程）优先调度算法（SJF/SPF）
- 优点
- 有效降低作业的平均等待时间，提高系统吞吐量
- 缺点
- 对长作业不理，该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会被及时处理。
- 由于作业（进程）的长短知识根据估计执行时间定的，主观因素较大，不一定能真正做到短作业优先。
- 注：作业是在内存中执行，而进程是交由处理机（CPU）执行
# 高优先权优先调度算法（FPF）
常用于批处理系统中，还可以用于实时系统中
# 优先权的类型
- 静态优先权
- 在创建进程时确定的，在进程的整个运行期间保持不变。利用某一范围的整数来表示（0~7），又称为优先数
- 动态优先权
- 在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变
- 高响应比优先调度算法
- 优先权=（等待时间 + 要求服务时间）/ 要求服务时间
- 由于 （等待时间 + 要求服务时间）= 系统的响应时间，故 Rp=响应时间 / 要求服务时间
- Rp值越小，优先权越高
# 时间片轮转调度算法
最古老，最简单，最公平且使用最广的算法，常用于分时系统
# 死锁
# 定义
是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种状态时，若无外力作用，他们都将无法再向前推进。
# 产生原因
# 竞争资源
- 资源数目不足以满足诸进程的需要，就会引起诸进程对资源的竞争而产生死锁
- 可分为两类
- 可剥夺性资源：资源分配给进程后可以被高优先级的进程剥夺。如：CPU，主存
- 不可剥夺性资源：分配给进程后只能在进程用完后才释放的资源。如：磁带机，打印机等
# 进程间推进顺序非法
进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁
# 产生死锁的必要条件（必背）
# 互斥条件
进程访问的是临界资源
# 请求和保持条件
一进程在请求新的资源的同时，保持对已分配资源的占有
# 不剥夺条件
指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时自己释放
# 环路等待条件
指在发生死锁时，必然存在一个进程 --资源的环形链
# 求不会发生死锁的最少资源数 N，已知并发进程数为n，需要同类资源为 k
N=n*（k-1）+1
# 已知信号量S的当前值为-2，则资源R的可用数和等待R的进程数分别为 0 和 2
- 由于 S<0, 则资源处于阻塞状态，可用数为 0
- 等待 R 的的进程树为 S 的绝对值
# 处理死锁的基本方法
# 预防
通过设置某些限制条件，去破坏除“互斥条件”的四个必要条件的一个或几个来预防
# 避免
- 用某种方法去防止系统进入不安全状态，使死锁不导致最终发生
- 银行家算法避免死锁
# 检测
# 解除
- 解除死锁和检测死锁使配套的
- 常用的实施方法是撤销或挂起一些进程，以便回收一些资源后分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行