计算机组成原理作业(0910学年第一学期).ppt

1 10 某计算机有个四阶段的管线 每个阶段完成其工作时间都是一样的 即1nsec 该计算机每秒钟可以处理多少条指令 答 从管道中每纳秒出现一条指令 意味着该机器每秒执行109条指令 它和管道有多少个阶段没有关系 即使是10 阶段管道 每阶段1nsec 也将是每秒执行109条指令 1 20 某文件的描述符为fd 包含如下的字节 3 1 4 1 5 9 2 6 执行下列系统调用lseek fd 3 SEEK SET read fd 其中lseek定位到文件的字节3 则当read完成后 buffer中包含什么内容 答 包含1 5 9 2 1 26 下面单位转换的练习 一微年是多少秒 31 536sgigamicron是多长 1000m1TB存储器中有多少字节 240B地球质量6000yottagram 换算成kilogram是多少 6 1024kg 2 1 图2 2所示为进程的三种状态和四种状态间转换 另两种转换是否可以想象答 从阻塞到运行的转换是可以想象的 如某进程在I O上阻塞 若I O结束时 CPU空闲 则此进程可以从阻塞态直接到运行态 而从就绪态到阻塞态是不可想象的 因为就绪态进程是不会做任何能引起阻塞的事情的 只有运行进程才可能被阻塞 2 22 答 enter region MOVEREG 1ECHGREG LOCKCMPREG 0JNEenter regionRET 2 38 2 38答 CPU利用率是 有用CPU时间 整个CPU时间 a 和 b Q T 进程运行T 然后切换S 利用率是 T T S c 进程每运行T 需进行T Q次切换 共需切换时间是S T Q 因此利用率为 T T S T Q 即Q Q S d 同上 Q Q S 以S代替Q 即50 e 同上 Q Q S Q趋于0 利用率趋近于0 2 40进程调度 进程 A B C D E运行时间 10 6 2 4 8优先级 3 5 2 1 4轮转法 在10分钟里 每个进程占用2分钟 第10分钟C结束 即C的周转时间是10接下来的8分钟 每个进程占用2分 第18分钟D结束 即D的周转时间是18接下来的6分钟 每个进程占用2分 第24分钟B结束 即B的周转时间是24接下来的4分钟 每个进程占用2分 第28分钟E结束 即E的周转时间是28最后A再运行2分钟结束 即A的周转时间是30平均周转时间是 10 18 24 28 30 5 22 2 40进程调度 优先级法按照B E A C D顺序执行 则B在第6分结束 周转时间是6E在第6 8分结束 周转时间是14A在第6 8 10分结束 周转时间是24C在第6 8 10 2分结束 周转时间是26D在第6 8 10 2 4分结束 周转时间是30平均周转时间是 6 14 24 26 30 5 20 2 40进程调度 先来先服务按照A B C D E顺序执行 则A在第10分结束 周转时间是10B在10 6分结束 周转时间是16C在10 6 2分结束 周转时间是18D在第10 6 2 4分结束 周转时间是22E在第10 6 2 4 8分结束 周转时间是30平均周转时间是 10 16 18 22 30 5 19 2 2 40进程调度 最短作业优先按照C D B E A顺序执行 则C在第2分结束 周转时间是2D在2 4分结束 周转时间是6B在2 4 6分结束 周转时间是12E在第2 4 6 8分结束 周转时间是20A在第2 4 6 8 10分结束 周转时间是30平均周转时间是 2 6 12 20 30 5 14 2 41 在CTSS系统中 若某进程需运行30个时间片 那它将需要多少次换入 包括第一次 答 CTSS系统中 每个进程在换入时将依此获得1 2 4 8 16 个时间片 因此 此进程将依此获得1 2 4 8 16 15 个时间片 需要经过5次交换 2 43 老化算法下一次预测时间是 40 2 20 2 2 40 2 2 15 2 40 8 20 8 40 4 15 2 25 2 44 某个软实时系统有4个周期性事件 它们周期分别是50ms 100ms 200ms 250ms 占用CPU时间分别是35 20 10 xms 则使得系统可调度的最大x是多少 答 实时系统可调度的条件是 35 50 20 100 10 200 x 250 1 即x 12 5ms 2 50 正在浴室或准备进入浴室的女生数intwoman num 0 正在浴室或准备进入浴室的男生数intman num 0 控制对woman num的访问semaphorewn mutex 1 控制对man num的访问semaphoremn mutex 1 semaphorebath 1 控制对浴室的使用 2 50 voidwoman want to enter down 2 50 voidman want to enter down 3 13 1 原状态 若D请求1个单元 状态变为 已有最大A16A16B15B15C24C24D47D57剩余2剩余1 由此状态出发检查是否存在一个分配序列使得所有进程都能完成 因为此状态只剩余1个资源 不能满足A B C D任何一个进程的需要 所有进程都不能完成 系统将会死锁 所以若D多请求1个单元 会引起不安全状态 3 13 2 原状态 若C请求1个单元 状态变为 已有最大A16A16B15B15C24C34D47D47剩余2剩余1 由此状态出发检查是否存在一个分配序列使得所有进程都能完成 3 13 2 A16A16A16A16B15B15B15B15C34C44C0 C0 D47D47D47D77剩余1剩余0剩余4剩余1A16A16A16A66B15B55B0 B0 C0 C0 C0 C0 D0 D0 D0 D0 剩余8剩余4剩余9剩余4因为从此状态出发 存在一个分配序列C D B A 使所有进程都能完成 因此C多请求1个单元会引起安全状态 3 17 若A请求最后1台磁带驱动器 则状态变为分配矩阵C申请矩阵RAvailableA401101000020B01000112C11103100D11010010E00002110分析从此状态出发是否存在一个分配序列使所有进程都可以完成 3 17 根据银行家算法分析 找到RD 0010 A 0020 标记D 并把CD加到A上 即A 0020 1101 1121 表示先分配给D所需要的A A RD D完成后释放其全部资源A A RD CD 找到RA 0100 A 1121 标记A 并把CA加到A上 即A 1121 4011 5132 找到RB 0112 A 5132 标记B 并把CB加到A上 即A 5132 0100 5232 找到RC 3100 A 5232 标记C 并把CC加到A上 即A 5232 1110 6342 找到RE 2110 A 6342 标记E 并把CE加到A上 即A 6342 0000 6342 所以该状态安全 因为所有进程都被标记 即表示存在一个分配序列D A B C E 使所有进程都可以完成 3 15 某一系统有两个进程和三个相同的资源 每个进程最多需要两个资源 此情况下系统有没有可能发生死锁 答 最坏的情况是两个进程每个获得1个资源 都又申请另外1个 此时系统还剩余1个 可以满足其中一个进程的需要 使此进程得以完成并释放资源 则另一个进程也可以完成 3 18 一个计算机有六台磁带机 由P个进程竞争使用 每个进程可能需要两台 P是多少时 系统没有死锁的危险 答 最坏的情况是P个进程每个都已获得1台磁带机 都又申请另外1台 如果此时系统至少剩余1台 可以满足其中一个进程的需要 使此进程得以完成并释放资源 则所有进程都可以完成 6 P 1 1即P 5若每个进程可能需要3台呢 3 18 若每个进程可能需要3台呢 答 最坏情况是每个进程已获得2台 又都申请另1台 此时系统应至少还剩1台以满足一个进程的需要 才不至于死锁 6 P 2 1即P 2若系统r个相同的资源 p个进程竞争使用 每个进程最多需要m个 则p r m要满足什么关系才可以使系统不出现死锁 3 16 若r个相同的资源 p个进程竞争使用 每个进程可能需要m个 则p r m要满足什么关系才可以使系统不出现死锁 答 最坏情况是p个进程每个已经获得了m 1个资源 此时系统至少应还剩余1个资源来满足其中某个进程最大需要 才不至于死锁 即r p m 1 1 3 20 已分配矩阵 需求矩阵A1021101002B2011102100剩余向量C110101030000 x11D1111000111答 可以看出 x 1时 D可以完成 剩余向量变为11221 此时将死锁 如果x 2 则剩余向量为11321 C可以完成 剩余向量变为22331 然后可以满足B后 剩余向量变为42442又可以满足A 所有进程可满足 是安全状态 即要求x 2 3 22 两个进程A和B 每个都需要某个数据库中的3个记录1 2和3 如果A按照1 2 3的次序请求 而B按相同的顺序请求 是不会死锁的 然而 如果B按3 2 1的次序请求 那么就可能死锁 对于3个资源 每个进程请求资源都有6种可能的组合 哪些组合可以保证不出现死锁 答 假设进程A要求按1 2 3申请记录 如果进程B同样先请求1 其中某个进程将得到它 而另一个将被阻塞 这种情形不会造成死锁 因为 获得记录1的进程现在没有干扰而运行结束 在其余几种组合中 某些可能导致死锁而某些不会死锁 6种情况如下进程A进程B123123不会死锁123132不会死锁123213可能死锁123231可能死锁123312可能死锁123321可能死锁因为6种组合中有4个可能导致死锁 因此有1 3机会避免死锁 2 3机会可能死锁 4 2 图4 21中 例示了多个作业可以并行运行 而且比顺序运行更快完成 假设有2个作业同时开始 每个都需要10分钟CPU时间 如果顺序运行 最后一个需要多久才能完成 如果是并行需要多久 假设I O等待时间为50 答 答 如果每个作业都有50 的I O等待 那么没有竞争的情况下 需要花费20分钟完成 如果顺序运行 第二个将在第40分钟完成 对于2个作业并行运行 CPU近似利用率为1 0 52 0 75 因此 每一分钟每个作业获得0 75 2 0 375分钟CPU时间 为了获得10分钟CPU时间 每个作业必须运行10 0 375分钟 大约为26 67分钟 所以并行在26 67分钟之后两个作业都完成 4 4 比较使用位映像和使用链表来记录空闲内存之间的区别 128 MB 227B 内存被划分成n字节的单元 对于链表 假定内存由64KB 216B 大小的碎片和空洞交替组成 同时假定链表中每个节点需要一个32位的内存地址 16位的长度 以及16位的next域 那么每种方法各需要多少字节 哪一种更好 4 4 答 位映像每个分配单元需要1位 对于227 n个分配单元 需要227 n比特 224 n字节 链表总共有227 216 211个节点 每个节点占用 32 16 16 位共8字节 也就是总共211 8 214字节 当224 n 214时 即n210 位映像较好 n为1K时 两者相等 4 5 按地址排列的空闲区大小依次是10KB 4KB 20KB 18KB 7KB 9KB 12KB 15KB 对于连续的段请求12KB 10KB 9KB答 首次适配算法 20KB 10KB 18KB下次适配算法 20KB 18KB 9KB最佳适配算法 12KB 10KB 9KB最差适配算法 20KB 18KB 15KB 4 7 200004KB页面 二进制和十进制两种方法 20000 100111000100000页号 100 页内偏移 11100010000020000 4096页号 商 4 页内偏移 余数 36168KB页面页号 10 页内偏移 111000100000页号 2 页内偏移 3616 4 7 327684KB页面 二进制和十进制两种方法 32768 1000000000000000页号 1000 页内偏移 032768 4096页号 商 8 页内偏移 余数 08KB页面页号 100 页内偏移 0页号 4 页内偏移 0 4 7 600004KB页面 二进制和十进制两种方法 60000 1110101001100000页号 1110 页内偏移 10100110000060000 4096页号 商 14 页内偏移 余数 26568KB页面页号 111 页内偏移 101001100000页号 7 页内偏移 2656 4 8指出对应于下列虚拟地址的物理地址 20 20 10 0000 000000010100 2虚页号 0查找页表 映射到页框2页内偏移 000000010100物理地址 页框号 页内偏移 即 0010000000010100 2或 8212 1020 4K即20 4096商 0 虚页号查找页表 映射到页框2余数 20 页内偏移物理地址 2 4K 20 2 4096 20 8212 10 4 8指出对应于下列虚拟地址的物理地址 4100 4100 10 0001 000000000100 2虚页号 1查找页表 映射到页框1页内偏移 000000000100物理地址 页框号 页内偏移 即 0001000000000100 2或 4100 104100 4K即4100 4096商 1 虚页号查找页表 映射到页框1余数 4 页内偏移物理地址 1 4K 20 1 4096 4 4100 10 4 8指出对应于下列虚拟地址的物理地址 8300 8300 10 0010 000001101100 2虚页号 2查找页表 映射到页框6页内偏移 000001101100物理地址 页框号 页内偏移 即 0110000001101100 2或 24684 108300 4K即8300 4096商 2 虚页号查找页表 映射到页框6余数 108 页内偏移物理地址 6 4K 108 6 4096 108 24684 10 4 11 如果一条指令需10nsec 而一个缺页还需另加nnsec 假设每k条指令发生一次缺页 给出计算有效指令时间的公式 答 每k条指令发生一次缺页 即需另加nnsec 因此每执行K条指令所需时间为 10k n nsec 即平均的指令时间为 10k n k 10 n k nsec 4 12 某机器有32 位的地址空间和8 KB 213B 的页 页表完全在硬件中 当一个进程开始时 该页表从内存复制到硬件中 复制每页表项需100nsec 如果每个进程运行100msec 包括载入页表的时间 那么CPU花费在载入页表的时间为多少 答 该页表包含232 213 219项 装载该页表需219 100ns 52ms 如果某进程运行100ms 其中载入页表为52ms 实际运行时间为48msec 因此 52 的CPU时间用于载入页表 4 23 页面访问顺序0172327103 FIFO算法6次缺页LRU7次缺页 4 23 页面访问顺序0172327103 23455 LRU算法6次缺页 4 25 第一个时钟周期时每页的R位是页0123R位0111计数器0 00000000计数器1 10000000计数器2 10000000计数器3 10000000 4 25 第二个时钟周期时每页的R位是页0123R位1011计数器0 10000000计数器1 01000000计数器2 11000000计数器3 11000000 4 25 第三个时钟周期时每页的R位是页0123R位1010计数器0 11000000计数器1 00100000计数器2 11100000计数器3 01100000 4 25 第四个时钟周期时每页的R位是页0123R位1101计数器0 11100000计数器1 10010000计数器2 01110000计数器3 10110000 4 25 第五个时钟周期时每页的R位是页0123R位0010计数器0 01110000计数器1 01001000计数器2 10111000计数器3 01011000 4 25 第六个时钟周期时每页的R位是页0123R位1010计数器0 10111000计数器1 00100100计数器2 11011100计数器3 00101100 4 25 第七个时钟周期时每页的R位是页0123R位1100计数器0 11011100计数器1 10010010计数器2 01101110计数器3 00010110 4 25 第八个时钟周期时每页的R位是页0123R位0001计数器0 01101110计数器1 01001001计数器2 00110111计数器3 10001011 4 29 页装入时间上次访问时间RM012628010123026501214027000311028511NRU将替换页2 因为RM 00 编号最小 表示页2最近未被访问且未被修改 FIFO将替换页3 因为装入时间最早 LRU将替换页1 因为上次访问时间最早 即最久未访问 第二次机会将替换页0按装入时间排序的链表 3R 1 0R 1 2R 0 1R 0检查表头页面 若R 1 则 0R 1 2R 0 1R 0 3R 0继续检查表头页面 直至R 0 所以选择页2 4 31 某计算机给每个过程提供65 536个字节的地址空间 每页4096字节 某程序正文为32 768字节 数据大小为16 386字节以及15 870字节的堆栈 该程序可以放入该地址中吗 如果页大小为512字节呢 一页不可能包含两个不同段的部分 答 进程地址空间65536 4096 16页 而此程序正文需32768 4096 8页 数据需16386 4096 5页 堆栈需15870 4096 4页 共需17页 该程序无法放入 而对于512 字节的页 进程地址空间65536 512 128页 此程序正文64页 数据33页 而堆栈31页 总共128页 刚好 4 37 解释内部碎片和外部碎片之间的区别 哪一种在分页系统中发生 哪一种在纯分段的系统中发生 答 当最后的分配单元不满时 就产生了内部碎片 而外部碎片是指两个分配单元之间被浪费的空间 在分页系统中 最后一页丢失的空间为内部碎片 在纯分段系统中 段之间的某些空间是不可用的 这是外部碎片 5 9 什么是 设备无关性 答 设备无关性是指以相同的方法访问文件和设备 而与其物理特性无关 如果系统采用一组调用写文件 而使用另一组调用写控制台 终端 那么就不具有设备无关性 5 10 下列操作分别在4个I O软件层的哪一层完成 为一个磁盘读操作计算磁道 扇区和磁头 设备驱动程序向设备寄存器写入命令 设备驱动程序检查用户是否有权允许使用设备 与设备无关的操作系统软件二进制整数转换为ASCII码以便打印 用户层软件 5 14 对于7200 rpm的磁盘 相邻寻道时间为1ms 其柱面倾斜为多少 设该磁盘每个磁道有200个扇区 答 该磁盘旋转速率为7200rpm 因此每旋转一周时间T1 60 1000 7200 100 12ms 磁盘每道200个扇区 则每个扇区在磁头下通过时间T2 T1 200 100 12 200 1 24ms 寻道时间T3 1ms 则在寻道期间将有T3 T2 24个扇区通过 因此柱面倾斜应该为24 5 24 FCFS服务顺序 20 102220240638磁臂移动的柱面数 1012218383432 146寻道时间 146 6 876msSSF服务顺序 20 202210623840磁臂移动的柱面数 021244362 60寻道时间 60 6 360ms电梯算法服务顺序 初始向上 20 202238401062磁臂移动的柱面数 021623044 58寻道时间 58 6 348ms 5 27 某计算机的中断处理程序每个时钟计时需2ms 包括进程切换的耗时 若时钟频率为60Hz 则该CPU用于时钟处理的比率为多少 答 每秒发生60次中断 共占用CPU时间60 2 120ms 则CPU用于时钟处理的比率为120ms 1000ms 12 6 11 当前工作目录是 usr jim 则相对路径是 ast x的文件的绝对路径是什么 答 usr ast x 6 12 文件的连续分配会导致磁盘碎片 而当一个文件的长度不等于块的整数倍时 文件中的最后一个磁盘块中的空间会浪费掉 请问这是内碎片还是外碎片 答 连续分配导致的是外碎片 类似于交换系统中的外碎片 而文件中最后一个磁盘块中浪费的空间属于内碎片 类似于分页系统中的页内碎片 6 21 设磁盘地址D位 一个磁盘有B块 其中F块空闲 在什么条件下 空闲表采用空间少于位图 空闲表需要的空间 F D比特位图需要的空间 B比特所以 当FD B时 适合于使用空闲表空闲磁盘比应是F B 由FD B F B 1 D 即空闲磁盘比应小于1 16 6 25 6 22 磁盘分区在格式化之后 磁盘