操作系统——考前资料(最终版).doc

第一章1.3操作系统的基本特性 1.并发性2.平行性3.引入进程4.引入线程5.共享性：是指系统中的资源可供内存中多个并发执行的进程共同使用，有互斥共享方式和同时访问方式。6.虚拟技术：是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。共有时分复用和空分复用两种技术。7.异步性：进程是以人们不可预知的速度向前推进，此即进程的异步性。1.2.4实现分时系统的关键问题：人机交互。解决的关键技术：（用多路卡解决）及时接收（用时间片轮转解决）及时处理第二章2.1进程的属性：1.进程是一个可拥有资源的独立单位2.是一个可独立调度和分派的基本单位。进程的独立性：指进程实体是一个可以独立运行独立分派资源和独立接收调度的基本单位。2.1.4进程三种基本状态1.就绪状态2.执行状态3.阻塞状态。转换见下图左（注意看状态间转换的条件）。三种特殊状态：挂起状态，创建状态和撤消状态。转换见下图右2.3.1并发进程之间的两种制约关系：间接相互制约关系（原因：资源共享）、直接相互制约关系（原因：进程间合作）2.3.1同步机构应遵循的四项原则：空闲让进，忙则等待，有限等待，让权等待2.3.1临界资源即共享资源：一次只允许一个进程访问的资源。临界区：进程中访问临界资源的那段代码2.3.2信号量：（S值意义）在记录型信号量机制中，S.value初值表示系统中某类资源的数目；若S.value0,表示该类资源已分配完毕，调用block语句进行自我阻塞,S.value:=S.value+1,若+1后仍是S.value=0,还应调用wakeup语句；若S.value初值为1，表示只允许一个进程访问临界资源，信号量转化为互斥信量。两个原语：wait(S),signal(CS)（详见课本P51）2.4生产者-消费者问题、哲学家进餐问题（详见大题1.）2.5.4消息缓冲队列通信机制:功能：1.构成消息2.发送消息3.接收消息4.互斥与同步第三章3.3、作业调度算法,计算平均周转时间：（详见大题2.）分类：（1）高级：作业或长程（2）中级：中程（3）低级：进程或短程调度方式：（1）非抢占（2）抢占算法：（1）先来先服务（FCFS）调度算法，既可用于作业调度，也可用于进程调度。有利于长作业，不利于短作业进程（2）短作业（进程）优先调度算法，对长作业不利（3）高优先权优先调度算法，高响应比优先调度算法 （HRRN） 优先权=（等待时间+要求服务时间）/要求服务时间（4）基于时间片的轮转调度算法（5）多级反馈队列调度算法计算周转时间：T=完成时间-到达时间计算平均周转时间， 一个低级错误。3.5.1解决死锁的方法：1预防死锁（最易于实现的）2避免死锁（可以使资源利用率达到最高）3检测死锁4解除死锁（两种方法：剥夺资源和撤销进程）。3.5某系统中有n个并发进程，分别需要同类资源m个，系统不可能发生死锁的最少资源数的计算：n(m-1)+1；可能发生死锁的最多资源数：n(m-1)第四章4.2.2作业的三种链接方式：1、静态链接方式【需解决以下问题（1）对相对地址进行修改（2）变换外部调用符号】；2、装入时动态链接优点（1）便于修改和更新（2）便于实现对目标模块的共享；3、运行时动态链接4.2.1重定位：在装入时对目标程序中指令和数据的修改过程。动态重定位：重定位的地址变换过程是在程序执行期间随着对每条指令或数据的访问自动进行的。重定位类型：静态重定位和动态重定位，重定位类型的依据：转换时间和执行工具类型时间工具对程序要求特点静态重定位装入时重定位装入程序可重定位（编译打标志）装慢执行快动态重定位运行时硬件地址变换机构无装快之星慢4.4分区分配算法：1.首次适应算法（缺点：低地址部分不断被划分）2.循环首次适应算法（）3.最佳适应算法（缺点：出现的内零头）4.最坏适应算法（缺乏大的空闲分区）5.快速适应算法（优点：为每一个空闲分区建立链表）。【看书上算法】4.4页长定为2n的原因：避免乘除运算，只需进行简单的移位运算。4.8.2页面置换算法及缺页率高低比较：先进先出和最近最久未使用（肯定出最近最久）看书上例题【P151】4.4；4.9；分页/段：逻辑地址位数的意义、页/段表控制寄存器的信息及其来源?、地址变换、分页提速措施：在地址变换机构中增设一个具有并行查询功能的特殊高速缓冲寄存器（即快表）。（详见大题4.）第五章5.4.4设备独立性：应用程序独立于具体使用的物理设备。实现设备独立性的数据结构的好处：1.设备分配时的灵活性 2.易于实现I/O重定向5.5设备管理的数据结构：1、DCT：设备控制表、2、COCT：控制器控制表、3、CHCT：通道控制表、4、SDT：系统设备表。5.5.4；SPOOLING技术是对脱机输入和输出系统的模拟。组成：（1）输入井和输出井（2）输入缓冲区和输出缓冲区（3）输出进程SPi和输出进程SPo。特点：（1）提高I/O速度（2）将独占设备改造为共享设备（3）实现了虚拟设备(详见课本P190，图522)5.6.2磁盘调度算法(最短寻道SSTF/扫描算法SCAN）【详见大题5】，饥饿现象:某一磁道长时间未被访问,只有SSTF产生。粘着现象:磁臂长时间停留在某一磁道，SSTF、SCAN都会产生。第六章6.4.1UNIX把文件控制块FCB分成文件和文件描述两部分，拆分的好处：使平均启动磁盘数减少，大大节省了系统开销。 6.3.4Unix中文件的物理结构：混合索引分配方式（包括直接寻址，一次间接寻址和多次间接寻址）6.5.3Unix的空闲盘块管理方法：成组链接法（结合了空心表法和空闲链表罚，并克服了两者表太长的缺点）第七章前言：操作系统用户接口类型：包括用户接口（命令接口和图形接口）和程序接口。1.哲学家进餐问题的描述算法 。l 2.作业调