第 1 章 计算机组成与体系结构

第 2 章 操作系统

进程管理

• 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块(PCB)和数据块三部分组成
• 进程与程序的区别:进程是程序的一次执行过程，没有程序就没有进程，程序是完成某个特定功能的一系列程序语句的集合，只要不被破坏，它就永远存在。程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后因撤销而消亡;进程是系统进行资源分配和调度的独立单位，而程序不是

进程管理-进程的状态

进程管理-进程的同步和互斥

• 互斥：直接制约关系
• 同步：间接制约关系

进程管理-PV操作

• 临界资源：各个进程间需要互斥方式对其进行共享的资源，如打印机
• 临界区：每个进程中访问临界资源的那段代码称为临界区
• 信号量：是一种特殊的变量，只能通过两个标准的原子操作来访问，即P操作和V操作
  • P操作：是一种申请资源的操作。S=S-1，若S>=0，则进程继续执行；若S<0，则该进程置为等待状态，排入等待队列
  • V操作：是一种释放资源的操作。S=S+1，若S>0，则进程继续执行；若S<=0，则从等待队列中唤醒一个等待进程

例子1：多个进程共享一台打印机问题（互斥模型）：

P(S);
// 访问打印机 S=1-1=0
V(S);
// 离开打印机 `S=0+1=1`
互斥信号量S的初始值为1

例子2：单缓冲区生产者、消费者问题（同步模型）

前趋图例题

❗PV操作总是成对出现的

进程管理-死锁

如果一个进程在等待意见不可能发生的事，则进程死锁。如果一个或多个进程产生死锁，就会造成系统死锁。

例题：系统有五个进程：ABCDE，这5个进程都需要4个系统资源，系统至少有多少资源才不会造成系统死锁

答：给每个进程分配需要-1个资源且系统还剩余一个空余资源即可。3*5+1=16

进程管理-银行家算法

• 银行家算法:分配资源的原则
  • 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程
  • 进程可以分期请求资源，但请求的总数不能超过最大需求量,
  • 当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。

例题

存储管理-段页式存储

存储管理-页式存储组织

页式存储：将用户程序的地址空间划分为若干个固定大小的区域，称为页，将内存空间划分为若干个与页大小相同的区域，称为页框。

逻辑地址=页号+页内地址 物理地址=页帧号(物理块号)+页内地址

优点：利用率高，碎片小，分配及管理简单 缺点：增加了系统开销；可能产生抖动现象

存储管理-段式存储组织

段式存储：按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样

优点：多道程序共享内存，各段程序修改互不影响 缺点：内存利用率低，内存碎片浪费大

段式存储中需要段表：

如果需要查找段号0，应该去40K-70K之间查找。 对于段号0，(0,25k)是一个合法段地址，(0,35k)是一个非法段地址，因为超过了段长（30K）

存储管理-段页式存储组织

段页式存储：先分段，再分页。1个程序有若干个段，每个段中可以有若干页，每个页的大小相同，但每个段的大小不同。

优点:空间浪费小、仔储共事容易、能动态连接 缺点:由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降。

存储管理-页面置换算法

1. 最优(Optimal，OPT)算法
2. 随机(RAND)算法
3. 先进先出(FIFO)算法:有可能产生“抖动”。例如，432143543215序列，用3个页面，比4个缺页要少
4. 最近最少使用(LRU)算法:不会“抖动”，LRU的理论依据是!“局部性原理
5. 时间局部性:刚被访问的内容，立即又被访问。
6. 空间局部性:刚被访问的内容，临近的空间很快被访问.

存储管理-磁盘管理

存取时间=寻道时间+等待时间，寻道时间是指磁头移动到磁道所需的时间; 等待时间为等待读写的扇区转到磁头下方所用的时间。

存储管理-磁盘调度算法

1. 先来先服务(FCFS )：按请求到达顺序调度，简单但可能造成较大寻道时间。
2. 最短寻道时间优先(SSTF)：优先处理与当前磁头位置距离最近的请求，减少寻道时间，但可能导致饥饿现象。
3. 扫描算法(SCAN)：磁头在磁盘上来回移动，按顺序处理沿途请求，减少远端请求的等待时间。
4. 循环扫描(CSCAN)算法：磁头只在一个方向处理请求，达到末端后直接返回起点，不处理中途请求，提供较均衡的响应时间。

存储管理-读取磁盘数据时间计算

读取磁盘数据的时间应包括以下三个部分:

1. 找磁道的时间
2. 找块(扇区)的时间，即旋转延迟时间,
3. 传输时间.

作业管理

作业状态与作业管理

提交->后备->执行->完成

作业调度算法

1. 先来先服务法：按请求到达顺序执行，简单但可能导致等待时间长。
2. 时间片轮转法：每个进程轮流执行固定时间片，公平但可能导致频繁切换。
3. 短作业优先法：优先执行执行时间最短的作业，减少平均等待时间，但可能造成长作业饥饿。
4. 最高优先权优先法：优先级高的进程先执行，可能导致低优先级进程长期等待。
5. 高响应比优先法：考虑等待时间和执行时间，平衡短作业优先和公平性，减少饥饿现象。

文件管理

索引文件结构

树型目录结构

空闲存储文件的管理

位示图法

单位换算：
1MB（兆字节）   = 1024KB（千字节）= 1024*1024B(字节) = 1048576B(字节)；
8bit（比特位）  = 1Byte（字节）；
1024Byte（字节）= 1KB(千字节)；
1024KB（千字节）= 1MB（兆字节）;
1024MB = 1GB;
1024GB = 1TB;

设备管理

数据传输控制方式

• 程序控制(查询)方式:分为无条件传送和程序查询方式两种，方法简单，硬件开销小，但I/O能力不高，严重影响CPU的利用率。
• 程序中断方式:与程序控制方式相比，中断方式因为CPU无需等待而提高了传输请求的响应速度。
• DMA方式:DMA方式是为了在主存与外设之间实现高速、批量数据交换而设置的。DMA方式比程序控制方式与中断方式都高效 全程不需要CPU参与，下达执行指令-指令完成后发出中断信号
• 通道方式
• I/O处理机

❗❗自上而下效率越来越高

虚设备与SPOOLING技术

SPOOLing是关于慢速字符设备如何与计算机主机交换信息的一种技术通常称为“假脱机技术”。!SPOOLing技术通过磁盘实现，在磁盘上建立一个输入井和一个输出井，输入井用于存放用户提交的打印作业，输出井用于存放打印输出的打印作业。

第 3 章 数据库

数据库模式

三级模式-两层映射

（视图级）外模式 又叫逻辑模式
       映|射
         v
（表级）概念模式 又叫 模式
       映|射
         v
（文件级）内模式 又叫存储模式

两层映射的好处，数据和程序分离。

E-R模型

实体：矩形 属性：椭圆形 联系：菱形 弱实体：某种实体的特殊化， 矩形带两竖 特殊化：

集成的方法

• 多个局部E-R图一次集成。
• 逐步集成，用累加的方式一次集成两个局部E-R。

集成产生的冲突及解决办法

• 属性冲突:包括属性域冲突和属性取值冲突。
• 命名冲突:包括同名异义和异名同义。
• 结构冲突:包括同一对象在不同应用中具有不同的抽象，以及同一实体在不同局部E-R图中所包含的属性个数和属性排列次序不完全相同。

ER模型转关系模式

一个实体型转换为一个关系模式

• 1:1联系：每个实体转为一个关系模式，中间的联系可以转为单独的联系模式，也可以合并到任意一端。即最少转为2个联系
• 1:n联系：每个实体转为一个关系模式，列如员工与部门的关系，联系只能合并到n端。即最少转为2个联系
• m:n联系：每个实体转为一个关系模式，列如学生与课程的关系，联系也必须转为一个实体（关键字为各实体关键字的集合）。即最少转为3个联系。
  例题

  在数据库逻辑结构的设计中，将E-R模型转换为关系模型应遵循相关原则。对于三个不同实体集和它们之间的多对多联系m:n:p,最少可转换为 个关系模式。

  A. 2

  B.3

  C.4 √

  D.5

关系代数

• 并
• 交
• 差
• 笛卡尔积
• 投影
• 选择
• 联结

关系S1

关系S2

S1 ∩ S2 （交）

S1 - S2 （差） ！ 特别注意顺序

S1 ∪ S2 （并） ！ 去除重复属性值

S1 × S2 （笛卡尔积）

π(Sno, Sname) (S1) （投影）

σ(Sno=No0003) (S1) （选择）

S1 ⋈ S2 （自然连接）

规范化理论

函数依赖

设R(U)是属性U上的一个关系模式，X和Y是U的子集，r为R的任一关系，如果对于r中的任意两个元组u，v，只要有u[X]=v[X]，就有u[Y]=v[Y]，则称X函数决定Y，或称Y函数依赖于X，记为X->Y。

价值与用途

非规范化的关系模式，可能存在的问题包括:数据冗余、更新异常、插入异常、删除异常

键

候选键（Candidate Key）： 候选键是能唯一标识元组且无冗余的属性集合。 可能有多个候选键。

主键（Primary Key）： 从候选键中任选一个作为主键。 主键用于唯一标识表中的每一行数据。

外键（Foreign Key）： 外键是另一个关系的主键，用于建立两个表之间的关联。

求候选键

图示法求候选键

1、将关系的函数依赖关系，用“有向图”的方式表示.

2、找出入度为0的属性，并以该属性集合为起点，尝试遍历有向图，若能正常遍历图中所有结点，则该属性集即为关系模式的候选键.

3、若入度为0的属性集不能遍历图中所有结点，则需要尝试性的将一些中间结点(既有入度，也有出度的结点)并入入度为0的属性集中，直至该集合能遍历所有结点，集合为候选键。

主属性与非主属性

定义：组成候选码的属性就是主属性，其他的就是非主属性

范式

• 第一范式(1NF):在关系模式R中，当且仅当所有域只包含原子值，即每个分量都是不可再分的数据项，则称R是第一范式。
• 第二范式(2NF):当且仅当R是1NF，且每一个非主属性完全依赖主键(不存在部分依赖)时，则称R是第二范式。
• 第三范式(3NF):当且仅当R是1NF，且E中没有非主属性传递依赖于码时，则称R是第三范式。
• BC范式(BCNF):设R是一个关系模式，F是它的依赖集，R属于BCNF当且仅当其F中每个依赖的决定因素必定包含R的某个候选码。

从上到下逐步优化以解决插入异常，删除一场，数据冗余。

flowchart TD A[1NF] --消除非主属性对候选键的部分依赖--> B[2NF] B --消除非主属性对候选键的传递依赖--> C[3NF] C --消除主属性对候选键的传递依赖--> D[BCNF] A --> E E[属性值都是不可分的原子值]

模式分解

保持函数依赖分解

设数据库模式p={R1，R2，…，Rk}是关系模式R的一个分解，F是R上的函数依赖集，p中每个模式Ri上的FD集是Fi。如果(F1，F2，…，Fk)与F是等价的(即相互逻辑蕴涵)，那么称分解p保持FD

无损分解

什么是有损，什么又是无损? 有损:不能还原。无损:可以还原，

无损联接分解

指将一个关系模式分解成若干个关系模式后，通过自然联接和投影等运算仍能还原到原来的关系模式

并发控制

封锁协议

• 一级封锁协议。事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。可防止丢失修改
• 二级封锁协议。一级封锁协议加上事务T在读取数据R之前先对其加S锁，读完后即可释放S锁。可防止丢失修改，还可防止读“脏”数据
• 三级封锁协议。一级封锁协议加上事务T在读取数据R之前先对其加S锁，直到事务结束才释放。可防止丢失修改、防止读“脏”数据与防止数据重复读
• 两段锁协议。可串行化的。可能发生死锁

数据库完整性约束

• 实体完整性约束：主键约束
• 参照完整性约束：外键约束
• 用户自定义完整性约束

数据库安全

数据备份

• 冷备份也称为静态备份，是将数据库正常关闭，在停止状态下，将数据库的文件全部备份(复制)下来。
• 热备份也称为动态备份，是利用备份软件，在数据库正常运行的状态下，将数据库中的数据文件备份出来。

• 完全备份:备份所有数据
• 差量备份:仅备份上一次完全备份之后变化的数据
• 增量备份:备份上一次备份之后变化的数据

1. 静态海量转储:在系统中无运行事务时进行，每次转储全部数据库。
2. 静态增量转储:在系统中无运行事务时进行，每次只转储上一次转储后更新过的数据。
3. 动态海量转储:转储期间允许对数据库进行存取或修改，每次转储全部数据库。
4. 动态增量转储:转储期间允许对数据库进行存取或修改，每次只转储上一次转储后更新过的数据。

日志文件:事务日志是针对数据库改变所做的记录，它可以记录针对数据库的任何操作，并将记录结果保存在独立的文件中

数据库故障与恢复

反规范化

由于规范化会使表不断的拆分，从而导致数据表过多。这样虽然减少了数据冗余，提高了增、删、改的速度，但会增加查询的工作量。系统需要进行多次连接，才能进行查询操作，使得系统效率大大下降

大数据

第 4 章 计算机网络

OSI/RM七层模型

网络技术标准与协议

TCP/IP协议:Internet，可扩展，可靠，应用最广，牺牲速度和效率

IPX/SPX协议:NOVELL，路由，大型企业网

NETBEUI协议:IBM，非路由，快速