Linux2.6内核进程调理队列

目录

媒介
运行队列runqueue
活跃队列&过期队列
​编辑 bitmap[5]&O(1)调理算法
nr_active 
active指针和expired指针
最后总结

---

媒介

本篇文章是Linux进程系列中的最后一篇文章，原来是想放在上一篇文章的末端的，但是想了想还是单独写一篇文章吧，虽然说这部门内容是比较难的，全部一样平常来说是简单的提及带过的，但是为了让大家对进程有更深的明白与熟悉，还是看了一些别人的文章，然后学习了学习，然后对此做了总结，尽大概详细的介绍明白。
运行队列runqueue

首先先简单的介绍一下runqueue
runqueue 代表了一个 CPU 的停当队列，此中包罗了多个进程的 task_struct（即进程控制块）。在 Linux 等操纵系统中，每个 CPU 都会有一个独立的 runqueue，用来管理该 CPU 上的全部停当进程。每个 task_struct 存储了该进程的状态、调理信息等。
   然后下图是Linux2.6内核中进程队列的数据结构，之间关系已经给大家画出来，方便大家明白。
  然后对此根据上面的介绍，我们在对此扩展一下他的内容。
  

• 一个CPU拥有一个runqueue （struct runqueue）
  
• runqueue是CPU的PCB（task_strutc)、
  
• 假如有多个CPU就要考虑进程个数的负载平衡题目
  
• 我们现在评论的OS都是分时操纵系统，调理时夸大的是公平！
  
• 关于实时操纵系统，暂且不谈，调理时夸大的时实时性！智能自动驾驶骑车等。
  

  对于后三个的解释：
  

• 多个 CPU 和负载平衡：
  
  
  
  • 当有多个 CPU 时，进程的负载平衡题目确实是一个紧张的考虑因素。操纵系统通常会通过负载平衡策略将进程分配到差别的 CPU 上，以避免某些 CPU 过载而其他 CPU 处于空闲状态。
    
  • Linux 等现代操纵系统会定期通过进程迁徙等本领实现负载平衡，确保各个 CPU 的负载较为平衡，从而提高系统的整体效率。
    
  
  
• 分时操纵系统的调理（公平性）：
  
  
  
  • 你说的“分时操纵系统，调理时夸大的是公平性”是正确的。在分时系统中，调理的焦点目的之一是公平性，即尽量保证每个进程能够在合理的时间内获得 CPU 时间片。调理算法（好比轮转法、优先级调理等）都是为了保证这种公平性，避免某些进程长时间得不到执行。
    
  • 这种公平性通常意味着“每个进程的执行时间应该大致相称”，纵然是用户进程，也会得到相对平等的 CPU 时间，而不是长期被某个进程或线程独占。
    
  
  
• 实时操纵系统的调理（实时性）：
  
  
  
  • 当你提到“实时操纵系统，调理时夸大的是实时性”，这个说法是准确的。实时操纵系统（RTOS）与分时操纵系统的差别之处在于，它的调理目的是保证任务在规定的时间内完成，而不仅仅是公平性。
    
  • 实时性调理更侧重于时间束缚，确保任务按照严格的时间要求进行执行，这对于一些实时应用（如智能驾驶、自动化控制等）至关紧张。实时操纵系统有差别的调理算法，如抢占式优先级调理、周期性调理等，来确保任务的实时性。
    
  
  

   

活跃队列&过期队列

   

• PU调理时，必要把进程拿走的同时，把正在执行的进程剥离下来（被放入运行队列）
  
• 运行队列中存在两套相同的结构体范例。
  
• 拿走的队列：活跃队列。放入队列：过期队列。
  
• 活跃队列表示当前CPU正在执行的运行队列，而正在执行的运行队列（也就是活跃队列）是不可以增加新的进程的 。
  
• 与此同时，操纵系统设置了一个 和活跃队列相同属性的过期队列，当活跃队列正在执行时假如有进程必要添加进运行队列，那么就会添加至过期队列当中，也就是说 活跃队列的进程一直在减少，而过期队列中的进程一直在增多！
  
• 活跃队列是只出不进
  
• 过期队列是只进不出
  
• 两个队列是被存放在结构体数组中的，结构体数组存放在运行队列中
  
• 且运行队列中存在active指针和expired指针分别指向活跃队列和过期队列。
  

  活跃队列runqueue（也有叫停当队列）
  

• 时间片还没有竣事的全部进程都按照优先级放在该队列
  
• nr_active: 统共有多少个运行状态的进程
  
• queue[140]: 一个元素就是一个进程队列，相同优先级的进程按照FIFO规则进行列队调理,以是，数组下标就是优先级！
  
• 从该结构中，选择一个最符合的进程，过程是怎么的呢？
  
• 从0下表开始遍历queue[140]
  
• 找到第一个非空队列，该队列必定为优先级最高的队列
  
• 拿到选中队列的第一个进程，开始运行，调理完成！
  
• 遍历queue[140]时间复杂度是常数！但还是太低效了！
  
• bitmap[5]:一共140个优先级，一共140个进程队列，为了提高查找非空队列的效率，就可以用5*32个比特位表示队列是否为空，如许，便可以大大提高查找效率！
  

  过期队列wait queue
  

• 过期队列和活动队列结构一模一样
  
• 过期队列上放置的进程，都是时间片耗尽的进程
  
• 当活动队列上的进程都被处置处罚完毕之后，对过期队列的进程进行时间片重新计算
  

  全部进程的调理并不是我们想象的环境下的那样，实在操纵系统是维护了两个结构体队列，一个是用于维护当前正在大概将要立刻运行的等待队列，而另一个结构体就是为了维护已经被运行过后的队列大概活跃队列调理完后，才轮到过期队列。也就是说像我们日常在Windows下，我们在添加运行进程时，不是向活跃队列添加进程的，而是向过期队列中添加的，虽然我们日常使用时完全感受不到，但是这就是事实，这是因为操纵系统调理算法（如 CFS）和上下文切换的高效性使得进程切换非常敏捷，且调理的过程对用户透明。
  当活跃队列调理完，那么这时候操纵系统就会进行一系列操纵使得过期队列变为活跃队列，把活跃队列变为过期队列。
  

 bitmap[5]&O(1)调理算法

   我们说操纵系统是聪明的，假如前面大面积没有进程PCB存放，只有在后面才有进程PCB存放。那么CPU在调理进程时，必要遍历数组，才能找到存放进程PCB的位置。效率低且贫困。以是对于聪明的操纵系统就会想到了更好的办理方法，就设计出来了 bitmap[5] &O(1)调理算法。
  在设计上对于bitmap就是设计为了long
  

• long bitmap[5]，因为long为4字节，全部5个一共有8*4*5=160个bite位.
  
• 但是我们一个队列只有140个，以是使用位图bitmap绰绰有余，以是我们就使用位图的头脑，来表示这个位置的队列有无进程PCB。
  
• 0表示无，1表示有。
  
• 以是，CPU不必要遍历140的队列数组，只必要遍历bitmap的5个位置，遍历一次就查找了32个bite位，大大提高了效率！
  
• 时间复杂度位O(1)，以是O（1）调理算法！
  

  nr_active 

   在 Linux 中，nr_active 是一个变量，用于表示系统中 全部 CPU 焦点上活跃的进程数。它资助操纵系统相识系统负载，并进行 负载平衡，即在多核系统中，确保各个 CPU 焦点上的进程数量大致相同。
  与调理和负载平衡的关系
  

• 调理：nr_active 影响调理器选择哪个进程执行。
  
• 负载平衡：假如某个 CPU 焦点的 nr_active 很高，调理器会把一些进程迁徙到负载较低的焦点上。
  

   Windows 中的类比
  在 Windows 中，虽然没有直接的 nr_active，但 任务管理器 和 多核调理（如进程迁徙）也在执行类似的负载平衡工作，确保差别焦点之间的负载相对平衡。
  总结
  

• nr_active 是 Linux 用来管理进程负载和调理的工具。
  
• 在 Windows 中，多核调理和任务迁徙的机制类似，也有负载平衡的功能。
  

  active指针和expired指针

   刚才我们在说活跃队列与过期队列中也提及了一句对于二者进程的交换，那么实际上是怎样交换的呢？总不能说内容完全交换吧，那多么显得操纵系统多么笨啊。
  实在运行队列中存在active指针和expired指针分别指向活跃队列和过期队列。CPU调理时只找active指向的队列，也就是找到活跃队列，实在CPU是不可以通过调理内容来知道当前队列是活跃队列还是过期队列，他只人active指针，他指向谁，谁就是活跃队列。 
  在Linux内核中，特别是在进程调理和任务管理的上下文中，active指针和expired指针通常与运行队列（runqueue）干系。运行队列是内核用于管理和调理进程的数据结构。
  active指针：
  

• active指针通常指向当前活跃的任务或进程。活跃任务是指那些已经准备好运行但尚未被调理器选中的进程。这些进程通常位于CPU的运行队列中，等待调理器的调理。active指针资助内核快速定位并调理这些活跃进程。
  

  expired指针：
  

• expired指针则用于管理那些已经凌驾其运行时间限定或因为其他缘故起因而被标记为“过期”的进程。这些进程不再处于活跃状态，但仍旧必要被适本地处置处罚，例如大概必要被叫醒或重新调理。expired指针资助内核跟踪这些过期的进程，以便在必要时进行处置处罚。
  

  以是也就向我们刚才所说的
  

• active指针永久指向活动队列
  
• expired指针永久指向过期队列   

  ---

  
  

  以是调理过程中的一些小过程就可以用下面的总结出来
  

• CPU正在执行访问的队列是active指向的A活跃队列（只出不进）
  
• 另外一个被expired指向的结构相同的过期队列B（只进不出）
  
• 新创建的进程的PCB只链接到过期队列B
  
• CPU调理的活跃队列A中的进程PCB被CPU调理时间片到了之后，也链接到过期队列B
  
• 最后A队列中的进程被CPU全部调理完/处置处罚完，B队列也满满的
  
• 接着将两个active指针和expired指针交换swap(active，expired)，交换的是指针内容
  
• 重复上诉过程
  

  最后总结

假如上面的介绍有资助的话，还请点赞，假如有不明白的还请谅解。
最后推荐一篇文章Linux的进程优先级 NI 和 PR - 简书

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。