《操作系统课程设计进程调度》由会员分享，可在线阅读，更多相关《操作系统课程设计进程调度（36页珍藏版）》请在金锄头文库上搜索。
1、进程调度实现源代码分析摘要 本文对Linux内核中进程调度部分的源代码进行了详细的流程分析与代码注释，并对该部分的代码实现进行了研究。画出了具体的流程图，及分析了具体的作用。在进程调度部分主要涉及了Linux的调度算法及实现.关键词：操作系统 进程 进程调度 中断 定时器 运行队列 系统调用 门 内核空间 用户空间目录第一章 引 言3第二章 Linux 内核的整体结构4第三章 进程调度5一、 Linux进程调度的策略5二、Linux进程调度的加权处理5三、在Linux中，进程的结构及状态转换关系6四、 Linux进程的调度算法8五、 Linux进程的调度时机9六、 Linux进程的队列10七、
2、Linux进程调度的全过程12第四章Linux源码模块功能12一、进程调度函数：schedule ( )12二、 计算进程权值的函数：goodness ( )15三、载入新进程函数：switch_mm ( )17四、函数add_to_runqueue ( )18五、函数del_from_runqueue ( )19六、函数move_last_runqueue ( )20七、函数 move_first_runqueue ( )20第五章 内核源代码分析22第六章 分析研究体会33第七章 自我评价36第八章 参考文献36第一章 引 言在计算机系统中，处理机是整个系统的核心资源。在多处理机操作系统中
3、，进程调度就是把处理机公平、合理、高效地分配给各个进程。计算机系统整体的运行性能如响应的及时性、用户作业周转时间的长短、作业吞吐量的大小等，都与进程调度有关。所以，进程调度是操作系统的核心部分。Linux中进程调度的对象是可运行队列中的进程，它是按照一定的调度方式、采用给定的调度算法，从可运行队列中选择一个进程，把处理机分配给它，使它成为运行态。Linux继承了UINX进程调度的方法，并且又采用了若干最新技术。在整个计算机系统中CPU是最宝贵的资源，所有的任务必须由CPU来执行。因此只有充分利用CPU，才能最大程度的提高系统的效率。Linux是一个多进程系统，它通过进程调度解决了充分利用CPU
4、的问题。当一个进程因为得不到某些资源而等待时，Linux在此时不是让CPU空转等待进程获得足够资源后继续运行，而是采取一定的调度策略选择另外一个进程交给CPU去执行。虽然某个进程会因为各种原因停止运行，CPU却总是有任务在执行，这样，CPU就得到了充分的利用，从而大大提高了系统的效率和吞吐量。 我国的IT产业起步较晚，技术落后于西方经济发达国家。在我国，由于受知识产权的限制，无论是使用PC 平台上的Windows，还是使用应用于大中型机的UNIX，都无法窥视到其内部结构。这些系统很可能存在不为我们所知的漏洞，如果这些漏洞为别有用心者所利用，将会严重危及我国的经济安全和国家安全。操作系统不同于其
5、它软件产品，它是其它应用程序得以运行的平台，应用软件的开发必须基于对相应平台(操作系统)的技术的理解和掌握。由于我们的软件企业无法获知这些系统的细节，根本无法与拥有这些关键技术的国外先进企业相抗衡，长此以往，将会对我国软件产业产生深远的负面影响。因此，分析Linux源代码对于在Linux现有的基础上开发我们自己的Linux就具有非常现实和重要的意义。在这次课程设计中，我主要在源码水平上讨论Linux内核进程调度的实现，其目的是通过对源码的分析与研究，为以后的学习打下基础。第二章 Linux 内核的整体结构Linux内核由5个主要的子系统组成。这5个子系统分别是进程调度(SCHED)、内存管理(
6、MM)、虚拟文件系统(Virtual File System,VFS)、网络接口(NET)和进程间通信(IPC)。进程调度控制着进程对CPU的访问。当需要选择下一个进程运行时，由调度程序选择最值得运行的进程。可运行进程实际是仅等待CPU资源的进程，如果某个进程在等待其它资源，则该进程是不可运行进程。Linux使用了比较简单的基于优先级的进程调度算法选择新的进程。下图显示了上述五个子系统之间的关系： 图 1 在这些子系统中，进程调度子系统是其他子系统得以顺利工作的关键。无论是文件系统的系统进程还是网络子系统的服务进程都需要通过进程调度来获得相应的CPU时间以正常运行。第三章 进程调度一、 Lin
7、ux进程调度的策略进程调度的策略主要考虑以下几个原则：1、高效 使处理器的利用率最高，空闲最小；2、公平 使每一个申请处理器的进程都得到合理的处理器时间；3、周转时间短 使用户提交任务后得到结果的时间尽可能短；4、吞吐量大 使单位时间内处理的任务数量尽可能多；5、响应时间短 使对每个用户响应的时间尽可能短。Linux有两种类型的进程：实时和非实时（普通）。实时进程比所有其它进程的优先级高。如果有一个实时的进程准备运行，那么它总是先被运行。实时进程有两种策略：时间片轮转或先进先出（round robin and first in first out）。在时间片轮转的调度策略下，每一个实时进程依次
8、运行，而在先进先出的策略下，每一个可以运行的进程按照它在调度队列中的顺序运行，这个顺序不会改变。对于非实时进程，Linux永远选择优先级最高的进程来运行。Linux进程优先级是一些简单的整数，它代表了为决定应该允许哪一个进程使用CPU的资源时判断方便而赋予进程的权值优先级越高，它得到CPU时间的机会也就越大。二、Linux进程调度的加权处理Linux采用了加权处理的方法，在进程调度过程中，每次选取下一个运行进程时，调度程序首先给可运行队列中的每个进程赋予一个权值。普通进程的权值就是它的counter值，而实时进程的权值是它的rt_Priority的值加1000。这样使得实时进程的权值总是大于普
9、通进程。然后，调度程序检查可运行队列中所有进程的权值，选择其中权值最大的进程作为下一个运行进程。这就使得实时进程总是比普通进程优先得到CPU的使用权。Linux使用内核函数goodness()对进程进行加权处理，他的源程序在/kernel/sched.c中，如下的是去掉其中多处理机部分后简化的程序代码。Static inline goodness(struct task_struct*p,struct task_struct*prev,int this_cpu)int weight;if(p-policy!=SCHED_OTHER)return 1000+p-rt_priotity;weigh
10、t=p-counter;return weight;三在Linux中，进程的结构及状态转换关系task_struct的结构用来管理系统中的进程。Task向量表是指向系统中每一个task_struct结构的指针的数组。这个表让Linux可以查到系统中的所有的进程。操作系统初始化后，建立了第一个task_struct结构INIT_TASK。当新的进程创建时，从系统内存中分配一个新的task_struct，并增加到Task向量表中。用current指针指向当前运行的进程。task_struct结构中有关于进程调度的两个重要的数据项： struct task_struct volatile long
11、state; unsigned long flags; ；Linux在sched.h中定义了六种状态， 它们的含义分别是：1.TASK_RUNNING：正在运行的进程（是系统的当前进程）或准备运行的进程（在Running队列中，等待被安排到系统的CPU）。处于该状态的进程实际参与了进程调度。2.TASK_INTERRUPTIBLE：处于等待队列中的进程，待资源有效时唤醒，也可由其它进程被信号中断、唤醒后进入就绪状态。3.TASK_UNINTERRUPTIBLE：处于等待队列中的进程，直接等待硬件条件，待资源有效时唤醒，不可由其它进程通过信号中断、唤醒。4.TASK_ZOMBIE：终止的进程，是
12、进程结束运行前的一个过度状态（僵死状态）。虽然此时已经释放了内存、文件等资源，但是在Task向量表中仍有一个task_struct数据结构项。它不进行任何调度或状态转换，等待父进程将它彻底释放。5.TASK_STOPPED：进程被暂停，通过其它进程的信号才能唤醒。正在调试的进程可以在该停止状态。6.TASK_SWAPPING：进程页面被兑换出内存的进程。这个状态基本上没有用到，只有在sched.c的count_active_tasks（）函数中判断处于该种状态的进程也属于active的进程，但没有对该状态的赋值。 进程的状态随着进程的调度发生改变，下图显示了一个进程的状态转换关系： 图 2四、
13、 Linux进程的调度算法Linux进程调度的对象是可运行的队列，任何进程申请使用CPU就必须加入到这个队列中。1、时间片轮转调度算法用于实时进程。系统使每个进程依次地按时间片轮流执行的方式。2、 优先权调度算法用于非实时进程。系统选择运行队列中优先级最高的进程运行。Linux采用抢占式的优级算法，即系统中当前运行的进程永远是可运行进程中优先权最高的那个。1 FIFO(先进先出) 调度算法实时进程按调度策略分为两种。采用FIFO的实时进程必须是运行时间较短的进程，因为这种进程一旦获得CPU就只有等到它运行完或因等待资源主动放弃CPU时其它进程才能获得运行机会。Linux系统把进程分为实时进程和
14、非实时进程。对于实时进程，Linux又把它们分成两种：一种是具有某种紧迫性的实时进程，Linux对它们采用FIFO的调度方式，即排在运行队列前面的进程先运行，直到它主动放弃CPU后，才能轮到下一个进程运行。由于采取这种算法，若是进程执行的任务比较短小，还能满足实时的需要，若是任务比较大，就会出现一个紧急的任务因为当前进程没有执行完而无法获得CPU，导致任务被迫等待而无法满足实时要求。对于这种实时进程，采用抢占式的调度算法更为合适，因此Linux处理实时任务的能力并不令人满意。另一种实时进程是用于保证人机及时性而设置的，称为分时进程也许更为贴切。Linux对这种进程采用时间片轮转调度法，使每个进
15、程都能及时地得到CPU，完全可以满足人机交互的需要。对于非实时进程，Linux采用优先权调度算法。采用这种算法，在很大程度上是在模仿UNIX。UNIX系统应用的事实证明，这种算法是很有效率的，它可以充分利用CPU时间，并使每一个进程都能够较公平地获得CPU时间。 五、 Linux进程的调度时机时机1.进程状态发生变化时(1) 处于运行态下的进程要等待某种资源，或等待其它进程的运行而转入等待态时，一般在该进程的程序中通过使用系统调用退出运行态。在这些系统调用中使用了进程调度函数schedule()。(2) 运行态下的进程在程序执行完毕后，一般通过调用内核函数do_exit()终止运行并转入僵死态。(3) 处于等待态的进程使用wake_up_process()函数唤醒它，然后置为可运行态。(4) 当一个进程的程序接受调试时，调式进程向被调试的进程发送信号SIGSTOP,被调试进程处理该信号时调用内核函数do_signal()。在该函数中，首先把当前进程置为暂停态TA
