操作系统第一章：初试操作系统

操作系统的概念，功能和目标

1. 负责管理协调硬件、软件等计算机资源的工作
2. 为上层的应用程序、用户提供简单易用的服务
3. 操作系统是系统软件，而不是硬件

操作系统（Operating System，OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境，它是计算机系统中最基本的系统软件。

①操作系统作为系统资源的管理者（这些资源包括软件、硬件、文件等)，需要提供什么功能?

用QQ和朋友视频聊天的过程:
Step 1:在各个文件夹中找到QQ安装的位置（如D:/Tencent/QQ/bin）逐层打开文件夹，找到QQ.exe这个程序（可执行文件）的存
放位置， 文件管理

Step 2:双击打开QQ.exe 需要把改程序相关数据放入内存 存储器管理

Step 3: QQ程序正常运行 对应的进程被处理机（CPU）处理 处理机管理

Step 4:开始和朋友视频聊天 需要将摄像头设备分配给进程 设备管理

②操作系统作为用户与计算机硬件之间的接口，要为其上层的用户、应用程序提供简单易用的服务，需要实现什么功能?

命令接口:允许用户直接使用

1. 联机命令接口：用户说一句，系统做一句， 交互式 命令接口
2. 脱机命令接口：用户说一堆，系统做一堆，批处理 命令接口

程序接口:允许用户通过程序间接使用 ：由一组系统调用组成（程序接口 = 系统调用）只能通过用户程序间接使用， 系统调用 = 系统调用命令 = 广义指令

GUI:现代操作系统中最流行的图形用户接口

所有提供给用户的接口可以统称为用户接口

③操作系统作为最接近硬件的层次，需要在纯硬件的基础上实现什么功能?

需要提供的功能和目标:实现对硬件机器的拓展

没有任何软件支持的计算机成为裸机。在裸机上安装的操作系统,可以提供资源管理功能和方便用户的服务功能，将裸机改造成功能更强、使用更方便的机器

通常把覆盖了软件的机器成为扩充机器，又称之为虚拟机

操作系统的特征

操作系统的特征包括并发，共享，虚拟，异步 这四个特征，其中 并发和共享是两个最基本的特征，二者互为存在条件

其中并发： 指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的 ，但微观上是交替发生的 。常考易混概念一一并行:指两个或多个事件在同一时刻同时发生。

一个单核处理器（CPU）同一时刻只能执行一个程序，因此操作系统会负责协调多个程序交替执行（这些程序微观上是交替执行的，但是在宏观上是同时执行的）

事实上，操作系统是伴随着“多道程序技术”而出现的。因此操作系统和程序并发是一起出现的

当今的计算机，一般都是多核CPU，比如Intel的第八代i3处理器就是4核CPU这意味着同一时刻可以有4个程序并行 执行，但是操作系统的并发性依然必不可少 当代人使用计算机绝对有4个以上的程序需要同时工作。

两种资源共享方式：

1
2
3

系统中的某些资源，虽然可以提供个多个进程使用。但是一个时间段内只允许一个进程访问该资源 

例子：使用QQ和微信进行视频的时候，同一时间段内摄像头只能分配给其中一个进程

1
2
3
4
5

系统中的某些资源，{%label 允许一个时间段内由多个进程“同时”对他进行访问 red %}

所谓的“同时”往往是宏观上的，而在微观上，这些进程可能是交替的对该资源进行访问（即分时共享）

同时共享方式:使用QQ发送文件A，同时使用微信发送文件B。宏观上看，两边都在同时读取并发送文件,说明两个进程都在访问硬盘资源，从中读取数据。微观上看，两个进程是交替着访问硬盘的。

通过上述例子来看并发与共享的关系:

使用QQ发送文件A，同时使用微信发送文件B。

1
2

两个进程正在并发执行
如果失去并发性，则系统中只有一个程序正在运行，则共享性失去存在的意义，共享性就是让多个进程“同时”对它进行访问，但是如果失去并发性的话，又何来多个进程同时存在哪

1
2

需要共享地访问硬盘资源
如果失去共享性，则QQ和微信不能同时访问硬盘资源，就无法实现同时发送文件，也就无法并发，既然不能同时访问这个文件，那么同一时间只能有一个进程在运作，所以也就有了并发性

这里说明虚拟 是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的，而逻辑上对应物（后者）是用户感受到的。例如一个单核CPU可以同时开很多个文件，这给我们的感觉就是看起来是有多个CPU同时在为我进行服务，这时候就用到了虚拟技术虚拟技术中的“时分复用技术”。微观上处理机在各个微小的时间段内交替着为各个进程服务

显然，如果失去了并发性，则一个时间段内系统中只需运行一道程序，那么就失去了实现虚拟性的意义了因此，没有并发性，就谈不上虚拟性 。

其中异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的,而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

显然，如果失去了异步性，则系统只能串行地处理各个进程，每个进程的执行会一贯到底。只有系统拥有并发性，才有可能导以异步性 .

操作系统的发展和分类

手工操作阶段，每一个程序员都需要把自己写的程序用二进制写在纸带上，然后通过纸带机传递给计算机，等待计算机运算完毕之后，再由纸带机将纸带返回回来，纸带上的二进制就是计算机计算完之后的结果

手工操作阶段：

为什么多道批处理系统能使资源利用率大幅度提升？

假设计算机需要处理三个作业

作业一:输入1秒，计算1秒，输出1秒

作业二:输入1秒，计算1秒，输出1秒

作业三:输入1秒，计算1秒，输出1秒

分时操作系统:计算机以时间片 为单位轮流为各个用户/作业服务 ，各个用户可通过终端与计算机进行交互。

主要优点:用户请求可以被即时响应，解决了人机交互问题 。 允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。

主要缺点:不能优先处理一些紧急任务 。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不区分任务的紧急性。

实时操作系统:

主要优点：能够优先响应一些紧急任务，某些紧急任务不需时间片排队。

在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性

网络操作系统:是伴随着计算机网络的发展而诞生的，能把网络中各个计算机有机地结合起来，实现数据传送等功能，实现网络中各种资源的共享(如文件共享〉和各台计算机之间的通信 。(如: Windows NT就是一种典型的网络操作系统，网站服务器就可以使用)

分布式操作系统:主要特点是分布性和并行性。系统中的各台计算机地位相同，任何工作都可以分布在这些计算机上，由它们并行、协同完成这个任务。

个人计算机操作系统:如 Windows XP、MacOs，方便个人使用。

操作系统的运行机制和体系结构

什么是指令？指令和我们平时所接触的代码有什么区别

C语言代码 需要翻译为机器指令 然后CPU才能看懂

简单来说，“指令”就是处理器（CPU)能识别、执行的最基本命令比如:加法指令就是让CPU进行加法运算

指令分为两种：

1
2
3

不允许用户程序使用例如内存清零指令

如果用户程序可以使用这个指令，就意味着一个用户可以将其他用户的内存数据随意清零，这样做显然是很危险的。

1

如普通的运算指令，能够让用户使用

CPU如何判断当前是否可以执行特权指令

这就引出CPU两种处理状态

用程序状态字寄存器（PSW）中的某标志位来标识当前处理器处于什么状
态。如0为用户态，1为核心态

1

当CPU处于这种形态的时候，表明CPU这时候只能执行非特权指令

1

当CPU处于这种形态的时候，表明CPU这时候特权指令和非特权指令都可以执行

有些程序需要执行特权指令，有些程序需要执行非特权指令，这时候程序就分为两种形态

1

操作系统的内核程序是系统的管理者,既可以执行特权指令，也可以执行非特权指令，运行在核心态。

1

为了保证系统能安全运行，普通应用程序只能执行非特权指令，运行在用户态

操作系统中那些功能应该由内核程序实现呢？

1. 时钟管理： 实现计算机的计时功能，所有的进程切换和进程调度都需要使用时钟管理来辅助实现
2. 源语： 原语是一种特殊的程序。是最接近硬件的部分，这种程序的运行具有原子性。
3. 内核 是计算机上配置的底层软件 ，是操作系统最基本、最核心的部分。

实现操作系统内核功能的那些程序就是内核程序。

• 内核 ： 分为大内核和微内核， 大内核其中包含了对系统资源管理的功能， 而微内核中只有时钟管理，中断管理和原语

操作系统的体系结构问题与企业的管理问题很相似。

• 内核就是企业的管理层，负责一些重要的工作。只有管理层才能执行特权指令，普通员工只能执行非特权指令。用户态、核心态之间的切换相当于普通员工和管理层之间的工作交接。

1. 大内核：企业初创时体量不大，管理层的人会负责大部分的事情。优点是效率高;缺点是组织结构混乱，难以维护。
2. 微内核 ：随着企业体量越来越大，管理层只负责最核心的一些工作。优点是组织结构清晰，方便维护;缺点是效率低。

中断和异常

早期的计算机，在接受一堆指令的时候，等待指令处理完之后，必须经过IO处理完成之后才能彻底离开处理器。

• 缺点：各个程序只能串行的执行，系统资源利用率低

为了解决上述问题，人们发明了操作系统（作为计算机的管理者），引入中断机制，实现了多道程序并发执行

• 本质:发生中断就意味着需要操作系统介入，开展管理工作。

1. 当中断发生时，CPU立即进入核心态。
2. 当中断发生后，当前运行的进程暂停运行，并由操作系统内核对中断进行处理
3. 对于不同的中断信号，会进行不同的处理

发生了中断，就意味着需要操作系统介入，开展管理工作。由于操作系统的管理工作（比如进程切换、分配I/O设备等）需要使用特权指令，因此CPU要从用户态转为核心态。中断 可以使CPU从用户态切换为核心态，使操作系统获得计算机的控制权。有了中断，才能实现多道程序并发执行。

问：用户态、核心态之间的切换是怎么实现的?
答:"用户态→核心态 "是通过中断实现的。并且中断是唯一途径。“核心态→用户态 ”的切换是通过执行一个特权指令，将程序状态字(PsW)）的标志位设置为“用户态”

Step 1:执行完每个指令之后，CPU都要检查当前是否有外部中断信号

Step 2:如果检测到外部中断信号，则需要保护被中断进程的CPU环境（如程序状态字PSw、程序计数器PC、各种通用寄存器)

Step 3:根据中断信号类型转入相应的中断处理程序

Step 4:恢复原进程的CPU环境并退出中断，返回原进程继续往下执行

系统调用

操作系统作为用户和计算机硬件之间的接口，需要向上提供一些简单易用的服务。主要包括命令接口和程序接口。其中，程序接口由一组系统调用组成。

“系统调用”是操作系统提供给应用程序（程序员/编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以发出系统调用请求来获得操作系统的服务。

应用程序通过系统调用请求操作系统的服务。系统中的各种共享资源都由操作系统统一掌管，因此在用户程序中，凡是与资源有关的操作（如存储分配、I/O操作、文件管理等），都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。

系统调用相关处理涉及到对系统资源的管理、对进程的控制,这些功能需要执行一些特权指令 才能完成，因此系统调用 的相关处理需要在核心态 下进行

不涉及系统调用的库函数:如的“取绝对值”的函数

涉及系统调用的库函数:如“创建一个新文件”的函数

传递系统调用参数→执行陷入指令（用户态 ）→执行系统调用相应服务程序（核心态）→返回用户程序

注意:

1. 陷入指令 是在用户态执行的，执行陷入指令之后立即引发一个内中断，从而CPU进入核心态。
2. 发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行
3. 陷入指令是唯一一个只能在用户态执行，而不可在核心态执行的指令

操作系统第二章：进程管理

进程的定义，组成，组成方式，特征

• 程序 :就是一个指令序列

• 早期的计算机（只支持单道程序），就是每一次只能进行一个程序

  内存中同一个时间段内只有一个程序在运行，所以程序的程序段和数据段可以放在固定的位置

  程序的代码放在程序段内，程序运行过程处理的数据放在数据段内（如变量)

  

• 引入多通道技术之后：

  内存中同时放入多道程序，各个程序的代码、运算数据存放的位置不同。操作系统要怎么才能找
  到各程序的存放位置呢?

  为了方便操作系统管理，完成各程序并发执行，引入了进程、进程实体的概念

  系统为每个运行的程序配置一个数据结构，称为进程控制块（PCB），用来描述进程的各种信息（如程
  序代码存放位置)

  

注意: PCB是进程存在的唯一标志!

从不同的角度，进程可以有不同的定义，比较传统典型的定义有:(强调动态性)

1. 进程是程序的一次执行过程。

2. 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。

3. 进程是具有独立功能的程序在数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

引入进程实体的概念后，可把进程定义为:

注:严格来说，进程实体和进程并不一样，进程实体是静态的，进程则是动态的。不过，除非题目专门考察二者区别，否则可以认为进程实体就是进程。因此我们也可以说“进程由程序段、数据段、PCB三部分组成”

进程（进程实体）由程序段、数据段、PCB三部分组成。

• PCD ： 操作系统通过PCB来管理进程,因此PCB中应该包含操作系统对其进行管理所需的各种信息。
• 程序段 ：程序代码即存放在此
• 数据段 ：程序运行时使用、产生的运算数据。如全局变量、局部变量、宏定义的常量就存放在数据段内

在一个系统中，通常有数十、数百乃至数千个PCB。为了能对他们加以有效的管理，应该用适当的方式把这些PCB组织起来。

注:进程的组成 讨论的是一个进程内部 由哪些部分构成的问题，而进程的组织讨论的是多个进程之间的组织方式问题

进程和特征具有两个截然不同的概念，相对于程序，进程有以下特征

进程的状态

进程是程序的一次执行。在这个执行过程中，有时进程正在被CPU处理，有时又需要等待CPU服务，可见进程的状态是会有各种变化。为了方便对各个进程的管理，操作系统需要将进程合理地划分为几种状态。

进程的三种基本状态：

• 运行态（Runing） :单核处理机环境下,每一时刻最系只有一个进程处于运行态。（双核环境下可以同时有两个进程处于运行态）
• 就绪态（Ready） ：进程已经有了除了处理机外所有需要的资源，一旦获得处理机即可立即进入运行态开始运行，即：万事具备，只欠CPU
• 阻塞态 ：如:等待操作系统分配打印机、等待读磁盘操作的结果。CPU是计算机中最昂贵的部件，为了提高CPU的利用率，需要先将其他进程需要的资源分配到位，才能得到CPU的服务

另外两种状态：

• 创建态 (New，又称:新建态)进程正在被创建，操作系统为进程分配资源、初始化PCB
• 终止态（Terminated，又称:结束态)进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB

进程控制

进程控制的主要工能是对系统中所有进程实施有效的管理，它具有创建新进程，撤销已有进程，实现进程状态转变等功能。

简化理解：进程控制就是要实现进程状态的转换

用原语 实现进程控制。原语的特点 是执行期间不允许中断，只能一气呵成。这种不可被中断的操作即原子操作。

原语采用“关中断 指令”和“开中断指令”实现

显然，关/开中断指令的权限非常大，必然是只允许在核心态下执行的特权指令。

学习技巧:进程控制会导致进程状态的转换。无论哪个原语，要做的无非三类事情:

1. 更新PCB中的信息（如修改进程状态标志、将运行环境保存到PCB、从PCB恢复运行环境)
   • 所有的进程控制原语一定都会修改进程状态标志
   • 剥夺当前运行进程的CPU使用权必然需要保存其运行环境
   • 某进程开始运行前必然要恢复期运行环境
2. 将PCB插入合适的队列
3. 分配/回收资源

进程通信

顾名思义：进程通讯就是指进程之间的信息交换。

进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立

为了保证进程的安全，一个进程不能直接访问另一个进程的地址空间。

但是进程之间的信息交换又是必须要实现的。为了保证进程之间的安全通信，操作系统提供了一些方法

进程通讯分为三种：

共享存储， 消息传递， 管道通信

线程概念多线程模型

在没有进程之前，CPU一次只能为一个程序进行服务，引入进程之后CPU可以一次性为多个进程进行服务。

例如原先玩QQ和听音乐只能选择其中一个运行，但是引入进程之后，我们就可以边听音乐，边玩QQ。

但是QQ有许多功能，例如视频聊天，文字聊天，如果让一个进程同时进行不同的功能呢，这时候就需要引入线程

可以把线程理解为“轻量级进程”

• 线程是一个基本的CPU执行单元，也是程序执行流的最小单位。
• 引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件)
• 引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的)

• 线程是处理机调度的单位
• 多CPU计算机中，各个线程可占用不同的CPU
• 每个线程都有一个线程ID、线程控制块（TCB)
• 线程也有就绪、阻塞、运行三种基本状态
• 线程几乎不拥有系统资源
• 同一进程的不同线程间共享进程的资源
• 由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
• 同一进程中的线程切换，不会引起进程切换
• 不同进程中的线程切换，会引起进程切换
• 切换同进程内的线程，系统开销很小
• 切换进程，系统开销较大

在同时支持用户级线程和内核级线程的系统中，可采用二者组合的方式:将n个用户级线程映射到m个内核级线程上( n >= m)

操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。

例如:下边这个模型中，该进程由两个内核级线程，三个用户级线程，在用户看来，这个进程中有三个线程。但即使该进程在一个4核处理机的计算机上运行，也最多只能被分配到两个核，最多只能有两个用户线程并行执行。

处理机调度的概念，层次

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则 来决定 处理这些任务的顺序 ，这就是“调度”研究的问题。

在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。

• 处理机的调度 ：从就绪队列中按照一定的算法选择一个进程 并将处理机分配给它 运行，以实现进程的并发执行。

进程调度的时机，切换与过程，方式

• 进程调度 (低级调度)，按照某种算法从就绪队列中选择一个进程为其分配处理机

需要进行进程调度和切换的情况

• 当前运行的进程主动放弃处理机
  • 进程正常终止
  • 运行过程中发生异常而终止
  • 进程主动请求阻塞（如等待I/O)
• 当前运行的进程被动放弃处理机
  • 分给进程的时间片用完
  • 有更紧急的事需要处理（如I/O中断)
  • 有更高优先级的进程进入就绪队列

不能进行进程调度和切换的情况

• 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
• 进程在操作系统内核程序临界区中。
• 在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列)

临界资源:一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。

临界区:访问临界资源的那段代码。

• 内核程序临界区 一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的PCB组成)
• 当一个程序处于内核程序临界区时：
  • 如果还没退出临界区（还没解锁)就进行进程调度,但是进程调度相关的程序也需要访问就绪队列,但此时就绪队列被锁住了，因此又无法顺利进行进程调度
  • 内核程序临界区访问的临界资源如果不尽快释放的话，极有可能影响到操作系统内核的其他管理工作。因此在访问内核程序临界
    区期间不能进行调度与切换
• 当一个程序处理普通临界区的时候
  • 在打印机打印完成之前，进程一直处于临界区内，临界资源不会解锁。但打印机又是慢速设备，此时如果一直不允许进程调度的话就会导致CPU一直空闲
  • 普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时可以进行调度与切换。

• 非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
  • 实现简单,系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统
• 剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。
  • 可以优先处理更紧急的进程,也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统

“狭义的进程调度”与“进程切换”的区别:

• 狭义的进程调度 指的是从就绪队列中选中一个要运行的进程。(这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）
• 进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。
• 广义的进程调度 包含了选择一个进程和进程切换两个步骤。

进程切换的过程主要完成了:

1. 对原来运行进程各种数据的保存
2. 对新的进程各种数据的恢复(如:程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块)

注意:进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

调度算法的评价指标

调度算法

FCFS（先来先服务）（First Come First Serve）

• 算法思想：
  • 主要从“公平”的角度考虑（类似于我们生活中排队买东西的例子)
• 算法规则
  • 按照作业/进程到达的先后顺序进行服务
• 用于作业/进程调度
  • 用于作业调度时，考虑的是哪个作业先到达后备队列;用于进程调度时，考虑的是哪个进程先到达就绪队列
• 是否可抢占?
  • 非抢占式的算法
• 优缺点
  • 优点:公平、算法实现简单
  • 缺点:排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即，FCFS算法对长作业有利，对短作业不利（Eg :排队买奶茶…)
• 是否会导致饥饿

  • 不会

  • 某进程/作业长期得不到服务

SJF（短作业优先）（Shortest Job First）

• 算法思想

  • 追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间

• 算法规则

  • 最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短)

• 用于作业/进程调度

  • 即可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先（SPF, Shortest Process First）算法”

• 是否可以抢占

  • SJF和SPF是非抢占式的算法。但是也有抢占式的版本一一最短剩余时间优先算法(SRTN, Shortest Remaining Time Next)

• 优缺点

  • 优点:
    • “最短的”平均等待时间、平均周转时间
  • 缺点:
    • 不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先

• 是否会导致饥饿

  • 会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为“饿死”

• 注意

  1. 如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的
  2. 很多书上都会说“SJF调度算法的平均等待时间、平均周转时间最少”
     • 严格来说，这个表述是错误的，不严谨的。之前的例子表明，最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少
     • 应该加上一个条件“在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最少”;
       或者说“在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少”;
     • 如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先, SRNT算法）的平均等待时间、平均周转时间最少”
  3. 虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如FCFS),SJF依然可以获得较少的平均等待时间、平均周转时间
  4. 如果选择题中遇到“SJF算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项

HRRN（高响应比优先）（Highest Response RatIO Next）

算法的来源：

FCFS 算法是在每次调度的时候选择一个等待时间最长的作业（进程）为其服务。但是没有考虑到作业的运行时间，因此导致了对短作业不友好的问题

SJF算法是选择一个执行时间最短的作业为其服务。但是又完全不考虑各个作业的等待时间，因此导致了对长作业不友好的问题，甚至还会造成饥饿问题

考虑到上面两个问题的出现，HRRN高响应比优先算法就应运而生

• 算法思想

  • 要综合考虑作业/进程的等待时间和要求服务的时间

• 算法规则

  • 在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
  • 响应比=（等待时间+要求服务时间）/ 要求服务时间
  • 响应比≥1

• 用于作业/进程调度

  • 即可用于作业调度，也可用于进程调度

• 是否可以抢占

  • 非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比

• 优缺点

  • 综合考虑了等待时间和运行时间（要求服务时间)
  • 等待时间相同时，要求服务时间短的优先（SJF的优点)
  • 要求服务时间相同时，等待时间长的优先（FCFS的优点)
  • 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题

• 是否会导致饥饿

  • 不会

RR（时间片轮转调度算法）（Round-Robin）

• 算法思想

  • 公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

• 算法规则

  • 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

• 用于作业/进程调度

  • 用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片)

• 是否可抢占?

  • 若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到

• 优缺点

  • 优点:公平;响应快，适用于分时操作系统;
  • 缺点:由于高频率的进程切换，因此有一定开销;不区分任务的紧急程度。

• 是否会导致饥饿

  • 不会

• 时间片太大或太小分别有什么影响

  • 如果时间片太大 ，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法 ，并且会增大进程响应时间 。因此时间片不能太大 。
  • 另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境)，因此如果时间片太小 ，会导致进程切换过于频繁 ，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小 。

优先级调度算法

• 算法思想

  • 随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序

• 算法规则

  • 调度时选择优先级最高的作业/进程

• 用于作业/进程调度

  • 既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的I/O调度中

• 是否可抢占?

  • 抢占式、非抢占式都有。做题时的区别在于:非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。

• 优缺点

  • 优点:用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
  • 缺点:若源源不断地有高优先级进程到来，则可能导致饥饿

• 是否会导致饥饿

  • 会

就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置

根据优先级是否可以动态改变，可将优先级分为静态优先级 和动态优先级 两种。

静态优先级:创建进程时确定，之后一直不变。

动态优先级:创建进程时有一个初始值，之后会根据情况动态地调整优先级。

如何合理的设置各类进程的优先级？

• 系统进程优先级高于用户进程
• 前台进程优先级高于后台进程
• 操作系统更偏好I/O型进程（或称I/O繁忙型进程)
• 与I/O型进程相对的是计算型进程（或称CPU繁忙型进程)
• I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升

如果采用的是动态优先级,什么时候应该调整?

• 可以从追求公平、提升资源利用率等角度考虑，如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级如果某进程占用处理机运行了很长时间，则可适当降低其优先级

多级返回队列调度算法

算法来源

• FCFS算法的优点是公平
• SJF算法的优点是能尽快处理完短作业,平均等待/周转时间等参数很优秀
• 时间片轮转调度算法可以让各个进程得到及时的响应
• 优先级调度算法可以灵活地调整各种进程被服务的机会

能否对上述几个算法做一个折中的权衡，得到一个综合表现优秀的算法呢？

• 算法思想

  • 对其他调度算法的折中权衡

• 算法规则

  1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
  2. 新进程到达时先进入第1级队列，按FCFS原则排队等待分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
  3. 只有第k 级队列为空时，才会为k+1级队头的进程分配时间片

• 用于作业/进程调度

  • 用于进程调度

• 是否可抢占?

  • 抢占式的算法。在k级队列的进程运行过程中，若更上级的队列(1~k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。

• 优缺点

  • 对各类型进程相对公平（FCFS的优点）;
  • 每个新到达的进程都可以很快就得到响应（RR的优点）﹔
  • 短进程只用较少的时间就可完成(SPF的优点）;
  • 不必实现估计进程的运行时间（避免用户作假);
  • 可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程
  • 拓展:可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级)

• 是否会导致饥饿

  • 会

算法运行过程

进程同步和进程互斥

知识点回顾:进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

• 读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据→读数据”的顺序来执行的。

• 写满才能读， 读完才能写

• 如何解决这种异步问题，就是“进程同步”所讨论的内容。

• 同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

上厕所排队，马桶是临界资源，每个人只能互斥地访问，访问的时候把厕所门锁上

1
2
3
4
5
6

do {
    entry sectIOn; // 进入区
    critical sectIOn; // 临界区
    exit sectIOn;  // 退出区
    remainder sectIOn; // 剩余区
}

注意:

• 临界区 是进程中访问临界资源的代码段。
• 进入区和退出区是负责实现互斥的代码段。临界区也可称为“临界段”。

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则:

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区;
2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待;
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）;
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

进程互斥的软件实现方法

单标志法

算法思想:两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int turn = 0;

// p0进程
while( turn != 0 ){			// 进入区
    critical sectIOn;		// 临界区
    turn = 1;				// 退出区
    remainder sectIOn;		// 剩余区
}

// p1进程
while( turn != 1 ){			// 进入区
    critical sectIOn;		// 临界区
    turn = 0;				// 退出区
    remainder sectIOn;		// 剩余区
}

turn表示当前允许进入临界区的进程号，而只有当前允许进入临界区的进程在访问了临界区之后，才会修改turn的值。也就是说，对于临界区的访问，一定是按PO→P1→PO→P1→…这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是PO，而PO一直不访问临界区，那么虽然此时临界区空闲，但是并不允许P1访问。

因此，单标志法 存在的主要问题是: 违背“空闲让进”原则。

双标志先检查

算法思想:设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] =ture”意味着0号进程PO现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

bool flag[2];		// 表示进入临界区意愿的数组
flag[0] = false; 	
flag[1] = false; 	// 刚开始设置两个进程都不想进入临界区

// p0进程
while(flag[1]);			// 1
flag[0] = true;			// 2
critical = sectIOn; 	// 3
flag[0] = false;		// 4
remainder sectIOn;

// p1进程
while(flag[0]);			// 5 如果此时p0想要进入临界区，p1就一直循环等待
flag[1] = true;			// 6 标记p1进程想要进入临界区
critical = sectIOn; 	// 7 访问临界区
flag[1] = false;		// 8 访问完临界区，修改标记为p1不想进入临界区
remainder sectIOn;

若按照①⑤②6③⑦…的顺序执行，PO和P1将会同时访问临界因此，双标志先检查法的主要问题是:违反“忙则等待”原则。

原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

双标志后检查

算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

bool flag[2];		// 表示进入临界区意愿的数组
flag[0] = false; 	
flag[1] = false; 	// 刚开始设置两个进程都不想进入临界区

// p0进程
flag[0] = true;			// 1
while(flag[1]);			// 2
critical = sectIOn; 	// 3
flag[0] = false;		// 4
remainder sectIOn;

// p1进程
flag[0] = true;			// 5 如果此时p0想要进入临界区，p1就一直循环等待
while(flag[1]);			// 6 标记p1进程想要进入临界区
critical = sectIOn; 	// 7 访问临界区
flag[0] = false;		// 8 访问完临界区，修改标记为p1不想进入临界区
remainder sectIOn;

若按照①⑤②⑥…的顺序执行，PO和P1将都无法进入临界区

因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。

两个进程都争着抢着想要进入临界区，但是谁也不让谁，最后谁也无法进入临界区

Peterson算法

算法思想:双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。Gary L.Peterson想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”，主动让对方先使用临界区。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

bool flag[2];		// 表示进入临界区意愿的数组
int turn = 0; 		// turn=0表示优先让那个进程进入临界

// p0进程
flag[0] = true;				// 1
turn = 1;					// 2
while(flag[1] && turn=1);	// 3
critical = sectIOn; 		// 4
flag[0] = false;			// 5
remainder sectIOn;

// p1进程
flag[1] = true;				// 6	表示自己想要进入临界区
turn = 0;					// 7	可以让对方优先进入临界区
while(flag[0] && turn=0);	// 8	对方想进，且最后一次是自己让“梨”，那自己就循环等待
critical = sectIOn; 		// 9
flag[1] = false;			// 10	访问完临界区，表示自己不想访问临界区了
remainder sectIOn;

进入区:1.主动争取;2.主动谦让;3.检查对方是否也想使用,且最后一次是不是自己说了“客气话”

Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

Peterson算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。

进程互斥硬件实现方法

中断屏蔽方法

利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)

1
2
3

// 关中断: 关中断后即不允许当前进程被中断，也必然不会发生进程切换
// 临界区
// 开中断:直到当前进程访问完临界区,再执行开中断指令，才有可能有别的进程上处理机并访问临界区

优点:简单、高效

缺点:不适用于多处理机;只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险

TestAndSet(Ts指令/TSL指令)

简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令

TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用c语言描述的逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14

//布尔型共享变量lock表示当前临界区是否被加锁
//true表示已加锁， false表示未加锁
bool TestAndSet(bool ×lock) {
    bool old; 
    old = ×lock;	// 用old来存放lock，原来的值
    ×lock = true;	// 无论之前是否已经加锁，都将lock设置为true
    return old;		// 返回lock原来的值
}

// 以下是使用TSL指令实现互斥的算法逻辑
while(TestAndSet(&lock));	// "上锁"并“检查”
// 临界区代码段
lock = false;		// "解锁"
// 剩余代码段

若刚开始lock是false，则TSL返回的old值为false，while循环条件不满足，直接跳过循环，进入临界区。若刚开始lock是true，则执行TLS后old返回的值为true，while循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。

相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。

优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境

缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

Swap指令(XCHG指令)

有的地方也叫Exchange指令，或简称XCHG指令。
Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用c语言描述的逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// Swap 指令作用是交换两个变量的值
Swap(bool ×a, bool ×b) {
    bool temp;
    temp = ×a;
    ×a = ×b;
    ×b = temp
}

// 以下是用Swap指令实现互斥的算法逻辑
// lock表示当前临界区是否被上锁
bool old = true;
while(old == true)
    Swap(&lock, &old);
// 临界区代码段
lock = false;		// "解锁"
// 剩余代码段

逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在 old变量上），再将上锁标记lock设置为true，最后检查old，如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。

优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境

缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

信号量机制

• 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥，进程同步。

• 信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如:系统中只有一台打印机，就可以设置一个初值为1的信号量。
• 原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
• 一对原语: wait(span) 原语和 signal(span)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量span其实就是函数调用时传入的一个参数。

wait、signal原语常简称为P、V操作（来目荷兰语proberen(测试) 和 Verhogen（增加)。因此做题的时候常常把wait(span)、signal(span)两个操作分别写为P(span)、v(span).

整形信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。

与普通整数变量的区别:对信号量的操作只有三种，即初始化、P操作、V操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int span = 1; 		//初始化整形信号量span， 表示当前系统中可用的打印机资源数


// “检查”和“上锁”一气呵成,避免了并发、异步导致的问题
// 存在的问题:不满足“让权等待”原则，会发生“忙等”

void wait(int span) {		// wait 原语，相当于“进入区”
    while(span <= 0);		// 如果资源数不够，就一直循环等待
    span = span-1;			// 如果资源数够，则占用一个资源
}

void signal(int span) { // signal 原语，相当于退出区
    span = span+1;		// 使用完资源之后，在退出区释放资源
}

进程P0

1
2
3
4
5

...
wait(span);			// 进入区，申请资源
使用打印机资源...		// 临界区，访问资源
signal(span);			// 退出区，释放资源
...

进程p1

1
2
3
4
5

...
wait(span);			// 进入区，申请资源
使用打印机资源...		// 临界区，访问资源
signal(span);			// 退出区，释放资源
...

…

进程pn

1
2
3
4
5

...
wait(span);			// 进入区，申请资源
使用打印机资源...		// 临界区，访问资源
signal(span);			// 退出区，释放资源
...

记录性信号量

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

1
2
3
4
5

/×记录性信号量的定义×/
typedef struct {
    int value;				// 剩余资源数
    struct process ×L;		// 等待队列
} semaphore;

1
2
3
4
5
6
7
8

/×某进程需要使用资源的时候，通过wait 原语申请 ×/
void wait(semaphore span){
    span.value--;
    if(span.value < 0){
        // 如果剩余资源数不够,使用block原语使进程从运行态进入阻塞态,并把挂到信号量span的等待队列（即阻塞队列）中
        block(span.L);
    }
}

1
2
3
4
5
6
7
8

/× 进程使用完资源之后，通过signal 原语释放 ×/
void signal(semaphore span) {
    span.value++;
    if(span.value <= 0) {
        // 释放资源后，若还有别的进程在等待这种资源，则使用wakeup原语唤醒等待队列中的一个进程,该进程从阻塞态变为就绪态
        wakeup(span.L);
    }
}

在考研题目中wait(span)、signal(span)也可以记为P(span)、v(span),这对原语可用于实现系统资源的“申请”和“释放”。

• span.value的初值表示系统中某种资源的数目。

对信号量span的一次Р操作意味着进程请求一个单位的该类资源，因此需要执行span.value–，表示资源数减1，当span.value <0时表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞（当前运行的进程从运行态→阻塞态），主动放弃处理机，并插入该类资源的等待队列span.L中。可见，该机制遵循了“让权等待”原则 ，不会出现“忙等”现象。

对信号量span的一次V操作意味着进程释放一个单位的该类资源，因此需要执行span.value++，表示资源数加1，若加1后仍是span.value <=0，表示依然有进程在等待该类资源，因此应调用wakeup原语唤醒等待队列中的第一个进程(被唤醒进程从阻塞态→就绪态)

用信号量实现进程互斥，同步，前驱关系

用信号量实现进程互斥

1. 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应该放在临界区）
2. 设置互斥信号量mutex，初值为1。
3. 在临界区之前执行P(mutex)
4. 在临界区之后执行V(mutex)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/×信号量机制实现互斥×/
// 要会自己定义记录型信号量，但如果题目中没特别说明,可以把信号量的声明简写成这种形式
semaphore mutex=1;		//初始化信号量

P1(){
	...
	P(mutex);		//使用临界资源前需要加锁
	临界区代码段...
	V(mutex);		//使用临界资源后需要解锁
	...
}

P2(){
	...
	P(mutex);
    临界区代码段...
    V(mutex);
	...
}

注意:对不同的临界资源需要设置不同的互斥信号量。

• P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒。

用信号量实现进程同步

进程同步:要让各并发进程按要求有序地推进。

1
2
3
4
5
6
7
8
9
10

P1() {
    代码1;
    代码2;
    代码3;
}
P2() {
    代码4;
    代码5;
    代码6;
}

比如，P1、P2并发执行，由于存在异步性，因此二者交替推进的次序是不确定的。

若P2的“代码4”要基于P1的“代码1”和“代码2”的运行结果才能执行，那么我们就必须保证“代码4”一定是在“代码2”之后才会执行。

这就是进程同步问题，让本来异步并发的进程互相配合，有序推进。

1.分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码)

2.设置同步信号量span,初始为0.

3．在“前操作”之后执行v(span)

4．在“后操作”之前执行P(span)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/×信号量机制实现同步×/
semaphore span=0;		//初始化同步信号量，初始值为0

P1() {
    代码1;
    代码2;
    V(span);
    代码3;
}
P2() {
    p(span);
    代码4;
    代码5;
    代码6;
}

若先执行到v(span)操作，则span++后span=1。之后当执行到P(span)操作时，由于span=1，表示有可用资源，会执行span–，span的值变回0，P2进程不会执行block 原语，而是继续往下执行代码4。

若先执行到P(span)操作，由于span=o，span–后span=-1，表示此时没有可用资源，因此P操作中会执行block原语，主动请求阻塞。之后当执行完代码2，继而执行v(span)操作，span++，使span变回o，由于此时有进程在该信号量对应的阻塞队列中，因此会在V操作中执行wakeup原语，唤醒P2进程。这样P2就可以继续执行代码4了

用信号量实现前驱关系

进程P1中有句代码span1，P2中有句代码span2 …P3… P6中有句代码span6。这些代码要求按如下前驱图所示的顺序来执行:

其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作)因此，

1. 要为每一对前驱关系各设置一个同步变量
2. 在“前操作”之后对相应的同步变量执行V操作
3. 在“后操作”之前对相应的同步变量执行Р操作

生产者消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注:这里的“产品”理解为某种数据)

生产者、消费者共享一个初始为空、大小为n的缓冲区。

• 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
• 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。

缓冲区是临界资源，各进程必须互斥地访问。

• 互斥：设置初值为1的互斥信号量
• 同步：设置初值为0的同步信号量（实现“前一后”）
• 对一类系统资源的申请和释放:设置一个信号量,初始值即为资源的数量（本质上也属于“同步问题”，若无空闲资源,则申请资源的进程需要等待别的进程释放资源后才能继续往下执行)

生产者、消费者共享一个初始为空、大小为n的缓冲区。

只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。

只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。

缓冲区是临界资源，各进程必须互斥地访问。

1
2
3

semaphore mutex = 1;		//互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;		//同步信号量，表示空闲缓冲区的数量
semaphore full = 0;			//同步信号量,表示产品的数量，也即非空缓冲区的数量

1
2
3
4
5
6
7
8
9
10
11

producer (){
    while (1){
    	// 生产一个产品;
   		P(empty);   	//消耗一个空闲缓冲区
        P(mutex);
    	// 把产记放入缓冲区;
        V(mutex);
    	V(full);		// 增加一个产品
    }
    // 实现互斥是在同一进程中进行对PV操作
}

1
2
3
4
5
6
7
8
9
10
11

consumer(){
    while (1){
    P(full);		// 消耗一个产品（非空缓冲区)
    P(mutex);
    //从缓冲区取出一个产品;
    V (mutex);
    v(empty);		// 增加一个空闲缓冲区
    //使用产品;
}
// 实现两进程的同步关系，是在其中一个进程中执行P，另一进程中执行V

1
2
3
4
5
6
7
8
9
10

producer (){
    while (1){
    	// 生产一个产品;
        P(mutex);		// 1
   		P(empty);   	// 2
    	// 把产记放入缓冲区;
        V(mutex);
    	V(full);		
    }
}

1
2
3
4
5
6
7
8
9
10

consumer(){
    while (1){
        P(mutex);    // 3
    	P(full);	// 4	
    	//从缓冲区取出一个产品;
    	V (mutex);
    	v(empty);		// 增加一个空闲缓冲区
    	//使用产品;
    }
}

若此时缓冲区内已经放满产品，则empty=0，full=n。表明这时候只允许消费者来进行访问缓冲区

则生产者进程执行 给缓冲区上锁

• 使mutex变为0，再执行
• 由于已没有空闲缓冲区，因此生产者被阻塞。由于生产者阻塞，因此切换回消费者进程。消费者进程执行
• 由于mutex为o，即生产者还没释放对临界资源的“锁”，因此消费者也被阻塞。

这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”。

同样的，若缓冲区中没有产品，即full=0，empty=n。按③④①的顺序执行就会发生死锁。因此，实现互斥的P操作一定要在实现同步的P操作之后。

V操作不会导致进程阻塞，因此两个V操作顺序可以交换。

PV操作题目的解题思路:

1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序
3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)

生产者消费者问题是一个互斥、同步的综合问题。

对于初学者来说最难的是发现题目中隐含的两对同步关系。

有时候是消费者需要等待生产者生产，有时候是生产者要等待消费者消费，这是两个不同的“一前一后问题”，因此也需要设置两个同步信号量。

易错点:实现互斥和实现同步的两个P操作的先后顺序

多生产者-多消费者

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。

1
2
3
4

semaphore apple = 0;	//盘子中有几个苹果
semaphore orange = 0;	//盘子中有几个橘子
semaphore plate = 1;	//盘子中还可以放多少个水果
// 当缓冲区之后一个的时候可以不是用这个变量 semaphore mutex = 1;	//实现互斥访问盘子（缓冲区）

父亲

1
2
3
4
5
6
7
8

dad (){
	while (1){
		// 准备一个苹果;
        P(plate);
		// 把萃果放入盘子;
        V(apple);
	}
}

母亲

1
2
3
4
5
6
7
8

mom (){
	while(1）{
		// 准备一个橘子;
        P(plate);
        //把橘子放入盘子;
        V(orange);
    }
}

女儿

1
2
3
4
5
6
7
8

doughter (){
	while (1）{
		P(apple);
		// 从盘中取出苹果;
        v(plate);
        // 吃掉苹果;
    }
}

儿子

1
2
3
4
5
6
7
8
9

son(){
	while（1）{
		P(orange);
        // 从盘中取出橘子;
        V(plate);
		// 吃掉橘子;
	}
}

当缓冲区有两个的时候，如果不设置缓冲区互斥访问量的时候，可能会出现，两个生产者同时访问同一块内存，可能发生覆盖的情况，但是需要注意的是：实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”.

单生产者多消费者

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟)

1. 关系分析：找出题目中描述的各个进程，分析它们之间的同步，互斥操作：

   • 互斥：桌子可以抽象为容量为1的缓冲区，要互斥访问
   • 同步：所有操作都做完之后才能让下一个进行，需要按照特定的顺序
     • 桌上有组合一→第一个抽烟者取走东西
     • 桌上有组合二→第二个抽烟者取走东西
     • 桌上有组合三→第三个抽烟者取走东西
     • 发出完成信号→供应者将下一个组合放到桌上

2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序

   • 先V后P

3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)

1
2
3
4
5

semaphore offer1 = 0;	//桌上组合一的数量
semaphore offer2 = 0;	//桌上组合二的数量
semaphore offer3 = 0;	//桌上组合三的数量
semaphore finish = 0;	//抽烟是否完成
int i = 0;				//用于实现”三个抽烟者轮流抽烟”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

provider(){
	while (1){
		if(i==0){
			// 将组合一放桌上;
            V(offer1);
		}else if(i==1）{
			// 将组合二放桌上
            V(offer2);
		}else if(i==2) {
			// 将组合三放桌上;
            V(offer3);
		}
        // 实现“三个抽象轮流抽象抽象”
		i=(i+1)%3;
        P(finish);
	}
}

1
2
3
4
5
6
7

smoker1 (){
	while (1）{
		P(offer1);
       	// 从桌上拿走组合一;卷烟;抽掉;
        V(finish);
    }
}

1
2
3
4
5
6
7

smoker2 (){
	while (1）{
		P(offer2);
       	// 从桌上拿走组合二;卷烟;抽掉;
        V(finish);
    }
}

1
2
3
4
5
6
7

smoker3 (){
	while (1）{
		P(offer1);
       	// 从桌上拿走组合三;卷烟;抽掉;
        V(finish);
    }
}

读者写者问题

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求:

• 允许多个读者可以同时对文件执行读操作;
  • 与消费者进程不同，读者进程在读数据后并不会将数据清空，并不会改变数据。因此多个读者可同时访问共享数据
• 只允许一个写者往文件中写信息;
• 任一写者在完成写操作之前不允许其他读者或写者工作;
• 写者执行写操作前，应让已有的读者和写者全部退出。
• 两个写进程同时共享数据，可能导致数据错误覆盖的问题

两类进程:写进程、读进程

• 互斥关系:写进程―写进程、写进程―读进程。读进程与读进程不存在互斥问题。
• 写者进程和任何进程都互斥，设置一个互斥信号量rw，在写者访问共享文件前后分别执行P、V操作。读者进程和写者进程也要互斥，因此读者访问共享文件前后也要对rw执行P、V操作。
• 如果所有读者进程在访问共享文件之前都执行P(rw)操作，那么会导致各个读进程之间也无法同时访问文件。

P(rw)和V(rw)其实就是对共享文件的“加锁”和“解锁”。既然各个读进程需要同时访问，而读进程与写进程又必须互斥访问，那么我们可以让第一个访问文件的读进程“加锁”，让最后一个访问完文件的读进程“解锁”。可以设置一个整数变量count来记录当前有几个读进程在访问文件。

1
2
3
4

semaphore rw=1;		//用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count = 0;		//记录当前有几个读进程在访问文件
semaphore mutex = 1; // 用户保证对count变量的互斥访问
semaphore w = 1; 	// 用于实现“写优先”

1
2
3
4
5
6
7
8

writer(){
	while (1){
		P(rw);//写之前"加锁"
		//写文件...
		V(rw);
		//写之后"解锁”
	}
}

1
2
3
4
5
6
7
8
9
10
11

reader (){
	while (1){
		if(count == 0)
			P(rw);		//第一个读进程负责"加锁"
		count++;		//访问文件的读进程数+1
		// 读文件...
		count--;		//访问文件的读进程数-1
		if (count == 0)
			V(rw);		//最后一个读进程负责"解锁"
    }
}

思考:若两个读进程并发执行，则两个读进程有可能先后执行P(rw)，从而使第二个读进程阻塞的情况。

如何解决: 出现上述问题的原因在于对count变量的检查和赋值无法一气呵成，因此可以设置另一个互斥信号量来保证各读进程对count的访问是互斥的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

reader (){
	while (1){
        P(mutex); 		// 各进程互斥访问count
		if(count == 0)
			P(rw);		//第一个读进程负责"加锁"
		count++;		//访问文件的读进程数+1
        V(mutex);
        
		// 读文件...
        
        P(mutex); 		// 各进程互斥访问count
		count--;		//访问文件的读进程数-1
		if (count == 0)
			V(rw);		//最后一个读进程负责"解锁"
        V(mutex);
    }
}

潜在的问题:只要有读进程还在读,写进程就要一直阻塞等待,可能“饿死”。因此，这种算法中,读进程是优先的

• 如果第一个读进程加锁之后，后来读进程来之后直接读就行，如果有源源不断的读进程来的话，可能会导致写文件饥饿

解决方法：

我们可以在加锁之前在进行一个读进程和写进程都服从的PV操作，如果一个读进程进入的话 先执行P(W) P(mutex)P(rw)V(mutex);

这时候如果有一个写进程进来的话，我们先执行P(W)，但由于这时候rw还没有释放，所以会被阻塞到P(rw)这里，这时候，如果再有一个读进程进来的话，因为P(w)在写进程哪里使用了，所以下一个读进程需要阻塞到P(w)这里，直到写进程写入完毕之后V(w)之后，下一个读进程才能够读入

1
2
3
4
5
6
7
8
9
10

writer(){ 
	while (1){
        P(w);
		P(rw);//写之前"加锁"
		//写文件...
		V(rw);
		//写之后"解锁”
        V(w);     
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

reader (){
	while (1){
        P(w);
        P(mutex); 		// 各进程互斥访问count
		if(count == 0)
			P(rw);		//第一个读进程负责"加锁"
		count++;		//访问文件的读进程数+1
        V(mutex);
        V(w);
        
		// 读文件...
        
        P(mutex); 		// 各进程互斥访问count
		count--;		//访问文件的读进程数-1
		if (count == 0)
			V(rw);		//最后一个读进程负责"解锁"
        V(mutex);
    }
}

读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。

其核心思想在于设置了一个计数器count用来记录当前正在访问共享文件的读进程数。我们可以用count的值来判断当前进入的进程是否是第一个/最后一个读进程,从而做出不同的处理。

另外，对count变量的检查和赋值不能一气呵成导致了一些错误,如果需要实现“一气呵成”，自然应该想到用互斥信号量。

哲学家进餐

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

1
2
3
4
5
6
7
8
9
10
11

semaphore chopstick [5]={1,1,1,1,1};
Pi (){		//i号哲学家的进程
	while(1）{
		P(chopstick[i]);	//拿左
		P(chopstick[(i+1)%5]）;	//拿右
		// 吃饭..
		v(chopstick[i]);		//放左
		v(chopstick[(i+1)%5]);	//放右
		// 思考.
    }
}

• 可能会导致死锁问题：如果5个哲学家并发地拿起自己左手边的筷子..
• 每位哲学家循环等待右达的人放下筷子（阻塞)发生“死锁”

解决方法：

• 可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
• 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这避免了占有一支后再等待另一只的情况。
• 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex = l;		//互斥地取筷子
Pi (){		//i号哲学家的进程
	while (1）{
		P(mutex);
		P(chopstick [i]);
		//拿左
		P (chopstick[(i+1)%5]）;
		//拿右
		V(mutex);
           
		//吃饭..
           
		v(chopstick[i]);
		//放左
		V(chopstick[(i+1)%5]);
		//放右
		//思考.
}

管程

管程是一种特殊的软件模块，有这些部分组成:

1. 局部于管程的共享数据结构说明;
2. 对该数据结构进行操作的一组过程;
3. 对局部于管程的共享数据设置初始值的语句;
4. 管程有一个名字。

管程的基本特征：

1. 局部于管程的数据只能被局部于管程的过程所访问;
2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据;
3. 每次仅允许一个进程在管程内执行某个内部过程。

管程操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

monitor ProducerConsumer
    // 管程中设置条件变量和等待/唤醒操作，已解决同步问题
	conditIOn full,empy;	// 条件变量用来实现同步(排队)
    int count=0;	// 缓冲区产品的个数
	// 由编译器负责实现各进程互斥地进入管程中的过程
	void insert (Item item){	// 把产品item放入缓冲区
        if (count == N)
			wait (full);
        count++;
		insert_item(item);
        if ( count == 1)
            signal(empty);
    }
	item remove (){		// 从缓冲区中取出一个产品
        if ( count == 0)
            wait (empty);
        count--;
		if ( count == N-1)
            signal(full);
		return remove_item();
    }

end monitor;

生产者进程

1
2
3
4
5
6

producer() {
    while(1){
        item="生产一个产品";
        ProducerConsumer.insert(item);
    }
}

消费者进程

1
2
3
4
5
6

consumer() {
    while(1) {
        item = ProducerConsumer.remove();
        消费产品item;
    }
}

每次仅允许一个进程在管程内执行某个内部过程

例1:两个生产者进程并发执行，依次调用了insert过程…

例2:两个消费者进程先执行，生产者进程后执行

引入管程的目的无非就是要更方便地实现进程互斥和同步。

1. 需要在管程中定义共享数据（如生产者消费者问题的缓冲区）
2. 需要在管程中定义用于访问这些共享数据的“入口”一—其实就是一些函数（如生产者消费者
   问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品)
3. 只有通过这些特定的“入口”才能访问共享数据.
4. 管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入(如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意:这种互斥特性是由编译器负责实现的，程序员不用关心 )
5. 可在管程中设置条件变量及 等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量
   上等待（此时，该进程应先释放管程的使用权，也就是让出“入口”)﹔可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

程序员可以用某种特殊的语法定义一个管程（比如: monitor ProducerConsumer …end monitor;）,之后其他程序员就可以使用这个管程提供的特定“入口”很方便地使用实现进程同步/互斥了。

Java中，如果用关键字synchronized来描述一个函数，那么这个函数同一时间段内只能被一个线程调用

1
2
3
4
5
6
7
8
9

static class monitor{
    private Item buffer[] = new Item[N];
    private int count = 0;
    
    // 每次只能有一个线程进入insert函数，如果多个线程同时调用insert 函数，则后来者需要排队等待
    public synchronized void insert (Item item) {
        .....;
    }
}

死锁

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉,这些进程都将无法向前推进。

• 死锁:各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
• 饥饿:由于长期得不到想要的资源，某进程无法向前推进的现象。比如:在短进程优先(SPF）算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。
• 死循环:某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。

产生死锁必须同时满足一下四个条件，只要其中任一条件不成立，死锁就不会发生。

• 互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。
• 不剥夺条件:进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
• 请求和保持条件:进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
• 循环等待条件:存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

注意!发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件)

如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。

1. 对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU)）的竞争是不会引起死锁的。

2. 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。

3. 信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。(可以把互斥信号量、同步信号量也看做是一种抽象的系统资源)

总之，对不可剥夺资源的不合理分配，可能导致死锁。

预防死锁。破坏死锁产生的四个必要条件中的一个或几个。

避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法)

死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。

预防死锁

• 互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁。
• 如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如: SPOOLING技术。操作系统可以采用SPOOLING 技术把独占设备在逻辑上改造成共享设备。比如，用SPOOLING技术将打印机改造为共享设备…
  入
• 该策略的缺点:并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。

• 不剥夺条件:进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。

破坏不剥夺条件:

• 方案一:当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。得不到的就放手.
• 方案二:当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如:剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用)得不到的就把他抢过来.

该策略的缺点:

1. 实现起来比较复杂。
2. 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
4. 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

• 请求和保持条件:进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
• 可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。

该策略实现起来简单，但也有明显的缺点:

有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。

• 例如上面这个程序，如果有源源不断的AB进程涌入过来的话，可能会导致C类进程饥饿

• 循环等待条件:存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
• 可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源,同类资源（即编号相同的资源）一次申请完。
• 原理分析:一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。

该策略的缺点:

1. 不方便增加新的设备，因为可能需要重新分配所有的编号;
2. 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费;
3. 必须按规定次序申请资源，用户编程麻烦。

避免死锁

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。

如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）

因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。

• 资源总数10.

此时系统是否处于安全状态?

思路:尝试找出一个安全序列… P1，P3，PO，P2，P4

依次检查剩余可用资源(3,3,2)是否能满足各进程的需求

可满足P1需求，将P1加入安全序列，并更新剩余可用资源值为(5，3，2)

依次检查剩余可用资源(5,3,2)是否能满足剩余进程（不包括已加入安全序列的进程）的需求

可满足P3需求，将P3加入安全序列，并更新剩余可用资源值为(7,4,3)

依次检查剩余可用资源(7,4,3)是否能满足剩余进程（不包括已加入安全序列的进程）的需求………

以此类推，共五次循环检查即可将5个进程都加入安全序列中，最终可得一个安全序列。该算法称为安全性算法。可以很方便地用代码实现以上流程，每一轮检查都从编号较小的进程开始检查。实际做题时可以更快速的得到安全序列。

• 手算算法

实际做题（手算）时可用更快速的方法找到一个安全序列:

经对比发现，(3,3,2）可满足P1、P3，说明无论如何，这两个进程的资源需求一定是可以依次被满足的，因此P1、P3一定可以顺利的执行完，并归还资源。可把P1、P3先加入安全序列。

(2,0,0)+(2,1,1)+(3,3,2)= (7,4,3)

剩下的PO、P2、P4都可被满足。同理，这些进程都可以加入安全序列。

于是，5个进程全部加入安全序列，说明此时系统处于安全状态,暂不可能发生死锁。

• 在看一个找不到安全序列的例子：

• 资源总数10.

经对比发现，(3,3,2）可满足P1、P3，说明无论如何，这两个进程的资源需求一定是可以依次被满足的，因此P1、P3一定可以顺利的执行完，并归还资源。可把P1、P3先加入安全序列。

(2,0,0)+(2,1,1)+(3,3,2)= (7,4,3)

剩下的P0需要(8,4,3)，P2需要(6,5,0)，P4需要(4,3,4),

任何一个进程都不能被完全满足

于是，无法找到任何一个安全序列，说明此时系统处于不安全状态，有可能发生死锁。

• 具体流程

假设系统中有n个进程，m种资源.

每个进程在运行前先声明对各种资源的最大需求数，则可用一个n×m 的矩阵（可用二维数组实现）表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵Max，Max[i, j]=K表示进程Pi最多需要K个资源Rj。同理，系统可以用一个n×m的分配矩阵AllocatIOn表示对所有进程的资源分配情况。Max 一 AllocatIOn = Need矩阵，表示各进程最多还需要多少各类资源。另外，还要用一个长度为m的一维数组Available表示当前系统中还有多少可用资源。

某进程Pi向系统申请资源，可用一个长度为m的一维数组 Request,表示本次申请的各种资源量。

可用银行家算法预判本次分配是否会导致系统进入不安全状态:

1. 如果Request[i]≤Need[ i, i ] (O≤j≤m)便转向 2 ;否则认为出错。因为它所需要的资源数已超过它所宣布的最大值。

2. 如果Request[i]<Available[i,j] (0≤j<m)，便转向③;否则表示尚无足够资源，Pi必须等待。

3. 系统试探着把资源分配给进程Pi，并修改相应的数据（并非真的分配，修改数值只是为了做预判):

   Available = Available - Request,;

   AllocatIOn[i, j] = AllocatIOn[i, j] + Request;[j]

   Need[i, j] = Need[i, j]- Request[j]

4. 操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式分配;否则，恢复相应数据，让进程阻塞等待。

数据结构:

长度为m的一维数组Available表示还有多少可用资源

n×m矩阵Max表示各进程对资源的最大需求数

n×m矩阵AllocatIOn表示已经给各进程分配了多少资源

Max - AllocatIOn = Need矩阵表示各进程最多还需要多少资源用长度为m的一位数组Request表示进程此次申请的各种资源数

银行家算法步骤:

1. 检查此次申请是否超过了之前声明的最大需求数
2. 检查此时系统剩余的可用资源是否还能满足这次请求
3. 试探着分配，更改各数据结构
4. 用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法步骤:

• 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列并把该进程持有的资源全部回收。
• 不断重复上述过程，看最终是否能让所有进程都加入安全序列。
• 系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。

死锁的检测和解除

为了能对系统是否已发生了死锁进行检测，必须:

1. 用某种数据结构来保存资源的请求和分配信息;
2. 提供一种算法，利用上述信息来检测系统是否已进入死锁状态。

一般用矩形表示资源结点，矩形中的小圆代表该类资源的数量

为了能对系统是否已发生了死锁进行检测，必须:

1. 用某种数据结构来保存资源的请求和分配信息;
2. 提供一种算法，利用上述信息来检测系统是否已进入死锁状态。

如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程…

如果按上述过程分析，最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（相当于能找到一个安全序列)

如果最终不能消除所有边，那么此时就是发生了死锁。

• 最终还连着边的那些进程就是处于死锁状态的进程

• 像上面这个图可以按照p1 p2 这个方式进行的话就可以消除所有的边

检测死锁的算法:

1. 在资源分配图中，找出既不阻塞又不是孤点的进程Pi(即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如下图中，R1没有空闲资源，R2有一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之称为孤立的结点。在下图中P1是满足这一条件的进程结点，于是将P1的所有边消去。
2. 进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在下图中，P2就满足这样的条件。根据1）中的方法进行一系列简化后，若能消去途中所有的边，则称该图是可完全简化的,那么此时系统死锁.

• 死锁定理:如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁.

一旦检测出死锁的发生，就应该立即解除死锁。
补充:并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程.

解除死锁的主要方法有:

1. 资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
2. 撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
3. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

• 如何决定“对那个进程执行操作”

1. 进程优先级
2. 已执行多长时间还要多久能完成
3. 进程已经使用了多少资源
4. 进程是交互式的还是批处理式的

操作系统第三章：内存管理

内存的基础知识

内存是用于存放数据的硬件。程序执行前需要先放到内存中才能被CPU处理。

内存中也有一个一个的“小房间”，每个小房间就是一个“存储单元”

如果计算机“按字节编址’则每个存储单元大小为1字节，即1B，即8个二进制位

如果字长为16位的计算机“按字编址”，则每个存储单元大小为1个字;每字的大小为16个二进制位

我们写的代码要翻译成CPU能识别的指令。这些指令会告诉CPU应该去内存的哪个地址存/取数据,这个数据应该做什么样的处理。在这个例子中，指令中直接给出了变量x的实际存放地址（物理地址）。但实际在生成机器指令的时候并不知道该进程的数据会被放到什么位置。所以编译生成的指令中一般是使用逻辑地址（相对地址)

宿舍四个人一起出去旅行，四个人的学号尾号分别是0、1、2、3。

住酒店时酒店给你们安排了4个房号相连的房间。四个人按学号递增次序入住房间。比如0、1、2、3号同学分别入住了5、6、7、8号房间。

四个人的编号0、1、2、3其实是一个“相对位置”，而各自入住的房间号是一个“绝对位置”。只要知道0号同学住的是房号为N的房间，那么M号同学的房号一定是N+M。

也就是说，只要知道各个同学的“相对位置”和“起始房号”，就一定可以算出所有同学的“绝对位置”

指令中的地址也可以采用这种思想。编译时产生的指令只关心“相对地址”，实际放入内存中时再想办法根据起始位置得到“绝对地址”。

Eg:编译时只需确定变量X存放的相对地址是100（也就是说相对于进程在内存中的起始地址而言的地址）。CPU想要找到X在内存中的实际存放位置，只需要用进程的起始地址+100即可。

• 相对地址又称逻辑地址，绝对地址又称物理地址。

• 编译:由编译程序将用户源代码编译成若干个目标模块（编译就是把高级语言翻译为机器语言，注意这里面的地址是逻辑地址)
• 链接:由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块装入（装载）:由装入程序将装入,这时候的地址是完整的逻辑地址.

• 模块装入内存运行，这时候的地址是物理地址.

• 如上面图片中所表达的，如果从内存地址为100的地址开始依此执行装入模块中的指令的话，如果不进行逻辑地址的转换,那么这时候会向地址为80的地址写入数据，会导致程序出错
• 装入的三种方式（用三种不同的方法完成逻辑地址到物理地址的转换）:
  1. 绝对装入
  2. 静态重定位
  3. 动态重定位

装入的三种方式

• 绝对装入:在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码.装入程序按照装入模块中的地址，将程序和数据装入内存。
• Eg:如果知道装入模块要从地址为100的地方开始存放…

• 绝对装入只适用于单道程序环境因为单道程序环境在同一时刻只会有一个程序在运行，我们可以规定每个程序的起始位置。
• 程序中使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。通常情况下都是编译或汇编时再转换为绝对地址。

• 静态重定位:又称可重定位装入。编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的）。

• 静态重定位的特点是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。

• 动态重定位:又称动态运行时装入。编译、链接后的装入模块的地址都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。

采用动态重定位时允许程序在内存中发生移动。

优点：

• 可将程序分配到不连续的存储区中;在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存;
• 便于程序段的共享,可以向用户提供一个比存储空间大得多的地址空间。

链接的三种方式

• 静态链接:在程序运行之前先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块）,之后不再拆开。

• 装入时动态链接:将各目标模块装入内存时，边装入边链接的链接方式。

• 运行时动态链接:在程序执行中需要该目标模块时。其优点是便于修改和更新，便于实现对目标模块的共享。

内存管理的概念

1. 操作系统要怎么记录哪些内存区域已经被分配出去了，哪些又还空闲?
2. 如果一个进程过来之后，内存中有许多位置都是空闲的要怎么确定放的位置？
3. 当进程结束之后，如何将进程占用的内存进行回收？

• 操作系统需要提供某种技术从逻辑上对内存空间进行扩充
• 操作系统的虚拟性

操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换.

为了使编程更方便，程序员写程序时应该只需要关注指令、数据的逻辑地址。而逻辑地址到物理地址的转换（这个过程称为地址重定位）应该由操作系统负责，这样就保证了程序员写程序时不需要关注物理内存的实际情况。

操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰.

每个进程都只能访问自己的内存空间，不能够访问其他进程的，或者是操作系统的

内存保护可采取两种方法:
方法一:在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。

方法二:采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

覆盖与交换

覆盖技术

早期的计算机内存很小，比如 IBM推出的第一台PC机最大只支持1MB大小的内存。因此经常会出现内存大小不够的情况。

后来人们引入了覆盖技术,用来解决“程序大小超过物理内存总和”的问题.

覆盖技术的思想:将程序分为多个段（多个模块)。常用的段常驻内存，不常用的段在需要时调入内存。

内存中分为一个“固定区”和若干个“覆盖区”。

需要常驻内存的段放在“固定区”中，调入后就不再调出(除非运行结束)

不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存.

B和C只能由A调用，BC在同一时间段只能有一个进程使用，同理，DEF在同一时间段只能由一个程序唤醒

• 按照自身逻辑结构，让那些不可能同时被访问的程序段共享同一个覆盖区
• 必须由程序员声明覆盖结构，操作系统完成自动覆盖。
• 缺点:对用户不透明，增加了用户编程负担。
• 覆盖技术只用与早期操作系统，现在已经成为历史

交换技术

交换（对换）技术的设计思想:内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度)

• 中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存。
• 在进程调出内存的时候，PCB不会跟着一起调出，因为PCB还需要在内存中控制程序的调入。

暂时换出外存等待的进程状态为挂起状态（挂起态，suspend）

挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态

1. 应该在外存（磁盘）的什么位置保存被换出的进程?

   具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式;对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式（学过文件管理章节后即可理解）。总之，对换区的I/O速度比文件区的更快。

2. 什么时候应该交换?

   交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如:在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程;如果缺页率明显下降，就可以暂停换出。

3. 应该换出哪些进程?

   可优先换出阻塞进程;可换出优先级低的进程;为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间…

注意:PCB会驻内存，不会被换出外存)

连续分配管理方式

单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据;用户区用于存放用户进程相关数据。

内存中只能有一道用户程序，用户程序独占整个用户区空间。

• 优点:实现简单;无外部碎片;可以采用覆盖技术扩充内存;不一定需要采取内存保护(eg:早期的PC操作系统MS-DOS)。
• 缺点:只能用于单用户、单任务的操作系统中;有内部碎片;存储器利用率极低。
• 内部碎片：内存已经给这个用户分配了，但是用户没有使用，内存利用率低

固定分区分配

20世纪60年代出现了支持多道程序的系统，为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。

分区方式：

• 分区大小相等
  • 缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合（比如:钢铁厂有n个相同的炼钢炉，就可把内存分为n个大小相等的区域存放n个炼钢炉控制程序)
• 分区大小不等
  • 增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分(比如:划分多个小分区、适量中等分区少量大分区)

操作系统需要建立一个数据结构—分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。

用数据结构的数组(或链表)即可表示这表

当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个能满足大小的、未分配的分区，将之分配给该程序,然后修改状态为“已分配”。

优点:实现简单，无外部碎片。

缺点:

• 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能;
• 会产生内部碎片，内存利用率低。

动态分区分配

• 动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。(eg:假设某计算机内存大小为64MB，系统区8MB 用户区共56 MB…)

• 空闲分区表

空闲分区表:每个空闲分区对应一个表项。

表项中包含分区号、分区大小、分区起始地址等信息

• 空闲分区链：

空闲分区链:每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可记录分区大小等信息

• 当一个新进程过来之后，如果多个空闲地方都满足这个进程的话，我们应该选择使用最大的分区进行分配，还是用最小的分区进行分配，又或者用地址最低的部分进行分配
• 把一个新作业装入内存时，须按照一定的动态分区分配算法，从空闲分区表（或空闲分区链）中选出一个分区分配给该作业。由于分配算法算法对系统性能有很大的影响，因此人们对它进行了广泛的研究。

1. 情况一：回收区的后面有一个相邻的空闲分区

   两个空闲分区合并为一个

2. 情况二：回收区的前面有一个相邻的空闲分区，两个空闲分区合并为一个

   

   3. 情况三：回收区前后都有一个空闲分区，三个相邻的分区合并为一个

      

   4. 情况四：回收区前后都没有空闲分区

      新增一个表项

      注:各表项的顺序不一定按照地址递增顺序排列，具体的排列方式需要依据动态分区分配算法来确定。

   

• 动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。
• 动态分区分配没有内部碎片，但是有外部碎片。
  • 内部碎片 ，分配给某进程的内存区域中，如果有些部分没有用上。
  • 外部碎片 ，是指内存中的某些空闲分区由于太小而难以利用。

如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。

可以通过紧凑（拼凑技术来解决外部碎片

动态分配算法

首次适应算法(First Fit)

• 算法思想:每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
• 如何实现:空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表)，找到大小能满足要求的第一个空闲分区。

最佳适应算法(Best Fit)

• 算法思想:由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。
• 如何实现:空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
• 缺点:每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。 .

最坏适应算法(Worst Fit)

又称最大适应算法（Largest Fit)

• 算法思想:为了解决最佳适应算法的问题一一即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
• 如何实现:空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表)，找到大小能满足要求的第一个空闲分区。

缺点：

• 每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。

邻近适应算法(Next Fit)

• 算法思想:首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
• 如何实现:空闲分区以地址递增的顺序排列(可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表)，找到大小能满足要求的第一个空闲分区。

首次适应算法每次都要从头查找，每次都需要检索低地址的小分区但是这种规则也决定了当低地址部分有更小的分区可以满足需求时会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来（最佳适应算法的优点）

邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用（最大适应算法的缺点)

基本分页存储管理的基本概念

考虑支持多道程序的两种连续分配方式:

1. 固定分区分配:缺乏灵活性，会产生大量的内部碎片，内存的利用率很低。
2. 动态分区分配:会产生很多外部碎片，虽然可以用“紧凑”技术来处理,但是“紧凑”的时间代价很高

如果允许将一个进程分散地装入到许多不相邻的分区中，便可充分地利用内存，而无需再进行“紧凑”

• 连续分配:为用户进程分配的必须是一个连续的内存空间。
• 非连续分配:为用户进程分配的可以是一些分散的内存空间。

分页存储管理的基本概念

将内存空间分为一个个大小相等的分区（比如:每个分区4KB），每个分区就是一个“页框”，或称“页帧”、“内存块”、“物理块”。每个页框有一个编号，即“页框号”(或者“内存块号”、“页帧号”、“物理块号”)页框号从0开始。

将用户进程的地址空间也分为与页框大小相等的一个个区域，称为“页”或“页面”。每个页面也有一个编号，即“页号”页号也是从0开始。（注:进程的最后一个页面可能没有一个页框那么大。因此，页框不能太大，否则可能产生过大的内部碎片)

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。

各个页面不必连续存放，也不必按先后顺序来，可以放到不相邻的各个页框中。

如何实现地址的转换

• 如果这时候CPU正在执行指令1，我们需要去寻找地址为80的页面，我们如何将80这个逻辑地址，改变成物理地址
• 逻辑地址为80的内存单元: 应该在1号页，该页在内存中的起始位置为450，逻辑地址为80的内存单元相对于该页的起始地址而言,“偏移量”应该是30。

逻辑地址转换成物理地址

1. 要算出逻辑地址对应的页号
2. 要知道该页号对应页面在内存中的起始地址
3. 要算出逻辑地址在页面内的“偏移量”
4. 物理地址 = 页面地址 + 页内偏移量

• 页号=逻辑地址/页面长度(取除法的整数部分)
• 页内偏移量=逻辑地址%页面长度（取除法的余数部分)
• 页面在内存中的起始位置:操作系统需要用某种数据结构记录进程各个页面的起始位置。

在计算机中为了方便计算页号，页内偏移量，页面大小一般使用2的整数幂

假设用32个二进制位表示逻辑地址，页面大小为$2^{12}B$= 4096B= 4KB

0号页的逻辑地址空间应该是0~4095，用二进制表示应该是:

00000000000000000000 000000000000~00000000000000000000 111111111111

1号页的逻辑地址空间应该是4096~8191，用二进制表示应该是:

00000000000000000001 000000000000 ~ 00000000000000000001 111111111111

2号页的逻辑地址空间应该是8192~12287，用二进制表示应该是:

00000000000000000010 000000000000~000000000000000000101 111111111111

• 前面是页号，后面是页内偏移量

结论:如果每个页面大小为2×B，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号.

因此，如果让每个页面的大小为2的整数幂，计算机就可以很方便地得出一个逻辑地址对应的页号和页内偏移量.

逻辑地址结构

地址结构包含两个部分:前一部分为页号，后一部分为页内偏移量w。在上图所示的例子中，地址长度为32位，其中0 ~ 11位为“页内偏移量”，或称“页内地址”;12 - 31位为“页号”。

• 如果有K位表示“页内偏移量”，则说明该系统中一个页面的大小是$2^k$个内存单元.
• 如果有M位表示“页号”，则说明在该系统中，一个进程最多允许有$2^M$个页面.

页表

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表

1. 一个进程对应一张页表
2. 进程的每一页对应一个页表项
3. 每个页表项由“页号”和“块号”组成
4. 页表记录进程页面和实际存放的内存块之间的对应关系.
5. 每个页表项的长度是相同的，页号是“隐含”的.

基本地址变换结构

• 重点理解、记忆基本地址变换机构（用于实现逻辑地址到物理地址转换的一组硬件机构）的原理和流程 .

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址.

通常会在系统中设置一个页表寄存器（PTR)，存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时， 作系统内核会把它们放到页表寄存器中。

注意:页面大小是2的整数幂.

设页面大小为L，逻辑地址A到物理地址E的变换过程如下:

1. 计算页号Р和页内偏移量w（如果用十进制数手算，则P=A/L，W=A%L;但是在计算机实际运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量)
2. 比较页号P和页表长度M，若P≥M，则产生越界中断，否则继续执行。（注意:页号是从0开始的，而页表长度至少是1，因此P=M时也会越界)
3. 页表中页号p对应的页表项地址=页表起始地址F+页号P×页表项长度，取出该页表项内容b,即为内存块号。（注意区分页表项长度、页表长度、页面大小的区别。
4. 页表长度指的是这个页表中总共有几个页表项，即总共有几个页;
5. 页表项长度指的是每个页表项P占多大的存储空间;
6. 页面大小:是一个页面占多大的存储空间
7. 计算E= b×L+W(物理块号×页面长度 + 页内偏移量)，用得到的物理地址E去访存。（如果内存块号、页面偏移量是用二进制表示的，那么把二者拼接起来就是最终的物理地址了)

EG: 若页面大小

L为1K字节，页号2对应的内存块号b=8，将逻辑地址A=2500转换为物理地址E。

等价描述:某系统按字节寻址，逻辑地址结构中，页内偏移量占10位，页号2对应的内存块号b=8,将逻辑地址A=2500转换为物理地址E。

• 页内偏移量占用位数: 就是偏移量占用的位数，偏移量一共有几位，偏移量的位数决定了页面的大小

1. 计算页号、页内偏移量

   页号P=A/L = 2500/1024= 2; 页内偏移量W=A%L = 2500%1024=452

2. 根据题中条件可知，页号没有越界，其存放的内存块号b=8

3. 物理地址E= b×L+W=8×1024+ 425=8644

在分页存储管理（页式管理）的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。因此，页式管理中地址是一维的。即，只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量两个部分，并不需要显式地告诉系统这个逻辑地址中，页内偏移量占多少位。

对页表项的进一步讨论

• 每个页表项的长度是相同的，页号是“隐含”的

Eg:假设某系统物理内存大小为4GB，页面大小为4KB，的内存总共会被分为$2^{32}/2^{12}=2^{20}$个内存块，因此内存块号的范围应该是$0-2^{20}-1$
因此至少要20个二进制位才能表示这么多的内存块号，因此至少要3个字节才够(每个字节8个二进制位，3个字节共24个二进制位)

各页表项会按顺序连续地存放在内存中
如果该页表在内存中存放的起始地址为X，则M号页对应的页表项是存放在内存地址为X＋3×M

一个页面为4KB，则每个页框可以存放4096/3= 1365个页表项，但是这个页框会剩余4096% 3=1B页内碎片。因此，1365号页表项存放的地址为X+3×1365＋1

如果每个页表项占4字节，则每个页框刚好可存放1024个而表项

1024号页表项虽然是存放在下一个页框中的，但是它的地址依然可以用X＋4×1024得出

• 结论:理论上，页表项长度为3B即可表示内存块号的范围，但是，为了方便页表的查询常常会让一个页表项占更多的字节，使得每个页面恰好可以装得下整数个页表项。

具有快表的地址变换机构

局部性原理

1
2
3
4
5
6

int i = 0;
int a[100];
while(i < 100) {
    a[i] = i;
    i++;
}

这个程序执行时,会很频繁地访问10号、23号内存块

• 时间局部性:如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)
• 空间局部性:一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)

• 上小节介绍的基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是同一个页表项。既然如此，能否利用这个特性减少访问页表的次数呢?

快表机制(TLB, TranslatIOn Lookaside Buffer)

• 快表，又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

引入快表之后，地址的变化过程

1. CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
2. 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此.若快表命中，则访问某个逻辑地址仅需一次访存即可。
3. 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此,若快表未命中，则访问某个逻辑地址需要两次访存（注意:在找到页表项后，应同时将其存入快表。但若快表已满，则必须按照一定的算法对旧的页表项进行替换)

由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理．一船来说快表的合中率可以达到90%以上

例:某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问一次快表耗时1us，访问一次内存耗时100us。若快表的命中率为90%，那么访问一个逻辑地址的平均耗时是多少?

(1+100)× 0.9+ (1+100+100)× 0.1= 111 us

有的系统支持快表和慢表同时查找，如果是这样，平均耗时应该是(1+100)×0.9+(100+100)× 0.1=110.9 us

若未采用快表机制，则访问一个逻辑地址需要100+100 = 200us显然，引入快表机制后，访问一个逻辑地址的速度快多了。

两级页表

单级页表存在什么问题?如何解决?

某计算机系统按字节寻址，支持32位的逻辑地址，采用分页存储管理，页面大小为4KB，页表项长度为4B。

4KB= $2^{12}$B，因此页内地址要用12位表示，剩余20位表示页号。

因此，该系统中用户进程最多有220页。相应的，一个进程的页表中，最多会有$2^{20}= 1M = 1,048,576$个页表项，所以一个页表最大需要$2^{20}× 4B= 2^{22}B$，共需要$2^{22}/2^{12}=2^{10}$个页框存储该页表。

根据局部性原理可知，很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。

• 页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。

没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。

• 解决方法：虚拟内存:是计算机系统内存管理的一种技术。使得应用程序以为它拥有连续可用的内存空间，而实际上，它通常是被分割成多个物理内存块，还有部分暂时存储在外存上，这种技术使得大型程序编写更加方便，对真正的物理内存使用也更有效率

可将长长的页表进行分组，使每个内存块刚好可以放入一个分组（比如上个例子中，页面大小4KB，每个页表项4B，每个页面可存放1K个页表项，因此每1K个连续的页表项为一组，每组刚好占一个内存块，再讲各组离散地放到各个内存块中)

另外，要为离散分配的页表再建立一张页表，称为页目录表，或称外层页表，或称顶层页表.

两级页表的原理、逻辑地址结构

32位逻辑地址空间，页表项大小为4B，页面大小为4KB，则页内地址占12位

• 单级页表结构的逻辑地址结构

• 多级页表的逻辑地址结构

如何实现地址变换?

1. 按照地址结构将逻辑地址拆分成三部分
2. 从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置
3. 根据二级页号查表，找到最终想访问的内存块号
4. 结合页内偏移量得到物理地址

最终要访问的内存块号为4

该内存块的起始地址为4×4096= 16384

页内偏移量为4095

最终的物理地址为16384 +4095=20479,

两级页表问题需要注意的几个细节

1. 若采用多级页表机制，则各级页表的大小不能超过一个页面.

例:某系统按字节编址，采用40位逻辑地址，页面大小为4KB，页表项大小为4B，假设采用纯页式存储，则要采用（)级页表，页内偏移量为（）位?

页面大小=4KB =$2^{12}$B，按字节编址，因此页内偏移量为12位

页号=40- 12= 28位

页面大小=$2^{12}$B，页表项大小=4B，则每个页面可存放$2^{12}/4 = 2^{10}$个页表项
因此各级页表最多包含$2^{10}$个页表项，需要10位二进制位才能映射到$2^{10}$个页表项，因此每一级的页表对应页号应为10位。总共28位的页号至少要分为三级

两级贝表的访存次数分析（假设没有快表机构)

第一次访存:访问内存中的页目录表

第二次访存:访问内存中的二级页表

第三次访存:访问目标内存单元

基本分段存储方式

分段

进程的地址空间:按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程)，每段从o开始编址.
内存分配规则:以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

由于是按逻辑功能模块划分，用户编程更方便，程序的可读性更高.

LOAD 1,[D] |< A >; //将分段D中A单元内的值读入寄存器1

• 写程序时使用的段名[D]、[A]会被编译程序翻译成对应段号

STORE 1,[X]|< B >; //将寄存器1的内容存入X分段的B单元中

• < A >单元、< B >单元会被编译程序翻译成段内地址

分段系统的逻辑地址由段号（段名）和段内地址（段内偏移量）所组成。如：

• 段号的位数决定了每个进程最多可以分几个段.
• 段内地址位数决定了每个段的最大长度是多少.

在上述例子中，若系统是按字节寻址的，则段号占16位，因此在该系统中，每个进程最多有$2^{16}=64K$个段段内地址占16位，因此每个段的最大长度是$2^{16} =64KB$。

段表

问题:程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称“段表”。

1. 每个段对应一个段表项，其中记录了该段在内存中的起始位置(又称“基址”）和段的长度。
2. 各个段表项的长度是相同的。例如:某系统按字节寻址，采用分段存储管理，逻辑地址结构为（段号16位,段内地址16位），因此用16位即可表示最大段长。物理内存大小为4GB(可用32位表示整个物理内存地址空间）。因此，可以让每个段表项占16+32=48位，即6B。由于段表项长度相同，因此段号可以是隐含的，不占存储空间。若段表存放的起始地址为M，则K号段对应的段表项存放的地址为M＋K×6

分段和分页管理的对比

• 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
• 段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
• 页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
• 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
• 分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。

• 不能被修改的代码称为纯代码或可重入代码（不属于临界资源)，这样的代码是可以共享的。可修改的代码是不能共享的（比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致)

只需让各进程的段表项指向同一个段即可实现共享

• 分页式共享操作

其中绿色的代码段表示可共享数据.

如果让消费者进程的某个页表项指向这个页面，显然不合理，因为这个页面中的橙色部分是不允许共享的,只有绿色部分可以

页面不是按逻辑模块划分的。这就很难实现共享。

• 分页（单级页表)∶第一次访存一一查内存中的页表，第二次访存一一访问目标内存单元。总共两次访存.
• 分段:第一次访存一一查内存中的段表，第二次访存一一访问目标内存单元。总共两次访存.
• 与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。

段页式管理方式

• 段页式管理集合了分页管理和分段管理的优点

• 段号的位数决定了每个进程最多可以分几个段 .
• 页号位数决定了每个段最大有多少页 .
• 页内偏移量决定了页面大小、内存块大小是多少 .

在上述例子中，若系统是按字节寻址的，则段号占16位，因此在该系统中，每个进程最多有$2^{16}=64K$个段

页号占4位，因此每个段最多有$2^4= 16$页

页内偏移量占12位，因此每个页面\每个内存块大小为$2^{12}$= 4096= 4KB

“分段”对用户是可见的,程序员编程时需要显式地给出段号、段内地址。而将各段“分页”对用户是不可见的。系统会根据段内地址自动划分页号和页内偏移量。

因此段页式管理的地址结构是二维的。

每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号(页表起始地址）组成。每个段表项长度相等，段号是隐含的。

每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的。

• 一个程序对应一个段表项，一个段表对应着多个页表，那么在段页式管理的时候，一个程序对应着多个页表

​

其中重要的是第四步，检查页号是否越界，因为每一个段可能对应着多个页面，所以这里需要检查一下页号是否越界了

虚拟内存

• 一次性 :作业必须一次性全部装入内存后才能开始运行。这会造成两个问题:①作业很大时，不能全部装入内存，导致大作业无法运行;②当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。
• 驻留性 :一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。

• 时间局部性:如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）
• 空间局部性:一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的)

• 高速缓冲技术 的思想: 将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中。

虚拟内存的定义和特征

基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。

若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存

操作系统虚拟性的一个体现，实际的物理内存大小没有变, 只是在逻辑上进行了扩充

虚拟内存的最大容量是由计算机的地址结构（CPU寻址范围）确定的

虚拟内存的实际容量= min（内存和外存容量之和，CPU寻址范围)

EG:如:某计算机地址结构为32位，按字节编址，内存大小为512MB,外存大小为2GB

则虚拟内存的最大容量:为$2^{32}B= 4GB$

虚拟内存的实际容量=min ($2^{32}B,512MB+2GB$)= 2GB+512MB

虚拟内存有一下三个主要特征 :

• 多次性:无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
• 对换性:在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换 入、换出。
• 虚拟性:从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。

如何实现虚拟内存技术

虚拟内存技术，允许一个作业分多次调入内存。如果采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上。

• 请求分页和基本分页的主要区别：

  在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。操作系统要提供请求调页(或请求调段）功能

  若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。操作系统要提供页面置换（或段置换）的功能

请求分页管理方式

• 请求分页存储管理与基本分页存储管理的主要区别:
• 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存(操作系统需要提供请求调页功能，将缺失的页面从外存调入内存)，然后继续执行程序。
• 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经调入内存；如果还没调入，那么也需要知道该页面在外存中存放的位置。

当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面；有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。

缺页中断机构

假设此时要访问逻辑地址=(页号，页内偏移量〉= (0,1024)

在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。

此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。

如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

页面置换算法

• 请求分页存储管理与基本分页存储管理的主要区别:
• 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
• 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
• 用页面置换算法决定应该先换出那个页面

最佳置换算法(OPT)

最佳置换算法（OPT，Optimal):每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

例:假设系统为某进程分配了三个内存块，并考虑到有一下页面号引用串（会依次访问这些页面):7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

• 当执行到第四步访问页面二的时候 ：选择从0，1，7中淘汰一页。按最佳置换的规则,往后寻找，最后一个出现的页号就是要淘汰的页面.
• 整个过程缺页中断发生了9次，页面置换发生了6次。
• 注意:缺页时未必发生页面置换。若还有可用的空闲内存块,就不用进行页面置换。
• 缺页率=9/20= 45%

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

先进先出算法(FIFO)

先进先出置换算法（FIFO):每次选择淘汰的页面是最早进入内存的页面.

实现方法:把调入内存的页面根据调入的先后顺序排成一个队列,需要换出页面时选择队头页面即可。

队列的最大长度取决于系统为进程分配了多少个内存块。

例:假设系统为某进程分配了四个内存块，并考虑到有以下页面号引用串:

3，2, 1，0, 3，2，4，3，2，1，0，4

分配四个内存块时:缺页次数:10次.

分配三个内存块时:缺页次数:9次.

• Belady异常―当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
• 只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差,

最近最久未使用置换算法(LRU)

最近最久未使用置换算法（LRU，least recently used):每次淘汰的页面是最近最久未使用的页面.

实现方法:赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。

例:假设系统为某进程分配了四个内存块，并考虑到有以下页面号引用串:1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7

在手动做题时，若需要淘汰页面，可以逆向检查此时在内存中的几个页面号。在逆向扫描过程中最后一个出现的页号就是要淘汰的页面。

该算法的实现需要专门的硬件支持,虽然算法性能好，但是实现困难.

时钟置换算法(Clock)

最佳置换算法性能最好，但无法实现;先进先出置换算法实现简单，但算法性能差﹔最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。

• 时钟置换算法是一种性能和开销较均衡的算法，乂称CLOCK算法，或最近未使用算法（NRU，Not Recently Used）
• 简单的CLOCK算法实现方法:为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)

例:假设系统为某进程分配了五个内存块，并考虑到有以下页面号引用串:1,3,4,2,5,6,3,4,7

当经过1,3,4,2,5之后所有内存块的访问位都被置为1，所以在放入第六个元素的时候，需要循环找出访问位为0的，经过一轮寻找之后，发现没有访问位为0的，但是在我们寻找的过程中，会将访问位为1的转换为0.

改进型的时钟置换算法

• 简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。
• 因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。
• 修改位=0，表示页面没有被修改过;修改位=1，表示页面被修改过。

为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1, 1）表示一个页面近期被访问过，且被修改过。

• 算法规则:将所有可能被置换的页面排成一个循环队列

  • 第一轮:从当前位置开始扫描到第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位. 第一优先级:最近没访问,且没修改的页面

  • 第二轮:若第一轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于替换。本轮将所有扫描过的帧访问位设为0.第二优先级:最近没访问，但修改过的页面

  • 第三轮:若第二轮扫描失败，则重新扫描，查找第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位,第三优先级:最近访问过,但没修改的页面

  • 第四轮:若第三轮扫描失败，则重新扫描，查找第一个(0, 1）的帧用于替换。第四优先级:最近访问过,且修改过的页面

• 由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描.

页面分配策略

驻留集:指请求分页存储管理中给进程分配的物理块的集合。

在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。

考虑一个极端情况，若某进程共有100个页面,则该进程的驻留集大小为100时进程可以全部放入内存，运行期间不可能再发生缺页。若驻留集大小为1，则进程运行期间必定会极频繁地缺页

• 若驻留集太小 ，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少;
• 驻留集太大 ，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

页面分配置换策略

• 固定分配:操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
• 可变分配:先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变.
• 局部置换:发生缺页时只能选进程自己的物理块进行置换。
• 全局置换:可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

全局置换意味着一个进程拥有的物理块数量必然会改变，因此不可能是固定分配

• 固定分配局部置换:系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略的缺点是:很难在刚开始就确定应为每个进程分配多少个物理块才算合理 。(采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数)
• 可变分配全局置换 :刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程;若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页,都将获得新的物理块 ，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。
• 可变分配局部置换 :刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度;反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。

可变分配全局置换:只要缺页就络分配新物理块

可变分配局部置换:要根据发生缺页的频率来动态地增加或减少进程的物理块

调入页面的时机

• 预调页策略 :根据局部性原理(主要指空间局部性 ，即:如果当前访问了某个内存单元，在之后很有可能会接着访问与其相邻的那些内存单元)，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50% 左右。故这种策略主要用于进程的首次调入(运行前调入) ，由程序员指出应该先调入哪些部分。
• 请求调页策略:进程在运行期间发现缺页时才将所缺页面调入内存(运行时调入)。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘lI/O操作，因此I/O开销较大。

系统拥有足够的对换区空间:页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前,需将进程相关的数据从文件区复制到对换区。

系统缺少足够的对换区空间:凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。

• UNIX方式 :运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。

抖动(颠簸)现象

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸 。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够)

• 为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率
• 为了研究为应该为每个进程分配多少个物理块，Denning提出了进程“工作集”的概念

工作机

• 驻留集:指请求分页存储管理中给进程分配的内存块的集合
• 工作集:指在某段时间间隔里，进程实际访问页面的集合。

操作系统会根据“窗口尺寸”来算出工作集。例:某进程的页面访问序列如下，窗口尺寸为4，各时刻的工作集为?

• 工作集大小,可能小于窗口尺寸，实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。如:窗口尺寸为5，经过一段时间的监测发现某进程的工作集最大为3，那么说明该进程有很好的局部性，可以给这个进程分配3个以上的内存块即可满足进程的运行需要。
• 一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。
• 拓展:基于局部性原理可知，进程在一段时间内访问的页面与不久之后会访问的页面是有相关性的。因此，可以根据进程近期访问的页面集合（工作集）来设计一种页面置换算法一一选择一个不在工作集中的页面进行淘汰。

操作系统第四章：文件管理

初识文件管理

一个文件有哪些属性?

• 文件名:由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件。
• 标识符:一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。
• 类型:指明文件的类型
• 位置:文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见)
• 大小:指明文件大小
• 创建时间、上次修改时间.
• 文件所有者信息.
• 保护信息:对文件进行保护的访问控制信息

1. 可以“创建文件”(点击新建后，图形化交互进程在背后调用了“create系统调用”)
2. 可以“读文件”,将文件数据读入内存，才能让CPU处理(双击后,“记事本”应用程序通过操作系统提供的“读文件”功能，即read系统调用,将文件数据从外存读入内存，并显示在屏幕上）
3. 可以“写文件”,，将更改过的文件数据写回外存（我们在“记事本”应用程序中编辑文件内容，点击“保存”后，“记事本”应用程序通过操作系统提供的“写文件”功能，即write系统调用，将文件数据从内存写回外存)
4. 可以“删除文件”（点了“删除”之后,图形化交互进程通过操作系统提供的“删除文件”功能，即delete系统调用，将文件数据从外存中删除)

与内存一样，外存也是由一个个存储单元组成的，每个存储单元可以存储一定量的数据（如1B）。每个存储单元对应一个物理地址

类似于内存分为一个个“内存块”，外存会分为一个个“块/磁盘块/物理块”。每个磁盘块的大小是相等的，每块一般包含2的整数幂个地址（如本例中，一块包含210个地址，即1KB）。同样类似的是，文件的逻辑地址也可以分为（逻辑块号，块内地址），操作系统同样需要将逻辑地址转换为外存的物理地址（物理块号，块内地址）的形式。块内地址的位数取决于磁盘块的大小

操作系统以“块”为单位为文件分配存储空间，因此即使一个文件大小只有10B，但它依然需要占用1KB的磁盘块。外存中的数据读入内存时同样以块为单位

文件的逻辑结构

所谓的“逻辑结构”，就是指在用户看来，文件内部的数据应该是如何组织起来的。而“物理结构”指的是在操作系统看来，文件
的数据是如何存放在外存中的。

类似于数据结构的“逻辑结构”和“物理结构”。

如“线性表”就是一种逻辑结构，在用户角度看来，线性表就是一组有先后关系的元素序列，如: a,b, c, d, e …

“线性表”这种逻辑结构可以用不同的物理结构实现，如:顺序表/链表。顺序表的各个元素在逻辑上相邻，在物理上也相邻;而链表的各个元素在物理上可以是不相邻的。因此，顺序表可以实现“随机访问”，而“链表”无法实现随机访问。

可见，算法的具体实现与逻辑结构、物理结构都有关（文件也一样，文件操作的具体实现与文件的逻辑结构、物理结构都有关)

有结构文件

按文件是否有结构分类，可以分为无结构文件、有结构文件两种

• 无结构文件:文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。如:Windows操作系统中的.txt文件。
• 有结构文件:由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。如:数据库表文件。一般来说，每条记录有一个数据项可作为关键字。根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。

这个有结构文件由可变长记录组成，由于各个学生的特长存在很大区别，因此“特长”这个数据项的长度不确定，这就导致了各条记录的长度也不确定。当然,没有特长的学生甚至可以去掉“特长”数据项。

顺序文件

• 顺序文件:文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储 或链式存储。

• 顺序可边长结构

虽然我们可以得出每一条记录是顺序存储的，但是这条记录的长度却不是固定的， 这时候我们需要使用一个可边长记录表，来记录每条记录的长度，因为每条记录的长度都不是固定的，所以不能够直接找到第i条记录的位置。

结论:定长记录的顺序文件，若物理上采用顺序存储，则可实现随机存取;若能再保证记录的顺序结构,则可实现快速检索(即根据关键字快速找到对应记录)

注:一般来说，考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件。之后的讲解中提到的顺序文件也默认如此。可见，顺序文件的缺点是增加/删除一个记录比较难（如果是串结构则相对简单)

索引文件

对于可变长记录文件，要找到第i个记录，必须先顺序第查找前i-1个记录但是很多应用场景中又必须使用可变长记录。如何解决这个问题

• 索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。

可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。

每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。
另外，可以用不同的数据项建立多个索引表。如:学生信息表中，可用关键字“学号”建立一张索引表。也可用“姓名”建立一张索引表。这样就可以根据“姓名”快速地检索文件了。

(Eg: SQL就支持根据某个数据项建立索引的功能)

顺序索引文件

思考索引文件的缺点:每个记录对应一个索引表项，因此索引表可能会很大。比如:文件的每个记录平均只占8B，而每个索引表项占32个字节，那么索引表都要比文件内容本身大4倍，这样对存储空间的利用率就太低了。

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是:并不是每个记录对应一个索引表项,而是一组记录对应一个索引表项。

若一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序查找（这里指的并不是定长记录、顺序结构的顺序文件），平均须查找5000个记录。

若采用索引顺序文件结构，可把10000个记录分为v10000 =100组，每组100个记录。则需要先顺序查找索引表找到分组（共100个分组，因此索引表长度为100，平均需要查50次〉，找到分组后，再在分组中顺序查找记录（每个分组100个记录，因此平均需要查50次）。可见，采用索引顺序文件结构后，平均查找次数减少为50+50 = 100次。

多级索引顺序文件

为了进一步提高检索效率，可以为顺序文件建立多级索引表。例如，对于一个含$10^6$个记录的文件，可先为该文件建立一张低级索引表，每100个记录为一组，故低级索引表中共有10000个表项(即10000个定长记录），再把这10000个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有100个表项。

文件目录

• 目录文件中的一条记录就是文件控制块（FCB)
• FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项。
• FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。
• 最重要，最基本的还是文件名、文件存放的物理地址。
• FCB 实现了文件名和文件之间的映射。使用户（用户程序)可以实现“按名存取”

文件控制块

• 文件控制块就是FCB的集合

需要对目录进行哪些操作?

搜索:当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项

创建文件:创建一个新文件时，需要在其所属的目录中增加一个目录项

删除文件:当删除一个文件时，需要在目录中删除相应的目录项

显示目录:用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性

修改目录:某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项(如:文件重命名)

单级目录结构

早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。每个文件占一个目录项.

单级目录实现了“按名存取”，但是不允许文件重名.

在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。

显然，单级目录结构不适用于多用户操作系统。

两极目录结构

早期的多用户操作系统，采用两级目录结构。分为主文件目录(MFD，Master File Directory)和用户文件目录（UFD，User Flie Directory）

允许不同用户的文件重名。文件名虽然相同,但是对应的其实是不同的文件

两级目录结构允许不同用户的文件重名,也可以在目录上实现实现访问限制（检查此时登录的用户名是否匹配）。但是两级目录结构依然缺乏灵活性,用户不能对自己的文件进行分类

多级目录结构-树形目录结构

用户(或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。

例如:自拍.jpg的绝对路径是“/照片/2015-08/自拍.jpg”.

系统根据绝对路径一层一层地找到下一级目录。刚开始从外存读入根目录的目录表;找到“照片”目录的存放位置后，从外存读入对应的目录表;再找到“2015-08”目录的存放位置，再从外存读入对应目录表;最后才找到文件“自拍.jpg”的存放位置。整个过程需要3次读磁盘I/O操作。

例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径 ”。

在Linux中，“.”表示当前目录，因此如果“照片”是当前目录，则"自拍.jpg"的相对路径为:

“./2015-08/自拍.jpg”。从当前路径出发，只需要查询内存中的“照片”目录表，即可知道”2015-08”目录表的存放位置，从外存调入该目录，即可知道“自拍.jpg”存放的位置了。

可见，引入“当前目录”和“相对路径”后，磁盘I/O的次数减少了。这就提升了访问文件的效率。

无环图目录结构

在树形目录结构的基础上,增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。可以更方便地实现多个用户间的文件共享。

• 可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）。

• 需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。

• 只有共享计数器减为0时，才删除结点。

• 注意:共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。

索引节点(FCB的改进)

其实在查找各级目录的过程中只需要用到“文件名”这个信息,有文件名匹配时，才需要读出文件的其他信息。因此可以考虑让目录表“瘦身”来提升效率。

思考有何好处?

假设一个FCB是64B，磁盘块的大小为1KB，则每个盘块中只能存放16个FCB。若一个文件目录中共有640个目录项，则共需要占用640/16= 40个盘块。因此按照某文件名检索该目录，平均需要查询320个目录项。

若使用索引结点机制，文件名占14B，索引结点指针站2B，则每个盘块可存放64个目录项，那么按文件名检索目录平均只需耍读入320/64=5个磁盘块。显然，这将大大提升文件检索速度。

当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。

存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。

相比之下内存索引结点中需要增加一些信息，比如:文件是否被修改、此时有几个进程正在访问该文件等。

文件的物理结构

类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。很多操作系统中，磁盘块的大小与内存块、页面的大小相同.

在内存管理中，进程的逻辑地址空间被分为一个一个页面

同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。

于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。

文件的分配方式：连续分配

• 连续分配方式要求每个文件在磁盘上占有一组连续的块。

用户通过逻辑地址来操作自己的文件，操作系统如何实现从逻辑地址到物理地址的映射?

(逻辑块号，块内地址)→(物理块号，块内地址）。只需转换块号就行，块内地址保持不变.

用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB)

• 物理块号=起始块号＋逻辑块号

例如我想要找到文件aaa中逻辑块号为2的地址，我们先要找到aaa对应的FCB中的起始块号4，然后4+2 = 6，最后得出逻辑地址为6

可以直接算出逻辑块号对应的物理块号,因此连续分配支持顺序访问和直接访间（即随机访问).

读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。

结论:连续分配的文件在顺序读/写时速度最快.

• 物理上连续分配的文件A占用了连续的三个块，
• 橙色区域为其他文件已经占用的磁盘块
• 绿色区域为空闲磁盘块
• 若此时文件A要拓展，需要再增加一个磁盘块（总共需要连续的4个磁盘块)。由于采用连续结构，因此文件A占用的磁盘块必须是连续的。
• 因此只能将文件A全部“迁移”到绿色区域。
• 结论:物理上采用连续分配的文件不方便拓展。

橙色区域为非空闲块,绿色区域为空闲磁盘块

若此时创建的新文件大小为3个块,那么无法为其分配足够的存储空间

结论:物理上采用连续分配.

可以用紧凑来处理碎片，但是需要耗费很大的时间代价。

• 优点:支持顺序访问和直接访问（即随机访问)﹔连续分配的文件在顺序访问时速度最快
• 缺点:不方便文件拓展;存储空间利用率低，会产生磁盘碎片

文件的分配方式：链接分配

• 链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。

目录中记录了文件存放的起始块号和结束块号。当然,也可以增加一个字段来表示文件的长度

除了文件的最后一个磁盘块之外，每个磁盘块中都会保存指向下一个盘块的指针,这些指针用户是透明的

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项(FCB)…

从目录项中找到起始块号（即0号块），将0号逻辑块读入内存，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块,再找到2号逻辑块的存放位置…以此类推。

因此，读入i号逻辑块，总共需要i+1次磁盘I/O。

结论:采用链式分配（隐式链接)方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。

结论:采用隐式链接的链接分配方式，很方便文件拓展。

另外,所有的空闲磁盘块都可以被利用，不会有碎片问题外存利用率高。

把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表（FAT,File AllocatIOn Table)

目录中只需记录文件的起始块号

假设某个新创建的文件“aaa”依次存放在磁盘块2→5→0→1

假设某个新创建的文件“bbb”依次存放在磁盘块4→2→3→3

• 注意:一个磁盘仅设置一张FAT。开机时，并常驻内存。FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此“物理块号”字段可以是隐含的。

如何实现文件的逻辑块号到物理块号的转变:

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项(FCB） …

从目录项中找到起始块号，若i>0，则查询内存中的文件分配表FAT往后找到i号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。

结论:采用链式分配（显式链接)方式的文件，支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要依次访问之前的0~i-1号逻辑块），由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。

显然，显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展。

文件的分配方式：索引的分配

• 索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表一一建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

假设某个新创建的文件“aaa”的数据依次存放在磁盘块2→5 → 13 →9。7号磁盘块作为“aaa”的索引块,索引块中保存了索引表的内容。

注:在显式链接的链式分配方式中，文件分配表FAT是一个磁盘对应一张。而索引分配方式中，索引表是一个文件对应一张。

可以用固定的长度表示物理块号（如:假设磁盘总容量为1TB=$2^{40}$B，磁盘块大小为1KB，则共有$2^{30}$个磁盘块，则可用4B表示磁盘块号），因此，索引表中的“逻辑块号”可以是隐含的。

从目录项中可知索引表存放位置,将索引表从外存读入内存，并查找索引表即可知i号逻辑块在外存中的存放位置。

可见，索引分配方式可以支持随机访问。文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可)但是索引表需要占用一定的存储空间.

若每个磁盘块1KB，一个索引表项4B，则一个磁盘块只能存放256个索引项。

如果一个文件的大小超过了256块,那么一个磁盘块是装不下文件的整张索引表的，如何解决这个问题?

• 链接方案
• 多层索引
• 混合索引

链接方案: 如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。

若一个文件大小为256× 256KB =65,536 KB = 64MB

该文件共有256×256个块，也就对应256×256个索引项，也就需要256个索引块来存储，这些索引块用链接方案连起来。

若想要访问文件的最后一个逻辑块,就必须找到最后一个索引块（第256个索引块），而各个索引块之间是用指针链接起来的,因此必须先顺序地读入前255个索引块。

• 多层索引:建立多层索引(原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。

假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。

若某文件采用两层索引，则该文件的最大长度可以到256×256×1KB= 65,536 KB = 64MB

可根据逻辑块号算出应该查找索引表中的哪个表项。如:要访问1026号逻辑块，则1026/256=4，1026%256=2

因此可以先将一级索引表调入内存，查询4号表项，将其对应的二级索引表调入内存，再查询二级索引表的2号表项即可知道1026号逻辑块存放的磁盘块号了。访问目标数据块，需要3次磁盘I/O。

若采用三层索引，则文件的最大长度为256×256×256×1KB = 16GB

类似的，访问目标数据块.

• 采用K层索引结构,且顶级索引表未调内存，则访问一个数据块只需要K+1读磁盘操作

混合索引:多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引(直接指向数据块），又包含一级间接索引（指向单层索引表)、还包含两级间接索引（指向两层索引表)）。

• 索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表―-建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

  若文件太大，索引表项太多，可以采取以下三种方法解决:

  1. 链接方案:如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点:若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0~i-1号索引块,这就导致磁盘I/O次数过多，查找效率低下。
  2. 多层索引:建立多层索引（原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块

     采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K +1次读磁盘操作。缺点:即使是小文件，访问一个数据块依然需要K+1次读磁盘操作。

  3. 混合索引:多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表)、还包含两级间接索引（指向两层索引表）。优点:对于小文件来说，访问一个数据块所需的读磁盘次数更少。
• 超级超级超级重要考点 :
  • 要会根据多层索引、混合索引的结构计算出文件的最大长度(Key:各级索引表最大不能超过一个块)﹔
  • 要能自己分析访问某个数据块所需要的读磁盘次数（Key:FCB中会存有指向顶级索引块的指针，因此可以根据FCB读入.顶级索引块。每次读入下一级的索引块都需要一次读他盘操作。另外，要注意题目条件一一顶级索引块是否已调入内存)

文件存储空间管理

文件存储空间管理：就是对空闲磁盘块的管理.

存储空间的划分和初始化

存储空间管理-空闲表法

适用于连续分配的方式.

如何分配磁盘块:与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。

如何回收磁盘块:与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况

1. 回收区的前后都没有相邻空闲区;
2. 回收区的前后都是空闲区;
3. 回收区前面是空闲区;
4. 回收区后面是空闲区。

• 总之，回收时需要注意表项的合并问题。

操作系统保存着链头、链尾指针。

如何分配:若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。

如何回收:回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作

如何分配：若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据

如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高

存储空间管理-位示图法

• 位示图:每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。位示图一般用连续的“字”来表示，如本例中一个字的字长是16位，字中的每一位对应一个盘块。因此可以用(字号，位号）对应一个盘块号。当然有的题目中也描述为（行号，列号)
• 重要重要重要:要能自己推出盘块号与(字号位号）相互转换的公式。
• 注意题目条件:盘块号、字号、位号到底是从0开始还是从1开始

如本例中盘块号、字号、位号从0开始，若n表示字长，则…

(字号,位号)=(i,j)的二进制位对应的盘块号b=ni+ j

b号盘块对应的字号i= b/n，位号j= b%n

如何分配:若文件需要k个块，

1. 顺序扫描位示图，找到k个相邻或不相邻的“0”;
2. 根据字号、位号算出对应的盘块号，将相应盘块分配给文件;
3. 将相应位设置为“1”。

如何回收:

1. 根据回收的盘块号计算出对应的字号、位号;
2. 将相应二进制位设为“0”

存储空间管理–成组链接法

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。

文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。

• 如何分配
• 需要1个空闲块
  1. 检查第一个分组的块数是否足够。1<100，因此是足够的。
  2. 分配第一个分组中的1个空闲块，并修改相应数据

• 需要100个空闲块
  1. 检查第一个分组的块数是否足够。100=100，是足够的。
  2. 分配第一个分组中的100个空闲块。但是由于300号块内存放了再下一组的信息，因此300号块的数据需要复制到超级块中。

• 假设每个分组最多为100个空闲块，此时第一个分组已有99个块，还要再回收一块。
• 假设每个分组最多为100个空闲块，此时第一个分组已有100个块，还要再回收一块。需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组 。

文件的基本操作

创建文件(create系统调用)

进行Create系统调用时，需要提供的几个主要参数:

1. 所需的外存空间大小（如:一个盘块，即1KB)
2. 文件存放路径（“D:/Demo”)
3. 文件名(这个地方默认为“新建文本文档.txt”)

操作系统在处理Create系统调用时，主要做了两件事:

1. 在外存中找到文件所需的空间（结合上小节学习的空闲链表法、位示图、成组链接法等管理策略，找到空闲空间)
2. 根据文件存放路径的信息找到该目录对应的目录文件（此处就是D:/Demo目录），在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。

删除文件(delete系统调用)

进行Delete系统调用时，需要提供的几个主要参数:

1. 文件存放路径（“D:/Demo”)
2. 文件名（“test.txt”)

操作系统在处理Delete系统调用时，主要做了几件事:

1. 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项。
2. 根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。(回收磁盘块时，根据空闲表法、空闲链表法、位图法等管理策略的不同，需要做不同的处理)
3. 从目录表中删除文件对应的目录项。

读文件(read系统调用)

进程使用read系统调用完成写操作。需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可)，还需要指明要读入多少数据（如:读入1KB）、指明读入的数据要放在内存中的什么位置。

操作系统在处理read系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。

写文件(write系统调用)

进程使用write系统调用完成写操作，需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可)，还需要指明要写出多少数据（如:写出1KB）、写回外存的数据放在内存中的什么位置

操作系统在处理write 系统调用时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存。

打开文件(open系统调用)

在很多操作系统中，在对文件进行操作之前，要求用户先使用open 系统调用“打开文件”，需要提供的几个主要参数:

1. 文件存放路径（“D:/Demo”)
2. 文件名( “test.txt”)
3. 要对文件的操作类型（如: r只读;rw读写等)

操作系统在处理open系统调用时，主要做了几件事:

1. 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户是否有指定的操作权限。
2. 将目录项复制到内存中的“打开文件表”中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件。

将目录表从外存中复制到内存中，以后用户在访问文件的时候，就不需要从新从外存中读取了

关闭文件(close系统调用)

进程使用完文件后，要“关闭文件”操作系统在处理Close系统调用时，主要做了几件事:

1. 将进程的打开文件表相应表项删除
2. 回收分配给该文件的内存空间等资源
3. 系统打开文件表的打开计数器count减1，若count =0，则删除对应表项。

文件共享

注意:多个用户共享同一个文件，意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。

如果是多个用户都“复制”了同一个文件，那么系统中会有“好几份”文件数据。其中一个用户修改了自己的那份文件数据，对其他用户的文件数据并没有影响。

基于索引节点的共享方式(硬链接)

知识回顾:索引结点，是一种文件目录瘦身策略。由于检索文件时只需用到文件名，因此可以将除了文件名之外的其他信息放到索引结点中。这样目录项就只需要包含文件名、索引结点指针。

索引结点中设置一个链接计数变量count，用于表示链接到本索引结点上的用户目录项数。

若count =2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的count值减1。

若count>0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。

当count=0的时候，系统负责删除文件

基于符号链的共享方式(软连接)

当User3访问“ccc”时，操作系统判断文件“ccc”属于Link类型文件，于是会根据其中记录的路径层层查找目录，最终找到User1的目录表中的“aaa”表项，于是就找到了文件1的索引结点。

文件保护

口令保护

为文件设置一个“口令”(如: abc112233），用户请求访问该文件时必须提供“口令”。

口令一般存放在文件对应的FCB或索引结点中 。用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比,如果正确，则允许该用户访问文件

优点:保存口令的空间开销不多，验证口令的时间开销也很小。

缺点:正确的“口令”存放在系统内部，不够安全。

加密保护

使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。

Eg:一个最简单的加密算法―—异或加密，假设用于加密/解密的“密码”为“01001”.

优点:保密性强，不需要在系统中存储“密码”

缺点:编码/译码，或者说加密/解密要花费一定时间。

访问控制

在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access-Control List,ACL)，该表中记录了各个用户可以对该文件执行哪些操作。

有的计算机可能会有很多个用户,因此访问控制列表可能会很大，可以用精简的访问列表解决这个问题

精简的访问列表:以“组”为单位，标记各“组”用户可以对文件执行哪些操作。

如:分为系统管理员、文件主、文件主的伙伴、其他用户几个分组。

当某用户想要访问文件时，系统会检查该用户所属的分组是否有相应的访问权限。

若想要让某个用户能够读取文件，只需要把该用户放入“文件主的伙伴”这个分组即可

文件系统的层次结构

用一个例子来辅助记忆文件系统的层次结构:

假设某用户请求删除文件“D:/工作目录/学生信息.xlsx”的最后100条记录。

1. 用户需要通过操作系统提供的接口发出上述请求一一用户接口.
2. 由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项一一文件目录系统.
3. 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限-----存取控制模块（存取控制验证层).
4. 验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址一一逻辑文件系统与文件信息缓冲区.
5. 知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址一一物理文件系统.
6. 要删除这条记录，必定要对磁盘设备发出请求一一设备管理程序模块.
7. 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收一一辅助分配模块.

磁盘的结构

磁盘，磁道，扇区

磁盘：磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据

磁盘的读写操作

需要把“磁头”移动到想要读/写的扇区所在的磁道。磁盘会转起来，让目标扇区从磁头下面划过，才能完成对扇区的读/写操作。

盘面，柱面

一个盘片可能对应着两个面，上面和下面

每个盘面对应一个磁头

所有的磁头都是连在同一个磁臂上的，因此所有磁头只能“共进退”

所有盘面中相对位置相同的磁道组成柱面,

可用（柱面号，盘面号，扇区号）来定位任意一个“磁盘块”。在“文件的物理结构”小节中，我们经常提到文件数据存放在外存中的几号块，这个块号就可以转换成（柱面号，盘面号，扇区号)的地址形式。

可根据该地址读取一个“块”

1. 根据“柱面号”移动磁臂，让磁头指向指定柱面;
2. 激活指定盘面对应的磁头;
3. 磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读/写。

磁盘的分类

磁头可以移动的称为活动头磁盘。磁臂可以来回伸缩来带动磁头定位磁道

磁头不可移动的称为固定头磁盘。这种磁盘中每个磁道有一个磁头

磁盘调度算法

一次磁盘读/写操作所需要的时间

• 寻找时间（寻道时间）Ts:在读/写数据前，将磁头移动到指定磁道所花的时间。

  1. 启动磁头臂是需要时间的。假设耗时为s;

  2. 移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道。则:寻道时间Ts = s+ m×n

  3. 延迟时间$T_R$:通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r(单位:转/秒，或转/分），则 平均所需的延迟时间TR=(1/2)×(1/r)= 1/(2r)

  4. 传输时间Tt:从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N。

     则:传输时间Tt =(1/r)×(b/N)= b/(rN).

     总的平均存取时间$T_t=T_s+ 1/2r + b/(rN)$.

• 延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间,只能够通过优化寻找时间来进行优化

先来先服务算法

根据进程请求访问磁盘的先后顺序进行调度。

假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道

按照FCFS的规则，按照请求到达的顺序，磁头需要依次移动到55，58、39、18、90、160、150、38、184号磁道

磁头总共移动了45+3+19+21+72+70+10+112+146=498 个磁道

响应一个请求平均需要移动498/9=55.3个磁道(平均寻找长度)

• 优点 : 公平;如果请求访问的磁道比较集中的话，算法性能还算过的去
• 缺点 :如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能 上很差，寻道时间长。

SSTF算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。( 其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优)

假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问55、58、39、18、 90、160、150、38、 184号磁道

磁头总共移动了(100-18) + (184-18) = 248个磁道

响应一个请求平均需要移动248/9=27.5个磁道(平均寻找长度)

优点:性能较好，平均寻道时间短.

缺点:可能产生“饥饿”现象.

本例中，如果在处理18号磁道的访问请求时又来了一个38号磁道的访问请求，处理38号磁道的访问请求时又来了一个18号磁道的访问请求。如果有源源不断的18号、38号磁道的访问请求到来的话，150、160、 184号磁道的访问请求就永远得不到满足，从而产生“饥饿”现象。

产生饥饿的原因： 磁头在一个小区域内来回跳动

扫描算法

SSTF算法会产生饥饿的原因在于:磁头有可能在一个小区域内来回来去地移动。为了防止这个问题,可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法(SCAN)的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。

假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道

磁头总共移动了(200-100) + (200-18) = 282个磁道响应一个请求平均需要移动282/9=31.3个磁道(平均寻找长度)

优点:性能较好，平均寻道时间较短，不会产生饥饿现象.

缺点:

1. 只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。
2. SCAN算法对于各个位置磁道的响应频率不平均(如:假设此时磁头正在往右移动，且刚处理过90号磁道，那么下次处理90号磁道的请求就需要等磁头移动很长一 段距离;而响应了184号磁道的请求之后，很快又可以再次响应184号磁道的请求了)

Look算法

在扫描算法(SCAN) 中，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。LOOK调度算法就是为了解决这个问题，如果在磁头移动方向.上已经没有别的请求，就可以立即改变磁头移动方向。(边移动边观察， 因此叫LOOK)

假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问55、58、39、18、90、160、 150、 38、184 号磁道

磁头总共移动了(184- 100) + (184-18)= 250个磁道响应一个请求平均需要移动250/9=27.5个磁道(平均寻找长度)

优点:比起SCAN算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短

循环扫描算法(C-Scan)

SCAN算法对于各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。

假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道

磁头总共移动了(200-100) + (200-0) + (90-0)= 390个磁道响应一个请求平均需要移动390/9=43.3个磁道(平均寻找长度)

优点:比起SCAN来，对于各个位置磁道的响应频率很平均。

缺点:只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了;并且，磁头返回时其实只需要返回到18号磁道即可，不需要返回到最边缘的磁道。另外，比起SCAN算法来，平均寻道时间更长。

C-LOOK调度算法

C-SCAN算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不- -定需要返回到最边缘的磁道上。C-LOOK 算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。

假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问55、58、39、18、 90、160、 150、38、184 号磁道

磁头总共移动了(184-100) + (184-18) + (90-18)= 322个磁道

响应-一个请求平均需要移动322/9=35.8个磁道(平均寻找长度)

优点:比起C-SCAN算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短

减少磁盘延迟时间的方法

假设要连续读取橙色区域的2、3、4扇区:磁头读取一块的内容(也就是一个扇区的内容)后需要一小段时间处理，而盘片又在不停地旋转,

因此，如果2、3号扇区相邻着排列，则读完2号扇区后无法连续不断地读入3号扇区必须等盘片继续旋转，3号扇区再次划过磁头，才能完成扇区读入

结论:磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的“延迟时间”

减少延迟时间的方法:交替编号

若采用交替编号的策略，即让逻辑上相邻的扇区在物理.上有一-定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。

磁盘地址结构的设计

思考:为什么?磁盘的物理地址是(柱面号，盘面号，扇区号)而不是(盘面号，柱面号，扇区号)

• 答:读取地址连续的磁盘块时，采用(柱面号，盘:面号，扇区号)的地址结构可以减少磁头移动消耗的时间

假设某磁盘有8个柱面/磁道(假设最内侧柱面/磁道号为0)4个盘面，8个扇区。则可用3个二进制位表示柱面，2个二进制位表示盘面，3个二进制位表示扇区。

若物理地址结构是( 盘面号.柱面号.扇区号)，且需要连，续读取物理地址( 00.000.000) ~ (00.001.111)的扇区:(00, 000, 000) ~ ( 00, 000, 111 )转两圈可读完

之后再读取物理地址相邻的区域，即(00.001.000) ~ ( 00.001.111 )，需要启动磁头臂，将磁头移动到下一个磁道.

若物理地址结构是(柱面号，盘面号，扇区号)，且需要连续读取物理地址(000, 00, 000) ~ (000, 01, 111)的扇区:(000.00.000) ~ ( 000.00.111 )由盘面0的磁头读入数据之后再读取物理地址相邻的区域，即(000.01.000) ~ ( 000.01.111 )，由于柱面号/磁道号相同，只是盘面号不同

• 两者的区别就是：如果是连续存储的话，第一种编址方式是存满一个盘面之后再存放下一个盘面，第二种编址方式是：存完这个盘面的这个柱面之后，在存放下一个盘面相同位置的柱面

减少延迟时间的方法：错位命名

如果不采用错位命名的话：就会呈现下面这种情况

0号盘面的0号扇区，对应着一号盘面的0号扇区，如果我们读取的是（000.00.000）--（000.01.111），这时候我们经过了0号页面的两圈旋转，这时候应该访问（000.01.000），但是这时候一号的盘面的指针需要休息，这时候我们不能够读取该位置的数据，需要从新转一圈之后才能读取。这样会大大延长读取时间。

注意，所有盘面都是一起连轴转的

读取完磁盘块( 000.00.111)之后，需要短暂的时间处理，而盘面又在不停地转动，因此当(000.01.000)第一次划过1号盘面的磁头下方时，并不能读取数据，只能再等该扇区再次划过磁头。

由于采用错位命名法，因此读取完磁盘块(000.00.111)之后，还有一段时间处理，当(000.01.000)第一次划过1号盘面的磁头下方时，就可以直接读取数据。从而减少了延迟时间

磁盘的管理

磁盘初始化

磁盘初始化:

Step 1:进行低级格式化(物理格式化)，将磁盘的各个磁道划分为扇区。一个扇区通常可分为头、数据区域(如512B大小)、尾三个部分组成。管理扇区所需要的各种数据结构- -般存放在头、尾两个部分，包括扇区校验码(如奇偶校验、CRC循环冗余校验码等，校验码用于校验扇区中的数据是否发生错误)

Step2:将磁盘分区，每个分区由若干柱面组成(即分为我们熟悉的C盘、D盘、E盘)

Step3:进行逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构( 如位示图、空闲分区表)

引导块

计算机开机时需要进行一系列初始化的工作，这些初始化工作是通过执行初始化程序(自举程序)完成的

初始化程序可以放在ROM ( 只读存储器）中。ROM中的数据在出厂时就写入了，并且以后不能再修改.

注: ROM-般是出厂时就集成在主板上的

初始化程序程序( 自举程序）放在ROM中存在什么问题?

万一需要更新自举程序，将会很不方便，因为ROM中的数据无法更改。如何解决呢?

• 采用自举装入程序
• ROM中只存放很小的“自举装入程序”开机时计算机先运行“自举装入程序”，通过执行该程序就可找到引导块，并将完整的“自举程序”读入内存，完成初始化

• 完整的自举程序放在磁盘的启动块(即引导块/启动分区). 上，启动块位于磁盘的固定位置。
• 拥有启动分区的磁盘称为启动磁盘或系统磁盘(C:盘).

坏块的管理

坏了、无法正常使用的扇区就是“坏块”。这属于硬件故障，操作系统是无法修复的。应该将坏块标记出来，以免错误地使用到它

对于简单的磁盘，可以在逻辑格式化时(建立文件系统时)对整个磁盘进行坏块检查,标明哪些扇区是坏扇区，比如:在FAT表上标明。(在这种方式中， 坏块对操作系统不透明)

对于复杂的磁盘，磁盘控制器(磁盘设备内部的一个硬件部件)会维护-一个坏块链表。

在磁盘出厂前进行低级格式化(物理格式化)时就将坏块链进行初始化。

会保留一些“备用扇区”，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明。

操作系统第五章：I/O设备

IO的概念和分类

IO的概念

“I/O”就是“输入/输出”(Input/Output)

I/O设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件。

Write操作:向外部设备写出数据

Read操作:从外部设备读入数据

IO设备分类—按使用特性分类

• 人机交互类外部设备：数据速度传输慢，鼠标、键盘、打印机等一一用于人机交互
• 存储设备：数据传输块，移动硬盘、光盘等一一用于数据存储
• 网络设备通讯：数据传输速度介于上述两者之间. 调制解调器等一一用于网络通信

IO设备分类—按传输速率分配

• 低速设备：鼠标、键盘一一传输速率为每秒几个到几百字节
• 中速设备: 如激光打印机等一一传输速率为每秒数千至上万个字节
• 高速设备: 如磁盘等一一传输速率为每秒数千字节至千兆字节的设备

IO设备分类—按信息交换的单位分类

• 块设备：如磁盘等一一数据传输的基本单位是“块”，传输速率较高，可寻址，即对它可随机地读/写任一块.
• 字符设备:鼠标、键盘等一一数据传输的基本单位是字符。传输速率较慢，不可寻址，在输入/输出时常采用中断驱动方式.

IO控制器

机械部件

IO设备的机械部件主要用来执行具体IO操作。

如我们看得见摸得着的鼠标/键盘的按钮;显示器的LED屏;移动硬盘的磁臂、磁盘盘面。

IO设备的电子部件通常是一块插入主板扩充槽的印刷电路板。

电子部件

CPU无法直接控制I/O设备的机械部件，因此I/O设备还要有一个电子部件作为CPU和I/O设备机械部件之间的“中介”，用于实现CPU对设备的控制。

这个电子部件就是I/O控制器，又称设备控制器。CPU可控制I/O控制器，又由I/O控制器来控制设备的机械部件。

• IO控制器的功能

  • 接受和识别CPU发出的命令

    如CPU发来的read/write命令，I/O控制器中会有相应的控制寄存器来存放命令和参数

  • 向CPU报告设备的状态

    IO控制器中会有相应的状态寄存器用于记录IO设备的当前状态。如:1表示空闲，0表示忙碌

  • 数据交换

    IO控制器中会设置相应的数据寄存器。输出时，数据寄存器用于暂存CPU发来的数据，之后再由控制器传送设备。输入时,数据寄存器用于暂存设备发来的数据，之后CPU从数据寄存器中取走数据。

  • 地址识别

    类似于内存的地址,为了区分设备控制器中的各个寄存器，也需要给各个寄存器设置一个特定的“地址”。I/O控制器通过CPU提供的“地址”来判断CPU要读/写的是哪个寄存器

IO控制器的组成

• CPU与控制器的接口：

  用于实现CPU与控制器之间的通信。CPU通过控制线发出命令;通过地址线指明要操作的设备;通过数据线来取出（输
  入）数据，或放入(输出）数据

• IO逻辑

  负责接收和识别CPL的各种命令（如地址译码)，并负责对设备发出命令

• 控制器与设备的接口

  用于实现控制器与设备之间的通信

值得注意的小细节:

1. 一个IO控制器可能会对应多个设备;
2. 数据寄存器、控制寄存器、状态寄存器可能有多个(如:每个控制/状态寄存器对应一个具体的设备），且这些寄存器都要有相应的地址，才能方便CPU操作。有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O;另一些计算机则采用I/O专用地址，即寄存器独立编址。

内存映像IO和寄存器独立编址

内存映射I/O。控制器中的寄存器与内存地址统一编址

优点:简化了指令。可以采用对内存进行操作的指令来对控制器进行操作

寄存器独立编制。控制器中的寄存器使用单独的地址

缺点:需要设置专门的指令来实现对控制器的操作，不仅要指明寄存器的地址，还要指明控制器的编号.

IO控制方式

分为四种：程序直接控制方式，中断驱动方式，DMA方式，通道控制方式

需要注意的问题：

1. 完成一次读/写操作的流程
2. CPU干预的频率;
3. 数据传送的单位
4. 数据的流向;
5. 主要缺点和主要优点。

程序直接控制方式

1. CPU向控制器发出读指令于是设备启动，并且状态寄存器设为1（未就绪)
2. 轮询检查控制器的状态(其实就是在不断地执行程序的循环，若状态位一直是1，说明设备还没准备好要输入的数据，于是CPU会不断地轮询) .
3. 输入设备准备好数据后将数据传给控制器，并报告自身状态.
4. 控制器将输入的数据放到数据寄存器中,并将状态改为0（已就绪)
5. CPU发现设备已就绪，即可将数据寄存器中的内容读入CPU的寄存器中,再把CPU寄存器中的内容放入内存.
6. 若还要继续读入数据，则CPU继续发出读指令

1. 完成一次读/写操作的流程（见右图，Key word:轮询)

2. CPU干预的频率

   很频繁，IO操作开始之前、完成之后需要CPU介入，并且在等待I/O完成的过程中CPU需要不断地轮询检查。

3. 数据传送的单位每次读/写一个字

4. 数据的流向

   读操作（数据输入）:I/O设备→CPU(CPU寄存器)→内存

   写操作（数据输出）:内存→CPU→>IO设备

   每个字的读/写都需要CPU的帮助

5. 主要缺点和主要优点

   优点:实现简单。在读/写指令之后，加上实现循环检查的一系列指令即可(因此才称为“程序直接控制方式”)

   缺点:CPU和I/O设备只能串行工作，CPU需要一直轮询检查长期处于“忙等”状态，CPU利用率低。

中断驱动方式

引入中断机制。

由于I/O设备速度很慢，因此在CPU发出读/写命令后，可将等待I/O的进程阻塞，先切换到别的进程执行。

当I/O完成后，控制器会向CPU发出一个中断信号 ，

CPU检测到中断信号后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断。

处理中断的过程中，CPU从I/O控制器读一个字的数据传送到CPU寄存器 ，再写入主存。

接着，CPU恢复等待I/O的进程（或其他进程）的运行环境，然后继续执行。

注意:

1. CPU会在每个指令周期的末尾检查中断;
2. 中断处理过程中需要保存、恢复进程的运行环境，这个过程是需要一定时间开销的。可见，如果中断发生的频率太高，也会降低系统性能。

1. 完成一次读/写操作的流程（见s上图，Key word:中断)

2. CPU干预的频率

   每次I/O操作开始之前、完成之后需要CPU介入。

   在等待I/O完成的过程中CPU可以切换到别的进程执行。

3. 数据传送的单位

   每次读/写一个字

4. 数据的流向

   读操作（数据输入）: I/O设备→>CPU→内存

   写操作（数据输出）:内存→>CPU→>I/O设备

5. 主要缺点和主要优点

   优点:与“程序直接控制方式”相比，在“中断驱动方式”中，I/O控制器会通过中断信号主动报告I/O已完成，CPU不再需要不停地轮询。CPU和I/O设备可并行工作，CPU利用率得到明显提升。

   缺点:每个字在IO设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间。

DMA方式

DR (Data Register，数据寄存器）:暂存从设备到内存，或从内存到设备的数据。

MAR (Memory Address Register，内存地址寄存器)∶

​ 在输入时，MAR表示数据应放到内存中的什么位置;

​ 输出时MAR表示要输出的数据放在内存中的什么位置。

DC ( Data Counter，数据计数器）:表示剩余要读/写的字节数。

CR(Command Register，命令/状态寄存器)︰用于存放CPU发来的I/O命令，或设备的状态信息。

• 虽然宏观上是一块一块的读入，但是在微观上，还是一个字节一个字节的进行读入的，读入的字节现在放在DR中，然后通过MAR放到内存中

1. 完成一次读/写操作的流程（见右图)

1. CPU干预的频率

   仅在传送一个或多个数据块的开始和结束时，才需要CPU千预。

2. 数据传送的单位

   每次读/写一个或多个块（注意:每次读写的只能是连续的多个块.

   如果不是连续的话我们需要CPU给出多条指令

3. 数据的流向（不再需要经过CPU)

   读操作（数据输入） : I/O设备→内存

   写操作（数据输出）:内存→I/O设备

4. 主要缺点和主要优点

   优点:数据传输以“块”为单位，CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加。CPU和I/O设备的并行性得到提升。

   缺点:CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块。

通道控制方式

通道:一种硬件，可以理解为是“弱鸡版的CPU”。通道可以识别并执行一系列通道指令.