操作系统复习指导(共10页).doc

精选优质文档-倾情为你奉上操作系统期末复习第一章 操作系统引论学习重点：1. 什么是操作系统：操作系统是控制和管理计算机系统内各种硬件和软件资源、有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口；2. 操作系统的主要功能：处理机管理：作业和进程调度、进程控制和进程通信；存储器管理：内存分配、地址映射、内存保护和内存扩充；设备管理：缓冲区管理、设备分配、设备驱动和设备无关性；文件管理：文件存储空间的管理、文件操作的一般管理、目录管理、文件的读写管理和存取控制、文件的逻辑结构和物理结构；用户接口功能：命令界面、程序界面、图形界面；3. 操作系统的基本特征（2个最基本的特征是并发和共享）:并发：两个或多个活动在同一给定的时间间隔内进行；共享：计算机系统中的资源被多个任务所共用。虚拟：虚拟处理机、虚拟内存、虚拟外设等。异步：多道程序下，各程序的执行过程由程序执行时的现场决定。4. 三种基本类型的操作系统：批处理系统：用户作业成批的处理，作业建立、过渡、完成都自动由系统成批完成，且在计算机内存中同时存放几道相互独立的程序，使它们在管理程序的控制下，相互穿插运行。分时系统：系统内存在若干并发程序对CPU时间片共享使用。实时系统：计算机对于外来信息能够以足够快的速度进行处理，并在被控对象允许的时间范围内做出快速反应。5. 分时概念：分时主要指若干并发进程对CPU时间的共享；6. 现代操作系统的三种用户界面：命令界面、图形界面和系统调用。7. 操作系统的发展过程：单道批处理系统多道批处理系统分时系统实时系统第二章 进程管理学习重点：1. 什么是进程，进程与程序的区别和关系：进程：进程是可以和别的计算并发执行的计算；进程是程序的一次执行，是在给定内存区域中的一组指令序列的执行过程；进程是一个程序在给定活动空间和初始条件下在一个处理机上的执行过程；进程可定义为一个数据结构和能在其上进行操作的一个程序；进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。进程与程序的区别：程序是静态概念，而进程是程序的一次执行过程，是动态概念。 进程是一个能独立运行的单位，能与其它进程并发执行。进程是作为申请和调度单位存在的；而通常的程序是不能作为一个独立运行的单位而并发执行的。 程序和进程无一一对应关系。 各个进程在并发执行过程中会产生相互制约关系，而程序本身是静态的，不存在这种异步特征。2. 进程的两个基本属性：可拥有资源的独立单位、可独立调度和分派的基本单位3. 进程的特征：动态性、并发行、独立性、异步性、结构特征4. 进程的基本状态及其变化：三种基本状态：运行态：当前进程已分配到CPU，它的程序正在处理机上运行；就绪态：进程已具备运行条件，但因为其它进程正占用CPU，所以暂时不能运行而等待分配CPU的状态；阻塞态：因等待某件事件发生而暂时不能运行的状态。就绪运行：被调度程序选中，分配到CPU。运行阻塞：因缺乏某种条件而放弃对CPU的占用。阻塞就绪：阻塞态进程所等待的事件发生了。运行就绪：进程用完时间片（分时系统中）或一个优先权更高的进程进入就绪队列（“优先权高优先”调度算法中）。有些操作系统中增加了两种状态：新状态和终止状态5. 某些操作系统中引入的进程的挂起状态（静止状态）- 挂起就绪、挂起阻塞；6. 进程由哪些部分组成，进程控制块的作用：进程由PCB、程序段和相关数据段组成；进程控制块是进程组成中最关键的部分，PCB是进程存在的唯一标志，每个进程有唯一的进程控制块，操作系统根据PCB对进程实施控制和管理，PCB是进程存在的唯一标志。7. 进程的切换（处理机从一个进程转到另一个进程），可能引起进程切换的时机（进程运行结束；进程从运行态变为就绪态；进程从运行态变为等待态；进程从等待态变为就绪态）；8. 并发进程间两种相互制约关系：什么是进程的同步（直接制约关系）与互斥（间接制约关系）：进程的同步：进程间共同完成一项任务时直接发生相互作用的关系；进程的互斥：两个逻辑上本来完全独立的进程由于竞争同一个物理资源而相互制约。9. 多道程序设计概念： 多道程序设计是在一台计算机上同时运行两个或更多个程序，多道程序设计具有提高系统资源利用率和增加作业吞吐量的优点；10. 处理机的两种执行状态：管态和目态；11. 什么是临界资源、临界区：临界资源：一次仅允许一个进程使用的资源；临界区：每个进程访问临界资源的那段程序。12. 进程同步的机制：信号量机制和管程机制。13. 信号量机制中包括：a整型信号量 b记录型信号量（重点）c AND型信号量。14. 什么是信号量，PV操作的动作，进程间简单同步与互斥的实现。信号量：也叫信号灯，记录型信号量是由两个成员组成的数据结构，其中一个成员是整型变量，表示信号量的值，另一个是进程链表L，用于链接等待进程。信号量的值与相应资源的使用情况有关。互斥信号量：初值为1；资源信号量：初值为资源的数目；P、V操作（也叫wait、signal操作）执行的动作。P操作的动作：信号量S.value减1，即S.value=S.value-1；如果S.value0，则该进程继续执行；否则放到另一个分量进程链表中等待。V操作的动作：S.value加1，即S.value=S.value+1；如果S.value0，则该进程继续执行；否则唤醒进程链表中的第一个等待进程。wait和signal操作描述： wait(S)： S.value:=S.value-1; if S.value<0 then block(S.L); signal(S): S.value:=S.value+1; if S.value<=0 then wakeup(S.L); 15. 三个经典的进程同步问题：生产者-消费者问题P58、读者-写者问题P63、哲学家进餐问题P62。能够使用信号量及PV操作解决进程的同步问题。16. 进程同步的例题1： 一条南北方向的公路桥，任何时刻同时只能允许一个方向的汽车通过它。试用P、V操作写出南或北向的一辆车到达桥，通过它，然后离开它到达对岸的同步算法（桥上可有多辆车）。分析：本题相当于两组读者进程互斥使用临界资源，同组的读者进程可同时读，但不同组的读者要争夺资源。为两组读者进程各设置一个计数器变量。设置分别用来计数两组读者数目的计数器变量c1和c2，初值均为0；两组读者进程互斥使用临界资源的互斥信号量sab（初值为1），两组进程互斥访问计数器变量c1和c2的互斥信号量s1和s2，初值为1。semaphore sab=1,s1=1,s2=1; int c1=0,c2=0;main() cobegin south(); north(); coend south() wait(s1); if c1=0 then wait(sab); c1:=c1+1; signal(s1); 上桥;过桥;下桥; wait(s1); c1:=c1-1; if c1=0 then signal(sab); signal(s1);north() wait(s2); if c2=0 then wait(sab); c2:=c2+1; signal(s2); 上桥;过桥;下桥; wait(s2); c2:=c2-1; if c2=0 then signal(sab); signal(s2);如果增加一个条件：公路桥的最大载重负荷为4辆汽车，应如何修改？ 增加一个资源信号量count，初值为4； 在“上桥;过桥;下桥”语句前面加上 wait(count)，后面加上signal(count)进程同步的例题2： 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题： (1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。 (2)根据所定义的信号量，把应执行的PV操作填入下述方框中，以保证进程能够正确地并发执行。COBEGIN PROCESS Pi(i=1 ， 2 ， ) begin ( )； 进入售票厅； 购票； 退出； ( )；end ； COEND (3) 若欲购票者最多为 n 个人，写出信号量可能的变化范围 ( 最大值和最小值 ) 。解答：（1）定义一信号量 S ，初始值为 20 。意义： S>0 S的值表示可继续进入售票厅的人数； S=0 表示售票厅中已有20名顾客(购票者)； S<0 |S|的值为等待进入售票厅的人数。 （2）上框为 P(S) 下框为 V(S) （3）S 的最大值为 20 S 的最小值为 20 n进程同步的例题3： 某寺庙，有小和尚、老和尚若干。有一水缸，由小和尚用水桶从井中提水入缸，老和尚用水桶从缸里取水饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容一个水桶取水。水桶总数为3个。每次入、取缸水仅为1桶，且不可以同时进行。试用P、V操作给出小和尚、老和尚动作的算法描述。分析： 小和尚从井中取水并向缸中倒水为一个进程，而老和尚从缸中取水为另一个进程。 有关互斥的资源有： 水井（一次仅允许一个水桶进出）； 水缸（一次倒水、取水仅一个水桶）。 分别为它们设置信号量mutex1、mutex2来实现互斥，初值均为1。有关同步的问题是： 3个水桶-无论是从井中取水还是倒水入缸或取水出缸都是一次一个，即为其设置信号量count，初值为3，抢不到水桶的进程只好等待。 此外，设置信号量empty来控制入缸的水量，初值为10，当水缸满时不可入水；设置信号full控制出缸的水量，初值为0，当水缸空时不可出水。Begin mutex1:=1;mutex2:=1; empty:=10;full:=0; count:=3; Cobegin 小和尚i（i=1,2,）打水； 老和尚j（j=1,2,）取水； Coend;End.小和尚i（i1,2,）打水: Begin Repeat P(empty); /*看水缸满否,满则阻塞打水进程*/ P(count); /*申请打水的桶*/ P(mutex1);/*互斥使用水井,即不允许两和尚同时打水*/ 从井中取水； V(mutex1); P(mutex2); /*互斥使用水缸*/ 送水入缸; V(mutex2); V(count); /*归还水桶*/ V(full) /*水缸又多一桶水*/ Until false End;老和尚j(j=1,2,)取水: Begin Repeat P(full); /*看水缸是否有水，无水则阻塞取水进程*/ P(count); /*申请取水的桶*/ P(mutex2); /*互斥使用水缸*/ 从缸中取水； V(mutex2); V(count) /*归还水桶*/ V(empty); /*缸中少了一桶水*/ Until false End17. 进程通信三种高级通信方式：共享存储器系统、消息传递系统（直接通信方式和间接通信方式信箱）、管道通信。18. 线程：什么是线程？有哪几种基本状态？为什么要在操作系统中引入线程？ -线程是一种比进程更小的能独立运行的基本单位，基本状态有三种执行，就绪，堵塞。引入线程的目的是为了减少程序的时空开销，使OS能具有更好的并发性。19. 线程的属性：是一种轻型进程；独立调度和分派的基本单位；可并发执行；共享所属进程所拥有的资源。20. 线程是调度的基本单位（即是分配CPU的基本单位），而进程是资源分配的基本单位。第三章 处理机调度与死锁学习重点：1. 三级调度：作业调度（高级调度或长程调度）、中级调度和进程调度（低级调度）。2. 进程调度的两种方式： 剥夺式调度和非剥夺式调度（或抢占式调度和非抢占式调度）。3. 调度算法：先来先服务调度法（FCFS）、短作业/短进程优先调度算法（SJF/SPF，分为剥夺式和非剥夺式，剥夺式短作业优先调度算法又叫最短剩余时间优先调度算法）、时间片轮转调度法（RR）、高优先权优先调度算法、高响应比优先调度算法；会用各种调度算法计算作业调度次序和作业的平均周转时间、平均带权周转时间。4. 评价调度算法的指标：吞吐量、周转时间、平均周转时间、带权周转时间和平均带权周转时间；5. 什么是死锁；-多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。6. 产生死锁的原因和四个必要条件；产生死锁的原因有两点：a竞争资源 b进程间推进顺序非法。四个必要条件：a互斥条件 b请求保持条件 c不剥夺条件 d环路等待条件。7. 处理死锁的四种方法：预防死锁、避免死锁、检测死锁和解除死锁。8. 死锁预防的基本思想和可行的解决办法（从产生死锁的四个必要条件出发）；9. 什么是进程的安全序列，死锁与安全序列的关系；-系统能按某种顺序（P1,P2，Pn）,来为每个当系统进入进程分配所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利的完成。-虽然并非所有的比安全状态都会转为死锁状态，但当系统进入不安全状态时，便有可能进入死锁状态。10. 死锁的避免与银行家算法，会用银行家算法判断某一时刻系统状态是否安全以及当某进程提出资源请求时能否分配。 设Requesti是进程Pi的请求向量，设Requesti j =k，表示进程Pi请求分配Rj类资源k个。当进程Pi 发出资源请求后，系统按如下步骤进行检查：(1)如RequestijNeedi,j,转(2);否则出错，因为进程申请资源量超过它声明的最大量。(2)如Requestij Availablej,转(3);否则表示资源不够，需等待。(3)系统试分配资源给进程Pi，并作如下修改：Availablej:= Availablej- RequestijAllocationi,j:= Allocationi,j+ RequestijNeedi,j:= Needi,j- Requestij(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，则正式进行分配，否则恢复原状态，让进程Pi等待。具体例题见书上110页。11. 资源分配图、死锁定理、死锁的检测和解除。第四章 存储器管理学习重点：1. 存储器管理的功能：内存分配、地址映射、内存保护、内存扩充；2. 内存以字节为单位进行编址，CPU按内存中的地址读出内存中的内容；3. 用户程序的主要处理阶段：编辑、编译、链接、装入、运行；4. 相对地址、绝对地址、重定位（静态重定位和动态重定位）的概念（地址重定位的对象是目标程序）、内存碎片；5. 内存的连续分配方式：单一连续分配方式、固定分区分配方式、动态分区分配方式（分配算法：首次适应算法将空闲分区按地址顺序从小到大登记在空闲分区表中、循环首次适应算法、最佳适应算法将空闲分区按长度大小递增的顺序登记在空闲分区表中、最坏适应算法-将空闲分区按长度大小递减的顺序登记在空闲分区表中）、可重定位分区分配方式（采用移动的技术）；6. 内存回收时的四种情况；7. 内存的离散分配方式：基本分页存储管理方式、基本分段存储管理方式、段页式存储管理方式；8. 基本分页存储管理方式：基本原理、页面（页是信息的物理单位）、地址机构（一维的）、页框、页表、地址变换机构（能够画出地址变换图、会把逻辑地址转换成物理地址）、没有快表的情况下访问一条指令或取得一个数据需2次访问内存（一次访问页表，一次根据物理地址取得指令或数据）、具有快表（联想存储器）的地址变换机构、具有联想存储器时根据命中率计算数据访问时间；9. 例题1： 在分页系统中地址结构长度为16位，页面大小为2K，作业地址空间为6K，该作业的各页依次存放在2、3、6号物理块中，相对地址2500处有一条指令store 1,4500，请给出该作业的页表，该指令的物理单元和数据存放的物理单元。解答：页面大小为2KB，作业地址空间为6KB，该作业被硬件自动分为3个页面，页面号分别为0、1、2，由题目知：各页依次存放在2、3、6号物理块中，所以页表为：页号物理块号021326逻辑地址2500所在页面号为2500 div 2048=1，页内地址为2500 mod 2048=452，查页表，1号页面装入3号物理块中，所以物理地址为：2K*3+452=6596由题目知，数据所在逻辑地址为4500，求得页面号为2，页内地址为404，查页表，对应的物理块号为6，故物理地址为：2K*6+404=1269210. 基本分段存储管理方式：基本原理、段（段是信息的逻辑单位）、地址结构（二维的）、段表、地址变换机构（能够画出地址变换图、会把逻辑地址转换成物理地址）、访问一条指令或取得一个数据需2次访问内存（一次访问段表，一次根据物理地址取得指令或数据）、分段和分页的区别、段式存储管理易于实现信息的共享；11. 段页式存储管理方式：基本原理、段表（一个用户进程有一个段表）、页表（用户进程有几段就有几个页表）、地址变换机构、访问一条指令或取得一个数据需3次访问内存（一次访问段表，一次访问该段所对应的页表，一次根据物理地址取得指令或数据）；12. 虚拟存储器：定义、特征、虚拟存储器的实现方式；虚拟存储器可管理的空间直接取决于处理器中地址寄存器的位数；13. 请求分页存储管理：在基本分页存储管理基础上增加了请求调页功能和页面置换功能、必需的硬件支持有：请求分页的页表机制、缺页中断机构、地址变换机构；14. 请求分页存储管理中的页面置换算法：最佳置换算法、先进先出页面置换算法（FIFO）-会产生Belady异常现象、最近最久未使用置换算法（LRU），能够根据某种页面置换算法计算缺页次数和缺页率；15. 性能比较：OPT：理论上性能最优，但无法实现； LRU：性能较好，但实现起来困难； FIFO：简单易行，但性能较差。16. 请求分段存储管理：在基本分段存储管理基础上增加了请求调段功能和段的置换功能、必需的硬件支持有：请求分段的段表机制、缺段中断机构、地址变换机构；17. 虚拟段页式存储管理第五章 设备管理学习重点：1. 设备管理功能：监视设备状态，进行设备分配，完成I/O操作，缓冲管理与地址转换。2. 设备的一般分类（按信息交换单位分类）：存储设备（块设备），输入/输出设备（字符设备）。3. 设备、设备控制器、通道（什么是通道？通道是一个独立于CPU专门管理输入输出的处理机，它控制外设与内存之间的信息交换。）4. 一个进程只有在获得了设备控制器、通道和所需设备后，才具备了进行I/O操作的物质条件。5. I/O控制方式（四种）：程序I/O方式、中断驱动I/O控制方式、直接存储器访问DMA I/O控制方式和I/O通道控制方式（需要CPU干预最少，I/O操作是由通道执行通道程序完成的）。6. 使用缓冲技术的目的（为了缓和CPU和I/O设备速度不匹配的矛盾）以及缓冲区的类型（单缓冲，双缓冲，循环缓冲，缓冲池）。7. 设备独立性概念及其优点；用户程序申请I/O设备时，通常采用逻辑设备名。8. 常用设备分配技术：独占分配，共享分配，虚拟分配；9. 设备分配时所使用的数据结构（四张表：设备控制表-DCT、控制器控制表-COCT、通道控制表-CHCT、系统设备表-SDT）。10. 设备分配算法：先来先服务、优先级高者优先。11. SPOOLing系统的组成（三个部分：输入井和输出井，输入缓冲区和输出缓冲区，输入进程SPi和输出进程SPo）、功能（提高I/O速度，将独占设备改为共享设备，实现虚拟设备功能）和实现思想（在联机情况下实现外围操作）。12. 如何实现共享打印机。用户请求打印后：1.由输出进程SPo在输出井中为之申请一个空闲磁盘块区， 并将要打印的数据送入其中； 2.输出进程SPo再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到请求打印队列上。3. 打印机空闲时，首先取第一张请求表，将数据从输出井传送到内存缓冲区，进行打印。13. 磁盘存储器管理：各种磁盘调度算法。先来先服务FCFS最短寻道时间优先SSTF扫描算法扫描(SCAN)算法循环扫描(CSCAN)算法N-STEP-SCAN调度算法FSCAN调度算法第六章 文件系统学习重点：1. 文件（在文件系统中是一个最大的数据单位，是指记录在外存上的具有文件名的一组相关信息的集合。可分为有结构文件和无结构文件两种。有结构文件由若干个相关记录组成，而无结构文件则被看成一个字符流）、文件系统的概念；2. 文件的逻辑结构：从用户的观点所看到的文件组织，分为：有结构文件（记录式文件）和无结构文件（流式文件）；3. 文件的物理结构（文件在外存上的实际存放形式，即外存的分配方式，分配存储空间的基本单位是块）及各自的特点：连续分配形成顺序文件（不便于文件的扩充）、链接分配形成链接文件（隐式链接和显示链接）、索引分配形成索引文件（一级索引分配、多级索引分配、混合索引分配方式会计算采用该方式的文件系统所能支持的单个文件的最大长度）；4. UNIX操作系统（分时操作系统）所采用的外存分配方式：混合索引分配方式（能够画图）、对空闲块的管理采用成组链接法；5. 在UNIX中，如果一个盘块的大小为1KB，每个盘块号占4个字节，即每块可放256个地址。请将下列文件的字节偏移量转换为物理地址： （1）9999 （2）18000 （3）解答：（1）9999 9999 div 1024=9; 9999 mod 1024=783 物理地址：第10个直接地址项所指的物理块，偏移量783 （2）18000 18000 div 1024=17，18000 mod 1024=592，为一次间接寻址方式。09块为直接地址，从一次间址块中读出第8个盘块号，在该块中的第592字节处即为文件的第18000字节。 （3） 前10个直接地址：10240B，一次间址：256×1024= -10240-= 二次间址：256×256块 div 1024=144 偏移量160 第10+256+145=411块6. 目录（文件系统通过目录来管理文件）和目录结构：目录项、索引结点（即i结点）、目录结构-单级目录结构、两级目录结构（解决不同用户文件重名的问题）、多级目录结构（树型目录结构）、目录查询技术（线性检索法）；7. 文件存储空间的管理：空闲表法（空闲链表法）、位示图法（会计算位示图所占的空间）、成组链接法（UNIX操作系统所采用的文件存储空间管理的方法）；8. 文件的共享：基于索引结点的共享方式、利用符号链实现文件共享；9. 文件的存取方式：顺序存取和随机存取（直接存取）；第七章 操作系统接口学习重点：1 联机命令接口；2 系统调用接口（程序员接口）；3 图形用户接口。第八章 操作系统实验学习重点：实验一实验三重点：fork()系统调用v 如果失败则返回-1v 父进程和子进程均在fork之后的语句开始执行n for child, fork() returns 0n for parent, fork() returns the PID of the child专心-专注-专业