好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

桂林电子科技大学信息科技学院操作系统习题复习课.ppt

73页
  • 卖家[上传人]:野鹰
  • 文档编号:26877870
  • 上传时间:2018-01-03
  • 文档格式:PPT
  • 文档大小:1.39MB
  • / 73 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1,习题复习课,2,第一部分 同步和互斥问题,3,1.有三个进程,进程get从输入设备上不断读数据,并存入buffer1;进程cut不断将buffer1的内容剪切到缓冲区buffer2,进程put则不断将buffer2的内容在打印机上输出三个进程并发执行,协调工作写出该三个进程并发执行的同步模型4,buffer1,buffer2,get,,,,,empty1,empty2,full1,full2,分析存在如下同步关系:(1)只有buffer1为空,get才能工作,并使buffer1为满2)要求buffer1为满,同时buffer2为空,cut才能工作,工作结果使buffer1为空,buffer2为满3)只有buffer2为满,put才能工作,并使buffer2为空5,解答:(1)设置信号量设信号量empty1表示缓冲区buffer1为空,初值为1设信号量full1表示缓冲区buffer1为满,初值为0设信号量empty2表示缓冲区buffer2为空,初值为1设信号量full2表示缓冲区buffer2为满,初值为0,buffer1,buffer2,get,,,,,empty1,empty2,full1,full2,6,,(2)同步算法描述如下:,cut( ){ while(true) { Wait(full1) Wait(empty2) cut操作 Signal(empty1) Signal(full2) }},get( ){ while(true) { Wait(empty1) get操作 Signal(full1) }},put( ){ while(true) { Wait(full2) put操作 Signal(empty2) } },,,buffer1,buffer2,get,,,,,empty1,empty2,full1,full2,7,semaphore empty1=1,full1=0,empty2=1,full2=0;get( ){ while(true) { Wait(empty1); get操作; Signal(full1); }} cut( ){ while(true) { Wait(full1); Wait(empty2); cut操作; Signal(empty1); Signal(full2); }},,put( ){ while(true) { Wait(full2); put操作; Signal(empty2); } }main(){ parbegin(get,cut,put);},8,,2.用PV操作解决司机和售票员的问题。

      司机进程: while (true) { 启动车辆 正常驾驶 到站停车 },售票员进程:while (true) { 关门 售票 开门 },分析存在如下同步关系:(1)售票员关门后,司机才能开车2)司机到站停车后,售票员才能开门设信号量close表示关门开车,初值为0;设信号量stop表示到站开门,初值为0,,,9,semaphore close=0,open=0;driver( ){ while(true) { Wait(close) 启动车辆; 正常行驶; 到站停车; Signal(stop) }},,seller( ){ while(true) { 关门 Signal(close) 售票 Wait(stop) 开门 }}main(){ parbegin(driver,seller);},10,3.有一个阅览室,共有100个座位,读者进入时必须先在一张登记表上登记,该表为每一位列一表目,包括座号和读者姓名等,读者离开时要消掉登记的信息 试用PV操作描述读者进程之间的同步关系。

      分析:读者填表进入阅览室,这时要考虑阅览室里是否有座位;同时还要考虑登记表的互斥使用设信号量seats=100,mutex=1前者用于约束只能有100个进程共享阅览室,后者用来约束登记表的互斥使用11,semaphore seats=100 reader( ){ while (true) { Wait(seats); 选书读书; Signal( seats ); }},Wait(mutex); 填写登记表; Signal(mutex); Wait(mutex); 消掉登记; Signal(mutex);,12,思考题,某小型超级市场,可容纳50个人同时购物入口处备有篮子,每个购物者可拿一只篮子入内购物出口处结帐,并归还篮子(出、入口禁止多人同时通过)。

      试用PV操作写出购物者的同步算法第二部分单道程序和多道程序,13,2.2 操作系统的发展过程,2.2.2 单道批处理系统(Simple Batch Processing System) (1955-1965,晶体管时代,出现监控程序) 编程语言:汇编语言 单道:内存中仅有一道作业在运行 批处理:计算机系统对一批作业自动进行处理,2.2 操作系统的发展过程,2.2.2 单道批处理系统1.处理过程 把一批作业(用户程序+数据+作业说明书)以脱机方式输入到磁盘上,并在系统中配以监督程序(Monitor,OS雏形)将作业逐个送入内存并运行2.2 操作系统的发展过程,2.2.2 单道批处理系统 2.特征:单道性、顺序性、自动性优点:减少CPU空闲时间,提高资源利用率和系统吞吐量缺点:人机交互性差,CPU和I/O设备忙闲不均(取决于作业的特性)解决办法:多道程序设计技术,2.2 操作系统的发展过程,2.2.3 多道批处理系统(Multiprogrammed Batch Processing System) (1965-1980,半导体、小规模集成电路时代) 1.多道程序设计的基本概念 在内存中同时存放多个作业,使之同时处于运行状态(均已开始运行但尚未结束)共享系统资源。

      单CPU系统中的多道程序运行的特征宏观上并行:并发程序都已开始执行,但都未结束微观上串行:并发程序轮流占有CPU交替执行,,t,A,A,,,,,,,,,,Δt,,等待I/O的时间(6个Δt),,(a)单道情况,,,,,11,0,7,8,B,B,,t,A,A,,,,,,,,,,Δt,(b)两道情况,,,,,11,0,7,1,8,9,,t,,,,,,,,,,Δt,(c)四道情况,,,,,11,0,7,1,8,9,2,3,10,单道、两道和四道情况,1,4,2,1/8Δt = 0.125道程序/Δt,,,,2/9Δt = 0.222道程序/Δt,4/11Δt = 0.363道程序/Δt,,多道程序设计的基本概念,(a)单道情形:,打印请求,打印请求,单道与多道程序运行情况,,(b)多道情形:,程序A,OS,I/O设备,绘图仪请求,,,,,,,,,,,,,,,,,,,,,,,,,t1,t2,t3,t4,t5,t6,t7,t8,,CPU,打印机,绘图仪,,程序B,,,,,,,,打印完成,,,,绘图完成,,,,,,,,,t9,t10,,,,,,,,,,,,,用户程序,监督程序,I/O操作,I/O中断请求,启动I/O,I/O完成中断,I/O中断请求,启动I/O,,,,,,,,,,,,t1,,,,,,I/O中断处理结束,,,,,,,,,,,t2,t3,,t4,t5,t6,t7,t8,,CPU,,,,,,,CPU空闲,空闲,,,,多道程序设计的基本概念,例题1,若内存中有3道程序A、B、C,它们按A、B、C优先次序运行。

      各程序的计算轨迹为:A:计算(20)、I/O(30)、计算(10) B:计算(40)、I/O(20)、计算(10)C:计算(10)、I/O(30)、计算(20)如果三道程序都使用相同设备进行I/O(即程序用串行方式使用设备,调度开销忽略不计)试分别画出单道和多道运行的时间关系图两种情况下,CPU的平均利用率各为多少?,20,单道,,21,多道,,22,例题2 理解单道和多道程序执行时的不同,例:A、B两个程序,程序A按顺序使用CPU 10s,设备甲5s,CPU 5s,设备乙10s,CPU 10s,程序B按顺序使用设备甲10s,CPU 10s,设备乙5s,CPU 5s,设备乙10s问:①在顺序环境下执行程序A和B,CPU利用率多少? ②在多道环境下呢?答:①A和B顺序执行时,A执行完毕B才开始,总共耗时80s,占用CPU40s,故CPU利用率为40/80=50%②,多道时,两程序共耗时45s,故CPU利用率为40/45=88.89%,24,第三部分 处理机调度,25,3. 低级调度的功能和类型,1.低级调度的主要功能调度程序两项任务:调度和分派。

      调度实现调度策略,确定就绪进程/线程竞争使用处理器的次序的裁决原则,即进程/线程何时应放弃CPU和选择哪个来执行;分派实现调度机制,确定如何时分复用CPU,处理上下文交换细节,完成进程/线程和CPU的绑定和放弃的实际工作26,调度机制逻辑功能程序模块组成,队列管理程序:管理等待调度的进程/线程(排队)上下文切换程序时:当发生进程/线程切换时,用来保存旧现场,调入新现场分派程序:分派CPU给选中的进程/线程27,3.1.低级调度的基本类型,第一类称剥夺式: 两种处理器剥夺原则 一是高优先级进程/线程可剥夺低优先级进程/线程, 二是当运行进程/线程时间片用完后被剥夺第二类称非剥夺式:一旦某个进程/线程开始运行后便不再让出处理器比较剥夺式策略的开销大,但可以避免进程/线程长时间的独占处理器;很多操作系统使用两种测略的组合,内核关键程序是非剥夺式的,用户进程是剥夺式的28,1、先到先服务调度(first-come,first-served,FCFS)先请求CPU的进程被首先分配到CPU,可用FIFO队列来实现平均周转时间通常相当长,与作业的提交和调度顺序有关非抢占调度例 进程 区间时间 P1 24 P2 3 P3 3,0 24 27 30平均周转时间(24+27+30)/3=27,0 3 6 30平均周转时间(3+6+30)/3=13,3.2 作业调度和低级调度算法,29,2. 最短作业优先算法,SJF算法以进入系统的作业所要求的CPU时间为标准,总选取估计计算时间最短的作业投入运行。

      算法易于实现,效率不高,主要弱点是忽视了作业等待时间会出现饥饿现象SJF的平均作业周转时间比FCFS要小,故它的调度性能比FCFS好实现SJF调度算法需要知道作业所需运行时间,否则调度就没有依据,要精确知道一个作业的运行时间是办不到的。

      点击阅读更多内容
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.