操作系统原理重点知识点.doc

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date操作系统原理重点知识点操作系统原理重点知识点注意：大题必看否则很难及格！1、 什么是操作系统： 操作系统是配置在计算机硬件上带第一层软件，是对硬件系统的首次扩充。2、 操作系统的作用： OS作为用户与计算机硬件系统之间带接口、OS作为计算机系统资源带管理者、OS实现啦对计算机资源带抽象3、 操作系统的目标： 有效性、方便性、可扩充性、开放性4、 操作系统基本特征（并发性 共享性 虚拟性 异步性）其中最重要的特征是 并发性5、 操作系统带主要功能：处理机管理 存储器管理 设备管理 文件管理 用户接口6、进程的三种基本状态：就绪-（进程调度）-执行-（I/O请求）-阻塞-（I/O完成）-就绪 执行-（时间片用完）-就绪 （P38页）7、进程的特征：动态性 并发性 独立性 异步性8、批处理系统带特征：脱机 多道 成批处理9、分时系统带特征：多路性 独立性 及时性 交互性10、常用I/O控制方式有：程序直接控制方式、中断控制方式、DMA方式、通道方式。11、为什么要引入缓冲区？(1)缓和CPU与I/O设备间速度不匹配的矛盾。(2) 减少对CPU的中断频率， 放宽对CPU中断响应时间的限制。(3) 提高CPU和I/O设备之间的并行性12、SPOOLing系统由哪几部分组成？以打印机为例说明如何利用该技术实现多个进程对打印机的共享？组成：输人井和输出井 输入缓冲区和输出缓冲区 输入进程和输出进程对所有提出输出请求的用户进程，系统接受它们的请求时，并不真正把打印机分配给它们，而是由输出进程在输出井中为它申请一空闲缓冲区，并将要打印的数据卷入其中，输出进程再为用户进程申请一张空白的用户打印请求表，并将用户的打印请求填入表中，再将该表挂到打印机队列上。这时，用户进程觉得它的打印过程已经完成，而不必等待真正的慢速的打印过程的完成。当打印机空闲时，输出进程将从请求队列队首取出一张打印请求表，根据表中的要求将要打印的数据从输出井传到内存输出缓冲区，再由打印机进行输出打印。打印完后，再处理打印队列中的一个打印请求表，实现了对打印机的共享。13、什么是死锁？产生死锁的必要条件有哪些？处理死锁的方法？所谓死锁是指多个进程在运行过程中因争夺资源而造成带一种僵局，当进程处于这种僵持状态时，若无外力作用，他们都将无法再向前推进。必要条件：互斥条件 请求和保持条件 不剥夺条件 环路等待条件 处理方法：预防死锁 避免死锁 检验死锁 解除死锁以上为简答题可能出带部分 以下全为计算题 做题时照猫画虎就差不多 计算过程比较简单 有不懂得同学赶快在考试之前问一下懂的同学保证你考试能打60分以上。 呵呵应用题1、 调度算法（FCFS/SPF 高度优先权 时间片轮转）有5个进程P1、P2、P3、P4、P5，它们的创建时刻、运行时间和优先数见下表。规定进程的优先数越小其优先级越高。试描述在采用下述调度算法时，各进程的运行过程，并计算平均周转时间（假设忽略进程的调度时间，时间单位为ms）。（1）先来先服务算法。 （2）剥夺式优先级调度算法。（此问可去掉。增加非剥夺式）进程创建时刻运行时间优先数P1033P2265P3441P4652P5824答：1）先来先服务调度算法：程序的运行过程如下图： 可知：每个进程的周转时间为：T1=3ms； T2=9-2=7ms； T3=13-4=9ms；T4=18-6=12ms； T5=20-8=12ms。系统平均周转时间为：T=（3+7+9+12+12）/5=8.6ms 2）剥夺式优先级调度算法：程序的运行过程如下图： 时间（ms） 可知：每个进程的周转时间为：T1=3-0=3ms； T2=20-2=18ms； T3=8-4=4ms；T4=13-6=7ms； T5=15-8=7ms系统平均周转时间为：T=（3+18+4+7+7）/5=7.8ms 2、 银行家算法在银行家算法中，T时刻的状态如下表，试问：（1）T时刻是否安全？（2）若P2提出请求（1，2，2，2）后，系统能否分配资源？要求：写出判断的过程。进程Allocation Need AvailableP0003200121622P110001750P213542356P303320652P400140656答：（1）利用安全性算法对上面的状态进行分析： workNeedAllocationWork+ AllocationfinishP0P3P1P2P41 6 2 21 6 5 41 9 8 62 9 8 63 12 13 100 0 1 206 5 21 7 5 02 3 5 60 6 5 60 0 3 20 3 3 21 0 0 01 3 5 40 0 1 41 6 5 41 9 8 62 9 8 63 12 13 103 12 14 14TTTTT找到一个安全序列P0,P3，P1, P2,P4，所以T 时刻系统是安全的。（2）P2发出请求向量Request(1,2,2,2)后，系统按银行家算法进行检查：Request(1,2,2,2)Need(2,3,5,6) Request(1,2,2,2) Available(1,6,2,2) 系统进行资源的试分配，并修改相应变量的值Available(0,4,0,0) Allocation（2,5,7,6） Need=(1,1,3,4) 进行安全性检查：此时对所有进程Need Available(0,4,0,0)都不成立，系统进入不安全状态。 系统不能将资源分配给P2。 3、 动态分区.对下图所示的内存分配情况（空白部分表示空闲块）若要申请一块40K的内存，按照最先适应算法、最佳适应算法、最差适应算法分配的首地址分别为什么？能使首地址最大的分配策略是什么？答： 最先适应算法分配的首地址为：100KB最佳适应算法分配的首地址为：330KB最差适应算法分配的首地址为：410KB能使首地址最大的分配策略是最差适应算法空闲区大小80K 空闲区大小90K 空闲区大小60K 空闲区大小102K 4、 基本分页/段储存管理1.某分页系统的用户空间共有32个页面，每页1KB，主存空间为16KB，试问：1） 逻辑地址的有效位是多少？格式如何？物理地址需多少二进制位表示？.2） 假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为2、10、4、7，试将逻辑地址1023（十进制）转换为对应的物理地址？并以逻辑地址1023（十进制）为例画出地址变换过程。答：1）法一：用户空间共有32个页面，故逻辑地址中的页号须用5位来描述。(页号范围:031);每页1KB，故页内地址须用10位描述。(页内地址范围:01023)所以逻辑地址共有：5+10=15位。法二：用户空间大小为32页*1KB/页=32 KB，32 KB=215 B，所以逻辑地址共有 15位。页号P页内地址W其格式为：14 10 9 0内存空间大小为16KB，16 KB=214 B，所以物理地址共有 14位。2)逻辑地址（1023）D 页号=int(1023/1024)=0页内地址=1023%1024=1023，由页表得，P=0对应的P=2其物理地址=1024*2+1023=3071（注：若求出的页号超过页表长度，则可以直接判断是非法的逻辑地址）页表寄存器(PTR) 页表始址 页表长度逻辑地址1023 0 1023物理地址3071 2 1023页号 内存块号012321047>+越界中断以逻辑地址1023为例的地址变换过程如图：2、在一段式存储管理系统中，段表如下，试求出下列逻辑地址对应的物理地址？段号内存始址段长02105001235020210090313505904193895（0，430） （1，10） （2，500） （3，400） （4，122） （5，132）答：逻辑地址（0，430）或写成0，430的物理地址=210+430=640逻辑地址（1，10）的物理地址=2350+10=2360逻辑地址（2，500）的物理地址=100+500=600 因为500>90，所以属于段内地址越界引起的非法地址访问 逻辑地址（3，400）的物理地址=1350+400=1750逻辑地址（4，122），因为122>95，所以属于段内地址越界引起的非法地址访问逻辑地址（5，132），因为5>4，所以属于段号越界引起的非法地址访问5、 页面置换算法（OPT/FIFO/LUR 最佳置换/先进先出/最近最久未使用）在一个请求分页中若一个作业的页面访问顺序为：432143543215，当系统分配给该作业的物理块数M分别为3和4（且初始均为空）时，分别采用FIFO置换法和OPT置换法求缺页中断率，并比较得到的结果。（此类题要注意初始时，内存块是否为空？还是预先调入若干页。）答案：（1）FIFO法(M=3): 注意：若初始时，预先调入4，3，2页，则前3次不缺页。（视具体调入的页号与访问序列而定）（2）OPT法：(M=3)（3）OPT法：m=3时，缺页中断7次，m=4时，缺页中断6次，可见，增加分配给作业的内存块数，可降低缺页率。FIFO法：m=3时，缺页中断9次，m=4时，缺页中断10次，可见，增加分配给作业的内存块数，反而提高了缺页率。FIFO页面淘汰算法会产生异常现象，对特定的访问序列，当分配给进程的物理页面数增加时，缺页次数反而也增加。称为Belady异常。注：如何判断一个页是否在内存-根据扩充页表的状态位P。可以计算每种算法下调页耗费的时间：次数*每页调入的时间。6、 磁盘调度算法(FCFS/SSTF/SCAN/CSCAN 先来先服务/最短寻道时间优先/扫描算法/循环扫描)某一磁盘先后有4个进程提出了磁盘访问请求，按申请到达的先后顺序依次为：43，66，26，88。系统中磁头停留在磁道号为68的磁道上，且移动臂正沿磁道号递减的方向移动。求出分别采用FCFS、SSTF和SCAN磁盘调度算法时，磁道的访问顺序及其所需寻道长度（走过多少柱面）。(会描述对应的算法思想)答：1）FCFS磁盘调度算法：顺序：43，66，26，88 寻道长度：（68-43）+（66-43）+（66-26）+（88-26）=1502）SSTF算法：顺序：66，88，43，26 寻道长度：（68-66）+（88-66）+（88-43）+（43-26）=86 3）SCAN算法：顺序：66，43，26，88 寻道长度：（68-66）+（66-43）+（43-26）+（88-26）=104 7、 外存分配（显示连接 FAT/NTFS 索引分配）(a)索引分配:存放在某个磁盘上的文件系统,采用混合索引分配方式(13个地址项,同UNIX系统的i结点结构),若每个盘块大小为512字节,磁盘块需用3个字节描述,则:1)该文件系统允许文件的最大长度是多少? 析：5123170余2，每个盘块最多存放170个盘块地址，所以索引表中表项最多170个。文件限制最大长度（1017017021703）块512字节2471040KB2）将文件的字节偏移量5000，15000，150000转换为物理块号和块内偏移量。析：50005129余392，所以字节偏移量5000对应逻辑块号为9（从0开始算的），块内偏移量为392，由于9<10，故可以直接从文件的FCB 的第9个地址项处得到物理盘块号，块内偏移量为392。1500051229余152，所以字节偏移量15000对应逻辑块号为29（从0开始算的），块内偏移量为1592，由于10<=29<10+170，而29-10=19，故可以直接从文件的FCB 的第10个地址项处得到一次间址块的地址，并从次间址块的第19项（即该块的第5759这3个字节处）中获得对应得物理盘块号，块内偏移量为152。（有关150000，略）3)假定某文件的FCB已在内存,但其它信息均在外存，试分析:为访问该文件中某个位置的内容,最少需要几次启动磁盘?最多需要几次启动磁盘? 析：由于文件的FCB已在内存，为访问文件中的某个位置，最少需要1次启动磁盘（直接地址）；最多需要4次启动磁盘（三次间址）。 注：若文件所有信息均在外存？则查找FCB操作也要算一次启盘。故最少需要2次启动磁盘（直接地址）；最多需要5次启动磁盘（三次间址）。(b)某文件系统中，如果磁盘容量为12GB，盘块大小为4KB，采用显式链接分配方式时，问：（1）每个FAT表项需占几个字节（FAT表项的长度取字节的整数倍）？答：盘块数=12G/4KB=3M=3KKB每个FAT表项需占3个字节（2）其FAT需占用多少存储空间？答：FAT需占用3B*3M=9MB（3）如果文件A依次占用3、5、7号三个盘块，画出A中各盘块间的链接情况及FAT的情况。P217页图（超简单必看）8、 位示图法某计算机系统采用位示图法（行号、列号和盘块号都从1开始编号）来管理文件存储空间,且0表示盘块空闲。对于32MB的磁盘，每个盘块的大小为1KB，试具体说明如何为某文件分配一个盘块？（回收？）该系统的位示图容量有多大？（注意：行号、列号也可以从0开始）答：为某文件分配一个盘块的过程如下：1）顺序检索位示图，从中找到一个值为0的二进制位。 2）设行号i列号j，计算出相应的盘块号b为：bn×(i-1)+j 3）修改位示图，令Mapi，j1，并将对应块分配给该文件。 位示图容量为：32MB/（1KB*8）=4KB 注：对具体的盘块号b，要会计算出具体的i和j 由于寝室马上要熄灯 今天的资料先写到这里 明天看看有改动带崽改 感谢辛苦带2418工作室 呵呵！四、综合题（12分）、操作系统在键盘管理中引入了键盘缓冲区，键盘缓冲区采用循环队列，键盘输入进程pin负责将用户键入的字符存入缓冲区，键盘输出进程pout负责从缓冲区取出字符。假设循环队列的长度为16，请给出利用信号量机制实现进程pin、pout同步及互斥使用键盘缓冲区的算法。要求：（1）定义所使用的信号量，给出信号量的初值、含义。（2）给出进程pin、pout的算法（用伪代码给出，不必给出循环队列操作代码）。答：semaphore mutex=1/互斥使用键盘缓冲区semaphore empty=16 / 开始时键盘缓冲区为空的信号量为16semaphore full=0 / 开始时键盘缓冲区为满的信号量为0char buffer16 / 键盘缓冲区pin()while(1)从键盘得到一个输入字符wait(empty) wait(mutex) 将该字符存入buffersignal(mutex) signal(full) pout()while(1)wait(full) wait(mutex) 从buffer中取出一个字符signal(mutex) signal(empty) -