导图社区 进程及处理器调度
进程及处理器调度的思维导图，包含进程的定义与特征、进程的状态及转换、进程的描述、进程的切换和管理、处理器调度等。
社区模板帮助中心，点此进入>>
英语词性
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
法理
刑法总则
【华政插班生】文学常识-先秦
【华政插班生】文学常识-秦汉
文学常识：魏晋南北朝
【华政插班生】文学常识-隋唐五代
民法分论
进程及处理器调度
进程的定义与特征
定义
进程(Process)是一个可并发执行的具有独立功能的程序关于某个数据集合的一次运行活动，是操作系统进行资源分配和保护的基本单位
从原理角度看，进程是对正在运行程序的活动规律的抽象。
从实现角度看，进程是一种数据结构。通过此数据结构，可以清晰地刻画动态系统的内在规律，有效地管理和调度进入存储器运行的程序。
进程的特征
结构性
每个进程至少包含三个组成要素：程序块、数据块和进程控制块
共享性
同一程序运行于不同数据集合上时，构成不同的进程。进程和程序不是一一对应的。
动态性
进程因创建而产生，因调度而执行，因事件而等待，因撤销而消亡。
独立性
进程是系统中资源分配和保护的基本单位，有自己的虚存空间、程序计数器和内部状态等。
异步性
进程因共享资源或协同工作产生相互制约的关系，造成执行速度的不可预测性，必须对进程的执行次序或相对执行速度加以调节。
并发性
在一个单处理器系统的环境下，各个进程轮流占用处理器 。
与进程的区别
动态与静态
程序是静态的概念，是一组指令的有序集合，不存在异步特征。
进程是程序的一次执行过程，是动态的概念，它有从创建到消亡的过程。
暂存和长存
程序本身可以作为一种软件资源长期保存在磁盘中
进程只能在内存中短暂驻留。
进程的状态及转换
三状态模型
五状态模型
排队状态
进程的挂起
概念
由于进程的不断创建，系统资源如不能满足进程运行的要求。这就必须把某些进程的全部或部分对换(Swap)到磁盘镜像区中，暂时不参与进程调度，这就是进程的挂起(Suspend)
原因
操作系统的需要
系统负荷的需要
父进程请求
终端用户的请求
七状态模型
特征
挂起进程不能立即被执行
挂起进程可能会等待事件，但所等待事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件
进程进入挂起状态是由于操作系统、父进程或进程本身阻止它的运行
结束进程挂起状态的命令只能通过操作系统或父进程发出。
进程的描述
进程映像
根据进程的定义，一个进程至少要包含程序、数据、栈以及进程控制块(PCB)等信息，它们就构成了进程的进程映像。
进程控制块（进程描述符）
概念：是操作系统用来记录和刻画进程状态及有关信息的数据结构。它是进程动态特征的一种汇集，也是操作系统掌握进程的唯一资料结构和管理进程的主要依据。
组成
进程标识
标识号
此进程的标识号(Process ID)，也称为进程ID
创建此进程的进程(父进程)标识号。以及子进程标识号
用户标识号(User ID)，也称为用户ID。
进程状态
进程状态信息(处理器状态)
用户可见寄存器
控制和标志寄存器
栈指针
进程控制
进程控制信息
调度和状态信息
数据结构（链接指针）
进程间通信
进程特权
存储管理
资源的所有权和使用情况
进程队列及其管理
进程队列
把处于同一状态的所有进程的PCB连接在一起的结构称为进程队列
进程队列的组织方式
线性方式
链接方式
索引方式
进程的切换和管理
进程上下文
操作系统把进程的物理实体和支持进程运行的环境合称为进程上下文
用户级上下文
由用户进程的程序块、用户数据块(含共享数据块)和用户堆栈组成的进程地址空间
系统级上下文
包括进程控制块、内存管理信息、进程环境块，及系统堆栈等组成的进程地址空间。
寄存器上下文
由程序状态字(PSW)寄存器和各类控制寄存器、地址寄存器、通用寄存器、用户栈指针等组成
切换
进程切换是让处于运行态的进程中断运行，让出处理器给其它就绪进程。切换的实质是进程上下文的切换，即保存老进程状态而装入新进程的状态，以便新进程运行。进程的切换必定发生在内核态。
进程因各种原因进入等待态
进程完成系统调用返回用户态但未获得处理器
内核完成中断处理，进程返回用户态但未获得处理器
进程执行的时间片用完或在规定的时间内结束
进程切换的时机
1．完成任务 2．等待资源 3．运行时间片到 4．进入睡眠状态 5．执行完系统调用 6．优先级进程抢占
处理器状态转换
从用户态到核心态或者从核心态到用户态的转换称为模式切换。
从用户态到核心态或者从核心态到用户态的转换称为模式切换
模型
进程的管理
操作系统内核(Kernel)是基于硬件的第一层软件扩充。它通过执行各种原语操作来实现各种控制和管理功能，具有创建进程、撤消进程、进程间通信以及资源管理等功能。同时常驻内存，以提高操作系统的运行效率。
原语
原语(Primitive)是由若干条机器指令构成的完成某种特定功能的程序段，运行在内核态。原语具有原子性(atomic) ，即原语在执行的过程中是连续的，不可中断
处理器调度
调度层次
高级调度(长程调度)
作业调度
中级调度(中程调度)
存储器管理的交换功能(Swap)
低级调度(短程调度)
进程调度
处理器调度和进程状态的转换
选择调度算法的原则
面向系统
资源利用率
公平性
吞吐率
面向用户
响应时间
周转时间
作业周转时间
作业后备队列中的等待时间
形成进程后在就绪队列中的等待时间
进程在CPU上的执行时间
等待事件发生的时间
带权周转时间
带权周转时间，也称为归一化周转时间是周转时间 Tr 和有效服务时间 Te的比值。它体现了一个进程的相对滞后的程度。
低级调度
逻辑功能模块
队列管理(Queuer)
当进程转换为就绪态时，其PCB就会更新以反映这种变化。并且Queuer要将PCB指针放入就绪队列中
上下文切换(Context Switcher)
当进程发生切换时，Context Switcher要把当前进程的上下文信息保存在PCB中，并且恢复选中进程的上下文信息
分派(Dispatcher)
当一个进程让出处理器后，Dispatcher首先激活，把其上下文装入处理器。接着要从就绪队列中选中某个进程，完成其自身到选中进程的上下文切换
进程调度的机制
基本类型
剥夺式调度(Preemptive Schedule)
抢占式调度
非剥夺式调度(Non-preemptive Schedule)
非抢占式调度
作业和进程调度算法
先来先服务调度算法FCFS
当进程调度采用FCFS算法时，系统按照进程到达的先后顺序进行调度
短作业优先调度算法SJF
SJF是非剥夺式调度算法，易于实现，效率不高，且必须提前掌握作业的运行时间，忽视了作业等待时间，SJF调度算法偏好短作业，可能会因为持续不断的短作业而导致长作业出现“饥饿” 的情况
最短剩余时间调度算法SRTF
是在SJF基础上的剥夺式调度算法，平均周转时间和带权周转时间相对SJF较低一些。但需要增加计算开销
最高响应比优先调度算法SRRN
R＝作业周转时间/运行时间 =（已等待时间＋运行时间）/运行时间 =1+等待时间/运行时间
在HRRN调度算法中，综合考虑等待时间和运行时间，短进程因为运行时间短(分母小)，因此容易得到较高的响应比而被调度。但对于长进程如果等待时间足够长(分子大)也可以得到较大的响应比而提高被调度的机会，不会产生饥饿的现象。
优先级调度算法HPF
静态优先级
根据作业或进程的静态特性，在开始执行前就确定优先级，一旦执行后不能改变。
简单但会产生饥饿现象，使得有些低优先级作业或进程无限期推迟执行
动态优先级。 （高响应比优先算法）
将作业或进程的静态特性和动态特性结合起来确定作业或进程的优先级，随着作业或进程的执行，其优先级不断发生变化
克服静态优先级的饥饿问题，但相应会增加计算开销。
轮转调度RR
轮转调度是一种剥夺式调度。系统耗费在进程切换上的开销比较大，这个开销与时间片的大小有关。
多级队列轮转调度算法MLQ
该算法适合进程调度。
多级队列轮转调度算法（multiple-level Queue,MLQ）是先来先服务调度算法、时间片轮转算法和优先级算法的综合。该调度算法的主要思想是将系统中的就绪进程，按其优先级高低不同，分为两级或多级队列。
多级反馈队列轮转调度算法MLFQ
小结
非剥夺式
FCFS（先来先服务）,SJF（短作业优先）,HRRF/HRN（最高响应比）,HPF（优先级）
剥夺式
SRTF（最短剩余时间）,RR（轮转法）,HPF（优先级）, MLQ(多级队列),MLFQ（多级反馈队列）
适用范围
FCFS,SJF,SRTF,HRRF,HPF
FCFS,SJF,SRTF,HPF,RR,MLQ,MLFQ
