操作系统课件 2-处理器管理

操作系统教程(第4版)

第二章处理器管理

高等教育出版社出版2008年3月第二章处理器管理2.1中央处理器2.2中断技术2.3进程及其实现2.4线程及其实现2.5Linux进程和线程2.6Windows2003进程和线程2.7处理器调度2.8作业的管理与调度2.9处理器调度算法2.10Linux调度算法2.11Windows2003调度算法2.1中央处理器

2.1.1处理器2.1.2程序状态字寄存器2.1.1处理器

1单处理器和多处理器系统共享存储(紧密耦合)多处理机系统和分布存储(松散耦合)多处理机系统。2寄存器(1)计算机系统的处理器包括一组寄存器，其个数根据机型的不同而不同，它们构成了一级存储，比主存容量小，但访问速度快。这组寄存器所存储的信息与程序的执行有很大关系，构成了处理器现场。寄存器(2)

通用寄存器--EAX，EBX，ECX和EDX指针及变址寄存器--ESP，EBP，ESI及EDI段选择符寄存器--CS、DS、SS、ES、FS、GS指令指针寄存器和标志寄存器--EIP、EFLAGS控制寄存器--CR0，CR1，CR2和CR3外部设备使用的寄存器3特权指令与非特权指令(1)机器指令的集合称指令系统

(1)数据处理类指令；

(2)转移类指令；

(3)数据传送类指令；

(4)移位与字符串指令；

(5)I/O类指令。特权指令与非特权指令(2)从资源管理和控制程序执行的角度出发，必须把指令系统中的指令分作两部分：特权指令和非特权指令。特权指令是指只能提供给操作系统的核心程序使用的指令，如启动I/O设备、设置时钟、控制中断屏蔽位、清主存、建立存储键，加载PSW等。4处理器状态处理器怎么知道当前是操作系统还是一般用户程序在运行呢?处理器状态标志:管理状态（特权状态、系统模式、特态或管态）和用户状态（目标状态、用户模式、常态或目态)。处理器状态的转换。处理器处于管理状态时，程序可以执行全部指令，使用所有资源，具有改变处理器状态的能力；处理器处于用户状态时，程序只能执行非特权指令IntelPentium的处理器状态有四种，支持4个保护级别，0级权限最高，3级权限最低2.1.5程序状态字寄存器(1)计算机如何知道当前处于何种工作状态？这时能否执行特权指令？通常操作系统都引入程序状态字PSW（ProgramStatusWord）来区别不同的处理器工作状态PSW用来控制指令执行顺序并保留和指示与程序有关的系统状态，主要作用是实现程序状态的保护和恢复每个程序都有一个与其执行相关的PSW，每个处理器都设置一个PSW寄存器。程序占有处理器执行，它的PSW将占有PSW寄存器程序状态字寄存器(2)

PSW寄存器包括以下内容：程序基本状态：

(1)程序计数器；

(2)条件码；

(3）处理器状态位。中断码。保存程序执行时当前发生的中断事件。中断屏蔽位。指明程序执行中发生中断事件时，是否响应出现的中断事件。

IBM360/370系列计算机

程序状态字的基本格式

XXXXXXXXXXXXXXXX8位系统屏蔽4位CMWP字段4位程序屏蔽4位保护键16位中断码字段指令长和条件码24位指令地址IntelPentium程序状态字IntelPentium中，PSW由标志寄存器EFLAGS和指令指针寄存器EIP组成，均为32位。EFLAGS的低16位称FLAGS，标志可划分为三组：状态标志、控制标志、系统标志。2.2中断技术2.2.1中断概念2.2.2中断源分类2.2.3中断和异常的响应及服务2.2.4中断事件处理2.2.5中断优先级和多重中断2.2.6Linux中断处理2.2.7Windows2003中断处理2.2.1中断的概念

•请求系统服务，•实现并行工作，•处理突发事件，•满足实时要求，都需要打断处理器正常的工作，为此，提出了中断概念。中断的定义

中断是指程序执行过程中，遇到急需处理的事件时，暂时中止CPU上现行程序的运行，转去执行相应的事件处理程序，待处理完成后再返回原程序被中断处或调度其他程序执行的过程。2.2.2中断源分类(1)

从中断事件的性质和激活的手段来说，可以分成两类：•强迫性中断事件强迫性中断事件不是正在运行的程序所期待的，而是由于某种事故或外部请求信息所引起的，分为：机器故障中断事件。程序性中断事件。外部中断事件。输入输出中断事件。•自愿性中断事件自愿性中断事件是正在运行的程序所期待的事件。

中断源分类(2)

按中断事件的性质和激活方式划分

运行程序中断处理程序中断装置中断处理程序中断装置机器故障中断事件程序性中断事件外部中断事件输入输出中断事件运行程序访管指令中断源分类(3)

硬中断软中断外中断(中断、异步中断)内中断(异常、同步中断)信号软件中断按事件来源和实现手段分类中断源分类(4)

•外中断(中断或异步中断)--是指来自处理器之外的中断信号，包括时钟中断、键盘中断、它机中断和设备中断等；外中断又分可屏蔽中断和不可屏蔽中断，每个不同中断具有不同的中断优先级，表示事件的紧急程度，在处理高一级中断时，往往会屏蔽部分或全部低级中断。•内中断(异常或同步中断)--是指来自处理器内部，通常由于程序执行中，发现与当前指令关联的、不正常的、或是错误的事件。中断和异常的区别

•中断是由与现行指令无关的中断信号触发的(异步的)，且中断的发生与CPU处在用户模式或内核模式无关，在两条机器指令之间才可响应中断，一般来说，中断处理程序提供的服务不是为当前进程所需的；•异常是由处理器正在执行现行指令而引起的，一条指令执行期间允许响应异常，异常处理程序提供的服务是为当前进程所用的。异常包括很多方面，有出错(fault)，也有陷入(trap)等。

Linux的异常

•Linux为例，异常按错误报告方式分四种：

故障、陷阱、终止、编程异常。

•故障发生时保存的返回指令地址指向触发异常的当前那条指令，故障处理后会重新执行。编程异常和陷阱是由于执行访管指令引起的同步操作，异常返回时，回到触发异常的下一条指令。

硬中断与软中断

中断和异常要通过硬件设施来产生中断请求，是硬中断。软中断是利用硬中断的概念，用软件方法对中断机制进行模拟，实现宏观上的异步执行效果。软中断分两种：“信号”和“软件中断”。中断的通常用法

“中断”(硬中断)用于外部设备对CPU的中断(中断的是正在运行的任何程序)，转向中断处理程序上半部分执行；“异常”(硬中断)因指令执行不正常而中断CPU(中断的是正在执行这条指令的程序)，转向异常处理程序；“软件中断”(软中断)用于硬中断服务程序对内核的中断，在上半部分中发出软件中断(即标记下半部分)，使得中断下半部分在适当时刻获得处理；“信号”(软中断)用于内核或进程对某个进程的中断，通知进程某个特定事件发生或迫使进程执行信号处理程序。中断机制与信号机制进行类比

相同点是：(1)概念上是一致的，(2)两者都是“异步”的，(3)实现上均采用“向量表”，(4）均具有“屏蔽”设施。区别是：中断机制由硬件与软件相结合来实现，而信号机制由软件实现；中断向量表和中断处理程序(由系统提供)均在系统空间，而信号向量表虽在系统空间，但信号处理程序由应用程序提供，并在用户空间执行。硬中断与软中断BH进行类比

(1)数组bh_base［］相当于硬件中断机制中的数组irq_desc[]；(2）bh_active在概念上相当于硬件的“中断请求寄存器”，而bh_mask相当于硬件中的“中断屏蔽寄存器”；(3)执行一个BH函数时，就通过mark_bh()将bh_active中的某位设成1，相当于中断源发出(软件)中断请求，所设置的具体标志位则类似于“中断向量”；(4)如果bh_mask中的相应位是l，就会在每次执行完do_IRQ（）中的中断服务程序后，及每次系统调用结束后，在函数do_bottom_half（）中执行相应BH函数，而do_bottom_half（），则类似于do_IRQ()。硬中断或软中断处理延时问题

CPU接到和响应硬中断或异常后会立即调用中断或异常处理程序处理；对于接收到的信号或软件中断，此时由于进程未必占有处理器运行或内核正在执行敏感性操作，通常会有一定时间的延迟，在适当的时刻内核或相关进程才能加以处理。信号和软件中断虽然都由软件产生，并都由软件处理，但它们的中断来源、使用场合、实现手段并不相同。中断/异常响应要做四件事发现中断源：保护现场：转向处理中断/异常事件的处理程序：恢复现场：IBM中大型机中断响应过程

外中断旧PSW访管中断旧PSW程序中断旧PSW机器故障中断旧PSWI/O中断旧PSW外中断新PSW访管中断新PSW程序中断新PSW机器故障中断新PSWI/O中断新PSW18202830385860687078现行PSW②中断时保存现行PSW③中断时装入现行PSW④中断后恢复PSW主存专用双字单元(16进制)①装配中断码

IBMPC机中断的响应过程

IPCSPSW现行PSW寄存器新IP新CS老IP老CS老PSW新栈顶主存新PSW2.2.4中断事件处理1中断和异常的一般处理过程2硬件故障中断3程序性中断4I/O中断5访管中断

6时钟中断(1)时钟是操作系统进行调度工作的重要工具，如让分时进程作时间片轮转、让实时进程定时发出或接收控制信号、系统定时唤醒或阻塞一个进程、对用户进程进行记账时钟可分成绝对时钟和间隔时钟两种时钟中断(2)

1)绝对时钟服务提供以下功能的函数：update_clock()更新当前时间；get_time()返回当前时钟值；set_clock()把当前时间设置为新值。时钟中断(3)

2)间隔定时器进程可被延迟、阻塞，直到被间隔定时器中断信号唤醒，应提供以下函数：delay(tdel)把调用进程阻塞由参数tdel指定的时间长度，进程保持阻塞直到本地时间到达进程阻塞时的当前时间+tdel的时刻。set_timer(tdel)硬件间隔定时器被设置为起始的递减值tdel，当该值达到0时，产生间隔时钟中断，调用timeout()函数进行处理。

时钟中断(4)

3)逻辑定时器需要提供函数：tn=creat_ltime()：创建逻辑定时器，tn中存放返回标识符。destroy_ltime(tn)：撤销tn标识的逻辑定时器。set_ltime(tn,tv)：把tv值装到逻辑定时器tn中，当该值为0时，产生时间到中断。时钟中断(5)

(1)使用带有绝对唤醒定时器的优先级队列硬件时钟绝对时钟间隔时钟10312定时器队列P1115P2135P3140P41500定时器队列P1115P2135P5138P3140P41500时钟中断(6)

(2)使用带有时间差值的优先级队列硬件时钟间隔时钟12定时器队列P112P220P35P4100定时器队列P112P220P53P32P41002.2.5中断优先级和多重中断1中断的优先级2中断的屏蔽3多重中断事件的处理1中断优先级

计算机执行的每一瞬间，可能有几个中断事件同时发生，中断装置如何来响应同时发生的中断呢?以不发生中断丢失为前提，把紧迫程度相当的中断源归在同一级，紧迫程度差别大的中断源归在不同级，级别高的有优先获得响应的权力，中断装置预定的这个响应顺序称为中断优先级。

2中断的屏蔽

•主机可允许或禁止某类中断的响应，如允许或禁止所有的I/O中断、外部中断、及某些程序性中断。•有些中断是不能被禁止的，例如，计算机中的自愿性访管中断就不能被禁止。

3多重中断事件的处理

中断正在进行处理期间，CPU又响应新的中断事件，于是暂时停止正在运行的中断处理程序，转去执行新的中断处理程序，就叫多重中断（又称中断嵌套）。处理方法：(1)串行处理，(2)嵌套处理，(3)即时处理。

2.2.6Linux中断处理1Linux内核处理流程中断自陷慢中断快中断

进程正在运行用户态核心态上半部分处理

返回原进程运行

排队下半部分

快中断处理

系统调用处理

从系统调用返回ret_from_sys_call

调用schedule()

调度新进程运行运行用户态调度下半部分do_bottom_half()/do_softirq()

处理积累的信号do_signal()restore_all中断快中断与慢中断

•Linux中，区分快中断和慢中断两类中断事件。•处理慢中断前需保存所有寄存器的内容，而快中断处理仅要保存被常规C函数修改的寄存器；慢中断处理时，不屏蔽其他中断信号，而快中断处理时会屏蔽所有其他中断；•慢中断处理完毕后，通常不立即返回被中断的进程，而是进入调度程序重新调度，调度结果未必是被中断的进程运行(是抢先式调度)。而快中断处理完毕后，通常恢复现场返回被中断的进程继续执行(是非抢先式调度)。2下半部分处理概述中断处理程序的特点什么是下半部分处理TophalfBottomhalfLinux各种下半部分机制

bottomhalf、taskqueue、tasklet、workqueueSoftirq3下半部分(bottomhalf)实现原理

BH数组、函数入口指针bh_base、函数安装标志bh_mask、函数处理标志bh_activeBH的缺点bh-mask310031

··bh-active310bh-base下半部分处理函数4任务队列(taskqueue)实现原理预定任务队列：1)定时器队列(TQ_TIMER)：2)即时队列(TQ_IMMEDIATE)：3)进程调度队列(TQ_SCHEDULE)：4)磁盘队列(TQ_DISK)：定时器Tophalf与bottomhalf协调工作的例子5小任务(tasklet)

tasklet能更好支持SMP，它基于软中断来实现，但比软中断接口简单，锁保护要求低；softirq保留给执行频率及时间要求特高的下半部分使用(如网络和SCSI)，多数场合下可使用tasklet。使用tasklet的步骤：BH全局串行处理，不适应SMP环境，而不同tasklet可同时运行于不同CPU上，当然，系统保证相同tasklet不会同时在不同CPU上运行，在这种情形下，tasklet就不需要是可重入的。在新版Linux中，tasklet是建议的异步任务延迟执行机制。6工作队列workqueue

Linux2.5内核引入-工作队列，它把一个任务延迟，并交给内核线程去完成，且该任务总是在进程上下文中执行，通过工作队列执行的代码能占尽进程上下文的优势，最重要的是工作队列允许重新调度及阻塞。如果延迟执行的任务需要阻塞，需要获取信号量或需要获得大量主存时，那么，可选择工作队列，否则可使用tasklet或softirq。7软中断softirq

Linux沿用最早BH思想，已实现了庞大和复杂的软中断子系统-softirq，它是一种软中断机制，又是一个框架，包括tasklet，及为网络操作专门设计的软中断。最多可注册32个软中断，目前版本预定义六个元素，enum{HI_SOFTIRQ,//高优先级taskletTIMER_SOFTIRQ,//定时器下半部分NET_TX_SOFTIRQ,//发送网络数据包NET_RX_SOFTIRQ,//接收网络数据包SCSI_SOFTIRQ,//SCSI下半部分TASKLET_SOFTIRQ,//公共tasklet};软中断使用步骤：软中断执行时机：2.2.7Windows2003中断处理

Window2003中断类型中断有I/O设备、处理器时钟或定时器等，可以启用或禁用。中断是异步事件，可能随时发生，与处理器正在执行的内容无关。异常是同步事件，它是某一个特定指令执行的结果。异常的例子是主存访问错误、调试指令及被零除。内核也将系统服务调用视作异常。硬件和软件都可以产生中断和异常，如总线出错异常由硬件造成，而被零除异常是由软件引起的；同样，I/O设备可产生中断，而内核自身也可以发出中断。

Windows2000/XP陷阱调度

中断服务例程中断服务例程中断服务例程异常调度器虚存管理的页面管理器中断调度器系统服务调度器异常调度器陷阱处理程序异常帧虚拟地址异常硬件异常软件异常系统服务调用中断

Windows2000/XP中断请求级

系统关闭高31掉电30处理器内的中断29时钟28配置文件设备n………设备1Dispatch/DPC2APC1低0硬件中断软件中断正常的线程执行Windows2000/XP中断屏蔽

高掉电处理器内的中断时钟配置文件设备n………设备1在处理器A上被屏蔽的中断Dispatch/DPCAPC低IRQL=时钟处理器A在处理器B上被屏蔽的中断IRQL=Dispatch/DPC处理器BWindows2000/XP硬件中断处理

低（无）………高掉电处理器间的中断时钟设备n………设备1②中断调度程序接收到中断源的IRQL，用作查询IDT的索引Dispatch/DPCAPC①有中断产生线程调度程序/DPC处理程序系统关闭例程系统调电例程处理器间中断处理程序时钟处理程序设备nISR设备1ISRAPC处理程序③中断调度程序跟随该指针，调用相应的处理程序Windows2000/XP软件中断处理

多数中断由硬件产生，但内核也为多种任务产生软件中断，包括：启动线程调度、处理计时器到时、在特定线程的描述表中异步执行一个过程及支持异步I/O等。延迟过程调用DPC软件中断延迟过程调用--DPC提交和执行

高掉电………②如果IRQL降到比Dispatch/DPC级低，则DPC中断发生。Dispatch/DPCAPC低①定时器到时，内核排好DPC队列，准备释放等候在定时器上的所有线程，然后内核请求软件中断。………调度程序③DPC中断之后，控制传送给（线程）调度程序DPCDPCDPC④调度程序执行DPC中的每一个DPC例程，然后使队列变空。如果需要，调度程序还重新安排处理器异步过程调用

异步过程调用APC为用户程序和系统代码提供了一种在特殊用户线程的描述表(特殊的地址空间)中执行代码的方法。用户态APC和核心态APC

异常调度

异常是由运行程序的执行产生的情况。异常处理工具，允许应用程序在异常发生时可以得到控制。应用程序可以固定这个状态并返回到异常发生的地方展开堆栈，也可以向系统声明不能识别异常，并继续搜寻能处理异常的异常处理程序。除陷阱处理程序解决的异常外，所有异常均由异常调度程序提供服务，它的任务是找到能处理该异常的异常处理程序。如果异常产生于核心态，异常调度程序将调用一个例程来定位处理该异常的异常处理程序。没有被处理的核心态异常是一种致命的系统错误。用户态核心态系统服务调用陷阱处理程序系统服务调度程序系统服务调度表0123………n系统服务扩展系统服务2系统服务调度(1)

系统服务调度(2)

调用NtWriteFile开中断NTOSKRNL.EXE中的KiSystemService执行操作返回调用者NTOSKRNL.EXE中的NtWriteFile调用WIN32例程开中断NTOSKRNL.EXE中的KiSystemService执行操作返回调用者WIN32K.SYS中的服务入口点核心态软件中断软件中断调用WriteFile()Win32应用程序调用NtWriteFile返回调用者KERNEL32.DLL中的WriteFileINT2E返回调用者NTDLL.DLL中的NtWriteFile调用USER及GDI服务应用程序INT2E返回调用者GDI32.DLL或USER32.DLL用户态WIN32专用WIN32专用所有子系统使用WIN32内核APIWIN32USER及GDIAPI2.3进程及其实现

2.3.1进程的定义和属性2.3.2进程的状态和转换2.3.3进程的描述和组成2.3.4进程切换与模式切换2.3.5进程的控制和管理2.3.1进程的定义和性质

•进程是可并发执行的程序在某个数据集合上的一次计算活动，也是操作系统进行资源分配和保护的基本单位。

•进程是一个既能用来共享资源，又能描述程序并发执行过程的一个基本单位。操作系统为什么要引入进程概念?原因1-刻画系统的动态性，发挥系统的并发性，提高资源利用率。原因2-它能解决系统的“共享性”，正确描述程序的执行状态。“可再用”程序“可再入”程序“可再入”程序具有的性质“可再入”程序举例

编译程序P(P的入口,处理源程序乙)(P把源程序甲的信息记盘等磁盘完成)AB源程序甲源程序乙

进程的属性

•结构性：•共享性：•动态性：•独立性：•制约性：•并发性：2.3.2进程的状态和转换

进程三态模型及其状态转换

运行态就绪态等待态选中落选出现等待事件等待事件结束进程五态模型及其转换运行态就绪态等待态选中落选出现等待事件等待事件结束新建态终止态进程的挂起

进程为什么要有“挂起”状态?进程挂起的原因?

具有挂起功能的进程状态及其转换

挂起等待事件结束出现等待事件解除挂起挂起落选选中运行态就绪态等待事件结束终止态新建态挂起就绪态解除挂起挂起挂起等待态等待态提交提交挂起进程具有如下特征

•该进程不能立即被执行。•挂起进程可能会等待事件，但所等待事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件。•进程进入挂起状态是由于操作系统、父进程或进程本身阻止它的运行。•结束进程挂起状态的命令只能通过操作系统或父进程发出。2.3.3

进程的描述和组成(1)

1进程映象

进程控制块进程程序块进程核心栈进程数据块进程—用户线程—内核线程进程的描述和组成(2)

操作系统中把进程物理实体和支持进程运行的环境合称为进程上下文。当系统调度新进程占有处理器时，新老进程随之发生上下文切换。进程的运行被认为是在上下文中执行。进程的描述和组成(2)

进程上下文组成

•用户级上下文：•系统级上下文：•寄存器上下文：

2进程控制块

进程控制块PCB，是操作系统用于记录和刻划进程状态及有关信息的数据结构。也是操作系统掌握进程的唯一资料结构，它包括了进程执行时的情况，以及进程让出处理器后所处的状态、断点等信息。进程控制块包含三类信息标识信息现场信息控制信息

3进程队列及其管理(1)处于同一状态的所有PCB链接在一起的数据结构称为进程队列。同一状态进程的PCB既可按先来先到的原则排成队列;也可按优先数或其它原则排成队列。通用队列组织方式：线性方式、链接方式索引方式。

进程队列及其管理(2)PCB表PCB10PCB25PCB30PCB40PCB50PCB64运行队列指针就绪队列指针等待队列1指针等待队列2指针…PCBn7PCB70…空闲进程队列指针链接方式运行队列指针就绪表指针等待表1指针…索引方式PCB表

PCB1PCB2PCB3PCB4PCB5PCB6……PCBn空闲表指针…就绪索引表…等待索引表1等待表2指针Linux进程链表双向循环链表进程可运行队列链表散列链表等待队列链表

队列管理和状态转换示意图

处理器指派提交完成超时事件1等待队列事件2等待队列事件n等待队列就绪队列……等待事件1等待事件2等待事件n事件1出现事件2出现事件n出现2.3.4进程切换与CPU模式切换

进程切换是让处于运行态的进程中断运行，让出处理器，这时要做一次进程上下文切换、即保存老进程状态而装入被保护了的新进程的状态，以便新进程运行进程切换的步骤保存被中断进程的处理器现场信息修改被中断进程的进程控制块的有关信息，如进程状态等把被中断进程的进程控制块加入有关队列选择下一个占有处理器运行的进程修改被选中进程的进程控制块的有关信息根据被选中进程设置操作系统用到的地址转换和存储保护信息根据被选中进程恢复处理器现场调度和切换时机问题

•请求调度的事件发生后，就会运行低级调度程序，低级调度程序选中新的就绪进程后，就会进行上下文切换。实际上，由于种种原因，调度和切换并不一定能一气呵成。•通常的做法是，由内核置上请求调度标志，延迟到上述工作完成后再进行调度和进程上下文切换，•Linux进程调度标志位need-resched，Windows延迟过程调用DPC/dispatch软件中断。处理器模式切换•当中断发生时，暂时中断正在执行的用户进程，把进程从用户状态切换到内核状态，去执行操作系统例行程序以获得服务，这就是一次模式切换，•内核在被中断了的进程的上下文中对这个中断事件作处理，即使该中断可能不是此进程引起的模式切换的步骤1)保存被中断进程的处理器现场信息；2)处理器从用户态切换到核心态，以便执行服务程序或中断处理程序；3)如果处理中断，可根据规定的中断级设置中断屏蔽位；4)根据系统调用号或中断号，从系统调用表或中断入口表找到服务程序或中断处理程序地址。CPU上执行的进程所处活动范围

用户空间中，处于进程上下文，用户进程在运行，使用用户栈。内核空间中，处于进程上下文，内核代表某进程在运行，使用核心栈。内核空间中，处于中断上下文，与任何进程无关，中断服务程序正在处理特定中断，Intelx86未提供中断栈，借用核心栈。UNIX/Linux中上下文切换和模式切换

核心态运行系统调用或中断(隐含模式切换)模式切换用户态运行等待状态就绪状态发生事件唤醒调度进程中断、中断返回允许的上下文切换切换2.3.5进程的控制和管理(1)

处理器管理的一个主要工作是对进程的控制，包括：创建进程、阻塞进程、唤醒进程、挂起进程、激活进程、终止进程和撤销进程等。这些控制和管理功能由操作系统中的原语实现。原语是在管态下执行、完成系统特定功能的过程。原语和机器指令类似，其特点是执行过程中不允许被中断，是一个不可分割的基本单位，原语的执行是顺序的而不可能是并发的。进程的控制和管理(2)

进程创建进程撤销进程阻塞进程唤醒进程挂起进程激活2.4线程及其实现

2.4.1引入多线程的动机2.4.2多线程环境中的进程和线程2.4.3线程的实现

2.4.1引入多线程的动机

单线程(结构)进程（SingleThreadedProcess）多线程（结构）进程（MultipleThreadedprocess）

单线程结构进程给并发程序设计效率带来问题

•进程切换开销大•进程通信代价大•进程间的并发性粒度较粗，并发度不高•不适合并行计算和分布并行计算的要求•不适合客户/服务器计算的要求。线程的概念(1)操作系统中引入进程的目的是为了使多个程序并发执行，以改善资源使用率和提高系统效率，操作系统中再引入线程，则是为了减少程序并发执行时所付出的时空开销，使得并发粒度更细、并发性更好。线程的概念(2)

解决问题的基本思路：•把进程的两项功能－－“独立分配资源”与“被调度分派执行”分离开来，•进程作为系统资源分配和保护的独立单位，不需要频繁地切换；•线程作为系统调度和分派的基本单位，能轻装运行，会被频繁地调度和切换，在这种指导思想下，产生了线程的概念。2.4.2多线程环境中的进程与线程

多线程结构进程进程进程PCB资源线程控制块用户栈核心栈线程控制块用户栈核心栈…线程n控制块用户栈核心栈存储区存储空间全局数据程序代码线程1线程1线程控制块…线程2线程1线程控制块用户栈核心栈线程i线程n多线程环境中进程的定义

进程是操作系统中进行除处理器外的资源分配和保护的基本单位，它有一个独立的虚拟地址空间，用来容纳进程映像(如与进程关联的程序与数据)，并以进程为单位对各种资源实施保护，如受保护地访问处理器、文件、外部设备及其他进程(进程间通信)。

多线程环境中的线程概念

线程是操作系统进程中能够独立执行的实体（控制流），是处理器调度和分派的基本单位。线程是进程的组成部分，每个进程内允许包含多个并发执行的实体（控制流），这就是多线程。线程组成线程惟一标识符及线程状态信息；未运行时保存的线程上下文；可把线程看成是进程中一个独立的程序计数器在操作；核心栈，核心态下工作时，保存参数，函数调用时的返回地址等；用于存放线程局部变量及用户栈的私有存储区。线程又称轻量进程

•线程运行在进程的上下文中,并使用进程的资源和环境。•系统调度的基本单位是线程而不是进程,每当创建一个进程时，至少要同时为该进程创建一个线程，否则该进程无法被调度执行。

线程的状态

线程状态有：运行、就绪和阻塞，线程的状态转换也类似于进程。挂起状态对线程是没有意义的，如果进程挂起后被对换出主存，则它的所有线程因共享了进程的地址空间，也必须全部对换出去。线程管理和线程库(1)多线程技术利用线程包(库)提供线程原语集来支持多线程运行，有的操作系统直接支持多线程，而有的操作系统不支持多线程。线程包(库)可分成两种：用户空间中运行的线程包(库)和内核中运行的线程包(库)。线程管理和线程库(2)

线程包(库)提供一组API，支持应用程序创建、调度、撤销和管理线程的运行。基本线程控制原语：•孵化（Spawn）：又称创建线程。•封锁（Block）：又称阻塞线程。•活化（Unblock）：又称恢复线程。•结束（Finish）：又称撤销线程。并发多线程程序设计的优点

•快速线程切换。•减少（系统）管理开销。•(线程）通信易于实现。•(线程）通信易于实现。•并行程度提高。•节省主存空间。

多线程技术的应用

进程中线程多种组织方式：第一种是调度员／工作者模式第二种是组模式第三种是流水线模式

多线程技术的应用

•前台和后台工作•C/S应用模式•异步处理•加快执行速度。•设计用户接口。2.4.3线程的实现

从实现的角度看，线程分成:•用户级线程ULT(如Java,Informix)•内核级线程KLT(如OS/2)。•混合式线程(如，Solaris)。2.5Linux进程与线程进程描述符task_struct中包含：进程标识、链接信息、调度信息、文件信息、虚存空间信息、信号处理信息等，在v2.4以上内核代码中，它有将近100个成员。Linux中认为线程就是共享地址空间及其他资源的进程，故并没有单独为线程定义数据结构，有一套在用户模式下运行的线程库-pthread，但每个线程都拥有惟一隶属于自己的task_struct。Linux2.4进程的核心栈、PCB

和虚存映象

esp存放堆栈栈顶指针核心栈structtask_struct8KB

00x080480000x400000000xc0000000内核虚存用户栈(运行时创建)共享库主存映象区运行时堆空间堆(malloc创建)读/写段只读段从可执行文件加载esp用户代码不可见未用brkLinux2.6进程的核心栈进程核心栈进程核心栈栈顶栈指针espthread_info{*task

…}}

currenttask_struct进程的核心栈、*task和task_struct结构Linux进程的运行环境信息thread_info结构

包含：进程描述符task_struct指针、当前CPU号、底层标志、线程同步标志、内核抢占计数器等。Linux2.6task_struct

增加用于调度的新成员，主要有：动态优先级prio静态优先级static_prio正常优先级normal_prio优先级数组prio_array进程平均等待时间sleep_avg负载平衡权重load_weight等Linux进程状态TASK_RUNNINGTASK_INTERRUPTIBLETASK_UNINTERRUPTIBLETASK_ZOMBIE。TASK_STOPPEDTASK_SWAPPINGLinux进程状态及转换

wake_up_interruptible()wake_up()TASK_ZOMBIETASK_RUNNINGTASK_UNINTERRUPTIBLETASK_INTERRUPTIBLETASK_STOPPED占有CPU运行schedule()时间片到schedule()interruptible_sleep_on()schedulle()sleep_on()wake_up()创建do_fork()do_exit()schedule()syscall_trace()sys_exit()收到SIG_KILL或SIG_CONT后，执行wake_up()2.6Windows2003进程与线程进程是资源的容器，容纳各种分配到的资源如主存、已打开文件等；线程是可被内核调度的执行实体，可被中断，使CPU能转向另一线程执行。进程和线程用对象来实现。Windows对象分类(1)

Windows是一个基于对象的操作系统，用对象来表示所有的系统资源。

(1)执行体对象由执行体的组件实现的对象，用来实现各种外部功能，用户态程序(服务器对象)可访问执行体对象。执行体对象：进程、线程、区域、文件、事件、事件对、文件映射、互斥、信号量、计时器、对象目录、符号连接、关键字、端口、存取令牌和终端等。

Windows对象分类(2)

(2)内核对象内核实现的更原始的对象集合，包括：内核过程对象、异步过程调用对象、延迟过程调用对象、中断对象、电源通知对象、电源状态对象、调度程序对象等。

内核对象对用户态代码是不可见的，仅在执行体内创建和使用，许多执行体对象包含一个或多个内核对象，而内核对象能提供仅能由内核来完成的基本功能。Windows对象分类(3)Windows对象结构对象头对象体对象管理器

进程及控制和使用的资源

对象句柄表虚拟地址空间描述符文件x信号量y区域z…VADVADVADVAD进程访问令牌可用对象句柄1句柄2线程线程线程句柄3对象和句柄间的关系

应用程序执行体对象执行体内核用户态核心态句柄内核对象进程对象(进程描述表结构)

EPROCESS…void*UniqueprocessId;…KPROCESS…uint32kernelTime;uint32UserTime;…byteState;…NT内核NT执行体线程对象(进程和线程描述表结构)

KTHREADKTHREADEPROCESSKPROCESSETHREADKTHREADKTHREADKTHREADNT内核NT执行体调用CreateProcess函数创建进程

创建WIN32进程的具体步骤：•打开将在进程中被执行的映像文件（.EXE）。•创建Windows2000/XP执行体进程对象。•创建初始线程（堆栈、描述表、执行体线程对象）。•通知WIN32子系统已创建了一个新的进程，以便它可设置新的进程和线程。•启动初始线程的执行。•在新进程和线程的描述表中完成地址空间的初始化，加载所需的DLL，并开始程序的执行调用CreateThread函数创建线程

创建WIN32线程的具体步骤：•在进程地址空间内为线程创建用户态堆栈；初始化线程描述表；•调用NtCreateThread创建执行体线程对象。包括：增加进程中的线程计数，创建并初始化执行体线程块，生成新线程ID，从非页交换区分配线程的内核堆栈，设置线程环境块TEB，设置线程起始地址和用户指定的WIN32起始地址，设置KTHREAD块，设置指向进程访问令牌的指针和创建时间；•通知WIN32子系统已创建新线程，以便设置新的进程和线程；•置新线程为准备态，把其句柄和ID返回到调用进程；调用ResumeThread，线程将被激活并调度执行。Windows进程和线程状态

资源可用事件完成但资源不可用事件完成资源可用阻塞挂起终止可运行不可运行选中切换抢占或时间片到Running运行态Ready就绪态Standby准备态Terminated中止态Waiting等待态Transition过渡态2.7处理机调度

2.7.1处理机调度的层次2.7.2选择调度算法的原则

2.7.1处理机调度的层次

作业从进入系统成为后备作业开始，直到运行结束退出系统为止，需经历不同级别的调度。•高级调度•中级调度•低级调度处理器三级调度模型处理器低级调度高级调度完成超时挂起就绪队列挂起等待队列等待队列就绪队列等待事件交互式用户事件出现后备作业队列中级调度处理器两级调度模型等待事件事件发生进程完成后备作业队列

就绪队列高级调度低级调度等待队列CPU时间片完2.7.2选择调度算法的原则(1)

l

资源利用率CPU利用率=CPU有效工作时间/CPU总的运行时间，CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间。选择调度算法的原则(2)

2

响应时间•交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。•使交互式用户的响应时间尽可能短，或尽快处理实时任务。•这是分时系统和实时系统衡量调度性能的一个重要指标。选择调度算法的原则(3)

3周转时间•批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间尽可能短。•这是批处理系统衡量调度性能的一个重要指标。

选择调度算法的原则(4)

4吞吐率单位时间内处理的作业数。5公平性确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死情况。

作业周转与平均周转时间如果作业i提交给系统的时刻是ts，完成时刻是tf，该作业的周转时间ti为：ti=tf-ts

实际上，它是作业在系统里的等待时间与运行时间之和。为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。平均作业周转时间T=(Σti)/n作业带权周转时间和平均

作业带权周转时间如果作业i的周转时间为ti，所需运行时间为tk，则称wi=ti/tk为该作业的带权周转时间。ti是等待时间与运行时间之和，故带权周转时间总大于1。平均作业带权周转时间W=(Σwi)/n2.8作业的管理与调度

2.8.1作业和进程的关系2.8.2作业的组织、调度和控制2.8.1作业和进程的关系

•作业(JOB)，•作业步(JobStep)，•作业组织，•作业的提交、收容、执行和完成。作业是任务实体，进程是完成任务的执行实体;没有作业任务，进程无事可干，没有进程，作业任务没法完成。作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。2.8.2作业的组织、调度和控制

1批作业的组织和管理1)批作业的输入

2)批作业的建立作业控制语言，作业说明书，

作业控制块多道批处理操作系统具有独立的作业管理模块，必须像进程管理一样为每一个作业建立作业控制块（JCB）。JCB通常是在批作业进入系统时，由Spooling系统建立的，它是作业存在于系统的标志，作业撤离时，JCB也被撤销。

JCB的主要内容包括：(1)作业情况(2)资源需求(3)资源使用情况作业生命周期状态输入状态：后备状态：执行状态：完成状态：3)批作业的调度(1)选择作业：(2)分配资源：(3)创建进程：(4)作业控制：(5)后续处理：作业调度与进程调度的关系

进程调度运行就绪等待输入状态后备状态完成状态预输入完成作业控制作业调度(选中并创建进程)作业调度(作业终止并撤离)SPOOLing作业预输入SPOOLing作业缓输出2交互作业的组织和管理分时系统的作业就是用户的一次上机交互过程，可认为终端进程的创建是一个交互型作业的开始，退出命令运行结束代表用户交互型作业的中止。交互作业的情况和资源需求通过操作命令告知系统，分时用户逐条输入命令，即提交作业（步）和控制作业运行，系统则逐条执行并给出应答，每键入一条或一组有关操作命令，便在系统内部创建一个进程或若干进程来完成相应命令。键盘命令有：作业控制类；资源申请类；文件操作类；目录操作类；设备控制类等。2.9处理器调度算法2.9.1低级调度的功能和类型2.9.2作业调度和低级调度算法2.9.3实时调度算法2.9.4多处理机调度算法

2.9.1低级调度的功能和类型1低级调度的主要功能调度程序两项任务：调度和分派。调度实现调度策略，确定就绪进程/线程竞争使用处理器的次序的裁决原则，即进程/线程何时应放弃CPU和选择哪个来执行；分派实现调度机制，确定如何时分复用CPU，处理上下文交换细节，完成进程/线程和CPU的绑定和放弃的实际工作。调度机制逻辑功能程序模块组成队列管理程序：上下文切换程序：分派程序：2低级调度的基本类型第一类称剥夺式：两种处理器剥夺原则，一是高优先级进程/线程可剥夺低优先级进程/线程，二是当运行进程/线程时间片用完后被剥夺。第二类称非剥夺式：

2.9.2作业调度和低级调度算法1先来先服务算法三个作业同时到达系统并立即进入调度：作业名/所需CPU时间:作业1/28，作业2/9，作业3/3。采用FCFS算法，平均作业周转时间为35。•若三个作业提交顺序改为作业2、1、3，平均作业周转时间约为29。若三个作业提交顺序改为作业3、2、1，平均作业周转时间约为18。FCFS调度算法的平均作业周转时间与作业提交的顺序有关。2

最短作业优先算法(1)

SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。算法易于实现，效率不高，主要弱点是忽视了作业等待时间。会出现饥饿现象。SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好。实现SJF调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时间是办不到的。最短作业优先算法(2)

四个作业同时到达系统并进入调度：作业名/所需CPU时间:作业1/9，作业2，作业3/10，作业4/8。SJF作业调度顺序为作业2、4、1、3，平均作业周转时间T=17，平均带权作业周转时间W=1.98。如果施行FCFS调度算法，平均作业周转时间T=19，平均带权作业周转时间W=2.61。3最短剩余时间优先算法(1)SRTF把SJF算法改为抢占式的。一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业。称最短剩余时间优先算法此算法不但适用于JOB调度，同样也适用于进程调度。最短剩余时间优先算法(2)四个作业其到达系统/所需CPU时间如下：Job1-0/8，Job2-1/4，Job3-2/9，Job4-3/5。SRTF调度平均等待时间=6.5毫秒。SJF调度平均等待时间=7.75毫秒。

J1J2J4J1J30151017264响应比最高者优先算法

FCFS与SJF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时问，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间。HRRF是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。

响应比定义响应比＝1+已等待时间/估计运行时间•短作业容易得到较高响应比，•长作业等待时间足够长后，也将获得足够高的响应比，•饥饿现象不会发生。HRRF算法举例

四个作业到达系统时间/所需CPU时间:作业1-0/20，作业2-5/15，作业3-10/5，作业4-15/10。SJF调度顺序为作业1、3、4、2，平均作业周转时间T=25，平均带权作业周转时间W=2.25。FCFS调度顺序为作业1、3、4、2，平均作业周转时间T=28.75，平均带权作业周转时间W=3.125。HRRF调度顺序为作业1、3、4、2，平均作业周转时间T=26.25，平均带权作业周转时间W=2.46。5优先级调度算法(1)

静态优先数法使用外围设备频繁者优先数大，这样有利于提高效率；重要算题程序的进程优先数大，这样有利于用户；进入计算机时间长的进程优先数大，这样有利于缩短作业完成的时间；交互式用户的进程优先数大，这样有利于终端用户的响应时间等等,

优先权调度算法(2)

动态优先数法①根据进程占有CPU时间多少来决定,当进程占有CPU时间愈长,那么，在它被阻塞之后再次获得调度的优先级就越低，反之,进程获得调度的可能性越大;②根据进程等待CPU时间多少来决定,当进程在就绪队列中等待时间愈长,那么，在它被阻塞之后再次获得调度的优先级就越高，反之,进程获得调度的可能性越小。6

时间片轮转调度算法时间片调度做法是：调度程序每次把CPU分配给就绪队列首进程使用一个时间片，例如100ms，就绪队列中的每个进程轮流地运行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度轮转策略可防止那些很少使用外围设备的进程过长的占用处理器而使得要使用外围设备的那些进程没有机会去启动外围设备轮转策略与间隔时钟7

多级反馈队列调度

又称反馈循环队列或多队列策略。主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。一个三级反馈队列调度策略

低级就绪队列高级就绪队列中级就绪队列等待磁盘磁带等待其他外设运行选中,时间片500ms超过时间片启动磁盘磁带启动其他外设选中,时间片200ms选中,时间片100ms8彩票调度算法

基本思想：为进程发放针对各种资源（如CPU时间）的彩票。调度程序随机选择一张彩票，持有该彩票的进程获得系统资源。进程都是平等的，有相同的运行机会。如果某些进程需要更多的机会，可被给予更多彩票，增加其中奖机会。2.9.3实时调度算法

实时系统是那些时间因素非常关键的系统。实时系统包括监控系统、自动驾驶系统、安全控制系统等，这些系统中，迟到的响应即使正确，也和没有响应一样糟糕。硬实时系统和软实时系统实时系统通常分为硬实时系统和软实时系统。前者意味着存在必须满足的时间限制；后者意味着偶尔超过时间限制时可以容忍的。

周期性和非周期性事件实时系统响应的事件可划分为周期性事件和非周期性事件。例如，m个周期性事件，事件i的周期为Pi，每个事件需要Ci秒的CPU时间来处理，则只有满足以下条件：

C1/P1+C2/P2+…+Cm/Pm≤1

时，才可能处理所有的负载。满足该条件的实时系统称作任务可调度的。

实时调度算法(1)

1）单比率调度算法基本思想：为每个进程分配一个与事件发生频率成正比的优先数。例如，周期为20ms的进程优先数为50，周期为100ms的进程优先数为10，运行时调度程序总是调度优先数最高的就绪进程，并采取抢占式分配策略。实时调度算法(2)

2）限期调度算法

基本思想：当一个事件发生时，对应的进程就按照截止期限被加入就绪进程队列。对于一个周期性事件，其截止期限即为事件下一次发生的时间。该调度算法首先运行队首进程，即截止时间最近的那个进程。实时调度算法(3)

3）最少裕度法

基本思想：首先计算各个进程的富裕时间，即裕度（laxity），然后选择裕度最少的进程执行。裕度=截止时间-(就绪时间+计算时间)2.9.4多处理器调度

1多处理机调度的设计要点1)如何为进程分配处理机、2)在单个处理机上是否使用多道程序设计技术3)如何实际指派进程，多处理器调度算法(1)

1）负载共享调度算法

基本思想：进程并不指派到特定处理机上，系统维护全局性进程就绪队列，当处理机空闲时，就选择进程的一个线程去运行。多处理器调度算法(2)2）群调度算法

基本思想：一群相关线程基于一对一的原则，被同时调度到一组处理机上运行。它具有的优点：•当紧密相关的进程同时执行时，同步造成的等待将减少，进程切换也相应减少，系统性能得到提高。•由于一次性同时调度一组处理器，调度的代价也将减少。多处理器调度算法(3)

3）处理器专派调度算法基本思想：给同属一个进程的一组线程，同时分派到一组处理机上运行，每个线程获得一个处理机，且它专用于处理这个线程，直到进程运行结束，这是群调度的一种极端形式。采用这一算法，处理器将不适用多道程序设计，即该应用的一个线程阻塞后，线程对应的处理器不会被调度给其他线程，而处于空闲状态。多处理器调度算法(4)

4）动态调度算法(1)

基本思想：由操作系统和应用进程共同完成调度。操作系统负责在应用进程之间划分处理器。应用进程在分配给它的处理器上执行可运行线程的子集，哪一些线程应该执行，哪一些线程应该挂起完全是应用进程自己的事。多处理器调度算法(5)

动态调度算法(2)

•

如果有空闲处理器，满足要求。否则，对新到达进程，从当前分配了一个以上处理器的进程中收回一个，并把它分给新到达进程。•如果要求不能被满足，则保留申请直到出现可用处理器或要求取消。•释放了一个或多个处理器后，扫描申请处理器的进程队列，按照FCFS原则把处理器逐一分配给每个申请进程直到没有可用处理器。2.10Linux调度算法

2.10.1Linux传统调度算法2.10.2Linux2.6调度算法2.10.1Linux传统调度算法(1)

1进程调度策略

1)policy：

SCHED_OTHER普通类任务SCHED_FIFO先进先出实时类任务SCHED_RR轮转法实时类任务

2)priority进程静态优先级

3)nice进程可控优先级因子4)rt_priority实时进程静态优先级

5)counter进程目前时间片配额，也称进程动态优先级Linux传统调度算法(2)

2动态优先级的产生和变化当counter递减到0时，运行进程被迫出让CPU；当可运行队列中所有进程的counter值变为0后，表明一轮调度已经结束。等待态进程的动态优先级通常会逐渐增加，当所有可运行进程的counter都为0时，系统重新计算所有进程的counter，计算公式为：p->counter=(p->counter>>1)+NICE_TO_TICKS(P->nice)

对于就绪态进程来说，因其counter都为0，计算结果就是nice转换过来的时钟滴答数；对于等待态进程就不一样，它们的counter都不为0，计算结束后，等待态进程的动态优先级会大于nice值。3Linux进程调度机制进程调度依据和时机进程调度任务进程切换

进程切换时机

(1)进程被动地放弃CPU，当前进程时间片用完或当一个进程被唤醒，且其优先级高于当前进程的优先级时，通过TIF_NEED_RESCHED位置1，来告诉内核在适当的时刻需要重新调度。(2)进程主动放弃CPU，是由于进程执行系统调用，状态发生变化，直接调用schedule()进入调度，这类系统调用有：yield()、pause()、sleep()、wait()和exit()。(3)进程执行等待系统调用，如read()或write()等，此时进程进入等待队列，系统调用schedule()进入调度，该函数的执行结果往往是当前进程放弃处理器。进程切换

上下文切换是从一个可运行进程切换到另一个可运行进程，由context_switch（）函数处理这项工作，每当一个新的进程被选出来准备投入运行时，schedule（）就会调用该函数。它首先调用switch_mm（），把虚拟主存从上一个进程映射切换到新进程中；再调用switch_to（），从上一个进程的处理器状态切换到新进程的处理器状态。2.10.2Linux2.6调度算法0（1）调度程序--特点是能够保证无论系统负载(进程数目或处理器数目)如何增加，选择合适进程并且给它分配处理器的时间是恒定的，具有的新特性有：支持SMP，每个处理器拥有自己的可运行队列；强化SMP的亲和力，尽量将相关任务分配到一个处理器上连续运行；确保响应时间，及时调度交互式进程；保证公平性，没有进程会处于饥饿状态。Linux2.6中，进程描述符task_struct含有与调度有关的成员(1)

1)policy-进程调度策略，有三种类型：·SCHED_NORMAL非实时进程；·SCHED_FIFO实时进程，采用先进先出的调度算法；·SCHED_RR实时进程，采用轮转法。

Linux2.6中，进程描述符task_struct含有与调度有关的成员(2)

2)rt_priority-实时进程的优先级。其值为1000+rt_priority，而MAX_RT_PRIO定义为100，故rt_priority范围为0至99，且不参与优先级计算；3)static_prio-非实时进程静态优先级。由nice值转换而来，公式为：static_prio=MAX_RT_PRIO+nice-20。Linux2.6中，进程描述符task_struct含有与调度有关的成员(3)

4)sleep_avg-进程平均等待时间。相当于进程等待时间与运行时间的差值，既反映该进程的交互程度，又表示进程需要运行的紧迫程度，该值越大，进程的优先级就越高；5)prio-进程动态优先级。在进程运行过程中动态计算，主要影响因素为sleep_avg。创建时子进程继承父进程的动态优先级、唤醒等待进程时对它进行优先级修正、时钟中断中重新计算进程优先级并进入相应队列、负载平衡/修改nice值/修改调度策略（setscheduler（））都有可能改变进程动态优先级；Linux2.6中，进程描述符task_struct含有与调度有关的成员(4)

6)prio_array_t*array-进程优先级数组。以进程优先级为序号排列；7)time_slice-进程时间片余额。进程默认时间片与static_prio有关，内核将100至139的优先级映射列800ms至5ms的时间片区间；创建进程时，子、父进程平分父进程的剩余时间片。终止进程时，若子进程如果从未重新分配过时间片，则把剩余时间片归还给父进程；Linux2.6中，进程描述符task_struct含有与调度有关的成员(5)

8)load_weight;-平衡负载用的权重。解决可运行队列出现的负载不均现象；9)CONFIG_PREEMPT-内核可剥夺编译选项，当该开关开启时，v2.6内核将会在更多内核安全点上检测TIF_NEED_RESCHED位，从而让刚被唤醒的高优先级任务减少延迟而尽快获得处理器运行。关于need_resched每个进程都包含need_resched标志，这是因为通过current宏访问进程描述符内的数值要比访问全局变量快，在v2.2以前内核版本中，该标志曾经是一个全局变量；v2.2到v2.4版内核中它放在进程的task_struct中；v2.6版中，它被移到thread_info结构体里，用特别的标志变量中的一位TIF_NEED_RESCHED来表示。1调度算法的数据结构调度程序中最主要的数据结构是可运行队列(runqueue)，它是给定处理器上的就绪进程链表，每个处理器一个，每个就绪进程都归属于一个可运行队列。它还包含每个处理器的调度信息，所以也是处理器的重要数据结构。可运行队列(处理器)的优先级数组一个是活跃的、一个是过期的。structprio_array{intnr_active;//数组中的进程数unsignedlongbitmap[BITMAP_SIZE];