操作系统复习资料

1、操作系统2012年期末考试复习资料整理第一章 引论一、操作系统概念1、计算机系统包括硬件和软件。2、硬件：中央处理器（运算器、控制器），存储器，输入设备，输出设备。3、软件：又称软设备，是程序和数据的集合。4、软件的分类：系统软件，应用软件，工具软件。5、操作系统是计算机系统中的i各系统软件，它统一管理计算机的软、硬件资源和控制程序的执行。二、操作系统的形成与发展1、操作系统的发展过程：（1）手工操作阶段：产生人机矛盾；（2）早期批处理系统：联机批处理系统（操作员），脱机批处理系统（卫星机）；（3）执行系统：通道和中断技术的引入；（4）多道批处理系统：单道批处理程序，多道批处理程序。单道：自动

2、性，顺序性，单道性；多道：多道，宏观并行，微观串行。多道提高了cpu、主存和i/o设备的利用率，增加了系统的吞吐量；（5）分时系统：一台计算机多个终端设备，采用分时技术完成用户任务。多道批处理系统和分时系统的出现标志操作系统初步形成。（一）分时系统的类型：i、单道分时系统：主存只能驻留一道作业，其余道在辅存上。导致频繁i/o，开销大；ii、前后台分时系统；iii、多道分时系统。（二）分时系统的特征：同时性，独立性，及时性，交互性；（6）实时系统；（7）通用操作系统：同时兼具多道批处理、分时、实时处理的功能；（8）微机操作系统：单用户单任务、单用户多任务、多用户多任务；（9）网络操作系统：通过通

3、信设施将物理上分散的，具有自治功能的多个计算机系统互联起来的，实现信息交换、资源共享、可互操作和协调处理的系统；（10）分布式操作系统：若干个能够独立工作的计算机（自治性）的集合，体现良好地多级合作和健壮性；（11）嵌入式操作系统：运行在嵌入式环境中，对整个系统及所有资源进行统一协调、处理、指挥控制的系统软件。三、操作系统的分类1、操作系统的基本类型：（1）批处理操作系统；（2）分时操作系统；（3）实时操作系统；（4）微机操作系统；（5）网络操作系统；（6）分布式操作系统；（7）嵌入式操作系统。四、操作系统的功能1、处理器管理：进程的控制和管理，进程的同步/互斥，进程通信，进程死锁，线程；2、

4、作业管理：作业输入输出，作业的调度和控制；3、存储管理：主存的分配和回收，地址转换，存储保护，主存共享；4、设备管理：i/o设备管理，缓冲区管理，设备的分配和回收，虚拟设备；5、文件管理：逻辑/物理组织，存取和使用，目录管理，共享和保护，存储空间管理。五、操作系统的特征和作用1、操作系统的特征：并发，共享（互斥共享、同时访问），虚拟，异步性；2、操作系统的作用：（1）作为用户与计算机硬件系统之间的接口；（2）作为计算机系统资源的管理者；（3）作为扩充机器。第二章 处理器管理一、程序的顺序执行和并发执行1、程序：指令的有序集合，是静态的。 进程：可并发执行的程序在一个数据集上的一次执行过程（动态

5、的），它是系统进行资源分配的基本单位。线程：进程中的一个实体，可独立参与调度的基本单位，但仅分配到极少量的资源。管程：关于共享资源的数据及在其上的操作的一组过程或共享数据结构及其规定的所有操作。2、顺序执行：依次执行程序段（顺序性、封闭性、可再现性）；3、并发执行：一组逻辑上相互独立的程序或程序段在执行过程中其执行时间在客观上重叠（间断性、失去封闭性、不可再现性）。二、进程的概念1、进程：见上。2、进程的基本状态：（1）就绪进程：已分配到除处理器外的全部资源的进程。一组就绪进程形成就绪队列；（2）执行进程：分配到处理器的进程。单处理器只能有一个执行进程，多处理器能有多个进程处于执行状态；（3）

6、等待进程：因某些事件（i/o请求、缓存申请等）而暂停执行的进程。一组等待进程形成就等待队列。3、进程的状态转换：就绪执行，执行等待，执行就绪，等待就绪。等待状态只有执行进程因某些事件而暂停执行，其他状态无法转换。进程调度中断执行就绪等待出现等待事件等待事件结束4、进程控制块（pcb）：操作系统用于记录和描述进程状态及有关信息的数据结构，是一个在多道程序环境下不能独立运行的程序成为一个能够独立运行的基本单位和一个能与其他进程并发执行的进程。由于pcb经常被访问，故应常驻主存。pcb包含的四类信息：（1）标识信息：进程标识符；（2）说明信息：进程状态、等待原因、程序和数据存放位置等；（3）现场信息

7、：进入等待状态前保护现场信息，多为各寄存器内容；（4）管理信息：进程优先数、队列指针。5、进程队列：多道程序设计的系统中，在单处理器情况下每次只能一个进程执行，其他进程均处于就绪或等待状态。为了便于管理，将处于相同状态的进程链接在一起，称为“进程队列”。队列管理方式：（1）链接方式：单向链接，双向链接；（2）索引方式：索引表中记录的是某个进程在pcb表中的地址（图见书p25）。三、进程控制1、进程控制：系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程各状态之间的转换，从而达到多进程、高效率的并发执行和协调，实现资源共享的目的。2、原语：即特定功能的程序段。其特点是在执行期间不允许中

8、断，是一个不可分割的单位。原语采用顺序执行而不是并发。原语包括：（1）进程创建：创建一个指定标识符的进程。创建新进程的进程为父进程，其新进程为子进程；（2）进程撤销：撤销一个进程。父进程被撤销时子进程也需一起撤销；（3）进程阻塞：将处于执行状态的进程中断为等待状态，并把cpu现场送至该进程的现场保护区。（4）进程唤醒：“发现者”进程用唤醒原语使等待进程重回执行状态。四、进程调度1、进程调度：又称处理器调度程序，按照某种调度算法从就绪队列里选择一个进程，让它占用处理器。2、进程调度的功能：（1）记录系统中所有进程的执行情况；（2）选择占有处理器的进程；（3）把处理器分配各进程，即进行进程上下文切

9、换；（4）收回处理器。五、线程1、定义：见上。2、特征：（1）线程由进程创建；（2）可独立调度；（3）仅拥有少量资源，如寄存器等；（4）可并发执行；（5）分为内核级线程、用户级线程和混合式线程。（6）进程被撤销时，相应其线程也将被撤销。六、进程互斥1、并发进程：操作不当会引起与实践有关的错误。2、临界区：并发进程中的共享段。3、pv操作实现进程的互斥。4、哲学家吃通心面问题。七、进程同步1、异步环境：相互合作的一组并发进程，各自独立但密切合作。2、共享缓冲器：进程之间相互合作的通道。3、pv操作实现进程的同步。4、实际问题：（1）生产者消费者问题：i、先申请同步信号量，再申请互斥信号量。ii、

10、消费者依赖于生产者，属于同步关系；缓冲区的使用属于互斥关系。（2）读者写者问题i、读者人数计数器为互斥资源，存在一互斥信号量；ii、写操作为一互斥信号量；iii、该问题中无同步信号量（读者无需依赖写者的修改内容）。（3）时间同步问题i、各进程能否执行均为一互斥信号量；ii、多条件下应多次申请信号量。八、管程1、定义：见上。九、进程通信1、直接通信2、间接通信十、死锁1、死锁：多个进程因竞争资源而造成的一种僵局，若无外力则无法再推进。2、死锁的原因：1）竞争资源，2）进程推进顺序非法。m个资源被n个进程共享，当每个进程都要求k个资源，则在mn*k时绝对不会发生死锁，而mn*k时分配不当即有可能发

11、生死锁。3、死锁的必要条件：（1）互斥条件（2）占有且等待条件（3）不剥夺条件（4）循环等待条件4、解决死锁的方法：预防、避免、检测、解除。5、银行家算法：进程首次申请资源时测试其最大需求量，如果可以满足则分配，否则推迟；当执行过程中申请资源，则测试剩余资源与已占资源之和能否满足进程的最大需求量，如果满足则分配，否则推迟。第三章 作业管理一、作业管理概述1、作业：用户在一次解题过程中要求计算机所做工作的集合。计算机运行用户作业一般经历四步：编辑、编译、链接装配、运行。2、作业步：每个作业均经历若干个“加工”步骤，我们把每个加工步骤称为一个作业步。3、作业控制方式：指用户根据操作系统提供的手段来

12、说明作业加工步骤的方式。分为批处理控制方式和交互式控制方式。4、批处理控制方式：又称脱机处理。将作业的源程序和初始数据一同提交给计算机，不必再进行干预，操作系统按要求自动的控制作业执行。5、交互式控制方式：又称联机处理。通过用户逐条输入命令控制作业的执行情况。二、批处理作业的管理1、批处理作业管理包括：（1）作业输入：把作业装入输入井，按照先后顺序形成后备作业队列；（2）作业调度：按照某种策略，选择后备队列中的若干作业装入主存运行；（3）作业控制：在操作系统的控制下，用户组织和控制其作业进入处理器运行的过程。2、批处理作业输入（1）作业控制语言（jcl）：由若干作业控制语言组成的集合，提供提交

13、作业，控制作业/作业步，使用各种软硬件资源等。（2）作业控制块（jcb）：包括作业名、作业状态、类别、优先数、控制方式、资源需求量、进入系统时间、开始运行时间、运行时间、完成时间和所需主存地址和外设等信息。（3）作业表：所有作业控制块构成的集合。其存放于辅存固定区域，长度有限。作业控制块建立后将其链入作业表，以便于访问和管理，作业完成后撤销作业，即同时在作业表中删除该作业信息。3、批处理作业调度（1）作业调度程序及相应状态：完成状态运行状态后备状态提交状态（2）作业调度的性能指标：cpu利用率、吞吐能力、周转时间、平均周转时间。平均带权周转时间（周转时间/运行时间）。（3）批处理作业调度阶段：

14、i、高级调度（作业调度）：作业进入输入井，进入作业后备队列。其执行频率较低；ii、低级调度（进程调度）：作业从后备队列进入主存，进入就绪进程队列。其执行频率较高；iii、中级调度（平均负载调度）：将暂不运行的进程调出主存（挂起）。其决定主存中所能容纳的进程个数。（4）调度算法：i、先来先服务算法（fcfs）；ii、短作业优先算法（sjf）；iii、最高响应比优先算法（hrrf）：响应比=（等待时间+运行时间）/运行时间；iv、优先数调度算法；v、分类调度算法。4、批处理作业控制：1）作业调度选中作业，2）查找该作业说明书，3）取出作业首个作业步并解释执行，4）若正常则一步步执行下去，反之分析错

15、误性质并处理，若能继续则转向其他作业步，5）作业完成，收回资源并撤销作业。三、交互式作业的管理1、交互式作业的特点：交互性（人机对话）。2、交互式作业控制方式：操作控制命令，菜单方式，视窗方式。3、终端作业管理：一般采用时间片轮转方式执行作业。主要分为终端连接、用户注册、作业控制。用户推出四个阶段。四、操作系统与用户的接口1、命令接口（作业级接口）：操作系统提供给用户对作业组织和运行进行全过程控制的命令接口。2、程序接口：由编程人员使用的系统调用命令组成。3、图形接口。第四章 存储管理一、存储管理概述1、存储器层次：寄存器高速缓存主存储器（以上均为可执行存储器）磁盘缓存（并非实际存在，其依托固

16、定磁盘）磁盘可移动存储介质2、存储管理功能：主存分配/去配，地址转换，主存的共享和保护，主存扩充；二、程序的装入与链接1、物理地址：主存的存储地址以字节为单位进行编址，每个字节单元都有其对应的物理地址，范围为0n-1；2、逻辑地址：用户所编程序中的地址，一般采用从0开始编址的相对地址。3、程序装入主存（1）绝对装入方式：编译时就确定了物理地址；（2）静态重定位装入方式：装入时一次性将地址转换为物理地址；（3）动态重定位装入方式：运行过程中在硬件配合下进行实时地址转换。该方式下能够实现“程序浮动”。4、程序的链接（1）静态链接：编译时设置了始址为0并相对始址链接；（2）装入时动态链接：边装入边链

17、接，可实现非连续地址的装入；（3）运行时动态链接：运行过程中链接各模块，可实现虚拟主存下的装入。三、连续存储管理1、单一连续存储：主存同一时间只能存放一个作业；2、固定分区存储：将主存分为若干区域，某一作业只能存放在一个区域内；3、可变分区存储：（1）需建立空闲区的数据结构分区表或分区链；（2）可变分区分配算法：i、最先适应分配算法；ii、最优适应分配算法；iii、最坏适应分配算法；（3）可变分区回收：存在“上邻”、“下邻”、“无邻”和“上下均邻”分区的情况；（4）移动技术：合并空闲分区，但需消耗大量时间和资源。4、覆盖和交换技术（1）覆盖技术：不将程序的所有数据和指令同时装入主存，而将程序划

18、为若干段，让不同时执行的程序段共享主存。可共享的主存区叫做覆盖区。以时间换取空间；（2）交换技术：将暂时不用的主存数据与辅存数据互换。促使了虚拟内存技术的发展。四、页式存储管理1、初始状态：将主存分为长度为l的若干块，将作业按长度l分为若干页。则逻辑地址分为：页号和页内地址。2、位示图记录主存块号是否空闲，并负责是否分配。3、建立页表实现作业页号到主存块号的地址映像。4、建立快表实现快速查找。五、段式存储管理1、初始状态：将作业分为逻辑上相对独立的若干段（长度不等），并编上段号。地址结构为段号+段内地址。调入主存时可将各段独立存入主存空间。2、建立段表记录作业各段的基址和长度。3、段式存储可以

19、较好地实现共享，但共享段不可置换出主存。六、段页式存储管理1、初始状态：作业分段存储，各段内在采取分页存储。逻辑地址为段号+页号+页内地址。七、虚拟存储管理1、虚拟存储存在离散性、多次性、对换性、虚拟性的特点，因此只有非连续存储才可实现虚拟存储。2、请求分页式存储（1）页表结构：页号物理块号状态位访问字段修改位辅存地址 访问字段记录访问次数，修改位为1是则需更新主存内容。（2）缺页中断时页面置换算法：i、最佳置换算法：选择最久不会被使用的页面淘汰；ii、先进先出置换算法：总是淘汰最先进入的页面。存在belady现象（分配的物理块增多，缺页中断次数反而增加，因为没有考虑程序执行的动态特征），产生

20、“颠簸”；iii、最近最少用置换算法：选择最近一段时间内最长时间未被访问的页面淘汰；iv、时钟置换算法：周期性记录页面访问次数；v、最近最不常用置换算法：为每一页设置一个计数器。（3）缺页中断率：存在临界值，当到达临界值后，即时增加较多物理块，进程缺页中断次数也不会明显减少。可通过设置工作集，动态分配物理块数量。3、请求分段式存储4、请求段页式存储第五章 设备管理一、设备管理概述1、设备分类（1）从属关系：系统设备、用户设备（2）工作特性：存储设备、i/o设备2、设备管理功能（1）外围设备分配与去配（2）外围设备启动（3）磁盘驱动调度（4）设备处理（5）虚拟设备二、i/o系统1、分类（1）按传

21、输速率：低速（鼠标、键盘），中速（打印机），高速（磁盘）；（2）按信息交换单位：块设备，传输速率高、可寻址，采用直接存储器访问（dma）（磁盘）；字符设备，传输速率低、不可寻址，采用中断驱动方式访问（打印机）；（3）按共享属性：独占型（打印机），共享型（磁盘），虚拟设备；2、设备控制器：介于cpu和外围设备之间，通过数据信号线、状态信号线和控制信号线，负责数据传输和控制。基本功能包括：1）接收和识别命令，2）数据交换，3）表示和报告设备的状态，4）地址识别，5）数据缓冲，6）差错控制。控制器与设备接口控制器与设备接口i/o逻辑寄存器地址线控制线数据线数据状态控制3、通道：又称i/o处理器。在c

22、pu与设备控制器之间增设的控制设备，对i/o操作进行组织、管理和处理，实现四层连接，三层控制。分为：字节多路通道（以字节为单位）、数组选择通道（以块为单位）、数组多路通道（满足多路程序设计）。设备设备设备通道通道内存cpu4、总线：通过时钟频率、带宽和传送速率等指标确定总线性能。5、i/o控制方式：（1）直接程序控制方式（询问方式、忙/等待方式）：cpui/o（读命令），i/ocpu（读状态，循环直至空闲），i/ocpu（读入字），cpu主存（写入主存）。适合低速设备；（2）中断驱动控制方式：cpui/o（读命令），i/ocpu（读状态，cpu做其他事，直至i/o发送状态请求中断），i/ocp

23、u（读入字），cpu主存（写入主存）。适合低速设备；（3）直接存储访问控制方式（dma）：cpudma（读命令），dmacpu（读状态，cpu做其他事，直至dma请求中断），dma主存（dma占用数周期总线控制权）。dma需设置四类寄存器：状态寄存器（cr），贮存地址寄存器（mar），数据寄存器（dr），数据计数器（dc）。适合少量高速设备；（4）通道控制方式：cpu通道（采用通道命令），通道主存（若设备空闲，则进行输入输出），通道cpu（状态报告）。适合大量高/低速设备；三、缓冲技术1、缓冲技术引入的原因：为了缓解各类设备间速度不匹配的矛盾，减少cpu中断频率，放宽中断响应时间，提高cpu和

24、i/o设备间的并行性。2、分类：（1）单缓冲；（2）双缓冲：交替使用；（3）多缓冲：循环使用；（4）缓冲池：形成空闲队列、输入队列和输出队列。四、独占设备的分配1、设备编号：（1）物理号：系统编制，不能更改；（2）逻辑号：用户规定，可以更改，使用时需进行逻辑号到物理号的映射。2、设备独立性：用户编制程序时使用的设备与世嘉使用的设备无关，依靠设备驱动程序进行管理。3、独占设备分配（1）静态分配：一次性将该作业所需的全部设备、控制器和通道全部分配给作业；（2）动态分配：根据作业执行过程中的需要进行分配，可能造成死锁。4、设备管理信息：（1）设备控制表（dct）：设备状态的记录，是否空闲，是否良好，

25、指针等；（2）控制器控制表（coct）：记录本控制器的使用状态以及通道连接情况等；（3）通道控制表（chct）：通道状态；（4）系统设备表（sdt）：登记所有设备信息；（5）逻辑设备表（lut）：逻辑设备与物理设备的映射。5、设别申请过程：根据设备名查找sdt，获取其dct，通过dct获取coct和chct中各级状态，最后根据dct、coct、chct中各状态决定是否分配。各级若空闲，则分配，否则挂起。五、磁盘管理1、温氏硬盘：每个扇区包括定界符、数据区和crc冗余校验。2、扇区：将一个磁道分为若干扇区。3、磁头：一个盘面对应一个磁头。4、柱面：同一圆柱面的磁道集合。5、磁盘存储顺序：优先同一

26、柱面，其次同一磁头，最后为不同扇区。6、i/o操作主要花费的时间：寻找时间（磁道至指定柱面），延迟时间（指定扇区旋转至磁头下），传送时间（磁头读写时间）。7、移臂调度：（1）先来先服务调度算法；（2）最短寻找时间优先调度算法：选择与当前磁头所在磁道最近、寻道时间最短的请求进行响应；（3）单向扫描调度算法（循环扫描调度算法）：从0柱面开始向最里柱面一次扫描并响应，可能存在空扫；（4）双向扫描调度算法：从0柱面到最里柱面后返回至0柱面并一次响应请求；（5）电梯调度算法：遵循“同向优先”和“最近优先”原则，响应移臂请求。8、旋转调度：选择延迟时间最短的请求访问者执行调度，即优先选择扇区号最近的，当多

27、个磁道同一扇区时，则任意选择。为了减小延迟时间，扇区编号时可将同一磁道的相邻数据错开分布（内容错开后，由于读取时会有延时，可以避免错过相邻数据而多次旋转），而不同磁道的扇区编号错开命名（避免同一时刻多个磁道同一扇区请求）。9、提高i/o速度的方法：设置高速缓冲，进行“提前读”、“延迟写”、“虚拟盘”（用主存仿真磁盘）。六、设备处理1、设备驱动程序：i/o设备和设备控制器之间的通信和转换程序。2、设备管理过程：（1）预备设置：将逻辑地址转化为物理地址，检验i/o请求合法性，检查设备状态，传送必要参数，设置工作方式；（2）启动i/o设备（3）设备中断处理：i、正常结束；ii、异常结束：现场保护并进

28、入相应的中断处理程序。七、虚拟设备1、虚拟设备的目的：提高独占性设备的利用效率。2、脱机外围设备：独立于主机，不在主机直接控制下的操作（需人工操作）；3、连接外围设备：spooling（假脱机操作）。4、spooling：由预输入程序、实现i/o的井管理程序、缓输出程序三部分组成。（1）预输入程序：把一批作业组织在一起形成作业流，并形成一张输入表，进行作业管理和调度，此时作业状态分为：i、输入状态：正在从输入设备预输入；ii、收容状态：进入作业队列但未被执行；iii、执行状态：作业已选中并正在从输入井读取信息（或向输出井写信息）；iv、完成状态：作业撤离，结果等待缓输出；（2）井管理程序：负责

29、管理输入输出；（3）缓输出程序：负责查看输出井中是否有等待输出的信息。第六章 文件管理一、文件管理概述1、文件：一组在逻辑上有完整意义的相关信息的集合。每个文件都有其文件名。2、文件属性：（1）基本属性：文件名、所有者、授权者、文件长度；（2）类型属性：普通、目录、系统、隐藏、设备等；（3）保护属性：可读、可写、可执行、可删除、可更新等；（4）管理属性：创建时间、修改时间、存取时间等；（5）控制信息：逻辑记录长、文件最大长、当前长等。3、文件系统：操作系统负责存取和管理文件的软件。4、文件的分类：（1）按用途：系统、库文、用户；（2）按信息流向：输入、输出、输入输出；（3）按保护级别：只读、读

30、写、可执行；（4）按存放时限：临时、永久、档案；（5）按数据形式：源、目标、可执行；（6）按文件性质：普通、目录、特殊。5、文件系统功能：目录管理（实现“按名存取”）、文件组织（逻辑文件、物理文件）、存储空间管理、文件操作、文件共享、保护和保密。6、文件系统的层次结构：（1）描述层：负责描述系统中所有文件和文件存储介质的使用状况；（2）管理层：设备驱动（i/o管理）、物理i/o（数据交换）、文件存储组织（物理存储管理）、逻辑i/o（逻辑操作管理）；（3）接口层：为用户使用文件系统提供相应接口，包括命令接口（用户与文件交互）和程序接口（系统调用进程）。二、文件的组织结构和存取方式1、文件的逻辑结

31、构（用户角度）：按信息的使用和处理方式来组织文件，遵循便于修改，检索效率高，减少文件所占存储空间和便于用户操作的原则，分为：（1）无结构文件：流式文件，基本信息单位为字节或字，如磁带；（2）有结构文件：记录式文件，由若干个逻辑记录组成，具有独立意义的基本信息单位，根据记录长度可分定长和变长，如磁盘。对能唯一标识某个逻辑记录的数据项称为“主键”，根据用户需要分为：顺序文件（定长顺序排列）、索引文件（变长需要索引表）、索引顺序文件。2、文件存储介质的物理单位为“卷”，分为单文件卷（一卷一文件）、多文件卷（一卷多文件）、多卷文件（一文件多卷）、多卷多文件（多文件多卷）。3、存储和信息交换的基本单位为

32、“块”，两个相邻物理块之间必须预留一定的间隙空间（机械操作中确定物理块位置）。4、文件存取方式：顺序、随机、按键。5、文件的物理结构（文件系统角度）：文件如何存放在存储介质上，即文件在辅存上的存储组织形式（与存储介质性能有关）。分为：（1）顺序结构：连续按序存取，利用率低且不易查找；（2）链式结构：实现分连续存储，但仍为顺序存取；（3）索引结构：可实现非连续存取，需建立索引表；（4）直接文件：按键存取，采用哈希转换技术解决地址冲突问题。6、记录的成组：将若干逻辑记录存入一个物理块的过程，提供存储效率。7、记录的分解：吧一组逻辑记录分离的过程。三、目录管理1、目录管理实现：按名存取，提供检索目录效率，实现文件共享和允许文件重名。2、文件控制块：基本信息、结构信息、管理信息、存取控制信息。3、文件目录结构：一级目录、二级目录、多级目录、无环图目录。四、辅存空间的管理1、空闲块表法（1）建立一张空闲块表，记录一组连续空闲块的首块号和块数等信息；（2）空闲块表法属于连续分配方式，适合采用顺序结构的文件；（3）空闲块表法可以减少