计算机操作系统面试准备.doc

关于操作系统一般笔试面试中问的比较浅，根据教材整理了一份比较基础的操作系统的学习笔记一、进程管理1. 为何引入进程程序的执行顺序：（1） 顺序执行：顺序性、封闭性、可再现性（2） 并发执行：间断性、失去封闭性、不可再现性在多道程序环境下程序的执行是并发的，这样程序就要失去封闭性，并且间断且不可再现。并发执行的三个特点决定通常的程序是不能被并发执行的，于是引入了进程。2. 进程的特征（1）结构特征：每个进程都对应一个PCB（进程控制块）。程序段、数据段和PCB构成了进程实体。（2）动态性：动态性是进程最基本的特征，因为进程的实质是进程实体的一次执行过程。（3）并发性：进程的引入就是为了满足多道程序的并发执行的特征。（4）独立性：进程是参与资源分配的基本单位（线程是被调度的基本单位）（5）异步性：指进程被执行的速度和顺序具有不确定性，即进程按异步方式运行。3. 进程的状态就绪状态：只差CPU就可以运行的进程执行状态阻塞状态：正在执行的进程遇到某个时间之后暂时不需要CPU了，就把CPU让出来并排到阻塞状态的进程队列中去。4. PCBPCB是进程存在的唯一标志。PCB的作用：是让一个在多道程序环境下无法兵法运行的程序成为一个能够独立地接受调度和运行的基本单位，从而使之成为能和其他进程并发运行的进程。PCB的内容：进程标识符、CPU状态信息、进程调度信息、进程控制信息等。PCB的组织方式：链接方式、索引方式5. 进程控制进程的创建1） 引起进程创建的事件有：用户登录、作业调度、提供服务、应用请求2） 创建步骤：申请空白PCB、为新进程分配资源、初始化进程控制块、将新进程插入就绪进程的终止1） 引起进程终止的事件有：正常结束、异常结束、外界干预2） 终止步骤：读进程状态、若被终止进程处于执行状态则表示该进程被终止后需要重新调度、若该进程有子孙进程则终止所有子孙进程、归还进程资源、移除队列中的PCB进程的阻塞与唤醒引起进程阻塞的事件：请求系统服务、启动某种操作、新数据尚未到达、无新工作可做引起唤醒的事件：当被阻塞进程所期待的事件出现的，如系统服务完成、I/O操作完成、所期待数据已经到达6、进程同步（1）临界资源：某些共享资源仅允许一个进程使用，这就是临界资源。比如打印机、磁带机。（2）临界区：每个进程中访问临界资源的那段代码叫做临界区。临界区是进程中的代码！为了查看当前有没有进程在访问临界资源，所以每个进程在进入临界区之前要执行一段检测代码，这段代码叫做进入区。在离开临界区后进程要标记下现在已经没有进程访问临界资源，这段代码叫做退出区。其他代码称为剩余区。（3） 同步（直接相互制约关系）：一个进程到达了某点后，除非另一进程已经完成了某些操作，否则就不得不停下来等待这些操作的结束，这就是进程间的同步，有了同步后进程间就可以相互合作。（4） 互斥（间接相互制约关系）：多个进程都想使用一个临界资源，但是不能同时使用，于是只好一个进程用完了才能给其他进程用，这就是进程互斥。某种意义上说进程互斥是进程同步的一个特殊情况。1. 实现同步的准则A. 空闲让进：当无进程处于临界区时，应允许一个请求进入临界区的进程立即进入自己的临界区B. 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待，以保证临界资源互斥访问C. 有限等待：对要求访问临界资源的进程，应保证有限时间内进入自己的临界区，以免陷入“死等”D. 让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”（忙等是指当一个进程在临界区，当其他进程欲进入临界区时，反复检测是否可以进入，即忙于等待临界区中的进程离开）2. 信号量机制（1）整型信号量整型信号量是一个整型的变量S，能对S进程的操作有3种：第一个是初始化S，给出S的初值；第二个原子操作wait(S)，又称作P操作；Wait(S)While(S = 0);/不执行任何操作，循环S-;第三个是原子操作signal(S)，又称作V操作Signal(S)S+;注：原子操作是指不能被中断的操作，可以用原语实现。（2）记录型信号量整型信号量没有实现同步机制的第四条“让权等待”，因为执行了wait操作时弱信号量S=0，那么就会不断的循环测试S的数值，不会释放CPU资源。记录型信号量就是为了解决这种忙等现象而被提出的。记录型信号量的数据结构可用结构体表示：StructInt value;Struct process *L;semaphore；Wait操作的伪代码：Void wait(semaphore S)S.value -;If(S.value 0)/S.value 0时，阻塞进程Add this process to S.L;Block(S.L);Signal操作的伪代码：Void signal(semaphore S)S.value +;If(S.value = 0)Remove a process P from S.L;3. 管程机制管程的定义：管程是由一组数据以及定义在这个数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。7. 进程通信进程通信就是进程间的数据交换。进程的互斥与进程的同步就是进程通信中的低级通信方式。Wait和signal操作成为低级通信原语。高级通信方式是指以较高的效率传输大量数据的通信方式。（1） 共享存储器系统：是指互相通信的进程通过某些共享存储区或者共享数据结构进行通信。通过对共享存储区的读写来进行通信的方式属于高级通信方式，基于共享数据结构的通信方式属于低级通信方式。（2） 消息传递系统：进程间的数据交换是以格式化的消息为单位进行。具体又分直接通信方式和简介通信方式。（3） 管道通信：所谓的管道就是一个共享文件，它连接了一个读进程和一个写进程，让它们之间可以借助这个共享文件进行通信。写进程以字符流的形式将大量信息写入管道，读进程则在需要时从管道读出数据。8. 线程引入线程的原因：创建进程的开销大、导致进程并发度不够，进程管理的开销大，进程间通信太麻烦，正是由于进程存在着这些缺点，致使引入线程。线程的概念：线程是进程中某个单一顺序的控制流，也被称为轻量进程，它是进程中的一个实体，是被系统独立调度和分派的基本单位。用户级线程和内核支持线程：用户级线程：仅存在用户空间，与内核无关。内核管理用户级线程对应的整个进程。它感觉不到用户级线程的存在。好处：无需内核支持就可以实现多线程，线程的切换不需要陷入到内核，所以切换的开销小速度快。缺点：进程的一个线程被阻塞后整个进程中的所有线程都被阻塞，并且无法享有多处理机带来的好处。（调度单位为进程）内核支持线程：是由内核负责管理的，线程控制块也在内核中。所以线程的创建、切换、撤销等操作都是通过系统调用在内核中完成的。好处：进程中的一个线程被阻塞之后该进程的其他线程还可以继续执行不会被阻塞。缺点：即使是同一个进程内的不同线程之间的切换也要陷入内核，开销大。多线程模型：（1） 多对一模型（多个用户级线程映射到一个内核线程）优点：线程管理是在用户控件进行的，因而效率比较高。缺点：进程的一个线程被阻塞后整个进程中的所有线程都被阻塞（2） 一对一模型（一个用户级线程映射到一个内核线程）优点：进程中的一个线程被阻塞之后该进程的其他线程不会被阻塞，并发能力较强缺点：开销大（3） 多对多模型（m个用户级线程映射到n个内核线程，m n）特点：集二者之所长二、处理及调度与死锁1. 处理及调度的基本概念1. 三级调度（1） 高级调度：又称为作业调度或长期调度作业调度负责从外存上等候调度的作业中断则一个调入内存，并给这个作业分配资源，创建进程，然后挂到就绪队列上等待进程调度。（2）中级调度：又称为进程对换或中程调度中级调度负责把暂时无法运行的在内存中的进程调到外存中等待以减少内存空间的浪费，在内存有空闲时把外存中有条件运行的进程重新调入内存。所以引入中程调度主要是为了提高内存的利用率和系统的吞吐量。被中级调度处内存的进程处于挂起状态，中级调度的实质是对换。（3）低级调度：又称为进程调度或短程调度，是最基本的一种调度进程调度负责从内存的就绪队列上等候调度的进程中选择一个分配CPU给他，该进程的状态于是从就绪转变为运行。调度队列进程进入系统时，会被加入到作业队列中。驻留在内存中就绪的等待运行的进程被保存在就绪队列上，该队列一般用链表的形式来存储。等到特定的I/O设备的进程被放在特点的设备队列中，每个设备都有自己的设备队列。2. 调度方式1）非抢占式：即一个进程在执行过程中除了它自身有I/O请求等事件发生的情况外，其他进程不得中断它的执行，也就是不得抢夺他的CPU资源2）抢占式：根据某种算法计算各个进程的优先权，优先权高的进程可以在优先权低的进程正在执行的时候抢夺其CPU资源抢占的原则：A. 给重要和紧急的进程赋予高的优先权B. 短作业优先原则，即给短作业赋予高的优先权C. 时间片原则，即给时间片完了的进程最低的优先权3. 选择调度方式和算法的准则（1）用户角度A. 周转时间短周转时间：作业从被提交给系统开始到作业完成为止的这段时间间隔的长度带权周转时间：周转时间/运行时间B. 相应是间短（尤其对于分时系统）响应时间：用户通过键盘提交请求后开始计时，到系统做出第一个响应为止的时间间隔。C. 截止时间的保证截止时间：一个任务开始得到执行或被执行完毕的最迟时间（2）系统的角度吞度量、处理机利用率、各类资源的平衡利用2. 调度算法1. 先来先服务算法（FCFS）2. 短作业优先算法（SJF）3. 优先级调度算法静态优先权算法：进程的优先权在整个运行期间不变动态优先权算法：进程的优先权随着进程被调度的情况变化而变化，如随着进程等待的时间的增加而增加，这样可以防止有些优先级低的进程长期得不到运行高响应比优先（动态）：响应比 = （等待时间 + 运行时间）/ 运行时间4. 时间片轮转法（RR）执行中的进程只要时间片用完就要被就绪队列队首的那个进程抢占CPU。5.多级队列调度算法将就绪队列分成多个独立的队列，根据进程的属性和类型将一个进程永久地分配到一个队列中。每个队列都有自己的调度算法。队列之间有优先级差别，通常采用固定优先权可抢占调度6.多级反馈队列调度算法多级反馈队列调度算法将就绪队列分成多个队列，每个队列拥有的优先级不同，一个新的进程到达内存后，先被放到优先级高的队列中按时间片轮转法被调度执行，若在时间片用完后没有被执行完，那就被扔到优先级低的下一个队列去时间片轮转，相应的得到执行的机会就减少了。优势：1） 保证了短作业的优先，让终端型用户满意2） 短批处理作业也能在一两个队列给的时间片里完成，周转时间仍然较短3） 长批处理作业虽然优先级较低，但经过前面几个队列后已经得到了部分执行，用户不必担心他长期处理先来先服务短作业优先高响应比优先时间片轮转多级反馈队列能否是可抢占否是是是队列内算法不一定能否使不可抢占是是是否队列内算法不一定优点公平，实现简单平均等待时间最少，效率最高兼顾长短作业兼顾长短作业兼顾长短作业，有较好的相应时间，可行性强缺点不利于短作业长作业容易饥饿，估计时间不确定计算响应比的开销大平均等待时间较长，上下文切换浪费时间无尤其适用于作业调度，批处理系统分时系统很通用3. 产生死锁的原因和必要条件1. 死锁产生的原因根本原因：系统资源数量不足、进程推进顺序不当（1）竞争资源可剥夺性资源；指抢占式系统中的一个进程得到了这种资源后还可以被其他进程所抢占。不可剥夺性资源：指一旦被分配给了一个进程就不能被抢占，除非该进程用完后释放的资源竞争不可剥夺性资源可能导致死锁，但竞争可剥夺型资源不可能导致死锁（2）进程间推进顺序非法2. 必要条件（1）互斥条件：被争夺的资源同一时间只能被一个进程使用（2）请求和保持条件：即一个进程由于请求某个资源不成功而被阻塞的时候不释放它之前申请到的资源（解决：只有一次性申请到所有所需资源，否则将释放已经申请的资源）（3）不剥夺条件：是指一个进程在申请到资源后不能被其他进程剥夺，直到其自己释放（解决：允许系统中的进程在申请了系统中已经没有的资源后，可从其他没有在运行的进程抢占该资源）（4）环路等待条件：是指发生死锁时必然存在一个资源-进程环路。（解决：要求进程按资源的编号来顺序申请资源）3. 处理方法（1）死锁预防：通过破坏上述四个必要条件的一个或多个，这种方法往往导致系统的效率低，资源利用率低（2）死锁避免：并非事先就设置好限制条件来破坏死锁发生的必要条件，而是在资源动态分配的过程中用某些算法加以限制，防止系统进入不安全状态从而避免死锁的发生。（银行家算法）（3）死锁检测（4）死锁解除：通过撤销一些进程回收资源，以较低限度的代价把系统从死锁中解脱出来。三、存储器管理1. 连续分配方式连续分配方式是指为一个用户程序分配一个连续的内存空间。（1） 单一连续分配：把内存分为系统区和用户区，各让OS和用户使用，只能用于单用户、单任务OS，可以采用覆盖技术。（2） 固定分区分配：把用户的内存空间划分成几个固定大小的区域，每个分区中可以装入一道作业，这样就可以实现多道程序。分区大小可相等也可不等。（3） 动态分区分配A. 首次适应算法FFB. 循环首次适应算法（每次不是从队首而是从上次找到空闲分区的下一分区开始查找）C. 最佳适应算法D. 最差适应算法（4） 动态可重定位分区分配分配方式有无内部碎片有无外部碎片优点缺点单一连续分配有无简单只能在单用户、单任务、单道的OS固定分区分配有无用于多道程序系统的最简单分配方案存储空间浪费较多首次适应算法无有动态分区中最简单方案地地址部分用得太多，高地址部分相对空闲，导致查询效率低循环首次适应算法无有查找时间少，内存分布均匀会导致缺乏大的空闲分区最佳适应算法无有使得外部碎片都很小，对于一次分配来说是最佳的需要查找整个内存空间，费时，长期来看留下来很多难以利用的小空闲区最差适应算法无有使得留下来的空闲区较大需要查找整个内存空间，费时，过早用掉大的空闲区会导致以后难以找到足够大的空闲区来满足进程动态可重定位无有内存利用率很高需要硬件支持，地址变换浪费时间内部碎片：就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间；外部碎片：还没有被分配出去（不属于任何进程），但由于大小太小无法分配给申请内存空间的新进程的内存空闲区。紧凑（拼接）：采用移动内存中的作业到一起的方法把空闲空间从多个小分区变为一个大分区以满足要求，紧凑之后要对被移动的作业的程序和数据的地址加以变化。对换：把系统中暂时无法运行的进程或暂时不用的程序和数据调出到外存上，以便腾出内存空间给已经具备运行条件的进程或进程所需的数据和程序，以增加内存使用率2. 基本分页和基本分段存储管理方式分页分段信息的物理单位信息的逻辑单位分页目的是为了系统管理，提高内存利用率分段的目的是为了能更好的满足用户需求页大小固定且有系统决定段长度补丁，不同段有不同段长，是有用户编写的程序的具体情况决定的作业地址空间是一维的作业地址空间是二维的有内部碎片无外部有外部碎片无内部3. 段也是存储管理方式先页后段克服了外部碎片，但是内部碎片比分页还多。多访问一次内存。4. 虚拟存储器引入原因：解决内存不足的问题1. 局部性原理程序的局部性原理是指程序在执行的时候呈现出的局部性规律，也就是说一个短的时间范围内，程序的执行仅仅局限于某个部分，相应的他所访问的存储空间也局限于某个区域。（1） 时间局部性程序中的某条指令一旦被执行，他们他不久后可能再次被执行（2） 空间局部性当程序访问了某个存储单元后，之后的时间内这个存储单元附近的存储单元也有可能被访问到，也就是程序在一段时间内访问的存储空间集中在一定的范围内。2. 虚拟存储器的概念和特征虚拟存储器是指有请求调入功能和置换功能的能从逻辑上对内存容量加以扩充的一种存储器系统，实际上是一个地址空间虚拟存储器的特征多次性（最重要的特征）：与常规存储管理的一次性相反，虚拟存储器把一个作业分多次调入到内存对换性：与常规存储管理的驻留性相反，在作业运行期间虚拟存储器允许将那些暂时不运行的程序或数据调出到外存的兑换区，到运行需要用到的时候才再调回到内存，提高了内存利用率虚拟性：虚拟存储器对内存的扩充是逻辑上的四、设备管理1. I/O设备和设备控制器（1）I/O设备类型按速度分类：低速设备（键鼠），中速设备（打印机），高速设备（磁盘）按信息交换单位：块设备（磁盘），字符设备（打印机、终端）按共享类型：独占设备、共享设备（同一时刻仍只允许一个进程访问）、虚拟设备按使用特性：I/O设备、存储设备（2）设备控制器控制一个或多个I/O设备的硬件，它提供了CPU和I/O设备直接的接口。如网卡、显卡2. I/O控制方式最主要的驱动力：减少CPU对I/O控制的干预（1）程序I/O方式程序I/O方式中，有I/O速度远远慢于CPU，致使CPU绝大部分时间都在测试I/O设备是否已经完成数据传输。（2）中断驱动I/O控制方式中断的优点：CPU和I/O可以并行工作，无需CPU不断测试，I/O设备会自行传输数据，等到一个数据传输完毕，I/O设备会发出一个中断来提醒CPU，CPU只需收到中断后处理下即可。中断的缺点：由于中断I/O控制方式每传输几个字节（由数据缓冲寄存器大小决定）就发出一次中断，所以CPU还是会频繁的去处理中断。中断处理程序的过程（仅指I/O完成时发出的中断）：1） 唤醒被阻塞的驱动程序进程2） 保护被中断进程的CPU环境：将处理机状态字PSW和程序计数器PC等压栈。3） 转入相应的设备处理程序：测试中断源以确定引起中断的设备号4） 恢复被中断进程的现场：把当时压入栈保护的数据弹