基于《计算机操作系统》(第四版)总结：OS引论、进程描述与控制、处理机调度与死锁、存储器管理、虚拟存储器、输入输出系统、文件系统

一、操作系统引论

1、目标：方便性、有效性、可扩充性、开放性

2、作用：

　　1、作为用户与计算机硬件系统之间的接口

　　2、作为计算机系统资源的管理者

　　3、实现对计算机资源的抽象

3、发展过程：

　　1、人工操作方式：用户独占全机，CPU等待人工操作--带（卡）装卸

　　2、脱机输入/输出方式：事先将装有用户程序和数据的纸带装入纸带输入机，外围机控制，把纸带内容输入到磁带上（类似于磁盘），CPU需要时，从磁带高速调入内存。反之类同。

　　　　优点：减少了CPU的空闲时间、提高了I/O速度

　　3、单道批处理：首先监督程序将磁带第一个作业装入内存，运行控制权在该作业，处理完改作业后，控制权回到监督程序，然后进行重复过程，系统自动对作业成批处理。（内存始终只保持一道作业---单道批处理）

　　　　缺点：内存浪费，不能充分利用系统资源

　　4、多道批处理：所提交的作业先存入外存，排成“后备队列”，再由作业调度程序按算法从队列调若干作业入内存。

　　　　优缺点：资源利用率高、系统吞吐量大、平均周转时间长、无交互能力

　　5、分时系统：作业直接进入内存，采用轮转运行方式，系统配置一个多路卡（实现分时多路复用），及时接收用户终端命令（数据）。

　　　　特征：多路性、独立性、及时性、交互性

　　6、实时系统：系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务的协调一致的运行。

　　　　特征：多路性（周期性信息采集，多个对象或执行机构进行控制）、独立性、及时性、交互性、可靠性（多级容错措施）

4、基本特征：

　　1、并发：引入进程，并行并发，系统程序独立并发执行，提高资源利用率，增加系统吞吐量。

　　2、共享：

　　　　①互斥共享，一段时间内只允许一个进程访问资源（临界资源）。

　　　　②同时共享，允许一段时间内多进程“同时”访问。

　　3、虚拟：提高通信信道的利用率--“虚拟”技术，通过“空分复用”或“时分复用”，将一条物理信道（实）变为若干条逻辑信道（虚）。

　　　　空分复用：利用存储器的空闲空间分区域存放和运行其他的多道程序

　　　　时分复用：利用处理机的空闲时间运行其他程序

　　4、异步：进程以不可预知的速度向前推进。

5、主要功能：

　　1、处理机管理功能：

　　　　①进程控制：创建和撤销进程，分配资源、资源回收，控制进程运行过程中的状态转换。

　　　　②进程同步：多进程运行进行协调--进程互斥（临界资源上锁）、进程同步。

　　　　③进程通信：实现相互合作之间的进程的信息交换。

　　　　④调度：作业调度，进程调度。

　　2、存储器管理功能：为多道程序的运行提供良好的环境，提高存储器的利用率，方便用户使用，并能从逻辑上扩充内存。

　　　　①内存分配：静态分配、动态分配。

　　　　②内存保护：各在其内存空间内运行（设两界限寄存器），互不干扰。

　　　　③地址映射：地址空间中的逻辑地址转换为内存空间中与之对应的物理地址。

　　　　④内存扩充：借助于虚拟存储技术，逻辑上扩充内存容量。

　　3、设备管理功能：完成用户进程提出的I/O请求，为其分配所需I/O设备，完成指定I/O操作；提高CPU和I/O设备的利用率，提高I/O速度，方便用户使用I/O设备。

　　　　①缓冲管理

　　　　②设备分配

　　　　③设备处理：设备驱动程序，用于实现CPU和设备控制器之间的通信。

　　4、文件管理功能：对用户文件和系统文件进行管理以方便用户使用，并保证文件的安全性。

　　　　①文件存储空间的管理：为文件分配合理外存空间，文件存储空间的使用情况。

　　　　②目录管理：为每个文件建立一个目录项。

　　　　③文件的读/写管理和保护

　　5、操作系统与用户之间的接口：用户接口，程序接口

6、微内核操作系统：

　　①内核足够小

　　②基于客户/服务器

　　③“机制与策略分离”原理

　　④面向对象技术

二、进程的描述与控制

1、前趋图：用于描述程序执行先后顺序 P1->P2，是指一个有向无循环图。

　　程序的顺序执行：按照某种先后次序顺序执行，仅当前一程序执行完后，才运行后一段程序。

　　　　顺序性、封闭性、可在现性

　　　　输入操作I->计算操作C->打印操作P

　　程序的并发执行：间断性、失去封闭性、不可再现性

2、进程

　　1、定义：

　　　　程序的一次执行，顺序执行时所发生的活动，是具有独立功能的程序在一个数据集合上的运行过程，系统资源调配的独立单位。

　　2、实体：

　　　　即进程，由程序段、相关的数据段和PCB组成，所谓创建和撤销进程实际是对其中的PCB的创建和撤销。（PCB：进程控制块Process Control Block）

　　3、特征：

　　　　①动态性 ②并发性 ③独立性 ④异步性

3、进程的三种基本状态：就绪、执行、阻塞状态（阻塞原因：I/O请求、申请缓冲区失败等）

　　1、进程状态的转换：

　　2、进程的挂起suspend：进程处于静止状态，暂停执行（执行状态下挂起），暂不接受调度（就绪状态下挂起）。是基于系统和用户的需求。

　　3、进程的激活active：先将进程从外存调入内存，检查进程现行状态，静止-->活动

4、进程控制块PCB：

　　1、记录系统所需，用于描述进程的当前情况以及管理进程运行的全部信息，是操作系统中记录型数据结构。

　　2、作用：一个在多道程序环境下不能独立运行的程序成为一个能独立执行的基本单位，一个能与其他进程并发执行的进程。

　　3、三种组织方式：

　　　　①线性方式：将系统中所有的PCB都组织在一张线性表中，查表

　　　　②链接方式：把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列

　　　　③索引方式：根据所有进程状态的不同，建立索引表

5、并发进程间的相互制约关系：

　　①间接相互制约关系：进程间对类临界资源的间接相互制约关系，为保证进程有序运行，此类资源必须由系统实施统一分配（即用户使用前，应先提出申请）。

　　②直接相互制约关系：源于某些进程（隶属于同一应用程序）之间为完成同一项任务而相互合作（相互间唤醒激活--制约）。

6、临界资源：

　　　　一次仅允许一个进程使用的资源（如打印机、磁带机等），进程间互斥来实现对临界资源的共享。

　　临界区：每个进程中访问临界资源的那段代码，进程互斥地进入自己的临界区，对临界资源访问

　　　　①进程进入临界区前，对临界资源进行检查是否正被访问---进入区

　　　　②若未被访问，进入临界区对该资源访问，并设置“正被访问”的标志---临界区

　　　　③临界区后面代码，将临界区“正被访问”的标志恢复为“未被访问”的标志---退出区

　　　　④除进入区（entry）、临界区（critical）、退出区（exit）代码，其余代码---剩余区

7、同步机制应遵循的原则：

　　1、为实现进程互斥地进入自己的临界区

　　2、空闲让进、忙则等待、有限等待、让权等待

8、信号量机制：解决进程同步问题（进程同步工具）

　　①整型信号量：表示资源数目的整型量（S），仅原子操作wait（S）和signal（S）可访问，执行时不可中断。（分别被称为P、V操作）

　　②记录型信号量：在代表资源数目的整型变量value基础，增加一个进程链表指针list，用于链接所有等待进程。不存在“忙等”的进程同步机制。

　　③AND型信号量：将进程运行所需所有资源，一次性全部分配给进程，待进程使用完后再一起释放。

　　④信号量集：AND型信号量基础上，对进程所申请的所有资源以及每类资源不同的资源需求量，在一次P、V原语操作中完成申请或释放。

9、管程

　　1、管程机制：

　　　　①共享资源的数据结构

　　　　②对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成的一个操作系统的资源管理模块。

　　“一个管程定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。”

　　2、管程的组成：

　　　　①管程的名称

　　　　②局部于管程的共享数据结构说明

　　　　③对该数据结构进行操作的一组过程

　　　　④对局部于管程的共享数据设置初始值的语句

　　管程被请求和释放资源的进程所调用。

10、经典进程同步问题（使用信号量方法解决）

　　生产者-消费者问题

　　哲学家进餐问题

　　读者-写者问题

11、进程通信的类型：

　　①共享存储器系统：相互通信的进程“共享数据结构”或“共享存储区”。

　　②管道通信系统：“管道”（pipe）是指用于连接一个读进程和一个写进程以实现彼此间通信的一个共享文件。借花献佛-管道通信。

　　③消息传递系统：将通信上网数据封装在消息中，通过一组通信命令在进程间传递消息，完成进程间的数据交换。直接通信方式和间接（邮箱）通信方式。

　　④客户机-服务器系统：套接字、远程过程调用、远程方法调用。

12、线程：“轻级进程”，作为调度和分派的基本单位，是程序执行流的最小单位。

进程与线程间的异同：

　　①调度性：线程是作为调度和分派的基本单位，进程只作为资源拥有的基本单位。

　　②线程上下文切换比进程上下文切换快得多。

　　③并发性：进程间可并发执行，线程（无论在同一进程与否）间也可并发执行。

　　④拥有资源：进程拥有系统资源，线程仅有一点必不可少、保证独立运行的资源。多个线程可共享本进程所拥有的资源。

　　⑤独立性：同一进程中的不同线程之间的独立比不同进程之间的独立性低得多。

　　⑥系统消耗：进程的创建或撤销的系统消耗“明显大于”线程的创建或撤销的系统消耗。

三、处理机调度与死锁

1、处理机调度的层次：

　　①高级调度：（长程调度或作业调度），调度对象是作业，主要功能是根据算法决定将外存后备队列中的某些作业调入内存，创建进程、分配必要资源，并将入就绪队列。

　　②低级调度：（短程调度或进程调度），调度对象是进程，主要功能是根据算法决定内存就绪队列中的某个进程应获得处理机，并由分派程序给选中的进程分派处理机。

　　③中级调度：（内存调度），内存中暂不能运行的进程调至外存（挂起状态），待条件齐全且内存空闲，中级调度，就绪进程重回内存（就绪状态）入就绪队列。

2、处理机调度算法的目标：

　　①共同目标：资源利用率、公平性、平衡性、策略强制执行

　　②批处理系统的目标：平均周转时间、系统吞吐量高、处理机利用率高

　　③分时系统的目标：响应时间快、均衡性

　　④实时系统的目标：截止时间的保证、可预测性

3、作业：通常的程序+数据+作业说明书。

　　1、作业控制块：作业标识+用户名称+用户账号+作业类型+作业状态+调度信息+资源需求+资源使用情况+……。管理和调度作业。

　　2、作业运行的三个阶段（三种状态）：收容阶段（后备状态）、运行阶段（运行状态）、完成阶段（完成状态）。

4、作业调度算法：

　　①先来先服务（FCFS）：先后次序进行调度（作业调度、进程调度）。

　　②短作业优先（SJF）：作业（或进程）越短（估计运行时间短），优先级越高。

　　③高响应比优先级调度算法：既考虑作业的等待时间，有考虑作业的运行时间，既照顾短作业，又不致使长作业的等待时间过长，从而改善处理机调度的性能。

　　　　R p优先级=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间

5、进程调度机制：

　　①任务：保存处理机的现场信息、按某种算法选取进程、把处理机分配给进程

　　②基本部分：排队器、分派器、上下文切换器

　　③进程调度方式：非抢占方式、抢占方式

6、轮转调度算法原理：

　　根据FCFS，使用轮转法处理，让每一个就绪队列上的进程每次运行一个时间片（若就绪队列上有n个进程，每个进程每次大约获得1/n的处理机时间）。

　　时间的片的确定：略大于一次典型交互所需时间。

7、多级反馈队列调度算法：

　　①设置多个就绪队列：每个队列赋予不同的优先级、不同大小的执行时间片。

　　②每个队列都采用FCFS算法

　　③按队列优先级调度

8、最早截止时间优先EDF（earliest deadline first）调度算法：根据任务的截止时间确定优先级，截止时间愈早的优先级愈高，具有最早截止时间的任务排队列首，优先分配处理机。

　　最低松弛度优先LLF（least laxity first）调度算法：根据任务的紧急（松弛）程度，紧急程度愈高的优先级愈高，优先执行处理。

9、死锁

　　1、死锁的定义：如果一组进程中的‘每一个进程’都在等待仅由该组进程中的‘其它进程’才能引发的‘事件’，那么该组进程是死锁的（Deadlock）。

　　2、死锁的必要条件（缺一不可）：

　　　　①互斥条件：进程分配到的资源互斥性使用，资源只能被一个进程占用，其他请求该资源的进程只能等到被用完释放。

　　　　②请求和保持条件：进程已占有某资源，又提出新资源请求，而该资源被占，则进程请求被阻塞，已得资源保持。

　　　　③不可抢占条件：进程已得资源不可被抢占。

　　　　④循环等待条件：存在一个进程的资源循环链。

　　3、死锁的处理方法：

　　　　①预防死锁：设置限制条件，破坏死锁四个必要条件。

　　　　②避免死锁：在资源的动态分配过程中，去防止系统进入不安全状态。

　　　　③检测死锁：允许进程死锁，但检测机构检测死锁发生，措施解决。

　　　　④解除死锁：撤销某些进程，回收它们的资源分配给处于阻塞状态的进程，使其能继续运行。

10、预防死锁的方法：破坏死锁四个必要条件

　　互斥条件是非共享设备所必须的----主要破坏其他三条件

　　①破坏“请求和保持”条件：第一种协议，所有进程运行前申请过程所需的全部资源；第二种协议，允许一个进程获得初期所需资源便开始运行，过程中逐步释放分配给自己的且用毕的资源，再请求新的所需资源。

　　②破坏“不可抢占”条件：新的资源请求得不到满足时，释放已经保持的所有资源，待需之时再申请。

　　③破坏“循环等待”条件：对系统所有资源类型进行线性排序，并赋予不同的序号。

11、安全序列：（P1，P2，……，P n）

　　安全状态：系统能按某种进程推进顺序（P1，P2，……，P n）为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利的完成。

12、利用银行家算法避免死锁的方法

四、存储器管理

1、存储器的层次结构：

　　①CPU寄存器：寄存器

　　②主存（内存）：高速缓存、主存储器、磁盘缓存

　　③辅存：固定磁盘，可移动存储介质

　　可执行存储器：寄存器、主存（掉电信息丢失）---属于操作系统存储管理负责分配、回收，以及提供存储层次间数据移动的管理机制。

2、用户程序在系统中运行，先将其装入内存，在将其转变位一个可执行程序

　　①编译：由编译程序对用户源程序编译，形成若干个目标模块。

　　②链接：由链接程序将一组目标模块及其所需库函数链接，形成一个完整的装入模块。

　　③装入：由装入程序将装入模块装入内存。

　　1、程序的装入（地址的变换）

　　　　①绝对装入方式：（系统小，单道程序）编译时知道程序将驻留在内存的位置，将产生绝对地址（即物理地址）的目标代码。绝对装入程序按照已知地址将装入模块装入内存，不需对地址修改。

　　　　②可重定位装入方式：装入时，对目标程序中指令和数据的各地址重定位（虚拟地址到内存地址映射）。（静态重定位）

　　　　③动态运行时的装入方式：装入程序将装入模块装入内存后，不对装入模块进行地址变换（逻辑地址转换为物理地址），而是推迟到程序真正要执行时才进行。（动态地址重定位）

　　2、程序的链接

　　　　①静态链接方式：程序运行前，先将各目标模块及其所需库函数链接成一个完整的装配模块，以后不再拆开。

　　　　②装入时动态链接：边装入边链接。

　　　　③运行时动态链接：对某些目标模块，在程序执行中需要时，才对其进行链接。

3、连续分配管理方式：

　　①单一连续分配：（单道程序环境下）将内存分为系统区和用户区，系统区仅供OS使用，用户区仅装用户程序（独占）。

　　②固定分区分配：（多道程序环境下）将整个用户空间划分为若干个固定大小的区域。被划分几个分区便允许几个程序并发运行而不会互相干扰。

　　③动态分区分配：根据进程的实际需要，动态地为之分配内存空间。（数据结构：空闲分区表、空闲分区链；算法：顺序式搜索算法；操作：分配内存、回收内存）

　　④动态可重定位分配：系统对内存进行“紧凑”使若干程序移位，用该程序在内存的新起始地址去置换原来的起始地址。（获得新起始地址--动态重定位：系统中增设一个重定位寄存器存放程序和数据在内存的起始地址，程序执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的）

　　碎片：因为内存中出现不相邻的小分区，而形成的不能被利用的小分区。

　　紧凑：通过移动内存中作业的位置，把原来多个分散的小分区拼接成一个大分区的方法。

4、动态分配分区算法：基于顺序搜索

　　依次搜索空闲分区链上的空闲分区，寻找一个其大小满足要求的分区。

　　①首次适应（FF）算法：要求空间分区链以地址递增的次序链接。分配内存时，从链首开始顺序查找，直至大小满足要求，按照作业大小从该空闲分区划分内存空间给请求者，余下的留在空闲链中。

　　②循环首次适应（NF）算法：从上次找到的空闲分区的下一个空闲分区开始查找。设置起始查寻指针，用于指示下一次起始查寻的空闲分区，采用循环查找方式。

　　③最佳适应（BF）算法：要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。（容易形成许多难以利用的碎片）

　　④最坏适应（WF）算法：扫描整个空闲分区表或链表，挑选一个最大的空闲区，分割一部分存储空间给作业使用。

5、离散存储管理方式：

　　连续分配方式形成的许多“碎片”，不进行“紧凑”，利用离散的方式，将一个进程直接分散地装入到许多不相邻接的分区中。

　　①分页：将用户程序的地址空间分为若干个固定大小的区域（称“页”），相应地，内存空间也分为若干个物理块（页框），页和块的大小相同。离散分配。

　　②分段：将用户程序的地址空间分为若干个大小不同的段，每段可定义一组相对完整的信息，以段为单位离散分配。

　　③段页式：分页和分段相结合。（目前应用较广泛）

6、分页存储管理方式（含义）

　　①页面：将进程的逻辑地址空间分成若干个页，并为各页加以编号，从0开始，如第0页、第1页等。

　　②物理块：将内存的物理地址空间分成若干个块，并为各块加以编号，从0开始，如0#块、#1块等。

　　③地址结构：前一部分为页号P，后一部分为位（偏）移量W（页内地址）。

　　④页表：记录相应页在内存中对应的物理块号，实现从页号到物理块号的地址映射。

7、进程在运行期间，需要对程序和数据的地址进行变换，即将用户地址空间中的逻辑地址变换为内存空间中的物理地址。

　　地址变换方式：设置地址变化机构---利用页面映射表（页表），将逻辑地址中的页号转换为内存中的物理块号，实现从逻辑地址到物理地址的转换。

　　快表：在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器。

8、分段系统的基本原理：

　　用户程序的地址空间分段，分段地址中的地址结构：段号-段内地址

　　①在系统中设置段表寄存器，用于存放段表始址和段表长度。

　　②逻辑地址中的段号S与段表长度TL比较。

　　③若S>TL，段号太大，访问越界，产生越界中断信号。

　　④若S<TL，未越界，根据段表始址和该段段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址。

　　⑤检查比较段内地址d和该段的段长SL。

　　⑥若d>SL，发出越界中断信号。

　　⑦若d<SL，未越界，段基址+段内地址=要访问的内存物理地址。

9、分页系统和分段系统的区别：

　　①页是信息的物理单位，分页系统是系统管理的需要，对用户不可见。

           段是信息的逻辑单位，分段系统是为满足用户的需要。

　　②页的大小固定且由系统决定。

  　　  段的长度不固定，决定于用户所编写的程序，根据信息的性质划分的。

　　③分页的用户程序地址空间是一维的。

　　    分段的用户程序地址空间是二维的。（分段是用户的行为，程序员标示一个地址时，既需给出段名，也需给出段内地址。）

10、段页式存储管理的基本思想：

　　分页系统能有效地提高内存的利用率；分段系统能反映程序的逻辑结构，便于段的共享与保护。将分页与分段两种存储方式结合，形成段页式存储管理方式。
　　段页式存储管理系统，作业的地址空间首先被分成若干个逻辑分段，每段都有自己的段号，然后再将每段分成若干个大小相等的页。对于内存空间也分成大小相等的页，内存的分配以页为单位。

五、虚拟存储器

1、程序运行时的局部性原理：一较短时间内，程序执行仅局限于某个部分，所访问的存储空间也仅局限于某个区域。

　　①时间局限性：程序中存在大量的循环操作。

　　②空间局限性：程序的顺序执行，导致访问区域局限。

2、虚拟存储器

　　1、定义：具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。（逻辑容量由内存容量和外存容量之和决定，运行速度接近于内存速度。）

　　2、特征：

　　　　①多次性：作业无须一次性地全部装入内存运行，允许被分多次调入内存运行，即只需将当前要运行的那部分程序和数据装入内存即可开始运行。（基础：离散分配存储管理方式）

　　　　②对换性：作业运行时程序和数据无须一直常驻内存，允许作业运行时进行换进、换出，即进程运行期间允许那些暂不使用的代码数据从内存调至外存的对换区（换出），待需要时再将其调回至内存（换进）。有效提高内存利用率。

　　　　③虚拟性：能够从逻辑上扩充内存容量，虚拟内存容量（实际内存容量小），实现小内存运行大作业，改善内存利用率，提高并发程度，增加系统吞吐量。

　　虚拟存储器的实现：请求分页系统or请求分段系统

3、请求分页系统：硬件支持、实现请求分页的软件

　　硬件支持：

　　　　①请求页表机制：请求页表增加四个字段作为请求分页的数据结构。（请求分页系统中页表诸项：页号 物理块号 状态位P 访问字段A 修改位M 外存地址）

　　　　②缺页中断机构：每当用户程序要访问的页面尚未调入内存时，产生缺页中断，以请求OS将所缺的页调入内存。

　　　　③地址变换机构：分页系统地址变换机构基础上为实现虚拟存储器，增加功能（如产生和处理缺页中断、从内存换出一页……）。

4、页面调入策略：

　　1、何时调入：预调页策略（一次调入若干相邻页）、请求调页策略（需要时提出请求）

　　2、从何处（外存）调入：对换区（存放对换页面）、文件区（存放文件--未运行过的页面）、UNIX方式（该系统允许页面共享--进程请求页面可能被其他进程调入内存，直接共享）

　　3、调入过程：

　　　每当程序所要访问的页面未在内存（存在位为“0”）

　　　　①向CPU发缺页中断

　　　　②中断处理程序保留CPU环境去分析中断原因

　　　　③转入缺页中断处理程序

　　　　④通过查找页表得到该页所在外存物理块

　　　　⑤若内存未满，启动磁盘I/O，调该缺页入内存，修改页表

　　　　⑥若内存已满，置换算法将内存中一页换出，调该缺页入内存，修改页表

　　　置该页面存在位为“1”，页表项写入快表。

　　4、缺页率：进程运行过程中，访问页面成功的次数S，访问页面失败的次数F

　　　　缺页率f=F/（S+F）

5、页面置换算法：

　　①最佳置换：淘汰的页面是以后永不使用的或在未来很长时间里不再被访问的。（保证获得最低的缺页率，但目前无法预知未来，难以实现，作为标准用来评价其他算法）

　　②先进先出：淘汰在内存中驻留时间最久的页面。（性能较差）

　　③最近最久未使用：根据页面调入内存后的使用情况，记录一个页面自上次被访问以来所经历的时间t，淘汰现有页面中t值大的。

　　④Clock算法：循环地检查各页面的应用情况，最近未用算法。

　　⑤页面缓冲算法：采用可变分配和局部置换方式的内存分配策略，系统为每个进程分配一定数目的物理块的同时自己保留一部分空闲物理块。在内存中设置一个空闲物理块链表（用于分配给频繁发生缺页的进程）、设置一个修改页面链表（已修改的页面不立即换出至外存，而是将其所在物理块挂在修改页面链表的末尾）

6、“抖动”的含义：进程的大部分时间用于页面的换进/换出，几乎无法去做任何有效的工作。

　　原因：系统运行的进程过多，分配给每个进程的物理块少，不能满足进程正常运行的基本要求，运行过程中，频繁缺页。

六、输入输出系统

1、I/O系统的基本功能：

　　①隐藏物理设备的细节：对设备加以适当的抽象，以隐藏掉物理设备的实现细节。

　　②与设备的无关性：对设备抽象化使用。

　　③提高处理机和I/O设备的利用率：尽可能地让处理机和I/O设备并行操作。

　　④对I/O设备进行控制：驱动程序的功能。（控制方式：轮询的可编程I/O方式、中断的可编程I/O方式、直接存储器访问方式、I/O通道方式）

　　⑤确保对设备的正确共享：独占设备（打印机、磁带机）、共享设备（磁盘）

　　⑥错误处理：临时性错误，重试操作；持久性错误，向上层报告。

2、I/O系统的层次结构：

　　①用户层I/O软件：用于实现用户与I/O设备交互。

　　②设备独立性软件：用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护、以及设备分配与释放等。（设备无关的I/O软件）

　　③设备驱动程序：与硬件直接相关，用来具体实现系统对设备发出的操作指令，驱动I/O设备工作。

　　④中断处理程序：用于保护被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完后恢复现场，并返回到被中断的进程。

　　⑤硬件：I/O设备。

3、设备控制器的基本功能：

　　①接收和识别命令：相应的控制寄存器，存放接收的命令和参数，进行译码。

　　②数据交换：CPU与控制器之间、控制器与I/O设备之间，数据交换。

　　③标识和报告设备的状态：控制器记录设备的状态供CPU了解。

　　④地址识别：控制器中配置地址译码器，识别其所控制的设备的地址。

　　⑤数据缓冲区：主机速率高，I/O设备速率低，暂存数据匹配速率再进行数据传送。

　　⑥差错控制：I/O设备传来的数据，设备控制器进行差错检测，若错，将差错检测码置位，并向CPU报告，CPU处理，数据作废，重新传送。

4、I/O通道：特殊处理机，处于CPU和设备控制器之间，具有执行I/O指令的能力，并通过执行通道程序来控制I/O操作。（指令类型单一、与CPU共享内存）

　　通道类型：

　　　　①字节多路通道：按字节交叉方式工作的通道。

　　　　②数组选择通道：按数组方式进行数据传送的数组选择通道，可连高速设备。（易出现独占通道现象，利用率低）

　　　　③数组多路通道：字节多路通道和数组选择通道相结合，按数组方式进行。

5、中断：I/O设备向CPU发来中断信号，CPU暂停正执行的程序，保护现场，转而执行该I/O设备的中断处理程序，执行完后，返回断点，继续执行原程序。（外中断）

　　中断向量表：存放中断处理程序的入口地址于中断向量表中的表项中。每种设备配以相应的中断处理程序，一个设备的中断请求规定一个中断号，一个中断号直接对应中断向量表中的一个表项。（I/O设备发中断请求信号，中断控制器确定中断号，查找中断向量表，取其中断处理程序的入口地址，转入执行该程序）

6、中断处理程序：

　　①测定是否有未响应的中断信号

　　②保护被中断进程的CPU环境

　　③转入相应的设备处理程序

　　④中断处理

　　⑤恢复CPU的现场并退出中断

7、设备驱动程序：I/O系统的高层与设备控制器之间的通信程序。

　　①接收软件发来的命令和参数，将其中的抽象要求转换为与设备相关的低层操作系列。

　　②检查用户I/O请求的合法性，了解I/O设备工作状态，传递与I/O设备操作有关的参数，设置设备的工作方式。

　　③发出I/O命令，若设备空闲，启动I/O设备，完成指定操作；若设备忙碌，将请求块挂在设备队列上等待。

　　④及时响应设备控制器发来的中断请求，根据其中断类型，调用相应的中断处理程序进行处理。

8、对I/O设备的控制方式：

　　①使用轮询的可编程I/O方式：不断循环测试状态寄存器中的忙/闲标志busy。

　　②使用中断的可编程I/O方式：CPU中断处理，I/O设备可与CPU并行工作。

　　③直接存储器访问方式：利用DMA控制器的直接存储器访问方式。

　　④I/O通道控制方式：DMA方式的发展，进一步减少CPU的干预，实现CPU、通道、I/O设备三者的并行操作。

9、设备无关软件：应用程序中所用的设备，不局限于使用某个具体的物理设备。

　　①设备驱动程序的统一接口

　　②缓冲

　　③错误报告

　　④分配与释放专用设备

　　⑤提供与设备无关的块大小

10、Spooling技术--假脱机技术

　　利用一道程序模拟脱机输入时的外围控制机功能，把低速I/O设备的数据传送到高速磁盘上（脱机输入），再利用另一道程序脱机输出时的外围控制机功能，把高速磁盘的数据传送到低速输出设备上（脱机输出）。

　　在联机情况（主机直接控制脱机输入、输出）下实现的同时外围操作的技术。

　　特点：

　　　　①提高I/O的速度。

　　　　②将独占设备改造为共享设备。

　　　　③实现虚拟设备功能。

11、缓冲区：暂存储区域，I/O设备与处理机交换数据的场所。

　　类型：

　　　　①单缓冲区：每当用户进程发出一I/O请求时，OS在内存中为其分配一缓冲区。

　　　　②双缓冲区：生产者缓冲区、消费者缓冲区。

七、文件系统

1、文件系统：OS存储和管理文件信息，方便用户对文件的存取、共享和保护等，有效提高系统资源的利用率。

2、文件的类型：

　　1、按用途分类：

　　　　①系统文件：系统软件

　　　　②用户文件：用户的文件

　　　　③库文件：标准子例程及常用的例程

　　2、按文件中数据的形式分类：

　　　　①源文件：源程序和数据

　　　　②目标文件：源程序经过编译，尚未链接的目标代码“.obj”

　　　　③可执行文件：目标代码经过链接后的文件“.exe”

　　3、按存取控制属性分类：

　　　　①只执行文件

　　　　②只读文件

　　　　③读写文件

　　4、按组织形式和处理方式分类：

　　　　①普通文件：由ASCII码或二进制码组成的字符文件

　　　　②目录文件：由文件目录组成的文件（检索执行下属文件）

　　　　③特殊文件：系统中的各类I/O设备

3、文件系统的层次结构：文件系统接口>对对象进行操纵和管理的软件集合>对象及其属性

　　①文件系统接口：命令接口、程序接口

　　②对对象进行操纵和管理的软件集合：（核心）层次组织结构

　　③对象及其属性：文件、目录、磁盘存储空间

4、文件操作：

　　①最基本的文件操作：创建、删除、读、写文件，设置文件的读/写位置

　　②文件的“打开”和“关闭”操作：用户和文件的连接建立和断开

　　③允许用户直接设置和获得文件的属性，文件共享

5、文件的组织方式：

　　①顺序文件：一系列记录按顺序进行存取操作，文件信息队列排列。

　　②索引文件：建立对应关系的索引表，与主文件构成索引文件。

　　③索引顺序：为每一个文件建立一张索引表，为一组记录中的第一个记录建立一个索引表项。

6、文件结构

　　1、文件目录：数据结构，用于标识系统中的文件及其物理地址，供检索时使用。

　　2、文件控制块FCB：基本信息、存取控制信息、使用信息。

　　3、索引节点：每一个索引节点保存文件系统中的一个文件系统对象的元信息数据，但不包括数据内容或者文件名。

7、目录分类：

　　1、简单目录：单级文件目录，在整个文件系统中只建立一张目录表，每个文件占一个目录项---按名存取（目录项：文件名、文件扩展名、文件长度、文件类型、文件物理地址、文件说明、状态位）

　　2、两级目录：主文件目录（一级，用户名、指向子目录指针），用户文件目录（二级，文件控制块）。

　　3、树形目录：树形结构目录，主目录被称为‘根目录’（唯一），每个文件和每个目录只能有一个父目录，子目录被称为‘树节点’，数据文件被称为‘树叶’。

8、路径名：从主目录开始，把全部目录文件名与数据文件名依次用“/”连接起来，构成数据文件唯一的路径名。

　　1、当前目录：当前访问工作的目录。

　　2、相对路径名：从当前目录开始直到数据文件为止所构成的路径名。

　　3、绝对路径名：从根目录开始的路径名。

9、文件共享方式：

　　①有向无循环图：允许每个文件都可以有多个父目录。

　　②索引节点：文件的物理地址及其他的文件属性等信息放在索引节点中，文件目录中只设置文件名及指向相应索引节点的指针。

　　③符号链接：链接父目录。

10、影响文件安全的因素：人为、系统、自然

　　确保文件系统的安全性：存取控制机制、系统容错机制、建立后备系统

计算机操作系统