说明

本文基于Linux Kernel早期版本（v0.12）介绍操作系统的工作原理

原理

启动

早期操作系统很小，可存储在软盘里面。内容大致分为三块：引导扇区（bootsect）、初始化程序(setup)、系统(system)。

引导扇区： 512B，软盘第一个扇区，以0x55, 0xAA结尾

1. 插入操作系统软盘、PC上电、ROM BIOS自检，BIOS将引导扇区加载到内存地址0x7c00开始处并执行
2. bootsect将setup和system全部读入内存，然后跳转到setup
3. setup获取必须的硬件信息，切换到保护模式，再跳转到system
4. system初始化各模块后运行shell，等待用户输入…

保护模式

实地址模式(Real Address Mode)

Intel 8086 CPU

• 地址总线=20位，可寻址空间为1M
• 数据总线=16位，可处理16位或8位的数据

因为寄存器都是16位，因此(20位)物理地址 = （16位）段地址<<4 + （16位）偏移

保护模式(Protected Mode)

Intel 80x86 CPU

• 地址总线=32位，可寻址空间为4G
• 数据总线=32位，可处理32位、16位或8位的数据（向下兼容）

80x86为向下兼容，启动后默认是实地址模式，可以手动切换到保护模式。

保护模式主要提供如下“保护”：

• 任务隔离：每个任务都有独立的虚拟地址空间，可映射到不同的物理地址；操作系统等共享数据可放在公共虚拟地址空间（全局地址空间），然后映射到同一块物理地址
• 特权级保护：4个特权级（0~3），操作系统运行在0级，用户程序运行在3级，每次访问都要检查权限；

保护模式的地址转换

                                         分段机制               分页机制
Selector : Offset = 逻辑地址（虚拟地址） ------------> 线性地址  -----------> 物理地址
  [16位]    [32位]
  
注：如果不开启分页机制，线性地址 = 物理地址

分段机制

进入保护模式前需要初始化GDT（Global Descriptor Table），切换到保护模式后，CPU通过GDTR（GDT Register）获取它的地址并访问；

Descriptor包含Segment的Base Address（32位）和Segment Limit（20位）

Selector的值是GDT的偏移，指向一个Descriptor，线性地址 = Base Address + Offset

GDTR ----> GDT + Selector ----> Descriptor ----> Base Address + Offset = 线性地址

见图：官方文档，P1969

分段机制实现了任务的隔离，每个任务都有独立的虚拟地址空间

分页机制

如果开启分页机制，线性地址被拆分成3块使用：

线性地址 = Directory(10位) + Table(10位) + Offset(12位)

CPU用CR3中存放的Page Directory地址，加上偏移Directory，找到PDE（Page Directory Entry）；
通过PDE中存放的Page Table地址，加上偏移Table，找到PTE（Page Table Entry）；
PTE中存放了Page Frame地址，物理地址 = Page Frame Address + Offset

CR3 ----> Page Directory + Directory ----> Page Table + Table ----> Page Frame Address + Offset = 物理地址

见图：官方文档，P1991

分页的作用：

• 将连续的大块线性地址拆分成4K的页存放在任意物理地址，可以解决程序占用的线性地址空间比物理内存容量大的问题，即程序不用再担心物理内存不够用
• 程序或数据被切分成4K的Page Frame，而Page Fault能让Page Frame直到被访问时才载入内存，提升了加载速度

中断与异常处理

IDT（Interrupt Descriptor Table）中可存放三种Descriptor：

• Task-gate Descriptor：用于任务切换
• Interrupt-gate Descriptor：处理Interrupt
• Trap-gate Descriptor：处理Exception

中断：由外部硬件或软件产生
异常：检测到程序或硬件错误，也可软件模拟
区别：调用Exception Handler之前，CPU会将Error Code压入栈，以便Handler追查错误原因，但中断不会；

CPU通过IDTR找到IDT，加上Interrupt Vector找到对应的Gate Descriptor，里面存放了Selector和Offset，然后通过分段机制……

IDTR ----> IDT + Interrupt Vector ----> Gate Descripotr ----> Selector + Offset -----> 分段机制

见图：官方文档，P2075

任务切换

Task-gate Descriptor可以存放在GDT、LDT或IDT中，当需要任务切换时，访问Task-gate Descriptor，CPU自动将其中的Selector加载至TR（Task Register），完成任务切换；

TR指向GDT中的TSS Descriptor，里面的Base Address指向TSS（Task Status Segment），用来保存任务上下文，即所有相关寄存器的值，以便下次切换回来后能够还原之前的上下文；

因此任务切换的本质就是把旧任务的上下文保存到当前TR（旧任务）指向的TSS中，然后修改TR值并用其（新任务）指向的TSS初始化上下文；这个过程是在改变TR值时由CPU自动完成的；

LDT/GDT/IDT ----> Task-gate Descriptor ----> TSS Selector ----> TR ----> [Old TSS << Context << New TSS]

见图：官方文档，P2124

每个TSS里都保存有如下信息，这样每个任务才能有独立的虚拟地址空间：

• LDT Segment Selector：用于通过GDT（全局地址空间）找到任务的LDT（局部地址空间），即分段机制
• CR3（PDBR，Page Directory Base Register）：Page Directory地址，即分页机制

系统初始化

• [当前为进程0]
• 获取并保存硬件信息
• 合理划分物理内存
• 初始化所有硬件和驱动（块设备、字符设备、tty、硬盘、软驱等等）
• 从内核态（0级）切换到用户态（3级）
• 创建子进程1（init()）
  • 加载RamDisk、安装根文件系统
  • 设置终端IO（把/dev/tty0作为stdin、stdout、stderr）
  • 执行Shell（/bin/sh）
• 死循环（pause()）

内存管理

物理内存划分

|  Kernel  |  Buffer  |  RamDisk  |  Main Memory  |
0         end        4M          4.5M            16M

Linux 0.12内核默认最大支持16MB物理内存
Buffer：1K块单位，用于块设备的缓冲
Main Memory：4K页单位，由内存管理（mm）模块通过分页机制管理和分配

进程线性地址空间

  |---------------------- 64MB -------------------------|
  |   Code   |   Data   |   BSS   |   Stack   |   Env   |
n*64MB                                               (n+1)*64MB

每个进程的线性地址空间为64MB，进程起始线性地址 = n * 64MB（n为进程号）

一些机制

• Page Fault：缺页异常。当被访问的页不存在或者权限不够时发生，处理程序返回后会重新执行引起错误的指令；
• Copy On Write：写时复制。当创建子进程时，父子进程共享同一个副本，并改为大家都只读，直到其中一方要写时，产生Page Fault，将该页复制一份后，大家都可写自己的页；这样可以加快创建进程的速度和节约内存；
• Load on Demand：按需加载。利用Page Fault可以当需要时再加载页至内存

文件系统

布局

（Minix）文件系统将整个磁盘（分区）划分为1KB的块

| Boot Block | Super Block | Inode Bitmap | Block Bitmap | Inodes | Blocks |

• Boot Block：由BIOS自动读取的引导代码（不用可以空着）
• Super Block：存储文件系统各划分区域的信息
• Inode Bitmap：每个位对应Inodes区域的一个Inode，置1表示该Inode被占用，用于快速查找空闲Inode
• Block Bitmap：每个位对应Blocks区域的一个Block，置1表示该Block被占用，用于快速查找空闲Block
• Inode：固定大小的结构体，每个文件或目录都对应一个Inode，记录了文件或目录的属性，并指出其数据所在的Block号
• Block：逻辑块，（Minix）逻辑块大小 = 物理块大小 = 1KB

读取文件

# 以/bin/sh为例
Super Block Table ----> Super Block ----> Inode of "/" ----> Block of "/" ----> DirEntry of "bin" (match name)
----> Inode of "bin" ----> Block of "bin" ----> DirEntry of "sh" (match name)
----> Inode of "sh" ----> Block of "sh"

Inode如果代表文件，相应Block里面就是文件内容；
Inode如果代表目录，相应Block里面存放的是DirEntrys，每个固定大小的DirEntry包含一个Name和一个Inode号，因此查找目录中的文件就是匹配DirEntrys中的Name。

硬链接：硬链接的Inode和被链接文件的Inode指向同一个Block，因此硬链接不能跨文件系统
符号链接：符号链接是个文本文件，（Block）里面存放的是被链接文件的路径（字符串），因此可以跨文件系统

查找Block的方式：

• 直接块号（7个）：对应一个Block
• 一级间接块号（1个）：如果文件较大（>7KB），直接块号不够用，就需要一次间接查询，一个间接Block里面能存放256个Block号
• 二级间接块号（1个）：原理同上，经过两次间接查询

Buffer

磁盘逻辑块被读入内存后就缓存在Buffer里面，下次再访问就直接到Buffer里取，可以提升块设备的访问速度；

整个Buffer被划分为两部分，即相同数量的Buffer Heads和Buffer Blocks

| Buffer Heads | Buffer Blocks |

Buffer Head是固定大小的结构体，里面主要包含：

• 逻辑块号
• 数据源的设备号
• 修改标志：即是否被保存到磁盘
• 锁标志：防止多方同时修改同一个Block
• Hash表：用于快速查找到对应的Buffer Block
• 空闲链表：按照空闲程度排列Buffer Block，最空闲的放在最前面待用

Buffer Block里面存放逻辑块的数据，Buffer Block Size = 逻辑块大小 = 1KB

文件类型

• 常规文件
• 块设备文件：可在块设备指定偏移处读写
• 字符设备文件
  • 串口终端（ttyS）
  • 控制台终端（tty）
  • 内存设备（memory）
  • 端口（port）
• 管道文件（pipe）：就是一个page的缓冲区，inode中有该缓冲区地址，并且有缓冲区中数据的头、尾指针

块设备驱动

块设备是以数据块为单位寻址、访问的设备

工作流程：

• 程序向缓冲区管理模块申请读取逻辑块后进入睡眠态，如果缓冲区中有则立即返回并唤醒程序
• 如果不存在，调用块设备驱动
• 创建一个request，并插入request list（为提高效率按照电梯移动算法逐个处理）
• 处理request，向设备控制器发出读指令
• 设备控制器将数据读到指定位置后，产生中断
• 中断处理程序唤醒进程

字符设备驱动

字符设备是以字符流为操作对象的设备，不能寻址

术语：

• terminal(终端)=tty(Teletype打字机)=IO环境（抽象概念）
• console(控制台)=物理终端设备

终端设备类型：

• 串行终端（ttyS）：硬件接口
• 伪终端（ptyp、ttyp）：伪终端为其它程序提供类似终端式样的接口，主要用于远程登录和X终端；必须成对使用：ptyp（主设备）、ttyp（从设备）
• tty,ttyn,console：tty是当前进程控制终端，tty1~tty6是虚拟终端，tty0是当前使用的虚拟终端的别名；

终端工作模式：

• 规范模式（canonical）：数据要经过行规则（line discipline）处理，比如将TAB替换为8个空格
• 原始模式（raw）：不处理数据

工作流程：

1. 进程调用API读取用户输入，进入睡眠态
2. 用户敲击键盘，产生中断
3. 中断处理程序将键盘扫描码转换为ASCII码放入读缓冲队列（如果开启回显则同时放入写缓冲队列，并调用控制台驱动，将写缓冲队列的字符显示在屏幕上），再将字符处理后放入辅助队列
4. 唤醒等待辅助队列的进程

参考

• 赵炯. Linux内核完全剖析——基于0.12内核. 机械工业出版社,2011.
• Intel Co. Intel 64 and IA-32 Architectures Software Developer Manuals.