关于操作系统:SYSBASE操作系统笔记理论篇

操作系统：向应用程序提供资源集的根本形象，在相互竞争的程序之间有序地管制对处理器、存储器以及其余 I / O 接口设施的调配（资源管理：工夫复用、空间复用）。

计算机硬件：

CPU：

• 每个 CPU 根本周期中，从内存取指令 - 解码(以确定其类型和操作)- 执行，如此重复。

• 因为拜访内存慢，CPU 内设有寄存器:

  • 通用寄存器: 用来保留要害变量和长期数据

  • 专用寄存器：

    • 程序计数器：下个指令的内存地址
    • 堆栈指针：以后栈顶端
    • 程序状态字（PSW): 条件码位（由比拟指令设置）、CPU 优先级、模式（用户态或内核态）等管制位

• 古代 CP 设计：

  • 流水线：有独自的取指单元、解码单元和执行单元，能同时取出多条指令。
  • 超标量：更先进，有多个执行单元（只有有一个执行单元闲暇，就查看缓冲区中是否还有可解决的指令，如果有，就把指令从缓冲区中移出并执行之。）

• 模式：

  • 用户态：用户程序编码可能解决的

  • 内核态：无奈编码表示的，用户程序必须应用零碎调用（内中断）陷入内核并调用操作系统。

    • 内中断（异样）

      • 出错(fault): 保留指向触发异样的那条指令（例：缺页异样）
      • 陷入（trap)：保留指向触发异样的那条指令的下一条指令（例：调试）
    • 外中断

存储器

• CPU 寄存器 1ns <1k:32 位 CPU 是 32\32 64 位 CPU 是 64\64
• 高速缓存 2ns 4M
• 主存 10ns 1-8G RAM ROM Flash CMOS
• 磁盘 10ms 1-4T 低端硬盘速率 50MB/s, 高速硬盘 160 MB/s

I/ 0 设施

• I/ 0 设施 = 设施控制器 + 设施自身

• 设施控制器

  • 为操作系统提供一个简略的接口。在控制器中常常装置一个小的嵌入式计算机，运行为执行这些工作而专门编好的程序。
  • 大多数设施驱动程序（专门与控制器对话，收回命令并接管响应的软件）须要在内核态运行
• 设施自身：设施自身有个绝对简略的接口，这是因为接口既不能做很多工作，又曾经被标准化了。
• 实现 IO 的形式：忙期待、中断、间接存储器拜访

总线

• 最次要的 PCIe 总线

  • 简介：10+Gb/ s 是串行总线架构，取代传统 PCI 的并行总线架构，通过一条被称为数据通路的链路传递汇合了所有位的一条音讯，这十分像网络包。PCIe 2.0 规格的 16 个数据通路提供 64Gb/ s 的速度，降级到 PCIe 3.0 后会提速 2 倍，而 PCIe 4.0 会再提速 2 倍。

  • CPU

    • 通过 DDR3 总线与内存对话
    • 通过 PCie 总线与外围图形设施对话
    • 通过 DMI 总线经集成核心与所有其余设施对话

  • 集成核心

    • 通过通用串行总线与 USB 设施对话
    • 通过 SATA 总线与硬盘和 DVD 驱动器对话
    • 通过 PCle 传输以太网络帧

• USB 用来将所有慢速 I / 0 设施（如键盘和鼠标）与计算机连贯的

  • USB 1.0 12Mb/s
  • USB 2.0 480Mb/s
  • USB 3.0 5Gb/s

• SCSI

  • 一种高速总线用在 高速硬盘、扫描仪、服务器和工作站 640MB/s
• 即插即用：零碎主动地收集无关 1 / 0 设施的信息，集中赋予中断级别和 I / 0 地址，而后告诉每块卡所应用的数值。

启动计算机

• BIOS 查看所装置的 RAM 数量，键盘和其余根本设施

  • 扫描 PCie 和 PCI 总线并找出连在下面的所有设施
  • 尝试存储在 CMOS 存储器中的设施清单决定启动设施
• 操作系统询问 BIOS, 以取得配置信息
• 查看就绪设施驱动程序，操作系统将它们调入内核
• 创立须要的任何背景过程，启动登录程序或 GUI

操作系统基本特征

• 并发：同一时间段内产生

  • 并行：同一时刻产生（多道程序解决宏观上并发，宏观上交替执行）

• 共享

  • 互斥共享（如音频设备 打印机）
  • 同时拜访（磁盘文件）

• 虚构

  • cpu: 每个用户（过程）的“虚处理机”
  • 存储器：每个过程都占有的地址空间（指令 + 数据 + 堆栈）
  • 显示设施：多窗口或虚构终端
  • 打印设施：将临界资源变为同时拜访资源

• 异步性

  - 判据：无论快慢，后果雷同
  

过程线程

过程

• 模型

  • 一个过程就是一个正在执行程序的实例，包含程序计数器、寄存器和变量的以后值。

多道程序设计：（伪）并行状况下运行的过程集
```
    CPU 利用率 = 1-p^n 
            一 个过程期待 I / 0 操作的工夫与其停留在内存中工夫的比为 p
            n 称为多道程序设计的道数
```

• 创立

  • 1)零碎初始化．
  • 2)正在运行的程序执行了创立过程的零碎调用。
  • 3)用户申请创立一个新过程。
  • 4)一个批处理作业的初始化。

• 终止

  • 1)失常退出（被迫的）。
  • 2)出错退出（被迫的）。
  • 3)严重错误（非被迫）。
  • 4)被其余过程杀死（非被迫）。
• 阻塞 block
• 唤醒 wakeup
• 挂起 suspend

• 层次结构

  • UNIX 过程和它的所有子过程以及后嗣独特组成一个过程组。用户发信号后每个过程能够别离捕捉该信号、疏忽该信号或采取默认的动作，即被该信号杀死。在整个零碎中，所有的过程都属千以 init 为根的一棵树
  • Windows 所有的过程都是位置雷同的

• 过程的状态与转换

  • 状态：就绪（ready) 执行(running) 阻塞(blocked)
  • 具备挂起的状态：执行，流动就绪，流动阻塞，静止就绪，静止阻塞

• 过程管制块

  • 过程管制块中的信息

    • 处理机状态

      • 通用寄存器
      • 指令计数器
      • psw

    • 调度信息

      • 过程状态
      • 优先级
      • 调度所需信息（过程已期待 CPU 工夫，过程已执行的工夫总和）

    • 管制信息

      • 程序、数据地址
      • 同步和通信（音讯队列指针 信号量）
      • 占用资源清单
      • 链接指针（本过程 PCB 所在队列的下一个过程 PCB 的首地址）
      • 家族关系 子过程父过程标示

线程

• 概念

  • 轻型实体：只领有必不可少的资源，如：线程状态、寄存器上下文和栈

    • 独立调度和分派的根本单位
    • 就绪阻塞执行 3 种根本状态
    • 创立、终止工夫比过程短
    • 同过程内线程切换工夫比过程短，零碎开销小
  • 可并发执行
  • 共享过程资源（如内存 文件）

• 模型

  • TCB

• POSIX 线程(IEEE 1003.lc 线程规范)

  • 线程包 pthread
  • pthread_create 创立一个新线程
  • pthread_exit 完结调用的线程
  • pthread_join 期待一个特定的线程退出
  • pthread_yield 开释 CPU 来运行另外一个线程
  • pthread_attr_init 创立并初始化一个线程的属性构造
  • pthread_attr_destroy 删除一个线程的属性构造

• 实现

  • 在用户态实现

    • 长处

      • 快捷（不须要陷入内核，上下文切换，刷新内存高 速缓存）
      • 它容许每个过程有本人定制的调度算法

    • 毛病：

      • 若外围阻塞过程，则过程中所有线程将被阻塞
      • 同一过程中的 2 个线程不能同时运行于 2 个处理器上
  • 在内核态实现

  • 混合实现

    • 应用内核级线程，而后将用户级线程与某些或者全副内核线程多路复用起来

• 调度程序激活机制

  • 指标：模仿内核线程的性能，为线程包提供通常在用户空间中能力实现的更好的性能和更大的灵活性。

• 弹出式线程

  • 概念：一个音讯的达到导致系统创立一个解决该音讯的线程
  • 长处：疾速创立。没有必须存储的寄存器、堆栈

过程间通信

• 临界区：对共享内存进行拜访的程序片段。

  • 互斥：阻止多个过程同时读写共享的数据

• 一个好的并发计划需满足：

  • 1)任何两个过程不能同时处千其临界区。
  • 2)不应答 CPU 的速度和数址做任何假如。
  • 3)临界区外运行的过程不得阻塞其余过程。
  • 4)不得使过程无限期期待进入临界区。

• 忙期待的互斥计划

  • 屏蔽中断: 每个过程在刚刚进入临界区后立刻屏蔽所有中断，在来到之前再关上中断, 防止不了竞争
  • 锁变量: 防止不了竞争
  • 严格轮换法：自旋锁(spin lock) 违反了 3）
  • Peterson 解法：个不须要严格轮换的软件互斥算法。
  • TSL 指令：须要硬件反对(test and set lock 测试井加锁)
  • XCHG：原子性地替换了两个地位的内容
  • 毛病：优先级反转问题

• 睡眠（sleep）与唤醒（wakeup）过程间通信原语使得在无奈进入临界区时将阻塞

  • 生产者-消费者 (producer-consumer) 问题（有界缓冲区）

• 信号量

  • 实现互斥或同步。

    • down（P）和 up(V) (别离为一般化后的 sleep 和 wakeup) 对一倌号县执行 down 操作，则是查看其值是否大千 0。若该值大千 0, 则将其值减 1 (即用掉一个保留的唤醒信号）并持续；若该值为 0, 则过程将睡眠，而且此时 down 操作并未完结。查看数值、批改变批值以及可能产生的睡眠操作均作为一个繁多的、不可分割的原子操作实现。

• 互斥量

  • 信号量的简化版

• 管程

  • 一种高级同步原语，任何时刻管程中只有一个沉闷过程，进入管程的互斥有编译器负责，通常是一个互斥量或信号量。
  • 引入条件变量和 2 个操作（wait signal）来保障过程在无奈运行时被阻塞。
  • 限度：太低级，在多数编程语言之外无奈应用。（分布式系统多个 CPU 各有公有内存，这些原语则生效）

• 消息传递

  • 2 条原语。send: 调用向一个给定的指标发送一条音讯，receive: 调用从一个给定的源（或者是任意源，如果接收者不介意的话）接管一条音讯。如果没有音讯可用，则接收者可能被阻塞，直到一条音讯达到，或者带着一个错误码立刻返回。

• 屏障

  • （barrier）用于过程组，除非所有的过程都就绪筹备着手下 一 个阶段，否则任何过程都不能进入下一个阶段。

• 防止锁

  • 读 - 复制 - 更新(Read-Copy-Update, RCU), 增删援用节点而不必锁。

调度

• 调度机会：

  • 1. 在创立一个新过程之后，须要决定是运行父过程还是运行子过程。
  • 2. 在一个过程退出时。
  • 3. 当一个过程阻塞在 1 / 0 和信号量上或由千其余起因阻塞时，必须抉择另一个过程运行。
  • 4. 在一个 I / O 中断产生时

• 调度算法分类和指标

  • 所有零碎

    • 偏心 – 给每个过程偏心的 CPU 份额
    • 策略强制执行 – 保障规定的策略被执行
    • 均衡 – 放弃零碎的所有局部都繁忙

  • 批处理零碎

    • 吞吐扯 – 每小时最大作业数
    • 周转工夫 – 从提交到终止间的最小工夫
    • CPU 利用率 – 放弃 CPU 始终繁忙

  • 交互式零碎

    • 响应工夫 – 疾速响应申请
    • 均衡性 – 满足用户的冀望

  • 实时零碎

    • 满足截止工夫 – 免失落数据
    • 可预测性 – 在多媒体系统中防止品质升高

• 典型调度算法

  • 批处理零碎

    • 先来先服务
    • 最短作业（过程、线程）优先
    • 最短剩余时间优先

  • 交互式零碎

    • 工夫片轮转调度算法
    • 优先级调度算法
    • 多级反馈队列调度算法
    • 最短过程优先
    • 保障调度
    • 彩票调度
    • 偏心分享调度
  • 实时零碎
  • 高响应比优先调度算法

• 策略和机制

  • 调度机制和调度策略拆散，是的调度算法参数化，可由用户设置扭转。
• IPC 问题
• 哲学家就餐问题
• 读者写者问题

内存治理

• 地址空间

  • 地址空间：存储器形象，用于内存寻址的一个过程
  • 基址寄存器：程序起始物理地址
  • 界线寄存器：程序的长度
  • 替换技术：把一个过程残缺调入内存，使该过程运行一段时间，而后把它存回磁盘。
  • 闲暇内存治理：动静分配内存时个别用位图和闲暇区链表治理

• 页表

  • 虚拟地址 = 虚构页号（高位）+ 偏移量（位置局部）

  • 减速分页过程

    • 要思考两个次要问题：

      • 1)虚拟地址到物理地址的映射必须十分快。
      • 2)如果虚拟地址空间很大，页表也会很大

    • 计划：

      • 1）转换检测缓冲区（相联存储器 / 快表）：为计算机设置一个小型的硬件设施，将虚拟地址间接映射到物理地址，而不用再拜访页表。
      • 2）软件 TLB 治理：TLB 大到（如 64 个表项）能够缩小失效率

  • 针对大内存的页表

    • 多级页表
    • 倒排页表：理论内存中的每个页框对应一个表项，而不是每个虚构页面对应一个表项。

• 页面置换算法

  • 最优
  • 最近未应用
  • 先进先出
  • 第二次机会
  • 时钟
  • 最近起码应用

  • 工作集模型：

    • 概念：分页零碎都会设法跟踪过程的工作集，以确保在让过程运行以前，它的工作集就已在内存中。
    • 算法：当产生缺页中断时，淘汰一个不在工作集中的页面。

  • 工作集时钟

    • 不用扫描整个页表能力确定被淘汰的页面
    • 所需的数据结构是一个以页框为元素的循环表

文件

• 文件

  • 命名

  • 构造

    • 字节序列；记录序列；树

• 目录

  • 档次目录零碎

• 文件系统实现

  • 间断调配
  • 链表调配
  • 采纳内存中的表进行链表调配

• 治理和优化

  • 磁盘空间治理

    • 块大小

      • 从历史观点上来说，文件系统将大小设在 1~4KB 之间，但当初随着磁盘超过了 1TB, 还是将块的大小晋升到 64KB 并且承受节约的磁盘空间更好

    • 记录闲暇块

      • 磁盘块链表 每一块要用到 32 位
      • 位图 每块只用一个二进制位标识 1TB 磁盘 须要大概 130 000 个 1KB

    • 磁盘配额

      • 系统管理员分给每个用户领有文件和块的最大数量，操作系统确保每个用户不超过分给他们的配额。

  • 备份

    • 1)从意外的劫难中复原。
    • 2)从谬误的操作中复原。

  • 一致性

    • 块的一致性检查和文件的一致性查看

  • 性能

    • 高速缓存
    • 块提前读
    • 缩小磁盘臂静止
  • 碎片整顿

输入输出

IO 硬件原理

• IO 设施

  • 分类：

    • 块设施：把信息存储在固定大小的块中，每个块有本人的地址（磁盘）
    • 字符设施：以字符为单位发送或接管一个字符流。（打印机 网络接口 鼠标）

  • 组成：

    • 机械部件（设施自身）

    • 电子部件（设施控制器 / 适配器）

      • 工作：把串行的位流转换为字节块，并进行必要的谬误校对工作

      • 组成：

        • 有几个寄存器用来与 CPU 进行通信，操作系统写入它从而发送 | 接管 | 开启 | 敞开

          • 形式：

            • 内存映射 I /O
            • 间接存储器存取（DMA）
        • 能够读写的数据缓冲区

IO 软件原理

• 指标

  • 设施独立性：能够拜访任意 I / 0 设施而无需当时指定设施
  • 对立命名：一个文件或一个设施的名字应该是个简略的字符串或整数，不依赖于设施
  • 错误处理：尽可能地在靠近硬件层面失去解决

• 实现

  • 程序控制 I /O：

    • 打印例子:

      • 1. 软件首先要在用户空间的一个缓冲区中组装字符串
      • 2. 用户过程通过收回关上打印机一类的零碎调用来取得打印机以便进行写操作
      • 3. 操作系统（通常）将字符串缓冲区复制到内核空间中的一个数组（如 p) 中
      • 4. 操作系统查看打印机以后是否可用（轮询、忙期待）
      • 5. 一旦打印机可用，操作系统就复制第一个字符到打印机的数据寄存器中（内存映射 1 /0），激活打印机

      • 6. 打印机的第二个寄存器表明其状态

        • 当字符写到数据寄存器的操作将导致状态变为非就绪
        • 解决完以后字符时设置某一位或者将某个值放到状态寄存器表明已就绪
      • 7. 反复 5 直到打印完，回到用户过程
    • 毛病：忙期待将是低效的

  • 中断驱动 I /O

    • 打印例子:

      • 当打印机将字符打印完并且筹备好接管下一个字符时，它将产生一个中断。这一中断将进行以后过程并且保留其状态。
    • 毛病：中断产生在每个字符上

  • DMA 的 I /O

    • 打印例子：

      • 让 DMA 控制器一次给打印机提供一个字符，而不用打搅 CPU。
      • DMA 控制器是程序控制 I /O, 由 DMA 而不是 CPU 做全副工作
      • 将中断的次数从打印每个字符一次缩小到打印每个缓冲区一次

IO 软件档次

• 自顶向下 4 层：

  • 1. 用户级 IO 软件
  • 2. 与设施无关的操作系统软件
  • 3. 设施驱动程序
  • 4. 中断处理程序

磁盘

• 磁盘臂调度算法

  • 1. 先来先服务
  • 2. 电梯算法

• 错误处理

  • 控制器中解决: 对千每一个坏扇区，用一个备用扇区替换它
  • 驱动程序中解决: 收回一个 recalibrate (从新校准）命令，让磁盘臂尽可能地向最里面挪动，并将控制器外部的以后柱面重置为 0

• 高级磁盘控制器

  • 相当弱小的多核 ARM 处理器，有足够的资源能够轻易地运行 Linux

• 稳固存储器

  • 稳固写
  • 稳固读
  • 解体复原

时钟

• 时钟硬件

  • 2 种类型：

    • 简略时钟：每个电压周期产生一个中断，频率是 50Hz 或 60Hz
    • 3 部件形成：晶体振荡器、计数器和存储寄存器，1000MHz 甚至更高的频率

  • 可编程时钟操作模式：

    • 实现模式：one-shot mode
    • 方波模式：square-wave mode

• 时钟软件（时钟驱动程序）

  • 1)保护日工夫。
  • 2) 避免过程超时运行。
  • 3)对 CPU 的应用状况记账。
  • 4)解决用户过程提出的 alarm 零碎调用。
  • 5)为零碎自身的各个局部提供监督定时器。
  • 6) 实现概要分析、监督和统计信息收集。

死锁

• 资源

  • 可抢占资源: 能够从领有它的过程中抢占而不会产生任何副作用(如 存储器)
  • 不可抢占资源：在不引起相干的计算失败的状况下，无奈把它从占有它的过程处抢占过去（如 蓝光光盘刻录机）死锁与不可抢占资源无关
• 定义：一个过程汇合中的每个过程都在等持只能由该过程汇合中的其余过程能力引发的事件

• 产生（资源）死锁的四个必要条件：

  • 1. 互斥条件
  • 2. 占有和期待条件
  • 3. 不可抢占条件
  • 4. 环路期待条件

• 死锁检测

  • 每种类型一个资源的死锁检测：检测有向图是否有环路、
  • 每种类型多个资源的死锁检测：基千向最的比拟（每个过程起初都是没有标记过的。算法开始会对过程做标记，过程被标记后就表明它们可能被执行，不会进入死锁。当算法完结时，任何没有标记的过程都是死锁过程。）

• 死锁复原

  • 利用抢占复原
  • 利用回滚复原
  • 通过杀死过程复原

• 死锁防止

  • 资源轨迹图
  • 平安状态和不平安状态
  • 单个资源的银行家算法
  • 多个资源的银行家算法

• 死锁预防

  • 毁坏四个必要条件之一

• 其余问题

  • 两阶段加锁
  • 通信死锁
  • 活锁
  • 饥饿

参考资料

• 《古代操作系统 第四版》
• 计算机考研基础课《操作系统》