操作系统复习all(共9页)

1、南理工紫金学院计算机科学与技术2班操作系统复习资料（lm）第 页操作系统(co zu x tn)复习第一章考点(ko din)：操作系统的定义，基本特性以及主要(zhyo)功能（选择、填空）定义：操作系统是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度、以及方便用户使用的程序集合。基本特性：并发性（最重要特征）、共享性、虚拟性、异步性所谓共享是指系统中的资源可供内存中多个并发执行的进程(线程)共同使用。资源属性的不同，对资源共享的方式也不同。实现资源共享的两种方式：(1)互斥共享方式(2)同时访问方式主要功能：处理器管理、存储器管理、设备管理、文件管理、用户之间的接口第二章考点：

2、进程、程序、线程的概念（简答）；PCB结构、进程状态（三种基本状态）；进程同步和互斥的含义（选择，填空）；临界资源、临界区、以及同步机制原则；信号量P或V操作时的信号量值的变化；经典进程同步问题（综合题）进程的定义：进程是进程实体的运行过程(程序在并发环境中的执行过程)，是系统进行资源分配和调度的基本单位。进程的特征动态性 并发性 独立性异步性 进程结构 PCB进程控制块-动态特征的集中反映程序段-描述要完成的功能数据段-操作对象及工作区程序的定义：是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。线程的定义：它是一个基本的CPU执行单元，也是程序执行流的最小单元，由线程ID、

3、程序计数器、寄存器集合和堆栈组成。线程是进程中的一个实体，一个进程中包含(bohn)多个线程，他们可以利用进程所拥有的资源，是被系统独立调度和分派的基本单位。PCB（进程控制块）结构：为了描述和控制进程的运行(ynxng)，系统为每个进程定义了一个数据结构-进程控制块，它是进程实体的一部分，是操作系统中最重要的记录型数据结构。在进程控制(kngzh)块中，主要包含四方面信息：进程标识符、处理机状态、进程调度信息、进程控制信息。进程三种基本状态：就绪状态、执行状态、阻塞状态就绪-执行 执行-阻塞 阻塞-就绪 执行-就绪进程的同步：进程间共同完成一项任务时直接发生相互作用的关系。同步进程间具有合作

4、关系；在执行时间上必须按照一定的顺序协调进行；进程的互斥：并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系。进程间相互合作的关系是同步关系，而对资源争用的关系是互斥关系。若干进程使用同一临界资源时必须互斥执行。临界资源：一次仅允许一个进程使用的共享资源如：打印机、磁带机、表格临界区：在每个进程中访问临界资源的那段程序;进程必须互斥进入临界区；同步机制原则:空闲让进、忙则等待、有限等待、让权等待信号量P操作（wait）、V操作（signal）时时的信号量值的变化：Wait操作：申请一个单位资源procedure wait(S) var S:semaphore;/*定义记录型信号量*/ b

5、egin S.value:=S.value-1; /*如果资源不足则阻塞该进程*/ if S.value0 then block(S.L); endSignal操作：释放一个单位资源procedure Signal(S) var S:semaphore;/*定义记录型信号量*/ begin S.value:=S.value+1; /*如果(rgu)阻塞队列中有进程，则唤醒该进程*/ if S.value0 then wakeup(S.L); endS.value 0时，代表系统中可用资源(zyun)的数目；S.values2 S2 b=a+3;A=0(信号量)P1 p2S1; P(A);V(A

6、); S2;第三章考点：作业经历的三级调度各种调度算法基本思想，计算周转时间，平均周转时间死锁概念、产生原因以及死锁的必要条件，死锁的预防、避免处理方法（简答，填空）银行家算法（作业）处理机调度的层次（三级调度）：高级调度（创建）、低级调度（找进程执行）、中级调度（激活挂起）短作业(进程)优先调度算法基本思想：从后备队列中选择一个或多个若干运行时间最短的作业调入内存运行。高优先权优先调度算法基本思想：从后备队列中选择优先级高的的作业调入内存运行。4.死锁的概念：多个进程在运行过程中因竞争资源而造成的一种僵局。 各并发进程彼此等待对方拥有的资源，且在得到对方资源前不释放自己的资源。死锁产生原因：

7、竞争资源。 资源（打印机、公用队列）数目不能满足进程的需要； 进程间推进顺序非法。进程在运行过程中，请求和释放资源(zyun)的顺序不当，也同样会导致进程死锁。竞争资源引起(ynq)死锁：可剥夺和非可剥夺性资源 竞争(jngzhng)非可剥夺性资源 竞争临时性资源产生死锁的必要条件：(1) 互斥条件 (2) 请求和保持条件 (3) 不剥夺条件 (4) 环路等待条件 7.处理死锁的基本方法(1) 预防死锁。-摒弃“请求和保护”条件互斥条件（ 错 ）请求和保持条件（ 对 ）不剥夺条件（ 对 ）环路等待条件（ 对 ）预防死锁的方法 1.摒弃“请求和保持”条件 解决方案（and型信号量）AND型信号量

8、基本思想：将进程在整个运行中需要的所有资源，一次性全部分配给进程，待进程使用完后一起释放。 2.摒弃“不剥夺”条件 解决方案（强制回收） 3.摒弃“环路等待”条件 解决方案（资源按序分配策略）(2) 避免死锁。-银行家算法 (3) 检测死锁。 (4) 解除死锁。-剥夺资源死锁的解除常采用的两种方法：剥夺资源（基本方法）撤销进程系统不发生死锁，满足不等式：n(k-1)+1m（n是进程个数，k是进程所需最大资源数，m是系统提供资源数）8.银行家算法(1)可利用资源向量Available；(2) 最大需求矩阵Max；(3) 分配矩阵Allocation；(4) 需求(xqi)矩阵Need；Needi

9、,j=Maxi,j-Allocationi,j 设Requesti是进程Pi的请求向量，如果Requestij=K，表示(biosh)进程Pi需要K个Rj类型的资源。Pi发出资源请求后，按下述步骤进行检查： (1)如果(rgu)RequestijNeedi,j，转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2)如果RequestijAvailablej，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。 (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej:=Availablej-Requestij Allocationi,

10、j:=Allocationi,j+Requestij; Needi,j:=Needi,j-Requestij; (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才将资源分配给进程Pi；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 安全性算法 (1) 设置两个向量：工作向量Work:系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available; Finish:系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi:=false; 当有足够资源分配给进程时，再令Finishi:

11、=true。 (2) 从进程集合中找到满足下述条件的进程： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。(3) 当进程Pi获得资源后，可顺利执行，直至完成， 并释放出分配给它的资源，故应执行： Workj:=Worki+Allocationi,j; Finishi:=true; go to step 2; (4) 如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。 对待死锁，一般应考虑死锁的预防、避免、检测和解除。典型的银行家算法属于避免死锁，摒弃“请求和保护”条件属于预防死锁，而剥

12、夺资源是解除死锁的基本方法。第四章考点：动态(dngti)分区分配思想、算法、回收基本分页系统(xtng)的地址转换过程基本分段系统的地址(dzh)转换过程段页式存储管理系统的原理虚拟存储的概念页面置换算法的原理（OPT、FIFO、LRU）动态分区分配思想：当有进程需分配，以进程为单位在内存中找到相等大小的空间进行切割。动态分区分配算法：首次适应算法FF（每次从头开始）循环首次适应算法（找到下次的位置）最佳适应算法（容量以从小到大顺序）最坏适应算法（容量以从大到小顺序）快速适应算法（分类搜索）回收内存情况1：与插入点的前一个空闲区F1相邻接情况2：与插入点的后一个空闲区F1相邻接情况3：同时与

13、插入点的前、后两个空闲区相邻接情况4：既不与F1邻接，又不与F2邻接基本分页系统的地址转换过程分页地址中的地址结构如下：31 12 11 0页号P位移量W位移量W又称页内地址：每页大小：212=4KB地址空间中最多有：220=1M页逻辑地址A 页面大小L 页号P 页内地址d基本分段系统的地址转换过程31 16 15 0段号段内地址允许一个作业最多有64K个段每个段的最大长度为64KB逻辑地址A 页面大小L 页号P 页内地址d段页式存储管理系统(xtng)的原理分段(fn dun)和分页原理结合；先将用户(yngh)进程分成若干个段；再把每个段分成若干个页，并为每个段赋予一个段名；段号(S)段内

14、页号(P)页内地址(W)作业地址空间和地址结构三次访问内存第一次访问段表，从中取得页表起始地址；第二次访问页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次真正访问数据或指令；虚拟存储的概念（局部性原理）虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。虚拟存储器的实现方法 建立在离散分配的存储管理方式基础上分页请求系统请求分段系统8.页面置换算法的原理（OPT、FIFO、LRU）最佳置换算法（OPT）-离得最远淘汰最佳置换算法选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面；先进先

15、出(FIFO)页面置换算法-最先进内存的淘汰淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。最近最久未使用(LRU)置换算法 -左边最远淘汰由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的我将来”的近似，选择最近最久未使用的页面予以淘汰；第五章考点：I/O控制方式缓冲管理种类Spooling技术磁盘调度算法（FCFS、SSTF、SCAN、CSCAN）1.I/O控制方式程序(chngx)I/O方式CPU要不断地测试I/O设备的状态，因为在CPU中无中断机构，使I/O设备无法向CPU报告(bogo)它已完成了一个字符的输入操作。 中断(zhngdun)驱动I/

16、O控制方式在I/O设备输入每个数据的过程中，无须CPU干预，可使CPU与I/O设备并行工作。仅当输完一个数据时，才需CPU花费极短的时间去做些中断处理。使CPU和I/O设备都处于忙碌状态，从而提高了整个系统的资源利用率及吞吐量。直接存储器访问（DMA） I/O控制方式数据传输的基本单位是数据块，即在CPU与I/O设备之间，每次传送至少一个数据块；数据传送是从设备直接送入内存的，或者相反；仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在控制器的控制下完成。I/O通道控制方式 I/O通道方式是DMA方式的发展，它可进一步减少CPU的干预，即把对一个数据块的读(或写)为单位

17、的干预，减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。 2.缓冲管理种类单缓冲用户发出I/O请求；OS在主存中分配一缓冲区用于暂存用户输入的一行数据；输入期间，用户进程被挂起以等待数据输入完毕；输出时，用户进程将一行数据输入到缓冲区后，继续执行处理，当户用已有第二行数据输出时，如果第一行数据尚未被提取完毕，则用户进程阻塞；双缓冲也称缓冲对换输入时，将数据送入第一缓冲区，装满后便转向第二缓冲区。同时，从第一缓冲区中移出数据，并送入用户进程，接着由CPU对数据进行计算；双缓冲，系统处理一块数据的时间可以粗略地认为是Max(C，T)。如果CT，则可使CPU不必等待设备输入；循环缓冲多

18、个缓冲区；多个指针；缓冲池于既可用于输入又可用于输出的公用(gngyng)缓冲池，其中至少应含有以下三种类型的缓冲区: 空(闲)缓冲区； 装满输入(shr)数据的缓冲区； 装满输出(shch)数据的缓冲区。Spooling技术是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。 共享打印机 当用户进程请求打印输出时， SPOOLing系统同意为它打印输出，但并不真正立即把打印机分配给该用户进程，而只为它做两件事： 由输出进程在输出井中为之申请一个空闲磁盘块区， 并将要打印的数据送入其中； 输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中， 再将该表挂到请求打印队列上。 4.磁盘调度算法（FCFS、SSTF、SCAN、CSCAN）先来先服务（FCFS）算法按访问请求到达的先后次序服务最短寻道时间优先（SSTF）算法优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先扫描（SCAN）算法当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务；然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复。循环扫描（C