操作系统基础复习题纲.ppt

1、复习题纲,操作系统基础（2000级）,掌握计算机软件的分类、操作系统的概念、微程序、命令解释器、操作系统的工作状态、用户软件的工作状态、操作系统的作用、进程、文件、虚拟机、系统调用以及系统结构等基本概念；并在掌握操作系统概念的基础上能够区分哪些指令是特权指令、哪些指令是非特权指令；CPU状态：管理状态与用户状态。,第一部分 引言,第二部分 进程,掌握进程的基本概念、进程的特点、进程的状态以及状态之间的转化关系、线程的概念、线程实现的两种方式以及相应的特点；掌握进程通信中的基本概念内容包括竞争条件、临界区、互斥、临界区的求解原则、信号量、进程调度所需要考虑的因素、具体的各种进程调度算法（先来先服

2、务、时间片轮转、优先级调度、多重队列、最短作业优先算法）等； 能够运用所学的进程通信的知识，分析软件算法中所存在的问题，并能够在分析问题的基础上能运用相应的知识解决实际应用中的相应问题；,第三部分 输入/输出系统,掌握：I/O设备的硬件软件原理，能够区分相关的I/O操作具体是在拿一软件层次上完成。了解死锁的定义、死锁发生的必要条件以及处理死锁的策略，针对于这些处理策略有哪些相应的算法来解决；磁盘软件以及磁盘臂调度算法、磁盘出错的处理等，掌握时钟软件所完成的任务 运用：根据系统给出的资源分配图能够分析判断系统的状态；根据实际的情况能够对I/O设备的处理进行优化设置；,第四部分 存储器管理,存储器

3、的重定位和保护； 固定分区与可变分区的概念； 可变分区的内存管理以及使用链表的内存管理中的分配算法； 分页的虚拟存储器的实现过程，虚拟地址到物理地址的转化过程； 页面的替换算法； 分页系统中的设计问题；,第五部分 文件系统,文件系统的基本概念：文件命名、文件结构、文件类型、文件存储、文件属性、文件操作、层次目录系统、路径名称、目录操作；掌握文件系统的实现（文件的实现、目录实现）、磁盘空间的管理、文件系统的可靠性、文件系统的性能；安全性,一、考试题型,判断个 个大题（分） 算法应用 应用理论 编程应用,二、复习纲要,作业调度 进程调度,FCFS.SJF.RR(Round Robin),时间片轮转

4、,3.内外存交换调度（页面置换） OPT （clock policy） FIFO、LRU Secondchance变境强型（NUR） P页 4.磁盘空白块管理算法 位图链表 FF.NF.BF.WF.伙伴,磁盘读写臂调度算法 FCFS、SSTF、SCAN、LOOK. 地址映射与转换 虚地址与实地址，地址转换图,UNIX文件系统结构与i结点。 P.V操作、读写者问题（读者优先）？ 9 资源管理，死锁分析与研究,三、例题讲解,例假设系统由相同类型的m个资源组成，系统有n个进程，每个进程至少请求一个资源，证明：当n个进程最多需要的资源之和小于m+n时，该系统无死锁。,解：,证明：假设当n个进程最多需要

5、的资源之和小于m+n，系统死锁。,因为系统死锁, 至少在一个Pi 其Needi=0，此时Pi不死锁，与假设题意矛盾，所以系统不死锁。,2. 某系统中有六台打印机，N个进程共享打印机资源，每个进程要求两台，试问N取哪些值时，系统才不会发生死锁？,解：由上可知,证：n个进程最多需要的资源之和小于6+n时，该系统无死锁，即2n6+n，n6。, n取值为1，2，3，4，5,另证：如下图所示：,当n=6时，最糟情况有：,每一进程已占有一个资源，还申请一个资源，此时死锁。,同理n6时系统也会出现死锁。,而n=5时，最糟情况下也会有,此时可化简为完全可化简图，不死锁。,同理1n5时也不死锁， n取值为1，2

6、，3，4，5。,例题2. 设某系统有一256k的空白区，现有以下作业序列和对内存的要求：,作业1要140k，作业2要求16k，作业3要求80k，作业1完成，作业3完成，作业4要求70k，作业5要求128k。,试用首次适应和最佳适应算法对上述作业进行可变分区存贮分配(绘图)并讨论。,解：,例题3. 在一个请求页式存储系统中，一程序的页面走向为4.3.2.1.4.3.5.4.3.2.1.5采取LRU页面置换算法，设分配给该程序的存储块数M分别为3和4时，请求出在访问过程中发生的缺页次数和缺页率，并比较所得结果，从中可得到什么启发？,解：,当M3时, 缺页10次，缺页中断率为,当M4时, 缺页7次，

7、缺页中断率为,在LRU算法下，当M增大时，缺页次数减少，缺页中断率也减少。,例题4. 假定五个作业AE提交时间相同，且实际需要运行的时间分别是10、6、2、4和8分钟，外部分配的优先级数分别是3、5、2、1和4，(设数值大的优先数高)。忽略CPU的切换时间，分别就下列几种调度算法计算作业的平均周转时间。a. 轮转法；b. 优先级调度；c. SJF,解：,(a) 轮转法：(时间片以及CPU切换时间都较小可忽略),C完成：25=10分钟,D完成：10+(42)4=18分钟,调度次序：C D B E A,E完成：24+(86)2=28分钟,A完成：28+(108)1=30分钟,B完成：18+(64)

8、3=24分钟,(b) 优先级调度,调度次序：B E A C D,(c) SJF,调度次序：C D B E A,例题5. 设有一个数据区，有若干进程要去读或写它，遵循下列原则：, 写是互斥的，当一进程正在写时，其它进程既不能写，也不能读；, 读可同时进行，只要没有进程正在写，则任何进程都可以读，请用P，V操作写出读写过程的同步算法(要给出信号量物理意义以及初值),答：var mutex, wrt: Semaphore;readcount: integer;mutex: = wrt: = 1;readcount: = 0;parbeginReaderi: beginWait (mutex);rea

9、dcount: = readcount + 1; if readcount = 1 then Wait (wrt);Signal (mutex);读数据集；Wait (mutex);readcount: = readcount 1; if readcount = 0 then Signal (wrt);Signal (mutex);endWriteri: begin Wait (wrt);写数据集;Signal (wrt);endcoend,例题6. 有一阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记信号，阅览室中共有100个座位，请问：,(1) 为描述读者的动作，应编写几个程序？设置几个进程？进程与程序间的对应关系如何？,(2) 用类Pascal语言和Wait, Signal操作写出这些进程间的同步算法。,答：(1) 应编写1个程序；设置2个进程；进程与程序间的对应关系是：多对1。,(2)beginS1:=100 (有100个座位)S2:=0 (有没阅读者)mutex: =1cob