目录

• 前言
• 进程的定义、组成、组织方式、特征
• 进程的状态与转换
• 进程控制
• 进程通信
• 线程概念和多线程模型
• 处理机调度
• 进程调度
• 调度算法的评价指标
• 早期批处理系统的调度算法
• 交互式系统的调度算法

前言

本文是对王道操作系统课程的速览和总结，如有侵权，请联系我删除
本文结构是"知识点+展开"，每一小节的展开顺序和知识点的顺序对应

进程的定义、组成、组织方式、特征

进程的定义
进程实体的组成
	PCB
	程序段
	数据段
进程的组织形式
	链接方式
	索引方式
进程的特征
	动态性
	并发性
	独立性
	异步性
	结构性

进程的定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

进程实体==进程映像

PCB是Process Control Block的缩写，是进程存在的唯一标志
PCB的组成：
1.进程描述信息：进程标识符PID、用户标识符UID
2.进程控制和管理信息：进程当前状态、进程优先级
3.资源分配清单：程序段指针、数据段指针、键盘、鼠标
4.处理机相关信息：各种寄存器值

进程的组织方式：
1.链接方式：将PCB分为多个队列，操作系统持有指向各个队列的指针
2.索引方式：建立PCB的索引表，操作系统持有指向各个索引表的指针

进程的特征：
动态性：进程的最基本特征
独立性：进程是系统进行资源分配、调度的独立单位
异步性：各进程以不可预知的速度向前推进，可能导致运行结果的不确定性

进程的状态与转换

进程的五种状态
	运行态
	就绪态
	阻塞态
	创建态
	终止态
进程状态间的转换

运行态(Running)：占有CPU资源、拥有其他所需资源
就绪态(Ready)：没有CPU资源、拥有其他所需资源
阻塞态(Waiting/Blocked)：没有CPU资源、没有其他所需资源
创建态(New)：操作系统为新进程分配资源、创建PCB
终止态(Terminated)：操作系统回收进程的资源、撤销PCB

就绪态->运行态：进程被调度
运行态->就绪态：时间片到，或CPU被其他高优先级的进程抢占
运行态->阻塞态：等待系统资源分配，或等待某事件发生(主动行为)
阻塞态->就绪态：资源分配到位，等待的事件发生(被动行为)
创建态->就绪态：系统完成创建进程相关的工作
运行态->终止态：进程运行结束，或运行中遇到不可修复的错误

进程控制

进程控制的基本概念
进程控制相关原语
	进程创建
	进程终止
	进程阻塞
	进程唤醒
	进程切换

进程控制的概念：进程控制就是要实现进程状态的转换

进程控制用原语实现

阻塞和唤醒要成对出现

进程通信

共享存储
	基于数据结构的共享
	基于存储区的共享
管道通信
消息传递
	直接通信方式
	间接通信方式

进程通信的概念：进程通信就是指进程之间的信息交换

共享存储：操作系统在内存中设置一个共享空间，供进程互斥地访问
共享存储的两种方式：
1.基于数据结构的共享：共享空间中只能放特定的数据结构；这种共享方式速度慢，限制多，是一种低级通信方式
2.基于存储区的共享：共享空间中的数据形式，存放位置都由进程控制，而不是操作系统；这种共享方式速度快，是一种高级通信方式

管道通信：操作系统在内存中开辟一个固定大小的缓冲区(pipe)，供进程互斥地访问
1.管道通信只能实现半双工通信，实现双向同时通信要建立两个管道
2.写满时，写进程阻塞；读空时，读进程阻塞
3.没写满，不能读；没读空，不能写
4.数据一旦被读出，就从管道中抛弃->读进程最多只能有一个

消息传递：进程间的数据交换以格式化的消息(Message)为单位，通过操作系统系统的"发送消息/接收消息"原语实现
格式化的消息==消息头+消息体
消息头包括：发送进程ID、接受进程ID、消息类型、消息长度等格式化信息
消息头就像信封，消息体就像信封里的信
消息传递的两种方式：
1.直接通信方式：消息直接挂到接收进程的消息缓冲队列上
2.间接通信方式：消息要先发送到中间实体(信箱)中，因此间接通信方式也称"信箱通信方式"

线程概念和多线程模型

线程的概念
引入线程的原因
线程机制和传统进程机制的对比
	资源分配、处理机调度
	并发性
	实现并发的系统开销
线程的属性
线程的实现方式
	用户级线程
	内核级线程
	组合方式
多线程模型
	多对一模型
	一对一模型
	多对多模型

线程的概念：线程是一个基本的CPU执行单位，也是程序执行的最小单位，是为了解决传统进程只能串行地执行一系列程序而引入的机制

引入线程的原因：
1.增加系统的并发度：引入线程后进程内的各线程之间也可以并发，提升了系统的并发度
2.减少并发带来的系统开销

线程机制和传统进程机制的对比：
1.资源分配、处理机调度
1)传统进程机制中，进程是资源分配、处理机调度的基本单位
2)引入线程后，进程是资源分配的基本单位，线程是处理机调度的基本单位
2.并发性
1)传统进程机制中，只能进程间并发
2)引入线程后，各线程间也能并发，提高了系统的并发度
3.实现并发的系统开销
1)传统的进程间并发，需要切换进程的运行环境，系统开销大
2)引入线程后，如果是统一进程内的线程切换，则不需要切换进程环境，系统开销小
2)引入线程后，减小了并发所带来的系统开销

线程的属性：
1.线程是处理机调度的单位
2.多CPU计算机中，各线程可以占用不同的CPU
3.每个线程都有一个线程ID，线程控制块(TCB，Thread Control Block)
4.线程也有就绪、阻塞、运行三种基本状态
5.对于同一进程的不同线程
1)共享进程资源
2)线程间通信无需系统干预
3)线程切换不会引起进程切换，因此线程切换的系统开销很小
6.对于不同进程中的不同线程，线程切换回引起进程切换，因此线程切换的系统开销很大

线程的实现方式：
1.用户级线程(User-Level Thread)：应用程序通过线程库实现的线程
线程切换工作由应用程序负责，因此用户级线程的切换在用户态下完成
2.内核级线程(Kernel-Level Thread)：操作系统内核视角的线程
内核级线程的管理工作由操作系统内核完成，因此内核级线程的切换在核心态下完成
3.用户级线程和内核级线程的组合方式
1)将n个用户级线程映射到m个内核级线程上，显然n>=m，否则会造成系统资源的浪费
2)具体的映射方式由多线程模型决定
3)内核级线程才是处理机分配的单位，因此在多核计算机上运行的进程，最多只能有n个用户级线程并行执行

多线程模型：
1.多对一模型：多个用户级线程对应一个内核级线程
优点：线程切换在用户态下完成，不需要切换到核心态，线程管理的系统开销小，效率高
缺点：只能有一个用户级线程并行执行，并发度不高，且一旦某个用户级线程被阻塞，整个进程都会被阻塞
2.一对一模型：用户级线程和内核级线程一一对应
优点：多线程可在多核处理机上并行执行，且当某个线程被阻塞时，其它线程可以继续执行，并发性高
缺点：用户进程占用过多的内核级线程，且内核级线程会频繁切换，因此需要CPU频繁切换到核心态，线程管理的系统开销大
3.多对多模型：将n个用户级线程映射到m个内核级线程上，显然n>=m
克服了多对一模型并发度不高的缺点，克服了一对一模型用户进程占用太多内核级线程的缺点，集二者之所长

处理机调度

基本概念
三个层次
	高级调度(作业调度)
	中级调度(内存调度)
	低级调度(进程调度)
三层调度的联系、对比
挂起态和七状态模型

处理机调度的概念：按照某种算法选择一个进程将处理机资源分配给它

处理机调度的三个层次：
1.高级调度(作业调度)：按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程
高级调度会为作业创建PCB，使其获得竞争处理机资源的权利
2.中级调度(内存调度)：按照某种规则，从挂起队列中选择合适的进程将其数据调回内存
1)中级调度的目的：提高内存利用率和系统吞吐量
2)中级调度不会将PCB一起调到外存，PCB会常驻内存
3.低级调度(进程调度)：按照某种规则，从就绪队列中选择一个进程为其分配处理机资源
低级调度是操作系统中最基本的调度

三层调度的联系、对比：
1.高级调度：作业从外存到内存的调入，每个作业只能调入一次，因此高级调度发生频率低
高级调度使进程从无状态->创建态->就绪态
2.中级调度：进程从外存到内存的调度，发生频率中
中级调度使进程从挂起态->就绪态/阻塞态
3.低级调度：进程从内存到CPU的调度，发生频率高
低级调度使进程从就绪态->运行态

挂起态：为了减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存从而变成"挂起态"
七状态模型：在五状态模型的基础上加入了"就绪挂起"和"阻塞挂起"两种状态
挂起和阻塞的区别：
1.挂起态和阻塞态都暂时不能获得处理机资源
2.挂起态是将部分进程映像调到外存，而阻塞态的进程映像还在内存中

进程调度

进程调度的时机
进程切换
进程调度的方式

什么时候需要进程调度：
1.运行态进程主动放弃处理机资源
1)进程正常终止
2)进程异常终止
3)进程阻塞
2.运行态进程被动放弃处理机资源
1)时间片用完
2)有更紧急的事情需要处理(如I/O中断)
3)有更高优先级的进程进入就绪队列

什么时候不能进行进程调度：
1.在中断处理的过程中
2.进程在操作系统的内核程序临界区中
临界资源：各进程需要互斥地访问的资源
临界区：访问临界资源的代码
内核程序临界区一般是用来访问内核数据结构的，比如进程的就绪队列，因此在访问内核程序临界区期间不能进行进程调度与切换
3.原子操作过程中(原语)

进程切换的过程：
1.保存原来进程的数据
2.恢复新进程的数据
进程调度和进程切换有代价，并不是调度越频繁，系统并发度越高

进程调度的方式：
1.非剥夺调度方式(非抢占式)：只能由当前运行的进程主动放弃CPU
非抢占式进程调度系统开销小，但是无法及时处理紧急任务，适合于早期的批处理系统
2.剥夺调度方式(抢占式)：可由操作系统剥夺当前进程的CPU使用权
抢占式进程调度适合于分时操作系统、实时操作系统

调度算法的评价指标

CPU利用率
系统吞吐量
周转时间
等待时间
响应时间

周转时间=作业完成的时间-作业提交的时间
带权周转时间=作业周转时间/作业实际运行的时间

进程等待时间=等待被服务的时间之和
作业等待时间=作业在外存后备队列中等待的时间+建立进程后的等待时间
进程在等待I/O完成的期间不计入等待时间

早期批处理系统的调度算法

饥饿
先来先服务(FCFS)算法
短作业优先(SJF/SPF)算法
高响应比优先(HRRN)算法

饥饿：某进程/作业长期得不到服务
如果某进程/作业一直得不到服务，则称为"饿死"

以下三种调度算法，既可以用于作业调度，也可以用于进程调度

先来先服务算法(First Come First Serve)
非抢占式
优点：公平、算法实现简单，不会导致饥饿
缺点：排在长作业后面的短作业等待时间长，带权周转时间长，对长作业有利，对短作业不利

短作业优先算法(Shorest Job First)
非抢占式，但是也有抢占式的版本–最短剩余时间优先算法(SRTN，Shortest,Remaining Time Next)
优点："最短的"平均等待时间、平均周转时间
缺点：不公平，对短作业有利，对长作业不利，可能产生饥饿；作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先

高响应比优先算法(Highest Response Ratio Next)
非抢占式
响应比=(等待时间+要求服务的时间)/要求服务的时间
响应比和带权周转时间的区别：
1.带权周转时间的静态的，作业/进程的一次执行过程中，带权周转时间是唯一确定的
2.响应比是动态的，外存后备队列中的作业或内存就绪队列中的进程的响应比，会随着时间的推移改变
优点：
1.等待时间相同时，要求服务时间短的优先(SJF算法的优点)
2.要求服务时间相同时，等待时间短的优先(FCFS算法的优点)
3.对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题

交互式系统的调度算法

时间片轮转调度(RR)算法
优先级调度算法
多级反馈队列调度算法

时间片轮转调度算法(Round-Robin)
抢占式
用于分时操作系统的进程调度，分时操作系统更注重"响应时间"，因此不计算周转时间
时间片设置不合理的影响：
1·时间片太大，则RR算法会退化成FCFS算法，增大进程的响应时间
2.时间片太小，进程切换过于频繁，切换进程的开销过大
优点：公平、响应快，适用于分时操作系统，不会造成饥饿
缺点：高频率的进程切换有一定开销；不区分任务的紧急程度

优先级调度算法
抢占式、非抢占式都有
既可用于作业调度，也可用于进程调度
补充：
1.可以按照优先级组织多个就绪队列，也可以把优先级高的进程排在队头位置
2.优先级可以分为静态优先级和动态优先级
通常：
1.系统进程优先级高于用户进程
2.前台进程优先级高于后台进程
3.操作系统更偏好I/O型进程(I/O繁忙型进程)，与I/O型进程对应的是计算型进程(CPU繁忙型进程)
I/O设备和CPU可以并行工作，优先调度I/O型进程可以提高系统资源利用率和吞吐量
优点：用优先级区分紧急程度、重要程度，适用于实时操作系统，可以灵活调整对各种作业/进程的偏好程度
缺点：若高优先级进程不断进入就绪队列，则可能导致饥饿

多级反馈队列调度算法
抢占式
优点：
1.对各类型进程相对公平(FCFS算法的优点)
2.每个新进程都可以很快得到响应(RR算法的优点)
3.短进程只用较短的时间就可以完成(SPF算法的优点)
4.不必估计进程的运行时间，避免用户作假
5.可灵活调整对各类进程的偏好程度
缺点：可能导致饥饿