os复习市公开课特等奖市赛课微课一等奖课件

经典题目与模拟练习1第1页一、进程并发：多个程序在一段时间内同时发生进程是什么?与程序区分进程基本状态进程控制块PCB.进程创建、阻塞、终止过程2第2页进程同时问题:源于进程相互制约关系：资源共享，有序合作同时概念：并发执行诸进程之间能有效地共享资源和相互合作，从而使程序执行含有可再现性。控制同时四大标准临界资源、临界区信号量机制信号量操作原语wait、signal3第3页经典同时题目：生产者-消费者取、用类，计数控制+互斥哲学家进餐计数类、死锁相关读者-写者有条件互斥类似经典题目：单行路，同方向不互斥；异向互斥4第4页信号量规律：分析同时关系、设置信号量初值、PV操作次序P、V操作成对出现多个进程对互斥同时，PV操作成对出现同进程中，初值为1多个进程有序同时，PV操作成对出现在不一样进程中，有V操作进程可经过控制先于有P操作进程执行。初值依据应用情况设置。5第5页一阅览室最多容纳100人，读者进入和离开都要在记录表上登记，每次只允许一个人登记。怎样编写进程间同时关系。资源：空数N，记录表S信号量n=N，mutex=1进程：读者进程 wait（n） wait（mutex） 进入 signal（mutex） 阅读后离开 signal（n）6第6页吸烟者问题（Patil,1971)三个吸烟者在一间房间内，还有一个香烟供给者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴。供给者有丰富货物提供。三个吸烟者中，第一个有自己烟草，第二个有自己纸，第三个有自己火柴。供给者（随机地）将两样东西放在桌子上，允许一个吸烟者进行对健康不利吸烟。当吸烟者完成吸烟后唤醒供给者，供给者再放两样东西在桌面上，然后唤醒另一个吸烟者。试为写出进程同时关系。7第7页主要是双向有序同时问题吸烟者要由供给者触发，s1=0而供给者再次供给也要靠吸烟者触发，s2=1供者P（s2）随机放物品V（s1）吸烟者P（s1）取物品V（s2）加三个控制物品计数信号量，完整程序以下8第8页随机放物品Randomnize; case=random(0,2); if(case==0){ V(tobacco); V(paper); V(smoker1); } elseif(case==1){ V(tobacco); V(match); V(smoker2); } elseif(cass==2){ V(paper); V(match); V(smoker3); }voidsmoker1(){while(1){ P(smoker1); V(match); P(tobacco); P(paper); P(match); //吸烟 V(seller) }}9第9页二、CPU调度三级调度调度时机\抢占\算法计算调度程序运行时机：程序正常完成IO\PV阻塞时间片到新任务产生调度算法基本调度算法：FCFS，SJF，HPF，HRRN，RR，FB*实时调度10第10页算法名称特点方式FCFS最简单不利于短作业非抢占SJF/SPF照料平均周转时间不适于长作业非抢占/抢占HPF/HRRN优先权考虑全方面非抢占/抢占RR及时响应简单时间片轮转FB最综合一个算法时间片轮转/马上抢占11第11页某系统进程请求如右图，画出RR调度下调度过程图。并计算平均周转时间。设时间片为2。进程名开始时刻执行时间A03B23C34D47ABCD012345678901234567890ACBCBDACDBA12第12页死锁相关概念与认识四个必要条件处理死锁各种方法防止死锁银行家算法（相对预防死锁，是一个软限制。）安全状态算法、计算13第13页三、存放器管理连续分配单一连续、固定分区动态分区分配可重定位动态分区（有紧凑功效）离散分配分页，地址转换过程，计算分段虚拟概念：虚拟、局部性置换调度算法：缺页次数（掉入次数） 缺页率=缺页次数/总页面数14第14页例分页系统，主存容量64K，页面大小1K。一个4K大作业，0-3页分别分配到物理块2、4、6、7中。该作业逻辑地址格式怎样？十进制逻辑地址1023（B）转换为物理地址画出地址变换过程。答：即页号与页内地址位数大小该作业4个页面编号需要2位；每页1K大小，即1K条指令编号需10位页号页内地址11109 … 015第15页逻辑地址10231023/1K=0余10230页对应物理块2，所以物理地址是2*1K+1023=2048+1023=307101023页表始址X页表长度4页表存放器

页号块号02142637X+02102316第16页例虚拟内存管理中LRU页面置换算法设页面走向以下，分配给该作业3个内存块，画出置换过程图，并计算缺页率。458134465127613注意在旁边对LRU栈次序实时把握17第17页四、文件管理文件结构逻辑结构：有结构文件：次序，链接，索引物理结构：已分配空间统计连续、链接、索引、混合索引分配方式 FAT表计算，索引文件大小计算，UNIX下混合索引空闲空间管理表、盘区\盘块链、成组链接、位示图目录、共享18第18页例：FAT与索引计算FAT表计算物理空间容量/盘块大小=FAT表项个数个数决定位数,决定每项大小个数*每项大小索引结点盘块大小/盘块号大小=可统计盘块个数单索引下，一个索引结点能统计N个盘块，则文件最大长度为：N*盘块大小19第19页例：混合索引分配方式计算FCB有13个地址项，0-9为直接地址，10为一次间接地址，11为二次间接地址，12为三次间接地址。若盘块大小为512B，盘块号需3B统计，每个盘块最多存放170个盘块地址。该文件系统文件最大允许多长？10+170+170*170+170*170*170=4942080块=4942080*512B=2471040KB将文件字节偏移量15000转换为物理块号和块内偏移。15000/512=29余152。10=<29<=10+170.所以文件使用第29块盘块号，统计在FCB中10项，即一次间接地址索引盘块中。从10项统计地址找到索引表，第19项即是要找物理块。20第20页若FCB已存在内存，其它信息均在外存，访问该文件某位置内容，最少/最多需要几次访问磁盘？最少需访问磁盘情况是直接寻址，直接读FCB中统计地址，访问磁盘1次即可最多需访问磁盘情况是三次间接寻址过程，需读三次间接索引块中内容，然后读它里面统计二次接索引块中内容，再一次，最终才能取得文件信息实际地址。姑，最多情况需4次访问磁盘。21第21页外存空间管理空闲空间三种分配方式：连续、链接、索引空闲空间管理空闲表/链、位示土图、成组链接成组链接22第22页例：某系统采取成组链接法管理磁盘空闲空间，当前状态以下列图，问：还有多少空闲盘块？若从当前状态下，系统分配3个盘块给某文件后，又删除另一文件，回收了第700，711，703，788，701这5个盘块。则磁盘空间状态图中链接情况又怎样？23第23页空闲盘块成组链接示意图7901-7999全部空闲盘块，被分成若干个组设有10000个盘块，每100个分为1组，则分成100个组。201-7999为文件区各组链接起来。301-400401-500……201-300299#202#201#数据空间302…400100301399#302#301#数据空间下一组指针可用块数数据空间799