《操作系统教程》（第二版）配套教学课件

操作系统(OperatingSystems)参考文献A.Silberschatz,P.Galvin,OperatingSystemConcepts,6thedition,Wiley,高等教育出版社,2002.系统，完善，国外大学多选用A.Silberschatz,P.Galvin,GregGagne.AppliedOperatingSystemConcept,JohnWiley&SonsInc.高等教育出版社，2001.面向应用，比较浅显，算法不够完整算法用Java语言描述参考文献A.S.Tanenbaum.ModernOperatingSystems,PrenticeHall,机械工业出版社,2002.国内用的比较多WilliamStalling,OperatingSystems,InternalsandDesignPrinciples,3rdEdition,PrenticeHall,清华大学出版社,1998.另一本比较权威的教材参考文献H.M.Deitel,P.J.Deitel,D.R.Choffnes.OperatingSystems,3rdedition,施平安等译,清华大学出版社,2007.很完整，篇幅很长（1331页）孙钟秀等，操作系统教程，第3版，高等教育出版社，2003.8国内代表性教材参考文献莱昂氏UNIX源代码分析，6thedition,机械工业出版社，2001.UNIX源代码10000行C语言9000行,汇编语言1000行PDP11-45,要求了解硬件体系结构,指令系统注释尤晋元，史美林，陈向群等.Windows操作系统原理，机械工业出版社，2001.第一章操作系统概述操作系统的概念操作系统的历史操作系统的特性操作系统的类型操作系统的运行环境操作系统的界面形式操作系统的运行机理研究操作系统的几种观点1.1操作系统概念操作系统地位操作系统作用操作系统定义Whatisoperatingsystem?1.1.1操作系统地位硬件抽象层（HAL）之上所有其它软件层之下硬件（HAL）OS其它系统软件层应用软件层运行视图系统库(lib)可调用操作系统，执行硬件指令应用程序可以调用lib和操作系统，执行硬件指令硬件(HAL)操作系统系统库应用程序机器指令系统调用库调用1.1.2操作系统的作用管理系统中软件硬件资源CPU内存设备文件为用户(应用程序)提供良好的服务(界面)APIGUI,行式命令JCL(JobControlLanguage)1.1.3操作系统定义操作系统是位于硬件层(HAL)之上，所有其它软件层之下的一个系统软件，是管理系统中各种软硬件资源，方便用户使用计算机系统的程序集合。Operatingsupervisormonitoringprogram1.2操作系统的历史操作系统的产生手工操作阶段成批处理阶段执行系统阶段操作系统的完善多道批处理系统分时系统实时处理系统通用操作系统操作系统的发展网络操作系统分布式操作系统多处理机操作系统单用户操作系统面向对象操作系统嵌入式操作系统智能卡操作系统Evolution1.3操作系统特性并发性多个程序在宏观上同时向前推进并发(concurrent)vs.并行(parallel)共享性多个程序共用系统中的各种软硬件资源在操作系统的协调和控制下异步行（随机性）多个程序以不可预知的速度向前推进虚拟性把一个实的CPU改造为多个虚的CPU内存+外存→虚存独占设备+共享设备→虚拟设备1.4操作系统类型多道批处理操作系统(batchprocessingsystem)分时操作系统(time-sharingsystem)实时操作系统(realtimesystem)通用操作系统(multi-purposesystem)单用户操作系统(singleusersystem)网络操作系统(networkoperatingsystem)分布式操作系统(distributedoperatingsystem)多处理机操作系统(multi-processorsystem)嵌入式操作系统(embeddedoperatingsystem)智能卡操作系统(smart-cardoperatingsystem)作业（Job)：程序+数据+说明书（JCL编写）结果：程序运行结果+记帐信息主机输入井输出井输出机输入机作业结果SPOOLing输入作业调度（1）作业调度（2）SPOOLing输出1.4.1多道批处理系统（off-line）1.4.1多道批处理系统(cont.)输入井作用缓冲(速度匹配作用)实现作业调度(jobscheduling)输出井作用缓冲(速度匹配作用)Buffering:处理数据到达与离开速度不一致1.4.1多道批处理系统(Cont.)主机中作业合理搭配目标1：提高资源利用率(eg.计算型+IO型)目标2：提高吞吐量(throughput)特点多道：系统中同时容纳多个作业成批：作业分批进入系统分时处理终端请求界面1：交互式命令语言(eg.shell,command)界面2：图形用户界面(GUI)1.4.2分时操作系统（On-line）TimeSharingOSHAL终端终端终端…...1.4.2分时操作系统(Cont.)特点：多路性：一个主机与多个终端相连；交互性：以对话的方式为用户服务；独占性：每个终端用户仿佛拥有一台虚拟机。典型系统：Multics(MIT)UNIX1.4.3实时操作系统实时控制工业控制，军事控制，医疗控制，…….实时信息处理航班定票，联机情报检索，…….

实时控制HALRealTimeOS被控对象A/DD/At1t2t2-t1:responsetime实时信息处理

HALRealTimeOS….终端终端终端通常为远程终端特点：（1）响应及时（promptresponse）（2）可靠性高（highreliability）1.4.4通用操作系统(multi-purposeOS)同时具有：分时、实时、批处理功能。目标：提高处理能力;扩展应用领域。常见模式:分时(前台)+批处理(后台)（eg.GCOS-8）实时(前台)+批处理(后台)

Foreground/BackgroundSystem1.4.5单用户操作系统同一时刻仅有一个用户使用的系统应用领域：台式机，笔记本，…….特点：单用户，多进程，多线程不同的程序，不同的进程；相同的程序,不同的线程1.4.6网络操作系统(NetworkOS)NOS3host3NOS2host2Printer建立在宿主操作系统之上，提供网络通讯、网络资源共享、网络服务的软件包。NOS1host1网络操作系统的目标相互通讯资源共享（信息，设备）提供网络服务databaseserverftpservere-mailservertelnetserveretc.

NoTransparentview1.4.7分布式操作系统(DistributedOS)紧耦合：(tightlycoupled)由多机系统发展而来（多CPU）有公共内存多处理机操作系统CPU内存CPUCPU…1.4.7分布式操作系统松散耦合：(looselycoupled)由计算机网络发展而来（多Host)无公共内存，无公共时钟DOShost3DOShost2DOShost11.4.7分布式操作系统(Cont.)分布式操作系统特征:统一的操作系统资源的进一步共享内存,CPU可靠性透明性1.4.7分布式操作系统(Cont.)目标：进一步共享资源，使负载均衡，计算加速。CPU内存途径：迁移（migration）作业迁移进程迁移（线程一般随同进程迁移）例子：SolarisMC1.4.8多处理机操作系统多处理机系统具有公共内存的多CPU系统对称多处理机系统(SMP-symmetricmulti-processor)没有主从关系的多处理机系统多处理机操作系统有效管理和使用多个CPU的操作系统复杂性：多个主动体（CPUs)例子：UNIX,Linux,Windows1.4.9嵌入式操作系统嵌入在掌上电脑、通讯设备、车载系统、信息家电等非计算机类设施上的操作系统。特点：微内核结构（Micro-kernel），许多操作系统功能(文件系统,设备驱动)以应用程序模式运行。核心小(基本内存管理,CPU管理,通讯程序),适应范围广,可靠性高效率低例子：WinCE.NET（维纳斯）PalmOSHOPEN（女娲）Embededworld1.4.10智能卡操作系统智能卡CPU芯片ROM面向Java的智能卡JVM解释程序下载Javaapplet并执行SC-OS支持多个applet并发执行必要的资源管理1.5操作系统运行环境定时装置系统栈特权指令与非特权指令处理机状态及状态转换地址映射机构存储保护设施中断装置通道与DMA控制器IO保护1.5.1定时装置绝对时钟：记载实际时间，不发中断。间隔时钟：定时发生中断，一般间隔单位为“毫秒”。间隔时钟是实现多道程序的基础—保证操作系统获得控制权。其它中断也进入操作系统，但是否发生，何时发生没有保障。1.5.2系统栈(systemstack)作用保存中断现场保存子程序转移返回点、参数、局部变量、返回值位置操作系统区域Stackvs.heap1.5.3特权指令与非特权指令特权指令（privilegedinstruction）只有在管态才能执行的指令(影响系统状态)关中断，置程序状态字，停机，IO，…….非特权指令（non-privilegedinstruction）所有程序可用(不影响系统状态)取数，四则运算，……

1.5.4处理机状态及状态转换处理机状态系统态（systemmode）(管态，核态)用户态（usermode)(目态，常态)状态转换管态目态(置程序状态字,特权指令)目态管态(中断，trap)Dualmodeoperation例子：IBM360/370PSW状态位（0，1）ModernPCnowsupport4modes:R0（权限最强）R1R2R3（权限最弱）OnlyR0,R3areused,now1.5.5地址映射机构逻辑地址物理地址逻辑地址(虚地址)：程序中产生的地址物理地址(实地址)：存储器地址Addressmappingbysoftwareispossible,butveryinefficient.1.5.6存储保护设施防止应用程序侵犯操作系统空间;侵犯其它用戶空间.地址检查越界检查;越权检查（对共享区域）.1.5.7中断装置发现并响应中断的硬件机构当前（PSW，PC）系统栈中断向量（PSW，PC）寄存器1.5.8通道与DMA通道：负责IO操作的处理机通道指令系统读写操作控制操作转移操作通道运控部件通道地址字CAW通道命令字CCW通道状态字CSW通道数据字CDWDMA？没有独立指令系统简单块传输Anyotherdifference?1.5.9IO保护定义所有IO指令为特权指令。方便使用防止发生冲突1.6操作系统界面形式交互终端命令（CommandLanguage）Eg.UNIXshell$命令名-选项参数图形界面（GUI—GraphicUserInterface）UNIXshellinterface优点:缩小核心不同用户可以选择不同界面UNIX硬件shellshellshell……终端终端终端1.6操作系统界面形式(Cont.)作业控制语言（JobControlLanguage）作业标识语句用户标识，作业标识，帐号作业步语句(编译、连接装配、执行）一般对应子进程资源描述语句内存需求，计算时间，其它资源Goto语句（正向转移）作业控制无循环1.6操作系统界面形式(Cont.)系统调用命令（OSAPI）高级语言形式fd=open(file_name,mode)汇编语言形式准备参数trapn取返回值如何转换？1.7操作系统的运行机理操作系统运行机理:硬件程序１程序２中断处理…程序切换保存程序1现场…选择P2…恢复程序2现场中断置pswOS1.8研究操作系统的几种观点进程观点支持进程支持进程之间的协同资源管理观点操作系统是资源管理者方便使用防止冲突虚拟机观点对硬件的第一次扩充提供虚拟资源单CPU→多个虚拟CPU内存+外存→虚拟存储独占设备+共享→虚拟设备1.8.1Linux系统

历史1991,0.01版运行于intel80386，仅支持Minix文件系统，支持有限的设备驱动程序，无网络支持.1994,1.0版支持UNIX标准TCP/IP协议，BSD兼容的socket网络通讯协议，增强的文件系统，SCSI控制器对文件的高效访问，以及其它设备驱动程序.1995,1.2版最后一个仅在PC平台上运行的Linux.1996,2.0版运行于多种平台，支持对称多处理，同时增强了存储管理功能，支持核心级线程，模块动态连接等．可运行于SunSparc,PowerMac等硬件平台.Linux特点：源代码开放,免费系统稳定可靠；速度快，效率高；内核模块化好，允许第三方配置文件系统及设备管理程序；功能完善；具有网络支持优势；标准化好.1.8.2Windows2000/XP系统基于NT技术构建的面向个人计算几平台的操作系统，本质上属于单用户系统，但可以组网并提供网络服务.特点具有多任务(包括多进程、多线程)管理功能，支持对称多处理支持客户/服务器计算模式

在设计上大量采用了面向对象思想，提供友好的图形操作界面

不是“纯”的微内核结构，许多系统服务功能已被放入核心

第二章进程、线程与作业2.1多道程序设计Multi-programming2.2进程的引入Process2.3线程与轻进程Threadandlight-weightedprocess2.4作业JobActiveobjects2.1多道程序设计2.1.1单道程序设计的缺点2.1.2多道程序设计的提出2.1.3多道程序设计的问题

Multi-programming多道程序设计目标提高系统效率(吞吐量)2.1.1单道程序设计的缺点处理机利用率低设备利用率低内存利用率低运行程序ACPU设备1运行程序Att1t2t5t6设备22.1.2多道程序设计的提出提高处理机、设备、内存等各种资源的利用率，从而提高系统效率。CPU设备1程序Att1t2t5t6设备2程序B程序At3t42.1.2多道程序设计的提出(Cont.)增加同时运行程序的道数可以提高资源利用率，从而提高系统效率，但道数应与系统资源数量相当。道数过少，系统资源利用率低。道数过多，系统开销(systemoverhead)增大，程序响应速度下降。2.1.3多道程序设计的问题处理机资源的管理程序个数处理机个数(如何分配?)存储资源的管理地址空间的相对独立性、共享性内存、外存(swapspace)的分配与去配设备资源管理分配策略IO控制2.2进程的引入2.2.1进程的概念2.2.2进程状态及状态转换2.2.3进程控制块2.2.4进程的组成与上下文2.2.5进程的队列2.2.6进程的类型与特征2.2.7进程间相互联系与相互作用2.2.8进程的创建与撤销2.2.9进程与程序间的联系与差别多道系统中的程序：

推进，暂停，推进，暂停，…….暂停：保存现场(PSW+PC，寄存器）推进：恢复现场(寄存器，PSW+PC)暂停原因：(1)自身原因：等待资源，启动IO

(2)剥夺CPU—给其它程序运行机会2.2进程的引入(Cont.)2.2.1进程的概念定义：可参与并发执行的程序称为进程。进程是具有一定独立功能的程序关于一个数据集合的一次运行活动。定义强调两个方面：动态：执行中的程序;并发：可与其他进程同时执行。并发vs.并行并发：concurrent宏观同时，“交替执行”，不要求多个CPU并行：parallel微观同时，要求多个CPU“并行算法”2.2.2进程状态及状态转换

进程状态(基本状态)运行态(RUN):占有CPU正在向前推进就绪态(READY):可以运行，但未得到CPU等待态(WAIT):等待某一事件发生

状态转换就绪运行：获得处理机运行就绪：剥夺处理机运行等待：申请资源未得到，启动IO等待就绪：得到资源，IO中断就绪等待运行获得处理机剥夺处理机等待事件事件发生

进程状态转换图KeepinMind

进程状态转换图就绪等待运行获得处理机剥夺处理机等待事件事件发生初创终止创建结束2.2.3进程控制块(PCB)标志进程存在的数据结构，其中保存系统管理进程所需的全部信息PCB内容：(不同系统不尽相同)进程标识(pid)家族联系进程状态地址信息现场信息打开文件调度参数消息指针所属用户(uid)队列指针ProcessControlBlock2.2.4进程的组成与上下文进程的组成进程控制块(processcontrolblock)建立进程建立PCB撤销PCB撤销进程程序代码(code)数据(data)堆栈(stack+heap)栈：保存返回点、参数、返回值、局部变量堆：动态变量2.2.4进程的组成与上下文进程的表记PCB程序PCB代码数据+堆栈表记1表记2系统空间用户空间2.2.4进程的组成与上下文进程上下文（processcontext)进程的物理实体与支持进程运行的物理环境统称为进程上下文PCB+程序系统环境：地址空间，系统栈，打开文件表，…上下文切换（contextswitch)由一个进程的上下文转到另外一个进程的上下文系统开销（systemoverhead)运行操作系统程序完成系统管理工作所花费的时间和空间2.2.5进程的队列PCBPCBPCB……head1.就绪队列：系统一个或若干个（根据调度算法确定）2.等待队列：每个等待事件一个3.运行指示字：每个处理机一个PCB构成的队列：（不一定FIFO，单向或双向）进程队列模型就绪队列等待队列1等待队列2等待队列n…CPU创建完成时间片用完等待事件1等待事件2等待事件n事件1发生事件2发生事件n发生2.2.6进程的类型与特征进程类型系统进程运行操作系统程序，完成系统管理(服务)功能.例如：UNIX#0--sched,#1--init用户进程运行用户(应用)程序，为用户服务。例如：UNIXvi,shell,cc2.2.6进程的类型与特征(Cont.)进程的特征并发性：可以与其它进程一道向前推进；动态性：动态产生、消亡，生存期内状态动态变化；独立性：一个进程是可以调度的基本单位；交往性：同时运行的进程可能发生相互作用；异步性：进程以各自独立，不可预知的速度向前推进；结构性：每个进程有一个PCB。2.2.7进程间相互联系与相互作用相互联系相关进程同一家族的进程可以共享文件，需要相互通讯，协调推进速度…父进程可以监视子进程，子进程完成父进程交给的任务。无关进程没有逻辑关系、同时执行的进程。有资源竞争关系，互斥、死锁、饿死。2.2.7进程间相互联系与相互作用相互作用1.直接相互作用：发生在相关进程之间2.间接相互作用：发生在任何进程之间RP2P1syncsendreceiveP1:P2:holdwait2.2.8进程的创建与撤销进程的创建建立PCB，分配内存，加载程序，入就绪链UNIX：pid=fork()，exec(prog,args)进程的撤销去配资源，撤销PCB，通知父进程UNIX：exit()vs.kill除初始进程外，其它进程由(父)进程创建，并形成进程家族。2.2.9进程与程序的联系与差别进程与程序的联系进程包括一个程序进程存在的目的就是执行这个程序进程与程序的差别程序静态，进程动态程序可长期保存，进程有生存期一个程序可对应多个进程，一个进程只能执行一个程序2.3线程与轻进程2.3.1线程的引入2.3.2线程的概念2.3.3线程的结构2.3.4线程控制块2.3.5线程的实现2.3.6线程的应用2.3.7Java线程ThreadLight-weightedprocess2.3.1线程的引入进程切换上下文涉及内容多，开销大，“笨重”PCB+程序系统环境：地址空间，系统栈，打开文件表，相关进程之间耦合关系差解决方案Multi-threading同一进程中包含多个线程上下文只涉及寄存器和用户栈，切换速度快相关线程之间通讯方便、快捷2.3.2线程的概念进程中一个相对独立的执行流。进程vs.线程进程是资源分配单位线程是执行单位多线程优点切换速度快（地址空间不变）(lightweighted)系统开销小通讯容易（共享数据空间）2.3.3线程结构寄存器静态数据程序代码栈寄存器进程2动态堆内存多进程结构（用户视图）静态数据程序代码栈进程1动态堆内存寄存器2.3.3线程结构静态数据程序代码栈栈寄存器寄存器线程1：线程2：进程动态堆内存多线程结构（用户视图）2.3.3线程结构（另一种表示）textsegmentdatasegmentProgramcounterTask:2.3.4线程控制块TCB（Threadcontrolblock)标志线程存在的数据结构，其中包含对线程管理需要的全部信息．内容线程标识线程状态调度参数现场(通用寄存器,PC,SP)链接指针存放位置用户级线程：目态空间（运行系统）核心级线程：系统空间2.3.5线程的实现2.3.1用户级别线程User-levelthread2.3.2核心级别线程Kernel-levelthread2.3.3混合线程Hybridapproach

用户级别线程实现方法：基于library函数，系统不可见线程创建、撤销、状态转换在目态完成TCB在用户空间，每个进程一个系统栈优点：不依赖于操作系统，调度灵活同一进程中多线程切换速度快(不需进入操作系统)缺点：同一进程中多个线程不能真正并行一个线程进入系统受阻，进程中其它线程不能执行

用户级别线程运行系统TCB进程线程核心栈进程表用户空间系统空间

核心级别线程实现方法：基于系统调用创建、撤销、状态转换由操作系统完成优点：同一进程内多线程可以并行执行一线程进入核心等待，其它线程仍可执行缺点：系统开销大，同一进程内多线程切换速度慢调度算法不能灵活控制

核心级别线程进程线程核心栈进程表用户空间系统空间TCB

混合线程Solaris例子Userlevelthread:由Lib程序支持（创建,调度）Lightweightedprocess(LWP):由Lib程序支持每个task至少一个LWP用戶级别线程与LWP可以多对多LWP对操作系统可见只有与LWP相联系的用户线程向前推进Kernellevelthread:由kernel支持每个LWP与唯一一个核心线程对应核心线程可与CPU多对多，可对一

混合线程(Solaris)CPUtask1task2task3kernelUserlevelthreadLightweightprocessKernelthread2.3.6线程的应用内在的多控制流,需要共享数据生产－消费问题多线程优于多进程快100倍!提高处理机与设备的并行性多处理机环境提高处理机利用率，加快进程推进速度2.3.6线程的应用例子：Word字处理（不同代码）交互编辑(T1)词法检查(T2)定时保存(T3)HTTPserver（相同代码）对每个http请求，popup一个线程2.4作业（Job)作业概念用户要求计算机系统为其完成的计算任务集合。作业步（jobstep)作业处理过程中一个相对独立的步骤一般一个作业步可由一个进程完成某些作业步之间可以并行作业分类批处理作业交互式作业2.4.1批处理作业作业控制语言(JCL)描述批处理作业控制意图的语言作业说明书(JCL语句的序列）一般一特殊符号起始$JOBJ1$FORTN…$LINK…$EXEC…$ENDJOB作业控制程序解释并处理作业说明书的程序作业控制进程执行作业控制程序的进程作业控制进程读入作业内容释放输入井空间顺取作业控制语句是结束语句

执行该作业步(可能创建子进程)申请输出井空间输出作业结果进程自我终止FT2.4.2交互式作业帐户管理/etc/passwd文件(用户名,口令,用户根目录,同组用户,余额…)创建与撤销创建：用户提供（用户名,口令,资金）系统操作员建立（根目录/usr/zhang,填写passwd文件）撤销：删除该用户目录及所有文件在passwd文件中清除对应entry2.4.2交互式作业注册与注销注册：logon:用户名password:********(使用)注销：显式注销：logoff隐式注销：（如5分钟无输入命令）命令解释程序提示符$读入终端命令分析Logout内部命令处理建立子进程后台命令等子进程结束输出子进程号记帐TFTFFT小结：作业、进程、线程作业与进程作业进入内存后变为进程一个作业通常与多个进程相对应进程与线程一个进程一般包含多个线程，至少包含一个线程不支持多线程的系统，可视为单线程进程

2.5.1Java线程

Java线程四种基本状态

New：新建的线程Runnable：可运行状态Blocked：封锁状态Dead：终止状态．

Java线程Java线程状态之间的转换关系图

Sleep()Suspend()IORunnableBlockedDeadNewStart()Stop()Resume()JAVA线程与JVMJava线程是由Java虚拟机JVM支持的JVM位于操作系统之上Java线程与操作系统线程之间的对应关系由JVM确定对于WindowsNT的JVM，Java线程与操作系统线程具有一对一关系;对于Solaris的JVM，其对应关系为多对多.2.5.2Linux进程与线程

进程与线程在系统内部具有统一的表示进程与线程的差别通过与fork不同的另外一个系统调用clone体现出来

Clone系统调用的形式pid=clone(function,stack_ptr,sharing_flag,arg)

Sharing-flag:CLONE_VM,CLONE_FILES,CLONE_SIGHAND,CLONE_PID2.5.3Windows2000/XP进程、线程与纤程进程在Win32环境中创建进程的过程当Win32应用执行CreateProcess调用，消息被发给Win32子系统，后者调用进程管理器创建进程，进程管理器调用OM创建进程对象，然后返回对象把柄给Win32.Win32子系统再次调用进程管理器为该进程创建线程，最后Win32将把柄返给新进程和线程

对象头部属性Type:Process对象体属性进程标识（Processid）访问令牌（Accesstoken）基础优先级（Basepriority）缺省亲合处理机（Defaultprocessoraffinity）配额限制（Quotalimits）执行时间（Executiontime）输入/输出记数（I/Ocounters）执行/调试端口（Exception/debuggingports）退出状态（exitstatus）服务创建进程（Createprocess）打开进程（Openprocess）查询进程信息（Queryprocessinformation）设置进程信息（Setprocessinformation）当前进程（Currentprocess）终止进程（Terminateprocess）分配/释放虚拟存储（Allocate/freevirtualmemory）读/写虚拟存储（Read/writevirtualmemory）保护虚拟存储（Protectvirtualmemory）加锁/开锁虚存（Lock/unlockvirtualmemory）查询虚拟存储（Queryvirtualmemory）刷新虚拟存储（Flushvirtualmemory）进程对象描述图

对象头部属性属性类型：线程（Type:thread）

属性客户标识（clientid）线程上下文（threadcontext）动态优先级（dynamicpriority）处理机亲合掩码（threadprocessoraffinity）已执行时间（threadexecutiontime）警觉状态（alertstatus）挂起记数（suspensioncount）非角色令牌（impersonationtoken）终止端口（terminationport）终止状态（exitstatus）

服务创建线程（Createthread）打开线程（Openthread）查询线程状态（Querythreadinformation）设置线程状态（Setthreadinformation）当前线程（Currentthread）终止线程（Terminatethread）取上下文（Getcontext）置上下文（Setcontext）挂起（Suspend）恢复（Resume）警示线程（Alertthread）测试线程警示（Testthreadalert）注册终止端口（Registerterminationport）

线程对象描述图

就绪等待初始备用运行转换终止创建线程对象重新初始化执行完入就绪队列剥夺唤醒唤醒栈在外换入内核栈切换选中等待某对象抢先Windows线程状态转换图

第三章中断与处理机调度3.1中断与中断系统3.2处理机调度3.3调度级别与多级调度3.4实时调度3.5多处理机调度3.6系统举例

操作系统是中断驱动的！Interruptdriven3.1中断与中断系统3.1.1中断的概念3.1.2中断装置3.1.3中断处理程序3.1.1中断的概念处理机在运行过程中，出现了某一事件，必须中止正在运行的程序，转去处理这个事件，然后再返回原来运行的程序，这一过程称为中断。中断系统：中断装置(硬件)中断处理程序(软件)3.1.2中断装置发现并响应中断的硬件机构识别中断源，当有多个中断源时，按紧迫程度排队；保存现场；引出中断处理程序。中断响应和处理的过程正运行程序

16处理程序

4PSW’，PC’PC’:PSW,PC系统桟psw,pc……...253HALOS中断

中断源与中断字中断源引起中断的事件。中断寄存器保存与中断事件相关信息的寄存器。中断字中断寄存器的内容。例：IO中断：设备状态寄存器。

中断类型与中断向量强迫性中断运行程序不期望的时钟中断IO中断控制台中断硬件故障中断powerfailure内存校验错程序性中断越界，越权缺页溢出，除0非法指令自愿性中断运行程序期望的系统调用访管指令系统调用fd=open(fname,mode)访管指令准备参数svcn取返回值

中断类型与中断向量中断装置

中断处理程序运行程序访管指令运行程序中断装置

中断处理程序clockIOconsolePowerfailuremalfunction强迫中断：自愿中断：SVCntrapn

中断类型与中断向量中断向量：中断处理程序的运行环境与入口地址（PSW，PC）每类中断事件有一个中断向量,中断向量的存放位置是由硬件规定的,中断向量的内容是OS在系统初始化时设置好的。

中断向量mode应为系统态

中断类型与中断向量PSW1,PC1时钟中断向量PSW2,PC2I/O中断向量PSW3,PC3console中断向量PSW4,PC4硬件故障PSW5,PC5程序错误

……PSWn,PCn访管中断向量00000008001600240030

…0090时钟中断处理程序PC1:I/O中断处理程序PC2:访管中断处理程序PCn:…系统空间

中断嵌套与系统栈一般原则：高优先级别中断可以嵌入低优先级中断实现方法：中断响应后立即屏蔽不高于当前中断优先级的中断源。

中断嵌套与系统栈中断响应后一般需要进一步保存现场

关中断（屏蔽所有中断）进一步保存现场（通用寄存器等）

开中断（或开放高优先级中断）

…...

中断处理

…...

关中断（屏蔽所有中断）恢复现场开中断（或开放高优先级中断）中断返回

中断嵌套与系统栈(Cont.)……目态PSW1:PC1……管态PSW2:PC2……管态PSWn:PCn…中断嵌套:……

中断嵌套与系统栈(Cont.)……PSWn-1PCn-1……PSW2PC2PSW1PC1栈顶指针:系统栈:

中断优先级与中断屏蔽中断优先级：硬件规定的中断响应次序，依据:紧迫程度；处理时间。中断屏蔽：高优先级中断事件处理不受低优先级中断打扰；程序调整中断响应次序。3.1.3中断处理程序强迫性中断：自愿性中断：

转中断处理程序是否嵌套中断由系统栈恢复现场需要切换进程返回上层中断由系统栈恢复现场转CPU分派返回目态程序（dispatcher）保存现场信息取中断字分析中断原因保存现场信息取访管号分析调用功能TFFT

IO中断处理正常结束继续传输；唤醒相关进程。传输错误复执（eg.3次)；报告系统操作员。

时钟中断处理Housekeeping进程管理重新计算进程调度参数(eg.动态优先数)实现软时钟，启动定时程序硬时钟5ms发生一次中断，软时钟50ms考虑进程切换

控制台中断处理一个控制按钮，一个中断向量，一个中断处理程序。

硬件故障处理电源故障处理掉电：内存，寄存器外存停止设备停止处理机恢复：启动处理机启动设备外存内存，寄存器

UseUPSforcriticalapplications

硬件故障处理(cont.)内存故障处理海明校验，奇偶校验错误下雨检查划出系统报告操作员

程序性中断的处理只能由操作系统处理的中断影响系统或其它进程越界，非法指令，（处理：终止进程、调试）需要系统管理或协助页故障，缺段，（处理：动态调入）可以由用户自己处理的中断不影响系统和其它进程除0，溢出，（处理：用户处理，或OS处理）应用程序自己处理中断调试语句：on<中断条件><中断续元入口>例如：on<divide_zero>gotoLA;除0中断时转LA处理除0中断时转LB处理on<divide_zero>gotoLB除0中断续元除0中断续元LA:LB:相同中断发生在不同位置可采用不同处理方法应用程序自行处理中断(Cont.)编译时：生成中断续元表：中断续元入口0中断续元入口1……中断续元入口n中断事件0:中断事件1:中断事件n:…...运行时：执行调试语句，填写中断续元表。中断时：根据中断原因查中断续元表，为0，用户未规定中断续元，由OS标准处理；非0，用户已规定中断续元，由用户处理。初始时均为0图3-9（P47）步骤：（1）发生溢出中断（2）保存旧PSW和PC（3）取中断向量（4）转到中断处理程序（5）访问中断续元表（假定非0）（6）系统栈中现场转移到用户栈（7）中断续元入口送寄存器（OS中断处理完成）（8）执行中断续元（9）用户栈PSW和PC送寄存器（10）返回中断断点

自愿性中断的处理访管指令（SuperVisorCall)形式：准备参数SVCn取返回值系统调用（systemcall)形式：返回值=系统调用名称（实参1,…,实参n)

参数和返回值的存放位置是由OS规定的。

自愿性中断的处理系统调用驱动表：(tabledriven)服务程序入口addr0…………addrm-1访管号：0……...m-1Eg.UNIX3.2处理机调度3.2.1处理机调度算法按什么原则分配3.2.2处理机调度时机何时重新分配3.2.3处理机调度过程如何完成分配scheduling3.2.1处理机调度算法考虑因素（schedulingcriteria）CPU利用率;(max)吞吐量;(max)周转时间;(min)响应时间;(min)系统开销;(min)调度参数周转时间：完成时间-进入时间平均周转时间：周转时间的平均值带权周转时间：周转时间/运行时间平均带权周转时间：带权周转时间的平均值CPUburstvs.I/Oburst阵发期:CPUburstcycle:进程(线程)使用CPU计算；I/Oburstcycle:进程(线程)使用设备I/O。进程运行行为：CPUburst,I/Oburst,CPUburst,I/Oburst,……CPU调度：考虑处于CPUburst进程集合

CPUburst时间根据以前行为推定。剥夺式调度与非剥夺式调度剥夺式(preemptive)就绪进程可以从运行进程手中抢占CPU。进程运行,直到结束、等待或被抢先非剥夺式(non-preemptive)就绪进程不可从运行进程手中抢占CPU。进程运行,直到结束或等待

先到先服务算法FCFS（FirstComeFirstServe)按进程申请CPU（就绪）的次序。Gantt图（到达次序：P1，P2，P3）processBursttimeP127P23P35P1P2P30273035

先到先服务算法FCFS（FirstComeFirstServe)按进程申请CPU（就绪）的次序。Process

Arrivaltime

BursttimeP1027P213P325CPU调度状况可用Gantt图表示．0273035P1P2P3

先到先服务算法(Cont.)进程到达时间运行时间开始时间完成时间周转时间带权周转时间P1027027271P2132730299.67P3253035336.6平均周转时间

=(27+29+33)/3=29.67平均带权周转时间

=(1+9.67+6.6)/3=5.760273035P1P2P3

先到先服务算法(Cont.)优点：“公平”；缺点:短作业等待时间长。

短作业优先SJF（ShortestJobFirst)按CPUburst长度Process

Arrivaltime

BursttimeP1012P205P307P403GantChart0381527P1P2P3P4

短作业优先0381527P1P2P3P4进程到达时间运行时间开始时间完成时间周转时间带权周转时间P10121527272.25P2053881.6P307815152.14P4030331平均周转时间=(27+8+15+3)/4=13.25

平均带权周转时间=(2.25+1.6+2.14+1)/4=1.75

短作业优先特点：假定所有任务同时到达，平均等待时间最短。长作业可能被饿死。下一个CPUburst的长度估算令τn是估计的第n个CPU阵发期的长度，tn的值是进程最近一次CPU阵发期长度，则有如下估算公式：τn+1=αtn+(1-α)τn参数α(0≤α≤1)控制tn和τn在公式中起的作用：当α=0时，τn+1=τn；当α=1时，τn+1=tn。通常α取0.5。最高响应比优先(HRN)HighestResponseRatioNextRR=(BT+WT)/BT=1+WT/BT其中:BT=bursttimeWT=waittime优点:同时到达任务,短者优先长作业随等待时间增加响应比增加

最高优先数算法(HPF)静态优先数(static)优先数在进程创建时分配，生存期内不变。响应速度慢，开销小。适合批处理进程动态优先数(dynamic)进程创建时继承优先数，生存期内可以修改。响应速度快，开销大。适用于实时系统

最高优先数算法(Cont.)非剥夺式静态优先数获得处理机的进程运行，直至终止等待剥夺式动(静)态优先数获得处理机的进程运行，直至终止等待出现高优先级的进程

最高优先数算法(Cont.)可抢占CPUProcess

Arrivaltime

Priority

BursttimeP1008P2215P3437P4023P5572GanttChart

0

3

4

5

7

131725P1P4P2P2P3P3P5

最高优先数算法(Cont.)进程到达时间运行时间优先级开始时间完成时间周转时间带权周转时间P10801725253.13P2251317153P347341391.29P40320331P55275721平均周转时间=(25+15+9+3+2)/5=38.8

平均带权周转时间=(3.13+3+1.29+1+1)/5=1.88

0

3

4

5

7

131725P1P4P2P2P3P3P5

最高优先数算法(Cont.)例子UNIX：preemptive+dynamicpriority（可抢占CPU动态优先数）。计算公式：p_pri=min{127,USER+p_cpu/16+p_nice}定义USER=100；p_cpu:运行进程每20ms加1（优先级降低），其它进程每1200ms减10（优先级提高）；p_nice:可以通过系统调用nice(…)修改的量：规定用户进程0~20之间（低），系统进程-20~+20之间（高）。调度时取p_pri最小的。

循环轮转算法(RR)RoundRobin(RR)基本轮转时间片(quantum,timeslice)长度固定，不变；所有进程等速向前推进。改进轮转时间片长度不定，可变。适用于分时系统

循环轮转算法(Cont.)时间片长度：几十毫秒几百毫秒(eg.50ms)过长：响应速度慢；过短：系统开销(overhead)大。适应系统：分时

多级队列算法(MLQ)多级队列多个就绪队列，进程所属的队列固定。例如：通用系统中：队列1：实时进程就绪队列（HPF）队列2：分时进程就绪队列（RR）队列3：批处理进程就绪队列（HPF）

最短剩余时间优先(SRTN)ShortestRemainingTimeNext可剥夺SJFProcess

Arrivaltime

BursttimeP1012P215P337P453Gantt图01691627P1P2P3P1P4

最短剩余时间优先(SRTN)进程到达时间运行时间开始时间完成时间周转时间带权周转时间P1012027272.25P2151651P337916131.86P4536941.33平均周转时=(27+5+13+4)/4=12.25平均带权周转时间=(2.25+1+1.86+1.33)=1.61

01691627P1P2P3P1P反馈排队算法(FB)Feed-Back:多个就绪队列，进程所属队列可变。Q1（RR,HPF）Q2（RR,HPF）Qn（RR,HPF）运行s1时间片运行s2时间片….创建唤醒优先级时间片运行sn时间片

反馈排队算法(Cont.)调度效果：资源利用率高P1等待P2占有的资源R,P2释放R,分给P1,P1被唤醒,进入最高级队列,可尽早投入运行,使用资源R；响应速度快交互式进程经常进入等待状态(等待用户输入),一旦被唤醒(输入完成),进入最高级队列,可尽快被调度选中,投入运行,反应及时；系统开销小计算量大的进程用完前面n-1级时间片,没有处理完,落入底层队列,调度频率下降,但每次获得较长的时间片。FeedBack3.2.2处理机调度时机中断处理完毕，没有嵌套中断，即将返回目态。目态（Pi运行）目态（Pj运行）管态管态…...中断中断中断返回返回返回Pi=Pj:未发生进程切换；Pi<>Pj:发生了进程切换。3.2.2处理机调度时机(Cont.)必然引起进程切换的中断进程自愿结束,exit()进程被强行终止；非法指令，越界，kill进程等待可能引起进程切换的中断时钟系统调用3.2.3处理机调度过程保存下降进程的现场系统栈PCB选择上升进程按处理机调度算法恢复上升进程的现场PCB寄存器先恢复通用寄存器和地址寄存器,最后恢复PSW,PCPSW和PC必须用一条指令恢复3.3调度级别与多级调度3.3.1交换与中级调度Swappingandmid-levelscheduling3.3.2作业与高级调度Jobandhigh-levelscheduling处理机调度为低级调度CPUscheduling=lowlevelscheduling3.3.1交换与中级调度术语交换(swapping)中级调度(mid-levelscheduling)并发度(degreeofmulti-programming)目标：控制并发度并发度过高系统开销大响应速度慢内存等资源紧张进程(线程)频繁进入等待状态Moredeadlocks3.3.1交换与中级调度剥夺就绪等待运行

选中等待事件事件发生就绪挂起等待挂起无终止创建创建结束换出换出换入换入事件发生UNIX的中级调度（sched#0)移入SRUN状态进程如内存不够，移出SWAIT和SSTOP状态进程；如还不够，移出SSLEEP和SRUN状态进程；条件：待移入进程在外存时间>=3秒；待移出进程在内存时间>=2秒。3.3.2作业与高级调度作业状态:提交:输入机向输入井传送后备:在输入井,尚未进入内存执行:分解为进程,在内存处理完成:处理完毕,结果在输出井退出:由输出井向打印机传送3.3.2作业与高级调度状态转换:提交后备:由SPOOLing输入进程完成SimultaneousPeripheralOperationOn-Line后备执行:由作业调度(1)(高级调度)完成高级调度:系统进程执行完成:由作业调度(2)完成完成退出:由SPOOLing输出进程完成提交后备执行完成退出SPOOLing输入作业调度1作业调度2SPOOLing输出作业调度算法适合批作业调度的算法先到先服务算法(FCFS)优先数调度算法(HPF)短作业优先调度算法(SJF)最高响应比优先调度算法(HRN)不适合批作业调度的算法时间片轮转算法(RR)反馈排队算法(FB)3.4实时调度(real-timescheduling)实时任务：具有明确时间约束的计算任务。Eg.某时刻前必须开始处理某时刻前必须处理完毕实时调度：合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。实时任务分类硬实时vs.软实时

硬实时(hardreal-time):必须满足任务截止期要求.软实时(softreal-time):期望满足截止期要求.周期性vs.随机性

周期性:每隔固定时间发生一次随机性:由随机事件触发，其发生时刻不确定术语解释Readytime:就绪时间Startingdeadline:开始截止期Processingtime:处理时间Completiondeadline:完成截止期Occurringfrequency:发生频率周期性实时事务周期性实时事务:令Ci为任务Pi处理时间，Ti为任务Pi的发生周期，则任务P1,…,Pm可调度的必要条件为：

周期性实时事务例：T1=100,T2=200,T3=500(ms)C1=50,C2=30,C3=100(ms)C1/T1+C2/T2+C3/T3=0.5+0.15+0.2=0.85<1满足可调度的必要条件周期性实时事务进程就绪时间处理时间完成截止期发生周期A0102020B025505010/20+25/50=1,可调度(不考虑开销)例子ProcessArrivaltimeExecutiontimecompletiondeadlineA(1)A(2)A(3)A(4)A(5)…...B(1)B(2)020406080…...0501010101010……252520406080100…...501003.4.1最早截止期调度EDF（EarliestDeadlineFirst)优先选择截止期最早的实时任务可抢先可以证明：对EDF来说，可调度充分条件是：在不可调度的条件下，可使错过截止期任务最小化例子:EarliestDeadlineFirst0102030405060708090100TimeA2A2dlA3A3dlA4A4dlB1A1A1dlB1dlB2B2dlA5A5dlA1B1A2B1A3B2A5B2A4A1A2B1A3A4A5B23.4.2速率单调调度RMS（RateMonotonicScheduling）提出于1973年面向周期性实时事务，非剥夺式优先调度发生周期最短（频度最高）的实时任务可调度条件：RMS的上限值n123456┇1.00.8280.7790.7560.7430.734┇ln20.693RMSvs.EDFRMS可调度条件强于EDFRMS调度较EDF实现简单RMS例子：进程ＴiCiA10020B15040C350100可调度，具体调度结果：A1B1C1A2B2A3A4B3C2020601601802202403003203604603.5多处理机调度问题：Mprocesses(threads)NprocessorsSMP：symmetricmulti-processorsallprocessorsareidentical(homogeneous)目标：load-sharingseparatereadyqueueforeachprocessor,notreallybalanced;commonreadyqueueQforallprocessorseachprocessoraccessesQonitsown,master/slaveassignment.3.5.1自调度(selfscheduling)均衡调度(balancedscheduling)一个就绪队列(多处理机访问互斥)优点不需要专门的处理机从事任务分派工作任务分配均衡缺点当CPU较多时,就绪队列成为瓶颈线程两次调度可能处于不同处理机不能保证同组线程同时调度自调度(selfscheduling)就绪队列进程(线程)进程(线程)进程(线程)CPUCPUCPU自调度(selfscheduling)例子:Mach,改进的自调度全局队列:系统一个局部队列:每个CPU一个调度时首先考虑局部队列然后考虑全局队列3.5.2组调度(gangscheduling)将一组相关(合作)的线程同时分派到多个处理机上运行避免合作线程之间的相互等待降低开销,提高运行效率例子:Cm*Taskforce(一组相关的计算)3.6系统举例Linux进程调度Windows2000/XP线程调度UNIX进程调度（见第12章）3.6.1Linux进程调度三种特征进程Real-timeFIFOReal-timeRoundRobinTimesharingGoodness-basedschedulingpriority0-40,(缺省