[toc]

多图详解CPU Cache Memory

Q: 为什么遍历二维数组时，最好是先行后列？#

A:
先行后列是最常见的二维数组的遍历方式，而且效率非常高
因为二维数组的每一行都是一段连续的空间
根据局部性原理，操作系统再访问每个元素时，会将该元素附近多个元素一次性加载到缓存中来提高程序效率。

[toc]

原文链接：I/O中断原理

什么是中断#

中断指当出现需要时，CPU暂时停止当前程序的执行转而执行处理新情况的程序和执行过程。
即在程序运行过程中，系统出现了一个必须由CPU立即处理的情况，此时，CPU暂时中止程序的执行转而处理这个新的情况的过程就叫做中断。

我们知道CPU是按指令顺序进行执行的，操作系统每过大约15ms会发生一次线程调度(Windows下)，根据线程优先级先调度优先级高的线程。但是实际情况并没有那么简单，若我们接收到一个网络请求，如果要等当前线程执行完或15ms线程调度之后才去处理网络请求，网卡缓冲区很有可能会被占满，此时就发生了丢包。

中断类型#

中断分为硬件中断和软件中断。

硬件中断#

硬件中断即为硬件发出的中断信号，如I/O中断和硬件失效中断。

• I/O中断：由I/O控制器产生，用于发送信号通知操作完成等信号。
• 硬件失效中断：如掉电或存储器奇偶错之类的故障。

软件中断#

软件中断即为非硬件发出的中断信号，如程序中断和时钟中断。

• 程序中断：一些指令产生的异常(如算数移除、除数为0等)。
• 时钟中断：由处理器内部的计时器产生，允许操作系统以一定规程执行函数。

我们提到了操作系统每过大约15ms会进行一次线程调度，就是利用时钟中断来实现的。

I/O中断流程#

I/O中断通过中断处理器执行中断操作。
当外部设备的I/O模块准备好时，它会发送给CPU一个中断信号，CPU则会“立即”做出响应，暂停当前程序的处理去服务该I/O设备的程序。

为了更好的说明中断带来的性能提升，我们先描述一下没有中断时程序如何处理I/O操作。

无中断#

1. 当我们程序需要从硬盘读取一个文件时，会先检查内核缓存中是否有数据，若没有数据，则执行实际I/O操作。
2. 在I/O操作执行时，我们的用户线程将阻塞等待数据从硬盘写到内存中。对于用户来说线程是被阻塞的。
3. 在实际的I/O操作过程中，若没有中断操作，CPU会不断轮询检查I/O操作是否完成
4. 若I/O操作没有完成则继续调度其他线程，过一会儿再来检查。若操作完成，CPU将线程加入到线程就绪队列中并恢复线程上下文信息。
5. 线程处于就绪队列，可以被操作系统调度从而继续执行读操作，此时会将数据从操作系统内核缓存读取到用户缓存中。

有中断#

1. 当我们程序需要从硬盘读取一个文件时，会先检查内核缓存中是否有数据，若没有数据，则执行实际I/O操作。在I/O操作执行时，我们的用户线程将阻塞等待数据从硬盘写到内存中。对于用户来说线程是被阻塞的。
2. 在实际的I/O操作过程中，CPU向I/O模块(DMA控制器)发送读指令，然后就去调度其他线程。
3. 当I/O模块(DMA控制器)I/O执行完成后，会产生中断信号在通知CPU，CPU将线程加入到线程就绪队列中并恢复线程上下文信息。
4. 线程处于就绪队列，可以被操作系统调度从而继续执行读操作，此时会将数据从操作系统内核缓存读取到用户缓存中。

• 由上面可知，有中断还是没有中断对于用户来说线程都是阻塞的，对于操作系统内核来说通过中断方式主动通知CPU的方式减少了线程轮询判断，提高了线程执行效率。

中断处理完整流程#

当I/O设备完成一次I/O操作时，发生以下事件：

1. 开始I/O操作前，处理器将当前处理的相关信息如指令地址、必要的状态信息等保存到栈中，使得中断后可以恢复执行。
2. I/O操作完成后，设备给处理器发送一个中断信号。
3. 处理器响应中断信号。
4. 处理器对中断信号进行判断，若存在未响应的中断，则给产生中断信号的设备发送确认信号，确认信号使得设备取消它的中断信号。
5. 处理器将控制前转移给中断程序中，中断程序从栈中获取之前保存的信息，使得能继续执行I/O完成时的后续操作。
6. 处理器将中断程序入口地址载入到程序计数器中，使得处理器能继续执行下一个指令周期。

[toc]

全景流程图：

[toc]

7.1 基本概念#

7.1.1 文件定义#

文件是以计算机硬盘为载体的信息集合
需要提供文件系统进行管理

7.1.2 文件结构#

• 数据项：
  类似于int、string这种，或者 学号、姓名等值（类似sql表中的某个值内容）
• 记录：
  一组数据项集合
  比如学号和姓名，组成了学生记录（例如sql表中的某一行）
• 文件

按逻辑结构可以分为2类：
? 无结构文件： 一般都是二进制文件流文件，直接按顺序封装。这里面不包含记录的概念
? 有结构文件： 包含记录的概念
顺序文件：按记录中的某个关键字排序过，可二分查找记录行
索引文件： 需要1个索引表，记录每个记录的位置
索引顺序文件：先按关键字索引，在部分擦护照
直接、散列文件：用哈希键值确定记录位置

7.1.3 文件属性#

名称
标识符——确认文件唯一性
类型
位置——设备文件指针
大小——文件大小或者文件最大值
保护——访问控制权限
时间、日期
用户标志——哪个用户可用

7.1.4 文件常见操作#

• 创建文件
• 写文件——要指定一个写指针确认从哪开始写
• 读文件——读写共用一个指针，避免文件不同步
• 重定位——修改文件位置
• 删除文件——先删除文件目录项，再去清理空间，避免还没清理完有人却正要用
• 截断文件——把文件长度截断

7.1.5 open打开文件的过程#

1. 从外存把文件属性拷贝进内存，建立文件目录表
2. 返回一个文件编号给用户
3. 用文件打开计数器，记录有多少个进程正在打开该进程。当没有进程在使用时，回收内存。
4. 进程获取文件的以下信息：

• 文件指针
• 文件打开计数
• 文件磁盘位置
• 访问权限

7.2 目录#

目录就是文件的外部组织结构

7.2.1 文件的组织结构#

7.2.1.1 文件控制块FCB（文件目录项）#

• 存放了操作文件所需要的信息
• 文件目录中存放了许多FCB，可以通过FCB按名查取。
• 包含的信息有：
  基本信息： 文件名/物理位置/逻辑结构/物理结构
  存取控制信息： 访问权限
  使用信息：建立时间、修改时间

7.2.1.2 索引节点#

• 存放文件描述信息， 但是不包含文件名

• 文件目录中只存放文件名和i节点指针

• 可减少外村磁盘的查找速度

• 节点内容包括：
  标识符、类型、权限、存取时间
  地址长度、链接计数
  节点编号、状态（是否上锁）
  访问计数、设备号

• 文件打开时，会把索引节点从磁盘复制进内存，称为内存索引节点

7.2.1.3 文件控制块和索引节点的区别#

只需要文件位置信息等时，只需要拿文件控制块来唯一确认一个文件即可。
但是需要真正使用文件时，则需要索引节点里的信息
但如果把索引节点提前加载进内存的话，容易导致开销浪费。所以只有需要的时候，才回去用到索引节点，减少要拷贝的信息。

7.2.2 目录的结构#

单级目录
两级目录
多级目录：树形结构，有相对路径和绝对路径

7.2.3 文件层次结构#

从用户层从上往下排列

1. 用户接口：
   若干程序模块组织曾，每一个模块对应一个系统调用
2. 文件目录系统： 查找目录项，找到索引节点
   存取控制：用户要访问的权限和FCB中的权限做比对
   逻辑文件系统： 把要读取的记录转为罗季葵爱好
   物理文件系统——把逻辑块号转为实际物理地址
   设备管理模块——分配磁盘设备做输入输出

7.2.4 目录的实现原理#

线性列表——宠用目录项， 顺序检索。
哈希表——根据文件名得到key值

linux的目录实现原理：

7.3 文件共享#

7.3.1 软连接#

符号链接
建立一个文件， 文件中存放共享文件的路径
只有文件拥有者才能有指向文件的i节点指针
不会出现指针悬空， 不存在时，软链接会被删除。

7.3.2 硬连接#

即一个文件名的指针
各用户文件目录表用i节点指针指向同一个索引节点
当文件被删除，另一个用户就不能访问了。
容易出错。

7.4 文件的实现原理#

7.4.1 文件分配#

指怎么给文件分配磁盘块

7.4.1.1 连续分配：#

每个文件在磁盘上占一组连续的块
目录项记录文件的起始位置和长度
这样能让作业的磁盘寻道数最少
适用于长度固定的文件

7.4.1.2 链接分配：#

• 隐式链接：
  每个文件有一个链表， 每个节点是一个磁盘块，next指针指向下一个磁盘块

• 显式链接：
  用一个二维数组表替代next指针， [0]是盘块，[1]是下一个盘块
  这个表就是文件分配表FAT
  文件的第一个盘号也就是链表头 会放入FCB的物理地址中

7.4.1.3 索引分配#

为了防止这个表占据太大空间或者不够用
给每个文件有一个索引表，按顺序给出盘块
同时可以多级索引， 即可以给出磁盘中下一级索引表的盘块号。然后再去把盘中的二级索引表导入到内存中使用

7.4.2 存储空间管理#

即把哪些磁盘块分给文件呢？

• 文件卷、逻辑卷

以下是空闲块分配方法：

• 空闲表法—— 从空闲盘块表中选取， 释放的时候要做前后空闲区合并
• 空闲链块法：把空闲块组成链表
• 位视图法： 用010101确定是否空闲，可减少空闲块信息的大小
• 成组链接法：
  把n个空闲区分组，存入不同的空闲盘块栈中。并且有各种指针指向其他组的空闲盘块
  当某组内的空闲块变化时， 可以修改上一个块号栈的指针指向位置。
  

[toc]

7.5.1 常见磁盘概念#

7.5.1.1 结构#

• 磁道：可以立即为磁盘上的圈圈
• 扇区
  1个磁道会划分为多个扇区
  扇区即块（盘块，即上面文件里提到的盘块）
  存储能力受限于内道的最大记录密度
• 磁盘地址
  地址=(柱面，盘面，扇区号）
  以簇为单位作为各文件的磁盘分配

7.5.1.2 分类#

根据磁头动作，可以分为 固定头磁盘 / 活动头磁盘
根据磁盘是否固定，可分为 固定盘磁盘 / 可换盘磁盘

7.5.1.3 存取时间#

这个时间是衡量磁盘设计好坏的重要因素

• 寻找时间Ts （先找磁道，即找在圈里的第几层）
  指找到磁道的时间
  Ts = 0.2ms * 跨越磁道数 + st(磁臂启动时间，即扫描的那个东西开始动的时间)

• 延迟时间（磁道找完，定位扇区，即在圈上的哪个方位）
  定位置某一扇区的时间
  转一圈的时间/2作为延迟时间， 即对转一圈的时间求个平均（毕竟实际速度和扫描算法有关）
  Tr = 1/2r

• 传输时间（找到位置了，接着开始读数据）
  就是读写数据时间
  扇区占一圈的几分之几 * 转一圈的描述

其实就是磁臂按正常速度扫完这个内容要花的时间。

7.5.2 调度算法#

其实就是收到多个盘块的请求，选择扫描磁道的方法

• FCFS 先来先服务
  按盘块请求里的顺序来扫描
  适合那种聚在一起的盘块
• SSTF 最短时间优先
  一直找最近的磁道
  如果频繁收到比较近的磁道，可能造成其他磁道饥饿，无法被访问
• SCAN 扫描、电梯算法
  从上倒下，再从下到上，再从上到下，扫到请求里的盘块就算检测到。
  对两端的节点不公平，扫描频率会比中间的低
• C-SCAN 循环扫描算法
  方向固定，每次都是从下往上， 当到达顶部时， 直接快速转回到底部，然后再继续从下往上（快速转回的过程不会响应任何盘块请求）

7.5.3 扇面划分#

• 交替编号
  1 3 2 4这样编号
  因为读出数据需要时间，这时候如果让磁道继续转动，可能已经移动到后面第2个扇区了。
  但数据又是希望能连续读的，所以交替放，保证读完后，不用再移动，直接用这个区的
• 错位命名
  第一层磁道的扇区是1 3 2 4
  第二层磁道的扇区是4 1 3 2
  第三层的磁道是 2 4 1 3
  可以看到每一层磁道的扇区，整体都右移了一位
  这是为了减少切换磁道时，重新扫圈的时间

7.5.4 磁盘管理#

7.5.4.1 初始化#

• 低级格式化
  初始化扇区号和纠错代码（ECC），ECC用于检验磁盘正确性
  物理分区
• 逻辑格式化
  初始化磁盘数据结构
  分为C\D\E盘， 对linux就是那些opt分区之类的

7.5.4.2 引导块#

磁盘的启动程序会放在磁盘的引导块上

7.5.4.3 坏块#

对于损坏的磁盘块， 他会检测并避免再使用这些坏块。

更多

7.6 IO管理#

7.6.1 IO控制方式#

• 程序直接控制
• 中断驱动方式
• DMA方式
  特点：
  以块位单位
  数据直接进入内存
  开始和结束需要CPU干预，无法通过外设自己完成

DMA会设置4个寄存器：
命令/状态寄存器CR——用于接收CPU发来的控制命令，存储当前状态
内存地址MAR——存放内存地址
数据寄存器DR——暂存数据
数据计数器DC——用于传输计数

工作过程：

1. CPU收到程序发来的DMA请求——发出控制命令
2. 启动DMA->DMA存取->结束
3. 发送中断信号——CPU中断，通知调用程序DMA结束

DMA和中断的区别

• DMA：是一种无须CPU的参与就可以让外设与系统内存之间进行双向数据传输的硬件机制，使用DMA可以使系统CPU从实际的I/O数据传输过程中摆脱出来，从而大大提高系统的吞吐率.
• 中断：是指CPU在执行程序的过程中，出现了某些突发事件时CPU必须暂停执行当前的程序，转去处理突发事件，处理完毕后CPU又返回源程序被中断的位置并继续执行。

所以中断和DMA的区别就是DMA不需CPU参与，而中断是需要CPU参与的。

• 通道控制方式
  是DMA的升级版
  指令单一，和CPU共享内存
  是一种硬件、特殊的处理器，无内存，指令存在主机内存中。
  传输数据的带线啊哦、内存存放位置，通道可以自主决定！
  即比DMA更高级了

7.6.2 IO层次性结构#

从上往下介绍

1. 用户层IO软件

• 由用户提供的库函数
• 需要一系列系统调用

2. 设备独立性软件
   曹旭哦提供相关调用

• 功能： 指向设备的共有操作，向用户层提供统一的IO接口（例如unix底层和IO相关的c函数）
• 支持设备独立，程序和设备可独立切换，不强依赖。

3. 设备驱动程序
   商家提供

• 实行系统对设备的具体操作
• 具体的硬件设备会配置1个驱动

4. 中断处理程序
5. 硬件设备

7.6.3 设备控制器（适配器）#

• 通过寄存器与CPU进行通信
  具有内存映像，占有CPU内存
  寄存器独立编址，采用IO专用地址
• 功能
  接收、识别CPU的命令
  实现数据交换
  提供设备状态、提供地址识别
• 组成部分
  与CPU的接口——数据、地址、命令线
  与设备的接口——1个接口一个设备
  IO控制器（地址、命令译码）

更多

7.6.4 IO核心子系统#

• 是一个进行设备控制的子系统
• 内核无需做太多的IO设备管理
• 子系统实现IO调度队列，改善IO的响应时间，比如磁盘调度

7.6.4.1 缓冲区#

磁盘高速缓存： 在内存中开辟单独空间，利用未利用的页做缓冲池

缓冲区的目的：
减少CPU\IO速度的不匹配
减少CPU中断
提高IO和CPU的并行性

缓冲分类

• 单缓冲：
  IO和CPU之间只有1个缓冲区。 处理数据的时候，可以提前读进来1份。
• 双缓冲
  2个缓冲区。
  缓冲1满了之后，装2. CPU可以接连取
  缓冲区1满了之后，
• 循环缓冲
  有一个缓冲循环队列， 有2个指针
  in指针指向空的缓冲，用于进行外部数据的IO输入。
  out指针指向满的缓冲，用于把数据读进系统中
• 缓冲池
  要用到的时候，就从池中取一个缓冲区。 用完就归还

7.6.4.2 设备分配和挥手机制#

设备分配分类

• 独占设备——只允许单进程
• 分时设备——分时交替IO
• spooling设备——虚拟设备

设备分配表
DCT设备控制表—— 1个控制表代表一个设备。
COCT控制器控制表——与内存交换数据。请求通道服务——指向CHCT
CHCT通道控制表
SDT系统设备表——记录系统中已连接的设备情况

7.6.4.3 spooling技术（虚拟化设备）#

• SPOOLing 技术是用于将 I\O 设备进行虚拟化的技术，
• 它是专门用于欺骗进程的。
• 就拿打印机举栗吧，我就买了一台打印机，但此时我打开了 word 和 pdf，想要打印 word 和 pdf 中的内容；此时计算机中有2个进程，word 进程和 pdf 进程，这两个进程都认为自己拥有一个打印机，那么是否此时我作为计算机的主人就拥有2台打印机了呢？当然不是啊，我又不是睁眼瞎，我就看到了一台打印机啊
• 这就是通过虚拟化技术欺骗了2个无知的进程。具体的实现道理我都懂，那么怎么实现欺骗进程的目的呢（也就是怎么实现SPOOLing技术呢）？
• SPOOLing 技术首先需要提供统一的调用接口，每一个进程都可以调用该接口，这样在进程看了自己是拥有该设备的。需要将磁盘设备和内存作为缓冲区，磁盘设备上的缓冲区称作井，而内存上的缓存区被称作缓冲区。需要一个专门的输入输出进程来实现对 I/O 设备的读写数据。

以向 I/O 设备写数据为例子，做出概念图，如下所示：

首先某一个进程（例如 word）调用了统一的接口，然后进入内核。内核例程负责将 word 想要打印的内容做成一个打印申请表，将这个申请表放入打印输出队列中（这个队列在输出井中）。然后由输出进程从打印队列中取打印申请表，根据表格内容将用户数据从磁盘中取出放入内存输出缓冲区，然后再输出到 I/O 设备中。输出进程会不断的查看打印输出队列，直到队列为空，则输出进程被阻塞。

即对于进程来说，看起来都已经输出或者输入了，实际上看还没有响应，有延迟，物理上共用1个设备。逻辑上是2个设备

Q: 讲一下阻塞和非阻塞的区别？（注意没有携带IO，对应的是广义的方法调用时的阻塞和非阻塞）#

A:
阻塞，对应的是执行线程会被挂起，线程时间片暂停执行，有结果了才返回。
非阻塞，线程不会挂起，而是直接返回结果或者异常，让线程调用者自己确认是否完成了读取，因此线程不会挂起。

阻塞和非阻塞的区别就在于：是否需要线程自己轮询检查

Q: 同步和异步的区别？（注意没有携带IO，对应的是广义的方法调用时的同步和异步）#

A:
同步， 调用Io方法时， 必须等结果返回，这个方法才会结束。
异步， 调用io方法时， 不需要等结果。 由接收方进行异步的通知或者发请求，因此线程可以作别的事情了。（与非阻塞IO不同）

同步和异步的区别就在于：是否通过回调函数进行通知确认结果。
综上可知，同步和异步,阻塞和非阻塞,有些混用,其实它们完全不是一回事,而且它们修饰的对象也不相同。

Q: 讲一下五种IO模型#

A:

1. 阻塞I/O（blocking I/O）
   调用recv()系统函数，阻塞挂起线程
2. 非阻塞I/O （nonblocking I/O）
   socket才支持，设置非阻塞时， recv是返回错误， 线程不断轮询
3. I/O复用(select 和poll) （I/O multiplexing）
   本质上是阻塞IO，关键在于可以监听多个端口上的读或写事件，直到有数据可读或可写时，才真正调用I/O操作函数
4. 信号驱动I/O （signal driven I/O (SIGIO)）
   需要绑定一个信号驱动。当数据准备好时，进程会收到一个SIGIO信号，可以在信号处理函数中调用I/O操作函数处理数据
5. 异步I/O （asynchronous I/O (the POSIX aio_functions)）
   当一个异步过程调用发出后，调用者不能立刻得到结果。实际处理这个调用的部件在完成后，通过状态、通知和回调来通知调用者的输入输出操作。
   需要服务调用方实现通知或者回调机制。
   

[toc]

6.1 内存管理的概念#

• 内存管理指操作系统对内存的划分和动态分配

• 地址空间：
  逻辑地址空间： 相对地址， 从0开始编址
  物理地址空间： 地址转换的最终地址

程序运行时和
编译： 吧源代码编译成目标模块
链接： 吧目标模块、库函数链接成1个装入模块
链接属于形成进程逻辑地址的过程

装入：
绝对装入： 编译时就确定了装入地址
可重定位装入： 根据内存情况， 把程序装到适当位置
运行时动态装入：运行前才真正把程序装起来（前面2个都是先分配，再装，再运行）

6.2 内存防溢出机制#

即怎么防止内存越界

• 设置上下限寄存器：
  存放内存中该进程的 上下限地址
  每次访问时，判断是否越界

重定位+界地址：
重定位寄存器——存放物理地址的最小地址
界地址寄存器——存放逻辑地址的最大值

先把访问地址（相对地址） 与界地址比较是否越界
再加到重定位寄存器上，作为物理地址

min + x， 且x <max， 这样保证地址在min到min+max之内

6.3 内存分配机制#

6.3.1 连续分配内存#

连续分配指 为用户程序分配的内存空间一定是连续的

6.3.1.1 单一连续：#

内存分为系统区和用户区2个区
每次用户区只能放1个程序， 这样可确保不会越界

6.3.1.2 固定分区分配#

用户区分成若干个大小的分区， 每个分区只能装一个作业。
程序如果大了会装不下
程序小了则有内存碎片

6.3.1.3 动态分区分配#

程序装入内存时，按照所需大小动态生成1个分区。 有多少碎片空间就给多少

可能会存在碎片， 比如中间的进程结束了， 于是中间就空出来一个内存碎片，而可能因为太小，其他进程帆布进来。

动态分配策略：

• 首次适应： 从上往下找第一个满足的分区——最简单也最好
• 最佳适应： 找一个大小差距最小的分区——最烂，碎片最多
• 最坏适应： 直接找最大的分区转入
• 邻近适应： 从上次查找位置开始找，而不是从第一个碎片位置开始找。——末尾碎片会很多

6.3.2 非连续内存分配#

非连续指进程内存可以 分成不同地址存放，不一定全部集中在一起。

6.3.2.1 分页#

把内存划分成固定大小的块， 进程以块为单位申请多个不同位置的块作为空间。

• 页表：
  每个进程PCB中会有一个页面寄存器PRT， 告知页表的起始位置和起始长度
  找到页表后， 页面中会告知你所持有的页号和偏移。
  通过 页号 * 块大小 + 偏移， 可知道这段内存的起始位置。

进程每次想通过虚拟地址去定位物理地址时，都需要先去页表中找到虚拟地址对应的页，然后再得到物理地址。

• 快表TBL（Translation Lookaside Buffer )）：
  为了避免每次斗取页表换算地址， 快表会缓存 虚拟地址->物理地址的直接映射，加快速度
  

• 多级页表
  地址空间超级大， 1页装不下怎么办？
  用多级
  一级页表指明二级页表的地址
  二级页表再去实际地址
  这样就可以有多页了。
  

6.3.2.2 分段#

分页的话， 页的长度时固定的， 所以偏移量的最大值是固定的

分段的话不限制偏移量最大值，即可以很长一段。

分段属于二维地址空间， 因为他除了给出逻辑地址，还得给出段长

有利于做动态链接： 程序动态修改

6.3.2.3 段页结合#

作业先分成若干段， 再把段分页， 每个段可以找到一个也变

段号S 页号P 页内偏移

Q: 遍历二维数组的时候, 行遍历优先和列遍历优先的效率差别, 为什么会这样

A: 按行遍历比按列遍历的效率高体现在这些方面：

1. CPU高速缓存
2. CPU缓存从内存中抓取一般都是整个数据块，所以它的物理内存是连续的，几乎都是同行不同列的，而如果内循环以列的方式进行遍历的话，将会使整个缓存块无法被利用，而不得不从内存中读取数据，而从内存读取速度是远远小于从缓存中读取数据的。随着数组元素越来越多，按列读取速度也会越来越慢。

6.4 虚拟内存#

6.4.1 概念#

虚拟地址可以让进程获得比实际内存要大的内存
特征：

• 多次性——作业可分多次装入内存
• 对换性——可在运行时对内存做兑换处理
• 虚拟性——逻辑上可充分扩充容量

要求：
必须使用非连续分配方式——分页、分段、段页
硬件需要支持 页表、中断、地址变换机构

理论依据：
时间局部性—— 指令和数据总是会在一段时间内被连续访问
空间局部性——某单元被访问，那么他附件的单元也很大概率会被访问

6.4.2 请求分页机制#

再分页的基础上， 增加了2个功能：
请求调页——当页面不在内存中时，从外村申请调入
页面置换——把暂时不用的内存换出去，给其他需要进来的页腾出空间

页表项：
页号、物理块号
状态位P：是否已经调入内存
访问字段A： 记录访问次数或者访问标记，用于置换策略判断
修改维 M： 记录是否被修改过
外村地址——当页被换出去时，指明这个页在外存的何处

缺页中断机构： 当页面不存在时， 负责产生缺页中断，进行页面置换操作。

缺页只能高端和系统中断不同， 属于指令中的操作，在执行期产生多次

地址变换机构：
1.先检索快表，如果能找到，则直接修改页表项的访问位。
2.快表中没有，则去 再检索内存中的页表，通过状态为P确认是否在内存中
如果不在，则产生缺页中断。

6.4.3 工作集概念#

驻留集：指系统给每个进程分配的内存中实际页面集合
但是可能分配了10个， 却只有5个经常在用

工作集： 某时间段内，这个进程访问和使用的页面集合

通过工作集， 系统可以评估这个驻留集是否需要做删减，以及哪些页应该持续保留。
这样可以减少抖动，即减少内外村之间频繁的交换页

6.4.4 页面置换算法#

• 最佳置换算法：
  选未来最长时间不会被用到的页
  这个要基于预测，比较难
• 先进先出FIFO
  可能引发bleady异常：

较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出，并且有Belady现象。所谓Belady现象是指：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。

• 最近最久未使用（LRU）
  选之前最长时间没访问的， 引入优先队列（最大堆）
  需要设置访问时间字段
• 简单时钟clock（最近未使用NRU）
  每个页有个标记。
  刚换入内存或者被访问时，都会置1

如果需要换页时，步骤如下：

1. 扫描围成换的页链表
2. 如果标记为1，则改成0，继续往下扫
3. 如果位0， 则替换，并让指针指向下一页。

• 改进的clock
  把标记为改成 访问位u和修改维m
• 1类(A =0, M = 0)：表示该页面最近既未被访问，又未被修改，是最佳淘汰页。
• 2类(A =0, M = 1)：表示该页面最近未被访问，但已被修改，并不是很好的淘汰页。
• 3类(A =1, M = 0)：表示该页面最近已被访问，但未被修改，该页有可能再被访问。
• 4类(A =1, M = 1)：表示该页最近已被访问且被修改，该页可能再被访问。

1. 先优先找u=0和m=0的页，有就直接替换
2. 没有，则找 u = 0 且m=1的页（ 没访问的最优先替换）， 做替换
3. 如果中间遇到U=1的， 则都会置0， 如果m=1的也会置0
4. 如果一圈都没有，则下一圈肯定有01或者00的。

6.4.5 页面分配量策略#

• 固定分配，局部替换
  每个进程分配固定的物理块， 且只能自己的块之间做替换
• 可变分配，全局替换
  缺页时，可以从全局队列的页替换
• 可变分配，局部置换
  自己替换自己，但是不够的时候可以加块

分配来源：
对换区：频繁切换的区
文件区：补怎么会变动和修改的

6.5 linux中的内存机制#

[toc]

4.1 调度的概念#

从就绪队列中选一个进程分配给处理机
处理机调度是操作系统进行多道程序运行的核心

4.1.1 三级调度#

操作系统中有三种调度：

• 作业调度（外存到内存）
  属于一种高级调度
  从外存队列中选一批作业进入内存进行执行。
  可以理解为有人一次性执行了10000个脚本，这时候的脚本作业是有调度机制的，没法一次性全部加载到内存中执行。
• 内存调度（外存->内存）
  就是决定将哪个挂起状态的进程从外存重新调回内存。 但是此时还没开始跑任务，只是从外存切换到内存就绪队列
• 进程调度（内存->CPU)
  从内存就绪队列中选择进程， 进行执行。

分别是从高级到低级， 频率从低到高

4.1.2 常见调度方式#

剥夺式调度： 按优先级、短时间、时间片进行抢占式调度，会强制暂停某些进程
非剥夺调度： 当某个进程完成，或者出现阻塞，才会重新分配CPU。 不可用于分时和实时系统。

linux属于剥夺还是费伯多？

4.1.3 调度系统设计的评价准则#

CPU利用率： CPU运行时间/ 空闲时间加运行时间
系统吞吐量： 单位时间内完成的作业数量
周转时间： 从提交到作业完成的时间， 包括了等待\IO等
等待时间： 在就绪队列中等待的时间之和
响应时间： 从提交请求到系统首次擦还是你哼响应的时间。

4.2 进程调度算法#

4.2.1 FCFS先来先服务#

• 不可抢占式
• 用于作业调度和进程调度
• 有利于CPU繁忙作业，即基本都在高强度计算，不会有IO操作等。这时候一般不允许抢占。

4.2.2 短作业优先#

• 从优先就绪队列中选择 预估运行时间最短的作业
• 可能导致长作业的饥饿
• 但是能让 平均等待时间最短， 但一般不考虑这个

4.2.3 优先级调度算法#

• 选择优先级最高的作业运行
• 有2种优先级判断方式：
  1. 静态优先：进程创建时已经决定了优先级
  2. 动态优先: 根据CPU占有时间、等待时间，判断他是否属于IO繁忙，并调整优先级

4.2.4 高相应比优先#

• 相应比= （等待时间+ 估计运行时间） / 估计运行时间
  这样等待的越久，就越有可能出队，避免4.2.2中的长作业饥饿

4.2.5 时间片轮转#

• 时间片用完，立刻切换到下一个进程
• 时间片的长短，取决于系统的处理能力、队列中的进程数量、系统响应时间

4.2.6 多级反馈队列调度算法#

• 设置多个不同优先级的队列。
• 队列优先级越高， 运行的时间片就越小
• 每当有一个作业跑完1次时间片，就放到下一级队列（相当于降低优先级）
• 当新进程进入，默认放入高优先级队列。对于短作业而言可以立刻响应，而他如果是长作业，则会逐步降低优先级。
• 相当于结合了短作业优先、 优先级调度、 时间片3个算法的优势

4.2.7 linux和windows中的调度算法#

linux的调度算法

Linux 标准内核实现两个调度类：采用 CFS 调度算法的默认调度类和实时调度类.

CFS 调度程序并不采用严格规则来为一个优先级分配某个长度的时间片，而是为每个任务分配一定比例的 CPU 处理时间。每个任务分配的具体比例是根据友好值来计算的。友好值的范围从 -20 到 +19，数值较低的友好值表示较高的相对优先级。具有较低友好值的任务，与具有较高友好值的任务相比，会得到更高比例的处理器处理时间。默认友好值为 0。

[toc]

5.1 同步的概念#

不同进程之间需要相互制约，或者存在先后顺序，就会用到同步。

• 临界资源： 1次只允许1个进程使用
  临界资源访问过程分为四步：

1. 进入区： 检查和设置临界区标识
2. 临界区： 访问和使用资源
3. 退出区： 清楚临界区标志
4. 剩余区：？

• 同步： 也称作直接制约关系
  为完成某个任务，多个进程需要协调工作次序并等待，即这个制约关系应该是意料之中出现的。

• 互斥： 间接制约关系
  因临界资源冲突而引发访问和等待，即不是他想要的制约关系。

• 同步机制准则：
  空闲让进： 资源空闲的时候允许进入
  忙则等待： 临界区被占用，其他等待
  有限等待： 不能一直等待，出现出现饥饿
  让权等待： 无法进入临界区时，要放弃CPU挂起一段时间，避免一直占用CPU

5.2 临界区的互斥实现原理#

5.2.1 软件实现方式#

• 单标志法：就是在临界区前后判断turn标志确认临界区谁可进， 当从临界区粗来，再修改临界区标志为另一个进程可进。
• 双标志法先检查： flag[i]标识低i个进程是否在临界区。 每次检查flag确认是否能进
  可能检查时两个人都通过了，就出错。
  属于先查，后改
• 双标志法后检查：
  即先改后查，可能2个人同时改，引发饥饿
• peterson法：
  turn和flag[]一起用。
  用turn判断谁可以先进。这样避免2个人同时改。

5.2.2 硬件方式#

• 中断屏蔽——禁止一切中断发生？？？ 这啥意思
• 硬件指令
  TestAndSet 原子操作， 读取lock并修改lock为true
  swap： 原子交换命令， 交换2个字节内容。

5.3 常见同步方式#

5.3.1 信号量#

共享资源数目有限时一般使用信号量。

• P操作——wait 申请和获取资源
  先减去信号量，再判断， 如果信号量<0，则进程加入阻塞队列

• V操作——signal 释放资源
  每次操作时，直接增加信号量
  此时说明已经有人空闲了一个资源了。
  当发现信号量此时<=0， 则从阻塞队列里选一个出队

5.3.2 管程#

在内存中而非外村中
是一个共享数据结构

1次只允许1个进管道
可以理解为信号量变成了 只有1的管道
为满时，不可写
为空时，不可读

管程和信号量的区别：
1、信号量可以并发，并发量是取决于s的初始值，而管程则是在任意时刻都是只能有一个。

2、信号量的P操作在操作之前不知道是否会被阻塞，而管程的wait操作则是一定会被阻塞。

3、管程的进程如果执行csignal后，但是没有在这个条件变量上等待的任务的话，则丢弃这个信号。进程在发出信号后会将自己置于紧急队列之中，因为他已经执行了部分代码，所以应该优先于入口队列中的新进入的进程执行。

4、当前进程对一个信号量加1后，会唤醒另一个进程，被唤醒进程程与当前进程并发执行

5.4 同步经典例子#

5.4.1 生产者消费者模型#

简单的信号量模型

5.4.2 读写者问题#

读可以并发读
写的话，必须等读的人都结束了才能写。

5.4.3 哲学家吃饭问题#

每个人都先拿自己最左边的筷子，就会吃不上饭

1次拿2双即可，而不是先拿左手，再拿右手。

5.4.4 吸烟者问题#

3种原材料的供应问题
每个人只有1种材料。
但是吸烟要3种材料。
供应者用完了再上新的
于是吸烟者每次要直接拿2个，而不能1次只拿1个。

5.5 死锁#

5.5.1 原因#

• 进程请求资源的顺序不对， 出现交叉申请的情况
• 共同竞争不可剥夺资源

5.5.2 死锁的4个条件和预防#

1. 互斥——1个资源只能1个进程使用
2. 不可剥夺——不允许主动抢占，必须等对方释放了才能用。
3. 请求和保持——
   请求：自己占用资源的情况下，还可以继续请求其他资源。
   保持： 被阻塞的情况下， 自己持有的资源仍然不会释放
4. 循环等待： 出现循环等待链

根据上面4个条件，可以给出4个预防措施

1. 破坏互斥——让资源可共享使用——无法实现
2. 破坏不可剥夺—— 当请求不成功时，会释放自己的资源给别人使用（这样确认不会有人卡着，要么是有人正在全力计算，要么就是阻塞后直接释放，下次再请求）—— 可能引发反复申请，开销大
3. 破坏请求和保持—— 一次性申请全部资源，不会申请到一半的情况（资源浪费，比如有时候确实得先用一半，接着再用另一半）
4. 破坏循环等待—— 请求资源时，按照顺序请求资源，给资源编号按优先级申请。——太麻烦

5.5.3 死锁检测和解除#

该方法不会影响资源分配。 只会定时地去检测，然后看是否解除某些死锁

以进程和资源构建一张DAG图

• 死锁检测定理：

1. 找到申请资源充足的进程，消去该进程的所有边
2. 继续消除，如果边被全部消完，说明无死锁。如果无法消除完，则存在死锁

• 死锁接触：
  资源剥夺——把死锁进程暂时挂起， 以释放资源，等ok后再放回来。
  撤销进程法——按优先级，强制kill一些进程
  进程回退法—— 把请求资源的操作回退，直到回退到不会发生死锁的DAG

5.5.4 死锁避免算法#

这个算法会影响分配过程，即在资源分配前判断以下。

5.5.4.1 系统安全状态（什么时候系统是安全的）：#

1. 存在一个安全序列P1\P2\P3， 理解为3个进程，并给出3个进程此时所需的资源
2. 先把剩余资源都给P1，然后P1用完后再给P2， P2用完再给P3
3. 按这个顺序下来都没发生资源不够的情况的花，则认为至少是安全的（即至少可通过顺序给资源保证顺利完成剩余任务）

5.5.4.2 银行家算法#

假设进程数量有n个
假设资源有r种

定义以下数组
各资源当前可用数量 Avaialbe[r]
各进程最大需求 max[n][r]
各进程当前已占资源 allocation[n][r]
各进程还需要的资源量 need[n][r]
此时的某进程i对各资源的请求量 request[r]

银行家算法描述：

1. request必须小于等于need，否则request有错误（即你肯定不能要得过多，都超出需求了）
2. 检查request是否比avali大，如果过大，则资源不足
3. 如果1和2都检验通过， 则分配资源，修改avalible、allocation、need
4. 执行安全性算法， 判断按照最优情况给资源时，是否会出现资源不足
   5.若分配不会导致系统进入不安全状态，则分配，否则等待一段时间，再判断

安全性算法描述：
按顺序，每次把进程剩余need的资源都占去，并剪掉avalid， 看下遍历完是否会出现不够用的情况

5.5 进程、线程同步的区别#

这个 同步 的概念都是一致的. 不论是进程还是线程.
不同在于所采用的同步方式, 进程的同步方式是线程的同步方式的子集. 换句话说, 进程之间的同步方式会比线程之间同步方式选择小. 就这样而已.

线程通信一般是指同一进程内的线程进行通讯，由于在同一进程内，共享地址空间，因此交互比较容易，全局变量之类的都能起到作用。

进程通信一般是指不同进程间的线程进行通讯，由于地址空间不同，因此需要使用操作系统相关机制进行“中转”，比如共享文件、管道、SOCKET。

5.6 linux延申#

linux的死锁检测、避免机制Lockdep
http://kernel.meizu.com/linux-dead-lock-detect-lockdep.html

[toc]

3.1 概念#

• 是基本的CPU执行单元
• 是程序执行流的最小胆小
• 被系统调度和分配的基本单位

3.1.1 目的#

• 提高系统性能
• 减小程序并发执行时的时空开销

3.1.2 组成#

• 线程id
• 程序计数器PC
• 寄存器集合
• 堆栈

3.1.3 实现方式#

一般会有2种线程：

• 用户级线程ULT： 创建发生在用户空间
• 系统级线程KLT： 完成系统内所有线程的管理，提供给用户一定的线程管理接口。

ULT和KLT的映射关系分类（即用户线程能给哪些系统线程管理）：

• 多用户线程对应1个系统线程。 即所有线程公用一个线程管理接口
  这样如果一旦阻塞就全部阻塞
• 一对一： 每个用户线程单独使用1个系统线程做管理
  这样会导致系统线程过多，开销大
• 多对多： n个用户线程对应m个内核线程（n>=m)
  这个比较好

linux用的是哪种呢？

3.2 进程和线程的区别#

• 从调度上看
  线程是CPU调度的最小单位
  进程是拥有资源的基本单位
• 切换
  同一进程内的线程之间切换，不用引起进程切换
  从a进程的线程跳到b进程的线程，需要引起进程切换
• 资源
  线程只独立拥有一点点小资源（线程栈、共享虚拟地址空间）
  进程则拥有很多
• 通信： 线程可通过读写进程的全局变量来通信，但是进程之间通信则无法依赖变量。
• 开销
  线程的系统/时空开销少
• 并发
  进程和线程都支持并发。
  是否支持并行要看CPU情况。

Q: 并发和并行有什么区别呢？#

A:

• 并发指 在某一个时间段内跑多个任务， 这些任务可能抢占同一个CPU资源， ”存在交替执行“
• 并行指 同一时刻，有多个任务同时在跑， 即分别占用不同的CPU跑任务。

[toc]

2.1 概念和特征#

• 是资源分配、调度的独立单位

• 进程包含以下内容：

  1. 程序段（代码段）
  2. 数据段（存数据）
  3. PCB进程控制块（ 进程存在的唯一标志）

• 进程具有动态性，是一个动态的概念。

• 每个进程具有独立的PCB结构， 资源也独立。

2.2 进程状态机图#

2.3 进程状态变化时的具体过程#

2.3.1 进程创建#

• 创建过程：

1. 分配进程；申请PCB
2. 分配资源
3. 初始化PCB
4. 插入到系统的就绪队列

• 父进程创建子进程：
  子进程可以继承父进程的所有资源。
  父进程退出时，需要杀光子进程。

2.3.2 进程的终止#

终止有3种触发情况

• 正常结束——运行完毕
• 异常结束——越界、非法
• 外界干预——直接kill进程

终止的触发过程：

1. 根据进程标识符，找到PCB控制块，读取进程状态
2. 如果正常执行，则终止进程。 如果有子进程，则杀死子进程
3. 归还资源给父进程或者操作系统
4. 将PCB从系统PCB队列删除

2.3.3 进程的阻塞#

阻塞的过程：

1. 根据标识符找到PCB
2. 切换PCB状态为阻塞状态
3. 把PCB插入到等待队列中

2.3.4 进程唤醒#

唤醒的过程：

1. 根据标识符从等待队列中找到PCB
2. 移出等待队列，修改运行状态为就绪
3. 插入到就绪队列

2.3.5 进程切换#

1. 保存当前处理器上下文信息，更新PCB并移入队列
2. 选择另一个进程，更新PCB状态
3. 更新内存管理
4. 恢复处理器上下文

上面可以看到基本是围绕 PCB、等待队列、就绪队列、进程状态更新这4个概念展开的。

注意调度是一个决策行为， 而切换是一个执行行为， 因此都是先调度，再切换。

2.4 进程的组成#

2.4.1 PCB进程控制块#

pcb控制块在进程创建后， 就常驻内存中
是进程的唯一标志

PCB控制块包含以下内容：

• 进程描述
  包括进程标识符 和 用户标识符
• 进程控制和管理
  包括 当前运行状态、 优先级、 入口地址、 外村地址、 进入内存时间、 CPU占用时间、信号量
• 资源分配清单
  包括 3个段指针（代码段、数据段、堆栈段）， 文件描述符， 键盘/鼠标资源
• 处理器相关信息
  寄存器值
  程序状态字

PCB控制块的组织方式：

• 链接方式： 各运行状态都有1个队列， 相关状态PCB都会放在链表队列中（因此可以非顺序取出）。
• 索引方式： 建立一个索引表，指向对应pcb， 即用数组去组织

2.5 进程之间的通信#

进程的通信有3种方式

• 共享存储方式
  由操作系统系统存储空间调用方式。
  注意用户进程的空间是互相独立的，不会互相访问。

• 消息传递
  直接通信： 发送到对方的消息队列，从消息队列去
  间接通信： 发信到中间邮箱（非双方进程）， 接收方自己去取。

• 管道通信：
  管道： 链接读写进程之间的共享文件
  功能为互斥、同步
  属于一次性操作， 一旦被读取，数据就被从管道中抛弃
  半双工， 只有1方能操作，要么存入要么写。
  如果要实现双方互动，则需要2个管道。

2.6 linux延申#

linux进程状态解读

linux下的PCB控制块

linux中的进程通信方式