发布时间 : 星期日 文章操作系统期末考试复习题（全）及提纲总结 - 图文更新完毕开始阅读
46.(8分) 设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。某进程最多需要6页数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框。
页号 0 1 2 3 页框号 7 4 2 9 装入时间 130 230 200 160 访问位 1 1 1 1
当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据。请回答下列问题： (1) 该逻辑地址对应的页号是多少?
(2) 若采用先进先出(FIFO)置换算法，求该逻辑地址对应的物理地址？要求给出计算过
程。
(3) 采用时钟(Clock)置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过
程。（设搜索下一页的指针按顺时针方向移动，且指向当前2号页框，示意图如题目所示） 解答、
（1）17CAH 转换为二进制为：0001 0111 1100 1010, 页的大小为1KB，所以页内偏移为10位，于是前6位是页号，所以其页号为0001 01，转换为10进制为5，所以，17CA对应的页号为5
（2）若采用先进先出置换算法，则被置换出的页号对应的页框号是7，因此对应的二进制物理地址为：0001 1111 1100 1010，转换为16进制位的物理地址为1FCAH
（3）若采用时钟算法，且当前指针指向2号页框，则第一次循环时，访问位都被置为0，在第二次循环时，将选择置换2号页框对应的页，因此对应的二进制物理地址为：0000 1011 1100 1010，转换为16进制物理地址为0BCAH
第一章 操作系统引论
1、 操作系统的目标：有效性（提高系统资源利用率、提高系统的吞吐量）、方便性、可扩充性、开放性 2、 操作系统的作用：OS作为用户与计算机硬件系统之间的接口、OS作为计算机系统资源的管理者、OS
实现了对计算机资源的抽象。
3、 推动提高计算机系统发展的主要动力：不断提高计算机资源的利用率、方便用户、器件的不断更新换
代、计算机体系结构的不断发展。
4、 OS作为用户与计算机硬件之间接口的含义是：OS处于用户与计算机硬件系统之间，用户通过OS来
使用计算机系统。
5、 OS:OS是一个系统软件，因而这种接口是软件接口。用户可以通过三种方式使用计算机：命令方式，
系统调用方式，图形、窗口方式。
6、 操作系统：是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。 操作系统的发张过程：
（1）无操作系统的计算机系统： 1、人工操作方式 2、脱机输入/输出方式
（2）单道批处理系统：由于系统对作业的处理都是成批的进行的且在内存中始终只保持一道多页。 单道批处理系统的特征：自动性、顺序性、单道性。
（3）多道批处理系统用户所提交的作业都先寸放在外村上并排列成一个队列，称为后备队列，然后由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。 优缺点：资源利用率搞、系统吞吐量大、平均周转时间长、无交互能力。
需要解决的问题：处理机管理问题、内存管理问题、I/O设备管理问题、文件管理问题、作业管理问题。 （4）分时系统：能很好多的将一抬计算机提供给多个用户同时使用，提高计算机的利用率。 分时系统实现中的关键问题：及时接受、及时处理。 分时系统的特征：多路性、独立性、及时性、交互性。 （5）实时系统
实时系统是指系统能及时火即时响应外部时间的请求，在规定的时间内完成对时间的处理，并控制所有实时任务协调一致的运行。 7、操作系统的基本特性 （1）并发性
并行性：是指两个或多个时间在同一时刻发生； 并发性：是指两个或多个时间在同一时间间隔内发生。 （2）引入进程
进程概念：是指在系统中能独立运行并作为资源分配的基本单位。它由一组机器指令、数据和堆栈等组成的，是一个能独立运行的活动实体。 目的：为了使得多个程序能并发执行。 （3）引入线程
概念：作为独立运行和独立调度的基本单位。 （4）共享性
概念：是指系统中的资源可供内存中多个并发执行的进程（线程）共同使用，相应的把这种资源共同使用称为资源共享。或称为资源复用。 方式：互斥共享方式、同时访问方式 （5）虚拟技术
概念：是指通过某种技术把一个物理试题变为若干个逻辑上的对应物。
实现方式：时分复用技术（实现虚拟处理机、虚拟设备等，以提高资源的利用率）、空分复用技术（虚拟磁盘技术、虚拟存储器技术）。 （6）异步性
8、操作系统的主要功能
（1）处理机管理功能：是创建和撤销进程（线程），对诸进程（线程）的运行进行协调，实现进程（线程）之间的信息交换，以及按照一定的算法把处理机分配给进程（线程）。
进程控制：是为了作业创建进程，撤销已结束的进程，以及控制进程在运行过程中的状态转换。 进程同步：为使多个进程能有条不紊的运行，系统中必须设置进程同步机制。
方式：进程互斥方式是之诸进程（线程）在对临界资源进行访问时，应采用互斥方式。进程同步方式：是指在相互合作去完成共同任务的诸进程（线程）间，由同步机构对它们的执行 次序加以协调。
进程通信任务：就是用来实现在相互合作的进程之间的信息交换。
调度包括作业调度和进程调度：作业调度的基本任务就是从后备队列中按照一定的算法，选择出若干个作
业，为它们分配运行所需的资源。进程调度的任务是从就绪队列中，按照一定的算法选出一个进程，把处理机分配给它，并为它设置运行现场，使进程投入执行。 （2）存储器管理功能
主要任务：为了多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率以及能从逻辑上扩充内存。存储器管理应具有内存分配，内存保护、地址映射和内存扩充等功能。 （3）设备管理功能：缓冲管理、设备分配、设备处理
（4）文件管理功能：文件存储空间的管理、目录管理、文件的读/写管理和保护（防止未径核准的用户存取文件、防止冒名顶替存取文件、防止以不正确的方式使用文件） （5）操作体统与用户之间的接口
用户接口：联机用户接口、脱机用户接口、图形用户接口
程序接口：是为了用户程序在执行中访问系统资源而设置的、用户程序存取得操作系统服务的唯一途径。
第二章
一、进程的基本概念 1、程序的顺序执行及其特征 特征：顺序性、封闭性、可再现性
2、前驱图：是一个有向无循环图、记为DAG、用于描述进程之间执行的前后关系。 3、进程的并发执行及其特征：间断性、失去封闭性、不可再现性、 4、进程的特征与状态：结构特征、动态性、并发性、独立性、异步性
定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单元。 5、进程的三种状态：继续状态、执行状态、阻塞状态。
6、挂起状态：终端用户的请求、父进程请求、负荷雕节的需要、操作系统的转换（活动就绪—静止就绪、活动阻塞—静止阻塞、静止就绪—活动就绪、静止阻塞—活动阻塞） 7、创建状态和终止状态
8、进程控制块（是进程存在的唯一标志）
作用：为了描述和控制进程的运行，系统为每个进程定义了一个数据结构
包括的信息：进程标识符（内部标识符、外部标志符）、处理机状态、进程调度信息、进程控制信息 二 进程控制: 1.进程的创建 2.进程的终止，3.进程的阻塞与唤醒 4.进程的挂起与激活
三 记录型信号量 在信号量机制中，除了素要一个用于代表资源数目的整型变量value外，还应增加一个进程链表指针L
四 经典进程的同步问题：
五 消息传递通信的实现方法：直接传递 间接传递
第三章处理机调度与死锁
概念：
1、 调度（High Level Scheduling）：高级调度又称作业调度或长程调度，主要功能是据某种算法，把外存
中处于后备队列中的那些作业调入内存，也就是说，它的调度对象是作业。
2、 中级调度：中级调度（*intermediate level scheduling）：又称中程调度。引入中级调度的主要目的是为
了提高内存利用率和系统吞吐量。
3、 低级调度（low Level cheduling）：称为进程调度或短程调度，他所调度的对象是进程。进程调度是一
中最基本的调度，在多批道处理、分时和实时三种类型的os中，都必须配置这级调度。
4、 调度算法的若干准则： (一) 面向用户的准则
周转时间短，响应时间快，截止时间保证，优先权准则 (二) 面向系统的准则
系统吞吐量高，处理机利用率好，各类资源的平衡利用 5、 进程调度方式
（1） 非抢占方式：采用这种调度方式时，一旦把处理机分配给某进程后，不管它要运行多长时间，都
一直让它运行下去，绝不会因为时钟中断而抢占正在运行进程的处理机，也不允许其它进程抢占分配给它的处理机。直至该进程完成，自愿释放处理机，或发生某种事件而被阻塞时，才在把处理机分配给其他进程。
（2） 抢占方式：这种调度方式允许调度程序根据某种原则暂停某个正在运行的进程，将已经分配给进
程的处理机重新分配给另一进程。
6、 调度算法
（1） 先来先服务调度算法（FCFS）
该算法是一种简单的调度算法，它既可用于作业调度，也可用于进程调度。在进程调度中采用FCFS算法时，将选择最先进入就绪的进程投入执行，该算法属于非抢占调度方式，其特点是简单、易于实现，但不利于短作业和I\\O型作业的运行。 （2） 短作业进程优先算法（SJF）
该算法是之短作业或短进程优先调度算法。短进程优先调度算法是选择就绪队列中估计运行时间最短的进程投入执行，它既可采用抢占方式，也可采用非抢占方式，抢占的SPF算法通常也叫做最短剩余时间优先算法。SPF算法能有效的缩短作业的平均周转时间，提高系统的吞吐量，但不利于长作业和紧迫作业的运行。由于估计时间不一定准确，它不一定能真正的做到短作业优先。 （3） 高优先权优先算法（HPF）
该算法也是一种既可用于作业调度，也可用于进程调度的算法，在用于进程调度时，它将选择就绪队列中优先权做高的进程投入执行。它既可采用抢占方式，也可采用非抢占方式。 （4） 高响应比优先调度算法（HRRN）
该算法实际上是一种动态优先权调度算法，它以响应比作为进程的动态优先权，即选择响应比最高的进程投入执行。其目的是既照顾作业，有考虑到作业的等待时间，是长作业不会长期等待；但每次调度前，都要进行响应比的计算，会增加系统开销。
响应比=响应时间/要求服务时间=（等待时间+要求服务时间）/要求服务时间 （5） 时间片轮转法（RR）
在分时系统中都采用时间片轮转法进行进程调度。在简单的轮转算法中，系统将所有的就绪进程按FIFO规则排成一个队列，将CPUf分配给队首进程，且规定它最多只能执行一个时间片，若时间片用完时进程仍未完成，也必须将其插入就绪队列末尾，并把CPU交给下一个进程。时间片轮转法属于抢占调度方式，其特点是简单易行，平均响应时间短，但它不利于处理紧急作业。 7、 产生死锁的必要条件
互斥条件，请求与保持条件，不剥夺条件，环路等待条件 8、 预防死锁的办法
摒弃 “请求与保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件 9、银行家算法
第四章：
1、熟悉内存的连续分配方式 连续分配方式可分为：
A单一连续分配：只能用于单用户，单任务的操作系统中。采用这种存储管理方式可把内存分为系统区和用户区两部分。