进程与线程的概念

基本概念：

进程是对运行时程序的封装，是系统进行资源调度和分配的的基本单位，实现了操作系统的并发；

线程是进程的子任务，是CPU调度和分派的基本单位，用于保证程序的实时性，实现进程内部的并发；线程是操作系统可识别的最小执行和调度单位。每个线程都独自占用一个虚拟处理器：独自的寄存器组，指令计数器和处理器状态。每个线程完成不同的任务，但是共享同一地址空间（也就是同样的 动态内存，映射文件，目标代码等等），打开的文件队列和其他内核资源。

区别：

• 通信：由于同一个进程间共享内存资源，因此线程间的通信较简单，通过简单的全局变量即可，也可以结合信号量，互斥量等实现互同步互斥等。而进程间的通信需要通过内核，借助IPC方式
• 开销：线程的切换开销小。由于每个进程的资源是独立分配的，因此进程的创建和销毁都伴随着资源分配和释放，创建更慢。而一个进程中的多个线程只需要分配独立的栈，其他的资源则是共享的，因此创建开销小。同时线程的切换速度也快，因为进程的地址空间是独立的，进程之间的页表不同，当进程切换，页表需要重新从内存（或外存）中重新加载到缓存中（多级页表可能是分布式存储需要从外存加载）使得切换速度慢，而同一进程的线程切换只需要设置少量的cpu寄存器状态即可。
• 调试和应用场景：线程调试困难可靠性低，一个线程挂掉会导致整个进程挂掉，适合多核场景；进程调试简单可靠性高，一个进程崩掉不会影响其他的进程，且多核多机的场景都适合。
• 性质：线程是任务调度的最小单位，而进程是资源分配的最小单位

从Linux实现上，它其实并没有专门区分进程和线程的概念。它使用了相同函数去创建进程/线程，通过设置是否共享资源的入口参数来创建进程/线程。

多进程和多线程的使用场景

多进程应用场景

• 例如 谷歌浏览器的每个页面就是一个单独的进程
• 电脑中每个软件就是一个独立的进程，这个软件崩了不会影响其他的软件
• 多机分布式环境

多线程场景

• 需要频繁创建和销毁的场景使用线程效率更高，例如web服务器处理客户的连接，一个线程一个连接
• 对于需要频繁的数据共享的场景，使用线程可以降低通信的开销
• 对于需要快速响应的场景，例如GUI界面，如果算法耗时很多，就会导致界面假死无法响应用户的请求

内核线程和用户线程

这里讲的用户线程是编译层面通过编程语言实现的用户线程，即协程。内核线程就是常规的线程（还有一种内核线程的称呼是指只运行在内核态的线程，是操作系统创建的用于完成操作系统事务的线程，也叫守护线程，它和普通的线程一样被同等调度）但是这里讨论的实际是协程和线程的区别。

协程是用户在编译器层面使用编程语言模拟出的线程，不通过系统调用，不用陷入内核，这时候创建新线程比较快，这就是用户线程。多个协程运行在一个线程上，OS感知不到协程的存在，它只是对承载这些协程的线程进行调度，因此如果协程中有IO阻塞操作导致线程被阻塞，那么所有的协程都无法再被调度。这种情况需要程序员自己避免，可以使用异步IO代替阻塞IO，手动调度协程。

而常规的线程是 由操作系统维护的，它的创建和调度都要从用户态陷入内核态，所以线程的切换代价高于协程。但是由于操作系统调度，所以不会因为一个线程的IO阻塞而饿死其他线程。

协程的优点：

• 协程极高的执行效率。因为子程序切换不是线程切换，而是由程序自身控制，因此，没有线程切换的开销，和多线程比，线程数量越多，协程的性能优势就越明显
• 第二大优势就是不需要多线程的锁机制，因为只有一个线程，也不存在同时写变量冲突，在协程中控制共享资源不加锁，只需要判断状态就好了，所以执行效率比多线程高很多

为什么进程切换比线程慢

首先无论进程还是线程切换都需要保存寄存器值，例如SP 栈寄存器，PC程序计数器指向下一条要执行的指令，EAX累加寄存器，用于加法乘法的确信寄存器等。但是 每个进程都有自己的虚拟地址空间， 进程内的所有线程共享进程的虚拟地址空间，进程切换涉及虚拟地址空间的切换而线程不会。把虚拟地址空间转换为物理地址是通过页表实现的，为了加速页表的查找速度，通常要使用缓存来存储常用的地址映射，即TLB。每个进程有自己的页表，当进程切换后，缓存就失效了，导致命中率低，那么虚拟地址转换为物理地址就会变慢，表现出来的就是程序运行会变慢，而线程切换则不会导致TLB失效，因为线程线程无需切换地址空间，因此我们通常说线程切换要比较进程切换快，原因就在这里。（为了加速虚拟地址的转换速度，会将常用的地址映射存放在缓存中，进程切换，页表也改变会导致缓存命中率低，同时就需要重新从内存中将新的页表加载进缓存，所以进程切换比线程切换慢的原因就在这儿）

进程间通信的方式

进程间通信主要包括管道、消息队列、信号量、信号、共享内存、以及套接字socket。

1. 管道：分为无名管道 和 有名管道，他们都只支持半双工的通信，通信时接收双方必须同时存在，由于传输的是字节流，需要程序自行定义通信协议。管道是存在于内存中，只是形式和文件类似，当消息被读取出便不再存在。

   • 无名管道：只能用于有亲缘关系的进程之间通信。

   • 有名管道：有路径名称与之关联，以一种特殊的文件形式存在于内存中。所以可以用于没有关系的进程之间通信。

2. 消息队列：消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标记。 (消息队列克服了信号传递信息少，管道只能承载无格式字节流以及缓冲区大小受限等特点)具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息；

   • 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。
   • 消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除
   • 消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取

3. 信号量：是一个计数器，用来控制进程间的同步或互斥访问。

   • 如果要传递信息，则需要结合共享内存，来实现同步或者互斥访问
   • 信号量基于 操作系统 的 P V操作，程序对信号的操作都是原子操作
   • P V，不仅只能对信号量的减加 还 可以加减任意正整数 当信号量为0时，进程休眠
   • 支持信号量组

4. 信号： 用于通知接收进程某个事件已经发生

5. 共享内存：它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等

   • 是速度最快的一种 IPC 因为 进程是直接对内存进行存取
   • 因为多个进程可以同时操作，所以需要进行同步。信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问

6. 套接字SOCKET：它用于不同主机之间的进程通信

线程间通信的方式：

1. 临界区：通过多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。如果有多个线程试图同时访问临界区，那么 在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。 * EnterCriticalSection() 进入临界区
   • LeaveCriticalSection()离开临界区
2. 互斥量Synchronized/Lock：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。
3. 信号量 Semphare：为控制具有有限数量的用户资源而设计的，它允许多个线程在同一时刻去访问同一个资源，但一般需要限制同一时刻访问此资源的最大线程数目。
4. 事件(信号)，Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作

对比：临界区是非内核对象，它运行在用户态，因此只能用于同一个进程中的线程之间的互斥访问，但是临界区的效率是最高的。而后面都是内核对象可以用于不同进程的线程之间的同步互斥。

Linux虚拟地址空间

程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。还有进程运行过程中，要动态分配内存，比如 malloc时，也只是分配了虚拟内存，即为这块虚拟内存对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。

好处：

1. 可以控制物理内存的访问权限，对特定的地址设置保护，防止在用户模式下执行错误的指令而意外改写内核数据
2. 每个进程的地址空间独立，通过页表映射到物理地址，可以防止不同进程之间相互干扰，一个进程无无法访问其他进程的地址空间
3. 通过页面的换入换出可以在小内存中运行大程序。另一方面由于逻辑地址不是全部都映射到具体的物理地址的，只有在读写时引发缺页异常才会进行映射，因此可以在内存上同时保留多个进程，提高系统的并发度
4. 可以将连续的逻辑地址映射到不连续的物理地址上，提高内存利用率

虚拟内存的代价：

1. 虚存的管理需要建立很多数据结构，这些数据结构要占用额外的内存
2. 虚拟地址到物理地址的转换，增加了指令的执行时间
3. 页面的换入换出需要磁盘I/O，这是很耗时的
4. 如果一页中只有一部分数据，会浪费内存

请你回答一下为什么要有page cache，操作系统怎么设计的page cache

加快从磁盘读取文件的速率。page cache 中有一部分磁盘文件的缓存，因为从磁盘中读取文件比较慢，所以读取文件先去page cache 中去查找，如果命中，则不需要去磁盘中读取，大大加快读取速度。

当系统需要读取某个文件的对应位置的数据时，首先根据打开的文件的 inode 找到 address_space 结构，address_space是建立内存和文件关联的桥梁，其中保存有该文件的 基数树，通过文件的偏移 在基数树中查找页缓存，如果缓存命中直接读取，否则分配一块缓存页并将磁盘中的对应数据拷贝到内存缓存页中。（最后害有一个双向链表来实现LRU？）

操作系统程序的内部结构

32位系统 一个程序的可寻址空间位 4G ， 其中0-3G是用户态空间，3-4G是内核空间。从低地址到高地址，依次为代码段，数据段，bss段，堆区，mmap映射区，栈区。

• 代码段：存放的是机器代码 和 字符常量，只读，在可执行文件生成的时候以已经写入。
• 数据段：存放的是初始化了的且初始值不为0的全局变量和局部静态变量。在可执行文件生成的时候已经写入。
• bss段：存放的是初始值为0或者未初始化的全局变量或者静态变量，单独分出这个区域的目的是减少可执行文件的尺寸，在可执行文件中只记录该区域的大小。
• 堆区：前三个大小都是固定的。后两个是在程序运行时新增的区域。堆区为程序员动态分配的空间，在运行中可以动态改变，由低地址向高地址生长。堆的效率比栈要低的多。
• 栈区：用于存放函数调用时函数的返回值，返回地址等信息，该部分内存由操作系统管理，栈区是从高地址位向低地址位增长的，是一块连续的内存区域，并且每个栈的最大地址有限制，超出了会异常。

缺页中断

malloc mmap 函数分配空间只是分配的虚拟内存，只有当程序访问虚拟空间，并发现虚拟内存和物理内存没有建立映射关系时，就会出发缺页中断。在请求分页系统中，可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。

缺页本身是一种中断，与一般的中断一样，需要经过4个处理步骤：

1. 保护CPU现场
2. 分析中断原因
3. 处理缺页中断
4. 恢复CPU现场，继续执行

但是缺页中断所要访问的页面不在内存时，由硬件所产生的一种特殊的中断，因此与一般中断存在的区别是：

1. 在指令执行期间产生和处理缺页中断信号
2. 一条指令在执行期间，可能产生多次缺页中断
3. 缺页中断返回是，执行产生中断的一条指令，而一般的中断返回是，执行下一条指令。

请你回答一下fork和vfork的区别

1
2
3
4

#include <sys/types.h>
#include <unistd.h>
pid_t fork(void);
pid_t vfork(void);

1. fork的发展：但是在早期 Unix系统中，调用fork，fork创造的子进程是父进程的完整副本，复制了父亲进程的资源，包括内存的内容和task_struct内容。逐页的复制方式是十分耗时的。现代的Unix系统采用了写时复制的方法，而不是对父进程空间进程整体复制。
2. 为何会有vfork： 由于早期 fork 全盘复制的弊端，常规用途中 往往直接在子进程中使用 exec 加载其他映像文件，并不需要全部复制父进程的东西。因此 出现了vfork 。
3. vfork 作用： vfork( ) 避免了地址空间的按页复制。在这个过程中，父进程和子进程共享相同的地址空间和页表项。实际上vfork( )只完成了一件事：复制内部的内核数据结构。因此，子进程也就不能修改地址空间中的任何内存。而且子进程将先于父进程运行，只有在 子进程调用 exec 或者 _exit 时，才会唤醒父进程。
4. 写时复制：写时复制是一种采取了惰性优化方法来避免复制时的系统开销。如果有多个进程要读取它们自己的那部门资源的副本，每个进程只要保存一个指向这个资源的指针就可以了。如果一个进程要修改自己的那份资源“副本”，那么就会复制那份资源，并把复制的那份提供给进程，这个进程就可以修改复制后的资源了，同时其他的进程仍然共享那份没有修改过的资源。
5. 写时复制的具体实现：在使用虚拟内存的情况下，写时复制（Copy-On-Write）是以页为基础进行的。所以，只要进程不修改它全部的地址空间，那么就不必复制整个地址空间。如果有进程试图修改一个页，就会产生一个缺页中断。内核处理缺页中断的方式就是对该页进行一次透明复制。这时会清除页面的COW属性，表示着它不再被共享。

fork 与 vfork 区别：

1. fork( )的子进程拷贝父进程的数据段和代码段；vfork( )的子进程与父进程共享数据段 直至子进程使用execve启动新的应用程序为止
2. fork( )的父子进程的执行次序不确定；vfork( )保证子进程先运行，在调用exec或exit之前与父进程数据是共享的，在它调用exec或exit之后父进程才能被调度运行，如果在调用这两个函数之前子进程依赖于父进程的进一步动作，则会导致死锁。

请问如何修改文件最大句柄数

1
2
3
4
5

ulimit -n 2048   # 将最大文件句柄数修改为2048 但是新开一个 shell 会失效
ulimit -a        # 查询 Linux 的相关参数，其中open files为最大文件数
vi /etc/security/limits.conf  ## 要永久修改 最大文件数 在 conf 文件中添加  修改以后保存，注销当前用户，重新登录，修改后的参数就生效了
*　　soft　　nofile　　65536
*　　hard　　nofile　　65536

并发(concurrency)和并行(parallelism)

并发：宏观上两个程序好像在同时运行，但是某一时刻只有一个程序在运行，两个程序交替执行一个小时间片，并发能提高程序的效率。

并行：并行需要硬件支持，例如多核或者多机。两个程序可以在不同核中同时运行，也就是运行了两个指令，互不影响。

MySQL的端口号是多少，如何修改这个端口号

mysql 的默认端口是 3306，修改端口号 在 /etc/my.cnf 文件 中修改即可

1
2
3

## 登录 mysql 使用命令
show global variables like 'port'   ## 查看端口号  
vim my.cnf   ### 修改端口号

说一说操作系统中的页表寻址

页式内存管理，内存分成固定长度的一个个页片。操作系统为每一个进程维护了一个从虚拟地址到物理地址的映射关系的数据结构，叫页表，页表的内容就是该进程的虚拟地址到物理地址的一个映射。页表中的每一项都记录了这个页的基地址。通过页表，由逻辑地址的高位部分先找到逻辑地址对应的页基地址，再由页基地址偏移一定长度就得到最后的物理地址，偏移的长度由逻辑地址的低位部分决定。一般情况下，这个过程都可以由硬件完成，所以效率还是比较高的。页式内存管理的优点就是比较灵活，内存管理以较小的页为单位，方便内存换入换出和扩充地址空间。

早期的Linux系统使用 一级 页表，由于页表是连续的，即使一个进程可能只会使用到少部分的寻址空间，但是也需要将整个页表存储在连续的内存中，这是比较浪费内存的。因此 逐渐出现 多级页表的 结构，通过分散存储的思想，内存中往往只用存储一个一级页表和少量使用到的二级页表，其他不用的二级页表可以存储在外存中，使用时再调入。这样大大减小了存储页表需要的内存空间。寻址方式类似，首先通过CR3寄存器获得一级页表的地址，根据逻辑地址的高位，映射得到对应的二级页表的地址，然后再在二级页表中，根据逻辑地址的中间位映射，得到该逻辑地址对应的完整页的基地址，再加上逻辑地址的低位偏移得到真实的物理地址。

说一说有了进程，为什么还要有线程

进程可以使多个程序能并发执行，以提高资源的利用率和系统的吞吐量；但是其具有一些缺点。

1. 进程中一旦有阻塞任务，整个进程都会被挂起，即使进程中有些工作不依赖于等待资源，但是仍然不会被执行。
2. 进程的建立需要耗费更多资源。线程是一种非常"节俭"的多任务操作方式。在linux系统下，启动一个新的进程必须分配给它独立的地址空间，建立众多的数据表来维护它的代码段、堆栈段和数据段，这是一种"昂贵"的多任务工作方式。
3. 进程间的通信复杂，因为不同进程的数据空间是独立的，要通信需要借助IPC，而线程之间共享资源，比较方便
4. 进程切换开销大，运行于一个进程中的多个线程，它们之间使用相同的地址空间，而且线程间彼此切换所需时间也远远小于进程间切换所需要的时间。

另外：

1. 使多CPU系统更加有效。操作系统会保证当线程数不大于CPU数目时，不同的线程运行于不同的CPU上
2. 改善程序结构。一个既长又复杂的进程可以考虑分为多个线程，成为几个独立或半独立的运行部分，这样的程序才会利于理解和修改。

单核机器上写多线程程序，是否需要考虑加锁，为什么？

需要，如果有一个线程正在对共享数据修改，还没修改完 突然被系统挂起，调入另一个线程，此时该线程再对共享数据读，读出的就是脏数据。

线程需要保存哪些上下文，SP、PC、EAX这些寄存器是干嘛用的

保存 当前线程id和状态，寄存器状态，堆栈信息等。其中寄存器信息主要有 SP指针 存放的是堆栈地址，PC指针程序计数器指向下一条将要执行的指令，EAX累加寄存器，是加法乘法的缺省寄存器，用来存储cpu计算产生的中间结果，如果没有累加器这样的寄存器，那么每次计算加法乘法移位等后产生的中间结果都要写会内存，也许马上又要读回来，速度慢。

线程间同步的方式

（如果问线程通信的方式 就 加上 临界区，通过多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问）

• 用户模式：原子操作，临界区
• 内核模式：事件，信号量，互斥量

信号量。通过PV操作来增减信号值，当信号值为0时，线程休眠。增减的操作是原子的。

1
2
3

sem_wait(sem_t* sem);   // 信号值减1，如果信号值是0 则休眠  
sem_post(sem_t* sem);   // 信号值加1  当值大于0后，其他因为没有信号值而休眠的线程将被唤醒
sem_init();   // 初始化信号量，可以设置初值，也可以选择该信号是用于局部线程还是进程间共享

互斥量/锁。主要用于线程互斥，不能保证按序访问，可以保证线程对临界区的互斥访问，也可以和条件锁一起实现线程同步。当进入临界区的时候需要获得互斥锁并且加锁，当离开临界区的时候，需要对解锁，以唤醒其他等待的线程。

1
2
3
4

pthread_mutex_init();     // 初始化互斥锁
pthread_mutex_lock();     // 以原子的方式给一个互斥锁加锁
pthread_mutex_unlock();   // 以原子的方式给互斥锁解锁
pthread_mutex_destroy();  // 销毁互斥锁

条件变量。和互斥锁不同，条件变量是当达到某个条件时，同时唤醒在等待该变量的线程，从而实现线程同步。但是为了防止出现唤醒信号丢失的情况，通常要和互斥锁配合使用，在测试条件变量的时候先加锁，防止在测试且还未睡眠时，另一个线程发出条件信号，而被当前线程错过的问题。

1
2
3
4

pthread_cond_init();    // 初始化条件变量
pthread_cond_wait();    // 等待目标条件变量，如果没有信号就休眠。在调用该函数测试条件时需要先使用互斥锁加锁确保原子性。在该函数中进入wait状态前会先解锁再休眠。因此该函数入口参数还有个互斥锁变量。在被条件唤醒后，函数内部会再加上互斥锁。
pthread_cond_signal();  // 唤醒一个等待目标条件变量的线程。哪个线程被唤醒取决于调度策略和优先级。
pthread_cond_destroy(); // 销毁条件变量

游戏服务器应该为每个用户开辟一个线程还是一个进程，为什么

游戏服务器应该为每个用户开辟一个进程。因为同一进程间的线程会相互影响，一个线程死掉会影响其他线程，从而导致进程崩溃。因此为了保证不同用户之间不会相互影响，应该为每个用户开辟一个进程

缺页置换算法

进程运行过程中，如果发生缺页中断，而此时内存中有没有空闲的物理块是，为了能够把所缺的页面装入内存，系统必须从内存中选择一页调出到磁盘的对换区。但此时应该把哪个页面换出，则需要根据一定的页面置换算法（Page Replacement Algorithm)来确定

先进先出(FIFO)算法：置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。

最近最少使用（LRU）算法: 置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。

当前最常采用的就是LRU算法。

死锁发生的条件以及如何解决死锁

1. 互斥条件：进程对所分配到的资源不允许其他进程访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源；
2. 请求和保持条件：进程获得一定的资源后，又对其他资源发出请求，但是该资源可能被其他进程占有，此时请求阻塞，但该进程不会释放自己已经占有的资源
3. 不可剥夺条件：进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用后自己释放
4. 环路等待条件：进程发生死锁后，必然存在一个进程-资源之间的环形链

解决死锁的方法即破坏上述四个条件之一，主要方法如下（死锁预防）：

• 静态分配资源，一次性把要用的资源都申请到 破坏请求保持条件
• 可剥夺资源：即当进程新的资源未得到满足时，释放已占有的资源，等到进程可以同时获取两个资源后再启动，从而破坏不可剥夺的条件
• 资源有序分配法：系统给每类资源赋予一个序号，每个进程按编号递增的请求资源，释放则相反，从而破坏环路等待的条件。例如 1，2，3资源，如果进程A 按照 1 2 3 顺序申请，而 B 按照 3 2 1 顺序申请，那必然环路，如果都按照 1 2 3 顺序申请就没事

运行时死锁状态判别

银行家算法

1. 需要预先知道系统当前剩余的资源数量，以及各个进程已经占有的资源数量和请求的资源数量。
2. 遍历每个进程判断 他当前球请求的资源数量是否小于系统剩余资源数量，如果是标记当前进程；然后将系统剩余资源数量加上当前进程占有的资源数量，这代表该进程释放资源后系统总的剩余资源数量。
3. 再按照之前的步骤去遍历标记剩下的进程。最终未被标记的进程都是死锁进程。

如果有一个状态是不安全的 就应该拒绝进入这个状态

通过宏定义 重写加锁去锁算法 主要就是在上锁之前打印请求的资源号和请求的进程 从而得到一个持有的图 然后拓扑排序判断是否有环

请问虚拟内存和物理内存怎么对应

操作系统中的结构体对齐，字节对齐

需要字节对齐的原因：

1. 平台原因：不是所有硬件平台都能随机访问任意地址的数据，可能只能从特定地址开始一次读取指定大小的数据，否则会抛出硬件异常。因此通过指定对齐方 式可以使代码方便兼容多种平台。
2. 性能原因：数据结构应该经可能在自然边界上对齐。原因在于，为了访问非对其的内存，可能需要做两次内存访问，而对齐的内存访问只需要一次。例如如果内存只能从偶地址开始读，那么直接访问奇地址开始的两字节变量需要先访问两次偶地址的地址，然后组合得到实际的数据值。

字节对齐的规则：

1. 结构体字节对齐规则：结构中，第一个变量的起始地址为0，其他变量的起始地址要是 变量本身大小 和 unpack指定的对齐数中 较小的整数倍。如果不是，就补齐。
2. 结构体本身对齐规则：结构本身所占的 大小，要是 成员中最大变量的字节数 和 unpack指定对齐参数中取较小的 数的整数倍。
3. 结构体中如果还有结构体：那么内部的结构体要对齐在它本身 元素中最大变量 的 地址上。

如何自定义对齐方式：

1
2
3
4
5
6
7
8

#program pack(2)   // n=1,2,4,8,16来改变这一系数，其中的n就是指定的“对齐系数”。
struct AA {
int a;       //长度4 > 2 按2对齐；偏移量为0；存放位置区间[0,3]
char b;      //长度1 < 2 按1对齐；偏移量为4；存放位置区间[4]
short c;     //长度2 = 2 按2对齐；偏移量要提升到2的倍数6；存放位置区间[6,7]
char d;      //长度1 < 2 按1对齐；偏移量为7；存放位置区间[8]；最后 结构体要是2的倍数 共10个字节
};
#pragma pack()     //结束对齐

进程间通信的方式

进程通信的方式有 管道，消息队列，套接字，共享内存，信号量

• 管道：管道有 无名管道和有名管道。
  1. 他们都只支持半双工通信，且收发数据双方得同时存在管道的两端；
  2. 管道实际是将信息存储在内存中，消息取出后就不再存在于管道中了；
  3. 管道传输的是数据流，收发双发需要自定义数据格式；
  4. 其中无名管道只能用于有亲缘关系的进程，而有名管道没有这个限制
• 消息队列：消息队列存在于内核中，一个消息队列由一个标识符（即队列ID）来标记，数据读取后仍然存在；且消息具有类型和优先级，因此读取方可以按照数据类型读取消息，而不必按照顺序读出；消息队列独立于发送与接收进程，进程终止时，消息队列及其内容并不会被删除。
• 共享内存：它使得多个进程可以访问同一块物理内存，但是需要用户使用信号量等辅助完成同步操作。这是最快的IPC，因为进程可以直接从物理内存读取。
• 套接字：用于不同主机中的进程通信。

虚拟内存置换的方式

比较常见的置换方法：FIFO 第二次机会算法 LRU LRU-K LFU NRU

1. FIFO： 用一个队列实现，先进先出。完全没有考虑页面使用的冷热信息。
2. 第二次机会算法：弥补了FIFO的缺点，当再次访问队列中已经存在的页时，将它标记为1，当需要置换页面是，从队头开始，如果其标记为1，那么将它置0并放在队尾，依次循环直到找到标记为0的页面换出。实现的时候可以使用一个环形数组实现，每次只需要移动指针即可完成对头到队尾的转变。
   • 当队列中所有的页面都标记为1时，退化成FIFO
3. LRU：使用一个链表维护，当访问某个页面时，将该页面放在队头，当需要换出时，将队尾的页面换出。
   • 由于需要链表，速度慢；
   • 缓存污染：出现偶然数据时，会让内存存放大量冷数据；
   • 缓存颠簸：当出现交替的数据时，命中率很低，每次都要置换。例如 0 1 2 3 0 1 2 3 … 这种数据 缓存大小只有3
     
4. LRU-K：为了解决LRU中缓存污染的问题。维护 一个 FIFO 加 一个 LRU，基本原理是只有当某个页面访问次数超过K次之后才使用LRU的规则置换，否则对于访问频率较少的页面直接使用FIFO的策略淘汰。具体思路是，当新加入一个页面时，先将它放入FIFO中，当访问某个页面时需要记录FIFO中每个页面的被访问次数，如果大于K，就将它从FIFO中删除并放入LRU的链表中，如果LRU缓存满了就按照LRU的规则删除链表尾部的元素。当需要删除页面时，将FIFO中先进入的页面删除。
   • 为了解决 LRU 的缓存污染问题
5. 2Q算法就是 LRU-2
   • 当访问的数据为 ABABABA时退化为 FIFO 用不到LRU

epoll原理

链接

编译系统

以下是一个 hello.c 程序：

1
2
3
4
5
6
7

#include <stdio.h>

int main()
{
    printf("hello, world\n");
    return 0;
}

在 Unix 系统上，由编译器把源文件转换为目标文件。

1

gcc -o hello hello.c

这个过程大致如下：

• 预处理阶段：处理以 # 开头的预处理命令，例如解决头文件的包含关系，宏定义替换，条件编译处理，去掉注释等；
• 编译阶段：检查函数和变量是否存在声明，检查语法是否正确，将C文件翻译成汇编文件；
  • 编译优化 -O1 -O2 -O3（利用了cpu流水线和缓存功能等） Og
• 汇编阶段：将 .s 汇编文件翻译成可重定位 .o 目标文件，二进制机器指令文件；
• 链接阶段：将所有的 .o 文件 还有库文件连接生成可执行文件。编译器将每个函数变量都使用符号表示，然后为每个目标文件提供两个符号表用于和其他文件连接。

链接

链接过程分为两步：重定位，符号解析

重定位：由于多个编译单元 .o 文件的符号地址可能相同，因此重定位就是在连接时会对每个编译单元中的符号地址进行调整，具体的文件内的地址加上该文件最终在可执行文件中的偏移位置即为重定位之后的内存地址。

符号解析 在符号解析阶段，编译器会给每个.o （编译单元）文件生成两个符号表

• 未解决符号表：就是本单元声明但是没有定义的符号
• 导出符号表：就是本单元定义，并且可供给其他文件调用的符号表

连接器会根据目标文件提供的未解决的符号表去所有的编译单元的导出符号表中查找与这个匹配的符号名，如果找到就将这个符号地址填到未解决的符号的地址处。

最后把所有的目标文件的内容写在各自的位置上，就生成一个可执行文件。

静态链接

静态链接在编译阶段就将库文件的所有代码加到可执行文件中，因此生成的程序体积更大，其后缀名一般为 .a

静态链接器以一组可重定位目标文件为输入，生成一个完全链接的可执行目标文件作为输出。链接器主要完成以下两个任务：

动态链接

静态库有以下两个问题：

• 当静态库更新时那么整个程序都要重新进行链接；
• 对于 printf 这种标准函数库，如果每个程序都要有代码，这会极大浪费资源。

共享库是为了解决静态库的这两个问题而设计的，在 Linux 系统中通常用 .so 后缀来表示，Windows 系统上它们被称为 DLL。动态链接在编译链接时并不会把库文件的代码加到可执行文件中，而是在运行时加载所需的动态库，后缀名一般为 .so

• 在给定的文件系统中一个库只有一个文件，所有引用该库的可执行目标文件都共享这个文件，它不会被复制到引用它的可执行文件中；
• 在内存中，一个共享库的 .text 节（已编译程序的机器代码）的一个副本可以被不同的正在运行的进程共享。

进程管理

进程与线程

进程

进程是资源分配的基本单位 进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。

下图显示了 4 个程序创建了 4 个进程，这 4 个进程可以并发地执行。

线程

线程是独立调度的基本单位。一个进程中可以有多个线程，它们共享进程资源。

QQ 和浏览器是两个进程，浏览器进程里面有很多线程，例如 HTTP 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时，浏览器还可以响应用户的其它事件

（内核线程）

协程

协程就是用户线程。是编译层面，由编程语言实现的东西，和操作系统无关。对于包含大量I/O的场景，通常的做法是每个I/O连接使用一个线程维护，大部分的线程都处于阻塞状态。这样由于线程很多，对系统内存资源消耗很多，同时线程的频繁切换也会有较大的开销。这时候就提出了协程的概念

协程是用户线程，所有的线程运行在一个线程上，由用户控制协程的调度，内核感知不到协程的存在，因此它只是对线程进行调度。使用协程需要结合异步I/O使用，因为如果某一个协程调用了IO阻塞的操作导致该线程休眠，那么其他的协程也就得不到调用。

区别

1. 拥有资源 进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。
2. 调度 线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
3. 系统开销 由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
4. 通信方面 线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC

进程状态的切换

• 就绪状态（ready）：等待被调度
• 运行状态（running）
• 阻塞状态（waiting）：等待资源

应该注意以下内容：

• 只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
• 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态

交换技术

当多个进程竞争内存资源时，会造成内存资源紧张，并且，如果此时没有就绪进程，处理机会空闲，I/0速度比处理机速度慢得多，可能出现全部进程阻塞等待I/O

针对以上问题，提出了两种解决方法：

1. 虚拟内存 ： 在内存管理中介绍
2. 交换技术：换出一部分进程到外存，腾出内存空间

进程调度算法

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

1. 先来先服务 first-come first-serverd（FCFS) : 非抢占式的调度算法，按照请求的顺序进行调度。有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。
2. 短作业优先 hortest job first（SJF）：非抢占式的调度算法，按估计运行时间最短的顺序进行调度。长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。
3. 最短剩余时间优先 shortest remaining time next（SRTN）：最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。 当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

时间片轮转

将所有就绪进程按 FCFS（先来先服务） 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。时间片轮转算法的效率和时间片的大小有很大关系：

• 因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
• 而如果时间片过长，那么实时性就不能得到保证

优先级制度

为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

多级反馈队列

这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

实时系统

实时系统要求一个请求在一个确定时间内得到响应。分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

同步

临界区

对临界资源进行访问的那段代码称为临界区。为了互斥访问临界资源，每个 进程/ 线程在进入临界区之前，需要先进行检查。

1
2
3

// entry section
// critical section;
// exit section

同步与互斥

互斥是一种特殊的同步。使用基本的锁可以实现同步，但是操作系统需要封装更高级的同步原语来实现更复杂、更实用的功能。信号量（semaphore）和管程（monitor）就是操作系统提供的两种更高级的同步方式，在操作系统（linux）和编程语言都有对应的实现和封装。

• 同步：多个进程/线程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。
• 互斥：多个进程/线程在同一时刻只有一个进程能进入临界区。

同步的方法

首先区分一个概念，常常说的同步指的是 线程间的同步，也就是可以用信号量，互斥量，管程等，因为这些变量是自己手动定义的，同一个进程中的线程之间的资源是共享的，所以需要使用自定义的变量来完成线程之间的同步或者互斥操作。进程间可能也需要同步，那么进程间的同步是使用IPC机制，即通过进程间的通信实现的，因为进程之间资源不共享，需要经过内核才能完成通信和同步。

信号量

信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。

• down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
• up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。

down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断（所谓原语（原子），一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断）如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// P1 P2 互斥地访问临界1区

typedef int semaphore;
semaphore mutex = 1;
void P1() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

void P2() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

管程

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。管程有一个重要特性：在一个时刻只能有一个线程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个线程持有。signal() 操作用于唤醒被阻塞的进程。

经典同步问题

生产消费者问题

问题描述：两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者，将信息放入缓冲区；另一个是消费者，从缓冲区中取出信息

其实仔细分析，这个题涉及到两个线程同步的问题，即要求 带休眠的功能。如果只使用一个信号量 那么只能表示 空，但是不能体现满的状态，因此需要定义两个信号量。同时 由于 缓冲区属于临界资源，因此访问的时候还需要对缓冲区加锁。

信号量实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#define N 100
typedef int semaphore;
semaphore mutex = 1;  
semaphore empty = N;   // empty大于0时 生产着才能放入 物品  否则休眠
semaphore full = 0;    // full 大于0时 消费者才能取出无 物品 否则休眠

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}
void consumer() {
    while(TRUE) {
        down(&full);
        down(&mutex);
        int item = remove_item();
        consume_item(item);
        up(&mutex);
        up(&empty);
    }
}

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

管程实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#define MAX 100
/* 定义管程 PC   C语言中没有管程这个功能，这里只是用C语言逻辑写一下。管程在编译器编译的时候已经使用互斥锁保证了同一时刻只能由一个线程线程运行，即要么是 insert  要么是remove 这也保证了 拿取的过程其实是串行的*/
monitor PC 
{
    int count = 0; 
    /* 我们使用条件变量full 表示被填满的buffer, empty 表示空的buffer */
    conditon full, empty;

    void insert(int item)
    {
        /* 当buffer满的时候,我们在full上将插入操作阻塞 */
        if ( count == MAX ) wait(&full);   // 等待full信号
        insert_item(item);
        count += 1;
        /* 当buffer不空的时候,我们在empty上唤醒取出操作 */
        if ( count == MAX -1 ) signal(&empty);    
    }

    int remove()
    {
        /* 当buffer空的时候,我们在empty上将取出操作阻塞 */
        if( count == 0 ) wait(&empty);    
        remove_item(item);
        count -= 1;
        /* 当buffer不满的时候,我们在full上唤醒插入操作 */
        return item;
        if( count == MAX - 1) signal(&full);  // 发送full信号  此时上面那个full就可以被唤醒了 
    }
}

    void producer()
    {
        int item;
        item = produce_item();
        /*调用管程中的函数 */
        PC.insert(item);
    }
    
    void consumer()
    {
        int item;
        /*调用管程中的函数 */
        item = PC.remove();
        consumer_item();
    }

科学家进餐问题

有五个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕，放下筷子又继续思考。

按题目的流程，伪代码表示如下（用一个互斥变量来保护一个筷子，拿筷子即为把该变量置0 这样就实现了题目要求的 一只筷子只能一个人拿，然后按流程组织得到下面初步结果）：

这样存在的问题是 如果这些人 都同时拿起坐边的筷子，然后等右手的筷子，那么就会导致锁死。可以从以下几个思路改进

1. 方法一：至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用
2. 方法二：仅当哲学家的左右手筷子都拿起时才允许进餐
3. 方法三：规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反

方法一 使用一个信号量控制 同时拿起左边筷子的人的数量，初始为4，拿起一个，信号量就减1，这样总能保证有一个人可以拿全两双筷子然后等他吃完释放信号。同时每个筷子用一个互斥变量，保证只有一个人能拿

方法二 利用and 型信号量机制实现 也可以用互斥信号对取左右筷子的操作进行保护，这样四个人取左筷子的流程其实就是串行的了。

读者-写者问题

允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。

思路：一个整型变量 count 记录在对数据进行读操作的进程数量，一个互斥量 count_mutex 用于对 count 加锁，一个互斥量 data_mutex 用于对读写的数据加锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;

void reader() {
    while(TRUE) {
        // 来读数据 读者数 conut + 1 修改count要先对count加锁
        down(&count_mutex);
        count++;
        if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
        up(&count_mutex);
         
        read();
        //  读取完毕  将读者数conut - 1  由于又要修改 count 需要将它上锁再修改
        down(&count_mutex);
        count--;
        if(count == 0) up(&data_mutex);
        up(&count_mutex);
    }
}

void writer() {
    while(TRUE) {
        down(&data_mutex);
        write();
        up(&data_mutex);
    }
}

进程通信

每个进程各自有不同的用户地址空间，任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核，在内核中开辟一块缓冲区，进程1把数据从用户空间拷到内核缓冲区，进程2再从内核缓冲区把数据读走，内核提供的这种机制称为进程间通信（IPC，InterProcess Communication）

进程同步与进程通信很容易混淆，它们的区别在于

• 进程同步：控制多个进程按一定顺序执行；
• 进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

管道

管道是通过调用 pipe 函数创建的，fd[0] 用于读，fd[1] 用于写。管道制存在于内存中，在管道创建时，为缓冲区分配一个页面大小

1
2

#include <unistd.h>
int pipe(int fd[2]);

它具有以下限制：

• 只支持半双工通信（单向交替传输），且写的时候必须同时在读
• 只能在父子进程或者兄弟进程中使用
• 数据一旦被读走，便不在管道中存在，不可反复读取
• 管道所传送的是无格式字节流，这就要求管道的读出方和写入方必须事先约定好数据的格式，比如多少字节算作一个消息（或命令、或记录）等等

FIFO

1
2
3

#include <sys/stat.h>
int mkfifo(const char *path, mode_t mode);
int mkfifoat(int fd, const char *path, mode_t mode);

也称为命名管道，去除了管道只能在父子进程中使用的限制。FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据

消息队列

消息队列是存放在内核中的消息链表，每个消息队列由消息队列标识符表示，消息队列存放在内核中，只有在内核重启 (即，操作系统重启) 或者显示地删除一个消息队列时，该消息队列才会被真正的删除。相比于 FIFO，消息队列具有以下优点：

• 消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
• 不需要进程自己提供同步方法，消息队列在某个进程往一个队列写入消息之前，并不需要另外某个进程在该队列上等待消息的到达；
• 读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收
• 消息存在于内核，读了之后不会被删除

共享存储

允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种 IPC。需要使用信号量用来同步对共享存储的访问。多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外 XSI 共享内存不是使用文件，而是使用内存的匿名段。

套接字

与其它通信机制不同的是，它可用于不同机器间的进程通信。

信号量/信号

线程之间的信号量和同一个进程的不同线程之间的信号量不一样 …..

设备管理

磁盘结构

• 盘面（Platter）：一个磁盘有多个盘面；
• 磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；
• 扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小；
• 磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；
• 制动手臂（Actuator arm）：用于在磁道之间移动磁头；
• 主轴（Spindle）：使整个盘面转动。

磁盘调度算法

读写一个磁盘块的时间的影响因素有：

• 旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）
• 寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
• 实际的数据传输时间

其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短

先来先服务

FCFS, First Come First Served 按照磁盘请求的顺序进行调度。优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。

最短寻道时间优先

SSTF, Shortest Seek Time First 优先调度与当前磁头所在磁道距离最近的磁道。虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

电梯算法

电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。

死锁

必要条件

通俗地讲，就是两个或多个进程被无限期地阻塞、相互等待的一种状态

• 互斥（mutualexclusion），一个资源每次只能被一个进程使用
• 不可抢占（nopreemption），进程已获得的资源，在未使用完之前，不能强行剥夺
• 占有并等待（hold andwait），一个进程因请求资源而阻塞时，对已获得的资源保持不放
• 环形等待（circularwait），若干进程之间形成一种首尾相接的循环等待资源关系。

处理方法

主要有以下四种方法：

• 鸵鸟策略
• 死锁检测与死锁恢复
• 死锁预防
• 死锁避免

鸵鸟策略

鸵鸟在遇见问题时，把头埋在沙子里，假装根本没发生问题。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。（就是不管）

大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

死锁检测与死锁恢复

不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复

每种类型一个资源的死锁检测

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。有环时 即发生死锁 因此 每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

每种类型多个资源的死锁检测

这时候后 就不能用上述的环路检测法检测了，一个类型多个资源的情况如下，左图发生了死锁，而右图未死锁。这种情况的死锁检测算法如下：

上图中，有三个进程四个资源，每个数据代表的含义如下：

• E 向量：资源总量
• A 向量：资源剩余量
• C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
• R 矩阵：每个进程请求的资源数量

进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

1. 寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
2. 如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
3. 如果没有这样一个进程，算法终止。

死锁恢复

• 利用抢占恢复 ： 剥夺陷于死锁的进程所占用的资源，但并不撤销此进程，直至死锁解除。
• 利用回滚恢复 ： 根据系统保存的检查点让所有的进程回退，直到足以解除死锁，这种措施要求系统建立保存检查点、回退及重启机制。
• 通过杀死进程恢复：撤销陷入死锁的所有进程，解除死锁，继续运行

死锁预防

在程序运行之前预防发生死锁

1. 破坏互斥条件
2. 破坏占有和等待条件 ： 一种实现方式是规定所有进程在开始执行前请求所需要的全部资源
3. 破坏不可抢占条件
4. 破坏环路等待：给资源统一编号，进程只能按编号顺序来请求资源

死锁避免

在程序运行时避免发生死锁。

定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

锁的实现

Linux中有很多种锁。互斥锁，读写锁，自旋锁，RCU锁等。从底层实现来看 锁就是一个标志位，哪个线程先得到该标志位并对他置位，则代表它先获得了该锁，其他的线程无法对他操作，直到该线程自己将标志位恢复为止。

1. 原子的CAS操作 （Compare and Set）

标志位本身也是一个共享的变量，对他进行读写也需要保护，那么这是个无解的问题嘛？不是的，其实对这个标志位的操作由硬件支持指令级的原子的 CAS 。原子的意思是 某一系列指令在执行过程中不会被任务调度和中断给打断，在单核系统中，简单的关中断即可实现系列指令的原子执行，但是多核系统中还要借助缓存一致性，来确保不同核上的线程对同一个内存区域的变量读取的是一致的。通过上面手段就在硬件层面上实现了变量的 原子性的CAS

CAS 原理就是，首先从内存中读取要修改的变量，将他和期望值比较，如果和期望值不同，那么就说明它被修改了就什么都不做返回false，如果相同，则对变量修改并返回true。

2. 根据锁是否获得，来决定执行什么策略

基于上面原子的CAS操作，就可以保证锁被某个线程唯一的获得不会出现多个线程同时拿到锁的情况。然后至于 互斥锁，自旋锁，读写锁什么的都是根据锁是否获得，来决定执行什么不同的策略

计算机操作系统 - 概述

基本特征

1. 并发

• 并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。
• 并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统。
• 操作系统通过引入进程和线程，使得程序能够并发运行

2.共享

共享是指系统中的资源可以被多个并发进程共同使用。有两种共享方式：互斥共享和同时共享。互斥共享 称为临界资源，例如打印机等，在同一时刻只允许一个进程访问，需要用同步机制来实现互斥访问

3.虚拟

虚拟技术把一个物理实体转换为多个逻辑实体。主要有两种虚拟技术：时（时间）分复用技术和空（空间）分复用技术。

• 时分复用：多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。
• 空分复用：虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中 。 它使得应用程序认为它拥有连续可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上使用这种技术的系统使得大型程序的编写变得更容易，对真正的物理内存（例如RAM）的使用也更有效率

4.异步

异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进

基本功能

进程管理

进程控制、进程同步、进程通信、死锁处理、处理机调度等

内存管理

内存分配、地址映射、内存保护与共享、虚拟内存等。

文件管理

文件存储空间的管理、目录管理、文件读写管理和保护等

设备管理

完成用户的 I/O 请求，方便用户使用各种设备，并提高设备的利用率。主要包括缓冲管理、设备分配、设备处理、虛拟设备等

系统调用

Linux内核中设置了一组用于实现各种系统功能的子程序，称为系统调用。用户可以通过系统调用命令在自己的应用程序中调用它们。从某种角度来看，系统调用和普通的函数调用非常相似。区别仅仅在于，系统调用由操作系统核心提供，运行于核心态（内核态）; 而普通的函数调用由函数库或用户自己提供，运行于用户态。

系统调用

Linux 的系统调用主要有以下这些：

宏内核和微内核

宏内核

简单来说，就是把很多东西都集成进内核，例如linux内核，除了最基本的进程、线程管理、内存管理外，文件系统，驱动，网络协议等等都在内核里面。由于各模块共享信息，因此有很高的性能。缺点是稳定性差，开发过程中的bug经常会导致整个系统挂掉。做驱动开发的应该经常有按电源键强行关机的经历。

微内核

内核中只有最基本的调度、内存管理。驱动、文件系统等都是用户态的守护进程去实现的。优点是超级稳定，驱动等的错误只会导致相应进程死掉，不会导致整个系统都崩溃，在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。因为需要频繁地在用户态和核心态之间进行切换，所以会有一定的性能损失。

中断分类

外中断

由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。

异常

由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等

陷入

在用户程序中使用系统调用

内存管理

虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。

从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。

分页系统地址映射

内存管理单元（MMU）管理着地址空间和物理内存的转换。 内存管理单元里的 页表 存储着 页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。 其中页面号通过 页表 转成真实 页的地址，另外，页表还有一个功能就是 标记 地址是否在内存中。具体实例如下：

例如虚拟地址 0010 000000000100 前 4 位是存储页面号 2 后 12 位存储页面内偏移量 但是 这个页面号不是真实地址的页面号。需要通过页表映射。取页面号2即页表的第二个位置存储的 表项内容为（110 1）：页表项最后一位表示是否存在于内存中，1 表示存在。则这个页对应的页框的地址为 （110 000000000100）。如果不在内存中 就将外存调入内存。

每个进程的虚拟空间地址都一样，那如果两个进程完全使用了相同的虚拟地址，页表项怎么区分呢？一个进程在执行前，操作系统要为它设置好页表寄存器，让它指向进程自己专属的页表，相当于虚拟地址 + 页表地址

页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）

FIFO先进先出

FIFO, First In First Out 选择换出的页面是最先进入的页面。该算法会将那些经常被访问的页面换出，导致缺页率升高。

LRU 最近最久未使用

LRU, Least Recently Used 虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

缺点：

1. 因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。
2. 缓存颠簸，当出现类似的 (3，2，1） 满了，然后又来连续的数据 (0,1,2,3,0,1,2,3….) 每次替换的页面都是下一次即将出现的序号，循环往复每次都要替换
3. 缓存污染，当出现偶然出现的数据时，它被替换到队头，需要整个队列的长度它才会被替换出去，缓存中冷数据会存放太久

LRU-K

最久未使用K次淘汰算法 为了缓解LRU缓存污染的缺点，只有当引用次数超过K次才会被提到对头。可以使用一个队列，一个双向链表实现。对于访问次数不超过 K 次的内存页，可以将它存放在历史访问 队列里，超过K次的元素可以放在缓存队列里。

1. 当历史队列中的元素满，并且还有新增访问元素的时候，将历史缓存队列的元素 按照 FIFO 的顺序置换页面（历史缓存页里的元素被访问的次数都不超过K次）
2. 当历史缓存页里的某个页 访问大于等于K次时，将它从历史队列里删除，并且添加到缓存队列里。
3. 当访问的元素大于K次，那么它应该在缓存队列里，缓存队列使用的双向链表实现，因此将该元素添加到队头
4. 当缓存队列里的元素需要删除的时候，删除链表尾的元素， 即第k次访问距离现在最久的那个页面。

2Q

2Q 就 类似于 LRU-2，采用一个FIFO队列 一个LRU队列，当FIFO容量为2，访问负载为 ABCABCABC时用不到 LRU队列

LFU（最不经常访问淘汰算法）

如果数据过去被访问多次，那么将来被访问的频率也更高。每个数据块一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。每次淘汰队尾数据块。

缓存颠簸

最近未使用

NRU, Not Recently Used 每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：

• R=0，M=0
• R=0，M=1
• R=1，M=0
• R=1，M=1

当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。

第二次机会算法

和FIFO 一样，但是设置了第二次机会。设置一个队列保存 被置置入的 页面序号，先被置入内存的页面在队列最前面。当内存满了 需要置换页面时，fifo方法是 把队列头的 页置换出去，但是可能这个页是频繁访问的页面。第二次机会算法 是 每次访问页面是，将该页面的R位设置为 1 需要置换时，如果队列头的R位是1 就将它放放到队列最后并R位清0，再找下一个，直到队列头的页的R位为0时，将其替换掉。当每个页面都被访问过时就退化为FIFO

这种方法的缺点时 如果缓存中所有的页面都已经被标记 就退化为 FIFO

时钟

第二次机会算法中的队列 即 （链表）需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。 从C移动到D就相当于 把C放到了队列尾！！！！

分段

虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。（代码段 …）

下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。

分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。

段页式

程序的地址空间划分成多个拥有独立地址空间的段 每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能

分页与分段的比较

• 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
• 地址空间的维度：分页是一维地址空间，分段是二维的。
• 大小是否可以改变：页的大小不可变，段的大小可以动态改变。
• 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

多级页表

一般来说，任何进程切换都会暗示着更换活动页表集。Linux内核为每一个进程维护一个task_struct结构体（即进程描述符PCB），task_struct->mm_struct结构体成员用来保存该进程的页表。在进程切换的过程中，内核把新的页表的地址写入CR3控制寄存器。

可以看出 多级页表的结构 是这样的 一级页表中的每一个项 指向下一级页表的地址。如果一级页表由 1K 个项，那么附属的就有 1K 个二级页表。

假设4G 的寻址空间，每个页大小 4K。

• 如果只用一级页表来寻址，那么需要的一级页表的项目数为 4 G / 4 K = 1 M的容量，假设表的每个项就是4字节的数组，那么存储这个1级表需要 1M X 4B = 4M
• 如果使用二级表，并且将一级表的数量设置为 1K， 那么对应的二级表的个数也为 1K 由于寻址4G空间，那么每个二级表的大小 1M / 1K = 1K ，也就是 需要1K 个 每个大小为 1K 的二级表，那么存放所有的二级表需要 1K x 1K x 4B =4M空间，加上一级表的空间 0.004M，总共需要 4.004 M 的空间存储一级和二级表。

多级页表的内存空间占用反而变大了

为什么用多级表

通过上面的计算，发现二级表占用空间反而多了。但是其实在大部分进程中，短时间内并不会真正用上 4G 的寻址空间，但是一级表由于是连续的，要加载就得全部加载进内存，尽管中间很多映射项都没用。如果使用二级表，那么一级表中只有百分之20的二级表需要存储，而没用上的二级表并不需要加载到内存，可以在使用的时候再调入。假设只用了4G寻址空间中的百分之20，二级表 需要存储的空间为 1K x 1K x 0.2 x 4B = 0.8 M 再加上一级表 1K x 4B = 0.004M 一共 使用 0.804M。即实现了分散存储 大大减少了存储页表的开支。

只有一级页表才需要总是在主存中；虚拟存储器系统可以在需要时创建，页面掉入或调出二级页表，这就减少了主存的压力；只有最经常使用的二级页表才需要缓存在主存中，这种离散的存储方式是非常便利的

page cache

参考连接

基数树 主要用于构建大范围 但是有较多公共前缀的 稀疏映射关系 例如稀疏的地址集合

malloc 和 free的实现原理解析

https://jacktang816.github.io/post/mallocandfree/

进程地址空间

如上图所示在一个32位系统中，可寻址的空间大小是4G，linux系统下0-3G是用户模式，3-4G是内核模式。而在用户模式下又分为代码段、数据段、.bss段、堆、栈。

• 代码段： 主要存放进程的可执行二进制代码，字符串字面值和只读变量（不能修改的）
• 数据段：数据段存放已经初始化且初始值非0的全局变量和局部静态变量
• bss段：存放未初始化或初始值为0的全局变量和局部静态变量
• 堆：存放由用户动态分配内存存储的变量；
• 栈：主要存储局部变量、函数参数、返回地址等

bss段、数据段和代码段是可执行程序编译时的分段，运行时还需要栈和堆。将应用程序加载到内存空间执行时，操作系统负责代码段、数据段和bss段的加载，并在内存中为这些段分配空间。栈也由操作系统分配和管理，堆则是由程序员自己管理。

为什么要区分 .bss段 和 数据段？ .data段存放的是已经初始化的且非0的全局或局部变量，因此这个初始化的值会保存在可执行文件中，而.bss段中是未初始化的，因此编译的时候只是记录了该段需要的空间大小，在执行额时候才会给.bss段中的数据分配内存。这样可以减少生成的可执行文件的大小。而对于字面值常量，显示是和代码一样的不可修改的常量值，所以放在代码段。

内存映射段(mmap) 内核将硬盘文件的内容直接映射到内存，任何应用程序都可通过 Linux 的 mmap() 系统调用请求这种映射。

• 内存映射是一种方便高效的文件 I/O 方式， 因而被用于装载动态共享库。

• 用户也可创建匿名内存映射，该映射没有对应的文件，可用于存放程序数据。

• mmap 映射区向下扩展，堆向上扩展，两者相对扩展，直到耗尽虚拟地址空间中的剩余区域.

进程

在Linux中进程由进程控制块(PCB)描述，用一个task_struct 数据结构表示，这个数据结构记录了所有进程信息，包括进程状态、进程调度信息、标示符、进程通信相关信息、进程连接信息、时间和定时器、文件系统信息、虚拟内存信息等.。

和 malloc密切相关的就是虚拟内存信息，定义为 struct mm_struct *mm 具体描述进程的地址空间。mm_struct结构是对整个用户空间（进程空间）的描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

///include/linux/sched.h 
struct mm_struct {
  struct vm_area_struct * mmap;  /* 指向虚拟区间（VMA）链表 */
  rb_root_t mm_rb;               /*指向red_black树*/
  struct vm_area_struct * mmap_cache;     /* 指向最近找到的虚拟区间*/
  pgd_t * pgd;                  /*指向进程的页目录*/
  atomic_t mm_users;                   /* 用户空间中的有多少用户*/                                     
  atomic_t mm_count;                   /* 对"struct mm_struct"有多少引用*/                                     
  int map_count;                       /* 虚拟区间的个数*/
  struct rw_semaphore mmap_sem;
  spinlock_t page_table_lock;         /* 保护任务页表和 mm->rss */       
  struct list_head mmlist;            /*所有活动（active）mm的链表 */
  unsigned long start_code, end_code, start_data, end_data; /* 代码段、数据段 起始地址和结束地址 */
  unsigned long start_brk, brk, start_stack; /* 栈区 的起始地址，堆区 起始地址和结束地址 */
  unsigned long arg_start, arg_end, env_start, env_end; /*命令行参数 和 环境变量的 起始地址和结束地址*/
  unsigned long rss, total_vm, locked_vm;
  unsigned long def_flags;
  unsigned long cpu_vm_mask;
  unsigned long swap_address;

  unsigned dumpable:1;
  /* Architecture-specific MM context */
  mm_context_t context;
};

• start_brk 和 brk 分别是堆的起始和终止地址。堆的大小由start_brk 和brk决定。
  • 可以使用系统调用 sbrk() 或 brk() 增加 brk的值，达到增大堆空间的效果，但是系统调用代价太大，涉及到用户态和内核态的相互转换。所以，实际中系统分配较大的堆空间，进程通过malloc() 库函数在堆上进行空间动态分配，堆如果不够用 malloc 可以进行系统调用，增大brk的值。
• start_stack是进程栈的起始地址，栈的大小是在编译时期确定的，在运行时不能改变。

malloc 只知道 start_brk 和brk之间连续可用的内存空间它可用任意分配，如果不够用了就向系统申请增大brk。后面一部分主要就malloc如何分配内存进行说明。

个人理解：每个进程都有一个4G的虚拟进程空间，但是其中很大一部分起始都没有映射到物理内存，比如堆区，不可能每个进程都同时把这么大的堆空间都分配物理内存。而是在动态申请后，真正使用了 才会分配。每个进程malloc管理的也是自己区域虚拟空间中的堆区，不同进程之间的malloc不存在交叉。

相关的系统调用

brk() 和 sbrk()

由之前的进程地址空间结构分析可以知道，要增加一个进程实际的可用堆大小，就需要将 brk 指针向高地址移动。Linux通过brk和sbrk系统调用操作break指针。两个系统调用的原型如下：

1
2
3

#include <unistd.h>
int brk(void *addr);             //将brk指针直接设置为某个地址
void *sbrk(intptr_t increment);  //将brk指针从当前位置移动increment所指定的增量 ，失败返回-1

进程所面对的虚拟内存地址空间，只有按页映射到物理内存地址，才能真正使用。受物理存储容量限制，整个堆虚拟内存空间不可能全部映射到实际的物理内存。因此每个进程有一个rlimit表示当前进程可用的资源上限。这个限制可以通过getrlimit系统调用得到。

mmap

1
2
3

#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off\_t offset);  // 向映射区申请一块内存
int munmap(void *addr, size_t length);   // 用于释放内存

mmap函数第一种用法是映射磁盘文件到内存中；而malloc使用的mmap函数的第二种用法，即匿名映射，匿名映射不映射磁盘文件，而是向映射区申请一块内存。

• 分配内存 < DEFAULT_MMAP_THRESHOLD （默认128K），走__brk，从内存池获取，失败的话走brk系统调用
• 分配内存 > DEFAULT_MMAP_THRESHOLD，走__mmap，直接调用mmap系统调用

上述的只是分配了虚拟内存，还没有映射到物理内存，当访问申请的内存时，才会因为缺页异常，内核分配物理内存。

malloc实现方案

直接使用系统调用分配内存存在的问题：

1. 由于brk/sbrk/mmap属于系统调用，如果每次申请内存，都调用这三个函数中的一个，那么每次都要产生系统调用开销（即cpu从用户态切换到内核态的上下文切换，这里要保存用户态数据，等会还要切换回用户态），这是非常影响性能的；
2. 其次，这样申请的内存容易产生碎片，因为堆是从低地址到高地址，如果低地址的内存没有被释放，高地址的内存就不能被回收。

因此， malloc采用的是内存池的实现方式，malloc内存池实现方式更类似于STL分配器和memcached的内存池，先申请一大块内存，然后将内存分成不同大小的内存块，然后用户申请内存时，直接从内存池中选择一块相近的内存块即可。

上图左边 是隐式 空闲闲链表，和上图的堆的结构对应；右边是显式空闲链表的结构，和bins(即内存池对应)。内存池保存在bins这个长128的数组中，每个元素都是一双向个链表，每个双向链表将大小接近的空闲块连接起来。

• bins[0]目前没有使用
• bins[1]的链表称为unsorted_list，用于维护free释放的chunk。
• bins[2,63)的区间称为small_bins，用于维护＜512字节的内存块，其中每个元素对应的链表中的chunk大小相同，均为index*8。
• bins[64,127)称为large_bins，用于维护>512字节的内存块，每个元素对应的链表中的chunk大小不同，index越大，链表中chunk的内存大小相差越大，例如: 下标为64的chunk大小介于[512, 512+64)，下标为95的chunk大小介于[2k+1,2k+512)。同一条链表上的chunk，按照从小到大的顺序排列。

malloc除了有unsorted bin，small bin，large bin三个bin之外，还有一个fast bin。一般的情况是，程序在运行时会经常需要申请和释放一些较小的内存空间。当分配器合并了相邻的几个小的 chunk 之后，也许马上就会有另一个小块内存的请求，这样分配器又需要从大的空闲内存中切分出一块，这样无疑是比较低效的，故而，malloc 中在分配过程中引入了 fast bins，不大于 max_fast(默认值为 64B)的 chunk 被释放后，首先会被放到 fast bins中，fast bins 中的 chunk 并不改变它的使用标志 P。这样也就无法将它们合并，当需要给用户分配的 chunk 小于或等于 max_fast 时，malloc 首先会在 fast bins 中查找相应的空闲块，然后才会去查找 bins 中的空闲 chunk。在某个特定的时候，malloc 会遍历 fast bins 中的 chunk，将相邻的空闲 chunk 进行合并，并将合并后的 chunk 加入 unsorted bin 中，然后再将 unsorted bin 里的 chunk 加入 bins 中。

unsorted bin 的队列使用 bins 数组的第一个，如果被用户释放的 chunk 大于 max_fast，或者 fast bins 中的空闲 chunk 合并后，这些 chunk 首先会被放到 unsorted bin 队列中，在进行 malloc 操作的时候，如果在 fast bins 中没有找到合适的 chunk，则malloc 会先在 unsorted bin 中查找合适的空闲 chunk，然后才查找 bins。如果 unsorted bin 不能满足分配要求。 malloc便会将 unsorted bin 中的 chunk 加入 bins 中。然后再从 bins 中继续进行查找和分配过程。从这个过程可以看出来，unsorted bin 可以看做是 bins 的一个缓冲区，增加它只是为了加快分配的速度。

综上：

malloc 内存分配流程

1. 如果分配内存<512字节，则通过内存大小定位到smallbins对应的index上(floor(size/8))
   • 如果smallbins[index]为空，进入步骤3
   • 如果smallbins[index]非空，直接返回第一个chunk
2. 如果分配内存>512字节，则定位到largebins对应的index上
   • 如果largebins[index]为空，进入步骤3
   • 如果largebins[index]非空，扫描链表，找到第一个大小最合适的chunk，如size=12.5K，则使用chunk B，剩下的0.5k放入unsorted_list中
3. 遍历unsorted_list，查找合适size的chunk，如果找到则返回；否则，将这些chunk都归类放到smallbins和largebins里面
4. index++从更大的链表中查找，直到找到合适大小的chunk为止，找到后将chunk拆分，并将剩余的加入到unsorted_list中
5. 如果还没有找到，那么使用top chunk
6. 或者，内存<128k，使用brk；内存>128k，使用mmap获取新内存

Linux

在面试中，Linux 知识点相对于网络和操作系统等知识点而言不是那么重要，只需要重点掌握一些原理和命令即可

• 能简单使用 cat，grep，cut 等命令进行一些操作；
• 文件系统相关的原理，inode 和 block 等概念，数据恢复；
• 硬链接与软链接；
• 进程管理相关，僵尸进程与孤儿进程，SIGCHLD

文件系统

组成

最主要的几个组成部分如下：

• inode：一个文件占用一个 inode，记录文件的属性，同时记录此文件的内容所在的 block 编号；
• block：记录文件的内容，文件太大时，会占用多个 block。

除此之外

• superblock：记录文件系统的整体信息，包括 inode 和 block 的总量、使用量、剩余量，以及文件系统的格式与相关信息等；
• block bitmap：记录 block 是否被使用的位图。

文件读取

对于 Ext2 文件系统，当要读取一个文件的内容时，先在 inode 中查找文件内容所在的所有 block，然后把所有 block 的内容读出来。

而对于 FAT 文件系统，它没有 inode，每个 block 中存储着下一个 block 的编号

磁盘碎片

指一个文件内容所在的 block 过于分散，导致磁盘磁头移动距离过大，从而降低磁盘读写性能

block

在 Ext2 文件系统中所支持的 block 大小有 1K，2K 及 4K 三种，不同的大小限制了单个文件和文件系统的最大大小。一个 block 只能被一个文件所使用，未使用的部分直接浪费了。因此如果需要存储大量的小文件，那么最好选用比较小的 block。

inode

inode 具体包含以下信息：

• 权限 (read/write/excute)；
• 拥有者与群组 (owner/group)；
• 容量；
• 建立或状态改变的时间 (ctime)；
• 最近读取时间 (atime)；
• 最近修改时间 (mtime)；
• 定义文件特性的旗标 (flag)，如 SetUID...；
• 该文件真正内容的指向 (pointer)。

inode 具有以下特点：

• 每个 inode 大小均固定为 128 bytes (新的 ext4 与 xfs 可设定到 256 bytes)；
• 每个文件都仅会占用一个 inode。

inode 中记录了文件内容所在的 block 编号，但是每个 block 非常小，一个大文件随便都需要几十万的 block。而一个 inode 大小有限，无法直接引用这么多 block 编号。因此引入了间接、双间接、三间接引用。间接引用让 inode 记录的引用 block 块记录引用信息。

目录

建立一个目录时，会分配一个 inode 与至少一个 block。block 记录的内容是目录下所有文件的 inode 编号以及文件名。可以看到文件的 inode 本身不记录文件名，文件名记录在目录中，因此新增文件、删除文件、更改文件名这些操作与目录的写权限有关。

挂载

挂载利用目录作为文件系统的进入点，也就是说，进入目录之后就可以读取文件系统的数据。

文件

文件属性

用户分为三种：文件拥有者、群组以及其它人，对不同的用户有不同的文件权限。使用 ls 查看一个文件时，会显示一个文件的信息，例如 drwxr-xr-x 3 root root 17 May 6 00:14 .config，对这个信息的解释如下：

• drwxr-xr-x：文件类型以及权限，第 1 位为文件类型字段，后 9 位为文件权限字段
• 3：链接数
• root：文件拥有者
• root：所属群组
• 17：文件大小
• May 6 00:14：文件最后被修改的时间
• .config：文件名

常见的文件类型及其含义有：

• d：目录
• -：文件
• l：链接文件

9 位的文件权限字段中，每 3 个为一组，共 3 组，每一组分别代表对文件拥有者、所属群组以及其它人的文件权限。一组权限中的 3 位分别为 r、w、x 权限，表示可读、可写、可执行。

链接

• 实体链接 ： 即硬链接，在目录下创建一个条目，记录着文件名和inode编号，这个inode编号就是源文件的inode，删除源文件 这个硬链接还是存在，只是把当前文件从它在的目录下的记录抹去了，但是还有别的地方链接了它，那么这个文件的inode就不会真正删除
• 软链接：类似于windows下的快捷方式，只是记录了文件的绝对路径，如果源文件删除了 软链接就失效了。

常用命令

chmod 修改权限

可以将一组权限用数字来表示，此时一组权限的 3 个位当做二进制数字的位，从左到右每个位的权值为 4、2、1，即每个权限对应的数字权值为 r : 4、w : 2、x : 1。

1

## chmod [-R] xyz dirname/filename

示例：将 .bashrc 文件的权限修改为 -rwxr-xr--

1
2
3
4
5
6
7
8

## chmod [ugoa]  [+-=] [rwx] dirname/filename
- u：拥有者
- g：所属群组
- o：其他人
- a：所有人
- +：添加权限
- -：移除权限
- =：设定权限

示例：为 .bashrc 文件的所有用户添加写权限。

1

chmod a+w .bashrc

ln 创建链接

1
2
3

## ln [-sf] source_filename dist_filename
-s ：默认是实体链接，加 -s 为符号链接
-f ：如果目标文件存在时，先删除目标文件

ls 查看目录信息

1
2
3
4

## ls [-aAdfFhilnrRSt] file|dir
-a ：列出全部的文件
-d ：仅列出目录本身
-l ：以长数据串行列出，包含文件的属性与权限等等数据

touch 建立新文件

1
2
3
4
5
6
7

更新文件时间或者建立新文件。
## touch [-acdmt] filename
-a ： 更新 atime
-c ： 更新 ctime，若该文件不存在则不建立新文件
-m ： 更新 mtime
-d ： 后面可以接更新日期而不使用当前日期，也可以使用 --date="日期或时间"
-t ： 后面可以接更新时间而不使用当前时间，格式为[YYYYMMDDhhmm]

cp 复制

复制文件。如果源文件有两个以上，则目的文件一定要是目录才行

1
2
3
4
5
6
7
8

cp [-adfilprsu] source destination
-a ：相当于 -dr --preserve=all
-d ：若来源文件为链接文件，则复制链接文件属性而非文件本身
-i ：若目标文件已经存在时，在覆盖前会先询问
-p ：连同文件的属性一起复制过去
-r ：递归复制
-u ：destination 比 source 旧才更新 destination，或 destination 不存在的情况下才复制
--preserve=all ：除了 -p 的权限相关参数外，还加入 SELinux 的属性, links, xattr 等也复制了

mv 移动

1
2
3

## mv [-fiu] source destination
## mv [options] source1 source2 source3 .... directory
-f ： force 强制的意思，如果目标文件已经存在，不会询问而直接覆盖

cat 取得文件内容

1
2
3
4
5

## cat [-AbEnTv] filename
-n ：打印出行号，连同空白行也会有行号，-b 不会

## cat test > test1   ### test 内容会覆盖test1的所有内容
## cat test >> test1  ### test内容添加在 test1 内容的后面

locate 文件搜索

文件搜索。可以用关键字或者正则表达式进行搜索。locate 使用 /var/lib/mlocate/ 这个数据库来进行搜索，它存储在内存中，并且每天更新一次，所以无法用 locate 搜索新建的文件。可以使用 updatedb 来立即更新数据库。较快

1
2
3

## locate [-ir] keyword
-r：正则表达式
##  locate -r /ls$     ### 查找以/ls结尾的文件  

find 文件搜索

文件搜索。可以使用文件的属性和权限进行搜索

1
2
3
4
5
6
7
8

## find [basedir] [option]
example: find . -name "shadow*"

与时间有关的选项

与文件拥有者和所属群组有关的选项

与文件权限和名称有关的权限

tar 打包指令

压缩指令只能对一个文件进行压缩，而打包能够将多个文件打包成一个大文件。tar 不仅可以用于打包，也可以使用 gzip、bzip2、xz 将打包文件进行压缩。