[!quote] 虚拟化 CPU 虚拟化 CPU 就是将单个 CPU，或 CPU 的其中一小部分转换为看似无限数量的 CPU，从而让许多程序看似同时运行
- 不过会造成性能损失，因为如果 CPU 必须共享，每个进程的运行就会慢一点
受限直接执行
[!hint] 为什么要限制 ？
- 让正在运行的进程有限制，不然进程有可能做一些坏事；
- 还需要让正在运行的进程能够随时停止，以便切换进程，实现虚拟化 CPU 的时分共享；
- 确保一直高效地运行进程；
进程不受限的直接执行
![[操作系统 Draw#^group=lwSh7jW0|825]]
如何让程序受限制地运行？
用户模式：是一种处理器模式，其中运行的代码受到许多限制 内核模式：操作系统就以这种模式运行，其中运行的代码可以做特权操作
在用户模式下运行时，进程无法直接访问系统总线或其他硬件接口，所以进程不能直接发出 I/O 请求或访问其他系统资源。 如果进程尝试在用户模式下发出 I/O 请求或访问其他系统资源，处理器会引发异常，并将控制权传递给操作系统。操作系统可能会终止进程或将其转换为特权模式【以便访问系统资源并执行请求的操作】。这种机制可以确保进程无法绕过操作系统和硬件实现的保护机制，从而保持系统的安全性和稳定性。
如果用户希望执行特权操作，该怎么办？
用户程序可以执行系统调用，来执行特殊的 陷阱指令。
之后处理器会将当前进程的一些寄存器的值保存到该进程的内核栈中，以便在从陷阱返回时能够正确恢复执行的上下文。
然后处理器会将控制权转移给操作系统内核，并执行与陷阱类型相关的处理程序。
一旦操作系统完成相关的陷阱工作，操作系统会调用一个特殊的 从陷阱返回指令，将控制权返回到发起调用的用户程序中，再次回到用户模式下。
具体的系统调用是怎么实现的？
系统调用发起后，程序会将系统调用号和参数传递给操作系统内核，内核会根据系统调用号来执行相应的 内核代码 来完成这些操作 #问题
如何让用户进程不能随意跳转到内核中的任意位置执行代码？
- 操作系统内核会针对每一种系统调用都编写相应的内核代码，并在内核中分配固定的入口地址。程序只能通过发起系统调用来调用这些内核代码，而无法直接跳转到内核中的任意位置。
- 此外，操作系统内核还会对每一个进程都维护一个 用户态 和 内核态 的地址空间。 程序只能通过系统调用访问内核态的地址空间，以执行特权操作。
这样，即使程序想要执行一些恶意代码，也无法直接访问内核态的地址空间，从而保证了操作系统的安全性。
陷阱表：通常用于处理软件中断【系统调用、断点、除以 0 等】。其中每个表项对应一个中断号和对应的中断处理程序的入口地址
| 陷阱表 | |
|---|---|
| 中断向量号 | 处理程序地址 |
| 0 | 0x1000 |
| 1 | 0x1020 |
| 2 | 0x1040 |
| ... | ... |
| 中断向量表：通常用于处理硬件中断【磁盘 I/O 完成、网络数据包到达、定时器时间到达等】。每个表项对应一个硬件中断号和对应的中断处理程序的入口地址 |
如何切换进程？如何重获 CPU 的控制权？
如果一个进程在 CPU 上运行，这就意味着操作系统没有运行。如果操作系统没有运行，那它显然没有办法切换进程
- 如果进程听话【会发生系统调用】：OS 通过等待系统调用，或某种非法操作发生，从而重新获得 CPU 的控制权。
- 那如果 进程不听话【从不进行系统调用】，并且一直循环：==利用时钟中断==【时钟设备可以编程为每几毫秒产生一次中断】。产生中断时，正在运行的进程停止，然后中断处理程序会运行，此时操作系统重新拿回了控制权。
那接下来是继续运行这个进程？还是切换进程？那就是由 调度程序 决定
切换进程的过程是怎么样的？
OS 会执行上下文切换【操作系统会为正在执行的进程保存寄存器的值到它的内核栈，并为即将执行的进程从它的内核栈恢复寄存器的值】，接着切换栈。这样一来，操作系统就可以确保最后执行从陷阱返回指令时，是执行另一个进程。
进程调度
假设工作负载：
- 每一个工作运行相同的时间；
- 所有的工作同时到达；
- 一旦开始，每个工作保持运行直到完成；
- 所有的工作只使用 CPU【不执行 IO 操作】；
- 每个工作的运行时间是已知的;
调度指标：
- T 周转时间 = T 任务完成时间 -T 任务开始时间【由于假设了所有工作同时到达所以都是 0】
- 公平：如果优化了 T 周转时间，相当于优化了性能，那代价就是要阻止一些任务的运行【这就是不公平】
- T 响应时间 = T 首次运行 -T 到达时间
==可以看出 T 周转时间与 T 响应时间是相悖的==
先进先出 FIFO
3 个工作 A、B 和 C 在大致相同的时间（T 到达时间 = 0）到达系统。因为 FIFO 必须将某个工作放在前面，所以我们假设当它们都同时到达时，A 比 B 早一点点，然后 B 比 C 早到达一点点 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=zYtSx3RS|700]]
- 优点：很简单，易于实现
- 缺点：如果耗时较少的进程被排在耗时很长的进程之后，那麻烦了
最短任务优先 SJF
如果 A，B，C 同时到达，那确实优化了 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=Imt0J5rF|372]] 如果 A 先到达呢？那又麻烦了 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=T6ZvE4VN|387]]
- 优点：任务同时到达时，有优势
- 缺点：任务不同时到达时，又会出现像 FIFO 一样的劣势
抢占式最短作业优先 STCF
![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=P7lQVDnC]]
- 优点：可以优化 SJF 在到达时间不同时的劣势
- 缺点：对于响应时间的优化不好【例如 A,B,C 同时到达，但是 C 有可能要等待 A, B 执行完后才可以执行】
如果有进程执行 IO 操作怎么办？
假设有两项工作 A 和 B，每项工作需要 50ms 的 CPU 时间。但是 A 每运行 10ms，然后发出 I/O 请求【假设 I/O 每个都需要 10ms】，而 B 只是使用 CPU 50ms，不执行 I/O。调度程序先运行 A，然后运行 B。 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=B6QGS9l6|670]] 这里的 STCF 运用了重叠
轮转 RR
![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=festMAZT|750]]
- 优点：优化了响应时间
- 缺点：周转时间非常糟糕；时间片太短会导致上下文切换频繁，导致影响整体的性能
如果你愿意不公平【不轮转】，你可以运行较短的工作直到完成，但是要以响应时间为代价 如果你重视公平，则响应时间会较短，但会以周转时间为代价
[!question] 可是在现实中，我们无法知道每个作业的长度，既要优化周转时间，又要兼顾响应时间，那我们如何设计调度程序呢？ 多级反馈队列（MLFQ）
多级反馈队列 MLFQ
![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=8sJzfdun|700]]
- 如果一个进程不断放弃 CPU 去等待键盘输入【频繁发生输入/输出操作】，为了确保这样的进程能够及时响应用户输入，MLFQ 将为其分配较高的优先级；
- 如果一个进程长时间地占用 CPU【持续执行计算密集型任务】，为了确保其他进程也能够得到充分的执行时间，MLFQ 会降低其优先级；
高优先级队列通常拥有较短的时间片【例如 10 毫秒或更少】： 高优先级队列的任务需要快速响应，较短的时间片长度可以使调度器更频繁地切换队列上的进程，从而提高系统的响应性能。 低优先级队列则配置更长的时间片： 低优先级队列的任务可能需要较长的连续执行时间才能完成，因此为低优先级队列配置较长的时间片可以提高 CPU 利用率，减少上下文切换的开销，并在任务之间提供较好的吞吐量。
如何改变优先级？
- 工作进入系统时，处于最高优先级
- 工作在其时间片以内主动释放 CPU，则优先级不变
- 工作用完整个时间片后，降低其优先级
![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=QgKhxsbJ|376]] ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=tt8Dp40J|500]]
目前的 MLFQ 会有什么问题？怎么解决？
问题：
- 如果系统有太多交互型工作就会不断的占用 CPU，导致密集型工作无法运行
- 可能有“聪明”的程序会在时间片快结束时，调用一个没用的 IO 操作，持续保持在高优先级
- 可能某个密集型程序在某段时间是表示出交互型的，那么它会很难享受到交互型的待遇
解决：
经过一段时间后，我们就把所有的工作都放到最高优先级队列中【这样可以 解决“饥饿”问题 和 密集型程序的间断交互型问题】 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=2Sty2oba|700]]
- 工作在其时间片以内主动释放 CPU，则优先级不变
- 工作用完整个时间片后，降低其优先级
我们重写以上这两条规则： 让调度程序记录一个进程在某一层队列中消耗的总时间，只要进程用完了其在当前队列的时间配额，就会将其降低到优先级较低的队列中【这样就 解决了有程序在愚弄 CPU 的问题】 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=W1yV2Wft|1000]]
[!summary] 总结一下 MLFQ 的 5 条规则：
- 如果优先级：A>B，则运行 A；
- 如果优先级：A=B，则轮转运行 A 和 B；
- 新工作加入系统时，放在最高优先级中；
- 一旦工作用完在某一队列中的时间份额时，降到下一队列；
- 每隔一段时间，就把所有工作重新放到最高优先级中；
彩票调度
假设有 A 和 B 两个进程，A 拥有 75 张彩票【进程占有某个资源的份额】，B 拥有 25 张。因此我们希望 A 可以占用 CPU 75% 的时间。根据彩票数量的比例来决定进程获得 CPU 时间片的概率 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=t0nRXtI5|600]]
- 优点：避免奇怪的边角情况；很轻量【只需记录几个状态】；运行起来很快；在新进程加入时，可以合理地处理
- 缺点：在工作长度短时，由于概率问题，无法准确达到预期效果
彩票转让：一个进程可以临时的把自己的彩票交给另一个进程【客户端在请求服务端时，为了加速服务端的执行，可以把自己的彩票交给服务端，完成任务后再返还】 彩票通胀：在一个互相信任的进程环境中，如果一个进程知道它自己需要更多的 CPU 时间，那么它就会增加自己的彩票
[!question] 怎么为工作分配彩票？怎么解决工作时间短引起的概率偶然性？ 运用步长调度
步长调度
系统中的每个工作都有自己的步长【这个值与票数值成反比】。例如工作 A、B、C 的票数分别是 100、50 和 250，我们通过用一个大数【比如 10000 】分别除以他们的票数来获得每个进程的步长，分别为 100、200 和 40。 当需要进行调度时，选择目前拥有最小行程值的进程，并且在运行之后将该进程的行程值增加一个步长。 ![[Excalidraw/计算机/四大件/操作系统 Draw.md#^group=uzk614lh|775]]
- 优点：不受随机性的影响，可以精准达到概率预期
- 缺点：在加入新进程时的处理不精准【比如加入了一个新进程，那我是把它的行程值设置为多少呢？如果是 0，那它就会马上执行，这样不一定好】
[!summary] 总结一下彩票调度，步长调度 这两种调度方法都没有被广泛使用【它们不能很好的适合 IO，票数分配问题没能很好地解决】 ，它们适合的领域很有限
第十章高级篇没有看，等看完并发再看 #问题