网站建设投标文件,c2c的网站,seo搜索引擎优化方案怎么写,非常好的资讯网站设计理解linux 当中如何做到 把一个PCB 放到多个 数据结构当中
在Linux 当中#xff0c;一个进程的 PCB 不会仅仅值存在一个 数据结构当中#xff0c;他既可以在 某一个队列当中#xff0c;又可以在 一个 多叉树当中。
队列比如 cpu 的 运行队列#xff0c;键盘的阻塞队列等等…理解linux 当中如何做到 把一个PCB 放到多个 数据结构当中
在Linux 当中一个进程的 PCB 不会仅仅值存在一个 数据结构当中他既可以在 某一个队列当中又可以在 一个 多叉树当中。
队列比如 cpu 的 运行队列键盘的阻塞队列等等的双线链表当中。
而多叉树就本篇博客需要阐述的 进程优先级了。
如何实现的其实也很简单就是在一个 PCB 结构体对象当中不仅仅只有 双链表的 prev 前序结点指针和 next 后继结点指针还有 多叉树当中的 比如 parent 父亲结点指针和各个孩子的指针。这时因为链式的数据结构管理各个 进程的 PCB 结构体对象也是通过这个结构体对象的 指针来实现管理的。所以我们才说一个结点就可以插入到 一个双向链表当中又可以插入到 一个多叉树当中。
下面简单实现一个 PCB 结构体的 demo来理解 如上所示通过在 PCB 结构体当中内嵌一个 双链表结点的结构体来维持 这个PCB在某一个 双链队列当中的存储位置。
这样就可以通过一个 PCB 来找到这个 PCB 所在队列的所以的PCB 了也就相当于是把 这个PCB链接到某一个队列当中了。
但是这样的话有一个问题就是我可以找到 存在与 各个 PCB 对象当中的 link 结构体对象在各个 PCB 当中存储的位置但是如果我们想要访问整个 PCB对象的话需要拿到 PCB 对象的地址存储 PCB 对象起始位置的 PCB类型的结构体指针。
所以结合上述 demo我们用以下方式来 计算出 link 和 link所在PCB对象当中的 地址偏移量然后 得到 PCB 对象的起始地址
(task_struct*)((char*)head - (char*)(task_struct*)0-link) - other
上述代码就可以拿到 PCB 的起始地址然后访问 PCB 当中的 其他 other属性。
怎么做到的呢我们来一步一步看 (上述的 head 和 (task_struct*)0-link 要强转成 char* 类似的以为此时是以 数字的方式来看待的而不是指针我们是为了计算出偏移量。但是上述为了图片的 宽度没有写上。)画个图来 理解 利用 0 开始 的 PCB 结构体指针计算出 link 距离 PCB 起始位置的 偏移量相对距离。 像上述是一个PCB 的访问方式当然一个队列当中会有很多个不同种类的 PCB 对象那么其中的 link 所在位置也是不一样的但是都可以同种上述的方式来计算出当前PCB当中 link 相对于 PCB 起始位置的偏移量。 进程的优先级
因为资源是有限的进程有很多个所以注定了进程之间是竞争关系。
操作系统必须要保证 各个进程之间必须要 良性竞争。 所以制定了优先级对于各个进程之间对于资源的访问谁先谁后由进程各自的优先级决定。
cpu资源分配的先后顺序就是指进程的优先权priority。
优先权高的进程有优先执行权利。配置进程优先权对多任务环境的linux很有用可能改善系统性能。 还可以把进程运行到指定的CPU上这样一来把不重要的进程安排到某个CPU可以大大改善系统整体性能。
如果因为调度算法不合理优先级设定算法不合理就会导致某些进程长时间得不到CPU资源某些进程的代码长时间得不到推进。造成了该进程的饥饿问题。 这种饥饿问题在用户体验上看来就是某个进程卡死了得不到响应。就像在 windows 当中可能遇到过其他进程都没事但是某一个进程卡死了提示无法响应此时你会有两个选项结束进程或者是再等等。 我们可以使用 ps -l 查看当前终端下用户启动的 进程但是这个命令不能查看单独由其他终端启动的进程。如果想查看的话可以再多加一个 -a 选项来查看用户启动的全部进程 UID 的解释因为计算机只认识数字所以区分各个 用户也是使用数字来区分的UID 就是各个用户独有的ID就像身份证号一样在这个操作系统当中一个用户的这一个 ID 是独有的。 PRI也还是比较好理解的即进程的优先级或者通俗点说就是程序被CPU执行的先后顺序此值越小进程的优先级别越高。 NI 的解释因为 操作系统当中的调度器要更具当前操作系统的需求或者是用户的需求要给根据算法来修改某一个进程的 优先级但是原来的优先级是 调度器计算出来非常合理的优先级也就是 PRI 是刚开始计算出来最合理的优先级所以这个 PRI 优先级是要保存的所以如果调度器要修改优先级的话修改的不是 PRI而是使用 PRI(new)PRI(old)nice 。从而使用 PRInew作为现在 进程所使用的优先级。当 此时 操作系统和用户没有再需求之后就会使用 原本的 PRI 优先级。
虽然都是按照 PRI(new)PRI(old)nice 这个公式来进行修改的但是 PRIold是不变的默认一直都是 80 。
这样当nice值为负值的时候那么该程序将会优先级值将变小即其优先级会变高则其越快被执行所以调整进程优先级。
需要强调一点的是进程的nice值不是进程的优先级他们不是一个概念但是进程nice值会影响到进程的优先级变化。
那么既然优先级可以被调整那么是不是就以为这个我们可以把一个 进程的nice 值调的非常的低使得这个进程优先级很高一直被调度答案是不行的。
Linux不想过多的让用户参与到 优先级的调整当中只能在对应的范围之内膝盖 nice 值。超过范围只能给范围的极值作为值返回不能超过极值。
在Linux下就是调整进程nice值nice其取值范围是-20至19一共40个级别。 利用 top 修改nice的同时修改 进程的 PRInew top 是任务管理器当我们在 top 窗口当中按下 r 键就可以执行 renice 命令 此时它提示我们输入 某个进程 的PID我们就输入 我们自己写的 死循环进程的PID 回车之后就会提示我们要修改的nice值为多少我们就可以再 上述所说的 nice 的区间当中给值就算是 超出了也就给出对应分为的极值。比如我们现在给出 100 回车之后就会修改 nice 值 因为 nice 最大就是 19所以此时就是修改到了 99。 Linux当中 cpu 当中调度不同优先级的做法 在 cpu 当中有一个运行队列这些队列当中的使用指针的方式排列着 处于运行状态的 进程的PCB指针。但是这些进程的 优先级有大有小cpu 是如何调度其中的 进程的呢
其实在这个运行队列当中会存储两个 存储 PCB指针的 指针数组这个两个数组一般的大小是 140 个元素前 0-99 个元素存储的是其他进程的 task_struct指针在后面的 [100 - 139 这个刚好 40 个元素 的指针就是存储的是 我们可以修改的 nice 指针的数目。
我们用这 40 个元素做例子
我们可以修改到的 优先级范围就在 [60 , 99) 这个区间当中这个区间就刚好映射到了 [100, 139 ) 这个指针数组的下标。那么我们就可以根据优先级映射到 这个指针数组下标。类似这样的结构如下图所示 利用这种 类似于 开散列式的哈希表来 实现这种结构非常像 哈希桶。
cpu只需要在左边的指针数组当中 按照下标来一个调用有这个 task_struct * 指向的单链表来依次调用其中的 进程。
如果后续需要添加进程只需要按照 这个进程的 优先级插入到对应的 指针数组 元素指向的 单链表尾插即可。 上述描述的是running 这个指针数组当 运行队列当中只有 running 这个指针数组之时那么就是按照上述的方式进行操作的。
但是在LInux 当中还有一个 waiting 指针数组在上述我们说过在后序插入的 进程是直接在 running 维护的对应的单链表当中尾插的。但是现在有了 waiting指针数组就不在 running 当中插入了直接在 waiting 指针数组当中插入即可。这个 waiting 指针数组的存储结构 和 running 是一样的。
而且不仅仅有上述两个 指针数组还有两个 二级指针指向这个两个数组。实际上cpu 不是按照 running数组的首元素地址开始执行程序而是按照 这个 指向 running数组的 二级指针来执行进程。当 running 当中的进程执行完之后只需要 交换 指向 running数组 和 waiting数组 两个数组的 两个二级指针指向即可。就是把 两个二级指针指向的内存做交换。 向上述所举的例子run 这个二级指针一定指向的是 正在执行的队列而 wait 二级指针指向的是 还没有新插入的正在等待的队列。 但是现在还有一问题怎么知道 run 指向的队列已经执行完了呢
就只能取遍历这个指针数组各个指针元素是否指向空。 但是这种方式有点满所以我们使用 位图 来映射 这个队列的每一个位置是否为空。使用 位图就可以 实现近乎 O1的时间复杂度来找到 从当前查找位置开始最近一个 不为空的 单链表位置。
具体位图可以看一下博客介绍
C - 位图 - bitset 容器介绍_chihiro1122的博客-CSDN博客 这种使用位图来实现查找 最近的 队列不为空的算法被称之为 --- Linux 内核 当中的 O1调度算法。
总结
我们所看到的 各种外设硬件设备进程试图访问或者使用这些外设之时都是要在各种队列当中进行排队的。因为 这些外设硬件设备是少量的而进程动不动就几百个是很多的这也就导致了 进程之间要竞争要排队。
所以操作系统为了能更好的管理 进程 之间的运行就引入了优先级让进程之间合理竞争相关资源。因为 各个资源是不能做到并发执行的但是因为 cpu 计算速度很快可以用一些调度算法结合优先级做到 用户看上去是很多进程在同时运行一样。
各种资源在各个进程使用期间是 独享的并不是多个进程占用同一资源。在多进程运行期间互不干扰。进程在设计理念之上就是 在自己运行之上不能影响到 其他进程的运行这样是进程的独立性。
如果在不考虑多核cpu的情况下多个进程在多个CPU下分别同时进行运行这称之为并行 这个称之为并行。
同时如果此时只有一个 cpu 在一段时间之内很多个进程都得到的执行或者实现完毕这个过程称之为并发。
当然为了防止某一个进程一直占用cpu所以一个进程还有一个时间片的概念只允许一个进程在规定的时间之内占用时间片。
如果一个进程的时间片到了那么这个进程就会排到下一个 等待队列当中等到cpu处理下一轮的 进程队列。
这也是 Linux 在处理进程队列这件事情之上的 优雅处理。使得后序链入的进程只能在当前cpu正在执行 的运行队列当中的进程全部执行完才会执行下一个队列当中的进程而在cpu 处理当前队列的 进程之时在此期间链接上来的 进程只能链接到 等待队列当中。
