操作系统复习2016.pptx

《操作系统复习2016.pptx》由会员分享，可在线阅读，更多相关《操作系统复习2016.pptx（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、注意要点考核形式试卷，闭卷考试，120分钟可以带计算器，但不得使用手机中的计算器功能试卷占总评成绩的80%考察范围第一章第九章部分章节除外2023/2/221第1页/共68页题型分布单选题15题，共30分填空题10题，共10分综合应用题6题，共60分2023/2/222第2页/共68页主要知识点第一章操作系统的目标操作系统的作用三种经典的操作系统类型分时系统的特征实时系统的特征操作系统的基本特征用户接口的种类2023/2/223第3页/共68页主要知识点第二章顺序执行程序的主要特征并发执行程序的主要特征进程的特征进程的各个状态，及各状态之间的转换条件导致进程创建、终止、阻塞的条件同步机制的4条

2、设计原则进程同步：只需要掌握用信号量解决P-C问题进程通信的方法2023/2/224第4页/共68页主要知识点第三章处理机的调度层次调度算法：FIFO，SJF，高相应比优先，时间片轮转产生死锁的4个必要条件银行家算法资源分配图的简化2023/2/225第5页/共68页主要知识点第四章动态分区分配中分配和回收内存的方法动态分区分配算法：FF，NF，BF，WF逻辑地址到物理地址的转换及访问时间的计算多级页表段页式存储管理的地址转换（虚地址到实地址的转换）2023/2/226第6页/共68页主要知识点第五章虚拟存储器的特征页面置换算法及缺页率的计算最佳，FIFO，LRU，时钟置换抖动的概念2023/

3、2/227第7页/共68页主要知识点第六章I/O系统的基本功能I/O系统的层次结构I/O设备的类型设备控制器的基本功能单缓冲和双缓冲传输时间的计算磁盘访问时间的计算磁盘调度算法：FCFS，SSTF，SCAN，CSCAN2023/2/228第8页/共68页主要知识点第七章文件的组织分类及其特征目录管理的要求目录结构的组织形式目录检索的方法文件共享的方法（文件）2023/2/229第9页/共68页主要知识点第八章连续组织方式的优缺点隐式连接、显示链接组织方式的优缺点索引组织方式的优缺点混合索引文件最大容量的计算方法位示图法存储空间管理（位图计算）2023/2/2210第10页/共68页主要知识点第

4、九章用户接口的类型主要联机命令Shell命令语言的主要简单命令系统调用的实现方法2023/2/2211第11页/共68页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表示整数相除取余数)(59999-1)div 32=1874 (59999-1)mod 32=30故59999块对应于位示图中第

5、1874字的第30位。由位示图的字号i和位号j，求对应的磁盘块号b的公式为：b=i32+j+1=159932+17+1=51186即第1599字的第17位对应于磁盘的第51186块。2023/2/2212第12页/共68页2.页式存储管理中，主存空间按页分配，可用一张“位示图”构成主存分配表。假设主存容量为2M字节，页面长度为512字节，若用字长为32位的字作主存分配的“位示图”需要多少个字？如页号从1开始，字号和字内位号（从高位到低位）均从1开始，试问：第2999页对应于何字何位；99字19位又对应于第几页？解：(1)内存总块数=2MB/512B=4096位示图需要字数=4096/32=12

6、8(2)字号=(2999-1)/32+1=94位号=(2999-1)%32+1=23即第2999内存页对应于位示图中94字的23位。(3)99*（32-1）+19=3088即位示图99字19位对应于内存的3088页2023/2/2213第13页/共68页2023/2/22143某某多多道道程程序序设设计计系系统统供供用用户户使使用用的的主主存存为为100KB，磁磁带带机机2台台，打打印印机机1台台。采采用用可可变变分分区区内内存存管管理理，采采用用静静态态方方式式分分配配外外围围设设备备，忽忽略略用用户户作作业业的的I/O时时间间。现现有有如如下下作作业业序序列：列：作业名作业名提交时间提交时

7、间需运行时间需运行时间主存需求量主存需求量磁带机需求磁带机需求打印机需求打印机需求J18:0025分钟分钟15KB11J28:2010分钟分钟30KB01J38:2020分钟分钟60KB10J48:3020分钟分钟20KB10J58:3515分钟分钟10KB11作作业业调调度度采采用用FCFS策策略略，优优先先分分配配主主存存低低地地址址区区域域且且不不准准移移动动已已在在主主存存中中的的作作业业，进进程程调调度度采采用用时时间间片片轮轮转转算算法法(即即在在主存中的作业均分主存中的作业均分CPU时间时间)。现求：。现求：第14页/共68页2023/2/2215(1)作业被调度的先后次序；作业

8、被调度的先后次序；(2)全部作业运行结束的时间；全部作业运行结束的时间；(3)作业的平均周转时间；作业的平均周转时间；(4)最大作业周转时间。最大作业周转时间。作业达到及结束顺序分析：作业达到及结束顺序分析：8:00J1到到达达，分分配配它它所所需需资资源源(15KB内内存存、1台台磁磁带带机机、1台打印机后，调入内存运行。余内存台打印机后，调入内存运行。余内存85KB、磁带机、磁带机1台。台。8:20J2到到达达，因因无无打打印印机机，不不调调入入。同同时时J3到到达达，分分配配它它内内存存60KB，磁磁带带机机1台台，调调入入内内存存，与与J1均均分分CPU时时间间运运行行。余内存余内存2

9、5KB、磁带机和打印机都已分完、磁带机和打印机都已分完(余余0台台)。8:30J1结结束束，释释放放内内存存15KB、磁磁带带机机1台台、打打印印机机1台台。虽虽有有打打印印机机但但内内存存不不够够，J2仍仍不不能能调调入入；J4到到达达，因因低低端端内内存存15KB不不够够，分分配配高高端端内内存存20KB和和磁磁带带机机1台台，调调入入内内存存与与J3一起运行。剩下内存空闲块是一起运行。剩下内存空闲块是15KB、5KB，打印机，打印机1台台8:35J5到达，因无磁带机，不能调入。到达，因无磁带机，不能调入。第15页/共68页2023/2/22169:00J3结结束束。释释放放资资源源后后，

10、系系统统有有内内存存75KB，5KB、打打印印机机和和磁磁带带机机个个1台台。J2调调入入，内内存存余余45KB，5KB、磁磁带带机机剩剩1台台、打打印印机机0台台。J5仍仍不不能能进进入入(无无打打印印机机)。将将J2、J4运运行行。J4还需运行还需运行5分钟。分钟。9:10J4结结束束，释释放放资资源源后后，内内存存空空余余70KB、磁磁带带机机空空2台台、打印机打印机0台。台。J5仍不能进入。仍不能进入。J2单独运行单独运行(还需还需5分钟分钟)。9:15J2结结束束，释释放放资资源源后后，内内存存有有100KB、磁磁带带机机有有2台台、打印机有打印机有1台。台。J5调入运行。调入运行。

11、9:30J5结束。结束。解：解：(1)作业被调度的先后次序为作业被调度的先后次序为J1,J3,J4,J2,J5(2)全部作业运行结束的时间为全部作业运行结束的时间为9:30(3)作业的平均周转时间为作业的平均周转时间为(30+55+40+40+55)5=44(分钟分钟)(4)最大作业周转时间为最大作业周转时间为55分钟。分钟。第16页/共68页2023/2/2217CPU磁带磁带1磁带磁带2打印机打印机8:008:20J1J1J1J1,J3J38:30J1J1J1结束结束J4J3J2,J3到到J2不入不入J3进入进入J3,J48:35J3,J4J5到达到达J5不入不入9:00J4J3J3结束结

12、束9:10J4结束结束内存余内存余85K25K15,515,5J2,J445,5J4J29:15J2J270KJ2结束结束9:3090KJ5J5J5J5结束结束J1到达到达J1进入进入J4到达到达J2不入不入J4进入进入J2进入进入J5仍不仍不能进入能进入J5进入进入以下是画图分析法：以下是画图分析法：第17页/共68页2023/2/22184多多道道批批处处理理系系统统中中配配有有一一个个处处理理器器和和2台台外外设设(D1和和D2)，用用户户存存储储空空间间为为100MB。已已知知系系统统采采用用可可抢抢占占式式的的高高优优先先数数调调度度算算法法和和不不允允许许移移动动的的可可变变分分区

13、区分分配配策策略略，设设备备分分配配按按照照动动态态分分配原则。今有配原则。今有4个作业同时提交给系统，如下表所示。个作业同时提交给系统，如下表所示。作业名作业名优先数优先数运行时间运行时间内存需求内存需求A65分钟分钟50MB34分钟分钟10MC87分钟分钟60MD46分钟分钟20M作业运行时间和作业运行时间和I/O时间按下述顺序进行：时间按下述顺序进行：A.CPU(1分钟分钟)，D1(2分钟分钟)，D2(2分钟分钟)B.CPU(3分钟分钟)，D1(1分钟分钟)C.CPU(2分钟分钟)，D1(3分钟分钟)，CPU(2分钟分钟)D.CPU(4分钟分钟)，D1(2分钟分钟)忽略其他辅助操作，求忽

14、略其他辅助操作，求4个作业的平均周转时间是多少分钟。个作业的平均周转时间是多少分钟。11分钟分钟分析见后页分析见后页第18页/共68页2023/2/2219C C D D D C C A D BBBC C CA A D D BA A12345678910 11 12 13CPUD1D2时间时间A的周转时间为的周转时间为12分钟分钟B的周转时间为的周转时间为13分钟分钟C的周转时间为的周转时间为7分钟分钟D的周转时间为的周转时间为12分钟分钟所以平均周转时间为所以平均周转时间为(12+13+7+12)/4=11(分钟分钟)第19页/共68页5.有一个具有两道作业的批处理系统（最多可有两道作业同时

15、装入内存执行），作业调度采用计算时间短的作业优先调度算法，进程调度采用以优先数为基础的抢占式调度算法，今有如下作业序列，作业优先数即为进程优先数，优先数越小优先级越高：(1)列出所有作业进入内存时间及结束时间。(2)计算平均周转时间。2023/2/2220作业名到达时间估计运行时间优先数J110:1020分钟5J210:2030分钟3J310:3025分钟4J410:5020分钟6第20页/共68页分析：10：10J1到达，进入系统，运行10分钟10：20J2到达，进入系统，因优先级高于J1抢夺CPU开始运行10：30J3到达后备队列，因为系统已经载入2个作业，无法进入系统10：50J2运行结

16、束退出，J4到达，根据短作业优先，调入J4，由于J1的优先级高于J4，J1开始运行11：00J1运行结束退出，J3进入系统，由于J3优先级较高，开始运行11：25J3运行结束退出，J4开始运行11：45J4运行结束2023/2/2221第21页/共68页答：（1）各个作业进入主存时间、结束时间和周转时间如下表所示：（2）平均周转时间：（50+30+55+55）/4=47.5（min）2023/2/2222作业名提交时间进入时间结束时间周转时间J110：1010：1011：0050J210：2010：2010：5030J310：3011：0011：2555J410：5010：5011：4555第

17、22页/共68页6有有一一个个多多道道程程序序设设计计系系统统，采采用用不不可可移移动动的的可可变变分分区区方方式式管管理理主主存存空空间间，设设主主存存空空间间为为100K，采采用用最最先先适适应应分分配配算算法法分分配配主主存存，作作业业调调度度采采用用响响应应比比高高者者优优先先算算法法，进进程程调调度度采采用用时时间间片片轮轮转转算算法法（即即内内存存中中的的作作业业均均分分CPU时时间间），今今有有如如下下作作业序列：业序列：假假定定所所有有作作业业都都是是计计算算型型作作业业且且忽忽略略系系统统调调度度时时间间。回回答答下下列列问题：问题：(1)列表说明各个作业被装入主存的时间、完

18、成时间和周转时间；列表说明各个作业被装入主存的时间、完成时间和周转时间；(2)写出各作业被调入主存的顺序；写出各作业被调入主存的顺序；(3)计算计算5个作业的平均周转时间。个作业的平均周转时间。2023/2/2223作业名提交时间需要执行时间要求主存量J110:0040分钟25KJ210:1530分钟60KJ310:3020分钟50KJ410:3525分钟18KJ510:4015分钟20K第23页/共68页答答：（1）各各个个作作业业被被装装入入主主存存的的时时间间、完完成成时时间间和和周周转转时时间间如下表所示：如下表所示：（2）作业被调入主存的顺序为）作业被调入主存的顺序为J1，J2，J5

19、，J3，J4。（3）平均周转时间）平均周转时间=（65+60+85+95+55）/5=72（分钟）。（分钟）。2023/2/2224作业名装入主存时间 作业完成时间 周转时间J110：0011：0565J210：1511：1560J311：1511：5585J411：3512：1095J511：0511：3555第24页/共68页25信号量机制解决进程同步问题的一般方法：1.为同同步步双双方方设置置各各自自的的信信号号量量，初初值为其其初初始始状状态可可用用的的资源源数数(故故该信信号号量量称称为资资源源信信号号量量或或私有信号量私有信号量)；2.同同步步双双方方任任一一进程程在在进入入临界界

20、区区之之前前，应先先对自自己己的的信信号号量量执行行wait()操操作作，以以测测试试是是否否有有自自己己可可用用的的资源源。若若有有资源源可可用用，则进入入临界区，否界区，否则阻塞；阻塞；3.同同步步双双方方任任一一进程程离离开开临界界区区后后，应对合合作作方方(对方方)的的信信号号量量执行行signal()操操作作，以以通通知知(若若对方方处于于阻阻塞塞状状态，则唤醒醒它它)对方方已已有有资源可用源可用(对方已可方已可进入入临界区界区)。第25页/共68页26用信号量机制解决用信号量机制解决P-C问题的基本方法：问题的基本方法：1.为为生生产产者者设设置置1个个私私有有信信号号量量empt

21、y，其其初初值值为为1，表表示示有有1个个空空缓缓冲冲区区；为为消消费费者者设设置置1个个私私有有信信号号量量full，其其初初值值为为0，表表示示开开始始时时没没有有满满缓缓冲冲区区；（信号量初值由物理意义确定信号量初值由物理意义确定）2.生生产产者者将将产产品品存存入入缓缓冲冲区区之之前前，应应先先测测试试缓缓冲冲区区是是否否空空：执执行行wait(empty)操操作作；离离开开临临界界区区(存存入入产产品品)后后，应应通通知知(可可能能会会唤唤醒醒)消消费费者者：执执行行signal(full)操作；操作；3.消消费费者者从从缓缓冲冲区区取取产产品品之之前前，应应先先测测试试缓缓冲冲区区

22、是是否否满满：执执行行wait(full)操操作作；离离开开临临界界区区(取取走走产产品品)后后，应应 通通 知知(可可 能能 会会 唤唤 醒醒)生生 产产 者者：执执 行行signal(empty)操作操作第26页/共68页2023/2/22277.进进程程P1使使用用缓缓冲冲区区buffer向向进进程程P2，P3，P4发发送送消消息息，要要求求每每当当P1向向buffer中中发发消消息息时时，只只有有当当P2，P3，P4进进程程都都读读取取这这条条消消息息后后才才可可向向buffer中中发发送送新新的的消消息息。利利用用P、V原语描述如下图所示进程的动作序列。原语描述如下图所示进程的动作序

23、列。P1bufferP2P3P4第27页/共68页2023/2/2228设设P1、P2、P3、P4的资源信号量分别为的资源信号量分别为S1、S2、S3、S4semaphoreS1,S2,S3,S4;S1.value=3;S2.vale=S3.vale=S4.value=0;parbeginprocessP1while(condition)P1生成一个消息；生成一个消息；P（S1）；）；P（S1）；）；P（S1）；）；P1将消息存入缓冲区将消息存入缓冲区buffer；V（S2）；）；V（S3）；）；V（S4）；）；解解:第28页/共68页2023/2/2229processPi(i=2,3,4)

24、while（condition）P（Si）；）；Pi从从buffer中取出消息；中取出消息；V（S1）；）；Pi消费（使用）该消息；消费（使用）该消息；parend第29页/共68页2023/2/22308.有如下图所示的工作模型：有如下图所示的工作模型：三三个个进进程程P0、P1、P2和和三三个个缓缓冲冲区区B0、B1、B2，进进程程间间借借助助相相邻邻缓缓冲冲区区传传递递消消息息：P0每每次次从从B0中中取取出出一一条条消消息息经经加加工工后后送送入入B1中中，P1每每次次从从B1中中取取出出一一条条消消息息经经加加工工后后送送入入B2中中，P2每每次次从从B2中中取取出出一一条条消消息息

25、经经加加工工后后送送入入B0中中。B0，B1，B2分分别别可可存存放放3，2，2个个消消息息。初初始始时时B0中中有有2个个消消息息，B1，B2中中各各有有1个个消消息息。用用P、V操操作作写写出出P0，P1，P2的同步及互斥流程。的同步及互斥流程。第30页/共68页2023/2/2231分析：三个进程形成一个环，两两互为分析：三个进程形成一个环，两两互为P-C因此设置因此设置6个资源信号量，另外需要再设置一个互斥信号个资源信号量，另外需要再设置一个互斥信号量保证缓冲区的互斥访问；量保证缓冲区的互斥访问；此外，本题请注意缓冲去开始是为非空状态，因此需要正此外，本题请注意缓冲去开始是为非空状态，

26、因此需要正确设置各个信号量的初始值确设置各个信号量的初始值解：解：semaphoreempty0,full0,empty1,full1,empty2,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;/互斥信号量互斥信号量第31页/共68页2023/2/2232parbeginProcessP0while(1)P(ful

27、l0);/看看看看B0中是否有消息中是否有消息P(mutex);/互斥访问互斥访问B0从缓冲区从缓冲区B0中取一个消息中取一个消息x;V(mutex);V(empty0);/B0中空出一个存放消息的位置中空出一个存放消息的位置加工消息加工消息x;P(empty1);/看看看看B1中是否可放一个消息中是否可放一个消息P(mutex);/互斥访问互斥访问B1将加工后的将加工后的x存入缓冲区存入缓冲区B1;V(mutex);V(full1);/B1中增加一个消息中增加一个消息第32页/共68页2023/2/2233ProcessP1while(1)P(full1);/看看看看B1中是否有消息中是否有

28、消息P(mutex);/互斥访问互斥访问B1从缓冲区从缓冲区B1中取一个消息中取一个消息y;V(mutex);V(empty1);/B1中空出一个存放消息的位置中空出一个存放消息的位置加工消息加工消息y;P(empty2);/看看看看B2中是否可放一个消息中是否可放一个消息P(mutex);/互斥访问互斥访问B2将加工后的将加工后的x存入缓冲区存入缓冲区B2;V(mutex);V(full2);/B2中增加一个消息中增加一个消息第33页/共68页2023/2/2234ProcessP2while(1)P(full2);/看看看看B2中是否有消息中是否有消息P(mutex);/互斥访问互斥访问B

29、2从缓冲区从缓冲区B2中取一个消息中取一个消息z;V(mutex);V(empty2);/B2中空出一个存放消息的中空出一个存放消息的位置位置加工消息加工消息z;P(empty0);/看看看看B0中是否可放一个消息中是否可放一个消息P(mutex);/互斥访问互斥访问B0将加工后的将加工后的z存入缓冲区存入缓冲区B0;V(mutex);V(full0);/B0中增加一个消息中增加一个消息parend第34页/共68页2023/2/22359.在一个生产车间中，有在一个生产车间中，有3个工人共同协作个工人共同协作生产某种产品，工人生产某种产品，工人1负责生产零件负责生产零件A并放入并放入车间的货

30、架，工人车间的货架，工人2负责生产零件负责生产零件B并放入车并放入车间的货架，工人间的货架，工人3从货架上获取零件，并将从货架上获取零件，并将1个零件个零件A和一个零件和一个零件B组装成成品运出车间，组装成成品运出车间，车间的货架上最多共可以存放车间的货架上最多共可以存放1000个零件，个零件，为了保证合理的库存和零件配比，当某种零为了保证合理的库存和零件配比，当某种零件数量比另一种零件数量多出件数量比另一种零件数量多出100个时，相个时，相应的工人暂时停止该种零件的生产。试用应的工人暂时停止该种零件的生产。试用PV操作描述上述生产过程。操作描述上述生产过程。第35页/共68页2023/2/2

31、236分析：分析：1.这是这是2个生产者、个生产者、1个消费者的问题；个消费者的问题；2.2个生产者公用一个缓冲区，因此个生产者公用一个缓冲区，因此Worker1和和Worker2的资的资源信号量为空闲缓冲区源信号量为空闲缓冲区empty；3.Worker3需要需要2种资源，因此设置资源信号量种资源，因此设置资源信号量full1和和full2；4.两种零件存在配比问题，可以使用两种零件存在配比问题，可以使用2个资源信号量来控制，个资源信号量来控制，设为设为sa和和sb；5.最后，需设置用于互斥访问的互斥信号量最后，需设置用于互斥访问的互斥信号量mutex解：解：semaphoremutex，e

32、mpty，full1，full2，sa，sb；mutex.vale=1；/互斥信号量互斥信号量empty.value=1000；/空闲货架位数，假设初始时货架全空空闲货架位数，假设初始时货架全空fulla.value=fullb.value=0；/零件零件A和零件和零件B的数量，的数量，sa.value=100；/sb.value=100；第36页/共68页2023/2/2237ProcessWorker2while(1)生产一个零件生产一个零件B；P（empty）；）；P（sb）；）；P（mutex）；）；将零件将零件B放入货架；放入货架；V（fullb）；）；V（sa）；）；V（mutex

33、）；）；ProcessWorker3while(1)P（fulla）；）；P（fullb）；）；P（mutex）；）；拿去零件拿去零件A和和B；V（empty）；）；V（empty）；）；V（mutex）；）；组装产品；组装产品；PARENDProcessWorker1while(1)生产一个零件生产一个零件B；P（empty）；）；P（sa）；）；P（mutex）：）：将零件将零件A放入货架；放入货架；V（fulla）；）；V（sb）；）；V（mutex）；）；第37页/共68页2023/2/223810.某银行提供某银行提供1个服务窗口和个服务窗口和10个顾客等待座位。个顾客等待座位。顾客

34、到达银行时，若有空座位，则到取号机领取一顾客到达银行时，若有空座位，则到取号机领取一个号，等待叫号。取号机每次仅允许一位顾客使用。个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：服务。顾客和营业员的活动过程描述如下：cobegin process 顾客顾客i 从取号机获得从取号机获得 一个号码一个号码;等待叫号等待叫号;获得服务获得服务;process 营业员营业员 while(TRUE)叫号叫号;为顾客服务为顾客服务;第38页/共68页2023/2/2239请添加必要的

35、信号量和请添加必要的信号量和P、V（或（或wait()、signal()）操作实现上述过程的互斥和同步。要求写出完整）操作实现上述过程的互斥和同步。要求写出完整的过程，说明信号量的含义并赋初值。的过程，说明信号量的含义并赋初值。分析：分析：semaphore mutex=1;/用于顾客取号的互斥用于顾客取号的互斥信号量信号量semaphore seat=10;/顾客等待座位的资源顾客等待座位的资源信号量，当没有空座位时顾客在其上阻塞信号量，当没有空座位时顾客在其上阻塞semaphore S1=0;/营业员与顾客的同步营业员与顾客的同步信号量，当没有顾客时营业员在其上阻塞信号量，当没有顾客时营业

36、员在其上阻塞semaphore S2=0;/顾客与营业员的同步顾客与营业员的同步信号量，等待叫号时顾客在其上阻塞信号量，等待叫号时顾客在其上阻塞第39页/共68页2023/2/2240cobeginprocess顾客顾客iP(seat);/若没有空座位，顾客等待若没有空座位，顾客等待P(mutex);/取号互斥取号互斥从取号机获得一个号码从取号机获得一个号码;V(mutex);V(S1);/通知营业员，已有顾客通知营业员，已有顾客P(S2);等待叫号等待叫号;V(seat);/空出一个座位空出一个座位获得服务获得服务;第40页/共68页2023/2/2241process营业员营业员while

37、(TRUE)P(S1);/若无顾客则等待若无顾客则等待V(S2);/唤醒等待叫号的顾客唤醒等待叫号的顾客叫号叫号;为顾客服务为顾客服务;第41页/共68页2023/2/224211.在在一一个个采采用用页页式式虚虚拟拟存存储储管管理理的的系系统统中中，有有一一用用户户作作业业，它它依依次次要要访访问问的的字字地地址址序序列列是是：115，228，120，88，446，102，321，432，260，167，若若该该作作业业的的第第0页页已已经经装装入入主主存存，现现分分配配给给该该作作业业的的主主存存共共300字，页的大小为字，页的大小为100字，请回答下列问题：字，请回答下列问题：(1)按按

38、FIFO调调度度算算法法，将将产产生生多多少少次次缺缺页页中中断断？依依次次淘汰的页号是什么？缺页中断率为多少？淘汰的页号是什么？缺页中断率为多少？(2)按按LRU调调度度算算法法，将将产产生生多多少少次次缺缺页页中中断断？依依次次淘汰的页号是什么？缺页中断率为多少？淘汰的页号是什么？缺页中断率为多少？第42页/共68页答：由题目的已知条件，可得页面走向为：答：由题目的已知条件，可得页面走向为：1,2,1,0,4,1,3,4,2,1(1)FIFO的页面置换图如下：的页面置换图如下：按按FIFO调度算法将产生调度算法将产生5次缺页中断，依次淘汰的页次缺页中断，依次淘汰的页号为号为0,1,2，缺页

39、中断率为，缺页中断率为5/10=50%。2023/2/2243页面走向1210413421页帧00004444441111113333222222221是否缺页被淘汰页号012第43页/共68页(2)LRU算法的页面置换图如下：按LRU调度算法将产生6次缺页中断，依次淘汰的页号为2,0,1,3，缺页中断率为6/10=60%。2023/2/2244页面走向1210413421页帧12104134210121041342002104134是否缺页被淘汰页号2013第44页/共68页2023/2/224512请请求求分分页页管管理理系系统统中中，假假设设某某进进程程的的页页表表内内容容如如下下表表所

40、所示。示。页表内容页表内容页号页号页框页框(Pageframe)号号有效位（存在位）有效位（存在位）0101H1102254H1页页面面大大小小为为4KB，一一次次内内存存的的访访问问时时间间是是100ns，一一次次快快表表(TLB)的的访访问问时时间间是是10ns，处处理理一一次次缺缺页页的的平平均均时时间间为为108ns(已已含含更更新新TLB和和页页表表的的时时间间)，进进程程的的驻驻留留集集大大小小固固定定为为2，采采用用最最近近最最少少使使用用置置换换算算法法(LRU)和和局局部部淘淘汰汰策策略略。假假设设TLB初初始始为为空空；地地址址转转换换时时先先访访问问TLB，若若TLB未未

41、命命中中，在在访访问问页页表表(忽忽略略访访问问页页表表之之后后的的TLB更更新新时时间间)；有有效效位位为为0表表示示页页面面不不再再内内存存，产产生生缺缺页页中中断断，缺缺页页中中断断后后，返返回回到到产产生生缺缺页页中中断断的的指指令令处处重重新新执执行行。设设有有虚虚地地址址访访问问序序列列2362H、1565H、25A5H，请问：，请问：第45页/共68页2023/2/2246(1)依次访问上述三个虚地址，各需多少时间？给出计算过程。依次访问上述三个虚地址，各需多少时间？给出计算过程。(2)基基于于上上述述访访问问序序列列，虚虚地地址址1565H的的物物理理地地址址是是多多少少？请请

42、说明理由。说明理由。分析：考察点地址转换的过程分析：考察点地址转换的过程快表命中：快表命中：快表访问时间快表访问时间+一次内存访问时间一次内存访问时间快表未命中但未缺页：快表未命中但未缺页：快表访问时间快表访问时间+二次内存访问时间二次内存访问时间（一次页表访问，一次实际地址访问）（一次页表访问，一次实际地址访问）快表未命中且存在缺页：快表未命中且存在缺页：快表访问时间快表访问时间+二次内存访问时间二次内存访问时间+缺页处理时间缺页处理时间第46页/共68页2023/2/2247(1)因因页页的的大大小小为为4KB，即即212，故故十十六六进进制制地地址址的的低低3位位是是页页内偏移，高位是页

43、号。内偏移，高位是页号。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命命中中，合合成成物物理理地地址址后后

44、访访问问内内存存100ns，共计，共计110ns。(2)故故访访问问1565H时时，因因在在此此之之前前刚刚刚刚访访问问2362H所所在在的的2号号页页，按按LRU算算法法，应应淘淘汰汰0号号页页，空空出出101H号号页页框框存存放放逻逻辑辑地地址址1565H所所在在的的1号号页页。由由页页框框号号101H和和页页内内偏偏移移565H合合成成得得到虚地址到虚地址1565H对应的物理地址为对应的物理地址为101565H。第47页/共68页13.某计算机主存按字节编址，逻辑地址和物理地址都是 32 位，页表项大小为 4 字节。请回答下列问题。1）若使用一级页表的分页存储管理方式，逻辑地址结构为：则

45、页的大小是多少字节？页表最大占用多少字节？2）若使用二级页表的分页存储管理方式，逻辑地址结构为：设逻辑地址为 LA，请分别给出其对应的页目录号和页表索引的表达式。2023/2/2248页号（20 位）页内偏移量（12 位）页目录号（10 位）页表索引（10 位）页内偏移量（12 位）代码页面2代码页面1物理地址3物理地址30900 0000H第48页/共68页3）采用（1）中的分页存储管理方式，一个代码段起始逻辑地址为 0000 8000H，其长度为 8 KB，被装载到从物理地址 0090 0000H 开始的连续主存空间中。页表从主存0020 0000H 开始的物理地址处连续存放，如下图所示（

46、地址大小自下向上递增）。请计算出该代码段对应的两个页表项的物理地址（假设每个页表项的长度为4字节）、这两个页表项中的页框号以及代码页面2的起始物理地址。2023/2/2249物理地址3代码页面2代码页面1物理地址30900 0000H页表物理地址2页框号2物理地址1页框号102000000H第49页/共68页2023/2/2250（1）因为页内偏移量是 12 位，所以页大小为 4 KB，页表项数为 232/4K=220，该一级页表最大为 2204 B=4 MB。（2）页目录号可表示为：(unsigned int)(LA )22)&0 x3FF。或INT(LA/pow(2,22)页表索引可表示为

47、：(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：0900 0000H页框号2：0900 0001H第50页/共68页2023/2/225114设设某某计计算算机机的的逻逻辑辑地地址址

48、空空间间和和物物理理地地址址空空间间均均为为64KB，按按字字节节编编址址。若若某某进进程程最最多多需需要要6页页(Page)数数据据存存储储空空间间，页页的的大大小小为为1KB，操操作作系系统统采采用用固固定定分分配配局局部部置置换换策策略略为为此此进进程程分分配配4个个页页框框(PageFrame)。在在时时刻刻260前前的的该该进进程程访访问问情情况况如如下下表表所所示示(访问位即使用位访问位即使用位)。页号页号页框号页框号装入时间装入时间访问位访问位071301142301222001391601当当进进程程执执行行到到时时刻刻260时时，要要访访问问逻逻辑辑地地址址为为17CAH的的

49、数数据据。请回答下列问题：请回答下列问题：（1）该逻辑地址的对应的页号是多少？）该逻辑地址的对应的页号是多少？（2）若若采采用用先先进进先先出出(FIFO)置置换换算算法法，该该逻逻辑辑地地址址对对应应的的物物理地址是多少？要求给出计算过程。理地址是多少？要求给出计算过程。第51页/共68页2023/2/2252（3）若若采采用用时时钟钟(CLOCK)置置换换算算法法，该该逻逻辑辑地地址址对对应应的的物物理理地地址址是是多多少少？要要求求给给出出计计算算过过程程(设设搜搜索索下下一一页页的的指指针针沿沿顺顺时时针方向移动，且当前指向针方向移动，且当前指向2号页框，示意图如下号页框，示意图如下)

50、。0号页号页1号页号页2号页号页3号页号页2号页框号页框4号页框号页框7号页框号页框9号页框号页框第52页/共68页2023/2/2253(1)17CAH=0001011111001010B，表表示示页页号号的的位位是是左左边边6位位，即即00101B，所以页号为，所以页号为5。(2)根根据据FIFO算算法法，需需要要替替换换装装入入时时间间最最早早的的页页，故故需需要要置置换换装装入入时时间间最最早早的的0号号页页，即即将将5页页装装入入7号号页页框框中中，所所以以物物理理地地址址为为0001111111001010B，换换算算成成十十六六进进制制，为为1FCAH。(3)根根据据CLOCK算