操作系统面试题

• 1. 进程和线程
  • 1.1. 进程的创建
    • 1.1.1. fork()原理
    • 1.1.2. fork()一次调用，两次返回
  • 1.2. 进程的结束
  • 1.3. 进程状态转化
    • 1.3.1. 僵尸进程和孤儿进程
    • 1.3.2. 进程状态转化
  • 1.4. PCB
    • 1.4.1. PCB的结构
  • 1.5. 进程间通信
    • 1.5.1. 总览
    • 1.5.2. 管道
    • 1.5.3. 消息队列
    • 1.5.4. 共享内存
    • 1.5.5. 信号量
    • 1.5.6. 信号
    • 1.5.7. socket
  • 1.6. 进程上下文切换
    • 1.6.1. 上下文切换的时机
    • 1.6.2. 过程
    • 1.6.3. 中断
    • 1.6.4. 中断流程
  • 1.7. 进程调度
  • 1.8. 进程、线程、协程的区别
    • 1.8.1. 进程和线程的区别
    • 1.8.2. 线程和协程区别
• 2. 内存管理
  • 2.1. 虚拟内存
    • 2.1.1. 虚拟内存是如何组织的
  • 2.2. 访问虚拟内存到访问物理内存的过程
  • 2.3. buddy伙伴算法和大页机制
  • 2.4. 申请内存时，如果内存不够了怎么办？
    • 2.4.1. 避免预读失效和缓存污染
  • 2.5. MMU？TLB？多级页表？
    • 2.5.1. MMU
    • 2.5.2. TLB
    • 2.5.3. 多级页表
  • 2.6. malloc两种申请内存方式
• 3. 文件系统
  • 3.1. VFS
    • 3.1.1. 文件描述符
    • 3.1.2. VFS四个对象
  • 3.2. inode与块存储
    • 3.2.1. inode存储了什么
    • 3.2.2. inode实现的文件系统
    • 3.2.3. 快速查找空闲内存
    • 3.2.4. 目录的存储格式
  • 3.3. 硬链接和软链接的区别
  • 3.4. 用户写了4KB写到磁盘上经历的过程
    • 3.4.1. cp和mv的时候inode如何变化？
  • 3.5. 零拷贝技术有哪些
    • 3.5.1. mmap本质
    • 3.5.2. 其他零拷贝技术
  • 3.6. page cache
    • 3.6.1. buffer io刷盘时间
  • 3.7. IO调度器，磁盘调度算法

1. 进程和线程

1.1. 进程的创建

一开始os创建出#0(idle)进程（非fork创建），之后通过fork()创建#1(init进程)，#2

1.1.1. fork()原理

调用fork()最终会调用到do_fork()里面的copy_process()函数

前置知识：

1. 进程在内存中可以分用户态空间和内核态空间两部分，内核态主要是PCB(struct task)和内核堆栈(kstack)。用户态空间即我们常说的代码段，数据段和用户栈，堆等内存。内核栈的用处可以理解为用户态与内核态的上下文切换，当进程从用户态转向内核态时，会把用户态时的寄存器信息保存到内核态，然后将指令寄存器指向内核栈地址。当进程从内核态转化为用户态的时候，再将内核态保存的寄存器信息还原，并将指令寄存器重置为内核栈保存的用户态指令地址。实际存储这部分信息的是内核栈栈底的pt_regs.

​ linux 进程内核栈 - 知乎 (zhihu.com)

2. 进程之间的上下文切换：进程的上下文切换是发生在内核态，在PCB(struct task)中存在thread成员变量，里面包含thread.thread_struct变量，这是为了适配不同的体系结构存在的，里面包含兼容了不同架构的CPU信息。在thread_struct中的cpu_context中保存了所有cpu寄存器上存储的值，进程在内核态进行切换的时候会将cpu_context的值进行切换。

​

a. 创建PCB并复制父进程的PCB控制块(struct stack)

新进程通过copy父进程的PCB来保证与父进程有相同的进程状态，在dump_task_struct()中调用alloc_task_struct_node()来为新进程申请管理PCB的页面，并使用函数arch_dup_task_struct()将父进程的PCB赋值给新进程。

//申请PCB，实际上就是allocate了一个page
#define alloc_task_struct_node(node)                        \
({                                      \
    struct page *page = alloc_pages_node(node, GFP_KERNEL | __GFP_COMP, \ //申请Page页
                         KERNEL_STACK_SIZE_ORDER);      \
    struct task_struct *ret = page ? page_address(page) : NULL;     \ //转化为空的task_strut
                                        \
    ret;                                    \
})
//复制PCB
int arch_dup_task_struct(struct task_struct *dst, struct task_struct *src)
{
    ...
    *dst = *src; //直接copy
    dst->thread.sve_state = NULL; //分离sve_state，避免dst过早的释放
    clear_tsk_thread_flag(dst, TIF_SVE); //把TIF_SVE flag清除
    clear_tsk_thread_flag(dst, TIF_MTE_ASYNC_FAULT);   //把所有异步的flag全都删除
    return 0;
}

b. 复制父进程的CPU上下文到新的进程中，使得新进程与父进程有相同的执行环境，这里一方面要有进行进程间调度的CPU信息（对应thread_struct中的cpu_context），也要有内核态恢复到用户态需要的上下文信息（内核栈栈底的pt_regs）

审视源码：

int copy_thread(struct task_struct *p, const struct kernel_clone_args *args)
{
    unsigned long clone_flags = args->flags;
    unsigned long stack_start = args->stack;
    unsigned long tls = args->tls;
    struct thread_info *thread = task_thread_info(p);
    struct pt_regs *childregs = task_pt_regs(p); //获取pt_regs结构，内含各种寄存器信息
    memset(&thread->cpu_context, 0, sizeof(struct cpu_context_save)); //将新进程内核态需要的寄存器清零
    
    *childregs = *current_pt_regs(); //将当前pt_regs copy给子进程
    childregs->ARM_r0 = 0;
    if (stack_start) //如果用户设置了栈的起始地址，设置用户栈的地址是stack_start
        childregs->ARM_sp = stack_start;
    thread->cpu_context.pc = (unsigned long)ret_from_fork; //设置pc
    thread->cpu_context.sp = (unsigned long)childregs; //设置栈指针
    return 0; //0表示X0寄存器
}

创建一个新的thread_info，将其task_struct的cpu_context寄存器信息清空，然后将父进程pt_regs给子进程，然后ret_from_fork即设置PC指针为fork()处，即从fork处开始执行。使用cpu_context直接修改当前进程的cpu的值。栈指针指向子进程内核态的栈顶。

c. 为新进程分配新的内存，使用copy on write技术

写时复制技术即 fork的时候只复制页表，不复制具体的数据，等真正write的时候再复制（需要分配设置mm_struct，其中会分配进程页全局目录所在的页，然后将首地址赋值给pgd。）

可以结合内存管理章节来看

1.1.2. fork()一次调用，两次返回

父进程调用fork，copy一份父进程的内存空间，并将子进程加入到CPU调度队列，修改父进程的返回值为child进程的pid，子进程的返回值是0。两个进程执行中断返回用户态继续从fork()处往下执行。（返回值负数代表fork出错）

1.2. 进程的结束

exit()和return()的区别：

return() 代表调用栈的返回，exit()代表一个过程的结束。从main函数退出，会隐式的调用exit()函数，并将return的返回值传递给exit()从exit()退出，会先调用退出程序，刷新stdio流缓冲区，使用由status提供的值执行_exit()系统调用

调用该系统调用后会导致当前进程直接退出，且函数不会返回。内核会关闭该进程打开的文件描述符，若还存在子进程，则交由1号进程init领养，再向进程的父进程发送 SIGCHLD 信号，让父进程回收该进程的资源。

父进程可以通过wait函数内部accept捕捉SIGHLD信号获得子进程的状态，并回收子进程的资源。返回pid或者-1（失败）。

kill -9 pid 是给进程发送SIGKILL信号，不会变成僵尸进程，内存资源已经被全部释放

1.3. 进程状态转化

1.3.1. 僵尸进程和孤儿进程

僵尸进程

int main()
{
	pid_t pid=fork();
 
	if(pid==0)  //子进程
	{
     	printf("child id is %d\n",getpid());
		printf("parent id is %d\n",getppid());
	}
	else  //父进程不退出，使子进程成为僵尸进程
	{
        while(1)
		{}
	}
	exit(0);
}

一般而言，我们在调用fork()之后，父进程会手动执行wait()和waitPid()函数，等待子进程结束并将子进程的PCB回收。如果子进程结束时父进程没有进行回收(wait信号)，或者如果父进程一直处于死循环（比如上面那段代码），则该子进程会成为僵尸进程，浪费系统资源。进程调用exit()并不会完全被销毁，还留下一个僵尸进程的数据结构，需要等待回收。

【linux】孤儿进程与僵尸进程产生及其处理 - 知乎 (zhihu.com)

处理：

我们无法直接处理僵尸进程，我们需要找到僵尸进程的父进程，ps -ef | grep defunct_process_pid，然后杀死父进程。或者使用wait信号处理。

孤儿进程

父进程先结束(sleep实现)，子进程变成孤儿进程。孤儿进程由#1的init进程处理，init进程完成状态收集工作。

1.3.2. 进程状态转化

进程状态

a. 就绪状态：表示进程已经获得到了CPU资源，等待被调度

b. 运行状态：进程中的指令正在被CPU执行

退出方法：(1) CPU被其他进程抢占，进入就绪状态 (2) 进程需要等待资源时进入阻塞状态

c. 阻塞状态：当外部事件发生的时候进入阻塞状态，例如有I/O请求

d. 终止状态：进程结束。包括僵尸状态和死亡状态

e. 其他状态：跟踪状态、停止状态（待研究）

挂起状态

1.4. PCB

1.4.1. PCB的结构

a. 描述信息：pid，ppid

b. 进程状态

c. CPU上下文 比如thread_struct （包含cpu_context）

d. 内存信息 mm_struct

e. files_struct：进程正打开的所有文件的列表

f. 信号处理相关的，比如阻塞blocking，pending信号队列，sig信号处理函数

PCB的组织方式

通过双向链表的方式将相同状态的进程链接在一起，组成各种队列

• 将所有处于就绪状态的进程链在一起，称为就绪队列；
• 把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列；

1.5. 进程间通信

1.5.1. 总览

为了实现进程间通信，我们首先提出了用管道的方法来实现单向通信，为了解决管道的阻塞问题，我们提出了消息队列。然而消息队列中存在内存拷贝，为了加快数据传输，我们使用共享内存的方法来进行进程间通信，共享内存是最快的进程间通信方式，被广泛应用，例如化交易系统以及JVM AppCDS。然而我们需要信号量机制来避免共享内存中的并发问题。操作系统提供了信号来处理异常，我们最熟悉的kill -9其底层就是调用了sigkill信号。当需要在不同的网络主机进程进行通信时，就需要用到socket的方式

1.5.2. 管道

匿名管道本质是系统调用：int pipe(int fd[2])

管道可以看作写入端一个内存中的fd和写出端一个内存中的fd文件，本质是写入到内核中的一块内存，再读出。且是阻塞的。

管道实现进程间通信的：可以利用fork父子进程，且两个进程的fd是一样的。则关闭其中一个的读端和另一个的写端即可实现两个进程的通信。

然而shell中的可不是这样的，shell中的 A | B指令实际是创建了两个进程，也就是shell、A、B三个进程，关闭shell的独写端，A、B的一个读端，一个写端。

5.2 进程间有哪些通信方式？ | 小林coding (xiaolincoding.com)

缺点：a. 单向传输 b. 效率低下 c. 阻塞

优点：简单易用

1.5.3. 消息队列

消息队列是保存在内核中的一个消息链表，消息发送方和接收方，需要约定数据结构类型和数据大小。

优点: 1. 实现非阻塞

缺点: 1. 不能传输较大的数据，内核有MSGMAX和MSGMNB限制单挑消息最大长度和总长度

     2. 用户态到内核态的数据拷贝开销

1.5.4. 共享内存

进程是虚拟内存映射到实际物理内存的。共享内存就是进程A和进程B的一部分地址映射到同一块物理内存中。

实现方法：posix API：1. shmget()获取共享内存段id 2. 调用 shmat() 将 id 标识的共享内存段加到进程的虚拟地址空间 接下来就可以直接对共享内存进行操作了

mmap也可以实现共享内存 UNIX(进程间通信)：12 揭秘mmap创建共享内存-腾讯云开发者社区-腾讯云 (tencent.com)

优点：快，不需要内核到用户态的拷贝（零拷贝） 缺点：需要手动实现同步

1.5.5. 信号量

信号量来处理共享内存中的并发问题

给定值S，P +1, V -1，当S<-1时阻塞。

当S = 1时为互斥信号量，

1. 对于某一资源T，A访问时-1， S=0，B访问时-1，S=-1，B阻塞，A执行完后+1，S=0，唤醒B

当S = 0时同步信号量

2. 对于某一资源T，B的访问需要等到A之后，若B先访问，则-1，S=-1，B阻塞，A访问时+1，S=0，B唤醒。若A先访问S=1，不会阻塞

1.5.6. 信号

实现原理：PCB的task struct中包含了以下几个结构：

struct task_struct {
    ...
    int sigpending;
    ...
    struct signal_struct *sig;
    sigset_t blocked;
    struct sigpending pending;
    ...
}

sigpending 表示进程是否有信号需要处理（1表示有，0表示没有）。

成员 blocked 表示被屏蔽的信息，每个位代表一个被屏蔽的信号。

成员 sig 表示信号相应的处理方法，所有信号类型linux都提供了默认的信号处理函数，可以通过signal()系统调用自定义信号处理函数，本质是将成员sig中对应的signal_struct中的的信号处理方法给替换掉

pending 成员，其类型为 struct sigpending，存储着进程接收到的信号队列（单向链表）

kill 用于发送信号，是异步的（唯一一个异步的），发送的信号会在从内核态回到用户态之前执行的，实际上还是在用户态中执行的

常见信号：

kill -9 SIGKILL

SIGINT: ctrl + c: 停止运行

SIGTSTP: ctrl + z: 停止在本shell运行

信号与中断的区别：

相同：当操作系统收到信号或者中断时，都需要停止当前的进程，转而去处理信号或中断。此时，操作系统需要保存当前进程的上下文，然后执行相应的信号处理程序或中断处理程序。

不同点：中断是内核态的中断服务程序，信号处理程序是在用户态，且有延迟，并且可以自定义处理函数

1.5.7. socket

见网络IO

1.6. 进程上下文切换

1.6.1. 上下文切换的时机

1. 时间片用完
2. 主动让出CPU，例如使用yield系统调用
3. 有硬中断到来

可以分为一个周期scheduler_tick的定时周期性被激活（时间片用完）和进程主动调用主调度器scheduler进行程序调度（主动让出CPU或者有硬中断到来）。

linux中就分这两个调度器

1.6.2. 过程

a. 信号通知：时钟中断处理程序发现进程的时间片用完，向进程发送一个SIGALRM信号

b. 保存上下文：保存进程A的上下文。用户态的上下文保存到pt_regs（内核堆栈一部分），进入内核态。进入内核态把通用寄存器、sp（为了保存内核堆栈地址）、pc（保存执行流）、fp（浮点数）、LR（链接）等保存到task_struct的cpu_context中。（ttrb0_el1保存了用户空间页表基地址，但是已经在task_struct的mm_struct中的pgd中保存了，不需要再保存。ttrb1_el1是内核空间页表首地址，所有进程共用，所以不需要切换）

c. 刷新TLB，因为不同进程TLB肯定不能共用（参考ASID机制可以实现共用，并且如果是同一进程的不同线程的切换则不需要）

d. 操作系统根据调度算法，如Linux中默认的调度算法为CFS，决定运行的进程B

e. 恢复进程B的上下文，分为内存地址空间和硬件上下文，内存地址空间是否需要恢复取决于是在同一进程的不同线程切换还是不同进程的线程切换。（这是进程和线程上下文切换的区别）内存地址空间的切换是通过switch_mm()实现，本质是将mm_struct中的gpd放到ttrb0_el1寄存器中。接下来就是switch_to_cpu()将cpu_context中的寄存器恢复。接下来就是从内核状态恢复到用户状态，从pt_regs弹出通用寄存器的值，恢复到进程B切换上下文前执行的地方。

一篇文带你了解Linux内核进程上下文切换 - 知乎 (zhihu.com)

再做一下总结：用户进程到内核进程（比如系统调用，IO中断）都是将通用寄存器等信息保存到内核堆栈的pt_regs中的，并且这个过程不需要保存pgd信息（内核进程用的是ttrb1_el1寄存器的页表，是内核空间的，所以全局共用的）。同一进程的不同线程之间只需要切换cpu_context，不同进程的线程之间还需要将pgd放到ttrb0_el1中。

什么时候会释放CPU？除了时间片结束还有哪些情况会提前释放CPU？

1. 阻塞：进程执行某些操作时，例如等待I/O操作完成、等待其他进程发送信号等，由于这些操作需要等待外部事件，因此进程需要阻塞并暂时释放CPU资源。
2. 信号：进程可以接收到一些由内核或其他进程发送的信号。当进程接收到信号时，它需要停止正在执行的代码并处理信号，然后再恢复之前的执行状态。

可以总结为除了切换CPU资源就是把CPU资源让给中断服务程序和信号处理程序

1.6.3. 中断

基本概念：

1. 设备控制器：块设备和字符设备 三个寄存器：数据寄存器、状态寄存器、命令寄存器

CPU与设备控制器通信的方法：端口I/O(in out指令) 和 内存映射 I/O

DMA：

1. CPU给DMA下发指令，放到什么内存位置，之后就没有CPU的事了
2. DMA请求磁盘控制器将数据放入内存
3. 磁盘控制器把数据放入内存
4. 磁盘控制器通知DMA
5. DMA通知CPU

区分驱动程序和设备控制程序：驱动程序在操作系统内部，设备控制程序属于硬件

1.6.4. 中断流程

1. 外部设备通过中断控制器发起I/O中断通知CPU，也可以是软件产生的软中断信号。
2. 进程保存中断上下文到内核栈
3. 根据中断号，查中断向量表，执行中断服务程序
4. 恢复中断上下文

中断: Linux 操作系统有 256个中断，分为两种

1. 硬中断：通过硬件向 CPU 发出信号触发中断，（如：网卡接受数据包）
2. 软中断：常见的有信号和系统调用

中断处理程序

1. 常见的有
2. 时钟中断处理程序：负责处理定时器产生的时钟中断，触发进程调度。
3. IO 中断处理程序：磁盘、网卡
4. 异常中断处理程序：负责处理异常事件，如缺页、段错误等。

1.7. 进程调度

算法：

1. 先到先服务 一个长任务在前，其他都卡住了

2. 最短作业优先 无法预知

3. 时间片轮转 如何设置合理的时间

4. 最高优先级 饿死，随年龄变化

5. 多级反馈队列：最高优先级+时间片轮转

1.8. 进程、线程、协程的区别

1.8.1. 进程和线程的区别

1. 线程占用空间更小。线程拥有自己的栈（用户栈或者内核栈），而同一进程和线程的堆内存是共享的。进程之间的的内存是隔离的
2. 线程更为轻量。从创建的角度来看，进程会copy一份完整的PCB结构，也会拷贝内核栈，也会拷贝进程的整个内存空间（COW）。线程只需要新增一个用户栈pthread，然后PCB都指向原来的，只是引用计数+1。
3. 共同的task struct结构

1.8.2. 线程和协程区别

协程相当于用户自己实现了一套用户态线程，不会线程切换陷入内核，Go语言自己实现了调度器，处理队列等

1. Goroutine比线程内存占用更小，因为有更多信息被共享到堆上
2. Goroutine更轻量，线程上下文切换不需要陷入内核

2. 内存管理

2.1. 虚拟内存

2.1.1. 虚拟内存是如何组织的

所有的组织是体现在PCB中的struct_mm *mm中的，内核线程的mm = NULL，在创建新的进程的时候会完整拷贝struct_mm，创建线程的时候还是会引用相同的struct_mm

struct mm_struct {
    unsigned long task_size;    /* size of task vm space */
    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 mmap_base;  /* base of mmap area */
    unsigned long total_vm;    /* Total pages mapped */
    unsigned long locked_vm;  /* Pages that have PG_mlocked set */
    unsigned long pinned_vm;  /* Refcount permanently increased */
    unsigned long data_vm;    /* VM_WRITE & ~VM_SHARED & ~VM_STACK */
    unsigned long exec_vm;    /* VM_EXEC & ~VM_WRITE & ~VM_STACK */
    unsigned long stack_vm;    /* VM_STACK */

       ...... 省略 ........
}

start_code 和 end_code 定义代码段的起始和结束位置，程序编译后的二进制文件中的机器码被加载进内存之后就存放在这里。

start_data 和 end_data 定义数据段的起始和结束位置，二进制文件中存放的全局变量和静态变量被加载进内存中就存放在这里。

end_data和start_stack之间的是bss段，未初始化的全局变量和静态变量

start_stack栈顶

mmap_base动态内存映射，mmap存放文件映射，动态链接库

start_brk, brk 堆顶，堆底指针

组织方式是通过vm_area_struct通过双向链表+红黑树组织的

2.2. 访问虚拟内存到访问物理内存的过程

a. CPU根据操作数和寄存器的值生成一个虚拟地址（这部分在MMU内完成）

b. 访问TLB中查找虚拟地址与物理地址的转换

c. 如果TLB中没有找到，则访问页表查找物理内存

​ i. 如果页表有n级，则需要访问n次页表。在Linux为四级页表

d. 如果页表项没有被加载，则发生缺页异常，向OS发送一个缺页中断，发生进程的上下文切换，os负责到buddy系统中申请内存。或者说内存页在磁盘上，那么需要换入页。然后再切换回该进程。

2.3. buddy伙伴算法和大页机制

Linux的内存分配系统使用伙伴算法

order数组，11个元素，每个位2^0 - 2^10大小

申请算法：

1. 如果2 ^ i有空闲则直接分配

2. 如果没有空闲页，则查找2^ (i + 1)，如果有则分配出去2 ^ i，剩下的2 ^ i 退回给上一层

3. 2 ^ (i + 1)也没有，重复2

4. 仍没有，返回内存分配失败

回收算法：

1. 查找 2^i 个页块对应的块链表，是否有与其物理地址是连续的页块，如果没有，则无需合并

2. 如果有，则合并成 2^(i +1)的页块，以此类推，继续查找下一级块链接，直到不能合并为止

大页机制：Linux 标准大页和透明大页-腾讯云开发者社区-腾讯云 (tencent.com)

2.4. 申请内存时，如果内存不够了怎么办？

三段斧：

1. 内存压力大，kswapd0 会执行后台异步内存回收，直到剩余内存大于高阈值（pages_high）为止。回收page cache中的不活跃的页面（文件页，分脏页和干净页。干净页直接回收，脏页先刷盘再回收。基于active list和inactive list的LRU置换）
2. 内存基本耗尽，开启同步阻塞进行内存清除（必须开启swap机制），将匿名页（栈、堆数据）swap out到磁盘。
3. OOM Killer杀死占用内存最大的进程
4. 爆OOM错误

2.4.1. 避免预读失效和缓存污染

本质是LRU的问题：设置两个或两段list，且进入active list阈值提高

4.5 如何避免预读失效和缓存污染的问题？ | 小林coding (xiaolincoding.com)

2.5. MMU？TLB？多级页表？

2.5.1. MMU

（1）软件实现

1. 比如ldr 4100， 线用4100/pageSize算出虚拟页号为1，再用4100 mod pageSize算出页偏移为4
2. 查找页表中页号为1对应的PTE（物理帧号），假设为5。这个过程首先要访问页表基地址寄存器ttrb找到页表的起始地址，再用PTE地址 = 页表基地址 + 页号 * sizeof(PTE)算出页帧5的基地址
3. 再用这个页帧5的基地址+页偏移算出物理内存地址

（2）MMU硬件加速的计算

1. MMU可以计算页号和页偏移
2. 从页表中找到PTE帧号并计算出对应物理帧基地址也可以由MMU计算出来
3. 对页帧基地址 + 页偏移也可以由MMU计算
4. 整个过程的数据交换可以放在MMU的寄存器中

2.5.2. TLB

cache，将虚拟地址到物理地址的对应关系维护在cache中

2.5.3. 多级页表

单级页表内存占用太大，多级页表占用内存小但拖慢时间

Linux支持最大4级页表：

1. 一级页表：PGD(Page Global Directory)
2. 二级页表：PUD(Page Upper Directory)
3. 三级页表：PMD(Page Middle Directory)
4. 页表项：PTE

2.6. malloc两种申请内存方式

brk() and mmap()

只是建立页表映射，没有真正分配物理内存，使用时会发生缺页中断然后分配物理内存

<128k，是brk()在堆上分配，直接移动堆指针。而且调用free()后堆内存还在，放到malloc内存池了以便回收。不好在会产生内存碎片。

大于128k，是mmap()在文件映射区申请内存空间，free()之后会被释放。因为会调用缺页中断，耗费资源。

3. 文件系统

3.1. VFS

3.1.1. 文件描述符

文件描述符就是内核为了高效管理这些已经被打开的文件所创建的索引，其是一个非负整数，用于指代被打开的文件，所有执行I/O操作的系统调用都通过文件描述符来实现。

task_struct中包含了fs和files，fs用来描述进程自身的文件系统信息，files里包含了该进程打开的一些文件描述符（默认前三个是系统标准输入、输入、异常流）

3.1.2. VFS四个对象

1. 超级块对象 super_block：记录了文件系统的信息，比如文件系统的总大小。整个文件系统的抽象
2. 索引节点对象 inode：拥有者、权限、文件大小。是磁盘上具体文件的抽象
3. dentry 目录项： 目录、层级结构的抽象
4. 文件对象 file：代表进程打开的文件，是VFS在创建对象的过程中生成的，在磁盘上无记录数据，供进程直接处理

文件描述符指向：file->dentry->inode->super_block

这四个对象描述了这些信息：文件打开计数器（file），文件磁盘位置（inode？），访问权限（inode？），文件指针（进程唯一）

3.2. inode与块存储

文件系统分为inode与block，inode存储了文件除了文件名和数据之外的所有信息。

3.2.1. inode存储了什么

文件类型，文件权限，文件修改时间，文件大小，以及i_block数组（真正起到索引作用，见下面的图)

struct ext4_inode {
    __le16  i_mode;     /* File mode */
    __le16  i_uid;      /* Low 16 bits of Owner Uid */
    __le32  i_size_lo;  /* Size in bytes */
    __le32  i_atime;    /* Access time */
    __le32  i_ctime;    /* Inode Change time */
    __le32  i_mtime;    /* Modification time */
    __le32  i_dtime;    /* Deletion Time */
    __le16  i_gid;      /* Low 16 bits of Group Id */
    __le16  i_links_count;  /* Links count */
    __le32  i_blocks_lo;    /* Blocks count */
    __le32  i_flags;    /* File flags */
......
    __le32  i_block[EXT4_N_BLOCKS];/* Pointers to blocks */
    __le32  i_generation;   /* File version (for NFS) */
    __le32  i_file_acl_lo;  /* File ACL */
    __le32  i_size_high;
......
};

3.2.2. inode实现的文件系统

早期的ext2,ext3中inode的i_block数组，前12项直接存的block的位置。

如果一个文件比较大，12块放不下。当我们用到i_block[12]的时候，这个块我们称为间接块。

如果文件再大一些，i_block[13]会指向一个块，我们可以用二次间接块。二次间接块里面存放了间接块的位置，间接块里面存放了数据块的位置，数据块里面存放的是真正的数据。

如果文件再大点，则需要多次IO才能找到，ext4可以解决这个问题。详见：

一文让你彻底了解Linux内核文件系统(大总结) - 知乎 (zhihu.com)

3.2.3. 快速查找空闲内存

inode的位图大小为4k，每一位对应一个inode。如果是1，表示这个inode已经被用了；如果是0，则表示没被用。block的位图同理。

因为通过位图块4k能表示空间有限128M，所以把文件系统分成块组

我们还需要有一个数据结构，对整个文件系统的情况进行描述，这个就是超级块ext4_super_block。里面有整个文件系统一共有多少inode，s_inodes_count；一共有多少块，s_blocks_count_lo，每个块组有多少inode，s_inodes_per_group，每个块组有多少块，s_blocks_per_group等。这些都是这类的全局信息。

3.2.4. 目录的存储格式

对于目录的block里面存的是文件信息，包括了文件名和inode等信息，通过这个inode就可以去找整个文件。

一般可能会通过hash索引来建立目录格式，文件名称会取hash，再对应到目录块号。于是找某个文件名的时候可以通过hash直接判断是否不在该目录里面，如果可能再再去对应的块号去找。

3.3. 硬链接和软链接的区别

• 硬链接：和原文件是同一个文件 inode、权限、内容都相同

• 软连接：相当于是8B快捷方式 inode不同

硬链接的用途

• 用途：对重要文件创建一个硬链接可以防止误删，因为只有当一个inode的最后一个链接被删除后，整个inode才会被删除
• 硬连接与复制的区别：建立硬链接的两个文件，当其中一个改变时另一个也会同步改变

3.4. 用户写了4KB写到磁盘上经历的过程

（1）write:

1. 用户态转化为内核态

2. 经过vfs层的API（vfs为了统一不同类型文件系统的接口，方便上层使用，比如ext4，/proc内存文件系统）（vfs属于内核层）

3. 写到page cache（page cache在vfs之后 ext4，os希望page cache对它不可见）（这里涉及的是write back，linux不支持write through）

4. 经过ext4的API

5. IO调度程序会通过合适的IO算法来调度指定的存储介质

6. 写文件（打开的文件的inode一般已经写在了PCB的目录项上了，不需要从根目录再层层去找该文件了吧？），通过inode找到block，并更新数据。写完后需要更新inode中的相关信息：大小，修改时间

（2）如果是mmap调用，则不需要经过用户态和内核态的转化（内核态到用户态缓存的拷贝）

（3）如果是direct IO(使用open系统调用，且设置标志位为O_DIRECT)，则不需要经过page cache，但是用户程序需要维护一层cache

3.4.1. cp和mv的时候inode如何变化？

1. 当使用cp命令创建文件时，新文件和旧文件的inode不同
2. 对于mv操作，如果是移动到同一个文件系统中，inode不会变化，否则会发生变化

3.5. 零拷贝技术有哪些

3.5.1. mmap本质

1. 在多级页表中建立进程虚拟地址和文件地址之间的映射
2. 第一次独写mmap映射的内存，由于页表未与物理内存映射，触发缺页异常
3. 查询page cache是否有缓存，如果没有则从磁盘加载到page cache

可以看出来本质就是用户进程可以直接通过自己的虚拟地址操作内核空间的page cache内存地址的内存

mmap与fread，direct IO的比较

1. read需要经过标准库的缓存->page cache两个缓存

2. mmap省略了从内核态的page cache拷贝到用户态缓存的开销，因为可以直接操作page cache的内存

3. direct IO不仅省去了page cache拷贝到用户态缓存的开销，还省去了磁盘copy到page cache的开销，但是可能需要用户进程维护一个cache

大文件

大文件会堆满page cache，不适合用mmap零拷贝：

小文件传输：mmap零拷贝

大文件传输：异步io + 直接io

3.5.2. 其他零拷贝技术

https://xiaolincoding.com/os/8_network_system/zero_copy.html#%E4%B8%BA%E4%BB%80%E4%B9%88%E8%A6%81%E6%9C%89-dma-%E6%8A%80%E6%9C%AF

1. Linux中DMA技术可以实现零拷贝
2. MySQL中为了避免使用page cache，使用direct IO实现了零拷贝
3. Java NIO中使用零拷贝技术避免了用户态数据与内核态数据的copy

3.6. page cache

主要包含：

1. File-backed pages：文件备份页也就是 Page Cache 中的 page，对应于磁盘上的若干数据块；对于这些页最大的问题是脏页回盘；
2. Anonymous pages：匿名页不对应磁盘上的任何磁盘数据块，它们是进程的运行是内存空间（例如方法栈、局部变量表等属性）

可以类比于RMDB中的Buffer Pool，swap机制是换出的page cache的Anonymous pages，Linux的LRU置换算法也是置换的page cache的File-backed pages。

3.6.1. buffer io刷盘时间

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

3.7. IO调度器，磁盘调度算法

1. 先来先得FIFO
2. 最短优先
3. 电梯
4. CFQ