《南阳理工学院操作系统复习重点(共28页).docx》由会员分享，可在线阅读，更多相关《南阳理工学院操作系统复习重点(共28页).docx（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上 复习重点第一章1. 什么是操作系统？操作系统（OS）是直接配置在计算机硬件上的最基本的系统软件，负责管理计算机的软硬件资源，实现对计算机资源的抽象，为用户提供方便易用的借口。2. 操作系统的四个目标：1）有效性（提高系统资源利用率，提高系统的吞吐量）2）方便些3）可扩充性4）开放性3. 操作系统的三大作用：1）OS作为用户与计算机硬件系统之间的借口2)OS作为计算机系统资源的管理者3）OS实现了对计算机资源的抽象4. 历史上的三种基本类型的操作系统：多道批处理系统，分时系统，实时系统5. 实时系统，分时系统的比较：1)多路性2）独立性3）及时性：实时信息处理系统对实
2、时性的要求与分实行系统类似，都是以人所能接受的等待时间来确定，而实时系统的及时性，是以控制对象所要求得的开始截止时间或完成截止时间来确定，一般为秒级到毫级，甚至有的要求低于100微妙。4）交互性：实时信息处理系统虽然也具有交互性，但这是人与系统的交互仅限于访问系统中某些特定的专用服务程序。它不像时分系统那样能像终端用户提供数据处理和资源共享服务5）可靠性：分时系统虽然也要求系统可靠，但相比之下，实时系统则要求洗头具有高度的可靠性，因为任何差错都有可能到来巨大的经济损失，甚至是无法预料的灾难性后果，所以在实时系统中，往往都采取了多级容错措施来保障系统的安全性及数据的安全性。6. 操作系统的四大基
3、本特征：并发性，共享性，虚拟性，异步性 其中并发和共享是最基本的特征，有事互为存在的条件，并发性是最重的特征7. 为什么要引入进程？为了是程序能可靠的并发，于是把程序包装成进程，程序以进程实体的方式驻留在内存，轮流占用CPU执行。8. 进程的特征：1）结构特征。程序段、相关数据段和进程控制块(Process Control Block, PCB)三部分构成了进程实体；2）动态性。进程由创建而产生，由调度而执行，由撤销而消亡，此即进程的生命期；3）并发性。引入进程的目的就是为了能够并发执行；4）独立性。进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。5）异步性。进程实体按照异步方
4、式，各自独立地以不可预知的速度向前推进。9. 进程的三种基本状态极其转换关系：10.进程控制块（PCB）是进程实体的一部分，是操作系统中最重要的记录性数据结构，记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的所有信息。OS是根据PCB来对并发执行的进程进行控制和管理11.进程控制块（PCB）是进程存在的唯一标志。为什么呢？当系统创建一个新进程时，就为它建立了一个PCB；进程结束时又回收其PCB，进程于是也随之消亡。PCB经常被系统访问，尤其是被运行频率很高的进程及分派程序访问，故PCB应常驻内存。12.进程并发执行时的相互制约关系1）间接相互制约关系，源于互斥资源的共享2）直接相
5、互制约关系，源于进程间的合作13.临界资源和临界区的概念：许多硬件资源如打印机，磁带机等，都属于临界资源。对于临界资源(Critical Resource)，无论是硬件临界资源（打印机等），还是软件临界资源（例如前面讨论生产者-消费者问题的变量counter），多个进程必须互斥地对它进行访问。人们把每个进程中访问临界资源的那段代码称为临界区(Critical Section)。14.同步机制四准则：空闲让进，忙则等待，有限等待 避免“死等”，让权等待 避免“忙等15.信号量机制：整型信号量：会出现“忙等”，未遵循让权等待准则。 wait(S): while SC时，系统对每一块数据的处理时间为
6、M+T，反之则为M+C，故可把系统对每一块数据的处理时间表示为Max(C，T)+M。44. 双缓冲区：双缓冲又称为缓冲对换(Buffer Swapping)，可加快输入输出速度，提高设备利用率。双缓冲时，系统处理一块数据的时间可以粗略地认为是Max(C，T)。如果CT，则可使CPU不必等待设备输入45. I/O软件：I/O软件的总体目标是高效性和通用性46. I/O软件的层次结构：1）用户层软件(高层)：实现与用户交互接口，用户可直接调用在用户层提供的，与I/O操作有关的库函数，对设备进行操作。2）设备独立性软件(中间层)：负责实现与设备驱动器的统一接口，设备命名，设备的保护以及设备的分配与释
7、放等，同时为设备管理与数据传送提供必要的存储空间。3）设备驱动程序(低层)：与硬件直接相关，负责具体实现系统对设备发出的操作指令，驱动I/O设备工作的驱动程序。4）中断处理程序(最低层)：用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完后再恢复被中断进程的现场后返回到被中断进程。此图为重点图之一在课本P179页可出选择或简答题（同上所诉）47.设备分配：需要用到一下几种数据结构;DCT(设备控制表)，COCT（控制器控制表），CHCT（通道控制表），SDT（系统设备表）48. SPOOLing技术：体现了操作系统的四大特征之一：虚拟性，第一章讲过脱机输入、输出技术，可缓和
8、CPU高速性和I/O设备低速性的矛盾。在多道程序系统中，可用一个进程SPi模拟脱机输入的外围机，把低速输入设备上的数据传送到高速磁盘上；用另一个进程SPo模拟脱机输出的外围机，把数据从高速磁盘传送到低速输出设备上。这样在CPU的直接控制下，模拟脱机输入、输出功能，使外围操作与CPU对数据的处理同时进行，这种联机操作称为SPOOLing(Simultaneous Peripheral Operations On-Line)，或称为假脱机操作。48.SPOOLing系统的特点：1）提高了I/O的速度 2）将独占设备改为共享设备 3）实现了虚拟设备的功能49.寻道时间（T）：其占据了磁盘访问时间的大
9、头，且可用磁盘调度算法进行优化。 改时间是启动磁臂的时间S与磁头移动n条磁道所花费的时间之和，即 T=m x n + s 其中m是一常数50.磁盘调度算法：1）先来先服务（FCFS）算法：平均寻道长度最大，故仅适用于请求磁盘I /O的进程数目较少的场合。根据进程请求访问磁盘的先后次序进行调度。缺点是平均寻道距离大，平均寻道时间长。2）最短寻道时间优先算法（SSTF）：存在starvation（饥饿）现象，优先选择要求访问的磁道与当前磁头所在的磁道距离最近的进程，以使每次寻道时间最短，但SSTF算法不能保证平均寻道时间最短，并且可能导致进程饥饿(starvation)现象。3）扫描（SCAN）算
10、法又称电梯调度算法：该算法不仅考虑欲访问的磁道与当前磁道的距离，更优先考虑磁头当前的移动方向。其磁头移动规律颇似电梯的运行，又称电梯调度算法。既有较好的寻道性能，又避免饥饿现象。4）循环扫描（CSCAN）：CSCAN是SCAN变种，规定磁头只能单向移动(例如自里向外)，移动到最外磁道访问后立即移动到最里的欲访问磁道，亦即将最小磁道号紧接着最大磁道号构成循环。相比SCAN可降低进程的最大等待时间(由2T降到TSmax)。5）算法和算法：SSTF、SCAN、CSCAN都可能会出现磁臂粘着(arm stickiness)现象，即有一个或几个进程对某一磁道访问频率很高，磁臂停留在该磁道不动，从而垄断了
11、整个磁盘设备，在高密度磁盘上容易出现此情况。N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列，而每处理一个队列时又是按SCAN算法。可避免粘着现象。当N取值很大时，NStepSCAN接近SCAN；当N=1时， NStepSCAN退化为FCFS。FSCAN实质上是对NStepSCAN的简化，只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘I/O的进程形成的队列，另一个是扫描期间新出现的所有请求磁盘I/O的进程形成的等待队列。先来先服务（FCFS）算法最短寻道时间优先算法（SSTF）扫描（SCAN）算法又称电梯调度算法循环扫描（CSCA
12、N） 第六章 文件管理（p-208）（重点）文件的逻辑结构：是从用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，独立于文件的物理特性，又称为文件组织(File Organization)。（重点）文件的物理结构：又称为文件的存储结构，是指文件在外存上的存储组织形式，不仅与存储介质性能有关，而且与所采用的外存分配方式有关。无论是文件的逻辑结构，还是其物理结构，都会影响到文件的检索速度。文件逻辑结构的类型有结构文件。根据每个记录的长度，可分为定长记录、变长记录两类；根据各记录的组织形式，可分为顺序文件、索引文件、索引顺序文件三种。无结构文件，即流式文件文件的逻辑结构：顺序文件
13、:文件是记录的集合，文件中的记录可以是任意顺序的，可归纳为串结构和顺序结构两种。串结构文件的检索只能逐个记录遍历，而对顺序结构文件可有更好的检索效率。顺序文件的优点是对诸数据进行批量存取时效率最高，并且只有顺序文件能存储在磁带上。缺点是在文件较大时，查找或修改单个记录性能很差，尤其是采用变长记录的顺序文件开销更大；并且，增加或删除一个记录都比较困难。索引文件:对于定长记录的顺序文件可较方便地实现直接存取，但变长记录的直接存取是十分低效的，检索时间太长。所以可为其建立一张索引表，而索引表本身是一个定长记录的顺序文件。对索引文件检索分为两步，第一步可用折半查找法检索索引表，找到相应表项；第二步利用
14、该表项指向记录的指针，访问该条记录。索引文件可用于对信息处理及时性要求较高的场合。缺点是存储费用高。索引顺序文件:索引顺序文件可能是最常见的一种逻辑文件形式，可看作是顺序文件和索引文件的折衷。它将顺序文件中的所有记录分为若干个组，为顺序文件建立一张稀疏索引表，在稀疏索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的指针。检索时，首先利用用户提供的关键字(键值) 检索稀疏索引表，再利用顺序查找法查找主文件。其中，顺序文件的检索性能最差，索引文件的存储成本最高，索引顺序文件是前两者的折中。常用的外存分配方法有连续分配、链接分配和索引分配三种。文件的物理结构：文件的物理结
15、构直接与外存分配方式有关。采用连续分配方式时，形成顺序式的文件物理结构；链接分配方式形成链接式文件物理结构；索引分配方式形成索引式文件物理结构。连续分配(顺序结构)：连续分配(Continuous Allocation)为每个文件分配一组相邻接的盘块。此时的物理文件称为顺序文件。应在目录项的文件物理地址字段中，记录该文件第一个记录所在的盘块号和文件长度(以盘块数进行计量)。优点：顺序访问容易，且顺序访问速度快(磁头移动距离最短)。缺点： 要求有连续的存储空间，与内存动态分配类似，会产生大量碎片，紧凑开销很大； 必须事先知道文件长度，容易造成外存空间的严重浪费。（重点）链接分配：链接分配(Cha
16、ined Allocation)将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的物理文件称为链接文件。链接分配属于离散分配方式，消除了外存碎片，显著提高了外存空间利用率，并且当文件动态增长时可动态再分配盘块，无需事先知道文件大小，对文件的增、删、改也十分方便。链接分配又分为隐式链接和显式链接两种形式。1.隐式链接：采用隐式链接分配方式，在文件目录的每个目录项中须含有指向链接文件第一个盘块和最后一个盘块的指针，而在每个盘块中都含有一个指向下一个盘块的指针。2.显式链接：把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中，该表对整个磁盘仅设置一张，称为文件分配表(File A
17、llocation Table, FAT)。文件的第一个盘块号，作为文件地址被填入文件的FCB的物理地址字段中。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。FAT和NTFS技术在早期的MS-DOS的FAT文件系统中最早引入了卷的概念，把一个物理硬盘分成四个逻辑磁盘，分别是C: 、D: 、E: 、F: 。为了适应磁盘容量不断增大的需要，在进行盘块分配时，不再以盘块而是以簇(cluster)为基本单位。簇是一组连续的扇区，其容量可以是一个扇区(512B)、两个扇区、四个扇区、八个扇区(4KB)等。一个簇包含扇区的数量与最大支持的磁盘容量大小直接相
18、关。相比于FAT12、FAT16，FAT32可管理更多的簇，(相比于FAT16)可采用较小的簇，碎片减少，同时支持更大的磁盘空间。FAT32的每个簇固定为4KB，可管理的单个最大磁盘空间大到 4KB232 = 16TB。缺点是不支持小分区，单个文件的长度不能大于4GB，且不能向下兼容。索引分配1. 单级索引分配：索引分配与链接分配同属于离散分配方式。索引分配可克服链接分配方式的两个缺点：(1) 不能高效的直接存取；(2) FAT表占用较大的内存空间。单级索引分配方式为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中。当文件较大时，索引分配方式优于链接分配方式。但它的
19、缺点是：对于小文件，其索引块的利用率很低，此时索引分配方式反而不如链接分配方式。2. 多级索引分配：对大文件分配磁盘空间时，可采用两级索引的方式，如果文件非常大，还可用三级、四级索引分配方式。倘若盘块大小为4KB，每个盘块号占4个字节，则一个索引块中可存放1024个盘块号，采用两级索引最大支持的文件长度可达1024 1024 4KB = 4GB。（重点）3. 混合索引分配方式：在UNIX的文件系统中采用混合索引分配方式，是将多种索引分配方式相结合形成的一种分配方式。索引结点中设置了13个地址项，其中iaddr(0) iaddr(9)存放直接地址；iaddr(10)提供一次间接地址，实质上就是一
20、级索引分配方式；iaddr(11)提供二次间接地址，实质上就是二级索引分配方式；iaddr(12)提供三次间接地址。假设每个盘块大小为4KB，每个盘块号占4个字节。当文件不大于40KB时，可从地址项iaddr(0) iaddr(9)直接读出文件的全部盘块号。地址项iaddr(10)提供一次间接地址，实质上是一级索引分配方式，而一次间址块中可存放1K个盘块号，因此最大支持文件长度为4MB40KB。同理，iaddr(11)提供二次间接地址，实质上是二级索引分配方式，最大支持文件长度为4GB4MB40KB。iaddr(12)提供三次间接地址，最大支持文件长度为4TB4GB4MB40KB。目录结构1.
21、 单级目录结构 优点是简单且能实现基本的按名存取的功能。缺点是查找速度慢，不允许重名，也不便于实现文件共享。简而言之，只能满足目录管理四点要求中的第一点。只适用于单用户环境。2. 两级目录结构两级目录结构在系统中建立一个主文件目录(MFD)，对每个用户单独建立一个用户文件目录(UFD)。相比于单级目录结构，两级目录结构的优点是：检索速度更快，在不同的用户目录中可以使用相同的文件名，不同用户还可使用不同的文件名来访问系统中的同一个共享文件。3. 多级目录结构目录结构：多级目录结构又称树型目录结构，主目录被称为根目录，数据文件称为树叶，其他目录作为树的结点。路径名(path name)：系统中的每
22、个文件都有唯一的路径名，例如，图中的15号文件，其路径名为“/B/F/J ”。当前目录(current directory)：为方便起见，可为每个进程设置一个当前目录，又称工作目录。把从当前目录开始直到数据文件为止所构成的路径名，称为相对路径名；而把从树根开始的路径名称为绝对路径名。相比于两级目录，多级目录查询速度更快，层次结构更加清晰，能够更加有效地进行文件的管理和保护。但是在多级目录中查找一个文件，需要按路径名逐级访问中间节点，这就增加了磁盘访问次数，无疑将影响查询速度。在多级目录结构中删除目录时，若该目录为空，则可直接删除，但若其非空，则可用两种方法处理： 不删除非空目录，采用递归方式删
23、除目录中的所有文件及子目录后才可删除该目录； 可删除非空目录，其包含的所有文件及子目录也一并被删除。第种方法更方便，但比较危险。位示图法：盘块的分配步骤： 顺序扫描位示图，找到一个或一组值为0的位； 算得其盘块号，假设该位位于位示图的第行、第列，则盘块号b=n(i-1)+j; 修改位示图，令mapi,j=1。盘块的回收步骤： 将回收盘块的盘块号转换成位示图中的行号和列号i=(b-1)DIV n+1，j=(b-1)MOD n+1； 修改位示图，令mapi,j=0;位示图法的优点是，从位示图中很容易找到一个或一组相邻接的空闲盘块。位示图很小，可令它常驻内存，使得在每次进行盘区分配时，无需首先把盘区
24、分配表读入内存，从而节省了大量的磁盘启动操作。位示图常用于微型机和小型机的操作系统中。成组链接法空闲表法和空闲链法都不适用于大型文件系统。UNIX系统采用的成组链接法，可看作是两种方法的结合，兼具前两者的优点而克服了两者的缺点。（1）空闲盘块号栈(临界资源)存放当前可用的一组空闲盘块的盘块号，以及栈中尚有的空闲盘块号数N。N 还可兼作栈顶指针用。S.free(0)是栈底，栈满时栈顶为S.free(99)。（2）文件区中的所有空闲盘块被分成若干个组，图中，每个盘块大小为1KB，第一组为201300号盘块，第二组为301400号盘块， ，最末一组盘块号是79017999。空闲盘块号栈以及300、400、 、7900号盘块均含有S.free(0)S.free(99)和N，专心-专注-专业