《操作系统课后习题》PPT课件.ppt
第3章作业,画出下面五条语句的前趋图 S1:a:=x+y S2:b:=z+1 S3:c:=a-b S4:w:=c+1 S5:x:=y-z 数据库中读写方面的互斥与本章节读者-写者问题有何不同?原因何在?改写读者-写者问题算法以适应数据库实现。,读者-写者问题,如果读者来: 无读者、写者,新读者可以读 有写者等,但有其它读者正在读,则新读者也可以读 有写者写,新读者等 如果写者来: 无读者,新写者可以写 有读者,新写者等待 有其它写者,新写者等待,读者-写者问题(修改),如果读者来: 无论如何都能读 如果写者来: 有其它写者,新写者等待,利用记录型信号量解决读者-写者问题 Var rmutex, 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个进程的处理顺序是P1、P2、Pn,执行时间是t1、t2、tn,进程的平均完成时间为 若进程不全按短作业优先原则,即存在Pj和Pk进程,满足jtk,则将Pj和Pk进程的交换,形成新的处理顺序P1、Pj-1、Pk 、Pj+1 、Pk-1、Pj 、Pk+1、Pn ,进程的平均完成时间为,两个周期任务平均每秒运算次数L=n1/m1+n2/m2 ,设 For i=0 to k /i表示第一种CPU数量 /j表示第二种CPU数量 c=c1*i+c2*j /c表示总成本 将最小的c对应的i和j作为第一种和第二种CPU的配置数量,P0请求Request0(0,1,0),P1、P3、P4、P2、P0,对于进程P1、P2、Pn,若资源分配图的两种简化方法涉及的进程(Pj1、Pj2、Pjm)相同,仅简化的顺序不同。由于资源简化的方法是将与进程节点有关的边都删除形成孤立节点,与执行顺序无关。资源分配图的初始值相同,故简化后也相同。 若方法一与方法二涉及不同的进程,不妨设方法一中有Pjk进程,而方法二中没有,则将Pjk进程补到方法二最后一个进程后。方法一在处理Pjk进程时仅回收了Pj1、Pj2、Pjk-1的资源,而方法二已回收了除Pjk外Pj1、Pj2、Pjm的资源,故有足够资源供Pjk完成,因此方法二不是不可简化图,与已知矛盾。 不同的简化方法涉及的进程相同,顺序可能不同,故得到相同的不可简化图。,将空集以及对应的代价0作为第一个元素放入队列中 循环执行 取队列首个元素A 若终止A中进程可解除死锁状态,则退出循环,A包含的进程为需终止进程,对应最小代价 分别在A中添加一个不在A中的其他进程,计算代价,并根据代价大小,与队列中已有的元素按从小到大的顺序排序,重新放入队列中,第5章习题,在伙伴系统中,某块的地址为i-j,求其伙伴块的地址。 描述分页、分段、段页式存储的寻址方法 段页式存储是否存在空间浪费?说明原因 内存太大或太小分别会带来什么问题? 在使用虚拟内存的系统中,若内存的缺页率达到5%,则内存的访问效率会降低多少?,块首地址为i,尾地址为j,根据伙伴系统的特点,j-i+1=2k,若i用二进制表示从低位(第0位)起的第k位上为1,则说明该块是右伙伴,其左伙伴的尾地址为i-1,首地址为2i-j-1。若i的第k位是0,则说明该块是左伙伴,其右伙伴的首地址为j+1,尾地址为2j+1-i。 内部碎片 内存太大:性价比高。内存太小:页面交换频繁。,内存带宽=内存工作频率*内存总线宽度/8 ,DDR2内存的总线带宽是64BIT,DDR2可以在时钟信号的上升沿和下降沿都传送数据,因此计算得到的相应带宽要*2 DDR2 800,运行频率为400MHz,带宽为400*2*64/8=6400MB/s=6.4GB/s 希捷500GB平均读写速度120MB/s 内存硬盘速度比约50:1 5%缺页率将导致2次I/O 1*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通道(一组数据块),