学习参考

Linux 0.11 闪客Linux0.11代码赵炯《Linux内核0.12完全注释》 csapp 哔哩哔哩 OSTEP

一、操作系统启动

一、bios

刚上电时OS在存储设备中，需要将其放入内存中才能让cpu取指执行

上电cs:ip指向0xffff0（固定下来）
这里是bios：
1. 电源自检（POST）：检查硬件设备是否正常，包括内存、键盘、鼠标等，并在物理地址 0 处开始设置和初始化中断向量
2. 引导序列：根据BIOS设置的启动顺序，查找包含操作系统的启动设备（如硬盘、U盘等），检查磁盘的第0磁头第0磁道第1扇区的内容是否以 0x55aa 结尾。
3. 加载引导扇区：从启动设备上读取引导扇区到内存，并执行其中的引导加载程序。
4. 加载操作系统：引导加载程序会找到操作系统的内核，加载到内存，并将控制权交给操作系统。

二、bootsec（引导加载程序）工作：

将自己从0x7c00移动到0x90000
int 0x13（读磁盘中断）将后面setup扇区读入内存中，al放扇区数量，cl放开始扇区索引号，es:bx指向setup扇区在内存的位置0x90200（boot扇区地址+512，因为boot扇区512字节大小）
int 0x10（读字符），显示loading system
int 0x13读system到0x10000
1. _~~（疑问：真的放在0x10000了吗，为什么不直接放入0地址处）
2. 回答：因为刚开始0地址存放的中断向量表，setup前面需要读取中断向量
将cs:ip指向setup扇区

三、setup模块工作：

通过中断获取硬件参数信息，存放到0x90000中，覆盖掉bootsec
将system移动到0地址处
进入保护模式
跳转到system

四、从实模式进入保护模式

为什么要有保护模式：实模式的寻址方式使程序可以直接访问物理地址，一个程序可以修改另一个程序导致后者崩溃，不安全
将cr0的最低位置为1启动保护模式
保护模式下段寄存器仍为16位
保护模式下，段寄存器（16位）不直接存放地址，而是段选择子，其中13位是段描述符在描述符表中的索引号，一位表示GDT或LDT，两位表示特权级，由描述符索引*8 + GDTR中的基地址可以访问某个段的段描述符
1. 描述符索引为0时，对应第一个段描述符（但处理器不用第一个段描述符）
保护模式下，将可访问的段的信息（段描述符）存放在一张表中（GDT或LDT），通过段描述符可以访问到该段
1. 段描述符存在一张表中，一个段描述符8字节
2. 段描述符里面有这个段的信息，例如粒度位（字节或4kb为单位），描述符类型，特权级，段的基地址，大小
通过段的基地址加偏移地址可访问该段
setup先加载加载全局描述符表寄存器（存放GDT的地址），再执行jmpi 0,8，将cs置为8，查表可知指向的段基址为0，将ip置为0，即跳转到0地址处，也就是system处

五、head.s

head.s 程序在被编译生成目标文件后会与内核其他程序的目标文件一起被链接成 system 模块，并位于 system 模块的最前面开始部分
head.s中使用AT&T格式32位汇编
初始化了IDT和GDT，开启A20号线
设置分页
执行完跳转到main.c（汇编调用c函数）

六、main.c

初始化各种硬件（除了鼠标）

二、操作系统接口

一、什么是接口？（系统调用）

用户通过命令行、图形界面来操作计算机硬件；命令行、图形界面本质也是c程序，但其中包含一些能进入操作系统来操作硬件的函数，这些函数调用就是接口，因为由系统提供，又称为系统调用
posix：ieee定义的系统调用标准，可以查到系统调用（不同操作系统接口各不相同的话，应用程序使用不便）

二、系统调用的实现

应用程序不能直接调用接口，因为可能访问到root密码等不该访问的内容

用户态和内核态

why：防止用户程序对系统进行破坏
what：
1. 用户态：进程执行自己的代码时，处于用户态，只能访问有限的硬件资源
2. 内核态：当进程执行系统调用陷入内核代码中执行时，处于内核态，可以访问所以硬件资源
特权级：**级别越低权限越高，**用户态3级，内核态0级
1. 当前特权级 CPL（Current Privilege Level）：CPL 是当前正在执行程序或任务的特权级。它存放在CS 和 SS 段寄存器的位0和位1中
2. 描述符特权级 DPL（Descriptor Privilege Level）：它存放在段或门描述符的 DPL 字段中，描述目标段特权级_（系统段的DPL在head.s中初始化为0）_
how：硬件提供了主动进入内核的方法，对于x86，就是中断指令int 0x80
1. 先将系统调用号置给%eax，再调用int 0x80
2. int将cs的CPL置为0
3. 用户程序进入内核的唯一方法
4. 系统调用通过一段包含int指令的代码，系统提供中断处理函数，获取想调取程序编号
5. 操作系统根据编号执行相应代码
int 0x80中断的处理：
1. 保护现场（详细过程）
2. 由中断号到IDT表中找到对应的中断描述符，由中断描述符得中断处理函数sys_call
3. sys_call()将用户态的寄存器内容保存到栈中，再由sys_call和%eax寄存器中的系统调用号去sys_call_table中找到对应的系统调用函数执行，每个系统调用函数地址4字节
4. 返回现场

sched_int()函数、set_system_gate函数（层层调用）初始化了中断描述符：将sys_call函数地址写入描述符中，并将DPL置为3，设置中断描述符种类（先存到寄存器中，再移到idt表中）参考1，参考2，此时cs为中断描述符的中的段选择符（8，索引为1），CPL为0，此时可以访问内核代码

系统调用可通过C库函数作为中介，因为C库将系统调用层层封装其最底层用_syscalln()宏，因为很多系统调用函数的形式相同，其中包含0x80中断例如write（）

中断

中断：系统或处理器处理某程序时出现一个事件，需要处理器处理，这个事件会导致从当前运行程序转移到中断处理程序执行
中断向量：中断服务程序的入口地址
中断向量表：所有中断向量组成的一个查询表，位于0地址处，共256*4字节（1kb）（进入保护模式后，在head.s中重新设置中断描述符表）
int 128（0x80）称为系统调用，是用户程序和操作系统资源唯一的接口界面
中断描述符：类似中断向量，保护中断处理程序的地址和中断类型，八字节
中断描述符表（IDT）：类似中断向量表，中断描述符的列表，8*256字节 = 2kb
类似于GDT，IDTR中保存IDT基地址，加上中断号*8可得中断描述符的地址

三、进程管理

通过进程管理，操作系统管理明白了cpu

cpu工作原理就是取指令、执行，只需要设置好初始pc，cpu就会自动工作
io设备运行速度远远远....低于cpu运行速度，因此io指令非常慢，执行io指令时cpu干嘛？将cpu切换到另外一个程序执行，提高cpu利用率，即多道程序，交替执行

一个cpu上交替执行多个程序：并发
如何实现程序切换？在程序切换前将程序状态保存（地址、数据等，否则另一个程序会改变寄存器的值），因此运行的程序跟静态的程序不同，需要记录他们的状态

一、进（进行的）程（程序）：一个运行、执行中的程序

进程有开始、结束，程序没用
进程会走走停停
进程需要记录运行的状态
为了完成一个任务，启动一个进程
用户使用计算机就是启动很多的进程
**PCB（Process Control Block）：**task_struct结构体，操作系统用来记录进程信息的数据结构，包含进程号、父进程号，执行的位置，现场的数据等信息来管理进程
有一些进程等待执行（就绪队列），有一些进程等待某事件（例如磁盘等待队列）；把进程根据状态区分开

进程如何交替：schedule()函数，从就绪队列找到下一个进程getNext()函数（调度，从就绪队列中选哪个进程），再进行切换switch_to()函数
**switch_to()函数：**把当前cpu中寄存器的内容（上下文）保存到当前进程pcb中，把下一个进程中pcb的内容存回cpu中
一个进程有可能会访问存放另外进程的地址，对后者造成破坏，解决办法：限制对后者地址的读写，通过映射表，多个进程在内存中共存
两个进程共享数据会发生生产者消费者问题（竞争），因此需要进程间同步与合作，不能随便进行进程间切换
进程=资源＋指令执行序列
进程是在内核中通过系统调用fork()创建的，因为进程要访问硬件资源
Linux中五种进程状态
运行状态（TASK_RUNNING）：当进程正在CPU上执行或准备就绪随时可被调度执行（就绪态）
可中断睡眠状态（TASK_INTERRUPTIBLE）：当系统产生中断或释放进程正在等待的资源或进程收到一个信号，可唤醒进程进入就绪态
不可中断睡眠状态（TASK_UNINTERRUPTIBLE）：只有使用wake_up函数才可唤醒
僵死状态（TASK_ZOMBIE）：进程已经停止运行，但父进程还没有调用wait询问其状态，此时子进程的PCB仍保留
暂停状态（TASK_STOPPED）：当进程收到一个相关信号时（例如 SIGSTOP、SIGTSTP、SIGTTIN 或 SIGTTOU）就会进入暂停状态。可向其发送 SIGCONT 信号让进程转换到可运行状态。

二、多进程间切换——用户级线程

**线程：**在进程切换的时候，只切换指令执行序列，而不改变资源（例如内存，共用一个映射表），保留了并发的优点，避免了进程切换代价（不需要切换映射表）
多个线程之间切换（yield()函数）如果用一个函数栈会导致执行顺序错误，因此需要多个栈分别存放各个线程的函数，在线程切换时，先切换tcb，再切换栈（将当前esp寄存器值入tcb，将目标tcb赋给esp）；不同的栈的地址需要保存在**TCB（Thread Control Block）**中

esp寄存器中存放当前栈地址

ThreadCreate()函数，开辟tcb，栈空间，栈中存放初始地址，将tcb和栈地址关联
用户级线程：若一个进程中的某个线程进入内核并阻塞，该进程就不会执行，cpu转去执行另一个进程内核级线程：相同情况，cpu执行该进程另一个线程，并发性更好

三、内核级线程

并行：多处理器同时执行多线程

内核级线程要在用户态和内核态运行，所以内核态和用户态都需要栈
iret指令：中断服务程序最后一条指令，将栈中的堆栈段地址和偏移地址弹出，使程序跳转到原来中断发生的地方
内核级线程切换：
1. 用户级线程a通过中断陷入内核态（在这之前已经保存了用户栈）
2. int命令找到内核栈（硬件完成），存入用户态的段基址，偏移地址，标志寄存器，pc寄存器等，关联到用户栈
3. 调用switch_to()函数，将当前esp存入当前tcb中，再找到b线程的tcb，并将栈地址赋给esp，再用ret指令跳转执行b线程
4. b线程内核栈顶存放iret中断返回指令，执行该指令将内核栈中用户态段寄存器，偏移寄存器等值返回

四、进程实现

一、进程的创建

idle进程：0号进程，系统创建的第一个进程，PID=0，让cpu空转，创建一号进程，一号进程创建后面所有进程

fork()：是系统调用，会引起中断，用于创建子进程
1. 通过fork，被创建的称为子进程，创建者称为父进程
2. 子进程从fork函数返回的地方执行
3. 父进程和子进程是并发执行
4. 一次调用，两次返回：对于子进程，返回0，对于父进程，返回子进程pid
fork执行过程
1. 执行int 0x80，cpu将用户栈的栈地址、标志寄存器、用户态下的pc放入内核栈**（硬件执行）**
2. int 0x80跳转到中断处理函数_system_call，将用户态下的一些寄存器放入内核栈**（中断服务函数）**

上面两步将用户态执行现场保护到内核栈中

通过%eax中保存的系统调用号2去sys_call_table中找到sys_fork函数跳转执行，该函数用于创建子进程
sys_fork函数先调用find_empty_process，用于获取一个新进程号
再将一些寄存器压入栈
再调用copy_process函数，用于创建并复制进程的数据段代码段以及环境

copy_process函数的参数是内核栈中内容，其中包含了用户态的栈地址、段寄存器、标志寄存器等信息

  1. 首先申请一块内存存放新进程的的PCB，将新PCB指针放入任务数组中，并把当前进程的PCB内容复制到新进程PCB中

子进程和父进程具有相同的用户栈、本地变量、全局变量，堆和代码，但却有自己私有的地址空间

  2. 更改当前进程状态为不可中断等待状态，设置新进程pid，时间片等

%eax寄存器中保存函数返回值

  3. 修改TSS内容：
     1. 设置好子进程的内核栈
     2. 设置eax寄存器设为0
     3. 寄存器的值置为函数参数，**其中也关联了父进程的用户栈（因此子进程在用户态拥有父进程fork函数之后的代码）**

（回到system_call中代码）判断当前进程如果未就绪或时间片用完，则调度切换到另一个进程

current：存放当前pcb指针

到ret_from_sys_call函数，见2-2中图，从中断返回，最后包含iret指令

pcb结构体中state项表明任务运行的状态，-1为不可运行，0为可运行（就绪），＞0为停止

二、进程切换的实现

一个进程的现场：代表这个进程当前运行状态的通用寄存器

TR任务寄存器：保存着当前TSS（任务状态段）的段选择子和描述符，可以借此从GDT中找到TSS基地址
TSS：结构体，保存在task_struct结构体中，进程切换时用来保存和恢复上下文的，里面含有当前各个寄存器的信息
switch_to函数：切换到下个进程（下个进程已经被调度选好）
1. 判断下个进程是当前进程吗？是的话直接退出
2. 将新任务的pcb指针保存到current变量中，当前任务的pcb指针保存在ECX寄存器中
3. ljmp长跳转指令**（硬件执行）**
  1. 处理器自动将当前进程上下文保存到对应TSS中
  2. 处理器从新TSS中加载上下文到当前cpu
  3. 处理器更新当前tr，使其指向当前TSS
  4. 通过新进程TSS的选择子找到新任务的指令地址进行执行

五、CPU调度策略

switch_to函数的前一步，如何找到下一个进程

追求目标：
1. 周转时间（从任务进入到任务结束，完成时间-到达时间（创建该进程的时间））短
2. 带权周转时间（周转时间/运行时间）低
3. 等待时间（周转时间-运行时间）
4. 响应时间（从操作发生到响应）短
5. 完成任务数量（吞吐量）大
存在的问题，需要折中综合考虑
1. 矛盾
  1. 响应时间短->切换次数多->系统内耗大->吞吐量低

进程切换有开销

前台任务关注响应时间，后台任务关注周转时间
两种任务
1. IO约束型任务：IO操作多，cpu运行少，应该高优先级
2. CPU约束型任务：cpu运行多，IO操作少，应该低优先级

一、调度算法

eg：

First Come，First Served(FCFS)
1. 先来先服务
2. 对长进程有利，短进程不利（带权周转时间大）
3. p1->p2->p3->p4
SPF（Shortest Process First）短进程优先
1. 追求平均周转时间、平均带权周转时间、平均等待时间最短
2. 选择当前已到达且运行时间最短的进程先执行
3. p1->p3->p2->p4
4. SRTN(Shortest Remaining Time Next)最短剩余时间优先
  1. 抢占式调度，即当前进程没有执行完也会被切换，被踢走
  2. 非抢占式调度：不会中断正在执行的进程，只能进程主动退出
  3. 当有进程进入就绪队列时就调度，当一个进程完成也要调度，和当前进程比较谁剩余时间更短，若新进程更短，则抢占调度
  4. p1->p2->p3->p2->p4->p1
5. 缺点：
  1. 对长进程不利
  2. 运行时间由用户提供，不一定真实
  3. 长进程长时间得不到执行，可能会饿死
RR（Round Robin）：时间片轮转
1. 公平的、轮流的让每个进程执行一个时间片，再切换到下一个进程
2. 用于分时操作系统，更注重响应时间

分时操作系统：通过时间片轮转给多用户使用，切换的很快让每个用户感觉计算机仅为自己服务（棋王多人对战）；人机交互；不能处理紧急任务

属于抢占式调度，由时钟装置发出时钟中断（外中断）通知CPU时间已到
新进程（先放）和执行完一个时间片的进程（后放）放入就绪队列队尾
要点是确定时间片的大小，时间片太大，响应时间太长，时间片太小，会导致增加浪费在进程切换的时间
响应时间和周转时间都存在
1. 一种调度算法让多种类型任务都满意
2. 办法：定义前台任务和后台任务两个队列，前台用RR，后台用SPF，队列间用优先级调度
  1. 前台优先级高会导致后台可能一直无法执行；提高后台优先级导致一直执行后台任务，无法保障前台响应时间
  2. 要以RR为核心（前台响应），又要考虑优先级、SPF......
  3. 如何分辨前台后台任务
Schedule()函数
1. Linux进程在用户态时是抢占式的
2. 优先级排队策略

void schedule(void)
{
    int i,next,c;
    struct task_struct ** p;

    /* check alarm, wake up any interruptible tasks that have got a signal */

    for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
        if (*p) {
            if ((*p)->timeout && (*p)->timeout < jiffies) {
                (*p)->timeout = 0;
                if ((*p)->state == TASK_INTERRUPTIBLE)
                    (*p)->state = TASK_RUNNING;
            }
            if ((*p)->alarm && (*p)->alarm < jiffies) {
                (*p)->signal |= (1<<(SIGALRM-1));
                (*p)->alarm = 0;
            }
            if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
                (*p)->state==TASK_INTERRUPTIBLE)
                (*p)->state=TASK_RUNNING;
        }

    /* this is the scheduler proper: */

    while (1) {
        c = -1;
        next = 0;
        i = NR_TASKS;
        p = &task[NR_TASKS];
        while (--i) {
            if (!*--p)
                continue;
            if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
                c = (*p)->counter, next = i;
        }
        if (c) break;
        for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
            if (*p)
                (*p)->counter = ((*p)->counter >> 1) +
                (*p)->priority;
    }
    switch_to(next);
}

核心算法（25行以下）：

从任务数组队尾开始，跳过空格，从**运行状态（包含就绪态）**挑出counter最大的任务（剩余时间最多的），将其索引号赋给next
如果counter≠0，即存在任务没运行完，此时next为该任务的索引号，跳出while循环，执行switch_to函数
如果任务数组为空，即其中没有可运行的任务，p=-1，next=0，跳出while循环，执行switch_to函数
此时进入for循环，对系统中所有进程（包括睡眠的进程）重新计算counter（睡眠进程唤醒时counter比较高），执行counter = 1/2counter + priority;
再回到26行循环执行上述过程（找到最大counter执行）
IO时间越长，counter越大，变相照顾到前台进程

六、进程的同步和信号量

生产者消费者问题：一群生成者进程生产产品，将产品放入具有一定大小的缓冲区中，一群消费者进程进去消费
1. 不能向满的缓冲区中放入产品
2. 不能向空的缓冲区取产品
3. 同一时刻只允许一个生产者或消费者存或取一个产品
进程合作：多个进程共同完成一个任务
进程同步：进程走走停停保证多进程合作的合理有序
需要信号量来保证进程、线程的同步进行而不会冲突

有一个共享缓冲区，生产者放入数据，消费者取出数据

如何判断何时停？看信号量sem（semaphore），生产者看到为负数则停止，消费者看到为负则执行一个生产者，信号量加一（理解为饭店排队取号，外面几个人排队信号量为负几）
P操作为减少资源数量，如果为负数，则表示有多少进程在等待，并阻塞当前进程
V操作为增加资源数量，如果为负数，则表示有多少进程在等待，并唤醒队列中第一个进程
信号量：包含剩余资源数量和进程等待队列的结构体（Posix里为sem_t）

struct semaphore {
    int value;//可用资源数量
    PCB *queue;//进程等待队列
}

P(semaphore s) { //消费资源
    s.value --;//先将资源数减一
    if (s.value < 0) {//如果此时资源数小于0，即没有资源可用
        sleep(s.queue);//则将当前进程加入阻塞队列s.queue（拿号排队）
    }
}

V(semaphore s) { //生产资源
    s.value ++;//先将资源数加一
    if (s.value <= 0) {//如果此时资源数小于等于0，即没有资源可用（门口仍有排队）
        wake(s.queue);//则执行队列中的进程（让排队的进屋就餐）
    }
}

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>

sem_t sem;  // 定义一个信号量

void* func(void* arg)
{
    // P操作
    sem_wait(&sem);  // 等待信号量的值大于0，然后将其减1
    printf("%s 获取到了信号量，开始工作...\n", (char*)arg);
    sleep(2);
    printf("%s 工作完成，释放信号量...\n", (char*)arg);
    // V操作
    sem_post(&sem);  // 释放信号量，将其值加1
}

int main()
{
    pthread_t t1, t2;
    // 初始化信号量，其初值为1
    sem_init(&sem, 0, 1);

    pthread_create(&t1, NULL, func, (void*)"Thread-1");
    pthread_create(&t2, NULL, func, (void*)"Thread-2");

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    sem_destroy(&sem);  // 销毁信号量

    return 0;
}

信号量解决生产者消费者问题
1. 定义两个信号量：
  1. empty表示剩余缓冲区个数（空座），初始为BUFFER_SIZE
  2. full表示产品数量（客人），初始为0
2. 生产者进程先执行**P(empty)操作减少缓冲区个数，若为负（表示没有缓冲区，即缓冲区满了，饭店没座了）则阻塞当前进程（不允许继续生产、往里进客人），否则继续执行，向缓冲区放入一个产品（减少一个缓冲区），随后执行V(full)**操作，增加产品数量，若为非正数（没有产品，没有乘客出租车多）则唤醒full信号量队列中第一个消费者进程（排队的出租车拉走这个乘客）
3. 消费者进程先执行**P(full)操作减少产品个数，若为负（表示没有产品）则阻塞当前进程（不允许继续消费产品），否则继续执行，从缓冲区取走一个产品，随后执行V(empty)**操作，增加缓冲区数量，若为非正数（没有缓冲区）则唤醒empty信号量队列中第一个生产者进程（叫号用餐）

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>

#define BUFFER_SIZE 10  // 定义缓冲区大小为10

int buffer[BUFFER_SIZE];  // 定义一个大小为BUFFER_SIZE的缓冲区
int in = 0;  // 定义一个指针，指向缓冲区的下一个空闲位置
int out = 0;  // 定义一个指针，指向缓冲区的下一个产品

sem_t empty;  // 定义一个信号量，表示缓冲区的空闲位置数量，初始值为BUFFER_SIZE
sem_t full;  // 定义一个信号量，表示缓冲区的产品数量，初始值为0
pthread_mutex_t mutex;  // 定义一个互斥锁，用于保护对缓冲区的访问

void* producer(void* arg)
{
    for (int i = 0; i < 20; i++) {
        sem_wait(&empty);  // 如果缓冲区有空闲位置
        pthread_mutex_lock(&mutex);  // 获取互斥锁

        buffer[in] = i;  // 往缓冲区放入一个产品
        printf("生产者生产了 %d\n", i);
        in = (in + 1) % BUFFER_SIZE;  // 移动in指针到下一个空闲位置

        pthread_mutex_unlock(&mutex);  // 释放互斥锁
        sem_post(&full);  // 增加产品数量

        sleep(1);  // 模拟生产过程需要的时间
    }

    return NULL;
}

void* consumer(void* arg)
{
    for (int i = 0; i < 20; i++) {
        sem_wait(&full);  // 如果缓冲区有产品
        pthread_mutex_lock(&mutex);  // 获取互斥锁

        int item = buffer[out];  // 从缓冲区消费一个产品
        printf("消费者消费了 %d\n", item);
        out = (out + 1) % BUFFER_SIZE;  // 移动out指针到下一个产品

        pthread_mutex_unlock(&mutex);  // 释放互斥锁
        sem_post(&empty);  // 增加空闲位置数量

        sleep(1);  // 模拟消费过程需要的时间
    }

    return NULL;
}

int main()
{
    pthread_t t1, t2;  // 定义两个线程，一个生产者线程和一个消费者线程

    sem_init(&empty, 0, BUFFER_SIZE);  // 初始化empty信号量，初始值为BUFFER_SIZE
    sem_init(&full, 0, 0);  // 初始化full信号量，初始值为0
    pthread_mutex_init(&mutex, NULL);  // 初始化互斥锁

    pthread_create(&t1, NULL, producer, NULL);  // 创建生产者线程
    pthread_create(&t2, NULL, consumer, NULL);  // 创建消费者线程

    pthread_join(t1, NULL);  // 等待生产者线程结束
    pthread_join(t2, NULL);  // 等待消费者线程结束

    sem_destroy(&empty);  // 销毁empty信号量
    sem_destroy(&full);  // 销毁full信号量
    pthread_mutex_destroy(&mutex);  // 销毁互斥锁

    return 0;
}

七、信号量临界区保护

如果empty的语义有误，如生产者进程P(empty)访问empty为0但实际empty为-1（可能由调度导致，例如时间片到时导致进程切换），会认为仍有空闲位置而将产品放入缓冲区导致覆盖

empty = 2;
//生产者P1
register = empty;
register -= 1;
empty = register;

//生产者P2
register = empty;
register -= 1;
empty = register;
//此时empty预期为0

//实际调度执行可能为
P1.register = empty;
P1.register -= 1;
P2.register = empty;//发生切换
P2.register -= 1;
empty = P1.register;//发生切换
empty = P2.register;//发生切换
//此时empty为1

竞争条件(Race Condition)：多个线程同时进入临界区并都试图更新共享数据

解决办法：在写共享变量时阻止其他进程也访问该变量，给该变量上锁，修改完开锁

如何实现？

临界区：访问共享变量（资源）的代码片段，一定不能由多个线程同时执行
读写信号量的代码一定是临界区

临界区代码的保护原则：
1. 基本原则：互斥mutual exclusion（如果一个进程在临界区中执行时，其他进程不允许进入）
2. 有空让进：若干进程要求进入空闲临界区时，应尽快使一进程进入临界区（充分利用时间）
3. 有限等待：从进程发出进入请求到允许进入，不能无限等待（排队过久导致饥饿）
不让调度，可以关闭中断

cli();//关闭中断内嵌汇编
/*
临界区
*/
sti();//打开中断

但是在多CPU或多核上不适用：因为在一个CPU上关闭中断，另一个CPU仍可以并行访问和修改共享数据

硬件原子操作：不可被打断的操作集合，如同执行一条指令，要么执行了，要么没执行
1. 比较与置换
2. 拿取并累加
**锁：**用原子操作实现，只有两种状态，记录临界区状态（可用0或占用1）
1. 用lock()获取锁，unlock()解开锁
2. 不同的锁保护不同的数据
3. 需要将锁初始化为0
锁的实现：
1. 控制中断：
  1. 在临界区关闭中断，使得执行线程的时候不会被调度，执行完打开中断
  2. 一个程序可能调用lock独占cpu
  3. 在多CPU或多核上不适用：因为在一个CPU上关闭中断，另一个CPU仍可以运行线程进入临界区
2. 使用硬件原子指令的自旋锁
  1. x86：xchg指令，测试并设置指令

int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr; //将旧值取出
    *old = new;//将新值赋给旧值
    return old;//返回旧值
}

typedef struct lock_t {
    int flag;
}

void lock_init(lock_t *lock) {
    lock->flag = 0;//表示没有进程访问临界区
}

void Lock(lock_t *lock) {
    while(TestAndSet(&(lock->flag), 1) == 1)//如果自旋锁flag为1，说明有进程正在访问临界区
        ;//则进入空转自旋不断判断等待flag变为0
    lock->flag = 1;//执行到这步说明flag已经为0，此时再将其置为1，让该进程进入临界区
}

void unLock(lock_t *lock) {
    lock->flag = 0;//进程访问完临界区，将flag置为0，使其他进程可以进入临界区
}

  2. 在单cpu上需要抢占式调度，否则进入自旋无法退出
  3. 单cpu抢占调度，除了持锁的其他进程会自旋一个时间片，浪费cpu
  4. 不公平，有的进程会一直占用cpu，其他进程可能饿死
  5. 比较并交换指令（Compare And Swap）

int CompareAndSwap(int *ptr, int expect, int new) {
    //如果指向的值跟预期相等，则更新指向的值，否则直接返回原来的值
    if(*ptr == expect) {
        *ptr = new;
    }
    return *ptr;
}

void Lock(lock_t *lock) {
    while(CompareAndSwap(&(lock->flag), 0, 1) == 1)//如果自旋锁flag为1，说明有进程正在访问临界区
        ;//则进入空转自旋不断判断等待flag变为0
   //否则将flag置为1，让该进程进入临界区
}//此方法将TAS方法中设置flag包含到条件判断中

八、死锁处理

死锁：当线程 1 持有锁 L1，正在等待另外一个锁 L2，而线程 2 持有锁 L2，却在等待锁 L1 释放时，死锁就产生了
成因：
1. 互斥：线程对于需要的资源进行互斥的访问（例如一个线程抢到锁）
2. 持有并等待：线程持有了资源（例如已将持有的锁），同时又在等待其他资源（例如，需要获得的锁）
3. 非抢占：线程获得的资源（例如锁），不能被抢占
4. 循环等待：线程之间存在一个环路，环路上每个线程都额外持有一个资源，而这个资源又是下一个线程要申请的
处理方法：

四、内存管理

内存管理的主要功能
- 地址变换机制
- 寻址保护机制

一、内存使用

重定位：汇编程序在编写时，函数（一个地址标号）为一个相对地址（相对于程序在内存中开始的位置），而不是实际物理地址；在程序执行时，会被变成一个物理地址
什么时候完成重定位：
1. 对于不再变化的系统，如嵌入式系统，可以在编译时，也就是代码中直接访问物理地址；此时程序只能放在内存固定位置，运行更快
2. 灵活的系统，在程序从磁盘载入内存时；更慢但更灵活；但是交换时不一定会回到原来的地址，会导致出错
3. 运行时重定位：在程序运行时完成重定位，根据逻辑地址算出物理地址，地址翻译，进程的基址(base)放在pcb中

交换：进程a睡眠，操作系统会将其移动到磁盘上，将内存空出，供其他进程使用

程序载入执行过程：
1. 从磁盘中取出放入一块空闲内存
2. 创建进程PCB并把空闲内存基址存入PCB中
地址转化：将虚拟地址加上基地址转换为物理地址
基地址（进程起始地址）保存在基址寄存器中（BX）
界限（限制寄存器）：限制了虚拟内存访问范围
CPU中负责地址转换的部分称为内存管理单元（MMU）

二、分段

将进程地址空间放在固定大小的内存块中，容易造成已分配的内存单元中有未使用的部分（堆和栈之间），即内存碎片，造成浪费（内部碎片）

程序分为数据段（可写）、代码段（只读）、BSS段、堆、栈等
**分段概念：**给每个段一对基址和界限寄存器，可将不同的段独立放入不同的物理内存中，避免地址空间内未使用的部分占据物理内存
每个段都是从0开始，用户可以分别考虑每个段
因此，一个程序的不同段分别放入内存
寻址变为<段号，段内偏移>
进程段表（也就是每个进程自己的LDT）：记录以上各个段号、基地址、长度和保护，进程切换时ldt也切换
分段好处：
1. 避免地址空间逻辑段内潜在的内存浪费
2. 每个段都可以保护
3. 多个进程可以共享代码

三、分区

固定分区，将内存等分（不合适，程序大小不一）
可变分区：空闲分区表、已分配分区表
申请空闲分区：
1. 首先适配：直接选择空闲分区表第一项（快）
2. 最佳适配：选择分配完剩余空间最小的（会分割出很多细小空间）
3. 最差适配：选择分配完剩余空间最小的（会分割出很多大空间）

四、分页

分段问题：采用分段可能导致可用内存被分为很多小块（内存碎片），可能导致一个进程申请内存，总可用内存足够但没有一块足够的可用内存（外部碎片）

通过移动段来将空闲分区合并_（浪费时间）_
分页概念：
1. 将进程地址空间分为若干固定大小的单元(4k)，称为一页；
2. 将物理地址分成许多固定长度的页，每个页称为一个页帧；
3. 一个页4k，没使用为0，使用了为1，为请求的段分配页（向上取整），一个段最多浪费4k

页表：
1. 每个进程拥有的一个数据结构，保存从虚拟地址转换信息，从而知道每个页在物理内存中的位置
2. 页表中由页表项构成，通过虚拟页号找到对应页表项再找到物理页帧

从虚拟地址到物理地址：

虚拟地址由VPN（虚拟页号）和偏移组成页表的起始物理地址保存在页表基址寄存器中

由页表基址寄存器（x86架构为CR3 ）找到页表的位置
再用VPN找到页表中对应的PTE（页表项）
由PTE中的PFN（物理帧号）和偏移量（用来寻找页中字节）找到对应的物理地址
32位的虚拟地址前20位为页表中第n行的内容，它指向一个物理内存页，而后12位正好可以检索4k项，用于在该内存页中寻找到具体地址
问题：
1. 32位地址空间（4Gb），每页大小4k，则有个页，页表中有项，每项4字节，则一个页表4Mb大，也就是页表本身会占据很大的空间
2. 会进行两次访问内存，效率降低

五、TLB（地址转换缓存）

频繁通过页表进行地址转换因为要多次访问内存导致开销较大

TLB是一个硬件，其中保存了部分VPN到PFN的转换，访问速度比页表更快
1. 先从虚拟地址中提取VPN
2. 检查TLB中是否存在转换映射
3. 如果存在（命中），则取出PFN并和虚拟地址中的偏移量结合访问内存
4. 如果不存在，则通过页表寻找转换映射，并更新TLB

未命中可由硬件或软件进行处理

TLB中的有效位表示是否存在地址转换映射

页表项有效位表示该页是否使用了，未使用则不会被分配物理页帧

当发生上下文切换时，两个进程共用TLB会引发混乱，因此需要添加ASID（地址空间标识符）来区分不同进程的转换映射

六、多级页表

采用线性页表

会导致页表本身很大

地址空间中大量未使用的部分（无效）也要分配页表空间，页表会很大

基本思想：
1. 将页表本身分成多个页，再用一个新的页表——页目录（page directory）指向它
2. 页目录中每一项——页目录项（page directory entry）指向一个页表的页；PDE至少包含页帧号和有效位
3. 如果PDE有效，则说明该页表的页中至少存在一个PTE；否则不分配页给该部分页表**（从而减少页表大小）**
4. TLB未命中时，需要从访问内存两次，增加开销
5. 此时虚拟地址仍分为VPN和offset，但VPN分为页目录索引（PD-Index）和页表索引（PT-Index）
  1. 先检查TLB，如果能命中，则直接形成物理地址，否则执行下面过程
  2. 通过PD-Index找到PDE（如果PDE有效），从而找到对应的页表的页帧号，从而找到对应的页
  3. 再通过PT-Index找到该页中的PTE，通过PTE的物理页帧号和offset找到真实物理地址

超过两级：
1. 目标：让页目录放入一个页中
2. 方法：将页目录分成几个页存放，再用另一个页目录来指向该页目录

七、交换空间

物理内存大小不能满足多个进程的地址空间，需要使用硬盘来存放部分物理页

存在位：页表中的PTE有个存在位来表示所指向的物理页是否在物理内存中
页错误：访问不在物理内存中的页，会引发页错误，进而执行页错误处理程序；当物理页在硬盘中时（存在位为0），PTE中存储PFN的位置用来存储硬盘地址
页错误处理流程：当发生虚拟地址访问时
1. 先检查TLB是否命中，如果命中则直接得到物理地址
2. 如果未命中，则去查看页表PTE
  1. 若PTE无效，则报错
  2. 若PTE有效且不存在，则进行页错误处理：先查看物理内存中是否有空闲页，如果有则直接将磁盘中的页换入，否则释放物理内存中的某些页（将其换出）再将磁盘中的页换入

IO运行时进程处于阻塞态，cpu执行其他进程

  3. 若PTE存在且有效，则通过PFN和offset得到物理地址

八、换页策略

从物理内存中选择哪个页换出

基本原则：让缓存命中最多（从内存中找到目标页次数最多），缓存未命中最少（从硬盘中获取页的次数最少）

将物理内存看作虚拟内存页的缓存

访问内存和硬盘的时间成本相差六个数量级（固态硬盘三个数量级）

最优替换策略：
1. 知道未来的访问页列表，发生未命中时从内存中踢出最远会被访问的页
2. 无法实现，因为不能知道未来访问顺序
3. 是缓存命中率最高的策略
FIFO：发生未命中时从内存中踢出最先进入内存的页
随机：发生未命中时从内存中随机踢出一个页
LRU（Least Recent Used）：发生未命中时从内存中踢出最少使用的页

程序倾向于表现两种类型的局部：

空间局部性：如果一个页被访问，围绕它的页也会被访问

时间局部性：近期访问过的页不久也会被访问

寻找最少使用的页需要很长时间，因此使用近似LRU
脏页：设置脏位，用来表示页是否被修改，如果修改，将其踢出需重新写入磁盘，造成开销；如果未修改，可无成本直接踢出
其他内存策略：
1. 预取：操作系统猜测一个页即将使用而提前将其载入内存，例如一个代码页被载入内存，下一个代码页页应载入
2. 将多个踢出的页一并写入硬盘，因为硬盘驱动器的性质，执行单次大的写操作，比许多小的写操作更有效

九、其他设计

地址空间0页设置为无效，不可访问，以便检测空指针（null）
分段FIFO：
1. 每个进程在内存中有个最大的页数，超过页数，按FIFO踢出
2. 引入干净页空闲列表和脏页空闲列表
页聚集：将脏页列表一举写入硬盘中
按需置零：
1. 进程申请一页时，操作系统在页表中增加一项不可访问的条目
2. 当对该页读写时，操作系统寻找物理页并置零
3. 如果进程不访问该页，则不需完成b
写时复制（Copy-on-write）：
1. 需要将一个页面从一个地址空间复制到另一个地址空间时，不用实际复制内容，而是将内容映射到目标地址空间，并在两个地址空间标记只读
2. 如果一个地址空间尝试写入，则分配新页，创建副本

五、存储设备

一、设备

一个设备包含内部结构和外部接口，外部接口通常包含状态、命令、数据寄存器
与设备交互方法：
1. 通过特权指令
2. 内存映射，将设备寄存器作为内存地址，操作系统直接访问该地址
编程的IO（programmed IO）：主CPU参与数据移动过程（从设备到内存）
与设备交换过程：
1. 轮询：CPU通过死循环不断询问状态寄存器判断设备是否空闲或忙碌

轮询的问题：CPU空转效率低下

中断：当设备开始和完成操作时，将发出中断，使cpu进行进程切换

使用中断的问题：

每次只能读写一个字长内容，遇到长数据或多个数据要多次中断，中断过程开销大

非常高性能设备运行快，采用轮询更方便

DMA（Direct Memory Access）：一个硬件，操作系统告诉它内存的位置和拷贝的大小及设备，数据传输过程由它来完成而不是CPU，从而解放CPU；且传输单位为一个块，效率更高；任务完成后抛出中断

DMA问题：每次传输数据单位为一个块，如果遇到不连续的块，需要多次中断

二、磁盘

扇区：
1. 磁盘被分为许多的扇区，每个扇区是512字节块
2. 扇区从0编号，可视为地址
3. 访问连续的块速度比随机访问更快
物理属性：
1. 由许多个同心圆构成，称为磁道
2. 转一周大概6ms
3. 由磁臂控制磁头在表面上定位
4. 外圈有比内圈更多的扇区
缓存：
1. 8MB或16MB，可以保存读写磁盘的数据，提高磁盘响应，例如保存写入同一磁道的数据
2. 后写缓存（立即报告）：当数据写入缓存后就报告写入完成
3. 直写：数据写入磁盘报告写入完成
延迟：
1. 旋转延迟：在磁道内等待目标扇区转过来的时间
2. 寻道时间：跨越不同磁道的时间
3. 传输时间：信息传输的时间
IO时间：
2. IO速率：
3. 顺序使用磁盘或大块传输数据
磁盘调度：选择哪个扇区
1. 最短寻道时间：会导致寻道时间长的进程饿死
2. 电梯：按照跨越磁道的顺序
3. 最短定位时间：寻找到扇区时间最短
4. IO合并：将临近扇区的请求合并执行
5. 非工作保全：发出IO指令后磁盘不立即工作，而是等待一会看是否有更好的请求，从而提高效率

三、廉价冗余磁盘阵列（RAID）

需求：更快、更大、更可靠的磁盘系统
RAID：
1. 由多个磁盘、内存和处理器组成
2. 对主机系统就像一块大磁盘
故障-停止模型：
1. 处于工作状态或故障状态
2. 工作状态可读可写、故障状态内容丢失
3. 实际故障更复杂
评价指标：
1. 容量：N个硬盘客户端可用多少
2. 可靠性：允许多少硬盘故障
3. 性能（吞吐量）：顺序读写（内容是连续的）、随机读写（每个请求很小，并且是到磁盘随机位置）速度
4. 延迟：
RAID0：条带化

没有冗余（备份），性能和容量为上限
以轮转的方式将块分布在各个磁盘上，在进行顺序读写时有很好的并行性（N个盘一起读写）
块的大小不一定，当块比较小时文件会跨多个磁盘，增加对单个文件读写的并行性，但会增加定位时间；当块比较大时，跨越磁盘比较少，读写并行性降低，但也减少定位时间
性能：

N：磁盘数；S：顺序读取的数据传输速度；R：随机读取的数据传输速度 S大概是R的50倍

  1. 顺序读写：![](https://cdn.nlark.com/yuque/__latex/0d76ecc563389bc8457a2503e811c721.svg#card=math&code=N%2AS%20MB%2Fs&id=r5mnm)
  2. 随机读写：![](https://cdn.nlark.com/yuque/__latex/2da210807e2b29f6063c55dc77ac8134.svg#card=math&code=N%2AR%20MB%2Fs&id=rxIf9)

延迟：同单磁盘延迟相同
RAID1：镜像

每个块，保存两份副本到两个磁盘中，因此有一半的磁盘用来备份
容量：
可靠性：最多允许个磁盘故障（特定情况）
延迟：读跟单磁盘相近，写要向两个磁盘写，取决于延迟更高的那个，可能比单磁盘略高
性能：
1. 顺序读写：：每次写入要写重复内容，导致带宽只有峰值一半；因为一半磁盘存放副本内容，按顺序并行读取内容则需要多一倍时间，导致带宽只有峰值一半
2. 随机读：可以在所有盘上读取，
3. 随机写：每个块要写入两个磁盘中，带宽减半
RAID4：奇偶校验位

用一个磁盘作为奇偶校验盘，盘中的每一个位作为其他盘对应位的奇偶校验位
奇偶校验：
1. 通过将所有位异或运算得到奇偶校验位
2. 当有奇数个1时，奇偶校验位为1，当有偶数个1时，奇偶检验位为0
3. 因此，如果有一位丢失可以通过奇偶校验位反推出来，但最多允许一位丢失
容量：用一个磁盘做奇偶校验，容量为N-1
可靠性：最多允许一个磁盘故障
性能：
1. 顺序读取：奇偶校验盘不提供数据
2. 顺序写入：不向奇偶校验盘写真实数据
3. 随机读取：
4. 随机写入：
  1. 加法奇偶校验：新写入块和其他所有块进行异或得出新奇偶检验块的值
  2. 减法奇偶校验：若新写入的块和旧块某位内容相同，则新奇偶校验位不变，否则改变
  3. 采用减法奇偶校验，每次写入要执行两次读取和两次写入，因此带宽只有一半
延迟：
1. 单次读取等于单个磁盘
2. 单次写入等于两倍单个磁盘
RAID5：选择奇偶校验

不单独设置一个奇偶校验盘，而是在每个盘上都放奇偶校验块
容量：N-1
可靠性：最多一个盘故障
性能：
1. 顺序读写：
2. 随机读：
3. 随机写：，可以并行处理

六、文件系统

一、操作文件的api

inode：每个文件和目录都有的存储元数据的数据结构
open：int fd = open("foo", O_CREAT | O_WRONLY | O_TRUNC);
1. 打开文件的系统调用，返回文件描述符（指向文件的指针）
2. foo为文件名词，O_CREAT：如果文件不存在，就创建一个新文件，O_WRONLY：以只写方式打开文件O_TRUNC：如果文件已存在，并且以写入或者追加方式打开，则清空文件内容。
3. 失败返回-1
strace：跟踪程序所做的每个系统调用
read：ssize_t bytesRead = read(fd, buffer, sizeof(buffer) - 1);
1. 系统调用，读取文件中的某些字节并存储到某块区域
2. 返回从文件中实际读取的字节数，达到文件末尾返回0，出错返回-1
write：ssize_t bytesWritten = write(fd, message, strlen(message));
1. 系统调用，向文件中写入存放在某块区域的某些字节
2. 返回从文件中实际读取的字节数，出错返回-1
close：close(fd);
1. 关闭一个打开文件描述符的系统调用
2. 成功返回0，并且不能再对该文件操作，错误返回-1
3. 再次open相同文件，文件指针从头开始
lseek：off_t newOffset = lseek(fd, 0, SEEK_SET);
1. 一个文件open以后，close之前，读写操作会改变文件指针，即下一次读写操作文件内容开始的位置
2. 通过lseek可重新定位文件指针位置
3. 成功返回文件开头到当前指针位置的字节偏移量，失败返回-1
5. SEEK_SET：将文件指针设置为距文件开头偏移量（第二个参数）个字节的位置。如果偏移量设置为0，那么文件指针将会被设置到文件的开头。
6. SEEK_CUR：将文件指针设置为当前位置加上偏移量（第二个参数）个字节的位置。如果偏移量设置为0，那么文件指针的位置不会改变。
7. SEEK_END：将文件指针设置为距文件末尾偏移量（第二个参数）个字节的位置。如果偏移量设置为0，那么文件指针将会被设置到文件的末尾。
fsync：fsync(fd);
1. 调用write，文件系统会将内容在内存中缓冲一段时间以提高性能，稍后再放入存储设备

每次都直接IO将会经常阻塞该进程

fsync强制将所有未写入数据写入硬盘
rename：rename("oldname.txt", "newname.txt");
1. 重命名的系统调用
2. 成功返回0，失败返回-1
stat命令：可查看文件详细信息
ln命令（硬链接）：创建一个新文件名和旧文件名指向同一文件的inode，不能创建目录的硬链接
rm：删除命令
调用unlink系统调用
删除当前文件名和该文件inode的链接并减少引用计数，当引用计数为0则真正删除

inode通过引用计数记录有多少文件名与自己链接

rm -rf /*：强制、递归（即目录及内部内容）删除根目录下所有文件

ln -s：符号链接（软链接）：
创建的新文件跟旧文件不是同一类型
可以链接到目录
删掉旧文件，则会变成悬空引用
mkfs：为一个硬盘分区创建一个文件系统
mount命令：
挂载文件系统，将一个文件系统挂载到一个指定路径
可以将所有文件系统挂载到同一棵树上

二、文件系统实现

思考方式：
1. 数据结构是怎样的
2. open、read、write等系统调用发生了什么
文件系统下的磁盘：
1. 最小单位为块4KB（磁盘本身最小为扇区512字节）
2. 包含数据区域、inode表、位图和超级块
3. 数据区域：存储数据
4. inode表：存储inode的表
5. 位图：每个位指示相应对象空闲（0）/使用（1）
  1. 数据位图
  2. inode位图
6. 超级块：
  1. 文件系统的信息，如有多少inode和数据块、inode表的位置
  2. 挂载文件系统时，操作系统首先读取超级块，初始化参数
inode：
1. 保存元数据（文件本身的信息）的数据结构
2. 一个文件和一个inode对应
3. 每个inode有自己的号
4. 包括文件大小、类型、块数、权限、时间、块的位置
inode如何访问数据块：
1. 在inode中放磁盘地址（直接指针），但可存放地址有限导致文件大小受限
2. 间接指针：inode中存放一个指针，这个指针指向存放直接指针的块
3. 双重间接指针：inode中存放一个指针，这个指针指向存放间接指针的块，每个间接指针又指向存放直接指针的块
4. 基于范围：一个指针加一个长度，不够灵活但比较紧凑
5. 实际inode用少量直接指针（访问小文件）和许多间接指针
6. 基于链接：inode中不用多个指针，而用链表将数据块串起来，在内存中维护一个链接信息表，其中保存数据块后面文件的下一块地址，可通过查表访问磁盘上的块
目录：
1. 特殊类型的文件，有自己的inode
2. 数据块中存放着目录内文件及目录的名称和inode号
访问路径读取：例如打开/foo/bar，open("/foo/bar",O_RDONLY);
1. 文件系统先读取根目录的inode（2），再找到数据块，从数据块中找到foo的inode号
2. 读取foo的inode，找到foo的数据块，从数据块中找到bar的inode号
3. 将bar的inode读入内存，文件系统检查权限，分配文件描述符返回用户
4. 每次执行read都会读取并更新inode
5. open导致的io量和路径名长度成正比；大型目录需要读多个数据块
访问路径写入文件：write
1. 读取数据位图，找到空位
2. 写入数据位图
3. 读取inode
4. 写入inode
5. 将内容写入数据块
访问路径创建文件：例如创建/foo/bar
1. 读取根目录的inode，找到数据块，从数据块中找到foo的inode
2. 从foo的inode中找到并读取数据块
3. 读取inode位图找到空位，写入位图
4. 向foo的数据块中增加新内容
5. 读取新inode，写入新inode
6. 更新foo的inode

上面读写文件产生大量IO，影响性能

缓冲区缓存：
1. 像TLB一样，保存常用块
2. 读取的时候可能命缓存
3. 写入的时候：可以延迟写入，将多次写操作用一次IO放入硬盘中；如果创建文件并删除，可以避免一次写入
4. 将写入在内存缓冲5~30s
5. 立刻写入速度慢但安全，延迟写入速度快但有丢失的风险

三、快速文件系统（FFS）

将内容随机存放的到磁盘，导致数据遍布各处，访问大文件要较大的寻道时间开销

原始块太小，访问效率低

对磁盘处理：FFS将磁盘划分为一些分组，称为柱面组或块组，在每个组中分配文件或目录

分配目录：将新目录放置在已有目录较少、空闲inode较多的柱面组中
分配文件：
1. 一般情况下，确保文件数据块和inode分配到相同组中，防止由inode到数据块的长时间寻道
2. 将同一目录下的文件放在目录所在的组中

目录中的文件通常一起访问

大文件例外：
1. 对于大文件，将一定数量的块放入第一个块组，再将一定数量的块放入下一个块组

在不同块组中寻找块损害性能，将块设计足够大，大部分时间就会用来传输数据，寻道时间相对减少，从而减少开销
对于FFS，前12个直接块跟inode在同一分组中，后续间接块和它们指向的数据块在不同分组中
对于小文件：
1. 块过大的话会造成内部碎片
2. 引入子块（512字节），写入小文件不会浪费整个块
3. 写小块会造成大量IO，需要缓冲写入
优化磁盘布局：
1. 当访问连续内容时，访问完0再要访问1，该位置已经转走
2. 但是会降低读取性能
3. 将磁道读取到磁盘缓冲中，再读取则从缓冲中读取

四、崩溃一致性

问题：对文件添加内容时，需要修改文件的inode，数据位图以及数据块，在对三者写入过程中发生崩溃（掉电或系统崩溃）导致有的部分没有写入则会出现一致性问题，例如没有写入数据块，导致inode指向旧的数据；inode和位图冲突等
FSCK（文件系统检查程序）：基于某些约定对整个磁盘进行检查修复，但是速度非常慢
数据日志：
1. 日志：磁盘中的某个部分，在日志中写入将要做的事情（事务，包括事务开始块——含有这次更新的内容，数据、元数据和事务结束块——标志着事务结束）

写入日志时崩溃：将事务块批量写入磁盘中，由于磁盘会调度，导致写入顺序不定（但在磁盘内的位置固定）；此时发生崩溃，进而导致部分块未能写入从而出现问题

屏障：再两次写入中通过增加写入屏障可强制按顺序写入，代价是速度较慢

避免该问题，将分成两步发出事务写入，下面为协议
1. 日志写入：将除了TxE以外所有块（TxB、元数据和数据块）写入日志
2. 日志提交：等上一步完成后，写入TxE块写入日志**（标志着日志写入）**
3. 加检查点：将数据和元数据写入磁盘
恢复：
1. 若在第二步之前发生崩溃，则认为日志没有写入，若在第二步发生之后发生崩溃，则认为日志写入完成
2. 日志写入后发生崩溃，则可以从日志恢复
批处理日志更新：可将对同一块的多次访问合并，从而降低开销
日志有限：
1. 日志大小有限
2. 在基本协议追加一条：通过更新超级块将空闲事务释放

元数据日志：
1. 每次写入要向磁盘写入两次
2. 元数据日志不将数据写入日志从而避免额外写入

协议为：
1. 数据写入
2. 日志元数据写入
3. 日志提交
4. 加检查点元数据
5. 释放
不要求开始二前完成一，但三开始前一二一定要完成
块复用问题：
1. 写入一个目录后再删除（目录的数据被视为元数据），在原来的位置再创建新的文件；在将新文件写入磁盘后发生崩溃后，恢复过程将会用目录的数据块覆写新文件的数据
2. 解决方法：删除文件将添加撤销记录，恢复时不会将撤销文件重写

Files

笔记.md

Latest commit

History