三、内存管理

进程持有的虚拟地址会通过CPU芯片中的内存管理单元(MMU)的映射关系，转换成物理地址，然后通过物理地址访问内存。

内存分段

程序是由若干个逻辑分段组成的，如代码段、数据段、栈段、堆段。所以通过分段的形式，将它们分离。
分段机制下虚拟地址由段选择子和段内偏移量组成。

段选择子保存在段寄存器中，其中段号用作段表索引。段表中保存该段的基地址、段的界限和特权等级。
虚拟地址中的段内偏移量应该位于0和段界限之间，如果端内偏移量合法，基址+偏移量=物理地址。

分段带来两个问题：

内存碎片
内存交换的效率低

其中内存碎片又细分为两种：

外部碎片：产生了许多不连续的小内存，虽然总量足够容纳新程序，但是因为不连续所以新程序无法装载；
内部碎片：程序所有的内存都被装载到物理内存，但是有部分不常使用，造成浪费。

解决外部内存碎片的方式：内存交换。

在此处，将音乐占用的256MB内存写到硬盘上，然后再读回来，但是要装载到游戏的512MB后面；确保留出连续的足够大的空间，让新的程序能够装载进来。然而，磁盘访问速度太慢了，对于每一次内存交换都会造成磁盘IO。所以内存交换效率低。

为了解决分段带来的内存碎片和交换效率低，出现了内存分页。

内存分页

分页把整个虚拟和物理内存空间切成固定尺寸大小，称为页。Linux中，每一页表示的内存大小为4KB。

页表存储在内存中。

分页解决分段的内存碎片、交换效率低的问题：

分页的内存空间都是预先划分好的，因此不会产生间隙小的内存。当释放内存的时候，是以页为单位的，所以不存在产生无法给进程使用的小内存的情况。
内存交换时，一次性写入磁盘只有少数一个或几个页，交换效率相对较高。

此外，分页使得加载程序时不用一次性全部加载到物理内存中，而是等虚存、物理内存建立映射后，在程序运行时，用到对应虚拟内存页中指令和数据时，再加载到物理内存。

虚拟地址分为两部分：页号和页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址。

内存地址转换，分为以下三个步骤：

把虚拟内存地址切分为页号和偏移量；
根据页号从页表里找出对应的物理页号；
直接用物理页号加上偏移量，得到物理地址。

每个页表项需要4个字节大小来存储。

多级页表

分了二级页表，映射4GB的地址空间就需要4KB(一级页表)+4MB(二级页表)的内存，如此一看内存占用更大了。
如果这4GB虚拟地址全部映射到物理内存上，那么占用空间确实大了，但是往往不会为一个进程分配那么多内存。根据局部性原理，对于大多数程序来说，不需要这么多空间，许多页表项都是空的没有分配。

所以对于使用了二级页表的系统来说，一级页表可以覆盖整个地址空间，而如果一级页表中的某一页表项对应的整个二级页表中的所有页表项都没有被使用，那么就可以只在需要的时候再创建二级页表。

对于64位系统，需要四级目录：

全局页目录 PGD
上层页目录项 PUD
中间页目录项 PMD
页表项 PTE

TLB

在CPU有一个页表缓存TLB，存放最常访问的几个页表项。CPU在寻址时会先查TLB，如果没有找到才会继续查常规页表。

段页式内存管理

先将程序划分为多个段，如代码段、数据段等。
接着把每个段划分为多个页，即对分段划分出连续的空间，再划分固定大小的页。

如此，地址结构就由段号、段内页号、页内偏移三部分组成：

OSTEP中说每个段都有一个页表，地址空间中前两位用来表示使用哪个段。

Linux内存管理

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

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

Linux内存主要采用页式内存管理，但是也用到了段机制：

Linux中每个段都是从0地址开始的整个4GB虚拟空间(32位环境下)，所有的段起始地址都是一样的。所以Linux系统中的代码，包括OS本身的代码，面对的都是线性地址空间。这种做法相当于屏蔽了处理器中的逻辑地址概念，段制备用于访问控制和内存保护。

虽然每个进程有独立的虚拟内存，但是每个虚拟内存中的内核地址，关联的都是相同的物理内存。进程切换内核态后，可以访问内核空间内存。

四、进程与线程

进程

并发与并行的区别：

进程

在一个进程的活动期间至少具备三种基本状态：运行状态、就绪状态、阻塞状态。

运行状态->阻塞状态：进程请求某个事件且必须等待，例如：请求I/O事件。
阻塞状态->就绪状态：进程要等待的事件完成时，就从阻塞状态变为就绪状态。
就绪状态->运行状态：被OS的调度器选中。
运行状态->就绪状态：运行中的进程，分配给它的时间片用完，OS会将它变为就绪状态，并从就绪状态中选择另一个进程运行。

如果有大量处于阻塞状态的进程，进程可能会占用物理内存空间造成浪费。在虚拟内存管理的OS中，通常把阻塞状态的进程的物理内存换出到硬盘，等到需要再次运行时，再从硬盘换入到物理内存。那么就需要一个挂起状态，来描述进程没有占用实际的物理内存空间。

导致进程挂起的原因不只是因为进程使用的内存空间不在物理内存，还包括：

通过**sleep**让进程间歇性挂起，其工作原理是设置一个定时器，到期后唤醒进程；
用户通过**Ctrl+Z**挂起进程。

进程控制结构

进程控制块(PCB)用来描述进程。是进程存在的唯一标识。

PCB包含的信息：

进程描述信息：
- 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符
- 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务
进程控制和管理信息：
- 进程当前状态
- 进程优先级：进程抢占CPU时的优先级
资源分配清单：
- 有关内存地址空间或虚拟地址空间的信息，锁打开文件的列表和所使用的IO设备信息
CPU相关信息：
- CPU中各个寄存器的值，当进程切换时，CPU的状态信息会保存在相应的PCB中，以便进程重新执行时恢复。

PCB组织形式：通过链表形式组织，把具有相同状态的进程链在一起，组成各种队列。
一般会组织成链表，因为可能面临进程创建，销毁等调度导致进程状态发生变化，所以链表能更加灵活的插入和删除。

进程的控制

①创建进程

OS 允许一个进程创建另一个进程，子进程继承父进程的资源，并在结束时将在父进程处继承的资源还给父进程。Linux 对于终止有子进程的父进程，会将子进程交给1号 init进程管理。

创建进程的过程：

为新进程分配唯一的进程标识号，申请一个空白的PCB。PCB是有限的，如果申请失败则创建失败；
为进程分配资源，如果资源不足，进程会进入等待状态，等待资源；
初始化PCB；
如果进程的调度队列能够接纳新进程，就将进程插入到就绪队列。

②终止进程

进程可以有三种终止方式：正常结束、异常结束、外接干预(信号**kill**掉)。

终止进程过程：

查找需要的终止进程的 PCB；
如果处于执行状态则立即终止，并将 CPU 资源分配给其他进程；
如果其还有子进程，将其所有子进程终止(Linux上是将子进程交给养父——1号 init进程)；
将该进程所拥有的全部资源都归还给父进程或OS；
将其从PCB所在队列删除。

③阻塞进程

当进程需要等待某一事件完成时，可以调用阻塞语句把自己阻塞等待。一旦阻塞，只能由另一个进程唤醒。

阻塞进程过程：

找到将要被阻塞进程标识号对应的 PCB；
如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行；
将该 PCB 插入到阻塞队列中。

④唤醒进程

唤醒进程过程：

在该时间的阻塞队列中找到相应进程的PCB
将其从阻塞队列中移出，置其状态为就绪状态
把该PCB插入就绪队列中，等待调度程序调度

进程的上下文切换

进程是由内核管理和调度的，所以进程切换只能发生在内核态。

进程的上下文切换包含虚拟内存、栈、全局变量等用户空间资源，还包括内核堆栈、寄存器等内核空间资源。

通常将交换的信息保存在进程的 PCB，当要运行另外一个进程的时候，从这个进程的 PCB 取出上下文，然后恢复到 CPU，进而继续执行：
发生进程上下文切换有哪些场景：

为了保证所有进程得到公平调度，CPU 时间被划分为一段段时间片，再轮流分配给各个进程。当某个进程被分配的时间片耗尽了，就会变为就绪状态，OS 就会从就绪队列中选择另一个进程执行；
进程在系统资源不足时，要等到资源满足后才可以运行，这时候进程也会被挂起，OS 调度其他进程运行；
当进程通过sleep将自己挂起，也会重新调度；
当有优先级更高的进程运行时，保证高优先级进程先运行，当前进程被挂起；
发生硬件中断。CPU上的进程被中断挂起，执行内核中的终端服务程序。

线程

对于多进程方式，会出现如下问题：

进程之间如何通信，共享数据；
维护进程的系统开销较大，如创建进程时，分配资源、建立PCB；终止进程时，回收资源、撤销PCB；进程切换时，保存当前进程的状态信息。

同一个进程内的多个线程，可以共享代码段、数据段、打开的文件等资源，但每个线程有独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。

HINT：Linux中，实际上线程就是进程，都有一个**task_struct**结构，通过标志位的不同，保证了共享的内容不同，从而实现了进程与线程的区别。

线程的缺点：当进程中的一个线程崩溃时，会导致所属进程的所有线程崩溃。

线程与进程的比较：

进程是资源(内存、打开的文件)分配的单位，线程是CPU调度的单位；
进程拥有一个完整的资源平台，线程只独享必不可少的资源，如寄存器和栈；
线程同样有就绪、阻塞、执行三种状态；
线程能减少并发执行的时间空间开销。

线程相比进程减少开销体现在：

线程的创建时间比进程快，因为在进程创建的过程中，还需要资源管理信息；而线程创建不涉及这些管理，而是共享它们；
线程的终止时间比进程快，因为线程释放的资源比进程少很多；
同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间，意味着同一个进程的线程都具有一个页表，在切换时不需要切换页表。对于进程的切换需要把页表也切换掉，页表的切换开销比较大；
线程之间数据传递不需要经过内核，效率更高。

线程上下文切换：

线程是调度的基本单位，而进程是自愿拥有的基本单位。所以OS的任务调度其实调度对象是线程，进程只是给线程提供了虚拟内存、全局变量等资源。

线程上下文切换的是什么：

当两个线程不属于同一个进程，则切换过程就和进程上下文切换一样
当两个线程属于同一个进程，因为虚拟内存共享，所以切换时虚拟内存这些资源保持不动，只需要切换线程的私有数据、寄存器、栈等不共享数据

线程的实现：

主要有三种线程的实现方式：

用户线程：在用户空间实现的线程；
内核线程：在内核中实现的线程，由内核管理；
轻量级进程：在内核中来支持用户线程。

用户线程

用户线程基于用户态的线程管理库实现，线程控制块(TCB)也是在库里实现的。对于OS来说看不到TCB，只能看到整个进程的 PCB。

所以用户线程的整个线程管理和调度，OS是不直接参与的，而是由用户级线程库函数完成线程的管理，如创建、终止、同步、调度等。

用户线程的优点：

每个进程都需要有它私有的TCB列表，用来记录各个线程状态信息；
用户线程的切换由线程库函数完成，无须用户态与内核态的切换，速度极快。

用户线程的缺点：

OS不参与线程调度，如果一个线程发起系统调用而阻塞，那进程包含的用户线程都无法执行了；
当一个用户线程开始运行后，除非主动交出CPU使用权，否则它所在进程中其他线程无法运行。因为用户态的线程无法打断当前运行中的线程；
由于时间片分配给进程，所以多线程执行时，每个线程得到的时间片较少，执行比较慢。

内核线程

内核线程由 OS 负责管理，线程对应的 TCB 放在OS中。

一个用户线程对应一个内核线程：
内核线程的优点：

在一个进程中，如果某个内核线程发起系统调用而被阻塞，不会影响其他内核线程的运行；
时间片分配给线程，多线程的进程获得更多的 CPU 运行时间

内核线程的缺点：

在支持内核线程的 OS 中，由内核来维护进程和线程的上下文信息，如 PCB 和 TCB；
线程的创建、终止和切换都通过系统调用，系统开销较大；而用户级线程都是通过线程库来管理。

4.1 调度算法

如果硬件时钟提供某个频率的周期性中断，那么可以把调度算法分为两类：

非抢占式调度算法，挑选一个进程，运行直到被阻塞或退出，才会调用另一个进程，也就是不会理会时钟中断
抢占式调度算法，挑选一个进程让它只运行一段时间，如果在该时段结束时仍在运行，那么就将它挂起，调度程序从就绪队列挑选另外一个进程。这种调度需要在时间间隔的末端发生时钟中断，以便把CPU控制权交还给调度程序。

调度原则：

CPU利用率：调度程序应确保CPU是始终匆忙，可以提高利用率；
系统吞吐量：吞吐量表示单位时间内CPU完成进程的数量，长作业的进程会占用较长的CPU资源，会降低吞吐量；反之短作业会提升系统吞吐量；
周转时间：是进程运行和阻塞时间总和，越小越好；
等待时间：进程处于就绪队列的时间，等待时间越长，用户越不满意；
响应时间：用户提交请求到系统第一次产生相应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

调度算法：

①先来先服务(FCFS)
每次从就绪队列选择最先进入队列的进程，然后一直运行直到进程退出或被阻塞。

如果有一个长作业先运行，那么后面的短作业等待的时间就会很长，不利于短作业。适合 CPU 繁忙型作业的系统，不利于 IO 繁忙型作业的系统

②最短作业优先(SJF)
优先选择运行时间最短的进程运行，有利于提高系统吞吐量。

显然对长作业不利，一个长作业在就绪队列等待运行，而该队列有许多短作业，那么就会使长作业不断往后推，等待时间变长，导致长作业长期不会被运行。

③高响应比优先调度算法(HRRN)
该算法主要权衡了短作业和长作业。每次进行进程调度时，先计算响应比优先级，然后把响应比优先级最高的进程投入运行：
可以发现：

如果两个进程的等待时间相同时，要求服务时间越短，响应比就越高，这样短作业的进程容易被选中；
如果两个进程要求服务时间相同时，等待时间越长，响应比就越高，这就兼顾到长作业进程了，因为长作业进程的响应比会随着它不断后移、等待时间不断变长而提高，当等待时间足够长时，就获得了运行机会

④时间片轮转调度算法(RR)
最简单、最公平且使用最广。
每个进程被分配一个时间段，称为时间片，即允许该进程在该时间段中运行。
时间片一般设为**20ms~50ms**，比较合理。

⑤最高优先级调度算法(HPF)

进程的优先级可以分为静态优先级和动态优先级：

静态优先级：创建进程时，就已经确定优先级，整个运行时间都不会改变
动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级；如果进程等待时间增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。

也有可能会导致低优先级的进程永远不会运行。

⑥多级反馈队列调度算法(MFQ)

是时间片轮转算法和最高优先级算法的综合。

多级表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短
反馈表示如果有新的进程加入优先级高的队列，立刻停止当前进程，转而去运行优先级高的队列

设置多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
新的进程会被放入第一级队列的末尾，按照先来先服务原则排队等待调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列末尾，以此类推直至完成；
当较高优先级队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新的进程进入较高优先级的队列，则停止当前运行的进程，并将其移入原队列末尾，接着让较高优先级的进程运行。

4.2 进程间通信

每个进程的用户地址空间都是独立的，一般不能互相访问，但是内核空间是每个进程共享的，所以进程间通信必须通过内核。

管道

匿名管道：

shell中的|是一个匿名管道，用完就销毁，功能是将前一个命令的输出作为后一个命令的输入。所以管道传输数据是单向的，要相互通信，需要创建两个管道。

命名管道：

命名管道也被称为FIFO，在使用之前mkfifo命令创建并指定管道名字:

将数据写入管道后，会卡住….管道等待清空。在管道里的数据被读取完后，命令才可以退出。

所以管道通信效率低，不适合进程间频繁交换数据。但是可以很容易地得知管道内数据被读取。

管道原理：
匿名管道的创建，通过系统调用pipe()：

int pipe(int fd[2])

返回两个描述符，管道读取端描述符fd[0]，和管道写入端描述符fd[1]。该匿名管道是特殊的文件，只存在于内存，不存在文件系统中。

其实管道就是内核里的一串缓存。写入数据实际上是缓存在内核中的，读取时也是从内核中读取。管道传输是无格式的流且大小受限。

此时两个描述符都在一个进程中，并没有起到进程间通信的作用；使用fork()创建子进程，创建的子进程会复制父进程的文件描述符，两个进程就都有fd[0]和fd[1]，通过读写同一个管道文件实现跨进程通信。

但是不限制两个进程的读写，就会造成混乱，所以两个进程分别关闭fd[0]和fd[1]。

HINT：在shell中执行A|B命令时，A进程和B进程都是shell创建出的子进程，二者不存在父子关系：

消息队列

管道通信效率低，不适合进程间频繁交换数据。

消息队列可以解决该问题。只需要将进程要发送的信息放到对应的消息队列后就可以正常返回，另一个进程需要的时候再去读取数据即可。

消息队列是保存在内核中的消息链表，在发送数据时，会分成一个个独立的数据单元(消息体)，消息体是用户自定义的数据类型，收送方约定好消息体的数据类型，每个消息体都是固定大小的存储块。内核在消息体被读取后删除。

消息队列生命周期随内核。如果没有释放消息队列或没有关闭操作系统，消息队列就会一直存在。

消息队列不适合比较大的数据传输，因为内核中每个消息体都有一个最大长度的限制，同时所有队列包含的全部消息体总长度也有上限。在 Linux 内核中，有两个宏定义：MSGMAX和MSGMNB，它们以字节为单位，分别定义了一条消息的最大长度和一个队列的最大长度。
消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销。

共享内存

消息队列的读写会发生用户态和内核态的消息拷贝。共享内存方式解决该问题。

共享内存的机制，就是拿出一块虚拟地址空间，映射到相同那部分的物理内存中：

信号量

在共享内存方式中，如果多个进程同时修改同一块共享内存，很有可能冲突。为了防止多进程竞争共享资源，就需要保护机制：信号量。
信号量实质上是一个整形计数器，用于实现进程间的互斥与同步。有P操作和V操作：

P操作，将信号量-1，若信号量<0，表示资源已被占用；若>=0，表示还有资源可用，进程可正常进行
V操作，将信号量+1，若信号量<=0，表示当前有阻塞中的进程，会将该进程唤醒；若>0，则表示当前没有阻塞的进程。

P操作用于进入共享资源前，V操作用于离开共享资源之后，必须成对出现。

信号初始化为1，代表互斥量，可以保证共享内存在任何时刻只有一个进程在访问。
信号初始化为0，代表同步信号量，保证进程A在进程B之前执行：

信号

异常情况下，使用信号的方式来通知进程。

在 Linux 中，使用kill -l命令查看所有信号：

键盘组合会给运行在shell终端的进程发送信号：

Ctrl+C产生SIGINT信号，表示终止该进程
Ctrl+Z产生SIGSTOP信号，表示停止该进程，但还未结束

如果进程运行在后台，可以kill命令给进程发送信号，但是需要提前知道该进程号，e.g. :

kill -9 1050表示给PID为1050的进程发送SIGKILL信号，立刻结束该进程。

信号是进程间通信机制中，唯一的异步通信机制，因为可以在任何时候发送信号给某一进程。

用户进程对信号的处理方式有：

执行默认操作：Linux 对每种信号都规定了默认操作，即产生信号的时候默认进行的事情。
捕捉信号：可以为信号定义一个信号处理函数(signal handler)。当信号发生时，调用相应的信号处理函数。
忽略信号：不希望处理某些信号时就可以忽略。但是有两个信号无法捕捉和忽略：SIGKILL和SIGSTOP，用于在任何时候中断或结束某一进程。

Socket

跨网络与不同主机上的进程之间通信，就需要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原本用来指定通信协议，现在废弃，前两个参数全包了；现在写成0即可。

4.3 多线程同步

竞争与协作

线程是调度的基本单位，进程则是资源分配的基本单位。所以鲜橙汁件共享进程的资源，但是每个线程都有自己独立的栈空间。

互斥：保证一个线程在玲姐去执行时，其他线程应该被阻止进入临界区。

互斥与同步的实现和使用

主要方式有两种：

锁：加锁、解锁操作
信号量：P、V操作

锁

任何想进入临界区的线程，必须先执行加锁操作，若加锁顺利则可以进入临界区；在完成对临界区资源访问后执行解锁操作，以释放该临界资源。

根据锁的实现不同，分为忙等待锁(自旋锁)和无忙等待锁：

具体实现看《操作系统导论》第28章

信号量

通常信号量表示资源的数量，对应的变量是一个整形(sem)变量。
有两个原子操作的系统调用来控制信号量：

P操作，将信号量-1，若信号量<0，表示资源已被占用；若>=0，表示还有资源可用，进程可正常进行
V操作，将信号量+1，若信号量<=0，表示当前有阻塞中的进程，会将该进程唤醒；若>0，则表示当前没有阻塞的进程。

只需要把进入临界区的操作置于P(s)和V(s)之间，即可实现互斥

TODO：几种经典互斥问题，死锁

4.5 悲观锁和乐观锁

互斥锁与自旋锁

互斥锁和自旋锁对于加锁失败后的处理方式是不一样的：

互斥锁加锁失败后，线程会释放CPU，给其他线程
自旋锁加锁失败后，线程会忙等待、一直占用CPU资源，直到它拿到锁

互斥锁是一种独占锁，如果锁已被持有，那么线程B的加锁会失败，将CPU释放给其他线程，此时线程B的加锁代码就会被阻塞。由内核来处理，内核将加锁失败的线程置为睡眠状态，等待锁被释放后唤醒：
所以，互斥锁加锁失败时，会带来两次线程上下文切换成本：

加锁失败时，内核把线程的状态改为睡眠，将CPU资源发配给其他线程运行；
当锁被释放后，睡眠状态的线程会变为就绪状态，内核在合适时间将CPU资源分配给它。

如果确定被锁住的代码执行时间很短，就不应该用互斥锁，而是自旋锁。

但是如果在单核CPU上使用自旋锁，需要抢占式调度器(不断通过时钟中断一个线程，运行其他线程)。否则，自旋锁在单核CPU上无法使用，因为一个自旋等待的线程永远无法放弃CPU。

读写锁

由读锁和写锁构成，用于能明确区分读操作和写操作的场景。

写锁是独占锁，因为任何时刻只能有一个线程持有写锁；而读锁是共享锁，因为读锁可以被多个线程同时持有。

读优先锁：读锁能被更多线程持有，以便提高读线程的并发性；写线程一直被阻塞，直到所有读线程释放锁，写线程才能获得写锁。

写优先锁：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 获取读锁时会失败，于是读线程 C 将被阻塞在获取读锁的操作，这样只要读线程 A 释放读锁后，写线程 B 就可以成功获取读锁。

读优先锁和写优先锁都会导致对方的饿死问题，可以采用公平读写锁：

用队列把获取锁的线程排队，不管是写线程还是读线程都按照先进先出的原则加锁即可。

乐观锁与悲观锁

互斥锁、自旋锁、读写锁，都属于悲观锁。

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

如果多个线程同时修改共享资源的概率比较低，就可以采用乐观锁。

乐观锁做事比较乐观，它假定冲突概率较低。工作原理：先修改完共享资源，再验证这段时间内有没有发生冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作。

所以乐观锁也叫无锁编程。在线文档、SVN和Git也都是运用了乐观锁思想。

由于重试成本非常高，所以只有在冲突概率非常低。且加锁成本非常高的场景，才考虑使用乐观锁。

五、调度算法

5.1 进程调度/页面置换/磁盘调度算法

进程调度算法

参见段落4.1 写的非常清楚

内存页面置换算法

缺页中断的处理流程：

上面的缺页异常处理程序，成功的前提是第四步能在物理内存中找到空闲页。如果找不到空闲页，说明内存已满。此时需要页面置换算法选择一个物理页，如果该物理页有被修改过(脏页)，则把它换出磁盘，然后把该置换出去的页表项的状态改成无效，最后把正在访问的页面装入到物理页中。

页表项字段：

最佳页面置换算法

置换在未来最长时间不访问的页面。所以需要计算内存中每个逻辑页面的下一次访问时间，然后比较，选择未来最长时间不访问的页面。

很理想，但是在实际系统中无法实现，因为程序访问页面是动态的，无法预知每个页面在下一次访问前的等待时间。所以最佳页面置换算法只是为了衡量可实现算法的效率

先进先出置换算法

可以选择在内存中驻留时间很长的页面进行置换。

可惜性能较差。

最近最久未使用置换算法 (LRU)

发生缺页时，选择最长时间没有被访问的页面进行置换。该算法假设已经很久没有使用的页面，很有可能在未来一段时间内仍然不会被使用。

需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最少使用的在表尾。每次访问内存时都要更新整个链表。

时钟页面置换算法

将所有页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。

当发生缺页中断时，首先检查表针指向的页面：

如果它的访问位是0，就淘汰该页面；并把新的页面插入这个位置，然后把表针前移一个位置
如果访问位是1就清除访问位，并把表针前移一个位置，重复这个过程直到找到一个访问位为0的页面为止，

最不常用算法 (LFU)

当发生缺页中断时，选择访问次数最少的那个页面，并将其淘汰。

实现方式：
对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器就累加1.在发生缺页中断时，淘汰计数器值最小的那个页面。

六、文件系统

6.1 文件系统

文件系统基本组成

Linux文件系统为每个文件分配两个数据结构：索引节点和目录项。

索引节点，就是inode，用来记录文件的元信息。是文件的唯一标识，索引节点同样占用磁盘空间。
目录项，就是dentry，记录文件名字、索引节点指针以及与其他目录项的层级关联关系。目录项是由内核维护的数据结构，不存放于磁盘，而是缓存在内存。

文件数据存储在磁盘的方式

磁盘读写的最小单位是扇区，扇区的大小只有512B。如果每次读写都以这么小为单位，效率会非常低。所以文件系统把多个扇区组成一个逻辑块，每次读写的最小单位就是逻辑块，大小为4KB。

索引节点、目录项和文件数据的关系如下：
磁盘格式化的时候，会被分成三个存储区域，分别是：超级块、索引节点区和数据块区。

超级块：存储文件系统详细信息，如块个数、块大小和空闲块。
索引节点区：存储索引节点。
数据块区：存储文件或目录数据。

内存无法容纳所有的超级块和索引节点区，所以只有当需要使用的时候，才将其加载进内存：

超级块：当文件系统挂载时进入内存
索引节点区：当文件被访问时进入内存

虚拟文件系统

在用户层和文件系统层之间引入了中间层：虚拟文件系统(VFS)，用以对用户提供统一的接口。

感觉存储位置不同，可以把文件系统分为三类：

磁盘的文件系统：直接把数据存储在磁盘中，比如 Ext 2/3/4、 XFS等等，都是这类文件系统
内存的文件系统：不存储在磁盘中，而是占用内存空间，比如**/proc**和**/sys**文件系统，读写这类文件，实际上是读写内核中的相关数据。
网络的文件系统：用于访问其他计算机主机上的数据的文件系统。

文件系统首先要挂载到某个目录才可以正常使用，比如Linux系统在启动时，会把文件系统挂载到根目录。

文件的使用

打开一个文件后，OS会跟踪进程打开的所有文件，为每个进程维护一个打开文件表，文件表中每一项代表文件描述符。

读写文件的过程：

当用户进程从文件中读取1个字节大小的数据时，文件系统要获取字节所在的数据块，再返回数据块对应的用户进程所需的数据部分
当用户进程把1个字节大小的数据写入文件时，文件系统找到需要写入数据的数据块位置，然后修改数据块中对应的部分，最后再把数据块写回磁盘。

所以，文件系统的基本操作单位是数据块。

文件的存储

文件存储有两种方式：连续空间存放方式、非连续空间存放方式。

连续空间存放方式

文件存放在连续的物理空间中，文件数据都是紧密相连的，读写效率高，一次磁盘寻道就可以读出整个文件。这种存放方式的前提是：必须先知道一个文件的大小。这样文件系统才会根据文件大小在磁盘上找到一块连续的空间分配给文件。

文件头类似于Linux中的**inode**。

所以，文件头里需要指定起始块的位置和长度：

虽然读写效率高，但是会由磁盘空间碎片和文件长度不易扩展的缺陷。

非连续空间存放方式

非连续存放方式分为链表方式和索引方式。

链表方式：

链表的方式是离散的，不用连续的，所以可以消除磁盘碎片。同时文件的长度可以动态扩展。

使用显式链接方式实现，把用于链接文件各数据块的指针，显式存放在内存的一个链接表中。每个表项中存放链接指针，指向下一个数据块号。

优点：提高了检索速度，而且大大减少了访问磁盘的次数。
缺点：但是因为整个表都存放在内存中，所以不适用于大磁盘。

索引方式：

链表方式解决饿连续分配的磁盘碎片和文件动态扩展问题，但是不能有效支持直接访问。

索引的实现是为每个文件创建一个索引数据块，里面存放指向文件数据块的指针列表。类似书的目录，要找哪个章节直接看目录查即可。

此外，文件头需要包含指向索引数据块的指针，这样就可以通过文件头直到索引数据块的位置，再通过索引数据块里的索引信息找到对应的数据块。

创建文件时，索引块的所有指针都设为空。当首次写入第i块时，先从空闲空间取得一个块，再将其地址写到索引块的第i个条目。
索引的方式优点：

文件的创建、增大、缩小很方便
不会有碎片的问题
支持顺序读写和随机读写

因为索引数据块也是存放在磁盘块的，所以如果文件很小，只需要一个块就可以存放得下，但是还需要额外分配一块来存放索引数据块，所以缺陷之一就是存储索引带来的开销。

如果文件很大，大到一个索引数据块放不下索引信息，可以使用链表+索引和索引+索引的方式处理大文件存储。

链表+索引：
链式索引块，实现方式是在索引数据块留出一个存放下一个索引数据块的指针。当一个索引块的信息要用完了就可以通过指针找到下一个索引数据块的信息。

索引+索引：
多级索引块，实现方式是通过一个索引块来存放多个索引数据块，有点像多级页表。。

几种文件实现方式的比较：

空闲空间管理

空闲空间管理法主要有以下几种：

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

空闲表法：
为所有空闲空间建立一张表，表内容包括空闲区的第一个块号和该空闲区的块个数，这个方式是连续分配的。

当请求分配磁盘空间时，系统依次扫描空闲表里的内容，直到找到一个合适的空闲区域为止。
当用户撤销一个文件时，系统回收文件空间，也需顺序扫描空闲表，寻找一个空闲表条目并将释放空间的第一个物理块号及它占用的块数填到这个条目中。

如果存储空间中有大量小的空闲区，那么空闲区表会变得很大，查询效率会很低。
这种分配技术适用于建立连续文件。

空闲链表法：
每一个空闲块中有一个指针指向下一个空闲块，可以方便找到空闲块并管理：
缺点：不能随机访问，工作效率低。

无论是空闲表法还是空闲链表法都不适合大型文件系统，因为会使空闲表或空闲链表太大。

位图法：
利用二进制的一位来表示磁盘中一个盘块的使用情况。

Linux文件系统就使用位图来管理空闲空间。

文件系统的结构

Linux中采用块组这个结构：

第一个块是引导块，在系统启动时用于引导。

超级块：包含文件系统的重要信息，如inode总个数、块总个数、每个块组的inode个数、每个块组的块个数
块组描述符：包含文件系统中各个块组的状态，比如块组中空闲块和inode的数目等
数据位图和inode位图：表示对应的数据块或inode是否空闲
inode列表：包含块组中所有的inode
数据块：包含文件的真实数据

每个块组有很多重复信息，超级块和块组描述符表都是全局信息，所以每个块组中的它们都是一样的。原因如下：

如果系统崩溃破坏了超级块或块组描述符，有关文件系统结构和内容的所有信息都会丢失。如果有重复的副本，那么是有可能恢复的。
通过使文件和管理数据尽可能接近，减少了磁头寻道和旋转，可以提高文件系统的性能。

目录的存储

在Linux中，目录其实也是文件。它也有inode，inode中也是指向一些块。

普通文的块中保存文件数据，而目录文件的块中保存的事目录里一项项的文件信息。

在目录文件的块中，最简单的保存方式就是列表，将目录底下的文件信息列在表中：

保存目录格式为哈希表，对文件名进行哈希计算，把哈希值保存起来。

目录查询是在磁盘上反复搜索完成的，需要大量I/O，为了减少I/O操作，把当前使用的文件目录缓存在内存，以后使用该文件时只需要在内存中操作，降低了磁盘I/O，提高了文件系统的访问速度。

软链接和硬链接

在Linux中，给文件取别名可以通过硬链接和软链接来实现。

硬链接是多个目录项中的索引节点指向一个文件，也就是指向同一个inode，但是inode无法跨越文件系统，所以硬链接不可用于跨文件系统。

由于多个目录项都指向一个inode，所以只有删除文件的所有硬链接和源文件时，系统才会彻底删除该文件。

软链接相当于重新创建一个文件，有独立的inode，但是这个文件的内容是另外一个文件的路径，所以访问软链接时，实际上是访问源文件的。所以软链接时可以跨文件系统的。如果源文件被删除了，链接文件仍然存在，只是指向的文件无法找到。

文件I/O

文件的读写方式有很多分类：

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

缓冲与非缓冲I/O

文件操作的标准库可以实现数据的缓存，根据是否利用标准库缓冲，可以把文件I/O分为缓冲和非缓冲：

缓冲I/O：利用标准库的缓存实现文件的加速访问，而标准库再通过系统调用访问文件；
非缓冲I/O：直接通过系统调用访问文件，不经过标准库缓存。

许多程序直到换行时才真正输出，而换行前的内容，其实是被标准库暂时缓存起来，这样做可以减少系统调用的次数，因为系统调用是有CPU上下文切换的开销的。

直接与非直接I/O

Linux为了减少磁盘I/O次数，在系统调用后，会把用户数据拷贝到内核中缓存起来，这个内核缓存空间就是页缓存，只有缓存满足某条件时，才发起磁盘I/O请求。

根据是否利用OS缓存，可以把文件I/O分成直接和非直接：

直接I/O：不会发生内核缓存和用户程序之间的数据复制，而是直接经过文件系统访问磁盘；
非直接I/O：读操作时，数据从内核缓冲中拷贝给用户程序，写操作时没数据从用户程序拷贝给内核缓存，再由内核决定何时写入数据到磁盘。

如果使用文件操作类系统调用时，指定了O_DIRECT标志，则表示直接I/O，否则默认非直接I/O。

以下几种场合会触发内核缓存的数据写入磁盘：

在调用write的最后，当发现内核缓存的数据太多时，会把数据写到磁盘上；
用户主动调用sync，内核缓存会刷到磁盘上；
当内存紧张，无法再分配页面时，内核缓存也会刷到磁盘上；
内核数据的缓存时间超过限定时间了，也会刷到磁盘上。

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

阻塞I/O：当用户程序执行read时，线程会被阻塞，一直等到内核数据准备好，并把数据从内核缓冲区拷贝到程序的缓冲区中，拷贝完成后，read才返回。

非阻塞I/O：非阻塞的read在数据未准备好的情况下立即返回，可以继续往下执行，此时用户程序不断轮询内核，直到数据准备好，内核将数据拷贝到程序缓冲区，read调用才可以获取结果。
此处最后一次read调用，获取数据的过程是一个同步的过程，需要等待。(同步指的是内核态的数据拷贝到用户程序的缓存区这个过程)

e.g. 访问管道或socket时，如果设置了O_NOBLOCK标志，就表示使用的是非阻塞I/O，否则默认阻塞I/O

如果采用非阻塞I/O，那么用户程序需要不断轮询内核，在此期间用户程序啥也做不了，相当于自旋锁(?)

采用I/O多路复用技术，如select、poll，它是通过I/O事件分发，当内核数据准备好时，再以时间通知应用程序进行操作。
此举改善了用户程序对CPU的利用率，在没有被通知的情况下，应用进程可以使用CPU做其他事。

但是此时的read获取数据的过程也是一个同步的过程，需要等待：

无论是阻塞 I/O、非阻塞 I/O，还是基于非阻塞 I/O 的多路复用都是同步调用。因为它们在read调用时，内核将数据拷贝到用户程序空间，过程都是需要等待的，意即如果内核实现的拷贝效率不高，read调用就会在同步过程中等待较长时间。

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

当发起aio_read后，便立即返回，内核自动将数据从内核空间拷贝到用户程序空间，该拷贝过程是异步的，内核自动完成，而不用用户程序主动发起拷贝操作。

计算机基础

小林coding图解系统