操作系统原理知识点总结.pdf

第一章 绪论1、操作系统是一组控制和管理计算机硬件和软件资源、合理的对各类作业进行调度以方便用户的程序集合2、操作系统的目标操作系统的目标：方便性、有效性、可扩展性、开发性3、操作系统的作用操作系统的作用：作为计算机硬件和用户间的接口、作为计算机系统资源的管理者、作为扩充机器4 4、单批道处理系统、单批道处理系统：作业处理成批进行，内存中始终保持一道作业（自动性、顺序性、单道性）5 5、多批道处理系统、多批道处理系统：系统中同时驻留多个作业，优点：提高 CPU 利用率、提高 I/O 设备和内存利用率、提高系统吞吐量（多道性、无序性、调度性）6 6、分时技术特性、分时技术特性：多路性、交互性、独立性、及时性，目标：对用户响应的及时性7 7、实时系统、实时系统：及时响应外部请求，在规定时间内完成事件处理，任务类型：周期性、非周期性或硬实时任务、软实时任务88、操作系统基本特性、操作系统基本特性：并发、共享、虚拟、异步性并行是指两或多个事件在同一时刻发生。并发是两或多个事件在同一时间间隔内发生。互斥共享：一段时间只允许一个进程访问该资源同时访问：微观上仍是互斥的虚拟是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。异步是指运行进度不可预知。共享性和并发性是操作系统两个最基本的特征共享性和并发性是操作系统两个最基本的特征99、操作系统主要功能、操作系统主要功能：处理机管理、存储器管理、设备管理、文件管理、用户管理第二章第二章 进程的描述和控制进程的描述和控制11、程序顺序执行特征、程序顺序执行特征：顺序性、封闭性、可再现性22、程序并发执行特征、程序并发执行特征：间断性、失去封闭性、不可再现性3、前趋图：有向无循环图，用于描述进程之间执行的前后关系表示方式：（1）p1-p2（2）-=(p1,p2)|p1 必须在 p2 开始前完成节点表示：一条语句，一个程序段，一进程。（详见书 P32）4、进程的定义：进程的定义：(1)是程序的一次执行过程，由程序段、数据段、程序控制块由程序段、数据段、程序控制块（PBCPBC）三部分构成）三部分构成，总称“进程映像”(2)是一个程序及其数据在处理机上顺序执行时所发生的活动(3)是程序在一个数据集合上的运行过程(4)进程是进程实体的运行过程，是系统进行资源分配资源分配和调度调度的一个独立单位进程特征进程特征：动态性、并发性、独立性、异步性由“创建”而产生，由“调度”而执行；由得不到资源而“阻塞”，由“撤消”而消亡 5、进程与程序关系进程与程序关系进程程序概念动态实体，强调执行过程静态实体，是指令的有序集合特征并发性、独立性、异步性,是竞争计算机系统资源的基本单位无并行特性，是静止的二者联系不同进程可以共享同一程序，只要对应数据集不同6、进程的三种状态进程的三种状态：就绪、阻塞、执行 转换：增加挂起：7、进程控制块进程控制块（PCB）的作用：进程存在的唯一标志。8 8、进程创建：进程创建：（1）申请空白 PCB（一个系统的 PCB 是有限的）（2）为新进程分配资源（3）初始化 PCB（4）将新进程插入就绪队列。进程终止：（1）检查进程状态；（2）执行态中止，且置调度标志为真。（3）有无子孙需终止。（4）归还资源给其父进程或系统。（5）从 PCB 队列中移出 PCB.9、原语原语：是由若干条指令组成的，用于完成一定功能的一个过程，原语在执行中不允许被中断，原语的作用原语的作用是实现进程的通信和控制。10、进程同步进程同步：并发进程在执行次序上的协调，以达到有效的资源共享和相互合作，使程序执行有可再现性。11、两种制约关系：资源共享关系：（进程间接制约）需互斥地访问临界资源。相互合作关系：（进程直接制约）12、临界资源临界资源：一次仅允许一个进程访问的资源引起不可再现性是因为临界资源没有互斥访问。临界区：进程访问临界资源的那段代码。13、同步资源应遵循的准则同步资源应遵循的准则：空闲让进、忙则等待、有限等待、让权等待14、整形信号量、记录型信号量、AND 型信号量（书 P53 2.4.3 和2.4.4）15、生产者消费者问题（书 P60）16、操作系统中引入进程的目的操作系统中引入进程的目的是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量，在操作系统中再次引入县城，则是为了减少程序在并发执行时所付出的时空开销。17、管程的定义：管程的定义：定义了一个数据结构和能为并发进程在该数据结构上执行的一组操作，这祖操作能同步进程和个 i 变管程中的数据。18、线程的概念线程的概念：线程是金成中的一个实体，是被系统独立调度和分派的基本单位。一个线程可以创建和撤销另一个线程；同一个进程中的多个线程之间可以并发执行。19、进程与线程比较进程与线程比较进程线程引入目的能并发执行，提高资源的利用率和系统吞吐量提高并发执行的程度，减小开销，进一步提高资源的利用率和系统吞吐量并发性较低较高基本属性（调度）资源拥有的基本单位独立调度/分派的基本单位基本状态就绪；执行；等待就绪；执行；等待拥有资源资源拥有的基本单位无资源分配系统开销创建/撤销/切换时空开销大创建/撤销/切换时空开销较小系统操作创建，撤销，切换创建，撤销，切换存在标志进程控制块（PCB）线程控制块（TCB）关系单进程单线程；单进程多线程；多进程单线程；多进程多线程第三章第三章 处理机调度与死锁处理机调度与死锁1、处理机调度处理机调度：高高级调度（作业调度、长程调度）：将外存上的作业插入就绪队列。中中级调度（中程调度）：为提高系统吞吐量和内存利用率而引入的一内外存对换功能。低低级调度（进程调度、短程调度）：把处理器分配给程序，对象是进程。高级调度与低级调度的区别高级调度与低级调度的区别 高级调度又称为作业调度或长程调度，调度对象是作业，作业调度往往发生于一个（批）作业运行完毕，退出系统，而需要重新调入一个（批）作业进入内存时，故作业调度的周期长；低级调度又称为进程调度和短程调度，调度物件为进程（或内核级线程），进程调度的运行频率最高，是最基本的一种调度，多道批处理、分时、实时三类 OS 中必须配置这种调度。引入中级调度的主要目的引入中级调度的主要目的：是为了提高系统资源的利用率和系统吞吐量2 2、选择调度方式和调度算法的准则、选择调度方式和调度算法的准则:面向用户准则：（1）周转时间短平均周转时间：带权周转时间：（2）响应时间快（对交互性作业）（3）截止时间保证（特别对于实时系统）（4）优先权准则（需要抢占调度）3、面向系统准则（1）系统吞吐量高（2）处理机利用率好（3）各类资源平衡利用4 4、调度算法：、调度算法：在中调度实质是一种资源的分配。先来先服务（FIFO）和短作业（进程）优先调度算法（SJF/SPF）、高优先权优先调度算法、基于时间片的轮转调度算法。实时调度算法实时调度算法：最早截止时间优先（EDF）：根据任务的截止时间来确定任务的优先级截止时间越早，优先级越高可以是抢占式或非抢占式最低松弛度优先（LLF）：主要用于可抢占的调度方式中松弛度=必须完成时间-本身运行时间-当前时间11niiTnT11nisiTTnW6、何谓死锁？产生死锁的原因和必要条件是什么？何谓死锁？产生死锁的原因和必要条件是什么？a.死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进；b.产生死锁的原因有二，一是竞争资源，二是进程推进顺序非法；c.必要条件是:互斥条件，请求和保持条件，不剥夺条件和环路等待条件8、处理死锁的基本方法处理死锁的基本方法：(1)预防死锁破坏产生死锁的四个必要条件中的一个或几个条件(2)避免死锁破坏产生死锁的四个必要条件(3)检测死锁通过系统设置的检测机构，及时检测出死锁的发生(4)解除死锁撤销或挂起一些进程预防死锁的方法预防死锁的方法:a.摒弃请求和保持条b.摒弃不剥夺条件c.摒弃环路等待条件9、（大题）银行家算法、安全性算法银行家算法、安全性算法(1)如果 Request=Need，去（2），否则错误(2)如果 Request=Available，去（3），否则等待(3)系统尝试分配资源给进程 Pi，并修改值Available=Available RequestAllocation=Allocations+RequestNeed=Need Request (4)安全检查，即所有进程都顺利完成第四章第四章 存储器管理存储器管理1、程序的装入程序的装入：绝对装入绝对装入：编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。可重定位装入可重定位装入：静态重定位：装入时完成，主要工作是对相对地址中的指令和数据地址的调整过程。动态运行时装入（动态重定位）：程序执行过程中，当访问指令或数据时，才进行的地址变换方法2、程序的链接程序的链接：静态链接、装入时动态链接、运行时动态链接。3、连续分配方式连续分配方式：单一连续分配：用于单用户单任务分区式分配：固定分区分配：分区大小不相等的利用率更高；动态分区分配；可重定位分区分配。4、分配算法分配算法：首次适应算法要求：分区按低址高址链接特点：找到第一个大小满足的分区，划分。有外零头，低址内存使用频繁。循环首次适应算法从上次查找的位置的下一个空闲空闲分区开始查找。特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。最佳适应算法分区按大小递增排序分区释放时需插入到适当位置。5、对换对换：概念：将阻塞的进程，暂时不用的程序、数据换出，将具备运行条件的数据换入。类型：整体对换、部分对换（页面对换、分段对换）空间管理：分为对换区和文件区对换区比文件区侧重于对换速度因此，对换区一般采用连续分配。采用数据结构和分配回收类似于可变化分区分配。6 6、页面与页表页面与页表分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页。由于进程的最后一页经常装不满一块而形成不可利用的碎片，称为“页内碎片”。系统为每个进程建立一张页面映像表，简称页表。页表的作用是实现从页号到物理块号的地址映射。7、基本分页存储管理方式基本分页存储管理方式 ：连续分配引起碎片碎片问题的解决：紧凑方式消耗系统开销解决方式用离散分配：分页、分段、段页页面和物理块：由机器的地址结构决定，将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从 0 开始。相应的把内存空间分成与页面相同大小的若干个存储块，称为物理块或页框。页面大小：通常在 512B8KB页太大，页内碎片大。页太小：页表可能很长，换入/出效率低地址结构（逻辑地址换物理地址基础）（参照 ppt 第四章和书 P139）地址变换机构：页表完成逻辑页号到物理块号的映射有快表访问内存速度会提高，但是快表不能太多题型：已知一次存取时间和快表命中率求访问时间已知逻辑地址求物理地址（第四章 PPT 有详解）8、基本分段储存管理基本分段储存管理：即多重定位分区管理原因：原因：引入分段存储管理方式，主要是为了满足用户和程序员的下述一系列需要：（1）方便编程（2）分段共享（3）分段保护（4）动态链接（5）动态增长对用户而言分段是二维的：段号+段内地址分段基本原理分段基本原理：每个段定义了一组逻辑信息，主程序段、子程序段、数据段等分页与分段的区别：（1）页是信息的物理单位，段是逻辑单位（2）页长度固定，段长度不固定（由用户指定）（3）一维与二维 段式系统易于共享9、虚拟存储器常规存储器特征：一次性、驻留性局部性原理：时间局部性（循环执行）、空间局部性（顺序执行）虚拟存储器定义：具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统虚拟存储器实质：以时间换空间，但时间牺牲不大虚拟存储器特征：离散性（部分装入）、多次性（局部多次装入）、对换性、虚拟性（大题必考）9、页面置换算法：FIFO、LRU、CLOCK（第四章ppt、书）第五章第五章 设备管理设备管理1、设备分类设备分类：按速度分：低（键盘）、中（打印机）、高（磁盘）按信息交换单位分：块（磁盘）、字符（打印机）按设备的共享属性分：独占（临界资源）、共享（磁盘）、虚拟2、设备控制器设备控制器：接收 CPU 命令，控制 I/O 设备工作，解放 CPU3、I/OI/O 通道通道：一种特殊的执行 I/O 指令的处理机，与 CPU 共享内存，可以有自己的总线。CPU 只需发送 I/O 命令给通道，通道通过调用内存中的相应通道程序完成任务类型类型：字节多路通道：各子通道以时间片轮转方式共享通道，适用于低、中速设备数组选择通道:无子通道，仅一主通道，某时间由某设备独占，适于高速设备。但通道未共享，利用率低数组多路通道:多子通道不是以时间片方式，而是“按需分配”，综合了前面 2 种通道类型的优点4、I/O 控制的四个阶段：程序 I/O、中断 I/O、DMA 控制、通道控制5、控制器的组成控制器的组成DMA 控制器由三部分组成：主机与控制器的接口、DMA 控制器与块设备的接口、I/O 控制逻辑。为了实现主机与控制器之间成块数据的直接交换，需设置控为了实现主机与控制器之间成块数据的直接交换，需设置控制器中四类寄存器制器中四类寄存器DR：数据寄存器，暂存从设备到内存或从内存到设备的数据MAR：内存地址寄存器DC：数据计数器，存放本次 CPU 要读或写的字（节）数CR：命令状态寄存器，接收从 CPU 发来的 I/O 命令，或相关控制信息，或设备状态6 6、缓冲的引入原因、缓冲的引入原因 操作系统引入缓冲机制的主要原因可归结为以下几点：（1）缓和 CPU 与 I/O 设备间速度不匹配的矛盾；（2）减少对 CPU 的中断频率，放宽对中断响应时间的限制；（3）提高 CPU 与 I/O 设备之间的并行性。7 7、缓冲池的组成、工作方式、缓冲池的组成、工作方式 三个队列：空缓冲队列、输入队列、输出队列 四种工作缓冲区：（1）用于收容输入数据的工作缓冲区；（2）用于提取输入数据的工作缓冲区；（3）用于收容输出数据的工作缓冲区；（2）用于提取输出数据的工作缓冲区；8、SPOOLINGSPOOLING 技术技术：定义：假脱机技术，在联机状态下同时出现外围操作作用：通过缓冲方式，将独占设备改造为共享设备特点：提高 I/O 速度。将独占设备改造为共享设备实现了虚拟设备功能9、磁盘：类型：固定头磁盘（快）、移动头磁盘（慢）访问时间：（大题）寻道方式：FCFS、SSTF、SCAN、CSCAN（PPT第五章）第六章第六章 文件系统文件系统1、程序和数据以文件的形式保留在外存中2 2、文件的定义属性：文件的定义属性：文件是指由创建者所定义的、具有文件名的一组相关信息的集合，可分为有机构文件和无结构文件。文件的属性包括：文件类型、文件长度、文件的物理位置、文件的建立时间。3、文件、记录和数据项文件、记录和数据项：数据项基本数据项：可命名的最小逻辑单位/字段组合数据项：由若干基本数据项组成记录一组相关数据项的集合关键字：能唯一地标识出记录的基本/组合数据项文件具有文件名的一组相关信息的集合，可分为有结构文件和无结构文件（流式文件）4、文件类型文件类型：用途：系统文件、用户文件、库文件文件中的数据形式：源文件、目标文件、可执行文件存取控制：只执行文件、只读文件、读写文件物理安排：顺序文件、链接文件、索引文件5、文件系统模型概念：文件和对文件进行操纵和管理的软件集合三个层：文件(对象及属性)文件操作文件访问对象及属性：文件、目录、磁盘存储空间文件系统接口：命令接口、程序接口文件操作基本操作：创建、删除、读、写、截断、设置文件的读写位置、打开关闭操作6、文件逻辑结构文件逻辑结构：概念：用户所能观察和访问到的文件的数据结构组织，独立于物理特性，容易检索和修改。无论是逻辑还是物理结构，都会影响到文件的检索速度逻辑结构类型：有结构文件：定长记录、变长记录记录的组织形式：顺序文件、索引文件、顺序索引文件无结构文件：流式文件，以字节为单位，利用读/写指针进行访问记录式文件、流式文件7 7、顺序文件顺序文件逻辑记录排序：按记录时间排：串结构 按关键字排：顺序结构后一种情况更有利于提高查询速度。如可用折半查找法等对顺序文件的读/写操作定长记录：易于定位，甚至可随机读取。变长记录：不易定位，只能顺序读取。最佳适用场合是在对诸记录进行批量存取时。批量存取时对顺序文件的存取速率是所有逻辑文件中最高的；只有顺序文件能存储在磁带上，并能有效地工作。在交互应用场合，顺序文件表现出来的性能很差；如果想增加或删除一个记录都比较困难。8 8、索引文件索引文件由变长记录组成的顺序文件不容易直接存取，因此，为其建立一有序的索引表，对索引采用折半查找，速度更快特点：提高了速度，增加了存储开销放索引文件增、删记录时，对索引表作相应的修改9 9、索引顺序文件索引顺序文件将顺序文件中若干记录分为一组，每组的第一项在索引表中占一项10、外存分配方法：连续分配：每个文件分配一组相邻盘块特点：简单链接分配：文件离散地分配于各盘块中，以提高外存利用率，文件长度可变，易于增删，只能顺序存取隐式链接：文件目录表中有 start 块号，每块中有下一块号。特点：只适合于顺序访问，对随机访问效率低，可靠性差。显式链接：把用于链接的指针显式存放在内存的一张表中，查找在内存中进行索引分配单级索引：为每个文件分配一个索引块特点：（1）文件较大时有利。文件较小时浪费外存空间（还需为小文件建索引块）（2）当文件较大时，索引块太多，查找速度减慢解决：当索引太大时，则需建立多级索引多级索引11、文件目录文件目录：文件控制块的有序集合功能功能/要求要求：（1）按名存取；（2）提高检索速度；（3）文件共享；（4）允许文件重名。单级目录结构两级目录结构树型目录结构1212、文件存储空间管理文件存储空间管理空闲表法空闲链表法空闲盘块链空闲盘区链位示图法成组链接法