第三章.操作系统基本原理

(ps:本人的学习记录，用于上下班途中背诵记忆的，若有侵权联系我删除)

3.1操作系统概述

• 操作系统的作用
  • 通过资源管理提高计算机系统的效率
  • 改善人机界面向用户提供友好的工作环境
• 操作系统的特征
  • 并发性
  • 共享性
  • 虚拟性
  • 不确定性
• 操作系统的功能
  • 进程管理
  • 存储管理
  • 文件管理
  • 设备管理
  • 作业管理
• 操作系统的分类
  • 批处理操作系统
  • 分时操作系统：轮流使用CPU工作片
  • 实时操作系统：快速响应
  • 络操作系统
  • 分布式操作系统：物理分散的计算机互联系统
  • 嵌入式操作系统
  • 微内核操作系统
• 计算机启动的基本流程：BIOS->主引导记录->操作系统

3.2进程管理

• 进程的组成
  • 进程控制块PCB：进程的唯一标志
  • 程序：描述进程要做什么
  • 数据：存放进程执行时所需的数据

3.2.1进程的状态

1、三态模型

分别为运行态、活跃就绪态、活跃阻塞态、静止就绪态、静止阻塞态，相较于三态模型，增加了静止就绪态、静止阻塞态

• 状态描述：
  • 静止就绪态：被挂起的进程原本处于就绪状态
  • 静止阻塞态：被挂起的进程原本处于阻塞状态
  • 上面两种状态都不可能被调度而执行，人为干预后，进程将被挂起，进入静止状态，此时需要认为激活才能恢复到活跃状态，之后的本质还是三态模型

3.2.2前趋图

前趋图是一个由节点和有向边构成的一个有向无循环图，通常用于表现事务之间先后顺序的制约关系。图中的每个节点可以表示一个语句、一个程序端或一个进程，节点间的有向边表示两个节点间存在前趋关系。例：

• P代表进程，R代表资源，R方框中有几个圆球就表示有几个这种资源，在图中，R1指向P1，表示R1有一个资源已经分配给了P1，P1指向R2，表示P1还需要请求一个R2资源才能执行
• 阻塞节点：某进程锁请求的资源已经全部分配完毕，无法获取所需资源，该进程被阻塞了无法继续。如上图中的P2
• 非阻塞节点：某进程所请求的资源还有剩余，可以分配给该进程继续运行。如上图中的P1、P3
• 当一个进程资源图中所有进程都是阻塞节点时，即陷入死锁状态。

2、同步与互斥

• 同步：在异步环境下一组并发进程因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度进行执行的过程
• 互斥：在同一时刻，只允许某一个进程去使用某一个资源
• 互斥是资源的竞争关系，同步是进程间的协作关系

3.2.4PV操作

1、相关概念

• 临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等
• 临界区：每个进程中访问临界资源的那段代码
• 信 量：一种特殊的变量，例如P(S)、V(S)中的S就是信 量
• PV操作：是两大原子操作的组合

2、PV操作

• PV操作：P(S)和V(S)是相反的操作
  • P操作：申请资源，S=S-1，若S
  • V操作：释放资源，S=S+1，若S

如下图所示：

P(S₁)和V(S₁)、P(S₂)和V(S₂)是一对PV操作

• 若没有PV操作，则最初生产者生产产品后，往缓冲区送入，若消费者进程还没有运行，生产者进程继续运行，则缓冲区已满，无法将产品放入，会产生溢出错误，所以需要在其中加上PV操作。
• 若加上PV 操作后，设置S₁（缓冲区空闲个数）初始值为1，S₂（商品数量）初始值为0，首先执行生产者进程，生产一个产品后，执行P(S₁)，S₁=0，产品送入缓冲区后执行V(sS₂)，S₂=1；若此时消费者进程不执行，再次执行生产者进程，S₁=-1，S₁

3、PV操作与前趋图

使用PV原语描述将前趋图表示出来，将依赖关系找出来，并且使用PV操作描述，如下图示例所示：

在V(S₂)后仍然优先执行完P2

3.2.5死锁问题

进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题，如果一个进程在等待一件不可能发生的事，则进程就思索了。而如果一个或多个进程产生死锁，就会造成系统死锁。

死锁问题通常考察两个点

• 给定资源判断什么情况不可能发生死锁
• 银行家算法

1、资源计算

• 例：系统有3个进程：A、B、C，这3个进程都需要5个系统资源，系统至少有多少个资源，则不可能发生死锁：
• 解答：（5-1）*3+1=13个
• 计算公式：
  • 不发生死锁的最小资源数：（每个进程所需要的资源-1）的总和+1
  • 发生死锁的最大资源数：（每个进程所需要的资源-1）的总和

2、产生死锁的四大条件

• 互斥：使用资源互斥
• 保持和等待：各个进程会保持自己的资源，并等待别人释放更多的资源给自己使用
• 不剥夺：系统不会去把分配给某个进程的资源剥夺掉分配给其他进程
• 环路等待：循环等待资源释放，形成闭环

3、解决死锁问题的方法

• 死锁的预防
  • 打破四大条件
• 死锁的避免
  • 有序资源分配法：资源利用率比较低
  • 银行家算法
• 死锁检测：允许死锁产生，但系统定时运行一个检测死锁程序，若检测到系统中发生死锁，则设法加以解除
• 死锁解除：即死锁发生后的解除方法，如强制剥夺资源，撤销进程等。

4、银行家算法

银行家算法是分配资源的原则

• 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程
• 进程可以分期请求资源，但请求的总数不能超过最大需求量
• 当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源

3.2.6线程

• 传统的进程有两个属性

  • 可拥有资源的独立单位
  • 可独立调度和分配的基本单位

• 线程和进程的比较

  线程	进程
  独立调度的最小单位	拥有资源的最小单位
  可以共享进程的公共数据、全部变量、代码、文件等资源	拥有线程无法共享的资源，如线程的栈指针等标识数据

3.3存储管理

3.3.1页式存储、段式存储、段页式存储

1、页式存储

• 基本思想：分页存储，是把程序的逻辑空间和内存的物理空间按照同样的大小划分成若干页面，并以页面为单位进行分配。
• 页式存储管理地址转换如下：

• 优点：空间浪费小、存储共享容易、存储保护容易、能动态连接
• 缺点：由于管理软件的增加，复杂性和开销也随之增大，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降。

3.3.2快表

快表是一块小容量的相联存储器，由高速缓存起组成，速度快，并且可以从硬件上保证内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页 。

3.3.3页面置换算法

• 抖动：内存资源分配多，但是缺页次数超过资源少的时候

• 最优算法(OPT)

• 随机算法(RAND)

• 先进先出算法(FIFO)：有可能产生“抖动”，内存资源分配越多，越容易出现缺页

  • 淘汰最先访问的，内存中不存在则缺页

• 最近做少使用算法(LRU)：不会“抖动”，由于局部性原理，分配资源越多，表现性能越好

  • 淘汰已经访问过最久的

3.4文件管理

3.4.1索引文件结构

1、一般的索引文件结构

• 包含13个索引节点：0~12
• 索引节点分类：
  • 直接索引：0~9 节点，直接对应物理盘块
  • 一级间接索引：10 节点，指向物理盘块的地址，每个地址对应一个物理盘块，该节点存储的地址数为：一个物理盘块的大小/每个地址所占字节大小
  • 二级间接索引：11 节点，指向物理盘块地址存储的地址
  • 三级间接索引：12 节点，依次类推
• 每个节点存储的文件大小为物理盘块大小*物理盘块数量
• 间接索引级次越多，访问效率越低

2、文件和树形目录结构

• 文件属性：R（只读文件属性）A（存档属性）S（系统属性）H（隐藏文件）
• 文件名组成：驱动器 、路径、主文件名、扩展名
• 文件路径：
  • 绝对路径：从盘符开始的路径
  • 相对路径：从当前路径开始的路径
  • 全文件名：绝对路径+文件名

3.4.2空闲存储空间管理

• 空闲区表法：用表记录空闲区
• 空闲链表法：把空闲区连接成链表
• 位示图法

  • 把存储空间分为很多物理块，用1表示占用，2表示空闲，以此展现空闲空间

  • 物理块 /字长=物理块位置

  • 例题：

    某文件管理系统采用位示图记录磁盘的使用情况，如果系统字长为32wie，磁盘物理块大小为4MB，物理块一次编 为0、1、2…，位示图依次编 为0、1、2…，那么16538 物理块的使用情况在位示图中的第（字中描述；若果磁盘容量为1000GB，那么位示图需要（字来表示。

    解答：

    （1）：由于物理块从0开始编 ，则16538 物理块为第16539个物理块，物理块位置=16539/32=512…2，故物理块位置为513，由于位示图从0开始编 ，则物理块在位示图中512个字中描述

    （2）：磁盘容量为1000GB，则由1000×1024/4=250×1024个物理块，则在位示图中为第250×1024/32=8000个字

• 成组链接法：分组分链的方式进行空闲区管理

3.5设备管理

3.5.1设备的分类

• 按数据组织分类：块设备、字符设备
• 按资源分配角度分类：独占设备、共享设备和虚拟设备
• 数据传输速率分类：低速设备、中速设备、高速设备

3.5.2I/O软件层次结构

3.7嵌入式操作系统

• 特点
  • 微型化
  • 代码质量高
  • 专业化
  • 实时性强
  • 可剪裁配置
• 实时嵌入式操作系统的内核服务
  • 异常和终端
  • 计时器
  • I/O管理
• 常见的嵌入式RTOS（实时操作系统）
  • VxWorks
  • RT-Linux
  • QNX
  • pSOS
• 嵌入式操作系统初始化过程：按照自底向上、从硬件到软件的次序依次为
  • 片级初始化->板级初始化->系统初始化
    ，便于剪裁和移植。
    系统服务程序运行在用户地址空间，系统的可靠性、稳定性和安全性较高。
    可用于分布式系统 | 用户状态和内核状态需要频繁切换，从而导致系统效率不如单体内核 |

3.7嵌入式操作系统

• 特点
  • 微型化
  • 代码质量高
  • 专业化
  • 实时性强
  • 可剪裁配置
• 实时嵌入式操作系统的内核服务
  • 异常和终端
  • 计时器
  • I/O管理
• 常见的嵌入式RTOS（实时操作系统）
  • VxWorks
  • RT-Linux
  • QNX
  • pSOS
• 嵌入式操作系统初始化过程：按照自底向上、从硬件到软件的次序依次为
  • 片级初始化->板级初始化->系统初始化
  • 芯片级是微处理器的初始化，板卡级是其他硬件设备初始化，系统级初始化是软件及操作系统初始化