Chapter 4 线程
在操作系统中引入进程的目的是：使用多道程序能并发执行，以改善资源利用率及提高系统吞吐量
在操作系统中引入线程的目的是：减少程序并发执行的时空开销，使操作系统有更好的并发性
线程是CPU使用的一个基本单元，包括线程标识（thread ID），程序计数器（PC），寄存器集（register set），栈（stack）
线程自己基本上不拥有资源，只拥有一点在运行时必不可少的资源（如程序计数器、寄存器集和栈）。但它可以与同属一个进程的其他线程共享进程拥有的全部资源
线程与属于同一进程的线程共享：代码段，数据段，其他操作系统资源 线程的状态，同步与通信与进程类似
进程的挂起及终止将影响到其中所有进程
线程的优点：响应能力强（即使进程的一块被阻塞了，其他部分也能运行），资源共享，经济性，多处理器体系结构的利用，创建撤销切换时间短，共享内存和资源线程间通信方便
多线程模型
操作系统中有多种方式实现对进程的支持：内核线程（kernel Threads），用户线程（User Threads）的组合实现
内核线程：也称内核级线程，是指依赖于内核，由操作系统内核完成创建和撤销工作的线程。
一个内核线程的阻塞不会影响其他线程的运行。
处理机分配的对象是线程，所以有多个线程的进程将获得更多的处理机时间 用户线程：也称用户级线程，是指不依赖于操作系统核心，由应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制的线程
用户线程的维护由应用进程完成，可以用于不支持线程的操作系统 当一个线程阻塞时，整个进程都必须等待。
处理机时间是分配给进程的，进程内有多个线程时，每个线程的执行时间相对少一点
用户线程与内核线程的关系
多对一模型：将多个用户线程映射到一个内核线程。线程管理由线程库在用户空间进行。用于不支持内核线程的系统中（只有一个内核线程，相当于没有） 一对一模型：将每个用户线程映射到一个内核线程。这种模型的绝大多数实现限制了系统支持的线程数量
多对多模型：多个用户线程到同样数量或更少的内核线程上
多线程问题：
线程取消可以再一下两种情况下发生：异步取消（一个线程立即终止目标进程），延迟取消（目标线程不断检查它是否应该终止）
线程与进程的比较：从调度的基本单位，拥有资源的基本单位，并发性，和系统开销四个方面说。
Chapter5 CPU调度
处理机的三级调度：作业调度，进程调度，交换调度
作业调度：又称长程调度，宏观调度和高级调度，从外存上处于后备状态的作业中选择一个或多个作业，给他们分配内存、I/O设备等必要资源，并建立相应的进程，使该作业具有获得竞争处理机的权利 作业调度的运行频率低，通常几分钟一次
进程调度：又称短程调度，微观调度和低级调度，从就绪队列中选取一个进程，将处理机分配给它。
进程调度的运行频率很高，一般十几毫秒就要运行一次
交换调度：又称中程调度，中级调度，将内存总暂时不用的信息移到外存，以腾出空间给内存中的其他进程使用，或将需要的信息从外存读入内存。 交换调度的目的是，提高内存利用率和系统吞吐量 交换调度的运行频率介于上面两者之间
作业：是用户在一次解题或一个事务处理过程中要求计算机系统所做的工作的集合，包括用户程序、所需的数据及命令等
作业从提交到完成要经历四种状态：提交状态，后备状态（将作业插入后备作业队列中等待调度运行），运行状态（作业在内存中执行），完成状态
作业控制块（JCB，job control block）：系统通过JCB感知作业的存在，JCB是作业存在的唯一标志
一个作业可以分成若干顺序处理的加工步骤，每个步骤称为一个 作业步
多道程序的设计目标在于任何时候都有某些进程运行，使CPU利用率最大化。
CPU调度可能发生如下4种情况 从运行状态转到等待状态 从运行状态转到就绪状态 从等待状态转到就绪状态 进程终止
1,4两种情况的调度称为非抢占调度，2，3两种情况的调度称为抢占式调度 进程调度的两种方式：抢占方式，非抢占方式
抢占方式：又称波多方式。抢占原则有，优先权，时间片
分派程序：用来将对CPU的控制交给由短程调度程序选择的进程
分派延迟：分派程序终止一个进程的运行并启动另一个进程运行所花的时间，也成为调度时间
调度准则： CPU利用率
吞吐量（单位时间内运行完的程序数）
周转时间（进程从提交到运行结束的全部时间
等待时间（进程在就绪队列中等待调度的时间总和）
响应时间（从提交请求到系统首次产生响应所用的时间） 带全周转时间（作业周转时间与作业实际运行时间的比）
调度算法:（画图用到gantt图）
FCFS 先来先服务调度，适用于作业调度，进程调度 算法简单易于实现，不适用与短作业和I/O繁忙的作业
SJB 最短作业优先（抢占/非抢占）
适合短作业，对长作业不利，运行时间为估计 抢占SJB调度有时称为最短剩余时间优先调度，若到达新进程的CPU区间短于当前运行进程的剩余时间，则它将抢占CPU。 可能有饥饿
优先级调度（抢占/非抢占）
优先级的类型：静态优先级，动态优先级（确定原则：占用CPU时间，等待时间） 存在的问题：饥饿，低优先级的进程可能永远得不到运行 解决方法：老化，视进程等待时间的延长提高其优先级数
时间片轮转调度（RR）
每个进程得到小单位的CPU时间，称为时间片，通常为10-100毫 秒。时间片用完后，该进程将被抢占并插入就绪队列末尾。
时间片大小：太大：退化为FCFS 太小：调度频繁系统开销大。现代操作系统的时间片一般为10-100ms，上下文切换时间一般少于10us。 确定时间片大小应考虑的因素：
系统对响应时间的要求：响应时间=时间片*进程数
就绪队列中的进程数目：时间片应与就绪进程数成反比
系统的处理能力：考虑响应时间在可承受范围内，系统速度快则时间片可以增长 时间片轮转算法的特点及改进：
虚拟时间片轮转法（针对偏重I/O的进程）： 新进程基于FCFS进入就绪队列，进程用完时间片后也进入就绪队列，进程因I/O阻塞进入I/O队列，I/O完成时进程进入附加队列，附加队列的优先级高于就绪队列，当进程从附加队列被调度时，其运行时间不超过上次发生中断时剩余的时间。
高响应比优先调度算法
响应比＝1＋作业等待时间/估计运行时间
多级队列调度
将就绪队列分为多个独立队列，每个队列有自己的调度算法，根据进程属性，一个进程被永久分配到一个队列
例如分为前台（交互式）RR算法，和后台（批处理）FCFS。前台的优先级高
多级反馈队列调度
进程能在不同的队列间移动。如果进程使用过多的CPU时间，那么它会被移动到更低优先级队列。此外，在较低优先级队列中等待时间过长的进程会被移到更高优先级队列
每个队列有不同优先级，第一队列最高，其余递减，每个队列的时间片大小也各不相同，优先级高的队列时间片短。 当一个新进程进入系统时，首先将它放入第1个队列的末尾，按先来先服务的原则排队等待调度。当轮到该进程执行时，如能在此时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2队列的末尾，再同样地按先来先服务原则等待调度执行。如此下去，最后一个队列中使用时间片轮转调度算法。仅当第1个队列为空时，调度程序才调度第2队列中的进程运行；仅当第1个至第（i－1）个队列均为空时，才会调度第i个队列中的进程运行。当处理机正在为第i个队列中的某进程服务时，若又有新进程进入优先级较高的队列中，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在执行进程放回第i个队列末尾，重新将处理机分配给新进程。 多级反馈队列调度算法能较好满足各类用户的需求
公平分享调度算法：基于进程组来分配CPU时间，其实现思想是对系统中的每个用户赋予某种权值，根据用户权值大小，按比例分配处理机时间。
进程切换：在操作系统中凡是要进行中断处理和进程调度时，都将涉及到进程上下文的保存的恢复。
中断时：系统保存和恢复的是同一个进程的上下文 进程调度时恢复的是调度程序所选中进程的上下文
既考虑作业等待时间，又考虑作业执行时间的调度算法是 响应比高优先调度
Chapter 6 进程同步
进程同步：系统中各进程之间逻辑上的相互制约关系叫做进程同步
在多道程序系统中，进程之间存在着的不同制约关系可以划分为两类：同步和互斥
同步指进程间具有的一定逻辑关系；互斥是指进程间在使用共享资源方面的约束关系。
临界区问题：每个进程有一个访问共享数据的代码段，称为临界区（critical section）。需保证一个进程在其临界区执行时，不允许其他进程在其临界区执行。 临界资源：一段时间内仅允许一个进程使用的资源称为临界资源。如打印机，共享变量
同类临界区：所有与同一临界资源相关联的临界区
临界区问题的解决应满足：互斥，前进（如果没有进程在其临界区内执行，且有进程需要进入临界区，那么只有不在剩余区执行的进程可以参加选择，以确定下一个进入临界区的进程，且选择不能无限期延长），有限等待（在一个进程提出进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区的次数必须是有限的）
访问临界资源应遵循的原则：空闲让进，忙则等待，有限等待，让权等待（当进程不能进入自己的临界区时，应释放处理机）
Peterson算法
enum boolean {false，true}；
boolean flag［2］ ＝{false，false}； int turn； P0：{
do {
flag[0]＝true； turn＝1； while （flag[1] && turn = = 1）；//实现互斥，前进 进程P0的临界区代码CS0 ； flag[0]＝false ； 进程P0的其他代码；} while (true) }
P1：{
do {
flag[1]＝true； turn＝0； while （flag[0] && turn = = 0）； 进程P1的临界区代码CS1 ； flag[1]＝false ； 进程P1的其他代码；} while (true) }
硬件同步：用硬件方法实现互斥的主要思想是保证检查操作与修改操作不被打断 禁止中断方法：当进程执行临界区代码时，禁止中断(很多缺点)