第2章处理器管理(201409)

1、高等教育出版社出版2014年1月第二章 处理器管理2.1 处理器状态 2.2 中断技术2.3 进程及其实现2.4 线程及其实现2.5 Linux进程2.6 处理器调度2.7 Linux调度算法2.1.1处理器2.1.2程序状态字l计算机系统的处理器包括一组寄存器，其个数根据机型的不同而不同，它们构成了一级存储，比主存容量小 ，但访问速度快。l这组寄存器所存储的信息与程序的执行有很大关系，构成了处理器现场。 l通用寄存器- EAX，EBX，ECX和EDXl指针及变址寄存器-ESP，EBP，ESI及EDIl段选择符寄存器-CS、DS、SS、ES 、FS、GS l指令指针寄存器和标志寄存器-EIP、

2、EFLAGSl控制寄存器-CR0，CR1，CR2和CR3 l外部设备使用的寄存器EAXEBXECXEDXAXBXCXDXESPEBPESIEDISPBPSIDICSDSSSESFSGSIPEFLAGSCR0CR1CR2 CR32. 特权指令与非特权指令(1) 机器指令的集合称指令系统 (1)数据处理类指令； (2)转移类指令； (3)数据传送类指令； (4)移位与字符串指令； (5)I/O类指令。l从资源管理和控制程序执行的角度出发，把指令系统中的指令分作两部分：特权指令和非特权指令。l特权指令是指只能提供给操作系统的核心程序使用的指令，如启动I/O设备、设置时钟、控制中断屏蔽位、清主存、建立

3、存储键，加载PSW等。3. 内核态和用户态 处理器怎么知道当前是操作系统还是一般用户程序在运行呢? 处理器状态标志: 管理状态（核心状态、特态或管态）和用户状态（目标状态、常态或目态)。处理器状态的转换。 处理器处于管理状态时，程序可以执行全部指令，使用所有资源，具有改变处只能执行非特权指令。 Intel x86的处理器状态有四理器状态的能力；处理器处于用户状态时，程序种，支持4个保护级别，0级权限最高，3级权限最低。 l导致处理器从用户态向内核态转换，一是程序请求操作系统服务，执行系统调用；二是程序运行时，产生中断或异常事件，运行程序被中断，转向中断处理或异常处理程序工作。l两类情况都通过中

4、断机制发生，中断和异常是用户态到内核态转换仅有的途径。l从内核态转向用户态，计算机提供一条特权指令称作加载程序状态字(Intel x86为iret指令)，用来实现从系统(核心态)返回到用户态，控制权交给应用进程。 (1) 用户栈 (2) 核心栈 (3) 栈指针2.1.2 程序状态字(1) 计算机如何知道当前处于何种工作状态？这时能否执行特权指令？通常操作系统都引入程序状态字PSW（Program Status Word）来区别不同的处理器工作状态。 PSW用来控制指令执行顺序并保留和指示与程序有关的系统状态，主要作用是实现程序状态的保护和恢复。 每个程序都有一个与其执行相关的PSW，每个处理器

5、都设置一个PSW寄存器。程序占有处理器执行，它的PSW将占有PSW寄存器。 程序状态字寄存器(2) PSW寄存器包括以下内容： 程序基本状态： (1) 程序计数器； (2) 条件码； (3）处理器状态位。 中断码。保存程序执行时当前发生的中断事件。 中断屏蔽位。指明程序执行中发生中断事件时，是否响应出现的中断事件。 lIntel x86中，PSW由标志寄存器EFLAGS和指令指针寄存器EIP组成，均为32位。lEFLAGS的低16位称FLAGS，标志可划分为三组：状态标志、控制标志、系统标志。2.2.1 中断概念2.2.2 中断源分类2.2.3 中断和异常的响应及服务2.2.4 中断事件处理原

6、则2.2.5 中断优先级和多重中断2.2.6 Linux中断处理 请求系统服务， 实现并行工作， 处理突发事件， 满足实时要求， 都需要打断处理器正常的工作，为此，提出了中断概念。 中断是指程序执行过程中，遇到急需处理的事件时，暂时中止CPU上现行程序的运行，转去执行相应的事件处理程序，待处理完成后再返回原程序被中断处或调度其他程序执行的过程。 外中断(中断或异步中断)-是指来自处理器之外的中断信号，包括时钟中断、键盘中断和设备中断等；外中断又分可屏蔽中断和不可屏蔽中断，每个不同中断具有不同的中断优先级，表示事件的紧急程度，在处理高一级中断时，往往会屏蔽部分或全部低级中断。 内中断(异常或同步

7、中断)-是指来自处理器内部，通常由于程序执行中，发现与当前指令关联的、不正常的、或是错误的事件。 (1)中断是由与现行指令无关的中断信号触发的(异步的)，且中断的发生与CPU处在用户模式或内核模式无关，在两条机器指令之间才可响应中断，一般来说，中断处理程序提供的服务不是为当前进程所需的； 异常是由处理器正在执行现行指令而引起的，一条指令执行期间允许响应异常，异常处理程序提供的服务是为当前进程所用的。异常包括很多方面，有出错(fault)，也有陷入(trap)等。 l（2）要求“中断”被快速处理，以便及时响应其它中断信号，所以，中断处理程序处理过程中是不能阻塞的。“异常”处于被打断的当前进程上下

8、文中，所提供的服务是当前进程所需要的，所以，异常处理程序处理过程中是可以阻塞的。l（3）中断允许发生嵌套，但异常大多为一重；异常处理过程中可能会产生中断，但中断处理过程中决不会被异常打断。 l发现中断源：l保护现场：l转向处理中断/异常事件的处理程序：l恢复现场。IPCSPSW现行PSW寄存器新IP新CS老IP老CS老PSW新栈顶 内存新PSW2.2.4 中断事件处理原则1 . 硬件故障中断2. 程序性中断3. I/O中断4. 访管中断5. 时钟中断 5时钟中断(1) 时钟是操作系统进行调度工作的重要工具，如让分时进程作时间片轮转、让实时进程定时发出或接收控制信号、系统定时唤醒或阻塞一个进程、

9、对用户进程进行记账 时钟可分成绝对时钟和间隔时钟两种 Linux系统运行不同的间隔定时器，类型有三种：lreal 间隔定时器-按实际经过时间计时，不管进程处在何种模式下运行，包括进程被挂起时，计时总在进行，定时到达时发送给进程一个SIGALRM信号。lvirtual 间隔定时器-进程在用户态下执行时才计时，定时到达时发送给进程一个SIGVTALRM信号。lprofile 间隔定时器-进程执行在用户态或核心态时都计时，当定时到达时发送给进程一个SIGROF信号。 2.2.5 中断优先级和多重中断1. 中断优先级2. 中断屏蔽3. 多重中断事件的处理 计算机执行的每一瞬间，可能有几个中断事件同时发

10、生，中断装置如何来响应同时发生的中断呢? 以不发生中断丢失为前提，把紧迫程度相当的中断源归在同一级，紧迫程度差别大的中断源归在不同级， 级别高的有优先获得响应的权力，中断装置预定的这个响应顺序称为中断优先级。 1. 中断优先级2. 中断屏蔽 可编程中断控制器，可通过指令设置屏蔽码。中断屏蔽是指禁止CPU响应中断或禁止中断产生。 前者指硬件产生中断请求后，CPU暂时不予响应的状态。后者指可引起中断的事件发生时，硬件不允许提出中断请求也不通知处理器，故不可能导致中断。中断屏蔽的作用 一、是延迟或禁止某些中断的响应。系统程序执行过程中，不希望产生干扰事件，以免共享数据结构受到破坏。程序运行过程中产生

11、某些事件认为是正常的，不必加以处理。 二、是协调中断响应与中断处理的关系。确保高优先级中断可以打断低优先级中断，反之却不能。 三、是防止同级中断相互干扰。在处理某优先级中断事件时，必须屏蔽该级中断，以免造成混乱。 中断正在进行处理期间，CPU又响应新的中断事件，于是暂时停止正在运行的中断处理程序，转去执行新的中断处理程序，就叫多重中断（又称中多重中断（又称中断嵌套）断嵌套）。处理方法： (1) 串行处理， (2) 嵌套处理， (3) 即时处理。 用户态快中断慢中断异常中断用户态核心态 上半部分处理 排队下半部分快中断处理 系统调用处理 从系统调用返回ret_from_sys_call( )调用

12、schedule( )调度被中断进程或新进程运行调度下半部分do_softirq( )处理积累信号do_signal( )恢复保存的部分寄存器中断保存部分寄存器保存全部寄存器 ret_from_intr( )进程运行检查TIF_NEED_RESCHED标志Linux内核处理流程lIntel x86机器支持256种中断信号，从0到255编号组成“中断向量”。l中断信号源分2类：中断和异常。中断分为屏蔽中断和非屏蔽中断；异常分为故障（fault）、陷阱（trap）、终止（abort）和编程异常 （programmed exception。l非屏蔽中断和异常的向量是固定的，而屏蔽中断的向量可通过对中

13、断控制器编程加以改变。l256个中断向量分配如下： 1)031的向量对应于异常和非屏蔽中断； 2)3247的向量对应于屏蔽中断，被外部设备使用； 3)48255的向量分配给软中断，Linux仅用1个，128号、即0 x80，实现系统调用。l在Linux系统中，每个能发送中断信号的硬件设备控制器都有一根输出线，它与中断控制器8259A的输入引脚相连，若一个硬件设备欲向CPU发送中断信号，必须申请一条可用的“中断请求线”，或者说必须申请一个IRQ号，这就是“中断请求”IRQ（Interrupt Requirement）。lIRQ号与中断向量号的对应关系。INTAINTRCPUIRQ15IRQ14I

14、RQ13IRQ12IRQ11IRQ10IRQ9IR0 INTAIR1 INTIR2IR3 IR4IR5IR6IR7IRQ8IRQ4IRQ6IRQ5IRQ1IRQ0IRQ7IRQ3IR0 INTAIR1 INTIR2IR3IR4IR5IR6IR78259A主片8259A从片IRQ2Linux系统要处理3种门机制：1)中断门(interrupt gate)-用于关中断的中断或异常处理；2)陷阱门(trap gate)-用于开中断的异常处理；3)系统门(system gate)。用于系统调用。l中断描述符表（Interrupt Descriptor Table，IDT）包含 个表项，每个中断异常都对

15、应一个，每个表项称为一个门描述符(gate descriptor)，作用是把程序控制权转交给中断异常处理程序。中断描述符表IDTIDTR IDT表基址 IDT表长度中断门描述符255中断门描述符254.中断门描述符3中断门描述符2中断门描述符1 IDT和IDTRl1) 中断处理程序和中断服务例程l硬件15条中断线对应15个中断处理程序，编号为：IRQ0 x00_interrupt( )、IRQ0 x01_interrupt( )、。l例如，IRQ0 x05_interrupt( )是IRQ号为5(中断向量号为37)的中断处理程序，若5号中断被网卡和图形卡共享，则2种卡各有中断服务例程。l区别中

16、断处理程序和中断服务例程(Interrupt Service Routine，ISR）。 lLinux系统为每个中断请求IRQ设置一个队列-“中断请求队列”l中断线共享的数据结构为irqaction，该结构I/O设备中断服务例程是handler。l每个中断服务队列开始为空，具体的中断服务例程在设备驱动程序初始化时，必须调用函数request_irq( )挂入，也就是进行注册。卸载设备驱动程序时，调用函数free_irq( )释放中断线，并注销中断服务例程。l(1)中断信号由外部设备发送到中断控制器，IRQ号转换成中断向量号I传送给CPU。l(2)CPU响应和接收中断，根据中断向量号I查找IDT

17、表，找到门描述符，也就找到了对应的IRQ0 x0n_interrupt( )中断处理程序入口地址。l跳转到common_interrupt代码执行，其做的工作有：中断向量号入栈，利用宏SAVE_ALL保护寄存器到核心栈。然后，调用do_IRQ( )函数。l (3) do_IRQ( )函数对中断进行应答，禁止该中断线，确保该中断线上有有效中断服务例程。在关中断条件下，do_IRQ( )调用handle_IRQ_event( ) 函数来执行注册到该中断线上的所有中断服务例程。l (4) 返回至内核 ret_from_sys_call ( )代码来完成一组标准任务，如调用do_softirq( )

18、函数处理软中断。调用do_signal( ) 函数处理信号。处理结束后跳转到ret_from_intr( )退出中断，使用宏RESTORE_ALL恢复现场，完成整个中断处理，彻底从中断返回。是(中断向量号I)否中 断 线 上 有中 断 处 理 例程?do_IRQ( )中 断 处 理 程 序IRQ0 x0n_interrupt( )产生中断(IRQ号)设备中断控制器处理器ret_from_intr( )从中断返回内核代码中断服务例程执行程序Handle_IRQ_event( )执行中断线上所有中断服务例程?l异常产生后，转向异常处理程序公共入口执行，执行下列操作：l1)将硬件错误码和异常向量号存

19、入当前进程PCB中；l2)判别异常产生于核心态还是用户态，对于前者，转向内核预定义服务程序处理，没有被处理的核心态异常是操作系统的致命错误；l3)对于用户态异常，终止当前进程运行，调用force_sig( )函数给当前进程发信号；l4)从ret_from_exception处返回用户空间时，检查进程是否有信号等待处理，如果有则根据信号类型调用相应函数进行处理。l中断处理程序的特点l什么是下半部分处理?lTop halflBottom halfl以异步方式运行，可能会打断关键代码的执行，甚至打断其他中断处理程序的执行；l在屏蔽中断状态下运行，最坏的情况会禁止所有中断；l要对硬件进行操作，有很高的

20、时限要求；它在中断上下文中运行，故不能被阻塞 。ltasklet、lwork queue、lSoftirq。ltasklet能更好支持SMP，它基于软中断来实现，但比软中断接口简单，锁保护要求低；softirq保留给执行频率及时间要求特高的下半部分使用(如网络和SCSI)，多数场合下可使用tasklet。l使用tasklet的步骤：声明tasklet 、编程tasklet、调度tasklet 。 lBH全局串行处理，不适应SMP环境，而不同tasklet可同时运行于不同CPU上，当然，系统保证相同tasklet不会同时在不同CPU上运行，在这种情形下，tasklet就不需要是可重入的。l在新版

21、Linux中，tasklet是建议的异步任务延迟执行机制。lLinux 2.5内核引入-工作队列，它把一个任务延迟，并交给内核线程去完成，且该任务总是在进程上下文中执行，通过工作队列执行的代码能占尽进程上下文的优势，最重要的是工作队列允许重新调度及阻塞。l如果延迟执行的任务需要阻塞，需要获取信号量或需要获得大量主存时，那么，可选择工作队列，否则可使用tasklet或softirq。lLinux沿用最早BH思想，实现了庞大和复杂的软中断子系统-softirq，它是一种软中断机制，又是一个框架，包括tasklet，及为网络操作专门设计的软中断。l软中断结构： struct softirq_acti

22、on void (*action)(struct softirq_action *); /待执行的函数 void *data; /传给函数的参数 l;l最多注册32个软中断，目前预定义六个元素， enum HI_SOFTIRQ, /高优先级tasklet TIMER_SOFTIRQ /定时器下半部分 NET_TX_SOFTIRQ, /发送网络数据包 NET_RX_SOFTIRQ, /接收网络数据包 SCSI_SOFTIRQ, /SCSI下半部分 TASKLET_SOFTIRQ, /公共tasklet ;l软中断使用步骤：声明softirq 、注册softirq 、触发softirq 、处理so

23、ftirq 。l软中断执行时机 ：1)在处理完硬件中断后；2)在 ksoftirqd 内核线程中；3)在显式检查和执行待处理的软中断的代码中。2.3.1 进程定义和属性2.3.2 进程状态和转换2.3.3 进程描述和组成2.3.4 进程上下文切换与处理器状态转换2.3.5 进程控制和管理程序的并发执行：程序的并发执行： P1P2P3P4I1I2I3I4C1C2C3C4程序的并发执行：程序的并发执行： 四条语句的前趋关系四条语句的前趋关系S1S2S3S4对于具有下述四条语句的程序段：对于具有下述四条语句的程序段：程序程序A A：每执行一次时，都要做：每执行一次时，都要做N=N+1N=N+1操作；

24、操作；程序程序B B：每执行一次时，：每执行一次时， 都要执行都要执行Print(N)Print(N)操作，然后再将操作，然后再将N N置成置成“0 0”。 (1) N=N+1(1) N=N+1在在Print(N)Print(N)和和N=0N=0之前，此时得到的之前，此时得到的N N值分别为值分别为n+1, n+1, n+1, n+1, 0 0。 (2) N=N+1(2) N=N+1在在Print(N)Print(N)和和N=0N=0之后，此时得到的之后，此时得到的N N值分别为值分别为n, 0, 1n, 0, 1。 (3) N=N+1(3) N=N+1在在Print(N)Print(N)和和

25、N=0N=0之间，此时得到的之间，此时得到的N N值分别为值分别为n, n+1, 0n, n+1, 0。 程序的并发执行时的特征：程序的并发执行时的特征： 举例：举例： 进程定义： 进程是可并发执行的程序在某个数据集合上的一次计算活动，也是操作系统进行资源分配和保护的基本单位。 进程是一个既能用来共享资源，又能描述程序并发执行过程的系统基本单位。 进程是一种支持程序执行的系统机制。l原因1-刻画程序的并发性。l程序是并发执行的，即不是连续而是走走停停的。程序的并发执行引起资源共享和竞争问题，执行的程序不再处在封闭环境中。l“程序”自身只是计算任务的指令和数据的描述，是静态概念无法刻画程序的并发

26、特性，系统需要寻找一个能描述程序动态执行过程的概念，这就是进程。l原因2-解决资源的共享性。l “可再用” 程序； “可再入” 程序； “可再入”程序具有的性质。 运行态就绪态等待态被调度运行时间片用完出现等待事件等待事件结束运行态就绪态等待态选中落选出现等待事件等待事件结束新建态终止态 进程为什么要有“挂起”状态? 为了让某些进程暂时不参与低级调度，释放它占有的资源，以平滑系统负荷的目的而需引入挂起态； 进程挂起的原因 ? 引起进程挂起的原因多种多样。 挂起等待事件结束出现等待事件解除挂起挂起落选选中运行态就绪态等待事件结束终止态新建态挂起就绪态解除挂起挂起挂起等待态等待态提交提交 该进程不

27、能立即被执行。 挂起进程可能会等待事件，但所等待事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件。 进程进入挂起状态是由于操作系统、父进程或进程本身阻止它的运行。 结束进程挂起状态的命令只能通过操作系统或父进程发出。2.3.3 进程描述和组成(1) 1.进程映象 进程控制块 进程程序块 进程核心栈 进程数据块 进程描述和组成(2) 操作系统中把进程物理实体和支持进程运行的环境合称为进程上下文。 当系统调度新进程占有处理器时，新老进程随之发生上下文切换。进程的运行被认为是在上下文中执行。 进程描述和组成(3)进程上下文组成用户级上下文：系统级上下文：寄存器上下文：进程描述和组成(4)L

28、inux进程上下文组成 Linux系统用户级上下文包括：text、data、shared memory和user stack等。 Linux系统寄存器上下文包括：general register、pragram counter、EFLAGS、ESP等。 Linux系统系统级上下文包括：t a s k _ s t r u c t 、 m m _ s t r u c t 、vm_area_struct、pgd、pmd、pte和kernel stack等。l进程控制块P C B ，是操作系统用于记录和刻划进程状态及有关信息的数据结构。也是操作系统掌握进程的唯一资料结构，它包括进程执行时的情况，以及进

29、程让出处理器后所处的状态、断点等信息。 l进程控制块包含三类信息 标识信息 现场信息 控制信息l处于同一状态的所有PCB链接在一起的数据结构称为进程队列。 l同一状态进程的PCB既可按先来先到的原则排成队列;也可按优先数或其它原则排队。l通用队列组织方式： 线性方式、 链接方式 索引方式。l进程入队和出队 PCB表 PCB1 0PCB2 5PCB3 0PCB4 0 PCB5 0PCB6 4运行队列指针 就绪队列指针 等待队列1指针 等待队列2指针 PCBn 7 PCB7 0 空闲进程队列指针 链接方式运行队列指针 就绪表指针 等待表1指针 索引方式 PCB表 PCB1 PCB2 PCB3 PC

30、B4 PCB5 PCB6 PCBn 空闲表指针 就绪索引表 等待索引表1 等待表2指针2.3.4 进程上下文切换与处理器状态转换 进程切换是让处于运行态的进程中断运行，让出处理器，这时要做一次进程上下文切换、即保存老进程的上下文而装入被保护了的新进程的上下文，以便新进程运行。进程上下文切换的步骤 保存被中断进程的处理器现场信息 修改被中断进程的进程控制块有关信息，如进程状态等 把被中断进程的PSW加入有关队列 选择下一个占有处理器运行的进程 修改被选中进程的PSW的有关信息 根据被选中进程设置操作系统用到的地址转换和存储保护信息 根据被选中进程恢复处理器现场 请求调度的事件发生后，就会运行低级

31、调度程序，低级调度程序选中新的就绪进程后，就会进行上下文切换。实际上，由于种种原因，调度和切换并不一定能一气呵成。 通常的做法是，由内核置上请求调度标志，延迟到上述工作完成后再进行调度和进程上下文切换， Linux进程调度标志位need-resched。 V.版中，被移至thread_info 结构体中，用标志TIF_NEED_RESCHED 表示 。Linux调度时机(1) (1)主动调度:指调用schedule( )函数来释放CPU,引起新一轮调度，通常发生在当前进程状态被改变,如:执行了read（）、write( )、exit（ ）等系统调用，导致进程终止、进程阻塞等。Linux调度时机

32、(2) (2)被动调度:指发生了引起调度的条件, 这时仅置进程TIF_NEED_RESCHED调度标志。调度标志设置有以下情况： 1) 时钟中断中调用函数scheduler_tick()，查看当前进程的时间片是否耗尽，如果是，则设置重调度标志； 2) 函数try_to_wake_up( )将阻塞的进程被唤醒，把它加入运行队列时，如果其优先级比当前正在运行进程的优先级高，设置重调度标志。Linux调度时机(3) 3)设置应用进程优先级参数nice值、创建新进程、SMP负载均衡时都可能使高优先级进程进入就绪状态，也可能设置重调度标志； 4)执行sched_setscheduler( )（设置调度策

33、略）、sched_yield( 暂时让出处理器)、pause( )（暂停）等系统调用，均要设置重调度标志。处理器状态转换 当中断/系统 调用发生时，暂时中断正在执行的用户进程，把进程从用户状态转换到内核状态，去执行操作系统服务程序以获得服务，这就是一次状态转换状态转换， 内核在被中断了的进程的上下文中对这个中断事件作处理，即使该中断可能不是此进程引起的。处理器状态转换步骤1)保存被中断进程的处理器现场信息；2)处理器从用户态转换到核心态，以便执行服务程序或中断处理程序；3)如果处理中断，可根据规定的中断级设置中断屏蔽位；4)根据系统调用号或中断号，从系统调用表或中断入口表找到服务程序或中断处理

34、程序地址。l用户空间中，处于进程上下文，用户进程在运行，使用用户栈。l内核空间中，处于进程上下文，内核代表某进程在运行，使用核心栈。l内核空间中，处于中断上下文，与任何进程无关，中断服务程序正在处理特定中断，Intel x86未提供中断栈，借用核心栈。l内核空间中，内核线程(无用户地址空间的进程)运行于内核态。 核心态运行系统调用或中断(隐含状态转换)状态转换用户态运行等待状态就绪状态等待唤醒调度进程中断、中断返回允许的上下文切换切换lLinux把内核空间中运行的程序称为任务，而在用户空间中运行的程序称为进程。l系统中存在两种进程(任务)：系统进程(任务)和用户进程(任务)，实质上是指一个进程

35、(任务)的两个侧面，。l两个进程(任务)所执行的程序不同，映射到不同物理地址空间、使用不同的堆栈。l处理器管理的一个主要工作是对进程的控制，包括：创建进程、阻塞进程、唤醒进程、挂起进程、激活进程、终止进程和撤销进程等。这些控制和管理功能由操作系统中的原语实现。l原语是在管态下执行、完成系统特定功能的过程。l原语和机器指令类似，其特点是执行过程中不允许被中断，是一个不可分割的基本单位，原语的执行是顺序的而不可能是并发的。l进程创建l进程撤销l进程阻塞l进程唤醒l进程挂起l进程激活l步1在进程列表中增加一项，从PCB池中申请一个空闲PCB，为新进程分配惟一的进程标识符；l步2为新进程的进程映像分配

36、地址空间，以便容纳进程实体。进程管理程序确定加载到进程地址空间中的程序；l步3为新进程分配除主存空间外的其他各种所需资源；l步4初始化PCB，如进程标识符、处理器初始状态、进程优先级等；l步5把新进程状态置为就绪态，并移入就绪进程队列；l步6通知操作系统的某些模块，如记账程序、性能监控程序。lfork( )-父子进程是独立的进程 lclone( ) -父子进程允许共享资源lvfork( )-子进程租用父进程地址空间 l步1根据撤销进程标识号，从相应队列中找到并移出它；l步2将该进程拥有的资源归还给父进程或操作系统；l步3若该进程拥有子进程，先撤销它的所有子进程，以防它们脱离控制；l步4回收PC

37、B，并归还到PCB池。 进程阻塞步骤：l步1停止进程执行，保存现场信息到PCB；l步2修改进程PCB有关内容，如进程状态由运行态改为等待态等，并把修改状态后的进程移入相应事件的等待队列中；l步3转入进程调度程序去调度其他进程运行。 进程唤醒步骤：l步1从相应的等待队列中移出进程；l步2修改进程PCB的有关信息，如进程状态改为就绪态，并移入就绪队列；l步3若被唤醒进程比当前运行进程优先级高，重新设置调度标志。2.4.1 引入多线程的动机2.4.2 多线程环境中的进程和线程2.4.3 线程的实现 2.4.1 引入多线程的动机 单线程(结构)进程（Single Threaded Process） 多

38、线程（结构）进程（Multiple Threaded process） 多线程结构进程 进程 进程PCB资源线程控制块用户栈核心栈线程控制块用户栈核心栈线程n控制块用户栈核心栈存储区存储空间全局数据程序代码线程1线程1线程控制块线程2线程1线程控制块用户栈核心栈线程i线程n 进程是操作系统中除处理器外进行的资源分配和保护的基本单位。 它有独立的虚拟地址空间，容纳进程映像(如与进程关联的程序与数据)，并以进程为单位对各种资源实施保护，如受保护地访问处理器、文件、外部设备及其他进程(进程间通信)。 线程线程是操作系统进程中能够独立执行的实体（控制流），是处理器调度和分派的基本单位。线程是进程的组成

39、部分，每个进程内允许包含多个并发执行的实体（控制流），这就是多线程。l（）线程唯一标识符及线程状态信息(运行态、就绪态、阻塞态和终止态)；l（）线程是一条执行路径，有独立的程序计数器；未运行时保护线程上下文。l（）线程有执行栈和存放局部变量的私用存储空间。l（4 ）可访问所属进程的内存和资源，并与该进程中的其他线程共享这些资源。 线程运行在进程的上下文中,并使用进程的资源和环境。 系统调度的基本单位是线程而不是进程,每当创建一个进程时，至少要同时为该进程创建一个线程。 Linux线程做法不一样。l线程状态有：运行、就绪、等待和终止，状态转换也类似于进程。l挂起状态对线程是没有意义，如果进程挂起

40、后被对换出主存，则它的所有线程因共享进程的地址空间，也必须全部对换出去。 进程中线程多种组织方式： 第一种是调度员工作者模式 第二种是组模式 第三种是流水线模式 多线程技术的应用 前台和后台工作 C/S应用模式 异步处理 加快执行速度。 设计用户接口。2.4.3 线程的实现从实现角度看，线程分成:用户级线程ULT(如Java ,Informix)。内核级线程KLT(如OS/2)。混合式线程(如Solaris)。各种线程实现方式的优点和缺点。 线程调度(1)当若干进程都有多个线程时，就存在两个层次的并行：进程和线程。操作系统调度程序需要根据是用户级线程还是内核级线程来决定对进程和线程的调度方法。

41、(2)用户级线程的调度：(3)内核级线程的调度；(4)用户级线程和内核级线程调度之间的差别：l进程描述符task_struct中包含：进程标识、进程状态、链接信息、环境信息、优先级信息、调度信息、通信信息、文件信息、虚存空间信息、信号处理信息、家族信息等。lLinux中认为线程就是共享地址空间及其他资源的进程，故并没有单独为线程定义数据结构，有一套在用户模式下运行的线程库-pthread，但每个线程都拥有惟一隶属于自己的task_struct。 00 x080480000 x400000000 xc0000000内核虚存用户栈(运行时创建)共享库主存映象区运行时堆空间堆(malloc创建)读/

42、写段只读段从可执行文件加载esp用户代码不可见未 用brk进程核心栈栈指针espcurrenttask_struct *thread_info;栈顶thred_info thred_info *task; 包含：l进程描述符task_struct指针、l当前CPU号、l底层标志、l线程同步标志、l内核抢占计数器等。 增加用于调度的新成员，主要有：l动态优先级priol静态优先级static_priol正常优先级normal_priol优先级数组prio_arrayl进程平均等待时间sleep_avgl负载平衡权重load_weight等(1)进程描述符分配过程(2)进程描述符删除过程(1)进程

43、链表：反映进程创建顺序及其亲属关系。(2)哈希链表：内核快速按pid查找进程。(3)就绪链表：进程就绪队列或运行队列。(4)等待链表：进程各种等待队列 。lTASK_RUNNINGlTASK_INTERRUPTIBLElTASK_UNINTERRUPTIBLElTASK_ZOMBIElTASK_STOPPEDlTASK_SWAPPING 等待状态current，拥有CPU运行TASK_ZOMBLETASK_UNINTERRUPTIBLETASK_INTERRUPTIBLETASK_STOPPED创建进程sys_exit()do_exit()sleep_on ()_down()wait_on()

44、interruptible_sleep_on()interruptible_sleep_on_timeout()_down_interruptble()do_fork()wake_up()wake_up_process()wake_up_interruptible()_up()wake_up()wake_up_process()_up()syscall_trace()do_signal()SIG_KILL|SIG_CONTwake_up_process()TASK_RUNNING(1) 创建进程1) fork( )-创建一般进程。2) vfork( )-创建完成特定任务的子进程。3) clon

45、e（）-创建线程。4) 创建函数的实现。#include stdio.h void main(int argc,char *argv ) pid_t pid; pid=fork( ); /*创建子进程*/ if(pid0) /*创建出错*/ fprint(stderr,“fork failed”); exit(-1); else if(pid=0) /*子进程*/ execlp(“/bin/ls”,“ls”,NULL); else wait(NULL); /* 父进程等待 子进程 完成*/ printf(“child complete”) exit(0); vfork( )函数创建子进程后，父

46、进程被阻塞，直到子进程执行exec( )或exit( )。允许子进程借用父进程的地址空间，执行结束后，归还地址空间并唤醒父进程，以减少不必要的开销。 在Linux系统中，线程被认为是一个与其他进程共享资源的进程，故被当作进程来实现，每个线程也用task_struct结构体描述。在Linux系统中，线程仅仅是一种进程间共享资源的方法。 clone（）用来创建线程。共享标志：lCLONE_VM：父子进程共享进程空间。l CLONE_FS：父子进程共享文件系统信息。l CLONE_FILES：父子进程共享打开的文件。l CLONE_SIGCHLD：子进程终结或者暂停时给父进程发信号。l CLONE_

47、SIGHAND：父子进程共享信号处理函数。l CLONE_PID：父子进程共享进程标识符。l CLONE_VFORK：父进程在子进程释放空间时被唤醒。 为子进程分配pid。 创建task_struct结构。 分配thread_info结构和核心栈。 复制父进程的task_struct信息和thread_info信息。 分配和初始化进程记账信息。 根据标志复制并继承父进程的信号量、文件、信号和进程地址空间和名字空间等信息。 初始化核心栈、状态设置为TASK_RUNNING，并将父进程时间片余额的一半分给它。 将子进程插入双向链表哈希链表 。 如果clone_flags包含CLONE_STOPPE

48、D标志，把子进程状态改为TASK_STOPPED；否则调用_activate_task()将子进程加入运行队列。 如果clone_flags包含CLONE_VFORK 标志，把父进程设置为阻塞状态直到子进程释放进程地址空间。 设置标志。需要时从某些队列中移出进程。 调用_exit_mm( )、_exit_files( )、_exit_fs( )、exit_sem( )、exit_sighand( )、exit_namespace( )、exit_thread( )释放进程占用的各种资源。释放资源时，先将共享计数器减1，若不为0表明有其他进程在使用该资源，此时直接返回。否则才真正释放资源。 设置

49、进程退出码，处理进程与父进程和子进程的关系。在该函数中，置状态为TASK_ZOMBIE，使其成为僵死进程。 调用schedule( )函数调度并切换到其他进程。 内核线程运行于内核态且只访问内核空间中的信息，既没有独立地址空间，也不切换到用户态。内核线程和普通进程一样，可以被调度，可以被抡占。 内核线程之间共享所有资源（除了各自拥有独立的栈和硬件上下文之外），并由系统中的其他内核线程通过内核函数kernel_thread（）创建。 内核线 程 周 期 性 地 被 唤 醒 和 调 用 ，用于实现系统后台操作，如页面对换、刷新磁盘缓存、网络连接等系统工作 。 kswapd( )和ksoftirqd

50、( )等都是内核线程。2.7.1 处理机调度层次2.7.2 选择调度算法的原则2.7.3 作业管理与调度2.7.4 低级调度功能和类型2.6.5 作业调度和低级调度算法p作业作业(Job)(Job)：作业是一个比程序更为广泛的概念，它不仅作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。统中，是以作业为基本单位从外存调入内存的。p作业步作业步(Job Step)(

51、Job Step)：通常，在作业运行期间，每个作业都通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，我们把其中的每一个加工步骤称为一个作业能得到结果，我们把其中的每一个加工步骤称为一个作业步，各作业步之间存在着相互联系，往往是把上一个作业步，各作业步之间存在着相互联系，往往是把上一个作业步的输出作为下一个作业步的输入。例如：步的输出作为下一个作业步的输入。例如： p作业流：作业流：若干个作业进入系统后，被依次存放若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作在外存上，这便形

52、成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形系统的控制下，逐个作业进行处理，于是便形成了处理作业流。成了处理作业流。： 为了管理和调度作业，在多道批处理系统中为每个作为了管理和调度作业，在多道批处理系统中为每个作业设置了一个作业控制块，它是作业在系统中存在的标志，业设置了一个作业控制块，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息：其中保存了系统对作业进行管理和调度所需的全部信息：作业标识、用户名称、用户帐户、作业类型作业标识、用户名称、用户帐户、作业类型(CPU (CPU 繁忙型、繁忙型、I/O I/O 繁忙型、批量型、终端型繁忙型、批量型

53、、终端型) )、作业状态、调度信息、作业状态、调度信息( (优优先级、作业已运行时间先级、作业已运行时间) )、资源需求、资源需求( (预计运行时间、要求预计运行时间、要求内存大小、要求内存大小、要求I/OI/O设备的类型和数量等设备的类型和数量等) )、进入系统时间、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用开始处理时间、作业完成时间、作业退出时间、资源使用情况等。情况等。在上述三种调度中，在上述三种调度中，进程调度进程调度的运行频率最高，在分时的运行频率最高，在分时系统中通常是系统中通常是1010100 ms100 ms便进行一次进程调度，因此把它称便进行一次进程调度

54、，因此把它称为短程调度。为避免进程调度占用太多的为短程调度。为避免进程调度占用太多的CPUCPU时间，进程调度时间，进程调度算法不宜太复杂。算法不宜太复杂。作业调度作业调度往往是发生在一个往往是发生在一个( (批批) )作业运行作业运行完毕，退出系统，而需要重新调入一个完毕，退出系统，而需要重新调入一个( (批批) )作业进入内存时，作业进入内存时，故作业调度的周期较长，大约几分钟一次，因此把它称为长故作业调度的周期较长，大约几分钟一次，因此把它称为长程调度。由于其运行频率较低，故允许作业调度算法花费较程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。多的时间。中级调度中级调度的运

55、行频率基本上介于上述两种调度之的运行频率基本上介于上述两种调度之间，因此把它称为中程调度。间，因此把它称为中程调度。 就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现1 1面向用户的准则面向用户的准则 (1) (1) 周转时间短。通常把周转时间的长短作为评价批处理周转时间短。通常把周转时间的长短作为评价批处理系统的性能、选择作业调度方式与算法的重要准则之一。所系统的性能、选择作业调度方式与算法的重要准则之一。所谓周转时间，是指从作业被提交给系统开始，到作业完成为谓周转时间，是指从作业被提交给系统开始

56、，到作业完成为止的这段时间间隔止的这段时间间隔( (称为作业周转时间称为作业周转时间) )。它包括四部分时间：。它包括四部分时间：作业在外存后备队列上等待作业在外存后备队列上等待( (作业作业) )调度的时间，进程在就绪调度的时间，进程在就绪队列上等待进程调度的时间，进程在队列上等待进程调度的时间，进程在CPUCPU上执行的时间，以及上执行的时间，以及进程等待进程等待I/OI/O操作完成的时间。其中的后三项在一个作业的整操作完成的时间。其中的后三项在一个作业的整个处理过程中可能会发生多次。个处理过程中可能会发生多次。 niiTnT11作业的周转时间作业的周转时间T T与系统为它提供服务的时间与

57、系统为它提供服务的时间TsTs之比，即之比，即W = T/TsW = T/Ts，称为带权周转时间，而平均带，称为带权周转时间，而平均带权周转时间则可表示为：权周转时间则可表示为： niiTTnW1s1(3) (3) 截止时间的保证。这是评价实时系统性能的重要指截止时间的保证。这是评价实时系统性能的重要指标，因而是选择实时调度算法的重要准则。所谓截止时间，标，因而是选择实时调度算法的重要准则。所谓截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。对于严格的实时系统，其调度方式和调度算法必须能保间。对于严格的实时系统，其调度方式和

58、调度算法必须能保证这一点，否则将可能造成难以预料的后果。证这一点，否则将可能造成难以预料的后果。(4) (4) 优先权准则。在批处理、分时和实时系统中选择调优先权准则。在批处理、分时和实时系统中选择调度算法时，都可遵循优先权准则，以便让某些紧急的作业能度算法时，都可遵循优先权准则，以便让某些紧急的作业能得到及时处理。在要求较严格的场合，往往还须选择抢占式得到及时处理。在要求较严格的场合，往往还须选择抢占式调度方式，才能保证紧急作业得到及时处理。调度方式，才能保证紧急作业得到及时处理。 2 2面向系统的准则面向系统的准则这是为了满足系统要求而应遵循的一些准则。其中，这是为了满足系统要求而应遵循的

59、一些准则。其中，较重要的有以下几点：较重要的有以下几点：(1) (1) 系统吞吐量高。系统吞吐量高。算法评价算法评价时间片时间片高响应高响应高优先权高优先权1 1提供必要的信息提供必要的信息(1) (1) 就绪时间就绪时间：是一个任务成为就绪状态的起始时间，在周期任务的：是一个任务成为就绪状态的起始时间，在周期任务的情况下，它就是事先预知的一串时间序列；而在非周期任务的情况下，它情况下，它就是事先预知的一串时间序列；而在非周期任务的情况下，它也可能是预知的。也可能是预知的。 (2) (2) 开始截止时间和完成截止时间：开始截止时间和完成截止时间：对于典型的实时应用，只须知对于典型的实时应用，只

60、须知道开始截止时间，或者知道完成截止时间。道开始截止时间，或者知道完成截止时间。(3) (3) 处理时间处理时间：这是指一个任务从开始执行直至完成所需的时间。：这是指一个任务从开始执行直至完成所需的时间。(4) (4) 资源要求资源要求：这是指任务执行时所需的一组资源。：这是指任务执行时所需的一组资源。(5) (5) 优先级：优先级：如果某任务的开始截止时间已经错过，就会引起故障，如果某任务的开始截止时间已经错过，就会引起故障，则应为该任务赋予则应为该任务赋予“绝对绝对”优先级；如果开始截止时间的推迟对任务的继优先级；如果开始截止时间的推迟对任务的继续运行无重大影响，则可为该任务赋予续运行无重