补充知识
- PSW程序状态字寄存器
- PC程序计数器：存放下一条指令的地址
- IR指令寄存器：存放当前正在执行的指令
- 通用寄存器：存放其他一些必要信息
进程
进程：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
进程实体 = 程序段 + 相关数据段 + 进程控制块PCB
PCB是给OS用的，程序段和数据段都是给进程自己使用的
①创建进程 = 创建进程实体中的PCB
撤销进程 = 撤销进程的PCB
②进程映像（进程实体） 是静止的，进程是动态的
③PCB是进程存在的唯一标识。OS管理时所需要的信息都放在PCB中
进程的特征
- 动态性（最基本特征）：进程是程序的一次执行，具有一定的生命周期，是动态的产生、变化和消亡的
- 并发性：多个进程实体同存于内存中，能在一段时间内同时运行
- 独立性：进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位
- 异步性：由于进程的相互制约，使得进程按各自独立的、不可预知的速度向前推进（OS提供“进程同步机制”来解决异步问题）
- 结构性：每个进程都会配置一个PCB
进程的状态
- 运行态 —— 单处理机中，每个时刻只有一个进程处于运行态
- 就绪态
- 阻塞态 / 等待态 ：进程正在等待某一事件而暂停运行（等待某资源为可用，等待输入/输出完成）
- 创建态
—— 创建进程：申请一个空白PCB → 向PCB里填写用于控制和管理进程的信息 → 为该进程分配运行时所必需的资源 → 把该进程转入就绪态并插入就绪队列
- 终止态 ：处理资源释放和回收（回收PCB）
补充知识
一个进程可以执行exit系统调用，请求OS终止该进程 → “终止态”
在进程PCB中，会有一个变量state来表示进程的当前状态
同一程序运行在不同的数据集上，形成不同的进程
一个计算机系统中，进程的最大数目主要受到 内存大小 限制
在一个多道系统中，若就绪队列不空，就绪的进程数目越多，处理器的效率不变
①进程控制块PCB
- 进程描述信息：进程标识符PID、用户标识符UID
- 进程控制和管理信息：进程当前状态、进程优先级、代码运行入口地址、程序的外存地址、进入内存时间、处理机占用时间、信号量使用
- 资源分配清单：代码段指针、数据段指针、堆栈段指针、文件描述符、键盘、鼠标
- 处理及相关信息：通用寄存器值、地址寄存器值、控制寄存器值、标志寄存器值、状态字
进程组织方式
①链接方式：按照进程状态将PCB分为多个队列；操作系统持有指向各个队列的指针
②索引方式：根据进程状态的不同，建立几张索引表；操作系统持有指向各个索引表的指针
②程序段
程序的代码（指令序列）
③数据段
运行过程中产生的各种数据。如：程序中定义的变量
进程控制
进程控制：对系统中的所有进程实施有效的管理，具有创建新进程、撤销已有进程、实现进程状态转换等功能
原语：进程控制用的程序段（执行期间不允许中断）
进程的创建
①允许一个进程（父进程）创建另一个进程（子进程）
- 子进程继承父进程所拥有的资源；
- 撤销子进程时，需把从父进程获取的资源还给父进程；
- 撤销父进程时，同时撤销子进程
- 父进程与子进程共享一部分资源，但不能共享虚拟地址空间
- 父进程创建子进程：父进程与子进程同时执行（并发）
- 主程序调用子程序：主程序暂停在调用点，子程序开始执行，直到子程序返回，主程序才开始执行
②引起进程的创建（创建态→就绪态）：终端用户登陆系统、作业调度、系统提供服务、用户程序的应用请求
- 申请一个空白PCB（PCB有限）
- 为进程分配所需资源
- 初始化PCB
- 将新进程插入就绪队列
进程的终止
①引起进程的终止（…态→终止态→无）：正常结束、异常结束、外界干预
- 根据被终止进程的标识符，检索出该进程的PCB
- 若被终止进程处于运行态，立即终止该进程的执行（剥夺CPU），将处理机资源分配给其他进程
- 将其所有子孙进程终止
- 将该进程所拥有的全部资源，归还给父进程或OS
- 将该PCB删除
进程的阻塞（Block原语）和唤醒（Wakeup原语）
①引起进程的阻塞（运行态→阻塞态）：请求系统资源失败、等待某种操作的完成、新数据尚未到达、无新任务可做 等期待的某些事件未发生
- 找到被阻塞进程的标识号对应的PCB
- 若该进程为运行态，则保护其现场，将其状态转为阻塞态，停止运行
- 把该PCB插入相应事件的等待队列
②引起进程的唤醒（阻塞态→就绪态）：I/O操作已完成、新数据已到达 等期待的某些事件发生
- 在该事件的等待队列中找到相应进程的PCB
- 将其从等待队列中移出，并置其状态为就绪态
- 把该PCB插入就绪队列，等待调度程序调度
进程的切换
①允许进程的切换：当前进程时间片到、有更高优先级的进程达到、当前进程主动阻塞、当前进程终止
- 将运行环境信息存入PCB
- 把该PCB移入相应队列
- 选择另一个进程执行，并更新其PCB
- 根据PCB恢复新进程所需的运行环境
进程的通信
∵各个进程拥有的内存地址空间相互独立，故需要进行通信，即进程之间的信息交换
1.共享存储
共享存储：存在一块可直接访问的共享空间，通过对这片共享空间进行读/写操作（各个进程的访问是互斥的）来实现信息交换
其中，读/写操作需要使用 同步互斥工具（P操作、V操作）
①基于数据结构的共享（低级）
速度慢，限制多
②基于存储区的共享（高级）
注：OS只负责为通信进程提供可共享使用的存储空间和同步互斥工具
数据交换由用户自己安排读/写指令完成
2.消息传递
消息传递：进程间的数据交换以格式化的消息为单位
需要使用 发送消息Send 和 接收消息Receive 两个原语
消息头：发送进程ID、接收进程ID、消息长度等格式化的信息
①直接通信方式
直接把消息发送给接收进程（需指明接收进程的ID）
②间接通信方式（信箱通信方式）
把消息发送到某个中间实体（需指明要发送到的信箱）
3.管道通信（单向）
- 管道通信允许两个进程按
生产者-消费者方式进行通信 - 数据在管道中
先进先出（循环队列） - 半双工通信：在某一时间段内只能实现单向的传输
- 管道文件：一个固定大小的缓冲区
- 管道机制需提供的能力：互斥（由OS实现）、同步、确定对方的存在
管道只能由创建进程所访问，当父进程创建一个管道后，由于管道是一种特殊文件，子进程会继承父进程的打开文件，因此子进程也会继承父进程的管道，并使用这个管道与父进程进行通信。
- 只要管道不是空的，读进程就能从管道中读出数据
- 若数据被读空，则读进程阻塞，直到写进程往管道中写入新的数据，再将读进程唤醒
- 只要管道没满，写进程就能往管道中写入数据
- 若管道被写满，则写进程阻塞，直到读进程读出数据，再将写进程唤醒
从管道读数据是一次性操作，数据一旦被读取，就彻底消失，同时释放空间以便写更多数据。这种普通管道只允许单向通信，若要实现父子进程双向通信，则需要定义两个管道。
解决方案：①一个管道允许多个写进程，一个读进程
②允许多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据
4.共享文件
线程
- 引入进程的目的：使多道程序并发执行，提高资源利用率和系统吞吐量
- 引入线程的目的：减小程序在并发执行时所付出的时空开销，提高OS的并发性能
线程（轻量级进程）：是一个基本的CPU执行单元，是程序执行流的最小单元。
线程 = 线程ID + 程序计数器 + 寄存器集合 + 堆栈
线程控制块TCB：记录线程执行的寄存器和栈等现场状态。
线程控制块TCB = 线程标识符TID + 寄存器 + 线程运行状态 + 优先级 + 线程专有存储区 + 堆栈指针
寄存器：程序计数器PC（线程目前执行到哪）、状态寄存器、通用寄存器（线程运行的中间结果）
线程运行状态：用于描述线程正处于何种状态
优先级：线程调度、资源分配的参考
线程专有存储区：线程切换时用于保存现场
堆栈指针：用于过程调度时保存局部变量及返回地址等
①线程是进程中的一个实体，是被系统独立调度和分派的基本单位
②线程自己不拥有系统资源，只拥有一点儿在运行在必不可少的资源，但它可与同属于一个进程的其他线程共享进程所拥有的全部资源，可独立执行程序
③一个线程可以创建和撤销另一个线程，同一进程中的多个线程之间可以并发执行
④引入线程后，进程只作为除CPU外的系统资源的分配单元，而线程是作为处理及的分配单元
| 线程与进程的比较 | 线程（引入线程的操作系统） | 进程（传统操作系统） |
| 调度 | 线程是独立调度的基本单位 线程切换代价小。 在同一进程内进行线程切换不会引起进程切换 | 进程是拥有资源和独立调度的基本单位。 每次调度都会引起上下文切换，开销大 |
| 并发性 | 进程之间可以并发执行 一个进程中的多个线程也可并发执行 | 进程之间可以并发执行 |
| 拥有资源 | 线程不拥有系统资源 | 进程是系统中拥有资源的基本单位 |
| 独立性 | 某进程中的线程对其他进程不可见。 同一进程内的不同线程共享进程的地址空间和资源 | 每个进程都拥有独立的地址空间和资源 |
| 系统开销 | 线程切换只需保存和设置少量寄存器内容，开销很小； 同一进程内的多个线程的同步与通信不需要OS的干预 | 系统开销很大 |
| 支持多处理机系统 | 多线程进程：进程中的多个线程可以分配到多个处理机上执行 | 单线程进程：进程只能允许在一个处理机上 |
线程的实现方式
①用户级线程ULT
用于早期OS：只支持进程，不支持线程
- 在用户级线程中，内核意识不到线程的存在，应用程序可以通过使用线程库设计成多线程程序
- 设置了用户级线程的系统，仍以
进程为单位进行调度
优点：①线程切换不需要转换到内核空间，系统开销小，效率高
②用户级线程的实现与OS平台无关
缺点：①当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高
②多个线程不可在多核处理机上并行运行
②内核级线程KLT = 内核支持的线程
内核级线程是处理机分配的基本单位
- 线程切换需要CPU变态
- 内核级线程是在
内核的支持下运行的
优点：①多个线程可并行执行，并发能力强；
②如果进程中的一个线程被阻塞，可运行其他进程中的线程；
③采用多线程技术
缺点：同一进程中的线程切换，需要从用户态转到核心态进行，系统开销较大
③组合方式
线程库：为程序员提供创建和管理线程的API
- 在用户空间中提供一个没有内核支持的库
- 实现由操作系统直接支持的内核级的一个库
多线程模型
①多对一模型
情况：1.以不同的参数或数据多次执行同一个应用程序（多对一）
2.进程在执行过程中可以加载执行不同的程序（一对多）
优点：线程管理在用户空间进行，不需要切换，效率较高
缺点：并发性不高。若一个线程在访问内核时发生阻塞，则整个进程都会被阻塞
②一对一模型
情况：执行一条命令或运行一个应用程序
优点：当一个线程被阻塞后，允许调度另一个线程允许（因为内核级线程是处理及分配的单位），故并发能力较强
缺点：每创建一个用户线程，相应的需创建一个内核线程，开销较大
③多对多模型
情况：并发执行不同的应用程序
特点：克服了多对一模型并发度不高的特点，克服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点
拥有上述两种模型的优点
补充知识
- 多线程：在一个程序中可以定义多个线程并同时运行它们，每个线程可以执行不同的任务
- 多任务：针对操作系统，代表OS可以同时执行的程序个数
- 多线程：针对一个程序，代表一个程序可以同时执行的线程个数，而每个线程可以完成不同的任务
- 一个系统中可能所有进程都处于等待态（死锁）
进程的调度
补充知识
- 进程处于临界区（访问临界资源的那段代码）时不能进行处理机调度
- 内核程序临界区：访问某种内核数据结构（例：进程的就绪队列）
①高级调度（作业调度）
作用：按照一定的原则从外存上处于后备队列的作业中挑选一个（或多个），分配内存、输入/输出设备等必要的资源
多道批处理系统大多配有作业调度，而其它系统中通常不需要配置作业调度
②中级调度（内存调度）
目的：提高内存利用率和系统吞吐量
将那些暂时不能运行的进程调至外存等待，此时进程的状态—— 挂起态
作用：把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪态，挂在就绪队列上等待
③低级调度（进程调度）
作用：按照某种算法从就绪队列中选择一个进程为其分配处理机
进程调度是最基本的一种调度，在各个操作系统中都必须配置
狭义进程调度：从就绪队列中选出一个要运行的进程
广义进程调度：包含了选择一个进程和进程切换两个步骤
三级调度的联系
作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列；
进程调度从就绪队列中选出一个进程，并把其状态改为运行态，把CPU分配给它；
中级调度是为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来。
- 作业调度为进程活动做准备，进程调度使进程正常活动起来
- 中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间
- 调度频率：作业<中级<进程
🤨调度算法评价标准
①CPU利用率
CPU利用率 = CPU有效工作时间 / ( CPU有效工作时间 + CPU空闲等待时间 ）
②系统吞吐量
单位时间内CPU完成作业的数量
③周转时间
从作业提交到作业完成所经历的时间
周转时间 = 作业完成时间 - 作业提交时间
平均周转时间 = （作业1的周转时间 + … + 作业n的周转时间）/ n
带权周转时间 = 作业周转时间 / 作业实际运行时间
平均带权周转时间 = （作业1的带权周转时间 + … + 作业n的带权周转时间）/n
④等待时间
进程：进程处于等处理机的时间之和
作业：需考虑建立进程后的等待时间，和作业在外存后备队列中等待的时间
⑤响应时间 ——衡量调度算法的重要准则之一
从用户提交请求到系统首次产生响应所用的时间
调度程序（调度器）
用于调度和分派CPU的组件（排队器、分派器、上下文切换器）
①触发“调度程序”的情况
- 非抢占式调度策略，只有运行进程阻塞或退出才触发
- 抢占式调度策略，每个时钟中断或k个时钟中断会触发
②触发“调度程序”
- 创建新进程
- 进程退出
- 运行进程阻塞
- I/O中断发生
🎃不能进行进程的调度与切换的情况
- 在处理中断的过程中
- 进程在操作系统内核临界区中
- 其他需要完全屏蔽中断的原子操作过程中
🎃应该进行进程调度与切换的情况
当前运行的进程主动放弃处理机：
- 进程正常终止
- 运行过程中发生异常而终止
- 进程主动请求阻塞（等待I/O）
当前运行的进程被动放弃处理机：
- 分给进程的时间片用完
- 有更紧急的事需要处理（I/O中断）
- 有更优先级的进程进入就绪队列
进程切换往往在调度完成后立刻发生，会保存原进程当前断点的现场信息，回复被调度进程的现场信息
当进程处于临界区时，说明进程正在占用处理机，只要不破坏临界资源的使用规则，就不会影响处理机的调度（即，在进程处于临界区时可以进行处理机调度）
😊进程调度方式
- 非抢占调度方式（非剥夺方式）
主动放弃处理机
优点：实现简单、系统开销小，适用于早期批处理系统
缺点：不能用于分时系统和大多数实时系统
- 抢占调度方式（剥夺方式）
适合分时系统和实时操作系统。
优点：遵循优先权、短进程优先和时间片原则
闲逛进程（能耗低、优先级最低、不需要CPU之外的资源、不会被阻塞）
在进程切换时，若系统中没有就绪进程，就会调度闲逛进程运行
可以是0地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）
调度算法
| 调度算法名称 | 先来先服务FCFS | 短作业优先SJF | 优先级调度 | 高响应比优先调度 | 时间片轮转RR | 多级队列调度 | 多级反馈队列调度 |
| 算法过程 | 选择最先进入后备队列的作业 | 选择运行时间最短的作业 | 选择优先级最高的作业 | 选择响应比最高的作业 | 选择就绪队列中的第一个进程 | ||
| 适用 | 作业、进程调度 | 作业、进程调度 | 作业、进程调度；实时操作系统 | 作业、进程调度 | 进程调度；分时系统 | 进程调度 | |
| 是否导致“饥饿” | 不会导致饥饿 | 会饥饿 | 会饥饿 | 不会饥饿 | 会饥饿 | ||
| 调度方式 | 非抢占式 | 非抢占式 | 非抢占式、抢占式优先级调度； | 非抢占式 | 抢占式 | 抢占式 | |
| 公式 | 响应比Rp= (等待时间+要求服务时间) / 要求服务时间 | 最高优先级 →系统进程→ →交互式进程→ →批处理进程→ 最低优先级 |  （如表格下图） | ||||
| 优点 | 算法简单公平 | 平均等待时间、平均周转时间最少 | 有利于短作业 | 公平，响应快 | - 公平，不必实现估计进程的运行时间 - 可灵活调整对各类进程的偏好程度 - 终端型作业用户：短作业优先 - 短批处理作业用户：周转时间较短 - 长批处理作业用户：不会长期得不到处理 | ||
| 缺点 | - 效率低 - 长作业有利，短作业不利 - 利于CPU繁忙型作业，不利于I/O繁忙型作业 | - 长作业不利，短作业有利 - 可能导致长作业饥饿 - 不能保证紧迫性作业会被及时处理 - 不一定能真正做到短作业优先调度 | 计算响应比的开销大 | - 不区分任务的紧急程度 - 处理机在进程间过于频繁的切换 - 开销增大 | 无 | ||
| 补充 | 短进程优先算法SPF 抢占式版本：最短剩余时间优先算法SRTN | - 静态优先级：创建进程时确定 - 动态优先级：根据进程情况的变化动态调整 - 进程优先级设置： 1. 系统进程>用户进程 2. 交互性进程>非交互型进程(前台>后台) 3. I/O型进程>计算型进程 | 时间片的长短： 系统的响应时间、就绪队列中的进程数目、系统的处理能力 | 同一队列中的进程可以设置不同的优先级； 不同的队列本身也可以设置不同的优先级 |
进程切换
任何进程都是在操作系统内核的支持下运行的
1.上下文切换
切换CPU到另一个进程需要保存当前进程状态并恢复另一个进程的状态
2.上下文切换的消耗
3.上下文切换与模式切换
模式切换：用户态和内核态之间的切换
调度：决定资源分配给哪个进程的行为（决策）
切换：实际分配的行为（执行）
