Happyboat's Blog
Go back

操作系统笔记整理

Updated:
Edit page

Table of contents

Open Table of contents

绪论

裸机、虚拟机（aka拓展机，不是开一个子系统那种虚拟机）

联机、脱机

批处理系统、实时操作系统、分时操作系统；通用操作系统

操作系统特征：并发、共享、虚拟、异步

并发是“多个任务交替推进、看起来同时进行”，并行是“多个任务在同一时刻真正同时执行”。

资源管理：进程管理、存储器管理、设备管理（外部 I/O 设备资源）、文件管理

操作系统中的中断可分为以下几类：

外中断 Interrupt：来自 CPU 外部，通常由硬件设备异步触发。常见例子有时钟中断、键盘中断、鼠标中断、磁盘 I/O 完成中断。

异常 Exception（内部中断）：来自 CPU 执行指令时发生的内部事件，通常是同步触发。异常又可分为故障 Fault、终止 Abort 和陷阱 Trap。

  • 故障 Fault：一种可恢复的异常，处理程序修复问题后，通常回到出错指令重新执行。常见例子有缺页异常 Page Fault、除零错误 Divide-by-zero。

  • 终止 Abort：一种严重且通常不可恢复的异常，处理程序一般会结束进程或导致系统崩溃。常见例子有严重硬件错误、机器检查异常 Machine Check。

  • 陷阱 Trap：由程序主动执行特殊指令触发，处理完成后通常执行下一条指令。常见例子有系统调用 System Call、调试断点 Breakpoint。软中断 Software Interrupt：由软件指令主动触发，很多教材会把它看作陷阱 Trap 的一种典型形式。常见例子有 int 指令、syscall、ecall。

进程管理

进程

内存中的进程

PCB包含：PPT第三章Page17

进程的状态：就绪，阻塞，运行；挂起，活动。挂起/活动之间：激活。阻塞/就绪之间：唤醒。 “就绪、阻塞是自身健康状态，挂起、活动是人身自由状态，二者并存”

失去CPU：发生中断，CPU被OS抢走，转就绪态；发起系统调用，OS无法立即完成，转阻塞态。

进程操作使用原语，原语实现方式：开头关中断，完成后重开中断。（外部中断）

进程调度：

级联终止

进程之间通信：消息，管道，共享内存

线程

动机：进程的创建、撤消、切换等操作涉及到资源（特别是内存资源）管理，时空开销较大；多个进程间的协作不方便

进程：拥有资源，调度分派单位；引入线程：进程为拥有资源单位，线程为调度分派单位

线程

每个线程有自己的用户栈和内核栈

TCB、线程的状态

进程切换的全过程：

多线程实现的两种方法：

用户线程和内核线程：一对一（主流） 多对多 多对一

Windows和Linux中的线程库、不同语言的线程库

进程调度

吞吐量：单位时间内运行完的进程数 周转时间：从作业提交到完成的时间间隔；带权周转时间：周转时间除以运行时间 等待时间：进程在就绪队列中等待调度的时间总和 响应时间：从提交请求到系统首次产生响应所用的时间

FCFS,SJF(SRF),RR,MQ,MFQ，PPT第5章Page18

  • FCFS（First-Come, First-Served / 先来先服务）

  • SJF（Shortest Job First / 最短作业优先）

  • SRF / SRTF（Shortest Remaining Time First / 最短剩余时间优先）：SJF 的抢占式版本

  • RR（Round Robin / 时间片轮转）：每个进程轮流获得固定时间片，时间片用完未完成就排到队尾。题目中同一时间时，先到达再排到队尾。对I/O型进程的奖励，使用优先级更高的附加队列。

  • HRRN（Highest Response Ratio Next / 高响应比优先）：根据“等待时间和运行时间的综合比例”选择进程，兼顾短作业优先和长作业不饥饿。这里似乎把响应假设为完成任务了。

  • 响应比=响应时间估计运行时间=等待时间+估计运行时间估计运行时间=1+作业等待时间估计运行时间\text{响应比} = \frac{\text{响应时间}}{\text{估计运行时间}} = \frac{\text{等待时间} + \text{估计运行时间}}{\text{估计运行时间}} = 1 + \frac{\text{作业等待时间}}{\text{估计运行时间}}

  • MQ（Multilevel Queue / 多级队列）：把进程固定分到不同优先级队列中，各队列可用不同算法，但队列之间优先级固定。

  • MFQ / MLFQ（Multilevel Feedback Queue / 多级反馈队列）：进程可在不同优先级队列间动态移动，短交互任务优先响应，长计算任务逐渐降级。（一次CPU burst）

Linux 的普通进程调度主要使用 CFS(Completely Fair Scheduler)，PPT第五章P64

多CPU：

同步：

临界区不能同时访问，解决方案：Peterson（两个进程、忙等，第六章Page19）、关中断、内存屏障、原子指令自旋锁、信号量、互斥锁、条件变量…

Test-and-Set（TAS）原子指令，Compare-and-Swap（CAS）原子指令，指令执行期间锁内存总线。

自旋锁spinlock：基于原子指令封装来。忙等，等的时间很小，保护简单的东西，本身撞上的概率就不大。 spin_lock() 只能防止调度切换，不能防止中断。 如果同一份临界资源可能被中断处理函数访问，就必须在拿锁时关本 CPU 中断，例如用* spin_lock_irq() 或更常用的 spin_lock_irqsave()。

原子变量有用自旋锁实现，但是是阻塞等待

信号量：标记资源有多少：结构体：资源数量和阻塞队列

互斥锁：类似于二元的信号量

用两个函数：增加资源个数P和减少资源个数V来操作，PV都是内核代码，实际要系统调用来使用

实现：临界区安全靠信号量，信号量安全靠自旋锁（保护变量），自旋锁安全靠特殊硬件指令

条件变量：信号量的变式，没有了信号量中的变量，只有一个队列，多了一个条件

同步实例：

PPT第7章写很清楚了，看一下就懂了

生产者消费者 读者写者 哲学家进餐

信号量集 SP(S1, t1, d1; S2, t2, d2; …; Sn, tn, dn)

死锁

必要条件：互斥（对于资源实例来说而不是一种资源来说）、占有并等待、非抢占、循环等待

处理方法：忽略（鸵鸟策略😆），预防，避免，检测死锁及解除

预防：破坏四个条件之一。互斥是本身属性不能破坏。 占有并等待，静态资源分配法，简单、安全且易于实现但可能出现饥饿。 非抢占，应用于状态可以保存和恢复的资源，如CPU寄存器、内存，对于大多数资源并不适用。 循环等待，有序资源分配法。反证法容易证明，在循环等待场景下，资源编号不可能单向持续递增。内核中多种资源依靠自旋锁，确会用有序资源分配法。不是对所有资源排序，仅涉及嵌套获取的自旋锁

避免：一类算法，在资源动态分配过程中，借助算法防止系统进入不安全状态，以避免死锁。针对特定年代，仅用于计算的计算机，现不适用。要求提供关于如何请求资源的额外信息。安全状态。银行家算法（Dijkstra，当用户申请一组资源时，系统必须确定这些资源的分配是否仍会使系统处于安全状态，如果是就可分配资源，否则等待）

检测：死锁定理：S为死锁状态的条件是当且仅当S状态的资源分配图是不可完全简化的。资源分配图简化法。

恢复：资源剥夺法，撤消进程法。

存储器管理

操作系统存储器管理：主存、高速缓存和寄存器，不包括磁盘。但从广义的存储器来说，磁盘当然也是存储器。

内存管理单元（MMU），运行时把虚拟地址映射到物理地址的电路，通常集成在CPU内

不记录old的技术了，见PPT第9章

动态分区分配策略：首次适应算法，循环首次适应算法（从上一次的位置下一个开始找），最佳适应算法，最坏适应算法

内部碎片：分配给作业，但未被作业利用的部分，固定分区分配会产生内部碎片 外部碎片：未分配，系统保留，但尺寸太小无法利用部分，动态分区分配会产生外部碎片 拼接（Compaction）：针对外部碎片，通过移动把多个分散的小分区拼接成一个大分区

伙伴系统

分页系统

将物理内存分为固定大小的块，称为帧（或称物理块、页框） 将逻辑内存也分成同样大小的块，称为页 最常见为4KB，也有更大的

分页系统中有碎片吗？没有外部碎片；进程的数据段、代码段、堆栈段等，总有末尾部分用不完，形成内部碎片。

每个进程有自己的页表，页表可被看作PCB的一部分，保存在物理内存中。

虚拟存储器

虚拟存储器是指具有请求调入和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统

物理块分配，见PPT第10章Page30

置换算法，见PPT第10章Page38

设备管理

磁盘

机械硬盘：柱面号，磁头号和扇区号；寻道时间，旋转延迟时间，传输时间；逻辑块寻址（LBA），传统的柱面-磁头-扇区的寻址方式称为CHS，出于兼容考虑仍被支持。 固态硬盘：基于闪存，需要擦取

磁盘调度（在磁盘层面上，有一堆要读取/写入的请求，谁先谁后）：

PPT11章Page11，主要是机械硬盘需要。最终FSCAN。

SSD 不需要像机械硬盘那样优化磁头移动，所以读请求可以简单按顺序处理；但写请求成本更复杂，因此会尽量合并相邻写请求来提高效率。

低格（低级格式化，划分扇区），高级格式化（分区+逻辑格式化aka创建文件系统）

Linux案例： NOOP，No Operation，请求按来的顺序排队，最多做一下相邻请求合并，常用于 SSD，尤其是 Linux 4.11 之前； None，内核不太干预，让 SSD 自己处理请求，Linux 4.11 之后常用于 SSD（现代 SSD 内部控制器已经很复杂，自己会做并行、重排、磨损均衡等优化，所以 Linux 内核层面不一定需要复杂调度）； Deadline，分读和写，读写都有一个LBA和一个FIFO，一般从LBA队列取请求，如果FIFO 队列前面的请求超时了，就优先处理超时请求； CFQ，Completely Fair Queuing，每个进程分配一个请求 FIFO 队列，时间片轮转，按照 I/O 优先级分类，Linux 4.11 之前常用于 HDD；

引导块： MBR+BIOS （= Master Boot Record + Basic Input/Output System = 主引导记录 + 基本输入输出系统） GPT+UEFI （= GUID Partition Table + Unified Extensible Firmware Interface = 全局唯一标识分区表 + 统一可扩展固件接口）

PPT11章Page31

硬件： 控制器：用控制寄存器、数据寄存器。 总线：系统总线（CPU可以直接控制），拓展总线。 轮询，中断，DMA，（I/O通道，现在已经不使用了，是一个别的ISA的小CPU，有执行程序的能力）

DMA，总线的一部分，外包了数据的搬运。以前是有限开放Memory给DMA，进一步开放成为IO通道那种。现在，硬盘控制器/USB控制器这些总线控制器，本身具备访问内存的能力，各种控制器在内存上有一块自己喜欢的数据结构。

应用接口：

设备驱动程序：设备驱动程序是 I/O 进程与设备控制器间的通信程序。统一的系统调用接口和设备的接口之间

上传下达。

系统调用的标准化封装

IO系统调用：阻塞(同步)，非阻塞（立刻返回已有的，无论够不够要求；需要程序再去问），异步（完成IO时通过一些变量、信号、软中断或回调函数传达给应用程序）

内核IO：

缓冲（这里的一个缓冲区是一个完整缓冲块，不能被同时读写），Spooling（Simultaneous Peripheral Operating On-Line，外部设备同时联机操作，又称假脱机操作），IO保护（特权指令、内存映射到内核部分）

文件管理

文件系统

文件结构：

保护：

内存映射文件： 普通 I/O 是“调用 read/write，把文件内容复制到用户缓冲区”；
mmap 是“把文件对应到进程虚拟地址，程序像访问内存一样访问文件”。

文件系统实现：

按层组织：I/O 控制层 基本文件系统层 文件组织模块层 逻辑文件系统层

分层文件系统

基本文件系统层：又称物理 I/O 层，向合适的设备驱动程序发送通用命令，处理内存和外存之间的数据块交换，关心数据块在外存和在缓冲区中的位置。简单来说，靠近IO系统的部分。

文件组织模块层：面向物理盘块。现代硬盘对外展示LBA，LBA是硬盘内部对CHS做了抽象。简单来说，管文件内的逻辑地址转换为LBA。

逻辑文件系统层：组织管理目录结构、文件夹、文件控制块（ FCB ）、权限控制等，有这些实例：

Windows: FAT32, exFAT, NTFS Linux: ext3, ext4, xfs, btrfs U盘常用FAT32/exFAT

文件系统在磁盘上的数据

用于文件系统管理的内存信息：

文件的盘块组织方式：连续分配、链接分配、索引分配 FAT：链接分配。分为FAT区（放每个块的下一个是谁，像链表一样，0表示空）、DIR(根目录)、DATA。 ext4：混合索引分配。分为数据块位图 block bitmap、inode位图 inode bitmap、inode表、数据。inode分为文件元数据（没有文件名，用inode编号。文件名在目录中，实现硬链接），索引，三级扩展索引。2号inode为根目录。 空间分配方式：静态分配、动态分配

空闲块管理：bitmap，链表。 改进：成组链接法，记录连续空闲区（这个好像没什么人用）

缓存：不是L1/L2 Cache那种。将读和写磁盘的操作先缓存到内存。统一缓存缓冲区，将内存映射的缓存和IO缓存统一在一起。LRU。

恢复： 事务：干就会全干。 基于日志的文件系统。崩溃就将日志重做一遍。保护的是文件系统，不是每一份文件。

其他：

Edit page
Next Post
Linux使用