计算机组成

计算机系统

硬件

处理器、存储器、总线、接口、外部设备等

软件

系统软件：操作系统、编译工具等

应用软件：办公软件、娱乐软件、信息系统软件等

硬件组成结构

冯诺依曼计算机

体系结构划分

计算机识别和工作的逻辑是：机器语言=>指令集=>微程序=>硬布线逻辑

上述指令集系统类型即不同指令集进行划分

CISC可以使用流水线，只是不适合

层次化存储体系

寄存器存取速度最快，大小一般为bit级别，常见64bit

内存：存储器类型为RAM，DRAM则是周期性刷新（RAM掉电数据会丢失，掉电数据不丢失的有：ROM、BIOS）

Cache：高速缓存

层次化存储体系目的：解决存储容量、价格、速度之间的矛盾

I/O数据传输方式

在cpu控制下数据交互：I/O<=>内存

DMA方式(直接内存存储器访问)：CPU只做初始化，后续所有控制，交给DMAC

操作系统

计算机硬件=>操作系统=>系统软件=>应用软件=>用户

操作系统类型

进程管理

概念

`PV`操作

信号量：是全局变量，表示资源数量。

信号量初值：最大表示没有任何操作的时候，资源的总数

信号量为负数表示欠有资源，绝对值即是排队进程数

PV成对存在，同一个信号量的PV成对，可以在不同进程里面成对

思考题：2，[-1,2]。解：初值是资源数，最大是资源总数，最小当两个人使用后，一人排队，故最小-1

前趋：箭头起始节点

后继：箭头指向节点

前驱关系：每个箭头表示一个前驱关系

起始进程：无前驱

终结进程：无后继

有后继V操作通知后继，有前驱P操作检查前驱

解：一共9个箭头，所以当存在9个前驱关系，关系中无P2到P1的关系，故C

答案：CA。解：根据起始判断P1两个前驱所以两个V操作通知后继，P2两个后继一个前驱,分别是两个

P操作检查前驱，一个V操作通知后继。故选C。并可推出信号量的位置

死锁

1. 资源数<5：必定死锁
1. 5<=资源数<13：可能死锁，可能正常（当且仅当某个进程一次性获得5个资源，才可能正常运行；不然就会出现每个进程占用的资源都不足以支持它们的运行，造成死锁）
1. 资源数>=13：不会死锁（在每个进程拿到4个资源的情况下，只需要加一个，就必定可以有序完成）

尚需资源数=最大需求数-已分配

如表，系统剩余25-6-4-7-6=2，故只有先分配给P3才能保证进程正常执行，系统处于安全状态

存储管理

页式存储

每页大小为4KB，则页内地址需要12位二进制来表示4096B（2^12）

逻辑地址：对于每页4KB大小而言，页号+12位二进制表示的页内地址

物理地址：物理块+页内地址（物理块通过页号可查，页内地址同上）

若是16进制（H）表示，那么一位16进制表示4位二进制，故4KB

根据局部性原理，访问位为1的页面尽量保留

在淘汰过程中

    1. 淘汰页面必定在内存中
    1. 优先淘汰访问位为0的页面
    1. 如果有多个访问位为0的可选页面，则考虑修改位为0

页大小4K，现访问十六进制的逻辑地址5148H，因为页大小4KB，故有12位二进制表示页地址，3位十六进制表示，即148表示页地址，5表示页号换算10进制还是5，查表物理块为3，故物理地址为3148H。

淘汰页首先需要存在内存中，再根据局部性原理，优先淘汰访问位为0，多个考虑修改位为0

去除12位页内地址后页号为0010即页号2，查表指向110补位，即物理地址：0110+页内地址

物理地址和虚拟地址页内地址是相同的，故CD明显错误

段式存储

1. 大小通常大于页
1. 段的逻辑地址，表示写法：（段号，段内偏移量）
1. 如果段内偏移量大于段长（非法段地址），逻辑地址转物理地址溢出

0段查表知段长为30K，故：

0段合法段地址（0，25K）

0段非法段地址（0，35K）

（段号，段内偏移量）

段内偏移量 <= 段长

段页式存储

对于一个完整编码来说

页内地址：[0-8] ，共占9个位，最多512个地址
页号：[9-13]，共占5个位，最多32页
段号：[14-15]，共占2个位，最多4段

A：段式 B：页式 C：段页式

磁盘管理

关键点

平均存取时间、优化分布、移臂调度序列、单缓冲区与双缓冲区（流水线技术）

存取时间

3：传输时间：磁头在对应扇区上移动的时候（数据读取–传输）

一块的时间：10x10+100+2

100块：（10x10+100+2）x100

理解：磁头是机械的处于一直旋转，与计算机在做的工作互不干扰

一个记录的旋转（数据传输）时间：33/11=3ms

题目得知每个记录处理时间：3ms

一个记录的处理时间=寻道时间+旋转延时+数据传输时间+处理时间

问1：除开第一个块处理时间式0+0+3+3，由于在处理时间中且是单缓冲区，一次只能进行一个处理，但是磁头依旧在旋转，故其余块的处理时间都是0+30+3+3（相当于延时1圈，即等待转过其余10个记录的时间，再转到自己，再处理）。

问2：若对存储优化后，即当R0处理完成后，接着处理的逻辑记录的R1。如此一次处理的时间就少去了旋转延迟，即相当于一个记录的处理时间=旋转时间+处理时间，故(0+0+3+3)x11

移臂调度算法

垂直寻道用到移臂调度算法，常见的有：

1. 先来先服务（`FCFS`）
1. 最短寻道时间优先（`SSTF`）：每次找离最近的序列
1. 扫描算法（`SCAN`）：电梯算法，由内向外，再由外向内
1. 循环扫描算法（`CSCAN`）：单方向扫描，只由内向外或只由外向内

1、2 会根据请求突然改变磁头运动方向，

3、4 不会受请求影响，固定方向

最短寻道时间优先计算时，每次需要与当前最新磁道位值比。

如上100=>90后，最近的就是58=>55=>39…

响应序列判断

优先考虑磁道–柱面号

如果一个磁道有多个请求（同时寻道两个相同磁道，即相同柱面号），则判断扇区：扇区号从小到大

文件系统

索引文件结构

索引类似目录、指针、地址项、磁盘块号…且会占用空间。如（地址项4B）

unix默认13个索引节点，假设数据块/索引块大小为1KB如下：

前10个索引节点是直接索引（0~9号页）[0,9] 共10个

第11个索引节点是一级间接索引表[10,265] 共256个

第12个索引节点是二级间接索引表，同时它又指向一个一级间接索引表[266,65801] 一共有65536个

第13个索引节点是三级间接索引表，[65802，16843017] 一共有256^3个

第一级间接索引表中的最大地址块

一共：1KB/4B=256

max: max-10+1=256 max=265

第二级间接索引表中的最大地址块

一共：256x256=65536

max: max-10-256+1=65536 max=265

第三级间接索引表中的最大地址块

一共：256x256x256=16777216

max: max-65802+1=16777216 max=16843017

0-5是直接索引，所以[0-5]含6个块

一级间接索引地址块个数：1KB/4B=256个，最大地址编号：max-6+1=256（运算个数需要+1）

通过计算得一级间接索引：地址号范围[7-261]

二级间接索引地址块个数：个数256x256，最大编号：max-262+1=256x256

通过计算得二级间接索引：地址号范围[262-65797] （下标从0开始，即一共有65798个块号）

故，逻辑块号为0是直接地址索引，260是一级间接索引，518是二级间接索引

可单个文件最大长度：6+256+256x256

记录文件方法

空闲区表法（空闲文件目录）、空闲链表法、位示图法、成组链接法

主要采用：位示图

0–空闲，1–占用

按字长分组

每个磁盘块的情况由1个bit进行记录（上图每个字[横行]由16个bit记录）

eg:如图，字长16bit，字的编号、位的编号、磁盘块的编号都是从0开始，那么第65号磁盘块放在几号字？几号bit位？

解：第65号在第66个处，即66/16=4…2。在第5个字，编号为4。bit位第2位，编号1

已知总容量大小，物理块大小

物理块个数：300GB/1MB=300x2^10

位示图bit位个数：300x2^10（一个物理块由一个bit位表示）

位示图字个数：300x2^10 / 32 = 300x32 = 9600 （此题一个字长为32bit）

思考：1023号物理块，在第31号字，31号bit位，置1（分配出是1，收回是0）