smart-os/计算机运作原理.md

# 概述
下述资料，大部分都是采摘于网上对应的博客，感觉内容不错，简单做了一下归纳，感谢大拿们的精彩分享！
有些流程是重复描述的，我没有调整，多读几次加深印象!

# 启动
启动可以分为两种，一种为冷启动，是指计算机在关机状态下按 POWER 键启动，又叫硬件启动，比如开机，这种启动方式在启动之前计算机处于断电状态，像内存这种需要加电维持的存储部件里面的内容都丢失了，加电开机那一刻里面的值都是随机的，操作系统会对其进行初始化。

而热启动是在加电的情况下启动，又叫软件启动，比如重启，这种启动方式在启动之前和启动之后电没断过，内存等存储部件里面的值不会改变，但毕竟是启动过程，操作系统会对其进行初始化

不论是哪种启动，都会向 CPU 发送启动的信号，然后开始启动。同第一篇文章，我们分五个大的步骤讲述启动，BIOS -> MBR -> Bootloader -> OS -> Multiprocessor

系统 BIOS 所在的 ROM 是被设计成 CPU 可直接寻址的，而且地址范围也是固定的，从 0xF0000H 至 0xFFFFFH 共 64 KB。PC 按通电源后，电源设备开始向主板和其他设备供电，此时电压还不太稳定，主板上的控制芯片组会向 CPU 发出并保持一个 RESET（重置）信号，让 CPU 内部自动恢复到初始状态，但 CPU 在此刻不会马上执行指令。当芯片组检测到电源已经开始稳定供电了（当然从不稳定到稳定的过程只是一瞬间的事情），它便撤去 RESET 信号（如果是手工按下计算机面板上的 Reset 按钮来重启机器，那么松开该按钮时芯片组就会撤去 RESET 信号）CPU 进行重置，IP 寄存器的值设成 0，CS寄存器的值设成 0xFFFF。也就是说 CPU 马上从地址 0xFFFF0H 处开始执行指令，这个地址在系统 BIOS 空间的地址范围内，CPU 就是从这个固定的地址开始执行 BIOS 程序的。

各厂家的 BIOS 程序不尽相同，但基本都是完成 POST 自检及本地设备的枚举和初始化，包括对硬件执行一系列的测试，用来检测现在都有什么设备以及这些设备是否能正常工作，在这个阶段中，会显示一些信息，例如 BIOS 版本号等；初始化硬件设备，这个阶段在现代基于 PCI 的体系结构中相当重要，因为它可以保证所有的硬件设备操作不会引起 IRQ 线与 I/O 端口的冲突，在本阶段的最后，会显示系统中所安装的所有 PCI 设备的一个列表等。

BIOS 自检和初始化完成后，开始执行 BIOS 引导程序。由于系统 BIOS 空间只有 64KB 大小，把 Linux 内核放在这个空间里让 BIOS 引导程序直接引导是不可能的，只能把内核放在硬盘里（或其他设备，如 USB 或网络上， BIOS 根据启动顺序的设置依次查找），然后再从硬盘里引导 Linux 内核。但是，这时系统还处于实模式中，寻址能力只有 1MB，没有硬盘上的文件系统等信息，不会直接的引导整个 Linux 内核，而是通过先载入一个引导装入程序，然后由这个引导装入程序来引导 Linux 内核。

引导装入程序通常放在第一块硬盘（或其他设备）的第一个扇区里，这个扇区就是主引导扇区，包括硬盘主引导记录 MBR（Master Boot Record）、分区表DPT（Disk Partition Table）及主引导扇区标志 “55AA”，共 512 个字节。系统 BIOS 引导程序的唯一任务就是把存放在 MBR 中的引导装入程序载入内存的 0x7C00 位置（可以通过 BIOS 中断方式 INT 13h 读取磁盘指定扇区的内容），然后 CPU 跳转到这个地址，把控制权交给引导装入程序继续引导系统。GRUB（GRand Unified Bootloader）就是这样的一个引导程序。

# BIOS
启动的瞬间会将寄存器 CS 和 IP 初始化：CS = 0xf000, IP = 0xfff0。

刚启动的时候正处于实模式，实模式下地址总线只用了 20 位，只有  2^20 = 1M 的寻址空间，也就是只用到的内存的低 1M ，这个时候分页机制还没有建立起来，CPU 运行时的地址都是实际的物理地址。

但实模式下寄存器只用到了 16 位寄存器，如何使用寄存器来寻址 20 位的地址空间？Intel 采用分段的机制来访问内存，也就是采用 段基址 ：段偏移，
"地址 = 段基址 + 偏移量"的方式来访问，但是实模式下的寄存器只能使用 16 位，所以规定实模式下 "地址 = 段基址 X 16 + 偏移量" 。
因此根据 CS = 0xf000, IP = 0xfff0，得到的 address = 0xf000 << 4 + 0xfff0 = 0xffff0 。

这个地址是啥？ 来看内存低 1M 的内存布局：

| 起始 | 结束 | 大小 | 用途 |
| --- | --- | --- | --- |
| FFFF0 | FFFFF | 16B | BIOS 入口地址，此地址也属于 BIOS 代码，同样属于顶部的 640 KB 字节，只是为了强调 其入口地址才单独贴出来。此处 16 字节的内容时跳转指令 jmp f000:e05b |
| F0000 | FFFEF | 64KB-16B | 系统 BIOS 范围是 F0000~FFFFF 共 640KB，为了说明入口地址，将最上面的 16 字节从此处去掉了，所以此处的终止地址是 0xFFFEF |
| C8000 | EFFFF | 160KB | 映射硬件适配器的 ROM 或内存映射模式 I/O |
| C0000 | C7FFF | 32KB | 显示适配器 BIOS |
| B8000 | BFFFF | 32KB | 用于文本模式显示适配器 |
| B0000 | B7FFF | 32KB | 用于黑白显示适配器 |
| A0000 | AFFFF | 64KB | 用于彩色显示适配器 |
| 9FC00 | 9FFFF | 1KB | EBDA (Extended BIOS Data Area) 扩展 BIOS 数据区 |
| 7E00  | 9FBFF | 622080B 约 608KB | 可用区域 |
| 7C00  | 7DFF  | 512B | MBR 被 BIOS 加载到此处，共 512 字节 |
| 500   | 7BFF  | 30464B 约 30KB | 可用区域 |
| 400   | 4FF   | 256B | BIOS Data Area( BIOS 数据区 ) |
| 000   | 3FF   | 1KB | Interrupt Vector Table ( 中断向量表 ) |
 
看最上面两行，可以知道 0xffff0 地址上存放的是一个跳转指令，CPU 执行这个命令然后跳转到 BIOS 代码的主体部分，BIOS 主要做一下几件事：

* 自检，然后对一些硬件设备做简单的初始化
* 构建中断向量表加载中断服务程序
* 将硬盘(通常引导设备就是硬盘)最开始那个扇区 MBR 加载到 

# MBR
关于 MBR(Master Boot Record)，我在捋一捋磁盘及分区一文讲的比较详细了，这里不赘述，简单再说一下 MBR 的结构：

1. 引导程序和一些参数，446 字节
2. 分区表 DPT，64字节
3. 结尾标记签名，0x55 和 0xaa，两字节
   
MBR 的代码在分区表中寻找可以引导存在操作系统的分区，也就是寻找标记为 0x80 的活动分区，然后加载该活动分区的引导块，再执行其中的操作系统引导程序 Bootloader。

# Bootloader
Bootloader，操作系统引导程序，操作系统加载器，不论怎么叫，它的主要作用就是将操作系统加载到内存里面。操作系统也是一个程序，需要加载到内存里面才能运行。平常正在运行的计算机我们可以使用 exec 族函数来加载运行一个程序，同样的要加载运行操作系统这个程序就使用 Bootloader。

在 Bootloader 里面还做了一些其他事情，比如进入保护模式，开启分页机制，建立内存的映射等等。像 GRUB，U-Boot 等都属于 Bootloader，只是功能更多更强大。

# GRUB引导过程

GRUB（GRand Unified Bootloader）是一个多重启动管理器。它可以在多个操作系统共存时选择启动哪个系统，可以启动的操作系统包括Linux, FreeBSD, Solaris, NetBSD, BeOS, OS/2, Windows 95/98 /NT /2000。它可以载入操作系统的内核和初始化操作系统（如Linux, FreeBSD），或者把启动权交给操作系统（如Windows 98）来完成启动。

GRUB 的实质是一个 mini os，它拥有 shell，支持 script，支持特定文件系统等。GRUB 由 stage1，stage1_5，stage2 以及 /boot/grub 目录下的诸多文件（包括Grub的配置文件与相关文件系统定义文件等）组成。

stage1 被编译成了一个 512 字节的 img，写在硬盘的 0 面 0 道第 1 扇，它所做的唯一的事情就是装载第二引导装载程序 stage2。

stage1_5 写进了 MBR 后的 15 个扇区中（因为 e2fs_stage1_5 大小为 7.5k)。硬盘上第一个文件系统分区的开始扇区最小也只能从 0 柱面，1 磁头，1 扇区开始。就是说 MBR 所在 0 磁头就只用到了 1 个扇区而已（其它扇区都是未用的，不属于任何分区），按照现在硬盘的规格来说，一般一个柱面磁头都有 60+ 个扇区，所有将 stage1_5 写进 MBR 以后的扇区中，不会影响正常的文件系统分区。stage1_5 就是文件系统的解释代码，根据 /boot分区（或/boot所在分区）的具体文件系统类型而异，如：ext3 分区的话就是 e2fs_stage1_5。在 stage1_5 没有被加载以前，系统无法识别任何文件系统（但是可以通过 BIOS 中断方式 INT 13h 读取磁盘指定扇区的内容）, 加载 stage1_5 以后就可以识别 /boot所在分区的文件系统了，从而为加载 stage2 作好了准备。

stage2 是 grub 最核心的部分有 100 多KB，所以只能放在文件系统中，放在 /boot 分区里，放在这里的通常还有 Linux 内核映像文件。加载 stage2 后 grub 会根据 menulist 或用户输入加载 Linux 内核映像文件，即将内核映像装入地址 0x90000 的内存中，将内核入口装入到地址 0x90200 的内存中，然后跳转到内核入口处开始启动内核。

# OS
操作系统内核加载到内存之后，就做一些初始化工作建立好工作环境，比如各个硬件的初始化，重新设置 GDT，IDT 等等初始的操作。初始化启动其他处理器(如果有多个处理器的话)。这里不细说，也不好叙述，等下面直接看实例 xv6 做了哪些事，怎么做的。

# Multiprocessor
上述的启动过程是单处理情况下的启动过程，多处理器的情况下有些不同，用一句话先来简单概括多处理器情况下的启动：先启动一个 CPU，用它作为基础启动其他的处理器。

先启动的这个 CPU 称作 BSP(BootStrap Processor)，其他处理器叫做 AP(Application Processor)。BSP 是由系统硬件或者 BIOS 动态选择决定的。

多处理器启动过程大致分为以下几个大步骤：

1. BIOS 启动 BSP，流程与上述讲的 BIOS-MBR-bootloader-OS 差不多
2. BSP 从 MP Configuration Table 中获取多处理器的的配置信息
3. BSP 启动 APs，通过发送 INIT-SIPI-SIPI 消息给 APs
4. APs 启动，各个 APs 处理器要像 BSP 一样建立自己的一些机制，比如保护模式，分页，中断等等
   
这里我们主要关注第二点，获取多处理器的配置信息

# BSP启动详解

1. 在 BIOS POST 阶段，BSP 创建了 ACPI 表并添加它的 initial APIC ID。
2. 进到 OS 后，内核最开始的代码还是由 BSP 执行，初始化后进入正式的 SMP Boot 流程。
3. 在 BSP 执行后，将 processor 设置为 CPU 0 并广播一条 SIPI 消息给其他 AP，SIPI 消息包含了 BIOS AP 初始化的代码地址。
4. 第一个获得 SIPI 消息的 AP 获取 BIOS 初始化信号量，执行初始化代码，添加 APIC ID 并将 processor 加1，初始化结束后，AP 执行 CLI (Clear Interrupt Flag) 指令并 halt 自己。
5. 所有的 AP 都执行完初始化后，BSP 通过系统总线获取 processors 数量后，开始执行 OS boot-strap code、start-up code。AP 现在只能对 INITs, NMIs, and SMIs 响应，当然也响应 STPCLK# 引脚的 snoops、assertions

用一句话来概括多处理器情况下的启动：先启动一个 CPU，再以它为基础启动其他的处理器。

先启动的这个 CPU 称作 BSP(BootStrap Processor)，其他处理器叫做 AP(Application Processor)。硬件会动态选择系统总线上的一个 processor 作为 BSP，其余的为 AP。在计算机上电或者重置系统时，每个 CPU 都先执行处理器自检（BIST），自检通过的CPU就拥有了称为 BSP 的资格，那么此时选谁呢？

选择的方式为上电后所有的 CPU 都执行 NOP 指令，看看哪个 CPU 先发送了 NOP，就会成为 BSP，BSP 选出来之后，它会将 IA32_APIC_BASE MSR 里面的 BSP flag 设置为1，标识该处理器是 BSP，其他的APs进入 wait for SIPI 的状态，等待 BSP 的发号施令。

在 BIOS 中，BSP 首先要收集所有的 AP 信息，将所有 AP 信息登记下来，这个登记表称为 MP Configuration Table，它首先把自己加进去（CPU 0），然后让 APs 自己在登记表上登记。Processors 之间传递消息靠的是一种叫 Inter-Processor Interrupt（IPI）的机制，而通知登记在它们的语言里就是 SIPI(Start-up IPI )，当然 SIPI 只能由 BSP 来说才管用。

通常BSP的初始化顺序为：

1. 初始化内存。
2. 加载microcode
3. 初始化MTRRs
4. 初始化Cache
5. 加载 AP start-up code 到 1Mbyte 以下的 4K 内存中。
6. Enable APIC (SVR bit8）
7. Program ICR寄存器，把AP start-up code地址写到该寄存器
8. 在AP start-up code里,每个AP将会增加一个COUNT变量表示AP已经起来了
9. 广播INIT-SIPI-SIPI IPI sequence to the Aps,这时所有的AP才会真正被唤醒起来执行

https://zhuanlan.zhihu.com/p/598552628  
https://peterhu.github.io/posts/2020/08/19/CPU%E5%A4%9A%E6%A0%B8%E5%88%9D%E5%A7%8B%E5%8C%96.html  

# UP
UP（Uni-Processor）：系统只有一个处理器单元，即单核CPU系统。

# SMP
对称多处理器结构 , 英文名称为 " Symmetrical Multi-Processing " , 简称 SMP 。  
SMP 又称为 UMA , 全称 " Uniform Memory Access " , 中文名称 " 统一内存访问架构 " 。  
在 " 对称多处理器结构 " 的 系统中 , 所有的处理器单元的地位都是平等的 , 一般指的是服务器设备上 , 运行的 多个 CPU , 没有 主次/从属 关系，都是平等的。  
这些处理器 共享 所有的设备资源 , 所有的资源对处理器单元具有相同的可访问性 , 如 : 磁盘 , 内存 , 总线等 ，多个CPU处理器共享相同的物理内存 , 每个 CPU 访问相同的物理地址 , 所消耗的时间是相同的 ;  
要注意，这里提到的“处理器单元”是指“logic CPU”，而不是“physical CPU”。举个例子，如果一个“physical CPU”包含2个core，并且一个core包含2个hardware thread。则一个“处理器单元”就是一个hardware thread。

# 内核针对多处理器 CPU 下的调度
BIOS 调入执行启动引导区程序后，这段程序录入 Linux 操作系统的启动部分，解压缩 Linux 内核核心映像，然后转入 start_kernel 函数开始执行。在这以前，系统没有对 AP 做任何处理。在 start_kernel 函数中，主要处理例如 cache、内存等初始化工作，最后要调用 smp_init 函数，在这个函数里，具体实现 SMP 系统各 CPU 的初始处理机制, 我们来分析 smp_init 函数  
在 [linux/init/main.c] 中  

~~~c
static void __init smp_init(void)
{
    smp_boot_cpus();
    smp_threads_ready=1;
    smp_commence();
}
~~~

在函数 smp_boot_cpus 中，要建立并初始化各 AP，关键代码如下：  
在 [linux/arch/i386/kernel/smpboot.c] 中  
~~~C
void __init smp_boot_cpus(void)
{
    ……
    for (apicid = 0; apicid < NR_CPUS; apicid++) {
        if (apicid == boot_cpu_id) 
            continue; // 是BP，因为上面已经初始化完毕，就不再需要初始化
        
        if (!(phys_cpu_present_map & (1 << apicid)))
            continue; // 如果CPU不存在，不需要初始化
            
        if ((max_cpus >= 0) && (max_cpus <= cpucount+1)) 
            continue; //如果超过最大支持范围，不需要初始化
        
        do_boot_cpu(apicid);// 对每个AP调用do_boot_cpu函数
        ……
    }
    ……
}
~~~

下面我们看一下do_boot_cpu中做了什么工作：  
在[linux/arch/i386/kernel/smpboot.c]中
~~~c
static void __init do_boot_cpu (int apicid)
{
    struct task_struct *idle; // 空闲进程结构
    ……
    if (fork_by_hand() < 0) //在每个cpu上建立0号进程，这些进程共享内存
        ……
        idle->thread.eip = (unsigned long) start_secondary;
        // 将空闲进程结构的eip设置为 start_secondary 函数的入口处
        ……
        start_eip = setup_trampoline(); // 得到trampoline.S代码的入口地址
        stack_start.esp = (void *) (1024 + PAGE_SIZE + (char *)idle);
        ……
        *((volatile unsigned short *) phys_to_virt(0x469)) = start_eip >> 4;
        Dprintk("2.\n");
        *((volatile unsigned short *) phys_to_virt(0x467)) = start_eip & 0xf;
        Dprintk("3.\n");
        // 将trampoline.S的入口地址写入热启动的中断向量(warm reset vector)40:67
        ……
        apic_write_around(APIC_ICR2, SET_APIC_DEST_FIELD(apicid));
        // 确定发送对象
        apic_write_around(APIC_ICR, APIC_INT_LEVELTRIG | APIC_DM_INIT); 
        // 发送INIT IPI
        ……
        apic_write_around(APIC_ICR2, SET_APIC_DEST_FIELD(apicid));
        //确定发送对象
        apic_write_around(APIC_ICR, APIC_DM_STARTUP | (start_eip >> 12));
        //发送STARTUP IPI
        ……
}
~~~

现在对上面初始设置做如下概括 [1]：
BSP 将 AP 在一开始被唤醒后需要执行的代码（trampoline.S）的首地址写入热启动向量（warm reset vector
），即从40:67开始的两个字。这样，当 BSP 对 AP 发送 IPI 时，AP 响应中断，自动跳入这个 trampoline.S 代码
部分继续执行。为了 AP 有足够的时间响应中断，BSP 在发送中断请求后要延迟一段时间，。
在这以后，事实上 AP 已经在工作了，我们跟随 AP，看它在做什么。AP 响应中断直接跳转至 trampoline.S 的
入口处，trampoline.S 在载入符号表 (gdt) 和局部符号表 (ldt) 之后进入保护模式并跳至 head.S 的入口处：  
在 [linux/arch/i386/kernel/trampoline.S] 中  
~~~C
    ……
    inc %ax #protected mode (PE) bit
    lmsw %ax # 进入保护模式
    jmp flush_instr
    flush_instr:
    ljmpl $__KERNEL_CS, $0x00100000
    # 一个长跳转，0x10:0x00100000是内核被解压后的起始地址，即 head.S 的 startup_32[7]
    ……
~~~

AP 转入 head.S 继续执行，但是执行的代码与 BSP 所执行的并不完全一致：  
在 [linux/arch/i386/kernel/head.S] 中  
~~~C
    ENTRY(stext)
    ENTRY(_stext)
startup_32:
    ……
    incb  ready # 该段代码每执行一次，ready 值加 1，BSP 执行时 ready 的值从 0 变为 1
    ……
    movb ready, %cl
    cmpb $1,%cl
    je 1f # 当执行 CPU 为 BSP 时，ready 的值为 1
    call SYMBOL_NAME(initialize_secondary) # 执行 initialize_secondary 函数
    jmp L6
1:
    call SYMBOL_NAME(start_kernel) # 执行 start_kernel() 函数
L6:
    jmp L6
ready: .byte 0 # ready 为字节变量，初始值为 0
~~~

AP 执行 head.S 的过程是当执行到上述代码的时候，由于 ready 的值被改变，不再等于 1，所以就继续向前执行
，调用 initialize_secondary 函数，而不是像 BSP 一样执行标号 1 处的代码（调用start_kernel函数）。
initialize_secondary 函数里面的代码很简单：  
在 [linux/arch/i386/kernel/smpboot.c] 中  
~~~c
void __init initialize_secondary(void)
{
    asm volatile(
        "movl %0,%%esp\n\t"
        "jmp *%1"
        :
        :"r" (current->thread.esp),"r" (current->thread.eip));
}
~~~

这是一段内嵌汇编程序，将程序跳转至 current->thread.esp（即前面的idle->thread.esp）处 [8]。CPU执
行 start_secondary 函数，进入空闲状态。  
在 [linux/arch/i386/kernel/smpboot.c] 中  
~~~c
int __init start_secondary(void *unused)
{
    cpu_init();
    smp_callin();
    while (!atomic_read(&smp_commenced))
        rep_nop();
    local_flush_tlb();
    return cpu_idle(); // 进入空闲进程
}
~~~

至此，一个 AP 的初始化过程就完成了。

总结
下面简要的再把Linux的SMP启动过程做一总结。
在 SMP 中，首先要对各个处理器进行初始化。然后 BSP 工作，而其它的 CPU（AP）则停留在一个初始化好的
中断屏蔽状态休眠。BSP 继续进行启动过程，在执行到操作系统的 start_kernel 之前，BSP 所进行的工作与单
处理器系统所做的工作是相同的。在 start_kernel 中，BSP 通过 smp_init 对每个 AP 进行初始化。初始化的
方式是通过 APIC 发送 IPI。当 BSP 初始化完毕所有的 AP 之后，就继续执行 start_kernel 中的其余部分代码。
而 AP 在接收到 IPI 之后，跳转到事先设置好的地址处执行 trampoline.S 和 head.S。在执行 head.S 的过程中
直接跳入事先创建好的空闲进程，进入空闲状态，等待以后的系统调度。

内核调度
在 [kernel/sched.c] 中, 内核为每一颗 CPU 分配了一个 runqueue ，我们的线程驱动就是每个 CPU 调用此队列的任务进行执行驱动

# 内核是怎么知道各个硬件的信息的？
答案就是通过 SMBios 表，此表由 UEFI 或者 Legacy BIOS 提供的, 从 SMBIOS 的 spec 中可以看到，对于基于 Legacy BIOS 的系统而言，系统软件可以通过在物理内存范围 000F0000h ～ 000FFFFFh 内搜索制定的字符串来定位到 SMBIOS 表的入口点。对于SMBIOS 2.1 而言，这个字符串是 "_SM_"，对于 SMBIOS 3.0 而言，这个字符串为 "_SM3_"。

而对于基于 UEFI 的系统而言，EFI configuration table (EFI_CONFIGURATION_TABLE) 包含了指向 SMBIOS table 的指针。


每个硬件方法不同。比如说内存，内存条上有一个 smbus 总线的 eeprom，记录内存条的信息。usb 总线的总线协议就规定了设备类型，如存储设备，输入设备等。pcie 总线有 vendor id, device id. 板上一些无法通过枚举过程识别的，可能会硬编码在 BIOS 里，因为每个主板都要研发一次 BIOS。BIOS 和内核传递信息有多种标准。acpi, device tree 之类的。有些设备内核还会自己枚举，不用 BIOS 告诉他。


# 内核线程的实现
https://segmentfault.com/a/1190000040253849

# 锁的实现
特别注意锁的悬停 ( mutex 的实现原理 )
所有的锁的机制都是类似于“自旋锁”的机制，mutex 也不例外，当然会阻塞，是因为加锁失败，会把当前线程加入等待队列，把当前线程加入等待队列，等待下一轮的锁的抢占，抢占到锁，线程继续执行，否则还得继续等待，而对应的 CPU 线程，可没闲着继续驱动内核线程执行，对于用户层来说，仿佛多个线程在不停的执行。
https://segmentfault.com/a/1190000040360086