分类： 第3章 进程管理

时间片轮转调度
优先级调度
多级队列
最短作业优先
保证调度算法
策略与机制
两级调度法

调度算法应考虑的问题

公平——确保每个进程获得合理的CPU份额
效率——使CPU百分之百地忙碌
响应时间——使交互用户的响应时间尽可能短
周转时间——使批处理用户等待输出的时间尽可能短
吞吐量——使每小时处理的作业数量多

时间片轮转调度

每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间；
如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程；
如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。

该方法中唯一有趣的问题是时间片的长度；
结论可以归结为：时间片设得太短会导致过多的进程切换，降低了CPU效率；而设得太长又可能引起对短的交互请求的响应时间变长；
通常将时间片设为100ms，是一个比较合理的折衷。

优先级调度

基本思想：每个进程被赋予一个优先级，优先级最高的就绪进程被率先执行；
优先级可以为静态或动态；
将一组进程按优先级分成若干类，在各类之间采用优先级调度，而各类进程内部采用时间片轮转调度。

多级队列

为CPU密集的进程设置较长的时间片，比频繁地分给它们很短的时间片要高效（因为减少了交换的次数）；
进程的长时间片又会影响响应时间，因此设立优先级类，属于最高级类的进程运行一个时间片，属于次高优先级类的进程运行2个时间片，再次一级运行4个时间片，依此类推，当一个进程用完分配的时间片后，它被移到下一类。

最短作业优先

进程控制原语

原语：由若干条指令组成，用于完成一定功能的一个过程，与一般过程区别：是“原子操作”，不可分割、不允许中断、常驻内存

建立一个进程原语
撤消一个进程原语
挂起一个进程原语
解除挂起进程原语
改变优先数原语
阻塞一个进程原语
唤醒一个进程原语
调度进程运行原语

建立进程原语

所有进程只能由父进程建立，不是自生自灭的
建立进程原语是供进程调用，以建立子进程使用的
主要功能是创建一个指定标识符的进程
主要任务是形成该进程的进程控制块PCB

挂起进程原语

执行挂起命令的功能模块
调用挂起原语的进程只能挂起他自己或它的子孙，而不能挂起其他族系的进程，否则认为该命令非法

撤销进程原语

当一个进程完成其任务后，应将其撤销，以便及时释放出它所占用的资源
撤销原语采取的策略
 只撤销某一个具有指定标识符的进程
 撤销它的一个子进程及该子进程的所有子孙
命令的形式为kill或exit

改变进程优先级原语

进程的优先数数是表示进程的重要性及运行的优先性，供进程调度程序调度进程运行时使用的
防止一些进程因优先数较低，而长期得不到运行的情况

进程的优先数与以下因素有关
 与作业开始时的静态优先数有关
 与进程的类型有关
 与进程所使用的资源量有关
 与进程在系统中等待时间有关

进程间通信（补充）（Inter Process Communication,IPC）

竞争条件
临界区
忙等待的互斥
睡眠与唤醒
信号量

进程的描述

进程的描述应包含哪些信息和内容
 一个或多个程序
 数据
 充分的主存
 用于保存过程调用现场信息和过程间传递的参数等信息的一个堆栈
 有关情况的属性信息

进程控制块（PCB）

系统在建立进程的同时就建立该进程的PCB，在撤销一个进程的同时也就撤销其PCB。所以说进程的PCB对进程说是它存在的具体物理标志和体现

进程标识信息
 本进程的标识Id
 父进程的标识Id
 用户标识
处理器状态信息
 用户使用的寄存器
 控制和状态寄存器
 堆栈指针
进程控制信息
 调度和状态信息
 进程在有关队列中的链接指针
 进程间的通信信息
 主存使用信息
 进程使用的其他资源信息
 进程得到有关服务的优先级

PCB的作用

PCB是操作系统中最重要的数据结构
 PCB记录进程的属性信息，以便操作系统对其进行控制和管理
 PCB是进程存在的具体物理标志和体现
 PCB对是调度进程的主要的数据基

进程管理

各进程的PCB的组织方法
 把所有不同状态的进程的PCB组织在一个表格中
 分别把有着相同状态的进程的PCB组织在同一个表格中
 分别把具有相同状态的所有进程的PCB按优先数排成一个或多个队列

进程的基本状态

运行状态(Running)：正在处理器上运行的状态
就绪状态(Ready)：一个进程获得了除处理器外的一切所需资源，一旦得到处理器即可运行的状态
等待/阻塞状态(Blocked)：一个进程正在等待某一事件发生而暂时停止运行的状态

进程状态的变化

处于运行状态的进程在其运行过程中需等待某一事件发生后才能继续运行，该进程变为等待/阻塞状态；
处于运行状态的进程在其运行过程中，因分给它的处理器时间片已用完而不得不让出处理器，该进程变为就绪状态；
处于就绪状态的进程被进程调度程序选中后，就分配到处理器来运行，变为运行状态；
处于阻塞状态的进程，若其等待的事件已经发生，该进程变为就绪状态。

进程的挂起和解挂

为何引入这两种状态
 系统故障或功能受到破坏
 用户怀疑自己执行的作业的中间结果时，要检查和改正
 调整系统负荷（系统负载过重）
增加两个新的状态
 挂起就绪和挂起等待
挂起命令可由进程自己或其他进程发出，而解挂命令只能由其他进程发出

进程的引入

多道程序设计具有并行性的特点
 并行性：所有用户程序、各种中断处理程序、各类设备管理程序、高级调度程序、低级调度程序
 制约性：简介制约关系、直接制约关系
 动态性：基于上述两个特点，个程序在系统中所处的状态不断变化

程序的概念难以反映这种复杂的特性
 程序本身是一个静态的概念，不能反映系统中的动态性
 程序概念也反映不了系统中的并行特性

进程（process）的定义

程序在处理器上执行
进程是一个可调度的实体
进程是逻辑上的一段程序，它在每一瞬间都含有一个程序控制点，指出现在正在执行的指令
顺序进程是一个程序机器数据在处理器上顺序地执行时所发生的活动
进程是这样的计算部分，它可以与别的进程并行运行

进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动
进程和程序之间的区别
 进程是程序的执行，属于动态概念，而程序是一组指令的有序集合，是静态概念
 进程的存在是暂时的，而程序的存在是永久的
 进程的组成包括程序和数据，还由“进程控制块(PCB)”组成
 一个程序可能对应多个进程
 一个进程可以包含多个程序

程序的顺序执行

若一个计算机由若干操作组成，而这些操作必须按照某种先后次序来执行，以保证某些操作的结果可为其他一些操作所利用，则这类计算过程就是程序的顺序执行过程

顺序程序的特点

顺序性：处理机的操作严格按照程序多规定的顺序执行，每个操作必须在下一个操作开始执行之前结束
封闭性：程序一旦开始执行，其计算结果不受外界因素的影响
可再现性：程序执行的结果与它执行速度无关（即与事件无关），而只与初始条件有关，只要给定相同的输入条件，程序重复执行一定会得到相同的结果

程序的并发执行

大多数计算问题只要求操作在时间是偏序的，即有些操作必须在其他操作之前执行，这是有序的，但其中有的却可以同时进行

若干个程序段同时在系统中运行，这些程序段在时间上是重叠的，一个程序段是执行尚未结束，另一个程序段已经开始，即使这种重叠是很小的一部分，也称这几个程序段是并发执行的

并发程序的特点

失去程序的封闭性：一个程序可以改变另一个程序的变量
程序与计算不再一一对应：当多个计算任务共享某个程序时，它们都可以调用这个程序
程序并发执行的互相制约：当并发执行的个程序之间需要协同操作完成一个共同的任务时，它们之间具有直接的相互制约关系，且一般这样的程序之间由一定的逻辑联系（竞争资源的间接联系）

进程介绍

现代的所有计算机都能同时做几件事情
伪并行（CPU在多道程序之间快速地切换）
人们很难对多个并行活动进行跟踪，进程是用于描述并行活动的一种模型
从概念上说，每个进程拥有它自己的虚拟CPU，而真正CPU在各进程来回切换（多道程序）