cpu时间分片
时间片是什么
CPU时间片是操作系统实现多任务并发执行的核心机制，它通过将CPU资源划分为小的时间段（时间片），并轮流分配给不同的任务（进程或线程），使得多个任务在宏观上看起来是同时运行的。
从宏观视角来看，用户可以同时打开多个应用程序，比如一边听音乐一边浏览网页，仿佛这些程序在并行运行。然而，从微观视角来看，CPU在同一时间只能执行一个任务，操作系统通过时间片轮转调度，快速切换任务，模拟出“并行”的效果。
举个例子： CPU先执行线程A一段时间，然后再执行线程B一段时间，然后再执行线程A一段时间，CPU时间被切分成短的时间片、分给不同线程执行的策略就是CPU时间分片。时间分片是对调度策略的一个极度简化，实际上操作系统的调度策略非常精细，要比简单的时间分片复杂的多。如果一秒钟被分成大量的非常短的时间片，比如100个10毫秒的时间片，10毫秒对人的感官而言太短了，以致于用户觉察不到延迟，仿佛计算机被该用户的任务所独占（实际上并不是），操作系统通过进程的抽象获得了这种任务独占CPU的效果（另一个抽象是进程通过虚拟内存独占存储）。
轮转调度算法
在谈到时间片时用到最多概念是时间片轮转，时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法是时间片调度。每个进程被分配一个时间段，称作它 的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU 当即进行切换。调度程序所要做的就是维护一张就绪进程列表，，当进程用完它的时间片后，它被移到队列的末尾。
时间片轮转调度中有趣的一点是时间片的长度。从一个进程切换到另一个进程是需要一定时间的--保存和装入寄存器值及内存映像，更新各种表格和队列等，即上下文切换（context switch）。
时间片的长度对系统性能有重要影响。如果时间片过短，任务切换会非常频繁，虽然系统的响应速度更快，但上下文切换的开销会增加，导致CPU效率降低。相反，如果时间片过长，虽然减少了上下文切换的次数，但可能导致任务响应变慢，影响用户体验。因此，现代操作系统通常会根据任务类型和系统负载动态调整时间片长度，以平衡效率和响应性。例如，交互式任务（如浏览器、编辑器）需要较短的时间片以确保快速响应，而计算密集型任务（如视频渲染）则可以分配较长的时间片以减少切换开销。
时间片轮转调度算法基本原理
在早期的时间片轮转法中,系统将所有的就绪进程按先来先服务的原则,排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片.时间片的大小从几ms到几百ms.当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片.这样就可以保证就绪队列中的所有进程,在一给定的时间内,均能获得一时间片的处理机执行时间.
在早期的时间片轮转调度算法中需要根据以下参数来计算时间片的大小：
- 系统对响应时间的要求
- 就绪队列中进程的数目
- 系统的处理能力
时间片是调度策略的基础，但现代操作系统的调度策略远比简单的时间片轮转复杂。
多级反馈队列调度算法 （ MLFQ）
多级反馈队列调度算法（Multilevel Feedback Queue Scheduling, MLFQ） 是一种动态优先级调度算法，结合了时间片轮转调度和优先级调度的特点。它通过设置多个优先级队列，并根据进程的行为动态调整其优先级，从而在兼顾响应时间的同时，提高系统的吞吐量和公平性。
(1) 多级队列
- 系统设置多个就绪队列（通常为 3~5 个），并为各个队列赋予不同的优先级。
- 优先级：第一个队列的优先级最高，第二个队列次之，依次递减。
- 时间片大小：优先级越高的队列，时间片越小。例如：
- 第一队列的时间片为 8ms。
- 第二队列的时间片为 16ms。
- 第三队列的时间片为 32ms。
(2) 进程调度规则
- 新进程进入：新进程首先被放入第一队列（优先级最高）的末尾，按照先来先服务（FCFS）的原则等待调度。
- 时间片用完：
- 如果进程在当前队列的时间片内完成，则撤离系统。
- 如果进程未完成，则被降级到下一个优先级较低的队列，并重新排队等待调度。
- 低优先级队列运行：
- 仅当所有更高优先级的队列为空时，才会调度当前队列中的进程。
- 如果正在运行低优先级队列的进程时，有新进程进入更高优先级的队列，则抢占当前进程，将其放回当前队列的末尾，并调度新进程。
(3) 动态优先级调整
- 如果一个进程在较低优先级队列中等待了很长时间，可以将其提升优先级，以避免“饥饿”现象。
- 这种动态调整机制使得算法能够适应不同类型的进程（如交互式进程和批处理进程）。
优先权调度算法（PSA）
优先权调度算法（Priority Scheduling Algorithm） 是一种基于进程优先级的调度算法，它根据进程的优先级来决定哪个进程先获得 CPU 资源。优先权调度算法可以分为非抢占式和抢占式两种类型，同时优先权本身也可以分为静态优先权和动态优先权。
优先权调度算法的类型
非抢占式优先权调度算法
- 工作原理：
- 系统将 CPU 分配给就绪队列中优先级最高的进程。
- 该进程会一直运行，直到完成或主动放弃 CPU（如等待 I/O 操作）。
- 只有在当前进程完成后，系统才会重新调度优先级最高的进程。
- 优点
- 实现简单，上下文切换次数较少。
- 缺点
- 高优先级进程可能需要等待低优先级进程完成，导致响应时间较长。
抢占式优先权调度算法
- 工作原理：
- 系统将 CPU 分配给优先级最高的进程。
- 如果在运行过程中出现优先级更高的进程，系统会立即停止当前进程，并将 CPU 分配给新进程。
- 优点
- 能够快速响应高优先级任务，适合实时系统。
- 缺点：
- 上下文切换频繁，增加了系统开销。
优先权的类型
静态优先权
- 定义：
- 进程的优先级在创建时确定，且在进程的整个生命周期内保持不变。
- 优先权的表示：
- 通常用一个整数表示优先级，例如 0~7 或 0~255。
- 不同系统的表示方式可能不同：
- 有些系统用 0 表示最高优先级，数值越大优先级越低。
- 有些系统则相反，数值越大优先级越高。
- 确定优先权的依据：
- 进程类型：系统进程通常比用户进程优先级高。
- 资源需求：资源需求较少的进程可能获得更高的优先级。
- 用户要求：用户可以为某些进程指定更高的优先级。
动态优先权
- 定义：
- 进程的优先级在运行过程中可以动态调整，以提高调度性能。
- 调整规则:
- 根据进程的等待时间、运行时间或其他因素动态调整优先级。
- 例如：
- 随着进程等待时间的增加，优先级逐渐提高。
- 长时间运行的进程优先级逐渐降低。
- 优点：
- 避免低优先级进程长时间得不到调度（“饥饿”问题）。
- 提高系统的公平性和响应性。
高响应比优先调度算法
高响应比优先调度算法（Highest Response Ratio Next, HRRN）是一种动态优先权调度算法，结合了短作业优先（SJF）和先来先服务（FCFS）的优点。
响应比的定义 响应比（Response Ratio, RR）的计算公式为：
- 等待时间：进程在就绪队列中等待的时间。
- 服务时间：进程需要运行的时间。
调度规则：
- 系统选择响应比最高的进程进行调度。
- 响应比的计算公式可以进一步简化为：
算法的特点
- 短作业优先：
- 如果等待时间相同，服务时间越短的作业，响应比越高，优先被调度。
- 先来先服务：
- 如果服务时间相同，等待时间越长的作业，响应比越高，优先被调度。
- 避免长作业饥饿：
- 长作业的响应比会随着等待时间的增加而提高，最终也能获得调度。 优点
- 兼顾了短作业和长作业的需求。
- 避免了短作业优先调度算法中长作业可能“饿死”的问题。
- 实现简单，适用于批处理系统。
假设有三个作业:
- 作业 A：到达时间 0，服务时间 3。
- 作业 B：到达时间 1，服务时间 6。
- 作业 C：到达时间 2，服务时间 4。 调度过程如下：
- 时间 0：只有作业 A 到达，开始运行。
- 时间 3：作业 A 完成，计算作业 B 和 C 的响应比：
- 作业 B：等待时间 = 2，响应比 = 1 + 2/6 ≈ 1.33。
- 作业 C：等待时间 = 1，响应比 = 1 + 1/4 = 1.25。
- 选择响应比更高的作业 B 运行。
- 时间 9：作业 B 完成，作业 C 开始运行。
- 时间 13：作业 C 完成。
YJ