操作系统-期末考试
进程管理
为什么要引入进程
多道程序（ multi-programming ）系统中，各个程序之间是并发执行的，共享系统资源。CPU需要在各个运行的程序之间来回地切换。
什么是进程？
并发执行的程序在执行过程中分配和管理资源的基本单位。个进程就是一个正在运行的程序。
一个进程包括：
- 程序的代码
- 程序的数据、
- CPU寄存器的值，如PC，用来指示下一条将运行的指令
- 堆、栈
- 进程占用的一组系统资源（如地址空间、打开的文件）
进程 = 程序 + 数据 + PCB
线程
线程是进程中的一个执行单元，是操作系统能够进行CPU调度的最小单位。
进程 = 线程 + 资源平台
- 进程是资源分配单位，线程是CPU调度单位
- 进程拥有一个完整的资源平台，而线程只独享必不可少的资源（寄存器和栈）；
- 线程同样具有就绪、阻塞和执行三种基本状态，同样具有状态之间的转换关系；
并发进程之间的两种关系
- 相互独立：进程之间没有任何关联关系，仅有CPU竞争关系；
- 相互关联：进程之间存在着某种关联关系（直接或间接）需要相互通信。
当两个或多个进程在访问共享资源时，如何确保它们不会相互妨碍？— 进程互斥问题
当进程之间存在着某种依存关系时，如何来调整它们运行的先后次序？—进程同步问题
临界资源：一次仅允许一个进程访问的资源（共享变量、共享内存、共享文件、共享设备等）。
临界区：在每个程序中，访问临界资源的那段程序。
实现互斥访问的四个条件：
- 任何两个进程都不能同时进入临界区
如何实现进程互斥：
- 硬件方法：基于关闭中断的互斥实现
- 软件方法：基于繁忙等待的互斥实现
- 信号量
实现互斥访问的四个条件：
- 任何两个进程都不能同时进入临界区（忙则等待）
- 不能事先假定 CPU 的个数和运行速度
- 某进程不在临界区，不能阻止其他进程进入临界区（空闲让进，让权等待）
- 某进程申请进入临界区，应该在有限时间内得以进入临界区（有限等待）
进程的特性
动态性
程序的运行状态在变，PC、寄存器、堆和栈等；
独立性
进程是系统调度和资源分配的独立单位。每个进程在一个“虚拟计算机”上运行，每个进程都有“自己”的寄存器和内部状态，拥有自己独立的进程控制块PCB
并发性
从宏观上看各进程是同时独立运行的。
进程的三种状态
- 运行状态：进程占有CPU，并在CPU上运行；
- 就绪状态：一个进程已经具备运行条件，但由于CPU忙暂时不能运行的状态（当调度给其CPU时，立即可以运行）；
- 等待状态（阻塞状态）：进程因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）。
- 就绪 -> 运行：通过进程调度程序获得CPU
- 运行 -> 就绪：一个进程已经运行了足够长时间，调度程序为保证公平会剥夺CPU分配给其他进程
- 运行 -> 等待：运行中申请的资源未得到，等待某一进程提供资源
- 等待 -> 就绪：当所等待的事件发生时
进程控制块（PCB）
系统为了管理进程设置的一个专门的数据结构，用来记录进程的外部特征，描述进程的变化过程：
- 包含三方面信息：进程管理、存储管理，文件管理
- 进程是进程存在的唯一表示，进程与 PCB 是一一对应的
PCB 存放在哪儿，如何组织 PCB
存放在消息队列里面
- 不同的状态分别用不同的链队列来表示（运行队列、就绪队列、各种类型的阻塞队列）
- 当一个进程的状态发生变化，它的PCB从一个状态队列中出队列，入队列到另外一个状态队列
信号量
进程调度
FCFS
FCFS（First-Come, First-Served）是操作系统中的一种调度算法，它的意思是“先来先服务”。也就是说，按照进程到达的顺序来分配 CPU 时间。
具体工作原理：
- 进程排队：操作系统把所有等待运行的进程按它们到达的顺序排成一个队列。
- 处理顺序：系统会按照队列中的顺序，依次给每个进程分配 CPU 时间，直到该进程完成。
- 不抢占：FCFS 是一种非抢占式调度算法，这意味着一旦一个进程开始运行，它就会一直运行到完成，期间不会被其他进程打断。
假设有 3 个进程，它们到达的顺序是：
- 进程 A（到达时间：0，执行时间：4）
- 进程 B（到达时间：1，执行时间：3）
- 进程 C（到达时间：2，执行时间：2）
按照 FCFS 算法，执行顺序如下：
- 进程 A 先执行，执行 4 个单位时间（从时间 0 到时间 4）
- 然后进程 B 执行，执行 3 个单位时间（从时间 4 到时间 7）
- 最后进程 C 执行，执行 2 个单位时间（从时间 7 到时间 9）
缺点：
- 如果某个长时间运行的进程排在队列前面，会导致后面的进程都需要等很久，这叫做 "convoy effect"（车队效应），造成系统响应时间较长。
- 不能有效地优化平均等待时间。
短作业优先（SJF/SPF）算法
短作业优先（SJF，Shortest Job First），也叫短作业优先调度算法，是一种根据进程的执行时间（即作业长度）来决定执行顺序的调度算法。它的基本思想是，选择最短的作业（即最短的执行时间）优先执行，以最小化系统的等待时间和响应时间。
特点：有剥夺和非剥夺两种方式
先来讲非剥夺式的 SJF 调度算法
系统根据每个进程的预计执行时间来排队，执行最短的进程。进程完成后，系统选择下一个剩余时间最短的进程继续执行。
假设有 4 个 进程
SJF（非剥夺）运行进度表
- 平均周转时间 =
- 平均等待时间
抢占式版本：短作业优先（SRTF，Shortest Remaining Time First）
SJF 算法有一个抢占式版本，叫短作业剩余时间优先（SRTF）。在 SRTF 中，如果一个新的进程到达且其剩余执行时间比当前运行进程的剩余时间短，系统会立即抢占当前进程，选择执行剩余时间更短的进程。
SJF（剥夺）运行进度表
- 平均周转时间
- 平均等待时间
优缺点：
- 与FCFS相比，降低了系统的平均等待时间和平均周转时间，改善了系统性能；
- 很难准确预测进程的执行时间，致使该算法很难真正做到短进程优先；
- 可能导致长进程饥饿，对长进程不公平；
- 不能依据作业的紧迫程度来划分执行的优先级。
时间片轮转法（RR）
将所有就绪进程按到达时间的先后次序排成一个队列，按FCFS选择队首的进程执行，并规定其执行完一个时间片时，系统将它送至就绪队列的末尾，再把CPU分配给就绪队列的队首进程。
特点：属于剥夺调度方式，分时系统的典型调度算法。
例：有4个进程P1，P2，P3，P4，假设它们都在时刻0到达，到达的顺序为P1、P2、P3、P4，它们的执行时间分别为6、4、8、5（s），若采用时间片轮转调度算法调度，试给出当时间片分别为1s和4s时进程的运行进度表，并计算平均周转时间和平均等待时间。
- 平均周转时间
- 平均等待时间
- 平均周转时间
- 平均等待时间
时间片大小对性能的影响：
- 若时间片足够大，退化为 FCFS 算法
- 若时间片太小，开销大
影响时间片长短设置的因素
- 系统的响应时间
- 就绪队列中的进程个数
- 系统的处理能力
死锁
一组进程由于竞争资源或者由于彼此通行不当而永远阻塞的现象
产生死锁的原因：
-
资源不足导致的资源竞争：多个进程所共享的资源不足，引起它们对资源的竞争
-
并发执行的顺序不当：进程运行过程中，请求和释放资源的顺序不当，如 P，V 操作的顺序不当
-
可抢占的资源：当一个进程正在使用这种类型的资源时，可以把它拿走而不会对该进程造成任何不良的影响。例如：CPU、内存。
-
不可抢占的资源：当一个进程正在使用这种类型的资源时，如果强行把它拿走，将会导致该进程运行失败。例如：输入、输出设备。
-
死锁主要由不可抢占资源引起
死锁的必要条件
- 互斥条件：一个资源一次只能被一个进程所使用
- 请求和保持条件：一个进程已占有了分给它的资源，但仍然要求其他资源
- 不可抢占条件：一个资源仅能被占有它的进程所释放，而不能被别的进程抢占
- 环路等待条件：存在一条由两个或多个进程所组成的环路链，其中每一个进程都在等待环路链中下一个进程所占用的资源
资源分配图的化简
- 在图中找一个进程顶点
， 的所有请求边均能立刻满足 - 若找到了这样的
，则将与 相连的边（包括分配边）全部删去 - 若找不到这样的进程顶点，则针对无请求边的
，删去其所有的分配边，转 1。否则化简结束
死锁的充分条件（死锁定理）：当且仅当资源分配图为不可完全化简状态
一旦检测出死锁，常有以下方法来从死锁中恢复：
- 剥夺资源：从一个或多个进程中抢占足够数量的资源分配给被死锁的进程；
- 撤消进程：相继的逐个撤销死锁进程直至死锁不再存在（在每个进程撤销后，都要使用死锁检测算法以确定死锁是否依然存在）。
- 进程回退：将死锁进程退回到前一个备份点，并重新从该备份点启动这些进程（前提是系统必须提供备份日志和重新启动的机制）；
一个状态被称为是“安全的”，必须满足以下的两个条件：
- 它自身不存在着死锁问题；
- 存在着某种调度顺序，使得即使在最坏的情况下（所有的进程突然间同时请求它们最大数目的资源），每一个进程都能够顺利地运行结束。
银行家算法
银行家算法通过模拟系统资源的分配，判断是否会导致不安全的状态。它的核心原则是：系统分配资源时，始终确保每个进程在未来能满足它的需求并最终完成。
银行家算法的目标是保持系统始终处于安全状态，即在每次资源分配之前，系统会预先判断是否会进入不安全状态。如果分配资源后系统变成了不安全状态，银行家算法就会拒绝资源的分配。
存储器管理
存储器的层次结构
在计算机执行时，几乎每一条指令都涉及对存储器的访问，因此要求对存储器的访问速度能跟得上处理机的运行速度。或者说，存储器的速度必须非常快，能与处理机的速度相匹配，否则会明显地影响到处理机的运行。此外还要求存储器具有非常大的容量，而且存储器的价格还应很便宜。
对于通用计算机而言，存储层次至少应具有三级：最高层为 CPU 寄存器，中间为主存，最底层是辅存。在较高档的计算机中，还可以根据具体的功能细分为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层
在计算机系统的存储层次中，寄存器和主存储器又被称为可执行存储器。对于存放于其中的信息，与存放于辅存中的信息相比较而言，计算机所采用的访问机制是不同的，所需耗费的时间也是不同的。进程可以在很少的时钟周期内使用一条 load 或 store 指令对可执行存储器进行访问。但对辅存的访问则需要通过 I/O 设备实现，因此，在访问中将涉及到中断、设备驱动程序以及物理设备的运行，所需耗费的时间远远高于访问可执行存储器的时间，一般相差3个数量级甚至更多。
主存储器
主存储器简称内存或主存，是计算机系统中的主要部件，用于保存进程运行时的程序和数据，也称可执行存储器。
寄存器
寄存器具有与处理机相同的速度，故对寄存器的访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大。
高速缓存
高速缓存是现代计算机结构中的一个重要部件，它是介于寄存器和存储器之间的存储器，主要用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数，这样可大幅度地提高程序执行速度。高速缓存容量远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。
磁盘缓存
由于自前磁盘的1/O速度远低于对主存的访问速度，为了缓和两者之间在速度上的不匹配，而设置了磁盘缓存，主要用于暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数。但磁盘缓存与高速缓存不同，它本身并不是一种实际存在的存储器，而是利用主存中的部分存储空间暂时存放从磁盘中读出（或写入）的信息。主存也可以看作是辅存的高速缓存，因为，辅存中的数据必须复制到主存方能使用，反之，数据也必须先存在主存中，才能输出到辅存。
程序的装入
用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通常都要经过以下几个步骤：
- 编译，由编译程序（Compiler）对用户源程序进行编译，形成若干个目标模块（ObjectModule）
- 链接，由链接程序（Linker）将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块（Load Module）
- 装入，由装入程序（Loader）将装入模块装入内存
我们先介绍一个无需进行链接的单个目标模块的装入过程。该目标模块也就是装入模块。在将一个装入模块装入内存时，可以有如下三种装入方式：
1.绝对装入方式
当计算机系统很小，且仅能运行单道程序时，完全有可能知道程序将驻留在内存的什么位置。此时可以采用绝对装入方式。用户程序经编译后，将产生绝对地址（即物理地址）的目标代码
2.可重定位装入模式
绝对装入方式只能将目标模块装入到内存中事先指定的位置，这只适用于单道程序环境。而在多道程序环境下，编译程序不可能预知经编译后所得到的目标模块应放在内存的何处。因此，对于用户程序编译所形成的若干个目标模块，它们的起始地址通常都是从0开始的，程序中的其它地址也都是相对于起始地址计算的。
如果这个程序还是在 3000 这个位置去找这个语句，肯定是会报错的
我们在装入内存的时候，我们把 LOAD 3000 这个指令改成 LOAD 13000
3.动态运行时的装入方式
可重定位装入方式可将装入模块装入到内存中任何允许的位置，故可用于多道程序环境。但该方式并不允许程序运行时在内存中移动位置。
于是，我们需要动态运行时的装入方式，装入内存的时候，指令还是装入 LOAD 3000，在运行的时候，需要寻找 3000 地址真正所在的位置
程序的链接
1.静态链接
在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开。
在图中示出了经过编译后所得到的三个目标模块A、B、C，它们的长度分别为L，M，N。
在模块A中有一条语句 CALL B ，用于调用模块B。在模块 B 中有一条语句 CALL C，用于调用模块 C。 B 和 C 都属于外部调用符号，在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：
- 对相对地址进行修改
- 变换外部调用符号
什么是对相对地址的修改，如果在 B 的目标模块里面有一个内存 20，那么在装入 B 的装入模块里面就应该是 B + 20
什么是变换外部调用符号，就是我们在模块 A 里面调用 B 的位置，那么在 A 的装入模块里面就变成了跳转到 L
静态链接就是在程序装入的时候，把这两个操作写死了
2.装入时动态链接
这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要按照图中所示的方式修改目标模块中的相对地址。装入时动态链接方式有以下优点：
- 便于更新和修改
- 便于实现对目标模块的共享
3.运行时动态链接
在许多情况下，应用程序在运行时，每次要运行的模块可能是不相同的。但由于事先无法知道本次要运行哪些模块，故只能是将所有可能要运行到的模块全部都装入内存，并在装入时全部链接在一起。显然这是低效的，因为往往会有部分目标模块根本就不运行。比较典型的例子是作为错误处理用的目标模块，如果程序在整个运行过程中都不出现错误，则显然就不会用到该模块。
连续分配存储管理方式
单一分配方式
在单道程序环境下，当时的存储器管理方式是把内存分为系统区和用户区两部分，系统区仅提供给OS使用，它通常是放在内存的低址部分。而在用户区内存中，仅装有一道用户程序，即整个内存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。
固定分区分配
划分分区的方法
- 分区大小相等
- 分区大小不等
为了便于内存分配，通常将分区按其大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址，大小及状态（是否已分配）
动态分区分配
动态分区分配中的数据结构
常用的数据结构有以下两种形式
- 空闲分区表
在系统中设置一张空闲分区表，用于记录每个空闲分区的情况，每个空闲分区占一个表目，表目中包括分区号，分区大小和分区起始地址等数据项
- 空闲分区链
为了实现对空闲分区的分配和链接，在每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，在分区尾部则设置一后向指针。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链，如图4-7所示。
- 动态分区分配算法
为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。由于内存分配算法对系统性能有很大的影响，故人们对它进行了较为广泛而深入的研究，于是产生了许多动态分区分配算法。
- 分区分配操作
（2）分配操作
系统应利用某种分配算法，从空闲分区链（表）中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小可表示为 m.size。
我们在看这个表
假设我们的 u.size 为 68，找到一个比 u.size 大的 m.size 然后查看 m.size-u.size 的大小
（2）回收内存
页式存储
- 逻辑空间等分为页；并从0开始编号
- 内存空间等分为块，与页面大小相同；从0开始编号
通过 页表实现逻辑页到物理页框的映射。
分页中最核心的三个概念
- 页：程序被切分后的小块
- 页框：内存被切分后的小块
- 页表：记录“第几页 → 在第几个页框”
在分页系统中：逻辑地址 = 页号 + 页内偏移量
例如一个 32 位地址系统：
| 页号 (20位) | 页内偏移 (12位) |
- 页号：第几页？
- 偏移量：这一页里的第几个字节？
假设：
- 逻辑地址是：
(页号 = 3，偏移 = 100) - 页表中查到：
第 3 页 → 放在第 8 号页框
那么有：物理地址 = 8 号页框起始地址 + 100
这一步是由：MMU（内存管理单元）自动完成
分页解决了什么根本问题
在分页之前（连续分配）：
- 程序必须整块连续存放
- 容易产生 外部碎片
- 内存利用率低
分页之后：
- 程序可以 零散存放
- 不再需要连续内存
- 彻底消除了外部碎片
- 支持 虚拟内存
地址变换原理及步骤
请看上图，给出逻辑地址的页号和页内地址，开始进行地址变换：
- 在被调进程的PCB中取出页表始址和页表大小，装入页表寄存器
- 页号与页表寄存器的页表长度比较，若页号大于等于页表长度，发生地址越界中断，停止调用，否则继续
- 由页号结合页表始址求出块号
- 块号&页内地址，即得物理地址