首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

linux的一个进程调度周期内新加入进程的处理机制分析

最近在研究Linux的短程调度(进程调度包括长程调度、中程调度和短程调度,详见参考博客1)相关的算法和调度器,由参考博客1可知,短程调度的主要任务是按照某种策略和算法将处理机分配给一个处于就绪状态的进程,分为抢占式和非抢占式。中程调度(又叫中级调度)的主要任务则是按照给定的原则和策略,将处于外存交换区中的就绪状态或等待状态的进程调入内存,或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。长程调度(又叫高级调度)的主要任务则是将已进入系统并处于后备状态的作业按某种算法选择一个或一批,为其建立进程,并进入主机,装入内存;当该作业执行完毕时,负责回收系统资源。如下图所示:

03

奈学:红黑树(RedBlackTree)的概述

AVL树是一种自平衡的二叉查找树,又称平衡二叉树。AVL用平衡因子判断是否平衡并通过旋转来实现平衡,它的平衡的要求是:所有节点的左右子树高度差不超过1。AVL树是一种高平衡度的二叉树,执行插入或者删除操作之后,只要不满足上面的平衡条件,就要通过旋转来保持平衡,而的由于旋转比较耗时,由此我们可以知道AVL树适合用于插入与删除次数比较少,但查找多的情况。   由于维护这种高度平衡所付出的代价可能比从中获得的效率收益还大,故而实际的应用不多,更多的地方是用追求局部而不是非常严格整体平衡的红黑树。   红黑树(Red Black Tree),它一种特殊的二叉查找树,是AVL树的特化变种,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 红黑树的平衡的要求是:从根到叶子的最长的路径不会比于最短的路径的长超过两倍。 因此,红黑树是一种弱平衡二叉树,在相同的节点情况下,AVL树的高度<=红黑树。   红黑树是用弱平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,降低了对旋转的要求,从而提高了性能,所以对于查询,插入,删除操作都较多的情况下,用红黑树。

00
领券