操作系统-初见?见了好多次,次次都要学!

目录

操作系统

不是很难哦,好吧其实很难,结合Linux 学习。

学校的课程 ,大家听听就好,那一本书,是真的不够,也不好用,多找找资料,多看几遍。

一、硬件结构

复习,兄弟们看看就好。

历史是怎么发展

最开始是图灵机,大概长这个样子。

很原始的 0 1 操作,接下来看看 冯诺依曼模型

今天的电脑基本上还是大体是这个结构,是不是很棒。

内存,我们的程序和数据都是存储在内存,存储的区域是线性的。

中央处理器,也就是我们常说的 CPU,32 位和 64 位 CPU 最主要区别在于⼀次能计算多少字节数据。

常⻅的寄存器种类:

通⽤寄存器,⽤来存放需要进⾏运算的数据,⽐如需要进⾏加和运算的两个数据。

程序计数器,⽤来存储 CPU 要执⾏下⼀条指令「所在的内存地址」,注意不是存储了下⼀条要执⾏的指令,此时指令还在内存中,程序计数器只是存储了下⼀条指令的地址。

指令寄存器,⽤来存放程序计数器指向的指令,也就是指令本身,指令被执⾏完成之前,指令都存储在这⾥。

总线是⽤于 CPU 和内存以及其他设备之间的通信,总线可分为 3 种:

地址总线,⽤于指定 CPU 将要操作的内存地址;

数据总线,⽤于读写内存的数据;

控制总线,⽤于发送和接收信号,⽐如中断、设备复位等信号,CPU 收到信号后⾃然进⾏响应,这时也需要控制总线;

程序是怎么执行

底层会涉及到汇编语言以及各种机器的指令


现代⼤多数 CPU 都使⽤来流⽔线的⽅式来执⾏指令

所谓的流⽔线就是把⼀个任务拆分成多个⼩任务,于是⼀条指令通常分为 4 个阶段,称为 4 级流⽔线,

四个阶段的具体含义:

  1. CPU 通过程序计数器读取对应内存地址的指令,这个部分称为 Fetch(取得指令);
  2. CPU 对指令进⾏解码,这个部分称为 Decode(指令译码);
  3. CPU 执⾏指令,这个部分称为 Execution(执⾏指令);
  4. CPU 将计算结果存回寄存器或者将寄存器的值存⼊内存,这个部分称为 Store(数据回写);
    上⾯这 4 个阶段,我们称为指令周期(Instrution Cycle),CPU 的⼯作就是⼀个周期接着⼀个周期,周
    ⽽复始。

来一些小问题:

64 位相⽐ 32 位 CPU 的优势在哪吗?64 位 CPU 的计算性能⼀定⽐ 32 位 CPU ⾼很多吗?

64 位相⽐ 32 位 CPU 的优势主要体现在两个⽅⾯:

64 位 CPU 可以⼀次计算超过 32 位的数字,⽽ 32 位 CPU 如果要计算超过 32 位的数字,要分多步骤进⾏计算,效率就没那么⾼,

但是⼤部分应⽤程序很少会计算那么⼤的数字,所以只有运算⼤数字的时候,64 位 CPU 的优势才能体现出来,否则和 32 位 CPU 的计算性能相差不⼤。

64 位 CPU 可以寻址更⼤的内存空间,32 位 CPU 最⼤的寻址地址是 4G,即使你加了 8G ⼤⼩的内存,也还是只能寻址到 4G,⽽ 64 位 CPU 最⼤寻址地址是 2^64 ,远超于 32 位 CPU 最⼤寻址地址的 2^32 。

你知道软件的 32 位和 64 位之间的区别吗?再来 32 位的操作系统可以运⾏在 64 位的电脑上吗?64 位的操
作系统可以运⾏在 32 位的电脑上吗?如果不⾏,原因是什么?

64 位和 32 位软件,实际上代表指令是 64 位还是 32 位的:

如果 32 位指令在 64 位机器上执⾏,需要⼀套兼容机制,就可以做到兼容运⾏了。

但是如果 64 位指令在 32 位机器上执⾏,就⽐较困难了,因为 32 位的寄存器存不下 64 位的指令;

操作系统其实也是⼀种程序,我们也会看到操作系统会分成 32 位操作系统、64 位操作系统,

其代表意义就是操作系统中程序的指令是多少位,⽐如 64 位操作系统,指令也就是 64 位,因此不能装在32 位机器上。

总之,硬件的 64 位和 32 位指的是 CPU 的位宽,软件的 64 位和 32 位指的是指令的位宽。

存储器

CPU Cache

CPU Cache ⽤的是⼀种叫 SRAM(Static Random-Access Memory,静态随机存储器) 的芯⽚。

SRAM 之所以叫「静态」存储器,是因为只要有电,数据就可以保持存在,⽽⼀旦断电,数据就会丢失
了。

在 SRAM ⾥⾯,⼀个 bit 的数据,通常需要 6 个晶体管,所以 SRAM 的存储密度不⾼,同样的物理空间
下,能存储的数据是有限的,不过也因为 SRAM 的电路简单,所以访问速度⾮常快。

CPU 的⾼速缓存,通常可以分为 L1、L2、L3 这样的三层⾼速缓存,也称为⼀级缓存、⼆次缓存、三次缓
存。

CPU Cache 通常会分为 L1、L2、L3 三层,
其中 L1 Cache 通常分成「数据缓存」和「指令缓存」,
L1是距离 CPU 最近的,因此它⽐ L2、L3 的读写速度都快、存储空间都⼩。我们⼤脑中短期记忆,就好⽐
L1 Cache,⽽⻓期记忆就好⽐ L2/L3 Cache。

寄存器和 CPU Cache 都是在 CPU 内部,跟 CPU 挨着很近,因此它们的读写速度都相当的快,但是能存储的数据很少,毕竟 CPU 就这么丁点⼤。

再实际的开发中,我们的设计思想也是和计算机有着异曲同工之妙

一个内存地址怎么取到实际的内存值呢?

如何写出让 CPU 跑得更快的代码?

我们知道 CPU 访问内存的速度,⽐访问 CPU Cache 的速度慢了 100 多倍,

所以如果 CPU 所要操作的数据在 CPU Cache 中的话,这样将会带来很⼤的性能提升。访问的数据在 CPU Cache 中的话,

意味着缓存命中,缓存命中率越⾼的话,代码的性能就会越好,CPU 也就跑的越快。

于是,「如何写出让 CPU 跑得更快的代码?」这个问题,可以改成「如何写出 CPU 缓存命中率⾼的代码?」。

如何提升数据缓存的命中率?

看一个有趣的例子:

// 二维数组
array[N][N] = 0;
//形式
for(i=0;i<N;i+=1){
	for(j=0;j<N;j+=1){
		array[i][j] = 0;
	}
}
//形式二:
for(i=0;i<N;i+=1){
	for(j=0;j<N;j+=1){
		array[j][i] = 0;
	}
}
//就是  i  j  的位置互换了

结论:经过测试,形式⼀ array[i][j] 执⾏时间⽐形式⼆ array[j][i] 快好⼏倍。

为什么:第一种形式是和cpu的访问的顺序是一致的,访问第一个的时候会顺序将后面的加入到缓存,

但是后一种是跳跃的,如果数值比较大,就没有办法加入进去。

这跟 CPU Cache Line 有关,它表示 CPU Cache ⼀次性能加载数据的⼤⼩,可以在Linux ⾥通过 coherency_line_size 配置查看 它的⼤⼩,通常是 64 个字节。

因此,遇到这种遍历数组的情况时,按照内存布局顺序访问,将可以有效的利⽤ CPU Cache 带来的好处,这样我们代码的性能就会得到很⼤的提升,

如果提升多核 CPU 的缓存命中率?

在单核 CPU,虽然只能执⾏⼀个进程,

但是操作系统给每个进程分配了⼀个时间⽚,时间⽚⽤完了,就调度下⼀个进程,于是各个进程就按时间⽚交替地占⽤ CPU,从宏观上看起来各个进程同时在执⾏。

⽽现代 CPU 都是多核⼼的,进程可能在不同 CPU 核⼼来回切换执⾏,这对 CPU Cache 不是有利的,

虽然 L3 Cache 是多核⼼之间共享的,但是 L1 和 L2 Cache 都是每个核⼼独有的,

如果⼀个进程在不同核⼼来回切换,各个核⼼的缓存命中率就会受到影响,相反如果进程都在同⼀个核⼼上执⾏,

那么其数据的 L1和 L2 Cache 的缓存命中率可以得到有效提⾼,缓存命中率⾼就意味着 CPU 可以减少访问 内存的频率。

当有多个同时执⾏「计算密集型」的线程,为了防⽌因为切换到不同的核⼼,⽽导致缓存命中率下降的问题,

我们可以把线程绑定在某⼀个 CPU 核⼼上,这样性能可以得到⾮常可观的提升。

在 Linux 上提供了 sched_setaffinity ⽅法,来实现将线程绑定到某个 CPU 核⼼这⼀功能。

CPU 缓存⼀致性

CPU Cache 的结构,CPU Cache 是由很多个 Cache Line 组成的,CPU Line 是 CPU

从内存读取数据的基本单位,⽽ CPU Line 是由各种标志(Tag)+ 数据块(Data Block)组成。

我们当然期望 CPU 读取数据的时候,都是尽可能地从 CPU Cache 中读取,⽽不是每⼀次都要从内存中获
取数据。

所以,身为程序员,我们要尽可能写出缓存命中率⾼的代码,这样就有效提⾼程序的性能。

什么时机才把 Cache 中的数据写回到内存呢?

  • 写直达(Write Through)
  • 写回(Write Back)

写直达

保持内存与 Cache ⼀致性最简单的⽅式是,把数据同时写⼊内存和 Cache 中,这种⽅法称为写直达(Write Through)。

写直达法很直观,也很简单,但是问题明显,⽆论数据在不在 Cache ⾥⾯,每次写操作都会写回到内存,这样写操作将会花费⼤量的时间,⽆疑性能会受到很⼤的影响。

写回

既然写直达由于每次写操作都会把数据写回到内存,⽽导致影响性能,于是为了要减少数据写回内存的频率,就出现了写回(Write Back)的⽅法。

在写回机制中,当发⽣写操作时,新的数据仅仅被写⼊ Cache Block ⾥,只有当修改过的 Cache Block「被替换」时才需要写到内存中,减少了数据写回内存的频率,这样便可以提⾼系统的性能。

缓存⼀致性问题

现在 CPU 都是多核的,由于 L1/L2 Cache 是多个核⼼各⾃独有的,那么会带来多核⼼的缓存⼀致性(Cache Coherence) 的问题,如果不能保证缓存⼀致性的问题,就可能造成结果错误。

  • 第⼀点,某个 CPU 核⼼⾥的 Cache 数据更新时,必须要传播到其他核⼼的 Cache,这个称为写传播(Wreite Propagation);
  • 第⼆点,某个 CPU 核⼼⾥对数据的操作顺序,必须在其他核⼼看起来顺序是⼀样的,这个称为事务的串形化(Transaction Serialization)

总线嗅探

写传播的原则就是当某个 CPU 核⼼更新了 Cache 中的数据,要把该事件⼴播通知到其他核⼼。

最常⻅实现的⽅式是总线嗅探(Bus Snooping)。

我还是以前⾯的 i 变量例⼦来说明总线嗅探的⼯作机制,当 A 号 CPU 核⼼修改了 L1 Cache 中 i 变量的值,

通过总线把这个事件⼴播通知给其他所有的核⼼,然后每个 CPU 核⼼都会监听总线上的⼴播事件,

并检查是否有相同的数据在⾃⼰的 L1 Cache ⾥⾯,如果 B 号 CPU 核⼼的 L1 Cache 中有该数据,

那么也需要把该数据更新到⾃⼰的 L1 Cache。

可以发现,总线嗅探⽅法很简单, CPU 需要每时每刻监听总线上的⼀切活动,但是不管别的核⼼的Cache 是否缓存相同的数据,都需要发出⼀个⼴播事件,这⽆疑会加重总线的负载。

另外,总线嗅探只是保证了某个 CPU 核⼼的 Cache 更新数据这个事件能被其他 CPU 核⼼知道,但是并不能保证事务串形化。

于是,有⼀个协议基于总线嗅探机制实现了事务串形化,也⽤状态机机制降低了总线带宽压⼒,这个协议就是 MESI 协议,这个协议就做到了 CPU 缓存⼀致性。

MESI 协议

MESI 协议其实是 4 个状态单词的开头字⺟缩写,分别是:

Modified,已修改

Exclusive,独占

Shared,共享

Invalidated,已失效

这四个状态来标记 Cache Line 四个不同的状态。

状态 描述
M(Modified) 代表该缓存行中的内容被修改了,并且该缓存行只被缓存在该CPU中。这个状态的缓存行中的数据和内存中的不一样,在未来的某个时刻它会被写入到内存中(当其他CPU要读取该缓存行的内容时。或者其他CPU要修改该缓存对应的内存中的内容时
E(Exclusive) 代表该缓存行对应内存中的内容只被该CPU缓存,其他CPU没有缓存该缓存对应内存行中的内容。这个状态的缓存行中的内容和内存中的内容一致。该缓存可以在任何其他CPU读取该缓存对应内存中的内容时变成S状态。或者本地处理器写该缓存就会变成M状态
S(Shared) 该状态意味着数据不止存在本地CPU缓存中,还存在别的CPU的缓存中。这个状态的数据和内存中的数据是一致的。当其他CPU修改该缓存行对应的内存的内容时会使该缓存行变成 I 状态
I(Invalid) 代表该缓存行中的内容是无效的

CPU 是如何执⾏任务的?

CPU 从内存中读取数据到 Cache 的时候,并不是⼀个字节⼀个字节读取,⽽是⼀块⼀块的⽅式来读取数据的,

这⼀块⼀块的数据被称为 CPU Line(缓存⾏),所以 CPU Line 是 CPU 从内存读取数据到 Cache的单位。

Cache 伪共享是什么?⼜如何避免这个问题?

可以发现如果 1 号和 2 号 CPU 核⼼这样持续交替的分别修改变量 A 和 B,就会重复 ”变为失效状态“ 和 ”变为修改状态“ 这两个步骤,

Cache 并没有起到缓存的效果,虽然变量 A 和 B 之间其实并没有任何的关系,但是因为同时归属于⼀个 Cache Line ,

这个 Cache Line 中的任意数据被修改后,都会相互影响,从⽽出现 这两个步骤。

因此,这种因为多个线程同时读写同⼀个 Cache Line 的不同变量时,⽽导致 CPU Cache 失效的现象称为伪共享(False Sharing)。

避免伪共享的⽅法

在 Linux 内核中存在 __cacheline_aligned_in_smp 宏定义,是⽤于解决伪共享的问题。

  • 如果在多核(MP)系统⾥,该宏定义是 __cacheline_aligned ,也就是 Cache Line 的⼤⼩;
  • ⽽如果在单核系统⾥,该宏定义是空的;

为了防⽌前⾯提到的 Cache 伪共享问题,我们可以使⽤上⾯介绍的宏定义,将 b 的地址设置为Cache Line 对⻬地址。

所以,避免 Cache 伪共享实际上是⽤空间换时间的思想,浪费⼀部分 Cache 空间,从⽽换来性能的提升。

我们再来看⼀个应⽤层⾯的规避⽅案,

有⼀个 Java 并发框架 Disruptor 使⽤「字节填充 + 继承」的⽅式,来避免伪共享的问题。

Disruptor 中有⼀个 RingBuffer 类会经常被多个线程使⽤,代码如下:

CPU Cache 从内存读取数据的单位是 CPU Line,⼀般 64 位 CPU 的 CPU Line 的⼤⼩是 64个字节,

⼀个 long 类型的数据是 8 个字节,所以 CPU ⼀下会加载 8 个 long 类型的数据。

根据 JVM 对象继承关系中⽗类成员和⼦类成员,内存地址是连续排列布局的,

因此 RingBufferPad 中的 7个 long 类型数据作为 Cache Line 前置填充,⽽ RingBuffer 中的 7 个 long 类型数据则作为 Cache Line 后置填充,

这 14 个 long 变量没有任何实际⽤途,更不会对它们进⾏读写操作。

另外,RingBufferFelds ⾥⾯定义的这些变量都是 final 修饰的,意味着第⼀次加载之后不会再修改, ⼜由于「前后」各填充了 7 个不会被读写的 long 类型变量,所以⽆论怎么加载 Cache Line,

这整个 CacheLine ⾥都没有会发⽣更新操作的数据,于是只要数据被频繁地读取访问,就⾃然没有数据被换出 Cache的可能,也因此不会产⽣伪共享的问题。

CPU 如何选择线程的?

⼀般来说,没有创建线程的进程,是只有单个执⾏流,它被称为是主线程。

如果想让进程处理更多的事情,可以创建多个线程分别去处理,但不管怎么样,它们对应到内核⾥都是 tark_struct 。

所以,Linux 内核⾥的调度器,调度的对象就是 tark_struct ,接下来我们就把这个数据结构统称为任务。

在 Linux 系统中,根据任务的优先级以及响应要求,主要分为两种,其中优先级的数值越⼩,优先级越⾼:

  • 实时任务,对系统的响应时间要求很⾼,也就是要尽可能快的执⾏实时任务,优先级在 0~99 范围内的就算实时任务;
  • 普通任务,响应时间没有很⾼的要求,优先级在 100~139 范围内都是普通任务级别;

调度类

由于任务有优先级之分,Linux 系统为了保障⾼优先级的任务能够尽可能早的被执⾏,于是分为了这⼏种调度类。

Deadline 和 Realtime 这两个调度类,都是应⽤于实时任务的,这两个调度类的调度策略合起来共有这三种,它们的作⽤如下:

  • SCHED_DEADLINE:是按照 deadline 进⾏调度的,距离当前时间点最近的 deadline 的任务会被优先调度;
  • SCHED_FIFO:对于相同优先级的任务,按先来先服务的原则,但是优先级更⾼的任务,可以抢占低优先级的任务,也就是优先级⾼的可以「插队」;
  • SCHED_RR:对于相同优先级的任务,轮流着运⾏,每个任务都有⼀定的时间⽚,当⽤完时间⽚的任务会被放到队列尾部,以保证相同优先级任务的公平性,但是⾼优先级的任务依然可以抢占低优先级的任务;

⽽ Fair 调度类是应⽤于普通任务,都是由 CFS 调度器管理的,分为两种调度策略:

  • SCHED_NORMAL:普通任务使⽤的调度策略;
  • SCHED_BATCH:后台任务的调度策略,不和终端进⾏交互,因此在不影响其他需要交互的任务,可以适当降低它的优先级。

完全公平调度

我们平⽇⾥遇到的基本都是普通任务,对于普通任务来说,公平性最重要,在 Linux ⾥⾯,实现了⼀个基于 CFS 的调度算法,也就是完全公平调度(Completely Fair Scheduling)。

这个算法的理念是想让分配给每个任务的 CPU 时间是⼀样,于是它为每个任务安排⼀个虚拟运⾏时间vruntime,

如果⼀个任务在运⾏,其运⾏的越久,该任务的 vruntime ⾃然就会越⼤,⽽没有被运⾏的任务,vruntime 是不会变化的。

那么,在 CFS 算法调度的时候,会优先选择 vruntime 少的任务,以保证每个任务的公平性。

虚拟运行时间 vruntime += 实际运行时间 delta_ exec * NICE_ 0_ LOAD / 权重

CPU 运⾏队列

⼀个系统通常都会运⾏着很多任务,多任务的数量基本都是远超 CPU 核⼼数量,因此这时候就需要排队。

事实上,每个 CPU 都有⾃⼰的运⾏队列(Run Queue, rq),⽤于描述在此 CPU 上所运⾏的所有进程,

其队列包含三个运⾏队列,Deadline 运⾏队列 dl_rq实时任务运⾏队列 rt_rqCFS 运⾏队列 csf_rq

其中 csf_rq 是⽤红⿊树来描述的,按 vruntime ⼤⼩来排序的,最左侧的叶⼦节点,就是下次会被调度的任务。

这⼏种调度类是有优先级的,优先级如下:Deadline > Realtime > Fair。

因此,实时任务总是会⽐普通任务优先被执⾏

调整优先级

可以调整任务的 nice 值,从⽽让优先级⾼⼀些的任务执⾏

更多时间。nice 的值能设置的范围是 -20~19 , 值越低,表明优先级越⾼,因此 -20 是最⾼优先级,19则是最低优先级,默认优先级是 0。

软中断

Linux 系统为了解决中断处理程序执⾏过⻓和中断丢失的问题,将中断过程分成了两个阶段,分别是「上半部和下半部分」。

  • 上半部⽤来快速处理中断,⼀般会暂时关闭中断请求,主要负责处理跟硬件紧密相关或者时间敏感的事情。
    • 上半部直接处理硬件请求,也就是硬中断,主要是负责耗时短的⼯作,特点是快速执⾏;
  • 下半部⽤来延迟处理上半部未完成的⼯作,⼀般以「内核线程」的⽅式运⾏。
    • 下半部是由内核触发,也就说软中断,主要是负责上半部未完成的⼯作,通常都是耗时⽐较⻓的事情,特点是延迟执⾏;

在 Linux 系统⾥,我们可以通过查看 /proc/softirqs 的 内容来知晓「软中断」的运⾏情况,以及/proc/interrupts 的 内容来知晓「硬中断」的运⾏情况。

要想知道当前的系统的软中断情况,我们可以使⽤ top 命令查看。

一般对于⽹络 I/O ⽐较⾼的 Web 服务器, NET_RX ⽹络接收中断的变化速率相⽐其他中断类型快很多。

如果发现 NET_RX ⽹络接收中断次数的变化速率过快,接下⾥就可以使⽤ sar -n DEV 查看⽹卡的⽹络包接收速率情况,然后分析是哪个⽹卡有⼤量的⽹络包进来。

接着,在通过 tcpdump 抓包,分析这些包的来源,如果是⾮法的地址,可以考虑加防⽕墙,如果是正常流量,则要考虑硬件升级等。

有意思的问题

为什么 0.1 + 0.2 不等于 0.3 ?

不是的,0.1 和 0.2 这两个数字⽤⼆进制表达会是⼀个⼀直循环的⼆进制数,

⽐如 0.1 的⼆进制表示为 0.00011 0011 0011… (0011 ⽆限循环),对于计算机⽽⾔,0.1 ⽆法精确表达,这是浮点数计算造成精度损失的根源。

因此,IEEE 754 标准定义的浮点数只能根据精度舍⼊,然后⽤「近似值」来表示该⼆进制,那么意味着计算机存放的⼩数可能不是⼀个真实值。

0.1 + 0.2 并不等于完整的 0.3,

这主要是因为这两个⼩数⽆法⽤「完整」的⼆进制来表示,只能根据精度舍⼊,

所以计算机⾥只能采⽤近似数的⽅式来保存,那两个近似数相加,得到的必然也是⼀个近似数。

二、操作系统结构

Linux 内核 vs Windows 内核

Windows 和 Linux 可以说是我们⽐较常⻅的两款操作系统的。

Windows 基本占领了电脑时代的市场,商业上取得了很⼤成就,但是它并不开源,所以要想接触源码得加⼊ Windows 的开发团队中。

对于服务器使⽤的操作系统基本上都是 Linux,⽽且内核源码也是开源的,任何⼈都可以下载,并增加⾃⼰的改动或功能,Linux 最⼤的魅⼒在于,全世界有⾮常多的技术⼤佬为它贡献代码。

这两个操作系统各有千秋,不分伯仲。

内核

计算机是由各种外部硬件设备组成的,⽐如内存、cpu、硬盘等,如果每个应⽤都要和这些硬件设备对接通信协议,

那这样太累了,所以这个中间⼈就由内核来负责,

让内核作为应⽤连接硬件设备的桥梁,应⽤程序只需关⼼与内核交互,不⽤关⼼硬件的细节。

内核有哪些能⼒呢?

现代操作系统,内核⼀般会提供 4 个基本能⼒:

  • 管理进程、线程,决定哪个进程、线程使⽤ CPU,也就是进程调度的能⼒;
  • 管理内存,决定内存的分配和回收,也就是内存管理的能⼒;
  • 管理硬件设备,为进程与硬件设备之间提供通信能⼒,也就是硬件通信能⼒;
  • 提供系统调⽤,如果应⽤程序要运⾏更⾼权限运⾏的服务,那么就需要有系统调⽤,它是⽤户程序与操作系统之间的接⼝。

内核是怎么⼯作的?

  • 内核具有很⾼的权限,可以控制 cpu、内存、硬盘等硬件,⽽应⽤程序具有的权限很⼩,因此⼤多数操作系统,把内存分成了两个区域:
    • 内核空间,这个内存空间只有内核程序可以访问;
    • ⽤户空间,这个内存空间专⻔给应⽤程序使⽤;

Linux 的设计

Linux 的开⼭始祖是来⾃⼀位名叫 Linus Torvalds 的芬兰⼩伙⼦,他在 1991 年⽤ C 语⾔写出了第⼀版的Linux 操作系统,那年他 22 岁

完成第⼀版 Linux 后,Linux Torvalds 就在⽹络上发布了 Linux 内核的源代码,每个⼈都可以免费下载和使⽤。

Linux 内核设计的理念主要有这⼏个点:

  • MutiTask,多任务
  • SMP,对称多处理
  • ELF,可执⾏⽂件链接格式
  • Monolithic Kernel,宏内核
与宏内核相反的是微内核,微内核架构的内核只保留最基本的能⼒,

⽐如进程调度、虚拟机内存、中断等,把⼀些应⽤放到了⽤户空间,⽐如驱动程序、⽂件系统等。

这样服务与服务之间是隔离的,单个服务出现故障或者完全攻击,也不会导致整个操作系统挂掉,提⾼了操作系统的稳定性和可靠性。

微内核内核功能少,可移植性⾼,
相⽐宏内核有⼀点不好的地⽅在于,由于驱动程序不在内核中,⽽且驱动程序⼀般会频繁调⽤底层能⼒的,于是驱动和硬件设备交互就需要频繁切换到内核态,这样会带来性能损耗。

华为的鸿蒙操作系统的内核架构就是微内核。

还有⼀种内核叫混合类型内核,它的架构有点像微内核,内核⾥⾯会有⼀个最⼩版本的内核,

然后其他模块会在这个基础上搭建,然后实现的时候会跟宏内核类似,也就是把整个内核做成⼀个完整的程序,

⼤部分服务都在内核中,这就像是宏内核的⽅式包裹着⼀个微内核。

Windows 设计

当今 Windows 7、Windows 10 使⽤的内核叫 Windows NT,NT 全称叫 New Technology。

下图是 Windows NT 的结构图⽚:

Windows 和 Linux ⼀样,同样⽀持 MutiTask 和 SMP,

但不同的是,Window 的内核设计是混合型内核,

在上图你可以看到内核中有⼀个 MicroKernel 模块,这个就是最⼩版本的内核,⽽整个内核实现是⼀个完整的程序,含有⾮常多模块。

三、内存管理

操作系统会提供⼀种机制,将不同进程的虚拟地址和不同内存的物理地址映射起来。

如果程序要访问虚拟地址的时候,由操作系统转换成不同的物理地址,这样不同的进程运⾏的时候,写⼊的是不同的物理地址,这样就不会冲突了。

于是,这⾥就引出了两种地址的概念:

  • 我们程序所使⽤的内存地址叫做虚拟内存地址(Virtual Memory Address)、
  • 实际存在硬件⾥⾯的空间地址叫物理内存地址(Physical Memory Address)。

主要有两种⽅式,分别是内存分段和内存分⻚

内存分段

程序是由若⼲个逻辑分段组成的,

如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的,所以就⽤分段(Segmentation)的形式把这些段分离出来。

虚拟地址是通过段表与物理地址进⾏映射

分段的办法很好,解决了程序本身不需要关⼼具体的物理内存地址的问题,但它也有⼀些不⾜之处:

  • 第⼀个就是内存碎⽚的问题。
  • 第⼆个就是内存交换的效率低的问题。
    • 如果内存交换的时候,交换的是⼀个占内存空间很⼤的程序,这样整个机器都会显得卡顿。

为了解决内存分段的内存碎⽚和内存交换效率低的问题,就出现了内存分⻚。

内存分⻚

分段的好处就是能产⽣连续的内存空间,但是会出现内存碎⽚和内存交换的空间太⼤的问题。

要解决这些问题,那么就要想出能少出现⼀些内存碎⽚的办法。

另外,当需要进⾏内存交换的时候,让需要交换写⼊或者从磁盘装载的数据更少⼀点,这样就可以解决问题了。这个办法,也就是内存分⻚(Paging)。

分⻚是把整个虚拟和物理内存空间切成⼀段段固定尺⼨的⼤⼩。

这样⼀个连续并且尺⼨固定的内存空间,我们叫⻚(Page)。在 Linux 下,每⼀⻚的⼤⼩为 4KB 。

⽽当进程访问的虚拟地址在⻚表中查不到时,系统会产⽣⼀个缺⻚异常,

进⼊系统内核空间分配物理内存、更新进程⻚表,最后再返回⽤户空间,恢复进程的运⾏。

分⻚是怎么解决分段的内存碎⽚、内存交换效率低的问题?

由于内存空间都是预先划分好的,也就不会像分段会产⽣间隙⾮常⼩的内存,

这正是分段会产⽣内存碎⽚的原因。

⽽采⽤了分⻚,那么释放的内存都是以⻚为单位释放的,也就不会产⽣⽆法给进程使⽤的⼩内存。

如果内存空间不够,操作系统会把其他正在运⾏的进程中的「最近没被使⽤」的内存⻚⾯给释放掉,

也就是暂时写在硬盘上,称为换出(Swap Out)。

⼀旦需要的时候,再加载进来,称为换⼊(Swap In)。

所以,⼀次性写⼊磁盘的也只有少数的⼀个⻚或者⼏个⻚,不会花太多时间,内存交换的效率就相对⽐较⾼。

更进⼀步地,分⻚的⽅式使得我们在加载程序的时候,不再需要⼀次性都把程序加载到物理内存中。

我们完全可以在进⾏虚拟内存和物理内存的⻚之间的映射之后,并不真的把⻚加载到物理内存⾥,

⽽是只有在程序运⾏中,需要⽤到对应虚拟内存⻚⾥⾯的指令和数据时,再加载到物理内存⾥⾯去。

分⻚机制下,虚拟地址和物理地址是如何映射的?

在分⻚机制下,虚拟地址分为两部分,⻚号和⻚内偏移。⻚号作为⻚表的索引,

⻚表包含物理⻚每⻚所在物理内存的基地址,这个基地址与⻚内偏移的组合就形成了物理内存地址。

总结⼀下,对于⼀个内存地址转换,其实就是这样三个步骤:

  • 把虚拟内存地址,切分成⻚号和偏移量;
  • 根据⻚号,从⻚表⾥⾯,查询对应的物理⻚号;
  • 直接拿物理⻚号,加上前⾯的偏移量,就得到了物理内存地址。

但是,就这样简单的分页是会有不少问题的,所以啊,我们又引入了多级页表的概念。

多级⻚表

对于 64 位的系统,两级分⻚肯定不够了,就变成了四级⽬录,分别是:

  • 全局⻚⽬录项 PGD(Page Global Directory);
  • 上层⻚⽬录项 PUD(Page Upper Directory);
  • 中间⻚⽬录项 PMD(Page Middle Directory);
  • ⻚表项 PTE(Page Table Entry);

TLB

多级⻚表虽然解决了空间上的问题,但是虚拟地址到物理地址的转换就多了⼏道转换的⼯序,

这显然就降低了这俩地址转换的速度,也就是带来了时间上的开销。

程序是有局部性的,即在⼀段时间内,整个程序的执⾏仅限于程序中的某⼀部分。

相应地,执⾏所访问的存储空间也局限于某个内存区域。

我们就可以利⽤这⼀特性,把最常访问的⼏个⻚表项存储到访问速度更快的硬件,

于是计算机科学家们,就在 CPU 芯⽚中,加⼊了⼀个专⻔存放程序最常访问的⻚表项的 Cache,

这个 Cache 就是 TLB(Translation Lookaside Buffer) ,通常称为⻚表缓存、转址旁路缓存、快表等。

在 CPU 芯⽚⾥⾯,封装了内存管理单元(Memory Management Unit)芯⽚,它⽤来完成地址转换和 TLB的访问与交互。

有了 TLB 后,那么 CPU 在寻址时,会先查 TLB,如果没找到,才会继续查常规的⻚表。

TLB 的命中率其实是很⾼的,因为程序最常访问的⻚就那么⼏个。

段⻚式内存管理

内存分段和内存分⻚并不是对⽴的,它们是可以组合起来在同⼀个系统中使⽤的,

那么组合起来后,通常称为段⻚式内存管理。

段⻚式地址变换中要得到物理地址须经过三次内存访问:

  • 第⼀次访问段表,得到⻚表起始地址;
  • 第⼆次访问⻚表,得到物理⻚号;
  • 第三次将物理⻚号与⻚内位移组合,得到物理地址。

可⽤软、硬件相结合的⽅法实现段⻚式地址变换,这样虽然增加了硬件成本和系统开销,但提⾼了内存的利⽤率。

Linux 内存管理

Intel 处理器的发展历史

早期 Intel 的处理器从 80286 开始使⽤的是段式内存管理。

但是很快发现,光有段式内存管理⽽没有⻚式内存管理是不够的,这会使它的 X86 系列会失去市场的竞争⼒。

因此,在不久以后的 80386 中就实现了对⻚式内存管理。

也就是说,80386 除了完成并完善从 80286 开始的段式内存管理的同时还实现了⻚式内存管理。

但是这个 80386 的⻚式内存管理设计时,没有绕开段式内存管理,⽽是建⽴在段式内存管理的基础上,

这就意味着,⻚式内存管理的作⽤是在由段式内存管理所映射⽽成的地址上再加上⼀层地址映射。

由于此时由段式内存管理映射⽽成的地址不再是“物理地址”了,

Intel 就称之为“线性地址”(也称虚拟地址)。

于是,段式内存管理先将逻辑地址映射成线性地址,然后再由⻚式内存管理将线性地址映射成物理地址。

这⾥说明下逻辑地址和线性地址:

  • 程序所使⽤的地址,通常是没被段式内存管理映射的地址,称为逻辑地址;
  • 通过段式内存管理映射的地址,称为线性地址,也叫虚拟地址;

逻辑地址是「段式内存管理」转换前的地址,线性地址则是「⻚式内存管理」转换前的地址。

Linux 内存

Linux 内存主要采⽤的是⻚式内存管理,但同时也不可避免地涉及了段机制。

这主要是上⾯ Intel 处理器发展历史导致的,因为 Intel X86 CPU ⼀律对程序中使⽤的地址先进⾏段式映射,

然后才能进⾏⻚式映射。

既然 CPU 的硬件结构是这样,Linux 内核也只好服从 Intel 的选择。

但是事实上,Linux 内核所采取的办法是使段式映射的过程实际上不起什么作⽤。

也就是说,“上有政策,下有对策”,若惹不起就躲着⾛。

Linux 系统中的每个段都是从 0 地址开始的整个 4GB 虚拟空间(32 位环境下),

也就是所有的段的起始地址都是⼀样的。

这意味着,Linux 系统中的代码,包括操作系统本身的代码和应⽤程序代码,

所⾯对的地址空间都是线性地址空间(虚拟地址),这种做法相当于屏蔽了处理器中的逻辑地址概念,段只被⽤于
访问控制和内存保护。

Linux 操作系统中,虚拟地址空间的内部⼜被分为内核空间和⽤户空间两部分,

不同位数的系统,地址空间的范围也不同。

⽐如最常⻅的 32 位和 64 位系统,如下所示:

虽然每个进程都各⾃有独⽴的虚拟内存,但是每个虚拟内存中的内核地址,其实关联的都是相同的物理内存。

这样,进程切换到内核态后,就可以很⽅便地访问内核空间内存。


通过这张图你可以看到,⽤户空间内存,从低到⾼分别是 7 种不同的内存段:

  • 程序⽂件段,包括⼆进制可执⾏代码;

  • 已初始化数据段,包括静态常量;

  • 未初始化数据段,包括未初始化的静态变量;

  • 堆段,包括动态分配的内存,从低地址开始向上增⻓;

  • ⽂件映射段,包括动态库、共享内存等,从低地址开始向上增⻓(跟硬件和内核版本有关);

  • 栈段,包括局部变量和函数调⽤的上下⽂等。栈的⼤⼩是固定的,⼀般是 8 MB 。

    当然系统也提供了参数,以便我们⾃定义⼤⼩;

在这 7 个内存段中,堆和⽂件映射段的内存是动态分配的。

⽐如说,使⽤ C 标准库的 malloc() 或者mmap() ,就可以分别在堆和⽂件映射段动态分配内存。

进程与线程

进程

我们编写的代码只是⼀个存储在硬盘的静态⽂件,通过编译后就会⽣成⼆进制可执⾏⽂件,

当我们运⾏这个可执⾏⽂件后,它会被装载到内存中,接着 CPU 会执⾏程序中的每⼀条指令,

那么这个运⾏中的程序,就被称为「进程」(Process)。

但是呢,你想,硬盘读取东西的速度太慢了,

所以,当进程要从硬盘读取数据时,CPU 不需要阻塞等待数据的返回,⽽是去执⾏另外的进程。

当硬盘数据返回时,CPU 会收到个中断,于是 CPU 再继续运⾏这个进程。

这种多个程序、交替执⾏的思想,虽然单核的 CPU 在某⼀个瞬间,只能运⾏⼀个进程。但在 1 秒钟期间,

它可能会运⾏多个进程,这样就产⽣并⾏的错觉,实际上这是并发。


进程的状态

如果有⼤量处于阻塞状态的进程,进程可能会占⽤着物理内存空间,物理内存空间是有限的,被阻塞状态的进程占⽤着物理内存就⼀种浪费物理内存的⾏为。

所以,在虚拟内存管理的操作系统中,通常会把阻塞状态的进程的物理内存空间换出到硬盘,等需要再次运⾏的时候,再从硬盘换⼊到物理内存。

那么,就需要⼀个新的状态,来描述进程没有占⽤实际的物理内存空间的情况,这个状态就是挂起状态

这跟阻塞状态是不⼀样,阻塞状态是等待某个事件的返回。

另外,挂起状态可以分为两种:

  • 阻塞挂起状态:进程在外存(硬盘)并等待某个事件的出现;
  • 就绪挂起状态:进程在外存(硬盘),但只要进⼊内存,即刻⽴刻运⾏;

导致进程挂起的原因不只是因为进程所使⽤的内存空间不在物理内存,还包括如下情况:

  • 通过 sleep 让进程间歇性挂起,其⼯作原理是设置⼀个定时器,到期后唤醒进程。
  • ⽤户希望挂起⼀个程序的执⾏,⽐如在 Linux 中⽤ Ctrl+Z 挂起进程;

进程的控制结构

在操作系统中,是⽤进程控制块(process control block,PCB)数据结构来描述进程的。

PCB 是进程存在的唯⼀标识,这意味着⼀个进程的存在,必然会有⼀个 PCB,如果进程消失了,那么PCB 也会随之消失。

PCB 具体包含什么信息呢?

进程描述信息:

  • 进程标识符:标识各个进程,每个进程都有⼀个并且唯⼀的标识符;
  • ⽤户标识符:进程归属的⽤户,⽤户标识符主要为共享和保护服务;

进程控制和管理信息:

  • 进程当前状态,如 new、ready、running、waiting 或 blocked 等;
  • 进程优先级:进程抢占 CPU 时的优先级;

资源分配清单:

  • 有关内存地址空间或虚拟地址空间的信息,所打开⽂件的列表和所使⽤的 I/O 设备信息。

CPU 相关信息:

  • CPU 中各个寄存器的值,当进程被切换时,CPU 的状态信息都会被保存在相应的 PCB 中,以便进程重新执⾏时,能从断点处继续执⾏。

通常是通过链表的⽅式进⾏组织,把具有相同状态的进程链在⼀起,组成各种队列。⽐如:

  • 将所有处于就绪状态的进程链在⼀起,称为就绪队列;
  • 把所有因等待某事件⽽处于等待状态的进程链在⼀起就组成各种阻塞队列;
  • 另外,对于运⾏队列在单核 CPU 系统中则只有⼀个运⾏指针了,因为单核 CPU 在某个时间,只能运
    ⾏⼀个程序。

进程的控制

我们熟知了进程的状态变迁和进程的数据结构 PCB 后,再来看看进程的创建、终⽌、阻塞、唤醒的过程。

01 创建进程

操作系统允许⼀个进程创建另⼀个进程,⽽且允许⼦进程继承⽗进程所拥有的资源,当⼦进程被终⽌时,

其在⽗进程处继承的资源应当还给⽗进程。同时,终⽌⽗进程时同时也会终⽌其所有的⼦进程。

注意:Linux 操作系统对于终⽌有⼦进程的⽗进程,会把⼦进程交给 1 号进程接管。

这里所指出的进程终⽌概念是宏观操作系统的⼀种观点,最后怎么实现当然是看具体的操作系统。

创建进程的过程如下:

  • 为新进程分配⼀个唯⼀的进程标识号,并申请⼀个空⽩的 PCB,PCB 是有限的,若申请失败则创建
    失败;
  • 为进程分配资源,此处如果资源不⾜,进程就会进⼊等待状态,以等待资源;
  • 初始化 PCB;
  • 如果进程的调度队列能够接纳新进程,那就将进程插⼊到就绪队列,等待被调度运⾏;

02 终⽌进程

进程可以有 3 种终⽌⽅式:正常结束、异常结束以及外界⼲预(信号 kill 掉)。

终⽌进程的过程如下:

  • 查找需要终⽌的进程的 PCB;
  • 如果处于执⾏状态,则⽴即终⽌该进程的执⾏,然后将 CPU 资源分配给其他进程;
  • 如果其还有⼦进程,则应将其所有⼦进程终⽌;
  • 将该进程所拥有的全部资源都归还给⽗进程或操作系统;
  • 将其从 PCB 所在队列中删除;

03 阻塞进程

当进程需要等待某⼀事件完成时,它可以调⽤阻塞语句把⾃⼰阻塞等待。⽽⼀旦被阻塞等待,它只能由另
⼀个进程唤醒。

阻塞进程的过程如下:

  • 找到将要被阻塞进程标识号对应的 PCB;
  • 如果该进程为运⾏状态,则保护其现场,将其状态转为阻塞状态,停⽌运⾏;
  • 将该 PCB 插⼊到阻塞队列中去;

04 唤醒进程

进程由「运⾏」转变为「阻塞」状态是由于进程必须等待某⼀事件的完成,

所以处于阻塞状态的进程是绝对不可能叫醒⾃⼰的。

如果某进程正在等待 I/O 事件,需由别的进程发消息给它,则只有当该进程所期待的事件出现时,

才由发现者进程⽤唤醒语句叫醒它。

唤醒进程的过程如下:

  • 在该事件的阻塞队列中找到相应进程的 PCB;
  • 将其从阻塞队列中移出,并置其状态为就绪状态;
  • 把该 PCB 插⼊到就绪队列中,等待调度程序调度;

进程的阻塞和唤醒是⼀对功能相反的语句,如果某个进程调⽤了阻塞语句,则必有⼀个与之对应的唤醒语句。

进程的上下⽂切换

各个进程之间是共享 CPU 资源的,在不同的时候进程之间需要切换,

让不同的进程可以在 CPU 执⾏,那么这个⼀个进程切换到另⼀个进程运⾏,称为进程的上下⽂切换。

可以根据进程、线程和中断的不同,

把 CPU 上下⽂切换分成:进程上下⽂切换、线程上下⽂切换和中断上下⽂切换。

进程的上下⽂切换到底是切换什么呢?

进程的上下⽂切换不仅包含了虚拟内存、栈、全局变量等⽤户空间的资源,还包括了内核堆栈、寄存器等内核空间的资源

通常,会把交换的信息保存在进程的 PCB,当要运⾏另外⼀个进程的时候,我们需要从这个进程的 PCB取出上下⽂,然后恢复到 CPU 中,这使得这个进程可以继续执⾏。

什么时候会发生上下文的切换?

为了保证所有进程可以得到公平调度,CPU 时间被划分为⼀段段的时间⽚,
这些时间⽚再被轮流分配给各个进程。
这样,当某个进程的时间⽚耗尽了,进程就从运⾏状态变为就绪状态,系统从就绪队列选择另外⼀个进程运⾏;

进程在系统资源不⾜(⽐如内存不⾜)时,要等到资源满⾜后才可以运⾏,
这个时候进程也会被挂起,并由系统调度其他进程运⾏;

当进程通过睡眠函数 sleep 这样的⽅法将⾃⼰主动挂起时,⾃然也会重新调度;

当有优先级更⾼的进程运⾏时,为了保证⾼优先级进程的运⾏,当前进程会被挂起,由⾼优先级进程来运⾏;

发⽣硬件中断时,CPU 上的进程会被中断挂起,转⽽执⾏内核中的中断服务程序

线程

在早期的操作系统中都是以进程作为独⽴运⾏的基本单位,直到后⾯,计算机科学家们⼜提出了更⼩的能独⽴运⾏的基本单位,也就是线程。

问题-》解决-》由来

什么是线程?

线程是进程当中的⼀条执⾏流程。

同⼀个进程内多个线程之间可以共享代码段、数据段、打开的⽂件等资源,

但每个线程各⾃都有⼀套独⽴的寄存器和栈,这样可以确保线程的控制流是相对独⽴的。

线程的优缺点?

线程的优点:

  • ⼀个进程中可以同时存在多个线程;
  • 各个线程之间可以并发执⾏;
  • 各个线程之间可以共享地址空间和⽂件等资源;

线程的缺点:

  • 当进程中的⼀个线程崩溃时,会导致其所属进程的所有线程崩溃。

线程与进程的⽐较

线程与进程的⽐较如下:

  • 进程是资源(包括内存、打开的⽂件等)分配的单位,线程是 CPU 调度的单位;
  • 进程拥有⼀个完整的资源平台,⽽线程只独享必不可少的资源,如寄存器和栈;
  • 线程同样具有就绪、阻塞、执⾏三种基本状态,同样具有状态之间的转换关系;
  • 线程能减少并发执⾏的时间和空间开销;

对于,线程相⽐进程能减少开销,体现在:

  • 线程的创建时间⽐进程快,

    因为进程在创建的过程中,还需要资源管理信息,⽐如内存管理信息、⽂件管理信息,

    ⽽线程在创建的过程中,不会涉及这些资源管理信息,⽽是共享它们;

  • 线程的终⽌时间⽐进程快,因为线程释放的资源相⽐进程少很多;

  • 同⼀个进程内的线程切换⽐进程切换快,因为线程具有相同的地址空间(虚拟内存共享),

    这意味着同⼀个进程的线程都具有同⼀个⻚表,那么在切换的时候不需要切换⻚表。

    ⽽对于进程之间的切换,切换的时候要把⻚表给切换掉,⽽⻚表的切换过程开销是⽐较⼤的;

  • 由于同⼀进程的各线程间共享内存和⽂件资源,那么在线程之间数据传递的时候就不需要经过内核了,

    这就使得线程之间的数据交互效率更⾼了;所以,不管是时间效率,还是空间效率线程⽐进程都要⾼。

线程的上下⽂切换

在前⾯我们知道了,线程与进程最⼤的区别在于:

线程是调度的基本单位,⽽进程则是资源拥有的基本单位。

所以,所谓操作系统的任务调度,实际上的调度对象是线程,

⽽进程只是给线程提供了虚拟内存、全局变量等资源。

对于线程和进程,我们可以这么理解:

  • 当进程只有⼀个线程时,可以认为进程就等于线程

  • 当进程拥有多个线程时,这些线程会共享相同的虚拟内存和全局变量等资源,

    这些资源在上下⽂切换时是不需要修改的;

线程上下⽂切换的是什么?

这还得看线程是不是属于同⼀个进程:

  • 当两个线程不是属于同⼀个进程,则切换的过程就跟进程上下⽂切换⼀样;

  • 当两个线程是属于同⼀个进程,因为虚拟内存是共享的,

    所以在切换时,虚拟内存这些资源就保持不动,只需要切换线程的私有数据、寄存器等不共享的数据;

所以,线程的上下⽂切换相⽐进程,开销要⼩很多。

线程的实现

主要有三种线程的实现⽅式:

  • ⽤户线程(User Thread):在⽤户空间实现的线程,不是由内核管理的线程,是由⽤户态的线程库
    来完成线程的管理;
  • 内核线程(Kernel Thread):在内核中实现的线程,是由内核管理的线程;
  • 轻量级进程(LightWeight Process):在内核中来⽀持⽤户线程;

⽤户线程如何理解?存在什么优势和缺陷?

⽤户线程是基于⽤户态的线程管理库来实现的,

那么线程控制块(Thread Control Block, TCB) 也是在库⾥⾯来实现的,对于操作系统⽽⾔是看不到这个 TCB 的,它只能看到整个进程的 PCB。

所以,⽤户线程的整个线程管理和调度,操作系统是不直接参与的,

⽽是由⽤户级线程库函数来完成线程的管理,包括线程的创建、终⽌、同步和调度等。

⽤户线程的优点:

每个进程都需要有它私有的线程控制块(TCB)列表,
⽤来跟踪记录它各个线程状态信息(PC、栈指针、寄存器),
TCB 由⽤户级线程库函数来维护,可⽤于不⽀持线程技术的操作系统;

⽤户线程的切换也是由线程库函数来完成的,⽆需⽤户态与内核态的切换,所以速度特别快;

⽤户线程的缺点:

由于操作系统不参与线程的调度,如果⼀个线程发起了系统调⽤⽽阻塞,
那进程所包含的⽤户线程都不能执⾏了。

当⼀个线程开始运⾏后,除⾮它主动地交出 CPU 的使⽤权,
否则它所在的进程当中的其他线程⽆法运⾏,因为⽤户态的线程没法打断当前运⾏中的线程,
但是⽤户线程不是由操作系统管理的。

由于时间⽚分配给进程,故与其他进程⽐,在多线程执⾏时,每个线程得到的时间⽚较少,执⾏会⽐
较慢;

那内核线程如何理解?存在什么优势和缺陷?

内核线程是由操作系统管理的,线程对应的 TCB ⾃然是放在操作系统⾥的,

这样线程的创建、终⽌和管理都是由操作系统负责。

内核线程的优点:

在⼀个进程当中,如果某个内核线程发起系统调⽤⽽被阻塞,并不会影响其他内核线程的运⾏;

分配给线程,多线程的进程获得更多的 CPU 运⾏时间;


内核线程的缺点:

在⽀持内核线程的操作系统中,由内核来维护进程和线程的上下⽂信息,如 PCB 和 TCB;

线程的创建、终⽌和切换都是通过系统调⽤的⽅式来进⾏,因此对于系统来说,系统开销⽐较⼤;

轻量级进程如何理解?

轻量级进程(Light-weight process,LWP)是内核⽀持的⽤户线程,⼀个进程可有⼀个或多个 LWP,

每个 LWP 是跟内核线程⼀对⼀映射的,也就是 LWP 都是由⼀个内核线程⽀持。

另外,LWP 只能由内核管理并像普通进程⼀样被调度,Linux 内核是⽀持 LWP 的典型例⼦。

在⼤多数系统中,LWP与普通进程的区别也在于它只有⼀个最⼩的执⾏上下⽂和调度程序所需的统计信息。

⼀般来说,⼀个进程代表程序的⼀个实例,⽽ LWP 代表程序的执⾏线程,

因为⼀个执⾏线程不像进程那样需要那么多状态信息,所以 LWP 也不带有这样的信息。

在 LWP 之上也是可以使⽤⽤户线程的,那么 LWP 与⽤户线程的对应关系就有三种:

  • 1 : 1 ,即⼀个 LWP 对应 ⼀个⽤户线程;
  • N : 1 ,即⼀个 LWP 对应多个⽤户线程;
  • M : N ,即多个 LMP 对应多个⽤户线程;

调度

进程都希望⾃⼰能够占⽤ CPU 进⾏⼯作,那么这涉及到前⾯说过的进程上下⽂切换。

⼀旦操作系统把进程切换到运⾏状态,也就意味着该进程占⽤着 CPU 在执⾏,

但是当操作系统把进程切换到其他状态时,那就不能在 CPU 中执⾏了,于是操作系统会选择下⼀个要运⾏的程。

选择⼀个进程运⾏这⼀功能是在操作系统中完成的,通常称为调度程序(scheduler)。

调度算法

  • 先来先服务调度算法,听名字就明白了。
  • 最短作业优先调度算法,同。
  • ⾼响应⽐优先调度算法,看吧,看懂中文意思就明白了。
  • 时间⽚轮转调度算法
  • 最⾼优先级调度算法
  • 多级反馈队列调度算法,多级反馈队列(Multilevel Feedback Queue)调度算法是「时间⽚轮转算法」和「最⾼优先级算法」的综合和发展。

进程与通信

每个进程的⽤户地址空间都是独⽴的,⼀般⽽⾔是不能互相访问的,但内核空间是每个进程都共享的,所以进程之间要通信必须通过内核。

管道

管道传输数据是单向的,如果想相互通信,我们需要创建两个管道才⾏。

管道还有另外⼀个类型是命名管道,也被叫做 FIFO ,因为数据是先进先出的传输⽅式。

但是呢,管道这种通信⽅式效率低,不适合进程间频繁地交换数据。

当然,它的好处,⾃然就是简单,同时也我们很容易得知管道⾥的数据已经被另⼀个进程读取了。

所谓的管道,就是内核⾥⾯的⼀串缓存。

从管道的⼀段写⼊的数据,实际上是缓存在内核中的,另⼀端读取,也就是从内核中读取这段数据。

另外,管道传输的数据是⽆格式的流且⼤⼩受限。

我们可以得知,对于匿名管道,它的通信范围是存在⽗⼦关系的进程。

因为管道没有实体,也就是没有管道⽂件,只能通过 fork 来复制⽗进程 fd ⽂件描述符,来达到通信的⽬的。

另外,对于命名管道,它可以在不相关的进程间也能相互通信。

因为命令管道,提前创建了⼀个类型为管道的设备⽂件,在进程⾥只要使⽤这个设备⽂件,就可以相互通信。

不管是匿名管道还是命名管道,进程写⼊的数据都是缓存在内核中,

另⼀个进程读取数据时候⾃然也是从内核中获取,同时通信数据都遵循先进先出原则,不⽀持 lseek 之类的⽂件定位操作。

消息队列

消息队列是保存在内核中的消息链表,

在发送数据时,会分成⼀个⼀个独⽴的数据单元,也就是消息体(数据块),消息体是⽤户⾃定义的数据类型,

消息的发送⽅和接收⽅要约定好消息体的数据类型。

所以每个消息体都是固定⼤⼩的存储块,不像管道是⽆格式的字节流数据。

如果进程从消息队列中读取了消息体,内核就会把这个消息体删除。

消息队列⽣命周期随内核,如果没有释放消息队列或者没有关闭操作系统,消息队列会⼀直存在,

⽽前⾯提到的匿名管道的⽣命周期,是随进程的创建⽽建⽴,随进程的结束⽽销毁。

消息队列不适合⽐较⼤数据的传输,消息队列通信过程中,存在⽤户态与内核态之间的数据拷⻉开销

共享内存

共享内存的机制,就是拿出⼀块虚拟地址空间来,映射到相同的物理内存中。

信号量

信号量其实是⼀个整型的计数器,主要⽤于实现进程间的互斥与同步,⽽不是⽤于缓存进程间通信的数据。

PV操作。

信号

于异常情况下的⼯作模式,就需要⽤「信号」的⽅式来通知进程。

Socket

跨⽹络与不同主机上的进程之间通信,就需要 Socket 通信了。

int socket(int domain, int type, int protocal)

三个参数分别代表:

  • domain 参数⽤来指定协议族,⽐如 AF_INET ⽤于 IPV4、AF_INET6 ⽤于 IPV6、AF_LOCAL/AF_UNIX ⽤于本机;

  • type 参数⽤来指定通信特性,⽐如 SOCK_STREAM 表示的是字节流,

    对应 TCP、SOCK_DGRAM表示的是数据报,对应 UDP、SOCK_RAW 表示的是原始套接字;

  • protocal 参数原本是⽤来指定通信协议的,但现在基本废弃。因为协议已经通过前⾯两个参数指定完
    成,protocol ⽬前⼀般写成 0 即可;

根据创建 socket 类型的不同,通信的⽅式也就不同:

  • 实现 TCP 字节流通信: socket 类型是 AF_INET 和 SOCK_STREAM;

  • 实现 UDP 数据报通信:socket 类型是 AF_INET 和 SOCK_DGRAM;

  • 实现本地进程间通信: 「本地字节流 socket 」类型是 AF_LOCAL 和 SOCK_STREAM,

    「本地数据报 socket 」类型是 AF_LOCAL 和 SOCK_DGRAM。

    另外,AF_UNIX 和 AF_LOCAL 是等价的,所以AF_UNIX 也属于本地 socket;

针对 TCP 协议通信的 socket 编程模型

针对 UDP 协议通信的 socket 编程模型

多线程同步

互斥(mutualexclusion)的,也就说保证⼀个线程在临界区执⾏时,其他线程应该被阻⽌进⼊临界区,说⽩了,就是这段代码执⾏过程中,最多只能出现⼀个线程。

同步与互斥是两种不同的概念:

  • 同步就好⽐:「操作 A 应在操作 B 之前执⾏」,「操作 C 必须在操作 A 和操作 B 都完成之后才能执⾏」等;
  • 互斥就好⽐:「操作 A 和操作 B 不能在同⼀时刻执⾏」;

互斥与同步的实现和使⽤

为了实现进程/线程间正确的协作,操作系统必须提供实现进程协作的措施和⽅法,主要的⽅法有两种:

  • 锁:加锁、解锁操作;
  • 信号量:P、V 操作;

想详细了解Java里面锁的实现可以看这几个文章:

从synchronize到CSA和AQS _

线程同步-锁

任何想进⼊临界区的线程,必须先执⾏加锁操作。

若加锁操作顺利通过,则线程可进⼊临界区;

在完成对临界资源的访问后再执⾏解锁操作,以释放该临界资源。

根据锁的实现不同,可以分为「忙等待锁」和「⽆忙等待锁」。

「忙等待锁」

⾃旋锁(spin lock)

⼀直⾃旋,利⽤ CPU 周期,直到锁可⽤。

在单处理器上,需要抢占式的调度器(即不断通过时钟中断⼀个线程,运⾏其他线程)。

否则,⾃旋锁在单 CPU 上⽆法使⽤,因为⼀个⾃旋的线程,永远不会放弃 CPU。

「⽆忙等待锁」

⽆等待锁顾明思议就是获取不到锁的时候,不⽤⾃旋。

既然不想⾃旋,那当没获取到锁的时候,就把当前线程放⼊到锁的等待队列,然后执⾏调度程序,把 CPU让给其他线程执⾏。

信号量

信号量实现临界区的互斥访问。

⽣产者-消费者问题

⽣产者-消费者问题描述:

  • ⽣产者在⽣成数据后,放在⼀个缓冲区中;
  • 消费者从缓冲区取出数据处理;
  • 任何时刻,只能有⼀个⽣产者或消费者可以访问缓冲区;

我们对问题分析可以得出:

  • 任何时刻只能有⼀个线程操作缓冲区,说明操作缓冲区是临界代码,需要互斥

  • 缓冲区空时,消费者必须等待⽣产者⽣成数据;缓冲区满时,⽣产者必须等待消费者取出数据。

    说明⽣产者和消费者需要同步

那么我们需要三个信号量,分别是:

  • 互斥信号量 mutex :⽤于互斥访问缓冲区,初始化值为 1;
  • 资源信号量 fullBuffers :⽤于消费者询问缓冲区是否有数据,有数据则读取数据,初始化值为 0
    (表明缓冲区⼀开始为空);
  • 资源信号量 emptyBuffers :⽤于⽣产者询问缓冲区是否有空位,有空位则⽣成数据,初始化值为 n
    (缓冲区⼤⼩);

经典同步问题

哲学家就餐问题

「哲学家进餐问题」对于互斥访问有限的竞争问题(如 I/O 设备)⼀类的建模过程⼗分有⽤。

先来看看哲学家就餐的问题描述:
5 个⽼⼤哥哲学家,闲着没事做,围绕着⼀张圆桌吃⾯;
巧就巧在,这个桌⼦只有 5 ⽀叉⼦,每两个哲学家之间放⼀⽀叉⼦;
哲学家围在⼀起先思考,思考中途饿了就会想进餐;
奇葩的是,这些哲学家要两⽀叉⼦才愿意吃⾯,也就是需要拿到左右两边的叉⼦才进餐;
吃完后,会把两⽀叉⼦放回原处,继续思考;

⽅案⼀

不过,这种解法存在⼀个极端的问题:

假设五位哲学家同时拿起左边的叉⼦,桌⾯上就没有叉⼦了,这样就没有⼈能够拿到他们右边的叉⼦,

也就说每⼀位哲学家都会在 P(fork[(i + 1) % N ]) 这条语句阻塞了,很明显这发⽣了死锁的现象。

⽅案二

只要有⼀个哲学家进⼊了「临界区」,也就是准备要拿叉⼦时,其他哲学家都不能动,只有这位哲学家⽤完叉⼦了,才能轮到下⼀个哲学家进餐。

⽅案⼆虽然能让哲学家们按顺序吃饭,但是每次进餐只能有⼀位哲学家,

⽽桌⾯上是有 5 把叉⼦,按道理能可以有两个哲学家同时进餐的,所以从效率⻆度上,这不是最好的解决⽅案。

⽅案三

即让偶数编号的哲学家「先拿左边的叉⼦后拿右边的叉⼦」,奇数编号的哲学家「先拿右边的叉⼦后拿左边的叉⼦」。

⽅案四

⽤⼀个数组 state 来记录每⼀位哲学家在进程、思考还是饥饿状态(正在试图拿叉⼦)。

那么,⼀个哲学家只有在两个邻居都没有进餐时,才可以进⼊进餐状态。

⽅案四同样不会出现死锁,也可以两⼈同时进餐。

读者-写者问题

它为数据库访问建⽴了⼀个模型。

读者-写者的问题描述:

  • 「读-读」允许:同⼀时刻,允许多个读者同时读
  • 「读-写」互斥:没有写者时读者才能读,没有读者时写者才能写
  • 「写-写」互斥:没有其他写者时,写者才能写

⽅案⼀

读者优先的策略,因为只要有读者正在读的状态,后来的读者都可以直接进⼊,

如果读者持续不断进⼊,则写者会处于饥饿状态。

⽅案⼆

那既然有读者优先策略,⾃然也有写者优先策略:

  • 只要有写者准备要写⼊,写者应尽快执⾏写操作,后来的读者就必须阻塞;
  • 如果有写者持续不断写⼊,则读者就处于饥饿;

⽅案三

既然读者优先策略和写者优先策略都会造成饥饿的现象,那么我们就来实现⼀下公平策略。

公平策略:

  • 优先级相同;
  • 写者、读者互斥访问;
  • 只能⼀个写者访问临界区;
  • 可以有多个读者同时访问临街资源;

死锁

死锁只有同时满⾜以下四个条件才会发⽣:

  • 互斥条件;
  • 持有并等待条件;
  • 不可剥夺条件;
  • 环路等待条件;

互斥锁与⾃旋锁

最底层的两种就是会「互斥锁和⾃旋锁」,有很多⾼级的锁都是基于它们实现的,你可以认为它们是各种锁的地基,所以我们必须清楚它俩之间的区别和应⽤。

加锁的⽬的就是保证共享资源在任意时间⾥,只有⼀个线程访问,这样就可以避免多线程导致共享数据错乱的问题。

当已经有⼀个线程加锁后,其他线程加锁则就会失败,互斥锁和⾃旋锁对于加锁失败后的处理⽅式是不⼀样的:

  • 互斥锁加锁失败后,线程会释放 CPU ,给其他线程;
  • ⾃旋锁加锁失败后,线程会忙等待,直到它拿到锁;

互斥锁

互斥锁是⼀种「独占锁」,对于互斥锁加锁失败⽽阻塞的现象,是由操作系统内核实现的。

当加锁失败时,内核会将线程置为「睡眠」状态,等到锁被释放后,内核会在合适的时机唤醒线程,

当这个线程成功获取到锁后,于是就可以继续执⾏。

所以,互斥锁加锁失败时,会从⽤户态陷⼊到内核态,让内核帮我们切换线程,

虽然简化了使⽤锁的难度,但是存在⼀定的性能开销成本。

那这个开销成本是什么呢?会有两次线程上下⽂切换的成本:

  • 当线程加锁失败时,内核会把线程的状态从「运⾏」状态设置为「睡眠」状态,然后把 CPU 切换给其他线程运⾏;
  • 接着,当锁被释放时,之前「睡眠」状态的线程会变为「就绪」状态,然后内核会在合适的时间,把CPU 切换给该线程运⾏。

线程的上下⽂切换的是什么?

当两个线程是属于同⼀个进程,因为虚拟内存是共享的,所以在切换时,虚拟内存这些资源就保持不动,

只需要切换线程的私有数据、寄存器等不共享的数据。

上下切换的耗时有⼤佬统计过,⼤概在⼏⼗纳秒到⼏微秒之间,如果你锁住的代码执⾏时间⽐较短,

那可能上下⽂切换的时间都⽐你锁住的代码执⾏时间还要⻓。

所以,如果你能确定被锁住的代码执⾏时间很短,就不应该⽤互斥锁,⽽应该选⽤⾃旋锁,否则使⽤互斥锁。

⾃旋锁

CPU 提供的 CAS 函数(Compare And Swap),在「⽤户态」完成加锁和解锁操作,不会主动产⽣线程上下⽂切换,所以相⽐互斥锁来说,会快⼀些,开销也⼩⼀些。

⼀般加锁的过程,包含两个步骤:

  • 第⼀步,查看锁的状态,如果锁是空闲的,则执⾏第⼆步;
  • 第⼆步,将锁设置为当前线程持有;

CAS 函数就把这两个步骤合并成⼀条硬件级指令,形成原⼦指令,

这样就保证了这两个步骤是不可分割的,要么⼀次性执⾏完两个步骤,要么两个步骤都不执⾏。

使⽤⾃旋锁的时候,当发⽣多线程竞争锁的情况,加锁失败的线程会「忙等待」,直到它拿到锁。

这⾥的「忙等待」可以⽤ while 循环等待实现,不过最好是使⽤ CPU 提供的 PAUSE 指令来实现「忙等待」,因为可以减少循环等待时的耗电量。

⾃旋锁是最⽐较简单的⼀种锁,⼀直⾃旋,利⽤ CPU 周期,直到锁可⽤。

需要注意,在单核 CPU 上,需要抢占式的调度器(即不断通过时钟中断⼀个线程,运⾏其他线程)。

否则,⾃旋锁在单 CPU 上⽆法使⽤,因为⼀个⾃旋的线程永远不会放弃 CPU。

⾃旋锁与互斥锁使⽤层⾯⽐较相似,但实现层⾯上完全不同:

当加锁失败时,互斥锁⽤「线程切换」来应对,⾃旋锁则⽤「忙等待」来应对。

读写锁

读写锁的⼯作原理是:

  • 当「写锁」没有被线程持有时,多个线程能够并发地持有读锁,这⼤⼤提⾼了共享资源的访问效率,

    因为「读锁」是⽤于读取共享资源的场景,所以多个线程同时持有读锁也不会破坏共享资源的数据。

  • 但是,⼀旦「写锁」被线程持有后,读线程的获取读锁的操作会被阻塞,

    ⽽且其他写线程的获取写锁的操作也会被阻塞。

所以说,写锁是独占锁,因为任何时刻只能有⼀个线程持有写锁,类似互斥锁和⾃旋锁,

读锁是共享锁,因为读锁可以被多个线程同时持有。

知道了读写锁的⼯作原理后,我们可以发现,读写锁在读多写少的场景,能发挥出优势

读写锁可以分为「读优先锁」和「写优先锁」。

公平读写锁⽐较简单的⼀种⽅式是:

⽤队列把获取锁的线程排队,不管是写线程还是读线程都按照先进先出的原则加锁即可,这样读线程仍然可以并发,也不会出现「饥饿」的现象。

互斥锁和⾃旋锁都是最基本的锁,读写锁可以根据场景来选择这两种锁其中的⼀个进⾏实现。

乐观锁与悲观锁

悲观锁做事⽐较悲观,它认为多线程同时修改共享资源的概率⽐较⾼,于是很容易出现冲突,所以访问共享资源前,先要上锁。

乐观锁做事⽐较乐观,它假定冲突的概率很低,

它的⼯作⽅式是:先修改完共享资源,再验证这段时间内有没有发⽣冲突,

如果没有其他线程在修改资源,那么操作完成,如果发现有其他线程已经修改过这个资源,就放弃本次操作。

乐观锁全程并没有加锁,所以它也叫⽆锁编程。

只有在冲突概率⾮常低,且加锁成本⾮常⾼的场景时,才考虑使⽤乐观锁。

调度算法

具体内容更新中…………

文件系统

⽂件系统的基本组成

Linux 最经典的⼀句话是:「⼀切皆⽂件」,不仅普通的⽂件和⽬录,就连块设备、管道、socket 等,也都是统⼀交给⽂件系统管理的。

虚拟⽂件系统

⽂件系统的种类众多,⽽操作系统希望对⽤户提供⼀个统⼀的接⼝,

于是在⽤户层与⽂件系统层引⼊了中间层,这个中间层就称为虚拟⽂件系统(Virtual File System,VFS)。

⽂件的存储

连续空间存放

连续空间存放的⽅式虽然读写效率⾼,但是有「磁盘空间碎⽚」和「⽂件⻓度不易扩展」的缺陷。

⾮连续空间存放⽅式

⾮连续空间存放⽅式分为「链表⽅式」和「索引⽅式」。

链表⽅式

链表的⽅式存放是离散的,不⽤连续的,于是就可以消除磁盘碎⽚,可⼤⼤提⾼磁盘空间的利⽤率,同时⽂件的⻓度可以动态扩展。

「隐式链表」的⽅式存放的话,实现的⽅式是⽂件头要包含「第⼀块」和「最后⼀块」的位置,并且每个数据块⾥⾯留出⼀个指针空间,⽤来存放下⼀个数据块的位置。

隐式链表的存放⽅式的缺点在于⽆法直接访问数据块,

只能通过指针顺序访问⽂件,以及数据块指针消耗了⼀定的存储空间。

隐式链接分配的稳定性较差,系统在运⾏过程中由于软件或者硬件错误导致链表中的指针丢失或损坏,会导致⽂件数据的丢失。

「显式链接」,它指把⽤于链接⽂件各数据块的指针,显式地存放在内存的⼀张链接表中,该表在整个磁盘仅设置⼀张,每个表项中存放链接指针,指向下⼀个数据块号。

因⽽不仅显著地提⾼了检索速度,⽽且⼤⼤减少了访问磁盘的次数。

但也正是整个表都存放在内存中的关系,它的主要的缺点是不适⽤于⼤磁盘。

索引⽅式

索引的实现是为每个⽂件创建⼀个「索引数据块」,⾥⾯存放的是指向⽂件数据块的指针列表,说⽩了就像书的⽬录⼀样,要找哪个章节的内容,看⽬录查就可以。

另外,⽂件头需要包含指向「索引数据块」的指针,这样就可以通过⽂件头知道索引数据块的位置,再通过索引数据块⾥的索引信息找到对应的数据块。

索引的⽅式优点在于:

  • ⽂件的创建、增⼤、缩⼩很⽅便;
  • 不会有碎⽚的问题;
  • ⽀持顺序读写和随机读写;

链表 + 索引的组合,这种组合称为「链式索引块」,它的实现⽅式是在索引数据块留出⼀个存放下⼀个索引数据块的指针

索引 + 索引的⽅式,这种组合称为「多级索引块」,实现⽅式是通过⼀个索引块来存放多个索引数据块,⼀层套⼀层索引,像极了俄罗斯套娃是吧。

Unix ⽂件的实现⽅式

空闲空间管理

⽂件的存储是针对已经被占⽤的数据块组织和管理,

接下来的问题是,如果我要保存⼀个数据块,我应该放在硬盘上的哪个位置呢?难道需要将所有的块扫描⼀遍,找个空的地⽅随便放吗?

那这种⽅式效率就太低了,所以针对磁盘的空闲空间也是要引⼊管理的机制,接下来介绍⼏种常⻅的⽅法:

  • 空闲表法
  • 空闲链表法
  • 位图法

空闲表法

空闲链表法

位图法

位图是利⽤⼆进制的⼀位来表示磁盘中⼀个盘块的使⽤情况,磁盘上所有的盘块都有⼀个⼆进制位与之对应。

当值为 0 时,表示对应的盘块空闲,值为 1 时,表示对应的盘块已分配。

在 Linux ⽂件系统就采⽤了位图的⽅式来管理空闲空间,不仅⽤于数据空闲块的管理,

还⽤于 inode 空闲块的管理,因为 inode 也是存储在磁盘的,⾃然也要有对其管理。

⽂件系统的结构

每个块组⾥有很多重复的信息,⽐如超级块和块组描述符表,这两个都是全局信息,⽽且⾮常的重要,这么做是有两个原因:

  1. 如果系统崩溃破坏了超级块或块组描述符,有关⽂件系统结构和内容的所有信息都会丢失。

    如果有冗余的副本,该信息是可能恢复的。

  2. 通过使⽂件和管理数据尽可能接近,减少了磁头寻道和旋转,这可以提⾼⽂件系统的性能。

不过,Ext2 的后续版本采⽤了稀疏技术。

该做法是,超级块和块组描述符表不再存储到⽂件系统的每个块组中,

⽽是只写⼊到块组 0、块组 1 和其他 ID 可以表示为 3、 5、7 的幂的块组中。

⽬录的存储

如果⼀个⽬录有超级多的⽂件,

我们要想在这个⽬录下找⽂件,按照列表⼀项⼀项的找,效率就不⾼了。

于是,保存⽬录的格式改成哈希表,对⽂件名进⾏哈希计算,把哈希值保存起来,如果我们要查找⼀个⽬录下⾯的⽂件名,可以通过名称取哈希。

Linux 系统的 ext ⽂件系统就是采⽤了哈希表,来保存⽬录的内容,这种⽅法的优点是查找⾮常迅速,插⼊和删除也较简单,不过需要⼀些预备措施来避免哈希冲突。

软链接和硬链接

硬链接(Hard Link) 和软链接(Symbolic Link)

硬链接是多个⽬录项中的「索引节点」指向⼀个⽂件,也就是指向同⼀个 inode,

但是 inode 是不可能跨越⽂件系统的,每个⽂件系统都有各⾃的 inode 数据结构和列表,所以硬链接是不可⽤跨⽂件系统的

由于多个⽬录项都是指向⼀个 inode,那么只有删除⽂件的所有硬链接以及源⽂件时,系统才会彻底删除该⽂件。

软链接相当于重新创建⼀个⽂件,这个⽂件有独⽴的 inode

但是这个⽂件的内容是另外⼀个⽂件的路径,所以访问软链接的时候,实际上相当于访问到了另外⼀个⽂件,

所以软链接是可以跨⽂件系统的,甚⾄⽬标⽂件被删除了,链接⽂件还是在的,只不过指向的⽂件找不到了⽽已。

⽂件 I/O

  • 缓冲与⾮缓冲 I/O
  • 直接与⾮直接 I/O
  • 阻塞与⾮阻塞 I/O VS 同步与异步 I/O

阻塞与⾮阻塞 I/O VS 同步与异步 I/O

先来看看阻塞 I/O,当⽤户程序执⾏ read ,线程会被阻塞,⼀直等到内核数据准备好,并把数据从内核缓冲区拷⻉到应⽤程序的缓冲区中,当拷⻉过程完成, read 才会返回。

注意,阻塞等待的是「内核数据准备好」和「数据从内核态拷⻉到⽤户态」这两个过程。

⾮阻塞 I/O

这⾥最后⼀次 read 调⽤,获取数据的过程,是⼀个同步的过程,是需要等待的过程。

这⾥的同步指的是内核态的数据拷⻉到⽤户程序的缓存区这个过程。

应⽤程序每次轮询内核的 I/O 是否准备好,感觉有点傻乎乎,因为轮询的过程中,应⽤程序啥也做不了,只是在循环。

为了解决这种傻乎乎轮询⽅式,于是 I/O 多路复⽤技术就出来了,如 select、poll,它是通过 I/O 事件分发,当内核数据准备好时,再以事件通知应⽤程序进⾏操作。

这个做法⼤⼤改善了应⽤进程对 CPU 的利⽤率,在没有被通知的情况下,应⽤进程可以使⽤ CPU 做其他的事情。

select I/O 多路复⽤

实际上,⽆论是阻塞 I/O、⾮阻塞 I/O,还是基于⾮阻塞 I/O 的多路复⽤都是同步调⽤

因为它们在 read调⽤时,内核将数据从内核空间拷⻉到应⽤程序空间,过程都是需要等待的,

也就是说这个过程是同步的,如果内核实现的拷⻉效率不⾼,read 调⽤就会在这个同步过程中等待⽐较⻓的间。

⽽真正的异步 I/O 是「内核数据准备好」和「数据从内核态拷⻉到⽤户态」这两个过程都不⽤等待。

异步的IO

当我们发起 aio_read 之后,就⽴即返回,

内核⾃动将数据从内核空间拷⻉到应⽤程序空间,这个拷⻉过程同样是异步的,

内核⾃动完成的,和前⾯的同步操作不⼀样,应⽤程序并不需要主动发起拷⻉动作。

⽤故事去理解这⼏种 I/O 模型

举个你去饭堂吃饭的例⼦,你好⽐⽤户程序,饭堂好⽐操作系统。

阻塞 I/O 好⽐,
你去饭堂吃饭,但是饭堂的菜还没做好,然后你就⼀直在那⾥等啊等,

等了好⻓⼀段时间终于等到饭堂阿姨把菜端了出来(数据准备的过程),

但是你还得继续等阿姨把菜(内核空间)打到你的饭盒⾥(⽤户空间),

经历完这两个过程,你才可以离开。



⾮阻塞 I/O 好⽐,
你去了饭堂,问阿姨菜做好了没有,阿姨告诉你没,

你就离开了,过⼏⼗分钟,你⼜来,

饭堂问阿姨,阿姨说做好了,于是阿姨帮你把菜打到你的饭盒⾥,这个过程你是得等待的。




基于⾮阻塞的 I/O 多路复⽤好⽐,
你去饭堂吃饭,发现有⼀排窗⼝,饭堂阿姨告诉你这些窗⼝都还没做好菜,

等做好了再通知你,于是等啊等( select 调⽤中),过了⼀会阿姨通知你菜做好了,

但是不知道哪个窗⼝的菜做好了,你⾃⼰看吧。

于是你只能⼀个⼀个窗⼝去确认,后⾯发现 5 号窗⼝菜做好了,

于是你让 5 号窗⼝的阿姨帮你打菜到饭盒⾥,这个打菜的过程你是要等待的,虽然时间不⻓。

打完菜后,你⾃然就可以离开了。



异步 I/O 好⽐,
你让饭堂阿姨将菜做好并把菜打到饭盒⾥后,把饭盒送到你⾯前,整个过程你都不需要任何等待。

设备管理

DMA(Direct Memory Access) 功能,它可以使得设备在CPU 不参与的情况下,能够⾃⾏完成把设备 I/O 数据放⼊到内存。

设备驱动程序

设备驱动程序会提供统⼀的接⼝给操作系统

存储系统 I/O 软件分层

网络系统


I/O 多路复⽤:select/poll/epoll

更新中…………