二、综合应用题设主存容量为1MB,Cache容量为16KB,每字块有16个字,每个字32位。1. 若Cache采用直接相联映像,求出主存地址字段中各段的位数。
因为每字块有16个字,每字32位=4字节,所以字块中含有16×4=64字节=26个字节,则块内地址的位数b=6。而Cache容量为16KB,所以Cache中含有16K×8/(16×32)=256=28个字块,则块号数c=8。
主存容量为1MB=220字节,则主存地址总位数为20,所以主存区号位数t=20-6-8=6。
2. 若Cache采用四路组相联映像,求出主存地址字段中各段的位数。
若Cache采用四路组相联映像:
因为每字块有16个字,每字32位=4字节,所以字块中含有16×4=64字节=26个字节,则块内地址的位数b=6。而Cache容量为16KB,所以Cache中含有16K×8/(16×32)=256个字块,每组含有4个字块,所以一共有256/4=64=26组,则组地址位数q=6。
主存容量为1MB=220字节,则主存地址总位数为20,主存区各段位数t=20-6-6=8。
3. 采用微程序控制器的某计算机在微程序级采用两级流水线,即取第i+1条微指令与执行第i条微指令同时进行。假设微指令的执行时间需要40ns,问:
(1)控制存储器CM选用读出时间为30ns的ROM,在这种情况下微周期为多少?并画出微指令执行时序图。
(2)若控制存储器CM选用读出时间为50ns的ROM,在这种情况下微周期又为多少?并画出微指令执行时序图。
(1)取第i+1条微指令与执行第i条微指令同时进行,取微指令的读出时间为30ns,而微指令的执行时间需要40ns,这种情况下微周期取最长的时间,即40ns。
微指令执行时序图如下图(a)所示。
(2)若控制存储器CM选用读出时间为50ns的ROM,这种情况下微周期需取50ns。微指令执行时序图如下图(b)所示。
微指令执行时序图
4. 设有8个进程M1,M2,…,M8,它们有如下图所示的优先关系,试用P、V操作实现这些进程间的同步。
8个进程的优先关系
这是进程之间的同步问题。M2、M3和M4必须在接收到M1的消息后才能运行。同理,M6必须在M2和M3之后运行,M7必须在M4和M5之后运行,M8必须在M3和M7之后运行。如何保证呢?需设置相应的信号量来保证:S12、S13、S14分别用来制约M2、M3和M4的运行;S26、S36用来制约M6的运行;S47、S57用来制约M7的运行;S38、S78用来制约M8的运行。各进程的制约关系如下:
用容量为L×K的动态RAM芯片,构成容量为M×N的存储器。问:5. 需要多少块存储芯片?
因为存储器的容量为M×N,存储芯片的容量为L×K,所以需要的存储芯片数量为[(M×N)/(L×K)](片)。
6. 存储器共有多少个片选信号,如何来实现,需要几位译码?
这个存储器使用了字和位同时扩展。共有M/L组存储芯片,需要M/L个片选信号。月选信号由译码器产生,需要?log2(M/L)?位地址参与译码。
7. 若采用自动刷新模式,刷新计数器的最大值是多少?
画出这个存储器的逻辑框图。
在存储器中所有芯片同时被刷新,在考虑刷新问题时,应当从单个芯片的存储容量着手。在本题中动态RAM的内部结构应该是一个的方阵,刷新通常是一行一行进行的,每一行中各记忆单元是同时被刷新的。
存储器的逻辑框图如下图所示。
存储器逻辑框图
多个进程共享一个文件,其中只读文件的称为读者,只写文件的称为写者。读者可以同时读,但写者只能独立写。8. 说明进程问的相互制约关系,应设置哪些信号量?
进程间的相互制约关系有三类:
一是读者之间允许同时读;
二是读者与写者之间须互斥;
三是写者之间须互斥。
为了解决读者、写者之间的同步,应设置两个信号量和一个共享变量;读互斥信号量rmutex,用于使读者互斥地访问共享变量count。其初值为1;写互斥信号量wmutex,用于实现写者与读者的互斥及写者与写者的互斥,其初值为1;共享变量count,用于记录当前正在读文件的读者数目,初值为0。
9. 用P、V操作写出其同步算法。
进程间的控制算法如下所示:
int rmutex=1;
int wmutex=1;
int count=0;
main()
{
cobegin
reader();
writer();
coend
}
reader()
{
while(1)
{
P(rmutex);
if(count==0)P(wmutex);//当第一个读者读文件时,阻止写
count++;
V(rmutex);
读文件;
P(rmutex);
count--;
if(count==0)V(wmutex);//当最后一个读者读文件时,允许写
V(rmutex);
}
}
writer()
{
while(1)
{
P(wmutex);
写文件;
V(wmutex);
}
}
10. 修改上述的同步算法。使得它对写者优先,即一旦有写者到达,后续的读者必须等待。而无论是否有读者在读文件。
为了提高写者的优先级,增加一个信号量S,用于在写进程到达后封锁后续的读者。其控制流程如下:
int rmutex=1;
int wmutex=1;
int count=0;
int s=1;
main()
{
cobegin
reader();
writer();
coend
}
reader()
{
while(1)
{
P(s);
P(rmutex);
if(count==0)P(wmutex);//当第一个读者读文件时,阻止写
count++;
V(rmutex);
V(s);
读文件;
P(rmutex);
count--;
if(count==0)V(wmutex);//当最后一个读者读文件时,允许写
V(rmutex);
}
}
writer()
{
while(1)
{
P(s);
P(wmutex);
写文件;
V(wmutex);
V(s);
}
}
11. 假定有一组作业(或进程),它们提交时间及要求运行的时间如下表所示(单位为小时,并以十进制计)。
作业提交时间和运行时间表 如果采用最短作业(或进程)优先调度算法,计算出该组作业的平均周转时间T=1.725和平均带权周转时间W=6.875。这个结果对吗,为什么?
不对。理由如下:
采用最短作业(或进程)优先调度算法,则作业的执行顺序是1、3、4、2。
(1)作业i的周转时间Ti=Tei-Tsi,其中,Tei为作业i的完成时间,Tsi为作业i的提交时间。
平均周转时间T,是指多个作业的周转时间的平均值。所以,T=(2.0+1.1+0.8+2.3)/4=1.55。
(2)带权周转时间Wi=Ti/Tri,其中,Ti为作业i的周转时间,Tri为作业i的实际运行时间。
平均带权周转时间W=(2.0/2.0+1.1/0.1+0.8/0.2+2.3/0.5)/4=5.15。
12. 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中,写出计算该算术表达式值的算法。
以二叉树表示算术表达式,根结点用于存储运算符。若能先分别求出左子树和右子树表示的子表达式的值,最后就可以根据根结点的运算符的要求,计算出表达式的最后结果。