操作系统的定义

一个管理计算机硬件与软件资源的程序

内核与操作系统的关系

• 内核是操作系统的核心：需要特权，内存管理和CPU调用。
• 内核不等于操作系统。
• 操作系统还包括GUI和用户相关的一些接口。

用户态切换为内核态：

系统调用：通过trap自陷实现

进程与线程

进程

定义：执行中的程序：

进程控制块 PCB：代码段，PC，栈/堆，系统资源等

• 包括程序状态：程序指针，栈，CPU寄存器状态，内存占用，文件列表等等。
• 包括进程状态：运行状态和进程编号。
  
  

进程运行状态

就绪状态：只需要CPU就能运行

执行状态

等待/阻塞状态：需要外部设备才能运行

• 例如：等待打印机-外部设备，需要进行IO读取操作等等。
• 信号量也是一种外部设备。

父子进程

级联终止：递归的终止每一个子进程

孤儿进程：父进程终止，子进程仍未终止

僵尸进程：进程已结束，但是OS未收回其进程控制块占用的资源

线程：轻量级进程，进程的一个执行流

特点：共享静态资源：例如地址空间和文件；独立拥有运行时状态：PC，栈和寄存器

进程 vs 线程

对比项	进程	线程
基本概念	正在运行的程序实例	进程中的执行流
资源拥有	拥有独立的地址空间和系统资源	不独立拥有资源，主要共享所属进程的资源
内存空间	进程之间内存相互独立	同一进程内线程共享代码段、数据段、堆等
栈空间	每个进程有自己的地址空间	每个线程有自己的栈和寄存器状态
创建/销毁开销	较大	较小
切换开销	较大，需要切换地址空间等	较小，同进程线程切换更轻量
通信方式	进程间通信较复杂，如管道、消息队列、共享内存、Socket	线程间通信较简单，可直接共享变量
安全性/隔离性	隔离性强，一个进程崩溃通常不直接影响其他进程	隔离性弱，一个线程出错可能导致整个进程崩溃
适合场景	需要资源隔离、稳定性较高的任务	需要并发执行、共享数据、低开销切换的任务

进程间通信

共享内存：低成本，同步问题

• 多个进程通讯时，可以划分同一块使用的进程，每一个进程的某个内存区域都用来存储其地址。
• 建立共享内存需要较多时间，但是几乎没有其他的通信成本。
• 缺点：存在明显的进程间不同步问题：写和读没有任何限制。

消息传递：较高成本，无同步问题

• 两个进程通讯时，使用内核的消息队列。
• 从消息队列中按顺序产出和消费消息，同步问题少。
• 缺点：生成消息和消费消息都需要切换到内核态，使用系统调用，会有较大成本。

进程间同步问题

竞态：多个进程同步访问同一个共享资源，导致产生错误结果

原子操作：不可被中断和拆分的操作

临界区：当多个进程访问同一处代码段时，该代码段称为临界区

解决同步问题的要求

互斥

进展

有限等待

解决同步问题：软件

双标志法：flag标识是否准备和turn标识其他条件

Peterson算法：谦让算法，将资格让给别人

Dekker算法：主动放弃 / 取消准备

• 钥匙在对方：主动放弃(取消准备)，让别人先进入临界区
• 别人结束后再重新准备进入临界区。
  

多进程方法：面包店算法

原始面包店算法为什么失败：1.相同取号 2.选号不同步

实现：(选号,进程号)标识，对于选号加锁

互斥锁：有锁不能进入临界区

• 有锁不能进入临界区
  

信号量：多个共享资源的锁

结构体信号量：避免阻塞进程处于就绪态占用资源

• wait：如果有可用资源，则减少当前资源数，否则阻塞
• signal：释放资源，可用资源+1

经典同步问题及其解决

有限缓冲区问题：使用两个信号量+互斥锁

多个读写者的问题：写者和第一个读者拿互斥锁，最后一个读者放弃锁

哲学家问题：同时拿一双筷子+加锁

• n个哲学家n个筷子，需要同时拿两个筷子才能就餐。

解决同步：硬件

test_and_set

compare_and_swap

死锁

死锁的必要条件

• 互斥

• 保持等待

• 非抢占

• 循环等待

死锁预防

破坏死锁的条件：互斥，保持等待，非抢占式，循环等待

• 互斥：不能解决
• 保持等待：只能一次性请求资源，否则放弃自身所有资源
• 非抢占：抢占其他进程的资源
• 循环等待：每一个进程请求资源的编号递增 (请求资源号只能递增)

数据库并发事务的死锁预防：Wait-die和Wound-die

事务：事务是一组数据库操作

• 等待-死亡法 Wait-die：时间戳早的老进程可以等待年轻进程的锁，年轻进程请求老进程的锁会自毁

• 创伤-等待法 Wound-die：年轻进程可以请求老进程的锁，老进程请求年轻进程的锁时直接杀死年轻进程。

死锁避免：银行家算法

资源分配向量，最大需求向量，当前需求向量和当前资源向量

• 确定进程现在分配了多少资源
• 进程运行所需要的各个资源数
• 进程还剩下多少资源

流程

• 1.比对当前资源是否能满足当前进程
• 2.如果可以，直接分配给当前进程，并且等待进程执行完释放资源。更新可以支配的资源
• 3.如果不行，跳转下一个进程
• 4.反复循环，直到为每一个进程都分配足够的资源并执行，否则无法避免死锁。
  

死锁检测：检测死锁并且解决

• 杀死某个进程

• 直接抢占某个进程的资源

CPU调度

调度器的种类：长期，中期和短期

• 长期调度器：负责调度作业到准备态，频率最低

• 短期调度器：负责调度准备态进程到运行态，频率最高

• 中期调度器：负责调度等待态进程到内存中，以节省资源

CPU调度算法

评价标准

• 等待事件
• 周转率
• CPU利用率

FCFS：先到先得

SJF：短作业优先，非抢占

• 根据当前就绪进程的预估执行事件来选择执行。
• $不会抢占，一直执行到底$。
  

SRTF：最短剩余时间优先，抢占式

• 实时进行检查：如果有预估执行时间少于当前执行进程的进程，优先执行该进程
• $抢占当前进程的执行权$。
  

优先级调度：固定优先级

Round Robin：轮询算法，每一个进程固定时间片

多级队列：权重分层，算法独立，不可流动

多级反馈队列：权重随执行次数降低，算法独立，可以流动

实时CPU调度算法

进程的实时性：某些进程必须在特定周期得到执行

单调速率调度：根据周期倒数确定权重

EDFS：最短截至时间优先，实时比较不同进程的截至时间，优先执行接近截至时间的进程

虚拟内存技术

虚拟地址(逻辑地址) vs 物理地址

• 程序只知道逻辑地址，所以看上去貌似是连续的。但很多时候对应的物理地址不是连续的。
• 逻辑地址是私有的，连续的。
  

内存管理单元 MMU：保护程序不访问错误物理地址

• 由base和limit组成：base标识程序逻辑地址对应的第一个物理地址。
• limit标识程序最多可以访问多少大小的物理/逻辑空间。

内存划分方法

固定内存划分：分为固定的分区，内碎片问题

变长内存划分：根据程序内存需要划分，外碎片问题

分段技术：变长区域，段表，外碎片

• 程序根据自身需要进行分段，分为多个可能不等长的段。
• 根据段表来存储程序段到物理段的映射关系。
• 因为不等长，所以段表需要存储段号和当前段长。

分页技术：固定长度，页表，内碎片

• 进程的内存和物理内存分为固定大小的帧，通过页表查询物理帧。
• 页表包括：逻辑帧对应哪一个物理帧。

页表查询：逻辑地址=虚拟页号(VPN)+偏移

单级别页表查询

• 先查虚拟页号VPN，然后查表，使用TLB块表或者其他方式，最后得到物理页号PPN，加上偏移得到真实数据地址。

多级页表查询：先查下一级页表所在块，然后递归查询直到数据

页表的内存问题：转置页表，下标代表物理页号，表项代表逻辑页号+偏移

• 每一个进程都有固定的页表，标识逻辑页号-物理页号，会很占用空间
• 转置页表就是每一个下标都是物理页表，对应逻辑页表+进程号，全局共享。
  

页表的访问：TLB快表技术。

• 记录映射和是否修改的记录。
  

共享页面：一般进程间的页面是不共享的

请求分页技术：进程按需加载内存

• 一个进程需要的内存比实际内存大得多。
• 只在必要时将进程所需要的内存加载到物理内存的页中，否则放在磁盘里。

页错误：实际上只是当前进程所需的内存未加载到物理内存中

页面替换算法

先到先来算法：永远将第一个页面进行交换

LRU：谁最久没被使用过就交换谁

• 其实就是页面命中时要增加权重，放在第一位更新LRU缓存。
• 每次都将LRU缓存中最后一位(标识最久没使用)的页面交换出去。
  

磁盘

磁盘的组成：读写头，轨道=圆形分布的数据块，扇区=数据块

• 读写头：用于读和写的媒介
• 轨道：一个 磁盘由多个轨道tracks组成。
• 扇区：扇区就是对应的数据块。

磁盘的读写的延迟：旋转时延+寻道时延+传输时延

• 旋转时延：与转速有关
• 寻道时延：读写头移动到某个扇区的时间有关
• 传输时延：数据进行读取和写入和时延

寻道算法

先到先来 FCFS

最短寻道时间优先 SSTF：优先去离当前磁头最近的扇区

电梯算法 SCAN：从左到右扫描，到右端终点后反向遍历

C-SCAN：从左到右扫描，到右端后回到最左端，不处理中间请求

LOOK：电梯算法快速版，只扫描最小请求和最大请求的区域，不扫描全部扇区

C-LOOK：C-SCAN快速版，只扫描最小请求和最大请求的区域，不扫描全部扇区

RAID：冗余磁盘阵列

RAID的定义

思想：多个物理磁盘组成一个/少量逻辑磁盘，将数据分散到各个物理磁盘上，增加读写性能和数据安全性。

条带化：数据切片，分散存储到多个磁盘上。

镜像：数据复制到多个磁盘上备份

检验：牺牲磁盘空间，保存检验信息，根据检验信息还原损坏数据

RAID0：条带化，读写性能强

RAID1：镜像保护，读性能快，写性能慢

RAID5：条带化+检验和，磁盘利用率低，读速度较快，写速度较慢

RAID10：条带化+镜像化，条带化存储，子磁盘系统使用镜像化保护，

文件系统

定义：操作系统管理和组织文件的软件系统

文件：不代表真实数据，包含数据的元信息

文件系统的组织结构：

• inode：linux系统管理文件的数据结构

• 包括文件大小，时间戳和真实存储位置的指针等信息。

• 目录项：文件名+inode

• 超级块：有多少个目录项和inode块

• 文件系统的存储情况：包括存储了多个inode，目录和块大小信息。

组织结构：磁盘中的多个扇区组成一个文件块，磁盘系统分为：inode，目录项和超级块。

文件存储方式

连续存储：文件包含首个块和块数量的信息

非连续存储：文件包含首位块和末位块的指针，使用链表链接

空间文件块管理

查表法

链表法：空闲文件块链接起来

位图法

链接Link：一个文件关联到另一个文件

硬链接：文件a和文件b链接=文件a和b的指向的inode都相同，删除任一一个文件不影响其他文件的数据引用

软链接：文件a和文件b链接=文件b指向文件a，如果文件a被删除，那么文件b就是指向空链接。

I/O 方式

程序化IO

• CPU一直询问缓存器是否准备好
• 一旦缓存区准备好，CPU直接开始将其传输到内存中去。

中断化IO

• CPU首先询问缓存是否准备好
• 如果没准备好，则等待缓存区准备好。
• 如果准备好，则向CPU发送中断，CPU停止当前的事情
  ，开始负责传输到内存中。

直接内存访问 DMA

• DMA负责CPU和磁盘的沟通
• CPU发送查询命令，DMA负责将磁盘中的内存复制到内存，然后再中断CPU程序。
• CPU负责将其从内存传输到内核区。

中断处理

• 中断当前的事务
• 保存CPU现场：程序的PC，栈指针和CPU当前寄存器状态等等。
• 根据中断向量查询\color{red}{中断服务程序}。
• 执行中断服务程序。
• 回复现场和重新执行。