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-20250317114536346image-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-20250317153721333image-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-20250319084719144image-20250319084953794

image-20250319085253591

image-20250319085343955

image-20250319085411520

image-20250319085711186

image-20250319085912726

image-20250319090103329

image-20250319090253310

image-20250319090331078

image-20250319090443404image-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