44.某16 位计算机中，带符号整数用补码表示，数据 Cache 和指令Cache 分离。题44表给出了指令系统中部分指令格式，其中Rs 和 Rd 表示寄存器，mem 表示存储单元地址，（x）表示寄存器x或存储单元x 的内容。
指令系统中部分指令格式
名称：指令的汇编格式/加法指令
加法指令：ADD Rs,Rd/(Rs)+(Rd)->Rd
算术/逻辑左移：SHR Rd/2*(Rd)>Rd
算术右移：SHR Rd/(Rd)2-Rd
取数指令：LOAD Rd,mem/(mem)->Rd
存数指令：STORE Rs, mem/(Rs)->mem
该计算机采用5段流水方式执行指令，各流水段分别是取指（IF）、译码/读寄存器（ID）、执行/计算有效地址（EX）、访问存储器（M）和结果写回寄存器（WB），流水线采用"按序发射，按序完成"方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题∶
1）若int 型变量x的值为-513，存放在寄存器R1中，则执行指令"SHR R1"后，R1的内容是多少?（用十六进制表示）
2）若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少?
3）若高级语言程序中某赋值语句为x=a+b，x、a 和b均为int 型变量，它们的存储单元地址分别表示为【x】、【a】和【b】。该语句对应的指令序列及其在指令流水线中的执行过程如下图所示。
则这4条指令执行过程中，I3的 ID 段和I4的IF 段被阻塞的原因各是什么?
4）若高级语言程序中某赋值语句为x=x*2+a，x和 a均为 unsigned int类型变量，它们的存储单元地址分别表示为[x]、[a]，则执行这条语句至少需要多少个时钟周期?要求模仿题 44 图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。
41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法∶
①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点;
② 选择离u最近且尚未在最短路径中的一个顶点v，加入最短路径中，修改当前顶点u=v;
③ 重复步骤②，直到u是目标顶点时为止。
请问上述方法能否求得最短路径?若该方法可行，请证明之;否则，请举例说明。
①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点;
② 选择离u最近且尚未在最短路径中的一个顶点v，加入最短路径中，修改当前顶点u=v;
③ 重复步骤②，直到u是目标顶点时为止。
请问上述方法能否求得最短路径?若该方法可行，请证明之;否则，请举例说明。
42. （5分）已知一个带有表头结点的单链表，结点结构为
Data/link
假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法;查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回1∶否则，只返回0。要求∶
1）描述算法的基本设计思想。
2）描述算法的详细实现步骤。
3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C++或 Java 语言实现），关键之处请给出简要注释。
Data/link
假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法;查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回1∶否则，只返回0。要求∶
1）描述算法的基本设计思想。
2）描述算法的详细实现步骤。
3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C++或 Java 语言实现），关键之处请给出简要注释。
43.（8分）某计算机的CPU主频为 500Mz，CPI为5（即执行每条指令平均需5个时钟周期）。假定某外设的数据传输率为 0.5MB/s，采用中断方式与主机进行数据传送，以 32 位为传输单位，对应的中断服务程序包含 18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。
1）在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少?
2）当该外设的数据传输率达到5MB/s 时，改用DMA 方式传送数据。假定每次 DMA传送块大小为 5000B，且DMA预处理和后处理的总开销为 500个时钟周期，则 CPU用于该外设 I/O 的时间占整个 CPU时间的百分比是多少（假设 DMA与CPU 之间没有访存冲突）?
1）在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少?
2）当该外设的数据传输率达到5MB/s 时，改用DMA 方式传送数据。假定每次 DMA传送块大小为 5000B，且DMA预处理和后处理的总开销为 500个时钟周期，则 CPU用于该外设 I/O 的时间占整个 CPU时间的百分比是多少（假设 DMA与CPU 之间没有访存冲突）?
44.（13 分）某计算机字长为16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效、为 0时表示无效。例如，控制信号MDRinE 为1表示允许数据从 DB打入 MDR，MDRin为1表示允许数据从内总线打入 MDR。假设 MAR 的输出一直处于使能状态。加法指令"ADD（R1），RO"的功能为（RO）+（R1））→（R1），即将R0中的数据与 R1的内容所指主存单元的数据相加，并将结果送入 R1的内容所指主存单元中保存。
下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号。请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。
时钟：功能/有效控制信号
C1：MAR←(PC)/PCout, MARin
C2：MDR←M(MDR) PC←(PC)+1/MemR, MDRinE, PC+1
C3：IR←(MDR)/MDRout, IRin
C4：指令译码/无
下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号。请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。
时钟：功能/有效控制信号
C1：MAR←(PC)/PCout, MARin
C2：MDR←M(MDR) PC←(PC)+1/MemR, MDRinE, PC+1
C3：IR←(MDR)/MDRout, IRin
C4：指令译码/无
45.（7分）三个进程P1、P2、P3互斥使用一个包含N（N>0）个单元的缓冲区。
P1每次用 produce（）生成一个正整数并用 putO）送入缓冲区某一空单元中;P2每次用 getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数;P3每次用 geteven（）从该缓冲区中取出一个偶数并用 counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义（要求用伪代码描述）。
P1每次用 produce（）生成一个正整数并用 putO）送入缓冲区某一空单元中;P2每次用 getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数;P3每次用 geteven（）从该缓冲区中取出一个偶数并用 counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义（要求用伪代码描述）。
