《《操作系统复习》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《操作系统复习》PPT课件.ppt（68页珍藏版）》请在三一办公上搜索。
1、操作系统原理复习,南京工业大学信息学院计算机系,注意要点,考核形式试卷，闭卷考试，120分钟可以带计算器，但不得使用手机中的计算器功能试卷占总评成绩的80%考察范围第一章第九章部分章节除外,2023/7/16,操作系统复习,2,题型分布,单选题15题，共30分填空题10题，共10分综合应用题6题，共60分,2023/7/16,操作系统复习,3,主要知识点,第一章操作系统的目标操作系统的作用三种经典的操作系统类型分时系统的特征实时系统的特征操作系统的基本特征用户接口的种类,2023/7/16,操作系统复习,4,主要知识点,第二章顺序执行程序的主要特征并发执行程序的主要特征进程的特征进程的各个状态
2、，及各状态之间的转换条件导致进程创建、终止、阻塞的条件同步机制的4条设计原则进程同步：只需要掌握用信号量解决P-C问题进程通信的方法,2023/7/16,操作系统复习,5,主要知识点,第三章处理机的调度层次调度算法：FIFO，SJF，高相应比优先，时间片轮转产生死锁的4个必要条件银行家算法资源分配图的简化,2023/7/16,操作系统复习,6,主要知识点,第四章动态分区分配中分配和回收内存的方法动态分区分配算法：FF，NF，BF，WF逻辑地址到物理地址的转换及访问时间的计算多级页表段页式存储管理的地址转换（虚地址到实地址的转换）,2023/7/16,操作系统复习,7,主要知识点,第五章虚拟存储
3、器的特征页面置换算法及缺页率的计算最佳，FIFO，LRU，时钟置换抖动的概念,2023/7/16,操作系统复习,8,主要知识点,第六章I/O系统的基本功能I/O系统的层次结构I/O设备的类型设备控制器的基本功能单缓冲和双缓冲传输时间的计算磁盘访问时间的计算磁盘调度算法：FCFS，SSTF，SCAN，CSCAN,2023/7/16,操作系统复习,9,主要知识点,第七章文件的组织分类及其特征目录管理的要求目录结构的组织形式目录检索的方法文件共享的方法（文件）,2023/7/16,操作系统复习,10,主要知识点,第八章连续组织方式的优缺点隐式连接、显示链接组织方式的优缺点索引组织方式的优缺点混合索引
4、文件最大容量的计算方法位示图法存储空间管理（位图计算）,2023/7/16,操作系统复习,11,主要知识点,第九章用户接口的类型主要联机命令Shell命令语言的主要简单命令系统调用的实现方法,2023/7/16,操作系统复习,12,1.假设有一磁盘含有64000块，块号记为164000，现用2000个32位(Bit)的字作该盘的位示图，试问第59999块对应于位示图中第几字的第几位(字、位均从0开始)；而第1599字的第17位对应于磁盘的第几块?解：由块号b，求字号i和位号j的公式为：i=(b-1)div 32(div表示整数除法，32是字长)j=(b-1)mod 32(mod表示整数相除取余
5、数)(59999-1)div 32=1874(59999-1)mod 32=30故59999块对应于位示图中第1874字的第30位。由位示图的字号i和位号j，求对应的磁盘块号b的公式为：b=i32+j+1=159932+17+1=51186即第1599字的第17位对应于磁盘的第51186块。,2023/7/16,操作系统复习,13,2.页式存储管理中，主存空间按页分配，可用一张“位示图”构成主存分配表。假设主存容量为2M字节，页面长度为512字节，若用字长为32位的字作主存分配的“位示图”需要多少个字？如页号从1开始，字号和字内位号（从高位到低位）均从1开始，试问：第2999页对应于何字何位；
6、99字19位又对应于第几页？解：(1)内存总块数=2MB/512B=4096位示图需要字数=4096/32=128(2)字号=(2999-1)/32+1=94位号=(2999-1)%32+1=23即第2999内存页对应于位示图中94字的23位。(3)99*（32-1）+19=3088即位示图99字19位对应于内存的3088页,2023/7/16,操作系统复习,14,2023/7/16,操作系统复习,15,3某多道程序设计系统供用户使用的主存为100KB，磁带机2台，打印机1台。采用可变分区内存管理，采用静态方式分配外围设备，忽略用户作业的I/O时间。现有如下作业序列：,作业调度采用FCFS策略
7、，优先分配主存低地址区域且不准移动已在主存中的作业，进程调度采用时间片轮转算法(即在主存中的作业均分CPU时间)。现求：,2023/7/16,操作系统复习,16,(1)作业被调度的先后次序；(2)全部作业运行结束的时间；(3)作业的平均周转时间；(4)最大作业周转时间。,作业达到及结束顺序分析：8:00J1到达，分配它所需资源(15KB内存、1台磁带机、1台打印机后，调入内存运行。余内存85KB、磁带机1台。8:20J2到达，因无打印机，不调入。同时J3到达，分配它内存60KB，磁带机1台，调入内存，与J1均分CPU时间运行。余内存25KB、磁带机和打印机都已分完(余0台)。8:30J1结束，
8、释放内存15KB、磁带机1台、打印机1台。虽有打印机但内存不够，J2仍不能调入；J4到达，因低端内存15KB不够，分配高端内存20KB和磁带机1台，调入内存与J3一起运行。剩下内存空闲块是15KB、5KB，打印机1台8:35J5到达，因无磁带机，不能调入。,2023/7/16,操作系统复习,17,9:00J3结束。释放资源后，系统有内存75KB，5KB、打印机和磁带机个1台。J2调入，内存余45KB，5KB、磁带机剩1台、打印机0台。J5仍不能进入(无打印机)。将J2、J4运行。J4还需运行5分钟。9:10J4结束，释放资源后，内存空余70KB、磁带机空2台、打印机0台。J5仍不能进入。J2单
9、独运行(还需5分钟)。9:15J2结束，释放资源后，内存有100KB、磁带机有2台、打印机有1台。J5调入运行。9:30J5结束。,解：(1)作业被调度的先后次序为J1,J3,J4,J2,J5(2)全部作业运行结束的时间为9:30(3)作业的平均周转时间为(30+55+40+40+55)5=44(分钟)(4)最大作业周转时间为55分钟。,2023/7/16,操作系统复习,18,CPU,磁带1,磁带2,打印机,8:00,8:20,J1,J1,J1,J1,J3,J3,8:30,J1,J1,J1结束,J4,J3,J2,J3到J2不入J3进入,J3,J4,8:35,J3,J4,J5到达J5不入,9:0
10、0,J4,J3,J3结束,9:10,J4结束,内存余,85K,25K,15,5,15,5,J2,J4,45,5,J4,J2,9:15,J2,J2,70K,J2结束,9:30,90K,J5,J5,J5,J5结束,J1到达J1进入,J4到达J2不入J4进入,J2进入,J5仍不能进入,J5进入,以下是画图分析法：,2023/7/16,操作系统复习,19,4多道批处理系统中配有一个处理器和2台外设(D1和D2)，用户存储空间为100MB。已知系统采用可抢占式的高优先数调度算法和不允许移动的可变分区分配策略，设备分配按照动态分配原则。今有4个作业同时提交给系统，如下表所示。,作业运行时间和I/O时间按下
11、述顺序进行：A.CPU(1分钟)，D1(2分钟)，D2(2分钟)B.CPU(3分钟)，D1(1分钟)C.CPU(2分钟)，D1(3分钟)，CPU(2分钟)D.CPU(4分钟)，D1(2分钟)忽略其他辅助操作，求4个作业的平均周转时间是多少分钟。,11分钟,分析见后页,2023/7/16,操作系统复习,20,CPU,D1,D2,时间,A的周转时间为12分钟B的周转时间为13分钟C的周转时间为7分钟D的周转时间为12分钟所以平均周转时间为(12+13+7+12)/4=11(分钟),5.有一个具有两道作业的批处理系统（最多可有两道作业同时装入内存执行），作业调度采用计算时间短的作业优先调度算法，进程
12、调度采用以优先数为基础的抢占式调度算法，今有如下作业序列，作业优先数即为进程优先数，优先数越小优先级越高：(1)列出所有作业进入内存时间及结束时间。(2)计算平均周转时间。,2023/7/16,操作系统复习,21,分析：10：10 J1到达，进入系统，运行10分钟10：20 J2到达，进入系统，因优先级高于J1抢夺CPU开始运行10：30 J3到达后备队列，因为系统已经载入2个作业，无法进入系统10：50 J2运行结束退出，J4到达，根据短作业优先，调入J4，由于 J1的优先级高于J4，J1开始运行11：00 J1运行结束退出，J3进入系统，由于J3优先级较高，开始运行11：25 J3运行结束
13、退出，J4开始运行11：45 J4运行结束,2023/7/16,操作系统复习,22,答：（1）各个作业进入主存时间、结束时间和周转时间如下表所示：（2）平均周转时间：（50+30+55+55）/4=47.5（min）,2023/7/16,操作系统复习,23,6有一个多道程序设计系统，采用不可移动的可变分区方式管理主存空间，设主存空间为100K，采用最先适应分配算法分配主存，作业调度采用响应比高者优先算法，进程调度采用时间片轮转算法（即内存中的作业均分CPU时间），今有如下作业序列：假定所有作业都是计算型作业且忽略系统调度时间。回答下列问题：(1)列表说明各个作业被装入主存的时间、完成时间和周转
14、时间；(2)写出各作业被调入主存的顺序；(3)计算5个作业的平均周转时间。,2023/7/16,操作系统复习,24,答：（1）各个作业被装入主存的时间、完成时间和周转时间如下表所示：（2）作业被调入主存的顺序为J1，J2，J5，J3，J4。（3）平均周转时间=（65+60+85+95+55）/5=72（分钟）。,2023/7/16,操作系统复习,25,26,信号量机制解决进程同步问题的一般方法：,为同步双方设置各自的信号量，初值为其初始状态可用的资源数(故该信号量称为资源信号量或私有信号量)；同步双方任一进程在进入临界区之前，应先对自己的信号量执行wait()操作，以测试是否有自己可用的资源。
15、若有资源可用，则进入临界区，否则阻塞；同步双方任一进程离开临界区后，应对合作方(对方)的信号量执行signal()操作，以通知(若对方处于阻塞状态，则唤醒它)对方已有资源可用(对方已可进入临界区)。,27,用信号量机制解决P-C问题的基本方法：,为生产者设置1个私有信号量empty，其初值为1，表示有1个空缓冲区；为消费者设置1个私有信号量full，其初值为0，表示开始时没有满缓冲区；（信号量初值由物理意义确定）生产者将产品存入缓冲区之前，应先测试缓冲区是否空：执行wait(empty)操作；离开临界区(存入产品)后，应通知(可能会唤醒)消费者：执行signal(full)操作；消费者从缓冲区
16、取产品之前，应先测试缓冲区是否满：执行wait(full)操作；离开临界区(取走产品)后，应通知(可能会唤醒)生产者：执行signal(empty)操作,2023/7/16,操作系统复习,28,7.进程P1使用缓冲区buffer向进程P2，P3，P4发送消息，要求每当P1向buffer中发消息时，只有当P2，P3，P4进程都读取这条消息后才可向buffer中发送新的消息。利用P、V原语描述如下图所示进程的动作序列。,2023/7/16,操作系统复习,29,设P1、P2、P3、P4的资源信号量分别为S1、S2、S3、S4semaphore S1,S2,S3,S4;S1.value=3;S2.va
17、le=S3.vale=S4.value=0;parbeginprocess P1 while(condition)P1生成一个消息；P（S1）；P（S1）；P（S1）；P1将消息存入缓冲区buffer；V（S2）；V（S3）；V（S4）；,解:,2023/7/16,操作系统复习,30,process Pi(i=2,3,4)while（condition）P（Si）；Pi从buffer中取出消息；V（S1）；Pi消费（使用）该消息；parend,2023/7/16,操作系统复习,31,8.有如下图所示的工作模型：三个进程P0、P1、P2和三个缓冲区B0、B1、B2，进程间借助相邻缓冲区传递消息：
18、P0每次从B0中取出一条消息经加工后送入B1中，P1每次从B1中取出一条消息经加工后送入B2中，P2每次从B2中取出一条消息经加工后送入B0中。B0，B1，B2分别可存放3，2，2个消息。初始时B0中有2个消息，B1，B2中各有1个消息。用P、V操作写出P0，P1，P2的同步及互斥流程。,2023/7/16,操作系统复习,32,分析：三个进程形成一个环，两两互为P-C因此设置6个资源信号量，另外需要再设置一个互斥信号量保证缓冲区的互斥访问；此外，本题请注意缓冲去开始是为非空状态，因此需要正确设置各个信号量的初始值解：semaphore empty0,full0,empty1,full1,emp
19、ty2,full2,mutex;empty0=1;full0=2;/冲区B0有2个消息，还可放1个消息empty1=1;full1=1;/冲区B1有1个消息，还可放1个消息empty2=1;full2=1;/冲区B2有1个消息，还可放1个消息mutex=1;/互斥信号量,2023/7/16,操作系统复习,33,parbeginProcess P0 while(1)P(full0);/看看B0中是否有消息 P(mutex);/互斥访问B0 从缓冲区B0中取一个消息x;V(mutex);V(empty0);/B0中空出一个存放消息的位置 加工消息x;P(empty1);/看看B1中是否可放一个消息
20、 P(mutex);/互斥访问B1 将加工后的x存入缓冲区B1;V(mutex);V(full1);/B1中增加一个消息,2023/7/16,操作系统复习,34,Process P1 while(1)P(full1);/看看B1中是否有消息 P(mutex);/互斥访问B1 从缓冲区B1中取一个消息y;V(mutex);V(empty1);/B1中空出一个存放消息的位置 加工消息y;P(empty2);/看看B2中是否可放一个消息 P(mutex);/互斥访问B2 将加工后的x存入缓冲区B2;V(mutex);V(full2);/B2中增加一个消息,2023/7/16,操作系统复习,35,Pr
21、ocess P2 while(1)P(full2);/看看B2中是否有消息 P(mutex);/互斥访问B2 从缓冲区B2中取一个消息z;V(mutex);V(empty2);/B2中空出一个存放消息的位置 加工消息z;P(empty0);/看看B0中是否可放一个消息 P(mutex);/互斥访问B0 将加工后的z存入缓冲区B0;V(mutex);V(full0);/B0中增加一个消息 parend,2023/7/16,操作系统复习,36,9.在一个生产车间中，有3个工人共同协作生产某种产品，工人1负责生产零件A并放入车间的货架，工人2负责生产零件B并放入车间的货架，工人3从货架上获取零件，并
22、将1个零件A和一个零件B组装成成品运出车间，车间的货架上最多共可以存放1000个零件，为了保证合理的库存和零件配比，当某种零件数量比另一种零件数量多出100个时，相应的工人暂时停止该种零件的生产。试用PV操作描述上述生产过程。,2023/7/16,操作系统复习,37,分析：这是2个生产者、1个消费者的问题；2个生产者公用一个缓冲区，因此Worker1和Worker2的资源信号量为空闲缓冲区empty；Worker3需要2种资源，因此设置资源信号量full1和full2；两种零件存在配比问题，可以使用2个资源信号量来控制，设为sa和sb；最后，需设置用于互斥访问的互斥信号量mutex解：sema
23、phore mutex，empty，full1，full2，sa，sb；mutex.vale=1；/互斥信号量empty.value=1000；/空闲货架位数，假设初始时货架全空fulla.value=fullb.value=0；/零件A和零件B的数量，sa.value=100；/sb.value=100；,2023/7/16,操作系统复习,38,Process Worker2 while(1)生产一个零件B；P（empty）；P（sb）；P（mutex）；将零件B放入货架；V（fullb）；V（sa）；V（mutex）；,Process Worker3 while(1)P（fulla）；P（
24、fullb）；P（mutex）；拿去零件A和B；V（empty）；V（empty）；V（mutex）；组装产品；PAREND,Process Worker1 while(1)生产一个零件B；P（empty）；P（sa）；P（mutex）：将零件A放入货架；V（fulla）；V（sb）；V（mutex）；,2023/7/16,操作系统复习,39,10.某银行提供1个服务窗口和10个顾客等待座位。顾客到达银行时，若有空座位，则到取号机领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：,cobegin process
25、 顾客i 从取号机获得 一个号码;等待叫号;获得服务;,process 营业员 while(TRUE)叫号;为顾客服务;,2023/7/16,操作系统复习,40,请添加必要的信号量和P、V（或wait()、signal()）操作实现上述过程的互斥和同步。要求写出完整的过程，说明信号量的含义并赋初值。,分析：semaphore mutex=1;/用于顾客取号的互斥信号量semaphore seat=10;/顾客等待座位的资源信号量，当没有空座位时顾客在其上阻塞semaphore S1=0;/营业员与顾客的同步信号量，当没有顾客时营业员在其上阻塞semaphore S2=0;/顾客与营业员的同步信
26、号量，等待叫号时顾客在其上阻塞,2023/7/16,操作系统复习,41,cobegin process 顾客i P(seat);/若没有空座位，顾客等待P(mutex);/取号互斥从取号机获得一个号码;V(mutex);V(S1);/通知营业员，已有顾客P(S2);等待叫号;V(seat);/空出一个座位获得服务;,2023/7/16,操作系统复习,42,process 营业员while(TRUE)P(S1);/若无顾客则等待V(S2);/唤醒等待叫号的顾客叫号;为顾客服务;,2023/7/16,操作系统复习,43,11.在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序
27、列是：115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题：(1)按FIFO调度算法，将产生多少次缺页中断？依次淘汰的页号是什么？缺页中断率为多少？(2)按LRU调度算法，将产生多少次缺页中断？依次淘汰的页号是什么？缺页中断率为多少？,答：由题目的已知条件，可得页面走向为：1,2,1,0,4,1,3,4,2,1(1)FIFO的页面置换图如下：按FIFO调度算法将产生5次缺页中断，依次淘汰的页号为0,1,2，缺页中断率为5/10=50%。,2023/7/16,操作系统复习,4
28、4,(2)LRU算法的页面置换图如下：按LRU调度算法将产生6次缺页中断，依次淘汰的页号为2,0,1,3，缺页中断率为6/10=60%。,2023/7/16,操作系统复习,45,2023/7/16,操作系统复习,46,12请求分页管理系统中，假设某进程的页表内容如下表所示。页表内容,页面大小为4KB，一次内存的访问时间是100ns，一次快表(TLB)的访问时间是10ns，处理一次缺页的平均时间为108ns(已含更新TLB和页表的时间)，进程的驻留集大小固定为2，采用最近最少使用置换算法(LRU)和局部淘汰策略。假设TLB初始为空；地址转换时先访问TLB，若TLB未命中，在访问页表(忽略访问页表
29、之后的TLB更新时间)；有效位为0表示页面不再内存，产生缺页中断，缺页中断后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：,2023/7/16,操作系统复习,47,(1)依次访问上述三个虚地址，各需多少时间？给出计算过程。(2)基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。,分析：考察点地址转换的过程 快表命中：快表访问时间+一次内存访问时间 快表未命中但未缺页：快表访问时间+二次内存访问时间（一次页表访问，一次实际地址访问）快表未命中且存在缺页：快表访问时间+二次内存访问时间+缺页处理时间,2023/7/16,操作系统复习
30、,48,(1)因页的大小为4KB，即212，故十六进制地址的低3位是页内偏移，高位是页号。2362H：页号P=2，访问快表10ns，因初始为空，访问页表100ns得到页框号，与页内偏移合成物理地址后访问内存100ns，共花时间10+100+100=210ns。1565H：P=1，访问快表10ns，落空，访问页表100ns缺页，进行缺页中断处理108ns，合成物理地址后访问内存100ns，共计10+100+108+100=318ns。25A5H：P=2，访问快表10ns命中，合成物理地址后访问内存100ns，共计110ns。(2)故访问1565H时，因在此之前刚刚访问2362H所在的2号页，按L
31、RU算法，应淘汰0号页，空出101H号页框存放逻辑地址1565H所在的1号页。由页框号101H和页内偏移565H合成得到虚地址1565H对应的物理地址为101565H。,13.某计算机主存按字节编址，逻辑地址和物理地址都是 32 位，页表项大小为 4 字节。请回答下列问题。1）若使用一级页表的分页存储管理方式，逻辑地址结构为：则页的大小是多少字节？页表最大占用多少字节？2）若使用二级页表的分页存储管理方式，逻辑地址结构为：设逻辑地址为 LA，请分别给出其对应的页目录号和页表索引的表达式。,2023/7/16,操作系统复习,49,物理地址3,物理地址3,0900 0000H,3）采用（1）中的分
32、页存储管理方式，一个代码段起始逻辑地址为 0000 8000H，其长度为 8 KB，被装载到从物理地址 0090 0000H 开始的连续主存空间中。页表从主存0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算出该代码段对应的两个页表项的物理地址（假设每个页表项的长度为4字节）、这两个页表项中的页框号以及代码页面 2 的起始物理地址。,2023/7/16,操作系统复习,50,物理地址3,2023/7/16,操作系统复习,51,（1）因为页内偏移量是 12 位，所以页大小为 4 KB，页表项数为 232/4K=220，该一级页表最大为 2204 B=4 MB
33、。（2）页目录号可表示为：(unsigned int)(LA)22)&0 x3FF。或INT(LA/pow(2,22)页表索引可表示为：(unsigned int)(LA)12)&0 x3FF。或(LA/pow(2,12)%pow(2,10)（3）代码页面 1 的逻辑地址为 0000 8000H，表明其位于第 8 个页处，对应页表中的第 8 个页表项，所以第 8 个页表项的物理地址=页表起始地址+8页表项的字节数=0020 0000H+84=0020 0020H。由此可得如下的答案：物理地址1：0020 0020H物理地址2：0020 0024H物理地址3：0900 1000H页框号1：090
34、0 0000H页框号2：0900 0001H,2023/7/16,操作系统复习,52,14设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页(Page)数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框(Page Frame)。在时刻260前的该进程访问情况如下表所示(访问位即使用位)。,当进程执行到时刻260时，要访问逻辑地址为17CAH的数据。请回答下列问题：（1）该逻辑地址的对应的页号是多少？（2）若采用先进先出(FIFO)置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。,2023/7/16,操作系统复习,5
35、3,（3）若采用时钟(CLOCK)置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程(设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，示意图如下)。,2023/7/16,操作系统复习,54,(1)17CAH=0001 0111 1100 1010B，表示页号的位是左边6位，即00101B，所以页号为5。根据FIFO算法，需要替换装入时间最早的页，故需要置换装入时间最早的0号页，即将5页装入7号页框中，所以物理地址为0001 1111 1100 1010B，换算成十六进制，为1FCAH。根据CLOCK算法，如果当前指针所指页框的使用位为0，则替换该页；否则将其使用位清零，并将指针
36、指向下一个页框，继续查找。根据题设和示意图，将从2号页框开始，前4次查找页框顺序为2479，并将对应页框的使用位清零。在第5次查找中，指针指向2号页框，因2号页框的使用位为0，故淘汰2号页框对应的2号页，把5号页装入2号页框中，并将对应的使用位置为1，所以对应的物理地址为0000 1011 1100 1010B，换算成十六进制，为0BCAH。,2023/7/16,操作系统复习,55,15.若递交给磁盘驱动程序的磁盘柱面请求按到达时间顺序分别是10、22、20、2、40、6和38，设磁头初始处于20柱面，磁头从一柱面移到另一相邻柱面的时间是2ms，则对于FCFS、最短寻道时间优先、电梯算法（初始
37、磁头向高柱面移动），平均寻道时间各为多少？,解：对于FCFS，服务顺序为10、22、20、2、40、6、38 平均寻道时间=(10+12+2+18+38+34+32)*2/7=41.71ms最短寻道时间优先，服务顺序为：20、22、10、6、2、38、40平均寻道时间=(0+2+12+4+4+36+2)*2/7=17.14ms电梯算法，服务顺序为：20、22、38、40、10、6、2平均寻道时间=(0+2+16+2+30+4+4)*2/8=16.57ms,2023/7/16,操作系统复习,56,16.设文件索引节点中有7个地址项，其中4个地址项是直接地址索引，2个地址项是一级间接地址索引，1个
38、地址项是二级间接地址索引，每个地址项大小为4字节。若磁盘索引块和磁盘数据块大小均为256字节，则可表示的单个文件最大长度是多少？,解：每个盘块存放的索引项=256/4=64（项）直接地址存储容量=4256=1KB 一级间址存储容量=264256=32KB 二级间址存储容量=16464256=1024KB 最大文件长度=1+32+1024=1057KB,2023/7/16,操作系统复习,57,17假设计算机系统采用CSCAN(循环扫描)磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。（1）请说明在上述条件下如何进行磁盘块空闲状态的管理。（2）设某单面磁盘旋转速度为每分钟600
39、0转，每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动(如下图所示)，磁道号请求队列为50,90,30,120，对请求队列中的每一个磁道需读取1个随机分布的扇区，则读完这4个扇区总共需要多少时间？给出计算过程。,2023/7/16,操作系统复习,58,磁头当前运动方向,0号磁道,随机分布的某扇区,100号磁道,2023/7/16,操作系统复习,59,解：(1)用位图表示磁盘的空闲块状态。每一位表示一个磁盘块的空闲状态，共需16384/32=512个字=5124个字节=2KB，正好可放在系统提供的内存中。(2)采用CSCAN
40、调度算法，访问磁道的顺序为120,30,50,90，则移动磁道长度为20+90+20+40=170，总的移动时间为1701ms=170ms。由于转速为6000r/m，则平均旋转延迟时间为60/(60002)1000ms=5ms，总的旋转时间为5ms4=20ms。由于转速为6000r/m，则读取一个磁道上的一个扇区的平均读取时间为10ms/100=0.1ms，总的读取扇区的时间=0.1ms4=0.4ms。读取上述磁道上的所有4个扇区所花费的总时间=170ms+20ms+0.4ms=190.4ms。,2023/7/16,操作系统复习,60,18.考虑一个存在于磁盘上的文件系统，其中的文件由大小为5
41、12B的逻辑块组成。假定每一个文件有一个文件目录项，该目录项包含该文件的文件名、文件长度以及第一块（或第一索引块）和最后一块的位置，而且该目录项位于内存。对于索引结构文件，该目录项指明第一索引块，该索引块又一次指向511个文件块（每个索引值占4B），且有一指向下一索引块的指针(指针占4B)。针对连续、链接、索引结构的每一种，如果当前位于逻辑块30（即之前最后一次访问的块是逻辑块30）且希望访问逻辑块20(假设逻辑块号从0开始编号)，那么，必须分别从磁盘上读多少个物理块？,2023/7/16,操作系统复习,61,解：(1)对于磁盘上的连续结构文件，由文件的逻辑块号、文件块大小、磁盘物理块大小以及
42、文件的首块位置，可以计算该逻辑块所在的物理块号（地址）A：A=A0+(N*L)/S=A0+20*512/2048=A0+5其中：A0为文件第0块位置，N为逻辑块号(N=20)，L为逻辑块长度(L=512)，S为磁盘块长度(由已知条件得S=511*4+1*4=2048)。因此，无论当前读写位置如何，要访问第20个逻辑块，只要直接读出文件的第6个物理块，即只需读1个磁盘块即可(因目录项已在内存)。,2023/7/16,操作系统复习,62,(2)对于磁盘上的链接结构文件，当前读写了逻辑块30，要访问逻辑块20，需要从文件开头开始。由前面分析知，磁盘块大小2048B，故每个盘块可存放4个逻辑块。逻辑块
43、20在文件的第6个物理块中，因此需依次读出第1、2、3、4、5等盘块，从第5个物理块获得第6个物理块的块号，在读出第6物理块，其开头的512B即是20号逻辑块的内容。所以，需读6个物理块。(3)对于磁盘上的索引结构文件，若要访问逻辑块20（假定此前在访问逻辑块30时已将索引块保存在内存），可在内存中的索引表中查到逻辑块20所在的第6个物理块号，再将该物理块读出来，其开头512B即是20号逻辑块的内容。因此需要读1个物理块。,19.一台转速为3600（转分）的磁盘，其存储密度为16.7（K/道）。已知磁盘由启动到运转平稳的时间为3ms，磁头臂的移动速度为0.3（ms/道），请回答：（1）设磁头的
44、当前位置在第20号磁道上，移动方向为磁道号增加的方向。若系统收到4条记录访问请求，请求序列如下表所示。请写出电梯调度算法的访问序列。（2）若上述4条记录的长度皆为16.7KB，求系统按电梯调度算法访问磁盘，上述4条记录的最长时间为多少？(计算时间时保留2位小数),2023/7/16,操作系统复习,63,2023/7/16,操作系统复习,64,解：（1）采用电梯调度算法的访问序列为：（20）2532187，即访问2、3、1、4号记录。（2）访问2号记录：寻道时间T2=0.3*5=1.5ms最大旋转一周时间R2=（60*1000）/3600=50/3ms=16.67 ms数据传输时间A2=旋转一周
45、时间=16.67 ms3项时间合计为34.84ms。访问3号记录：移臂时间T3=0.3*7=2.1ms最大旋转一周时间16.67 ms数据传输时间16.67 ms3项时间合计为35.44ms。所以，总的访问时间为：3+34.84+35.44+37.54+36.64=147.46ms,访问1号记录：移臂时间T1=0.3*14=4.2ms最大旋转一周时间16.67 ms数据传输时间16.67 ms3项时间合计为37.54ms。访问4号记录：移臂时间T4=0.3*11=3.3ms最大旋转一周时间16.67 ms数据传输时间16.67 ms3项时间合计为36.64ms。,2023/7/16,操作系统复
46、习,65,19设某计算机系统有1台输入机，1台打印机。现有2道程序同时投入运行，且程序A先开始运行，程序B后运行。程序A的运行轨迹为：计算50ms，打印100ms，再计算50ms，打印信息100ms，结束。程序B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试说明：（1）两道程序运行时，CPU有无空闲等待？若有，在哪段时间等待？为什么？（2）程序A、B运行时有无等待现象？若有，在什么时候发生等待现象？,【注】本题属于其他类型题。,2023/7/16,操作系统复习,66,解：(1)我们可以画出CPU的运行轨迹图如下图粗线所示。,0,50,100,150,200,A打印,3
47、00,ms,A,B,A打印,B输入,从上图可以看出，CPU有等待时间，在100ms到150ms之间，共空闲50ms。在这段时间，A等待打印完成，B等待输入数据，CPU无事可做。（2）程序A无等待现象；程序B有等待现象，在050ms之间以及180ms200ms之间等待CPU。,2023/7/16,操作系统复习,67,20假定某系统当时的资源分配图如下所示：,题19图,（1）分析当时系统是否存在死锁。（2）若进程P3再申请R3时，系统将发生什么变化，说明原因。,2023/7/16,操作系统复习,68,解：(1)因为当时系统的资源分配图中不存在环路所以不存在死锁。(2)当进程P3申请资源R3后，资源分配图中形成环路P2R2P3R3P2，而R2,R3都是单个资源的类，该环路无法消除，所以进程P2，P3永远处于等待状态从而引起死锁。,
