操作系统与数据库基础

本章覆盖通用操作系统概念, MySQL/InnoDB 面试术语和 Android SQLite/Room 实践. 网络见网络协议, Binder 见 Binder 与 IPC 深入. 不同数据库实现不能混用同一套结论.

学习目标与章节边界

本章定义 OS, 并发和数据库的基础术语, 并给出 SQL/SQLite 的基础机制. mmap, I/O 多路复用, 传统 CFS 的 vruntime 心智模型, EEVDF 版本边界和死锁现场排查在操作系统进阶展开, 避免重复. 完成后应能画出事务并发时序, 解释索引是否覆盖查询, 并为 SQLite 锁问题收集证据.

一, 进程, 线程, 协程

	进程	线程	协程
资源	独立地址空间	共享进程内存	共享线程, 用户态
调度	OS	OS	用户 / 运行时
开销	大	中	小
通信	IPC	共享内存 (需同步)	直接

进程: 资源分配的基本单位, 有独立内存空间.
线程: CPU 调度的基本单位, 共享进程资源, 需同步 (锁).
协程: 由语言 / 运行时调度的可挂起任务, 挂起本身不阻塞承载线程, 详见 Kotlin 协程与 Flow.

二, 进程间通信 (IPC)

管道, 消息队列, 共享内存, 信号量, Socket 和信号各有语义与代价. Android 进程间调用主要使用 Binder;“一次拷贝” 只是在特定数据路径和实现语境下的简化, 详见 Binder 与 IPC 深入.

方式	数据路径	适合	典型失败边界
管道/Unix domain socket	内核缓冲传递字节流	父子进程, 本机服务	无消息边界或未处理背压会阻塞/丢协议边界
共享内存	多进程映射同一页	大块数据	只共享数据, 不共享同步; 仍需原子/锁/信号量
Binder	`Parcel` 请求, 内核驱动路由, 线程池分发	Android 服务 RPC	同步调用可阻塞调用线程; 大 payload 应改文件描述符 / 共享内存方案

选择 IPC 时先明确 “传命令还是传大数据”“ 同步还是异步 ““谁负责生命周期”.例如 UI 进程给 remote service 发小控制命令可用 AIDL/Binder; 把几十 MB 图片直接塞进 Transaction 会触及 Binder 事务大小与内存压力边界. 证据路径: 查看调用线程堆栈是否等待 Binder, 再看服务端线程池/耗时操作, 最后验证改为异步或流式传输后调用是否恢复.

三, 内存管理

虚拟内存: 每个进程有独立虚拟地址空间, 通过页表映射到物理内存, 实现隔离 + 按需加载.
分页: 内存分固定大小页, 虚拟页↔物理页帧映射, 缺页中断时从磁盘加载.
页面置换: 内存不够时选择淘汰哪个页, 目标是降低未来缺页率.

页面置换算法

算法	机制	优点	缺点/坑点	Android/Linux 关联
FIFO	淘汰最早进入内存的页	实现简单	可能出现 Belady 异常: 分配页框更多反而缺页更多	面试用来说明 “简单策略不等于命中率高”
LRU	淘汰最长时间未访问的页	符合时间局部性	精确维护访问顺序成本高	系统常做近似 LRU, App 侧 LruCache 是同类思想
LFU	淘汰访问次数最低的页	适合长期热点稳定场景	旧热点可能因历史计数过高难淘汰, 需衰减	更常见于缓存策略讨论, OS 页面置换较少直接精确使用
Clock / 二次机会	页形成环, 访问位为 1 则清零并跳过, 为 0 才淘汰	近似 LRU, 实现成本低	只能粗略表达 “最近是否访问过”	操作系统常用近似策略, 兼顾成本与效果

Belady 异常: FIFO 不考虑局部性, 在某些访问序列中增加页框会改变淘汰顺序, 导致缺页次数反而上升; LRU 属于栈算法, 不会出现这种异常.

面试答题流: 先讲缺页中断和淘汰目标, 再用 FIFO/LRU/Clock 对比 “实现成本 vs 命中率”, 最后联系 Android: App 内存压力会触发 LMK/进程回收, 而 Linux 内核页回收也会用近似 LRU 思路维护活跃/非活跃页.

MMU / TLB: 硬件做地址翻译, TLB 缓存页表项加速.
用户态 vs 内核态: 特权级隔离, 系统调用 / 中断时从用户态陷入内核态.

四, 并发与同步

死锁四条件: 互斥, 持有并等待, 不可剥夺, 循环等待.破坏任一即可避免 (如按序申请资源破坏循环等待).
临界区: 互斥访问共享资源的代码段.
同步原语: 互斥锁, 信号量 (Semaphore), 条件变量, 读写锁.
CPU 调度: 在多个可运行任务之间分配 CPU, 目标通常是吞吐, 响应时间, 公平性和实时性之间折中.

CPU 调度算法

算法	机制	优点	缺点 / 饥饿问题	适用直觉
FCFS	先来先服务, 非抢占	简单, 无饥饿	短任务可能被长任务堵住 (护航效应)	批处理直觉, 交互系统不理想
SJF / SRTF	优先执行预计时间最短任务; SRTF 是抢占版	平均等待时间低	难准确预估执行时间, 长任务可能饥饿	理论题常考, 实际需估算
时间片轮转 (RR)	每个任务运行一个时间片, 到期切换	响应公平, 适合交互	时间片太小切换开销大, 太大退化为 FCFS	UI / 交互系统强调响应
优先级调度	高优先级先运行	能表达重要性 / 实时性	低优先级可能饥饿, 需 aging 提升等待过久任务	Android 线程优先级, 后台任务降级
多级反馈队列 (MLFQ)	多队列不同优先级 / 时间片, 任务按行为升降级	兼顾交互与吞吐	参数复杂, 可能被行为模式影响	通过反馈识别短交互任务与长 CPU 任务

Linux/Android 关联: 传统 / 常见的 Linux 普通任务调度心智模型是 CFS (Completely Fair Scheduler): 它不是简单 RR, 而是用虚拟运行时间 vruntime 近似公平, 谁 “用得少” 谁更容易被调度. 该模型适合解释经典 CFS 行为, 但不能冒充所有当前系统事实: 新上游 Linux 内核可能采用 EEVDF; Android 设备实际采用 CFS 还是 EEVDF, 以及是否有厂商回移植, 必须以实际 kernel 版本, 源码配置和厂商补丁为准, 详见操作系统进阶. 无论具体选任务机制如何, Android 仍会叠加线程优先级, cgroup/cpuset 和前后台进程调度策略; UI 线程应避免长时间占 CPU, 否则仍可能错过显示 deadline.16.7 ms 只是 60 Hz 的单帧周期示例, 多刷新率口径见 ANR 与卡顿排查.

面试答题流: 先说目标 (公平/响应/吞吐), 再逐个算法讲机制和缺点, 最后补 “ 可用 CFS + vruntime 解释传统/常见模型; 新上游内核可能采用 EEVDF, Android 必须按实际 kernel 版本, 源码配置和厂商回移植确认, 且还会叠加优先级/cgroup“, 不是直接套书本算法.

五, I/O 模型 (进阶, 可选)

阻塞 I/O, 非阻塞 I/O, I/O 多路复用 (select/poll/epoll), 信号驱动, 异步 I/O. Android 的 Looper 底层就用了 epoll(无消息时阻塞等待, 详见 Android 系统原理).

第二部分: 数据库

一, SQL 基础

增删改查: INSERT / DELETE / UPDATE / SELECT.
JOIN: INNER (交集), LEFT (左全保留), RIGHT, FULL.
聚合: COUNT/SUM/AVG/MAX/MIN + GROUP BY + HAVING.
子查询, UNION, ORDER BY, LIMIT.

二, 索引 (高频)

作用: 加速查询, 空间换时间. 底层多用 B+ 树.
为什么 B+ 树而非 B 树 / 红黑树? B+ 树矮胖 (减少磁盘 I/O 次数), 叶子节点链表 (范围查询快), 非叶子只存索引 (单页存更多键).
MySQL/InnoDB 聚簇索引: 主键 B+ 树叶子保存行记录; 二级索引叶子保存主键值, 查询其他列时可能回表. 这是 InnoDB 语境, 不能直接套到 SQLite 的存储实现.
最左前缀: 联合索引 (a,b,c) 通常需要从左侧条件开始才能高效定位; where b=x 通常不能用 a 的左前导键高效定位, 优化器仍可能选择全索引扫描, 或在少数实现 / 数据分布下使用 skip-scan, 必须以 EXPLAIN 验证.
索引失效: 对索引列函数运算, 隐式类型转换, like '%x' 前缀模糊, OR 部分无索引.
代价: 占空间, 拖慢写入 (增删改要维护索引).

三, 事务 (ACID)

A 原子性: 全成功或全回滚.
C 一致性: 事务前后数据完整性约束不破坏.
I 隔离性: 并发事务互不干扰.
D 持久性: 提交后永久保存.

隔离级别 (解决并发问题)

级别	脏读	不可重复读	幻读
读未提交	可能	可能	可能
读已提交	否	可能	可能
可重复读 (MySQL/InnoDB 默认)	否	否	SQL 标准允许; InnoDB 的 MVCC/next-key locking 行为需按查询与索引条件说明
串行化	否	否	否

脏读: 读到别的事务未提交的数据.
不可重复读: 同一事务两次读同一行结果不同 (被别人 update).
幻读: 同一查询两次返回行数不同 (被别人 insert).

SQL 并发时序: 先指明数据库与隔离级别

下列为 MySQL 8.0 / InnoDB 教学 SQL 时序, 假设表 account(id PRIMARY KEY, balance) 中已有 (1,100), 且 T1/T2 是两个不同的物理连接. 每段都在两个会话中显式设置隔离级别; 若连接池复用连接, 实验结束后应恢复会话设置. 不同引擎, 隔离级别, 索引条件和锁读会改变细节, 不能把这三段直接当作 SQLite 或其他数据库的全部行为.

脏读 (READ UNCOMMITTED 才可能):

-- T1                                      -- T2
SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED;
START TRANSACTION;
UPDATE account SET balance=0 WHERE id=1;
                                            SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED;
                                            START TRANSACTION;
                                            SELECT balance FROM account WHERE id=1; -- 读到 0
ROLLBACK;
                                            SELECT balance FROM account WHERE id=1; -- 100
                                            COMMIT;

T2 第一次读到了从未提交, 随后回滚的值. 解决是至少 READ COMMITTED; 证据是两个连接的事务日志与隔离级别, 而不是单次 SELECT 输出.

不可重复读 (READ COMMITTED 可出现):

-- T1                                      -- T2
SET TRANSACTION ISOLATION LEVEL READ COMMITTED;
START TRANSACTION;
SELECT balance FROM account WHERE id=1; -- 100
                                            SET TRANSACTION ISOLATION LEVEL READ COMMITTED;
                                            START TRANSACTION;
                                            UPDATE account SET balance=120 WHERE id=1;
                                            COMMIT;
SELECT balance FROM account WHERE id=1; -- 120
COMMIT;

同一行两次读取不同. 可重复读快照或适当锁读可避免, 但会牺牲新鲜度 / 并发.

幻读 (谓词范围新增行):

-- T1                                      -- T2
SET TRANSACTION ISOLATION LEVEL READ COMMITTED;
START TRANSACTION;
SELECT COUNT(*) FROM account WHERE balance >= 100; -- 1
                                            SET TRANSACTION ISOLATION LEVEL READ COMMITTED;
                                            START TRANSACTION;
                                            INSERT INTO account(id,balance) VALUES (2,150);
                                            COMMIT;
SELECT COUNT(*) FROM account WHERE balance >= 100; -- 2
COMMIT;

这里变化的是符合条件的 “行集合”, 不是已读行的列值. 串行化, 范围锁或引擎的 next-key locking 行为要结合实际 SQL / 索引验证.

MVCC 与覆盖索引

MVCC (多版本并发控制): 写事务产生行版本; 一致性读依据 read view 判断哪个已提交版本可见, 因此读者通常无需阻塞写者, 写者也不必等待普通快照读. 它不是 “没有锁”:写写冲突, 显式锁读, 范围约束仍可能等待. InnoDB 版本链 / undo log 是实现细节; SQLite 的 WAL 以读者快照和 WAL 文件实现读写并行语义, 不能逐项等同.

覆盖索引指查询所需列都在索引条目中, 执行器可直接返回索引数据, 避免按主键回表. 例如 InnoDB 中索引 (user_id, created_at, title) 可覆盖:

SELECT created_at, title
FROM article
WHERE user_id = 42
ORDER BY created_at;

若查询 SELECT body 而 body 不在该二级索引中, 仍需回表. 是否真覆盖应以 EXPLAIN/执行计划为证, 索引越宽也会增加写入和缓存成本.

四, SQLite / 移动端

SQLite: 嵌入式, 单文件, 无服务进程, Android 本地存储核心 (Room 基于它).
WAL 模式: 写入追加到 WAL, 通常允许读者与写者并行, 但 SQLite 仍是单写者模型, checkpoint, 长读事务和锁竞争仍会阻塞.
移动端实践: 用 Room 而非裸 SQLite (编译期校验 + 协程 / Flow); 大数据量分页; 事务批量写; 索引优化查询; 数据库迁移 Migration.

SQLite WAL 操作与排障: 对 Room 使用公开的 setJournalMode() 配置 WAL, 并保持事务短小. WAL 让读取旧快照的读者与一个写者通常并行, 但同一时刻仍只有一个写者; 长读事务会阻止 checkpoint 回收 WAL, 导致 -wal 文件增长或写者等待. 连接池, 事务与锁竞争的进阶边界见数据库进阶.

// Room 的公开配置;不要在回调中以 PRAGMA 覆盖其 journal mode 管理.
val database = Room.databaseBuilder(appContext, AppDatabase::class.java, "app.db")
    .setJournalMode(RoomDatabase.JournalMode.WRITE_AHEAD_LOGGING)
    .build()

// 仅用于当前拿到的物理 SQLite 连接的排障实验片段.
val connection = database.openHelper.writableDatabase
connection.execSQL("PRAGMA busy_timeout=2000")

busy_timeout 是物理连接级设置. 上面的片段只说明当前连接的实验行为, 不能推导 Room 全部连接池, 其他进程连接或生产配置都已设置; 生产策略应由实际 Room/SQLite 版本, 连接创建路径和压测结果确认. 排查 database is locked/busy: 症状是写入失败/超时; 证据是记录事务开始结束, SQL 耗时和 WAL 文件大小; 定位是否有长事务, 并发写或主线程事务; 修复为批量拆分, 单写串行化/重试退避, 并缩短读事务; 验证在代表性并发压测下锁等待和 WAL 增长受控. busy_timeout=2000 只是示例, 必须根据交互 deadline 和数据可靠性要求测量调整.

高频面试题

Q1: 进程和线程区别? 进程是资源分配单位有独立地址空间; 线程是 CPU 调度单位共享进程资源. 进程间隔离开销大, 线程间共享内存需同步.

Q2: 死锁产生的四个条件? 怎么避免? 互斥, 持有并等待, 不可剥夺, 循环等待. 破坏任一即可: 如资源一次性申请 (破坏持有并等待), 按固定顺序申请资源 (破坏循环等待).

Q3: 为什么数据库索引用 B+ 树? B+ 树矮胖减少磁盘 I/O, 非叶子节点只存键能存更多, 降低树高, 叶子节点链表利于范围查询和排序. 相比红黑树/B 树更适合磁盘存储.

Q4: 事务隔离级别? 分别解决什么问题? 读未提交→读已提交 (解决脏读)→可重复读 (解决不可重复读)→串行化 (解决幻读).级别越高越安全但并发越低.

Q5: 什么情况索引会失效? 索引列做函数运算 / 类型转换, like '%x' 前缀模糊, 不满足最左前缀, OR 连接非索引列.

Q6: Looper 为什么不会因为死循环耗尽 CPU?(联系 OS) 底层用 epoll, MessageQueue 无消息时阻塞在 epoll_wait 让出 CPU, 有消息再唤醒, 不是忙等.

Q7: 虚拟内存的作用? 给每个进程独立的地址空间 (隔离 + 安全), 突破物理内存限制 (按需分页 + 换页), 简化内存管理 (连续虚拟地址映射到不连续物理页).

主题练习与预期证据

用两个数据库连接按上述不可重复读时序操作, 预期记录两次结果与实际隔离级别; 若行为不同, 说明引擎 / 隔离级别, 而非强行套结论.
为 article 写一个查询只选覆盖列, 一个查询额外选 body, 预期用 EXPLAIN 说明是否需要回表.
制造一个持有事务的后台任务和一次写入, 预期收集锁等待 / SQL 时长; 修复后证明事务缩短或写入串行化.

Android 中级面试复习手册