操作系统复习.ppt

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