计算机系统笔记

基础硬件

计算机系统可分为：CPU、内存、输入设备、输出设备

CPU内部由运算单元和操作单元组成。

CPU依据设计风格可分为两种：精简RISC和复杂CISC指令集。RISC指令集的指令较为精简，指令功能单一，运行时间短，常见RISC指令集的CPU有ARM等等;SISC指令集不同于RISC，是把一些简单的操作合成一条，指令执行较为复杂且运行时间长，但功能丰富，常见SICS指令集CPU主要有AMD、Intel等x86架构。

网络速度单位：Mbps，例如 8M/1M ADSL 传输速度指的就是理论最大传输值为:每秒8Mbit(1Mbyte)/每秒1Mbyte(125Kbyte)的上传/下载容量。

CPU倍频和超频：为兼顾外部组件，CPU工作时CPU不得不降低其运算频率;但其内部工作频率可以很高，以提供强大的运算能力。那所谓的外频就是CPU与外部组件进行数据传输时的速度，倍频则是CPU内部用来加速工作效能的一个倍数，二者相乘才是我们平时所说的CPU工作频率。而超频，就是通过提高CPU外频，进而提高内频的手段。但CPU外频一般都是厂家预定设计好的，贸然更改可能会导致电脑完蛋。

一般主板芯片组有分北桥和南桥, 北桥的总线称为系统总线,因为是内存传输的主要信道,所以速度较快。南桥就是所谓的输入输出(I/O)总线,主要在联系硬盘、USB、网卡等接口设备。

总线带宽 = 工作频率 * 总线宽度

CPU等级：i3, i5, i7

内存：DRAM, SRAM。前者主要用于内存，后者速度快，主要用于CPU缓存（cache）。

BIOS：ROM

GPU：专攻图形运算

外部存储：

硬盘：扇区，磁道，磁柱

编码系统：ascll ——> Unicode（UTF8）

操作系统核心（Kernel）：核心是参考硬件写成的，所以不同架构就有不同版本的操作系统

核心（Kernel）功能：

接口
内存管理
程序管理
文件系统管理
装置驱动管理

计算机网络

计算机网络分为五层：

网络层：交互，域名，URL，DNS
传输层：确定端口，多路复用，拥塞控制，流量控制，差错控制，传输层协议（UDP, TCP, SCTP）
网络层：数据包，确定传输路线，路由选择（RIP, OSPF, BGP），IPv4，IPv6
数据链路层：数据帧，封装数据包，MAC　地址（物理地址，与 IP（逻辑地址）相对）
物理层：　实际传输数据

操作系统

自举

发展历史

批处理系统
分时系统
个人系统
并行系统
分布式系统
实时系统

组成：内存管理器、进程管理器，设备管理器，文件管理器，用户界面

内存管理器：
- 单道程序：程序运行时独占内存。即便程序在等待 I/O，并不需要 CPU，也不允许其它程序进入内存，使用 CPU。
- 多道程序：同一时刻内存可以载入多个程序，CPU 轮流服务。具体又可分为非交换（分区，分页）和交换（请求分页，请求分段）模式。
- 虚拟内存：程序运行，需要占用内存。在请求调度下，程序只需要一部分载入内存，增强了内存的承载能力，扩大了计算机内存。
进程管理器：
- 程序：统称
- 作业：进入内存的程序，等待运行，或者等待 I/O，或者等待退出内存
- 进程：调用 CPU 开始执行的作业
- 调度器：协调程序状态转换
- 队列；协调资源的一种有效策略
- 进程同步：
  - 锁死：系统没有对资源的使用进行限制
  - 饿死：系统对资源的使用限制过多
设备管理器：管理 I/O 资源，一般使用队列
文件管理器

不同的操作系统

UNIX：1969 年，贝尔实验室，Thomson, Ritchie 开发
Linux：1991 年，芬兰 Helsinki 大学学生 Linus Torvalds 开发
Windows：20 世纪 80 年代后期，微软开发

抽象数据类型（ADT）

简单数据类型：整数、实数、字符、指针
抽象数据类型模型：数据结构，操作函数（公有，私有）

栈：限制线性列表，后进先出

栈的应用：倒转数据，配对数据，数据延迟使用，回溯步骤
栈的实现：数组，或者链表；两个域

队列：限制线性列表，先进先出

队列的应用：调节 I/O
队列的实现：三个域，计数域、队首域、队尾域

广义线性表：就是排序好的链表，所有项数据类型相同

广义线性表的操作：list, insert, delete, retrieve, traverse, empty
广义线性表的应用：学生信息系统
广义线性表的实现：数组或链表；两个域

树——二叉树：任一节点最后只能有两个子树

二叉树的操作：遍历
- 深度优先：前序遍历、中序遍历、后序遍历，还有三种
- 广度优先：一层一层的处理
二叉树的应用——赫夫曼编码
二叉树的应用——表达式树：算数表达式可以用三种格式来表示：中缀、前缀、后缀。平常我们书写的表达式即是用中缀表示。但程序编译时会将其转化为后缀表示。
- 前缀：+ A B
- 中缀：A + B
- 后缀：A B +
二叉树的实现：，可以用数组，但链表效率更高

二叉搜索树（BST），每个节点的值都大于其左子树的所有节点的值。中序遍历，会得到升序列表。可以使用折半查找。

二叉搜索树的实现：列表效率更高

图：一组节点和一组节点的连线构成的一种抽象数据类型。

图和树的差异：树是层次结构，有向的；而图无层次，可以有向，也可以无向。可应用于城市的地图和连接城市的道路、计算机网络……

文件结构

　文件就是数据记录的集合

存取方式

顺序存取：顺序文件
随机存取：索引文件，散列文件

顺序文件

记录按顺序一个个存取

文件更新：

更新需要的文件：新文件，旧文件，事务文件，错误报告文件
文件更新过程：所有文件按同一键排序，然后依次比较旧文件和事务文件键值，根据键值的不同，增加、更改、删除数据。

索引文件

带索引的顺序文件，索引包含顺序文件的键和相应记录在内存中的地址，即键－地址对，通过键值对应的地址找到记录。索引是顺序存储的。

索引文件可以有不止一个的索引

倒排文件

散列文件

索引文件中，键通过索引－键值对－映射到数据地址；
散列文件中，键通过函数，映射到数据地址。

散列方法

直接法
求模法
数字析取法
……

冲突

使用散列，可能出现多个键值映射到同一地址的情况，即出现冲突，可以使用下列方法解决：

开放寻址
链表
桶散列法

这几种方法各有优缺点，往往根据实际情况组成使用。

数据库

数据库模型：

层次模型，网状模型，关系模型。前两种被淘汰，只有最后一种在使用。
现在还有其他两种常见模型：分布式数据库、面向对象数据库。

分布式数据库：数据分布在各个站点或者在每个站点都有完整的副本
面向对象数据库：

SQL 语句：

insert, delete, update, select, union, intersection, minus；其它关键词：values, from, where, set

数据库设计：

实体关系模型（ERM）及其规范化

压缩

安全

安全目标：

机密性
完整性
可用性

对应可能受到的攻击：

探嗅、流量分析；
修改、假冒、回放、否认；
拒绝服务。

相应的五类安全服务：

数据机密性：对称、非对称密钥均可解决
数据完整性：散列函数形成消息摘要可以保护数据完整性
验证：MDC(modification detection code) –> MAC(modification authentication code) ，其实就是用密钥加密糊弄了一下。当然，用数字签名是更好的办法。
不可否认：数字签名，一个中立的可信中心。发送者将信息传给可信中心，可信验证通过后，保留信息副本，用可信中心自己的私钥签名后发送给接收者，接收者使用可信中心的公钥验证消息。
访问控制：

密码概念

密码：即加密、解密算法
密钥：算法参数
明文：未加密的消息
密文：加密后的消息

对称密钥密码

传统密码：置换、移位
现代密码：DES —> AES

非对称密钥密码

明文和密文被当作整数来看待，所以常被用来加密少量信息。

RSA 算法是最常用的非对称加密算法

散列密码

经过散列密码压缩后的信息可以用来确认消息是否完整，有无修改。

数字签名

同样是使用非对称密钥，但是发送者是用自己的私钥加密，然后由接收者用发送者的公钥验证签名

实体验证

要求实时验证，分为：所知道的、所拥有的、所固有的。

口令、质询－相应、零知识、生物测定。

密钥管理

一般而言，使用可信中心比较安全

对称密钥：可信中心 KDC
非对称密钥：　认证机构 CA