考研真题

假定题44给出的计算机M采用二级分页虚拟存储管理方式，虚拟地址格式如下：

请针对题43的函数f1和题44中的机器指令代码，回答下列问题。

（1）函数f1的机器指令代码占多少页？

（2）取第1条指令(push ebp)时，若在进行地址变换的过程中需要访问内存中的页目录和页表，则会分别访问它们各自的第几个表项(编号从0开始)？

（3）M的I/O采用中断控制方式。若进程P在调用f1之前通过scanf( )获取n的值，则在执行scanf( )的过程中，进程P的状态会如何变化?CPU是否会进入内核态？

答：

（1）函数f1的代码段中所有指令的虚拟地址的高20位相同，因此f1的机器指令代码在同一页中，仅占用1页。（1分）页目录号用于寻找页目录的表项，该表项包含页表的位置。页表索引用于寻找页表的表项，该表项包含页的位置。

（2）push ebp指令的虚拟地址的最高10位（页目录号）为 00 0000 0001，中间10位（页表索引）为00 0000 0001，所以，取该指令时访问了页目录的第1个表项，（1分）在对应的页表中访问了第1个表项。（1分）

（3）在执行scanf( )的过程中，进程P因等待输入而从执行态变为阻塞态。(1分)输入结束时，P被中断处理程序唤醒，变为就绪态。(1分)P被调度程序调度，变为运行态。(1分)CPU状态会从用户态变为内核态。(1分)

某进程中有3个并发执行的线程thread1、thread2和thread3，其伪代码如下所示。

//复数的结构类型定义
typedef struct
{
    float a;
    float b;
} cnum;
cnum x, y, z; //全局变量
 
//计算两个复数之和
cnum add(cnum p, cnum q)
{
    cnum s;
    s.a = p.a+q.a;
    s.b = p.b+q.b;
    return s;
}

thread1
{
    cnum w;
    w = add(x, y);
    …
}
 
thread2
{
    cnum w;
    w = add(y, z),
    …
}

thread3
{
    cnum w;
    w.a = 1;
    w.b = 1;
    z = add(z, w);
    y = add(y, w);
    …
}

请添加必要的信号量和P、V(或wait( )、signal( ))操作，要求确保线程互斥访问临界资源，并且最大程度地并发执行。

答：

先找出线程对在各个变量上的互斥、并发关系。如果是一读一写或两个都是写，那么这就是互斥关系。每一个互斥关系都需要一个信号量进行调节。

semaphore mutex_y1=1；//mutex_y1用于thread1与thread3对变量y的互斥访问。(1分)

semaphore mutex_y2=1；//mutex_y2用于thread2与thread3对变量y的互斥访问。(1分)

semaphore mutex_z=1； //mutex_z用于变量z的互斥访问。(1分)

互斥代码如下：(5分)

甲乙双方均采用后退N帧协议(GBN)进行持续的双向数据传输，且双方始终采用捎带确认，帧长均为1000B。Sx, y和Rx, y分别表示甲方和乙方发送的数据帧，其中x是发送序号，y是确认序号(表示希望接收对方的下一帧序号)；数据帧的发送序号和确认序号字段均为3比特。信道传输速率为100Mbps，RTT=0.96ms。下图给出丁甲方发送数据帧和接收数据帧的两种场景，其中t0为初始时刻，此时甲方的发送和确认字号均为0，t1时刻甲方有足够多的数据待发送。

请回答下列问题。

（1）对于图(a)，t0时刻到t1时刻期间，甲方可以断定乙方已正确接收的数据帧数是多少?正确接收的是哪几个帧(请用Sx, y形式给出)?

（2）对于图(a)，从t1时刻起，甲方在不出现超时且未收到乙方新的数据帧之前，最多还可以发送多少个数据帧?其中第一个帧和最后一个帧分别是哪个(请用Sx, y形式给出)?

（3）对于图(b)，从t1时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，需要重发多少个数据帧?重发的第一个帧是哪个(请用Sx, y形式给出)?

（4）甲方可以达到的最大信道利用率是多少?

答：

（1）t0时刻到t1时刻期间，甲方可以断定乙方已正确接收了3个数据帧，(1分)分别是S0,0、S1,0、S2,0。(1分)R3,3说明乙发送的数据帧确认号是3，即希望甲发送序号3的数据帧，说明乙已经接收了序号为 0~2的数据帧。

（2）从t1时刻起，甲方最多还可以发送5个数据帧，(1分)其中第一个帧是S5,2，(1分)最后一个数据帧是S1,2。(1分)发送序号3位，有8个序号。在GBN协议中，序号个数>=发送窗口+1，所以这里发送窗口最大为7。此时已发送了S3,0 和 S4,1，所以最多还可以发送5个帧。

（3）甲方需要重发3个数据帧（1分），重发的第一个帧是S2,3。(1分）在GBN协议中，接收方发送了N帧后，检测出错，则需要发送出错帧及其之后的帧。S2,0超时，所以重发的第一帧是S2。已收到乙的R2帧，所以确认号应为3。

（4）甲方可以达到的最大信道利用率是：

U=发送数据的时间/从开始发送第一帧到收到第一个确认帧的时间 = N * Td /(Td + RTT + Ta)。

U是信道利用率，N是发送窗口的最大值，Td是发送一数据帧的时间，RTT是往返时间，Ta是发送一确认帧的时间。这里采用捎带确认，Td=Ta。

2023 年 10 月 26 日，神舟十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导子工程，以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图G 采用邻接矩阵存储，类型定义如下。

typedef struct //图的类型定义
{
int numVertices, numEdges;//图的顶点数和有向边数
char VerticesList[MAXV];//顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV];//邻接矩阵
}MGraph;

请设计算法

int uniquely(MGraph G)

，判定G 是否存在唯一的拓扑序列，若是，则返回1，否则返回 0。要求如下。

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。

将关键字序列 20, 3, 11, 18, 9, 14, 7 依次存储到初始为空、长度为 11 的散列表HT 中，散列函数H(key) = (key×3)%11。H(key)计算出的初始散列地址为H0，发生冲突时探查地址序列是H1 , H2 , H3 , …，其中，Hk =(H0 + k2)%11，k = 1, 2, 3, …。

请回答下列问题。

（1）画出所构造的HT，并计算HT 的装填因子。

（2）给出在HT 中查找关键字 14 的关键字比较序列。

（3）在HT 中查找关键字 8，确认查找失败时的散列地址是多少？

假定计算机M 字长为 32 位，按字节编址，采用 32 位定长指令字，指令add、slli 和 lw 的格式、编码和功能说明如题 43 图（a）所示。

其中，R[x]表示通用寄存器x 的内容，M[x]表示地址为x 的存储单元内容，shamt 为移位位数，imm 为补码表示的偏移量。题 43 图（b）给出了计算机M 的部分数据通路及其控制信号（用带箭头虚线表示），其中，A 和B 分别表示从通用寄存器rs1和rs2 中读出的内容；IR[31:20]表示指存器中的高 12 位；控制信号Ext 为 0、1 时扩展器分别实现零扩展、符号扩展，ALUctr 为 000、001、010 时ALU 分别实现加、减、逻辑左移运算。

请回答下列问题。

（1）计算机M 最多有多少个通用寄存器？为什么shamt 字段占 5 位？

（2）执行add 指令时，控制信号ALUBsrc 的取值应是什么？若rs1和rs2 寄存器内容分别是8765 4321H 和 9876 5432H，则add 指令执行后，ALU 输出端F、OF 和CF 的结果分别是什么？若该add 指令处理的是无符号整数，则应根据哪个标志判断是否溢出？

（3）执行slli 指令时，控制信号Ext 的取值可以是 0 也可以是 1，为什么？

（4）执行lw 指令时，控制信号Ext、ALUctr 的取值分别是什么？

（5）若一条指令的机器码是A040A103H，则该指令一定是lw 指令，为什么？若执行该指令时，R[01H]=FFFF A2D0H，则所读取数据的存储地址是什么？

对于题 43 中的计算机M，C 语言程序P 包含的语句“sum+=a[i];”在M 中对应的指令序列S 如下。

slli r4, r2, 2  //R[r4]←R[r2]<<2
add r4, r3, r4  //R[r4]←R[r3]+R[r4]
lw r5, 0(r4)    //R[r5]←M[R[r4]+0]
add r1, r1, r5  //R[r1]←R[r1]+R[r5]

已知变量i、sum 和数组a 都为int 型，通用寄存器r1~r5 的编号为 01H～05H。请回答下列问题。

（1）根据指令序列S 中每条指令的功能，写出存放数组a 的首地址、变量i 和sum 的通用寄存器编号。

（2）已知M 为小端方式计算机，采用页式存储管理方式，页大小为 4KB。若执行到指令序列S中第 1 条指令时，i = 5且r1和r3 的内容分别为 0000 1332H 和 0013DFF0H，从地址 0013DFF0H 开始的存储单元内容如题 44 图所示，则执行“sum+=a[i];”语句后，a[i]的地址、a[i]和sum 的机器数分别是什么（用十六进制表示）？a[i]所在页的页号是多少？此次执行中，数组a至少存放在几页中？

（3）指令“slli r4, r2, 2”的机器码是什么（用十六进制表示）？若数组a 改为short 类型，则指令序列S 中slli 指令的汇编形式应是什么？

某计算机按字节编址，采用页式虚拟存储管理方式，虚拟地址和物理地址的长度均为 32位，页表项的大小为 4 字节，页大小为 4MB，虚拟地址结构如下。

进程P 的页表起始虚拟地址为B8C0 0000H，被装载到从物理地址 6540 0000H 开始的连续主存空间中。

请回答下列问题，要求答案用十六进制表示。

（1）若CPU 在执行进程P 的过程中，访问虚拟地址 1234 5678H 时发生了缺页异常，经过缺页异常处理和MMU 地址转换后得到的物理地址是BAB4 5678H，在此次缺页异常处理过程中，需要为所缺页分配页框并更新相应的页表项，则该页表项的虚拟地址和物理地址分别是什么？该页表项中的页框号更新后的值是什么？

（2）进程P 的页表所在页的页号是什么？该页对应的页表项的虚拟地址是什么？该页表项中的页框号是什么？

计算机系统中的进程之间往往需要相互协作以完成一个任务。在某网络系统中，缓冲区B 用于存放一个数据分组，对B 的操作有C1、C2和C3。C1 将一个数据分组写入B 中，C2从B 中读出一个数据分组，C3对B 中的数据分组进行修改。要求B 为空时才能执行C1，B 非空时才能执行C2和C3。

（1）假设进程P1和P2 均需要执行C1，实现C1 的代码是否为临界区？为什么？

（2）假设B 初始为空，进程P1执行C1 一次，进程P2执行C2 一次。请定义尽可能少的信号量，并用wait()、signal()操作描述进程P1和P2 之间的同步或互斥关系，说明所用信号量的作用及其初值。

（3）假设B 初始不为空，进程P1和P2 各执行C3 一次。请定义尽可能少的信号量，并用wait()、signal()操作描述进程P1和P2 之间的同步或互斥关系，说明所用信号量的作用及其初值。

网络空间是继陆海空天之后的“第五疆域”，网络技术是网络疆域建设与治理的基础。路由算法与协议是网络核心技术之一，对其准确认知、合理选择与应用，对于网络建设十分重要。假设现有互联网中的 4 个自治系统如题 47 图所示。其中，AS1 运行内部网关协议RIP；AS3 规模较小，自治系统内任意两个主机间通信，经过路由器数量不超过 15 个；AS4 规模较大，自治系统内任意两个主机间通信，经过路由器数量可能超过 20 个。

请回答下列问题。

（1）若仅有RIP 和OSPF 内部网关协议供选择，则AS4 应该选择哪个协议？

（2）若 AS3 中的某主机向本自治系统内另一主机发送 1 个 IP 分组，为确保该 IP 分组能够被正常接收，则该IP 分组的初始TTL 值应该至少设置为多少？

（3）假设AS1 中的路由器同一时刻启动，启动后立即构建并交换初始距离向量，之后，每隔 30s交换一次最新的距离向量。则从交换初始距离向量时刻算起，R11~R16 路由器均获到达网络210.2.4.0/24 的正确路由，至少需多长时间？

（4）R44向R13 通告到达网络 136.5.16.0/20 路由时，由BGP 协议哪类会话完成？通过哪个BGP报文通告？R13 通过BGP 协议的哪类会话将该网络可达性信息通告给R14和R15？

（5）若 R14 和 R15 均收到分别由 R11、R12、R13 通告的到达网络 136.5.16.0/20 的可达性信息为：

则在无策略约束情况下，R14和R15 更新路由表后，各自路由表中到达网络 136.5.16.0/20 路由的下一跳分别是什么（用路由器名称表示）？

（本题 13 分）设有两个长度均为 n 的一维整型数组 A 和 res，对数组 A 中的每个元素 A [i]，计算 A [i] 与 A [j]（0≤i≤j≤n-1）乘积的最大值，并将其保存到 res [i] 中。例如，若 A [ ]={1,4,-9,6}，则得到 res [ ]={6,24,81,36}。现给定数组 A，请设计一个时间和空间上尽可能高效的算法 calMulMax，求 res 中各元素的值。函数原型为：void calMulMax (int A [ ],int res [ ],int n)。要求如下：

（1）给出算法的基本设计思想。（4 分）

（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。（7 分）

（3）说明你所设计算法的时间复杂度和空间复杂度。（2 分）

（本题 10 分）某工程包含 12 个活动，使用下图所示的 AOE 网描述，图中各边上标注了活动及其持续时间。请回答下列问题（活动均用活动名表示）：

（1）完成该工程的最短时间是多少？哪些活动是关键活动？（3 分）

（2）若以最短时间完成工程，则与活动 e 同时进行的活动可能有哪些？（3 分）

（3）时间余量最大的活动是哪个？其时间余量是多少？（2 分）

（4）假设工程从时刻 0 启动，因某种原因，活动 b 在时刻 6 开始。为了保证工程不延期，在其他活动持续时间均不变的情况下，b 的持续时间最多是多少？若不改变 b 的持续时间，则压缩哪个活动的持续时间也能保证工程不延期？（2 分）

（本题 12 分）现有 C 语言程序 P 的部分代码如图所示。假定运行程序 P 的计算机 M 字长为 32 位，按字节编址，数据 Cache 的数据区大小为 32KB，采用 8 路组相联映射方式，主存块大小为 64B，Cache 的命中时间为 2 个时钟周期，缺失损失为 200 个时钟周期；采用页式虚拟存储管理方式，页大小为 4KB。数组 d 的起始虚拟地址 VA₃₁~VA₀为 01800020H。请回答下列问题：

（1）主存地址中 Cache 组号字段和块内地址字段分别占几位？虚拟地址中哪些位可作为 Cache 索引？（3 分）

（2）d [100] 的虚拟地址为多少？d [100] 所在主存块对应的 Cache 组号是多少？（2 分）

（3）假定执行 for 语句时对应代码已在 Cache，变量 i 和 x 已装入寄存器，数组 d 已调入主存但不在 Cache，则 d [0] 在其所在主存块内的偏移量是多少（用十六进制表示）？for 语句执行过程中，访问数组 d 的 Cache 缺失率和数组元素的平均访问时间分别是多少（Cache 缺失率的计算结果要求用百分比表示，保留两位小数）？（5 分）

（4）数组 d 分布在几个页中？若执行 for 语句时对应代码已在主存，但数组 d 还未调入主存，则执行 for 语句过程中，访问数组 d 所引起的缺页次数是多少？（2 分）

（本题 11 分）对于题 43 中计算机 M 和程序 P，假定 P 的部分机器级代码如（a）图所示，其中，R0~R4 为通用寄存器，SEXT 表示按符号扩展；M 中补码除法器逻辑结构如（b）图所示。请回答下列问题：

（1）若执行题 （a）图中 idiv 指令的除运算时，d [i]=0x87654321、x=0xff，则补码除法器中寄存器 R、Q 和 Y 的初始内容分别是什么（用十六进制表示）？题 （b）图中哪个部件包含计数器？在补码除法器执行过程中，由 ALUop 所控制的 ALU 运算有哪几种？（6 分）

（2）假设 idiv 指令执行过程中会检测并触发除法异常，则执行 idiv 指令时，哪些情况下会发生除法异常（要求给出此时 d [i] 和 x 的十六进制表示机器数）？发生除法异常时，在异常响应过程中 CPU 需要完成哪些操作？（5 分）

（本题 7 分）甲、乙、丙三人一起植树，甲负责挖树坑，乙负责将树苗放入树坑中并填土，丙负责为新种的树苗浇水。植树的步骤依次为：挖树坑、放树苗、填土和浇水。现有铁锹和水桶各 1 个，铁锹用于挖树坑和填土，水桶用于浇水。当树坑的数量小于 3 时，甲才可以挖树坑。假设初始时树坑的数量为 0，铁锹和水桶均可用。请定义尽可能少的信号量，用 wait ()、signal () 操作描述植树过程中三人之间的同步或互斥关系，并说明所用信号量的作用及其初值。

（本题 8 分）某系统中进程的虚拟地址空间包括内核区、用户栈、运行时堆、可读写数据段、只读代码段等区域，其布局如图所示，图中阴影部分表示未占用区域。现有 C 语言程序的部分代码如下：

char*ptr;
void main()
{
int length;
ptr=(char *)malloc(100);
scanf("%s", ptr);
length=strlen(ptr);
printf("length=%d\n", length);
free(ptr);
}

请回答下列问题：

（1）上述程序执行时，其进程控制块位于哪个区域？执行 scanf () 等待键盘输入时，该进程处于什么状态？（2 分）

（2）main () 函数的代码位于哪个区域？其直接调用的哪些函数的功能需要通过执行驱动程序实现？（3 分）

（3）变量 ptr 被分配在哪个区域？若变量 length 没有被分配在寄存器中，则会被分配在哪个区域？ptr 指向的字符串位于哪个区域？（3 分）

（本题 9 分）某公司在承建国家重大工程项目时，工程部需要较长时间驻扎在偏远山区，工程部网络需要连接公司总部网络。假设综合考虑方案的技术可行性、安全性与经济成本等因素后，决定租用我国自主建设的天通一号卫星通信链路，连接工程部网络的路由器 R1 和公司总部网络的路由器 R2，如图所示。S1 和 S2 为千兆以太网交换机；TR1 和 TR2 是卫星信号地面收发设备，实现全双工调制解调。天通一号卫星轨道高度是 36000km，电磁波信号传播速度为 300000km/s。租用的卫星链路为 R1 和 R2 之间提供对称全双工信道，每个方向的数据传输速率为 200kb/s。请回答下列问题：

（1）若忽略卫星信号中继以及 TR1 和 TR2 调制解调的时间开销，则 R1 到 R2 之间卫星链路的单向传播时延是多少？主机 H 向总部服务器传输数据时可以达到的最大吞吐量是多少？若忽略各层协议数据包的首部开销以及以太网内的传播时延，则主机 H 向总部服务器上传一个 4000B 大小的工程进度报告文件，至少需要多长时间？（3 分）

（2）现需要基于 GBN 滑动窗口协议为卫星链路设计单向可靠的数据链路层协议 SLP，支持 R1 向 R2 发送数据，SLP 数据帧长为 1500B，忽略 ACK 帧长度。若要求 SLP 的单向信道利用率不低于 80%，则 SLP 的发送窗口至少为多少？SLP 帧的序号字段至少需要多少位？（3 分）

（3）若公司总部为工程部网络分配的 IP 地址空间是 10.10.10.0/24，工程部进一步将该 IP 地址空间分配给 3 个子网，其中生活区子网可分配 IP 地址数不少于 120 个，作业区子网和管理区子网可分配 IP 地址数均不少于 60 个，且主机 H 已正确配置了 IP 地址，则作业区子网、管理区子网和生活区子网的子网地址分别是什么（给出 CIDR 地址形式）？（3 分）