↓ 跳过正文
DogDu’s blog
DogDu’s blog
  1. Posts/

复习操作系统

·4054 字·9 分钟
操作系统与系统 已完成 操作系统 复习
📖 阅读 -- 次
DogDu
作者
DogDu
工作结束或者累了, 要不休息一会, 看会动漫吧 ~
目录

这篇文章是一份操作系统复习提纲，主要面向课程回顾和面试快速查漏补缺，内容以知识点整理和图示记录为主。

参考视频：中山大学 OS

image-20250314110302993

操作系统结构
#

image-20250314113816249
image-20250314114956362
image-20250314120120032
image-20250314120544469
image-20250314142527874
image-20250314143216151
image-20250314143313378
image-20250314143403271
image-20250314143546894
image-20250314145255384
image-20250314145811970
image-20250314150359989
image-20250314163117766

硬件环境与软件抽象：特权模型与中断
#

image-20250314165750903
image-20250314165923300

虚拟内存管理
#

image-20250315104435568
image-20250315105156740

  • 以虚拟地址为核心进行内存管理
    #

image-20250315105608412
image-20250315110143568

分段虚拟内存
#

把虚拟地址切分成若干个大小的段。

  • 段表存储着分段信息，可供MMU查询
  • 虚拟地址分为：段号+段内偏移。
  • 段的大小不一
image-20250315110434956
image-20250315112205038

虽然外部碎片大，但是没有内部碎片

分页虚拟内存
#

image-20250315112456514
image-20250315112703790
image-20250315112941442
image-20250315114202127
image-20250315114343191
image-20250315114526843
image-20250315114646374
  • 紫色表示硬件
  • 蓝色表示物理地址
  • 红色表示虚拟地址
  • 分页虚拟内存没什么外部碎片，但是有一定的内部碎片。
  • 操作系统创建，操作系统管理，MMU查询
image-20250315115946928
image-20250315120410525
  • 因为页内偏移量是不需要的，这12bit是没有意义的。
  • 对于页表来说，高一些位默认是1111，或者0000，也是没有实际意义。
image-20250315120556805
  • 多级页表的设计是时间换空间是trade-off
  • 那可以使用MMU中的TLB来加速翻译的过程。

TLB：地址翻译加速
#

image-20250315120734343
image-20250315120841711
image-20250315172509378
  • 为了防止多个进程相互访问内存地址，必须对TLB进行刷新。
  • 不过可以设置一些条件。
image-20250315172629660
image-20250315172708504
  • 内核态的高 16 bit为111，非内核为 000
  • 内核态有自己的页表基址寄存器，与非内核态有隔离，所以从内核态到非内核态不需要刷新。
  • 对非内核态，使用高16位对进程进行标记。
image-20250315172944805

虚拟内存管理：拓展功能
#

image-20250316171228205

直接映射
#

image-20250316171518582
image-20250316171951910
  • 操作系统本身不需要复杂的页表。只是有一个自己的页表基址寄存器，简单相加即可。
  • 它只需要自己创建和维护一个地址即可，自己进行维护。
image-20250316172309257
image-20250316183828639
image-20250316184020594
image-20250316184120113
image-20250316184213004

立即映射
#

image-20250316184605596
  • mmap立刻映射。立刻分配物理地址。会出现在性能要求高的地方。
  • 但是需要在mmap中填写MAP_POPULATE参数，否则默认都是延迟映射
  • 栈空间的物理内存分配在发生栈溢出（访问未分配的栈地址）时触发，通过缺页中断处理。
image-20250316184658981

延迟映射
#

image-20250316184855646
image-20250316185457124
image-20250316185801199
  • 默认情况下，如果第一次访问地址都是延迟映射，触发缺页异常。

缺页异常
#

image-20250316190441628
image-20250316190451692
image-20250316190545017
image-20250316190618960

共享内存
#

image-20250316190726614
  • 共享内存存在权限操作，如果权限冲突。
  • 那么在写的时候会触发copy on write，之后触发重映射
image-20250316191247880
image-20250316191555107
image-20250316191655590

大页
#

image-20250316191953986
image-20250316192055682
image-20250316192457512

物理内存管理
#

image-20250316192717809

物理内存管理：伙伴系统
#

评价维度
#

image-20250316193514744
image-20250316193653523
  • 哈哈哈，malloc lab的经典 trade-off

基于位图的连续物理页分配。
#

image-20250316193802411
image-20250316193946999
  • 比较的时候可能可以使用 int64 的 & 操作，这样每次运算可以计算 64bit
  • C语言没有所谓的初始化操作，int a; 可能是五花八门的，但是C++有一个所谓的初始化，int a;八成是0。
  • 其他大小一致的以块/页划分的存储结构，可能存在一个类似 bitmap，比如文件系统，可能也是这样的结构。
  • 位图的效率低。
  • 这里给出的代码是物理地址连续的，但是实际上不一定是物理地址连续的，也就是连续的虚拟地址不一定是连续的物理地址。

伙伴系统
#

image-20250316194818828
  • 看到这个图，想到了csapp中说，现代的分配机制，总是倾向于把空闲块分配成少而大的空闲块，而不是多而小的空闲块。
image-20250316195225109
  • byd，这不就是malloc lab里面的显示链表法吗。
  • 分裂与合并，链表的创建，大小类的合并，最优最先匹配。。。。熟悉的知识。
  • 伙伴也就是说物理地址相邻的地址，说白了其实是一样的。
  • 在 4K 地址对齐之后，互为伙伴的块，只有1bit不同。

SLAB分配器家族（Linux）
#

image-20250316200535778

SLAB分配器

SLUB分配器

SLOB分配器

  • 伙伴系统分配的最小单位是一个物理页 4K。
  • 但是常用的结构体大小常常不大。 -> SLAB 分配器，快而小。
  • 避免过多的内部碎片。
image-20250316200818821
  • 设置一个特殊的大小的198字节再进一步进行精细分配。
image-20250316200930374
image-20250316201548712
  • SLAB表示这个数组
  • SLUB指这整个数据结构
  • 分配时
image-20250316201702244
image-20250316202029372
image-20250316202119809
image-20250316202144149
image-20250316202321076

物理内存管理：页替换
#

image-20250316202428438
image-20250316202919323
image-20250316203132434
image-20250316203324058
image-20250316203428634
image-20250316203521719
image-20250316203651676
  • 内存成为磁盘的缓存。
image-20250316203843797

页替换策略
#

image-20250316204426753
  • MIN策略：选择长时间内不会被访问的页进行踢出。
image-20250316204646255
  • 给 3 一次机会，如果之前已经再队列但是被访问过，那么队头加上一个标记。
image-20250316204842305
  • 经典LRU策略。
image-20250316205319156
  • 与LRU完全相反的对立，MRU策略。
image-20250316205352366
image-20250316205440614
image-20250316205500961

工作集模型（working set method）
#

在工作过程中，就对程序进行规范化，在前期进行一个管理，可能会有更优得效果。

working set method.

image-20250316205847605
image-20250316210017679
  • 和替换页策略不同。是另一种思路。

进程、线程与协程
#

image-20250316211343985

进程的诞生和概念
#

image-20250316212305183

  • 进程是任务的抽象。
    #

  • 进程是运行中的程序
    #

进程的状态
#

image-20250316212658699
image-20250316212840203

数据结构
#

image-20250316213023641
image-20250316213100091
image-20250316213242752
image-20250316213351649
image-20250316213639522

进程基本操作接口
#

  • CSAPP已经说尽了，除了 spawn，vfork，clone 没讲到。
    #

image-20250316213903337
image-20250316215053139

  • fork的时候，只有 fd 表一样，但是文件相关表不一样。
    #

image-20250316215157712
image-20250316215519564

  • 目的是为了方便管理进程
    #

image-20250316215705674
image-20250316215821788
image-20250316215902134
image-20250316220009121
  • 这个vfork有点像线程的创建，但是可能有点问题。
image-20250316220048103
image-20250316220118266

线程与协程
#

线程
#

image-20250317083311919
image-20250317083626111
image-20250317083719101
image-20250317083920888
image-20250317084154713
image-20250317084310497
image-20250317084338684
image-20250317084410104
image-20250317084426845
image-20250317084550531
image-20250317084636882
image-20250317084733756
image-20250317085016465
image-20250317090657932
image-20250317090800479
image-20250317090924436
image-20250317091041616
image-20250317091050231
image-20250317091114953
image-20250317091400594
  • 因为内核和线程也是一对一的，所以线程从t1切换到t2，需要内核栈也切换一次。

纤程（Fiber）、协程（Coroutine）
#

image-20250317092359180
image-20250317092525740
image-20250317092558176

  • 纤程的上下文切换有点像，setjmp 和 longjmp。只是给它封装了出来而已
    #

image-20250317093025127
  • 上面答案为C

  • 纤程是用户的库函数，由POSIX实现，不是系统调用
    #

  • setjmp 和 longjmp 也不是系统调用，是用户库函数。
    #

  • 区别：setjmp 和 longjmp 仅保存基本的执行上下文（程序计数器，栈指针），而纤程函数可以保存更完整的上下文（信号掩码，浮点数寄存器），支持更复杂的协程切换。
image-20250317093830353

  • 协程与纤程基本上是一个东西，协程是编程语言原生支持的纤程
    #

image-20250317093908387

处理器调度：单核调度策略
#

image-20250317100321104
image-20250317103816433
image-20250317103827931
image-20250317104030862
image-20250317104345321
image-20250317104609904

单核调度策略
#

经典调度策略
#

  • 先到先得（First Come First Served）
    • 优点：简单、直观
    • 缺点：队头阻塞，IO密集型任务不友好（因为频繁IO导致被挂起）。
  • 最短任务有限（Shortest Job First）
    • 优点：单位时间内任务吞吐量大、平均周转时间短。
    • 缺点：不公平、平均响应时间长、大任务饿死。
  • 抢占式调度（Preemptive Scheduling）
    • 非抢占式调度：前面一个任务完整之后再执行下一个。
    • 抢占式调度：执行一段时间之后，切换到下一个任务。而非执行至中指，通过定时触发时钟中断实现。如：最短完成时间任务优先。
  • 最短完成时间任务优先：
    • 优点：平均周转时间短、
    • 缺点：会打断正在运行的任务；可能不可得知完成时间。
  • 时间片轮转（Round Robin）
    • 优点：响应时间短、公平
    • 缺点：牺牲周转时间、平均响应时间短

优先级调度
#

  • 操作系统中任务分三六九等。

    • 系统VS用户、前台VS后台
    • 保证重要的任务被优先调度

  • 不同的调度策略隐藏对应的优先级确定方式

    image-20250317110934433

  • 优先级是会变化的。可以是动态的。

  • 维护多个优先级队列，高优先级的任务优先执行。同等优先级使用时间片轮转。

image-20250317111412562
  • 会因为IO的操作而导致CPU资源空闲。

  • 什么样的任务应该有高优先级？
    #

image-20250317112133355
image-20250317112308197
image-20250317112457752
image-20250317112658943
  • 保证优先级？保证高资源利用率？
image-20250317112753358

  • 多级反馈队列（Multi-Level Feedback Queue, MLFQ)
    #

image-20250317113324896

公平共享调度
#

image-20250317113601271
image-20250317113820613
  • 但是场景是多用户的，每个用户有若干任务。
image-20250317113948497
image-20250317114128525
image-20250317114308619
image-20250317114445885

image-20250317114536346
image-20250317114638901

image-20250317114845197
image-20250317114944689
  • 步幅调度的优点比起随机更加实际，更加接近比例。
image-20250317115042861
image-20250317115230362
image-20250317115501021
image-20250317115705462
image-20250317115806984
image-20250317120049842
image-20250317120522587

Deadline是第一生产力

image-20250317120652764

处理器调度：多核调度策略
#

image-20250317141259201
image-20250317141512336
image-20250317141714188
image-20250317142006045
image-20250317142156126
  • 如果在不同CPU上，会出现缓冲失效。
image-20250317142628980
  • 问题：任务之间有关联，频繁切换对缓存不友好
image-20250317142936592
  • 但两级调度问题是容易负载不均衡。
image-20250317143139356
image-20250317143500484
image-20250317143649221
image-20250317143759156
image-20250317143932350

进程间通信（IPC）
#

image-20250317145516635
image-20250317145605097
image-20250317145704966
image-20250317150013064
image-20250317150216694
image-20250317150313148
image-20250317150526657

共享内存通信
#

image-20250317150758939
image-20250317150927870
image-20250317151027426
image-20250317151143597

消息传递
#

image-20250317151418438
image-20250317151431299
image-20250317151755822

  • 谁收到算谁的。
    #

image-20250317151951321
image-20250317152123646
  • 同步异步的折中：超时机制，如果超时了，那么就走。
  • 先同步后异步。
image-20250317152433489

管道
#

image-20250317152601584
image-20250317152832660
image-20250317153147531

消息队列
#

image-20250317153256535
image-20250317153455271

image-20250317153721333
image-20250317153603621

同步原语：互斥锁
#

image-20250317183203477
image-20250317184346233
image-20250317185403229
  • 硬件无法处理。

解决数据竞争：

  • 申请标记
  • 有限处理
  • 标记消除

互斥锁
#

image-20250317185603178
image-20250317190149340
image-20250317190336392

原子操作
#

image-20250317190525978
  • 这需要硬件支持
image-20250317191518460
  • 能软件就软件，软件解决不了就硬件解决
image-20250317191757009
image-20250317191858717
image-20250317192108142
image-20250317192228562

互斥锁抽象
#

image-20250317193303537
image-20250317193633830

简单优化：排号自旋。

同步原语：条件变量与读写锁
#

image-20250317194558545
image-20250317195044504
  • C++ STL 中没有自旋锁，std::mutex 和 std::shared_mutex 都是睡眠唤醒模型的互斥锁。
  • 但是C++ STL提供了 std::atomic 可以提供 test_and_set() clear() 还有 load(), store() 来自己实现自旋锁。
image-20250317200903358
image-20250317201003476

  • 条件变量必须配合互斥锁使用。
    #

  • 通过在 while（condition）中填入条件来实现条件判断。
image-20250317201645572
image-20250317201839904
image-20250317202111359
image-20250317202224042

  • PV操作显示为POSIX实现的库函数，但是底层会调用系统调用。
    #

image-20250317202727702

读写锁
#

image-20250317203445719
  • 偏向读者：只要能读就让读者读，并发高，但是写者可能饿死。

C++中的std::shared_mutex的实现是基于一个 std::mutex 和 两个条件变量，条件变量用于写者等待和读者等待。

同步原语：死锁问题
#

image-20250317210219822
image-20250317210443862
image-20250317210848460
image-20250317210945536
  • 但是对于一个程序，不存在程序内的死锁，只存在因外部输入而导致的死锁应该是必须的吧。
  • 数据库怎么可能也怎么可以存在因自身代码导致死锁。
image-20250317211200318
image-20250317211307023

运行时死锁：死锁避免
#

银行家算法：

image-20250317211521610
image-20250317211754921
image-20250317211923803

活锁
#

image-20250317212402096

优先级反转
#

image-20250317212558368

基于 inode 的文件系统
#

image-20250318085037986
image-20250318085250600
image-20250318085556334
image-20250318085908051
image-20250318090233963
image-20250318090308409
image-20250318091040683
image-20250318090025293
  • 并没有减少指针数量。
image-20250318091826167
image-20250318092122062
image-20250318092342860
image-20250318090126450
image-20250318092700134
image-20250318092924346
image-20250318093342555
image-20250318093333503
image-20250318094112219
image-20250318094239851
image-20250318094450654
image-20250318094603664
image-20250318094850989

基于表的文件系统：FAT、NTFS
#

image-20250318095429367
image-20250318095656609
image-20250318095913076
image-20250318100045479
image-20250318100353636
image-20250318100452023

使用文件系统
#

image-20250318103522362
image-20250318103734313
  • 硬链接在目录的 inode 文件中存储的 inode 编号一样，只有文件名不同，操控文件的时候，会操控同样的 inode 也就是完全一样的文件。
  • 硬链接和原文件的地位一样，存在一个引用计数。删除一个硬链接或者源文件会是引用计数减一，直到为0才会删除。
  • windows中没有硬链接。
image-20250318104028300
image-20250318104456956
image-20250318105143782
image-20250318105539492

写回+写分配。

内存映射
#

image-20250318105751525
image-20250318105837820
image-20250318105907861

文件系统的高级功能
#

image-20250318110053993
image-20250318110326191

写时拷贝的作用：

image-20250318110434666

虚拟文件系统
#

image-20250318110801132
  • 可以共存多套文件系统
image-20250318111104646
image-20250318111240353
image-20250318111304586
image-20250318111453418

用户态文件系统
#

image-20250318111758347
image-20250318111943873

文件系统崩溃一致性：原子更新技术
#

image-20250318112819786
image-20250318113204549

  • 文件的建立以及操作是多步骤的，文件系统需要保证，要么都发生，要么都不发生，保证状态的一致性。
    #

image-20250318113407291
image-20250318113443920
image-20250318113534784
image-20250318113731734
image-20250318113906299
image-20250318114415065
  • 另一方面来说，操作系统不能像数据库一样，随意使用WAL。
image-20250318114533929
image-20250318114737348
image-20250318114819805
image-20250318114944176
image-20250318115209141
image-20250318115313518
image-20250318115353081
image-20250318115543922
image-20250318115653608
image-20250318115702787
image-20250318115900292
image-20250318120142828
image-20250318120508966
image-20250318120538921
image-20250318120717638
image-20250318160316987
image-20250318160403913
image-20250318160626055
  • 写时复制是时间优先，日志是空间优先。
image-20250318161143444
image-20250318161234531
image-20250318161355793

日志文件系统
#

image-20250318161520352

这不是 LSM 与 B+ 长久不衰之争嘛

image-20250318161634537

日志系统：合并，查找，写入缓存。

image-20250318162523496
image-20250318162905390
image-20250318165729210
image-20250318165938843
image-20250318170316690

设备管理：分类与交互
#

image-20250318170508328
image-20250318171937411
image-20250318172156069
image-20250318172456428
image-20250318172552564

设备与操作系统的交互
#

可编程IO（Programmable IO，PIO）

image-20250318173012669
image-20250318173226545

直接内存访问（Direct Memory Access，DMA）

image-20250318173553989
image-20250318173707266

设备管理：中断响应与驱动模型
#

image-20250318211747889
  • 操作系统的交互需要中断
image-20250318212202491
image-20250318212835439
image-20250318213016210
  • 因为硬中断会屏蔽中断，所以必须快速执行，可以把任务转交给软中断处理函数。
image-20250318213058431
image-20250318213253197
image-20250318213520165
image-20250318214521776
image-20250318214658597
image-20250318214902766
image-20250318215007816

系统虚拟化：CPU虚拟化
#

  • 装虚拟机的时候，虽然操作系统不一样，但是硬件架构还是要求相同的。
    #

image-20250319083503226
image-20250319083758107
image-20250319083938336
image-20250319084445042

image-20250319084719144
image-20250319084953794

image-20250319085253591
image-20250319085343955
image-20250319085411520
image-20250319085711186
image-20250319085912726
image-20250319090103329
image-20250319090253310
image-20250319090331078

image-20250319090443404
image-20250319090628085

image-20250319090653686
image-20250319091107349
image-20250319091205560
image-20250319091401468
image-20250319091453615

image-20250319091635923

image-20250319091906581

image-20250319092036690
image-20250319092237037
image-20250319092341167
image-20250319092441425

多核处理器：缓存一致性与内存一致性
#

image-20250319104349677
image-20250319103725835
  • 右边快得多。写操作导致每个CPU核的缓冲是不一样的，如果用char[64]分割开，那么在不同的缓冲行中，不会导致缓冲不一致，会很快。
  • 这是多核CPU中的缓冲不一致导致的。
image-20250319103903226

多核并发技巧：增加字段之间的字节填充，防止缓冲行伪共享。

image-20250319104550114
image-20250319104812663
image-20250319104855789

在临界区中缓冲不一致导致的缓冲失效，导致性能断崖。

image-20250319105230349
image-20250319105356226
image-20250319105553298
image-20250319105802052
image-20250319110025297
image-20250319110219153
image-20250319111131012

多核性能低下的原因
#

image-20250319111318379
image-20250319111414144

back-off等待避免单一缓冲行竞争。

image-20250319112508375

但是可能同时等待，。

解决方法：随机时间、指数回退。

但是仍然存在竞争，只是减轻了冲突的程度。

image-20250319112632930
image-20250319112847357

  • 通过一个链表的结点，节点在内存中不在同一缓冲行，不同的核等待不同的节点，实现解决竞争。
    #

image-20250319113134555
image-20250319113334405
image-20250319113517449
image-20250319113839471
image-20250319114954177
image-20250319115117316
image-20250319115452467
image-20250319115759737
  • 弱序一致性，可能需要编译器来保证。
image-20250319115841692
image-20250319115918888
image-20250319120056650

网络协议栈与系统实现：Linux
#

image-20250319185606181
image-20250319185738363
image-20250319190126493
image-20250319190458115
image-20250319190738332
  • sk_buff 里面都是指针，指向环形缓冲池，不会进行copy。
image-20250319191121179
image-20250319191515372

网络协议栈与系统实现：Intel DPDK
#

image-20250319193459306
image-20250319193633819
image-20250319193654846
image-20250319194031002
image-20250319194218449
image-20250319194335473

Intel DPDK软件优化方案
#

image-20250319194604972
image-20250319194741215
image-20250319194848623
image-20250319195024440
image-20250319195059385
image-20250319195219351

无锁环
#

image-20250319201018819
  • 特殊点是为了实现特性。
image-20250319201345489
image-20250319201432053
image-20250319201528819
image-20250319205813210

内存池
#

image-20250319205922790
image-20250319210415932