操作系统复习提纲10级课件

第二章进程管理一、综合应用—使用wait和signal原语解决同步问题1、互斥对临界资源（一次只允许一个进程访问的资源）的访问2、描述前趋图：设计前趋图并使用wait和signal原语描述3、生产者-消费者问题：1个生产者，1个消费者，共享1个缓冲区1个生产者，1个消费者，共享n个缓冲区m个生产者，n个消费者，共享k个缓冲区1最新课件第二章进程管理一、综合应用—使用wait和signal原第二章进程管理4、哲学家进餐问题：设计不会死锁的哲学家进餐问题—如何通过信号量机制来控制系统的并发度5、读者-写者问题读者优先问题两组读者共享文件F时：同一组的进程可同时访问，不同组的进程互斥访问。2最新课件第二章进程管理4、哲学家进餐问题：2最新课件第三章调度与死锁二、应用与计算1、调度算法的应用（1）先来先服务（2）短作业（进程）优先（3）高优先权优先（4）高响应比优先※进程调度算法要分清：抢占还是非抢占2、银行家算法的应用（1）判断某状态是否安全—安全性算法（2）判断是否满足某进程的资源请求—银行家算法3最新课件第三章调度与死锁二、应用与计算3最新课件第四章内存管理一、计算与应用1、动态分区分配的应用：利用首次适应算法、最佳适应算法对内存进行分配。2、页式存储管理方式中逻辑地址的格式，页表的设计。4最新课件第四章内存管理一、计算与应用4最新课件第四章内存管理3、逻辑地址到物理地址的转换（1）分页系统：（10进制、16进制）（2）分段系统：注意：出现缺页（段）、非法地址、非法操作等情况的处理4、页面置换算法（1）FIFO（3）LRU（4）Clock算法（5）改进的Clock算法5最新课件第四章内存管理3、逻辑地址到物理地址的转换5最新课件第五章外设管理二、计算应用题1、磁盘调度算法（1）先来先服务（2）短距离优先（3）扫描（电梯）调度算法2、物理块的优化分布6最新课件第五章外设管理二、计算应用题6最新课件第六章文件管理二、流程图设计1、使用位示图法分配、回收一个盘块的过程三、计算与应用1、显示链接（1）FAT大小的计算（2）使用FAT组织某文件分配的盘块2、一级索引、二级索引对应文件大小的计算7最新课件第六章文件管理二、流程图设计7最新课件第六章文件管理3、混合索引方式对应文件的大小、启动盘块的次数及逻辑地址转换为物理地址的过程4、位示图（1）位示图行数的计算（2）盘块号与位示图行、列号的转换5、成组链接法分配一组、回收一组盘块后，空闲盘块的链接情况8最新课件第六章文件管理3、混合索引方式对应文件的大小、启动盘块的应用：调度算法现有A、B、C、D、E五个作业，每个作业的到达时间、服务时间、优先级如下表所示：进程名到达时间服务时间优先级开始时间完成时间周转时间带权周转时间A035B263C442D654E821及：平均周转时间、平均带权周转时间返回9最新课件应用：调度算法现有A、B、C、D、E五个作业，每个作业的到达应用—安全性算法判断系统是否安全进程MaxAllocationNeedAvailableABCABCABCABCP0753010P1322200P2902302P3222211P4433002已知：某系统分别有A、B、C类资源10、5、7。T0时刻系统状态如下所示，请问T0时刻该系统是否安全？返回10最新课件应用—安全性算法判断系统是否安全进程MaxA应用—银行家算法判断是否满足进程的资源请求进程MaxAllocationNeedAvailableABCABCABCABCP0753010P1322200P2902302P3222211P4433002743

332

122600011431已知：某系统的资源分配情况如下所示，T1时刻进程P1提出资源请求Request1(1,0,2),请问是否能满足进程P1的资源请求？返回11最新课件应用—银行家算法判断是否满足进程的资源请求进程Max某系统采用动态分配方式管理内存，内存空间为640K，其中高址端的40K空间分配给OS，对下列请求序列：顺序作业名动作空间(K)顺序作业名动作空间(K)123456作业1作业2作业3作业2作业4作业3申请申请申请释放申请释放13060100602001007891011作业1作业5作业6作业7作业6释放申请申请申请释放130140605060应用—动态分区分配算法返回12最新课件某系统采用动态分配方式管理内存，内存空间为640K，其中高址试用下列算法：给出在上述申请与释放过程中，内存的变化情况。（1）首次适应算法：空闲区按照地址从小到大排列。（2）最佳适应算法：空闲区按照大小从小到大排列。应用—动态分区分配算法返回13最新课件试用下列算法：给出在上述申请与释放过程中，内存的变化情况。应某系统的空闲分区按照大小如下表排列，现有作业大小分别为23K，45K，19K，请按照最佳适用算法和首次适用算法给出内存分配情况：应用—动态分区分配算法序号始址大小1100K21K2180K30K330K50K返回14最新课件某系统的空闲分区按照大小如下表排列，现有作业大小分别为23K1、设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，内存总共有8个存储块，试问逻辑地址至少应为

位？内存空间

字节？页表有

页表项？每个页表项

位？应用——逻辑地址与页表

返回15最新课件1、设有一页式存储管理系统，向用户提供的逻辑地址空间最大为1练习：已知某用户作业划分为5个页面，每个页面的大小为1K，每个页表项需要两个字节，该作业在装入过程中形成如下页表，请将下列操作中的逻辑地址转换成物理地址。应用—逻辑地址到物理地址的转换42739RWWREstoreR1,3015loadR1,5110storeR1,5122返回16最新课件练习：已知某用户作业划分为5个页面，每个页面的大小为1K，每某请求分页虚拟存储器的用户空间共有32个页面，每页1KB。假定系统为某作业分配了5,4,6,7四个物理块，并将作业的0，1，2页装入物理块5，4，6中，试将十六进制虚地址A5CH和193CH分别转换为16进制的物理地址。应用—逻辑地址到物理地址的转换返回17最新课件某请求分页虚拟存储器的用户空间共有32个页面，每页1KB。假回答下列问题：（1）计算该作业分别访问[0，432]、[1，10]、[2，500]、[3、400]，[6，350]时的绝对地址。练习：某采用段式存储管理的系统为装入主存的一个作业建立了如下所示的段表：段号段长段基址01234660140100580960221933009012371959应用—逻辑地址到物理地址的转换返回18最新课件回答下列问题：练习：某采用段式存储管理的系统为装入主存的一个系统为某进程分配了三个物理块，并有以下的页面引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1。请使用下面算法分析发生缺页中断的次数、淘汰的页面序列、缺页率。（1）最佳置换算法（2）先进先出页面置换算法（3）LRU应用—页面置换算法返回19最新课件系统为某进程分配了三个物理块，并有以下的页面引用串：7,0有如下页表：页号物理块进入内存时间最后访问时间访问位修改位058:309:0011187:5011:2011239:4010:30013210:2011:0000请问：先进先出

最近最久未使用简单的Clock

改进的Clock算法会淘汰哪个页面？应用—页面置换算法返回20最新课件有如下页表：页号物理块进入内存时间最后访问时间访问位修改位0某系统的读写磁头刚刚访问完100号磁道，现正在53号柱面上服务，而等待访问进程依次要访问的柱面为98,183,37,122,14,124,65,67。请使用下列算法分析：访问磁道的顺序、磁头移动的总距离、平均寻道长度。（1）先来先服务（2）最短寻道时间优先（3）扫描（电梯）调度算法（4）循环扫描调度算法应用—移臂调度算法返回21最新课件某系统的读写磁头刚刚访问完100号磁道，现正在53号柱面上服某系统对磁盘初始化时把每个盘面分成8个扇区，今有8个逻辑记录被存放在同一个磁道上供处理程序使用，现在要按顺序读出这8个记录。每次请求从磁盘上读一个记录，然后对读出的记录要花5毫秒的时间处理，磁盘转速为20毫秒/周。现把这8个逻辑记录依次存放在磁道上，如图所示：处理这8个记录要花费的时间为：应用—物理块的优化分布1234587613852746优化后返回22最新课件某系统对磁盘初始化时把每个盘面分成8个扇区，今有8个逻辑记应用—位示图法分配、回收一个盘块分配一个盘块：for(i=0;i<n;i++){for(j=0;j<32;j++)if(a[i][j]==0){k=i*32+j;a[i][j]=1;break;}

if(j<32)break;}printf(“No=%d\n”,k);回收一个盘块：scanf(“%d”,&no);i=no/32;j=no%32;A[i][j]=0;返回23最新课件应用—位示图法分配、回收一个盘块分配一个盘块：回收一个盘块举例：若FAT的每个表目需要字节的整数倍对于1.2MB的软盘，盘块大小为1KB，其FAT占用多少空间？磁盘容量为12GB,盘块的大小为4KB时，其FAT占用多少空间？应用—FAT大小的计算返回24最新课件举例：若FAT的每个表目需要字节的整数倍应用—FAT大小的如果文件A占用硬盘的第11，12，16，14四个盘块，试画出文件A中各盘块间的链接情况及目录项（FCB）的信息。应用—使用FAT链接盘块返回25最新课件如果文件A占用硬盘的第11，12，16，14四个盘块，试画出若某系统的外存分配方式使用索引结构，每个盘块的大小为1KB，索引表中的每个索引项需要2个字节，问：（1）使用一级索引结构，该文件系统对应的最大文件为多少字节？（2）使用二级索引结构，该文件系统对应的最大文件为多少字节？应用—索引文件大小的计算返回26最新课件若某系统的外存分配方式使用索引结构，每个盘块的大小为1KB，应用—混合索引UNIX系统使用混合索引组织文件：索引结点共13个地址项，0-9为直接文件，10为1级索引，11为2级索引，12为3级索引，若盘块大小为1KB，记录盘块号需要4个字节（1）混合索引能处理的最长文件的计算。（2）计算逻辑地址：5000、15000、1500000的逻辑盘块号和块内位移。（3）简述读取上述逻辑地址对应数据所在的物理盘块的过程。（4）若某文件的目录项已经在内存，采用混合索引方式，读取文件的内容，最少需要启动几次盘块？最多需要启动几次盘块？并解释。返回27最新课件应用—混合索引UNIX系统使用混合索引组织文件：索引结点共1举例：某系统的磁盘空间为600KB，每个盘块的大小为1KB，系统使用一个计算机字（32位）来代表位示图的一行，请计算：（位示图行、列号从0开始，盘块号从0开始）（1）该位示图至少需要

个计算机字。（2）第208个盘块，对应位示图的

字

列。（3）位示图的第7字第28列对应的盘块号是

。应用—位示图

返回28最新课件举例：某系统的磁盘空间为600KB，每个盘块的大小为1KB，1、某系统采用成组链接法来管理磁盘的空闲空间，目前磁盘的状态如图所示：请回答（1）该磁盘中目前还有多少个空闲盘块？（2）在给文件F分配三个盘块后，试给出分配后的盘块链接情况。（3）接着，系统要删除另一个文件，并回收它所占的5个盘块，它们的盘块号依次为700，711，703，788，701，试给出回收后的盘块链接情况。应用—成组链接法

返回29最新课件1、某系统采用成组链接法来管理磁盘的空闲空间，目前磁盘的状态2300299s.free019899空闲盘块号栈1004003993013002991005004994011000599501400399301599501500401499返回应用—成组链接法

30最新课件2300299s.free019899空闲盘块号栈10040感谢亲观看此幻灯片，此课件部分内容来源于网络，如有侵权请及时联系我们删除，谢谢配合！31感谢亲观看此幻灯片，此课件部分内容来源于网络，31第二章进程管理一、综合应用—使用wait和signal原语解决同步问题1、互斥对临界资源（一次只允许一个进程访问的资源）的访问2、描述前趋图：设计前趋图并使用wait和signal原语描述3、生产者-消费者问题：1个生产者，1个消费者，共享1个缓冲区1个生产者，1个消费者，共享n个缓冲区m个生产者，n个消费者，共享k个缓冲区32最新课件第二章进程管理一、综合应用—使用wait和signal原第二章进程管理4、哲学家进餐问题：设计不会死锁的哲学家进餐问题—如何通过信号量机制来控制系统的并发度5、读者-写者问题读者优先问题两组读者共享文件F时：同一组的进程可同时访问，不同组的进程互斥访问。33最新课件第二章进程管理4、哲学家进餐问题：2最新课件第三章调度与死锁二、应用与计算1、调度算法的应用（1）先来先服务（2）短作业（进程）优先（3）高优先权优先（4）高响应比优先※进程调度算法要分清：抢占还是非抢占2、银行家算法的应用（1）判断某状态是否安全—安全性算法（2）判断是否满足某进程的资源请求—银行家算法34最新课件第三章调度与死锁二、应用与计算3最新课件第四章内存管理一、计算与应用1、动态分区分配的应用：利用首次适应算法、最佳适应算法对内存进行分配。2、页式存储管理方式中逻辑地址的格式，页表的设计。35最新课件第四章内存管理一、计算与应用4最新课件第四章内存管理3、逻辑地址到物理地址的转换（1）分页系统：（10进制、16进制）（2）分段系统：注意：出现缺页（段）、非法地址、非法操作等情况的处理4、页面置换算法（1）FIFO（3）LRU（4）Clock算法（5）改进的Clock算法36最新课件第四章内存管理3、逻辑地址到物理地址的转换5最新课件第五章外设管理二、计算应用题1、磁盘调度算法（1）先来先服务（2）短距离优先（3）扫描（电梯）调度算法2、物理块的优化分布37最新课件第五章外设管理二、计算应用题6最新课件第六章文件管理二、流程图设计1、使用位示图法分配、回收一个盘块的过程三、计算与应用1、显示链接（1）FAT大小的计算（2）使用FAT组织某文件分配的盘块2、一级索引、二级索引对应文件大小的计算38最新课件第六章文件管理二、流程图设计7最新课件第六章文件管理3、混合索引方式对应文件的大小、启动盘块的次数及逻辑地址转换为物理地址的过程4、位示图（1）位示图行数的计算（2）盘块号与位示图行、列号的转换5、成组链接法分配一组、回收一组盘块后，空闲盘块的链接情况39最新课件第六章文件管理3、混合索引方式对应文件的大小、启动盘块的应用：调度算法现有A、B、C、D、E五个作业，每个作业的到达时间、服务时间、优先级如下表所示：进程名到达时间服务时间优先级开始时间完成时间周转时间带权周转时间A035B263C442D654E821及：平均周转时间、平均带权周转时间返回40最新课件应用：调度算法现有A、B、C、D、E五个作业，每个作业的到达应用—安全性算法判断系统是否安全进程MaxAllocationNeedAvailableABCABCABCABCP0753010P1322200P2902302P3222211P4433002已知：某系统分别有A、B、C类资源10、5、7。T0时刻系统状态如下所示，请问T0时刻该系统是否安全？返回41最新课件应用—安全性算法判断系统是否安全进程MaxA应用—银行家算法判断是否满足进程的资源请求进程MaxAllocationNeedAvailableABCABCABCABCP0753010P1322200P2902302P3222211P4433002743

332

122600011431已知：某系统的资源分配情况如下所示，T1时刻进程P1提出资源请求Request1(1,0,2),请问是否能满足进程P1的资源请求？返回42最新课件应用—银行家算法判断是否满足进程的资源请求进程Max某系统采用动态分配方式管理内存，内存空间为640K，其中高址端的40K空间分配给OS，对下列请求序列：顺序作业名动作空间(K)顺序作业名动作空间(K)123456作业1作业2作业3作业2作业4作业3申请申请申请释放申请释放13060100602001007891011作业1作业5作业6作业7作业6释放申请申请申请释放130140605060应用—动态分区分配算法返回43最新课件某系统采用动态分配方式管理内存，内存空间为640K，其中高址试用下列算法：给出在上述申请与释放过程中，内存的变化情况。（1）首次适应算法：空闲区按照地址从小到大排列。（2）最佳适应算法：空闲区按照大小从小到大排列。应用—动态分区分配算法返回44最新课件试用下列算法：给出在上述申请与释放过程中，内存的变化情况。应某系统的空闲分区按照大小如下表排列，现有作业大小分别为23K，45K，19K，请按照最佳适用算法和首次适用算法给出内存分配情况：应用—动态分区分配算法序号始址大小1100K21K2180K30K330K50K返回45最新课件某系统的空闲分区按照大小如下表排列，现有作业大小分别为23K1、设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，内存总共有8个存储块，试问逻辑地址至少应为

位？内存空间

字节？页表有

页表项？每个页表项

位？应用——逻辑地址与页表

返回46最新课件1、设有一页式存储管理系统，向用户提供的逻辑地址空间最大为1练习：已知某用户作业划分为5个页面，每个页面的大小为1K，每个页表项需要两个字节，该作业在装入过程中形成如下页表，请将下列操作中的逻辑地址转换成物理地址。应用—逻辑地址到物理地址的转换42739RWWREstoreR1,3015loadR1,5110storeR1,5122返回47最新课件练习：已知某用户作业划分为5个页面，每个页面的大小为1K，每某请求分页虚拟存储器的用户空间共有32个页面，每页1KB。假定系统为某作业分配了5,4,6,7四个物理块，并将作业的0，1，2页装入物理块5，4，6中，试将十六进制虚地址A5CH和193CH分别转换为16进制的物理地址。应用—逻辑地址到物理地址的转换返回48最新课件某请求分页虚拟存储器的用户空间共有32个页面，每页1KB。假回答下列问题：（1）计算该作业分别访问[0，432]、[1，10]、[2，500]、[3、400]，[6，350]时的绝对地址。练习：某采用段式存储管理的系统为装入主存的一个作业建立了如下所示的段表：段号段长段基址01234660140100580960221933009012371959应用—逻辑地址到物理地址的转换返回49最新课件回答下列问题：练习：某采用段式存储管理的系统为装入主存的一个系统为某进程分配了三个物理块，并有以下的页面引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1。请使用下面算法分析发生缺页中断的次数、淘汰的页面序列、缺页率。（1）最佳置换算法（2）先进先出页面置换算法（3）LRU应用—页面置换算法返回50最新课件系统为某进程分配了三个物理块，并有以下的页面引用串：7,0有如下页表：页号物理块进入内存时间最后访问时间访问位修改位058:309:0011187:5011:2011239:4010:30013210:2011:0000请问：先进先出

最近最久未使用简单的Clock

改进的Clock算法会淘汰哪个页面？应用—页面置换算法返回51最新课件有如下页表：页号物理块进入内存时间最后访问时间访问位修改位0某系统的读写磁头刚刚访问完100号磁道，现正在53号柱面上服务，而等待访问进程依次要访问的柱面为98,183,37,122,14,124,65,67。请使用下列算法分析：访问磁道的顺序、磁头移动的总距离、平均寻道长度。（1）先来先服务（2）最短寻道时间优先（3）扫描（电梯）调度算法（4）循环扫描调度算法应用—移臂调度算法返回52最新课件某系统的读写磁头刚刚访问完100号磁道，现正在53号柱面上服某系统对磁盘初始化时把每个盘面分成8个扇区，今有8个逻辑记录被存放在同一个磁道上供处理程序使用，现在要按顺序读出这8个记录。每次请求从磁盘上读一个记录，然后对读出的记录要花5毫秒的时间处理，磁盘转速为20毫秒/周。现把这8个逻辑记录依次存放在磁道上，如图所示：处理这8个记录要花费的时间为：应用—物理块的优化分布1234587613852746优化后返回53最新课件某系统对磁盘初始化时把每个盘面分成8个扇区，今有8个逻辑记应用—位示图法分配、回收一个盘块分配一个盘块：for(i=0;i<n;i++){for(j=0;j<32;j++)if(a[i][j]==0){k=i*32+j;a[i][j]=1;break;}

if(j<32)break;}printf(“No=%d\n”,k);回收一个盘块：scanf(“%d”,&no);i=no/32;j=no%32;A[i][j]=0;返回54最新课件应用—位示图法分配、回收一个盘块分配一个盘块：回收一个盘块举例：若FAT的每个表目需要字节的整数倍对于1.2MB的软盘，盘块大小为1KB，其FAT占用多少空间？磁盘容量为12GB,盘块的大小为4KB时，其FAT占用多少空间？应用—FAT大小的计算返回55最新课件举例：若FAT的每个表目需要字节的整数倍应用—FAT大小的如果文件A占用硬盘的第11，12，16，14四个盘块，试画出文件A