操作系统复习.doc

第一章操作系统引论1.1.1目标：有效性（早期推动操作系统发展最主要的动力） （1） 提高系统的资源利用率； （2） 提高系统的吞吐量。方便性 可扩充性 开放性1.1.2作用： 1.OS作为用户与计算机硬件系统之间的接口含义：OS处于用户与计算机硬件系统之间，用户通过OS来使用计算机系统。 用户使用计算机的三种方式：命令方式 系统调用方式 图形、窗口方式2.OS作为计算机系统资源的管理者（系统资源：处理器、存储器、I/O设备以及信息） 3.OS实现了对计算机资源的抽象1.3 操作系统的基本特性（并发、共享、虚拟、异步）1.3.1.并发性 操作系统最重要的特征，其他特征都是以并发特征为前提。 并行性指两个或多个事件在同一时刻发生； 并发性指两个或过个事件在同一时间间隔内发生。1.3.2共享性：是指系统中的资源可供内存中多个并发执行的进程共同使用。主要实现资源共享的方式：互斥共享方式；同时访问方式。1.3.3虚拟技术：是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。 在操作系统中利用了两种方式实现虚拟技术：时分复用技术和空分复用技术。1.4操作系统的主要功能主要功能分类处理机管理功能创建和撤销进程，对诸进程的运行进行协调，实现进程之间的信息交换，以及按照一定的算法把处理机分配给进程进程控制 进程同步 进程通信 调度存储器管理功能为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率以及能从逻辑上扩充内存。内存分配 内存保护 地址映射 内存扩充设备管理功能完成用户进程提出的I/O请求；为用户进程分配其所需的I/O设备；提高CPU和I/O设备的利用率；提高I/O的速度；方便用户使用I/O设备。缓冲管理 设备分配 设备处理 文件管理功能对用户文件和系统文件进行管理，以方便用户使用，并保证文件的安全性。文件存储空间的管理 目录管理 文件的读/写管理和保护第二章进程管理：基本功能：进程控制。1.程序顺序执行时的特征：顺序性、封闭性、可再现性。3.进程的特征：结构特征、动态性、并发性、独立性、异步性。4.进程实体：由程序段、相关的数据段、和PCB三部分构成。5.进程的定义：进程是程序的一次执行； 进程是一个程序及其数据在处理机上顺序执行时所发生的活动； 进程程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。6.进程的三种基本状态：就绪状态、执行状态、阻塞状态。进程在三个基本状态之间转换的典型原因.a. 处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态变为执行状态。b. 当前进程因发生某事件而无法执行，如访问已被占用的临界资源，就会使进程由执行状态转变为阻塞状态。c. 当前进程因时间片用完而被暂停执行，该进程便由执行状态转变为就绪状态。8.进程控制块（PCB）是操作系统中最重要的记录型数据，是进程存在的唯一标志；存储进程信息。9.进程控制块的作用：使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。11.进程控制块的组织方式：链接方式、索引方式。12.临界资源及进程对临界资源的互斥访问16.同步机制应遵循的规则：空闲让进、忙则等待、有限等待、让权等待。17.信号量机制：整型信号量、记录型信号量、AND型信号量、信号量集。P51、 P58生产者与消费者问题。18.信号量机制的应用：利用信号量实现进程互斥；利用信号量实现前趋关系。19.进程通信（高级通信机制）类型：共享存储器系统、消息传递系统、管道通信系统。20.进程通信方式：直接通信方式、间接通信方式。21进程互斥（游乐场、订票系统例子）进程同步（生产者-消费者例子）（信号量机制实现、写出伪代码）。21.为什么说PCB是进程存在的唯一标志?在进程的整个生命周期中，系统总是通过其PCB对进程进行控制，系统是根据进程的PCB而不是任何别的什么而感知到该进程的存在的，所以说，PCB是进程存在的唯一标志23.试从物理概念上说明记录型信号量wait和signal。 Wait(S)：当S.value0时，表示目前系统中这类资源还有可用的，执行一次wait操作，意味着进程请求一个单位的该类资源，是系统中可供分配的该类资源减少一个，因此描述为S.value:=S.value-1；当S.value0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。 Signal(S)：执行一次signal操作，意味着释放一个单位的可用资源，使系统中可供分配的该类资源数增加一个，故执行S.value:=S.value+1操作。若加1后S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，因此应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。23.在生产者消费者问题中，如果缺少了signal(full)或signal(empty)，对执行结果将会有何影响？ 如果缺少了signal(full)，那么表明从第一个生产者进程开始就没有对信号量full值改变，即使缓冲池存放的产品已满了，但full的值还是0，这样消费者进程在执行wait(full)时会认为缓冲池是空的而取不到产品，那么消费者进程则会一直处于等待状态。 如果缺少了signal(empty)，例如在生产者进程向n个缓冲区投满产品后消费者进程才开始从中取产品，这时empty=0，full=n，那么每当消费者进程取走一个产品时empty并没有被改变，直到缓冲池中的产品都取走了，empty的值也一直是0，即使目前缓冲池有n个空缓冲区，生产者进程要想再往缓冲池中投放产品会因申请不到空缓冲区而被阻塞。24. 在生产者消费者问题中，如果将两个wait操作即wait(full)和wait(mutex)互换位置，或者将signal(mutex)和signal(full)互换位置，结果会如何？ 在生产者消费者问题中，如果将两个wait操作，即wait(full)和wait(mutex)互换位置后，可能引起死锁。考虑系统中缓冲区全满时，若一生产者进程先执行了wait(mutex)操作并获得成功，则当再执行wait(empty)操作时，它将因失败而进入阻塞状态，它期待消费者进程执行signal(empty)来唤醒自己，在此之前，它不可能执行signal(mutex)操作，从而使试图通过执行wait(mutex)操作而进入自己的临界区的其他生产者和所有消费者进程全部进入阻塞状态，这样容易引起系统死锁。 若signal(mutex)和signal(full)互换位置后只是影响进程对临界资源的释放次序，而不会引起系统死锁，因此可以互换位置。第三章处理机调度与死锁1.处理机调度层次：高级调度（作业调度）、低级调度（进程调度）、中级调度（中程调度）。高级调度的主要任务：用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程，分配必要的资源，然后，再将新创建的进程插入就绪队列上，准备执行。低级调度的主要任务：用于决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行将处理机分配给该进程的具体操作。2.低级调度的功能：保存处理机的现场信息、按某种算法选取进程、把处理器分配给进程。5.抢占调度方式原则：优先权优先、短作业（进程）优先原则、时间片原则。6.引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。9.调度算法：（1）先来先服务（FCFS）和短作业优先调度算法；思想、特点、计算 （2）高优先权优先调度算法；思想、特点 （3）基于时间片地轮转调度算法； 13何谓死锁？产生死锁的原因和必要条件是什么？处理死锁的基本方法？a.死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将永远无法再向前推进。b.产生死锁的原因有二，一是竞争资源，二是进程间推进顺序非法。c.必要条件是: 互斥条件，请求和保持条件，不剥夺条件和环路等待条件。 d预防死锁、避免死锁、检测死锁、解除死锁。14.系统安全性：是指系统能按某种进程顺序（P1，P2，P3Pn）（称P1,p2Pn序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。第四章存储器管理 1.重定位的定义：通常是把在装入时对目标程序中指令和数据的修改过程称为重定位。2.对换的概念：是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需的程序和数据调入内存。对换是提高内存利用率的有效措施。3.基本分页存储管理方式（地址转换计算）2.程序的装入方式：绝对装入方式适用于单道程序环境中、可重定位装入方式和动态运行时装入方式适用于多道程序环境中4.连续分配方式是指为一个用户程序分配一个连续的内存空间。 四种分配方式：单一连续分配、固定分区分配、动态分区分配、动态重定位分区分配。5.动态分区分配是根据进程的实际需要，动态地为之分配内存空间。 分区分配中的数据结构：空闲分区表（分区序号，分区始址，分区的大小）、空闲分区链。 分区分配方法：首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法、快速适应算法。分区存储管理中常采用哪些分配策略？比较它们的优缺点。分区存储管理中常采用的分配策略有：首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法。a.首次适应算法的优缺点：保留了高址部分的大空闲区，有利于后到来的大型作业的分配；低址部分不断被划分，留下许多难以利用的、小的空闲区，且每次分区分配查找时都是从低址部分开始，会增加查找时的系统开销。b.循环首次适应算法的优缺点：使内存中的空闲分区分布得更为均匀，减少了查找时的系统开销；缺乏大的空闲分区，从而导致不能装入大型作业。c.最佳适应算法的优缺点：每次分配给文件的都是最适合该文件大小的分区；内存中留下许多难以利用的小的空闲区。d.最坏适应算法的优缺点：给文件分配分区后剩下的的空闲区不至于太小，产生碎片的几率最小，对中小型文件分配分区操作有利；使存储器中缺乏大的空闲区，对大型文件的分区分配不利。 e.快速适应算法的优缺点：查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可；在分区归还主存时算法复杂，系统开销较大。6.请求分页存储管理方式（地址转换计算）7.页面置换算法（最佳置换算法思想；FIFO、LRU思想、计算） 最佳置换算法是理论上的算法，其所选择的被淘汰的页面，将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。FIFO 算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。LRU置换算法是选择最近最未久使用的页面予以淘汰。8虚拟存储器的定义：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。9.虚拟存储器的特征：多次性、对换性、虚拟性。在一个请求分页系统中，采用FIFO页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M分别为3和4时，试计算在访问过程中所发生的缺页次数和缺页率，并比较所得结果。M=3M=44 3 2 1 4 3 5 4 3 2 1 54441115553334442222233314444555511333344445222233331111222M=3时，采用FIFO页面置换算法的缺页次数为9次，缺页率为75%；M=4时，采用FIFO页面置换算法的缺页次数为10次，缺页率为83%。由此可见，增加分配给作业的内存块数，反而增加了缺页次数，提高了缺页率，这种现象被称为是Belady现象。第五章设备管理1.I/O系统的组成：I/O设备、设备控制器、I/O通道、总线系统。1.I/O设备的性能指标：设备使用特性、数据传输速率、数据传输单位、设备共享属性。2.设备控制器的主要职责是控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换。3.设备控制器的功能：接收和识别命令、数据交换、标识和报告设备的状态、地址识别、数据缓冲、差错控制。4.设备控制器的组成：设备控制器与处理机的接口、设备控制器与设备的接口、I/O逻辑。6.I/O控制方式及特点：程序I/O方式、中断驱动I/O控制方式、DMAI/O控制方式、I/O通道控制方式。程序I/O方式适用于早期的计算机系统中，并且是无中断的计算机系统；中断驱动I/O控制方式是普遍用于现代的计算机系统中； DMA I/O控制方式适用于I/O设备为块设备时在和主机进行数据交换的一种I/O控制方式；当I/O设备和主机进行数据交换是一组数据块时通常采用I/O通道控制方式，但此时要求系统必须配置相应的通道及通道控制器。3、公用缓冲池的组成及形成的队列：空缓冲区、装满输入数据的缓冲区、装满输出数据的缓冲区； 空缓冲队列emq、输入队列inq、输出队列outq4、逻辑设备名到物理设备名的映射，申请设备时应该使用逻辑设备名5、设备中断处理程序的处理步骤 (1)唤醒被阻塞的驱动（程序）进程；（2）保护被中断进程的CPU环境；（3）转入相应的设备处理程序； （4）中断处理；（5）恢复被中断进程的现场。6、SPOOLING系统的组成：输入井和输出井；输入缓冲区和输出缓冲区；输入进程SPi和输出进程SPo7.引入缓冲的原因：（1）缓和CPU和I/O设备间速度不匹配的矛盾；（2）减少对CPU的中断频率，放宽对CPU中断响应时间的限制；（3） 提高CPU和I/O设备之间的并行性。8.在实现后台打印时，SPOOLING系统应为请求I/O的进程提供哪些服务？在实现后台打印时，SPOOLing系统应为请求I/O的进程提供以下服务：（1）由输出进程在输出井中为之申请一空闲盘块区，并将要打印的数据送入其中；（2）输出进程再为用户进程申请一张空白的用户打印表，并将用户的打印要求填入其中，再将该表挂到请求打印队列上。（3）一旦打印机空闲，输出进程便从请求打印队列的队首取出一张请求打印表，根据表中的要求将要打印的数据从输出井传送到内存缓冲区，再由打印机进行打印第六章 文件管理1、文件的逻辑结构、物理结构文件的逻辑结构是指从用户的观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于物理特性,；而文件的物理结构则是指文件在外存上的存储组织形式，与存储介质的存储性能有关。2、文件的三种外存分配方式及特点，不同的分配方式对应于怎样的物理结构？ 连续分配方式：优缺点：顺序访问容易、顺序访问速度快；要求有连续的存储空间、必须事先知道文件的长度。 链接分配方式：分为隐式链接和显示链接； 索引分配方式：分为单级索引分配、多级索引分配、混合索引分配方式。3、文件的三种逻辑结构（顺序、索引、索引顺序）4、常用的目录结构形式：单级目录结构、两级目录多级目录结构。目前广泛采用的目录结构是哪种？它有什么优点？目前广泛采用的目录结构是树型目录结构。它具有以下优点：a.能有效提高对目录的检索速度；假定文件系统中有N个文件，在单级目录中，最多要检索N个目录项，但对于有i级的树型目录，在目录中每检索一个指定文件，最多可能要检索i*个目录项。b.允许文件重名；由于在树型结构的文件系统中，是利用文件路径名来检索文件的，故允许每个用户在自己的分目录中使用与其他用户文件相同的名字。c.便于实现文件共享；在树型目录中，用户可通过路径名来共享其他用户的文件，也可将一个共享文件链接到自己的目录下，从而使文件的共享变得更为方便，其实现方式也非常简单，系统只需在用户的目录文件中增设一个目录项，填上用户赋予该共享文件的新文件名，以及该共享文件的唯一标识符即可。5、位示图方法空闲盘块的管理有一计算机系统利用图6-33所示的位示图来管理空闲盘块。盘块的大小为1KB，现要为某文件分配量个盘块，试说明盘块的具体分配过程。12345678910111213141516111111111111111112111111111111111131101111111111111411111