计算机软件技术基础复习题(1004)(1)(精)

6 5 p5 回答下列问题:

①简单叙述什么是银行家算法,为什么它可以避免产生死锁? ②该状态是安全状态吗?为什么?

③如果进程P3提出资源请求(1,2,2,1,能否立即给予满足?(要求给出计算过程、各资源矩阵的变化情况

①当某一进程申请一组资源时,要先测试系统是否安全?如果安全则可以分配,否则不予分配。

测试的方法是:是否能找到一个安全序列,保证在任一时刻系统所剩资源至少满足一个进程的最大需求。如能找到则系统安全,可以分配,否则系统不安全,不予分配。

②此时存在一个安全序列:P1-P4-P5-P2-P3,故系统是安全的。 ③若P3提出请求(1,2,2,1 因为(1,2,2,1<(2,3,5,6 (1,2,2,1<(1,6,2,2

故可假设将资源分配给P3,修改相应的数据结构,此时资源分配情况如下: AL=(0,4,0,1 0 0 3 2 p1 0 0 1 2 p1 1 0 0 0 p 2 1 7 5 0 p2

U = 2 5 7 5 p3 N= 1 1 3 5 p3 0 3 3 2 p4 0 6 5 2 p4 0 0 1 4 p5 0 6 5 6 p5

此时用安全性算法检查系统是否安全, 可用资源AL=(0,4,0,1已不能满足任何进程的需要,故系统处于不安全状态,故不能将资源分配给P3。

2、某计算机的存储系统由cache、主存和磁盘组成。在cache中访问一个字需20ns,把一个字从主存装入cache需60ns,把一个字从磁盘调入主存需12ns。Cache的命中率是0.9,主存的命中率是0.6。

问:此系统访问一个字的平均存取时间是多少?(以ns为单位

因为cache的命中率是0.9,所以90%的字的平均存取时间是0.9*20ns=18ns 因为主存的命中率是0.6,所以有0.6*0.1的数据要从主存装入cache,再从cache中存取,其平均存取时间是0.6*0.1*(60ns+20ns=4.8ns

有0.4*0.1的数据要从磁盘调入主存,再调入cache进行存取,其平均存取时间是0.4*0.1*(12ns+60ns+20ns=3.68ns

此系统访问一个字的平均存取时间是18ns+4.8ns+3.68ns=26.48ns

3、设有4个进程R1、R2、W1、W2,共享可以存放一个数的缓冲区B。进程R1把来自键盘的一个数存入缓冲区B,供进程W1打印输出;进程R2每次从磁盘上读一个数存入缓冲

区B,供进程W2打印输出。 回答问题:

①给出应设置的信号量及其初值,说明其含义。

②用P、V操作来描述4个进程之间的同步、互斥关系。 ①empty表示缓冲区的容量,初值为1;

mutex为R1和R2之间的互斥信号量,初值为1;

sa 为R1与W1之间的同步信号量,表示缓冲区中有来自键盘的一个数,初值为0; sb 为R2与W2之间的同步信号量,表示缓冲区中有来自磁盘的一个数,初值为0。

②Process R1 Process R2 Process W1 Process W2 P(empty P(empty P(sa P(sb

P(mutex P(mutex; 取R1放入的数取R2放入的数 把来自键盘的一个把来自键盘的一个V(empty; V(empty; 数存入缓冲区B 数存入缓冲区B V(mutex; V(mutex; V(sa; V(sb;

4、某机字长32位,按字节编址。现有10个数据依次存入主存,其长度分别是字节、半字、双字、单字、字节、单字、双字、半字、单字、字节。请设计一种既节省存储空间,又能保证任何长度的数据都能在单个存储周期内完成读写的存储方式,画出主存中数据存放的示意图。

采用边界对齐的方法存放这10个数据,数据存放的示意图如下: 字节半字 双字

单字字节 单字 双字 半字单字 字节

5、磁盘的每个磁道分成7个块,现有一文件共有7个记录,依次为:A、B、C、D、E、F、G,存放在某一磁道上,每个记录的大小与块的大小相等,设磁盘的转速为21ms/转,每读出一块后需要2ms的处理时间,忽略其它辅助时间。

问:

①如果顺序存放这些记录并顺序读取,处理该文件需要多少时间?

②如果要顺序读取该文件,记录如何存放处理时间最短?计算此时读取、处理该文件

所需的时间。

读出1个记录的时间为:21/7=3(ms

①顺序存放这7个记录时,读出并处理共需7*(3ms+2ms=35ms

第1个记录没有延迟,其余每个记录延迟19ms,6个记录共延迟6*19ms=114ms 顺序读取并处理这7个记录共用114ms+35ms=149ms ②应将记录按如下顺序存放:

此时读出并处理这7个记录仍需7*(3ms+2ms=35ms

第1个记录没有延迟,其余每个记录延迟1ms ,6个记录共延迟6*1ms=6ms 顺序读取并处理这7个记录共用6ms+35ms=41ms 6、给出生成下述语言的上下文无关文法:

(1{a n b n a m b m |n,m>=0} (2{1n 0m 1m 0n |n,m>=0}

(1所求文法为G[S]=({S,A},{a,b},P,S,其中P 为: S →AA A →aAb|ε (2所求文法为G[S]=({S,A},{0,1},P,S,其中P 为: S →1S0|A A →0A1|ε

7、已知NFA=({x,y,z},{0,1},M,{x},{z}其中:

M(x,0={z},M(y,0={x,y},M(z,0={x,z},M(x,1={x}, M(y,1=φ,M(z,1={y},构造相应的DFA 。

根据题意有 NFA