- Chapter1 编写单机API
- 排序
- 归类
- 最短路径
- Chapter2 多进程API
- Chapter4 SQL =》API
- Chapter5 数据 =》数据库
1.1. Chapter1 绪论
1.1.1. 软件开发流程
- 问题分析与抽象
- 系统结构设计
- 数据库设计
- 算法分析与设计
- 数据结构分析与设计
- 编译实现
- 性能分析与改进
- 编程与测试
1.1.2. 软件系统核心逻辑
- 数据结构与算法设计类型
1.1.3. 软件系统运行平台
- 计算机操作系统–”硬件上的第一层软件”(实际不恰当,因为还有BIOS)
- 管理三大资源:
- 管理CPU
- 管理存储
- 进程管理
- 管理I/O
- 提供用户接口
- 命令行
- GUI
- 提供开发接口
发展历史:
- 纸带阶段
- 批处理阶段
- 管理程序阶段
- 通道:用于控制I/O设备与内存间的数据传输
- 中断
- 控制程序发展为executive system,常驻内存
- 多批批处理
- 分时系统(Time-Sharing System)
- 工业化军事金融领域:实时系统(Real-Time System)
操作系统功能:
- 处理机资源: 以进程或线程为单位完成处理机资源的分配调度
- 进程控制:创建,撤销,挂起,改变运行优先级等–主动改变进程状态
- 进程同步:协调并发进程之间的推进步骤–交换信息能力弱
- 进程通信:进程间的数据传输
- 进程调度:作业和进程的运行交换
- 存储器管理: 提高内存利用率,提供足够的存储空间,方便进程并发运行
- 存储分配与回收
- 存储保护:保证进程互不干扰,相互保密
- 地址映射:进程逻辑地址到内存物理地址的映射
- 内存扩充(覆盖,交换和虚拟存储):提高内存利用率,扩大进程的内存空间
- 设备管理: 方便设备使用,提高CPU与I/O设备利用率
- 设备操作:利用设备驱动(位于Kernel)完成对设备的操作
- 设备独立性(device independence):提供统一的I/O接口,应用程序独立于物理设备
- 设备分配与回收:多用户间共享I/O设备资源
- 虚拟设备(virtual device):设备有多个进程共享,比方说虚拟打印机
- 缓冲区管理:匹配CPU和外设的速度
- 文件管理: 解决软件资源的存储,共享,保密和保护
- 文件存储空间管理:解决如何存放信息,提高空间利用率和读写性能
- 目录管理:解决信息检索问题
- 文件的读写管理和存储控制:解决信息安全问题,文件权限,系统token
- 软件管理:软件版本,相互依赖关系,安装和拆除
- 作业管理: 提供用户访问操作系统的接口
- 系统命令:供用户用于组织和控制自己的作业运行.命令行或GUI联机,命令脚本-“脱机”
- 编程接口:供用户程序和系统程序调用操作系统功能.系统调用和高级语言库函数
1.1.4. 软件系统数据管理
- 数据库体系
DBMS系统对数据库操作
1.1.5. 软件系统程序编译
- 编译连接
1.2. Chapter2 软件系统逻辑
1.2.1. 简单物流质询系统最优路线计算案例分析
需要考虑很多因素：
- 物品的优先级排序
- 路径的选择问题
- 采用海陆空哪种运输最便宜
1.2.2. 线性数据结构
23.3.7 上午一二节
- 线性表的存储结构
- 顺序存储和链式存储以及存储特点
- 线性表的基本操作编程实现
- 查找
- 插入
- 删除
1.2.3. 树数据结构
- 二叉树和树的递归定义和基本性质
- 二叉树,树和森林的顺序存储及链式存储,各种遍历方法
1.2.4. 图数据结构
- 图的基本概念,基本操作和存储
- 邻接矩阵,邻接表(逆邻接表)
- DFS和BFS
1.2.5. 分治递归和贪心算法
- 分治递归算法的思想
- 贪心算法思想
- 最短路径问题
1.2.6. 查询排序算法
23.3.14
- 基本排序算法
- 内部排序（内存）
- 插入
- 选择
- 交换
- 改进（分治）从$O(n^2)\to O(nlogn)$
- 外部排序
- 内部排序（内存）
- 利用分治递归思想的改进型排序算法
- 基本查询算法
1.3. Chapter3 软件系统运行平台
1.3.1. 多进程多用户文件一致性读写访问案例分析
1.3.2. 软件并发与进程-进程
- 程序并发执行
- 进程的定义与特征
- 进程的基本状态
- 进程控制模块的基础知识
- 线程
1.3.3. 软件并发与进程-同步
- 进程互斥与同步问题及其解决办法
- 信号量与管程机制
- 进程直接通信和间接通信方式
- 生产者/消费者问题
1.3.4. 程序的装入和链接
- 现代计算机系统的程序装入和链接机制
- 程序空间分类
- 链接技术
1.4. Chapter4 软件系统程序编译
1.4.1. 编译概述
1.4.2. 语言及文法
1.4.3. 词法分析
词法分析器
词：二元组（type，value）
符号表（名称｜value）
（*）DFS，NFS
1.4.4. 语法分析
- 上下文无关文法
- 下推自动机
文法： - 上-下
- 使用左递归
- 不确定-词法分析过程中不确定分析过程
- 确定-清除回溯-无左递归
- 1/2
- 右递归
（*）First集/Follow集
- 使用左递归
1.4.5. 语义分析和中间代码生成
- 词法分析->语法分析->语义分析
词法分析
- 自上而下（LL）
- 递归下降
- 词汇表
- 构建
- 递归栈
- AST树
- 自下而上构建AST
- AST树离散
- AST树
- 自下而上（LR）
- 规约
- 递归栈
- 规约
语法分析
- 语法翻译制导
- 依赖图
- 语法树
语义分析
- 依赖图
- 遍历
- 自上而下
- 翻译模式
- 推导
- 翻译模式
- 自下而上
- 加一个语义化
- 规约
最后得到
- 规约
- 加一个语义化
- 自上而下
- 执行结果
- 中间代码（AST、三/四地址）
语法分析 | ├── 语法翻译制导 | | | ├── 依赖图 | | | └── 语法树 | └── 语义分析 | ├── 依赖图 | └── 遍历 | ├── 自上而下 | | | ├── 翻译模式 | | | | | └── 推导 | | | └── 执行结果 | └── 自下而上 | ├── 加一个语义化 | | | └── 规约 | └── 中间代码（AST、三/四地址）
汇总：
词法-语法-「「解释API；生成中间代码」-「什么样子-「三地址，四元式；三元式」；间接三元式-「间接对象（代码执行顺序）；三元式表（内容）」；-语义-「自上而下；自下而上」-「OP；Type」
词法
|
└── 语法
|
├── 解释API；生成中间代码
| |
| ├── 什么样子
| | |
| | ├── 三地址，四元式
| | |
| | └── 三元式
| |
| └── 间接三元式
| |
| ├── 间接对象（代码执行顺序）
| |
| └── 三元式表（内容）
|
└── 语义 |
└── Type
|
| └── OP
|
├── 自上而下
|
└── 自下而上
