《第三章-操作系统课件.ppt》由会员分享，可在线阅读，更多相关《第三章-操作系统课件.ppt（123页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、3.1 进程管理的基本概念进程管理的基本概念进程控制块及进程状态进程控制（进程间的相互作用）进程调度（CPU调度）实时系统的进程调度线 程进程调度讨论3.1 进程管理的基本概念3.1.1 程序的运行方式1、顺序运行、顺序运行2、并发运行、并发运行3.1 进程管理的基本概念3.1.1 程序的运行方式1、顺序运行、顺序运行程序：程序：指令或语句序列，体现了某种算法，指令或语句序列，体现了某种算法，所有程序是顺序的所有程序是顺序的顺序环境：顺序环境：在计算机系统中只有一个程序在运行，在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行这个程序独占系统中所有资源，其执行不受外界影响不受
2、外界影响3.1 进程管理的基本概念3.1.1 程序的运行方式1、顺序运行、顺序运行特征：特征：程序执行的顺序性程序执行的顺序性:程序执行的封闭性程序执行的封闭性:独占资源，执行过程中不受外界影响独占资源，执行过程中不受外界影响独占资源，执行过程中不受外界影响独占资源，执行过程中不受外界影响程序执行结果的确定性程序执行结果的确定性 即：程序结果的可再现性即：程序结果的可再现性 程序运行结果与程序执行速度无关，只要程序运行结果与程序执行速度无关，只要初始状态相同，结果应相同初始状态相同，结果应相同3.1 进程管理的基本概念3.1.1 程序的运行方式2、并发运行、并发运行并发环境：并发环境：在一定时
3、间内物理机器上有两个或两个以上的程序同在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先处于开始运行但尚未结束的状态，并且次序不是事先确定的确定的,（目的是为了提高（目的是为了提高CPU的利用率）的利用率）BAABBAAB3.1 进程管理的基本概念3.1.1 程序的运行方式2 2、并发运行、并发运行特征：特征：（1）异步特征：在并发环境下程序的执行是间断性的，）异步特征：在并发环境下程序的执行是间断性的，执行执行执行执行停停停停执行执行执行执行（2）资源共享：）资源共享：系统中资源被多个进程使用系统中资源被多个进程使用系统中资源被多个进程使用系统中资源
4、被多个进程使用（3）独立性和制约性：）独立性和制约性：独立的相对速度、起始时间独立的相对速度、起始时间独立的相对速度、起始时间独立的相对速度、起始时间 进程之间可相互作用（相互进程之间可相互作用（相互进程之间可相互作用（相互进程之间可相互作用（相互制约）可分为直接作用和间接作用制约）可分为直接作用和间接作用制约）可分为直接作用和间接作用制约）可分为直接作用和间接作用（4）程序结果的不可再现性：）程序结果的不可再现性：并发程序执行的结果与其执行的相对速度有关，是并发程序执行的结果与其执行的相对速度有关，是并发程序执行的结果与其执行的相对速度有关，是并发程序执行的结果与其执行的相对速度有关，是不确
5、定的不确定的不确定的不确定的（以并发交易事务为例）（以并发交易事务为例）BAABBAAB3.1 进程管理的基本概念3.1.1 程序的运行方式2、并发运行、并发运行引入并发的目的：引入并发的目的：引入并发是为了提高资源利用率，从而提高系统效率引入并发是为了提高资源利用率，从而提高系统效率引入并发是为了提高资源利用率，从而提高系统效率引入并发是为了提高资源利用率，从而提高系统效率并发与并行概念的区别：并发与并行概念的区别：Concurrency：并发：并发Parallel ：并行：并行3.1 进程管理的基本概念3.1.2 进程概念定义：程序的执行过程。是定义：程序的执行过程。是可以独立申请并获得系
6、统资可以独立申请并获得系统资源，与其它进程并发执行的源，与其它进程并发执行的基本单位。基本单位。3.1 进程管理的基本概念3.1.2 进程概念进程的五个特征：进程的五个特征：动态特征：从运行的角度动态特征：从运行的角度并发特征：从宏观的角度并发特征：从宏观的角度独立特征：从资源分配的角度独立特征：从资源分配的角度异步特征：从运行过程的角度异步特征：从运行过程的角度结构特征：从进程产生的角度结构特征：从进程产生的角度3.1 进程管理的基本概念3.1.3 进程管理的主要功能1、进程控制、进程控制 创建、撤销、阻塞、唤醒、进创建、撤销、阻塞、唤醒、进程同步、通信控制、进程死锁防范程同步、通信控制、进
7、程死锁防范等。等。2、进度调度、进度调度 在进程间进行在进程间进行CPU调度。调度。3.2 进程控制块及进程状态进程控制块（Process Control Block):操作系统对进程进行全局管理的一个数据结构。系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志 进程与PCB是一一对应的3.2 进程控制块及进程状态3.2.1 进程控制块（Process Control Block)内容2、调度信息：、调度信息：进程优先级；进程优先级；进程状态信息进程状态信息其它状态信息其它状态信息1
8、、进程标识：、进程标识：进程的内部标识：（通常是整数，唯一的）进程的内部标识：（通常是整数，唯一的）pid 进程的外部标识：（进程名字）进程的外部标识：（进程名字）mame pid=GetInternalName(name);3、进程上下文、进程上下文（一些重要的现场信息）（一些重要的现场信息）（1）、通用寄存器的信息）、通用寄存器的信息 （2）、程序状态字（）、程序状态字（PSW）值）值 （3）、程序计数器（）、程序计数器（PC）（4）、进程的堆栈指针）、进程的堆栈指针4、进程控制信息、进程控制信息 （1）、内容地址）、内容地址 （2）、资源清单）、资源清单 （3）、同步与通信信息（机制）、
9、同步与通信信息（机制）（4）、外存地址）、外存地址 （5）、家族信息）、家族信息 （6）、链接指针）、链接指针3.2 进程控制块及进程状态3.2.1 进程基本状态及状态变迁 通常进程的三种基本状态通常进程的三种基本状态（就绪、运（就绪、运行、阻塞）行、阻塞）进程在生命消亡前处于且仅处于三种进程在生命消亡前处于且仅处于三种基本状态之一基本状态之一 不同系统设置的进程状态数目不同不同系统设置的进程状态数目不同3.2 进程控制块及进程状态3.2.2 进程基本状态及状态变迁1、进程的基本状态：、进程的基本状态：（1）就绪（）就绪（Ready)（2）运行（）运行（Running）（3）阻塞（）阻塞（Bl
10、ocked）3.2 进程控制块及进程状态3.2.2 进程基本状态及状态变迁1、状态变迁：、状态变迁：活动活动挂起挂起事件事件发生发生事件事件发生发生等待等待事件事件挂起挂起调度调度超时超时释放释放活动活动挂起挂起3.2 进程控制块及进程状态3.2.3 扩展状态挂起：将进程调入到外存上挂起：将进程调入到外存上去。去。3.2 进程控制块及进程状态3.2.4 PCB的组织结构挂起的进挂起的进程被调到程被调到外存上去外存上去系系统统区区进程进程H进程进程D进程进程C进程进程I进程进程E进程进程G就绪队列就绪队列阻塞队列阻塞队列运行队列运行队列挂起就绪队列挂起就绪队列挂起阻塞队列挂起阻塞队列用用户户区区
11、PCBIPCBIPCBIPCBIPCBIPCBIPCBIPCBIPCBI进程进程A进程进程B进程进程F3.3 进程控制为了防止操作系统及关键数据受到破坏，通常将处理机的状态分为系统态和用户态。OS内核通常是运行在系统态的，进程控制是由OS内核实现的。3.3 进程控制为了防止操作系统及关键数据受到破坏，通常将处理机的状态分为系统态和用户态。OS内核通常是运行在系统态的，进程控制是由OS内核实现的。OS内核使用原语进行进程控制,这些原语通常分为下面四类:控制进程用的原语控制进程用的原语:创建、撤消、阻塞、唤醒、挂起、激活、调度创建、撤消、阻塞、唤醒、挂起、激活、调度控制通信用的原语控制通信用的原语
12、:消息发送、消息接收消息发送、消息接收资源互斥与同步用的原语资源互斥与同步用的原语:P(wait)与与V(signal)操作原语操作原语3.3.1 进程创建与撤消原语1、创建原语Create_Process()提交一个批处理作业用户登录由OS创建，用以向一用户提供服务(如：打印文件)由已存在的一进程创建一个用户程序可创建成多个进程进程何时创建?索取一个空白的PCB块赋予一个统一进程标识符初始化进程控制块设置相应的链接Pid优先级内存地址资源清单家族信息PCB现场信息PCB进程状态信息把新进程加到就绪队列的链表中将程序代码和数据装入内存可选项结束从PCB的链表上的空闲队列获取一个指针，将当前创建
13、的进程指向该位置3.3.1 进程创建与撤消原语1、撤消原语Destroy(name)批处理作业发出暂停（Halt）指令用户退出登录进程执行一中止服务请求出错及失败因素运行正常结束进程何时撤消？FLAG :=false中止进程Kill(nameKill(name)以递归方式对该以递归方式对该进程及其子进程进程及其子进程进行中止操作，进行中止操作，并回收所占用的并回收所占用的所有资源和所有资源和PCBPCB若需要调度，则运行系统的调度程序。可选项结束将该系统的调度标志置为不可调度。3.3.2阻塞与唤醒原语 1、阻塞原语Block()原因有以下几种：原因有以下几种：等待等待I/OI/O请求资源得不到
14、满足请求资源得不到满足进程同步约束进程同步约束服务进程无服务任务服务进程无服务任务进程为何会被阻塞？获取进程的获取进程的内部标识内部标识j从运行队列上摘下j Remove(RunQueue,j)J(状):=“Blocked”运行调度程序结束j:=GetInternalname()保护现场 J(进程上下文)：=CPU现场信息。将该进程的状态改为阻塞将进程j插入阻塞队列 J(进程上下文)：=CPU现场信息。Scheduler().3.3.2阻塞与唤醒原语 1、唤醒原语唤醒原语 Wakeup()引起进程唤醒的原因源自进程的阻塞原因，因此相应地有以下几种：所等的I/O操作已完成。请求的资源得到了满足。
15、进程同步约束已撤消。服务进程收到新的任务。进程何时会被阻塞？当前进程的当前进程的CPU现场信现场信息压栈息压栈 从阻塞队列从阻塞队列上查找等待上查找等待该事件的进该事件的进程程PCB PCB(状态状态):=“Ready”结束将将PCB从从阻塞队列阻塞队列上摘下来上摘下来 将该进程的状态改为就绪将PCB挂入就绪队列 Insert(ReadyQueue，PCB)。/将PCB挂入就绪队列 恢复被当前中断进程的上下文，让被中断的进程恢复运行。当前进程的当前进程的CPU现场信现场信息出栈息出栈 3.3.3挂起和激活原语 1、挂起原语挂起原语 Suspend(name)虚拟存储管理方式中，当虚拟存储管理方
16、式中，当前进程的内存空间太少。前进程的内存空间太少。当前进程的运行代码无法当前进程的运行代码无法装入，系统需要挂起内存装入，系统需要挂起内存中部分进程。中部分进程。根据操作系统的需要，将根据操作系统的需要，将部分进程挂起，以便改善部分进程挂起，以便改善运行性能。运行性能。应用户的要求，将用户进应用户的要求，将用户进程挂起。程挂起。应父进程要求，将其子进应父进程要求，将其子进程挂起。程挂起。进程为何会被挂起？找到要挂起进程的pid 将将j从所在队列从所在队列XQueue上摘下上摘下 PCB(状态状态):=“SReady”结束申请外存交换区空申请外存交换区空间，其地址写入间，其地址写入PCB（外存
17、地址）（外存地址）回收回收j（内存地址）（内存地址）中记录的内存空中记录的内存空间。间。将j挂入静止就绪队列 j:=GetInternalname(name)Remove(XQueue,j)启动I/O，将被阻塞的进程写到交换区 Ready?将j挂入静止阻塞队列 PCB(状态状态):=“SBlock”3.3.3挂起和激活原语 1、激活原语激活原语 Active(name)当一个进程运行完当一个进程运行完毕，若当前内存空毕，若当前内存空间并不紧张，需要间并不紧张，需要增加进程数量。增加进程数量。应用户要求。应用户要求。应父进程的要求，应父进程的要求，将其子进程激活。将其子进程激活。进程自身设定的挂
18、进程自身设定的挂起周期已结束。起周期已结束。进程为何会被激活？找到要激活进程的pid 将将j从所在队列从所在队列XQueue上摘下上摘下 PCB(状态状态):=“Ready”结束启动I/O，将进程加载到内存中 按其按其PCB登记的空登记的空间需求申请内存间需求申请内存 将j挂入就绪队列 j:=GetInternalname(name)Remove(XQueue,j)SReady?将j挂入阻塞队列 PCB(状态状态):=“Block”归还外存交换区空间3.4 进程调度在操作系统中，进程调度是整个管理系统的核心，其采用的调度策略直接影响着系统的性能，在早期的单道批处理系统中，进程调度与作业调度的区
19、分并不明显，所起的作用仅仅是作业的运行切换。而在多道程序设计中，进程调度成了多进程并发运行的基础和关键的环节。它的作用是，选择一个就绪的进程投入运行。由于进程调度比作业调度更靠近硬件，因此也称为低级调度。3.4.1 两种调度模式调度方式调度方式非强占式调度强占式调度3.4.1 两种调度模式1、非强占式调度当一个进程占有处理机后，可一直运行下去。如果该进程不主动让出处理机，则系统不强迫它交出来。在这种方式中，可能引起当前进程主动放弃处理机控制权的情况有两个：（1 1）进程运行完毕推出或遇到不可挽回的故障。）进程运行完毕推出或遇到不可挽回的故障。（2 2）运行受阻。）运行受阻。在多道批处理系统中，
20、只要出现两种情况之一时，正在运行的进程就将主动放弃CPU。3.4.1 两种调度模式1、非强占式调度t0t1t2t3t4t运行P1运行P2运行KernelCpu状态3.4.1 两种调度模式2、强占式调度抢占调度也称做剥夺调度，主要指的是，在系统正常运行期间，如果某种事件某种事件出现，系统将迫使正在运行的进程停下来，将CPU控制权交给其他进程。3.4.1 两种调度模式2、强占式调度进进程程标识标识创创建建时时刻刻运行运行长长度度/h/h优优先先级级ProcessProcessA A8.000.107ProcessProcessB B8.050.1010ProcessProcessC C8.080.
21、254ProcessProcessD D8.300.0553.4.1 两种调度模式2、强占式调度进进程程标识标识创创建建时时刻刻运行运行长长度度/h/h优优先先级级ProcessProcessA A8.000.107ProcessProcessB B8.050.1010ProcessProcessC C8.080.254ProcessProcessD D8.300.055PAPBPCPD8.00PB8.05 8.088.158.208.308.35PAPC8.503.4.1 两种调度模式3、调度算法缩缩写写算法名称算法名称算法目算法目标标FCFSFCFS先进入就绪进程队列的进程先调度先进入就绪
22、进程队列的进程先调度公平性公平性SPFSPF(shortest Process First)(shortest Process First)最短进程优先调度。最短进程优先调度。照照顾顾短运行短运行时间时间的的进进程任程任务务HPFHPF(Highest Priority First)(Highest Priority First)算法，最高优先级调度。算法，最高优先级调度。特特权权任任务务优优先先，保保障障紧紧急急任任务务执执行的及行的及时时性性HRFHRF(Highest Response First)(Highest Response First)算法，最高算法，最高响应比优先调度。响应比
23、优先调度。在在多多用用户户系系统统中中，使使多多用用户户的的终终端响端响应应性最好性最好RRRR(Round Robin)(Round Robin)算法，算法，轮转调轮转调度。度。使系使系统统的平均周的平均周转时间转时间最短最短MLPMLP(Multilevel Priority)(Multilevel Priority)算法，多算法，多队队列列调调度。度。对对任任务进务进行分行分类类管理和管理和调调度度MLFMLF(Multilevel(Multilevel Feedback)Feedback)算算法法，多多级级反反馈馈队队列列调调度。度。兼兼顾顾长长时时间间和和短短时时间间的的进进行行任任
24、务务SRTSRT(Shortest(Shortest Remain Remain Time)Time)算算法法，最最短短剩剩余余时间优时间优先先调调度。度。满满足足实时实时系系统统的要求的要求3.4.2 RR算法算法 这是一种按时间片进行轮转调度的算法。但正在进行的进程用完自己的时间片后，管理程序停止它的运行，并将他转入就需对列尾部，然后重新分配CPU。在这种情况下，进程失去CPU不是自愿的，而是被剥夺的。就绪队列3.4.2 RR算法算法1、RR算法的调度过程算法的调度过程RR算法是分时系统中采用的主要算法。该算法也可用于批处理系统或实时系统中，CPU每次运行管理程序的切换时间非常小，而且各次
25、运行都是等长的。(下图为有四人终端的RR例子)P1P2P3P4ScScScScP1P2P3P4P1P2P3P4ScScScScP1P2P3P4ScScScScP1P2P3P4ScScScSctSc3.4.2 RR算法算法1、RR算法的调度过程算法的调度过程RR算法是分时系统中采用的主要算法。该算法也可用于批处理系统或实时系统中，CPU每次运行管理程序的切换时间非常小，而且各次运行都是等长的。(下图为有四个不同运行时间任务的RR例子)P1P2P3P4ScScScScP1P2P3P4P1P2P3P4ScScScSctScP4P4P4P3P3P1P1P1P1P1P2P1P3P4ScScScP1P4S
26、cScP1ScP1ScScScSc3.4.2 RR算法算法2.时间片的选取时间片的选取 在轮转调度中，时间片的大小对系统的性能影响很大。对于一个有m个终端进程的系统，若时间片的长度规定为q，管理程序每次的切换时间为M，则轮转周期Q为：Q=(q+M)m这里，这里，M通常是一个常量，当通常是一个常量，当Mq时，处理机的利用率才比较高。当时，处理机的利用率才比较高。当q选得选得过于小时，调度周期将缩短，那么进程切换花费的时间在整个调度周过于小时，调度周期将缩短，那么进程切换花费的时间在整个调度周期中所占的比例将增大。这种情况下处理机的利用率不会太高。期中所占的比例将增大。这种情况下处理机的利用率不会
27、太高。时间片时间片q3.4.2 RR算法算法2.时间片的选取时间片的选取 Q=(q+M)m如果时间片太长，虽然如果时间片太长，虽然CPU有效利用率上去了，但响应时间会降低。有效利用率上去了，但响应时间会降低。P1P2P3P4P4P4P4P3P3P1P1P1ScP2ScScP3P3P3P4P4P4P4Sc时间片时间片qP1P1P1P1时间片时间片q时间片时间片qt3.4.2 RR算法算法2.时间片的选取时间片的选取 时间片的确定通常有下面几个原则：时间片的确定通常有下面几个原则：(1)进程的道数较多时，进程的道数较多时，q就选得小一些；反之，可选的大一些。就选得小一些；反之，可选的大一些。(2)
28、系统要求的响应时间比较苛刻的时候，系统要求的响应时间比较苛刻的时候，q就选得小一些；反之，可选得大就选得小一些；反之，可选得大一些。一些。(3)计算机的运算速度较慢的时候，计算机的运算速度较慢的时候，q就选得小一些；反之，可选得大一些。就选得小一些；反之，可选得大一些。Q=(q+M)m时间片时间片qP1P2P3P4P4P4P4P3P3P1P1P1ScP2ScScP3P3P3P4P4P4P4Sc时间片时间片qP1P1P1P1时间片时间片q时间片时间片qt3.4.2 RR算法算法2.时间片的选取时间片的选取 Q=(q+M)m时间片的确定通常有下面几个原则：时间片的确定通常有下面几个原则：若把若把R
29、R算法用于多终端进程的并发控制中，由于终端用户能够算法用于多终端进程的并发控制中，由于终端用户能够接受响应时间一般不超过接受响应时间一般不超过23秒，所以进程的调度秒，所以进程的调度Q最大应最大应以以3s为界。比如，假设系统支持为界。比如，假设系统支持500个终端用户，那么时间个终端用户，那么时间片的长度片的长度q应满足应满足 q=Q/500=3000/500=600 ms3.4.3 MLP调度算法调度算法这是一种混合调度算法。假设系统设有这是一种混合调度算法。假设系统设有n+1个就绪队列，他们按调度优先级的个就绪队列，他们按调度优先级的大小依次排列成下图的形式。其中有一个前台队列和大小依次排
30、列成下图的形式。其中有一个前台队列和n个后台队列，那个后台队列，那么，系统的调度将对这么，系统的调度将对这n个队列由上而下地进行。个队列由上而下地进行。前台前台后台后台1后台后台2后台后台n:PCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCBPCB3.4.4 MLF调度算法调度算法在一个支持优先级调度的系统中，可以设立多个就绪在一个支持优先级调度的系统中，可以设立多个就绪队列，以体现对紧迫型作业的照顾，进而将队列，以体现对紧迫型作业的照顾，进而将RR算算法运用
31、到批处理系统中。法运用到批处理系统中。多级反馈队列调度是一种被普遍认可的调度方法。该多级反馈队列调度是一种被普遍认可的调度方法。该方法需要在系统中设置多个就绪队列，每个队列有方法需要在系统中设置多个就绪队列，每个队列有一个优先数（一个优先数（p）和一个时间片（）和一个时间片（q）。系统按照）。系统按照队列的优先数大小进行调度。即，优先调度队列的优先数大小进行调度。即，优先调度p较高较高的队列，当队列为空时再调度的队列，当队列为空时再调度p较低的队列。在各较低的队列。在各个队列内部的调度上，系统采用轮转调度算法。当个队列内部的调度上，系统采用轮转调度算法。当一个进程在某个队列上运行完一个时间片后
32、，若不一个进程在某个队列上运行完一个时间片后，若不能运行完成，则转入下一个对列。能运行完成，则转入下一个对列。3.4.4 MLF调度算法调度算法队列队列i优先数优先数pi队列队列i时间片时间片qi。时间片时间片:q1q2q3BAt3.5.1实时任务的分类及其调度方法实时任务的分类及其调度方法非周期性任务是指既没有运行规律性，也不具有运行周期性的任务。这类任务按时间响应的要求苛刻程度，可分为紧迫型、普通型和宽松型。不同类型中采用的调度算法也各有所异，下面是实时系统中常用的调度算法。3.5.1实时任务的分类及其调度方法实时任务的分类及其调度方法1、紧迫型的实时任务调度紧迫型的实时任务调度紧迫性强的
33、任务多见于一些专用的、响应时间要求特别苛刻的数据采集和控制系统中，所要求的响应时间很短，一般是微秒量级的。解决的方法就是，采用“立即抢占的HPF”调度算法。进程A进程A进程B进程B进程A调度响应时间优先级：BAt立即抢占（Immediate Preemption）的含义是，当一个高优先级的任务到来时，可以立即抢占当前进程的处理机。难点：释放临界资源难点：释放临界资源 3.5.1实时任务的分类及其调度方法实时任务的分类及其调度方法2.2.普通型的实施任务调度普通型的实施任务调度 目前，大多数自动控制系统对相应时间的要求都不是很高，一般是毫秒量级的。由于它允许的相应时间长度和时钟中断的周期基本吻合
34、，所以可采用“基于时钟中断抢占的高优先级调度”算法。算法的设计思想：当一个实施任务T进入内存时，首先将其挂到就绪队列上等待。等到时钟中断到来时，系统比较T的优先级是否高于当前任务。如果高于，就剥夺当前任务的处理机，调度T投入运行；否则将继续执行当前任务。该算法要求为每一个任务制定一个优先级，以便调度时参考。进程A进程A进程B进程B进程A调度响应时间优先级：BA时间中时间中断周期断周期时间中时间中断周期断周期时间中时间中断周期断周期时间中时间中断周期断周期时间中时间中断周期断周期时间中时间中断周期断周期时间中时间中断周期断周期时间中时间中断周期断周期时间中时间中断周期断周期t3.5.1实时任务的
35、分类及其调度方法实时任务的分类及其调度方法3宽松型的实时任务调度宽松型的实时任务调度宽松型实时任务要求的响应时间比较宽松型实时任务要求的响应时间比较长，一般可达数百毫秒，甚至数秒。长，一般可达数百毫秒，甚至数秒。这类任务的要求差异很大，通常又这类任务的要求差异很大，通常又有很多不同的处理。常见的算法有：有很多不同的处理。常见的算法有：(1)非抢占的非抢占的HPE调度算法调度算法(2)RR算法算法3.5.1实时任务的分类及其调度方法实时任务的分类及其调度方法3宽松型的实时任务调度宽松型的实时任务调度 (1)非抢占的非抢占的HPE调度算法调度算法这一算法的实现过程比较简单，也不需要额外的系统开销。
36、当一个具有高优先级的这一算法的实现过程比较简单，也不需要额外的系统开销。当一个具有高优先级的实时任务进入内存后，首先挂在就绪队列上。直到当前进程运行完成或受阻，实时任务进入内存后，首先挂在就绪队列上。直到当前进程运行完成或受阻，系统启动任务调度，可使就绪队列上的高优先任务被调度运行。这种情况下，系统启动任务调度，可使就绪队列上的高优先任务被调度运行。这种情况下，实时任务的响应时间不会超过当前任务的最大周转时间。实时任务的响应时间不会超过当前任务的最大周转时间。进程A进程A进程X进程X(实时)调度响应时间t进程F进程E进程D进程C进程B进程X就绪进程队列:X 的优先级BCDEF3.5.1实时任务
37、的分类及其调度方法实时任务的分类及其调度方法3宽松型的实时任务调度宽松型的实时任务调度(2)RR算法算法有些实时任务的响应时间要求非常宽松，有的可以达到数秒。比如信息查询系统就有些实时任务的响应时间要求非常宽松，有的可以达到数秒。比如信息查询系统就属于此类任务。此类任务既可以进入批处理系统按上面说的高优先级算法进行属于此类任务。此类任务既可以进入批处理系统按上面说的高优先级算法进行调度，也可以作为交互型的任务，通过终端提交给系统，按时间片实行调度，也可以作为交互型的任务，通过终端提交给系统，按时间片实行RR调度。调度。进程A进程A进程B实时进程B调度响应时间优先级：BAt时间片进程A时间片时间
38、片进程B时进程A时间片3.5.2周期性任务调度周期性任务调度 周周期期性性任任务务代代码码长长度度系系统统周周期期长长度度资资源源需需求求每每个个周周期期执执行行时时间间信息提交一个周期任务第i次运行前的剩余时间F(i)的计算公式是：(SRT（最小剩余时间）调度算法。)F(iF(i)=)=iTiTA A-T-TSASA t tTA:任务A的周期长度(两次任务之间的间隔)；TSA:任务A的每次执行时间长度；t:为系统的当前时间。F(i)越小，说明任务的截止时间离当前时间越近，就越迫切。系统可以按照最小F(i)者优先原则进行调度，相应的算法称为SRT（最小剩余时间）调度算法。3.5.2周期性任务调
39、度周期性任务调度 0 80 160 2400 50 100 150 200 250F(iF(i)=)=iTiTA A-T-TSASA t t任务A的周期长度为50ms，执行时间为10ms/次，松弛时间为40ms。任务B的周期长度为80ms，执行时间为20ms/次，松弛时间为60ms。3.5.2周期性任务调度周期性任务调度 AAAAABBBAB松驰时间松驰时间0 80 160 2400 50 100 150 200 250F(iF(i)=)=iTiTA A-T-TSASA t t任务A的周期长度为50ms，执行时间为10ms/次，松弛时间为40ms。任务B的周期长度为80ms，执行时间为20ms
40、/次，松弛时间为60ms。3.5.2周期性任务调度周期性任务调度 A1A2B1松驰时间松驰时间（1）在时刻为0ms时，A1S=40 B1S=60 A1执行A1B20 80 160 2400 50 100 150 200 250F(iF(i)=)=iTiTA A-T-TSASA t t任务A的周期长度为50ms，执行时间为10ms/次，松弛时间为40ms。任务B的周期长度为80ms，执行时间为20ms/次，松弛时间为60ms。3.5.2周期性任务调度周期性任务调度 A2B1松驰时间松驰时间（2）在时刻为10ms时，A1=END A2还未到达 B1S=50 B1执行A1B2B10 80 160 2
41、400 50 100 150 200 250F(iF(i)=)=iTiTA A-T-TSASA t t任务A的周期长度为50ms，执行时间为10ms/次，松弛时间为40ms。任务B的周期长度为80ms，执行时间为20ms/次，松弛时间为60ms。3.5.2周期性任务调度周期性任务调度 A2（3）在时刻为30ms时，B1=END A2还未到达 B2还未到达 CPU空闲A1B2B10 80 160 2400 50 100 150 200 250F(iF(i)=)=iTiTA A-T-TSASA t t任务A的周期长度为50ms，执行时间为10ms/次，松弛时间为40ms。任务B的周期长度为80ms
42、，执行时间为20ms/次，松弛时间为60ms。3.5.2周期性任务调度周期性任务调度 A2（4）在时刻为50ms时，A1S=40 B2还未到达 A2执行A1B2B1A2A30 80 160 2400 50 100 150 200 250F(iF(i)=)=iTiTA A-T-TSASA t t任务A的周期长度为50ms，执行时间为10ms/次，松弛时间为40ms。任务B的周期长度为80ms，执行时间为20ms/次，松弛时间为60ms。3.5.2周期性任务调度周期性任务调度 A2（5）在时刻为60ms时，A2=END B2还未到达 CPU空闲A1B2B1A2A30 80 160 2400 50
43、100 150 200 250F(iF(i)=)=iTiTA A-T-TSASA t t任务A的周期长度为50ms，执行时间为10ms/次，松弛时间为40ms。任务B的周期长度为80ms，执行时间为20ms/次，松弛时间为60ms。3.5.2周期性任务调度周期性任务调度 A2（6）在时刻为80ms时，A3还未到达,B2S=60 执行B2A1B2B1A2A3B20 80 160 2400 50 100 150 200 250F(iF(i)=)=iTiTA A-T-TSASA t t任务A的周期长度为50ms，执行时间为10ms/次，松弛时间为40ms。任务B的周期长度为80ms，执行时间为20m
44、s/次，松弛时间为60ms。3.5.2周期性任务调度周期性任务调度（7）在时刻为100ms时，A3S=40 B3未到达 A3执行A1 B1A2A3B2 A30 80 160 2400 50 100 150 200 250F(iF(i)=)=iTiTA A-T-TSASA t t任务A的周期长度为50ms，执行时间为10ms/次，松弛时间为40ms。任务B的周期长度为80ms，执行时间为20ms/次，松弛时间为60ms。3.5.2周期性任务调度周期性任务调度（8）在时刻为110ms时，A4 B3未到达 CPU空闲A1 B1A2B2 A3A4B30 80 160 2400 50 100 150 2
45、00 250F(iF(i)=)=iTiTA A-T-TSASA t t任务A的周期长度为50ms，执行时间为10ms/次，松弛时间为40ms。任务B的周期长度为80ms，执行时间为20ms/次，松弛时间为60ms。3.5.2周期性任务调度周期性任务调度（9）在时刻为150ms时，A4s=40 B3未到达 A4执行A1 B1A2B2 A3A4B3周期任务的调度定理：对于单CPU系统中接受的n(n0)个周期任务，每个任务的周期长度为Ti，执行时间为Tsi。只有当下式成立是，系统有望实现调度的必要条件是：3.5.2周期性任务调度周期性任务调度 该定理说明，在只有1台处理机的系统中，所有任务的运行时间
46、与滞留时间之比的总和不能大于一。推广之，在包含N台处理机的系统中，所有任务的这种比例之和不能大于等于N。3.6 线 程 前面介绍的进程管理主要涉及资源分配和调度运行两方面，他们是进程的本质所在。从逻辑上讲这两方面是互相独立的，可以分开处理。事实上近年来开发的很多操作系统都把这两方面区分开，将体现资源所有权的部分定义为进程，调度运行的部分称为线程（Thread）。线程与进程：在支持多线程操作系统中，线程被定理为调度运行的基本单位，而进程仅仅是资源分配和占有实体。3.6.1线程的引入进程的两个基本属性：资源的拥有者：给每个进程分配一虚拟地址空间，保存进程映像，控制一些资源（文件，I/O设备），有状
47、态、优先级、调度调度单位：进程是一个执行轨迹 以上两个属性构成进程并发执行的基础3.6.1线程的引入系统必须完成的操作：创建进程撤消进程进程切换缺点：时间空间开销大，限制并发度的提高3.6.1线程的引入在操作系统中，进程的引入提高了计算机资源的利用效率。但在进一步提高进程的并发性时，人们发现进程切换开销占的比重越来越大，同时进程间通信的效率也受到限制线程的引入正是为了简化进程间的通信，以小的开销来提高进程内的并发程度3.6.1线程的引入线程：有时称轻量级进程 进程中的一个运行实体 是一个CPU调度单位 资源的拥有者还是进程或称任务将原来进程的两个属性分开处理3.6.1线程的引入线程：有执行状态
48、（状态转换）不运行时保存上下文有一个执行栈有一些局部变量的静态存储可存取所在进程的内存和其他资源可以创建、撤消另一个线程3.6.1线程的引入线程和进程：单进程、单线程单进程、多线程多进程、一个进程一个线程多进程、一个进程多个线程3.6.1线程的引入P C B用用户户栈栈单线程进程模型单线程进程模型用户地址空间用户地址空间核核心心栈栈线程控制块：线程控制块：包含了寄存器映像，线程优先数和线程状态信息包含了寄存器映像，线程优先数和线程状态信息3.6.1线程的引入引入线程的好处：引入线程的好处：创建一个新线程花费时间少（结束亦如此）创建一个新线程花费时间少（结束亦如此）两个线程间的切换花费时间少两个
49、线程间的切换花费时间少（如果机器设有（如果机器设有“存储存储 恢复恢复 所有寄存器所有寄存器”指令，则整个切换过指令，则整个切换过程用几条指令即可完成）程用几条指令即可完成）因为同一进程内的线程共享内存和文件，因此它因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核适合多处理机系统们之间相互通信无须调用内核适合多处理机系统适合多处理机系统适合多处理机系统3.6.1线程的引入引入线程的好处：引入线程的好处：创建一个新线程花费时间少（结束亦如此）创建一个新线程花费时间少（结束亦如此）两个线程间的切换花费时间少两个线程间的切换花费时间少（如果机器设有（如果机器设有“存储存储 恢复恢
50、复 所有寄存器所有寄存器”指令，则整个切换过指令，则整个切换过程用几条指令即可完成）程用几条指令即可完成）因为同一进程内的线程共享内存和文件，因此它因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核适合多处理机系统们之间相互通信无须调用内核适合多处理机系统适合多处理机系统适合多处理机系统FS3.6.1线程的引入例子:LANLAN中的一个文件服务器，在一段时间内需要处理几个文中的一个文件服务器，在一段时间内需要处理几个文件请求件请求因此有效的方法是：为每一个请求创建一个线程因此有效的方法是：为每一个请求创建一个线程在一个在一个SMPSMP机器上：多个线程可以同时在不同的处理器上