目录进程的优先级怎么实现细节信息进程和进程的关系进程的切换切换的理解Linux内核真实的调度算法总结进程的优先级CPU 资源分配的先后顺序就是指进程的优先权priority。优先权高的进程有优先执行权利。为什么需要优先级因为 CPU 资源有限进程很多必须决定谁先运行。怎么实现优先级实际上是一种数字(int ,char各不相同)数字越低优先级越高反之越低。一个小知识大部分操作系统是基于时间片的分时操作系统 把 CPU 时间切成一小片一小片轮流分给每个进程让每个进程都能“雨露均沾”地运行。他是为了考虑相对公平性。有了时间片让每个进程都分到一点时间但是时间的长短不同优先级越高时间越长因此优先级时间片可以变化变化幅度不能太大。查找详细的优先级信息输入命令前提是myprocess跑起来了ps -al |head - l | ps -al |grep myprocess细节信息UID:执行者身份系统怎么知道我访问文件的时候是拥有组、所属组还是other?答案就是他的UID至于名字是给我们看的系统看的是UID。识别权限不是识别用户的而是进程和文件的权限的。因此Linux系统中访问任何资源都是进程访问进程代表用户。PRI:进程的优先级默认80NI:进程的修正数据nice值0进程真实的优先级PRI(默认)NI更改优先级在进程启动的时候输入top进入了一个页面输入r输入要修改的进程pid输入要修改的值(nice)。注意系统为了保证安全性优先级不能频繁的更改。nice和优先级极值的问题进程的优先级设计不合理会导致进程优先级低的进程长时间得不到CPU资源导致进程饥饿进程和进程的关系竞争性系统进程数目众多而CPU资源只有少量甚至1个所以进程之间是具有竞争属性的。为了高效完成任务更合理竞争相关资源便具有了优先级。——所以才有了权限和优先级的概念。。独立性 多进程运行需要独享各种资源多进程运行期间互不干扰并行多个进程在多个CPU下分别同时进行运行这称之为并行并发多个进程在⼀个CPU下采⽤进程切换的方式在⼀段时间之内让多个进程都得以推进称之为并发。进程的切换死循环进程怎么运行当写一段while(1)死循环代码运行会一卡一卡的但是他不会死机。一旦一个进程占有CPU会一次性把代码跑完吗——不会除非很短。一个进程CPU会分配时间片一旦跑完了时间片但是进程本身没有完这个进程会被CPU拿下来重新分配到运行队列里面下次重新到他了会继续运行所以一个进程分配一定的时间片防止在CPU一直占用资源。如果只执行这个进程其他进程如果不执行整个系统可能会崩溃。因此死循环不会打死进程不会一直占用CPU。CPU和寄存器的再了解CPU执行进程的时候和PCB关系不大但他会访问对应的代码和数据一条一条拿到CPU为了处理一条条代码和数据CPU内部会有很多寄存器保存进程的临时数据。小结论寄存器!寄存器里面数据和代码。寄存器是一个保存数据的空间数据是内容。内容可以是变化的空间永远是那个空间。切换的理解疑问当前进程要把自己的进程硬件上下文数据保存起来保存到哪里了可以先理解为保存到进程的take_struct里面里面有一个TSS任务状态段。CPU怎么区分是全新的进程还是已经调度过的进程take_struct里面里面有一个isrunning的变量一旦被调度了就会变成1他是一个bool类型。Linux内核真实的调度算法实时操作系统和分时操作系统runqueuestruct rq { spinlock_t lock; // 保护队列的锁 unsigned long nr_running; // 运行队列中的进程总数 unsigned long nr_switches; // 上下文切换次数 struct task_struct *curr; // 当前正在运行的进程 struct task_struct *idle; // 空闲进程 struct prio_array *active; // 活动队列指针 struct prio_array *expired; // 过期队列指针 // ... };字段作用nr_running队列里有多少个就绪进程curr当前正在 CPU 上运行的进程active指向活动队列时间片还没用完的进程expired指向过期队列时间片用完的进程核心结构prio_array图中蓝色和红色框是prio_array这是 O(1) 调度的核心数据结构。struct prio_array { unsigned int nr_active; // 活跃进程数 DECLARE_BITMAP(bitmap, 140); // 位图标记哪些队列非空 struct list_head queue[140]; // 140 个优先级队列 };字段作用nr_active这个数组里有多少个进程bitmap[5]5 个 32 位整数 160 位标记 140 个队列是否非空queue[140]140 个链表每个优先级一个为什么是 140普通优先级100~139对应 nice 值 -20~19实时优先级0~99总共 140 个两个队列active 和 expired图中最核心的设计是两个 prio_array队列颜色放什么进程active活动队列蓝色时间片还没用完的进程expired过期队列红色时间片已经用完的进程两个队列结构完全一样只是放不同状态的进程。四、O(1) 调度算法的工作流程1. 调度时从 active 队列选优先级最高的进程1. 从 bitmap[5] 中找到第一个非空的优先级队列 2. 从 queue[该优先级] 中取出第一个进程 3. 这个进程就是下一个要运行的进程时间复杂度O(1)因为找非空队列bitmap 查找几条指令取进程链表头取O(1)不随进程数量增加而变慢。2. 进程时间片用完时移到 expired 队列1. 进程时间片用完 2. 从 active 队列移除 3. 重新计算时间片 4. 移到 expired 队列3. active 队列空了交换 active 和 expired1. active 队列空了 2. 交换 active 和 expired 指针 3. 原来的 expired 变成 active 4. 进程重新参与调度这就是图中*active和*expired两个指针的作用。图解工作流程初始状态 active → [队列 100~139] 有进程 A、B、C expired → [队列 100~139] 空 调度 A active → [队列 120] A、B、C A 运行时间片用完 A 移到 expired 调度 B B 运行时间片用完 B 移到 expired 调度 C C 运行时间片用完 C 移到 expired active 空了 交换 active 和 expired active → [队列 120] A、B、C expired → 空 循环继续...优先级和 bitmap 的关系bitmap 的作用快速找到非空队列。bitmap[5] 5 个 32 位整数 160 位 第 0 位 → 优先级 0 是否非空 第 1 位 → 优先级 1 是否非空 ... 第 139 位 → 优先级 139 是否非空 找非空队列 遍历 bitmap找到第一个为 1 的位 该位对应的优先级就是最高优先级举例bitmap 0000...0001 0000...0000 ↑ 第 120 位为 1 → 优先级 120 非空 → 从 queue[120] 取进程为什么是 O(1)操作复杂度找最高优先级非空队列O(1)bitmap 查找从队列取进程O(1)链表头取把进程加入队列O(1)链表尾插交换 active/expiredO(1)交换指针不管系统里有 10 个进程还是 10000 个进程调度时间都是常数。这就是 O(1) 调度算法的核心优势。O(1) 调度算法的优点优点说明时间复杂度 O(1)不随进程数增加而变慢优先级支持140 个优先级支持实时和普通进程公平性active/expired 机制保证所有进程都能运行缓存友好bitmap 和 queue 数组紧凑多 CPU 支持每个 CPU 一个 runqueueO(1) 调度算法的缺点缺点说明交互性差对交互式进程如桌面响应不够快公平性不够精细只按优先级排队不区分进程行为时间片固定不考虑进程实际需求这也是后来被 CFS完全公平调度器取代的原因。总结问题答案O(1) 调度算法是什么Linux 2.6 的调度算法时间复杂度 O(1)核心数据结构runqueue prio_arrayactive 和 expired 是什么活动队列时间片未用完 过期队列时间片用完怎么找下一个进程从 bitmap 找最高优先级非空队列取队头为什么是 O(1)bitmap 查找和链表操作都是常数时间active 空了怎么办交换 active 和 expired 指针为什么被淘汰交互性差被 CFS 取代核心理解O(1) 调度算法用 active 和 expired 两个队列配合 bitmap 和 140 个优先级队列实现常数时间的调度。进程时间片用完移到 expiredactive 空了就交换两个指针循环往复。这是 Linux 2.6 的经典调度算法。上图是本人用AI做的解释因为感觉自己纯文字说不清楚。加上下面的图理解一下吧。