OS---简答
简答
21. (简答题, 5分) 某分时系统中的进程可能出现如下图所示的状态变化，请回答下列问题: 图片关键字：运行 等待磁盘读文件 等待打印机输出 1)根据图示，该系统应采用什么进程调度策略? 2)把图中每个状态变化的可能原因填写在下表中。 正确答案： （1）从运行态直接可以回到就绪队列的末尾，而且就绪队列按先来先服务排队的，所以调度算法是时间片轮转调度算法。 （2） 1 进度调度 2 等待从磁盘读入文件，因I/O请求进入阻塞状态。 3 等待打印机，因I/O请求进入阻塞状态。 4 打印机打印结束，因I/O完成，进入就绪队列。 5 等待的文件已读入内存，因I/O完成，进入就绪队列。 6 时间片完，进入就绪队列的末尾。 22. (简答题, 5分) 进程之间存在哪几种制约关系?各是什么原因引起的?以下活动各属于哪种制约关系? 1)若干学生去图书馆借书。 2)两队进行篮球比赛。 3)流水线生产的各道工序。 4)商品生产和消费。 正确答案： 答: 直接制约关系：由于进程之间有相互合作关系，并发执行时形成的制约关系。 间接制约关系：由于并发进程共享临界资源，临界资源必须互斥的使用而形成的制约关系。 1) 共享临界资源，互斥使用一本书，间接关系 2) 共享临界资源，互斥使用篮球，间接关系 3) 并发进程相互合作，直接制约关系 4) 并发进程相互合作，直接制约关系 jianda,2= 处理机调度与死锁作业 31. (简答题, 5分)何谓死锁?产生死锁的原因和必要条件是什么?（5分） 正确答案： a.死锁是指多个进程因竞争资源而造成的一种僵局,若无外力作用,这些进程都将永远不能再向前推进; b.产生死锁的原因有二,一是竞争资源,二是进程推进顺序非法; c.必要条件是: 互斥条件,请求和保持条件,不剥夺条件和环路等待条件。 32. (简答题, 5分)高级调度与低级调度的主要任务是什么?为什么要引入中级调度?（5分） 正确答案： 高级调度的主要任务:用于决定把外存上处于后备队列中的哪些作业调入内存,并为它们创建进程,分配必要的资源,然后,再将新创建的进程插入就绪队列上,准备执行。 低级调度的主要任务:用于决定就绪队列中的哪个进程应获得处理机,然后 再由分派程序执行将处理机分配给该进程的具体操作。 引入中级调度的主要目的:是为了提高系统资源的利用率和系统吞吐量。 33. (简答题, 5分)什么是安全状态?避免死锁的关键是什么?（5分） 正确答案： 所谓安全状态,是指系统能按某种进程顺序(P1,P2,…,Pn)(称〈P1,P2,…,Pn〉序列为安全序列),来为每个进程Pi分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列,则称系统处于不安全状态。 避免死锁的关键在于:系统在进行资源分配时,如何使系统不进入不安全状态。 34. (简答题, 5分)处理死锁有哪些方法?（5分） 正确答案： 处理死锁的方法有:(1)预防死锁。通过设置某些限制条件,去破坏产生死锁的四个必要条件中的一个或几个条件,来预防发生死锁。(2)避免死锁。在资源的动态分配过程中,用某种方法去防止系统进入不安全状态,从而避免发生死锁。(3)检测死锁。通过系统所设置的检测机构,及时地检测出死锁的发生,并精确地确定与死锁有关的进程和资源;然后,采取适当措施,从系统中将已发生的死锁清除掉。(4)解除死锁。当检测到系统中已发生死锁时,须将进程从死锁状态中解脱出来。 jianda,3= 存储器管理 31. (简答题, 30分) 在一个请求分页存储系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给作业的物理块号分别为3和4时，试计算采用下列页面淘汰算法时的缺页率（假设执行时主存中没有页面），并比较结果。 （1）最佳置换算法 （2）先进先出置换算法 （3）最近最久未使用算法 正确答案： （1）最佳置换算法 物理块3块：缺页率 7/12 物理块4块：缺页率 6/12 （2）先进先出置换算法 物理块3块：缺页率 9/12 物理块4块：缺页率 10/12 （3）最近最久未使用算法 物理块3块：缺页率 10/12 物理块4块：缺页率 8/12 32. (简答题, 10分) 有一系统采用分页存储管理方式，内存容量为64KB，有一作业大小是8KB，页面大小为2KB，依次装入内存的第8、9、12、4块。求： （1）逻辑地址十六进制表示为：0AFB（H），求对应的物理地址。 （2）逻辑地址十六进制表示为：1AD8（H），求对应的物理地址。 正确答案： 分析题意可知，页号0，1，2，3分别对应块号8，9，12，4 （1）逻辑地址0AFB(H)由十六进制转化为二进制为：0000 1010 1111 1011 页面地址2048=2的11次方,所以后11位为页内地址；页面4=2的2次方，前几位为页号，所以页号为01=1，页内地址为010 1111 1011=763 所以物理地址=9*2048+763=19195 （2）逻辑地址1AD8（H）)由十六进制转化为二进制为：0001 1010 1101 1000 页面地址2048=2的11次方,所以后11位为页内地址；页面4=2的2次方，前两位为页号，所以页号为011=3 逻辑页号为3，对应物理页号为4，页内地址为010 1101 1000=728 所以物理地址为4*2048+728=8920 jianda,4= 第七章 文件管理作业 26. (简答题, 10分) 文件逻辑结构有哪些类型,并说明各个类型的特点? 答： 从逻辑结构可以将文件分为两大类: 有结构的记录式文件和无结构的流式文件。有结构的文件又可分为三类: (1)顺序文件，指由一系列记录按某种顺序排列所形成的文件,其中的记录可以是定长记录或变长记录; (2)索引文件，指为变长记录建立一-张索引表，为每个记录设置- -个表项，以加.快对记录检索的速度。 (3)索引顺序文件，这是顺序文件和索引文件相结合的产物。它为文件建立一张索引表，为每一组记录中的第一 个记录设置一个表项，以缩短索引表的长度,而.记录检索的速度也不很慢。 27. (阅读理解, 10分) 某操作系统的磁盘文件空间共有500块,若用字长为32为的位视图管理盘空间,试问: (1) (简答题) 位示图需要多少个字? 位示图需要的字数计算：INT（500/32）=16 个字。 (2) (简答题) 第i字第j位对应的块号是多少? 块号b=(i-1)*32+j (3) (简答题) 给出申请/归还一块的工作流程。 申请的过程：顺序扫描位示图、找到空闲块并分配、修改位示图map[i,j]=1。 28. (阅读理解, 15分) 假设用户甲要用到文件A、B、C、E,用户乙要用到文件A、D、E、F。已知:用户甲的文件A与 用户乙的文件A实际上不是同一文件;用户甲与用户乙又分别用文件名C和F共享同一文件;甲、乙两用户的文件E是同 一个文件。请回答下列问题: (1) (简答题) 系统应采用怎样的目录结构才能使两用户在使用文件时不致于造成混乱? 如下图所示。用户甲的主目录名为jia，有四个文件，文件名为a、b、c、e。 用户乙的主目录名为 yi，有四个文件，文件名为 a、d、e、f。 (2) (简答题) 请画出这个目录的结构。 根目录 jia | yi / \ 用户甲目录 用户乙目录 a|b| c | e e|f|d|a (f连c) / | \ \ / | \ a b c e d a (3) (简答题) 两个用户使用了几个共享文件?写出它们的文件名。 两个，a,e 29. (阅读理解, 15分) 某文件系统采用单级索引文件结构,假定文件索引表的每个表项占3个字节存放一个磁盘块的块号,磁盘块的大小为512B。试问: (1) (简答题) (1)该文件系统能支持的最大文件大小是多少字节?能管理的最大磁盘空间是多大? 文件系统可以支持的最大文件为： 341*1KB=341KB 能管理的最大磁盘空间：224*1KB=16GB (2) (简答题) (2)若采用3级索引,该文件系统能支持的最大文件大小是多少字节? 若采用三级索引，则是：341*341*341*1KB=39651821KB=38722.4M 能管理的最大磁盘空间：224*1KB=16GB
老师画的范围
一.进程和线程的比较？ 进程 一个在内存中运行的应用程序。每个进程都有自己独立的一块内存空间，一个进程可以有多个线程，比如 在Windows系统中，一个运行的xx.exe就是一个进程。 线程 进程中的一个执行任务（控制单元），负责当前进程中程序的执行。一个进程至少有一个线程，一个进程可以运行多个线 程，多个线程可共享数据。 进程线程 区别总结 线程具有许多传统进程所具有的特征，故又称为轻型进程(Light—Weight Process)或进程元；而把传统的进程称为重型 进程(Heavy—Weight Process)，它相当于只有一个线程的任务。在引入了线程的操作系统中，通常一个进程都有若干个 线程，至少包含一个线程。 根本区别：进程是操作系统资源分配的基本单位，而线程是处理器任务调度和执行的基本单位 资源开销：每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级 的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小。 包含关系：如果一个进程内有多个线程，则执行过程不是一条线的，而是多条线（线程）共同完成的；线程是进程的一部 分，所以线程也被称为轻权进程或者轻量级进程。 内存分配：同一进程的线程共享本进程的地址空间和资源，而进程之间的地址空间和资源是相互独立的 影响关系：一个进程崩溃后，在保护模式下不会对其他进程产生影响，但是一个线程崩溃整个进程都死掉。所以多进程要比多线程健壮。 执行过程：每个独立的进程有程序运行的入口、顺序执行序列和程序出口。但是线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制，两者均可并发执行 二. 同步机构应遵循哪些基本准则 a. 空闲让进.当无进程处于临界区时，表明临界资源处于空闲状态，允许一个请求进入临界区的进程立即进入临界区，以有效利用临界资源 b. 忙则等待.当已有进程处于临界区时，表面临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问 c. 有限等待.对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态 d. 让权等待.当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态 三.分页存储管理方式逻辑地址转物理地址，十进制和十六进制 例题： 分页存储逻辑地址转物理地址： 例题：已知某个分页系统，页面大小为1K(即1024字节)，某一个作业有4个页面，分别装入到主存的第3、4、6、8块中，求逻辑地址2100对应的物理地址。 页号 物理块号 0 3 1 4 2 6 3 8 分析： 第一步：求逻辑地址的页号：2100 ÷ 1024 = 2 （整除） 第二步：求页内地址：2100 % 1024 = 52 （取余） 第三步：根据逻辑地址的页号查出物理地址的物理块号：即逻辑地址的第2页对应物理地址的第6页。 第四步：求出物理地址：6 × 1024 + 52 = 6196 十六进制逻辑地址转物理地址 例题：一分页存储管理系统中逻辑地址长度为16位，页面大小为4KB字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，求逻辑地址2F6AH对应的物理地址。 页号 物理块号 0 5 1 10 2 11 分析： 第一步：由 “页面大小为4KB字节” 得出，页内地址是二进制的12位（4K=），所以F6A是页内地址，页号也就是2了。 第二步：通过页表查询到物理块号：11。所以物理地址是：BF6A。 jianda,6= 四.常用的几种处理机调度算法优劣特点比较 1、时间片轮转调度算法（RR）：给每个进程固定的执行时间，根据进程到达的先后顺序让进程在单位时间片内执行，执行完成后便调度下一个进程执行，时间片轮转调度不考虑进程等待时间和执行时间，属于抢占式调度。优点是兼顾长短作业；缺点是平均等待时间较长，上下文切换较费时。适用于分时系统。 2、先来先服务调度算法（FCFS）：根据进程到达的先后顺序执行进程，不考虑等待时间和执行时间，会产生饥饿现象。属于非抢占式调度，优点是公平，实现简单；缺点是不利于短作业。 3、优先级调度算法（HPF）：在进程等待队列中选择优先级最高的来执行。 4、多级反馈队列调度算法：将时间片轮转与优先级调度相结合，把进程按优先级分成不同的队列，先按优先级调度，优先级相同的，按时间片轮转。优点是兼顾长短作业，有较好的响应时间，可行性强，适用于各种作业环境。 5、高响应比优先调度算法：根据“响应比=（进程执行时间+进程等待时间）/ 进程执行时间”这个公式得到的响应比来进行调度。高响应比优先算法在等待时间相同的情况下，作业执行的时间越短，响应比越高，满足段任务优先，同时响应比会随着等待时间增加而变大，优先级会提高，能够避免饥饿现象。优点是兼顾长短作业，缺点是计算响应比开销大，适用于批处理系统。 八.常用的磁盘调度算法，哪个会产生“饥饿”、“磁臂粘着”现象 短作业/进程优先算法（SJF/SPF) 优先级调度算法 会产生“饥饿” 在SSTF、SCAN及CSCAN几种调度算法中，都有可能出现“磁臂粘着”. (磁臂粘着现象:有一个或几个进程对某一磁道有着较高的访问频率，即他们反复地请求对一个磁道进行了I/O请求，从而垄断了整个磁盘设备，这一现象称为磁臂粘着) 九.I/O控制方式 1、直接程序控制方式 直接程序控制方式由用户进程直接控制主存或 CPU 和外围设备之间的信息传送。直接程序控制方式又称为询问方式，或忙/等待方式。通过 I/O 指令或询问指令测试 I/O 设备的忙/闲标志位，决定主存与外围设备之间是否交换一个字符或一个字。 直接程序控制方式流程图 流程图概述直接程序控制方式的工作流程如下： ① 当用户进程需要输入数据时，通过 CPU 向控制器发出一条 I/O 指令，启动设备输入数据，同时把状态寄存器中的忙/闲状态 busy 置为1 ② 用户进程进入测试等待状态，在等待过程中，CPU 不断地用一条测试指令检查外围设备状态寄存器中的 busy 位，而外围设备只有在数据传入控制器的数据寄存器之后，才将该 busy 位置为0,。 ③ 处理器将数据寄存器中的数据取出，送入主存指定单元，完成一个字符的I/O操作，接着进行下一个数据的 I/O 操作 直接程序控制方式虽然简单，不需要多少硬件的支持，但由于高速的 CPU 和低速的 I/O 设备之间的速度上不匹配，因此，CPU 与外围设备只能串行工作，使 CPU 的绝大部分时间都处于等待是否完成 I/O 操作的循环测试中，造成 CPU 的极大浪费，外围设备也不能得到合理的使用，整个系统的效率很低。因此，这种I/O控制方式只适合于 CPU 执行速度较慢，且外围设备较少的系统。 2、中断驱动控制方式 为了减少程序直接控制方式下 CPU 的等待时间以及提高系统的并行程度，系统引入了中断机制。中断机制引入后，外围设备仅当操作正常结束或异常结束时才向 CPU 发出中断请求。在 I/O 设备输入每个数据的过程中，由于无需 CPU 的干预，一定程度上实现了 CPU 与 I/O设备的并行工作。仅当输入或输出完一个数据时，才需 CPU 花费极短的时间做中断处理。 中断驱动方式流程图 存在的问题：由于I/O操作直接由 CPU 控制，每传送一个字符或一个字，都要发生一次中断，仍然占用了大量的 CPU 处理时间，因此可以通过为外围设备增加缓冲寄存器存放数据来减少中断次数。 上述两种方法的特点都是以 CPU 为中心，数据传送通过一段程序来实现，软件的传送手段限制了数据传送的速度。接下来介绍的这两种I/O 控制方式采用硬件的方法来显示 I/O 的控制 3.直接存储器访问控制方式 直接存储器访问控制方式又称 DMA（Direct Memory Access）方式。为了进一步减少 CPU 对 I/O 操作的干预，防止因并行操作设备过多使 CPU 来不及处理或因速度不匹配而造成的数据丢失现象，引入了 DMA 控制方式。在 DMA 控制器的控制下，采用窃取或挪用总线控制权，在设备和主存之间开辟直接数据交换通道，成批地交换数据，而不必让 CPU 干预。 DMA方式的特点： ① 数据传送以数据块为基本单位 ② 所传送的数据从设备直接送入主存，或者从主存直接输出到设备上 ③ 仅在传送一个或多个数据块的开始和结束时才需 CPU 的干预，而整块数据的传送则是在控制器的控制下完成。 DMA方式和中断驱动控制方式相比，减少了 CPU 对 I/O 操作的干预，进一步提高了 CPU 与 I/O 设备的并行操作程度。 DMA方式的线路简单、价格低廉，适合高速设备与主存之间的成批数据传送，小型、微型机中的快速设备均采用这种方式，但其功能较差，不能满足复杂的 I/O 要求。 4、通道控制方式 通道，独立于 CPU 的专门负责输入输出控制的处理机，它控制设备与内存直接进行数据交换。有自己的通道指令，这些指令由 CPU 启动，并在操作结束时向 CPU 发出中断信号。 直接程序控制方式和中断程序控制方式适合于低速设备的数据传送，而 DMA 方式虽然适合于高速设备的数据传送，但一个 DMA 控制器只能控制少量的同类设备，这远远不能满足大型计算机系统的需要。通常，一个大型计算机需要连接大量的高速和低速设备，通道控制方式可以满足这个要求。（DMA和通道控制方式的主要区别——能否满足大型计算机系统的既能处理高速设备又能处理低速设备的需要） 通道控制方式，实现了CPU、通道和I/O设备三者的并行操作，从而更加有效地提高整个系统的资源利用率。例如，当 CPU 要完成一组相关的读（或写）操作时，只需要向 I/O 通道发出一条 I/O 指令，指出其所要执行的通道程序的首址和要访问的I/O设备，通道接收到该指令后，通过执行通道程序便可完成 CPU 指定的 I/O 任务。可见，通道只是在 I/O 操作的起始和结束时向 CPU 发出 I/O 中断申请，相对于之前的控制方式进一步减少了 CPU 的干预程度。 jianda,8= 设计题：进程同步算法（P、V操作），作业中的大题进程同步问题理解透彻 P-V操作概念 数据结构 变量定义为一个二元矢量（S，q） S:整数，初值为负 q：PCB队列，初值为空集 struct { int s; pointer_PCB q; } 操作： P操作：可能使进程在调用处阻塞 S值减1 若差大于或等于0，该进程继续 若差小于0，则该进程阻塞并加入队列q中，并转调度函数 p(S,q) { S=S-1; if (S<0) { Insert(Caller,q); Block (Caller); 转调度函数(); } } V操作：可能会唤醒阻塞的进程 S值加1 若和大于0，该进程继续 若和小于或等于0，该进程继续同时从q中唤醒一个进程 V(S,q) { S=S+1; if (S<0) { Remove (q,pid); Wakeup (pid); } } 三、P-V操作解决互斥问题 本质：实现对临界区的互斥访问（允许最多一个进程处于临界区） 应用过程： 进入临界区之前先执行P操作（相当于上锁操作） 离开临界区之后再执行V操作（相当于开锁操作） S的初值要设计合理。 四、P-V操作解决同步问题 同步机制实质： 运行条件不满足时，能让进程暂停。 运行条件满足时，能让进程立即继续 基本思路： 暂停当前进程：在关键操作之前执行p操作（必要时可暂停） 继续进程：在关键操作之后执行V操作（必要时唤醒合作进程） 定义有意义的信号量S，并设置合适的初值。（S能明确地表示运行条件）
计算
23. (计算题, 10分)对于哲学家进餐问题，请给出一种不会死锁的解决方案。 正确答案： 答：给出一种限制人数方式： semaphore chopstick[5]={1,1,1,1,1}, LR=4;//代表桌子上最多做4人 第i个哲学家的活动如下： while(1) { 思考； wait(LR); wait(chopstick[i]); wait(chopstick[(i+1)%5]); 进餐； signal(chopstick[i]); signal(chopstick[(i+1)%5]); signal(LR); 思考； } 24. (计算题, 10分) 2、有桥如下图所示。车流方向如箭头所示。回答如下问题:假设桥上每次只能有一辆车行驶，试 用信号灯的P,V操作实现交通管理。 图关键字：北桥南 正确答案： 答：semaphore bmutex=1;//桥互斥通过 NtoS://由北向南 while(1) { wait(bmutex); 通过桥； signal(bmutex); } StoN://由南向北 while(1) { wait(bmutex); 通过桥； signal(bmutex); } 25. (计算题, 10分) 某博物馆最多可容纳800人同时参观，有一个出入口，该出入口一次仅允许一人通过。参观者的活动描述如下: cobegin 参观者进程i: { … 进门。 … 参观; … 出门; … } coend 请添加必要的信号量和P,V [或wait(), signal()]操作，以实现上述过程中的互斥与同步。要求写出完整的 过程，说明信号量的含义并赋初值。 正确答案： 答： semaphore empty=800;//最多容纳800人。 semaphore mutex=1;//互斥通过出入口 cobegin 参观者进程i: { wait(empty); wait(mutex); 进门。 signal(mutex); 参观; wait(mutex); 出门; signal(mutex); signal(empty); } coend jisuan,2= 处理机调度与死锁作业 三. 计算题（共2题，20分） 35. (计算题, 10分) 假定在单CPU条件下有下列要执行的作业： 作业 运行时间 优先级 1 10 2 2 4 3 3 3 5 作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。（10分） （1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。 （2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？ （3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？ 正确答案： (1) 非抢占式优先级算法 | 作业1 | 作业3 | 作业2 | ——————————————————> t 0 10 13 17 (2)(3) 作业 | 到达时间 | 运行时间 | 完成时间 | **周转时间 **| **带权周转时间 ** 1 0 10 10 10 1.0 2 1 4 17 16 4.0 3 2 3 13 11 3.7 ———————————————————————————— 平均周转时间 ： 12.3 平均带权周转时间 ： 2.9 36. (计算题, 10分) 在银行家算法中，若出现下述资源分配情况： Process Allocation Need Available P0 0032 0012 1622 P1 1354 2356 P3 0332 0652 P4 0014 0656 试问：（10分） （1）该状态是否安全？ （2）若进程P2提出请求Request(1，2，2，2)后，系统能否将资源分配给它？ 正确答案： （1）该状态是安全的，因为存在一个安全序列< P0 P3 P4 P1 P2>。下表为该时刻的安全序列表。 \ 资源 \ 情况 Work Need Allocation Work+Allocation Finish 进程 P0 1 6 2 2 0 0 1 2 0 0 3 2 1 6 5 4 true P3 1 6 5 4 0 6 5 2 0 3 3 3 1 9 8 7 true P4 1 9 8 7 0 6 5 6 0 0 1 4 1 9 9 11 true P1 1 9 9 11 1 7 5 0 1 0 0 0 2 9 9 11 true P2 2 9 9 11 2 3 5 6 1 3 5 4 3 12 14 17 true （2）若进程P2提出请求Request(1，2，2，2)后，系统不能将资源分配给它，若分配给进程P2，系统还剩的 资源情况为（0，4，0，0），此时系统中的资源将无法满足任何一个进程的资源请求，从而导致系统进入不 安全状态，容易引起死锁的发生。