《操作系统操作系统习题课2PPT.ppt》由会员分享，可在线阅读，更多相关《操作系统操作系统习题课2PPT.ppt（94页珍藏版）》请在第壹文秘上搜索。
1、第一章 5、在单CPU和两台I/O(I1,I2)设备的多道程序设计环境下，同时投入三个作业运行。它们的执行轨迹如下： Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms) Job2：I1(20ms)、CPU(20ms)、I2(40ms) Job3：CPU(30ms)、I1(20ms) 如果CPU、I1和I2都能并行工作，优先级从高到低为Job1、Job2和Job3，优先级高的作业可以抢占优先级低的作业的CPU。试求：(1)每个作业从投入到完成分别所需的时间。(2) 每个作业投入到完成CPU的利用率。(3)I/O设备利用率。画出三个作业并行工作图如下(图中着色部分
2、为作业等待时间)：Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms)Job2：I1(20ms)、CPU(20ms)、I2(40ms)Job3：CPU(30ms)、I1(20ms) Job1从投入到运行完成需80ms，Job2从投入到运行完成需90ms，Job3从投入到运行完成需90ms。 CPU空闲时间段为：60ms至70ms，80ms至90ms。所以CPU利用率为(90-20)/90=77.78%。 设备I1空闲时间段为：20ms至40ms，故I1的利用率为(90-20)/90=77.78%。设备I2空闲时间段为：30ms至50ms，故I2的利用率为(90-
3、20)/90=77.78%。8、若主存中有3道程序A、B、C，优先级从高到低为A、B和C，它们单独运行时的CPU和I/O占用时间为：若3道程序并发执行，调度开销忽略不计，但优先级高的程序可中断优先级低的程序，优先级与I/O设备无关。试画出多道运行的时间关系图，并问最早与最迟结束的程序是哪个？每道程序执行到结束分别用了多少时间？计算3个程序全部运算结束时的CPU利用率? 最早结束的程序为B，最后结束的程序为C。 程序A为250ms。程序B为220ms。程序C为310ms。 CPU利用率为(310-120)/310=61.3%第二章 11 有5个批处理作业A到E均已到达计算中心，其运行时间分别2、
4、4、6、8和10分钟；各自的优先级分别被规定为1、2、3、4和5，这里5为最高级。对于(1）时间片轮转算法、(2）优先数法、(3）短作业优先算法、(4）先来先服务调度算法(按到达次序C、D、B、E、A)，在忽略进程切换时间的前提下，计算出平均作业周转时间。（对(1）每个作业获得相同的2分钟长的时间片；对(2）到(4）采用单道运行，直到结束。）调度算法准则的计算(P123) (1)资源利用率(CPU、I/O操作利用率) (2)吞吐率 (3)公平性 (4)响应时间 (5)周转时间(平均作业周转时间、平均带权作业周转时间) (1)FCFS调度算法 (2)优先级调度算法(3)时间片轮转法按次序A B
5、C D E B C D EC D E D E E轮转执行。(4)SJF调度算法 20，有一个四道作业的操作系统，若在一段时间内先后到达6个作业，它们的提交和估计运行时间由下表给出： 作业 提交时间 估计运行时间(分钟) 1 8：00 60 2 8：20 35 3 8：25 20 4 8：30 25 5 8：35 5 6 8：40 10 系统采用剩余SJF调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被剩余时间更短作业抢占。(1)分别给出6个作业的执行时间序列、即开始执行时间、作业完成时间、作业周转时间。(2)计算平均作业周转时间。 作业 提交 需运行 开始运行 被抢占还 完成 周转
6、 号 时间 时间 时间 需运行时间 时间 时间 J1 8:00 60 8:00 40 10:35 155 J2 8:20 35 8:20 30 9:55 95 J3 8:25 20 8:25 8:45 20 J4 8:30 25 9:00 25 9:25 55 J5 8:35 5 8:45 8:50 15 J6 8:40 10 8:50 9:00 20 说明: (1) J2到达时抢占J1；J3到达时抢占J2。 (2) 但J4到达时，因不满足SJF，故J4不能被运行，J3继续执行5分钟。 (3) 由于是4道的作业系统，故后面作业不能进入主存而在后备队列等待，直到有作业结束。 (4) 根据进程调度
7、可抢占原则，J3第一个做完。而这时J5、J6均己进入后备队列，而J5可进入主存。 (5) 因J5最短，故它第二个完成。这时J6方可进入主存。因J6最短，故它第三个完成。 (6) 然后是:J4、J2和J1 (7) T=(155+95+20+55+15+20)/6=60 27，某多道程序系统供用户使用的主存为100K，磁带机2台，打印机1台。采用可变分区主存管理，采用静态方式分配外围设备，忽略用户作业I/O时间。现有作业序列如下： 作业调度采用FCFS策略，优先分配为多少?主存低地址区且不准移动已在主存的作业，在主存中的各作业平分CPU时间。现求：(1)作业被调度的先后次序?(2)全部作业运行结束
8、的时间?(3)作业平均周转时间为多少?(4)最大作业周转时间参照P238的可变分区管理的定义 本题综合测试了作业调度、进程调度、及对外设的竞争、主存的竞争。8:00 作业1到达，占有资源并调入主存运行。8:20 作业2和3同时到达，但作业2因分不到打印机，只能在后备队列等待。作业3资源满足，可进主存运行，并与作业1平分CPU时间。8:30 作业1在8:30结束，释放磁带与打印机。但作业2仍不能执行，因不能移动而没有30KB的空闲区，继续等待。作业4在8:30到达，并进入主存执行，与作业3分享CPU。8:35 作业5到达，因分不到磁带机/打印机，只能在后备队列等待。9:00 作业3运行结束，释放
9、磁带机。此时作业2的主存及打印机均可满足，投入运行。作业5到达时间晚，只能等待。9:10 作业4运行结束，作业5因分不到打印机，只能在后备队列继续等待。9:15 作业2运行结束，作业5投入运行。9:30 作业全部执行结束。答：答：(1)作业调度选择的作业次序为：作业1、作业3、作业4、作业2和作业5。 (2)全部作业运行结束的时间9:30。 (3)周转时间：作业1为30分钟、作业2为55分钟、作业3为40分钟、作业4为40分钟和作业5为55分钟。 (4)平均作业周转时间=44分钟。 (5) )最大作业周转时间为55分钟。 28， 某多道程序设计系统采用可变分区主存管理，供用户使用的主存为200
10、K，磁带机5台。采用静态方式分配外围设备，且不能移动在主存中的作业，进程调度采用FCFS，忽略用户作业I/O时间。现有作业序列如下： 现求：(1)FIFO算法选中作业执行的次序及作业平均周转时间。(2)SJF算法选中作业执行的次序及作业平均周转时间。几个注意问题： 1，这里还需要考虑进程调度（FCFS). 2, 需要搞清楚几个关键时刻点内存和磁带机的状态，以确定是否需要装入相应的作业，以及是否需要可以占用处理机。 1、先来先服务算法：1.先来先服务算法。说明： (1) 8:30 作业A到达并投入运行。注意它所占用的资源。 (2) 8:50 作业B到达，资源满足进主存就绪队列等CPU。 (3)
11、9:00 作业C到达，主存和磁带机均不够，进后备作业队列等待。 (4) 9:05 作业D到达，磁带机不够，进后备作业队列等待。后备作业队列有C、D。 (5) 9:10 作业A运行结束，归还资源磁带，但注意主存不能移动(即不能紧缩)。作业B投入运行。作业C仍因主存不够而等在后备队列。这时作业E也到达了，也由于主存不够进入后备作业队列。此时作业D因资源满足(主存/磁带均满足)，进主存就绪队列等待。后备作业队列还有C、E。 (6)9:35 作业B运行结束，作业D投入运行。这时作业C因资源满足而调入主存进就绪队列等CPU。而作业E因磁带机不够继续在后备作业队列等待。 (7)9:55 作业D运行结束，作
12、业C投入运行。这时作业E因资源满足而调入主存进就绪队列等CPU。 (8)10:30 作业C运行结束，作业E投入运行。 (9)10:40 作业E运行结束。 2. 短作业优先算法。 (1) 8:30 作业A到达并投入运行。注意它所占用的资源。 (2) 8:50 作业B到达，资源满足进主存就绪队列等CPU。 (3) 9:00 作业C到达，主存和磁带机均不够，进后备作业队列等待。 (4) 9:05 作业D到达，磁带机不够，进后备作业队列等待。后备作业队列有C、D。 (5) 9:10 作业A运行结束，归还资源磁带，但注意主存不能移动(即不能紧缩)。作业B投入运行。作业C仍因主存不够而等在后备队列。这时作
13、业E也到达了，虽然该作业最短，也由于主存不够进入后备作业队列。此时作业D因资源满足(主存/磁带均满足)，进主存就绪队列等待。后备作业队列还有C、E。 (6)9:35 作业B运行结束，作业D投入运行。这时作业C和E资源均满足，但按SJF应把作业E调入主存进就绪队列等CPU。而作业C因磁带机不够磁带机不够继续在后备作业队列等待。 (7)9:55 作业D运行结束，作业C调入主存进就绪队列等CPU。 (8)10:05 作业E运行结束，作业C投入运行。 (9)10:40 作业C运行结束。第三章77 试利用test&set指令实现单处理器上的信号量机制。(P229)typedef struct int f
14、lag; /标志 int value; /信号量值struct pcb *list; /信号量队列指针semaphore;void P(s) while(!test_set(s.flag) s.value-; if(s.value0) W(s.list); s.flag =1; s.flag=1; void V(s) while(!test_set(!s.flag) s.value+; if(s.value=0) R(s.list); s.flag=1; 19，四个进程Pi（i=03）和四个信箱Mj（j=03），进程间借助相邻信箱传递消息，即Pi每次从Mi中取一条消息，经加工后送入M(i+1)
15、mod4，其中M0、M1、M2、M3分别可存放3、3、2、2个消息。初始状态下，M0装了三条消息，其余为空。试以P、V操作为工具，写出Pi（i=03）的同步工作算法。semaphore mutex1,mutex2,mutex3,mutex0;mutex1=mutex2=mutex3=mutex0=1;semaphore empty0,empty1,empty2,empty3;empty=0;empty1=3;empty=2;empty3=2;semaphore full0,full1,full2,full3;full0=3;full1=full2=full3=0;int in0,in1,in2
16、,in3,out0,out1,out2,out3;in0=in1=in2=in3=out0=out1=out2=out3=0;cobeginprocess P0( ) while(true) P(full0); P(mutex0); 从M0out0取一条消息; out0=(out0+1) % 3; V(mutex0); V(empty0); 加工消息; P(empty1); P(mutex1); 消息存M1in1; in1=(in1+1) % 3; V(mutex1); V(full1); process P1( ) while(true) P(full1); P(mutex1); 从M1out1取一条消息; out1=(out1+1) % 3; V(mutex1); V(empty1); 加工消息; P(empty2); P(mutex2); 消息存M2in2; in2=(in2+1) % 2; V(mutex2); V(full2); process P2( ) while(true) P(full2); P(mutex2); 从M2out2取一条消息; out2=(out2+1)
