操作系统

操作系统占70分，题型及分配比例：
填空题（20%）、选择题（20%）、简述题（20%）、算法实现与综合分析习题（40%）。
[TOC]

一、操作系统概述

1.操作系统的概念、特征、功能和作用
2.操作系统的发展与分类
3.操作系统体系结构

二、进程管理

1.进程与线程

(1)进程概念

① 进程是程序的一次执行
② 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
③ 进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位
进程是进程实体的运行过程
是系统进行资源分配和调度的一个独立单位
进程与程序的区别：进程和程序是两个截然不同的概念，除了进程具有程序所没有的PCB结构（结构性）外，还具有动态性（程序的一次执行，最基本的特征）、并发性、独立性（资源分配和调度的独立单位）和异步性。
进程的组成：PCB（保存进程运行期间的相关数据，是进程存在的唯一标志） + 程序段（能被进程调度程序调度到CPU运行的程序的代码段） + 数据段（存储程序运行期间的相关数据，可以是原始数据也可以是相关结果）
引入进程的目的：为了更好地使多道程序并发执行，提高资源利用率和系统吞吐量。

(2)进程的状态与转换

运行态：占有CPU，并在CPU上运行
（CPU ✓ 其他所需资源 ×）
就绪态：已具备运行条件，但没有空闲CPU
（CPU × 其他所需资源 ✓）
阻塞态：因等待某一事件（打印机、读写磁盘等）而暂时不能运行
（CPU × 其他所需资源 × ）
进程的状态转换

(3)进程控制

对系统中的所有进程实施有效的管理。（原语：进程控制的程序段，执行期间不允许中断，它是一个不可分割的基本单位）
功能：
① 进程的创建：终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等
② 进程的终止：正常结束、发生异常、外界干预
③ 进程的阻塞与唤醒：等待资源 与 资源到达
④ 进程切换：时间片用完、主动放弃处理机、被更高优先级的进程剥夺处理机

(4)进程同步

(5)进程通信

共享存储系统；消息传递系统；管道通信。
进程通信是指进程之间的信息交换。
① 共享存储
在共享空间进行读/写操作实现进程之间的信息交换。

在对共享空间进行读/写操作时，需要使用同步互斥工具（如P、V操作）。
分类：
低级方式的共享是基于数据结构的共享；
高级方式的共享是基于存储区的共享。
② 消息传递
数据交换单位：格式化的消息（Message）。
进程通过系统提供的发送消息和接收消息两个原语进行数据交换。
分类：
a. 直接通信方式——发送进程直接把消息发送给接受进程。

b. 间接通信方式（信箱通信方式）——有中间实体（信箱），发送进程发送消息到信箱，接受进程从信箱取得消息。
③ 管道通信
“管道”——用于连接一个读进程和一个写进程以实现它们之间的通信的一个共享文件，又名pipe文件。
管道机制必须提供三方面的协调能力：互斥、同步和确定对方的存在。

(6)线程概念与线程实现方式

线程：是进程中的一个实体，
是系统独立调度和分派的基本单位。
——“轻量级进程”

  • 🏁进程与线程的比较
    ① 调度
    线程是独立调度的基本单位，
    进程是拥有资源的基本单位
    ② 并发性
    都可以并发执行
    ③ 拥有资源
    进程是拥有资源的基本单位，
    而线程不拥有系统资源。
    ④ 系统开销
    进程远大于线程（因为创建或撤销进程时，系统都要分配或回收资源）
    ⑤ 地址空间和其他资源
    进程的地址空间之间相互独立，
    进程内的线程对其他进程不可见。
    ⑥ 通信方面
    进程间通信（IPC）需要进程同步和互斥手段的辅助，以保证数据的一致性，
    线程间可以直接读/写进程数据段（如全局变量）来进行通信。
  • 线程的实现方式
    ① 用户级线程
    线程管理的所有工作由应用程序完成
    ② 内核级线程
    线程管理的所有工作由内核完成
    ③ 组合方式
    线程创建完全在用户空间中完成，线程的调度和同步也在应用程序中进行。一个应用程序中的多个用户级线程被映射到内核级线程上。

    2.处理机调度

    (1)调度的基本概念

    进程调度的原因：合理的处理计算机软件硬件资源。
    在多道程序系统中，进程的数量往往多于处理机的个数，因此进程争用处理机的情况在所难免。处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

调度的层次－－三级调度
① 作业调度（高级调度）：为后备作业分配内存、输入输出设备等必要的资源，即内存与辅存的调度。发生频率最低。
② 中级调度（内存调度）：选择暂时不能运行的的进程调出内存（此时进程状态叫做挂起态）。发生频率中等。
③ 进程调度（低级调度）：选择就绪队列中合适的进程分配处理机。最基本的调度，发生频率最高。
作业调度为进程活动做准备，进程调度使进程正常活动起来，中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间。

(2)调度时机、切换与过程

进程调度的时机
a. 需要进行进程调度与切换的情况
① 当前运行程序主动放弃处理机：进程正常终止；运行过程中发生异常而终止；进程主动请求阻塞（如等待I/O）。
② 当前运行的进程被动放弃处理机：分给进程的时间片用完；有更紧急的事需要处理（如I/O中断）；有更高优先级的进程进入就绪队列。
b.

(3)调度的基本准则

① CPU利用率
② 系统吞吐量：单位时间内CPU完成作业的数量。
③ ★周转时间
周转时间 = 作业完成时间 - 作业提交时间
平均周转时间 = (作业1的周转时间 + … + 作业n的周转时间)/n
带权周转时间 = 作业周转时间/作业实际运行时间
平均带权周转时间 = (作业1的带权周转时间 + … + 作业n的带权周转时间) /n
④ 等待时间：进程处于等处理机状态的时间之和。
⑤ 响应时间：从用户提交请求到系统首次产生响应所用的时间。

(4)调度方式

① 非剥夺调度方式（非抢占方式）：当一个进程正在处理机上执行时，即使有某个更为重要或更紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入阻塞态时，才把处理机分配给更为重要或紧迫的进程。
② 剥夺调度方式（抢占方式）：当一个进程正在处理机上执行时，有某个更为重要或更紧迫的进程进入就绪队列，则立即暂停正在执行的进程，将处理机分配给这个更重要、紧迫的进程。｛抢占式必须遵循一定原则——优先权、短进程优先和时间片原则等｝

★(5)典型调度算法

①先来先服务调度算法（FCFS）
即先来先服务。属于不可剥夺算法。

特点是算法简单，但效率低；对长作业有利，但对短作业不利（相对于SJF和高响应比）；有利于CPU繁忙型作业，而不利于I/O繁忙型作业。
②短作业(短进程、短线程)优先调度算法（SJF）
指对短作业（进程）优先调度的算法。

缺点：对长作业不利，将导致长作业长期不被调度（饥饿）；不能保证紧迫性作业会被及时处理；作业长短由预估时间而定，不一定能做到真正的短作业优先。
SJF的平均等待时间、平均周转时间最少。
③时间片轮转调度算法；
主要适用分时系统。 先来先服务原则，但仅能运行一个时间片，如100ms。
时间片的长短通常由：系统的响应时间、就绪队列中的进程数目和系统的处理能力决定。
④优先级调度算法；
即可用于作业调度，又可用于进程调度。
⑤高响应比优先调度算法；
主要用于作业调度，是对FCFS和SJF的一种综合平衡。
响应比Rp = (等待时间 + 要求服务时间)/要求服务时间
⑥多级反馈队列调度算法。
是时间片轮转和优先级调度算法的综合与发展。
设置多个就绪队列赋予不同的优先级；赋予各个队列中进程执行的时间片大小各不相同；进1队列，时间片内能完成即可撤离，未完成进2队列

3.同步与互斥

(1)进程同步的基本概念

为了协调进程之间的相互制约关系，引入了进程同步的概念。
临界资源：一次仅允许一个进程使用的资源。（如：打印机、内存中的变量、数据等）
临界资源的互斥访问过程可以分为以下4个部分：进入区—检查是否可以进入临界区； 临界区—访问临界资源的代码； 退出区—清除访问临界区的标志； 剩余区—代码中的其他部分。
进程同步
同步也称为直接制约关系，为协调两个或多个进程的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系来源于它们之间的相互合作。
进程互斥
互斥也称为间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待。
原则：空闲让进、忙则等待、有限等待、让权等待。

(2)实现临界区互斥的基本方法

软件实现方法； p82
① 单标志法
② 双标志先检查
③ 双标志后检查
④ Peterson’s Algorithm：先设置自己的标志再设置turn标志。
硬件实现方法
① 中断屏蔽方法
② 硬件指令方法
TestAndSet; Swap.

★(3)信号量机制

a、解决互斥与同步问题。
只能被两个标准的原语wait(S), signal(S)访问，也可记为“P操作”和“V操作”。
在同步问题中，若某个行为要用到某种资源，则在这个行为前面P这种资源一下；若某个行为会提供某种资源，则在这个行为后面V这种资源一下。
在互斥问题中，P，V操作要紧夹住使用互斥资源的那个行为，中间不能有其他冗余代码。
b、利用信号量实现前驱关系 （看例题）

(4)管程机制

进程同步工具。
管程的特性保证了进程互斥，无需程序员自己实现互斥，从而降低了死锁发生的可能性。
定义：代表共享资源的数据结构，以及对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操 作系统的资源管理模块，称之为管程
组成：①局部于管程的共享数据结构说明；② 对该数据结构进行操作的一组过程； ③对局部于管程的共享数据设置初始值的语句；④ 管程有一个名字
管程的基本特征：① 局部于管程的数据只能被局部于管程的进程所访问；② 一个进程只有通过调用管程内的进程才能进入管程访问共享数据；③ 每次仅允许一个进程在管程内执行某个内部过程。

(5)经典同步问题

生产者-消费者问题
利用记录型信号量对生产者—消费者问题描述如下:

  1. Var mutex, empty, full : semaphore := 1, n, 0 ;
  2. buffer : array[0, … ,n-1] of item； 　　
  3. in，out: integer:=0，0； 
  4. begin 
  5.     parbegin
  6.     producer: begin 
  7.                 repeat
  8.                 ...
  9.                 producer an item nextp;
  10.                 ...
  11.                 wait(empty); wait(mutex)；
  12.                 buffer[in]:=nextp；
  13.                 in:=(in+1) mod n；
  14.                 signal(mutex)；
  15.                 signal(full)；
  16.                 until false；
  17.               end
  18.     consumer: begin
  19.                 repeat
  20.                     wait(full)；
  21.                     wait(mutex)；
  22.                     nextc:=buffer[out]；
  23.                     out:=(out+1) mod n；
  24.                     signal(mutex)；
  25.                     signal(empty)；
  26.                     consumer the item in nextc；
  27.                     until false；
  28.                 end
  29.     parend
  30. end

在生产者—消费者问题中应注意：
首先，在每个程序中用于实现互斥的wait(mutex)和signal(mutex) 必须成对地出现；
其次，对资源信号量empty和full的wait和signal操作，同样需要 成对地出现，但它们分别处于不同的程序中。如wait(empty)在生 产者进程中，而signal(empty)则在消费者进程中，生产者进程若 因执行wait(empty)而阻塞，则以后将由消费者进程将它唤醒；
最后，在每个程序中的多个wait操作顺序不能颠倒，应先执行对 资源信号量的wait操作，然后再执行对互斥信号量的wait操作， 否则可能引起进程死锁。
读者-写者问题
哲学家进餐问题
睡眠理发师问题

4.死锁

(1)死锁的概念

定义：多个进程因竞争资源而造成的一种僵局（互相等待）。｛并发环境下，各个进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象｝

死锁产生的原因：
① 系统资源的竞争－－对不可剥夺资源的竞争、对可消耗性资源的竞争。
② 进程推进顺序非法－－进程在运行过程中，请求和释放资源的顺序不当
③ 信号量使用不当－－生产者消费者问题等
总之，是对不可剥夺资源的不合理分配问题。
死锁产生的必要条件★：
产生死锁必须同时满足以下4个条件，只要其中任意一个条件不成立，死锁就不会发生。
① 互斥条件－－只有对互斥使用的资源争强才会导致死锁
② 不剥夺条件－－资源不能被其他进程强行夺走
③ 请求和保持条件－－进程已经保持了至少一个资源，又提出新的资源请求，请求不到，还对自己获得的资源保持不放
④ 循环等待条件－－存在一种循环等待链
（发生死锁一定有循环等待，有循环等待但不一定死锁）

(2)死锁处理策略

预防死锁：破坏死锁产生的4个必要条件的1个或多个。
避免死锁：用某种方法防止系统进入不安全状态
死锁的检测和解除解除：允许死锁的发生，及时检测出死锁后采取措施解除死锁。

(3)死锁预防

  1. 破坏互斥条件：
    把只能互斥使用的资源改造成允许共享使用。
    如：SPOOLing技术。
    【但有的场合应该保护这种互斥性，因此不常用】
  2. 破坏不剥夺条件：
    a. 当一个已保持了某些不可剥夺资源的进程请求新的资源而得不到满足时，它必须释放已经保持了的所有资源。即 一个进程已占有的资源会被暂时释放。
    b. 操作系统强行抢占。
  3. 破坏请求并保持条件：
    a. 采用预先静态分配方法－－运行前一次分配完全部资源。
    b. 改进第一种－－只获得运行初期所需资源后便开始运行，运行过程中再逐步释放用毕的资源，然后再请求新的所需资源。
  4. 破坏循环等待条件：
    可以采用顺序资源分配法－－首先给系统资源编号，每个进程必须按编号递增的顺序请求资源。

    (4)死锁避免

    系统安全状态：
    安全序列－－按照这种序列分配资源，每个进程都能顺利完成。
    只要能找出一个安全状态，系统就是安全状态。
    只要系统处于安全状态，系统就可以避免进入死锁。
    ★银行家算法
    计算

    (5)死锁检测和解除

    死锁的检测：
    资源分配图 = 进程结点 + 资源结点 + 请求边 + 分配边
    简化资源分配图后能消去图中所有边，则称该图是可完全简化的，此时一定没有产生死锁。
    不能消去所有边的资源分配图是不可完全简化的——死锁定理。
    死锁解除：
    ① 资源剥夺法——挂起某些死锁进程，并抢占它的资源。
    ② 撤销进程法——（终止进程法）强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。
    ③ 进程回退法——让一个或多个进程回退到足以避免死锁的地步。

    三、存储器管理

    1.存储器管理概念

    (1)存储器的层次结构

(2)程序的装入和链接

创建进程的步骤：
① 编译——由编译程序将用户源代码编译成若干目标模块；
② 链接——由链接程序将编译后形成的一组目标模块与所需的库函数链接在一起，形成一个完整的装入模块。
③ 装入——由装入程序将装入模块装入内存运行。
【程序的装入】

  1. 绝对装入方式；
    知道程序将驻留在内存的某个位置，则编译程序将产生绝对地址的目标代码。逻辑地址与实际内存地址完全相同。
    [只适用于单道程序环境]
  2. 可重定位装入方式；
    [在多道程序环境下，所得到的目标模块的起始地址通常是从0开始的，程序中的其它地址也都是相对于起始地址计算的。]
    装入时对目标程序中指令和数据的修改过程称为重定位，地址变换通常是在装入时一次完成的，因此又称为静态重定位。
    静态重定位特点——一个作业装入内存时，必须给它分配要求的全部内存空间，若没有足够的内存，则不能装入该作业。装入后不能移动、不能再申请内存空间。
  3. 动态运行时装入方式。
    也称动态重定位。
    程序在内存中若发生移动，则需要采用动态的装入方式。
    装入内存后，并不立即转换相对地址为绝对地址，而是推迟到程序执行时才进行地址转换。
    动态重定位的特点——可以将程序分配到不连续的存储区中；装入部分代码即可投入运行，根据动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大的多的地址空间。

程序的链接

  1. 静态链接方式；
    在程序运行之前，先将各目标模块及所需库函数链接成一个完整的可执行程序，以后不再拆开。
  2. 装入时动态链接方式；
    将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。
  3. 运行时动态链接方式。
    对某些目标模块的链接，是在程序执行中需要该目标模块才进行的。其优点是便于修改和更新，便于实现对目标模块的共享。

    (3)交换技术

    覆盖与交换技术是在 多道程序环境下 用来扩充内存的两种方法。
    覆盖（了解即可，已成为历史，现在用虚拟内存解决这个问题）
    把用户空间分成一个固定区和若干覆盖区。经常活跃的放在固定区，即将要访问的段放在覆盖区。特点是，打破了必须将一个进程的全部信息装入主存后才能运行的限制。
    交换
    *作用－－提高内存利用率。
    换出——将等待状态的程序从内存移到辅存；
    换入——将准备好竞争CPU运行的程序从辅存移到内存。
    ｛交换需要备份存储，通常是快速磁盘；若换出进程，必须确保该进程完全处于空闲状态；交换空间通常作为磁盘的一整块且独立于文件系统；交换在系统内存吃紧时启动，负荷降低时暂停；普通的交换使用不多，但交换策略的变体仍发挥作用｝

    (4)连续分配存储管理方式

    单一连续分配：
    内存分为系统区（仅供操作系统使用，一般在低地址）和用户区（为用户提供的、除系统区之外的内存空间）。
    简单、无外部碎片，可用覆盖技术；只能用于单用户、单任务的操作系统，有内部碎片，存储器利用率极低。
    固定分区分配：
    将用户空间划分为若干固定大小的区域，每个分区只装入一道作业。无外部碎片。
    程序可能太大而放不进任何一个分区；主存利用率低，有内部碎片。
    ★动态分区分配：
    根据进程大小动态的建立分区。
    ① 基于顺序搜索的动态分区分配算法、
    首次适应算法(First Fit)——按地址顺序查找，不仅是最简单的，通常也是最快最好的算法。
    最佳适应算法(Best Fit)——按容量递增查找
    最坏适应算法(Worst Fit)——按容量递减查找，找到最大的分区
    临近适应算法(Next Fit)——又称为循环首次适应算法，分配内存时从上次查找结束的位置开始继续查找
    ② 基于索引的动态分区分配算法)；
    快速适应算法(quick fit)——又称分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区单独设立一个空闲分区链表。空闲分区的分类根据进程常用的空间大小进行划分，2KB、4KB等。
    伙伴系统(buddy system)——对固定分区算法和动态分区算法折中的方案。[具体看书p140] 在伙伴系统中，分配和回收的时间性能取决于查找空闲分区位置和分割、合并空闲分区所花费的时间。时间性能比分类搜索算法差，但比顺序搜索算法好，而其空间性能则远优于分类搜索法，比顺序搜索法略差。
    哈希算法——哈希算法利用哈希快速查找的优点，以及空
    闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表的表头指针。　　当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。
    ③ 动态可重定位分区分配
    紧凑——将内存中的所有作业进行移动，使它们全都相邻接。
    动态重定位——见前面的“动态运行时装入方式”。
    动态重定位分区分配算法——与动态分区分配算法基本相同，在这种基础上增加了“紧凑”的功能。

★(5)非连续分配管理方式

分页管理方式：
分页——把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位划分，进程在执行时，以块为单位逐个申请主存中的块空间。
分页不会产生外部碎片。进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片（页内碎片）
【几个基本概念】

  • 页——过程中的块
  • 页框（页帧）——内存中的块
  • 块——外存以同样的单位进行划分
  • 页面大小——2的整数幂。大小适中
  • 地址结构——例如下图 0~11位为页内地址，即每页大小为4KB；12－31位为页号，地址空间最多允许220页。
  • 页表——系统为每一个进程建立了一张页表。作用是实现从页号到物理块号的地址映射。｛页表记录进程页面和实际存放的内存块之间的关系；页表项由“页号”和“块号”组成；页表项的长度是相同的，页号是隐含的｝

【地址变换机构】——逻辑地址转变为物理地址

分段管理方式：
分段——按照用户进程中的自然段划分逻辑空间，每个段定义了一组逻辑信息。

段式系统中，段号和段内偏移量必须由用户显式提供。
【优点】① 方便编程 ② 信息共享 ③ 信息保护 ④ 动态增长 ⑤ 动态链接
【段表】——每个进程都有一张逻辑空间与内存空间映射的段表
【地址变换机构】

段页式管理方式：

在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。段表的内容与分段系统略有不同，它不再是内存始址和段长，而是页表始址和页表长度。

分段与分页的比较
① 页是信息的物理单位，分页是为了提高内存利用率。
段是信息的逻辑单位，它含有一组其意义相对完整的信息，分段是为了满足用户的需要。
② 页的大小固定由系统决定。
段的长度不固定，由用户编写的程序决定。
③ 分页的地址空间是一维的，程序员只需要利用一个记忆符，便可表示一个地址。
分段的地址空间是二维的，程序员在标识一个地址时，既需要给出段名，又需给出段内地址。

2.虚拟内存管理

(1)虚拟存储器基本概念

传统存储管理方式特征：
① 一次性——作业必须一次性全部装入内存后才能开始运行→作业很大装不进去内存将无法运行；大量作业只能让少数作业先运行。
② 驻留性——作业被装入内存后就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束→运行中的进程会因等待I/O而阻塞，处于长期等待状态。
局部性原理：
① 时间局部性——程序中的某条指令一旦执行，不久后可能再次执行；某数据被访问后，不久后可能会再次被访问。（由于循环）
② 空间局部性——一旦程序访问了某个存储单元，不久后其附近的存储单元也将被访问，即程序在一定时间内访问的地址，可能集中在某一范围内。
虚拟存储器的定义
“内存-外存”两级存储器结构，利用局部性原理实现高速缓存。
具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。
逻辑容量 与 内存容量 + 外存容量 相关，由计算机的地址结构决定，并不是内存和外存的简单相加；成本→外存成本
虚拟存储器的特征
① 多次性——无需在作业运行时一次性地全部装入内存，而允许被分成多次调入内存运行。
② 对换性——无须在作业运行时一直常驻内存，而允许在作业运行过程中，进行换入和换出。
③ 虚拟性——从逻辑上扩充了内存的容量，使用户看到的内存容量远大于实际的内存容量。

(2)请求分页存储管理方式

目前最常用的一种实现虚拟存储器的方法。
在基本分页系统基础之上，增加了请求调页功能和页面置换功能。当所要访问的页面不在内存中时，通过调页功能将其调入，通过置换功能将暂时不用的页面换出至外存。
硬件支持：一定容量的内存外存、页表机制、缺页中断机构和地址变换机构。
页表机制：

状态位P——用于指示该页是否已调入内存，供程序访问时参考
访问字段A——用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供置换算法换出页面时参考。
修改位M——标识该页在调入内存后是否被修改过。
外存地址——用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。
缺页中断机构
当所要访问的页面不再内存时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时将缺页的进程阻塞（待调页完成后唤醒）。
缺页中断与一般中断的区别：
a. 在指令执行期间中断，属于内部中断。即不是在一条指令执行完后产生和处理中断信号。
b. 一条指令在执行期间，可能产生多次缺页中断。
地址变换机构

(3)页面置换算法

最佳置换算法OPT：
淘汰以后永不使用的页面，或是在最长时间内不再访问的页面，以获得最低的缺页率。
由于无法预知，因此该算法无法实现。
先进先出置换算法FIFO：
每次淘汰的页面是最早进入内存的页面。
实现简单，性能很差，可能出现Belady异常（所分配的物理块数增大而页故障数不减反增的异常现象）。
最近最久未使用置换算法LRU：
每次淘汰最近最久未使用的页面。页表项中记录该页面上次被访问以来所经历的时间t，淘汰t最大的。
逆向扫描过程最后一个出现的页号。
性能很好，但需要寄存器和栈的硬件支持，算法开销大。
最少使用置换算法LFU：
淘汰在最近使用最少的页面。
无法直接记录某页访问的次数（成千上万太多了），只能用LRU那种方法假装记录。
时钟置换算法CLOCK：
循环扫描缓冲区，像时钟一样转动。
页面链接成循环队列，访问过（使用位或访问位）置1，扫描过（修改位）置0 ——
第一优先级~最近没访问，且没修改（0，0）
第二优先级~最近没访问，但修改过（0，1）
↑在这个扫描过程中，对每个跳过的帧，把它的使用位置0
第三优先级~最近访问过，但没修改（0，0）
第四优先级~最近访问过，且修改过（0，1）
即 有未使用过的页面先换出未使用过的，都使用过先换出未修改过的。
页面缓冲算法PBA：
系统自己保留一部分空闲物理块，用于以下两个链表
① 空闲页面链表——当有未被修改的页要换出时，不把它换到外存，把它们所在的物理块挂在空闲链表的末尾。用来读取这些页面的数据时免除从磁盘读入数据的操作。
② 修改页面链表——当要换出一个已修改的页面时，不立即换到外存，将它所在的物理块挂在修改页面链表的末尾。用来降低已修改页面写回磁盘的频率。
特点：显著降低了页面换进、换出的频率，使磁盘I/O的操作次数减少，因而减少了换进换出的开销；换入换出的开销大幅减少，就可以采用一种简单的置换算法如FIFO。

(4)页面分配策略

驻留集：给一个进程分配的物理页框的集合。
三种策略：
① 固定分配局部置换——为每个进程分配一定数目的物理块，在整个运行期间都不改变（驻留集大小不变）
② 可变分配局部置换——只要缺页就从空闲物理块队列中取出物理块分配给进程。
③ 可变分配全局置换——根据进程缺页的频率分配物理块，若频繁缺页，则增加物理块至适当程度，若缺页率低，则适当减少物理块。
调入页面的时机：
① 预调页——运行前的调入
② 请求调页——运行期间调入
从何处调入页面：
文件区和对换区，对换区速度更快。

(5)抖动与工作集

抖动：
指频繁的页面调度行为，刚刚换出的页面马上又换入主存，刚刚换入的页面马上又换出主存。
主要原因——某个进程频繁访问的页面数目高于可用的物理页帧数目。（分配给进程的物理块不够）
工作集：
指在某段时间间隔，进程要访问的页面集合。
工作集模型的原理——让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。
一般驻留集大小要大于工作集大小。

(6)请求分段存储管理方式

共享段的分配与回收 ① 分配——count++ ② 回收——count— ，若为0则回收物理内存

四、输入输出(I/O)管理

1.I/O管理概述

(1)I/O系统的功能

(2)I/O软件层次结构

作用：为了使复杂的I/O软件具有清晰的结构、良好的可移植性和适应性。
每层都利用下层提供的服务完成某些功能，并屏蔽这些功能实现的细节，向高层提供服务。只要层次间的接口不变，对某一层次中的软件的修改都不会引起其下层或高层代码的变更，仅最底层才涉及硬件的具体特性。

① 用户层IO软件——实现与用户交互的接口，用户可直接调用在用户层提供的、与IO操作相关的库函数，对设备进行操作。用户层软件必须通过一组系统调用在获取操作系统服务。
② 设备独立性软件——用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护及设备分配与释放等，同时为设备管理和数据传送提供必要的存储空间。
③设备驱动程序——与硬件直接相关，负责具体是先系统对设备发出的操作命令，驱动IO设备正常工作。控制IO设备工作，为IO内核子系统隐藏设备控制器之间的差异。
④中断处理程序——用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完并恢复被中断进程的现场后，返回被中断进程。
⑤硬件设备——硬件+设备控制器。

(3)I/O系统接口

块设备接口
是块设备管理程序与高层之间的接口。
① 块设备——指数据的存取和传输都是以数据块为单位的设备，如：磁盘等。传输速度快，可寻址，磁盘设备的IO常采用DMA方式。
② 隐藏了磁盘的二维结构。把磁盘的二维结构改变成一种线性序列。
③ 将抽象命令映射为低层操作。如将抽象命令中的逻辑块号转变为磁盘的盘面、磁道和扇区等。
流设备接口
是流设备管理程序与高层之间的接口。又称字符设备接口。
① 字符设备——指数据的存取和传输是以字符为单位的设备，如键盘等。传输速度慢，不可寻址，IO常用中断驱动方式。
② get和put操作——设备字符流进入字符缓冲区（队列），get操作从队列取得一个字符到内存，put操作把一个字符从内存输出到队列。
③ in-control指令——该指令包含了许多参数，每个参数表示一个与具体设备相关的特定功能。处理字符设备间差异过大问题，统一一下。
网络通信接口
计网内容。把计算机连接到网络上的接口。

(4)I/O控制方式

程序直接控制方式（轮询）
在等待IO的过程中CPU需要不断地轮询检查。
由于CPU和IO设备只能串行工作，导致CPU的利用率相当低。
中断驱动方式
引入中断机制，发出读写命令后，将IO进程阻塞，检测到中断信号后再回来。
允许IO设备主动打断CPU的运行并请求服务，从而解放CPU，使得其向IO控制器发送读命令后可以距徐做其他有用的工作。
DMA方式－直接存储器访问方式
在IO设备和内存之间开辟直接的数据交换通路，彻底解放CPU。
改进
① 数据的传送单位是“块”，不再是字。
② 数据的流向是从设备直接放入内存 或 从内存直接到设备。
③ 仅在传送一个或多个数据块的开始和结束，才需要CPU的干预。

IO通道控制方式
利用专门负责输入&输出的处理机。是DMA的发展。
CPU 只有在完成一组数据块的读写后，才需要发出中断信号，请求CPU干预。
每次传输 一组块。

(5)设备控制器

设备控制器的基本功能
① 接受和识别命令。
② 数据交换。
③ 标识和报告设备的状态。
④ 地址识别。
⑤ 数据缓冲区。
⑥ 差错控制。
设备控制器的组成
① 设备控制器与处理机的接口
② 设备控制器与设备的接口
③ I/O逻辑

(6)设备驱动程序

设备驱动程序的特点
① 驱动程序是请求I/O的进程与设备控制器之间的一个通
信和转换程序。
② 驱动程序与设备控制器、I/O设备的硬件特性紧密相关，
因而对不同类型的设备应配置不同的驱动程序。
③ 驱动程序与I/O设备所采用的I/O控制方式紧密相关。
④ 由于驱动程序与硬件紧密相关，因而其中的一部分必
须用汇编语言书写。
⑤ 驱动程序应允许可重入。一个正在运行的驱动程序常会
在一次调用完成前，被再次调用。
设备处理方式
①为每一类设备设置一个进程
②在整个系统中设置一个I/O进程，也可以设置一个输入进程和一个输出进程
③不设置专门的设备处理进程，只为各类设备设置相应的
设备处理程序
★设备驱动程序的流程
① 将抽象要求转换为具体要求
② 对服务请求进行校验
③ 检查设备的状态
④ 传送必要的参数
⑤ 启动I/O设备
附：★中断处理程序的流程
① 检查是否有未响应的中断信号
唤醒被阻塞的驱动程序
② 保护被中断进程的CPU环境
③ 寻找合适的中断处理程序
④ 中断处理
⑤ 还原并退出

(7)设备无关性

也称设备独立性。
设备独立性是指用户在编程序时使用的设备与实际设备无关。一个程序应独立于分配给它的某类设备的具体设备，即在用户程序中只指明IO使用的设备类型即可。
设备独立性有以下优点：
① 方便用户编程
② 是程序运行不受具体机器环境的限制
③ 便于程序移植

2.I/O核心子系统

(1)缓冲区管理

引入缓冲区的目的：
① 缓和CPU与IO设备间速度不匹配的矛盾
② 减少对CPU的中断频率，放宽对CPU中断响应时间的限制。
③ 解决基本数据单元大小（即数据粒度）不匹配的问题。
④ 提高CPU和IO设备的并行性。
单缓冲：
在设备和处理机之间设置一个缓冲区。
单缓冲区处理每块数据的用时为 max(C,T)+M ，T-数据输入缓冲区的时间，M-将缓冲区的数据传送到用户区的时间，C-CPU处理数据的时间。

双缓冲：
双缓冲区处理一块数据的用时为 max(C+M, T)

循环缓冲：
包含多个大小相等的缓冲区，多个缓冲区构成一个环形。

缓冲池：
由多个公用缓冲区组成，缓冲区可以形成以下三个队列
① 空(闲)缓冲区；
② 装满输入数据的缓冲区；
③ 装满输出数据的缓冲区。

(2)设备分配与回收

设备分配：
设备分配——指根据用户的IO请求分配所需的设备。
分配的总原则——充分发挥设备的使用效率，尽可能地让设备忙碌，又要避免由于不合理的分配方法造成进程死锁。
① 独占式使用设备——独占设备
② 分时式共享使用设备——共享设备
③ 以SPOOLing方式使用外部设备——虚拟设备——把一个物理设备变换成多个对应的逻辑设备
设备分配的数据结构：
设备控制表DCT
控制器控制表COCT
通道控制表CHCT
系统设备表SDT
设备分配的考虑因素：IO设备的固有属性、IO设备的分配算法、IO设备分配的安全性以及IO设备的独立性。
设备分配的策略：
① 设备分配原则——既要充分发挥设备的使用效率，又要避免造成进程死锁，还要将用户程序和具体设备隔离开。
② 设备分配方式——静态分配[用于对独占设备的分配]、动态分配[在进程执行过程中根据执行需要进行]。
③ 设备分配算法——先请求先分配、优先级高优先等。
设备分配的安全性：
指设备分配过程中应防止发生死锁。
① 安全分配方式——进程有IO请求就阻塞
② 不安全分配方式——当进程请求的设备被占用时才阻塞

(3)假脱机技术(SPOOLing)

空间换时间。
是将独占设备改造成共享设备的技术。
“脱机”——脱离主机的控制
假脱机——用软件模拟脱机技术
示例：共享打印机
SPOOLing技术特点：提高了IO速度；将独占设备改造成共享设备、实现了虚拟设备功能。

3.磁盘存储器的性能和调度

(1)磁盘性能与结构

｛
磁头－－导体线圈，从磁盘存取数据
磁道——磁盘盘面上的数据存储在一组同心圆中，称为磁道
扇区——磁道划分为几百个扇区，每个扇区固定存储大小（通常为512B），一个扇区称为一个盘块
｝
磁盘地址用“柱面号 · 盘面号 · 扇区号（或块号）”表示。

磁盘类型
固定头磁盘－－磁头相对于盘片的径向方向固定的，每个磁道一个磁头；
活动头磁盘－－磁头可移动的
固定盘磁盘－－磁盘永久固定在磁盘驱动器的
可换盘磁盘－－可移动和替换的

(2)磁盘调度算法

先来先服务FCFSl；
最短寻道时间优先DDTF；
扫描算法SCAN (电梯调度算法)；
循环扫描算法CSCAN；
NStepSCAN和FSCAN调度算法。

五、文件管理

1.文件系统基础

(1)文件概念

文件是以计算机硬件为载体的存储在计算机的信息集合。
它的形式多样，可以是文本文档、图片、程序等。
在用户输入输出中，以文件为基本单位。
文件系统
操作系统中负责管理和存储文件信息的软件机构称为文件管理系统，简称 文件系统。
文件系统由三部分组成 ①与文件管理相关的软件 ②被管理文件 ③ 实施文件管理所需要的数据结构
文件的结构｛
① 数据项——数据项是文件系统中最低级的数据组织形式，

  • 基本数据项
  • 组合数据项

② 记录——记录是一组相关的数据项的集合。
③ 文件——文件是指由创建者所定义的一组相关信息的集合，逻辑上分为有结构文件（记录式文件）和无结构文件（流式文件）。

｝

(2)文件的逻辑结构（顺序文件、索引文件、索引顺序文件）

文件的逻辑结构 文件的物理结构
从用户观点出发看到的文件的组织形式 从实现观点出发看到的文件在外存上的存储组织形式
与存储介质特性无关 与存储介质特性有很大关系

文件的逻辑结构实际上是指在文件的内部，数据逻辑上是如何组织起来的。
无结构文件：流式文件，单位 字节（Byte），如源程序文件、目标代码文件等基本信息单位操作不多的文件适合这种组织形式。
★有结构文件：记录式文件
① 顺序文件——文件中的记录一个接一个地顺序排列，记录通常是定长的，可以顺序存储或链式存储。访问时需要顺序搜索。有两种结构 串结构（按时间排列），顺序结构（按关键字顺序排列）。批量操作是效率最高的。只有顺序文件才能储存在磁带。缺点是增删改查单项记录的操作比较困难。
② 索引文件——当记录为可变长度时，通常为之建立一张索引表，并为每个记录设置一个表项，以加快对记录检索的速度。索引表本身是定长记录的顺序文件。通过索引可以成百上千倍的提高访问速度。主要用于对信息处理的及时性要求比较高的场合。也可以用不同的数据项建立多个索引表。

③ 索引顺序文件——
索引顺序文件是最常见的一种逻辑文件形式。它有效地克服
了变长记录文件不便于直接存取的缺点，而且付出的代价较小。[将顺序文件的所有记录分为若干组，在为各组建立索引表，索引表中为每组的一条记录。] 若记录数很多，可以采用两级或多级索引。

④ 直接文件或散列文件——给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。没有顺序的特性。

(3)文件目录

文件控制块和索引节点：
① 文件控制块（FCB）——是用来存放控制文件需要的各种信息的数据结构。
FCB的有序集合称为文件目录，一个FCB就是一个目录项。
FCB主要包含｛基本信息，存取控制信息，使用信息｝
FCB必须连续存放。
② 索引结点——文件描述信息单独形成一个称为索引结点的数据结构，简称i结点。每个目录项 = 文件名 + i结点的指针。
磁盘索引结点——存放在磁盘上的索引结点称为磁盘索引结点。主要包括｛文件主标识符，文件类型，文件存取权限，文件物理地址，文件长度，文件链接计数，文件存取时间，索引结点编号，状态，访问计数，逻辑设备号，链接指针｝
单级目录结构和两级目录结构：
① 单级目录结构
在整个文件系统中只建立一张目录表，每个文件占一个目录项。
单级目录优点－－简单且能实现目录管理的基本功能—按名
存取。缺点－－查找速度慢、文件不允许重名、不便于文件共享等。

② 两级目录结构
将文件目录分成 主文件目录（Master File Directory，MFD，记录用户名及相应用户文件目录所在的存储位置）和 用户文件目录（User File Directory，UFD，记录该用户文件的FCB信息）。
优点－－解决了不同用户文件的“重名”问题，在一定程度上保证了文件的安全；缺点－－缺乏灵活性，不能对文件分类。

树形目录结构：
将两级目录的层次关系加以推广。
进程对各个文件的访问都是相对于当前目录进行的。[因此这里引入了相对路径的概念]
好处－－可以很方便的对文件进行分类，层次结构清晰，能够更有效的进行文件的管理和保护；缺点－－在树形结构目录中查找文件时，需要按路径逐级访问中间结点，这就增加了磁盘访问次数，无疑影响了查询速度。
Linux，Windows都用的树形结构。

(4)文件共享

文件共享使多个用户（进程）共享同一个文件，系统中只需保留该文件的一个副本。
常用的两种方式
基于索引结点的共享方式（硬链接）
多个指针指向一个索引结点，保证只要还有一个指针指向索引结点，索引结点就不能删除。
利用符号链实现文件共享（软链接）
把到达共享文件的路径记录下来，当要访问文件时，根据路径访问文件。
优点－－网络共享仅需提供该文件所在机器的IP及文件目录即可。
硬链接和软链接都存在一个问题－－每个共享文件都有几个文件名，即每增加一条链接就增加一个文件名。
硬链接和软链接都是文件系统中的静态共享方法。
硬链接的查找速度比软链接快。
此外还有动态共享，能实现两个进程同时对一个文件进行操作。

(5)文件保护

解决文件的读、写、执行的许可问题。
一般方法
① 口令加密
② 加密保护——①②是为了防止用户文件被他人存取或窃取；
③ 访问控制——用于控制用户对文件的访问方式。

2.磁盘存储器的管理

(1)外存组织方式

连续组织方式；链接组织方式（FAT技术、NTFS技术）；索引组织方式。

(2)文件存储空间的管理

空闲表法；空闲链表法；位示图法；成组链接法。

(3)提高磁盘I/O速度的方法

(4)磁盘可靠性技术

(5)数据一致性控制