# Foundation

我非常希望看到这里的同学能够认认真真去系统性的学习整个计算机体系结构。因此我将各个模块中偏向应用的东西都梳理了出来。这些梳理出来的点比较偏工程，稍做迁移就可以应用在我们工作当中。学习的时候可以暂时根据这些梳理出来的关键字去过一下知识点。

我省略了《软件工程》与《数据库系统》的内容，因为前者方法论适合实践总结，后者我还不太熟悉。我推荐一本《计算机程序的构造和解释（SICP）》，是MIT本科的第一门课，讲述如何构造和分析复杂系统（程序）。这些书我自己也定期的回顾，之前与大佬讨论，不论科班还是非科班出身，不断回顾并思考计算机基础的东西，是非常重要的。

# Operating System

• 进程与线程
• 虚拟地址，物理地址
• 进程间通信：临界区、忙等待互斥、睡眠与唤醒、信号量、互斥量、管程、消息传递、屏障、避免锁
• 进程调度策略：批处理、交互式、实时；
• 批处理调度：FCFS、SJF、SRTF
• 交互式调度：轮转、优先级、多级队列、最短进程优先、保证调度、彩票调度、公平分享调度
• 实时调度：硬实时、软实时、周期性
• IPC问题：读者-写者、生产者-消费者、哲学家进餐、银行家算法
• 页面置换算法：最优页面置换算法、最近未使用页面置换算法（NRU）、先进先出页面置换算法（FIFO）、第二次机会页面置换算法、时钟页面置换算法（clock）、最近最少使用页面置换算法（LRU）、软件模拟LRU、工作集页面置换算法、工作集时钟页面置换算法

# Computer Organization

• 缺页中断——FIFO、LRU、OPT三种置换算法
• 流水线、指令集

# Network

• 帧、报文、报文段、分组、包、数据报的概念
• DNS原理
• UDP和TCP
• 可靠性数据传输原理、拥塞控制原理
• 路由选择：RIP、OSPF、BGP
• 差错检验和纠正技术
• 计算机网络安全

# Algorithm

• 递归与非递归
• 排序算法（8种）
• 栈、队列、散列表、二叉树、红黑树
• 动态规划、贪心、平摊分析
• B树、二项堆、斐波那契堆、不相交集合
• 最小生成树Kruskal和Prim，最短路Dijstra和Bellman-Ford
• 最短路Floyd-Warshall和Johnson，最大流Ford-Fulkerson
• 排序网络、矩阵运算、线性规划、多项式与快速傅立叶变换
• 有限数论，字符串匹配Rabin-Karp和KMP
• 计算几何学、NP完全性、近似算法

# Compliers

• 词法分析、自动机、DFA
• 语法分析、语法制导
• 中间代码、AST树、类型检查
• 堆、栈管理，垃圾回收机制
• 目标代码生成、代码优化
• 指令集并行性
• 并行性与局部性优化
• 过程间分析