[嵌入式] 操作系统简述复习笔记

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 嵌入式 -> 操作系统简述复习笔记 -> 正文阅读

[嵌入式]操作系统简述复习笔记

1.操作系统基本概述

略

2.处理器

2.1.处理器和寄存器

处理器中有大量的寄存器，不同的寄存器有不同的作用，例如储存执行结果，储存数据地址等等。因此，寄存器多而复杂。

2.1.1.CPU内部的寄存器

在CPU内部有一个控制单元，里面有指令暂存器IR和指令译码器ID，分别用于存储下一条要执行的指令和对指令进行翻译。在对指令进行翻译后，就会遇到算数逻辑单元，通过计算处理后，便会将处理后的结果存入标志寄存器Flag，并且会用程序计数器PC来统计执行的程序数。

上述的全部寄存器及其他硬件都连接在内部总线上，通过内部总线和内存相连。

2.1.2.内存中的寄存器

内存中有内存地址寄存器MAR和内存数据寄存器MDR。

2.1.3.系统总线与其他地方的寄存器

在高级的操作系统中，IO寄存器等其他寄存器可以直接和内部总线相连，这样就可以提高数据的交互速率，但在简单的操作系统中，这些寄存器都是集成在系统总线上的。

2.1.4.用户程序可见寄存器 and 控制与状态寄存器

用户程序可见寄存器：

这就可以让程序员直接与寄存器进行交互，减少访问主存储器的次数，以此来提高效率

控制与状态寄存器：

被操作系统程序所使用，用于控制程序执行

2.1.5.程序状态字PSW

PSW是一种概念，用于记录当前程序运行的动态信息

在部分计算机系统中，PSW是一个寄存器，为控制与状态寄存器

2.2.指令与处理器模式

2.2.1.机器指令

机器指令是计算机系统执行的基本命令，是中央处理器执行的基本单位。由一个或多个字节组成。

2.2.2.指令执行过程

指令的执行步骤如下：取指解码执行

取指是指PC从存储器中将指令放入IR中

解码是指解译IR中的指令来决定其执行行为

执行是指连接到CPU，执行运算，产生结果并写回

2.2.3.指令执行周期与指令流水线

执行周期就是取指解码执行这三个过程

而指令流水线是指当指令1进行解码时，指令2可以同时进行取指，以此类推执行与解码

2.2.4.特权命令和非特权命令

特权指令只可被操作系统内核所使用

非特权指令能够被所有程序使用

2.2.5.处理器模式

完整的处理器模式为

0：代表操作系统内核

1：代表系统调用

2：代表共享库程序

3：代表用户程序

通常只分为0与3两种模式，即对应内核模式和用户模式

2.2.6.处理器模式的切换

用户模式->内核模式：可通过中断、异常或系统异常等触发

内核模式->用户模式：调用中断返回指令

2.3.中断、异常与系统异常

2.3.1.狭义的中断

仅指源于处理器之外的中断事件，即与当前运行的指令无关。例如I/O中断，时钟中断等

2.3.2.异常

指当前运行指令引起的中断事件，例如地址异常，处理器硬件故障

2.3.3.系统异常

指执行陷入指令而触发系统调用，如请求设备、请求I/O等，与异常不同的是，异常是当前运行指令出现问题，而系统异常是指当前指令请求某种资源等

2.3.4.中断源

2.3.4.1.处理器硬件故障中断事件

即处理器，内存，总线等硬件出现故障

处理原则：保护现场，停止设备与CPU，等待人工干预

2.3.4.2.程序性中断事件

除数为零等：简单处理，报告用户

非法指令，用户态使用特权指令：终止进程

终止进程指令：终止进程

虚拟地址异常：调整内存后重新执行指令

虚拟地址异常：调整内存后重新执行

2.3.4.3.自愿性中断事件

执行陷入命令

例如请求分配外设，请求I/O

处理流程：陷入内核，保护现场，跳转具体程序

2.3.4.4.I/O中断事件

完成操作：等待释放进程

出错或异常：等待人工干预

2.3.4.5.外部中断事件

中断什么，就记录现场，然后执行中断

2.4.中断系统

2.4.1.中断系统的构成

包括硬件子系统和软件子系统两部分

中断响应由硬件子系统完成

中断处理由软件子系统完成

2.4.2.中断响应处理与指令执行周期

在取指解码执行后面有一步检测中断，若为不屏蔽中断，就需要进入中断阶段，若是屏蔽中断，那就跳过执行下一个步骤

2.4.3.中断装置

即计算机系统中响应中断/异常的硬件装置

中断装置根据不同情况而有所区别

处理器外的中断：由中断控制器发现和响应

处理器内的异常：由指令的控制逻辑和实现线路发现，也称作陷阱

处理器内的系统异常：直接触发，成为系统陷阱

中断控制器：

包含中断控制逻辑线路和中断寄存器。当外部设备请求中断时，中断寄存器中会设置已发生的中断，中断检查时就是检查寄存器中的中断是否被屏蔽，未被屏蔽就会引发中断处理程序

2.4.4.中断的处理

中断处理程序的作用：处理中断事件和恢复正常操作

过程：

1.保护未被硬件保护的处理器状态

2.识别PSW中的断码字段，识别中断源

3.分别处理发生的中断事件

4.恢复正常操作

2.5.多中断的响应和处理

2.5.1.中断屏蔽

当计算机检测到中断时，其会根据中断是否屏蔽来决定是否响应这些中断

2.5.2.中断优先级

当计算机检测到多个中断时，中断装置会有响应中断的一个顺序，其会给不同类型的中断标上不同的优先级，按照优先级来执行中断。不同的操作系统中优先级的设置也是不同的。

2.5.3.中断的嵌套处理

当计算机响应中断后，在中断处理过程中，可以再响应其他中断

为了保证计算机性能，一般嵌套层数不会太多，如三层

中断的嵌套可以改变中断处理顺序，即不一定先中断先处理，可能后处理

2.5.4.响应与处理

通过中断屏蔽，中断优先级和中断嵌套处理，可以改变中断处理的次序

2.6.进程及其状态

2.6.1.进程的概念

为了更系统的管理运行的程序，计算机会为正在运行的程序建立一个管理实体。这个实体就称为进程。

进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，简单地说，就是某个程序的依次运行。

需特别注意的是，进程是操作系统进行资源分配和调度的独立单位。

进程包括以下五个实体：

数据结构P 内存代码C 内存数据D 通用寄存器信息R 程序状态字信息PSW

2.6.2.进程举例

需牢记的是，进程是一个程序在一组数据上的一次执行。

因此，就算是一个程序在不同时间，同一组数据上运行，也算两个进程，其PCDR PSW都是不同的

普通进程可分成两大类：

1.在不同数据上运行的不同进程

2.在同一数据下运行的共享数据的不同进程

2.6.3.进程状态

一般的，分为运行态，就绪态和等待态（阻塞态）。

运行态：进程获得了CPU资源与其他所需要的资源

就绪态：进程获得了其他所需要的资源但没有获得CPU资源

等待态：进程未获得其他所有所需要的资源（与CPU资源无关）

2.6.5.进程之间的互相转换

1.运行态->就绪态：被更高优先级的进程抢占了CPU资源，时间片用完

2.就绪态->运行态：在其他资源齐全的情况下，获得CPU资源

3.运行态->等待态：当运行进程申请I/O等其他资源时，会被阻塞然后进入等待态

4.等待态->就绪态：获取了其他所有资源，等待获取CPU资源

2.6.6.进程挂起

提出进程挂起的概念是为了解决计算机系统在运行过程中可能出现的资源不足的情况。

其表现为性能低和死锁两种情况。

进程挂起的作用：剥夺某些进程的内存与其他资源，调入OS管理的对换区，待适当时候再参与进程执行。

挂起态和等待态的区别就是：后者是已占有部分资源，而前者不占有任何资源

2.6.7.进程挂起有关的状态

一般的，都选择等待态进程进入挂起等待态。

实在不得已再选择就绪态进程进入挂起就绪态。

同样的，也会先恢复挂起就绪态，再恢复挂起等待态

2.7.进程的数据描述

2.7.1.进程控制块 PCB

PCB用于记录进程状态机环境信息，便于OS对进程进行管理

PCB中的信息分为标识信息、现场信息、控制信息三块

2.7.1.1.标识信息

用于存放唯一标识该进程的信息

有系统分配的标识号和进程组标识号

有用户定义的进程名和进程组名

2.7.1.2.现场信息

包括用户可见寄存器信息如数据寄存器和地址寄存器、控制与状态寄存器信息如PSW、栈指针内容如核心栈与用户栈指针信息

2.7.1.3.控制信息

包括存放与管理、调度进程相关信息如处理器实用信息，资源清单等

2.7.2.进程映像

是进程在某一时刻的内容与执行状态的集合

其中包括：进程控制块、进程程序块、进程数据块与核心栈

注意，其是内存级的物理实体，也被称为进程的内存映像

2.7.3.进程上下文

先声明一点，进程的执行是需要环境支持的，包括CPU现场和Cache中的执行信息

因此，我们提出了进程上下文的概念：进程物理实体+运行环境=进程上下文

其包括用户级上下文（用户程序块、数据区、栈、共享内存）、寄存器上下文（PSW、栈指针、通用寄存器）、系统级上下文（PCB、内存区表、核心栈）

由此我们可以看到，几乎关于进程的全部信息都可在上下文中找到，因此其刻画了进程执行的具体情况

2.8.进程的管理

2.8.1.关键的进程管理软件

系统调用/中断/异常处理程序

队列管理模块

进程控制、调度、通信程序

2.8.2.进程实现的队列模型

总体的队列分为就绪队列和等待队列

CPU从就绪队列中取到就绪态的进程进行运行，若进程需要其他资源，则进入等待队列，待获得资源后再返回就绪队列。而如果是因为时间片轮转等导致的运行态剥夺，则直接回到就绪队列末尾

2.8.3.队列管理模块

这是操作系统实现进程管理的核心模块

用于管理2.8.2中的内容

2.8.4.进程的控制与管理

1.进程创建：进程表加一项进程，并申请PCB且初始化，建立标识，建立映像，分配资源，移入就绪队列

2.进程撤销：从队列中移除，归还资源，撤销标识，回收PCB，移除进程表项

3.进程阻塞：保存现场，修改PCB中的相关信息，并移入等待队列

4.资源唤醒：从等待队列中移出，修改PCB中的相关信息，移入就绪队列

5.进程挂起：修改状态并出入相关队列，回收资源

2.8.5.原语与进程控制原语

由于进程控制过程是会涉及OS的核心数据结构的，为了防止与时间有关的错误，应当使用原语

同时，原语会被多个进程所使用的，应当是不可修改的精简代码

2.9.进程切换与模式切换

2.9.1.进程切换

上文中我们提到，进程的上下文，既有进程的物理信息，也有进程的环境信息，那么在切换进程时，实际上就是其上下文的切换

分为三步：保存被中断进程上下文–转向进程调度–恢复待运行进程的上下文

2.9.2.模式切换

进程切换的前提是系统处于管态（内核模式），所以，在进程切换前应当有模式切换

从用户模式到管理模式是通过中断引发的

从管理模式到用户模式是通过中断返回命令引发的

2.9.2.1.基本工作任务

终端装置完成正向模式切换：

处理器模式转化为内核模式

保存当前进程的PSW/PC值到核心栈

转向处理程序

中断返回指令完成逆向模式转换：

从核心栈中弹出PSW/PC值

处理器转为用户模式

2.9.3.进程切换的工作过程

首先一定是保存一些模式切换硬件信息：PSW/PC等

然后是保存一些硬件未保存的现场信息，这部分由软件完成

然后便是对进程进行操作，首要任务就是改变PCB

先将被中断进程的堆栈指针SP保存至PCB

先调整被中断进程的PCB，再调整被选中进程的PCB

先是加入中断/恢复信息，再是将相关进程移入/移出相关队列

而恢复进程步骤与上相反，先恢复PCB的信息，再恢复堆栈指针SP，再还原现场信息，最后弹出PSW/PC

2.9.4.发生进程切换的时机

进程切换一定发生在中断/异常/系统调用的处理过程中

但是不一定全部的中断都会引发进程切换，比如进程自身的虚拟地址出错等，那么进程会先中断，处理完后继续执行。当然在这过程中也需要保存现场信息和还原现场信息。只要有中断，就一定要保存和恢复中断前后的现场信息

2.10.多线程技术描述

2.10.1.线程的概念

之前我们详细了解了进程的概念。由概念可知，进程是分配资源的独立单位，那么如果每个程序都是一个进程，在进行程序之间的并发等操作时，切换程序将带来很多资源浪费。因此我们提出一个新的概念，线程。

线程是进程的一条执行路径，是调度的基本单位。也就是说，一个进程可以包含多个线程。那么在执行任务时，可以进行线程的并发执行，这会比进程的并发执行更快捷，效率更高。

2.10.2.多线程环境下的进程和线程

多线程环境下的进程只负责容纳进程映像的虚拟地址空间，并对进程、文件和设备的存取实行保护机制。

而线程就只是执行程序。

2.10.3.线程的状态与调度

线程有运行、就续和睡眠三个状态，无挂起状态

与线程状态有关的操作有：孵化，封锁，活化，剥夺，指派，结束

同时，这也与OS是否可以感知线程有关

若OS可感知线程：那么CPU的调度对象就是线程，进程就没有就续、运行、阻塞三个状态了

若OS不可感知线程：那么处理器的调度对象仍是进程，线程是由用户调度程序负责调度

2.11.KLT和ULT

KLT是内核级多线程，ULT是用户级多线程

2.11.1.KLT

内核级多线程的所有线程操作都由操作系统内核来完成

当一个线程发生阻塞时，其可以调度其他CPU来完成进程切换或执行其他线程

2.11.2.ULT

用户级多线程的线程操作放在用户态下完成

但由于用户态无法操作CPU，因此当线程阻塞时，会导致进程阻塞

2.11.3.Jacketing算法

专用于用户级线程发生阻塞时

可以引发用户调度来选择下一个需要执行的用户级线程

2.11.4.两者比较

相同：进程是资源保护的单位，进程有多个线程，线程接口类似，共享资源通信块

不同：ULT适用于解决逻辑并行问题，KLT适用于解决物理并行问题

2.12.多线程的混合式策略

2.12.1.混合式策略的概念

将ULT映射到KLT上，通过调整KLT的数量，来达到较好的并行效果

线程的创建、调度、同步都在用户态下完成

这个策略可以结合两者优点并减少两者缺点

2.12.2.线程状态分析

ULT的三态：可运行态、活跃态、睡眠态

KLT的三态：就绪态、运行态、阻塞态

下面介绍两者三态的关系：

因为ULT是映射到KLT上的，因此，无论KLT处于哪个状态，ULT都处于活跃态，即ULT的活跃态包含KLT的三态

而Jacketing算法可以执行用户调度，来改变用户态线程的状态

2.13.处理器调度的层次

2.13.1.层次概念

大致分为高级调度，中级调度，低级调度

2.13.2.高级调度

与创建相关

高级调度是统筹进程的调度

主要工作如下：

1.是否接受一个终端用户的连接

2.是否被系统接纳并构成进程

3.新建进程是否加入就续进程队列

2.13.3.中级调度

与挂起相关

可以提高内存利用率和作业吞吐量

因此，其可以决定哪些进程留在内存中，可以来竞争资源

2.13.4.低级调度

是最重要的调度

与状态切换相关

按照某种原则进行CPU的分配，即与三态有关

同时会记录各个进程或内核级线程的状态

实现方法：进程调度程序，也被称为所有进程的父进程，因为其决定了进程的生死等

2.14.CPU的调度算法

这里我们介绍操作系统的几种不同的调度算法

2.14.1.调度算法选择的原则

资源利用率：CPU或其他资源的使用效率

响应时间：任务开始执行时间-任务提交时间

周转时间：任务结束时间-任务提交时间

吞吐量：单位时间内吞吐的数据量

公平性：确保每个用户获得合理的CPU或其他资源份额

2.14.2.优先数调度算法

分为抢占式与非抢占式两种

可以根据任务的紧迫性、等待时间长短等来调整优先数

2.14.3.与进入系统时间相关的算法

短进程优先算法SPN

剩余计算时间短进程优先算法

高响应比优先算法（响应比 = 等待时间+要求服务时间/要求服务时间） HRRN

先来先服务算法 FCFS

2.14.4.时间片轮转调度算法

即进程进入就绪队列后，会轮流占有一定时间的CPU，在时间用完后，便排到就绪队列队尾准备下一次执行

2.14.5.分级调度算法

分级调度算法就是给进程排多个就绪队列，每个就绪队列优先级不同

同时，为了保证尽量公平，优先级越高的队列执行时间越短

2.14.6.彩票调度算法

即为每张彩票赋予同样的时间片，不同进程的初始彩票拥有数不同，优先级越高的越多

每次由系统抽取一张彩票，抽到的进程将彩票上交，并执行一个时间片的进程

这样，随着时间的发展，初始彩票少的进程的执行概率会逐渐增加，这也增加了平衡性

3.存储管理

3.1.存储管理的主要模式

3.1.1.逻辑地址

逻辑地址又称为相对地址，是用户在编程时所用到的地址空间

逻辑地址从0开始编号，分为以下两种形式：

1.一维逻辑地址：这是直接给地址

2.二维逻辑地址：这是给内存分段，通过段号去对应相应的内存

3.1.2.段式程序设计

在设计程序时，我们将一个程序设计成多个段，例如代码段、数据段、堆栈段等

同时，用户可以通过段覆盖技术来扩充内存使用量，这个技术是程序设计技术，不是OD存储管理的功能

3.1.3.物理地址

物理地址又称为绝对地址，即程序在执行时占用的地址空间

CPU在执行命令时必须要按照物理地址来执行

这里来区分一下绝对地址和逻辑地址：

逻辑地址是用户程序经过编译后将存储空间从0开始编号，而绝对地址是内存中各物理存储单元统一的基地址顺序编址

3.1.4.主存储器的复用

内存复用是指在服务器物理内存一定的情况下，通过综合运用内存复用单项技术（内存气泡、内存交换、内存共享）对内存进行分时复用。通过内存复用，使得虚拟机内存规格总和大于服务器规格内存总和，提高服务器中虚拟机密度。智能内存复用可提升内存资源的利用率，帮助用户节省内存采购成本，延长物理服务器升级内存的周期。

有分区复用和页架复用两种：

分区复用：

分区大小可固定也可改变，一个程序/程序段占用一个分区

页架复用：

页架大小是固定的，一个程序/程序段占用多个页架

3.1.5.存储管理的基本模式

通过两种复用方式和两种多里地址方式，可构成四种存储管理的模式

单连续存储管理：通过一维逻辑地址空间和分区复用组合，即一个程序是采用一维逻辑地址空间来存储程序，并且采取分区复用的方式复用内存**（不可虚拟|共享）**

段式存储管理：通过二维逻辑地址空间和分区复用组合，即一个程序是采用段式二维逻辑地址来存储程序，并且采用分区复用来复用内存（可虚拟|共享）

页式存储管理：通过一维逻辑地址空间和页架复用组合，即通过一维逻辑地址空间来存储程序，并通过页架的形式进行内存复用（可虚拟|共享）

段页式存储管理：通过二维逻辑地址空间和页架复用那个组合，即通过段式二维逻辑地址空间来存储程序，并且通过页架的形式来实现内存复用（可虚拟|共享）

3.2.存储管理的功能

3.2.1.地址转换

地址转换又称为地址重定位，即把逻辑地址转换为绝对地址

重定位的两种方式：

静态重定位：程序装入内存时进行地址转换，这是由装入程序执行的

动态重定位：在CPU执行程序时进行地址转换，这必须是由硬件完成的，效率较高

3.2.2.内存的分配和去配

分配：进程装入主存时，存储管理软件来进行主存分配，并设置一个表格记录空间的分配情况

去配：某个进程撤离或归还内存资源时，存储管理软件将这些资源收回并调整记录表格

3.2.3.内存的空间共享

共享有以下两种意义：

1.多个进程共享同一内存的资源：即一块内存上，多个进程分别占用不同的存储空间，即不重复或共享

2.多个进程共享主存储器的某些区域：若干个协作进程拥有公共的内存程序块或数据块

3.2.4.存储保护

由上可知，内存是有可能被干扰的，因此必须对其进行保护

对于本进程：

私有内存区：可读可写

公共内存区：根据自身权限

非本进程内存区：不可读写

存储保护极其重要，因此是由硬软件协同完成的，CPU也参与到生成地址保护中去

3.2.5.内存空间的扩充

存储扩充的意义就是把磁盘作为内存的扩充，这样就只需要在内存中装入要执行的部分进程，不需要将整个程序全部装入内存

对换技术：将不在执行的进程调出内存

虚拟技术：值调入进程的部分内容

同样的，这个功能也需要硬软件协作完成：

1.当进程决定对换时，硬件会实行调换

2.当CPU处理到不在主存的地址时，即访问到了未装入内存的程序，CPU会发出虚拟地址异常指令，将该部分进程调入内存中执行

3.3.虚拟存储器的概念

3.3.1.为什么会有虚拟存储器

因为主存的容量大小严重影响到了用户编写程序的大小和多道程序设计的道数

同时，程序执行时具有互斥性，时间局部性，顺序性和循环性，因此可以考虑部分调入进程内容

注意，虚拟存储器不是其物理不存在的意思，而是指对于内存来说，其实虚拟存在的，即与内存无关，其大小等均只与外存大小有关

3.3.2.基本思想

在程序开始时，先调一部分内存到主存中，再根据程序的需要随调随用

同时，若主存没有足够的空间，就会把暂时不用的信息调出到辅存中去

3.3.3.实现思路

虚拟地址空间：容纳进程装入

实际地址空间：承载进程执行

因此，对于用户来说，计算机系统具有一个容量极大的主存空间，即虚拟存储器

虚拟存储器作为一种地址空间扩展技术，通常对用户是透明的，除非用户需要进行高性能的程序设计

3.4.存储管理的硬件支撑

3.4.1.缓存Cache的概念

缓存是比内存更快的存储器，其直接位于CPU内部，且分为L1，L2，L3三级，性能依次降低

三级结构：

L1：是最快的Chace，因此最小，速度最快，其与CPU频率一致

L2：其次快的Chace，因此稍大，较好的L2缓存频率与CPU一致，也有可能稍低于CPU频率

L3：是最慢的Chace，但也最大，因此，改善总线比设置L3可能更有利于提高系统性能

3.4.2.缓存的构成

通常由高速存储器，联想存储器，地址转换部件，替换逻辑等组成

? 联想存储器：根据内容进行寻址的存储器

地址转换部件：通过联想存储器建立的目录表来进行快速的地址转换。若命中就直接访问Chace，未命中就去内存中找相应的地址

替换逻辑：根据相应逻辑，在缓存已满的情况下进行数据块的替换，并修改地址转换部件

3.4.3.存储管理涉及的存储对象

存储管理是OS来管理内存的软件部分

有两点比较重要：

1.为了获取更好的处理性能，内存中的关键数据与程序往往被存入其中，这样就需要存储管理来对Cache进行调整，甚至包括对联想存储器的管理

2.为了获得更大的虚拟地址空间，存储管理也会对各种外放硬盘，SSD等进行管理

3.5.单连续分区存储管理

概念：每个进程占用一个物理上完全连续的存储空间

有三种：

单用户连续存储管理

固定分区存储管理

可变分区存储管理

3.5.1.单用户连续分区存储管理

如何区分系统区和用户区：通过一个栅栏寄存器分两个区域，并且通过栅栏寄存器来进行存储保护。栅栏寄存器相当于一堵墙，一旦越界，就会警报

一般采用静态重定位进行地址转换，即在将进程传入内存时，就将虚拟地址改为绝对地址

3.5.2.固定分区存储管理

支持多个分区

分区数量、大小固定

可使用静态重定位

硬件实现代价低

但由于每个分区大小固定，一定会造成部分内存的浪费，即内存的内零头

内部有一张内存分配表：包括了起始地址，长度，标志

内存分配与去配：有一个占用标志，当被占用时，就将相关进程的标志放入其中，未被占用时，就清除标志

3.5.3.可变分区存储管理

浪费内存空间较小，仍会有小的不可用的内存分区，称为内存外零头，外零头是不可避免的

且分区的大小、个数都是可变的

分配内存：会将内存中所有的空闲区域加起来，检查是否够进程使用，若不够，就让进程等待，若够，则会将小片的空闲区域拼成大块的内存区域，来存放新进程

3.5.3.1.主存分配表

主存分配表分为已分配区表和未分配区表

每张表都包含起址、长度、标志三部分

3.5.3.2.内存分配

有最先适应分配算法，邻近适应分配算法，最优适应分配算法和最坏适应分配算法

最先适应分配算法：从未分配区表的首地址开始查询符合的内存块

邻近适应分配算法：就是寻找最近的，符合的内存块，不从首部开始查

最优适应分配算法：把满足要求的最小空闲分区分配给作业（最易产生外零头）

最坏适应分配算法：将最大的满足要求的空闲分区分配给作业

3.5.4.内存分配过程中的地址转换与存储保护

3.5.4.1.单连续分区存储

下限寄存器中包含了分配内存的首地址和结束地址

当CPU在动态重定位时，若分配的内存绝对地址低于下限，就会报错中断

3.5.4.2.可变分区存储

其中包含了限长寄存器和基址寄存器

首先，限长寄存器会判断逻辑地址是否限长，若限长且超过长度限制，便中断

再利用基址寄存器，来判断进程的内存占用长度是否在小于分区最大长度，若超过，则中断

3.6. 页式存储管理的基本原理

3.6.1.基本原理

分页存储器将主存划分为多个大小相等的页架

受到页架大小的限制，程序的逻辑也必须分为多个页（在同一个页架或不同的页架上）

相应程序或数据的逻辑地址存在页表中，页表就是一个页号及其对应的物理块号（页架号），这样就可以用于转换页架号

对页架和页的申疑：页架从基本上来说，就是内存中的一个物理块，其大小是确定的。而页则是每个作业的地址空间占用的基本单位，每个作业占用一系列页。在这里我们可以对3.6.2进行一定理解，即真正的物理地址是页架，而页号则是每个作业的逻辑地址，在访问页架前要对其页的内容进行转换

3.6.2.页式存储管理中的地址

逻辑地址由页号和单元号两部分组成

物理地址由页架号和单元号两部分组成

逻辑地址和物理地址的变换：就是将逻辑地址的页号替换为页架号即可

3.6.3.页式存储管理的内存分配和去配

通过一个位来记录主存的分配情况，所有的存储情况都保存在一张位示图中

3.6.4.页的共享

共享分为数据共享和程序共享

数据共享：不同进程可以使用不同页号共享数据页因为不同的数据可以存在不同的页中

程序共享：不同进程必须使用相同页号共享代码页 因为代码应当是相同的段

3.7.页式存储管理的地址转换

3.7.1.通过页表来进行地址转换

页表存放在内存中，每次进行地址转换时有如下步骤：

1.按照页号读出页表中的页架号

2.计算出相应的物理地址来进行读写

由于两次读取内存，就导致速度很慢。相应的解决方法就是将页表放入缓存Cache中

3.7.2.利用快表来进行地址转换

快表是储存在高速存储器中的部分页表，是专门用来提高地址转换速度的

这里的高速存储器是联想存储器，是按照内容寻址的，并非按照地址访问

3.7.3.利用快表进行地址转换的流程

1.记录到需要转换的页号

2.在快表中查询，若已存在于快表中，则由页架号和单元号可以直接形成绝对地址

3.若不在快表中，就需要在页表中查询并形成绝对地址，并将该页登记到快表中去

4.当快表快要填满时，就会按照一定策略淘汰一个旧的登记表

3.7.4.进程表

进程表用于记录每个进程的名称，页表起始地址和页表长度

3.8.页式虚拟存储管理

这里的虚拟也是指外存，并非不存在

总体概括为：将进程的页面装入虚拟存储器，只调用部分到内存中，随后根据执行行为，动态的调入所需要的页和进行必要的页面调出

首次只把进程第一页信息存入主存，称为请求式页式存储管理

3.8.1.页式虚拟存储管理的页表

由于存在虚拟存储器，因此需要扩充页表项来存储虚拟地址，实际地址和一系列标志（主存驻留标志，写回标志，保护标志，引用标志和可移动标志）

3.8.2.页式虚拟存储管理的实现

处理地址是交给CPU处理的。如果查询的相关页表在内存中，那么就可以直接计算出绝对地址

若查询的相关页不在内存中，则会发出CPU缺页中断，特别注意的是，这里的中断是即时中断，即一有中断发生，立刻切断程序执行中断，不会等待程序执行完

缺页中断的处理：若有空闲的页架，就可以从辅存中调入页，来进行更新等。若没有空闲的页架，就需要决定淘汰页，以此来更新页表和快表

3.9.页面调度及其算法（页面置换）

3.9.1.页面调度的概念

页面调度是指当需要淘汰页时，该以何种方式进行淘汰，即选择淘汰页

3.9.2.页面调度算法

页面调度算法就是具体决定哪些淘汰页的算法

不理想的页面调度算法会导致刚调入的页面又立即被调出等等，这种现象被称为抖动或颠簸

这里要提一下缺页中断率

首先定义一下缺页：是指需要访问的页不在内存中

缺页中断率=缺页次数/总访问次数

页架数、页面大小、用户程序的编制方法会影响缺页中断率

3.9.2.1.OPT页面调度算法（综述）

理想的调度算法是：在调入新页面时，会首先淘汰不会访问的页，然后选择距今最长时间再访问的页

但由于CPU必定无法预知后续会发生的事情，因此OPT只可模拟，不可实现

3.9.2.2.先进先出FIFO页面调度算法

总是淘汰先调入主存的页，这是模拟程序的顺序执行，是有一定道理的，但并非最好

3.9.2.3.最近最少用LRU页面调度算法（最长时间不用）

淘汰最近一段时间中最久没用的页，这是比较好的页面调度算法，但是实现的代价太大了，需要维护特定的特殊序列才可以实现，可以用堆栈来进行更新

实现方法：一旦页面被调用到，就会更新计数器中的时间值，最近使用的时间值会大于以前使用的页面，用一个堆栈来进行统计，在栈底的页面就是很久未被调用的，但是时间开销依旧很大。

3.9.2.4.最不常用LFU页面调度算法

一旦发生中断，就将标志置为0，一旦被访问，就将标志加1

在计数最小的页面中淘汰即可

3.9.2.5.时钟CLOCK页面调度算法

利用指针来指向要被淘汰的页

这里也是用了引用标志位：

调入内存标志置为1

访问内存页面时标志置为1

每次用指针扫描时，都将标志为1的置为0，标志为0的淘汰

3.9.3.反置页表

反置页表及相关硬件机制在地址转换、存储保护、虚拟地址访问中发挥了关键作用。

内存管理单元MMU是为页式存储管理设置的专门硬件机构。MMU是CPU管理虚拟/物理存储器的控制线路，把虚拟地址映射为物理地址，并提供存储保护，必要时确定淘汰页面。

反置页表是MMU用的数据结构，用来完成内存页架到访问进程页号的对应，即物理地址到逻辑地址的转换。

3.9.3.1.设计的基本思想

针对内存中的每个页架建立一个页表

反置页表中，包含：进程号、进程标志位、页号、链指针

3.9.3.2.反置页表的地址转换过程

1.MMU读取逻辑地址中的进程号和页号

2.通过哈希函数，转换成一个哈希值，通过哈希表指向反置页表的一个表目

3.若在反置页表中存在该表目，就可通过索引（页架号）直接找到物理地址的页架号

4.若无该表目，就发生中断，等待系统处理

3.9.按需调页

由上可知，当CPU进行内存访问时，有以下三种情况

1.页面已装入内存，有对应的页帧

2.非法的页面引用

3.合法引用，但是引用对象不在内存中，即在虚拟内存中

3.9.1.解决合法引用时页表不在内存中的问题

在页表中有一个有效位，来反应是否缺页中断，这个有效位也可以来表示3的情况

1.判断是非法引用导致的缺页中断还是合法引用导致的缺页中断

2.找到一个空闲页帧，这个页帧用于将所需的页面信息存入

3.从外存中调入所需的部分页表

4.更新页表内容，更新有效位

5.缺页中断返回并重新调用引起中断的那条程序

3.10.页面调度及其算法（页面置换）

3.10.1.页面调度的概念

页面调度是指当需要淘汰页时，该以何种方式进行淘汰，即选择淘汰页

3.10.2.页面调度算法

页面调度算法就是具体决定哪些淘汰页的算法

不理想的页面调度算法会导致刚调入的页面又立即被调出等等，这种现象被称为抖动或颠簸

这里要提一下缺页中断率

首先定义一下缺页：是指需要访问的页不在内存中

缺页中断率=缺页次数/总访问次数

页架数、页面大小、用户程序的编制方法会影响缺页中断率

3.10.2.1.OPT页面调度算法（综述）

理想的调度算法是：在调入新页面时，会首先淘汰不会访问的页，然后选择距今最长时间再访问的页

但由于CPU必定无法预知后续会发生的事情，因此OPT只可模拟，不可实现

3.10.2.2.先进先出FIFO页面调度算法

总是淘汰先调入主存的页，这是模拟程序的顺序执行，是有一定道理的，但并非最好

3.10.2.3.最近最少用LRU页面调度算法（最长时间不用）

3.10.2.4.时钟CLOCK页面调度算法

利用指针来指向要被淘汰的页

这里也是用了引用标志位：

调入内存标志置为1

访问内存页面时标志置为1

每次用指针扫描时，都将标志为1的置为0，标志为0的淘汰

3.10.2.5.最不常用LFU页面调度算法

制定一个计数器，一旦被访问，就将计数器加1

在计数最小的页面中淘汰即可

3.10.2.6.MFU页面调度算法

由于部分页面刚调入内存，还未被引用，先删除计数器最大的页面

3.10.3.反置页表

反置页表及相关硬件机制在地址转换、存储保护、虚拟地址访问中发挥了关键作用。

反置页表是MMU用的数据结构，用来完成内存页架到访问进程页号的对应，即物理地址到逻辑地址的转换。

3.10.3.1.设计的基本思想

针对内存中的每个页架建立一个页表

反置页表中，包含：进程号、进程标志位、页号、链指针

3.10.3.2.反置页表的地址转换过程

1.MMU读取逻辑地址中的进程号和页号

2.通过哈希函数，转换成一个哈希值，通过哈希表指向反置页表的一个表目

3.若在反置页表中存在该表目，就可通过索引（页架号）直接找到物理地址的页架号

4.若无该表目，就发生中断，等待系统处理

3.11.页帧分配和系统抖动

3.11.1.页帧分配

一个进程在执行前，就必须拥有部分页帧，即这部分页帧可以使得该进程可以运行或初始化

这就会涉及到页帧分配常用的页帧分配有fixed allocation和priority allocation

3.11.1.1.Fixed Allocation（固定分配）

第一个方式是相等分配，即所有进程平分页帧

第二个方式是按照进程映像占用的逻辑空间大小，按相应比例分配页帧，类似按需分配

3.11.1.2.Priority Allocation（优先级分配）

即按照进程的优先级高低进行分配

若进程出现了缺页，会从自身进程占用的页帧中选取页面调出或者从较低优先级的进程中选取页帧来换出部分页面

3.11.2.全局分配与局部分配

全局置换：即进程可从所有页帧中选取一个进行置换操作，其可以选取其他进程的页帧

局部置换：进程只能从其自己占用的一个页帧中选取页面进行置换

3.11.3.抖动

抖动就等于进程一直忙于换入换出页面

有多种情况会导致抖动：

1.本身内存中的进程数就过多

2.原先进程不多，CPU利用率低，OS便将大量进程放入内存中，导致内存中进程过多，产生抖动，CPU利用率又一次降低，OS以为进程不够多，便再加入进程量，进而造成恶性循环

3.11.4.按需调页来处理抖动

按需调页的基础是，当CPU在执行一个进程的时候不需要用到该进程的所有代码，只需要将要执行的那部分内容调入内存中即可

同时，调入是懒惰交换，即只有CPU要求调度某一部分程序且该部分程序不在内存中时，才会进行调入

4.文件系统

4.1.文件系统基本概念

4.1.1.文件类型

大致分为数据文件和程序

其中数据文件分为数字文件、文本文件与二进制文件

文件类型的区分方式有很多，其中最常用的是以文件扩展名区分

4.1.2.文件结构

分为无结构文件、简单的记录型结构、复杂结构

无结构文件：一串字节流 可以插入控制字符来模仿相关结构文件

简单的记录型结构：如行文件、固定长度文件、变长度文件

复杂结构：格式化文档、重定位可执行文件

4.1.3.文件属性

文件名：唯一一项可行性指导文件信息

文件标识：在文件系统中，该标识才是唯一的身份标识

文件类型

位置：文件内容在存储设备中的首地址

长度

保护：即读、写、执行权限

时间，日期，用户标识

4.1.4.文件操作

创建文件读写文件内定位删除截取

这里举例打开文件与退出文件

打开文件：将文件从外存中复制一份到内存中

关闭文件：将文件从内存中保存到外存中去

4.1.5.文件访问方式

直接访问：定位要访问的数据块号直接访问

串行访问：只能从标记的开始位置开始访问

4.1.6.目录结构

目录结构与文件一样，驻留在磁盘

目录相当于一堆节点的集合，该节点包含了文件的基本信息

4.1.6.2.目录结构的分类

1.单层目录结构

即所有用户的所有文件都放置在同一层

2.二层目录结构

即为每一个用户建立一个独立目录

3.树型目录结构

即数据结构中树的类似结构

这里有绝对路径和相对路径的概念，与基本理解一致，创建新文件就是在当前目录创建一个新文件

4.有向无环图目录结构

可以实现文件的共享，即不同绝对路径下指向同一文件

操作系统用一个计数器来确定文件的共享量

当且仅当共享量-1=0时才可删除共享文件，即要删除共享文件的话，就要同时删去所有共享了该文件的目录下的该文件

5.图目录结构

即有环目录，这是必须要被避免的，方法如下：

1.保证指针不得指向子目录

2.利用算法清理孤立环

4.2.文件共享与保护

4.2.1.文件系统分区

文件系统大多是放在磁盘中的

通过RAID技术，可以将一个分区跨越多块磁盘，同时一个磁盘当然也可以分成多个分区

根分区：放置操作系统内核及其他的文件系统

在内存中有一张安装信息表：用于即时查询各种文件系统信息

4.2.2.文件系统安装

文件系统必须安装好、建立好目录才可被访问

每一个文件系统被安装在一个安装点上

4.2.3.共享

如何进行共享？那肯定是将一个文件放入一个用户组中，该用户组的用户对这个文件有一定访问权限

由上可知，我们需要两个ID来区分，User ID和Group ID分别来唯一的标识用户和用户组

4.2.4.保护

保护即对不同的用户开放不同的权限

基本权限如下：读写执行附加删除列表

4.3.文件系统实现

4.3.1.文件系统管理的基本概念

文件的基本逻辑单元为数据块

文件的管理信息被存在文件控制块FCB中

文件控制块的结构：

1.权限

2.执行的操作记录（新建，执行，读写等）

3.文件的用户，用户组

4.文件的大小

5.文件数据块或文件数据块的指针

文件系统是层次化的管理系统

文件系统多主存缓存，要求高效管理文件

磁盘的设备驱动程序仅操控物理设备，对其余如内存等硬件无关

4.3.1.1.层次化的文件系统

device（基础设备）-> I/O control（是最低层次的控制，直接与设备交互）-> basic file system（基础的文件系统，用于控制文件的读写命令）-> file-organization module（即管理逻辑块与物理块）-> logical file system（管理信息，数据结构，文件保护等）

4.3.2.文件系统的分序管理

1.每个文件都有引导块，用于将OS从磁盘引导至内存中

2.分区控制块保存分区的详细信息

3.目录结构用于组织、管理文件

4.3.3.文件系统结构

这里主要分析内存中的文件系统结构（打开与读取步骤）

1.用户申请打开一个文件

2.文件系统在内存的目录结构中查找相应的文件（目录结构原先在磁盘中，在第一次访问时会被部分或全部读入到内存中）

3.可以从目录结构中查到文件在磁盘中的存储位置，及相应文件控制块的位置

4.在打开文件时，每个文件在内存中都存在一张文件打开表（保存了打开指定文件的所有信息），在该表中查到需要访问的文件索引值

5.内存中还有一张打开文件的系统总表（在该文件系统下打开的文件都会在这张表内有记录），我们通过4中的文件打开表，与总表建立连接，文件系统会将上面找到的文件控制块信息放到这张表里去，以便于记录操作信息

6.进行文件数据块的查找读取等操作

4.3.4.虚拟文件系统 VFS

虚拟文件系统是对各种不同文件系统的统一管理，使得用户可以使用VFS提供的统一系统调用界面去访问所有类型的文件系统，这大大简化了用户端的压力

4.3.5.目录实现

目录实现总体有两种方法：线性列表和哈希表

1.线性列表

除了文件名，表项内含指针，指向文件的数据块

较为简单，但时间复杂度不好

2.哈希表

哈希表是通过哈希数据结构来实现目录

时间得到了简化，但哈希冲突等问题依旧不可避免

4.3.6.外存分配方法

这里讨论三种分配方法

连续分配链接分配索引分配

4.3.6.1.连续分配

连续分配中有一张表（FAT），记录了文件名起始地址长度

逻辑地址与物理地址的关系：

物理地址=文件起始物理地址+前面的总数据块数+数据块内部的偏移

逻辑地址的求法：指定数据块

优点：

1.与数组一样，可以随机访问

2.实现简单

缺点：

1.不可增加长度，因为后面的数据块可能被占用

解决方案：添加一个指针，当要增加文件长度时，该指针指向另一片连续空间

2.会有许多空闲块

4.3.6.2.链接分配

即如链表一般，一个文件的数据块不需要连续，而是通过指针互相连接

逻辑地址与物理地址的关系：

物理地址=文件起始物理地址+前面的总数据块数+数据块内部的偏移

逻辑地址求法：指针指向位置

特别注意：内部偏移量=原偏移量+1，+1是因为指针，该指针指向该文件的下一个数据块

优点：

1.可以充分利用空白数据块

缺点：

1.无法随机访问

优化方法：链表索引

即将所有指针的位置放入一张FAT中，这样就可以根据FAT迅速找到所需要查找的数据块的所指指针，根据该指针便可以快速得到相应数据块逻辑地址

2.太依靠指针，对磁盘设备要求高

4.3.6.3.索引分配

索引分配类似如上的链表索引

其与链表分配不同的地方就在于其抛弃了链表结构，真正通过索引块中的索引表（即表内的编号）来寻找数据块

逻辑地址与物理地址的关系：

物理地址=文件起始物理地址+前面的总数据块数+数据块内部的偏移

逻辑地址求法：索引编号

优点：

1.支持随机访问

2.支持动态伸缩文件长度，没有外部碎片

缺点：

1.需要建立索引数据块

2.索引数据块的访问耗时较长

索引分配的扩充办法——多重索引

当一层索引不够用时（即索引表满了但还未放下所有文件数据），可以采用二层索引，即让一层索引的每个指针再去指向一张索引表，这样就是一层索引的平方倍容量

4.3.7.空闲空间管理

通过位图来管理各个空闲块（一个一维数组）

对应下标的值来代表对应下标数据块的状态，0为空闲，1为被占用

因此，n个数据块需要n个单位长度的位图来管理，即占用n bit

5.大容量存储器

5.1.大容量存储结构

内存之外的存储器都成为大容量存储器，且一般越大读取速度越慢

5.1.1.磁盘结构

由若干面组成，每一面有一个同心圆，

每一面的同心圆可分成多个小同心圆，每一个小同心圆都是一个磁道且可等分成多个扇区

扇区是I/O的基本单位，读写均以扇区为单位

0扇区是最外边柱面的第一个磁道的第一个扇区

读写装置称为磁头，每一面上下都有磁头

与磁盘有关的数据计算：

1.平均宣传延迟时间，假设为X转/min，则该时间=60*1000/X/2，因为平均访问一个扇区对称扇区相加再相除，故要除2

2.CD-ROM的读取速率为150KB/s

5.1.2.计算机与外存储器的连接

当前有三种存储方式：

DAS随机附赠存储

NAS：网络附加存储

SAN：存储区域网

5.1.2.1.NAS的存储

通过LAN/WAN来进行存储

NAS - LAN/WAN - client

当用户需要访问时通过网络寻找

NAS不一定是盘阵，一台普通的主机就可以做出NAS,只要它自己有磁盘和文件系统，而且对外提供访问其文件系统的接口（如NFS,CIFS等），它就是一台NAS。就是将文件放在网络中，需要时通过相应的网络映射来找到该文件

5.1.2.2.SAN的存储

通过WAN/LAN存储

storage array - SAN - server - LAN/WAN - client

通过服务器等，用户可以访问SAN硬件（一个光通道交换机）来获取相关存储结构

SAN\NAS的区别：

可以这样来比作：SAN是一个网络上的磁盘；NAS是一个网络上的文件系统。其实根据SAN的定义，可知SAN其实是指一个网络，但是这个网络里包含着各种各样的元素，主机、适配器、网络交换机、磁盘阵列前端、盘阵后端、磁盘等。长时间以来，人们都习惯性的用SAN来特指FC，特指远端的磁盘。那么，一旦设计出了一种基于FC网络的NAS,而此时的SAN应该怎样称呼？所以，在说两者的区别时，用了一个比方，即把FC网络上的磁盘叫做SAN,把以太网络上的文件系统称为NAS，我们可以这样简单来理解。

普通台式机也可以充当NAS。NAS必须具备的物理条件有两条，第一，不管用什么方式，NAS必须可以访问卷或者物理磁盘；第二，NAS必须具有接入以太网的能力，也就是必须具有以太网卡。