Windows抢占式多任务是如何实现的？

http://msdn.microsoft.com/en-us/magazine/jj553509.aspx
介绍的不错，还有代码。

全英文
这个是介绍协作式多任务吧
是早期windows采用的方式

2、经常看时钟周期这么一个概念，做某种运算要4个时钟周期，
// 时钟周期就是 2个时钟间的时间，其倒数为时钟频率。
// 时钟周期是节拍时间一条指令可能要一个以上节拍。
时钟周期是cpu晶体的物理特性？
// 通常CPU 不包含晶体。时钟周期是晶体振荡器产生的
还是时钟芯片发出高低电平的频率？
// 时钟芯片可能会是实时时钟那是用来记年月日的。
是否时钟芯片控制整个cpu高低电平变化的频率？
// 由晶振产生高低电平的脉冲，
有看到某些运算只要时钟周期的上升阶段就完成了，
// 如何使用高低电平的脉冲是芯片的自由
那似乎说cpu运算不完全受时钟控制。
// 一条指令可能要一个以上节拍（时钟脉冲）
但IO操作时，必须要时钟控制，与外设协调？
// IO 操作是 CPU 的指令，同样可能要一个以上节拍

调度器的时间片楼主理解这个了么？就算你有死循环，别人也要继续干活的，只不过调度器对于死循环分配的时间片可能会多点。那么他占用的CPU的时间就更长。

时间片，我看过操作系统，我的疑问是：任务运行中控制权如何回到调度器。一个任务在执行中，调度器并没工作，如果判断时间片到时，并把cpu交给调度器？根据 7 楼 VisualEleven 的回复中的文字，就像调试过程中编译器插入一个int3，操作系统预先插入一条指令。这在大多数情况下是可以的，但于遇到该指令前正好有一个循环，就无法到达该指令，控制权就不可能回到调度器。

谢谢！我搜了一下晶振：每个单片机系统里都有晶振，全程是叫晶体震荡器，在单片机系统里晶振的作用非常大，他结合单片机内部的电路，产生单片机所必须的时钟频率，单片机的一切指令的执行都是建立在这个基础上的，晶振的提供的时钟频率越高，那单片机的运行速度也就越快。那就是说，计算机中晶振是由晶体震荡器产生的，与时间芯片是两码事。1、时间芯片通过对晶振计数，获得时间。2、晶振产生高低电平，影响cpu工作。那么晶振与时钟周期是不是一个概念，还是若干个晶振形成一个时钟周期？

指令遇到循环，我觉得这个Microsoft都不会允许。你这个是强盗逻辑。你等于把操作系统故意弄死。

指令遇到循环，是再普通不过的情形。下面一个链接说linux中，抢占式是用中断实现的，但解释的不够清楚。
http://bbs.csdn.net/topics/10023953
抢占式内核靠系统时钟控制任务，每隔一定时间就按照任务切换策略执行任务切换，非抢占式的则靠每个任务内部消息处理或其他方式进行调度，在该任务的处理没结束之前不会切换到另一个任务。

http://blog.csdn.net/kanghua/article/details/1684009
实时和Linux之二：抢占式内核抢占点的核心思想是在特定点上调用调度程序去检查是否有更高优级的任务做好了运行准备，需要即刻运行。Molnar和Morton就是利用该思想，测量内核路径的执行时间，找到时间过长的路径插入调度检查点（等于打断了长路径）。你可以通过抢占补丁代码或是对比打过补丁的内核和先前未达补丁的内核，从中发现那些地方需要插入抢占点。抢占补丁看起来很象if (current ->need_resched) schedule()（这是用户空间抢占执行的典型情形）;
说得比较复杂，似乎是有一个“插入调度检查点”的问题。
http://bbs.chinaunix.net/thread-2002749-1-1.html
单cpu抢占模式下，spin_lock定义是禁止抢占。应该是说unix的情形。一下子理解不了。
下面文字的原链接失效，是百度快照，但说的不是很明白，好像还是用“中断”方式实现的。关于如何实现抢占式

作者：61IC录入    文章来源：本站原创    点击数：    更新时间：2006-4-7
我以前是这样实现的：用自己的外壳程序接管每一个中断，将进中断后保存的现场和系统dispatch所要保存的现场设计成基本一样。进中断后置上一个标志，中断服务程序可以进行wakeup调用，在wakeup程序中，如果唤醒了更高优先级的任务，需要检查当前是否在ISR中，如果不是，则转入正常调度，如果有“中断正在执行”标志，则不立即进行调度，而是置上“延迟调度”的标志，在中断返回前的“外壳程序”中检查“延迟调度”标志决定是返回原来被中断的任务还是进行重新调度。用伪码说明如下。ISR_Shell:
    保存现场;
    Int_Flag=1;
    执行用户ISR;
    if (Dispatch_Flag)
        goto Dispatch;
    Int_Flag=0;
    恢复现场;
    中断返回;Dispatch:
    if (!Int_Flag)
        保存现场;
    Int_Flag=0;
    找出最高优先级任务;
    切换堆栈指针;
    Dispatch_Flag=0;
    恢复现场;
    返回到最高优先级任务;Wakeup:
    将待唤醒的任务置入Ready队列;
    if (唤醒的是最高优先级任务)
    {
        if (Int_Flag)
            Dispatch_Flag=1;
        else
            goto Dispatch;
    }至于要实现函数可重入，只要将所有现场都保存就可以了（因为C语言函数天然可重入）。比如老版本的ethernut用嵌入汇编实现的：
void NutThreadSwitch(void)
{
    /*
     * Save all CPU registers.
     */
    asm volatile ("push r0" "\n\t"
                  "push r1" "\n\t"
                  "push r2" "\n\t"
                  "push r3" "\n\t"
                  "push r4" "\n\t"
                  "push r5" "\n\t"
                  "push r6" "\n\t"
                  "push r7" "\n\t"
                  "push r8" "\n\t"
                  "push r9" "\n\t"
                  "push r10" "\n\t"
                  "push r11" "\n\t"
                  "push r12" "\n\t"
                  "push r13" "\n\t"
                  "push r14" "\n\t"
                  "push r15" "\n\t"
                  "push r16" "\n\t"
                  "push r17" "\n\t"
                  "push r18" "\n\t"
                  "push r19" "\n\t"
                  "push r20" "\n\t"
                  "push r21" "\n\t"
                  "push r22" "\n\t"
                  "push r23" "\n\t"
                  "push r24" "\n\t"
                  "push r25" "\n\t"
                  "push r26" "\n\t"
                  "push r27" "\n\t"
                  "push r28" "\n\t"
                  "push r29" "\n\t"
                  "push r30" "\n\t"
                  "push r31" "\n\t"
                  "in %A0, %1" "\n\t"
                  "in %B0, %2" "\n\t":"=r" (runningThread->td_sp)
                  :"I" _SFR_IO_ADDR(SPL), "I" _SFR_IO_ADDR(SPH)
        );    /*
     * This defines a global label, which may be called
     * as an entry point into this function.
     */
    asm volatile (".global thread_start\n" "thread_start:\n\t"::);    /*
     * Reload CPU registers from the thread in front
     * of the run queue.
     */
    runningThread = runQueue;
    runningThread->td_state = TDS_RUNNING;
    asm volatile ("out %1, %A0" "\n\t"
                  "out %2, %B0" "\n\t"
                  "pop r31" "\n\t"
                  "pop r30" "\n\t"
                  "pop r29" "\n\t"
                  "pop r28" "\n\t"
                  "pop r27" "\n\t"
                  "pop r26" "\n\t"
                  "pop r25" "\n\t"
                  "pop r24" "\n\t"
                  "pop r23" "\n\t"
                  "pop r22" "\n\t"
                  "pop r21" "\n\t"
                  "pop r20" "\n\t"
                  "pop r19" "\n\t"
                  "pop r18" "\n\t"
                  "pop r17" "\n\t"
                  "pop r16" "\n\t"
                  "pop r15" "\n\t"
                  "pop r14" "\n\t"
                  "pop r13" "\n\t"
                  "pop r12" "\n\t"
                  "pop r11" "\n\t"
                  "pop r10" "\n\t"
                  "pop r9" "\n\t"
                  "pop r8" "\n\t"
                  "pop r7" "\n\t"
                  "pop r6" "\n\t"
                  "pop r5" "\n\t"
                  "pop r4" "\n\t"
                  "pop r3" "\n\t"
                  "pop r2" "\n\t"
                  "pop r1" "\n\t"
                  "pop r0" "\n\t"::"r" (runningThread->td_sp),
                  "I" _SFR_IO_ADDR(SPL), "I" _SFR_IO_ADDR(SPH)
        );
}至于比较协作式和抢占式两种类型的RTOS，其实是各有优缺点的。很多人只看到了抢占式的实时性强的优点，却没有看到它有3个缺点：1、任务间公用的数据结构必需考虑完整性问题；2、增加的任务切换频率实际上加大了内务开销，降低了总体的CPU利用率；3、导致内核实现困难，代码增多。而协作式的RTOS，任务间公用的数据结构很容易保证其完整性（因为任务切换的位置是已知的），至于其实时性差的缺点，其实是很容易克服的，即，只要在执行时间长的任务中间人为增加一些taskdelay(0)进行系统调度检查即可。实际上，对大多数的任务而言，执行时间不会超过几毫秒，这一点延时完全能够满足要求的（更急迫的工作当然可以用中断或者硬件来做）。

80386保护模式我此前已经看过。从实模式启动到进入保护模式，以及在任务之间通过门/中断进行切换。如果不考虑时间片，直到一个任务运行到某一个指令点，通过门/中断转移控制，那好办。我现在关心的是单cpu单core情况下，要考虑时间片限制的情况下，Windows正在执行一个任务中，控制权采用什么方式从该任务转移到调度器？因为此时调度器作为一个进程程，不在运行中，可以说处于内存中，本身没有取得控制权。一种可能是采用时钟中断。第二中可能是：操作系统在任务的代码的某个位置插入转移指令，把控制权转移到调度器，但这种方式，如果在插入的转移指令的前面遇到循环，则无法到达插入的转移指令，控制权就无法及时转移到调度器，那么就更加无法转移到其它任务。我希望看到明确的Windows方面的资料。

1、触发任务调度的路径有2：
1）中断(各种中断都会把cpu交还给操作系统)
2）系统调用(sleep, waitfor...object, select, querycompeletestatus, .....)2、时钟周期=当前cpu主频取倒数

太好了。时钟周期=当前cpu主频取倒数。

基于优先级的时间片轮转算法，优先级高的任务先运行一个时间片，时间片到了之后，然后调度器查看系统中优先级最高的任务，再把cpu分配给它运行。如果优先级相同的任务，就依次执行相同的时间片

呵呵，我对这种话题比较感兴趣，谈一谈我的理解，不对的地方大家多多指教。
我觉得要回答楼主的问题，要先解释1个概念，在Windows里有个称之为中断请求级别(IRQL)的东西,下面是有关软件中断的几种IRQL：
PASSIVE_LEVEL,
LOW_LEVEL,
APC_LEVEL,
DISPATCH_LEVELPASSIVE_LEVEL表示最低的IRQL，运行在PASSIVE_LEVEL的线程可以被任何高IRQL的事情打断，所有用户模式代码都运行在PASSIVE_LEVEL上。
而线程调度器是运行在DISPATCH_LEVEL上，运行在DISPATCH_LEVEL上的线程只有可能被更高基本的中断抢占，
DISPATCH_LEVEL是最高的软件中断，在它之上的IRQL就是硬件中断（DIRQL），系统的时钟中断就是硬件中断。
所以线程调度的大概流程就是时钟中断到来时，会触发运行在DISPATCH_LEVEL上的线程调度器，而线程调度器会根据线程的优先级来选择优先级较高的线程运行，即使某一用户线程会出现楼主所说的循环运行并阻塞的情况，但它的IRQL是最低的，所有还是会被线程调度器重新调度。不知道有没有解释清楚？

第一个问题，内核内部始终会有一个中断，就是时钟中断，每到这个时候，总有重新排程的可能。
即OS负责排程/调度，一般是在IO等待等场合都有重新调度的可能；就算没有这些时机，时钟中断总能保证CPU能够有调度的机会。第二个问题看看简单的时序电路就能理解。

NT 内核的进程调度分析笔记本篇文章来源于黑客基地-全球最大的中文黑客站众所周知 nt kernel 是多任务抢占试方式运行的，在非 SMP 系统上，每个进程分配特定的CPU 时间片来达到执行目的，这样看上去就象多个任务在同时运行。而 nt kernel又是以线程调度为核心的，这样线程切换了也就意味着当前进程的切换。系统不断重复这个过程，来使每个进程得以运行。在介绍流程前，需要先了解几个系统内部结构：KPCR、ETHREAD、EPROCESS、可以说，涉及到进程调度的函数基本都是对这几个重要结构的设置与填充。关于各结构的细节，对系统内核有所了解的人自然都很熟悉，我就不再多废话了。这里是结合进程调度来说。KPCR 这个结构存放的是当前 CPU 所正在处理的各种信息，其中包括了当前正在运行的线程 ETHREAD 结构。而 ETHREAD 结构又与EPROCESS 结构是相互关联的。这也就是很多核心函数通过 KPCR 启始地址 0xFFDFF000 + 偏移就能够得到当前正在运行的线程与进程的原因，如 KeGetCurrentThread()、IoGetCurrentProcess() 等。这也表明在非 SMP 系统上，某时间段内当前 CPU 处理的进程只可能有一个。当进行进程调度时系统将根据当前所存活的进程来选择让哪个线程 ETHREAD 结构来替换 KPCR 中的 ETHREAD，使其变为正在运行的状态。那么又是如何触发进程调度请求能让所有进程均得以执行的呢？
开始已经提到过，每个进程分配特定的 CPU时间片来达到执行目的，而系统的 CPU 时钟中断确定了每个进程分配的时间片。也就是当系统 CPU 时钟中断触发时，产生的进程调度请求。在详细分析调度流程与各函数分支前，我们先来看一下大致的流程。
首先当 CPU 时钟中断触发时，系统将调用 KiDispatchInterrupt()，比较当前进程分配的时间片，如用完后会调用 KiQuantumEnd()根据各线程优先级等信息用特定的调度算法选择新的线程（ETHREAD），然后将其返回值，一个 ETHREAD 结构作为参数，来调用 SwapContext() 设置 ETHREAD，EPROCESS 中的各项参数，并替换 KPCR 中的相应结构完成线程切换，调度到另一个进程（EPROCESS）的线程（ETHREAD）继续执行。（当线程等待某一事件（Event）或信号量（Semaphore）时会自动放弃当前时间片）。通过上面的大致分析，我们可以看出与进程调度密切相关的几个函数，KiDispatchInterrupt() 与 SwapContext()，下面我们将就这两个关键的调度函数进行详细的分析。.........笔记是今年春节利用放假时间写的，当时分析到一半才发现原来 WIN2K 源代码中已经包含了此部分，无奈已经把汇编进行了简单的注释，索性就这样写下去。错误之处再　　所难免，还望得到您的指正。
　　参考资源： Windows 2000 源代码
　　感谢 FlashSky，SoBeIt 与我探讨。
　　WSS(Whitecell Security Systems)，一个非营利性民间技术组织，致力于各种系统安全技术的研究。坚持传统的hacker精神，追求技术的精原文比较长，不引用，请看下面链接：
http://www.hackbase.com/tech/2008-11-26/42443.html

下面网文：Windows的调度是基于中断实现的，这与linux的实现不同：全文见：http://www.douban.com/group/topic/11077068/某种意义上nt内核用irql解决了一切，这正是由于它有一个基本的，核心的支撑。这就是它的抽象中断框架---IRQL。在linux中，我们知道，如果我要知道能否调用schedule进行调度，那么我必须知道还有什么数据结构处在临界区，这个时候是否适合抢占，等等，当然内核的数据结构已经做得很好，我们做开发的不用考虑那么多，比如用spin_lock啦，用preempt_disable啦，但是当你读到这些横七竖八的加锁，禁中断，一会又开锁，一会又锁页面...我估计有几种人会疯狂的：1.c语言基础不好的人；2.没有耐心的人；3.在读源码方面没有激情的人；.....剩下的就是 linux内核社区的人了，呵呵
再看看windows的代码，虽然都是反汇编得到的，但是就是不看c代码，直接看汇编吗，也是很容易的。
nt系统的总体框架做得异常威猛，它能不与硬件交互就尽量不与硬件交互，把整个系统抽象到了一个很高的级别，比如，它为每一个cpu都抽象出一个结构体，记录此cpu的一些信息，比如当前线程，当前进程，切换次数...，这个数据结构连接到此cpu上的所有进程控制块。相比之下，linux就简陋多了，只是每个cpu一个current宏，还有一系列以cpu为索引的每cpu变量，这些结构没有像nt内核里做得那样：高内聚。
nt内核引入irql完全是为了异步性操作，这就是为什么nt一开始就是为异步而存在，在这点上，异步性是设计理念，而irql是实现方案。中断是一个百分之百的异步性操作，你预测不到它下一次何时到来（时钟中断除外），所以nt内核将所有的操作都像中断的概念抽象，因为中断的不确定---异步性，那么线程上下文就是个问题了，于是ddk文档中屡次提到“任意上下文”。这就是说，只要你把操作（执行绪）抽象成了中断---拥有了passtive以上的中断优先级，那么你就不要指望会在特定的上下文里面执行你的操作，这就是完全异步的概念。实际上，nt内核可能受到了unix进程的影响，所以线程上下文大多数情况在被动中断请求级别运行，它们拥有上下文，而且叫做“进程”，“线程”，系统里面的执行绪，它们比较特殊，而且不那么异步，可以说，一切都为线程服务，这可能是唯一那么一点不对称的地方吧
nt内核的另一大特性就是对象化，几乎所有的模块都纳入对象化管理范畴，比如io管理器，进程管理器之类的，实际上，irql和对象化是有联系的，前者着重于执行，后者着重于管理，中断本身就是一种对象。
......这么看来，如果在硬件中断到来之前，当前cpu已经在dispatch_level了，那么硬件中断完毕后就不会执行dpc过程，而是会返回到原来的环境。那么现在可以谈谈nt内核的调度机制了，这里只是说机制，并不提算法，比算法，nt倒是没法和linux和solaris比了，呵呵（还是有所偏好啊），这里只谈结构。nt的调度代码运行在dispatch_level上，这是因为nt是个完全抢占式的内核，而且它所谓的抢占不仅仅是基于线程优先级，还有一个中断请求级（irql），如果调度代码在被动优先级运行，那么别的线程代码都可能抢占它，要想不被抢占就要加锁禁止抢占等，但是那就到 linux的方法上去了，所以，调度代码必须在一个很高的中断优先级上运行，但是又不能太高，于是选择了dispatch级别，这个名称就是由他而来的，这样，高于或等于这个级别的代码在执行时，完全不可能切换线程，达到了锁定一些东西的目的，另外，缺页处理也在这个级别，道理和此一样，但是高于等于此优先级的代码就不能用分页内存了，这是一个弊端（缺页在dispatch以上不能发生的原因实际是缺页要进行磁盘io，而磁盘io的开始例程在 dispatch级别进行，分发例程在被动级别运行，可能还要睡眠，而进入缺页就到了dispatch级别，睡眠了进程不能切换，系统崩溃，还有即使不睡眠，那么磁盘io也不能抢占缺页处理），继续说调度，那么，什么时机进行调度呢？
nt内核是可抢占的，任何时候只要新的线程被加入运行队列，那么它的线程优先级就可能被重新安排，如果有优先级比当前线程大的，就切换，这一切都是由dispath_level的中断进行的，也就是说，如果我现在想中断一个线程的执行，我只需要发起一个KiRequestSoftwareInterrupt请求，请求一个调度就可以了。

http://download.csdn.net/detail/a3212857896/3011539

1. 时钟芯片不在CPU上，一般集成在主板上，OS启动时配置好时钟中断，CPU的interrupt引脚每ms就会收到中断信号，时钟中断优先级很高的，高于一般的外设，时钟中断服务程序响应中断更新系统tick count，检查当前线程的时间片，如果时间片已用完，生成一个线程调度dispatch的软中断，这样时钟中断服务例程结束后，负责调度软中断服务例程就得到响应执行线程调度；2. 主板上晶振产生时钟源，CPU经过自己的分频倍频后可以得到一个很快的时钟，然后这个时钟驱动CPU工作。
当然这个工作频率针对特定的CPU有上限，如果调得过快，内部的开关条件得不到满足CPU就会工作异常。
至于IO操作，现在外设一般都怪在内部总线上(如PCI)，它的时钟跟CPU就无关了。

任务调度的硬件基础是中断，中断是硬件实现的，和软件层面无关，操作系统（软件）只是负责在中断发生后处理啥，操作系统不能在无硬件中断的CPU上纯软件实现抢先式任务调度。就算没有操作系统，我们也可以用硬件时钟中断来自己实现多任务调度，只是麻烦一点而已

时钟中断，阿门。
楼主可以去看看《intel开发者手册，卷3：系统编程向导》。

有点明白，但还是不懂。能不能从开源的OS code中取一段来个举例说明？

“OS启动时配置好时钟中断”，BIOS引导前就完成时钟同步了吧

我目前只是想了解设计一个操作系统最有挑战性的问题是如何解决的。弄清一个开源的OS需要不少时间。再说，完全弄清一个开源的OS有意义，但意义不是很大，因为版权的问题，我们无法再利用。如果有资金，又有足够的技术储备，象韩国人那样开发出一个兼容Windows的操作系统，就有点意义。

调试易

Windows抢占式多任务是如何实现的？

解决方案 »