操作系统

概述

操作系统的类型

1. 多道程序设计技术和批量操作系统
2. 分时技术与分时系统
3. 实时操作系统

多道程序设计技术和批量操作系统

概念

多道程序设计技术是在计算机内存中同时存放几道相互独立的程序，它们在管理程序的控制下相互穿插地运行。

在批处理系统中采用多道程序设计技术，就形成了批量操作系统。该系统把用户提交的作业成批地送入计算机内存，然后由作业调度程序自动地选择作业运行。

特点

• 多道：内存中同时存放几个作业；
• 宏观上并行运行：都处于运行状态，但都未运行完；
• 微观上串行运行：各作业交替使用 CPU；

优点

• 资源利用率高：CPU 和内存利用率较高
• 作业吞吐量大：缩短作业之间的交接时间，单位时间内完成的工作总量大

缺点

• 用户交互性差：整个作业完成后或中间出错时，才与用户交互，不利于调试和修改
• 作业平均周转时间长：短作业的周转时间显著增长

分时技术与分时系统

概念

把处理机的响应时间分成若于个大小相等（或不相等）的时间单位，称为时间片（如 100 毫秒），每个终端用户获得 CPU，就等于获得一个时间片，该用户程序开始运行，当时间片到（用完），用户程序暂停运行，等待下一次运行。

分时操作系统利用分时技术实现多道程序设计的一种操作系统，它一般采用 时间片轮转 的办法，使一台计算机同时为多个终端用户服务，对每个用户都能保证足够快的响应时间，并提供交互会话功能。

目标

提高计算机系统的交互性和响应时间

特点

1. 同时性：众多联机用户可以同时使用同一台计算机
2. 独占性：各终端用户感觉到自己独占了计算机
3. 及时性：用户的要求能够及时得到响应
4. 交互性：用户与计算机之间可进行会话

实时系统

概念

实时操作系统主要用于过程控制、事务处理等有实时要求的领域。实时系统要求对外部的请求，实时操作系统能够在规定的时间内处理完毕。

特点

1. 系统对外部的信号必须能在规定的时间内及时响应
2. 要求高可靠性和安全性，效率则放在第二位
3. 系统整体性强
4. 不要求很强的“会话”能力

应用

1. 实时控制：工业过程控制、防空系统等
2. 实时信息处理：情报检索和查询、飞机订票系统、银行信用卡系统

三种系统的异同

批量操作系统与分时系统

1. 用户体验上：批量操作系统用户交互性差，只有作业完成或出错时才与用户交互，用户也不能控制作业的运行；而分时系统可以让用户的要求得到及时的响应
2. 侧重层面上：批量操作系统侧重于多个程序与操作系统的关系；分时系统侧重于多个用户与操作系统的关系

分时系统与实时系统

1. 用户交互上：分时系统可以让用户的要求得到及时的响应；实时系统不要求很强的用户交互性
2. 响应时间上：实时系统对系统的响应时间要求更高；而分时系统的响应时间由人能够承受的等待时间决定。
3. 可靠性：相比于分时系统，实时系统对可靠性要求更高。

特点

1. 并发：两个或多个事件在同一时间间隔内发生
2. 共享：系统中的资源可供内存中多个并发执行的进程(线程)共同使用。分为互斥共享和同时共享两种方式。
3. 虚拟：虚拟处理机、虚拟内存、虚拟外部设备和虚拟信道等
4. 异步：由于资源等因素的限制，使进程的执行通常都不是“一气呵成”，而是以“停停走走”的方式运行。

操作系统的虚拟性

1. 虚拟处理机技术：利用多道程序设计技术，把物理 CPU 虚拟为多个逻辑 CPU。此时一个 CPU 可以供多个用户使用。

通过多道程序设计技术，让多道程序并发执行的方法，来分时使用一台处理机的。亦即，利用多道程序设计技术，把一台物理上的 CPU 虚拟为多台逻辑上的 CPU，也称为虚拟处理机，我们把用户所感觉到的 CPU 称为虚拟处理器。 此时，虽然只有一台处理机，但它能同时为多个用户服务，使每个终端用户都认为是有一个 CPU 在专门为他服务。

2. 虚拟存储器技术：将物理存储器变为虚拟存储器，从而从逻辑上拓充存储器的容量。

将一台机器的物理存储器变为虚拟存储器，以便从逻辑上来扩充存储器的容量。此时，虽然物理内存的容量可能不大(如 32 MB)， 但它可以运行比它大得多的用户程序(如 128 MB)。这使用户所感觉到的内存容量比实际内存容量大得多，认为该机器的内存至少也有 128 MB。当然这时用户所感觉到的内存容量是虚的。我们把用户所感觉到的存储器称为虚拟存储器。

3. 虚拟设备技术：将物理 I/O 设备转变为多个逻辑上的 I/O 设备，使得一个设备可以供多个用户使用。

虚拟设备技术，将一台物理 I/O 设备虚拟为多台逻辑上的 I/O 设备，并允许每个用户占用一台逻辑上的 I/O 设备，这样便可使原来仅允许在一段时间内由一个用户访问的设备(即临界资源)，变为在一段时间内允许多个用户同时访问的共享设备。例如，原来的打印机属于临界资源，而通过虚拟设备技术，可以把它变为多台逻辑上的打印机，供多个用户“同时”打印。此外，也可以把一条物理信道虚拟为多条逻辑信道(虚信道)。在操作系统中，虚拟的实现主要是通过分时使用的方法。

组织架构

操作系统的接口

1. 命令接口：（作业一级）提供一组控制命令供用户去组织和控制自己的作业
2. 系统调用：（程序一级）通过一组广义指令（或称系统调用）供用户程序和其他系统程序调用

处理机的状态

分类

1. 核态(Kernel Mode)：CPU 执行操作系统程序时所处的状态。在此状态下允许 CPU 使用全部资源和全部指令，其中包括一组特权指令（如涉及外设的 I/O、改变处理机状态、修改存储保护的指令），实现对系统资源的分配与管理，为用户提供使用外部设备的服务。
2. 管态(Supervisor mode)：管态比核态的权限低，在此状态下允许使用一些用户态下不能使用的资源，但不能使用修改 CPU 状态的指令。无核态时，管态执行核态的全部功能。
3. 用户态(User Mode)：用户程序执行时 CPU 所处的状态。在此状态下禁止使用特权指令，不能直接使用系统资源与改变 CPU 状态，并且只能访问用户程序所在的存储空间。

特权指令

在核态下操作系统可以使用所有指令，包括一组特权指令：

• 允许和禁止中断；
• 在进程之间切换处理机；
• 存取用于内存保护的寄存器；
• 执行输入和输出操作；
• 停止一个中央处理机的工作。

在下列情况下，由用户态转向核态：

• 用户程序要求操作系统的服务，系统调用；
• 发生一次中断；
• 在用户程序中产生了一个错误的状态；
• 在用户程序中企图执行一条特权指令；

从核态转回用户态用一条指令实现，这条指令也是特权指令，一般是：

• 中断返回指令

中断技术

类型

1. 输入输出中断：它是当外部设备或通道操作正常结束或发生错误时所发生的中断。例如：打印机打印完成、缺纸，读磁盘时相应驱动器中没有磁盘等。
2. 外中断：对某个中央处理机而言，它的外部非通道式装置所引起的中断称为外部中断。例如，时钟中断、操作员控制台中断，多处理机系统中 CPU 到 CPU 之间的通信中断等。
3. 硬件故障中断：当机器发生故障时的中断叫硬件故障中断。例如，电源故障、内存单元奇偶校验错。
4. 程序性中断：在程序执行的过程中，发现了程序性质的错误或出现了某些特定状态而产生的中断。如浮点溢出、用户态下使用了特权指令、内存越界、跟踪等。
5. 访管中断：对操作系统提出某种请（需）求时所发生的中断。例如，创建进程，I/O 传输、打开文件、关闭文件、文件的读、写等系统调用。

也可以分为两类：

1. 来自处理机外部的事件，称为外部中断，如 I/O 中断、外中断。
2. 是来自处理机的中断，称为内部中断，如硬件故障中断、程序性中断、访管中断。这类中断有时称俘获。

机制

1. 保护现场
2. 中断响应
3. 中断处理
4. 恢复现场

保护中断现场和恢复现场

现场：是被中断断点时刻处理机的各种信息，包括：

• 程序状态字
• 各寄存器的值
• 打开文件的状态

保护现场：在进入中断时将现场信息保存到指定的位置，一般情况是保留到系统栈中。
恢复现场：在中断处理完成后，返回断点之前将保留在栈中的断点的现场信息恢复，使被中断的程序能继续正确地执行。

中断响应

是处理机发现有中断请求时，中止现运行程序的执行，并自动引出中断处理程序的过程。

中断响应的实质是交换指令执行地址和处理机的状态，以达到如下目的：

• 保留程序断点及有关信息；
• 自动转入相应的中断处理程序执行。

中断响应过程:

• 发现中断源(识别中断原因)
• 保存现场,将中断向量推入系统堆栈
• 引出中断处理程序

中断响应具体做法:

• CPU 在执行每条指令后扫描中断寄存器，查看有无中断请求。
• 如果没有，则运行下一条指令；
• 如果有中断请求，则通过交换中断向量引出（进入）中断处理程序

中断处理

当硬件完成了中断进入后，转到中断处理程序，进入软件中断处理过程。

1. 硬件中断的处理（硬件故障）
2. 软件中断的处理（程序错误等）
3. 外部中断的处理（时钟中断等）
4. 外部设备中断的处理（传输结束、出现错误等）

程序状态字

在计算机系统中有一个寄存器（有的系统有几个寄存器）用来存放程序状态字，称为 PS。其中包括：

• 指令计数器
• 程序现应执行哪条指令，当前指令执行的情况
• 机器处于何种状态（核态、用户态）
• 程序执行时应屏蔽哪些中断（处理机运行级）
• 寻址方式、编址、保护键
• 响应中断的内容

用户界面

作业

作业和作业步

1. 作业：要求计算机系统按指定的步骤对原始数据进行处理，并得到计算结果的加工工作。

2. 作业步：对作业的加工工作中的一个步骤称为一个作业步。

3. 四个作业步：编辑、编译、连接、运行

4. 作业步之间的关系：

   • 每个作业步运行的结果产生下一作业步运行所需要的文件。
   • 一个作业步能否正确执行，取决于前一作业步是否成功完成。

作业的状态

1. 进入状态：作业的信息从输入设备上预输入到输入井，此时称为作业处于进入状态。
2. 后备状态：当作业的全部信息都已输入，且由操作系统将其存放在输入井中，此时称作业处于后备状态。系统将所有处于后备状态的作业组成后备作业队列，等待作业调度程序的调度。
3. 运行状态：一个后备作业被作业调度程序选中，分配了必要的资源，调入内存运行，称作业处于运行状态。④
4. 完成状态：当作业正常运行完毕或因发生错误非正常终止时，作业进入这完成状态。

系统调用

概念

是操作系统和用户的第二个接口。它是管理程序提供的服务界面，或更确切地说是操作系统中支持程序设计语言正常工作的支撑系统所提供的界面。

与一般过程调用的区别

1. 运行在不同的系统状态：系统调用中，调用程序运行在用户态，而被调用程序则运行在核心态；一般过程调用都在用户态。
2. 状态的转换：一般的过程调用不涉及系统状态的转换，但系统调用通常都是通过软中断机制先由用户态转换为核心态。
3. 返回问题：一般的过程调用在被调用过程执行完后，将返回到调用过程继续执行。但系统调用结束后，系统将根据优先级进行调度。
4. 嵌套调用：像一般过程一样，系统调用也允许嵌套调用，但每个系统对嵌套调用的深度都有一定的限制。

实现机制

系统调用是通过访管指令实现的。

在程序中，如果希望请求操作系统的服务（例如，打开一个文件，显示某个目录的内容等），就要执行一条访管指令（trap、int），系统处理这个中断，即为用户提供相应的服务（或者称响应用户的请求）。

并发和调度

程序的两种执行方式

顺序执行

一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。

1. 顺序性：处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束；
2. 封闭性：程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它；
3. 可再现性：程序执行的结果与初始条件有关，而与执行时间无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。

并发执行

若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。

特点：

1. 失去了程序的封闭性和结果的可再现性：程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度。
2. 程序与计算不再一一对应：在程序顺序执行时，一个程序总是对应一个具体的计算；并发执行时，一个程序对应多个计算。
3. 程序执行的间断性：程序在并发执行时，由于它们共享资源或为完成同一项任务而相互合作，致使在并发程序之间形成了相互制约的关系。
4. 资源共享：程序的并发执行与资源共享之间互为条件：一方面，资源共享是以程序并发执行为条件的；另一方面，资源共享的有效管理必将影响程序的并发执行程度。
5. 程序并发执行的相互制约：同步和互斥

进程

特征

最基本的两个特征：并发性和动态性。

1. 并发性：任何进程都可以同其他进程一起向前推进
2. 动态性：对应程序的执行；动态产生消亡；在三种状态间转换
3. 独立性：进程是 CPU 调度的一个独立单位
4. 交互性：指进程在执行过程中可能与其它进程产生直接或间接的关系
5. 异步：每个进程都与其相对独立的不可预知的速度向前推进
6. 结构性：

组成

1. 程序:表示该进程所要进行的操作
2. 数据:程序加工的对象和场所、它包括操作的数据和程序自己的变量单元
3. PCB:
   • 用于刻画一个进程在各个不同时期所处的状态的数据块
   • 作用：是标识进程的唯一实体；操作系统根据 PCB 对进程实施管理和控制

进程与程序

1. 进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件，是静态和可以复制的。
2. 进程是暂时的，程序的永久的：进程是对应程序的执行过程过程，有一定的生命周期，而程序可长久保存。
3. 进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。
4. 进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。
   进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位，也是一个独立的运行单位。

线程的概念

特点

1. 并发程度高：可在系统中建立多线程提高并发度。
2. 易于调度，开销小（经济）：线程的创建时间、终止时间比进程短；同进程内的线程切换时间比进程短（上下文有许多是相同的）；
3. 由于同进程内线程间共享进程的代码，数据，内存和文件资源，可直接进行不通过内核的通信；而进程间的通信需要通过内核进行，以提供保护和通信所需机制
4. 响应度高
5. 资源共享：线程共享它们所属进程的内存和资源。
6. 多处理器体系结构的利用。

分类

1. 用户级线程：内核不了解用户线程的存在，切换也不需要内核特权，切换速度快；一旦发起系统调用，整个进程直接阻塞。
2. 内核支持线程：内核知道线程的存在，并加以控制；切换开销较大；系统调用只阻塞进程。

进程和线程的区别

状态

最基本的状态

1. 就绪状态(Ready)：存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到 CPU，就立即可以运行，这些进程所取的状态为就绪状态。（有多个进程处于此状态）
2. 运行状态(Running）：当进程由调度/分派程序分派后，得到 CPU 控制权，它的程序正在运行，该进程所处的状态为运行状态。(在单 CPU 系统中，总只有一个进程处于此状态）
3. 等待状态(Wait)：若一个进程正在等待某个事件的发生（如等待 I/O 的完成），而暂停执行，这时，即使给它 CPU 时间，它也无法执行，则称该进程处于等待状态。

graph TB
READY(就绪)-->RUNNING(运行)
RUNNING-->WAIT(等待)
WAIT-->READY
RUNNING-->READY

1. 就绪–>等待：等待某事件的发生（如等待 I/O 完成）
2. 等待–>就绪：某事件已经完成（如 I/O 已经完成）
3. 运行–>就绪：时间片用完了
4. 就绪–>运行：处理机空闲时，调度程序选择一个程序占用 CPU
5. 新建进程默认进入就绪状态

其他状态

1. 终止：中止后进程移入该状态，它不再具有执行资格
2. 挂起：引入挂起状态可能是基于下述需要：调节负载，对换，父进程，操作系统，终端用户
3. 创建：OS 已完成为创建一进程所必要的工作，但未允许执行

五状态模型：

七状态模型：

作业的状态

1. 提交状态:用户将自己的程序和数据放在输入设备上，等待；
2. 后备状态:系统响应用户的要求，将作业带领到直接存取的后援存储器中，等待调度；
3. 执行状态:从作业计算开始，到计算完成为止，该作业处于执行状态；
4. 完成状态:从作业计算完成开始，到善后处理完毕退出系统为止，称为作业完成状态。

进程控制

1. 创建原语：fork
2. 撤销原语：exit
3. 阻塞原语：sleep
4. 唤醒原语：wakeup

进程的相互制约关系

1. 两种方式：互斥、同步
2. 原因：资源共享、进程协作

互斥

1. 临界资源：一次仅允许一个进程使用的资源称为临界资源。
2. 临界区：每个进程中访问临界资源的那段程序段称为临界区（临界段）。

在操作系统中，当某一进程正在访问某临界区时，就不允许其它进程进入。我们把进程之间的这种相互制约的关系称为互斥。

某一个资源只能同时被一个进程访问和修改。

同步

并发进程在一些关键点上可能需要相互等待与互通消息，这样的相互制约关系称为进程同步。

进程需要等待另一个或进程完成

同步规则：

1. 空闲让进：当没有进程处于临界区时，可以允许一个请求进入临界区的进程立即进入自己的临界区。
2. 忙则等待：当已有进程进入其临界区时，其他试图进入临界区的进程必须等待。
3. 有限等待：对要求访问临界资源的进程，应该保证能在有限时间内进入自己的临界区。
4. 让权等待：当进程不能进入自己的临界区时，应释放处理机。

区别

互斥：仅是让两个进程不能同时访问某资源；
同步：互斥且同步执行的各进程前后顺序有限制。

互斥是无序的，同步是有序的。

• 例题

1. 若干同学缴纳学费。

互斥 资源是窗口。一个窗口只能有一个人去缴费。但对于学生的顺序没有规定。

2. 两队举行篮球比赛。

互斥 资源是球。一次只能有一个运动员拿球，但对于拿球的顺序是没有规定的。

3. A 考试抄 B 的答案。

同步 资源是这个题的答案。只有 B 做完了，A 才能抄。

4. 4 个同学参加 4 * 100 接力赛

同步 资源是接力棒。很明显，参加比赛之前，每个运动员拿棒的顺序是固定的。

通信

通信方式

1. 共享内存
2. 消息传递系统
3. 管道

类型

1. 低级通信：信号量、管程等
2. 高级通信：直接通信（消息缓冲机制）、间接通信（使用信箱）、管道

资源管理

目的

1. 保证资源的高利用率；
2. 在“合理”时间内使所有顾客有获得所需资源的机会；
3. 对不可共享的资源实施互斥使用；
4. 防止由资源分配不当而引起的死锁。

任务

1. （分配）解决资源分配问题，并严防发生死锁现象
2. （存取使用）解决对资源地存取、使用方法问题
3. （控制保护）提供对资源存取的控制和实行安全保护措施

数据结构

1. 资源描述器（资源的描述）：描述各类资源的最小分配单位的数据结构
2. 资源信息块（资源的申请和分配）：资源、请求者以及实施分配所需信息。包含可利用资源队列和该类资源的等待队列。

死锁

概念

两个或两个以上并发进程，如果每个进程持有某种资源，而又等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，每个进程都占用了一定的资源，但又都不能向前推进。这种现象称为死锁。

两个资源互相等待资源，无法向前推进

产生原因

1. 资源竞争
2. 进程推进顺序不当

竞争不意味着死锁

必要条件

1. 互斥条件：资源不可共享，一次只能由一个进程使用。
2. 不可剥夺条件（非抢占）：进程占用的资源只能由进程自己释放，其他进程不能夺走。
3. 部分分配：进程每次申请一部分资源。等待新资源的同时，继续占有已有的资源。
4. 循环等待条件（环路）：存在一种进程的循环链，链中的每一个进程已获得的资源被下一个进程所请求。

解决死锁问题的策略

1. 死锁预防：预先设置一些条件限制去破坏四个必要条件之一，从而预防死锁。缺点：系统资源利用率、吞吐率降低。（预先条件限制）
2. 死锁避免：不预先采取条件限制，只是在动态分配前提下，防止进入不安全状态，从而避免死锁。适当提高资源利用率，吞吐率。（动态分配时防止进入不安全状态）
3. 死锁检测：允许死锁发生，再去检测发生死锁的进程和资源，然后去消除死锁。（允许发生，然后检测）
4. 死锁解除：取消或挂起相应发生死锁的进程，回收该进程资源，再分配给阻塞进程。

死锁预防

1. 预先静态分配法（破坏部分分配）：在作业运行前一次性将其所需的全部资源分配给它。
2. 有序资源使用法（破坏环路）：资源编号，每个进程按资源序号次序请求资源。
3. “可剥夺”资源使用法（破坏不可剥夺）：申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。（申请资源不成功时，必须释放已有资源）

处理机调度

二级调度

1. 宏观上：作业调度
   • 使该作业对应的进程（进入就绪态），具有使用 CPU 的权利。
   • 任务：将外存上的作业有选择地调入内存，建立作业对应的进程，使其投入运行。
2. 微观上：进程调度
   • 从各就绪进程中选中一个，使其占有 CPU 开始执行。
   • 任务：在进入内存的所有进程中，确定哪个进程何时占有 CPU ，使用多长时间。

三级调度

1. 高级调度（作业调度、宏观调度）：按一定原则对外存输入井上的作业进行调度，并建立进程 PCB。
2. 中级调度（交换调度）：它决定允许哪些进程竞争处理机。
3. 低级调度（进程调度）：它决定了存在就绪进程时，哪一个就绪进程将分配到中央处理机。

作业调度

JCB

它是存放作业控制和管理信息的数据结构。

目标

1. 对所有作业应该是公平合理
2. 应使设备有高的利用率
3. 每天执行尽可能多的作业
4. 有快的响应时间

衡量标准

平均周转时间和带权平均周转时间

1. 作业周转时间$t_i$：完成时间-提交时间
2. 平均周转时间：

$$T=\frac{\sum_{i}^n t_i}{n}$$

3. 带权周转时间$w_i=\frac{t_i}{t_r}$: 周转时间除以实际运行时间
4. 平均带权周转时间：

$$T=\frac{\sum_{i}^n w_i}{n}$$

主存管理

功能

1. 主存映射 映射逻辑地址到物理主存地址：将程序地址空间中使用的逻辑地址变换成主存中的地址。
2. 主存分配 在多用户之间分配物理主存：按照一定的算法把某一空闲的主存区分配给作业或进程。
3. 主存保护 对操作系统以及各用户的信息提供保护措施：保证用户程序(或进程映象)在各自的存储区域内操作，互不干扰。
4. 主存扩容 扩充逻辑主存区：提供虚拟存储技术，使用户程序的大小和结构不受主存容量和结构的限制，即使在用户程序比实际主存容量还要大的情况下，程序也能正确运行。

映射、分配、保护、扩容

虚拟存储技术

实现条件：

1. 需要有相当容量的辅存
2. 要有一定容量的主存
3. 地址变换机构。引进虚存后必须在地址变换上花费开销，所以，在设计虚拟存储器时，应力求地址变换能快速进行。

主存分配策略

3 种放置策略

1. 最佳适应算法：将申请者放入与其大小最接近的空闲区中。
2. 首次适应算法：从表首开始找到第一个满足要求的空闲区分配给申请者。
3. 最坏适应算法：将最大的空闲区分配给请求者。

2 种调度策略

当要访问的页面不在内存中，便会发生缺页中断。

1. 预调策略:系统预测程序哪些页需要执行，从而在运行前调入内容，避免缺页中断。（难以实现）

2. 请调策略:进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求。

5 种淘汰策略

当要将某一个待访问的页面送入到全满的内存中时，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫做置换算法。

衡量指标

设$s$ 为访问成功的次数，$f$为访问失败的次数，$a=s+f$ 为访问总次数。那么缺页中断率$f'=\frac{f}{s+f}$

缺页中断率越小，性能越高。

1. 最佳算法(OPT):淘汰以后不再使用的页。
2. 先进先出(FIFO):淘汰最早进入队列的页。
3. 最久未使用淘汰算法(LRU):淘汰最长时间未使用的页。
4. 最不经常使用淘汰算法(LFU):淘汰最近访问次数最少的页。
5. 简单的 Clock 置换算法: 在页表中设一个“引用位”，当存储分块表中的某一页被访问时，该位由硬件自动置 1，并由页面管理软件周期性把所有引用位置 0。这样，在一个时间周期 T 内，某些被访问过的页面其引用位为 1，而未被访问过的页面其引用位为 0。

碎片问题

概念和危害

系统运行一段时间，分布在主存各处的破碎空闲区占据了相当数量的空间，当一个作业申请一定数量的主存时，虽然此时空闲区的总和大于新作业所要的主存容量，但却没有单个的空闲区大到足够装下这个作业。

消除

1. 拼接技术：移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区。（消耗资源，且需要停止其他工作）

2. 覆盖技术：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。将程序必要部分(常用功能)的代码和数据常驻内存；可选部分(不常用功能)平时存放在外存(覆盖文件)中，在需要时才装入内存。（需要程序员手动实现，增加编程难度）

3. 交换技术：系统根据需要把主存中暂时不运行的某个(或某些)作业部分或全部移到外存，而把外存中的某个(或某些)作业移到相应的主存区，并使其投入运行。

4. 采用页式存储管理

一个程序的大小不一定完全是块大小的整数倍，所以最后一个页面只有一部分分配给了程序，这时候仍然会有内存碎片。但是已经小了很多。

分页和分段的区别

分段：将作业的代码、数据、堆栈等进行逻辑分段
分页：直接将作业的整个空间按照块大小进行分页，不考虑各个空间的用途

1. 页是信息的物理单位，段是信息的逻辑单位
2. 页的大小是由系统固定的，段的长度因段而异，由用户决定
3. 分页的作业地址空间是一维的，分段的作业地址空间是二维的

设备管理

介绍

1. 存储设备
2. I/O 设备：输入设备、输出设备
3. 传输设备

设备管理的功能

1. 状态跟踪：设备控制块是存放设备管理和控制信息的数据结构。系统要掌握设备的状态。
2. 设备存取：实现对设备的存取操作。
3. 设备分配：在多用户的环境下，负责设备的分配和回收。
4. 设备控制：设备控制包括设备的驱动、完成和故障中断处理。

设备独立性

概念

设备独立性是指用户在编程序时所使用的设备与实际设备无关。

两类设备独立性

1. **一个程序应独立于分配给它的某类设备的具体设备。**即在用户程序中只指明 I/O 使用的设备类型即可。如在系统中配备了两台打印机，用户要打印时只要告诉系统要将信息送到打印机即可。

2. **程序要尽可能地与它使用的设备类型无关。**即在用户程序中只要指出要输入或输出信息，至于信息 I/O 使用的设备不需用户指明。

设备独立性的实现

1. 逻辑设备和物理设备的联系通常是由操作系统命令语言（作业控制语言、键盘命令或用户程序中的语言级）中提供的信息实现的。

2. 在高级语言中，通过软通道实现

3. 通过作业说明书实现设备独立性

4. 通过指派命令实现设备独立性

5. 批处理系统，用联接说明语句来定义

缓冲技术

解决 CPU 与各 I/O 设备速度不匹配，保证数据平滑传输的一项技术。

目的

1. 缓和 CPU 与 I/O 设备间速度不匹配的矛盾
2. 提高 I/O 设备传输之间的并行性
3. 减少对 CPU 的中断次数，放宽 CPU 对中 断响应时间的要求

分类

按缓冲区存储位置分类：

1. 硬缓冲：在设备中设置缓冲区，由硬件实现；
2. 软缓冲：在内存中开辟一个空间，用作缓冲区。

按管理方式分类：

1. 单缓冲
2. 双缓冲
3. 环形缓冲
4. 缓冲池：多个缓冲区连接起来统一管理，常采用多缓冲管理

虚拟分配技术(SPOOLing 技术)

又称假脱机操作。

1. 用来缓和 CPU 和外设的速度
2. 将独占设备转为共享设备

组成

硬件部分

这部分包含了在磁盘或磁鼓上设立的两区域：输入井和输出井，以及在主存中开辟出的两个缓冲区：输入缓冲区和输出缓冲区。

1. 输入井：用来存放来自于输入设备的信息。
2. 输出井：用来保存即将送到输出设备上的结果。
3. 输入缓冲区：暂时保存外设准备送入输入井的信息。
4. 输出缓冲区：暂时保存从输出井送出的结果。

软件部分

1. 在这部分中，包含了预输入进程，缓输出进程，输入井管理进程，输出井管理进程。
2. 预输入进程：将用户要求的输入数据输入到输入设备上，再经通道和输入缓冲区送入输入井。
3. 缓输出进程：将用户的输出结果在设备空闲时从输出井中，经输出缓冲区送至输入设备。
4. 输入井管理进程：将输入井中的数据读入内存。
5. 输出井管理进程：将内存中的结果送至输出井中。

原理

输入进程将用户要求的数据从输入设备传送到输入缓冲区，再存放到输入井。

当 CPU 需要输入设备时，直接从输入井读入内存。

输出进程把用户要求输入的数据从内存传送并存放到输出井，待输出设备空闲时，再将输出井中的数据经过输出缓冲区输出至输出设备上。

CPU 和外设的交换方式

1. 循环测试 I/O 方式：通过轮询来测试设备 I/O 是否完成，需要占用 CPU 绝大时间，效率低

2. I/O 中断方式：I/O 操作完成后发送中断请求信号。

3. DMA(直接存储器访问)方式：

   • 传输数据块
   • 仅在传送开始结束时，才需 CPU 干预，整块数据的传送是在 DMA 控制器的控制下完成的。

4. 通道方式:

   • 通道本质上是一个简单的处理器，专门负责输入、输出控制，具有执行 I/O 指令的能力。
   • 在通道控制方式中，CPU 只需发出启动指令，指出要求通道执行的操作和使用的 I/O 设备，该指令就可以启动通道并使该通道从内存中调出相应的通道程序执行。当数据传送结束时，通道处理器向 CPU 发送一个中断请求。
   • 进一步减少 CPU 的干预，即把对一个数据块的读(或写)为单位的干预，减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。

通道

作用

使 CPU 从 I/O 事务中解脱出来，同时为了提高 CPU 与设备，设备与设备之间的并行工作能力。

类型

1. 字节多路通道：字节多路通道以字节为单位传输信息，它可以分时地执行多个通道程序。当一台传送一个字节后，立即转去为另一台传送字节。主要连接以字节为单位的低速 I/O 设备。
2. 选择通道：选择通道每次传送一批数据，故传送速度很高。选择通道在一段时间内只能执行一个通道程序，只允许一台设备进行数据传输。主要连接磁盘，磁带等高速 I/O 设备。
3. 成组通道：它结合了选择通道传送速度高和字节多路通道能进行分时并行操作的优点。它先为一台设备执行一条通道指令，然后自动转接，为另一台设备执行一条通道指令。主要连接高速设备。

I/O 请求

为每一类设备设置一个进程，专门用于执行这类设备的 I/O 操作。
在整个系统中设置一个 I/O 进程，专门用于执行系统中所有各类设备的 I/O 操作。
不设置专门的设备处理进程，而只为各类设备设置相应的设备处理程序(模块)， 供用户进程或系统进程调用。

文件管理

文件系统的功能

1. (文件操作)提供用户对文件操作的命令；
2. (文件共享)提供用户共享文件的机制；
3. (存储器管理)管理文件的存储介质；
4. (存取控制)提供文件的存取控制的机制，保障文件及文件系统的安全性；
5. (备份恢复)提供文件及文件系统的备份和恢复功能；
6. (加密解密)提供对文件的加密和解密功能。

文件的结构

文件的逻辑结构

1. 流式文件(无结构文件)：无结构的流式文件是相关的有序字符的集合。文件的长度为所含字符数。一般文件都是流式文件。
2. 记录式文件(有结构文件,结构式文件)：结构文件是记录的集合。每个记录由彼此相关的域构成。记录可按顺序编号。

文件的物理结构

1. 连续文件：分配在物理盘的连续区域。(数组)

优点：
结构简单，实现容易，不需要额外的开销。

缺点：

1. 用户创建文件时要给出文件的大小；
2. 不利于文件的动态增加和修改；
3. 连续文件是一种连续结构的文件，对每个文件要求存放在存储介质上的连续的物理块中，存储空间利用率不高。类似于存储管理中的分区，适用于变化不大的顺序访问的文件，流行的 UNIX 系统仍保留了连续文件结构。

2. 串联文件：一个串联文件结构是按顺序由串联的块组成的，即文件的信息按存储介质的物理特性存于若干块中。每个物理块的最末一个字(或第一个字)作为链接字，它指出后继块的物理地址。(链表)

优点：

1. 存储空间利用率高；
2. 文件创建时用户不必指出文件的大小；
3. 文件动态扩充和修改容易。
4. 顺序存取效率高。

缺点：

1. 随机存取效率太低，如果访问文件的最后内容，实际上是要访问整个文件。
2. 指针域需额外占用空间；
3. 指针与数据同时存放，破坏了物理块的完整性。

3. 文件映照：把串联文件的指针域集中到一个表中。例如 FAT。

缺点：

1. 不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在 FAT 中顺序地查找许多盘块号。
2. FAT 需占用较大的内存空间。

4. 随机文件：文件数据存放的存储介质上的物理块号与文件的逻辑块号一一对应，并建立这样对应关系的数据结构－－文件索引表。通过索引来访问文件。包含直接地址结构、计算寻址结构(散列文件)和索引结构。

直接地址结构：直接通过某一给定的记录地址，直接对记录存取。

• 优点：存储效率高，不需要进行任何查找；
• 缺点：知道记录所在地址较困难。

索引文件结构：分索引区和数据区

• 优点：可直接读写记录，便于文件的增删
• 缺点：增加了索引表的空间开销及查找时间

计算寻址结构：利用一个简单宜于实现的变换函数（HASH 函数），把每个符号名唯一的变换成表中的表目位置

空间管理

空闲文件项
把每个空闲区看成一个文件，并登记在文件目录中，目录中各表目按文件起始地址从小到大排列。

空闲文件目录

系统为所有空闲文件单独建立一个目录，而每个空闲文件在这个目录中均有一个表目。表目的内容包括第一个空闲块的地址（物理块号）和空闲块的个数。

分配：当某用户提出请求分配存储空间时，系统依次扫描该空白文件目录的各表目，直到找到一个满足要求的空白文件为止。

释放：当用户删除一个文件时，系统收回其文件空间。这时也要扫描空白文件目录，找出一个空表将其释放空间的第一个物理块号及占用的块号数填入该表目中。

空闲块链

记住存储空间分配情况的另一种办法是把所有“空闲块”链在一起。

当创建文件需要一块或几块时，就从链头上依次取下一块或几块。反之，当回收空间时，把这些空闲块依次接到链头上。

位示图

位示图是外存空间的存储映射图。位示图是系统在内存中划分出的若干字节的集合，用来指示磁盘存储情况。

文件目录

概念

文件目录也被称为文件说明或文件控制块（File Control Block，FCB）即文件名址录。它是一张记录所有文件名及其存放地址、文件的说明和控制信息的表格。

作用

1. 实现“按名存取”。
2. 提高对目录的检索速度。
3. 文件共享。
4. 允许文件重名。

文件共享和保护

文件共享

1. 绕道法：建立当前目录
2. 链接技术：
3. 基本文件目录
4. 符号链接
5. 索引节点

文件保护

1. 访问控制矩阵
2. 存取控制表
3. 用户权限表
4. 隐藏文件目录
5. 口令：使用前输入口令
6. 密码：写入时加密

文件操作

文件备份

1. 全量转储
2. 增量转储

计算题

进程同步规则计算题

同步规则：

1. 空闲让进：当没有进程处于临界区时，可以允许一个请求进入临界区的进程立即进入自己的临界区。
2. 忙则等待：当已有进程进入其临界区时，其他试图进入临界区的进程必须等待。
3. 有限等待：对要求访问临界资源的进程，应该保证能在有限时间内进入自己的临界区。
4. 让权等待：当进程不能进入自己的临界区时，应释放处理机。

• 进程标志位实现进程同步1
• 进程标志位实现进程同步2

int flag [2] = {0,0};
  …
Pi:
  while(1)
  {
    …
    while(flag[1-i])
      no-op;
		flag[i]=true;
    进程Pi的临界段代码CSi;
    flag[i]=false;
    进程Pi的其它代码;
    …
  }

其中：

• p1 和 p2 并发执行，pi 表示pi 的程序段
• flag[i]= true 进程i在临界段中执行；
• flag[i]= false 进程i不在临界段中执行。

当 p1 和 p2 对应的 flag 都是 false 时，两个程序都可以进入，违背了 忙则等待的原则。

int flag [2] = {0,0};
…
Pi:
  while(1)
  {
    …
    flag[i]=true;
    while(flag[1- i])
      no-op;
		进程Pi的临界段代码CSi;
    flag[i] =false;
    进程Pi的其它代码;
    …
  }

• p1 和 p2 并发执行，pi 表示pi 的程序段
• flag[i]=true 进程 i 想进入临界段中

当两个进程同时设置 flag[i]=true 时，发现对方也设置了 flag 为 true，然后两个进程都互相等待，无法执行，违背了空闲让进的原则。

PV 操作计算题

合作进程的同步次序

根据每条路径的前导路径来确定执行次序。

• 例题

信号量的个数：

$P_1$ 没有前导路径。不需要信号量。
$P_2$ 的前导路径为$P_1$。需要 1 个信号量。
$P_3$ 的前导路径为$P_1$。需要 1 个信号量。
$P_4$ 的前导路径为$P_1$。需要 1 个信号量。
$P_5$ 的前导路径为$P_2$。需要 1 个信号量。
$P_6$ 的前导路径为$P_3,P_5$。需要 2 个信号量。
$P_7$ 的前导路径为$P_4,P_6$。需要 2 个信号量

一共需要 10 个信号量。

1. 确定同步规则

$P_1$ 完，$P_2、P_3、P_4$ 才能开始；
$P_2$ 完，$P_5$ 才能开始；
$P_3$、$P_5$ 完，$P_6$ 才能开始；
$P_4$、$P_6$ 完，$P_7$ 才能开始；
$P_7$ 完，任务结束。

2. 确定信号量

S2 ～ S5：P2 ～ P5 能否开始；
S56：P5 完成后，P6 能否开始；
S36：P3 完成后，P6 能否开始；
S47：P4 完成后，P7 能否开始；
S67：P6 完成后，P7 能否开始；

• main
• P1
• P2
• P3
• P4
• P5
• P6
• P7

main()
{
  int s2=0;
  int s3=0;
  ...
  cobegin
    P1()；
    P2()；
  ...
  coend
}

P1()
{
  …
  V(S2);
  V(S3);
  V(S4);
}

P2()
{
  P(S2);
  …
  V(S5);
}

P3()
{
  P(S3);
  …
  V(S36);
}

P4()
{
  P(S4);
  …
  V(S47);
}

P5()
{
  P(S5)；
  …
  V(S56);
}

P6()
{
  P(S36);
  P(S56);
  …
  V(S67);
}

P7()
{
  P(S47);
  P(S67);
  …
}

生产者-消费者问题

• 生产者进程：不断生产数据到临界资源
• 消费者进程：不断从临界资源中读取数据

设临界资源的大小为$n$，那么需要设置 3 个信号量：

• $empty$: 最大值为$n$,初值为$n$。临界资源的剩余空间。
• $full$: 最大值为$n$,初值为$0$。临界资源的已用空间。
• $mutex$：最大值为$1$ ，初值为$0$。因为只能有一个进程读取或修改临界资源

• 生产者进程
• 消费者进程

同步规则：

1. 只有临界资源未满($empty$>0)，才能继续操作
2. 只有临界资源未被访问时，才能继续操作

void producer()
{
      while(1)
      {
            wait (empty);
            wait (mutex);
            操作资源
            signal (mutex);
            signal (full);
       }
}

同步规则：

1. 只有临界资源放了资源$full>0$，才能继续操作
2. 只有临界资源未被访问时，才能继续操作

void consumer()
{
      while(1)
      {
            wait (full);
            wait (mutex);
            操作资源;
            signal (mutex);
            signal (empty);
       }
}

死锁避免计算题

死锁证明

若系统中有$m$ 个某类资源，共有$n$ 个进程。每个进程需要$K$ 个资源，当

$$m \ge n \times (k-1)$$

时，系统不会发生死锁。

证明方法：每个均分$k-1$个资源，若还有剩余资源分配给 1 个程序，就不会发生死锁。

在最坏的情况下,每个进程都得到了$k-1$个资源 i 并且都需申请最后一个资源。
这时系统剩余资源数为:$m-n(k-1)$。

只要系统还有一个资源可用,就可使其中的一个进程获得所需的全部资源。该进程运行结束后释放出它所占用的资源,其它进程的资源需求也可得到全部满足。

因此,当$m-n(k-1) \geq 1$ 时,即$k\leq (m+n-1)/n$ 时系统不会发生死锁。

银行家算法

数据结构

1. 可利用资源向量 Available$j$
2. 分配矩阵 Allocation$i \times j$
3. 需求矩阵 Need$Need(i,j)=Max(i,j)-Allocation(i,j)$
4. 最大需求矩阵 Max$i \times j$

寻找安全序列

1. 设置工作向量： Work=Available
2. 从所有进程中寻找一个未执行过，且可以分配资源的进程$i$$Need(i,j) \leq Work(j)$
3. 假装执行这个进程，并释放所有资源。$Work(j)∶=Work(i)+Allocation(i,j)$
4. 如果所有进程都可以正常执行并释放资源，那么进程执行的顺序就是安全序列。

银行家算法

1. 检查异常：

   • 请求资源$Request(i)$是否超过可用资源$Available$
   • 请求资源$Request(i)$是否超过所需的最大值$Need(i)$

2. 尝试分配资源

3. 分配后，寻找安全序列，如果能找到，说明申请的序列是安全的。

处理机调度计算题

1. 理解作业调度：将已经到达的作业按照一定次序调入内存
2. 理解进程调度：从内存中所有就绪的作业选择一个出来执行

作业调度

五种调度策略

1. 先来先服务(FCFS,FIFO)：按作业到来的先后次序进行调度。
2. 短作业优先(SJF)：每次选择运行时间最短的作业进行调度。
3. 响应比高者优先调度算法(HRRN):每次选择响应比高的作业进行调度。

$\text{响应比}=1+\frac{等待时间}{运行时间}$

4. 优先数调度算法:给每个作业选择一个合适的优先数。
5. 均衡调度算法:按作业本身的特性分类，作业调度程序轮流从这些不同类的作业中挑选作业运行。

进程调度

两种方式

1. 非剥夺方式，非抢占方式：进程一旦执行，就只能等待其完成或阻塞。
2. 剥夺方式，抢占方式：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。

五种调度策略

1. 先来先服务(FIFO,FCFS)调度算法：按照进程进入就绪队列的先后顺序，一旦运行就一直占用处理机(不可抢占)
2. 最短 CPU 运行期优先调度算法：从就绪队列中选出“下一个 CPU 执行期” 最短的进程，为之分配处理机使之运行。（不可抢占）
3. 最短剩余时间优先调度算法：让运行到作业完成时所需运行时间最短的进程优先得到处理，包括新进入系统的进程。（可抢占）
4. 进程优先数调度算法：每个进程赋予优先数，按照优先级次序进行调度。
5. 循环轮转调度：所有的就绪进程按照 FCFS 原则，排成一个队列。每个程序每次执行一个时间片，时间片用完后进入队尾。（不考虑优先级）

• 进程调度例题

有 5 个任务 A,B,C,D,E,它们几乎同时到达,预计它们的运行时间为 10,6,2,4,8min。其优先级分别为 3,5,2,1 和 4,这里 5 为最高优先级。对于下列每一种调度算法,计算其平均进程周转时间(进程切换开销可不考虑)。

1. 先来先服务(按 A,B,C,D,E)算法。
2. 优先级调度算法。
3. 时间片轮转算法。

解

(1)采用 FCFS 的调度算法时,各任务在系统中的执行情况如下表所示:

执行次序	运行时间	优先数	等待时间	周转时间
A	10	3	0	10
B	6	5	10	16
C	2	2	16	18
D	4	1	18	22
E	8	4	22	30

所以,进程的平均周转时间为:T=(10+16+18+22+3O)/5=19.2 min

(2)采用优先级调度算法时,各任务在系统中的执行情况如下表所示:

执行次序	运行时间	优先数	等待时间	周转时间
B	6	5	0	6
E	8	4	6	14
A	10	3	14	24
C	2	2	24	26
D	1	1	26	27

所以,进程的平均周转时间为: T=(6+14+24+26+27)/5=19.4 min

(3)采用时间片轮转算法时,假定时间片为 2min,各任务的执行情况是:(A,B,C,D,E),(A,B,D,E),(A,B,E),(A,E),(A)。设 A ～ E 五个进程的周转时间依次为 T1 ～ T5,显然,T1=3Omin, T2=22min, T3=6min,T4=16min,T5=28min

所以,进程的平均周转时间为:T=(30+22+6+16+28)/5=20.4min

混合调度

• 混合调度例题

在一个四道作业的操作系统中，设在一段时间内先后到达 6 个作业，它们的提交时刻和运行时间由下表给出。

作业号	提交时刻（时）	运行时间（分钟）
JOB1	8:00	60
JOB2	8:20	35
JOB3	8:25	20
JOB4	8:30	25
JOB5	8:35	5
JOB6	8:40	10

系统采用短作业优先的调动算法，作业被调度进入运行后不再退出，但每当一作业进入运行时，可以调整运行的优先次序。

1. 按照所选择的调度算法，请分别给出上述 6 个作业的执行实间序列。
2. 计算在上述调度算法下作业的平均周转时间。

注意

1. 4 道程序的意思是，内存中最多可以放 4 个程序。如果内存占满，则无法添加新程序。
2. 可以调整运行的优先次序的意思是，调度是抢占式的。

题解

作业号	运行时间段	周转时间
JOB1	8:00-8:20,9:55-10:35	155
JOB2	8:20-8:25,9:25-9:55	95
JOB3	8:25-8:30,8:30-8:45	20
JOB4	9:00-9:25	55
JOB5	8:45-8:50	15
JOB6	8:50-9:00	20

平均周转时间：60 分钟

1. $8:20$ JOB2 进入内存，且运行时间比 JOB1 短，JOB2 优先执行
2. $8:25$ JOB3 进入内存，且运行时间比 JOB1,JOB2 短，JOB3 优先执行
3. $8:30$ JOB4 进入内存，但 JOB3 运行时间最短，JOB3 优先执行
4. $8:35$ 内存已满，JOB5 无法进入
5. $8:40$ 内存已满,JOB6 无法进入
6. $8:45$ JOB3 执行完，JOB5 运行时间最短，进入内存，且 JOB5 先执行
7. $8:50$ JOB5 执行完，JOB6 进入内存，由于 JOB6 运行时间最短，JOB6 先执行
8. $9:00$ JOB6 执行完毕，此时内存中 JOB4 运行时间最短，JOB4 执行
9. $9:25$ JOB4 执行完毕，此时内存中 JOB2 运行时间最短，JOB2 执行
10. $9:55$ JOB2 执行完毕，JOB1 执行

主存管理计算题

地址转换计算

情况 1 若虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出

1. 将虚地址转换成二进制的数；
2. 按页的大小分离出页号和位移量（低位部分是位移量，高位部分是页号）；
3. 根据题意产生页表；
4. 将位移量直接复制到内存地址寄存器的低位部分；
5. 以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。

情况 2 虚地址以十进制数给出

1. 页号＝虚地址/页大小
2. 位移量＝虚地址 mod 页大小
3. 根据题意产生页表；
4. 以页号查页表，得到对应页装入内存的块号
5. 内存地址＝块号 × 页大小＋位移量

• 例题1

有一系统采用页式存储管理，有一作业大小是 8KB，页大小为 2KB，依次装入内存的第 7、9、A、5 块，试将虚地址 0AFEH，7145 转换成内存地址。

1. 虚地址 0AFEH

0000 1010 1111 1110
P ＝ 1 W ＝ 010 1111 1110
MR ＝ 0100 1010 1111 1110 ＝ 4AFEH

2. 虚地址 7145

P ＝ 7145 / 2048 ＝ 3
W ＝ 7145 mod 2048 ＝ 1001
MR=5*2048+1001=11241
虚地址 7145 的内存地址是：11241

计算缺页中断

1. 先进先出(FIFO):淘汰最早进入队列的页。
2. 最久未使用淘汰算法(LRU):淘汰最长时间未使用的页。
3. 最不经常使用淘汰算法(LFU):淘汰最近访问次数最少的页。

• 例题

在一个请求分页管理中,一个程序的页面走向为 4,3,2,1,4,3,5,4,3,2,1,5。

若采用 LRU 算法：

时间	1	2	3	4	5	6	7	8	9	10	11	12
地址	4	3	2	1	4	3	5	4	3	2	1	5
队尾	4	3	2	1	4	3	5	4	3	2	1	5
		4	3	2	1	4	3	5	4	3	2	1
			4	3	2	1	4	3	5	4	3	2
队头				4	3	2	1	1	1	5	4	3
中断	+	+	+	+			+			+	+	+

缺页中断次数为 8 次。

注意：

• 这是一个优先级队列，按照上次访问的时间进行排序
• 初始时没有对应页的存储块，一定会发生缺页中断
• 注意 7、10、11、12 处的队列变化

文件管理计算题

索引结构

每个文件有一个文件控制块。

1. 块数：$\frac{总空间}{磁盘块空间}=\frac{索引表空间}{索引表一项占用的空间}$，占用位数则对其取对数即可。
2. 文件占用的空间：$\text{块数} \times \text{磁盘块空间}$

• 例1
• 例2

某文件系统空间的最大容量为 4TB（$1T=2^{40}$），以磁盘块为基本分配单位，磁盘块大小为 1KB。文件控制块（FCB）包含一个 512B 的索引表区。请回答下列问题：

1. 假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？
2. 假设索引表区采用如下结构：第 0~7 字节采用 <起始块号，块数> 格式表示文件创建时预分配的连续存储空间，其中起始块号占 6B，块数占 2B；剩余 504 字节采用直接索引结构，一个索引项占 6B，则可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。

解

1. 该文件系统空间总的盘块数为$4TB/1KB=4G=2^{32}$个，因此索引表项中块号最少占 32/8=4 字节。

由于索引表区可存放的盘块号最多为 512B/4B=128 个，因此可支持的单个文件最大长度是$128 \times 1KB=128KB$ 。

2. 由于<起始块号，块数> 格式中，块数占 2B，因此为文件预分配的连续存储空间最大为$2^{16} \times 1KB=64MB$。

直接索引结构部分支持的文件最大长度为$（504B/6B）\times 1KB=84KB$。

综上该地址结构可支持的单个文件最大长度是$64MB+84KB=65620KB$。

起始块号和块数分别所占字节数的合理值是 <4, 4> ，块号占 4B 正好可以表示 232 个盘块，块数占 4B 支持的文件最大长度是$2^{32} \times 1KB=4TB$，正好可以达到文件系统空间的最大容量。

一个 UNIX 系统使用 2KB 磁盘块和 4 字节磁盘地址。如果每个 inode 节点中有 10 个直接地址、1 个一次间接地址、1 个二次间接地址和 1 个三次间接地址,那么文件的最大尺寸是多少?

解

系统使用$2KB$磁盘块,磁盘地址使用$4$个字节，因此一个磁盘块可以存放$512$ 个地址。

文件的最大尺寸$(10+512+512 \times 512+512 \times 512 \times 512) \times 2KB$，约为 256GB。

磁盘访问次数

位示图

位示图是外存空间的存储映射图,是系统在内存中划分出的若干字节的集合，用来指示磁盘存储情况。位示图中的每一位（bit）对应外存空间的一个物理块。

• 若该位为 1，表示对应块被占用
• 若该位为 0，表示对应物理块空闲

理解磁盘的结构：https://blog.csdn.net/weixin_37641832/article/details/103217311

对于磁盘来说，$(柱面,磁道,扇区)$ 可以确定一个磁盘块。

对于位示图来说，$(块号)$ 或者$(字号,位号)$ 可以确定位示图的某一位。

磁盘和位示图对于的转换关系：

1. 磁盘$(柱面,磁道,扇区)$->位示图$(块号),(字号,位号)$

   • $块号=柱面号 \times 单个柱面的磁道数 \times 单个磁道的扇区数 + 磁道号 \times 单个磁道的扇区数 + 扇区号$
   • $字号=块号/字长$
   • $位号=块号 \mod 字长$

2. 位示图$(块号),(字号,位号)$->磁盘$(柱面,磁道,扇区)$

   • $柱面号=块号 / (单个柱面的磁道数 \times 单个磁道的扇区数)$
   • $磁道号=(块号 \mod \times 单个柱面的磁道数 \times 单个磁道的扇区数)/ 单个磁道的扇区数$
   • $扇区号=(块号\mod (单个柱面的磁道数 \times 单个磁道的扇区数)) \mod 单个磁道的扇区数$