进程
概念&定义：
* 资源分配的基本单位
* 程序在处理器上的一次执行过程
* 可以和别的进程并行执行的计算
* 进程时程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位
* 进程是程序关于某个数据集合在 处理器上顺序执行所发生的活动
* 进程是一个 数据结构以及能在其上进行操作的一个程序
特征：动态性，并发性，独立性，异步性
进程的组成：
* 进程控制块PCB:结构：进程标识符PID、进程当前状态、进程队列指针、程序和数据地址、进程优先级、CPU现场保护区、通信信息、家族联系、占有资源清单
* 程序段，数据段
* 进程标识符PID
进程的状态
5种基本状态
就绪状态，执行状态，阻塞状态，创建状态，结束状态
状态转换
就绪→执行、执行→阻塞、执行→就绪、阻塞→就绪
进程控制
1.创建
* 进程前趋图.创建原语
* 创建事件：用户登录，作业调度，请求执行
2.撤销
* 只撤销一个具有指定标识符的进程
* 撤销指定进程及其所有子进程
3.阻塞(主动调用原语阻塞自己)
4.唤醒(由发现者进程用唤醒原语唤醒进程，被动进程)
5.切换
* 进程切换一定会产生中断
* 处理器模式切换(从用户态进入核心态再回到用户态)，不一定产生进程切换
进程与程序的关系
* 进程是动态的，程序是静止的；进程是程序的执行，程序是有序代码的合集
* 进程是暂时的，程序是永久的
* 进程与程序的组成不同，进程由程序段、数据段、进程控制块构成
* 通过多次执行，一个程序可以产生多个不同进程；通过调用，一个进程可以执行多个程序；进程可以创建其他进程，程序不能形成新程序
* 进程具有并行性，程序没有
进程与作业的关系
* 进程是已提交完毕的作业的执行过程
* 作业完成过程：作业提交、作业收容、作业执行、作业完成
* 作业是用户向计算机提交任务的任务实体
* 一个作业可由多个进程组成，且至少由一个进程组成；但一个进程不能构成多个作业
* 作业一般用于批处理系统中
进程通信
高级进程通信方式
* 共享存储器系统
* 消息传递系统——直接通信方式、间接通信方式(中间实体-信箱)
* 管道通信系统(管道是一个共享文件)
线程
减少程序并发执行的空间开销，提高并发性
概念与定义
* 线程是进程中一个相对独立的，可调度的执行单元
* 线程是进程内部的一个执行单元，壁进程更小
* 线程是进程内的一个可调度实体
* 线程是程序中相对独立的一个控制流序列
* 线程本身不能单独运行，只能在进程中执行
* 线程本身不具备资源，但进程间可以互相共享拥有的资源
实现
内核级线程
用户级线程(应用程序实现)
线程与进程
* 在同一进程中，线程的切换不会引起进程切换；但在不同进程中进行线程切换，会引起进程切换
* 线程是独立调度的基本单位，进程是拥有资源的基本单位
* 即线程不拥有系统资源，但它可以共享访问所属进程的资源
* 引入线程的操作系统中，进程间可以并发执行，同一进程中的多个线程也可以并发执行
* 进程切换时系统开销大，线程切换时开销小
* 多线程间的同步与通信非常容易实现，甚至不需要操作系统干预
多线程模型
多对一模型、一对一模型、多对多模型
处理器调度
1.三级调度
高级调度(作业调度)
* 按照一定原则从外存上处于后备状态的作业中选择一个或多个，给他们分配内存和I/O设备等资源，建立相应的进程
* 作业调度的运行频率较低，通常为几分钟一次
中级调度(交换调度)
* 按照一定原则，将处于外存对换区的具备运行条件的进程调入内存，并修改其状态为就绪，挂到就绪队列上等待；或将处于内存中且暂时不能运行的进程，交换到外存对换区，并修改进程状态为挂起
低级调度(进程调度)
* 按照一定原则，从就绪队列中选择一个进程，将处理器分配给它
* 进程调度的运行频率很高，一般为几十毫秒一次
2.调度准则
CPU利用率、系统吞吐量、响应时间
周转时间(等待时间+运行时间)、平均周转时间
带权周转时间(周转时间/运行时间)、平均带权周转时间
3.进程调度
功能
* 记录系统中所有进程的执行情况和状态特征(通过PCB)
* 选择获得处理器的进程
* 处理器分配
引起进程调度的原因
* 当前运行进程运行结束(正常or异常)
* 当前运行进程因某种原因进入阻塞状态
* 执行完系统程序后返回用户进程
* 在抢占调度方式的系统中，一个优先级更高的进程请求使用处理器
* 在分时系统中，分配给该进程的时间片用完
不能进程调度的情况
* 处理中断的进程
* 在操作系统内核程序临界区中（进入临界区后，需要独占式访问共享数据）
* 其他需要完全屏蔽中断的原子操作系统
进程调度的方法
* 抢占方式/可剥夺方式(会死锁)
* 非抢占方式/不可剥夺方式
常见的调度算法
FCFS先来先服务调度算法（作业调度/进程调度）
SJF短作业优先调度算法（作业调度/进程调度）
优先级调度算法（作业调度/进程调度）
* 静态优先级
按进程类型确定(系统进程优先)
按作业的资源要求确定(申请少的优先)
按用户类型和要求确定(高收费用户优先)
* 动态优先级
按进程占有CPU的时间长短决定(占有越长,优先级越低)
按就绪进程等待CPU的时间长短决定(等待越久,优先级越高)
* ps.优先级相同的情况，通常按先来先服务/短作业优先顺序执行
时间片调度算法（进程调度）
*决定时间片大小的因素
系统的响应时间(正比)
就绪队列的进程数目(反比)
系统的处理能力(越高,时间片越小)
高响应比优先调度算法（作业调度）
* 响应比=(等待时间+预估运行时间)/预估运行时间
多级队列调度算法（进程调度）
* 根据进程的类型划分为若干个独立队列，每个队列采用不同的调度算法
多级反馈队列调度算法(进程调度)
* 时间片轮转调度算法+优先级调度算法
* 兼顾多方面系统目标，不需要事先预估进程执行时间
* ①先设置多个就绪队列，第一个队列优先级最高，依次降低
* ②优先级越高的队列，时间片越小
* ③当一个新进程进入时，先放到第一个队列末尾，若其不能在对应时间片完成则移到下一个队列末尾，反复执行
* ④当处理器正在执行第i个队列时，若有优先级较高的新进程进入，则中断当前进程并将其放到第i队列末尾，转而执行新进程
* ⑤最后一个队列采用时间片轮转调度算法
同步与互斥
概念
* 互斥：多个同类进程互斥的共享某种系统资源
互斥准则： 空闲让进，忙则等待，有限等待，让权等待
* 同步：不同类进程间的互相合作(ex.B进程需要等待A进程的运算结果才能够继续执行)
临界资源与临界区
* 临界资源：同一时刻仅允许一个进程使用的资源(ex.打印机)
* 临界区：访问临界资源过程中的一段代码
* 临界资源访问过程
进入区：检查是否可以进入临界区，若可以则设置"正在访问临界区"标志，以阻止其他进程同时进入
临界区：进程中用于访问临界资源的代码，又叫做临界段；每个进程的临界区代码可以不同
退出区：清楚之前设置的"正在访问临界区"标志
剩余区：其他代码
*互斥实现方法
* 软件方法
多种算法代码
缺点：存在忙等
* 硬件方法
中断屏蔽、硬件指令
优点：适用范围广、简单、支持多个临界区
缺点：×让权等待、饥饿现象
*信号量
* 信号量与同步原语概念
* 信号量分类
整型信号量
记录型信号量/资源信号量
* 信号量应用：实现进程同步、互斥
***经典同步问题
- 生产者-消费者问题
一组生产者向一组消费者提供产品，共享一个有界缓冲区，生产者投入产品，消费者取走产品
* *必须先对资源信号量进行P操作，再对互斥信号量进行P操作，不然会“死锁”
- 读者-写者问题
读者优先算法
公平情况算法(按到达顺序进行操作)--其实还是读者优先
写者优先算法
- 哲学家进餐问题
死锁问题解决：奇数号哲学家先拿左边筷子，偶数号哲学家先拿右边筷子
- 理发师问题
两种思路(把凳子、理发椅看作同一种资源)
管程
* 定义了一个数据结构，以及由并发进程执行的一组操作，该操作可以同步进程、改变管程中的数据
* 管程把分散在各个进程中互斥访问公共变量的临界区集中起来，提供对它们的保护
* 特征
局部于管程的数据，只能被局部于管程的过程所访问
一个进程只有通过调用管程内的进程，才能进入管程访问共享数据
每次仅允许一个进程在管程内执行某内部过程
死锁
概念：多个进程因竞争系统资源或互相通信，处于永久阻塞状态
特点
* 参与死锁的进程至少有两个，且至少两个进程占有资源
* 每个参与死锁的进程均在等待资源
* 死锁进程是系统当前进程集合的一个子集
补充知识
资源分类：可剥夺资源、不可剥夺资源
只有对不可剥夺资源的竞争才有可能造成死锁
死锁产生的原因
* ！竞争资源
* 根本原因：资源不足
* 重要原因：进程推进顺序不当
死锁产生的必要条件
* 互斥条件
* 不可剥夺条件
* 请求与保持条件(申请新资源的同时继续占有原有资源)
* 环路等待条件
处理死锁的基本方法
* 鸵鸟算法(就是啥都不做 随便它)
* 预防死锁
在调度方式上破坏死锁产生的必要条件
破坏互斥条件：不大可能
破坏不可剥夺条件：若进程申请新资源不成功，则它必须释放已经获得的资源
破坏请求与保持条件：采用预先静态分配(进入运行前一次性分配所有资源)
破坏环路等待条件：有序资源分配法
* 避免死锁
概念
1. 在动态分配过程中，预先估计进行这种分配，是否会导致系统进入不安全状态，若会则不进行该分配
2. 安全状态：至少存在一种安全序列
3. 不安全状态：系统有可能发生死锁的状态，不是指系统已发生死锁
银行家算法
* 检测及解除死锁
资源分配图
死锁定理(资源分配图无法完全简化，则为死锁状态)
死锁检测算法
死锁解除： 剥夺资源、撤销进程、进程回退
* 死锁、饥饿与饿死
饥饿：等待时间对进程的推进和响应造成明显影响
饿死：即使此时完成进程，也没有实际意义
活锁：忙时等待下的饥饿状态
区别：
1. 死锁进程都处于等待状态，而忙时等待处于运行或就绪状态时也可能会被饿死
2. 死锁进程等待的是永远不会被释放的资源，而饿死进程等待的是会被释放但是不会分配给自己的资源
3. 死锁一定发生了循环等待；资源分配图可以检测死锁，但无法检测饿死
4. 死锁涉及多个进程，饥饿或饿死可能只涉及一个
