操作系统复习资料

1、、第一章 操作系统的概念1、OS的基本概念： P1-3OS的定义：是管理系统资源、控制程序执行，改善人机界面，提供各种服务，合理组织计算机 工作流程和为用户有效使用计算机提供良好运行环境的一种系统软件。OS的目的： 1）方便性 2 ）有效性 3 ）可扩充性 4 ）开放性OS的作用： 1）OS作为用户与计算机硬件系统之间的接口2 ） OS作为计算机系统资源的管理者（资源分为四类：处理机，存储器，I/O 设备，信息）3 ） OS用作扩充机器（覆盖了软件的机器）2、OS的功能： P14存储器管理功能，主要包括：内存分配、地址映射、内存保护和内存扩充。 处理机管理功能，其功能包括：作业和进程调度，进程

2、控制和进程通信。 设备管理功能，主要包括：缓冲区管理、设备分配、设备驱动和设备无关性（设备处理） 文件管理功能，其功能包括：文件存储空间的管理、文件操作的一般管理、目录管理、文 件的读写管理，存取控制和保护。用户接口 （P18） ：命令接口、程序接口、图形接口3、OS的特征： P11操作系统作为一类系统软件有其基本特征：并存、共享和异步性。4、OS中的相关概念：多道程序技术 P6：在批处理系统中引入多道程序设计技术形成了多道批处理系统。进程： 3 种典型定义进程是程序的一次执行进程是一个程序及其数据在处理机上顺序执行时所发生的活动 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调

3、度的一个独立单位 线程：线程是操作系统分配 cpu 时间的基本单位，一个进程中可以有多个线程。 作业：5、OS的分类： P8分时（ a）与实时（ b）系统的主要区别。 （从一下几点比较）1 ）多路性：都有多路性， a 表现在允许一台主机上同时联接多台联机终端，系统按分时原则为每 个用户服务： b 还主要表现在系统经常对多路的现场信息进行采集，以及对多个对象或多个执行机 构进行控制2 ）独立性：都有独立性， a 中每个用户各占一个终端，彼此独立操作，互不干扰：而对b，对信息的采集和对对象的控制，也是彼此互不干扰的3 ）及时性：要求类似，都以人能接受的等待时间来确定，而 b 以控制对象所要求的开始

4、截止时间 或完成截止时间来确定4 ）交互性： a 能向终端用户提供数据处理服务，资源共享的服务 ;b 虽也有交互性，但此处人与系统的交互仅限于访问系统中某些特定的专用服务程序5 ）可靠性： b比 a要求高二、第二章 进程管理本章内容为掌握的重点，分成两部分：进程控制与同步、进程通信。1、程序的执行方式：顺序与并发，以及它们的区别P26顺序执行即在一个程序执行完后，才允许另一个程序执行2、程序并发执行的特征： P28失去封闭性：资源状态由多个程序改变间断性：“程序”是指令的有序集合，是“静态”的概念，而“计算”是指令序列在处理机 上的执行过程，是“动态”的概念。在并发执行中，一个共享程序可被多个

5、用户作业调用， 从而形成了多个间断的“计算”过程。形成相互制约关系不可再现性： 并发程序在执行期间可以相互制约。 前趋图可以是并发程序相互制约的示例。（P27）3、进程的引入：为了更好地描述系统中的并发活动。进程实体由程序，数据集合和PCB三部分组成#4、PCB（Process Control Block进程控制块）的构成及作用： P32进程控制块包括如下内容 ：（1）进程标识符：它是惟一的标志对应进程的一个标志符或数字；（2）处理机状态：包括是处理机的各种寄存器内容信息；（3）进程调度信息：表明该进程的执行状态；调度优先权：表示进程获取CPU的优先级别；进程之间通信信息：反映该进程与哪些进程

6、有什么样的通信关系；（4）进程控制信息：被保护的信息有：程序计数器程序状态字，各工作寄存器的内容等；资源需求、分配和控制方面的信息；进程实体信息：指出该进程的程序和数据的存储情况，在内存或外存的地址、大小等；族系关系：反映父子进程的隶属关系；其它信息：如文件信息、工作单位等。进程控制块的作用 ：进程控制块是进程组成中最关键的部分。每个进程有惟一的进程控制块。操作系统根据 PCB对进程实施控制和管理。进程的动态、并发等特征是利用PCB表现出来的。 PCB是进程存在的惟一标志。5、进程控制原语： P34所谓原语（ Primitive ）由若干条机器指令构成的并用以完成特定功能的一段程序，而且这段程

7、 序在执行期间不允许中断。原语又称为“原子操作（Atomic Operation） ”过程，作为一个整体而不可分割要么全都完成，要么全都不做。内核中有很多原语，如创建进程、终止进程、阻塞进程等。#6、进程同步1）进程间两种制约关系：1. 资源共享关系（进程间接制约） ：需互斥地访问资源2. 相互协作关系（进程直接制约） ：一个进程的执行依赖于另外一个 （几个 ）进程的完2）临界资源：一次仅允许一个进程使用的这类资源称为临界资源。P393）临界区：进程访问临界资源的那段程序代码叫临界区。P404）同步机制应遵循的规则：空闲让进、忙则等待、有限等待、让权等待。P415）信号量机制解决进程同步问题?

8、 Wait（s）? Signal（s）6）信号量的应用 1. 利用信号量实现互斥 2. 利用信号量来描述前趋关系7）经典进程同步问题编程求解（ P-C）（ P46）1、生产者 - 消费者问题2、哲学家进餐问题3、读者- 写者问题4、嗜睡的理发师问题 BP43。7、进程状态及变迁 P31图 2-51）P30三种基本状态是：进行态、就绪态和阻塞态（或等待态）（ 1）运行态（ Running ）运行状态是指当前进程已分配到CPU，它的程序正在处理机上执行时的状态。 此时正用 CPU。（2）就绪态（ Ready）就绪状态是指进程已具备运行条件，但因为其它进程正占用CPU，所以暂时不能运行而等待分配 C

9、PU的状态。 可运行, 但未分到 CPU。不能运3）阻塞态（ Blocked ）阻塞态是指进程因等待某种事件发生而暂时不能运行的状态。行, 等待某个外部事件发生 。2）进程状态的转换（ 1）就绪运行：处于就绪状态的进程被调度程序选中，分配到 CPU后，该进程的状态就由就绪 态变为运行态。（ 2）运行阻塞：正在运行的进程因某个条件未满足而放弃对CPU的占用，这个进程的状态就由运行态变为阻塞态。（3）阻塞就绪：处于阻塞状态的进程所等待事件发生了，系统就把该进程的状态由阻塞态变为 就绪态。（ 4）运行就绪： 正在运行的进程如用完了本次分配给它的CPU时间片， 它就得从 CPU上退下来 ,暂停运行。该

10、进程状态就由运行态变为就绪态 .同步机制。实现进程同步的机制有：标志位、加锁、信号量同步，要求能进行信号量的设置和编程。9、进程调度的方式（ P54）：进程调度方式有剥夺、非剥夺两种。#10、进程通信 P54（是高级通信 / 进程同步是低级通信）1）共享存储器系统 2 ）消息传递系统 3 ）管道通信（是基于文件的 /外存）三、第三章 处理机调度与死锁1、调度类型和调度队列 P70类型：高级调度（作业调度、长程调度、接纳调度） 低级调度（进程调度，短程调度） （抢占式 / 非抢占式） 中级调度（中程）调度队列： 1）仅有进程调度的调度队列模型（ P72）2）具有高级和低级调度队列的模型（P72）

11、3）同时具有三级调度队列的模型（P73）2、调度算法 P751 ）先来先服务（ FCFS）法 它的实现思想就是“排队买票”的办法，是非剥夺式的，最简单的一种调度算法，但效率 低下。有可能使作业长时间等待。2）短进程优先算法（ P76）：是剥夺式的，缺点是使用长进程等待更长的时间。FCFS实例作业情况进程名ABCDE平均调度算法到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149（a）带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398（b）带权周转时间12.673.11.52.252.13）优先级调度原则：将 CPU分

12、配给就绪队列中优先级最高的进程。进程优先级的两种确定方式：静态方式和动态方式。 P78（1） 静态优先级是在创建进程时就确定下来，而且在整个运行期间保持不变。（2） 动态优先级是随着进程的推进而不断改变的。4）高响应比优先算法（ P78） 这是一种兼顾短作业及等待时间两个因素的算法。在多个进程等待调度的情况下，以响应比高 者作为调度对象。响应比 =（等待时间 +估计运行时间） / 估计运行时间5）时间片轮转法（ RR）根据进程分配到的 CPU时间片，公平轮转，是剥夺式的。 具体：系统把所有就绪进程按先进先出的原则排成一个队列。新来的进程加到就绪队列末尾，每当执行进程调度时，进程调度程序总是选出

13、就绪队列的队首进程，让它在CPU上运行一个时间片的时间。时间片是一个小的时间单位。当时间片用完，该进程将置于就绪队列，重新等待分配 CPU 时间片。时间片大小的确定 :1）系统对响应时间的要求2）就绪队列中进程的数目3）系统的处理能力6）多级队列法（ P79）设置 n 级就绪队列，第一级队列的优先级最高，每次总是调度级别较高的队列中的进程。每个 就绪队列对应一个时间片，各级队列的时间片随级别递增（即级别越高，时间片越长） 。对第 n 级按 时间片轮转法调度，其余各级均按 FCFS法调度。多级队列法综合了多种因素，它根据进程运行情况的反馈信息对进程就绪队列进行组织并实施调度。 P80 图 3-5

14、.3. 死锁与避免 P90：产生死锁的必要条件 ： 如果在计算机系统中同时具备下面四个必要条件时，那么会发生死锁。即只要下面四个条件有 一个不具备，系统就不会出现死锁。互斥条件：即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的 进程占有。不可抢占条件：进程所获得的资源在未使用完毕之前，资源申请者不能强制地从资源占有 者手中夺取资源，而只能由该资源的占有者进程自行释放。占有且申请条件：进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外 进程占有，此时该进程阻塞；但是，它在等待新资源时，仍继续占用已占有的资源。 循环等待条件： 存在一个进程等待序列 P1 ，P2 P

15、n其中 P1 等待 P2 所占有的某一资源， P2 等待 P3 所占有的某一资源，而 Pn 等待 P1 所占有的资源，形成一个进程循环等待 环。上面提到的这四个条件在死锁时会同时发生。也就是说，只有一个必要条件不满足，则死锁就 可以排除。死锁的预防 （死锁预防是排除死锁的静态策略。 ）它的基本思想是要求进程申请资源时遵循某种协议，从而打破产生死锁的四个必要条件中的一个或几个，保证系统不会进入死锁的状态。打破互斥条件，即允许进程同时访问某些资源。此办法无实用价值。打破不可抢占条件。即允许进程强行从占有者那里夺取某些资源。这种方法实现起来困难，会 降低系统性能。打破占有且申请条件。可以实行资源预先

16、分配策略。即进程在运行前一次性地向系统申请它所 需要的全部资源。但也有缺点。打破循环等待条件，实行资源有序分配策略。死锁的避免 ：排除死锁的动态策略死锁的避免，它不限制进程有关申请资源的命令，而是对进程所发出 的每一个申请资源命令加以动态地检查，并根据检查的结果决定是否进行资源分配。死锁避免中应用到了安全序列的概念P94，其定义如下：所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列 P1 ，P2 Pn 就是安 全序列。如果存在这样一个安全序列，则系统是安全的。 P95 示例#银行家算法这是一个著名的避免死锁的算法（应很好地掌握） 。数据结构：

17、P95银行家算法步骤： P96 银行家算法示例 P97死锁的检测：资源分配图 P99（图 3-20 ）死锁定理 P99：如果能在资源分配图中，找到一个既不阻塞又非独立的进程结点，并将它消去， 使之成为孤立结点。依此类推，如能将所有结点都成为孤立结点。则称该图是可完全简化的。死锁状态的充分条件是：当且仅当 S 状态的资源分配图是不可完全简化的。该充分条件称为死 锁定理。死锁解除： P1001）剥夺资源法，从其它进程剥夺资源给死锁进程，以求解除死锁；2）撤消进程法，撤消死锁进程。四、第四章 存储管理重点掌握存储管理的功能，以及虚拟存储的概念和应用。具体的包括各种内存的分配策略、所 用的数据结构及算

18、法优劣的比较。1、分区管理 P107：固定分区、动态分区( FFBFWF) 、可重定位分区2、分页管理 P113：原理是将一个作业的地址空间与物理地址分成大小相同的页或帧，使得个作业可以被分配到不连接的区域。基本任务是实现页的虚拟地址到帧的映射。分页存储管理的基本方法是： 逻辑空间分页：将一个进程的逻辑地址空间划分成若干大小相等的部分，每一部分称做页面或 页，每页都有一个编号，叫做页号。内存空间分块：把内存也划分成与页面相同大小的若干个存储块，称做内存块或页框。 逻辑地址表示：在分页存储管理方式中，表示地址的结构。页号 p页内地址 d (位移量 w)内存分配原则：在分页情况下，系统以块为单位把

19、内存分给作业或进程，并且一个进程可装入 物理上不相邻的内存块中，页表，为解决作业或进程离散地分布在内存块中，系统为每个进程设立一张页面映象表，简称 页表。其作用是实现从页号到内存块的地址映射，如同邮政编码分页系统地址变换机构具有快表的地址变换机构分页地址结构3112 110页号 P位移 W逻辑地址 A；页大小 L（ 设为 1024）页号 P=INT(A/L) 页内偏移 d=A mod L如：A 2170B. 则 P=2, d=1223、动态分页 （即请求分页存储管理 , 是目前最常用的一种实现虚拟存储的方式 ）P128 ：基 本功能是调入策略、替换策略（页面置换算法）和地址变换的实现。缺页中断

20、机构 ：可在指令执行期间产生例:涉及 6 次缺页中断的指令 （如图）地址变换机构比基本分页机制，增加了中断处理页面置换算法页面置换算法的优劣影响系统效率，不好的算法可能导致“抖动”现象OPT、 #FIFO（先进先出） ：见书本 P143习题 23 题、LRU越界中断段表始址段表长度>段号（ 2）100段表寄存器逻辑地址8292物理地址4、分段管理 P119：原理是作业按逻辑段管理，段的大小长度不等。1k6k6004k5008k20092003段表段号 段长 基址 01分段系统地址变换机构5、段页式管理：将作业按段划分，每个段再划分成若干大小相同的页，其地址机构由段号、段内页号和页内相对位

21、移地址三部分组成。#6. 内存分配策略和分配算法（ P129）将内存分配涉及三个问题： 最小物理块数的确定、 物理块的分配策略和物理块的分配算法。 在为作业分配物理块时，将涉及到三个问题： 第一，确定为保证作业正常运行所需要的最少物理块数；第二，为每个作业分配的物理块，其数目是固定的还是可变的； 第三，对各作业所分配的物理块数， 是采取平均分配算法还是根据作业的大小按比例分配等。物理块的分配策略 P130 有三种： 固定分配局部置换：为作业分配固定的物理块，并当缺页时，只能在本程序内实现置换。 可变分配全局置换：为作业分配一定的物理块，当缺页时从系统中找到空闲块再分配之，系 统无空闲块时，从任

22、一进程中实现页的置换。可变分配局部置换：为作业分配物理块后，若缺页只能从本进程中实施页的置换，若系统发 现某进程频繁置换时，可再为之分配物理块，以使之降低缺页率。作业在内存中物理块数的分配算法（1）平均分配算法（2）按比例分配算法（3）优先权分配算法五、第五章 设备管理1、I/O 设备与 I/O 控制方式 P144，P1511 ）I/O 设备种类繁多，重要性能指标有：数据传输速率，数据传输单位，设备共享属性。 分别按以上三个指标分类：低速设备，中速设备，高速设备 块设备，字符设备 独占设备，共享设备，虚拟设备。2 ）I/O 控制方式：程序 I/O 方式，中断驱动 I/O 控制方式（了解），直接

23、存储器访问 DMA I/O 方式， I/O 通道控制方式2、中断处理过程（了解）3、缓冲技术 P155：是为了解决与低速 I/O 设备之间的矛盾而采用的技术。4、设备分配 P161（熟悉图 5-16 设备控制表）5.SPOOLing 技术为了缓和 CPU的高速性与 I/O 设备低速性间的矛盾而引入了脱机输入、 脱机输出技术。 组成spooling 组成：1） 输入和输出：在磁盘上开辟的 2 个大存储空间，模拟输入和输出设备。2）输入 buf 和输出 buf （内存中）输入设备输入 buf 输入 #用户区（ 1）用户区输出 #输出 buf 设备（ 2）3）输入 Spi 和输出 SPo进程。分别控

24、制（ 1），（2）的动作。SPi 相当于脱机输入控制器。SPo相当于脱机输出控制器。6，磁盘存储器管理 : 磁盘访问时间磁盘调度 :FCFS、SSTF、扫描 （SCAN）算法 、循环扫描 （CSCAN）算法FCFSSSTF SCANCSCAN100 道开始100 道开始100 道开始100 道开始下一个磁道移动距离下一个磁道移动距离下一个磁道移动距离下一个磁道移动距离5545901015050150505835832160101601039195531842418424182139169094181669072381583238201607018205533911501015013239165

25、51638112160103815831841461842418209032平均寻道长度： 55.3平均寻道长度： 27.5平均寻道长度：27.8平均寻道长度： 27.5六、第六章 文件管理1、文件与文件系统：文件是信息的一种组织方式，是在外存上具有标识名的一组相关数据 的集合。2、文件的特点： （P182）3、文件系统的功能4、文件的逻辑结构 P186：是从用户的观点出发所观察到的文件组织形式，是用户可以直接 处理的数据及其结构，它独立与文件的物理特性，又称为文件组织。可分为两类：有结构文件，无结构文件5、文件的物理结构 P191：又称文件的存储结构，指文件在外存上的存储组织形式。不仅与 存

26、储介质性能有关，而且与所采用的外存分配方式有关。6、文件的管理：文件的管理实际上是文件目录的管理。文件目录，是文件系统在创建每个 文件时，为文件建立的文件目录，也称文件说明或FCB，用于为文件设置文件描述和控制文件的数据结构，与文件一一对应。要求如下：1）实现“按名存取” 2）提高对目录的检索速度 3 ）文件共享 4）文件重命名7、目录文件：是文件系统管理文件的重要信息源，由全部的文件目录组成。常用目录结构 有单级目录、二级目录和多级目录。8、文件存储空间管理： P205：实现文件存储空间分配与空闲空间的组织。常用两种数据结 构：空闲链表与位示图。除此之外还有空闲表法，成组链接法。9、文件共享

27、与保护（ P209） 文件共享即指系统应允许多个用户（进程）共享同一份文件。七、第七章 操作系统接口1、用户接口包括：命令接口、程序接口、图形用户接口（注：其余章节自己复习）综合练习：选择题：1、 Linux 是（ A ）。）实时系统 ）分时系统）网络操作系统）文件系统分时 OS通常采用（ B ）策略为用户服务）可靠性和灵活性 ）时间片轮转 ）优先数 ）短作业优先 在下列 OS的组成中，（ A ）不需要硬件的支持。）进程调度 ）时钟管理 ）地址映射 ）中断系统 对进程的管理和控制使用的是（ B ）指令）原语）信号量）信箱通信若信号量S的初值为2，当前值为-1 ，则表示有（B ）个等待进程。）

28、0）1）2）36、对于两个并发进程，设互斥信号量mutex, 若 mutex=0, 则表示（ C ）没有进程进入临界区有一个进程进入临界区有一个进程进入临界区，另一个在等待两个都进入临界区系统在（ C ），发生从目态到管态的转换。 （目态：用户态，管态：系统态）发出 wait 操作时 ）发出 signal 操作时）执行系统调用时 ）执行置程序状态字时填空动态重定位技术依赖于重定位寄存器系统“抖动”现象是由于置换算法选择不当3、在虚拟存储系统中，若进程在内存中占3块，采用 FIFO 算法，当执行访问序列为 1，2，3，4，1，2，5，1，2，3，4，5，6，时，将产生 _10次缺页中断。（缺页率

29、为 10/13=76.92% ）（本题为 FIFO 页面置换算法的一例）4、采用段式存储的系统中，若地址用24位表示，其中 8 位表示段号，则允许每段的最大长度是 _2165、作业在执行中发生了缺页中断，经OS 处理后，应该让其执行（中断前 后 被中断 第一条） 被中断 指令。6、在页式管理系统中，页表如下：虚页号 物理页号0 21 12 63 34 7若页的大小这 4K，则将逻辑地址 0 转换成了 8192物理地址7、若有一分页系统，某作业的页表如下虚页号 物理页号0 21 3页面大小为 1024 字节，请将逻辑地址 1011，2148，3000，4000，5012，转化为物理地址 解：页面

30、大小为 1024 字节 =1K=210字节对十进制数逻辑地址 / 页面大小 =页号（虚页号）页内地址 转化后物理地址 =页号（对应的物理页号） * 页面大小 +页内地址 1011：1011/1K=0 1011,查表 0对应 2，故物理地址为 2*1K+1011=3059 2148：2148/1K=1 1124,查表 1对应 3，故物理地址为 3*1K+1124=3059 3000：3000/1K=2 952, 查表 2 对应 1，故物理地址为 1*1K+952=1976 4000：4000/1K=3 928, 查表 3 对应 6，故物理地址为 6*1K+928=7072 5012：5012/1

31、K=4 916, 查表，页号大于表长，则产生越界中断。8、若页面改为 2048 字节，且第 0，1，2 页依次存放在物理块 5，10，11 中，则逻辑地址 0A5C, 的物理地址是多少？解：页面大小为 2048字节=2K=211字节，则页内地址为 11位，题中 2F6AH很显然为一个十六进制的数，则地址长度为 4*4=16 位 （其中 H有两个十六进制数，因此页号为16-11=5 位。0A5C转换为二进制： 000010100101110000010100101110虚页号页内地址10100101110物理页号页内地址100100101110010100100101110010100100101110 转换为十六进制数为 525C（注意产生越界中断的情况）典型示例：BP23 读者- 写者问题 BP45BP63例2BP69 例 11，例 12Bp94例 10BP95 例 13 BP98例 16BP99 例 17，例 18综合题：1、将 BP53 第 5题改为：只有父亲一人放水果，可能放A或 O，如何改写程序？参考程序：int empty=1, a=o=0;f() while(1) cuts an applewait(empty);Put asignal(a); m() while(1)cuts an orangewaits (empty);put