操作系统 课后习题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第,3,章作业,画出下面五条语句的前趋图,S1,：,a:=x+y,S2,：,b:=z+1,S3,：,c:=a-b,S4,：,w:=c+1,S5,：,x:=y-z,数据库中读写方面的互斥与本章节读者,-,写者问题有何不同？原因何在？改写读者,-,写者问题算法以适应数据库实现。,读者,-,写者问题,如果读者来,：,无读者、写者，新读者可以读,有写者等，但有其它读者正在读，则新读者也可以读,有写者写，新读者等,如果写者来,：,无读者，新写者可以写,有读者，新写者等待,有其它写者，新写者等待,读者,-,写者问题修改）,如果读者来,：,无论如何都能读,如果写者来,：,有其它写者，新写者等待,利用记录型信号量解决读者,-,写者问题,Varrmutex,wmutex:semaphore:=1,1;,Readcount:integer:=0;,Begin,parbegin,Reader:,begin,repeat,wait(rmutex);,if readcount=0 then wait(wmutex);,Readcount=Readcount+1;,signal(rmutex);,perform read operation;,wait(rmutex);,readcount=readcount-1;,if readcount=0 then signal(wmutex);,signal(rmutex);,until false;,end,Writer:,begin,repeat,wait(wmutex);,perform write operation;,signal(wmutex);,until false;,end,parend,end,第,4,章作业,证明对于给定的一组进程，使用非抢占的短作业优先调度算法时，进程的平均完成时间最短。,实时系统中有,2,个周期任务。第一个任务每隔,m1,秒需要进行,n1,次运算；第二个任务每隔,m2,秒需要进行,n2,次运算。现有,2,种,CPU,可供选择，第一种,CPU,每秒能运算,r1,次运算，价格为,c1,；第二种,CPU,每秒能运算,r2,次，价格为,c2,。问如何配置最省钱。,课件第,81,页银行家算法案例中，如果把,P0,请求从,Request0(0,2,0),改为,Request0(0,1,0),，系统是否安全？,证明同一个资源分配图按不同的简化顺序都将得到相同的不可简化图。,写死锁解除算法，使用撤消进程的方法，通过撤销权值（表示撤销代价）总和最小的,n,个进程，使系统脱离死锁状态。,设,n,个进程的处理顺序是,P,1,、,P,2,、,、,P,n,，执行时间是,t,1,、,t,2,、,、,t,n,，进程的平均完成时间为,若进程不全按短作业优先原则，即存在,P,j,和,P,k,进程，满足,jt,k,，则将,P,j,和,P,k,进程的交换，形成新的处理顺序,P,1,、,、,P,j-1,、,P,k,、,P,j+1,、,P,k-1,、,P,j,、,P,k+1,、,、,P,n,，进程的平均完成时间为,两个周期任务平均每秒运算次数,L=n,1,/m,1,+n,2,/m,2,，设,For i=0 to k/i,表示第一种,CPU,数量,/j,表示第二种,CPU,数量,c=c,1,*i+c,2,*j/c,表示总成本,将最小的,c,对应的,i,和,j,作为第一种和第二种,CPU,的配置数量,P0,请求,Request0(0,1,0),P1,、,P3,、,P4,、,P2,、,P0,对于进程,P,1,、,P,2,、,、,P,n,，若资源分配图的两种简化方法涉及的进程（,P,j1,、,P,j2,、,、,P,jm,）相同，仅简化的顺序不同。由于资源简化的方法是将与进程节点有关的边都删除形成孤立节点，与执行顺序无关。资源分配图的初始值相同，故简化后也相同。,若方法一与方法二涉及不同的进程，不妨设方法一中有,P,jk,进程，而方法二中没有，则将,P,jk,进程补到方法二最后一个进程后。方法一在处理,P,jk,进程时仅回收了,P,j1,、,P,j2,、,、,P,jk-1,的资源，而方法二已回收了除,P,jk,外,P,j1,、,P,j2,P,jm,的资源，故有足够资源供,P,jk,完成，因此方法二不是不可简化图，与已知矛盾。,不同的简化方法涉及的进程相同，顺序可能不同，故得到相同的不可简化图。,将空集以及对应的代价,0,作为第一个元素放入队列中,循环执行,取队列首个元素,A,若终止,A,中进程可解除死锁状态，则退出循环，,A,包含的进程为需终止进程，对应最小代价,分别在,A,中添加一个不在,A,中的其他进程，计算代价，并根据代价大小，与队列中已有的元素按从小到大的顺序排序，重新放入队列中,第,5,章习题,在伙伴系统中，某块的地址为,i-j,，求其伙伴块的地址。,描述分页、分段、段页式存储的寻址方法,段页式存储是否存在空间浪费？说明原因,内存太大或太小分别会带来什么问题？,在使用虚拟内存的系统中，若内存的缺页率达到,5%,，则内存的访问效率会降低多少？,块首地址为,i,，尾地址为,j,，根据伙伴系统的特点，,j-i+1=2,k,，若,i,用二进制表示从低位（第,0,位）起的第,k,位上为,1,，则说明该块是右伙伴，其左伙伴的尾地址为,i-1,，首地址为,2i-j-1,。若,i,的第,k,位是,0,，则说明该块是左伙伴，其右伙伴的首地址为,j+1,，尾地址为,2j+1-i,。,内部碎片,内存太大：性价比高。内存太小：页面交换频繁。,内存带宽,=,内存工作频率*内存总线宽度,/8,，,DDR2,内存的总线带宽是,64BIT,，,DDR2,可以在时钟信号的上升沿和下降沿都传送数据，因此计算得到的相应带宽要*,2DDR2 800,运行频率为,400MHz,，,带宽为,400*2*64/8=6400MB/s=6.4GB/s,希捷,500GB,平均读写速度,120MB/s,内存硬盘速度比约,50:15%,缺页率将导致,2,次,I/O1*0.95+50*2*0.05=5.95,第,6,章习题,某硬盘大小为,8G,，有,8,个双面可存储盘片，转速为,7200rpm,，每一磁道上的数据量为,2.5MB,，磁臂的启动时间是,2ms,，磁臂每移动一个磁道需要,0.1ms,，需要传输一个,600M,的连续文件，求磁盘平均访问时间,一个共享文件删除时需要执行哪些操作？,文件存储空间管理有哪些方式？,I/O,设备所采用的,I/O,控制方式有哪些？,磁盘平均访问时间,磁盘转速：,7200,转,/,分钟,=120,转,/,秒,文件占用的磁道数：,600/2.5=240,240/120=2s,从文件目录中删除、回收空间、所有指向该文件的链接失效。,空闲表、空闲链表、位图,轮询（位）、中断（字符）、,DMA,（一个数据块）、,I/O,通道（一组数据块）,