资源描述
1 3 4 9 7 8 11 12 6章第10章多CPU调度，实时调度第1章 作业：习题P25 1.3 1.8 1.9（更正印刷错误106）1.3操作系统的大神求解答假设有一个32位微处理器，其32位的指令由两个域组成：第一个字节包含操作码，其余部分为一个直接操作数或一个操作数地址。如果微处理器总线具有如下特征，分析a、最大可直接寻址的存储器能力为多少？以字节为单位如果微处理器总线具有如下特征，分析对系统速度的影响：b、（1）一个32位局部地址总线和一个16位局部数据总线，或者（2） 一个16位局部地址总线和一个16位局部数据总线。C、程序计数器和指令寄存器分别需要多少位答案：没必要全写捡重点(定长)指令32位，1字节操作码，则后3字节为立即数或内存地址(a) 最大可直接寻址直接寻址是一种基本的寻址方法，其特点是：在指令格式的地址的字段中直接指出操作数在内存的地址。由于操作数的地址直接给出而不需要经过某种变换，所以称这种寻址方式为直接寻址方式。224(b) 总线问题地址总线32位，数据总线16位直接寻址存储器24位，bus32位，地址传送一次即可；但指令32位，操作数32位(因为是32位微处理器)，要两次传送地址总线16位，数据总线16位传送地址，传送指令/数据全部需要2次。地址可视作：先行地址后列地址(c) PC和IR 至少：PC24位，IR8位一般：PC32bit IR 32bit更现实复杂情形：是否分段，使用段寄存器; 直接寻址中逻辑地址/位移/偏移offset，与有效地址effective address区别OS中，逻辑地址与物理地址1.8一个DMA模块从外部设备给内存传送字节，传送速度为9600位每秒（b/s)。处理器可以每秒100万次的速度取指令，由于DMA活动，处理器的速度将会减慢多少？答案：没必要全写捡重点看清楚题干：每秒100万次取指令，即1M/s取一次指令，不是100M！该CPU主频多少不知，是否使用cache不知，执行一条指令多少时钟周期不知，此题中无需知道还假设，此CPU只取指令要访问内存，执行指令不需要读写数据，不访内存. 还假设DMA一次访问内存传送1个字节 凭什么如此假设？9600b/s=1200B/s 即1s中要传送1200次，而原本CPU要1M次访存，现在因DMA要减少1200次，所以影响是1200/1M=0.12%1.9一台计算机包括一个CPU和一台I/O设备D，通过一条共享总线连接到主存储器M，数据总线的宽度为1个字。CPU每秒最多可执行106条指令，平均每条指令需要5个机器周期，其中3个周期需要使用存储器总线。存储器读/写操作使用1个机器周期。假设CPU正在连续不断地执行后台程序，并且需要保证95%的指令执行速度，但没有任何I/O指令。假设1个处理器周期等于1个总线周期，现在要在M和D之间传送大块数据。a.若使用程序控制I/O，I/O每传送1个字需要CPU执行两条指令。请估计通过D的I/O数据传送的最大可能速度。b.如果使用DMA传送，请估计传送速度。答案：没必要全写捡重点题干信息：多少位CPU不知，字长多少位不知，以处理器周期为单位，访问内存(读1条指令读1字数据)要1周期，执行1指令需要5周期。CPU每秒最多执行106条指令程序IO：传送1字要2条指令限制只能有5%的CPU处理用于IO程序IO：传送1字要2条指令限制只能有5%的CPU处理用于IO此限制下，1秒可执行用于IO的指令为5% * 106条指令而2条指令才可传送1字数据，所以每秒IO最大可传送的字为0.5*5%*106=25000字/秒DMA情形：最大速度：在CPU执行后台程序时，总共能找到多少周期可以利用。1周期传送1字5%CPU处理能力，全部可用于DMA,可执行指令条数为5%*106，而1条有5周期，所以可传送字：5*5%*106 个字DMA情形：最大速度：在CPU执行后台程序时，总共能找到多少周期可以利用。1周期传送1字最大吗？要见缝插针！后台程序执行时，执行1条指令共5个周期，但只在3个周期中访存，还有2个没有使用，DMA可用这两个周期DMA情形：最大速度：在CPU执行后台程序时，总共能找到多少周期可以利用。1周期传送1字最后，DMA最大速度为：106(0.05 5 + 0.95 2) = 2.15 106 即2.15M字/秒第3章 ：进程描述与控制P103 3.5，3.14 P104 3.111、概念：交换(swapping)：操作系统将内存中进程的内容或部分内容写入硬盘，或反之的操作。进程：具有一定独立功能的程序关于一个数据集合的一次运行活动。2. 进程有哪三个基本状态？试说明状态转换的典型原因，图示。（1） 处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程就由就绪状态变为执行状态 （2） 正在执行的进程因发生某事件而无法执行，如暂时无法取得所需资源，则由执行状态转变为阻塞状态。 （3） 正在执行的进程，如因时间片用完或被高优先级的进程抢占处理机而被暂停执行，该进程便由执行转变为就绪状态。（2） 状态转换1不会立即引起其他状态转换。 状态转换2必然立即引发状态转换1：状态转换2发生后，进程调度程序必然要选出一个新的就绪进程投入运行，该新进程可能是其他进程，也可能是刚从执行状态转换成就绪状态的那个进程。 状态转换3可能立即引发状态转换1：状态转换3发生后，若就绪队列非空，则进程调度程序将选出一个就绪进程投入执行。 状态转换4可能引发状态转换1：状态转换4发生后，若CPU空闲，并且没有其他进程竞争CPU，则该进程将被立即调度。 另外，状态转换4还可能同时引发状态转换1和2：若系统采用抢占调度方式，而新就绪的进程具备抢占CPU的条件（如其优先权很高），则它可立即得到CPU转换成执行状态，而原来正在执行的进程则转换成就绪状态。3.5什么是交换，目的是什么：操作系统将内存中进程的内容或部分内容写入硬盘，或反之的操作。目的：将暂时无法运行的进程（阻塞状态）从内存中移出，空出内存，以便在内存中装入尽可能多的可运行的进程。3.14模式切换与进程切换是什么有什么区别是什么：为便于OS实现和管理，处理器一般支持两种（以上的）执行模式：用户态和内核态。OS在内核态下运行，用户进程在用户态下运行。从用户态到内核态的改变或反之，称之为模式切换。用户进程运行时，如处理器响应中断，进入中断处理程序，则由用户态进入内核态；而中断返回后，从内核态返回用户态。区别：模式切换不一定会改变当前运行的进程的状态，而进程切换过程中必然会出现模式切换。模式切换（对应的中断处理）保存/恢复的状态信息少，而进程切换需要保存/恢复的状态信息多。3.11 中断A）中断如何支持多道程序设计：1.外部设备具备中断能力后，CPU才可能在外部设备开始工作到完成之间执行其它程序；（轮询方式中，外部设备工作完成之前，CPU一直循环测试外部设备的状态，不可能执行其它程序）2.利用中断方式，操作系统可以及时获得控制权，在多个程序之间选择调度。B)中断如何支持错误处理：在硬件发生异常时，如奇偶校验错，掉电等，以特殊中断形式出现；程序中出现系统错误时，如除零，地址越界，（无访问权限的）非法访问，以特殊中断形式出现；程序中应用语义级的错误，也可以中断形式出现；各种错误统一地用中断方式处理，只要分别编制相应的中断处理程序即可，简化了硬件设计，也方便了用户程序开发。C）对于单线程而言，说明一个能够引起中断并且导致进程切换的情景，另外说明能引起中断但没有进程切换的例子导致切换例：用户进程要求输入，则在启动外部设备工作后，用户进程进入阻塞状态，进行进程切换；不导致切换例：发生时钟中断，当前运行的用户进程的时间片还未用完，则继续执行。(另，若不限定为外部中断，则用户进程执行系统调用时，发生中断，若系统调用不涉及IO，则不会发生进程切换)第4章 线程对称处理SMP和微内核概念：线程是进程中一个相对独立的执行流，是CPU调度的单位。1、为什么要引入线程，多线程有何优点？操作系统引入线程后，可以简化并发程序的设计，方便在一个进程内实现多个并行处理。多线程的优点包括：实现进程内并行处理；方便数据共享；降低了切换时的系统开销；提高了CPU的利用率；改善了程序的响应性。2. 比较TCB与PCB内容。TCB：线程标识，线程状态（运行,就绪,阻塞）,处理器状态，（堆栈,私用数据段的）指针PCB: (TCB中没有的)进程的虚拟空间指针，文件等资源，进程的权限，进程间通信等。3. 比较用户级线程与内核级线程的异同用户级：优点：不需要OS支持，调度方式灵活，开销小；缺点：不能并行，一线程阻塞，其它线程也不能运行。内核级：优点：可并行，一线程阻塞不会阻塞其它线程，缺点：创建切换开销相对大第9章 ：单处理器调度 P291 9.1, 9.5, 9.109.1简要描述三种类型的处理器调度长程调度：决定加入到待执行的进程池中；中程调度：决定加入到部分或全部在主存中的进程集合中；短程调度：决定哪一个可用进程将被处理器执行。9.5抢占式和非抢占式有什么区别非抢占：在这种情况下，一旦进程处于运行态，他就不断执行直到终止，或者为等待I/O或请求某些操作系统服务而阻塞自己。抢占：当前正在运行的进程可能被操作系统中断，并转移到就绪态。关于抢占的决策可能是在一个新进程到达时，或者在一个中断发生后把一个被阻塞的进程置为就绪态时，或者基于周期性的时间中断。9.10简答定义最高响应比优先调度调度基于抢占原则并且使用动态优先级机制。当一个进程第一次进入系统时，它被放置在RQ0。当它第一次被抢占后并返回就绪状态时，它被防止在RQ1。在随后的时间里，每当它被抢占时，它被降级到下一个低优先级队列中。一个短进程很快会执行完，不会在就绪队列中降很多级。一个长进程会逐级下降。因此，新到的进程和短进程优先于老进程和长进程。在每个队列中，除了在优先级最低的队列中，都使用简单的FCFS机制。一旦一个进程处于优先级最低的队列中，它就不可能再降低，但是会重复地返回该队列，直到运行结束。补充题：分析多级反馈算法(指出其目标，假设，内容及效果)反馈调度算法分析：目标系统效率：减少平均等待时间，提高系统呑吐量公平：减少饥饿现象出现或减轻程度尽量减少系统开销反馈调度算法分析:假设,理由程序由CPU阵发期，IO阵发期交替构成程序完成一次IO后，紧接着可能是一个短暂的IO阵发期程序一开始，一般都是一个CPU阵发期程序运行时间有长有短；长时间运行没有结束的程序可能还需要很长时间才能结束反馈调度算法分析:内容设置多个分成优先级不同的就绪队列，高优先级队列的时间片短，低优先级队列的时间片长。(任一优先级的进程被调度运行时，时间片内不会被抢占。)调度时，某一优先级队列的进程只在所有比其高的队列都为空时，才会调度这一队列中的进程。进程新创建时，进入优先级最高的队列。每一进程被调度运行，用完时间片仍未结束重新回到就绪状态时，移入下一优先级队列而进程从阻塞状态到就绪状态时，提高优先级反馈调度算法分析：效果体现了短作业“优先”：因为其所需的时间片少，优先级不会下降很多，会被优先调度，从而很快运行结束。因此，响应时间短，平均周转时间短有较好的响应时间：因为新进程优先级最高，被优先调度执行，所以响应时间短；IO结束的进程提高优先级，也会相对优先被调度执行，同样响应时间短(用户在输入完成后，进程很快会有反应)长作业的系统开销较小：长作业最终会落到优先级最低，时间片最长的就绪队列中。一旦此类作业被调度运行时，(大)时间片用完之前不会有抢占调度，减少了调度次数，所以系统开销小。公平性和饥饿：由于长作业最终的时间片长，可以减少周转时间；在发生一次IO操作后可提升优先级，可以部分抵消“短作业优先”的不公平，也可减轻长作业的饥饿程序。选做9.1第7章 ：内存1. 什么是重定位，为什么需要重定位，如何实现重定位？2. P227， 7.12(不做d小题) (删除用6位表示页号描述)1. 什么是重定位，为什么需要重定位，如何实现重定位？什么是：重定位指在执行过程中，程序在内存中的位置发生了移动。（可重定位指代码在内存中移动后仍能正确执行）为什么需要：为了实现多道程序设计，在内存中存在多个程序，一个程序一旦被换出内存，当它再次换入时可能原来的位置已经被占用，故收到限制，需要找其他空闲的内存存放，这时便需要重定位。如何实现：代码中只使用相对的逻辑地址，不使用绝对的物理地址，在加载时根据分配的物理内存地址，由加载工具将代码中逻辑地址改写为物理地址；或者在指令执行时由CPU完成逻辑地址到物理地址的转换。重定位：与页式管理中逻辑地址物理地址转换无必然关系。2. P227， 7.12(不做d小题) (删除用6位表示页号描述)在一个32位机器上，假设把逻辑地址分为8位，6位，6位，12位四个部分。换句话说，系统使用3级页表，其中第一个8位是第一季，后边的6位是第二季，以此类推。在这个系统中，用6位表示页号，假设内存是按照字节访问的。A), 页大小212=4096字节B), 一个进程的页面个数为220=1M个C), 逻辑地址空间为232=4GB字节如题干中，改为“用6位表示页框号”，则D)答案：物理内存最大为26 *4K=256K第8章 虚拟内存1.解释下列术语：抖动，TLB，工作集，LRU算法2. P266 8.4 题目印刷错误1.解释下列术语：TLB:存放页表内容的特殊Cache,一般多采用联想寄存器实现。CPU在地址转换时，首先检查该虚拟地址的页号的映射项在TLB中是否存在，TLB命中可大大缩短逻辑地址到物理地址的转换。抖动/颠簸：CPU将绝大多数时间用在进程的换进换出而不是执行用户程序的现象。出现抖动时，应改进替换算法;增加物理内存的容量;减少并发执行的进程的个数。页表：是页式内存管理中使用的数据结构，存放逻辑地址到物理地址的映射。工作集(working set)：进程在过去一段时间内所访问页面的集合。工作集随时间变化而变化。如果一个进程的工作集没有在内存中，则会影响进程的执行效率。LRU算法:页式内存管理中的替换算法。选择最近最少使用的页替换,即最后一次访问时间最早的页，推测该页在不远的将来被访问的可能性最低。理论分析LRU的准确性很高，但是实现复杂，系统开销大，实际使用时一般采用LRU的简化版本。2. P266 8.4 题目印刷错误P266 8.4 一个进程分配给4个页框（下面的所有数字均为十进制数，每一项都是从0开始计数的）。上一次把一页装入到一个页框的时间，上一次访问页框中的页的时间，每个页框中的虚拟页号以及每个页帧的访问位（R）和修改位（M）如下表所示（时间均为从进程开始到该事件之间的时钟时间，而不是从事件发生到当前的时钟值）8.4题目印刷错误 3-5当虚拟页4发生错误时，使用下列内存管理策略，哪一个页帧将用于置换？解释原因。 a.FIFO（先进先出）算法 b.LRU（最近最少使用）算法 c.Clock算法 d.最佳（使用下面的访问串）算法 e.在页错误之前给定上述内存状态，考虑下面的虚拟页访问序列： 4,0,0,2,4,2,1,0,3,2 如果使用窗口大小为4的工作集策略来代替固定分配，会发生多少页错误？每个页错误何时发生？ P266 8.4题目印刷错误说明：clock算法按“加载时间”顺序查找E)算法：LRU,窗口4时间单位A).替换页框3，因为其内容最早装入(加载时间20)B).替换页框1， 因为最后一次访问时间最早(访问时间160)C).替换页框0，因为这个页框是扫描时最一个遇到的访问位为0的页框D).替换页框3，因为其内容(页号3)将来最晚被访问。4,0,0,0,2,4,2,1,0,3,2E).P266 8.4 工作集策略可变分配！E).P266 8.4 工作集策略工作集窗口示意图第11章 ：I/O管理和磁盘管理P363 11.5,11.7（0,1,5级）,11.8选做：P364,11.3(a),11.7(多少个扇区，柱面), 11.8, 11.911.5磁盘读写延迟因素：寻道时间:指磁头移动到指定柱面所需要的时间；旋转延迟:指要访问的指定扇区转动到磁头位置所需要的时间；传送时间:指完成对指定扇区读写操作所需要的时间。11.7 简单定义7个RAID级别 RAID（0,1,5级）0级：分条，指逻辑上连续的数据被分散存放在多个可用磁盘中，以后(连续)读写时，可利用多个磁盘并行工作以缩短操作时间;1级：镜像,指数据重复存放在多个磁盘中，通过这种冗余的方式来提高整体可靠性;5级：块分布奇偶校验,指逻辑上连续的数据分块，并计算逐位奇偶校验和，然后分散到N个磁盘构成的磁盘组中。以后如果组中任一个磁盘发生故障，可利用其余N-1个可用磁盘计算出故障磁盘中的所有数据。(常用：0，1，5及0+1)0：非冗余 1：被镜像；每个磁盘都有一个包含相同数据的镜像磁盘。 2：通过汉明码实现冗余；对每个数据磁盘中的相应都计算一个错误校正码，并且这个码位保存在多个奇偶校验磁盘中相应的文件。 3：交错位奇偶校验；类似于第二层，不同之处在于RAID3为所有数据磁盘中同一位置的位的集合计算一个简单的奇偶校验位，而不是错误校正码。 4：交错块分布奇偶校验；对每个数据磁盘中相应的条带计算一个逐位奇偶。 5：交错块分布奇偶校验；类似于第四层，但把奇偶校验条带分布在所有磁盘中。 6：交错块双重分布奇偶校验；两种不同的奇偶校验计算保存在不同磁盘的不同块中。11.8 典型磁盘扇区大小：512字节(在今天超大容量磁盘中，真正的物理扇区的大小是512的2n,如4096，但OS和应用程序在逻辑上仍然可以认为扇区为512字节。)512比特， 比特？512KB11.3a11.7如果磁盘中扇区大小固定为每扇区512字节，并且每磁道128个扇区，每面130个磁道，一共有12个可用的面，计算存储90000条200比特长的逻辑记录需要多少磁盘空间（扇区，磁道和面）.忽略文件头的记录和磁道索引，并假设记录不能跨越两个扇区。200比特=25字节，一扇区512字节中，可存放512/25 = 20个记录(因记录不跨扇区存放)90000记录需要90000/20=4500个扇区。一个柱面有128*12=1536个扇区90000记录需要4500/1536=2.93=3个柱面或2个完整柱面+1428个扇区 11.8考虑11.7中的提到的磁盘系统，假设磁盘转速是1200转/分，磁盘控制器每旋转一圈可以讲一个扇区读入其内部缓冲区，接着操作系统以字节为单位读取这些数据，每读取一个字节，磁盘控制器会产生一个中断A)如果中断服务列成处理每个中断的时间是1.8微妙，那么系统读入整个扇区需要花多少时间？（不考虑寻道所需要花费的时间）1200转/分，则每秒20转一转为1/20秒=50ms题意：“每旋转一圈可以将一个扇区读入内部缓冲区”一字节一中断，一扇区512字节，中断512次，共需要时间：1.8us*512=921.6us=0.92msB)在系统读取数据的过程汇总，操作系统可以用于处理其他进程的时间是多少？相对于读取磁盘的总传输时间？所占的百分比是多少？50ms中0.92ms用于中断，其余时间CPU处理其它内容，50-0.92=49.08ms百分比： ( 50-0.92)/50 = 98.16%(另外一种理解:磁盘控制器先从盘面将数据读入内部缓冲区(50ms),然后再一个字节一个字节中断，共0.92ms，百分比为50/(50+0.92)=98.193%)11.9再次考虑11.7 11.8中的磁盘系统，假设磁盘控制器和系统内存之间的数据传输采用DMA方式，总线速度为2MB/S，在该条件下，系统读入整个扇区需要花费多少时间？在这段时间内，操作系统可以用于处理其他进程的时间是多少？总线速度2MB/s，则传输一字节时间为：1/2M = 0.5s传512字节时间为0.5*512=256s=0.256ms依前例，磁盘控制器准备一扇区数据需要50ms所以，其它处理时间为50-0.256=49.744ms百分比：49.744/50=99.49%(与11.8同样:若考虑磁盘先读盘面数据，然后再DMA传送，没有任何并行，则百分比计算为：50/(50+.256)第十二章 文件管理 概念文件,文件系统,文件目录文件系统功能，P404 12.10文件(file):(文件系统中)具有符号名而且在逻辑上具有完整意义的信息项的序列。文件系统：文件与管理文件的方法和程序集合称作文件系统。文件目录:包含文件信息的一类特殊文件,文件系统利用其完成从文件名到文件号(inode)的映射。文件系统功能：建立文件目录;提供必要的存取方法以适应不同应用的要求;完成从文件的逻辑组织到物理组织的转换;有效地管理文件在外存的存放;实现文件保护和共享;提供对文件进行操作的系统调用命令.12.10考虑由一个索引节点表示的UNIX文件的组织 见图12.12 假设有12个直接快指针，在每个索引节点中由一个一级，二级，和三级间接指针，此外,假设系统块大小和磁盘扇区大小都是8K。如果磁盘块指针是32位，其中8位用于标识物理磁盘，24位用于标识物理块，那么A）该系统支持的最大文件大小是多少A)8K*(12+2K+4M+8G)=8K*(8594130956)=70403120791552B)该系统支持的最大文件系统分区是多少B)8K*224=8K*16M=128GBC)假设内存中除了文件索引节点外没有别的信息，访问在位置13 423 956中的字节需要多少次磁盘访问？C)文件的索引结点已读入哪一块？13423956 / 8192=1638.66650390625块号码1638前12块：直接块前12+2048=2060块，一级间接IO次数：2次，一次读一级索引块，一次读数据块第六章：并发死锁和饥饿1. 什么是死锁，什么是饥饿？2. 解释死锁四个必要条件的含义.3. P206，6.6，给出过程4. P207，6.11饥饿(starvation)：当饥饿到一定程度，导致进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死(starve to death)。概念：什么是死锁？：一组进程中的每一个进程，均无限期地等待此组进程中某个被其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁(deadlock)死锁四个必要条件的含义“资源独占”指在一段时间内只能由一个进程使用，不能共享；“不可抢占”指高优先级进程或说操作系统不能从抢占己分配给其它进程的资源；“保持申请”指占有资源的进程不释放自己占有的资源，又提出了新的资源申请；“循环等待”指等待其它进程占有资源的等待关系构成了环路。6.6请把6.4结中的死锁检测算法应用与下面的数据，并给出结果答:1. W = (2 1 0 0)2. Mark P3; W = (2 1 0 0) + (0 1 2 0) = (2 2 2 0)3. Mark P2; W = (2 2 2 0) + (2 0 0 1) = (4 2 2 1)4. Mark P1; no deadlock detectedRequest是还需要的 alloction是已经分配的 相加时加已经分配的6.116.11假设在系统中有四个进程和四种类型的资源，系统使用银行家算法来避免死锁。最大资源需求矩阵是：其中Claim(ij)(1=i=4,且1=j=4)表示进程i对于资源j的最大需求。系统中每一种类型的资源总量有向量【16,5,2,8】给出。当前的资源分配情况有下面的矩阵给出：其中，Allocation(i j)表示当前分配给进程i的资源j的数量。a). 当前状态是否安全？说明这个状态是安全的回答：安全，因为存在一个安全进程序列：P2,P4,P1,P3b).说明进程1申请1个单位的资源2是否容许答案：允许如分配，则系统状态为： 此时，P4仍可结束，释放P2需要的一个单位的资源2，P2，随后，P1，P3c).说明进程3申请6个单位资源1是否容许答案：不允许如分配，则系统状态为： 此时，没有一个进程可以结束，是不安全状态，不允许d).说明进程2申请2个单位资源4是否通许答案：不允许因为，进程2最初申请的资源4的最大个数为2，现已分配1个单位，再申请2个单位，则超出了最初申明的最大个数。不允许,不分配。
展开阅读全文