了解Linux调度程序
我是 Linux 内核和低级编程的新手。我想知道linux调度程序的时间复杂度应该是O(1)。
我发现了以下文章，内容非常丰富，但我在理解下面复制的段落时遇到问题 http://www.ibm.com/developerworks/linux/library/l-调度程序/
调度程序的工作很简单：选择最高层的任务 要执行的优先级列表。为了使这个过程更加高效， 位图用于定义任务何时位于给定优先级列表上。 因此，在大多数体系结构上，查找第一个位组指令是 用于查找 5 个 32 位字之一中设置的最高优先级位 （针对 140 个优先事项）。找到要执行的任务所需的时间 不取决于活动任务的数量，而是取决于活动任务的数量 优先事项。这使得 2.6 调度程序成为一个 O(1) 进程，因为 计划时间既是固定的又是确定的，无论 活动任务数。
为什么 140 个队列需要 5 个 32 位字？ find-first-bit-set 指令帮助谁选择 140 个队列中的一个？
I am new to linux kernel and low level programming. I wanted to know how linux scheduler is supposed to be O(1) in time complexity.
I came across the following article which is very informative but I have a problem understanding the pargraph I have reproduced below
http://www.ibm.com/developerworks/linux/library/l-scheduler/
The job of the scheduler is simple: choose the task on the highest
priority list to execute. To make this process more efficient, a
bitmap is used to define when tasks are on a given priority list.
Therefore, on most architectures, a find-first-bit-set instruction is
used to find the highest priority bit set in one of five 32-bit words
(for the 140 priorities). The time it takes to find a task to execute
depends not on the number of active tasks but instead on the number of
priorities. This makes the 2.6 scheduler an O(1) process because the
time to schedule is both fixed and deterministic regardless of the
number of active tasks.
Why 5 words of 32 bits for 140 queues ? Who the find-first-bit-set instruction helps to select one of the 140 queues ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
位字段使用单个值来表示多个布尔状态，例如，如果我们使用 8 位整数，那么我们可以这样说：
这表明第 4 个和第 8 个布尔值为 true，而所有其他布尔值均为 true错误的。由于有 8 个位，总共可以跟踪 8 个布尔状态。
由于我们希望跟踪 140 个状态（每个队列 1 个，true 表示队列包含任务），因此需要 140 位，因此 140 / 32 = 4.375，我们至少需要 5 个 32 位整数来存储所有布尔状态。
A bit field uses a single value to represent a number of boolean states, for example if we were using an 8 bit integer then we might say that:
Which would indicates that the 4th and 8th boolean values are true, where all other boolean values are false. In total 8 boolean states can be tracked as there are 8 bits.
As we wish to track 140 states (1 for each queue, true indicating that queue contains a task), 140 bits are required, and so as 140 / 32 = 4.375, we need at least 5 32 bit integers to store all boolean states.
像这样的东西：
用于通过优先级数组到达特定进程，这就是在调度程序中使用位图的方式，而调度程序又取决于 struct prio_array
您指出的文章已过时，请检查这篇文章
http://www.informit.com/articles/article.aspx ?p=101760&seqNum=2
Something like this:
is used to reach the particular process with priority array and this is how bitmaps are used in scheduler which in turns depends upon struct prio_array
The article you pointed out is outdated check this one
http://www.informit.com/articles/article.aspx?p=101760&seqNum=2