线程调度实习报告目录内容一：总体概述 (3)内容二：任务完成情况 (3)任务完成列表（Y/N） (3)具体Exercise的完成情况 (3)内容三：遇到的困难以及解决方法 (8)内容四：收获及感想 (9)内容五：对课程的意见和建议 (9)内容六：参考文献 (9)内容一：总体概述本次lab主要是对线程调度的学习和理解。

当计算机系统是多道程序设计系统时，通常就会有多个进程或或线程同时竞争CPU。

只要有两个或更多的进程处于就绪态，这种情况就会发生，那么就必须选择下一个要运行的进程。

在操作系统中，完成选择工作的这一部分称为调度程序，该程序使用的算法称为调度算法。

进程调度策略的选择对整个系统性能有至关重要的影响，一个好的调度算法应该考虑很多方面：公平、有效、响应时间、周转时间、系统吞吐量等等。

但这些因素之间又是相互矛盾的，最终的取舍根据系统要达到的目标而定,同时我们也可以看出多进程的管理是～种非常复杂的并发程序设计．每个进程的状态不仅由其自身决定，而且还要受诸多外在因素的影响．而在此基础上的进程调度，为了保证操作系统的稳定性、提高效率和增加灵活性，还必须采用很多方法，这些都是值得我们去研究和探讨的。

本次实验针对Nachos系统的代码的阅读和修改，了解Nachos系统中线程调度在代码中如何实现，以及在其上扩展线程调度算法，实现基于优先级的抢占式调度算法。

内容二：任务完成情况任务完成列表（Y/N）Exercise1 Exercise2 Exercise3完成情况Y Y Y具体Exercise的完成情况Exercise1调研了解Linux或Windows中采用的进程/线程调度算法。

解答：Linux 的调度算法演化伴随着其内核版本的更迭，具有代表性的版本以此为：2.4，2.6,以及最近几年频繁更替的版本：3.5,3.6,3.7,3.8，其中3.8 是最新的稳定版本。

下面就其调度机制的演化进行论述。

在 2.4 版本的内核之前，当很多任务都处于活动状态时，调度器有很明显的限制。

这是由于调度器是使用一个复杂度为O(n) 的算法实现的。

在这种调度器中，调度任务所花费的时间是一个系统中任务个数的函数。

换而言之，活动的任务越多，调度任务所花费的时间越长。

在任务负载非常重时，处理器会因调度消耗掉大量的时间，用于任务本身的时间就非常少了。

因此，这个算法缺乏可伸缩性。

在对称多处理系统（SMP）中，2.4 版本之前的调度器对所有的处理器都使用一个运行队列。

具体来说，linux2.4 采用的是遍历可运行队列，动态优先级调度算法，其算法的复杂度在O(n)级别上，而linux2.6 采用的是双队列调度算法，一个是活跃的优先级数组，另一个是过期的优先级数组，这一思想在最新版的3.8 上面仍然继续沿用。

Linux 的调度将所有进程分为三类，一是交互式进程，他们有大量的人机交互，不断地处于睡眠状态，等待用户输入。

此类进程对系统响应时间要求比较高，否则用户会感觉系统反应迟缓。

第二个是批处理进程，他们不需要人机交互，在后台运行大量的运算。

此类进程需要占用大量的系统资源，但是能够忍受响应延迟。

第三个是实时进程，他们对调度延迟的要求最高，这些进程往往执行非常重要的操作，要求立即响应并执行。

这类程序不能容忍长时间的调度延迟。

在2.4 的调度策略使用的是Pick-Next 算法：对Runqueue 中所有进程的优先级进行依次进行比较，选择最高优先级的进程作为下一个被调度的进程。

(Runqueue 是Linux 内核中保存所有就绪进程的队列)。

旧版的进程时间片计算：每个进程被创建时都被赋予一个时间片。

时钟中断递减当前运行进程的时间片，当进程的时间片被用完时，它必须等待重新赋予时间片才能有机会运行。

Linux2.4 调度器保证只有当所有RUNNING 进程的时间片都被用完之后，才对所有进程重新分配时间片。

这段时间被称为一个epoch。

这种设计保证了每个进程都有机会得到执行。

旧版的进程优先级计算：普通进程的优先级主要由进程描述符中的Counter 字段决定(还要加上nice 设定的静态优先级)。

当所有RUNNING进程的时间片被用完之后，调度器将重新计算所有普通进程的Counter 值（不仅包括RUNNING 进程，也包括睡眠进程）。

处于睡眠状态的进程的Counter 本来就没有用完，在重新计算时，他们的Counter 值会加上这些原来未用完的部分，从而提高了它们的优先级。

实时进程：实时进程的优先级是静态设定的，而且始终大于普通进程的优先级。

因此只有当Runqueue 中没有实时进程的情况下，普通进程才能够获得调度。

实时进程的时间片被用完时，重新分配时间片，并重新插入Runqueue 中。

实时进程调度策略：SCHED_FIFO 和SCHED_RR。

FIFO 采用先进先出的策略，对于所有相同优先级的进程，最先进入Runqueue 的进程总能优先获得调度；Round Robin 采用更加公平的轮转策略，使得相同优先级的实时进程能够轮流获得调度。

而在 2.6 版本的调度策略是基于动态抢占的，支持负载均衡，并以恒定的速度进行O(1)，它解决了2.6 之前调度器中三个主要问题（O(n)、SMP 调度、实时性）。

调度器为每一个CPU 维护了两个进程队列数组：active 数组和expire数组。

数组中的元素保存某一优先级的进程队列指针。

系统一共有140 个不同的优先级，因此这两个数组大小都是140（1-99 为实时任务）。

当需要选择当前最高优先级的进程时，2.6 调度器不用遍历整个Runqueue，而是直接从active 数组中选择当前最高优先级队列中的第一个进程。

普通进程时间片计算：每次时钟tick 中断中，进程的时间片(time_slice)被减一。

当time_slice 为0 时，调度器判断当前进程的类型（交互式进程满足Dynamic priority ≤3 x staticpriority /4 + 28），如果是交互式进程或者实时进程，则重置其时间片并重新插入active 数组。

如果不是交互式进程则从active 数组中移到expired 数组。

这样实时进程和交互式进程就总能优先获得CPU。

然而这些进程不能始终留在active 数组中，否则进入expire 数组的进程就会产生饥饿现象。

当进程已经占用CPU 时间超过一个固定值后，即使它是实时进程或者交互式进程也会被移到expire 数组中。

普通进程优先级计算：dynamic priority = max(100, min(staticpriority – bonus + 5, 139))。

其中bonus 取决于进程的平均睡眠时间。

平均睡眠时间越长，其bonus 越大，从而得到更高的优先级（提高了交互式进程的优先级）。

实时进程：实时进程的优先级由sys_sched_setschedule()设置。

该值不会动态修改，而且总是比普通进程的优先级高。

实时进程的时间片被用完时，重新分配时间片，并重新插入Active 队列尾部。

Ingo Molnar 从RSDL/SD 中吸取了完全公平的思想，在Linux Kernel2.6.23 引入CFS 调度器。

按照作者的说法：“CFS 百分之八十的工作可以用一句话概括：CFS 在真实的硬件上模拟了完全理想的多任务处理器”。

在“完全理想的多任务处理器”下，每个进程都能同时获得CPU 的执行时间。

当系统中有两个进程时，CPU 的计算时间被分成两份，每个进程获得50%。

然而在实际的硬件上，当一个进程占用CPU 时，其它进程就必须等待。

这就产生了不公平。

所以CFS 将惩罚当前进程，使其它进程能够在下次调度时尽可能取代当前进程。

CFS 使用红黑树选取下一个被调度进程。

所有状态为RUNABLE 的进程都被插入红黑树。

在每个调度点，CFS 调度器都会选择红黑树的最左边的叶子节点作为下一个将获得cpu 的进程（该读取操作的时间复杂度是O(LgN)）。

如果在调度时当前进程不再是红黑树的最左边的叶子节点，就会被抢占。

Windows 中的每一个进程都是EPROCESS 结构体。

此结构体中除了进程的属性之外还引用了其它一些与实现进程紧密相关的结构体。

例如，每个进程都有一个或几个线程, 线程在系统中就是ETHREAD 结构体。

简要描述一下存在于这个结构体中的主要的信息, 这些信息都是由对内核函数的研究而得知的。

首先，结构体中有KPROCESS 结构体, 这个结构体中又有指向这些进程的内核线程(KTHREAD) 链表的指针( 分配地址空间), 基优先级, 在内核模式或是用户模式执行进程的线程的时间, 处理器affinity( 掩码，定义了哪个处理器能执行进程的线程) ，时间片值。

在ETHREAD 结构体中还存在着这样的信息: 进程ID 、父进程ID 、进程映象名。

在EPROCESS 结构体中还有指向PEB 的指针。

ETHREAD 结构体还包含有创建时间和退出时间、进程ID 和指向EPROCESS 的指针, 启动地址，I/O 请求链表和KTHREAD 结构体。

在KTHREAD 中包含有以下信息: 内核模式和用户模式线程的创建时间，指向内核堆栈基址和顶点的指针、指向服务表的指针、基优先级与当前优先级、指向APC的指针和指向T E B 的指针。

KTHREAD 中包含有许多其它的数据, 通过观察这些数据可以分析出KTHREAD 的结构。

通过遍历KPROCESS 结构体中的ETHREAD, 找到系统中当前所有的KTHREAD 结构, 这个结构中的偏移量为0x124处的Affinity 域(WindowsXPsp3) 即为设置CPU 亲缘性掩码的内存地址。

Windows 实现了一个优先驱动的，抢先式的调度系统——具有最高优先级的可运行线程总是运行，而该线程可能仅限于在允许它运行的处理器上运行，这种现象称为处理器亲和性，在默认的情况下，线程可以在任何一个空闲的处理器上运行，但是，你可以使用windows 调度函数，或者在映像头部设置一个亲和性掩码来改变处理器亲和性。

在此重点解释CPU 亲缘性的概念,CPU 亲缘性就是指在系统中能够将一个或多个进程或线程绑定到一个或多个处理器上运行, 这是期待已久的特性。

也就是说“: 在1 号处理器上一直运行该程序”或者是“在所有的处理器上运行这些程序，而不是在0 号处理器上运行”。

然后, 调度器将遵循该规则，程序仅仅运行在允许的处理器上。

Windows 的进程调度代码是在它的System 进程下的，所以它不属于任何用户进程上下文。

调度代码在适当的时机会切换进程上下文, 这里的切换进程上下文是指进程环境的切换, 包括内存中的可执行程序, 提供程序运行的各种资源. 进程拥有虚拟的地址空间, 可执行代码, 数据, 对象句柄集, 环境变量, 基础优先级, 以及最大最小工作集等的切换。