Operating System

CS专业课学习笔记

操作系统介绍

概念

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

功能和目标

作为系统资源的管理者

作为用户和计算机硬件之间的接口

• 用户接口
  • 命令接口：允许用户直接使用， 分为联机命令接口和脱机命令接口
  • 程序接口：允许用户通过程序间接使用，由一组系统调用组成（程序接口=系统调用）

作为最接近硬件的层次

小节1.2

四个特征

操作系统的特征：并发，共享，虚拟，异步。其中，并发和共享是最基本的特征，二者互为存在条件

并发

并发：两个或者多个事件在同一时间间隔内发送。这些事件宏观上是同时发生的，但是微观上是交替发生的

易混概念–并行：指两个或多个事件在同一时刻同时发生

操作系统的并发性指计算机系统中同时存在着多个运行着的程序。

并发性：计算机系统中同时存在着多个运行着的程序

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

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

共享

共享：指系统中的资源可供内存中多个并发执行的进程共同使用

共享性：系统中的资源可供内存中多个并发执行的进程共同使用

• 互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但是一个时间段内只允许一个进程访问该资源
  • 例如：使用QQ和微信视频。同一时间段内摄像头只能分配给其中一个进程
• 同时共享方式：系统中某些资源，允许一个时间段内由多个进程“同时”对它们进行访问
  • 例如：使用QQ发送文件A，同时使用微信发送文件B。宏观上看，两边都在同时读取并发送文件，说明两个进程都在访问硬盘资源，从中读取数据。微观上看，两个进程是交替着访问硬盘的。

虚拟

虚拟：把物理上的实体变为若干个逻辑上的对应物。物理实体是实际存在的，而逻辑上对应物是用户感受到的。

举例1：

一个程序需要放入内存并给他分配CPU才能运行

某个游戏需要4GB的运行内存，QQ需要256MB的内存，迅雷需要256MB的内存，网易云音乐需要256MB的内存等等，但是电脑只有4GB内存。

问题：这些程序同时运行需要的内存远大于4GB，那么为什么他们还可以在电脑上同时运行起来呢？

回答：应用了虚拟存储器技术。实际上只有4GB的内存，在用户看起来似乎远远大于4GB。这就是虚拟技术中的空分复用技术

举例2：

某单核CPU的计算机中，用户打开了微信，QQ，Word，Chrome浏览器，QQ音乐

问题：既然一个程序需要被分配CPU才能正常执行，那么为什么单核CPU的电脑中能同时运行这么多个程序呢？

回答：应用了虚拟处理器技术。实际上只有一个单核CPU，在用户看来似乎有5个CPU在同时为自己服务。这就是虚拟技术中的时分复用技术，微观上处理机在各个微小的时间段内交替着为各个进程服务。

异步

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

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

发展和分类

手工操作阶段

• 主要缺点：用户独占主机，人机速度矛盾导致资源利用率极低

批处理阶段

单道批处理系统：

引入脱机输入/输出技术（用磁带完成），并监督程序负责控制作业的输入，输出

• 主要优点：缓解了一定程度的人机速度矛盾，资源利用率有所提升
• 主要缺点：内存中仅能有一道程序运行，只有该程序运行结束之后才能调入到下一道程序。CPU有大量的时间是在空闲等待I/O完成。资源利用率依然很低。

多道批处理系统：

每次往内存中输入多道程序。操作系统正式诞生，并引入了中断技术，由操作系统复杂管理这些程序的运行。各个程序并发执行。

• 主要优点：多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源保持“忙碌”状态，系统吞吐量增大。
• 主要缺点：用户响应时间长，没有人机交互功能（用户提交自己的作业之后就只能等待计算机处理完成，中间不能控制自己的作业执行）

分时操作系统

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

• 主要优点：用户请求可以被即时相应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到人的存在。
• 主要缺点：不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不分区任务的紧急性。

实时操作系统

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

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

实时操作系统可分为以下2类：

• 硬实时操作：必须在绝对严格的规定事件内完成处理，如导弹控制系统，自动驾驶系统
• 软实时系统：能接受偶尔违反事件规定，如12306火车订票系统

其他几种操作系统

• 网络操作系统：是伴随着计算机网络的发展而诞生的，能把网络中各个计算机有机地结合起来，实现数据传送等功能，实现网络中各种资源地共享（如文件共享）和各台计算机之间地通信。（如：Windows NT就是一种典型地网络操作系统，网站服务器就可以使用）
• 分布式操作系统：主要特点是分布性和并行性。系统中地各台计算机地位相同，任何工作都可以分布在这些计算机上，由它们并行，协调完成这个任务。
• 个人计算机操作系统：如：Windows XP，MacOS，个人方便使用

小节1.4

OS运行机制和体系架构

运行机制

两种指令

有的指令没有什么危害，比如：加减乘除这些普通的运算指令。

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

• 特权指令：不允许普通用户程序使用，如内存清零指令
• 非特权指令：如普通的运算指令

两种处理器状态

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

• 用户态（目态）：此时CPU只能执行非特权指令
• 核心态（管态）：特权指令，非特权指令都可以执行

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

两种程序

• 内核程序：操作系统的内核程序是系统的管理者，既可以执行特权指令，也可以执行非特权指令，运行在核心态
• 应用程序：为了保证系统能安全运行，普通应用程序只能执行非特权指令，运行在用户态

操作系统内核

问题：操作系统中的哪些功能应该由内核程序实现呢？

内核是计算机上配置的底层软件，是操作系统最基本，最核心的部分，实现操作系统内核功能的那些程序就是内核程序

操作系统的体系结构

• 大内核
  • 将操作系统的主要功能模块都作为系统内核，运行在核心态
  • 优点：高性能
  • 缺点：内核代码庞大，结构混乱，难以维护
• 微内核
  • 只把最基本的功能保留在内核
  • 优点：内核功能少，结构清晰，方便维护
  • 缺点：需要频繁地在核心态和用户态之间切换，性能低

中断和异常

中断机制的诞生

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

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

引入中断机制后，可以把多道程序同时放入到内存，各个程序并发的执行。

• 最开始是第一道程序，它在用户态下，CPU收到计时部件发出的中断信号，切换为核心态对中断进行处理
• CPU接着进入核心态，把CPU的权限交给操作系统，操作系统内核负责对中断信号进行处理，进程1的时间片已用完，换进程2运行，再完成这一系列工作后，操作系统会把CPU使用权交还给用户进程，接下来进程2就会在用户态下执行
• 进程2发出系统调用（内中断信号），请求输出。CPU切换为核心态，对中断进行处理
• 为了保证系统的安全性，输入输出操作相应的指令是特权指令，不允许用户进程直接使用，因此这些应用程序只能通过系统调用的方式，来主动的要求操作系统接入工作，让操作系统代它完成输出操作
• CPU接着进入核心态，操作系统内核负责对中断信号进行处理，并按照进程2要求打印机设备开始工作，由于进程2要等待I/O设备的完成，所以会让进程2暂停运行，换进程3运行，完成这一系列工作后，操作系统会把CPU使用权交还给用户进程，接下来进程3就会在用户态下执行
• 并且输出设备在操作系统的要求下并行的工作，当它工作结束之后，会向CPU发出I/O完成的中断信号
• CPU收到I/O设备发来的中断信号，切换为核心态对中断进行处理

中断的概念和作用

上述操作总结如下

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

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

问题：用户态，核心态之间的切换是怎么实现的？

"用户态到核心态"是通过中断实现的。并且中断是唯一途径

“核心态到用户态"是通过执行一个特权指令，将程序状态字（PSW）的标志位设置为"用户态”

中断的分类

• 中断是一种在系统内硬件产生的流量变化。中断操作装置是用来处理中断请求；然后返回控制中断的上下文和指令
  • 中断可以被用来标志I/O的完成，从而排除设备投票站(device polling)的需要
• 陷阱是软件产生的冲断，比如用视频软件放一个电影，视频软件就发出陷阱使用显示器和声卡从而访问硬件。
  • 陷阱可以被用来调用操作系统的程序或者捕捉到算术错误

外中断的处理过程

系统调用(System call)

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

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

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

系统调用（按功能分类）：

• 设备管理：完成设备的请求/释放/启动等功能
• 文件管理：完成文件的读/写/创建/删除等功能
• 进程控制：完成进程的创建/撤销/堵塞/唤醒等功能
• 进程通信：完成进程之间的消息传递/信号传递/启动等功能
• 内存管理：完成内存的分配/回收等功能

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

系统调用与库函数的区别

系统调用背后的过程

进程1(process)

程序：就是一个指令序列

在早期的计算机，只支持单道程序，因此在同一时间段内，只能有一道程序正在运行，CPU只为这个程序服务，内存当中也只会存放程序相关的信息，除此之外，I/O设备，所有的系统资源都是为当前执行的程序服务的，

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

引入多道程序技术以后：计算机当中同一时刻可以有多道程序并发地在运行，内存当中也会有相应地多道数据，由于内存中同时放入多道程序，各个程序的代码，运算数据存放的位置不同。操作系统要怎么才能找到各程序的存放位置呢？

为了方便操作系统管理，完成各程序并发执行，引入了进程，进程实体的概念。操作系统为每个运行的程序配置了一个数据结构，称为进程控制块（Process Control Block, PCB），用来描述进程的各种信息（如程序代码存放位置）。

进程的定义

程序段，数据段，PCB三部分组成了进程实体（进程映像）。一般情况下，我们把进程实体就简称为进程，例如，所谓的创建进程，实质上是创建进程实体中的PCB，而撤销进程，实质上是撤销进程实体中的PCB。

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

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

严格地说，进程实体和进程并不一样，进程实体是静态的，进程强调动态性。

进程的组成

PCB的组成：

• 进程描述信息
  • 进程标识符PID：当进程被创建时，操作系统会为该进程分配一个唯一的，不重复的ID，用于区分不同的进程
  • 用户标识符UID
• 进程控制和管理信息
  • 进程当前状态
  • 进程优先级
• 资源分配清单
  • 程序段指针
  • 数据段指针
  • 键盘
  • 鼠标
• 处理机相关信息
  • 各种寄存器值：当进程切换时需要把进程当前的运行情况记录下来保存在PCB中，如程序计数器的值表示了当前程序执行到了哪一句

PCB是进程的管理者，操作系统所需的数据都在PCB中， 而程序段和数据段存放的是程序本身的运行所需的数据。

进程的组织方式

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

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

• 链接方式
  • 按照进程状态将PCB分为多个序列
  • 操作系统持有指向各个队列的指针
    • 执行指针：指向当前处于运行状态的进程
    • 就绪队列指针：会把优先级高的放在前面
    • 阻塞队列指针
• 索引方式
  • 根据进程状态不同，建立几张索引表
  • 操作系统持有指向各个索引表的指针

进程的特征

• 动态性
  • 进程是程序的一次执行的过程
• 并发性
  • 内存中有多个进程实体，各进程可并发执行
• 独立性
  • 进程是能独立运行，独立获得自由，独立接受调度的基本单位
• 异步性
  • 各进程按自独立的，不可预知的速度向前前进
• 结构性
  • 每个进程都会配置一个PCB，由程序段，数据段，PCB组成

进程的状态与转换

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

• 运行态(Running)
  • 占有CPU，并在CPU上运行
• 就绪态(Ready)
  • 已经具备运行条件，但是由于没有空闲CPU，而暂时不能运行
• 阻塞态(Waiting/Blocked)
  • 因等待某一事件而暂时不能运行
• 创建态(New)
  • 进程正在被创建，操作系统为进程分配资源，初始化PCB
• 终止态(Terminated)
  • 进程正在从系统中撤销，操作系统会回收进程拥有的资源，撤销PCB

注意：单核处理机环境下，每一时刻最多只有一个进程处于运行态。（双核环境下可以同时有两个进程处于运行态）

不能由阻塞态直接转换为运行态，也不能由就绪态直接转化为阻塞态（因为进入阻塞态是进程主动请求的，必然需要进程在运行时才能发出这种请求）

进程的挂起态与七状态模型

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

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

小节2.5

进程控制

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

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

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

简单的说：进程控制就是要实现进程状态转换，无论哪个原语，要做的无非三类事情：

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

进程的创建

进程的终止

进程的阻塞和唤醒

进程的切换

进程通信

进程通信就是进程之间的信息交换

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

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

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

共享存储

消息传递

管道通信

进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的"发送消息/接受消息"两个原语进行数据交换

线程(thread)

有的进程可能需要"同时"做很多事情，而传统的进程只能串行地执行一系列程序。为此，引入了"线程"，来增加并发度

可以把线程理解成"轻量级进程"。

线程是一个基本的CPU执行单元，也是程序执行流的最小单位

引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内可以并发处理各种任务（如QQ视频，文字聊天，传文件）

引入线程之后，进程只作为除CPU之外的系统资源分配单元（如打印机，内存地址空间等都是分配给进程的）

线程的属性

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

线程的实现方式

用户级线程(ULT)

用户级线程由应用程序通过线程库实现。所有的线程管理工作都由应用程序负责（包括线程切换）

用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预

在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。（用户级线程对用户不透明，对操作系统透明）

内核级线程(KLT)

内核级线程的管理工作是由操作系统内核完成。线程调度，切换等工作都由内核负责，因此，内核级线程的切换必然需要在核心态下才能完成

ULT+KLT

在同时支持用户级线程和内核级线程的系统中，可采用二者组合的方式：将n个用户级线程映射到m个内核级线程上（n $\geq$ m）

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

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

多线程模型

在同时支持用户级线程和内核级线程的系统中，由几个用户级线程映射到几个内核级线程的问题引出了"多线程模型"问题

多对一模型

多对一模型：多个用户及线程映射到一个内核级线程，每个用户进程只对应一个内核级线程

• 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
• 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并发运行

一对一模型

一对一模型：一个用户级线程映射到一个内核级线程，每个用户进程有与用户级线程同数量的内核级线程

• 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强，多线程可以在多核处理器上并行执行
• 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大

多对多模型

多对多模型：n用户级线程映射到m个内核级线程上，每个用户进程对应m个内核级线程

• 优点：克服了多对一模型并发度不高的缺点，又克服了一对一模型中一个用户进程占用太多内核级线程，开销大的缺点

处理机调度

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

在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行

高级调度(作业调度)

由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定将作业调入内存的顺序

高级调度(作业调度)按一定的原则从外存上处于后备序列的作业中挑选一个（或多个）作业，给他们分配内存等必要资源，并建立相应的进程（PCB），以使它们获得竞争处理机的权力

高级调度是外存（辅存）与内存之间的调度。每个作业只调入一次，调出一次，作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出

中级调度(内存调度)

引入了虚拟存储技术，可将暂时不能运行的进程调至外存等待，等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。这么做的目的是为了提高内存利用率和系统吞吐量

暂时调到外存等待的进程状态为挂起状态。值得做注意的是，PCB并不会一起被调到外存，而是会常驻内存，PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控，管理，被挂起的进程PCB会被放到挂起队列中

中级调度是决定将哪个处于挂起状态的进程重新调入内存

一个进程可能会被多次调出，调入内存，因此中级调度发生的频率要比高级调度更高

低级调度(进程调度)

低级调度(进程调度)的主要任务时按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次

进程调度时机

进程调度需要进行进程调度与切换的时候：

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

进程调度不能进行进程调度与切换的时候：

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

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

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的PCB组成）

当一个进程处于内核程序临界区，并且这个临界区是要访问就绪队列时：在访问之前会把就绪队列上锁，如果还没退出临界区（还没上锁）就进行进程调度，但是进程调度相关的程序也需要访问就绪队列，但此时就绪队列被锁住了，因此又无法顺利进行进程调度。所以对于内核程序临界区访问的临界资源如果不尽快释放的话，极有可能影响到操作系统内核的其他管理工作。因此在访问内核程序临界区期间不能进行调度与切换

另外一种情况，当一个进程访问的是普通临界资源（例如打印机）时：在访问之前会把它上锁，在打印机打印完成之前，进程一直处于临界区内，临界资源不会解锁。但打印机又是慢速设备，此时如果一直不允许进程调度的话就会导致CPU一直空闲。普通临界区访问的临界资源不会直接影响操作系统内核的管理工作，因此在访问普通临界区时可以进行调度与切换

进程调度方式

非剥夺调度方式，又称非抢占方式。即只允许进程主动放弃处理机。在运行过程中即便有更紧急的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态

这种方式实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统

剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧急的进程需要使用处理机，则立刻暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程

这种方式可以优先处理更紧急的进程，也可以实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统，实时操作系统

进程调度切换与过程

• 狭义的进程调度：从就绪队列中选中一个要运行的进程
• 进程切换：一个进程让出处理机，由另一个进程占用处理机
• 广义的进程调度：包含了选择一个进程和进程切换两个步骤

进程调度切换的过程主要完成了：

1. 对原来进程的各种数据的保存
2. 对新的进程各种数据的恢复（如：程序计数器，程序状态字，各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块PCB中）

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

调度算法的评价指标

• CPU利用率：指CPU忙碌的时间占总时间的比例
• 系统吞吐量：单位时间内完成作业数量
• 周转时间：从作业被提交给系统开始，到作业完成为止这段时间间隔
  • 作业在外存后备队列上等待高级调度（作业调度）的时间
  • 作业在就绪队列上等待低级调度（进程调度）的时间
  • 进程在CPU上执行的时间
  • 进程等待I/O操作完成的时间
• 带权周转时间：作业周转时间 / 作业实际运行时间 $\geq 1$
• 等待时间：指进程/作业处于等待处理机状态时间之和（等待I/O不算）
• 响应时间：指从用户提交请求到首次产生响应所用的时间

调度算法

先来先服务(FCFS)

短作业优先(SJF)

高响应比优先(HRRN)

时间片轮转调度算法(RR)

优先级调度算法

多级反馈队列调度算法

调度算法总结

FCFS，SJF/SPF，HRRN这几种算法主要关心对用户的公平性，平均周转时间，平均等待时间等评价系统整体性能的指标，但不关心响应时间，也不区分任务的紧急程度，因此对用户来说交互型很差。因此这三种算法一般适合于早期的批处理系统，当然，FCFS算法也常结合其他算法使用，扮演着很重要的角色

比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统（包括分时操作系统，实时操作系统等）更注重系统的响应时间，公平性，平衡性等指标。而时间片轮转调度算法(RR)，优先级调度算法，多级反馈队列调度算法这三种算法恰好较好满足了交互式系统的需求，因此适用于交互式系统（比如UNIX使用的就是多级反馈队列调度算法）

进程2(process)

进程同步

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

例如：进程通信——管道通信中，读进程和写进程并发地运行，由于并发必然导致异步性，因此，写数据和读数据两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照写数据 $\rightarrow$ 读数据的顺序来执行。如何解决这种异步问题，就是进程同步所讨论的内容

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

进程互斥

两种资源共享方式：

• 互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但是一个时间段内只允许一个进程访问该资源
  • 例如：使用QQ和微信视频。同一时间段内摄像头只能分配给其中一个进程
• 同时共享方式：系统中某些资源，允许一个时间段内由多个进程“同时”对它们进行访问
  • 例如：使用QQ发送文件A，同时使用微信发送文件B。宏观上看，两边都在同时读取并发送文件，说明两个进程都在访问硬盘资源，从中读取数据。微观上看，两个进程是交替着访问硬盘的。

临界资源：一个时间段内只允许一个进程使用的资源，各进程需要互斥地访问临界资源。许多物理设备（摄像头，打印机）都属于临界资源。此外还有许多变量，数据，内存缓冲区等都属于临界资源

对临界资源的访问，必须是互斥地进行，互斥亦称简介制约关系

进程互斥：指当一个进程访问某临界资源时，另一个想要访问该资源地进程必须等待。当前访问临界资源地进程访问结束，释放该资源之后，另一个进程才能去访问临界资源

对临界资源地互斥访问，可以在逻辑上分为如下四个部分：

• 进入区：负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志，以阻止其他进程同时进入临界区
• 临界区：访问临界资源的那段代码
• 退出区：负责解除正在访问临界资源的标志
• 剩余区：其他处理

进程互斥的原则

问题：如果一个进程暂时不能进入临界区，那么该进程是否应该一直占着处理机？该进程有没有可能一直进不了临界区？

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

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

进程互斥的软件实现方法

单标志法

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

该算法可以实现同一时刻最多只允许一个进程访问临界区，且是轮流访问的，这种方法的主要问题是：违背空闲让进原则

双标志先检查法

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

若按照1-5-2-6-3-7的顺序执行，P0和P1将会同时访问临界区，因此，双标志先检查法的主要问题是：违反忙则等待原则

双标志后检查法

算法思想：前一个算法的问题是先检查后上锁，但是两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，就有了先上锁后检查的方法来避免上述问题

若按照1-5-2-6的顺序执行，P0和P1将都无法进入临界区，因此，双标志后检查法虽然解决了忙则等待问题，但又违背了空闲让进和有限等待原则，会因各进程都长期无法访问临界资源而产生饥饿现象

Peterson算法(1981)

算法思想：双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。Gary L. Peterson提出：如果双方都争着想进入临界区的话，可以让进程尝试"孔融让梨"，主动让对方使用临界区

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

进程互斥的硬件实现方法

信号量机制

进程互斥的4种软件实现方式和3种硬件实现方式都无法实现让权等待，1965年，荷兰学者Dijkstra提出一种卓有成效的实现进程互斥，同步的方法——信号量机制

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

信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量

• 知识回顾：原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的
• 一对原语：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数。wait和signal原语简称为P，V操作，P=wait，V=signal

整型信号量

用一个整数型的变量作为信号量，用来表示系统中的某种资源的数量。与普通整数变量的区别：对信号量的操作只有3种，即初始化，P操作和V操作

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

// eg. 某计算机系统中有一台打印机

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

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

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

// 进程P0
wait(S);    // 进入区，申请资源
use();      // 临界区，访问资源
signal(S);  // 退出区，释放资源

整型信号量检查和上锁一气呵成，避免了并发，异步导致的问题。存在的问题：不满足让权等待原则，会发生忙等

记录型信号量

整型信号量存在忙等问题，因此提出了记录型信号量，即用记录型数据结构表示数据量

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

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

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

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

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

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

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

信号量机制实现进程互斥

信号量机制实现进程同步

信号量机制实现前驱关系

生产者-消费者模型

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。

• 它们共享一个初始为空，大小为n的缓冲区
• 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待
• 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待
• 缓冲区是临界资源，各进程必须互斥地访问

生产消费者模型中，实现互斥的P操作一定要在实现同步的P操作后，否则发生死锁。V操作不会导致进程阻塞，因此两个V操作顺序可以互换

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

多生产者-多消费者模型

吸烟者问题

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

读者-写者问题

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

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

哲学家进餐问题

各哲学家拿筷子这件事情必须互斥地执行。这就保证了即使一个哲学家在拿到筷子一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭地哲学家放下筷子后，被阻塞地哲学家就可以获得等待地筷子了

哲学家进餐问题的关键在于解决进程死锁。这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有"死锁"问题的隐患

管程

为什么要引入管程

信号量机制存在的问题：编写程序困难，易出错。所以人们考虑能不能设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松呢？1973年，Brinch Hansen首次在程序设计语言(Pascal)中引入了"管程"成分——一种高级同步机制

管程的定义和基本特征

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

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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

monitor ProducerConsumer
  // 条件变量用来实现同步（排队）
  condition full, empty;
  // 缓冲区中的产品数
  int count = 0;
  // 吧产品item放入缓冲区
  void insert(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;

// 生产者进程
producer(){
  while(1){
    item = 生产一个产品;
    ProducerConsumer.insert(item);
  }
}

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

由编译器复制实现各进程互斥地进入管程中的过程，程序员在写程序时不需要关心如何实现互斥，只需直接调用管程提供的方法

每次仅允许一个进程在管城内执行某个内部过程。例如：两个生产者进程并发执行，依次调用了insert过程（函数），刚开始由于没有进程正在访问管程中的insert函数，所以第一个进程调用insert函数的时候是可以顺利执行下去的。如果第一个进程还没有执行完函数中的逻辑的时候，第二个进程尝试着也想调用insert函数，那么由于编译器实现了这些功能，会暂时阻止第二个进程进入insert函数，就会把第二个进程阻塞在insert后面

管程中设置条件变量和等待/唤醒操作，以解决同步问题

例如：两个消费者进程先执行，生产者进程后执行，第一个消费者进程在执行时首先调用了remove函数，count=0，于是它需要执行wait，也就是等待操作，于是第一个进程会等待在empty相关队列中，同样的，第二个消费者进程开始执行remove函数时，也会发现此时count的值为0，所以也需要执行等待操作。之后，如果有生产者进程执行，它会把它生产的item放入insert_item()中，并且看自己放入的产品是不是缓冲区的第一个产品，如果是第一个产品，意味着可能有别的消费者进程在等待，所以接下来生产者进程会执行唤醒操作signal，用来唤醒等待在empty队列当中某一个进程，唤醒后可以继续往后执行count–，如果说缓冲区之前是满的(count == N-1)，那么意味着有可能有生产者进程需要被唤醒，于是消费者进程会调用signal操作，最后消费者得到它要的item。

总结如下：

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

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

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

Java中类似于管程地机制

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

1
2
3
4
5
6
7
8

static class monitor{
  private Item butter[] = new Item[N];
  private int count = 0;

  public synchronized void insert(Item item){

  }
}

每次只能有一个线程进入insert函数，如果多个线程同时调用insert函数，则后来者需要等待排队

死锁(Deadlock)

死锁的概念

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

死锁产生的必要条件

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

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

注意，发生死锁时一定有循环等待，但是发生循环等待时未必死锁

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

预防死锁

避免死锁

检测和解除死锁

内存

内存的基础知识

存储单元与内存地址

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

内存中有一个个的小空间，每个小空间就是一个存储单元，内存地址从0开始，每个地址对应一个存储单元。

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

逻辑地址 vs 物理地址

相对地址又称逻辑地址，绝对地址又称物理地址。编译时产生的指令只关心"相对地址"，实际放入内存中时再想办法根据起始位置得到"绝对地址"

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

从写程序到程序运行

• 编译：由编译程序将用户源代码编译成若干个目标模块（编译就是把高级语言翻译为机器语言）
• 链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块，链接后形成完整的逻辑地址
• 装入（装载）：由装入程序将装入模块装入内存运行，装入后形成物理地址

链接的三种方式：

1. 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开
2. 装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式
3. 运行时动态链接：在各程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享

装入的三种方式（用三种不同的方法完成逻辑地址到物理地址的转换）：

1. 绝对装入
2. 静态重定位
3. 动态重定位

参考计算机系统结构寻址部分

绝对装入

绝对装入：在编译时，如果直到程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存

静态重定位

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

动态重定位

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

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

内存管理的概念

操作系统负责内存空间的分配与回收

操作系统需要提供某种技术从逻辑上对内存空间进行扩充（覆盖技术，交换技术，虚拟储存器技术）

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

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

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

内存保护可采取的两种方法：

1. 在CPU中设置一对上，下限寄存器，存放进程的上，下限地址。进程的指令要访问某个地址时，CPU检查是否越界
2. 采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址

内存空间的扩充

• 覆盖技术
• 交换技术
• 虚拟存储技术

覆盖技术

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

• 需要常驻内存的段放在固定区中，调入后就不再调出（除非运行结束）
• 不常用的段放在覆盖区中，需要用到时调入内存，用不到时调出内存

必须由程序员声明覆盖结构，操作系统完成自动覆盖。缺点：对用户不透明，增加了用户编程负担

交换技术

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

中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存

1. 应该在外存（磁盘）的什么位置保存被换出的进程？
2. 什么时候应该交换？
3. 应该换出哪些进程？

• 具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分
  • 文件区主要用于存放文件，主要追求储存空间利用率，因此对文件区空间的管理采用离散分配方式
  • 对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。对换区空间的管理主要追求换入换出速度，采用连续分配方式，即对换区的I/O速度比文件区的更快
• 交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停
  • 例如：在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程；如果缺页率明显下降，就可以暂停换出
• 可优先换出阻塞进程；可换出优先级低的进程
  • 为了防止优先级低的进程在被调入内存后很快又被调出，有的系统还会考虑进程在内存的驻留时间。（注意：PCB会常驻内存，不会被换出外存）

内存空间的分配与回收

• 连续分配管理方式
  • 单一连续分配
  • 固定分区分配
  • 动态分区分配
• 非连续分配管理方式

连续分配：指为用户进程分配的必须是一个连续的内存空间

单一连续分配

固定分区分配

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

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

固定分区分配的优点：实现简单，无外部碎片。缺点：a.当用户程序太大，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；b.会产生内部碎片，内存利用率低

动态分区分配

动态分区分配又称为可变分区分配，这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区地大小正好适合进程的需要。因此系统分区的大小和数目是可变的

动态分区分配没有内部碎片，但是有外部碎片

• 内部碎片：分配给某进程的内存区域中，有些部分没有用上
• 外部碎片：是指内存中的某些空间分区由于太小而难以利用

如果内存中空闲空间的总和本来可以满足某进程的需求，但由于进程需要的是一整块连续的内存空间，因此这些"碎片"不能满足进程的需求。这时，可以通过紧凑（拼凑，Compaction）技术来解决外部碎片

回收内存分区时，可能遇到四种情况：

1. 回收区之后有相邻的空闲分区
2. 回收区之前有相邻的空闲分区
3. 回收区之前，后都有相邻的空闲分区
4. 回收区之前，后都没有相邻的空闲分区

总之，相邻的空闲分区要合并

动态分区分配算法

• 动态分区分配算法
  • 首次适应算法(First Fit)
  • 最佳适应算法(Best Fit)
  • 最坏适应算法(Worst Fit)
  • 邻近适应算法(Next Fit)

首次适应算法(First Fit)：每次都从低地址开始查找，找到第一个能满足大小的空闲分区

如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区

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

最佳适应算法(Best Fit)：为了保证当"大进程"到来时能有连续的大片空间，可以尽可能地多留下大片地空闲区，即优先使用更小地空闲区

如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区

最佳适应算法缺点：每次都选最小的分区进行分配，会留下越来越多的，很小的，且难以利用的内存块。因此这种方法会产生很多的外部碎片。

最坏适应算法(Worst Fit)：每次分配时优先使用最大的连续空间区，这样分配后剩余的空间区就不会太小，更方便使用

如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区

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

邻近适应算法(Next Fit)：首次适应算法每次都从链头开始查找，导致低地址部分出现很多小空闲分区，每次查找都要经过这些分区，因而增加了查找开销，因此邻近适应算法是每次都从上次查找结束的位置开始搜索

如何实现：空闲分区以地址递增的顺序排列。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区

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

综合来看，四种算法中，首次适应算法的效果反而更好

非连续分配

连续分配方式的缺点

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

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

如果允许将一个进程分散的装入到许多不相邻的分区中，便可充分的利用内存，从而无需再进行"紧凑"，基于这一思想，产生了"非连续分配方式"，或者称为离散分配方式

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

分页存储管理的基本概念

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

如何实现地址的转换

• 页号 = 逻辑地址 / 页面长度（取除法的整数部分）
• 页内偏移量 = 逻辑地址 % 页面长度（取除法的余数部分）

页面在内存中的起始位置：操作系统需要用某种数据结构记录进程各个页面的初始位置。为了方便计算页号，页内偏移量，页面大小一般设为2的整数幂

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

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

页表

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

那么为什么每个页表项的长度是相同的，页号是"隐含"的？

例如：假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节？

• 4GB = $2^{32}$B
• 4KB = $2^{12}$B

因此4GB的内存总共会被分为 $2^{32} / 2^{12} = 2^{20}$ 个内存块，因此内存块号的范围应该是 $0 -2^{20} - 1$，因此至少要20个二进制位才能表示这么多的内存块号，因此至少需要3个字节才够（每个字节8个二进制位，3个字节共24个二进制位）

基本地址变换机构

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

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

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

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

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

具有快表的地址变换机构

局部性原理

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

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

快表(TLB)

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

引入快表后，地址的变换过程：

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

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

参考计算机系统架构中缓存部分

两级页表

单极页表的问题：

1. 页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框
2. 没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面

问题1的解决方法：可将长长的页表进行分组，使每个内存块刚好可以放入一个分组。要为离散分配的页表再建立一张页表，称为页目录表，或称外层页表，或称顶层页表

那么如何实现地址变换呢？

这样第一个问题便解决了，对于第二个问题，可以再需要访问页面时才把页面调入内存（虚拟储存技术）。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存

需要注意的几个细节：

1. 若采用多级页表机制，则各级页表的大小不能超过一个界面
2. 两级页表的访存次数分析（假设没有快表机制）
   1. 第一次访存：访问内存中的页目录表
   2. 第二次访存：访问内存中的二级页表
   3. 第三次访存：访问目标内存单元

基本分段存储管理

分段

进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从0开始编址

内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻

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

段表

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

1. 每个段对于一个段表项，其中记录了该段在内存中的起始位置（又称"基址"）和段的长度
2. 每个段表项的长度是相同的。因此，段号可以是隐含的，不占存储空间

分段存储的地址变换过程与分页存储的地址变换过程有相似之处，也有不同之处：在分页储存管理中，每个页面的长度是相同的，而分段存储管理中，每个段的长度是不同的，因此需要检查段内地址（段内偏移量）是否超过段长

分段vs分页

页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的

段时信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户时可见的，用户编程时需要显式地给出段名

页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序

分页的用户进程地址空间是1维的，程序员只需给出一个记忆符即可表示一个地址。而分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址

另外，分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或称可重入代码（不属于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的

问题：访问一个逻辑地址需要几次访存？

• 分页（单级页表）：第一次访存是查内存中的页表，第二次访存是访问目标内存单元。总计两次访存
• 分段：第一次访存是查内存中的段表，第二次访存是访问目标内存单元。总计两次访存

与分页系统类似，分段系统中也可以因此快表机制，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度

段页式管理方式

段页式管理的逻辑地址结构

一个进程只会对应一个段表，但是每个段会对应一个页表，因此一个进程有可能会对应多个页表

虚拟存储技术

传统存储管理方式的特征，缺点

所谓的传统储存管理即为：

• 连续分配
  • 单一连续分配
  • 固定分区分配
  • 动态分区分配
• 非连续分配
  • 基本分页存储管理
  • 基本分段存储管理
  • 基本段页式存储管理

传统存储管理方式的特征1：一次性，即作业必须一次性全部装入内存后才能开始运行。这会造成2个问题：

1. 作业很大时，不能全部装进内存，导致大作业无法运行
2. 当大量作业要求运行时，由于内存无法容纳所有作业，因此只能有少量作业能运行，导致多道程序并发度下降

传统存储管理方式的特征2：驻留性，即一旦作业被装入内存，就会一直驻留在内存中，直到作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的，暂时用不到的数据，浪费了宝贵的内存资源

解决方式：虚拟存储技术

虚拟内存的定义和特征

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

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

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

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

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

虚拟内存有以下三个主要特征：

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

如何实现虚拟内存技术

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

• 传统的非连续分配储存管理
  • 基本分页储存管理
  • 基本分段储存管理
  • 基本段页式储存管理
• 虚拟内存的实现
  • 请求分页储存管理
  • 请求分段储存管理
  • 请求段页式储存管理

主要区别在于：

1. 操作系统要提供请求调页（或请求调段）功能：在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将信息从外存调入内存，然后继续执行程序
2. 操作系统要提供页面置换（或段置换）功能：若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存

请求分页管理方式

页表机制

缺页中断机构

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

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

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

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

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断。一条指令在执行期间，可能产生多次缺页中断

地址变换机构

请求分页存储管理与基本分页存储管理的主要区别：

• 在程序执行的过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序
• 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存

• 快表中有的页面一定是在内存中的。若某个页面被换出外存，则快表中的相应表项也要被删除，否则可能访问错误的页面

页面置换算法

页面置换算法是决定应该换出哪个页面到外存

• 页面置换算法
  • 最佳置换算法（OPT）
  • 先进先出置换算法（FIFO）
  • 最近最久未使用置换算法（LRU）
  • 时钟置换算法（CLOCK）
  • 改进型的时钟置换算法

页面的换入，换出需要启动磁盘I/O，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率

最佳置换算法(OPT)

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

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

先进先出置换算法(FIFO)

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

实现方法：把调入内存的页面根据调入先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块

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

最近最久未使用置换算法(LRU)：每次淘汰的页面是最近最久未使用的页面

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

最近最久未使用置换算法(LRU)的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大

时钟置换算法(CLOCK)

时钟置换算法(CLOCK)：是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法(NRU)

简单的CLOCK算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。

• 当某页被访问时，其访问位置为1
• 当需要淘汰一个页面时，只需检查页的访问位
  • 如果是0，就选择退出
  • 如果是1，就将它置为0，暂不换出，继续检查下一个页面
• 若第一轮扫描中所有的页面都是1，则将这些页面的访问位依次置为0后再进行第二轮扫描

第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰界面最多会经过两轮扫描

时钟置换算法(CLOCK)实现简单，算法开销小，但未考虑页面是否被修改过

改进型的时钟置换算法

简单的CLOCK算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只要被淘汰的页面被修改过时，才需要写回外存

因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想

• 修改位 = 0：表示页面没有被修改过
• 修改位 = 1：表示页面被修改过

改进型的时钟置换算法开销较小，性能也不错

页面分配策略

驻留集：指请求分页储存管理中给进程分配的物理块集合。在采用了虚拟储存技术的系统中，驻留集大小一般小于进程的总大小

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

固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即驻留集大小不变

可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少，即驻留集大小可变

局部置换：发生缺页时只能选进程自己的物理块进行置换

全居置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程

• 固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。
  • 缺点：很难刚开始就确定应为每个进程分配多少个物理块才算合理
• 可变分配全局置换：刚开始为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列，当某进程发送缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程
  • 只要某进程发生缺页，都将获得新的物理块
  • 缺点：被选中的进程拥有的物理块会减少，缺页率会增加
• 可变分配局部置换：刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块

区别：

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

何时调入页面

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

从何处调入页面

抖动(颠簸)现象

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要调出外存，这种频繁的页面调度行为称为抖动，或颠簸

产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）

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

文件系统

初始文件管理

文件的属性

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

文件内部数据的组织

• 无结构文件（如文本文件）：由一些二进制或字符流组成，又称"流式文件"
• 有结构文件（如数据库表）：由一组相似的记录组成，又称"记录式文件"
  • 记录：是一组相关数据项的集合
  • 数据项：是文件系统中最基本的数据单位

操作系统向上提供的功能

操作系统向上提供的几个最基本的功能：

• 创建文件（create系统调用）
• 删除文件（delete系统调用）
• 读文件（read系统调用）
• 写文件（write系统调用）
• 打开文件（open系统调用）
• 关闭文件（close系统调用）

文件如何存放在外存

文件逻辑结构

• 无结构文件
  • 二进制或字符流
• 有结构文件：有一组相似的记录组成，又称记录式文件，每条记录由若干个数据项组成
  • 定长记录
    • 数据项
  • 可变长记录

目录也是一种特殊的有结构文件

顺序文件

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

• 顺序存储：逻辑上相邻的记录物理上也相邻
• 链式储存：逻辑上相邻的记录物理上不一定相邻

• 顺序文件
  • 串结构：记录之间的顺序与关键字无关
  • 顺序结构：记录之间的顺序按关键字顺序排列

只有物理顺序存储（定长记录）非串结构才可以随机存储，若保持顺序结构，则可实现快速检索，但是要增加或减少记录会比较麻烦

索引文件

建立一张索引表加快文件检索速度，每条记录对应一个索引项，索引表本身是定长记录的顺序文件，索引按顺序排序还可以折半查找，用于对信息处理的及时性要求比较高的场合
每个记录对应一个索引表项的话，索引表本身可能会更大，所以引入索引顺序文件：是索引文件和顺序文件思想的结合，用一组记录对应一个索引表项
为了进一步提高检索效率，可以为顺序文件建立多级索引表

文件目录

• FCB：有序集合，文件目录项
  • 文件名
  • 物理地址
  • 逻辑结构
  • 物理结构
  • 可读/可写
  • 权限
  • 建立事件
  • 修改时间

操作

• 搜索
• 创建文件
• 删除文件
• 显示目录
• 修改目录

• 单机目录结构
  • 整个系统只建立一张目录表，每个文件占一个目录项
  • 不允许重名
• 两级目录结构
  • 主文件目录
  • 用户文件目录
• 多级目录结构

文件一般会在树状结构的叶节点，所以我们可以有一个当前目录，从当前目录出发的相对路径进行查找

树形结构不便于实现文件的共享

• 无环图目录结构
  • 在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图，可以方便的实现文件共享（类似linux硬连接）
  • 需要为每个共享结点设置一个共享计数器，用户删除文件，只删除FCB，并减1共享计数器，当为0时才删除结点

索引结点：搜索文件时只需要关注文件名，所以对文件目录项瘦身
文件越小，占用盘块越小，启动磁盘的次数就越少（每次IO读入一快）

• 磁盘索引结点
• 内存索引结点
  • 内存索引结点会增加一些信息
  • 文件是否修改…

文件的物理结构

文件的数据如何存放在外存中

• 文件块：文件的逻辑地址被分为一个个的文件块
  • 逻辑地址（逻辑块号，块内地址）
• 磁盘块：操作系统按照块分配储存空间

文件连续分配

要求每个文件在磁盘上占有一组连续的块

逻辑块号，块内地址 -> 物理地址，块内地址

• 优点
  • 支持：顺序访问+直接访问
  • 移动磁头的距离也变短，连续分配的文件在顺序读写时速度最快
• 缺点
  • 文件难以扩展
  • 物理上采用连续分配，存储空间利用率低，会产生磁盘碎片

文件链接分配

采取离散分配的方式，可以为文件分配离散的磁盘块

• 隐式链接
  • 目录中记录了文件的起始块号和结束块号
  • 每个磁盘块中保存指向下一个磁盘的指针
  • 只支持顺序访问，不支持随机访问
  • 查找效率低，需要耗费空间储存指针
  • 很方便扩展文件，不会产生磁盘碎片
• 显式链接
  • 把用于连接文件的各物理块的指针显式地放在一张表中，文件分配表（FAT）
  • 一个磁盘仅设置一张FAT，开机时读入并常驻内存
  • 支持顺序访问和随机访问，且不需要访问磁盘进行转换
  • 不会产生磁盘碎片，且方便扩展

文件索引分配

允许文件离散地分散在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块

• 索引块：索引表存放的磁盘块
• 数据块：文件数据存放的磁盘块

索引表是一个文件对应一个

• 优点
  • 支持随机访问，拓展容易实现
• 缺点
  • 索引表会占用空间

若文件索引表太大

• 链接方案
  • 将索引表拆分，并链接索引块
  • 找到最后的索引块效率非常低
• 多层索引
  • 使第一层索引指向第二层索引块，以此类推
  • 但是每次读取都需要进入树状结构，小文件也一样
• 混合索引
  • 多种索引分配方式的结合
  • 包含直接地址索引，又包含一级间接索引
  • 还包含二级间接索引
  • 对于小文件，只需要较少的读取

文件存储空间管理

空闲表法

用表管理空闲盘块数，为一个文件分配连续的存储空间，同样可采取首次适应，最佳适应，最坏适应

• 回收区的前后都没有相邻的空闲区
• 回收区的前后都是空闲区
• 回收区的前面是空闲区
• 回收区的后面是空闲区

回收时要注意表项合并问题

空闲链表法

• 空闲盘块链
  • 以盘块为单位组成一条空闲链
  • 记录：链头+链尾
  • 适用于离散分配的物理结构
• 空闲盘区链
  • 以盘区为单位组成一条空闲链
  • 盘区：连续的空闲盘块
  • 记录这个盘的长度，下一个盘区
  • 可以采取算法进行分配，或者多个分配
  • 回收同样注意合并问题

位示图法

每个二进制位对应一个盘块，用矩阵进行储存

需要注意2维对1维的转换

成组链接法

空闲表法，空闲链表法不适用于大型文件系统，在文件卷的目录区中，专门用一个磁盘块作为超级块，当系统启动时将超级快读入内存，并且保存外存同步

• 超级块
  • 下一组空闲盘块数
  • 空闲块号组
    • 下一组空闲盘块数
    • 空闲块号组
      • 下一组空闲盘块数
      • 空闲块号组

在分配时，如果存有下一组空闲盘数的信息，需要先复制到超级块中
在回收的时候，如果满了，就建新一个分组，然后重新指向（类似链表）

文件的基本操作

• 创建文件
  • 在外存中找到文件所需的空间
  • 创建该文件对应的目录项
• 删除文件
  • 找到对应的目录项
  • 回收文件占用的磁盘块
  • 删除文件的目录项
• 读文件
  • 在打开文件时，已经有编号，提供读的文件编号（文件描述符），读多少，读到哪
• 写文件
  • 在打开文件时，已经有编号，提供写的文件编号（文件描述符），写多少，从哪写
• 打开文件
  • 找到对应的目录项，检测权限
  • 将目录项复制到内存的打开文件表中
  • 使用打开文件表的编号来操作文件
  • 系统打开文件表：整个系统一张（有打开计数器）
  • 用户进程打开文件表->对应系统打开文件表
• 关闭文件
  • 将进程的打开文件表对应项删除
  • 回收分配给文件的内存空间
  • 系统打开计数器减1，若0则删除项

文件共享

共享只有一份文件，更改会同步

• 基于索引结点的共享（硬链接）
  • 在索引表中创建指向索引结点的项，索引结点中设置一个链接计数变量，来记录目录有几个用户链接到该结点上
• 基于符号链的共享方式（软连接）
  • 类似快捷方式，记录文件的位置

文件保护

• 口令保密
  • 开销小
  • 不够安全，口令储存在系统里
• 加密保护
  • 提供密码才能解密
  • 保密性强
  • 需要时间加密解密
• 访问控制列表
  • 精简访问列表：用户组
  • 读
  • 写
  • 执行
  • 添加
  • 删除
  • 列表清单

文件系统层次结构

graph TD
  用户接口-->文件目录系统
  文件目录系统-->用户接口
  文件目录系统-->存取控制模块
  存取控制模块-->文件目录系统
  存取控制模块-->逻辑文件系统与文件信息缓冲区
  逻辑文件系统与文件信息缓冲区-->存取控制模块
  逻辑文件系统与文件信息缓冲区-->物理文件系统
  物理文件系统-->逻辑文件系统与文件信息缓冲区
  物理文件系统-->设备管理模块
  设备管理模块-->物理文件系统
  设备管理模块-->设备
  设备-->设备管理模块
  物理文件系统-->辅助分配模块
  辅助分配模块-->物理文件系统

• 用户接口：向上提供接口
• 文件目录系统：找到FCB或索引结点，管理打开文件目录表
• 存取控制模块：文件保护
• 逻辑文件系统与文件信息缓冲区：文件记录号 -> 逻辑地址
• 物理文件系统：逻辑地址 -> 物理地址
• 辅助分配模块：负责分配回收空间
• 设备管理模块：和设备直接进行交互

磁盘

• 磁盘：一个盘
• 磁道：磁盘盘面的环
• 扇区：环继续划分的块

最内侧是扇区储存密度最大

(柱面号，盘面号，扇区号)确定一个扇区

磁盘调度算法

• 寻找时间
  • 将磁头移动到指定磁道
    • 启动磁头臂s
    • 移动磁头：跨越n个磁道，每个耗时m
• 延迟时间
  • 旋转磁盘，定位到目标扇区
  • 转速r：平均时间1/(2r)
• 传输时间
  • 从磁盘读出或写入数据的时间
  • 转速r，字节数b，磁道上字节数N
    • (1/r)*(b/N) = b/(rN)

• 先来先服务
  • 按照请求访问磁盘的先后顺序进行调度
  • 公平，若请求集中，性能还行
• 最短寻找时机优先
  • 贪心算法寻找当前最近的磁道
  • 性能较好，平均寻道时间短
  • 缺点：可能产生饥饿
• 扫描算法
  • 就是来回扫描，但是必须移动到头才会转向
  • 公平，不会饥饿，
  • 有多余移动，响应不平均
• LOOK算法
  • 如果在这个方向上没有请求了，可以立刻改变方向
• 循环扫描算法
  • 只有磁头朝某个特定的方向移动时才处理磁道访问请求，而快速返回的起始端过程不处理
  • 还是要撞墙才能改变方向
• C-LOOK算法
  • 循环扫描算法进一步改进，没请求就可以返回起始端
  • 同时返回也可以只返回到有请求的磁道上

减少磁盘延迟

如果扇区相邻，读完第一个不能连续读取第二个，因为要进行处理，所以需要再次旋转

• 交替编号：采用交替编号，将逻辑上相邻的扇区，在物理上交替相连，

磁盘地址结构设计

• 把数据放在多个盘同一个磁道上，就可以不移动磁头臂

盘面对应的扇区的编号错位

• 错位命名：可以让不同盘错开不能读取的那段时期

同一个时间只能有一个磁头臂在读写，且读取后一小段时间不能读写

磁盘管理

• 磁盘初始化
  • 进行低级格式化（物理格式化）：将磁盘的各个磁道划分扇区，一个扇区分头，数据区域，尾
  • 头尾用于奇偶校验，CRC循环冗余效验码
• 每个分区由若干柱面组成
• 逻辑格式化，创建文件系统，文件系统根目录，管理文件的数据结构

引导块

• 读取ROM的程序完成初始化
• ROW只存放很小的bootstarp程序
• 完整的bootstarp程序存放在磁盘启动块

参见GPT，grub等

坏块：标注坏块，后续不需要使用

磁盘控制器维护一个坏块链表，可以保留扇区进行备用

IO设备

IO设备：将数据输入到计算机，或者可以接受计算机输出数据的外部设备
UNIX系统将外部设备抽象位一种特殊的文件，用户可以使用与文件操作相同的方式对外部设备进行操作

• 人机交互类外部设备
• 储存设备
• 网络通信设备

信息交换单位

• 块设备
• 字符设备

IO控制器

CPU无法直接控制IO设备的机械部件，因此IO设备还要有一个电子部件作为CPU和IO设备机械部件之间的中介

• 接受和识别CPU发出的命令
  • 控制寄存器来存放命令和参数
• 向CPU报告设备的状态
  • 状态寄存器用于记录IO设备当前的状态
• 数据交换
  • 数据寄存器，用来作为缓存
• 地址识别
  • 给CPU提供寄存器的地址

• IO控制器
  • CPU与控制器的接口，完成通信
  • IO逻辑
    • 负责接受和识别CPU的命令，并向设备发送命令
  • 控制器与设备接口
    • 控制器与设备的接口，完成通信

CPU通过数据总线控制IO控制器，通过控制线+地址线与IO逻辑链接
IO控制器可能控制多个IO设备，所以需要区分

• 内存映像IO
  • 在内存地址之后编址，与内存同一
• 寄存器独立编址
  • 从0开始编址，需要指明控制器+寄存器编号

IO控制方式

• 程序直接控制方式
  • 读写
    • CPU向控制器发出读，设置状态为忙碌
    • CPU轮询检查寄存器读状态
    • 设备传输数据
    • 控制器把数据放进寄存器，并把状态改为就绪
    • CPU读取到寄存器，然后转到内存
  • CPU干预很频繁
  • 每次读写一个字
  • IO<->CPU<->内存
  • 优点：实现简单
  • 缺点：CPU利用率低，效率低
• 中断驱动方式（系统中断）
  • CPU会在每个周期的末尾检查中断是否达到
  • 中断处理需要保存环境，每次发送中断，只能读一个字
  • CPU和IO设备可以并行运行，利用率提升
  • IO<->CPU<->内存
• DMA方式
  • 直接存储器存取
  • 传输单位由字变为块
  • 直接传输数据到内存，不经过CPU
  • 仅在传输开始和接受才需要CPU干预
  • DMA控制器
    • DR：数据寄存器，缓存数据
    • MAR：存放内存地址，数据放哪
    • DC：剩余要读写的数据多少
    • CR：记录CPU发来的IO命令，状态信息
  • 总线直接连接内存和DMA控制器
  • 读数据还是一个字一个字读取
  • 块必须连接，在内存也必须连续
  • IO<->内存
• 通道控制方式
  • 一种硬件，可以识别并执行一系列的通道指令
  • CPU向通道发出IO指令，表明通道程序的内存位置，哪个IO设备
  • 通道执行内存中的通道程序
  • 完成任务后，向CPU发出信号
  • 每次读写一组数据块
  • IO<->内存
  • 需要硬件支持，效率特别高

IO软件层次

graph TD
  用户层软件-->设备独立性软件
  设备独立性软件-->用户层软件
  设备独立性软件-->设备驱动程序
  设备驱动程序-->设备独立性软件
  设备驱动程序-->中断处理程序
  中断处理程序-->设备驱动程序
  中断处理程序-->硬件
  硬件-->中断处理程序

• 用户层软件：提供与用户交互的接口（库函数）
  • 翻译为IO请求，通过系统调用请求操作系统内核服务
• 设备独立性软件：以设备硬件无关的功能在这里实现
  • 向上提供接口
  • 提供对设备的保护
  • 差错处理
  • 设备的分配与回收
  • 数据缓冲区管理
  • 建立逻辑设备到物理设备名的映射关系，选择相应的驱动程序
    • 逻辑设备表（LUT）
      • 逻辑设备名
      • 物理设备名
      • 驱动程序入口地址
• 设备驱动程序
  • 主要负责对硬件的具体控制，翻译命令
• 中断处理程序
  • 读出设备的状态，判断是否正常结束
    • 从设备中读入一个字的数据放到内存缓冲区
    • 或处理异常

IO核心子系统

• 用户层
  • 假脱机技术（SPOOLing技术）

• IO核心子系统（IO系统）
  • 设备独立性软件
  • 设备驱动程序
  • 中断处理程序
• IO调度
  • 用某种确定的算法确定一个好的顺序来处理各个IO请求
  • 如：磁盘调度
• 设备保护
  • 把设备看作文件进行权限管理

假脱机技术

脱机：脱离主机的控制进行输入/输出
引入脱机技术，缓解了CPU与慢速IO设备的速度矛盾，现在用软件模拟脱机数据

graph LR
  输入设备--输入进程-->输入缓冲区-->输入井
  输出井--输出进程-->输出缓冲区-->输出设备

设备的分配与回收

• 设备固有属性
  • 独占设备
  • 共享设备
  • 虚拟设备

• 安全分配方式：为进程分配一个设备后就将进程阻塞，本次IO完成后才将进程唤醒
  • 优点：不会死锁
  • 缺点：不能并行工作
• 不安全分配方式：发出IO请求后，还可以继续执行，直到IO请求得不到满足才阻塞
  • 优点：可以并行处理，一个进程可以使用多个设备
  • 缺点：可能发生死锁

• 静态分配：进程运行前为其分配所有资源，结束后归还资源，不会发生死锁
• 动态分配：动态的分配资源

设备控制表（DCT）

• 设备类型
• 设备标识符
• 设备状态
• 指向控制器表的指针：找到控制器信息
• 重复执行次数或时间：记录失败次数
• 设备队列的队首指针：指向正在等待设备的进程队列

控制器控制表：每个控制器对应一张COCT

• 控制器标识符
• 控制器状态
• 指向通道表的指针
• 控制器队列的队首指针
• 控制器队列的队尾指针

通道控制表：每个通道对应一张CHCT

• 通道标识符
• 通道状态
• 与通道连接的控制器表首址
• 通道队列的队首指针
• 通道队列的队尾指针

系统设备表（SDT）：记录了系统中全部设备的情况

• 表面1
• 表目1
  • 设备类型
  • 设备标识符
  • 设备控制表
  • 驱动程序入口

1. 根据设备请求查找系统设备表
2. 根据系统设备表找到设备控制表
   1. 设备忙则等待队列
   2. 不忙则分配给进程
3. 根据设备控制表找到控制器控制表
   1. 控制器忙则等待队列
   2. 不忙则分配给进程
4. 根据控制器控制表找到通道控制表
   1. 控制器忙则等待队列
   2. 不忙则分配给进程

只有设备，控制器，通道3者都分配成功时，本次设备分配才算成功，才能数据传输

用户编程需要提供物理设备名->建立逻辑设备名与物理设备名的转换

缓冲区管理

缓冲区就是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区，使用硬件作为缓冲区的成本很高，容量也不大，一般情况下，是利用内存作为缓冲区，设备独立性软件的缓冲区管理就是要组织管理好这些缓冲区

• 缓和CPU与IO设备之间的速度不匹配的矛盾
• 减少对CPU的中断频率，放宽对CPU中断响应时间的限制
• 解决数据粒度不匹配
• 提高CPU与IO设备之间的并行性

单缓冲

操作系统会在主存中为其分配一块缓冲区，缓冲区每次都要用干净才能读或者写
所以会耗时Max(C, T) + M

双缓冲

操作系统会在主存中为其分配两块缓冲区，缓冲区每次都要用干净才能读或者写
难以找到一个周期，平均耗时Max(T, C+M)

缓冲池

由系统中公用的缓冲区组成，这些缓冲区按使用状态可以分为

• 空缓冲队列
• 装满输入数据的缓冲队列
• 装满输出数据的缓冲队列

根据功能不同

• 用于收容输入数据的工作缓冲区
• 用于提取输入数据的工作缓冲区
• 用于收容输出数据的工作缓冲区
• 用于提取输出数据的工作缓冲区

企业面试题

Linux 开机启动过程

1. 主机加电自检，加载 BIOS 硬件信息。
2. 读取 MBR 的引导文件(GRUB、LILO)。
3. 引导 Linux 内核。
4. 运行第一个进程 init (进程号永远为 1 )。
5. 进入相应的运行级别。
6. 运行终端，输入用户名和密码。

Linux 的目录结构

Linux 文件系统的结构层次鲜明，就像一棵倒立的树，最顶层是其根目录：

常见目录说明：

• /bin：存放二进制可执行文件(ls,cat,mkdir等)，常用命令一般都在这里；
• /etc：存放系统管理和配置文件；
• /home：存放所有用户文件的根目录，是用户主目录的基点，比如用户user的主目录就是/home/user，可以用~user表示；
• /usr：用于存放系统应用程序；
• /opt：额外安装的可选应用程序包所放置的位置。一般情况下，我们可以把tomcat等都安装到这里；
• /proc：虚拟文件系统目录，是系统内存的映射。可直接访问这个目录来获取系统信息；
• /root：超级用户（系统管理员）的主目录（特权阶级o）；
• /sbin：存放二进制可执行文件，只有root才能访问。这里存放的是系统管理员使用的系统级别的管理命令和程序。如ifconfig等；
• /dev：用于存放设备文件；
• /mnt：系统管理员安装临时文件系统的安装点，系统提供这个目录是让用户临时挂载其他的文件系统；
• /boot：存放用于系统引导时使用的各种文件；
• /lib：存放着和系统运行相关的库文件 ；
• /tmp：用于存放各种临时文件，是公用的临时文件存储点；
• /var：用于存放运行时需要改变数据的文件，也是某些大文件的溢出区，比方说各种服务的日志文件（系统启动日志等。）等；
• /lost+found：这个目录平时是空的，系统非正常关机而留下“无家可归”的文件（windows下叫什么.chk）就在这里。

RAID 是什么

RAID 全称为独立磁盘冗余阵列(Redundant Array of Independent Disks)，基本思想就是把多个相对便宜的硬盘组合起来，成为一个硬盘阵列组，使性能达到甚至超过一个价格昂贵、 容量巨大的硬盘。RAID 通常被用在服务器电脑上，使用完全相同的硬盘组成一个逻辑扇区，因此操作系统只会把它当做一个硬盘。

RAID 分为不同的等级，各个不同的等级均在数据可靠性及读写性能上做了不同的权衡。在实际应用中，可以依据自己的实际需求选择不同的 RAID 方案。

参考文献

• 2019 王道考研 操作系统