操作系统复习指南讲义课件

1第一章1.1什么是操作系统掌握：操作系统的概念1.2操作系统的发展过程掌握：多道程序设计的原理及优点1.3现代操作系统类型掌握：现代操作系统的类型及各自的特点1.4操作系统的概念、特征和功能掌握：作业的概念、进程的概念、操作系统的特征、操作系统的主要功能2第二章存储管理2.1存储管理基础掌握：地址重定位的概念；静态重定位技术；动态重定位技术2.2基本存储管理方法了解：单一连续分区存储管理；固定分区存储管理2.3可变分区存储管理方法掌握：可变分区存储管理的基本原理;重点：可变分区内存的分配与回收算法；2.4内存扩充技术掌握：虚拟存储器的概念，虚拟存储器的容量限制。3第二章存储管理2.5纯分页的存储管理掌握：纯分页式存储管理的原理，重点：纯分页式存储管理地址定位问题。2.6请求分页系统掌握：请求页式系统的原理，重点：缺页中断机制及页面淘汰算法。2.7段式存储管理掌握：段式存储管理的地址定位2.8段页式存储管理掌握：段页式存储管理的地址定位4第三章进程管理3.1进程概述掌握：进程概念；进程组成；进程状态及其变换3.2进程控制块掌握：进程控制块的作用3.3调度掌握：三级调度的概念；调度算法（先进先出，短作业优先，时间片轮转，优先级，多级反馈队列）3.4UNIX系统的进程调度（了解）3.5进程控制（了解）3.6进程的创建和图像改换（了解）3.7线程（掌握线程的概念）5第四章进程通信4.1进程的同步与互斥掌握：同步互斥的基本概念4.2进程间互斥控制方法（了解）4.3信号量和Wait、Signal操作（重点掌握）4.4信号量的应用（重点掌握）4.5进程间的数据通信（了解）4.6软中断和信号机构（不要求）4.7死锁掌握：死锁产生的原因；发生死锁的4个必要条件；死锁预防；死锁避免（银行家算法）6第五章设备管理5.1引言掌握：设备的分类5.2操作系统与中断处理掌握：中断处理的基本过程5.3操作系统与时钟系统（不要求）5.4操作系统对I/O操作的控制掌握：DMA技术；通道技术；缓冲技术的基本原理5.5设备管理的数据结构（了解）5.6磁盘调度掌握：磁盘访问时间，磁盘调度算法（移臂调度）5.7UNIX系统V的设备管理（不要求）5.8设备分配（了解）7第六章文件管理6.1概述掌握：文件的逻辑结构分类6.2文件目录掌握：目录管理的要求，以及三种目录结构各种的特点。6.3文件存储资源分配掌握：文件的物理结构81.下列选项中，导致创建新进程的操作是（C）。(1)用户登录成功；(2)设备分配；(3)启动程序执行。A.（1）和（2）B.（2）和（3）C.（1）和（3）D.（1）、（2）、（3）2.以下所述步骤中，（A）不是创建进程所必需的。A.由调度程序为进程分配CPUB.建立一个进程控制块C.为进程分配内存D.将进程控制块链入到就绪队列93、从资源管理的角度来看，OS的主要功能是什么？现代OS的四大主要特征是什么？答：从资源管理的角度来看，OS的主要功能是控制和管理计算机中的软硬件资源，包括处理机管理、存储管理、设备管理、文件管理，并提供系统接口。现代OS的4大主要特征是：并发、共享、虚拟和不确定性。104、某基于动态分区存储管理的计算机，其主存容量为55MB（初始为空），采用最佳适配（BestFit）算法，分配和释放的顺序为：分配15M，分配30M，释放15M，分配8M，分配6M，此时主存中最大空闲分区的大小是（）答：9M115、什么是虚拟存储器？虚拟存储器技术究竟可运行多大的程序呢？虚存是由操作系统调度，采有内外存的交换技术，各道程序在必需使用时调入内存，不用的调出内存，这样好象内存容量不受限制。但要注意：(1)虚存容量不是无限的，极端情况受内存、外存的可使用的总容量限制；(2)虚存容量还受计算机总线长度的地址结构限制；126、请详细说明请求分页系统的地址变换过程。答：请求分页系统的地址变换过程如下：（图略去）1）取逻辑地址分解为页号P和页内偏移w;2)根据页号查找页表，获得该页的描述信息；3）若该页中断位为1，产生缺页中断；4）更新该页的描述信息；5）根据页块号和页内偏移w，计算物理地址。137.在一个分页式存储管理系统中，页表的内容如表所示。虚页号页架号021127若页面大小为4KB，则地址转换机构将相对地址0、1056、8423转换成的物理地址分别是多少？答：(1)0->8192;(2)1056->9248;(3)8423->28903148.有个一虚拟存储系统,每个进程在内存占有3页数据区,刚开始时数据区为空.有以下访页序列:2,3,4,5,3,4,1,2,3,5,1,4,2,4,5,1,3,2,1,3试给出下列情形下的缺页次数:

(1)系统采用先进先出(FIFO)淘汰算法.

(2)系统采用最近最少使用(LRU)淘汰算法.

(3)系统采用优化(OPT)淘汰算法.

15页面流缺页情况答：（1）采用FIFO算法：23453412351424513213234555123514225132222344451235144251333233345123511425111TTTTTTTTTTTTTTT缺页次数为15。16（2）采用LRU算法：23453412351424513213234534123514245132132345341235142451321234534123511245132TTTTTTTTTTTTTTT缺页次数为15。17（3）采用OPT算法：23453412351424513213234444122222222222222333333331444443333255555555555511111TTTTTTTTTT缺页次数为10。189.设某计算机的逻辑地址空间和物理地址空间均为64KB.按字节编址。若某进程最多需要6页（Page）数据存储空间，页的大小为1KB.操作系统采用固定分配局部置换策略为此进程分配4个页框（PageFame）.当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据，请问答下列问题：（1）该逻辑地址对应的页号是多少？（2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。页号页框号装入时刻访问位07130114230122200139160119解：（1）因为17ACH=（0001011111001010）2，由于采用固定分配局部置换策略，所以该进程只能占用4个页框。页大小为1KB，所以页内偏移量为10位，于是前6位为页号，对应的页号为5。（2）页面走向是：0，3，2，1，5。采用FIFO置换算法时的页面置换情况如表所示（需要替换装入时间最早的页面），从中看到被置换的页面所在的页框为7，所以17ACH对应的物理地址为（0001111111001010）2=1FCAH。页面走向03215物理块2222物理块411物理块700005物理块93333缺页否TTTTT2010、下列进程调度算法中，综合考虑进程等待时间和执行时间的是（）。A时间片轮转调度算法B短进程优先调度算法C先来先服务调度算法D高响应比优先调度算法解释：在高响应比调度算法中，响应比=（等待时间+估计作业运行时间）/估计作业运行时间。D2111.现有3个同时到达的作业J1、J2和J3，它们的执行时间分别为2、3和4，。系统按单道方式运行且采用短作业优先算法，则平均周转时间是（）。2212、一单道批处理系统中,有如下五个作业,并采用FCFS,SJF调度算法,试计算作业的平均周转时间和平均带权周转时间。(单位:小时)作业提交时间运行时间

１7．002．5２8．002.5３9．00149．000．50510．001．023答（1）FCFS算法：7点时作业1先运行,作业提交时间运行时间开始时间结束时间周转时间带权周转

１7．002．57．009．302.51２8．002.59.3012.0041.6３9．00112.0013.004449．000．5013.0013.304.59510．001．013.3014.306.56.524答（1）SJF算法：7点时作业1先运行,作业提交时间运行时间开始时间结束时间周转时间带权周转

１7．002．57．009．302.51２8．002.512.0014.306.52.6３9．00110.0011.002249．000．509.3010.0012510．001．011.0012.00222513.有4个进程P1，P2，P3，P4，它们进入就绪队列的先后次序为P1，P2，P3，P4，它们的优先级和需要的处理机时间如表所示。假定这四个进程执行过程中不会发生等待事件，忽略进程调度等所花费的时间，从某个时刻开始进程调度，请写出分别采用“先来先服务”、“非抢占式优先级”（固定优先级），“时间片轮转”调度算法中进程的执行次序。计算各个进程在就绪队列中的等待时间以及平均等待时间。进程处理机时间优先级P183P261P3225P444261）先来先服务算法进程的执行顺序P1、P2、P3、P4；进程P1等待时间为0；进程P2等待时间为8；进程P3等待时间为8＋6＝14；进程P4等待时间为8＋6＋22＝36；平均等待时间为（0+8+14+36）/4＝14.52）优先级算法进程的执行顺序P3、P4、P1、P2；进程P1等待时间为4+22＝26；进程P2等待时间为22+4+8＝34；进程P3等待时间为0；进程P4等待时间为22；平均等待时间为（26+34+0+22）/4＝20.5273）时间片轮转算法进程的执行顺序P1、P2、P3、P4、P1、P2、P3、P3、P3、P3；进程P1等待时间为0＋（5＋5＋4）＝14；进程P2等待时间为5＋（5＋4＋3）＝17；进程P3等待时间为（5＋5）＋（4＋3＋1）＝18；进程P4等待时间为5＋5＋5＝15；平均等待时间为（14+17+18+15）/4＝162814．下面对临界区的论述中，正确的论述是＿＿＿＿。A．临界区是指进程中用于实现进程互斥的那段代码。B．临界区是指进程中用于实现进程同步的那段代码。C．临界区是指进程中用于实现共享资源的那段代码。D．临界区是指进程中访问临界资源的那段代码。2915、设与某资源相关联的信号量初值为3，当前值为1，若M表示现在资源的可用个数，N表示等待资源的进程数，则M、N分别是（）。1，03016.有m个进程共享同一临界资源，若使用信号量机制实现对临界资源的互斥访问，则信号量值的变化范围是？范围：1—1-m3117、三个进程P1、P2、P3互斥使用一个包含N（N>0）个单元的缓冲区，P1每次用produce（）生成一个正整数并用put（）送入缓冲区的某一空单元中；P2每次用getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。32解：（1）缓冲区是一互斥资源，因此设互斥信号量mutex；（2）同步问题：P1、P2因为奇数的放置与取用而同步，设同步信号量odd；P1、P3因为偶数的放置与取用而同步，设同步信号量even；P1、P2、P3因为共享缓冲区，设同步信号量empty。P1、P2、P3的活动描述如下：semaphoremutex=1，odd=0,even=0,empty=N;进程P1while(true){number=produce();wait(empty);wait(mutex);put();signal(mutex);if(number%2==0) signal(even);else signal(odd);}进程P2while(true){ wait(odd); wait(mutex); getodd(); signal(mutex); signal(empty); countodd();}进程P3while(true){ wait(even); wait(mutex); geteven(); signal(mutex); signal(empty); counteven();}3318、什么是死锁？产生死锁的原因是什么？死锁产生的必要条件有哪些？答：两个或两个以上的进程在保持部分资源的同时等待本组其他进程占有的资源而形成的一种循环等待僵局叫死锁。死锁产生的原因是资源竞争以及进程推进顺序不当。死锁产生的必要条件是：互斥条件、不剥夺条件、占有并等待条件和环路等待条件。3419、请详细说明可通过哪些途径预防死锁？答：预防死锁是通过破坏死锁产生的必要条件来预防死锁发生的，具体如下：剥夺资源法：当进程阻塞时，剥夺该进程已获得的全部资源；全部分配法：当给进程分配资源时一次性地分配给进程所需要的全部资源，如资源不够分配，则进程一个资源都不分配；有序资源分配法：要求进程申请同类资源时采用全部分配的方法，而申请不同类资源时，按资源类别的序号从小到大的顺序申请。3520、系统中有3种类型的资源（A,B,C,）和5个进程P1,P2,P3,P4,P5,A资源总数为10，B为8，C为8，在T0时刻系统状态如下表。系统采用银行家算法实施死锁避免策略。试问：a:T0时刻此系统是否安全，若是，给出一个安全序列。b:此时若进程P2请求资源（1，1，0），是否能实施资源分配，为什么？c:在此基础上，若进程P1请求资源（2，0，1），能否实施资源分配，为什么？36

最大资源需求量已分配资源数量ABCABCP1773020P2334210P3912302P4233212P5434012解：依题意可得Available（3，3，2）a:T0时刻是安全的，安全序列为（P4,p2,p3,p5,p1）。（过程略）b:若进程P2请求资源Req（1，1，0），按银行家算法判断如下：371）判断Req(1，1，0)<=Need2(1,2,4),表示Req为合法请求；2）判断Req(1，1，0)<=Available（3，3，2），表示Req为可满足的请求；3）试探性分配

Available-=Req; 变为（2，2，2）

Alloc2+=Req; 变为（3，2，0）

Need2-=Req; 变为（0，1，4）4）判断新状态的安全性 新状态是安全的，可找到安全序列（P4,p2,p3,p5,p1）（具体过程在此略去）,因此可分配资源，Available变为（2,2,2）,38c:若进程P1请求资源Req（2，0，1），按银行家算法判断如下：1）判断Req(2,0,1)<=Need1(7,5,3),表示Req为合法请求；2）判断Req(2,0,1)<=Available（2，2，2），表示Req为可满足的请求；3）试探性分配

Available-=Req; 变为（0，2，1）

Alloc1+=Req; 变为（2，2，1）

Need1-=Req; 变为（5，5，2）4）判断新状态的安全性 新状态是不安全的，因为可利用资源只能满足P4后就不能满足任何进程的全部资源需求了，即找不到安全序列，此时系统进入不安全状态。因此，不能满足进程P1的资源请求Req（2，0，1）。3921、某系统同有m个同类资源被n个进程共享，请分别讨论当m>n和m<=n时，每个进程最多可以请求多少个资源才能保证系统不会发生死锁？当m<=n时，每个进程最多请求1个。当m>n时，如果m%n==0，每个进程最多请求m/n个。如果m%n<>0，每个进程最多请求(m/n)+1个4022、本地用户通过键盘登录系统时，首先获得键盘输入信息的程序是（）。A命令解释程序B中断处理程序C系统调用程序D用户登录程序23、程序员利用系统调用打开I/O设备时，通常使用的设备标识是（）。A逻辑设备名B物理设备名C主设备号D从设备号BA4124、简述中断处理过程。答：当中断发生时，一旦CPU响应中断，系统就开始进行中断处理，中断处理过程如下：（1）保护被中断进程的现场，为了在中断处理程序结束后能使进程正确的返回到中断点，系统必须保存当前处理机的状态字（PSW）和程序计数器（PC）等的值。（2）分析中断原因，转去执行相应的中断处理程序，在多个中断请求同时发生时，处理优先级最高的中断源发出的中断请求。（3）恢复被中断进程的现场，CPU继续执行原来被中断的进程。4225.磁盘访问时间一般要有哪几部分时间？简述磁盘调度算法中SSTF、Scan算法的原理。1）由三部分组成：寻道时间；等待时间；传送时间。2）SSTF算法选择从当前磁头位置出发，移动最少的磁盘I/O请求。2）Sc