本博客采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本博客文章必须也遵循署名-非商业用途-保持一致的创作共用协议.

#0. 绪论

多数计算机有两种运行模式: 内核态和用户态

  • 操作系统运行在内核态(管态, 核心态), 具有对所有硬件的访问权
  • 用户态下, 只是用机器指令的一个子集(Shell, GUI处在用户态的最低层次)

操作系统提供资源集的清晰抽象, 并管理硬件资源

  1. 第一代(1945-1955): 真空管和穿孔卡片
  2. 第二代(1955-1965): 晶体管和批处理系统
  3. 第三代(1965-1980): 集成电路芯片和多道程序设计
  4. 第四代(1980至今): 个人计算机(PC)

#1. 进程与线程

计算机上所有可运行的软件, 通常也包括操作系统, 被组织成若干顺序进程, 简称进程

4种主要事件导致进程的创建:

  1. 系统初始化
  2. 正在执行的进程进行系统调用
  3. 用户请求创建一个新进程
  4. 一个批处理作业的初始化

4中进程终止:

  1. 正常退出(自愿退出)
  2. 出错退出(自愿退出)
  3. 严重错误(非自愿退出)
  4. 被其他进程杀死(非自愿退出)

父进程和子进程以某种形式保持关联, 进程只有一个父进程

进程三态及其转化 : 就绪, 执行, 阻塞

进程有一个地址空间和多个控制线程(又称轻量级进程)

  • 线程中有一个程序计数器, 记录接下来要执行的指令
  • 线程拥有寄存器, 保存线程当前的工作变量
  • 线程拥有堆栈, 记录执行历史, 其中每一帧保存已调用但还没有返回的过程

线程共享进程中的地址空间, 全局变量, 打开文件, 子进程, 即将发生的预警, 信号与信号处理程序, 账户信息

三种线程及优缺点:

  • 用户级线程
  • 内核级线程
  • 混合机线程

##1.1. 进程间通信(IPC)

怎么避免竞争条件, 进行互斥访问?

当前主要的解决方案是使用信号量

三大经典IPC问题:

  • 生产证-消费者问题
  • 哲学家就餐问题(注意解法, 互斥访问有限资源的竞争问题)
  • 读者写者问题(数据库访问问题)

##1.2. 调度

多个进程或者线程同时竞争CPU, 有两个或者更多的处于就绪状态, 完全选择使用CPU权利的工作的部分叫做调度程序

总体可以分为两大类: 抢占式和非抢占式

#2. 存储管理

保证多个应用程序同时处于内存中并且不相互影响, 需要解决的关键问题: 保护和重定位

地址空间是对内存的抽象.

交换和虚拟内存:

  • 交换: 把一个进程完整调入内存, 使该进程运行一段时间, 然后存回内存(交换在内存中产生多个空闲区, 将小的空闲区合成一大块, 称为内存紧缩)
  • 虚拟内存: 进程在只有一部分被调入内存的情况下运行

空闲内存的管理:

  • 位图(查找耗时)
  • 空闲链表管理方法(首次适配算法, 下次适配算法, 最佳适配算法, 最差适配算法, 快速适配算法)

##2.1. 虚拟内存

虚拟内存的基本思想: 每个程序拥有自己的地址空间, 这个空间被分割成多个快, 每块称作一页, 通过MMU将页映射到物理内存.

加速分页使用TLB
对大内存的也表使用多级页表, 倒排页表

页面置换算法:

  • 最优算法(理想化)
  • NRU, LRU, 老化算法(基于LRU思想)
  • FIFO算法, 第二次机会算法(基于FIFO)
  • 时钟算法
  • 工作集算法和工作集时钟算法

缺页终端处理

  1. 硬件陷入内核(中断),在堆栈保存程序计算器(上下文)
  2. 启动汇编代码例程保存通用寄存器和其他易失信息, 以免操作系统被破坏
  3. 操作系统发现缺页终端, 尝试发现需要的虚拟页面(通过硬件或者软件)
  4. 获得缺页终端的虚拟地址, 操作系统检查该地址的有效性, 并检查存取和保护是否一致.
  5. 如果是脏位,安排页写会磁盘, 一旦页框干净了,操作系统检查所需要页面在磁盘上的地址, 通过磁盘操作将其装入.
  6. 当磁盘终端发生, 表示该页已被装入, 页表已经更新可以反映它的位置, 页框标记也正常.
  7. 回复发生缺页中断之前的状态, 程序计算器重新指向这条指令.
  8. 调度引发缺页终端的进程, 操作系统返回调用它的汇编语言例程
  9. 该例程回复寄存器和其他状态信息, 返回到用户空间继续执行, 就像没发生中断一样.

分页和分段的区别

3. 文件系统

文件是进城创建的信息逻辑单元

文件的存取(注意优缺点):

  • 顺序存取
  • 随机存取

文件存储的实现:

  1. 连续分配(实现简单, 读操作性好, 磁盘会变零碎)
  2. 链表分配(充分利用磁盘块, 随机存取慢)
  3. 在内存中采用表的链表分配(文件分配表, 必须把整个表放在内存中)
  4. i节点(给每个文件赋予一个i节点的数据结构记录磁盘块)

共享文件中的软链接和硬链接问题

日志文件系统: 当系统完成即将完成的任务前崩溃时, 重新启动后, 可以查看日志, 获取崩溃前计划完成的任务, 并完成他们.

虚拟文件系统(重要)

##3.1. 磁盘空间管理

  • 磁盘块的大小设置(一般为4KB)
  • 跟踪空闲块(位图和空闲链表)

##3.2. 文件系统性能优化

  1. 使用高速缓存较少磁盘访问次数
  2. 块提前读(主要适用于顺序存取)
  3. 减少磁盘臂运动(将可以一起读到的文件放在同一个柱面)

#4. 输出/输出(I/O)

I/O设置大致分为: 块设备和字符设备

设备控制器的任务是把串行的位流转换为字节块, 并进行必要的错误校正工作.

##4.1. DMA

  1. CPU通过设置DMA控制器的寄存器对它进行编程
  2. DMA控制器通过在总线上发出一个读请求到磁盘控制器而发起DMA传送
  3. 数据传送, 写到内存
  4. 磁盘控制器在总线上发出一个应答信号到DMA控制器
  5. 完成时, DMA控制器将中断CPU

设备与中断控制器之间的连接实际上使用的是总线上的中断线

中断信号导致CPU停止当前正在做的工作并且开始做其他的事, 地址线上数字被用作指向一个中断向量的表格的索引, 以便读取一个新的程序计数器

##4.2. I/O三种实现方式

  • 程序控制I/O
  • 中断驱动I/O
  • 使用DMA的I/O

##4.3. I/O软件层次

  1. 用户级I/O软件
  2. 与设备无关的操作系统软件(执行对所有设备公共的I/O功能, 并且向用户层软件提供统一的接口)
  3. 设备驱动程序(接收来自其上方与设备无关的软件发出的抽象的读写请求)
  4. 中断驱动程序(中断的结果是使先前被阻塞的驱动程序现在能够继续运行)
  5. 硬件

#5. 死锁

资源分为可抢占和不可抢占的. 死锁和不可抢占的资源有关, 有关可抢占的资源的潜在死锁通常可以通过在进程之间重新分配资源而化解.

死锁定义: 如果一个进程集合中的每一个进程都在等待只能由该进程集合中的其他进程才能引发的事件, 那么该进程集合发生死锁.

死锁的四个必要条件:

  • 互斥条件
  • 占有与等待条件
  • 不可抢占条件
  • 环路等待条件

死锁检测可以通过有向图检测环路算法(单个资源), 使用矩阵数据结构算法(多个资源)

死锁避免: 银行家算法

死锁预防: (死锁避免本质上是不可能的)可以通过破坏四个必要条件