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