cpu -> 抽象成进程 磁盘 -> 文件 内存 -> 地址空间 面向外面的 -> shell 面向内面的 -> kernel

kernel 组成部分: cpu 调度器 物理内存管理 虚拟内存管理 文件系统管理 中断处理与设备驱动

Kernel 特征: 并发(一段时间内多个程序) 计算机系统同时存在多个运行的程序,需要OS管理和调度 共享 “同时"访问 互斥共享 虚拟 利用多道程序设计技术,让每个用户都觉得有一个计算机专门为他服务

冯诺依曼体系

• 将程序指令和数据一起存储的计算机设计概念结构
• 冯诺依曼瓶颈：CPU 和存储器速率自建的问题无法调和（因为在冯诺依曼体系中，他们是分开的） CPU 经常空转，等待数据传输

现代计算机的结构

将存储器，控制器，运算器合在一起 = cpu 以存储器为核心的计算机结构（冯诺依曼是以运算器为核心的计算机结构）

计算机的层次和编程语言

程序翻译和程序解释

较高级的计算机语言L1 -> 较低级的计算机语言L0 L1 是 L0的输入

硬件逻辑层：

• 门、触发器等逻辑电路组成
• 属于电子工程的领域

微程序机器层：

• 编程语言是微指令集
• 微指令所组成的微程序直接交由硬件执 行

传统机器层：

• 编程语言是CPU指令集
• 编程语言和硬件是直接相关
• 不同架构的CPU使用不同的CPu指令集

一条机器指令 对应 一个微程序 一个微程序 对应 一组微指令

微指令 < 微程序 = 机器指令

汇编语言层

• 编程语言是汇编语言
• 汇编语言可以翻译成可直接执行的机器语言
• 完成翻译的过程的程序就是汇编器

高级语言层

没什么好说的

应用层

程序例如 office word等

计算机的计算单位

容量单位

• 物理层面，高低电平记录信息
• 理论上只认识0/1两种转台
• 0/1能够表示的内容太少了，需要更大的容量表示方法 字节 1byte = 8bits 千字节 kb = 1024b 兆字节 mn = 1024kb 吉字节 1024mb

速度单位

• 网络速度 100M宽带 100M = 100M/s 100M/s = 100Mbps = 100Mbit/s 100Mbit/s = 100/8 MB/s = 12.5M/s
• CPU速度单位
• CPU的时钟频率
• HZ 每秒钟周期性变动重复次数的计量

字符与编码集

ASCII码

• 使用7个bits就可以完全表示ASCII码
• 包含95个可打印字符
• 33个不可打印字符(包括控制字符) 33 + 95 = 128 = 2 **7

但是很多数学符号都无法表示

然后就将 7bits -> 8bits 被称为 Extended ASCII码

字符编码集的国际化

• GB2312 中文编码集 需要
• GBK 向下兼容GB2312，向上支持国际ISO标准
• Unicode：统一码，万国码，单一码
• UTF-8 以字节位单位编码
• 中文windows 系统默认使用GBK编码

计算机组成

计算机的总线与IO设备

计算机的总线

USB = Universal Serial Bus 通用串行总线

总线的概述

总线是什么

• 提供了对外链接的接口
• 不同设备可以通过USB接口进行连接
• 连接的标准，促使外围设备接口的统一 总线是为了解决什么问题 为了解决不同设备的之间的通信问题 总线如何使用 没有IO总线 有了Io总线之后

总线的分类

• 片内总线
• 
  • 芯片内部的总线
  • 寄存器与寄存器之间
  • 寄存器与控制器、运算器之间 高集成度芯片内部的信息传输线
• 系统总线
  • 系统总线
  • 地址总线
  • 控制总线 CPU、主内存、IO设备、各组件之间的信息传输线 一般和CPU位数相同
• 数据总线
  • 双向传输各个部件的数据信息
  • 数据总线的位数（总线宽度）是数据总线的重要参数
• 地址总线
  • 指定源数据或目的数据在内存中的地址
  • 地址总线的位数和存储单元的位数相关 地址总线位数 = n， 寻址范围：0 ~ 2**n
• 控制总线
  • 控制总线是用来发出各种控制信号的传输线
  • 控制信号经由控制总线从一个组件发给另外一个组件
  • 控制总线可以监视不同组件之间的状态（就绪/未就绪） 总线的仲裁
• 为什么需要总线的仲裁？ 假设当主存和硬盘以及IO设备交换数据，且硬盘和IO设备已经都就绪了。这个时候总线应该是给硬盘使用还是给IO设备使用呢？ 这个时候就需要仲裁器，防止设备冲突。 解决不同设备需要使用总线的优先顺序的问题 为了解决总线使用权的冲突问题
• 总线仲裁的办法
  • 链式查询
  • 计时器定时查询
  • 独立请求
• 链式查询
• 
  • 优点：电路复杂度低，仲裁方式简单（串联起来就行了）
  • 坏处：优先级低的设备很难获得总线使用权
  • 坏处：对电路故障敏感（串联电路）
  • 按照链式的顺序判断优先级（如果该设备申请了仲裁的话）
• 计时器定时查询
  • 仲裁控制器对设备编号并使用计数器累积计数
  • 接收到仲裁信号后，往所有设备发出计数值
  • 当技术值与设备编号一致时则获得总线使用权（设备编号越小，优先级越高，如果超出了呢？）
• 独立请求
  • 每个设备均有总线独立连接仲裁器
  • 设备可单独向仲裁器发送请求和接收请求
  • 当同时收到多个请求信号，仲裁器有权按优先级分配使用权
  • 好处：响应速度快，优先顺序可以动态改变
  • 设备连线多，总线控制复杂

计算机的输入/输出设备

常见的输入输出设备

1. 字符输入设备
   • 键盘
2. 图像输入设备
   • 鼠标
   • 数位板
   • 扫描仪
3. 图像输出设备
   • 显示器
   • 打印机
   • 投影仪

输入输出接口的通用设计

1. 向设备发送数据
2. 读取设备中的数据
3. 判断设备是否被占用
4. 设备是否已经连接
5. 设备是否已经启动 所以通用设计

• 数据线
  • 是IO设备与主机之间进行数据交换的传送线
  • 单向传输数据线
  • 双向传输数据线
• 状态线
  • IO设备状态向主机报告的信号线
  • 查询设备是否已经正常连接并就绪
  • 查询设备是否已经被占用（其他进程）
• 命令线
  • CPU向设备发送命令的信号线
  • 发送读写信号
  • 发送启动停止信号
• 设备选择线
  • 主机选择IO设备进行操作的信号线
  • 对连在总线上的设备进行选择

CPU与IO设备的通信

1. 程序中断
   • 当外围IO设备就绪的时候，向CPU发出中断信号
   • CPU有专门的电路响应中断信号（收到信号之后就会停止当前的工作（记录工作状态），先去执行外围IO设备的 那份工作） 提供低速设备通知CPU的一种异步的方式 CPU可以高速运转同时兼顾低速设备的响应
2. DMA（直接存储器访问）
   • DMA直接连接主存与IO设备
   • DMA工作的时候不需要CPU的参与
   • 硬盘、外置显卡都有DMA设备
   • 当主存和IO设备交换信息的时候，不需要中断CPU（提高CPU的效率）

这原因就是因为 CPU速度和IO设备速度不一致导致的 DMA是个硬件设备

计算机的存储器

计算机的存储器概览

存储器分类

• 按存储介质
  • 半导体存储器（内存，u盘，固态硬盘）
  • 磁存储器（磁盘，磁带）
• 按存取方式分类
  • 随机存储器（RAM随机读取，与位置无关）
  • 串行存储器（与位置有关，按顺序查找）
  • 只读存储器（ROm）

存储器的层次结构

• 缓存-主存层次
  • 缓存 （CPU的缓存和寄存器）主存辅存
  • 原理： 局部性原理
  • 实现：在CPU和主存之间增加一层速度快（容量小）的Cache
  • 目的：解决主存速度不足的问题 局部性原理： 是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中（这个统计得到的吧）
• 主存-辅存层次
  • 原理：局部性原理
  • 实现：主存之外增加辅助存储器（磁盘、SD、U盘）
  • 目的：解决主存容量不足的问题

计算机的高速存储器

高速缓存的工作原理

• 字：是指存放在一个存储单元中的二进制代码组合
• 字块：存储在连续的存储单元中而被看做是一个单元的一组字 主存寻址过程
• 字的地址包含两个部分
• 前m位指定字块的地址
• 后b位指定字在字块中的地址 命中率 访问效率 平均访问时间

为了保证高命中率和高访问效率，我们需要良好的缓存替换策略

高速缓存的替换策略

• 高速缓存的替换时机：
  • 当CPU需要的数据不在高速缓存中，需要从主存加载所需数据时（即未命中时） ，这个时候就应该把主存中的数据替换到高速缓存中去。 四种替换策略（淘汰策略）
• 随机算法
• 先进先出算法（FIFO）：
  • 把高速缓存看做是一个先进先出的队列
  • 优先替换最先进入队列的字块
• 最不经常使用算法（LFU）
  • 优先淘汰最不经常使用的字块
  • 需要额外的空间记录字块的使用频率
• 最近最少使用算法（LRU）
  • 优先淘汰一段时间内没有使用的字块
  • 有多种实现方法，一般使用双向链表
  • 把当前访问节点置于链表前面（保证链表头部节点是最近使用过的）

计算机的主存储器与辅助存储器

主存储器

辅助存储器

磁盘 盘面的平面图

• 表面是可磁化的硬磁特性材料
• 移动磁头径向运动读取磁道信息

调度算法

1. 先来先服务算法 ： 按顺序访问进程的磁道读写需求
2. 最短寻道时间优先
3. 扫描算法(电梯算法)：
   • 每次只往一个方向移动
   • 每次移动到末尾反向
4. 循环扫描算法
   • 读取只能往一个方向读取

计算机的CPU

计算机的指令系统

机器指令的形式

• 机器指令由两部分组成， 操作码字段 + 地址码字段

• 操作码指明指令所要完成的操作

• 操作码的位数反应了机器的操作种类

• 地址码给出操作数或者操作数的地址

• 根据地址码的不同分类

  • 三地址指令 (addr1)OP(addr2) -> (addr3) 结果放在addr3里面
  • 二地址指令
  • 一地址指令
  1. 自己对自己的操作
  2. 一个操作数做默认的行为例如 ++ 其实还存在零地址指令
  • 在机器指令中无地址码
  • 空操作、停机操作、中断返回

机器指令的操作类型

• 数据传输类型
  • 寄存器之间、寄存器于存储单元、存储单元之间传送
  • 数据读写、交换地址数据、清零置一等操作
• 算数逻辑操作
  • 操作数之间加减乘除运算
  • 操作数的与或非等逻辑位运算
• 移位操作类型
  • 数据左移、数据右移
  • 完成数据在算数逻辑单元的必要操作
• 控制指令
  • 等待指令、停机指令、空操作指令、中断指令。

机器指令的寻址方式

• 指令寻址
  • 顺序寻址
  • 跳跃寻址
• 数据寻址
  • 立即寻址
  • 直接寻址
  • 间接寻址
  • 综合对比

计算机的运算器

运算器是用来进行数据运算加工的

数据缓冲器

• 分为输入/输出缓冲
• 输入缓冲暂时存放外设送过来的数据
• 输出缓冲暂时存放送往外设的数据

ALU 算数逻辑单元

• 运算器的主要组成
• 常见的位运算
• 算术运算

状态字寄存器

• 存放运算状态（条件码、进位、溢出、结果正负等）
• 存放运算控制信息（调试跟踪标记位、允许中断位）

通用寄存器

和控制器的差不多

• 可保存ALU运算中间结果
• 用域暂时存放或传送数据或指令
• 容量比一般的专用寄存器大

计算机的控制器

控制器是用来协作和控制计算机运行的

程序计数器

• 程序计数器用来存储下一条指令的地址
• 循环从程序计数器中拿出指令
• 当指令被拿出时，指向下一条指令

时序发生器

• 电气工程领域，用于发送时序脉冲
• CPU依据不同的时序脉冲有节奏的进行工作

指令译码器

• 指令译码器时控制器的主要部件之一
• 计算机指令由操作码和地址码组成
• 翻译操作码对应的操作以及控制传输地址对应的数据

指令寄存器

• 指令寄存器也是控制器的主要部件之一
• 从主存或高速缓存取计算机指令

主存地址寄存器

• 保存当前CPU正要访问的内存单元的地址

主存数据寄存器

• 保存CPU正要读或写的主存数据

通用寄存器

• 用于存放或传送数据或指令
• 可保存ALU的运算中间结果
• 容量比一般的寄存器要大

指令执行过程

1. 取指令
2. 分析指令
3. 执行指令
4. 程序计数器 缓存101指令（这个时候，程序计数器只知道这个指令的地址，不知道指令的内容）
5. 通过总线将指令101内容拿出来
6. 通过片内总线，指令寄存器将缓存指令内容（操作码，地址码）但是指令寄存器依然不知道指令的意义。
7. 指令寄存器将指令内容发送到指令译码器（片内总线
8. 指令译码器进行译码，发出控制信号通过片内总线来到运算器里面
9. 将R0数据加载到ALU里面去，然后送到数据总线，再由数据总线送到数据缓存器。
10. 数据缓存器再将数据发送到寄存器中。 取指令由控制器工作 执行指令由运算器工作 因此CPU的综合利用率并不高

CPU的流水线设计

就是因为CPU的综合利用率不高，我们想出了CPU的流水线设计。（上面那种时串行）

• 类似工厂的装配线
• 工厂的装配线使得多个产品可以同时被加工
• 在同一个时刻，不同产品均位于不同的加工阶段

流水线的效率是串行的三倍

进制

为什么需要补码？

因为0 在原码中有两种表示

1. 希望使用正数代表负数的方法

2. 使用加法操作代替减法的操作（没有实现）

反码就是为了实现2做到的

反码的目的是找出原码和补码之间的规律，消除转换过程中的减法

对负数而言 补码= 反码 - 1（直接-1，不考虑符号位）实质上是 反码 + 1 （因为是负数）

对负数而言 反码 = 原码 按位置取反（除符号位以外）

定点数和浮点数

定点数的表示方法

• 小数点固定在某个位置的数，称之为定点数 如果既不是纯小数，也不是纯整数 这个时候就需要乘以比例因子以满足定点数保存格式 下面这种就不需要写出小数点 如果不是纯小数和纯整数，我们乘以比例因子转化为纯小数/纯整数

浮点数的表示方法

为什么已经有了定点数还需要浮点数？

• 计算机处理的很大程度上不是纯小数或者纯整数
• 数据范围很大，定点数很难以表达

浮点数的表示格式

• 尾数（必须使用纯小数,需要时8位）
• 阶码
• 基码

浮点数的表示范围

假设阶码数值取m位，尾数数值取n位 N = S * rj 阶码表示的最大值 2 m -1 [-(2m -1), 2m -1] 尾数表示的最大值 1- 2**（-n） 尾数表示的最小值 2**(-n) [2**(-n), 1- 2**(0n)] 考虑正负 负数的表示范围[-(1-2**(-n)), -(2**(-n))] 正数的表示范围[2**(-n), 1- 2**(-n)] 表示的最大范围 单精度浮点数：使用4字节、32位来表达浮点数（float） 双精度浮点数：使用8字节 double

浮点数的规格化

定点数的加减法

整数 数值位和符号位一同运算，并将符号位产生的进位自然丢掉

浮点数的加减法

对阶

操作系统篇

操作系统的演变

无操作系统

• 人工操作
• 用户独占
• CPU等待人工操作
• 资源利用率很低

批处理系统

• 无需等待人工操作
• 批量输入任务
• 资源利用率提升
• 多道程序设计

分时系统

• 人机交互
• 多用户共享
• 及时调试程序
• 资源利用率提升

多道程序设计

• 早期批处理系统只能一次处理一个任务
• 多道程序设计使得批处理系统可以一次处理多个任务

什么是多道程序设计

• 多道程序设计是指在计算机内存中同时存放多个程序
• 多道程序在计算机的管理程序之下相互穿插运行

对多道程序的管理是操作系统的重要功能 共五大管理功能

1. 进程管理
2. 存储管理
3. 作业管理
4. 文件管理
5. 设备管理

操作系统概览

什么是操作系统

• 操作系统是管理计算机硬件和软件资源的计算机程序（它也是软件）
• 管理配置内存、决定资源供需顺序、控制输入输出设备等
• 操作系统提供让用户和系统交互的操作界面

为什么需要操作系统

• 我们不可能直接操作计算机硬件
• 设备种类繁多复杂，需要统一界面
• 操作系统的简易性是的更多人能够使用计算机

操作系统的基本功能

• 资源管理
  • 处理器资源
  • IO设备资源
  • 存储器资源
  • 文件资源 操作系统统一管理着资源
• 抽象
  • 用户无需面向硬件接口编程
  • IO设备管理软件，提供读写接口
  • 文件管理软件，提供文件接口 操作系统实现了对计算机资源的抽象
• 用户和计算机之间的接口
  • 图像窗口
  • 命令形式
  • 系统调用形式 操作系统提供了用户与计算机之间的接口

操作系统的相关概念

• 并发性 与并行对比 并行指的是 同一个时刻 并发是指 在同一个时间间隔
• 共享性
  • 共享性表现为操作系统中的资源可供多个并发程序共同使用
  • 这种共同使用的形式称之为资源共享
  • 互斥共享和同时访问
  • 什么是互斥共享
    • 当资源被程序A占用时，其他想使用的话只能等待
    • 只有进程A使用完以后，其他进程才可以使用该资源
    • 例如 打印机
  • 什么是同时访问
    • 某种资源在一段时间内并发地被多个程序访问
    • 这种“同时”是宏观的，从宏观去看该资源是可以被同时访问的（例如访问硬盘，速度很快可以当做同时）
• 虚拟性
  • 虚拟性表现为把一个物理实体转变为若干个逻辑实体
  • 物理实体是真实存在的，逻辑实体是虚拟的。
  • 虚拟的技术主要有时分复用技术和空分复用技术
  • 什么是时分复用技术
    • 资源在时间上进行复用，不同程序并发使用
    • 多道程序分时使用计算机的硬件资源
    • 提高资源的利用率
    • 虚拟处理器技术
      • 借助多道程序设计技术
      • 为每个程序建立进程
      • 多个程序分时复用处理器
    • 虚拟设备技术
      • 物理设备虚拟为多个逻辑设备
      • 每个程序占用一个逻辑设备
      • 多个程序通过逻辑设备并发访问
  • 什么是空分复用技术
    • 用来实现虚拟磁盘、虚拟内存等
    • 提高资源的利用率、编程效率
    • 虚拟磁盘技术
      • 物理磁盘虚拟为逻辑磁盘
      • C、D、E等逻辑盘
      • 使用起来更加安全、方便
    • 虚拟内存技术
      • 在逻辑上扩大程序的存储容量
      • 使用比实际内存更大的容量
      • 大大提升编程效率
• 异步性
  • 在多道程序环境下，允许多个进程并发执行
  • 进程在使用资源时可能需要等待或放弃
  • 进程的执行并不是一气呵成的，而是以走走停停的形式推进的 程序以不可预知的速度向前推进

进程

进程管理之进程实体

为什么需要进程

在没有配置os之前，资源属于当前的程序 一个程序一个程序的运行，且资源只属于一个程序 配置os之后，引入多道程序设计的概念 合理的隔离资源、运行环境、提升资源利用率

1. 进程是系统资源分配和调度的基本单位
2. 进程作为程序独立运行的载体，保障程序正常执行。
3. 进程的存在使得操作系统资源的利用率大幅提升 多道程序设计很重要

进程实体

主存中的进程形态

在主存中，进程也是一块连续的内存空间，这块空间就被称为进程控制块 进程控制块

• 包含 标识符、状态、优先级、程序计数器、内存指针、上下文数据、IO状态信息、记账信息
• 标识符：标识符唯一标记一个进程，用于区别其他进程
• 状态：标记进程的状态，如：运行态
• 程序计数器：进程即将被执行的下一条地址
• 内存指针：程序代码、进程数据相关指针
• 上下文数据：进程执行时处理器存储的数据
• IO状态信息：被进程IO操作所占用的文件列表
• 记账信息：使用处理器时间、时钟树总和。 总结：

1. 进程标识符
2. 处理机状态
3. 进程调度信息
4. 进程控制信息 进程控制块（PCB）:

• 用于描述和控制进程运行的通用数据结构
• 记录进程当前状态和控制进程运行的全部信息
• PCB使得进程是能够独立运行的基本单位

进程与线程

一个进程可以有一个/多个线程

• 线程是操作系统进行运行调度的最小单位（进程是系统资源分配和调度的基本单位）
• 包含在进程之中，是进程中实际运行工作的单位
• 一个进程可以并发多个线程，每个线程执行不同的任务 进程的线程共享进程资源

进程管理之五状态模型

1. 就绪
   • 当进程被分配到除CPU以外的所有必要的资源后
   • 只要再获得CPU的使用权，就可以立即运行
   • 其他资源都准备好、只差CPU资源的状态为就绪状态

• 在一个系统中多个处于就绪状态的进程通常排成一个队列– 就绪队列

2. 执行

• 进程获得CPU，其程序正在执行成为执行装填
• 单处理机，任意时刻只能有一个进程处于执行状态

3. 阻塞

• 进程因某种原因：其他设备未就绪而无法继续执行
• 从而放弃CPU的状态成为阻塞状态
• 操作系统也会将处于阻塞状态的进程排成一个队列–阻塞队列

4. 创建

• 分配PCB -> 插入就绪队列
• 创建进程时拥有PCB但其他资源尚未就绪的状态称为创建状态
• 操作系统提供fork函数接口创建进程

5. 终止

• 系统清理 -> PCB归还
• 进程结束由系统清理或者归还PCB的状态称为终止状态

进程管理之进程同步

为什么需要进程间同步

生产者消费者问题

• 生产者生产一个产品 就往缓冲区 +1
• 消费者拿走一个产品 就往缓冲区 -1 这些操作在现实生活中没有问题。 但是在计算机的角度就有问题了。
• 缓冲是在Cache上的
• 操作缓冲需要三个步骤
  1. register(生产者/消费者的寄存器) =count
  2. register = register + 1
  3. count = register
• 单从生产者程序或消费者程序去看没有问题
• 但是两者并发执行时就可能出差错 这里count 就是临界资源 哲学家进餐问题 在这个例子里，筷子是临界资源，哲学家是进程 根源问题：
• 彼此之间没有通信
• 如果生产者通知消费者我已经完成一件生产
• 哲学家向旁边哲学家说我要进餐了 所以需要进程间的同步 进程间的同步解决对竞争资源在多进程间进行使用次序的协调 临界资源：
• 临界资源指的是一些虽作为共享资源却又无法同时被多个线程共同访问的共享资源。当有进程在使用临界资源时，其他进程必须依据操作系统的同步机制等待占用进程释放该共享资源才可重新竞争使用共享资源。

进程间同步的原则

• 空闲让进：资源无占用，允许使用
• 忙则等待：资源由占用，请求进程等待
• 有限等待：保证有限等待时间能够使用资源
• 让权等待：等待时，进程需要让出CPU(保证CPU的高效率运行)

进程同步的方法

• 消息队列
• 共享存储
• 信号量

线程同步

线程也可能会抢占 进程的共享资源

线程同步的方法：

• 互斥量
• 读写锁
• 自旋锁
• 条件变量

Linux 进程管理

Linux 进程的相关概念

linux 进程类型

1. 前台进程

• 前台进程就是具有终端，可以和用户交互的进程

2. 后台进程

• 没有占用终端的就是后台进程
• 后台程序基本不和用户交互，优先级比前台进程低
• 将需要执行的命令以‘&’符号结束

3. 守护进程

• 守护进程（daemon）是特殊的后台进程
• 很多守护进程在系统引导的时候启动，一直运行到系统关闭（就是windows的服务） 例如 crond（定时任务）, httpd, sshd，mysqld 一般以’d’结尾的进程都是守护进程

进程的标记

1. 进程ID
   • 进程ID是进程唯一标记，每个进程拥有不同的ID
   • 进程ID表现为一个非负整数，最大值由操作系统限定
   • 在linux中 父子进程的关系可以通过 pstree 命令查看
   • ID为0的进程为idle进程，是系统创建的第一个进程
   • ID为1的进程是init进程，是0号进程的子进程，完成系统初始化
2. 状态符号
   • R: (TASK_RUNNING),进程正处于运行状态
   • S: (TASK_INTERRUPTIBLE),进程正处于睡眠状态
   • D: (TASK_UNINTERRUPTIBLE),进程正在处于IO等待的睡眠状态
   • T: (TASK_STOPPED),进程正处于暂停状态
   • Z: (TASK_DEAD OR EXIT_ZOMBIE),进程正处于退出状态，或僵尸进程

操作Linux进程的相关命令

• ps

  • ps -aux 打印进程详细信息
  • ps -u root 查看用户root的进程
  • ps -ef –forest 查看进程树
  • ps -aux –sort=-pcpu 按照cpu使用情况排序查看进程
  • ps -aux –sort=-pmem 按照内存使用情况排序查看进程

• top

  • 查看进程的所有状态 有pr 优先级 virt 进程的虚拟内存等这些字段

• kill

  • 给进程发送信号
  • kill -9 51015 给51015进程发送9信号，9 信号代表无条件停止下来（除了9信号，其他信号进程有权忽略）
  • kill -l 查看操作系统支持的信号

作业管理之进程调度

什么是进程的调度

进程调度是指计算机通过决策决定哪个就绪进程可以获得CPU使用权（前提也是多道程序设计）

• 保留旧进程的运行信息，请出旧进程（收拾包袱）
• 选择新进程，准备运行环境并分配CPU（新进驻） 为了理解进程的调度，还需要了解三种机制

1. 就绪队列的排队机制

• 将就绪进程按照一定的方式排成队列，一边调度程序可以最快找到就绪进程

2. 选择运行进程的委派机制

• 调度程序以一定的策略选择就绪进程，将CPU资源分配给它

3. 新老进程的上下文切换机制

• 保存当前进程的上下文信息，装入被委派执行进程的运行上下文（首先将老进程的上下文从高速缓存移动到主存，然后装入新进程的上下文）
  • 如果调度的时候老进程没有执行完该怎么办？
  • 按照老进程是否执行完可以分为两类

1. 非抢占式的调度
   • 处理器一旦分配给某个进程，就让该进程一直使用下去
   • 调度程序不以任何原因抢占正在被使用的处理器
   • 直到进程完成工作或因为IO阻塞才会让出处理器
2. 抢占式调度
   • 允许调度程序以一定的策略暂停当前运行的进程
   • 保存好旧进程的上下文信息，分配处理器给新进程

进程调度算法

• 先来先服务调度算法 在就绪队列里面，按照先来先执行的顺序
• 短进程优先调度算法
  • 调度程序优先选择就绪队列中估计运行时间最短的进程
  • 不利于厂作业进程的执行
• 高优先权优先调度算法
  • 进程附带优先权，调度程序优先选择权重的进程
  • 高优先权优先调度算法使得紧迫的任务可以优先处理
• 时间片轮转调度算法
  • 按照先来先服务的原则排列就绪队列
  • 每次从队列头部取出待执行进程，分配一个时间片执行
  • 公平，但是不能保证及时响应用户

作业管理

作业管理之死锁

死锁的产生原因

• 竞争资源

  • 共享资源数量不满足各个进程需求
  • 进程调度顺序不当

• 死锁的四个必要条件

  • 互斥条件：
    • 进程对资源的使用是排他性的使用
    • 某资源只能由一个进程使用，其他进程需要使用只能等待
  • 请求保持条件
    • 进程至少保持一个资源，又提出新的资源请求
    • 新资源被占用，请求被阻塞
    • 被阻塞的进程不释放自己保持的资源
  • 不可剥夺条件
    • 进程获得资源在未完成使用前不能剥夺
    • 资源只能由进程本身释放
  • 环路等待条件
    • 发生死锁时，必然存在进程-资源环形链

预防死锁的方法

• 破坏请求保持条件
  • 系统规定进程运行之前，一次性申请所有需要的资源
• 破坏不可剥夺条件
  • 当一个进程请求新的资源得不到满足时，必须释放占有的资源
  • 进程运行时占有的资源可以被释放，意味着可以被剥夺
• 破坏环路等待条件
  • 可用资源线性排序，申请必须按照需要递增申请
  • 线性申请不再形成环路，从而破坏了环路等待条件

银行家算法

1. 客户申请的贷款是有限的，每次申请需声明最大资金量
2. 银行家在能够满足贷款时，都应该给用户贷款
3. 客户在使用贷款后，能够及时归还贷款

存储管理

存储管理之内存分配与回收 （物理内存角度）

早期计算机编程并不需要过多的存储管理 随着计算机和程序越来越复杂，存储管理成为必要

• 确保计算机有足够的内存处理数据
• 确保程序可以从可用内存中获取一部分内存使用

内存分配的过程

单一连续分配

• 单一连续分配是最简单的内存分配方式
• 只能在单用户、单进程的操作系统中使用

固定分区分配

• 固定分区分配是支持多道程序的最简单存储分配方式
• 内存空间被划分为若干固定大小的区域
• 每个分区只提供一个程序使用，互不干扰

动态分配分配

• 根据进程实际需要，动态分配内存空间
• 相关数据结构、分配算法 动态分区空闲表数据结构

动态分区空闲链数据结构 使用双链表把空闲节点连接起来，连续的空闲节点可以直接合并起来

动态分区分配算法

首次适应算法（FF）

• 分配内存时从开始顺序查找合适内存区
• 若没有合适的空闲区，则分配失败
• 每次都从头部开始，使得头部地址空间不断划分（只要前面找到了，就不会去后面。大概率都是在前面的地址空间内划分，到最后很多碎片，每次都要遍历到最后）
• 改进方向，从上次检索位置开始查找适合内存区（循环适应算法）

最佳适应算法(BF)

• 最佳适应算法要求空闲区链表按照容量大小排序
• 遍历空闲区链表找到最佳合适空闲区（>= 容量i）

快速适应算法（QF）

• 快速适应算法要求有多个空闲区链表
• 每个空闲区链表存储一种容量的空闲区 感觉很像桶排序的思想啊。

内存回收的过程

2种情况（细分4种）

1. 需要回收的区域和空闲区连在一起的
   1. 回收区在空闲区后面
      • 不需要新建空闲链表节点
      • 只需要把空闲区1的容量增大为包括回收区的空闲区容量即可
   2. 回收区在空闲区前面
      • 将回收区和空闲区合并
      • 新的空闲区使用回收区的地址
   3. 回收区在两块空闲区中间
      • 将空闲区1、空闲区2和回收区合并
      • 新的空闲区使用空闲区1的地址
2. 需要回收的区域和空闲区无连接
   1. 回收区单一，没有连接任何空闲区
      • 为回收区创建新的空闲节点
      • 插入到相应的空闲区链表中去

存储管理之段页式存储管理（操作系统角度，进程角度）

操作系统是如何管理进程的空间的

页式存储管理

• 将进程逻辑空间等分成若干大小的页面
• 相应的把物理内存空间分成与页面大小的一样的物理块
• 以页面为单位把进程空间装进物理内存中分散的物理块
  • 页面大小应该适中，过大难以分配，过小都是碎片
  • 页面大小通常是512B- 8K

页表

页表负责记录进程逻辑空间和物理空间的映射（要不然找不到啊） 多级页表可以解决这个问题 页式存储的缺点 有一段连续的逻辑分布在多个页面中，将大大降低执行效率

什么是内存碎片呢？

段式存储管理

• 将进程逻辑空间划分成若干段
• 段的长度由连续逻辑的长度决定
• 主函数MAIN、子程序段X、子函数Y等

共同点和区别

段式存储和页式存储都离散地管理了进程的逻辑空间

• 页是物理单位，段式逻辑单位
• 分页是为了合理利用空间，分段是满足用户要求
• 页大小由硬件固定，段长度可动态变化
• 页表信息是一维的，段表信息是二维的

段页式存储管理

首先来看看分页和分段的好处

• 分页可以有效提高内存利用率（虽然存在页内碎片）
• 分段可以更好的满足用户需求
• 两者结合，形成段页式存储管理 段页式存储管理的方法

1. 现将逻辑空间按段式管理分成若干段
2. 再把段内空间按页式管理等分成若干页

存储管理之虚拟内存

• 有些进程实际需要的内存很大，超过物理内存的容量
• 多道程序设计，使得每个进程可用物理内存更加稀缺

虚拟内存概述

• 虚拟内存时操作系统内存管理的关键技术
• 使得多道程序运行和大程序运行成为现实
• 把程序使用内存划分，将部分暂时不适用的内存放置在辅存

程序的局部性原理

局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。

• 根据这个原理，不需将所有数据都装入内存，装入部分即可，其余的可以放在辅存
• 如果访问页不在内存，则发出缺页中断，发起页面置换（页面置换速度慢）
• 从用户层面看，程序拥有很大的空间，即是虚拟内存

虚拟内存的置换算法（其实就是缓存淘汰的算法，和它的原因相同，总把热数据置换到主存里面。）

• 先进先出算法（FIFO）
• 最不经常使用算法（LFU）
• 最近最少使用算法（LRU）
• 替换策略发生在Cache-主存层次、主存-辅存层次
• Cache-主存层次的替换策略主要是为了解决速度问题
• 主存-辅存层次主要是为了解决容量问题

Linux的存储管理

Buddy内存管理算法

• Buddy算法是经典的内存管理算法
• 算法基于计算机处理二进制的优劣具有极高的效率
• 算法主要是为了解决内存外碎片的问题

  • 什么是页内碎片 内部碎片是已经被分配出去（能明确指出属于哪个进程)的内存空间大于请求所需的内存空间，不能被利用的内存空间就是内部碎片。

  • 什么是页外碎片 外部碎片是指还没有分配出去(不属于任何进程)，但是由于大小而无法分配给申请内存空间的新进程的内存空闲块。

Buddy内存管理算法方法

1. 向上取整为2的幂大小(如果进程申请78k，将分配128k)
2. 伙伴系统
   • 伙伴是指内存的伙伴
   • 一片连续内存的伙伴时相邻的另一片大小一样的连续内存 也是段页式存储结构

• 先分配，后回收 分配 回收
• 算法基于计算机处理二进制的优势（就像二分查找）具有极高的效率
• 算法主要是为了解决内存外碎片的问题 实质上 内存外碎片 -> 内存内碎片问题（例如上面的进程需要78kb 分配了 128kb 变成了片内碎片）

Linux交换空间（swap）

• 冷启动内存管理（不怎么使用的空间放在swap里）
• 系统睡眠依赖
• 大进程空间依赖

交换空间和虚拟内存的关系

Swap空间

• Swap 空间存在于磁盘
• Swap空间与主存发生置换
• Swap空间是操作系统概念
• Swap空间解决系统物理内存不足问题 虚拟内存
• 虚拟内存存在于磁盘
• 虚拟内存与主存发生置换
• 虚拟内存是进程的概念
• 虚拟内存解决进程物理内存不足问题

文件管理

操作系统的文件文理

文件的逻辑结构

逻辑结构的文件类型

• 有结构文件
  • 文本文件、文档、媒体文件
  • 文件内容由定长记录和可变长记录组成
  • 定长记录存储文件格式、文件描述等结构化数据项
  • 可变长记录存储文件具体内容
• 无结构文件
  • 二进制文件、链接库
  • 也称为流式文件
  • 文件内容长度以字节为单位
  • 例如exe dll so

顺序文件

• 按照顺序存放在存储介质中的文件
• 磁带的存储特性使得磁带文件只能存储顺序文件
• 顺序文件是所有逻辑文件当中存储效率最高的
• 增删查改慢（就像顺序读写结构和随机）

索引文件

就是为了解决顺序文件的增删改慢

• 可变长文件不适合使用顺序文件格式存储
• 索引文件是为了解决可变长文件存储发明的一种文件格式
• 索引文件需要配合索引表完成存储结构

辅存的存储空间分配

辅存的分配方式

连续分配

• 顺序读取文件内容非常容易，速度快
• 对存储要求高，要求满足容量的连续空间

链接分配

• 链接分配可以将文件存储在离散的盘块中
• 又可分为显式链接和隐式链接
  • 显式链接
  • 隐式链接
    • 隐式分配的下一个链接指向存储在当前盘块
    • 顺序访问块，随机访问慢（其实就是顺序存储和非顺序存储的区别）
    • FAT表（FAT文件系统，File Allocation Table）
    • 不支持高效的直接存储
    • 检索时FAT表占用较大的存储空间（需要将整个FAT表加载到内存）

索引分配

• 把文件的所有盘块集中存储（索引）
• 读取某个文件时，将文件索引读取仅内存即可
• 每个文件拥有一个索引快，记录所有盘块信息
• 索引分配方式支持直接访问盘块
• 文件较大时，索引分配方式具有明显优势

辅存的存储空间分配

空闲表

空闲链表

位示图（新的和主存不一样的地方了）

• 维护成本低
• 容易找到空闲盘块
• 使用0/1比特，占用空间小

目录管理

目录树

Linux文件基本操作

Linux文件类型

• 套接字（s）、普通文件（-）、目录文件（d）、符号链接（l表示）、设备文件（c表示字符设备文件，b表示块设备文件）、FIFO（p）

Linux文件系统

• FAT
• NTFS
• EXT2/3/4

EXT文件系统（索引分配）

• Boot Sector：启动山区，安装开机管理程序
• Block Group：块组，存储数据的实际位置

Inode Table

• 存放文件Inode 的地方
• 每一个文件（目录）都有一个Inode
• 每一个文件（目录）的索引节点（所以是索引分配的方式） Inode
• 保存了文件类型、文件权限、文件的物理地址、文件长度、文件连接计数、文件存取时间、文件状态、访问计数、链接指针…
• 文件名不是存放在Inode节点上的，而是存放在目录的Inode节点
• 列出目录文件的时候无需加载文件的Inode（为了方便）

Inode bitmap

• Inode的位示图
• 记录已分配的Inode和未分配的Inode

Data block

• Data block 是存放文件内容的地方
• 每个block 都有唯一的编号
• 文件的blcok记录在文件的Inode上

Block bitmap

• 记录data block的使用猖狂

Superblcok

• 记录整个文件系统相关信息的地方
• Block和Inode的使用情况
• 时间信息、控制信息等

df -T 查看磁盘挂载信息 dump2fs /dev/sda2 输出磁盘信息

设备管理

操作系统的设备管理

什么是广义的IO设备

对CPU而言，凡是对CPU进行数据输入的都是输入设备 对CPU而言，凡是CPU进行数据输出的都是输出设备

• 按特性分类
• 按信息交换的单位分类
• 按设备的共享属性分类
• 按传输的速率分类

IO设备的缓冲区

上面因为CPU和IO设备的速率不匹配，所以我们采用了层次结构 同样IO设备的缓冲区也是为了解决这个问题

• 减少CPU处理IO请求的频率
• 提高CPU和IO设备的之间的并行性
• 专用缓冲区只适用于特定的IO进程
• 当这样的IO进程比较多时，对内存的消耗也很大
• 操作系统划出可供多个进程使用的公共缓冲区，称之为缓冲池

SPOOLing技术（重点， 虚拟设备技术）

• 关于慢速字符设备何如和计算机主机交换信息的一种技术
• 利用高速共享设备将低速的独享设备模拟为高速的共享设备（虚拟设备技术）
• 逻辑上，系统为每一个用户都分配了一台独立的高速独享设备

把同步调度变成了异步调度

• 在输入、输出之间增加了排队转储环节(输入井、输出井)
• SPOOLing负责输入(出)井与低速设备之间的调度
• 逻辑上，进程直接与高速设备交互，减少 了进程的等待时间