操作系统
c2 进程管理
2.1进程与线程
进程概念与特征
进程：便更好的描述和控制程序的并发执行，实现操作系统的并发性与共享性。
PCB：进程控制块，描述进程的基本情况预计运行状态，进而控制和管理进程。
程序段，相关数据段和PCB三部分构成了进程映像（实体）。
创建进程：创建进程中的PCB，撤销进程：撤销PCB
进程映像是静态的，进程是动态的
进程是进程实体的运行过程，是系统进行资源分配的一个独立单位。
特征：动态性，并发性，独立性，异步性，结构性
进程的状态与切换
运行态，就绪态，阻塞态，创建态，结束态
进程控制：把进程控制用的程序段称为原语
进程创建：分配唯一进程标识号–>申请空白PCB，申请成功则进程创建成功
进程终止：正常结束，异常结束，外界干扰；资源释放，子进程撤销，从PCB队列中删除
进程阻塞：等待某种操作，由系统自动执行阻塞（Block）原语，变为阻塞态；
? 只有处于运行态的进程才能变成阻塞态
进程唤醒：阻塞进程所期待的时间发生了，将阻塞态进程切换为就绪态，唤醒原语（Wakeup）；
进程切换：处理机从一个进程转到另一个进程运行；利用系统调用进入内核，再由内核中的相应处理程序完成。
调度：决策行为，如调度算法；切换：执行行为。先有资源的调度，然后才有进程的切换。
进程的组织：PCB，程序段，数据段
PCB：进程描述信息，进程控制和管理信息，资源分配清单，处理机相关信息
程序段：能被进程调度程序调到CPU执行的代码段；程序可被多个进程共享。
数据段：原始数据或者加工后的数据
进程的通信
PV操作是低级通信方式，高级通信方式，以较高的效率传输大量数据
共享存储：A与B中间有一箱子，AB通信通过箱子进行，A将信息放入箱子，B从箱子取走。
直接消息传递：A直接将消息送到B手中
间接消息传递：A将消息放到B的邮箱中，B从邮箱取出
管道通信
固定大小的缓冲区，读进程可能比写进程快；
半双工通信，不能两端同时进行，写满通知都进程读；
读数据是一次性操作，一旦被读取就抛弃。
实现父子进程互动通信，需要定义两个管道。
线程
线程：基本的CPU执行单元，程序执行流的最小单元，线程ID，PC，寄存器以及堆栈组成。
是进程的一个实体，被系统独立调度和分派的基本单位，线程只拥有一部分必不可少的资源，共享进程的全部资源。同一进程的多个线程可以并发执行。就绪。阻塞。运行三种状态。
比较：进程是拥有资源的最基本单位，线程是独立调度的基本单位。
同一进程，线程切换不会导致进程切换。
线程实现方式：用户级线程，内核级线程
用户级线程，线程管理相关操作都由应用程序完成，内核意识不到线程存在
内核级线程：线程管理由内核完成，应用程序没有线程管理代码，只有一个编程接口
多线程模型：同时支持用户线程和内核线程
多对一模型：多个用户级线程映射道一个内核线程
一对一模型：每个用户线程映射到一个内核线程
多对多模型：n------m，m<=n
2.2处理机调度
调度的概念
处理机调度是按照一定的算法，就绪队列中选择一个进程分配处理机给它，实现进程的并发执行
调度的层次
作业调度：高级调度，内存和辅存之间的调度，每个作业只调入一次，调出一次，多道批处理系统， 执行频率低。
中级调度：内存调度，提高内存利用率和系统吞吐量，挂起，当具备运行条件时，重新调入内存，并 修改为就绪态。
进程调度：低级调度，从就绪队列中选取一个进程，将处理机分配给它。操作系统的最基本调度，
? 频率很高。
三级调度的关系
作业调度为进程活动做准备，进程调度使进程正常活动起来，中级调度将暂时不能运行的进程挂起
作业调度次数少，进程调度频率高
进程调度最基本的，不可或缺
调度的时机切换与过程
不能进行调度和切换的情况：处理中断过程中，进程在内核程序临界区中，原子操作时
进程调度的方式
非剥夺与剥夺调度方式
调度的基本原则
CPU利用率，系统吞吐量，周转时间，等待时间，响应时间
周转时间=作业完成时间-作业提交时间
平均周转时间
带权周转时间=作业周转时间/作业实际运行时间
平均带权周转时间
典型的调度算法
先来先服务（FCFS）//对长作业有利，有利于CPU繁忙型作业，不利于IO型作业
**短作业优先（SJF）**调度算法 //对长作业不利，平均等待时间，周转时间最少
优先级调度算法：非剥夺/剥夺式进程调度算法，静态优先级，动态优先级
优先级：系统进程>用户进程，交互型进程>非交互型进程，IO型进程>计算型进程
高响应比优先级调度算法：
? 等待时间相同时，有利于短作业，要求服务时间相同时，等待时间越长，响应比越高
? 对于长作业，随等待时间增加而提高，克服了饥饿状态，兼顾了长作业
时间片轮转调度算法：适用于分时系统。时间片足够大=先来先服务，时间片很小，频繁切换，开销 增大。
多组反馈队列调度算法：融合了前几种的优点，动态调整进程优先级和时间片大小
? 设置多个就绪队列，赋予不同优先级，各队列时间片带下不同，逐级递增
? 新进程进入内存，先到第一队列的末尾(FCFS)，若一个时间片内没完成，
? 则放到第二队列…,当第一队列为空时，才运行第二队列…,可被剥夺！
优势：短作业优点，周转时间短，长作业不会长期得不到执行。
2.3进程同步
进程同步基本概念
多道程序环境下，进程是并发执行的，不同进程之间存在着相互制约关系。为了协调这种制约关系
临界资源：对临界资源的使用必须互斥进行，访问临界资源的那段代码称为临界区。
进入区：进入区检查是否可以进入临界区，设置访问标志
临界区：访问临界资源的那段代码，临界端
退出区：将正在访问临界区的标志清除
剩余区：代码中剩余部分
同步：直接制约关系，协调工作次序发送等待，传递信息等，源于进程的相互合作
互斥：间接制约关系，通过临界资源进行制约
? 空闲让进，忙则等待，有限等待，让权等待
临界区实现互斥的基本方法
软件实现：单标志法，设置一个访问标识
? 双标志法先检查，检查对方标志，再置自己标志
? 双标志法后检查，先置自己标志，在检查对方标志
? Peterson’s Algorithm，防止两个进程进入临界区无限等待
硬件实现方式：中断屏蔽方法， 硬件指令方法
信号量
信号量机制用来解决互斥与同步问题，只能被两个标准的原语wait(S),signal(S)访问，也记为PV操作
整型信号量，资源数目的整型量S
记录型信号量，不存在忙等的进程同步机制，资源数目＋进程链表
分析进行同步和互斥问题的方法步骤
关系分析：找出问题中的进程数，分析同步互斥关系
整理思路：找出关键点，写出PV操作的大致顺序
设置信号量：设置初值，完善整理
管程
管程，抽象为数据结构，包括管程名称，内部共享数据结构的说明，一组操作过程，设置初始值语句
管程把对共享资源的操作封装起来，每次只允许一个进程进入管程
条件变量，阻塞的原因，每个条件变量保存了一个等待队列
经典同步问题
生产者-消费者问题，读者-写者问题，哲学家进程问题，吸烟者问题
2.4死锁
死锁：多个进程因竞争资源而造成的一种僵局，相互等待，若无外力作用，这些进程都无法进行
死锁产生的原因
系统资源的竞争，进程推进顺序非法
死锁产生的必要条件：互斥，不剥夺，请求并保持，循环等待，产生死锁必须四个条件都满足
死锁的处理策略
死锁预防：破坏四个必要条件之一
避免死锁：动态分配过程，用某种方法阻止系统进入不安全状态
银行家算法：最大需求矩阵，分配矩阵，需求矩阵，
死锁检测与解除：不采取任何限制性措施
资源分配图，（检测是否发生死锁）进入资源的有向边分为请求边，资源到进程的有向边为分配边
死锁定理，找出一条有向边与它相连，且对应资源的申请数量小于系统中空闲资源数量，消去它，如此循环，一直简化，若不能完全简化，则发生死锁。