操作系统期末复习总结

操作系统引论操作系统的作用：1OS作为用户与计算机硬件系统之间的接口；2〕OS作为计算机系统资源的管理者；3〕OS实现了对计算机资源的抽象多道批处理的概念及特征：1〕概念：允许多个程序同时进入一个计算机系统的主存储器并启动进行计算。2〕特征：多道性；无序性；调度性分时系统的概念及特征：1〕概念：在一台主机上连接多个带有显示器和键盘的终端，同时允许多个用户通过主机的终端，以交互方式使用计算机，共享主机中的资源。2〕特征：多路性；独立性；及时性；交互性实时系统的概念及特征：1〕概念：是指当外界事件或数据产生时，能够接受并以足够快的速度予以处理，其处理的结果又能在规定的时间之内来控制生产过程或对处理系统作出快速响应，并控制所有实时任务协调一致运行的操作系统。2〕特征：多路性；独立性；及时性；交互性；可靠性操作系统的概念及特征：1〕概念：是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序集合2〕特征：并发性；共享性；虚拟技术；异步性；进程管理进程的概念及特征1〕概念：是进程尸实体的运行过程，是系统进行资源分配和调度的一个独立单位2〕特征：结构特征；动态性；并发性；独立性；异步性；进程的三种根本状态和挂起状态及互相转化1〕就绪状态；执行状态；阻塞状态2〕终端用户的请求；父进程请求；负荷调节的需要；操作系统的需要3〕活动就绪—静止就绪；活动阻塞—静止阻塞；静止就绪—活动就绪；静止阻塞—活动阻塞进程控制块的作用及内容：作用：是使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的根本单位，一个能与其他进程并发执行的进程内容：1〕进程标识符2〕处理机状态3〕进程调度信息4〕进程控制信息临界资源、临界区、同步机制遵循准那么临界资源：一段时间内只允许一个进程访问的资源临界区：每个进程中访问临界资源的代码段.各进程互斥地进入临界区，可实现互斥访问临界资源同步应遵循的规那么：空闲让进、忙那么等待、有限等待、让权等待高级进程通信的三种类型：共享存储器系统；消息传递系统；管道通信第三章处理机调度与死锁1高级中级低级调度的功能和作用高级调度：又称为作业调度或长程调度，其主要功能是根据某种算法，把外存上处于后备队列中的那些作业调入内存，也就是说，它的调度对象是作业。中级调度：又称为中程调度，引入它的主要目的是为了提高内存利用率和系统吞吐量。由中级调度来决定把外存上那些又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。中级调度实际上就是存储器管理中的对换功能。低级调度：又称为进程调度或短程调度，它所调度的对象是进程或内核级线程。其主要功能有1保存处理机的现场信息2按某种算法选取进程3把处理器分配给进程。2面向用户的选择调度方式和算法的准那么1〕周转时间短2〕响应时间快3〕截止时间的保证4〕优先权准那么3调度算法及优缺点1)先来先效劳调度算法：当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创立进程，然后放入就绪队列。当在进程中采用该算法时，那么每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。FCFS算法比拟有利于长作业〔进程〕，而不利于短作业〔进程〕。(2)短作业〔进程〕优先调度算法:短作业优先〔SJF〕的调度算法是从后备队列中选择一个或假设干个估计运行时间最短的作业，将它们调入内存运行。短进程优先(SPF)调度算法是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。缺点：1该算法对长作业不利。2该算法完全未考虑作业的紧迫程度因而不能保证紧迫性作业〔进程〕会被及时处理。3由于作业〔进程〕的长度只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度3〕高优先权优先调度算法作业调度：从后备队列中选择假设干个优先权最高的作业装入内存。进程调度：把处理机分配给就绪队列中优先权最高的进程，分为非抢占式优先权算法和抢占式优先权算法。(4〕高响应度比优先调度算法为每个进程引入动态优先权，随着等待时间增加优先权提高。优点：1等待时间相同，短作业优先权高〔即SPF〕；2要求效劳时间相同，等待时间长，优先权高〔即FCFS〕；3对于长作业，在等待足够时间后，可获得处理机。(5〕时间片轮转系统将所有的就绪进程按先来先效劳的原那么排成一个队列，将CPU分配给对首进程，执行一个时间片。在时间片内进程未完，那么插入就绪队列末尾，CPU交给下一个进程。(6〕多级反应队列调度算法1〕设置多个就绪队列，并为各个队列赋予不同的优先级和不同长度的时间片；2〕新创立的进程挂到第一优先级的队列后，然后按FCFS原那么排队等待调度。当轮到其执行时，如果它能在时间片内完成，便撤离系统；如果不能完成，便被挂入第二级队列后，。。。。最后一级队列采用时间片轮转法；3〕仅当第一级队列空闲时，调度程序才调度第二级队列中的进程运行，依次类推。。。。。；新进程可抢占低级进程的处理机。多级反应队列调度算法具有较好的性能能满足终端型作业用户，短批处理作业用户，长批处理作业用户。4死锁的概念，产生原因和必要条件死锁是指两个或两个以上的进程在运行过程中，因争夺资源而造成的一种互相等待〔谁也无法继续推进〕的现象，假设无外力作用，它们都将无法推进下去。产生原因：竞争资源进程间推进顺序非法。必要条件：1互斥条件2请求和保持条件〔局部分配〕3不可剥夺条件〔不可抢占〕4环路等待条件〔循环等待〕5处理死锁的根本方法如何预防死锁通过设置某些限制条件，破坏导致死锁的四个必要条件之一。互斥条件有资源的性质决定，不能改变。摒弃"请求和保持"条件；摒弃"不可剥夺"条件；摒弃"循环等待"条件。如何防止死锁——银行家算法防止死锁的方法：在资源的动态分配过程中，用某种方法防止系统进入不平安状态。平安状态：系统能按某种进程顺序(P1,P2,…,P3)，来为每个进程Pi分配其所需资源，直至最大需求，使每个进程都可以顺利完成。反之，那么系统处于不平安状态。不平安状态不一定发生死锁，但死锁一定属于不平安状态。利用银行家算法防止死锁银行家算法的实质就是要设法保证系统动态分配资源后仍然保持平安状态，从而防止死锁的发生。要求进程预先告知自己的最大资源需求，并且假设系统拥有固定的资源总量。数据结构：可用资源向量Available最大需求矩阵Max分配矩阵Allocation需求矩阵Need资源请求向量Requesti平安性算法：工作向量Work、Finish〔平安序列需要过程〕第四章存储器管理1.虚拟储存器的特征与概念概念：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种储存器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的本钱却又接近于外村。特征：屡次性，对换性，虚拟性。2.请求分页储存管理方式的硬件支持1〕一台具有一定容量的内存及外存的计算机系统2〕页表机制3〕缺页中断机构4〕地址变换机构3.根本分页存储管理方式页面与物理块：分页存储管理是将一个进程的逻辑地址空间分成假设干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，相应的，也把内存空间分成与页面相同大小的假设干个存储块，称为块或页框，也同样把他们加以编号，在为进程分配内存时，以块为单位将进程中的假设干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。页表：在分页系统中，允许将进程的各个页离散地存储在内存不同的物理块中，但系统应能保证进程的正确运行，既能在内存中找到每个页面所对应的物理块。为此，系统尤为每个进程建立了一张页面映像表，称为页表。第五章设备管理1.设备控制器的作用及功能、I/O通道概念作用：设备控制器是计算机中的一个实体，其主要职责是控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换。功能：接受和识别命令；数据交换；标识和报告设备的状态；地址识别；数据缓冲；过失控制。I/O通道：I/O通道是一种特殊的处理机，它具有执行I/O指令的能力，并通过执行通道〔I/O〕程序来控制I/O操作。2.四种I/O控制方式程序I/O方式；中断驱动I/O控制方式；直接存储器访问〔DMA〕I/O控制方式；I/O通道控制方式。DMA控制器的组成(1)命令/状态存放器CR(2)内存地址存放器MAR(3)数据存放器DR:暂存从设备到内存的数据，或反之(4)数据计数器DC:存放本次CPU要读或写的字(节)数3.缓冲的作用、类型作用：1〕缓和CPU与I/O设备间速度不匹配的矛盾。2〕减少对CPU的中断频率。3〕提高CPU和I/O设备之间的并行性。类型：单缓冲和双缓冲；循环缓冲；缓冲池4.I/O软件的层次结构1〕用户层软件2〕设备独立性软件3〕设备驱动程序4〕中断处理程序5.中断处理程序的处理过程1〕唤醒被阻塞的驱动〔程序〕进程2〕保护被中断进程的CPU环境3〕转入相应的设备处理程序4〕中断处理5〕恢复被中断进程的现场。6.设备驱动程序的处理过程1〕将抽象要求转换为具体要求2〕检查I/O请求的合法性3〕读出和检查设备的状态4〕传送必要的参数5〕工作方式的设置6〕启动I/O设备7.设备独立性概念设备独立性，即应用程序独立于具体使用的物理设备。8.设备分配中涉及的数据结构设备控制表DCT，控制器控制表COCT，通道控制表CHCT，系统设备表SDT9.Spooling(假脱机)技术的概念、组成及应用概念：为了缓和CPU的高速性与I/O设备低俗性间的矛盾而引入了脱机输入、脱机输出技术组成：1〕输入井和输出井2〕输入缓冲区和输出缓冲区3〕输入进程SPi和输出进程SPo应用：共享打印机〔SPOOLing系统做的两件事：1.有输出进程在输出井中为之申请一个空闲磁盘块区，并将要打印的数据送入其中；2.输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到请求打印队列上〕SPOOLing系统的特点:(1)提高了I/O的速度，缓和了CPU与低速I/O设备速度不匹配的矛盾(2)利用高速共享设备，将独占设备改造为共享设备(3)实现了虚拟设备功能：用户都感到独占了一台设备10.磁盘调度算法1〕先来先效劳FCFS(磁头随意)2〕最短寻道时间优先SSTF(随意)3〕扫描算法SCAN(先顺一个方向,后反方向)4〕循环扫描算法CSCAN(一个方向)(5〕NStepSCAN和FSCAN调度算法第六章文件管理1.文件的概念、类型概念：文件是指由创立者所定义的，具有文件名的一组相关元素的集合，可分为有结构文件无结构文件两种。类型：按用途分类：系统文件，用户文件，库文件；按文件中数据的形式分类：源文件，目标文件，可执行文件。2.文件的逻辑结构、组织方式逻辑结构：从用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立与文件的物理特性，又称为文件组织。可分为两类：〔1〕有结构文件〔2〕无结构文件组织方式：有结构文件组织方式〔1〕顺序文件,效率低〔2〕索引文件〔3〕索引顺序文件。无结构文件为流式文件3.文件的物理结构、外存分配方式文件的物理结构：又称为文件的存储结构，是指文件在外存上的存储组织形式外存分配方式：连续分配，链接分配。4.连续、链接、索引方式的实现、优缺点连续分配方式要求为每一个文件分配一组相邻接的盘块。连续分配的优点：〔1〕顺序访问容易2〕顺序访问速度快。缺点1〕要求有连续的存储空间2〕必须事先知道文件的长度。链接分配：优点：提高了磁盘空间利用率,不存在外部碎片问题；有利于文件插入和删除；有利于文件动态扩充。缺点：隐式链接的主要问题是：它只适合于顺序访问，对随机访问是极其低效的。显式链接的主要问题：不能支持高效地直接存取，FAT表需占用较大的内存空间。索引分配：优点：保持了链接结构的优点,又解决了其缺点：按块分配可以消除外部碎片，按大小可变的分区分配可以提高局部性。索引分配支持顺序访问文件和直接访问文件，是普遍采用的一种方式；满足了文件动态增长、插入删除的要求〔只要有空闲块〕；能充分利用外存空间。缺点：较多的寻道次数和寻道时间；索引表本身带来了系统开销，如：内外存空间，存取时间5.要求、文件控制块(FCB)、各目录结构的优缺点对目录管理的要求：1〕实现“按名存取”2〕提高对目录的检所速度3〕文件共享4〕允许文件重名。文件控制块：文件控制块通常含有三类信息，即根本信息，存取控制信息及使用信息。一个FCB就是一个文件目录项.1〕根本信息类包括：文件名，文件物理位置，文件逻辑结构，文件物理结构。2〕存取控制信息类：文件主的存取权限，核准用户的存取权限以及一般用户的存取权限3〕使用信息类：文件的建立日期和时间，文件上一次修改的日期和时间及当前使用信息〔这项信息包括当前已翻开该文件的进程数、是否被其他进程锁住、文件在内存中是否已被修改但尚未拷贝到盘上〕。各目录结构的优缺点：目录结构：单级目录，两级目录，多级目录。单级目录优点：简单且能实现目录管理的根本功能——按明存取。缺点：1〕查找速度慢2〕不允许重名3〕不便于实现文件共享两级目录优点：克服了单级目录的缺点，并具有以下优点：1〕提高了检索目录的速度2〕在不同的用户目录中，可以使用相同的文件名3〕不同用户还可使用不同的文件名来访问系统中的同一个共享文件。缺点：该结构将多个用户隔开，不利于用户间的相互合作，不便于共享文件。多级目录结构：优点：查询速度快，同时层次结构更加清晰，能够更加有效的进行文件的管理和保护。在多级目录中，不同性质，不同用户的文件可以构成不同的目录子树，不同层次，不同用户的文件分别呈现在系统目录树中的不同层系或不同子树中，可以容易的赋予不同的存取权限。缺点：在多级目录中查找一个文件，需要按路径名逐级访问中间节点，这就增加了磁盘的访问次数，影响查询速度。6.文件存储空间的管理文件存储空间的管理方法：空闲表法和空闲链表法，位示图法，成组链接法。位示图法：是利用二进制的一位来表示磁盘中一个盘快的使用情况。当其值为0时，表示对应的盘块空闲；为1时，表示已分配。成组链接法：文件共享的方式：基于索引结点的共享方式，利用符号链实现文件共享.优点:四章存储器管理固定、动态、可重定位分区分配算法固定分区分配最简单的一种可运行多道程序的存储管理方式。划分分区的方法：分区大小相等：缺乏灵活性，用于控制多个相同对象的系统分区大小不等：多个较小分区、适量中等分区、少量大分区内存分配管理：将分区按大小排队建立分区使用表——起址、大小、状态程序装入时，由内存分配程序检索分区使用表，找到符合要求的分区，并进行标记。动态分区分配根据进程的实际需要，动态的分配内存空间内存管理方式：空闲分区表——序号、起址、大小等项空闲分区链——双向链表分区分配算法〔1〕首次适应算法：空闲分区按起址递增次序排列，从头开始直至找到第一个满足要求的空闲分区。特点：内存低端会留下小的空闲区，高端有大的空闲区；〔2〕循环适应算法：从上次分配的位置之后开始查找。特点：使内存的空闲分区均匀，但缺乏大的空闲分区；〔3〕最正确适应算法：空闲分区按大小递增的次序排列，从头开始找到第一个满足要求的空闲分区。缺点：会留下大量小碎片。〔4〕最差适应算法：空闲分区按大小递减的次序排列，最前面的最大的空闲分区就是找到的分区。优点：分配后剩下的可用空间比拟大缺点：一段时间后就不能满足对于较大空闲区的分配要求。〔5〕快速适应算法(quickfit)：又称分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。在内存中需设立一张管理索引表管理空闲分区链表。优点：查找效率高、不产生内存碎片缺点：在分区归还主存时算法复杂，系统开销较大分区存在浪费分区分配操作〔分配算法流程〕分配内存:从空闲分区链〔表〕中找到所需大小的分区。判断条件：M.Size-U.Size≦Size剩余局部挂接到空闲分区链〔表〕上。回收内存:回收区与插入点的前一个空闲分区相邻接；回收区与插入点的后一个空闲分区相邻接；回收区与插入点的前后两个空闲分区相邻接；回收区不与任何一个空闲分区相邻接；优缺点:管理复杂，总会有闲置的小分区——“碎片”。动态重定位的实现:必须由硬件地址变换机构支持实现——重定位R重定位存放器：存放程序在内存中的起始地址。可重定位分区分配算法:与动态分区分配算法根本相同，但增加了紧凑功能优缺点分析:优点：消除了“碎片”，提高了内存利用率，同时提高了系统效率。缺点：需要动态重定位“硬件”机构支持，增加了系统本钱，并轻度降低了程序执行速度，“紧凑”处理增加了系统开销。根本分页存储管理方式页、块、页表、地址结构、物理地址与逻辑地址的转换、地址变换机构页：分页存储管理是将一个进程的逻辑地址空间分成假设干个大小相等的片，称为页面或页，并为各页加以编号。块：把内存空间分为与页面相同大小的假设干个存储块，称为〔物理〕块或页框，也同样为它们加以编号。页表——页面映像表数据结构：页号、块号、存取控制项页表的作用：实现从页号到物理块号的地址映射。地址结构根本的地址变换机构地址变换机构的任务：实现地址映射，即从逻辑地址到物理地址的变换过程。页表存放在内存系统区的一个连续空间中；PCB和页表存放器PTR中存有页表在内存的首地址和页表长度；地址映射过程：