CRC循环冗余校验

真题：循环冗余校验码（Cyclic Redundancy Check,CRC)是数据通信领域中最常用的一种差错校验码，该校验方法中，使用多项式除法（模2除法）运算后的余数为校验字段。若数据信息为n位，则将其左移k位后，被长度为k+1位的生成多项式相除，所得的k位余数即构成k个校验位，构成n+k位编码。若数据信息为1100,生成多项式为x3+X+1(即1011)，则CRC编码是（）。

解析：CRC循环校验码的编码流程为：

1. 在原始信息位后面添0，假设生成多项式的阶为r，则在原始信息位后添加r个0，本题中，G(x)阶为3，则在原始信息串后加3个0,得到的新串为1100000，作为被除数。
2. 由多项式得到除数，多项中x的幂指数存在的位置1，不存在的位置0。本题中，x的幂指数为0,1,3的变量都存在，而幂指数为2的不存在，因此得到串1011。
3. 生成CRC校验码，将前两步得出的被除数和除数进行模2除法运算（即不进位也不借位的除法运算），得到余数010。
4. 将原始信息位与余数连接起来得到：1100010。

海明码计算

真题：海明码是一种纠错码，其方法是为需要校验的数据位增加若干校验位，使得校验位的值决定于某些被校位的数据，当被校数据出错时，可根据校验位的值的变化找到出错位，从而纠正错误。对于32位的数据，至少需要加（）个校验位才能构成海明码。
以10位数据为例，其海明码表示为D9D8D7D6D5D4P4D3D2D1P3D0P2P1中，其中Di(0≤i≤9)表示数据位，Pj(1≤j≤4)表示校验位，数据位D9由P4、P3、P2进行校验（从右至左D9的位序为14，即等8+4+2，因此用第8位的P4、第4位的P3和第2位的P2校验），数据位D5由（）进行校验。

解析：

第一问：32位信息位至少要包含1、2、4、8、16这5个校验位才能构成海明码。

第二问：表格做题法

D5在第10位，10=8+2，所以D5由P4和P2校验。

补充知识：

流水线的时间计算

真题1：流水线的吞吐率是指流水线在单位时间里所完成的任务数或输出的结果数。设某流水线有5段，有1段的时间为2ns另外4段的每段时间为1ns,利用此流水线完成100个任务的吞吐率约为（）个／s.

解析1：流水线执行100个任务所需要的时间为：(2+1+1+1+1)+(100-1)*2=204ns。所以每秒吞
吐率为：(100/204)*109=490*10^6。注意：1秒=10^9纳秒。

真题2：假设磁盘块与缓冲区大小相同，每个盘块读入缓冲区的时间为15us，由缓冲区送至用户区的时间是5us，在用户区内系统对每块数据的处理时间为1us，若用户需要将大小为10个磁盘块的Docl文件逐块从磁盘读入缓冲区，并送至用户区进行处理，那么采用单缓冲区需要花费的时间为（）us；采用双缓冲区需要花费的时间为（）us。

解析2：单缓冲区：前两段要合并，是两段流水线，21+20*(10-1)=201
双缓冲区：标准三段流水线，21+15*(10-1)=156

补充知识：流水线时间计算
流水线周期：指令分成不同执行段，其中执行时间最长的段为流水线周期。
流水线执行时间：1条指令总执行时间+（总指令条数-1）*流水线周期。
流水线吞吐率计算：吞吐率即单位时间内执行的指令条数。公式：指令条数/流水线执行时间。
流水线的加速比计算：加速比即使用流水线后的效率提升度，即比不使用流水线快了多少倍，越高表明流水线效率越高，公式：不使用流水线执行时间/使用流水线执行时间。

存储系统

真题：地址编号从80000H到BFFFFH且按字节编址的内存容量（）KB，若用16K4bit的存储器芯片构成该内存，共需（）片

解析：

第一问：首先计算出地址段包含的存储空间数，为BFFFFH-80000H+1=40000H。按字节编制，即一个存储空间占一个字节，共40000H字节，不要硬算，要化简为的幕指数来算，即416^4 B，2^18 B。因为1KB=2^10B，所以内存容量为2^8，即256KB。

第二问：该存储芯片总容量为16K*0.5B=8KB，所以需要256KB/8KB=32片。

PV操作

真题：假设系统中有n个进程共享3台打印机，任一进程在任一时刻最多只能使用1台打印机。若用PV操作控制个进程使用打印机，则相应信号量S的取值范围为()。

解析：若S初始值为3，当n个进程同时执行时，需要执行n次P操作，这时信号量的值应为 3-n，所以信号量的变化范围为：-（n-3）~3。

补充知识：引起阻塞的原因：执行P操作（申请资源）

时间片到，进程应该进入就绪态；I/O完成进程应该是阻塞态到就绪态；V操作是释放资源，到一个进程释放资源，应该会唤醒另一个进程运行

P操作的定义：S:=S-1，若S>=0，则执行P操作的进程继续执行；若S<0，则将该进程设为阻塞状态（因为无可用资源），并将其插入阻塞队列。

V操作的定义：S:=S+1，若S>0，则执行V操作的进程继续执行；若S<=0，则从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续。

死锁资源计算

真题：某系统中有3个并发进程竞争资源R,每个进程都需要5个R,那么至少有()个R,才能保证系统不会发生死锁。
解析：每个进程需要5个R才能执行，则当每个进程都只有4个R时是死锁最坏的情况，即3*4=12个。资源是死锁发生的最大资源数，再加1就能保证不发生死锁，因此是13.

补充知识：系统内有个进程，每个进程都需要R个资源，那么其发生死锁的最大资源数为n*(R-1)。其不发生死锁的最小资源数为n*(R-1)+1。

分页存储

真题：某计算机系统页面大小为4K,若进程的页面变换表如下所示，逻辑地址为十六进制1D16H。该地
址经过变换后，其物理地址应为十六进制（）。

解析：页面大小为4K，即2^12，则页内偏移地址为12位，才能表示4K大小空间；由此，可知逻辑地址
1D16H的低12位D16H为偏移地址，高4位1为逻辑页号，在页表中对应物理块号3，因此物理地址
为3D16H。