操作系统与数据库基础
计算机基础四大件的另外两件(网络在 18 篇)。操作系统这块你底层强,容易拿分;数据库移动端偏 SQLite,掌握核心概念即可。
第一部分:操作系统
一、进程、线程、协程
| 进程 | 线程 | 协程 | |
|---|---|---|---|
| 资源 | 独立地址空间 | 共享进程内存 | 共享线程,用户态 |
| 调度 | OS | OS | 用户/运行时 |
| 开销 | 大 | 中 | 小 |
| 通信 | IPC | 共享内存(需同步) | 直接 |
- 进程:资源分配的基本单位,有独立内存空间。
- 线程:CPU 调度的基本单位,共享进程资源,需同步(锁)。
- 协程:用户态轻量“线程“,由程序调度,挂起不阻塞内核线程(见 02 篇 Kotlin 协程)。
二、进程间通信(IPC)
管道、消息队列、共享内存(最快,需同步)、信号量、Socket、信号。Android 主用 Binder(见 09 篇,一次拷贝 + 安全)。
三、内存管理
- 虚拟内存:每个进程有独立虚拟地址空间,通过页表映射到物理内存,实现隔离 + 按需加载。
- 分页:内存分固定大小页,虚拟页↔物理页帧映射,缺页中断时从磁盘加载。
- 页面置换:内存不够时选择淘汰哪个页,目标是降低未来缺页率。
页面置换算法
| 算法 | 机制 | 优点 | 缺点/坑点 | 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 近似公平:谁“用得少”谁更容易被调度。Android 在此基础上叠加线程优先级、cgroup/cpuset、前后台进程调度策略;UI 线程应避免长时间占 CPU,否则即使能被调度也会错过 16.6ms 帧预算。
面试答题流:先说目标(公平/响应/吞吐),再逐个算法讲机制和缺点,最后补“真实 Linux/Android 用 CFS + 优先级/cgroup,不是直接套书本算法”。
五、I/O 模型(进阶,可选)
阻塞 I/O、非阻塞 I/O、I/O 多路复用(select/poll/epoll)、信号驱动、异步 I/O。Android 的 Looper 底层就用了 epoll(无消息时阻塞等待,见 09 篇)。
第二部分:数据库
一、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 次数)、叶子节点链表(范围查询快)、非叶子只存索引(单页存更多键)。
- 聚簇索引 vs 非聚簇索引:聚簇索引叶子存整行数据(主键),非聚簇叶子存主键需回表。
- 最左前缀:联合索引
(a,b,c)从左匹配,where b=x用不上。 - 索引失效:对索引列函数运算、隐式类型转换、
like '%x'前缀模糊、OR 部分无索引。 - 代价:占空间、拖慢写入(增删改要维护索引)。
三、事务(ACID)
- A 原子性:全成功或全回滚。
- C 一致性:事务前后数据完整性约束不破坏。
- I 隔离性:并发事务互不干扰。
- D 持久性:提交后永久保存。
隔离级别(解决并发问题)
| 级别 | 脏读 | 不可重复读 | 幻读 |
|---|---|---|---|
| 读未提交 | 可能 | 可能 | 可能 |
| 读已提交 | 否 | 可能 | 可能 |
| 可重复读(MySQL默认) | 否 | 否 | 可能(InnoDB 用 MVCC+间隙锁基本解决) |
| 串行化 | 否 | 否 | 否 |
- 脏读:读到别的事务未提交的数据。
- 不可重复读:同一事务两次读同一行结果不同(被别人 update)。
- 幻读:同一查询两次返回行数不同(被别人 insert)。
四、SQLite / 移动端
- SQLite:嵌入式、单文件、无服务进程,Android 本地存储核心(Room 基于它)。
- WAL 模式:写前日志,提升并发(读写不互斥)。
- 移动端实践:用 Room 而非裸 SQLite(编译期校验 + 协程/Flow);大数据量分页;事务批量写;索引优化查询;数据库迁移 Migration。
高频面试题
Q1:进程和线程区别? 进程是资源分配单位有独立地址空间;线程是 CPU 调度单位共享进程资源。进程间隔离开销大,线程间共享内存需同步。
Q2:死锁产生的四个条件?怎么避免? 互斥、持有并等待、不可剥夺、循环等待。破坏任一即可:如资源一次性申请(破坏持有并等待)、按固定顺序申请资源(破坏循环等待)。
Q3:为什么数据库索引用 B+ 树? B+ 树矮胖减少磁盘 I/O,非叶子节点只存键能存更多、降低树高,叶子节点链表利于范围查询和排序。相比红黑树/B 树更适合磁盘存储。
Q4:事务隔离级别?分别解决什么问题? 读未提交→读已提交(解决脏读)→可重复读(解决不可重复读)→串行化(解决幻读)。级别越高越安全但并发越低。
Q5:什么情况索引会失效?
索引列做函数运算/类型转换、like '%x' 前缀模糊、不满足最左前缀、OR 连接非索引列。
Q6:Looper 为什么不会因为死循环耗尽 CPU?(联系 OS) 底层用 epoll,MessageQueue 无消息时阻塞在 epoll_wait 让出 CPU,有消息再唤醒,不是忙等。
Q7:虚拟内存的作用? 给每个进程独立的地址空间(隔离 + 安全)、突破物理内存限制(按需分页 + 换页)、简化内存管理(连续虚拟地址映射到不连续物理页)。