操作系统重点.docx

简答第三章 进程管理(小概念)1.进程和程序的区别:l 进程是动态的，程序是静态的：程序是有序代码的集合,属于静态的文本概念；进程是程序的一次执行。l 进程是并发的，会相互制约，程序是顺序的。l 进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。l 进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。l 进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。2.进程控制块PCB:l 描述信息(进程名或进程标识号、用户名或用户标识号、家族关系)l 控制信息（进程当前状态、进程优先级、程序开始地址、各种计时信息、通信信息）l 资源管理信息1) 占用内存大小及其管理用数据结构指针2) 对换或覆盖用的有关信息3) 共享程序的大小及起始地址4) I/O设备号，传送的数据的长度，缓冲区地址，缓冲区长度以及所用设备的有关数据结构指针5) 指向文件系统的指针及有关标识l CPU现场保护结构3.产生死锁的必要条件：（大概念）综合ppt（银行家算法）互斥条件、不可剥夺条件、部分分配、环路条件。破环其中的一个条件，死锁就可以解除。4死锁预防：l 打破资源的互斥和不可剥夺这两个条件l 打破资源的部分分配条件5.进程通信的实例管道：（基本概念）是一种共享文件模式，基于文件系统，连接于两个进程之间，以先进先出的方式实现消息的单向传送。注意：（1）通过系统调用write()和read()进行管道的读写。（2）进程间要进行双向通信，通常需要定义两个管道。（3）只适用于父子进程之间的通信。管道能够把信息从一个进程的地址空间拷贝到另一个进程的地址空间。第四章 处理机调度1.在多道程序系统中，一个作业从提交到执行，通常都要经历多级调度（1）如高级调度、低级调度、中级调度以及IO调度等系统的运行性能在很大程度上取决于调度。高级调度：主要用于批处理系统。其设计目标是最大限度地发挥各种资源的利用率和保持系统内各种活动的充分并行低级调度：又称进程调度或短程调度，其主要功能是按照某种原则将处理机分配给就绪进程。执行低级调度功能的程序称为进程调度程序，由它实现处理机在进程间的转换。它必须常驻主存，是操作系统内核的主要部分。中级调度：中级调度又称中程调度(Medium-Term Scheduling) 引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。调度类型运行频率运行时间算法复杂性进程调度高短低中程调度中等较短中等作业调度低长高（2）如吞吐量的大小、周转时间的长短、响应的及时性等调度是多道系统的关键2. 作业（JOB）是用户在一次算题过程中或一次事务处理中，要求计算机系统所做的工作的集合。（小概念）（1）作业是比进程更广泛的概念，不仅包含了通常的程序和数据，而且还配有一份作业说明书，系统根据作业说明书对程序运行进行控制。在批处理系统中，以作业为单位从外存调入内存（2）用户为了让计算机完成某个特定任务，首先编写成源程序，然后提交给计算机通过编译或汇编、连接、装配、运行等步骤，最终由计算机送出用户所需要的运行结果。从计算机管理的角度看，上述一系列的由计算机执行的任务的集合就是作业。3多级反馈队列调度算法：不必事先知道各进程所需执行时间，可满足各种进程需要，是目前被公认较好的调度算法。n 设置多个就绪队列，每个队列赋予不同的优先级。队列按FCFS原则排列n 各队列时间片不同n 当一个新进程进入内存后，首先放在第一队列尾，按FCFS原则调度；如果该时间片内未结束，转入第二队队列尾；直到最后的第N队列，在第N队列采取按时间片轮转方式调度n 仅当第I队列空闲时，才调度第i+1队列n 如有新进程进入优先级较高的队列，则剥夺CPU执行新进程，旧进程放入原队列尾第五章 存储系统1. 地址变换：静态地址重定位：是在虚拟空间程序执行之前由装配程序完成地址映射工作。（一口气换完）动态地址重定位：在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换成内存地址。静态重定位的优点：（1）不需要硬件的支持，使用静态重定位方法进行地址变化无法实现虚拟存储器。（2）必须占用连续的内存空间，这就难以做到程序和数据的共享。动态重定位的优点：（1） 可以对内存进行非连续分配。显然对于同一进程的各分散程序段，只要把各程序段在内存中的首地址统一存放在不同的BR中，就可以由地址变换机构变换得到正确的内存地址。（2） 动态动态重定位提供了实现虚拟存储器的基础。因为动态重定位不要求在作业执行前为所有程序分配内存，也就是说，可以部分地，动态地分配内存。从而，可以在动态重定位的基础上，在执行期间采用请求方式为那些不在内存中的程序段分配内存，以达到内存扩充的目的。（3） 有利于程序段的共享。2. 覆盖技术: 一个程序并不需要一开始就把它的全部指令和数据都装入内存后再执行。单CPU系统中，每一时刻事实上只能执行一条指令。可以把程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区。通常，这些程序段都被保存在外存中，当有关程序段的先头程序段已经执行结束后，再把后续程序段调入内存覆盖前面的程序段。这使得用户看来，好像内存扩大了，从而达到了内存扩充的目的。3. Belady现象：（是非题）P121 5.24 在分页式虚拟存储器管理中，发生缺页时的置换算法采用FIFO（先进先出）算法时，出现分配的页面数增多但缺页率反而提高的异常现象。另外：不是页面数越多缺页越少的。4.内存的分配与回收为了有效合理地利用内存，设计内存的分配和回收方法时，必须考虑和确定以下几种策略和数据结构：(1) 分配结构：登记内存使用情况，供分配程序使用的表格与链表。例如内存空闲区表、空闲区队列等。(2) 放置策略：确定调入内存的程序和数据在内存中的位置。这是一种选择内存空闲区的策略。(3) 交换策略：在需要将某个程序段和数据调入内存时，如果内存中没有足够的空闲区，由交换策略来确定把内存中的哪些程序段和数据段调出内存，以便腾出足够的空间。(4) 调入策略：外存中的程序段和数据段什么时间按什么样的控制方式进入内存。调入策略与5.1.3节中所述内外存数据流动控制方式有关。(5) 回收策略：回收策略包括二点，一是回收的时机，二是对所回收的内存空闲区和已存在的内存空闲区的调整。5.地址变换第八章 文件系统1.位示图：文件存储空间管理:空闲文件目录、空闲块链、位示图。用二进制位表示磁盘中某一块的使用情况。“0”表示空闲，“1”表示已分配，或者相反。磁盘上所有盘块都有一个二进制位与之对应。所有盘块对应的位构成一集合，称为位示图。通常用mn个位构成位示图。mn等于盘块总数。已知块号，则磁盘地址： 柱面号块号/（磁头数扇区数） 磁头号（块号mod （磁头数扇区数）/扇区数 扇区号（块号mod （磁头数扇区数）mod 扇区数已知磁盘地址：块号柱面号（磁头数扇区数）磁头号扇区数扇区号5.成组链接法：(1)文件区中的所有空闲盘块，分成若干个组。（2）将每一组的盘块总数N和该组所有盘块号记入其前一组的第一个盘块中。（3）将第一组的盘块总数和所有的盘块号，记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。（4）将最末一组的盘块号分别记入其前一组中，盘块总数中存放0作为空闲盘块链的结束标志。记住一点的是，分配过程是从前往后分配，先分配第一组，然后分配第二组回收过程是正好相反，从后往前分配，先将释放的空闲块放入第一组，第一组满了，再开辟一组，之前的第一组变为第二组2. 空闲盘块的分配与回收（1） 在系统回收空闲盘块时需调用盘块回收过程进行回收。（2） 它将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中的空闲盘块号数目已达100时，表示栈已满，便将现有栈中的100个盘块号记入新回收的盘块中，再将其盘块号作为新栈底。第九章 设备管理“设备管理的功能和任务（选择题，是非题和大题）”1.设备管理程序一般要提供下述功能：（1）提供和进程管理系统的接口。当进程要求设备资源时，该接口将进程要求转达给设备管理程序；（2）进行设备分配。按照设备类型和相应的分配算法把设备和其他有关的硬件分配给请求该设备的进程，并把未分配到所请求设备或其他有关硬件的进程放入等待队列；（3）实现设备和设备、设备和CPU等之间的并行操作。除控制状态寄存器、数据缓冲寄存器等的控制器之外，对应于不同的I/O控制方式，还要DMA( Directed Memory Access)通道等硬件支持。在设备分配程序根据进程要求分配设备、控制器和通道或DMA等之后，通道或DMA将自动完成设备和内存之间的数据传送工作，从而完成并行操作。在无通道或DMA时，由设备管理程序利用中断技术来完成操作；（4）进行缓冲区管理。一般CPU的执行速度和访问内存速度都比较高，而外设的数据流通速度则低得多(如键盘)，为减少外设和内存与CPU之间的数据速度不匹配的问题，系统中一般设有缓冲区(器)来暂放数据。设备管理程序负责进行缓冲区分配、释放及有关的管理工作。2.数据传送控制方式外围设备和内存之间的常用数据传送控制方式有4种： 程序直接控制方式； 中断控制方式； DMA方式； 通道方式。3. 缓冲池的管理对缓冲池的管理由如下几个操作组成：（1）从三种缓冲区队列中按一定的选取规则取出一个缓冲区的过程take_buf(type)；（2）把缓冲区按一定的选取规则插入相应的缓冲区队列的过程add_buf(type，number)；（3）供进程申请缓冲区用的过程get_buf(type，number)；（4）供进程将缓冲区放入相应缓冲区队列的过程put_buf(type，work_buf)。（5）其中，参数type表示缓冲队列类型，number为缓冲区号，而work_buf则表示工作缓冲区类型。4.系统把各缓冲区按其使用状况连成三种队列，其队列构成如图所示：空白缓冲队列em，其队首指针为F(em)，队尾指针为L(em)；装满输入数据的输入缓冲队列in，其队首指针为F(in)，队尾指针为L(in)；装满输出数据的输出缓冲队列out，其队首指针为F(out)，队尾指针为L(out)。缓冲区队列5. 中断处理过程：（1）CPU检查响应中断的条件是否满足。CPU响应中断的条件是：有来自于中断源的中断请求、CPU允许中断。如果中断响应条件不满足，则中断处理无法进行。（2）如果CPU响应中断，则CPU关中断，使其进入不可再次响应中断的状态。（3）保存被中断进程现场。为了在中断处理结束后能使进程正确地返回到中断点，系统必须保存当前处理机状态字PSW和程序计数器PC等的值。这些值一般保存在特定堆栈或硬件寄存器中。（4）分析中断原因，调用中断处理子程序。在多个中断请求同时发生时，处理优先级最高的中断源发出的中断请求。在系统中，为了处理上的方便，通常都是针对不同的中断源编制有不同的中断处理子程序(陷阱处理子程序)。这些子程序的入口地址(或陷阱指令的入口地址)存放在内存的特定单元中。再者，不同的中断源也对应着不同的处理机状态字PSW。这些不同的PSW被放在相应的内存单元中。存放的PSW与中断处理子程序入口地址一起构成中断向量。显然，根据中断或陷阱的种类，系统可由中断向量表迅速地找到该中断响应的优先级、中断处理子程序(或陷阱指令)的入口地址和对应的PSW。（5）执行中断处理子程序。对陷阱来说，在有些系统中则是通过陷阱指令向当前执行进程发软中断信号后调用对应的处理子程序执行。（6）退出中断，恢复被中断进程的现场或调度新进程占据处理机。（7）开中断，CPU继续执行。6.设备分配过程：（设备分配原则）（大点）分配策略：先请求先分配、优先级高者先分配设备控制表DCT(Device Control Table) 系统设备表SDT(System Device Table) 控制器表COCT(COntroler Control Table) 通道控制表CHCT(CHannel Control Table)7.I/0进程控制（选择题）（1）I/O控制的引入从用户进程的输入输出请求开始，给用户进程分配设备和启动有关设备进行I/O操作，以及在I/O操作完成之后响应中断，进行善后处理为止的整个系统控制过程称为I/O控制。（2）I/O控制的功能 I/O控制过程首先收集和分析调用I/O控制过程的原因：是外设来的中断请求？ 还是进程来的I/O请求？然后，根据不同的请求，分别调用不同的程序模块进行处理。综合题第三章 进程管理1.生产-消费问题：2.司机-售票员问题：4. 哲学家就餐：5.理发师问题：理发店里有一个理发师、一把理发椅、n把供等候理发的顾客坐的椅子。如果没有顾客，则理发师便在理发椅上睡觉。当一个顾客到来时，他必须先叫醒理发师，进行理发。如果理发师在理发时又有顾客到来，则如果有空椅子可坐，他就坐下来等，如果没有空椅子，他就离开。为理发师和顾客各编写一段程序描述他们的行为，要求不能带有竞争条件。设三个信号量：customers，用来记录等待理发师的顾客数（不包括正在理发的顾客），初值为0；barbers，记录正在等候顾客的理发师数，初值为0；mutex，用于互斥，初值为1。还需一个变量waiting，初值为0，也用于记录等候的顾客数，实际上是customers的一个副本。之所以使用waiting是因为无法读取信号量的当前值。在该解法中，进入理发店的顾客必须先看等待的 顾客数，如果少于椅子数，他留下来等，否则他就离开。第四章 处理机调度（调度算法，具体题目在笔记本上）第五章 存储管理1.段页式管理第八章 文件系统2.在某FAT16文件系统中，FAT表的每个表项用16位表示，每簇64扇区，扇区的大小为512字节。有一个文件，其起始簇号为0002H，如下图所示。 FAT表中的表目为FFFFH，表示该簇为文件的最后一簇；表目为0000H，表示该簇为空闲蔟。问：(1)该文件占用了多大的磁盘存储空间？ 由下图可知，该文件占用了2、4、7簇，共512*64*3=98304B=96K(2)若要为该文