1、操作系统复习alldocx操作系统复习第一章考点：操作系统的定义，基本特性以及主耍功能（选择、填空）1定义：操作系统是一组控制和管理计算机硬件和软件资源、合理地対各类作业进行调度、 以及方便用户使用的程序集合。2. 基本特性：并发性（最重要特征）、共享性、虚拟性、异步性所谓共享是指系统屮的资源可供内存屮多个并发执行的进程（线程）共同使用。 资源属性的不同，对资源共享的方式也不同。实现资源共享的两种方式：（1）互斥共享方式同吋访问方式3. 主耍功能：处理器管理、存储器管理、设备管理、文件管理、用户Z间的接口第二章考点：进程、程序、线程的概念（简答）；PCB结构、进程状态（三种基木状态）；进程同步
2、和互斥的含义（选择，填空）；临界资源、临界区、以及同步机制原则；信号量P或V操作时的信号量值的变化；经典进程同步问题（综合题）1进程的定义：进程是进程实体的运行过程（程序在并发环境中的执行过程），是系统进行资 源分配和调度的基本单位。进程的特征动态性并发性独立性异步性进程结构PCB进程控制块-动态特征的集中反映程序段描述要完成的功能数据段- 操作对象及工作区2. 程序的定义：是为实现特定FI标或解决特定问题而用计算机语言编写的命令序列的集合。3. 线程的定义：它是一个基本的CPU执行单元，也是程序执行流的最小单元，rtl线程ID、 程序计数器、寄存器集合和堆栈组成。线程是进程中的一个实体，一个
3、进程中包含多个线程, 他们可以利用进程所拥有的资源，是被系统独立调度和分派的基本单位。4. PCB (进程控制块)结构：为了描述和控制进程的运行，系统为每个进程定义了一个数据 结构-进程控制块，它是进程实体的一部分，是操作系统屮最重要的记录型数据结构。在进程控制块中，主耍包含四方面信息：进程标识符、处理机状态、进程调度信息、进程控 制信息。5. 进程三种基木状态：就绪状态、执行状态、阻塞状态就绪执行执行 阻塞阻塞 就绪执行- 就绪&进程的同步：进程间共同完成一项任务时直接发生相互作用的关系。同步进程间具有合作关系；在执行吋间上必须按照一定的顺序协调进行；7. 进程的互斥：并发执疔的多个进程由于
4、竞争同一资源而产生的相互排斥的关系。进程间相互合作的关系是同步关系，而対资源争用的关系是互斥关系。若T进程使用同一临 界资源时必须互斥执行。8. 临界资源：一次仅允许一个进程使用的共享资源如：打印机、磁带机、表格9临界区：在每个进程中访问临界资源的那段程序;进程必须互斥进入临界区；10.同步机制原则:空闲让进、忙则等待、有限等待、让权等待信号量P操作(wait) V操作(signal)时时的信号量值的变化:Wait操作：申请一个单位资源procedure wait(S)var S:semaphore;/*定义记录型信号量*/beginS.value:=S.value/*如果资源不足则阻塞该进程
5、*/if S.value0 then block(S.L);endSignal操作：释放一个单位资源procedure Signal(S)var S:semaphore;/*定义记录型信号量*/beginS.value:=S.value+l;厂如果阻塞队列中冇进程，则唤醒该进程*/if S.value WO then wakeup(S.L);endS.value 20时,代表系统中可用资源的数目;S.values252 b=a+3;A二0（信号量）Pl p2SI； P（A）;V（A）; S2;第三章考点：作业经历的三级调度各种调度算法基本思想，计算周转时间，平均周转时间死锁概念、产生原因以及死
6、锁的必要条件，死锁的预防、避免处理方法（简答，填空） 银行家算法（作业）1. 处理机调度的层次（三级调度）：高级调度（创建）、低级调度（找进程执行）、小级调 度（激活挂起）2. 短作业（进程）优先调度算法基本思想：从后备队列屮选择一个或多个若干运行时间最短的 作业调入内存运行。3. 高优先权优先调度算法基本思想：从后备队列中选择优先级高的的作业调入内存运行。4. 死锁的概念：多个进程在运行过程中因竟争资源而造成的一种僵局。各并发进程彼此等待对方拥有的资源，且在得到对方资源前不释放口己的资源。5. 死锁产生原因：竞争资源。资源（打印机、公用队列）数日不能满足进程的需要；进程间推进顺序非法。进程在
7、运行过程中，请求和释放资源的顺序不当，也 同样会导致进程死锁。竞争资源引起死锁：可剥夺和非可剥夺性资源竞争非可剥夺性资源竞争临时性资源6. 产生死锁的必要条件：（1）互斥条件请求和保持条件（3）不剥夺条件坏路等待条件7处理死锁的基本方法预防死锁。-摒弃“请求和保护”条件互斥条件（错）请求和保持条件（对 ）不剥夺条件（ 对 ）环路等待条件（对 ）预防死锁的方法1摒弃“请求和保持”条件解决方案（and型信号罐）AND型信号量基本思想：将进程在整个运行中需要的所有资源，一次性全部分配给进程，待进程使用完后 起释放。2. 摒弃“不剥夺”条件解决方案（强制回收）3. 摒弃“环路等待”条件 解决方案（资源
8、按序分配策略）避免死锁。-银行家算法检测死锁。解除死锁。-剥夺资源死锁的解除常采用的两种方法：剥夺资源（基木方法）撤销进程系统不发生死锁，满足不等式：n（k-l）+lm（n是进程个数，k是进程所需垠大资源数，m是系统提供资源数）8银行家算法（1）可利用资源向量Available；最人需求矩阵Max；分配矩阵Allocation；（4）需求矩阵Need；Need i,j =Max i,j -Allocation ij设Request!是进程Pi的请求向量,如果Requestij=K,表示进程Pi需要K个Rj类型的资源。Pi发出资源请求示，按下述步骤进行检杏：如果RequestijNeediJ,转
9、向步骤2；否则认为出错，因为它所需要的资源数 已超过它所宣布的最大值。（2） 如果RequestijAvailablej,便转向步骤;否则,表示尚无足够资源,Pi须等 待。（3） 系统试探着把资源分配给进程Pi,并修改下而数据结构中的数值： Availablej:=Availablej-RequestijAllocationizj:=Allocationij+Requestij;Needizj:=NeediJ-Requestij;（4） 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全, 才将资源分配给进程Pi；否则，将木次的试探分配作废，恢复原来的资源分配状态，让进程 P
10、i等待。安全性算法（1）设置两个向量:1 工作向M Work:系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执 行安全算法开始时，Work:=Available;2 Finish:系统是否有足够的资源分配给进程，便Z运行完成。开始吋先做Finishi:=false;当 有足够资源分配给进程时，再令Finishi:=true从进程集合屮找到满足卜-述条件的进程：1 Finishi=false;2 Needi,jWWorkj；若找到，执行步骤（3）,否则，执行步骤（4）。 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj:=Worki+All
11、ocationi,j;Fin ishi:=true; go to step 2;如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不 安全状态。对待死锁，一般应考虑死锁的预防、避免、检测和解除。典型的银行家算法属于避免死锁,摒弃“请求和保护”条件属于预防死锁，而剥夺资源是解除死锁的基本方法。第四章考点：动态分区分配思想、算法、回收基本分页系统的地址转换过程基木分段系统的地址转换过程段页式存储管理系统的原理虚拟存储的概念页面置换算法的原理（OPT、FIFO、LRU）1. 动态分区分配思想：当有进程需分配，以进程为单位在内存屮找到相等人小的空间进行切 割。2动态分
12、区分配算法：首次适应算法FF （每次从头开始）循环首次适应算法（找到下次的位置）最佳适应算法（容虽以从小到大顺序）最坏适应算法（容最以从大到小顺序）快速适应算法（分类搜索）3. 回收内存情况1：与插入点的前一个空闲区F1相邻接情况2：与插入点的后一个空闲区F1和邻接情况3：同时与插入点的前、后两个空闲区相邻接情况4：既不与F1邻接，又不与F2邻接4. 基本分页系统的地址转换过程分页地址中的地址结构如F:31 12 11 0页号P位移量W位移量W 乂称页内地址：每页大小:212=4KB地址空间中最多有：22O=1M页逻辑地址A页而人小L 页号P页内地址d AP = INT -L d = A MO
13、DL5 基木分段系统的地址转换过程31 16 15 0段号段内地址允许一个作业最多有64K个段每个段的最大长度为64KB6. 段页式存储管理系统的原理分段和分页原理结合；先将用户进程分成若干个段；再把每个段分成若干个页，并为每个段赋予一个段名;段号段内页号(P)页内地址(W)作业地址空间和地址结构三次访问内存第一次访问段表，从中取得页表起始地址；笫二次访问页表，从屮取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数 据的物理地址；第三次真正访问数据或指令；7. 焜拟存储的概念(局部性原理)虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存 储器系统。虚拟
14、存储器的实现方法建立在离散分配的存储管理方式基础上分页请求系统请求分段系统8. 页面置换算法的原理（OPT、FIFO、LRU）最佳置换算法（OPT）-离得最远淘汰最住證换算法选择的被淘汰页面，将是以后永不使用的，或许是在最长（未來川寸间内不再被访问的页面；先进先出（FIFO）页面置换算法 最先进内存的淘汰淘汰最先进入内存的页面，即选择在内存中驻留吋间最久的页面予以淘汰。最近最久未使用（LRU）置换算法左边最远淘汰由于无法预测各页面将來的使丿lj情况，只能利用“最近的过去”作为“最近的我将來”的近 似，选择最近最久未使用的页而了以淘汰；第五章考点：I/O控制方式缓冲管理种类Spooling 技术
15、磁盘调度算法（FCFS、SSTF、SCAN、CSCAN）1.1/0控制方式程序I/O方式CPU要不断地测试I/O设备的状态，因为在CPU中无中断机构，使I/O设备无法向CPU报告 它已完成了一个字符的输入操作。中断驱动I/O控制方式在I/O设备输入每个数据的过程屮，无须CPU干预，可使CPU与I/O设备并行工作。仅当输完一个数据时，才需CPU花费极短的时间去做些中断处理。使CPU和I/O设备都处于忙碌状态，从而提高了整个系统的资源利用率及吞吐最。直接存储器访问（DMA） I/O控制方式数据传输的基木单位是数据块，即在CPU与I/O设备之间，每次传送至少一个数据块；数据传送是从设备直接送入内存的
16、，或者相反；仅在传送一个或多个数据块的开始和结束吋，才需CPU干预，整块数据的传送是在控制器 的控制下完成。I/O通道控制方式I/O通道方式是DMA方式的发展，它可进一步减少CPU的干预，即把对一个数据块的读（或写）为单位的干预，减少为对一组数据块的读（或写）及有关的控制和管理为单位的干预。2. 缓冲管理种类单缓冲用户发出I/O请求；OS在主存中分配一缓冲区用于暂存用户输入的一行数据；输入期间，用户进程被挂起以等待数据输入完毕；输出时，用户进程将一行数据输入到缓冲区示，继续执行处理，当户用已有第二行数据输出 时，如果第一行数据尚未被提取完毕，则用户进程阻塞；双缓冲也称缓冲对换输入时，将数据送入
17、第一缓冲区，装满后便转向第二缓冲区。同时，从第一缓冲区屮移出数 据，并送入用户进程，接着由CPU对数据进行计算；双缓冲，系统处理一块数据的吋间可以粗略地认为是Max（C, T）o如果CT,则可使CPU不必等待设备输入；循环缓冲多个缓冲区；多个指针；缓冲池于既可用于输入又可用于输出的公用缓冲池，其中至少应含有以下三种类型的缓冲区：1 空（闲）缓冲区；2 装满输入数据的缓冲区；3 装满输岀数据的缓冲区。3.Spooling 技术是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。 共享打卬机当川户进程请求打印输出时，SPOOLing系统同意为它打印输出，但并不真正立即把打
18、印机 分配给该用户进程，而只为它做两件事：1 山输出进程在输出井中为之屮请一个空闲磁盘块区，并将要打印的数据送入其中；2 输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中， 再将该表挂到请求打卬队列上。4. 磁盘调度算法（FCFS、SSTF、SCAN、CSCAN ）先來先服务（FCFS）算法按访问请求到达的先后次序服务最短寻道时间优先（SSTF）算法优先选择距当而磁头最近的访问请求进行服务，主要考虑寻道优先扫描（SCAN）算法当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中対遇到的访问请求进行服务；然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复。循环扫描（CSCAN ）算法总是从0号柱面开始向里扫描；按照各自所要访问的柱面位置的次序去选择访问者；移动臂到达最后个一个柱面后，立即带动读写磁头快速返回到0号林面; 返回时不为任何的等待访问者服务；返回后可再次进行扫描。
