天津理工大学 2014-2015 操作系统复习

1、By Touchkiss第一章 引论【了解和知道】1. 小标题，概念，各种名词，基本控制，（填空选择）1. 操作系统的目标:有效性（提高系统资源利用率、提高系统的吞吐量）、方便性、可扩充性、开放性。2. 操作系统的作用（1） OS作为用户与计算机硬件系统之间的接口；（命令方式、系统调用方式、图形窗口方式）（2） OS作为计算机系统资源的管理者；（3） OS实现了对计算机资源的抽象。3. 推动操作系统发展的主要动力（1） 不断提高计算机资源的利用率；（2） 方便用户；（3） 器件的不断更新换代；（4） 计算机体系结构的不断发展。4. 单道批处理系统的特征：（1） 自动性。在顺利情况下，在磁带上的

2、一批作业能自动地逐个地依次运行，而无需人工干预。（2） 顺序性。磁带上的各道作业是顺序的进入内存，各道作业的完成顺序与他们进入内存的顺序，在正常情况下应完全相同，亦即先调入内存的作业先完成。（3） 单道性。内存中仅有一道程序运行，即监督程序每次从磁带上只调入一道程序进入内存运行，当该程序完成或发生异常情况时，才换入其后继程序进入内存运行。5. 多道批处理系统特点：（1） 资源利用率高；（2） 系统吞吐量大；（3） 平均周转时间长；（4） 无交互能力。6. 分时系统特点：（1） 多路性；（2） 独立性；（3） 及时性；（4） 交互性。7、操作系统的特征： 并发性、共享性、虚拟性、异步性。最基本的

3、是并发性。【重点】1.4 操作系统的主要功能：处理机管理功能：1、进程控制 2、进程同步：为多个进程的运行进行协调 进程互斥方式：诸进程在对临界资源进行访问时 进程同步方式：相互合作去完成共同任务时 3、进程通信：合作的进程处于同一计算机上采用直接通信方式。 4、调度：作业调度：选出若干作业，为他们分配资源 进程调度：从线程队列中选出一个线程，分配处理机存储器管理功能：1、内存分配：为每道程序分配内存空间，提高存储器的利用率，以减少不可用的内存空间。可采用动态和静态 2、内存保护：确保每道程序都在自己的内存空间内运行；决不允许用户程序访问操作系统的程序和数据；不允许用户程序转移到其他非共享程序

4、中去执行 3、地址映射 4、内存扩充：用来实现请求调入功能和置换功能。设备管理功能：1、缓冲管理：为了有效缓和CPU与IO设备速度不匹配的矛盾，提高CPU的利用率 2、设备分配 3、设备处理 4、虚拟设备文件管理功能：1、文件存储空间管理：提高外存利用率 2、目录管理 3、文件的读/写管理和保护操作系统与用户之间的接口：1、 用户接口2、 程序接口第二章 进程管理1.进程的基本概念：前趋图：有向无循环图，必须不存在循环进程与线程的关系：进程和线程都是由操作系统所体会的程序运行的基本单元。进程与线程的不同点【重点】（简答） 1、线程的划分尺度小于进程，使得多线程程序的并发性高。 2、进程在执行过

5、程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。 3、 每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。 4、从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。 2.进程同步：（貌似不考信号量）就绪和转换图 就绪(IO完成) (进程调度) (时间片完)阻塞 (IO请求) 执行 P34 程序顺序执行时的特征 顺序性封闭性可再现性P37 进程的特

6、征与状态【理解】 结构特征：程序段、相关的数据段、PCB动态性：最基本的特征。并发性：进程实体能和其他进程并发执行，而程序不能。独立性：进程实体是一个能独立运行，独立分配资源和独立接受调度的基本单位异步性：进程按各自独立地不可预知的速度前进。P38 进程的三种状态图2-5 进程的三种基本状态及其转换 就绪(IO完成) (进程调度) (时间片完)阻塞 (IO请求) 执行 P39 进入挂起状态的主要原因图2-6 具有挂起状态的进程状态图 1、终端用户的请求2、父进程的请求3、负荷调节的需要4、操作系统的需要P40 加了创建和终止的状态图 进程控制块的作用和组织方式对每个进程是不是只有一个，记录进程

7、的状态及名称，是不是在主存当中 对每个进程只有一个作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其他进程并发的进程. PCB是进程存在的唯一标志. PCB应常驻内存. 组织方式：1、链接方式：具有统一状态的PCB链接字链接的队列2、索引方式：根据所有进程的状态建立索引表2.2 进程控制：掌握各种状态的基本含义和过程2.3 进程同步：什么叫临界资源，同步机制应遵循的规则，信号量的主要应用P50 主要目的：同步，还有利用信号量实现前驱关系，进程互斥临界资源是一次仅允许一个进程使用的共享资源。各进程采取互斥的方式，实现共享的资源称作临界资源。属于临界

8、资源的硬件有打印机、磁带机等,软件有消息缓冲队列、变量、数组、缓冲区等。 诸进程间应采取互斥方式，实现对这种资源的共享。每个进程中访问临界资源的那段代码称为临界区.同步机制应遵循的原则：1、空闲让进2、忙则等待3、有限等待4、让权等待 信号量的主要应用：1、利用信号量实现进程互斥2、利用信号量实现前驱关系3、管程机制：进程的同步工具2.5 进程通信：进程通信的类型 1、共享存储器系统： 基于共享数据结构的通信方式 寄语共享存储区的通信方式2、消息传递系统：应用最为广泛3、管道通信2.6 线程的基本概念，P73线程与进程在几方面的比较，P75线程间的同步和通信习题P81 3、4、7 第三章 处理

9、机调度与死锁3.1处理机调度的层次3.1.1 高级调度1 高级调度：又称为作业调度或长程调度，其主要功能是根据某种算法，把外存上处于后备队列中的那些作业调入内存，也就是说，它的调度对象是作业。2 作业：是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。3 作业步：在作业运行期间，每个作业都必须经过若干个相对独立又相互关联的顺序加工步骤才能得到结果，我们把其中的每一个加工步骤成为一个作业步。4 作业流：若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在

10、操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。3.1.2 低级调度1. 通常把低级调度称为进程调度或短程调度，它所调度的对象是进程。进程调度是最基本的一种调度，再多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。2. 功能：（1） 保存处理机的现场信息（2） 按照某种算法选取进程（3） 把处理器分配给进程3. 进程调度三个基本机制（1） 排队器。为了提高进程调度的效率，应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列，以便调度程序能最快的找到它。（2） 分派器（分派程序）。分派器把由进程调度程序所选定的进程，从就绪队列中取出该进程，然后进行上下文切换，将处理

11、机分配给它。（3） 上下文切换机制。4. 进程调度方式（1） 非抢占方式：一旦处理机分配给某进程后，不管运行多长时间，都不会因时钟中断等原因而抢占正在运行进程的处理机，也不允许其他进程抢占已分配给他的处理机。（2） 抢占方式：优先权原则、短作业优先原则、时间片原则。3.1.3 中级调度1. 中级调度：又称中程调度。引入的主要目的是为了提高内存利用率和系统吞吐量。中级调度实际上就是存储器管理中的对换功能。3.3 调度算法3.3.1先来先服务和短作业优先调度算法1. 先来先服务FCFS2. 短作业优先调度算法SJ（P）F3.3.2 高优先权优先调度1. 优先权调度算法类型：非抢占式优先权算法、抢占

12、式优先权调度算法。2. 优先权的类型：静态优先权（进程类型、进程对资源的需求、用户要求）、动态优先权3. 高响应比优先调度算法3.3.3基于时间片的轮转调度算法1. 时间片轮转法2. 多级反馈队列调度算法3. 多级反馈队列调度算法的性能（1） 终端型作业用户。系统只要能使这些作业在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。（2） 短批处理作业用户。可以满意（3） 长批处理作业用户。用户不必担心其作业长期得不到处理。3.4实时调度3.4.1实时调度基本条件1. 提供必要的信息:就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级。2. 系统处理能力强3. 采用抢占

13、式调度机制4. 具有快速切换机制：对外部中断的快速响应能力、快速的任务分派能力。3.4.2实时调度算法的分类1. 非抢占式调度算法：非抢占式轮转调度算法、非抢占式优先调度算法。2. 抢占式调度算法：基于时钟中断的抢占式优先权调度算法、立即抢占的优先权调度算法。3.4.3常用的几种实时调度算法1. 最早截止时间优先即EDF（earliest deadline first）算法：非抢占式调度算法用于非周期实时任务、抢占式调度方式用于周期实时任务2. 最低松弛度优先LLF（least laxity first）算法3.5产生死锁的原因和必要条件1. 死锁：是指多个进程在运行过程中因争夺系统资源而造成

14、的一种僵局，当进程处于这种僵持状态时，若无外力作用，他们都将无法再向前推进。3.5.1产生死锁的原因（竞争资源、进程间推进顺序非法）1. 竞争资源引起进程死锁（1） 可剥夺和非剥夺性资源（2） 竞争非剥夺性资源（3） 竞争临时性资源2. 进程推进顺序不当引起死锁3.5.2产生死锁的必要条件1. 互斥条件：指进程对所分配到的资源进行排他性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其他进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。2. 请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源有已被其他进程占有，此时请求进程阻塞，但又对自己已获得

15、的其他资源保持不放。3. 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。4. 环路等待条件： 3.5.3处理死锁的基本方法（1） 预防死锁。较易实现，但会导致系统资源利用率和系统吞吐量降低。（2） 避免死锁。只需事先施加较弱的限制条件，便可获得较高的资源利用率和系统吞吐量。（3） 检测死锁。（4） 解除死锁。与检测死锁相配套的一种措施。3.6预防死锁的方法3.6.1预防死锁1. 摒弃“请求和保持”条件2. 摒弃“不剥夺”条件3. 摒弃“环路等待”条件4. 环路等待条件严重问题：（1） 为系统中各类资源所分配的序号必须相对稳定，这就限制了新类型设备的增加。

16、（2） 尽管在为资源的类型分配序号时，已经考虑到大多数作业在实际使用这些资源时的顺序，但也经常会发生这种情况：即作业（进程）使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。（3） 为方便用户，系统对用户在编程时所施加的限制条件应尽量少。然而这种按规定次序申请的方法，必然会限制用户简单、自主的编程。3.6.2系统安全状态1. 安全状态：是指系统能按某种进程顺序，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。2. 银行家算法之例：假定系统中有五个进程P0, P1, P2, P3, P4

17、和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-15 所示。图 3-15 T0时刻的资源分配表（1） T0时刻的安全性： 图 3-16 T0时刻的安全序列（2） P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：a) Request1(1, 0, 2)Need1(1, 2, 2)b) Request1(1, 0, 2)Available1(3, 3, 2)c) 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图 3-15 中的圆括号所示。d

18、) 再利用安全性算法检查此时系统是否安全。图 3-17 P1申请资源时的安全性检查 （3） P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：a) Request4(3, 3, 0)Need4(4, 3, 1);b) Request4(3, 3, 0) Available(2, 3, 0)，让P4等待。（4） P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查：a) Request0(0, 2, 0)Need0(7, 4, 3);b) Request0(0, 2, 0)Available(2, 3, 0);c) 系统暂时先

19、假定可为P0分配资源，并修改有关数据，如图 3-18 所示。图 3-18 为P0分配资源后的有关资源数据（5） 进行安全性检查：可用资源Available（2,1,0）已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。第四章 存储器管理4.3 连续分配方式1. 单一连续分配2. 固定分区分配3. 动态分区分配4. 伙伴系统5. 哈希算法6. 可重定位分区分配7. 对换4.3.3 动态分区分配1. 首次适应算法2. 循环首次适应算法3. 最佳适应算法4. 最坏适应算法5. 快速适应算法内存分配流程4.4 基本分页存储器管理方式1. 分页和分段的概念：分段是信息的逻辑单位由原程序

20、的逻辑结构及含义所决定，是用户可见的，段长由用户根据需要来确定，段起始地址可从任何主存地址开始。在分段方式中，源程序经链接装配后仍保持二维结构，引入目的是满足用户模块化程序设计的需要。 分页是信息的物理单位与源程序的逻辑结构无关，是用户不可见的，页长由系统确定，页面只能从页大小的整数倍地址开始。在分页方式中，源程序经链接装配后变成一维结构，引入目的是实现离散分配并提高主存利用率。2. 区别和联系：（1） 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头， 提高内存的利用率。或者说， 分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信

21、息。 分段的目的是为了能更好地满足用户的需要。（2） 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定， 决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。（3） 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址； 而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名， 又需给出段内地址。 4.4.3 两级和多级页表两级页表结构图 4-15 具有两级页表的地址变换机构 4.6 虚拟存储器的基本概念4.6.1引入

22、1. 定义：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和决定，其运行速度接近于内存速度，而每位的成本却又接近与外存。4.6.2 实现方法1. 分页请求系统1) 硬件支持：a) 请求分页的页表机制，他是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；b) 缺页中断机构，即每当用户程序要访问的页面尚未调入内存时，便产生一缺页中断，以请求OS将所缺的页调入内存；c) 地址变换机构，它同样是在纯分页地址变换机构的基础上发展形成的。2) 实现请求分页的软件：这里包括有用于实现请求调页的软件和实现页面置换的软件。它们在硬件

23、的支持下，将程序正在运行时所需的页面（尚未在内存中的）调入内存，再将内存中暂时不用的页面从内存中置换到磁盘上。2. 请求分段系统：1) 请求分段的段表机制2) 缺段中断机构3) 地址变换机构4.6.3 虚拟存储器的特征1. 多次性：是指一个作业被分成多次调入内存运行，亦即在作业运行时没有必要将其余全部装入，只需将当前要运行的那部分程序和数据装入内存即可；以后每当要运到尚未调入的那部分程序时，再将它调入。多次性是虚拟存储器最重要的特征，任何其他的存储器管理方式都不具有这一特征。因此，我们以为可以认为虚拟存储器是具有多次性特征的存储器系统。2. 对换性：是指允许在作业的运行过程中进行换进、换出，亦

24、即，在进程运行期间，允许将那些暂不使用的程序和数据，从内存调至外存的对换区（换出），待以后需要时再将他们从外存调至内存（换进），甚至还允许将暂时不运行的进程调至外存，待他们重又具备运行条件时再调入内存。换进和换出能有效地提高内存利用率。3. 虚拟性：是指能够从逻辑上扩充内存容量，是用户所看到的内存容量远大于实际内存容量。这是虚拟存储器所表现出来的最重要的特征，也是实现虚拟存储器的最重要目标。4.8页面置换算法4.8.1 最佳置换算法和先进先出置换算法1. 最佳置换算法OPT假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2

25、，0，1，7，0，1 进程运行时， 先将7，0，1三个页面装入内存。 以后， 当进程要访问页面2时， 将会产生缺页中断。此时OS根据最佳置换算法， 将选择页面7予以淘汰。4这是因为页面0将作为第5个被访问的页面，页面1是第14个被访问的页面，而页面7则要在第18此页面访问时才需调入。下次访问页面0时，因它已在内存而不必产生缺页中断。当进程访问页面3时，又将引起页面1被淘汰；因为，它在现有的1,2,0三个页面中，将是以后最晚才被访问的。 图 4-25 利用最佳页面置换算法时的置换图4.8.2 最近最久未使用置换算法 LRU最近最久未使用的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由

26、于无法预测个页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当需淘汰一个页面时，选在现有页面中其t值最大的，及最近最久未使用的页面予以淘汰。第五章 设备管理5.2 I/O控制方式5.2.1 程序I/O方式又称忙等待方式，即在处理机向控制器发出一条I/O指令启动输入设备输入数据时，要同时把状态寄存器中的忙/闲标志busy置为1，然后便不断的循环测试，直至busy=0。在程序I/O方式中，由于CPU的高速性和I/O设备的低速性，只是CPU的绝大

27、部分时间都处于等待I/O设备完成数据I/O的循环测试中，造成对CPU的极大浪费。在该方式中，CPU之所以要不断测试I/O设备的状态，就是因为在CPU中无中断机构，使I/O设备无法向CPU报告它已完成了一个字符的输入操作。5.2.2 中断驱动I/O控制方式5.2.3 直接存储器访问（DMA）I/O控制方式1. 特点：（1） 数据传输的基本单位是数据块，即在CPU和I/O设备之间，每次传送至少一个数据块；（2） 所传送的数据是从设备直接送入内存的，或者相反；（3） 仅在传送一个或多个数据块的开始和结束时，才需要CPU干预，整块数据的传送师在控制器的控制下完成的。2. 组成：（1） 命令/状态寄存器（CR）；（2） 内存地址寄存器（MAR）；（3） 数据寄存器（DR）；（4） 数据计数器（DC）。3. 工作过程：5.2.4 I/O通道控制方式1. 进一步减少CPU的干预，即把对一个数据块的读或写为单位的干预减少为对一组数据块的读或写及有关的控制和管理为单位的干预。同时又可实现CPU、通道和I/O设备三者的并行操作，提高整个系统资源利用率。2. 通道指令：操作码、内存地址、计数、通道程序结束位P、记录结束标志R。5.4 I/O软件5.4.1 I/O软件的设计目标和原则1. 与具体设备无关2. 统一命名3. 对错误的处理4. 缓冲技术