操作系统复习市公开课一等奖百校联赛获奖课件.pptx

操作系统原理复习操作系统原理复习南京工业大学信息学院计算机系南京工业大学信息学院计算机系第第1页页注意关键点注意关键点n考评形式考评形式n试卷，闭卷考试，试卷，闭卷考试，120分钟分钟n能够带计算器，但不得使用手机中计算器功效能够带计算器，但不得使用手机中计算器功效n试卷占总评成绩试卷占总评成绩80%n考查范围考查范围n第一章第九章第一章第九章n部分章节除外部分章节除外/10/10操作系统复习2第第2页页题型分布题型分布n单项选择题单项选择题15题，共题，共30分分n填空题填空题10题，共题，共10分分n综合应用题综合应用题6题，共题，共60分分/10/10操作系统复习3第第3页页主要知识点主要知识点n第一章第一章n操作系统目标操作系统目标n操作系统作用操作系统作用n三种经典操作系统类型三种经典操作系统类型n分时系统特征分时系统特征n实时系统特征实时系统特征n操作系统基本特征操作系统基本特征n用户接口种类用户接口种类/10/10操作系统复习4第第4页页主要知识点主要知识点n第二章第二章n次序执行程序主要特征次序执行程序主要特征n并发执行程序主要特征并发执行程序主要特征n进程特征进程特征n进程各个状态，及各状态之间转换条件进程各个状态，及各状态之间转换条件n造成进程创建、终止、阻塞条件造成进程创建、终止、阻塞条件n同时机制同时机制4条设计标准条设计标准n进程同时：只需要掌握用信号量处理进程同时：只需要掌握用信号量处理P-C问题问题n进程通信方法进程通信方法/10/10操作系统复习5第第5页页主要知识点主要知识点n第三章第三章n处理机调度层次处理机调度层次n调度算法：调度算法：FIFO，SJF，高对应比优先，时间，高对应比优先，时间片轮转片轮转n产生死锁产生死锁4个必要条件个必要条件n银行家算法银行家算法n资源分配图简化资源分配图简化/10/10操作系统复习6第第6页页主要知识点主要知识点n第四章第四章n动态分区分配中分配和回收内存方法动态分区分配中分配和回收内存方法n动态分区分配算法：动态分区分配算法：FF，NF，BF，WFn逻辑地址到物理地址转换及访问时间计算逻辑地址到物理地址转换及访问时间计算n多级页表多级页表n段页式存放管理地址转换段页式存放管理地址转换n（虚地址到实地址转换）（虚地址到实地址转换）/10/10操作系统复习7第第7页页主要知识点主要知识点n第五章第五章n虚拟存放器特征虚拟存放器特征n页面置换算法及缺页率计算页面置换算法及缺页率计算n最正确，最正确，nFIFO，nLRU，n时钟置换时钟置换n抖动概念抖动概念/10/10操作系统复习8第第8页页主要知识点主要知识点n第六章第六章nI/O系统基本功效系统基本功效nI/O系统层次结构系统层次结构nI/O设备类型设备类型n设备控制器基本功效设备控制器基本功效n单缓冲和双缓冲传输时间计算单缓冲和双缓冲传输时间计算n磁盘访问时间计算磁盘访问时间计算n磁盘调度算法：磁盘调度算法：FCFS，SSTF，SCAN，CSCAN/10/10操作系统复习9第第9页页主要知识点主要知识点n第七章第七章n文件组织分类及其特征文件组织分类及其特征n目录管理要求目录管理要求n目录结构组织形式目录结构组织形式n目录检索方法目录检索方法n文件共享方法文件共享方法n（文件）（文件）/10/10操作系统复习10第第10页页主要知识点主要知识点n第八章第八章n连续组织方式优缺点连续组织方式优缺点n隐式连接、显示链接组织方式优缺点隐式连接、显示链接组织方式优缺点n索引组织方式优缺点索引组织方式优缺点n混合索引文件最大容量计算方法混合索引文件最大容量计算方法n位示图法存放空间管理（位图计算）位示图法存放空间管理（位图计算）/10/10操作系统复习11第第11页页主要知识点主要知识点n第九章第九章n用户接口类型用户接口类型n主要联机命令主要联机命令nShell命令语言主要简单命令命令语言主要简单命令n系统调用实现方法系统调用实现方法/10/10操作系统复习12第第12页页1.假设有一磁盘含有假设有一磁盘含有64000块，块号记为块，块号记为164000，现用，现用个个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块对应于位示图中第块对应于位示图中第1874字第字第30位。位。由位示图字号由位示图字号i和位号和位号j，求对应磁盘块号，求对应磁盘块号b公式为：公式为：b=i32+j+1=159932+17+1=51186即第即第1599字第字第17位对应于磁盘第位对应于磁盘第51186块。块。/10/10操作系统复习13第第13页页2.页式存放管理中，主存空间按页分配，可用一张页式存放管理中，主存空间按页分配，可用一张“位示图位示图”组成主存分配表。假设主存容量为组成主存分配表。假设主存容量为2M字字节，页面长度为节，页面长度为512字节，若用字长为字节，若用字长为32位字作主位字作主存分配存分配“位示图位示图”需要多少个字？如页号从需要多少个字？如页号从1开始，开始，字号和字内位号（从高位到低位）均从字号和字内位号（从高位到低位）均从1开始，试问：开始，试问：第第2999页对应于何字何位；页对应于何字何位；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页页/10/10操作系统复习14第第14页页/10/10操作系统复习153某某多多道道程程序序设设计计系系统统供供用用户户使使用用主主存存为为100KB，磁磁带带机机2台台，打打印印机机1台台。采采取取可可变变分分区区内内存存管管理理，采采取取静静态态方方式式分分配外围设备，忽略用户作业配外围设备，忽略用户作业I/O时间。现有以下作业序列：时间。现有以下作业序列：作作业业名名提交提交时间时间需运行需运行时间时间主存需求量主存需求量磁磁带带机需求机需求打印机需求打印机需求J18:0025分分钟钟15KB11J28:2010分分钟钟30KB01J38:2020分分钟钟60KB10J48:3020分分钟钟20KB10J58:3515分分钟钟10KB11作作业业调调度度采采取取FCFS策策略略，优优先先分分配配主主存存低低地地址址区区域域且且不不准准移移动动已已在在主主存存中中作作业业，进进程程调调度度采采取取时时间间片片轮轮转转算算法法(即即在在主主存中作业均分存中作业均分CPU时间时间)。现求：。现求：第第15页页/10/10操作系统复习16(1)作业被调度先后次序；作业被调度先后次序；(2)全部作业运行结束时间；全部作业运行结束时间；(3)作业平均周转时间；作业平均周转时间；(4)最大作业周转时间。最大作业周转时间。作业抵达及结束次序分析：作业抵达及结束次序分析：8:00J1抵抵达达，分分配配它它所所需需资资源源(15KB内内存存、1台台磁磁带带机机、1台打印机后，调入内存运行。余内存台打印机后，调入内存运行。余内存85KB、磁带机、磁带机1台。台。8:20J2抵抵达达，因因无无打打印印机机，不不调调入入。同同时时J3抵抵达达，分分配配它它内内存存60KB，磁磁带带机机1台台，调调入入内内存存，与与J1均均分分CPU时时间间运运行行。余内存余内存25KB、磁带机和打印机都已分完、磁带机和打印机都已分完(余余0台台)。8:30J1结结束束，释释放放内内存存15KB、磁磁带带机机1台台、打打印印机机1台台。虽虽有有打打印印机机但但内内存存不不够够，J2仍仍不不能能调调入入；J4抵抵达达，因因低低端端内内存存15KB不不够够，分分配配高高端端内内存存20KB和和磁磁带带机机1台台，调调入入内内存存与与J3一起运行。剩下内存空闲块是一起运行。剩下内存空闲块是15KB、5KB，打印机，打印机1台台8:35J5抵达，因无磁带机，不能调入。抵达，因无磁带机，不能调入。第第16页页/10/10操作系统复习179:00J3结结束束。释释放放资资源源后后，系系统统有有内内存存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调入运行。调入运行。9:30J5结束。结束。解：解：(1)作业被调度先后次序为作业被调度先后次序为J1,J3,J4,J2,J5(2)全部作业运行结束时间为全部作业运行结束时间为9:30(3)作业平均周转时间为作业平均周转时间为(30+55+40+40+55)5=44(分钟分钟)(4)最大作业周转时间为最大作业周转时间为55分钟。分钟。第第17页页/10/10操作系统复习18CPU磁带磁带1磁带磁带2打印机打印机8:008:20J1J1J1J1,J3J38:30J1J1J1结束结束J4J3J2,J3到到J2不入不入J3进入进入J3,J48:35J3,J4J5抵达抵达J5不入不入9:00J4J3J3结束结束9:10J4结束结束内存余内存余85K25K15,515,5J2,J445,5J4J29:15J2J270KJ2结束结束9:3090KJ5J5J5J5结束结束J1抵达抵达J1进入进入J4抵达抵达J2不入不入J4进入进入J2进入进入J5仍不仍不能进入能进入J5进入进入以下是画图分析法：以下是画图分析法：第第18页页/10/10操作系统复习194多多道道批批处处理理系系统统中中配配有有一一个个处处理理器器和和2台台外外设设(D1和和D2)，用用户户存存放放空空间间为为100MB。已已知知系系统统采采取取可可抢抢占占式式高高优优先先数数调调度度算算法法和和不不允允许许移移动动可可变变分分区区分分配配策策略略，设设备备分分配配按按照照动动态态分分配配标标准。今有准。今有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分钟分钟)忽略其它辅助操作，求忽略其它辅助操作，求4个作业平均周转时间是多少分钟。个作业平均周转时间是多少分钟。11分钟分钟分析见后页分析见后页第第19页页/10/10操作系统复习20C 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(分钟分钟)第第20页页5.有一个含有两道作业批处理系统（最多可有两道作业同有一个含有两道作业批处理系统（最多可有两道作业同时装入内存执行），作业调度采取计算时间短作业优先调度时装入内存执行），作业调度采取计算时间短作业优先调度算法，进程调度采取以优先数为基础抢占式调度算法，今有算法，进程调度采取以优先数为基础抢占式调度算法，今有以下作业序列，作业优先数即为进程优先数，优先数越小优以下作业序列，作业优先数即为进程优先数，优先数越小优先级越高：先级越高：(1)列出全部作业进入内存时间及结束时间。列出全部作业进入内存时间及结束时间。(2)计算平均周转时间。计算平均周转时间。/10/10操作系统复习21作业名 抵达时间抵达时间预计运行时间预计运行时间优先数J110:1020分钟5J210:2030分钟3J310:3025分钟4J410:5020分钟6第第21页页分析：分析：10：10J1抵达，进入系统，运行抵达，进入系统，运行10分钟分钟10：20J2抵达，进入系统，因优先级高于抵达，进入系统，因优先级高于J1抢夺抢夺CPU开始开始运行运行10：30J3抵达后备队列，因为系统已经载入抵达后备队列，因为系统已经载入2个作业，无个作业，无法进入系统法进入系统10：50J2运行结束退出，运行结束退出，J4抵达，依据短作业优先，调入抵达，依据短作业优先，调入J4，因为，因为J1优先级高于优先级高于J4，J1开始运行开始运行11：00J1运行结束退出，运行结束退出，J3进入系统，因为进入系统，因为J3优先级较高，优先级较高，开始运行开始运行11：25J3运行结束退出，运行结束退出，J4开始运行开始运行11：45J4运行结束运行结束/10/10操作系统复习22第第22页页答：（答：（1）各个作业进入主存时间、结束时间和周转时间以）各个作业进入主存时间、结束时间和周转时间以下表所表示：下表所表示：（2）平均周转时间：（）平均周转时间：（50+30+55+55）/4=47.5（min）/10/10操作系统复习23作业名提交时间进入时间结束时间周转时间J110：1010：1011：0050J210：2010：2010：5030J310：3011：0011：2555J410：5010：5011：4555第第23页页6有有一一个个多多道道程程序序设设计计系系统统，采采取取不不可可移移动动可可变变分分区区方方式式管管理理主主存存空空间间，设设主主存存空空间间为为100K，采采取取最最先先适适应应分分配配算算法法分分配配主主存存，作作业业调调度度采采取取响响应应比比高高者者优优先先算算法法，进进程程调调度度采采取取时时间间片片轮轮转转算算法法（即即内内存存中中作作业业均均分分CPU时时间间），今今有有以以下下作作业业序序列：列：假假定定全全部部作作业业都都是是计计算算型型作作业业且且忽忽略略系系统统调调度度时时间间。回回答答以以下下问题：问题：(1)列表说明各个作业被装入主存时间、完成时间和周转时间；列表说明各个作业被装入主存时间、完成时间和周转时间；(2)写出各作业被调入主存次序；写出各作业被调入主存次序；(3)计算计算5个作业平均周转时间。个作业平均周转时间。/10/10操作系统复习24作业名提交时间需要执行时间要求主存量J110:0040分钟25KJ210:1530分钟60KJ310:3020分钟50KJ410:3525分钟18KJ510:4015分钟20K第第24页页答答：（1）各各个个作作业业被被装装入入主主存存时时间间、完完成成时时间间和和周周转转时时间间以以下表所表示：下表所表示：（2）作业被调入主存次序为）作业被调入主存次序为J1，J2，J5，J3，J4。（3）平均周转时间）平均周转时间=（65+60+85+95+55）/5=72（分钟）。（分钟）。/10/10操作系统复习25作业名装入主存时间 作业完成时间 周转时间J110：0011：0565J210：1511：1560J311：1511：5585J411：3512：1095J511：0511：3555第第25页页26信号量机制处理进程同时问题普通方法：信号量机制处理进程同时问题普通方法：1.为为同同时时双双方方设设置置各各自自信信号号量量，初初值值为为其其初初始始状状态态可可用用资资源源数数(故故该该信信号号量量称称为为资资源源信信号号量量或或私私有有信号量信号量)；2.同同时时双双方方任任一一进进程程在在进进入入临临界界区区之之前前，应应先先对对自自己己信信号号量量执执行行wait()操操作作，以以测测试试是是否否有有自自己己可可用用资资源源。若若有有资资源源可可用用，则则进进入入临临界区，不然阻塞；界区，不然阻塞；3.同同时时双双方方任任一一进进程程离离开开临临界界区区后后，应应对对合合作作方方(对对方方)信信号号量量执执行行signal()操操作作，以以通通知知(若若对对方方处处于于阻阻塞塞状状态态，则则唤唤醒醒它它)对对方方已已经经有资源可用有资源可用(对方已可进入临界区对方已可进入临界区)。第第26页页27用信号量机制处理用信号量机制处理P-C问题基本方法：问题基本方法：1.为为生生产产者者设设置置1个个私私有有信信号号量量empty，其其初初值值为为1，表表示示有有1个个空空缓缓冲冲区区；为为消消费费者者设设置置1个个私私有有信信号号量量full，其其初初值值为为0，表表示示开开始始时时没没有有满满缓缓冲冲区区；（信号量初值由物理意义确定信号量初值由物理意义确定）2.生生产产者者将将产产品品存存入入缓缓冲冲区区之之前前，应应先先测测试试缓缓冲冲区区是是否否空空：执执行行wait(empty)操操作作；离离开开临临界界区区(存存入入产产品品)后后，应应通通知知(可可能能会会唤唤醒醒)消消费费者者：执执行行signal(full)操作；操作；3.消消费费者者从从缓缓冲冲区区取取产产品品之之前前，应应先先测测试试缓缓冲冲区区是是否否满满：执执行行wait(full)操操作作；离离开开临临界界区区(取取走走产产品品)后后，应应 通通 知知(可可 能能 会会 唤唤 醒醒)生生 产产 者者：执执 行行signal(empty)操作操作第第27页页/10/10操作系统复习287.进进程程P1使使用用缓缓冲冲区区buffer向向进进程程P2，P3，P4发发送送消消息息，要要求求每每当当P1向向buffer中中发发消消息息时时，只只有有当当P2，P3，P4进进程程都都读读取取这这条条消消息息后后才才可可向向buffer中中发发送送新新消消息息。利利用用P、V原语描述以下列图所表示进程动作序列。原语描述以下列图所表示进程动作序列。P1bufferP2P3P4第第28页页/10/10操作系统复习29设设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）；）；解解:第第29页页/10/10操作系统复习30processPi(i=2,3,4)while（condition）P（Si）；）；Pi从从buffer中取出消息；中取出消息；V（S1）；）；Pi消费（使用）该消息；消费（使用）该消息；parend第第30页页/10/10操作系统复习318.有以下列图所表示工作模型：有以下列图所表示工作模型：三三个个进进程程P0、P1、P2和和三三个个缓缓冲冲区区B0、B1、B2，进进程程间间借借助助相相邻邻缓缓冲冲区区传传递递消消息息：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同时及互斥流程。同时及互斥流程。第第31页页/10/10操作系统复习32分析：三个分析：三个进进程形成一个程形成一个环环，两两互，两两互为为P-C所以所以设设置置6个个资资源信号量，另外需要再源信号量，另外需要再设设置一个互斥信号置一个互斥信号量确保量确保缓缓冲区互斥冲区互斥访问访问；另外，本另外，本题请题请注意注意缓缓冲去开始是冲去开始是为为非空状非空状态态，所以需要正，所以需要正确确设设置各个信号量初始置各个信号量初始值值解：解：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;/互斥信号量互斥信号量第第32页页/10/10操作系统复习33parbeginProcessP0while(1)P(full0);/看看看看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中增加一个消息中增加一个消息第第33页页/10/10操作系统复习34ProcessP1while(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中增加一个消息中增加一个消息第第34页页/10/10操作系统复习35ProcessP2while(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第第35页页/10/10操作系统复习369.在一个生产车间中，有在一个生产车间中，有3个工人共同协作个工人共同协作生产某种产品，工人生产某种产品，工人1负责生产零件负责生产零件A并放入并放入车间货架，工人车间货架，工人2负责生产零件负责生产零件B并放入车间并放入车间货架，工人货架，工人3从货架上获取零件，并将从货架上获取零件，并将1个零个零件件A和一个零件和一个零件B组装成成品运出车间，车间组装成成品运出车间，车间货架上最多共能够存放货架上最多共能够存放1000个零件，为了个零件，为了确保合理库存和零件配比，当某种零件数量确保合理库存和零件配比，当某种零件数量比另一个零件数量多出比另一个零件数量多出100个时，对应工人个时，对应工人暂时停顿该种零件生产。试用暂时停顿该种零件生产。试用PV操作描述上操作描述上述生产过程。述生产过程。第第36页页/10/10操作系统复习37分析：分析：1.这这是是2个生个生产产者、者、1个消个消费费者者问题问题；2.2个生个生产产者公用一个者公用一个缓缓冲区，所以冲区，所以Worker1和和Worker2资资源源信号量信号量为为空空闲缓闲缓冲区冲区empty；3.Worker3需要需要2种种资资源，所以源，所以设设置置资资源信号量源信号量full1和和full2；4.两种零件存在配比两种零件存在配比问题问题，能，能够够使用使用2个个资资源信号量来控制，源信号量来控制，设为设为sa和和sb；5.最最终终，需，需设设置用于互斥置用于互斥访问访问互斥信号量互斥信号量mutex解：解：semaphoremutex，empty，full1，full2，sa，sb；mutex.vale=1；/互斥信号量互斥信号量empty.value=1000；/空空闲货闲货架位数，假架位数，假设设初始初始时货时货架全空架全空fulla.value=fullb.value=0；/零件零件A和零件和零件B数量，数量，sa.value=100；/sb.value=100；第第37页页/10/10操作系统复习38ProcessWorker2while(1)生生产产一个零件一个零件B；P（empty）；）；P（sb）；）；P（mutex）；）；将零件将零件B放入放入货货架；架；V（fullb）；）；V（sa）；）；V（mutex）；）；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）；）；第第38页页/10/10操作系统复习3910.某银行提供某银行提供1个服务窗口和个服务窗口和10个用户等候座位。个用户等候座位。用户抵达银行时，若有空座位，则到取号机领取一用户抵达银行时，若有空座位，则到取号机领取一个号，等候叫号。取号机每次仅允许一位用户使用。个号，等候叫号。取号机每次仅允许一位用户使用。当营业员空闲时，经过叫号选取一位用户，并为其当营业员空闲时，经过叫号选取一位用户，并为其服务。用户和营业员活动过程描述以下：服务。用户和营业员活动过程描述以下：cobegin process 用户用户i 从取号机取得从取号机取得 一个号码一个号码;等候叫号等候叫号;取得服务取得服务;process 营业员营业员 while(TRUE)叫号叫号;为用户服务为用户服务;第第39页页/10/10操作系统复习40请添加必要信号量和请添加必要信号量和P、V（或（或wait()、signal()）操作实现上述过程互斥和同时。要求写出完整过程，操作实现上述过程互斥和同时。要求写出完整过程，说明信号量含义并赋初值。说明信号量含义并赋初值。分析：分析：semaphore mutex=1;/用于用户取号互斥信用于用户取号互斥信号量号量semaphore seat=10;/用户等候座位资源信用户等候座位资源信号量，当没有空座位时用户在其上阻塞号量，当没有空座位时用户在其上阻塞semaphore S1=0;/营业员与用户同时信营业员与用户同时信号量，当没有用户时营业员在其上阻塞号量，当没有用户时营业员在其上阻塞semaphore S2=0;/用户与营业员同时信用户与营业员同时信号量，等候叫号时用户在其上阻塞号量，等候叫号时用户在其上阻塞第第40页页/10/10操作系统复习41cobeginprocess用户用户iP(seat);/若没有空座位，用户等候若没有空座位，用户等候P(mutex);/取号互斥取号互斥从取号机取得一个号码从取号机取得一个号码;V(mutex);V(S1);/通知营业员，已经有用户通知营业员，已经有用户P(S2);等候叫号等候叫号;V(seat);/空出一个座位空出一个座位取得服务取得服务;第第41页页/10/10操作系统复习42process营业员营业员while(TRUE)P(S1);/若无用户则等候若无用户则等候V(S2);/唤醒等候叫号用户唤醒等候叫号用户叫号叫号;为用户服务为用户服务;第第42页页/10/10操作系统复习4311.在在一一个个采采取取页页式式虚虚拟拟存存放放管管理理系系统统中中，有有一一用用户户作作业业，它它依依次次要要访访问问字字地地址址序序列列是是：115，228，120，88，446，102，321，432，260，167，若若该该作作业业第第0页页已已经经装装入入主主存存，现现分分配配给给该该作作业业主主存存共共300字字，页大小为页大小为100字，请回答以下问题：字，请回答以下问题：(1)按按FIFO调调度度算算法法，将将产产生生多多少少次次缺缺页页中中止止？依依次次淘汰页号是什么？缺页中止率为多少？淘汰页号是什么？缺页中止率为多少？(2)按按LRU调调度度算算法法，将将产产生生多多少少次次缺缺页页中中止止？依依次次淘汰页号是什么？缺页中止率为多少？淘汰页号是什么？缺页中止率为多少？第第43页页答：由题目标已知条件，可得页面走向为：答：由题目标已知条件，可得页面走向为：1,2,1,0,4,1,3,4,2,1(1)FIFO页面置换图以下：页面置换图以下：按按FIFO调度算法将产生调度算法将产生5次缺页中止，依次淘汰页号次缺页中止，依次淘汰页号为为0,1,2，缺页中止率为，缺页中止率为5/10=50%。/10/10操作系统复习44页面走向1210413421页帧00004444441111113333222222221是否缺页被淘汰页号012第第44页页(2)LRU算法页面置换图以下：算法页面置换图以下：按按LRU调度算法将产生调度算法将产生6次缺页中止，依次淘汰页号次缺页中止，依次淘汰页号为为2,0,1,3，缺页中止率为，缺页中止率为6/10=60%。/10/10操作系统复习45页面走向1210413421页帧12104134210121041342002104134是否缺页被淘汰页号2013第第45页页/10/10操作系统复习4612请请求求分分页页管管理理系系统统中中，假假设设某某进进程程页页表表内内容容以以下下表表所所表表示。示。页表内容页表内容页页号号页页框框(Pageframe)号号有效位（存在位）有效位（存在位）0101H1102254H1页页面面大大小小为为4KB，一一次次内内存存访访问问时时间间是是100ns，一一次次快快表表(TLB)访访问问时时间间是是10ns，处处理理一一次次缺缺页页平平均均时时间间为为108ns(已已含含更更新新TLB和和页页表表时时间间)，进进程程驻驻留留集集大大小小固固定定为为2，采采取取最最近近最最少少使使用用置置换换算算法法(LRU)和和局局部部淘淘汰汰策策略略。假假设设TLB初初始始为为空空；地地址址转转换换时时先先访访问问TLB，若若TLB未未命命中中，在在访访问问页页表表(忽忽略略访访问问页页表表之之后后TLB更更新新时时间间)；有有效效位位为为0表表示示页页面面不不再再内内存存，产产生生缺缺页页中中止止，缺缺页页中中止止后后，返返回回到到产产生生缺缺页页中中止止指指令令处处重重新新执行。设有虚地址访问序列执行。设有虚地址访问序列2362H、1565H、25A5H，请问：，请问：第第46页页/10/10操作系统复习47(1)依次访问上述三个虚地址，各需多少时间？给出计算过程。依次访问上述三个虚地址，各需多少时间？给出计算过程。(2)基基于于上上述述访访问问序序列列，虚虚地地址址1565H物物理理地地址址是是多多少少？请请说说明理由。明理由。分析：考查点地址转换过程分析：考查点地址转换过程快表命中：快表命中：快表访问时间快表访问时间+一次内存访问时间一次内存访问时间快表未命中但未缺页：快表未命中但未缺页：快表访问时间快表访问时间+二次内存访问时间二次内存访问时间（一次页表访问，一次实际地址访问）（一次页表访问，一次实际地址访问）快表未命中且存在缺页：快表未命中且存在缺页：快表访问时间快表访问时间+二次内存访问时间二次内存访问时间+缺页处理时间缺页处理时间第第47页页/10/10操作系统复习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号号页页，按按LRU算算法法，应应淘淘汰汰0号号页页，空空出出101H号号页页框框存存放放逻逻辑辑地地址址1565H所所在在1号号页页。由由页页框框号号101H和和页页内内偏偏移移565H合合成成得得到到虚地址虚地址1565H对应物理地址为对应物理地址为101565H。第第48页页13.某某计计算机主存按字算机主存按字节编节编址，址，逻辑逻辑地址和物理地址都是地址和物理地址都是 32 位，位，页页表表项项大小大小为为 4 字字节节。请请回答以下回答以下问题问题。1）若使用一）若使用一级页级页表分表分页页存放管理方式，存放管理方式，逻辑逻辑地址地址结结构构为为：则页则页大小是多少字大小是多少字节节？页页表最大占用多少字表最大占用多少字节节？2）若使用二）若使用二级页级页表分表分页页存放管理方式，存放管理方式，逻辑逻辑地址地址结结构构为为：设逻辑设逻辑地址地址为为 LA，请请分分别给别给出其出其对应页对应页目目录录号和号和页页表索引表表索引表示式。示式。/10/10操作系统复习49页号（页号（20 位）位）页内偏移量（页内偏移量（12 位）位）页目录号（页目录号（10 位）位）页表索引（页表索引（10 位）位）页内偏移量（页内偏移量（12 位）位）代代码页码页面面2代代码页码页面面1物理地址物理地址3物理地址物理地址30900 0000H第第49页页3）采取（）采取（1）中分）中分页页存放管理方式，一个代存放管理方式，一个代码码段起始段起始逻辑逻辑地址地址为为 0000 8000H，其，其长长度度为为 8 KB，被装，被装载载到从物理地址到从物理地址 0090 0000H 开始开始连续连续主存空主存空间间中。中。页页表从主存表从主存0020 0000H 开始物理开始物理地址地址处连续处连续存放，以下列存放，以下列图图所表示