各位好，QNX可以动态限制进程对CPU的使用，也就是当系统中有多个可运行进程时可限制某进程占用一部分CPU时间，当系统中只有一个进程时，允许这个进程占用所有的CPU时间，请问QNX是怎样实现的呢？有这方面的文档吗？谢谢了
这个东西叫"自适应型分区调度“(Adaptive Partioning Scheduling)。可以去GOOGLE一下（Adaptive Partion, QNX)。也可以试试下面的连接。
非常感谢唐老师。我这就去看看，等有了结果，我再发过来
这是QNX的分区技术，原理倒也不复杂。需要有Budget的概念。
首先系统会计算进程使用的CPU时间（如果计算文档有详细说明）。然后根据它们的Budget（预算）来决定何时降低他们的优先级。
这样一来，你的Budget用完了，优先级就会降低，过一段时间你又有了新的Budget，你的优先级会恢复。通过这样的调整，互相制衡，确保各分区能拿到和指定Budget一样的CPU分配结果。如果系统空闲，那优先级就算低了，也可以拿到CPU来使用，所以又不会浪费CPU.
系统按分区的Budget,然后分区里又按线程优先级，来进行线程调度。比普通的实时操作系统多了一层，从而让系统设计更容易。
谢谢楼上的nakeyfish。我看了下http://community.qnx.com/sf/wiki/do/viewPage/projects.core_os/wiki/APS_How_it_Works_FAQ，还没看大明白。
“系统按分区的Budget,然后分区里又按线程优先级，来进行线程调度。”
这句话的意思是否是系统先按分区剩余的Budget大小来选择分区，再在分区里面选择优先级最高的进程运行呢？但是为什么不是先按分区里优先级高的进程来选择分区，再判断这个分区是否有剩余的Budget呢？因为有可能即使剩余Budget很小，但进程优先级仍然很高的情况吧。
文档中好象都没有谈到多处理器的情况，因为这种情况应该更复杂吧，所以我主要是想看看在多处理器系统中APS是怎样运行的，能指点下吗？
还有Linux2.6.28中使用的分区调度技术，根据源代码来看是没有根据budget来动态改变进程优先级的。而所有分区时间用完的时候，如果还没到指定的period，则会选择idle进程运行，而不是分配给需要运行但是没有时间的进程，所以CPU资源有所浪费，不知道这是不是qnx文档中所说的静态分区。我也没找到技术文档，只是从Linux源代码中看来的，也不知道是不是这样？
同样也没看到多处理器系统中是怎样处理的，因为不可能这么简单，呵呵。
不好意思，再请教一个问题
文档中说APS的调度算法在libmod中，我想问问是在哪个lib中呢？我通过在源代码中查找SCHEDULER_TYPE_APS都没找到
惨愧，我下了源码却很少看。一般只看文档。所以只能谈一下我的理解。还需要你去求证。
“但是为什么不是先按分区里优先级高的进程来选择分区，再判断这个分区是否有剩余的Budget呢？因为有可能即使剩余Budget很小，但进程优先级仍然很高的情况吧。 ”
这个问题，我想讲讲QNX的调度方法你就明白了。为什么是这样而不那样。
QNX的调度通过一个READY Queue。按优先级分为256个Queue，每个Queue排列着某优先级的线程（如优先级10的线程为一队）。系统调度时从高往低，再从左到右，找第一个可用的线程来进行调度。这样即保证优先级，也保证同一优先级的时间片调度等。因为新加进来的线程会被加在Queue后面，相当于重新排队。
现在再考虑AP技术，怎么才能和之前的调度方式结合在一起，不需要大动干戈呢，自然是通过优先级的转换，使之很自然的融合在一起。系统调度还是按原来的样子，找到第一个适合的线程就好了。AP要做的就是如何在Queue里加减线程。
好。下面再看多处理器的情况。其实再容易不过了。多处理器所增加的工作，只不过是把找出来的线程放到适当空闲的核上运行罢了。所以QNX对多核的支持，香港回归的时候就开始了。
写完直流汗，应该都没有好好看文档呢。XTANG，AP是这样子工作的吗？
呵呵，你讲的QNX调度算法和Linux2.6中是一致的。
我现在理解“系统按分区的Budget,然后分区里又按线程优先级，来进行线程调度。”这句话的意思了，因为我先前分析了linux2.6.28里面的这AP技术，调度时有个进程分组的概念，所以理解你这句话时自然而然就加上了分组，所以我才有了选择哪个分区的概念，呵呵，真是不好意思。
刚才听老大说以前qnx的内核只运行在一个CPU上，其他CPU都只运行应用程序，不知道现在的情况是怎样的？如果是这样那qnx和linux相比，可能更容易解决CPU之间平衡问题。
我不知道在QNX中是怎样在CPU之间平衡线程的。因为Linux2.6.28中的AP应用于实时进程，而不用于普通进程，且实时进程不在CPU之间移动。但我现在要将此技术应用于所有进程，所以AP技术则线程平衡技术还需要调整，因为有平衡操作时机和进程可用时间之间还有微妙的关系，如果把握不好，则会因为AP的引入，平衡操作就会降低系统性能。呵呵，我再看看了，
以前qnx的内核只运行在一个CPU上？
没有听说过这样的事情。正确来说，QNX内核只是一个库，没有线程，也不会运行，只会被调用。一般意义上的QNX的内核是指进程管理器（procnto＝kenel(lib)+process manager）.微内核架构看来，所以的进程都在核外，都是一样的，无所谓内核线程或客户线程，process manager也不例外。所以正确的说法是，QNX的任何线程可运行在任何一个CPU或核上。也正是由于架构的关系，QNX很容易实现对多核的支持。某个CPU核调用了内核，它就会先做调度检查，再决定是否要调度。多核调度变成了很简单的自然的事情。
你说的如何在CPU间平衡线程的问题，不知我理解的对不对，在QNX下很简单呀：内核运行时（或讲被调用，在某一CPU上），会从Ready Queue里找出适当的线程，把它换上来运行就是了。单核，多核都是一样，原理上没什么特别的。
感觉你是要在Linux上写一个类似于QNX APS的东西。架构不一样，不知道参考QNX是否可行。我觉得FAQ里有许多东西讲得挺细的。里面有许多细节上的考虑。可供你参考。更详细的技术可能要问XTANG了。
AP的问题，我看了下文档（FAQ），还是有许多不明白的地方：
1.先选分区，分区里再根据优先级进行调度。
How does the scheduling algorithm work?
The thread scheduler evaluates a merit function on each partition and chooses the partition with the highest merit. It then picks the highest-priority thread in that partition. A partition with budget has more merit than a partition that has exhausted its budget.
但是系统只有一个Ready Queue，还是每个分区维护一个Ready Queue呢？还没找到确切的答案。
非常感谢nakeyfish，从你的讲解中我了解了qnx的许多基本知识和整体架构，就是因为要在Linux上实现CPU资源的动态控制，也就是类似于qnx的AP调度，所以参考下qnx的算法，有很多qnx的东西都不知道，见笑了。
根据你的描述，我的理解是qnx在多处理系统中和单处理器系统中都只维护一个调度队列，每个CPU都从这个队列中选择可运行线程进行运行。如果是这样，那么也就没有CPU之间平衡的问题了。
在多处理架构的Linux中，因为每个CPU都维护自身的一个调度队列，所以有可能出现某个CPU上有很多可运行进程，但是另外的CPU却为idle状态，所以会存在CPU资源的浪费，那么就需要在CPU之间平衡可运行的进程了，也就是从忙的CPU中迁移一个可运行进程到空闲CPU中。看来qnx和Linux还是大大的不同啊。
FAQ里面的东西也看了一遍，现在来说对我还太细节了，文档<<AP_June2006_videtalk4_v2>>是其原理的东西，先前看了一遍，居然没意识到，呵呵。现在正在看。
不知道你的How does the scheduling algorithm work?在哪个FAQ中，能给个地址吗？我看的FAQ中还没有这个问题的解释呢。
从这里的解释来看，实现和Linux也大体相似，就是将进程分区（Linux中是将进程分组，和分区是同样的意思了）。Linux中是在分组之间选择有最高优先级进程且有可运行时间（budget)的组，再在此组内选择进程调度，但是我没有看到根据budget改变进程优先级的操作，这也许是两者之间的差别吧。
热切希望XTANG出来指点迷津！
从你对Linux的描述我也学到很多呀。以后有Linux的问题还需要向你请教。
就在你给出的URL里呀，这个也许更清晰：http://www.qnx.com/developers/docs/6.4.0/adaptive_partitioning_en/user_guide/faq_ap.html#SCH_AGRHM
根据budget改变进程优先级的操作,也许是我杜撰出来的。因为之前XTANG之前有提到过，AP使用的是QNX的SCHED_SPORADIC调度方式。而SCHED_SPORADIC是那样的工作原理。
还是请XTANG来指点一二吧！
关于APS算法的代码在/services/system/ker/aps目录中，http://community.qnx.com/sf/wiki/do/viewPage/projects.core_os/wiki/APS_source上有介绍，但是还没有时间看。
qnx文档中还有窗口的概念呢，不知道究竟是怎么回事，还需要再看看了。
Wow，前两天刚想写几句，一耽误就来去这许多帖子了。
这里“进程调度”， ”多核进程调度“，和”AP“几件事都搞到一起来了。先分开来说说。
QNX的进程调度，跟nakeyfish描述的那样，基本上就是一个从高优先级往下找的READY队列阵。因为优先级个数是一定的，所以扫描的时间也是可确定的，所以调度时间不会随线程个数的多少而变化。
在QNX的进程调度里，一般不会随意修改线程优先级（随消息传递而带来的优先级变化不算），像nakeyfish所描述的“线程占用CPU时间太长就把它优先级下降”的做法，是传统的Desktop的调度，不会在QNX里出现。唯一例外的是如果你的线程指定了Spradic调度算法。（SCHED_SPORADIC）
“多核”的进程调度，跟单核一样，也是单一队列。就好象nakeyfish讲的，内核其实可以想像是一个库，它自己是浍自动“运行”的。要么是硬件有中断，要么是用户程序进行kernel call，才会进入到内核。如果用户线程是在CPU X上运行，那么内核调用后也会在CPU X上运行内核，调度也在X上进行。
QNX之所以没有一个CPU一个调度队列。主要是因为QNX保证在同一时间，只有一个CPU在内核里面。当然，如果多个CPU大家都要进内核会造成等待或是抢占；但QNX的好处是“微内核”，系统大量的时间应该是花在核外的，即使是进行内核调用，也应该是很快就出内核的（没有在内核内部因IO而要阻塞这样的事）。所以“微内核”在这方面占了简单易处理的好处。
因为所有的线程都可以在所有的CPU上运行，“CPU间的平衡”也是自然形成的。
当然，QNX的多核调度算法也有一定的考量。比如，理论上一个线程上一次在CPU X上运行，下一次也在 CPU X上运行，对CPU Cache有好处，这是多核调度时QNX的调度算法会考量的一点。另一个是因为QNX是一个消息传递系统，也就是说，客户端“发送”以后一定会被阻塞，那时，把接收这批数据的服务器端调度到同一CPU，就更能有效地使用CPU Cache（发送数据很可能已经在Cache里了）。
这些小情况，加上可能的用户强行指定CPU的时候，（在QNX上叫BMP，Bounded Multiprocessing，在Linux上好象叫CPU Affarinity吧)。多核调度算法都要综合考虑，再做出判断。
最后讲讲AP。首先一个是，AP并不会根据Budget来改变线程优先级。（我有说过AP是用SPORADIC吗？如果有，那是不对的。）
基本上AP是逻辑上分区，把不同的线程分在不同的分区里，每个分区都有预算。同一个分区里，按标准的调度算法调度。每个线程所花的时间，按micro second数，加到分区所耗的时间上。(micro second billing)
调度时找没有超预算的分区里的最高优先级线程，直接调度它。如果所有分区都不超预算的话，这个就跟一般的实时调度没什么区别（最高优先级线程得到CPU）。
到这里，应该是跟Linux的很相近的。
Qnx的分区前有个 Adaptive (自适应性），这个可能跟别的系统不同。假设一个系统有三个分区，分别为A%30, B%30, C%40，现在%40的C分区里有线程要运行，如果这个分区没有预算的话，传统的做法是放弃这个线程，另找别的分区里的线程。
但是，如果A和B分区里的线程都被阻塞，没有线程可以运行，那时候会怎样呢？
QNX的做法是，把A和B的预算，临时送给C，让C里的线程可以“超预算”运行。这样，如果A/B里没有线程可运行的话，C可以占用100%的CPU。当然，如果A/B里突然有线程需要运行了，哪怕它优先级再低，C里的线程也要为它让路。
其它还有一些比较细小的东西，比如“重要线程”的概念，“借”“还”预算的概念，但总的来说，这个“自适应性”，是QNX比较独特的东西。
“到这里，应该是跟Linux的很相近的。”，前面这部分确实是和Linux一致的。但是后面部分有所不同，因为Linux中一个CPU一个运行队列，所以一个进程组在每个CPU的运行队列上都有其组管理结构，当一个分区没有运算时，是向属于同组的其他CPU借取时间，而不是qnx中的向同一CPU上的其他组借取时间，所以在同一个CPU上好像存在CPU浪费的现象，Linux也应该借鉴下同CPU时间的方法。我也只是从源码中看来的，但是自带的文档中说的是可以动态利用CPU的。
对不起，不当心按错键了，改动了你的原帖。
那么Linux在生成“分区”时，还要为分区指定CPU吗？（除了预算以外）
这个实际上涉及到另一个较复杂的问题。我们上面提到的AP的工作原理，是按单CPU来解释的，在多CPU上的AP是怎样的呢？如果有4个CPU，是不是我的预算就是400%呢？
答案是“不是的”。不管有几个CPU，QNX的调度分区的预算总和应该总是100%。如果想像预算就是“占用多少运算资源”，那么不管几个CPU，运算资源总是100%，具体在哪个CPU上运算没有什么区别。
如果系统里所有的线程可以在任意的CPU上迁移，那么这个结果也是容易理解的。你只要想像4个物理CPU是“1个逻辑CPU”就可以了。
如果有线程衩限定，比如有分区A，里面有一个线程被绑定的CPU0上，那这个分区的理论预算就是25%了，即使给它30%它也永运不会达到那么多的。
谢谢，qnx中的方法我大体也知道了，这两天暂时忙其他事情了，还没看分区时间的"借"和"还"究竟是怎样进行的，大体知道是根据过去一段时间内的使用情况来决定当前窗口中分配多少CPU时间给分区。能不能请XTANG讲下这个呢？
Linux在生成分区时，可以为分区指定多个CPU。Linux对CPU访问控制和qnx有所不同，qnx是直接指定百分比吧，也就是一个选项;Linux是要指定两个选项：一个周期period和一个周期内可运行时间run_time，run_time/period就是分区可占用的CPU百分比。如果系统有多个CPU，每个属于分区的CPU都预留了run_time这么多时间给分区，如果分区在一个CPU上的run_time变为0了，可以从另一个CPU上借取，所以分区的可运行时间在单个CPU可能表现为大于run_time，小于period，也就是可能会在百分百占用某个CPU，但是因为被借取的CPU的时间减少，所以在其他CPU上占用的百分比就会减少，那么分区在整个系统中CPU的占用百分比还是run_time/period.
总的来说，假设系统有4个CPU，指定分区在4秒内可运行时间为1秒，那么分区总的运行时间就是4*1=4秒，有可能会占用单个CPU百分百的时间。
呵呵，qnx和Linux相比，因为架构的不同，所以Linux相对复杂点